dm-array.c 24 KB

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