Loading...
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 */
68struct 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 */
82void 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 */
92int 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 */
109int 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 */
129typedef int (*value_fn)(uint32_t index, void *value_le, void *context);
130int 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 */
137int 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 */
149int 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 */
167int 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 */
179int 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 */
195struct 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
204int dm_array_cursor_begin(struct dm_array_info *info,
205 dm_block_t root, struct dm_array_cursor *c);
206void dm_array_cursor_end(struct dm_array_cursor *c);
207
208uint32_t dm_array_cursor_index(struct dm_array_cursor *c);
209int dm_array_cursor_next(struct dm_array_cursor *c);
210int 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 */
215void dm_array_cursor_get_value(struct dm_array_cursor *c, void **value_le);
216
217/*----------------------------------------------------------------*/
218
219#endif /* _LINUX_DM_ARRAY_H */
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 */
69struct 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 */
83void 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 */
93int 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 */
110int 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 */
130typedef int (*value_fn)(uint32_t index, void *value_le, void *context);
131int 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 */
138int 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 */
150int 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 */
168int 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 */
180int 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 */
196struct 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
205int dm_array_cursor_begin(struct dm_array_info *info,
206 dm_block_t root, struct dm_array_cursor *c);
207void dm_array_cursor_end(struct dm_array_cursor *c);
208
209uint32_t dm_array_cursor_index(struct dm_array_cursor *c);
210int dm_array_cursor_next(struct dm_array_cursor *c);
211int 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 */
216void dm_array_cursor_get_value(struct dm_array_cursor *c, void **value_le);
217
218/*----------------------------------------------------------------*/
219
220#endif /* _LINUX_DM_ARRAY_H */