Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (28.8 kB)

1 f7d0fe02 Kevin Wolf
/*
2 f7d0fe02 Kevin Wolf
 * Block driver for the QCOW version 2 format
3 f7d0fe02 Kevin Wolf
 *
4 f7d0fe02 Kevin Wolf
 * Copyright (c) 2004-2006 Fabrice Bellard
5 f7d0fe02 Kevin Wolf
 *
6 f7d0fe02 Kevin Wolf
 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 f7d0fe02 Kevin Wolf
 * of this software and associated documentation files (the "Software"), to deal
8 f7d0fe02 Kevin Wolf
 * in the Software without restriction, including without limitation the rights
9 f7d0fe02 Kevin Wolf
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 f7d0fe02 Kevin Wolf
 * copies of the Software, and to permit persons to whom the Software is
11 f7d0fe02 Kevin Wolf
 * furnished to do so, subject to the following conditions:
12 f7d0fe02 Kevin Wolf
 *
13 f7d0fe02 Kevin Wolf
 * The above copyright notice and this permission notice shall be included in
14 f7d0fe02 Kevin Wolf
 * all copies or substantial portions of the Software.
15 f7d0fe02 Kevin Wolf
 *
16 f7d0fe02 Kevin Wolf
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 f7d0fe02 Kevin Wolf
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 f7d0fe02 Kevin Wolf
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 f7d0fe02 Kevin Wolf
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 f7d0fe02 Kevin Wolf
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 f7d0fe02 Kevin Wolf
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22 f7d0fe02 Kevin Wolf
 * THE SOFTWARE.
23 f7d0fe02 Kevin Wolf
 */
24 f7d0fe02 Kevin Wolf
25 f7d0fe02 Kevin Wolf
#include "qemu-common.h"
26 f7d0fe02 Kevin Wolf
#include "block_int.h"
27 f7d0fe02 Kevin Wolf
#include "block/qcow2.h"
28 f7d0fe02 Kevin Wolf
29 f7d0fe02 Kevin Wolf
static int64_t alloc_clusters_noref(BlockDriverState *bs, int64_t size);
30 f7d0fe02 Kevin Wolf
static int update_refcount(BlockDriverState *bs,
31 f7d0fe02 Kevin Wolf
                            int64_t offset, int64_t length,
32 f7d0fe02 Kevin Wolf
                            int addend);
33 f7d0fe02 Kevin Wolf
34 3b88e52b Kevin Wolf
35 3b88e52b Kevin Wolf
static int cache_refcount_updates = 0;
36 3b88e52b Kevin Wolf
37 3b88e52b Kevin Wolf
static int write_refcount_block(BDRVQcowState *s)
38 3b88e52b Kevin Wolf
{
39 3b88e52b Kevin Wolf
    size_t size = s->cluster_size;
40 3b88e52b Kevin Wolf
41 3b88e52b Kevin Wolf
    if (s->refcount_block_cache_offset == 0) {
42 3b88e52b Kevin Wolf
        return 0;
43 3b88e52b Kevin Wolf
    }
44 3b88e52b Kevin Wolf
45 3b88e52b Kevin Wolf
    if (bdrv_pwrite(s->hd, s->refcount_block_cache_offset,
46 3b88e52b Kevin Wolf
            s->refcount_block_cache, size) != size)
47 3b88e52b Kevin Wolf
    {
48 3b88e52b Kevin Wolf
        return -EIO;
49 3b88e52b Kevin Wolf
    }
50 3b88e52b Kevin Wolf
51 3b88e52b Kevin Wolf
    return 0;
52 3b88e52b Kevin Wolf
}
53 3b88e52b Kevin Wolf
54 f7d0fe02 Kevin Wolf
/*********************************************************/
55 f7d0fe02 Kevin Wolf
/* refcount handling */
56 f7d0fe02 Kevin Wolf
57 ed6ccf0f Kevin Wolf
int qcow2_refcount_init(BlockDriverState *bs)
58 f7d0fe02 Kevin Wolf
{
59 f7d0fe02 Kevin Wolf
    BDRVQcowState *s = bs->opaque;
60 f7d0fe02 Kevin Wolf
    int ret, refcount_table_size2, i;
61 f7d0fe02 Kevin Wolf
62 f7d0fe02 Kevin Wolf
    s->refcount_block_cache = qemu_malloc(s->cluster_size);
63 f7d0fe02 Kevin Wolf
    refcount_table_size2 = s->refcount_table_size * sizeof(uint64_t);
64 f7d0fe02 Kevin Wolf
    s->refcount_table = qemu_malloc(refcount_table_size2);
65 f7d0fe02 Kevin Wolf
    if (s->refcount_table_size > 0) {
66 f7d0fe02 Kevin Wolf
        ret = bdrv_pread(s->hd, s->refcount_table_offset,
67 f7d0fe02 Kevin Wolf
                         s->refcount_table, refcount_table_size2);
68 f7d0fe02 Kevin Wolf
        if (ret != refcount_table_size2)
69 f7d0fe02 Kevin Wolf
            goto fail;
70 f7d0fe02 Kevin Wolf
        for(i = 0; i < s->refcount_table_size; i++)
71 f7d0fe02 Kevin Wolf
            be64_to_cpus(&s->refcount_table[i]);
72 f7d0fe02 Kevin Wolf
    }
73 f7d0fe02 Kevin Wolf
    return 0;
74 f7d0fe02 Kevin Wolf
 fail:
75 f7d0fe02 Kevin Wolf
    return -ENOMEM;
76 f7d0fe02 Kevin Wolf
}
77 f7d0fe02 Kevin Wolf
78 ed6ccf0f Kevin Wolf
void qcow2_refcount_close(BlockDriverState *bs)
79 f7d0fe02 Kevin Wolf
{
80 f7d0fe02 Kevin Wolf
    BDRVQcowState *s = bs->opaque;
81 f7d0fe02 Kevin Wolf
    qemu_free(s->refcount_block_cache);
82 f7d0fe02 Kevin Wolf
    qemu_free(s->refcount_table);
83 f7d0fe02 Kevin Wolf
}
84 f7d0fe02 Kevin Wolf
85 f7d0fe02 Kevin Wolf
86 f7d0fe02 Kevin Wolf
static int load_refcount_block(BlockDriverState *bs,
87 f7d0fe02 Kevin Wolf
                               int64_t refcount_block_offset)
