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#define MIN_CELLS 1024
18
19struct dm_bio_prison {
20	spinlock_t lock;
21	mempool_t *cell_pool;
22	struct rb_root cells;
23};
24
25static struct kmem_cache *_cell_cache;
26
27/*----------------------------------------------------------------*/
28
29/*
30 * @nr_cells should be the number of cells you want in use _concurrently_.
31 * Don't confuse it with the number of distinct keys.
32 */
33struct dm_bio_prison *dm_bio_prison_create(void)
34{
35	struct dm_bio_prison *prison = kmalloc(sizeof(*prison), GFP_KERNEL);
36
37	if (!prison)
38		return NULL;
39
40	spin_lock_init(&prison->lock);
41
42	prison->cell_pool = mempool_create_slab_pool(MIN_CELLS, _cell_cache);
43	if (!prison->cell_pool) {
44		kfree(prison);
45		return NULL;
46	}
47
48	prison->cells = RB_ROOT;
49
50	return prison;
51}
52EXPORT_SYMBOL_GPL(dm_bio_prison_create);
53
54void dm_bio_prison_destroy(struct dm_bio_prison *prison)
55{
56	mempool_destroy(prison->cell_pool);
57	kfree(prison);
58}
59EXPORT_SYMBOL_GPL(dm_bio_prison_destroy);
60
61struct dm_bio_prison_cell *dm_bio_prison_alloc_cell(struct dm_bio_prison *prison, gfp_t gfp)
62{
63	return mempool_alloc(prison->cell_pool, gfp);
64}
65EXPORT_SYMBOL_GPL(dm_bio_prison_alloc_cell);
66
67void dm_bio_prison_free_cell(struct dm_bio_prison *prison,
68			     struct dm_bio_prison_cell *cell)
69{
70	mempool_free(cell, prison->cell_pool);
71}
72EXPORT_SYMBOL_GPL(dm_bio_prison_free_cell);
73
74static void __setup_new_cell(struct dm_cell_key *key,
75			     struct bio *holder,
76			     struct dm_bio_prison_cell *cell)
77{
78       memcpy(&cell->key, key, sizeof(cell->key));
79       cell->holder = holder;
80       bio_list_init(&cell->bios);
81}
82
83static int cmp_keys(struct dm_cell_key *lhs,
84		    struct dm_cell_key *rhs)
85{
86	if (lhs->virtual < rhs->virtual)
87		return -1;
88
89	if (lhs->virtual > rhs->virtual)
90		return 1;
91
92	if (lhs->dev < rhs->dev)
93		return -1;
94
95	if (lhs->dev > rhs->dev)
96		return 1;
97
98	if (lhs->block_end <= rhs->block_begin)
99		return -1;
100
101	if (lhs->block_begin >= rhs->block_end)
102		return 1;
103
104	return 0;
105}
106
107static int __bio_detain(struct dm_bio_prison *prison,
108			struct dm_cell_key *key,
109			struct bio *inmate,
110			struct dm_bio_prison_cell *cell_prealloc,
111			struct dm_bio_prison_cell **cell_result)
112{
113	int r;
114	struct rb_node **new = &prison->cells.rb_node, *parent = NULL;
115
116	while (*new) {
117		struct dm_bio_prison_cell *cell =
118			container_of(*new, struct dm_bio_prison_cell, node);
119
120		r = cmp_keys(key, &cell->key);
121
122		parent = *new;
123		if (r < 0)
124			new = &((*new)->rb_left);
125		else if (r > 0)
126			new = &((*new)->rb_right);
127		else {
128			if (inmate)
129				bio_list_add(&cell->bios, inmate);
130			*cell_result = cell;
131			return 1;
132		}
133	}
134
135	__setup_new_cell(key, inmate, cell_prealloc);
136	*cell_result = cell_prealloc;
137
138	rb_link_node(&cell_prealloc->node, parent, new);
139	rb_insert_color(&cell_prealloc->node, &prison->cells);
140
141	return 0;
142}
143
144static int bio_detain(struct dm_bio_prison *prison,
145		      struct dm_cell_key *key,
146		      struct bio *inmate,
147		      struct dm_bio_prison_cell *cell_prealloc,
148		      struct dm_bio_prison_cell **cell_result)
149{
150	int r;
151	unsigned long flags;
152
153	spin_lock_irqsave(&prison->lock, flags);
154	r = __bio_detain(prison, key, inmate, cell_prealloc, cell_result);
155	spin_unlock_irqrestore(&prison->lock, flags);
156
157	return r;
158}
159
160int dm_bio_detain(struct dm_bio_prison *prison,
161		  struct dm_cell_key *key,
162		  struct bio *inmate,
163		  struct dm_bio_prison_cell *cell_prealloc,
164		  struct dm_bio_prison_cell **cell_result)
165{
166	return bio_detain(prison, key, inmate, cell_prealloc, cell_result);
167}
168EXPORT_SYMBOL_GPL(dm_bio_detain);
169
170int dm_get_cell(struct dm_bio_prison *prison,
171		struct dm_cell_key *key,
172		struct dm_bio_prison_cell *cell_prealloc,
173		struct dm_bio_prison_cell **cell_result)
174{
175	return bio_detain(prison, key, NULL, cell_prealloc, cell_result);
176}
177EXPORT_SYMBOL_GPL(dm_get_cell);
178
179/*
180 * @inmates must have been initialised prior to this call
181 */
182static void __cell_release(struct dm_bio_prison *prison,
183			   struct dm_bio_prison_cell *cell,
184			   struct bio_list *inmates)
185{
186	rb_erase(&cell->node, &prison->cells);
187
188	if (inmates) {
189		if (cell->holder)
190			bio_list_add(inmates, cell->holder);
191		bio_list_merge(inmates, &cell->bios);
192	}
193}
194
195void dm_cell_release(struct dm_bio_prison *prison,
196		     struct dm_bio_prison_cell *cell,
197		     struct bio_list *bios)
198{
199	unsigned long flags;
200
201	spin_lock_irqsave(&prison->lock, flags);
202	__cell_release(prison, cell, bios);
203	spin_unlock_irqrestore(&prison->lock, flags);
204}
205EXPORT_SYMBOL_GPL(dm_cell_release);
206
207/*
208 * Sometimes we don't want the holder, just the additional bios.
209 */
210static void __cell_release_no_holder(struct dm_bio_prison *prison,
211				     struct dm_bio_prison_cell *cell,
212				     struct bio_list *inmates)
213{
214	rb_erase(&cell->node, &prison->cells);
215	bio_list_merge(inmates, &cell->bios);
216}
217
218void dm_cell_release_no_holder(struct dm_bio_prison *prison,
219			       struct dm_bio_prison_cell *cell,
220			       struct bio_list *inmates)
221{
222	unsigned long flags;
223
224	spin_lock_irqsave(&prison->lock, flags);
225	__cell_release_no_holder(prison, cell, inmates);
226	spin_unlock_irqrestore(&prison->lock, flags);
227}
228EXPORT_SYMBOL_GPL(dm_cell_release_no_holder);
229
230void dm_cell_error(struct dm_bio_prison *prison,
231		   struct dm_bio_prison_cell *cell, int error)
232{
233	struct bio_list bios;
234	struct bio *bio;
235
236	bio_list_init(&bios);
237	dm_cell_release(prison, cell, &bios);
238
239	while ((bio = bio_list_pop(&bios)))
240		bio_endio(bio, error);
241}
242EXPORT_SYMBOL_GPL(dm_cell_error);
243
244void dm_cell_visit_release(struct dm_bio_prison *prison,
245			   void (*visit_fn)(void *, struct dm_bio_prison_cell *),
246			   void *context,
247			   struct dm_bio_prison_cell *cell)
248{
249	unsigned long flags;
250
251	spin_lock_irqsave(&prison->lock, flags);
252	visit_fn(context, cell);
253	rb_erase(&cell->node, &prison->cells);
254	spin_unlock_irqrestore(&prison->lock, flags);
255}
256EXPORT_SYMBOL_GPL(dm_cell_visit_release);
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