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