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