Re: [Qemu-devel] [PATCH] dmg: fix binary search
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 > > 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.
Re: [Qemu-devel] [PATCH] dmg: fix binary search
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
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
Re: [Qemu-devel] [PATCH] dmg: fix binary search
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
> ---
> 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 0x so the loop continues with out-of-bounds sectors[]
accesses!
signature.asc
Description: PGP signature
[Qemu-devel] [PATCH] dmg: fix binary search
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
---
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
