From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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: , X-List-Received-Date: Mon, 11 Jun 2018 20:55:48 -0000 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; -- 2.17.1