qemu

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