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