Re: [PATCH v1 1/8] New functions for virBitmap

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On 08/30/2012 02:55 AM, Hu Tao wrote:
> In many places we store bitmap info in a chunk of data
> (pointed to by a char *), and have redundant codes to
> set/unset bits. This patch extends virBitmap, and convert
> those codes to use virBitmap in subsquent patches.

s/subsquent/subsequent/

The overall series sounds nice.  There was no cover letter (0/8) to the
series, so it's a bit harder to track the overall diffstat, although it
looks like you have a net reduction of lines based on previewing
individual patches later in the series - always a nice result.  And
having nice interfaces here means that later patches should still apply
even if I make you change the internals of this patch.  Overall, I think
we can get this series into shape for 0.10.2.

> ---
>  .gitignore               |    1 +
>  src/libvirt_private.syms |   10 ++
>  src/util/bitmap.c        |  391 +++++++++++++++++++++++++++++++++++++++++++++-
>  src/util/bitmap.h        |   23 +++
>  tests/Makefile.am        |    8 +-
>  tests/virbitmaptest.c    |  134 ++++++++++++++++
>  6 files changed, 562 insertions(+), 5 deletions(-)
>  create mode 100644 tests/virbitmaptest.c
> 
> diff --git a/.gitignore b/.gitignore
> index 5041ddf..9aaa1f5 100644
> --- a/.gitignore
> +++ b/.gitignore
> @@ -155,6 +155,7 @@
>  /tests/storagebackendsheepdogtest
>  /tests/utiltest
>  /tests/viratomictest
> +/tests/virbitmaptest
>  /tests/virauthconfigtest

Needs to be sorted, otherwise the next person running ./autogen.sh on a
fresh checkout will have a spurious difference.

> +++ b/src/util/bitmap.c
> @@ -33,15 +33,17 @@
>  #include "bitmap.h"
>  #include "memory.h"
>  #include "buf.h"
> +#include "util.h"
> +#include "c-ctype.h"
>  
>  
>  struct _virBitmap {
>      size_t size;
> -    unsigned long *map;
> +    unsigned char *map;

NACK to this hunk; iterating over longs is more efficient than iterating
over char.  It means the conversion from a char* data will have to be a
bit more involved, but that's life.

>  };
>  
>  
> -#define VIR_BITMAP_BITS_PER_UNIT  ((int) sizeof(unsigned long) * CHAR_BIT)
> +#define VIR_BITMAP_BITS_PER_UNIT  ((int) sizeof(unsigned char) * CHAR_BIT)

sizeof(unsigned char) == 1, by definition; I always question use of code
like this (and if you follow my earlier comment of keeping things with
long* rather than char*, then my objection on this hunk becomes irrelevant).

>  
> +/* Helper function. caller must ensure b < bitmap->size */
> +static bool bitmapIsset(virBitmapPtr bitmap, size_t b)

s/bitmapIsset/virBitmapIsSet/ - we want to use consistent naming, even
for static functions.


