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

[Max Reitz <mreitz@redhat.com>]

On 2015-03-17 at 13:44, John Snow wrote:
>
>
> On 03/17/2015 01:28 PM, Max Reitz wrote:
>> 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.
>>
>
> It sets 2^g bits per each distinct (bit >> granularity) value, not 'g' 
> bits.

*cough cough* Yes, that's what I meant.

> If g=1 and you set(0) on an empty map, you'll have a popcount of 2, 
> but only one real physical bit set in the implementation. If you 
> get(0) and get(1) on this map, both will come back true.
>
> set(0) and set(1) will not produce a popcount of four, for example.
>
> I can amend this with a little bit of an explanation, and keep your 
> R-B if (given the above) your review still stands.

Yes it does, I just mixed it up.

Max

>> 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;
>>>>
>>>>
>>
>