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