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

171