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 /* Needed for CONFIG_MADVISE */
  26 #include "qemu/osdep.h"
  27 #include "block/block_int.h"
  28 #include "qemu-common.h"
  29 #include "qcow2.h"
  30 #include "trace.h"
  31
  32 typedef struct Qcow2CachedTable {
  33     int64_t  offset;
  34     uint64_t lru_counter;
  35     int      ref;
  36     bool     dirty;
  37 } Qcow2CachedTable;
  38
  39 struct Qcow2Cache {
  40     Qcow2CachedTable       *entries;
  41     struct Qcow2Cache      *depends;
  42     int                     size;
  43     bool                    depends_on_flush;
  44     void                   *table_array;
  45     uint64_t                lru_counter;
  46     uint64_t                cache_clean_lru_counter;
  47 };
  48
  49 static inline void *qcow2_cache_get_table_addr(BlockDriverState *bs,
  50                     Qcow2Cache *c, int table)
  51 {
  52     BDRVQcow2State *s = bs->opaque;
  53     return (uint8_t *) c->table_array + (size_t) table * s->cluster_size;
  54 }
  55
  56 static inline int qcow2_cache_get_table_idx(BlockDriverState *bs,
  57                   Qcow2Cache *c, void *table)
  58 {
  59     BDRVQcow2State *s = bs->opaque;
  60     ptrdiff_t table_offset = (uint8_t *) table - (uint8_t *) c->table_array;
  61     int idx = table_offset / s->cluster_size;
  62     assert(idx >= 0 && idx < c->size && table_offset % s->cluster_size == 0);
  63     return idx;
  64 }
  65
  66 static void qcow2_cache_table_release(BlockDriverState *bs, Qcow2Cache *c,
  67                                       int i, int num_tables)
  68 {
  69 /* Using MADV_DONTNEED to discard memory is a Linux-specific feature */
  70 #ifdef CONFIG_LINUX
  71     BDRVQcow2State *s = bs->opaque;
  72     void *t = qcow2_cache_get_table_addr(bs, c, i);
  73     int align = getpagesize();
  74     size_t mem_size = (size_t) s->cluster_size * num_tables;
  75     size_t offset = QEMU_ALIGN_UP((uintptr_t) t, align) - (uintptr_t) t;
  76     size_t length = QEMU_ALIGN_DOWN(mem_size - offset, align);
  77     if (length > 0) {
  78         madvise((uint8_t *) t + offset, length, MADV_DONTNEED);
  79     }
  80 #endif
  81 }
  82
  83 static inline bool can_clean_entry(Qcow2Cache *c, int i)
  84 {
  85     Qcow2CachedTable *t = &c->entries[i];
  86     return t->ref == 0 && !t->dirty && t->offset != 0 &&
  87         t->lru_counter <= c->cache_clean_lru_counter;
  88 }
  89
  90 void qcow2_cache_clean_unused(BlockDriverState *bs, Qcow2Cache *c)
  91 {
  92     int i = 0;
  93     while (i < c->size) {
  94         int to_clean = 0;
  95
  96         /* Skip the entries that we don't need to clean */
  97         while (i < c->size && !can_clean_entry(c, i)) {
  98             i++;
  99         }
 100
 101         /* And count how many we can clean in a row */
 102         while (i < c->size && can_clean_entry(c, i)) {
 103             c->entries[i].offset = 0;
 104             c->entries[i].lru_counter = 0;
 105             i++;
 106             to_clean++;
 107         }
 108
 109         if (to_clean > 0) {
 110             qcow2_cache_table_release(bs, c, i - to_clean, to_clean);
 111         }
 112     }
 113
 114     c->cache_clean_lru_counter = c->lru_counter;
 115 }
 116
 117 Qcow2Cache *qcow2_cache_create(BlockDriverState *bs, int num_tables)
 118 {
 119     BDRVQcow2State *s = bs->opaque;
 120     Qcow2Cache *c;
 121
 122     c = g_new0(Qcow2Cache, 1);
 123     c->size = num_tables;
 124     c->entries = g_try_new0(Qcow2CachedTable, num_tables);
 125     c->table_array = qemu_try_blockalign(bs->file->bs,
 126                                          (size_t) num_tables * s->cluster_size);
 127
 128     if (!c->entries || !c->table_array) {
 129         qemu_vfree(c->table_array);
 130         g_free(c->entries);
 131         g_free(c);
 132         c = NULL;
 133     }
 134
 135     return c;
 136 }
 137
 138 int qcow2_cache_destroy(BlockDriverState *bs, Qcow2Cache *c)
 139 {
 140     int i;
 141
 142     for (i = 0; i < c->size; i++) {
 143         assert(c->entries[i].ref == 0);
 144     }
 145
 146     qemu_vfree(c->table_array);
 147     g_free(c->entries);
 148     g_free(c);
 149
 150     return 0;
 151 }
 152
 153 static int qcow2_cache_flush_dependency(BlockDriverState *bs, Qcow2Cache *c)
 154 {
 155     int ret;
 156
 157     ret = qcow2_cache_flush(bs, c->depends);
 158     if (ret < 0) {
 159         return ret;
 160     }
 161
 162     c->depends = NULL;
 163     c->depends_on_flush = false;
 164
 165     return 0;
 166 }
 167
 168 static int qcow2_cache_entry_flush(BlockDriverState *bs, Qcow2Cache *c, int i)
 169 {
 170     BDRVQcow2State *s = bs->opaque;
 171     int ret = 0;
 172
 173     if (!c->entries[i].dirty || !c->entries[i].offset) {
 174         return 0;
 175     }
 176
 177     trace_qcow2_cache_entry_flush(qemu_coroutine_self(),
 178                                   c == s->l2_table_cache, i);
 179
 180     if (c->depends) {
 181         ret = qcow2_cache_flush_dependency(bs, c);
 182     } else if (c->depends_on_flush) {
 183         ret = bdrv_flush(bs->file->bs);
 184         if (ret >= 0) {
 185             c->depends_on_flush = false;
 186         }
 187     }
 188
 189     if (ret < 0) {
 190         return ret;
 191     }
 192
 193     if (c == s->refcount_block_cache) {
 194         ret = qcow2_pre_write_overlap_check(bs, QCOW2_OL_REFCOUNT_BLOCK,
 195                 c->entries[i].offset, s->cluster_size);
 196     } else if (c == s->l2_table_cache) {
 197         ret = qcow2_pre_write_overlap_check(bs, QCOW2_OL_ACTIVE_L2,
 198                 c->entries[i].offset, s->cluster_size);
 199     } else {
 200         ret = qcow2_pre_write_overlap_check(bs, 0,
 201                 c->entries[i].offset, s->cluster_size);
 202     }
 203
 204     if (ret < 0) {
 205         return ret;
 206     }
 207
 208     if (c == s->refcount_block_cache) {
 209         BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_UPDATE_PART);
 210     } else if (c == s->l2_table_cache) {
 211         BLKDBG_EVENT(bs->file, BLKDBG_L2_UPDATE);
 212     }
 213
 214     ret = bdrv_pwrite(bs->file, c->entries[i].offset,
 215                       qcow2_cache_get_table_addr(bs, c, i), s->cluster_size);
 216     if (ret < 0) {
 217         return ret;
 218     }
 219
 220     c->entries[i].dirty = false;
 221
 222     return 0;
 223 }
 224
 225 int qcow2_cache_write(BlockDriverState *bs, Qcow2Cache *c)
 226 {
 227     BDRVQcow2State *s = bs->opaque;
 228     int result = 0;
 229     int ret;
 230     int i;
 231
 232     trace_qcow2_cache_flush(qemu_coroutine_self(), c == s->l2_table_cache);
 233
 234     for (i = 0; i < c->size; i++) {
 235         ret = qcow2_cache_entry_flush(bs, c, i);
 236         if (ret < 0 && result != -ENOSPC) {
 237             result = ret;
 238         }
 239     }
 240
 241     return result;
 242 }
 243
 244 int qcow2_cache_flush(BlockDriverState *bs, Qcow2Cache *c)
 245 {
 246     int result = qcow2_cache_write(bs, c);
 247
 248     if (result == 0) {
 249         int ret = bdrv_flush(bs->file->bs);
 250         if (ret < 0) {
 251             result = ret;
 252         }
 253     }
 254
 255     return result;
 256 }
 257
 258 int qcow2_cache_set_dependency(BlockDriverState *bs, Qcow2Cache *c,
 259     Qcow2Cache *dependency)
 260 {
 261     int ret;
 262
 263     if (dependency->depends) {
 264         ret = qcow2_cache_flush_dependency(bs, dependency);
 265         if (ret < 0) {
 266             return ret;
 267         }
 268     }
 269
 270     if (c->depends && (c->depends != dependency)) {
 271         ret = qcow2_cache_flush_dependency(bs, c);
 272         if (ret < 0) {
 273             return ret;
 274         }
 275     }
 276
 277     c->depends = dependency;
 278     return 0;
 279 }
 280
 281 void qcow2_cache_depends_on_flush(Qcow2Cache *c)
 282 {
 283     c->depends_on_flush = true;
 284 }
 285
 286 int qcow2_cache_empty(BlockDriverState *bs, Qcow2Cache *c)
 287 {
 288     int ret, i;
 289
 290     ret = qcow2_cache_flush(bs, c);
 291     if (ret < 0) {
 292         return ret;
 293     }
 294
 295     for (i = 0; i < c->size; i++) {
 296         assert(c->entries[i].ref == 0);
 297         c->entries[i].offset = 0;
 298         c->entries[i].lru_counter = 0;
 299     }
 300
 301     qcow2_cache_table_release(bs, c, 0, c->size);
 302
 303     c->lru_counter = 0;
 304
 305     return 0;
 306 }
 307
 308 static int qcow2_cache_do_get(BlockDriverState *bs, Qcow2Cache *c,
 309     uint64_t offset, void **table, bool read_from_disk)
 310 {
 311     BDRVQcow2State *s = bs->opaque;
 312     int i;
 313     int ret;
 314     int lookup_index;
 315     uint64_t min_lru_counter = UINT64_MAX;
 316     int min_lru_index = -1;
 317
 318     trace_qcow2_cache_get(qemu_coroutine_self(), c == s->l2_table_cache,
 319                           offset, read_from_disk);
 320
 321     /* Check if the table is already cached */
 322     i = lookup_index = (offset / s->cluster_size * 4) % c->size;
 323     do {
 324         const Qcow2CachedTable *t = &c->entries[i];
 325         if (t->offset == offset) {
 326             goto found;
 327         }
 328         if (t->ref == 0 && t->lru_counter < min_lru_counter) {
 329             min_lru_counter = t->lru_counter;
 330             min_lru_index = i;
 331         }
 332         if (++i == c->size) {
 333             i = 0;
 334         }
 335     } while (i != lookup_index);
 336
 337     if (min_lru_index == -1) {
 338         /* This can't happen in current synchronous code, but leave the check
 339          * here as a reminder for whoever starts using AIO with the cache */
 340         abort();
 341     }
 342
 343     /* Cache miss: write a table back and replace it */
 344     i = min_lru_index;
 345     trace_qcow2_cache_get_replace_entry(qemu_coroutine_self(),
 346                                         c == s->l2_table_cache, i);
 347
 348     ret = qcow2_cache_entry_flush(bs, c, i);
 349     if (ret < 0) {
 350         return ret;
 351     }
 352
 353     trace_qcow2_cache_get_read(qemu_coroutine_self(),
 354                                c == s->l2_table_cache, i);
 355     c->entries[i].offset = 0;
 356     if (read_from_disk) {
 357         if (c == s->l2_table_cache) {
 358             BLKDBG_EVENT(bs->file, BLKDBG_L2_LOAD);
 359         }
 360
 361         ret = bdrv_pread(bs->file, offset,
 362                          qcow2_cache_get_table_addr(bs, c, i),
 363                          s->cluster_size);
 364         if (ret < 0) {
 365             return ret;
 366         }
 367     }
 368
 369     c->entries[i].offset = offset;
 370
 371     /* And return the right table */
 372 found:
 373     c->entries[i].ref++;
 374     *table = qcow2_cache_get_table_addr(bs, c, i);
 375
 376     trace_qcow2_cache_get_done(qemu_coroutine_self(),
 377                                c == s->l2_table_cache, i);
 378
 379     return 0;
 380 }
 381
 382 int qcow2_cache_get(BlockDriverState *bs, Qcow2Cache *c, uint64_t offset,
 383     void **table)
 384 {
 385     return qcow2_cache_do_get(bs, c, offset, table, true);
 386 }
 387
 388 int qcow2_cache_get_empty(BlockDriverState *bs, Qcow2Cache *c, uint64_t offset,
 389     void **table)
 390 {
 391     return qcow2_cache_do_get(bs, c, offset, table, false);
 392 }
 393
 394 void qcow2_cache_put(BlockDriverState *bs, Qcow2Cache *c, void **table)
 395 {
 396     int i = qcow2_cache_get_table_idx(bs, c, *table);
 397
 398     c->entries[i].ref--;
 399     *table = NULL;
 400
 401     if (c->entries[i].ref == 0) {
 402         c->entries[i].lru_counter = ++c->lru_counter;
 403     }
 404
 405     assert(c->entries[i].ref >= 0);
 406 }
 407
 408 void qcow2_cache_entry_mark_dirty(BlockDriverState *bs, Qcow2Cache *c,
 409      void *table)
 410 {
 411     int i = qcow2_cache_get_table_idx(bs, c, table);
 412     assert(c->entries[i].offset != 0);
 413     c->entries[i].dirty = true;
 414 }