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