1 /*===- RootAutodetector.h- auto-detect roots for ctxprof -----------------===*\ 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 #ifndef CTX_PROFILE_ROOTAUTODETECTOR_H_ 10 #define CTX_PROFILE_ROOTAUTODETECTOR_H_ 11 12 #include "sanitizer_common/sanitizer_dense_map.h" 13 #include "sanitizer_common/sanitizer_internal_defs.h" 14 #include "sanitizer_common/sanitizer_stacktrace.h" 15 #include "sanitizer_common/sanitizer_vector.h" 16 #include <pthread.h> 17 #include <sanitizer/common_interface_defs.h> 18 19 using namespace __asan; 20 using namespace __sanitizer; 21 22 namespace __ctx_profile { 23 24 /// Capture all the stack traces observed for a specific thread. The "for a 25 /// specific thread" part is not enforced, but assumed in determineRoots. 26 class PerThreadCallsiteTrie { 27 protected: 28 /// A trie. A node is the address of a callsite in a function activation. A 29 /// child is a callsite in the activation made from the callsite 30 /// corresponding to the parent. 31 struct Trie final { 32 const uptr CallsiteAddress; 33 uint64_t Count = 0; 34 DenseMap<uptr, Trie> Children; 35 CallsiteAddressfinal36 Trie(uptr CallsiteAddress = 0) : CallsiteAddress(CallsiteAddress) {} 37 }; 38 Trie TheTrie; 39 40 /// Return the runtime start address of the function that contains the call at 41 /// the runtime address CallsiteAddress. May be overriden for easy testing. 42 virtual uptr getFctStartAddr(uptr CallsiteAddress) const; 43 44 public: 45 PerThreadCallsiteTrie(const PerThreadCallsiteTrie &) = delete; 46 PerThreadCallsiteTrie(PerThreadCallsiteTrie &&) = default; 47 PerThreadCallsiteTrie() = default; 48 49 virtual ~PerThreadCallsiteTrie() = default; 50 51 void insertStack(const StackTrace &ST); 52 53 /// Return the runtime address of root functions, as determined for this 54 /// thread, together with the number of samples that included them. 55 DenseMap<uptr, uint64_t> determineRoots() const; 56 }; 57 58 class RootAutoDetector final { 59 // A prime number. We may want to make this configurable at collection start. 60 static const uint64_t SampleRate = 6113; 61 const unsigned WaitSeconds; 62 pthread_t WorkerThread; 63 64 struct PerThreadSamples { 65 PerThreadSamples(RootAutoDetector &Parent); 66 67 PerThreadCallsiteTrie TrieRoot; 68 SpinMutex M; 69 }; 70 SpinMutex AllSamplesMutex; 71 SANITIZER_GUARDED_BY(AllSamplesMutex) 72 Vector<PerThreadSamples *> AllSamples; 73 atomic_uintptr_t &FunctionDataListHead; 74 atomic_uintptr_t &Self; 75 void collectStack(); 76 77 public: RootAutoDetector(atomic_uintptr_t & FunctionDataListHead,atomic_uintptr_t & Self,unsigned WaitSeconds)78 RootAutoDetector(atomic_uintptr_t &FunctionDataListHead, 79 atomic_uintptr_t &Self, unsigned WaitSeconds) 80 : WaitSeconds(WaitSeconds), FunctionDataListHead(FunctionDataListHead), 81 Self(Self) {} 82 83 // Samples the stack at `SampleRate` (rate observed independently on each 84 // thread) in thread local `PerThreadCallsiteTrie`s. 85 void sample(); 86 87 // Start a thread waiting `WaitSeconds`, after which it uses the 88 // `PerThreadCallsiteTrie` data observed so far over all threads to determine 89 // roots. Marks those roots by traversing the linked list of FunctionData that 90 // starts at `FunctionDataListHead`, and assigning their `CtxRoot`. Finally, 91 // resets the `Self` atomic, so that other threads don't continue calling 92 // `sample`. 93 void start(); 94 95 // join the waiting thread. 96 void join(); 97 }; 98 99 } // namespace __ctx_profile 100 #endif 101