[Qemu-devel] [PATCH] dmg: fix binary search

[Qemu-devel] [PATCH] dmg: fix binary search

[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 <npes87184@gmail.com>
---
 block/dmg.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/block/dmg.c b/block/dmg.c
index 50e91aef6d..0e05702f5d 100644
--- a/block/dmg.c
+++ b/block/dmg.c
@@ -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] dmg: fix binary search

[Stefan Hajnoczi]

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

On Fri, Dec 21, 2018 at 09:58:03PM +0800, yuchenlin wrote:
> 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 <npes87184@gmail.com>
> ---
>  block/dmg.c | 6 +++---
>  1 file changed, 3 insertions(+), 3 deletions(-)

Do you have an example dmg file that triggers this bug?

> diff --git a/block/dmg.c b/block/dmg.c
> index 50e91aef6d..0e05702f5d 100644
> --- a/block/dmg.c
> +++ b/block/dmg.c
> @@ -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!

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

Re: [Qemu-devel] [Qemu-block] [PATCH] dmg: fix binary search

[Julio Faracco]

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 <stefanha@redhat.com>
escreveu:

> On Fri, Dec 21, 2018 at 09:58:03PM +0800, yuchenlin wrote:
> > 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 <npes87184@gmail.com>
> > ---
> >  block/dmg.c | 6 +++---
> >  1 file changed, 3 insertions(+), 3 deletions(-)
>
> Do you have an example dmg file that triggers this bug?
>
> > diff --git a/block/dmg.c b/block/dmg.c
> > index 50e91aef6d..0e05702f5d 100644
> > --- a/block/dmg.c
> > +++ b/block/dmg.c
> > @@ -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!
>

Re: [Qemu-devel] [PATCH] dmg: fix binary search

[John Snow]

On 12/21/18 8:58 AM, yuchenlin wrote:
> 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 <npes87184@gmail.com>

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.

> ---
>  block/dmg.c | 6 +++---
>  1 file changed, 3 insertions(+), 3 deletions(-)
> 
> diff --git a/block/dmg.c b/block/dmg.c
> index 50e91aef6d..0e05702f5d 100644
> --- a/block/dmg.c
> +++ b/block/dmg.c
> @@ -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 */
> 

yuchenlin, did you see Stefan's response to your patch? Do you have any
plans to send a follow-up?

--js

Re: [Qemu-devel] [PATCH] dmg: fix binary search

[John Snow]

On 1/17/19 2:29 PM, John Snow wrote:
> 
> 
> On 12/21/18 8:58 AM, yuchenlin wrote:
>> 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 <npes87184@gmail.com>
> 
> 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.