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 };
  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                 sfree(axmap->levels[i].map);
  83
  84         sfree(axmap->levels);
  85         sfree(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 = smalloc(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 = smalloc(axmap->nr_levels * sizeof(struct axmap_level));
 106
 107         for (i = 0; i < axmap->nr_levels; i++) {
 108                 struct axmap_level *al = &axmap->levels[i];
 109
 110                 al->level = i;
 111                 al->map_size = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
 112                 al->map = smalloc(al->map_size * sizeof(unsigned long));
 113                 if (!al->map)
 114                         goto err;
 115
 116                 nr_bits = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
 117         }
 118
 119         axmap_reset(axmap);
 120         return axmap;
 121 err:
 122         for (i = 0; i < axmap->nr_levels; i++)
 123                 if (axmap->levels[i].map)
 124                         sfree(axmap->levels[i].map);
 125
 126         sfree(axmap->levels);
 127         return NULL;
 128 }
 129
 130 static int axmap_handler(struct axmap *axmap, uint64_t bit_nr,
 131                           int (*func)(struct axmap_level *, unsigned long, unsigned int,
 132                           void *), void *data)
 133 {
 134         struct axmap_level *al;
 135         int i;
 136
 137         for (i = 0; i < axmap->nr_levels; i++) {
 138                 unsigned long index = ulog64(bit_nr, i);
 139                 unsigned long offset = index >> UNIT_SHIFT;
 140                 unsigned int bit = index & BLOCKS_PER_UNIT_MASK;
 141
 142                 al = &axmap->levels[i];
 143
 144                 if (func(al, offset, bit, data))
 145                         return 1;
 146         }
 147
 148         return 0;
 149 }
 150
 151 static int axmap_handler_topdown(struct axmap *axmap, uint64_t bit_nr,
 152         int (*func)(struct axmap_level *, unsigned long, unsigned int, void *),
 153         void *data)
 154 {
 155         struct axmap_level *al;
 156         int i, level = axmap->nr_levels;
 157
 158         for (i = axmap->nr_levels - 1; i >= 0; i--) {
 159                 unsigned long index = ulog64(bit_nr, --level);
 160                 unsigned long offset = index >> UNIT_SHIFT;
 161                 unsigned int bit = index & BLOCKS_PER_UNIT_MASK;
 162
 163                 al = &axmap->levels[i];
 164
 165                 if (func(al, offset, bit, data))
 166                         return 1;
 167         }
 168
 169         return 0;
 170 }
 171
 172 static int axmap_clear_fn(struct axmap_level *al, unsigned long offset,
 173                            unsigned int bit, void *unused)
 174 {
 175         if (!(al->map[offset] & (1UL << bit)))
 176                 return 1;
 177
 178         al->map[offset] &= ~(1UL << bit);
 179         return 0;
 180 }
 181
 182 void axmap_clear(struct axmap *axmap, uint64_t bit_nr)
 183 {
 184         axmap_handler(axmap, bit_nr, axmap_clear_fn, NULL);
 185 }
 186
 187 struct axmap_set_data {
 188         unsigned int nr_bits;
 189         unsigned int set_bits;
 190         unsigned int fail_ok;
 191 };
 192
 193 static unsigned long bit_masks[] = {
 194         0x0000000000000000, 0x0000000000000001, 0x0000000000000003, 0x0000000000000007,
 195         0x000000000000000f, 0x000000000000001f, 0x000000000000003f, 0x000000000000007f,
 196         0x00000000000000ff, 0x00000000000001ff, 0x00000000000003ff, 0x00000000000007ff,
 197         0x0000000000000fff, 0x0000000000001fff, 0x0000000000003fff, 0x0000000000007fff,
 198         0x000000000000ffff, 0x000000000001ffff, 0x000000000003ffff, 0x000000000007ffff,
 199         0x00000000000fffff, 0x00000000001fffff, 0x00000000003fffff, 0x00000000007fffff,
 200         0x0000000000ffffff, 0x0000000001ffffff, 0x0000000003ffffff, 0x0000000007ffffff,
 201         0x000000000fffffff, 0x000000001fffffff, 0x000000003fffffff, 0x000000007fffffff,
 202         0x00000000ffffffff,
 203 #if BITS_PER_LONG == 64
 204         0x00000001ffffffff, 0x00000003ffffffff, 0x00000007ffffffff, 0x0000000fffffffff,
 205         0x0000001fffffffff, 0x0000003fffffffff, 0x0000007fffffffff, 0x000000ffffffffff,
 206         0x000001ffffffffff, 0x000003ffffffffff, 0x000007ffffffffff, 0x00000fffffffffff,
 207         0x00001fffffffffff, 0x00003fffffffffff, 0x00007fffffffffff, 0x0000ffffffffffff,
 208         0x0001ffffffffffff, 0x0003ffffffffffff, 0x0007ffffffffffff, 0x000fffffffffffff,
 209         0x001fffffffffffff, 0x003fffffffffffff, 0x007fffffffffffff, 0x00ffffffffffffff,
 210         0x01ffffffffffffff, 0x03ffffffffffffff, 0x07ffffffffffffff, 0x0fffffffffffffff,
 211         0x1fffffffffffffff, 0x3fffffffffffffff, 0x7fffffffffffffff, 0xffffffffffffffff
 212 #endif
 213 };
 214
 215 static int axmap_set_fn(struct axmap_level *al, unsigned long offset,
 216                          unsigned int bit, void *__data)
 217 {
 218         struct axmap_set_data *data = __data;
 219         unsigned long mask, overlap;
 220         unsigned int nr_bits;
 221
 222         nr_bits = min(data->nr_bits, BLOCKS_PER_UNIT - bit);
 223
 224         mask = bit_masks[nr_bits] << bit;
 225
 226         /*
 227          * Mask off any potential overlap, only sets contig regions
 228          */
 229         overlap = al->map[offset] & mask;
 230         if (overlap == mask) {
 231                 assert(data->fail_ok);
 232                 return 1;
 233         }
 234
 235         while (overlap) {
 236                 unsigned long clear_mask = ~(1UL << ffz(~overlap));
 237
 238                 mask &= clear_mask;
 239                 overlap &= clear_mask;
 240                 nr_bits--;
 241         }
 242
 243         assert(mask);
 244         assert(!(al->map[offset] & mask));
 245
 246         al->map[offset] |= mask;
 247
 248         if (!al->level)
 249                 data->set_bits = nr_bits;
 250
 251         data->nr_bits = 1;
 252         return al->map[offset] != -1UL;
 253 }
 254
 255 static void __axmap_set(struct axmap *axmap, uint64_t bit_nr,
 256                          struct axmap_set_data *data)
 257 {
 258         unsigned int set_bits, nr_bits = data->nr_bits;
 259
 260         if (axmap->first_free >= bit_nr &&
 261             axmap->first_free < bit_nr + data->nr_bits)
 262                 axmap->first_free = -1ULL;
 263
 264         set_bits = 0;
 265         while (nr_bits) {
 266                 axmap_handler(axmap, bit_nr, axmap_set_fn, data);
 267                 set_bits += data->set_bits;
 268
 269                 if (data->set_bits != (BLOCKS_PER_UNIT - nr_bits))
 270                         break;
 271
 272                 nr_bits -= data->set_bits;
 273                 bit_nr += data->set_bits;
 274
 275                 data->nr_bits = nr_bits;
 276                 data->fail_ok = 1;
 277         }
 278
 279         data->set_bits = set_bits;
 280 }
 281
 282 void axmap_set(struct axmap *axmap, uint64_t bit_nr)
 283 {
 284         struct axmap_set_data data = { .nr_bits = 1, };
 285
 286         __axmap_set(axmap, bit_nr, &data);
 287 }
 288
 289 unsigned int axmap_set_nr(struct axmap *axmap, uint64_t bit_nr, unsigned int nr_bits)
 290 {
 291         struct axmap_set_data data = { .nr_bits = nr_bits, };
 292
 293         __axmap_set(axmap, bit_nr, &data);
 294         return data.set_bits;
 295 }
 296
 297 static int axmap_isset_fn(struct axmap_level *al, unsigned long offset,
 298                             unsigned int bit, void *unused)
 299 {
 300         return (al->map[offset] & (1UL << bit)) != 0;
 301 }
 302
 303 int axmap_isset(struct axmap *axmap, uint64_t bit_nr)
 304 {
 305         return axmap_handler_topdown(axmap, bit_nr, axmap_isset_fn, NULL);
 306 }
 307
 308 static uint64_t axmap_find_first_free(struct axmap *axmap, unsigned int level,
 309                                        uint64_t index)
 310 {
 311         unsigned long j;
 312         int i;
 313
 314         /*
 315          * Start at the bottom, then converge towards first free bit at the top
 316          */
 317         for (i = level; i >= 0; i--) {
 318                 struct axmap_level *al = &axmap->levels[i];
 319
 320                 if (index >= al->map_size) {
 321                         index = -1ULL;
 322                         break;
 323                 }
 324
 325                 for (j = index; j < al->map_size; j++) {
 326                         if (al->map[j] == -1UL)
 327                                 continue;
 328
 329                         /*
 330                          * First free bit here is our index into the first
 331                          * free bit at the next higher level
 332                          */
 333                         index = (j << UNIT_SHIFT) + ffz(al->map[j]);
 334                         break;
 335                 }
 336         }
 337
 338         return index;
 339 }
 340
 341 uint64_t axmap_first_free(struct axmap *axmap)
 342 {
 343         if (firstfree_valid(axmap))
 344                 return axmap->first_free;
 345
 346         axmap->first_free = axmap_find_first_free(axmap, axmap->nr_levels - 1, 0);
 347         return axmap->first_free;
 348 }
 349
 350 struct axmap_next_free_data {
 351         unsigned int level;
 352         unsigned long offset;
 353         uint64_t bit;
 354 };
 355
 356 static int axmap_next_free_fn(struct axmap_level *al, unsigned long offset,
 357                                unsigned int bit, void *__data)
 358 {
 359         struct axmap_next_free_data *data = __data;
 360         uint64_t mask = ~((1UL << ((data->bit & BLOCKS_PER_UNIT_MASK) + 1)) - 1);
 361
 362         if (!(mask & al->map[offset]))
 363                 return 0;
 364
 365         if (al->map[offset] != -1UL) {
 366                 data->level = al->level;
 367                 data->offset = offset;
 368                 return 1;
 369         }
 370
 371         data->bit = (data->bit + BLOCKS_PER_UNIT - 1) / BLOCKS_PER_UNIT;
 372         return 0;
 373 }
 374
 375 /*
 376  * 'bit_nr' is already set. Find the next free bit after this one.
 377  */
 378 uint64_t axmap_next_free(struct axmap *axmap, uint64_t bit_nr)
 379 {
 380         struct axmap_next_free_data data = { .level = -1U, .bit = bit_nr, };
 381
 382         if (firstfree_valid(axmap) && bit_nr < axmap->first_free)
 383                 return axmap->first_free;
 384
 385         if (!axmap_handler(axmap, bit_nr, axmap_next_free_fn, &data))
 386                 return axmap_first_free(axmap);
 387
 388         assert(data.level != -1U);
 389
 390         return axmap_find_first_free(axmap, data.level, data.offset);
 391 }