Statistics
| Branch: | Revision:

root / block / qcow2-refcount.c @ 1c02e2a1

History | View | Annotate | Download (39.2 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
static int cache_refcount_updates = 0;
36

    
37
static int write_refcount_block(BlockDriverState *bs)
38
{
39
    BDRVQcowState *s = bs->opaque;
40
    size_t size = s->cluster_size;
41

    
42
    if (s->refcount_block_cache_offset == 0) {
43
        return 0;
44
    }
45

    
46
    BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_UPDATE);
47
    if (bdrv_pwrite_sync(bs->file, s->refcount_block_cache_offset,
48
            s->refcount_block_cache, size) < 0)
49
    {
50
        return -EIO;
51
    }
52

    
53
    return 0;
54
}
55

    
56
/*********************************************************/
57
/* refcount handling */
58

    
59
int qcow2_refcount_init(BlockDriverState *bs)
60
{
61
    BDRVQcowState *s = bs->opaque;
62
    int ret, refcount_table_size2, i;
63

    
64
    s->refcount_block_cache = qemu_malloc(s->cluster_size);
65
    refcount_table_size2 = s->refcount_table_size * sizeof(uint64_t);
66
    s->refcount_table = qemu_malloc(refcount_table_size2);
67
    if (s->refcount_table_size > 0) {
68
        BLKDBG_EVENT(bs->file, BLKDBG_REFTABLE_LOAD);
69
        ret = bdrv_pread(bs->file, s->refcount_table_offset,
70
                         s->refcount_table, refcount_table_size2);
71
        if (ret != refcount_table_size2)
72
            goto fail;
73
        for(i = 0; i < s->refcount_table_size; i++)
74
            be64_to_cpus(&s->refcount_table[i]);
75
    }
76
    return 0;
77
 fail:
78
    return -ENOMEM;
79
}
80

    
81
void qcow2_refcount_close(BlockDriverState *bs)
82
{
83
    BDRVQcowState *s = bs->opaque;
84
    qemu_free(s->refcount_block_cache);
85
    qemu_free(s->refcount_table);
86
}
87

    
88

    
89
static int load_refcount_block(BlockDriverState *bs,
90
                               int64_t refcount_block_offset)
91
{
92
    BDRVQcowState *s = bs->opaque;
93
    int ret;
94

    
95
    if (cache_refcount_updates) {
96
        ret = write_refcount_block(bs);
97
        if (ret < 0) {
98
            return ret;
99
        }
100
    }
101

    
102
    BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_LOAD);
103
    ret = bdrv_pread(bs->file, refcount_block_offset, s->refcount_block_cache,
104
                     s->cluster_size);
105
    if (ret < 0) {
106
        s->refcount_block_cache_offset = 0;
107
        return ret;
108
    }
109

    
110
    s->refcount_block_cache_offset = refcount_block_offset;
111
    return 0;
112
}
113

    
114
/*
115
 * Returns the refcount of the cluster given by its index. Any non-negative
116
 * return value is the refcount of the cluster, negative values are -errno
117
 * and indicate an error.
118
 */
119
static int get_refcount(BlockDriverState *bs, int64_t cluster_index)
120
{
121
    BDRVQcowState *s = bs->opaque;
122
    int refcount_table_index, block_index;
123
    int64_t refcount_block_offset;
124
    int ret;
125

    
126
    refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
127
    if (refcount_table_index >= s->refcount_table_size)
128
        return 0;
129
    refcount_block_offset = s->refcount_table[refcount_table_index];
130
    if (!refcount_block_offset)
131
        return 0;
132
    if (refcount_block_offset != s->refcount_block_cache_offset) {
133
        /* better than nothing: return allocated if read error */
134
        ret = load_refcount_block(bs, refcount_block_offset);
135
        if (ret < 0) {
136
            return ret;
137
        }
138
    }
139
    block_index = cluster_index &
140
        ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
141
    return be16_to_cpu(s->refcount_block_cache[block_index]);
142
}
143

    
144
/*
145
 * Rounds the refcount table size up to avoid growing the table for each single
146
 * refcount block that is allocated.
147
 */
148
static unsigned int next_refcount_table_size(BDRVQcowState *s,
149
    unsigned int min_size)
150
{
151
    unsigned int min_clusters = (min_size >> (s->cluster_bits - 3)) + 1;
152
    unsigned int refcount_table_clusters =
153
        MAX(1, s->refcount_table_size >> (s->cluster_bits - 3));
154

    
155
    while (min_clusters > refcount_table_clusters) {
156
        refcount_table_clusters = (refcount_table_clusters * 3 + 1) / 2;
157
    }
158

    
159
    return refcount_table_clusters << (s->cluster_bits - 3);
160
}
161

    
162

    
163
/* Checks if two offsets are described by the same refcount block */
164
static int in_same_refcount_block(BDRVQcowState *s, uint64_t offset_a,
165
    uint64_t offset_b)
166
{
167
    uint64_t block_a = offset_a >> (2 * s->cluster_bits - REFCOUNT_SHIFT);
168
    uint64_t block_b = offset_b >> (2 * s->cluster_bits - REFCOUNT_SHIFT);
169

    
170
    return (block_a == block_b);
171
}
172

    
173
/*
174
 * Loads a refcount block. If it doesn't exist yet, it is allocated first
175
 * (including growing the refcount table if needed).
176
 *
177
 * Returns the offset of the refcount block on success or -errno in error case
178
 */
179
static int64_t alloc_refcount_block(BlockDriverState *bs, int64_t cluster_index)
180
{
181
    BDRVQcowState *s = bs->opaque;
182
    unsigned int refcount_table_index;
183
    int ret;
184

    
185
    BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC);
186

    
187
    /* Find the refcount block for the given cluster */
188
    refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
