On Thu, Nov 11, 2010 at 4:57 PM, Corentin Chary <corenti...@iksaif.net> wrote: > Add most used bitmap and bitops functions into bitmap.c and bitops.c. > Theses functions are mostly copied from Linux kernel source. > > Some of these functions are already redefined in the VNC server. Some > of them could be used for some block stuff. The yet yo be submitted > NUMA work also need bitmaps. > > Signed-off-by: Corentin Chary <corenti...@iksaif.net> > --- > Makefile.objs | 1 + > bitmap.c | 255 +++++++++++++++++++++++++++++++++++++++++++++++++++++ > bitmap.h | 222 ++++++++++++++++++++++++++++++++++++++++++++++ > bitops.c | 142 ++++++++++++++++++++++++++++++ > bitops.h | 272 > +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ > osdep.h | 4 + > 6 files changed, 896 insertions(+), 0 deletions(-) > create mode 100644 bitmap.c > create mode 100644 bitmap.h > create mode 100644 bitops.c > create mode 100644 bitops.h > > diff --git a/Makefile.objs b/Makefile.objs > index 3da959c..e9ee4a8 100644 > --- a/Makefile.objs > +++ b/Makefile.objs > @@ -92,6 +92,7 @@ common-obj-y += msmouse.o ps2.o > common-obj-y += qdev.o qdev-properties.o > common-obj-y += block-migration.o > common-obj-y += pflib.o > +common-obj-y += bitmap.c bitops.c > > common-obj-$(CONFIG_BRLAPI) += baum.o > common-obj-$(CONFIG_POSIX) += migration-exec.o migration-unix.o > migration-fd.o > diff --git a/bitmap.c b/bitmap.c > new file mode 100644 > index 0000000..eaafbea > --- /dev/null > +++ b/bitmap.c > @@ -0,0 +1,255 @@ > +/* > + * Bitmap Module > + * > + * Stolen from linux/src/lib/bitmap.c > + * > + * Copyright (C) 2010 Corentin Chary > + * > + * This source code is licensed under the GNU General Public License, > + * Version 2. > + */ > + > +#include "bitops.h" > +#include "bitmap.h" > + > +/* > + * bitmaps provide an array of bits, implemented using an an > + * array of unsigned longs. The number of valid bits in a > + * given bitmap does _not_ need to be an exact multiple of > + * BITS_PER_LONG. > + * > + * The possible unused bits in the last, partially used word > + * of a bitmap are 'don't care'. The implementation makes > + * no particular effort to keep them zero. It ensures that > + * their value will not affect the results of any operation. > + * The bitmap operations that return Boolean (bitmap_empty, > + * for example) or scalar (bitmap_weight, for example) results > + * carefully filter out these unused bits from impacting their > + * results. > + * > + * These operations actually hold to a slightly stronger rule: > + * if you don't input any bitmaps to these ops that have some > + * unused bits set, then they won't output any set unused bits > + * in output bitmaps. > + * > + * The byte ordering of bitmaps is more natural on little > + * endian architectures. > + */ > + > +int __bitmap_empty(const unsigned long *bitmap, int bits)
Please don't use identifiers starting with underscore. > +{ > + int k, lim = bits/BITS_PER_LONG; > + > + for (k = 0; k < lim; ++k) { > + if (bitmap[k]) { > + return 0; > + } > + } > + if (bits % BITS_PER_LONG) { > + if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) { > + return 0; > + } > + } > + > + return 1; > +} > + > +int __bitmap_full(const unsigned long *bitmap, int bits) > +{ > + int k, lim = bits/BITS_PER_LONG; > + > + for (k = 0; k < lim; ++k) { > + if (~bitmap[k]) { > + return 0; > + } > + } > + > + if (bits % BITS_PER_LONG) { > + if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) { > + return 0; > + } > + } > + > + return 1; > +} > + > +int __bitmap_equal(const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits) > +{ > + int k, lim = bits/BITS_PER_LONG; > + > + for (k = 0; k < lim; ++k) { > + if (bitmap1[k] != bitmap2[k]) { > + return 0; > + } > + } > + > + if (bits % BITS_PER_LONG) { > + if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) { > + return 0; > + } > + } > + > + return 1; > +} > + > +void __bitmap_complement(unsigned long *dst, const unsigned long *src, int > bits) > +{ > + int k, lim = bits/BITS_PER_LONG; > + > + for (k = 0; k < lim; ++k) { > + dst[k] = ~src[k]; > + } > + > + if (bits % BITS_PER_LONG) { > + dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits); > + } > +} > + > +int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits) > +{ > + int k; > + int nr = BITS_TO_LONGS(bits); > + unsigned long result = 0; > + > + for (k = 0; k < nr; k++) { > + result |= (dst[k] = bitmap1[k] & bitmap2[k]); > + } > + return result != 0; > +} > + > +void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits) > +{ > + int k; > + int nr = BITS_TO_LONGS(bits); > + > + for (k = 0; k < nr; k++) { > + dst[k] = bitmap1[k] | bitmap2[k]; > + } > +} > + > +void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits) > +{ > + int k; > + int nr = BITS_TO_LONGS(bits); > + > + for (k = 0; k < nr; k++) { > + dst[k] = bitmap1[k] ^ bitmap2[k]; > + } > +} > + > +int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits) > +{ > + int k; > + int nr = BITS_TO_LONGS(bits); > + unsigned long result = 0; > + > + for (k = 0; k < nr; k++) { > + result |= (dst[k] = bitmap1[k] & ~bitmap2[k]); > + } > + return result != 0; > +} > + > +#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG)) > + > +void bitmap_set(unsigned long *map, int start, int nr) > +{ > + unsigned long *p = map + BIT_WORD(start); > + const int size = start + nr; > + int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); > + unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); > + > + while (nr - bits_to_set >= 0) { > + *p |= mask_to_set; > + nr -= bits_to_set; > + bits_to_set = BITS_PER_LONG; > + mask_to_set = ~0UL; > + p++; > + } > + if (nr) { > + mask_to_set &= BITMAP_LAST_WORD_MASK(size); > + *p |= mask_to_set; > + } > +} > + > +void bitmap_clear(unsigned long *map, int start, int nr) > +{ > + unsigned long *p = map + BIT_WORD(start); > + const int size = start + nr; > + int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); > + unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); > + > + while (nr - bits_to_clear >= 0) { > + *p &= ~mask_to_clear; > + nr -= bits_to_clear; > + bits_to_clear = BITS_PER_LONG; > + mask_to_clear = ~0UL; > + p++; > + } > + if (nr) { > + mask_to_clear &= BITMAP_LAST_WORD_MASK(size); > + *p &= ~mask_to_clear; > + } > +} > + > +#define __ALIGN_MASK(x,mask) (((x)+(mask))&~(mask)) > + > +/** > + * bitmap_find_next_zero_area - find a contiguous aligned zero area > + * @map: The address to base the search on > + * @size: The bitmap size in bits > + * @start: The bitnumber to start searching at > + * @nr: The number of zeroed bits we're looking for > + * @align_mask: Alignment mask for zero area > + * > + * The @align_mask should be one less than a power of 2; the effect is that > + * the bit offset of all zero areas this function finds is multiples of that > + * power of 2. A @align_mask of 0 means no alignment is required. > + */ > +unsigned long bitmap_find_next_zero_area(unsigned long *map, > + unsigned long size, > + unsigned long start, > + unsigned int nr, > + unsigned long align_mask) > +{ > + unsigned long index, end, i; > +again: > + index = find_next_zero_bit(map, size, start); > + > + /* Align allocation */ > + index = __ALIGN_MASK(index, align_mask); > + > + end = index + nr; > + if (end > size) { > + return end; > + } > + i = find_next_bit(map, end, index); > + if (i < end) { > + start = i + 1; > + goto again; > + } > + return index; > +} > + > +int __bitmap_intersects(const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits) > +{ > + int k, lim = bits/BITS_PER_LONG; > + > + for (k = 0; k < lim; ++k) { > + if (bitmap1[k] & bitmap2[k]) { > + return 1; > + } > + } > + > + if (bits % BITS_PER_LONG) { > + if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) { > + return 1; > + } > + } > + return 0; > +} > diff --git a/bitmap.h b/bitmap.h > new file mode 100644 > index 0000000..a8280b0 > --- /dev/null > +++ b/bitmap.h > @@ -0,0 +1,222 @@ > +/* > + * Bitmap Module > + * > + * Copyright (C) 2010 Corentin Chary <corentin.ch...@gmail.com> > + * > + * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h > + * > + * This work is licensed under the terms of the GNU LGPL, version 2.1 or > later. > + * See the COPYING.LIB file in the top-level directory. > + */ > + > +#ifndef BITMAP_H > +#define BITMAP_H > + > +#include "qemu-common.h" > +#include "bitops.h" > + > +/* > + * The available bitmap operations and their rough meaning in the > + * case that the bitmap is a single unsigned long are thus: > + * > + * Note that nbits should be always a compile time evaluable constant. > + * Otherwise many inlines will generate horrible code. > + * > + * bitmap_zero(dst, nbits) *dst = 0UL > + * bitmap_fill(dst, nbits) *dst = ~0UL > + * bitmap_copy(dst, src, nbits) *dst = *src > + * bitmap_and(dst, src1, src2, nbits) *dst = *src1 & *src2 > + * bitmap_or(dst, src1, src2, nbits) *dst = *src1 | *src2 > + * bitmap_xor(dst, src1, src2, nbits) *dst = *src1 ^ *src2 > + * bitmap_andnot(dst, src1, src2, nbits) *dst = *src1 & ~(*src2) > + * bitmap_complement(dst, src, nbits) *dst = ~(*src) > + * bitmap_equal(src1, src2, nbits) Are *src1 and *src2 equal? > + * bitmap_intersects(src1, src2, nbits) Do *src1 and *src2 overlap? > + * bitmap_empty(src, nbits) Are all bits zero in *src? > + * bitmap_full(src, nbits) Are all bits set in *src? > + * bitmap_set(dst, pos, nbits) Set specified bit area > + * bitmap_clear(dst, pos, nbits) Clear specified bit area > + * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area > + */ > + > +/* > + * Also the following operations apply to bitmaps. > + * > + * set_bit(bit, addr) *addr |= bit > + * clear_bit(bit, addr) *addr &= ~bit > + * change_bit(bit, addr) *addr ^= bit > + * test_bit(bit, addr) Is bit set in *addr? > + * test_and_set_bit(bit, addr) Set bit and return old value > + * test_and_clear_bit(bit, addr) Clear bit and return old value > + * test_and_change_bit(bit, addr) Change bit and return old value > + * find_first_zero_bit(addr, nbits) Position first zero bit in *addr > + * find_first_bit(addr, nbits) Position first set bit in *addr > + * find_next_zero_bit(addr, nbits, bit) Position next zero bit in > *addr >= bit > + * find_next_bit(addr, nbits, bit) Position next set bit in *addr >= bit > + */ > + > +#define BITMAP_LAST_WORD_MASK(nbits) \ > + ( \ > + ((nbits) % BITS_PER_LONG) ? \ > + (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL \ > + ) > + > +#define DECLARE_BITMAP(name,bits) \ > + unsigned long name[BITS_TO_LONGS(bits)] > + > +#define small_nbits(nbits) \ > + ((nbits) <= BITS_PER_LONG) > + > +int __bitmap_empty(const unsigned long *bitmap, int bits); > +int __bitmap_full(const unsigned long *bitmap, int bits); > +int __bitmap_equal(const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits); > +void __bitmap_complement(unsigned long *dst, const unsigned long *src, > + int bits); > +void __bitmap_shift_right(unsigned long *dst, > + const unsigned long *src, int shift, int bits); > +void __bitmap_shift_left(unsigned long *dst, > + const unsigned long *src, int shift, int bits); > +int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits); > +void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits); > +void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits); > +int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits); > +int __bitmap_intersects(const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits); > + > +static inline unsigned long *bitmap_new(int nbits) > +{ > + int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); > + return qemu_mallocz(len); > +} > + > +static inline void bitmap_zero(unsigned long *dst, int nbits) > +{ > + if (small_nbits(nbits)) { > + *dst = 0UL; > + } else { > + int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); > + memset(dst, 0, len); > + } > +} > + > +static inline void bitmap_fill(unsigned long *dst, int nbits) > +{ > + size_t nlongs = BITS_TO_LONGS(nbits); > + if (!small_nbits(nbits)) { > + int len = (nlongs - 1) * sizeof(unsigned long); > + memset(dst, 0xff, len); > + } > + dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits); > +} > + > +static inline void bitmap_copy(unsigned long *dst, const unsigned long *src, > + int nbits) > +{ > + if (small_nbits(nbits)) { > + *dst = *src; > + } else { > + int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); > + memcpy(dst, src, len); > + } > +} > + > +static inline int bitmap_and(unsigned long *dst, const unsigned long *src1, > + const unsigned long *src2, int nbits) > +{ > + if (small_nbits(nbits)) { > + return (*dst = *src1 & *src2) != 0; > + } > + return __bitmap_and(dst, src1, src2, nbits); > +} > + > +static inline void bitmap_or(unsigned long *dst, const unsigned long *src1, > + const unsigned long *src2, int nbits) > +{ > + if (small_nbits(nbits)) { > + *dst = *src1 | *src2; > + } else { > + __bitmap_or(dst, src1, src2, nbits); > + } > +} > + > +static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1, > + const unsigned long *src2, int nbits) > +{ > + if (small_nbits(nbits)) { > + *dst = *src1 ^ *src2; > + } else { > + __bitmap_xor(dst, src1, src2, nbits); > + } > +} > + > +static inline int bitmap_andnot(unsigned long *dst, const unsigned long > *src1, > + const unsigned long *src2, int nbits) > +{ > + if (small_nbits(nbits)) { > + return (*dst = *src1 & ~(*src2)) != 0; > + } > + return __bitmap_andnot(dst, src1, src2, nbits); > +} > + > +static inline void bitmap_complement(unsigned long *dst, const unsigned long > *src, > + int nbits) > +{ > + if (small_nbits(nbits)) { > + *dst = ~(*src) & BITMAP_LAST_WORD_MASK(nbits); > + } else { > + __bitmap_complement(dst, src, nbits); > + } > +} > + > +static inline int bitmap_equal(const unsigned long *src1, > + const unsigned long *src2, int nbits) > +{ > + if (small_nbits(nbits)) { > + return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits)); > + } else { > + return __bitmap_equal(src1, src2, nbits); > + } > +} > + > +static inline int bitmap_empty(const unsigned long *src, int nbits) > +{ > + if (small_nbits(nbits)) { > + return ! (*src & BITMAP_LAST_WORD_MASK(nbits)); > + } else { > + return __bitmap_empty(src, nbits); > + } > +} > + > +static inline int bitmap_full(const unsigned long *src, int nbits) > +{ > + if (small_nbits(nbits)) { > + return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits)); > + } else { > + return __bitmap_full(src, nbits); > + } > +} > + > +static inline int bitmap_intersects(const unsigned long *src1, > + const unsigned long *src2, int nbits) > +{ > + if (small_nbits(nbits)) { > + return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0; > + } else { > + return __bitmap_intersects(src1, src2, nbits); > + } > +} > + > +void bitmap_set(unsigned long *map, int i, int len); > +void bitmap_clear(unsigned long *map, int start, int nr); > +unsigned long bitmap_find_next_zero_area(unsigned long *map, > + unsigned long size, > + unsigned long start, > + unsigned int nr, > + unsigned long align_mask); > + > +#endif /* BITMAP_H */ > diff --git a/bitops.c b/bitops.c > new file mode 100644 > index 0000000..730739c > --- /dev/null > +++ b/bitops.c > @@ -0,0 +1,142 @@ > +/* > + * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. > + * Written by David Howells (dhowe...@redhat.com) > + * Copyright (C) 2008 IBM Corporation > + * Written by Rusty Russell <ru...@rustcorp.com.au> > + * (Inspired by David Howell's find_next_bit implementation) > + * > + * This program is free software; you can redistribute it and/or > + * modify it under the terms of the GNU General Public License > + * as published by the Free Software Foundation; either version > + * 2 of the License, or (at your option) any later version. > + */ > + > +#include "bitops.h" > + > +#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) > + > +/* > + * Find the next set bit in a memory region. > + */ > +unsigned long find_next_bit(const unsigned long *addr, unsigned long size, > + unsigned long offset) > +{ > + const unsigned long *p = addr + BITOP_WORD(offset); > + unsigned long result = offset & ~(BITS_PER_LONG-1); > + unsigned long tmp; > + > + if (offset >= size) { > + return size; > + } > + size -= result; > + offset %= BITS_PER_LONG; > + if (offset) { > + tmp = *(p++); > + tmp &= (~0UL << offset); > + if (size < BITS_PER_LONG) { > + goto found_first; > + } > + if (tmp) { > + goto found_middle; > + } > + size -= BITS_PER_LONG; > + result += BITS_PER_LONG; > + } > + while (size & ~(BITS_PER_LONG-1)) { > + if ((tmp = *(p++))) { > + goto found_middle; > + } > + result += BITS_PER_LONG; > + size -= BITS_PER_LONG; > + } > + if (!size) { > + return result; > + } > + tmp = *p; > + > +found_first: > + tmp &= (~0UL >> (BITS_PER_LONG - size)); > + if (tmp == 0UL) { /* Are any bits set? */ > + return result + size; /* Nope. */ > + } > +found_middle: > + return result + __ffs(tmp); > +} > + > +/* > + * This implementation of find_{first,next}_zero_bit was stolen from > + * Linus' asm-alpha/bitops.h. > + */ > +unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long > size, > + unsigned long offset) > +{ > + const unsigned long *p = addr + BITOP_WORD(offset); > + unsigned long result = offset & ~(BITS_PER_LONG-1); > + unsigned long tmp; > + > + if (offset >= size) { > + return size; > + } > + size -= result; > + offset %= BITS_PER_LONG; > + if (offset) { > + tmp = *(p++); > + tmp |= ~0UL >> (BITS_PER_LONG - offset); > + if (size < BITS_PER_LONG) { > + goto found_first; > + } > + if (~tmp) { > + goto found_middle; > + } > + size -= BITS_PER_LONG; > + result += BITS_PER_LONG; > + } > + while (size & ~(BITS_PER_LONG-1)) { > + if (~(tmp = *(p++))) { > + goto found_middle; > + } > + result += BITS_PER_LONG; > + size -= BITS_PER_LONG; > + } > + if (!size) { > + return result; > + } > + tmp = *p; > + > +found_first: > + tmp |= ~0UL << size; > + if (tmp == ~0UL) { /* Are any bits zero? */ > + return result + size; /* Nope. */ > + } > +found_middle: > + return result + ffz(tmp); > +} > + > +unsigned long find_last_bit(const unsigned long *addr, unsigned long size) > +{ > + unsigned long words; > + unsigned long tmp; > + > + /* Start at final word. */ > + words = size / BITS_PER_LONG; > + > + /* Partial final word? */ > + if (size & (BITS_PER_LONG-1)) { > + tmp = (addr[words] & (~0UL >> (BITS_PER_LONG > + - (size & (BITS_PER_LONG-1))))); > + if (tmp) { > + goto found; > + } > + } > + > + while (words) { > + tmp = addr[--words]; > + if (tmp) { > + found: > + return words * BITS_PER_LONG + __fls(tmp); > + } > + } > + > + /* Not found */ > + return size; > +} > diff --git a/bitops.h b/bitops.h > new file mode 100644 > index 0000000..dcd3da9 > --- /dev/null > +++ b/bitops.h > @@ -0,0 +1,272 @@ > +/* > + * Bitops Module > + * > + * Copyright (C) 2010 Corentin Chary <corentin.ch...@gmail.com> > + * > + * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h > + * > + * This work is licensed under the terms of the GNU LGPL, version 2.1 or > later. > + * See the COPYING.LIB file in the top-level directory. > + */ > + > +#ifndef BITOPS_H > +#define BITOPS_H > + > +#include "qemu-common.h" > + > +#define BITS_PER_BYTE CHAR_BIT > +#define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE) > + > +#define BIT(nr) (1UL << (nr)) > +#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) > +#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) > +#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) > + > +/** > + * __ffs - find first bit in word. > + * @word: The word to search > + * > + * Undefined if no bit exists, so code should check against 0 first. > + */ > +static unsigned long __ffs(unsigned long word) We already have ffs() in qemu-common.h and oslib-win32.c. Please use the same method.