diff options
author | Adin Scannell <ascannell@google.com> | 2021-07-01 15:05:28 -0700 |
---|---|---|
committer | gVisor bot <gvisor-bot@google.com> | 2021-07-01 15:07:56 -0700 |
commit | 16b751b6c610ec2c5a913cb8a818e9239ee7da71 (patch) | |
tree | 5596ea010c6afbbe79d1196197cd4bfc5d517e79 /tools/checklocks/facts.go | |
parent | 570ca571805d6939c4c24b6a88660eefaf558ae7 (diff) |
Mix checklocks and atomic analyzers.
This change makes the checklocks analyzer considerable more powerful, adding:
* The ability to traverse complex structures, e.g. to have multiple nested
fields as part of the annotation.
* The ability to resolve simple anonymous functions and closures, and perform
lock analysis across these invocations. This does not apply to closures that
are passed elsewhere, since it is not possible to know the context in which
they might be invoked.
* The ability to annotate return values in addition to receivers and other
parameters, with the same complex structures noted above.
* Ignoring locking semantics for "fresh" objects, i.e. objects that are
allocated in the local frame (typically a new-style function).
* Sanity checking of locking state across block transitions and returns, to
ensure that no unexpected locks are held.
Note that initially, most of these findings are excluded by a comprehensive
nogo.yaml. The findings that are included are fundamental lock violations.
The changes here should be relatively low risk, minor refactorings to either
include necessary annotations to simplify the code structure (in general
removing closures in favor of methods) so that the analyzer can be easily
track the lock state.
This change additional includes two changes to nogo itself:
* Sanity checking of all types to ensure that the binary and ast-derived
types have a consistent objectpath, to prevent the bug above from occurring
silently (and causing much confusion). This also requires a trick in
order to ensure that serialized facts are consumable downstream. This can
be removed with https://go-review.googlesource.com/c/tools/+/331789 merged.
* A minor refactoring to isolation the objdump settings in its own package.
This was originally used to implement the sanity check above, but this
information is now being passed another way. The minor refactor is preserved
however, since it cleans up the code slightly and is minimal risk.
PiperOrigin-RevId: 382613300
Diffstat (limited to 'tools/checklocks/facts.go')
-rw-r--r-- | tools/checklocks/facts.go | 614 |
1 files changed, 614 insertions, 0 deletions
diff --git a/tools/checklocks/facts.go b/tools/checklocks/facts.go new file mode 100644 index 000000000..1a43dbbe6 --- /dev/null +++ b/tools/checklocks/facts.go @@ -0,0 +1,614 @@ +// Copyright 2020 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package checklocks + +import ( + "fmt" + "go/ast" + "go/token" + "go/types" + "regexp" + "strings" + + "golang.org/x/tools/go/ssa" +) + +// atomicAlignment is saved per type. +// +// This represents the alignment required for the type, which may +// be implied and imposed by other types within the aggregate type. +type atomicAlignment int + +// AFact implements analysis.Fact.AFact. +func (*atomicAlignment) AFact() {} + +// atomicDisposition is saved per field. +// +// This represents how the field must be accessed. It must either +// be non-atomic (default), atomic or ignored. +type atomicDisposition int + +const ( + atomicDisallow atomicDisposition = iota + atomicIgnore + atomicRequired +) + +// fieldList is a simple list of fields, used in two types below. +// +// Note that the integers in this list refer to one of two things: +// - A positive integer refers to a field index in a struct. +// - A negative integer refers to a field index in a struct, where +// that field is a pointer and must be subsequently resolved. +type fieldList []int + +// resolvedValue is an ssa.Value with additional fields. +// +// This can be resolved to a string as part of a lock state. +type resolvedValue struct { + value ssa.Value + valid bool + fieldList []int +} + +// findExtract finds a relevant extract. This must exist within the referrers +// to the call object. If this doesn't then the object which is locked is never +// consumed, and we should consider this a bug. +func findExtract(v ssa.Value, index int) (ssa.Value, bool) { + if refs := v.Referrers(); refs != nil { + for _, inst := range *refs { + if x, ok := inst.(*ssa.Extract); ok && x.Tuple == v && x.Index == index { + return inst.(ssa.Value), true + } + } + } + return nil, false +} + +// resolve resolves the given field list. +func (fl fieldList) resolve(v ssa.Value) (rv resolvedValue) { + return resolvedValue{ + value: v, + fieldList: fl, + valid: true, + } +} + +// valueAsString returns a string representing this value. +// +// This must align with how the string is generated in valueAsString. +func (rv resolvedValue) valueAsString(ls *lockState) string { + typ := rv.value.Type() + s := ls.valueAsString(rv.value) + for i, fieldNumber := range rv.fieldList { + switch { + case fieldNumber > 0: + field, ok := findField(typ, fieldNumber-1) + if !ok { + // This can't be resolved, return for debugging. + return fmt.Sprintf("{%s+%v}", s, rv.fieldList[i:]) + } + s = fmt.Sprintf("&(%s.%s)", s, field.Name()) + typ = field.Type() + case fieldNumber < 1: + field, ok := findField(typ, (-fieldNumber)-1) + if !ok { + // See above. + return fmt.Sprintf("{%s+%v}", s, rv.fieldList[i:]) + } + s = fmt.Sprintf("*(&(%s.%s))", s, field.Name()) + typ = field.Type() + } + } + return s +} + +// lockFieldFacts apply on every struct field. +type lockFieldFacts struct { + // IsMutex is true if the field is of type sync.Mutex. + IsMutex bool + + // IsRWMutex is true if the field is of type sync.RWMutex. + IsRWMutex bool + + // IsPointer indicates if the field is a pointer. + IsPointer bool + + // FieldNumber is the number of this field in the struct. + FieldNumber int +} + +// AFact implements analysis.Fact.AFact. +func (*lockFieldFacts) AFact() {} + +// lockGuardFacts contains guard information. +type lockGuardFacts struct { + // GuardedBy is the set of locks that are guarding this field. The key + // is the original annotation value, and the field list is the object + // traversal path. + GuardedBy map[string]fieldList + + // AtomicDisposition is the disposition for this field. Note that this + // can affect the interpretation of the GuardedBy field above, see the + // relevant comment. + AtomicDisposition atomicDisposition +} + +// AFact implements analysis.Fact.AFact. +func (*lockGuardFacts) AFact() {} + +// functionGuard is used by lockFunctionFacts, below. +type functionGuard struct { + // ParameterNumber is the index of the object that contains the + // guarding mutex. From this parameter, a walk is performed + // subsequently using the resolve method. + // + // Note that is ParameterNumber is beyond the size of parameters, then + // it may return to a return value. This applies only for the Acquires + // relation below. + ParameterNumber int + + // NeedsExtract is used in the case of a return value, and indicates + // that the field must be extracted from a tuple. + NeedsExtract bool + + // FieldList is the traversal path to the object. + FieldList fieldList +} + +// resolveReturn resolves a return value. +// +// Precondition: rv is either an ssa.Value, or an *ssa.Return. +func (fg *functionGuard) resolveReturn(rv interface{}, args int) resolvedValue { + if rv == nil { + // For defers and other objects, this may be nil. This is + // handled in state.go in the actual lock checking logic. + return resolvedValue{ + value: nil, + valid: false, + } + } + index := fg.ParameterNumber - args + // If this is a *ssa.Return object, i.e. we are analyzing the function + // and not the call site, then we can just pull the result directly. + if r, ok := rv.(*ssa.Return); ok { + return fg.FieldList.resolve(r.Results[index]) + } + if fg.NeedsExtract { + // Resolve on the extracted field, this is necessary if the + // type here is not an explicit return. Note that rv must be an + // ssa.Value, since it is not an *ssa.Return. + v, ok := findExtract(rv.(ssa.Value), index) + if !ok { + return resolvedValue{ + value: v, + valid: false, + } + } + return fg.FieldList.resolve(v) + } + if index != 0 { + // This should not happen, NeedsExtract should always be set. + panic("NeedsExtract is false, but return value index is non-zero") + } + // Resolve on the single return. + return fg.FieldList.resolve(rv.(ssa.Value)) +} + +// resolveStatic returns an ssa.Value representing the given field. +// +// Precondition: per resolveReturn. +func (fg *functionGuard) resolveStatic(fn *ssa.Function, rv interface{}) resolvedValue { + if fg.ParameterNumber >= len(fn.Params) { + return fg.resolveReturn(rv, len(fn.Params)) + } + return fg.FieldList.resolve(fn.Params[fg.ParameterNumber]) +} + +// resolveCall returns an ssa.Value representing the given field. +func (fg *functionGuard) resolveCall(args []ssa.Value, rv ssa.Value) resolvedValue { + if fg.ParameterNumber >= len(args) { + return fg.resolveReturn(rv, len(args)) + } + return fg.FieldList.resolve(args[fg.ParameterNumber]) +} + +// lockFunctionFacts apply on every method. +type lockFunctionFacts struct { + // HeldOnEntry tracks the names and number of parameter (including receiver) + // lockFuncfields that guard calls to this function. + // + // The key is the name specified in the checklocks annotation. e.g given + // the following code: + // + // ``` + // type A struct { + // mu sync.Mutex + // a int + // } + // + // // +checklocks:a.mu + // func xyz(a *A) {..} + // ``` + // + // '`+checklocks:a.mu' will result in an entry in this map as shown below. + // HeldOnEntry: {"a.mu" => {ParameterNumber: 0, FieldNumbers: {0}} + // + // Unlikely lockFieldFacts, there is no atomic interpretation. + HeldOnEntry map[string]functionGuard + + // HeldOnExit tracks the locks that are expected to be held on exit. + HeldOnExit map[string]functionGuard + + // Ignore means this function has local analysis ignores. + // + // This is not used outside the local package. + Ignore bool +} + +// AFact implements analysis.Fact.AFact. +func (*lockFunctionFacts) AFact() {} + +// checkGuard validates the guardName. +func (lff *lockFunctionFacts) checkGuard(pc *passContext, d *ast.FuncDecl, guardName string, allowReturn bool) (functionGuard, bool) { + if _, ok := lff.HeldOnEntry[guardName]; ok { + pc.maybeFail(d.Pos(), "annotation %s specified more than once, already required", guardName) + return functionGuard{}, false + } + if _, ok := lff.HeldOnExit[guardName]; ok { + pc.maybeFail(d.Pos(), "annotation %s specified more than once, already acquired", guardName) + return functionGuard{}, false + } + fg, ok := pc.findFunctionGuard(d, guardName, allowReturn) + return fg, ok +} + +// addGuardedBy adds a field to both HeldOnEntry and HeldOnExit. +func (lff *lockFunctionFacts) addGuardedBy(pc *passContext, d *ast.FuncDecl, guardName string) { + if fg, ok := lff.checkGuard(pc, d, guardName, false /* allowReturn */); ok { + if lff.HeldOnEntry == nil { + lff.HeldOnEntry = make(map[string]functionGuard) + } + if lff.HeldOnExit == nil { + lff.HeldOnExit = make(map[string]functionGuard) + } + lff.HeldOnEntry[guardName] = fg + lff.HeldOnExit[guardName] = fg + } +} + +// addAcquires adds a field to HeldOnExit. +func (lff *lockFunctionFacts) addAcquires(pc *passContext, d *ast.FuncDecl, guardName string) { + if fg, ok := lff.checkGuard(pc, d, guardName, true /* allowReturn */); ok { + if lff.HeldOnExit == nil { + lff.HeldOnExit = make(map[string]functionGuard) + } + lff.HeldOnExit[guardName] = fg + } +} + +// addReleases adds a field to HeldOnEntry. +func (lff *lockFunctionFacts) addReleases(pc *passContext, d *ast.FuncDecl, guardName string) { + if fg, ok := lff.checkGuard(pc, d, guardName, false /* allowReturn */); ok { + if lff.HeldOnEntry == nil { + lff.HeldOnEntry = make(map[string]functionGuard) + } + lff.HeldOnEntry[guardName] = fg + } +} + +// fieldListFor returns the fieldList for the given object. +func (pc *passContext) fieldListFor(pos token.Pos, fieldObj types.Object, index int, fieldName string, checkMutex bool) (int, bool) { + var lff lockFieldFacts + if !pc.pass.ImportObjectFact(fieldObj, &lff) { + // This should not happen: we export facts for all fields. + panic(fmt.Sprintf("no lockFieldFacts available for field %s", fieldName)) + } + // Check that it is indeed a mutex. + if checkMutex && !lff.IsMutex && !lff.IsRWMutex { + pc.maybeFail(pos, "field %s is not a mutex or an rwmutex", fieldName) + return 0, false + } + // Return the resolution path. + if lff.IsPointer { + return -(index + 1), true + } + return (index + 1), true +} + +// resolveOneField resolves a field in a single struct. +func (pc *passContext) resolveOneField(pos token.Pos, structType *types.Struct, fieldName string, checkMutex bool) (fl fieldList, fieldObj types.Object, ok bool) { + // Scan to match the next field. + for i := 0; i < structType.NumFields(); i++ { + fieldObj := structType.Field(i) + if fieldObj.Name() != fieldName { + continue + } + flOne, ok := pc.fieldListFor(pos, fieldObj, i, fieldName, checkMutex) + if !ok { + return nil, nil, false + } + fl = append(fl, flOne) + return fl, fieldObj, true + } + // Is this an embed? + for i := 0; i < structType.NumFields(); i++ { + fieldObj := structType.Field(i) + if !fieldObj.Embedded() { + continue + } + // Is this an embedded struct? + structType, ok := resolveStruct(fieldObj.Type()) + if !ok { + continue + } + // Need to check that there is a resolution path. If there is + // no resolution path that's not a failure: we just continue + // scanning the next embed to find a match. + flEmbed, okEmbed := pc.fieldListFor(pos, fieldObj, i, fieldName, false) + flCont, fieldObjCont, okCont := pc.resolveOneField(pos, structType, fieldName, checkMutex) + if okEmbed && okCont { + fl = append(fl, flEmbed) + fl = append(fl, flCont...) + return fl, fieldObjCont, true + } + } + pc.maybeFail(pos, "field %s does not exist", fieldName) + return nil, nil, false +} + +// resolveField resolves a set of fields given a string, such a 'a.b.c'. +// +// Note that this checks that the final element is a mutex of some kind, and +// will fail appropriately. +func (pc *passContext) resolveField(pos token.Pos, structType *types.Struct, parts []string) (fl fieldList, ok bool) { + for partNumber, fieldName := range parts { + flOne, fieldObj, ok := pc.resolveOneField(pos, structType, fieldName, partNumber >= len(parts)-1 /* checkMutex */) + if !ok { + // Error already reported. + return nil, false + } + fl = append(fl, flOne...) + if partNumber < len(parts)-1 { + // Traverse to the next type. + structType, ok = resolveStruct(fieldObj.Type()) + if !ok { + pc.maybeFail(pos, "invalid intermediate field %s", fieldName) + return fl, false + } + } + } + return fl, true +} + +var ( + mutexRE = regexp.MustCompile("((.*/)|^)sync.(CrossGoroutineMutex|Mutex)") + rwMutexRE = regexp.MustCompile("((.*/)|^)sync.(CrossGoroutineRWMutex|RWMutex)") +) + +// exportLockFieldFacts finds all struct fields that are mutexes, and ensures +// that they are annotated approperly. +// +// This information is consumed subsequently by exportLockGuardFacts, and this +// function must be called first on all structures. +func (pc *passContext) exportLockFieldFacts(ts *ast.TypeSpec, ss *ast.StructType) { + structType := pc.pass.TypesInfo.TypeOf(ts.Name).Underlying().(*types.Struct) + for i := range ss.Fields.List { + lff := &lockFieldFacts{ + FieldNumber: i, + } + // We use HasSuffix below because fieldType can be fully + // qualified with the package name eg for the gvisor sync + // package mutex fields have the type: + // "<package path>/sync/sync.Mutex" + fieldObj := structType.Field(i) + s := fieldObj.Type().String() + switch { + case mutexRE.MatchString(s): + lff.IsMutex = true + case rwMutexRE.MatchString(s): + lff.IsRWMutex = true + } + // Save whether this is a pointer. + _, lff.IsPointer = fieldObj.Type().Underlying().(*types.Pointer) + // We must always export the lockFieldFacts, since traversal + // can take place along any object in the struct. + pc.pass.ExportObjectFact(fieldObj, lff) + } +} + +// exportLockGuardFacts finds all relevant guard information for structures. +// +// This function requires exportLockFieldFacts be called first on all +// structures. +func (pc *passContext) exportLockGuardFacts(ts *ast.TypeSpec, ss *ast.StructType) { + structType := pc.pass.TypesInfo.TypeOf(ts.Name).Underlying().(*types.Struct) + for i, field := range ss.Fields.List { + if field.Doc == nil { + continue + } + var ( + lff lockFieldFacts + lgf lockGuardFacts + ) + pc.pass.ImportObjectFact(structType.Field(i), &lff) + fieldObj := structType.Field(i) + for _, l := range field.Doc.List { + pc.extractAnnotations(l.Text, map[string]func(string){ + checkAtomicAnnotation: func(string) { + switch lgf.AtomicDisposition { + case atomicRequired: + pc.maybeFail(fieldObj.Pos(), "annotation is redundant, already atomic required") + case atomicIgnore: + pc.maybeFail(fieldObj.Pos(), "annotation is contradictory, already atomic ignored") + } + lgf.AtomicDisposition = atomicRequired + }, + checkLocksIgnore: func(string) { + switch lgf.AtomicDisposition { + case atomicIgnore: + pc.maybeFail(fieldObj.Pos(), "annotation is redundant, already atomic ignored") + case atomicRequired: + pc.maybeFail(fieldObj.Pos(), "annotation is contradictory, already atomic required") + } + lgf.AtomicDisposition = atomicIgnore + }, + checkLocksAnnotation: func(guardName string) { + // Check for a duplicate annotation. + if _, ok := lgf.GuardedBy[guardName]; ok { + pc.maybeFail(fieldObj.Pos(), "annotation %s specified more than once", guardName) + return + } + fl, ok := pc.resolveField(fieldObj.Pos(), structType, strings.Split(guardName, ".")) + if ok { + // If we successfully resolved + // the field, then save it. + if lgf.GuardedBy == nil { + lgf.GuardedBy = make(map[string]fieldList) + } + lgf.GuardedBy[guardName] = fl + } + }, + }) + } + // Save only if there is something meaningful. + if len(lgf.GuardedBy) > 0 || lgf.AtomicDisposition != atomicDisallow { + pc.pass.ExportObjectFact(structType.Field(i), &lgf) + } + } +} + +// countFields gives an accurate field count, according for unnamed arguments +// and return values and the compact identifier format. +func countFields(fl []*ast.Field) (count int) { + for _, field := range fl { + if len(field.Names) == 0 { + count++ + continue + } + count += len(field.Names) + } + return +} + +// matchFieldList attempts to match the given field. +func (pc *passContext) matchFieldList(pos token.Pos, fl []*ast.Field, guardName string) (functionGuard, bool) { + parts := strings.Split(guardName, ".") + parameterName := parts[0] + parameterNumber := 0 + for _, field := range fl { + // See countFields, above. + if len(field.Names) == 0 { + parameterNumber++ + continue + } + for _, name := range field.Names { + if name.Name != parameterName { + parameterNumber++ + continue + } + ptrType, ok := pc.pass.TypesInfo.TypeOf(field.Type).Underlying().(*types.Pointer) + if !ok { + // Since mutexes cannot be copied we only care + // about parameters that are pointer types when + // checking for guards. + pc.maybeFail(pos, "parameter name %s does not refer to a pointer type", parameterName) + return functionGuard{}, false + } + structType, ok := ptrType.Elem().Underlying().(*types.Struct) + if !ok { + // Fields can only be in named structures. + pc.maybeFail(pos, "parameter name %s does not refer to a pointer to a struct", parameterName) + return functionGuard{}, false + } + fg := functionGuard{ + ParameterNumber: parameterNumber, + } + fl, ok := pc.resolveField(pos, structType, parts[1:]) + fg.FieldList = fl + return fg, ok // If ok is false, already failed. + } + } + return functionGuard{}, false +} + +// findFunctionGuard identifies the parameter number and field number for a +// particular string of the 'a.b'. +// +// This function will report any errors directly. +func (pc *passContext) findFunctionGuard(d *ast.FuncDecl, guardName string, allowReturn bool) (functionGuard, bool) { + var ( + parameterList []*ast.Field + returnList []*ast.Field + ) + if d.Recv != nil { + parameterList = append(parameterList, d.Recv.List...) + } + if d.Type.Params != nil { + parameterList = append(parameterList, d.Type.Params.List...) + } + if fg, ok := pc.matchFieldList(d.Pos(), parameterList, guardName); ok { + return fg, ok + } + if allowReturn { + if d.Type.Results != nil { + returnList = append(returnList, d.Type.Results.List...) + } + if fg, ok := pc.matchFieldList(d.Pos(), returnList, guardName); ok { + // Fix this up to apply to the return value, as noted + // in fg.ParameterNumber. For the ssa analysis, we must + // record whether this has multiple results, since + // *ssa.Call indicates: "The Call instruction yields + // the function result if there is exactly one. + // Otherwise it returns a tuple, the components of + // which are accessed via Extract." + fg.ParameterNumber += countFields(parameterList) + fg.NeedsExtract = countFields(returnList) > 1 + return fg, ok + } + } + // We never saw a matching parameter. + pc.maybeFail(d.Pos(), "annotation %s does not have a matching parameter", guardName) + return functionGuard{}, false +} + +// exportFunctionFacts exports relevant function findings. +func (pc *passContext) exportFunctionFacts(d *ast.FuncDecl) { + if d.Doc == nil || d.Doc.List == nil { + return + } + var lff lockFunctionFacts + for _, l := range d.Doc.List { + pc.extractAnnotations(l.Text, map[string]func(string){ + checkLocksIgnore: func(string) { + // Note that this applies to all atomic + // analysis as well. There is no provided way + // to selectively ignore only lock analysis or + // atomic analysis, as we expect this use to be + // extremely rare. + lff.Ignore = true + }, + checkLocksAnnotation: func(guardName string) { lff.addGuardedBy(pc, d, guardName) }, + checkLocksAcquires: func(guardName string) { lff.addAcquires(pc, d, guardName) }, + checkLocksReleases: func(guardName string) { lff.addReleases(pc, d, guardName) }, + }) + } + + // Export the function facts if there is anything to save. + if lff.Ignore || len(lff.HeldOnEntry) > 0 || len(lff.HeldOnExit) > 0 { + funcObj := pc.pass.TypesInfo.Defs[d.Name].(*types.Func) + pc.pass.ExportObjectFact(funcObj, &lff) + } +} |