libfrog/bitmap.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * Copyright (C) 2018 Oracle.  All Rights Reserved.
   4  * Author: Darrick J. Wong <darrick.wong@oracle.com>
   5  */
   6 #include "xfs.h"
   7 #include <stdint.h>
   8 #include <stdlib.h>
   9 #include <assert.h>
  10 #include <pthread.h>
  11 #include "platform_defs.h"
  12 #include "avl64.h"
  13 #include "list.h"
  14 #include "bitmap.h"
  15
  16 /*
  17  * Space Efficient Bitmap
  18  *
  19  * Implements a space-efficient bitmap.  We use an AVL tree to manage
  20  * extent records that tell us which ranges are set; the bitmap key is
  21  * an arbitrary uint64_t.  The usual bitmap operations (set, clear,
  22  * test, test and set) are supported, plus we can iterate set ranges.
  23  */
  24
  25 #define avl_for_each_range_safe(pos, n, l, first, last) \
  26         for (pos = (first), n = pos->avl_nextino, l = (last)->avl_nextino; pos != (l); \
  27                         pos = n, n = pos ? pos->avl_nextino : NULL)
  28
  29 #define avl_for_each_safe(tree, pos, n) \
  30         for (pos = (tree)->avl_firstino, n = pos ? pos->avl_nextino : NULL; \
  31                         pos != NULL; \
  32                         pos = n, n = pos ? pos->avl_nextino : NULL)
  33
  34 #define avl_for_each(tree, pos) \
  35         for (pos = (tree)->avl_firstino; pos != NULL; pos = pos->avl_nextino)
  36
  37 struct bitmap_node {
  38         struct avl64node        btn_node;
  39         uint64_t                btn_start;
  40         uint64_t                btn_length;
  41 };
  42
  43 static uint64_t
  44 extent_start(
  45         struct avl64node        *node)
  46 {
  47         struct bitmap_node      *btn;
  48
  49         btn = container_of(node, struct bitmap_node, btn_node);
  50         return btn->btn_start;
  51 }
  52
  53 static uint64_t
  54 extent_end(
  55         struct avl64node        *node)
  56 {
  57         struct bitmap_node      *btn;
  58
  59         btn = container_of(node, struct bitmap_node, btn_node);
  60         return btn->btn_start + btn->btn_length;
  61 }
  62
  63 static struct avl64ops bitmap_ops = {
  64         extent_start,
  65         extent_end,
  66 };
  67
  68 /* Initialize a bitmap. */
  69 int
  70 bitmap_init(
  71         struct bitmap           **bmapp)
  72 {
  73         struct bitmap           *bmap;
  74
  75         bmap = calloc(1, sizeof(struct bitmap));
  76         if (!bmap)
  77                 return -ENOMEM;
  78         bmap->bt_tree = malloc(sizeof(struct avl64tree_desc));
  79         if (!bmap->bt_tree) {
  80                 free(bmap);
  81                 return -ENOMEM;
  82         }
  83
  84         pthread_mutex_init(&bmap->bt_lock, NULL);
  85         avl64_init_tree(bmap->bt_tree, &bitmap_ops);
  86         *bmapp = bmap;
  87
  88         return 0;
  89 }
  90
  91 /* Free a bitmap. */
  92 void
  93 bitmap_free(
  94         struct bitmap           **bmapp)
  95 {
  96         struct bitmap           *bmap;
  97         struct avl64node        *node;
  98         struct avl64node        *n;
  99         struct bitmap_node      *ext;
 100
 101         bmap = *bmapp;
 102         avl_for_each_safe(bmap->bt_tree, node, n) {
 103                 ext = container_of(node, struct bitmap_node, btn_node);
 104                 free(ext);
 105         }
 106         free(bmap->bt_tree);
 107         free(bmap);
 108         *bmapp = NULL;
 109 }
 110
 111 /* Create a new bitmap extent node. */
 112 static struct bitmap_node *
 113 bitmap_node_init(
 114         uint64_t                start,
 115         uint64_t                len)
 116 {
 117         struct bitmap_node      *ext;
 118
 119         ext = malloc(sizeof(struct bitmap_node));
 120         if (!ext)
 121                 return NULL;
 122
 123         ext->btn_node.avl_nextino = NULL;
 124         ext->btn_start = start;
 125         ext->btn_length = len;
 126
 127         return ext;
 128 }
 129
 130 /* Create a new bitmap node and insert it. */
 131 static inline int
 132 __bitmap_insert(
 133         struct bitmap           *bmap,
 134         uint64_t                start,
 135         uint64_t                length)
 136 {
 137         struct bitmap_node      *ext;
 138         struct avl64node        *node;
 139
 140         ext = bitmap_node_init(start, length);
 141         if (!ext)
 142                 return -ENOMEM;
 143
 144         node = avl64_insert(bmap->bt_tree, &ext->btn_node);
 145         if (node == NULL) {
 146                 free(ext);
 147                 return -EEXIST;
 148         }
 149
 150         return 0;
 151 }
 152
 153 /* Set a region of bits (locked). */
 154 static int
 155 __bitmap_set(
 156         struct bitmap           *bmap,
 157         uint64_t                start,
 158         uint64_t                length)
 159 {
 160         struct avl64node        *firstn;
 161         struct avl64node        *lastn;
 162         struct avl64node        *pos;
 163         struct avl64node        *n;
 164         struct avl64node        *l;
 165         struct bitmap_node      *ext;
 166         uint64_t                new_start;
 167         uint64_t                new_length;
 168
 169         /* Find any existing nodes adjacent or within that range. */
 170         avl64_findranges(bmap->bt_tree, start - 1, start + length + 1,
 171                         &firstn, &lastn);
 172
 173         /* Nothing, just insert a new extent. */
 174         if (firstn == NULL && lastn == NULL)
 175                 return __bitmap_insert(bmap, start, length);
 176
 177         assert(firstn != NULL && lastn != NULL);
 178         new_start = start;
 179         new_length = length;
 180
 181         avl_for_each_range_safe(pos, n, l, firstn, lastn) {
 182                 ext = container_of(pos, struct bitmap_node, btn_node);
 183
 184                 /* Bail if the new extent is contained within an old one. */
 185                 if (ext->btn_start <= start &&
 186                     ext->btn_start + ext->btn_length >= start + length)
 187                         return 0;
 188
 189                 /* Check for overlapping and adjacent extents. */
 190                 if (ext->btn_start + ext->btn_length >= start ||
 191                     ext->btn_start <= start + length) {
 192                         if (ext->btn_start < start) {
 193                                 new_start = ext->btn_start;
 194                                 new_length += ext->btn_length;
 195                         }
 196
 197                         if (ext->btn_start + ext->btn_length >
 198                             new_start + new_length)
 199                                 new_length = ext->btn_start + ext->btn_length -
 200                                                 new_start;
 201
 202                         avl64_delete(bmap->bt_tree, pos);
 203                         free(ext);
 204                 }
 205         }
 206
 207         return __bitmap_insert(bmap, new_start, new_length);
 208 }
 209
 210 /* Set a region of bits. */
 211 int
 212 bitmap_set(
 213         struct bitmap           *bmap,
 214         uint64_t                start,
 215         uint64_t                length)
 216 {
 217         int                     res;
 218
 219         pthread_mutex_lock(&bmap->bt_lock);
 220         res = __bitmap_set(bmap, start, length);
 221         pthread_mutex_unlock(&bmap->bt_lock);
 222
 223         return res;
 224 }
 225
 226 #if 0   /* Unused, provided for completeness. */
 227 /* Clear a region of bits. */
 228 bool
 229 bitmap_clear(
 230         struct bitmap           *bmap,
 231         uint64_t                start,
 232         uint64_t                len)
 233 {
 234         struct avl64node        *firstn;
 235         struct avl64node        *lastn;
 236         struct avl64node        *pos;
 237         struct avl64node        *n;
 238         struct avl64node        *l;
 239         struct bitmap_node      *ext;
 240         uint64_t                new_start;
 241         uint64_t                new_length;
 242         struct avl64node        *node;
 243         int                     stat;
 244
 245         pthread_mutex_lock(&bmap->bt_lock);
 246         /* Find any existing nodes over that range. */
 247         avl64_findranges(bmap->bt_tree, start, start + len, &firstn, &lastn);
 248
 249         /* Nothing, we're done. */
 250         if (firstn == NULL && lastn == NULL) {
 251                 pthread_mutex_unlock(&bmap->bt_lock);
 252                 return true;
 253         }
 254
 255         assert(firstn != NULL && lastn != NULL);
 256
 257         /* Delete or truncate everything in sight. */
 258         avl_for_each_range_safe(pos, n, l, firstn, lastn) {
 259                 ext = container_of(pos, struct bitmap_node, btn_node);
 260
 261                 stat = 0;
 262                 if (ext->btn_start < start)
 263                         stat |= 1;
 264                 if (ext->btn_start + ext->btn_length > start + len)
 265                         stat |= 2;
 266                 switch (stat) {
 267                 case 0:
 268                         /* Extent totally within range; delete. */
 269                         avl64_delete(bmap->bt_tree, pos);
 270                         free(ext);
 271                         break;
 272                 case 1:
 273                         /* Extent is left-adjacent; truncate. */
 274                         ext->btn_length = start - ext->btn_start;
 275                         break;
 276                 case 2:
 277                         /* Extent is right-adjacent; move it. */
 278                         ext->btn_length = ext->btn_start + ext->btn_length -
 279                                         (start + len);
 280                         ext->btn_start = start + len;
 281                         break;
 282                 case 3:
 283                         /* Extent overlaps both ends. */
 284                         ext->btn_length = start - ext->btn_start;
 285                         new_start = start + len;
 286                         new_length = ext->btn_start + ext->btn_length -
 287                                         new_start;
 288
 289                         ext = bitmap_node_init(new_start, new_length);
 290                         if (!ext)
 291                                 return false;
 292
 293                         node = avl64_insert(bmap->bt_tree, &ext->btn_node);
 294                         if (node == NULL) {
 295                                 errno = EEXIST;
 296                                 return false;
 297                         }
 298                         break;
 299                 }
 300         }
 301
 302         pthread_mutex_unlock(&bmap->bt_lock);
 303         return true;
 304 }
 305 #endif
 306
 307 #ifdef DEBUG
 308 /* Iterate the set regions of this bitmap. */
 309 int
 310 bitmap_iterate(
 311         struct bitmap           *bmap,
 312         int                     (*fn)(uint64_t, uint64_t, void *),
 313         void                    *arg)
 314 {
 315         struct avl64node        *node;
 316         struct bitmap_node      *ext;
 317         int                     error = 0;
 318
 319         pthread_mutex_lock(&bmap->bt_lock);
 320         avl_for_each(bmap->bt_tree, node) {
 321                 ext = container_of(node, struct bitmap_node, btn_node);
 322                 error = fn(ext->btn_start, ext->btn_length, arg);
 323                 if (error)
 324                         break;
 325         }
 326         pthread_mutex_unlock(&bmap->bt_lock);
 327
 328         return error;
 329 }
 330 #endif
 331
 332 /* Do any bitmap extents overlap the given one?  (locked) */
 333 static bool
 334 __bitmap_test(
 335         struct bitmap           *bmap,
 336         uint64_t                start,
 337         uint64_t                len)
 338 {
 339         struct avl64node        *firstn;
 340         struct avl64node        *lastn;
 341
 342         /* Find any existing nodes over that range. */
 343         avl64_findranges(bmap->bt_tree, start, start + len, &firstn, &lastn);
 344
 345         return firstn != NULL && lastn != NULL;
 346 }
 347
 348 /* Is any part of this range set? */
 349 bool
 350 bitmap_test(
 351         struct bitmap           *bmap,
 352         uint64_t                start,
 353         uint64_t                len)
 354 {
 355         bool                    res;
 356
 357         pthread_mutex_lock(&bmap->bt_lock);
 358         res = __bitmap_test(bmap, start, len);
 359         pthread_mutex_unlock(&bmap->bt_lock);
 360
 361         return res;
 362 }
 363
 364 /* Are none of the bits set? */
 365 bool
 366 bitmap_empty(
 367         struct bitmap           *bmap)
 368 {
 369         return bmap->bt_tree->avl_firstino == NULL;
 370 }
 371
 372 #ifdef DEBUG
 373 static int
 374 bitmap_dump_fn(
 375         uint64_t                startblock,
 376         uint64_t                blockcount,
 377         void                    *arg)
 378 {
 379         printf("%"PRIu64":%"PRIu64"\n", startblock, blockcount);
 380         return 0;
 381 }
 382
 383 /* Dump bitmap. */
 384 void
 385 bitmap_dump(
 386         struct bitmap           *bmap)
 387 {
 388         printf("BITMAP DUMP %p\n", bmap);
 389         bitmap_iterate(bmap, bitmap_dump_fn, NULL);
 390         printf("BITMAP DUMP DONE\n");
 391 }
 392 #endif