189

    
190
    if (refcount_table_index < s->refcount_table_size) {
191

    
192
        uint64_t refcount_block_offset =
193
            s->refcount_table[refcount_table_index];
194

    
195
        /* If it's already there, we're done */
196
        if (refcount_block_offset) {
197
            if (refcount_block_offset != s->refcount_block_cache_offset) {
198
                ret = load_refcount_block(bs, refcount_block_offset);
199
                if (ret < 0) {
200
                    return ret;
201
                }
202
            }
203
            return refcount_block_offset;
204
        }
205
    }
206

    
207
    /*
208
     * If we came here, we need to allocate something. Something is at least
209
     * a cluster for the new refcount block. It may also include a new refcount
210
     * table if the old refcount table is too small.
211
     *
212
     * Note that allocating clusters here needs some special care:
213
     *
214
     * - We can't use the normal qcow2_alloc_clusters(), it would try to
215
     *   increase the refcount and very likely we would end up with an endless
216
     *   recursion. Instead we must place the refcount blocks in a way that
217
     *   they can describe them themselves.
218
     *
219
     * - We need to consider that at this point we are inside update_refcounts
220
     *   and doing the initial refcount increase. This means that some clusters
221
     *   have already been allocated by the caller, but their refcount isn't
222
     *   accurate yet. free_cluster_index tells us where this allocation ends
223
     *   as long as we don't overwrite it by freeing clusters.
224
     *
225
     * - alloc_clusters_noref and qcow2_free_clusters may load a different
226
     *   refcount block into the cache
227
     */
228

    
229
    if (cache_refcount_updates) {
230
        ret = write_refcount_block(bs);
231
        if (ret < 0) {
232
            return ret;
233
        }
234
    }
235

    
236
    /* Allocate the refcount block itself and mark it as used */
237
    int64_t new_block = alloc_clusters_noref(bs, s->cluster_size);
238
    if (new_block < 0) {
239
        return new_block;
240
    }
241

    
242
#ifdef DEBUG_ALLOC2
243
    fprintf(stderr, "qcow2: Allocate refcount block %d for %" PRIx64
244
        " at %" PRIx64 "\n",
245
        refcount_table_index, cluster_index << s->cluster_bits, new_block);
246
#endif
247

    
248
    if (in_same_refcount_block(s, new_block, cluster_index << s->cluster_bits)) {
249
        /* Zero the new refcount block before updating it */
250
        memset(s->refcount_block_cache, 0, s->cluster_size);
251
        s->refcount_block_cache_offset = new_block;
252

    
253
        /* The block describes itself, need to update the cache */
254
        int block_index = (new_block >> s->cluster_bits) &
255
            ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
256
        s->refcount_block_cache[block_index] = cpu_to_be16(1);
257
    } else {
258
        /* Described somewhere else. This can recurse at most twice before we
259
         * arrive at a block that describes itself. */
260
        ret = update_refcount(bs, new_block, s->cluster_size, 1);
261
        if (ret < 0) {
262
            goto fail_block;
263
        }
264

    
265
        bdrv_flush(bs->file);
266

    
267
        /* Initialize the new refcount block only after updating its refcount,
268
         * update_refcount uses the refcount cache itself */
269
        memset(s->refcount_block_cache, 0, s->cluster_size);
270
        s->refcount_block_cache_offset = new_block;
271
    }
272

    
273
    /* Now the new refcount block needs to be written to disk */
274
    BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_WRITE);
275
    ret = bdrv_pwrite_sync(bs->file, new_block, s->refcount_block_cache,
276
        s->cluster_size);
277
    if (ret < 0) {
278
        goto fail_block;
279
    }
280

    
281
    /* If the refcount table is big enough, just hook the block up there */
282
    if (refcount_table_index < s->refcount_table_size) {
283
        uint64_t data64 = cpu_to_be64(new_block);
284
        BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_HOOKUP);
285
        ret = bdrv_pwrite_sync(bs->file,
286
            s->refcount_table_offset + refcount_table_index * sizeof(uint64_t),
287
            &data64, sizeof(data64));
288
        if (ret < 0) {
289
            goto fail_block;
290
        }
291

    
292
        s->refcount_table[refcount_table_index] = new_block;
293
        return new_block;
294
    }
295

    
296
    /*
297
     * If we come here, we need to grow the refcount table. Again, a new
298
     * refcount table needs some space and we can't simply allocate to avoid
299
     * endless recursion.
300
     *
301
     * Therefore let's grab new refcount blocks at the end of the image, which
302
     * will describe themselves and the new refcount table. This way we can
303
     * reference them only in the new table and do the switch to the new
304
     * refcount table at once without producing an inconsistent state in
305
     * between.
306
     */
307
    BLKDBG_EVENT(bs->file, BLKDBG_REFTABLE_GROW);
308

    
309
    /* Calculate the number of refcount blocks needed so far */
310
    uint64_t refcount_block_clusters = 1 << (s->cluster_bits - REFCOUNT_SHIFT);
311
    uint64_t blocks_used = (s->free_cluster_index +
312
        refcount_block_clusters - 1) / refcount_block_clusters;
313

    
314
    /* And now we need at least one block more for the new metadata */
315
    uint64_t table_size = next_refcount_table_size(s, blocks_used + 1);
316
    uint64_t last_table_size;
317
    uint64_t blocks_clusters;
318
    do {
319
        uint64_t table_clusters = size_to_clusters(s, table_size);
320
        blocks_clusters = 1 +
321
            ((table_clusters + refcount_block_clusters - 1)
322
            / refcount_block_clusters);
323
        uint64_t meta_clusters = table_clusters + blocks_clusters;
324

    
325
        last_table_size = table_size;
326
        table_size = next_refcount_table_size(s, blocks_used +
327
            ((meta_clusters + refcount_block_clusters - 1)
328
            / refcount_block_clusters));
329

    
330
    } while (last_table_size != table_size);
