From 58ae5e18624eaaac79cab00e63d6f32c9bd64ee0 Mon Sep 17 00:00:00 2001 From: Dmitry Vyukov Date: Sun, 3 May 2020 11:29:12 +0200 Subject: prog: remove StructDesc Remove StructDesc, KeyedStruct, StructKey and all associated logic/complexity in prog and pkg/compiler. We can now handle recursion more generically with the Ref type, and Dir/FieldName are not a part of the type anymore. This makes StructType/UnionType simpler and more natural. Reduces size of sys/linux/gen/amd64.go from 5201321 to 4180861 (-20%). Update #1580 --- prog/any.go | 29 ++++++++-------- prog/prio.go | 91 ++++++++++++++++++++++++------------------------- prog/prog_test.go | 18 +++++----- prog/rand_test.go | 28 +++++++-------- prog/resources.go | 20 +++++------ prog/rotation.go | 2 +- prog/target.go | 63 ++++++++-------------------------- prog/types.go | 100 +++++++++++++++++++++++++++++++----------------------- 8 files changed, 162 insertions(+), 189 deletions(-) (limited to 'prog') diff --git a/prog/any.go b/prog/any.go index 1ce444ce2..ce3736a4b 100644 --- a/prog/any.go +++ b/prog/any.go @@ -36,7 +36,12 @@ type anyTypes struct { // resoct fmt[oct, ANYRES64] // ] [varlen] func initAnyTypes(target *Target) { - target.any.union = &UnionType{} + target.any.union = &UnionType{ + TypeCommon: TypeCommon{ + TypeName: "ANYUNION", + IsVarlen: true, + }, + } target.any.array = &ArrayType{ TypeCommon: TypeCommon{ TypeName: "ANYARRAY", @@ -89,20 +94,14 @@ func initAnyTypes(target *Target) { target.any.resdec = createResource("ANYRESDEC", "int64", FormatStrDec, 20) target.any.reshex = createResource("ANYRESHEX", "int64", FormatStrHex, 18) target.any.resoct = createResource("ANYRESOCT", "int64", FormatStrOct, 23) - target.any.union.StructDesc = &StructDesc{ - TypeCommon: TypeCommon{ - TypeName: "ANYUNION", - IsVarlen: true, - }, - Fields: []Field{ - {Name: "ANYBLOB", Type: target.any.blob}, - {Name: "ANYRES16", Type: target.any.res16}, - {Name: "ANYRES32", Type: target.any.res32}, - {Name: "ANYRES64", Type: target.any.res64}, - {Name: "ANYRESDEC", Type: target.any.resdec}, - {Name: "ANYRESHEX", Type: target.any.reshex}, - {Name: "ANYRESOCT", Type: target.any.resoct}, - }, + target.any.union.Fields = []Field{ + {Name: "ANYBLOB", Type: target.any.blob}, + {Name: "ANYRES16", Type: target.any.res16}, + {Name: "ANYRES32", Type: target.any.res32}, + {Name: "ANYRES64", Type: target.any.res64}, + {Name: "ANYRESDEC", Type: target.any.resdec}, + {Name: "ANYRESHEX", Type: target.any.reshex}, + {Name: "ANYRESOCT", Type: target.any.resoct}, } } diff --git a/prog/prio.go b/prog/prio.go index 43668d48d..648af0422 100644 --- a/prog/prio.go +++ b/prog/prio.go @@ -64,56 +64,55 @@ func (target *Target) calcStaticPriorities() [][]float32 { func (target *Target) calcResourceUsage() map[string]map[int]weights { uses := make(map[string]map[int]weights) - for _, c := range target.Syscalls { - foreachType(c, func(t Type, ctx typeCtx) { - switch a := t.(type) { - case *ResourceType: - if target.AuxResources[a.Desc.Name] { - noteUsage(uses, c, 0.1, ctx.Dir, "res%v", a.Desc.Name) - } else { - str := "res" - for i, k := range a.Desc.Kind { - str += "-" + k - w := 1.0 - if i < len(a.Desc.Kind)-1 { - w = 0.2 - } - noteUsage(uses, c, float32(w), ctx.Dir, str) + ForeachType(target.Syscalls, func(t Type, ctx TypeCtx) { + c := ctx.Meta + switch a := t.(type) { + case *ResourceType: + if target.AuxResources[a.Desc.Name] { + noteUsage(uses, c, 0.1, ctx.Dir, "res%v", a.Desc.Name) + } else { + str := "res" + for i, k := range a.Desc.Kind { + str += "-" + k + w := 1.0 + if i < len(a.Desc.Kind)-1 { + w = 0.2 } + noteUsage(uses, c, float32(w), ctx.Dir, str) } - case *PtrType: - if _, ok := a.Elem.(*StructType); ok { - noteUsage(uses, c, 1.0, ctx.Dir, "ptrto-%v", a.Elem.Name()) - } - if _, ok := a.Elem.(*UnionType); ok { - noteUsage(uses, c, 1.0, ctx.Dir, "ptrto-%v", a.Elem.Name()) - } - if arr, ok := a.Elem.(*ArrayType); ok { - noteUsage(uses, c, 1.0, ctx.Dir, "ptrto-%v", arr.Elem.Name()) - } - case *BufferType: - switch a.Kind { - case BufferBlobRand, BufferBlobRange, BufferText: - case BufferString: - if a.SubKind != "" { - noteUsage(uses, c, 0.2, ctx.Dir, fmt.Sprintf("str-%v", a.SubKind)) - } - case BufferFilename: - noteUsage(uses, c, 1.0, DirIn, "filename") - default: - panic("unknown buffer kind") - } - case *VmaType: - noteUsage(uses, c, 0.5, ctx.Dir, "vma") - case *IntType: - switch a.Kind { - case IntPlain, IntRange: - default: - panic("unknown int kind") + } + case *PtrType: + if _, ok := a.Elem.(*StructType); ok { + noteUsage(uses, c, 1.0, ctx.Dir, "ptrto-%v", a.Elem.Name()) + } + if _, ok := a.Elem.(*UnionType); ok { + noteUsage(uses, c, 1.0, ctx.Dir, "ptrto-%v", a.Elem.Name()) + } + if arr, ok := a.Elem.(*ArrayType); ok { + noteUsage(uses, c, 1.0, ctx.Dir, "ptrto-%v", arr.Elem.Name()) + } + case *BufferType: + switch a.Kind { + case BufferBlobRand, BufferBlobRange, BufferText: + case BufferString: + if a.SubKind != "" { + noteUsage(uses, c, 0.2, ctx.Dir, fmt.Sprintf("str-%v", a.SubKind)) } + case BufferFilename: + noteUsage(uses, c, 1.0, DirIn, "filename") + default: + panic("unknown buffer kind") } - }) - } + case *VmaType: + noteUsage(uses, c, 0.5, ctx.Dir, "vma") + case *IntType: + switch a.Kind { + case IntPlain, IntRange: + default: + panic("unknown int kind") + } + } + }) return uses } diff --git a/prog/prog_test.go b/prog/prog_test.go index 9b8f442e3..6374b6d25 100644 --- a/prog/prog_test.go +++ b/prog/prog_test.go @@ -20,15 +20,13 @@ func TestGeneration(t *testing.T) { func TestDefault(t *testing.T) { target, _, _ := initTest(t) - for _, meta := range target.Syscalls { - foreachType(meta, func(typ Type, ctx typeCtx) { - arg := typ.DefaultArg(ctx.Dir) - if !isDefault(arg) { - t.Errorf("default arg is not default: %s\ntype: %#v\narg: %#v", - typ, typ, arg) - } - }) - } + ForeachType(target.Syscalls, func(typ Type, ctx TypeCtx) { + arg := typ.DefaultArg(ctx.Dir) + if !isDefault(arg) { + t.Errorf("default arg is not default: %s\ntype: %#v\narg: %#v", + typ, typ, arg) + } + }) } func TestDefaultCallArgs(t *testing.T) { @@ -203,7 +201,7 @@ func TestSpecialStructs(t *testing.T) { t.Run(special, func(t *testing.T) { var typ Type for i := 0; i < len(target.Syscalls) && typ == nil; i++ { - foreachType(target.Syscalls[i], func(t Type, ctx typeCtx) { + ForeachCallType(target.Syscalls[i], func(t Type, ctx TypeCtx) { if ctx.Dir == DirOut { return } diff --git a/prog/rand_test.go b/prog/rand_test.go index 6f251cb7c..da0871505 100644 --- a/prog/rand_test.go +++ b/prog/rand_test.go @@ -101,22 +101,20 @@ func TestEnabledCalls(t *testing.T) { func TestSizeGenerateConstArg(t *testing.T) { target, rs, iters := initRandomTargetTest(t, "test", "64") r := newRand(target, rs) - for _, c := range target.Syscalls { - foreachType(c, func(typ Type, ctx typeCtx) { - if _, ok := typ.(*IntType); !ok { - return - } - bits := typ.TypeBitSize() - limit := uint64(1< limit { - t.Fatalf("invalid generated value: %d. (arg bitsize: %d; max value: %d)", newVal, bits, limit) - } + ForeachType(target.Syscalls, func(typ Type, ctx TypeCtx) { + if _, ok := typ.(*IntType); !ok { + return + } + bits := typ.TypeBitSize() + limit := uint64(1< limit { + t.Fatalf("invalid generated value: %d. (arg bitsize: %d; max value: %d)", newVal, bits, limit) } - }) - } + } + }) } func TestFlags(t *testing.T) { diff --git a/prog/resources.go b/prog/resources.go index b7bcecf95..311eb72dd 100644 --- a/prog/resources.go +++ b/prog/resources.go @@ -45,16 +45,14 @@ 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)) - for call, meta := range target.Syscalls { - foreachType(meta, func(typ Type, ctx typeCtx) { - switch typ1 := typ.(type) { - case *ResourceType: - if ctx.Dir != DirIn { - callsResources[call] = append(callsResources[call], typ1.Desc) - } + ForeachType(target.Syscalls, func(typ Type, ctx TypeCtx) { + switch typ1 := typ.(type) { + case *ResourceType: + if ctx.Dir != DirIn { + callsResources[ctx.Meta.ID] = append(callsResources[ctx.Meta.ID], typ1.Desc) } - }) - } + } + }) // Populate resource ctors accounting for resource compatibility. for _, res := range target.Resources { @@ -126,7 +124,7 @@ func isCompatibleResourceImpl(dst, src []string, precise bool) bool { func (target *Target) getInputResources(c *Syscall) []*ResourceDesc { var resources []*ResourceDesc - foreachType(c, func(typ Type, ctx typeCtx) { + ForeachCallType(c, func(typ Type, ctx TypeCtx) { if ctx.Dir == DirOut { return } @@ -146,7 +144,7 @@ func (target *Target) getInputResources(c *Syscall) []*ResourceDesc { func (target *Target) getOutputResources(c *Syscall) []*ResourceDesc { var resources []*ResourceDesc - foreachType(c, func(typ Type, ctx typeCtx) { + ForeachCallType(c, func(typ Type, ctx TypeCtx) { switch typ1 := typ.(type) { case *ResourceType: if ctx.Dir != DirIn { diff --git a/prog/rotation.go b/prog/rotation.go index 47ee2ca81..0171e6ace 100644 --- a/prog/rotation.go +++ b/prog/rotation.go @@ -50,7 +50,7 @@ func MakeRotator(target *Target, calls map[*Syscall]bool, rnd *rand.Rand) *Rotat } // VMAs and filenames are effectively resources for our purposes // (but they don't have ctors). - foreachType(call, func(t Type, _ typeCtx) { + ForeachCallType(call, func(t Type, _ TypeCtx) { switch a := t.(type) { case *BufferType: switch a.Kind { diff --git a/prog/target.go b/prog/target.go index 89940a61a..8999f25ac 100644 --- a/prog/target.go +++ b/prog/target.go @@ -22,7 +22,6 @@ type Target struct { Syscalls []*Syscall Resources []*ResourceDesc - Structs []*KeyedStruct Consts []ConstValue Types []Type @@ -137,8 +136,7 @@ func (target *Target) initTarget() { target.ConstMap[c.Name] = c.Value } - target.resourceMap = restoreLinks(target.Syscalls, target.Resources, target.Structs, target.Types) - target.Structs = nil + target.resourceMap = restoreLinks(target.Syscalls, target.Resources, target.Types) target.Types = nil target.SyscallMap = make(map[string]*Syscall) @@ -173,63 +171,30 @@ func (target *Target) sanitize(c *Call, fix bool) error { return nil } -func RestoreLinks(syscalls []*Syscall, resources []*ResourceDesc, structs []*KeyedStruct, types []Type) { - restoreLinks(syscalls, resources, structs, types) +func RestoreLinks(syscalls []*Syscall, resources []*ResourceDesc, types []Type) { + restoreLinks(syscalls, resources, types) } -func restoreLinks(syscalls []*Syscall, resources []*ResourceDesc, structs []*KeyedStruct, - types []Type) map[string]*ResourceDesc { +func restoreLinks(syscalls []*Syscall, resources []*ResourceDesc, types []Type) map[string]*ResourceDesc { resourceMap := make(map[string]*ResourceDesc) for _, res := range resources { resourceMap[res.Name] = res } - keyedStructs := make(map[StructKey]*StructDesc) - for _, desc := range structs { - keyedStructs[desc.Key] = desc.Desc - for i := range desc.Desc.Fields { - unref(&desc.Desc.Fields[i].Type, types) + ForeachType(syscalls, func(_ Type, ctx TypeCtx) { + if ref, ok := (*ctx.Ptr).(Ref); ok { + *ctx.Ptr = types[ref] } - } - for _, c := range syscalls { - for i := range c.Args { - unref(&c.Args[i].Type, types) - } - if c.Ret != nil { - unref(&c.Ret, types) - } - foreachType(c, func(t0 Type, _ typeCtx) { - switch t := t0.(type) { - case *PtrType: - unref(&t.Elem, types) - case *ArrayType: - unref(&t.Elem, types) - case *ResourceType: - t.Desc = resourceMap[t.TypeName] - if t.Desc == nil { - panic("no resource desc") - } - case *StructType: - t.StructDesc = keyedStructs[t.Key] - if t.StructDesc == nil { - panic("no struct desc") - } - case *UnionType: - t.StructDesc = keyedStructs[t.Key] - if t.StructDesc == nil { - panic("no union desc") - } + switch t := (*ctx.Ptr).(type) { + case *ResourceType: + t.Desc = resourceMap[t.TypeName] + if t.Desc == nil { + panic("no resource desc") } - }) - } + } + }) return resourceMap } -func unref(tp *Type, types []Type) { - if ref, ok := (*tp).(Ref); ok { - *tp = types[ref] - } -} - type Gen struct { r *randGen s *state diff --git a/prog/types.go b/prog/types.go index 4412239d3..33c7bd356 100644 --- a/prog/types.go +++ b/prog/types.go @@ -110,7 +110,6 @@ type Ref uint32 func (ti Ref) String() string { panic("prog.Ref method called") } func (ti Ref) Name() string { panic("prog.Ref method called") } -func (ti Ref) FieldName() string { panic("prog.Ref method called") } func (ti Ref) TemplateName() string { panic("prog.Ref method called") } func (ti Ref) Optional() bool { panic("prog.Ref method called") } @@ -579,8 +578,9 @@ func (t *PtrType) isDefaultArg(arg Arg) bool { } type StructType struct { - Key StructKey - *StructDesc + TypeCommon + Fields []Field + AlignAttr uint64 } func (t *StructType) String() string { @@ -606,8 +606,8 @@ func (t *StructType) isDefaultArg(arg Arg) bool { } type UnionType struct { - Key StructKey - *StructDesc + TypeCommon + Fields []Field } func (t *UnionType) String() string { @@ -623,64 +623,80 @@ func (t *UnionType) isDefaultArg(arg Arg) bool { return a.Index == 0 && isDefault(a.Option) } -type StructDesc struct { - TypeCommon - Fields []Field - AlignAttr uint64 +type ConstValue struct { + Name string + Value uint64 } -type StructKey struct { - Name string +type TypeCtx struct { + Meta *Syscall + Dir Dir + Ptr *Type } -type KeyedStruct struct { - Key StructKey - Desc *StructDesc +func ForeachType(syscalls []*Syscall, f func(t Type, ctx TypeCtx)) { + for _, meta := range syscalls { + foreachTypeImpl(meta, true, f) + } } -type ConstValue struct { - Name string - Value uint64 +func ForeachTypePost(syscalls []*Syscall, f func(t Type, ctx TypeCtx)) { + for _, meta := range syscalls { + foreachTypeImpl(meta, false, f) + } } -type typeCtx struct { - Dir Dir +func ForeachCallType(meta *Syscall, f func(t Type, ctx TypeCtx)) { + foreachTypeImpl(meta, true, f) } -func foreachType(meta *Syscall, f func(t Type, ctx typeCtx)) { - var rec func(t Type, dir Dir) - seen := make(map[*StructDesc]bool) - recStruct := func(desc *StructDesc, dir Dir) { - if seen[desc] { - return // prune recursion via pointers to structs/unions - } - seen[desc] = true - for _, f := range desc.Fields { - rec(f.Type, dir) +func foreachTypeImpl(meta *Syscall, preorder bool, f func(t Type, ctx TypeCtx)) { + // Note: we specifically don't create seen in ForeachType. + // It would prune recursion more (across syscalls), but lots of users need to + // visit each struct per-syscall (e.g. prio, used resources). + seen := make(map[Type]bool) + var rec func(*Type, Dir) + rec = func(ptr *Type, dir Dir) { + if preorder { + f(*ptr, TypeCtx{Meta: meta, Dir: dir, Ptr: ptr}) } - } - rec = func(t Type, dir Dir) { - f(t, typeCtx{Dir: dir}) - switch a := t.(type) { + switch a := (*ptr).(type) { case *PtrType: - rec(a.Elem, a.ElemDir) + rec(&a.Elem, a.ElemDir) case *ArrayType: - rec(a.Elem, dir) + rec(&a.Elem, dir) case *StructType: - recStruct(a.StructDesc, dir) + if seen[a] { + break // prune recursion via pointers to structs/unions + } + seen[a] = true + for i := range a.Fields { + rec(&a.Fields[i].Type, dir) + } case *UnionType: - recStruct(a.StructDesc, dir) - case *ResourceType, *BufferType, *VmaType, *LenType, - *FlagsType, *ConstType, *IntType, *ProcType, *CsumType: + if seen[a] { + break // prune recursion via pointers to structs/unions + } + seen[a] = true + for i := range a.Fields { + rec(&a.Fields[i].Type, dir) + } + case *ResourceType, *BufferType, *VmaType, *LenType, *FlagsType, + *ConstType, *IntType, *ProcType, *CsumType: + case Ref: + // This is only needed for pkg/compiler. default: panic("unknown type") } + if !preorder { + f(*ptr, TypeCtx{Meta: meta, Dir: dir, Ptr: ptr}) + } } - for _, field := range meta.Args { - rec(field.Type, DirIn) + for i := range meta.Args { + rec(&meta.Args[i].Type, DirIn) } if meta.Ret != nil { - rec(meta.Ret, DirOut) + rec(&meta.Ret, DirOut) } } -- cgit mrf-deployment