dmg: fix binary search
PATCH 1/1 dmg: fix binary search
There is a possible hang in original binary searsh implemtation. 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
Quoted 9 lines · yuchenlin
There is a possible hang in original binary searsh implemtation. 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(-)
Do you have an example dmg file that triggers this bug?
Quoted 5 lines
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 ;
What if chunk1 = 0 and chunk2 = 1? chunk3 = 0 and the new chunk2 value would be 0xffffffff so the loop continues with out-of-bounds sectors[] accesses!
Hi Stefan,
I created a simple DMG file from MacOS to reproduce the problem:
https://bugs.launchpad.net/qemu/+bug/1809304
Em qua, 2 de jan de 2019 às 08:47, Stefan Hajnoczi <[email protected]> escreveu:
Quoted 33 lines · yuchenlin
Quoted 9 lines
There is a possible hang in original binary searsh implemtation. 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(-)Do you have an example dmg file that triggers this bug?
block/dmg.c static inline uint32_t search_chunk(BDRVDMGState
Quoted 5 lines
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 ;What if chunk1 = 0 and chunk2 = 1? chunk3 = 0 and the new chunk2 value would be
0xffffffffso the loop continues with out-of-bounds sectors[] accesses!
Quoted 6 lines · yuchenlin
There is a possible hang in original binary searsh implemtation. 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]>
Generally we ask that people use their full names for their Signed-off-by (for legal and copyright reasons) and not an alias.
If I am mistaken and your name is a mononym or written as a mononym, please forgive me and disregard.
Quoted 17 lines
--- block/dmg.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)block/dmg.c +1
-1@@ -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) {
block/dmg.c static inline uint32_t search_chunk(BDRVDMGState *s, uint64_t sector_num) · line 585
Quoted 10 lines
block/dmg.c +2
-2- 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 */
yuchenlin, did you see Stefan's response to your patch? Do you have any plans to send a follow-up?
--js
Quoted 8 lines · John Snow
Quoted 5 lines · yuchenlin
There is a possible hang in original binary searsh implemtation. That is if chunk1 = 4, chunk2 = 5, chunk3 = 4, and we go else case.
The chunk1 will be still 4, and so on.
Quoted 8 lines
Quoted 1 line
Signed-off-by yuchenlin <[email protected]>Generally we ask that people use their full names for their Signed-off-by (for legal and copyright reasons) and not an alias.
If I am mistaken and your name is a mononym or written as a mononym, please forgive me and disregard.
ah, just found the later threads. Still email backlogged, disregard.