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_BITSET_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   7) #define _LINUX_DM_BITSET_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   8) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   9) #include "dm-array.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)  * This bitset type is a thin wrapper round a dm_array of 64bit words.  It
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  15)  * uses a tiny, one word cache to reduce the number of array lookups and so
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  16)  * increase performance.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  17)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  18)  * Like the dm-array that it's based on, the caller needs to keep track of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  19)  * the size of the bitset separately.  The underlying dm-array implicitly
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  20)  * knows how many words it's storing and will return -ENODATA if you try
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  21)  * and access an out of bounds word.  However, an out of bounds bit in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  22)  * final word will _not_ be detected, you have been warned.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  23)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  24)  * Bits are indexed from zero.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  25) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  26)  * Typical use:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  27)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  28)  * a) Initialise a dm_disk_bitset structure with dm_disk_bitset_init().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  29)  *    This describes the bitset and includes the cache.  It's not called it
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  30)  *    dm_bitset_info in line with other data structures because it does
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  31)  *    include instance data.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  32)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  33)  * 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  34)  *    disk that holds a particular instance of an bitset.  You may have a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  35)  *    pre existing root in your metadata that you wish to use, or you may
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  36)  *    want to create a brand new, empty bitset with dm_bitset_empty().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  37)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  38)  * Like the other data structures in this library, dm_bitset objects are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  39)  * immutable between transactions.  Update functions will return you the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  40)  * root for a _new_ array.  If you've incremented the old root, via
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  41)  * dm_tm_inc(), before calling the update function you may continue to use
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  42)  * it in parallel with the new root.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  43)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  44)  * Even read operations may trigger the cache to be flushed and as such
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  45)  * return a root for a new, updated bitset.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  46)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  47)  * c) resize a bitset with dm_bitset_resize().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  48)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  49)  * d) Set a bit with dm_bitset_set_bit().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  50)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  51)  * e) Clear a bit with dm_bitset_clear_bit().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  52)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  53)  * f) Test a bit with dm_bitset_test_bit().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  54)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  55)  * g) Flush all updates from the cache with dm_bitset_flush().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  56)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  57)  * h) Destroy the bitset with dm_bitset_del().  This tells the transaction
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  58)  *    manager that you're no longer using this data structure so it can
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  59)  *    recycle it's blocks.  (dm_bitset_dec() would be a better name for it,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  60)  *    but del is in keeping with dm_btree_del()).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  61)  */
^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)  * Opaque object.  Unlike dm_array_info, you should have one of these per
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  65)  * bitset.  Initialise with dm_disk_bitset_init().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  66)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  67) struct dm_disk_bitset {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  68) 	struct dm_array_info array_info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  69) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  70) 	uint32_t current_index;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  71) 	uint64_t current_bits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  72) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  73) 	bool current_index_set:1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  74) 	bool dirty:1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  75) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  76) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  77) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  78)  * Sets up a dm_disk_bitset structure.  You don't need to do anything with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  79)  * this structure when you finish using it.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  80)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  81)  * tm - the transaction manager that should supervise this structure
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  82)  * info - the structure being initialised
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  83)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  84) void dm_disk_bitset_init(struct dm_transaction_manager *tm,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  85) 			 struct dm_disk_bitset *info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  86) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  87) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  88)  * Create an empty, zero length bitset.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  89)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  90)  * info - describes the bitset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  91)  * new_root - on success, points to the new root block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  92)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  93) int dm_bitset_empty(struct dm_disk_bitset *info, dm_block_t *new_root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  94) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  95) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  96)  * Creates a new bitset populated with values provided by a callback
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  97)  * function.  This is more efficient than creating an empty bitset,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  98)  * resizing, and then setting values since that process incurs a lot of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  99)  * copying.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101)  * info - describes the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102)  * root - the root block of the array on disk
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103)  * size - the number of entries in the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104)  * fn - the callback
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105)  * context - passed to the callback
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) typedef int (*bit_value_fn)(uint32_t index, bool *value, void *context);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) int dm_bitset_new(struct dm_disk_bitset *info, dm_block_t *root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) 		  uint32_t size, bit_value_fn fn, void *context);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112)  * Resize the bitset.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114)  * info - describes the bitset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115)  * old_root - the root block of the array on disk
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116)  * old_nr_entries - the number of bits in the old bitset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117)  * new_nr_entries - the number of bits you want in the new bitset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118)  * default_value - the value for any new bits
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119)  * new_root - on success, points to the new root block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) int dm_bitset_resize(struct dm_disk_bitset *info, dm_block_t old_root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) 		     uint32_t old_nr_entries, uint32_t new_nr_entries,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) 		     bool default_value, dm_block_t *new_root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126)  * Frees the bitset.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) int dm_bitset_del(struct dm_disk_bitset *info, dm_block_t root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131)  * Set a bit.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133)  * info - describes the bitset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134)  * root - the root block of the bitset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135)  * index - the bit index
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136)  * new_root - on success, points to the new root block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138)  * -ENODATA will be returned if the index is out of bounds.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) int dm_bitset_set_bit(struct dm_disk_bitset *info, dm_block_t root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) 		      uint32_t index, dm_block_t *new_root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144)  * Clears a bit.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146)  * info - describes the bitset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147)  * root - the root block of the bitset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148)  * index - the bit index
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149)  * new_root - on success, points to the new root block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151)  * -ENODATA will be returned if the index is out of bounds.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) int dm_bitset_clear_bit(struct dm_disk_bitset *info, dm_block_t root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) 			uint32_t index, dm_block_t *new_root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157)  * Tests a bit.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159)  * info - describes the bitset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160)  * root - the root block of the bitset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161)  * index - the bit index
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162)  * new_root - on success, points to the new root block (cached values may have been written)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163)  * result - the bit value you're after
^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_bitset_test_bit(struct dm_disk_bitset *info, dm_block_t root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) 		       uint32_t index, dm_block_t *new_root, bool *result);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171)  * Flush any cached changes to disk.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173)  * info - describes the bitset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174)  * root - the root block of the bitset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175)  * new_root - on success, points to the new root block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) int dm_bitset_flush(struct dm_disk_bitset *info, dm_block_t root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) 		    dm_block_t *new_root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) struct dm_bitset_cursor {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) 	struct dm_disk_bitset *info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) 	struct dm_array_cursor cursor;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) 	uint32_t entries_remaining;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) 	uint32_t array_index;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) 	uint32_t bit_index;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) 	uint64_t current_bits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191)  * Make sure you've flush any dm_disk_bitset and updated the root before
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192)  * using this.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) int dm_bitset_cursor_begin(struct dm_disk_bitset *info,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) 			   dm_block_t root, uint32_t nr_entries,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) 			   struct dm_bitset_cursor *c);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) void dm_bitset_cursor_end(struct dm_bitset_cursor *c);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) int dm_bitset_cursor_next(struct dm_bitset_cursor *c);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) int dm_bitset_cursor_skip(struct dm_bitset_cursor *c, uint32_t count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) bool dm_bitset_cursor_get_value(struct dm_bitset_cursor *c);
^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) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) #endif /* _LINUX_DM_BITSET_H */