From 3f590eebf929ad4443e80dc9fae1f86500b1857c Mon Sep 17 00:00:00 2001 From: Dmitry Vyukov Date: Tue, 4 Jan 2022 16:59:51 +0100 Subject: prog: refactor generation of resources Currnetly we loop up to 1000 times in randGen.createResource, this is necessary because we can't guarantee that the generated syscall will indeed contain the necessary resources. This is ugly. Now that we have stricter constructors (no unions) with few additional tweaks we can guarantee that we generate the resource every time. Generate at least 1 array element when in createResource. Don't generate special empty pointers when in createResource. Record only resource constructors in Syscall.outputResource, this makes rotation logic to include at least 1 of them. --- prog/rand.go | 106 +++++++++++++++++++++++++------------------------ prog/resources.go | 78 ++++++++++++++++++------------------ prog/resources_test.go | 48 ++++++++++++++++++++++ prog/target.go | 2 - 4 files changed, 140 insertions(+), 94 deletions(-) (limited to 'prog') diff --git a/prog/rand.go b/prog/rand.go index aea2daeb1..7a256e4b0 100644 --- a/prog/rand.go +++ b/prog/rand.go @@ -345,8 +345,14 @@ func (r *randGen) allocVMA(s *state, typ Type, dir Dir, numPages uint64) *Pointe return MakeVmaPointerArg(typ, dir, page*r.target.PageSize, numPages*r.target.PageSize) } -func (r *randGen) createResource(s *state, res *ResourceType, dir Dir) (arg Arg, calls []*Call) { +func (r *randGen) createResource(s *state, res *ResourceType, dir Dir) (Arg, []*Call) { + if !r.inGenerateResource { + panic("inGenerateResource is not set") + } kind := res.Desc.Name + // Find calls that produce the necessary resources. + // TODO: reduce priority of less specialized ctors. + metas := r.enabledCtors(s, kind) // We may have no resources, but still be in createResource due to ANYRES. if len(r.target.resourceMap) != 0 && r.oneOf(1000) { // Spoof resource subkind. @@ -361,64 +367,54 @@ func (r *randGen) createResource(s *state, res *ResourceType, dir Dir) (arg Arg, kind, r.target.OS, r.target.Arch)) } sort.Strings(all) - kind = all[r.Intn(len(all))] - } - // Find calls that produce the necessary resources. - metas0 := r.target.resourceCtors[kind] - // TODO: reduce priority of less specialized ctors. - var metas []*Syscall - for _, meta := range metas0 { - if s.ct.Enabled(meta.ID) { - metas = append(metas, meta) + kind1 := all[r.Intn(len(all))] + metas1 := r.enabledCtors(s, kind1) + if len(metas1) != 0 { + // Don't use the resource for which we don't have any ctors. + // It's fine per-se because below we just return nil in such case. + // But in TestCreateResource tests we want to ensure that we don't fail + // to create non-optional resources, and if we spoof a non-optional + // resource with ctors with a optional resource w/o ctors, then that check will fail. + kind, metas = kind1, metas1 } } if len(metas) == 0 { - return res.DefaultArg(dir), nil + // We may not have any constructors for optional input resources because we don't disable + // syscalls based on optional inputs resources w/o ctors in TransitivelyEnabledCalls. + return nil, nil } - // Now we have a set of candidate calls that can create the necessary resource. - for i := 0; i < 1e3; i++ { - // Generate one of them. - meta := metas[r.Intn(len(metas))] - calls := r.generateParticularCall(s, meta) - s1 := newState(r.target, s.ct, nil) - s1.analyze(calls[len(calls)-1]) - // Now see if we have what we want. - var allres []*ResultArg - for kind1, res1 := range s1.resources { - if r.target.isCompatibleResource(kind, kind1) { - allres = append(allres, res1...) - } - } - sort.SliceStable(allres, func(i, j int) bool { - return allres[i].Type().Name() < allres[j].Type().Name() - }) - if len(allres) != 0 { - // Bingo! - arg := MakeResultArg(res, dir, allres[r.Intn(len(allres))], 0) - return arg, calls - } - // Discard unsuccessful calls. - // Note: s.ma/va have already noted allocations of the new objects - // in discarded syscalls, ideally we should recreate state - // by analyzing the program again. - for _, c := range calls { - ForeachArg(c, func(arg Arg, _ *ArgCtx) { - if a, ok := arg.(*ResultArg); ok && a.Res != nil { - delete(a.Res.uses, a) - } - }) + // Generate one of them. + meta := metas[r.Intn(len(metas))] + calls := r.generateParticularCall(s, meta) + s1 := newState(r.target, s.ct, nil) + s1.analyze(calls[len(calls)-1]) + // Now see if we have what we want. + var allres []*ResultArg + for kind1, res1 := range s1.resources { + if r.target.isCompatibleResource(kind, kind1) { + allres = append(allres, res1...) } } - // Generally we can loop several times, e.g. when we choose a call that returns - // the resource in an array, but then generateArg generated that array of zero length. - // But we must succeed eventually. - var ctors []string - for _, meta := range metas { - ctors = append(ctors, meta.Name) + sort.SliceStable(allres, func(i, j int) bool { + return allres[i].Type().Name() < allres[j].Type().Name() + }) + if len(allres) == 0 { + panic(fmt.Sprintf("failed to create a resource %v (%v) with %v", + res.Desc.Kind[0], kind, meta.Name)) } - panic(fmt.Sprintf("failed to create a resource %v (%v) with %v", - kind, res.Desc.Kind[0], strings.Join(ctors, ", "))) + arg := MakeResultArg(res, dir, allres[r.Intn(len(allres))], 0) + return arg, calls +} + +func (r *randGen) enabledCtors(s *state, kind string) []*Syscall { + var metas []*Syscall + for _, meta := range r.target.resourceCtors[kind] { + if s.ct.Enabled(meta.ID) { + metas = append(metas, meta) + } + } + return metas } func (r *randGen) generateText(kind TextKind) []byte { @@ -781,6 +777,10 @@ func (a *ArrayType) generate(r *randGen, s *state, dir Dir) (arg Arg, calls []*C case ArrayRangeLen: count = r.randRange(a.RangeBegin, a.RangeEnd) } + // The resource we are trying to generate may be in the array elements, so create at least 1. + if r.inGenerateResource && count == 0 { + count = 1 + } var inner []Arg for i := uint64(0); i < count; i++ { arg1, calls1 := r.generateArg(s, a.Elem, dir) @@ -804,7 +804,9 @@ func (a *UnionType) generate(r *randGen, s *state, dir Dir) (arg Arg, calls []*C } func (a *PtrType) generate(r *randGen, s *state, dir Dir) (arg Arg, calls []*Call) { - if r.oneOf(1000) { + // The resource we are trying to generate may be in the pointer, + // so don't try to create an empty special pointer during resource generation. + if !r.inGenerateResource && r.oneOf(1000) { index := r.rand(len(r.target.SpecialPointers)) return MakeSpecialPointerArg(a, dir, index), nil } diff --git a/prog/resources.go b/prog/resources.go index 7c7fa1770..95480a8a0 100644 --- a/prog/resources.go +++ b/prog/resources.go @@ -45,20 +45,34 @@ func (target *Target) calcResourceCtors(res *ResourceDesc, precise bool) []*Sysc func (target *Target) populateResourceCtors() { // Find resources that are created by each call. callsResources := make([][]*ResourceDesc, len(target.Syscalls)) - ForeachType(target.Syscalls, func(typ Type, ctx *TypeCtx) { - if typ.Optional() { - ctx.Stop = true - return - } - switch typ1 := typ.(type) { - case *UnionType: - ctx.Stop = true - case *ResourceType: - if ctx.Dir != DirIn { - callsResources[ctx.Meta.ID] = append(callsResources[ctx.Meta.ID], typ1.Desc) + for _, meta := range target.Syscalls { + dedup := make(map[*ResourceDesc]bool) + ForeachCallType(meta, func(typ Type, ctx *TypeCtx) { + if typ.Optional() { + ctx.Stop = true + return } - } - }) + switch typ1 := typ.(type) { + case *UnionType: + ctx.Stop = true + case *ResourceType: + if ctx.Dir == DirIn || dedup[typ1.Desc] { + break + } + dedup[typ1.Desc] = true + callsResources[meta.ID] = append(callsResources[meta.ID], typ1.Desc) + meta.outputResources = append(meta.outputResources, typ1.Desc) + } + }) + } + + if c := target.SyscallMap["clock_gettime"]; c != nil { + c.outputResources = append(c.outputResources, timespecRes) + } + + for _, c := range target.Syscalls { + c.inputResources = target.getInputResources(c) + } // Populate resource ctors accounting for resource compatibility. for _, res := range target.Resources { @@ -129,6 +143,7 @@ func isCompatibleResourceImpl(dst, src []string, precise bool) bool { } func (target *Target) getInputResources(c *Syscall) []*ResourceDesc { + dedup := make(map[*ResourceDesc]bool) var resources []*ResourceDesc ForeachCallType(c, func(typ Type, ctx *TypeCtx) { if ctx.Dir == DirOut { @@ -136,11 +151,13 @@ func (target *Target) getInputResources(c *Syscall) []*ResourceDesc { } switch typ1 := typ.(type) { case *ResourceType: - if !typ1.IsOptional { + if !typ1.IsOptional && !dedup[typ1.Desc] { + dedup[typ1.Desc] = true resources = append(resources, typ1.Desc) } case *StructType: - if target.OS == "linux" && (typ1.Name() == "timespec" || typ1.Name() == "timeval") { + if target.OS == "linux" && !dedup[timespecRes] && (typ1.Name() == "timespec" || typ1.Name() == "timeval") { + dedup[timespecRes] = true resources = append(resources, timespecRes) } } @@ -148,44 +165,25 @@ func (target *Target) getInputResources(c *Syscall) []*ResourceDesc { return resources } -func (target *Target) getOutputResources(c *Syscall) []*ResourceDesc { - var resources []*ResourceDesc - ForeachCallType(c, func(typ Type, ctx *TypeCtx) { - switch typ1 := typ.(type) { - case *ResourceType: - if ctx.Dir != DirIn { - resources = append(resources, typ1.Desc) - } - } - }) - if c.CallName == "clock_gettime" { - resources = append(resources, timespecRes) - } - return resources -} - func (target *Target) transitivelyEnabled(enabled map[*Syscall]bool) (map[*Syscall]bool, map[string]bool) { supported := make(map[*Syscall]bool, len(enabled)) canCreate := make(map[string]bool, len(enabled)) for { n := len(supported) + nextCall: for c := range enabled { if supported[c] { continue } - ready := true for _, res := range c.inputResources { if !canCreate[res.Name] { - ready = false - break + continue nextCall } } - if ready { - supported[c] = true - for _, res := range c.outputResources { - for _, kind := range res.Kind { - canCreate[kind] = true - } + supported[c] = true + for _, res := range c.outputResources { + for _, kind := range res.Kind { + canCreate[kind] = true } } } diff --git a/prog/resources_test.go b/prog/resources_test.go index b041bf8e9..e48efa65c 100644 --- a/prog/resources_test.go +++ b/prog/resources_test.go @@ -4,6 +4,7 @@ package prog import ( + "math/rand" "strings" "testing" @@ -115,3 +116,50 @@ func TestClockGettime(t *testing.T) { len(calls), len(trans), len(disabled)) } } + +func TestCreateResourceRotation(t *testing.T) { + target, rs, _ := initTest(t) + allCalls := make(map[*Syscall]bool) + for _, call := range target.Syscalls { + allCalls[call] = true + } + rotator := MakeRotator(target, allCalls, rand.New(rs)) + testCreateResource(t, target, rotator.Select(), rs) +} + +func TestCreateResourceHalf(t *testing.T) { + target, rs, _ := initTest(t) + r := rand.New(rs) + var halfCalls map[*Syscall]bool + for len(halfCalls) == 0 { + halfCalls = make(map[*Syscall]bool) + for _, call := range target.Syscalls { + if r.Intn(10) == 0 { + halfCalls[call] = true + } + } + halfCalls, _ = target.TransitivelyEnabledCalls(halfCalls) + } + testCreateResource(t, target, halfCalls, rs) +} + +func testCreateResource(t *testing.T, target *Target, calls map[*Syscall]bool, rs rand.Source) { + r := newRand(target, rs) + r.inGenerateResource = true + ct := target.BuildChoiceTable(nil, calls) + for call := range calls { + t.Logf("testing call %v", call.Name) + ForeachCallType(call, func(typ Type, ctx *TypeCtx) { + if res, ok := typ.(*ResourceType); ok && ctx.Dir != DirOut { + s := newState(target, ct, nil) + arg, calls := r.createResource(s, res, DirIn) + if arg == nil && !res.Optional() { + t.Fatalf("failed to create resource %v", res.Name()) + } + if arg != nil && len(calls) == 0 { + t.Fatalf("created resource %v, but got no calls", res.Name()) + } + } + }) + } +} diff --git a/prog/target.go b/prog/target.go index 182d46391..08495f1f2 100644 --- a/prog/target.go +++ b/prog/target.go @@ -151,8 +151,6 @@ func (target *Target) initTarget() { for i, c := range target.Syscalls { c.ID = i target.SyscallMap[c.Name] = c - c.inputResources = target.getInputResources(c) - c.outputResources = target.getOutputResources(c) } target.populateResourceCtors() -- cgit mrf-deployment