Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
tjh.dev
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.
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
26struct dbitmap {
27 unsigned int nbits;
28 unsigned long *map;
29};
30
31static inline int dbitmap_enabled(struct dbitmap *dmap)
32{
33 return !!dmap->nbits;
34}
35
36static 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. */
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 /* 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 */
69static inline void
70dbitmap_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
78static inline void
79dbitmap_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. */
98static inline unsigned int dbitmap_grow_nbits(struct dbitmap *dmap)
99{
100 return dmap->nbits << 1;
101}
102
103static inline void
104dbitmap_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 */
135static inline int
136dbitmap_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
151static inline void
152dbitmap_clear_bit(struct dbitmap *dmap, unsigned long bit)
153{
154 clear_bit(bit, dmap->map);
155}
156
157static 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