From patchwork Mon Jun 11 20:55:34 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Burakov, Anatoly" X-Patchwork-Id: 40987 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 7D4F01DE4C; Mon, 11 Jun 2018 22:55:50 +0200 (CEST) Received: from mga18.intel.com (mga18.intel.com [134.134.136.126]) by dpdk.org (Postfix) with ESMTP id 409881DB16 for ; Mon, 11 Jun 2018 22:55:45 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga007.jf.intel.com ([10.7.209.58]) by orsmga106.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 11 Jun 2018 13:55:43 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.51,211,1526367600"; d="scan'208";a="48181353" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by orsmga007.jf.intel.com with ESMTP; 11 Jun 2018 13:55:43 -0700 Received: from sivswdev01.ir.intel.com (sivswdev01.ir.intel.com [10.237.217.45]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id w5BKtg1c026368 for ; Mon, 11 Jun 2018 21:55:42 +0100 Received: from sivswdev01.ir.intel.com (localhost [127.0.0.1]) by sivswdev01.ir.intel.com with ESMTP id w5BKtgKC021563 for ; Mon, 11 Jun 2018 21:55:42 +0100 Received: (from aburakov@localhost) by sivswdev01.ir.intel.com with LOCAL id w5BKtgcf021559 for dev@dpdk.org; Mon, 11 Jun 2018 21:55:42 +0100 From: Anatoly Burakov To: dev@dpdk.org Date: Mon, 11 Jun 2018 21:55:34 +0100 Message-Id: <69a90d1387ef6345923b278163c563b29a5144d8.1528749451.git.anatoly.burakov@intel.com> X-Mailer: git-send-email 1.7.0.7 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH 1/9] fbarray: fix errno values returned from functions X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Errno values are supposed to be positive, yet they were negative. This changes API, so not backporting. Fixes: c44d09811b40 ("eal: add shared indexed file-backed array") Signed-off-by: Anatoly Burakov --- lib/librte_eal/common/eal_common_fbarray.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/lib/librte_eal/common/eal_common_fbarray.c b/lib/librte_eal/common/eal_common_fbarray.c index 019f84c18..9ae942bfe 100644 --- a/lib/librte_eal/common/eal_common_fbarray.c +++ b/lib/librte_eal/common/eal_common_fbarray.c @@ -231,7 +231,7 @@ find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n, return MASK_GET_IDX(msk_idx, run_start); } /* we didn't find anything */ - rte_errno = used ? -ENOENT : -ENOSPC; + rte_errno = used ? ENOENT : ENOSPC; return -1; } @@ -287,7 +287,7 @@ find_next(const struct rte_fbarray *arr, unsigned int start, bool used) return MASK_GET_IDX(idx, found); } /* we didn't find anything */ - rte_errno = used ? -ENOENT : -ENOSPC; + rte_errno = used ? ENOENT : ENOSPC; return -1; } From patchwork Mon Jun 11 20:55:35 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Burakov, Anatoly" X-Patchwork-Id: 40988 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 819241DE73; Mon, 11 Jun 2018 22:55:53 +0200 (CEST) Received: from mga03.intel.com (mga03.intel.com [134.134.136.65]) by dpdk.org (Postfix) with ESMTP id 6CB891DB37 for ; Mon, 11 Jun 2018 22:55:46 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga008.jf.intel.com ([10.7.209.65]) by orsmga103.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 11 Jun 2018 13:55:44 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.51,211,1526367600"; d="scan'208";a="48522981" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by orsmga008.jf.intel.com with ESMTP; 11 Jun 2018 13:55:43 -0700 Received: from sivswdev01.ir.intel.com (sivswdev01.ir.intel.com [10.237.217.45]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id w5BKtguh026371 for ; Mon, 11 Jun 2018 21:55:42 +0100 Received: from sivswdev01.ir.intel.com (localhost [127.0.0.1]) by sivswdev01.ir.intel.com with ESMTP id w5BKtgCf021574 for ; Mon, 11 Jun 2018 21:55:42 +0100 Received: (from aburakov@localhost) by sivswdev01.ir.intel.com with LOCAL id w5BKtgS4021570 for dev@dpdk.org; Mon, 11 Jun 2018 21:55:42 +0100 From: Anatoly Burakov To: dev@dpdk.org Date: Mon, 11 Jun 2018 21:55:35 +0100 Message-Id: <4c43dd7982c8211249d45bf0e1ffbdd1ca788b1c.1528749451.git.anatoly.burakov@intel.com> X-Mailer: git-send-email 1.7.0.7 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH 2/9] fbarray: reduce duplication in find_contig code X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Mostly a code move, to have all code related to find_contig in one place. This slightly changes the API in that previously, calling find_contig_free() on a full fbarray would've been an error, but equivalent call to find_contig_used() on an empty array does not return an error, leading to an inconsistency in the API. The decision was made to not treat this condition as an error, because it is equivalent to calling find_contig() on an index that just happens to be used/free, which is not an error and will return 0. Signed-off-by: Anatoly Burakov --- lib/librte_eal/common/eal_common_fbarray.c | 52 ++++++++++++---------- 1 file changed, 28 insertions(+), 24 deletions(-) diff --git a/lib/librte_eal/common/eal_common_fbarray.c b/lib/librte_eal/common/eal_common_fbarray.c index 9ae942bfe..e37fe1e4d 100644 --- a/lib/librte_eal/common/eal_common_fbarray.c +++ b/lib/librte_eal/common/eal_common_fbarray.c @@ -773,8 +773,8 @@ rte_fbarray_find_next_n_used(struct rte_fbarray *arr, unsigned int start, return ret; } -int __rte_experimental -rte_fbarray_find_contig_free(struct rte_fbarray *arr, unsigned int start) +static int +fbarray_find_contig(struct rte_fbarray *arr, unsigned int start, bool used) { int ret = -1; @@ -786,14 +786,25 @@ rte_fbarray_find_contig_free(struct rte_fbarray *arr, unsigned int start) /* prevent array from changing under us */ rte_rwlock_read_lock(&arr->rwlock); - if (arr->len == arr->count) { - rte_errno = ENOSPC; - goto out; - } - - if (arr->count == 0) { - ret = arr->len - start; - goto out; + /* cheap checks to prevent doing useless work */ + if (used) { + if (arr->count == 0) { + ret = 0; + goto out; + } + if (arr->len == arr->count) { + ret = arr->len - start; + goto out; + } + } else { + if (arr->len == arr->count) { + ret = 0; + goto out; + } + if (arr->count == 0) { + ret = arr->len - start; + goto out; + } } ret = find_contig(arr, start, false); @@ -803,22 +814,15 @@ rte_fbarray_find_contig_free(struct rte_fbarray *arr, unsigned int start) } int __rte_experimental -rte_fbarray_find_contig_used(struct rte_fbarray *arr, unsigned int start) +rte_fbarray_find_contig_free(struct rte_fbarray *arr, unsigned int start) { - int ret = -1; - - if (arr == NULL || start >= arr->len) { - rte_errno = EINVAL; - return -1; - } - - /* prevent array from changing under us */ - rte_rwlock_read_lock(&arr->rwlock); - - ret = find_contig(arr, start, true); + return fbarray_find_contig(arr, start, false); +} - rte_rwlock_read_unlock(&arr->rwlock); - return ret; +int __rte_experimental +rte_fbarray_find_contig_used(struct rte_fbarray *arr, unsigned int start) +{ + return fbarray_find_contig(arr, start, true); } int __rte_experimental From patchwork Mon Jun 11 20:55:36 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Burakov, Anatoly" X-Patchwork-Id: 40992 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id DC7F91DEA4; Mon, 11 Jun 2018 22:56:01 +0200 (CEST) Received: from mga03.intel.com (mga03.intel.com [134.134.136.65]) by dpdk.org (Postfix) with ESMTP id 167331D940 for ; Mon, 11 Jun 2018 22:55:46 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga008.jf.intel.com ([10.7.209.65]) by orsmga103.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 11 Jun 2018 13:55:44 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.51,211,1526367600"; d="scan'208";a="48522982" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by orsmga008.jf.intel.com with ESMTP; 11 Jun 2018 13:55:43 -0700 Received: from sivswdev01.ir.intel.com (sivswdev01.ir.intel.com [10.237.217.45]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id w5BKthcq026374 for ; Mon, 11 Jun 2018 21:55:43 +0100 Received: from sivswdev01.ir.intel.com (localhost [127.0.0.1]) by sivswdev01.ir.intel.com with ESMTP id w5BKtg3b021583 for ; Mon, 11 Jun 2018 21:55:42 +0100 Received: (from aburakov@localhost) by sivswdev01.ir.intel.com with LOCAL id w5BKtgkD021577 for dev@dpdk.org; Mon, 11 Jun 2018 21:55:42 +0100 From: Anatoly Burakov To: dev@dpdk.org Date: Mon, 11 Jun 2018 21:55:36 +0100 Message-Id: <26cd3a33611c40bcb09cd09d8a1d36d686635271.1528749451.git.anatoly.burakov@intel.com> X-Mailer: git-send-email 1.7.0.7 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH 3/9] fbarray: reduce duplication in find_next_n code X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Mostly code move, aside from more quick checks done to avoid doing computations in obviously hopeless cases. Signed-off-by: Anatoly Burakov --- lib/librte_eal/common/eal_common_fbarray.c | 63 ++++++++++++---------- 1 file changed, 36 insertions(+), 27 deletions(-) diff --git a/lib/librte_eal/common/eal_common_fbarray.c b/lib/librte_eal/common/eal_common_fbarray.c index e37fe1e4d..c5ee017dd 100644 --- a/lib/librte_eal/common/eal_common_fbarray.c +++ b/lib/librte_eal/common/eal_common_fbarray.c @@ -723,54 +723,63 @@ rte_fbarray_find_next_used(struct rte_fbarray *arr, unsigned int start) return ret; } -int __rte_experimental -rte_fbarray_find_next_n_free(struct rte_fbarray *arr, unsigned int start, - unsigned int n) +static int +fbarray_find_n(struct rte_fbarray *arr, unsigned int start, unsigned int n, + bool used) { int ret = -1; - if (arr == NULL || start >= arr->len || n > arr->len) { + if (arr == NULL || start >= arr->len || n > arr->len || n == 0) { rte_errno = EINVAL; return -1; } + if (arr->len - start < n) { + rte_errno = used ? ENOENT : ENOSPC; + return -1; + } /* prevent array from changing under us */ rte_rwlock_read_lock(&arr->rwlock); - if (arr->len == arr->count || arr->len - arr->count < n) { - rte_errno = ENOSPC; - goto out; + /* cheap checks to prevent doing useless work */ + if (!used) { + if (arr->len == arr->count || arr->len - arr->count < n) { + rte_errno = ENOSPC; + goto out; + } + if (arr->count == 0) { + ret = start; + goto out; + } + } else { + if (arr->count < n) { + rte_errno = ENOENT; + goto out; + } + if (arr->count == arr->len) { + ret = start; + goto out; + } } - ret = find_next_n(arr, start, n, false); + ret = find_next_n(arr, start, n, used); out: rte_rwlock_read_unlock(&arr->rwlock); return ret; } int __rte_experimental -rte_fbarray_find_next_n_used(struct rte_fbarray *arr, unsigned int start, +rte_fbarray_find_next_n_free(struct rte_fbarray *arr, unsigned int start, unsigned int n) { - int ret = -1; - - if (arr == NULL || start >= arr->len || n > arr->len) { - rte_errno = EINVAL; - return -1; - } - - /* prevent array from changing under us */ - rte_rwlock_read_lock(&arr->rwlock); - - if (arr->count < n) { - rte_errno = ENOENT; - goto out; - } + return fbarray_find_n(arr, start, n, false); +} - ret = find_next_n(arr, start, n, true); -out: - rte_rwlock_read_unlock(&arr->rwlock); - return ret; +int __rte_experimental +rte_fbarray_find_next_n_used(struct rte_fbarray *arr, unsigned int start, + unsigned int n) +{ + return fbarray_find_n(arr, start, n, true); } static int From patchwork Mon Jun 11 20:55:37 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Burakov, Anatoly" X-Patchwork-Id: 40993 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 7450B1DEAA; Mon, 11 Jun 2018 22:56:03 +0200 (CEST) Received: from mga12.intel.com (mga12.intel.com [192.55.52.136]) by dpdk.org (Postfix) with ESMTP id 6A8B11DE4C for ; Mon, 11 Jun 2018 22:55:48 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga005.jf.intel.com ([10.7.209.41]) by fmsmga106.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 11 Jun 2018 13:55:48 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.51,211,1526367600"; d="scan'208";a="231737137" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by orsmga005.jf.intel.com with ESMTP; 11 Jun 2018 13:55:45 -0700 Received: from sivswdev01.ir.intel.com (sivswdev01.ir.intel.com [10.237.217.45]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id w5BKthg1026377 for ; Mon, 11 Jun 2018 21:55:43 +0100 Received: from sivswdev01.ir.intel.com (localhost [127.0.0.1]) by sivswdev01.ir.intel.com with ESMTP id w5BKthq5021592 for ; Mon, 11 Jun 2018 21:55:43 +0100 Received: (from aburakov@localhost) by sivswdev01.ir.intel.com with LOCAL id w5BKthHO021588 for dev@dpdk.org; Mon, 11 Jun 2018 21:55:43 +0100 From: Anatoly Burakov To: dev@dpdk.org Date: Mon, 11 Jun 2018 21:55:37 +0100 Message-Id: X-Mailer: git-send-email 1.7.0.7 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH 4/9] fbarray: reduce duplication in find_next code X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Just code move to put all checks and calls in one place. Signed-off-by: Anatoly Burakov --- lib/librte_eal/common/eal_common_fbarray.c | 54 ++++++++++++---------- 1 file changed, 29 insertions(+), 25 deletions(-) diff --git a/lib/librte_eal/common/eal_common_fbarray.c b/lib/librte_eal/common/eal_common_fbarray.c index c5ee017dd..22370398f 100644 --- a/lib/librte_eal/common/eal_common_fbarray.c +++ b/lib/librte_eal/common/eal_common_fbarray.c @@ -675,8 +675,8 @@ rte_fbarray_is_used(struct rte_fbarray *arr, unsigned int idx) return ret; } -int __rte_experimental -rte_fbarray_find_next_free(struct rte_fbarray *arr, unsigned int start) +static int +fbarray_find(struct rte_fbarray *arr, unsigned int start, bool used) { int ret = -1; @@ -688,39 +688,43 @@ rte_fbarray_find_next_free(struct rte_fbarray *arr, unsigned int start) /* prevent array from changing under us */ rte_rwlock_read_lock(&arr->rwlock); - if (arr->len == arr->count) { - rte_errno = ENOSPC; - goto out; + /* cheap checks to prevent doing useless work */ + if (!used) { + if (arr->len == arr->count) { + rte_errno = ENOSPC; + goto out; + } + if (arr->count == 0) { + ret = start; + goto out; + } + } else { + if (arr->count == 0) { + rte_errno = ENOENT; + goto out; + } + if (arr->len == arr->count) { + ret = start; + goto out; + } } - ret = find_next(arr, start, false); + ret = find_next(arr, start, used); out: rte_rwlock_read_unlock(&arr->rwlock); return ret; } int __rte_experimental -rte_fbarray_find_next_used(struct rte_fbarray *arr, unsigned int start) +rte_fbarray_find_next_free(struct rte_fbarray *arr, unsigned int start) { - int ret = -1; - - if (arr == NULL || start >= arr->len) { - rte_errno = EINVAL; - return -1; - } - - /* prevent array from changing under us */ - rte_rwlock_read_lock(&arr->rwlock); - - if (arr->count == 0) { - rte_errno = ENOENT; - goto out; - } + return fbarray_find(arr, start, false); +} - ret = find_next(arr, start, true); -out: - rte_rwlock_read_unlock(&arr->rwlock); - return ret; +int __rte_experimental +rte_fbarray_find_next_used(struct rte_fbarray *arr, unsigned int start) +{ + return fbarray_find(arr, start, true); } static int From patchwork Mon Jun 11 20:55:38 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Burakov, Anatoly" X-Patchwork-Id: 40989 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 125351DE7F; Mon, 11 Jun 2018 22:55:56 +0200 (CEST) Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by dpdk.org (Postfix) with ESMTP id 5E5B81D940 for ; Mon, 11 Jun 2018 22:55:46 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga006.fm.intel.com ([10.253.24.20]) by fmsmga103.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 11 Jun 2018 13:55:44 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.51,211,1526367600"; d="scan'208";a="236556763" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by fmsmga006.fm.intel.com with ESMTP; 11 Jun 2018 13:55:43 -0700 Received: from sivswdev01.ir.intel.com (sivswdev01.ir.intel.com [10.237.217.45]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id w5BKthP3026380 for ; Mon, 11 Jun 2018 21:55:43 +0100 Received: from sivswdev01.ir.intel.com (localhost [127.0.0.1]) by sivswdev01.ir.intel.com with ESMTP id w5BKthaM021599 for ; Mon, 11 Jun 2018 21:55:43 +0100 Received: (from aburakov@localhost) by sivswdev01.ir.intel.com with LOCAL id w5BKtheo021595 for dev@dpdk.org; Mon, 11 Jun 2018 21:55:43 +0100 From: Anatoly Burakov To: dev@dpdk.org Date: Mon, 11 Jun 2018 21:55:38 +0100 Message-Id: <35f3ada5026b8619499ddd3a8b41b2d1066c3e31.1528749451.git.anatoly.burakov@intel.com> X-Mailer: git-send-email 1.7.0.7 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH 5/9] fbarray: add reverse find_free/used X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Add function to look up used/free indexes starting from specified index, but going backwards instead of forward. Semantics are kept similar to the existing function, except for the fact that, given the same input, the results returned will be in reverse order. Signed-off-by: Anatoly Burakov --- lib/librte_eal/common/eal_common_fbarray.c | 78 +++++++++++++++++++-- lib/librte_eal/common/include/rte_fbarray.h | 34 +++++++++ lib/librte_eal/rte_eal_version.map | 2 + 3 files changed, 109 insertions(+), 5 deletions(-) diff --git a/lib/librte_eal/common/eal_common_fbarray.c b/lib/librte_eal/common/eal_common_fbarray.c index 22370398f..d5d72e37b 100644 --- a/lib/librte_eal/common/eal_common_fbarray.c +++ b/lib/librte_eal/common/eal_common_fbarray.c @@ -352,6 +352,60 @@ find_contig(const struct rte_fbarray *arr, unsigned int start, bool used) return result; } +static int +find_prev(const struct rte_fbarray *arr, unsigned int start, bool used) +{ + const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz, + arr->len); + unsigned int idx, first, first_mod; + uint64_t ignore_msk; + + /* + * mask only has granularity of MASK_ALIGN, but start may not be aligned + * on that boundary, so construct a special mask to exclude anything we + * don't want to see to avoid confusing clz. + */ + first = MASK_LEN_TO_IDX(start); + first_mod = MASK_LEN_TO_MOD(start); + /* we're going backwards, so mask must start from the top */ + ignore_msk = first_mod == MASK_ALIGN - 1 ? + -1ULL : /* prevent overflow */ + ~(-1ULL << (first_mod + 1)); + + /* go backwards, include zero */ + idx = first; + do { + uint64_t cur = msk->data[idx]; + int found; + + /* if we're looking for free entries, invert mask */ + if (!used) + cur = ~cur; + + /* ignore everything before start on first iteration */ + if (idx == first) + cur &= ignore_msk; + + /* check if we have any entries */ + if (cur == 0) + continue; + + /* + * find last set bit - that will correspond to whatever it is + * that we're looking for. we're counting trailing zeroes, thus + * the value we get is counted from end of mask, so calculate + * position from start of mask. + */ + found = MASK_ALIGN - __builtin_clzll(cur) - 1; + + return MASK_GET_IDX(idx, found); + } while (idx-- != 0); /* decrement after check to include zero*/ + + /* we didn't find anything */ + rte_errno = used ? ENOENT : ENOSPC; + return -1; +} + static int set_used(struct rte_fbarray *arr, unsigned int idx, bool used) { @@ -676,7 +730,7 @@ rte_fbarray_is_used(struct rte_fbarray *arr, unsigned int idx) } static int -fbarray_find(struct rte_fbarray *arr, unsigned int start, bool used) +fbarray_find(struct rte_fbarray *arr, unsigned int start, bool next, bool used) { int ret = -1; @@ -708,8 +762,10 @@ fbarray_find(struct rte_fbarray *arr, unsigned int start, bool used) goto out; } } - - ret = find_next(arr, start, used); + if (next) + ret = find_next(arr, start, used); + else + ret = find_prev(arr, start, used); out: rte_rwlock_read_unlock(&arr->rwlock); return ret; @@ -718,13 +774,25 @@ fbarray_find(struct rte_fbarray *arr, unsigned int start, bool used) int __rte_experimental rte_fbarray_find_next_free(struct rte_fbarray *arr, unsigned int start) { - return fbarray_find(arr, start, false); + return fbarray_find(arr, start, true, false); } int __rte_experimental rte_fbarray_find_next_used(struct rte_fbarray *arr, unsigned int start) { - return fbarray_find(arr, start, true); + return fbarray_find(arr, start, true, true); +} + +int __rte_experimental +rte_fbarray_find_prev_free(struct rte_fbarray *arr, unsigned int start) +{ + return fbarray_find(arr, start, false, false); +} + +int __rte_experimental +rte_fbarray_find_prev_used(struct rte_fbarray *arr, unsigned int start) +{ + return fbarray_find(arr, start, false, true); } static int diff --git a/lib/librte_eal/common/include/rte_fbarray.h b/lib/librte_eal/common/include/rte_fbarray.h index 3e61fffee..54abe938a 100644 --- a/lib/librte_eal/common/include/rte_fbarray.h +++ b/lib/librte_eal/common/include/rte_fbarray.h @@ -336,6 +336,40 @@ rte_fbarray_find_contig_free(struct rte_fbarray *arr, int __rte_experimental rte_fbarray_find_contig_used(struct rte_fbarray *arr, unsigned int start); +/** + * Find index of previous free element, starting at specified index. + * + * @param arr + * Valid pointer to allocated and correctly set up ``rte_fbarray`` structure. + * + * @param start + * Element index to start search from. + * + * @return + * - non-negative integer on success. + * - -1 on failure, with ``rte_errno`` indicating reason for failure. + */ +int __rte_experimental +rte_fbarray_find_prev_free(struct rte_fbarray *arr, unsigned int start); + + +/** + * Find index of previous used element, starting at specified index. + * + * @param arr + * Valid pointer to allocated and correctly set up ``rte_fbarray`` structure. + * + * @param start + * Element index to start search from. + * + * @return + * - non-negative integer on success. + * - -1 on failure, with ``rte_errno`` indicating reason for failure. + */ +int __rte_experimental +rte_fbarray_find_prev_used(struct rte_fbarray *arr, unsigned int start); + + /** * Dump ``rte_fbarray`` metadata. diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map index f7dd0e7bc..79b87f504 100644 --- a/lib/librte_eal/rte_eal_version.map +++ b/lib/librte_eal/rte_eal_version.map @@ -269,6 +269,8 @@ EXPERIMENTAL { rte_fbarray_find_next_used; rte_fbarray_find_next_n_free; rte_fbarray_find_next_n_used; + rte_fbarray_find_prev_free; + rte_fbarray_find_prev_used; rte_fbarray_find_contig_free; rte_fbarray_find_contig_used; rte_fbarray_get; From patchwork Mon Jun 11 20:55:39 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Burakov, Anatoly" X-Patchwork-Id: 40990 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 2FDC21DE8D; Mon, 11 Jun 2018 22:55:58 +0200 (CEST) Received: from mga11.intel.com (mga11.intel.com [192.55.52.93]) by dpdk.org (Postfix) with ESMTP id 826C81DB16 for ; Mon, 11 Jun 2018 22:55:46 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga008.fm.intel.com ([10.253.24.58]) by fmsmga102.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 11 Jun 2018 13:55:44 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.51,211,1526367600"; d="scan'208";a="46964667" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by fmsmga008.fm.intel.com with ESMTP; 11 Jun 2018 13:55:44 -0700 Received: from sivswdev01.ir.intel.com (sivswdev01.ir.intel.com [10.237.217.45]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id w5BKth4V026383 for ; Mon, 11 Jun 2018 21:55:43 +0100 Received: from sivswdev01.ir.intel.com (localhost [127.0.0.1]) by sivswdev01.ir.intel.com with ESMTP id w5BKthAg021610 for ; Mon, 11 Jun 2018 21:55:43 +0100 Received: (from aburakov@localhost) by sivswdev01.ir.intel.com with LOCAL id w5BKthMn021606 for dev@dpdk.org; Mon, 11 Jun 2018 21:55:43 +0100 From: Anatoly Burakov To: dev@dpdk.org Date: Mon, 11 Jun 2018 21:55:39 +0100 Message-Id: <1ede509dfe977ac28772bd11227846e8ef6a4edc.1528749451.git.anatoly.burakov@intel.com> X-Mailer: git-send-email 1.7.0.7 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH 6/9] fbarray: add reverse find n used/free X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Add a function to look for N used/free slots, but going backwards instead of forwards. All semantics are kept similar to the existing function, with the difference being that given the same input, the same results will be returned in reverse order. Signed-off-by: Anatoly Burakov --- lib/librte_eal/common/eal_common_fbarray.c | 198 +++++++++++++++++++- lib/librte_eal/common/include/rte_fbarray.h | 44 +++++ lib/librte_eal/rte_eal_version.map | 2 + 3 files changed, 237 insertions(+), 7 deletions(-) diff --git a/lib/librte_eal/common/eal_common_fbarray.c b/lib/librte_eal/common/eal_common_fbarray.c index d5d72e37b..a2e01148b 100644 --- a/lib/librte_eal/common/eal_common_fbarray.c +++ b/lib/librte_eal/common/eal_common_fbarray.c @@ -352,6 +352,169 @@ find_contig(const struct rte_fbarray *arr, unsigned int start, bool used) return result; } +static int +find_prev_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n, + bool used) +{ + const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz, + arr->len); + unsigned int msk_idx, lookbehind_idx, first, first_mod; + uint64_t ignore_msk; + + /* + * mask only has granularity of MASK_ALIGN, but start may not be aligned + * on that boundary, so construct a special mask to exclude anything we + * don't want to see to avoid confusing ctz. + */ + first = MASK_LEN_TO_IDX(start); + first_mod = MASK_LEN_TO_MOD(start); + /* we're going backwards, so mask must start from the top */ + ignore_msk = first_mod == MASK_ALIGN - 1 ? + -1ULL : /* prevent overflow */ + ~(-1ULL << (first_mod + 1)); + + /* go backwards, include zero */ + msk_idx = first; + do { + uint64_t cur_msk, lookbehind_msk; + unsigned int run_start, run_end, ctz, left; + bool found = false; + /* + * The process of getting n consecutive bits from the top for + * arbitrary n is a bit involved, but here it is in a nutshell: + * + * 1. let n be the number of consecutive bits we're looking for + * 2. check if n can fit in one mask, and if so, do n-1 + * lshift-ands to see if there is an appropriate run inside + * our current mask + * 2a. if we found a run, bail out early + * 2b. if we didn't find a run, proceed + * 3. invert the mask and count trailing zeroes (that is, count + * how many consecutive set bits we had starting from the + * start of current mask) as k + * 3a. if k is 0, continue to next mask + * 3b. if k is not 0, we have a potential run + * 4. to satisfy our requirements, next mask must have n-k + * consecutive set bits at the end, so we will do (n-k-1) + * lshift-ands and check if last bit is set. + * + * Step 4 will need to be repeated if (n-k) > MASK_ALIGN until + * we either run out of masks, lose the run, or find what we + * were looking for. + */ + cur_msk = msk->data[msk_idx]; + left = n; + + /* if we're looking for free spaces, invert the mask */ + if (!used) + cur_msk = ~cur_msk; + + /* if we have an ignore mask, ignore once */ + if (ignore_msk) { + cur_msk &= ignore_msk; + ignore_msk = 0; + } + + /* if n can fit in within a single mask, do a search */ + if (n <= MASK_ALIGN) { + uint64_t tmp_msk = cur_msk; + unsigned int s_idx; + for (s_idx = 0; s_idx < n - 1; s_idx++) + tmp_msk &= tmp_msk << 1ULL; + /* we found what we were looking for */ + if (tmp_msk != 0) { + /* clz will give us offset from end of mask, and + * we only get the end of our run, not start, + * so adjust result to point to where start + * would have been. + */ + run_start = MASK_ALIGN - + __builtin_clzll(tmp_msk) - n; + return MASK_GET_IDX(msk_idx, run_start); + } + } + + /* + * we didn't find our run within the mask, or n > MASK_ALIGN, + * so we're going for plan B. + */ + + /* count trailing zeroes on inverted mask */ + if (~cur_msk == 0) + ctz = sizeof(cur_msk) * 8; + else + ctz = __builtin_ctzll(~cur_msk); + + /* if there aren't any runs at the start either, just + * continue + */ + if (ctz == 0) + continue; + + /* we have a partial run at the start, so try looking behind */ + run_end = MASK_GET_IDX(msk_idx, ctz); + left -= ctz; + + /* go backwards, include zero */ + lookbehind_idx = msk_idx - 1; + + /* we can't lookbehind as we've run out of masks, so stop */ + if (msk_idx == 0) + break; + + do { + const uint64_t last_bit = 1ULL << (MASK_ALIGN - 1); + unsigned int s_idx, need; + + lookbehind_msk = msk->data[lookbehind_idx]; + + /* if we're looking for free space, invert the mask */ + if (!used) + lookbehind_msk = ~lookbehind_msk; + + /* figure out how many consecutive bits we need here */ + need = RTE_MIN(left, MASK_ALIGN); + + for (s_idx = 0; s_idx < need - 1; s_idx++) + lookbehind_msk &= lookbehind_msk << 1ULL; + + /* if last bit is not set, we've lost the run */ + if ((lookbehind_msk & last_bit) == 0) { + /* + * we've scanned this far, so we know there are + * no runs in the space we've lookbehind-scanned + * as well, so skip that on next iteration. + */ + ignore_msk = -1ULL << need; + msk_idx = lookbehind_idx; + break; + } + + left -= need; + + /* check if we've found what we were looking for */ + if (left == 0) { + found = true; + break; + } + } while ((lookbehind_idx--) != 0); /* decrement after check to + * include zero + */ + + /* we didn't find anything, so continue */ + if (!found) + continue; + + /* we've found what we were looking for, but we only know where + * the run ended, so calculate start position. + */ + return run_end - n; + } while (msk_idx-- != 0); /* decrement after check to include zero */ + /* we didn't find anything */ + rte_errno = used ? ENOENT : ENOSPC; + return -1; +} + static int find_prev(const struct rte_fbarray *arr, unsigned int start, bool used) { @@ -797,7 +960,7 @@ rte_fbarray_find_prev_used(struct rte_fbarray *arr, unsigned int start) static int fbarray_find_n(struct rte_fbarray *arr, unsigned int start, unsigned int n, - bool used) + bool next, bool used) { int ret = -1; @@ -805,7 +968,11 @@ fbarray_find_n(struct rte_fbarray *arr, unsigned int start, unsigned int n, rte_errno = EINVAL; return -1; } - if (arr->len - start < n) { + if (next && (arr->len - start) < n) { + rte_errno = used ? ENOENT : ENOSPC; + return -1; + } + if (!next && start < (n - 1)) { rte_errno = used ? ENOENT : ENOSPC; return -1; } @@ -820,7 +987,7 @@ fbarray_find_n(struct rte_fbarray *arr, unsigned int start, unsigned int n, goto out; } if (arr->count == 0) { - ret = start; + ret = next ? start : start - n + 1; goto out; } } else { @@ -829,12 +996,15 @@ fbarray_find_n(struct rte_fbarray *arr, unsigned int start, unsigned int n, goto out; } if (arr->count == arr->len) { - ret = start; + ret = next ? start : start - n + 1; goto out; } } - ret = find_next_n(arr, start, n, used); + if (next) + ret = find_next_n(arr, start, n, used); + else + ret = find_prev_n(arr, start, n, used); out: rte_rwlock_read_unlock(&arr->rwlock); return ret; @@ -844,14 +1014,28 @@ int __rte_experimental rte_fbarray_find_next_n_free(struct rte_fbarray *arr, unsigned int start, unsigned int n) { - return fbarray_find_n(arr, start, n, false); + return fbarray_find_n(arr, start, n, true, false); } int __rte_experimental rte_fbarray_find_next_n_used(struct rte_fbarray *arr, unsigned int start, unsigned int n) { - return fbarray_find_n(arr, start, n, true); + return fbarray_find_n(arr, start, n, true, true); +} + +int __rte_experimental +rte_fbarray_find_prev_n_free(struct rte_fbarray *arr, unsigned int start, + unsigned int n) +{ + return fbarray_find_n(arr, start, n, false, false); +} + +int __rte_experimental +rte_fbarray_find_prev_n_used(struct rte_fbarray *arr, unsigned int start, + unsigned int n) +{ + return fbarray_find_n(arr, start, n, false, true); } static int diff --git a/lib/librte_eal/common/include/rte_fbarray.h b/lib/librte_eal/common/include/rte_fbarray.h index 54abe938a..980b4969f 100644 --- a/lib/librte_eal/common/include/rte_fbarray.h +++ b/lib/librte_eal/common/include/rte_fbarray.h @@ -370,6 +370,50 @@ int __rte_experimental rte_fbarray_find_prev_used(struct rte_fbarray *arr, unsigned int start); +/** + * Find lowest start index of chunk of ``n`` free elements, down from specified + * index. + * + * @param arr + * Valid pointer to allocated and correctly set up ``rte_fbarray`` structure. + * + * @param start + * Element index to start search from. + * + * @param n + * Number of free elements to look for. + * + * @return + * - non-negative integer on success. + * - -1 on failure, with ``rte_errno`` indicating reason for failure. + */ +int __rte_experimental +rte_fbarray_find_prev_n_free(struct rte_fbarray *arr, unsigned int start, + unsigned int n); + + +/** + * Find lowest start index of chunk of ``n`` used elements, down from specified + * index. + * + * @param arr + * Valid pointer to allocated and correctly set up ``rte_fbarray`` structure. + * + * @param start + * Element index to start search from. + * + * @param n + * Number of used elements to look for. + * + * @return + * - non-negative integer on success. + * - -1 on failure, with ``rte_errno`` indicating reason for failure. + */ +int __rte_experimental +rte_fbarray_find_prev_n_used(struct rte_fbarray *arr, unsigned int start, + unsigned int n); + + /** * Dump ``rte_fbarray`` metadata. diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map index 79b87f504..3a1b93e12 100644 --- a/lib/librte_eal/rte_eal_version.map +++ b/lib/librte_eal/rte_eal_version.map @@ -271,6 +271,8 @@ EXPERIMENTAL { rte_fbarray_find_next_n_used; rte_fbarray_find_prev_free; rte_fbarray_find_prev_used; + rte_fbarray_find_prev_n_free; + rte_fbarray_find_prev_n_used; rte_fbarray_find_contig_free; rte_fbarray_find_contig_used; rte_fbarray_get; From patchwork Mon Jun 11 20:55:40 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Burakov, Anatoly" X-Patchwork-Id: 40991 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 455061DE9C; Mon, 11 Jun 2018 22:56:00 +0200 (CEST) Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by dpdk.org (Postfix) with ESMTP id ED5741DE46 for ; Mon, 11 Jun 2018 22:55:47 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga006.fm.intel.com ([10.253.24.20]) by fmsmga103.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 11 Jun 2018 13:55:44 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.51,211,1526367600"; d="scan'208";a="236556764" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by fmsmga006.fm.intel.com with ESMTP; 11 Jun 2018 13:55:44 -0700 Received: from sivswdev01.ir.intel.com (sivswdev01.ir.intel.com [10.237.217.45]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id w5BKthND026386 for ; Mon, 11 Jun 2018 21:55:43 +0100 Received: from sivswdev01.ir.intel.com (localhost [127.0.0.1]) by sivswdev01.ir.intel.com with ESMTP id w5BKthZo021617 for ; Mon, 11 Jun 2018 21:55:43 +0100 Received: (from aburakov@localhost) by sivswdev01.ir.intel.com with LOCAL id w5BKthMf021613 for dev@dpdk.org; Mon, 11 Jun 2018 21:55:43 +0100 From: Anatoly Burakov To: dev@dpdk.org Date: Mon, 11 Jun 2018 21:55:40 +0100 Message-Id: <65767a81393fa034a9813559d657b7ba34bf5df2.1528749451.git.anatoly.burakov@intel.com> X-Mailer: git-send-email 1.7.0.7 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH 7/9] fbarray: add reverse find contig used/free X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Add a function to return starting point of current contiguous block, going backwards. All semantics are kept the same as the existing function, with the only difference being that given the same input, results will be returned in reverse order. Signed-off-by: Anatoly Burakov --- lib/librte_eal/common/eal_common_fbarray.c | 90 +++++++++++++++++++-- lib/librte_eal/common/include/rte_fbarray.h | 36 +++++++++ lib/librte_eal/rte_eal_version.map | 2 + 3 files changed, 122 insertions(+), 6 deletions(-) diff --git a/lib/librte_eal/common/eal_common_fbarray.c b/lib/librte_eal/common/eal_common_fbarray.c index a2e01148b..977174c4f 100644 --- a/lib/librte_eal/common/eal_common_fbarray.c +++ b/lib/librte_eal/common/eal_common_fbarray.c @@ -569,6 +569,60 @@ find_prev(const struct rte_fbarray *arr, unsigned int start, bool used) return -1; } +static int +find_rev_contig(const struct rte_fbarray *arr, unsigned int start, bool used) +{ + const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz, + arr->len); + unsigned int idx, first, first_mod; + unsigned int need_len, result = 0; + + first = MASK_LEN_TO_IDX(start); + first_mod = MASK_LEN_TO_MOD(start); + + /* go backwards, include zero */ + idx = first; + do { + uint64_t cur = msk->data[idx]; + unsigned int run_len; + + need_len = MASK_ALIGN; + + /* if we're looking for free entries, invert mask */ + if (!used) + cur = ~cur; + + /* ignore everything after start on first iteration */ + if (idx == first) { + unsigned int end_len = MASK_ALIGN - first_mod - 1; + cur <<= end_len; + /* at the start, we don't need the full mask len */ + need_len -= end_len; + } + + /* we will be looking for zeroes, so invert the mask */ + cur = ~cur; + + /* if mask is zero, we have a complete run */ + if (cur == 0) + goto endloop; + + /* + * see where run ends, starting from the end. + */ + run_len = __builtin_clzll(cur); + + /* add however many zeroes we've had in the last run and quit */ + if (run_len < need_len) { + result += run_len; + break; + } +endloop: + result += need_len; + } while (idx-- != 0); /* decrement after check to include zero */ + return result; +} + static int set_used(struct rte_fbarray *arr, unsigned int idx, bool used) { @@ -1039,7 +1093,8 @@ rte_fbarray_find_prev_n_used(struct rte_fbarray *arr, unsigned int start, } static int -fbarray_find_contig(struct rte_fbarray *arr, unsigned int start, bool used) +fbarray_find_contig(struct rte_fbarray *arr, unsigned int start, bool next, + bool used) { int ret = -1; @@ -1057,22 +1112,33 @@ fbarray_find_contig(struct rte_fbarray *arr, unsigned int start, bool used) ret = 0; goto out; } - if (arr->len == arr->count) { + if (next && arr->count == arr->len) { ret = arr->len - start; goto out; } + if (!next && arr->count == arr->len) { + ret = start + 1; + goto out; + } } else { if (arr->len == arr->count) { ret = 0; goto out; } - if (arr->count == 0) { + if (next && arr->count == 0) { ret = arr->len - start; goto out; } + if (!next && arr->count == 0) { + ret = start + 1; + goto out; + } } - ret = find_contig(arr, start, false); + if (next) + ret = find_contig(arr, start, used); + else + ret = find_rev_contig(arr, start, used); out: rte_rwlock_read_unlock(&arr->rwlock); return ret; @@ -1081,13 +1147,25 @@ fbarray_find_contig(struct rte_fbarray *arr, unsigned int start, bool used) int __rte_experimental rte_fbarray_find_contig_free(struct rte_fbarray *arr, unsigned int start) { - return fbarray_find_contig(arr, start, false); + return fbarray_find_contig(arr, start, true, false); } int __rte_experimental rte_fbarray_find_contig_used(struct rte_fbarray *arr, unsigned int start) { - return fbarray_find_contig(arr, start, true); + return fbarray_find_contig(arr, start, true, true); +} + +int __rte_experimental +rte_fbarray_find_rev_contig_free(struct rte_fbarray *arr, unsigned int start) +{ + return fbarray_find_contig(arr, start, false, false); +} + +int __rte_experimental +rte_fbarray_find_rev_contig_used(struct rte_fbarray *arr, unsigned int start) +{ + return fbarray_find_contig(arr, start, false, true); } int __rte_experimental diff --git a/lib/librte_eal/common/include/rte_fbarray.h b/lib/librte_eal/common/include/rte_fbarray.h index 980b4969f..5d8805515 100644 --- a/lib/librte_eal/common/include/rte_fbarray.h +++ b/lib/librte_eal/common/include/rte_fbarray.h @@ -414,6 +414,42 @@ rte_fbarray_find_prev_n_used(struct rte_fbarray *arr, unsigned int start, unsigned int n); +/** + * Find how many more free entries there are before specified index (like + * ``rte_fbarray_find_contig_free`` but going in reverse). + * + * @param arr + * Valid pointer to allocated and correctly set up ``rte_fbarray`` structure. + * + * @param start + * Element index to start search from. + * + * @return + * - non-negative integer on success. + * - -1 on failure, with ``rte_errno`` indicating reason for failure. + */ +int __rte_experimental +rte_fbarray_find_rev_contig_free(struct rte_fbarray *arr, + unsigned int start); + + +/** + * Find how many more used entries there are before specified index (like + * ``rte_fbarray_find_contig_used`` but going in reverse). + * + * @param arr + * Valid pointer to allocated and correctly set up ``rte_fbarray`` structure. + * + * @param start + * Element index to start search from. + * + * @return + * - non-negative integer on success. + * - -1 on failure, with ``rte_errno`` indicating reason for failure. + */ +int __rte_experimental +rte_fbarray_find_rev_contig_used(struct rte_fbarray *arr, unsigned int start); + /** * Dump ``rte_fbarray`` metadata. diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map index 3a1b93e12..6936ba308 100644 --- a/lib/librte_eal/rte_eal_version.map +++ b/lib/librte_eal/rte_eal_version.map @@ -275,6 +275,8 @@ EXPERIMENTAL { rte_fbarray_find_prev_n_used; rte_fbarray_find_contig_free; rte_fbarray_find_contig_used; + rte_fbarray_find_rev_contig_free; + rte_fbarray_find_rev_contig_used; rte_fbarray_get; rte_fbarray_init; rte_fbarray_is_used; From patchwork Mon Jun 11 20:55:41 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Burakov, Anatoly" X-Patchwork-Id: 40994 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 677981DEB2; Mon, 11 Jun 2018 22:56:05 +0200 (CEST) Received: from mga04.intel.com (mga04.intel.com [192.55.52.120]) by dpdk.org (Postfix) with ESMTP id 8595A1DB16 for ; Mon, 11 Jun 2018 22:55:48 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga007.fm.intel.com ([10.253.24.52]) by fmsmga104.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 11 Jun 2018 13:55:45 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.51,211,1526367600"; d="scan'208";a="46337847" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by fmsmga007.fm.intel.com with ESMTP; 11 Jun 2018 13:55:44 -0700 Received: from sivswdev01.ir.intel.com (sivswdev01.ir.intel.com [10.237.217.45]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id w5BKthtK026389 for ; Mon, 11 Jun 2018 21:55:43 +0100 Received: from sivswdev01.ir.intel.com (localhost [127.0.0.1]) by sivswdev01.ir.intel.com with ESMTP id w5BKthLT021624 for ; Mon, 11 Jun 2018 21:55:43 +0100 Received: (from aburakov@localhost) by sivswdev01.ir.intel.com with LOCAL id w5BKthQN021620 for dev@dpdk.org; Mon, 11 Jun 2018 21:55:43 +0100 From: Anatoly Burakov To: dev@dpdk.org Date: Mon, 11 Jun 2018 21:55:41 +0100 Message-Id: X-Mailer: git-send-email 1.7.0.7 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH 8/9] test: add fbarray autotests X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Introduce a suite of autotests to cover functionality of fbarray. This will check for invalid parameters, check API return values and errno codes, and will also do some basic functionality checks on the indexing code. Signed-off-by: Anatoly Burakov --- test/test/Makefile | 1 + test/test/test_fbarray.c | 576 +++++++++++++++++++++++++++++++++++++++ 2 files changed, 577 insertions(+) create mode 100644 test/test/test_fbarray.c diff --git a/test/test/Makefile b/test/test/Makefile index eccc8efcf..41eab00e7 100644 --- a/test/test/Makefile +++ b/test/test/Makefile @@ -70,6 +70,7 @@ SRCS-y += test_memzone.c SRCS-y += test_bitmap.c SRCS-y += test_reciprocal_division.c SRCS-y += test_reciprocal_division_perf.c +SRCS-y += test_fbarray.c SRCS-y += test_ring.c SRCS-y += test_ring_perf.c diff --git a/test/test/test_fbarray.c b/test/test/test_fbarray.c new file mode 100644 index 000000000..8c44e2c7e --- /dev/null +++ b/test/test/test_fbarray.c @@ -0,0 +1,576 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2010-2014 Intel Corporation + */ + +#include +#include +#include + +#include +#include +#include +#include + +#include "test.h" + +struct fbarray_testsuite_params { + struct rte_fbarray arr; + int start; + int end; +}; + +static struct fbarray_testsuite_params param; + +#define FBARRAY_TEST_ARR_NAME "fbarray_autotest" +#define FBARRAY_TEST_LEN 256 +#define FBARRAY_TEST_ELT_SZ (sizeof(int)) + +static int autotest_setup(void) +{ + return rte_fbarray_init(¶m.arr, FBARRAY_TEST_ARR_NAME, + FBARRAY_TEST_LEN, FBARRAY_TEST_ELT_SZ); +} + +static void autotest_teardown(void) +{ + rte_fbarray_destroy(¶m.arr); +} + +static int init_array(void) +{ + int i; + for (i = param.start; i <= param.end; i++) { + if (rte_fbarray_set_used(¶m.arr, i)) + return -1; + } + return 0; +} + +static void reset_array(void) +{ + int i; + for (i = 0; i < FBARRAY_TEST_LEN; i++) + rte_fbarray_set_free(¶m.arr, i); +} + +static int first_msk_test_setup(void) +{ + /* put all within first mask */ + param.start = 3; + param.end = 10; + return init_array(); +} + +static int cross_msk_test_setup(void) +{ + /* put all within second and third mask */ + param.start = 70; + param.end = 160; + return init_array(); +} + +static int multi_msk_test_setup(void) +{ + /* put all within first and last mask */ + param.start = 3; + param.end = FBARRAY_TEST_LEN - 20; + return init_array(); +} + +static int last_msk_test_setup(void) +{ + /* put all within last mask */ + param.start = FBARRAY_TEST_LEN - 20; + param.end = FBARRAY_TEST_LEN - 1; + return init_array(); +} + +static int full_msk_test_setup(void) +{ + /* fill entire mask */ + param.start = 0; + param.end = FBARRAY_TEST_LEN - 1; + return init_array(); +} + +static int empty_msk_test_setup(void) +{ + /* do not fill anything in */ + reset_array(); + return 0; +} + +static int test_invalid(void) +{ + struct rte_fbarray dummy; + + /* invalid parameters */ + TEST_ASSERT_FAIL(rte_fbarray_attach(NULL), + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT_FAIL(rte_fbarray_detach(NULL), + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT_FAIL(rte_fbarray_destroy(NULL), + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno valuey\n"); + TEST_ASSERT_FAIL(rte_fbarray_init(NULL, "fail", 16, 16), + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT_FAIL(rte_fbarray_init(&dummy, NULL, 16, 16), + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT_FAIL(rte_fbarray_init(&dummy, "fail", 0, 16), + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT_FAIL(rte_fbarray_init(&dummy, "fail", 16, 0), + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + /* len must not be greater than INT_MAX */ + TEST_ASSERT_FAIL(rte_fbarray_init(&dummy, "fail", INT_MAX + 1U, 16), + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT_NULL(rte_fbarray_get(NULL, 0), + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_idx(NULL, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_set_free(NULL, 0), + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_set_used(NULL, 0), + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_contig_free(NULL, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_contig_used(NULL, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_rev_contig_free(NULL, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_rev_contig_used(NULL, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_next_free(NULL, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_next_used(NULL, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_prev_free(NULL, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_prev_used(NULL, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_next_n_free(NULL, 0, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_next_n_used(NULL, 0, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_prev_n_free(NULL, 0, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_prev_n_used(NULL, 0, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_is_used(NULL, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT_SUCCESS(rte_fbarray_init(&dummy, "success", + FBARRAY_TEST_LEN, 8), + "Failed to initialize valid fbarray\n"); + + /* test API for handling invalid parameters with a valid fbarray */ + TEST_ASSERT_NULL(rte_fbarray_get(&dummy, FBARRAY_TEST_LEN), + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT(rte_fbarray_find_idx(&dummy, NULL) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT(rte_fbarray_set_free(&dummy, FBARRAY_TEST_LEN), + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT(rte_fbarray_set_used(&dummy, FBARRAY_TEST_LEN), + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT(rte_fbarray_find_contig_free(&dummy, FBARRAY_TEST_LEN) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT(rte_fbarray_find_contig_used(&dummy, FBARRAY_TEST_LEN) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT(rte_fbarray_find_rev_contig_free(&dummy, + FBARRAY_TEST_LEN) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT(rte_fbarray_find_rev_contig_used(&dummy, + FBARRAY_TEST_LEN) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT(rte_fbarray_find_next_free(&dummy, FBARRAY_TEST_LEN) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT(rte_fbarray_find_next_used(&dummy, FBARRAY_TEST_LEN) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT(rte_fbarray_find_prev_free(&dummy, FBARRAY_TEST_LEN) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT(rte_fbarray_find_prev_used(&dummy, FBARRAY_TEST_LEN) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT(rte_fbarray_find_next_n_free(&dummy, + FBARRAY_TEST_LEN, 1) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_next_n_free(&dummy, 0, + FBARRAY_TEST_LEN + 1) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_next_n_free(&dummy, 0, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT(rte_fbarray_find_next_n_used(&dummy, + FBARRAY_TEST_LEN, 1) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_next_n_used(&dummy, 0, + FBARRAY_TEST_LEN + 1) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_next_n_used(&dummy, 0, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT(rte_fbarray_find_prev_n_free(&dummy, + FBARRAY_TEST_LEN, 1) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_prev_n_free(&dummy, 0, + FBARRAY_TEST_LEN + 1) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_prev_n_free(&dummy, 0, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT(rte_fbarray_find_prev_n_used(&dummy, + FBARRAY_TEST_LEN, 1) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_prev_n_used(&dummy, 0, + FBARRAY_TEST_LEN + 1) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_prev_n_used(&dummy, 0, 0) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT(rte_fbarray_is_used(&dummy, FBARRAY_TEST_LEN) < 0, + "Call succeeded with invalid parameters\n"); + TEST_ASSERT_EQUAL(rte_errno, EINVAL, "Wrong errno value\n"); + + TEST_ASSERT_SUCCESS(rte_fbarray_destroy(&dummy), + "Failed to destroy valid fbarray\n"); + + return TEST_SUCCESS; +} + +static int check_free(void) +{ + const int idx = 0; + const int last_idx = FBARRAY_TEST_LEN - 1; + + /* ensure we can find a free spot */ + TEST_ASSERT_EQUAL(rte_fbarray_find_next_free(¶m.arr, idx), idx, + "Free space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_next_n_free(¶m.arr, idx, 1), idx, + "Free space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_contig_free(¶m.arr, idx), + FBARRAY_TEST_LEN, + "Free space not found where expected\n"); + + TEST_ASSERT_EQUAL(rte_fbarray_find_prev_free(¶m.arr, idx), idx, + "Free space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_prev_n_free(¶m.arr, idx, 1), idx, + "Free space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_free(¶m.arr, idx), 1, + "Free space not found where expected\n"); + + TEST_ASSERT_EQUAL(rte_fbarray_find_prev_free(¶m.arr, last_idx), + last_idx, "Free space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_prev_n_free(¶m.arr, last_idx, 1), + last_idx, "Free space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_free(¶m.arr, + last_idx), FBARRAY_TEST_LEN, + "Free space not found where expected\n"); + + /* ensure we can't find any used spots */ + TEST_ASSERT(rte_fbarray_find_next_used(¶m.arr, idx) < 0, + "Used space found where none was expected\n"); + TEST_ASSERT_EQUAL(rte_errno, ENOENT, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_next_n_used(¶m.arr, idx, 1) < 0, + "Used space found where none was expected\n"); + TEST_ASSERT_EQUAL(rte_errno, ENOENT, "Wrong errno value\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_contig_used(¶m.arr, idx), 0, + "Used space found where none was expected\n"); + + TEST_ASSERT(rte_fbarray_find_prev_used(¶m.arr, last_idx) < 0, + "Used space found where none was expected\n"); + TEST_ASSERT_EQUAL(rte_errno, ENOENT, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_prev_n_used(¶m.arr, last_idx, 1) < 0, + "Used space found where none was expected\n"); + TEST_ASSERT_EQUAL(rte_errno, ENOENT, "Wrong errno value\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_used(¶m.arr, + last_idx), 0, + "Used space found where none was expected\n"); + + return 0; +} + +static int check_used_one(void) +{ + const int idx = 0; + const int last_idx = FBARRAY_TEST_LEN - 1; + + /* check that we can find used spots now */ + TEST_ASSERT_EQUAL(rte_fbarray_find_next_used(¶m.arr, idx), idx, + "Used space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_next_n_used(¶m.arr, idx, 1), idx, + "Used space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_contig_used(¶m.arr, idx), 1, + "Used space not found where expected\n"); + + TEST_ASSERT_EQUAL(rte_fbarray_find_prev_used(¶m.arr, last_idx), idx, + "Used space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_prev_n_used(¶m.arr, last_idx, 1), + idx, "Used space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_used(¶m.arr, idx), 1, + "Used space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_used(¶m.arr, + last_idx), idx, + "Used space not found where expected\n"); + + /* check if further indices are still free */ + TEST_ASSERT(rte_fbarray_find_next_used(¶m.arr, idx + 1) < 0, + "Used space not found where none was expected\n"); + TEST_ASSERT_EQUAL(rte_errno, ENOENT, "Wrong errno value\n"); + TEST_ASSERT(rte_fbarray_find_next_n_used(¶m.arr, idx + 1, 1) < 0, + "Used space not found where none was expected\n"); + TEST_ASSERT_EQUAL(rte_errno, ENOENT, "Wrong errno value\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_contig_used(¶m.arr, idx + 1), 0, + "Used space not found where none was expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_contig_free(¶m.arr, idx + 1), + FBARRAY_TEST_LEN - 1, + "Used space not found where none was expected\n"); + + TEST_ASSERT_EQUAL(rte_fbarray_find_prev_used(¶m.arr, last_idx), 0, + "Used space not found where none was expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_prev_n_used(¶m.arr, last_idx, 1), + 0, "Used space not found where none was expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_used(¶m.arr, + last_idx), 0, + "Used space not found where none was expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_free(¶m.arr, + last_idx), FBARRAY_TEST_LEN - 1, + "Used space not found where none was expected\n"); + + return 0; +} + +static int test_basic(void) +{ + const int idx = 0; + int i; + + /* check array count */ + TEST_ASSERT_EQUAL(param.arr.count, 0, "Wrong element count\n"); + + /* ensure we can find a free spot */ + if (check_free()) + return TEST_FAILED; + + /* check if used */ + TEST_ASSERT_EQUAL(rte_fbarray_is_used(¶m.arr, idx), 0, + "Used space found where not expected\n"); + + /* mark as used */ + TEST_ASSERT_SUCCESS(rte_fbarray_set_used(¶m.arr, idx), + "Failed to set as used\n"); + + /* check if used again */ + TEST_ASSERT_NOT_EQUAL(rte_fbarray_is_used(¶m.arr, idx), 0, + "Used space not found where expected\n"); + + if (check_used_one()) + return TEST_FAILED; + + /* check array count */ + TEST_ASSERT_EQUAL(param.arr.count, 1, "Wrong element count\n"); + + /* check if getting pointers works for every element */ + for (i = 0; i < FBARRAY_TEST_LEN; i++) { + void *td = rte_fbarray_get(¶m.arr, i); + TEST_ASSERT_NOT_NULL(td, "Invalid pointer returned\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_idx(¶m.arr, td), i, + "Wrong index returned\n"); + } + + /* mark as free */ + TEST_ASSERT_SUCCESS(rte_fbarray_set_free(¶m.arr, idx), + "Failed to set as free\n"); + + /* check array count */ + TEST_ASSERT_EQUAL(param.arr.count, 0, "Wrong element count\n"); + + /* check if used */ + TEST_ASSERT_EQUAL(rte_fbarray_is_used(¶m.arr, idx), 0, + "Used space found where not expected\n"); + + if (check_free()) + return TEST_FAILED; + + reset_array(); + + return TEST_SUCCESS; +} + +static int ensure_correct(struct rte_fbarray *arr, int first, int last, + bool used) +{ + int i, len = last - first + 1; + for (i = 0; i < len; i++) { + int cur = first + i; + int cur_len = len - i; + + if (used) { + TEST_ASSERT_EQUAL(rte_fbarray_find_contig_used(arr, + cur), cur_len, + "Used space length is wrong\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_used(arr, + last), len, + "Used space length is wrong\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_used(arr, + cur), i + 1, + "Used space length is wrong\n"); + + TEST_ASSERT_EQUAL(rte_fbarray_find_next_used(arr, cur), + cur, + "Used space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_next_n_used(arr, + cur, 1), cur, + "Used space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_next_n_used(arr, cur, + cur_len), cur, + "Used space not found where expected\n"); + + TEST_ASSERT_EQUAL(rte_fbarray_find_prev_used(arr, cur), + cur, + "Used space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_prev_n_used(arr, + last, cur_len), cur, + "Used space not found where expected\n"); + } else { + TEST_ASSERT_EQUAL(rte_fbarray_find_contig_free(arr, + cur), cur_len, + "Free space length is wrong\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_free(arr, + last), len, + "Free space length is wrong\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_free(arr, + cur), i + 1, + "Free space length is wrong\n"); + + TEST_ASSERT_EQUAL(rte_fbarray_find_next_free(arr, cur), + cur, + "Free space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_next_n_free(arr, cur, + 1), cur, + "Free space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_next_n_free(arr, cur, + cur_len), cur, + "Free space not found where expected\n"); + + TEST_ASSERT_EQUAL(rte_fbarray_find_prev_free(arr, cur), + cur, + "Free space not found where expected\n"); + TEST_ASSERT_EQUAL(rte_fbarray_find_prev_n_free(arr, + last, cur_len), cur, + "Free space not found where expected\n"); + } + } + return 0; +} + +static int test_find(void) +{ + TEST_ASSERT_EQUAL((int)param.arr.count, param.end - param.start + 1, + "Wrong element count\n"); + /* ensure space is free before start */ + if (ensure_correct(¶m.arr, 0, param.start - 1, false)) + return TEST_FAILED; + /* ensure space is occupied where it's supposed to be */ + if (ensure_correct(¶m.arr, param.start, param.end, true)) + return TEST_FAILED; + /* ensure space after end is free as well */ + if (ensure_correct(¶m.arr, param.end + 1, FBARRAY_TEST_LEN - 1, + false)) + return TEST_FAILED; + return TEST_SUCCESS; +} + +static int test_empty(void) +{ + TEST_ASSERT_EQUAL((int)param.arr.count, 0, "Wrong element count\n"); + /* ensure space is free */ + if (ensure_correct(¶m.arr, 0, FBARRAY_TEST_LEN - 1, false)) + return TEST_FAILED; + return TEST_SUCCESS; +} + + +static struct unit_test_suite fbarray_test_suite = { + .suite_name = "fbarray autotest", + .setup = autotest_setup, + .teardown = autotest_teardown, + .unit_test_cases = { + TEST_CASE(test_invalid), + TEST_CASE(test_basic), + TEST_CASE_ST(first_msk_test_setup, reset_array, test_find), + TEST_CASE_ST(cross_msk_test_setup, reset_array, test_find), + TEST_CASE_ST(multi_msk_test_setup, reset_array, test_find), + TEST_CASE_ST(last_msk_test_setup, reset_array, test_find), + TEST_CASE_ST(full_msk_test_setup, reset_array, test_find), + TEST_CASE_ST(empty_msk_test_setup, reset_array, test_empty), + TEST_CASES_END() + } +}; + +static int +test_fbarray(void) +{ + return unit_test_suite_runner(&fbarray_test_suite); +} + +REGISTER_TEST_COMMAND(fbarray_autotest, test_fbarray); From patchwork Mon Jun 11 20:55:42 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Burakov, Anatoly" X-Patchwork-Id: 40995 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id D6F311DEBB; Mon, 11 Jun 2018 22:56:06 +0200 (CEST) Received: from mga12.intel.com (mga12.intel.com [192.55.52.136]) by dpdk.org (Postfix) with ESMTP id 08C981D940 for ; Mon, 11 Jun 2018 22:55:48 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga005.jf.intel.com ([10.7.209.41]) by fmsmga106.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 11 Jun 2018 13:55:48 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.51,211,1526367600"; d="scan'208";a="231737140" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by orsmga005.jf.intel.com with ESMTP; 11 Jun 2018 13:55:45 -0700 Received: from sivswdev01.ir.intel.com (sivswdev01.ir.intel.com [10.237.217.45]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id w5BKthPd026392 for ; Mon, 11 Jun 2018 21:55:43 +0100 Received: from sivswdev01.ir.intel.com (localhost [127.0.0.1]) by sivswdev01.ir.intel.com with ESMTP id w5BKthdp021631 for ; Mon, 11 Jun 2018 21:55:43 +0100 Received: (from aburakov@localhost) by sivswdev01.ir.intel.com with LOCAL id w5BKthpF021627 for dev@dpdk.org; Mon, 11 Jun 2018 21:55:43 +0100 From: Anatoly Burakov To: dev@dpdk.org Date: Mon, 11 Jun 2018 21:55:42 +0100 Message-Id: <914a5f584be81d6c129b35bc8e358774854d8960.1528749451.git.anatoly.burakov@intel.com> X-Mailer: git-send-email 1.7.0.7 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH 9/9] memalloc: allocate memory in reverse X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Currently, all hugepages are allocated from lower VA address to higher VA address, while malloc heap allocates from higher VA address to lower VA address. This results in heap fragmentation over time due to multiple reserves leaving small space below the allocated elements. Fix this by allocating VA memory from the top, thereby reducing fragmentation and lowering overall memory usage. Signed-off-by: Anatoly Burakov --- lib/librte_eal/linuxapp/eal/eal_memalloc.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/lib/librte_eal/linuxapp/eal/eal_memalloc.c b/lib/librte_eal/linuxapp/eal/eal_memalloc.c index 8c11f98c9..d35fb52c4 100644 --- a/lib/librte_eal/linuxapp/eal/eal_memalloc.c +++ b/lib/librte_eal/linuxapp/eal/eal_memalloc.c @@ -682,7 +682,8 @@ alloc_seg_walk(const struct rte_memseg_list *msl, void *arg) need = wa->n_segs; /* try finding space in memseg list */ - cur_idx = rte_fbarray_find_next_n_free(&cur_msl->memseg_arr, 0, need); + cur_idx = rte_fbarray_find_prev_n_free(&cur_msl->memseg_arr, + cur_msl->memseg_arr.len - 1, need); if (cur_idx < 0) return 0; start_idx = cur_idx;