| Message ID | 20181221135803.9583-1-npes87184@gmail.com |
|---|---|
| State | New |
| Headers | show |
| Series | dmg: fix binary search | expand |
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!
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! >
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
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.
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 */
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(-)