Root/
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 { |
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 | |
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 | |
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; |
114 | |
115 | hlist_for_each_entry(cell, bucket, list) |
116 | if (keys_equal(&cell->key, key)) |
117 | return cell; |
118 | |
119 | return NULL; |
120 | } |
121 | |
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) |
127 | { |
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 | } |
133 | |
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; |
142 | |
143 | cell = __search_bucket(prison->cells + hash, key); |
144 | if (cell) { |
145 | if (inmate) |
146 | bio_list_add(&cell->bios, inmate); |
147 | *cell_result = cell; |
148 | return 1; |
149 | } |
150 | |
151 | __setup_new_cell(prison, key, inmate, hash, cell_prealloc); |
152 | *cell_result = cell_prealloc; |
153 | return 0; |
154 | } |
155 | |
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; |
164 | |
165 | spin_lock_irqsave(&prison->lock, flags); |
166 | r = __bio_detain(prison, key, inmate, cell_prealloc, cell_result); |
167 | spin_unlock_irqrestore(&prison->lock, flags); |
168 | |
169 | return r; |
170 | } |
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 | } |
180 | EXPORT_SYMBOL_GPL(dm_bio_detain); |
181 | |
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 | |
191 | /* |
192 | * @inmates must have been initialised prior to this call |
193 | */ |
194 | static void __cell_release(struct dm_bio_prison_cell *cell, |
195 | struct bio_list *inmates) |
196 | { |
197 | hlist_del(&cell->list); |
198 | |
199 | if (inmates) { |
200 | if (cell->holder) |
201 | bio_list_add(inmates, cell->holder); |
202 | bio_list_merge(inmates, &cell->bios); |
203 | } |
204 | } |
205 | |
206 | void dm_cell_release(struct dm_bio_prison *prison, |
207 | struct dm_bio_prison_cell *cell, |
208 | struct bio_list *bios) |
209 | { |
210 | unsigned long flags; |
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 | |
218 | /* |
219 | * Sometimes we don't want the holder, just the additional bios. |
220 | */ |
221 | static void __cell_release_no_holder(struct dm_bio_prison_cell *cell, |
222 | struct bio_list *inmates) |
223 | { |
224 | hlist_del(&cell->list); |
225 | bio_list_merge(inmates, &cell->bios); |
226 | } |
227 | |
228 | void dm_cell_release_no_holder(struct dm_bio_prison *prison, |
229 | struct dm_bio_prison_cell *cell, |
230 | struct bio_list *inmates) |
231 | { |
232 | unsigned long flags; |
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 | |
240 | void dm_cell_error(struct dm_bio_prison *prison, |
241 | struct dm_bio_prison_cell *cell) |
242 | { |
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"); |
397 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9