Statistics
| Branch: | Revision:

root / block / qcow2-refcount.c @ 80fa3341

History | View | Annotate | Download (37.8 kB)

1
/*
2
 * Block driver for the QCOW version 2 format
3
 *
4
 * Copyright (c) 2004-2006 Fabrice Bellard
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-common.h"
26
#include "block_int.h"
27
#include "block/qcow2.h"
28

    
29
static int64_t alloc_clusters_noref(BlockDriverState *bs, int64_t size);
30
static int QEMU_WARN_UNUSED_RESULT update_refcount(BlockDriverState *bs,
31
                            int64_t offset, int64_t length,
32
                            int addend);
33

    
34

    
35
/*********************************************************/
36
/* refcount handling */
37

    
38
int qcow2_refcount_init(BlockDriverState *bs)
39
{
40
    BDRVQcowState *s = bs->opaque;
41
    int ret, refcount_table_size2, i;
42

    
43
    refcount_table_size2 = s->refcount_table_size * sizeof(uint64_t);
44
    s->refcount_table = qemu_malloc(refcount_table_size2);
45
    if (s->refcount_table_size > 0) {
46
        BLKDBG_EVENT(bs->file, BLKDBG_REFTABLE_LOAD);
47
        ret = bdrv_pread(bs->file, s->refcount_table_offset,
48
                         s->refcount_table, refcount_table_size2);
49
        if (ret != refcount_table_size2)
50
            goto fail;
51
        for(i = 0; i < s->refcount_table_size; i++)
52
            be64_to_cpus(&s->refcount_table[i]);
53
    }
54
    return 0;
55
 fail:
56
    return -ENOMEM;
57
}
58

    
59
void qcow2_refcount_close(BlockDriverState *bs)
60
{
61
    BDRVQcowState *s = bs->opaque;
62
    qemu_free(s->refcount_table);
63
}
64

    
65

    
66
static int load_refcount_block(BlockDriverState *bs,
67
                               int64_t refcount_block_offset,
68
                               void **refcount_block)
69
{
70
    BDRVQcowState *s = bs->opaque;
71
    int ret;
72

    
73
    BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_LOAD);
74
    ret = qcow2_cache_get(bs, s->refcount_block_cache, refcount_block_offset,
75
        refcount_block);
76

    
77
    return ret;
78
}
79

    
80
/*
81
 * Returns the refcount of the cluster given by its index. Any non-negative
82
 * return value is the refcount of the cluster, negative values are -errno
83
 * and indicate an error.
84
 */
85
static int get_refcount(BlockDriverState *bs, int64_t cluster_index)
86
{
87
    BDRVQcowState *s = bs->opaque;
88
    int refcount_table_index, block_index;
89
    int64_t refcount_block_offset;
90
    int ret;
91
    uint16_t *refcount_block;
92
    uint16_t refcount;
93

    
94
    refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
95
    if (refcount_table_index >= s->refcount_table_size)
96
        return 0;
97
    refcount_block_offset = s->refcount_table[refcount_table_index];
98
    if (!refcount_block_offset)
99
        return 0;
100

    
101
    ret = qcow2_cache_get(bs, s->refcount_block_cache, refcount_block_offset,
102
        (void**) &refcount_block);
103
    if (ret < 0) {
104
        return ret;
105
    }
106

    
107
    block_index = cluster_index &
108
        ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
109
    refcount = be16_to_cpu(refcount_block[block_index]);
110

    
111
    ret = qcow2_cache_put(bs, s->refcount_block_cache,
112
        (void**) &refcount_block);
113
    if (ret < 0) {
114
        return ret;
115
    }
116

    
117
    return refcount;
118
}
119

    
120
/*
121
 * Rounds the refcount table size up to avoid growing the table for each single
122
 * refcount block that is allocated.
123
 */
124
static unsigned int next_refcount_table_size(BDRVQcowState *s,
125
    unsigned int min_size)
126
{
127
    unsigned int min_clusters = (min_size >> (s->cluster_bits - 3)) + 1;
128
    unsigned int refcount_table_clusters =
129
        MAX(1, s->refcount_table_size >> (s->cluster_bits - 3));
130

    
131
    while (min_clusters > refcount_table_clusters) {
132
        refcount_table_clusters = (refcount_table_clusters * 3 + 1) / 2;
133
    }
134

    
135
    return refcount_table_clusters << (s->cluster_bits - 3);
136
}
137

    
138

    
139
/* Checks if two offsets are described by the same refcount block */
140
static int in_same_refcount_block(BDRVQcowState *s, uint64_t offset_a,
141
    uint64_t offset_b)
142
{
143
    uint64_t block_a = offset_a >> (2 * s->cluster_bits - REFCOUNT_SHIFT);
144
    uint64_t block_b = offset_b >> (2 * s->cluster_bits - REFCOUNT_SHIFT);
145

    
146
    return (block_a == block_b);
147
}
148

    
149
/*
150
 * Loads a refcount block. If it doesn't exist yet, it is allocated first
151
 * (including growing the refcount table if needed).
152
 *
153
 * Returns 0 on success or -errno in error case
154
 */
155
static int alloc_refcount_block(BlockDriverState *bs,
156
    int64_t cluster_index, uint16_t **refcount_block)
157
{
158
    BDRVQcowState *s = bs->opaque;
159
    unsigned int refcount_table_index;
160
    int ret;
161

    
162
    BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC);
163

    
164
    /* Find the refcount block for the given cluster */
165
    refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
