Message ID | 1325604879-15862-2-git-send-email-owasserm@redhat.com |
---|---|
State | New |
Headers | show |
On 01/03/2012 09:34 AM, Orit Wasserman wrote: > Add page caching mechanism. > The pages are stored in the cache ordered by their address. > > Signed-off-by: Orit Wasserman<owasserm@redhat.com> > --- > 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<sys/types.h> > #include<sys/mman.h> > #endif > +#include<assert.h> > #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 */ Is there any reason we can't just use a GCache for this? http://developer.gnome.org/glib/stable/glib-Caches.html Regards, Anthony Liguori
On 01/03/2012 09:54 PM, Anthony Liguori wrote: > On 01/03/2012 09:34 AM, Orit Wasserman wrote: >> Add page caching mechanism. >> The pages are stored in the cache ordered by their address. >> >> Signed-off-by: Orit Wasserman<owasserm@redhat.com> >> --- >> 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<sys/types.h> >> #include<sys/mman.h> >> #endif >> +#include<assert.h> >> #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 */ > > Is there any reason we can't just use a GCache for this? > > http://developer.gnome.org/glib/stable/glib-Caches.html I'm not familiar with I will check. Is it 2-way associative cache ? Orit > > Regards, > > Anthony Liguori
On Tue, Jan 3, 2012 at 3:34 PM, Orit Wasserman <owasserm@redhat.com> wrote: > +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); Where do we guarantee that cache_num_buckets is a power of 2? > +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); If we're evicting an entry: 1. Free existing data. 2. Allocate new data. 3. Zero new data. 4. Memcpy pdata into new data. That does a bunch of extra work. How about: 1. Memcpy pdata over old data. So: if (!it->it_data) { cache_num_items++; it->it_data = g_malloc(TARGET_PAGE_SIZE); } memcpy(it->it_data, pdata, TARGET_PAGE_SIZE);
On 01/04/2012 01:46 PM, Stefan Hajnoczi wrote: > On Tue, Jan 3, 2012 at 3:34 PM, Orit Wasserman <owasserm@redhat.com> wrote: >> +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); > > Where do we guarantee that cache_num_buckets is a power of 2? We should do it to when setting cache size , I will add the check. > >> +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); > > If we're evicting an entry: > 1. Free existing data. > 2. Allocate new data. > 3. Zero new data. > 4. Memcpy pdata into new data. > > That does a bunch of extra work. How about: > 1. Memcpy pdata over old data. I noticed it too , i will fix it in next version. > > So: > if (!it->it_data) { > cache_num_items++; > it->it_data = g_malloc(TARGET_PAGE_SIZE); > } > memcpy(it->it_data, pdata, TARGET_PAGE_SIZE);
On 01/04/2012 03:29 AM, Orit Wasserman wrote: > On 01/03/2012 09:54 PM, Anthony Liguori wrote: >> On 01/03/2012 09:34 AM, Orit Wasserman wrote: >>> Add page caching mechanism. >>> The pages are stored in the cache ordered by their address. >>> >>> Signed-off-by: Orit Wasserman<owasserm@redhat.com> >>> --- >>> 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<sys/types.h> >>> #include<sys/mman.h> >>> #endif >>> +#include<assert.h> >>> #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 */ >> >> Is there any reason we can't just use a GCache for this? >> >> http://developer.gnome.org/glib/stable/glib-Caches.html > I'm not familiar with I will check. > Is it 2-way associative cache ? Not quite...it's a very loose wrapper around GHashTable, which appears to be fully associative in nature. It also doesn't seem to allow you to do a lookup without destroying the table entry =\ (unless you do something hacky like an extra insert beforehand to jack up the refcount). If you go this route you're probably better off looking at GHashTable directly. > > Orit >> >> Regards, >> >> Anthony Liguori > >
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 <sys/types.h> #include <sys/mman.h> #endif +#include <assert.h> #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;
Add page caching mechanism. The pages are stored in the cache ordered by their address. Signed-off-by: Orit Wasserman <owasserm@redhat.com> --- arch_init.c | 183 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 183 insertions(+), 0 deletions(-)