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 | */ |
37 | struct dm_bio_prison_v2 *dm_bio_prison_create_v2(struct workqueue_struct *wq) |
38 | { |
39 | struct dm_bio_prison_v2 *prison = kzalloc(size: 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(pool: &prison->cell_pool, MIN_CELLS, kc: _cell_cache); |
49 | if (ret) { |
50 | kfree(objp: 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 | |
60 | void dm_bio_prison_destroy_v2(struct dm_bio_prison_v2 *prison) |
61 | { |
62 | mempool_exit(pool: &prison->cell_pool); |
63 | kfree(objp: prison); |
64 | } |
65 | EXPORT_SYMBOL_GPL(dm_bio_prison_destroy_v2); |
66 | |
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(pool: &prison->cell_pool, gfp_mask: gfp); |
70 | } |
71 | EXPORT_SYMBOL_GPL(dm_bio_prison_alloc_cell_v2); |
72 | |
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(element: cell, pool: &prison->cell_pool); |
77 | } |
78 | EXPORT_SYMBOL_GPL(dm_bio_prison_free_cell_v2); |
79 | |
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(bl: &cell->bios); |
86 | } |
87 | |
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 | */ |
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(lhs: key, rhs: &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: cell_prealloc); |
143 | *result = cell_prealloc; |
144 | rb_link_node(node: &cell_prealloc->node, parent, rb_link: new); |
145 | rb_insert_color(&cell_prealloc->node, &prison->cells); |
146 | |
147 | return false; |
148 | } |
149 | |
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, result: cell)) { |
158 | if ((*cell)->exclusive_lock) { |
159 | if (lock_level <= (*cell)->exclusive_level) { |
160 | bio_list_add(bl: &(*cell)->bios, bio: 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 | |
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(lock: &prison->lock); |
183 | r = __get(prison, key, lock_level, inmate, cell_prealloc, cell: cell_result); |
184 | spin_unlock_irq(lock: &prison->lock); |
185 | |
186 | return r; |
187 | } |
188 | EXPORT_SYMBOL_GPL(dm_cell_get_v2); |
189 | |
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(wq: prison->wq, work: 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 | |
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(lock: &prison->lock, flags); |
221 | |
222 | return r; |
223 | } |
224 | EXPORT_SYMBOL_GPL(dm_cell_put_v2); |
225 | |
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, result: &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 | |
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(lock: &prison->lock); |
266 | r = __lock(prison, key, lock_level, cell_prealloc, cell_result); |
267 | spin_unlock_irq(lock: &prison->lock); |
268 | |
269 | return r; |
270 | } |
271 | EXPORT_SYMBOL_GPL(dm_cell_lock_v2); |
272 | |
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(wq: prison->wq, work: continuation); |
279 | else |
280 | cell->quiesce_continuation = continuation; |
281 | } |
282 | |
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(lock: &prison->lock); |
288 | __quiesce(prison, cell, continuation); |
289 | spin_unlock_irq(lock: &prison->lock); |
290 | } |
291 | EXPORT_SYMBOL_GPL(dm_cell_quiesce_v2); |
292 | |
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 | |
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(lock: &prison->lock); |
311 | r = __promote(prison, cell, new_lock_level); |
312 | spin_unlock_irq(lock: &prison->lock); |
313 | |
314 | return r; |
315 | } |
316 | EXPORT_SYMBOL_GPL(dm_cell_lock_promote_v2); |
317 | |
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(bl: bios, bl2: &cell->bios); |
325 | bio_list_init(bl: &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 | |
336 | bool 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(lock: &prison->lock); |
343 | r = __unlock(prison, cell, bios); |
344 | spin_unlock_irq(lock: &prison->lock); |
345 | |
346 | return r; |
347 | } |
348 | EXPORT_SYMBOL_GPL(dm_cell_unlock_v2); |
349 | |
350 | /*----------------------------------------------------------------*/ |
351 | |
352 | int __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 | |
361 | void dm_bio_prison_exit_v2(void) |
362 | { |
363 | kmem_cache_destroy(s: _cell_cache); |
364 | _cell_cache = NULL; |
365 | } |
366 | |