Re: [Qemu-devel] [PATCH v2 1/3] dmg: fix binary search
Stefan Hajnoczi 於 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 >
Re: [Qemu-devel] [PATCH v2 1/3] dmg: fix binary search
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 signature.asc Description: PGP signature
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 於 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
> > ---
> > 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
>
Re: [Qemu-devel] [PATCH v2 1/3] dmg: fix binary search
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
> ---
> 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
signature.asc
Description: PGP signature
Re: [Qemu-devel] [PATCH v2 1/3] dmg: fix binary search
Looks good to me.
Reviewed-by: Julio Faracco
Em dom, 23 de dez de 2018 às 01:04, yuchenlin
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
> ---
> 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
>
>
>
