1 /*
2  * Copyright (C) 2020 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "src/trace_processor/dynamic/thread_state_generator.h"
18 
19 #include <algorithm>
20 
21 #include "src/trace_processor/importers/common/args_tracker.h"
22 #include "src/trace_processor/importers/common/global_args_tracker.h"
23 #include "src/trace_processor/types/trace_processor_context.h"
24 #include "test/gtest_and_gmock.h"
25 
26 namespace perfetto {
27 namespace trace_processor {
28 namespace {
29 
30 class ThreadStateGeneratorUnittest : public testing::Test {
31  public:
32   struct Ts {
33     int64_t ts;
34   };
35 
ThreadStateGeneratorUnittest()36   ThreadStateGeneratorUnittest() : idle_thread_(0), thread_a_(1), thread_b_(2) {
37     context_.storage.reset(new TraceStorage());
38     context_.global_args_tracker.reset(new GlobalArgsTracker(&context_));
39     context_.args_tracker.reset(new ArgsTracker(&context_));
40     thread_state_generator_.reset(new ThreadStateGenerator(&context_));
41   }
42 
ForwardSchedTo(Ts ts)43   void ForwardSchedTo(Ts ts) { sched_insert_ts_ = ts.ts; }
44 
AddWaking(Ts ts,UniqueTid utid)45   void AddWaking(Ts ts, UniqueTid utid) {
46     tables::InstantTable::Row row;
47     row.ts = ts.ts;
48     row.ref = utid;
49     row.name = context_.storage->InternString("sched_waking");
50     context_.storage->mutable_instant_table()->Insert(row);
51   }
52 
AddWakup(Ts ts,UniqueTid utid)53   void AddWakup(Ts ts, UniqueTid utid) {
54     tables::InstantTable::Row row;
55     row.ts = ts.ts;
56     row.ref = utid;
57     row.name = context_.storage->InternString("sched_wakeup");
58     context_.storage->mutable_instant_table()->Insert(row);
59   }
60 
AddSched(base::Optional<Ts> end,UniqueTid utid,const char * end_state)61   void AddSched(base::Optional<Ts> end, UniqueTid utid, const char* end_state) {
62     StringId end_state_id = context_.storage->InternString(end_state);
63 
64     tables::SchedSliceTable::Row row;
65 
66     // cpu is hardcoded because it doesn't matter for the algorithm and is
67     // just passed through unchanged.
68     row.cpu = 0;
69 
70     row.ts = sched_insert_ts_;
71     row.dur = end ? end->ts - row.ts : -1;
72     row.utid = utid;
73     row.end_state = end_state_id;
74     context_.storage->mutable_sched_slice_table()->Insert(row);
75 
76     sched_insert_ts_ = end ? end->ts : -1;
77   }
78 
AddBlockedReason(Ts ts,UniqueTid utid,bool io_wait)79   void AddBlockedReason(Ts ts, UniqueTid utid, bool io_wait) {
80     tables::InstantTable::Row row;
81     row.ts = ts.ts;
82     row.ref = utid;
83     row.name = context_.storage->InternString("sched_blocked_reason");
84 
85     auto id = context_.storage->mutable_instant_table()->Insert(row).id;
86     auto inserter = context_.args_tracker->AddArgsTo(id);
87     inserter.AddArg(context_.storage->InternString("io_wait"),
88                     Variadic::Boolean(io_wait));
89     context_.args_tracker->Flush();
90   }
91 
RunThreadStateComputation(Ts trace_end_ts=Ts{ std::numeric_limits<int64_t>::max()})92   void RunThreadStateComputation(Ts trace_end_ts = Ts{
93                                      std::numeric_limits<int64_t>::max()}) {
94     unsorted_table_ =
95         thread_state_generator_->ComputeThreadStateTable(trace_end_ts.ts);
96     table_.reset(
97         new Table(unsorted_table_->Sort({unsorted_table_->ts().ascending()})));
98   }
99 
VerifyThreadState(Ts from,base::Optional<Ts> to,UniqueTid utid,const char * state,base::Optional<bool> io_wait=base::nullopt)100   void VerifyThreadState(Ts from,
101                          base::Optional<Ts> to,
102                          UniqueTid utid,
103                          const char* state,
104                          base::Optional<bool> io_wait = base::nullopt) {
105     uint32_t row = thread_state_verify_row_++;
106 
107     const auto& ts_col = table_->GetTypedColumnByName<int64_t>("ts");
108     const auto& dur_col = table_->GetTypedColumnByName<int64_t>("dur");
109     const auto& utid_col = table_->GetTypedColumnByName<UniqueTid>("utid");
110     const auto& cpu_col =
111         table_->GetTypedColumnByName<base::Optional<uint32_t>>("cpu");
112     const auto& end_state_col = table_->GetTypedColumnByName<StringId>("state");
113     const auto& io_wait_col =
114         table_->GetTypedColumnByName<base::Optional<uint32_t>>("io_wait");
115 
116     ASSERT_LT(row, table_->row_count());
117     ASSERT_EQ(ts_col[row], from.ts);
118     ASSERT_EQ(dur_col[row], to ? to->ts - from.ts : -1);
119     ASSERT_EQ(utid_col[row], utid);
120     if (state == kRunning) {
121       ASSERT_EQ(cpu_col[row], 0u);
122     } else {
123       ASSERT_EQ(cpu_col[row], base::nullopt);
124     }
125     ASSERT_EQ(end_state_col.GetString(row), base::StringView(state));
126 
127     base::Optional<uint32_t> mapped_io_wait =
128         io_wait ? base::make_optional(static_cast<uint32_t>(*io_wait))
129                 : base::nullopt;
130     ASSERT_EQ(io_wait_col[row], mapped_io_wait);
131   }
132 
VerifyEndOfThreadState()133   void VerifyEndOfThreadState() {
134     ASSERT_EQ(thread_state_verify_row_, table_->row_count());
135   }
136 
137  protected:
138   static constexpr char kRunning[] = "Running";
139 
140   const UniqueTid idle_thread_;
141   const UniqueTid thread_a_;
142   const UniqueTid thread_b_;
143 
144  private:
145   TraceProcessorContext context_;
146 
147   int64_t sched_insert_ts_ = 0;
148 
149   uint32_t thread_state_verify_row_ = 0;
150 
151   std::unique_ptr<ThreadStateGenerator> thread_state_generator_;
152   std::unique_ptr<tables::ThreadStateTable> unsorted_table_;
153   std::unique_ptr<Table> table_;
154 };
155 
156 constexpr char ThreadStateGeneratorUnittest::kRunning[];
157 
TEST_F(ThreadStateGeneratorUnittest,MultipleThreadWithOnlySched)158 TEST_F(ThreadStateGeneratorUnittest, MultipleThreadWithOnlySched) {
159   ForwardSchedTo(Ts{0});
160   AddSched(Ts{10}, thread_a_, "S");
161   AddSched(Ts{15}, thread_b_, "D");
162   AddSched(Ts{20}, thread_a_, "R");
163 
164   RunThreadStateComputation();
165 
166   VerifyThreadState(Ts{0}, Ts{10}, thread_a_, kRunning);
167   VerifyThreadState(Ts{10}, Ts{15}, thread_b_, kRunning);
168   VerifyThreadState(Ts{10}, Ts{15}, thread_a_, "S");
169   VerifyThreadState(Ts{15}, Ts{20}, thread_a_, kRunning);
170   VerifyThreadState(Ts{15}, base::nullopt, thread_b_, "D");
171   VerifyThreadState(Ts{20}, base::nullopt, thread_a_, "R");
172 
173   VerifyEndOfThreadState();
174 }
175 
TEST_F(ThreadStateGeneratorUnittest,WakingFirst)176 TEST_F(ThreadStateGeneratorUnittest, WakingFirst) {
177   AddWaking(Ts{10}, thread_a_);
178 
179   ForwardSchedTo(Ts{20});
180   AddSched(Ts{30}, thread_a_, "S");
181 
182   RunThreadStateComputation();
183 
184   VerifyThreadState(Ts{10}, Ts{20}, thread_a_, "R");
185   VerifyThreadState(Ts{20}, Ts{30}, thread_a_, kRunning);
186   VerifyThreadState(Ts{30}, base::nullopt, thread_a_, "S");
187 
188   VerifyEndOfThreadState();
189 }
190 
TEST_F(ThreadStateGeneratorUnittest,SchedWithWaking)191 TEST_F(ThreadStateGeneratorUnittest, SchedWithWaking) {
192   ForwardSchedTo(Ts{0});
193   AddSched(Ts{10}, thread_a_, "S");
194 
195   AddWaking(Ts{15}, thread_a_);
196 
197   ForwardSchedTo(Ts{20});
198   AddSched(Ts{25}, thread_a_, "R");
199 
200   RunThreadStateComputation();
201 
202   VerifyThreadState(Ts{0}, Ts{10}, thread_a_, kRunning);
203   VerifyThreadState(Ts{10}, Ts{15}, thread_a_, "S");
204   VerifyThreadState(Ts{15}, Ts{20}, thread_a_, "R");
205   VerifyThreadState(Ts{20}, Ts{25}, thread_a_, kRunning);
206   VerifyThreadState(Ts{25}, base::nullopt, thread_a_, "R");
207 
208   VerifyEndOfThreadState();
209 }
210 
TEST_F(ThreadStateGeneratorUnittest,SchedWithWakeup)211 TEST_F(ThreadStateGeneratorUnittest, SchedWithWakeup) {
212   ForwardSchedTo(Ts{0});
213   AddSched(Ts{10}, thread_a_, "S");
214 
215   AddWakup(Ts{15}, thread_a_);
216 
217   ForwardSchedTo(Ts{20});
218   AddSched(Ts{25}, thread_a_, "R");
219 
220   RunThreadStateComputation();
221 
222   VerifyThreadState(Ts{0}, Ts{10}, thread_a_, kRunning);
223   VerifyThreadState(Ts{10}, Ts{15}, thread_a_, "S");
224   VerifyThreadState(Ts{15}, Ts{20}, thread_a_, "R");
225   VerifyThreadState(Ts{20}, Ts{25}, thread_a_, kRunning);
226   VerifyThreadState(Ts{25}, base::nullopt, thread_a_, "R");
227 
228   VerifyEndOfThreadState();
229 }
230 
TEST_F(ThreadStateGeneratorUnittest,SchedIdleIgnored)231 TEST_F(ThreadStateGeneratorUnittest, SchedIdleIgnored) {
232   ForwardSchedTo(Ts{0});
233   AddSched(Ts{10}, idle_thread_, "R");
234   AddSched(Ts{15}, thread_a_, "R");
235 
236   RunThreadStateComputation();
237 
238   VerifyThreadState(Ts{10}, Ts{15}, thread_a_, kRunning);
239   VerifyThreadState(Ts{15}, base::nullopt, thread_a_, "R");
240 
241   VerifyEndOfThreadState();
242 }
243 
TEST_F(ThreadStateGeneratorUnittest,NegativeSchedDuration)244 TEST_F(ThreadStateGeneratorUnittest, NegativeSchedDuration) {
245   ForwardSchedTo(Ts{0});
246 
247   AddSched(Ts{10}, thread_a_, "S");
248 
249   AddWaking(Ts{15}, thread_a_);
250 
251   ForwardSchedTo(Ts{20});
252   AddSched(base::nullopt, thread_a_, "");
253 
254   RunThreadStateComputation();
255 
256   VerifyThreadState(Ts{0}, Ts{10}, thread_a_, kRunning);
257   VerifyThreadState(Ts{10}, Ts{15}, thread_a_, "S");
258   VerifyThreadState(Ts{15}, Ts{20}, thread_a_, "R");
259   VerifyThreadState(Ts{20}, base::nullopt, thread_a_, kRunning);
260 
261   VerifyEndOfThreadState();
262 }
263 
TEST_F(ThreadStateGeneratorUnittest,WakingOnRunningThreadAtEnd)264 TEST_F(ThreadStateGeneratorUnittest, WakingOnRunningThreadAtEnd) {
265   AddWaking(Ts{5}, thread_a_);
266 
267   ForwardSchedTo(Ts{10});
268   AddSched(base::nullopt, thread_a_, "");
269 
270   AddWaking(Ts{15}, thread_a_);
271 
272   RunThreadStateComputation();
273 
274   VerifyThreadState(Ts{5}, Ts{10}, thread_a_, "R");
275   VerifyThreadState(Ts{10}, base::nullopt, thread_a_, kRunning);
276   VerifyThreadState(Ts{15}, base::nullopt, thread_a_, "R");
277 
278   VerifyEndOfThreadState();
279 }
280 
TEST_F(ThreadStateGeneratorUnittest,SchedDataLoss)281 TEST_F(ThreadStateGeneratorUnittest, SchedDataLoss) {
282   ForwardSchedTo(Ts{10});
283   AddSched(base::nullopt, thread_a_, "");
284   ForwardSchedTo(Ts{30});
285   AddSched(Ts{40}, thread_a_, "D");
286 
287   RunThreadStateComputation();
288 
289   VerifyThreadState(Ts{10}, base::nullopt, thread_a_, kRunning);
290   VerifyThreadState(Ts{30}, Ts{40}, thread_a_, kRunning);
291   VerifyThreadState(Ts{40}, base::nullopt, thread_a_, "D");
292 
293   VerifyEndOfThreadState();
294 }
295 
TEST_F(ThreadStateGeneratorUnittest,StrechedSchedIgnored)296 TEST_F(ThreadStateGeneratorUnittest, StrechedSchedIgnored) {
297   ForwardSchedTo(Ts{10});
298   AddSched(Ts{100}, thread_a_, "");
299 
300   RunThreadStateComputation(Ts{100});
301 
302   VerifyThreadState(Ts{10}, base::nullopt, thread_a_, kRunning);
303 
304   VerifyEndOfThreadState();
305 }
306 
TEST_F(ThreadStateGeneratorUnittest,WakingAfterStrechedSched)307 TEST_F(ThreadStateGeneratorUnittest, WakingAfterStrechedSched) {
308   ForwardSchedTo(Ts{10});
309   AddSched(Ts{100}, thread_a_, "");
310 
311   AddWaking(Ts{15}, thread_a_);
312 
313   RunThreadStateComputation(Ts{100});
314 
315   VerifyThreadState(Ts{10}, base::nullopt, thread_a_, kRunning);
316   VerifyThreadState(Ts{15}, base::nullopt, thread_a_, "R");
317 
318   VerifyEndOfThreadState();
319 }
320 
TEST_F(ThreadStateGeneratorUnittest,BlockedReason)321 TEST_F(ThreadStateGeneratorUnittest, BlockedReason) {
322   ForwardSchedTo(Ts{10});
323   AddSched(Ts{12}, thread_a_, "D");
324   AddWaking(Ts{15}, thread_a_);
325   AddBlockedReason(Ts{16}, thread_a_, true);
326 
327   ForwardSchedTo(Ts{18});
328   AddSched(Ts{20}, thread_a_, "S");
329   AddWaking(Ts{24}, thread_a_);
330   AddBlockedReason(Ts{26}, thread_a_, false);
331 
332   ForwardSchedTo(Ts{29});
333   AddSched(Ts{30}, thread_a_, "R");
334 
335   ForwardSchedTo(Ts{39});
336   AddSched(Ts{40}, thread_a_, "D");
337   AddBlockedReason(Ts{44}, thread_a_, false);
338 
339   ForwardSchedTo(Ts{49});
340   AddSched(Ts{50}, thread_a_, "D");
341 
342   RunThreadStateComputation();
343 
344   VerifyThreadState(Ts{10}, Ts{12}, thread_a_, kRunning);
345   VerifyThreadState(Ts{12}, Ts{15}, thread_a_, "D", true);
346   VerifyThreadState(Ts{15}, Ts{18}, thread_a_, "R");
347 
348   VerifyThreadState(Ts{18}, Ts{20}, thread_a_, kRunning);
349   VerifyThreadState(Ts{20}, Ts{24}, thread_a_, "S", false);
350   VerifyThreadState(Ts{24}, Ts{29}, thread_a_, "R");
351 
352   VerifyThreadState(Ts{29}, Ts{30}, thread_a_, kRunning);
353   VerifyThreadState(Ts{30}, Ts{39}, thread_a_, "R", base::nullopt);
354 
355   VerifyThreadState(Ts{39}, Ts{40}, thread_a_, kRunning);
356   VerifyThreadState(Ts{40}, Ts{49}, thread_a_, "D", false);
357 
358   VerifyThreadState(Ts{49}, Ts{50}, thread_a_, kRunning);
359   VerifyThreadState(Ts{50}, base::nullopt, thread_a_, "D");
360 
361   VerifyEndOfThreadState();
362 }
363 
364 }  // namespace
365 }  // namespace trace_processor
366 }  // namespace perfetto
367