[deliverable/linux.git] / drivers / md / dm-bio-prison.c

/*
 * Copyright (C) 2012 Red Hat, Inc.
 *
 * This file is released under the GPL.
 */

#include "dm.h"
#include "dm-bio-prison.h"

#include <linux/spinlock.h>
#include <linux/mempool.h>
#include <linux/module.h>
#include <linux/slab.h>

/*----------------------------------------------------------------*/

struct dm_bio_prison_cell {
	struct hlist_node list;
	struct dm_bio_prison *prison;
	struct dm_cell_key key;
	struct bio *holder;
	struct bio_list bios;
};

struct dm_bio_prison {
	spinlock_t lock;
	mempool_t *cell_pool;

	unsigned nr_buckets;
	unsigned hash_mask;
	struct hlist_head *cells;
};

/*----------------------------------------------------------------*/

static uint32_t calc_nr_buckets(unsigned nr_cells)
{
	uint32_t n = 128;

	nr_cells /= 4;
	nr_cells = min(nr_cells, 8192u);

	while (n < nr_cells)
		n <<= 1;

	return n;
}

static struct kmem_cache *_cell_cache;

/*
 * @nr_cells should be the number of cells you want in use _concurrently_.
 * Don't confuse it with the number of distinct keys.
 */
struct dm_bio_prison *dm_bio_prison_create(unsigned nr_cells)
{
	unsigned i;
	uint32_t nr_buckets = calc_nr_buckets(nr_cells);
	size_t len = sizeof(struct dm_bio_prison) +
		(sizeof(struct hlist_head) * nr_buckets);
	struct dm_bio_prison *prison = kmalloc(len, GFP_KERNEL);

	if (!prison)
		return NULL;

	spin_lock_init(&prison->lock);
	prison->cell_pool = mempool_create_slab_pool(nr_cells, _cell_cache);
	if (!prison->cell_pool) {
		kfree(prison);
		return NULL;
	}

	prison->nr_buckets = nr_buckets;
	prison->hash_mask = nr_buckets - 1;
	prison->cells = (struct hlist_head *) (prison + 1);
	for (i = 0; i < nr_buckets; i++)
		INIT_HLIST_HEAD(prison->cells + i);

	return prison;
}
EXPORT_SYMBOL_GPL(dm_bio_prison_create);

void dm_bio_prison_destroy(struct dm_bio_prison *prison)
{
	mempool_destroy(prison->cell_pool);
	kfree(prison);
}
EXPORT_SYMBOL_GPL(dm_bio_prison_destroy);

static uint32_t hash_key(struct dm_bio_prison *prison, struct dm_cell_key *key)
{
	const unsigned long BIG_PRIME = 4294967291UL;
	uint64_t hash = key->block * BIG_PRIME;

	return (uint32_t) (hash & prison->hash_mask);
}

static int keys_equal(struct dm_cell_key *lhs, struct dm_cell_key *rhs)
{
	       return (lhs->virtual == rhs->virtual) &&
		       (lhs->dev == rhs->dev) &&
		       (lhs->block == rhs->block);
}

static struct dm_bio_prison_cell *__search_bucket(struct hlist_head *bucket,
						  struct dm_cell_key *key)
{
	struct dm_bio_prison_cell *cell;

	hlist_for_each_entry(cell, bucket, list)
		if (keys_equal(&cell->key, key))
			return cell;

	return NULL;
}

/*
 * This may block if a new cell needs allocating.  You must ensure that
 * cells will be unlocked even if the calling thread is blocked.
 *
 * Returns 1 if the cell was already held, 0 if @inmate is the new holder.
 */
int dm_bio_detain(struct dm_bio_prison *prison, struct dm_cell_key *key,
		  struct bio *inmate, struct dm_bio_prison_cell **ref)
{
	int r = 1;
	unsigned long flags;
	uint32_t hash = hash_key(prison, key);
	struct dm_bio_prison_cell *cell, *cell2;

	BUG_ON(hash > prison->nr_buckets);

	spin_lock_irqsave(&prison->lock, flags);

	cell = __search_bucket(prison->cells + hash, key);
	if (cell) {
		bio_list_add(&cell->bios, inmate);
		goto out;
	}

