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" | |
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 | ||
a195db2d | 17 | #define MIN_CELLS 1024 |
adcc4447 HM |
18 | |
19 | struct dm_bio_prison { | |
a195db2d | 20 | spinlock_t lock; |
4f81a417 | 21 | mempool_t *cell_pool; |
a195db2d | 22 | struct rb_root cells; |
4f81a417 MS |
23 | }; |
24 | ||
4f81a417 MS |
25 | static struct kmem_cache *_cell_cache; |
26 | ||
a195db2d | 27 | /*----------------------------------------------------------------*/ |
adcc4447 | 28 | |
4f81a417 MS |
29 | /* |
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 | */ | |
a195db2d | 33 | struct dm_bio_prison *dm_bio_prison_create(void) |
4f81a417 | 34 | { |
a195db2d | 35 | struct dm_bio_prison *prison = kmalloc(sizeof(*prison), GFP_KERNEL); |
4f81a417 MS |
36 | |
37 | if (!prison) | |
38 | return NULL; | |
39 | ||
a195db2d JT |
40 | spin_lock_init(&prison->lock); |
41 | ||
42 | prison->cell_pool = mempool_create_slab_pool(MIN_CELLS, _cell_cache); | |
4f81a417 MS |
43 | if (!prison->cell_pool) { |
44 | kfree(prison); | |
45 | return NULL; | |
46 | } | |
47 | ||
a195db2d | 48 | prison->cells = RB_ROOT; |
4f81a417 MS |
49 | |
50 | return prison; | |
51 | } | |
52 | EXPORT_SYMBOL_GPL(dm_bio_prison_create); | |
53 | ||
54 | void dm_bio_prison_destroy(struct dm_bio_prison *prison) | |
55 | { | |
56 | mempool_destroy(prison->cell_pool); | |
57 | kfree(prison); | |
58 | } | |
59 | EXPORT_SYMBOL_GPL(dm_bio_prison_destroy); | |
60 | ||
6beca5eb JT |
61 | struct 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 | } | |
65 | EXPORT_SYMBOL_GPL(dm_bio_prison_alloc_cell); | |
66 | ||
67 | void 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 | } | |
72 | EXPORT_SYMBOL_GPL(dm_bio_prison_free_cell); | |
73 | ||
a195db2d JT |
74 | static void __setup_new_cell(struct dm_cell_key *key, |
75 | struct bio *holder, | |
76 | struct dm_bio_prison_cell *cell) | |
4f81a417 | 77 | { |
a195db2d JT |
78 | memcpy(&cell->key, key, sizeof(cell->key)); |
79 | cell->holder = holder; | |
80 | bio_list_init(&cell->bios); | |
4f81a417 MS |
81 | } |
82 | ||
a195db2d JT |
83 | static int cmp_keys(struct dm_cell_key *lhs, |
84 | struct dm_cell_key *rhs) | |
4f81a417 | 85 | { |
a195db2d JT |
86 | if (lhs->virtual < rhs->virtual) |
87 | return -1; | |
4f81a417 | 88 | |
a195db2d JT |
89 | if (lhs->virtual > rhs->virtual) |
90 | return 1; | |
adcc4447 | 91 | |
a195db2d JT |
92 | if (lhs->dev < rhs->dev) |
93 | return -1; | |
4f81a417 | 94 | |
a195db2d JT |
95 | if (lhs->dev > rhs->dev) |
96 | return 1; | |
4f81a417 | 97 | |
5f274d88 | 98 | if (lhs->block_end <= rhs->block_begin) |
a195db2d | 99 | return -1; |
4f81a417 | 100 | |
5f274d88 | 101 | if (lhs->block_begin >= rhs->block_end) |
a195db2d JT |
102 | return 1; |
103 | ||
104 | return 0; | |
6beca5eb | 105 | } |
4f81a417 | 106 | |
a195db2d | 107 | static int __bio_detain(struct dm_bio_prison *prison, |
6beca5eb JT |
108 | 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 | { | |
a195db2d JT |
113 | int r; |
114 | struct rb_node **new = &prison->cells.rb_node, *parent = NULL; | |
115 | ||
116 | 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 | } | |
4f81a417 MS |
133 | } |
134 | ||
a195db2d | 135 | __setup_new_cell(key, inmate, cell_prealloc); |
6beca5eb | 136 | *cell_result = cell_prealloc; |
a195db2d JT |
137 | |
138 | rb_link_node(&cell_prealloc->node, parent, new); | |
139 | rb_insert_color(&cell_prealloc->node, &prison->cells); | |
140 | ||
6beca5eb JT |
141 | return 0; |
142 | } | |
4f81a417 | 143 | |
6beca5eb JT |
144 | static 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; | |
4f81a417 | 152 | |
a195db2d JT |
153 | spin_lock_irqsave(&prison->lock, flags); |
154 | r = __bio_detain(prison, key, inmate, cell_prealloc, cell_result); | |
155 | spin_unlock_irqrestore(&prison->lock, flags); | |
4f81a417 | 156 | |
4f81a417 MS |
157 | return r; |
158 | } | |
6beca5eb JT |
159 | |
160 | int 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 | } | |
4f81a417 MS |
168 | EXPORT_SYMBOL_GPL(dm_bio_detain); |
169 | ||
c6b4fcba JT |
170 | int 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 | } | |
177 | EXPORT_SYMBOL_GPL(dm_get_cell); | |
178 | ||
4f81a417 MS |
179 | /* |
180 | * @inmates must have been initialised prior to this call | |
181 | */ | |
a195db2d JT |
182 | static void __cell_release(struct dm_bio_prison *prison, |
183 | struct dm_bio_prison_cell *cell, | |
6beca5eb | 184 | struct bio_list *inmates) |
4f81a417 | 185 | { |
a195db2d | 186 | rb_erase(&cell->node, &prison->cells); |
4f81a417 MS |
187 | |
188 | if (inmates) { | |
6beca5eb JT |
189 | if (cell->holder) |
190 | bio_list_add(inmates, cell->holder); | |
4f81a417 MS |
191 | bio_list_merge(inmates, &cell->bios); |
192 | } | |
4f81a417 MS |
193 | } |
194 | ||
6beca5eb JT |
195 | void dm_cell_release(struct dm_bio_prison *prison, |
196 | struct dm_bio_prison_cell *cell, | |
197 | struct bio_list *bios) | |
4f81a417 MS |
198 | { |
199 | unsigned long flags; | |
4f81a417 | 200 | |
a195db2d JT |
201 | spin_lock_irqsave(&prison->lock, flags); |
202 | __cell_release(prison, cell, bios); | |
203 | spin_unlock_irqrestore(&prison->lock, flags); | |
4f81a417 MS |
204 | } |
205 | EXPORT_SYMBOL_GPL(dm_cell_release); | |
206 | ||
4f81a417 MS |
207 | /* |
208 | * Sometimes we don't want the holder, just the additional bios. | |
209 | */ | |
a195db2d JT |
210 | static void __cell_release_no_holder(struct dm_bio_prison *prison, |
211 | struct dm_bio_prison_cell *cell, | |
6beca5eb | 212 | struct bio_list *inmates) |
4f81a417 | 213 | { |
a195db2d | 214 | rb_erase(&cell->node, &prison->cells); |
4f81a417 | 215 | bio_list_merge(inmates, &cell->bios); |
4f81a417 MS |
216 | } |
217 | ||
6beca5eb JT |
218 | void dm_cell_release_no_holder(struct dm_bio_prison *prison, |
219 | struct dm_bio_prison_cell *cell, | |
220 | struct bio_list *inmates) | |
4f81a417 MS |
221 | { |
222 | unsigned long flags; | |
4f81a417 | 223 | |
a195db2d JT |
224 | spin_lock_irqsave(&prison->lock, flags); |
225 | __cell_release_no_holder(prison, cell, inmates); | |
226 | spin_unlock_irqrestore(&prison->lock, flags); | |
4f81a417 MS |
227 | } |
228 | EXPORT_SYMBOL_GPL(dm_cell_release_no_holder); | |
229 | ||
6beca5eb | 230 | void dm_cell_error(struct dm_bio_prison *prison, |
af91805a | 231 | struct dm_bio_prison_cell *cell, int error) |
4f81a417 | 232 | { |
4f81a417 MS |
233 | struct bio_list bios; |
234 | struct bio *bio; | |
4f81a417 MS |
235 | |
236 | bio_list_init(&bios); | |
adcc4447 | 237 | dm_cell_release(prison, cell, &bios); |
4f81a417 | 238 | |
4246a0b6 CH |
239 | while ((bio = bio_list_pop(&bios))) { |
240 | bio->bi_error = error; | |
241 | bio_endio(bio); | |
242 | } | |
4f81a417 MS |
243 | } |
244 | EXPORT_SYMBOL_GPL(dm_cell_error); | |
245 | ||
2d759a46 JT |
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 | 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 | } | |
258 | EXPORT_SYMBOL_GPL(dm_cell_visit_release); | |
259 | ||
3cdf93f9 JT |
260 | static 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 | ||
272 | int 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 | } | |
284 | EXPORT_SYMBOL_GPL(dm_cell_promote_or_release); | |
285 | ||
4f81a417 MS |
286 | /*----------------------------------------------------------------*/ |
287 | ||
288 | #define DEFERRED_SET_SIZE 64 | |
289 | ||
290 | struct dm_deferred_entry { | |
291 | struct dm_deferred_set *ds; | |
292 | unsigned count; | |
293 | struct list_head work_items; | |
294 | }; | |
295 | ||
296 | struct 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 | ||
303 | struct 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 | } | |
323 | EXPORT_SYMBOL_GPL(dm_deferred_set_create); | |
324 | ||
325 | void dm_deferred_set_destroy(struct dm_deferred_set *ds) | |
326 | { | |
327 | kfree(ds); | |
328 | } | |
329 | EXPORT_SYMBOL_GPL(dm_deferred_set_destroy); | |
330 | ||
331 | struct 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 | } | |
343 | EXPORT_SYMBOL_GPL(dm_deferred_entry_inc); | |
344 | ||
345 | static unsigned ds_next(unsigned index) | |
346 | { | |
347 | return (index + 1) % DEFERRED_SET_SIZE; | |
348 | } | |
349 | ||
350 | static 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 | ||
362 | void 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 | } | |
372 | EXPORT_SYMBOL_GPL(dm_deferred_entry_dec); | |
373 | ||
374 | /* | |
375 | * Returns 1 if deferred or 0 if no pending items to delay job. | |
376 | */ | |
377 | int 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 | } | |
397 | EXPORT_SYMBOL_GPL(dm_deferred_set_add_work); | |
398 | ||
399 | /*----------------------------------------------------------------*/ | |
400 | ||
401 | static 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 | ||
410 | static 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 | */ | |
419 | module_init(dm_bio_prison_init); | |
420 | module_exit(dm_bio_prison_exit); | |
421 | ||
422 | MODULE_DESCRIPTION(DM_NAME " bio prison"); | |
423 | MODULE_AUTHOR("Joe Thornber <dm-devel@redhat.com>"); | |
424 | MODULE_LICENSE("GPL"); |