xref: /qemu/block/qcow2-cache.c (revision 0bb79c97)
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 
qcow2_cache_get_table_addr(Qcow2Cache * c,int table)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 
qcow2_cache_get_table_idx(Qcow2Cache * c,void * table)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 
qcow2_cache_get_name(BDRVQcow2State * s,Qcow2Cache * c)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 
qcow2_cache_table_release(Qcow2Cache * c,int i,int num_tables)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 
can_clean_entry(Qcow2Cache * c,int i)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 
qcow2_cache_clean_unused(Qcow2Cache * c)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 
qcow2_cache_create(BlockDriverState * bs,int num_tables,unsigned table_size)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 
qcow2_cache_destroy(Qcow2Cache * c)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
qcow2_cache_flush_dependency(BlockDriverState * bs,Qcow2Cache * c)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
qcow2_cache_entry_flush(BlockDriverState * bs,Qcow2Cache * c,int i)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 
qcow2_cache_write(BlockDriverState * bs,Qcow2Cache * c)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 
qcow2_cache_flush(BlockDriverState * bs,Qcow2Cache * c)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 
qcow2_cache_set_dependency(BlockDriverState * bs,Qcow2Cache * c,Qcow2Cache * dependency)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 
qcow2_cache_depends_on_flush(Qcow2Cache * c)296 void qcow2_cache_depends_on_flush(Qcow2Cache *c)
297 {
298     c->depends_on_flush = true;
299 }
300 
qcow2_cache_empty(BlockDriverState * bs,Qcow2Cache * c)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
qcow2_cache_do_get(BlockDriverState * bs,Qcow2Cache * c,uint64_t offset,void ** table,bool read_from_disk)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 
qcow2_cache_get(BlockDriverState * bs,Qcow2Cache * c,uint64_t offset,void ** table)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 
qcow2_cache_get_empty(BlockDriverState * bs,Qcow2Cache * c,uint64_t offset,void ** table)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 
qcow2_cache_put(Qcow2Cache * c,void ** table)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 
qcow2_cache_entry_mark_dirty(Qcow2Cache * c,void * table)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 
qcow2_cache_is_table_offset(Qcow2Cache * c,uint64_t offset)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 
qcow2_cache_discard(Qcow2Cache * c,void * table)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