From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([140.186.70.92]:34537) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ri6Ol-0005fH-FR for qemu-devel@nongnu.org; Tue, 03 Jan 2012 10:35:36 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Ri6Oh-0006wm-Ac for qemu-devel@nongnu.org; Tue, 03 Jan 2012 10:35:35 -0500 Received: from mx1.redhat.com ([209.132.183.28]:2061) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ri6Oh-0006wY-3t for qemu-devel@nongnu.org; Tue, 03 Jan 2012 10:35:31 -0500 From: Orit Wasserman Date: Tue, 3 Jan 2012 17:34:31 +0200 Message-Id: <1325604879-15862-2-git-send-email-owasserm@redhat.com> In-Reply-To: <1325604879-15862-1-git-send-email-owasserm@redhat.com> References: <1325604879-15862-1-git-send-email-owasserm@redhat.com> Subject: [Qemu-devel] [PATCH v5 1/9] Add cache handling functions List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org Cc: blauwirbel@gmail.com, stefanha@gmail.com, Orit Wasserman , quintela@redhat.com Add page caching mechanism. The pages are stored in the cache ordered by their address. Signed-off-by: Orit Wasserman --- arch_init.c | 183 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 183 insertions(+), 0 deletions(-) diff --git a/arch_init.c b/arch_init.c index d4c92b0..fdda277 100644 --- a/arch_init.c +++ b/arch_init.c @@ -28,6 +28,7 @@ #include #include #endif +#include #include "config.h" #include "monitor.h" #include "sysemu.h" @@ -42,6 +43,14 @@ #include "gdbstub.h" #include "hw/smbios.h" +#ifdef DEBUG_ARCH_INIT +#define DPRINTF(fmt, ...) \ + do { fprintf(stdout, "arch_init: " fmt, ## __VA_ARGS__); } while (0) +#else +#define DPRINTF(fmt, ...) \ + do { } while (0) +#endif + #ifdef TARGET_SPARC int graphic_width = 1024; int graphic_height = 768; @@ -94,6 +103,180 @@ const uint32_t arch_type = QEMU_ARCH; #define RAM_SAVE_FLAG_EOS 0x10 #define RAM_SAVE_FLAG_CONTINUE 0x20 +/***********************************************************/ +/* Page cache for storing previous pages as basis for XBRLE compression */ +#define CACHE_N_WAY 2 /* 2-way assossiative cache */ + +typedef struct CacheItem { + ram_addr_t it_addr; + unsigned long it_age; + uint8_t *it_data; +} CacheItem; + +typedef struct CacheBucket { + CacheItem bkt_item[CACHE_N_WAY]; +} CacheBucket; + +static CacheBucket *page_cache; +static int64_t cache_num_buckets; +static uint64_t cache_max_item_age; +static int64_t cache_num_items; + +static void cache_init(ssize_t num_buckets); +static void cache_fini(void); +static int cache_is_cached(ram_addr_t addr); +static int cache_get_oldest(CacheBucket *buck); +static int cache_get_newest(CacheBucket *buck, ram_addr_t addr); +static void cache_insert(ram_addr_t id, uint8_t *pdata); +static unsigned long cache_get_cache_pos(ram_addr_t address); +static CacheItem *cache_item_get(unsigned long pos, int item); + +/***********************************************************/ +/* XBRLE (Xor Based Run-Length Encoding) */ +typedef struct XBRLEHeader { + uint8_t xh_flags; + uint16_t xh_len; + uint32_t xh_cksum; +} XBRLEHeader; + +/***********************************************************/ +/* XBRLE page cache implementation */ +static CacheItem *cache_item_get(unsigned long pos, int item) +{ + assert(page_cache); + return &page_cache[pos].bkt_item[item]; +} + +static void cache_init(int64_t num_bytes) +{ + int i; + + cache_num_items = 0; + cache_max_item_age = 0; + cache_num_buckets = num_bytes / (TARGET_PAGE_SIZE * CACHE_N_WAY); + assert(cache_num_buckets); + DPRINTF("Setting cache buckets to %lu\n", cache_num_buckets); + + assert(!page_cache); + page_cache = (CacheBucket *)g_malloc0((cache_num_buckets) * + sizeof(CacheBucket)); + + for (i = 0; i < cache_num_buckets; i++) { + int j; + for (j = 0; j < CACHE_N_WAY; j++) { + CacheItem *it = cache_item_get(i, j); + it->it_data = NULL; + it->it_age = 0; + it->it_addr = -1; + } + } +} + +static void cache_fini(void) +{ + int i; + + assert(page_cache); + + for (i = 0; i < cache_num_buckets; i++) { + int j; + for (j = 0; j < CACHE_N_WAY; j++) { + CacheItem *it = cache_item_get(i, j); + g_free(it->it_data); + it->it_data = 0; + } + } + + g_free(page_cache); + page_cache = NULL; +} + +static unsigned long cache_get_cache_pos(ram_addr_t address) +{ + unsigned long pos; + + assert(cache_num_buckets); + pos = (address/TARGET_PAGE_SIZE) & (cache_num_buckets - 1); + return pos; +} + +static int cache_get_newest(CacheBucket *buck, ram_addr_t addr) +{ + unsigned long big = 0; + int big_pos = -1; + int j; + + assert(page_cache); + + for (j = 0; j < CACHE_N_WAY; j++) { + CacheItem *it = &buck->bkt_item[j]; + + if (it->it_addr != addr) { + continue; + } + + if (!j || it->it_age > big) { + big = it->it_age; + big_pos = j; + } + } + + return big_pos; +} + +static int cache_get_oldest(CacheBucket *buck) +{ + unsigned long small = 0; + int small_pos = -1; + int j; + + assert(page_cache); + + for (j = 0; j < CACHE_N_WAY; j++) { + CacheItem *it = &buck->bkt_item[j]; + + if (!j || it->it_age < small) { + small = it->it_age; + small_pos = j; + } + } + + return small_pos; +} + +static int cache_is_cached(ram_addr_t addr) +{ + unsigned long pos = cache_get_cache_pos(addr); + + assert(page_cache); + CacheBucket *bucket = &page_cache[pos]; + return cache_get_newest(bucket, addr); +} + +static void cache_insert(unsigned long addr, uint8_t *pdata) +{ + unsigned long pos; + int slot = -1; + CacheBucket *bucket; + + pos = cache_get_cache_pos(addr); + assert(page_cache); + bucket = &page_cache[pos]; + slot = cache_get_oldest(bucket); /* evict LRU */ + + /* actual update of entry */ + CacheItem *it = cache_item_get(pos, slot); + if (!it->it_data) { + cache_num_items++; + } + g_free(it->it_data); + + it->it_data = g_malloc0(TARGET_PAGE_SIZE); + memcpy(it->it_data, pdata, TARGET_PAGE_SIZE); + it->it_age = ++cache_max_item_age; + it->it_addr = addr; +} + static int is_dup_page(uint8_t *page, uint8_t ch) { uint32_t val = ch << 24 | ch << 16 | ch << 8 | ch; -- 1.7.6.5