From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:38726) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cADHX-0003Ed-0g for qemu-devel@nongnu.org; Fri, 25 Nov 2016 04:59:00 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cADHV-00030g-5b for qemu-devel@nongnu.org; Fri, 25 Nov 2016 04:58:59 -0500 References: <20161115063715.12561-1-pbutsykin@virtuozzo.com> <20161115063715.12561-6-pbutsykin@virtuozzo.com> <20161124122050.GA4535@noname.redhat.com> From: Pavel Butsykin Message-ID: <58380B4F.50703@virtuozzo.com> Date: Fri, 25 Nov 2016 12:58:39 +0300 MIME-Version: 1.0 In-Reply-To: <20161124122050.GA4535@noname.redhat.com> Content-Type: text/plain; charset="windows-1252"; format=flowed Content-Transfer-Encoding: 7bit Subject: Re: [Qemu-devel] [PATCH v1 05/18] tests/test-rbcache: add test cases List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Kevin Wolf Cc: qemu-devel@nongnu.org, qemu-block@nongnu.org, den@openvz.org, famz@redhat.com, stefanha@redhat.com, mreitz@redhat.com, eblake@redhat.com On 24.11.2016 15:20, Kevin Wolf wrote: > Am 15.11.2016 um 07:37 hat Pavel Butsykin geschrieben: >> Signed-off-by: Pavel Butsykin >> --- >> tests/Makefile.include | 3 + >> tests/test-rbcache.c | 308 +++++++++++++++++++++++++++++++++++++++++++++++++ >> 2 files changed, 311 insertions(+) >> create mode 100644 tests/test-rbcache.c >> >> diff --git a/tests/Makefile.include b/tests/Makefile.include >> index 8162f6f..36bb472 100644 >> --- a/tests/Makefile.include >> +++ b/tests/Makefile.include >> @@ -54,6 +54,8 @@ check-unit-y += tests/test-hbitmap$(EXESUF) >> gcov-files-test-hbitmap-y = blockjob.c >> check-unit-y += tests/test-blockjob$(EXESUF) >> check-unit-y += tests/test-blockjob-txn$(EXESUF) >> +gcov-files-test-rbcache-y = util/rbcache.c >> +check-unit-y += tests/test-rbcache$(EXESUF) >> check-unit-y += tests/test-x86-cpuid$(EXESUF) >> # all code tested by test-x86-cpuid is inside topology.h >> gcov-files-test-x86-cpuid-y = >> @@ -481,6 +483,7 @@ tests/test-blockjob-txn$(EXESUF): tests/test-blockjob-txn.o $(test-block-obj-y) >> tests/test-thread-pool$(EXESUF): tests/test-thread-pool.o $(test-block-obj-y) >> tests/test-iov$(EXESUF): tests/test-iov.o $(test-util-obj-y) >> tests/test-hbitmap$(EXESUF): tests/test-hbitmap.o $(test-util-obj-y) >> +tests/test-rbcache$(EXESUF): tests/test-rbcache.o $(test-util-obj-y) >> tests/test-x86-cpuid$(EXESUF): tests/test-x86-cpuid.o >> tests/test-xbzrle$(EXESUF): tests/test-xbzrle.o migration/xbzrle.o page_cache.o $(test-util-obj-y) >> tests/test-cutils$(EXESUF): tests/test-cutils.o util/cutils.o >> diff --git a/tests/test-rbcache.c b/tests/test-rbcache.c >> new file mode 100644 >> index 0000000..1c72bfa >> --- /dev/null >> +++ b/tests/test-rbcache.c >> @@ -0,0 +1,308 @@ >> +/* >> + * QEMU Range-Based Cache core >> + * >> + * Copyright (C) 2015-2016 Parallels IP Holdings GmbH. All rights reserved. >> + * >> + * Author: Pavel Butsykin >> + * >> + * This work is licensed under the terms of the GNU GPL, version 2 or >> + * later. See the COPYING file in the top-level directory. >> + */ >> + >> +#include "qemu/osdep.h" >> +#include "qemu/rbcache.h" >> + >> +typedef struct TestRBCacheData { >> + RBCache *cache; >> +} TestRBCacheData; >> + >> +typedef struct TestRBCacheConfig { >> + uint64_t limit_size; >> + int eviction_type; >> + RBNodeAlloc *alloc; >> + RBNodeFree *free; >> + void *opaque; >> +} TestRBCacheConfig; >> + >> +#define KB(_n) ((_n) << 10) >> +#define MB(_n) ((_n) << 20) >> + >> +#define OFFSET1 0 >> +#define SIZE1 KB(1) >> + >> +#define OFFSET2 KB(1) >> +#define SIZE2 KB(2) >> + >> +#define OFFSET3 KB(15) >> +#define SIZE3 KB(1) >> + >> +#define OFFSET4 KB(7) >> +#define SIZE4 KB(7) >> + >> +#define OFFSET5 KB(2) >> +#define SIZE5 KB(8) > > Visualised, we test these requests: > > 1: * > 2: ** > 3: * > 4: ******* > 5: ******** > > You test inserting the only element, inserting after the last element, > inserting in the middle and inserting something that overlaps two other > requests at its start and end. > > That's a good start, but it might be worth testing more scenarios: > > - Inserting a new first element to a non-empty cache What do you mean? To insert an element with zero offset when the cache already contains other nodes.? > - Overlapping only at the start > - Overlapping only at the end > - Overlapping in the middle (i.e. including existing ranges as a > subset) > * With only one node > * With multiple nodes (like adding offset=2, size=16kb here) > Ok. >> + >> +static void test_rbcache_init(TestRBCacheData *data, const void *ctx) >> +{ >> + g_assert_nonnull(data->cache); >> +} >> + >> +static void test_rbcache_insert(TestRBCacheData *data, const void *ctx) >> +{ >> + RBCacheNode *node1 = rbcache_node_alloc(data->cache, OFFSET1, SIZE1); >> + RBCacheNode *node2 = rbcache_node_alloc(data->cache, OFFSET2, SIZE2); >> + RBCacheNode *node3 = rbcache_node_alloc(data->cache, OFFSET3, SIZE3); >> + RBCacheNode *node4 = rbcache_node_alloc(data->cache, OFFSET4, SIZE4); >> + RBCacheNode *node5 = rbcache_node_alloc(data->cache, OFFSET5, SIZE5); >> + RBCacheNode *node; >> + >> + node = rbcache_insert(data->cache, node1); >> + g_assert_true(node == node1); >> + >> + node = rbcache_insert(data->cache, node2); >> + g_assert_true(node == node2); >> + >> + node = rbcache_insert(data->cache, node3); >> + g_assert_true(node == node3); >> + >> + node = rbcache_insert(data->cache, node4); >> + g_assert_true(node == node4); >> + >> + node = rbcache_insert(data->cache, node5); >> + g_assert_true(node != node5); > > You can test for the right result instead: > > g_assert_true(node == node2); > > >> + rbcache_node_free(data->cache, node5); >> +} >> + >> +static void test_rbcache_search(TestRBCacheData *data, const void *ctx) >> +{ >> + RBCacheNode *node; >> + >> + test_rbcache_insert(data, ctx); >> + >> + node = rbcache_search(data->cache, OFFSET1, SIZE1); >> + g_assert_nonnull(node); >> + g_assert_cmpuint(node->offset, ==, OFFSET1); >> + g_assert_cmpuint(node->bytes, ==, SIZE1); >> + >> + node = rbcache_search(data->cache, OFFSET2 + KB(1), SIZE1); > > Intentional that you use SIZE1 here even though we're looking at node 2? No, here we need to use SIZE2 or SIZE2 - KB(1) >> + g_assert_nonnull(node); >> + g_assert_cmpuint(node->offset, ==, OFFSET2); >> + g_assert_cmpuint(node->bytes, ==, SIZE2); >> + >> + node = rbcache_search(data->cache, OFFSET5, SIZE5); >> + g_assert_nonnull(node); >> + g_assert_cmpuint(node->offset, ==, OFFSET2); >> + g_assert_cmpuint(node->bytes, ==, SIZE2); >> + >> + node = rbcache_search(data->cache, OFFSET5 + KB(2), SIZE5); >> + g_assert_nonnull(node); >> + g_assert_cmpuint(node->offset, ==, OFFSET4); >> + g_assert_cmpuint(node->bytes, ==, SIZE4); >> + >> + node = rbcache_search(data->cache, OFFSET3 + SIZE3, SIZE3); >> + g_assert_null(node); >> +} >> + >> +static void test_rbcache_search_and_insert(TestRBCacheData *data, >> + const void *ctx) >> +{ >> + RBCacheNode *node; >> + >> + node = rbcache_search_and_insert(data->cache, OFFSET1, SIZE1); >> + g_assert_nonnull(node); >> + g_assert_cmpuint(node->offset, ==, OFFSET1); >> + g_assert_cmpuint(node->bytes, ==, SIZE1); >> + >> + node = rbcache_search_and_insert(data->cache, OFFSET2, SIZE2); >> + g_assert_nonnull(node); >> + g_assert_cmpuint(node->offset, ==, OFFSET2); >> + g_assert_nonnull(node); > > I think you wanted to check node->bytes here instead of duplicating the > nonnull check. > >> + node = rbcache_search_and_insert(data->cache, OFFSET3, SIZE3); >> + g_assert_nonnull(node); >> + g_assert_cmpuint(node->offset, ==, OFFSET3); >> + g_assert_cmpuint(node->bytes, ==, SIZE3); >> + >> + node = rbcache_search_and_insert(data->cache, OFFSET4, SIZE4); >> + g_assert_nonnull(node); >> + g_assert_cmpuint(node->offset, ==, OFFSET4); >> + g_assert_cmpuint(node->bytes, ==, SIZE4); >> + >> + node = rbcache_search_and_insert(data->cache, OFFSET5, SIZE5); >> + g_assert_nonnull(node); >> + g_assert_cmpuint(node->offset, ==, OFFSET2); >> + g_assert_cmpuint(node->bytes, ==, SIZE2); >> +} >> + >> +static void test_rbcache_remove(TestRBCacheData *data, const void *ctx) >> +{ >> + RBCacheNode *node; >> + >> + test_rbcache_search_and_insert(data, ctx); >> + >> + node = rbcache_search(data->cache, OFFSET1, SIZE1); >> + g_assert_nonnull(node); >> + rbcache_remove(data->cache, node); >> + node = rbcache_search(data->cache, OFFSET1, SIZE1); >> + g_assert_null(node); >> + >> + node = rbcache_search(data->cache, OFFSET3, SIZE3); >> + g_assert_nonnull(node); >> + rbcache_remove(data->cache, node); >> + node = rbcache_search(data->cache, OFFSET3, SIZE3); >> + g_assert_null(node); >> + >> + node = rbcache_search(data->cache, OFFSET4, SIZE4); >> + g_assert_nonnull(node); >> + rbcache_remove(data->cache, node); >> + node = rbcache_search(data->cache, OFFSET4, SIZE4); >> + g_assert_null(node); >> + >> + node = rbcache_search(data->cache, OFFSET2, SIZE2); >> + g_assert_nonnull(node); >> + rbcache_remove(data->cache, node); >> + node = rbcache_search(data->cache, OFFSET2, SIZE2); >> + g_assert_null(node); >> +} >> + >> +static void test_rbcache_shrink(TestRBCacheData *data, const void *ctx) >> +{ >> + RBCacheNode *node; >> + >> + node = rbcache_search_and_insert(data->cache, 0, MB(2)); >> + g_assert_nonnull(node); >> + >> + node = rbcache_search_and_insert(data->cache, MB(2), MB(3)); >> + g_assert_nonnull(node); >> + >> + node = rbcache_search(data->cache, 0, MB(2)); >> + g_assert_null(node); >> + >> + node = rbcache_search(data->cache, MB(2), MB(3)); >> + g_assert_nonnull(node); >> + >> + node = rbcache_search_and_insert(data->cache, 0, MB(2)); >> + g_assert_nonnull(node); >> + >> + node = rbcache_search(data->cache, 0, MB(2)); >> + g_assert_nonnull(node); >> + >> + node = rbcache_search(data->cache, MB(2), MB(3)); >> + g_assert_null(node); >> +} >> + >> +static void test_rbcache_shrink_fifo(TestRBCacheData *data, const void *ctx) >> +{ >> + RBCacheNode *node; >> + >> + rbcache_search_and_insert(data->cache, 0, MB(1)); >> + rbcache_search_and_insert(data->cache, MB(1), MB(1)); >> + rbcache_search_and_insert(data->cache, MB(2), MB(1)); >> + rbcache_search_and_insert(data->cache, MB(3), MB(1)); >> + >> + node = rbcache_search_and_insert(data->cache, MB(4), MB(1)); >> + g_assert_nonnull(node); >> + node = rbcache_search(data->cache, 0, MB(1)); >> + g_assert_null(node); >> + >> + node = rbcache_search_and_insert(data->cache, MB(5), MB(1)); >> + g_assert_nonnull(node); >> + node = rbcache_search(data->cache, MB(1), MB(1)); >> + g_assert_null(node); >> + >> + node = rbcache_search_and_insert(data->cache, MB(6), MB(1)); >> + g_assert_nonnull(node); >> + node = rbcache_search(data->cache, MB(2), MB(1)); >> + g_assert_null(node); >> + >> + node = rbcache_search_and_insert(data->cache, MB(7), MB(1)); >> + g_assert_nonnull(node); >> + node = rbcache_search(data->cache, MB(3), MB(1)); >> + g_assert_null(node); > > This test doesn't really show that this is any different from LRU mode. > LRU would behave exactly the same because you have no accesses to > existing nodes. > > It also doesn't test that the other nodes still exist. > >> +} >> + >> +static void test_rbcache_shrink_lru(TestRBCacheData *data, const void *ctx) >> +{ >> + RBCacheNode *node; >> + >> + rbcache_search_and_insert(data->cache, 0, MB(1)); >> + rbcache_search_and_insert(data->cache, MB(1), MB(1)); >> + rbcache_search_and_insert(data->cache, MB(2), MB(1)); >> + rbcache_search_and_insert(data->cache, MB(3), MB(1)); >> + >> + node = rbcache_search(data->cache, MB(2), MB(1)); >> + g_assert_nonnull(node); >> + >> + node = rbcache_search(data->cache, MB(1), MB(1)); >> + g_assert_nonnull(node); >> + >> + node = rbcache_search_and_insert(data->cache, MB(4), MB(1)); >> + g_assert_nonnull(node); >> + node = rbcache_search(data->cache, 0, MB(1)); >> + g_assert_null(node); >> + >> + node = rbcache_search_and_insert(data->cache, MB(5), MB(1)); >> + g_assert_nonnull(node); >> + node = rbcache_search(data->cache, MB(3), MB(1)); >> + g_assert_null(node); >> + >> + node = rbcache_search_and_insert(data->cache, MB(6), MB(1)); >> + g_assert_nonnull(node); >> + node = rbcache_search(data->cache, MB(2), MB(1)); >> + g_assert_null(node); >> + >> + node = rbcache_search_and_insert(data->cache, MB(7), MB(1)); >> + g_assert_nonnull(node); >> + node = rbcache_search(data->cache, MB(1), MB(1)); >> + g_assert_null(node); > > Here as well we don't test whether the other nodes still exist, but at > least we have rbcache_search() calls to make the difference clear. You > should probably copy those calls to the FIFO test to show that they > don't have any effect on the order. Yes, good point. >> +} >> + >> +static void test_rbcache_setup(TestRBCacheData *data, const void *ctx) >> +{ >> + const TestRBCacheConfig *config = ctx; >> + >> + data->cache = >> + rbcache_create(config->alloc, config->free, config->limit_size, >> + config->eviction_type, config->opaque); >> +} >> + >> +static void test_rbcache_teardown(TestRBCacheData *data, const void *ctx) >> +{ >> + rbcache_destroy(data->cache); >> +} >> + >> +static void rbcache_test_add(const char *testpath, >> + void (*test_func)(TestRBCacheData *data, >> + const void *user_data), void *ctx) >> +{ >> + g_test_add(testpath, TestRBCacheData, ctx, test_rbcache_setup, test_func, >> + test_rbcache_teardown); >> +} >> + >> +int main(int argc, char **argv) >> +{ >> + TestRBCacheConfig config = { >> + .limit_size = MB(4), >> + .eviction_type = RBCACHE_FIFO, >> + }; >> + >> + g_test_init(&argc, &argv, NULL); >> + >> + rbcache_test_add("/rbcache/init", test_rbcache_init, &config); >> + rbcache_test_add("/rbcache/insert", test_rbcache_insert, &config); >> + rbcache_test_add("/rbcache/search", test_rbcache_search, &config); >> + rbcache_test_add("/rbcache/search_and_insert", >> + test_rbcache_search_and_insert, &config); >> + rbcache_test_add("/rbcache/rbcache_remove", test_rbcache_remove, &config); >> + rbcache_test_add("/rbcache/shrink", test_rbcache_shrink, &config); >> + rbcache_test_add("/rbcache/shrink/fifo", test_rbcache_shrink_fifo, &config); >> + >> + config.eviction_type = RBCACHE_LRU; >> + rbcache_test_add("/rbcache/shrink/lru", test_rbcache_shrink_lru, &config); >> + >> + g_test_run(); >> + >> + return 0; >> +} > > Kevin >