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 <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

Looks good to me.

Reviewed-by: Julio Faracco <jcfaracco@gmail.com>

Em dom, 23 de dez de 2018 às 01:04, yuchenlin <npes87184@gmail.com>
escreveu:

> 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 <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
>
>
>

On Sun, Dec 23, 2018 at 10:59:37AM +0800, yuchenlin wrote:
> 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 <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;

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

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 <stefanha@redhat.com> 於 2019年1月2日 週三 下午7:49寫道：

> On Sun, Dec 23, 2018 at 10:59:37AM +0800, yuchenlin wrote:
> > 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 <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;
>
> 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
>

On Wed, Jan 02, 2019 at 08:20:54PM +0800, 林育辰 wrote:
> 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?

> 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?

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

Stefan Hajnoczi <stefanha@redhat.com> 於 2019年1月3日 週四 下午6:09寫道：

> On Wed, Jan 02, 2019 at 08:20:54PM +0800, 林育辰 wrote:
> > 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?
>

Sure!


>
> > 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?
>
> 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


> Stefan
>