166

    
167
    if (refcount_table_index < s->refcount_table_size) {
168

    
169
        uint64_t refcount_block_offset =
170
            s->refcount_table[refcount_table_index];
171

    
172
        /* If it's already there, we're done */
173
        if (refcount_block_offset) {
174
             return load_refcount_block(bs, refcount_block_offset,
175
                 (void**) refcount_block);
176
        }
177
    }
178

    
179
    /*
180
     * If we came here, we need to allocate something. Something is at least
181
     * a cluster for the new refcount block. It may also include a new refcount
182
     * table if the old refcount table is too small.
183
     *
184
     * Note that allocating clusters here needs some special care:
185
     *
186
     * - We can't use the normal qcow2_alloc_clusters(), it would try to
187
     *   increase the refcount and very likely we would end up with an endless
188
     *   recursion. Instead we must place the refcount blocks in a way that
189
     *   they can describe them themselves.
190
     *
191
     * - We need to consider that at this point we are inside update_refcounts
192
     *   and doing the initial refcount increase. This means that some clusters
193
     *   have already been allocated by the caller, but their refcount isn't
194
     *   accurate yet. free_cluster_index tells us where this allocation ends
195
     *   as long as we don't overwrite it by freeing clusters.
196
     *
197
     * - alloc_clusters_noref and qcow2_free_clusters may load a different
198
     *   refcount block into the cache
199
     */
200

    
201
    *refcount_block = NULL;
202

    
203
    /* We write to the refcount table, so we might depend on L2 tables */
204
    qcow2_cache_flush(bs, s->l2_table_cache);
205

    
206
    /* Allocate the refcount block itself and mark it as used */
207
    int64_t new_block = alloc_clusters_noref(bs, s->cluster_size);
208
    if (new_block < 0) {
209
        return new_block;
210
    }
211

    
212
#ifdef DEBUG_ALLOC2
213
    fprintf(stderr, "qcow2: Allocate refcount block %d for %" PRIx64
214
        " at %" PRIx64 "\n",
215
        refcount_table_index, cluster_index << s->cluster_bits, new_block);
216
#endif
217

    
218
    if (in_same_refcount_block(s, new_block, cluster_index << s->cluster_bits)) {
219
        /* Zero the new refcount block before updating it */
220
        ret = qcow2_cache_get_empty(bs, s->refcount_block_cache, new_block,
221
            (void**) refcount_block);
222
        if (ret < 0) {
223
            goto fail_block;
224
        }
225

    
226
        memset(*refcount_block, 0, s->cluster_size);
227

    
228
        /* The block describes itself, need to update the cache */
229
        int block_index = (new_block >> s->cluster_bits) &
230
            ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
231
        (*refcount_block)[block_index] = cpu_to_be16(1);
232
    } else {
233
        /* Described somewhere else. This can recurse at most twice before we
234
         * arrive at a block that describes itself. */
235
        ret = update_refcount(bs, new_block, s->cluster_size, 1);
236
        if (ret < 0) {
237
            goto fail_block;
238
        }
239

    
240
        bdrv_flush(bs->file);
241

    
242
        /* Initialize the new refcount block only after updating its refcount,
243
         * update_refcount uses the refcount cache itself */
244
        ret = qcow2_cache_get_empty(bs, s->refcount_block_cache, new_block,
245
            (void**) refcount_block);
246
        if (ret < 0) {
247
            goto fail_block;
248
        }
249

    
250
        memset(*refcount_block, 0, s->cluster_size);
251
    }
252

    
253
    /* Now the new refcount block needs to be written to disk */
254
    BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_WRITE);
255
    qcow2_cache_entry_mark_dirty(s->refcount_block_cache, *refcount_block);
256
    ret = qcow2_cache_flush(bs, s->refcount_block_cache);
257
    if (ret < 0) {
258
        goto fail_block;
259
    }
260

    
261
    /* If the refcount table is big enough, just hook the block up there */
262
    if (refcount_table_index < s->refcount_table_size) {
263
        uint64_t data64 = cpu_to_be64(new_block);
264
        BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_HOOKUP);
265
        ret = bdrv_pwrite_sync(bs->file,
266
            s->refcount_table_offset + refcount_table_index * sizeof(uint64_t),
267
            &data64, sizeof(data64));
268
        if (ret < 0) {
269
            goto fail_block;
270
        }
271

    
272
        s->refcount_table[refcount_table_index] = new_block;
273
        return 0;
274
    }
275

    
276
    ret = qcow2_cache_put(bs, s->refcount_block_cache, (void**) refcount_block);
277
    if (ret < 0) {
278
        goto fail_block;
279
    }
280

    
281
    /*
282
     * If we come here, we need to grow the refcount table. Again, a new
283
     * refcount table needs some space and we can't simply allocate to avoid
284
     * endless recursion.
285
     *
286
     * Therefore let's grab new refcount blocks at the end of the image, which
287
     * will describe themselves and the new refcount table. This way we can
288
     * reference them only in the new table and do the switch to the new
289
     * refcount table at once without producing an inconsistent state in
290
     * between.
291
     */
292
    BLKDBG_EVENT(bs->file, BLKDBG_REFTABLE_GROW);
293

    
294
    /* Calculate the number of refcount blocks needed so far */
295
    uint64_t refcount_block_clusters = 1 << (s->cluster_bits - REFCOUNT_SHIFT);
296
    uint64_t blocks_used = (s->free_cluster_index +
297
        refcount_block_clusters - 1) / refcount_block_clusters;
298

    
299
    /* And now we need at least one block more for the new metadata */
300
    uint64_t table_size = next_refcount_table_size(s, blocks_used + 1);
301
    uint64_t last_table_size;
302
    uint64_t blocks_clusters;
