Re: [Qemu-devel] [RFC V6 01/33] qcow2: Add deduplication to the qcow2 specification.

[Stefan Hajnoczi]

On Wed, Feb 06, 2013 at 01:31:34PM +0100, Benoît Canet wrote:
> Signed-off-by: Benoit Canet <address@hidden>
> ---
>  docs/specs/qcow2.txt |  105 
> +++++++++++++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 103 insertions(+), 2 deletions(-)
> 
> diff --git a/docs/specs/qcow2.txt b/docs/specs/qcow2.txt
> index 36a559d..8e52de1 100644
> --- a/docs/specs/qcow2.txt
> +++ b/docs/specs/qcow2.txt
> @@ -80,7 +80,12 @@ in the description of a field.
>                                  tables to repair refcounts before accessing 
> the
>                                  image.
>  
> -                    Bits 1-63:  Reserved (set to 0)
> +                    Bit 1:      Deduplication bit.  If this bit is set then
> +                                deduplication is used on this image.
> +                                L2 tables size 64KB is different from
> +                                cluster size 4KB.

Does that mean L2 table size is fixed at 64KB when dedup is enabled with
no way for the user to set it?

I guess this is okay but please document it explicitly.

> +
> +                    Bits 2-63:  Reserved (set to 0)
>  
>           80 -  87:  compatible_features
>                      Bitmask of compatible features. An implementation can
> @@ -116,6 +121,7 @@ be stored. Each extension has a structure like the 
> following:
>                          0x00000000 - End of the header extension area
>                          0xE2792ACA - Backing file format name
>                          0x6803f857 - Feature name table
> +                        0xCD8E819B - Deduplication
>                          other      - Unknown header extension, can be safely
>                                       ignored
>  
> @@ -159,6 +165,101 @@ the header extension data. Each entry look like this:
>                      terminated if it has full length)
>  
>  
> +== Deduplication ==
> +
> +The deduplication extension contains information concerning deduplication.
> +
> +    Byte   0 - 7:   Offset of the RAM deduplication table (RAM lookup)
> +
> +          8 - 11:   Size of the RAM deduplication table = number of L1 64-bit
> +                    pointers
> +
> +              12:   Hash algo enum field
> +                        0: SHA-256
> +                        1: SHA3
> +                        2: SKEIN-256
> +
> +              13:   Dedup strategies bitmap
> +                        0: RAM based hash lookup (always set to 1 for now)
> +                        1: Disk based hash lookup
> +                        2: Deduplication running if set to 1

I don't understand the purpose of bit 2.  Please document it further.

> +
> +        14 - 69:    Set to zero and reserved for future use
> +
> +Disk based lookup structure will be described in a future QCOW2 
> specification.

In that case please leave out the disk based lookup bit for now.  Add it
later when you submit the disk based hash lookup patches.

> +
> +== Deduplication table (RAM method) ==
> +
> +The deduplication table maps a physical offset to a data hash and
> +logical offset. It is used to permanently store the information to
> +do the deduplication. It is loaded at startup into a RAM based representation
> +used to do the lookups.
> +
> +The deduplication table contains 64-bit offsets to the level 2 deduplication
> +table blocks.
> +Each entry of these blocks contains a 32-byte SHA256 hash followed by the

Refine this to explain how Skein and SHA3 fit into the structure?

> +64-bit logical offset of the first encountered cluster having this hash.

I'm not sure if "first encountered" is always correct.  After the first
encountered logical cluster changes contents, what happens?

> +== Deduplication table schematic (RAM method) ==
> +
> +0       l1_dedup_index                                              Size
> +              |
> +|--------------------------------------------------------------------|
> +|             |                                                      |
> +|             |        L1 Deduplication table                        |
> +|             |                                                      |
> +|--------------------------------------------------------------------|
> +              |
> +              |
> +              |
> +0             |           l2_dedup_block_entries
> +              |
> +|---------------------------------|
> +|                                 |
> +|    L2 deduplication block       |
> +|                                 |
> +|                 l2_dedup_index  |
> +|---------------------------------|
> +                         |
> +         0               |              40
> +                         |
> +         |-------------------------------|
> +         |                               |
> +         |    Deduplication table entry  |
> +         |                               |
> +         |-------------------------------|
> +
> +
> +== Deduplication table entry description (RAM method) ==
> +
> +Each L2 deduplication table entry has the following structure:
> +
> +    Byte  0 - 31:   hash of data cluster
> +
> +         32 - 39:   Logical offset of first encountered block having
> +                    this hash
> +
> +== Deduplication table arithmetics (RAM method) ==
> +
> +cluster_size = 4096
> +dedup_block_size = 65536 * 5
> +l2_size = 65536 * 16 (16 factor is from the smaller cluster_size)
> +refcount_order must be >= 4
> +
> +Entries in the deduplication table are ordered by physical cluster index.
> +
> +The number of entries in an l2 deduplication table block is :
> +l2_dedup_block_entries = FLOOR(dedup_block_size / (32 + 8))
> +
> +The index in the level 1 deduplication table is :
> +l1_dedup_index = physical_cluster_index / l2_block_cluster_entries
> +
> +The index in the level 2 deduplication table is:
> +l2_dedup_index = physical_cluster_index % l2_block_cluster_entries
> +
> +The 16 remaining bytes in each l2 deduplication blocks are set to zero and
> +reserved for a future usage.
> +
>  == Host cluster management ==
>  
>  qcow2 manages the allocation of host clusters by maintaining a reference 
> count
> @@ -211,7 +312,7 @@ guest clusters to host clusters. They are called L1 and 
> L2 table.
>  
>  The L1 table has a variable size (stored in the header) and may use multiple
>  clusters, however it must be contiguous in the image file. L2 tables are
> -exactly one cluster in size.
> +exactly one cluster in size excepted for the deduplication case.

Please either define their size for the dedup case or refer to where in
the spec the value can be found.