Patchwork [v9,01/10] Add cache handling functions

login
register
mail settings
Submitter Orit Wasserman
Date April 11, 2012, 6:49 p.m.
Message ID <1334170153-9503-2-git-send-email-owasserm@redhat.com>
Download mbox | patch
Permalink /patch/151852/
State New
Headers show

Comments

Orit Wasserman - April 11, 2012, 6:49 p.m.
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(-)
Juan Quintela - April 18, 2012, 2:34 p.m.
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.
Orit Wasserman - April 18, 2012, 4:23 p.m.
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.
Anthony Liguori - April 18, 2012, 5:19 p.m.
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;
>
Juan Quintela - April 18, 2012, 5:44 p.m.
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.
Orit Wasserman - April 19, 2012, 6:32 a.m.
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;
>>
>
Jianjun Kong - April 19, 2012, 10:48 p.m.
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/

...

Patch

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;