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 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 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
 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
 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
 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 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
 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,
 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
 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
 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
 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
 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
 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  */
 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 }