1 | // SPDX-License-Identifier: GPL-2.0-only |
2 | /* |
3 | * Copyright (C) 2011 Red Hat, Inc. |
4 | * |
5 | * This file is released under the GPL. |
6 | */ |
7 | #include "dm-transaction-manager.h" |
8 | #include "dm-space-map.h" |
9 | #include "dm-space-map-disk.h" |
10 | #include "dm-space-map-metadata.h" |
11 | #include "dm-persistent-data-internal.h" |
12 | |
13 | #include <linux/export.h> |
14 | #include <linux/mutex.h> |
15 | #include <linux/hash.h> |
16 | #include <linux/slab.h> |
17 | #include <linux/device-mapper.h> |
18 | |
19 | #define DM_MSG_PREFIX "transaction manager" |
20 | |
21 | /*----------------------------------------------------------------*/ |
22 | |
23 | #define PREFETCH_SIZE 128 |
24 | #define PREFETCH_BITS 7 |
25 | #define PREFETCH_SENTINEL ((dm_block_t) -1ULL) |
26 | |
27 | struct prefetch_set { |
28 | struct mutex lock; |
29 | dm_block_t blocks[PREFETCH_SIZE]; |
30 | }; |
31 | |
32 | static unsigned int prefetch_hash(dm_block_t b) |
33 | { |
34 | return hash_64(val: b, PREFETCH_BITS); |
35 | } |
36 | |
37 | static void prefetch_wipe(struct prefetch_set *p) |
38 | { |
39 | unsigned int i; |
40 | |
41 | for (i = 0; i < PREFETCH_SIZE; i++) |
42 | p->blocks[i] = PREFETCH_SENTINEL; |
43 | } |
44 | |
45 | static void prefetch_init(struct prefetch_set *p) |
46 | { |
47 | mutex_init(&p->lock); |
48 | prefetch_wipe(p); |
49 | } |
50 | |
51 | static void prefetch_add(struct prefetch_set *p, dm_block_t b) |
52 | { |
53 | unsigned int h = prefetch_hash(b); |
54 | |
55 | mutex_lock(&p->lock); |
56 | if (p->blocks[h] == PREFETCH_SENTINEL) |
57 | p->blocks[h] = b; |
58 | |
59 | mutex_unlock(lock: &p->lock); |
60 | } |
61 | |
62 | static void prefetch_issue(struct prefetch_set *p, struct dm_block_manager *bm) |
63 | { |
64 | unsigned int i; |
65 | |
66 | mutex_lock(&p->lock); |
67 | |
68 | for (i = 0; i < PREFETCH_SIZE; i++) |
69 | if (p->blocks[i] != PREFETCH_SENTINEL) { |
70 | dm_bm_prefetch(bm, b: p->blocks[i]); |
71 | p->blocks[i] = PREFETCH_SENTINEL; |
72 | } |
73 | |
74 | mutex_unlock(lock: &p->lock); |
75 | } |
76 | |
77 | /*----------------------------------------------------------------*/ |
78 | |
79 | struct shadow_info { |
80 | struct hlist_node hlist; |
81 | dm_block_t where; |
82 | }; |
83 | |
84 | /* |
85 | * It would be nice if we scaled with the size of transaction. |
86 | */ |
87 | #define DM_HASH_SIZE 256 |
88 | #define DM_HASH_MASK (DM_HASH_SIZE - 1) |
89 | |
90 | struct dm_transaction_manager { |
91 | int is_clone; |
92 | struct dm_transaction_manager *real; |
93 | |
94 | struct dm_block_manager *bm; |
95 | struct dm_space_map *sm; |
96 | |
97 | spinlock_t lock; |
98 | struct hlist_head buckets[DM_HASH_SIZE]; |
99 | |
100 | struct prefetch_set prefetches; |
101 | }; |
102 | |
103 | /*----------------------------------------------------------------*/ |
104 | |
105 | static int is_shadow(struct dm_transaction_manager *tm, dm_block_t b) |
106 | { |
107 | int r = 0; |
108 | unsigned int bucket = dm_hash_block(b, DM_HASH_MASK); |
109 | struct shadow_info *si; |
110 | |
111 | spin_lock(lock: &tm->lock); |
112 | hlist_for_each_entry(si, tm->buckets + bucket, hlist) |
113 | if (si->where == b) { |
114 | r = 1; |
115 | break; |
116 | } |
117 | spin_unlock(lock: &tm->lock); |
118 | |
119 | return r; |
120 | } |
121 | |
122 | /* |
123 | * This can silently fail if there's no memory. We're ok with this since |
124 | * creating redundant shadows causes no harm. |
125 | */ |
126 | static void insert_shadow(struct dm_transaction_manager *tm, dm_block_t b) |
127 | { |
128 | unsigned int bucket; |
129 | struct shadow_info *si; |
130 | |
131 | si = kmalloc(size: sizeof(*si), GFP_NOIO); |
132 | if (si) { |
133 | si->where = b; |
134 | bucket = dm_hash_block(b, DM_HASH_MASK); |
135 | spin_lock(lock: &tm->lock); |
136 | hlist_add_head(n: &si->hlist, h: tm->buckets + bucket); |
137 | spin_unlock(lock: &tm->lock); |
138 | } |
139 | } |
140 | |
141 | static void wipe_shadow_table(struct dm_transaction_manager *tm) |
142 | { |
143 | struct shadow_info *si; |
144 | struct hlist_node *tmp; |
145 | struct hlist_head *bucket; |
146 | int i; |
147 | |
148 | spin_lock(lock: &tm->lock); |
149 | for (i = 0; i < DM_HASH_SIZE; i++) { |
150 | bucket = tm->buckets + i; |
151 | hlist_for_each_entry_safe(si, tmp, bucket, hlist) |
152 | kfree(objp: si); |
153 | |
154 | INIT_HLIST_HEAD(bucket); |
155 | } |
156 | |
157 | spin_unlock(lock: &tm->lock); |
158 | } |
159 | |
160 | /*----------------------------------------------------------------*/ |
161 | |
162 | static struct dm_transaction_manager *dm_tm_create(struct dm_block_manager *bm, |
163 | struct dm_space_map *sm) |
164 | { |
165 | int i; |
166 | struct dm_transaction_manager *tm; |
167 | |
168 | tm = kmalloc(size: sizeof(*tm), GFP_KERNEL); |
169 | if (!tm) |
170 | return ERR_PTR(error: -ENOMEM); |
171 | |
172 | tm->is_clone = 0; |
173 | tm->real = NULL; |
174 | tm->bm = bm; |
175 | tm->sm = sm; |
176 | |
177 | spin_lock_init(&tm->lock); |
178 | for (i = 0; i < DM_HASH_SIZE; i++) |
179 | INIT_HLIST_HEAD(tm->buckets + i); |
180 | |
181 | prefetch_init(p: &tm->prefetches); |
182 | |
183 | return tm; |
184 | } |
185 | |
186 | struct dm_transaction_manager *dm_tm_create_non_blocking_clone(struct dm_transaction_manager *real) |
187 | { |
188 | struct dm_transaction_manager *tm; |
189 | |
190 | tm = kmalloc(size: sizeof(*tm), GFP_KERNEL); |
191 | if (tm) { |
192 | tm->is_clone = 1; |
193 | tm->real = real; |
194 | } |
195 | |
196 | return tm; |
197 | } |
198 | EXPORT_SYMBOL_GPL(dm_tm_create_non_blocking_clone); |
199 | |
200 | void dm_tm_destroy(struct dm_transaction_manager *tm) |
201 | { |
202 | if (!tm) |
203 | return; |
204 | |
205 | if (!tm->is_clone) |
206 | wipe_shadow_table(tm); |
207 | |
208 | kfree(objp: tm); |
209 | } |
210 | EXPORT_SYMBOL_GPL(dm_tm_destroy); |
211 | |
212 | int dm_tm_pre_commit(struct dm_transaction_manager *tm) |
213 | { |
214 | int r; |
215 | |
216 | if (tm->is_clone) |
217 | return -EWOULDBLOCK; |
218 | |
219 | r = dm_sm_commit(sm: tm->sm); |
220 | if (r < 0) |
221 | return r; |
222 | |
223 | return dm_bm_flush(bm: tm->bm); |
224 | } |
225 | EXPORT_SYMBOL_GPL(dm_tm_pre_commit); |
226 | |
227 | int dm_tm_commit(struct dm_transaction_manager *tm, struct dm_block *root) |
228 | { |
229 | if (tm->is_clone) |
230 | return -EWOULDBLOCK; |
231 | |
232 | wipe_shadow_table(tm); |
233 | dm_bm_unlock(b: root); |
234 | |
235 | return dm_bm_flush(bm: tm->bm); |
236 | } |
237 | EXPORT_SYMBOL_GPL(dm_tm_commit); |
238 | |
239 | int dm_tm_new_block(struct dm_transaction_manager *tm, |
240 | struct dm_block_validator *v, |
241 | struct dm_block **result) |
242 | { |
243 | int r; |
244 | dm_block_t new_block; |
245 | |
246 | if (tm->is_clone) |
247 | return -EWOULDBLOCK; |
248 | |
249 | r = dm_sm_new_block(sm: tm->sm, b: &new_block); |
250 | if (r < 0) |
251 | return r; |
252 | |
253 | r = dm_bm_write_lock_zero(bm: tm->bm, b: new_block, v, result); |
254 | if (r < 0) { |
255 | dm_sm_dec_block(sm: tm->sm, b: new_block); |
256 | return r; |
257 | } |
258 | |
259 | /* |
260 | * New blocks count as shadows in that they don't need to be |
261 | * shadowed again. |
262 | */ |
263 | insert_shadow(tm, b: new_block); |
264 | |
265 | return 0; |
266 | } |
267 | |
268 | static int __shadow_block(struct dm_transaction_manager *tm, dm_block_t orig, |
269 | struct dm_block_validator *v, |
270 | struct dm_block **result) |
271 | { |
272 | int r; |
273 | dm_block_t new; |
274 | struct dm_block *orig_block; |
275 | |
276 | r = dm_sm_new_block(sm: tm->sm, b: &new); |
277 | if (r < 0) |
278 | return r; |
279 | |
280 | r = dm_sm_dec_block(sm: tm->sm, b: orig); |
281 | if (r < 0) |
282 | return r; |
283 | |
284 | r = dm_bm_read_lock(bm: tm->bm, b: orig, v, result: &orig_block); |
285 | if (r < 0) |
286 | return r; |
287 | |
288 | /* |
289 | * It would be tempting to use dm_bm_unlock_move here, but some |
290 | * code, such as the space maps, keeps using the old data structures |
291 | * secure in the knowledge they won't be changed until the next |
292 | * transaction. Using unlock_move would force a synchronous read |
293 | * since the old block would no longer be in the cache. |
294 | */ |
295 | r = dm_bm_write_lock_zero(bm: tm->bm, b: new, v, result); |
296 | if (r) { |
297 | dm_bm_unlock(b: orig_block); |
298 | return r; |
299 | } |
300 | |
301 | memcpy(dm_block_data(*result), dm_block_data(orig_block), |
302 | dm_bm_block_size(tm->bm)); |
303 | |
304 | dm_bm_unlock(b: orig_block); |
305 | return r; |
306 | } |
307 | |
308 | int dm_tm_shadow_block(struct dm_transaction_manager *tm, dm_block_t orig, |
309 | struct dm_block_validator *v, struct dm_block **result, |
310 | int *inc_children) |
311 | { |
312 | int r; |
313 | |
314 | if (tm->is_clone) |
315 | return -EWOULDBLOCK; |
316 | |
317 | r = dm_sm_count_is_more_than_one(sm: tm->sm, b: orig, result: inc_children); |
318 | if (r < 0) |
319 | return r; |
320 | |
321 | if (is_shadow(tm, b: orig) && !*inc_children) |
322 | return dm_bm_write_lock(bm: tm->bm, b: orig, v, result); |
323 | |
324 | r = __shadow_block(tm, orig, v, result); |
325 | if (r < 0) |
326 | return r; |
327 | insert_shadow(tm, b: dm_block_location(b: *result)); |
328 | |
329 | return r; |
330 | } |
331 | EXPORT_SYMBOL_GPL(dm_tm_shadow_block); |
332 | |
333 | int dm_tm_read_lock(struct dm_transaction_manager *tm, dm_block_t b, |
334 | struct dm_block_validator *v, |
335 | struct dm_block **blk) |
336 | { |
337 | if (tm->is_clone) { |
338 | int r = dm_bm_read_try_lock(bm: tm->real->bm, b, v, result: blk); |
339 | |
340 | if (r == -EWOULDBLOCK) |
341 | prefetch_add(p: &tm->real->prefetches, b); |
342 | |
343 | return r; |
344 | } |
345 | |
346 | return dm_bm_read_lock(bm: tm->bm, b, v, result: blk); |
347 | } |
348 | EXPORT_SYMBOL_GPL(dm_tm_read_lock); |
349 | |
350 | void dm_tm_unlock(struct dm_transaction_manager *tm, struct dm_block *b) |
351 | { |
352 | dm_bm_unlock(b); |
353 | } |
354 | EXPORT_SYMBOL_GPL(dm_tm_unlock); |
355 | |
356 | void dm_tm_inc(struct dm_transaction_manager *tm, dm_block_t b) |
357 | { |
358 | /* |
359 | * The non-blocking clone doesn't support this. |
360 | */ |
361 | BUG_ON(tm->is_clone); |
362 | |
363 | dm_sm_inc_block(sm: tm->sm, b); |
364 | } |
365 | EXPORT_SYMBOL_GPL(dm_tm_inc); |
366 | |
367 | void dm_tm_inc_range(struct dm_transaction_manager *tm, dm_block_t b, dm_block_t e) |
368 | { |
369 | /* |
370 | * The non-blocking clone doesn't support this. |
371 | */ |
372 | BUG_ON(tm->is_clone); |
373 | |
374 | dm_sm_inc_blocks(sm: tm->sm, b, e); |
375 | } |
376 | EXPORT_SYMBOL_GPL(dm_tm_inc_range); |
377 | |
378 | void dm_tm_dec(struct dm_transaction_manager *tm, dm_block_t b) |
379 | { |
380 | /* |
381 | * The non-blocking clone doesn't support this. |
382 | */ |
383 | BUG_ON(tm->is_clone); |
384 | |
385 | dm_sm_dec_block(sm: tm->sm, b); |
386 | } |
387 | EXPORT_SYMBOL_GPL(dm_tm_dec); |
388 | |
389 | void dm_tm_dec_range(struct dm_transaction_manager *tm, dm_block_t b, dm_block_t e) |
390 | { |
391 | /* |
392 | * The non-blocking clone doesn't support this. |
393 | */ |
394 | BUG_ON(tm->is_clone); |
395 | |
396 | dm_sm_dec_blocks(sm: tm->sm, b, e); |
397 | } |
398 | EXPORT_SYMBOL_GPL(dm_tm_dec_range); |
399 | |
400 | void dm_tm_with_runs(struct dm_transaction_manager *tm, |
401 | const __le64 *value_le, unsigned int count, dm_tm_run_fn fn) |
402 | { |
403 | uint64_t b, begin, end; |
404 | bool in_run = false; |
405 | unsigned int i; |
406 | |
407 | for (i = 0; i < count; i++, value_le++) { |
408 | b = le64_to_cpu(*value_le); |
409 | |
410 | if (in_run) { |
411 | if (b == end) |
412 | end++; |
413 | else { |
414 | fn(tm, begin, end); |
415 | begin = b; |
416 | end = b + 1; |
417 | } |
418 | } else { |
419 | in_run = true; |
420 | begin = b; |
421 | end = b + 1; |
422 | } |
423 | } |
424 | |
425 | if (in_run) |
426 | fn(tm, begin, end); |
427 | } |
428 | EXPORT_SYMBOL_GPL(dm_tm_with_runs); |
429 | |
430 | int dm_tm_ref(struct dm_transaction_manager *tm, dm_block_t b, |
431 | uint32_t *result) |
432 | { |
433 | if (tm->is_clone) |
434 | return -EWOULDBLOCK; |
435 | |
436 | return dm_sm_get_count(sm: tm->sm, b, result); |
437 | } |
438 | |
439 | int dm_tm_block_is_shared(struct dm_transaction_manager *tm, dm_block_t b, |
440 | int *result) |
441 | { |
442 | if (tm->is_clone) |
443 | return -EWOULDBLOCK; |
444 | |
445 | return dm_sm_count_is_more_than_one(sm: tm->sm, b, result); |
446 | } |
447 | |
448 | struct dm_block_manager *dm_tm_get_bm(struct dm_transaction_manager *tm) |
449 | { |
450 | return tm->bm; |
451 | } |
452 | |
453 | void dm_tm_issue_prefetches(struct dm_transaction_manager *tm) |
454 | { |
455 | prefetch_issue(p: &tm->prefetches, bm: tm->bm); |
456 | } |
457 | EXPORT_SYMBOL_GPL(dm_tm_issue_prefetches); |
458 | |
459 | /*----------------------------------------------------------------*/ |
460 | |
461 | static int dm_tm_create_internal(struct dm_block_manager *bm, |
462 | dm_block_t sb_location, |
463 | struct dm_transaction_manager **tm, |
464 | struct dm_space_map **sm, |
465 | int create, |
466 | void *sm_root, size_t sm_len) |
467 | { |
468 | int r; |
469 | |
470 | *sm = dm_sm_metadata_init(); |
471 | if (IS_ERR(ptr: *sm)) |
472 | return PTR_ERR(ptr: *sm); |
473 | |
474 | *tm = dm_tm_create(bm, sm: *sm); |
475 | if (IS_ERR(ptr: *tm)) { |
476 | dm_sm_destroy(sm: *sm); |
477 | return PTR_ERR(ptr: *tm); |
478 | } |
479 | |
480 | if (create) { |
481 | r = dm_sm_metadata_create(sm: *sm, tm: *tm, nr_blocks: dm_bm_nr_blocks(bm), |
482 | superblock: sb_location); |
483 | if (r) { |
484 | DMERR("couldn't create metadata space map" ); |
485 | goto bad; |
486 | } |
487 | |
488 | } else { |
489 | r = dm_sm_metadata_open(sm: *sm, tm: *tm, root_le: sm_root, len: sm_len); |
490 | if (r) { |
491 | DMERR("couldn't open metadata space map" ); |
492 | goto bad; |
493 | } |
494 | } |
495 | |
496 | return 0; |
497 | |
498 | bad: |
499 | dm_tm_destroy(*tm); |
500 | dm_sm_destroy(sm: *sm); |
501 | return r; |
502 | } |
503 | |
504 | int dm_tm_create_with_sm(struct dm_block_manager *bm, dm_block_t sb_location, |
505 | struct dm_transaction_manager **tm, |
506 | struct dm_space_map **sm) |
507 | { |
508 | return dm_tm_create_internal(bm, sb_location, tm, sm, create: 1, NULL, sm_len: 0); |
509 | } |
510 | EXPORT_SYMBOL_GPL(dm_tm_create_with_sm); |
511 | |
512 | int dm_tm_open_with_sm(struct dm_block_manager *bm, dm_block_t sb_location, |
513 | void *sm_root, size_t root_len, |
514 | struct dm_transaction_manager **tm, |
515 | struct dm_space_map **sm) |
516 | { |
517 | return dm_tm_create_internal(bm, sb_location, tm, sm, create: 0, sm_root, sm_len: root_len); |
518 | } |
519 | EXPORT_SYMBOL_GPL(dm_tm_open_with_sm); |
520 | |
521 | /*----------------------------------------------------------------*/ |
522 | |