[Qemu-devel] [PATCH v3 0/3] dmg: fixing reading in dmg

[Qemu-devel] [PATCH v3 0/3] dmg: fixing reading in dmg

[yuchenlin]

There are two bugs in dmg reading.

First, it may hang in binary search. this problem is solved by patch 1.
Second, because of lacking zero chunk table, reading zero sector will
return EIO. this problem is solved by patch 2 and 3.

Thanks

v2 -> v3:
* fix potential overflow (Thanks Stefan)
* add Reviewed tag in patch 2 and 3

v1 -> v2:
* fix typos in patch 1
* add patch 2 and patch 3

yuchenlin (3):
  dmg: fix binary search
  dmg: use enumeration type instead of hard coding number
  dmg: don't skip zero chunk

 block/dmg.c | 29 +++++++++++++++++++----------
 1 file changed, 19 insertions(+), 10 deletions(-)

-- 
2.17.1

[Qemu-devel] [PATCH v3 1/3] dmg: fix binary search

[yuchenlin]

There is a possible hang in original binary search implementation. That is
if chunk1 = 4, chunk2 = 5, chunk3 = 4, and we go else case.

The chunk1 will be still 4, and so on.

Signed-off-by: yuchenlin <npes87184@gmail.com>
---
 block/dmg.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

