diff --git a/tests/Makefile.include b/tests/Makefile.include
index 4841d582a1..74bdcd2aac 100644
--- a/tests/Makefile.include
+++ b/tests/Makefile.include
@@ -55,6 +55,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 =
@@ -498,6 +500,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 0000000000..40ccd6b225
--- /dev/null
+++ b/tests/test-rbcache.c
@@ -0,0 +1,431 @@
+/*
+ * QEMU Range-Based Cache core
+ *
+ * Copyright (C) 2015-2016 Parallels IP Holdings GmbH.
+ *
+ * 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(18)
+#define SIZE3   KB(1)
+
+#define OFFSET4 KB(7)
+#define SIZE4   KB(7)
+
+#define OFFSET5 KB(1)
+#define SIZE5   KB(4)
+
+#define OFFSET6 KB(5)
+#define SIZE6   KB(5)
+
+#define OFFSET7 KB(15)
+#define SIZE7   KB(20)
+
+#define OFFSET8 KB(2)
+#define SIZE8   KB(20)
+
+
+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 *node6 = rbcache_node_alloc(data->cache, OFFSET6, SIZE6);
+    RBCacheNode *node7 = rbcache_node_alloc(data->cache, OFFSET7, SIZE7);
+    RBCacheNode *node8 = rbcache_node_alloc(data->cache, OFFSET8, SIZE8);
+    RBCacheNode *node;
+
+    node = rbcache_insert(data->cache, node2);
+    g_assert_true(node == node2);
+
+    node = rbcache_insert(data->cache, node1);
+    g_assert_true(node == node1);
+
+    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 == node2);
+    rbcache_node_free(data->cache, node5);
+
+    node = rbcache_insert(data->cache, node6);
+    g_assert_true(node == node4);
+    rbcache_node_free(data->cache, node6);
+
+    node = rbcache_insert(data->cache, node7);
+    g_assert_true(node == node3);
+    rbcache_node_free(data->cache, node7);
+
+    node = rbcache_insert(data->cache, node8);
+    g_assert_true(node == node2);
+    rbcache_node_free(data->cache, node8);
+}
+
+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), SIZE2);
+    g_assert_nonnull(node);
+    g_assert_cmpuint(node->offset, ==, OFFSET2);
+    g_assert_cmpuint(node->bytes, ==, SIZE2);
+
+    node = rbcache_search(data->cache, OFFSET8, SIZE8);
+    g_assert_nonnull(node);
+    g_assert_cmpuint(node->offset, ==, OFFSET2);
+    g_assert_cmpuint(node->bytes, ==, SIZE2);
+
+    node = rbcache_search(data->cache, OFFSET8 + KB(2), SIZE5);
+    g_assert_nonnull(node);
+    g_assert_cmpuint(node->offset, ==, OFFSET4);
+    g_assert_cmpuint(node->bytes, ==, OFFSET4);
+
+    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, OFFSET2, SIZE2);
+    g_assert_nonnull(node);
+    g_assert_cmpuint(node->offset, ==, OFFSET2);
+    g_assert_cmpuint(node->bytes, ==, SIZE2);
+
+    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, 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);
+
+    node = rbcache_search_and_insert(data->cache, OFFSET6, SIZE6);
+    g_assert_nonnull(node);
+    g_assert_cmpuint(node->offset, ==, OFFSET4);
+    g_assert_cmpuint(node->bytes, ==, SIZE4);
+
+    node = rbcache_search_and_insert(data->cache, OFFSET7, SIZE7);
+    g_assert_nonnull(node);
+    g_assert_cmpuint(node->offset, ==, OFFSET3);
+    g_assert_cmpuint(node->bytes, ==, SIZE3);
+
+    node = rbcache_search_and_insert(data->cache, OFFSET8, SIZE8);
+    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(data->cache, MB(3), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(1), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(2), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(4), MB(1));
+    g_assert_nonnull(node);
+
+    node = rbcache_search_and_insert(data->cache, MB(5), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, 0, MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(1), MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(3), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(2), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(4), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(5), MB(1));
+    g_assert_nonnull(node);
+
+    node = rbcache_search_and_insert(data->cache, MB(6), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, 0, MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(1), MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(2), MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(3), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(4), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(5), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(6), MB(1));
+    g_assert_nonnull(node);
+
+    node = rbcache_search_and_insert(data->cache, MB(7), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, 0, MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(1), MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(2), MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(3), MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(4), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(5), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(6), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(7), MB(1));
+    g_assert_nonnull(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_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(data->cache, MB(3), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(1), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(2), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(4), MB(1));
+    g_assert_nonnull(node);
+
+    node = rbcache_search_and_insert(data->cache, MB(5), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, 0, MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(3), MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(1), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(2), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(4), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(5), MB(1));
+    g_assert_nonnull(node);
+
+    node = rbcache_search_and_insert(data->cache, MB(6), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, 0, MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(3), MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(1), MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(2), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(4), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(5), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(6), MB(1));
+    g_assert_nonnull(node);
+
+    node = rbcache_search_and_insert(data->cache, MB(7), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, 0, MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(3), MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(1), MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(2), MB(1));
+    g_assert_null(node);
+    node = rbcache_search(data->cache, MB(4), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(5), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(6), MB(1));
+    g_assert_nonnull(node);
+    node = rbcache_search(data->cache, MB(7), MB(1));
+    g_assert_nonnull(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,
+    };
+    TestRBCacheConfig config_lru = {
+        .limit_size = MB(4),
+        .eviction_type = RBCACHE_LRU,
+    };
+
+    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);
+    rbcache_test_add("/rbcache/shrink/lru", test_rbcache_shrink_lru,
+                     &config_lru);
+
+    g_test_run();
+
+    return 0;
+}
