• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Bitmap of bitmaps, where each layer is number-of-bits-per-word smaller than
3  * the previous. Hence an 'axmap', since we axe each previous layer into a
4  * much smaller piece. I swear, that is why it's named like that. It has
5  * nothing to do with anything remotely narcissistic.
6  *
7  * A set bit at layer N indicates a full word at layer N-1, and so forth. As
8  * the bitmap becomes progressively more full, checking for existence
9  * becomes cheaper (since fewer layers are walked, making it a lot more
10  * cache friendly) and locating the next free space likewise.
11  *
12  * Axmaps get pretty close to optimal (1 bit per block) space usage, since
13  * layers quickly diminish in size. Doing the size math is straight forward,
14  * since we have log64(blocks) layers of maps. For 20000 blocks, overhead
15  * is roughly 1.9%, or 1.019 bits per block. The number quickly converges
16  * towards 1.0158, or 1.58% of overhead.
17  */
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include <string.h>
21 #include <assert.h>
22 
23 #include "../arch/arch.h"
24 #include "axmap.h"
25 #include "../minmax.h"
26 
27 #if BITS_PER_LONG == 64
28 #define UNIT_SHIFT		6
29 #elif BITS_PER_LONG == 32
30 #define UNIT_SHIFT		5
31 #else
32 #error "Number of arch bits unknown"
33 #endif
34 
35 #define BLOCKS_PER_UNIT		(1U << UNIT_SHIFT)
36 #define BLOCKS_PER_UNIT_MASK	(BLOCKS_PER_UNIT - 1)
37 
38 #define firstfree_valid(b)	((b)->first_free != (uint64_t) -1)
39 
40 struct axmap_level {
41 	int level;
42 	unsigned long map_size;
43 	unsigned long *map;
44 };
45 
46 struct axmap {
47 	unsigned int nr_levels;
48 	struct axmap_level *levels;
49 	uint64_t first_free;
50 	uint64_t nr_bits;
51 };
52 
ulog64(unsigned long val,unsigned int log)53 static unsigned long ulog64(unsigned long val, unsigned int log)
54 {
55 	while (log-- && val)
56 		val >>= UNIT_SHIFT;
57 
58 	return val;
59 }
60 
axmap_reset(struct axmap * axmap)61 void axmap_reset(struct axmap *axmap)
62 {
63 	int i;
64 
65 	for (i = 0; i < axmap->nr_levels; i++) {
66 		struct axmap_level *al = &axmap->levels[i];
67 
68 		memset(al->map, 0, al->map_size * sizeof(unsigned long));
69 	}
70 
71 	axmap->first_free = 0;
72 }
73 
axmap_free(struct axmap * axmap)74 void axmap_free(struct axmap *axmap)
75 {
76 	unsigned int i;
77 
78 	if (!axmap)
79 		return;
80 
81 	for (i = 0; i < axmap->nr_levels; i++)
82 		free(axmap->levels[i].map);
83 
84 	free(axmap->levels);
85 	free(axmap);
86 }
87 
axmap_new(unsigned long nr_bits)88 struct axmap *axmap_new(unsigned long nr_bits)
89 {
90 	struct axmap *axmap;
91 	unsigned int i, levels;
92 
93 	axmap = malloc(sizeof(*axmap));
94 	if (!axmap)
95 		return NULL;
96 
97 	levels = 1;
98 	i = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
99 	while (i > 1) {
100 		i = (i + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
101 		levels++;
102 	}
103 
104 	axmap->nr_levels = levels;
105 	axmap->levels = malloc(axmap->nr_levels * sizeof(struct axmap_level));
106 	axmap->nr_bits = nr_bits;
107 
108 	for (i = 0; i < axmap->nr_levels; i++) {
109 		struct axmap_level *al = &axmap->levels[i];
110 
111 		al->level = i;
112 		al->map_size = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
113 		al->map = malloc(al->map_size * sizeof(unsigned long));
114 		if (!al->map)
115 			goto err;
116 
117 		nr_bits = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
118 	}
119 
120 	axmap_reset(axmap);
121 	return axmap;
122 err:
123 	for (i = 0; i < axmap->nr_levels; i++)
124 		if (axmap->levels[i].map)
125 			free(axmap->levels[i].map);
126 
127 	free(axmap->levels);
128 	free(axmap);
129 	return NULL;
130 }
131 
axmap_handler(struct axmap * axmap,uint64_t bit_nr,bool (* func)(struct axmap_level *,unsigned long,unsigned int,void *),void * data)132 static bool axmap_handler(struct axmap *axmap, uint64_t bit_nr,
133 			  bool (*func)(struct axmap_level *, unsigned long, unsigned int,
134 			  void *), void *data)
135 {
136 	struct axmap_level *al;
137 	int i;
138 
139 	for (i = 0; i < axmap->nr_levels; i++) {
140 		unsigned long index = ulog64(bit_nr, i);
141 		unsigned long offset = index >> UNIT_SHIFT;
142 		unsigned int bit = index & BLOCKS_PER_UNIT_MASK;
143 
144 		al = &axmap->levels[i];
145 
146 		if (func(al, offset, bit, data))
147 			return true;
148 	}
149 
150 	return false;
151 }
152 
axmap_handler_topdown(struct axmap * axmap,uint64_t bit_nr,bool (* func)(struct axmap_level *,unsigned long,unsigned int,void *),void * data)153 static bool axmap_handler_topdown(struct axmap *axmap, uint64_t bit_nr,
154 	bool (*func)(struct axmap_level *, unsigned long, unsigned int, void *),
155 	void *data)
156 {
157 	struct axmap_level *al;
158 	int i, level = axmap->nr_levels;
159 
160 	for (i = axmap->nr_levels - 1; i >= 0; i--) {
161 		unsigned long index = ulog64(bit_nr, --level);
162 		unsigned long offset = index >> UNIT_SHIFT;
163 		unsigned int bit = index & BLOCKS_PER_UNIT_MASK;
164 
165 		al = &axmap->levels[i];
166 
167 		if (func(al, offset, bit, data))
168 			return true;
169 	}
170 
171 	return false;
172 }
173 
axmap_clear_fn(struct axmap_level * al,unsigned long offset,unsigned int bit,void * unused)174 static bool axmap_clear_fn(struct axmap_level *al, unsigned long offset,
175 			   unsigned int bit, void *unused)
176 {
177 	if (!(al->map[offset] & (1UL << bit)))
178 		return true;
179 
180 	al->map[offset] &= ~(1UL << bit);
181 	return false;
182 }
183 
axmap_clear(struct axmap * axmap,uint64_t bit_nr)184 void axmap_clear(struct axmap *axmap, uint64_t bit_nr)
185 {
186 	axmap_handler(axmap, bit_nr, axmap_clear_fn, NULL);
187 }
188 
189 struct axmap_set_data {
190 	unsigned int nr_bits;
191 	unsigned int set_bits;
192 };
193 
194 static unsigned long bit_masks[] = {
195 	0x0000000000000000, 0x0000000000000001, 0x0000000000000003, 0x0000000000000007,
196 	0x000000000000000f, 0x000000000000001f, 0x000000000000003f, 0x000000000000007f,
197 	0x00000000000000ff, 0x00000000000001ff, 0x00000000000003ff, 0x00000000000007ff,
198 	0x0000000000000fff, 0x0000000000001fff, 0x0000000000003fff, 0x0000000000007fff,
199 	0x000000000000ffff, 0x000000000001ffff, 0x000000000003ffff, 0x000000000007ffff,
200 	0x00000000000fffff, 0x00000000001fffff, 0x00000000003fffff, 0x00000000007fffff,
201 	0x0000000000ffffff, 0x0000000001ffffff, 0x0000000003ffffff, 0x0000000007ffffff,
202 	0x000000000fffffff, 0x000000001fffffff, 0x000000003fffffff, 0x000000007fffffff,
203 	0x00000000ffffffff,
204 #if BITS_PER_LONG == 64
205 	0x00000001ffffffff, 0x00000003ffffffff, 0x00000007ffffffff, 0x0000000fffffffff,
206 	0x0000001fffffffff, 0x0000003fffffffff, 0x0000007fffffffff, 0x000000ffffffffff,
207 	0x000001ffffffffff, 0x000003ffffffffff, 0x000007ffffffffff, 0x00000fffffffffff,
208 	0x00001fffffffffff, 0x00003fffffffffff, 0x00007fffffffffff, 0x0000ffffffffffff,
209 	0x0001ffffffffffff, 0x0003ffffffffffff, 0x0007ffffffffffff, 0x000fffffffffffff,
210 	0x001fffffffffffff, 0x003fffffffffffff, 0x007fffffffffffff, 0x00ffffffffffffff,
211 	0x01ffffffffffffff, 0x03ffffffffffffff, 0x07ffffffffffffff, 0x0fffffffffffffff,
212 	0x1fffffffffffffff, 0x3fffffffffffffff, 0x7fffffffffffffff, 0xffffffffffffffff
213 #endif
214 };
215 
axmap_set_fn(struct axmap_level * al,unsigned long offset,unsigned int bit,void * __data)216 static bool axmap_set_fn(struct axmap_level *al, unsigned long offset,
217 			 unsigned int bit, void *__data)
218 {
219 	struct axmap_set_data *data = __data;
220 	unsigned long mask, overlap;
221 	unsigned int nr_bits;
222 
223 	nr_bits = min(data->nr_bits, BLOCKS_PER_UNIT - bit);
224 
225 	mask = bit_masks[nr_bits] << bit;
226 
227 	/*
228 	 * Mask off any potential overlap, only sets contig regions
229 	 */
230 	overlap = al->map[offset] & mask;
231 	if (overlap == mask)
232 		return true;
233 
234 	while (overlap) {
235 		unsigned long clear_mask = ~(1UL << ffz(~overlap));
236 
237 		mask &= clear_mask;
238 		overlap &= clear_mask;
239 		nr_bits--;
240 	}
241 
242 	assert(mask);
243 	assert(!(al->map[offset] & mask));
244 
245 	al->map[offset] |= mask;
246 
247 	if (!al->level)
248 		data->set_bits = nr_bits;
249 
250 	data->nr_bits = 1;
251 	return al->map[offset] != -1UL;
252 }
253 
__axmap_set(struct axmap * axmap,uint64_t bit_nr,struct axmap_set_data * data)254 static void __axmap_set(struct axmap *axmap, uint64_t bit_nr,
255 			 struct axmap_set_data *data)
256 {
257 	unsigned int set_bits, nr_bits = data->nr_bits;
258 
259 	if (axmap->first_free >= bit_nr &&
260 	    axmap->first_free < bit_nr + data->nr_bits)
261 		axmap->first_free = -1ULL;
262 
263 	if (bit_nr > axmap->nr_bits)
264 		return;
265 	else if (bit_nr + nr_bits > axmap->nr_bits)
266 		nr_bits = axmap->nr_bits - bit_nr;
267 
268 	set_bits = 0;
269 	while (nr_bits) {
270 		axmap_handler(axmap, bit_nr, axmap_set_fn, data);
271 		set_bits += data->set_bits;
272 
273 		if (!data->set_bits ||
274 		    data->set_bits != (BLOCKS_PER_UNIT - nr_bits))
275 			break;
276 
277 		nr_bits -= data->set_bits;
278 		bit_nr += data->set_bits;
279 
280 		data->nr_bits = nr_bits;
281 	}
282 
283 	data->set_bits = set_bits;
284 }
285 
axmap_set(struct axmap * axmap,uint64_t bit_nr)286 void axmap_set(struct axmap *axmap, uint64_t bit_nr)
287 {
288 	struct axmap_set_data data = { .nr_bits = 1, };
289 
290 	__axmap_set(axmap, bit_nr, &data);
291 }
292 
axmap_set_nr(struct axmap * axmap,uint64_t bit_nr,unsigned int nr_bits)293 unsigned int axmap_set_nr(struct axmap *axmap, uint64_t bit_nr,
294 			  unsigned int nr_bits)
295 {
296 	unsigned int set_bits = 0;
297 
298 	do {
299 		struct axmap_set_data data = { .nr_bits = nr_bits, };
300 		unsigned int max_bits, this_set;
301 
302 		max_bits = BLOCKS_PER_UNIT - (bit_nr & BLOCKS_PER_UNIT_MASK);
303 		if (max_bits < nr_bits)
304 			data.nr_bits = max_bits;
305 
306 		this_set = data.nr_bits;
307 		__axmap_set(axmap, bit_nr, &data);
308 		set_bits += data.set_bits;
309 		if (data.set_bits != this_set)
310 			break;
311 
312 		nr_bits -= data.set_bits;
313 		bit_nr += data.set_bits;
314 	} while (nr_bits);
315 
316 	return set_bits;
317 }
318 
axmap_isset_fn(struct axmap_level * al,unsigned long offset,unsigned int bit,void * unused)319 static bool axmap_isset_fn(struct axmap_level *al, unsigned long offset,
320 			   unsigned int bit, void *unused)
321 {
322 	return (al->map[offset] & (1UL << bit)) != 0;
323 }
324 
axmap_isset(struct axmap * axmap,uint64_t bit_nr)325 bool axmap_isset(struct axmap *axmap, uint64_t bit_nr)
326 {
327 	if (bit_nr <= axmap->nr_bits)
328 		return axmap_handler_topdown(axmap, bit_nr, axmap_isset_fn, NULL);
329 
330 	return false;
331 }
332 
axmap_find_first_free(struct axmap * axmap,unsigned int level,uint64_t index)333 static uint64_t axmap_find_first_free(struct axmap *axmap, unsigned int level,
334 				       uint64_t index)
335 {
336 	uint64_t ret = -1ULL;
337 	unsigned long j;
338 	int i;
339 
340 	/*
341 	 * Start at the bottom, then converge towards first free bit at the top
342 	 */
343 	for (i = level; i >= 0; i--) {
344 		struct axmap_level *al = &axmap->levels[i];
345 
346 		/*
347 		 * Clear 'ret', this is a bug condition.
348 		 */
349 		if (index >= al->map_size) {
350 			ret = -1ULL;
351 			break;
352 		}
353 
354 		for (j = index; j < al->map_size; j++) {
355 			if (al->map[j] == -1UL)
356 				continue;
357 
358 			/*
359 			 * First free bit here is our index into the first
360 			 * free bit at the next higher level
361 			 */
362 			ret = index = (j << UNIT_SHIFT) + ffz(al->map[j]);
363 			break;
364 		}
365 	}
366 
367 	if (ret < axmap->nr_bits)
368 		return ret;
369 
370 	return (uint64_t) -1ULL;
371 }
372 
axmap_first_free(struct axmap * axmap)373 static uint64_t axmap_first_free(struct axmap *axmap)
374 {
375 	if (firstfree_valid(axmap))
376 		return axmap->first_free;
377 
378 	axmap->first_free = axmap_find_first_free(axmap, axmap->nr_levels - 1, 0);
379 	return axmap->first_free;
380 }
381 
382 struct axmap_next_free_data {
383 	unsigned int level;
384 	unsigned long offset;
385 	uint64_t bit;
386 };
387 
axmap_next_free_fn(struct axmap_level * al,unsigned long offset,unsigned int bit,void * __data)388 static bool axmap_next_free_fn(struct axmap_level *al, unsigned long offset,
389 			       unsigned int bit, void *__data)
390 {
391 	struct axmap_next_free_data *data = __data;
392 	uint64_t mask = ~bit_masks[(data->bit + 1) & BLOCKS_PER_UNIT_MASK];
393 
394 	if (!(mask & ~al->map[offset]))
395 		return false;
396 
397 	if (al->map[offset] != -1UL) {
398 		data->level = al->level;
399 		data->offset = offset;
400 		return true;
401 	}
402 
403 	data->bit = (data->bit + BLOCKS_PER_UNIT - 1) / BLOCKS_PER_UNIT;
404 	return false;
405 }
406 
407 /*
408  * 'bit_nr' is already set. Find the next free bit after this one.
409  */
axmap_next_free(struct axmap * axmap,uint64_t bit_nr)410 uint64_t axmap_next_free(struct axmap *axmap, uint64_t bit_nr)
411 {
412 	struct axmap_next_free_data data = { .level = -1U, .bit = bit_nr, };
413 	uint64_t ret;
414 
415 	if (firstfree_valid(axmap) && bit_nr < axmap->first_free)
416 		return axmap->first_free;
417 
418 	if (!axmap_handler(axmap, bit_nr, axmap_next_free_fn, &data))
419 		return axmap_first_free(axmap);
420 
421 	assert(data.level != -1U);
422 
423 	/*
424 	 * In the rare case that the map is unaligned, we might end up
425 	 * finding an offset that's beyond the valid end. For that case,
426 	 * find the first free one, the map is practically full.
427 	 */
428 	ret = axmap_find_first_free(axmap, data.level, data.offset);
429 	if (ret != -1ULL)
430 		return ret;
431 
432 	return axmap_first_free(axmap);
433 }
434