drivers/md/dm-bio-prison.c

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