@@ -117,9 +117,11 @@ find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
{
const struct used_mask *msk = get_used_mask(arr->data, arr->elt_sz,
arr->len);
- unsigned int msk_idx, lookahead_idx, first, first_mod;
+ unsigned int msk_idx, first, first_mod;
unsigned int last, last_mod;
- uint64_t last_msk, ignore_msk;
+ uint64_t last_msk, first_msk;
+ unsigned int run_start, left = 0;
+ bool run_started = false;
/*
* mask only has granularity of MASK_ALIGN, but start may not be aligned
@@ -128,7 +130,7 @@ find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
*/
first = MASK_LEN_TO_IDX(start);
first_mod = MASK_LEN_TO_MOD(start);
- ignore_msk = ~((1ULL << first_mod) - 1);
+ first_msk = ~((1ULL << first_mod) - 1);
/* array length may not be aligned, so calculate ignore mask for last
* mask index.
@@ -137,131 +139,120 @@ find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
last_mod = MASK_LEN_TO_MOD(arr->len);
last_msk = ~(UINT64_MAX << last_mod);
+ left = n;
+
for (msk_idx = first; msk_idx < msk->n_masks; msk_idx++) {
- uint64_t cur_msk, lookahead_msk;
- unsigned int run_start, clz, left;
- bool found = false;
+ unsigned int s_idx, clz, need;
+ uint64_t cur_msk, tmp_msk;
+
/*
- * The process of getting n consecutive bits for arbitrary n is
- * a bit involved, but here it is in a nutshell:
+ * In order to find N consecutive bits for arbitrary N, we need
+ * to be aware of the following:
*
- * 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
- * rshift-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 leading zeroes (that is, count
- * how many consecutive set bits we had starting from the
- * end 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 right at the start, so we will do
- * (n-k-1) rshift-ands and check if first bit is set.
+ * 1. To find N number of consecutive bits within a mask, we
+ * need to do N-1 rshift-ands and see if we still have set
+ * bits anywhere in the mask
+ * 2. N may be larger than mask size, in which case we need to
+ * do a search in multiple consecutive masks
+ * 3. For multi-mask search to be meaningful, we need to anchor
+ * our searches, i.e. first we find a run of M bits at the
+ * end of current mask, then we look for N-M bits at the
+ * beginning of next mask (or multiple masks)
*
- * 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.
+ * With all of the above, the algorihm looks as follows:
+ *
+ * 1. let N be the number of consecutive bits we're looking for
+ * 2. if we already started a run, check if we can continue it
+ * by looking for remainder of N at the beginning of current
+ * mask
+ * 3. if we lost a run or if we never had a run, we look for N
+ * bits anywhere within the current mask (up to mask size,
+ * we can finish this run in the next mask if N > mask size)
+ * 4. if we didn't find anything up to this point, check if any
+ * topmost bits of the mask are set (meaning we can start a
+ * run and finish it in the next mask)
+ * 5. at any point in steps 2-4, we may do an early exit due to
+ * finding what we were looking for, or continue searching
+ * further
*/
cur_msk = msk->data[msk_idx];
- left = n;
/* if we're looking for free spaces, invert the mask */
if (!used)
cur_msk = ~cur_msk;
- /* combine current ignore mask with last index ignore mask */
+ /* first and last mask may not be aligned */
+ if (msk_idx == first)
+ cur_msk &= first_msk;
if (msk_idx == last)
- ignore_msk &= last_msk;
+ cur_msk &= last_msk;
- /* if we have an ignore mask, ignore once */
- if (ignore_msk) {
- cur_msk &= ignore_msk;
- ignore_msk = 0;
- }
+ /* do we have an active previous run? */
+ if (run_started) {
+ /* figure out how many consecutive bits we need here */
+ need = RTE_MIN(left, MASK_ALIGN);
- /* 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++)
+ /* see if we get a run of needed length */
+ tmp_msk = cur_msk;
+ for (s_idx = 0; s_idx < need - 1; s_idx++)
tmp_msk &= tmp_msk >> 1ULL;
- /* we found what we were looking for */
- if (tmp_msk != 0) {
- run_start = rte_ctz64(tmp_msk);
- return MASK_GET_IDX(msk_idx, run_start);
+
+ /* if first bit is set, we keep the run */
+ if (tmp_msk & 1) {
+ left -= need;
+
+ /* did we find what we were looking for? */
+ if (left == 0)
+ return run_start;
+
+ /* keep looking */
+ continue;
}
+ /* we lost the run, reset */
+ run_started = false;
+ left = n;
}
- /*
- * we didn't find our run within the mask, or n > MASK_ALIGN,
- * so we're going for plan B.
- */
+ /* if we're here, we either lost the run or never had it */
+
+ /* figure out how many consecutive bits we need here */
+ need = RTE_MIN(left, MASK_ALIGN);
+
+ /* do a search */
+ tmp_msk = cur_msk;
+ for (s_idx = 0; s_idx < need - 1; s_idx++)
+ tmp_msk &= tmp_msk >> 1ULL;
+
+ /* have we found something? */
+ if (tmp_msk != 0) {
+ /* figure out where the run started */
+ run_start = MASK_GET_IDX(msk_idx, rte_ctz64(tmp_msk));
+ run_started = true;
+ left -= need;
+
+ /* do we need to look further? */
+ if (left == 0)
+ return run_start;
+
+ /* we need to keep looking */
+ continue;
+ }
+
+ /* we didn't find our run within current mask, go for plan B. */
/* count leading zeroes on inverted mask */
- if (~cur_msk == 0)
- clz = sizeof(cur_msk) * 8;
- else
- clz = rte_clz64(~cur_msk);
+ clz = rte_clz64(~cur_msk);
- /* if there aren't any runs at the end either, just continue */
+ /* if there aren't any set bits at the end, just continue */
if (clz == 0)
continue;
- /* we have a partial run at the end, so try looking ahead */
- run_start = MASK_ALIGN - clz;
+ /* we have a partial run at the end */
+ run_start = MASK_GET_IDX(msk_idx, MASK_ALIGN - clz);
+ run_started = true;
left -= clz;
- for (lookahead_idx = msk_idx + 1; lookahead_idx < msk->n_masks;
- lookahead_idx++) {
- unsigned int s_idx, need;
- uint64_t first_bit = 1;
-
- lookahead_msk = msk->data[lookahead_idx];
-
- /* if we're looking for free space, invert the mask */
- if (!used)
- lookahead_msk = ~lookahead_msk;
-
- /* figure out how many consecutive bits we need here */
- need = RTE_MIN(left, MASK_ALIGN);
-
- /* count number of shifts we performed */
- for (s_idx = 0; s_idx < need - 1; s_idx++) {
- lookahead_msk &= lookahead_msk >> 1ULL;
- /* did we lose the run yet? */
- if ((lookahead_msk & first_bit) == 0)
- break;
- }
-
- /* if first bit is not set, we've lost the run */
- if ((lookahead_msk & first_bit) == 0) {
- /*
- * we've scanned this far, so we know there are
- * no runs in the space we've lookahead-scanned
- * as well, so skip that on next iteration.
- */
- ignore_msk = ~((1ULL << (s_idx + 1)) - 1);
- /* outer loop will increment msk_idx so add 1 */
- msk_idx = lookahead_idx - 1;
- break;
- }
-
- left -= need;
-
- /* check if we've found what we were looking for */
- if (left == 0) {
- found = true;
- break;
- }
- }
-
- /* we didn't find anything, so continue */
- if (!found)
- continue;
-
- return MASK_GET_IDX(msk_idx, run_start);
+ /* we'll figure this out in the next iteration */
}
/* we didn't find anything */
rte_errno = used ? ENOENT : ENOSPC;