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<owass...@redhat.com>
>> Signed-off-by: Benoit Hudzia<benoit.hud...@sap.com>
>> Signed-off-by: Petter Svard<pett...@cs.umu.se>
>> Signed-off-by: Aidan Shribman<aidan.shrib...@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;
>>
>