303
    do {
304
        uint64_t table_clusters = size_to_clusters(s, table_size);
305
        blocks_clusters = 1 +
306
            ((table_clusters + refcount_block_clusters - 1)
307
            / refcount_block_clusters);
308
        uint64_t meta_clusters = table_clusters + blocks_clusters;
309

    
310
        last_table_size = table_size;
311
        table_size = next_refcount_table_size(s, blocks_used +
312
            ((meta_clusters + refcount_block_clusters - 1)
313
            / refcount_block_clusters));
314

    
315
    } while (last_table_size != table_size);
316

    
317
#ifdef DEBUG_ALLOC2
318
    fprintf(stderr, "qcow2: Grow refcount table %" PRId32 " => %" PRId64 "\n",
319
        s->refcount_table_size, table_size);
320
#endif
321

    
322
    /* Create the new refcount table and blocks */
323
    uint64_t meta_offset = (blocks_used * refcount_block_clusters) *
324
        s->cluster_size;
325
    uint64_t table_offset = meta_offset + blocks_clusters * s->cluster_size;
326
    uint16_t *new_blocks = qemu_mallocz(blocks_clusters * s->cluster_size);
327
    uint64_t *new_table = qemu_mallocz(table_size * sizeof(uint64_t));
328

    
329
    assert(meta_offset >= (s->free_cluster_index * s->cluster_size));
330

    
331
    /* Fill the new refcount table */
332
    memcpy(new_table, s->refcount_table,
333
        s->refcount_table_size * sizeof(uint64_t));
334
    new_table[refcount_table_index] = new_block;
335

    
336
    int i;
337
    for (i = 0; i < blocks_clusters; i++) {
338
        new_table[blocks_used + i] = meta_offset + (i * s->cluster_size);
339
    }
340

    
341
    /* Fill the refcount blocks */
342
    uint64_t table_clusters = size_to_clusters(s, table_size * sizeof(uint64_t));
343
    int block = 0;
344
    for (i = 0; i < table_clusters + blocks_clusters; i++) {
345
        new_blocks[block++] = cpu_to_be16(1);
346
    }
347

    
348
    /* Write refcount blocks to disk */
349
    BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_WRITE_BLOCKS);
350
    ret = bdrv_pwrite_sync(bs->file, meta_offset, new_blocks,
351
        blocks_clusters * s->cluster_size);
352
    qemu_free(new_blocks);
353
    if (ret < 0) {
354
        goto fail_table;
355
    }
356

    
357
    /* Write refcount table to disk */
358
    for(i = 0; i < table_size; i++) {
359
        cpu_to_be64s(&new_table[i]);
360
    }
361

    
362
    BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_WRITE_TABLE);
363
    ret = bdrv_pwrite_sync(bs->file, table_offset, new_table,
364
        table_size * sizeof(uint64_t));
365
    if (ret < 0) {
366
        goto fail_table;
367
    }
368

    
369
    for(i = 0; i < table_size; i++) {
370
        cpu_to_be64s(&new_table[i]);
371
    }
372

    
373
    /* Hook up the new refcount table in the qcow2 header */
374
    uint8_t data[12];
375
    cpu_to_be64w((uint64_t*)data, table_offset);
376
    cpu_to_be32w((uint32_t*)(data + 8), table_clusters);
377
    BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_SWITCH_TABLE);
378
    ret = bdrv_pwrite_sync(bs->file, offsetof(QCowHeader, refcount_table_offset),
379
        data, sizeof(data));
380
    if (ret < 0) {
381
        goto fail_table;
382
    }
383

    
384
    /* And switch it in memory */
385
    uint64_t old_table_offset = s->refcount_table_offset;
386
    uint64_t old_table_size = s->refcount_table_size;
387

    
388
    qemu_free(s->refcount_table);
389
    s->refcount_table = new_table;
390
    s->refcount_table_size = table_size;
391
    s->refcount_table_offset = table_offset;
392

    
393
    /* Free old table. Remember, we must not change free_cluster_index */
394
    uint64_t old_free_cluster_index = s->free_cluster_index;
395
    qcow2_free_clusters(bs, old_table_offset, old_table_size * sizeof(uint64_t));
396
    s->free_cluster_index = old_free_cluster_index;
397

    
398
    ret = load_refcount_block(bs, new_block, (void**) refcount_block);
399
    if (ret < 0) {
400
        return ret;
401
    }
402

    
403
    return new_block;
404

    
405
fail_table:
406
    qemu_free(new_table);
407
fail_block:
408
    if (*refcount_block != NULL) {
409
        qcow2_cache_put(bs, s->refcount_block_cache, (void**) refcount_block);
410
    }
411
    return ret;
412
}
413

    
414
/* XXX: cache several refcount block clusters ? */
415
static int QEMU_WARN_UNUSED_RESULT update_refcount(BlockDriverState *bs,
416
    int64_t offset, int64_t length, int addend)
