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

0001 /*
0002  * Copyright (C) 2012 Red Hat, Inc.
0003  *
0004  * This file is released under the GPL.
0005  */
0006
0007 #include "dm.h"
0008 #include "dm-bio-prison-v1.h"
0009 #include "dm-bio-prison-v2.h"
0010
0011 #include <linux/spinlock.h>
0012 #include <linux/mempool.h>
0013 #include <linux/module.h>
0014 #include <linux/slab.h>
0015
0016 /*----------------------------------------------------------------*/
0017
0018 #define MIN_CELLS 1024
0019
0020 struct dm_bio_prison {
0021     spinlock_t lock;
0022     struct rb_root cells;
0023     mempool_t cell_pool;
0024 };
0025
0026 static struct kmem_cache *_cell_cache;
0027
0028 /*----------------------------------------------------------------*/
0029
0030 /*
0031  * @nr_cells should be the number of cells you want in use _concurrently_.
0032  * Don't confuse it with the number of distinct keys.
0033  */
0034 struct dm_bio_prison *dm_bio_prison_create(void)
0035 {
0036     struct dm_bio_prison *prison = kzalloc(sizeof(*prison), GFP_KERNEL);
0037     int ret;
0038
0039     if (!prison)
0040         return NULL;
0041
0042     spin_lock_init(&prison->lock);
0043
0044     ret = mempool_init_slab_pool(&prison->cell_pool, MIN_CELLS, _cell_cache);
0045     if (ret) {
0046         kfree(prison);
0047         return NULL;
0048     }
0049
0050     prison->cells = RB_ROOT;
0051
0052     return prison;
0053 }
0054 EXPORT_SYMBOL_GPL(dm_bio_prison_create);
0055
0056 void dm_bio_prison_destroy(struct dm_bio_prison *prison)
0057 {
0058     mempool_exit(&prison->cell_pool);
0059     kfree(prison);
0060 }
0061 EXPORT_SYMBOL_GPL(dm_bio_prison_destroy);
0062
0063 struct dm_bio_prison_cell *dm_bio_prison_alloc_cell(struct dm_bio_prison *prison, gfp_t gfp)
0064 {
0065     return mempool_alloc(&prison->cell_pool, gfp);
0066 }
0067 EXPORT_SYMBOL_GPL(dm_bio_prison_alloc_cell);
0068
0069 void dm_bio_prison_free_cell(struct dm_bio_prison *prison,
0070                  struct dm_bio_prison_cell *cell)
0071 {
0072     mempool_free(cell, &prison->cell_pool);
0073 }
0074 EXPORT_SYMBOL_GPL(dm_bio_prison_free_cell);
0075
0076 static void __setup_new_cell(struct dm_cell_key *key,
0077                  struct bio *holder,
0078                  struct dm_bio_prison_cell *cell)
0079 {
0080        memcpy(&cell->key, key, sizeof(cell->key));
0081        cell->holder = holder;
0082        bio_list_init(&cell->bios);
0083 }
0084
0085 static int cmp_keys(struct dm_cell_key *lhs,
0086             struct dm_cell_key *rhs)
0087 {
0088     if (lhs->virtual < rhs->virtual)
0089         return -1;
0090
0091     if (lhs->virtual > rhs->virtual)
0092         return 1;
0093
0094     if (lhs->dev < rhs->dev)
0095         return -1;
0096
0097     if (lhs->dev > rhs->dev)
0098         return 1;
0099
0100     if (lhs->block_end <= rhs->block_begin)
0101         return -1;
0102
0103     if (lhs->block_begin >= rhs->block_end)
0104         return 1;
0105
0106     return 0;
0107 }
0108
0109 static int __bio_detain(struct dm_bio_prison *prison,
0110             struct dm_cell_key *key,
0111             struct bio *inmate,
0112             struct dm_bio_prison_cell *cell_prealloc,
0113             struct dm_bio_prison_cell **cell_result)
0114 {
0115     int r;
0116     struct rb_node **new = &prison->cells.rb_node, *parent = NULL;
0117
0118     while (*new) {
0119         struct dm_bio_prison_cell *cell =
0120             rb_entry(*new, struct dm_bio_prison_cell, node);
0121
0122         r = cmp_keys(key, &cell->key);
0123
0124         parent = *new;
0125         if (r < 0)
0126             new = &((*new)->rb_left);
0127         else if (r > 0)
0128             new = &((*new)->rb_right);
0129         else {
0130             if (inmate)
0131                 bio_list_add(&cell->bios, inmate);
0132             *cell_result = cell;
0133             return 1;
0134         }
0135     }
0136
0137     __setup_new_cell(key, inmate, cell_prealloc);
0138     *cell_result = cell_prealloc;
0139
0140     rb_link_node(&cell_prealloc->node, parent, new);
0141     rb_insert_color(&cell_prealloc->node, &prison->cells);
0142
0143     return 0;
0144 }
0145
0146 static int bio_detain(struct dm_bio_prison *prison,
0147               struct dm_cell_key *key,
0148               struct bio *inmate,
0149               struct dm_bio_prison_cell *cell_prealloc,
0150               struct dm_bio_prison_cell **cell_result)
0151 {
0152     int r;
0153
0154     spin_lock_irq(&prison->lock);
0155     r = __bio_detain(prison, key, inmate, cell_prealloc, cell_result);
0156     spin_unlock_irq(&prison->lock);
0157
0158     return r;
0159 }
0160
0161 int dm_bio_detain(struct dm_bio_prison *prison,
0162           struct dm_cell_key *key,
0163           struct bio *inmate,
0164           struct dm_bio_prison_cell *cell_prealloc,
0165           struct dm_bio_prison_cell **cell_result)
0166 {
0167     return bio_detain(prison, key, inmate, cell_prealloc, cell_result);
0168 }
0169 EXPORT_SYMBOL_GPL(dm_bio_detain);
0170
0171 int dm_get_cell(struct dm_bio_prison *prison,
0172         struct dm_cell_key *key,
0173         struct dm_bio_prison_cell *cell_prealloc,
0174         struct dm_bio_prison_cell **cell_result)
0175 {
0176     return bio_detain(prison, key, NULL, cell_prealloc, cell_result);
0177 }
0178 EXPORT_SYMBOL_GPL(dm_get_cell);
0179
0180 /*
0181  * @inmates must have been initialised prior to this call
0182  */
0183 static void __cell_release(struct dm_bio_prison *prison,
0184                struct dm_bio_prison_cell *cell,
0185                struct bio_list *inmates)
0186 {
0187     rb_erase(&cell->node, &prison->cells);
0188
0189     if (inmates) {
0190         if (cell->holder)
0191             bio_list_add(inmates, cell->holder);
0192         bio_list_merge(inmates, &cell->bios);
0193     }
0194 }
0195
0196 void dm_cell_release(struct dm_bio_prison *prison,
0197              struct dm_bio_prison_cell *cell,
0198              struct bio_list *bios)
0199 {
0200     spin_lock_irq(&prison->lock);
0201     __cell_release(prison, cell, bios);
0202     spin_unlock_irq(&prison->lock);
0203 }
0204 EXPORT_SYMBOL_GPL(dm_cell_release);
0205
0206 /*
0207  * Sometimes we don't want the holder, just the additional bios.
0208  */
0209 static void __cell_release_no_holder(struct dm_bio_prison *prison,
0210                      struct dm_bio_prison_cell *cell,
0211                      struct bio_list *inmates)
0212 {
0213     rb_erase(&cell->node, &prison->cells);
0214     bio_list_merge(inmates, &cell->bios);
0215 }
0216
0217 void dm_cell_release_no_holder(struct dm_bio_prison *prison,
0218                    struct dm_bio_prison_cell *cell,
0219                    struct bio_list *inmates)
0220 {
0221     unsigned long flags;
0222
0223     spin_lock_irqsave(&prison->lock, flags);
0224     __cell_release_no_holder(prison, cell, inmates);
0225     spin_unlock_irqrestore(&prison->lock, flags);
0226 }
0227 EXPORT_SYMBOL_GPL(dm_cell_release_no_holder);
0228
0229 void dm_cell_error(struct dm_bio_prison *prison,
0230            struct dm_bio_prison_cell *cell, blk_status_t error)
0231 {
0232     struct bio_list bios;
0233     struct bio *bio;
0234
0235     bio_list_init(&bios);
0236     dm_cell_release(prison, cell, &bios);
0237
0238     while ((bio = bio_list_pop(&bios))) {
0239         bio->bi_status = error;
0240         bio_endio(bio);
0241     }
0242 }
0243 EXPORT_SYMBOL_GPL(dm_cell_error);
0244
0245 void dm_cell_visit_release(struct dm_bio_prison *prison,
0246                void (*visit_fn)(void *, struct dm_bio_prison_cell *),
0247                void *context,
0248                struct dm_bio_prison_cell *cell)
0249 {
0250     spin_lock_irq(&prison->lock);
0251     visit_fn(context, cell);
0252     rb_erase(&cell->node, &prison->cells);
0253     spin_unlock_irq(&prison->lock);
0254 }
0255 EXPORT_SYMBOL_GPL(dm_cell_visit_release);
0256
0257 static int __promote_or_release(struct dm_bio_prison *prison,
0258                 struct dm_bio_prison_cell *cell)
0259 {
0260     if (bio_list_empty(&cell->bios)) {
0261         rb_erase(&cell->node, &prison->cells);
0262         return 1;
0263     }
0264
0265     cell->holder = bio_list_pop(&cell->bios);
0266     return 0;
0267 }
0268
0269 int dm_cell_promote_or_release(struct dm_bio_prison *prison,
0270                    struct dm_bio_prison_cell *cell)
0271 {
0272     int r;
0273
0274     spin_lock_irq(&prison->lock);
0275     r = __promote_or_release(prison, cell);
0276     spin_unlock_irq(&prison->lock);
0277
0278     return r;
0279 }
0280 EXPORT_SYMBOL_GPL(dm_cell_promote_or_release);
0281
0282 /*----------------------------------------------------------------*/
0283
0284 #define DEFERRED_SET_SIZE 64
0285
0286 struct dm_deferred_entry {
0287     struct dm_deferred_set *ds;
0288     unsigned count;
0289     struct list_head work_items;
0290 };
0291
0292 struct dm_deferred_set {
0293     spinlock_t lock;
0294     unsigned current_entry;
0295     unsigned sweeper;
0296     struct dm_deferred_entry entries[DEFERRED_SET_SIZE];
0297 };
0298
0299 struct dm_deferred_set *dm_deferred_set_create(void)
0300 {
0301     int i;
0302     struct dm_deferred_set *ds;
0303
0304     ds = kmalloc(sizeof(*ds), GFP_KERNEL);
0305     if (!ds)
0306         return NULL;
0307
0308     spin_lock_init(&ds->lock);
0309     ds->current_entry = 0;
0310     ds->sweeper = 0;
0311     for (i = 0; i < DEFERRED_SET_SIZE; i++) {
0312         ds->entries[i].ds = ds;
0313         ds->entries[i].count = 0;
0314         INIT_LIST_HEAD(&ds->entries[i].work_items);
0315     }
0316
0317     return ds;
0318 }
0319 EXPORT_SYMBOL_GPL(dm_deferred_set_create);
0320
0321 void dm_deferred_set_destroy(struct dm_deferred_set *ds)
0322 {
0323     kfree(ds);
0324 }
0325 EXPORT_SYMBOL_GPL(dm_deferred_set_destroy);
0326
0327 struct dm_deferred_entry *dm_deferred_entry_inc(struct dm_deferred_set *ds)
0328 {
0329     unsigned long flags;
0330     struct dm_deferred_entry *entry;
0331
0332     spin_lock_irqsave(&ds->lock, flags);
0333     entry = ds->entries + ds->current_entry;
0334     entry->count++;
0335     spin_unlock_irqrestore(&ds->lock, flags);
0336
0337     return entry;
0338 }
0339 EXPORT_SYMBOL_GPL(dm_deferred_entry_inc);
0340
0341 static unsigned ds_next(unsigned index)
0342 {
0343     return (index + 1) % DEFERRED_SET_SIZE;
0344 }
0345
0346 static void __sweep(struct dm_deferred_set *ds, struct list_head *head)
0347 {
0348     while ((ds->sweeper != ds->current_entry) &&
0349            !ds->entries[ds->sweeper].count) {
0350         list_splice_init(&ds->entries[ds->sweeper].work_items, head);
0351         ds->sweeper = ds_next(ds->sweeper);
0352     }
0353
0354     if ((ds->sweeper == ds->current_entry) && !ds->entries[ds->sweeper].count)
0355         list_splice_init(&ds->entries[ds->sweeper].work_items, head);
0356 }
0357
0358 void dm_deferred_entry_dec(struct dm_deferred_entry *entry, struct list_head *head)
0359 {
0360     unsigned long flags;
0361
0362     spin_lock_irqsave(&entry->ds->lock, flags);
0363     BUG_ON(!entry->count);
0364     --entry->count;
0365     __sweep(entry->ds, head);
0366     spin_unlock_irqrestore(&entry->ds->lock, flags);
0367 }
0368 EXPORT_SYMBOL_GPL(dm_deferred_entry_dec);
0369
0370 /*
0371  * Returns 1 if deferred or 0 if no pending items to delay job.
0372  */
0373 int dm_deferred_set_add_work(struct dm_deferred_set *ds, struct list_head *work)
0374 {
0375     int r = 1;
0376     unsigned next_entry;
0377
0378     spin_lock_irq(&ds->lock);
0379     if ((ds->sweeper == ds->current_entry) &&
0380         !ds->entries[ds->current_entry].count)
0381         r = 0;
0382     else {
0383         list_add(work, &ds->entries[ds->current_entry].work_items);
0384         next_entry = ds_next(ds->current_entry);
0385         if (!ds->entries[next_entry].count)
0386             ds->current_entry = next_entry;
0387     }
0388     spin_unlock_irq(&ds->lock);
0389
0390     return r;
0391 }
0392 EXPORT_SYMBOL_GPL(dm_deferred_set_add_work);
0393
0394 /*----------------------------------------------------------------*/
0395
0396 static int __init dm_bio_prison_init_v1(void)
0397 {
0398     _cell_cache = KMEM_CACHE(dm_bio_prison_cell, 0);
0399     if (!_cell_cache)
0400         return -ENOMEM;
0401
0402     return 0;
0403 }
0404
0405 static void dm_bio_prison_exit_v1(void)
0406 {
0407     kmem_cache_destroy(_cell_cache);
0408     _cell_cache = NULL;
0409 }
0410
0411 static int (*_inits[])(void) __initdata = {
0412     dm_bio_prison_init_v1,
0413     dm_bio_prison_init_v2,
0414 };
0415
0416 static void (*_exits[])(void) = {
0417     dm_bio_prison_exit_v1,
0418     dm_bio_prison_exit_v2,
0419 };
0420
0421 static int __init dm_bio_prison_init(void)
0422 {
0423     const int count = ARRAY_SIZE(_inits);
0424
0425     int r, i;
0426
0427     for (i = 0; i < count; i++) {
0428         r = _inits[i]();
0429         if (r)
0430             goto bad;
0431     }
0432
0433     return 0;
0434
0435       bad:
0436     while (i--)
0437         _exits[i]();
0438
0439     return r;
0440 }
0441
0442 static void __exit dm_bio_prison_exit(void)
0443 {
0444     int i = ARRAY_SIZE(_exits);
0445
0446     while (i--)
0447         _exits[i]();
0448 }
0449
0450 /*
0451  * module hooks
0452  */
0453 module_init(dm_bio_prison_init);
0454 module_exit(dm_bio_prison_exit);
0455
0456 MODULE_DESCRIPTION(DM_NAME " bio prison");
0457 MODULE_AUTHOR("Joe Thornber <dm-devel@redhat.com>");
0458 MODULE_LICENSE("GPL");