dm-array.h 7.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219
  1. /*
  2. * Copyright (C) 2012 Red Hat, Inc.
  3. *
  4. * This file is released under the GPL.
  5. */
  6. #ifndef _LINUX_DM_ARRAY_H
  7. #define _LINUX_DM_ARRAY_H
  8. #include "dm-btree.h"
  9. /*----------------------------------------------------------------*/
  10. /*
  11. * The dm-array is a persistent version of an array. It packs the data
  12. * more efficiently than a btree which will result in less disk space use,
  13. * and a performance boost. The element get and set operations are still
  14. * O(ln(n)), but with a much smaller constant.
  15. *
  16. * The value type structure is reused from the btree type to support proper
  17. * reference counting of values.
  18. *
  19. * The arrays implicitly know their length, and bounds are checked for
  20. * lookups and updated. It doesn't store this in an accessible place
  21. * because it would waste a whole metadata block. Make sure you store the
  22. * size along with the array root in your encompassing data.
  23. *
  24. * Array entries are indexed via an unsigned integer starting from zero.
  25. * Arrays are not sparse; if you resize an array to have 'n' entries then
  26. * 'n - 1' will be the last valid index.
  27. *
  28. * Typical use:
  29. *
  30. * a) initialise a dm_array_info structure. This describes the array
  31. * values and ties it into a specific transaction manager. It holds no
  32. * instance data; the same info can be used for many similar arrays if
  33. * you wish.
  34. *
  35. * b) Get yourself a root. The root is the index of a block of data on the
  36. * disk that holds a particular instance of an array. You may have a
  37. * pre existing root in your metadata that you wish to use, or you may
  38. * want to create a brand new, empty array with dm_array_empty().
  39. *
  40. * Like the other data structures in this library, dm_array objects are
  41. * immutable between transactions. Update functions will return you the
  42. * root for a _new_ array. If you've incremented the old root, via
  43. * dm_tm_inc(), before calling the update function you may continue to use
  44. * it in parallel with the new root.
  45. *
  46. * c) resize an array with dm_array_resize().
  47. *
  48. * d) Get a value from the array with dm_array_get_value().
  49. *
  50. * e) Set a value in the array with dm_array_set_value().
  51. *
  52. * f) Walk an array of values in index order with dm_array_walk(). More
  53. * efficient than making many calls to dm_array_get_value().
  54. *
  55. * g) Destroy the array with dm_array_del(). This tells the transaction
  56. * manager that you're no longer using this data structure so it can
  57. * recycle it's blocks. (dm_array_dec() would be a better name for it,
  58. * but del is in keeping with dm_btree_del()).
  59. */
  60. /*
  61. * Describes an array. Don't initialise this structure yourself, use the
  62. * init function below.
  63. */
  64. struct dm_array_info {
  65. struct dm_transaction_manager *tm;
  66. struct dm_btree_value_type value_type;
  67. struct dm_btree_info btree_info;
  68. };
  69. /*
  70. * Sets up a dm_array_info structure. You don't need to do anything with
  71. * this structure when you finish using it.
  72. *
  73. * info - the structure being filled in.
  74. * tm - the transaction manager that should supervise this structure.
  75. * vt - describes the leaf values.
  76. */
  77. void dm_array_info_init(struct dm_array_info *info,
  78. struct dm_transaction_manager *tm,
  79. struct dm_btree_value_type *vt);
  80. /*
  81. * Create an empty, zero length array.
  82. *
  83. * info - describes the array
  84. * root - on success this will be filled out with the root block
  85. */
  86. int dm_array_empty(struct dm_array_info *info, dm_block_t *root);
  87. /*
  88. * Resizes the array.
  89. *
  90. * info - describes the array
  91. * root - the root block of the array on disk
  92. * old_size - the caller is responsible for remembering the size of
  93. * the array
  94. * new_size - can be bigger or smaller than old_size
  95. * value - if we're growing the array the new entries will have this value
  96. * new_root - on success, points to the new root block
  97. *
  98. * If growing the inc function for 'value' will be called the appropriate
  99. * number of times. So if the caller is holding a reference they may want
  100. * to drop it.
  101. */
  102. int dm_array_resize(struct dm_array_info *info, dm_block_t root,
  103. uint32_t old_size, uint32_t new_size,
  104. const void *value, dm_block_t *new_root)
  105. __dm_written_to_disk(value);
  106. /*
  107. * Creates a new array populated with values provided by a callback
  108. * function. This is more efficient than creating an empty array,
  109. * resizing, and then setting values since that process incurs a lot of
  110. * copying.
  111. *
  112. * Assumes 32bit values for now since it's only used by the cache hint
  113. * array.
  114. *
  115. * info - describes the array
  116. * root - the root block of the array on disk
  117. * size - the number of entries in the array
  118. * fn - the callback
  119. * context - passed to the callback
  120. */
  121. typedef int (*value_fn)(uint32_t index, void *value_le, void *context);
  122. int dm_array_new(struct dm_array_info *info, dm_block_t *root,
  123. uint32_t size, value_fn fn, void *context);
  124. /*
  125. * Frees a whole array. The value_type's decrement operation will be called
  126. * for all values in the array
  127. */
  128. int dm_array_del(struct dm_array_info *info, dm_block_t root);
  129. /*
  130. * Lookup a value in the array
  131. *
  132. * info - describes the array
  133. * root - root block of the array
  134. * index - array index
  135. * value - the value to be read. Will be in on-disk format of course.
  136. *
  137. * -ENODATA will be returned if the index is out of bounds.
  138. */
  139. int dm_array_get_value(struct dm_array_info *info, dm_block_t root,
  140. uint32_t index, void *value);
  141. /*
  142. * Set an entry in the array.
  143. *
  144. * info - describes the array
  145. * root - root block of the array
  146. * index - array index
  147. * value - value to be written to disk. Make sure you confirm the value is
  148. * in on-disk format with__dm_bless_for_disk() before calling.
  149. * new_root - the new root block
  150. *
  151. * The old value being overwritten will be decremented, the new value
  152. * incremented.
  153. *
  154. * -ENODATA will be returned if the index is out of bounds.
  155. */
  156. int dm_array_set_value(struct dm_array_info *info, dm_block_t root,
  157. uint32_t index, const void *value, dm_block_t *new_root)
  158. __dm_written_to_disk(value);
  159. /*
  160. * Walk through all the entries in an array.
  161. *
  162. * info - describes the array
  163. * root - root block of the array
  164. * fn - called back for every element
  165. * context - passed to the callback
  166. */
  167. int dm_array_walk(struct dm_array_info *info, dm_block_t root,
  168. int (*fn)(void *context, uint64_t key, void *leaf),
  169. void *context);
  170. /*----------------------------------------------------------------*/
  171. /*
  172. * Cursor api.
  173. *
  174. * This lets you iterate through all the entries in an array efficiently
  175. * (it will preload metadata).
  176. *
  177. * I'm using a cursor, rather than a walk function with a callback because
  178. * the cache target needs to iterate both the mapping and hint arrays in
  179. * unison.
  180. */
  181. struct dm_array_cursor {
  182. struct dm_array_info *info;
  183. struct dm_btree_cursor cursor;
  184. struct dm_block *block;
  185. struct array_block *ab;
  186. unsigned index;
  187. };
  188. int dm_array_cursor_begin(struct dm_array_info *info,
  189. dm_block_t root, struct dm_array_cursor *c);
  190. void dm_array_cursor_end(struct dm_array_cursor *c);
  191. uint32_t dm_array_cursor_index(struct dm_array_cursor *c);
  192. int dm_array_cursor_next(struct dm_array_cursor *c);
  193. int dm_array_cursor_skip(struct dm_array_cursor *c, uint32_t count);
  194. /*
  195. * value_le is only valid while the cursor points at the current value.
  196. */
  197. void dm_array_cursor_get_value(struct dm_array_cursor *c, void **value_le);
  198. /*----------------------------------------------------------------*/
  199. #endif /* _LINUX_DM_ARRAY_H */