> @@ -168,7 +176,7 @@ char *virBitmapString(virBitmapPtr bitmap)
>            VIR_BITMAP_BITS_PER_UNIT;
>  
>      while (sz--) {
> -        virBufferAsprintf(&buf, "%0*lx",
> +        virBufferAsprintf(&buf, "%0*hx",

char* would be hhx, not hx (but again, I want to keep this at lx).

> +/**
> + * virBitmapFormat:
> + * @bitmap: the bitmap
> + *
> + * This function is the counterpart of virBitmapParse. This function creates
> + * a human-readable string representing the bits in bitmap.
> + *
> + * See virBitmapParse for the format of @str.
> + *
> + * Returns the string on success or NULL otherwise. Caller should call
> + * VIR_FREE to free the string.
> + */
> +char *virBitmapFormat(virBitmapPtr bitmap)
> +{
> +    virBuffer buf =VIR_BUFFER_INITIALIZER;

space after =

> +/**
> + * virBitmapParse:
> + * @str: points to a string representing a human-readable bitmap
> + * @bitmap: a bitmap created from @str
> + * @bitmapSize: the upper limit of num of bits in created bitmap
> + *
> + * This function is the counterpart of virBitmapFormat. This function creates
> + * a bitmap, in which bits are set according to the content of @str.
> + *
> + * @str is a comma separated string of fields N, which means a number of bit
> + * to set, and ^N, which means to unset the bit, and N-M for ranges of bits
> + * to set.
> + *
> + * Returns the number of bits set in @bitmap, or -1 in case of error.
> + */
> +
> +int virBitmapParse(const char *str,
> +                   char sep,
> +                   virBitmapPtr *bitmap,
> +                   size_t bitmapSize)
> +{
> +    int ret = 0;
> +    int neg = 0;

s/int/bool/; s/0/false/ for all uses of neg in this function

> +/**
> + * virBitmapAllocFromData:
> + * @data: the data
> + * @len: len of @data in byte

length of @data in bytes

> + *
> + * Allocate a bitmap from a chunk of data containing bits
> + * information
> + *
> + * Returns a pointer to the allocated bitmap or NULL if
> + * memory cannot be allocated.
> + */
> +virBitmapPtr virBitmapAllocFromData(void *data, int len)
> +{
> +    virBitmapPtr bitmap;
> +
> +    bitmap = virBitmapAlloc(len * CHAR_BIT);
> +    if (!bitmap)
> +        return NULL;
> +
> +    memcpy(bitmap->map, data, len);

Here's where you need to do some work to keep virBitmap using longs.

> +/**
> + * virBitmapToData:
> + * @data: the data
> + * @len: len of @data in byte
> + *
> + * Convert a bitmap to a chunk of data containing bits information.
> + * Data consists of sequential bytes, with lower bytes containing
> + * lower bits.
> + *
> + * Returns 0 on success, -1 otherwise.
> + */
> +int virBitmapToData(virBitmapPtr bitmap, char **data, int *dataLen)
> +{
> +    size_t sz;
> +
> +    sz = (bitmap->size + VIR_BITMAP_BITS_PER_UNIT - 1) /
> +         VIR_BITMAP_BITS_PER_UNIT;

Hmm; we seem to be recomputing this in a lot of code; maybe it's better
to compute it once at virBitmap creation and make the struct one member
larger.

> +
> +    if (VIR_ALLOC_N(*data, sz) < 0)
> +        return -1;
> +
> +    memcpy(*data, bitmap->map, sz);

And another conversion needed, this time from long to char.

> +/**
> + * virBitmapCmp:
> + * @b1: bitmap 1
> + * @b2: bitmap 2
> + *
> + * Compares two bitmaps. Returns true if two bitmaps have exactly
> + * the same set of bits set, otherwise false.

Mention specifically that this works even for maps of different lengths,
if the longer map has a 0 tail.

> + */
> +bool virBitmapCmp(virBitmapPtr b1, virBitmapPtr b2)
> +{
> +    virBitmapPtr b;
> +    size_t sz1, sz2, sz;
> +    int i;
> +
> +    sz1 = (b1->size + VIR_BITMAP_BITS_PER_UNIT - 1) /
> +         VIR_BITMAP_BITS_PER_UNIT;
> +    sz2 = (b2->size + VIR_BITMAP_BITS_PER_UNIT - 1) /
> +         VIR_BITMAP_BITS_PER_UNIT;
> +
> +    sz = sz1 < sz2 ? sz1 : sz2;
> +
> +    for (i = 0; i < sz; i++) {
> +        if (b1->map[i] != b2->map[i])
> +            return false;
> +    }
> +
> +    b = sz1 > sz ? b1 : b2;
> +    sz = sz1 > sz ? sz1 : sz2;

Rather than computing 'sz1 > sz ?:' three times, why not:

if (b1->size > b2->size) {
  virBitmapPtr tmp = b1;
  b1 = b2;
  b2 = b1;
}

up front, prior to computing sz1 and sz2, at which point you know that
sz1 <= sz2 for the rest of the function.

> +/**
> + * virBitmapSetAll:
> + * @bitmap: the bitmap
> + *
> + * set all bits in @bitmap.
> + */
> +void virBitmapSetAll(virBitmapPtr bitmap)
> +{

Do we _also_ want virBitmapSetRange(virBitmapPtr bitmap, size_t start,
size_t len), for setting a portion of the map?

> 
> +    for (i = 0; i < sz; i++)
> +        bitmap->map[i] = -1;

Why not memset()?

> +/**
> + * virBitmapClearAll:
> + * @bitmap: the bitmap
> + *
> + * clear all bits in @bitmap.

Similarly for virBitmapClearRange(virBitmapPtr bitmap, size_t start,
size_t len).

> + */
> +void virBitmapClearAll(virBitmapPtr bitmap)
> +{
> +    int i;
> +    size_t sz;
> +
> +    sz = (bitmap->size + VIR_BITMAP_BITS_PER_UNIT - 1) /
> +         VIR_BITMAP_BITS_PER_UNIT;
> +
> +    for (i = 0; i < sz; i++)
> +        bitmap->map[i] = 0;

Again, memset().

> + * virBitmapIsAllSet:
> + * @bitmap: the bitmap to check
> + *
> + * check if all bits in @bitmap are set.
> + */
> +bool virBitmapIsAllSet(virBitmapPtr bitmap)
> +{
> +    int i;
> +    int unusedBits;
> +    size_t sz, tmp;
> +
> +    sz = (bitmap->size + VIR_BITMAP_BITS_PER_UNIT - 1) /
> +         VIR_BITMAP_BITS_PER_UNIT;
> +    unusedBits = sz * VIR_BITMAP_BITS_PER_UNIT - bitmap->size;
> +
> +    tmp = sz;
> +    if (unusedBits > 0)
> +        tmp = sz - 1;
> +
> +    for (i = 0; i < tmp; i++)
> +        if (bitmap->map[i] != (unsigned char)-1)

Unnecessary cast (especially if you keep the code with long).

> +            return false;
> +
> +    if (unusedBits > 0) {
> +        if ((bitmap->map[sz - 1] & ((1 << (VIR_BITMAP_BITS_PER_UNIT - unusedBits + 1)) - 1))

s/1 <</1U <</ - need to use unsigned math to guarantee defined results.

> +++ b/src/util/bitmap.h
> @@ -62,4 +62,27 @@ int virBitmapGetBit(virBitmapPtr bitmap, size_t b, bool *result)
>  char *virBitmapString(virBitmapPtr bitmap)
>      ATTRIBUTE_NONNULL(1) ATTRIBUTE_RETURN_CHECK;
>  
> +char *virBitmapFormat(virBitmapPtr bitmap);

Quite a few of these need ATTRIBUTE_NONNULL() markings.

> +++ b/tests/Makefile.am
> @@ -92,7 +92,8 @@ test_programs = virshtest sockettest \
>  	viratomictest \
>  	utiltest virnettlscontexttest shunloadtest \
>  	virtimetest viruritest virkeyfiletest \
> -	virauthconfigtest
> +	virauthconfigtest \
> +        virbitmaptest

Spacing is off; Makefiles use TAB.

> @@ -592,6 +597,7 @@ shunloadtest_SOURCES = \
>  shunloadtest_LDADD = $(LIB_PTHREAD)
>  shunloadtest_DEPENDENCIES = libshunload.la
>  
> +
>  if WITH_CIL

Spurious whitespace change.

> +++ b/tests/virbitmaptest.c

> +bool testBit(virBitmapPtr bitmap, unsigned int start, unsigned int end)

Too weak - you are using this to check that all bits in a range have a
given value, but for that to work, you need to know what the desired
value is as a fourth parameter.

> +    if (!testBit(bitmap, 1021, 1023))
> +        goto error;
> +
> +    if (testBit(bitmap, 0, 0))
> +        goto error;
> +    if (testBit(bitmap, 33,49))
> +        goto error;

That is, in these uses, you really want:

if (testBits(bitmap, 1021, 1023, true) < 0 ||
    testBits(bitmap, 33, 49, false) < 0)
    goto error;

-- 
Eric Blake   eblake@xxxxxxxxxx    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

Attachment: signature.asc
Description: OpenPGP digital signature

--
libvir-list mailing list
libvir-list@xxxxxxxxxx
https://www.redhat.com/mailman/listinfo/libvir-list

[Index of Archives]     [Virt Tools]     [Libvirt Users]     [Lib OS Info]     [Fedora Users]     [Fedora Desktop]     [Fedora SELinux]     [Big List of Linux Books]     [Yosemite News]     [KDE Users]     [Fedora Tools]