lib/axmap.c

   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 existance
   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 "../smalloc.h"
  26 #include "../minmax.h"
  27
  28 #if BITS_PER_LONG == 64
  29 #define UNIT_SHIFT              6
  30 #elif BITS_PER_LONG == 32
  31 #define UNIT_SHIFT              5
  32 #else
  33 #error "Number of arch bits unknown"
  34 #endif
  35
  36 #define BLOCKS_PER_UNIT         (1UL << UNIT_SHIFT)
  37 #define BLOCKS_PER_UNIT_MASK    (BLOCKS_PER_UNIT - 1)
  38
  39 #define firstfree_valid(b)      ((b)->first_free != (uint64_t) -1)
  40
  41 struct axmap_level {
  42         int level;
  43         unsigned long map_size;
  44         unsigned long *map;
  45 };
  46
  47 struct axmap {
  48         unsigned int nr_levels;
  49         struct axmap_level *levels;
  50         uint64_t first_free;
  51         uint64_t nr_bits;
  52 };
  53
  54 static unsigned long ulog64(unsigned long val, unsigned int log)
  55 {
  56         while (log-- && val)
  57                 val >>= UNIT_SHIFT;
  58
  59         return val;
  60 }
  61
  62 void axmap_reset(struct axmap *axmap)
  63 {
  64         int i;
  65
  66         for (i = 0; i < axmap->nr_levels; i++) {
  67                 struct axmap_level *al = &axmap->levels[i];
  68
  69                 memset(al->map, 0, al->map_size * sizeof(unsigned long));
  70         }
  71
  72         axmap->first_free = 0;
  73 }
  74
  75 void axmap_free(struct axmap *axmap)
  76 {
  77         unsigned int i;
  78
  79         if (!axmap)
  80                 return;
  81
  82         for (i = 0; i < axmap->nr_levels; i++)
  83                 sfree(axmap->levels[i].map);
  84
  85         sfree(axmap->levels);
  86         sfree(axmap);
  87 }
  88
  89 struct axmap *axmap_new(unsigned long nr_bits)
  90 {
  91         struct axmap *axmap;
  92         unsigned int i, levels;
  93
  94         axmap = smalloc(sizeof(*axmap));
  95         if (!axmap)
  96                 return NULL;
  97
  98         levels = 1;
  99         i = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
 100         while (i > 1) {
 101                 i = (i + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
 102                 levels++;
 103         }
 104
 105         axmap->nr_levels = levels;
 106         axmap->levels = smalloc(axmap->nr_levels * sizeof(struct axmap_level));
 107         axmap->nr_bits = nr_bits;
 108
 109         for (i = 0; i < axmap->nr_levels; i++) {
 110                 struct axmap_level *al = &axmap->levels[i];
 111
 112                 al->level = i;
 113                 al->map_size = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
 114                 al->map = smalloc(al->map_size * sizeof(unsigned long));
 115                 if (!al->map)
 116                         goto err;
 117
 118                 nr_bits = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
 119         }
 120
 121         axmap_reset(axmap);
 122         return axmap;
 123 err:
 124         for (i = 0; i < axmap->nr_levels; i++)
 125                 if (axmap->levels[i].map)
 126                         sfree(axmap->levels[i].map);
 127
 128         sfree(axmap->levels);
 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         unsigned int fail_ok;
 193 };
 194
 195 static unsigned long bit_masks[] = {
 196         0x0000000000000000, 0x0000000000000001, 0x0000000000000003, 0x0000000000000007,
 197         0x000000000000000f, 0x000000000000001f, 0x000000000000003f, 0x000000000000007f,
 198         0x00000000000000ff, 0x00000000000001ff, 0x00000000000003ff, 0x00000000000007ff,
 199         0x0000000000000fff, 0x0000000000001fff, 0x0000000000003fff, 0x0000000000007fff,
 200         0x000000000000ffff, 0x000000000001ffff, 0x000000000003ffff, 0x000000000007ffff,
 201         0x00000000000fffff, 0x00000000001fffff, 0x00000000003fffff, 0x00000000007fffff,
 202         0x0000000000ffffff, 0x0000000001ffffff, 0x0000000003ffffff, 0x0000000007ffffff,
 203         0x000000000fffffff, 0x000000001fffffff, 0x000000003fffffff, 0x000000007fffffff,
 204         0x00000000ffffffff,
 205 #if BITS_PER_LONG == 64
 206         0x00000001ffffffff, 0x00000003ffffffff, 0x00000007ffffffff, 0x0000000fffffffff,
 207         0x0000001fffffffff, 0x0000003fffffffff, 0x0000007fffffffff, 0x000000ffffffffff,
 208         0x000001ffffffffff, 0x000003ffffffffff, 0x000007ffffffffff, 0x00000fffffffffff,
 209         0x00001fffffffffff, 0x00003fffffffffff, 0x00007fffffffffff, 0x0000ffffffffffff,
 210         0x0001ffffffffffff, 0x0003ffffffffffff, 0x0007ffffffffffff, 0x000fffffffffffff,
 211         0x001fffffffffffff, 0x003fffffffffffff, 0x007fffffffffffff, 0x00ffffffffffffff,
 212         0x01ffffffffffffff, 0x03ffffffffffffff, 0x07ffffffffffffff, 0x0fffffffffffffff,
 213         0x1fffffffffffffff, 0x3fffffffffffffff, 0x7fffffffffffffff, 0xffffffffffffffff
 214 #endif
 215 };
 216
 217 static int axmap_set_fn(struct axmap_level *al, unsigned long offset,
 218                          unsigned int bit, void *__data)
 219 {
 220         struct axmap_set_data *data = __data;
 221         unsigned long mask, overlap;
 222         unsigned int nr_bits;
 223
 224         nr_bits = min(data->nr_bits, BLOCKS_PER_UNIT - bit);
 225
 226         mask = bit_masks[nr_bits] << bit;
 227
 228         /*
 229          * Mask off any potential overlap, only sets contig regions
 230          */
 231         overlap = al->map[offset] & mask;
 232         if (overlap == mask) {
 233                 assert(data->fail_ok);
 234                 return 1;
 235         }
 236
 237         while (overlap) {
 238                 unsigned long clear_mask = ~(1UL << ffz(~overlap));
 239
 240                 mask &= clear_mask;
 241                 overlap &= clear_mask;
 242                 nr_bits--;
 243         }
 244
 245         assert(mask);
 246         assert(!(al->map[offset] & mask));
 247
 248         al->map[offset] |= mask;
 249
 250         if (!al->level)
 251                 data->set_bits = nr_bits;
 252
 253         data->nr_bits = 1;
 254         return al->map[offset] != -1UL;
 255 }
 256
 257 static void __axmap_set(struct axmap *axmap, uint64_t bit_nr,
 258                          struct axmap_set_data *data)
 259 {
 260         unsigned int set_bits, nr_bits = data->nr_bits;
 261
 262         if (axmap->first_free >= bit_nr &&
 263             axmap->first_free < bit_nr + data->nr_bits)
 264                 axmap->first_free = -1ULL;
 265
 266         if (bit_nr > axmap->nr_bits)
 267                 return;
 268         else if (bit_nr + nr_bits > axmap->nr_bits)
 269                 nr_bits = axmap->nr_bits - bit_nr;
 270
 271         set_bits = 0;
 272         while (nr_bits) {
 273                 axmap_handler(axmap, bit_nr, axmap_set_fn, data);
 274                 set_bits += data->set_bits;
 275
 276                 if (data->set_bits != (BLOCKS_PER_UNIT - nr_bits))
 277                         break;
 278
 279                 nr_bits -= data->set_bits;
 280                 bit_nr += data->set_bits;
 281
 282                 data->nr_bits = nr_bits;
 283                 data->fail_ok = 1;
 284         }
 285
 286         data->set_bits = set_bits;
 287 }
 288
 289 void axmap_set(struct axmap *axmap, uint64_t bit_nr)
 290 {
 291         struct axmap_set_data data = { .nr_bits = 1, };
 292
 293         __axmap_set(axmap, bit_nr, &data);
 294 }
 295
 296 unsigned int axmap_set_nr(struct axmap *axmap, uint64_t bit_nr, unsigned int nr_bits)
 297 {
 298         struct axmap_set_data data = { .nr_bits = nr_bits, };
 299
 300         __axmap_set(axmap, bit_nr, &data);
 301         return data.set_bits;
 302 }
 303
 304 static int axmap_isset_fn(struct axmap_level *al, unsigned long offset,
 305                             unsigned int bit, void *unused)
 306 {
 307         return (al->map[offset] & (1UL << bit)) != 0;
 308 }
 309
 310 int axmap_isset(struct axmap *axmap, uint64_t bit_nr)
 311 {
 312         if (bit_nr <= axmap->nr_bits)
 313                 return axmap_handler_topdown(axmap, bit_nr, axmap_isset_fn, NULL);
 314
 315         return 0;
 316 }
 317
 318 static uint64_t axmap_find_first_free(struct axmap *axmap, unsigned int level,
 319                                        uint64_t index)
 320 {
 321         uint64_t ret = -1ULL;
 322         unsigned long j;
 323         int i;
 324
 325         /*
 326          * Start at the bottom, then converge towards first free bit at the top
 327          */
 328         for (i = level; i >= 0; i--) {
 329                 struct axmap_level *al = &axmap->levels[i];
 330
 331                 /*
 332                  * Clear 'ret', this is a bug condition.
 333                  */
 334                 if (index >= al->map_size) {
 335                         ret = -1ULL;
 336                         break;
 337                 }
 338
 339                 for (j = index; j < al->map_size; j++) {
 340                         if (al->map[j] == -1UL)
 341                                 continue;
 342
 343                         /*
 344                          * First free bit here is our index into the first
 345                          * free bit at the next higher level
 346                          */
 347                         ret = index = (j << UNIT_SHIFT) + ffz(al->map[j]);
 348                         break;
 349                 }
 350         }
 351
 352         if (ret < axmap->nr_bits)
 353                 return ret;
 354
 355         return (uint64_t) -1ULL;
 356 }
 357
 358 uint64_t axmap_first_free(struct axmap *axmap)
 359 {
 360         if (firstfree_valid(axmap))
 361                 return axmap->first_free;
 362
 363         axmap->first_free = axmap_find_first_free(axmap, axmap->nr_levels - 1, 0);
 364         return axmap->first_free;
 365 }
 366
 367 struct axmap_next_free_data {
 368         unsigned int level;
 369         unsigned long offset;
 370         uint64_t bit;
 371 };
 372
 373 static int axmap_next_free_fn(struct axmap_level *al, unsigned long offset,
 374                                unsigned int bit, void *__data)
 375 {
 376         struct axmap_next_free_data *data = __data;
 377         uint64_t mask = ~bit_masks[(data->bit + 1) & BLOCKS_PER_UNIT_MASK];
 378
 379         if (!(mask & ~al->map[offset]))
 380                 return 0;
 381
 382         if (al->map[offset] != -1UL) {
 383                 data->level = al->level;
 384                 data->offset = offset;
 385                 return 1;
 386         }
 387
 388         data->bit = (data->bit + BLOCKS_PER_UNIT - 1) / BLOCKS_PER_UNIT;
 389         return 0;
 390 }
 391
 392 /*
 393  * 'bit_nr' is already set. Find the next free bit after this one.
 394  */
 395 uint64_t axmap_next_free(struct axmap *axmap, uint64_t bit_nr)
 396 {
 397         struct axmap_next_free_data data = { .level = -1U, .bit = bit_nr, };
 398         uint64_t ret;
 399
 400         if (firstfree_valid(axmap) && bit_nr < axmap->first_free)
 401                 return axmap->first_free;
 402
 403         if (!axmap_handler(axmap, bit_nr, axmap_next_free_fn, &data))
 404                 return axmap_first_free(axmap);
 405
 406         assert(data.level != -1U);
 407
 408         /*
 409          * In the rare case that the map is unaligned, we might end up
 410          * finding an offset that's beyond the valid end. For that case,
 411          * find the first free one, the map is practically full.
 412          */
 413         ret = axmap_find_first_free(axmap, data.level, data.offset);
 414         if (ret != -1ULL)
 415                 return ret;
 416
 417         return axmap_first_free(axmap);
 418 }