drivers/md/dm-bio-prison-v1.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * Copyright (C) 2012 Red Hat, Inc.
   4  *
   5  * This file is released under the GPL.
   6  */
   7
   8 #include "dm.h"
   9 #include "dm-bio-prison-v1.h"
  10 #include "dm-bio-prison-v2.h"
  11
  12 #include <linux/spinlock.h>
  13 #include <linux/mempool.h>
  14 #include <linux/module.h>
  15 #include <linux/slab.h>
  16
  17 /*----------------------------------------------------------------*/
  18
  19 #define MIN_CELLS 1024
  20
  21 struct dm_bio_prison {
  22         spinlock_t lock;
  23         struct rb_root cells;
  24         mempool_t cell_pool;
  25 };
  26
  27 static struct kmem_cache *_cell_cache;
  28
  29 /*----------------------------------------------------------------*/
  30
  31 /*
  32  * @nr_cells should be the number of cells you want in use _concurrently_.
  33  * Don't confuse it with the number of distinct keys.
  34  */
  35 struct dm_bio_prison *dm_bio_prison_create(void)
  36 {
  37         struct dm_bio_prison *prison = kzalloc(sizeof(*prison), GFP_KERNEL);
  38         int ret;
  39
  40         if (!prison)
  41                 return NULL;
  42
  43         spin_lock_init(&prison->lock);
  44
  45         ret = mempool_init_slab_pool(&prison->cell_pool, MIN_CELLS, _cell_cache);
  46         if (ret) {
  47                 kfree(prison);
  48                 return NULL;
  49         }
  50
  51         prison->cells = RB_ROOT;
  52
  53         return prison;
  54 }
  55 EXPORT_SYMBOL_GPL(dm_bio_prison_create);
  56
  57 void dm_bio_prison_destroy(struct dm_bio_prison *prison)
  58 {
  59         mempool_exit(&prison->cell_pool);
  60         kfree(prison);
  61 }
  62 EXPORT_SYMBOL_GPL(dm_bio_prison_destroy);
  63
  64 struct dm_bio_prison_cell *dm_bio_prison_alloc_cell(struct dm_bio_prison *prison, gfp_t gfp)
  65 {
  66         return mempool_alloc(&prison->cell_pool, gfp);
  67 }
  68 EXPORT_SYMBOL_GPL(dm_bio_prison_alloc_cell);
  69
  70 void dm_bio_prison_free_cell(struct dm_bio_prison *prison,
  71                              struct dm_bio_prison_cell *cell)
  72 {
  73         mempool_free(cell, &prison->cell_pool);
  74 }
  75 EXPORT_SYMBOL_GPL(dm_bio_prison_free_cell);
  76
  77 static void __setup_new_cell(struct dm_cell_key *key,
  78                              struct bio *holder,
  79                              struct dm_bio_prison_cell *cell)
  80 {
  81         memcpy(&cell->key, key, sizeof(cell->key));
  82         cell->holder = holder;
  83         bio_list_init(&cell->bios);
  84 }
  85
  86 static int cmp_keys(struct dm_cell_key *lhs,
  87                     struct dm_cell_key *rhs)
  88 {
  89         if (lhs->virtual < rhs->virtual)
  90                 return -1;
  91
  92         if (lhs->virtual > rhs->virtual)
  93                 return 1;
  94
  95         if (lhs->dev < rhs->dev)
  96                 return -1;
  97
  98         if (lhs->dev > rhs->dev)
  99                 return 1;
 100
 101         if (lhs->block_end <= rhs->block_begin)
 102                 return -1;
 103
 104         if (lhs->block_begin >= rhs->block_end)
 105                 return 1;
 106
 107         return 0;
 108 }
 109
 110 static int __bio_detain(struct dm_bio_prison *prison,
 111                         struct dm_cell_key *key,
 112                         struct bio *inmate,
 113                         struct dm_bio_prison_cell *cell_prealloc,
 114                         struct dm_bio_prison_cell **cell_result)
 115 {
 116         int r;
 117         struct rb_node **new = &prison->cells.rb_node, *parent = NULL;
 118
 119         while (*new) {
 120                 struct dm_bio_prison_cell *cell =
 121                         rb_entry(*new, struct dm_bio_prison_cell, node);
 122
 123                 r = cmp_keys(key, &cell->key);
 124
 125                 parent = *new;
 126                 if (r < 0)
 127                         new = &((*new)->rb_left);
 128                 else if (r > 0)
 129                         new = &((*new)->rb_right);
 130                 else {
 131                         if (inmate)
 132                                 bio_list_add(&cell->bios, inmate);
 133                         *cell_result = cell;
 134                         return 1;
 135                 }
 136         }
 137
 138         __setup_new_cell(key, inmate, cell_prealloc);
 139         *cell_result = cell_prealloc;
 140
 141         rb_link_node(&cell_prealloc->node, parent, new);
 142         rb_insert_color(&cell_prealloc->node, &prison->cells);
 143
 144         return 0;
 145 }
 146
 147 static int bio_detain(struct dm_bio_prison *prison,
 148                       struct dm_cell_key *key,
 149                       struct bio *inmate,
 150                       struct dm_bio_prison_cell *cell_prealloc,
 151                       struct dm_bio_prison_cell **cell_result)
 152 {
 153         int r;
 154
 155         spin_lock_irq(&prison->lock);
 156         r = __bio_detain(prison, key, inmate, cell_prealloc, cell_result);
 157         spin_unlock_irq(&prison->lock);
 158
 159         return r;
 160 }
 161
 162 int dm_bio_detain(struct dm_bio_prison *prison,
 163                   struct dm_cell_key *key,
 164                   struct bio *inmate,
 165                   struct dm_bio_prison_cell *cell_prealloc,
 166                   struct dm_bio_prison_cell **cell_result)
 167 {
 168         return bio_detain(prison, key, inmate, cell_prealloc, cell_result);
 169 }
 170 EXPORT_SYMBOL_GPL(dm_bio_detain);
 171
 172 int dm_get_cell(struct dm_bio_prison *prison,
 173                 struct dm_cell_key *key,
 174                 struct dm_bio_prison_cell *cell_prealloc,
 175                 struct dm_bio_prison_cell **cell_result)
 176 {
 177         return bio_detain(prison, key, NULL, cell_prealloc, cell_result);
 178 }
 179 EXPORT_SYMBOL_GPL(dm_get_cell);
 180
 181 /*
 182  * @inmates must have been initialised prior to this call
 183  */
 184 static void __cell_release(struct dm_bio_prison *prison,
 185                            struct dm_bio_prison_cell *cell,
 186                            struct bio_list *inmates)
 187 {
 188         rb_erase(&cell->node, &prison->cells);
 189
 190         if (inmates) {
 191                 if (cell->holder)
 192                         bio_list_add(inmates, cell->holder);
 193                 bio_list_merge(inmates, &cell->bios);
 194         }
 195 }
 196
 197 void dm_cell_release(struct dm_bio_prison *prison,
 198                      struct dm_bio_prison_cell *cell,
 199                      struct bio_list *bios)
 200 {
 201         spin_lock_irq(&prison->lock);
 202         __cell_release(prison, cell, bios);
 203         spin_unlock_irq(&prison->lock);
 204 }
 205 EXPORT_SYMBOL_GPL(dm_cell_release);
 206
 207 /*
 208  * Sometimes we don't want the holder, just the additional bios.
 209  */
 210 static void __cell_release_no_holder(struct dm_bio_prison *prison,
 211                                      struct dm_bio_prison_cell *cell,
 212                                      struct bio_list *inmates)
 213 {
 214         rb_erase(&cell->node, &prison->cells);
 215         bio_list_merge(inmates, &cell->bios);
 216 }
 217
 218 void dm_cell_release_no_holder(struct dm_bio_prison *prison,
 219                                struct dm_bio_prison_cell *cell,
 220                                struct bio_list *inmates)
 221 {
 222         unsigned long flags;
 223
 224         spin_lock_irqsave(&prison->lock, flags);
 225         __cell_release_no_holder(prison, cell, inmates);
 226         spin_unlock_irqrestore(&prison->lock, flags);
 227 }
 228 EXPORT_SYMBOL_GPL(dm_cell_release_no_holder);
 229
 230 void dm_cell_error(struct dm_bio_prison *prison,
 231                    struct dm_bio_prison_cell *cell, blk_status_t error)
 232 {
 233         struct bio_list bios;
 234         struct bio *bio;
 235
 236         bio_list_init(&bios);
 237         dm_cell_release(prison, cell, &bios);
 238
 239         while ((bio = bio_list_pop(&bios))) {
 240                 bio->bi_status = error;
 241                 bio_endio(bio);
 242         }
 243 }
 244 EXPORT_SYMBOL_GPL(dm_cell_error);
 245
 246 void dm_cell_visit_release(struct dm_bio_prison *prison,
 247                            void (*visit_fn)(void *, struct dm_bio_prison_cell *),
 248                            void *context,
 249                            struct dm_bio_prison_cell *cell)
 250 {
 251         spin_lock_irq(&prison->lock);
 252         visit_fn(context, cell);
 253         rb_erase(&cell->node, &prison->cells);
 254         spin_unlock_irq(&prison->lock);
 255 }
 256 EXPORT_SYMBOL_GPL(dm_cell_visit_release);
 257
 258 static int __promote_or_release(struct dm_bio_prison *prison,
 259                                 struct dm_bio_prison_cell *cell)
 260 {
 261         if (bio_list_empty(&cell->bios)) {
 262                 rb_erase(&cell->node, &prison->cells);
 263                 return 1;
 264         }
 265
 266         cell->holder = bio_list_pop(&cell->bios);
 267         return 0;
 268 }
 269
 270 int dm_cell_promote_or_release(struct dm_bio_prison *prison,
 271                                struct dm_bio_prison_cell *cell)
 272 {
 273         int r;
 274
 275         spin_lock_irq(&prison->lock);
 276         r = __promote_or_release(prison, cell);
 277         spin_unlock_irq(&prison->lock);
 278
 279         return r;
 280 }
 281 EXPORT_SYMBOL_GPL(dm_cell_promote_or_release);
 282
 283 /*----------------------------------------------------------------*/
 284
 285 #define DEFERRED_SET_SIZE 64
 286
 287 struct dm_deferred_entry {
 288         struct dm_deferred_set *ds;
 289         unsigned int count;
 290         struct list_head work_items;
 291 };
 292
 293 struct dm_deferred_set {
 294         spinlock_t lock;
 295         unsigned int current_entry;
 296         unsigned int sweeper;
 297         struct dm_deferred_entry entries[DEFERRED_SET_SIZE];
 298 };
 299
 300 struct dm_deferred_set *dm_deferred_set_create(void)
 301 {
 302         int i;
 303         struct dm_deferred_set *ds;
 304
 305         ds = kmalloc(sizeof(*ds), GFP_KERNEL);
 306         if (!ds)
 307                 return NULL;
 308
 309         spin_lock_init(&ds->lock);
 310         ds->current_entry = 0;
 311         ds->sweeper = 0;
 312         for (i = 0; i < DEFERRED_SET_SIZE; i++) {
 313                 ds->entries[i].ds = ds;
 314                 ds->entries[i].count = 0;
 315                 INIT_LIST_HEAD(&ds->entries[i].work_items);
 316         }
 317
 318         return ds;
 319 }
 320 EXPORT_SYMBOL_GPL(dm_deferred_set_create);
 321
 322 void dm_deferred_set_destroy(struct dm_deferred_set *ds)
 323 {
 324         kfree(ds);
 325 }
 326 EXPORT_SYMBOL_GPL(dm_deferred_set_destroy);
 327
 328 struct dm_deferred_entry *dm_deferred_entry_inc(struct dm_deferred_set *ds)
 329 {
 330         unsigned long flags;
 331         struct dm_deferred_entry *entry;
 332
 333         spin_lock_irqsave(&ds->lock, flags);
 334         entry = ds->entries + ds->current_entry;
 335         entry->count++;
 336         spin_unlock_irqrestore(&ds->lock, flags);
 337
 338         return entry;
 339 }
 340 EXPORT_SYMBOL_GPL(dm_deferred_entry_inc);
 341
 342 static unsigned int ds_next(unsigned int index)
 343 {
 344         return (index + 1) % DEFERRED_SET_SIZE;
 345 }
 346
 347 static void __sweep(struct dm_deferred_set *ds, struct list_head *head)
 348 {
 349         while ((ds->sweeper != ds->current_entry) &&
 350                !ds->entries[ds->sweeper].count) {
 351                 list_splice_init(&ds->entries[ds->sweeper].work_items, head);
 352                 ds->sweeper = ds_next(ds->sweeper);
 353         }
 354
 355         if ((ds->sweeper == ds->current_entry) && !ds->entries[ds->sweeper].count)
 356                 list_splice_init(&ds->entries[ds->sweeper].work_items, head);
 357 }
 358
 359 void dm_deferred_entry_dec(struct dm_deferred_entry *entry, struct list_head *head)
 360 {
 361         unsigned long flags;
 362
 363         spin_lock_irqsave(&entry->ds->lock, flags);
 364         BUG_ON(!entry->count);
 365         --entry->count;
 366         __sweep(entry->ds, head);
 367         spin_unlock_irqrestore(&entry->ds->lock, flags);
 368 }
 369 EXPORT_SYMBOL_GPL(dm_deferred_entry_dec);
 370
 371 /*
 372  * Returns 1 if deferred or 0 if no pending items to delay job.
 373  */
 374 int dm_deferred_set_add_work(struct dm_deferred_set *ds, struct list_head *work)
 375 {
 376         int r = 1;
 377         unsigned int next_entry;
 378
 379         spin_lock_irq(&ds->lock);
 380         if ((ds->sweeper == ds->current_entry) &&
 381             !ds->entries[ds->current_entry].count)
 382                 r = 0;
 383         else {
 384                 list_add(work, &ds->entries[ds->current_entry].work_items);
 385                 next_entry = ds_next(ds->current_entry);
 386                 if (!ds->entries[next_entry].count)
 387                         ds->current_entry = next_entry;
 388         }
 389         spin_unlock_irq(&ds->lock);
 390
 391         return r;
 392 }
 393 EXPORT_SYMBOL_GPL(dm_deferred_set_add_work);
 394
 395 /*----------------------------------------------------------------*/
 396
 397 static int __init dm_bio_prison_init_v1(void)
 398 {
 399         _cell_cache = KMEM_CACHE(dm_bio_prison_cell, 0);
 400         if (!_cell_cache)
 401                 return -ENOMEM;
 402
 403         return 0;
 404 }
 405
 406 static void dm_bio_prison_exit_v1(void)
 407 {
 408         kmem_cache_destroy(_cell_cache);
 409         _cell_cache = NULL;
 410 }
 411
 412 static int (*_inits[])(void) __initdata = {
 413         dm_bio_prison_init_v1,
 414         dm_bio_prison_init_v2,
 415 };
 416
 417 static void (*_exits[])(void) = {
 418         dm_bio_prison_exit_v1,
 419         dm_bio_prison_exit_v2,
 420 };
 421
 422 static int __init dm_bio_prison_init(void)
 423 {
 424         const int count = ARRAY_SIZE(_inits);
 425
 426         int r, i;
 427
 428         for (i = 0; i < count; i++) {
 429                 r = _inits[i]();
 430                 if (r)
 431                         goto bad;
 432         }
 433
 434         return 0;
 435
 436 bad:
 437         while (i--)
 438                 _exits[i]();
 439
 440         return r;
 441 }
 442
 443 static void __exit dm_bio_prison_exit(void)
 444 {
 445         int i = ARRAY_SIZE(_exits);
 446
 447         while (i--)
 448                 _exits[i]();
 449 }
 450
 451 /*
 452  * module hooks
 453  */
 454 module_init(dm_bio_prison_init);
 455 module_exit(dm_bio_prison_exit);
 456
 457 MODULE_DESCRIPTION(DM_NAME " bio prison");
 458 MODULE_AUTHOR("Joe Thornber <dm-devel@redhat.com>");
 459 MODULE_LICENSE("GPL");