331

    
332
#ifdef DEBUG_ALLOC2
333
    fprintf(stderr, "qcow2: Grow refcount table %" PRId32 " => %" PRId64 "\n",
334
        s->refcount_table_size, table_size);
335
#endif
336

    
337
    /* Create the new refcount table and blocks */
338
    uint64_t meta_offset = (blocks_used * refcount_block_clusters) *
339
        s->cluster_size;
340
    uint64_t table_offset = meta_offset + blocks_clusters * s->cluster_size;
341
    uint16_t *new_blocks = qemu_mallocz(blocks_clusters * s->cluster_size);
342
    uint64_t *new_table = qemu_mallocz(table_size * sizeof(uint64_t));
343

    
344
    assert(meta_offset >= (s->free_cluster_index * s->cluster_size));
345

    
346
    /* Fill the new refcount table */
347
    memcpy(new_table, s->refcount_table,
348
        s->refcount_table_size * sizeof(uint64_t));
349
    new_table[refcount_table_index] = new_block;
350

    
351
    int i;
352
    for (i = 0; i < blocks_clusters; i++) {
353
        new_table[blocks_used + i] = meta_offset + (i * s->cluster_size);
354
    }
355

    
356
    /* Fill the refcount blocks */
357
    uint64_t table_clusters = size_to_clusters(s, table_size * sizeof(uint64_t));
358
    int block = 0;
359
    for (i = 0; i < table_clusters + blocks_clusters; i++) {
360
        new_blocks[block++] = cpu_to_be16(1);
361
    }
362

    
363
    /* Write refcount blocks to disk */
364
    BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_WRITE_BLOCKS);
365
    ret = bdrv_pwrite_sync(bs->file, meta_offset, new_blocks,
366
        blocks_clusters * s->cluster_size);
367
    qemu_free(new_blocks);
368
    if (ret < 0) {
369
        goto fail_table;
370
    }
371

    
372
    /* Write refcount table to disk */
373
    for(i = 0; i < table_size; i++) {
374
        cpu_to_be64s(&new_table[i]);
375
    }
376

    
377
    BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_WRITE_TABLE);
378
    ret = bdrv_pwrite_sync(bs->file, table_offset, new_table,
379
        table_size * sizeof(uint64_t));
380
    if (ret < 0) {
381
        goto fail_table;
382
    }
383

    
384
    for(i = 0; i < table_size; i++) {
385
        cpu_to_be64s(&new_table[i]);
386
    }
387

    
388
    /* Hook up the new refcount table in the qcow2 header */
389
    uint8_t data[12];
390
    cpu_to_be64w((uint64_t*)data, table_offset);
391
    cpu_to_be32w((uint32_t*)(data + 8), table_clusters);
392
    BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC_SWITCH_TABLE);
393
    ret = bdrv_pwrite_sync(bs->file, offsetof(QCowHeader, refcount_table_offset),
394
        data, sizeof(data));
395
    if (ret < 0) {
396
        goto fail_table;
397
    }
398

    
399
    /* And switch it in memory */
400
    uint64_t old_table_offset = s->refcount_table_offset;
401
    uint64_t old_table_size = s->refcount_table_size;
402

    
403
    qemu_free(s->refcount_table);
404
    s->refcount_table = new_table;
405
    s->refcount_table_size = table_size;
406
    s->refcount_table_offset = table_offset;
407

    
408
    /* Free old table. Remember, we must not change free_cluster_index */
409
    uint64_t old_free_cluster_index = s->free_cluster_index;
410
    qcow2_free_clusters(bs, old_table_offset, old_table_size * sizeof(uint64_t));
411
    s->free_cluster_index = old_free_cluster_index;
412

    
413
    ret = load_refcount_block(bs, new_block);
414
    if (ret < 0) {
415
        goto fail_block;
416
    }
417

    
418
    return new_block;
419

    
420
fail_table:
421
    qemu_free(new_table);
422
fail_block:
423
    s->refcount_block_cache_offset = 0;
424
    return ret;
425
}
426

    
427
#define REFCOUNTS_PER_SECTOR (512 >> REFCOUNT_SHIFT)
428
static int write_refcount_block_entries(BlockDriverState *bs,
429
    int64_t refcount_block_offset, int first_index, int last_index)
430
{
431
    BDRVQcowState *s = bs->opaque;
432
    size_t size;
433
    int ret;
434

    
435
    if (cache_refcount_updates) {
436
        return 0;
437
    }
438

    
439
    if (first_index < 0) {
440
        return 0;
441
    }
442

    
443
    first_index &= ~(REFCOUNTS_PER_SECTOR - 1);
444
    last_index = (last_index + REFCOUNTS_PER_SECTOR)
445
        & ~(REFCOUNTS_PER_SECTOR - 1);
446

    
447
    size = (last_index - first_index) << REFCOUNT_SHIFT;
448

    
449
    BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_UPDATE_PART);
450
    ret = bdrv_pwrite(bs->file,
451
        refcount_block_offset + (first_index << REFCOUNT_SHIFT),
452
        &s->refcount_block_cache[first_index], size);
453
    if (ret < 0) {
454
        return ret;
455
    }
456

    
457
    return 0;
458
}
459

    
460
/* XXX: cache several refcount block clusters ? */
461
static int QEMU_WARN_UNUSED_RESULT update_refcount(BlockDriverState *bs,
462
    int64_t offset, int64_t length, int addend)