	/*
	 * Allocate a new cell
	 */
	spin_unlock_irqrestore(&prison->lock, flags);
	cell2 = mempool_alloc(prison->cell_pool, GFP_NOIO);
	spin_lock_irqsave(&prison->lock, flags);

	/*
	 * We've been unlocked, so we have to double check that
	 * nobody else has inserted this cell in the meantime.
	 */
	cell = __search_bucket(prison->cells + hash, key);
	if (cell) {
		mempool_free(cell2, prison->cell_pool);
		bio_list_add(&cell->bios, inmate);
		goto out;
	}

	/*
	 * Use new cell.
	 */
	cell = cell2;

	cell->prison = prison;
	memcpy(&cell->key, key, sizeof(cell->key));
	cell->holder = inmate;
	bio_list_init(&cell->bios);
	hlist_add_head(&cell->list, prison->cells + hash);

	r = 0;

out:
	spin_unlock_irqrestore(&prison->lock, flags);

	*ref = cell;

	return r;
}
EXPORT_SYMBOL_GPL(dm_bio_detain);

/*
 * @inmates must have been initialised prior to this call
 */
static void __cell_release(struct dm_bio_prison_cell *cell, struct bio_list *inmates)
{
	struct dm_bio_prison *prison = cell->prison;

	hlist_del(&cell->list);

	if (inmates) {
		bio_list_add(inmates, cell->holder);
		bio_list_merge(inmates, &cell->bios);
	}

	mempool_free(cell, prison->cell_pool);
}

void dm_cell_release(struct dm_bio_prison_cell *cell, struct bio_list *bios)
{
	unsigned long flags;
	struct dm_bio_prison *prison = cell->prison;

	spin_lock_irqsave(&prison->lock, flags);
	__cell_release(cell, bios);
	spin_unlock_irqrestore(&prison->lock, flags);
}
EXPORT_SYMBOL_GPL(dm_cell_release);

/*
 * Sometimes we don't want the holder, just the additional bios.
 */
static void __cell_release_no_holder(struct dm_bio_prison_cell *cell, struct bio_list *inmates)
{
	struct dm_bio_prison *prison = cell->prison;

	hlist_del(&cell->list);
	bio_list_merge(inmates, &cell->bios);

	mempool_free(cell, prison->cell_pool);
}

void dm_cell_release_no_holder(struct dm_bio_prison_cell *cell, struct bio_list *inmates)
{
	unsigned long flags;
	struct dm_bio_prison *prison = cell->prison;

	spin_lock_irqsave(&prison->lock, flags);
	__cell_release_no_holder(cell, inmates);
	spin_unlock_irqrestore(&prison->lock, flags);
}
EXPORT_SYMBOL_GPL(dm_cell_release_no_holder);

void dm_cell_error(struct dm_bio_prison_cell *cell)
{
	struct dm_bio_prison *prison = cell->prison;
	struct bio_list bios;
	struct bio *bio;
	unsigned long flags;

	bio_list_init(&bios);

	spin_lock_irqsave(&prison->lock, flags);
	__cell_release(cell, &bios);
	spin_unlock_irqrestore(&prison->lock, flags);

	while ((bio = bio_list_pop(&bios)))
		bio_io_error(bio);
}
EXPORT_SYMBOL_GPL(dm_cell_error);

/*----------------------------------------------------------------*/

#define DEFERRED_SET_SIZE 64

struct dm_deferred_entry {
	struct dm_deferred_set *ds;
	unsigned count;
	struct list_head work_items;
};

struct dm_deferred_set {
	spinlock_t lock;
	unsigned current_entry;
	unsigned sweeper;
	struct dm_deferred_entry entries[DEFERRED_SET_SIZE];
};

struct dm_deferred_set *dm_deferred_set_create(void)
{
	int i;
	struct dm_deferred_set *ds;

	ds = kmalloc(sizeof(*ds), GFP_KERNEL);
	if (!ds)
		return NULL;

	spin_lock_init(&ds->lock);
	ds->current_entry = 0;
	ds->sweeper = 0;
	for (i = 0; i < DEFERRED_SET_SIZE; i++) {
		ds->entries[i].ds = ds;
		ds->entries[i].count = 0;
		INIT_LIST_HEAD(&ds->entries[i].work_items);
	}

	return ds;
}
EXPORT_SYMBOL_GPL(dm_deferred_set_create);

