scrub/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 bool
  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 false;
  78         bmap->bt_tree = malloc(sizeof(struct avl64tree_desc));
  79         if (!bmap->bt_tree) {
  80                 free(bmap);
  81                 return false;
  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 true;
  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         *bmapp = NULL;
 108 }
 109
 110 /* Create a new bitmap extent node. */
 111 static struct bitmap_node *
 112 bitmap_node_init(
 113         uint64_t                start,
 114         uint64_t                len)
 115 {
 116         struct bitmap_node      *ext;
 117
 118         ext = malloc(sizeof(struct bitmap_node));
 119         if (!ext)
 120                 return NULL;
 121
 122         ext->btn_node.avl_nextino = NULL;
 123         ext->btn_start = start;
 124         ext->btn_length = len;
 125
 126         return ext;
 127 }
 128
 129 /* Set a region of bits (locked). */
 130 static bool
 131 __bitmap_set(
 132         struct bitmap           *bmap,
 133         uint64_t                start,
 134         uint64_t                length)
 135 {
 136         struct avl64node        *firstn;
 137         struct avl64node        *lastn;
 138         struct avl64node        *pos;
 139         struct avl64node        *n;
 140         struct avl64node        *l;
 141         struct bitmap_node      *ext;
 142         uint64_t                new_start;
 143         uint64_t                new_length;
 144         struct avl64node        *node;
 145         bool                    res = true;
 146
 147         /* Find any existing nodes adjacent or within that range. */
 148         avl64_findranges(bmap->bt_tree, start - 1, start + length + 1,
 149                         &firstn, &lastn);
 150
 151         /* Nothing, just insert a new extent. */
 152         if (firstn == NULL && lastn == NULL) {
 153                 ext = bitmap_node_init(start, length);
 154                 if (!ext)
 155                         return false;
 156
 157                 node = avl64_insert(bmap->bt_tree, &ext->btn_node);
 158                 if (node == NULL) {
 159                         free(ext);
 160                         errno = EEXIST;
 161                         return false;
 162                 }
 163
 164                 return true;
 165         }
 166
 167         assert(firstn != NULL && lastn != NULL);
 168         new_start = start;
 169         new_length = length;
 170
 171         avl_for_each_range_safe(pos, n, l, firstn, lastn) {
 172                 ext = container_of(pos, struct bitmap_node, btn_node);
 173
 174                 /* Bail if the new extent is contained within an old one. */
 175                 if (ext->btn_start <= start &&
 176                     ext->btn_start + ext->btn_length >= start + length)
 177                         return res;
 178
 179                 /* Check for overlapping and adjacent extents. */
 180                 if (ext->btn_start + ext->btn_length >= start ||
 181                     ext->btn_start <= start + length) {
 182                         if (ext->btn_start < start) {
 183                                 new_start = ext->btn_start;
 184                                 new_length += ext->btn_length;
 185                         }
 186
 187                         if (ext->btn_start + ext->btn_length >
 188                             new_start + new_length)
 189                                 new_length = ext->btn_start + ext->btn_length -
 190                                                 new_start;
 191
 192                         avl64_delete(bmap->bt_tree, pos);
 193                         free(ext);
 194                 }
 195         }
 196
 197         ext = bitmap_node_init(new_start, new_length);
 198         if (!ext)
 199                 return false;
 200
 201         node = avl64_insert(bmap->bt_tree, &ext->btn_node);
 202         if (node == NULL) {
 203                 free(ext);
 204                 errno = EEXIST;
 205                 return false;
 206         }
 207
 208         return res;
 209 }
 210
 211 /* Set a region of bits. */
 212 bool
 213 bitmap_set(
 214         struct bitmap           *bmap,
 215         uint64_t                start,
 216         uint64_t                length)
 217 {
 218         bool                    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 bool
 311 bitmap_iterate(
 312         struct bitmap           *bmap,
 313         bool                    (*fn)(uint64_t, uint64_t, void *),
 314         void                    *arg)
 315 {
 316         struct avl64node        *node;
 317         struct bitmap_node      *ext;
 318         bool                    moveon = true;
 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                 moveon = fn(ext->btn_start, ext->btn_length, arg);
 324                 if (!moveon)
 325                         break;
 326         }
 327         pthread_mutex_unlock(&bmap->bt_lock);
 328
 329         return moveon;
 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 bool
 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 true;
 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