88 f7d0fe02 Kevin Wolf
{
89 f7d0fe02 Kevin Wolf
    BDRVQcowState *s = bs->opaque;
90 f7d0fe02 Kevin Wolf
    int ret;
91 3b88e52b Kevin Wolf
92 3b88e52b Kevin Wolf
    if (cache_refcount_updates) {
93 3b88e52b Kevin Wolf
        write_refcount_block(s);
94 3b88e52b Kevin Wolf
    }
95 3b88e52b Kevin Wolf
96 f7d0fe02 Kevin Wolf
    ret = bdrv_pread(s->hd, refcount_block_offset, s->refcount_block_cache,
97 f7d0fe02 Kevin Wolf
                     s->cluster_size);
98 f7d0fe02 Kevin Wolf
    if (ret != s->cluster_size)
99 f7d0fe02 Kevin Wolf
        return -EIO;
100 f7d0fe02 Kevin Wolf
    s->refcount_block_cache_offset = refcount_block_offset;
101 f7d0fe02 Kevin Wolf
    return 0;
102 f7d0fe02 Kevin Wolf
}
103 f7d0fe02 Kevin Wolf
104 f7d0fe02 Kevin Wolf
static int get_refcount(BlockDriverState *bs, int64_t cluster_index)
105 f7d0fe02 Kevin Wolf
{
106 f7d0fe02 Kevin Wolf
    BDRVQcowState *s = bs->opaque;
107 f7d0fe02 Kevin Wolf
    int refcount_table_index, block_index;
108 f7d0fe02 Kevin Wolf
    int64_t refcount_block_offset;
109 f7d0fe02 Kevin Wolf
110 f7d0fe02 Kevin Wolf
    refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
111 f7d0fe02 Kevin Wolf
    if (refcount_table_index >= s->refcount_table_size)
112 f7d0fe02 Kevin Wolf
        return 0;
113 f7d0fe02 Kevin Wolf
    refcount_block_offset = s->refcount_table[refcount_table_index];
114 f7d0fe02 Kevin Wolf
    if (!refcount_block_offset)
115 f7d0fe02 Kevin Wolf
        return 0;
116 f7d0fe02 Kevin Wolf
    if (refcount_block_offset != s->refcount_block_cache_offset) {
117 f7d0fe02 Kevin Wolf
        /* better than nothing: return allocated if read error */
118 f7d0fe02 Kevin Wolf
        if (load_refcount_block(bs, refcount_block_offset) < 0)
119 f7d0fe02 Kevin Wolf
            return 1;
120 f7d0fe02 Kevin Wolf
    }
121 f7d0fe02 Kevin Wolf
    block_index = cluster_index &
122 f7d0fe02 Kevin Wolf
        ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
123 f7d0fe02 Kevin Wolf
    return be16_to_cpu(s->refcount_block_cache[block_index]);
124 f7d0fe02 Kevin Wolf
}
125 f7d0fe02 Kevin Wolf
126 f7d0fe02 Kevin Wolf
static int grow_refcount_table(BlockDriverState *bs, int min_size)
127 f7d0fe02 Kevin Wolf
{
128 f7d0fe02 Kevin Wolf
    BDRVQcowState *s = bs->opaque;
129 f7d0fe02 Kevin Wolf
    int new_table_size, new_table_size2, refcount_table_clusters, i, ret;
130 f7d0fe02 Kevin Wolf
    uint64_t *new_table;
131 f7d0fe02 Kevin Wolf
    int64_t table_offset;
132 f7d0fe02 Kevin Wolf
    uint8_t data[12];
133 f7d0fe02 Kevin Wolf
    int old_table_size;
134 f7d0fe02 Kevin Wolf
    int64_t old_table_offset;
135 f7d0fe02 Kevin Wolf
136 f7d0fe02 Kevin Wolf
    if (min_size <= s->refcount_table_size)
137 f7d0fe02 Kevin Wolf
        return 0;
138 f7d0fe02 Kevin Wolf
    /* compute new table size */
139 f7d0fe02 Kevin Wolf
    refcount_table_clusters = s->refcount_table_size >> (s->cluster_bits - 3);
140 f7d0fe02 Kevin Wolf
    for(;;) {
141 f7d0fe02 Kevin Wolf
        if (refcount_table_clusters == 0) {
142 f7d0fe02 Kevin Wolf
            refcount_table_clusters = 1;
143 f7d0fe02 Kevin Wolf
        } else {
144 f7d0fe02 Kevin Wolf
            refcount_table_clusters = (refcount_table_clusters * 3 + 1) / 2;
145 f7d0fe02 Kevin Wolf
        }
146 f7d0fe02 Kevin Wolf
        new_table_size = refcount_table_clusters << (s->cluster_bits - 3);
147 f7d0fe02 Kevin Wolf
        if (min_size <= new_table_size)
148 f7d0fe02 Kevin Wolf
            break;
149 f7d0fe02 Kevin Wolf
    }
150 f7d0fe02 Kevin Wolf
#ifdef DEBUG_ALLOC2
151 f7d0fe02 Kevin Wolf
    printf("grow_refcount_table from %d to %d\n",
152 f7d0fe02 Kevin Wolf
           s->refcount_table_size,
153 f7d0fe02 Kevin Wolf
           new_table_size);
154 f7d0fe02 Kevin Wolf
#endif
155 f7d0fe02 Kevin Wolf
    new_table_size2 = new_table_size * sizeof(uint64_t);
156 f7d0fe02 Kevin Wolf
    new_table = qemu_mallocz(new_table_size2);
157 f7d0fe02 Kevin Wolf
    memcpy(new_table, s->refcount_table,
158 f7d0fe02 Kevin Wolf
           s->refcount_table_size * sizeof(uint64_t));
159 f7d0fe02 Kevin Wolf
    for(i = 0; i < s->refcount_table_size; i++)
160 f7d0fe02 Kevin Wolf
        cpu_to_be64s(&new_table[i]);
161 f7d0fe02 Kevin Wolf
    /* Note: we cannot update the refcount now to avoid recursion */
162 f7d0fe02 Kevin Wolf
    table_offset = alloc_clusters_noref(bs, new_table_size2);
163 f7d0fe02 Kevin Wolf
    ret = bdrv_pwrite(s->hd, table_offset, new_table, new_table_size2);
164 f7d0fe02 Kevin Wolf
    if (ret != new_table_size2)
165 f7d0fe02 Kevin Wolf
        goto fail;
166 f7d0fe02 Kevin Wolf
    for(i = 0; i < s->refcount_table_size; i++)
167 f7d0fe02 Kevin Wolf
        be64_to_cpus(&new_table[i]);
168 f7d0fe02 Kevin Wolf
169 f7d0fe02 Kevin Wolf
    cpu_to_be64w((uint64_t*)data, table_offset);
170 f7d0fe02 Kevin Wolf
    cpu_to_be32w((uint32_t*)(data + 8), refcount_table_clusters);
171 f7d0fe02 Kevin Wolf
    if (bdrv_pwrite(s->hd, offsetof(QCowHeader, refcount_table_offset),
172 f7d0fe02 Kevin Wolf
                    data, sizeof(data)) != sizeof(data))
173 f7d0fe02 Kevin Wolf
        goto fail;
174 f7d0fe02 Kevin Wolf
    qemu_free(s->refcount_table);
175 f7d0fe02 Kevin Wolf
    old_table_offset = s->refcount_table_offset;
176 f7d0fe02 Kevin Wolf
    old_table_size = s->refcount_table_size;
177 f7d0fe02 Kevin Wolf
    s->refcount_table = new_table;
178 f7d0fe02 Kevin Wolf
    s->refcount_table_size = new_table_size;
179 f7d0fe02 Kevin Wolf
    s->refcount_table_offset = table_offset;
180 f7d0fe02 Kevin Wolf
181 f7d0fe02 Kevin Wolf
    update_refcount(bs, table_offset, new_table_size2, 1);
182 ed6ccf0f Kevin Wolf
    qcow2_free_clusters(bs, old_table_offset, old_table_size * sizeof(uint64_t));
183 f7d0fe02 Kevin Wolf
    return 0;
184 f7d0fe02 Kevin Wolf
 fail:
185 ed6ccf0f Kevin Wolf
    qcow2_free_clusters(bs, table_offset, new_table_size2);
186 f7d0fe02 Kevin Wolf
    qemu_free(new_table);
187 f7d0fe02 Kevin Wolf
    return -EIO;
188 f7d0fe02 Kevin Wolf
}
189 f7d0fe02 Kevin Wolf
190 f7d0fe02 Kevin Wolf
191 f7d0fe02 Kevin Wolf
static int64_t alloc_refcount_block(BlockDriverState *bs, int64_t cluster_index)
192 f7d0fe02 Kevin Wolf
{
193 f7d0fe02 Kevin Wolf
    BDRVQcowState *s = bs->opaque;
194 f7d0fe02 Kevin Wolf
    int64_t offset, refcount_block_offset;
195 f7d0fe02 Kevin Wolf
    int ret, refcount_table_index;
196 f7d0fe02 Kevin Wolf
    uint64_t data64;
197 3b88e52b Kevin Wolf
    int cache = cache_refcount_updates;
198 f7d0fe02 Kevin Wolf
199 f7d0fe02 Kevin Wolf
    /* Find L1 index and grow refcount table if needed */
200 f7d0fe02 Kevin Wolf
    refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
201 f7d0fe02 Kevin Wolf
    if (refcount_table_index >= s->refcount_table_size) {
202 f7d0fe02 Kevin Wolf
        ret = grow_refcount_table(bs, refcount_table_index + 1);
203 f7d0fe02 Kevin Wolf
        if (ret < 0)
204 f7d0fe02 Kevin Wolf
            return ret;
205 f7d0fe02 Kevin Wolf
    }
206 f7d0fe02 Kevin Wolf
207 f7d0fe02 Kevin Wolf
    /* Load or allocate the refcount block */
208 f7d0fe02 Kevin Wolf
    refcount_block_offset = s->refcount_table[refcount_table_index];
209 f7d0fe02 Kevin Wolf
    if (!refcount_block_offset) {
210 3b88e52b Kevin Wolf
        if (cache_refcount_updates) {
211 3b88e52b Kevin Wolf
            write_refcount_block(s);
212 3b88e52b Kevin Wolf
            cache_refcount_updates = 0;
213 3b88e52b Kevin Wolf
        }
214 f7d0fe02 Kevin Wolf
        /* create a new refcount block */
215 f7d0fe02 Kevin Wolf
        /* Note: we cannot update the refcount now to avoid recursion */
216 f7d0fe02 Kevin Wolf
        offset = alloc_clusters_noref(bs, s->cluster_size);
217 f7d0fe02 Kevin Wolf
        memset(s->refcount_block_cache, 0, s->cluster_size);
218 f7d0fe02 Kevin Wolf
        ret = bdrv_pwrite(s->hd, offset, s->refcount_block_cache, s->cluster_size);
219 f7d0fe02 Kevin Wolf
        if (ret != s->cluster_size)
220 f7d0fe02 Kevin Wolf
            return -EINVAL;
221 f7d0fe02 Kevin Wolf
        s->refcount_table[refcount_table_index] = offset;
222 f7d0fe02 Kevin Wolf
        data64 = cpu_to_be64(offset);
223 f7d0fe02 Kevin Wolf
        ret = bdrv_pwrite(s->hd, s->refcount_table_offset +
224 f7d0fe02 Kevin Wolf
                          refcount_table_index * sizeof(uint64_t),
225 f7d0fe02 Kevin Wolf
                          &data64, sizeof(data64));
226 f7d0fe02 Kevin Wolf
        if (ret != sizeof(data64))
227 f7d0fe02 Kevin Wolf
            return -EINVAL;
228 f7d0fe02 Kevin Wolf
229 f7d0fe02 Kevin Wolf
        refcount_block_offset = offset;
230 f7d0fe02 Kevin Wolf
        s->refcount_block_cache_offset = offset;
231 f7d0fe02 Kevin Wolf
        update_refcount(bs, offset, s->cluster_size, 1);
232 3b88e52b Kevin Wolf
        cache_refcount_updates = cache;
233 f7d0fe02 Kevin Wolf
    } else {
234 f7d0fe02 Kevin Wolf
        if (refcount_block_offset != s->refcount_block_cache_offset) {
235 f7d0fe02 Kevin Wolf
            if (load_refcount_block(bs, refcount_block_offset) < 0)
236 f7d0fe02 Kevin Wolf
                return -EIO;
237 f7d0fe02 Kevin Wolf
        }
238 f7d0fe02 Kevin Wolf
    }
239 f7d0fe02 Kevin Wolf
240 f7d0fe02 Kevin Wolf
    return refcount_block_offset;
241 f7d0fe02 Kevin Wolf
}
242 f7d0fe02 Kevin Wolf
243 9923e05e Kevin Wolf
#define REFCOUNTS_PER_SECTOR (512 >> REFCOUNT_SHIFT)
244 9923e05e Kevin Wolf
static int write_refcount_block_entries(BDRVQcowState *s,
245 9923e05e Kevin Wolf
    int64_t refcount_block_offset, int first_index, int last_index)
