[Qemu-devel] [PATCH 0/3] qed: Add support for zero clusters

[Qemu-devel] [PATCH 0/3] qed: Add support for zero clusters

[Stefan Hajnoczi]

This patch series adds zero data clusters to QED.  Clusters can be marked as
zero clusters to store zeroed regions in a space-efficient way.  The patch
never actually creates new zero clusters but includes the I/O path support code
to handle them if they are used by an image file.

Image streaming and copy-on-read take advantage of zero data clusters to avoid
expanding out zeroes from the backing file.  Those features are separate
patches that will come later but I'm presenting this patch now so we can get
this core QED image format feature in before doing the first QEMU release
containing QED.

The first patch fixes up an issue with the QED merge where '^' characters were
dropped from the QED specification.

The last two patches document and implement zero clusters, which were
originally implemented by Anthony Liguori <aliguori@us.ibm.com>.

[Qemu-devel] [PATCH 1/3] docs: Fix missing carets in QED specification

[Stefan Hajnoczi]

For some reason the carets ('^') in the QED specification disappeared.
This patch puts them back.

Signed-off-by: Stefan Hajnoczi <stefanha@linux.vnet.ibm.com>
---
 docs/specs/qed_spec.txt |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/docs/specs/qed_spec.txt b/docs/specs/qed_spec.txt
index 446b5a2..1d5fa87 100644
--- a/docs/specs/qed_spec.txt
+++ b/docs/specs/qed_spec.txt
@@ -33,7 +33,7 @@ All fields are little-endian.
  }
 
 Field descriptions:
-* ''cluster_size'' must be a power of 2 in range [212, 226].
+* ''cluster_size'' must be a power of 2 in range [2^12, 2^26].
 * ''table_size'' must be a power of 2 in range [1, 16].
 * ''header_size'' is the number of clusters used by the header and any additional information stored before regular clusters.
 * ''features'', ''compat_features'', and ''autoclear_features'' are file format extension bitmaps.  They work as follows:
@@ -90,7 +90,7 @@ L1, L2, and data cluster offsets must be aligned to header.cluster_size.  The fo
 ===Data cluster offsets===
 * 0 - unallocated.  The data cluster is not yet allocated.
 
-Future format extensions may wish to store per-offset information.  The least significant 12 bits of an offset are reserved for this purpose and must be set to zero.  Image files with cluster_size > 212 will have more unused bits which should also be zeroed.
+Future format extensions may wish to store per-offset information.  The least significant 12 bits of an offset are reserved for this purpose and must be set to zero.  Image files with cluster_size > 2^12 will have more unused bits which should also be zeroed.
 
 ===Unallocated L2 tables and data clusters===
 Reads to an unallocated area of the image file access the backing file.  If there is no backing file, then zeroes are produced.  The backing file may be smaller than the image file and reads of unallocated areas beyond the end of the backing file produce zeroes.
-- 
1.7.2.3

[Qemu-devel] [PATCH 2/3] docs: Describe zero data clusters in QED specification

[Stefan Hajnoczi]

Zero data clusters are a space-efficient way of storing zeroed regions
of the image.

Signed-off-by: Stefan Hajnoczi <stefanha@linux.vnet.ibm.com>
---
 docs/specs/qed_spec.txt |    8 ++++++++
 1 files changed, 8 insertions(+), 0 deletions(-)

diff --git a/docs/specs/qed_spec.txt b/docs/specs/qed_spec.txt
index 1d5fa87..7982e05 100644
--- a/docs/specs/qed_spec.txt
+++ b/docs/specs/qed_spec.txt
@@ -89,6 +89,7 @@ L1, L2, and data cluster offsets must be aligned to header.cluster_size.  The fo
 
 ===Data cluster offsets===
 * 0 - unallocated.  The data cluster is not yet allocated.
+* 1 - zero.  The data cluster contents are all zeroes and no cluster is allocated.
 
 Future format extensions may wish to store per-offset information.  The least significant 12 bits of an offset are reserved for this purpose and must be set to zero.  Image files with cluster_size > 2^12 will have more unused bits which should also be zeroed.
 
@@ -97,6 +98,13 @@ Reads to an unallocated area of the image file access the backing file.  If ther
 
 Writes to an unallocated area cause a new data clusters to be allocated, and a new L2 table if that is also unallocated.  The new data cluster is populated with data from the backing file (or zeroes if no backing file) and the data being written.
 
+===Zero data clusters===
+Zero data clusters are a space-efficient way of storing zeroed regions of the image.
+
+Reads to a zero data cluster produce zeroes.  Note that the difference between an unallocated and a zero data cluster is that zero data clusters stop the reading of contents from the backing file.
+
+Writes to a zero data cluster cause a new data cluster to be allocated.  The new data cluster is populated with zeroes and the data being written.
+
 ===Logical offset translation===
 Logical offsets are translated into cluster offsets as follows:
 
-- 
1.7.2.3

[Qemu-devel] [PATCH 3/3] qed: Add support for zero clusters

[Stefan Hajnoczi]

