linux/drivers/md/dm-bio-prison.c
<<
>>
Prefs
   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
  17struct 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
  28static 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
  41static 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 */
  47struct 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}
  73EXPORT_SYMBOL_GPL(dm_bio_prison_create);
  74
  75void dm_bio_prison_destroy(struct dm_bio_prison *prison)
  76{
  77        mempool_destroy(prison->cell_pool);
  78        kfree(prison);
  79}
  80EXPORT_SYMBOL_GPL(dm_bio_prison_destroy);
  81
  82struct 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}
  86EXPORT_SYMBOL_GPL(dm_bio_prison_alloc_cell);
  87
  88void 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}
  93EXPORT_SYMBOL_GPL(dm_bio_prison_free_cell);
  94
  95static 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
 103static 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
 110static 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
 122static 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
 134static 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
 156static 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
 172int 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}
 180EXPORT_SYMBOL_GPL(dm_bio_detain);
 181
 182int 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}
 189EXPORT_SYMBOL_GPL(dm_get_cell);
 190
 191/*
 192 * @inmates must have been initialised prior to this call
 193 */
 194static 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
 206void 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}
 216EXPORT_SYMBOL_GPL(dm_cell_release);
 217
 218/*
 219 * Sometimes we don't want the holder, just the additional bios.
 220 */
 221static 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
 228void 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}
 238EXPORT_SYMBOL_GPL(dm_cell_release_no_holder);
 239
 240void 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}
 256EXPORT_SYMBOL_GPL(dm_cell_error);
 257
 258/*----------------------------------------------------------------*/
 259
 260#define DEFERRED_SET_SIZE 64
 261
 262struct dm_deferred_entry {
 263        struct dm_deferred_set *ds;
 264        unsigned count;
 265        struct list_head work_items;
 266};
 267
 268struct 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
 275struct 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}
 295EXPORT_SYMBOL_GPL(dm_deferred_set_create);
 296
 297void dm_deferred_set_destroy(struct dm_deferred_set *ds)
 298{
 299        kfree(ds);
 300}
 301EXPORT_SYMBOL_GPL(dm_deferred_set_destroy);
 302
 303struct 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}
 315EXPORT_SYMBOL_GPL(dm_deferred_entry_inc);
 316
 317static unsigned ds_next(unsigned index)
 318{
 319        return (index + 1) % DEFERRED_SET_SIZE;
 320}
 321
 322static 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
 334void 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}
 344EXPORT_SYMBOL_GPL(dm_deferred_entry_dec);
 345
 346/*
 347 * Returns 1 if deferred or 0 if no pending items to delay job.
 348 */
 349int 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}
 369EXPORT_SYMBOL_GPL(dm_deferred_set_add_work);
 370
 371/*----------------------------------------------------------------*/
 372
 373static 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
 382static 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 */
 391module_init(dm_bio_prison_init);
 392module_exit(dm_bio_prison_exit);
 393
 394MODULE_DESCRIPTION(DM_NAME " bio prison");
 395MODULE_AUTHOR("Joe Thornber <dm-devel@redhat.com>");
 396MODULE_LICENSE("GPL");
 397
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.