246 9923e05e Kevin Wolf
{
247 9923e05e Kevin Wolf
    size_t size;
248 9923e05e Kevin Wolf
249 3b88e52b Kevin Wolf
    if (cache_refcount_updates) {
250 3b88e52b Kevin Wolf
        return 0;
251 3b88e52b Kevin Wolf
    }
252 3b88e52b Kevin Wolf
253 9923e05e Kevin Wolf
    first_index &= ~(REFCOUNTS_PER_SECTOR - 1);
254 9923e05e Kevin Wolf
    last_index = (last_index + REFCOUNTS_PER_SECTOR)
255 9923e05e Kevin Wolf
        & ~(REFCOUNTS_PER_SECTOR - 1);
256 9923e05e Kevin Wolf
257 9923e05e Kevin Wolf
    size = (last_index - first_index) << REFCOUNT_SHIFT;
258 9923e05e Kevin Wolf
    if (bdrv_pwrite(s->hd,
259 9923e05e Kevin Wolf
        refcount_block_offset + (first_index << REFCOUNT_SHIFT),
260 9923e05e Kevin Wolf
        &s->refcount_block_cache[first_index], size) != size)
261 9923e05e Kevin Wolf
    {
262 9923e05e Kevin Wolf
        return -EIO;
263 9923e05e Kevin Wolf
    }
264 9923e05e Kevin Wolf
265 9923e05e Kevin Wolf
    return 0;
266 9923e05e Kevin Wolf
}
267 9923e05e Kevin Wolf
268 f7d0fe02 Kevin Wolf
/* XXX: cache several refcount block clusters ? */
269 f7d0fe02 Kevin Wolf
static int update_refcount(BlockDriverState *bs,
270 f7d0fe02 Kevin Wolf
                            int64_t offset, int64_t length,
271 f7d0fe02 Kevin Wolf
                            int addend)
272 f7d0fe02 Kevin Wolf
{
273 f7d0fe02 Kevin Wolf
    BDRVQcowState *s = bs->opaque;
274 f7d0fe02 Kevin Wolf
    int64_t start, last, cluster_offset;
275 f7d0fe02 Kevin Wolf
    int64_t refcount_block_offset = 0;
276 f7d0fe02 Kevin Wolf
    int64_t table_index = -1, old_table_index;
277 f7d0fe02 Kevin Wolf
    int first_index = -1, last_index = -1;
278 f7d0fe02 Kevin Wolf
279 f7d0fe02 Kevin Wolf
#ifdef DEBUG_ALLOC2
280 f7d0fe02 Kevin Wolf
    printf("update_refcount: offset=%lld size=%lld addend=%d\n",
281 f7d0fe02 Kevin Wolf
           offset, length, addend);
282 f7d0fe02 Kevin Wolf
#endif
283 f7d0fe02 Kevin Wolf
    if (length <= 0)
284 f7d0fe02 Kevin Wolf
        return -EINVAL;
285 f7d0fe02 Kevin Wolf
    start = offset & ~(s->cluster_size - 1);
286 f7d0fe02 Kevin Wolf
    last = (offset + length - 1) & ~(s->cluster_size - 1);
287 f7d0fe02 Kevin Wolf
    for(cluster_offset = start; cluster_offset <= last;
288 f7d0fe02 Kevin Wolf
        cluster_offset += s->cluster_size)
289 f7d0fe02 Kevin Wolf
    {
290 f7d0fe02 Kevin Wolf
        int block_index, refcount;
291 f7d0fe02 Kevin Wolf
        int64_t cluster_index = cluster_offset >> s->cluster_bits;
292 f7d0fe02 Kevin Wolf
293 f7d0fe02 Kevin Wolf
        /* Only write refcount block to disk when we are done with it */
294 f7d0fe02 Kevin Wolf
        old_table_index = table_index;
295 f7d0fe02 Kevin Wolf
        table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
296 f7d0fe02 Kevin Wolf
        if ((old_table_index >= 0) && (table_index != old_table_index)) {
297 9923e05e Kevin Wolf
298 9923e05e Kevin Wolf
            if (write_refcount_block_entries(s, refcount_block_offset,
299 9923e05e Kevin Wolf
                first_index, last_index) < 0)
300 f7d0fe02 Kevin Wolf
            {
301 f7d0fe02 Kevin Wolf
                return -EIO;
302 f7d0fe02 Kevin Wolf
            }
303 f7d0fe02 Kevin Wolf
304 f7d0fe02 Kevin Wolf
            first_index = -1;
305 f7d0fe02 Kevin Wolf
            last_index = -1;
306 f7d0fe02 Kevin Wolf
        }
307 f7d0fe02 Kevin Wolf
308 f7d0fe02 Kevin Wolf
        /* Load the refcount block and allocate it if needed */
309 f7d0fe02 Kevin Wolf
        refcount_block_offset = alloc_refcount_block(bs, cluster_index);
310 f7d0fe02 Kevin Wolf
        if (refcount_block_offset < 0) {
311 f7d0fe02 Kevin Wolf
            return refcount_block_offset;
312 f7d0fe02 Kevin Wolf
        }
313 f7d0fe02 Kevin Wolf
314 f7d0fe02 Kevin Wolf
        /* we can update the count and save it */
315 f7d0fe02 Kevin Wolf
        block_index = cluster_index &
316 f7d0fe02 Kevin Wolf
            ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
317 f7d0fe02 Kevin Wolf
        if (first_index == -1 || block_index < first_index) {
318 f7d0fe02 Kevin Wolf
            first_index = block_index;
319 f7d0fe02 Kevin Wolf
        }
320 f7d0fe02 Kevin Wolf
        if (block_index > last_index) {
321 f7d0fe02 Kevin Wolf
            last_index = block_index;
322 f7d0fe02 Kevin Wolf
        }
323 f7d0fe02 Kevin Wolf
324 f7d0fe02 Kevin Wolf
        refcount = be16_to_cpu(s->refcount_block_cache[block_index]);
325 f7d0fe02 Kevin Wolf
        refcount += addend;
326 f7d0fe02 Kevin Wolf
        if (refcount < 0 || refcount > 0xffff)
327 f7d0fe02 Kevin Wolf
            return -EINVAL;
328 f7d0fe02 Kevin Wolf
        if (refcount == 0 && cluster_index < s->free_cluster_index) {
329 f7d0fe02 Kevin Wolf
            s->free_cluster_index = cluster_index;
330 f7d0fe02 Kevin Wolf
        }
331 f7d0fe02 Kevin Wolf
        s->refcount_block_cache[block_index] = cpu_to_be16(refcount);
332 f7d0fe02 Kevin Wolf
    }
333 f7d0fe02 Kevin Wolf
334 f7d0fe02 Kevin Wolf
    /* Write last changed block to disk */
335 f7d0fe02 Kevin Wolf
    if (refcount_block_offset != 0) {
336 9923e05e Kevin Wolf
        if (write_refcount_block_entries(s, refcount_block_offset,
337 9923e05e Kevin Wolf
            first_index, last_index) < 0)
338 f7d0fe02 Kevin Wolf
        {
339 f7d0fe02 Kevin Wolf
            return -EIO;
340 f7d0fe02 Kevin Wolf
        }
341 f7d0fe02 Kevin Wolf
    }
342 f7d0fe02 Kevin Wolf
343 f7d0fe02 Kevin Wolf
    return 0;
344 f7d0fe02 Kevin Wolf
}
345 f7d0fe02 Kevin Wolf
346 f7d0fe02 Kevin Wolf
/* addend must be 1 or -1 */
347 f7d0fe02 Kevin Wolf
static int update_cluster_refcount(BlockDriverState *bs,
348 f7d0fe02 Kevin Wolf
                                   int64_t cluster_index,
349 f7d0fe02 Kevin Wolf
                                   int addend)