463
{
464
    BDRVQcowState *s = bs->opaque;
465
    int64_t start, last, cluster_offset;
466
    int64_t refcount_block_offset = 0;
467
    int64_t table_index = -1, old_table_index;
468
    int first_index = -1, last_index = -1;
469
    int ret;
470

    
471
#ifdef DEBUG_ALLOC2
472
    printf("update_refcount: offset=%" PRId64 " size=%" PRId64 " addend=%d\n",
473
           offset, length, addend);
474
#endif
475
    if (length < 0) {
476
        return -EINVAL;
477
    } else if (length == 0) {
478
        return 0;
479
    }
480

    
481
    start = offset & ~(s->cluster_size - 1);
482
    last = (offset + length - 1) & ~(s->cluster_size - 1);
483
    for(cluster_offset = start; cluster_offset <= last;
484
        cluster_offset += s->cluster_size)
485
    {
486
        int block_index, refcount;
487
        int64_t cluster_index = cluster_offset >> s->cluster_bits;
488
        int64_t new_block;
489

    
490
        /* Only write refcount block to disk when we are done with it */
491
        old_table_index = table_index;
492
        table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
493
        if ((old_table_index >= 0) && (table_index != old_table_index)) {
494

    
495
            ret = write_refcount_block_entries(bs, refcount_block_offset,
496
                first_index, last_index);
497
            if (ret < 0) {
498
                return ret;
499
            }
500

    
501
            first_index = -1;
502
            last_index = -1;
503
        }
504

    
505
        /* Load the refcount block and allocate it if needed */
506
        new_block = alloc_refcount_block(bs, cluster_index);
507
        if (new_block < 0) {
508
            ret = new_block;
509
            goto fail;
510
        }
511
        refcount_block_offset = new_block;
512

    
513
        /* we can update the count and save it */
514
        block_index = cluster_index &
515
            ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
516
        if (first_index == -1 || block_index < first_index) {
517
            first_index = block_index;
518
        }
519
        if (block_index > last_index) {
520
            last_index = block_index;
521
        }
522

    
523
        refcount = be16_to_cpu(s->refcount_block_cache[block_index]);
524
        refcount += addend;
525
        if (refcount < 0 || refcount > 0xffff) {
526
            ret = -EINVAL;
527
            goto fail;
528
        }
529
        if (refcount == 0 && cluster_index < s->free_cluster_index) {
530
            s->free_cluster_index = cluster_index;
531
        }
532
        s->refcount_block_cache[block_index] = cpu_to_be16(refcount);
533
    }
534

    
535
    ret = 0;
536
fail:
537

    
538
    /* Write last changed block to disk */
539
    if (refcount_block_offset != 0) {
540
        int wret;
541
        wret = write_refcount_block_entries(bs, refcount_block_offset,
542
            first_index, last_index);
543
        if (wret < 0) {
544
            return ret < 0 ? ret : wret;
545
        }
546
    }
547

    
548
    /*
549
     * Try do undo any updates if an error is returned (This may succeed in
550
     * some cases like ENOSPC for allocating a new refcount block)
551
     */
552
    if (ret < 0) {
553
        int dummy;
554
        dummy = update_refcount(bs, offset, cluster_offset - offset, -addend);
555
        (void)dummy;
556
    }
557

    
558
    return ret;
559
}
560

    
561
/*
562
 * Increases or decreases the refcount of a given cluster by one.
563
 * addend must be 1 or -1.
564
 *
565
 * If the return value is non-negative, it is the new refcount of the cluster.
566
 * If it is negative, it is -errno and indicates an error.
567
 */
568
static int update_cluster_refcount(BlockDriverState *bs,
569
                                   int64_t cluster_index,
570
                                   int addend)
571
{
572
    BDRVQcowState *s = bs->opaque;
573
    int ret;
574

    
575
    ret = update_refcount(bs, cluster_index << s->cluster_bits, 1, addend);
576
    if (ret < 0) {
577
        return ret;
578
    }
579

    
580
    bdrv_flush(bs->file);
581

    
582
    return get_refcount(bs, cluster_index);
583
}
584

    
585

    
586

    
587
/*********************************************************/
588
/* cluster allocation functions */
589

    
590

    
591

    
592
/* return < 0 if error */
593
static int64_t alloc_clusters_noref(BlockDriverState *bs, int64_t size)
594
{
595
    BDRVQcowState *s = bs->opaque;
596
    int i, nb_clusters, refcount;
597

    
598
    nb_clusters = size_to_clusters(s, size);
599
retry:
600
    for(i = 0; i < nb_clusters; i++) {
601
        int64_t next_cluster_index = s->free_cluster_index++;
602
        refcount = get_refcount(bs, next_cluster_index);
603

    
604
        if (refcount < 0) {
605
            return refcount;
606
        } else if (refcount != 0) {
607
            goto retry;
608
        }
609
    }
610
#ifdef DEBUG_ALLOC2
611
    printf("alloc_clusters: size=%" PRId64 " -> %" PRId64 "\n",
612
            size,
613
            (s->free_cluster_index - nb_clusters) << s->cluster_bits);
614
#endif
615
    return (s->free_cluster_index - nb_clusters) << s->cluster_bits;
616
}
617

    
618
int64_t qcow2_alloc_clusters(BlockDriverState *bs, int64_t size)
619
{
620
    int64_t offset;
621
    int ret;
622

    
623
    BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_ALLOC);
624
    offset = alloc_clusters_noref(bs, size);
625
    if (offset < 0) {
626
        return offset;
627
    }
628

    
629
    ret = update_refcount(bs, offset, size, 1);
630
    if (ret < 0) {
631
        return ret;
632
    }
633

    
634
    return offset;
635
}
636

    
637
/* only used to allocate compressed sectors. We try to allocate
638
   contiguous sectors. size must be <= cluster_size */
639
int64_t qcow2_alloc_bytes(BlockDriverState *bs, int size)
640
{
641
    BDRVQcowState *s = bs->opaque;
642
    int64_t offset, cluster_offset;
643
    int free_in_cluster;
644

    
645
    BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_ALLOC_BYTES);