void dm_deferred_set_destroy(struct dm_deferred_set *ds)
{
	kfree(ds);
}
EXPORT_SYMBOL_GPL(dm_deferred_set_destroy);

struct dm_deferred_entry *dm_deferred_entry_inc(struct dm_deferred_set *ds)
{
	unsigned long flags;
	struct dm_deferred_entry *entry;

	spin_lock_irqsave(&ds->lock, flags);
	entry = ds->entries + ds->current_entry;
	entry->count++;
	spin_unlock_irqrestore(&ds->lock, flags);

	return entry;
}
EXPORT_SYMBOL_GPL(dm_deferred_entry_inc);

static unsigned ds_next(unsigned index)
{
	return (index + 1) % DEFERRED_SET_SIZE;
}

static void __sweep(struct dm_deferred_set *ds, struct list_head *head)
{
	while ((ds->sweeper != ds->current_entry) &&
	       !ds->entries[ds->sweeper].count) {
		list_splice_init(&ds->entries[ds->sweeper].work_items, head);
		ds->sweeper = ds_next(ds->sweeper);
	}

	if ((ds->sweeper == ds->current_entry) && !ds->entries[ds->sweeper].count)
		list_splice_init(&ds->entries[ds->sweeper].work_items, head);
}

void dm_deferred_entry_dec(struct dm_deferred_entry *entry, struct list_head *head)
{
	unsigned long flags;

	spin_lock_irqsave(&entry->ds->lock, flags);
	BUG_ON(!entry->count);
	--entry->count;
	__sweep(entry->ds, head);
	spin_unlock_irqrestore(&entry->ds->lock, flags);
}
EXPORT_SYMBOL_GPL(dm_deferred_entry_dec);

/*
 * Returns 1 if deferred or 0 if no pending items to delay job.
 */
int dm_deferred_set_add_work(struct dm_deferred_set *ds, struct list_head *work)
{
	int r = 1;
	unsigned long flags;
	unsigned next_entry;

	spin_lock_irqsave(&ds->lock, flags);
	if ((ds->sweeper == ds->current_entry) &&
	    !ds->entries[ds->current_entry].count)
		r = 0;
	else {
		list_add(work, &ds->entries[ds->current_entry].work_items);
		next_entry = ds_next(ds->current_entry);
		if (!ds->entries[next_entry].count)
			ds->current_entry = next_entry;
	}
	spin_unlock_irqrestore(&ds->lock, flags);

	return r;
}
EXPORT_SYMBOL_GPL(dm_deferred_set_add_work);

/*----------------------------------------------------------------*/

static int __init dm_bio_prison_init(void)
{
	_cell_cache = KMEM_CACHE(dm_bio_prison_cell, 0);
	if (!_cell_cache)
		return -ENOMEM;

	return 0;
}

static void __exit dm_bio_prison_exit(void)
{
	kmem_cache_destroy(_cell_cache);
	_cell_cache = NULL;
}

/*
 * module hooks
 */
module_init(dm_bio_prison_init);
module_exit(dm_bio_prison_exit);

