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 } 463