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 <qiuhao...@outlook.com>
Reviewed-by: Alexander Bulekov <alx...@bu.edu>
> ---
> 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
>
