From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:37808) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YXvXQ-0001wo-5H for qemu-devel@nongnu.org; Tue, 17 Mar 2015 13:44:22 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YXvXL-0006L8-TM for qemu-devel@nongnu.org; Tue, 17 Mar 2015 13:44:20 -0400 Message-ID: <550867ED.9020309@redhat.com> Date: Tue, 17 Mar 2015 13:44:13 -0400 From: John Snow 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> In-Reply-To: <55086452.9070600@redhat.com> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: quoted-printable 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: Max Reitz , 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 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 =3D=3D 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 *da= ta, >>>> } >>>> } >>>> +static inline size_t hbitmap_test_array_size(size_t bits) >>>> +{ >>>> + size_t n =3D (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 =3D data->size; >>>> + data->size =3D size; >>>> + >>>> + if (data->size =3D=3D data->old_size) { >>>> + return; >>>> + } >>>> + >>>> + n =3D hbitmap_test_array_size(size); >>>> + m =3D hbitmap_test_array_size(data->old_size); >>>> + data->bits =3D 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 =3D size % (sizeof(unsigned long) * 8); >>>> + if (m) { >>>> + unsigned long mask =3D (1ULL << m) - 1; >>>> + data->bits[n-1] &=3D 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 =3D 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 =3D=3D 0) { >>>> + hbitmap_test_check_get(data); >>>> + } >>>> +} >>>> + >>>> +static void hbitmap_test_check_boundary_bits(TestHBitmapData *data) >>>> +{ >>>> + size_t size =3D MIN(data->size, data->old_size); >>>> + >>>> + if (data->granularity =3D=3D 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, =3D=3D, >>>> 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=3D1 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 basicall= y > 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=3D1 (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=3D0 cases >> where we can rely on the shadow data that Paolo keeps track of. For >> g=3D1 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' bi= ts. If g=3D1 and you set(0) on an empty map, you'll have a popcount of 2, but= =20 only one real physical bit set in the implementation. If you get(0) and=20 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=20 if (given the above) your review still stands. > 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 *unuse= d) >>>> +{ >>>> + size_t size =3D L2 - 1; >>>> + size_t diff =3D 1; >>>> + int granularity =3D 1; >>>> + >>>> + hbitmap_test_truncate(data, size, diff, granularity); >>>> +} >>>> + >>>> +/** >>>> + * Shrink by an amount smaller than the granularity, without crossi= ng >>>> + * a granularity alignment boundary. Effectively a NOP. >>>> + */ >>>> +static void test_hbitmap_truncate_shrink_negligible(TestHBitmapData >>>> *data, >>>> + const void >>>> *unused) >>>> +{ >>>> + size_t size =3D L2; >>>> + ssize_t diff =3D -1; >>>> + int granularity =3D 1; >>>> + >>>> + hbitmap_test_truncate(data, size, diff, granularity); >>>> +} >>>> + >>>> +/** >>>> + * Grow by an amount smaller than the granularity, but crossing ove= r >>>> + * a granularity alignment boundary. >>>> + */ >>>> +static void test_hbitmap_truncate_grow_tiny(TestHBitmapData *data, >>>> + const void *unused) >>>> +{ >>>> + size_t size =3D L2 - 2; >>>> + ssize_t diff =3D 1; >>>> + int granularity =3D 1; >>>> + >>>> + hbitmap_test_truncate(data, size, diff, granularity); >>>> +} >>>> + >>>> +/** >>>> + * Shrink by an amount smaller than the granularity, but crossing o= ver >>>> + * a granularity alignment boundary. >>>> + */ >>>> +static void test_hbitmap_truncate_shrink_tiny(TestHBitmapData *data= , >>>> + const void *unused) >>>> +{ >>>> + size_t size =3D L2 - 1; >>>> + ssize_t diff =3D -1; >>>> + int granularity =3D 1; >>>> + >>>> + hbitmap_test_truncate(data, size, diff, granularity); >>>> +} >>>> + >>>> +/** >>>> + * Grow by an amount smaller than sizeof(long), and not crossing ov= er >>>> + * a sizeof(long) alignment boundary. >>>> + */ >>>> +static void test_hbitmap_truncate_grow_small(TestHBitmapData *data, >>>> + const void *unused) >>>> +{ >>>> + size_t size =3D L2 + 1; >>>> + size_t diff =3D 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 *dat= a, >>>> + const void *unused) >>>> +{ >>>> + size_t size =3D L2; >>>> + size_t diff =3D 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 =3D L2 - 1; >>>> + size_t diff =3D sizeof(long) / 2; >>>> + >>>> + hbitmap_test_truncate(data, size, diff, 0); >>>> +} >>>> + >>>> +/** >>>> + * Shrink by an amount smaller than sizeof(long), while crossing ov= er >>>> + * a sizeof(long) alignment boundary. >>>> + */ >>>> +static void test_hbitmap_truncate_shrink_medium(TestHBitmapData *da= ta, >>>> + const void *unused) >>>> +{ >>>> + size_t size =3D L2 + 1; >>>> + size_t diff =3D 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 =3D L2; >>>> + size_t diff =3D 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 *dat= a, >>>> + const void *unused) >>>> +{ >>>> + size_t size =3D L2; >>>> + size_t diff =3D 8 * sizeof(long); >>>> + >>>> + hbitmap_test_truncate(data, size, -diff, 0); >>>> +} >>>> + >>>> static void hbitmap_test_add(const char *testpath, >>>> void (*test_func)(TestHBitmapDa= ta >>>> *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; >>> >>> > --=20 =E2=80=94js