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