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