1 //===-- xray_fdr_controller.h ---------------------------------------------===//
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 function call tracing system.
10 //
11 //===----------------------------------------------------------------------===//
12 #ifndef COMPILER_RT_LIB_XRAY_XRAY_FDR_CONTROLLER_H_
13 #define COMPILER_RT_LIB_XRAY_XRAY_FDR_CONTROLLER_H_
14 
15 #include <limits>
16 #include <time.h>
17 
18 #include "xray/xray_interface.h"
19 #include "xray/xray_records.h"
20 #include "xray_buffer_queue.h"
21 #include "xray_fdr_log_writer.h"
22 
23 namespace __xray {
24 
25 template <size_t Version = 5> class FDRController {
26   BufferQueue *BQ;
27   BufferQueue::Buffer &B;
28   FDRLogWriter &W;
29   int (*WallClockReader)(clockid_t, struct timespec *) = 0;
30   uint64_t CycleThreshold = 0;
31 
32   uint64_t LastFunctionEntryTSC = 0;
33   uint64_t LatestTSC = 0;
34   uint16_t LatestCPU = 0;
35   tid_t TId = 0;
36   pid_t PId = 0;
37   bool First = true;
38 
39   uint32_t UndoableFunctionEnters = 0;
40   uint32_t UndoableTailExits = 0;
41 
finalized()42   bool finalized() const XRAY_NEVER_INSTRUMENT {
43     return BQ == nullptr || BQ->finalizing();
44   }
45 
hasSpace(size_t S)46   bool hasSpace(size_t S) XRAY_NEVER_INSTRUMENT {
47     return B.Data != nullptr && B.Generation == BQ->generation() &&
48            W.getNextRecord() + S <= reinterpret_cast<char *>(B.Data) + B.Size;
49   }
50 
mask(int32_t FuncId)51   constexpr int32_t mask(int32_t FuncId) const XRAY_NEVER_INSTRUMENT {
52     return FuncId & ((1 << 29) - 1);
53   }
54 
getNewBuffer()55   bool getNewBuffer() XRAY_NEVER_INSTRUMENT {
56     if (BQ->getBuffer(B) != BufferQueue::ErrorCode::Ok)
57       return false;
58 
59     W.resetRecord();
60     DCHECK_EQ(W.getNextRecord(), B.Data);
61     LatestTSC = 0;
62     LatestCPU = 0;
63     First = true;
64     UndoableFunctionEnters = 0;
65     UndoableTailExits = 0;
66     atomic_store(B.Extents, 0, memory_order_release);
67     return true;
68   }
69 
setupNewBuffer()70   bool setupNewBuffer() XRAY_NEVER_INSTRUMENT {
71     if (finalized())
72       return false;
73 
74     DCHECK(hasSpace(sizeof(MetadataRecord) * 3));
75     TId = GetTid();
76     PId = internal_getpid();
77     struct timespec TS {
78       0, 0
79     };
80     WallClockReader(CLOCK_MONOTONIC, &TS);
81 
82     MetadataRecord Metadata[] = {
83         // Write out a MetadataRecord to signify that this is the start of a new
84         // buffer, associated with a particular thread, with a new CPU. For the
85         // data, we have 15 bytes to squeeze as much information as we can. At
86         // this point we only write down the following bytes:
87         //   - Thread ID (tid_t, cast to 4 bytes type due to Darwin being 8
88         //   bytes)
89         createMetadataRecord<MetadataRecord::RecordKinds::NewBuffer>(
90             static_cast<int32_t>(TId)),
91 
92         // Also write the WalltimeMarker record. We only really need microsecond
93         // precision here, and enforce across platforms that we need 64-bit
94         // seconds and 32-bit microseconds encoded in the Metadata record.
95         createMetadataRecord<MetadataRecord::RecordKinds::WalltimeMarker>(
96             static_cast<int64_t>(TS.tv_sec),
97             static_cast<int32_t>(TS.tv_nsec / 1000)),
98 
99         // Also write the Pid record.
100         createMetadataRecord<MetadataRecord::RecordKinds::Pid>(
101             static_cast<int32_t>(PId)),
102     };
103 
104     if (finalized())
105       return false;
106     return W.writeMetadataRecords(Metadata);
107   }
108 
prepareBuffer(size_t S)109   bool prepareBuffer(size_t S) XRAY_NEVER_INSTRUMENT {
110     if (finalized())
111       return returnBuffer();
112 
113     if (UNLIKELY(!hasSpace(S))) {
114       if (!returnBuffer())
115         return false;
116       if (!getNewBuffer())
117         return false;
118       if (!setupNewBuffer())
119         return false;
120     }
121 
122     if (First) {
123       First = false;
124       W.resetRecord();
125       atomic_store(B.Extents, 0, memory_order_release);
126       return setupNewBuffer();
127     }
128 
129     return true;
130   }
131 
returnBuffer()132   bool returnBuffer() XRAY_NEVER_INSTRUMENT {
133     if (BQ == nullptr)
134       return false;
135 
136     First = true;
137     if (finalized()) {
138       BQ->releaseBuffer(B); // ignore result.
139       return false;
140     }
141 
142     return BQ->releaseBuffer(B) == BufferQueue::ErrorCode::Ok;
143   }
144 
145   enum class PreambleResult { NoChange, WroteMetadata, InvalidBuffer };
recordPreamble(uint64_t TSC,uint16_t CPU)146   PreambleResult recordPreamble(uint64_t TSC,
147                                 uint16_t CPU) XRAY_NEVER_INSTRUMENT {
148     if (UNLIKELY(LatestCPU != CPU || LatestTSC == 0)) {
149       // We update our internal tracking state for the Latest TSC and CPU we've
150       // seen, then write out the appropriate metadata and function records.
151       LatestTSC = TSC;
152       LatestCPU = CPU;
153 
154       if (B.Generation != BQ->generation())
155         return PreambleResult::InvalidBuffer;
156 
157       W.writeMetadata<MetadataRecord::RecordKinds::NewCPUId>(CPU, TSC);
158       return PreambleResult::WroteMetadata;
159     }
160 
161     DCHECK_EQ(LatestCPU, CPU);
162 
163     if (UNLIKELY(LatestTSC > TSC ||
164                  TSC - LatestTSC >
165                      uint64_t{std::numeric_limits<int32_t>::max()})) {
166       // Either the TSC has wrapped around from the last TSC we've seen or the
167       // delta is too large to fit in a 32-bit signed integer, so we write a
168       // wrap-around record.
169       LatestTSC = TSC;
170 
171       if (B.Generation != BQ->generation())
172         return PreambleResult::InvalidBuffer;
173 
174       W.writeMetadata<MetadataRecord::RecordKinds::TSCWrap>(TSC);
175       return PreambleResult::WroteMetadata;
176     }
177 
178     return PreambleResult::NoChange;
179   }
180 
rewindRecords(int32_t FuncId,uint64_t TSC,uint16_t CPU)181   bool rewindRecords(int32_t FuncId, uint64_t TSC,
182                      uint16_t CPU) XRAY_NEVER_INSTRUMENT {
183     // Undo one enter record, because at this point we are either at the state
184     // of:
185     // - We are exiting a function that we recently entered.
186     // - We are exiting a function that was the result of a sequence of tail
187     //   exits, and we can check whether the tail exits can be re-wound.
188     //
189     FunctionRecord F;
190     W.undoWrites(sizeof(FunctionRecord));
191     if (B.Generation != BQ->generation())
192       return false;
193     internal_memcpy(&F, W.getNextRecord(), sizeof(FunctionRecord));
194 
195     DCHECK(F.RecordKind ==
196                uint8_t(FunctionRecord::RecordKinds::FunctionEnter) &&
197            "Expected to find function entry recording when rewinding.");
198     DCHECK_EQ(F.FuncId, FuncId & ~(0x0F << 28));
199 
200     LatestTSC -= F.TSCDelta;
201     if (--UndoableFunctionEnters != 0) {
202       LastFunctionEntryTSC -= F.TSCDelta;
203       return true;
204     }
205 
206     LastFunctionEntryTSC = 0;
207     auto RewindingTSC = LatestTSC;
208     auto RewindingRecordPtr = W.getNextRecord() - sizeof(FunctionRecord);
209     while (UndoableTailExits) {
210       if (B.Generation != BQ->generation())
211         return false;
212       internal_memcpy(&F, RewindingRecordPtr, sizeof(FunctionRecord));
213       DCHECK_EQ(F.RecordKind,
214                 uint8_t(FunctionRecord::RecordKinds::FunctionTailExit));
215       RewindingTSC -= F.TSCDelta;
216       RewindingRecordPtr -= sizeof(FunctionRecord);
217       if (B.Generation != BQ->generation())
218         return false;
219       internal_memcpy(&F, RewindingRecordPtr, sizeof(FunctionRecord));
220 
221       // This tail call exceeded the threshold duration. It will not be erased.
222       if ((TSC - RewindingTSC) >= CycleThreshold) {
223         UndoableTailExits = 0;
224         return true;
225       }
226 
227       --UndoableTailExits;
228       W.undoWrites(sizeof(FunctionRecord) * 2);
229       LatestTSC = RewindingTSC;
230     }
231     return true;
232   }
233 
234 public:
235   template <class WallClockFunc>
FDRController(BufferQueue * BQ,BufferQueue::Buffer & B,FDRLogWriter & W,WallClockFunc R,uint64_t C)236   FDRController(BufferQueue *BQ, BufferQueue::Buffer &B, FDRLogWriter &W,
237                 WallClockFunc R, uint64_t C) XRAY_NEVER_INSTRUMENT
238       : BQ(BQ),
239         B(B),
240         W(W),
241         WallClockReader(R),
242         CycleThreshold(C) {}
243 
functionEnter(int32_t FuncId,uint64_t TSC,uint16_t CPU)244   bool functionEnter(int32_t FuncId, uint64_t TSC,
245                      uint16_t CPU) XRAY_NEVER_INSTRUMENT {
246     if (finalized() ||
247         !prepareBuffer(sizeof(MetadataRecord) + sizeof(FunctionRecord)))
248       return returnBuffer();
249 
250     auto PreambleStatus = recordPreamble(TSC, CPU);
251     if (PreambleStatus == PreambleResult::InvalidBuffer)
252       return returnBuffer();
253 
254     if (PreambleStatus == PreambleResult::WroteMetadata) {
255       UndoableFunctionEnters = 1;
256       UndoableTailExits = 0;
257     } else {
258       ++UndoableFunctionEnters;
259     }
260 
261     auto Delta = TSC - LatestTSC;
262     LastFunctionEntryTSC = TSC;
263     LatestTSC = TSC;
264     return W.writeFunction(FDRLogWriter::FunctionRecordKind::Enter,
265                            mask(FuncId), Delta);
266   }
267 
functionTailExit(int32_t FuncId,uint64_t TSC,uint16_t CPU)268   bool functionTailExit(int32_t FuncId, uint64_t TSC,
269                         uint16_t CPU) XRAY_NEVER_INSTRUMENT {
270     if (finalized())
271       return returnBuffer();
272 
273     if (!prepareBuffer(sizeof(MetadataRecord) + sizeof(FunctionRecord)))
274       return returnBuffer();
275 
276     auto PreambleStatus = recordPreamble(TSC, CPU);
277     if (PreambleStatus == PreambleResult::InvalidBuffer)
278       return returnBuffer();
279 
280     if (PreambleStatus == PreambleResult::NoChange &&
281         UndoableFunctionEnters != 0 &&
282         TSC - LastFunctionEntryTSC < CycleThreshold)
283       return rewindRecords(FuncId, TSC, CPU);
284 
285     UndoableTailExits = UndoableFunctionEnters ? UndoableTailExits + 1 : 0;
286     UndoableFunctionEnters = 0;
287     auto Delta = TSC - LatestTSC;
288     LatestTSC = TSC;
289     return W.writeFunction(FDRLogWriter::FunctionRecordKind::TailExit,
290                            mask(FuncId), Delta);
291   }
292 
functionEnterArg(int32_t FuncId,uint64_t TSC,uint16_t CPU,uint64_t Arg)293   bool functionEnterArg(int32_t FuncId, uint64_t TSC, uint16_t CPU,
294                         uint64_t Arg) XRAY_NEVER_INSTRUMENT {
295     if (finalized() ||
296         !prepareBuffer((2 * sizeof(MetadataRecord)) + sizeof(FunctionRecord)) ||
297         recordPreamble(TSC, CPU) == PreambleResult::InvalidBuffer)
298       return returnBuffer();
299 
300     auto Delta = TSC - LatestTSC;
301     LatestTSC = TSC;
302     LastFunctionEntryTSC = 0;
303     UndoableFunctionEnters = 0;
304     UndoableTailExits = 0;
305 
306     return W.writeFunctionWithArg(FDRLogWriter::FunctionRecordKind::EnterArg,
307                                   mask(FuncId), Delta, Arg);
308   }
309 
functionExit(int32_t FuncId,uint64_t TSC,uint16_t CPU)310   bool functionExit(int32_t FuncId, uint64_t TSC,
311                     uint16_t CPU) XRAY_NEVER_INSTRUMENT {
312     if (finalized() ||
313         !prepareBuffer(sizeof(MetadataRecord) + sizeof(FunctionRecord)))
314       return returnBuffer();
315 
316     auto PreambleStatus = recordPreamble(TSC, CPU);
317     if (PreambleStatus == PreambleResult::InvalidBuffer)
318       return returnBuffer();
319 
320     if (PreambleStatus == PreambleResult::NoChange &&
321         UndoableFunctionEnters != 0 &&
322         TSC - LastFunctionEntryTSC < CycleThreshold)
323       return rewindRecords(FuncId, TSC, CPU);
324 
325     auto Delta = TSC - LatestTSC;
326     LatestTSC = TSC;
327     UndoableFunctionEnters = 0;
328     UndoableTailExits = 0;
329     return W.writeFunction(FDRLogWriter::FunctionRecordKind::Exit, mask(FuncId),
330                            Delta);
331   }
332 
customEvent(uint64_t TSC,uint16_t CPU,const void * Event,int32_t EventSize)333   bool customEvent(uint64_t TSC, uint16_t CPU, const void *Event,
334                    int32_t EventSize) XRAY_NEVER_INSTRUMENT {
335     if (finalized() ||
336         !prepareBuffer((2 * sizeof(MetadataRecord)) + EventSize) ||
337         recordPreamble(TSC, CPU) == PreambleResult::InvalidBuffer)
338       return returnBuffer();
339 
340     auto Delta = TSC - LatestTSC;
341     LatestTSC = TSC;
342     UndoableFunctionEnters = 0;
343     UndoableTailExits = 0;
344     return W.writeCustomEvent(Delta, Event, EventSize);
345   }
346 
typedEvent(uint64_t TSC,uint16_t CPU,uint16_t EventType,const void * Event,int32_t EventSize)347   bool typedEvent(uint64_t TSC, uint16_t CPU, uint16_t EventType,
348                   const void *Event, int32_t EventSize) XRAY_NEVER_INSTRUMENT {
349     if (finalized() ||
350         !prepareBuffer((2 * sizeof(MetadataRecord)) + EventSize) ||
351         recordPreamble(TSC, CPU) == PreambleResult::InvalidBuffer)
352       return returnBuffer();
353 
354     auto Delta = TSC - LatestTSC;
355     LatestTSC = TSC;
356     UndoableFunctionEnters = 0;
357     UndoableTailExits = 0;
358     return W.writeTypedEvent(Delta, EventType, Event, EventSize);
359   }
360 
flush()361   bool flush() XRAY_NEVER_INSTRUMENT {
362     if (finalized()) {
363       returnBuffer(); // ignore result.
364       return true;
365     }
366     return returnBuffer();
367   }
368 };
369 
370 } // namespace __xray
371 
372 #endif // COMPILER-RT_LIB_XRAY_XRAY_FDR_CONTROLLER_H_
373