1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * Copyright (C) 2012 Red Hat, Inc. 4 * 5 * This file is released under the GPL. 6 */ 7 8 #include "dm.h" 9 #include "dm-bio-prison-v1.h" 10 #include "dm-bio-prison-v2.h" 11 12 #include <linux/spinlock.h> 13 #include <linux/mempool.h> 14 #include <linux/module.h> 15 #include <linux/slab.h> 16 17 /*----------------------------------------------------------------*/ 18 19 #define NR_LOCKS 64 20 #define MIN_CELLS 1024 21 22 struct prison_region { 23 spinlock_t lock; 24 struct rb_root cell; 25 } ____cacheline_aligned_in_smp; 26 27 struct dm_bio_prison { 28 mempool_t cell_pool; 29 unsigned int num_locks; 30 struct prison_region regions[NR_LOCKS]; 31 }; 32 33 static struct kmem_cache *_cell_cache; 34 35 /*----------------------------------------------------------------*/ 36 37 /* 38 * @nr_cells should be the number of cells you want in use _concurrently_. 39 * Don't confuse it with the number of distinct keys. 40 */ 41 struct dm_bio_prison *dm_bio_prison_create(void) 42 { 43 int ret; 44 unsigned i; 45 struct dm_bio_prison *prison = kzalloc(sizeof(*prison), GFP_KERNEL); 46 47 if (!prison) 48 return NULL; 49 prison->num_locks = NR_LOCKS; 50 51 for (i = 0; i < prison->num_locks; i++) { 52 spin_lock_init(&prison->regions[i].lock); 53 prison->regions[i].cell = RB_ROOT; 54 } 55 56 ret = mempool_init_slab_pool(&prison->cell_pool, MIN_CELLS, _cell_cache); 57 if (ret) { 58 kfree(prison); 59 return NULL; 60 } 61 62 return prison; 63 } 64 EXPORT_SYMBOL_GPL(dm_bio_prison_create); 65 66 void dm_bio_prison_destroy(struct dm_bio_prison *prison) 67 { 68 mempool_exit(&prison->cell_pool); 69 kfree(prison); 70 } 71 EXPORT_SYMBOL_GPL(dm_bio_prison_destroy); 72 73 struct dm_bio_prison_cell *dm_bio_prison_alloc_cell(struct dm_bio_prison *prison, gfp_t gfp) 74 { 75 return mempool_alloc(&prison->cell_pool, gfp); 76 } 77 EXPORT_SYMBOL_GPL(dm_bio_prison_alloc_cell); 78 79 void dm_bio_prison_free_cell(struct dm_bio_prison *prison, 80 struct dm_bio_prison_cell *cell) 81 { 82 mempool_free(cell, &prison->cell_pool); 83 } 84 EXPORT_SYMBOL_GPL(dm_bio_prison_free_cell); 85 86 static void __setup_new_cell(struct dm_cell_key *key, 87 struct bio *holder, 88 struct dm_bio_prison_cell *cell) 89 { 90 memcpy(&cell->key, key, sizeof(cell->key)); 91 cell->holder = holder; 92 bio_list_init(&cell->bios); 93 } 94 95 static int cmp_keys(struct dm_cell_key *lhs, 96 struct dm_cell_key *rhs) 97 { 98 if (lhs->virtual < rhs->virtual) 99 return -1; 100 101 if (lhs->virtual > rhs->virtual) 102 return 1; 103 104 if (lhs->dev < rhs->dev) 105 return -1; 106 107 if (lhs->dev > rhs->dev) 108 return 1; 109 110 if (lhs->block_end <= rhs->block_begin) 111 return -1; 112 113 if (lhs->block_begin >= rhs->block_end) 114 return 1; 115 116 return 0; 117 } 118 119 static unsigned lock_nr(struct dm_cell_key *key, unsigned int num_locks) 120 { 121 return (key->block_begin >> BIO_PRISON_MAX_RANGE_SHIFT) & (num_locks - 1); 122 } 123 124 bool dm_cell_key_has_valid_range(struct dm_cell_key *key) 125 { 126 if (WARN_ON_ONCE(key->block_end - key->block_begin > BIO_PRISON_MAX_RANGE)) 127 return false; 128 if (WARN_ON_ONCE((key->block_begin >> BIO_PRISON_MAX_RANGE_SHIFT) != 129 (key->block_end - 1) >> BIO_PRISON_MAX_RANGE_SHIFT)) 130 return false; 131 132 return true; 133 } 134 EXPORT_SYMBOL(dm_cell_key_has_valid_range); 135 136 static int __bio_detain(struct rb_root *root, 137 struct dm_cell_key *key, 138 struct bio *inmate, 139 struct dm_bio_prison_cell *cell_prealloc, 140 struct dm_bio_prison_cell **cell_result) 141 { 142 int r; 143 struct rb_node **new = &root->rb_node, *parent = NULL; 144 145 while (*new) { 146 struct dm_bio_prison_cell *cell = 147 rb_entry(*new, struct dm_bio_prison_cell, node); 148 149 r = cmp_keys(key, &cell->key); 150 151 parent = *new; 152 if (r < 0) 153 new = &((*new)->rb_left); 154 else if (r > 0) 155 new = &((*new)->rb_right); 156 else { 157 if (inmate) 158 bio_list_add(&cell->bios, inmate); 159 *cell_result = cell; 160 return 1; 161 } 162 } 163 164 __setup_new_cell(key, inmate, cell_prealloc); 165 *cell_result = cell_prealloc; 166 167 rb_link_node(&cell_prealloc->node, parent, new); 168 rb_insert_color(&cell_prealloc->node, root); 169 170 return 0; 171 } 172 173 static int bio_detain(struct dm_bio_prison *prison, 174 struct dm_cell_key *key, 175 struct bio *inmate, 176 struct dm_bio_prison_cell *cell_prealloc, 177 struct dm_bio_prison_cell **cell_result) 178 { 179 int r; 180 unsigned l = lock_nr(key, prison->num_locks); 181 182 spin_lock_irq(&prison->regions[l].lock); 183 r = __bio_detain(&prison->regions[l].cell, key, inmate, cell_prealloc, cell_result); 184 spin_unlock_irq(&prison->regions[l].lock); 185 186 return r; 187 } 188 189 int dm_bio_detain(struct dm_bio_prison *prison, 190 struct dm_cell_key *key, 191 struct bio *inmate, 192 struct dm_bio_prison_cell *cell_prealloc, 193 struct dm_bio_prison_cell **cell_result) 194 { 195 return bio_detain(prison, key, inmate, cell_prealloc, cell_result); 196 } 197 EXPORT_SYMBOL_GPL(dm_bio_detain); 198 199 int dm_get_cell(struct dm_bio_prison *prison, 200 struct dm_cell_key *key, 201 struct dm_bio_prison_cell *cell_prealloc, 202 struct dm_bio_prison_cell **cell_result) 203 { 204 return bio_detain(prison, key, NULL, cell_prealloc, cell_result); 205 } 206 EXPORT_SYMBOL_GPL(dm_get_cell); 207 208 /* 209 * @inmates must have been initialised prior to this call 210 */ 211 static void __cell_release(struct rb_root *root, 212 struct dm_bio_prison_cell *cell, 213 struct bio_list *inmates) 214 { 215 rb_erase(&cell->node, root); 216 217 if (inmates) { 218 if (cell->holder) 219 bio_list_add(inmates, cell->holder); 220 bio_list_merge(inmates, &cell->bios); 221 } 222 } 223 224 void dm_cell_release(struct dm_bio_prison *prison, 225 struct dm_bio_prison_cell *cell, 226 struct bio_list *bios) 227 { 228 unsigned l = lock_nr(&cell->key, prison->num_locks); 229 230 spin_lock_irq(&prison->regions[l].lock); 231 __cell_release(&prison->regions[l].cell, cell, bios); 232 spin_unlock_irq(&prison->regions[l].lock); 233 } 234 EXPORT_SYMBOL_GPL(dm_cell_release); 235 236 /* 237 * Sometimes we don't want the holder, just the additional bios. 238 */ 239 static void __cell_release_no_holder(struct rb_root *root, 240 struct dm_bio_prison_cell *cell, 241 struct bio_list *inmates) 242 { 243 rb_erase(&cell->node, root); 244 bio_list_merge(inmates, &cell->bios); 245 } 246 247 void dm_cell_release_no_holder(struct dm_bio_prison *prison, 248 struct dm_bio_prison_cell *cell, 249 struct bio_list *inmates) 250 { 251 unsigned l = lock_nr(&cell->key, prison->num_locks); 252 unsigned long flags; 253 254 spin_lock_irqsave(&prison->regions[l].lock, flags); 255 __cell_release_no_holder(&prison->regions[l].cell, cell, inmates); 256 spin_unlock_irqrestore(&prison->regions[l].lock, flags); 257 } 258 EXPORT_SYMBOL_GPL(dm_cell_release_no_holder); 259 260 void dm_cell_error(struct dm_bio_prison *prison, 261 struct dm_bio_prison_cell *cell, blk_status_t error) 262 { 263 struct bio_list bios; 264 struct bio *bio; 265 266 bio_list_init(&bios); 267 dm_cell_release(prison, cell, &bios); 268 269 while ((bio = bio_list_pop(&bios))) { 270 bio->bi_status = error; 271 bio_endio(bio); 272 } 273 } 274 EXPORT_SYMBOL_GPL(dm_cell_error); 275 276 void dm_cell_visit_release(struct dm_bio_prison *prison, 277 void (*visit_fn)(void *, struct dm_bio_prison_cell *), 278 void *context, 279 struct dm_bio_prison_cell *cell) 280 { 281 unsigned l = lock_nr(&cell->key, prison->num_locks); 282 spin_lock_irq(&prison->regions[l].lock); 283 visit_fn(context, cell); 284 rb_erase(&cell->node, &prison->regions[l].cell); 285 spin_unlock_irq(&prison->regions[l].lock); 286 } 287 EXPORT_SYMBOL_GPL(dm_cell_visit_release); 288 289 static int __promote_or_release(struct rb_root *root, 290 struct dm_bio_prison_cell *cell) 291 { 292 if (bio_list_empty(&cell->bios)) { 293 rb_erase(&cell->node, root); 294 return 1; 295 } 296 297 cell->holder = bio_list_pop(&cell->bios); 298 return 0; 299 } 300 301 int dm_cell_promote_or_release(struct dm_bio_prison *prison, 302 struct dm_bio_prison_cell *cell) 303 { 304 int r; 305 unsigned l = lock_nr(&cell->key, prison->num_locks); 306 307 spin_lock_irq(&prison->regions[l].lock); 308 r = __promote_or_release(&prison->regions[l].cell, cell); 309 spin_unlock_irq(&prison->regions[l].lock); 310 311 return r; 312 } 313 EXPORT_SYMBOL_GPL(dm_cell_promote_or_release); 314 315 /*----------------------------------------------------------------*/ 316 317 #define DEFERRED_SET_SIZE 64 318 319 struct dm_deferred_entry { 320 struct dm_deferred_set *ds; 321 unsigned int count; 322 struct list_head work_items; 323 }; 324 325 struct dm_deferred_set { 326 spinlock_t lock; 327 unsigned int current_entry; 328 unsigned int sweeper; 329 struct dm_deferred_entry entries[DEFERRED_SET_SIZE]; 330 }; 331 332 struct dm_deferred_set *dm_deferred_set_create(void) 333 { 334 int i; 335 struct dm_deferred_set *ds; 336 337 ds = kmalloc(sizeof(*ds), GFP_KERNEL); 338 if (!ds) 339 return NULL; 340 341 spin_lock_init(&ds->lock); 342 ds->current_entry = 0; 343 ds->sweeper = 0; 344 for (i = 0; i < DEFERRED_SET_SIZE; i++) { 345 ds->entries[i].ds = ds; 346 ds->entries[i].count = 0; 347 INIT_LIST_HEAD(&ds->entries[i].work_items); 348 } 349 350 return ds; 351 } 352 EXPORT_SYMBOL_GPL(dm_deferred_set_create); 353 354 void dm_deferred_set_destroy(struct dm_deferred_set *ds) 355 { 356 kfree(ds); 357 } 358 EXPORT_SYMBOL_GPL(dm_deferred_set_destroy); 359 360 struct dm_deferred_entry *dm_deferred_entry_inc(struct dm_deferred_set *ds) 361 { 362 unsigned long flags; 363 struct dm_deferred_entry *entry; 364 365 spin_lock_irqsave(&ds->lock, flags); 366 entry = ds->entries + ds->current_entry; 367 entry->count++; 368 spin_unlock_irqrestore(&ds->lock, flags); 369 370 return entry; 371 } 372 EXPORT_SYMBOL_GPL(dm_deferred_entry_inc); 373 374 static unsigned int ds_next(unsigned int index) 375 { 376 return (index + 1) % DEFERRED_SET_SIZE; 377 } 378 379 static void __sweep(struct dm_deferred_set *ds, struct list_head *head) 380 { 381 while ((ds->sweeper != ds->current_entry) && 382 !ds->entries[ds->sweeper].count) { 383 list_splice_init(&ds->entries[ds->sweeper].work_items, head); 384 ds->sweeper = ds_next(ds->sweeper); 385 } 386 387 if ((ds->sweeper == ds->current_entry) && !ds->entries[ds->sweeper].count) 388 list_splice_init(&ds->entries[ds->sweeper].work_items, head); 389 } 390 391 void dm_deferred_entry_dec(struct dm_deferred_entry *entry, struct list_head *head) 392 { 393 unsigned long flags; 394 395 spin_lock_irqsave(&entry->ds->lock, flags); 396 BUG_ON(!entry->count); 397 --entry->count; 398 __sweep(entry->ds, head); 399 spin_unlock_irqrestore(&entry->ds->lock, flags); 400 } 401 EXPORT_SYMBOL_GPL(dm_deferred_entry_dec); 402 403 /* 404 * Returns 1 if deferred or 0 if no pending items to delay job. 405 */ 406 int dm_deferred_set_add_work(struct dm_deferred_set *ds, struct list_head *work) 407 { 408 int r = 1; 409 unsigned int next_entry; 410 411 spin_lock_irq(&ds->lock); 412 if ((ds->sweeper == ds->current_entry) && 413 !ds->entries[ds->current_entry].count) 414 r = 0; 415 else { 416 list_add(work, &ds->entries[ds->current_entry].work_items); 417 next_entry = ds_next(ds->current_entry); 418 if (!ds->entries[next_entry].count) 419 ds->current_entry = next_entry; 420 } 421 spin_unlock_irq(&ds->lock); 422 423 return r; 424 } 425 EXPORT_SYMBOL_GPL(dm_deferred_set_add_work); 426 427 /*----------------------------------------------------------------*/ 428 429 static int __init dm_bio_prison_init_v1(void) 430 { 431 _cell_cache = KMEM_CACHE(dm_bio_prison_cell, 0); 432 if (!_cell_cache) 433 return -ENOMEM; 434 435 return 0; 436 } 437 438 static void dm_bio_prison_exit_v1(void) 439 { 440 kmem_cache_destroy(_cell_cache); 441 _cell_cache = NULL; 442 } 443 444 static int (*_inits[])(void) __initdata = { 445 dm_bio_prison_init_v1, 446 dm_bio_prison_init_v2, 447 }; 448 449 static void (*_exits[])(void) = { 450 dm_bio_prison_exit_v1, 451 dm_bio_prison_exit_v2, 452 }; 453 454 static int __init dm_bio_prison_init(void) 455 { 456 const int count = ARRAY_SIZE(_inits); 457 458 int r, i; 459 460 for (i = 0; i < count; i++) { 461 r = _inits[i](); 462 if (r) 463 goto bad; 464 } 465 466 return 0; 467 468 bad: 469 while (i--) 470 _exits[i](); 471 472 return r; 473 } 474 475 static void __exit dm_bio_prison_exit(void) 476 { 477 int i = ARRAY_SIZE(_exits); 478 479 while (i--) 480 _exits[i](); 481 } 482 483 /* 484 * module hooks 485 */ 486 module_init(dm_bio_prison_init); 487 module_exit(dm_bio_prison_exit); 488 489 MODULE_DESCRIPTION(DM_NAME " bio prison"); 490 MODULE_AUTHOR("Joe Thornber <dm-devel@redhat.com>"); 491 MODULE_LICENSE("GPL"); 492