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 177