Patchwork [04/11] Add cache handling functions

login
register
mail settings
Submitter Orit Wasserman
Date July 25, 2012, 2:50 p.m.
Message ID <1343227834-5400-6-git-send-email-owasserm@redhat.com>
Download mbox | patch
Permalink /patch/173182/
State New
Headers show

Comments

Orit Wasserman - July 25, 2012, 2:50 p.m.
Add LRU page cache mechanism.
The page are accessed by their address.

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>
Signed-off-by: Orit Wasserman <owasserm@redhat.com>
---
 Makefile.objs             |    1 +
 cutils.c                  |    9 ++
 include/qemu/page_cache.h |   79 ++++++++++++++++
 page_cache.c              |  216 +++++++++++++++++++++++++++++++++++++++++++++
 qemu-common.h             |   13 +++
 5 files changed, 318 insertions(+), 0 deletions(-)
 create mode 100644 include/qemu/page_cache.h
 create mode 100644 page_cache.c
Eric Blake - July 26, 2012, 9:51 p.m.
On 07/25/2012 08:50 AM, Orit Wasserman wrote:
> Add LRU page cache mechanism.
> The page are accessed by their address.
> 
> 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>
> Signed-off-by: Orit Wasserman <owasserm@redhat.com>

> +
> +PageCache *cache_init(int64_t num_pages, unsigned int page_size)
> +{
> +    int64_t i;
> +
> +    PageCache *cache = g_malloc(sizeof(*cache));
> +
> +    if (num_pages <= 0) {
> +        DPRINTF("invalid number of pages\n");
> +        return NULL;

Unless memory returned by g_malloc() is automatically garbage collected,
then this is a memory leak.

> +static unsigned long cache_get_cache_pos(const PageCache *cache,
> +                                         uint64_t address)
> +{
> +    unsigned long pos;

On a 32-bit platform, this could be 32 bits...

> +
> +    g_assert(cache->max_num_items);
> +    pos = (address / cache->page_size) & (cache->max_num_items - 1);

while cache->max_num_items is int64_t and could thus overflow.  Then
again, a 32-bit platform can't access more than 4G memory, so I think
this limitation is theoretical; still, I can't help but wonder if you
should be consistently using size_t instead of a mix of 'unsigned int',
'int32_t', and 'unsigned long' in referring to sizing within your cache
table.

> +int64_t cache_resize(PageCache *cache, int64_t new_num_pages)
> +{

> +
> +    /* move all data from old cache */
> +    for (i = 0; i < cache->max_num_items; i++) {
> +        old_it = &cache->page_cache[i];
> +        if (old_it->it_addr != -1) {
> +            /* check for collision , if there is, keep the first value */

No space before ',' in English sentences.

The comment about 'keep the first value' is wrong, you are keeping the
'MRU page'...

> +            new_it = cache_get_by_addr(new_cache, old_it->it_addr);
> +            if (new_it->it_data) {
> +                /* keep the oldest page */

...also wrong, you are keeping the MRU page, not the oldest page...

> +                if (new_it->it_age >= old_it->it_age) {
> +                    g_free(old_it->it_data);

since a larger it_age implies more recently used.

> +++ b/qemu-common.h
> @@ -1,3 +1,4 @@
> +
>  /* Common header file that is included by all of qemu.  */
>  #ifndef QEMU_COMMON_H
>  #define QEMU_COMMON_H
> @@ -411,6 +412,18 @@ static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
>  /* Round number up to multiple */
>  #define QEMU_ALIGN_UP(n, m) QEMU_ALIGN_DOWN((n) + (m) - 1, (m))
>  
> +static inline bool is_power_of_2(int64_t value)
> +{
> +    if (!value) {
> +        return 0;
> +    }
> +
> +    return !(value & (value - 1));

Technically undefined by C99 if value is INT64_MIN, since 'value - 1'
then overflows.  Do you want this function to take uint64_t instead, to
guarantee defined results even for 0x8000000000000000?
Orit Wasserman - July 29, 2012, 6:16 a.m.
On 07/27/2012 12:51 AM, Eric Blake wrote:
> On 07/25/2012 08:50 AM, Orit Wasserman wrote:
>> Add LRU page cache mechanism.
>> The page are accessed by their address.
>>
>> 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>
>> Signed-off-by: Orit Wasserman <owasserm@redhat.com>
> 
>> +
>> +PageCache *cache_init(int64_t num_pages, unsigned int page_size)
>> +{
>> +    int64_t i;
>> +
>> +    PageCache *cache = g_malloc(sizeof(*cache));
>> +
>> +    if (num_pages <= 0) {
>> +        DPRINTF("invalid number of pages\n");
>> +        return NULL;
> 
> Unless memory returned by g_malloc() is automatically garbage collected,
> then this is a memory leak.
> 
good catch I will move the check up.
>> +static unsigned long cache_get_cache_pos(const PageCache *cache,
>> +                                         uint64_t address)
>> +{
>> +    unsigned long pos;
> 
> On a 32-bit platform, this could be 32 bits...
I will switch it to  uint64_t.
> 
>> +
>> +    g_assert(cache->max_num_items);
>> +    pos = (address / cache->page_size) & (cache->max_num_items - 1);
> 
> while cache->max_num_items is int64_t and could thus overflow.  Then
> again, a 32-bit platform can't access more than 4G memory, so I think
> this limitation is theoretical; still, I can't help but wonder if you
> should be consistently using size_t instead of a mix of 'unsigned int',
> 'int32_t', and 'unsigned long' in referring to sizing within your cache
> table.
> 
same here
>> +int64_t cache_resize(PageCache *cache, int64_t new_num_pages)
>> +{
> 
>> +
>> +    /* move all data from old cache */
>> +    for (i = 0; i < cache->max_num_items; i++) {
>> +        old_it = &cache->page_cache[i];
>> +        if (old_it->it_addr != -1) {
>> +            /* check for collision , if there is, keep the first value */
> 
> No space before ',' in English sentences.
> 
> The comment about 'keep the first value' is wrong, you are keeping the
> 'MRU page'...
> 
I will fix it
>> +            new_it = cache_get_by_addr(new_cache, old_it->it_addr);
>> +            if (new_it->it_data) {
>> +                /* keep the oldest page */
> 
> ...also wrong, you are keeping the MRU page, not the oldest page...
here too
> 
>> +                if (new_it->it_age >= old_it->it_age) {
>> +                    g_free(old_it->it_data);
> 
> since a larger it_age implies more recently used.
> 
>> +++ b/qemu-common.h
>> @@ -1,3 +1,4 @@
>> +
>>  /* Common header file that is included by all of qemu.  */
>>  #ifndef QEMU_COMMON_H
>>  #define QEMU_COMMON_H
>> @@ -411,6 +412,18 @@ static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
>>  /* Round number up to multiple */
>>  #define QEMU_ALIGN_UP(n, m) QEMU_ALIGN_DOWN((n) + (m) - 1, (m))
>>  
>> +static inline bool is_power_of_2(int64_t value)
>> +{
>> +    if (!value) {
>> +        return 0;
>> +    }
>> +
>> +    return !(value & (value - 1));
> 
> Technically undefined by C99 if value is INT64_MIN, since 'value - 1'
> then overflows.  Do you want this function to take uint64_t instead, to
> guarantee defined results even for 0x8000000000000000?
> 
good idea.

Thanks,
Orit

Patch

diff --git a/Makefile.objs b/Makefile.objs
index 5ebbcfa..e0fb69b 100644
--- a/Makefile.objs
+++ b/Makefile.objs
@@ -77,6 +77,7 @@  common-obj-y += qemu-char.o #aio.o
 common-obj-y += block-migration.o iohandler.o
 common-obj-y += pflib.o
 common-obj-y += bitmap.o bitops.o
+common-obj-y += page_cache.o
 
 common-obj-$(CONFIG_POSIX) += migration-exec.o migration-unix.o migration-fd.o
 common-obj-$(CONFIG_WIN32) += version.o
diff --git a/cutils.c b/cutils.c
index e2bc1b8..b0bdd4b 100644
--- a/cutils.c
+++ b/cutils.c
@@ -375,3 +375,12 @@  int qemu_parse_fd(const char *param)
     }
     return fd;
 }
+
+/* round down to the nearest power of 2*/
+int64_t pow2floor(int64_t value)
+{
+    if (!is_power_of_2(value)) {
+        value = 0x8000000000000000ULL >> clz64(value);
+    }
+    return value;
+}
diff --git a/include/qemu/page_cache.h b/include/qemu/page_cache.h
new file mode 100644
index 0000000..3839ac7
--- /dev/null
+++ b/include/qemu/page_cache.h
@@ -0,0 +1,79 @@ 
+/*
+ * Page cache for QEMU
+ * The cache is base on a hash of the page address
+ *
+ * Copyright 2012 Red Hat, Inc. and/or its affiliates
+ *
+ * Authors:
+ *  Orit Wasserman  <owasserm@redhat.com>
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2 or later.
+ * See the COPYING file in the top-level directory.
+ *
+ */
+
+#ifndef PAGE_CACHE_H
+#define PAGE_CACHE_H
+
+/* Page cache for storing guest pages */
+typedef struct PageCache PageCache;
+
+/**
+ * cache_init: Initialize the page cache
+ *
+ *
+ * Returns new allocated cache or NULL on error
+ *
+ * @cache pointer to the PageCache struct
+ * @num_pages: cache maximal number of cached pages
+ * @page_size: cache page size
+ */
+PageCache *cache_init(int64_t num_pages, unsigned int page_size);
+
+/**
+ * cache_fini: free all cache resources
+ * @cache pointer to the PageCache struct
+ */
+void cache_fini(PageCache *cache);
+
+/**
+ * cache_is_cached: Checks to see if the page is cached
+ *
+ * Returns %true if page is cached
+ *
+ * @cache pointer to the PageCache struct
+ * @addr: page addr
+ */
+bool cache_is_cached(const PageCache *cache, uint64_t addr);
+
+/**
+ * get_cached_data: Get the data cached for an addr
+ *
+ * Returns pointer to the data cached or NULL if not cached
+ *
+ * @cache pointer to the PageCache struct
+ * @addr: page addr
+ */
+uint8_t *get_cached_data(const PageCache *cache, uint64_t addr);
+
+/**
+ * cache_insert: insert the page into the cache. the previous value will be overwritten
+ *
+ * @cache pointer to the PageCache struct
+ * @addr: page address
+ * @pdata: pointer to the page
+ */
+void cache_insert(PageCache *cache, uint64_t addr, uint8_t *pdata);
+
+/**
+ * cache_resize: resize the page cache. In case of size reduction the extra
+ * pages will be freed
+ *
+ * Returns -1 on error new cache size on success
+ *
+ * @cache pointer to the PageCache struct
+ * @num_pages: new page cache size (in pages)
+ */
+int64_t cache_resize(PageCache *cache, int64_t num_pages);
+
+#endif
diff --git a/page_cache.c b/page_cache.c
new file mode 100644
index 0000000..8110273
--- /dev/null
+++ b/page_cache.c
@@ -0,0 +1,216 @@ 
+/*
+ * Page cache for QEMU
+ * The cache is base on a hash of the page address
+ *
+ * Copyright 2012 Red Hat, Inc. and/or its affiliates
+ *
+ * Authors:
+ *  Orit Wasserman  <owasserm@redhat.com>
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2 or later.
+ * See the COPYING file in the top-level directory.
+ *
+ */
+
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <strings.h>
+#include <string.h>
+#include <sys/time.h>
+#include <sys/types.h>
+#include <stdbool.h>
+#include <glib.h>
+#include <strings.h>
+
+#include "qemu-common.h"
+#include "qemu/page_cache.h"
+
+#ifdef DEBUG_CACHE
+#define DPRINTF(fmt, ...) \
+    do { fprintf(stdout, "cache: " fmt, ## __VA_ARGS__); } while (0)
+#else
+#define DPRINTF(fmt, ...) \
+    do { } while (0)
+#endif
+
+typedef struct CacheItem CacheItem;
+
+struct CacheItem {
+    uint64_t it_addr;
+    uint64_t it_age;
+    uint8_t *it_data;
+};
+
+struct PageCache {
+    CacheItem *page_cache;
+    unsigned int page_size;
+    int64_t max_num_items;
+    uint64_t max_item_age;
+    int64_t num_items;
+};
+
+PageCache *cache_init(int64_t num_pages, unsigned int page_size)
+{
+    int64_t i;
+
+    PageCache *cache = g_malloc(sizeof(*cache));
+
+    if (num_pages <= 0) {
+        DPRINTF("invalid number of pages\n");
+        return NULL;
+    }
+
+    /* round down to the nearest power of 2 */
+    if (!is_power_of_2(num_pages)) {
+        num_pages = pow2floor(num_pages);
+        DPRINTF("rounding down to %" PRId64 "\n", num_pages);
+    }
+    cache->page_size = page_size;
+    cache->num_items = 0;
+    cache->max_item_age = 0;
+    cache->max_num_items = num_pages;
+
+    DPRINTF("Setting cache buckets to %" PRId64 "\n", cache->max_num_items);
+
+    cache->page_cache = g_malloc((cache->max_num_items) *
+                                 sizeof(*cache->page_cache));
+
+    for (i = 0; i < cache->max_num_items; i++) {
+        cache->page_cache[i].it_data = NULL;
+        cache->page_cache[i].it_age = 0;
+        cache->page_cache[i].it_addr = -1;
+    }
+
+    return cache;
+}
+
+void cache_fini(PageCache *cache)
+{
+    int64_t i;
+
+    g_assert(cache);
+    g_assert(cache->page_cache);
+
+    for (i = 0; i < cache->max_num_items; i++) {
+        g_free(cache->page_cache[i].it_data);
+    }
+
+    g_free(cache->page_cache);
+    cache->page_cache = NULL;
+}
+
+static unsigned long cache_get_cache_pos(const PageCache *cache,
+                                         uint64_t address)
+{
+    unsigned long pos;
+
+    g_assert(cache->max_num_items);
+    pos = (address / cache->page_size) & (cache->max_num_items - 1);
+    return pos;
+}
+
+bool cache_is_cached(const PageCache *cache, uint64_t addr)
+{
+    unsigned long pos;
+
+    g_assert(cache);
+    g_assert(cache->page_cache);
+
+    pos = cache_get_cache_pos(cache, addr);
+
+    return (cache->page_cache[pos].it_addr == addr);
+}
+
+static CacheItem *cache_get_by_addr(const PageCache *cache, uint64_t addr)
+{
+    unsigned long pos;
+
+    g_assert(cache);
+    g_assert(cache->page_cache);
+
+    pos = cache_get_cache_pos(cache, addr);
+
+    return &cache->page_cache[pos];
+}
+
+uint8_t *get_cached_data(const PageCache *cache, uint64_t addr)
+{
+    return cache_get_by_addr(cache, addr)->it_data;
+}
+
+void cache_insert(PageCache *cache, uint64_t addr, uint8_t *pdata)
+{
+
+    CacheItem *it = NULL;
+
+    g_assert(cache);
+    g_assert(cache->page_cache);
+
+    /* actual update of entry */
+    it = cache_get_by_addr(cache, addr);
+
+    if (!it->it_data) {
+        cache->num_items++;
+    }
+
+    it->it_data = pdata;
+    it->it_age = ++cache->max_item_age;
+    it->it_addr = addr;
+}
+
+int64_t cache_resize(PageCache *cache, int64_t new_num_pages)
+{
+    PageCache *new_cache;
+    int64_t i;
+
+    CacheItem *old_it, *new_it;
+
+    g_assert(cache);
+
+    /* cache was not inited */
+    if (cache->page_cache == NULL) {
+        return -1;
+    }
+
+    /* same size */
+    if (pow2floor(new_num_pages) == cache->max_num_items) {
+        return cache->max_num_items;
+    }
+
+    new_cache = cache_init(new_num_pages, cache->page_size);
+    if (!(new_cache)) {
+        DPRINTF("Error creating new cache\n");
+        return -1;
+    }
+
+    /* move all data from old cache */
+    for (i = 0; i < cache->max_num_items; i++) {
+        old_it = &cache->page_cache[i];
+        if (old_it->it_addr != -1) {
+            /* check for collision , if there is, keep the first value */
+            new_it = cache_get_by_addr(new_cache, old_it->it_addr);
+            if (new_it->it_data) {
+                /* keep the oldest page */
+                if (new_it->it_age >= old_it->it_age) {
+                    g_free(old_it->it_data);
+                } else {
+                    g_free(new_it->it_data);
+                    new_it->it_data = old_it->it_data;
+                    new_it->it_age = old_it->it_age;
+                    new_it->it_addr = old_it->it_addr;
+                }
+            } else {
+                cache_insert(new_cache, old_it->it_addr, old_it->it_data);
+            }
+        }
+    }
+
+    cache->page_cache = new_cache->page_cache;
+    cache->max_num_items = new_cache->max_num_items;
+    cache->num_items = new_cache->num_items;
+
+    g_free(new_cache);
+
+    return cache->max_num_items;
+}
diff --git a/qemu-common.h b/qemu-common.h
index 09676f5..195bab5 100644
--- a/qemu-common.h
+++ b/qemu-common.h
@@ -1,3 +1,4 @@ 
+
 /* Common header file that is included by all of qemu.  */
 #ifndef QEMU_COMMON_H
 #define QEMU_COMMON_H
@@ -411,6 +412,18 @@  static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
 /* Round number up to multiple */
 #define QEMU_ALIGN_UP(n, m) QEMU_ALIGN_DOWN((n) + (m) - 1, (m))
 
+static inline bool is_power_of_2(int64_t value)
+{
+    if (!value) {
+        return 0;
+    }
+
+    return !(value & (value - 1));
+}
+
+/* round down to the nearest power of 2*/
+int64_t pow2floor(int64_t value);
+
 #include "module.h"
 
 #endif