Root/drivers/md/dm-bio-prison.c

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
17struct 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
28static 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
41static 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 */
47struct 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}
73EXPORT_SYMBOL_GPL(dm_bio_prison_create);
74
75void dm_bio_prison_destroy(struct dm_bio_prison *prison)
76{
77    mempool_destroy(prison->cell_pool);
78    kfree(prison);
79}
80EXPORT_SYMBOL_GPL(dm_bio_prison_destroy);
81
82struct 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}
86EXPORT_SYMBOL_GPL(dm_bio_prison_alloc_cell);
87
88void 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}
93EXPORT_SYMBOL_GPL(dm_bio_prison_free_cell);
94
95static 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
103static 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
110static 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
122static 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
134static 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
156static 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
172int 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}
180EXPORT_SYMBOL_GPL(dm_bio_detain);
181
182int 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}
189EXPORT_SYMBOL_GPL(dm_get_cell);
190
191/*
192 * @inmates must have been initialised prior to this call
193 */
194static 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
206void 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}
216EXPORT_SYMBOL_GPL(dm_cell_release);
217
218/*
219 * Sometimes we don't want the holder, just the additional bios.
220 */
221static 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
228void 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}
238EXPORT_SYMBOL_GPL(dm_cell_release_no_holder);
239
240void 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}
256EXPORT_SYMBOL_GPL(dm_cell_error);
257
258/*----------------------------------------------------------------*/
259
260#define DEFERRED_SET_SIZE 64
261
262struct dm_deferred_entry {
263    struct dm_deferred_set *ds;
264    unsigned count;
265    struct list_head work_items;
266};
267
268struct 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
275struct 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}
295EXPORT_SYMBOL_GPL(dm_deferred_set_create);
296
297void dm_deferred_set_destroy(struct dm_deferred_set *ds)
298{
299    kfree(ds);
300}
301EXPORT_SYMBOL_GPL(dm_deferred_set_destroy);
302
303struct 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}
315EXPORT_SYMBOL_GPL(dm_deferred_entry_inc);
316
317static unsigned ds_next(unsigned index)
318{
319    return (index + 1) % DEFERRED_SET_SIZE;
320}
321
322static 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
334void 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}
344EXPORT_SYMBOL_GPL(dm_deferred_entry_dec);
345
346/*
347 * Returns 1 if deferred or 0 if no pending items to delay job.
348 */
349int 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}
369EXPORT_SYMBOL_GPL(dm_deferred_set_add_work);
370
371/*----------------------------------------------------------------*/
372
373static 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
382static 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 */
391module_init(dm_bio_prison_init);
392module_exit(dm_bio_prison_exit);
393
394MODULE_DESCRIPTION(DM_NAME " bio prison");
395MODULE_AUTHOR("Joe Thornber <dm-devel@redhat.com>");
396MODULE_LICENSE("GPL");
397

Archive Download this file



interactive