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