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