GNU Linux-libre 4.19.264-gnu1
[releases.git] / drivers / md / dm-bio-prison-v1.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-v1.h"
9 #include "dm-bio-prison-v2.h"
10
11 #include <linux/spinlock.h>
12 #include <linux/mempool.h>
13 #include <linux/module.h>
14 #include <linux/slab.h>
15
16 /*----------------------------------------------------------------*/
17
18 #define MIN_CELLS 1024
19
20 struct dm_bio_prison {
21         spinlock_t lock;
22         struct rb_root cells;
23         mempool_t cell_pool;
24 };
25
26 static struct kmem_cache *_cell_cache;
27
28 /*----------------------------------------------------------------*/
29
30 /*
31  * @nr_cells should be the number of cells you want in use _concurrently_.
32  * Don't confuse it with the number of distinct keys.
33  */
34 struct dm_bio_prison *dm_bio_prison_create(void)
35 {
36         struct dm_bio_prison *prison = kzalloc(sizeof(*prison), GFP_KERNEL);
37         int ret;
38
39         if (!prison)
40                 return NULL;
41
42         spin_lock_init(&prison->lock);
43
44         ret = mempool_init_slab_pool(&prison->cell_pool, MIN_CELLS, _cell_cache);
45         if (ret) {
46                 kfree(prison);
47                 return NULL;
48         }
49
50         prison->cells = RB_ROOT;
51
52         return prison;
53 }
54 EXPORT_SYMBOL_GPL(dm_bio_prison_create);
55
56 void dm_bio_prison_destroy(struct dm_bio_prison *prison)
57 {
58         mempool_exit(&prison->cell_pool);
59         kfree(prison);
60 }
61 EXPORT_SYMBOL_GPL(dm_bio_prison_destroy);
62
63 struct dm_bio_prison_cell *dm_bio_prison_alloc_cell(struct dm_bio_prison *prison, gfp_t gfp)
64 {
65         return mempool_alloc(&prison->cell_pool, gfp);
66 }
67 EXPORT_SYMBOL_GPL(dm_bio_prison_alloc_cell);
68
69 void dm_bio_prison_free_cell(struct dm_bio_prison *prison,
70                              struct dm_bio_prison_cell *cell)
71 {
72         mempool_free(cell, &prison->cell_pool);
73 }
74 EXPORT_SYMBOL_GPL(dm_bio_prison_free_cell);
75
76 static void __setup_new_cell(struct dm_cell_key *key,
77                              struct bio *holder,
78                              struct dm_bio_prison_cell *cell)
79 {
80        memcpy(&cell->key, key, sizeof(cell->key));
81        cell->holder = holder;
82        bio_list_init(&cell->bios);
83 }
84
85 static int cmp_keys(struct dm_cell_key *lhs,
86                     struct dm_cell_key *rhs)
87 {
88         if (lhs->virtual < rhs->virtual)
89                 return -1;
90
91         if (lhs->virtual > rhs->virtual)
92                 return 1;
93
94         if (lhs->dev < rhs->dev)
95                 return -1;
96
97         if (lhs->dev > rhs->dev)
98                 return 1;
99
100         if (lhs->block_end <= rhs->block_begin)
101                 return -1;
102
103         if (lhs->block_begin >= rhs->block_end)
104                 return 1;
105
106         return 0;
107 }
108
109 static int __bio_detain(struct dm_bio_prison *prison,
110                         struct dm_cell_key *key,
111                         struct bio *inmate,
112                         struct dm_bio_prison_cell *cell_prealloc,
113                         struct dm_bio_prison_cell **cell_result)
114 {
115         int r;
116         struct rb_node **new = &prison->cells.rb_node, *parent = NULL;
117
118         while (*new) {
119                 struct dm_bio_prison_cell *cell =
120                         rb_entry(*new, struct dm_bio_prison_cell, node);
121
122                 r = cmp_keys(key, &cell->key);
123
124                 parent = *new;
125                 if (r < 0)
126                         new = &((*new)->rb_left);
127                 else if (r > 0)
128                         new = &((*new)->rb_right);
129                 else {
130                         if (inmate)
131                                 bio_list_add(&cell->bios, inmate);
132                         *cell_result = cell;
133                         return 1;
134                 }
135         }
136
137         __setup_new_cell(key, inmate, cell_prealloc);
138         *cell_result = cell_prealloc;
139
140         rb_link_node(&cell_prealloc->node, parent, new);
141         rb_insert_color(&cell_prealloc->node, &prison->cells);
142
143         return 0;
144 }
145
146 static int bio_detain(struct dm_bio_prison *prison,
147                       struct dm_cell_key *key,
148                       struct bio *inmate,
149                       struct dm_bio_prison_cell *cell_prealloc,
150                       struct dm_bio_prison_cell **cell_result)
151 {
152         int r;
153         unsigned long flags;
154
155         spin_lock_irqsave(&prison->lock, flags);
156         r = __bio_detain(prison, key, inmate, cell_prealloc, cell_result);
157         spin_unlock_irqrestore(&prison->lock, flags);
158
159         return r;
160 }
161
162 int dm_bio_detain(struct dm_bio_prison *prison,
163                   struct dm_cell_key *key,
164                   struct bio *inmate,
165                   struct dm_bio_prison_cell *cell_prealloc,
166                   struct dm_bio_prison_cell **cell_result)
167 {
168         return bio_detain(prison, key, inmate, cell_prealloc, cell_result);
169 }
170 EXPORT_SYMBOL_GPL(dm_bio_detain);
171
172 int dm_get_cell(struct dm_bio_prison *prison,
173                 struct dm_cell_key *key,
174                 struct dm_bio_prison_cell *cell_prealloc,
175                 struct dm_bio_prison_cell **cell_result)
176 {
177         return bio_detain(prison, key, NULL, cell_prealloc, cell_result);
178 }
179 EXPORT_SYMBOL_GPL(dm_get_cell);
180
181 /*
182  * @inmates must have been initialised prior to this call
183  */
184 static void __cell_release(struct dm_bio_prison *prison,
185                            struct dm_bio_prison_cell *cell,
186                            struct bio_list *inmates)
187 {
188         rb_erase(&cell->node, &prison->cells);
189
190         if (inmates) {
191                 if (cell->holder)
192                         bio_list_add(inmates, cell->holder);
193                 bio_list_merge(inmates, &cell->bios);
194         }
195 }
196
197 void dm_cell_release(struct dm_bio_prison *prison,
198                      struct dm_bio_prison_cell *cell,
199                      struct bio_list *bios)
200 {
201         unsigned long flags;
202
203         spin_lock_irqsave(&prison->lock, flags);
204         __cell_release(prison, cell, bios);
205         spin_unlock_irqrestore(&prison->lock, flags);
206 }
207 EXPORT_SYMBOL_GPL(dm_cell_release);
208
209 /*
210  * Sometimes we don't want the holder, just the additional bios.
211  */
212 static void __cell_release_no_holder(struct dm_bio_prison *prison,
213                                      struct dm_bio_prison_cell *cell,
214                                      struct bio_list *inmates)
215 {
216         rb_erase(&cell->node, &prison->cells);
217         bio_list_merge(inmates, &cell->bios);
218 }
219
220 void dm_cell_release_no_holder(struct dm_bio_prison *prison,
221                                struct dm_bio_prison_cell *cell,
222                                struct bio_list *inmates)
223 {
224         unsigned long flags;
225
226         spin_lock_irqsave(&prison->lock, flags);
227         __cell_release_no_holder(prison, cell, inmates);
228         spin_unlock_irqrestore(&prison->lock, flags);
229 }
230 EXPORT_SYMBOL_GPL(dm_cell_release_no_holder);
231
232 void dm_cell_error(struct dm_bio_prison *prison,
233                    struct dm_bio_prison_cell *cell, blk_status_t error)
234 {
235         struct bio_list bios;
236         struct bio *bio;
237
238         bio_list_init(&bios);
239         dm_cell_release(prison, cell, &bios);
240
241         while ((bio = bio_list_pop(&bios))) {
242                 bio->bi_status = error;
243                 bio_endio(bio);
244         }
245 }
246 EXPORT_SYMBOL_GPL(dm_cell_error);
247
248 void dm_cell_visit_release(struct dm_bio_prison *prison,
249                            void (*visit_fn)(void *, struct dm_bio_prison_cell *),
250                            void *context,
251                            struct dm_bio_prison_cell *cell)
252 {
253         unsigned long flags;
254
255         spin_lock_irqsave(&prison->lock, flags);
256         visit_fn(context, cell);
257         rb_erase(&cell->node, &prison->cells);
258         spin_unlock_irqrestore(&prison->lock, flags);
259 }
260 EXPORT_SYMBOL_GPL(dm_cell_visit_release);
261
262 static int __promote_or_release(struct dm_bio_prison *prison,
263                                 struct dm_bio_prison_cell *cell)
264 {
265         if (bio_list_empty(&cell->bios)) {
266                 rb_erase(&cell->node, &prison->cells);
267                 return 1;
268         }
269
270         cell->holder = bio_list_pop(&cell->bios);
271         return 0;
272 }
273
274 int dm_cell_promote_or_release(struct dm_bio_prison *prison,
275                                struct dm_bio_prison_cell *cell)
276 {
277         int r;
278         unsigned long flags;
279
280         spin_lock_irqsave(&prison->lock, flags);
281         r = __promote_or_release(prison, cell);
282         spin_unlock_irqrestore(&prison->lock, flags);
283
284         return r;
285 }
286 EXPORT_SYMBOL_GPL(dm_cell_promote_or_release);
287
288 /*----------------------------------------------------------------*/
289
290 #define DEFERRED_SET_SIZE 64
291
292 struct dm_deferred_entry {
293         struct dm_deferred_set *ds;
294         unsigned count;
295         struct list_head work_items;
296 };
297
298 struct dm_deferred_set {
299         spinlock_t lock;
300         unsigned current_entry;
301         unsigned sweeper;
302         struct dm_deferred_entry entries[DEFERRED_SET_SIZE];
303 };
304
305 struct dm_deferred_set *dm_deferred_set_create(void)
306 {
307         int i;
308         struct dm_deferred_set *ds;
309
310         ds = kmalloc(sizeof(*ds), GFP_KERNEL);
311         if (!ds)
312                 return NULL;
313
314         spin_lock_init(&ds->lock);
315         ds->current_entry = 0;
316         ds->sweeper = 0;
317         for (i = 0; i < DEFERRED_SET_SIZE; i++) {
318                 ds->entries[i].ds = ds;
319                 ds->entries[i].count = 0;
320                 INIT_LIST_HEAD(&ds->entries[i].work_items);
321         }
322
323         return ds;
324 }
325 EXPORT_SYMBOL_GPL(dm_deferred_set_create);
326
327 void dm_deferred_set_destroy(struct dm_deferred_set *ds)
328 {
329         kfree(ds);
330 }
331 EXPORT_SYMBOL_GPL(dm_deferred_set_destroy);
332
333 struct dm_deferred_entry *dm_deferred_entry_inc(struct dm_deferred_set *ds)
334 {
335         unsigned long flags;
336         struct dm_deferred_entry *entry;
337
338         spin_lock_irqsave(&ds->lock, flags);
339         entry = ds->entries + ds->current_entry;
340         entry->count++;
341         spin_unlock_irqrestore(&ds->lock, flags);
342
343         return entry;
344 }
345 EXPORT_SYMBOL_GPL(dm_deferred_entry_inc);
346
347 static unsigned ds_next(unsigned index)
348 {
349         return (index + 1) % DEFERRED_SET_SIZE;
350 }
351
352 static void __sweep(struct dm_deferred_set *ds, struct list_head *head)
353 {
354         while ((ds->sweeper != ds->current_entry) &&
355                !ds->entries[ds->sweeper].count) {
356                 list_splice_init(&ds->entries[ds->sweeper].work_items, head);
357                 ds->sweeper = ds_next(ds->sweeper);
358         }
359
360         if ((ds->sweeper == ds->current_entry) && !ds->entries[ds->sweeper].count)
361                 list_splice_init(&ds->entries[ds->sweeper].work_items, head);
362 }
363
364 void dm_deferred_entry_dec(struct dm_deferred_entry *entry, struct list_head *head)
365 {
366         unsigned long flags;
367
368         spin_lock_irqsave(&entry->ds->lock, flags);
369         BUG_ON(!entry->count);
370         --entry->count;
371         __sweep(entry->ds, head);
372         spin_unlock_irqrestore(&entry->ds->lock, flags);
373 }
374 EXPORT_SYMBOL_GPL(dm_deferred_entry_dec);
375
376 /*
377  * Returns 1 if deferred or 0 if no pending items to delay job.
378  */
379 int dm_deferred_set_add_work(struct dm_deferred_set *ds, struct list_head *work)
380 {
381         int r = 1;
382         unsigned long flags;
383         unsigned next_entry;
384
385         spin_lock_irqsave(&ds->lock, flags);
386         if ((ds->sweeper == ds->current_entry) &&
387             !ds->entries[ds->current_entry].count)
388                 r = 0;
389         else {
390                 list_add(work, &ds->entries[ds->current_entry].work_items);
391                 next_entry = ds_next(ds->current_entry);
392                 if (!ds->entries[next_entry].count)
393                         ds->current_entry = next_entry;
394         }
395         spin_unlock_irqrestore(&ds->lock, flags);
396
397         return r;
398 }
399 EXPORT_SYMBOL_GPL(dm_deferred_set_add_work);
400
401 /*----------------------------------------------------------------*/
402
403 static int __init dm_bio_prison_init_v1(void)
404 {
405         _cell_cache = KMEM_CACHE(dm_bio_prison_cell, 0);
406         if (!_cell_cache)
407                 return -ENOMEM;
408
409         return 0;
410 }
411
412 static void dm_bio_prison_exit_v1(void)
413 {
414         kmem_cache_destroy(_cell_cache);
415         _cell_cache = NULL;
416 }
417
418 static int (*_inits[])(void) __initdata = {
419         dm_bio_prison_init_v1,
420         dm_bio_prison_init_v2,
421 };
422
423 static void (*_exits[])(void) = {
424         dm_bio_prison_exit_v1,
425         dm_bio_prison_exit_v2,
426 };
427
428 static int __init dm_bio_prison_init(void)
429 {
430         const int count = ARRAY_SIZE(_inits);
431
432         int r, i;
433
434         for (i = 0; i < count; i++) {
435                 r = _inits[i]();
436                 if (r)
437                         goto bad;
438         }
439
440         return 0;
441
442       bad:
443         while (i--)
444                 _exits[i]();
445
446         return r;
447 }
448
449 static void __exit dm_bio_prison_exit(void)
450 {
451         int i = ARRAY_SIZE(_exits);
452
453         while (i--)
454                 _exits[i]();
455 }
456
457 /*
458  * module hooks
459  */
460 module_init(dm_bio_prison_init);
461 module_exit(dm_bio_prison_exit);
462
463 MODULE_DESCRIPTION(DM_NAME " bio prison");
464 MODULE_AUTHOR("Joe Thornber <dm-devel@redhat.com>");
465 MODULE_LICENSE("GPL");