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 bool
 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 true;
 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                                 return false;
 302
 303                         node = avl64_insert(bmap->bt_tree, &ext->btn_node);
 304                         if (node == NULL) {
 305                                 errno = EEXIST;
 306                                 return false;
 307                         }
 308                         break;
 309                 }
 310         }
 311
 312         pthread_mutex_unlock(&bmap->bt_lock);
 313         return true;
 314 }
 315 #endif
 316
 317 #ifdef DEBUG
 318 /* Iterate the set regions of this bitmap. */
 319 int
 320 bitmap_iterate(
 321         struct bitmap           *bmap,
 322         int                     (*fn)(uint64_t, uint64_t, void *),
 323         void                    *arg)
 324 {
 325         struct avl64node        *node;
 326         struct bitmap_node      *ext;
 327         int                     error = 0;
 328
 329         pthread_mutex_lock(&bmap->bt_lock);
 330         avl_for_each(bmap->bt_tree, node) {
 331                 ext = container_of(node, struct bitmap_node, btn_node);
 332                 error = fn(ext->btn_start, ext->btn_length, arg);
 333                 if (error)
 334                         break;
 335         }
 336         pthread_mutex_unlock(&bmap->bt_lock);
 337
 338         return error;
 339 }
 340 #endif
 341
 342 /* Do any bitmap extents overlap the given one?  (locked) */
 343 static bool
 344 __bitmap_test(
 345         struct bitmap           *bmap,
 346         uint64_t                start,
 347         uint64_t                len)
 348 {
 349         struct avl64node        *firstn;
 350         struct avl64node        *lastn;
 351
 352         /* Find any existing nodes over that range. */
 353         avl64_findranges(bmap->bt_tree, start, start + len, &firstn, &lastn);
 354
 355         return firstn != NULL && lastn != NULL;
 356 }
 357
 358 /* Is any part of this range set? */
 359 bool
 360 bitmap_test(
 361         struct bitmap           *bmap,
 362         uint64_t                start,
 363         uint64_t                len)
 364 {
 365         bool                    res;
 366
 367         pthread_mutex_lock(&bmap->bt_lock);
 368         res = __bitmap_test(bmap, start, len);
 369         pthread_mutex_unlock(&bmap->bt_lock);
 370
 371         return res;
 372 }
 373
 374 /* Are none of the bits set? */
 375 bool
 376 bitmap_empty(
 377         struct bitmap           *bmap)
 378 {
 379         return bmap->bt_tree->avl_firstino == NULL;
 380 }
 381
 382 #ifdef DEBUG
 383 static int
 384 bitmap_dump_fn(
 385         uint64_t                startblock,
 386         uint64_t                blockcount,
 387         void                    *arg)
 388 {
 389         printf("%"PRIu64":%"PRIu64"\n", startblock, blockcount);
 390         return 0;
 391 }
 392
 393 /* Dump bitmap. */
 394 void
 395 bitmap_dump(
 396         struct bitmap           *bmap)
 397 {
 398         printf("BITMAP DUMP %p\n", bmap);
 399         bitmap_iterate(bmap, bitmap_dump_fn, NULL);
 400         printf("BITMAP DUMP DONE\n");
 401 }
 402 #endif