1//===-- xray_function_call_trie.h ------------------------------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file is a part of XRay, a dynamic runtime instrumentation system.
11//
12// This file defines the interface for a function call trie.
13//
14//===----------------------------------------------------------------------===//
15#ifndef XRAY_FUNCTION_CALL_TRIE_H
16#define XRAY_FUNCTION_CALL_TRIE_H
17
18#include "xray_buffer_queue.h"
19#include "xray_defs.h"
20#include "xray_profiling_flags.h"
21#include "xray_segmented_array.h"
22#include <limits>
23#include <memory> // For placement new.
24#include <utility>
25
26namespace __xray {
27
28/// A FunctionCallTrie represents the stack traces of XRay instrumented
29/// functions that we've encountered, where a node corresponds to a function and
30/// the path from the root to the node its stack trace. Each node in the trie
31/// will contain some useful values, including:
32///
33///   * The cumulative amount of time spent in this particular node/stack.
34///   * The number of times this stack has appeared.
35///   * A histogram of latencies for that particular node.
36///
37/// Each node in the trie will also contain a list of callees, represented using
38/// a Array<NodeIdPair> -- each NodeIdPair instance will contain the function
39/// ID of the callee, and a pointer to the node.
40///
41/// If we visualise this data structure, we'll find the following potential
42/// representation:
43///
44///   [function id node] -> [callees] [cumulative time]
45///                         [call counter] [latency histogram]
46///
47/// As an example, when we have a function in this pseudocode:
48///
49///   func f(N) {
50///     g()
51///     h()
52///     for i := 1..N { j() }
53///   }
54///
55/// We may end up with a trie of the following form:
56///
57///   f -> [ g, h, j ] [...] [1] [...]
58///   g -> [ ... ] [...] [1] [...]
59///   h -> [ ... ] [...] [1] [...]
60///   j -> [ ... ] [...] [N] [...]
61///
62/// If for instance the function g() called j() like so:
63///
64///   func g() {
65///     for i := 1..10 { j() }
66///   }
67///
68/// We'll find the following updated trie:
69///
70///   f -> [ g, h, j ] [...] [1] [...]
71///   g -> [ j' ] [...] [1] [...]
72///   h -> [ ... ] [...] [1] [...]
73///   j -> [ ... ] [...] [N] [...]
74///   j' -> [ ... ] [...] [10] [...]
75///
76/// Note that we'll have a new node representing the path `f -> g -> j'` with
77/// isolated data. This isolation gives us a means of representing the stack
78/// traces as a path, as opposed to a key in a table. The alternative
79/// implementation here would be to use a separate table for the path, and use
80/// hashes of the path as an identifier to accumulate the information. We've
81/// moved away from this approach as it takes a lot of time to compute the hash
82/// every time we need to update a function's call information as we're handling
83/// the entry and exit events.
84///
85/// This approach allows us to maintain a shadow stack, which represents the
86/// currently executing path, and on function exits quickly compute the amount
87/// of time elapsed from the entry, then update the counters for the node
88/// already represented in the trie. This necessitates an efficient
89/// representation of the various data structures (the list of callees must be
90/// cache-aware and efficient to look up, and the histogram must be compact and
91/// quick to update) to enable us to keep the overheads of this implementation
92/// to the minimum.
93class FunctionCallTrie {
94public:
95  struct Node;
96
97  // We use a NodeIdPair type instead of a std::pair<...> to not rely on the
98  // standard library types in this header.
99  struct NodeIdPair {
100    Node *NodePtr;
101    int32_t FId;
102  };
103
104  using NodeIdPairArray = Array<NodeIdPair>;
105  using NodeIdPairAllocatorType = NodeIdPairArray::AllocatorType;
106
107  // A Node in the FunctionCallTrie gives us a list of callees, the cumulative
108  // number of times this node actually appeared, the cumulative amount of time
109  // for this particular node including its children call times, and just the
110  // local time spent on this node. Each Node will have the ID of the XRay
111  // instrumented function that it is associated to.
112  struct Node {
113    Node *Parent;
114    NodeIdPairArray Callees;
115    uint64_t CallCount;
116    uint64_t CumulativeLocalTime; // Typically in TSC deltas, not wall-time.
117    int32_t FId;
118
119    // TODO: Include the compact histogram.
120  };
121
122private:
123  struct ShadowStackEntry {
124    uint64_t EntryTSC;
125    Node *NodePtr;
126    uint16_t EntryCPU;
127  };
128
129  using NodeArray = Array<Node>;
130  using RootArray = Array<Node *>;
131  using ShadowStackArray = Array<ShadowStackEntry>;
132
133public:
134  // We collate the allocators we need into a single struct, as a convenience to
135  // allow us to initialize these as a group.
136  struct Allocators {
137    using NodeAllocatorType = NodeArray::AllocatorType;
138    using RootAllocatorType = RootArray::AllocatorType;
139    using ShadowStackAllocatorType = ShadowStackArray::AllocatorType;
140
141    // Use hosted aligned storage members to allow for trivial move and init.
142    // This also allows us to sidestep the potential-failing allocation issue.
143    typename std::aligned_storage<sizeof(NodeAllocatorType),
144                                  alignof(NodeAllocatorType)>::type
145        NodeAllocatorStorage;
146    typename std::aligned_storage<sizeof(RootAllocatorType),
147                                  alignof(RootAllocatorType)>::type
148        RootAllocatorStorage;
149    typename std::aligned_storage<sizeof(ShadowStackAllocatorType),
150                                  alignof(ShadowStackAllocatorType)>::type
151        ShadowStackAllocatorStorage;
152    typename std::aligned_storage<sizeof(NodeIdPairAllocatorType),
153                                  alignof(NodeIdPairAllocatorType)>::type
154        NodeIdPairAllocatorStorage;
155
156    NodeAllocatorType *NodeAllocator = nullptr;
157    RootAllocatorType *RootAllocator = nullptr;
158    ShadowStackAllocatorType *ShadowStackAllocator = nullptr;
159    NodeIdPairAllocatorType *NodeIdPairAllocator = nullptr;
160
161    Allocators() = default;
162    Allocators(const Allocators &) = delete;
163    Allocators &operator=(const Allocators &) = delete;
164
165    struct Buffers {
166      BufferQueue::Buffer NodeBuffer;
167      BufferQueue::Buffer RootsBuffer;
168      BufferQueue::Buffer ShadowStackBuffer;
169      BufferQueue::Buffer NodeIdPairBuffer;
170    };
171
172    explicit Allocators(Buffers &B) XRAY_NEVER_INSTRUMENT {
173      new (&NodeAllocatorStorage)
174          NodeAllocatorType(B.NodeBuffer.Data, B.NodeBuffer.Size);
175      NodeAllocator =
176          reinterpret_cast<NodeAllocatorType *>(&NodeAllocatorStorage);
177
178      new (&RootAllocatorStorage)
179          RootAllocatorType(B.RootsBuffer.Data, B.RootsBuffer.Size);
180      RootAllocator =
181          reinterpret_cast<RootAllocatorType *>(&RootAllocatorStorage);
182
183      new (&ShadowStackAllocatorStorage) ShadowStackAllocatorType(
184          B.ShadowStackBuffer.Data, B.ShadowStackBuffer.Size);
185      ShadowStackAllocator = reinterpret_cast<ShadowStackAllocatorType *>(
186          &ShadowStackAllocatorStorage);
187
188      new (&NodeIdPairAllocatorStorage) NodeIdPairAllocatorType(
189          B.NodeIdPairBuffer.Data, B.NodeIdPairBuffer.Size);
190      NodeIdPairAllocator = reinterpret_cast<NodeIdPairAllocatorType *>(
191          &NodeIdPairAllocatorStorage);
192    }
193
194    explicit Allocators(uptr Max) XRAY_NEVER_INSTRUMENT {
195      new (&NodeAllocatorStorage) NodeAllocatorType(Max);
196      NodeAllocator =
197          reinterpret_cast<NodeAllocatorType *>(&NodeAllocatorStorage);
198
199      new (&RootAllocatorStorage) RootAllocatorType(Max);
200      RootAllocator =
201          reinterpret_cast<RootAllocatorType *>(&RootAllocatorStorage);
202
203      new (&ShadowStackAllocatorStorage) ShadowStackAllocatorType(Max);
204      ShadowStackAllocator = reinterpret_cast<ShadowStackAllocatorType *>(
205          &ShadowStackAllocatorStorage);
206
207      new (&NodeIdPairAllocatorStorage) NodeIdPairAllocatorType(Max);
208      NodeIdPairAllocator = reinterpret_cast<NodeIdPairAllocatorType *>(
209          &NodeIdPairAllocatorStorage);
210    }
211
212    Allocators(Allocators &&O) XRAY_NEVER_INSTRUMENT {
213      // Here we rely on the safety of memcpy'ing contents of the storage
214      // members, and then pointing the source pointers to nullptr.
215      internal_memcpy(&NodeAllocatorStorage, &O.NodeAllocatorStorage,
216                      sizeof(NodeAllocatorType));
217      internal_memcpy(&RootAllocatorStorage, &O.RootAllocatorStorage,
218                      sizeof(RootAllocatorType));
219      internal_memcpy(&ShadowStackAllocatorStorage,
220                      &O.ShadowStackAllocatorStorage,
221                      sizeof(ShadowStackAllocatorType));
222      internal_memcpy(&NodeIdPairAllocatorStorage,
223                      &O.NodeIdPairAllocatorStorage,
224                      sizeof(NodeIdPairAllocatorType));
225
226      NodeAllocator =
227          reinterpret_cast<NodeAllocatorType *>(&NodeAllocatorStorage);
228      RootAllocator =
229          reinterpret_cast<RootAllocatorType *>(&RootAllocatorStorage);
230      ShadowStackAllocator = reinterpret_cast<ShadowStackAllocatorType *>(
231          &ShadowStackAllocatorStorage);
232      NodeIdPairAllocator = reinterpret_cast<NodeIdPairAllocatorType *>(
233          &NodeIdPairAllocatorStorage);
234
235      O.NodeAllocator = nullptr;
236      O.RootAllocator = nullptr;
237      O.ShadowStackAllocator = nullptr;
238      O.NodeIdPairAllocator = nullptr;
239    }
240
241    Allocators &operator=(Allocators &&O) XRAY_NEVER_INSTRUMENT {
242      // When moving into an existing instance, we ensure that we clean up the
243      // current allocators.
244      if (NodeAllocator)
245        NodeAllocator->~NodeAllocatorType();
246      if (O.NodeAllocator) {
247        new (&NodeAllocatorStorage)
248            NodeAllocatorType(std::move(*O.NodeAllocator));
249        NodeAllocator =
250            reinterpret_cast<NodeAllocatorType *>(&NodeAllocatorStorage);
251        O.NodeAllocator = nullptr;
252      } else {
253        NodeAllocator = nullptr;
254      }
255
256      if (RootAllocator)
257        RootAllocator->~RootAllocatorType();
258      if (O.RootAllocator) {
259        new (&RootAllocatorStorage)
260            RootAllocatorType(std::move(*O.RootAllocator));
261        RootAllocator =
262            reinterpret_cast<RootAllocatorType *>(&RootAllocatorStorage);
263        O.RootAllocator = nullptr;
264      } else {
265        RootAllocator = nullptr;
266      }
267
268      if (ShadowStackAllocator)
269        ShadowStackAllocator->~ShadowStackAllocatorType();
270      if (O.ShadowStackAllocator) {
271        new (&ShadowStackAllocatorStorage)
272            ShadowStackAllocatorType(std::move(*O.ShadowStackAllocator));
273        ShadowStackAllocator = reinterpret_cast<ShadowStackAllocatorType *>(
274            &ShadowStackAllocatorStorage);
275        O.ShadowStackAllocator = nullptr;
276      } else {
277        ShadowStackAllocator = nullptr;
278      }
279
280      if (NodeIdPairAllocator)
281        NodeIdPairAllocator->~NodeIdPairAllocatorType();
282      if (O.NodeIdPairAllocator) {
283        new (&NodeIdPairAllocatorStorage)
284            NodeIdPairAllocatorType(std::move(*O.NodeIdPairAllocator));
285        NodeIdPairAllocator = reinterpret_cast<NodeIdPairAllocatorType *>(
286            &NodeIdPairAllocatorStorage);
287        O.NodeIdPairAllocator = nullptr;
288      } else {
289        NodeIdPairAllocator = nullptr;
290      }
291
292      return *this;
293    }
294
295    ~Allocators() XRAY_NEVER_INSTRUMENT {
296      if (NodeAllocator != nullptr)
297        NodeAllocator->~NodeAllocatorType();
298      if (RootAllocator != nullptr)
299        RootAllocator->~RootAllocatorType();
300      if (ShadowStackAllocator != nullptr)
301        ShadowStackAllocator->~ShadowStackAllocatorType();
302      if (NodeIdPairAllocator != nullptr)
303        NodeIdPairAllocator->~NodeIdPairAllocatorType();
304    }
305  };
306
307  static Allocators InitAllocators() XRAY_NEVER_INSTRUMENT {
308    return InitAllocatorsCustom(profilingFlags()->per_thread_allocator_max);
309  }
310
311  static Allocators InitAllocatorsCustom(uptr Max) XRAY_NEVER_INSTRUMENT {
312    Allocators A(Max);
313    return A;
314  }
315
316  static Allocators
317  InitAllocatorsFromBuffers(Allocators::Buffers &Bufs) XRAY_NEVER_INSTRUMENT {
318    Allocators A(Bufs);
319    return A;
320  }
321
322private:
323  NodeArray Nodes;
324  RootArray Roots;
325  ShadowStackArray ShadowStack;
326  NodeIdPairAllocatorType *NodeIdPairAllocator;
327  uint32_t OverflowedFunctions;
328
329public:
330  explicit FunctionCallTrie(const Allocators &A) XRAY_NEVER_INSTRUMENT
331      : Nodes(*A.NodeAllocator),
332        Roots(*A.RootAllocator),
333        ShadowStack(*A.ShadowStackAllocator),
334        NodeIdPairAllocator(A.NodeIdPairAllocator),
335        OverflowedFunctions(0) {}
336
337  FunctionCallTrie() = delete;
338  FunctionCallTrie(const FunctionCallTrie &) = delete;
339  FunctionCallTrie &operator=(const FunctionCallTrie &) = delete;
340
341  FunctionCallTrie(FunctionCallTrie &&O) XRAY_NEVER_INSTRUMENT
342      : Nodes(std::move(O.Nodes)),
343        Roots(std::move(O.Roots)),
344        ShadowStack(std::move(O.ShadowStack)),
345        NodeIdPairAllocator(O.NodeIdPairAllocator),
346        OverflowedFunctions(O.OverflowedFunctions) {}
347
348  FunctionCallTrie &operator=(FunctionCallTrie &&O) XRAY_NEVER_INSTRUMENT {
349    Nodes = std::move(O.Nodes);
350    Roots = std::move(O.Roots);
351    ShadowStack = std::move(O.ShadowStack);
352    NodeIdPairAllocator = O.NodeIdPairAllocator;
353    OverflowedFunctions = O.OverflowedFunctions;
354    return *this;
355  }
356
357  ~FunctionCallTrie() XRAY_NEVER_INSTRUMENT {}
358
359  void enterFunction(const int32_t FId, uint64_t TSC,
360                     uint16_t CPU) XRAY_NEVER_INSTRUMENT {
361    DCHECK_NE(FId, 0);
362
363    // If we're already overflowed the function call stack, do not bother
364    // attempting to record any more function entries.
365    if (UNLIKELY(OverflowedFunctions)) {
366      ++OverflowedFunctions;
367      return;
368    }
369
370    // If this is the first function we've encountered, we want to set up the
371    // node(s) and treat it as a root.
372    if (UNLIKELY(ShadowStack.empty())) {
373      auto *NewRoot = Nodes.AppendEmplace(
374          nullptr, NodeIdPairArray(*NodeIdPairAllocator), 0u, 0u, FId);
375      if (UNLIKELY(NewRoot == nullptr))
376        return;
377      if (Roots.AppendEmplace(NewRoot) == nullptr) {
378        Nodes.trim(1);
379        return;
380      }
381      if (ShadowStack.AppendEmplace(TSC, NewRoot, CPU) == nullptr) {
382        Nodes.trim(1);
383        Roots.trim(1);
384        ++OverflowedFunctions;
385        return;
386      }
387      return;
388    }
389
390    // From this point on, we require that the stack is not empty.
391    DCHECK(!ShadowStack.empty());
392    auto TopNode = ShadowStack.back().NodePtr;
393    DCHECK_NE(TopNode, nullptr);
394
395    // If we've seen this callee before, then we access that node and place that
396    // on the top of the stack.
397    auto* Callee = TopNode->Callees.find_element(
398        [FId](const NodeIdPair &NR) { return NR.FId == FId; });
399    if (Callee != nullptr) {
400      CHECK_NE(Callee->NodePtr, nullptr);
401      if (ShadowStack.AppendEmplace(TSC, Callee->NodePtr, CPU) == nullptr)
402        ++OverflowedFunctions;
403      return;
404    }
405
406    // This means we've never seen this stack before, create a new node here.
407    auto* NewNode = Nodes.AppendEmplace(
408        TopNode, NodeIdPairArray(*NodeIdPairAllocator), 0u, 0u, FId);
409    if (UNLIKELY(NewNode == nullptr))
410      return;
411    DCHECK_NE(NewNode, nullptr);
412    TopNode->Callees.AppendEmplace(NewNode, FId);
413    if (ShadowStack.AppendEmplace(TSC, NewNode, CPU) == nullptr)
414      ++OverflowedFunctions;
415    return;
416  }
417
418  void exitFunction(int32_t FId, uint64_t TSC,
419                    uint16_t CPU) XRAY_NEVER_INSTRUMENT {
420    // If we're exiting functions that have "overflowed" or don't fit into the
421    // stack due to allocator constraints, we then decrement that count first.
422    if (OverflowedFunctions) {
423      --OverflowedFunctions;
424      return;
425    }
426
427    // When we exit a function, we look up the ShadowStack to see whether we've
428    // entered this function before. We do as little processing here as we can,
429    // since most of the hard work would have already been done at function
430    // entry.
431    uint64_t CumulativeTreeTime = 0;
432
433    while (!ShadowStack.empty()) {
434      const auto &Top = ShadowStack.back();
435      auto TopNode = Top.NodePtr;
436      DCHECK_NE(TopNode, nullptr);
437
438      // We may encounter overflow on the TSC we're provided, which may end up
439      // being less than the TSC when we first entered the function.
440      //
441      // To get the accurate measurement of cycles, we need to check whether
442      // we've overflowed (TSC < Top.EntryTSC) and then account the difference
443      // between the entry TSC and the max for the TSC counter (max of uint64_t)
444      // then add the value of TSC. We can prove that the maximum delta we will
445      // get is at most the 64-bit unsigned value, since the difference between
446      // a TSC of 0 and a Top.EntryTSC of 1 is (numeric_limits<uint64_t>::max()
447      // - 1) + 1.
448      //
449      // NOTE: This assumes that TSCs are synchronised across CPUs.
450      // TODO: Count the number of times we've seen CPU migrations.
451      uint64_t LocalTime =
452          Top.EntryTSC > TSC
453              ? (std::numeric_limits<uint64_t>::max() - Top.EntryTSC) + TSC
454              : TSC - Top.EntryTSC;
455      TopNode->CallCount++;
456      TopNode->CumulativeLocalTime += LocalTime - CumulativeTreeTime;
457      CumulativeTreeTime += LocalTime;
458      ShadowStack.trim(1);
459
460      // TODO: Update the histogram for the node.
461      if (TopNode->FId == FId)
462        break;
463    }
464  }
465
466  const RootArray &getRoots() const XRAY_NEVER_INSTRUMENT { return Roots; }
467
468  // The deepCopyInto operation will update the provided FunctionCallTrie by
469  // re-creating the contents of this particular FunctionCallTrie in the other
470  // FunctionCallTrie. It will do this using a Depth First Traversal from the
471  // roots, and while doing so recreating the traversal in the provided
472  // FunctionCallTrie.
473  //
474  // This operation will *not* destroy the state in `O`, and thus may cause some
475  // duplicate entries in `O` if it is not empty.
476  //
477  // This function is *not* thread-safe, and may require external
478  // synchronisation of both "this" and |O|.
479  //
480  // This function must *not* be called with a non-empty FunctionCallTrie |O|.
481  void deepCopyInto(FunctionCallTrie &O) const XRAY_NEVER_INSTRUMENT {
482    DCHECK(O.getRoots().empty());
483
484    // We then push the root into a stack, to use as the parent marker for new
485    // nodes we push in as we're traversing depth-first down the call tree.
486    struct NodeAndParent {
487      FunctionCallTrie::Node *Node;
488      FunctionCallTrie::Node *NewNode;
489    };
490    using Stack = Array<NodeAndParent>;
491
492    typename Stack::AllocatorType StackAllocator(
493        profilingFlags()->stack_allocator_max);
494    Stack DFSStack(StackAllocator);
495
496    for (const auto Root : getRoots()) {
497      // Add a node in O for this root.
498      auto NewRoot = O.Nodes.AppendEmplace(
499          nullptr, NodeIdPairArray(*O.NodeIdPairAllocator), Root->CallCount,
500          Root->CumulativeLocalTime, Root->FId);
501
502      // Because we cannot allocate more memory we should bail out right away.
503      if (UNLIKELY(NewRoot == nullptr))
504        return;
505
506      if (UNLIKELY(O.Roots.Append(NewRoot) == nullptr))
507        return;
508
509      // TODO: Figure out what to do if we fail to allocate any more stack
510      // space. Maybe warn or report once?
511      if (DFSStack.AppendEmplace(Root, NewRoot) == nullptr)
512        return;
513      while (!DFSStack.empty()) {
514        NodeAndParent NP = DFSStack.back();
515        DCHECK_NE(NP.Node, nullptr);
516        DCHECK_NE(NP.NewNode, nullptr);
517        DFSStack.trim(1);
518        for (const auto Callee : NP.Node->Callees) {
519          auto NewNode = O.Nodes.AppendEmplace(
520              NP.NewNode, NodeIdPairArray(*O.NodeIdPairAllocator),
521              Callee.NodePtr->CallCount, Callee.NodePtr->CumulativeLocalTime,
522              Callee.FId);
523          if (UNLIKELY(NewNode == nullptr))
524            return;
525          if (UNLIKELY(NP.NewNode->Callees.AppendEmplace(NewNode, Callee.FId) ==
526                       nullptr))
527            return;
528          if (UNLIKELY(DFSStack.AppendEmplace(Callee.NodePtr, NewNode) ==
529                       nullptr))
530            return;
531        }
532      }
533    }
534  }
535
536  // The mergeInto operation will update the provided FunctionCallTrie by
537  // traversing the current trie's roots and updating (i.e. merging) the data in
538  // the nodes with the data in the target's nodes. If the node doesn't exist in
539  // the provided trie, we add a new one in the right position, and inherit the
540  // data from the original (current) trie, along with all its callees.
541  //
542  // This function is *not* thread-safe, and may require external
543  // synchronisation of both "this" and |O|.
544  void mergeInto(FunctionCallTrie &O) const XRAY_NEVER_INSTRUMENT {
545    struct NodeAndTarget {
546      FunctionCallTrie::Node *OrigNode;
547      FunctionCallTrie::Node *TargetNode;
548    };
549    using Stack = Array<NodeAndTarget>;
550    typename Stack::AllocatorType StackAllocator(
551        profilingFlags()->stack_allocator_max);
552    Stack DFSStack(StackAllocator);
553
554    for (const auto Root : getRoots()) {
555      Node *TargetRoot = nullptr;
556      auto R = O.Roots.find_element(
557          [&](const Node *Node) { return Node->FId == Root->FId; });
558      if (R == nullptr) {
559        TargetRoot = O.Nodes.AppendEmplace(
560            nullptr, NodeIdPairArray(*O.NodeIdPairAllocator), 0u, 0u,
561            Root->FId);
562        if (UNLIKELY(TargetRoot == nullptr))
563          return;
564
565        O.Roots.Append(TargetRoot);
566      } else {
567        TargetRoot = *R;
568      }
569
570      DFSStack.AppendEmplace(Root, TargetRoot);
571      while (!DFSStack.empty()) {
572        NodeAndTarget NT = DFSStack.back();
573        DCHECK_NE(NT.OrigNode, nullptr);
574        DCHECK_NE(NT.TargetNode, nullptr);
575        DFSStack.trim(1);
576        // TODO: Update the histogram as well when we have it ready.
577        NT.TargetNode->CallCount += NT.OrigNode->CallCount;
578        NT.TargetNode->CumulativeLocalTime += NT.OrigNode->CumulativeLocalTime;
579        for (const auto Callee : NT.OrigNode->Callees) {
580          auto TargetCallee = NT.TargetNode->Callees.find_element(
581              [&](const FunctionCallTrie::NodeIdPair &C) {
582                return C.FId == Callee.FId;
583              });
584          if (TargetCallee == nullptr) {
585            auto NewTargetNode = O.Nodes.AppendEmplace(
586                NT.TargetNode, NodeIdPairArray(*O.NodeIdPairAllocator), 0u, 0u,
587                Callee.FId);
588
589            if (UNLIKELY(NewTargetNode == nullptr))
590              return;
591
592            TargetCallee =
593                NT.TargetNode->Callees.AppendEmplace(NewTargetNode, Callee.FId);
594          }
595          DFSStack.AppendEmplace(Callee.NodePtr, TargetCallee->NodePtr);
596        }
597      }
598    }
599  }
600};
601
602} // namespace __xray
603
604#endif // XRAY_FUNCTION_CALL_TRIE_H
605