Skip to contentSkip to conversation

dmg: fixing reading in dmg

PATCH Applied yuchenlin 2 participants 5 messages Jan 3, 2019 – Jan 4, 2019 Block layer

lore
Share & tools
lore

yuchenlin

author
#0 lore raw

v3 cover dmg: fixing reading in dmg

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(-)
Signature · 1 line
2.17.1
author
#1 lore raw

PATCH v3 1/3 dmg: fix binary search

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.

---
 block/dmg.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)
block/dmg.c +7 -3
index 50e91aef6d..65a0140487 100644
@@ -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 */
 }
 
Signature · 1 line
2.17.1
author
#2 lore raw

PATCH v3 2/3 dmg: use enumeration type instead of hard coding number

In reply to yuchenlin
---
 block/dmg.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
block/dmg.c +2 -2
index 65a0140487..9758482131 100644
@@ -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;
         }
Signature · 1 line
2.17.1
author
#3 lore raw

PATCH v3 3/3 dmg: don't skip zero chunk

In reply to 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---]

---
 block/dmg.c | 19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)
block/dmg.c +12 -7
index 9758482131..351f2991a7 100644
@@ -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;
         }
Signature · 1 line
2.17.1
#4 lore raw
In reply to yuchenlin
Quoted 16 lines · 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

Quoted 11 lines

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(-)
Signature · 1 line
2.17.1

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

Stefan