On Tue, Jul 3, 2012 at 1:52 PM, Orit Wasserman <owass...@redhat.com> wrote:
> Add LRU page cache mechanism.
> The page are accessed by their address.
>
> 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>
> Signed-off-by: Orit Wasserman <owass...@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 <owass...@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 <owass...@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
>