350 f7d0fe02 Kevin Wolf
{
351 f7d0fe02 Kevin Wolf
    BDRVQcowState *s = bs->opaque;
352 f7d0fe02 Kevin Wolf
    int ret;
353 f7d0fe02 Kevin Wolf
354 f7d0fe02 Kevin Wolf
    ret = update_refcount(bs, cluster_index << s->cluster_bits, 1, addend);
355 f7d0fe02 Kevin Wolf
    if (ret < 0) {
356 f7d0fe02 Kevin Wolf
        return ret;
357 f7d0fe02 Kevin Wolf
    }
358 f7d0fe02 Kevin Wolf
359 f7d0fe02 Kevin Wolf
    return get_refcount(bs, cluster_index);
360 f7d0fe02 Kevin Wolf
}
361 f7d0fe02 Kevin Wolf
362 f7d0fe02 Kevin Wolf
363 f7d0fe02 Kevin Wolf
364 f7d0fe02 Kevin Wolf
/*********************************************************/
365 f7d0fe02 Kevin Wolf
/* cluster allocation functions */
366 f7d0fe02 Kevin Wolf
367 f7d0fe02 Kevin Wolf
368 f7d0fe02 Kevin Wolf
369 f7d0fe02 Kevin Wolf
/* return < 0 if error */
370 f7d0fe02 Kevin Wolf
static int64_t alloc_clusters_noref(BlockDriverState *bs, int64_t size)
371 f7d0fe02 Kevin Wolf
{
372 f7d0fe02 Kevin Wolf
    BDRVQcowState *s = bs->opaque;
373 f7d0fe02 Kevin Wolf
    int i, nb_clusters;
374 f7d0fe02 Kevin Wolf
375 f7d0fe02 Kevin Wolf
    nb_clusters = size_to_clusters(s, size);
376 f7d0fe02 Kevin Wolf
retry:
377 f7d0fe02 Kevin Wolf
    for(i = 0; i < nb_clusters; i++) {
378 f7d0fe02 Kevin Wolf
        int64_t i = s->free_cluster_index++;
379 f7d0fe02 Kevin Wolf
        if (get_refcount(bs, i) != 0)
380 f7d0fe02 Kevin Wolf
            goto retry;
381 f7d0fe02 Kevin Wolf
    }
382 f7d0fe02 Kevin Wolf
#ifdef DEBUG_ALLOC2
383 f7d0fe02 Kevin Wolf
    printf("alloc_clusters: size=%lld -> %lld\n",
384 f7d0fe02 Kevin Wolf
            size,
385 f7d0fe02 Kevin Wolf
            (s->free_cluster_index - nb_clusters) << s->cluster_bits);
386 f7d0fe02 Kevin Wolf
#endif
387 f7d0fe02 Kevin Wolf
    return (s->free_cluster_index - nb_clusters) << s->cluster_bits;
388 f7d0fe02 Kevin Wolf
}
389 f7d0fe02 Kevin Wolf
390 ed6ccf0f Kevin Wolf
int64_t qcow2_alloc_clusters(BlockDriverState *bs, int64_t size)
391 f7d0fe02 Kevin Wolf
{
392 f7d0fe02 Kevin Wolf
    int64_t offset;
393 f7d0fe02 Kevin Wolf
394 f7d0fe02 Kevin Wolf
    offset = alloc_clusters_noref(bs, size);
395 f7d0fe02 Kevin Wolf
    update_refcount(bs, offset, size, 1);
396 f7d0fe02 Kevin Wolf
    return offset;
397 f7d0fe02 Kevin Wolf
}
398 f7d0fe02 Kevin Wolf
399 f7d0fe02 Kevin Wolf
/* only used to allocate compressed sectors. We try to allocate
400 f7d0fe02 Kevin Wolf
   contiguous sectors. size must be <= cluster_size */
401 ed6ccf0f Kevin Wolf
int64_t qcow2_alloc_bytes(BlockDriverState *bs, int size)
402 f7d0fe02 Kevin Wolf
{
403 f7d0fe02 Kevin Wolf
    BDRVQcowState *s = bs->opaque;
404 f7d0fe02 Kevin Wolf
    int64_t offset, cluster_offset;
405 f7d0fe02 Kevin Wolf
    int free_in_cluster;
406 f7d0fe02 Kevin Wolf
407 f7d0fe02 Kevin Wolf
    assert(size > 0 && size <= s->cluster_size);
408 f7d0fe02 Kevin Wolf
    if (s->free_byte_offset == 0) {
409 ed6ccf0f Kevin Wolf
        s->free_byte_offset = qcow2_alloc_clusters(bs, s->cluster_size);
410 f7d0fe02 Kevin Wolf
    }
411 f7d0fe02 Kevin Wolf
 redo:
412 f7d0fe02 Kevin Wolf
    free_in_cluster = s->cluster_size -
413 f7d0fe02 Kevin Wolf
        (s->free_byte_offset & (s->cluster_size - 1));
414 f7d0fe02 Kevin Wolf
    if (size <= free_in_cluster) {
415 f7d0fe02 Kevin Wolf
        /* enough space in current cluster */
416 f7d0fe02 Kevin Wolf
        offset = s->free_byte_offset;
417 f7d0fe02 Kevin Wolf
        s->free_byte_offset += size;
418 f7d0fe02 Kevin Wolf
        free_in_cluster -= size;
419 f7d0fe02 Kevin Wolf
        if (free_in_cluster == 0)
420 f7d0fe02 Kevin Wolf
            s->free_byte_offset = 0;
421 f7d0fe02 Kevin Wolf
        if ((offset & (s->cluster_size - 1)) != 0)
422 f7d0fe02 Kevin Wolf
            update_cluster_refcount(bs, offset >> s->cluster_bits, 1);
423 f7d0fe02 Kevin Wolf
    } else {
424 ed6ccf0f Kevin Wolf
        offset = qcow2_alloc_clusters(bs, s->cluster_size);
425 f7d0fe02 Kevin Wolf
        cluster_offset = s->free_byte_offset & ~(s->cluster_size - 1);
426 f7d0fe02 Kevin Wolf
        if ((cluster_offset + s->cluster_size) == offset) {
427 f7d0fe02 Kevin Wolf
            /* we are lucky: contiguous data */
428 f7d0fe02 Kevin Wolf
            offset = s->free_byte_offset;
429 f7d0fe02 Kevin Wolf
            update_cluster_refcount(bs, offset >> s->cluster_bits, 1);
430 f7d0fe02 Kevin Wolf
            s->free_byte_offset += size;
431 f7d0fe02 Kevin Wolf
        } else {
432 f7d0fe02 Kevin Wolf
            s->free_byte_offset = offset;
433 f7d0fe02 Kevin Wolf
            goto redo;
434 f7d0fe02 Kevin Wolf
        }
435 f7d0fe02 Kevin Wolf
    }
436 f7d0fe02 Kevin Wolf
    return offset;
437 f7d0fe02 Kevin Wolf
}
438 f7d0fe02 Kevin Wolf
439 ed6ccf0f Kevin Wolf
void qcow2_free_clusters(BlockDriverState *bs,
440 f7d0fe02 Kevin Wolf
                          int64_t offset, int64_t size)
441 f7d0fe02 Kevin Wolf
{
442 f7d0fe02 Kevin Wolf
    update_refcount(bs, offset, size, -1);
443 f7d0fe02 Kevin Wolf
}
444 f7d0fe02 Kevin Wolf
445 45aba42f Kevin Wolf
/*
446 45aba42f Kevin Wolf
 * free_any_clusters
447 45aba42f Kevin Wolf
 *
448 45aba42f Kevin Wolf
 * free clusters according to its type: compressed or not
449 45aba42f Kevin Wolf
 *
450 45aba42f Kevin Wolf
 */
451 45aba42f Kevin Wolf
452 ed6ccf0f Kevin Wolf
void qcow2_free_any_clusters(BlockDriverState *bs,
453 45aba42f Kevin Wolf
    uint64_t cluster_offset, int nb_clusters)
