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