| 1 |
|
| 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 |
|
| 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 |
|
| 61 | if (bit == dmap->nbits)
|
| 62 | return NBITS_MIN;
|
| 63 |
|
| 64 | return 0;
|
| 65 | }
|
| 66 |
|
| 67 |
|
| 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 |
|
| 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
|