From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-13.0 required=3.0 tests=BAYES_00,HK_RANDOM_FROM, INCLUDES_CR_TRAILER,INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE, URIBL_BLOCKED autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 17C08C433DB for ; Thu, 7 Jan 2021 04:20:52 +0000 (UTC) Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 94AA523100 for ; Thu, 7 Jan 2021 04:20:51 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 94AA523100 Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=bu.edu Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=qemu-devel-bounces+qemu-devel=archiver.kernel.org@nongnu.org Received: from localhost ([::1]:56416 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kxMn4-0005Wl-OT for qemu-devel@archiver.kernel.org; Wed, 06 Jan 2021 23:20:50 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]:57432) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kxMm1-0004cB-2K for qemu-devel@nongnu.org; Wed, 06 Jan 2021 23:19:45 -0500 Received: from relay64.bu.edu ([128.197.228.104]:44530) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kxMlz-0003lr-80 for qemu-devel@nongnu.org; Wed, 06 Jan 2021 23:19:44 -0500 X-Envelope-From: alxndr@bu.edu X-BU-AUTH: mozz.bu.edu [128.197.127.33] Received: from BU-AUTH (localhost.localdomain [127.0.0.1]) (authenticated bits=0) by relay64.bu.edu (8.14.3/8.14.3) with ESMTP id 1074JGS4012739 (version=TLSv1/SSLv3 cipher=AES256-GCM-SHA384 bits=256 verify=NO); Wed, 6 Jan 2021 23:19:19 -0500 Date: Wed, 6 Jan 2021 23:19:16 -0500 From: Alexander Bulekov To: Qiuhao Li Subject: Re: [PATCH v4 2/7] fuzz: double the IOs to remove for every loop Message-ID: <20210107041916.zy7xtzbbdurnowdc@mozz.bu.edu> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: Received-SPF: pass client-ip=128.197.228.104; envelope-from=alxndr@bu.edu; helo=relay64.bu.edu X-Spam_score_int: -15 X-Spam_score: -1.6 X-Spam_bar: - X-Spam_report: (-1.6 / 5.0 requ) BAYES_00=-1.9, HK_RANDOM_ENVFROM=0.001, HK_RANDOM_FROM=0.999, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=no 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: thuth@redhat.com, qemu-devel@nongnu.org, darren.kenny@oracle.com, bsd@redhat.com, stefanha@redhat.com, pbonzini@redhat.com Errors-To: qemu-devel-bounces+qemu-devel=archiver.kernel.org@nongnu.org Sender: "Qemu-devel" On 201229 1240, Qiuhao Li wrote: > 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 > --- > 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/minimize_qtest_trace.py > index aa69c7963e..0b665ae657 100755 > --- a/scripts/oss-fuzz/minimize_qtest_trace.py > +++ b/scripts/oss-fuzz/minimize_qtest_trace.py > @@ -85,19 +85,28 @@ def minimize_trace(inpath, outpath): > > i = 0 > newtrace = trace[:] > - # For each line > + remove_step = 1 > while i < len(newtrace): > - # 1.) Try to remove it completely and reproduce the crash. If it works, > - # we're done. > - prior = newtrace[i] > - print("Trying to remove {}".format(newtrace[i])) > - # Try to remove the line completely > - newtrace[i] = "" > + # 1.) Try to remove lines completely and reproduce the crash. > + # If it works, we're done. > + if (i+remove_step) >= len(newtrace): > + remove_step = 1 > + prior = newtrace[i:i+remove_step] > + for j in range(i, i+remove_step): > + newtrace[j] = "" > + print("Removing {lines} ...".format(lines=prior)) > if check_if_trace_crashes(newtrace, outpath): > - i += 1 > + i += remove_step > + # Double the number of lines to remove for next round > + remove_step *= 2 > continue > - newtrace[i] = prior > - > + # Failed to remove multiple IOs, fast recovery > + if remove_step > 1: > + for j in range(i, i+remove_step): > + newtrace[j] = prior[j-i] > + remove_step = 1 > + continue > + newtrace[i] = prior[0] # remove_step = 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) > @@ -118,7 +127,7 @@ def minimize_trace(inpath, outpath): > if(check_if_trace_crashes(newtrace, outpath)): > break > else: > - newtrace[i] = prior > + newtrace[i] = prior[0] > > # 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 > @@ -151,7 +160,7 @@ def minimize_trace(inpath, outpath): > if check_if_trace_crashes(newtrace, outpath): > i -= 1 > else: > - newtrace[i] = prior > + newtrace[i] = prior[0] > del newtrace[i+1] > i += 1 > check_if_trace_crashes(newtrace, outpath) > -- > 2.25.1 >