From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:38074) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YXvYk-00039v-BU for qemu-devel@nongnu.org; Tue, 17 Mar 2015 13:45:44 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YXvYf-0007Jg-On for qemu-devel@nongnu.org; Tue, 17 Mar 2015 13:45:42 -0400 Message-ID: <5508683C.2070107@redhat.com> Date: Tue, 17 Mar 2015 13:45:32 -0400 From: Max Reitz MIME-Version: 1.0 References: <1426271419-8277-1-git-send-email-jsnow@redhat.com> <1426271419-8277-17-git-send-email-jsnow@redhat.com> <55083FD7.3080004@redhat.com> <550862B2.2020808@redhat.com> <55086452.9070600@redhat.com> <550867ED.9020309@redhat.com> In-Reply-To: <550867ED.9020309@redhat.com> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Subject: Re: [Qemu-devel] [2.4 PATCH v3 16/19] hbitmap: truncate tests List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: John Snow , qemu-block@nongnu.org Cc: kwolf@redhat.com, famz@redhat.com, qemu-devel@nongnu.org, armbru@redhat.com, vsementsov@parallels.com, stefanha@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 >>>>> --- >>>>> 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 >>>>> #include >>>>> +#include >>>>> +#include >>>>> #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 >> >>>>> + } >>>>> +} >>>>> + >>>>> +/* 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; >>>> >>>> >> >