From 7ebd796f4e50c21d652e62bf1e112755b0f338a8 Mon Sep 17 00:00:00 2001 From: Jens Axboe Date: Wed, 28 Nov 2012 21:24:46 +0100 Subject: [PATCH] Rename the bitmap to axmap It's not really a bitmap, it's a bitmap of bitmaps. Now named. Signed-off-by: Jens Axboe --- Makefile | 2 +- file.h | 8 +- filesetup.c | 10 +- io_ddir.h | 2 +- io_u.c | 10 +- lib/axmap.c | 390 +++++++++++++++++++++++++++++++++++++++++++++++++++ lib/axmap.h | 18 +++ lib/bitmap.c | 373 ------------------------------------------------ lib/bitmap.h | 18 --- 9 files changed, 424 insertions(+), 407 deletions(-) create mode 100644 lib/axmap.c create mode 100644 lib/axmap.h delete mode 100644 lib/bitmap.c delete mode 100644 lib/bitmap.h diff --git a/Makefile b/Makefile index d197853e..6384ff01 100644 --- a/Makefile +++ b/Makefile @@ -17,7 +17,7 @@ SOURCE := gettime.c fio.c ioengines.c init.c stat.c log.c time.c filesetup.c \ lib/num2str.c lib/ieee754.c $(wildcard crc/*.c) engines/cpu.c \ engines/mmap.c engines/sync.c engines/null.c engines/net.c \ memalign.c server.c client.c iolog.c backend.c libfio.c flow.c \ - json.c lib/zipf.c lib/bitmap.c lib/lfsr.c gettime-thread.c + json.c lib/zipf.c lib/axmap.c lib/lfsr.c gettime-thread.c ifeq ($(UNAME), Linux) SOURCE += diskutil.c fifo.c blktrace.c helpers.c cgroup.c trim.c \ diff --git a/file.h b/file.h index 9dd08731..3024c544 100644 --- a/file.h +++ b/file.h @@ -6,7 +6,7 @@ #include "io_ddir.h" #include "flist.h" #include "lib/zipf.h" -#include "lib/bitmap.h" +#include "lib/axmap.h" #include "lib/lfsr.h" /* @@ -110,7 +110,7 @@ struct fio_file { /* * block map for random io */ - struct bitmap *io_bitmap; + struct axmap *io_axmap; struct fio_lfsr lfsr; @@ -181,8 +181,8 @@ static inline void fio_file_reset(struct fio_file *f) f->last_pos = f->file_offset; f->last_start = -1ULL; f->file_pos = -1ULL; - if (f->io_bitmap) - bitmap_reset(f->io_bitmap); + if (f->io_axmap) + axmap_reset(f->io_axmap); } #endif diff --git a/filesetup.c b/filesetup.c index b70bd454..4fe37ae7 100644 --- a/filesetup.c +++ b/filesetup.c @@ -13,7 +13,7 @@ #include "filehash.h" #include "os/os.h" #include "hash.h" -#include "lib/bitmap.h" +#include "lib/axmap.h" #ifdef FIO_HAVE_LINUX_FALLOCATE #include @@ -921,8 +921,8 @@ int init_random_map(struct thread_data *td) if (!lfsr_init(&f->lfsr, blocks)) continue; } else if (!td->o.norandommap) { - f->io_bitmap = bitmap_new(blocks); - if (f->io_bitmap) + f->io_axmap = axmap_new(blocks); + if (f->io_axmap) continue; } @@ -972,8 +972,8 @@ void close_and_free_files(struct thread_data *td) sfree(f->file_name); f->file_name = NULL; - bitmap_free(f->io_bitmap); - f->io_bitmap = NULL; + axmap_free(f->io_axmap); + f->io_axmap = NULL; sfree(f); } diff --git a/io_ddir.h b/io_ddir.h index d13c6b1e..4fde56e3 100644 --- a/io_ddir.h +++ b/io_ddir.h @@ -30,7 +30,7 @@ enum td_ddir { #define td_trim(td) ((td)->o.td_ddir & TD_DDIR_TRIM) #define td_rw(td) (((td)->o.td_ddir & TD_DDIR_RW) == TD_DDIR_RW) #define td_random(td) ((td)->o.td_ddir & TD_DDIR_RAND) -#define file_randommap(td, f) (!(td)->o.norandommap && (f)->io_bitmap) +#define file_randommap(td, f) (!(td)->o.norandommap && (f)->io_axmap) static inline int ddir_sync(enum fio_ddir ddir) { diff --git a/io_u.c b/io_u.c index 2904ad40..006f2c9e 100644 --- a/io_u.c +++ b/io_u.c @@ -10,7 +10,7 @@ #include "verify.h" #include "trim.h" #include "lib/rand.h" -#include "lib/bitmap.h" +#include "lib/axmap.h" struct io_completion_data { int nr; /* input */ @@ -21,12 +21,12 @@ struct io_completion_data { }; /* - * The ->io_bitmap contains a map of blocks we have or have not done io + * The ->io_axmap contains a map of blocks we have or have not done io * to yet. Used to make sure we cover the entire range in a fair fashion. */ static int random_map_free(struct fio_file *f, const unsigned long long block) { - return !bitmap_isset(f->io_bitmap, block); + return !axmap_isset(f->io_axmap, block); } /* @@ -43,7 +43,7 @@ static void mark_random_map(struct thread_data *td, struct io_u *io_u) nr_blocks = (io_u->buflen + min_bs - 1) / min_bs; if (!(io_u->flags & IO_U_F_BUSY_OK)) - nr_blocks = bitmap_set_nr(f->io_bitmap, block, nr_blocks); + nr_blocks = axmap_set_nr(f->io_axmap, block, nr_blocks); if ((nr_blocks * min_bs) < io_u->buflen) io_u->buflen = nr_blocks * min_bs; @@ -122,7 +122,7 @@ static int __get_next_rand_offset(struct thread_data *td, struct fio_file *f, dprint(FD_RANDOM, "get_next_rand_offset: offset %llu busy\n", *b); - *b = bitmap_next_free(f->io_bitmap, *b); + *b = axmap_next_free(f->io_axmap, *b); if (*b == (uint64_t) -1ULL) return 1; ret: diff --git a/lib/axmap.c b/lib/axmap.c new file mode 100644 index 00000000..a44e0ecb --- /dev/null +++ b/lib/axmap.c @@ -0,0 +1,390 @@ +/* + * Bitmap of bitmaps, where each layer is number-of-bits-per-word smaller than + * the previous. Hence an 'axmap', since we axe each previous layer into a + * much smaller piece. I swear, that is why it's named like that. It has + * nothing to do with anything remotely narcissistic. + * + * A set bit at layer N indicates a full word at layer N-1, and so forth. As + * the bitmap becomes progressively more full, checking for existance + * becomes cheaper (since fewer layers are walked, making it a lot more + * cache friendly) and locating the next free space likewise. + * + * Axmaps get pretty close to optimal (1 bit per block) space usage, since + * layers quickly diminish in size. Doing the size math is straight forward, + * since we have log64(blocks) layers of maps. For 20000 blocks, overhead + * is roughly 1.9%, or 1.019 bits per block. The number quickly converges + * towards 1.0158, or 1.58% of overhead. + */ +#include +#include +#include +#include + +#include "../arch/arch.h" +#include "axmap.h" +#include "../smalloc.h" +#include "../minmax.h" + +#if BITS_PER_LONG == 64 +#define UNIT_SHIFT 6 +#elif BITS_PER_LONG == 32 +#define UNIT_SHIFT 5 +#else +#error "Number of arch bits unknown" +#endif + +#define BLOCKS_PER_UNIT (1UL << UNIT_SHIFT) +#define BLOCKS_PER_UNIT_MASK (BLOCKS_PER_UNIT - 1) + +#define firstfree_valid(b) ((b)->first_free != (uint64_t) -1) + +struct axmap_level { + int level; + unsigned long map_size; + unsigned long *map; +}; + +struct axmap { + unsigned int nr_levels; + struct axmap_level *levels; + uint64_t first_free; +}; + +static unsigned long ulog64(unsigned long val, unsigned int log) +{ + while (log-- && val) + val >>= UNIT_SHIFT; + + return val; +} + +void axmap_reset(struct axmap *axmap) +{ + int i; + + for (i = 0; i < axmap->nr_levels; i++) { + struct axmap_level *al = &axmap->levels[i]; + + memset(al->map, 0, al->map_size * sizeof(unsigned long)); + } +} + +void axmap_free(struct axmap *axmap) +{ + unsigned int i; + + if (!axmap) + return; + + for (i = 0; i < axmap->nr_levels; i++) + sfree(axmap->levels[i].map); + + sfree(axmap->levels); + sfree(axmap); +} + +struct axmap *axmap_new(unsigned long nr_bits) +{ + struct axmap *axmap; + unsigned int i, levels; + + axmap = smalloc(sizeof(*axmap)); + if (!axmap) + return NULL; + + levels = 1; + i = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT; + while (i > 1) { + i = (i + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT; + levels++; + } + + axmap->nr_levels = levels; + axmap->levels = smalloc(axmap->nr_levels * sizeof(struct axmap_level)); + axmap->first_free = 0; + + for (i = 0; i < axmap->nr_levels; i++) { + struct axmap_level *al = &axmap->levels[i]; + + al->level = i; + al->map_size = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT; + al->map = smalloc(al->map_size * sizeof(unsigned long)); + if (!al->map) + goto err; + + nr_bits = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT; + } + + axmap_reset(axmap); + return axmap; +err: + for (i = 0; i < axmap->nr_levels; i++) + if (axmap->levels[i].map) + sfree(axmap->levels[i].map); + + sfree(axmap->levels); + return NULL; +} + +static int axmap_handler(struct axmap *axmap, uint64_t bit_nr, + int (*func)(struct axmap_level *, unsigned long, unsigned int, + void *), void *data) +{ + struct axmap_level *al; + int i; + + for (i = 0; i < axmap->nr_levels; i++) { + unsigned long index = ulog64(bit_nr, i); + unsigned long offset = index >> UNIT_SHIFT; + unsigned int bit = index & BLOCKS_PER_UNIT_MASK; + + al = &axmap->levels[i]; + + if (func(al, offset, bit, data)) + return 1; + } + + return 0; +} + +static int axmap_handler_topdown(struct axmap *axmap, uint64_t bit_nr, + int (*func)(struct axmap_level *, unsigned long, unsigned int, void *), + void *data) +{ + struct axmap_level *al; + int i, level = axmap->nr_levels; + + for (i = axmap->nr_levels - 1; i >= 0; i--) { + unsigned long index = ulog64(bit_nr, --level); + unsigned long offset = index >> UNIT_SHIFT; + unsigned int bit = index & BLOCKS_PER_UNIT_MASK; + + al = &axmap->levels[i]; + + if (func(al, offset, bit, data)) + return 1; + } + + return 0; +} + +static int axmap_clear_fn(struct axmap_level *al, unsigned long offset, + unsigned int bit, void *unused) +{ + if (!(al->map[offset] & (1UL << bit))) + return 1; + + al->map[offset] &= ~(1UL << bit); + return 0; +} + +void axmap_clear(struct axmap *axmap, uint64_t bit_nr) +{ + axmap_handler(axmap, bit_nr, axmap_clear_fn, NULL); +} + +struct axmap_set_data { + unsigned int nr_bits; + unsigned int set_bits; + unsigned int fail_ok; +}; + +static unsigned long bit_masks[] = { + 0x0000000000000000, 0x0000000000000001, 0x0000000000000003, 0x0000000000000007, + 0x000000000000000f, 0x000000000000001f, 0x000000000000003f, 0x000000000000007f, + 0x00000000000000ff, 0x00000000000001ff, 0x00000000000003ff, 0x00000000000007ff, + 0x0000000000000fff, 0x0000000000001fff, 0x0000000000003fff, 0x0000000000007fff, + 0x000000000000ffff, 0x000000000001ffff, 0x000000000003ffff, 0x000000000007ffff, + 0x00000000000fffff, 0x00000000001fffff, 0x00000000003fffff, 0x00000000007fffff, + 0x0000000000ffffff, 0x0000000001ffffff, 0x0000000003ffffff, 0x0000000007ffffff, + 0x000000000fffffff, 0x000000001fffffff, 0x000000003fffffff, 0x000000007fffffff, + 0x00000000ffffffff, +#if BITS_PER_LONG == 64 + 0x00000001ffffffff, 0x00000003ffffffff, 0x00000007ffffffff, 0x0000000fffffffff, + 0x0000001fffffffff, 0x0000003fffffffff, 0x0000007fffffffff, 0x000000ffffffffff, + 0x000001ffffffffff, 0x000003ffffffffff, 0x000007ffffffffff, 0x00000fffffffffff, + 0x00001fffffffffff, 0x00003fffffffffff, 0x00007fffffffffff, 0x0000ffffffffffff, + 0x0001ffffffffffff, 0x0003ffffffffffff, 0x0007ffffffffffff, 0x000fffffffffffff, + 0x001fffffffffffff, 0x003fffffffffffff, 0x007fffffffffffff, 0x00ffffffffffffff, + 0x01ffffffffffffff, 0x03ffffffffffffff, 0x07ffffffffffffff, 0x0fffffffffffffff, + 0x1fffffffffffffff, 0x3fffffffffffffff, 0x7fffffffffffffff, 0xffffffffffffffff +#endif +}; + +static int axmap_set_fn(struct axmap_level *al, unsigned long offset, + unsigned int bit, void *__data) +{ + struct axmap_set_data *data = __data; + unsigned long mask, overlap; + unsigned int nr_bits; + + nr_bits = min(data->nr_bits, BLOCKS_PER_UNIT - bit); + + mask = bit_masks[nr_bits] << bit; + + /* + * Mask off any potential overlap, only sets contig regions + */ + overlap = al->map[offset] & mask; + if (overlap == mask) { + assert(data->fail_ok); + return 1; + } + + while (overlap) { + unsigned long clear_mask = ~(1UL << ffz(~overlap)); + + mask &= clear_mask; + overlap &= clear_mask; + nr_bits--; + } + + assert(mask); + assert(!(al->map[offset] & mask)); + + al->map[offset] |= mask; + + if (!al->level) + data->set_bits = nr_bits; + + data->nr_bits = 1; + return al->map[offset] != -1UL; +} + +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; + + if (axmap->first_free >= bit_nr && + axmap->first_free < bit_nr + data->nr_bits) + axmap->first_free = -1ULL; + + set_bits = 0; + while (nr_bits) { + axmap_handler(axmap, bit_nr, axmap_set_fn, data); + set_bits += data->set_bits; + + if (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->fail_ok = 1; + } + + data->set_bits = set_bits; +} + +void axmap_set(struct axmap *axmap, uint64_t bit_nr) +{ + struct axmap_set_data data = { .nr_bits = 1, }; + + __axmap_set(axmap, bit_nr, &data); +} + +unsigned int axmap_set_nr(struct axmap *axmap, uint64_t bit_nr, unsigned int nr_bits) +{ + struct axmap_set_data data = { .nr_bits = nr_bits, }; + + __axmap_set(axmap, bit_nr, &data); + return data.set_bits; +} + +static int axmap_isset_fn(struct axmap_level *al, unsigned long offset, + unsigned int bit, void *unused) +{ + return (al->map[offset] & (1UL << bit)) != 0; +} + +int axmap_isset(struct axmap *axmap, uint64_t bit_nr) +{ + return axmap_handler_topdown(axmap, bit_nr, axmap_isset_fn, NULL); +} + +static uint64_t axmap_find_first_free(struct axmap *axmap, unsigned int level, + uint64_t index) +{ + unsigned long j; + int i; + + /* + * Start at the bottom, then converge towards first free bit at the top + */ + for (i = level; i >= 0; i--) { + struct axmap_level *al = &axmap->levels[i]; + + if (index >= al->map_size) { + index = -1ULL; + break; + } + + for (j = index; j < al->map_size; j++) { + if (al->map[j] == -1UL) + continue; + + /* + * First free bit here is our index into the first + * free bit at the next higher level + */ + index = (j << UNIT_SHIFT) + ffz(al->map[j]); + break; + } + } + + return index; +} + +uint64_t axmap_first_free(struct axmap *axmap) +{ + if (firstfree_valid(axmap)) + return axmap->first_free; + + axmap->first_free = axmap_find_first_free(axmap, axmap->nr_levels - 1, 0); + return axmap->first_free; +} + +struct axmap_next_free_data { + unsigned int level; + unsigned long offset; + uint64_t bit; +}; + +static int axmap_next_free_fn(struct axmap_level *al, unsigned long offset, + unsigned int bit, void *__data) +{ + struct axmap_next_free_data *data = __data; + uint64_t mask = ~((1UL << ((data->bit & BLOCKS_PER_UNIT_MASK) + 1)) - 1); + + if (!(mask & al->map[offset])) + return 0; + + if (al->map[offset] != -1UL) { + data->level = al->level; + data->offset = offset; + return 1; + } + + data->bit = (data->bit + BLOCKS_PER_UNIT - 1) / BLOCKS_PER_UNIT; + return 0; +} + +/* + * 'bit_nr' is already set. Find the next free bit after this one. + */ +uint64_t axmap_next_free(struct axmap *axmap, uint64_t bit_nr) +{ + struct axmap_next_free_data data = { .level = -1U, .bit = bit_nr, }; + + if (firstfree_valid(axmap) && bit_nr < axmap->first_free) + return axmap->first_free; + + if (!axmap_handler(axmap, bit_nr, axmap_next_free_fn, &data)) + return axmap_first_free(axmap); + + assert(data.level != -1U); + + return axmap_find_first_free(axmap, data.level, data.offset); +} diff --git a/lib/axmap.h b/lib/axmap.h new file mode 100644 index 00000000..edfeba80 --- /dev/null +++ b/lib/axmap.h @@ -0,0 +1,18 @@ +#ifndef FIO_BITMAP_H +#define FIO_BITMAP_H + +#include + +struct axmap; +struct axmap *axmap_new(unsigned long nr_bits); +void axmap_free(struct axmap *bm); + +void axmap_clear(struct axmap *axmap, uint64_t bit_nr); +void axmap_set(struct axmap *axmap, uint64_t bit_nr); +unsigned int axmap_set_nr(struct axmap *axmap, uint64_t bit_nr, unsigned int nr_bits); +int axmap_isset(struct axmap *axmap, uint64_t bit_nr); +uint64_t axmap_first_free(struct axmap *axmap); +uint64_t axmap_next_free(struct axmap *axmap, uint64_t bit_nr); +void axmap_reset(struct axmap *axmap); + +#endif diff --git a/lib/bitmap.c b/lib/bitmap.c deleted file mode 100644 index 51b91d9c..00000000 --- a/lib/bitmap.c +++ /dev/null @@ -1,373 +0,0 @@ -#include -#include -#include -#include - -#include "../arch/arch.h" -#include "bitmap.h" -#include "../smalloc.h" -#include "../minmax.h" - -#if BITS_PER_LONG == 64 -#define UNIT_SHIFT 6 -#elif BITS_PER_LONG == 32 -#define UNIT_SHIFT 5 -#else -#error "Number of arch bits unknown" -#endif - -#define BLOCKS_PER_UNIT (1UL << UNIT_SHIFT) -#define BLOCKS_PER_UNIT_MASK (BLOCKS_PER_UNIT - 1) - -#define firstfree_valid(b) ((b)->first_free != (uint64_t) -1) - -struct bitmap_level { - int level; - unsigned long map_size; - unsigned long *map; -}; - -struct bitmap { - unsigned int nr_levels; - struct bitmap_level *levels; - uint64_t first_free; -}; - -static unsigned long ulog64(unsigned long val, unsigned int log) -{ - while (log-- && val) - val >>= UNIT_SHIFT; - - return val; -} - -void bitmap_reset(struct bitmap *bitmap) -{ - int i; - - for (i = 0; i < bitmap->nr_levels; i++) { - struct bitmap_level *bl = &bitmap->levels[i]; - - memset(bl->map, 0, bl->map_size * sizeof(unsigned long)); - } -} - -void bitmap_free(struct bitmap *bitmap) -{ - unsigned int i; - - if (!bitmap) - return; - - for (i = 0; i < bitmap->nr_levels; i++) - sfree(bitmap->levels[i].map); - - sfree(bitmap->levels); - sfree(bitmap); -} - -struct bitmap *bitmap_new(unsigned long nr_bits) -{ - struct bitmap *bitmap; - unsigned int i, levels; - - bitmap = smalloc(sizeof(*bitmap)); - if (!bitmap) - return NULL; - - levels = 1; - i = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT; - while (i > 1) { - i = (i + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT; - levels++; - } - - bitmap->nr_levels = levels; - bitmap->levels = smalloc(bitmap->nr_levels * sizeof(struct bitmap_level)); - bitmap->first_free = 0; - - for (i = 0; i < bitmap->nr_levels; i++) { - struct bitmap_level *bl = &bitmap->levels[i]; - - bl->level = i; - bl->map_size = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT; - bl->map = smalloc(bl->map_size * sizeof(unsigned long)); - if (!bl->map) - goto err; - - nr_bits = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT; - } - - bitmap_reset(bitmap); - return bitmap; -err: - for (i = 0; i < bitmap->nr_levels; i++) - if (bitmap->levels[i].map) - sfree(bitmap->levels[i].map); - - sfree(bitmap->levels); - return NULL; -} - -static int bitmap_handler(struct bitmap *bitmap, uint64_t bit_nr, - int (*func)(struct bitmap_level *, unsigned long, unsigned int, - void *), void *data) -{ - struct bitmap_level *bl; - int i; - - for (i = 0; i < bitmap->nr_levels; i++) { - unsigned long index = ulog64(bit_nr, i); - unsigned long offset = index >> UNIT_SHIFT; - unsigned int bit = index & BLOCKS_PER_UNIT_MASK; - - bl = &bitmap->levels[i]; - - if (func(bl, offset, bit, data)) - return 1; - } - - return 0; -} - -static int bitmap_handler_topdown(struct bitmap *bitmap, uint64_t bit_nr, - int (*func)(struct bitmap_level *, unsigned long, unsigned int, void *), - void *data) -{ - struct bitmap_level *bl; - int i, level = bitmap->nr_levels; - - for (i = bitmap->nr_levels - 1; i >= 0; i--) { - unsigned long index = ulog64(bit_nr, --level); - unsigned long offset = index >> UNIT_SHIFT; - unsigned int bit = index & BLOCKS_PER_UNIT_MASK; - - bl = &bitmap->levels[i]; - - if (func(bl, offset, bit, data)) - return 1; - } - - return 0; -} - -static int bitmap_clear_fn(struct bitmap_level *bl, unsigned long offset, - unsigned int bit, void *unused) -{ - if (!(bl->map[offset] & (1UL << bit))) - return 1; - - bl->map[offset] &= ~(1UL << bit); - return 0; -} - -void bitmap_clear(struct bitmap *bitmap, uint64_t bit_nr) -{ - bitmap_handler(bitmap, bit_nr, bitmap_clear_fn, NULL); -} - -struct bitmap_set_data { - unsigned int nr_bits; - unsigned int set_bits; - unsigned int fail_ok; -}; - -static unsigned long bit_masks[] = { - 0x0000000000000000, 0x0000000000000001, 0x0000000000000003, 0x0000000000000007, - 0x000000000000000f, 0x000000000000001f, 0x000000000000003f, 0x000000000000007f, - 0x00000000000000ff, 0x00000000000001ff, 0x00000000000003ff, 0x00000000000007ff, - 0x0000000000000fff, 0x0000000000001fff, 0x0000000000003fff, 0x0000000000007fff, - 0x000000000000ffff, 0x000000000001ffff, 0x000000000003ffff, 0x000000000007ffff, - 0x00000000000fffff, 0x00000000001fffff, 0x00000000003fffff, 0x00000000007fffff, - 0x0000000000ffffff, 0x0000000001ffffff, 0x0000000003ffffff, 0x0000000007ffffff, - 0x000000000fffffff, 0x000000001fffffff, 0x000000003fffffff, 0x000000007fffffff, - 0x00000000ffffffff, -#if BITS_PER_LONG == 64 - 0x00000001ffffffff, 0x00000003ffffffff, 0x00000007ffffffff, 0x0000000fffffffff, - 0x0000001fffffffff, 0x0000003fffffffff, 0x0000007fffffffff, 0x000000ffffffffff, - 0x000001ffffffffff, 0x000003ffffffffff, 0x000007ffffffffff, 0x00000fffffffffff, - 0x00001fffffffffff, 0x00003fffffffffff, 0x00007fffffffffff, 0x0000ffffffffffff, - 0x0001ffffffffffff, 0x0003ffffffffffff, 0x0007ffffffffffff, 0x000fffffffffffff, - 0x001fffffffffffff, 0x003fffffffffffff, 0x007fffffffffffff, 0x00ffffffffffffff, - 0x01ffffffffffffff, 0x03ffffffffffffff, 0x07ffffffffffffff, 0x0fffffffffffffff, - 0x1fffffffffffffff, 0x3fffffffffffffff, 0x7fffffffffffffff, 0xffffffffffffffff -#endif -}; - -static int bitmap_set_fn(struct bitmap_level *bl, unsigned long offset, - unsigned int bit, void *__data) -{ - struct bitmap_set_data *data = __data; - unsigned long mask, overlap; - unsigned int nr_bits; - - nr_bits = min(data->nr_bits, BLOCKS_PER_UNIT - bit); - - mask = bit_masks[nr_bits] << bit; - - /* - * Mask off any potential overlap, only sets contig regions - */ - overlap = bl->map[offset] & mask; - if (overlap == mask) { - assert(data->fail_ok); - return 1; - } - - while (overlap) { - unsigned long clear_mask = ~(1UL << ffz(~overlap)); - - mask &= clear_mask; - overlap &= clear_mask; - nr_bits--; - } - - assert(mask); - assert(!(bl->map[offset] & mask)); - - bl->map[offset] |= mask; - - if (!bl->level) - data->set_bits = nr_bits; - - data->nr_bits = 1; - return bl->map[offset] != -1UL; -} - -static void __bitmap_set(struct bitmap *bitmap, uint64_t bit_nr, - struct bitmap_set_data *data) -{ - unsigned int set_bits, nr_bits = data->nr_bits; - - if (bitmap->first_free >= bit_nr && - bitmap->first_free < bit_nr + data->nr_bits) - bitmap->first_free = -1ULL; - - set_bits = 0; - while (nr_bits) { - bitmap_handler(bitmap, bit_nr, bitmap_set_fn, data); - set_bits += data->set_bits; - - if (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->fail_ok = 1; - } - - data->set_bits = set_bits; -} - -void bitmap_set(struct bitmap *bitmap, uint64_t bit_nr) -{ - struct bitmap_set_data data = { .nr_bits = 1, }; - - __bitmap_set(bitmap, bit_nr, &data); -} - -unsigned int bitmap_set_nr(struct bitmap *bitmap, uint64_t bit_nr, unsigned int nr_bits) -{ - struct bitmap_set_data data = { .nr_bits = nr_bits, }; - - __bitmap_set(bitmap, bit_nr, &data); - return data.set_bits; -} - -static int bitmap_isset_fn(struct bitmap_level *bl, unsigned long offset, - unsigned int bit, void *unused) -{ - return (bl->map[offset] & (1UL << bit)) != 0; -} - -int bitmap_isset(struct bitmap *bitmap, uint64_t bit_nr) -{ - return bitmap_handler_topdown(bitmap, bit_nr, bitmap_isset_fn, NULL); -} - -static uint64_t bitmap_find_first_free(struct bitmap *bitmap, unsigned int level, - uint64_t index) -{ - unsigned long j; - int i; - - /* - * Start at the bottom, then converge towards first free bit at the top - */ - for (i = level; i >= 0; i--) { - struct bitmap_level *bl = &bitmap->levels[i]; - - if (index >= bl->map_size) { - index = -1ULL; - break; - } - - for (j = index; j < bl->map_size; j++) { - if (bl->map[j] == -1UL) - continue; - - /* - * First free bit here is our index into the first - * free bit at the next higher level - */ - index = (j << UNIT_SHIFT) + ffz(bl->map[j]); - break; - } - } - - return index; -} - -uint64_t bitmap_first_free(struct bitmap *bitmap) -{ - if (firstfree_valid(bitmap)) - return bitmap->first_free; - - bitmap->first_free = bitmap_find_first_free(bitmap, bitmap->nr_levels - 1, 0); - return bitmap->first_free; -} - -struct bitmap_next_free_data { - unsigned int level; - unsigned long offset; - uint64_t bit; -}; - -static int bitmap_next_free_fn(struct bitmap_level *bl, unsigned long offset, - unsigned int bit, void *__data) -{ - struct bitmap_next_free_data *data = __data; - uint64_t mask = ~((1UL << ((data->bit & BLOCKS_PER_UNIT_MASK) + 1)) - 1); - - if (!(mask & bl->map[offset])) - return 0; - - if (bl->map[offset] != -1UL) { - data->level = bl->level; - data->offset = offset; - return 1; - } - - data->bit = (data->bit + BLOCKS_PER_UNIT - 1) / BLOCKS_PER_UNIT; - return 0; -} - -/* - * 'bit_nr' is already set. Find the next free bit after this one. - */ -uint64_t bitmap_next_free(struct bitmap *bitmap, uint64_t bit_nr) -{ - struct bitmap_next_free_data data = { .level = -1U, .bit = bit_nr, }; - - if (firstfree_valid(bitmap) && bit_nr < bitmap->first_free) - return bitmap->first_free; - - if (!bitmap_handler(bitmap, bit_nr, bitmap_next_free_fn, &data)) - return bitmap_first_free(bitmap); - - assert(data.level != -1U); - - return bitmap_find_first_free(bitmap, data.level, data.offset); -} diff --git a/lib/bitmap.h b/lib/bitmap.h deleted file mode 100644 index 41c0fd8a..00000000 --- a/lib/bitmap.h +++ /dev/null @@ -1,18 +0,0 @@ -#ifndef FIO_BITMAP_H -#define FIO_BITMAP_H - -#include - -struct bitmap; -struct bitmap *bitmap_new(unsigned long nr_bits); -void bitmap_free(struct bitmap *bm); - -void bitmap_clear(struct bitmap *bitmap, uint64_t bit_nr); -void bitmap_set(struct bitmap *bitmap, uint64_t bit_nr); -unsigned int bitmap_set_nr(struct bitmap *bitmap, uint64_t bit_nr, unsigned int nr_bits); -int bitmap_isset(struct bitmap *bitmap, uint64_t bit_nr); -uint64_t bitmap_first_free(struct bitmap *bitmap); -uint64_t bitmap_next_free(struct bitmap *bitmap, uint64_t bit_nr); -void bitmap_reset(struct bitmap *bitmap); - -#endif -- 2.25.1