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