646
    assert(size > 0 && size <= s->cluster_size);
647
    if (s->free_byte_offset == 0) {
648
        s->free_byte_offset = qcow2_alloc_clusters(bs, s->cluster_size);
649
        if (s->free_byte_offset < 0) {
650
            return s->free_byte_offset;
651
        }
652
    }
653
 redo:
654
    free_in_cluster = s->cluster_size -
655
        (s->free_byte_offset & (s->cluster_size - 1));
656
    if (size <= free_in_cluster) {
657
        /* enough space in current cluster */
658
        offset = s->free_byte_offset;
659
        s->free_byte_offset += size;
660
        free_in_cluster -= size;
661
        if (free_in_cluster == 0)
662
            s->free_byte_offset = 0;
663
        if ((offset & (s->cluster_size - 1)) != 0)
664
            update_cluster_refcount(bs, offset >> s->cluster_bits, 1);
665
    } else {
666
        offset = qcow2_alloc_clusters(bs, s->cluster_size);
667
        if (offset < 0) {
668
            return offset;
669
        }
670
        cluster_offset = s->free_byte_offset & ~(s->cluster_size - 1);
671
        if ((cluster_offset + s->cluster_size) == offset) {
672
            /* we are lucky: contiguous data */
673
            offset = s->free_byte_offset;
674
            update_cluster_refcount(bs, offset >> s->cluster_bits, 1);
675
            s->free_byte_offset += size;
676
        } else {
677
            s->free_byte_offset = offset;
678
            goto redo;
679
        }
680
    }
681

    
682
    bdrv_flush(bs->file);
683
    return offset;
684
}
685

    
686
void qcow2_free_clusters(BlockDriverState *bs,
687
                          int64_t offset, int64_t size)
688
{
689
    int ret;
690

    
691
    BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_FREE);
692
    ret = update_refcount(bs, offset, size, -1);
693
    if (ret < 0) {
694
        fprintf(stderr, "qcow2_free_clusters failed: %s\n", strerror(-ret));
695
        /* TODO Remember the clusters to free them later and avoid leaking */
696
    }
697
}
698

    
699
/*
700
 * free_any_clusters
701
 *
702
 * free clusters according to its type: compressed or not
703
 *
704
 */
705

    
706
void qcow2_free_any_clusters(BlockDriverState *bs,
707
    uint64_t cluster_offset, int nb_clusters)
708
{
709
    BDRVQcowState *s = bs->opaque;
710

    
711
    /* free the cluster */
712

    
713
    if (cluster_offset & QCOW_OFLAG_COMPRESSED) {
714
        int nb_csectors;
715
        nb_csectors = ((cluster_offset >> s->csize_shift) &
716
                       s->csize_mask) + 1;
717
        qcow2_free_clusters(bs,
718
            (cluster_offset & s->cluster_offset_mask) & ~511,
719
            nb_csectors * 512);
720
        return;
721
    }
722

    
723
    qcow2_free_clusters(bs, cluster_offset, nb_clusters << s->cluster_bits);
724

    
725
    return;
726
}
727

    
728

    
729

    
730
/*********************************************************/
731
/* snapshots and image creation */
732

    
733

    
734

    
735
void qcow2_create_refcount_update(QCowCreateState *s, int64_t offset,
736
    int64_t size)
737
{
738
    int refcount;
739
    int64_t start, last, cluster_offset;
740
    uint16_t *p;
741

    
742
    start = offset & ~(s->cluster_size - 1);
743
    last = (offset + size - 1)  & ~(s->cluster_size - 1);
744
    for(cluster_offset = start; cluster_offset <= last;
745
        cluster_offset += s->cluster_size) {
746
        p = &s->refcount_block[cluster_offset >> s->cluster_bits];
747
        refcount = be16_to_cpu(*p);
748
        refcount++;
749
        *p = cpu_to_be16(refcount);
750
    }
751
}
752

    
753
/* update the refcounts of snapshots and the copied flag */
754
int qcow2_update_snapshot_refcount(BlockDriverState *bs,
755
    int64_t l1_table_offset, int l1_size, int addend)
