kernel/drivers/md/persistent-data/dm-array.h

   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  * Frees a whole array.  The value_type's decrement operation will be called
 116  * for all values in the array
 117  */
 118 int dm_array_del(struct dm_array_info *info, dm_block_t root);
 119
 120 /*
 121  * Lookup a value in the array
 122  *
 123  * info - describes the array
 124  * root - root block of the array
 125  * index - array index
 126  * value - the value to be read.  Will be in on-disk format of course.
 127  *
 128  * -ENODATA will be returned if the index is out of bounds.
 129  */
 130 int dm_array_get_value(struct dm_array_info *info, dm_block_t root,
 131                        uint32_t index, void *value);
 132
 133 /*
 134  * Set an entry in the array.
 135  *
 136  * info - describes the array
 137  * root - root block of the array
 138  * index - array index
 139  * value - value to be written to disk.  Make sure you confirm the value is
 140  *         in on-disk format with__dm_bless_for_disk() before calling.
 141  * new_root - the new root block
 142  *
 143  * The old value being overwritten will be decremented, the new value
 144  * incremented.
 145  *
 146  * -ENODATA will be returned if the index is out of bounds.
 147  */
 148 int dm_array_set_value(struct dm_array_info *info, dm_block_t root,
 149                        uint32_t index, const void *value, dm_block_t *new_root)
 150         __dm_written_to_disk(value);
 151
 152 /*
 153  * Walk through all the entries in an array.
 154  *
 155  * info - describes the array
 156  * root - root block of the array
 157  * fn - called back for every element
 158  * context - passed to the callback
 159  */
 160 int dm_array_walk(struct dm_array_info *info, dm_block_t root,
 161                   int (*fn)(void *context, uint64_t key, void *leaf),
 162                   void *context);
 163
 164 /*----------------------------------------------------------------*/
 165
 166 #endif  /* _LINUX_DM_ARRAY_H */