[dpdk-dev] [PATCH 0/9] mem: reduce memory fragmentation

[dpdk-dev] [PATCH 0/9] mem: reduce memory fragmentation

[Anatoly Burakov]

This patchset is mostly dealing with changes fbarray, but it is
actually about reducing fragmentation in Linuxapp memalloc.

We allocate hugepages from lower VA to higher VA. However, our
malloc heap allocates addresses from higher VA to lower VA. This
results in a situation where, whenever new page is allocated,
malloc starts to allocate memory from the top, leaving fragmented
space between new allocation's leftover and previous leftover.

Over time, this leads to lots of free elements sitting at page
boundaries, small enough to be useful but large enough to have an
impact on memory fragmentation in certain circumstances.

To fix this, we need to allocate memory from higher VA first.
However, in order to do that, we need the ability to search fbarray
in reverse, which is currently not supported. Adding this support is
what most of this patchset is about.

First 4 patches fix some issues in existing fbarray implementation
and remove some code duplication, preparing for adding of new
functionality.

Next 3 patches add new functionality - reverse search of used/free
slots, mirroring already existing functionality in semantics and
capable of returning identical results but in reverse order.

Patch 8 adds unit tests for fbarray, testing both existing and new
functionality.

Finally, patch 9 changes memalloc to look up free slots in memseg
list in reverse order. No other changes is necessary, as all other
code can handle segments, wherever they are allocated.

Anatoly Burakov (9):
  fbarray: fix errno values returned from functions
  fbarray: reduce duplication in find_contig code
  fbarray: reduce duplication in find_next_n code
  fbarray: reduce duplication in find_next code
  fbarray: add reverse find_free/used
  fbarray: add reverse find n used/free
  fbarray: add reverse find contig used/free
  test: add fbarray autotests
  memalloc: allocate memory in reverse

 lib/librte_eal/common/eal_common_fbarray.c  | 493 ++++++++++++++---
 lib/librte_eal/common/include/rte_fbarray.h | 114 ++++
 lib/librte_eal/linuxapp/eal/eal_memalloc.c  |   3 +-
 lib/librte_eal/rte_eal_version.map          |   6 +
 test/test/Makefile                          |   1 +
 test/test/test_fbarray.c                    | 576 ++++++++++++++++++++
 6 files changed, 1119 insertions(+), 74 deletions(-)
 create mode 100644 test/test/test_fbarray.c

-- 
2.17.1

[dpdk-dev] [PATCH 1/9] fbarray: fix errno values returned from functions

[Anatoly Burakov]

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 <anatoly.burakov@intel.com>
---
 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;
 }
 
-- 
2.17.1

[dpdk-dev] [PATCH 2/9] fbarray: reduce duplication in find_contig code

[Anatoly Burakov]

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 <anatoly.burakov@intel.com>
---
 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
-- 
2.17.1

[dpdk-dev] [PATCH 3/9] fbarray: reduce duplication in find_next_n code

[Anatoly Burakov]

Mostly code move, aside from more quick checks done to avoid
doing computations in obviously hopeless cases.

Signed-off-by: Anatoly Burakov <anatoly.burakov@intel.com>
---
 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
-- 
2.17.1

[dpdk-dev] [PATCH 4/9] fbarray: reduce duplication in find_next code

[Anatoly Burakov]

Just code move to put all checks and calls in one place.

Signed-off-by: Anatoly Burakov <anatoly.burakov@intel.com>
---
 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
-- 
2.17.1

[dpdk-dev] [PATCH 5/9] fbarray: add reverse find_free/used

[Anatoly Burakov]

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

[dpdk-dev] [PATCH 6/9] fbarray: add reverse find n used/free

[Anatoly Burakov]

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 <anatoly.burakov@intel.com>
---
 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;
-- 
2.17.1

[dpdk-dev] [PATCH 7/9] fbarray: add reverse find contig used/free

[Anatoly Burakov]

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

[dpdk-dev] [PATCH 8/9] test: add fbarray autotests

[Anatoly Burakov]

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 <anatoly.burakov@intel.com>
---
 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 <stdio.h>
