Orange Pi5 kernel

^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   1) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   2)  * Copyright (C) 2012 Red Hat, Inc.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   3)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   4)  * This file is released under the GPL.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   5)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   6) #ifndef _LINUX_DM_ARRAY_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   7) #define _LINUX_DM_ARRAY_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   8) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   9) #include "dm-btree.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  10) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  11) /*----------------------------------------------------------------*/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  12) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  13) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  14)  * The dm-array is a persistent version of an array.  It packs the data
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  15)  * more efficiently than a btree which will result in less disk space use,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  16)  * and a performance boost.  The element get and set operations are still
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  17)  * O(ln(n)), but with a much smaller constant.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  18)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  19)  * The value type structure is reused from the btree type to support proper
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  20)  * reference counting of values.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  21)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  22)  * The arrays implicitly know their length, and bounds are checked for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  23)  * lookups and updated.  It doesn't store this in an accessible place
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  24)  * because it would waste a whole metadata block.  Make sure you store the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  25)  * size along with the array root in your encompassing data.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  26)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  27)  * Array entries are indexed via an unsigned integer starting from zero.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  28)  * Arrays are not sparse; if you resize an array to have 'n' entries then
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  29)  * 'n - 1' will be the last valid index.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  30)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  31)  * Typical use:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  32)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  33)  * a) initialise a dm_array_info structure.  This describes the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  34)  *    values and ties it into a specific transaction manager.  It holds no
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  35)  *    instance data; the same info can be used for many similar arrays if
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  36)  *    you wish.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  37)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  38)  * b) Get yourself a root.  The root is the index of a block of data on the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  39)  *    disk that holds a particular instance of an array.  You may have a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  40)  *    pre existing root in your metadata that you wish to use, or you may
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  41)  *    want to create a brand new, empty array with dm_array_empty().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  42)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  43)  * Like the other data structures in this library, dm_array objects are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  44)  * immutable between transactions.  Update functions will return you the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  45)  * root for a _new_ array.  If you've incremented the old root, via
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  46)  * dm_tm_inc(), before calling the update function you may continue to use
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  47)  * it in parallel with the new root.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  48)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  49)  * c) resize an array with dm_array_resize().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  50)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  51)  * d) Get a value from the array with dm_array_get_value().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  52)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  53)  * e) Set a value in the array with dm_array_set_value().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  54)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  55)  * f) Walk an array of values in index order with dm_array_walk().  More
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  56)  *    efficient than making many calls to dm_array_get_value().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  57)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  58)  * g) Destroy the array with dm_array_del().  This tells the transaction
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  59)  *    manager that you're no longer using this data structure so it can
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  60)  *    recycle it's blocks.  (dm_array_dec() would be a better name for it,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  61)  *    but del is in keeping with dm_btree_del()).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  62)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  63) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  64) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  65)  * Describes an array.  Don't initialise this structure yourself, use the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  66)  * init function below.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  67)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  68) struct dm_array_info {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  69) 	struct dm_transaction_manager *tm;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  70) 	struct dm_btree_value_type value_type;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  71) 	struct dm_btree_info btree_info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  72) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  73) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  74) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  75)  * Sets up a dm_array_info structure.  You don't need to do anything with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  76)  * this structure when you finish using it.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  77)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  78)  * info - the structure being filled in.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  79)  * tm   - the transaction manager that should supervise this structure.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  80)  * vt   - describes the leaf values.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  81)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  82) void dm_array_info_init(struct dm_array_info *info,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  83) 			struct dm_transaction_manager *tm,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  84) 			struct dm_btree_value_type *vt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  85) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  86) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  87)  * Create an empty, zero length array.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  88)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  89)  * info - describes the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  90)  * root - on success this will be filled out with the root block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  91)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  92) int dm_array_empty(struct dm_array_info *info, dm_block_t *root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  93) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  94) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  95)  * Resizes the array.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  96)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  97)  * info - describes the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  98)  * root - the root block of the array on disk
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  99)  * old_size - the caller is responsible for remembering the size of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100)  *            the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101)  * new_size - can be bigger or smaller than old_size
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102)  * value - if we're growing the array the new entries will have this value
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103)  * new_root - on success, points to the new root block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105)  * If growing the inc function for 'value' will be called the appropriate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106)  * number of times.  So if the caller is holding a reference they may want
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107)  * to drop it.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) int dm_array_resize(struct dm_array_info *info, dm_block_t root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) 		    uint32_t old_size, uint32_t new_size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) 		    const void *value, dm_block_t *new_root)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) 	__dm_written_to_disk(value);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115)  * Creates a new array populated with values provided by a callback
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116)  * function.  This is more efficient than creating an empty array,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117)  * resizing, and then setting values since that process incurs a lot of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118)  * copying.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120)  * Assumes 32bit values for now since it's only used by the cache hint
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121)  * array.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123)  * info - describes the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124)  * root - the root block of the array on disk
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125)  * size - the number of entries in the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126)  * fn - the callback
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127)  * context - passed to the callback
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) typedef int (*value_fn)(uint32_t index, void *value_le, void *context);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) int dm_array_new(struct dm_array_info *info, dm_block_t *root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) 		 uint32_t size, value_fn fn, void *context);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134)  * Frees a whole array.  The value_type's decrement operation will be called
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135)  * for all values in the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) int dm_array_del(struct dm_array_info *info, dm_block_t root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140)  * Lookup a value in the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142)  * info - describes the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143)  * root - root block of the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144)  * index - array index
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145)  * value - the value to be read.  Will be in on-disk format of course.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147)  * -ENODATA will be returned if the index is out of bounds.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) int dm_array_get_value(struct dm_array_info *info, dm_block_t root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) 		       uint32_t index, void *value);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153)  * Set an entry in the array.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155)  * info - describes the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156)  * root - root block of the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157)  * index - array index
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158)  * value - value to be written to disk.  Make sure you confirm the value is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159)  *         in on-disk format with__dm_bless_for_disk() before calling.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160)  * new_root - the new root block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162)  * The old value being overwritten will be decremented, the new value
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163)  * incremented.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165)  * -ENODATA will be returned if the index is out of bounds.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) int dm_array_set_value(struct dm_array_info *info, dm_block_t root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) 		       uint32_t index, const void *value, dm_block_t *new_root)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) 	__dm_written_to_disk(value);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172)  * Walk through all the entries in an array.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174)  * info - describes the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175)  * root - root block of the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176)  * fn - called back for every element
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177)  * context - passed to the callback
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) int dm_array_walk(struct dm_array_info *info, dm_block_t root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) 		  int (*fn)(void *context, uint64_t key, void *leaf),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) 		  void *context);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) /*----------------------------------------------------------------*/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186)  * Cursor api.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188)  * This lets you iterate through all the entries in an array efficiently
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189)  * (it will preload metadata).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191)  * I'm using a cursor, rather than a walk function with a callback because
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192)  * the cache target needs to iterate both the mapping and hint arrays in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193)  * unison.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) struct dm_array_cursor {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) 	struct dm_array_info *info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) 	struct dm_btree_cursor cursor;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) 	struct dm_block *block;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) 	struct array_block *ab;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) 	unsigned index;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) int dm_array_cursor_begin(struct dm_array_info *info,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) 			  dm_block_t root, struct dm_array_cursor *c);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) void dm_array_cursor_end(struct dm_array_cursor *c);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) uint32_t dm_array_cursor_index(struct dm_array_cursor *c);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) int dm_array_cursor_next(struct dm_array_cursor *c);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) int dm_array_cursor_skip(struct dm_array_cursor *c, uint32_t count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213)  * value_le is only valid while the cursor points at the current value.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) void dm_array_cursor_get_value(struct dm_array_cursor *c, void **value_le);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) /*----------------------------------------------------------------*/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) #endif	/* _LINUX_DM_ARRAY_H */