From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([208.118.235.92]:36419) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UGVwr-0006Mj-Ij for qemu-devel@nongnu.org; Fri, 15 Mar 2013 10:49:36 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UGVwo-0003yn-9e for qemu-devel@nongnu.org; Fri, 15 Mar 2013 10:49:33 -0400 Received: from nodalink.pck.nerim.net ([62.212.105.220]:59527 helo=paradis.irqsave.net) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UGVwn-0003ya-Me for qemu-devel@nongnu.org; Fri, 15 Mar 2013 10:49:30 -0400 From: =?UTF-8?q?Beno=C3=AEt=20Canet?= Date: Fri, 15 Mar 2013 15:49:17 +0100 Message-Id: <1363358986-8360-4-git-send-email-benoit@irqsave.net> In-Reply-To: <1363358986-8360-1-git-send-email-benoit@irqsave.net> References: <1363358986-8360-1-git-send-email-benoit@irqsave.net> Subject: [Qemu-devel] [RFC V7 03/32] qcow2: Add deduplication structures and fields. List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org Cc: kwolf@redhat.com, =?UTF-8?q?Beno=C3=AEt=20Canet?= , stefanha@redhat.com Signed-off-by: Benoit Canet --- block/qcow2.h | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 76 insertions(+), 1 deletion(-) diff --git a/block/qcow2.h b/block/qcow2.h index 718b52b..87da573 100644 --- a/block/qcow2.h +++ b/block/qcow2.h @@ -43,6 +43,10 @@ #define QCOW_OFLAG_COPIED (1LL << 63) /* indicate that the cluster is compressed (they never have the copied flag) */ #define QCOW_OFLAG_COMPRESSED (1LL << 62) +/* indicate that the cluster must be processed when deduplication restarts + * also indicate that the on disk dedup hash must be ignored and discarded + */ +#define QCOW_OFLAG_PENDING_DEDUP (1LL << 61) /* The cluster reads as all zeros */ #define QCOW_OFLAG_ZERO (1LL << 0) @@ -56,7 +60,64 @@ /* Must be at least 4 to cover all cases of refcount table growth */ #define REFCOUNT_CACHE_SIZE 4 +#define DEDUP_CACHE_SIZE 4 #define DEFAULT_CLUSTER_SIZE 65536 +#define DEFAULT_DEDUP_CLUSTER_SIZE 4096 + +#define HASH_LENGTH 32 + +/* indicate that this cluster refcount has reached its maximum value */ +#define QCOW_DEDUP_FLAG_HALF_MAX_REFCOUNT (1LL << 61) +/* indicate that the hash structure is empty and miss offset */ +#define QCOW_DEDUP_FLAG_EMPTY (1LL << 62) + +#define QCOW_DEDUP_STRATEGY_RUNNING (1 << 0) +#define QCOW_DEDUP_STRATEGY_RAM (1 << 1) + +typedef enum { + QCOW_HASH_SHA256 = 0, + QCOW_HASH_SHA3 = 1, + QCOW_HASH_SKEIN = 2, +} QCowHashAlgo; + +typedef struct { + uint8_t data[HASH_LENGTH]; /* 32 bytes hash of a given cluster */ +} QCowHash; + +/* Used to keep a single precomputed hash between the calls of the dedup + * function + */ +typedef struct { + QCowHash hash; + bool reuse; /* The main deduplication function can set this field to + * true before exiting to avoid computing the same hash + * twice. It's a speed optimization. + */ +} QcowPersistentHash; + +/* deduplication node */ +typedef struct { + QCowHash hash; + uint64_t physical_sect; /* where the cluster is stored on disk */ + uint64_t first_logical_sect; /* logical sector of the first occurrence of + * this cluster + */ +} QCowHashNode; + +/* Undedupable hashes that must be written later to disk */ +typedef struct QCowHashElement { + QCowHash hash; + QTAILQ_ENTRY(QCowHashElement) next; +} QCowHashElement; + +typedef struct { + QcowPersistentHash phash; /* contains a hash persisting between calls of + * qcow2_dedup() + */ + QTAILQ_HEAD(, QCowHashElement) undedupables; + uint64_t nb_clusters_processed; + uint64_t nb_undedupable_sectors; +} QCowDedupState; typedef struct QCowHeader { uint32_t magic; @@ -114,8 +175,10 @@ enum { enum { QCOW2_INCOMPAT_DIRTY_BITNR = 0, QCOW2_INCOMPAT_DIRTY = 1 << QCOW2_INCOMPAT_DIRTY_BITNR, + QCOW2_INCOMPAT_DEDUP_BITNR = 1, + QCOW2_INCOMPAT_DEDUP = 1 << QCOW2_INCOMPAT_DEDUP_BITNR, - QCOW2_INCOMPAT_MASK = QCOW2_INCOMPAT_DIRTY, + QCOW2_INCOMPAT_MASK = QCOW2_INCOMPAT_DIRTY | QCOW2_INCOMPAT_DEDUP, }; /* Compatible feature bits */ @@ -138,6 +201,7 @@ typedef struct BDRVQcowState { int cluster_sectors; int l2_bits; int l2_size; + int hash_block_size; int l1_size; int l1_vm_state_index; int csize_shift; @@ -148,6 +212,7 @@ typedef struct BDRVQcowState { Qcow2Cache* l2_table_cache; Qcow2Cache* refcount_block_cache; + Qcow2Cache *dedup_cluster_cache; uint8_t *cluster_cache; uint8_t *cluster_data; @@ -160,6 +225,16 @@ typedef struct BDRVQcowState { int64_t free_cluster_index; int64_t free_byte_offset; + bool has_dedup; + DedupStatus dedup_status; + QCowHashAlgo dedup_hash_algo; + Coroutine *dedup_resume_co; + int dedup_co_delay; + uint64_t *dedup_table; + uint64_t dedup_table_offset; + size_t dedup_table_size; + GTree *dedup_tree_by_hash; + CoMutex lock; uint32_t crypt_method; /* current crypt method, 0 if no key yet */ -- 1.7.10.4