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

[Max Reitz <mreitz@redhat.com>]

On 2015-03-17 at 13:21, John Snow wrote:
>
>
> On 03/17/2015 10:53 AM, Max Reitz wrote:
>> 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?
>>
>
> I assume you are referring to specifically the population count. On 
> both grow and shrink operations, we should be left with only two 
> real/physical bits set: the first and either the last or the formerly 
> last bit in the bitmap.
>
> For shrink operations, we truncate off two extra bits that exist 
> within the now 'dead space.', leaving us with two.
>
> For grow operations, we add empty space, leaving the first and 
> formerly last bit set. (This is the MIN() call above.)
>
> In both cases, we should have two real bits left. Adjusting for 
> granularity (g=1 in my tests, here, when used) we should always find 
> four "virtual bits" set.

Ooooh, yeah, I was wondering about the granularity adjustment. But of 
course, if you set one bit but your granularity is 2^x, you're basically 
setting x bits.

> Confusingly, this even happens when the bitmap ends or is truncated on 
> a virtual granularity boundary: e.g. a bitmap of 3 bits with a 
> granularity of g=1 (2^1 - 2 bits). Setting the 3rd bit will set two 
> virtual bits, giving us a popcount of 2, even though one of those bits 
> is a phantom.
>
> The boundary bits that I am checking here are set in 
> test_set_boundary_bits, and are not checked explicitly for g=0 cases 
> where we can rely on the shadow data that Paolo keeps track of. For 
> g=1 cases, I check manually.
>
> The implication here is that "test_check_boundary_bits" is only 
> expected to avoid an assertion if it is called after 
> "test_set_boundary_bits" and, in the shrinking case, a truncate operation.

I was about to propose making this a comment (I know it's only a test, 
but even tests deserve comments on what they're testing), but now I 
noticed that my main problem of understanding was simply the "you call 
hbitmap_set() once and it sets x bits if your granularity is 2^x", so I 
guess it can stay this way.

Reviewed-by: Max Reitz <mreitz@redhat.com>

>>> +    }
>>> +}
>>> +
>>> +/* 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;
>>
>>