dmg: fixing reading in dmg
v2 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. thie problem is solved by patch 2 and 3.
Thanks
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 | 25 +++++++++++++++---------- 1 file changed, 15 insertions(+), 10 deletions(-)
Signature · 1 line
2.17.1
PATCH v2 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 | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)
block/dmg.c +3 -3
@@ -572,14 +572,14 @@ 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; + chunk2 = chunk3 -1 ; }else if (s->sectors[chunk3] + s->sectorcounts[chunk3] > sector_num) {return chunk3; }else { - chunk1 = chunk3; + chunk1 = chunk3 +1 ; } }return s->n_chunks;/* error */
Signature · 1 line
2.17.1
Re: [Qemu-devel] [PATCH v2 1/3] dmg: fix binary search
Looks good to me.
Em dom, 23 de dez de 2018 às 01:04, yuchenlin <[email protected]> escreveu:
Quoted 39 lines
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 <[email protected]>--- block/dmg.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)block/dmg.c +3
-3@@ -572,14 +572,14 @@ 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; + chunk2 = chunk3 -1 ; }else if (s->sectors[chunk3] + s->sectorcounts[chunk3] > sector_num) {return chunk3; }else { - chunk1 = chunk3; + chunk1 = chunk3 +1 ; }} return s->n_chunks; /* error */--
2.17.1
Re: [Qemu-devel] [PATCH v2 1/3] dmg: fix binary search
In reply to yuchenlinQuoted 15 lines · 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 <[email protected]>--- block/dmg.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)block/dmg.c +0
-0
block/dmg.c static inline uint32_t search_chunk(BDRVDMGState *s, uint64_t sector_num) · line 578
Quoted 9 lines
block/dmg.c +2
-2@@ -572,14 +572,14 @@ 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; + chunk2 = chunk3 -1 ;
Question from the previous email you sent:
What happens when chunk1 = 0, chunk2 = 1, and chunk3 = 0? This would cause out-of-bounds sectors[] accesses.
Stefan
Re: [Qemu-devel] [PATCH v2 1/3] dmg: fix binary search
Hi, Stefan
Thank you for your reviewing.
This series is focus on fixing bug #1809304 (see:
https://bugs.launchpad.net/qemu/+bug/1809304).
There is an example dmg file in #1809304 which will trigger this bug.
About your case, I think we can simply check whether chunk3 is zero before we decrease it.
if s->sectors[chunk3] > sector_num and chunk3 is zero (i.e. s->sectors[0] > sector_num), it means we cannot find the table contains sector_num. We can return s->n_chunks (error) directly.
What do you think?
Thanks,
Yu-Chen
Stefan Hajnoczi <[email protected]> 於 2019年1月2日 週三 下午7:49寫道:
Quoted 35 lines · yuchenlin
Quoted 1 line
There is a possible hang in original binary search implementation. That
is
block/dmg.c static inline uint32_t search_chunk(BDRVDMGState
Quoted 14 lines
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 <[email protected]>--- block/dmg.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)block/dmg.c +0
-0@@ -572,14 +572,14 @@ static inline uint32_t search_chunk(BDRVDMGState*s,
uint64_tsector_num)block/dmg.c static inline uint32_t search_chunk(BDRVDMGState *s, uint64_t sector_num) · line 578
Quoted 9 lines
block/dmg.c +2
-2{/* 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; + chunk2 = chunk3 -1 ;Question from the previous email you sent:
What happens when chunk1 = 0, chunk2 = 1, and chunk3 = 0? This would cause out-of-bounds sectors[] accesses.
Stefan
Re: [Qemu-devel] [PATCH v2 1/3] dmg: fix binary search
Quoted 3 lines · 林育辰
This series is focus on fixing bug #1809304 (see:
https://bugs.launchpad.net/qemu/+bug/1809304).
There is an example dmg file in #1809304 which will trigger this bug.
Thanks. It would be great to include a tiny dmg file in tests/qemu-iotests/sample_images/ and add a test case for it.
The file should be small (kilobytes, not megabytes) and must be redistributable (no proprietary content or even GPL software, which requires distributing source code).
Do you have time to do that?
Quoted 7 lines
About your case, I think we can simply check whether chunk3 is zero before we decrease it.
if s->sectors[chunk3] >sector_numand chunk3 is zero (i.e. s->sectors[0] >sector_num), it means we cannot find the table containssector_num. We can returns->n_chunks(error) directly.What do you think?
Sounds good. We have to assume that the file contents are invalid and handle all cases.
I'll review the next revision of your patch. Thanks!
Stefan
Re: [Qemu-devel] [PATCH v2 1/3] dmg: fix binary search
Stefan Hajnoczi <[email protected]> 於 2019年1月3日 週四 下午6:09寫道:
Quoted 5 lines · 林育辰
Quoted 3 lines
This series is focus on fixing bug #1809304 (see:
https://bugs.launchpad.net/qemu/+bug/1809304).
There is an example dmg file in #1809304 which will trigger this bug.
Quoted 9 lines
Thanks. It would be great to include a tiny dmg file in tests/qemu-iotests/sample_images/ and add a test case for it.
The file should be small (kilobytes, not megabytes) and must be redistributable (no proprietary content or even GPL software, which requires distributing source code).
Do you have time to do that?
Sure!
Quoted 9 lines
Quoted 2 lines
About your case, I think we can simply check whether chunk3 is zero
before
Quoted 2 lines
we decrease it.
if s->sectors[chunk3] >sector_numand chunk3 is zero (i.e.s->sectors[0] >
Quoted 3 lines
sector_num), it means we cannot find the table containssector_num. We can returns->n_chunks(error) directly.
Quoted 7 lines
Quoted 1 line
What do you think?
Sounds good. We have to assume that the file contents are invalid and handle all cases.
I'll review the next revision of your patch. Thanks!
Thanks!
Yu-Chen Lin
Quoted 2 lines
Stefan
PATCH v2 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
@@ -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 );
@@ -706,7 +706,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
Re: [Qemu-devel] [PATCH v2 2/3] dmg: use enumeration type instead of hard coding number
Looks good to me.
Em dom, 23 de dez de 2018 às 01:03, yuchenlin <[email protected]> escreveu:
Quoted 41 lines
Signed-off-by yuchenlin <[email protected]>--- block/dmg.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)block/dmg.c +0
-0@@ -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);block/dmg.c +0
-0@@ -706,7 +706,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_chunkmay be too small to cover the large
all-zeroes
* section.dmg_read_chunkis called to finds->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
Re: [Qemu-devel] [PATCH v2 2/3] dmg: use enumeration type instead of hard coding number
In reply to yuchenlinQuoted 4 lines · yuchenlin
Signed-off-by yuchenlin <[email protected]>--- block/dmg.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
PATCH v2 3/3 dmg: don't skip zero chunk
In reply to yuchenlinThe 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
@@ -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 );
@@ -671,7 +674,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 ;
@@ -706,7 +710,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
Re: [Qemu-devel] [PATCH v2 3/3] dmg: don't skip zero chunk
Looks good to me.
Em dom, 23 de dez de 2018 às 01:03, yuchenlin <[email protected]> escreveu:
Quoted 126 lines
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()returns->n_chunks,dmg_read_chunk()return -1 and finally causingdmg_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 <[email protected]>--- block/dmg.c | 19 ++++++++++++------- 1 file changed, 12 insertions(+), 7 deletions(-)block/dmg.c +2
-1@@ -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. Thereforeuncompressed_sectorsdoes not need to be
set. */block/dmg.c +2
-2@@ -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
block/dmg.c +0
-2-* therefore be unbounded. */ - if (s->types[i] != UDIG && s->sectorcounts[i] >
DMG_SECTORCOUNTS_MAX) {block/dmg.c +6
-1+/* 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 );@@ -671,7 +674,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;block/dmg.c +0
-0@@ -706,7 +710,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_chunkmay be too small to cover the large
all-zeroes
* section.dmg_read_chunkis called to finds->current_chunk*/
- if (s->types[s->current_chunk] == UDIG) { /* all zeroes block
entry */block/dmg.c +2
-0+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 v2 3/3] dmg: don't skip zero chunk
In reply to yuchenlinQuoted 40 lines · 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()returns->n_chunks,dmg_read_chunk()return -1 and finally causingdmg_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:
Quoted 7 lines
[-----------The expanded file------------]
[---bzip table ---][--zeros--][---zlib---]Signed-off-by yuchenlin <[email protected]>--- block/dmg.c | 19 ++++++++++++------- 1 file changed, 12 insertions(+), 7 deletions(-)
The series looks good to me.
I tested with existing DMGs and DMGs that I created by myself. Both are working fine now.
Em dom, 23 de dez de 2018 às 01:01, yuchenlin <[email protected]> escreveu:
Quoted 25 lines
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. thie problem is solved by patch 2 and 3.
Thanks
v1 - >v2:
* fix typos in patch 1
* add patch 2 and patch 3yuchenlin (3):
dmg: fix binary search
dmg: use enumeration type instead of hard coding number
dmg: don't skip zero chunkblock/dmg.c | 25 +++++++++++++++---------- 1 file changed, 15 insertions(+), 10 deletions(-)--
2.17.1