Commit | Line | Data |
---|---|---|
3bd94003 | 1 | // SPDX-License-Identifier: GPL-2.0-only |
742c8fdc JT |
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; | |
742c8fdc | 25 | struct rb_root cells; |
72d711c8 | 26 | mempool_t cell_pool; |
742c8fdc JT |
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 | { | |
d3775354 | 39 | struct dm_bio_prison_v2 *prison = kzalloc(sizeof(*prison), GFP_KERNEL); |
6f1c819c | 40 | int ret; |
742c8fdc JT |
41 | |
42 | if (!prison) | |
43 | return NULL; | |
44 | ||
45 | prison->wq = wq; | |
46 | spin_lock_init(&prison->lock); | |
47 | ||
6f1c819c KO |
48 | ret = mempool_init_slab_pool(&prison->cell_pool, MIN_CELLS, _cell_cache); |
49 | if (ret) { | |
742c8fdc JT |
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 | ||
60 | void dm_bio_prison_destroy_v2(struct dm_bio_prison_v2 *prison) | |
61 | { | |
6f1c819c | 62 | mempool_exit(&prison->cell_pool); |
742c8fdc JT |
63 | kfree(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 | { | |
6f1c819c | 69 | return mempool_alloc(&prison->cell_pool, gfp); |
742c8fdc JT |
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 | { | |
6f1c819c | 76 | mempool_free(cell, &prison->cell_pool); |
742c8fdc JT |
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(&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 = | |
6e333d0b | 125 | rb_entry(*new, struct dm_bio_prison_cell_v2, node); |
742c8fdc JT |
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 | ||
150 | static bool __get(struct dm_bio_prison_v2 *prison, | |
151 | struct dm_cell_key_v2 *key, | |
86a3238c | 152 | unsigned int lock_level, |
742c8fdc JT |
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 | ||
173 | bool dm_cell_get_v2(struct dm_bio_prison_v2 *prison, | |
174 | struct dm_cell_key_v2 *key, | |
86a3238c | 175 | unsigned int lock_level, |
742c8fdc JT |
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; | |
742c8fdc | 181 | |
235bc861 | 182 | spin_lock_irq(&prison->lock); |
742c8fdc | 183 | r = __get(prison, key, lock_level, inmate, cell_prealloc, cell_result); |
235bc861 | 184 | spin_unlock_irq(&prison->lock); |
742c8fdc JT |
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) { | |
96422281 | 198 | if (cell->exclusive_lock) { |
742c8fdc JT |
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 | ||
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 | ||
226 | static int __lock(struct dm_bio_prison_v2 *prison, | |
227 | struct dm_cell_key_v2 *key, | |
86a3238c | 228 | unsigned int lock_level, |
742c8fdc JT |
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 | ||
257 | int dm_cell_lock_v2(struct dm_bio_prison_v2 *prison, | |
258 | struct dm_cell_key_v2 *key, | |
86a3238c | 259 | unsigned int lock_level, |
742c8fdc JT |
260 | struct dm_bio_prison_cell_v2 *cell_prealloc, |
261 | struct dm_bio_prison_cell_v2 **cell_result) | |
262 | { | |
263 | int r; | |
742c8fdc | 264 | |
235bc861 | 265 | spin_lock_irq(&prison->lock); |
742c8fdc | 266 | r = __lock(prison, key, lock_level, cell_prealloc, cell_result); |
235bc861 | 267 | spin_unlock_irq(&prison->lock); |
742c8fdc JT |
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(prison->wq, 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 | { | |
235bc861 | 287 | spin_lock_irq(&prison->lock); |
742c8fdc | 288 | __quiesce(prison, cell, continuation); |
235bc861 | 289 | spin_unlock_irq(&prison->lock); |
742c8fdc JT |
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, | |
86a3238c | 295 | unsigned int new_lock_level) |
742c8fdc JT |
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, | |
86a3238c | 306 | unsigned int new_lock_level) |
742c8fdc JT |
307 | { |
308 | int r; | |
742c8fdc | 309 | |
235bc861 | 310 | spin_lock_irq(&prison->lock); |
742c8fdc | 311 | r = __promote(prison, cell, new_lock_level); |
235bc861 | 312 | spin_unlock_irq(&prison->lock); |
742c8fdc JT |
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(bios, &cell->bios); | |
325 | bio_list_init(&cell->bios); | |
326 | ||
327 | if (cell->shared_count) { | |
67b92d97 | 328 | cell->exclusive_lock = false; |
742c8fdc JT |
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; | |
742c8fdc | 341 | |
235bc861 | 342 | spin_lock_irq(&prison->lock); |
742c8fdc | 343 | r = __unlock(prison, cell, bios); |
235bc861 | 344 | spin_unlock_irq(&prison->lock); |
742c8fdc JT |
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(_cell_cache); | |
364 | _cell_cache = NULL; | |
365 | } |