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 dmap->map = NULL; 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 /* find_last_bit() returns dmap->nbits when no bits are set. */ 62 if (bit == dmap->nbits) 63 return NBITS_MIN; 64 65 return 0; 66 } 67 68 /* Replace the internal bitmap with a new one of different size */ 69 static inline void 70 dbitmap_replace(struct dbitmap *dmap, unsigned long *new, unsigned int nbits) 71 { 72 bitmap_copy(new, dmap->map, min(dmap->nbits, nbits)); 73 kfree(dmap->map); 74 dmap->map = new; 75 dmap->nbits = nbits; 76 } 77 78 static inline void 79 dbitmap_shrink(struct dbitmap *dmap, unsigned long *new, unsigned int nbits) 80 { 81 if (!new) 82 return; 83 84 /* 85 * Verify that shrinking to @nbits is still possible. The @new 86 * bitmap might have been allocated without locks, so this call 87 * could now be outdated. In this case, free @new and move on. 88 */ 89 if (!dbitmap_enabled(dmap) || dbitmap_shrink_nbits(dmap) != nbits) { 90 kfree(new); 91 return; 92 } 93 94 dbitmap_replace(dmap, new, nbits); 95 } 96 97 /* Returns the nbits that a dbitmap can grow to. */ 98 static inline unsigned int dbitmap_grow_nbits(struct dbitmap *dmap) 99 { 100 return dmap->nbits << 1; 101 } 102 103 static inline void 104 dbitmap_grow(struct dbitmap *dmap, unsigned long *new, unsigned int nbits) 105 { 106 /* 107 * Verify that growing to @nbits is still possible. The @new 108 * bitmap might have been allocated without locks, so this call 109 * could now be outdated. In this case, free @new and move on. 110 */ 111 if (!dbitmap_enabled(dmap) || nbits <= dmap->nbits) { 112 kfree(new); 113 return; 114 } 115 116 /* 117 * Check for ENOMEM after confirming the grow operation is still 118 * required. This ensures we only disable the dbitmap when it's 119 * necessary. Once the dbitmap is disabled, binder will fallback 120 * to slow_desc_lookup_olocked(). 121 */ 122 if (!new) { 123 dbitmap_free(dmap); 124 return; 125 } 126 127 dbitmap_replace(dmap, new, nbits); 128 } 129 130 /* 131 * Finds and sets the next zero bit in the bitmap. Upon success @bit 132 * is populated with the index and 0 is returned. Otherwise, -ENOSPC 133 * is returned to indicate that a dbitmap_grow() is needed. 134 */ 135 static inline int 136 dbitmap_acquire_next_zero_bit(struct dbitmap *dmap, unsigned long offset, 137 unsigned long *bit) 138 { 139 unsigned long n; 140 141 n = find_next_zero_bit(dmap->map, dmap->nbits, offset); 142 if (n == dmap->nbits) 143 return -ENOSPC; 144 145 *bit = n; 146 set_bit(n, dmap->map); 147 148 return 0; 149 } 150 151 static inline void 152 dbitmap_clear_bit(struct dbitmap *dmap, unsigned long bit) 153 { 154 clear_bit(bit, dmap->map); 155 } 156 157 static inline int dbitmap_init(struct dbitmap *dmap) 158 { 159 dmap->map = bitmap_zalloc(NBITS_MIN, GFP_KERNEL); 160 if (!dmap->map) { 161 dmap->nbits = 0; 162 return -ENOMEM; 163 } 164 165 dmap->nbits = NBITS_MIN; 166 167 return 0; 168 } 169 #endif 170