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