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 8 #include "dm-bitset.h" 9 #include "dm-transaction-manager.h" 10 11 #include <linux/export.h> 12 #include <linux/device-mapper.h> 13 14 #define DM_MSG_PREFIX "bitset" 15 #define BITS_PER_ARRAY_ENTRY 64 16 17 /*----------------------------------------------------------------*/ 18 19 static struct dm_btree_value_type bitset_bvt = { 20 .context = NULL, 21 .size = sizeof(__le64), 22 .inc = NULL, 23 .dec = NULL, 24 .equal = NULL, 25 }; 26 27 /*----------------------------------------------------------------*/ 28 29 void dm_disk_bitset_init(struct dm_transaction_manager *tm, 30 struct dm_disk_bitset *info) 31 { 32 dm_array_info_init(&info->array_info, tm, &bitset_bvt); 33 info->current_index_set = false; 34 } 35 EXPORT_SYMBOL_GPL(dm_disk_bitset_init); 36 37 int dm_bitset_empty(struct dm_disk_bitset *info, dm_block_t *root) 38 { 39 return dm_array_empty(&info->array_info, root); 40 } 41 EXPORT_SYMBOL_GPL(dm_bitset_empty); 42 43 struct packer_context { 44 bit_value_fn fn; 45 unsigned nr_bits; 46 void *context; 47 }; 48 49 static int pack_bits(uint32_t index, void *value, void *context) 50 { 51 int r; 52 struct packer_context *p = context; 53 unsigned bit, nr = min(64u, p->nr_bits - (index * 64)); 54 uint64_t word = 0; 55 bool bv; 56 57 for (bit = 0; bit < nr; bit++) { 58 r = p->fn(index * 64 + bit, &bv, p->context); 59 if (r) 60 return r; 61 62 if (bv) 63 set_bit(bit, (unsigned long *) &word); 64 else 65 clear_bit(bit, (unsigned long *) &word); 66 } 67 68 *((__le64 *) value) = cpu_to_le64(word); 69 70 return 0; 71 } 72 73 int dm_bitset_new(struct dm_disk_bitset *info, dm_block_t *root, 74 uint32_t size, bit_value_fn fn, void *context) 75 { 76 struct packer_context p; 77 p.fn = fn; 78 p.nr_bits = size; 79 p.context = context; 80 81 return dm_array_new(&info->array_info, root, dm_div_up(size, 64), pack_bits, &p); 82 } 83 EXPORT_SYMBOL_GPL(dm_bitset_new); 84 85 int dm_bitset_resize(struct dm_disk_bitset *info, dm_block_t root, 86 uint32_t old_nr_entries, uint32_t new_nr_entries, 87 bool default_value, dm_block_t *new_root) 88 { 89 uint32_t old_blocks = dm_div_up(old_nr_entries, BITS_PER_ARRAY_ENTRY); 90 uint32_t new_blocks = dm_div_up(new_nr_entries, BITS_PER_ARRAY_ENTRY); 91 __le64 value = default_value ? cpu_to_le64(~0) : cpu_to_le64(0); 92 93 __dm_bless_for_disk(&value); 94 return dm_array_resize(&info->array_info, root, old_blocks, new_blocks, 95 &value, new_root); 96 } 97 EXPORT_SYMBOL_GPL(dm_bitset_resize); 98 99 int dm_bitset_del(struct dm_disk_bitset *info, dm_block_t root) 100 { 101 return dm_array_del(&info->array_info, root); 102 } 103 EXPORT_SYMBOL_GPL(dm_bitset_del); 104 105 int dm_bitset_flush(struct dm_disk_bitset *info, dm_block_t root, 106 dm_block_t *new_root) 107 { 108 int r; 109 __le64 value; 110 111 if (!info->current_index_set || !info->dirty) 112 return 0; 113 114 value = cpu_to_le64(info->current_bits); 115 116 __dm_bless_for_disk(&value); 117 r = dm_array_set_value(&info->array_info, root, info->current_index, 118 &value, new_root); 119 if (r) 120 return r; 121 122 info->current_index_set = false; 123 info->dirty = false; 124 125 return 0; 126 } 127 EXPORT_SYMBOL_GPL(dm_bitset_flush); 128 129 static int read_bits(struct dm_disk_bitset *info, dm_block_t root, 130 uint32_t array_index) 131 { 132 int r; 133 __le64 value; 134 135 r = dm_array_get_value(&info->array_info, root, array_index, &value); 136 if (r) 137 return r; 138 139 info->current_bits = le64_to_cpu(value); 140 info->current_index_set = true; 141 info->current_index = array_index; 142 info->dirty = false; 143 144 return 0; 145 } 146 147 static int get_array_entry(struct dm_disk_bitset *info, dm_block_t root, 148 uint32_t index, dm_block_t *new_root) 149 { 150 int r; 151 unsigned array_index = index / BITS_PER_ARRAY_ENTRY; 152 153 if (info->current_index_set) { 154 if (info->current_index == array_index) 155 return 0; 156 157 r = dm_bitset_flush(info, root, new_root); 158 if (r) 159 return r; 160 } 161 162 return read_bits(info, root, array_index); 163 } 164 165 int dm_bitset_set_bit(struct dm_disk_bitset *info, dm_block_t root, 166 uint32_t index, dm_block_t *new_root) 167 { 168 int r; 169 unsigned b = index % BITS_PER_ARRAY_ENTRY; 170 171 r = get_array_entry(info, root, index, new_root); 172 if (r) 173 return r; 174 175 set_bit(b, (unsigned long *) &info->current_bits); 176 info->dirty = true; 177 178 return 0; 179 } 180 EXPORT_SYMBOL_GPL(dm_bitset_set_bit); 181 182 int dm_bitset_clear_bit(struct dm_disk_bitset *info, dm_block_t root, 183 uint32_t index, dm_block_t *new_root) 184 { 185 int r; 186 unsigned b = index % BITS_PER_ARRAY_ENTRY; 187 188 r = get_array_entry(info, root, index, new_root); 189 if (r) 190 return r; 191 192 clear_bit(b, (unsigned long *) &info->current_bits); 193 info->dirty = true; 194 195 return 0; 196 } 197 EXPORT_SYMBOL_GPL(dm_bitset_clear_bit); 198 199 int dm_bitset_test_bit(struct dm_disk_bitset *info, dm_block_t root, 200 uint32_t index, dm_block_t *new_root, bool *result) 201 { 202 int r; 203 unsigned b = index % BITS_PER_ARRAY_ENTRY; 204 205 r = get_array_entry(info, root, index, new_root); 206 if (r) 207 return r; 208 209 *result = test_bit(b, (unsigned long *) &info->current_bits); 210 return 0; 211 } 212 EXPORT_SYMBOL_GPL(dm_bitset_test_bit); 213 214 static int cursor_next_array_entry(struct dm_bitset_cursor *c) 215 { 216 int r; 217 __le64 *value; 218 219 r = dm_array_cursor_next(&c->cursor); 220 if (r) 221 return r; 222 223 dm_array_cursor_get_value(&c->cursor, (void **) &value); 224 c->array_index++; 225 c->bit_index = 0; 226 c->current_bits = le64_to_cpu(*value); 227 return 0; 228 } 229 230 int dm_bitset_cursor_begin(struct dm_disk_bitset *info, 231 dm_block_t root, uint32_t nr_entries, 232 struct dm_bitset_cursor *c) 233 { 234 int r; 235 __le64 *value; 236 237 if (!nr_entries) 238 return -ENODATA; 239 240 c->info = info; 241 c->entries_remaining = nr_entries; 242 243 r = dm_array_cursor_begin(&info->array_info, root, &c->cursor); 244 if (r) 245 return r; 246 247 dm_array_cursor_get_value(&c->cursor, (void **) &value); 248 c->array_index = 0; 249 c->bit_index = 0; 250 c->current_bits = le64_to_cpu(*value); 251 252 return r; 253 } 254 EXPORT_SYMBOL_GPL(dm_bitset_cursor_begin); 255 256 void dm_bitset_cursor_end(struct dm_bitset_cursor *c) 257 { 258 return dm_array_cursor_end(&c->cursor); 259 } 260 EXPORT_SYMBOL_GPL(dm_bitset_cursor_end); 261 262 int dm_bitset_cursor_next(struct dm_bitset_cursor *c) 263 { 264 int r = 0; 265 266 if (!c->entries_remaining) 267 return -ENODATA; 268 269 c->entries_remaining--; 270 if (++c->bit_index > 63) 271 r = cursor_next_array_entry(c); 272 273 return r; 274 } 275 EXPORT_SYMBOL_GPL(dm_bitset_cursor_next); 276 277 int dm_bitset_cursor_skip(struct dm_bitset_cursor *c, uint32_t count) 278 { 279 int r; 280 __le64 *value; 281 uint32_t nr_array_skip; 282 uint32_t remaining_in_word = 64 - c->bit_index; 283 284 if (c->entries_remaining < count) 285 return -ENODATA; 286 287 if (count < remaining_in_word) { 288 c->bit_index += count; 289 c->entries_remaining -= count; 290 return 0; 291 292 } else { 293 c->entries_remaining -= remaining_in_word; 294 count -= remaining_in_word; 295 } 296 297 nr_array_skip = (count / 64) + 1; 298 r = dm_array_cursor_skip(&c->cursor, nr_array_skip); 299 if (r) 300 return r; 301 302 dm_array_cursor_get_value(&c->cursor, (void **) &value); 303 c->entries_remaining -= count; 304 c->array_index += nr_array_skip; 305 c->bit_index = count & 63; 306 c->current_bits = le64_to_cpu(*value); 307 308 return 0; 309 } 310 EXPORT_SYMBOL_GPL(dm_bitset_cursor_skip); 311 312 bool dm_bitset_cursor_get_value(struct dm_bitset_cursor *c) 313 { 314 return test_bit(c->bit_index, (unsigned long *) &c->current_bits); 315 } 316 EXPORT_SYMBOL_GPL(dm_bitset_cursor_get_value); 317 318 /*----------------------------------------------------------------*/ 319