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