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 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 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 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 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 132 static int axmap_handler(struct axmap *axmap, uint64_t bit_nr, 133 int (*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 1; 148 } 149 150 return 0; 151 } 152 153 static int axmap_handler_topdown(struct axmap *axmap, uint64_t bit_nr, 154 int (*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 1; 169 } 170 171 return 0; 172 } 173 174 static int 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 1; 179 180 al->map[offset] &= ~(1UL << bit); 181 return 0; 182 } 183 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 216 static int 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 1; 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 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 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 293 unsigned int axmap_set_nr(struct axmap *axmap, uint64_t bit_nr, unsigned int nr_bits) 294 { 295 unsigned int set_bits = 0; 296 297 do { 298 struct axmap_set_data data = { .nr_bits = nr_bits, }; 299 unsigned int max_bits, this_set; 300 301 max_bits = BLOCKS_PER_UNIT - (bit_nr & BLOCKS_PER_UNIT_MASK); 302 if (max_bits < nr_bits) 303 data.nr_bits = max_bits; 304 305 this_set = data.nr_bits; 306 __axmap_set(axmap, bit_nr, &data); 307 set_bits += data.set_bits; 308 if (data.set_bits != this_set) 309 break; 310 311 nr_bits -= data.set_bits; 312 bit_nr += data.set_bits; 313 } while (nr_bits); 314 315 return set_bits; 316 } 317 318 static int axmap_isset_fn(struct axmap_level *al, unsigned long offset, 319 unsigned int bit, void *unused) 320 { 321 return (al->map[offset] & (1UL << bit)) != 0; 322 } 323 324 int axmap_isset(struct axmap *axmap, uint64_t bit_nr) 325 { 326 if (bit_nr <= axmap->nr_bits) 327 return axmap_handler_topdown(axmap, bit_nr, axmap_isset_fn, NULL); 328 329 return 0; 330 } 331 332 static uint64_t axmap_find_first_free(struct axmap *axmap, unsigned int level, 333 uint64_t index) 334 { 335 uint64_t ret = -1ULL; 336 unsigned long j; 337 int i; 338 339 /* 340 * Start at the bottom, then converge towards first free bit at the top 341 */ 342 for (i = level; i >= 0; i--) { 343 struct axmap_level *al = &axmap->levels[i]; 344 345 /* 346 * Clear 'ret', this is a bug condition. 347 */ 348 if (index >= al->map_size) { 349 ret = -1ULL; 350 break; 351 } 352 353 for (j = index; j < al->map_size; j++) { 354 if (al->map[j] == -1UL) 355 continue; 356 357 /* 358 * First free bit here is our index into the first 359 * free bit at the next higher level 360 */ 361 ret = index = (j << UNIT_SHIFT) + ffz(al->map[j]); 362 break; 363 } 364 } 365 366 if (ret < axmap->nr_bits) 367 return ret; 368 369 return (uint64_t) -1ULL; 370 } 371 372 static uint64_t axmap_first_free(struct axmap *axmap) 373 { 374 if (firstfree_valid(axmap)) 375 return axmap->first_free; 376 377 axmap->first_free = axmap_find_first_free(axmap, axmap->nr_levels - 1, 0); 378 return axmap->first_free; 379 } 380 381 struct axmap_next_free_data { 382 unsigned int level; 383 unsigned long offset; 384 uint64_t bit; 385 }; 386 387 static int axmap_next_free_fn(struct axmap_level *al, unsigned long offset, 388 unsigned int bit, void *__data) 389 { 390 struct axmap_next_free_data *data = __data; 391 uint64_t mask = ~bit_masks[(data->bit + 1) & BLOCKS_PER_UNIT_MASK]; 392 393 if (!(mask & ~al->map[offset])) 394 return 0; 395 396 if (al->map[offset] != -1UL) { 397 data->level = al->level; 398 data->offset = offset; 399 return 1; 400 } 401 402 data->bit = (data->bit + BLOCKS_PER_UNIT - 1) / BLOCKS_PER_UNIT; 403 return 0; 404 } 405 406 /* 407 * 'bit_nr' is already set. Find the next free bit after this one. 408 */ 409 uint64_t axmap_next_free(struct axmap *axmap, uint64_t bit_nr) 410 { 411 struct axmap_next_free_data data = { .level = -1U, .bit = bit_nr, }; 412 uint64_t ret; 413 414 if (firstfree_valid(axmap) && bit_nr < axmap->first_free) 415 return axmap->first_free; 416 417 if (!axmap_handler(axmap, bit_nr, axmap_next_free_fn, &data)) 418 return axmap_first_free(axmap); 419 420 assert(data.level != -1U); 421 422 /* 423 * In the rare case that the map is unaligned, we might end up 424 * finding an offset that's beyond the valid end. For that case, 425 * find the first free one, the map is practically full. 426 */ 427 ret = axmap_find_first_free(axmap, data.level, data.offset); 428 if (ret != -1ULL) 429 return ret; 430 431 return axmap_first_free(axmap); 432 } 433
