[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-block] [PULL 07/22] qcow2: use an LRU algorithm to replace entries
From: |
Kevin Wolf |
Subject: |
[Qemu-block] [PULL 07/22] qcow2: use an LRU algorithm to replace entries from the L2 cache |
Date: |
Fri, 22 May 2015 17:26:25 +0200 |
From: Alberto Garcia <address@hidden>
The current algorithm to evict entries from the cache gives always
preference to those in the lowest positions. As the size of the cache
increases, the chances of the later elements of being removed decrease
exponentially.
In a scenario with random I/O and lots of cache misses, entries in
positions 8 and higher are rarely (if ever) evicted. This can be seen
even with the default cache size, but with larger caches the problem
becomes more obvious.
Using an LRU algorithm makes the chances of being removed from the
cache independent from the position.
Signed-off-by: Alberto Garcia <address@hidden>
Reviewed-by: Max Reitz <address@hidden>
Signed-off-by: Kevin Wolf <address@hidden>
---
block/qcow2-cache.c | 33 +++++++++++++++------------------
1 file changed, 15 insertions(+), 18 deletions(-)
diff --git a/block/qcow2-cache.c b/block/qcow2-cache.c
index 6e78c8f..3a31895 100644
--- a/block/qcow2-cache.c
+++ b/block/qcow2-cache.c
@@ -28,10 +28,10 @@
#include "trace.h"
typedef struct Qcow2CachedTable {
- int64_t offset;
- bool dirty;
- int cache_hits;
- int ref;
+ int64_t offset;
+ bool dirty;
+ uint64_t lru_counter;
+ int ref;
} Qcow2CachedTable;
struct Qcow2Cache {
@@ -40,6 +40,7 @@ struct Qcow2Cache {
int size;
bool depends_on_flush;
void *table_array;
+ uint64_t lru_counter;
};
static inline void *qcow2_cache_get_table_addr(BlockDriverState *bs,
@@ -233,16 +234,18 @@ int qcow2_cache_empty(BlockDriverState *bs, Qcow2Cache *c)
for (i = 0; i < c->size; i++) {
assert(c->entries[i].ref == 0);
c->entries[i].offset = 0;
- c->entries[i].cache_hits = 0;
+ c->entries[i].lru_counter = 0;
}
+ c->lru_counter = 0;
+
return 0;
}
static int qcow2_cache_find_entry_to_replace(Qcow2Cache *c)
{
int i;
- int min_count = INT_MAX;
+ uint64_t min_lru_counter = UINT64_MAX;
int min_index = -1;
@@ -251,15 +254,9 @@ static int qcow2_cache_find_entry_to_replace(Qcow2Cache *c)
continue;
}
- if (c->entries[i].cache_hits < min_count) {
+ if (c->entries[i].lru_counter < min_lru_counter) {
min_index = i;
- min_count = c->entries[i].cache_hits;
- }
-
- /* Give newer hits priority */
- /* TODO Check how to optimize the replacement strategy */
- if (c->entries[i].cache_hits > 1) {
- c->entries[i].cache_hits /= 2;
+ min_lru_counter = c->entries[i].lru_counter;
}
}
@@ -316,14 +313,10 @@ static int qcow2_cache_do_get(BlockDriverState *bs,
Qcow2Cache *c,
}
}
- /* Give the table some hits for the start so that it won't be replaced
- * immediately. The number 32 is completely arbitrary. */
- c->entries[i].cache_hits = 32;
c->entries[i].offset = offset;
/* And return the right table */
found:
- c->entries[i].cache_hits++;
c->entries[i].ref++;
*table = qcow2_cache_get_table_addr(bs, c, i);
@@ -356,6 +349,10 @@ int qcow2_cache_put(BlockDriverState *bs, Qcow2Cache *c,
void **table)
c->entries[i].ref--;
*table = NULL;
+ if (c->entries[i].ref == 0) {
+ c->entries[i].lru_counter = ++c->lru_counter;
+ }
+
assert(c->entries[i].ref >= 0);
return 0;
}
--
1.8.3.1
- [Qemu-block] [PULL 00/22] Block layer core and image format patches, Kevin Wolf, 2015/05/22
- [Qemu-block] [PULL 03/22] vmdk: Fix next_cluster_sector for compressed write, Kevin Wolf, 2015/05/22
- [Qemu-block] [PULL 02/22] nvme: support NVME_VOLATILE_WRITE_CACHE feature, Kevin Wolf, 2015/05/22
- [Qemu-block] [PULL 04/22] vmdk: Fix overflow if l1_size is 0x20000000, Kevin Wolf, 2015/05/22
- [Qemu-block] [PULL 01/22] qcow2: Flush pending discards before allocating cluster, Kevin Wolf, 2015/05/22
- [Qemu-block] [PULL 05/22] qcow2: use one single memory block for the L2/refcount cache tables, Kevin Wolf, 2015/05/22
- [Qemu-block] [PULL 06/22] qcow2: simplify qcow2_cache_put() and qcow2_cache_entry_mark_dirty(), Kevin Wolf, 2015/05/22
- [Qemu-block] [PULL 07/22] qcow2: use an LRU algorithm to replace entries from the L2 cache,
Kevin Wolf <=
- [Qemu-block] [PULL 09/22] qcow2: use a hash to look for entries in the L2 cache, Kevin Wolf, 2015/05/22
- [Qemu-block] [PULL 08/22] qcow2: remove qcow2_cache_find_entry_to_replace(), Kevin Wolf, 2015/05/22
- [Qemu-block] [PULL 10/22] qcow2: make qcow2_cache_put() a void function, Kevin Wolf, 2015/05/22
- [Qemu-block] [PULL 11/22] qcow2: style fixes in qcow2-cache.c, Kevin Wolf, 2015/05/22
- [Qemu-block] [PULL 13/22] block: Detect multiplication overflow in bdrv_getlength, Kevin Wolf, 2015/05/22
- [Qemu-block] [PULL 12/22] qemu-io: Use getopt() correctly, Kevin Wolf, 2015/05/22
- [Qemu-block] [PULL 14/22] qemu-iotests: qemu-img info on afl VMDK image with a huge capacity, Kevin Wolf, 2015/05/22
- [Qemu-block] [PULL 18/22] util: allow \n to terminate password input, Kevin Wolf, 2015/05/22
- [Qemu-block] [PULL 16/22] qcow2/qcow: protect against uninitialized encryption key, Kevin Wolf, 2015/05/22
- [Qemu-block] [PULL 17/22] util: move read_password method out of qemu-img into osdep/oslib, Kevin Wolf, 2015/05/22