mem: reduce memory fragmentation

index 019f84c18..9ae942bfe 100644
@@ -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;
 }
 

index 9ae942bfe..e37fe1e4d 100644
@@ -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

index e37fe1e4d..c5ee017dd 100644
@@ -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

index 22370398f..d5d72e37b 100644
@@ -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

index 3e61fffee..54abe938a 100644
@@ -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.

index d5d72e37b..a2e01148b 100644
@@ -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

50 lines not on this page · raw message

index a2e01148b..977174c4f 100644
@@ -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

index 980b4969f..5d8805515 100644
@@ -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.

index c5ee017dd..22370398f 100644
@@ -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

576 lines not on this page · raw message

index 8c11f98c9..d35fb52c4 100644
@@ -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;