1 // Copyright 2022 The gVisor Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 15 //go:build lockdep
16 // +build lockdep
17 18 package locking
19 20 import (
21 "fmt"
22 "reflect"
23 "strings"
24 25 "gvisor.dev/gvisor/pkg/goid"
26 "gvisor.dev/gvisor/pkg/log"
27 )
28 29 // NewMutexClass allocates a new mutex class.
30 func NewMutexClass(t reflect.Type, lockNames []string) *MutexClass {
31 c := &MutexClass{
32 typ: t,
33 nestedLockNames: lockNames,
34 nestedLockClasses: make([]*MutexClass, len(lockNames)),
35 }
36 for i := range lockNames {
37 c.nestedLockClasses[i] = NewMutexClass(t, nil)
38 c.nestedLockClasses[i].lockName = lockNames[i]
39 }
40 return c
41 }
42 43 // MutexClass describes dependencies of a specific class.
44 type MutexClass struct {
45 // The type of the mutex.
46 typ reflect.Type
47 48 // Name of the nested lock of the above type.
49 lockName string
50 51 // ancestors are locks that are locked before the current class.
52 ancestors ancestorsAtomicPtrMap
53 // nestedLockNames is a list of names for nested locks which are considered difference instances
54 // of the same lock class.
55 nestedLockNames []string
56 // namedLockClasses is a list of MutexClass instances of the same mutex class, but that are
57 // considered OK to lock simultaneously with each other, as well as with this mutex class.
58 // This is used for nested locking, where multiple instances of the same lock class are used
59 // simultaneously.
60 // Maps one-to-one with nestedLockNames.
61 nestedLockClasses []*MutexClass
62 }
63 64 func (m *MutexClass) String() string {
65 if m.lockName == "" {
66 return m.typ.String()
67 }
68 return fmt.Sprintf("%s[%s]", m.typ.String(), m.lockName)
69 }
70 71 type goroutineLocks map[*MutexClass]bool
72 73 var routineLocks goroutineLocksAtomicPtrMap
74 75 // maxChainLen is the maximum length of a lock chain.
76 const maxChainLen = 32
77 78 // checkLock checks that class isn't in the ancestors of prevClass.
79 func checkLock(class *MutexClass, prevClass *MutexClass, chain []*MutexClass) {
80 chain = append(chain, prevClass)
81 if len(chain) >= maxChainLen {
82 // It can be a race condition with another thread that added
83 // the lock to the graph but don't complete the validation.
84 var b strings.Builder
85 fmt.Fprintf(&b, "WARNING: The maximum lock depth has been reached: %s", chain[0])
86 for i := 1; i < len(chain); i++ {
87 fmt.Fprintf(&b, "-> %s", chain[i])
88 }
89 log.Warningf("%s", b.String())
90 return
91 }
92 if c := prevClass.ancestors.Load(class); c != nil {
93 var b strings.Builder
94 fmt.Fprintf(&b, "WARNING: circular locking detected: %s -> %s:\n%s\n",
95 chain[0], class, log.LocalStack(3))
96 97 fmt.Fprintf(&b, "known lock chain: ")
98 c := class
99 for i := len(chain) - 1; i >= 0; i-- {
100 fmt.Fprintf(&b, "%s -> ", c)
101 c = chain[i]
102 }
103 fmt.Fprintf(&b, "%s\n", chain[0])
104 c = class
105 for i := len(chain) - 1; i >= 0; i-- {
106 fmt.Fprintf(&b, "\n====== %s -> %s =====\n%s",
107 c, chain[i], *chain[i].ancestors.Load(c))
108 c = chain[i]
109 }
110 panic(b.String())
111 }
112 prevClass.ancestors.RangeRepeatable(func(parentClass *MutexClass, stacks *string) bool {
113 // The recursion is fine here. If it fails, you need to reduce
114 // a number of nested locks.
115 checkLock(class, parentClass, chain)
116 return true
117 })
118 }
119 120 // AddGLock records a lock to the current goroutine and updates dependencies.
121 func AddGLock(class *MutexClass, lockNameIndex int) {
122 gid := goid.Get()
123 124 if lockNameIndex != -1 {
125 class = class.nestedLockClasses[lockNameIndex]
126 }
127 currentLocks := routineLocks.Load(gid)
128 if currentLocks == nil {
129 locks := goroutineLocks(make(map[*MutexClass]bool))
130 locks[class] = true
131 routineLocks.Store(gid, &locks)
132 return
133 }
134 135 if (*currentLocks)[class] {
136 panic(fmt.Sprintf("nested locking: %s:\n%s", class, log.LocalStack(2)))
137 }
138 (*currentLocks)[class] = true
139 // Check dependencies and add locked mutexes to the ancestors list.
140 for prevClass := range *currentLocks {
141 if prevClass == class {
142 continue
143 }
144 checkLock(class, prevClass, nil)
145 146 if c := class.ancestors.Load(prevClass); c == nil {
147 stacks := string(log.LocalStack(2))
148 class.ancestors.Store(prevClass, &stacks)
149 }
150 }
151 }
152 153 // DelGLock deletes a lock from the current goroutine.
154 func DelGLock(class *MutexClass, lockNameIndex int) {
155 if lockNameIndex != -1 {
156 class = class.nestedLockClasses[lockNameIndex]
157 }
158 gid := goid.Get()
159 currentLocks := routineLocks.Load(gid)
160 if currentLocks == nil {
161 panic("the current goroutine doesn't have locks")
162 }
163 if _, ok := (*currentLocks)[class]; !ok {
164 var b strings.Builder
165 fmt.Fprintf(&b, "Lock not held: %s:\n", class)
166 fmt.Fprintf(&b, "Current stack:\n%s\n", string(log.LocalStack(2)))
167 fmt.Fprintf(&b, "Current locks:\n")
168 for c := range *currentLocks {
169 heldToClass := class.ancestors.Load(c)
170 classToHeld := c.ancestors.Load(class)
171 if heldToClass == nil && classToHeld == nil {
172 fmt.Fprintf(&b, "\t- Holding lock: %s (no dependency to/from %s found)\n", c, class)
173 } else if heldToClass != nil && classToHeld != nil {
174 fmt.Fprintf(&b, "\t- Holding lock: %s (mutual dependency with %s found, this should never happen)\n", c, class)
175 } else if heldToClass != nil && classToHeld == nil {
176 fmt.Fprintf(&b, "\t- Holding lock: %s (dependency: %s -> %s)\n", c, c, class)
177 fmt.Fprintf(&b, "%s\n\n", *heldToClass)
178 } else if heldToClass == nil && classToHeld != nil {
179 fmt.Fprintf(&b, "\t- Holding lock: %s (dependency: %s -> %s)\n", c, class, c)
180 fmt.Fprintf(&b, "%s\n\n", *classToHeld)
181 }
182 }
183 fmt.Fprintf(&b, "** End of locks held **\n")
184 panic(b.String())
185 }
186 187 delete(*currentLocks, class)
188 if len(*currentLocks) == 0 {
189 routineLocks.Store(gid, nil)
190 }
191 }
192