756
{
757
    BDRVQcowState *s = bs->opaque;
758
    uint64_t *l1_table, *l2_table, l2_offset, offset, l1_size2, l1_allocated;
759
    int64_t old_offset, old_l2_offset;
760
    int l2_size, i, j, l1_modified, l2_modified, nb_csectors, refcount;
761

    
762
    qcow2_l2_cache_reset(bs);
763
    cache_refcount_updates = 1;
764

    
765
    l2_table = NULL;
766
    l1_table = NULL;
767
    l1_size2 = l1_size * sizeof(uint64_t);
768
    if (l1_table_offset != s->l1_table_offset) {
769
        if (l1_size2 != 0) {
770
            l1_table = qemu_mallocz(align_offset(l1_size2, 512));
771
        } else {
772
            l1_table = NULL;
773
        }
774
        l1_allocated = 1;
775
        if (bdrv_pread(bs->file, l1_table_offset,
776
                       l1_table, l1_size2) != l1_size2)
777
            goto fail;
778
        for(i = 0;i < l1_size; i++)
779
            be64_to_cpus(&l1_table[i]);
780
    } else {
781
        assert(l1_size == s->l1_size);
782
        l1_table = s->l1_table;
783
        l1_allocated = 0;
784
    }
785

    
786
    l2_size = s->l2_size * sizeof(uint64_t);
787
    l2_table = qemu_malloc(l2_size);
788
    l1_modified = 0;
789
    for(i = 0; i < l1_size; i++) {
790
        l2_offset = l1_table[i];
791
        if (l2_offset) {
792
            old_l2_offset = l2_offset;
793
            l2_offset &= ~QCOW_OFLAG_COPIED;
794
            l2_modified = 0;
795
            if (bdrv_pread(bs->file, l2_offset, l2_table, l2_size) != l2_size)
796
                goto fail;
797
            for(j = 0; j < s->l2_size; j++) {
798
                offset = be64_to_cpu(l2_table[j]);
799
                if (offset != 0) {
800
                    old_offset = offset;
801
                    offset &= ~QCOW_OFLAG_COPIED;
802
                    if (offset & QCOW_OFLAG_COMPRESSED) {
803
                        nb_csectors = ((offset >> s->csize_shift) &
804
                                       s->csize_mask) + 1;
805
                        if (addend != 0) {
806
                            int ret;
807
                            ret = update_refcount(bs,
808
                                (offset & s->cluster_offset_mask) & ~511,
809
                                nb_csectors * 512, addend);
810
                            if (ret < 0) {
811
                                goto fail;
812
                            }
813

    
814
                            /* TODO Flushing once for the whole function should
815
                             * be enough */
816
                            bdrv_flush(bs->file);
817
                        }
818
                        /* compressed clusters are never modified */
819
                        refcount = 2;
820
                    } else {
821
                        if (addend != 0) {
822
                            refcount = update_cluster_refcount(bs, offset >> s->cluster_bits, addend);
823
                        } else {
824
                            refcount = get_refcount(bs, offset >> s->cluster_bits);
825
                        }
826

    
827
                        if (refcount < 0) {
828
                            goto fail;
829
                        }
830
                    }
831

    
832
                    if (refcount == 1) {
833
                        offset |= QCOW_OFLAG_COPIED;
834
                    }
835
                    if (offset != old_offset) {
836
                        l2_table[j] = cpu_to_be64(offset);
837
                        l2_modified = 1;
838
                    }
839
                }
840
            }
841
            if (l2_modified) {
842
                if (bdrv_pwrite_sync(bs->file,
843
                                l2_offset, l2_table, l2_size) < 0)
844
                    goto fail;
845
            }
846

    
847
            if (addend != 0) {
848
                refcount = update_cluster_refcount(bs, l2_offset >> s->cluster_bits, addend);
849
            } else {
850
                refcount = get_refcount(bs, l2_offset >> s->cluster_bits);
851
            }
852
            if (refcount < 0) {
853
                goto fail;
854
            } else if (refcount == 1) {
855
                l2_offset |= QCOW_OFLAG_COPIED;
856
            }
857
            if (l2_offset != old_l2_offset) {
858
                l1_table[i] = l2_offset;
859
                l1_modified = 1;
860
            }
861
        }
862
    }
863
    if (l1_modified) {
864
        for(i = 0; i < l1_size; i++)
865
            cpu_to_be64s(&l1_table[i]);
866
        if (bdrv_pwrite_sync(bs->file, l1_table_offset, l1_table,
867
                        l1_size2) < 0)
868
            goto fail;
869
        for(i = 0; i < l1_size; i++)
870
            be64_to_cpus(&l1_table[i]);
871
    }
872
    if (l1_allocated)
873
        qemu_free(l1_table);
874
    qemu_free(l2_table);
875
    cache_refcount_updates = 0;
876
    write_refcount_block(bs);
877
    return 0;
878
 fail:
879
    if (l1_allocated)
880
        qemu_free(l1_table);
881
    qemu_free(l2_table);
882
    cache_refcount_updates = 0;
883
    write_refcount_block(bs);
884
    return -EIO;
885
}
886

    
887

    
888

    
889

    
890
/*********************************************************/
891
/* refcount checking functions */
892

    
893

    
894

    
895
/*
896
 * Increases the refcount for a range of clusters in a given refcount table.
897
 * This is used to construct a temporary refcount table out of L1 and L2 tables
898
 * which can be compared the the refcount table saved in the image.
899
 *
900
 * Modifies the number of errors in res.
901
 */
902
static void inc_refcounts(BlockDriverState *bs,
903
                          BdrvCheckResult *res,
904
                          uint16_t *refcount_table,
905
                          int refcount_table_size,
906
                          int64_t offset, int64_t size)
907
{
908
    BDRVQcowState *s = bs->opaque;
909
    int64_t start, last, cluster_offset;
910
    int k;
911

    
912
    if (size <= 0)
913
        return;
914

    
915
    start = offset & ~(s->cluster_size - 1);
916
    last = (offset + size - 1) & ~(s->cluster_size - 1);
917
    for(cluster_offset = start; cluster_offset <= last;
918
        cluster_offset += s->cluster_size) {
919
        k = cluster_offset >> s->cluster_bits;
920
        if (k < 0) {
921
            fprintf(stderr, "ERROR: invalid cluster offset=0x%" PRIx64 "\n",
922
                cluster_offset);
923
            res->corruptions++;
924
        } else if (k >= refcount_table_size) {
925
            fprintf(stderr, "Warning: cluster offset=0x%" PRIx64 " is after "
926
                "the end of the image file, can't properly check refcounts.\n",
927
                cluster_offset);
928
            res->check_errors++;
929
        } else {
930
            if (++refcount_table[k] == 0) {
931
                fprintf(stderr, "ERROR: overflow cluster offset=0x%" PRIx64
932
                    "\n", cluster_offset);
933
                res->corruptions++;
934
            }
935
        }
936
    }
937
}
938

    
939
/*
940
 * Increases the refcount in the given refcount table for the all clusters
941
 * referenced in the L2 table. While doing so, performs some checks on L2
942
 * entries.
943
 *
944
 * Returns the number of errors found by the checks or -errno if an internal
945
 * error occurred.
946
 */
