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