From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:34329) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YXvIX-0001hX-IB for qemu-devel@nongnu.org; Tue, 17 Mar 2015 13:28:59 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YXvIS-0001C5-En for qemu-devel@nongnu.org; Tue, 17 Mar 2015 13:28:57 -0400 Message-ID: <55086452.9070600@redhat.com> Date: Tue, 17 Mar 2015 13:28:50 -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> In-Reply-To: <550862B2.2020808@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: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. 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; >> >>