diff options
| author | yuchenlin <npes87184@gmail.com> | 2019-01-03 19:46:58 +0800 |
|---|---|---|
| committer | Stefan Hajnoczi <stefanha@redhat.com> | 2019-01-04 11:15:09 +0000 |
| commit | 5ef40828baafc27dc3e52320c3125f2bd3f44886 (patch) | |
| tree | be5704bd78f6884f02a49135a34e22d18fe37834 /block | |
| parent | b47c7d53252d46811c555bc08aeb9918fd7dbd24 (diff) | |
dmg: fix binary search
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 <npes87184@gmail.com>
Message-id: 20190103114700.9686-2-npes87184@gmail.com
Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
Diffstat (limited to 'block')
| -rw-r--r-- | block/dmg.c | 10 |
1 files changed, 7 insertions, 3 deletions
diff --git a/block/dmg.c b/block/dmg.c index 2c806e3389..b26ddb1f68 100644 --- a/block/dmg.c +++ b/block/dmg.c @@ -572,16 +572,20 @@ 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; + if (chunk3 == 0) { + goto err; + } + chunk2 = chunk3 - 1; } else if (s->sectors[chunk3] + s->sectorcounts[chunk3] > sector_num) { return chunk3; } else { - chunk1 = chunk3; + chunk1 = chunk3 + 1; } } +err: return s->n_chunks; /* error */ } |