417
{
418
    BDRVQcowState *s = bs->opaque;
419
    int64_t start, last, cluster_offset;
420
    uint16_t *refcount_block = NULL;
421
    int64_t old_table_index = -1;
422
    int ret;
423

    
424
#ifdef DEBUG_ALLOC2
425
    printf("update_refcount: offset=%" PRId64 " size=%" PRId64 " addend=%d\n",
426
           offset, length, addend);
427
#endif
428
    if (length < 0) {
429
        return -EINVAL;
430
    } else if (length == 0) {
431
        return 0;
432
    }
433

    
434
    if (addend < 0) {
435
        qcow2_cache_set_dependency(bs, s->refcount_block_cache,
436
            s->l2_table_cache);
437
    }
438

    
439
    start = offset & ~(s->cluster_size - 1);
440
    last = (offset + length - 1) & ~(s->cluster_size - 1);
441
    for(cluster_offset = start; cluster_offset <= last;
442
        cluster_offset += s->cluster_size)
443
    {
444
        int block_index, refcount;
445
        int64_t cluster_index = cluster_offset >> s->cluster_bits;
446
        int64_t table_index =
447
            cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
448

    
449
        /* Load the refcount block and allocate it if needed */
450
        if (table_index != old_table_index) {
451
            if (refcount_block) {
452
                ret = qcow2_cache_put(bs, s->refcount_block_cache,
453
                    (void**) &refcount_block);
454
                if (ret < 0) {
455
                    goto fail;
456
                }
457
            }
458

    
459
            ret = alloc_refcount_block(bs, cluster_index, &refcount_block);
460
            if (ret < 0) {
461
                goto fail;
462
            }
463
        }
464
        old_table_index = table_index;
465

    
466
        qcow2_cache_entry_mark_dirty(s->refcount_block_cache, refcount_block);
467

    
468
        /* we can update the count and save it */
469
        block_index = cluster_index &
470
            ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
471

    
472
        refcount = be16_to_cpu(refcount_block[block_index]);
473
        refcount += addend;
474
        if (refcount < 0 || refcount > 0xffff) {
475
            ret = -EINVAL;
476
            goto fail;
477
        }
478
        if (refcount == 0 && cluster_index < s->free_cluster_index) {
479
            s->free_cluster_index = cluster_index;
480
        }
481
        refcount_block[block_index] = cpu_to_be16(refcount);
482
    }
483

    
484
    ret = 0;
485
fail:
486
    /* Write last changed block to disk */
487
    if (refcount_block) {
488
        int wret;
489
        wret = qcow2_cache_put(bs, s->refcount_block_cache,
490
            (void**) &refcount_block);
491
        if (wret < 0) {
492
            return ret < 0 ? ret : wret;
493
        }
494
    }
495

    
496
    /*
497
     * Try do undo any updates if an error is returned (This may succeed in
498
     * some cases like ENOSPC for allocating a new refcount block)
499
     */
500
    if (ret < 0) {
501
        int dummy;
502
        dummy = update_refcount(bs, offset, cluster_offset - offset, -addend);
503
        (void)dummy;
504
    }
505

    
506
    return ret;
507
}
508

    
509
/*
510
 * Increases or decreases the refcount of a given cluster by one.
511
 * addend must be 1 or -1.
512
 *
513
 * If the return value is non-negative, it is the new refcount of the cluster.
514
 * If it is negative, it is -errno and indicates an error.
515
 */
516
static int update_cluster_refcount(BlockDriverState *bs,
517
                                   int64_t cluster_index,
518
                                   int addend)
519
{
520
    BDRVQcowState *s = bs->opaque;
521
    int ret;
522

    
523
    ret = update_refcount(bs, cluster_index << s->cluster_bits, 1, addend);
524
    if (ret < 0) {
525
        return ret;
526
    }
527

    
528
    bdrv_flush(bs->file);
529

    
530
    return get_refcount(bs, cluster_index);
531
}
532

    
533

    
534

    
535
/*********************************************************/
536
/* cluster allocation functions */
537

    
538

    
539

    
540
/* return < 0 if error */
541
static int64_t alloc_clusters_noref(BlockDriverState *bs, int64_t size)
542
{
543
    BDRVQcowState *s = bs->opaque;
544
    int i, nb_clusters, refcount;
545

    
546
    nb_clusters = size_to_clusters(s, size);
547
retry:
548
    for(i = 0; i < nb_clusters; i++) {
549
        int64_t next_cluster_index = s->free_cluster_index++;
550
        refcount = get_refcount(bs, next_cluster_index);
551

    
552
        if (refcount < 0) {
553
            return refcount;
554
        } else if (refcount != 0) {
555
            goto retry;
556
        }
557
    }
558
#ifdef DEBUG_ALLOC2
559
    printf("alloc_clusters: size=%" PRId64 " -> %" PRId64 "\n",
560
            size,
561
            (s->free_cluster_index - nb_clusters) << s->cluster_bits);
562
#endif
563
    return (s->free_cluster_index - nb_clusters) << s->cluster_bits;
564
}
565

    
566
int64_t qcow2_alloc_clusters(BlockDriverState *bs, int64_t size)
567
{
568
    int64_t offset;
569
    int ret;
570

    
571
    BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_ALLOC);
572
    offset = alloc_clusters_noref(bs, size);
573
    if (offset < 0) {
574
        return offset;
575
    }
576

    
577
    ret = update_refcount(bs, offset, size, 1);
578
    if (ret < 0) {
579
        return ret;
580
    }
581

    
582
    return offset;
583
}
584

    
585
/* only used to allocate compressed sectors. We try to allocate
586
   contiguous sectors. size must be <= cluster_size */
587
int64_t qcow2_alloc_bytes(BlockDriverState *bs, int size)
588
{
589
    BDRVQcowState *s = bs->opaque;
590
    int64_t offset, cluster_offset;
591
    int free_in_cluster;
592

    
593
    BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_ALLOC_BYTES);
594
    assert(size > 0 && size <= s->cluster_size);
595
    if (s->free_byte_offset == 0) {
596
        s->free_byte_offset = qcow2_alloc_clusters(bs, s->cluster_size);
597
        if (s->free_byte_offset < 0) {
598
            return s->free_byte_offset;
599
        }
600
    }
