repair/slab.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * Copyright (C) 2016 Oracle.  All Rights Reserved.
   4  * Author: Darrick J. Wong <darrick.wong@oracle.com>
   5  */
   6 #include <libxfs.h>
   7 #include "slab.h"
   8
   9 #undef SLAB_DEBUG
  10
  11 #ifdef SLAB_DEBUG
  12 # define dbg_printf(f, a...)  do {printf(f, ## a); fflush(stdout); } while (0)
  13 #else
  14 # define dbg_printf(f, a...)
  15 #endif
  16
  17 /*
  18  * Slab Arrays and Bags
  19  *
  20  * The slab array is a dynamically growable linear array.  Internally it
  21  * maintains a list of slabs of increasing size; when a slab fills up, another
  22  * is allocated.  Each slab is sorted individually, which means that one must
  23  * use an iterator to walk the entire logical array, sorted order or otherwise.
  24  * Array items can neither be removed nor accessed randomly, since (at the
  25  * moment) the only user of them (storing reverse mappings) doesn't need either
  26  * piece.  Pointers are not stable across sort operations.
  27  *
  28  * A bag is a collection of pointers.  The bag can be added to or removed from
  29  * arbitrarily, and the bag items can be iterated.  Bags are used to process
  30  * rmaps into refcount btree entries.
  31  */
  32
  33 /*
  34  * Slabs -- each slab_hdr holds an array of items; when a slab_hdr fills up, we
  35  * allocate a new one and add to that one.  The slab object coordinates the
  36  * slab_hdrs.
  37  */
  38
  39 /* Each slab holds at least 4096 items */
  40 #define MIN_SLAB_NR             4096
  41 /* and cannot be larger than 128M */
  42 #define MAX_SLAB_SIZE           (128 * 1048576)
  43 struct xfs_slab_hdr {
  44         size_t                  sh_nr;
  45         size_t                  sh_inuse;       /* items in use */
  46         struct xfs_slab_hdr     *sh_next;       /* next slab hdr */
  47                                                 /* objects follow */
  48 };
  49
  50 struct xfs_slab {
  51         size_t                  s_item_sz;      /* item size */
  52         size_t                  s_nr_slabs;     /* # of slabs */
  53         size_t                  s_nr_items;     /* # of items */
  54         struct xfs_slab_hdr     *s_first;       /* first slab header */
  55         struct xfs_slab_hdr     *s_last;        /* last sh_next pointer */
  56 };
  57
  58 /*
  59  * Slab cursors -- each slab_hdr_cursor tracks a slab_hdr; the slab_cursor
  60  * tracks the slab_hdr_cursors.  If a compare_fn is specified, the cursor
  61  * returns objects in increasing order (if you've previously sorted the
  62  * slabs with qsort_slab()).  If compare_fn == NULL, it returns slab items
  63  * in order.
  64  */
  65 struct xfs_slab_hdr_cursor {
  66         struct xfs_slab_hdr     *hdr;           /* a slab header */
  67         size_t                  loc;            /* where we are in the slab */
  68 };
  69
  70 typedef int (*xfs_slab_compare_fn)(const void *, const void *);
  71
  72 struct xfs_slab_cursor {
  73         size_t                          nr;             /* # of per-slab cursors */
  74         struct xfs_slab                 *slab;          /* pointer to the slab */
  75         struct xfs_slab_hdr_cursor      *last_hcur;     /* last header we took from */
  76         xfs_slab_compare_fn             compare_fn;     /* compare items */
  77         struct xfs_slab_hdr_cursor      hcur[0];        /* per-slab cursors */
  78 };
  79
  80 /*
  81  * Bags -- each bag is an array of pointers items; when a bag fills up, we
  82  * resize it.
  83  */
  84 #define MIN_BAG_SIZE    4096
  85 struct xfs_bag {
  86         size_t                  bg_nr;          /* number of pointers */
  87         size_t                  bg_inuse;       /* number of slots in use */
  88         void                    **bg_ptrs;      /* pointers */
  89 };
  90 #define BAG_END(bag)    (&(bag)->bg_ptrs[(bag)->bg_nr])
  91
  92 /*
  93  * Create a slab to hold some objects of a particular size.
  94  */
  95 int
  96 init_slab(
  97         struct xfs_slab **slab,
  98         size_t          item_size)
  99 {
 100         struct xfs_slab *ptr;
 101
 102         ptr = calloc(1, sizeof(struct xfs_slab));
 103         if (!ptr)
 104                 return -ENOMEM;
 105         ptr->s_item_sz = item_size;
 106         ptr->s_last = NULL;
 107         *slab = ptr;
 108
 109         return 0;
 110 }
 111
 112 /*
 113  * Frees a slab.
 114  */
 115 void
 116 free_slab(
 117         struct xfs_slab         **slab)
 118 {
 119         struct xfs_slab         *ptr;
 120         struct xfs_slab_hdr     *hdr;
 121         struct xfs_slab_hdr     *nhdr;
 122
 123         ptr = *slab;
 124         if (!ptr)
 125                 return;
 126         hdr = ptr->s_first;
 127         while (hdr) {
 128                 nhdr = hdr->sh_next;
 129                 free(hdr);
 130                 hdr = nhdr;
 131         }
 132         free(ptr);
 133         *slab = NULL;
 134 }
 135
 136 static void *
 137 slab_ptr(
 138         struct xfs_slab         *slab,
 139         struct xfs_slab_hdr     *hdr,
 140         size_t                  idx)
 141 {
 142         char                    *p;
 143
 144         ASSERT(idx < hdr->sh_inuse);
 145         p = (char *)(hdr + 1);
 146         p += slab->s_item_sz * idx;
 147         return p;
 148 }
 149
 150 /*
 151  * Add an item to the slab.
 152  */
 153 int
 154 slab_add(
 155         struct xfs_slab         *slab,
 156         void                    *item)
 157 {
 158         struct xfs_slab_hdr             *hdr;
 159         void                    *p;
 160
 161         hdr = slab->s_last;
 162         if (!hdr || hdr->sh_inuse == hdr->sh_nr) {
 163                 size_t n;
 164
 165                 n = (hdr ? hdr->sh_nr * 2 : MIN_SLAB_NR);
 166                 if (n * slab->s_item_sz > MAX_SLAB_SIZE)
 167                         n = MAX_SLAB_SIZE / slab->s_item_sz;
 168                 hdr = malloc(sizeof(struct xfs_slab_hdr) + (n * slab->s_item_sz));
 169                 if (!hdr)
 170                         return -ENOMEM;
 171                 hdr->sh_nr = n;
 172                 hdr->sh_inuse = 0;
 173                 hdr->sh_next = NULL;
 174                 if (slab->s_last)
 175                         slab->s_last->sh_next = hdr;
 176                 if (!slab->s_first)
 177                         slab->s_first = hdr;
 178                 slab->s_last = hdr;
 179                 slab->s_nr_slabs++;
 180         }
 181         hdr->sh_inuse++;
 182         p = slab_ptr(slab, hdr, hdr->sh_inuse - 1);
 183         memcpy(p, item, slab->s_item_sz);
 184         slab->s_nr_items++;
 185
 186         return 0;
 187 }
 188
 189 #include "threads.h"
 190
 191 struct qsort_slab {
 192         struct xfs_slab         *slab;
 193         struct xfs_slab_hdr     *hdr;
 194         int                     (*compare_fn)(const void *, const void *);
 195 };
 196
 197 static void
 198 qsort_slab_helper(
 199         struct workqueue        *wq,
 200         xfs_agnumber_t          agno,
 201         void                    *arg)
 202 {
 203         struct qsort_slab       *qs = arg;
 204
 205         qsort(slab_ptr(qs->slab, qs->hdr, 0), qs->hdr->sh_inuse,
 206                         qs->slab->s_item_sz, qs->compare_fn);
 207         free(qs);
 208 }
 209
 210 /*
 211  * Sort the items in the slab.  Do not run this method if there are any
 212  * cursors holding on to the slab.
 213  */
 214 void
 215 qsort_slab(
 216         struct xfs_slab         *slab,
 217         int (*compare_fn)(const void *, const void *))
 218 {
 219         struct workqueue        wq;
 220         struct xfs_slab_hdr     *hdr;
 221         struct qsort_slab       *qs;
 222
 223         /*
 224          * If we don't have that many slabs, we're probably better
 225          * off skipping all the thread overhead.
 226          */
 227         if (slab->s_nr_slabs <= 4) {
 228                 hdr = slab->s_first;
 229                 while (hdr) {
 230                         qsort(slab_ptr(slab, hdr, 0), hdr->sh_inuse,
 231                                         slab->s_item_sz, compare_fn);
 232                         hdr = hdr->sh_next;
 233                 }
 234                 return;
 235         }
 236
 237         create_work_queue(&wq, NULL, platform_nproc());
 238         hdr = slab->s_first;
 239         while (hdr) {
 240                 qs = malloc(sizeof(struct qsort_slab));
 241                 qs->slab = slab;
 242                 qs->hdr = hdr;
 243                 qs->compare_fn = compare_fn;
 244                 queue_work(&wq, qsort_slab_helper, 0, qs);
 245                 hdr = hdr->sh_next;
 246         }
 247         destroy_work_queue(&wq);
 248 }
 249
 250 /*
 251  * init_slab_cursor() -- Create a slab cursor to iterate the slab items.
 252  *
 253  * @slab: The slab.
 254  * @compare_fn: If specified, use this function to return items in ascending order.
 255  * @cur: The new cursor.
 256  */
 257 int
 258 init_slab_cursor(
 259         struct xfs_slab         *slab,
 260         int (*compare_fn)(const void *, const void *),
 261         struct xfs_slab_cursor  **cur)
 262 {
 263         struct xfs_slab_cursor  *c;
 264         struct xfs_slab_hdr_cursor      *hcur;
 265         struct xfs_slab_hdr     *hdr;
 266
 267         c = malloc(sizeof(struct xfs_slab_cursor) +
 268                    (sizeof(struct xfs_slab_hdr_cursor) * slab->s_nr_slabs));
 269         if (!c)
 270                 return -ENOMEM;
 271         c->nr = slab->s_nr_slabs;
 272         c->slab = slab;
 273         c->compare_fn = compare_fn;
 274         c->last_hcur = NULL;
 275         hcur = (struct xfs_slab_hdr_cursor *)(c + 1);
 276         hdr = slab->s_first;
 277         while (hdr) {
 278                 hcur->hdr = hdr;
 279                 hcur->loc = 0;
 280                 hcur++;
 281                 hdr = hdr->sh_next;
 282         }
 283         *cur = c;
 284         return 0;
 285 }
 286
 287 /*
 288  * Free the slab cursor.
 289  */
 290 void
 291 free_slab_cursor(
 292         struct xfs_slab_cursor  **cur)
 293 {
 294         if (!*cur)
 295                 return;
 296         free(*cur);
 297         *cur = NULL;
 298 }
 299
 300 /*
 301  * Return the smallest item in the slab, without advancing the iterator.
 302  * The slabs must be sorted prior to the creation of the cursor.
 303  */
 304 void *
 305 peek_slab_cursor(
 306         struct xfs_slab_cursor  *cur)
 307 {
 308         struct xfs_slab_hdr_cursor      *hcur;
 309         void                    *p = NULL;
 310         void                    *q;
 311         size_t                  i;
 312
 313         cur->last_hcur = NULL;
 314
 315         /* no compare function; inorder traversal */
 316         if (!cur->compare_fn) {
 317                 if (!cur->last_hcur)
 318                         cur->last_hcur = &cur->hcur[0];
 319                 hcur = cur->last_hcur;
 320                 while (hcur < &cur->hcur[cur->nr] &&
 321                         hcur->loc >= hcur->hdr->sh_inuse)
 322                         hcur++;
 323                 if (hcur == &cur->hcur[cur->nr])
 324                         return NULL;
 325                 p = slab_ptr(cur->slab, hcur->hdr, hcur->loc);
 326                 cur->last_hcur = hcur;
 327                 return p;
 328         }
 329
 330         /* otherwise return things in increasing order */
 331         for (i = 0, hcur = &cur->hcur[i]; i < cur->nr; i++, hcur++) {
 332                 if (hcur->loc >= hcur->hdr->sh_inuse)
 333                         continue;
 334                 q = slab_ptr(cur->slab, hcur->hdr, hcur->loc);
 335                 if (!p || cur->compare_fn(p, q) > 0) {
 336                         p = q;
 337                         cur->last_hcur = hcur;
 338                 }
 339         }
 340
 341         return p;
 342 }
 343
 344 /*
 345  * After a peek operation, advance the cursor.
 346  */
 347 void
 348 advance_slab_cursor(
 349         struct xfs_slab_cursor  *cur)
 350 {
 351         ASSERT(cur->last_hcur);
 352         cur->last_hcur->loc++;
 353 }
 354
 355 /*
 356  * Retrieve the next item in the slab and advance the cursor.
 357  */
 358 void *
 359 pop_slab_cursor(
 360         struct xfs_slab_cursor  *cur)
 361 {
 362         void                    *p;
 363
 364         p = peek_slab_cursor(cur);
 365         if (p)
 366                 advance_slab_cursor(cur);
 367         return p;
 368 }
 369
 370 /*
 371  * Return the number of items in the slab.
 372  */
 373 size_t
 374 slab_count(
 375         struct xfs_slab *slab)
 376 {
 377         return slab->s_nr_items;
 378 }
 379
 380 /*
 381  * Create a bag to point to some objects.
 382  */
 383 int
 384 init_bag(
 385         struct xfs_bag  **bag)
 386 {
 387         struct xfs_bag  *ptr;
 388
 389         ptr = calloc(1, sizeof(struct xfs_bag));
 390         if (!ptr)
 391                 return -ENOMEM;
 392         ptr->bg_ptrs = calloc(MIN_BAG_SIZE, sizeof(void *));
 393         if (!ptr->bg_ptrs) {
 394                 free(ptr);
 395                 return -ENOMEM;
 396         }
 397         ptr->bg_nr = MIN_BAG_SIZE;
 398         *bag = ptr;
 399         return 0;
 400 }
 401
 402 /*
 403  * Free a bag of pointers.
 404  */
 405 void
 406 free_bag(
 407         struct xfs_bag  **bag)
 408 {
 409         struct xfs_bag  *ptr;
 410
 411         ptr = *bag;
 412         if (!ptr)
 413                 return;
 414         free(ptr->bg_ptrs);
 415         free(ptr);
 416         *bag = NULL;
 417 }
 418
 419 /*
 420  * Add an object to the pointer bag.
 421  */
 422 int
 423 bag_add(
 424         struct xfs_bag  *bag,
 425         void            *ptr)
 426 {
 427         void            **p, **x;
 428
 429         p = &bag->bg_ptrs[bag->bg_inuse];
 430         if (p == BAG_END(bag)) {
 431                 /* No free space, alloc more pointers */
 432                 size_t nr;
 433
 434                 nr = bag->bg_nr * 2;
 435                 x = realloc(bag->bg_ptrs, nr * sizeof(void *));
 436                 if (!x)
 437                         return -ENOMEM;
 438                 bag->bg_ptrs = x;
 439                 memset(BAG_END(bag), 0, bag->bg_nr * sizeof(void *));
 440                 bag->bg_nr = nr;
 441         }
 442         bag->bg_ptrs[bag->bg_inuse] = ptr;
 443         bag->bg_inuse++;
 444         return 0;
 445 }
 446
 447 /*
 448  * Remove a pointer from a bag.
 449  */
 450 int
 451 bag_remove(
 452         struct xfs_bag  *bag,
 453         size_t          nr)
 454 {
 455         ASSERT(nr < bag->bg_inuse);
 456         memmove(&bag->bg_ptrs[nr], &bag->bg_ptrs[nr + 1],
 457                 (bag->bg_inuse - nr - 1) * sizeof(void *));
 458         bag->bg_inuse--;
 459         return 0;
 460 }
 461
 462 /*
 463  * Return the number of items in a bag.
 464  */
 465 size_t
 466 bag_count(
 467         struct xfs_bag  *bag)
 468 {
 469         return bag->bg_inuse;
 470 }
 471
 472 /*
 473  * Return the nth item in a bag.
 474  */
 475 void *
 476 bag_item(
 477         struct xfs_bag  *bag,
 478         size_t          nr)
 479 {
 480         if (nr >= bag->bg_inuse)
 481                 return NULL;
 482         return bag->bg_ptrs[nr];
 483 }