Re: [PATCH v4 2/7] fuzz: double the IOs to remove for every loop

[Alexander Bulekov <alxndr@bu.edu>]

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.Li@outlook.com>

Reviewed-by: Alexander Bulekov <alxndr@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
>