xref: /linux/drivers/md/dm-bio-prison-v2.c (revision 621cde16e49b3ecf7d59a8106a20aaebfb4a59a9)
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 
21 struct 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 
29 static 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  */
dm_bio_prison_create_v2(struct workqueue_struct * wq)37 struct 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 }
58 EXPORT_SYMBOL_GPL(dm_bio_prison_create_v2);
59 
dm_bio_prison_destroy_v2(struct dm_bio_prison_v2 * prison)60 void dm_bio_prison_destroy_v2(struct dm_bio_prison_v2 *prison)
61 {
62 	mempool_exit(&prison->cell_pool);
63 	kfree(prison);
64 }
65 EXPORT_SYMBOL_GPL(dm_bio_prison_destroy_v2);
66 
dm_bio_prison_alloc_cell_v2(struct dm_bio_prison_v2 * prison,gfp_t gfp)67 struct 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 }
71 EXPORT_SYMBOL_GPL(dm_bio_prison_alloc_cell_v2);
72 
dm_bio_prison_free_cell_v2(struct dm_bio_prison_v2 * prison,struct dm_bio_prison_cell_v2 * cell)73 void 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 }
78 EXPORT_SYMBOL_GPL(dm_bio_prison_free_cell_v2);
79 
__setup_new_cell(struct dm_cell_key_v2 * key,struct dm_bio_prison_cell_v2 * cell)80 static 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 
cmp_keys(struct dm_cell_key_v2 * lhs,struct dm_cell_key_v2 * rhs)88 static 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  */
__find_or_insert(struct dm_bio_prison_v2 * prison,struct dm_cell_key_v2 * key,struct dm_bio_prison_cell_v2 * cell_prealloc,struct dm_bio_prison_cell_v2 ** result)115 static 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 
__get(struct dm_bio_prison_v2 * prison,struct dm_cell_key_v2 * key,unsigned int lock_level,struct bio * inmate,struct dm_bio_prison_cell_v2 * cell_prealloc,struct dm_bio_prison_cell_v2 ** cell)150 static 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 
dm_cell_get_v2(struct dm_bio_prison_v2 * prison,struct dm_cell_key_v2 * key,unsigned int lock_level,struct bio * inmate,struct dm_bio_prison_cell_v2 * cell_prealloc,struct dm_bio_prison_cell_v2 ** cell_result)173 bool 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 }
188 EXPORT_SYMBOL_GPL(dm_cell_get_v2);
189 
__put(struct dm_bio_prison_v2 * prison,struct dm_bio_prison_cell_v2 * cell)190 static 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 
dm_cell_put_v2(struct dm_bio_prison_v2 * prison,struct dm_bio_prison_cell_v2 * cell)212 bool 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 }
224 EXPORT_SYMBOL_GPL(dm_cell_put_v2);
225 
__lock(struct dm_bio_prison_v2 * prison,struct dm_cell_key_v2 * key,unsigned int lock_level,struct dm_bio_prison_cell_v2 * cell_prealloc,struct dm_bio_prison_cell_v2 ** cell_result)226 static 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 
dm_cell_lock_v2(struct dm_bio_prison_v2 * prison,struct dm_cell_key_v2 * key,unsigned int lock_level,struct dm_bio_prison_cell_v2 * cell_prealloc,struct dm_bio_prison_cell_v2 ** cell_result)257 int 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 }
271 EXPORT_SYMBOL_GPL(dm_cell_lock_v2);
272 
__quiesce(struct dm_bio_prison_v2 * prison,struct dm_bio_prison_cell_v2 * cell,struct work_struct * continuation)273 static 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 
dm_cell_quiesce_v2(struct dm_bio_prison_v2 * prison,struct dm_bio_prison_cell_v2 * cell,struct work_struct * continuation)283 void 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 }
291 EXPORT_SYMBOL_GPL(dm_cell_quiesce_v2);
292 
__promote(struct dm_bio_prison_v2 * prison,struct dm_bio_prison_cell_v2 * cell,unsigned int new_lock_level)293 static 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 
dm_cell_lock_promote_v2(struct dm_bio_prison_v2 * prison,struct dm_bio_prison_cell_v2 * cell,unsigned int new_lock_level)304 int 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 }
316 EXPORT_SYMBOL_GPL(dm_cell_lock_promote_v2);
317 
__unlock(struct dm_bio_prison_v2 * prison,struct dm_bio_prison_cell_v2 * cell,struct bio_list * bios)318 static 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_init(bios, &cell->bios);
325 
326 	if (cell->shared_count) {
327 		cell->exclusive_lock = false;
328 		return false;
329 	}
330 
331 	rb_erase(&cell->node, &prison->cells);
332 	return true;
333 }
334 
dm_cell_unlock_v2(struct dm_bio_prison_v2 * prison,struct dm_bio_prison_cell_v2 * cell,struct bio_list * bios)335 bool dm_cell_unlock_v2(struct dm_bio_prison_v2 *prison,
336 		       struct dm_bio_prison_cell_v2 *cell,
337 		       struct bio_list *bios)
338 {
339 	bool r;
340 
341 	spin_lock_irq(&prison->lock);
342 	r = __unlock(prison, cell, bios);
343 	spin_unlock_irq(&prison->lock);
344 
345 	return r;
346 }
347 EXPORT_SYMBOL_GPL(dm_cell_unlock_v2);
348 
349 /*----------------------------------------------------------------*/
350 
dm_bio_prison_init_v2(void)351 int __init dm_bio_prison_init_v2(void)
352 {
353 	_cell_cache = KMEM_CACHE(dm_bio_prison_cell_v2, 0);
354 	if (!_cell_cache)
355 		return -ENOMEM;
356 
357 	return 0;
358 }
359 
dm_bio_prison_exit_v2(void)360 void dm_bio_prison_exit_v2(void)
361 {
362 	kmem_cache_destroy(_cell_cache);
363 	_cell_cache = NULL;
364 }
365