601
 redo:
602
    free_in_cluster = s->cluster_size -
603
        (s->free_byte_offset & (s->cluster_size - 1));
604
    if (size <= free_in_cluster) {
605
        /* enough space in current cluster */
606
        offset = s->free_byte_offset;
607
        s->free_byte_offset += size;
608
        free_in_cluster -= size;
609
        if (free_in_cluster == 0)
610
            s->free_byte_offset = 0;
611
        if ((offset & (s->cluster_size - 1)) != 0)
612
            update_cluster_refcount(bs, offset >> s->cluster_bits, 1);
613
    } else {
614
        offset = qcow2_alloc_clusters(bs, s->cluster_size);
615
        if (offset < 0) {
616
            return offset;
617
        }
618
        cluster_offset = s->free_byte_offset & ~(s->cluster_size - 1);
619
        if ((cluster_offset + s->cluster_size) == offset) {
620
            /* we are lucky: contiguous data */
621
            offset = s->free_byte_offset;
622
            update_cluster_refcount(bs, offset >> s->cluster_bits, 1);
623
            s->free_byte_offset += size;
624
        } else {
625
            s->free_byte_offset = offset;
626
            goto redo;
627
        }
628
    }
629

    
630
    bdrv_flush(bs->file);
631
    return offset;
632
}
633

    
634
void qcow2_free_clusters(BlockDriverState *bs,
635
                          int64_t offset, int64_t size)
636
{
637
    int ret;
638

    
639
    BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_FREE);
640
    ret = update_refcount(bs, offset, size, -1);
641
    if (ret < 0) {
642
        fprintf(stderr, "qcow2_free_clusters failed: %s\n", strerror(-ret));
643
        /* TODO Remember the clusters to free them later and avoid leaking */
644
    }
645
}
646

    
647
/*
648
 * free_any_clusters
649
 *
650
 * free clusters according to its type: compressed or not
651
 *
652
 */
653

    
654
void qcow2_free_any_clusters(BlockDriverState *bs,
655
    uint64_t cluster_offset, int nb_clusters)
656
{
657
    BDRVQcowState *s = bs->opaque;
658

    
659
    /* free the cluster */
660

    
661
    if (cluster_offset & QCOW_OFLAG_COMPRESSED) {
662
        int nb_csectors;
663
        nb_csectors = ((cluster_offset >> s->csize_shift) &
664
                       s->csize_mask) + 1;
665
        qcow2_free_clusters(bs,
666
            (cluster_offset & s->cluster_offset_mask) & ~511,
667
            nb_csectors * 512);
668
        return;
669
    }
670

    
671
    qcow2_free_clusters(bs, cluster_offset, nb_clusters << s->cluster_bits);
672

    
673
    return;
674
}
675

    
676

    
677

    
678
/*********************************************************/
679
/* snapshots and image creation */
680

    
681

    
682

    
683
void qcow2_create_refcount_update(QCowCreateState *s, int64_t offset,
684
    int64_t size)
685
{
686
    int refcount;
687
    int64_t start, last, cluster_offset;
688
    uint16_t *p;
689

    
690
    start = offset & ~(s->cluster_size - 1);
691
    last = (offset + size - 1)  & ~(s->cluster_size - 1);
692
    for(cluster_offset = start; cluster_offset <= last;
693
        cluster_offset += s->cluster_size) {
694
        p = &s->refcount_block[cluster_offset >> s->cluster_bits];
695
        refcount = be16_to_cpu(*p);
696
        refcount++;
697
        *p = cpu_to_be16(refcount);
698
    }
699
}
700

    
701
/* update the refcounts of snapshots and the copied flag */
702
int qcow2_update_snapshot_refcount(BlockDriverState *bs,
703
    int64_t l1_table_offset, int l1_size, int addend)
