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