dm-array.c 24 KB

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