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