From patchwork Tue Jan 16 12:00:05 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Github ODP bot X-Patchwork-Id: 124661 Delivered-To: patch@linaro.org Received: by 10.46.64.148 with SMTP id r20csp988557lje; Tue, 16 Jan 2018 04:03:05 -0800 (PST) X-Google-Smtp-Source: ACJfBovm+i6Hy4LXeqUAoWtpEiDDWKfQBcVvyGNht8lH3bMNMwoKV2Rp4v1t7XbRxJxLXRjse7sj X-Received: by 10.55.25.234 with SMTP id 103mr53655632qkz.217.1516104185038; Tue, 16 Jan 2018 04:03:05 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1516104185; cv=none; d=google.com; s=arc-20160816; b=imPJ+96MoWpWCn9QHuRkSPY1lihn539LsvGGHWKscmkbbuai9Ajbz1htX5GENONmCg JX1r98uaqiBfDyQpatDnPL3x6G3TiMRjv4tS+bAxTb4ocR7A9EQMd29N31znrptgEDn0 SizCXCoDhm0Gu+OFVRuXpWjbJgNC/MeXkxj4QaWjI2Fwm+iuZdK1ARpIxnxXCtqC5EdB 3QqOdb0sZjO6TFsjKNdl4q7gI/SOZAuRsaMfXSIo77onoogaDRp4Qa5Dp6Fotz6c765B wIqsEahXfK4DSM8ggkaTZuJFcamULlSefAqt8JycxKW4dE0WB2HXL7C66qcxbSwGj3wt AjWQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:subject:github-pr-num :references:in-reply-to:message-id:date:to:from:delivered-to :arc-authentication-results; bh=z2OATuWcdA+ZZUY2m6Huln2WgniYZWNvjjQQZhWxxls=; b=s0I9Twcdn77N+yY4ATSPGETTtQIQ3F0lN5EMB5IeaP5A8fr3AyjMyCKQ19qnOXd3WD CM78dJAf36GrS3eDsIb2Lscx3PTIn1/fbulTnNgcrQkzLqG1XN082m0YwqomQzYBaUF1 yGxohfyVWorDSNX0AHnCl7ykr54ez9nhHY+uLW8EaLxJOo74lkqos9lfCYqW7QLDrawL 1bR3TFkEWUTx370XUhz1WWM4kwimdCR8cqFjIrbjruaOEox+dFkzacmVDzCK87STLf0g VShOMNjjd4GaDlkOqsA6QjzdXqnmZRdfQemnkbbkrfeD1lXQ9jS2qTko8tL4mJmnaNqZ O4yw== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.197.127.237 as permitted sender) smtp.mailfrom=lng-odp-bounces@lists.linaro.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=yandex.ru Return-Path: Received: from lists.linaro.org (ec2-54-197-127-237.compute-1.amazonaws.com. [54.197.127.237]) by mx.google.com with ESMTP id c50si2143959qtk.86.2018.01.16.04.03.04; Tue, 16 Jan 2018 04:03:05 -0800 (PST) Received-SPF: pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.197.127.237 as permitted sender) client-ip=54.197.127.237; Authentication-Results: mx.google.com; spf=pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.197.127.237 as permitted sender) smtp.mailfrom=lng-odp-bounces@lists.linaro.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=yandex.ru Received: by lists.linaro.org (Postfix, from userid 109) id 8B468617BF; Tue, 16 Jan 2018 12:03:04 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on ip-10-142-244-252 X-Spam-Level: X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2 autolearn=disabled version=3.4.0 Received: from [127.0.0.1] (localhost [127.0.0.1]) by lists.linaro.org (Postfix) with ESMTP id 8489F617A6; Tue, 16 Jan 2018 12:01:07 +0000 (UTC) X-Original-To: lng-odp@lists.linaro.org Delivered-To: lng-odp@lists.linaro.org Received: by lists.linaro.org (Postfix, from userid 109) id E144F61798; Tue, 16 Jan 2018 12:00:49 +0000 (UTC) Received: from forward105o.mail.yandex.net (forward105o.mail.yandex.net [37.140.190.183]) by lists.linaro.org (Postfix) with ESMTPS id C6CE4617A8 for ; Tue, 16 Jan 2018 12:00:11 +0000 (UTC) Received: from mxback2g.mail.yandex.net (mxback2g.mail.yandex.net [IPv6:2a02:6b8:0:1472:2741:0:8b7:163]) by forward105o.mail.yandex.net (Yandex) with ESMTP id 63F854443DB1 for ; Tue, 16 Jan 2018 15:00:10 +0300 (MSK) Received: from smtp1j.mail.yandex.net (smtp1j.mail.yandex.net [2a02:6b8:0:801::ab]) by mxback2g.mail.yandex.net (nwsmtp/Yandex) with ESMTP id aIeQeCrd4R-0ANWv6sL; Tue, 16 Jan 2018 15:00:10 +0300 Received: by smtp1j.mail.yandex.net (nwsmtp/Yandex) with ESMTPSA id b7CVxjO9hV-09gKr6EX; Tue, 16 Jan 2018 15:00:09 +0300 (using TLSv1.2 with cipher ECDHE-RSA-AES128-SHA256 (128/128 bits)) (Client certificate not present) From: Github ODP bot To: lng-odp@lists.linaro.org Date: Tue, 16 Jan 2018 15:00:05 +0300 Message-Id: <1516104008-9628-2-git-send-email-odpbot@yandex.ru> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1516104008-9628-1-git-send-email-odpbot@yandex.ru> References: <1516104008-9628-1-git-send-email-odpbot@yandex.ru> Github-pr-num: 393 Subject: [lng-odp] [PATCH API-NEXT v1 1/4] api: queue: block-free capabilities X-BeenThere: lng-odp@lists.linaro.org X-Mailman-Version: 2.1.16 Precedence: list List-Id: "The OpenDataPlane \(ODP\) List" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: lng-odp-bounces@lists.linaro.org Sender: "lng-odp" From: Petri Savolainen Lock-free and wait-free implementations may differ a lot from the default (blocking) implementation. Thus the maximum number of queues and queue sizes may be more limited. Non-blocking enum is not needed anymore as capability, since number of queues may be zero for LF/WF when not implemented. Signed-off-by: Petri Savolainen --- /** Email created from pull request 393 (psavol:next-lockfree-queue-impl-rebased) ** https://github.com/Linaro/odp/pull/393 ** Patch: https://github.com/Linaro/odp/pull/393.patch ** Base sha: f6dab2bfa90ef5d3146cb76f86bc8782666f0f3e ** Merge commit sha: 3da13358015ca674abf51f61f539fcbf6607cb2d **/ include/odp/api/spec/queue.h | 74 +++++++++++++++++++++++------ platform/linux-generic/odp_queue.c | 2 - platform/linux-generic/odp_queue_scalable.c | 2 - test/validation/api/queue/queue.c | 2 - 4 files changed, 60 insertions(+), 20 deletions(-) diff --git a/include/odp/api/spec/queue.h b/include/odp/api/spec/queue.h index 79a26df3a..107ef3f75 100644 --- a/include/odp/api/spec/queue.h +++ b/include/odp/api/spec/queue.h @@ -164,35 +164,81 @@ typedef struct odp_queue_capability_t { /** Plain queue capabilities */ struct { - /** Maximum number of plain queues of the default size. */ + /** Maximum number of plain (ODP_BLOCKING) queues of the + * default size. */ uint32_t max_num; - /** Maximum number of events a plain queue can store - * simultaneously. The value of zero means that plain + /** Maximum number of events a plain (ODP_BLOCKING) queue can + * store simultaneously. The value of zero means that plain * queues do not have a size limit, but a single queue can * store all available events. */ uint32_t max_size; - /** The strongest guarantee of block freedom that is supported - * for plain queues. */ - odp_nonblocking_t nonblocking; + /** Lock-free (ODP_NONBLOCKING_LF) implementation capabilities. + * The specification is the same as for the blocking + * implementation. */ + struct { + /** Maximum number of queues. Lock-free queues are not + * supported when zero. */ + uint32_t max_num; + + /** Maximum queue size */ + uint32_t max_size; + + } lockfree; + + /** Wait-free (ODP_NONBLOCKING_WF) implementation capabilities. + * The specification is the same as for the blocking + * implementation. */ + struct { + /** Maximum number of queues. Wait-free queues are not + * supported when zero. */ + uint32_t max_num; + + /** Maximum queue size */ + uint32_t max_size; + + } waitfree; } plain; /** Scheduled queue capabilities */ struct { - /** Maximum number of scheduled queues of the default size. */ + /** Maximum number of scheduled (ODP_BLOCKING) queues of the + * default size. */ uint32_t max_num; - /** Maximum number of events a scheduled queue can store - * simultaneously. The value of zero means that scheduled - * queues do not have a size limit, but a single queue can - * store all available events. */ + /** Maximum number of events a scheduled (ODP_BLOCKING) queue + * can store simultaneously. The value of zero means that + * scheduled queues do not have a size limit, but a single + * queue can store all available events. */ uint32_t max_size; - /** The strongest guarantee of block freedom that is supported - * for scheduled queues. */ - odp_nonblocking_t nonblocking; + /** Lock-free (ODP_NONBLOCKING_LF) implementation capabilities. + * The specification is the same as for the blocking + * implementation. */ + struct { + /** Maximum number of queues. Lock-free queues are not + * supported when zero. */ + uint32_t max_num; + + /** Maximum queue size */ + uint32_t max_size; + + } lockfree; + + /** Wait-free (ODP_NONBLOCKING_WF) implementation capabilities. + * The specification is the same as for the blocking + * implementation. */ + struct { + /** Maximum number of queues. Wait-free queues are not + * supported when zero. */ + uint32_t max_num; + + /** Maximum queue size */ + uint32_t max_size; + + } waitfree; } sched; diff --git a/platform/linux-generic/odp_queue.c b/platform/linux-generic/odp_queue.c index 58103930c..6a69eb849 100644 --- a/platform/linux-generic/odp_queue.c +++ b/platform/linux-generic/odp_queue.c @@ -150,9 +150,7 @@ static int queue_capability(odp_queue_capability_t *capa) capa->max_sched_groups = sched_fn->num_grps(); capa->sched_prios = odp_schedule_num_prio(); capa->plain.max_num = capa->max_queues; - capa->plain.nonblocking = ODP_BLOCKING; capa->sched.max_num = capa->max_queues; - capa->sched.nonblocking = ODP_BLOCKING; return 0; } diff --git a/platform/linux-generic/odp_queue_scalable.c b/platform/linux-generic/odp_queue_scalable.c index 88a5a8c27..72dec15b0 100644 --- a/platform/linux-generic/odp_queue_scalable.c +++ b/platform/linux-generic/odp_queue_scalable.c @@ -315,10 +315,8 @@ static int queue_capability(odp_queue_capability_t *capa) capa->sched_prios = odp_schedule_num_prio(); capa->plain.max_num = ODP_CONFIG_QUEUES - NUM_INTERNAL_QUEUES; capa->plain.max_size = 0; - capa->plain.nonblocking = ODP_BLOCKING; capa->sched.max_num = ODP_CONFIG_QUEUES - NUM_INTERNAL_QUEUES; capa->sched.max_size = 0; - capa->sched.nonblocking = ODP_BLOCKING; return 0; } diff --git a/test/validation/api/queue/queue.c b/test/validation/api/queue/queue.c index 3c6db33ab..f674b0813 100644 --- a/test/validation/api/queue/queue.c +++ b/test/validation/api/queue/queue.c @@ -69,8 +69,6 @@ void queue_test_capa(void) CU_ASSERT(capa.sched_prios != 0); CU_ASSERT(capa.plain.max_num != 0); CU_ASSERT(capa.sched.max_num != 0); - CU_ASSERT(capa.plain.nonblocking >= ODP_BLOCKING); - CU_ASSERT(capa.sched.nonblocking >= ODP_BLOCKING); min = capa.plain.max_num; if (min > capa.sched.max_num) From patchwork Tue Jan 16 12:00:06 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Github ODP bot X-Patchwork-Id: 124659 Delivered-To: patch@linaro.org Received: by 10.46.64.148 with SMTP id r20csp987767lje; Tue, 16 Jan 2018 04:01:04 -0800 (PST) X-Google-Smtp-Source: ACJfBosSAknInl5VXUaBN8v1I3QFwWMi8KVohJ3vp+bjR6Hgnp/v74VarCxdbQrg2/dmSd4tgqgH X-Received: by 10.55.82.197 with SMTP id g188mr55929203qkb.335.1516104064584; Tue, 16 Jan 2018 04:01:04 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1516104064; cv=none; d=google.com; s=arc-20160816; b=VBkaMON/SCuZs1T7BXho3z19xi82eXs6iaqlncuaTrLl64qkm11NIuUBtZPSPET96W 6dIZX87qZwMFqsMEYWgl44UDGm1PTiDfORoA24nCz1IWn16gGZwlAyBYhur7xpjOLPR8 9rV7VCWvIOZ3Fzii78bC+olu9QN9ug5blBV6h76nOsJqql+qoyut3581BxhCh226ekvq MYeqZCWvqoBKg/aoCYsfLVfNnHZaoSsWbRvpxJiDJ9pkMF+ri8q+7cJfYC3ZDcuSXKzL 0tMzc/h5bAmvN9fezLj+gcZtkLO1j6WEx7TU7fJkkA0rP8t2JzIosP4HpivNGZeX9LZB dCHg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:subject:github-pr-num :references:in-reply-to:message-id:date:to:from:delivered-to :arc-authentication-results; bh=z958e/LHmgQ0ifbOnpJh7LpRII2+xdCDLujA+7eG1B0=; b=ZjvSMqUFHa7KghAhNN8/FbV9ZpIn9ghMylFgviiQOnIcPSzotXuAeJ2h9IJVdCFAp0 XF4es6iA0cI1nO1Xkkpv1ls2bsZGXC/1CZEhFDcDUideBzMyKrRjPEjvtt4KXkoqtf+X 2BtezB4BWBK1v/kMHUWcX60DYosDzbTl/pOi56BsSedayox8JDVwyNuRKxD+JWSpCTxv f9hL7oX28EqZ6HdMdDpTwVlFis8H0bkFv9eKcxNaH3H3LpMh1JwO80hXaoUzmIBSJpVL x2tdKAItF6GqWsZAQzrBSrggAaTAoRPJ2MifFmiaeUCbjUSprw3CHp43HenwLVBUFy2+ v7ow== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.197.127.237 as permitted sender) smtp.mailfrom=lng-odp-bounces@lists.linaro.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=yandex.ru Return-Path: Received: from lists.linaro.org (ec2-54-197-127-237.compute-1.amazonaws.com. [54.197.127.237]) by mx.google.com with ESMTP id 3si1259075qtt.39.2018.01.16.04.01.03; Tue, 16 Jan 2018 04:01:04 -0800 (PST) Received-SPF: pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.197.127.237 as permitted sender) client-ip=54.197.127.237; Authentication-Results: mx.google.com; spf=pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.197.127.237 as permitted sender) smtp.mailfrom=lng-odp-bounces@lists.linaro.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=yandex.ru Received: by lists.linaro.org (Postfix, from userid 109) id E1108617A8; Tue, 16 Jan 2018 12:01:03 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on ip-10-142-244-252 X-Spam-Level: X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL autolearn=disabled version=3.4.0 Received: from [127.0.0.1] (localhost [127.0.0.1]) by lists.linaro.org (Postfix) with ESMTP id D707361798; Tue, 16 Jan 2018 12:00:53 +0000 (UTC) X-Original-To: lng-odp@lists.linaro.org Delivered-To: lng-odp@lists.linaro.org Received: by lists.linaro.org (Postfix, from userid 109) id 55BB361798; Tue, 16 Jan 2018 12:00:48 +0000 (UTC) Received: from forward105j.mail.yandex.net (forward105j.mail.yandex.net [5.45.198.248]) by lists.linaro.org (Postfix) with ESMTPS id BC2F661785 for ; Tue, 16 Jan 2018 12:00:12 +0000 (UTC) Received: from mxback4j.mail.yandex.net (mxback4j.mail.yandex.net [IPv6:2a02:6b8:0:1619::10d]) by forward105j.mail.yandex.net (Yandex) with ESMTP id 25448183AE4 for ; Tue, 16 Jan 2018 15:00:11 +0300 (MSK) Received: from smtp1j.mail.yandex.net (smtp1j.mail.yandex.net [2a02:6b8:0:801::ab]) by mxback4j.mail.yandex.net (nwsmtp/Yandex) with ESMTP id 5iyQktTk8a-0BNG8dR9; Tue, 16 Jan 2018 15:00:11 +0300 Received: by smtp1j.mail.yandex.net (nwsmtp/Yandex) with ESMTPSA id b7CVxjO9hV-0AgaNdk0; Tue, 16 Jan 2018 15:00:10 +0300 (using TLSv1.2 with cipher ECDHE-RSA-AES128-SHA256 (128/128 bits)) (Client certificate not present) From: Github ODP bot To: lng-odp@lists.linaro.org Date: Tue, 16 Jan 2018 15:00:06 +0300 Message-Id: <1516104008-9628-3-git-send-email-odpbot@yandex.ru> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1516104008-9628-1-git-send-email-odpbot@yandex.ru> References: <1516104008-9628-1-git-send-email-odpbot@yandex.ru> Github-pr-num: 393 Subject: [lng-odp] [PATCH API-NEXT v1 2/4] validation: queue: test lock-free queue X-BeenThere: lng-odp@lists.linaro.org X-Mailman-Version: 2.1.16 Precedence: list List-Id: "The OpenDataPlane \(ODP\) List" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: lng-odp-bounces@lists.linaro.org Sender: "lng-odp" From: Petri Savolainen Added simple, single threaded enqueue/dequeue test for lock-free queues. Signed-off-by: Petri Savolainen --- /** Email created from pull request 393 (psavol:next-lockfree-queue-impl-rebased) ** https://github.com/Linaro/odp/pull/393 ** Patch: https://github.com/Linaro/odp/pull/393.patch ** Base sha: f6dab2bfa90ef5d3146cb76f86bc8782666f0f3e ** Merge commit sha: 3da13358015ca674abf51f61f539fcbf6607cb2d **/ test/validation/api/queue/queue.c | 121 +++++++++++++++++++++++++++++++++----- test/validation/api/queue/queue.h | 1 + 2 files changed, 106 insertions(+), 16 deletions(-) diff --git a/test/validation/api/queue/queue.c b/test/validation/api/queue/queue.c index f674b0813..1ff029176 100644 --- a/test/validation/api/queue/queue.c +++ b/test/validation/api/queue/queue.c @@ -10,9 +10,9 @@ #include #include "queue.h" -#define MAX_BUFFER_QUEUE (8) -#define MSG_POOL_SIZE (4 * 1024 * 1024) -#define CONFIG_MAX_ITERATION (100) +#define BURST_SIZE (8) +#define MAX_NUM_EVENT (1 * 1024) +#define MAX_ITERATION (100) #define MAX_QUEUES (64 * 1024) static int queue_context = 0xff; @@ -33,9 +33,11 @@ int queue_suite_init(void) { odp_pool_param_t params; - params.buf.size = 0; + odp_pool_param_init(¶ms); + + params.buf.size = 4; params.buf.align = ODP_CACHE_LINE_SIZE; - params.buf.num = 1024 * 10; + params.buf.num = MAX_NUM_EVENT; params.type = ODP_POOL_BUFFER; pool = odp_pool_create("msg_pool", ¶ms); @@ -153,18 +155,105 @@ void queue_test_mode(void) } } +static odp_event_t dequeue_event(odp_queue_t queue) +{ + odp_event_t ev; + int i; + + for (i = 0; i < MAX_ITERATION; i++) { + ev = odp_queue_deq(queue); + if (ev != ODP_EVENT_INVALID) + break; + } + + return ev; +} + +void queue_test_lockfree(void) +{ + odp_queue_param_t param; + odp_queue_t queue; + odp_queue_capability_t capa; + uint32_t max_burst, burst, i, j; + odp_pool_t pool; + odp_buffer_t buf; + odp_event_t ev; + uint32_t *data; + + CU_ASSERT_FATAL(odp_queue_capability(&capa) == 0); + + if (capa.plain.lockfree.max_num == 0) + return; + + max_burst = capa.plain.lockfree.max_size; + + if (max_burst == 0 || max_burst > MAX_NUM_EVENT) + max_burst = MAX_NUM_EVENT; + + pool = odp_pool_lookup("msg_pool"); + CU_ASSERT_FATAL(pool != ODP_POOL_INVALID); + + odp_queue_param_init(¶m); + param.type = ODP_QUEUE_TYPE_PLAIN; + param.nonblocking = ODP_NONBLOCKING_LF; + param.size = max_burst; + + queue = odp_queue_create("lockfree_queue", ¶m); + CU_ASSERT_FATAL(queue != ODP_QUEUE_INVALID); + + CU_ASSERT(odp_queue_deq(queue) == ODP_EVENT_INVALID); + + buf = odp_buffer_alloc(pool); + CU_ASSERT_FATAL(buf != ODP_BUFFER_INVALID); + ev = odp_buffer_to_event(buf); + CU_ASSERT(odp_queue_enq(queue, ev) == 0); + ev = dequeue_event(queue); + CU_ASSERT_FATAL(ev != ODP_EVENT_INVALID); + if (ev != ODP_EVENT_INVALID) + odp_event_free(ev); + + for (j = 0; j < 2; j++) { + if (j == 0) + burst = max_burst / 4; + else + burst = max_burst; + + for (i = 0; i < burst; i++) { + buf = odp_buffer_alloc(pool); + CU_ASSERT_FATAL(buf != ODP_BUFFER_INVALID); + data = odp_buffer_addr(buf); + *data = i; + ev = odp_buffer_to_event(buf); + CU_ASSERT(odp_queue_enq(queue, ev) == 0); + } + + for (i = 0; i < burst; i++) { + ev = dequeue_event(queue); + CU_ASSERT(ev != ODP_EVENT_INVALID); + if (ev != ODP_EVENT_INVALID) { + buf = odp_buffer_from_event(ev); + data = odp_buffer_addr(buf); + CU_ASSERT(*data == i); + odp_event_free(ev); + } + } + } + + CU_ASSERT(odp_queue_destroy(queue) == 0); +} + void queue_test_param(void) { odp_queue_t queue, null_queue; - odp_event_t enev[MAX_BUFFER_QUEUE]; - odp_event_t deev[MAX_BUFFER_QUEUE]; + odp_event_t enev[BURST_SIZE]; + odp_event_t deev[BURST_SIZE]; odp_buffer_t buf; odp_event_t ev; odp_pool_t msg_pool; odp_event_t *pev_tmp; int i, deq_ret, ret; int nr_deq_entries = 0; - int max_iteration = CONFIG_MAX_ITERATION; + int max_iteration = MAX_ITERATION; odp_queue_param_t qparams; odp_buffer_t enbuf; @@ -223,7 +312,7 @@ void queue_test_param(void) odp_buffer_free(buf); } - for (i = 0; i < MAX_BUFFER_QUEUE; i++) { + for (i = 0; i < BURST_SIZE; i++) { buf = odp_buffer_alloc(msg_pool); enev[i] = odp_buffer_to_event(buf); } @@ -233,23 +322,22 @@ void queue_test_param(void) * constraints in the implementation at that given point of time. * But here we assume that we succeed in enqueuing all buffers. */ - ret = odp_queue_enq_multi(queue, enev, MAX_BUFFER_QUEUE); - CU_ASSERT(MAX_BUFFER_QUEUE == ret); + ret = odp_queue_enq_multi(queue, enev, BURST_SIZE); + CU_ASSERT(BURST_SIZE == ret); i = ret < 0 ? 0 : ret; - for ( ; i < MAX_BUFFER_QUEUE; i++) + for ( ; i < BURST_SIZE; i++) odp_event_free(enev[i]); pev_tmp = deev; do { - deq_ret = odp_queue_deq_multi(queue, pev_tmp, - MAX_BUFFER_QUEUE); + deq_ret = odp_queue_deq_multi(queue, pev_tmp, BURST_SIZE); nr_deq_entries += deq_ret; max_iteration--; pev_tmp += deq_ret; CU_ASSERT(max_iteration >= 0); - } while (nr_deq_entries < MAX_BUFFER_QUEUE); + } while (nr_deq_entries < BURST_SIZE); - for (i = 0; i < MAX_BUFFER_QUEUE; i++) { + for (i = 0; i < BURST_SIZE; i++) { enbuf = odp_buffer_from_event(enev[i]); CU_ASSERT(enev[i] == deev[i]); odp_buffer_free(enbuf); @@ -326,6 +414,7 @@ void queue_test_info(void) odp_testinfo_t queue_suite[] = { ODP_TEST_INFO(queue_test_capa), ODP_TEST_INFO(queue_test_mode), + ODP_TEST_INFO(queue_test_lockfree), ODP_TEST_INFO(queue_test_param), ODP_TEST_INFO(queue_test_info), ODP_TEST_INFO_NULL, diff --git a/test/validation/api/queue/queue.h b/test/validation/api/queue/queue.h index 6b787b1d6..b85090707 100644 --- a/test/validation/api/queue/queue.h +++ b/test/validation/api/queue/queue.h @@ -12,6 +12,7 @@ /* test functions: */ void queue_test_capa(void); void queue_test_mode(void); +void queue_test_lockfree(void); void queue_test_param(void); void queue_test_info(void); From patchwork Tue Jan 16 12:00:07 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Github ODP bot X-Patchwork-Id: 124660 Delivered-To: patch@linaro.org Received: by 10.46.64.148 with SMTP id r20csp988121lje; Tue, 16 Jan 2018 04:02:04 -0800 (PST) X-Google-Smtp-Source: ACJfBovPbV+jWD9zBUMaiWynEbS/1cKb16h4LQBn8dtsQsVcCOWYBfoM/c4xCj1XGCK3I5dPJZ+u X-Received: by 10.237.45.7 with SMTP id h7mr18306482qtd.44.1516104124486; Tue, 16 Jan 2018 04:02:04 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1516104124; cv=none; d=google.com; s=arc-20160816; b=wKYHniMSm8xO0rUtyTd1n8nWe8AMIR6fdoR3Fu5umlzQ1OdjvXeINHH+zuLBbNdzY8 0D9OAQdw10CK2wcPpNa+EQsLp48R8obzVJKxfezs9OTC35cp2GK/PZUdlhYxcBZcHqSx kVGJXx+BPoJtLR5Pt9Lsjp6wtzSYbNBxbTleJw9xDMoLu38cQ+rnD44ucJmVdIcKv3hU 9iuvm/gYoWcZUH4zGxA53uNnCehf2QyKM6qAmaBd6gOiHFuyf4ENdpXbk+GunL50cosK T8yGuFmX25j1U9fgjJFZJKiEl6s6/rkDqFS+8Czc+18SaC45CKNbIZ142hCKQILt8str klWA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:subject:github-pr-num :references:in-reply-to:message-id:date:to:from:delivered-to :arc-authentication-results; bh=OOsUs22WKE1T9wLAr5NmuotfC/xz5HfAMZGsbmu1tnY=; b=du9Rlqh36/52YIHWeVpcL74lfhxaTOE6hB9/MXCBvWUW1LaqWBpGiSY2LG2OQbPxOG fBVl+i/Nxl1fL8Ct5ZjxUeWk+KYVRY5SXoK7AF9nAcW9rtUGZrZOqaX5o6Ejzu/Cx+zb li2nuyKbUA0PRMK5BOj7Kid7u/eVnx5hOVIFZa8OTNrM+hYHnusz7FX+IoAyhCtyo4tk Pzcpq/crU+16MAL8w7J56MliPKLKcv0AyMe0ifjCI5fRS0QrUFt9OyrsM2sdlVMydnpe Jxfu2fXqKQh3T+yZ4hh006dDIo1sOzdCuTogxnGBbuiPVN7n0V9Hz7qImsRWWD3LEnrq 7mlA== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.197.127.237 as permitted sender) smtp.mailfrom=lng-odp-bounces@lists.linaro.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=yandex.ru Return-Path: Received: from lists.linaro.org (ec2-54-197-127-237.compute-1.amazonaws.com. [54.197.127.237]) by mx.google.com with ESMTP id v14si1626699qka.385.2018.01.16.04.02.04; Tue, 16 Jan 2018 04:02:04 -0800 (PST) Received-SPF: pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.197.127.237 as permitted sender) client-ip=54.197.127.237; Authentication-Results: mx.google.com; spf=pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.197.127.237 as permitted sender) smtp.mailfrom=lng-odp-bounces@lists.linaro.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=yandex.ru Received: by lists.linaro.org (Postfix, from userid 109) id 26EA16179C; Tue, 16 Jan 2018 12:02:04 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on ip-10-142-244-252 X-Spam-Level: X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2 autolearn=disabled version=3.4.0 Received: from [127.0.0.1] (localhost [127.0.0.1]) by lists.linaro.org (Postfix) with ESMTP id 31F9A6179E; Tue, 16 Jan 2018 12:00:58 +0000 (UTC) X-Original-To: lng-odp@lists.linaro.org Delivered-To: lng-odp@lists.linaro.org Received: by lists.linaro.org (Postfix, from userid 109) id 68AB961785; Tue, 16 Jan 2018 12:00:49 +0000 (UTC) Received: from forward105p.mail.yandex.net (forward105p.mail.yandex.net [77.88.28.108]) by lists.linaro.org (Postfix) with ESMTPS id AD8E8617A9 for ; Tue, 16 Jan 2018 12:00:13 +0000 (UTC) Received: from mxback3j.mail.yandex.net (mxback3j.mail.yandex.net [IPv6:2a02:6b8:0:1619::10c]) by forward105p.mail.yandex.net (Yandex) with ESMTP id D02474082F96 for ; Tue, 16 Jan 2018 15:00:11 +0300 (MSK) Received: from smtp1j.mail.yandex.net (smtp1j.mail.yandex.net [2a02:6b8:0:801::ab]) by mxback3j.mail.yandex.net (nwsmtp/Yandex) with ESMTP id 7WwJBybcvk-0BQ4PqWJ; Tue, 16 Jan 2018 15:00:11 +0300 Received: by smtp1j.mail.yandex.net (nwsmtp/Yandex) with ESMTPSA id b7CVxjO9hV-0BgKuCPn; Tue, 16 Jan 2018 15:00:11 +0300 (using TLSv1.2 with cipher ECDHE-RSA-AES128-SHA256 (128/128 bits)) (Client certificate not present) From: Github ODP bot To: lng-odp@lists.linaro.org Date: Tue, 16 Jan 2018 15:00:07 +0300 Message-Id: <1516104008-9628-4-git-send-email-odpbot@yandex.ru> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1516104008-9628-1-git-send-email-odpbot@yandex.ru> References: <1516104008-9628-1-git-send-email-odpbot@yandex.ru> Github-pr-num: 393 Subject: [lng-odp] [PATCH API-NEXT v1 3/4] validation: queue: multi-thread plain queue test X-BeenThere: lng-odp@lists.linaro.org X-Mailman-Version: 2.1.16 Precedence: list List-Id: "The OpenDataPlane \(ODP\) List" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: lng-odp-bounces@lists.linaro.org Sender: "lng-odp" From: Petri Savolainen Test plain queue enqueue and dequeue with multiple concurrent threads. Test blocking and non-blocking lock-free implementations. Signed-off-by: Petri Savolainen --- /** Email created from pull request 393 (psavol:next-lockfree-queue-impl-rebased) ** https://github.com/Linaro/odp/pull/393 ** Patch: https://github.com/Linaro/odp/pull/393.patch ** Base sha: f6dab2bfa90ef5d3146cb76f86bc8782666f0f3e ** Merge commit sha: 3da13358015ca674abf51f61f539fcbf6607cb2d **/ test/validation/api/queue/queue.c | 258 +++++++++++++++++++++++++++++++++++++- 1 file changed, 257 insertions(+), 1 deletion(-) diff --git a/test/validation/api/queue/queue.c b/test/validation/api/queue/queue.c index 1ff029176..59a917c08 100644 --- a/test/validation/api/queue/queue.c +++ b/test/validation/api/queue/queue.c @@ -14,6 +14,22 @@ #define MAX_NUM_EVENT (1 * 1024) #define MAX_ITERATION (100) #define MAX_QUEUES (64 * 1024) +#define GLOBALS_NAME "queue_test_globals" +#define DEQ_RETRIES 100 +#define ENQ_RETRIES 100 + +typedef struct { + pthrd_arg cu_thr; + int num_workers; + odp_barrier_t barrier; + odp_queue_t queue; + odp_atomic_u32_t num_event; + + struct { + uint32_t num_event; + } thread[ODP_THREAD_COUNT_MAX]; + +} test_globals_t; static int queue_context = 0xff; static odp_pool_t pool; @@ -31,7 +47,30 @@ static void generate_name(char *name, uint32_t index) int queue_suite_init(void) { + odp_shm_t shm; + test_globals_t *globals; odp_pool_param_t params; + int num_workers; + odp_cpumask_t mask; + + shm = odp_shm_reserve(GLOBALS_NAME, sizeof(test_globals_t), + ODP_CACHE_LINE_SIZE, 0); + + if (shm == ODP_SHM_INVALID) { + printf("Shared memory reserve failed\n"); + return -1; + } + + globals = odp_shm_addr(shm); + memset(globals, 0, sizeof(test_globals_t)); + + num_workers = odp_cpumask_default_worker(&mask, 0); + + if (num_workers > MAX_WORKERS) + num_workers = MAX_WORKERS; + + globals->num_workers = num_workers; + odp_barrier_init(&globals->barrier, num_workers); odp_pool_param_init(¶ms); @@ -51,7 +90,25 @@ int queue_suite_init(void) int queue_suite_term(void) { - return odp_pool_destroy(pool); + odp_shm_t shm; + + shm = odp_shm_lookup(GLOBALS_NAME); + if (shm == ODP_SHM_INVALID) { + printf("SHM lookup failed.\n"); + return -1; + } + + if (odp_shm_free(shm)) { + printf("SHM free failed.\n"); + return -1; + } + + if (odp_pool_destroy(pool)) { + printf("Pool destroy failed.\n"); + return -1; + } + + return 0; } void queue_test_capa(void) @@ -411,12 +468,211 @@ void queue_test_info(void) CU_ASSERT(odp_queue_destroy(q_order) == 0); } +static uint32_t alloc_and_enqueue(odp_queue_t queue, odp_pool_t pool, + uint32_t num) +{ + uint32_t i, ret; + odp_buffer_t buf; + odp_event_t ev; + + for (i = 0; i < num; i++) { + buf = odp_buffer_alloc(pool); + + CU_ASSERT(buf != ODP_BUFFER_INVALID); + + ev = odp_buffer_to_event(buf); + + ret = odp_queue_enq(queue, ev); + + CU_ASSERT(ret == 0); + + if (ret) + break; + } + + return i; +} + +static uint32_t dequeue_and_free_all(odp_queue_t queue) +{ + odp_event_t ev; + uint32_t num, retries; + + num = 0; + retries = 0; + + while (1) { + ev = odp_queue_deq(queue); + + if (ev == ODP_EVENT_INVALID) { + if (retries >= DEQ_RETRIES) + return num; + + retries++; + continue; + } + + retries = 0; + num++; + + odp_event_free(ev); + } + + return num; +} + +static int enqueue_with_retry(odp_queue_t queue, odp_event_t ev) +{ + int i; + + for (i = 0; i < ENQ_RETRIES; i++) + if (odp_queue_enq(queue, ev) == 0) + return 0; + + return -1; +} + +static int queue_test_worker(void *arg) +{ + uint32_t num, retries, num_workers; + int thr_id, ret; + odp_event_t ev; + odp_queue_t queue; + test_globals_t *globals = arg; + + thr_id = odp_thread_id(); + queue = globals->queue; + num_workers = globals->num_workers; + + if (num_workers > 1) + odp_barrier_wait(&globals->barrier); + + retries = 0; + num = odp_atomic_fetch_inc_u32(&globals->num_event); + + /* On average, each worker deq-enq each event once */ + while (num < (num_workers * MAX_NUM_EVENT)) { + ev = odp_queue_deq(queue); + + if (ev == ODP_EVENT_INVALID) { + if (retries < DEQ_RETRIES) { + retries++; + continue; + } + + /* Prevent thread to starve */ + num = odp_atomic_fetch_inc_u32(&globals->num_event); + retries = 0; + continue; + } + + globals->thread[thr_id].num_event++; + + ret = enqueue_with_retry(queue, ev); + + CU_ASSERT(ret == 0); + + num = odp_atomic_fetch_inc_u32(&globals->num_event); + } + + return 0; +} + +static void reset_thread_stat(test_globals_t *globals) +{ + int i; + + odp_atomic_init_u32(&globals->num_event, 0); + + for (i = 0; i < ODP_THREAD_COUNT_MAX; i++) + globals->thread[i].num_event = 0; +} + +static void multithread_test(odp_nonblocking_t nonblocking) +{ + odp_shm_t shm; + test_globals_t *globals; + odp_queue_t queue; + odp_queue_param_t qparams; + odp_queue_capability_t capa; + uint32_t queue_size, max_size; + uint32_t num, sum, num_free, i; + + CU_ASSERT(odp_queue_capability(&capa) == 0); + + queue_size = 2 * MAX_NUM_EVENT; + + max_size = capa.plain.max_size; + + if (nonblocking == ODP_NONBLOCKING_LF) { + if (capa.plain.lockfree.max_num == 0) + return; + + max_size = capa.plain.lockfree.max_size; + } + + if (max_size && queue_size > max_size) + queue_size = max_size; + + num = MAX_NUM_EVENT; + + if (num > queue_size) + num = queue_size / 2; + + shm = odp_shm_lookup(GLOBALS_NAME); + CU_ASSERT_FATAL(shm != ODP_SHM_INVALID); + + globals = odp_shm_addr(shm); + globals->cu_thr.numthrds = globals->num_workers; + + odp_queue_param_init(&qparams); + qparams.type = ODP_QUEUE_TYPE_PLAIN; + qparams.size = queue_size; + qparams.nonblocking = nonblocking; + + queue = odp_queue_create("queue_test_mt", &qparams); + CU_ASSERT_FATAL(queue != ODP_QUEUE_INVALID); + + globals->queue = queue; + reset_thread_stat(globals); + + CU_ASSERT(alloc_and_enqueue(queue, pool, num) == num); + + odp_cunit_thread_create(queue_test_worker, (pthrd_arg *)globals); + + /* Wait for worker threads to terminate */ + odp_cunit_thread_exit((pthrd_arg *)globals); + + sum = 0; + for (i = 0; i < ODP_THREAD_COUNT_MAX; i++) + sum += globals->thread[i].num_event; + + CU_ASSERT(sum != 0); + + num_free = dequeue_and_free_all(queue); + + CU_ASSERT(num_free == num); + CU_ASSERT(odp_queue_destroy(queue) == 0); +} + +static void queue_test_mt_plain_block(void) +{ + multithread_test(ODP_BLOCKING); +} + +static void queue_test_mt_plain_nonblock_lf(void) +{ + multithread_test(ODP_NONBLOCKING_LF); +} + odp_testinfo_t queue_suite[] = { ODP_TEST_INFO(queue_test_capa), ODP_TEST_INFO(queue_test_mode), ODP_TEST_INFO(queue_test_lockfree), ODP_TEST_INFO(queue_test_param), ODP_TEST_INFO(queue_test_info), + ODP_TEST_INFO(queue_test_mt_plain_block), + ODP_TEST_INFO(queue_test_mt_plain_nonblock_lf), ODP_TEST_INFO_NULL, }; From patchwork Tue Jan 16 12:00:08 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Github ODP bot X-Patchwork-Id: 124662 Delivered-To: patch@linaro.org Received: by 10.46.64.148 with SMTP id r20csp988899lje; Tue, 16 Jan 2018 04:04:06 -0800 (PST) X-Google-Smtp-Source: ACJfBos+I4vZRjV9Q8BMQR6Qhgj1AB+MJOQ32vwVflSMJlZD1acnQ+cCLFrvRkJYABUzVrwS+eGH X-Received: by 10.13.225.69 with SMTP id k66mr12679223ywe.114.1516104245954; Tue, 16 Jan 2018 04:04:05 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1516104245; cv=none; d=google.com; s=arc-20160816; b=uk6dz9kOztTdyoHjVRL46+FcqB7M/EYIlfEvMAVZnVxbYtHnyG5ze2R7QYGCBHWjum WJ7GVjBZh/liMEYpRJh808og4cDNXxUqrltj6iwglzmw5wkb0vSZ/pzABnigCF7yQ4LB P7qfmh9gCqWRANoevX4NH52VlHKH8QsHMPmjJziG0ljcpRyaliB3wU6dRBYF7vMlM0gQ WZAne3cTCYxhAD3pttUjNCOrybvCaHQdWYR6QMv+4JNveWe5BXlmay+d/A4oBQRh5tN4 kPTgtxfZyE1o4i10GAbgs0NsHsrovQlp8RhPKLQbviKcQNtaSO7FaCuoLrXmfmSgPJT6 Kj4w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:subject:github-pr-num :references:in-reply-to:message-id:date:to:from:delivered-to :arc-authentication-results; bh=92W2Dknu9zwv3e5kS1GQuyWUxlwEmmjegSFH03bxXV0=; b=fgeuKOGd06pfTf6Xlw5adRFq2qOKYAoIpqRBim7AaLn6vmDWsyMoahqO/4RZw1l7Ed NGoihPfteNPXat6FCX4NVJEF/5jcvicTrmzwCXzCh5yl2bAYaqxYqAD0v07p8HVBU4SD 3B+Rawb9ytvUeQYmh/F70Q06v2Bve1y+EP/LDivfRz8Dnsg6dHqUe5HP56Vawee8qNYx 7kVC/ORZwD6LmjGGZJHRmSvaAvyo2n1poRoh+FXy3lmF0hf3iX/60icQypmm11Mp3b2M AKw/CixtQyJiYdAU7nRgfeYnEWcEd3VsYUsrZncLDmydM8GADx5fQzq1nyaLxJPO8tVF lwLw== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.197.127.237 as permitted sender) smtp.mailfrom=lng-odp-bounces@lists.linaro.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=yandex.ru Return-Path: Received: from lists.linaro.org (ec2-54-197-127-237.compute-1.amazonaws.com. [54.197.127.237]) by mx.google.com with ESMTP id t2si279245qkb.339.2018.01.16.04.04.05; Tue, 16 Jan 2018 04:04:05 -0800 (PST) Received-SPF: pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.197.127.237 as permitted sender) client-ip=54.197.127.237; Authentication-Results: mx.google.com; spf=pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.197.127.237 as permitted sender) smtp.mailfrom=lng-odp-bounces@lists.linaro.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=yandex.ru Received: by lists.linaro.org (Postfix, from userid 109) id 9082E617B2; Tue, 16 Jan 2018 12:04:05 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on ip-10-142-244-252 X-Spam-Level: X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL autolearn=disabled version=3.4.0 Received: from [127.0.0.1] (localhost [127.0.0.1]) by lists.linaro.org (Postfix) with ESMTP id D2768617A8; Tue, 16 Jan 2018 12:01:17 +0000 (UTC) X-Original-To: lng-odp@lists.linaro.org Delivered-To: lng-odp@lists.linaro.org Received: by lists.linaro.org (Postfix, from userid 109) id 2AC3961798; Tue, 16 Jan 2018 12:00:50 +0000 (UTC) Received: from forward103j.mail.yandex.net (forward103j.mail.yandex.net [5.45.198.246]) by lists.linaro.org (Postfix) with ESMTPS id EE42A617AC for ; Tue, 16 Jan 2018 12:00:13 +0000 (UTC) Received: from mxback7j.mail.yandex.net (mxback7j.mail.yandex.net [IPv6:2a02:6b8:0:1619::110]) by forward103j.mail.yandex.net (Yandex) with ESMTP id AE98B34C290F for ; Tue, 16 Jan 2018 15:00:12 +0300 (MSK) Received: from smtp1j.mail.yandex.net (smtp1j.mail.yandex.net [2a02:6b8:0:801::ab]) by mxback7j.mail.yandex.net (nwsmtp/Yandex) with ESMTP id 0CfQPpy2mi-0CAqum0x; Tue, 16 Jan 2018 15:00:12 +0300 Received: by smtp1j.mail.yandex.net (nwsmtp/Yandex) with ESMTPSA id b7CVxjO9hV-0Bgudn1Z; Tue, 16 Jan 2018 15:00:11 +0300 (using TLSv1.2 with cipher ECDHE-RSA-AES128-SHA256 (128/128 bits)) (Client certificate not present) From: Github ODP bot To: lng-odp@lists.linaro.org Date: Tue, 16 Jan 2018 15:00:08 +0300 Message-Id: <1516104008-9628-5-git-send-email-odpbot@yandex.ru> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1516104008-9628-1-git-send-email-odpbot@yandex.ru> References: <1516104008-9628-1-git-send-email-odpbot@yandex.ru> Github-pr-num: 393 Subject: [lng-odp] [PATCH API-NEXT v1 4/4] linux-gen: queue: lock-free implementation X-BeenThere: lng-odp@lists.linaro.org X-Mailman-Version: 2.1.16 Precedence: list List-Id: "The OpenDataPlane \(ODP\) List" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: lng-odp-bounces@lists.linaro.org Sender: "lng-odp" From: Petri Savolainen Simple implementation of non-blocking, lock-free plain queues. Enqueues are done freely to any free ring node with an atomically increasing counter value. Dequeue operation finds the node with lowest counter value. Implementation requires lockfree 128 bit atomics. Lock-free queues are not supported when those are not available. Signed-off-by: Petri Savolainen --- /** Email created from pull request 393 (psavol:next-lockfree-queue-impl-rebased) ** https://github.com/Linaro/odp/pull/393 ** Patch: https://github.com/Linaro/odp/pull/393.patch ** Base sha: f6dab2bfa90ef5d3146cb76f86bc8782666f0f3e ** Merge commit sha: 3da13358015ca674abf51f61f539fcbf6607cb2d **/ platform/linux-generic/Makefile.am | 2 + .../linux-generic/include/odp_queue_internal.h | 1 + platform/linux-generic/include/odp_queue_lf.h | 36 +++ platform/linux-generic/odp_queue.c | 71 ++++- platform/linux-generic/odp_queue_lf.c | 346 +++++++++++++++++++++ 5 files changed, 442 insertions(+), 14 deletions(-) create mode 100644 platform/linux-generic/include/odp_queue_lf.h create mode 100644 platform/linux-generic/odp_queue_lf.c diff --git a/platform/linux-generic/Makefile.am b/platform/linux-generic/Makefile.am index e25970b0c..b701d8071 100644 --- a/platform/linux-generic/Makefile.am +++ b/platform/linux-generic/Makefile.am @@ -160,6 +160,7 @@ noinst_HEADERS = \ include/odp_queue_scalable_internal.h \ include/odp_ring_internal.h \ include/odp_queue_if.h \ + include/odp_queue_lf.h \ include/odp_schedule_if.h \ include/odp_schedule_scalable.h \ include/odp_schedule_scalable_config.h \ @@ -220,6 +221,7 @@ __LIB__libodp_linux_la_SOURCES = \ odp_pool.c \ odp_queue.c \ odp_queue_if.c \ + odp_queue_lf.c \ odp_queue_scalable.c \ odp_rwlock.c \ odp_rwlock_recursive.c \ diff --git a/platform/linux-generic/include/odp_queue_internal.h b/platform/linux-generic/include/odp_queue_internal.h index dd846d592..26410ac7b 100644 --- a/platform/linux-generic/include/odp_queue_internal.h +++ b/platform/linux-generic/include/odp_queue_internal.h @@ -53,6 +53,7 @@ struct queue_entry_s { odp_queue_param_t param; odp_pktin_queue_t pktin; odp_pktout_queue_t pktout; + void *queue_lf; char name[ODP_QUEUE_NAME_LEN]; }; diff --git a/platform/linux-generic/include/odp_queue_lf.h b/platform/linux-generic/include/odp_queue_lf.h new file mode 100644 index 000000000..9bd61e428 --- /dev/null +++ b/platform/linux-generic/include/odp_queue_lf.h @@ -0,0 +1,36 @@ +/* Copyright (c) 2018, Linaro Limited + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +#ifndef ODP_QUEUE_LF_H_ +#define ODP_QUEUE_LF_H_ + +#ifdef __cplusplus +extern "C" { +#endif + +#include +#include + +/* Lock-free queue functions */ +typedef struct { + queue_enq_fn_t enq; + queue_enq_multi_fn_t enq_multi; + queue_deq_fn_t deq; + queue_deq_multi_fn_t deq_multi; + +} queue_lf_func_t; + +uint32_t queue_lf_init_global(uint32_t *queue_lf_size, + queue_lf_func_t *lf_func); +void queue_lf_term_global(void); +void *queue_lf_create(queue_entry_t *queue); +void queue_lf_destroy(void *queue_lf); + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/platform/linux-generic/odp_queue.c b/platform/linux-generic/odp_queue.c index 6a69eb849..7cb60562b 100644 --- a/platform/linux-generic/odp_queue.c +++ b/platform/linux-generic/odp_queue.c @@ -8,6 +8,7 @@ #include #include +#include #include #include #include @@ -39,11 +40,16 @@ static int queue_init(queue_entry_t *queue, const char *name, const odp_queue_param_t *param); -typedef struct queue_table_t { - queue_entry_t queue[ODP_CONFIG_QUEUES]; -} queue_table_t; +typedef struct queue_global_t { + queue_entry_t queue[ODP_CONFIG_QUEUES]; -static queue_table_t *queue_tbl; + uint32_t queue_lf_num; + uint32_t queue_lf_size; + queue_lf_func_t queue_lf_func; + +} queue_global_t; + +static queue_global_t *queue_glb; static queue_entry_t *get_qentry(uint32_t queue_id); @@ -64,26 +70,28 @@ static inline odp_queue_t queue_from_id(uint32_t queue_id) static queue_entry_t *get_qentry(uint32_t queue_id) { - return &queue_tbl->queue[queue_id]; + return &queue_glb->queue[queue_id]; } static int queue_init_global(void) { uint32_t i; odp_shm_t shm; + uint32_t lf_size = 0; + queue_lf_func_t *lf_func; ODP_DBG("Queue init ... "); shm = odp_shm_reserve("odp_queues", - sizeof(queue_table_t), + sizeof(queue_global_t), sizeof(queue_entry_t), 0); - queue_tbl = odp_shm_addr(shm); + queue_glb = odp_shm_addr(shm); - if (queue_tbl == NULL) + if (queue_glb == NULL) return -1; - memset(queue_tbl, 0, sizeof(queue_table_t)); + memset(queue_glb, 0, sizeof(queue_global_t)); for (i = 0; i < ODP_CONFIG_QUEUES; i++) { /* init locks */ @@ -93,6 +101,10 @@ static int queue_init_global(void) queue->s.handle = queue_from_id(i); } + lf_func = &queue_glb->queue_lf_func; + queue_glb->queue_lf_num = queue_lf_init_global(&lf_size, lf_func); + queue_glb->queue_lf_size = lf_size; + ODP_DBG("done\n"); ODP_DBG("Queue init global\n"); ODP_DBG(" struct queue_entry_s size %zu\n", @@ -122,7 +134,7 @@ static int queue_term_global(void) int i; for (i = 0; i < ODP_CONFIG_QUEUES; i++) { - queue = &queue_tbl->queue[i]; + queue = &queue_glb->queue[i]; LOCK(&queue->s.lock); if (queue->s.status != QUEUE_STATUS_FREE) { ODP_ERR("Not destroyed queue: %s\n", queue->s.name); @@ -131,6 +143,8 @@ static int queue_term_global(void) UNLOCK(&queue->s.lock); } + queue_lf_term_global(); + ret = odp_shm_free(odp_shm_lookup("odp_queues")); if (ret < 0) { ODP_ERR("shm free failed for odp_queues"); @@ -151,6 +165,8 @@ static int queue_capability(odp_queue_capability_t *capa) capa->sched_prios = odp_schedule_num_prio(); capa->plain.max_num = capa->max_queues; capa->sched.max_num = capa->max_queues; + capa->plain.lockfree.max_num = queue_glb->queue_lf_num; + capa->plain.lockfree.max_size = queue_glb->queue_lf_size; return 0; } @@ -188,6 +204,7 @@ static odp_queue_t queue_create(const char *name, { uint32_t i; queue_entry_t *queue; + void *queue_lf; odp_queue_t handle = ODP_QUEUE_INVALID; odp_queue_type_t type = ODP_QUEUE_TYPE_PLAIN; odp_queue_param_t default_param; @@ -198,7 +215,7 @@ static odp_queue_t queue_create(const char *name, } for (i = 0; i < ODP_CONFIG_QUEUES; i++) { - queue = &queue_tbl->queue[i]; + queue = &queue_glb->queue[i]; if (queue->s.status != QUEUE_STATUS_FREE) continue; @@ -207,7 +224,26 @@ static odp_queue_t queue_create(const char *name, if (queue->s.status == QUEUE_STATUS_FREE) { if (queue_init(queue, name, param)) { UNLOCK(&queue->s.lock); - return handle; + return ODP_QUEUE_INVALID; + } + + if (param->nonblocking == ODP_NONBLOCKING_LF) { + queue_lf_func_t *lf_func; + + lf_func = &queue_glb->queue_lf_func; + + queue_lf = queue_lf_create(queue); + + if (queue_lf == NULL) { + UNLOCK(&queue->s.lock); + return ODP_QUEUE_INVALID; + } + queue->s.queue_lf = queue_lf; + + queue->s.enqueue = lf_func->enq; + queue->s.enqueue_multi = lf_func->enq_multi; + queue->s.dequeue = lf_func->deq; + queue->s.dequeue_multi = lf_func->deq_multi; } type = queue->s.type; @@ -224,7 +260,10 @@ static odp_queue_t queue_create(const char *name, UNLOCK(&queue->s.lock); } - if (handle != ODP_QUEUE_INVALID && type == ODP_QUEUE_TYPE_SCHED) { + if (handle == ODP_QUEUE_INVALID) + return ODP_QUEUE_INVALID; + + if (type == ODP_QUEUE_TYPE_SCHED) { if (sched_fn->init_queue(queue->s.index, &queue->s.param.sched)) { queue->s.status = QUEUE_STATUS_FREE; @@ -289,6 +328,10 @@ static int queue_destroy(odp_queue_t handle) default: ODP_ABORT("Unexpected queue status\n"); } + + if (queue->s.param.nonblocking == ODP_NONBLOCKING_LF) + queue_lf_destroy(queue->s.queue_lf); + UNLOCK(&queue->s.lock); return 0; @@ -313,7 +356,7 @@ static odp_queue_t queue_lookup(const char *name) uint32_t i; for (i = 0; i < ODP_CONFIG_QUEUES; i++) { - queue_entry_t *queue = &queue_tbl->queue[i]; + queue_entry_t *queue = &queue_glb->queue[i]; if (queue->s.status == QUEUE_STATUS_FREE || queue->s.status == QUEUE_STATUS_DESTROYED) diff --git a/platform/linux-generic/odp_queue_lf.c b/platform/linux-generic/odp_queue_lf.c new file mode 100644 index 000000000..9f5090825 --- /dev/null +++ b/platform/linux-generic/odp_queue_lf.c @@ -0,0 +1,346 @@ +/* Copyright (c) 2018, Linaro Limited + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +#include +#include +#include +#include +#include +#include + +#include "config.h" +#include + +#define RING_LF_SIZE 32 +#define QUEUE_LF_NUM 128 +#define ENQ_RETRIES (RING_LF_SIZE / 4) +#define DEQ_RETRIES (RING_LF_SIZE / 8) + +#ifdef __SIZEOF_INT128__ + +typedef unsigned __int128 u128_t; + +static inline u128_t atomic_load_u128(u128_t *atomic) +{ + return __atomic_load_n(atomic, __ATOMIC_RELAXED); +} + +static inline void atomic_zero_u128(u128_t *atomic) +{ + __atomic_store_n(atomic, 0, __ATOMIC_RELAXED); +} + +static inline int atomic_cas_rel_u128(u128_t *atomic, u128_t old_val, + u128_t new_val) +{ + return __atomic_compare_exchange_n(atomic, &old_val, new_val, + 0 /* strong */, + __ATOMIC_RELEASE, + __ATOMIC_RELAXED); +} + +static inline int atomic_cas_acq_u128(u128_t *atomic, u128_t old_val, + u128_t new_val) +{ + return __atomic_compare_exchange_n(atomic, &old_val, new_val, + 0 /* strong */, + __ATOMIC_ACQUIRE, + __ATOMIC_RELAXED); +} + +#else + +/* These definitions enable build in non 128 bit compatible systems. + * Implementation is active only when 128 bit lockfree atomics are available. + * So, these are never actually used. */ +typedef struct { + uint64_t u64[2]; +} u128_t ODP_ALIGNED(16); + +static inline u128_t atomic_load_u128(u128_t *atomic) +{ + return *atomic; +} + +static inline void atomic_zero_u128(u128_t *atomic) +{ + atomic->u64[0] = 0; + atomic->u64[1] = 0; +} + +static inline int atomic_cas_rel_u128(u128_t *atomic, u128_t old_val, + u128_t new_val) +{ + (void)old_val; + *atomic = new_val; + return 1; +} + +static inline int atomic_cas_acq_u128(u128_t *atomic, u128_t old_val, + u128_t new_val) +{ + return atomic_cas_rel_u128(atomic, old_val, new_val); +} + +#endif + +/* Node in lock-free ring */ +typedef union { + u128_t u128; + + struct { + /* 0: empty, 1: data */ + uint64_t mark: 1; + + /* A cache aligned pointer fits into 63 bits, since the least + * significant bits are zero. */ + uint64_t ptr: 63; + + /* Data with lowest counter value is the head. */ + uint64_t count; + } s; + +} ring_lf_node_t; + +/* Lock-free ring */ +typedef struct { + ring_lf_node_t node[RING_LF_SIZE]; + int used; + odp_atomic_u64_t enq_counter; + +} queue_lf_t ODP_ALIGNED_CACHE; + +/* Lock-free queue globals */ +typedef struct { + queue_lf_t queue_lf[QUEUE_LF_NUM]; + odp_shm_t shm; + +} queue_lf_global_t ODP_ALIGNED_CACHE; + +static queue_lf_global_t *queue_lf_glb; + +static inline int next_idx(int idx) +{ + int next = idx + 1; + + if (next == RING_LF_SIZE) + next = 0; + + return next; +} + +static int queue_lf_enq(queue_t q_int, odp_buffer_hdr_t *buf_hdr) +{ + queue_entry_t *queue; + queue_lf_t *queue_lf; + int i, j, i_node; + int found; + ring_lf_node_t node_val; + ring_lf_node_t new_val; + ring_lf_node_t *node; + uint64_t counter; + + queue = qentry_from_int(q_int); + queue_lf = queue->s.queue_lf; + + i_node = 0; + + counter = odp_atomic_fetch_inc_u64(&queue_lf->enq_counter); + + for (j = 0; j < ENQ_RETRIES; j++) { + found = 0; + + /* Find empty node */ + for (i = 0; i < RING_LF_SIZE; i++) { + i_node = next_idx(i_node); + node = &queue_lf->node[i_node]; + node_val.u128 = atomic_load_u128(&node->u128); + + if (node_val.s.mark == 0) { + found = 1; + break; + } + } + + /* Queue is full */ + if (found == 0) + return -1; + + /* Try to insert data */ + new_val.s.mark = 1; + new_val.s.count = counter; + new_val.s.ptr = ((uintptr_t)buf_hdr) >> 1; + + if (atomic_cas_rel_u128(&node->u128, node_val.u128, + new_val.u128)) + return 0; + } + + return -1; +} + +static int queue_lf_enq_multi(queue_t q_int, odp_buffer_hdr_t **buf_hdr, + int num) +{ + (void)num; + + if (queue_lf_enq(q_int, buf_hdr[0]) == 0) + return 1; + + return 0; +} + +static odp_buffer_hdr_t *queue_lf_deq(queue_t q_int) +{ + queue_entry_t *queue; + queue_lf_t *queue_lf; + int i, j, i_node; + int found; + ring_lf_node_t node_val, old_val, new_val; + ring_lf_node_t *node, *old; + uint64_t lowest; + + queue = qentry_from_int(q_int); + queue_lf = queue->s.queue_lf; + i_node = 0; + + for (j = 0; j < DEQ_RETRIES; j++) { + found = 0; + lowest = -1; + + /* Find the head node. The one with data and + * the lowest counter. */ + for (i = 0; i < RING_LF_SIZE; i++) { + i_node = next_idx(i_node); + node = &queue_lf->node[i_node]; + node_val.u128 = atomic_load_u128(&node->u128); + + if (node_val.s.mark == 1 && node_val.s.count < lowest) { + old = node; + old_val.u128 = node_val.u128; + lowest = node_val.s.count; + found = 1; + } + } + + /* Queue is empty */ + if (found == 0) + return NULL; + + /* Try to remove data */ + new_val.u128 = old_val.u128; + new_val.s.mark = 0; + + if (atomic_cas_acq_u128(&old->u128, old_val.u128, + new_val.u128)) + return (void *)(((uintptr_t)old_val.s.ptr) << 1); + } + + return NULL; +} + +static int queue_lf_deq_multi(queue_t q_int, odp_buffer_hdr_t **buf_hdr, + int num) +{ + odp_buffer_hdr_t *buf; + + (void)num; + + buf = queue_lf_deq(q_int); + + if (buf == NULL) + return 0; + + buf_hdr[0] = buf; + return 1; +} + +uint32_t queue_lf_init_global(uint32_t *queue_lf_size, + queue_lf_func_t *lf_func) +{ + odp_shm_t shm; + bool lockfree = 0; + + /* 16 byte lockfree CAS operation is needed. */ +#ifdef __SIZEOF_INT128__ + lockfree = __atomic_is_lock_free(16, NULL); +#endif + + ODP_DBG("\nLock-free queue init\n"); + ODP_DBG(" u128 lock-free: %i\n\n", lockfree); + + if (!lockfree) + return 0; + + shm = odp_shm_reserve("odp_queues_lf", sizeof(queue_lf_global_t), + ODP_CACHE_LINE_SIZE, 0); + + queue_lf_glb = odp_shm_addr(shm); + memset(queue_lf_glb, 0, sizeof(queue_lf_global_t)); + + queue_lf_glb->shm = shm; + + memset(lf_func, 0, sizeof(queue_lf_func_t)); + lf_func->enq = queue_lf_enq; + lf_func->enq_multi = queue_lf_enq_multi; + lf_func->deq = queue_lf_deq; + lf_func->deq_multi = queue_lf_deq_multi; + + *queue_lf_size = RING_LF_SIZE; + + return QUEUE_LF_NUM; +} + +void queue_lf_term_global(void) +{ + odp_shm_t shm; + + if (queue_lf_glb == NULL) + return; + + shm = queue_lf_glb->shm; + + if (odp_shm_free(shm) < 0) + ODP_ERR("shm free failed"); +} + +static void init_queue(queue_lf_t *queue_lf) +{ + int i; + + odp_atomic_init_u64(&queue_lf->enq_counter, 0); + + for (i = 0; i < RING_LF_SIZE; i++) + atomic_zero_u128(&queue_lf->node[i].u128); +} + +void *queue_lf_create(queue_entry_t *queue) +{ + int i; + queue_lf_t *queue_lf = NULL; + + if (queue->s.type != ODP_QUEUE_TYPE_PLAIN) + return NULL; + + for (i = 0; i < QUEUE_LF_NUM; i++) { + if (queue_lf_glb->queue_lf[i].used == 0) { + queue_lf = &queue_lf_glb->queue_lf[i]; + memset(queue_lf, 0, sizeof(queue_lf_t)); + init_queue(queue_lf); + queue_lf->used = 1; + break; + } + } + + return queue_lf; +} + +void queue_lf_destroy(void *queue_lf_ptr) +{ + queue_lf_t *queue_lf = queue_lf_ptr; + + queue_lf->used = 0; +}