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; \
  27                         pos != (l); \
  28                         pos = n, n = pos ? pos->avl_nextino : NULL)
  29
  30 #define avl_for_each_safe(tree, pos, n) \
  31         for (pos = (tree)->avl_firstino, n = pos ? pos->avl_nextino : NULL; \
  32                         pos != NULL; \
  33                         pos = n, n = pos ? pos->avl_nextino : NULL)
  34
  35 #define avl_for_each(tree, pos) \
  36         for (pos = (tree)->avl_firstino; pos != NULL; pos = pos->avl_nextino)
  37
  38 struct bitmap_node {
  39         struct avl64node        btn_node;
  40         uint64_t                btn_start;
  41         uint64_t                btn_length;
  42 };
  43
  44 static uint64_t
  45 extent_start(
  46         struct avl64node        *node)
  47 {
  48         struct bitmap_node      *btn;
  49
  50         btn = container_of(node, struct bitmap_node, btn_node);
  51         return btn->btn_start;
  52 }
  53
  54 static uint64_t
  55 extent_end(
  56         struct avl64node        *node)
  57 {
  58         struct bitmap_node      *btn;
  59
  60         btn = container_of(node, struct bitmap_node, btn_node);
  61         return btn->btn_start + btn->btn_length;
  62 }
  63
  64 static struct avl64ops bitmap_ops = {
  65         extent_start,
  66         extent_end,
  67 };
  68
  69 /* Initialize a bitmap. */
  70 int
  71 bitmap_alloc(
  72         struct bitmap           **bmapp)
  73 {
  74         struct bitmap           *bmap;
  75         int                     ret;
  76
  77         bmap = calloc(1, sizeof(struct bitmap));
  78         if (!bmap)
  79                 return -errno;
  80         bmap->bt_tree = malloc(sizeof(struct avl64tree_desc));
  81         if (!bmap->bt_tree) {
  82                 ret = -errno;
  83                 goto out;
  84         }
  85
  86         ret = -pthread_mutex_init(&bmap->bt_lock, NULL);
  87         if (ret)
  88                 goto out_tree;
  89
  90         avl64_init_tree(bmap->bt_tree, &bitmap_ops);
  91         *bmapp = bmap;
  92
  93         return 0;
  94 out_tree:
  95         free(bmap->bt_tree);
  96 out:
  97         free(bmap);
  98         return ret;
  99 }
 100
 101 /* Free a bitmap. */
 102 void
 103 bitmap_free(
 104         struct bitmap           **bmapp)
 105 {
 106         struct bitmap           *bmap;
 107         struct avl64node        *node;
 108         struct avl64node        *n;
 109         struct bitmap_node      *ext;
 110
 111         bmap = *bmapp;
 112         avl_for_each_safe(bmap->bt_tree, node, n) {
 113                 ext = container_of(node, struct bitmap_node, btn_node);
 114                 free(ext);
 115         }
 116         free(bmap->bt_tree);
 117         free(bmap);
 118         *bmapp = NULL;
 119 }
 120
 121 /* Create a new bitmap extent node. */
 122 static struct bitmap_node *
 123 bitmap_node_init(
 124         uint64_t                start,
 125         uint64_t                len)
 126 {
 127         struct bitmap_node      *ext;
 128
 129         ext = malloc(sizeof(struct bitmap_node));
 130         if (!ext)
 131                 return NULL;
 132
 133         ext->btn_node.avl_nextino = NULL;
 134         ext->btn_start = start;
 135         ext->btn_length = len;
 136
 137         return ext;
 138 }
 139
 140 /* Create a new bitmap node and insert it. */
 141 static inline int
 142 __bitmap_insert(
 143         struct bitmap           *bmap,
 144         uint64_t                start,
 145         uint64_t                length)
 146 {
 147         struct bitmap_node      *ext;
 148         struct avl64node        *node;
 149
 150         ext = bitmap_node_init(start, length);
 151         if (!ext)
 152                 return -errno;
 153
 154         node = avl64_insert(bmap->bt_tree, &ext->btn_node);
 155         if (node == NULL) {
 156                 free(ext);
 157                 return -EEXIST;
 158         }
 159
 160         return 0;
 161 }
 162
 163 /* Set a region of bits (locked). */
 164 static int
 165 __bitmap_set(
 166         struct bitmap           *bmap,
 167         uint64_t                start,
 168         uint64_t                length)
 169 {
 170         struct avl64node        *firstn;
 171         struct avl64node        *lastn;
 172         struct avl64node        *pos;
 173         struct avl64node        *n;
 174         struct avl64node        *l;
 175         struct bitmap_node      *ext;
 176         uint64_t                new_start;
 177         uint64_t                new_length;
 178
 179         /* Find any existing nodes adjacent or within that range. */
 180         avl64_findranges(bmap->bt_tree, start - 1, start + length + 1,
 181                         &firstn, &lastn);
 182
 183         /* Nothing, just insert a new extent. */
 184         if (firstn == NULL && lastn == NULL)
 185                 return __bitmap_insert(bmap, start, length);
 186
 187         assert(firstn != NULL && lastn != NULL);
 188         new_start = start;
 189         new_length = length;
 190
 191         avl_for_each_range_safe(pos, n, l, firstn, lastn) {
 192                 ext = container_of(pos, struct bitmap_node, btn_node);
 193
 194                 /* Bail if the new extent is contained within an old one. */
 195                 if (ext->btn_start <= start &&
 196                     ext->btn_start + ext->btn_length >= start + length)
 197                         return 0;
 198
 199                 /* Check for overlapping and adjacent extents. */
 200                 if (ext->btn_start + ext->btn_length >= start ||
 201                     ext->btn_start <= start + length) {
 202                         if (ext->btn_start < start) {
 203                                 new_start = ext->btn_start;
 204                                 new_length += ext->btn_length;
 205                         }
 206
 207                         if (ext->btn_start + ext->btn_length >
 208                             new_start + new_length)
 209                                 new_length = ext->btn_start + ext->btn_length -
 210                                                 new_start;
 211
 212                         avl64_delete(bmap->bt_tree, pos);
 213                         free(ext);
 214                 }
 215         }
 216
 217         return __bitmap_insert(bmap, new_start, new_length);
 218 }
 219
 220 /* Set a region of bits. */
 221 int
 222 bitmap_set(
 223         struct bitmap           *bmap,
 224         uint64_t                start,
 225         uint64_t                length)
 226 {
 227         int                     res;
 228
 229         pthread_mutex_lock(&bmap->bt_lock);
 230         res = __bitmap_set(bmap, start, length);
 231         pthread_mutex_unlock(&bmap->bt_lock);
 232
 233         return res;
 234 }
 235
 236 #if 0   /* Unused, provided for completeness. */
 237 /* Clear a region of bits. */
 238 int
 239 bitmap_clear(
 240         struct bitmap           *bmap,
 241         uint64_t                start,
 242         uint64_t                len)
 243 {
 244         struct avl64node        *firstn;
 245         struct avl64node        *lastn;
 246         struct avl64node        *pos;
 247         struct avl64node        *n;
 248         struct avl64node        *l;
 249         struct bitmap_node      *ext;
 250         uint64_t                new_start;
 251         uint64_t                new_length;
 252         struct avl64node        *node;
 253         int                     stat;
 254
 255         pthread_mutex_lock(&bmap->bt_lock);
 256         /* Find any existing nodes over that range. */
 257         avl64_findranges(bmap->bt_tree, start, start + len, &firstn, &lastn);
 258
 259         /* Nothing, we're done. */
 260         if (firstn == NULL && lastn == NULL) {
 261                 pthread_mutex_unlock(&bmap->bt_lock);
 262                 return 0;
 263         }
 264
 265         assert(firstn != NULL && lastn != NULL);
 266
 267         /* Delete or truncate everything in sight. */
 268         avl_for_each_range_safe(pos, n, l, firstn, lastn) {
 269                 ext = container_of(pos, struct bitmap_node, btn_node);
 270
 271                 stat = 0;
 272                 if (ext->btn_start < start)
 273                         stat |= 1;
 274                 if (ext->btn_start + ext->btn_length > start + len)
 275                         stat |= 2;
 276                 switch (stat) {
 277                 case 0:
 278                         /* Extent totally within range; delete. */
 279                         avl64_delete(bmap->bt_tree, pos);
 280                         free(ext);
 281                         break;
 282                 case 1:
 283                         /* Extent is left-adjacent; truncate. */
 284                         ext->btn_length = start - ext->btn_start;
 285                         break;
 286                 case 2:
 287                         /* Extent is right-adjacent; move it. */
 288                         ext->btn_length = ext->btn_start + ext->btn_length -
 289                                         (start + len);
 290                         ext->btn_start = start + len;
 291                         break;
 292                 case 3:
 293                         /* Extent overlaps both ends. */
 294                         ext->btn_length = start - ext->btn_start;
 295                         new_start = start + len;
 296                         new_length = ext->btn_start + ext->btn_length -
 297                                         new_start;
 298
 299                         ext = bitmap_node_init(new_start, new_length);
 300                         if (!ext) {
 301                                 ret = -errno;
 302                                 goto out;
 303                         }
 304
 305                         node = avl64_insert(bmap->bt_tree, &ext->btn_node);
 306                         if (node == NULL) {
 307                                 ret = -EEXIST;
 308                                 goto out;
 309                         }
 310                         break;
 311                 }
 312         }
 313
 314 out:
 315         pthread_mutex_unlock(&bmap->bt_lock);
 316         return ret;
 317 }
 318 #endif
 319
 320 /* Iterate the set regions of this bitmap. */
 321 int
 322 bitmap_iterate(
 323         struct bitmap           *bmap,
 324         int                     (*fn)(uint64_t, uint64_t, void *),
 325         void                    *arg)
 326 {
 327         struct avl64node        *node;
 328         struct bitmap_node      *ext;
 329         int                     error = 0;
 330
 331         pthread_mutex_lock(&bmap->bt_lock);
 332         avl_for_each(bmap->bt_tree, node) {
 333                 ext = container_of(node, struct bitmap_node, btn_node);
 334                 error = fn(ext->btn_start, ext->btn_length, arg);
 335                 if (error)
 336                         break;
 337         }
 338         pthread_mutex_unlock(&bmap->bt_lock);
 339
 340         return error;
 341 }
 342
 343 /* Iterate the set regions of part of this bitmap. */
 344 int
 345 bitmap_iterate_range(
 346         struct bitmap           *bmap,
 347         uint64_t                start,
 348         uint64_t                length,
 349         int                     (*fn)(uint64_t, uint64_t, void *),
 350         void                    *arg)
 351 {
 352         struct avl64node        *firstn;
 353         struct avl64node        *lastn;
 354         struct avl64node        *pos;
 355         struct avl64node        *n;
 356         struct avl64node        *l;
 357         struct bitmap_node      *ext;
 358         int                     ret = 0;
 359
 360         pthread_mutex_lock(&bmap->bt_lock);
 361
 362         avl64_findranges(bmap->bt_tree, start, start + length, &firstn,
 363                         &lastn);
 364
 365         if (firstn == NULL && lastn == NULL)
 366                 goto out;
 367
 368         avl_for_each_range_safe(pos, n, l, firstn, lastn) {
 369                 ext = container_of(pos, struct bitmap_node, btn_node);
 370                 ret = fn(ext->btn_start, ext->btn_length, arg);
 371                 if (ret)
 372                         break;
 373         }
 374
 375 out:
 376         pthread_mutex_unlock(&bmap->bt_lock);
 377         return ret;
 378 }
 379
 380 /* Do any bitmap extents overlap the given one?  (locked) */
 381 static bool
 382 __bitmap_test(
 383         struct bitmap           *bmap,
 384         uint64_t                start,
 385         uint64_t                len)
 386 {
 387         struct avl64node        *firstn;
 388         struct avl64node        *lastn;
 389
 390         /* Find any existing nodes over that range. */
 391         avl64_findranges(bmap->bt_tree, start, start + len, &firstn, &lastn);
 392
 393         return firstn != NULL && lastn != NULL;
 394 }
 395
 396 /* Is any part of this range set? */
 397 bool
 398 bitmap_test(
 399         struct bitmap           *bmap,
 400         uint64_t                start,
 401         uint64_t                len)
 402 {
 403         bool                    res;
 404
 405         pthread_mutex_lock(&bmap->bt_lock);
 406         res = __bitmap_test(bmap, start, len);
 407         pthread_mutex_unlock(&bmap->bt_lock);
 408
 409         return res;
 410 }
 411
 412 /* Are none of the bits set? */
 413 bool
 414 bitmap_empty(
 415         struct bitmap           *bmap)
 416 {
 417         return bmap->bt_tree->avl_firstino == NULL;
 418 }
 419
 420 #ifdef DEBUG
 421 static int
 422 bitmap_dump_fn(
 423         uint64_t                startblock,
 424         uint64_t                blockcount,
 425         void                    *arg)
 426 {
 427         printf("%"PRIu64":%"PRIu64"\n", startblock, blockcount);
 428         return 0;
 429 }
 430
 431 /* Dump bitmap. */
 432 void
 433 bitmap_dump(
 434         struct bitmap           *bmap)
 435 {
 436         printf("BITMAP DUMP %p\n", bmap);
 437         bitmap_iterate(bmap, bitmap_dump_fn, NULL);
 438         printf("BITMAP DUMP DONE\n");
 439 }
 440 #endif