drivers/net/bnxt/tf_core/bitalloc.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2019-2020 Broadcom
   3  * All rights reserved.
   4  */
   5
   6 #ifndef _BITALLOC_H_
   7 #define _BITALLOC_H_
   8
   9 #include <stdint.h>
  10
  11 /* Bitalloc works on uint32_t as its word size */
  12 typedef uint32_t bitalloc_word_t;
  13
  14 struct bitalloc {
  15         bitalloc_word_t size;
  16         bitalloc_word_t free_count;
  17         bitalloc_word_t storage[1];
  18 };
  19
  20 #define BA_L0(s) (((s) + 31) / 32)
  21 #define BA_L1(s) ((BA_L0(s) + 31) / 32)
  22 #define BA_L2(s) ((BA_L1(s) + 31) / 32)
  23 #define BA_L3(s) ((BA_L2(s) + 31) / 32)
  24 #define BA_L4(s) ((BA_L3(s) + 31) / 32)
  25
  26 #define BITALLOC_SIZEOF(size)                                    \
  27         (sizeof(struct bitalloc) *                               \
  28          (((sizeof(struct bitalloc) +                            \
  29             sizeof(struct bitalloc) - 1 +                        \
  30             (sizeof(bitalloc_word_t) *                           \
  31              ((BA_L0(size) - 1) +                                \
  32               ((BA_L0(size) == 1) ? 0 : (BA_L1(size) + 1)) +     \
  33               ((BA_L1(size) == 1) ? 0 : (BA_L2(size) + 1)) +     \
  34               ((BA_L2(size) == 1) ? 0 : (BA_L3(size) + 1)) +     \
  35               ((BA_L3(size) == 1) ? 0 : (BA_L4(size) + 1)))))) / \
  36           sizeof(struct bitalloc)))
  37
  38 #define BITALLOC_MAX_SIZE (32 * 32 * 32 * 32 * 32 * 32)
  39
  40 /* The instantiation of a bitalloc looks a bit odd. Since a
  41  * bit allocator has variable storage, we need a way to get a
  42  * a pointer to a bitalloc structure that points to the correct
  43  * amount of storage. We do this by creating an array of
  44  * bitalloc where the first element in the array is the
  45  * actual bitalloc base structure, and the remaining elements
  46  * in the array provide the storage for it. This approach allows
  47  * instances to be individual variables or members of larger
  48  * structures.
  49  */
  50 #define BITALLOC_INST(name, size)                      \
  51         struct bitalloc name[(BITALLOC_SIZEOF(size) /  \
  52                               sizeof(struct bitalloc))]
  53
  54 /* Symbolic return codes */
  55 #define BA_SUCCESS           0
  56 #define BA_FAIL             -1
  57 #define BA_ENTRY_FREE        0
  58 #define BA_ENTRY_IN_USE      1
  59 #define BA_NO_ENTRY_FOUND   -1
  60
  61 /**
  62  * Initializates the bitallocator
  63  *
  64  * Returns 0 on success, -1 on failure.  Size is arbitrary up to
  65  * BITALLOC_MAX_SIZE
  66  */
  67 int ba_init(struct bitalloc *pool, int size);
  68
  69 /**
  70  * Returns -1 on failure, or index of allocated entry
  71  */
  72 int ba_alloc(struct bitalloc *pool);
  73 int ba_alloc_index(struct bitalloc *pool, int index);
  74
  75 /**
  76  * Returns -1 on failure, or index of allocated entry
  77  */
  78 int ba_alloc_reverse(struct bitalloc *pool);
  79
  80 /**
  81  * Query a particular index in a pool to check if its in use.
  82  *
  83  * Returns -1 on invalid index, 1 if the index is allocated, 0 if it
  84  * is free
  85  */
  86 int ba_inuse(struct bitalloc *pool, int index);
  87
  88 /**
  89  * Variant of ba_inuse that frees the index if it is allocated, same
  90  * return codes as ba_inuse
  91  */
  92 int ba_inuse_free(struct bitalloc *pool, int index);
  93
  94 /**
  95  * Find next index that is in use, start checking at index 'idx'
  96  *
  97  * Returns next index that is in use on success, or
  98  * -1 if no in use index is found
  99  */
 100 int ba_find_next_inuse(struct bitalloc *pool, int idx);
 101
 102 /**
 103  * Variant of ba_find_next_inuse that also frees the next in use index,
 104  * same return codes as ba_find_next_inuse
 105  */
 106 int ba_find_next_inuse_free(struct bitalloc *pool, int idx);
 107
 108 /**
 109  * Multiple freeing of the same index has no negative side effects,
 110  * but will return -1.  returns -1 on failure, 0 on success.
 111  */
 112 int ba_free(struct bitalloc *pool, int index);
 113
 114 /**
 115  * Returns the pool's free count
 116  */
 117 int ba_free_count(struct bitalloc *pool);
 118
 119 /**
 120  * Returns the pool's in use count
 121  */
 122 int ba_inuse_count(struct bitalloc *pool);
 123
 124 #endif /* _BITALLOC_H_ */