xref: /linux/drivers/android/dbitmap.h (revision 6093a688a07da07808f0122f9aa2a3eed250d853)
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