Patchwork [v5,1/9] Add cache handling functions

login
register
mail settings
Submitter Orit Wasserman
Date Jan. 3, 2012, 3:34 p.m.
Message ID <1325604879-15862-2-git-send-email-owasserm@redhat.com>
Download mbox | patch
Permalink /patch/134019/
State New
Headers show

Comments

Orit Wasserman - Jan. 3, 2012, 3:34 p.m.
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(-)
Anthony Liguori - Jan. 3, 2012, 7:54 p.m.
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
Orit Wasserman - Jan. 4, 2012, 9:29 a.m.
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
Stefan Hajnoczi - Jan. 4, 2012, 11:46 a.m.
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);
Orit Wasserman - Jan. 4, 2012, 1:27 p.m.
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);
Michael Roth - Jan. 4, 2012, 10:20 p.m.
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
>
>

Patch

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;