block/qcow2-cache.c

   1 /*
   2  * L2/refcount table cache for the QCOW2 format
   3  *
   4  * Copyright (c) 2010 Kevin Wolf <kwolf@redhat.com>
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a copy
   7  * of this software and associated documentation files (the "Software"), to deal
   8  * in the Software without restriction, including without limitation the rights
   9  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  10  * copies of the Software, and to permit persons to whom the Software is
  11  * furnished to do so, subject to the following conditions:
  12  *
  13  * The above copyright notice and this permission notice shall be included in
  14  * all copies or substantial portions of the Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  19  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  22  * THE SOFTWARE.
  23  */
  24
  25 #include "block_int.h"
  26 #include "qemu-common.h"
  27 #include "qcow2.h"
  28
  29 typedef struct Qcow2CachedTable {
  30     void*   table;
  31     int64_t offset;
  32     bool    dirty;
  33     int     cache_hits;
  34     int     ref;
  35 } Qcow2CachedTable;
  36
  37 struct Qcow2Cache {
  38     int                     size;
  39     Qcow2CachedTable*       entries;
  40     struct Qcow2Cache*      depends;
  41     bool                    writethrough;
  42 };
  43
  44 Qcow2Cache *qcow2_cache_create(BlockDriverState *bs, int num_tables,
  45     bool writethrough)
  46 {
  47     BDRVQcowState *s = bs->opaque;
  48     Qcow2Cache *c;
  49     int i;
  50
  51     c = qemu_mallocz(sizeof(*c));
  52     c->size = num_tables;
  53     c->entries = qemu_mallocz(sizeof(*c->entries) * num_tables);
  54     c->writethrough = writethrough;
  55
  56     for (i = 0; i < c->size; i++) {
  57         c->entries[i].table = qemu_blockalign(bs, s->cluster_size);
  58     }
  59
  60     return c;
  61 }
  62
  63 int qcow2_cache_destroy(BlockDriverState* bs, Qcow2Cache *c)
  64 {
  65     int i;
  66
  67     for (i = 0; i < c->size; i++) {
  68         assert(c->entries[i].ref == 0);
  69         qemu_vfree(c->entries[i].table);
  70     }
  71
  72     qemu_free(c->entries);
  73     qemu_free(c);
  74
  75     return 0;
  76 }
  77
  78 static int qcow2_cache_flush_dependency(BlockDriverState *bs, Qcow2Cache *c)
  79 {
  80     int ret;
  81
  82     ret = qcow2_cache_flush(bs, c->depends);
  83     if (ret < 0) {
  84         return ret;
  85     }
  86
  87     c->depends = NULL;
  88     return 0;
  89 }
  90
  91 static int qcow2_cache_entry_flush(BlockDriverState *bs, Qcow2Cache *c, int i)
  92 {
  93     BDRVQcowState *s = bs->opaque;
  94     int ret;
  95
  96     if (!c->entries[i].dirty || !c->entries[i].offset) {
  97         return 0;
  98     }
  99
 100     if (c->depends) {
 101         ret = qcow2_cache_flush_dependency(bs, c);
 102         if (ret < 0) {
 103             return ret;
 104         }
 105     }
 106
 107     ret = bdrv_pwrite(bs->file, c->entries[i].offset, c->entries[i].table,
 108         s->cluster_size);
 109     if (ret < 0) {
 110         return ret;
 111     }
 112
 113     c->entries[i].dirty = false;
 114
 115     return 0;
 116 }
 117
 118 int qcow2_cache_flush(BlockDriverState *bs, Qcow2Cache *c)
 119 {
 120     int result = 0;
 121     int ret;
 122     int i;
 123
 124     for (i = 0; i < c->size; i++) {
 125         ret = qcow2_cache_entry_flush(bs, c, i);
 126         if (ret < 0 && result != -ENOSPC) {
 127             result = ret;
 128         }
 129     }
 130
 131     if (result == 0) {
 132         ret = bdrv_flush(bs->file);
 133         if (ret < 0) {
 134             result = ret;
 135         }
 136     }
 137
 138     return result;
 139 }
 140
 141 int qcow2_cache_set_dependency(BlockDriverState *bs, Qcow2Cache *c,
 142     Qcow2Cache *dependency)
 143 {
 144     int ret;
 145
 146     if (dependency->depends) {
 147         ret = qcow2_cache_flush_dependency(bs, dependency);
 148         if (ret < 0) {
 149             return ret;
 150         }
 151     }
 152
 153     if (c->depends && (c->depends != dependency)) {
 154         ret = qcow2_cache_flush_dependency(bs, c);
 155         if (ret < 0) {
 156             return ret;
 157         }
 158     }
 159
 160     c->depends = dependency;
 161     return 0;
 162 }
 163
 164 static int qcow2_cache_find_entry_to_replace(Qcow2Cache *c)
 165 {
 166     int i;
 167     int min_count = INT_MAX;
 168     int min_index = -1;
 169
 170
 171     for (i = 0; i < c->size; i++) {
 172         if (c->entries[i].ref) {
 173             continue;
 174         }
 175
 176         if (c->entries[i].cache_hits < min_count) {
 177             min_index = i;
 178             min_count = c->entries[i].cache_hits;
 179         }
 180
 181         /* Give newer hits priority */
 182         /* TODO Check how to optimize the replacement strategy */
 183         c->entries[i].cache_hits /= 2;
 184     }
 185
 186     if (min_index == -1) {
 187         /* This can't happen in current synchronous code, but leave the check
 188          * here as a reminder for whoever starts using AIO with the cache */
 189         abort();
 190     }
 191     return min_index;
 192 }
 193
 194 static int qcow2_cache_do_get(BlockDriverState *bs, Qcow2Cache *c,
 195     uint64_t offset, void **table, bool read_from_disk)
 196 {
 197     BDRVQcowState *s = bs->opaque;
 198     int i;
 199     int ret;
 200
 201     /* Check if the table is already cached */
 202     for (i = 0; i < c->size; i++) {
 203         if (c->entries[i].offset == offset) {
 204             goto found;
 205         }
 206     }
 207
 208     /* If not, write a table back and replace it */
 209     i = qcow2_cache_find_entry_to_replace(c);
 210     if (i < 0) {
 211         return i;
 212     }
 213
 214     ret = qcow2_cache_entry_flush(bs, c, i);
 215     if (ret < 0) {
 216         return ret;
 217     }
 218
 219     c->entries[i].offset = 0;
 220     if (read_from_disk) {
 221         ret = bdrv_pread(bs->file, offset, c->entries[i].table, s->cluster_size);
 222         if (ret < 0) {
 223             return ret;
 224         }
 225     }
 226
 227     /* Give the table some hits for the start so that it won't be replaced
 228      * immediately. The number 32 is completely arbitrary. */
 229     c->entries[i].cache_hits = 32;
 230     c->entries[i].offset = offset;
 231
 232     /* And return the right table */
 233 found:
 234     c->entries[i].cache_hits++;
 235     c->entries[i].ref++;
 236     *table = c->entries[i].table;
 237     return 0;
 238 }
 239
 240 int qcow2_cache_get(BlockDriverState *bs, Qcow2Cache *c, uint64_t offset,
 241     void **table)
 242 {
 243     return qcow2_cache_do_get(bs, c, offset, table, true);
 244 }
 245
 246 int qcow2_cache_get_empty(BlockDriverState *bs, Qcow2Cache *c, uint64_t offset,
 247     void **table)
 248 {
 249     return qcow2_cache_do_get(bs, c, offset, table, false);
 250 }
 251
 252 int qcow2_cache_put(BlockDriverState *bs, Qcow2Cache *c, void **table)
 253 {
 254     int i;
 255
 256     for (i = 0; i < c->size; i++) {
 257         if (c->entries[i].table == *table) {
 258             goto found;
 259         }
 260     }
 261     return -ENOENT;
 262
 263 found:
 264     c->entries[i].ref--;
 265     *table = NULL;
 266
 267     assert(c->entries[i].ref >= 0);
 268
 269     if (c->writethrough) {
 270         return qcow2_cache_entry_flush(bs, c, i);
 271     } else {
 272         return 0;
 273     }
 274 }
 275
 276 void qcow2_cache_entry_mark_dirty(Qcow2Cache *c, void *table)
 277 {
 278     int i;
 279
 280     for (i = 0; i < c->size; i++) {
 281         if (c->entries[i].table == table) {
 282             goto found;
 283         }
 284     }
 285     abort();
 286
 287 found:
 288     c->entries[i].dirty = true;
 289 }
 290