[v14,04/13] Add cache handling functions

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 +
 include/qemu/page_cache.h |   79 +++++++++++++++++
 page_cache.c              |  209 +++++++++++++++++++++++++++++++++++++++++++++
 qemu-common.h             |   18 ++++
 4 files changed, 307 insertions(+), 0 deletions(-)
 create mode 100644 include/qemu/page_cache.h
 create mode 100644 page_cache.c

On Tue, Jul 3, 2012 at 1:52 PM, Orit Wasserman <owasserm@redhat.com> 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>
> ---
>  Makefile.objs             |    1 +
>  include/qemu/page_cache.h |   79 +++++++++++++++++
>  page_cache.c              |  209 +++++++++++++++++++++++++++++++++++++++++++++
>  qemu-common.h             |   18 ++++
>  4 files changed, 307 insertions(+), 0 deletions(-)
>  create mode 100644 include/qemu/page_cache.h
>  create mode 100644 page_cache.c
>
> diff --git a/Makefile.objs b/Makefile.objs
> index 625c4d5..d7a199e 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/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..7122756
> --- /dev/null
> +++ b/page_cache.c
> @@ -0,0 +1,209 @@
> +/*
> + * 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;
> +    unsigned long 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)
> +{
> +    int i;
> +
> +    PageCache *cache = g_malloc(sizeof(PageCache));
> +
> +    if (num_pages <= 0) {
> +        DPRINTF("invalid number pages\n");
> +        return NULL;
> +    }
> +
> +    /* round down to the nearest power of 2 */
> +    if (!is_power_of_2(num_pages)) {
> +        num_pages = round2pow2(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(CacheItem));
> +
> +    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)
> +{
> +    int 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);
> +        cache->page_cache[i].it_data = 0;
> +    }
> +
> +    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, unsigned long 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;
> +    int i;
> +
> +    CacheItem *old_it, *new_it;
> +
> +    g_assert(cache);
> +
> +    /* cache was not inited */
> +    if (cache->page_cache == NULL) {
> +        return -1;
> +    }
> +
> +    /* same size */
> +    if (round2pow2(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) {
> +                g_free(old_it->it_data);
> +            } 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 c8c6b2a..1ce7023 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
> @@ -417,6 +418,23 @@ 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));
> +}
> +
> +static inline int64_t round2pow2(int64_t value)
> +{
> +    while (!is_power_of_2(value)) {
> +        value &=  ~(1 << (ffs(value) - 1));

ffs() only uses 'int', not int64_t.  ffsl() is not universally available.

> +    }
> +    return value;
> +}
> +
>  #include "module.h"
>
>  #endif
> --
> 1.7.7.6
>

On 07/03/2012 01:23 PM, Blue Swirl wrote:

>> +
>> +static inline int64_t round2pow2(int64_t value)

round up or down?

>> +{
>> +    while (!is_power_of_2(value)) {
>> +        value &=  ~(1 << (ffs(value) - 1));
> 
> ffs() only uses 'int', not int64_t.  ffsl() is not universally available.
> 
>> +    }
>> +    return value;
>> +}

Not to mention that iterating one bit at a time is inefficient.  We
already gave you several more efficient solutions; my favorite being:

static inline int64_t pow2floor(int64_t value)
{
    if (!is_power_of_2(value)) {
        value = 0x8000000000000000ULL >> clz64(value);
    }
    return value;
}

since clz64() is already part of qemu sources.

On 07/03/2012 07:52 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)
> +{
> +    int i;

Type mismatch.  Either 'i' needs to be int64_t, or you don't need
num_pages to be 64-bit.  Although I think it will be unlikely to
encounter someone with a desire to use 2**32 pages of 4096 bytes each as
their cache, I can't rule it out, so I think 'i' needs to be bigger
rather than changing your API to be smaller.

> +
> +    PageCache *cache = g_malloc(sizeof(PageCache));

Personally, I like the style g_malloc(sizeof(*cache)), as it is immune
to type changes on cache.  If you later change the type of 'cache', your
style has to make two edits to this line, while my style only makes one
edit.

> +
> +    if (num_pages <= 0) {
> +        DPRINTF("invalid number pages\n");

s/number pages/number of pages/

> +    cache->page_cache = g_malloc((cache->max_num_items) *
> +                                 sizeof(CacheItem));

Here my style is even more useful.  With your style, I have to search
elsewhere in the code to validate that cache->page_cache really does
have the type CacheItem; but my style means I can see the result at once
without having to care about typing:

cache->page_cache = g_malloc(cache->max_num_items *
                             sizeof(*cache->page_cache));

> +void cache_fini(PageCache *cache)
> +{
> +    int i;

Type mismatch again; max_num_items can be larger than INT_MAX, so you
need a bigger type for '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);
> +        cache->page_cache[i].it_data = 0;

Wasted assignment, since you are just about to free cache->page_cache
anyways.

> +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, unsigned long addr, uint8_t *pdata)

Why are you using 'uint64_t addr' in some places, and 'unsigned long
addr' in others?

> +    /* 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 */

s/ ,/,/ (no space before comma in English)

Shouldn't we instead prefer to keep the page with larger age, regardless
of whether we found it first or second?  That is, a cache is more likely
to be useful on most-recently-used pages, rather than on which address
happened to map to the collision first.

On 07/03/2012 10:49 PM, Eric Blake wrote:
> On 07/03/2012 01:23 PM, Blue Swirl wrote:
> 
>>> +
>>> +static inline int64_t round2pow2(int64_t value)
> 
> round up or down?
> 
>>> +{
>>> +    while (!is_power_of_2(value)) {
>>> +        value &=  ~(1 << (ffs(value) - 1));
>>
>> ffs() only uses 'int', not int64_t.  ffsl() is not universally available.
>>
>>> +    }
>>> +    return value;
>>> +}
> 
> Not to mention that iterating one bit at a time is inefficient.  We
> already gave you several more efficient solutions; my favorite being:
> 
> static inline int64_t pow2floor(int64_t value)
> {
>     if (!is_power_of_2(value)) {
>         value = 0x8000000000000000ULL >> clz64(value);
>     }
>     return value;
> }
> 
> since clz64() is already part of qemu sources.
> 
I will fix it