Skip to contentSkip to conversation

dmg: fix binary search

PATCH Superseded yuchenlin 4 participants 5 messages Dec 21, 2018 – Jan 17, 2019 Block layer

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

yuchenlin

author
#0 lore raw

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
index 50e91aef6d..0e05702f5d 100644
@@ -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
#1 lore raw
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.

---
 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
index 50e91aef6d..0e05702f5d 100644

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!

#2 lore raw

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.

---
 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
index 50e91aef6d..0e05702f5d 100644
@@ -572,14 +572,14 @@ static inline uint32_t search_chunk(BDRVDMGState

*s, uint64_t sector_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 0xffffffff so the loop continues with out-of-bounds sectors[] accesses!

#3 lore raw
In reply to yuchenlin
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.

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
index 50e91aef6d..0e05702f5d 100644
@@ -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

#4 lore raw
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

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.