From: Joey Zhong <[email protected]> Add ba_find_prev_inuse() and ba_find_prev_inuse_free(), the backward-searching counterparts of the existing ba_find_next_inuse() and ba_find_next_inuse_free(). The new helpers walk the multi-level bitalloc tree from a given index down towards index 0, using ba_fls() to locate the highest in-use bit at or below the starting position, mirroring the forward-search helpers which use ba_ffs() to locate the lowest in-use bit at or above the starting position.
Signed-off-by: Joey Zhong <[email protected]> Signed-off-by: Manish Kurup <[email protected]> --- .mailmap | 1 + drivers/net/bnxt/tf_core/bitalloc.c | 81 +++++++++++++++++++++++++++++ drivers/net/bnxt/tf_core/bitalloc.h | 14 +++++ 3 files changed, 96 insertions(+) diff --git a/.mailmap b/.mailmap index 2e348c3bce..9763a95d09 100644 --- a/.mailmap +++ b/.mailmap @@ -785,6 +785,7 @@ Job Abraham <[email protected]> Jochen Behrens <[email protected]> <[email protected]> Joel Kavanagh <[email protected]> Joey Xing <[email protected]> +Joey Zhong <[email protected]> Johan Faltstrom <[email protected]> Johan Källström <[email protected]> Johan Samuelsson <[email protected]> diff --git a/drivers/net/bnxt/tf_core/bitalloc.c b/drivers/net/bnxt/tf_core/bitalloc.c index 136263b6a4..dc0a2c8834 100644 --- a/drivers/net/bnxt/tf_core/bitalloc.c +++ b/drivers/net/bnxt/tf_core/bitalloc.c @@ -470,3 +470,84 @@ ba_find_next_inuse_free(struct bitalloc *pool, int index) return ba_find_next_helper(pool, 0, 1, 32, &index, 1); } + +static int +ba_find_prev_helper(struct bitalloc *pool, + int offset, + int words, + unsigned int size, + int *index, + int free) +{ + bitalloc_word_t *storage = &pool->storage[offset]; + int loc, r, bottom = 0; + + if (pool->size > size) + r = ba_find_prev_helper(pool, + offset + words + 1, + storage[words], + size * 32, + index, + free); + else + bottom = 1; /* Bottom of tree */ + + loc = (*index % 32); + *index = *index / 32; + + if (bottom) { + int bit_index = *index * 32; + + loc = ba_fls(~storage[*index] & ((bitalloc_word_t)-1 >> (31 - loc))); + if (loc > 0) { + loc--; + r = (bit_index + loc); + } else { + /* Loop over array at bottom of tree */ + r = -1; + bit_index -= 32; + *index = *index - 1; + while (bit_index >= 0) { + loc = ba_fls(~storage[*index]); + + if (loc > 0) { + loc--; + r = (bit_index + loc); + break; + } + bit_index -= 32; + *index = *index - 1; + } + } + } + + if (r >= 0 && (free)) { + if (bottom) + pool->free_count++; + storage[*index] |= (1 << loc); + } + + return r; +} + +int +ba_find_prev_inuse(struct bitalloc *pool, int index) +{ + if (index < 0 || + index >= (int)pool->size || + pool->free_count == pool->size) + return -1; + + return ba_find_prev_helper(pool, 0, 1, 32, &index, 0); +} + +int +ba_find_prev_inuse_free(struct bitalloc *pool, int index) +{ + if (index < 0 || + index >= (int)pool->size || + pool->free_count == pool->size) + return -1; + + return ba_find_prev_helper(pool, 0, 1, 32, &index, 1); +} diff --git a/drivers/net/bnxt/tf_core/bitalloc.h b/drivers/net/bnxt/tf_core/bitalloc.h index bf15cbc87b..6c8e325675 100644 --- a/drivers/net/bnxt/tf_core/bitalloc.h +++ b/drivers/net/bnxt/tf_core/bitalloc.h @@ -106,6 +106,20 @@ int ba_find_next_inuse(struct bitalloc *pool, int idx); */ int ba_find_next_inuse_free(struct bitalloc *pool, int idx); +/** + * Find prev index that is in use, start checking at index 'idx' + * + * Returns prev index that is in use on success, or + * -1 if no in use index is found + */ +int ba_find_prev_inuse(struct bitalloc *pool, int idx); + +/** + * Variant of ba_find_prev_inuse that also frees the prev in use index, + * same return codes as ba_find_prev_inuse + */ +int ba_find_prev_inuse_free(struct bitalloc *pool, int idx); + /** * Multiple freeing of the same index has no negative side effects, * but will return -1. returns -1 on failure, 0 on success. -- 2.31.1
