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 25 namespace __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. 92 class FunctionCallTrie { 93 public: 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 121 private: 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 132 public: 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 321 private: 322 NodeArray Nodes; 323 RootArray Roots; 324 ShadowStackArray ShadowStack; 325 NodeIdPairAllocatorType *NodeIdPairAllocator; 326 uint32_t OverflowedFunctions; 327 328 public: 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