MODULE_DESCRIPTION(DM_NAME " bio prison");
MODULE_AUTHOR("Joe Thornber <dm-devel@redhat.com>");
MODULE_LICENSE("GPL");
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;
4f81a417	109
b67bfe0d	110	hlist_for_each_entry(cell, bucket, list)
4f81a417 MS	111	if (keys_equal(&cell->key, key))
	112	return cell;
	113
	114	return NULL;
	115	}
	116
	117	/*
	118	* This may block if a new cell needs allocating. You must ensure that
	119	* cells will be unlocked even if the calling thread is blocked.
	120	*
	121	* Returns 1 if the cell was already held, 0 if @inmate is the new holder.
	122	*/
	123	int dm_bio_detain(struct dm_bio_prison prison, struct dm_cell_key key,
	124	struct bio inmate, struct dm_bio_prison_cell *ref)
	125	{
	126	int r = 1;
	127	unsigned long flags;
	128	uint32_t hash = hash_key(prison, key);
	129	struct dm_bio_prison_cell cell, cell2;
	130
	131	BUG_ON(hash > prison->nr_buckets);
	132
	133	spin_lock_irqsave(&prison->lock, flags);
	134
	135	cell = __search_bucket(prison->cells + hash, key);
	136	if (cell) {
	137	bio_list_add(&cell->bios, inmate);
	138	goto out;
	139	}
	140
	141	/*
	142	* Allocate a new cell
	143	*/
	144	spin_unlock_irqrestore(&prison->lock, flags);
	145	cell2 = mempool_alloc(prison->cell_pool, GFP_NOIO);
	146	spin_lock_irqsave(&prison->lock, flags);
	147
	148	/*
	149	* We've been unlocked, so we have to double check that
	150	* nobody else has inserted this cell in the meantime.
	151	*/
	152	cell = __search_bucket(prison->cells + hash, key);
	153	if (cell) {
	154	mempool_free(cell2, prison->cell_pool);
	155	bio_list_add(&cell->bios, inmate);
	156	goto out;
	157	}
	158
	159	/*
	160	* Use new cell.
	161	*/
	162	cell = cell2;
	163
	164	cell->prison = prison;
	165	memcpy(&cell->key, key, sizeof(cell->key));
	166	cell->holder = inmate;
	167	bio_list_init(&cell->bios);
	168	hlist_add_head(&cell->list, prison->cells + hash);
	169
	170	r = 0;
	171
	172	out:
	173	spin_unlock_irqrestore(&prison->lock, flags);
	174
175	*ref = cell;
176
177	return r;
178	}
179	EXPORT_SYMBOL_GPL(dm_bio_detain);
180
181	/*
182	* @inmates must have been initialised prior to this call
183	*/
184	static void __cell_release(struct dm_bio_prison_cell cell, struct bio_list inmates)
185	{
186	struct dm_bio_prison *prison = cell->prison;
187
188	hlist_del(&cell->list);
189
190	if (inmates) {
191	bio_list_add(inmates, cell->holder);
192	bio_list_merge(inmates, &cell->bios);
193	}
194
195	mempool_free(cell, prison->cell_pool);
196	}
197
198	void dm_cell_release(struct dm_bio_prison_cell cell, struct bio_list bios)
199	{
200	unsigned long flags;
201	struct dm_bio_prison *prison = cell->prison;
202
203	spin_lock_irqsave(&prison->lock, flags);
204	__cell_release(cell, bios);
205	spin_unlock_irqrestore(&prison->lock, flags);
206	}
207	EXPORT_SYMBOL_GPL(dm_cell_release);
208
4f81a417 MS	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_cell cell, struct bio_list inmates)
	213	{
	214	struct dm_bio_prison *prison = cell->prison;
	215
	216	hlist_del(&cell->list);
	217	bio_list_merge(inmates, &cell->bios);
	218
	219	mempool_free(cell, prison->cell_pool);
	220	}
	221
	222	void dm_cell_release_no_holder(struct dm_bio_prison_cell cell, struct bio_list inmates)
	223	{
	224	unsigned long flags;
	225	struct dm_bio_prison *prison = cell->prison;
	226
	227	spin_lock_irqsave(&prison->lock, flags);
	228	__cell_release_no_holder(cell, inmates);
	229	spin_unlock_irqrestore(&prison->lock, flags);
	230	}
	231	EXPORT_SYMBOL_GPL(dm_cell_release_no_holder);
	232
	233	void dm_cell_error(struct dm_bio_prison_cell *cell)
	234	{
	235	struct dm_bio_prison *prison = cell->prison;
	236	struct bio_list bios;
	237	struct bio *bio;
	238	unsigned long flags;
	239
	240	bio_list_init(&bios);
	241
	242	spin_lock_irqsave(&prison->lock, flags);
	243	__cell_release(cell, &bios);
	244	spin_unlock_irqrestore(&prison->lock, flags);
	245
	246	while ((bio = bio_list_pop(&bios)))
	247	bio_io_error(bio);
	248	}
	249	EXPORT_SYMBOL_GPL(dm_cell_error);
	250
	251	/----------------------------------------------------------------/
	252
	253	#define DEFERRED_SET_SIZE 64
	254
	255	struct dm_deferred_entry {
	256	struct dm_deferred_set *ds;
	257	unsigned count;
	258	struct list_head work_items;
	259	};
	260
	261	struct dm_deferred_set {
	262	spinlock_t lock;
	263	unsigned current_entry;
	264	unsigned sweeper;
	265	struct dm_deferred_entry entries[DEFERRED_SET_SIZE];
	266	};
	267
	268	struct dm_deferred_set *dm_deferred_set_create(void)
	269	{
	270	int i;
	271	struct dm_deferred_set *ds;
	272
273	ds = kmalloc(sizeof(*ds), GFP_KERNEL);
274	if (!ds)
275	return NULL;
276
277	spin_lock_init(&ds->lock);
278	ds->current_entry = 0;
279	ds->sweeper = 0;
280	for (i = 0; i < DEFERRED_SET_SIZE; i++) {
281	ds->entries[i].ds = ds;
282	ds->entries[i].count = 0;
283	INIT_LIST_HEAD(&ds->entries[i].work_items);
284	}
285
286	return ds;
287	}
288	EXPORT_SYMBOL_GPL(dm_deferred_set_create);
289
290	void dm_deferred_set_destroy(struct dm_deferred_set *ds)
291	{
292	kfree(ds);
293	}
294	EXPORT_SYMBOL_GPL(dm_deferred_set_destroy);
295
296	struct dm_deferred_entry dm_deferred_entry_inc(struct dm_deferred_set ds)
297	{
298	unsigned long flags;
299	struct dm_deferred_entry *entry;
300
301	spin_lock_irqsave(&ds->lock, flags);
302	entry = ds->entries + ds->current_entry;
303	entry->count++;
304	spin_unlock_irqrestore(&ds->lock, flags);
305
306	return entry;
307	}
308	EXPORT_SYMBOL_GPL(dm_deferred_entry_inc);
309
310	static unsigned ds_next(unsigned index)
311	{
312	return (index + 1) % DEFERRED_SET_SIZE;
313	}
314
315	static void __sweep(struct dm_deferred_set ds, struct list_head head)
316	{
317	while ((ds->sweeper != ds->current_entry) &&
318	!ds->entries[ds->sweeper].count) {
319	list_splice_init(&ds->entries[ds->sweeper].work_items, head);
320	ds->sweeper = ds_next(ds->sweeper);
321	}
322
323	if ((ds->sweeper == ds->current_entry) && !ds->entries[ds->sweeper].count)
324	list_splice_init(&ds->entries[ds->sweeper].work_items, head);
325	}
326
327	void dm_deferred_entry_dec(struct dm_deferred_entry entry, struct list_head head)
328	{
329	unsigned long flags;
330
331	spin_lock_irqsave(&entry->ds->lock, flags);
332	BUG_ON(!entry->count);
333	--entry->count;
334	__sweep(entry->ds, head);
335	spin_unlock_irqrestore(&entry->ds->lock, flags);
336	}
337	EXPORT_SYMBOL_GPL(dm_deferred_entry_dec);
338
339	/*
340	* Returns 1 if deferred or 0 if no pending items to delay job.
341	*/
342	int dm_deferred_set_add_work(struct dm_deferred_set ds, struct list_head work)
343	{
344	int r = 1;
345	unsigned long flags;
346	unsigned next_entry;
347
348	spin_lock_irqsave(&ds->lock, flags);
349	if ((ds->sweeper == ds->current_entry) &&
350	!ds->entries[ds->current_entry].count)
351	r = 0;
352	else {
353	list_add(work, &ds->entries[ds->current_entry].work_items);
354	next_entry = ds_next(ds->current_entry);
355	if (!ds->entries[next_entry].count)
356	ds->current_entry = next_entry;
357	}
358	spin_unlock_irqrestore(&ds->lock, flags);
359
360	return r;
361	}
362	EXPORT_SYMBOL_GPL(dm_deferred_set_add_work);
363
364	/----------------------------------------------------------------/
365
366	static int __init dm_bio_prison_init(void)
367	{
368	_cell_cache = KMEM_CACHE(dm_bio_prison_cell, 0);
369	if (!_cell_cache)
370	return -ENOMEM;
371
372	return 0;
373	}
374
375	static void __exit dm_bio_prison_exit(void)
376	{
377	kmem_cache_destroy(_cell_cache);
378	_cell_cache = NULL;
379	}
380
381	/*
382	* module hooks
383	*/
384	module_init(dm_bio_prison_init);
385	module_exit(dm_bio_prison_exit);
386
387	MODULE_DESCRIPTION(DM_NAME " bio prison");
388	MODULE_AUTHOR("Joe Thornber <dm-devel@redhat.com>");
389	MODULE_LICENSE("GPL");