[PATCH] net/bnxt: truflow enhance bitalloc utility

[Manish Kurup]

From: Joey Zhong <xiaozhen.zhong at broadcom.com>

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 <xiaozhen.zhong at broadcom.com>
Signed-off-by: Manish Kurup <manish.kurup at broadcom.com>
---
 .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 <job.abraham at intel.com>
 Jochen Behrens <jochen.behrens at broadcom.com> <jbehrens at vmware.com>
 Joel Kavanagh <joel.kavanagh at intel.com>
 Joey Xing <joey.xing at jaguarmicro.com>
+Joey Zhong <xiaozhen.zhong at broadcom.com>
 Johan Faltstrom <johan.faltstrom at netinsight.net>
 Johan Källström <johan.kallstrom at ericsson.com>
 Johan Samuelsson <johan.xb.samuelsson at ericsson.com>
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