drivers/md/persistent-data/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  */
  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 */