221 lines · c
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_H8#define _LINUX_DM_ARRAY_H9 10#include "dm-btree.h"11 12/*----------------------------------------------------------------*/13 14/*15 * The dm-array is a persistent version of an array. It packs the data16 * 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 still18 * O(ln(n)), but with a much smaller constant.19 *20 * The value type structure is reused from the btree type to support proper21 * reference counting of values.22 *23 * The arrays implicitly know their length, and bounds are checked for24 * lookups and updated. It doesn't store this in an accessible place25 * because it would waste a whole metadata block. Make sure you store the26 * 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 then30 * 'n - 1' will be the last valid index.31 *32 * Typical use:33 *34 * a) initialise a dm_array_info structure. This describes the array35 * values and ties it into a specific transaction manager. It holds no36 * instance data; the same info can be used for many similar arrays if37 * you wish.38 *39 * b) Get yourself a root. The root is the index of a block of data on the40 * disk that holds a particular instance of an array. You may have a41 * pre existing root in your metadata that you wish to use, or you may42 * 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 are45 * immutable between transactions. Update functions will return you the46 * root for a _new_ array. If you've incremented the old root, via47 * dm_tm_inc(), before calling the update function you may continue to use48 * 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(). More57 * efficient than making many calls to dm_array_get_value().58 *59 * g) Destroy the array with dm_array_del(). This tells the transaction60 * manager that you're no longer using this data structure so it can61 * 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 the67 * 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 with77 * 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 array91 * root - on success this will be filled out with the root block92 */93int dm_array_empty(struct dm_array_info *info, dm_block_t *root);94 95/*96 * Resizes the array.97 *98 * info - describes the array99 * root - the root block of the array on disk100 * old_size - the caller is responsible for remembering the size of101 * the array102 * new_size - can be bigger or smaller than old_size103 * value - if we're growing the array the new entries will have this value104 * new_root - on success, points to the new root block105 *106 * If growing the inc function for 'value' will be called the appropriate107 * number of times. So if the caller is holding a reference they may want108 * 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 callback117 * function. This is more efficient than creating an empty array,118 * resizing, and then setting values since that process incurs a lot of119 * copying.120 *121 * Assumes 32bit values for now since it's only used by the cache hint122 * array.123 *124 * info - describes the array125 * root - the root block of the array on disk126 * size - the number of entries in the array127 * fn - the callback128 * context - passed to the callback129 */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 called136 * for all values in the array137 */138int dm_array_del(struct dm_array_info *info, dm_block_t root);139 140/*141 * Lookup a value in the array142 *143 * info - describes the array144 * root - root block of the array145 * index - array index146 * 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 array157 * root - root block of the array158 * index - array index159 * value - value to be written to disk. Make sure you confirm the value is160 * in on-disk format with__dm_bless_for_disk() before calling.161 * new_root - the new root block162 *163 * The old value being overwritten will be decremented, the new value164 * 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 array176 * root - root block of the array177 * fn - called back for every element178 * context - passed to the callback179 */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 efficiently190 * (it will preload metadata).191 *192 * I'm using a cursor, rather than a walk function with a callback because193 * the cache target needs to iterate both the mapping and hint arrays in194 * 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 */221