Back to home page

OSCL-LXR
 
 

     

0001 /*
0002  * Copyright (C) 2012 Red Hat, Inc.
0003  *
0004  * This file is released under the GPL.
0005  */
0006 
0007 #include "dm-bitset.h"
0008 #include "dm-transaction-manager.h"
0009 
0010 #include <linux/export.h>
0011 #include <linux/device-mapper.h>
0012 
0013 #define DM_MSG_PREFIX "bitset"
0014 #define BITS_PER_ARRAY_ENTRY 64
0015 
0016 /*----------------------------------------------------------------*/
0017 
0018 static struct dm_btree_value_type bitset_bvt = {
0019     .context = NULL,
0020     .size = sizeof(__le64),
0021     .inc = NULL,
0022     .dec = NULL,
0023     .equal = NULL,
0024 };
0025 
0026 /*----------------------------------------------------------------*/
0027 
0028 void dm_disk_bitset_init(struct dm_transaction_manager *tm,
0029              struct dm_disk_bitset *info)
0030 {
0031     dm_array_info_init(&info->array_info, tm, &bitset_bvt);
0032     info->current_index_set = false;
0033 }
0034 EXPORT_SYMBOL_GPL(dm_disk_bitset_init);
0035 
0036 int dm_bitset_empty(struct dm_disk_bitset *info, dm_block_t *root)
0037 {
0038     return dm_array_empty(&info->array_info, root);
0039 }
0040 EXPORT_SYMBOL_GPL(dm_bitset_empty);
0041 
0042 struct packer_context {
0043     bit_value_fn fn;
0044     unsigned nr_bits;
0045     void *context;
0046 };
0047 
0048 static int pack_bits(uint32_t index, void *value, void *context)
0049 {
0050     int r;
0051     struct packer_context *p = context;
0052     unsigned bit, nr = min(64u, p->nr_bits - (index * 64));
0053     uint64_t word = 0;
0054     bool bv;
0055 
0056     for (bit = 0; bit < nr; bit++) {
0057         r = p->fn(index * 64 + bit, &bv, p->context);
0058         if (r)
0059             return r;
0060 
0061         if (bv)
0062             set_bit(bit, (unsigned long *) &word);
0063         else
0064             clear_bit(bit, (unsigned long *) &word);
0065     }
0066 
0067     *((__le64 *) value) = cpu_to_le64(word);
0068 
0069     return 0;
0070 }
0071 
0072 int dm_bitset_new(struct dm_disk_bitset *info, dm_block_t *root,
0073           uint32_t size, bit_value_fn fn, void *context)
0074 {
0075     struct packer_context p;
0076     p.fn = fn;
0077     p.nr_bits = size;
0078     p.context = context;
0079 
0080     return dm_array_new(&info->array_info, root, dm_div_up(size, 64), pack_bits, &p);
0081 }
0082 EXPORT_SYMBOL_GPL(dm_bitset_new);
0083 
0084 int dm_bitset_resize(struct dm_disk_bitset *info, dm_block_t root,
0085              uint32_t old_nr_entries, uint32_t new_nr_entries,
0086              bool default_value, dm_block_t *new_root)
0087 {
0088     uint32_t old_blocks = dm_div_up(old_nr_entries, BITS_PER_ARRAY_ENTRY);
0089     uint32_t new_blocks = dm_div_up(new_nr_entries, BITS_PER_ARRAY_ENTRY);
0090     __le64 value = default_value ? cpu_to_le64(~0) : cpu_to_le64(0);
0091 
0092     __dm_bless_for_disk(&value);
0093     return dm_array_resize(&info->array_info, root, old_blocks, new_blocks,
0094                    &value, new_root);
0095 }
0096 EXPORT_SYMBOL_GPL(dm_bitset_resize);
0097 
0098 int dm_bitset_del(struct dm_disk_bitset *info, dm_block_t root)
0099 {
0100     return dm_array_del(&info->array_info, root);
0101 }
0102 EXPORT_SYMBOL_GPL(dm_bitset_del);
0103 
0104 int dm_bitset_flush(struct dm_disk_bitset *info, dm_block_t root,
0105             dm_block_t *new_root)
0106 {
0107     int r;
0108     __le64 value;
0109 
0110     if (!info->current_index_set || !info->dirty)
0111         return 0;
0112 
0113     value = cpu_to_le64(info->current_bits);
0114 
0115     __dm_bless_for_disk(&value);
0116     r = dm_array_set_value(&info->array_info, root, info->current_index,
0117                    &value, new_root);
0118     if (r)
0119         return r;
0120 
0121     info->current_index_set = false;
0122     info->dirty = false;
0123 
0124     return 0;
0125 }
0126 EXPORT_SYMBOL_GPL(dm_bitset_flush);
0127 
0128 static int read_bits(struct dm_disk_bitset *info, dm_block_t root,
0129              uint32_t array_index)
0130 {
0131     int r;
0132     __le64 value;
0133 
0134     r = dm_array_get_value(&info->array_info, root, array_index, &value);
0135     if (r)
0136         return r;
0137 
0138     info->current_bits = le64_to_cpu(value);
0139     info->current_index_set = true;
0140     info->current_index = array_index;
0141     info->dirty = false;
0142 
0143     return 0;
0144 }
0145 
0146 static int get_array_entry(struct dm_disk_bitset *info, dm_block_t root,
0147                uint32_t index, dm_block_t *new_root)
0148 {
0149     int r;
0150     unsigned array_index = index / BITS_PER_ARRAY_ENTRY;
0151 
0152     if (info->current_index_set) {
0153         if (info->current_index == array_index)
0154             return 0;
0155 
0156         r = dm_bitset_flush(info, root, new_root);
0157         if (r)
0158             return r;
0159     }
0160 
0161     return read_bits(info, root, array_index);
0162 }
0163 
0164 int dm_bitset_set_bit(struct dm_disk_bitset *info, dm_block_t root,
0165               uint32_t index, dm_block_t *new_root)
0166 {
0167     int r;
0168     unsigned b = index % BITS_PER_ARRAY_ENTRY;
0169 
0170     r = get_array_entry(info, root, index, new_root);
0171     if (r)
0172         return r;
0173 
0174     set_bit(b, (unsigned long *) &info->current_bits);
0175     info->dirty = true;
0176 
0177     return 0;
0178 }
0179 EXPORT_SYMBOL_GPL(dm_bitset_set_bit);
0180 
0181 int dm_bitset_clear_bit(struct dm_disk_bitset *info, dm_block_t root,
0182             uint32_t index, dm_block_t *new_root)
0183 {
0184     int r;
0185     unsigned b = index % BITS_PER_ARRAY_ENTRY;
0186 
0187     r = get_array_entry(info, root, index, new_root);
0188     if (r)
0189         return r;
0190 
0191     clear_bit(b, (unsigned long *) &info->current_bits);
0192     info->dirty = true;
0193 
0194     return 0;
0195 }
0196 EXPORT_SYMBOL_GPL(dm_bitset_clear_bit);
0197 
0198 int dm_bitset_test_bit(struct dm_disk_bitset *info, dm_block_t root,
0199                uint32_t index, dm_block_t *new_root, bool *result)
0200 {
0201     int r;
0202     unsigned b = index % BITS_PER_ARRAY_ENTRY;
0203 
0204     r = get_array_entry(info, root, index, new_root);
0205     if (r)
0206         return r;
0207 
0208     *result = test_bit(b, (unsigned long *) &info->current_bits);
0209     return 0;
0210 }
0211 EXPORT_SYMBOL_GPL(dm_bitset_test_bit);
0212 
0213 static int cursor_next_array_entry(struct dm_bitset_cursor *c)
0214 {
0215     int r;
0216     __le64 *value;
0217 
0218     r = dm_array_cursor_next(&c->cursor);
0219     if (r)
0220         return r;
0221 
0222     dm_array_cursor_get_value(&c->cursor, (void **) &value);
0223     c->array_index++;
0224     c->bit_index = 0;
0225     c->current_bits = le64_to_cpu(*value);
0226     return 0;
0227 }
0228 
0229 int dm_bitset_cursor_begin(struct dm_disk_bitset *info,
0230                dm_block_t root, uint32_t nr_entries,
0231                struct dm_bitset_cursor *c)
0232 {
0233     int r;
0234     __le64 *value;
0235 
0236     if (!nr_entries)
0237         return -ENODATA;
0238 
0239     c->info = info;
0240     c->entries_remaining = nr_entries;
0241 
0242     r = dm_array_cursor_begin(&info->array_info, root, &c->cursor);
0243     if (r)
0244         return r;
0245 
0246     dm_array_cursor_get_value(&c->cursor, (void **) &value);
0247     c->array_index = 0;
0248     c->bit_index = 0;
0249     c->current_bits = le64_to_cpu(*value);
0250 
0251     return r;
0252 }
0253 EXPORT_SYMBOL_GPL(dm_bitset_cursor_begin);
0254 
0255 void dm_bitset_cursor_end(struct dm_bitset_cursor *c)
0256 {
0257     return dm_array_cursor_end(&c->cursor);
0258 }
0259 EXPORT_SYMBOL_GPL(dm_bitset_cursor_end);
0260 
0261 int dm_bitset_cursor_next(struct dm_bitset_cursor *c)
0262 {
0263     int r = 0;
0264 
0265     if (!c->entries_remaining)
0266         return -ENODATA;
0267 
0268     c->entries_remaining--;
0269     if (++c->bit_index > 63)
0270         r = cursor_next_array_entry(c);
0271 
0272     return r;
0273 }
0274 EXPORT_SYMBOL_GPL(dm_bitset_cursor_next);
0275 
0276 int dm_bitset_cursor_skip(struct dm_bitset_cursor *c, uint32_t count)
0277 {
0278     int r;
0279     __le64 *value;
0280     uint32_t nr_array_skip;
0281     uint32_t remaining_in_word = 64 - c->bit_index;
0282 
0283     if (c->entries_remaining < count)
0284         return -ENODATA;
0285 
0286     if (count < remaining_in_word) {
0287         c->bit_index += count;
0288         c->entries_remaining -= count;
0289         return 0;
0290 
0291     } else {
0292         c->entries_remaining -= remaining_in_word;
0293         count -= remaining_in_word;
0294     }
0295 
0296     nr_array_skip = (count / 64) + 1;
0297     r = dm_array_cursor_skip(&c->cursor, nr_array_skip);
0298     if (r)
0299         return r;
0300 
0301     dm_array_cursor_get_value(&c->cursor, (void **) &value);
0302     c->entries_remaining -= count;
0303     c->array_index += nr_array_skip;
0304     c->bit_index = count & 63;
0305     c->current_bits = le64_to_cpu(*value);
0306 
0307     return 0;
0308 }
0309 EXPORT_SYMBOL_GPL(dm_bitset_cursor_skip);
0310 
0311 bool dm_bitset_cursor_get_value(struct dm_bitset_cursor *c)
0312 {
0313     return test_bit(c->bit_index, (unsigned long *) &c->current_bits);
0314 }
0315 EXPORT_SYMBOL_GPL(dm_bitset_cursor_get_value);
0316 
0317 /*----------------------------------------------------------------*/
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!