[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [RFC V7 03/32] qcow2: Add deduplication structures and fiel
From: |
Benoît Canet |
Subject: |
[Qemu-devel] [RFC V7 03/32] qcow2: Add deduplication structures and fields. |
Date: |
Fri, 15 Mar 2013 15:49:17 +0100 |
Signed-off-by: Benoit Canet <address@hidden>
---
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
- [Qemu-devel] [RFC V7 00/32] QCOW2 deduplication core functionality, Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 02/32] qmp: Add DedupStatus enum., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 01/32] qcow2: Add deduplication to the qcow2 specification., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 03/32] qcow2: Add deduplication structures and fields.,
Benoît Canet <=
- [Qemu-devel] [RFC V7 04/32] qcow2: Add qcow2_de dup_read_missing_and_concatenate, Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 05/32] qcow2: Create a way to link to l2 tables when deduplicating., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 06/32] qcow2: Make qcow2_update_cluster_refcount public., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 09/32] qcow2: Do allocate on rewrite on the dedup case., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 07/32] qcow2: Add qcow2_dedup and related functions, Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 08/32] qcow2: Add qcow2_dedup_store_new_hashes., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 10/32] qcow2: Implement qcow2_compute_cluster_hash., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 12/32] qcow2: Makes qcow2_alloc_cluster_link_l2 mark to deduplicate clusters., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 11/32] qcow2: Add qcow2_dedup_grow_table and use it., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 13/32] qcow2: make the deduplication forget a cluster hash when a cluster is to dedupe, Benoît Canet, 2013/03/15