947
static int check_refcounts_l2(BlockDriverState *bs, BdrvCheckResult *res,
948
    uint16_t *refcount_table, int refcount_table_size, int64_t l2_offset,
949
    int check_copied)
950
{
951
    BDRVQcowState *s = bs->opaque;
952
    uint64_t *l2_table, offset;
953
    int i, l2_size, nb_csectors, refcount;
954

    
955
    /* Read L2 table from disk */
956
    l2_size = s->l2_size * sizeof(uint64_t);
957
    l2_table = qemu_malloc(l2_size);
958

    
959
    if (bdrv_pread(bs->file, l2_offset, l2_table, l2_size) != l2_size)
960
        goto fail;
961

    
962
    /* Do the actual checks */
963
    for(i = 0; i < s->l2_size; i++) {
964
        offset = be64_to_cpu(l2_table[i]);
965
        if (offset != 0) {
966
            if (offset & QCOW_OFLAG_COMPRESSED) {
967
                /* Compressed clusters don't have QCOW_OFLAG_COPIED */
968
                if (offset & QCOW_OFLAG_COPIED) {
969
                    fprintf(stderr, "ERROR: cluster %" PRId64 ": "
970
                        "copied flag must never be set for compressed "
971
                        "clusters\n", offset >> s->cluster_bits);
972
                    offset &= ~QCOW_OFLAG_COPIED;
973
                    res->corruptions++;
974
                }
975

    
976
                /* Mark cluster as used */
977
                nb_csectors = ((offset >> s->csize_shift) &
978
                               s->csize_mask) + 1;
979
                offset &= s->cluster_offset_mask;
980
                inc_refcounts(bs, res, refcount_table, refcount_table_size,
981
                    offset & ~511, nb_csectors * 512);
982
            } else {
983
                /* QCOW_OFLAG_COPIED must be set iff refcount == 1 */
984
                if (check_copied) {
985
                    uint64_t entry = offset;
986
                    offset &= ~QCOW_OFLAG_COPIED;
987
                    refcount = get_refcount(bs, offset >> s->cluster_bits);
988
                    if (refcount < 0) {
989
                        fprintf(stderr, "Can't get refcount for offset %"
990
                            PRIx64 ": %s\n", entry, strerror(-refcount));
991
                        goto fail;
992
                    }
993
                    if ((refcount == 1) != ((entry & QCOW_OFLAG_COPIED) != 0)) {
994
                        fprintf(stderr, "ERROR OFLAG_COPIED: offset=%"
995
                            PRIx64 " refcount=%d\n", entry, refcount);
996
                        res->corruptions++;
997
                    }
998
                }
999

    
1000
                /* Mark cluster as used */
1001
                offset &= ~QCOW_OFLAG_COPIED;
1002
                inc_refcounts(bs, res, refcount_table,refcount_table_size,
1003
                    offset, s->cluster_size);
1004

    
1005
                /* Correct offsets are cluster aligned */
1006
                if (offset & (s->cluster_size - 1)) {
1007
                    fprintf(stderr, "ERROR offset=%" PRIx64 ": Cluster is not "
1008
                        "properly aligned; L2 entry corrupted.\n", offset);
1009
                    res->corruptions++;
1010
                }
1011
            }
1012
        }
1013
    }
1014

    
1015
    qemu_free(l2_table);
1016
    return 0;
1017

    
1018
fail:
1019
    fprintf(stderr, "ERROR: I/O error in check_refcounts_l2\n");
1020
    qemu_free(l2_table);
1021
    return -EIO;
1022
}
1023

    
1024
/*
1025
 * Increases the refcount for the L1 table, its L2 tables and all referenced
1026
 * clusters in the given refcount table. While doing so, performs some checks
1027
 * on L1 and L2 entries.
1028
 *
1029
 * Returns the number of errors found by the checks or -errno if an internal
1030
 * error occurred.
1031
 */
1032
static int check_refcounts_l1(BlockDriverState *bs,
1033
                              BdrvCheckResult *res,
1034
                              uint16_t *refcount_table,
1035
                              int refcount_table_size,
1036
                              int64_t l1_table_offset, int l1_size,
1037
                              int check_copied)
