page_cache.c

   1 /*
   2  * Page cache for QEMU
   3  * The cache is base on a hash of the page address
   4  *
   5  * Copyright 2012 Red Hat, Inc. and/or its affiliates
   6  *
   7  * Authors:
   8  *  Orit Wasserman  <owasserm@redhat.com>
   9  *
  10  * This work is licensed under the terms of the GNU GPL, version 2 or later.
  11  * See the COPYING file in the top-level directory.
  12  *
  13  */
  14
  15 #include "qemu/osdep.h"
  16 #include <glib.h>
  17
  18 #include "qemu-common.h"
  19 #include "qemu/host-utils.h"
  20 #include "migration/page_cache.h"
  21
  22 #ifdef DEBUG_CACHE
  23 #define DPRINTF(fmt, ...) \
  24     do { fprintf(stdout, "cache: " fmt, ## __VA_ARGS__); } while (0)
  25 #else
  26 #define DPRINTF(fmt, ...) \
  27     do { } while (0)
  28 #endif
  29
  30 /* the page in cache will not be replaced in two cycles */
  31 #define CACHED_PAGE_LIFETIME 2
  32
  33 typedef struct CacheItem CacheItem;
  34
  35 struct CacheItem {
  36     uint64_t it_addr;
  37     uint64_t it_age;
  38     uint8_t *it_data;
  39 };
  40
  41 struct PageCache {
  42     CacheItem *page_cache;
  43     unsigned int page_size;
  44     int64_t max_num_items;
  45     uint64_t max_item_age;
  46     int64_t num_items;
  47 };
  48
  49 PageCache *cache_init(int64_t num_pages, unsigned int page_size)
  50 {
  51     int64_t i;
  52
  53     PageCache *cache;
  54
  55     if (num_pages <= 0) {
  56         DPRINTF("invalid number of pages\n");
  57         return NULL;
  58     }
  59
  60     /* We prefer not to abort if there is no memory */
  61     cache = g_try_malloc(sizeof(*cache));
  62     if (!cache) {
  63         DPRINTF("Failed to allocate cache\n");
  64         return NULL;
  65     }
  66     /* round down to the nearest power of 2 */
  67     if (!is_power_of_2(num_pages)) {
  68         num_pages = pow2floor(num_pages);
  69         DPRINTF("rounding down to %" PRId64 "\n", num_pages);
  70     }
  71     cache->page_size = page_size;
  72     cache->num_items = 0;
  73     cache->max_item_age = 0;
  74     cache->max_num_items = num_pages;
  75
  76     DPRINTF("Setting cache buckets to %" PRId64 "\n", cache->max_num_items);
  77
  78     /* We prefer not to abort if there is no memory */
  79     cache->page_cache = g_try_malloc((cache->max_num_items) *
  80                                      sizeof(*cache->page_cache));
  81     if (!cache->page_cache) {
  82         DPRINTF("Failed to allocate cache->page_cache\n");
  83         g_free(cache);
  84         return NULL;
  85     }
  86
  87     for (i = 0; i < cache->max_num_items; i++) {
  88         cache->page_cache[i].it_data = NULL;
  89         cache->page_cache[i].it_age = 0;
  90         cache->page_cache[i].it_addr = -1;
  91     }
  92
  93     return cache;
  94 }
  95
  96 void cache_fini(PageCache *cache)
  97 {
  98     int64_t i;
  99
 100     g_assert(cache);
 101     g_assert(cache->page_cache);
 102
 103     for (i = 0; i < cache->max_num_items; i++) {
 104         g_free(cache->page_cache[i].it_data);
 105     }
 106
 107     g_free(cache->page_cache);
 108     cache->page_cache = NULL;
 109     g_free(cache);
 110 }
 111
 112 static size_t cache_get_cache_pos(const PageCache *cache,
 113                                   uint64_t address)
 114 {
 115     size_t pos;
 116
 117     g_assert(cache->max_num_items);
 118     pos = (address / cache->page_size) & (cache->max_num_items - 1);
 119     return pos;
 120 }
 121
 122 static CacheItem *cache_get_by_addr(const PageCache *cache, uint64_t addr)
 123 {
 124     size_t pos;
 125
 126     g_assert(cache);
 127     g_assert(cache->page_cache);
 128
 129     pos = cache_get_cache_pos(cache, addr);
 130
 131     return &cache->page_cache[pos];
 132 }
 133
 134 uint8_t *get_cached_data(const PageCache *cache, uint64_t addr)
 135 {
 136     return cache_get_by_addr(cache, addr)->it_data;
 137 }
 138
 139 bool cache_is_cached(const PageCache *cache, uint64_t addr,
 140                      uint64_t current_age)
 141 {
 142     CacheItem *it;
 143
 144     it = cache_get_by_addr(cache, addr);
 145
 146     if (it->it_addr == addr) {
 147         /* update the it_age when the cache hit */
 148         it->it_age = current_age;
 149         return true;
 150     }
 151     return false;
 152 }
 153
 154 int cache_insert(PageCache *cache, uint64_t addr, const uint8_t *pdata,
 155                  uint64_t current_age)
 156 {
 157
 158     CacheItem *it;
 159
 160     /* actual update of entry */
 161     it = cache_get_by_addr(cache, addr);
 162
 163     if (it->it_data && it->it_addr != addr &&
 164         it->it_age + CACHED_PAGE_LIFETIME > current_age) {
 165         /* the cache page is fresh, don't replace it */
 166         return -1;
 167     }
 168     /* allocate page */
 169     if (!it->it_data) {
 170         it->it_data = g_try_malloc(cache->page_size);
 171         if (!it->it_data) {
 172             DPRINTF("Error allocating page\n");
 173             return -1;
 174         }
 175         cache->num_items++;
 176     }
 177
 178     memcpy(it->it_data, pdata, cache->page_size);
 179
 180     it->it_age = current_age;
 181     it->it_addr = addr;
 182
 183     return 0;
 184 }
 185
 186 int64_t cache_resize(PageCache *cache, int64_t new_num_pages)
 187 {
 188     PageCache *new_cache;
 189     int64_t i;
 190
 191     CacheItem *old_it, *new_it;
 192
 193     g_assert(cache);
 194
 195     /* cache was not inited */
 196     if (cache->page_cache == NULL) {
 197         return -1;
 198     }
 199
 200     /* same size */
 201     if (pow2floor(new_num_pages) == cache->max_num_items) {
 202         return cache->max_num_items;
 203     }
 204
 205     new_cache = cache_init(new_num_pages, cache->page_size);
 206     if (!(new_cache)) {
 207         DPRINTF("Error creating new cache\n");
 208         return -1;
 209     }
 210
 211     /* move all data from old cache */
 212     for (i = 0; i < cache->max_num_items; i++) {
 213         old_it = &cache->page_cache[i];
 214         if (old_it->it_addr != -1) {
 215             /* check for collision, if there is, keep MRU page */
 216             new_it = cache_get_by_addr(new_cache, old_it->it_addr);
 217             if (new_it->it_data && new_it->it_age >= old_it->it_age) {
 218                 /* keep the MRU page */
 219                 g_free(old_it->it_data);
 220             } else {
 221                 if (!new_it->it_data) {
 222                     new_cache->num_items++;
 223                 }
 224                 g_free(new_it->it_data);
 225                 new_it->it_data = old_it->it_data;
 226                 new_it->it_age = old_it->it_age;
 227                 new_it->it_addr = old_it->it_addr;
 228             }
 229         }
 230     }
 231
 232     g_free(cache->page_cache);
 233     cache->page_cache = new_cache->page_cache;
 234     cache->max_num_items = new_cache->max_num_items;
 235     cache->num_items = new_cache->num_items;
 236
 237     g_free(new_cache);
 238
 239     return cache->max_num_items;
 240 }