207 lines · c
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_H8#define _LINUX_DM_BITSET_H9 10#include "dm-array.h"11 12/*----------------------------------------------------------------*/13 14/*15 * This bitset type is a thin wrapper round a dm_array of 64bit words. It16 * uses a tiny, one word cache to reduce the number of array lookups and so17 * increase performance.18 *19 * Like the dm-array that it's based on, the caller needs to keep track of20 * the size of the bitset separately. The underlying dm-array implicitly21 * knows how many words it's storing and will return -ENODATA if you try22 * and access an out of bounds word. However, an out of bounds bit in the23 * 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 it31 * dm_bitset_info in line with other data structures because it does32 * include instance data.33 *34 * b) Get yourself a root. The root is the index of a block of data on the35 * disk that holds a particular instance of an bitset. You may have a36 * pre existing root in your metadata that you wish to use, or you may37 * 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 are40 * immutable between transactions. Update functions will return you the41 * root for a _new_ array. If you've incremented the old root, via42 * dm_tm_inc(), before calling the update function you may continue to use43 * it in parallel with the new root.44 *45 * Even read operations may trigger the cache to be flushed and as such46 * 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 transaction59 * manager that you're no longer using this data structure so it can60 * 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 per66 * bitset. Initialise with dm_disk_bitset_init().67 */68struct 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 with80 * this structure when you finish using it.81 *82 * tm - the transaction manager that should supervise this structure83 * info - the structure being initialised84 */85void 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 bitset92 * new_root - on success, points to the new root block93 */94int 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 callback98 * function. This is more efficient than creating an empty bitset,99 * resizing, and then setting values since that process incurs a lot of100 * copying.101 *102 * info - describes the array103 * root - the root block of the array on disk104 * size - the number of entries in the array105 * fn - the callback106 * context - passed to the callback107 */108typedef int (*bit_value_fn)(uint32_t index, bool *value, void *context);109int 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 bitset116 * old_root - the root block of the array on disk117 * old_nr_entries - the number of bits in the old bitset118 * new_nr_entries - the number of bits you want in the new bitset119 * default_value - the value for any new bits120 * new_root - on success, points to the new root block121 */122int 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 */129int dm_bitset_del(struct dm_disk_bitset *info, dm_block_t root);130 131/*132 * Set a bit.133 *134 * info - describes the bitset135 * root - the root block of the bitset136 * index - the bit index137 * new_root - on success, points to the new root block138 *139 * -ENODATA will be returned if the index is out of bounds.140 */141int 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 bitset148 * root - the root block of the bitset149 * index - the bit index150 * new_root - on success, points to the new root block151 *152 * -ENODATA will be returned if the index is out of bounds.153 */154int 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 bitset161 * root - the root block of the bitset162 * index - the bit index163 * new_root - on success, points to the new root block (cached values may have been written)164 * result - the bit value you're after165 *166 * -ENODATA will be returned if the index is out of bounds.167 */168int 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 bitset175 * root - the root block of the bitset176 * new_root - on success, points to the new root block177 */178int dm_bitset_flush(struct dm_disk_bitset *info, dm_block_t root,179 dm_block_t *new_root);180 181struct 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 before193 * using this.194 */195int dm_bitset_cursor_begin(struct dm_disk_bitset *info,196 dm_block_t root, uint32_t nr_entries,197 struct dm_bitset_cursor *c);198void dm_bitset_cursor_end(struct dm_bitset_cursor *c);199 200int dm_bitset_cursor_next(struct dm_bitset_cursor *c);201int dm_bitset_cursor_skip(struct dm_bitset_cursor *c, uint32_t count);202bool dm_bitset_cursor_get_value(struct dm_bitset_cursor *c);203 204/*----------------------------------------------------------------*/205 206#endif /* _LINUX_DM_BITSET_H */207