454 45aba42f Kevin Wolf
{
455 45aba42f Kevin Wolf
    BDRVQcowState *s = bs->opaque;
456 45aba42f Kevin Wolf
457 45aba42f Kevin Wolf
    /* free the cluster */
458 45aba42f Kevin Wolf
459 45aba42f Kevin Wolf
    if (cluster_offset & QCOW_OFLAG_COMPRESSED) {
460 45aba42f Kevin Wolf
        int nb_csectors;
461 45aba42f Kevin Wolf
        nb_csectors = ((cluster_offset >> s->csize_shift) &
462 45aba42f Kevin Wolf
                       s->csize_mask) + 1;
463 ed6ccf0f Kevin Wolf
        qcow2_free_clusters(bs,
464 ed6ccf0f Kevin Wolf
            (cluster_offset & s->cluster_offset_mask) & ~511,
465 ed6ccf0f Kevin Wolf
            nb_csectors * 512);
466 45aba42f Kevin Wolf
        return;
467 45aba42f Kevin Wolf
    }
468 45aba42f Kevin Wolf
469 ed6ccf0f Kevin Wolf
    qcow2_free_clusters(bs, cluster_offset, nb_clusters << s->cluster_bits);
470 45aba42f Kevin Wolf
471 45aba42f Kevin Wolf
    return;
472 45aba42f Kevin Wolf
}
473 45aba42f Kevin Wolf
474 f7d0fe02 Kevin Wolf
475 f7d0fe02 Kevin Wolf
476 f7d0fe02 Kevin Wolf
/*********************************************************/
477 f7d0fe02 Kevin Wolf
/* snapshots and image creation */
478 f7d0fe02 Kevin Wolf
479 f7d0fe02 Kevin Wolf
480 f7d0fe02 Kevin Wolf
481 ed6ccf0f Kevin Wolf
void qcow2_create_refcount_update(QCowCreateState *s, int64_t offset,
482 ed6ccf0f Kevin Wolf
    int64_t size)
483 f7d0fe02 Kevin Wolf
{
484 f7d0fe02 Kevin Wolf
    int refcount;
485 f7d0fe02 Kevin Wolf
    int64_t start, last, cluster_offset;
486 f7d0fe02 Kevin Wolf
    uint16_t *p;
487 f7d0fe02 Kevin Wolf
488 f7d0fe02 Kevin Wolf
    start = offset & ~(s->cluster_size - 1);
489 f7d0fe02 Kevin Wolf
    last = (offset + size - 1)  & ~(s->cluster_size - 1);
490 f7d0fe02 Kevin Wolf
    for(cluster_offset = start; cluster_offset <= last;
491 f7d0fe02 Kevin Wolf
        cluster_offset += s->cluster_size) {
492 f7d0fe02 Kevin Wolf
        p = &s->refcount_block[cluster_offset >> s->cluster_bits];
493 f7d0fe02 Kevin Wolf
        refcount = be16_to_cpu(*p);
494 f7d0fe02 Kevin Wolf
        refcount++;
495 f7d0fe02 Kevin Wolf
        *p = cpu_to_be16(refcount);
496 f7d0fe02 Kevin Wolf
    }
497 f7d0fe02 Kevin Wolf
}
498 f7d0fe02 Kevin Wolf
499 f7d0fe02 Kevin Wolf
/* update the refcounts of snapshots and the copied flag */
500 ed6ccf0f Kevin Wolf
int qcow2_update_snapshot_refcount(BlockDriverState *bs,
501 ed6ccf0f Kevin Wolf
    int64_t l1_table_offset, int l1_size, int addend)
502 f7d0fe02 Kevin Wolf
{
503 f7d0fe02 Kevin Wolf
    BDRVQcowState *s = bs->opaque;
504 f7d0fe02 Kevin Wolf
    uint64_t *l1_table, *l2_table, l2_offset, offset, l1_size2, l1_allocated;
505 f7d0fe02 Kevin Wolf
    int64_t old_offset, old_l2_offset;
506 f7d0fe02 Kevin Wolf
    int l2_size, i, j, l1_modified, l2_modified, nb_csectors, refcount;
507 f7d0fe02 Kevin Wolf
508 ed6ccf0f Kevin Wolf
    qcow2_l2_cache_reset(bs);
509 3b88e52b Kevin Wolf
    cache_refcount_updates = 1;
510 f7d0fe02 Kevin Wolf
511 f7d0fe02 Kevin Wolf
    l2_table = NULL;
512 f7d0fe02 Kevin Wolf
    l1_table = NULL;
513 f7d0fe02 Kevin Wolf
    l1_size2 = l1_size * sizeof(uint64_t);
514 f7d0fe02 Kevin Wolf
    l1_allocated = 0;
515 f7d0fe02 Kevin Wolf
    if (l1_table_offset != s->l1_table_offset) {
516 f7d0fe02 Kevin Wolf
        l1_table = qemu_malloc(l1_size2);
517 f7d0fe02 Kevin Wolf
        l1_allocated = 1;
518 f7d0fe02 Kevin Wolf
        if (bdrv_pread(s->hd, l1_table_offset,
519 f7d0fe02 Kevin Wolf
                       l1_table, l1_size2) != l1_size2)
520 f7d0fe02 Kevin Wolf
            goto fail;
521 f7d0fe02 Kevin Wolf
        for(i = 0;i < l1_size; i++)
522 f7d0fe02 Kevin Wolf
            be64_to_cpus(&l1_table[i]);
523 f7d0fe02 Kevin Wolf
    } else {
524 f7d0fe02 Kevin Wolf
        assert(l1_size == s->l1_size);
525 f7d0fe02 Kevin Wolf
        l1_table = s->l1_table;
526 f7d0fe02 Kevin Wolf
        l1_allocated = 0;
527 f7d0fe02 Kevin Wolf
    }
528 f7d0fe02 Kevin Wolf
529 f7d0fe02 Kevin Wolf
    l2_size = s->l2_size * sizeof(uint64_t);
530 f7d0fe02 Kevin Wolf
    l2_table = qemu_malloc(l2_size);
531 f7d0fe02 Kevin Wolf
    l1_modified = 0;
532 f7d0fe02 Kevin Wolf
    for(i = 0; i < l1_size; i++) {
533 f7d0fe02 Kevin Wolf
        l2_offset = l1_table[i];
534 f7d0fe02 Kevin Wolf
        if (l2_offset) {
535 f7d0fe02 Kevin Wolf
            old_l2_offset = l2_offset;
536 f7d0fe02 Kevin Wolf
            l2_offset &= ~QCOW_OFLAG_COPIED;
537 f7d0fe02 Kevin Wolf
            l2_modified = 0;
538 f7d0fe02 Kevin Wolf
            if (bdrv_pread(s->hd, l2_offset, l2_table, l2_size) != l2_size)
539 f7d0fe02 Kevin Wolf
                goto fail;
540 f7d0fe02 Kevin Wolf
            for(j = 0; j < s->l2_size; j++) {
541 f7d0fe02 Kevin Wolf
                offset = be64_to_cpu(l2_table[j]);
542 f7d0fe02 Kevin Wolf
                if (offset != 0) {
543 f7d0fe02 Kevin Wolf
                    old_offset = offset;
544 f7d0fe02 Kevin Wolf
                    offset &= ~QCOW_OFLAG_COPIED;
545 f7d0fe02 Kevin Wolf
                    if (offset & QCOW_OFLAG_COMPRESSED) {
546 f7d0fe02 Kevin Wolf
                        nb_csectors = ((offset >> s->csize_shift) &
547 f7d0fe02 Kevin Wolf
                                       s->csize_mask) + 1;
548 f7d0fe02 Kevin Wolf
                        if (addend != 0)
549 f7d0fe02 Kevin Wolf
                            update_refcount(bs, (offset & s->cluster_offset_mask) & ~511,
550 f7d0fe02 Kevin Wolf
                                            nb_csectors * 512, addend);
551 f7d0fe02 Kevin Wolf
                        /* compressed clusters are never modified */
552 f7d0fe02 Kevin Wolf
                        refcount = 2;
553 f7d0fe02 Kevin Wolf
                    } else {
554 f7d0fe02 Kevin Wolf
                        if (addend != 0) {
555 f7d0fe02 Kevin Wolf
                            refcount = update_cluster_refcount(bs, offset >> s->cluster_bits, addend);
556 f7d0fe02 Kevin Wolf
                        } else {
557 f7d0fe02 Kevin Wolf
                            refcount = get_refcount(bs, offset >> s->cluster_bits);
558 f7d0fe02 Kevin Wolf
                        }
559 f7d0fe02 Kevin Wolf
                    }
560 f7d0fe02 Kevin Wolf
561 f7d0fe02 Kevin Wolf
                    if (refcount == 1) {
562 f7d0fe02 Kevin Wolf
                        offset |= QCOW_OFLAG_COPIED;
563 f7d0fe02 Kevin Wolf
                    }
564 f7d0fe02 Kevin Wolf
                    if (offset != old_offset) {
565 f7d0fe02 Kevin Wolf
                        l2_table[j] = cpu_to_be64(offset);
566 f7d0fe02 Kevin Wolf
                        l2_modified = 1;
567 f7d0fe02 Kevin Wolf
                    }
568 f7d0fe02 Kevin Wolf
                }
569 f7d0fe02 Kevin Wolf
            }
570 f7d0fe02 Kevin Wolf
            if (l2_modified) {
571 f7d0fe02 Kevin Wolf
                if (bdrv_pwrite(s->hd,
572 f7d0fe02 Kevin Wolf
                                l2_offset, l2_table, l2_size) != l2_size)
573 f7d0fe02 Kevin Wolf
                    goto fail;
574 f7d0fe02 Kevin Wolf
            }
575 f7d0fe02 Kevin Wolf
576 f7d0fe02 Kevin Wolf
            if (addend != 0) {
577 f7d0fe02 Kevin Wolf
                refcount = update_cluster_refcount(bs, l2_offset >> s->cluster_bits, addend);
578 f7d0fe02 Kevin Wolf
            } else {
579 f7d0fe02 Kevin Wolf
                refcount = get_refcount(bs, l2_offset >> s->cluster_bits);
580 f7d0fe02 Kevin Wolf
            }
581 f7d0fe02 Kevin Wolf
            if (refcount == 1) {
582 f7d0fe02 Kevin Wolf
                l2_offset |= QCOW_OFLAG_COPIED;
583 f7d0fe02 Kevin Wolf
            }
584 f7d0fe02 Kevin Wolf
            if (l2_offset != old_l2_offset) {
585 f7d0fe02 Kevin Wolf
                l1_table[i] = l2_offset;
586 f7d0fe02 Kevin Wolf
                l1_modified = 1;
587 f7d0fe02 Kevin Wolf
            }
588 f7d0fe02 Kevin Wolf
        }
589 f7d0fe02 Kevin Wolf
    }
590 f7d0fe02 Kevin Wolf
    if (l1_modified) {
591 f7d0fe02 Kevin Wolf
        for(i = 0; i < l1_size; i++)
592 f7d0fe02 Kevin Wolf
            cpu_to_be64s(&l1_table[i]);
593 f7d0fe02 Kevin Wolf
        if (bdrv_pwrite(s->hd, l1_table_offset, l1_table,
594 f7d0fe02 Kevin Wolf
                        l1_size2) != l1_size2)
595 f7d0fe02 Kevin Wolf
            goto fail;
596 f7d0fe02 Kevin Wolf
        for(i = 0; i < l1_size; i++)
597 f7d0fe02 Kevin Wolf
            be64_to_cpus(&l1_table[i]);
598 f7d0fe02 Kevin Wolf
    }
599 f7d0fe02 Kevin Wolf
    if (l1_allocated)
600 f7d0fe02 Kevin Wolf
        qemu_free(l1_table);
601 f7d0fe02 Kevin Wolf
    qemu_free(l2_table);
602 3b88e52b Kevin Wolf
    cache_refcount_updates = 0;
603 3b88e52b Kevin Wolf
    write_refcount_block(s);
604 f7d0fe02 Kevin Wolf
    return 0;
605 f7d0fe02 Kevin Wolf
 fail:
606 f7d0fe02 Kevin Wolf
    if (l1_allocated)
607 f7d0fe02 Kevin Wolf
        qemu_free(l1_table);
608 f7d0fe02 Kevin Wolf
    qemu_free(l2_table);
609 3b88e52b Kevin Wolf
    cache_refcount_updates = 0;
610 3b88e52b Kevin Wolf
    write_refcount_block(s);
611 f7d0fe02 Kevin Wolf
    return -EIO;
612 f7d0fe02 Kevin Wolf
}
613 f7d0fe02 Kevin Wolf
614 f7d0fe02 Kevin Wolf
615 f7d0fe02 Kevin Wolf
616 f7d0fe02 Kevin Wolf
617 f7d0fe02 Kevin Wolf
/*********************************************************/
618 f7d0fe02 Kevin Wolf
/* refcount checking functions */
619 f7d0fe02 Kevin Wolf
620 f7d0fe02 Kevin Wolf
621 f7d0fe02 Kevin Wolf
622 f7d0fe02 Kevin Wolf
/*
623 f7d0fe02 Kevin Wolf
 * Increases the refcount for a range of clusters in a given refcount table.
624 f7d0fe02 Kevin Wolf
 * This is used to construct a temporary refcount table out of L1 and L2 tables
625 f7d0fe02 Kevin Wolf
 * which can be compared the the refcount table saved in the image.
626 f7d0fe02 Kevin Wolf
 *
627 f7d0fe02 Kevin Wolf
 * Returns the number of errors in the image that were found
628 f7d0fe02 Kevin Wolf
 */
