dm-btree-remove.c 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688
  1. /*
  2. * Copyright (C) 2011 Red Hat, Inc.
  3. *
  4. * This file is released under the GPL.
  5. */
  6. #include "dm-btree.h"
  7. #include "dm-btree-internal.h"
  8. #include "dm-transaction-manager.h"
  9. #include <linux/export.h>
  10. /*
  11. * Removing an entry from a btree
  12. * ==============================
  13. *
  14. * A very important constraint for our btree is that no node, except the
  15. * root, may have fewer than a certain number of entries.
  16. * (MIN_ENTRIES <= nr_entries <= MAX_ENTRIES).
  17. *
  18. * Ensuring this is complicated by the way we want to only ever hold the
  19. * locks on 2 nodes concurrently, and only change nodes in a top to bottom
  20. * fashion.
  21. *
  22. * Each node may have a left or right sibling. When decending the spine,
  23. * if a node contains only MIN_ENTRIES then we try and increase this to at
  24. * least MIN_ENTRIES + 1. We do this in the following ways:
  25. *
  26. * [A] No siblings => this can only happen if the node is the root, in which
  27. * case we copy the childs contents over the root.
  28. *
  29. * [B] No left sibling
  30. * ==> rebalance(node, right sibling)
  31. *
  32. * [C] No right sibling
  33. * ==> rebalance(left sibling, node)
  34. *
  35. * [D] Both siblings, total_entries(left, node, right) <= DEL_THRESHOLD
  36. * ==> delete node adding it's contents to left and right
  37. *
  38. * [E] Both siblings, total_entries(left, node, right) > DEL_THRESHOLD
  39. * ==> rebalance(left, node, right)
  40. *
  41. * After these operations it's possible that the our original node no
  42. * longer contains the desired sub tree. For this reason this rebalancing
  43. * is performed on the children of the current node. This also avoids
  44. * having a special case for the root.
  45. *
  46. * Once this rebalancing has occurred we can then step into the child node
  47. * for internal nodes. Or delete the entry for leaf nodes.
  48. */
  49. /*
  50. * Some little utilities for moving node data around.
  51. */
  52. static void node_shift(struct btree_node *n, int shift)
  53. {
  54. uint32_t nr_entries = le32_to_cpu(n->header.nr_entries);
  55. uint32_t value_size = le32_to_cpu(n->header.value_size);
  56. if (shift < 0) {
  57. shift = -shift;
  58. BUG_ON(shift > nr_entries);
  59. BUG_ON((void *) key_ptr(n, shift) >= value_ptr(n, shift));
  60. memmove(key_ptr(n, 0),
  61. key_ptr(n, shift),
  62. (nr_entries - shift) * sizeof(__le64));
  63. memmove(value_ptr(n, 0),
  64. value_ptr(n, shift),
  65. (nr_entries - shift) * value_size);
  66. } else {
  67. BUG_ON(nr_entries + shift > le32_to_cpu(n->header.max_entries));
  68. memmove(key_ptr(n, shift),
  69. key_ptr(n, 0),
  70. nr_entries * sizeof(__le64));
  71. memmove(value_ptr(n, shift),
  72. value_ptr(n, 0),
  73. nr_entries * value_size);
  74. }
  75. }
  76. static void node_copy(struct btree_node *left, struct btree_node *right, int shift)
  77. {
  78. uint32_t nr_left = le32_to_cpu(left->header.nr_entries);
  79. uint32_t value_size = le32_to_cpu(left->header.value_size);
  80. BUG_ON(value_size != le32_to_cpu(right->header.value_size));
  81. if (shift < 0) {
  82. shift = -shift;
  83. BUG_ON(nr_left + shift > le32_to_cpu(left->header.max_entries));
  84. memcpy(key_ptr(left, nr_left),
  85. key_ptr(right, 0),
  86. shift * sizeof(__le64));
  87. memcpy(value_ptr(left, nr_left),
  88. value_ptr(right, 0),
  89. shift * value_size);
  90. } else {
  91. BUG_ON(shift > le32_to_cpu(right->header.max_entries));
  92. memcpy(key_ptr(right, 0),
  93. key_ptr(left, nr_left - shift),
  94. shift * sizeof(__le64));
  95. memcpy(value_ptr(right, 0),
  96. value_ptr(left, nr_left - shift),
  97. shift * value_size);
  98. }
  99. }
  100. /*
  101. * Delete a specific entry from a leaf node.
  102. */
  103. static void delete_at(struct btree_node *n, unsigned index)
  104. {
  105. unsigned nr_entries = le32_to_cpu(n->header.nr_entries);
  106. unsigned nr_to_copy = nr_entries - (index + 1);
  107. uint32_t value_size = le32_to_cpu(n->header.value_size);
  108. BUG_ON(index >= nr_entries);
  109. if (nr_to_copy) {
  110. memmove(key_ptr(n, index),
  111. key_ptr(n, index + 1),
  112. nr_to_copy * sizeof(__le64));
  113. memmove(value_ptr(n, index),
  114. value_ptr(n, index + 1),
  115. nr_to_copy * value_size);
  116. }
  117. n->header.nr_entries = cpu_to_le32(nr_entries - 1);
  118. }
  119. static unsigned merge_threshold(struct btree_node *n)
  120. {
  121. return le32_to_cpu(n->header.max_entries) / 3;
  122. }
  123. struct child {
  124. unsigned index;
  125. struct dm_block *block;
  126. struct btree_node *n;
  127. };
  128. static int init_child(struct dm_btree_info *info, struct dm_btree_value_type *vt,
  129. struct btree_node *parent,
  130. unsigned index, struct child *result)
  131. {
  132. int r, inc;
  133. dm_block_t root;
  134. result->index = index;
  135. root = value64(parent, index);
  136. r = dm_tm_shadow_block(info->tm, root, &btree_node_validator,
  137. &result->block, &inc);
  138. if (r)
  139. return r;
  140. result->n = dm_block_data(result->block);
  141. if (inc)
  142. inc_children(info->tm, result->n, vt);
  143. *((__le64 *) value_ptr(parent, index)) =
  144. cpu_to_le64(dm_block_location(result->block));
  145. return 0;
  146. }
  147. static void exit_child(struct dm_btree_info *info, struct child *c)
  148. {
  149. dm_tm_unlock(info->tm, c->block);
  150. }
  151. static void shift(struct btree_node *left, struct btree_node *right, int count)
  152. {
  153. uint32_t nr_left = le32_to_cpu(left->header.nr_entries);
  154. uint32_t nr_right = le32_to_cpu(right->header.nr_entries);
  155. uint32_t max_entries = le32_to_cpu(left->header.max_entries);
  156. uint32_t r_max_entries = le32_to_cpu(right->header.max_entries);
  157. BUG_ON(max_entries != r_max_entries);
  158. BUG_ON(nr_left - count > max_entries);
  159. BUG_ON(nr_right + count > max_entries);
  160. if (!count)
  161. return;
  162. if (count > 0) {
  163. node_shift(right, count);
  164. node_copy(left, right, count);
  165. } else {
  166. node_copy(left, right, count);
  167. node_shift(right, count);
  168. }
  169. left->header.nr_entries = cpu_to_le32(nr_left - count);
  170. right->header.nr_entries = cpu_to_le32(nr_right + count);
  171. }
  172. static void __rebalance2(struct dm_btree_info *info, struct btree_node *parent,
  173. struct child *l, struct child *r)
  174. {
  175. struct btree_node *left = l->n;
  176. struct btree_node *right = r->n;
  177. uint32_t nr_left = le32_to_cpu(left->header.nr_entries);
  178. uint32_t nr_right = le32_to_cpu(right->header.nr_entries);
  179. /*
  180. * Ensure the number of entries in each child will be greater
  181. * than or equal to (max_entries / 3 + 1), so no matter which
  182. * child is used for removal, the number will still be not
  183. * less than (max_entries / 3).
  184. */
  185. unsigned int threshold = 2 * (merge_threshold(left) + 1);
  186. if (nr_left + nr_right < threshold) {
  187. /*
  188. * Merge
  189. */
  190. node_copy(left, right, -nr_right);
  191. left->header.nr_entries = cpu_to_le32(nr_left + nr_right);
  192. delete_at(parent, r->index);
  193. /*
  194. * We need to decrement the right block, but not it's
  195. * children, since they're still referenced by left.
  196. */
  197. dm_tm_dec(info->tm, dm_block_location(r->block));
  198. } else {
  199. /*
  200. * Rebalance.
  201. */
  202. unsigned target_left = (nr_left + nr_right) / 2;
  203. shift(left, right, nr_left - target_left);
  204. *key_ptr(parent, r->index) = right->keys[0];
  205. }
  206. }
  207. static int rebalance2(struct shadow_spine *s, struct dm_btree_info *info,
  208. struct dm_btree_value_type *vt, unsigned left_index)
  209. {
  210. int r;
  211. struct btree_node *parent;
  212. struct child left, right;
  213. parent = dm_block_data(shadow_current(s));
  214. r = init_child(info, vt, parent, left_index, &left);
  215. if (r)
  216. return r;
  217. r = init_child(info, vt, parent, left_index + 1, &right);
  218. if (r) {
  219. exit_child(info, &left);
  220. return r;
  221. }
  222. __rebalance2(info, parent, &left, &right);
  223. exit_child(info, &left);
  224. exit_child(info, &right);
  225. return 0;
  226. }
  227. /*
  228. * We dump as many entries from center as possible into left, then the rest
  229. * in right, then rebalance2. This wastes some cpu, but I want something
  230. * simple atm.
  231. */
  232. static void delete_center_node(struct dm_btree_info *info, struct btree_node *parent,
  233. struct child *l, struct child *c, struct child *r,
  234. struct btree_node *left, struct btree_node *center, struct btree_node *right,
  235. uint32_t nr_left, uint32_t nr_center, uint32_t nr_right)
  236. {
  237. uint32_t max_entries = le32_to_cpu(left->header.max_entries);
  238. unsigned shift = min(max_entries - nr_left, nr_center);
  239. BUG_ON(nr_left + shift > max_entries);
  240. node_copy(left, center, -shift);
  241. left->header.nr_entries = cpu_to_le32(nr_left + shift);
  242. if (shift != nr_center) {
  243. shift = nr_center - shift;
  244. BUG_ON((nr_right + shift) > max_entries);
  245. node_shift(right, shift);
  246. node_copy(center, right, shift);
  247. right->header.nr_entries = cpu_to_le32(nr_right + shift);
  248. }
  249. *key_ptr(parent, r->index) = right->keys[0];
  250. delete_at(parent, c->index);
  251. r->index--;
  252. dm_tm_dec(info->tm, dm_block_location(c->block));
  253. __rebalance2(info, parent, l, r);
  254. }
  255. /*
  256. * Redistributes entries among 3 sibling nodes.
  257. */
  258. static void redistribute3(struct dm_btree_info *info, struct btree_node *parent,
  259. struct child *l, struct child *c, struct child *r,
  260. struct btree_node *left, struct btree_node *center, struct btree_node *right,
  261. uint32_t nr_left, uint32_t nr_center, uint32_t nr_right)
  262. {
  263. int s;
  264. uint32_t max_entries = le32_to_cpu(left->header.max_entries);
  265. unsigned total = nr_left + nr_center + nr_right;
  266. unsigned target_right = total / 3;
  267. unsigned remainder = (target_right * 3) != total;
  268. unsigned target_left = target_right + remainder;
  269. BUG_ON(target_left > max_entries);
  270. BUG_ON(target_right > max_entries);
  271. if (nr_left < nr_right) {
  272. s = nr_left - target_left;
  273. if (s < 0 && nr_center < -s) {
  274. /* not enough in central node */
  275. shift(left, center, -nr_center);
  276. s += nr_center;
  277. shift(left, right, s);
  278. nr_right += s;
  279. } else
  280. shift(left, center, s);
  281. shift(center, right, target_right - nr_right);
  282. } else {
  283. s = target_right - nr_right;
  284. if (s > 0 && nr_center < s) {
  285. /* not enough in central node */
  286. shift(center, right, nr_center);
  287. s -= nr_center;
  288. shift(left, right, s);
  289. nr_left -= s;
  290. } else
  291. shift(center, right, s);
  292. shift(left, center, nr_left - target_left);
  293. }
  294. *key_ptr(parent, c->index) = center->keys[0];
  295. *key_ptr(parent, r->index) = right->keys[0];
  296. }
  297. static void __rebalance3(struct dm_btree_info *info, struct btree_node *parent,
  298. struct child *l, struct child *c, struct child *r)
  299. {
  300. struct btree_node *left = l->n;
  301. struct btree_node *center = c->n;
  302. struct btree_node *right = r->n;
  303. uint32_t nr_left = le32_to_cpu(left->header.nr_entries);
  304. uint32_t nr_center = le32_to_cpu(center->header.nr_entries);
  305. uint32_t nr_right = le32_to_cpu(right->header.nr_entries);
  306. unsigned threshold = merge_threshold(left) * 4 + 1;
  307. BUG_ON(left->header.max_entries != center->header.max_entries);
  308. BUG_ON(center->header.max_entries != right->header.max_entries);
  309. if ((nr_left + nr_center + nr_right) < threshold)
  310. delete_center_node(info, parent, l, c, r, left, center, right,
  311. nr_left, nr_center, nr_right);
  312. else
  313. redistribute3(info, parent, l, c, r, left, center, right,
  314. nr_left, nr_center, nr_right);
  315. }
  316. static int rebalance3(struct shadow_spine *s, struct dm_btree_info *info,
  317. struct dm_btree_value_type *vt, unsigned left_index)
  318. {
  319. int r;
  320. struct btree_node *parent = dm_block_data(shadow_current(s));
  321. struct child left, center, right;
  322. /*
  323. * FIXME: fill out an array?
  324. */
  325. r = init_child(info, vt, parent, left_index, &left);
  326. if (r)
  327. return r;
  328. r = init_child(info, vt, parent, left_index + 1, &center);
  329. if (r) {
  330. exit_child(info, &left);
  331. return r;
  332. }
  333. r = init_child(info, vt, parent, left_index + 2, &right);
  334. if (r) {
  335. exit_child(info, &left);
  336. exit_child(info, &center);
  337. return r;
  338. }
  339. __rebalance3(info, parent, &left, &center, &right);
  340. exit_child(info, &left);
  341. exit_child(info, &center);
  342. exit_child(info, &right);
  343. return 0;
  344. }
  345. static int rebalance_children(struct shadow_spine *s,
  346. struct dm_btree_info *info,
  347. struct dm_btree_value_type *vt, uint64_t key)
  348. {
  349. int i, r, has_left_sibling, has_right_sibling;
  350. struct btree_node *n;
  351. n = dm_block_data(shadow_current(s));
  352. if (le32_to_cpu(n->header.nr_entries) == 1) {
  353. struct dm_block *child;
  354. dm_block_t b = value64(n, 0);
  355. r = dm_tm_read_lock(info->tm, b, &btree_node_validator, &child);
  356. if (r)
  357. return r;
  358. memcpy(n, dm_block_data(child),
  359. dm_bm_block_size(dm_tm_get_bm(info->tm)));
  360. dm_tm_dec(info->tm, dm_block_location(child));
  361. dm_tm_unlock(info->tm, child);
  362. return 0;
  363. }
  364. i = lower_bound(n, key);
  365. if (i < 0)
  366. return -ENODATA;
  367. has_left_sibling = i > 0;
  368. has_right_sibling = i < (le32_to_cpu(n->header.nr_entries) - 1);
  369. if (!has_left_sibling)
  370. r = rebalance2(s, info, vt, i);
  371. else if (!has_right_sibling)
  372. r = rebalance2(s, info, vt, i - 1);
  373. else
  374. r = rebalance3(s, info, vt, i - 1);
  375. return r;
  376. }
  377. static int do_leaf(struct btree_node *n, uint64_t key, unsigned *index)
  378. {
  379. int i = lower_bound(n, key);
  380. if ((i < 0) ||
  381. (i >= le32_to_cpu(n->header.nr_entries)) ||
  382. (le64_to_cpu(n->keys[i]) != key))
  383. return -ENODATA;
  384. *index = i;
  385. return 0;
  386. }
  387. /*
  388. * Prepares for removal from one level of the hierarchy. The caller must
  389. * call delete_at() to remove the entry at index.
  390. */
  391. static int remove_raw(struct shadow_spine *s, struct dm_btree_info *info,
  392. struct dm_btree_value_type *vt, dm_block_t root,
  393. uint64_t key, unsigned *index)
  394. {
  395. int i = *index, r;
  396. struct btree_node *n;
  397. for (;;) {
  398. r = shadow_step(s, root, vt);
  399. if (r < 0)
  400. break;
  401. /*
  402. * We have to patch up the parent node, ugly, but I don't
  403. * see a way to do this automatically as part of the spine
  404. * op.
  405. */
  406. if (shadow_has_parent(s)) {
  407. __le64 location = cpu_to_le64(dm_block_location(shadow_current(s)));
  408. memcpy(value_ptr(dm_block_data(shadow_parent(s)), i),
  409. &location, sizeof(__le64));
  410. }
  411. n = dm_block_data(shadow_current(s));
  412. if (le32_to_cpu(n->header.flags) & LEAF_NODE)
  413. return do_leaf(n, key, index);
  414. r = rebalance_children(s, info, vt, key);
  415. if (r)
  416. break;
  417. n = dm_block_data(shadow_current(s));
  418. if (le32_to_cpu(n->header.flags) & LEAF_NODE)
  419. return do_leaf(n, key, index);
  420. i = lower_bound(n, key);
  421. /*
  422. * We know the key is present, or else
  423. * rebalance_children would have returned
  424. * -ENODATA
  425. */
  426. root = value64(n, i);
  427. }
  428. return r;
  429. }
  430. int dm_btree_remove(struct dm_btree_info *info, dm_block_t root,
  431. uint64_t *keys, dm_block_t *new_root)
  432. {
  433. unsigned level, last_level = info->levels - 1;
  434. int index = 0, r = 0;
  435. struct shadow_spine spine;
  436. struct btree_node *n;
  437. struct dm_btree_value_type le64_vt;
  438. init_le64_type(info->tm, &le64_vt);
  439. init_shadow_spine(&spine, info);
  440. for (level = 0; level < info->levels; level++) {
  441. r = remove_raw(&spine, info,
  442. (level == last_level ?
  443. &info->value_type : &le64_vt),
  444. root, keys[level], (unsigned *)&index);
  445. if (r < 0)
  446. break;
  447. n = dm_block_data(shadow_current(&spine));
  448. if (level != last_level) {
  449. root = value64(n, index);
  450. continue;
  451. }
  452. BUG_ON(index < 0 || index >= le32_to_cpu(n->header.nr_entries));
  453. if (info->value_type.dec)
  454. info->value_type.dec(info->value_type.context,
  455. value_ptr(n, index));
  456. delete_at(n, index);
  457. }
  458. if (!r)
  459. *new_root = shadow_root(&spine);
  460. exit_shadow_spine(&spine);
  461. return r;
  462. }
  463. EXPORT_SYMBOL_GPL(dm_btree_remove);
  464. /*----------------------------------------------------------------*/
  465. static int remove_nearest(struct shadow_spine *s, struct dm_btree_info *info,
  466. struct dm_btree_value_type *vt, dm_block_t root,
  467. uint64_t key, int *index)
  468. {
  469. int i = *index, r;
  470. struct btree_node *n;
  471. for (;;) {
  472. r = shadow_step(s, root, vt);
  473. if (r < 0)
  474. break;
  475. /*
  476. * We have to patch up the parent node, ugly, but I don't
  477. * see a way to do this automatically as part of the spine
  478. * op.
  479. */
  480. if (shadow_has_parent(s)) {
  481. __le64 location = cpu_to_le64(dm_block_location(shadow_current(s)));
  482. memcpy(value_ptr(dm_block_data(shadow_parent(s)), i),
  483. &location, sizeof(__le64));
  484. }
  485. n = dm_block_data(shadow_current(s));
  486. if (le32_to_cpu(n->header.flags) & LEAF_NODE) {
  487. *index = lower_bound(n, key);
  488. return 0;
  489. }
  490. r = rebalance_children(s, info, vt, key);
  491. if (r)
  492. break;
  493. n = dm_block_data(shadow_current(s));
  494. if (le32_to_cpu(n->header.flags) & LEAF_NODE) {
  495. *index = lower_bound(n, key);
  496. return 0;
  497. }
  498. i = lower_bound(n, key);
  499. /*
  500. * We know the key is present, or else
  501. * rebalance_children would have returned
  502. * -ENODATA
  503. */
  504. root = value64(n, i);
  505. }
  506. return r;
  507. }
  508. static int remove_one(struct dm_btree_info *info, dm_block_t root,
  509. uint64_t *keys, uint64_t end_key,
  510. dm_block_t *new_root, unsigned *nr_removed)
  511. {
  512. unsigned level, last_level = info->levels - 1;
  513. int index = 0, r = 0;
  514. struct shadow_spine spine;
  515. struct btree_node *n;
  516. struct dm_btree_value_type le64_vt;
  517. uint64_t k;
  518. init_le64_type(info->tm, &le64_vt);
  519. init_shadow_spine(&spine, info);
  520. for (level = 0; level < last_level; level++) {
  521. r = remove_raw(&spine, info, &le64_vt,
  522. root, keys[level], (unsigned *) &index);
  523. if (r < 0)
  524. goto out;
  525. n = dm_block_data(shadow_current(&spine));
  526. root = value64(n, index);
  527. }
  528. r = remove_nearest(&spine, info, &info->value_type,
  529. root, keys[last_level], &index);
  530. if (r < 0)
  531. goto out;
  532. n = dm_block_data(shadow_current(&spine));
  533. if (index < 0)
  534. index = 0;
  535. if (index >= le32_to_cpu(n->header.nr_entries)) {
  536. r = -ENODATA;
  537. goto out;
  538. }
  539. k = le64_to_cpu(n->keys[index]);
  540. if (k >= keys[last_level] && k < end_key) {
  541. if (info->value_type.dec)
  542. info->value_type.dec(info->value_type.context,
  543. value_ptr(n, index));
  544. delete_at(n, index);
  545. keys[last_level] = k + 1ull;
  546. } else
  547. r = -ENODATA;
  548. out:
  549. *new_root = shadow_root(&spine);
  550. exit_shadow_spine(&spine);
  551. return r;
  552. }
  553. int dm_btree_remove_leaves(struct dm_btree_info *info, dm_block_t root,
  554. uint64_t *first_key, uint64_t end_key,
  555. dm_block_t *new_root, unsigned *nr_removed)
  556. {
  557. int r;
  558. *nr_removed = 0;
  559. do {
  560. r = remove_one(info, root, first_key, end_key, &root, nr_removed);
  561. if (!r)
  562. (*nr_removed)++;
  563. } while (!r);
  564. *new_root = root;
  565. return r == -ENODATA ? 0 : r;
  566. }
  567. EXPORT_SYMBOL_GPL(dm_btree_remove_leaves);