diff mbox

[v1,05/18] tests/test-rbcache: add test cases

Message ID 20161115063715.12561-6-pbutsykin@virtuozzo.com (mailing list archive)
State New, archived
Headers show

Commit Message

Pavel Butsykin Nov. 15, 2016, 6:37 a.m. UTC 
Signed-off-by: Pavel Butsykin <pbutsykin@virtuozzo.com>
---
 tests/Makefile.include |   3 +
 tests/test-rbcache.c   | 308 +++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 311 insertions(+)
 create mode 100644 tests/test-rbcache.c

Comments

Kevin Wolf Nov. 24, 2016, 12:20 p.m. UTC | #1 
Am 15.11.2016 um 07:37 hat Pavel Butsykin geschrieben:
> Signed-off-by: Pavel Butsykin <pbutsykin@virtuozzo.com>
> ---
>  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 <pbutsykin@virtuozzo.com>
> + *
> + * 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
- 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)


> +
> +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?

> +    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.

> +}
> +
> +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
Pavel Butsykin Nov. 25, 2016, 9:58 a.m. UTC | #2 
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 <pbutsykin@virtuozzo.com>
>> ---
>>   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 <pbutsykin@virtuozzo.com>
>> + *
>> + * 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
>
Kevin Wolf Nov. 25, 2016, 10:11 a.m. UTC | #3 
Am 25.11.2016 um 10:58 hat Pavel Butsykin geschrieben:
> On 24.11.2016 15:20, Kevin Wolf wrote:
> >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.?

Yes, that would be one way to do it. Maybe just swap requests 1 and 2.

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

Kevin
diff mbox

Patch

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 <pbutsykin@virtuozzo.com>
+ *
+ * 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)
+
+
+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);
+
+    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);
+    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);
+
+    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);
+}
+
+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);
+}
+
+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;
+}