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 <address@hidden> 於 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 <address@hidden>
> > ---
> >  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
>