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 | |