629 f7d0fe02 Kevin Wolf
static int inc_refcounts(BlockDriverState *bs,
630 f7d0fe02 Kevin Wolf
                          uint16_t *refcount_table,
631 f7d0fe02 Kevin Wolf
                          int refcount_table_size,
632 f7d0fe02 Kevin Wolf
                          int64_t offset, int64_t size)
633 f7d0fe02 Kevin Wolf
{
634 f7d0fe02 Kevin Wolf
    BDRVQcowState *s = bs->opaque;
635 f7d0fe02 Kevin Wolf
    int64_t start, last, cluster_offset;
636 f7d0fe02 Kevin Wolf
    int k;
637 f7d0fe02 Kevin Wolf
    int errors = 0;
638 f7d0fe02 Kevin Wolf
639 f7d0fe02 Kevin Wolf
    if (size <= 0)
640 f7d0fe02 Kevin Wolf
        return 0;
641 f7d0fe02 Kevin Wolf
642 f7d0fe02 Kevin Wolf
    start = offset & ~(s->cluster_size - 1);
643 f7d0fe02 Kevin Wolf
    last = (offset + size - 1) & ~(s->cluster_size - 1);
644 f7d0fe02 Kevin Wolf
    for(cluster_offset = start; cluster_offset <= last;
645 f7d0fe02 Kevin Wolf
        cluster_offset += s->cluster_size) {
646 f7d0fe02 Kevin Wolf
        k = cluster_offset >> s->cluster_bits;
647 f7d0fe02 Kevin Wolf
        if (k < 0 || k >= refcount_table_size) {
648 f7d0fe02 Kevin Wolf
            fprintf(stderr, "ERROR: invalid cluster offset=0x%" PRIx64 "\n",
649 f7d0fe02 Kevin Wolf
                cluster_offset);
650 f7d0fe02 Kevin Wolf
            errors++;
651 f7d0fe02 Kevin Wolf
        } else {
652 f7d0fe02 Kevin Wolf
            if (++refcount_table[k] == 0) {
653 f7d0fe02 Kevin Wolf
                fprintf(stderr, "ERROR: overflow cluster offset=0x%" PRIx64
654 f7d0fe02 Kevin Wolf
                    "\n", cluster_offset);
655 f7d0fe02 Kevin Wolf
                errors++;
656 f7d0fe02 Kevin Wolf
            }
657 f7d0fe02 Kevin Wolf
        }
658 f7d0fe02 Kevin Wolf
    }
659 f7d0fe02 Kevin Wolf
660 f7d0fe02 Kevin Wolf
    return errors;
661 f7d0fe02 Kevin Wolf
}
662 f7d0fe02 Kevin Wolf
663 f7d0fe02 Kevin Wolf
/*
664 f7d0fe02 Kevin Wolf
 * Increases the refcount in the given refcount table for the all clusters
665 f7d0fe02 Kevin Wolf
 * referenced in the L2 table. While doing so, performs some checks on L2
666 f7d0fe02 Kevin Wolf
 * entries.
667 f7d0fe02 Kevin Wolf
 *
668 f7d0fe02 Kevin Wolf
 * Returns the number of errors found by the checks or -errno if an internal
669 f7d0fe02 Kevin Wolf
 * error occurred.
670 f7d0fe02 Kevin Wolf
 */
671 f7d0fe02 Kevin Wolf
static int check_refcounts_l2(BlockDriverState *bs,
672 f7d0fe02 Kevin Wolf
    uint16_t *refcount_table, int refcount_table_size, int64_t l2_offset,
673 f7d0fe02 Kevin Wolf
    int check_copied)
