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