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