+#include <stdint.h>
+#include <limits.h>
+
+#include <rte_common.h>
+#include <rte_debug.h>
+#include <rte_errno.h>
+#include <rte_fbarray.h>
+
+#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(&param.arr, FBARRAY_TEST_ARR_NAME,
+			FBARRAY_TEST_LEN, FBARRAY_TEST_ELT_SZ);
+}
+
+static void autotest_teardown(void)
+{
+	rte_fbarray_destroy(&param.arr);
+}
+
+static int init_array(void)
+{
+	int i;
+	for (i = param.start; i <= param.end; i++) {
+		if (rte_fbarray_set_used(&param.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(&param.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(&param.arr, idx), idx,
+			"Free space not found where expected\n");
+	TEST_ASSERT_EQUAL(rte_fbarray_find_next_n_free(&param.arr, idx, 1), idx,
+			"Free space not found where expected\n");
+	TEST_ASSERT_EQUAL(rte_fbarray_find_contig_free(&param.arr, idx),
+			FBARRAY_TEST_LEN,
+			"Free space not found where expected\n");
+
+	TEST_ASSERT_EQUAL(rte_fbarray_find_prev_free(&param.arr, idx), idx,
+			"Free space not found where expected\n");
+	TEST_ASSERT_EQUAL(rte_fbarray_find_prev_n_free(&param.arr, idx, 1), idx,
+			"Free space not found where expected\n");
+	TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_free(&param.arr, idx), 1,
+			"Free space not found where expected\n");
+
+	TEST_ASSERT_EQUAL(rte_fbarray_find_prev_free(&param.arr, last_idx),
+			last_idx, "Free space not found where expected\n");
+	TEST_ASSERT_EQUAL(rte_fbarray_find_prev_n_free(&param.arr, last_idx, 1),
+			last_idx, "Free space not found where expected\n");
+	TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_free(&param.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(&param.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(&param.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(&param.arr, idx), 0,
+			"Used space found where none was expected\n");
+
+	TEST_ASSERT(rte_fbarray_find_prev_used(&param.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(&param.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(&param.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(&param.arr, idx), idx,
+			"Used space not found where expected\n");
+	TEST_ASSERT_EQUAL(rte_fbarray_find_next_n_used(&param.arr, idx, 1), idx,
+			"Used space not found where expected\n");
+	TEST_ASSERT_EQUAL(rte_fbarray_find_contig_used(&param.arr, idx), 1,
+			"Used space not found where expected\n");
+
+	TEST_ASSERT_EQUAL(rte_fbarray_find_prev_used(&param.arr, last_idx), idx,
+			"Used space not found where expected\n");
+	TEST_ASSERT_EQUAL(rte_fbarray_find_prev_n_used(&param.arr, last_idx, 1),
+			idx, "Used space not found where expected\n");
+	TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_used(&param.arr, idx), 1,
+			"Used space not found where expected\n");
+	TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_used(&param.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(&param.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(&param.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(&param.arr, idx + 1), 0,
+			"Used space not found where none was expected\n");
+	TEST_ASSERT_EQUAL(rte_fbarray_find_contig_free(&param.arr, idx + 1),
+			FBARRAY_TEST_LEN - 1,
+			"Used space not found where none was expected\n");
+
+	TEST_ASSERT_EQUAL(rte_fbarray_find_prev_used(&param.arr, last_idx), 0,
+			"Used space not found where none was expected\n");
+	TEST_ASSERT_EQUAL(rte_fbarray_find_prev_n_used(&param.arr, last_idx, 1),
+			0, "Used space not found where none was expected\n");
+	TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_used(&param.arr,
+			last_idx), 0,
+			"Used space not found where none was expected\n");
+	TEST_ASSERT_EQUAL(rte_fbarray_find_rev_contig_free(&param.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(&param.arr, idx), 0,
+			"Used space found where not expected\n");
+
+	/* mark as used */
+	TEST_ASSERT_SUCCESS(rte_fbarray_set_used(&param.arr, idx),
+			"Failed to set as used\n");
+
+	/* check if used again */
+	TEST_ASSERT_NOT_EQUAL(rte_fbarray_is_used(&param.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(&param.arr, i);
+		TEST_ASSERT_NOT_NULL(td, "Invalid pointer returned\n");
+		TEST_ASSERT_EQUAL(rte_fbarray_find_idx(&param.arr, td), i,
+				"Wrong index returned\n");
+	}
+
+	/* mark as free */
+	TEST_ASSERT_SUCCESS(rte_fbarray_set_free(&param.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(&param.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(&param.arr, 0, param.start - 1, false))
+		return TEST_FAILED;
+	/* ensure space is occupied where it's supposed to be */
+	if (ensure_correct(&param.arr, param.start, param.end, true))
+		return TEST_FAILED;
+	/* ensure space after end is free as well */
+	if (ensure_correct(&param.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(&param.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);
-- 
2.17.1

[dpdk-dev] [PATCH 9/9] memalloc: allocate memory in reverse

[Anatoly Burakov]

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 <anatoly.burakov@intel.com>
---
 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;
-- 
2.17.1

Re: [dpdk-dev] [PATCH 0/9] mem: reduce memory fragmentation

[Thomas Monjalon]

11/06/2018 22:55, Anatoly Burakov:
> This patchset is mostly dealing with changes fbarray, but it is
> actually about reducing fragmentation in Linuxapp memalloc.
> 
> We allocate hugepages from lower VA to higher VA. However, our
> malloc heap allocates addresses from higher VA to lower VA. This
> results in a situation where, whenever new page is allocated,
> malloc starts to allocate memory from the top, leaving fragmented
> space between new allocation's leftover and previous leftover.
> 
> Over time, this leads to lots of free elements sitting at page
> boundaries, small enough to be useful but large enough to have an
> impact on memory fragmentation in certain circumstances.
> 
> To fix this, we need to allocate memory from higher VA first.
> However, in order to do that, we need the ability to search fbarray
> in reverse, which is currently not supported. Adding this support is
> what most of this patchset is about.
> 
> First 4 patches fix some issues in existing fbarray implementation
> and remove some code duplication, preparing for adding of new
> functionality.
> 
> Next 3 patches add new functionality - reverse search of used/free
> slots, mirroring already existing functionality in semantics and
> capable of returning identical results but in reverse order.
> 
> Patch 8 adds unit tests for fbarray, testing both existing and new
> functionality.
> 
> Finally, patch 9 changes memalloc to look up free slots in memseg
> list in reverse order. No other changes is necessary, as all other
> code can handle segments, wherever they are allocated.
> 
> Anatoly Burakov (9):
>   fbarray: fix errno values returned from functions
>   fbarray: reduce duplication in find_contig code
>   fbarray: reduce duplication in find_next_n code
>   fbarray: reduce duplication in find_next code
>   fbarray: add reverse find_free/used
>   fbarray: add reverse find n used/free
>   fbarray: add reverse find contig used/free
>   test: add fbarray autotests
>   memalloc: allocate memory in reverse

Applied, thanks

Re: [dpdk-dev] [PATCH 9/9] memalloc: allocate memory in reverse

[Burakov, Anatoly]

On 11-Jun-18 9:55 PM, Anatoly Burakov wrote:
> 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 <anatoly.burakov@intel.com>
> ---
>   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;
> 

Hi Thomas,

We have discovered a few regressions in virtio/vhost use cases due to 
this patch. Virtio expects to map all segments starting from 0 address, 
and this patch breaks that assumption.

Can we revert this for 18.08? It will be reintroduced in 18.11 along 
with fixes for virtio/vhost fixes to account for this change.

-- 
Thanks,
Anatoly

Re: [dpdk-dev] [PATCH 9/9] memalloc: allocate memory in reverse

[Thomas Monjalon]

24/07/2018 12:10, Burakov, Anatoly:
> On 11-Jun-18 9:55 PM, Anatoly Burakov wrote:
> > 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 <anatoly.burakov@intel.com>
> > ---
> >   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;
> > 
> 
> Hi Thomas,
> 
> We have discovered a few regressions in virtio/vhost use cases due to 
> this patch. Virtio expects to map all segments starting from 0 address, 
> and this patch breaks that assumption.
> 
> Can we revert this for 18.08? It will be reintroduced in 18.11 along 
> with fixes for virtio/vhost fixes to account for this change.

Yes, please send the patch with explanations.