1 /**
2 * Copyright (c) 2022-2022 Huawei Device Co., Ltd.
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
16 #include "runtime/include/panda_vm.h"
17
18 #include "runtime/lock_order_graph.h"
19
20 namespace panda {
UpdateMonitorsForThread(PandaMap<ManagedThread::ThreadId,Monitor::MonitorId> & enteringMonitors,PandaMap<Monitor::MonitorId,PandaSet<ManagedThread::ThreadId>> & enteredMonitors,MTManagedThread * thread)21 void UpdateMonitorsForThread(PandaMap<ManagedThread::ThreadId, Monitor::MonitorId> &enteringMonitors,
22 PandaMap<Monitor::MonitorId, PandaSet<ManagedThread::ThreadId>> &enteredMonitors,
23 MTManagedThread *thread)
24 {
25 auto threadId = thread->GetId();
26 auto enteringMonitor = thread->GetEnteringMonitor();
27 if (enteringMonitor != nullptr) {
28 enteringMonitors[threadId] = enteringMonitor->GetId();
29 }
30 for (auto enteredMonitorId : thread->GetVM()->GetMonitorPool()->GetEnteredMonitorsIds(thread)) {
31 enteredMonitors[enteredMonitorId].insert(threadId);
32 }
33 }
34
CheckForTerminationLoops(const PandaList<MTManagedThread * > & threads,const PandaList<MTManagedThread * > & daemonThreads,MTManagedThread * current)35 bool LockOrderGraph::CheckForTerminationLoops(const PandaList<MTManagedThread *> &threads,
36 const PandaList<MTManagedThread *> &daemonThreads,
37 MTManagedThread *current)
38 {
39 PandaMap<ThreadId, bool> nodes;
40 PandaMap<ThreadId, ThreadId> edges;
41 PandaMap<ThreadId, MonitorId> enteringMonitors;
42 PandaMap<MonitorId, PandaSet<ThreadId>> enteredMonitors;
43 for (auto thread : threads) {
44 if (thread == current) {
45 continue;
46 }
47
48 auto threadId = thread->GetId();
49 auto status = thread->GetStatus();
50 if (status == ThreadStatus::NATIVE) {
51 nodes[threadId] = true;
52 } else {
53 if (status != ThreadStatus::IS_BLOCKED) {
54 LOG(DEBUG, RUNTIME) << "Thread " << threadId << " has changed its status during graph construction";
55 return false;
56 }
57 nodes[threadId] = false;
58 }
59 LOG(DEBUG, RUNTIME) << "LockOrderGraph node: " << threadId << ", is NATIVE = " << nodes[threadId];
60 UpdateMonitorsForThread(enteringMonitors, enteredMonitors, thread);
61 }
62 for (auto thread : daemonThreads) {
63 auto threadId = thread->GetId();
64 nodes[threadId] = true;
65 LOG(DEBUG, RUNTIME) << "LockOrderGraph node: " << threadId << ", in termination loop";
66 UpdateMonitorsForThread(enteringMonitors, enteredMonitors, thread);
67 }
68
69 for (const auto &[from_thread_id, entering_monitor_id] : enteringMonitors) {
70 for (const auto toThreadId : enteredMonitors[entering_monitor_id]) {
71 // We can only wait for a single monitor here.
72 if (edges.count(from_thread_id) != 0) {
73 LOG(DEBUG, RUNTIME) << "Graph has been changed during its construction. Previous edge "
74 << from_thread_id << " -> " << edges[from_thread_id]
75 << " cannot be overwritten with " << from_thread_id << " -> " << toThreadId;
76 return false;
77 }
78 edges[from_thread_id] = toThreadId;
79 LOG(DEBUG, RUNTIME) << "LockOrderGraph edge: " << from_thread_id << " -> " << toThreadId;
80 }
81 }
82 return LockOrderGraph(nodes, edges).CheckForTerminationLoops();
83 }
84
CheckForTerminationLoops() const85 bool LockOrderGraph::CheckForTerminationLoops() const
86 {
87 // This function returns true, if the following conditions are satisfied for each node:
88 // the node belongs to a loop (i.e., there is a deadlock with corresponding threads), or
89 // this is a terminating node (thread with NATIVE status), or
90 // there is a path to a loop or to a terminating node.
91 PandaSet<ThreadId> nodesInDeadlocks = {};
92 for (auto const nodeElem : nodes_) {
93 auto node = nodeElem.first;
94 if (nodesInDeadlocks.count(node) != 0) {
95 // If this node belongs to some previously found loop, we ignore it.
96 continue;
97 }
98 if (nodes_.at(node)) {
99 // This node is terminating, ignore it.
100 nodesInDeadlocks.insert(node);
101 continue;
102 }
103
104 // explored_nodes contains nodes reachable from the node chosen in the outer loop.
105 PandaSet<ThreadId> exploredNodes = {node};
106 // front contains nodes which have not been explored yet.
107 PandaList<ThreadId> front = {node};
108 // On each iteration of the loop we take next unexplored node from the front and find all reachable nodes from
109 // it. If we find already explored node then there is a loop and we save it in nodes_in_deadlocks. Also we
110 // detect paths leading to nodes_in_deadlocks and to termination nodes.
111 while (!front.empty()) {
112 auto i = front.begin();
113 while (i != front.end()) {
114 ThreadId currentNode = *i;
115 i = front.erase(i);
116 if (edges_.count(currentNode) == 0) {
117 // No transitions from this node.
118 continue;
119 }
120 auto nextNode = edges_.at(currentNode);
121 // There is a rare case, in which a monitor may be entered recursively in a
122 // daemon thread. If a runtime calls DeregisterSuspendedThreads exactly when
123 // the daemon thread sets SetEnteringMonitor, then we create an edge from a thread
124 // to itself, i.e. a self-loop and, thus, falsely flag this situation as a deadlock.
125 // So here we ignore this self-loop as a false loop.
126 if (nextNode == currentNode) {
127 continue;
128 }
129 if (exploredNodes.count(nextNode) != 0 || nodesInDeadlocks.count(nextNode) != 0 ||
130 nodes_.at(nextNode)) {
131 // Loop or path to another loop or to terminating node was found
132 nodesInDeadlocks.merge(exploredNodes);
133 front.clear();
134 break;
135 }
136 exploredNodes.insert(nextNode);
137 front.push_back(nextNode);
138 }
139 }
140 }
141 return nodesInDeadlocks.size() == nodes_.size();
142 }
143 } // namespace panda
144