704
{
705
    BDRVQcowState *s = bs->opaque;
706
    uint64_t *l1_table, *l2_table, l2_offset, offset, l1_size2, l1_allocated;
707
    int64_t old_offset, old_l2_offset;
708
    int i, j, l1_modified, nb_csectors, refcount;
709
    int ret;
710

    
711
    l2_table = NULL;
712
    l1_table = NULL;
713
    l1_size2 = l1_size * sizeof(uint64_t);
714
    if (l1_table_offset != s->l1_table_offset) {
715
        if (l1_size2 != 0) {
716
            l1_table = qemu_mallocz(align_offset(l1_size2, 512));
717
        } else {
718
            l1_table = NULL;
719
        }
720
        l1_allocated = 1;
721
        if (bdrv_pread(bs->file, l1_table_offset,
722
                       l1_table, l1_size2) != l1_size2)
723
            goto fail;
724
        for(i = 0;i < l1_size; i++)
725
            be64_to_cpus(&l1_table[i]);
726
    } else {
727
        assert(l1_size == s->l1_size);
728
        l1_table = s->l1_table;
729
        l1_allocated = 0;
730
    }
731

    
732
    l1_modified = 0;
733
    for(i = 0; i < l1_size; i++) {
734
        l2_offset = l1_table[i];
735
        if (l2_offset) {
736
            old_l2_offset = l2_offset;
737
            l2_offset &= ~QCOW_OFLAG_COPIED;
738

    
739
            ret = qcow2_cache_get(bs, s->l2_table_cache, l2_offset,
740
                (void**) &l2_table);
741
            if (ret < 0) {
742
                goto fail;
743
            }
744

    
745
            for(j = 0; j < s->l2_size; j++) {
746
                offset = be64_to_cpu(l2_table[j]);
747
                if (offset != 0) {
748
                    old_offset = offset;
749
                    offset &= ~QCOW_OFLAG_COPIED;
750
                    if (offset & QCOW_OFLAG_COMPRESSED) {
751
                        nb_csectors = ((offset >> s->csize_shift) &
752
                                       s->csize_mask) + 1;
753
                        if (addend != 0) {
754
                            int ret;
755
                            ret = update_refcount(bs,
756
                                (offset & s->cluster_offset_mask) & ~511,
757
                                nb_csectors * 512, addend);
758
                            if (ret < 0) {
759
                                goto fail;
760
                            }
761

    
762
                            /* TODO Flushing once for the whole function should
763
                             * be enough */
764
                            bdrv_flush(bs->file);
765
                        }
766
                        /* compressed clusters are never modified */
767
                        refcount = 2;
768
                    } else {
769
                        if (addend != 0) {
770
                            refcount = update_cluster_refcount(bs, offset >> s->cluster_bits, addend);
771
                        } else {
772
                            refcount = get_refcount(bs, offset >> s->cluster_bits);
773
                        }
774

    
775
                        if (refcount < 0) {
776
                            goto fail;
777
                        }
778
                    }
779

    
780
                    if (refcount == 1) {
781
                        offset |= QCOW_OFLAG_COPIED;
782
                    }
783
                    if (offset != old_offset) {
784
                        if (addend > 0) {
785
                            qcow2_cache_set_dependency(bs, s->l2_table_cache,
786
                                s->refcount_block_cache);
787
                        }
788
                        l2_table[j] = cpu_to_be64(offset);
789
                        qcow2_cache_entry_mark_dirty(s->l2_table_cache, l2_table);
790
                    }
791
                }
792
            }
793

    
794
            ret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
795
            if (ret < 0) {
796
                goto fail;
797
            }
798

    
799

    
800
            if (addend != 0) {
801
                refcount = update_cluster_refcount(bs, l2_offset >> s->cluster_bits, addend);
802
            } else {
803
                refcount = get_refcount(bs, l2_offset >> s->cluster_bits);
804
            }
805
            if (refcount < 0) {
806
                goto fail;
807
            } else if (refcount == 1) {
808
                l2_offset |= QCOW_OFLAG_COPIED;
809
            }
810
            if (l2_offset != old_l2_offset) {
811
                l1_table[i] = l2_offset;
812
                l1_modified = 1;
813
            }
814
        }
815
    }
816
    if (l1_modified) {
817
        for(i = 0; i < l1_size; i++)
818
            cpu_to_be64s(&l1_table[i]);
819
        if (bdrv_pwrite_sync(bs->file, l1_table_offset, l1_table,
820
                        l1_size2) < 0)
821
            goto fail;
822
        for(i = 0; i < l1_size; i++)
823
            be64_to_cpus(&l1_table[i]);
824
    }
825
    if (l1_allocated)
826
        qemu_free(l1_table);
827
    return 0;
828
 fail:
829
    if (l2_table) {
830
        qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
831
    }
832

    
833
    if (l1_allocated)
834
        qemu_free(l1_table);
835
    return -EIO;
836
}
837

    
838

    
839

    
840

    
841
/*********************************************************/
842
/* refcount checking functions */
843

    
844

    
845

    
846
/*
847
 * Increases the refcount for a range of clusters in a given refcount table.
848
 * This is used to construct a temporary refcount table out of L1 and L2 tables
849
 * which can be compared the the refcount table saved in the image.
850
 *
851
 * Modifies the number of errors in res.
852
 */
853
static void inc_refcounts(BlockDriverState *bs,
854
                          BdrvCheckResult *res,
855
                          uint16_t *refcount_table,
856
                          int refcount_table_size,
857
                          int64_t offset, int64_t size)
858
{
859
    BDRVQcowState *s = bs->opaque;
860
    int64_t start, last, cluster_offset;
861
    int k;
862

    
863
    if (size <= 0)
864
        return;
865

    
866
    start = offset & ~(s->cluster_size - 1);
867
    last = (offset + size - 1) & ~(s->cluster_size - 1);
868
    for(cluster_offset = start; cluster_offset <= last;
869
        cluster_offset += s->cluster_size) {
870
        k = cluster_offset >> s->cluster_bits;
871
        if (k < 0) {
872
            fprintf(stderr, "ERROR: invalid cluster offset=0x%" PRIx64 "\n",
873
                cluster_offset);
874
            res->corruptions++;
875
        } else if (k >= refcount_table_size) {
876
            fprintf(stderr, "Warning: cluster offset=0x%" PRIx64 " is after "
877
                "the end of the image file, can't properly check refcounts.\n",
878
                cluster_offset);
879
            res->check_errors++;
880
        } else {
881
            if (++refcount_table[k] == 0) {
882
                fprintf(stderr, "ERROR: overflow cluster offset=0x%" PRIx64
883
                    "\n", cluster_offset);
884
                res->corruptions++;
885
            }
886
        }
887
    }
888
}
889

    
890
/*
891
 * Increases the refcount in the given refcount table for the all clusters
892
 * referenced in the L2 table. While doing so, performs some checks on L2
893
 * entries.
894
 *
895
 * Returns the number of errors found by the checks or -errno if an internal
896
 * error occurred.
897
 */
898
static int check_refcounts_l2(BlockDriverState *bs, BdrvCheckResult *res,
899
    uint16_t *refcount_table, int refcount_table_size, int64_t l2_offset,
900
    int check_copied)
