From nobody Mon Feb 9 02:14:29 2026 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=redhat.com ARC-Seal: i=1; a=rsa-sha256; t=1610372820; cv=none; d=zohomail.com; s=zohoarc; b=Ok9RtQxpYgzcQS6bHg+o9czPa/xf49H+nuea9m1tA821ve6H8mOsWnHCKNInSLO55KBFxL9WoK7z9ynG/o2MXlQ80rm9SCzpIcQZvqh1KNFk2MhWFmhi62JcaF92ERYRzf798XNGNFXGTWillruS6VDEaiPgqMhBk6JjOZ96rS0= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1610372820; h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=9OyA7s3fu9/RJlUjnURCpan4t4/LnXrI2eQKIq33aXc=; b=BVFrFC4ZadbskRLLPGM5lEwjM5Yldk4Eshse/eJqt/R/6yRLR0OeDbL66O5/hTucuybOBb/JUIdfhyqPZPVWxeO+86rehp8BPu7izxmIOME+buDkkHuxQx2ztVoyyJPb88ksv9KQgIkRpt1+UoyGn8+hh3vzIiVLsT9w2JJk68c= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail header.from= (p=none dis=none) header.from= Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1610372820050101.61949462619828; Mon, 11 Jan 2021 05:47:00 -0800 (PST) Received: from localhost ([::1]:54862 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kyxX8-0004Zd-Ej for importer@patchew.org; Mon, 11 Jan 2021 08:46:58 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]:52736) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kyxUM-0002hs-ST for qemu-devel@nongnu.org; Mon, 11 Jan 2021 08:44:06 -0500 Received: from us-smtp-delivery-124.mimecast.com ([216.205.24.124]:55097) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.90_1) (envelope-from ) id 1kyxUE-00082r-W0 for qemu-devel@nongnu.org; Mon, 11 Jan 2021 08:44:06 -0500 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-219-otO8p-xsPvSIj8fp84JNGw-1; Mon, 11 Jan 2021 08:43:52 -0500 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id D0FC4DF8A4; Mon, 11 Jan 2021 13:43:50 +0000 (UTC) Received: from thuth.com (ovpn-112-147.ams2.redhat.com [10.36.112.147]) by smtp.corp.redhat.com (Postfix) with ESMTP id 16C4D2BFE9; Mon, 11 Jan 2021 13:43:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1610372636; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=9OyA7s3fu9/RJlUjnURCpan4t4/LnXrI2eQKIq33aXc=; b=eA9/5Pg+QYlW2GbUPe39Y8uFVX+F9iudMDtXkrbovNc13BL2+8WPARxUkDbk/+P86s9LBU 8+ELCtPJXzzfMA+oR5PuGx4YCWJaNKxEsN2ui0YiE/7WrXYnlsh1rV8FEthq9XEU8cKRfb KM4W/eeWCmI4Odi0ii2J8GjgPNuyd48= X-MC-Unique: otO8p-xsPvSIj8fp84JNGw-1 From: Thomas Huth To: qemu-devel@nongnu.org, Peter Maydell Subject: [PULL 05/15] fuzz: double the IOs to remove for every loop Date: Mon, 11 Jan 2021 14:43:18 +0100 Message-Id: <20210111134328.157775-6-thuth@redhat.com> In-Reply-To: <20210111134328.157775-1-thuth@redhat.com> References: <20210111134328.157775-1-thuth@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 Authentication-Results: relay.mimecast.com; auth=pass smtp.auth=CUSA124A263 smtp.mailfrom=thuth@redhat.com X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Received-SPF: pass client-ip=216.205.24.124; envelope-from=thuth@redhat.com; helo=us-smtp-delivery-124.mimecast.com X-Spam_score_int: -29 X-Spam_score: -3.0 X-Spam_bar: --- X-Spam_report: (-3.0 / 5.0 requ) BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.251, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Alexander Bulekov , Warner Losh , Qiuhao Li Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: fail (Header signature does not verify) Content-Type: text/plain; charset="utf-8" From: Qiuhao Li Instead of removing IO instructions one by one, we can try deleting multiple instructions at once. According to the locality of reference, we double the number of instructions to remove for the next round and recover it to one once we fail. This patch is usually significant for large input. Test with quadrupled trace input at: https://bugs.launchpad.net/qemu/+bug/1890333/comments/1 Patched 1/6 version: real 0m45.904s user 0m16.874s sys 0m10.042s Refined version: real 0m11.412s user 0m6.888s sys 0m3.325s Signed-off-by: Qiuhao Li Reviewed-by: Alexander Bulekov Tested-by: Alexander Bulekov Message-Id: Signed-off-by: Thomas Huth --- scripts/oss-fuzz/minimize_qtest_trace.py | 33 +++++++++++++++--------- 1 file changed, 21 insertions(+), 12 deletions(-) diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/mi= nimize_qtest_trace.py index a28913a2a7..cacabf2638 100755 --- a/scripts/oss-fuzz/minimize_qtest_trace.py +++ b/scripts/oss-fuzz/minimize_qtest_trace.py @@ -88,19 +88,28 @@ def minimize_trace(inpath, outpath): =20 i =3D 0 newtrace =3D trace[:] - # For each line + remove_step =3D 1 while i < len(newtrace): - # 1.) Try to remove it completely and reproduce the crash. If it w= orks, - # we're done. - prior =3D newtrace[i] - print("Trying to remove {}".format(newtrace[i])) - # Try to remove the line completely - newtrace[i] =3D "" + # 1.) Try to remove lines completely and reproduce the crash. + # If it works, we're done. + if (i+remove_step) >=3D len(newtrace): + remove_step =3D 1 + prior =3D newtrace[i:i+remove_step] + for j in range(i, i+remove_step): + newtrace[j] =3D "" + print("Removing {lines} ...".format(lines=3Dprior)) if check_if_trace_crashes(newtrace, outpath): - i +=3D 1 + i +=3D remove_step + # Double the number of lines to remove for next round + remove_step *=3D 2 continue - newtrace[i] =3D prior - + # Failed to remove multiple IOs, fast recovery + if remove_step > 1: + for j in range(i, i+remove_step): + newtrace[j] =3D prior[j-i] + remove_step =3D 1 + continue + newtrace[i] =3D prior[0] # remove_step =3D 1 # 2.) Try to replace write{bwlq} commands with a write addr, len # command. Since this can require swapping endianness, try both LE= and # BE options. We do this, so we can "trim" the writes in (3) @@ -121,7 +130,7 @@ def minimize_trace(inpath, outpath): if(check_if_trace_crashes(newtrace, outpath)): break else: - newtrace[i] =3D prior + newtrace[i] =3D prior[0] =20 # 3.) If it is a qtest write command: write addr len data, try to = split # it into two separate write commands. If splitting the write down= the @@ -154,7 +163,7 @@ def minimize_trace(inpath, outpath): if check_if_trace_crashes(newtrace, outpath): i -=3D 1 else: - newtrace[i] =3D prior + newtrace[i] =3D prior[0] del newtrace[i+1] i +=3D 1 check_if_trace_crashes(newtrace, outpath) --=20 2.27.0