repair/slab.c

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