diff options
Diffstat (limited to 'tools/checklocks/facts.go')
| -rw-r--r-- | tools/checklocks/facts.go | 641 |
1 files changed, 0 insertions, 641 deletions
diff --git a/tools/checklocks/facts.go b/tools/checklocks/facts.go deleted file mode 100644 index fd681adc3..000000000 --- a/tools/checklocks/facts.go +++ /dev/null @@ -1,641 +0,0 @@ -// 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 - - // Exclusive indicates an exclusive lock is required. - Exclusive bool -} - -// 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, exclusive bool, 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, exclusive, allowReturn) - return fg, ok -} - -// addGuardedBy adds a field to both HeldOnEntry and HeldOnExit. -func (lff *lockFunctionFacts) addGuardedBy(pc *passContext, d *ast.FuncDecl, guardName string, exclusive bool) { - if fg, ok := lff.checkGuard(pc, d, guardName, exclusive, 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, exclusive bool) { - if fg, ok := lff.checkGuard(pc, d, guardName, exclusive, 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, exclusive bool) { - if fg, ok := lff.checkGuard(pc, d, guardName, exclusive, 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, exclusive 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 - } - if checkMutex && !exclusive && !lff.IsRWMutex { - pc.maybeFail(pos, "field %s must be a RWMutex, but it is not", 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, exclusive 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, exclusive) - 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, exclusive) - flCont, fieldObjCont, okCont := pc.resolveOneField(pos, structType, fieldName, checkMutex, exclusive) - 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, exclusive bool) (fl fieldList, ok bool) { - for partNumber, fieldName := range parts { - flOne, fieldObj, ok := pc.resolveOneField(pos, structType, fieldName, partNumber >= len(parts)-1 /* checkMutex */, exclusive) - 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 properly. -// -// This information is consumed subsequently by exportLockGuardFacts, and this -// function must be called first on all structures. -func (pc *passContext) exportLockFieldFacts(structType *types.Struct, ss *ast.StructType) { - for i, field := 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) - // If this is an anonymous type, then we won't discover it via - // the AST global declarations. We can recurse from here. - if ss, ok := field.Type.(*ast.StructType); ok { - if st, ok := fieldObj.Type().(*types.Struct); ok { - pc.exportLockFieldFacts(st, ss) - } - } - } -} - -// exportLockGuardFacts finds all relevant guard information for structures. -// -// This function requires exportLockFieldFacts be called first on all -// structures. -func (pc *passContext) exportLockGuardFacts(structType *types.Struct, ss *ast.StructType) { - for i, field := range ss.Fields.List { - fieldObj := structType.Field(i) - if field.Doc != nil { - var ( - lff lockFieldFacts - lgf lockGuardFacts - ) - pc.pass.ImportObjectFact(structType.Field(i), &lff) - 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, "."), true /* exclusive */) - 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 - } - }, - // N.B. We support only the vanilla - // annotation on individual fields. If - // the field is a read lock, then we - // will allow read access by default. - checkLocksAnnotationRead: func(guardName string) { - pc.maybeFail(fieldObj.Pos(), "annotation %s not legal on fields", guardName) - }, - }) - } - // Save only if there is something meaningful. - if len(lgf.GuardedBy) > 0 || lgf.AtomicDisposition != atomicDisallow { - pc.pass.ExportObjectFact(structType.Field(i), &lgf) - } - } - // See above, for anonymous structure fields. - if ss, ok := field.Type.(*ast.StructType); ok { - if st, ok := fieldObj.Type().(*types.Struct); ok { - pc.exportLockGuardFacts(st, ss) - } - } - } -} - -// 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, exclusive bool) (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, - Exclusive: exclusive, - } - fl, ok := pc.resolveField(pos, structType, parts[1:], exclusive) - 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, exclusive bool, 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, exclusive); 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, exclusive); 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, true /* exclusive */) }, - checkLocksAnnotationRead: func(guardName string) { lff.addGuardedBy(pc, d, guardName, false /* exclusive */) }, - checkLocksAcquires: func(guardName string) { lff.addAcquires(pc, d, guardName, true /* exclusive */) }, - checkLocksAcquiresRead: func(guardName string) { lff.addAcquires(pc, d, guardName, false /* exclusive */) }, - checkLocksReleases: func(guardName string) { lff.addReleases(pc, d, guardName, true /* exclusive */) }, - checkLocksReleasesRead: func(guardName string) { lff.addReleases(pc, d, guardName, false /* exclusive */) }, - }) - } - - // 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) - } -} |