2 * Block driver for the QCOW version 2 format
4 * Copyright (c) 2004-2006 Fabrice Bellard
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:
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
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
27 #include "qemu-common.h"
28 #include "block_int.h"
29 #include "block/qcow2.h"
31 int grow_l1_table(BlockDriverState
*bs
, int min_size
)
33 BDRVQcowState
*s
= bs
->opaque
;
34 int new_l1_size
, new_l1_size2
, ret
, i
;
35 uint64_t *new_l1_table
;
36 uint64_t new_l1_table_offset
;
39 new_l1_size
= s
->l1_size
;
40 if (min_size
<= new_l1_size
)
42 while (min_size
> new_l1_size
) {
43 new_l1_size
= (new_l1_size
* 3 + 1) / 2;
46 printf("grow l1_table from %d to %d\n", s
->l1_size
, new_l1_size
);
49 new_l1_size2
= sizeof(uint64_t) * new_l1_size
;
50 new_l1_table
= qemu_mallocz(new_l1_size2
);
51 memcpy(new_l1_table
, s
->l1_table
, s
->l1_size
* sizeof(uint64_t));
53 /* write new table (align to cluster) */
54 new_l1_table_offset
= alloc_clusters(bs
, new_l1_size2
);
56 for(i
= 0; i
< s
->l1_size
; i
++)
57 new_l1_table
[i
] = cpu_to_be64(new_l1_table
[i
]);
58 ret
= bdrv_pwrite(s
->hd
, new_l1_table_offset
, new_l1_table
, new_l1_size2
);
59 if (ret
!= new_l1_size2
)
61 for(i
= 0; i
< s
->l1_size
; i
++)
62 new_l1_table
[i
] = be64_to_cpu(new_l1_table
[i
]);
65 cpu_to_be32w((uint32_t*)data
, new_l1_size
);
66 cpu_to_be64w((uint64_t*)(data
+ 4), new_l1_table_offset
);
67 if (bdrv_pwrite(s
->hd
, offsetof(QCowHeader
, l1_size
), data
,
68 sizeof(data
)) != sizeof(data
))
70 qemu_free(s
->l1_table
);
71 free_clusters(bs
, s
->l1_table_offset
, s
->l1_size
* sizeof(uint64_t));
72 s
->l1_table_offset
= new_l1_table_offset
;
73 s
->l1_table
= new_l1_table
;
74 s
->l1_size
= new_l1_size
;
77 qemu_free(s
->l1_table
);
81 void l2_cache_reset(BlockDriverState
*bs
)
83 BDRVQcowState
*s
= bs
->opaque
;
85 memset(s
->l2_cache
, 0, s
->l2_size
* L2_CACHE_SIZE
* sizeof(uint64_t));
86 memset(s
->l2_cache_offsets
, 0, L2_CACHE_SIZE
* sizeof(uint64_t));
87 memset(s
->l2_cache_counts
, 0, L2_CACHE_SIZE
* sizeof(uint32_t));
90 static inline int l2_cache_new_entry(BlockDriverState
*bs
)
92 BDRVQcowState
*s
= bs
->opaque
;
96 /* find a new entry in the least used one */
98 min_count
= 0xffffffff;
99 for(i
= 0; i
< L2_CACHE_SIZE
; i
++) {
100 if (s
->l2_cache_counts
[i
] < min_count
) {
101 min_count
= s
->l2_cache_counts
[i
];
111 * seek l2_offset in the l2_cache table
112 * if not found, return NULL,
114 * increments the l2 cache hit count of the entry,
115 * if counter overflow, divide by two all counters
116 * return the pointer to the l2 cache entry
120 static uint64_t *seek_l2_table(BDRVQcowState
*s
, uint64_t l2_offset
)
124 for(i
= 0; i
< L2_CACHE_SIZE
; i
++) {
125 if (l2_offset
== s
->l2_cache_offsets
[i
]) {
126 /* increment the hit count */
127 if (++s
->l2_cache_counts
[i
] == 0xffffffff) {
128 for(j
= 0; j
< L2_CACHE_SIZE
; j
++) {
129 s
->l2_cache_counts
[j
] >>= 1;
132 return s
->l2_cache
+ (i
<< s
->l2_bits
);
141 * Loads a L2 table into memory. If the table is in the cache, the cache
142 * is used; otherwise the L2 table is loaded from the image file.
144 * Returns a pointer to the L2 table on success, or NULL if the read from
145 * the image file failed.
148 static uint64_t *l2_load(BlockDriverState
*bs
, uint64_t l2_offset
)
150 BDRVQcowState
*s
= bs
->opaque
;
154 /* seek if the table for the given offset is in the cache */
156 l2_table
= seek_l2_table(s
, l2_offset
);
157 if (l2_table
!= NULL
)
160 /* not found: load a new entry in the least used one */
162 min_index
= l2_cache_new_entry(bs
);
163 l2_table
= s
->l2_cache
+ (min_index
<< s
->l2_bits
);
164 if (bdrv_pread(s
->hd
, l2_offset
, l2_table
, s
->l2_size
* sizeof(uint64_t)) !=
165 s
->l2_size
* sizeof(uint64_t))
167 s
->l2_cache_offsets
[min_index
] = l2_offset
;
168 s
->l2_cache_counts
[min_index
] = 1;
176 * Allocate a new l2 entry in the file. If l1_index points to an already
177 * used entry in the L2 table (i.e. we are doing a copy on write for the L2
178 * table) copy the contents of the old L2 table into the newly allocated one.
179 * Otherwise the new table is initialized with zeros.
183 static uint64_t *l2_allocate(BlockDriverState
*bs
, int l1_index
)
185 BDRVQcowState
*s
= bs
->opaque
;
187 uint64_t old_l2_offset
, tmp
;
188 uint64_t *l2_table
, l2_offset
;
190 old_l2_offset
= s
->l1_table
[l1_index
];
192 /* allocate a new l2 entry */
194 l2_offset
= alloc_clusters(bs
, s
->l2_size
* sizeof(uint64_t));
196 /* update the L1 entry */
198 s
->l1_table
[l1_index
] = l2_offset
| QCOW_OFLAG_COPIED
;
200 tmp
= cpu_to_be64(l2_offset
| QCOW_OFLAG_COPIED
);
201 if (bdrv_pwrite(s
->hd
, s
->l1_table_offset
+ l1_index
* sizeof(tmp
),
202 &tmp
, sizeof(tmp
)) != sizeof(tmp
))
205 /* allocate a new entry in the l2 cache */
207 min_index
= l2_cache_new_entry(bs
);
208 l2_table
= s
->l2_cache
+ (min_index
<< s
->l2_bits
);
210 if (old_l2_offset
== 0) {
211 /* if there was no old l2 table, clear the new table */
212 memset(l2_table
, 0, s
->l2_size
* sizeof(uint64_t));
214 /* if there was an old l2 table, read it from the disk */
215 if (bdrv_pread(s
->hd
, old_l2_offset
,
216 l2_table
, s
->l2_size
* sizeof(uint64_t)) !=
217 s
->l2_size
* sizeof(uint64_t))
220 /* write the l2 table to the file */
221 if (bdrv_pwrite(s
->hd
, l2_offset
,
222 l2_table
, s
->l2_size
* sizeof(uint64_t)) !=
223 s
->l2_size
* sizeof(uint64_t))
226 /* update the l2 cache entry */
228 s
->l2_cache_offsets
[min_index
] = l2_offset
;
229 s
->l2_cache_counts
[min_index
] = 1;
234 static int count_contiguous_clusters(uint64_t nb_clusters
, int cluster_size
,
235 uint64_t *l2_table
, uint64_t start
, uint64_t mask
)
238 uint64_t offset
= be64_to_cpu(l2_table
[0]) & ~mask
;
243 for (i
= start
; i
< start
+ nb_clusters
; i
++)
244 if (offset
+ i
* cluster_size
!= (be64_to_cpu(l2_table
[i
]) & ~mask
))
250 static int count_contiguous_free_clusters(uint64_t nb_clusters
, uint64_t *l2_table
)
254 while(nb_clusters
-- && l2_table
[i
] == 0)
260 /* The crypt function is compatible with the linux cryptoloop
261 algorithm for < 4 GB images. NOTE: out_buf == in_buf is
263 void encrypt_sectors(BDRVQcowState
*s
, int64_t sector_num
,
264 uint8_t *out_buf
, const uint8_t *in_buf
,
265 int nb_sectors
, int enc
,
274 for(i
= 0; i
< nb_sectors
; i
++) {
275 ivec
.ll
[0] = cpu_to_le64(sector_num
);
277 AES_cbc_encrypt(in_buf
, out_buf
, 512, key
,
286 static int qcow_read(BlockDriverState
*bs
, int64_t sector_num
,
287 uint8_t *buf
, int nb_sectors
)
289 BDRVQcowState
*s
= bs
->opaque
;
290 int ret
, index_in_cluster
, n
, n1
;
291 uint64_t cluster_offset
;
293 while (nb_sectors
> 0) {
295 cluster_offset
= get_cluster_offset(bs
, sector_num
<< 9, &n
);
296 index_in_cluster
= sector_num
& (s
->cluster_sectors
- 1);
297 if (!cluster_offset
) {
298 if (bs
->backing_hd
) {
299 /* read from the base image */
300 n1
= backing_read1(bs
->backing_hd
, sector_num
, buf
, n
);
302 ret
= bdrv_read(bs
->backing_hd
, sector_num
, buf
, n1
);
307 memset(buf
, 0, 512 * n
);
309 } else if (cluster_offset
& QCOW_OFLAG_COMPRESSED
) {
310 if (decompress_cluster(s
, cluster_offset
) < 0)
312 memcpy(buf
, s
->cluster_cache
+ index_in_cluster
* 512, 512 * n
);
314 ret
= bdrv_pread(s
->hd
, cluster_offset
+ index_in_cluster
* 512, buf
, n
* 512);
317 if (s
->crypt_method
) {
318 encrypt_sectors(s
, sector_num
, buf
, buf
, n
, 0,
319 &s
->aes_decrypt_key
);
329 static int copy_sectors(BlockDriverState
*bs
, uint64_t start_sect
,
330 uint64_t cluster_offset
, int n_start
, int n_end
)
332 BDRVQcowState
*s
= bs
->opaque
;
338 ret
= qcow_read(bs
, start_sect
+ n_start
, s
->cluster_data
, n
);
341 if (s
->crypt_method
) {
342 encrypt_sectors(s
, start_sect
+ n_start
,
344 s
->cluster_data
, n
, 1,
345 &s
->aes_encrypt_key
);
347 ret
= bdrv_write(s
->hd
, (cluster_offset
>> 9) + n_start
,
358 * For a given offset of the disk image, return cluster offset in
361 * on entry, *num is the number of contiguous clusters we'd like to
362 * access following offset.
364 * on exit, *num is the number of contiguous clusters we can read.
366 * Return 1, if the offset is found
367 * Return 0, otherwise.
371 uint64_t get_cluster_offset(BlockDriverState
*bs
, uint64_t offset
, int *num
)
373 BDRVQcowState
*s
= bs
->opaque
;
374 int l1_index
, l2_index
;
375 uint64_t l2_offset
, *l2_table
, cluster_offset
;
377 int index_in_cluster
, nb_available
, nb_needed
, nb_clusters
;
379 index_in_cluster
= (offset
>> 9) & (s
->cluster_sectors
- 1);
380 nb_needed
= *num
+ index_in_cluster
;
382 l1_bits
= s
->l2_bits
+ s
->cluster_bits
;
384 /* compute how many bytes there are between the offset and
385 * the end of the l1 entry
388 nb_available
= (1 << l1_bits
) - (offset
& ((1 << l1_bits
) - 1));
390 /* compute the number of available sectors */
392 nb_available
= (nb_available
>> 9) + index_in_cluster
;
394 if (nb_needed
> nb_available
) {
395 nb_needed
= nb_available
;
400 /* seek the the l2 offset in the l1 table */
402 l1_index
= offset
>> l1_bits
;
403 if (l1_index
>= s
->l1_size
)
406 l2_offset
= s
->l1_table
[l1_index
];
408 /* seek the l2 table of the given l2 offset */
413 /* load the l2 table in memory */
415 l2_offset
&= ~QCOW_OFLAG_COPIED
;
416 l2_table
= l2_load(bs
, l2_offset
);
417 if (l2_table
== NULL
)
420 /* find the cluster offset for the given disk offset */
422 l2_index
= (offset
>> s
->cluster_bits
) & (s
->l2_size
- 1);
423 cluster_offset
= be64_to_cpu(l2_table
[l2_index
]);
424 nb_clusters
= size_to_clusters(s
, nb_needed
<< 9);
426 if (!cluster_offset
) {
427 /* how many empty clusters ? */
428 c
= count_contiguous_free_clusters(nb_clusters
, &l2_table
[l2_index
]);
430 /* how many allocated clusters ? */
431 c
= count_contiguous_clusters(nb_clusters
, s
->cluster_size
,
432 &l2_table
[l2_index
], 0, QCOW_OFLAG_COPIED
);
435 nb_available
= (c
* s
->cluster_sectors
);
437 if (nb_available
> nb_needed
)
438 nb_available
= nb_needed
;
440 *num
= nb_available
- index_in_cluster
;
442 return cluster_offset
& ~QCOW_OFLAG_COPIED
;
448 * for a given disk offset, load (and allocate if needed)
451 * the l2 table offset in the qcow2 file and the cluster index
452 * in the l2 table are given to the caller.
456 static int get_cluster_table(BlockDriverState
*bs
, uint64_t offset
,
457 uint64_t **new_l2_table
,
458 uint64_t *new_l2_offset
,
461 BDRVQcowState
*s
= bs
->opaque
;
462 int l1_index
, l2_index
, ret
;
463 uint64_t l2_offset
, *l2_table
;
465 /* seek the the l2 offset in the l1 table */
467 l1_index
= offset
>> (s
->l2_bits
+ s
->cluster_bits
);
468 if (l1_index
>= s
->l1_size
) {
469 ret
= grow_l1_table(bs
, l1_index
+ 1);
473 l2_offset
= s
->l1_table
[l1_index
];
475 /* seek the l2 table of the given l2 offset */
477 if (l2_offset
& QCOW_OFLAG_COPIED
) {
478 /* load the l2 table in memory */
479 l2_offset
&= ~QCOW_OFLAG_COPIED
;
480 l2_table
= l2_load(bs
, l2_offset
);
481 if (l2_table
== NULL
)
485 free_clusters(bs
, l2_offset
, s
->l2_size
* sizeof(uint64_t));
486 l2_table
= l2_allocate(bs
, l1_index
);
487 if (l2_table
== NULL
)
489 l2_offset
= s
->l1_table
[l1_index
] & ~QCOW_OFLAG_COPIED
;
492 /* find the cluster offset for the given disk offset */
494 l2_index
= (offset
>> s
->cluster_bits
) & (s
->l2_size
- 1);
496 *new_l2_table
= l2_table
;
497 *new_l2_offset
= l2_offset
;
498 *new_l2_index
= l2_index
;
504 * alloc_compressed_cluster_offset
506 * For a given offset of the disk image, return cluster offset in
509 * If the offset is not found, allocate a new compressed cluster.
511 * Return the cluster offset if successful,
512 * Return 0, otherwise.
516 uint64_t alloc_compressed_cluster_offset(BlockDriverState
*bs
,
520 BDRVQcowState
*s
= bs
->opaque
;
522 uint64_t l2_offset
, *l2_table
, cluster_offset
;
525 ret
= get_cluster_table(bs
, offset
, &l2_table
, &l2_offset
, &l2_index
);
529 cluster_offset
= be64_to_cpu(l2_table
[l2_index
]);
530 if (cluster_offset
& QCOW_OFLAG_COPIED
)
531 return cluster_offset
& ~QCOW_OFLAG_COPIED
;
534 free_any_clusters(bs
, cluster_offset
, 1);
536 cluster_offset
= alloc_bytes(bs
, compressed_size
);
537 nb_csectors
= ((cluster_offset
+ compressed_size
- 1) >> 9) -
538 (cluster_offset
>> 9);
540 cluster_offset
|= QCOW_OFLAG_COMPRESSED
|
541 ((uint64_t)nb_csectors
<< s
->csize_shift
);
543 /* update L2 table */
545 /* compressed clusters never have the copied flag */
547 l2_table
[l2_index
] = cpu_to_be64(cluster_offset
);
548 if (bdrv_pwrite(s
->hd
,
549 l2_offset
+ l2_index
* sizeof(uint64_t),
551 sizeof(uint64_t)) != sizeof(uint64_t))
554 return cluster_offset
;
557 int alloc_cluster_link_l2(BlockDriverState
*bs
, uint64_t cluster_offset
,
560 BDRVQcowState
*s
= bs
->opaque
;
561 int i
, j
= 0, l2_index
, ret
;
562 uint64_t *old_cluster
, start_sect
, l2_offset
, *l2_table
;
564 if (m
->nb_clusters
== 0)
567 old_cluster
= qemu_malloc(m
->nb_clusters
* sizeof(uint64_t));
569 /* copy content of unmodified sectors */
570 start_sect
= (m
->offset
& ~(s
->cluster_size
- 1)) >> 9;
572 ret
= copy_sectors(bs
, start_sect
, cluster_offset
, 0, m
->n_start
);
577 if (m
->nb_available
& (s
->cluster_sectors
- 1)) {
578 uint64_t end
= m
->nb_available
& ~(uint64_t)(s
->cluster_sectors
- 1);
579 ret
= copy_sectors(bs
, start_sect
+ end
, cluster_offset
+ (end
<< 9),
580 m
->nb_available
- end
, s
->cluster_sectors
);
586 /* update L2 table */
587 if (!get_cluster_table(bs
, m
->offset
, &l2_table
, &l2_offset
, &l2_index
))
590 for (i
= 0; i
< m
->nb_clusters
; i
++) {
591 /* if two concurrent writes happen to the same unallocated cluster
592 * each write allocates separate cluster and writes data concurrently.
593 * The first one to complete updates l2 table with pointer to its
594 * cluster the second one has to do RMW (which is done above by
595 * copy_sectors()), update l2 table with its cluster pointer and free
596 * old cluster. This is what this loop does */
597 if(l2_table
[l2_index
+ i
] != 0)
598 old_cluster
[j
++] = l2_table
[l2_index
+ i
];
600 l2_table
[l2_index
+ i
] = cpu_to_be64((cluster_offset
+
601 (i
<< s
->cluster_bits
)) | QCOW_OFLAG_COPIED
);
604 if (bdrv_pwrite(s
->hd
, l2_offset
+ l2_index
* sizeof(uint64_t),
605 l2_table
+ l2_index
, m
->nb_clusters
* sizeof(uint64_t)) !=
606 m
->nb_clusters
* sizeof(uint64_t))
609 for (i
= 0; i
< j
; i
++)
610 free_any_clusters(bs
, be64_to_cpu(old_cluster
[i
]) & ~QCOW_OFLAG_COPIED
,
615 qemu_free(old_cluster
);
620 * alloc_cluster_offset
622 * For a given offset of the disk image, return cluster offset in
625 * If the offset is not found, allocate a new cluster.
627 * Return the cluster offset if successful,
628 * Return 0, otherwise.
632 uint64_t alloc_cluster_offset(BlockDriverState
*bs
,
634 int n_start
, int n_end
,
635 int *num
, QCowL2Meta
*m
)
637 BDRVQcowState
*s
= bs
->opaque
;
639 uint64_t l2_offset
, *l2_table
, cluster_offset
;
640 int nb_clusters
, i
= 0;
642 ret
= get_cluster_table(bs
, offset
, &l2_table
, &l2_offset
, &l2_index
);
646 nb_clusters
= size_to_clusters(s
, n_end
<< 9);
648 nb_clusters
= MIN(nb_clusters
, s
->l2_size
- l2_index
);
650 cluster_offset
= be64_to_cpu(l2_table
[l2_index
]);
652 /* We keep all QCOW_OFLAG_COPIED clusters */
654 if (cluster_offset
& QCOW_OFLAG_COPIED
) {
655 nb_clusters
= count_contiguous_clusters(nb_clusters
, s
->cluster_size
,
656 &l2_table
[l2_index
], 0, 0);
658 cluster_offset
&= ~QCOW_OFLAG_COPIED
;
664 /* for the moment, multiple compressed clusters are not managed */
666 if (cluster_offset
& QCOW_OFLAG_COMPRESSED
)
669 /* how many available clusters ? */
671 while (i
< nb_clusters
) {
672 i
+= count_contiguous_clusters(nb_clusters
- i
, s
->cluster_size
,
673 &l2_table
[l2_index
], i
, 0);
675 if(be64_to_cpu(l2_table
[l2_index
+ i
]))
678 i
+= count_contiguous_free_clusters(nb_clusters
- i
,
679 &l2_table
[l2_index
+ i
]);
681 cluster_offset
= be64_to_cpu(l2_table
[l2_index
+ i
]);
683 if ((cluster_offset
& QCOW_OFLAG_COPIED
) ||
684 (cluster_offset
& QCOW_OFLAG_COMPRESSED
))
689 /* allocate a new cluster */
691 cluster_offset
= alloc_clusters(bs
, nb_clusters
* s
->cluster_size
);
693 /* save info needed for meta data update */
695 m
->n_start
= n_start
;
696 m
->nb_clusters
= nb_clusters
;
699 m
->nb_available
= MIN(nb_clusters
<< (s
->cluster_bits
- 9), n_end
);
701 *num
= m
->nb_available
- n_start
;
703 return cluster_offset
;
706 static int decompress_buffer(uint8_t *out_buf
, int out_buf_size
,
707 const uint8_t *buf
, int buf_size
)
709 z_stream strm1
, *strm
= &strm1
;
712 memset(strm
, 0, sizeof(*strm
));
714 strm
->next_in
= (uint8_t *)buf
;
715 strm
->avail_in
= buf_size
;
716 strm
->next_out
= out_buf
;
717 strm
->avail_out
= out_buf_size
;
719 ret
= inflateInit2(strm
, -12);
722 ret
= inflate(strm
, Z_FINISH
);
723 out_len
= strm
->next_out
- out_buf
;
724 if ((ret
!= Z_STREAM_END
&& ret
!= Z_BUF_ERROR
) ||
725 out_len
!= out_buf_size
) {
733 int decompress_cluster(BDRVQcowState
*s
, uint64_t cluster_offset
)
735 int ret
, csize
, nb_csectors
, sector_offset
;
738 coffset
= cluster_offset
& s
->cluster_offset_mask
;
739 if (s
->cluster_cache_offset
!= coffset
) {
740 nb_csectors
= ((cluster_offset
>> s
->csize_shift
) & s
->csize_mask
) + 1;
741 sector_offset
= coffset
& 511;
742 csize
= nb_csectors
* 512 - sector_offset
;
743 ret
= bdrv_read(s
->hd
, coffset
>> 9, s
->cluster_data
, nb_csectors
);
747 if (decompress_buffer(s
->cluster_cache
, s
->cluster_size
,
748 s
->cluster_data
+ sector_offset
, csize
) < 0) {
751 s
->cluster_cache_offset
= coffset
;