From: Anthony Liguori <aliguori@us.ibm.com>

Zero clusters are similar to unallocated clusters except instead of reading
their value from a backing file when one is available, the cluster is always
read as zero.

This implements read support only.  At this stage, QED will never write a
zero cluster.

Signed-off-by: Anthony Liguori <aliguori@us.ibm.com>
Signed-off-by: Stefan Hajnoczi <stefanha@linux.vnet.ibm.com>
---
 block/qed-check.c   |    5 +++--
 block/qed-cluster.c |   31 +++++++++++++++++++++----------
 block/qed.c         |   21 ++++++++++++++++-----
 block/qed.h         |   26 ++++++++++++++++++++++++++
 4 files changed, 66 insertions(+), 17 deletions(-)

diff --git a/block/qed-check.c b/block/qed-check.c
index 4600932..ea4ebc8 100644
--- a/block/qed-check.c
+++ b/block/qed-check.c
@@ -72,7 +72,8 @@ static unsigned int qed_check_l2_table(QEDCheck *check, QEDTable *table)
     for (i = 0; i < s->table_nelems; i++) {
         uint64_t offset = table->offsets[i];
 
-        if (!offset) {
+        if (qed_offset_is_unalloc_cluster(offset) ||
+            qed_offset_is_zero_cluster(offset)) {
             continue;
         }
 
@@ -111,7 +112,7 @@ static int qed_check_l1_table(QEDCheck *check, QEDTable *table)
         unsigned int num_invalid_l2;
         uint64_t offset = table->offsets[i];
 
-        if (!offset) {
+        if (qed_offset_is_unalloc_cluster(offset)) {
             continue;
         }
 
diff --git a/block/qed-cluster.c b/block/qed-cluster.c
index 0ec864b..3e19ad1 100644
--- a/block/qed-cluster.c
+++ b/block/qed-cluster.c
@@ -23,7 +23,8 @@
  * @n:              Maximum number of clusters
  * @offset:         Set to first cluster offset
  *
- * This function scans tables for contiguous allocated or free clusters.
+ * This function scans tables for contiguous clusters.  A contiguous run of
+ * clusters may be allocated, unallocated, or zero.
  */
 static unsigned int qed_count_contiguous_clusters(BDRVQEDState *s,
                                                   QEDTable *table,
@@ -38,9 +39,14 @@ static unsigned int qed_count_contiguous_clusters(BDRVQEDState *s,
     *offset = last;
 
     for (i = index + 1; i < end; i++) {
-        if (last == 0) {
-            /* Counting free clusters */
-            if (table->offsets[i] != 0) {
+        if (qed_offset_is_unalloc_cluster(last)) {
+            /* Counting unallocated clusters */
+            if (!qed_offset_is_unalloc_cluster(table->offsets[i])) {
+                break;
+            }
+        } else if (qed_offset_is_zero_cluster(last)) {
+            /* Counting zero clusters */
+            if (!qed_offset_is_zero_cluster(table->offsets[i])) {
                 break;
             }
         } else {
@@ -87,14 +93,19 @@ static void qed_find_cluster_cb(void *opaque, int ret)
     n = qed_count_contiguous_clusters(s, request->l2_table->table,
                                       index, n, &offset);
 
-    ret = offset ? QED_CLUSTER_FOUND : QED_CLUSTER_L2;
-    len = MIN(find_cluster_cb->len, n * s->header.cluster_size -
-              qed_offset_into_cluster(s, find_cluster_cb->pos));
-
-    if (offset && !qed_check_cluster_offset(s, offset)) {
+    if (qed_offset_is_unalloc_cluster(offset)) {
+        ret = QED_CLUSTER_L2;
+    } else if (qed_offset_is_zero_cluster(offset)) {
+        ret = QED_CLUSTER_ZERO;
+    } else if (qed_check_cluster_offset(s, offset)) {
+        ret = QED_CLUSTER_FOUND;
+    } else {
         ret = -EINVAL;
     }
 
+    len = MIN(find_cluster_cb->len, n * s->header.cluster_size -
+              qed_offset_into_cluster(s, find_cluster_cb->pos));
+
 out:
     find_cluster_cb->cb(find_cluster_cb->opaque, ret, offset, len);
     qemu_free(find_cluster_cb);
@@ -132,7 +143,7 @@ void qed_find_cluster(BDRVQEDState *s, QEDRequest *request, uint64_t pos,
     len = MIN(len, (((pos >> s->l1_shift) + 1) << s->l1_shift) - pos);
 
     l2_offset = s->l1_table->offsets[qed_l1_index(s, pos)];
-    if (!l2_offset) {
+    if (qed_offset_is_unalloc_cluster(l2_offset)) {
         cb(opaque, QED_CLUSTER_L1, 0, len);
         return;
     }
diff --git a/block/qed.c b/block/qed.c
index 085c4f2..056e852 100644
--- a/block/qed.c
+++ b/block/qed.c
@@ -560,7 +560,7 @@ static void qed_is_allocated_cb(void *opaque, int ret, uint64_t offset, size_t l
 {
     QEDIsAllocatedCB *cb = opaque;
     *cb->pnum = len / BDRV_SECTOR_SIZE;
-    cb->is_allocated = ret == QED_CLUSTER_FOUND;
+    cb->is_allocated = (ret == QED_CLUSTER_FOUND || ret == QED_CLUSTER_ZERO);
 }
 
 static int bdrv_qed_is_allocated(BlockDriverState *bs, int64_t sector_num,
@@ -732,7 +732,10 @@ static void qed_copy_from_backing_file(BDRVQEDState *s, uint64_t pos,
  * @table:          L2 table
  * @index:          First cluster index
  * @n:              Number of contiguous clusters
- * @cluster:        First cluster byte offset in image file
+ * @cluster:        First cluster offset
+ *
+ * The cluster offset may be an allocated byte offset in the image file, the
+ * zero cluster marker, or the unallocated cluster marker.
  */
 static void qed_update_l2_table(BDRVQEDState *s, QEDTable *table, int index,
                                 unsigned int n, uint64_t cluster)
@@ -740,7 +743,10 @@ static void qed_update_l2_table(BDRVQEDState *s, QEDTable *table, int index,
     int i;
     for (i = index; i < index + n; i++) {
         table->offsets[i] = cluster;
-        cluster += s->header.cluster_size;
+        if (!qed_offset_is_unalloc_cluster(cluster) &&
+            !qed_offset_is_zero_cluster(cluster)) {
+            cluster += s->header.cluster_size;
+        }
     }
 }
 
@@ -1052,6 +1058,7 @@ static void qed_aio_write_data(void *opaque, int ret,
 
     case QED_CLUSTER_L2:
     case QED_CLUSTER_L1:
+    case QED_CLUSTER_ZERO:
         qed_aio_write_alloc(acb, len);
         break;
 
@@ -1091,8 +1098,12 @@ static void qed_aio_read_data(void *opaque, int ret,
 
     qemu_iovec_copy(&acb->cur_qiov, acb->qiov, acb->qiov_offset, len);
 
-    /* Handle backing file and unallocated sparse hole reads */
-    if (ret != QED_CLUSTER_FOUND) {
+    /* Handle zero cluster and backing file reads */
+    if (ret == QED_CLUSTER_ZERO) {
+        qemu_iovec_memset(&acb->cur_qiov, 0, acb->cur_qiov.size);
+        qed_aio_next_io(acb, 0);
+        return;
+    } else if (ret != QED_CLUSTER_FOUND) {
         qed_read_backing_file(s, acb->cur_pos, &acb->cur_qiov,
                               qed_aio_next_io, acb);
         return;
diff --git a/block/qed.h b/block/qed.h
index 2925e37..3e1ab84 100644
--- a/block/qed.h
+++ b/block/qed.h
@@ -161,6 +161,7 @@ typedef struct {
 
 enum {
     QED_CLUSTER_FOUND,         /* cluster found */
+    QED_CLUSTER_ZERO,          /* zero cluster found */
     QED_CLUSTER_L2,            /* cluster missing in L2 */
     QED_CLUSTER_L1,            /* cluster missing in L1 */
 };
@@ -298,4 +299,29 @@ static inline bool qed_check_table_offset(BDRVQEDState *s, uint64_t offset)
            qed_check_cluster_offset(s, end_offset);
 }
 
+static inline bool qed_offset_is_cluster_aligned(BDRVQEDState *s,
+                                                 uint64_t offset)
+{
+    if (qed_offset_into_cluster(s, offset)) {
+        return false;
+    }
+    return true;
+}
+
+static inline bool qed_offset_is_unalloc_cluster(uint64_t offset)
+{
+    if (offset == 0) {
+        return true;
+    }
+    return false;
+}
+
+static inline bool qed_offset_is_zero_cluster(uint64_t offset)
+{
+    if (offset == 1) {
+        return true;
+    }
+    return false;
+}
+
 #endif /* BLOCK_QED_H */
-- 
1.7.2.3

Re: [Qemu-devel] [PATCH 0/3] qed: Add support for zero clusters

[Kevin Wolf]

Am 17.12.2010 16:58, schrieb Stefan Hajnoczi:
> This patch series adds zero data clusters to QED.  Clusters can be marked as
> zero clusters to store zeroed regions in a space-efficient way.  The patch
> never actually creates new zero clusters but includes the I/O path support code
> to handle them if they are used by an image file.
> 
> Image streaming and copy-on-read take advantage of zero data clusters to avoid
> expanding out zeroes from the backing file.  Those features are separate
> patches that will come later but I'm presenting this patch now so we can get
> this core QED image format feature in before doing the first QEMU release
> containing QED.
> 
> The first patch fixes up an issue with the QED merge where '^' characters were
> dropped from the QED specification.
> 
> The last two patches document and implement zero clusters, which were
> originally implemented by Anthony Liguori <aliguori@us.ibm.com>.

Thanks, applied all to the block branch.

Kevin