674 f7d0fe02 Kevin Wolf
{
675 f7d0fe02 Kevin Wolf
    BDRVQcowState *s = bs->opaque;
676 f7d0fe02 Kevin Wolf
    uint64_t *l2_table, offset;
677 f7d0fe02 Kevin Wolf
    int i, l2_size, nb_csectors, refcount;
678 f7d0fe02 Kevin Wolf
    int errors = 0;
679 f7d0fe02 Kevin Wolf
680 f7d0fe02 Kevin Wolf
    /* Read L2 table from disk */
681 f7d0fe02 Kevin Wolf
    l2_size = s->l2_size * sizeof(uint64_t);
682 f7d0fe02 Kevin Wolf
    l2_table = qemu_malloc(l2_size);
683 f7d0fe02 Kevin Wolf
684 f7d0fe02 Kevin Wolf
    if (bdrv_pread(s->hd, l2_offset, l2_table, l2_size) != l2_size)
685 f7d0fe02 Kevin Wolf
        goto fail;
686 f7d0fe02 Kevin Wolf
687 f7d0fe02 Kevin Wolf
    /* Do the actual checks */
688 f7d0fe02 Kevin Wolf
    for(i = 0; i < s->l2_size; i++) {
689 f7d0fe02 Kevin Wolf
        offset = be64_to_cpu(l2_table[i]);
690 f7d0fe02 Kevin Wolf
        if (offset != 0) {
691 f7d0fe02 Kevin Wolf
            if (offset & QCOW_OFLAG_COMPRESSED) {
692 f7d0fe02 Kevin Wolf
                /* Compressed clusters don't have QCOW_OFLAG_COPIED */
693 f7d0fe02 Kevin Wolf
                if (offset & QCOW_OFLAG_COPIED) {
694 f7d0fe02 Kevin Wolf
                    fprintf(stderr, "ERROR: cluster %" PRId64 ": "
695 f7d0fe02 Kevin Wolf
                        "copied flag must never be set for compressed "
696 f7d0fe02 Kevin Wolf
                        "clusters\n", offset >> s->cluster_bits);
697 f7d0fe02 Kevin Wolf
                    offset &= ~QCOW_OFLAG_COPIED;
698 f7d0fe02 Kevin Wolf
                    errors++;
699 f7d0fe02 Kevin Wolf
                }
700 f7d0fe02 Kevin Wolf
701 f7d0fe02 Kevin Wolf
                /* Mark cluster as used */
702 f7d0fe02 Kevin Wolf
                nb_csectors = ((offset >> s->csize_shift) &
703 f7d0fe02 Kevin Wolf
                               s->csize_mask) + 1;
704 f7d0fe02 Kevin Wolf
                offset &= s->cluster_offset_mask;
705 f7d0fe02 Kevin Wolf
                errors += inc_refcounts(bs, refcount_table,
706 f7d0fe02 Kevin Wolf
                              refcount_table_size,
707 f7d0fe02 Kevin Wolf
                              offset & ~511, nb_csectors * 512);
708 f7d0fe02 Kevin Wolf
            } else {
709 f7d0fe02 Kevin Wolf
                /* QCOW_OFLAG_COPIED must be set iff refcount == 1 */
710 f7d0fe02 Kevin Wolf
                if (check_copied) {
711 f7d0fe02 Kevin Wolf
                    uint64_t entry = offset;
712 f7d0fe02 Kevin Wolf
                    offset &= ~QCOW_OFLAG_COPIED;
713 f7d0fe02 Kevin Wolf
                    refcount = get_refcount(bs, offset >> s->cluster_bits);
714 f7d0fe02 Kevin Wolf
                    if ((refcount == 1) != ((entry & QCOW_OFLAG_COPIED) != 0)) {
715 f7d0fe02 Kevin Wolf
                        fprintf(stderr, "ERROR OFLAG_COPIED: offset=%"
716 f7d0fe02 Kevin Wolf
                            PRIx64 " refcount=%d\n", entry, refcount);
717 f7d0fe02 Kevin Wolf
                        errors++;
718 f7d0fe02 Kevin Wolf
                    }
719 f7d0fe02 Kevin Wolf
                }
720 f7d0fe02 Kevin Wolf
721 f7d0fe02 Kevin Wolf
                /* Mark cluster as used */
722 f7d0fe02 Kevin Wolf
                offset &= ~QCOW_OFLAG_COPIED;
723 f7d0fe02 Kevin Wolf
                errors += inc_refcounts(bs, refcount_table,
724 f7d0fe02 Kevin Wolf
                              refcount_table_size,
725 f7d0fe02 Kevin Wolf
                              offset, s->cluster_size);
726 f7d0fe02 Kevin Wolf
727 f7d0fe02 Kevin Wolf
                /* Correct offsets are cluster aligned */
728 f7d0fe02 Kevin Wolf
                if (offset & (s->cluster_size - 1)) {
729 f7d0fe02 Kevin Wolf
                    fprintf(stderr, "ERROR offset=%" PRIx64 ": Cluster is not "
730 f7d0fe02 Kevin Wolf
                        "properly aligned; L2 entry corrupted.\n", offset);
731 f7d0fe02 Kevin Wolf
                    errors++;
732 f7d0fe02 Kevin Wolf
                }
733 f7d0fe02 Kevin Wolf
            }
734 f7d0fe02 Kevin Wolf
        }
735 f7d0fe02 Kevin Wolf
    }
736 f7d0fe02 Kevin Wolf
737 f7d0fe02 Kevin Wolf
    qemu_free(l2_table);
738 f7d0fe02 Kevin Wolf
    return errors;
739 f7d0fe02 Kevin Wolf
740 f7d0fe02 Kevin Wolf
fail:
741 f7d0fe02 Kevin Wolf
    fprintf(stderr, "ERROR: I/O error in check_refcounts_l1\n");
742 f7d0fe02 Kevin Wolf
    qemu_free(l2_table);
743 f7d0fe02 Kevin Wolf
    return -EIO;
744 f7d0fe02 Kevin Wolf
}
745 f7d0fe02 Kevin Wolf
746 f7d0fe02 Kevin Wolf
/*
747 f7d0fe02 Kevin Wolf
 * Increases the refcount for the L1 table, its L2 tables and all referenced
748 f7d0fe02 Kevin Wolf
 * clusters in the given refcount table. While doing so, performs some checks
749 f7d0fe02 Kevin Wolf
 * on L1 and L2 entries.
750 f7d0fe02 Kevin Wolf
 *
751 f7d0fe02 Kevin Wolf
 * Returns the number of errors found by the checks or -errno if an internal
752 f7d0fe02 Kevin Wolf
 * error occurred.
753 f7d0fe02 Kevin Wolf
 */
754 f7d0fe02 Kevin Wolf
static int check_refcounts_l1(BlockDriverState *bs,
755 f7d0fe02 Kevin Wolf
                              uint16_t *refcount_table,
756 f7d0fe02 Kevin Wolf
                              int refcount_table_size,
757 f7d0fe02 Kevin Wolf
                              int64_t l1_table_offset, int l1_size,
758 f7d0fe02 Kevin Wolf
                              int check_copied)
