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