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

0001 /*
0002  * Copyright (C) 2012-2017 Red Hat, Inc.
0003  *
0004  * This file is released under the GPL.
0005  */
0006
0007 #include "dm.h"
0008 #include "dm-bio-prison-v2.h"
0009
0010 #include <linux/spinlock.h>
0011 #include <linux/mempool.h>
0012 #include <linux/module.h>
0013 #include <linux/slab.h>
0014 #include <linux/rwsem.h>
0015
0016 /*----------------------------------------------------------------*/
0017
0018 #define MIN_CELLS 1024
0019
0020 struct dm_bio_prison_v2 {
0021     struct workqueue_struct *wq;
0022
0023     spinlock_t lock;
0024     struct rb_root cells;
0025     mempool_t cell_pool;
0026 };
0027
0028 static struct kmem_cache *_cell_cache;
0029
0030 /*----------------------------------------------------------------*/
0031
0032 /*
0033  * @nr_cells should be the number of cells you want in use _concurrently_.
0034  * Don't confuse it with the number of distinct keys.
0035  */
0036 struct dm_bio_prison_v2 *dm_bio_prison_create_v2(struct workqueue_struct *wq)
0037 {
0038     struct dm_bio_prison_v2 *prison = kzalloc(sizeof(*prison), GFP_KERNEL);
0039     int ret;
0040
0041     if (!prison)
0042         return NULL;
0043
0044     prison->wq = wq;
0045     spin_lock_init(&prison->lock);
0046
0047     ret = mempool_init_slab_pool(&prison->cell_pool, MIN_CELLS, _cell_cache);
0048     if (ret) {
0049         kfree(prison);
0050         return NULL;
0051     }
0052
0053     prison->cells = RB_ROOT;
0054
0055     return prison;
0056 }
0057 EXPORT_SYMBOL_GPL(dm_bio_prison_create_v2);
0058
0059 void dm_bio_prison_destroy_v2(struct dm_bio_prison_v2 *prison)
0060 {
0061     mempool_exit(&prison->cell_pool);
0062     kfree(prison);
0063 }
0064 EXPORT_SYMBOL_GPL(dm_bio_prison_destroy_v2);
0065
0066 struct dm_bio_prison_cell_v2 *dm_bio_prison_alloc_cell_v2(struct dm_bio_prison_v2 *prison, gfp_t gfp)
0067 {
0068     return mempool_alloc(&prison->cell_pool, gfp);
0069 }
0070 EXPORT_SYMBOL_GPL(dm_bio_prison_alloc_cell_v2);
0071
0072 void dm_bio_prison_free_cell_v2(struct dm_bio_prison_v2 *prison,
0073                 struct dm_bio_prison_cell_v2 *cell)
0074 {
0075     mempool_free(cell, &prison->cell_pool);
0076 }
0077 EXPORT_SYMBOL_GPL(dm_bio_prison_free_cell_v2);
0078
0079 static void __setup_new_cell(struct dm_cell_key_v2 *key,
0080                  struct dm_bio_prison_cell_v2 *cell)
0081 {
0082     memset(cell, 0, sizeof(*cell));
0083     memcpy(&cell->key, key, sizeof(cell->key));
0084     bio_list_init(&cell->bios);
0085 }
0086
0087 static int cmp_keys(struct dm_cell_key_v2 *lhs,
0088             struct dm_cell_key_v2 *rhs)
0089 {
0090     if (lhs->virtual < rhs->virtual)
0091         return -1;
0092
0093     if (lhs->virtual > rhs->virtual)
0094         return 1;
0095
0096     if (lhs->dev < rhs->dev)
0097         return -1;
0098
0099     if (lhs->dev > rhs->dev)
0100         return 1;
0101
0102     if (lhs->block_end <= rhs->block_begin)
0103         return -1;
0104
0105     if (lhs->block_begin >= rhs->block_end)
0106         return 1;
0107
0108     return 0;
0109 }
0110
0111 /*
0112  * Returns true if node found, otherwise it inserts a new one.
0113  */
0114 static bool __find_or_insert(struct dm_bio_prison_v2 *prison,
0115                  struct dm_cell_key_v2 *key,
0116                  struct dm_bio_prison_cell_v2 *cell_prealloc,
0117                  struct dm_bio_prison_cell_v2 **result)
0118 {
0119     int r;
0120     struct rb_node **new = &prison->cells.rb_node, *parent = NULL;
0121
0122     while (*new) {
0123         struct dm_bio_prison_cell_v2 *cell =
0124             rb_entry(*new, struct dm_bio_prison_cell_v2, node);
0125
0126         r = cmp_keys(key, &cell->key);
0127
0128         parent = *new;
0129         if (r < 0)
0130             new = &((*new)->rb_left);
0131
0132         else if (r > 0)
0133             new = &((*new)->rb_right);
0134
0135         else {
0136             *result = cell;
0137             return true;
0138         }
0139     }
0140
0141     __setup_new_cell(key, cell_prealloc);
0142     *result = cell_prealloc;
0143     rb_link_node(&cell_prealloc->node, parent, new);
0144     rb_insert_color(&cell_prealloc->node, &prison->cells);
0145
0146     return false;
0147 }
0148
0149 static bool __get(struct dm_bio_prison_v2 *prison,
0150           struct dm_cell_key_v2 *key,
0151           unsigned lock_level,
0152           struct bio *inmate,
0153           struct dm_bio_prison_cell_v2 *cell_prealloc,
0154           struct dm_bio_prison_cell_v2 **cell)
0155 {
0156     if (__find_or_insert(prison, key, cell_prealloc, cell)) {
0157         if ((*cell)->exclusive_lock) {
0158             if (lock_level <= (*cell)->exclusive_level) {
0159                 bio_list_add(&(*cell)->bios, inmate);
0160                 return false;
0161             }
0162         }
0163
0164         (*cell)->shared_count++;
0165
0166     } else
0167         (*cell)->shared_count = 1;
0168
0169     return true;
0170 }
0171
0172 bool dm_cell_get_v2(struct dm_bio_prison_v2 *prison,
0173             struct dm_cell_key_v2 *key,
0174             unsigned lock_level,
0175             struct bio *inmate,
0176             struct dm_bio_prison_cell_v2 *cell_prealloc,
0177             struct dm_bio_prison_cell_v2 **cell_result)
0178 {
0179     int r;
0180
0181     spin_lock_irq(&prison->lock);
0182     r = __get(prison, key, lock_level, inmate, cell_prealloc, cell_result);
0183     spin_unlock_irq(&prison->lock);
0184
0185     return r;
0186 }
0187 EXPORT_SYMBOL_GPL(dm_cell_get_v2);
0188
0189 static bool __put(struct dm_bio_prison_v2 *prison,
0190           struct dm_bio_prison_cell_v2 *cell)
0191 {
0192     BUG_ON(!cell->shared_count);
0193     cell->shared_count--;
0194
0195     // FIXME: shared locks granted above the lock level could starve this
0196     if (!cell->shared_count) {
0197         if (cell->exclusive_lock){
0198             if (cell->quiesce_continuation) {
0199                 queue_work(prison->wq, cell->quiesce_continuation);
0200                 cell->quiesce_continuation = NULL;
0201             }
0202         } else {
0203             rb_erase(&cell->node, &prison->cells);
0204             return true;
0205         }
0206     }
0207
0208     return false;
0209 }
0210
0211 bool dm_cell_put_v2(struct dm_bio_prison_v2 *prison,
0212             struct dm_bio_prison_cell_v2 *cell)
0213 {
0214     bool r;
0215     unsigned long flags;
0216
0217     spin_lock_irqsave(&prison->lock, flags);
0218     r = __put(prison, cell);
0219     spin_unlock_irqrestore(&prison->lock, flags);
0220
0221     return r;
0222 }
0223 EXPORT_SYMBOL_GPL(dm_cell_put_v2);
0224
0225 static int __lock(struct dm_bio_prison_v2 *prison,
0226           struct dm_cell_key_v2 *key,
0227           unsigned lock_level,
0228           struct dm_bio_prison_cell_v2 *cell_prealloc,
0229           struct dm_bio_prison_cell_v2 **cell_result)
0230 {
0231     struct dm_bio_prison_cell_v2 *cell;
0232
0233     if (__find_or_insert(prison, key, cell_prealloc, &cell)) {
0234         if (cell->exclusive_lock)
0235             return -EBUSY;
0236
0237         cell->exclusive_lock = true;
0238         cell->exclusive_level = lock_level;
0239         *cell_result = cell;
0240
0241         // FIXME: we don't yet know what level these shared locks
0242         // were taken at, so have to quiesce them all.
0243         return cell->shared_count > 0;
0244
0245     } else {
0246         cell = cell_prealloc;
0247         cell->shared_count = 0;
0248         cell->exclusive_lock = true;
0249         cell->exclusive_level = lock_level;
0250         *cell_result = cell;
0251     }
0252
0253     return 0;
0254 }
0255
0256 int dm_cell_lock_v2(struct dm_bio_prison_v2 *prison,
0257             struct dm_cell_key_v2 *key,
0258             unsigned lock_level,
0259             struct dm_bio_prison_cell_v2 *cell_prealloc,
0260             struct dm_bio_prison_cell_v2 **cell_result)
0261 {
0262     int r;
0263
0264     spin_lock_irq(&prison->lock);
0265     r = __lock(prison, key, lock_level, cell_prealloc, cell_result);
0266     spin_unlock_irq(&prison->lock);
0267
0268     return r;
0269 }
0270 EXPORT_SYMBOL_GPL(dm_cell_lock_v2);
0271
0272 static void __quiesce(struct dm_bio_prison_v2 *prison,
0273               struct dm_bio_prison_cell_v2 *cell,
0274               struct work_struct *continuation)
0275 {
0276     if (!cell->shared_count)
0277         queue_work(prison->wq, continuation);
0278     else
0279         cell->quiesce_continuation = continuation;
0280 }
0281
0282 void dm_cell_quiesce_v2(struct dm_bio_prison_v2 *prison,
0283             struct dm_bio_prison_cell_v2 *cell,
0284             struct work_struct *continuation)
0285 {
0286     spin_lock_irq(&prison->lock);
0287     __quiesce(prison, cell, continuation);
0288     spin_unlock_irq(&prison->lock);
0289 }
0290 EXPORT_SYMBOL_GPL(dm_cell_quiesce_v2);
0291
0292 static int __promote(struct dm_bio_prison_v2 *prison,
0293              struct dm_bio_prison_cell_v2 *cell,
0294              unsigned new_lock_level)
0295 {
0296     if (!cell->exclusive_lock)
0297         return -EINVAL;
0298
0299     cell->exclusive_level = new_lock_level;
0300     return cell->shared_count > 0;
0301 }
0302
0303 int dm_cell_lock_promote_v2(struct dm_bio_prison_v2 *prison,
0304                 struct dm_bio_prison_cell_v2 *cell,
0305                 unsigned new_lock_level)
0306 {
0307     int r;
0308
0309     spin_lock_irq(&prison->lock);
0310     r = __promote(prison, cell, new_lock_level);
0311     spin_unlock_irq(&prison->lock);
0312
0313     return r;
0314 }
0315 EXPORT_SYMBOL_GPL(dm_cell_lock_promote_v2);
0316
0317 static bool __unlock(struct dm_bio_prison_v2 *prison,
0318              struct dm_bio_prison_cell_v2 *cell,
0319              struct bio_list *bios)
0320 {
0321     BUG_ON(!cell->exclusive_lock);
0322
0323     bio_list_merge(bios, &cell->bios);
0324     bio_list_init(&cell->bios);
0325
0326     if (cell->shared_count) {
0327         cell->exclusive_lock = false;
0328         return false;
0329     }
0330
0331     rb_erase(&cell->node, &prison->cells);
0332     return true;
0333 }
0334
0335 bool dm_cell_unlock_v2(struct dm_bio_prison_v2 *prison,
0336                struct dm_bio_prison_cell_v2 *cell,
0337                struct bio_list *bios)
0338 {
0339     bool r;
0340
0341     spin_lock_irq(&prison->lock);
0342     r = __unlock(prison, cell, bios);
0343     spin_unlock_irq(&prison->lock);
0344
0345     return r;
0346 }
0347 EXPORT_SYMBOL_GPL(dm_cell_unlock_v2);
0348
0349 /*----------------------------------------------------------------*/
0350
0351 int __init dm_bio_prison_init_v2(void)
0352 {
0353     _cell_cache = KMEM_CACHE(dm_bio_prison_cell_v2, 0);
0354     if (!_cell_cache)
0355         return -ENOMEM;
0356
0357     return 0;
0358 }
0359
0360 void dm_bio_prison_exit_v2(void)
0361 {
0362     kmem_cache_destroy(_cell_cache);
0363     _cell_cache = NULL;
0364 }