llvm.org GIT mirror llvm / b92b0b8 lib / XRay / Profile.cpp
b92b0b8

Tree @b92b0b8 (Download .tar.gz)

Profile.cpp @b92b0b8raw · history · blame

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
//===- Profile.cpp - XRay Profile Abstraction -----------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Defines the XRay Profile class representing the latency profile generated by
// XRay's profiling mode.
//
//===----------------------------------------------------------------------===//
#include "llvm/XRay/Profile.h"

#include "llvm/Support/DataExtractor.h"
#include "llvm/Support/Error.h"
#include "llvm/Support/FileSystem.h"
#include "llvm/XRay/Trace.h"
#include <deque>
#include <memory>

namespace llvm {
namespace xray {

Profile::Profile(const Profile &O) {
  // We need to re-create all the tries from the original (O), into the current
  // Profile being initialized, through the Block instances we see.
  for (const auto &Block : O) {
    Blocks.push_back({Block.Thread, {}});
    auto &B = Blocks.back();
    for (const auto &PathData : Block.PathData)
      B.PathData.push_back({internPath(cantFail(O.expandPath(PathData.first))),
                            PathData.second});
  }
}

Profile &Profile::operator=(const Profile &O) {
  Profile P = O;
  *this = std::move(P);
  return *this;
}

namespace {

struct BlockHeader {
  uint32_t Size;
  uint32_t Number;
  uint64_t Thread;
};

static Expected<BlockHeader> readBlockHeader(DataExtractor &Extractor,
                                             uint32_t &Offset) {
  BlockHeader H;
  uint32_t CurrentOffset = Offset;
  H.Size = Extractor.getU32(&Offset);
  if (Offset == CurrentOffset)
    return make_error<StringError>(
        Twine("Error parsing block header size at offset '") +
            Twine(CurrentOffset) + "'",
        std::make_error_code(std::errc::invalid_argument));
  CurrentOffset = Offset;
  H.Number = Extractor.getU32(&Offset);
  if (Offset == CurrentOffset)
    return make_error<StringError>(
        Twine("Error parsing block header number at offset '") +
            Twine(CurrentOffset) + "'",
        std::make_error_code(std::errc::invalid_argument));
  CurrentOffset = Offset;
  H.Thread = Extractor.getU64(&Offset);
  if (Offset == CurrentOffset)
    return make_error<StringError>(
        Twine("Error parsing block header thread id at offset '") +
            Twine(CurrentOffset) + "'",
        std::make_error_code(std::errc::invalid_argument));
  return H;
}

static Expected<std::vector<Profile::FuncID>> readPath(DataExtractor &Extractor,
                                                       uint32_t &Offset) {
  // We're reading a sequence of int32_t's until we find a 0.
  std::vector<Profile::FuncID> Path;
  auto CurrentOffset = Offset;
  int32_t FuncId;
  do {
    FuncId = Extractor.getSigned(&Offset, 4);
    if (CurrentOffset == Offset)
      return make_error<StringError>(
          Twine("Error parsing path at offset '") + Twine(CurrentOffset) + "'",
          std::make_error_code(std::errc::invalid_argument));
    CurrentOffset = Offset;
    Path.push_back(FuncId);
  } while (FuncId != 0);
  return std::move(Path);
}

static Expected<Profile::Data> readData(DataExtractor &Extractor,
                                        uint32_t &Offset) {
  // We expect a certain number of elements for Data:
  //   - A 64-bit CallCount
  //   - A 64-bit CumulativeLocalTime counter
  Profile::Data D;
  auto CurrentOffset = Offset;
  D.CallCount = Extractor.getU64(&Offset);
  if (CurrentOffset == Offset)
    return make_error<StringError>(
        Twine("Error parsing call counts at offset '") + Twine(CurrentOffset) +
            "'",
        std::make_error_code(std::errc::invalid_argument));
  CurrentOffset = Offset;
  D.CumulativeLocalTime = Extractor.getU64(&Offset);
  if (CurrentOffset == Offset)
    return make_error<StringError>(
        Twine("Error parsing cumulative local time at offset '") +
            Twine(CurrentOffset) + "'",
        std::make_error_code(std::errc::invalid_argument));
  return D;
}

} // namespace

Error Profile::addBlock(Block &&B) {
  if (B.PathData.empty())
    return make_error<StringError>(
        "Block may not have empty path data.",
        std::make_error_code(std::errc::invalid_argument));

  Blocks.emplace_back(std::move(B));
  return Error::success();
}

Expected<std::vector<Profile::FuncID>> Profile::expandPath(PathID P) const {
  auto It = PathIDMap.find(P);
  if (It == PathIDMap.end())
    return make_error<StringError>(
        Twine("PathID not found: ") + Twine(P),
        std::make_error_code(std::errc::invalid_argument));
  std::vector<Profile::FuncID> Path;
  for (auto Node = It->second; Node; Node = Node->Caller)
    Path.push_back(Node->Func);
  return std::move(Path);
}

Profile::PathID Profile::internPath(ArrayRef<FuncID> P) {
  if (P.empty())
    return 0;

  auto RootToLeafPath = reverse(P);

  // Find the root.
  auto It = RootToLeafPath.begin();
  auto PathRoot = *It++;
  auto RootIt =
      find_if(Roots, [PathRoot](TrieNode *N) { return N->Func == PathRoot; });

  // If we've not seen this root before, remember it.
  TrieNode *Node = nullptr;
  if (RootIt == Roots.end()) {
    NodeStorage.emplace_back();
    Node = &NodeStorage.back();
    Node->Func = PathRoot;
    Roots.push_back(Node);
  } else {
    Node = *RootIt;
  }

  // Now traverse the path, re-creating if necessary.
  while (It != RootToLeafPath.end()) {
    auto NodeFuncID = *It++;
    auto CalleeIt = find_if(Node->Callees, [NodeFuncID](TrieNode *N) {
      return N->Func == NodeFuncID;
    });
    if (CalleeIt == Node->Callees.end()) {
      NodeStorage.emplace_back();
      auto NewNode = &NodeStorage.back();
      NewNode->Func = NodeFuncID;
      NewNode->Caller = Node;
      Node->Callees.push_back(NewNode);
      Node = NewNode;
    } else {
      Node = *CalleeIt;
    }
  }

  // At this point, Node *must* be pointing at the leaf.
  assert(Node->Func == P.front());
  if (Node->ID == 0) {
    Node->ID = NextID++;
    PathIDMap.insert({Node->ID, Node});
  }
  return Node->ID;
}

Profile mergeProfilesByThread(const Profile &L, const Profile &R) {
  Profile Merged;
  using PathDataMap = DenseMap<Profile::PathID, Profile::Data>;
  using PathDataMapPtr = std::unique_ptr<PathDataMap>;
  using PathDataVector = decltype(Profile::Block::PathData);
  using ThreadProfileIndexMap = DenseMap<Profile::ThreadID, PathDataMapPtr>;
  ThreadProfileIndexMap ThreadProfileIndex;

  for (const auto &P : {std::ref(L), std::ref(R)})
    for (const auto &Block : P.get()) {
      ThreadProfileIndexMap::iterator It;
      std::tie(It, std::ignore) = ThreadProfileIndex.insert(
          {Block.Thread, PathDataMapPtr{new PathDataMap()}});
      for (const auto &PathAndData : Block.PathData) {
        auto &PathID = PathAndData.first;
        auto &Data = PathAndData.second;
        auto NewPathID =
            Merged.internPath(cantFail(P.get().expandPath(PathID)));
        PathDataMap::iterator PathDataIt;
        bool Inserted;
        std::tie(PathDataIt, Inserted) = It->second->insert({NewPathID, Data});
        if (!Inserted) {
          auto &ExistingData = PathDataIt->second;
          ExistingData.CallCount += Data.CallCount;
          ExistingData.CumulativeLocalTime += Data.CumulativeLocalTime;
        }
      }
    }

  for (const auto &IndexedThreadBlock : ThreadProfileIndex) {
    PathDataVector PathAndData;
    PathAndData.reserve(IndexedThreadBlock.second->size());
    copy(*IndexedThreadBlock.second, std::back_inserter(PathAndData));
    cantFail(
        Merged.addBlock({IndexedThreadBlock.first, std::move(PathAndData)}));
  }
  return Merged;
}

Profile mergeProfilesByStack(const Profile &L, const Profile &R) {
  Profile Merged;
  using PathDataMap = DenseMap<Profile::PathID, Profile::Data>;
  PathDataMap PathData;
  using PathDataVector = decltype(Profile::Block::PathData);
  for (const auto &P : {std::ref(L), std::ref(R)})
    for (const auto &Block : P.get())
      for (const auto &PathAndData : Block.PathData) {
        auto &PathId = PathAndData.first;
        auto &Data = PathAndData.second;
        auto NewPathID =
            Merged.internPath(cantFail(P.get().expandPath(PathId)));
        PathDataMap::iterator PathDataIt;
        bool Inserted;
        std::tie(PathDataIt, Inserted) = PathData.insert({NewPathID, Data});
        if (!Inserted) {
          auto &ExistingData = PathDataIt->second;
          ExistingData.CallCount += Data.CallCount;
          ExistingData.CumulativeLocalTime += Data.CumulativeLocalTime;
        }
      }

  // In the end there's a single Block, for thread 0.
  PathDataVector Block;
  Block.reserve(PathData.size());
  copy(PathData, std::back_inserter(Block));
  cantFail(Merged.addBlock({0, std::move(Block)}));
  return Merged;
}

Expected<Profile> loadProfile(StringRef Filename) {
  int Fd;
  if (auto EC = sys::fs::openFileForRead(Filename, Fd))
    return make_error<StringError>(
        Twine("Cannot read profile from '") + Filename + "'", EC);

  uint64_t FileSize;
  if (auto EC = sys::fs::file_size(Filename, FileSize))
    return make_error<StringError>(
        Twine("Cannot get filesize of '") + Filename + "'", EC);

  std::error_code EC;
  sys::fs::mapped_file_region MappedFile(
      Fd, sys::fs::mapped_file_region::mapmode::readonly, FileSize, 0, EC);
  if (EC)
    return make_error<StringError>(
        Twine("Cannot mmap profile '") + Filename + "'", EC);
  StringRef Data(MappedFile.data(), MappedFile.size());

  Profile P;
  uint32_t Offset = 0;
  DataExtractor Extractor(Data, true, 8);

  // For each block we get from the file:
  while (Offset != MappedFile.size()) {
    auto HeaderOrError = readBlockHeader(Extractor, Offset);
    if (!HeaderOrError)
      return HeaderOrError.takeError();

    // TODO: Maybe store this header information for each block, even just for
    // debugging?
    const auto &Header = HeaderOrError.get();

    // Read in the path data.
    auto PathOrError = readPath(Extractor, Offset);
    if (!PathOrError)
      return PathOrError.takeError();
    const auto &Path = PathOrError.get();

    // For each path we encounter, we should intern it to get a PathID.
    auto DataOrError = readData(Extractor, Offset);
    if (!DataOrError)
      return DataOrError.takeError();
    auto &Data = DataOrError.get();

    if (auto E =
            P.addBlock(Profile::Block{Profile::ThreadID{Header.Thread},
                                      {{P.internPath(Path), std::move(Data)}}}))
      return std::move(E);
  }

  return P;
}

namespace {

struct StackEntry {
  uint64_t Timestamp;
  Profile::FuncID FuncId;
};

} // namespace

Expected<Profile> profileFromTrace(const Trace &T) {
  Profile P;

  // The implementation of the algorithm re-creates the execution of
  // the functions based on the trace data. To do this, we set up a number of
  // data structures to track the execution context of every thread in the
  // Trace.
  DenseMap<Profile::ThreadID, std::vector<StackEntry>> ThreadStacks;
  DenseMap<Profile::ThreadID, DenseMap<Profile::PathID, Profile::Data>>
      ThreadPathData;

  //  We then do a pass through the Trace to account data on a per-thread-basis.
  for (const auto &E : T) {
    auto &TSD = ThreadStacks[E.TId];
    switch (E.Type) {
    case RecordTypes::ENTER:
    case RecordTypes::ENTER_ARG:

      // Push entries into the function call stack.
      TSD.push_back({E.TSC, E.FuncId});
      break;

    case RecordTypes::EXIT:
    case RecordTypes::TAIL_EXIT:

      // Exits cause some accounting to happen, based on the state of the stack.
      // For each function we pop off the stack, we take note of the path and
      // record the cumulative state for this path. As we're doing this, we
      // intern the path into the Profile.
      while (!TSD.empty()) {
        auto Top = TSD.back();
        auto FunctionLocalTime = AbsoluteDifference(Top.Timestamp, E.TSC);
        SmallVector<Profile::FuncID, 16> Path;
        transform(reverse(TSD), std::back_inserter(Path),
                  std::mem_fn(&StackEntry::FuncId));
        auto InternedPath = P.internPath(Path);
        auto &TPD = ThreadPathData[E.TId][InternedPath];
        ++TPD.CallCount;
        TPD.CumulativeLocalTime += FunctionLocalTime;
        TSD.pop_back();

        // If we've matched the corresponding entry event for this function,
        // then we exit the loop.
        if (Top.FuncId == E.FuncId)
          break;

        // FIXME: Consider the intermediate times and the cumulative tree time
        // as well.
      }

      break;

    case RecordTypes::CUSTOM_EVENT:
    case RecordTypes::TYPED_EVENT:
      // TODO: Support an extension point to allow handling of custom and typed
      // events in profiles.
      break;
    }
  }

  // Once we've gone through the Trace, we now create one Block per thread in
  // the Profile.
  for (const auto &ThreadPaths : ThreadPathData) {
    const auto &TID = ThreadPaths.first;
    const auto &PathsData = ThreadPaths.second;
    if (auto E = P.addBlock({
            TID,
            std::vector<std::pair<Profile::PathID, Profile::Data>>(
                PathsData.begin(), PathsData.end()),
        }))
      return std::move(E);
  }

  return P;
}

} // namespace xray
} // namespace llvm