Re: [Qemu-devel] [2.4 PATCH v3 16/19] hbitmap: truncate tests

[Max Reitz <mreitz@redhat.com>]

On 2015-03-13 at 14:30, John Snow wrote:
> The general approach is to set bits close to the boundaries of
> where we are truncating and ensure that everything appears to
> have gone OK.
>
> We test growing and shrinking by different amounts:
> - Less than the granularity
> - Less than the granularity, but across a boundary
> - Less than sizeof(unsigned long)
> - Less than sizeof(unsigned long), but across a ulong boundary
> - More than sizeof(unsigned long)
>
> Signed-off-by: John Snow <jsnow@redhat.com>
> ---
>   tests/test-hbitmap.c | 247 +++++++++++++++++++++++++++++++++++++++++++++++++++
>   1 file changed, 247 insertions(+)
>
> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
> index 8c902f2..65401ab 100644
> --- a/tests/test-hbitmap.c
> +++ b/tests/test-hbitmap.c
> @@ -11,6 +11,8 @@
>   
>   #include <glib.h>
>   #include <stdarg.h>
> +#include <string.h>
> +#include <sys/types.h>
>   #include "qemu/hbitmap.h"
>   
>   #define LOG_BITS_PER_LONG          (BITS_PER_LONG == 32 ? 5 : 6)
> @@ -23,6 +25,7 @@ typedef struct TestHBitmapData {
>       HBitmap       *hb;
>       unsigned long *bits;
>       size_t         size;
> +    size_t         old_size;
>       int            granularity;
>   } TestHBitmapData;
>   
> @@ -91,6 +94,44 @@ static void hbitmap_test_init(TestHBitmapData *data,
>       }
>   }
>   
> +static inline size_t hbitmap_test_array_size(size_t bits)
> +{
> +    size_t n = (bits + BITS_PER_LONG - 1) / BITS_PER_LONG;
> +    return n ? n : 1;
> +}
> +
> +static void hbitmap_test_truncate_impl(TestHBitmapData *data,
> +                                       size_t size)
> +{
> +    size_t n;
> +    size_t m;
> +    data->old_size = data->size;
> +    data->size = size;
> +
> +    if (data->size == data->old_size) {
> +        return;
> +    }
> +
> +    n = hbitmap_test_array_size(size);
> +    m = hbitmap_test_array_size(data->old_size);
> +    data->bits = g_realloc(data->bits, sizeof(unsigned long) * n);
> +    if (n > m) {
> +        memset(&data->bits[m], 0x00, sizeof(unsigned long) * (n - m));
> +    }
> +
> +    /* If we shrink to an uneven multiple of sizeof(unsigned long),
> +     * scrub the leftover memory. */
> +    if (data->size < data->old_size) {
> +        m = size % (sizeof(unsigned long) * 8);
> +        if (m) {
> +            unsigned long mask = (1ULL << m) - 1;
> +            data->bits[n-1] &= mask;
> +        }
> +    }
> +
> +    hbitmap_truncate(data->hb, size);
> +}
> +
>   static void hbitmap_test_teardown(TestHBitmapData *data,
>                                     const void *unused)
>   {
> @@ -369,6 +410,190 @@ static void test_hbitmap_iter_granularity(TestHBitmapData *data,
>       g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
>   }
>   
> +static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
> +{
> +    size_t size = data->size;
> +
> +    /* First bit */
> +    hbitmap_test_set(data, 0, 1);
> +    if (diff < 0) {
> +        /* Last bit in new, shortened map */
> +        hbitmap_test_set(data, size + diff - 1, 1);
> +
> +        /* First bit to be truncated away */
> +        hbitmap_test_set(data, size + diff, 1);
> +    }
> +    /* Last bit */
> +    hbitmap_test_set(data, size - 1, 1);
> +    if (data->granularity == 0) {
> +        hbitmap_test_check_get(data);
> +    }
> +}
> +
> +static void hbitmap_test_check_boundary_bits(TestHBitmapData *data)
> +{
> +    size_t size = MIN(data->size, data->old_size);
> +
> +    if (data->granularity == 0) {
> +        hbitmap_test_check_get(data);
> +        hbitmap_test_check(data, 0);
> +    } else {
> +        g_assert(hbitmap_get(data->hb, 0));
> +        g_assert(hbitmap_get(data->hb, size - 1));
> +        g_assert_cmpint(2 << data->granularity, ==, hbitmap_count(data->hb));

Hm, where does this come from?

> +    }
> +}
> +
> +/* Generic truncate test. */
> +static void hbitmap_test_truncate(TestHBitmapData *data,
> +                                  size_t size,
> +                                  ssize_t diff,
> +                                  int granularity)
> +{
> +    hbitmap_test_init(data, size, granularity);
> +    hbitmap_test_set_boundary_bits(data, diff);
> +    hbitmap_test_truncate_impl(data, size + diff);
> +    hbitmap_test_check_boundary_bits(data);
> +}
> +
> +static void test_hbitmap_truncate_nop(TestHBitmapData *data,
> +                                      const void *unused)
> +{
> +    hbitmap_test_truncate(data, L2, 0, 0);
> +}
> +
> +/**
> + * Grow by an amount smaller than the granularity, without crossing
> + * a granularity alignment boundary. Effectively a NOP.
> + */
> +static void test_hbitmap_truncate_grow_negligible(TestHBitmapData *data,
> +                                                  const void *unused)
> +{
> +    size_t size = L2 - 1;
> +    size_t diff = 1;
> +    int granularity = 1;
> +
> +    hbitmap_test_truncate(data, size, diff, granularity);
> +}
> +
> +/**
> + * Shrink by an amount smaller than the granularity, without crossing
> + * a granularity alignment boundary. Effectively a NOP.
> + */
> +static void test_hbitmap_truncate_shrink_negligible(TestHBitmapData *data,
> +                                                    const void *unused)
> +{
> +    size_t size = L2;
> +    ssize_t diff = -1;
> +    int granularity = 1;
> +
> +    hbitmap_test_truncate(data, size, diff, granularity);
> +}
> +
> +/**
> + * Grow by an amount smaller than the granularity, but crossing over
> + * a granularity alignment boundary.
> + */
> +static void test_hbitmap_truncate_grow_tiny(TestHBitmapData *data,
> +                                            const void *unused)
> +{
> +    size_t size = L2 - 2;
> +    ssize_t diff = 1;
> +    int granularity = 1;
> +
> +    hbitmap_test_truncate(data, size, diff, granularity);
> +}
> +
> +/**
> + * Shrink by an amount smaller than the granularity, but crossing over
> + * a granularity alignment boundary.
> + */
> +static void test_hbitmap_truncate_shrink_tiny(TestHBitmapData *data,
> +                                              const void *unused)
> +{
> +    size_t size = L2 - 1;
> +    ssize_t diff = -1;
> +    int granularity = 1;
> +
> +    hbitmap_test_truncate(data, size, diff, granularity);
> +}
> +
> +/**
> + * Grow by an amount smaller than sizeof(long), and not crossing over
> + * a sizeof(long) alignment boundary.
> + */
> +static void test_hbitmap_truncate_grow_small(TestHBitmapData *data,
> +                                             const void *unused)
> +{
> +    size_t size = L2 + 1;
> +    size_t diff = sizeof(long) / 2;
> +
> +    hbitmap_test_truncate(data, size, diff, 0);
> +}
> +
> +/**
> + * Shrink by an amount smaller than sizeof(long), and not crossing over
> + * a sizeof(long) alignment boundary.
> + */
> +static void test_hbitmap_truncate_shrink_small(TestHBitmapData *data,
> +                                               const void *unused)
> +{
> +    size_t size = L2;
> +    size_t diff = sizeof(long) / 2;
> +
> +    hbitmap_test_truncate(data, size, -diff, 0);
> +}
> +
> +/**
> + * Grow by an amount smaller than sizeof(long), while crossing over
> + * a sizeof(long) alignment boundary.
> + */
> +static void test_hbitmap_truncate_grow_medium(TestHBitmapData *data,
> +                                              const void *unused)
> +{
> +    size_t size = L2 - 1;
> +    size_t diff = sizeof(long) / 2;
> +
> +    hbitmap_test_truncate(data, size, diff, 0);
> +}
> +
> +/**
> + * Shrink by an amount smaller than sizeof(long), while crossing over
> + * a sizeof(long) alignment boundary.
> + */
> +static void test_hbitmap_truncate_shrink_medium(TestHBitmapData *data,
> +                                                const void *unused)
> +{
> +    size_t size = L2 + 1;
> +    size_t diff = sizeof(long) / 2;
> +
> +    hbitmap_test_truncate(data, size, -diff, 0);
> +}
> +
> +/**
> + * Grow by an amount larger than sizeof(long).
> + */
> +static void test_hbitmap_truncate_grow_large(TestHBitmapData *data,
> +                                             const void *unused)
> +{
> +    size_t size = L2;
> +    size_t diff = 8 * sizeof(long);

You can use L1 here. But you don't have to. Do as you please. (just saying)

Max

> +
> +    hbitmap_test_truncate(data, size, diff, 0);
> +}
> +
> +/**
> + * Shrink by an amount larger than sizeof(long).
> + */
> +static void test_hbitmap_truncate_shrink_large(TestHBitmapData *data,
> +                                               const void *unused)
> +{
> +    size_t size = L2;
> +    size_t diff = 8 * sizeof(long);
> +
> +    hbitmap_test_truncate(data, size, -diff, 0);
> +}
> +
>   static void hbitmap_test_add(const char *testpath,
>                                      void (*test_func)(TestHBitmapData *data, const void *user_data))
>   {
> @@ -395,6 +620,28 @@ int main(int argc, char **argv)
>       hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
>       hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
>       hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
> +
> +    hbitmap_test_add("/hbitmap/truncate/nop", test_hbitmap_truncate_nop);
> +    hbitmap_test_add("/hbitmap/truncate/grow/negligible",
> +                     test_hbitmap_truncate_grow_negligible);
> +    hbitmap_test_add("/hbitmap/truncate/shrink/negligible",
> +                     test_hbitmap_truncate_shrink_negligible);
> +    hbitmap_test_add("/hbitmap/truncate/grow/tiny",
> +                     test_hbitmap_truncate_grow_tiny);
> +    hbitmap_test_add("/hbitmap/truncate/shrink/tiny",
> +                     test_hbitmap_truncate_shrink_tiny);
> +    hbitmap_test_add("/hbitmap/truncate/grow/small",
> +                     test_hbitmap_truncate_grow_small);
> +    hbitmap_test_add("/hbitmap/truncate/shrink/small",
> +                     test_hbitmap_truncate_shrink_small);
> +    hbitmap_test_add("/hbitmap/truncate/grow/medium",
> +                     test_hbitmap_truncate_grow_medium);
> +    hbitmap_test_add("/hbitmap/truncate/shrink/medium",
> +                     test_hbitmap_truncate_shrink_medium);
> +    hbitmap_test_add("/hbitmap/truncate/grow/large",
> +                     test_hbitmap_truncate_grow_large);
> +    hbitmap_test_add("/hbitmap/truncate/shrink/large",
> +                     test_hbitmap_truncate_shrink_large);
>       g_test_run();
>   
>       return 0;