From patchwork Tue Jun 19 15:43:12 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Orit Wasserman X-Patchwork-Id: 165812 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 8884FB7019 for ; Wed, 20 Jun 2012 02:48:28 +1000 (EST) Received: from localhost ([::1]:35348 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Sh0bj-0000uQ-EI for incoming@patchwork.ozlabs.org; Tue, 19 Jun 2012 11:44:43 -0400 Received: from eggs.gnu.org ([208.118.235.92]:49144) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Sh0ay-0007Br-Ms for qemu-devel@nongnu.org; Tue, 19 Jun 2012 11:44:01 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Sh0at-0004jL-9P for qemu-devel@nongnu.org; Tue, 19 Jun 2012 11:43:56 -0400 Received: from mx1.redhat.com ([209.132.183.28]:24764) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Sh0at-0004ig-1Y for qemu-devel@nongnu.org; Tue, 19 Jun 2012 11:43:51 -0400 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id q5JFhhOn023751 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Tue, 19 Jun 2012 11:43:44 -0400 Received: from dhcp-1-120.tlv.redhat.com (vpn-200-13.tlv.redhat.com [10.35.200.13]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id q5JFhCkU007577; Tue, 19 Jun 2012 11:43:38 -0400 From: Orit Wasserman To: qemu-devel@nongnu.org Date: Tue, 19 Jun 2012 18:43:12 +0300 Message-Id: <1340120601-24747-5-git-send-email-owasserm@redhat.com> In-Reply-To: <1340120601-24747-1-git-send-email-owasserm@redhat.com> References: <1340120601-24747-1-git-send-email-owasserm@redhat.com> X-Scanned-By: MIMEDefang 2.68 on 10.5.11.22 X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 209.132.183.28 Cc: peter.maydell@linaro.org, aliguori@us.ibm.com, quintela@redhat.com, Petter Svard , stefanha@gmail.com, mdroth@linux.vnet.ibm.com, Benoit Hudzia , blauwirbel@gmail.com, Orit Wasserman , chegu_vinod@hp.com, avi@redhat.com, Aidan Shribman , pbonzini@redhat.com, eblake@redhat.com Subject: [Qemu-devel] [PATCH v12 04/13] Add cache handling functions X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Add LRU page cache mechanism. The page are accessed by their address. Signed-off-by: Benoit Hudzia Signed-off-by: Petter Svard Signed-off-by: Aidan Shribman Signed-off-by: Orit Wasserman --- Makefile.objs | 1 + cache.c | 219 ++++++++++++++++++++++++++++++++++++++++++++++++++ include/qemu/cache.h | 81 ++++++++++++++++++ qemu-common.h | 10 +++ 4 files changed, 311 insertions(+), 0 deletions(-) create mode 100644 cache.c create mode 100644 include/qemu/cache.h diff --git a/Makefile.objs b/Makefile.objs index 74110dd..a64f3ed 100644 --- a/Makefile.objs +++ b/Makefile.objs @@ -76,6 +76,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 += cache.o common-obj-$(CONFIG_POSIX) += migration-exec.o migration-unix.o migration-fd.o common-obj-$(CONFIG_WIN32) += version.o diff --git a/cache.c b/cache.c new file mode 100644 index 0000000..cc0870b --- /dev/null +++ b/cache.c @@ -0,0 +1,219 @@ +/* + * Page cache for qemu + * The cache is base on a hash on the page address + * + * Copyright 2011 Red Hat, Inc. and/or its affiliates + * + * Authors: + * Orit Wasserman + * + * This work is licensed under the terms of the GNU GPL, version 2. See + * the COPYING file in the top-level directory. + * + * Contributions after 2012-01-13 are licensed under the terms of the + * GNU GPL, version 2 or (at your option) any later version. + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "qemu-common.h" +#include "qemu/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 Cache { + CacheItem *page_cache; + unsigned int page_size; + int64_t max_num_items; + uint64_t max_item_age; + int64_t num_items; +}; + +Cache *cache_init(int64_t num_pages, unsigned int page_size) +{ + int i; + + Cache *cache = g_malloc(sizeof(Cache)); + if (!cache) { + DPRINTF("Error allocation Cache\n"); + return NULL; + } + + if (num_pages <= 0) { + DPRINTF("invalid number pages\n"); + return NULL; + } + + /* round down to the nearst power of 2 */ + if (!is_power_of_2(num_pages)) { + num_pages = 1 << ffs(num_pages); + DPRINTF("rounding down to %ld\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 %lu\n", cache->max_num_items); + + cache->page_cache = g_malloc((cache->max_num_items) * + sizeof(CacheItem)); + if (!cache->page_cache) { + DPRINTF("could not allocate cache\n"); + g_free(cache); + return NULL; + } + + 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(Cache *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 Cache *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 Cache *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 Cache *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 Cache *cache, uint64_t addr) +{ + return cache_get_by_addr(cache, addr)->it_data; +} + +void cache_insert(Cache *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; +} + +int cache_resize(Cache *cache, int64_t new_num_pages) +{ + Cache *new_cache; + int i; + + CacheItem *old_it, *new_it; + + g_assert(cache); + + /* same size */ + if (new_num_pages == cache->max_num_items) { + return 0; + } + + /* cache was not inited */ + if (cache->page_cache == NULL) { + return -1; + } + + 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 0; +} diff --git a/include/qemu/cache.h b/include/qemu/cache.h new file mode 100644 index 0000000..16145e1 --- /dev/null +++ b/include/qemu/cache.h @@ -0,0 +1,81 @@ +/* + * Page cache for qemu + * The cache is base on a hash on the page address + * + * Copyright 2011 Red Hat, Inc. and/or its affiliates + * + * Authors: + * Orit Wasserman + * + * This work is licensed under the terms of the GNU GPL, version 2. See + * the COPYING file in the top-level directory. + * + * Contributions after 2012-01-13 are licensed under the terms of the + * GNU GPL, version 2 or (at your option) any later version. + */ + +#ifndef CACHE_H +#define CACHE_H + +/* Page cache for storing guest pages */ +typedef struct Cache Cache; + +/** + * cache_init: Initialize the page cache + * + * + * Returns new allocated cache or NULL on error + * + * @cache pointer to the Cache struct + * @num_pages: cache maximal number of cached pages + * @page_size: cache page size + */ +Cache *cache_init(int64_t num_pages, unsigned int page_size); + +/** + * cache_fini: free all cache resources + * @cache pointer to the Cache struct + */ +void cache_fini(Cache *cache); + +/** + * cache_is_cached: Checks to see if the page is cached + * + * Returns %true if page is cached + * + * @cache pointer to the Cache struct + * @addr: page addr + */ +bool cache_is_cached(const Cache *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 Cache struct + * @addr: page addr + */ +uint8_t *get_cached_data(const Cache *cache, uint64_t addr); + +/** + * cache_insert: insert the page into the cache. the previous value will be overwritten + * + * @cache pointer to the Cache struct + * @addr: page address + * @pdata: pointer to the page + */ +void cache_insert(Cache *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 + * + * @cache pointer to the Cache struct + * @num_pages: new page cache size (in pages) + */ +int cache_resize(Cache *cache, int64_t num_pages); + +#endif diff --git a/qemu-common.h b/qemu-common.h index 62081c0..39f9d58 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 @@ -409,6 +410,15 @@ 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)); +} + #include "module.h" #endif