drivers/net/bnxt/tf_core/bitalloc.h

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