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> & entering_monitors,PandaMap<Monitor::MonitorId,PandaSet<ManagedThread::ThreadId>> & entered_monitors,MTManagedThread * thread)21 void UpdateMonitorsForThread(PandaMap<ManagedThread::ThreadId, Monitor::MonitorId> &entering_monitors,
22 PandaMap<Monitor::MonitorId, PandaSet<ManagedThread::ThreadId>> &entered_monitors,
23 MTManagedThread *thread)
24 {
25 auto thread_id = thread->GetId();
26 auto entering_monitor = thread->GetEnteringMonitor();
27 if (entering_monitor != nullptr) {
28 entering_monitors[thread_id] = entering_monitor->GetId();
29 }
30 for (auto entered_monitor_id : thread->GetVM()->GetMonitorPool()->GetEnteredMonitorsIds(thread)) {
31 entered_monitors[entered_monitor_id].insert(thread_id);
32 }
33 }
34
CheckForTerminationLoops(const PandaList<MTManagedThread * > & threads,const PandaList<MTManagedThread * > & daemon_threads,MTManagedThread * current)35 bool LockOrderGraph::CheckForTerminationLoops(const PandaList<MTManagedThread *> &threads,
36 const PandaList<MTManagedThread *> &daemon_threads,
37 MTManagedThread *current)
38 {
39 PandaMap<ThreadId, bool> nodes;
40 PandaMap<ThreadId, ThreadId> edges;
41 PandaMap<ThreadId, MonitorId> entering_monitors;
42 PandaMap<MonitorId, PandaSet<ThreadId>> entered_monitors;
43 for (auto thread : threads) {
44 if (thread == current) {
45 continue;
46 }
47
48 auto thread_id = thread->GetId();
49 auto status = thread->GetStatus();
50 if (status == ThreadStatus::NATIVE) {
51 nodes[thread_id] = true;
52 } else {
53 if (status != ThreadStatus::IS_BLOCKED) {
54 LOG(DEBUG, RUNTIME) << "Thread " << thread_id << " has changed its status during graph construction";
55 return false;
56 }
57 nodes[thread_id] = false;
58 }
59 LOG(DEBUG, RUNTIME) << "LockOrderGraph node: " << thread_id << ", is NATIVE = " << nodes[thread_id];
60 UpdateMonitorsForThread(entering_monitors, entered_monitors, thread);
61 }
62 for (auto thread : daemon_threads) {
63 auto thread_id = thread->GetId();
64 nodes[thread_id] = true;
65 LOG(DEBUG, RUNTIME) << "LockOrderGraph node: " << thread_id << ", in termination loop";
66 UpdateMonitorsForThread(entering_monitors, entered_monitors, thread);
67 }
68
69 for (const auto &[from_thread_id, entering_monitor_id] : entering_monitors) {
70 for (const auto to_thread_id : entered_monitors[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 << " -> " << to_thread_id;
76 return false;
77 }
78 edges[from_thread_id] = to_thread_id;
79 LOG(DEBUG, RUNTIME) << "LockOrderGraph edge: " << from_thread_id << " -> " << to_thread_id;
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> nodes_in_deadlocks = {};
92 for (auto const node_elem : nodes_) {
93 auto node = node_elem.first;
94 if (nodes_in_deadlocks.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 nodes_in_deadlocks.insert(node);
101 continue;
102 }
103
104 // explored_nodes contains nodes reachable from the node chosen in the outer loop.
105 PandaSet<ThreadId> explored_nodes = {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 current_node = *i;
115 i = front.erase(i);
116 if (edges_.count(current_node) == 0) {
117 // No transitions from this node.
118 continue;
119 }
120 auto next_node = edges_.at(current_node);
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 (next_node == current_node) {
127 continue;
128 }
129 if (explored_nodes.count(next_node) != 0 || nodes_in_deadlocks.count(next_node) != 0 ||
130 nodes_.at(next_node)) {
131 // Loop or path to another loop or to terminating node was found
132 nodes_in_deadlocks.merge(explored_nodes);
133 front.clear();
134 break;
135 }
136 explored_nodes.insert(next_node);
137 front.push_back(next_node);
138 }
139 }
140 }
141 return nodes_in_deadlocks.size() == nodes_.size();
142 }
143 } // namespace panda
144