1// SPDX-License-Identifier: GPL-2.0-only
2/*
3 * Copyright (C) 2012-2017 Red Hat, Inc.
4 *
5 * This file is released under the GPL.
6 */
7
8#include "dm.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#include <linux/rwsem.h>
16
17/*----------------------------------------------------------------*/
18
19#define MIN_CELLS 1024
20
21struct dm_bio_prison_v2 {
22	struct workqueue_struct *wq;
23
24	spinlock_t lock;
25	struct rb_root cells;
26	mempool_t cell_pool;
27};
28
29static struct kmem_cache *_cell_cache;
30
31/*----------------------------------------------------------------*/
32
33/*
34 * @nr_cells should be the number of cells you want in use _concurrently_.
35 * Don't confuse it with the number of distinct keys.
36 */
37struct dm_bio_prison_v2 *dm_bio_prison_create_v2(struct workqueue_struct *wq)
38{
39	struct dm_bio_prison_v2 *prison = kzalloc(sizeof(*prison), GFP_KERNEL);
40	int ret;
41
42	if (!prison)
43		return NULL;
44
45	prison->wq = wq;
46	spin_lock_init(&prison->lock);
47
48	ret = mempool_init_slab_pool(&prison->cell_pool, MIN_CELLS, _cell_cache);
49	if (ret) {
50		kfree(prison);
51		return NULL;
52	}
53
54	prison->cells = RB_ROOT;
55
56	return prison;
57}
58EXPORT_SYMBOL_GPL(dm_bio_prison_create_v2);
59
60void dm_bio_prison_destroy_v2(struct dm_bio_prison_v2 *prison)
61{
62	mempool_exit(&prison->cell_pool);
63	kfree(prison);
64}
65EXPORT_SYMBOL_GPL(dm_bio_prison_destroy_v2);
66
67struct dm_bio_prison_cell_v2 *dm_bio_prison_alloc_cell_v2(struct dm_bio_prison_v2 *prison, gfp_t gfp)
68{
69	return mempool_alloc(&prison->cell_pool, gfp);
70}
71EXPORT_SYMBOL_GPL(dm_bio_prison_alloc_cell_v2);
72
73void dm_bio_prison_free_cell_v2(struct dm_bio_prison_v2 *prison,
74				struct dm_bio_prison_cell_v2 *cell)
75{
76	mempool_free(cell, &prison->cell_pool);
77}
78EXPORT_SYMBOL_GPL(dm_bio_prison_free_cell_v2);
79
80static void __setup_new_cell(struct dm_cell_key_v2 *key,
81			     struct dm_bio_prison_cell_v2 *cell)
82{
83	memset(cell, 0, sizeof(*cell));
84	memcpy(&cell->key, key, sizeof(cell->key));
85	bio_list_init(&cell->bios);
86}
87
88static int cmp_keys(struct dm_cell_key_v2 *lhs,
89		    struct dm_cell_key_v2 *rhs)
90{
91	if (lhs->virtual < rhs->virtual)
92		return -1;
93
94	if (lhs->virtual > rhs->virtual)
95		return 1;
96
97	if (lhs->dev < rhs->dev)
98		return -1;
99
100	if (lhs->dev > rhs->dev)
101		return 1;
102
103	if (lhs->block_end <= rhs->block_begin)
104		return -1;
105
106	if (lhs->block_begin >= rhs->block_end)
107		return 1;
108
109	return 0;
110}
111
112/*
113 * Returns true if node found, otherwise it inserts a new one.
114 */
115static bool __find_or_insert(struct dm_bio_prison_v2 *prison,
116			     struct dm_cell_key_v2 *key,
117			     struct dm_bio_prison_cell_v2 *cell_prealloc,
118			     struct dm_bio_prison_cell_v2 **result)
119{
120	int r;
121	struct rb_node **new = &prison->cells.rb_node, *parent = NULL;
122
123	while (*new) {
124		struct dm_bio_prison_cell_v2 *cell =
125			rb_entry(*new, struct dm_bio_prison_cell_v2, node);
126
127		r = cmp_keys(key, &cell->key);
128
129		parent = *new;
130		if (r < 0)
131			new = &((*new)->rb_left);
132
133		else if (r > 0)
134			new = &((*new)->rb_right);
135
136		else {
137			*result = cell;
138			return true;
139		}
140	}
141
142	__setup_new_cell(key, cell_prealloc);
143	*result = cell_prealloc;
144	rb_link_node(&cell_prealloc->node, parent, new);
145	rb_insert_color(&cell_prealloc->node, &prison->cells);
146
147	return false;
148}
149
150static bool __get(struct dm_bio_prison_v2 *prison,
151		  struct dm_cell_key_v2 *key,
152		  unsigned int lock_level,
153		  struct bio *inmate,
154		  struct dm_bio_prison_cell_v2 *cell_prealloc,
155		  struct dm_bio_prison_cell_v2 **cell)
156{
157	if (__find_or_insert(prison, key, cell_prealloc, cell)) {
158		if ((*cell)->exclusive_lock) {
159			if (lock_level <= (*cell)->exclusive_level) {
160				bio_list_add(&(*cell)->bios, inmate);
161				return false;
162			}
163		}
164
165		(*cell)->shared_count++;
166
167	} else
168		(*cell)->shared_count = 1;
169
170	return true;
171}
172
173bool dm_cell_get_v2(struct dm_bio_prison_v2 *prison,
174		    struct dm_cell_key_v2 *key,
175		    unsigned int lock_level,
176		    struct bio *inmate,
177		    struct dm_bio_prison_cell_v2 *cell_prealloc,
178		    struct dm_bio_prison_cell_v2 **cell_result)
179{
180	int r;
181
182	spin_lock_irq(&prison->lock);
183	r = __get(prison, key, lock_level, inmate, cell_prealloc, cell_result);
184	spin_unlock_irq(&prison->lock);
185
186	return r;
187}
188EXPORT_SYMBOL_GPL(dm_cell_get_v2);
189
190static bool __put(struct dm_bio_prison_v2 *prison,
191		  struct dm_bio_prison_cell_v2 *cell)
192{
193	BUG_ON(!cell->shared_count);
194	cell->shared_count--;
195
196	// FIXME: shared locks granted above the lock level could starve this
197	if (!cell->shared_count) {
198		if (cell->exclusive_lock) {
199			if (cell->quiesce_continuation) {
200				queue_work(prison->wq, cell->quiesce_continuation);
201				cell->quiesce_continuation = NULL;
202			}
203		} else {
204			rb_erase(&cell->node, &prison->cells);
205			return true;
206		}
207	}
208
209	return false;
210}
211
212bool dm_cell_put_v2(struct dm_bio_prison_v2 *prison,
213		    struct dm_bio_prison_cell_v2 *cell)
214{
215	bool r;
216	unsigned long flags;
217
218	spin_lock_irqsave(&prison->lock, flags);
219	r = __put(prison, cell);
220	spin_unlock_irqrestore(&prison->lock, flags);
221
222	return r;
223}
224EXPORT_SYMBOL_GPL(dm_cell_put_v2);
225
226static int __lock(struct dm_bio_prison_v2 *prison,
227		  struct dm_cell_key_v2 *key,
228		  unsigned int lock_level,
229		  struct dm_bio_prison_cell_v2 *cell_prealloc,
230		  struct dm_bio_prison_cell_v2 **cell_result)
231{
232	struct dm_bio_prison_cell_v2 *cell;
233
234	if (__find_or_insert(prison, key, cell_prealloc, &cell)) {
235		if (cell->exclusive_lock)
236			return -EBUSY;
237
238		cell->exclusive_lock = true;
239		cell->exclusive_level = lock_level;
240		*cell_result = cell;
241
242		// FIXME: we don't yet know what level these shared locks
243		// were taken at, so have to quiesce them all.
244		return cell->shared_count > 0;
245
246	} else {
247		cell = cell_prealloc;
248		cell->shared_count = 0;
249		cell->exclusive_lock = true;
250		cell->exclusive_level = lock_level;
251		*cell_result = cell;
252	}
253
254	return 0;
255}
256
257int dm_cell_lock_v2(struct dm_bio_prison_v2 *prison,
258		    struct dm_cell_key_v2 *key,
259		    unsigned int lock_level,
260		    struct dm_bio_prison_cell_v2 *cell_prealloc,
261		    struct dm_bio_prison_cell_v2 **cell_result)
262{
263	int r;
264
265	spin_lock_irq(&prison->lock);
266	r = __lock(prison, key, lock_level, cell_prealloc, cell_result);
267	spin_unlock_irq(&prison->lock);
268
269	return r;
270}
271EXPORT_SYMBOL_GPL(dm_cell_lock_v2);
272
273static void __quiesce(struct dm_bio_prison_v2 *prison,
274		      struct dm_bio_prison_cell_v2 *cell,
275		      struct work_struct *continuation)
276{
277	if (!cell->shared_count)
278		queue_work(prison->wq, continuation);
279	else
280		cell->quiesce_continuation = continuation;
281}
282
283void dm_cell_quiesce_v2(struct dm_bio_prison_v2 *prison,
284			struct dm_bio_prison_cell_v2 *cell,
285			struct work_struct *continuation)
286{
287	spin_lock_irq(&prison->lock);
288	__quiesce(prison, cell, continuation);
289	spin_unlock_irq(&prison->lock);
290}
291EXPORT_SYMBOL_GPL(dm_cell_quiesce_v2);
292
293static int __promote(struct dm_bio_prison_v2 *prison,
294		     struct dm_bio_prison_cell_v2 *cell,
295		     unsigned int new_lock_level)
296{
297	if (!cell->exclusive_lock)
298		return -EINVAL;
299
300	cell->exclusive_level = new_lock_level;
301	return cell->shared_count > 0;
302}
303
304int dm_cell_lock_promote_v2(struct dm_bio_prison_v2 *prison,
305			    struct dm_bio_prison_cell_v2 *cell,
306			    unsigned int new_lock_level)
307{
308	int r;
309
310	spin_lock_irq(&prison->lock);
311	r = __promote(prison, cell, new_lock_level);
312	spin_unlock_irq(&prison->lock);
313
314	return r;
315}
316EXPORT_SYMBOL_GPL(dm_cell_lock_promote_v2);
317
318static bool __unlock(struct dm_bio_prison_v2 *prison,
319		     struct dm_bio_prison_cell_v2 *cell,
320		     struct bio_list *bios)
321{
322	BUG_ON(!cell->exclusive_lock);
323
324	bio_list_merge(bios, &cell->bios);
325	bio_list_init(&cell->bios);
326
327	if (cell->shared_count) {
328		cell->exclusive_lock = false;
329		return false;
330	}
331
332	rb_erase(&cell->node, &prison->cells);
333	return true;
334}
335
336bool dm_cell_unlock_v2(struct dm_bio_prison_v2 *prison,
337		       struct dm_bio_prison_cell_v2 *cell,
338		       struct bio_list *bios)
339{
340	bool r;
341
342	spin_lock_irq(&prison->lock);
343	r = __unlock(prison, cell, bios);
344	spin_unlock_irq(&prison->lock);
345
346	return r;
347}
348EXPORT_SYMBOL_GPL(dm_cell_unlock_v2);
349
350/*----------------------------------------------------------------*/
351
352int __init dm_bio_prison_init_v2(void)
353{
354	_cell_cache = KMEM_CACHE(dm_bio_prison_cell_v2, 0);
355	if (!_cell_cache)
356		return -ENOMEM;
357
358	return 0;
359}
360
361void dm_bio_prison_exit_v2(void)
362{
363	kmem_cache_destroy(_cell_cache);
364	_cell_cache = NULL;
365}
366