blob: 03af174485d3066c62659f252c5306fc86fa3f68 [file] [log] [blame]
Mike Snitzer4f81a412012-10-12 21:02:13 +01001/*
2 * Copyright (C) 2012 Red Hat, Inc.
3 *
4 * This file is released under the GPL.
5 */
6
7#include "dm.h"
8#include "dm-bio-prison.h"
9
10#include <linux/spinlock.h>
11#include <linux/mempool.h>
12#include <linux/module.h>
13#include <linux/slab.h>
14
15/*----------------------------------------------------------------*/
16
Joe Thornbera195db22014-10-06 16:30:06 -040017#define MIN_CELLS 1024
Heinz Mauelshagenadcc4442014-06-05 15:23:09 +010018
19struct dm_bio_prison {
Joe Thornbera195db22014-10-06 16:30:06 -040020 spinlock_t lock;
Mike Snitzer4f81a412012-10-12 21:02:13 +010021 mempool_t *cell_pool;
Joe Thornbera195db22014-10-06 16:30:06 -040022 struct rb_root cells;
Mike Snitzer4f81a412012-10-12 21:02:13 +010023};
24
Mike Snitzer4f81a412012-10-12 21:02:13 +010025static struct kmem_cache *_cell_cache;
26
Joe Thornbera195db22014-10-06 16:30:06 -040027/*----------------------------------------------------------------*/
Heinz Mauelshagenadcc4442014-06-05 15:23:09 +010028
Mike Snitzer4f81a412012-10-12 21:02:13 +010029/*
30 * @nr_cells should be the number of cells you want in use _concurrently_.
31 * Don't confuse it with the number of distinct keys.
32 */
Joe Thornbera195db22014-10-06 16:30:06 -040033struct dm_bio_prison *dm_bio_prison_create(void)
Mike Snitzer4f81a412012-10-12 21:02:13 +010034{
Joe Thornbera195db22014-10-06 16:30:06 -040035 struct dm_bio_prison *prison = kmalloc(sizeof(*prison), GFP_KERNEL);
Mike Snitzer4f81a412012-10-12 21:02:13 +010036
37 if (!prison)
38 return NULL;
39
Joe Thornbera195db22014-10-06 16:30:06 -040040 spin_lock_init(&prison->lock);
41
42 prison->cell_pool = mempool_create_slab_pool(MIN_CELLS, _cell_cache);
Mike Snitzer4f81a412012-10-12 21:02:13 +010043 if (!prison->cell_pool) {
44 kfree(prison);
45 return NULL;
46 }
47
Joe Thornbera195db22014-10-06 16:30:06 -040048 prison->cells = RB_ROOT;
Mike Snitzer4f81a412012-10-12 21:02:13 +010049
50 return prison;
51}
52EXPORT_SYMBOL_GPL(dm_bio_prison_create);
53
54void dm_bio_prison_destroy(struct dm_bio_prison *prison)
55{
56 mempool_destroy(prison->cell_pool);
57 kfree(prison);
58}
59EXPORT_SYMBOL_GPL(dm_bio_prison_destroy);
60
Joe Thornber6beca5e2013-03-01 22:45:50 +000061struct dm_bio_prison_cell *dm_bio_prison_alloc_cell(struct dm_bio_prison *prison, gfp_t gfp)
62{
63 return mempool_alloc(prison->cell_pool, gfp);
64}
65EXPORT_SYMBOL_GPL(dm_bio_prison_alloc_cell);
66
67void dm_bio_prison_free_cell(struct dm_bio_prison *prison,
68 struct dm_bio_prison_cell *cell)
69{
70 mempool_free(cell, prison->cell_pool);
71}
72EXPORT_SYMBOL_GPL(dm_bio_prison_free_cell);
73
Joe Thornbera195db22014-10-06 16:30:06 -040074static void __setup_new_cell(struct dm_cell_key *key,
Joe Thornber6beca5e2013-03-01 22:45:50 +000075 struct bio *holder,
Joe Thornber6beca5e2013-03-01 22:45:50 +000076 struct dm_bio_prison_cell *cell)
Mike Snitzer4f81a412012-10-12 21:02:13 +010077{
Joe Thornbera195db22014-10-06 16:30:06 -040078 memcpy(&cell->key, key, sizeof(cell->key));
79 cell->holder = holder;
80 bio_list_init(&cell->bios);
Joe Thornber6beca5e2013-03-01 22:45:50 +000081}
Mike Snitzer4f81a412012-10-12 21:02:13 +010082
Joe Thornbera195db22014-10-06 16:30:06 -040083static int cmp_keys(struct dm_cell_key *lhs,
84 struct dm_cell_key *rhs)
85{
86 if (lhs->virtual < rhs->virtual)
87 return -1;
88
89 if (lhs->virtual > rhs->virtual)
90 return 1;
91
92 if (lhs->dev < rhs->dev)
93 return -1;
94
95 if (lhs->dev > rhs->dev)
96 return 1;
97
Joe Thornber5f274d82014-09-17 10:17:39 +010098 if (lhs->block_end <= rhs->block_begin)
Joe Thornbera195db22014-10-06 16:30:06 -040099 return -1;
100
Joe Thornber5f274d82014-09-17 10:17:39 +0100101 if (lhs->block_begin >= rhs->block_end)
Joe Thornbera195db22014-10-06 16:30:06 -0400102 return 1;
103
104 return 0;
105}
106
107static int __bio_detain(struct dm_bio_prison *prison,
Joe Thornber6beca5e2013-03-01 22:45:50 +0000108 struct dm_cell_key *key,
109 struct bio *inmate,
110 struct dm_bio_prison_cell *cell_prealloc,
111 struct dm_bio_prison_cell **cell_result)
112{
Joe Thornbera195db22014-10-06 16:30:06 -0400113 int r;
114 struct rb_node **new = &prison->cells.rb_node, *parent = NULL;
Mike Snitzer4f81a412012-10-12 21:02:13 +0100115
Joe Thornbera195db22014-10-06 16:30:06 -0400116 while (*new) {
117 struct dm_bio_prison_cell *cell =
118 container_of(*new, struct dm_bio_prison_cell, node);
119
120 r = cmp_keys(key, &cell->key);
121
122 parent = *new;
123 if (r < 0)
124 new = &((*new)->rb_left);
125 else if (r > 0)
126 new = &((*new)->rb_right);
127 else {
128 if (inmate)
129 bio_list_add(&cell->bios, inmate);
130 *cell_result = cell;
131 return 1;
132 }
Joe Thornber6beca5e2013-03-01 22:45:50 +0000133 }
134
Joe Thornbera195db22014-10-06 16:30:06 -0400135 __setup_new_cell(key, inmate, cell_prealloc);
Joe Thornber6beca5e2013-03-01 22:45:50 +0000136 *cell_result = cell_prealloc;
Joe Thornbera195db22014-10-06 16:30:06 -0400137
138 rb_link_node(&cell_prealloc->node, parent, new);
139 rb_insert_color(&cell_prealloc->node, &prison->cells);
140
Joe Thornber6beca5e2013-03-01 22:45:50 +0000141 return 0;
142}
143
144static int bio_detain(struct dm_bio_prison *prison,
145 struct dm_cell_key *key,
146 struct bio *inmate,
147 struct dm_bio_prison_cell *cell_prealloc,
148 struct dm_bio_prison_cell **cell_result)
149{
150 int r;
151 unsigned long flags;
152
Joe Thornbera195db22014-10-06 16:30:06 -0400153 spin_lock_irqsave(&prison->lock, flags);
154 r = __bio_detain(prison, key, inmate, cell_prealloc, cell_result);
155 spin_unlock_irqrestore(&prison->lock, flags);
Mike Snitzer4f81a412012-10-12 21:02:13 +0100156
Mike Snitzer4f81a412012-10-12 21:02:13 +0100157 return r;
158}
Joe Thornber6beca5e2013-03-01 22:45:50 +0000159
160int dm_bio_detain(struct dm_bio_prison *prison,
161 struct dm_cell_key *key,
162 struct bio *inmate,
163 struct dm_bio_prison_cell *cell_prealloc,
164 struct dm_bio_prison_cell **cell_result)
165{
166 return bio_detain(prison, key, inmate, cell_prealloc, cell_result);
167}
Mike Snitzer4f81a412012-10-12 21:02:13 +0100168EXPORT_SYMBOL_GPL(dm_bio_detain);
169
Joe Thornberc6b4fcb2013-03-01 22:45:51 +0000170int dm_get_cell(struct dm_bio_prison *prison,
171 struct dm_cell_key *key,
172 struct dm_bio_prison_cell *cell_prealloc,
173 struct dm_bio_prison_cell **cell_result)
174{
175 return bio_detain(prison, key, NULL, cell_prealloc, cell_result);
176}
177EXPORT_SYMBOL_GPL(dm_get_cell);
178
Mike Snitzer4f81a412012-10-12 21:02:13 +0100179/*
180 * @inmates must have been initialised prior to this call
181 */
Joe Thornbera195db22014-10-06 16:30:06 -0400182static void __cell_release(struct dm_bio_prison *prison,
183 struct dm_bio_prison_cell *cell,
Joe Thornber6beca5e2013-03-01 22:45:50 +0000184 struct bio_list *inmates)
Mike Snitzer4f81a412012-10-12 21:02:13 +0100185{
Joe Thornbera195db22014-10-06 16:30:06 -0400186 rb_erase(&cell->node, &prison->cells);
Mike Snitzer4f81a412012-10-12 21:02:13 +0100187
188 if (inmates) {
Joe Thornber6beca5e2013-03-01 22:45:50 +0000189 if (cell->holder)
190 bio_list_add(inmates, cell->holder);
Mike Snitzer4f81a412012-10-12 21:02:13 +0100191 bio_list_merge(inmates, &cell->bios);
192 }
Mike Snitzer4f81a412012-10-12 21:02:13 +0100193}
194
Joe Thornber6beca5e2013-03-01 22:45:50 +0000195void dm_cell_release(struct dm_bio_prison *prison,
196 struct dm_bio_prison_cell *cell,
197 struct bio_list *bios)
Mike Snitzer4f81a412012-10-12 21:02:13 +0100198{
199 unsigned long flags;
Mike Snitzer4f81a412012-10-12 21:02:13 +0100200
Joe Thornbera195db22014-10-06 16:30:06 -0400201 spin_lock_irqsave(&prison->lock, flags);
202 __cell_release(prison, cell, bios);
203 spin_unlock_irqrestore(&prison->lock, flags);
Mike Snitzer4f81a412012-10-12 21:02:13 +0100204}
205EXPORT_SYMBOL_GPL(dm_cell_release);
206
207/*
Mike Snitzer4f81a412012-10-12 21:02:13 +0100208 * Sometimes we don't want the holder, just the additional bios.
209 */
Joe Thornbera195db22014-10-06 16:30:06 -0400210static void __cell_release_no_holder(struct dm_bio_prison *prison,
211 struct dm_bio_prison_cell *cell,
Joe Thornber6beca5e2013-03-01 22:45:50 +0000212 struct bio_list *inmates)
Mike Snitzer4f81a412012-10-12 21:02:13 +0100213{
Joe Thornbera195db22014-10-06 16:30:06 -0400214 rb_erase(&cell->node, &prison->cells);
Mike Snitzer4f81a412012-10-12 21:02:13 +0100215 bio_list_merge(inmates, &cell->bios);
Mike Snitzer4f81a412012-10-12 21:02:13 +0100216}
217
Joe Thornber6beca5e2013-03-01 22:45:50 +0000218void dm_cell_release_no_holder(struct dm_bio_prison *prison,
219 struct dm_bio_prison_cell *cell,
220 struct bio_list *inmates)
Mike Snitzer4f81a412012-10-12 21:02:13 +0100221{
222 unsigned long flags;
Mike Snitzer4f81a412012-10-12 21:02:13 +0100223
Joe Thornbera195db22014-10-06 16:30:06 -0400224 spin_lock_irqsave(&prison->lock, flags);
225 __cell_release_no_holder(prison, cell, inmates);
226 spin_unlock_irqrestore(&prison->lock, flags);
Mike Snitzer4f81a412012-10-12 21:02:13 +0100227}
228EXPORT_SYMBOL_GPL(dm_cell_release_no_holder);
229
Joe Thornber6beca5e2013-03-01 22:45:50 +0000230void dm_cell_error(struct dm_bio_prison *prison,
Mike Snitzeraf918052014-05-22 14:32:51 -0400231 struct dm_bio_prison_cell *cell, int error)
Mike Snitzer4f81a412012-10-12 21:02:13 +0100232{
Mike Snitzer4f81a412012-10-12 21:02:13 +0100233 struct bio_list bios;
234 struct bio *bio;
Mike Snitzer4f81a412012-10-12 21:02:13 +0100235
236 bio_list_init(&bios);
Heinz Mauelshagenadcc4442014-06-05 15:23:09 +0100237 dm_cell_release(prison, cell, &bios);
Mike Snitzer4f81a412012-10-12 21:02:13 +0100238
Christoph Hellwig4246a0b2015-07-20 15:29:37 +0200239 while ((bio = bio_list_pop(&bios))) {
240 bio->bi_error = error;
241 bio_endio(bio);
242 }
Mike Snitzer4f81a412012-10-12 21:02:13 +0100243}
244EXPORT_SYMBOL_GPL(dm_cell_error);
245
Joe Thornber2d759a42014-10-10 15:27:16 +0100246void 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 unsigned long flags;
252
253 spin_lock_irqsave(&prison->lock, flags);
254 visit_fn(context, cell);
255 rb_erase(&cell->node, &prison->cells);
256 spin_unlock_irqrestore(&prison->lock, flags);
257}
258EXPORT_SYMBOL_GPL(dm_cell_visit_release);
259
Joe Thornber3cdf93f2015-05-15 15:23:35 +0100260static int __promote_or_release(struct dm_bio_prison *prison,
261 struct dm_bio_prison_cell *cell)
262{
263 if (bio_list_empty(&cell->bios)) {
264 rb_erase(&cell->node, &prison->cells);
265 return 1;
266 }
267
268 cell->holder = bio_list_pop(&cell->bios);
269 return 0;
270}
271
272int dm_cell_promote_or_release(struct dm_bio_prison *prison,
273 struct dm_bio_prison_cell *cell)
274{
275 int r;
276 unsigned long flags;
277
278 spin_lock_irqsave(&prison->lock, flags);
279 r = __promote_or_release(prison, cell);
280 spin_unlock_irqrestore(&prison->lock, flags);
281
282 return r;
283}
284EXPORT_SYMBOL_GPL(dm_cell_promote_or_release);
285
Mike Snitzer4f81a412012-10-12 21:02:13 +0100286/*----------------------------------------------------------------*/
287
288#define DEFERRED_SET_SIZE 64
289
290struct dm_deferred_entry {
291 struct dm_deferred_set *ds;
292 unsigned count;
293 struct list_head work_items;
294};
295
296struct dm_deferred_set {
297 spinlock_t lock;
298 unsigned current_entry;
299 unsigned sweeper;
300 struct dm_deferred_entry entries[DEFERRED_SET_SIZE];
301};
302
303struct dm_deferred_set *dm_deferred_set_create(void)
304{
305 int i;
306 struct dm_deferred_set *ds;
307
308 ds = kmalloc(sizeof(*ds), GFP_KERNEL);
309 if (!ds)
310 return NULL;
311
312 spin_lock_init(&ds->lock);
313 ds->current_entry = 0;
314 ds->sweeper = 0;
315 for (i = 0; i < DEFERRED_SET_SIZE; i++) {
316 ds->entries[i].ds = ds;
317 ds->entries[i].count = 0;
318 INIT_LIST_HEAD(&ds->entries[i].work_items);
319 }
320
321 return ds;
322}
323EXPORT_SYMBOL_GPL(dm_deferred_set_create);
324
325void dm_deferred_set_destroy(struct dm_deferred_set *ds)
326{
327 kfree(ds);
328}
329EXPORT_SYMBOL_GPL(dm_deferred_set_destroy);
330
331struct dm_deferred_entry *dm_deferred_entry_inc(struct dm_deferred_set *ds)
332{
333 unsigned long flags;
334 struct dm_deferred_entry *entry;
335
336 spin_lock_irqsave(&ds->lock, flags);
337 entry = ds->entries + ds->current_entry;
338 entry->count++;
339 spin_unlock_irqrestore(&ds->lock, flags);
340
341 return entry;
342}
343EXPORT_SYMBOL_GPL(dm_deferred_entry_inc);
344
345static unsigned ds_next(unsigned index)
346{
347 return (index + 1) % DEFERRED_SET_SIZE;
348}
349
350static void __sweep(struct dm_deferred_set *ds, struct list_head *head)
351{
352 while ((ds->sweeper != ds->current_entry) &&
353 !ds->entries[ds->sweeper].count) {
354 list_splice_init(&ds->entries[ds->sweeper].work_items, head);
355 ds->sweeper = ds_next(ds->sweeper);
356 }
357
358 if ((ds->sweeper == ds->current_entry) && !ds->entries[ds->sweeper].count)
359 list_splice_init(&ds->entries[ds->sweeper].work_items, head);
360}
361
362void dm_deferred_entry_dec(struct dm_deferred_entry *entry, struct list_head *head)
363{
364 unsigned long flags;
365
366 spin_lock_irqsave(&entry->ds->lock, flags);
367 BUG_ON(!entry->count);
368 --entry->count;
369 __sweep(entry->ds, head);
370 spin_unlock_irqrestore(&entry->ds->lock, flags);
371}
372EXPORT_SYMBOL_GPL(dm_deferred_entry_dec);
373
374/*
375 * Returns 1 if deferred or 0 if no pending items to delay job.
376 */
377int dm_deferred_set_add_work(struct dm_deferred_set *ds, struct list_head *work)
378{
379 int r = 1;
380 unsigned long flags;
381 unsigned next_entry;
382
383 spin_lock_irqsave(&ds->lock, flags);
384 if ((ds->sweeper == ds->current_entry) &&
385 !ds->entries[ds->current_entry].count)
386 r = 0;
387 else {
388 list_add(work, &ds->entries[ds->current_entry].work_items);
389 next_entry = ds_next(ds->current_entry);
390 if (!ds->entries[next_entry].count)
391 ds->current_entry = next_entry;
392 }
393 spin_unlock_irqrestore(&ds->lock, flags);
394
395 return r;
396}
397EXPORT_SYMBOL_GPL(dm_deferred_set_add_work);
398
399/*----------------------------------------------------------------*/
400
401static int __init dm_bio_prison_init(void)
402{
403 _cell_cache = KMEM_CACHE(dm_bio_prison_cell, 0);
404 if (!_cell_cache)
405 return -ENOMEM;
406
407 return 0;
408}
409
410static void __exit dm_bio_prison_exit(void)
411{
412 kmem_cache_destroy(_cell_cache);
413 _cell_cache = NULL;
414}
415
416/*
417 * module hooks
418 */
419module_init(dm_bio_prison_init);
420module_exit(dm_bio_prison_exit);
421
422MODULE_DESCRIPTION(DM_NAME " bio prison");
423MODULE_AUTHOR("Joe Thornber <dm-devel@redhat.com>");
424MODULE_LICENSE("GPL");