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
dbitmap_enabled(struct dbitmap * dmap)31 static inline int dbitmap_enabled(struct dbitmap *dmap)
32 {
33 return !!dmap->nbits;
34 }
35
dbitmap_free(struct dbitmap * dmap)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. */
dbitmap_shrink_nbits(struct dbitmap * dmap)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
dbitmap_replace(struct dbitmap * dmap,unsigned long * new,unsigned int nbits)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
dbitmap_shrink(struct dbitmap * dmap,unsigned long * new,unsigned int nbits)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. */
dbitmap_grow_nbits(struct dbitmap * dmap)97 static inline unsigned int dbitmap_grow_nbits(struct dbitmap *dmap)
98 {
99 return dmap->nbits << 1;
100 }
101
102 static inline void
dbitmap_grow(struct dbitmap * dmap,unsigned long * new,unsigned int nbits)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
dbitmap_acquire_next_zero_bit(struct dbitmap * dmap,unsigned long offset,unsigned long * bit)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
dbitmap_clear_bit(struct dbitmap * dmap,unsigned long bit)151 dbitmap_clear_bit(struct dbitmap *dmap, unsigned long bit)
152 {
153 clear_bit(bit, dmap->map);
154 }
155
dbitmap_init(struct dbitmap * dmap)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
169