dm-btree.h 6.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215
  1. /*
  2. * Copyright (C) 2011 Red Hat, Inc.
  3. *
  4. * This file is released under the GPL.
  5. */
  6. #ifndef _LINUX_DM_BTREE_H
  7. #define _LINUX_DM_BTREE_H
  8. #include "dm-block-manager.h"
  9. struct dm_transaction_manager;
  10. /*----------------------------------------------------------------*/
  11. /*
  12. * Annotations used to check on-disk metadata is handled as little-endian.
  13. */
  14. #ifdef __CHECKER__
  15. # define __dm_written_to_disk(x) __releases(x)
  16. # define __dm_reads_from_disk(x) __acquires(x)
  17. # define __dm_bless_for_disk(x) __acquire(x)
  18. # define __dm_unbless_for_disk(x) __release(x)
  19. #else
  20. # define __dm_written_to_disk(x)
  21. # define __dm_reads_from_disk(x)
  22. # define __dm_bless_for_disk(x)
  23. # define __dm_unbless_for_disk(x)
  24. #endif
  25. /*----------------------------------------------------------------*/
  26. /*
  27. * Manipulates hierarchical B+ trees with 64-bit keys and arbitrary-sized
  28. * values.
  29. */
  30. /*
  31. * Information about the values stored within the btree.
  32. */
  33. struct dm_btree_value_type {
  34. void *context;
  35. /*
  36. * The size in bytes of each value.
  37. */
  38. uint32_t size;
  39. /*
  40. * Any of these methods can be safely set to NULL if you do not
  41. * need the corresponding feature.
  42. */
  43. /*
  44. * The btree is making a duplicate of the value, for instance
  45. * because previously-shared btree nodes have now diverged.
  46. * @value argument is the new copy that the copy function may modify.
  47. * (Probably it just wants to increment a reference count
  48. * somewhere.) This method is _not_ called for insertion of a new
  49. * value: It is assumed the ref count is already 1.
  50. */
  51. void (*inc)(void *context, const void *value);
  52. /*
  53. * This value is being deleted. The btree takes care of freeing
  54. * the memory pointed to by @value. Often the del function just
  55. * needs to decrement a reference count somewhere.
  56. */
  57. void (*dec)(void *context, const void *value);
  58. /*
  59. * A test for equality between two values. When a value is
  60. * overwritten with a new one, the old one has the dec method
  61. * called _unless_ the new and old value are deemed equal.
  62. */
  63. int (*equal)(void *context, const void *value1, const void *value2);
  64. };
  65. /*
  66. * The shape and contents of a btree.
  67. */
  68. struct dm_btree_info {
  69. struct dm_transaction_manager *tm;
  70. /*
  71. * Number of nested btrees. (Not the depth of a single tree.)
  72. */
  73. unsigned levels;
  74. struct dm_btree_value_type value_type;
  75. };
  76. /*
  77. * Set up an empty tree. O(1).
  78. */
  79. int dm_btree_empty(struct dm_btree_info *info, dm_block_t *root);
  80. /*
  81. * Delete a tree. O(n) - this is the slow one! It can also block, so
  82. * please don't call it on an IO path.
  83. */
  84. int dm_btree_del(struct dm_btree_info *info, dm_block_t root);
  85. /*
  86. * All the lookup functions return -ENODATA if the key cannot be found.
  87. */
  88. /*
  89. * Tries to find a key that matches exactly. O(ln(n))
  90. */
  91. int dm_btree_lookup(struct dm_btree_info *info, dm_block_t root,
  92. uint64_t *keys, void *value_le);
  93. /*
  94. * Tries to find the first key where the bottom level key is >= to that
  95. * given. Useful for skipping empty sections of the btree.
  96. */
  97. int dm_btree_lookup_next(struct dm_btree_info *info, dm_block_t root,
  98. uint64_t *keys, uint64_t *rkey, void *value_le);
  99. /*
  100. * Insertion (or overwrite an existing value). O(ln(n))
  101. */
  102. int dm_btree_insert(struct dm_btree_info *info, dm_block_t root,
  103. uint64_t *keys, void *value, dm_block_t *new_root)
  104. __dm_written_to_disk(value);
  105. /*
  106. * A variant of insert that indicates whether it actually inserted or just
  107. * overwrote. Useful if you're keeping track of the number of entries in a
  108. * tree.
  109. */
  110. int dm_btree_insert_notify(struct dm_btree_info *info, dm_block_t root,
  111. uint64_t *keys, void *value, dm_block_t *new_root,
  112. int *inserted)
  113. __dm_written_to_disk(value);
  114. /*
  115. * Remove a key if present. This doesn't remove empty sub trees. Normally
  116. * subtrees represent a separate entity, like a snapshot map, so this is
  117. * correct behaviour. O(ln(n)).
  118. */
  119. int dm_btree_remove(struct dm_btree_info *info, dm_block_t root,
  120. uint64_t *keys, dm_block_t *new_root);
  121. /*
  122. * Removes a _contiguous_ run of values starting from 'keys' and not
  123. * reaching keys2 (where keys2 is keys with the final key replaced with
  124. * 'end_key'). 'end_key' is the one-past-the-end value. 'keys' may be
  125. * altered.
  126. */
  127. int dm_btree_remove_leaves(struct dm_btree_info *info, dm_block_t root,
  128. uint64_t *keys, uint64_t end_key,
  129. dm_block_t *new_root, unsigned *nr_removed);
  130. /*
  131. * Returns < 0 on failure. Otherwise the number of key entries that have
  132. * been filled out. Remember trees can have zero entries, and as such have
  133. * no lowest key.
  134. */
  135. int dm_btree_find_lowest_key(struct dm_btree_info *info, dm_block_t root,
  136. uint64_t *result_keys);
  137. /*
  138. * Returns < 0 on failure. Otherwise the number of key entries that have
  139. * been filled out. Remember trees can have zero entries, and as such have
  140. * no highest key.
  141. */
  142. int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root,
  143. uint64_t *result_keys);
  144. /*
  145. * Iterate through the a btree, calling fn() on each entry.
  146. * It only works for single level trees and is internally recursive, so
  147. * monitor stack usage carefully.
  148. */
  149. int dm_btree_walk(struct dm_btree_info *info, dm_block_t root,
  150. int (*fn)(void *context, uint64_t *keys, void *leaf),
  151. void *context);
  152. /*----------------------------------------------------------------*/
  153. /*
  154. * Cursor API. This does not follow the rolling lock convention. Since we
  155. * know the order that values are required we can issue prefetches to speed
  156. * up iteration. Use on a single level btree only.
  157. */
  158. #define DM_BTREE_CURSOR_MAX_DEPTH 16
  159. struct cursor_node {
  160. struct dm_block *b;
  161. unsigned index;
  162. };
  163. struct dm_btree_cursor {
  164. struct dm_btree_info *info;
  165. dm_block_t root;
  166. bool prefetch_leaves;
  167. unsigned depth;
  168. struct cursor_node nodes[DM_BTREE_CURSOR_MAX_DEPTH];
  169. };
  170. /*
  171. * Creates a fresh cursor. If prefetch_leaves is set then it is assumed
  172. * the btree contains block indexes that will be prefetched. The cursor is
  173. * quite large, so you probably don't want to put it on the stack.
  174. */
  175. int dm_btree_cursor_begin(struct dm_btree_info *info, dm_block_t root,
  176. bool prefetch_leaves, struct dm_btree_cursor *c);
  177. void dm_btree_cursor_end(struct dm_btree_cursor *c);
  178. int dm_btree_cursor_next(struct dm_btree_cursor *c);
  179. int dm_btree_cursor_skip(struct dm_btree_cursor *c, uint32_t count);
  180. int dm_btree_cursor_get_value(struct dm_btree_cursor *c, uint64_t *key, void *value_le);
  181. #endif /* _LINUX_DM_BTREE_H */