From: Anatoly Burakov <anatoly.burakov@intel.com>
To: dev@dpdk.org
Subject: [dpdk-dev] [PATCH 5/9] fbarray: add reverse find_free/used
Date: Mon, 11 Jun 2018 21:55:38 +0100 [thread overview]
Message-ID: <35f3ada5026b8619499ddd3a8b41b2d1066c3e31.1528749451.git.anatoly.burakov@intel.com> (raw)
In-Reply-To: <cover.1528749451.git.anatoly.burakov@intel.com>
In-Reply-To: <cover.1528749451.git.anatoly.burakov@intel.com>
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 <anatoly.burakov@intel.com>
---
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;
--
2.17.1
next prev parent reply other threads:[~2018-06-11 20:55 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-06-11 20:55 [dpdk-dev] [PATCH 0/9] mem: reduce memory fragmentation Anatoly Burakov
2018-06-11 20:55 ` [dpdk-dev] [PATCH 1/9] fbarray: fix errno values returned from functions Anatoly Burakov
2018-06-11 20:55 ` [dpdk-dev] [PATCH 2/9] fbarray: reduce duplication in find_contig code Anatoly Burakov
2018-06-11 20:55 ` [dpdk-dev] [PATCH 3/9] fbarray: reduce duplication in find_next_n code Anatoly Burakov
2018-06-11 20:55 ` [dpdk-dev] [PATCH 4/9] fbarray: reduce duplication in find_next code Anatoly Burakov
2018-06-11 20:55 ` Anatoly Burakov [this message]
2018-06-11 20:55 ` [dpdk-dev] [PATCH 6/9] fbarray: add reverse find n used/free Anatoly Burakov
2018-06-11 20:55 ` [dpdk-dev] [PATCH 7/9] fbarray: add reverse find contig used/free Anatoly Burakov
2018-06-11 20:55 ` [dpdk-dev] [PATCH 8/9] test: add fbarray autotests Anatoly Burakov
2018-06-11 20:55 ` [dpdk-dev] [PATCH 9/9] memalloc: allocate memory in reverse Anatoly Burakov
2018-07-24 10:10 ` Burakov, Anatoly
2018-07-24 10:24 ` Thomas Monjalon
2018-07-13 9:06 ` [dpdk-dev] [PATCH 0/9] mem: reduce memory fragmentation Thomas Monjalon
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=35f3ada5026b8619499ddd3a8b41b2d1066c3e31.1528749451.git.anatoly.burakov@intel.com \
--to=anatoly.burakov@intel.com \
--cc=dev@dpdk.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).