1038
{
1039
    BDRVQcowState *s = bs->opaque;
1040
    uint64_t *l1_table, l2_offset, l1_size2;
1041
    int i, refcount, ret;
1042

    
1043
    l1_size2 = l1_size * sizeof(uint64_t);
1044

    
1045
    /* Mark L1 table as used */
1046
    inc_refcounts(bs, res, refcount_table, refcount_table_size,
1047
        l1_table_offset, l1_size2);
1048

    
1049
    /* Read L1 table entries from disk */
1050
    if (l1_size2 == 0) {
1051
        l1_table = NULL;
1052
    } else {
1053
        l1_table = qemu_malloc(l1_size2);
1054
        if (bdrv_pread(bs->file, l1_table_offset,
1055
                       l1_table, l1_size2) != l1_size2)
1056
            goto fail;
1057
        for(i = 0;i < l1_size; i++)
1058
            be64_to_cpus(&l1_table[i]);
1059
    }
1060

    
1061
    /* Do the actual checks */
1062
    for(i = 0; i < l1_size; i++) {
1063
        l2_offset = l1_table[i];
1064
        if (l2_offset) {
1065
            /* QCOW_OFLAG_COPIED must be set iff refcount == 1 */
1066
            if (check_copied) {
1067
                refcount = get_refcount(bs, (l2_offset & ~QCOW_OFLAG_COPIED)
1068
                    >> s->cluster_bits);
1069
                if (refcount < 0) {
1070
                    fprintf(stderr, "Can't get refcount for l2_offset %"
1071
                        PRIx64 ": %s\n", l2_offset, strerror(-refcount));
1072
                    goto fail;
1073
                }
1074
                if ((refcount == 1) != ((l2_offset & QCOW_OFLAG_COPIED) != 0)) {
1075
                    fprintf(stderr, "ERROR OFLAG_COPIED: l2_offset=%" PRIx64
1076
                        " refcount=%d\n", l2_offset, refcount);
1077
                    res->corruptions++;
1078
                }
1079
            }
1080

    
1081
            /* Mark L2 table as used */
1082
            l2_offset &= ~QCOW_OFLAG_COPIED;
1083
            inc_refcounts(bs, res, refcount_table, refcount_table_size,
1084
                l2_offset, s->cluster_size);
1085

    
1086
            /* L2 tables are cluster aligned */
1087
            if (l2_offset & (s->cluster_size - 1)) {
1088
                fprintf(stderr, "ERROR l2_offset=%" PRIx64 ": Table is not "
1089
                    "cluster aligned; L1 entry corrupted\n", l2_offset);
1090
                res->corruptions++;
1091
            }
1092

    
1093
            /* Process and check L2 entries */
1094
            ret = check_refcounts_l2(bs, res, refcount_table,
1095
                refcount_table_size, l2_offset, check_copied);
1096
            if (ret < 0) {
1097
                goto fail;
1098
            }
1099
        }
1100
    }
1101
    qemu_free(l1_table);
1102
    return 0;
1103

    
1104
fail:
1105
    fprintf(stderr, "ERROR: I/O error in check_refcounts_l1\n");
1106
    res->check_errors++;
1107
    qemu_free(l1_table);
1108
    return -EIO;
1109
}
1110

    
1111
/*
1112
 * Checks an image for refcount consistency.
1113
 *
1114
 * Returns 0 if no errors are found, the number of errors in case the image is
1115
 * detected as corrupted, and -errno when an internal error occured.
1116
 */
1117
int qcow2_check_refcounts(BlockDriverState *bs, BdrvCheckResult *res)
1118
{
1119
    BDRVQcowState *s = bs->opaque;
1120
    int64_t size;
1121
    int nb_clusters, refcount1, refcount2, i;
1122
    QCowSnapshot *sn;
1123
    uint16_t *refcount_table;
1124
    int ret;
1125

    
1126
    size = bdrv_getlength(bs->file);
1127
    nb_clusters = size_to_clusters(s, size);
1128
    refcount_table = qemu_mallocz(nb_clusters * sizeof(uint16_t));
1129

    
1130
    /* header */
1131
    inc_refcounts(bs, res, refcount_table, nb_clusters,
1132
        0, s->cluster_size);
1133

    
1134
    /* current L1 table */
1135
    ret = check_refcounts_l1(bs, res, refcount_table, nb_clusters,
1136
                       s->l1_table_offset, s->l1_size, 1);
1137
    if (ret < 0) {
1138
        return ret;
1139
    }
1140

    
1141
    /* snapshots */
1142
    for(i = 0; i < s->nb_snapshots; i++) {
1143
        sn = s->snapshots + i;
1144
        ret = check_refcounts_l1(bs, res, refcount_table, nb_clusters,
1145
            sn->l1_table_offset, sn->l1_size, 0);
1146
        if (ret < 0) {
1147
            return ret;
1148
        }
1149
    }
1150
    inc_refcounts(bs, res, refcount_table, nb_clusters,
1151
        s->snapshots_offset, s->snapshots_size);
1152

    
1153
    /* refcount data */
1154
    inc_refcounts(bs, res, refcount_table, nb_clusters,
1155
        s->refcount_table_offset,
1156
        s->refcount_table_size * sizeof(uint64_t));
1157

    
1158
    for(i = 0; i < s->refcount_table_size; i++) {
1159
        uint64_t offset, cluster;
1160
        offset = s->refcount_table[i];
1161
        cluster = offset >> s->cluster_bits;
1162

    
1163
        /* Refcount blocks are cluster aligned */
1164
        if (offset & (s->cluster_size - 1)) {
1165
            fprintf(stderr, "ERROR refcount block %d is not "
1166
                "cluster aligned; refcount table entry corrupted\n", i);
1167
            res->corruptions++;
1168
            continue;
1169
        }
1170

    
1171
        if (cluster >= nb_clusters) {
1172
            fprintf(stderr, "ERROR refcount block %d is outside image\n", i);
1173
            res->corruptions++;
1174
            continue;
1175
        }
1176

    
1177
        if (offset != 0) {
1178
            inc_refcounts(bs, res, refcount_table, nb_clusters,
1179
                offset, s->cluster_size);
1180
            if (refcount_table[cluster] != 1) {
1181
                fprintf(stderr, "ERROR refcount block %d refcount=%d\n",
1182
                    i, refcount_table[cluster]);
1183
                res->corruptions++;
1184
            }
1185
        }
1186
    }
1187

    
1188
    /* compare ref counts */
1189
    for(i = 0; i < nb_clusters; i++) {
1190
        refcount1 = get_refcount(bs, i);
1191
        if (refcount1 < 0) {
1192
            fprintf(stderr, "Can't get refcount for cluster %d: %s\n",
1193
                i, strerror(-refcount1));
1194
            res->check_errors++;
1195
            continue;
1196
        }
1197

    
1198
        refcount2 = refcount_table[i];
1199
        if (refcount1 != refcount2) {
1200
            fprintf(stderr, "%s cluster %d refcount=%d reference=%d\n",
1201
                   refcount1 < refcount2 ? "ERROR" : "Leaked",
1202
                   i, refcount1, refcount2);
1203
            if (refcount1 < refcount2) {
1204
                res->corruptions++;
1205
            } else {
1206
                res->leaks++;
1207
            }
1208
        }
1209
    }
1210

    
1211
    qemu_free(refcount_table);
1212

    
1213
    return 0;
1214
}
1215