901
{
902
    BDRVQcowState *s = bs->opaque;
903
    uint64_t *l2_table, offset;
904
    int i, l2_size, nb_csectors, refcount;
905

    
906
    /* Read L2 table from disk */
907
    l2_size = s->l2_size * sizeof(uint64_t);
908
    l2_table = qemu_malloc(l2_size);
909

    
910
    if (bdrv_pread(bs->file, l2_offset, l2_table, l2_size) != l2_size)
911
        goto fail;
912

    
913
    /* Do the actual checks */
914
    for(i = 0; i < s->l2_size; i++) {
915
        offset = be64_to_cpu(l2_table[i]);
916
        if (offset != 0) {
917
            if (offset & QCOW_OFLAG_COMPRESSED) {
918
                /* Compressed clusters don't have QCOW_OFLAG_COPIED */
919
                if (offset & QCOW_OFLAG_COPIED) {
920
                    fprintf(stderr, "ERROR: cluster %" PRId64 ": "
921
                        "copied flag must never be set for compressed "
922
                        "clusters\n", offset >> s->cluster_bits);
923
                    offset &= ~QCOW_OFLAG_COPIED;
924
                    res->corruptions++;
925
                }
926

    
927
                /* Mark cluster as used */
928
                nb_csectors = ((offset >> s->csize_shift) &
929
                               s->csize_mask) + 1;
930
                offset &= s->cluster_offset_mask;
931
                inc_refcounts(bs, res, refcount_table, refcount_table_size,
932
                    offset & ~511, nb_csectors * 512);
933
            } else {
934
                /* QCOW_OFLAG_COPIED must be set iff refcount == 1 */
935
                if (check_copied) {
936
                    uint64_t entry = offset;
937
                    offset &= ~QCOW_OFLAG_COPIED;
938
                    refcount = get_refcount(bs, offset >> s->cluster_bits);
939
                    if (refcount < 0) {
940
                        fprintf(stderr, "Can't get refcount for offset %"
941
                            PRIx64 ": %s\n", entry, strerror(-refcount));
942
                        goto fail;
943
                    }
944
                    if ((refcount == 1) != ((entry & QCOW_OFLAG_COPIED) != 0)) {
945
                        fprintf(stderr, "ERROR OFLAG_COPIED: offset=%"
946
                            PRIx64 " refcount=%d\n", entry, refcount);
947
                        res->corruptions++;
948
                    }
949
                }
950

    
951
                /* Mark cluster as used */
952
                offset &= ~QCOW_OFLAG_COPIED;
953
                inc_refcounts(bs, res, refcount_table,refcount_table_size,
954
                    offset, s->cluster_size);
955

    
956
                /* Correct offsets are cluster aligned */
957
                if (offset & (s->cluster_size - 1)) {
958
                    fprintf(stderr, "ERROR offset=%" PRIx64 ": Cluster is not "
959
                        "properly aligned; L2 entry corrupted.\n", offset);
960
                    res->corruptions++;
961
                }
962
            }
963
        }
964
    }
965

    
966
    qemu_free(l2_table);
967
    return 0;
968

    
969
fail:
970
    fprintf(stderr, "ERROR: I/O error in check_refcounts_l2\n");
971
    qemu_free(l2_table);
972
    return -EIO;
973
}
974

    
975
/*
976
 * Increases the refcount for the L1 table, its L2 tables and all referenced
977
 * clusters in the given refcount table. While doing so, performs some checks
978
 * on L1 and L2 entries.
979
 *
980
 * Returns the number of errors found by the checks or -errno if an internal
981
 * error occurred.
982
 */
983
static int check_refcounts_l1(BlockDriverState *bs,
984
                              BdrvCheckResult *res,
985
                              uint16_t *refcount_table,
986
                              int refcount_table_size,
987
                              int64_t l1_table_offset, int l1_size,
988
                              int check_copied)
989
{
990
    BDRVQcowState *s = bs->opaque;
991
    uint64_t *l1_table, l2_offset, l1_size2;
992
    int i, refcount, ret;
993

    
994
    l1_size2 = l1_size * sizeof(uint64_t);
995

    
996
    /* Mark L1 table as used */
997
    inc_refcounts(bs, res, refcount_table, refcount_table_size,
998
        l1_table_offset, l1_size2);
999

    
1000
    /* Read L1 table entries from disk */
1001
    if (l1_size2 == 0) {
1002
        l1_table = NULL;
1003
    } else {
1004
        l1_table = qemu_malloc(l1_size2);
1005
        if (bdrv_pread(bs->file, l1_table_offset,
1006
                       l1_table, l1_size2) != l1_size2)
1007
            goto fail;
1008
        for(i = 0;i < l1_size; i++)
1009
            be64_to_cpus(&l1_table[i]);
1010
    }
1011

    
1012
    /* Do the actual checks */
1013
    for(i = 0; i < l1_size; i++) {
1014
        l2_offset = l1_table[i];
1015
        if (l2_offset) {
1016
            /* QCOW_OFLAG_COPIED must be set iff refcount == 1 */
1017
            if (check_copied) {
1018
                refcount = get_refcount(bs, (l2_offset & ~QCOW_OFLAG_COPIED)
1019
                    >> s->cluster_bits);
1020
                if (refcount < 0) {
1021
                    fprintf(stderr, "Can't get refcount for l2_offset %"
1022
                        PRIx64 ": %s\n", l2_offset, strerror(-refcount));
1023
                    goto fail;
1024
                }
1025
                if ((refcount == 1) != ((l2_offset & QCOW_OFLAG_COPIED) != 0)) {
1026
                    fprintf(stderr, "ERROR OFLAG_COPIED: l2_offset=%" PRIx64
1027
                        " refcount=%d\n", l2_offset, refcount);
1028
                    res->corruptions++;
1029
                }
1030
            }
1031

    
1032
            /* Mark L2 table as used */
1033
            l2_offset &= ~QCOW_OFLAG_COPIED;
1034
            inc_refcounts(bs, res, refcount_table, refcount_table_size,
1035
                l2_offset, s->cluster_size);
1036

    
1037
            /* L2 tables are cluster aligned */
1038
            if (l2_offset & (s->cluster_size - 1)) {
1039
                fprintf(stderr, "ERROR l2_offset=%" PRIx64 ": Table is not "
1040
                    "cluster aligned; L1 entry corrupted\n", l2_offset);
1041
                res->corruptions++;
1042
            }
1043

    
1044
            /* Process and check L2 entries */
1045
            ret = check_refcounts_l2(bs, res, refcount_table,
1046
                refcount_table_size, l2_offset, check_copied);
1047
            if (ret < 0) {
1048
                goto fail;
1049
            }
1050
        }
1051
    }
1052
    qemu_free(l1_table);
1053
    return 0;
1054

    
1055
fail:
1056
    fprintf(stderr, "ERROR: I/O error in check_refcounts_l1\n");
1057
    res->check_errors++;
1058
    qemu_free(l1_table);
1059
    return -EIO;
1060
}
1061

    
1062
/*
1063
 * Checks an image for refcount consistency.
1064
 *
1065
 * Returns 0 if no errors are found, the number of errors in case the image is
1066
 * detected as corrupted, and -errno when an internal error occurred.
1067
 */
