Message ID | 1334170153-9503-2-git-send-email-owasserm@redhat.com |
---|---|
State | New |
Headers | show |
Orit Wasserman <owasserm@redhat.com> wrote: > Add LRU page cache mechanism. > The page are accessed by their address. > > + > +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; I will put this 3 variables inside CacheBucket, just to make clear that they are related. > + > +static void cache_init(int64_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, int use_buffer); > +static unsigned long cache_get_cache_pos(ram_addr_t address); > +static CacheItem *cache_item_get(unsigned long pos, int item); > +static void cache_resize(int64_t new_size); None of this are needed. Notice that cache_resize is not marked static later. > + > +/***********************************************************/ We normally don't use this to split code O:-) > +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); Do we check that num_bytes is not negative? I can't see. > + assert(cache_num_buckets); > + DPRINTF("Setting cache buckets to %lu\n", cache_num_buckets); > + > + assert(!page_cache); Only user of this function make page_cache = NULL before calling. Returning an error looks more sensible, but haven't yet looked at the next patechs to see if we have a way to do anything good with the error. > + page_cache = (CacheBucket *)g_malloc((cache_num_buckets) * > + sizeof(CacheBucket)); g_malloc() returns void * (well gpointer, but that is void*). We don't need to cast its return. > +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); > +} Can we make this function return a bool? Basically we put that anything != -1 means cached, -1 means non-cached. > + > +static void cache_insert(unsigned long addr, uint8_t *pdata, int > use_buffer) Change use_buffer to a bool? or even better, just remove the parameter altogether and change inteface to: cache_insert(addr, foo, 1) -> cache_insert(addr, foo) cache_insert(addr, foo, 0) -> cache_insert(addr, g_memdup(foo,TARGET_PAGE_SIZE)) and remove all the use_buffer() code? > +{ > + unsigned long pos; > + int slot = -1; > + CacheBucket *bucket; > + > + pos = cache_get_cache_pos(addr); > + assert(page_cache); Function call in previous line already use page_cache, switch lines or just remove the assert? > +void cache_resize(int64_t new_size) > +{ > + int64_t new_num_buckets = new_size/(TARGET_PAGE_SIZE * CACHE_N_WAY); > + CacheBucket *old_page_cache = page_cache; > + int i; > + int64_t old_num_buckets = cache_num_buckets; > + > + /* same size */ > + if (new_num_buckets == cache_num_buckets) { > + return; > + } Shouldn't we check that new_num_buckets makes sense? > + /* cache was not inited */ > + if (page_cache == NULL) { > + return; > + } > + > + /* create a new cache */ > + page_cache = NULL; > + cache_init(new_size); Later, Juan.
On 04/18/2012 05:34 PM, Juan Quintela wrote: > Orit Wasserman <owasserm@redhat.com> wrote: >> Add LRU page cache mechanism. >> The page are accessed by their address. >> >> + >> +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; > > I will put this 3 variables inside CacheBucket, just to make clear that > they are related. OK. > >> + >> +static void cache_init(int64_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, int use_buffer); >> +static unsigned long cache_get_cache_pos(ram_addr_t address); >> +static CacheItem *cache_item_get(unsigned long pos, int item); >> +static void cache_resize(int64_t new_size); > > None of this are needed. Notice that cache_resize is not marked static later. > > >> + >> +/***********************************************************/ > > We normally don't use this to split code O:-) Will be removed ... > >> +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); > > Do we check that num_bytes is not negative? I can't see. I will add a check . > >> + assert(cache_num_buckets); >> + DPRINTF("Setting cache buckets to %lu\n", cache_num_buckets); >> + >> + assert(!page_cache); > > Only user of this function make page_cache = NULL before calling. > Returning an error looks more sensible, but haven't yet looked at the > next patechs to see if we have a way to do anything good with the error. I guess we can fail the migration in case of an error. > >> + page_cache = (CacheBucket *)g_malloc((cache_num_buckets) * >> + sizeof(CacheBucket)); > > g_malloc() returns void * (well gpointer, but that is void*). We don't > need to cast its return. Will be fixed > >> +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); >> +} > > Can we make this function return a bool? Basically we put that anything > != -1 means cached, -1 means non-cached. > sure >> + >> +static void cache_insert(unsigned long addr, uint8_t *pdata, int >> use_buffer) > > Change use_buffer to a bool? > > or even better, just remove the parameter altogether and change inteface > to: > > cache_insert(addr, foo, 1) -> cache_insert(addr, foo) > cache_insert(addr, foo, 0) -> cache_insert(addr, g_memdup(foo,TARGET_PAGE_SIZE)) > > and remove all the use_buffer() code? > >> +{ >> + unsigned long pos; >> + int slot = -1; >> + CacheBucket *bucket; >> + >> + pos = cache_get_cache_pos(addr); >> + assert(page_cache); > > Function call in previous line already use page_cache, switch lines or just remove > the assert? The assert should be first . > > >> +void cache_resize(int64_t new_size) >> +{ >> + int64_t new_num_buckets = new_size/(TARGET_PAGE_SIZE * CACHE_N_WAY); >> + CacheBucket *old_page_cache = page_cache; >> + int i; >> + int64_t old_num_buckets = cache_num_buckets; >> + >> + /* same size */ >> + if (new_num_buckets == cache_num_buckets) { >> + return; >> + } > > Shouldn't we check that new_num_buckets makes sense? The checks are done in the calling function (patch 9) . Do you think I should move them here ? Orit > >> + /* cache was not inited */ >> + if (page_cache == NULL) { >> + return; >> + } >> + >> + /* create a new cache */ >> + page_cache = NULL; >> + cache_init(new_size); > > Later, Juan.
On 04/11/2012 01:49 PM, Orit Wasserman wrote: > Add LRU page cache mechanism. > The page are accessed by their address. > > Signed-off-by: Orit Wasserman<owasserm@redhat.com> > Signed-off-by: Benoit Hudzia<benoit.hudzia@sap.com> > Signed-off-by: Petter Svard<petters@cs.umu.se> > Signed-off-by: Aidan Shribman<aidan.shribman@sap.com> > --- > arch_init.c | 220 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ > 1 files changed, 220 insertions(+), 0 deletions(-) > > diff --git a/arch_init.c b/arch_init.c > index 595badf..2e534f1 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" > @@ -44,6 +45,14 @@ > #include "exec-memory.h" > #include "hw/pcspk.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; > @@ -127,6 +136,217 @@ static int is_dup_page(uint8_t *page) > return 1; > } > > +/***********************************************************/ > +/* Page cache for storing previous pages as basis for XBZRLE 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(int64_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, int use_buffer); > +static unsigned long cache_get_cache_pos(ram_addr_t address); > +static CacheItem *cache_item_get(unsigned long pos, int item); > +static void cache_resize(int64_t new_size); > + > +/***********************************************************/ > +/* 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) If we're caching pages, let's take a num_pages argument. Then we can avoid TARGET_PAGE_SIZE and move this to it's own cache.c file and build it once. Let's also make a proper header (include/qemu/cache.h) and document the public functions. I really am not convinced we need a custom data structure here but if we're going to add one, we should make at least a small attempt to make it reusable. > +{ > + 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); use g_assert instead and drop the explicit include of assert.h > + DPRINTF("Setting cache buckets to %lu\n", cache_num_buckets); > + > + assert(!page_cache); return page_cache instead of using a global > + page_cache = (CacheBucket *)g_malloc((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; Take page_cache as an argument here. > + 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); And here, etc. > + 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, int use_buffer) > +{ > + 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); This is done a lot. We don't use C99 declarations in QEMU. Please move all the variable declarations to the top of the functions. Regards, Anthony Liguori > + if (!it->it_data) { > + if (!use_buffer) { > + it->it_data = g_malloc(TARGET_PAGE_SIZE); > + } > + cache_num_items++; > + } > + > + if (!use_buffer) { > + memcpy(it->it_data, pdata, TARGET_PAGE_SIZE); > + } else { > + it->it_data = pdata; > + } > + it->it_age = ++cache_max_item_age; > + it->it_addr = addr; > +} > + > +void cache_resize(int64_t new_size) > +{ > + int64_t new_num_buckets = new_size/(TARGET_PAGE_SIZE * CACHE_N_WAY); > + CacheBucket *old_page_cache = page_cache; > + int i; > + int64_t old_num_buckets = cache_num_buckets; > + > + /* same size */ > + if (new_num_buckets == cache_num_buckets) { > + return; > + } > + /* cache was not inited */ > + if (page_cache == NULL) { > + return; > + } > + > + /* create a new cache */ > + page_cache = NULL; > + cache_init(new_size); > + > + /* move all data from old cache */ > + for (i = 0; i< old_num_buckets; i++) { > + int j; > + for (j = 0; j< CACHE_N_WAY; j++) { > + CacheItem *it =&old_page_cache[i].bkt_item[j]; > + if (it->it_addr != -1) { > + /* check for collision , if there is keep the first value */ > + if (cache_is_cached(it->it_addr) != -1) { > + g_free(it->it_data); > + } else { > + cache_insert(it->it_addr, it->it_data, 1); > + } > + } > + } > + } > + > + g_free(old_page_cache); > +} > + > static RAMBlock *last_block; > static ram_addr_t last_offset; >
Orit Wasserman <owasserm@redhat.com> wrote: > On 04/18/2012 05:34 PM, Juan Quintela wrote: >>> + assert(cache_num_buckets); >>> + DPRINTF("Setting cache buckets to %lu\n", cache_num_buckets); >>> + >>> + assert(!page_cache); >> >> Only user of this function make page_cache = NULL before calling. >> Returning an error looks more sensible, but haven't yet looked at the >> next patechs to see if we have a way to do anything good with the error. > > I guess we can fail the migration in case of an error. > Yeap. >>> +void cache_resize(int64_t new_size) >>> +{ >>> + int64_t new_num_buckets = new_size/(TARGET_PAGE_SIZE * CACHE_N_WAY); >>> + CacheBucket *old_page_cache = page_cache; >>> + int i; >>> + int64_t old_num_buckets = cache_num_buckets; >>> + >>> + /* same size */ >>> + if (new_num_buckets == cache_num_buckets) { >>> + return; >>> + } >> >> Shouldn't we check that new_num_buckets makes sense? > > The checks are done in the calling function (patch 9) . Do you think I > should move them here ? I think they are not. But what I mean is that they need to be done in one place. probably in patch 9 is a better place. Later, Juan.
On 04/18/2012 08:19 PM, Anthony Liguori wrote: > On 04/11/2012 01:49 PM, Orit Wasserman wrote: >> Add LRU page cache mechanism. >> The page are accessed by their address. >> >> Signed-off-by: Orit Wasserman<owasserm@redhat.com> >> Signed-off-by: Benoit Hudzia<benoit.hudzia@sap.com> >> Signed-off-by: Petter Svard<petters@cs.umu.se> >> Signed-off-by: Aidan Shribman<aidan.shribman@sap.com> >> --- >> arch_init.c | 220 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ >> 1 files changed, 220 insertions(+), 0 deletions(-) >> >> diff --git a/arch_init.c b/arch_init.c >> index 595badf..2e534f1 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" >> @@ -44,6 +45,14 @@ >> #include "exec-memory.h" >> #include "hw/pcspk.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; >> @@ -127,6 +136,217 @@ static int is_dup_page(uint8_t *page) >> return 1; >> } >> >> +/***********************************************************/ >> +/* Page cache for storing previous pages as basis for XBZRLE 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(int64_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, int use_buffer); >> +static unsigned long cache_get_cache_pos(ram_addr_t address); >> +static CacheItem *cache_item_get(unsigned long pos, int item); >> +static void cache_resize(int64_t new_size); >> + >> +/***********************************************************/ >> +/* 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) > > If we're caching pages, let's take a num_pages argument. Then we can avoid TARGET_PAGE_SIZE and move this to it's own cache.c file and build it once. > > Let's also make a proper header (include/qemu/cache.h) and document the public functions. I really am not convinced we need a custom data structure here but if we're going to add one, we should make at least a small attempt to make it reusable. I will look again into glib to see if I can find a data structure I can use. If not, I will add the cache.h/cache.c and the documentation. > >> +{ >> + 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); > > use g_assert instead and drop the explicit include of assert.h > >> + DPRINTF("Setting cache buckets to %lu\n", cache_num_buckets); >> + >> + assert(!page_cache); > > return page_cache instead of using a global OK > >> + page_cache = (CacheBucket *)g_malloc((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; > > > Take page_cache as an argument here. OK > >> + 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); > > And here, etc. OK > >> + 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, int use_buffer) >> +{ >> + 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); > > This is done a lot. We don't use C99 declarations in QEMU. Please move all the variable declarations to the top of the functions. OK Thanks, Orit > > Regards, > > Anthony Liguori > > >> + if (!it->it_data) { >> + if (!use_buffer) { >> + it->it_data = g_malloc(TARGET_PAGE_SIZE); >> + } >> + cache_num_items++; >> + } >> + >> + if (!use_buffer) { >> + memcpy(it->it_data, pdata, TARGET_PAGE_SIZE); >> + } else { >> + it->it_data = pdata; >> + } >> + it->it_age = ++cache_max_item_age; >> + it->it_addr = addr; >> +} >> + >> +void cache_resize(int64_t new_size) >> +{ >> + int64_t new_num_buckets = new_size/(TARGET_PAGE_SIZE * CACHE_N_WAY); >> + CacheBucket *old_page_cache = page_cache; >> + int i; >> + int64_t old_num_buckets = cache_num_buckets; >> + >> + /* same size */ >> + if (new_num_buckets == cache_num_buckets) { >> + return; >> + } >> + /* cache was not inited */ >> + if (page_cache == NULL) { >> + return; >> + } >> + >> + /* create a new cache */ >> + page_cache = NULL; >> + cache_init(new_size); >> + >> + /* move all data from old cache */ >> + for (i = 0; i< old_num_buckets; i++) { >> + int j; >> + for (j = 0; j< CACHE_N_WAY; j++) { >> + CacheItem *it =&old_page_cache[i].bkt_item[j]; >> + if (it->it_addr != -1) { >> + /* check for collision , if there is keep the first value */ >> + if (cache_is_cached(it->it_addr) != -1) { >> + g_free(it->it_data); >> + } else { >> + cache_insert(it->it_addr, it->it_data, 1); >> + } >> + } >> + } >> + } >> + >> + g_free(old_page_cache); >> +} >> + >> static RAMBlock *last_block; >> static ram_addr_t last_offset; >> >
On Thu, Apr 12, 2012 at 2:49 AM, Orit Wasserman <owasserm@redhat.com> wrote: > Add LRU page cache mechanism. > The page are accessed by their address. > > Signed-off-by: Orit Wasserman <owasserm@redhat.com> > Signed-off-by: Benoit Hudzia <benoit.hudzia@sap.com> > Signed-off-by: Petter Svard <petters@cs.umu.se> > Signed-off-by: Aidan Shribman <aidan.shribman@sap.com> > --- > arch_init.c | 220 > +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ > 1 files changed, 220 insertions(+), 0 deletions(-) > > diff --git a/arch_init.c b/arch_init.c > index 595badf..2e534f1 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" > @@ -44,6 +45,14 @@ > #include "exec-memory.h" > #include "hw/pcspk.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; > @@ -127,6 +136,217 @@ static int is_dup_page(uint8_t *page) > return 1; > } > > +/***********************************************************/ > +/* Page cache for storing previous pages as basis for XBZRLE compression > */ > +#define CACHE_N_WAY 2 /* 2-way assossiative cache */ > typo, %s/assossiative/associative/ ...
diff --git a/arch_init.c b/arch_init.c index 595badf..2e534f1 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" @@ -44,6 +45,14 @@ #include "exec-memory.h" #include "hw/pcspk.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; @@ -127,6 +136,217 @@ static int is_dup_page(uint8_t *page) return 1; } +/***********************************************************/ +/* Page cache for storing previous pages as basis for XBZRLE 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(int64_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, int use_buffer); +static unsigned long cache_get_cache_pos(ram_addr_t address); +static CacheItem *cache_item_get(unsigned long pos, int item); +static void cache_resize(int64_t new_size); + +/***********************************************************/ +/* 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_malloc((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, int use_buffer) +{ + 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) { + if (!use_buffer) { + it->it_data = g_malloc(TARGET_PAGE_SIZE); + } + cache_num_items++; + } + + if (!use_buffer) { + memcpy(it->it_data, pdata, TARGET_PAGE_SIZE); + } else { + it->it_data = pdata; + } + it->it_age = ++cache_max_item_age; + it->it_addr = addr; +} + +void cache_resize(int64_t new_size) +{ + int64_t new_num_buckets = new_size/(TARGET_PAGE_SIZE * CACHE_N_WAY); + CacheBucket *old_page_cache = page_cache; + int i; + int64_t old_num_buckets = cache_num_buckets; + + /* same size */ + if (new_num_buckets == cache_num_buckets) { + return; + } + /* cache was not inited */ + if (page_cache == NULL) { + return; + } + + /* create a new cache */ + page_cache = NULL; + cache_init(new_size); + + /* move all data from old cache */ + for (i = 0; i < old_num_buckets; i++) { + int j; + for (j = 0; j < CACHE_N_WAY; j++) { + CacheItem *it = &old_page_cache[i].bkt_item[j]; + if (it->it_addr != -1) { + /* check for collision , if there is keep the first value */ + if (cache_is_cached(it->it_addr) != -1) { + g_free(it->it_data); + } else { + cache_insert(it->it_addr, it->it_data, 1); + } + } + } + } + + g_free(old_page_cache); +} + static RAMBlock *last_block; static ram_addr_t last_offset;