drivers/android/dbitmap.h

   1 /* SPDX-License-Identifier: GPL-2.0-only */
   2 /*
   3  * Copyright 2024 Google LLC
   4  *
   5  * dbitmap - dynamically sized bitmap library.
   6  *
   7  * Used by the binder driver to optimize the allocation of the smallest
   8  * available descriptor ID. Each bit in the bitmap represents the state
   9  * of an ID.
  10  *
  11  * A dbitmap can grow or shrink as needed. This part has been designed
  12  * considering that users might need to briefly release their locks in
  13  * order to allocate memory for the new bitmap. These operations then,
  14  * are verified to determine if the grow or shrink is sill valid.
  15  *
  16  * This library does not provide protection against concurrent access
  17  * by itself. Binder uses the proc->outer_lock for this purpose.
  18  */
  19
  20 #ifndef _LINUX_DBITMAP_H
  21 #define _LINUX_DBITMAP_H
  22 #include <linux/bitmap.h>
  23
  24 #define NBITS_MIN       BITS_PER_TYPE(unsigned long)
  25
  26 struct dbitmap {
  27         unsigned int nbits;
  28         unsigned long *map;
  29 };
  30
  31 static inline int dbitmap_enabled(struct dbitmap *dmap)
  32 {
  33         return !!dmap->nbits;
  34 }
  35
  36 static inline void dbitmap_free(struct dbitmap *dmap)
  37 {
  38         dmap->nbits = 0;
  39         kfree(dmap->map);
  40 }
  41
  42 /* Returns the nbits that a dbitmap can shrink to, 0 if not possible. */
  43 static inline unsigned int dbitmap_shrink_nbits(struct dbitmap *dmap)
  44 {
  45         unsigned int bit;
  46
  47         if (dmap->nbits <= NBITS_MIN)
  48                 return 0;
  49
  50         /*
  51          * Determine if the bitmap can shrink based on the position of
  52          * its last set bit. If the bit is within the first quarter of
  53          * the bitmap then shrinking is possible. In this case, the
  54          * bitmap should shrink to half its current size.
  55          */
  56         bit = find_last_bit(dmap->map, dmap->nbits);
  57         if (bit < (dmap->nbits >> 2))
  58                 return dmap->nbits >> 1;
  59
  60         /* find_last_bit() returns dmap->nbits when no bits are set. */
  61         if (bit == dmap->nbits)
  62                 return NBITS_MIN;
  63
  64         return 0;
  65 }
  66
  67 /* Replace the internal bitmap with a new one of different size */
  68 static inline void
  69 dbitmap_replace(struct dbitmap *dmap, unsigned long *new, unsigned int nbits)
  70 {
  71         bitmap_copy(new, dmap->map, min(dmap->nbits, nbits));
  72         kfree(dmap->map);
  73         dmap->map = new;
  74         dmap->nbits = nbits;
  75 }
  76
  77 static inline void
  78 dbitmap_shrink(struct dbitmap *dmap, unsigned long *new, unsigned int nbits)
  79 {
  80         if (!new)
  81                 return;
  82
  83         /*
  84          * Verify that shrinking to @nbits is still possible. The @new
  85          * bitmap might have been allocated without locks, so this call
  86          * could now be outdated. In this case, free @new and move on.
  87          */
  88         if (!dbitmap_enabled(dmap) || dbitmap_shrink_nbits(dmap) != nbits) {
  89                 kfree(new);
  90                 return;
  91         }
  92
  93         dbitmap_replace(dmap, new, nbits);
  94 }
  95
  96 /* Returns the nbits that a dbitmap can grow to. */
  97 static inline unsigned int dbitmap_grow_nbits(struct dbitmap *dmap)
  98 {
  99         return dmap->nbits << 1;
 100 }
 101
 102 static inline void
 103 dbitmap_grow(struct dbitmap *dmap, unsigned long *new, unsigned int nbits)
 104 {
 105         /*
 106          * Verify that growing to @nbits is still possible. The @new
 107          * bitmap might have been allocated without locks, so this call
 108          * could now be outdated. In this case, free @new and move on.
 109          */
 110         if (!dbitmap_enabled(dmap) || nbits <= dmap->nbits) {
 111                 kfree(new);
 112                 return;
 113         }
 114
 115         /*
 116          * Check for ENOMEM after confirming the grow operation is still
 117          * required. This ensures we only disable the dbitmap when it's
 118          * necessary. Once the dbitmap is disabled, binder will fallback
 119          * to slow_desc_lookup_olocked().
 120          */
 121         if (!new) {
 122                 dbitmap_free(dmap);
 123                 return;
 124         }
 125
 126         dbitmap_replace(dmap, new, nbits);
 127 }
 128
 129 /*
 130  * Finds and sets the next zero bit in the bitmap. Upon success @bit
 131  * is populated with the index and 0 is returned. Otherwise, -ENOSPC
 132  * is returned to indicate that a dbitmap_grow() is needed.
 133  */
 134 static inline int
 135 dbitmap_acquire_next_zero_bit(struct dbitmap *dmap, unsigned long offset,
 136                               unsigned long *bit)
 137 {
 138         unsigned long n;
 139
 140         n = find_next_zero_bit(dmap->map, dmap->nbits, offset);
 141         if (n == dmap->nbits)
 142                 return -ENOSPC;
 143
 144         *bit = n;
 145         set_bit(n, dmap->map);
 146
 147         return 0;
 148 }
 149
 150 static inline void
 151 dbitmap_clear_bit(struct dbitmap *dmap, unsigned long bit)
 152 {
 153         clear_bit(bit, dmap->map);
 154 }
 155
 156 static inline int dbitmap_init(struct dbitmap *dmap)
 157 {
 158         dmap->map = bitmap_zalloc(NBITS_MIN, GFP_KERNEL);
 159         if (!dmap->map) {
 160                 dmap->nbits = 0;
 161                 return -ENOMEM;
 162         }
 163
 164         dmap->nbits = NBITS_MIN;
 165
 166         return 0;
 167 }
 168 #endif