On Mon, 2020-12-21 at 15:01 -0500, Alexander Bulekov wrote: > Qiuhao Li <qiuhao...@outlook.com> writes: > > > Currently, we split the write commands' data from the middle. If it > > does not > > work, try to move the pivot "left" and retry until there is no > > space left. > > But, this is complete for ram writes but not for IO writes. > > > > For example, there is an IO write command: > > > > write addr uuxxxxuu > > > > u is the unnecessary byte for the crash. Unlike ram write commands, > > in most > > case, a split IO write won't trigger the same crash, So if we split > > from the > > middle, we will get: > > > > write addr uu (will be removed in next round) > > write addr xxxxuu > > > > For xxxxuu, since split it from the middle and retry to the > > leftmost byte > > won't get the same crash, we will be stopped from removing the last > > two > > bytes. > > > > Good catch! I missed this case. > > > Therefore, we should split QTest writes from the rightmost byte. > > > > Tested with Bug 1908062. Refined vs. Original result: > > > > outl 0xcf8 0x8000081c outl 0xcf8 0x8000081c > > outb 0xcfc 0xc3 outb 0xcfc 0xc3 > > outl 0xcf8 0x8000082f outl 0xcf8 0x8000082f > > outl 0xcf8 0x80000804 outl 0xcf8 0x80000804 > > outl 0xcfc 0x9b2765be outl 0xcfc 0x9b2765be > > write 0xc300001024 0x2 0x0055 write 0xc300001024 0x2 0x0055 > > write 0xc300001028 0x1 0x5a write 0xc300001028 0x1 0x5a > > write 0xc30000101c 0x1 0x01 write 0xc30000101c 0x1 0x01 > > writel 0xc30000100c 0x2a6f6c63 writel 0xc30000100c 0x2a6f6c63 > > write 0xc300001018 0x1 0xa4 <-- write 0xc300001016 0x3 0xa4a4a4 > > write 0x5c 0x1 0x19 write 0x5c 0x1 0x19 > > write 0xc300003002 0x1 0x8a write 0xc300003002 0x1 0x8a > > > > Can we wrap-around to the right when we hit the end of the input on > the > left, instead of going byte-by-byte? Otherwise, i think we would need > O(n) operations to reach the leftmost in a write, rather than > O(logN). > > i.e. > xxxxuu -> > xxx xuu -> > xx xxuu -> > x xxxuu -> > xxxxu u > > I think the case where we would need to wrap around the entire input > usually happens for smaller writes, so it shouldn't slow the > minimizer > down too much > > -Alex
If we want to achieve O(logN), should we change the step size besides using a wrap-around strategy? @@ -164,8 +164,8 @@ def minimize_trace(inpath, outpath): if check_if_trace_crashes(newtrace, outpath): break else: - leftlength -= 1 - rightlength += 1 + leftlength -= leftlength/2 + rightlength = length - leftlength And how about using a binary search directly? Like: binary_search(newtrace, i,leftlen=1, len) base case: leftlen >= len xxxxuu len=6 + | + xxx,xuu (1+6)/2=3 + +--------------+-------------+ | | + + xx,xxuu (1+3)/2=2 xxxx,uu (3+6)/2=4 + success | +------+--------------+ | | | | + + x,xxxuu (1+2)/2=1 xx,xxuu (2+3)/2=2 base case base case > > > Signed-off-by: Qiuhao Li <qiuhao...@outlook.com> > > --- > > scripts/oss-fuzz/minimize_qtest_trace.py | 4 ++-- > > 1 file changed, 2 insertions(+), 2 deletions(-) > > > > diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py > > b/scripts/oss-fuzz/minimize_qtest_trace.py > > index d3b09e6567..855c3bcb54 100755 > > --- a/scripts/oss-fuzz/minimize_qtest_trace.py > > +++ b/scripts/oss-fuzz/minimize_qtest_trace.py > > @@ -140,7 +140,7 @@ def minimize_trace(inpath, outpath): > > > > # 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 > > - # middle does not work, try to move the pivot "left" and > > retry, until > > + # rightmost does not work, try to move the pivot "left" > > and retry, until > > # there is no space left. The idea is to prune > > unneccessary bytes from > > # long writes, while accommodating arbitrary MemoryRegion > > access sizes > > # and alignments. > > @@ -149,7 +149,7 @@ def minimize_trace(inpath, outpath): > > length = int(newtrace[i].split()[2], 16) > > data = newtrace[i].split()[3][2:] > > if length > 1: > > - leftlength = int(length/2) > > + leftlength = length - 1 > > rightlength = length - leftlength > > newtrace.insert(i+1, "") > > while leftlength > 0: > > -- > > 2.25.1