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