1 | // SPDX-License-Identifier: GPL-2.0-only |
2 | /* |
3 | * Copyright (C) 2012 Red Hat, Inc. |
4 | * |
5 | * This file is released under the GPL. |
6 | */ |
7 | |
8 | #include "dm-array.h" |
9 | #include "dm-space-map.h" |
10 | #include "dm-transaction-manager.h" |
11 | |
12 | #include <linux/export.h> |
13 | #include <linux/device-mapper.h> |
14 | |
15 | #define DM_MSG_PREFIX "array" |
16 | |
17 | /*----------------------------------------------------------------*/ |
18 | |
19 | /* |
20 | * The array is implemented as a fully populated btree, which points to |
21 | * blocks that contain the packed values. This is more space efficient |
22 | * than just using a btree since we don't store 1 key per value. |
23 | */ |
24 | struct array_block { |
25 | __le32 csum; |
26 | __le32 max_entries; |
27 | __le32 nr_entries; |
28 | __le32 value_size; |
29 | __le64 blocknr; /* Block this node is supposed to live in. */ |
30 | } __packed; |
31 | |
32 | /*----------------------------------------------------------------*/ |
33 | |
34 | /* |
35 | * Validator methods. As usual we calculate a checksum, and also write the |
36 | * block location into the header (paranoia about ssds remapping areas by |
37 | * mistake). |
38 | */ |
39 | #define CSUM_XOR 595846735 |
40 | |
41 | static void array_block_prepare_for_write(struct dm_block_validator *v, |
42 | struct dm_block *b, |
43 | size_t size_of_block) |
44 | { |
45 | struct array_block *bh_le = dm_block_data(b); |
46 | |
47 | bh_le->blocknr = cpu_to_le64(dm_block_location(b)); |
48 | bh_le->csum = cpu_to_le32(dm_bm_checksum(&bh_le->max_entries, |
49 | size_of_block - sizeof(__le32), |
50 | CSUM_XOR)); |
51 | } |
52 | |
53 | static int array_block_check(struct dm_block_validator *v, |
54 | struct dm_block *b, |
55 | size_t size_of_block) |
56 | { |
57 | struct array_block *bh_le = dm_block_data(b); |
58 | __le32 csum_disk; |
59 | |
60 | if (dm_block_location(b) != le64_to_cpu(bh_le->blocknr)) { |
61 | DMERR_LIMIT("%s failed: blocknr %llu != wanted %llu" , __func__, |
62 | (unsigned long long) le64_to_cpu(bh_le->blocknr), |
63 | (unsigned long long) dm_block_location(b)); |
64 | return -ENOTBLK; |
65 | } |
66 | |
67 | csum_disk = cpu_to_le32(dm_bm_checksum(&bh_le->max_entries, |
68 | size_of_block - sizeof(__le32), |
69 | CSUM_XOR)); |
70 | if (csum_disk != bh_le->csum) { |
71 | DMERR_LIMIT("%s failed: csum %u != wanted %u" , __func__, |
72 | (unsigned int) le32_to_cpu(csum_disk), |
73 | (unsigned int) le32_to_cpu(bh_le->csum)); |
74 | return -EILSEQ; |
75 | } |
76 | |
77 | return 0; |
78 | } |
79 | |
80 | static struct dm_block_validator array_validator = { |
81 | .name = "array" , |
82 | .prepare_for_write = array_block_prepare_for_write, |
83 | .check = array_block_check |
84 | }; |
85 | |
86 | /*----------------------------------------------------------------*/ |
87 | |
88 | /* |
89 | * Functions for manipulating the array blocks. |
90 | */ |
91 | |
92 | /* |
93 | * Returns a pointer to a value within an array block. |
94 | * |
95 | * index - The index into _this_ specific block. |
96 | */ |
97 | static void *element_at(struct dm_array_info *info, struct array_block *ab, |
98 | unsigned int index) |
99 | { |
100 | unsigned char *entry = (unsigned char *) (ab + 1); |
101 | |
102 | entry += index * info->value_type.size; |
103 | |
104 | return entry; |
105 | } |
106 | |
107 | /* |
108 | * Utility function that calls one of the value_type methods on every value |
109 | * in an array block. |
110 | */ |
111 | static void on_entries(struct dm_array_info *info, struct array_block *ab, |
112 | void (*fn)(void *, const void *, unsigned int)) |
113 | { |
114 | unsigned int nr_entries = le32_to_cpu(ab->nr_entries); |
115 | |
116 | fn(info->value_type.context, element_at(info, ab, index: 0), nr_entries); |
117 | } |
118 | |
119 | /* |
120 | * Increment every value in an array block. |
121 | */ |
122 | static void inc_ablock_entries(struct dm_array_info *info, struct array_block *ab) |
123 | { |
124 | struct dm_btree_value_type *vt = &info->value_type; |
125 | |
126 | if (vt->inc) |
127 | on_entries(info, ab, fn: vt->inc); |
128 | } |
129 | |
130 | /* |
131 | * Decrement every value in an array block. |
132 | */ |
133 | static void dec_ablock_entries(struct dm_array_info *info, struct array_block *ab) |
134 | { |
135 | struct dm_btree_value_type *vt = &info->value_type; |
136 | |
137 | if (vt->dec) |
138 | on_entries(info, ab, fn: vt->dec); |
139 | } |
140 | |
141 | /* |
142 | * Each array block can hold this many values. |
143 | */ |
144 | static uint32_t calc_max_entries(size_t value_size, size_t size_of_block) |
145 | { |
146 | return (size_of_block - sizeof(struct array_block)) / value_size; |
147 | } |
148 | |
149 | /* |
150 | * Allocate a new array block. The caller will need to unlock block. |
151 | */ |
152 | static int alloc_ablock(struct dm_array_info *info, size_t size_of_block, |
153 | uint32_t max_entries, |
154 | struct dm_block **block, struct array_block **ab) |
155 | { |
156 | int r; |
157 | |
158 | r = dm_tm_new_block(tm: info->btree_info.tm, v: &array_validator, result: block); |
159 | if (r) |
160 | return r; |
161 | |
162 | (*ab) = dm_block_data(b: *block); |
163 | (*ab)->max_entries = cpu_to_le32(max_entries); |
164 | (*ab)->nr_entries = cpu_to_le32(0); |
165 | (*ab)->value_size = cpu_to_le32(info->value_type.size); |
166 | |
167 | return 0; |
168 | } |
169 | |
170 | /* |
171 | * Pad an array block out with a particular value. Every instance will |
172 | * cause an increment of the value_type. new_nr must always be more than |
173 | * the current number of entries. |
174 | */ |
175 | static void fill_ablock(struct dm_array_info *info, struct array_block *ab, |
176 | const void *value, unsigned int new_nr) |
177 | { |
178 | uint32_t nr_entries, delta, i; |
179 | struct dm_btree_value_type *vt = &info->value_type; |
180 | |
181 | BUG_ON(new_nr > le32_to_cpu(ab->max_entries)); |
182 | BUG_ON(new_nr < le32_to_cpu(ab->nr_entries)); |
183 | |
184 | nr_entries = le32_to_cpu(ab->nr_entries); |
185 | delta = new_nr - nr_entries; |
186 | if (vt->inc) |
187 | vt->inc(vt->context, value, delta); |
188 | for (i = nr_entries; i < new_nr; i++) |
189 | memcpy(element_at(info, ab, i), value, vt->size); |
190 | ab->nr_entries = cpu_to_le32(new_nr); |
191 | } |
192 | |
193 | /* |
194 | * Remove some entries from the back of an array block. Every value |
195 | * removed will be decremented. new_nr must be <= the current number of |
196 | * entries. |
197 | */ |
198 | static void trim_ablock(struct dm_array_info *info, struct array_block *ab, |
199 | unsigned int new_nr) |
200 | { |
201 | uint32_t nr_entries, delta; |
202 | struct dm_btree_value_type *vt = &info->value_type; |
203 | |
204 | BUG_ON(new_nr > le32_to_cpu(ab->max_entries)); |
205 | BUG_ON(new_nr > le32_to_cpu(ab->nr_entries)); |
206 | |
207 | nr_entries = le32_to_cpu(ab->nr_entries); |
208 | delta = nr_entries - new_nr; |
209 | if (vt->dec) |
210 | vt->dec(vt->context, element_at(info, ab, index: new_nr - 1), delta); |
211 | ab->nr_entries = cpu_to_le32(new_nr); |
212 | } |
213 | |
214 | /* |
215 | * Read locks a block, and coerces it to an array block. The caller must |
216 | * unlock 'block' when finished. |
217 | */ |
218 | static int get_ablock(struct dm_array_info *info, dm_block_t b, |
219 | struct dm_block **block, struct array_block **ab) |
220 | { |
221 | int r; |
222 | |
223 | r = dm_tm_read_lock(tm: info->btree_info.tm, b, v: &array_validator, result: block); |
224 | if (r) |
225 | return r; |
226 | |
227 | *ab = dm_block_data(b: *block); |
228 | return 0; |
229 | } |
230 | |
231 | /* |
232 | * Unlocks an array block. |
233 | */ |
234 | static void unlock_ablock(struct dm_array_info *info, struct dm_block *block) |
235 | { |
236 | dm_tm_unlock(tm: info->btree_info.tm, b: block); |
237 | } |
238 | |
239 | /*----------------------------------------------------------------*/ |
240 | |
241 | /* |
242 | * Btree manipulation. |
243 | */ |
244 | |
245 | /* |
246 | * Looks up an array block in the btree, and then read locks it. |
247 | * |
248 | * index is the index of the index of the array_block, (ie. the array index |
249 | * / max_entries). |
250 | */ |
251 | static int lookup_ablock(struct dm_array_info *info, dm_block_t root, |
252 | unsigned int index, struct dm_block **block, |
253 | struct array_block **ab) |
254 | { |
255 | int r; |
256 | uint64_t key = index; |
257 | __le64 block_le; |
258 | |
259 | r = dm_btree_lookup(info: &info->btree_info, root, keys: &key, value_le: &block_le); |
260 | if (r) |
261 | return r; |
262 | |
263 | return get_ablock(info, le64_to_cpu(block_le), block, ab); |
264 | } |
265 | |
266 | /* |
267 | * Insert an array block into the btree. The block is _not_ unlocked. |
268 | */ |
269 | static int insert_ablock(struct dm_array_info *info, uint64_t index, |
270 | struct dm_block *block, dm_block_t *root) |
271 | { |
272 | __le64 block_le = cpu_to_le64(dm_block_location(block)); |
273 | |
274 | __dm_bless_for_disk(block_le); |
275 | return dm_btree_insert(info: &info->btree_info, root: *root, keys: &index, value: &block_le, new_root: root); |
276 | } |
277 | |
278 | /*----------------------------------------------------------------*/ |
279 | |
280 | static int __shadow_ablock(struct dm_array_info *info, dm_block_t b, |
281 | struct dm_block **block, struct array_block **ab) |
282 | { |
283 | int inc; |
284 | int r = dm_tm_shadow_block(tm: info->btree_info.tm, orig: b, |
285 | v: &array_validator, result: block, inc_children: &inc); |
286 | if (r) |
287 | return r; |
288 | |
289 | *ab = dm_block_data(b: *block); |
290 | if (inc) |
291 | inc_ablock_entries(info, ab: *ab); |
292 | |
293 | return 0; |
294 | } |
295 | |
296 | /* |
297 | * The shadow op will often be a noop. Only insert if it really |
298 | * copied data. |
299 | */ |
300 | static int __reinsert_ablock(struct dm_array_info *info, unsigned int index, |
301 | struct dm_block *block, dm_block_t b, |
302 | dm_block_t *root) |
303 | { |
304 | int r = 0; |
305 | |
306 | if (dm_block_location(b: block) != b) { |
307 | /* |
308 | * dm_tm_shadow_block will have already decremented the old |
309 | * block, but it is still referenced by the btree. We |
310 | * increment to stop the insert decrementing it below zero |
311 | * when overwriting the old value. |
312 | */ |
313 | dm_tm_inc(tm: info->btree_info.tm, b); |
314 | r = insert_ablock(info, index, block, root); |
315 | } |
316 | |
317 | return r; |
318 | } |
319 | |
320 | /* |
321 | * Looks up an array block in the btree. Then shadows it, and updates the |
322 | * btree to point to this new shadow. 'root' is an input/output parameter |
323 | * for both the current root block, and the new one. |
324 | */ |
325 | static int shadow_ablock(struct dm_array_info *info, dm_block_t *root, |
326 | unsigned int index, struct dm_block **block, |
327 | struct array_block **ab) |
328 | { |
329 | int r; |
330 | uint64_t key = index; |
331 | dm_block_t b; |
332 | __le64 block_le; |
333 | |
334 | r = dm_btree_lookup(info: &info->btree_info, root: *root, keys: &key, value_le: &block_le); |
335 | if (r) |
336 | return r; |
337 | b = le64_to_cpu(block_le); |
338 | |
339 | r = __shadow_ablock(info, b, block, ab); |
340 | if (r) |
341 | return r; |
342 | |
343 | return __reinsert_ablock(info, index, block: *block, b, root); |
344 | } |
345 | |
346 | /* |
347 | * Allocate an new array block, and fill it with some values. |
348 | */ |
349 | static int insert_new_ablock(struct dm_array_info *info, size_t size_of_block, |
350 | uint32_t max_entries, |
351 | unsigned int block_index, uint32_t nr, |
352 | const void *value, dm_block_t *root) |
353 | { |
354 | int r; |
355 | struct dm_block *block; |
356 | struct array_block *ab; |
357 | |
358 | r = alloc_ablock(info, size_of_block, max_entries, block: &block, ab: &ab); |
359 | if (r) |
360 | return r; |
361 | |
362 | fill_ablock(info, ab, value, new_nr: nr); |
363 | r = insert_ablock(info, index: block_index, block, root); |
364 | unlock_ablock(info, block); |
365 | |
366 | return r; |
367 | } |
368 | |
369 | static int insert_full_ablocks(struct dm_array_info *info, size_t size_of_block, |
370 | unsigned int begin_block, unsigned int end_block, |
371 | unsigned int max_entries, const void *value, |
372 | dm_block_t *root) |
373 | { |
374 | int r = 0; |
375 | |
376 | for (; !r && begin_block != end_block; begin_block++) |
377 | r = insert_new_ablock(info, size_of_block, max_entries, block_index: begin_block, nr: max_entries, value, root); |
378 | |
379 | return r; |
380 | } |
381 | |
382 | /* |
383 | * There are a bunch of functions involved with resizing an array. This |
384 | * structure holds information that commonly needed by them. Purely here |
385 | * to reduce parameter count. |
386 | */ |
387 | struct resize { |
388 | /* |
389 | * Describes the array. |
390 | */ |
391 | struct dm_array_info *info; |
392 | |
393 | /* |
394 | * The current root of the array. This gets updated. |
395 | */ |
396 | dm_block_t root; |
397 | |
398 | /* |
399 | * Metadata block size. Used to calculate the nr entries in an |
400 | * array block. |
401 | */ |
402 | size_t size_of_block; |
403 | |
404 | /* |
405 | * Maximum nr entries in an array block. |
406 | */ |
407 | unsigned int max_entries; |
408 | |
409 | /* |
410 | * nr of completely full blocks in the array. |
411 | * |
412 | * 'old' refers to before the resize, 'new' after. |
413 | */ |
414 | unsigned int old_nr_full_blocks, new_nr_full_blocks; |
415 | |
416 | /* |
417 | * Number of entries in the final block. 0 iff only full blocks in |
418 | * the array. |
419 | */ |
420 | unsigned int old_nr_entries_in_last_block, new_nr_entries_in_last_block; |
421 | |
422 | /* |
423 | * The default value used when growing the array. |
424 | */ |
425 | const void *value; |
426 | }; |
427 | |
428 | /* |
429 | * Removes a consecutive set of array blocks from the btree. The values |
430 | * in block are decremented as a side effect of the btree remove. |
431 | * |
432 | * begin_index - the index of the first array block to remove. |
433 | * end_index - the one-past-the-end value. ie. this block is not removed. |
434 | */ |
435 | static int drop_blocks(struct resize *resize, unsigned int begin_index, |
436 | unsigned int end_index) |
437 | { |
438 | int r; |
439 | |
440 | while (begin_index != end_index) { |
441 | uint64_t key = begin_index++; |
442 | |
443 | r = dm_btree_remove(info: &resize->info->btree_info, root: resize->root, |
444 | keys: &key, new_root: &resize->root); |
445 | if (r) |
446 | return r; |
447 | } |
448 | |
449 | return 0; |
450 | } |
451 | |
452 | /* |
453 | * Calculates how many blocks are needed for the array. |
454 | */ |
455 | static unsigned int total_nr_blocks_needed(unsigned int nr_full_blocks, |
456 | unsigned int nr_entries_in_last_block) |
457 | { |
458 | return nr_full_blocks + (nr_entries_in_last_block ? 1 : 0); |
459 | } |
460 | |
461 | /* |
462 | * Shrink an array. |
463 | */ |
464 | static int shrink(struct resize *resize) |
465 | { |
466 | int r; |
467 | unsigned int begin, end; |
468 | struct dm_block *block; |
469 | struct array_block *ab; |
470 | |
471 | /* |
472 | * Lose some blocks from the back? |
473 | */ |
474 | if (resize->new_nr_full_blocks < resize->old_nr_full_blocks) { |
475 | begin = total_nr_blocks_needed(nr_full_blocks: resize->new_nr_full_blocks, |
476 | nr_entries_in_last_block: resize->new_nr_entries_in_last_block); |
477 | end = total_nr_blocks_needed(nr_full_blocks: resize->old_nr_full_blocks, |
478 | nr_entries_in_last_block: resize->old_nr_entries_in_last_block); |
479 | |
480 | r = drop_blocks(resize, begin_index: begin, end_index: end); |
481 | if (r) |
482 | return r; |
483 | } |
484 | |
485 | /* |
486 | * Trim the new tail block |
487 | */ |
488 | if (resize->new_nr_entries_in_last_block) { |
489 | r = shadow_ablock(info: resize->info, root: &resize->root, |
490 | index: resize->new_nr_full_blocks, block: &block, ab: &ab); |
491 | if (r) |
492 | return r; |
493 | |
494 | trim_ablock(info: resize->info, ab, new_nr: resize->new_nr_entries_in_last_block); |
495 | unlock_ablock(info: resize->info, block); |
496 | } |
497 | |
498 | return 0; |
499 | } |
500 | |
501 | /* |
502 | * Grow an array. |
503 | */ |
504 | static int grow_extend_tail_block(struct resize *resize, uint32_t new_nr_entries) |
505 | { |
506 | int r; |
507 | struct dm_block *block; |
508 | struct array_block *ab; |
509 | |
510 | r = shadow_ablock(info: resize->info, root: &resize->root, |
511 | index: resize->old_nr_full_blocks, block: &block, ab: &ab); |
512 | if (r) |
513 | return r; |
514 | |
515 | fill_ablock(info: resize->info, ab, value: resize->value, new_nr: new_nr_entries); |
516 | unlock_ablock(info: resize->info, block); |
517 | |
518 | return r; |
519 | } |
520 | |
521 | static int grow_add_tail_block(struct resize *resize) |
522 | { |
523 | return insert_new_ablock(info: resize->info, size_of_block: resize->size_of_block, |
524 | max_entries: resize->max_entries, |
525 | block_index: resize->new_nr_full_blocks, |
526 | nr: resize->new_nr_entries_in_last_block, |
527 | value: resize->value, root: &resize->root); |
528 | } |
529 | |
530 | static int grow_needs_more_blocks(struct resize *resize) |
531 | { |
532 | int r; |
533 | unsigned int old_nr_blocks = resize->old_nr_full_blocks; |
534 | |
535 | if (resize->old_nr_entries_in_last_block > 0) { |
536 | old_nr_blocks++; |
537 | |
538 | r = grow_extend_tail_block(resize, new_nr_entries: resize->max_entries); |
539 | if (r) |
540 | return r; |
541 | } |
542 | |
543 | r = insert_full_ablocks(info: resize->info, size_of_block: resize->size_of_block, |
544 | begin_block: old_nr_blocks, |
545 | end_block: resize->new_nr_full_blocks, |
546 | max_entries: resize->max_entries, value: resize->value, |
547 | root: &resize->root); |
548 | if (r) |
549 | return r; |
550 | |
551 | if (resize->new_nr_entries_in_last_block) |
552 | r = grow_add_tail_block(resize); |
553 | |
554 | return r; |
555 | } |
556 | |
557 | static int grow(struct resize *resize) |
558 | { |
559 | if (resize->new_nr_full_blocks > resize->old_nr_full_blocks) |
560 | return grow_needs_more_blocks(resize); |
561 | |
562 | else if (resize->old_nr_entries_in_last_block) |
563 | return grow_extend_tail_block(resize, new_nr_entries: resize->new_nr_entries_in_last_block); |
564 | |
565 | else |
566 | return grow_add_tail_block(resize); |
567 | } |
568 | |
569 | /*----------------------------------------------------------------*/ |
570 | |
571 | /* |
572 | * These are the value_type functions for the btree elements, which point |
573 | * to array blocks. |
574 | */ |
575 | static void block_inc(void *context, const void *value, unsigned int count) |
576 | { |
577 | const __le64 *block_le = value; |
578 | struct dm_array_info *info = context; |
579 | unsigned int i; |
580 | |
581 | for (i = 0; i < count; i++, block_le++) |
582 | dm_tm_inc(tm: info->btree_info.tm, le64_to_cpu(*block_le)); |
583 | } |
584 | |
585 | static void __block_dec(void *context, const void *value) |
586 | { |
587 | int r; |
588 | uint64_t b; |
589 | __le64 block_le; |
590 | uint32_t ref_count; |
591 | struct dm_block *block; |
592 | struct array_block *ab; |
593 | struct dm_array_info *info = context; |
594 | |
595 | memcpy(&block_le, value, sizeof(block_le)); |
596 | b = le64_to_cpu(block_le); |
597 | |
598 | r = dm_tm_ref(tm: info->btree_info.tm, b, result: &ref_count); |
599 | if (r) { |
600 | DMERR_LIMIT("couldn't get reference count for block %llu" , |
601 | (unsigned long long) b); |
602 | return; |
603 | } |
604 | |
605 | if (ref_count == 1) { |
606 | /* |
607 | * We're about to drop the last reference to this ablock. |
608 | * So we need to decrement the ref count of the contents. |
609 | */ |
610 | r = get_ablock(info, b, block: &block, ab: &ab); |
611 | if (r) { |
612 | DMERR_LIMIT("couldn't get array block %llu" , |
613 | (unsigned long long) b); |
614 | return; |
615 | } |
616 | |
617 | dec_ablock_entries(info, ab); |
618 | unlock_ablock(info, block); |
619 | } |
620 | |
621 | dm_tm_dec(tm: info->btree_info.tm, b); |
622 | } |
623 | |
624 | static void block_dec(void *context, const void *value, unsigned int count) |
625 | { |
626 | unsigned int i; |
627 | |
628 | for (i = 0; i < count; i++, value += sizeof(__le64)) |
629 | __block_dec(context, value); |
630 | } |
631 | |
632 | static int block_equal(void *context, const void *value1, const void *value2) |
633 | { |
634 | return !memcmp(p: value1, q: value2, size: sizeof(__le64)); |
635 | } |
636 | |
637 | /*----------------------------------------------------------------*/ |
638 | |
639 | void dm_array_info_init(struct dm_array_info *info, |
640 | struct dm_transaction_manager *tm, |
641 | struct dm_btree_value_type *vt) |
642 | { |
643 | struct dm_btree_value_type *bvt = &info->btree_info.value_type; |
644 | |
645 | memcpy(&info->value_type, vt, sizeof(info->value_type)); |
646 | info->btree_info.tm = tm; |
647 | info->btree_info.levels = 1; |
648 | |
649 | bvt->context = info; |
650 | bvt->size = sizeof(__le64); |
651 | bvt->inc = block_inc; |
652 | bvt->dec = block_dec; |
653 | bvt->equal = block_equal; |
654 | } |
655 | EXPORT_SYMBOL_GPL(dm_array_info_init); |
656 | |
657 | int dm_array_empty(struct dm_array_info *info, dm_block_t *root) |
658 | { |
659 | return dm_btree_empty(info: &info->btree_info, root); |
660 | } |
661 | EXPORT_SYMBOL_GPL(dm_array_empty); |
662 | |
663 | static int array_resize(struct dm_array_info *info, dm_block_t root, |
664 | uint32_t old_size, uint32_t new_size, |
665 | const void *value, dm_block_t *new_root) |
666 | { |
667 | int r; |
668 | struct resize resize; |
669 | |
670 | if (old_size == new_size) { |
671 | *new_root = root; |
672 | return 0; |
673 | } |
674 | |
675 | resize.info = info; |
676 | resize.root = root; |
677 | resize.size_of_block = dm_bm_block_size(bm: dm_tm_get_bm(tm: info->btree_info.tm)); |
678 | resize.max_entries = calc_max_entries(value_size: info->value_type.size, |
679 | size_of_block: resize.size_of_block); |
680 | |
681 | resize.old_nr_full_blocks = old_size / resize.max_entries; |
682 | resize.old_nr_entries_in_last_block = old_size % resize.max_entries; |
683 | resize.new_nr_full_blocks = new_size / resize.max_entries; |
684 | resize.new_nr_entries_in_last_block = new_size % resize.max_entries; |
685 | resize.value = value; |
686 | |
687 | r = ((new_size > old_size) ? grow : shrink)(&resize); |
688 | if (r) |
689 | return r; |
690 | |
691 | *new_root = resize.root; |
692 | return 0; |
693 | } |
694 | |
695 | int dm_array_resize(struct dm_array_info *info, dm_block_t root, |
696 | uint32_t old_size, uint32_t new_size, |
697 | const void *value, dm_block_t *new_root) |
698 | __dm_written_to_disk(value) |
699 | { |
700 | int r = array_resize(info, root, old_size, new_size, value, new_root); |
701 | |
702 | __dm_unbless_for_disk(value); |
703 | return r; |
704 | } |
705 | EXPORT_SYMBOL_GPL(dm_array_resize); |
706 | |
707 | static int populate_ablock_with_values(struct dm_array_info *info, struct array_block *ab, |
708 | value_fn fn, void *context, |
709 | unsigned int base, unsigned int new_nr) |
710 | { |
711 | int r; |
712 | unsigned int i; |
713 | struct dm_btree_value_type *vt = &info->value_type; |
714 | |
715 | BUG_ON(le32_to_cpu(ab->nr_entries)); |
716 | BUG_ON(new_nr > le32_to_cpu(ab->max_entries)); |
717 | |
718 | for (i = 0; i < new_nr; i++) { |
719 | r = fn(base + i, element_at(info, ab, index: i), context); |
720 | if (r) |
721 | return r; |
722 | |
723 | if (vt->inc) |
724 | vt->inc(vt->context, element_at(info, ab, index: i), 1); |
725 | } |
726 | |
727 | ab->nr_entries = cpu_to_le32(new_nr); |
728 | return 0; |
729 | } |
730 | |
731 | int dm_array_new(struct dm_array_info *info, dm_block_t *root, |
732 | uint32_t size, value_fn fn, void *context) |
733 | { |
734 | int r; |
735 | struct dm_block *block; |
736 | struct array_block *ab; |
737 | unsigned int block_index, end_block, size_of_block, max_entries; |
738 | |
739 | r = dm_array_empty(info, root); |
740 | if (r) |
741 | return r; |
742 | |
743 | size_of_block = dm_bm_block_size(bm: dm_tm_get_bm(tm: info->btree_info.tm)); |
744 | max_entries = calc_max_entries(value_size: info->value_type.size, size_of_block); |
745 | end_block = dm_div_up(size, max_entries); |
746 | |
747 | for (block_index = 0; block_index != end_block; block_index++) { |
748 | r = alloc_ablock(info, size_of_block, max_entries, block: &block, ab: &ab); |
749 | if (r) |
750 | break; |
751 | |
752 | r = populate_ablock_with_values(info, ab, fn, context, |
753 | base: block_index * max_entries, |
754 | min(max_entries, size)); |
755 | if (r) { |
756 | unlock_ablock(info, block); |
757 | break; |
758 | } |
759 | |
760 | r = insert_ablock(info, index: block_index, block, root); |
761 | unlock_ablock(info, block); |
762 | if (r) |
763 | break; |
764 | |
765 | size -= max_entries; |
766 | } |
767 | |
768 | return r; |
769 | } |
770 | EXPORT_SYMBOL_GPL(dm_array_new); |
771 | |
772 | int dm_array_del(struct dm_array_info *info, dm_block_t root) |
773 | { |
774 | return dm_btree_del(info: &info->btree_info, root); |
775 | } |
776 | EXPORT_SYMBOL_GPL(dm_array_del); |
777 | |
778 | int dm_array_get_value(struct dm_array_info *info, dm_block_t root, |
779 | uint32_t index, void *value_le) |
780 | { |
781 | int r; |
782 | struct dm_block *block; |
783 | struct array_block *ab; |
784 | size_t size_of_block; |
785 | unsigned int entry, max_entries; |
786 | |
787 | size_of_block = dm_bm_block_size(bm: dm_tm_get_bm(tm: info->btree_info.tm)); |
788 | max_entries = calc_max_entries(value_size: info->value_type.size, size_of_block); |
789 | |
790 | r = lookup_ablock(info, root, index: index / max_entries, block: &block, ab: &ab); |
791 | if (r) |
792 | return r; |
793 | |
794 | entry = index % max_entries; |
795 | if (entry >= le32_to_cpu(ab->nr_entries)) |
796 | r = -ENODATA; |
797 | else |
798 | memcpy(value_le, element_at(info, ab, entry), |
799 | info->value_type.size); |
800 | |
801 | unlock_ablock(info, block); |
802 | return r; |
803 | } |
804 | EXPORT_SYMBOL_GPL(dm_array_get_value); |
805 | |
806 | static int array_set_value(struct dm_array_info *info, dm_block_t root, |
807 | uint32_t index, const void *value, dm_block_t *new_root) |
808 | { |
809 | int r; |
810 | struct dm_block *block; |
811 | struct array_block *ab; |
812 | size_t size_of_block; |
813 | unsigned int max_entries; |
814 | unsigned int entry; |
815 | void *old_value; |
816 | struct dm_btree_value_type *vt = &info->value_type; |
817 | |
818 | size_of_block = dm_bm_block_size(bm: dm_tm_get_bm(tm: info->btree_info.tm)); |
819 | max_entries = calc_max_entries(value_size: info->value_type.size, size_of_block); |
820 | |
821 | r = shadow_ablock(info, root: &root, index: index / max_entries, block: &block, ab: &ab); |
822 | if (r) |
823 | return r; |
824 | *new_root = root; |
825 | |
826 | entry = index % max_entries; |
827 | if (entry >= le32_to_cpu(ab->nr_entries)) { |
828 | r = -ENODATA; |
829 | goto out; |
830 | } |
831 | |
832 | old_value = element_at(info, ab, index: entry); |
833 | if (vt->dec && |
834 | (!vt->equal || !vt->equal(vt->context, old_value, value))) { |
835 | vt->dec(vt->context, old_value, 1); |
836 | if (vt->inc) |
837 | vt->inc(vt->context, value, 1); |
838 | } |
839 | |
840 | memcpy(old_value, value, info->value_type.size); |
841 | |
842 | out: |
843 | unlock_ablock(info, block); |
844 | return r; |
845 | } |
846 | |
847 | int dm_array_set_value(struct dm_array_info *info, dm_block_t root, |
848 | uint32_t index, const void *value, dm_block_t *new_root) |
849 | __dm_written_to_disk(value) |
850 | { |
851 | int r; |
852 | |
853 | r = array_set_value(info, root, index, value, new_root); |
854 | __dm_unbless_for_disk(value); |
855 | return r; |
856 | } |
857 | EXPORT_SYMBOL_GPL(dm_array_set_value); |
858 | |
859 | struct walk_info { |
860 | struct dm_array_info *info; |
861 | int (*fn)(void *context, uint64_t key, void *leaf); |
862 | void *context; |
863 | }; |
864 | |
865 | static int walk_ablock(void *context, uint64_t *keys, void *leaf) |
866 | { |
867 | struct walk_info *wi = context; |
868 | |
869 | int r; |
870 | unsigned int i; |
871 | __le64 block_le; |
872 | unsigned int nr_entries, max_entries; |
873 | struct dm_block *block; |
874 | struct array_block *ab; |
875 | |
876 | memcpy(&block_le, leaf, sizeof(block_le)); |
877 | r = get_ablock(info: wi->info, le64_to_cpu(block_le), block: &block, ab: &ab); |
878 | if (r) |
879 | return r; |
880 | |
881 | max_entries = le32_to_cpu(ab->max_entries); |
882 | nr_entries = le32_to_cpu(ab->nr_entries); |
883 | for (i = 0; i < nr_entries; i++) { |
884 | r = wi->fn(wi->context, keys[0] * max_entries + i, |
885 | element_at(info: wi->info, ab, index: i)); |
886 | |
887 | if (r) |
888 | break; |
889 | } |
890 | |
891 | unlock_ablock(info: wi->info, block); |
892 | return r; |
893 | } |
894 | |
895 | int dm_array_walk(struct dm_array_info *info, dm_block_t root, |
896 | int (*fn)(void *, uint64_t key, void *leaf), |
897 | void *context) |
898 | { |
899 | struct walk_info wi; |
900 | |
901 | wi.info = info; |
902 | wi.fn = fn; |
903 | wi.context = context; |
904 | |
905 | return dm_btree_walk(info: &info->btree_info, root, fn: walk_ablock, context: &wi); |
906 | } |
907 | EXPORT_SYMBOL_GPL(dm_array_walk); |
908 | |
909 | /*----------------------------------------------------------------*/ |
910 | |
911 | static int load_ablock(struct dm_array_cursor *c) |
912 | { |
913 | int r; |
914 | __le64 value_le; |
915 | uint64_t key; |
916 | |
917 | if (c->block) |
918 | unlock_ablock(info: c->info, block: c->block); |
919 | |
920 | c->block = NULL; |
921 | c->ab = NULL; |
922 | c->index = 0; |
923 | |
924 | r = dm_btree_cursor_get_value(c: &c->cursor, key: &key, value_le: &value_le); |
925 | if (r) { |
926 | DMERR("dm_btree_cursor_get_value failed" ); |
927 | dm_btree_cursor_end(c: &c->cursor); |
928 | |
929 | } else { |
930 | r = get_ablock(info: c->info, le64_to_cpu(value_le), block: &c->block, ab: &c->ab); |
931 | if (r) { |
932 | DMERR("get_ablock failed" ); |
933 | dm_btree_cursor_end(c: &c->cursor); |
934 | } |
935 | } |
936 | |
937 | return r; |
938 | } |
939 | |
940 | int dm_array_cursor_begin(struct dm_array_info *info, dm_block_t root, |
941 | struct dm_array_cursor *c) |
942 | { |
943 | int r; |
944 | |
945 | memset(c, 0, sizeof(*c)); |
946 | c->info = info; |
947 | r = dm_btree_cursor_begin(info: &info->btree_info, root, prefetch_leaves: true, c: &c->cursor); |
948 | if (r) { |
949 | DMERR("couldn't create btree cursor" ); |
950 | return r; |
951 | } |
952 | |
953 | return load_ablock(c); |
954 | } |
955 | EXPORT_SYMBOL_GPL(dm_array_cursor_begin); |
956 | |
957 | void dm_array_cursor_end(struct dm_array_cursor *c) |
958 | { |
959 | if (c->block) { |
960 | unlock_ablock(info: c->info, block: c->block); |
961 | dm_btree_cursor_end(c: &c->cursor); |
962 | } |
963 | } |
964 | EXPORT_SYMBOL_GPL(dm_array_cursor_end); |
965 | |
966 | int dm_array_cursor_next(struct dm_array_cursor *c) |
967 | { |
968 | int r; |
969 | |
970 | if (!c->block) |
971 | return -ENODATA; |
972 | |
973 | c->index++; |
974 | |
975 | if (c->index >= le32_to_cpu(c->ab->nr_entries)) { |
976 | r = dm_btree_cursor_next(c: &c->cursor); |
977 | if (r) |
978 | return r; |
979 | |
980 | r = load_ablock(c); |
981 | if (r) |
982 | return r; |
983 | } |
984 | |
985 | return 0; |
986 | } |
987 | EXPORT_SYMBOL_GPL(dm_array_cursor_next); |
988 | |
989 | int dm_array_cursor_skip(struct dm_array_cursor *c, uint32_t count) |
990 | { |
991 | int r; |
992 | |
993 | do { |
994 | uint32_t remaining = le32_to_cpu(c->ab->nr_entries) - c->index; |
995 | |
996 | if (count < remaining) { |
997 | c->index += count; |
998 | return 0; |
999 | } |
1000 | |
1001 | count -= remaining; |
1002 | r = dm_array_cursor_next(c); |
1003 | |
1004 | } while (!r); |
1005 | |
1006 | return r; |
1007 | } |
1008 | EXPORT_SYMBOL_GPL(dm_array_cursor_skip); |
1009 | |
1010 | void dm_array_cursor_get_value(struct dm_array_cursor *c, void **value_le) |
1011 | { |
1012 | *value_le = element_at(info: c->info, ab: c->ab, index: c->index); |
1013 | } |
1014 | EXPORT_SYMBOL_GPL(dm_array_cursor_get_value); |
1015 | |
1016 | /*----------------------------------------------------------------*/ |
1017 | |