1068
int qcow2_check_refcounts(BlockDriverState *bs, BdrvCheckResult *res)
1069
{
1070
    BDRVQcowState *s = bs->opaque;
1071
    int64_t size;
1072
    int nb_clusters, refcount1, refcount2, i;
1073
    QCowSnapshot *sn;
1074
    uint16_t *refcount_table;
1075
    int ret;
1076

    
1077
    size = bdrv_getlength(bs->file);
1078
    nb_clusters = size_to_clusters(s, size);
1079
    refcount_table = qemu_mallocz(nb_clusters * sizeof(uint16_t));
1080

    
1081
    /* header */
1082
    inc_refcounts(bs, res, refcount_table, nb_clusters,
1083
        0, s->cluster_size);
1084

    
1085
    /* current L1 table */
1086
    ret = check_refcounts_l1(bs, res, refcount_table, nb_clusters,
1087
                       s->l1_table_offset, s->l1_size, 1);
1088
    if (ret < 0) {
1089
        goto fail;
1090
    }
1091

    
1092
    /* snapshots */
1093
    for(i = 0; i < s->nb_snapshots; i++) {
1094
        sn = s->snapshots + i;
1095
        ret = check_refcounts_l1(bs, res, refcount_table, nb_clusters,
1096
            sn->l1_table_offset, sn->l1_size, 0);
1097
        if (ret < 0) {
1098
            goto fail;
1099
        }
1100
    }
1101
    inc_refcounts(bs, res, refcount_table, nb_clusters,
1102
        s->snapshots_offset, s->snapshots_size);
1103

    
1104
    /* refcount data */
1105
    inc_refcounts(bs, res, refcount_table, nb_clusters,
1106
        s->refcount_table_offset,
1107
        s->refcount_table_size * sizeof(uint64_t));
1108

    
1109
    for(i = 0; i < s->refcount_table_size; i++) {
1110
        uint64_t offset, cluster;
1111
        offset = s->refcount_table[i];
1112
        cluster = offset >> s->cluster_bits;
1113

    
1114
        /* Refcount blocks are cluster aligned */
1115
        if (offset & (s->cluster_size - 1)) {
1116
            fprintf(stderr, "ERROR refcount block %d is not "
1117
                "cluster aligned; refcount table entry corrupted\n", i);
1118
            res->corruptions++;
1119
            continue;
1120
        }
1121

    
1122
        if (cluster >= nb_clusters) {
1123
            fprintf(stderr, "ERROR refcount block %d is outside image\n", i);
1124
            res->corruptions++;
1125
            continue;
1126
        }
1127

    
1128
        if (offset != 0) {
1129
            inc_refcounts(bs, res, refcount_table, nb_clusters,
1130
                offset, s->cluster_size);
1131
            if (refcount_table[cluster] != 1) {
1132
                fprintf(stderr, "ERROR refcount block %d refcount=%d\n",
1133
                    i, refcount_table[cluster]);
1134
                res->corruptions++;
1135
            }
1136
        }
1137
    }
1138

    
1139
    /* compare ref counts */
1140
    for(i = 0; i < nb_clusters; i++) {
1141
        refcount1 = get_refcount(bs, i);
1142
        if (refcount1 < 0) {
1143
            fprintf(stderr, "Can't get refcount for cluster %d: %s\n",
1144
                i, strerror(-refcount1));
1145
            res->check_errors++;
1146
            continue;
1147
        }
1148

    
1149
        refcount2 = refcount_table[i];
1150
        if (refcount1 != refcount2) {
1151
            fprintf(stderr, "%s cluster %d refcount=%d reference=%d\n",
1152
                   refcount1 < refcount2 ? "ERROR" : "Leaked",
1153
                   i, refcount1, refcount2);
1154
            if (refcount1 < refcount2) {
1155
                res->corruptions++;
1156
            } else {
1157
                res->leaks++;
1158
            }
1159
        }
1160
    }
1161

    
1162
    ret = 0;
1163

    
1164
fail:
1165
    qemu_free(refcount_table);
1166

    
1167
    return ret;
1168
}
1169