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> --- 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 a290dc0579..71fb0cef32 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
