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
19using namespace __asan;
20using namespace __sanitizer;
21
22namespace __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.
26class PerThreadCallsiteTrie {
27protected:
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
36 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
44public:
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
58class 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
77public:
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