From b0fa969c096608d3411359b3d0c4f95b95ddc2d5 Mon Sep 17 00:00:00 2001 From: Dmitry Vyukov Date: Fri, 8 Dec 2017 12:27:39 +0100 Subject: prog: speedup and simplify hints code Clone program only once. Preallocate slices in clone. Remove the clone full mode. Always mutate args in place. Allocate replacers map lazily. Don't allocate res map at all (calculate valus on the go). Remove sliceToUint64, pad. benchmark old ns/op new ns/op delta BenchmarkHints 122100048 7466013 -93.89% --- prog/clone.go | 33 +++++++-------- prog/hints.go | 120 ++++++++++++++++++++--------------------------------- prog/hints_test.go | 11 +++-- 3 files changed, 67 insertions(+), 97 deletions(-) diff --git a/prog/clone.go b/prog/clone.go index 2253c7e75..1ff42f60f 100644 --- a/prog/clone.go +++ b/prog/clone.go @@ -4,33 +4,30 @@ package prog func (p *Prog) Clone() *Prog { - p1, _ := p.cloneImpl(false) - return p1 -} - -func (p *Prog) cloneImpl(full bool) (*Prog, map[Arg]Arg) { p1 := &Prog{ Target: p.Target, + Calls: make([]*Call, len(p.Calls)), } newargs := make(map[Arg]Arg) - for _, c := range p.Calls { + for ci, c := range p.Calls { c1 := new(Call) c1.Meta = c.Meta - c1.Ret = clone(c.Ret, newargs, full) - for _, arg := range c.Args { - c1.Args = append(c1.Args, clone(arg, newargs, full)) + c1.Ret = clone(c.Ret, newargs) + c1.Args = make([]Arg, len(c.Args)) + for ai, arg := range c.Args { + c1.Args[ai] = clone(arg, newargs) } - p1.Calls = append(p1.Calls, c1) + p1.Calls[ci] = c1 } if debug { if err := p1.validate(); err != nil { panic(err) } } - return p1, newargs + return p1 } -func clone(arg Arg, newargs map[Arg]Arg, full bool) Arg { +func clone(arg Arg, newargs map[Arg]Arg) Arg { var arg1 Arg switch a := arg.(type) { case *ConstArg: @@ -42,7 +39,7 @@ func clone(arg Arg, newargs map[Arg]Arg, full bool) Arg { *a1 = *a arg1 = a1 if a.Res != nil { - a1.Res = clone(a.Res, newargs, full) + a1.Res = clone(a.Res, newargs) } case *DataArg: a1 := new(DataArg) @@ -53,15 +50,15 @@ func clone(arg Arg, newargs map[Arg]Arg, full bool) Arg { a1 := new(GroupArg) *a1 = *a arg1 = a1 - a1.Inner = nil - for _, arg2 := range a.Inner { - a1.Inner = append(a1.Inner, clone(arg2, newargs, full)) + a1.Inner = make([]Arg, len(a.Inner)) + for i, arg2 := range a.Inner { + a1.Inner[i] = clone(arg2, newargs) } case *UnionArg: a1 := new(UnionArg) *a1 = *a arg1 = a1 - a1.Option = clone(a.Option, newargs, full) + a1.Option = clone(a.Option, newargs) case *ResultArg: a1 := new(ResultArg) *a1 = *a @@ -85,8 +82,6 @@ func clone(arg Arg, newargs map[Arg]Arg, full bool) Arg { if used, ok := arg1.(ArgUsed); ok { *used.Used() = nil // filled when we clone the referent newargs[arg] = arg1 - } else if full { - newargs[arg] = arg1 } return arg1 } diff --git a/prog/hints.go b/prog/hints.go index dabb722da..e9f6f8a62 100644 --- a/prog/hints.go +++ b/prog/hints.go @@ -63,17 +63,26 @@ func (m CompMap) String() string { // Mutates the program using the comparison operands stored in compMaps. // For each of the mutants executes the exec callback. -func (p *Prog) MutateWithHints(callIndex int, comps CompMap, exec func(newP *Prog)) { - c := p.Calls[callIndex] - if c.Meta == p.Target.MmapSyscall { +func (p *Prog) MutateWithHints(callIndex int, comps CompMap, exec func(p *Prog)) { + if p.Calls[callIndex].Meta == p.Target.MmapSyscall { return } + p = p.Clone() + c := p.Calls[callIndex] + execValidate := func() { + if debug { + if err := p.validate(); err != nil { + panic(fmt.Sprintf("invalid hints candidate: %v", err)) + } + } + exec(p) + } foreachArg(c, func(arg, _ Arg, _ *[]Arg) { - generateHints(p, comps, callIndex, arg, exec) + generateHints(p, comps, c, arg, execValidate) }) } -func generateHints(p *Prog, compMap CompMap, callIndex int, arg Arg, exec func(p *Prog)) { +func generateHints(p *Prog, compMap CompMap, c *Call, arg Arg, exec func()) { if arg.Type().Dir() == DirOut { return } @@ -92,56 +101,35 @@ func generateHints(p *Prog, compMap CompMap, callIndex int, arg Arg, exec func(p return } - newP, argMap := p.cloneImpl(true) - newCall := newP.Calls[callIndex] - validateExec := func() { - if err := newP.validate(); err != nil { - panic(fmt.Sprintf("invalid hints candidate: %v", err)) - } - exec(newP) - } - var originalArg Arg - constArgCandidate := func(newArg Arg) { - oldArg := argMap[arg] - newP.replaceArg(newCall, oldArg, newArg, nil) - validateExec() - newP.replaceArg(newCall, oldArg, originalArg, nil) - } - - dataArgCandidate := func() { - // Data arg mutations are done in-place. No need to restore the original - // value - it gets restored in checkDataArg(). - // dataArgCandidate is only needed for unit tests. - validateExec() - } - switch a := arg.(type) { case *ConstArg: - originalArg = MakeConstArg(a.Type(), a.Val) - checkConstArg(a, compMap, constArgCandidate) + checkConstArg(a, compMap, exec) case *DataArg: - checkDataArg(argMap[arg].(*DataArg), compMap, dataArgCandidate) + checkDataArg(a, compMap, exec) } } -func checkConstArg(arg *ConstArg, compMap CompMap, cb func(newArg Arg)) { - for replacer := range shrinkExpand(arg.Val, compMap) { - cb(MakeConstArg(arg.typ, replacer)) +func checkConstArg(arg *ConstArg, compMap CompMap, exec func()) { + original := arg.Val + for replacer := range shrinkExpand(original, compMap) { + arg.Val = replacer + exec() } + arg.Val = original } -func checkDataArg(arg *DataArg, compMap CompMap, cb func()) { +func checkDataArg(arg *DataArg, compMap CompMap, exec func()) { bytes := make([]byte, 8) - original := make([]byte, 8) for i := 0; i < min(len(arg.Data), maxDataLength); i++ { + original := make([]byte, 8) copy(original, arg.Data[i:]) - val := sliceToUint64(arg.Data[i:]) + val := binary.LittleEndian.Uint64(original) for replacer := range shrinkExpand(val, compMap) { binary.LittleEndian.PutUint64(bytes, replacer) copy(arg.Data[i:], bytes) - cb() - copy(arg.Data[i:], original) + exec() } + copy(arg.Data[i:], original) } } @@ -175,20 +163,22 @@ func checkDataArg(arg *DataArg, compMap CompMap, cb func()) { // As with shrink we ignore cases when the other operand is wider. // Note that executor sign extends all the comparison operands to int64. // ====================================================================== -func shrinkExpand(v uint64, compMap CompMap) uint64Set { - replacers := make(uint64Set) - // Map: key is shrank/extended value, value is the maximal number of bits - // that can be replaced. - res := make(map[uint64]uint) - for _, size := range []uint{8, 16, 32} { - res[v&((1< 0 { + size = uint(isize) + mutant = v & ((1 << size) - 1) + } else { + size = uint(-isize) + mutant = v | ^((1 << size) - 1) } - } - res[v] = 64 - - for mutant, size := range res { + if size != 64 && prev == mutant { + continue + } + prev = mutant for newV := range compMap[mutant] { mask := uint64(1<= size returns a subslice of arr. -// Else creates a copy of arr padded with value to size. -func pad(arr []byte, value byte, size int) []byte { - if len(arr) >= size { - return arr[0:size] - } - block := make([]byte, size) - copy(block, arr) - for j := len(arr); j < size; j++ { - block[j] = value - } - return block -} - func min(a, b int) int { if a <= b { return a diff --git a/prog/hints_test.go b/prog/hints_test.go index b2999ad14..59b90d06d 100644 --- a/prog/hints_test.go +++ b/prog/hints_test.go @@ -57,8 +57,8 @@ func TestHintsCheckConstArg(t *testing.T) { t.Run(fmt.Sprintf("%v", test.name), func(t *testing.T) { res := uint64Set{} constArg := &ConstArg{ArgCommon{nil}, test.in} - checkConstArg(constArg, test.comps, func(arg Arg) { - res[arg.(*ConstArg).Val] = true + checkConstArg(constArg, test.comps, func() { + res[constArg.Val] = true }) if !reflect.DeepEqual(res, test.res) { t.Fatalf("\ngot : %v\nwant: %v", res, test.res) @@ -263,7 +263,7 @@ func TestHintsShrinkExpand(t *testing.T) { "Shrink with a wider replacer test1", 0x1234, CompMap{0x34: uint64Set{0x1bab: true}}, - uint64Set{}, + nil, }, { // Models the following code: @@ -329,7 +329,7 @@ func TestHintsShrinkExpand(t *testing.T) { "Extend with a wider replacer test", 0xff, CompMap{0xffffffffffffffff: uint64Set{0xfffffffffffffeff: true}}, - uint64Set{}, + nil, }, } for _, test := range tests { @@ -453,6 +453,9 @@ func TestHintsData(t *testing.T) { } func BenchmarkHints(b *testing.B) { + olddebug := debug + debug = false + defer func() { debug = olddebug }() target, err := GetTarget("linux", "amd64") if err != nil { b.Fatal(err) -- cgit mrf-deployment