X-Git-Url: https://git.kernel.dk/?a=blobdiff_plain;f=lib%2Faxmap.c;h=27301bd8465848d3cf8af57fb4c28b1078084742;hb=36833fb04b5f9a734e96a571dfb52fc54b5b95e7;hp=923aae403085ac0cb1ee2efe48aef5b0207de651;hpb=6fa22eb8d7aec95851b37b64a2c38a17b1da48ee;p=fio.git diff --git a/lib/axmap.c b/lib/axmap.c index 923aae40..27301bd8 100644 --- a/lib/axmap.c +++ b/lib/axmap.c @@ -57,26 +57,33 @@ static const unsigned long bit_masks[] = { #endif }; +/** + * struct axmap_level - a bitmap used to implement struct axmap + * @level: Level index. Each map has at least one level with index zero. The + * higher the level index, the fewer bits a struct axmap_level contains. + * @map_size: Number of elements of the @map array. + * @map: A bitmap with @map_size elements. + */ struct axmap_level { int level; unsigned long map_size; unsigned long *map; }; +/** + * struct axmap - a set that can store numbers 0 .. @nr_bits - 1 + * @nr_level: Number of elements of the @levels array. + * @levels: struct axmap_level array in which lower levels contain more bits + * than higher levels. + * @nr_bits: One more than the highest value stored in the set. + */ struct axmap { unsigned int nr_levels; struct axmap_level *levels; uint64_t nr_bits; }; -static inline unsigned long ulog64(unsigned long val, unsigned int log) -{ - while (log-- && val) - val >>= UNIT_SHIFT; - - return val; -} - +/* Remove all elements from the @axmap set */ void axmap_reset(struct axmap *axmap) { int i; @@ -102,7 +109,8 @@ void axmap_free(struct axmap *axmap) free(axmap); } -struct axmap *axmap_new(unsigned long nr_bits) +/* Allocate memory for a set that can store the numbers 0 .. @nr_bits - 1. */ +struct axmap *axmap_new(uint64_t nr_bits) { struct axmap *axmap; unsigned int i, levels; @@ -120,34 +128,44 @@ struct axmap *axmap_new(unsigned long nr_bits) axmap->nr_levels = levels; axmap->levels = calloc(axmap->nr_levels, sizeof(struct axmap_level)); + if (!axmap->levels) + goto free_axmap; axmap->nr_bits = nr_bits; for (i = 0; i < axmap->nr_levels; i++) { struct axmap_level *al = &axmap->levels[i]; + nr_bits = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT; + al->level = i; - al->map_size = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT; + al->map_size = nr_bits; al->map = malloc(al->map_size * sizeof(unsigned long)); if (!al->map) - goto err; + goto free_levels; - nr_bits = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT; } axmap_reset(axmap); return axmap; -err: + +free_levels: for (i = 0; i < axmap->nr_levels; i++) - if (axmap->levels[i].map) - free(axmap->levels[i].map); + free(axmap->levels[i].map); free(axmap->levels); + +free_axmap: free(axmap); return NULL; } +/* + * Call @func for each level, starting at level zero, until a level is found + * for which @func returns true. Return false if none of the @func calls + * returns true. + */ static bool axmap_handler(struct axmap *axmap, uint64_t bit_nr, - bool (*func)(struct axmap_level *, unsigned long, unsigned int, + bool (*func)(struct axmap_level *, uint64_t, unsigned int, void *), void *data) { struct axmap_level *al; @@ -170,13 +188,18 @@ static bool axmap_handler(struct axmap *axmap, uint64_t bit_nr, return false; } +/* + * Call @func for each level, starting at the highest level, until a level is + * found for which @func returns true. Return false if none of the @func calls + * returns true. + */ static bool axmap_handler_topdown(struct axmap *axmap, uint64_t bit_nr, - bool (*func)(struct axmap_level *, unsigned long, unsigned int, void *)) + bool (*func)(struct axmap_level *, uint64_t, unsigned int, void *)) { int i; for (i = axmap->nr_levels - 1; i >= 0; i--) { - unsigned long index = ulog64(bit_nr, i); + uint64_t index = bit_nr >> (UNIT_SHIFT * i); unsigned long offset = index >> UNIT_SHIFT; unsigned int bit = index & BLOCKS_PER_UNIT_MASK; @@ -192,7 +215,12 @@ struct axmap_set_data { unsigned int set_bits; }; -static bool axmap_set_fn(struct axmap_level *al, unsigned long offset, +/* + * Set at most @__data->nr_bits bits in @al at offset @offset. Do not exceed + * the boundary of the element at offset @offset. Return the number of bits + * that have been set in @__data->set_bits if @al->level == 0. + */ +static bool axmap_set_fn(struct axmap_level *al, uint64_t offset, unsigned int bit, void *__data) { struct axmap_set_data *data = __data; @@ -208,18 +236,14 @@ static bool axmap_set_fn(struct axmap_level *al, unsigned long offset, */ overlap = al->map[offset] & mask; if (overlap == mask) { -done: data->set_bits = 0; return true; } if (overlap) { - const int __bit = ffz(~overlap); - - nr_bits = __bit - bit; + nr_bits = ffz(~overlap) - bit; if (!nr_bits) - goto done; - + return true; mask = bit_masks[nr_bits] << bit; } @@ -230,36 +254,33 @@ done: if (!al->level) data->set_bits = nr_bits; + /* For the next level */ data->nr_bits = 1; + return al->map[offset] != -1UL; } +/* + * Set up to @data->nr_bits starting from @bit_nr in @axmap. Start at + * @bit_nr. If that bit has not yet been set then set it and continue until + * either @data->nr_bits have been set or a 1 bit is found. Store the number + * of bits that have been set in @data->set_bits. It is guaranteed that all + * bits that have been requested to set fit in the same unsigned long word of + * level 0 of @axmap. + */ static void __axmap_set(struct axmap *axmap, uint64_t bit_nr, struct axmap_set_data *data) { - unsigned int set_bits, nr_bits = data->nr_bits; + unsigned int nr_bits = data->nr_bits; if (bit_nr > axmap->nr_bits) return; else if (bit_nr + nr_bits > axmap->nr_bits) nr_bits = axmap->nr_bits - bit_nr; - set_bits = 0; - while (nr_bits) { - axmap_handler(axmap, bit_nr, axmap_set_fn, data); - set_bits += data->set_bits; + assert(nr_bits <= BLOCKS_PER_UNIT); - if (!data->set_bits || - data->set_bits != (BLOCKS_PER_UNIT - nr_bits)) - break; - - nr_bits -= data->set_bits; - bit_nr += data->set_bits; - - data->nr_bits = nr_bits; - } - - data->set_bits = set_bits; + axmap_handler(axmap, bit_nr, axmap_set_fn, data); } void axmap_set(struct axmap *axmap, uint64_t bit_nr) @@ -269,6 +290,12 @@ void axmap_set(struct axmap *axmap, uint64_t bit_nr) __axmap_set(axmap, bit_nr, &data); } +/* + * Set up to @nr_bits starting from @bit in @axmap. Start at @bit. If that + * bit has not yet been set then set it and continue until either @nr_bits + * have been set or a 1 bit is found. Return the number of bits that have been + * set. + */ unsigned int axmap_set_nr(struct axmap *axmap, uint64_t bit_nr, unsigned int nr_bits) { @@ -295,10 +322,10 @@ unsigned int axmap_set_nr(struct axmap *axmap, uint64_t bit_nr, return set_bits; } -static bool axmap_isset_fn(struct axmap_level *al, unsigned long offset, +static bool axmap_isset_fn(struct axmap_level *al, uint64_t offset, unsigned int bit, void *unused) { - return (al->map[offset] & (1UL << bit)) != 0; + return (al->map[offset] & (1ULL << bit)) != 0; } bool axmap_isset(struct axmap *axmap, uint64_t bit_nr)