1 //===- Profile.cpp - XRay Profile Abstraction -----------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Defines the XRay Profile class representing the latency profile generated by
10 // XRay's profiling mode.
11 //
12 //===----------------------------------------------------------------------===//
13 #include "llvm/XRay/Profile.h"
14 
15 #include "llvm/Support/DataExtractor.h"
16 #include "llvm/Support/Error.h"
17 #include "llvm/Support/FileSystem.h"
18 #include "llvm/XRay/Trace.h"
19 #include <deque>
20 #include <memory>
21 
22 namespace llvm {
23 namespace xray {
24 
25 Profile::Profile(const Profile &O) {
26   // We need to re-create all the tries from the original (O), into the current
27   // Profile being initialized, through the Block instances we see.
28   for (const auto &Block : O) {
29     Blocks.push_back({Block.Thread, {}});
30     auto &B = Blocks.back();
31     for (const auto &PathData : Block.PathData)
32       B.PathData.push_back({internPath(cantFail(O.expandPath(PathData.first))),
33                             PathData.second});
34   }
35 }
36 
37 Profile &Profile::operator=(const Profile &O) {
38   Profile P = O;
39   *this = std::move(P);
40   return *this;
41 }
42 
43 namespace {
44 
45 struct BlockHeader {
46   uint32_t Size;
47   uint32_t Number;
48   uint64_t Thread;
49 };
50 
51 static Expected<BlockHeader> readBlockHeader(DataExtractor &Extractor,
52                                              uint64_t &Offset) {
53   BlockHeader H;
54   uint64_t CurrentOffset = Offset;
55   H.Size = Extractor.getU32(&Offset);
56   if (Offset == CurrentOffset)
57     return make_error<StringError>(
58         Twine("Error parsing block header size at offset '") +
59             Twine(CurrentOffset) + "'",
60         std::make_error_code(std::errc::invalid_argument));
61   CurrentOffset = Offset;
62   H.Number = Extractor.getU32(&Offset);
63   if (Offset == CurrentOffset)
64     return make_error<StringError>(
65         Twine("Error parsing block header number at offset '") +
66             Twine(CurrentOffset) + "'",
67         std::make_error_code(std::errc::invalid_argument));
68   CurrentOffset = Offset;
69   H.Thread = Extractor.getU64(&Offset);
70   if (Offset == CurrentOffset)
71     return make_error<StringError>(
72         Twine("Error parsing block header thread id at offset '") +
73             Twine(CurrentOffset) + "'",
74         std::make_error_code(std::errc::invalid_argument));
75   return H;
76 }
77 
78 static Expected<std::vector<Profile::FuncID>> readPath(DataExtractor &Extractor,
79                                                        uint64_t &Offset) {
80   // We're reading a sequence of int32_t's until we find a 0.
81   std::vector<Profile::FuncID> Path;
82   auto CurrentOffset = Offset;
83   int32_t FuncId;
84   do {
85     FuncId = Extractor.getSigned(&Offset, 4);
86     if (CurrentOffset == Offset)
87       return make_error<StringError>(
88           Twine("Error parsing path at offset '") + Twine(CurrentOffset) + "'",
89           std::make_error_code(std::errc::invalid_argument));
90     CurrentOffset = Offset;
91     Path.push_back(FuncId);
92   } while (FuncId != 0);
93   return std::move(Path);
94 }
95 
96 static Expected<Profile::Data> readData(DataExtractor &Extractor,
97                                         uint64_t &Offset) {
98   // We expect a certain number of elements for Data:
99   //   - A 64-bit CallCount
100   //   - A 64-bit CumulativeLocalTime counter
101   Profile::Data D;
102   auto CurrentOffset = Offset;
103   D.CallCount = Extractor.getU64(&Offset);
104   if (CurrentOffset == Offset)
105     return make_error<StringError>(
106         Twine("Error parsing call counts at offset '") + Twine(CurrentOffset) +
107             "'",
108         std::make_error_code(std::errc::invalid_argument));
109   CurrentOffset = Offset;
110   D.CumulativeLocalTime = Extractor.getU64(&Offset);
111   if (CurrentOffset == Offset)
112     return make_error<StringError>(
113         Twine("Error parsing cumulative local time at offset '") +
114             Twine(CurrentOffset) + "'",
115         std::make_error_code(std::errc::invalid_argument));
116   return D;
117 }
118 
119 } // namespace
120 
121 Error Profile::addBlock(Block &&B) {
122   if (B.PathData.empty())
123     return make_error<StringError>(
124         "Block may not have empty path data.",
125         std::make_error_code(std::errc::invalid_argument));
126 
127   Blocks.emplace_back(std::move(B));
128   return Error::success();
129 }
130 
131 Expected<std::vector<Profile::FuncID>> Profile::expandPath(PathID P) const {
132   auto It = PathIDMap.find(P);
133   if (It == PathIDMap.end())
134     return make_error<StringError>(
135         Twine("PathID not found: ") + Twine(P),
136         std::make_error_code(std::errc::invalid_argument));
137   std::vector<Profile::FuncID> Path;
138   for (auto Node = It->second; Node; Node = Node->Caller)
139     Path.push_back(Node->Func);
140   return std::move(Path);
141 }
142 
143 Profile::PathID Profile::internPath(ArrayRef<FuncID> P) {
144   if (P.empty())
145     return 0;
146 
147   auto RootToLeafPath = reverse(P);
148 
149   // Find the root.
150   auto It = RootToLeafPath.begin();
151   auto PathRoot = *It++;
152   auto RootIt =
153       find_if(Roots, [PathRoot](TrieNode *N) { return N->Func == PathRoot; });
154 
155   // If we've not seen this root before, remember it.
156   TrieNode *Node = nullptr;
157   if (RootIt == Roots.end()) {
158     NodeStorage.emplace_back();
159     Node = &NodeStorage.back();
160     Node->Func = PathRoot;
161     Roots.push_back(Node);
162   } else {
163     Node = *RootIt;
164   }
165 
166   // Now traverse the path, re-creating if necessary.
167   while (It != RootToLeafPath.end()) {
168     auto NodeFuncID = *It++;
169     auto CalleeIt = find_if(Node->Callees, [NodeFuncID](TrieNode *N) {
170       return N->Func == NodeFuncID;
171     });
172     if (CalleeIt == Node->Callees.end()) {
173       NodeStorage.emplace_back();
174       auto NewNode = &NodeStorage.back();
175       NewNode->Func = NodeFuncID;
176       NewNode->Caller = Node;
177       Node->Callees.push_back(NewNode);
178       Node = NewNode;
179     } else {
180       Node = *CalleeIt;
181     }
182   }
183 
184   // At this point, Node *must* be pointing at the leaf.
185   assert(Node->Func == P.front());
186   if (Node->ID == 0) {
187     Node->ID = NextID++;
188     PathIDMap.insert({Node->ID, Node});
189   }
190   return Node->ID;
191 }
192 
193 Profile mergeProfilesByThread(const Profile &L, const Profile &R) {
194   Profile Merged;
195   using PathDataMap = DenseMap<Profile::PathID, Profile::Data>;
196   using PathDataMapPtr = std::unique_ptr<PathDataMap>;
197   using PathDataVector = decltype(Profile::Block::PathData);
198   using ThreadProfileIndexMap = DenseMap<Profile::ThreadID, PathDataMapPtr>;
199   ThreadProfileIndexMap ThreadProfileIndex;
200 
201   for (const auto &P : {std::ref(L), std::ref(R)})
202     for (const auto &Block : P.get()) {
203       ThreadProfileIndexMap::iterator It;
204       std::tie(It, std::ignore) = ThreadProfileIndex.insert(
205           {Block.Thread, PathDataMapPtr{new PathDataMap()}});
206       for (const auto &PathAndData : Block.PathData) {
207         auto &PathID = PathAndData.first;
208         auto &Data = PathAndData.second;
209         auto NewPathID =
210             Merged.internPath(cantFail(P.get().expandPath(PathID)));
211         PathDataMap::iterator PathDataIt;
212         bool Inserted;
213         std::tie(PathDataIt, Inserted) = It->second->insert({NewPathID, Data});
214         if (!Inserted) {
215           auto &ExistingData = PathDataIt->second;
216           ExistingData.CallCount += Data.CallCount;
217           ExistingData.CumulativeLocalTime += Data.CumulativeLocalTime;
218         }
219       }
220     }
221 
222   for (const auto &IndexedThreadBlock : ThreadProfileIndex) {
223     PathDataVector PathAndData;
224     PathAndData.reserve(IndexedThreadBlock.second->size());
225     copy(*IndexedThreadBlock.second, std::back_inserter(PathAndData));
226     cantFail(
227         Merged.addBlock({IndexedThreadBlock.first, std::move(PathAndData)}));
228   }
229   return Merged;
230 }
231 
232 Profile mergeProfilesByStack(const Profile &L, const Profile &R) {
233   Profile Merged;
234   using PathDataMap = DenseMap<Profile::PathID, Profile::Data>;
235   PathDataMap PathData;
236   using PathDataVector = decltype(Profile::Block::PathData);
237   for (const auto &P : {std::ref(L), std::ref(R)})
238     for (const auto &Block : P.get())
239       for (const auto &PathAndData : Block.PathData) {
240         auto &PathId = PathAndData.first;
241         auto &Data = PathAndData.second;
242         auto NewPathID =
243             Merged.internPath(cantFail(P.get().expandPath(PathId)));
244         PathDataMap::iterator PathDataIt;
245         bool Inserted;
246         std::tie(PathDataIt, Inserted) = PathData.insert({NewPathID, Data});
247         if (!Inserted) {
248           auto &ExistingData = PathDataIt->second;
249           ExistingData.CallCount += Data.CallCount;
250           ExistingData.CumulativeLocalTime += Data.CumulativeLocalTime;
251         }
252       }
253 
254   // In the end there's a single Block, for thread 0.
255   PathDataVector Block;
256   Block.reserve(PathData.size());
257   copy(PathData, std::back_inserter(Block));
258   cantFail(Merged.addBlock({0, std::move(Block)}));
259   return Merged;
260 }
261 
262 Expected<Profile> loadProfile(StringRef Filename) {
263   Expected<sys::fs::file_t> FdOrErr = sys::fs::openNativeFileForRead(Filename);
264   if (!FdOrErr)
265     return FdOrErr.takeError();
266 
267   uint64_t FileSize;
268   if (auto EC = sys::fs::file_size(Filename, FileSize))
269     return make_error<StringError>(
270         Twine("Cannot get filesize of '") + Filename + "'", EC);
271 
272   std::error_code EC;
273   sys::fs::mapped_file_region MappedFile(
274       *FdOrErr, sys::fs::mapped_file_region::mapmode::readonly, FileSize, 0,
275       EC);
276   sys::fs::closeFile(*FdOrErr);
277   if (EC)
278     return make_error<StringError>(
279         Twine("Cannot mmap profile '") + Filename + "'", EC);
280   StringRef Data(MappedFile.data(), MappedFile.size());
281 
282   Profile P;
283   uint64_t Offset = 0;
284   DataExtractor Extractor(Data, true, 8);
285 
286   // For each block we get from the file:
287   while (Offset != MappedFile.size()) {
288     auto HeaderOrError = readBlockHeader(Extractor, Offset);
289     if (!HeaderOrError)
290       return HeaderOrError.takeError();
291 
292     // TODO: Maybe store this header information for each block, even just for
293     // debugging?
294     const auto &Header = HeaderOrError.get();
295 
296     // Read in the path data.
297     auto PathOrError = readPath(Extractor, Offset);
298     if (!PathOrError)
299       return PathOrError.takeError();
300     const auto &Path = PathOrError.get();
301 
302     // For each path we encounter, we should intern it to get a PathID.
303     auto DataOrError = readData(Extractor, Offset);
304     if (!DataOrError)
305       return DataOrError.takeError();
306     auto &Data = DataOrError.get();
307 
308     if (auto E =
309             P.addBlock(Profile::Block{Profile::ThreadID{Header.Thread},
310                                       {{P.internPath(Path), std::move(Data)}}}))
311       return std::move(E);
312   }
313 
314   return P;
315 }
316 
317 namespace {
318 
319 struct StackEntry {
320   uint64_t Timestamp;
321   Profile::FuncID FuncId;
322 };
323 
324 } // namespace
325 
326 Expected<Profile> profileFromTrace(const Trace &T) {
327   Profile P;
328 
329   // The implementation of the algorithm re-creates the execution of
330   // the functions based on the trace data. To do this, we set up a number of
331   // data structures to track the execution context of every thread in the
332   // Trace.
333   DenseMap<Profile::ThreadID, std::vector<StackEntry>> ThreadStacks;
334   DenseMap<Profile::ThreadID, DenseMap<Profile::PathID, Profile::Data>>
335       ThreadPathData;
336 
337   //  We then do a pass through the Trace to account data on a per-thread-basis.
338   for (const auto &E : T) {
339     auto &TSD = ThreadStacks[E.TId];
340     switch (E.Type) {
341     case RecordTypes::ENTER:
342     case RecordTypes::ENTER_ARG:
343 
344       // Push entries into the function call stack.
345       TSD.push_back({E.TSC, E.FuncId});
346       break;
347 
348     case RecordTypes::EXIT:
349     case RecordTypes::TAIL_EXIT:
350 
351       // Exits cause some accounting to happen, based on the state of the stack.
352       // For each function we pop off the stack, we take note of the path and
353       // record the cumulative state for this path. As we're doing this, we
354       // intern the path into the Profile.
355       while (!TSD.empty()) {
356         auto Top = TSD.back();
357         auto FunctionLocalTime = AbsoluteDifference(Top.Timestamp, E.TSC);
358         SmallVector<Profile::FuncID, 16> Path;
359         transform(reverse(TSD), std::back_inserter(Path),
360                   std::mem_fn(&StackEntry::FuncId));
361         auto InternedPath = P.internPath(Path);
362         auto &TPD = ThreadPathData[E.TId][InternedPath];
363         ++TPD.CallCount;
364         TPD.CumulativeLocalTime += FunctionLocalTime;
365         TSD.pop_back();
366 
367         // If we've matched the corresponding entry event for this function,
368         // then we exit the loop.
369         if (Top.FuncId == E.FuncId)
370           break;
371 
372         // FIXME: Consider the intermediate times and the cumulative tree time
373         // as well.
374       }
375 
376       break;
377 
378     case RecordTypes::CUSTOM_EVENT:
379     case RecordTypes::TYPED_EVENT:
380       // TODO: Support an extension point to allow handling of custom and typed
381       // events in profiles.
382       break;
383     }
384   }
385 
386   // Once we've gone through the Trace, we now create one Block per thread in
387   // the Profile.
388   for (const auto &ThreadPaths : ThreadPathData) {
389     const auto &TID = ThreadPaths.first;
390     const auto &PathsData = ThreadPaths.second;
391     if (auto E = P.addBlock({
392             TID,
393             std::vector<std::pair<Profile::PathID, Profile::Data>>(
394                 PathsData.begin(), PathsData.end()),
395         }))
396       return std::move(E);
397   }
398 
399   return P;
400 }
401 
402 } // namespace xray
403 } // namespace llvm
404