From: Anatoly Burakov <anatoly.burakov@intel.com>
To: dev@dpdk.org
Subject: [dpdk-dev] [PATCH 7/9] fbarray: add reverse find contig used/free
Date: Mon, 11 Jun 2018 21:55:40 +0100 [thread overview]
Message-ID: <65767a81393fa034a9813559d657b7ba34bf5df2.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 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 <anatoly.burakov@intel.com>
---
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
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 ` [dpdk-dev] [PATCH 5/9] fbarray: add reverse find_free/used Anatoly Burakov
2018-06-11 20:55 ` [dpdk-dev] [PATCH 6/9] fbarray: add reverse find n used/free Anatoly Burakov
2018-06-11 20:55 ` Anatoly Burakov [this message]
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=65767a81393fa034a9813559d657b7ba34bf5df2.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).