tjh.dev
Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
kernel
os
linux
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
27struct dbitmap {
28 unsigned int nbits;
29 unsigned long *map;
30};
31
32static inline int dbitmap_enabled(struct dbitmap *dmap)
33{
34 return !!dmap->nbits;
35}
36
37static 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. */
44static 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 */
73static inline void
74dbitmap_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
82static inline void
83dbitmap_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. */
102static inline unsigned int dbitmap_grow_nbits(struct dbitmap *dmap)
103{
104 return dmap->nbits << 1;
105}
106
107static inline void
108dbitmap_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 */
139static inline int
140dbitmap_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
154static inline void
155dbitmap_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
162static 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