1 // Copyright 2018 The Fuchsia Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #pragma once
6 
7 #include <stdint.h>
8 #include <zircon/assert.h>
9 #include <zircon/compiler.h>
10 
11 #include <fbl/intrusive_double_list.h>
12 
13 #include <lockdep/common.h>
14 #include <lockdep/lock_class_state.h>
15 
16 #include <utility>
17 
18 namespace lockdep {
19 
20 // Linked list entry that tracks a lock acquired by a thread. Each thread
21 // maintains a local list of AcquiredLockEntry instances. AcquiredLockEntry is
22 // intended to be allocated on the stack as a member of a RAII type to manage
23 // the lifetime of the acquisition. Consequently, this type is move-only to
24 // permit moving the context to a different stack frame. However, an instance
25 // must only be manipulated by the thread that created it.
26 class AcquiredLockEntry : public fbl::DoublyLinkedListable<AcquiredLockEntry*> {
27 public:
28     AcquiredLockEntry() = default;
AcquiredLockEntry(LockClassId id,uintptr_t order)29     AcquiredLockEntry(LockClassId id, uintptr_t order)
30         : id_{id}, order_{order} {}
31 
~AcquiredLockEntry()32     ~AcquiredLockEntry() {
33         ZX_DEBUG_ASSERT(!InContainer());
34     }
35 
36     AcquiredLockEntry(const AcquiredLockEntry&) = delete;
37     AcquiredLockEntry& operator=(const AcquiredLockEntry&) = delete;
38 
AcquiredLockEntry(AcquiredLockEntry && other)39     AcquiredLockEntry(AcquiredLockEntry&& other) { *this = std::move(other); }
40     AcquiredLockEntry& operator=(AcquiredLockEntry&& other) {
41         if (this != &other) {
42             ZX_ASSERT(!InContainer());
43 
44             if (other.InContainer())
45                 Replace(&other);
46 
47             id_ = other.id_;
48             order_ = other.order_;
49 
50             other.id_ = kInvalidLockClassId;
51             other.order_ = 0;
52         }
53         return *this;
54     }
55 
id()56     LockClassId id() const { return id_; }
order()57     uintptr_t order() const { return order_; }
58 
59 private:
60     friend class ThreadLockState;
61 
62     // Replaces the given entry in the list with this entry.
63     void Replace(AcquiredLockEntry* target);
64 
65     LockClassId id_{kInvalidLockClassId};
66     uintptr_t order_{0};
67 };
68 
69 // Tracks the locks held by a thread and updates accounting during acquire and
70 // release operations.
71 class ThreadLockState {
72 public:
73     // Returns the ThreadLockState instance for the current thread.
Get()74     static ThreadLockState* Get() {
75         return SystemGetThreadLockState();
76     }
77 
78     // Attempts to add the given lock class to the acquired lock list. Lock
79     // ordering and other checks are performed here.
Acquire(AcquiredLockEntry * lock_entry)80     void Acquire(AcquiredLockEntry* lock_entry) {
81         if (LockClassState::IsTrackingDisabled(lock_entry->id()))
82             return;
83 
84         if (LockClassState::IsReportingDisabled(lock_entry->id()))
85             reporting_disabled_count_++;
86 
87         // Scans the acquired lock list and performs the following operations:
88         //  1. Checks that the given lock class is not already in the list unless
89         //     the lock class is nestable or address ordering is correctly applied.
90         //  2. Checks that the given lock class is not in the dependency set for
91         //     any lock class already in the list.
92         //  3. Checks that irq-safe locks are not held when acquiring an irq-unsafe
93         //     lock.
94         //  4. Adds each lock class already in the list to the dependency set of the
95         //     given lock class.
96         last_result_ = LockResult::Success;
97         for (AcquiredLockEntry& entry : acquired_locks_) {
98             if (entry.id() == lock_entry->id()) {
99                 if (lock_entry->order() <= entry.order()) {
100                     if (!LockClassState::IsNestable(lock_entry->id()) && lock_entry->order() == 0)
101                         Report(lock_entry, &entry, LockResult::AlreadyAcquired);
102                     else
103                         Report(lock_entry, &entry, LockResult::InvalidNesting);
104                 }
105             } else {
106                 const LockResult result =
107                     LockClassState::AddLockClass(lock_entry->id(), entry.id());
108                 if (result == LockResult::Success) {
109                     // A new edge has been added to the graph, trigger a loop
110                     // detection pass.
111                     TriggerLoopDetection();
112                 } else if (result == LockResult::MaxLockDependencies) {
113                     // If the dependency set is full report error.
114                     Report(lock_entry, &entry, result);
115                 } else /* if (result == LockResult::DependencyExists) */ {
116                     // Nothing to do when there are no changes to the graph.
117                 }
118 
119                 // The following tests only need to be run when a new edge is
120                 // added for this ordered pair of locks; when the edge already
121                 // exists these tests have been performed before.
122                 if (result == LockResult::Success) {
123                     const bool entry_irqsafe = LockClassState::IsIrqSafe(entry.id());
124                     const bool lock_entry_irqsafe = LockClassState::IsIrqSafe(lock_entry->id());
125                     if (entry_irqsafe && !lock_entry_irqsafe)
126                         Report(lock_entry, &entry, LockResult::InvalidIrqSafety);
127 
128                     if (LockClassState::HasLockClass(entry.id(), lock_entry->id()))
129                         Report(lock_entry, &entry, LockResult::OutOfOrder);
130                 }
131             }
132         }
133 
134         if (!LockClassState::IsActiveListDisabled(lock_entry->id()))
135             acquired_locks_.push_back(lock_entry);
136     }
137 
138     // Removes the given lock entry from the acquired lock list.
Release(AcquiredLockEntry * entry)139     void Release(AcquiredLockEntry* entry) {
140         if (LockClassState::IsTrackingDisabled(entry->id()))
141             return;
142 
143         if (LockClassState::IsReportingDisabled(entry->id()))
144             reporting_disabled_count_--;
145 
146         if (entry->InContainer())
147             acquired_locks_.erase(*entry);
148     }
149 
150     // Returns result of the last Acquire operation for testing.
last_result()151     LockResult last_result() const { return last_result_; }
152 
reporting_disabled()153     bool reporting_disabled() const { return reporting_disabled_count_ > 0; }
154 
155 private:
156     friend ThreadLockState* SystemGetThreadLockState();
157     friend void SystemInitThreadLockState(ThreadLockState*);
158     friend void AcquiredLockEntry::Replace(AcquiredLockEntry*);
159 
160     ThreadLockState() = default;
161     ~ThreadLockState() = default;
162     ThreadLockState(const ThreadLockState&) = delete;
163     void operator=(const ThreadLockState&) = delete;
164 
165     // Replaces the given original entry with the replacement entry. This permits
166     // lock entries to be allocated on the stack and migrate between stack
167     // frames if lock guards are moved or returned.
168     //
169     // The original entry must already be on the acquired locks list and the
170     // replacement entry must not be on any list.
Replace(AcquiredLockEntry * original,AcquiredLockEntry * replacement)171     void Replace(AcquiredLockEntry* original, AcquiredLockEntry* replacement) {
172         acquired_locks_.replace(*original, replacement);
173     }
174 
175     // Reports a detected lock violation using the system-defined runtime handler.
Report(AcquiredLockEntry * bad_entry,AcquiredLockEntry * conflicting_entry,LockResult result)176     void Report(AcquiredLockEntry* bad_entry, AcquiredLockEntry* conflicting_entry,
177                 LockResult result) {
178         if ((result == LockResult::AlreadyAcquired ||
179              result == LockResult::InvalidNesting) &&
180             LockClassState::IsReAcquireFatal(bad_entry->id())) {
181             SystemLockValidationFatal(bad_entry, this,
182                                       __GET_CALLER(0),
183                                       __GET_FRAME(0),
184                                       LockResult::AlreadyAcquired);
185         }
186 
187         if (!reporting_disabled()) {
188             reporting_disabled_count_++;
189 
190             SystemLockValidationError(bad_entry, conflicting_entry, this,
191                                       __GET_CALLER(0), __GET_FRAME(0), result);
192 
193             reporting_disabled_count_--;
194 
195             // Update the last result for testing.
196             if (last_result_ == LockResult::Success)
197                 last_result_ = result;
198         }
199     }
200 
201     // Triggers a loop detection by the system-defined runtime handler.
TriggerLoopDetection()202     void TriggerLoopDetection() {
203         if (!reporting_disabled()) {
204             reporting_disabled_count_++;
205 
206             SystemTriggerLoopDetection();
207 
208             reporting_disabled_count_--;
209         }
210     }
211 
212     // Tracks the lock classes acquired by the current thread.
213     fbl::DoublyLinkedList<AcquiredLockEntry*> acquired_locks_{};
214 
215     // Tracks the number of locks held that have the LockFlagsReportingDisabled
216     // flag set. Reporting and loop detection are not triggered when this count
217     // is greater than zero. This value is also incremented by one for the
218     // duration of a report or loop detection trigger to prevent recursive calls
219     // due to locks acquired by the system-defined runtime API.
220     uint16_t reporting_disabled_count_{0};
221 
222     // Tracks the result of the last Acquire operation for testing.
223     LockResult last_result_{LockResult::Success};
224 };
225 
226 // Defined after ThreadLockState because of dependency on its methods.
Replace(AcquiredLockEntry * target)227 inline void AcquiredLockEntry::Replace(AcquiredLockEntry* target) {
228     ThreadLockState::Get()->Replace(target, this);
229 }
230 
231 } // namespace lockdep
232