Re: [Qemu-devel] [PATCH v2 11/15] bitmap: add a generic bitmap and bitops library

[Blue Swirl]

On Thu, Nov 11, 2010 at 4:57 PM, Corentin Chary <address@hidden> 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 <address@hidden>
> ---
>  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 <address@hidden>
> + *
> + * 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 (address@hidden)
> + * Copyright (C) 2008 IBM Corporation
> + * Written by Rusty Russell <address@hidden>
> + * (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 <address@hidden>
> + *
> + * 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.