]>
Commit | Line | Data |
---|---|---|
6513c29f JT |
1 | /* |
2 | * Copyright (C) 2012 Red Hat, Inc. | |
3 | * | |
4 | * This file is released under the GPL. | |
5 | */ | |
6 | ||
7 | #include "dm-array.h" | |
8 | #include "dm-space-map.h" | |
9 | #include "dm-transaction-manager.h" | |
10 | ||
11 | #include <linux/export.h> | |
12 | #include <linux/device-mapper.h> | |
13 | ||
14 | #define DM_MSG_PREFIX "array" | |
15 | ||
16 | /*----------------------------------------------------------------*/ | |
17 | ||
18 | /* | |
19 | * The array is implemented as a fully populated btree, which points to | |
20 | * blocks that contain the packed values. This is more space efficient | |
21 | * than just using a btree since we don't store 1 key per value. | |
22 | */ | |
23 | struct array_block { | |
24 | __le32 csum; | |
25 | __le32 max_entries; | |
26 | __le32 nr_entries; | |
27 | __le32 value_size; | |
28 | __le64 blocknr; /* Block this node is supposed to live in. */ | |
29 | } __packed; | |
30 | ||
31 | /*----------------------------------------------------------------*/ | |
32 | ||
33 | /* | |
34 | * Validator methods. As usual we calculate a checksum, and also write the | |
35 | * block location into the header (paranoia about ssds remapping areas by | |
36 | * mistake). | |
37 | */ | |
38 | #define CSUM_XOR 595846735 | |
39 | ||
40 | static void array_block_prepare_for_write(struct dm_block_validator *v, | |
41 | struct dm_block *b, | |
42 | size_t size_of_block) | |
43 | { | |
44 | struct array_block *bh_le = dm_block_data(b); | |
45 | ||
46 | bh_le->blocknr = cpu_to_le64(dm_block_location(b)); | |
47 | bh_le->csum = cpu_to_le32(dm_bm_checksum(&bh_le->max_entries, | |
48 | size_of_block - sizeof(__le32), | |
49 | CSUM_XOR)); | |
50 | } | |
51 | ||
52 | static int array_block_check(struct dm_block_validator *v, | |
53 | struct dm_block *b, | |
54 | size_t size_of_block) | |
55 | { | |
56 | struct array_block *bh_le = dm_block_data(b); | |
57 | __le32 csum_disk; | |
58 | ||
59 | if (dm_block_location(b) != le64_to_cpu(bh_le->blocknr)) { | |
60 | DMERR_LIMIT("array_block_check failed: blocknr %llu != wanted %llu", | |
61 | (unsigned long long) le64_to_cpu(bh_le->blocknr), | |
62 | (unsigned long long) dm_block_location(b)); | |
63 | return -ENOTBLK; | |
64 | } | |
65 | ||
66 | csum_disk = cpu_to_le32(dm_bm_checksum(&bh_le->max_entries, | |
67 | size_of_block - sizeof(__le32), | |
68 | CSUM_XOR)); | |
69 | if (csum_disk != bh_le->csum) { | |
70 | DMERR_LIMIT("array_block_check failed: csum %u != wanted %u", | |
71 | (unsigned) le32_to_cpu(csum_disk), | |
72 | (unsigned) le32_to_cpu(bh_le->csum)); | |
73 | return -EILSEQ; | |
74 | } | |
75 | ||
76 | return 0; | |
77 | } | |
78 | ||
79 | static struct dm_block_validator array_validator = { | |
80 | .name = "array", | |
81 | .prepare_for_write = array_block_prepare_for_write, | |
82 | .check = array_block_check | |
83 | }; | |
84 | ||
85 | /*----------------------------------------------------------------*/ | |
86 | ||
87 | /* | |
88 | * Functions for manipulating the array blocks. | |
89 | */ | |
90 | ||
91 | /* | |
92 | * Returns a pointer to a value within an array block. | |
93 | * | |
94 | * index - The index into _this_ specific block. | |
95 | */ | |
96 | static void *element_at(struct dm_array_info *info, struct array_block *ab, | |
97 | unsigned index) | |
98 | { | |
99 | unsigned char *entry = (unsigned char *) (ab + 1); | |
100 | ||
101 | entry += index * info->value_type.size; | |
102 | ||
103 | return entry; | |
104 | } | |
105 | ||
106 | /* | |
107 | * Utility function that calls one of the value_type methods on every value | |
108 | * in an array block. | |
109 | */ | |
110 | static void on_entries(struct dm_array_info *info, struct array_block *ab, | |
111 | void (*fn)(void *, const void *)) | |
112 | { | |
113 | unsigned i, nr_entries = le32_to_cpu(ab->nr_entries); | |
114 | ||
115 | for (i = 0; i < nr_entries; i++) | |
116 | fn(info->value_type.context, element_at(info, ab, i)); | |
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, 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, 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(info->btree_info.tm, &array_validator, block); | |
159 | if (r) | |
160 | return r; | |
161 | ||
162 | (*ab) = dm_block_data(*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 new_nr) | |
177 | { | |
178 | unsigned i; | |
179 | uint32_t nr_entries; | |
180 | struct dm_btree_value_type *vt = &info->value_type; | |
181 | ||
182 | BUG_ON(new_nr > le32_to_cpu(ab->max_entries)); | |
183 | BUG_ON(new_nr < le32_to_cpu(ab->nr_entries)); | |
184 | ||
185 | nr_entries = le32_to_cpu(ab->nr_entries); | |
186 | for (i = nr_entries; i < new_nr; i++) { | |
187 | if (vt->inc) | |
188 | vt->inc(vt->context, value); | |
189 | memcpy(element_at(info, ab, i), value, vt->size); | |
190 | } | |
191 | ab->nr_entries = cpu_to_le32(new_nr); | |
192 | } | |
193 | ||
194 | /* | |
195 | * Remove some entries from the back of an array block. Every value | |
196 | * removed will be decremented. new_nr must be <= the current number of | |
197 | * entries. | |
198 | */ | |
199 | static void trim_ablock(struct dm_array_info *info, struct array_block *ab, | |
200 | unsigned new_nr) | |
201 | { | |
202 | unsigned i; | |
203 | uint32_t nr_entries; | |
204 | struct dm_btree_value_type *vt = &info->value_type; | |
205 | ||
206 | BUG_ON(new_nr > le32_to_cpu(ab->max_entries)); | |
207 | BUG_ON(new_nr > le32_to_cpu(ab->nr_entries)); | |
208 | ||
209 | nr_entries = le32_to_cpu(ab->nr_entries); | |
210 | for (i = nr_entries; i > new_nr; i--) | |
211 | if (vt->dec) | |
212 | vt->dec(vt->context, element_at(info, ab, i - 1)); | |
213 | ab->nr_entries = cpu_to_le32(new_nr); | |
214 | } | |
215 | ||
216 | /* | |
217 | * Read locks a block, and coerces it to an array block. The caller must | |
218 | * unlock 'block' when finished. | |
219 | */ | |
220 | static int get_ablock(struct dm_array_info *info, dm_block_t b, | |
221 | struct dm_block **block, struct array_block **ab) | |
222 | { | |
223 | int r; | |
224 | ||
225 | r = dm_tm_read_lock(info->btree_info.tm, b, &array_validator, block); | |
226 | if (r) | |
227 | return r; | |
228 | ||
229 | *ab = dm_block_data(*block); | |
230 | return 0; | |
231 | } | |
232 | ||
233 | /* | |
234 | * Unlocks an array block. | |
235 | */ | |
236 | static int unlock_ablock(struct dm_array_info *info, struct dm_block *block) | |
237 | { | |
238 | return dm_tm_unlock(info->btree_info.tm, block); | |
239 | } | |
240 | ||
241 | /*----------------------------------------------------------------*/ | |
242 | ||
243 | /* | |
244 | * Btree manipulation. | |
245 | */ | |
246 | ||
247 | /* | |
248 | * Looks up an array block in the btree, and then read locks it. | |
249 | * | |
250 | * index is the index of the index of the array_block, (ie. the array index | |
251 | * / max_entries). | |
252 | */ | |
253 | static int lookup_ablock(struct dm_array_info *info, dm_block_t root, | |
254 | unsigned index, struct dm_block **block, | |
255 | struct array_block **ab) | |
256 | { | |
257 | int r; | |
258 | uint64_t key = index; | |
259 | __le64 block_le; | |
260 | ||
261 | r = dm_btree_lookup(&info->btree_info, root, &key, &block_le); | |
262 | if (r) | |
263 | return r; | |
264 | ||
265 | return get_ablock(info, le64_to_cpu(block_le), block, ab); | |
266 | } | |
267 | ||
268 | /* | |
269 | * Insert an array block into the btree. The block is _not_ unlocked. | |
270 | */ | |
271 | static int insert_ablock(struct dm_array_info *info, uint64_t index, | |
272 | struct dm_block *block, dm_block_t *root) | |
273 | { | |
274 | __le64 block_le = cpu_to_le64(dm_block_location(block)); | |
275 | ||
276 | __dm_bless_for_disk(block_le); | |
277 | return dm_btree_insert(&info->btree_info, *root, &index, &block_le, root); | |
278 | } | |
279 | ||
280 | /* | |
281 | * Looks up an array block in the btree. Then shadows it, and updates the | |
282 | * btree to point to this new shadow. 'root' is an input/output parameter | |
283 | * for both the current root block, and the new one. | |
284 | */ | |
285 | static int shadow_ablock(struct dm_array_info *info, dm_block_t *root, | |
286 | unsigned index, struct dm_block **block, | |
287 | struct array_block **ab) | |
288 | { | |
289 | int r, inc; | |
290 | uint64_t key = index; | |
291 | dm_block_t b; | |
292 | __le64 block_le; | |
293 | ||
294 | /* | |
295 | * lookup | |
296 | */ | |
297 | r = dm_btree_lookup(&info->btree_info, *root, &key, &block_le); | |
298 | if (r) | |
299 | return r; | |
300 | b = le64_to_cpu(block_le); | |
301 | ||
302 | /* | |
303 | * shadow | |
304 | */ | |
305 | r = dm_tm_shadow_block(info->btree_info.tm, b, | |
306 | &array_validator, block, &inc); | |
307 | if (r) | |
308 | return r; | |
309 | ||
310 | *ab = dm_block_data(*block); | |
311 | if (inc) | |
312 | inc_ablock_entries(info, *ab); | |
313 | ||
314 | /* | |
315 | * Reinsert. | |
316 | * | |
317 | * The shadow op will often be a noop. Only insert if it really | |
318 | * copied data. | |
319 | */ | |
ed9571f0 JT |
320 | if (dm_block_location(*block) != b) { |
321 | /* | |
322 | * dm_tm_shadow_block will have already decremented the old | |
323 | * block, but it is still referenced by the btree. We | |
324 | * increment to stop the insert decrementing it below zero | |
325 | * when overwriting the old value. | |
326 | */ | |
327 | dm_tm_inc(info->btree_info.tm, b); | |
6513c29f | 328 | r = insert_ablock(info, index, *block, root); |
ed9571f0 | 329 | } |
6513c29f JT |
330 | |
331 | return r; | |
332 | } | |
333 | ||
334 | /* | |
335 | * Allocate an new array block, and fill it with some values. | |
336 | */ | |
337 | static int insert_new_ablock(struct dm_array_info *info, size_t size_of_block, | |
338 | uint32_t max_entries, | |
339 | unsigned block_index, uint32_t nr, | |
340 | const void *value, dm_block_t *root) | |
341 | { | |
342 | int r; | |
343 | struct dm_block *block; | |
344 | struct array_block *ab; | |
345 | ||
346 | r = alloc_ablock(info, size_of_block, max_entries, &block, &ab); | |
347 | if (r) | |
348 | return r; | |
349 | ||
350 | fill_ablock(info, ab, value, nr); | |
351 | r = insert_ablock(info, block_index, block, root); | |
352 | unlock_ablock(info, block); | |
353 | ||
354 | return r; | |
355 | } | |
356 | ||
357 | static int insert_full_ablocks(struct dm_array_info *info, size_t size_of_block, | |
358 | unsigned begin_block, unsigned end_block, | |
359 | unsigned max_entries, const void *value, | |
360 | dm_block_t *root) | |
361 | { | |
362 | int r = 0; | |
363 | ||
364 | for (; !r && begin_block != end_block; begin_block++) | |
365 | r = insert_new_ablock(info, size_of_block, max_entries, begin_block, max_entries, value, root); | |
366 | ||
367 | return r; | |
368 | } | |
369 | ||
370 | /* | |
371 | * There are a bunch of functions involved with resizing an array. This | |
372 | * structure holds information that commonly needed by them. Purely here | |
373 | * to reduce parameter count. | |
374 | */ | |
375 | struct resize { | |
376 | /* | |
377 | * Describes the array. | |
378 | */ | |
379 | struct dm_array_info *info; | |
380 | ||
381 | /* | |
382 | * The current root of the array. This gets updated. | |
383 | */ | |
384 | dm_block_t root; | |
385 | ||
386 | /* | |
387 | * Metadata block size. Used to calculate the nr entries in an | |
388 | * array block. | |
389 | */ | |
390 | size_t size_of_block; | |
391 | ||
392 | /* | |
393 | * Maximum nr entries in an array block. | |
394 | */ | |
395 | unsigned max_entries; | |
396 | ||
397 | /* | |
398 | * nr of completely full blocks in the array. | |
399 | * | |
400 | * 'old' refers to before the resize, 'new' after. | |
401 | */ | |
402 | unsigned old_nr_full_blocks, new_nr_full_blocks; | |
403 | ||
404 | /* | |
405 | * Number of entries in the final block. 0 iff only full blocks in | |
406 | * the array. | |
407 | */ | |
408 | unsigned old_nr_entries_in_last_block, new_nr_entries_in_last_block; | |
409 | ||
410 | /* | |
411 | * The default value used when growing the array. | |
412 | */ | |
413 | const void *value; | |
414 | }; | |
415 | ||
416 | /* | |
417 | * Removes a consecutive set of array blocks from the btree. The values | |
418 | * in block are decremented as a side effect of the btree remove. | |
419 | * | |
420 | * begin_index - the index of the first array block to remove. | |
421 | * end_index - the one-past-the-end value. ie. this block is not removed. | |
422 | */ | |
423 | static int drop_blocks(struct resize *resize, unsigned begin_index, | |
424 | unsigned end_index) | |
425 | { | |
426 | int r; | |
427 | ||
428 | while (begin_index != end_index) { | |
429 | uint64_t key = begin_index++; | |
430 | r = dm_btree_remove(&resize->info->btree_info, resize->root, | |
431 | &key, &resize->root); | |
432 | if (r) | |
433 | return r; | |
434 | } | |
435 | ||
436 | return 0; | |
437 | } | |
438 | ||
439 | /* | |
440 | * Calculates how many blocks are needed for the array. | |
441 | */ | |
442 | static unsigned total_nr_blocks_needed(unsigned nr_full_blocks, | |
443 | unsigned nr_entries_in_last_block) | |
444 | { | |
445 | return nr_full_blocks + (nr_entries_in_last_block ? 1 : 0); | |
446 | } | |
447 | ||
448 | /* | |
449 | * Shrink an array. | |
450 | */ | |
451 | static int shrink(struct resize *resize) | |
452 | { | |
453 | int r; | |
454 | unsigned begin, end; | |
455 | struct dm_block *block; | |
456 | struct array_block *ab; | |
457 | ||
458 | /* | |
459 | * Lose some blocks from the back? | |
460 | */ | |
461 | if (resize->new_nr_full_blocks < resize->old_nr_full_blocks) { | |
462 | begin = total_nr_blocks_needed(resize->new_nr_full_blocks, | |
463 | resize->new_nr_entries_in_last_block); | |
464 | end = total_nr_blocks_needed(resize->old_nr_full_blocks, | |
465 | resize->old_nr_entries_in_last_block); | |
466 | ||
467 | r = drop_blocks(resize, begin, end); | |
468 | if (r) | |
469 | return r; | |
470 | } | |
471 | ||
472 | /* | |
473 | * Trim the new tail block | |
474 | */ | |
475 | if (resize->new_nr_entries_in_last_block) { | |
476 | r = shadow_ablock(resize->info, &resize->root, | |
477 | resize->new_nr_full_blocks, &block, &ab); | |
478 | if (r) | |
479 | return r; | |
480 | ||
481 | trim_ablock(resize->info, ab, resize->new_nr_entries_in_last_block); | |
482 | unlock_ablock(resize->info, block); | |
483 | } | |
484 | ||
485 | return 0; | |
486 | } | |
487 | ||
488 | /* | |
489 | * Grow an array. | |
490 | */ | |
491 | static int grow_extend_tail_block(struct resize *resize, uint32_t new_nr_entries) | |
492 | { | |
493 | int r; | |
494 | struct dm_block *block; | |
495 | struct array_block *ab; | |
496 | ||
497 | r = shadow_ablock(resize->info, &resize->root, | |
498 | resize->old_nr_full_blocks, &block, &ab); | |
499 | if (r) | |
500 | return r; | |
501 | ||
502 | fill_ablock(resize->info, ab, resize->value, new_nr_entries); | |
503 | unlock_ablock(resize->info, block); | |
504 | ||
505 | return r; | |
506 | } | |
507 | ||
508 | static int grow_add_tail_block(struct resize *resize) | |
509 | { | |
510 | return insert_new_ablock(resize->info, resize->size_of_block, | |
511 | resize->max_entries, | |
512 | resize->new_nr_full_blocks, | |
513 | resize->new_nr_entries_in_last_block, | |
514 | resize->value, &resize->root); | |
515 | } | |
516 | ||
517 | static int grow_needs_more_blocks(struct resize *resize) | |
518 | { | |
519 | int r; | |
9c1d4de5 | 520 | unsigned old_nr_blocks = resize->old_nr_full_blocks; |
6513c29f JT |
521 | |
522 | if (resize->old_nr_entries_in_last_block > 0) { | |
9c1d4de5 JT |
523 | old_nr_blocks++; |
524 | ||
6513c29f JT |
525 | r = grow_extend_tail_block(resize, resize->max_entries); |
526 | if (r) | |
527 | return r; | |
528 | } | |
529 | ||
530 | r = insert_full_ablocks(resize->info, resize->size_of_block, | |
9c1d4de5 | 531 | old_nr_blocks, |
6513c29f JT |
532 | resize->new_nr_full_blocks, |
533 | resize->max_entries, resize->value, | |
534 | &resize->root); | |
535 | if (r) | |
536 | return r; | |
537 | ||
538 | if (resize->new_nr_entries_in_last_block) | |
539 | r = grow_add_tail_block(resize); | |
540 | ||
541 | return r; | |
542 | } | |
543 | ||
544 | static int grow(struct resize *resize) | |
545 | { | |
546 | if (resize->new_nr_full_blocks > resize->old_nr_full_blocks) | |
547 | return grow_needs_more_blocks(resize); | |
548 | ||
549 | else if (resize->old_nr_entries_in_last_block) | |
550 | return grow_extend_tail_block(resize, resize->new_nr_entries_in_last_block); | |
551 | ||
552 | else | |
553 | return grow_add_tail_block(resize); | |
554 | } | |
555 | ||
556 | /*----------------------------------------------------------------*/ | |
557 | ||
558 | /* | |
559 | * These are the value_type functions for the btree elements, which point | |
560 | * to array blocks. | |
561 | */ | |
562 | static void block_inc(void *context, const void *value) | |
563 | { | |
564 | __le64 block_le; | |
565 | struct dm_array_info *info = context; | |
566 | ||
567 | memcpy(&block_le, value, sizeof(block_le)); | |
568 | dm_tm_inc(info->btree_info.tm, le64_to_cpu(block_le)); | |
569 | } | |
570 | ||
571 | static void block_dec(void *context, const void *value) | |
572 | { | |
573 | int r; | |
574 | uint64_t b; | |
575 | __le64 block_le; | |
576 | uint32_t ref_count; | |
577 | struct dm_block *block; | |
578 | struct array_block *ab; | |
579 | struct dm_array_info *info = context; | |
580 | ||
581 | memcpy(&block_le, value, sizeof(block_le)); | |
582 | b = le64_to_cpu(block_le); | |
583 | ||
584 | r = dm_tm_ref(info->btree_info.tm, b, &ref_count); | |
585 | if (r) { | |
586 | DMERR_LIMIT("couldn't get reference count for block %llu", | |
587 | (unsigned long long) b); | |
588 | return; | |
589 | } | |
590 | ||
591 | if (ref_count == 1) { | |
592 | /* | |
593 | * We're about to drop the last reference to this ablock. | |
594 | * So we need to decrement the ref count of the contents. | |
595 | */ | |
596 | r = get_ablock(info, b, &block, &ab); | |
597 | if (r) { | |
598 | DMERR_LIMIT("couldn't get array block %llu", | |
599 | (unsigned long long) b); | |
600 | return; | |
601 | } | |
602 | ||
603 | dec_ablock_entries(info, ab); | |
604 | unlock_ablock(info, block); | |
605 | } | |
606 | ||
607 | dm_tm_dec(info->btree_info.tm, b); | |
608 | } | |
609 | ||
610 | static int block_equal(void *context, const void *value1, const void *value2) | |
611 | { | |
612 | return !memcmp(value1, value2, sizeof(__le64)); | |
613 | } | |
614 | ||
615 | /*----------------------------------------------------------------*/ | |
616 | ||
617 | void dm_array_info_init(struct dm_array_info *info, | |
618 | struct dm_transaction_manager *tm, | |
619 | struct dm_btree_value_type *vt) | |
620 | { | |
621 | struct dm_btree_value_type *bvt = &info->btree_info.value_type; | |
622 | ||
623 | memcpy(&info->value_type, vt, sizeof(info->value_type)); | |
624 | info->btree_info.tm = tm; | |
625 | info->btree_info.levels = 1; | |
626 | ||
627 | bvt->context = info; | |
628 | bvt->size = sizeof(__le64); | |
629 | bvt->inc = block_inc; | |
630 | bvt->dec = block_dec; | |
631 | bvt->equal = block_equal; | |
632 | } | |
633 | EXPORT_SYMBOL_GPL(dm_array_info_init); | |
634 | ||
635 | int dm_array_empty(struct dm_array_info *info, dm_block_t *root) | |
636 | { | |
637 | return dm_btree_empty(&info->btree_info, root); | |
638 | } | |
639 | EXPORT_SYMBOL_GPL(dm_array_empty); | |
640 | ||
641 | static int array_resize(struct dm_array_info *info, dm_block_t root, | |
642 | uint32_t old_size, uint32_t new_size, | |
643 | const void *value, dm_block_t *new_root) | |
644 | { | |
645 | int r; | |
646 | struct resize resize; | |
647 | ||
648 | if (old_size == new_size) | |
649 | return 0; | |
650 | ||
651 | resize.info = info; | |
652 | resize.root = root; | |
653 | resize.size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm)); | |
654 | resize.max_entries = calc_max_entries(info->value_type.size, | |
655 | resize.size_of_block); | |
656 | ||
657 | resize.old_nr_full_blocks = old_size / resize.max_entries; | |
658 | resize.old_nr_entries_in_last_block = old_size % resize.max_entries; | |
659 | resize.new_nr_full_blocks = new_size / resize.max_entries; | |
660 | resize.new_nr_entries_in_last_block = new_size % resize.max_entries; | |
661 | resize.value = value; | |
662 | ||
663 | r = ((new_size > old_size) ? grow : shrink)(&resize); | |
664 | if (r) | |
665 | return r; | |
666 | ||
667 | *new_root = resize.root; | |
668 | return 0; | |
669 | } | |
670 | ||
671 | int dm_array_resize(struct dm_array_info *info, dm_block_t root, | |
672 | uint32_t old_size, uint32_t new_size, | |
673 | const void *value, dm_block_t *new_root) | |
674 | __dm_written_to_disk(value) | |
675 | { | |
676 | int r = array_resize(info, root, old_size, new_size, value, new_root); | |
677 | __dm_unbless_for_disk(value); | |
678 | return r; | |
679 | } | |
680 | EXPORT_SYMBOL_GPL(dm_array_resize); | |
681 | ||
682 | int dm_array_del(struct dm_array_info *info, dm_block_t root) | |
683 | { | |
684 | return dm_btree_del(&info->btree_info, root); | |
685 | } | |
686 | EXPORT_SYMBOL_GPL(dm_array_del); | |
687 | ||
688 | int dm_array_get_value(struct dm_array_info *info, dm_block_t root, | |
689 | uint32_t index, void *value_le) | |
690 | { | |
691 | int r; | |
692 | struct dm_block *block; | |
693 | struct array_block *ab; | |
694 | size_t size_of_block; | |
695 | unsigned entry, max_entries; | |
696 | ||
697 | size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm)); | |
698 | max_entries = calc_max_entries(info->value_type.size, size_of_block); | |
699 | ||
700 | r = lookup_ablock(info, root, index / max_entries, &block, &ab); | |
701 | if (r) | |
702 | return r; | |
703 | ||
704 | entry = index % max_entries; | |
705 | if (entry >= le32_to_cpu(ab->nr_entries)) | |
706 | r = -ENODATA; | |
707 | else | |
708 | memcpy(value_le, element_at(info, ab, entry), | |
709 | info->value_type.size); | |
710 | ||
711 | unlock_ablock(info, block); | |
712 | return r; | |
713 | } | |
714 | EXPORT_SYMBOL_GPL(dm_array_get_value); | |
715 | ||
716 | static int array_set_value(struct dm_array_info *info, dm_block_t root, | |
717 | uint32_t index, const void *value, dm_block_t *new_root) | |
718 | { | |
719 | int r; | |
720 | struct dm_block *block; | |
721 | struct array_block *ab; | |
722 | size_t size_of_block; | |
723 | unsigned max_entries; | |
724 | unsigned entry; | |
725 | void *old_value; | |
726 | struct dm_btree_value_type *vt = &info->value_type; | |
727 | ||
728 | size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm)); | |
729 | max_entries = calc_max_entries(info->value_type.size, size_of_block); | |
730 | ||
731 | r = shadow_ablock(info, &root, index / max_entries, &block, &ab); | |
732 | if (r) | |
733 | return r; | |
734 | *new_root = root; | |
735 | ||
736 | entry = index % max_entries; | |
737 | if (entry >= le32_to_cpu(ab->nr_entries)) { | |
738 | r = -ENODATA; | |
739 | goto out; | |
740 | } | |
741 | ||
742 | old_value = element_at(info, ab, entry); | |
743 | if (vt->dec && | |
744 | (!vt->equal || !vt->equal(vt->context, old_value, value))) { | |
745 | vt->dec(vt->context, old_value); | |
746 | if (vt->inc) | |
747 | vt->inc(vt->context, value); | |
748 | } | |
749 | ||
750 | memcpy(old_value, value, info->value_type.size); | |
751 | ||
752 | out: | |
753 | unlock_ablock(info, block); | |
754 | return r; | |
755 | } | |
756 | ||
757 | int dm_array_set_value(struct dm_array_info *info, dm_block_t root, | |
758 | uint32_t index, const void *value, dm_block_t *new_root) | |
759 | __dm_written_to_disk(value) | |
760 | { | |
761 | int r; | |
762 | ||
763 | r = array_set_value(info, root, index, value, new_root); | |
764 | __dm_unbless_for_disk(value); | |
765 | return r; | |
766 | } | |
767 | EXPORT_SYMBOL_GPL(dm_array_set_value); | |
768 | ||
769 | struct walk_info { | |
770 | struct dm_array_info *info; | |
771 | int (*fn)(void *context, uint64_t key, void *leaf); | |
772 | void *context; | |
773 | }; | |
774 | ||
775 | static int walk_ablock(void *context, uint64_t *keys, void *leaf) | |
776 | { | |
777 | struct walk_info *wi = context; | |
778 | ||
779 | int r; | |
780 | unsigned i; | |
781 | __le64 block_le; | |
782 | unsigned nr_entries, max_entries; | |
783 | struct dm_block *block; | |
784 | struct array_block *ab; | |
785 | ||
786 | memcpy(&block_le, leaf, sizeof(block_le)); | |
787 | r = get_ablock(wi->info, le64_to_cpu(block_le), &block, &ab); | |
788 | if (r) | |
789 | return r; | |
790 | ||
791 | max_entries = le32_to_cpu(ab->max_entries); | |
792 | nr_entries = le32_to_cpu(ab->nr_entries); | |
793 | for (i = 0; i < nr_entries; i++) { | |
794 | r = wi->fn(wi->context, keys[0] * max_entries + i, | |
795 | element_at(wi->info, ab, i)); | |
796 | ||
797 | if (r) | |
798 | break; | |
799 | } | |
800 | ||
801 | unlock_ablock(wi->info, block); | |
802 | return r; | |
803 | } | |
804 | ||
805 | int dm_array_walk(struct dm_array_info *info, dm_block_t root, | |
806 | int (*fn)(void *, uint64_t key, void *leaf), | |
807 | void *context) | |
808 | { | |
809 | struct walk_info wi; | |
810 | ||
811 | wi.info = info; | |
812 | wi.fn = fn; | |
813 | wi.context = context; | |
814 | ||
815 | return dm_btree_walk(&info->btree_info, root, walk_ablock, &wi); | |
816 | } | |
817 | EXPORT_SYMBOL_GPL(dm_array_walk); | |
818 | ||
819 | /*----------------------------------------------------------------*/ |