1//===- IndexedMemProfData.h - MemProf format support ------------*- 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// MemProf data is serialized in writeMemProf provided in this file.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/ProfileData/DataAccessProf.h"
14#include "llvm/ProfileData/InstrProf.h"
15#include "llvm/ProfileData/InstrProfReader.h"
16#include "llvm/ProfileData/MemProf.h"
17#include "llvm/ProfileData/MemProfRadixTree.h"
18#include "llvm/ProfileData/MemProfSummary.h"
19#include "llvm/Support/FormatVariadic.h"
20#include "llvm/Support/OnDiskHashTable.h"
21
22namespace llvm {
23
24// Serialize Schema.
25static void writeMemProfSchema(ProfOStream &OS,
26 const memprof::MemProfSchema &Schema) {
27 OS.write(V: static_cast<uint64_t>(Schema.size()));
28 for (const auto Id : Schema)
29 OS.write(V: static_cast<uint64_t>(Id));
30}
31
32// Serialize MemProfRecordData. Return RecordTableOffset.
33static uint64_t writeMemProfRecords(
34 ProfOStream &OS,
35 llvm::MapVector<GlobalValue::GUID, memprof::IndexedMemProfRecord>
36 &MemProfRecordData,
37 memprof::MemProfSchema *Schema, memprof::IndexedVersion Version,
38 llvm::DenseMap<memprof::CallStackId, memprof::LinearCallStackId>
39 *MemProfCallStackIndexes = nullptr) {
40 memprof::RecordWriterTrait RecordWriter(Schema, Version,
41 MemProfCallStackIndexes);
42 OnDiskChainedHashTableGenerator<memprof::RecordWriterTrait>
43 RecordTableGenerator;
44 for (auto &[GUID, Record] : MemProfRecordData) {
45 // Insert the key (func hash) and value (memprof record).
46 RecordTableGenerator.insert(Key: GUID, Data&: Record, InfoObj&: RecordWriter);
47 }
48 // Release the memory of this MapVector as it is no longer needed.
49 MemProfRecordData.clear();
50
51 // The call to Emit invokes RecordWriterTrait::EmitData which destructs
52 // the memprof record copies owned by the RecordTableGenerator. This works
53 // because the RecordTableGenerator is not used after this point.
54 return RecordTableGenerator.Emit(Out&: OS.OS, InfoObj&: RecordWriter);
55}
56
57// Serialize MemProfFrameData. Return the mapping from FrameIds to their
58// indexes within the frame array.
59static llvm::DenseMap<memprof::FrameId, memprof::LinearFrameId>
60writeMemProfFrameArray(
61 ProfOStream &OS,
62 llvm::MapVector<memprof::FrameId, memprof::Frame> &MemProfFrameData,
63 llvm::DenseMap<memprof::FrameId, memprof::FrameStat> &FrameHistogram) {
64 // Mappings from FrameIds to array indexes.
65 llvm::DenseMap<memprof::FrameId, memprof::LinearFrameId> MemProfFrameIndexes;
66
67 // Compute the order in which we serialize Frames. The order does not matter
68 // in terms of correctness, but we still compute it for deserialization
69 // performance. Specifically, if we serialize frequently used Frames one
70 // after another, we have better cache utilization. For two Frames that
71 // appear equally frequently, we break a tie by serializing the one that tends
72 // to appear earlier in call stacks. We implement the tie-breaking mechanism
73 // by computing the sum of indexes within call stacks for each Frame. If we
74 // still have a tie, then we just resort to compare two FrameIds, which is
75 // just for stability of output.
76 std::vector<std::pair<memprof::FrameId, const memprof::Frame *>> FrameIdOrder;
77 FrameIdOrder.reserve(n: MemProfFrameData.size());
78 for (const auto &[Id, Frame] : MemProfFrameData)
79 FrameIdOrder.emplace_back(args: Id, args: &Frame);
80 assert(MemProfFrameData.size() == FrameIdOrder.size());
81 llvm::sort(C&: FrameIdOrder,
82 Comp: [&](const std::pair<memprof::FrameId, const memprof::Frame *> &L,
83 const std::pair<memprof::FrameId, const memprof::Frame *> &R) {
84 const auto &SL = FrameHistogram[L.first];
85 const auto &SR = FrameHistogram[R.first];
86 // Popular FrameIds should come first.
87 if (SL.Count != SR.Count)
88 return SL.Count > SR.Count;
89 // If they are equally popular, then the one that tends to appear
90 // earlier in call stacks should come first.
91 if (SL.PositionSum != SR.PositionSum)
92 return SL.PositionSum < SR.PositionSum;
93 // Compare their FrameIds for sort stability.
94 return L.first < R.first;
95 });
96
97 // Serialize all frames while creating mappings from linear IDs to FrameIds.
98 uint64_t Index = 0;
99 MemProfFrameIndexes.reserve(NumEntries: FrameIdOrder.size());
100 for (const auto &[Id, F] : FrameIdOrder) {
101 F->serialize(OS&: OS.OS);
102 MemProfFrameIndexes.insert(KV: {Id, Index});
103 ++Index;
104 }
105 assert(MemProfFrameData.size() == Index);
106 assert(MemProfFrameData.size() == MemProfFrameIndexes.size());
107
108 // Release the memory of this MapVector as it is no longer needed.
109 MemProfFrameData.clear();
110
111 return MemProfFrameIndexes;
112}
113
114static llvm::DenseMap<memprof::CallStackId, memprof::LinearCallStackId>
115writeMemProfCallStackArray(
116 ProfOStream &OS,
117 llvm::MapVector<memprof::CallStackId, llvm::SmallVector<memprof::FrameId>>
118 &MemProfCallStackData,
119 llvm::DenseMap<memprof::FrameId, memprof::LinearFrameId>
120 &MemProfFrameIndexes,
121 llvm::DenseMap<memprof::FrameId, memprof::FrameStat> &FrameHistogram,
122 unsigned &NumElements) {
123 llvm::DenseMap<memprof::CallStackId, memprof::LinearCallStackId>
124 MemProfCallStackIndexes;
125
126 memprof::CallStackRadixTreeBuilder<memprof::FrameId> Builder;
127 Builder.build(MemProfCallStackData: std::move(MemProfCallStackData), MemProfFrameIndexes: &MemProfFrameIndexes,
128 FrameHistogram);
129 for (auto I : Builder.getRadixArray())
130 OS.write32(V: I);
131 NumElements = Builder.getRadixArray().size();
132 MemProfCallStackIndexes = Builder.takeCallStackPos();
133
134 // Release the memory of this vector as it is no longer needed.
135 MemProfCallStackData.clear();
136
137 return MemProfCallStackIndexes;
138}
139
140static Error writeMemProfRadixTreeBased(
141 ProfOStream &OS, memprof::IndexedMemProfData &MemProfData,
142 memprof::IndexedVersion Version, bool MemProfFullSchema,
143 std::unique_ptr<memprof::DataAccessProfData> DataAccessProfileData =
144 nullptr,
145 std::unique_ptr<memprof::MemProfSummary> MemProfSum = nullptr) {
146 assert((Version == memprof::Version3 || Version == memprof::Version4) &&
147 "Unsupported version for radix tree format");
148
149 OS.write(V: Version); // Write the specific version (V3 or V4)
150 uint64_t HeaderUpdatePos = OS.tell();
151 OS.write(V: 0ULL); // Reserve space for the memprof call stack payload offset.
152 OS.write(V: 0ULL); // Reserve space for the memprof record payload offset.
153 OS.write(V: 0ULL); // Reserve space for the memprof record table offset.
154 if (Version >= memprof::Version4) {
155 OS.write(V: 0ULL); // Reserve space for the data access profile offset.
156
157 MemProfSum->write(OS);
158 }
159
160 auto Schema = memprof::getHotColdSchema();
161 if (MemProfFullSchema)
162 Schema = memprof::getFullSchema();
163 writeMemProfSchema(OS, Schema);
164
165 llvm::DenseMap<memprof::FrameId, memprof::FrameStat> FrameHistogram =
166 memprof::computeFrameHistogram(MemProfCallStackData&: MemProfData.CallStacks);
167 assert(MemProfData.Frames.size() == FrameHistogram.size());
168
169 llvm::DenseMap<memprof::FrameId, memprof::LinearFrameId> MemProfFrameIndexes =
170 writeMemProfFrameArray(OS, MemProfFrameData&: MemProfData.Frames, FrameHistogram);
171
172 uint64_t CallStackPayloadOffset = OS.tell();
173 // The number of elements in the call stack array.
174 unsigned NumElements = 0;
175 llvm::DenseMap<memprof::CallStackId, memprof::LinearCallStackId>
176 MemProfCallStackIndexes =
177 writeMemProfCallStackArray(OS, MemProfCallStackData&: MemProfData.CallStacks,
178 MemProfFrameIndexes, FrameHistogram,
179 NumElements);
180
181 uint64_t RecordPayloadOffset = OS.tell();
182 uint64_t RecordTableOffset = writeMemProfRecords(
183 OS, MemProfRecordData&: MemProfData.Records, Schema: &Schema, Version, MemProfCallStackIndexes: &MemProfCallStackIndexes);
184
185 uint64_t DataAccessProfOffset = 0;
186 if (DataAccessProfileData != nullptr) {
187 assert(Version >= memprof::Version4 &&
188 "Data access profiles are added starting from v4");
189 DataAccessProfOffset = OS.tell();
190 if (Error E = DataAccessProfileData->serialize(OS))
191 return E;
192 }
193
194 // Verify that the computation for the number of elements in the call stack
195 // array works.
196 assert(CallStackPayloadOffset +
197 NumElements * sizeof(memprof::LinearFrameId) ==
198 RecordPayloadOffset);
199
200 SmallVector<uint64_t, 4> Header = {
201 CallStackPayloadOffset,
202 RecordPayloadOffset,
203 RecordTableOffset,
204 };
205 if (Version >= memprof::Version4)
206 Header.push_back(Elt: DataAccessProfOffset);
207
208 OS.patch(P: {{.Pos: HeaderUpdatePos, .D: Header}});
209
210 return Error::success();
211}
212
213// Write out MemProf Version3
214static Error writeMemProfV3(ProfOStream &OS,
215 memprof::IndexedMemProfData &MemProfData,
216 bool MemProfFullSchema) {
217 return writeMemProfRadixTreeBased(OS, MemProfData, Version: memprof::Version3,
218 MemProfFullSchema);
219}
220
221// Write out MemProf Version4
222static Error writeMemProfV4(
223 ProfOStream &OS, memprof::IndexedMemProfData &MemProfData,
224 bool MemProfFullSchema,
225 std::unique_ptr<memprof::DataAccessProfData> DataAccessProfileData,
226 std::unique_ptr<memprof::MemProfSummary> MemProfSum) {
227 return writeMemProfRadixTreeBased(
228 OS, MemProfData, Version: memprof::Version4, MemProfFullSchema,
229 DataAccessProfileData: std::move(DataAccessProfileData), MemProfSum: std::move(MemProfSum));
230}
231
232// Write out the MemProf data in a requested version.
233Error writeMemProf(
234 ProfOStream &OS, memprof::IndexedMemProfData &MemProfData,
235 memprof::IndexedVersion MemProfVersionRequested, bool MemProfFullSchema,
236 std::unique_ptr<memprof::DataAccessProfData> DataAccessProfileData,
237 std::unique_ptr<memprof::MemProfSummary> MemProfSum) {
238 switch (MemProfVersionRequested) {
239 case memprof::Version3:
240 return writeMemProfV3(OS, MemProfData, MemProfFullSchema);
241 case memprof::Version4:
242 return writeMemProfV4(OS, MemProfData, MemProfFullSchema,
243 DataAccessProfileData: std::move(DataAccessProfileData),
244 MemProfSum: std::move(MemProfSum));
245 }
246
247 return make_error<InstrProfError>(
248 Args: instrprof_error::unsupported_version,
249 Args: formatv(Fmt: "MemProf version {} not supported; "
250 "requires version between {} and {}, inclusive",
251 Vals&: MemProfVersionRequested, Vals: memprof::MinimumSupportedVersion,
252 Vals: memprof::MaximumSupportedVersion));
253}
254
255Error IndexedMemProfReader::deserializeRadixTreeBased(
256 const unsigned char *Start, const unsigned char *Ptr,
257 memprof::IndexedVersion Version) {
258 assert((Version == memprof::Version3 || Version == memprof::Version4) &&
259 "Unsupported version for radix tree format");
260 // The offset in the stream right before invoking
261 // CallStackTableGenerator.Emit.
262 const uint64_t CallStackPayloadOffset =
263 support::endian::readNext<uint64_t, llvm::endianness::little>(memory&: Ptr);
264 // The offset in the stream right before invoking RecordTableGenerator.Emit.
265 const uint64_t RecordPayloadOffset =
266 support::endian::readNext<uint64_t, llvm::endianness::little>(memory&: Ptr);
267 // The value returned from RecordTableGenerator.Emit.
268 const uint64_t RecordTableOffset =
269 support::endian::readNext<uint64_t, llvm::endianness::little>(memory&: Ptr);
270
271 uint64_t DataAccessProfOffset = 0;
272 if (Version >= memprof::Version4) {
273 DataAccessProfOffset =
274 support::endian::readNext<uint64_t, llvm::endianness::little>(memory&: Ptr);
275 MemProfSum = memprof::MemProfSummary::deserialize(Ptr);
276
277 if (DataAccessProfOffset > RecordTableOffset) {
278 DataAccessProfileData = std::make_unique<memprof::DataAccessProfData>();
279 const unsigned char *DAPPtr = Start + DataAccessProfOffset;
280 if (Error E = DataAccessProfileData->deserialize(Ptr&: DAPPtr))
281 return E;
282 MemProfSum->buildDataAccessSummary(DataAccessProfile: *DataAccessProfileData);
283 }
284 }
285
286 assert((!DataAccessProfOffset || DataAccessProfOffset > RecordTableOffset) &&
287 "Data access profile is either empty or after the record table");
288
289 // Read the schema.
290 auto SchemaOr = memprof::readMemProfSchema(Buffer&: Ptr);
291 if (!SchemaOr)
292 return SchemaOr.takeError();
293 Schema = SchemaOr.get();
294
295 FrameBase = Ptr;
296 CallStackBase = Start + CallStackPayloadOffset;
297
298 // Compute the number of elements in the radix tree array. Since we use this
299 // to reserve enough bits in a BitVector, it's totally OK if we overestimate
300 // this number a little bit because of padding just before the next section.
301 RadixTreeSize = (RecordPayloadOffset - CallStackPayloadOffset) /
302 sizeof(memprof::LinearFrameId);
303
304 // Now initialize the table reader with a pointer into data buffer.
305 MemProfRecordTable.reset(p: MemProfRecordHashTable::Create(
306 /*Buckets=*/Start + RecordTableOffset,
307 /*Payload=*/Start + RecordPayloadOffset,
308 /*Base=*/Start, InfoObj: memprof::RecordLookupTrait(Version, Schema)));
309
310 return Error::success();
311}
312
313Error IndexedMemProfReader::deserialize(const unsigned char *Start,
314 uint64_t MemProfOffset) {
315 const unsigned char *Ptr = Start + MemProfOffset;
316
317 // Read the MemProf version number.
318 const uint64_t FirstWord =
319 support::endian::readNext<uint64_t, llvm::endianness::little>(memory&: Ptr);
320
321 // Check if the version is supported
322 if (FirstWord >= memprof::MinimumSupportedVersion &&
323 FirstWord <= memprof::MaximumSupportedVersion) {
324 // Everything is good. We can proceed to deserialize the rest.
325 Version = static_cast<memprof::IndexedVersion>(FirstWord);
326 } else {
327 return make_error<InstrProfError>(
328 Args: instrprof_error::unsupported_version,
329 Args: formatv(Fmt: "MemProf version {} not supported; "
330 "requires version between {} and {}, inclusive",
331 Vals: FirstWord, Vals: memprof::MinimumSupportedVersion,
332 Vals: memprof::MaximumSupportedVersion));
333 }
334
335 switch (Version) {
336 case memprof::Version3:
337 case memprof::Version4:
338 // V3 and V4 share the same high-level structure (radix tree, linear IDs).
339 if (Error E = deserializeRadixTreeBased(Start, Ptr, Version))
340 return E;
341 break;
342 }
343
344 return Error::success();
345}
346} // namespace llvm
347