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