| 1 |
|
| 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
|