[Qemu-devel] [RFC V7 03/32] qcow2: Add deduplication structures and fields.

["Benoît Canet" <benoit@irqsave.net>]

Signed-off-by: Benoit Canet <benoit@irqsave.net>
---
 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