759 f7d0fe02 Kevin Wolf
{
760 f7d0fe02 Kevin Wolf
    BDRVQcowState *s = bs->opaque;
761 f7d0fe02 Kevin Wolf
    uint64_t *l1_table, l2_offset, l1_size2;
762 f7d0fe02 Kevin Wolf
    int i, refcount, ret;
763 f7d0fe02 Kevin Wolf
    int errors = 0;
764 f7d0fe02 Kevin Wolf
765 f7d0fe02 Kevin Wolf
    l1_size2 = l1_size * sizeof(uint64_t);
766 f7d0fe02 Kevin Wolf
767 f7d0fe02 Kevin Wolf
    /* Mark L1 table as used */
768 f7d0fe02 Kevin Wolf
    errors += inc_refcounts(bs, refcount_table, refcount_table_size,
769 f7d0fe02 Kevin Wolf
                  l1_table_offset, l1_size2);
770 f7d0fe02 Kevin Wolf
771 f7d0fe02 Kevin Wolf
    /* Read L1 table entries from disk */
772 f7d0fe02 Kevin Wolf
    l1_table = qemu_malloc(l1_size2);
773 f7d0fe02 Kevin Wolf
    if (bdrv_pread(s->hd, l1_table_offset,
774 f7d0fe02 Kevin Wolf
                   l1_table, l1_size2) != l1_size2)
775 f7d0fe02 Kevin Wolf
        goto fail;
776 f7d0fe02 Kevin Wolf
    for(i = 0;i < l1_size; i++)
777 f7d0fe02 Kevin Wolf
        be64_to_cpus(&l1_table[i]);
778 f7d0fe02 Kevin Wolf
779 f7d0fe02 Kevin Wolf
    /* Do the actual checks */
780 f7d0fe02 Kevin Wolf
    for(i = 0; i < l1_size; i++) {
781 f7d0fe02 Kevin Wolf
        l2_offset = l1_table[i];
782 f7d0fe02 Kevin Wolf
        if (l2_offset) {
783 f7d0fe02 Kevin Wolf
            /* QCOW_OFLAG_COPIED must be set iff refcount == 1 */
784 f7d0fe02 Kevin Wolf
            if (check_copied) {
785 f7d0fe02 Kevin Wolf
                refcount = get_refcount(bs, (l2_offset & ~QCOW_OFLAG_COPIED)
786 f7d0fe02 Kevin Wolf
                    >> s->cluster_bits);
787 f7d0fe02 Kevin Wolf
                if ((refcount == 1) != ((l2_offset & QCOW_OFLAG_COPIED) != 0)) {
788 f7d0fe02 Kevin Wolf
                    fprintf(stderr, "ERROR OFLAG_COPIED: l2_offset=%" PRIx64
789 f7d0fe02 Kevin Wolf
                        " refcount=%d\n", l2_offset, refcount);
790 f7d0fe02 Kevin Wolf
                    errors++;
791 f7d0fe02 Kevin Wolf
                }
792 f7d0fe02 Kevin Wolf
            }
793 f7d0fe02 Kevin Wolf
794 f7d0fe02 Kevin Wolf
            /* Mark L2 table as used */
795 f7d0fe02 Kevin Wolf
            l2_offset &= ~QCOW_OFLAG_COPIED;
796 f7d0fe02 Kevin Wolf
            errors += inc_refcounts(bs, refcount_table,
797 f7d0fe02 Kevin Wolf
                          refcount_table_size,
798 f7d0fe02 Kevin Wolf
                          l2_offset,
799 f7d0fe02 Kevin Wolf
                          s->cluster_size);
800 f7d0fe02 Kevin Wolf
801 f7d0fe02 Kevin Wolf
            /* L2 tables are cluster aligned */
802 f7d0fe02 Kevin Wolf
            if (l2_offset & (s->cluster_size - 1)) {
803 f7d0fe02 Kevin Wolf
                fprintf(stderr, "ERROR l2_offset=%" PRIx64 ": Table is not "
804 f7d0fe02 Kevin Wolf
                    "cluster aligned; L1 entry corrupted\n", l2_offset);
805 f7d0fe02 Kevin Wolf
                errors++;
806 f7d0fe02 Kevin Wolf
            }
807 f7d0fe02 Kevin Wolf
808 f7d0fe02 Kevin Wolf
            /* Process and check L2 entries */
809 f7d0fe02 Kevin Wolf
            ret = check_refcounts_l2(bs, refcount_table, refcount_table_size,
810 f7d0fe02 Kevin Wolf
                l2_offset, check_copied);
811 f7d0fe02 Kevin Wolf
            if (ret < 0) {
812 f7d0fe02 Kevin Wolf
                goto fail;
813 f7d0fe02 Kevin Wolf
            }
814 f7d0fe02 Kevin Wolf
            errors += ret;
815 f7d0fe02 Kevin Wolf
        }
816 f7d0fe02 Kevin Wolf
    }
817 f7d0fe02 Kevin Wolf
    qemu_free(l1_table);
818 f7d0fe02 Kevin Wolf
    return errors;
819 f7d0fe02 Kevin Wolf
820 f7d0fe02 Kevin Wolf
fail:
821 f7d0fe02 Kevin Wolf
    fprintf(stderr, "ERROR: I/O error in check_refcounts_l1\n");
822 f7d0fe02 Kevin Wolf
    qemu_free(l1_table);
823 f7d0fe02 Kevin Wolf
    return -EIO;
824 f7d0fe02 Kevin Wolf
}
825 f7d0fe02 Kevin Wolf
826 f7d0fe02 Kevin Wolf
/*
827 f7d0fe02 Kevin Wolf
 * Checks an image for refcount consistency.
828 f7d0fe02 Kevin Wolf
 *
829 f7d0fe02 Kevin Wolf
 * Returns 0 if no errors are found, the number of errors in case the image is
830 f7d0fe02 Kevin Wolf
 * detected as corrupted, and -errno when an internal error occured.
831 f7d0fe02 Kevin Wolf
 */
832 ed6ccf0f Kevin Wolf
int qcow2_check_refcounts(BlockDriverState *bs)
833 f7d0fe02 Kevin Wolf
{
834 f7d0fe02 Kevin Wolf
    BDRVQcowState *s = bs->opaque;
835 f7d0fe02 Kevin Wolf
    int64_t size;
836 f7d0fe02 Kevin Wolf
    int nb_clusters, refcount1, refcount2, i;
837 f7d0fe02 Kevin Wolf
    QCowSnapshot *sn;
838 f7d0fe02 Kevin Wolf
    uint16_t *refcount_table;
839 f7d0fe02 Kevin Wolf
    int ret, errors = 0;
840 f7d0fe02 Kevin Wolf
841 f7d0fe02 Kevin Wolf
    size = bdrv_getlength(s->hd);
842 f7d0fe02 Kevin Wolf
    nb_clusters = size_to_clusters(s, size);
843 f7d0fe02 Kevin Wolf
    refcount_table = qemu_mallocz(nb_clusters * sizeof(uint16_t));
844 f7d0fe02 Kevin Wolf
845 f7d0fe02 Kevin Wolf
    /* header */
846 f7d0fe02 Kevin Wolf
    errors += inc_refcounts(bs, refcount_table, nb_clusters,
847 f7d0fe02 Kevin Wolf
                  0, s->cluster_size);
848 f7d0fe02 Kevin Wolf
849 f7d0fe02 Kevin Wolf
    /* current L1 table */
850 f7d0fe02 Kevin Wolf
    ret = check_refcounts_l1(bs, refcount_table, nb_clusters,
851 f7d0fe02 Kevin Wolf
                       s->l1_table_offset, s->l1_size, 1);
852 f7d0fe02 Kevin Wolf
    if (ret < 0) {
853 f7d0fe02 Kevin Wolf
        return ret;
854 f7d0fe02 Kevin Wolf
    }
855 f7d0fe02 Kevin Wolf
    errors += ret;
856 f7d0fe02 Kevin Wolf
857 f7d0fe02 Kevin Wolf
    /* snapshots */
858 f7d0fe02 Kevin Wolf
    for(i = 0; i < s->nb_snapshots; i++) {
859 f7d0fe02 Kevin Wolf
        sn = s->snapshots + i;
860 f7d0fe02 Kevin Wolf
        check_refcounts_l1(bs, refcount_table, nb_clusters,
861 f7d0fe02 Kevin Wolf
                           sn->l1_table_offset, sn->l1_size, 0);
862 f7d0fe02 Kevin Wolf
    }
863 f7d0fe02 Kevin Wolf
    errors += inc_refcounts(bs, refcount_table, nb_clusters,
864 f7d0fe02 Kevin Wolf
                  s->snapshots_offset, s->snapshots_size);
865 f7d0fe02 Kevin Wolf
866 f7d0fe02 Kevin Wolf
    /* refcount data */
867 f7d0fe02 Kevin Wolf
    errors += inc_refcounts(bs, refcount_table, nb_clusters,
868 f7d0fe02 Kevin Wolf
                  s->refcount_table_offset,
869 f7d0fe02 Kevin Wolf
                  s->refcount_table_size * sizeof(uint64_t));
870 f7d0fe02 Kevin Wolf
    for(i = 0; i < s->refcount_table_size; i++) {
871 f7d0fe02 Kevin Wolf
        int64_t offset;
872 f7d0fe02 Kevin Wolf
        offset = s->refcount_table[i];
873 f7d0fe02 Kevin Wolf
        if (offset != 0) {
874 f7d0fe02 Kevin Wolf
            errors += inc_refcounts(bs, refcount_table, nb_clusters,
875 f7d0fe02 Kevin Wolf
                          offset, s->cluster_size);
876 f7d0fe02 Kevin Wolf
        }
877 f7d0fe02 Kevin Wolf
    }
878 f7d0fe02 Kevin Wolf
879 f7d0fe02 Kevin Wolf
    /* compare ref counts */
880 f7d0fe02 Kevin Wolf
    for(i = 0; i < nb_clusters; i++) {
881 f7d0fe02 Kevin Wolf
        refcount1 = get_refcount(bs, i);
882 f7d0fe02 Kevin Wolf
        refcount2 = refcount_table[i];
883 f7d0fe02 Kevin Wolf
        if (refcount1 != refcount2) {
884 f7d0fe02 Kevin Wolf
            fprintf(stderr, "ERROR cluster %d refcount=%d reference=%d\n",
885 f7d0fe02 Kevin Wolf
                   i, refcount1, refcount2);
886 f7d0fe02 Kevin Wolf
            errors++;
887 f7d0fe02 Kevin Wolf
        }
888 f7d0fe02 Kevin Wolf
    }
889 f7d0fe02 Kevin Wolf
890 f7d0fe02 Kevin Wolf
    qemu_free(refcount_table);
891 f7d0fe02 Kevin Wolf
892 f7d0fe02 Kevin Wolf
    return errors;
893 f7d0fe02 Kevin Wolf
}