* [Qemu-devel] [PATCH] dmg: fix binary search
@ 2018-12-21 13:58 yuchenlin
2019-01-02 10:46 ` Stefan Hajnoczi
2019-01-17 19:29 ` [Qemu-devel] " John Snow
0 siblings, 2 replies; 5+ messages in thread
From: yuchenlin @ 2018-12-21 13:58 UTC (permalink / raw)
To: qemu-devel; +Cc: stefanha, qemu-block, qemu-trivial, 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
^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [Qemu-devel] [PATCH] dmg: fix binary search
2018-12-21 13:58 [Qemu-devel] [PATCH] dmg: fix binary search yuchenlin
@ 2019-01-02 10:46 ` Stefan Hajnoczi
2019-01-02 14:19 ` [Qemu-devel] [Qemu-block] " Julio Faracco
2019-01-17 19:29 ` [Qemu-devel] " John Snow
1 sibling, 1 reply; 5+ messages in thread
From: Stefan Hajnoczi @ 2019-01-02 10:46 UTC (permalink / raw)
To: yuchenlin; +Cc: qemu-devel, qemu-block, qemu-trivial
[-- 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 --]
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Qemu-devel] [Qemu-block] [PATCH] dmg: fix binary search
2019-01-02 10:46 ` Stefan Hajnoczi
@ 2019-01-02 14:19 ` Julio Faracco
0 siblings, 0 replies; 5+ messages in thread
From: Julio Faracco @ 2019-01-02 14:19 UTC (permalink / raw)
To: Stefan Hajnoczi; +Cc: yuchenlin, qemu-trivial, QEMU Developers, qemu-block
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!
>
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Qemu-devel] [PATCH] dmg: fix binary search
2018-12-21 13:58 [Qemu-devel] [PATCH] dmg: fix binary search yuchenlin
2019-01-02 10:46 ` Stefan Hajnoczi
@ 2019-01-17 19:29 ` John Snow
2019-01-17 19:50 ` John Snow
1 sibling, 1 reply; 5+ messages in thread
From: John Snow @ 2019-01-17 19:29 UTC (permalink / raw)
To: yuchenlin, qemu-devel; +Cc: qemu-trivial, qemu-block, stefanha
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
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Qemu-devel] [PATCH] dmg: fix binary search
2019-01-17 19:29 ` [Qemu-devel] " John Snow
@ 2019-01-17 19:50 ` John Snow
0 siblings, 0 replies; 5+ messages in thread
From: John Snow @ 2019-01-17 19:50 UTC (permalink / raw)
To: yuchenlin, qemu-devel; +Cc: qemu-trivial, qemu-block, stefanha
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.
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2019-01-17 19:50 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-12-21 13:58 [Qemu-devel] [PATCH] dmg: fix binary search yuchenlin
2019-01-02 10:46 ` Stefan Hajnoczi
2019-01-02 14:19 ` [Qemu-devel] [Qemu-block] " Julio Faracco
2019-01-17 19:29 ` [Qemu-devel] " John Snow
2019-01-17 19:50 ` John Snow
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.