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