From nobody Fri Nov 7 03:51:43 2025 Delivered-To: importer@patchew.org Received-SPF: pass (zoho.com: domain of gnu.org designates 208.118.235.17 as permitted sender) client-ip=208.118.235.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zoho.com: domain of gnu.org designates 208.118.235.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=gmail.com Return-Path: Received: from lists.gnu.org (208.118.235.17 [208.118.235.17]) by mx.zohomail.com with SMTPS id 1546516175456987.6015201336523; Thu, 3 Jan 2019 03:49:35 -0800 (PST) Received: from localhost ([127.0.0.1]:52792 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gf1V7-0001n1-8x for importer@patchew.org; Thu, 03 Jan 2019 06:49:25 -0500 Received: from eggs.gnu.org ([208.118.235.92]:53055) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gf1TK-0000Um-Ux for qemu-devel@nongnu.org; Thu, 03 Jan 2019 06:47:35 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1gf1TK-0003SN-CS for qemu-devel@nongnu.org; Thu, 03 Jan 2019 06:47:34 -0500 Received: from mail-pf1-x442.google.com ([2607:f8b0:4864:20::442]:37391) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1gf1TK-0003S1-71; Thu, 03 Jan 2019 06:47:34 -0500 Received: by mail-pf1-x442.google.com with SMTP id y126so16600854pfb.4; Thu, 03 Jan 2019 03:47:34 -0800 (PST) Received: from localhost.localdomain (223-137-100-47.emome-ip.hinet.net. [223.137.100.47]) by smtp.gmail.com with ESMTPSA id t67sm103011808pfd.90.2019.01.03.03.47.31 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 03 Jan 2019 03:47:32 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=JrqOcFUpKvSl7P5WLgjrOg0Yk69+g6Qle5b6/IqyXG4=; b=sd2SF7vkDgy+5YCdwyVCKiFc3N8lhOLkTCEBUoDMr4SEtnmn2QX+Ift/OC71o0IToa 6b5TIIhD+Msib5KT0kc6lrqujeEh++RzK04krrswZxKH/nLMDZKx+/iiDEaSZVExPIdd Cv/lJLanU2cVMgn27YG2by7xOftRUeRTo/cxnWDENuvYIoh6E9ixYdUzvjwooHCn8s3C uERA0Iumy+gzX0D+rEsF/dEqDQLSsmNGUXTvqzcByFntuOAcrzf2irdJDwUXmmyDlUMR XM3xTw54suEJtCV9RA1JGnJ1iDbv956xTkVPo928yxQ5qUDeG187MNYoweciLwyY9lPG A5Ug== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=JrqOcFUpKvSl7P5WLgjrOg0Yk69+g6Qle5b6/IqyXG4=; b=cDFvDBekv5YqEUASZZzomuPNAOm/mbJMoaRM0tCwhnXyJ8mJwU9LqWTeudUrvNe6Lr x/WjTwGddIBU0jM83cr2AxlIAvIUqE69WSa+sZAASWr6GwlxUheVO2EnJFyMlcxUIg4/ 7oIT3sd/3UxC/jCVzPYtVds61qpnz9KeijtnCE/tjH2st/DTGQtahh1p2dT0iTrYMDa7 9geg6ulWHc4wUwqEqT+ZkYhAEH0muO0gQl9ZManbpsbA9rsjMljfpQAFtXeHG2vCIcJ6 U6DMn4Y2YtYANUvIv2+IiOyOgU97FGRBBTOGs2Bbx5FsG5WKsQa68gS1n7xjnmjVoV39 Sw3g== X-Gm-Message-State: AA+aEWbTazTrAIG8/I2Wl4mDuLFPcB+akyOYkQ1f4n3OiLdmLr7yr6Lc KuuNjmtZqCOEZKgPY8Uwa2B7kOy4MEc= X-Google-Smtp-Source: AFSGD/UMi80B1ArgmlfmajygcavPVnLUtIXwIq7L4c1O5wOPShraQE1j1mPYhqf2Rzmwm83wt1tIFQ== X-Received: by 2002:a62:5dd1:: with SMTP id n78mr47287101pfj.58.1546516052968; Thu, 03 Jan 2019 03:47:32 -0800 (PST) From: yuchenlin To: qemu-devel@nongnu.org Date: Thu, 3 Jan 2019 19:46:58 +0800 Message-Id: <20190103114700.9686-2-npes87184@gmail.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190103114700.9686-1-npes87184@gmail.com> References: <20190103114700.9686-1-npes87184@gmail.com> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2607:f8b0:4864:20::442 Subject: [Qemu-devel] [PATCH v3 1/3] dmg: fix binary search X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: yuchenlin , qemu-block@nongnu.org, stefanha@redhat.com Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: fail (Header signature does not verify) Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" There is a possible hang in original binary search implementation. That is if chunk1 =3D 4, chunk2 =3D 5, chunk3 =3D 4, and we go else case. The chunk1 will be still 4, and so on. Signed-off-by: yuchenlin --- block/dmg.c | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-) diff --git a/block/dmg.c b/block/dmg.c index 50e91aef6d..65a0140487 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 =3D 0, chunk2 =3D s->n_chunks, chunk3; - while (chunk1 !=3D chunk2) { + while (chunk1 <=3D chunk2) { chunk3 =3D (chunk1 + chunk2) / 2; if (s->sectors[chunk3] > sector_num) { - chunk2 =3D chunk3; + if (chunk3 =3D=3D 0) { + goto err; + } + chunk2 =3D chunk3 - 1; } else if (s->sectors[chunk3] + s->sectorcounts[chunk3] > sector_n= um) { return chunk3; } else { - chunk1 =3D chunk3; + chunk1 =3D chunk3 + 1; } } +err: return s->n_chunks; /* error */ } =20 --=20 2.17.1