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