diff --git a/block/dmg.c b/block/dmg.c
index 50e91aef6d..65a0140487 100644
--- a/block/dmg.c
+++ b/block/dmg.c
@@ -572,16 +572,20 @@ static inline uint32_t search_chunk(BDRVDMGState *s, uint64_t sector_num)
 {
     /* binary search */
     uint32_t chunk1 = 0, chunk2 = s->n_chunks, chunk3;
-    while (chunk1 != chunk2) {
+    while (chunk1 <= chunk2) {
         chunk3 = (chunk1 + chunk2) / 2;
         if (s->sectors[chunk3] > sector_num) {
-            chunk2 = chunk3;
+            if (chunk3 == 0) {
+                goto err;
+            }
+            chunk2 = chunk3 - 1;
         } else if (s->sectors[chunk3] + s->sectorcounts[chunk3] > sector_num) {
             return chunk3;
         } else {
-            chunk1 = chunk3;
+            chunk1 = chunk3 + 1;
         }
     }
+err:
     return s->n_chunks; /* error */
 }
 
-- 
2.17.1

[Qemu-devel] [PATCH v3 2/3] dmg: use enumeration type instead of hard coding number

[yuchenlin]

Signed-off-by: yuchenlin <npes87184@gmail.com>
Reviewed-by: Julio Faracco <jcfaracco@gmail.com>
Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com>
---
 block/dmg.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/block/dmg.c b/block/dmg.c
index 65a0140487..9758482131 100644
--- a/block/dmg.c
+++ b/block/dmg.c
@@ -267,7 +267,7 @@ static int dmg_read_mish_block(BDRVDMGState *s, DmgHeaderState *ds,
 
         /* all-zeroes sector (type 2) does not need to be "uncompressed" and can
          * therefore be unbounded. */
-        if (s->types[i] != 2 && s->sectorcounts[i] > DMG_SECTORCOUNTS_MAX) {
+        if (s->types[i] != UDIG && s->sectorcounts[i] > DMG_SECTORCOUNTS_MAX) {
             error_report("sector count %" PRIu64 " for chunk %" PRIu32
                          " is larger than max (%u)",
                          s->sectorcounts[i], i, DMG_SECTORCOUNTS_MAX);
@@ -710,7 +710,7 @@ dmg_co_preadv(BlockDriverState *bs, uint64_t offset, uint64_t bytes,
         /* Special case: current chunk is all zeroes. Do not perform a memcpy as
          * s->uncompressed_chunk may be too small to cover the large all-zeroes
          * section. dmg_read_chunk is called to find s->current_chunk */
-        if (s->types[s->current_chunk] == 2) { /* all zeroes block entry */
+        if (s->types[s->current_chunk] == UDIG) { /* all zeroes block entry */
             qemu_iovec_memset(qiov, i * 512, 0, 512);
             continue;
         }
-- 
2.17.1

[Qemu-devel] [PATCH v3 3/3] dmg: don't skip zero chunk

[yuchenlin]

The dmg file has many tables which describe: "start from sector XXX to
sector XXX, the compression method is XXX and where the compressed data
resides on".

Each sector in the expanded file should be covered by a table. The table
will describe the offset of compressed data (or raw depends on the type)
in the dmg.

For example:

[-----------The expanded file------------]
[---bzip table ---]/* zeros */[---zlib---]
    ^
    | if we want to read this sector.

we will find bzip table which contains this sector, and get the
compressed data offset, read it from dmg, uncompress it, finally write to
expanded file.

If we skip zero chunk (table), some sector cannot find the table which
will cause search_chunk() return s->n_chunks, dmg_read_chunk() return -1
and finally causing dmg_co_preadv() return EIO.

See:

[-----------The expanded file------------]
[---bzip table ---]/* zeros */[---zlib---]
                    ^
                    | if we want to read this sector.

Oops, we cannot find the table contains it...

In the original implementation, we don't have zero table. When we try to
read sector inside the zero chunk. We will get EIO, and skip reading.

After this patch, we treat zero chunk the same as ignore chunk, it will
directly write zero and avoid some sector may not find the table.

After this patch:

[-----------The expanded file------------]
[---bzip table ---][--zeros--][---zlib---]

Signed-off-by: yuchenlin <npes87184@gmail.com>
Reviewed-by: Julio Faracco <jcfaracco@gmail.com>
Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com>
---
 block/dmg.c | 19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)

diff --git a/block/dmg.c b/block/dmg.c
index 9758482131..351f2991a7 100644
--- a/block/dmg.c
+++ b/block/dmg.c
@@ -130,7 +130,8 @@ static void update_max_chunk_size(BDRVDMGState *s, uint32_t chunk,
     case UDRW: /* copy */
         uncompressed_sectors = DIV_ROUND_UP(s->lengths[chunk], 512);
         break;
-    case UDIG: /* zero */
+    case UDZE: /* zero */
+    case UDIG: /* ignore */
         /* as the all-zeroes block may be large, it is treated specially: the
          * sector is not copied from a large buffer, a simple memset is used
          * instead. Therefore uncompressed_sectors does not need to be set. */
@@ -199,8 +200,9 @@ typedef struct DmgHeaderState {
 static bool dmg_is_known_block_type(uint32_t entry_type)
 {
     switch (entry_type) {
+    case UDZE:    /* zeros */
     case UDRW:    /* uncompressed */
-    case UDIG:    /* zeroes */
+    case UDIG:    /* ignore */
     case UDZO:    /* zlib */
         return true;
     case UDBZ:    /* bzip2 */
@@ -265,9 +267,10 @@ static int dmg_read_mish_block(BDRVDMGState *s, DmgHeaderState *ds,
         /* sector count */
         s->sectorcounts[i] = buff_read_uint64(buffer, offset + 0x10);
 
-        /* all-zeroes sector (type 2) does not need to be "uncompressed" and can
-         * therefore be unbounded. */
-        if (s->types[i] != UDIG && s->sectorcounts[i] > DMG_SECTORCOUNTS_MAX) {
+        /* all-zeroes sector (type UDZE and UDIG) does not need to be
+         * "uncompressed" and can therefore be unbounded. */
+        if (s->types[i] != UDZE && s->types[i] != UDIG
+            && s->sectorcounts[i] > DMG_SECTORCOUNTS_MAX) {
             error_report("sector count %" PRIu64 " for chunk %" PRIu32
                          " is larger than max (%u)",
                          s->sectorcounts[i], i, DMG_SECTORCOUNTS_MAX);
@@ -675,7 +678,8 @@ static inline int dmg_read_chunk(BlockDriverState *bs, uint64_t sector_num)
                 return -1;
             }
             break;
-        case UDIG: /* zero */
+        case UDZE: /* zeros */
+        case UDIG: /* ignore */
             /* see dmg_read, it is treated specially. No buffer needs to be
              * pre-filled, the zeroes can be set directly. */
             break;
@@ -710,7 +714,8 @@ dmg_co_preadv(BlockDriverState *bs, uint64_t offset, uint64_t bytes,
         /* Special case: current chunk is all zeroes. Do not perform a memcpy as
          * s->uncompressed_chunk may be too small to cover the large all-zeroes
          * section. dmg_read_chunk is called to find s->current_chunk */
-        if (s->types[s->current_chunk] == UDIG) { /* all zeroes block entry */
+        if (s->types[s->current_chunk] == UDZE
+            || s->types[s->current_chunk] == UDIG) { /* all zeroes block entry */
             qemu_iovec_memset(qiov, i * 512, 0, 512);
             continue;
         }
-- 
2.17.1

Re: [Qemu-devel] [PATCH v3 0/3] dmg: fixing reading in dmg

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 864 bytes --]

On Thu, Jan 03, 2019 at 07:46:57PM +0800, yuchenlin wrote:
> There are two bugs in dmg reading.
> 
> First, it may hang in binary search. this problem is solved by patch 1.
> Second, because of lacking zero chunk table, reading zero sector will
> return EIO. this problem is solved by patch 2 and 3.
> 
> Thanks
> 
> v2 -> v3:
> * fix potential overflow (Thanks Stefan)
> * add Reviewed tag in patch 2 and 3
> 
> v1 -> v2:
> * fix typos in patch 1
> * add patch 2 and patch 3
> 
> yuchenlin (3):
>   dmg: fix binary search
>   dmg: use enumeration type instead of hard coding number
>   dmg: don't skip zero chunk
> 
>  block/dmg.c | 29 +++++++++++++++++++----------
>  1 file changed, 19 insertions(+), 10 deletions(-)
> 
> -- 
> 2.17.1
> 

Thanks, applied to my block tree:
https://github.com/stefanha/qemu/commits/block

Stefan

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 455 bytes --]