Snehasish Kumar via llvm-dev
2021-Sep-29 22:17 UTC
[llvm-dev] RFC: A binary serialization format for MemProf
This RFC contains the following:
* Proposal to introduce a new raw binary serialization format for heap
allocation profiles
* Proposal to extend the PGO indexed format to hold heap allocation profiles
We look forward to your feedback on the proposals.
Authors: snehasishk at google.com, davidxl at google.com, tejohnson at
google.com
Introduction
—-----------
The design of a sanitizer-based heap profiler (MemProf) was shared with
llvm-dev in Jun 2020 [1]. Since then Teresa (@tejohnson) has added a
sanitizer based heap profiler which can be enabled with -fmemory-profile.
Today it writes out the data in a text format which can be inspected by
users. We have used this to drive analyses of heap behaviour at Google.
This RFC shares details on a binary serialization format for heap profiling
data which can then be reused by the compiler to guide optimizations
similar to traditional PGO.
Similar to the existing instrumentation based PGO, the binary heap profile
data for PGHO has two forms. One is the raw data format that is used by the
profiler runtime, and the other is the indexed profile format used by the
compiler. The profile data with the indexed profile data format will be
generated by llvm-profdata from the raw profile data offline. This allows a
single binary profile file to hold the PGO and Memprof profiling data. Fig
1 below shows the binary format generation and use.
┌──────────────────┐ Raw Profile ┌───────────────┐ Indexed Profile
(v8)
│ Compiler Runtime ├─────────────► llvm-profdata ├───► with Memprof data
───► -fprofile-use
└──────────────────┘ └───────────────┘
Fig 1: Memprof binary profile lifecycle
Raw Binary Format
—----------------
The raw binary format contains 4 sections
1. Memprof raw profile header
2. Memory mapping layout
3. Memory Info Block (MIB) records
4. Call stack information
+----------------------+
| Magic |
+----------------------+ H
| Version | E
+----------------------+ A
| Total Size | D
+----------------------+ E
+---------| Map Offset | R
| +----------------------+
| +-----| MIB Offset |
| | +----------------------+
| | | Call Stack Offset |---------+
| | +----------------------+ |
+-------->| Number of | M |
| | Map Entries | A |
| +----------------------+ P |
| | | |
| | Map Entry | S |
| +----------------------+ E |
| | ... | C |
| +----------------------+ T |
| | | I |
| | Map Entry | O |
| +----------------------+ N |
| |
| |
| +----------------------+ |
+---->| Number of | M |
| MIB Entries | I |
+----------------------+ B |
| | |
| MIB Entry | S |
+----------------------+ E |
| ... | C |
+----------------------+ T |
| | I |
| MIB Entry | O |
+----------------------+ N |
|
+----------------------+ |
| Number of |<--------+
| Call Stack Entries | S S
+----------------------+ T E
| Call Stack Entry | A C
+----------------------+ C T
| ... | K I
+----------------------+ O
| Call Stack Entry | N
+----------------------+
Fig 2: Memprof Raw Format
* Memprof raw profile header
The header consists of a unique identifier, version number, total size of
the profile as well as offset into the profile for each of the following
sections - memory mapping layout, memprof profile entries and call stack
information. We do not intend to maintain backwards compatibility for the
raw binary format.
* Memory mapping layout
The process memory mappings for the executable segment during profiling are
stored in this section. This allows symbolization during post processing
for binaries which are built with position independent code. For now all
read only, executable mappings are recorded, however in the future,
mappings for heap data can also potentially be stored. For each mapping, we
record
-
Start (virtual address)
-
End (virtual address)
-
Offset (from the file it was mmap-ed from)
-
buildId (linker generated hash -Wl,build-id
* MIB Records
The profile information we collect is currently defined in [2]. The section
begins with a 8 byte entry containing the number of profile entries in this
section. Each entry is uniquely identified by the dynamic calling context
of the allocation site. For each entry, various metrics such as access
counts, allocation sizes, object lifetimes etc are computed via profiling.
This section may contain multiple entries identified by the same callstack
id. Subsequent processing to convert and merge multiple raw profiles will
deduplicate any such entries.
* Call stack information
Each memprof profile entry is uniquely identified by its dynamic calling
context. In this section we record the identifier and its corresponding
call stack trace. We use the sanitizer stack depot provided identifier and
serialize the trace for each without deduplication. The section begins with
a 8b entry containing the number of call stack entries. Each call stack
entry contains a 8b field which denotes how many contexts are recorded in
this entry. Each frame is identified by an 8b program counter address which
holds the call instruction virtual address - 1. Further deduplication is
possible though we do not do so at this time.
* Raw Profile Characteristics
To understand the characteristics of raw binary profiles generated by
Memprof, we experimented with a clang bootstrap build. We ran 500
invocations of Memprof-instrumented clang on clang source code. Each
invocation produced a raw binary profile and we present some aggregate
information about them below:
+---------------------------------+--------+---------+---------+
| | Min | Median | Max |
+---------------------------------+--------+---------+---------+
| Unique allocation contexts | 940 | 10661 | 35355 |
+---------------------------------+--------+---------+---------+
| MIB records size (bytes) | 101528 | 1151396 | 3818348 |
+---------------------------------+--------+---------+---------+
| Call stack section size (bytes) | 31080 | 419048 | 1439144 |
+---------------------------------+--------+---------+---------+
| Total Size (bytes) | 133336 | 1571680 | 5258220 |
+---------------------------------+--------+---------+---------+
The size of the header is 48 bytes and the number of read only executable
memory maps is usually small (12 in this case) with each map entry
consuming 64 bytes. We find that the raw profiles are highly compressible,
on average files are compressed by 81%. The largest raw profile in the
dataset is ~5M in size. It is compressed to 975K using zip on default
settings. In contrast for the same clang build, the instrumented PGO raw
profile is ~21M in size (zip compressed 73%). Note that the Memprof profile
size is proportional to the number of allocation contexts during
profiling.
Since these are profiles from individual invocations, they must be merged
before use. This is performed implicitly during the conversion to indexed
profile format by llvm-profdata. MIBs are merged based on their call stack.
Memprof extensions for the indexed profile format
—------------------------------------------------
+----------------+
| MAGIC |
+----------------+
| VERSION |
+----------------+
| HASHTYPE |
+--+----------+--+
|HASHTAB OFFSET |-------+
+--+----------+--+ |
+----------------+ |
| | |
| PROFILE | |
| SUMMARY | |
| DATA | |
+----------------+ |
+----------------+ <----+
| |
| OnDisk |
| Chained |
| HashTable |
| |
+----------------+
Fig 3: Existing PGO indexed profile format
During the offline processing step (using llvm-profdata), allocation
contexts are pruned and merged. The end result is a collection of unique
allocation contexts with access, size and lifetime properties. Contexts are
uniquely identified based on the call stack and are stored using a prefix
deduplication scheme described in Section “Symbolized Memprof call stack
section”.
To fit into the PGO profile format, we need to index the profile using the
function name. The only functions that own Memprof profile data are those
direct callers of the allocator primitive functions. Thus the profile data
mapping in the IR must account for potentially missing frames. Implications
on matching of the profile data with the IR is touched upon in Section
“Profile Data matching in IR” and will be further detailed in an upcoming
RFC.
The Memprof profile data for a particular function can then be just an
array of MIB entries. One allocation site in the function can have multiple
MIB entries each one of them corresponding to one allocation context.
The change to the existing PGO indexed format is summarized as:
-
Augment the profile record data structure to include an optional MIB
array after the value profile data [3].
-
Add one additional section before the existing OnDiskChainedHashtable to
store the allocation stacks (referenced by the MIBs). This section is after
the profile summary data section [4].
-
Bump the version number.
Memprof portable entry format
—----------------------------
The raw memprof profile entry format is subject to change with version.
However, the indexed profile entry must be backwards compatible to ensure
that the PGO profile as a whole is backwards compatible. We propose a
schema based format - per function description of a Memprof profile entry.
Each field is identified by a tag. We propose the following schema:
struct MIBMeta {
enum MIBFieldTag {
// The tag ids remain unchanged.
Unused = 0,
StackID = 1,
AllocCount = 2,
AveSize = 3,
MinSize = 4,
MaxSize = 5,
AveAccessCount = 6,
MinAccessCount = 7,
MaxAccessCount = 8,
AveLifetime = 9,
MinLifetime = 10,
MaxLifetime = 11,
NumMigration = 12,
NumLifetimeOverlaps = 13,
NumSameAllocCPU = 14,
NumSameDeallocCPU = 15
};
enum MIBFieldType {
Unused = 0,
UINT8 = 1,
UINT16 = 2,
UINT32 = 3, // Varint encoded
UINT64 = 4, // Varint encoded
};
};
// Mapping of tags to their descriptive names
const char *MIBFieldName[] = {
"",
"StackID",
"AllocCount",
…
"NumSameDeallocCPU"
};
// Mapping of tags to their types
uint8 MIBFieldType [] = {
0, // unused
MIBMeta::MIBFieldType::UINT64,
….
};
To make the field tag, field name, and field type declarations always in
sync, a shared .inc file will be used. This file will be shared between
compiler-rt and llvm/lib/ProfileData libraries. Dependencies across the
compiler-rt project are not recommended for isolation.
// MIBDef.inc file
// define MIBEntryDef(tag, name, type) before inclusion
MIBEntryDef(StackID = 1, "StackID",
MIBMeta::MIBFieldType::UINT64)
MIBEntryDef(AllocCount = 2, "AllocCount",
MIBMeta::MIBFieldType::UINT32)
...
MIBEntryDef(NumSameDeallocCPU=13,"NumSameDeallocCPU",
MIBMeta::MIBFieldType:UINT8)
enum MIBFieldTag {
StartTag = 0,
#define MIBEntryDef(tag, name, type) tag
#include "MIBDef.inc"
#undef MIBEntryDef
};
const char *MIBFieldName {
#define MIBEntryDef(tag, name, type) name
"",
#include "MIBEntryDef.inc"
#undef MIBEntryDef
};
uint8 MIBFieldType {
#define MIBEntryDef(tag, name, type) type
0, // not used
#include "MIBEntryDef.inc"
#undef MIBDefEntry
};
The InstrProfRecord for each function will hold the schema and an array of
Memprof info blocks, one for each unique allocation context.
Symbolized Memprof call stack section
—------------------------------------
This section holds the symbolized version of the call stack section in the
raw profile. This is necessary to enable the compiler to map recorded
runtime PC addresses to source locations during recompilation. For space
efficiency, this section is split into three subsections: 1. stack entry
table 2. file path table 3. string table.
Fig 4 shows the relationship between the three tables.
STACK ENTRY FILE PATH STRING
TABLE TABLE TABLE
┌────────┐ ┌──┬──┬──┐ ┌─────────┐
│ │ │ │ │ │ │10 abc │
│ │ ├──┼──┼──┤ ├─────────┤
│ │ │ │ │ │◄┐ │11 def │
│ │ ├──┼──┼──┤ │ ├─────────┤
├──┬──┬──┤ │ │ │ │ │ │12 ghi │
┌───┤03│LN│DI│ ├──┼──┼──┤ │ ├─────────┤
│ ├──┴──┴──┤ ┌───►│03│13│01├─┘ ┌─►│13 XY.h │
│ └────────┘ │ └──┴─┬┴──┘ │ └─────────┘
│ │ │ │
└────────────────┘ └────────┘
Fig 4. The Stack Entry, File Path and String Table.
LN = Line Number, DI = Discriminator
* Stack Entry Table: Each uniquely identified symbolized call stack
consists of a variable number of callsites. In the indexed format, each
callsite needs to be represented as file:line:discriminator (as shown in
Fig 4). The call stack location is a 64-bit field, but it is split into
three subfields: file table index, line number, and the discriminator
value. The file table index is a pointer to a leaf node in the prefix
encoded scheme described below.
* File path table using prefix encoding: Full path filenames have lots of
common substrings due to the directory structure so they can be compressed.
One simple scheme is to use the reverse prefix tree representation. In this
representation, the name string of a directory at each level (not including
prefixes) is represented by a node, and it is linked to its parent node. To
summarize, the file path table is represented as an array of nodes
organized as a forest of reversed tree structures.
For instance, the strings
“abc/def/ghi/XY.c”,
“abc/def/ghi/XY.h”,
“abc/def/jkl/UV.c”
are represented as
+-----------+<------+
| abc | |
+----->+---->+-----------+ |
| | | def +-------+
| | +-----------+
| +-----+ ghi |<-------+----+
| +-----------+ | |
+-+--------->| jkl | | |
| +-----------+ | |
| | XY.c +--------+ |
| +-----------+ |
+----------+ UV.c | |
+-----------+ |
| XY.h +-------------+
+-----------+
Fig 5. Prefix tree representation of paths in the file path table
Each parent link implies a path separator ‘/’. Furthermore we represent
each file or directory string as an integer offset into the string table
(see Fig 4). Thus each node holds an offset into the string table and a
pointer to the parent (interior) directory node.
* String table: To remove redundancies across prefix tree nodes in the file
path encoding, we use a string table which stores the mapping of string to
a unique id. The id can be simplified as the implicit offset into the table.
Thus this representation exploits redundancy in the source file path prefix
where there are a large number of source files in a small number of deeply
nested directories.
Symbolizing the raw PC addresses in post-processing using llvm-profdata
requires the binary to also be provided as input. As an alternative, we
will also experiment with incrementally generating the symbolized call
stack section as part of the raw profile dump at the cost of increased
profiling overhead.
Profile Data matching in IR
—--------------------------
When matching the profile data, we may have already early inlined the
direct caller of the allocation into its caller(s). This means we need to
take some additional steps to identify the matching MIBs. For example,
consider the following partial call graph:
┌────────────────────┐ ┌────────────────────┐
A │ Call B; debug loc1 │ C │ Call B; debug loc2 │
└───────┬────────────┘ └───────────┬────────┘
│ │
│ │
│ ┌─────────────────────────┐ │
└────► Call malloc; debug loc3 ◄─────┘
B └─────────────────────────┘
There will be 2 MIB entries, one for each context (A->B and C->B). As
noted
earlier, the MIB profile entries will be owned by the function calling the
allocation function. Therefore, we will keep both MIB entries associated
with function B in the profile.
If early inlining (i.e. before profile matching) inlines B into A but not
into C it will look like the following when we try to match the profile:
┌────────────────────┐
┌────────────────────────┐ C │ Call B; debug loc2 │
A │Call malloc; debug loc3 │ └───────────┬────────┘
│ ; inlined at │ │
│ ; debug loc1 │ ┌──────────────┴───────────┐
└────────────────────────┘ B │ Call malloc; debug loc3 │
└──────────────────────────┘
Because the MIB corresponding to the A->B context is associated with
function B in the profile, we do not find it by looking at function A’s
profile when we see function A’s malloc call during matching. To address
this we need to keep a correspondence from debug locations to the
associated profile information. The details of the design will be shared in
a separate RFC in the future.
[1] https://lists.llvm.org/pipermail/llvm-dev/2020-June/142744.html
[2] https://git.io/JzdRa
[3] https://git.io/JzdRR
[4] https://git.io/JzdRN
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210929/497362fd/attachment-0001.html>
Xinliang David Li via llvm-dev
2021-Sep-30 00:46 UTC
[llvm-dev] RFC: A binary serialization format for MemProf
FYI you can also view the RFC here https://groups.google.com/g/llvm-dev/c/h1DvHguLpxU , which displays the diagrams better (without extra wide space). David On Wed, Sep 29, 2021 at 3:17 PM Snehasish Kumar <snehasishk at google.com> wrote:> This RFC contains the following: > > * Proposal to introduce a new raw binary serialization format for heap > allocation profiles > > * Proposal to extend the PGO indexed format to hold heap allocation > profiles > We look forward to your feedback on the proposals. > Authors: snehasishk at google.com, davidxl at google.com, tejohnson at google.com > > Introduction > > —----------- > > The design of a sanitizer-based heap profiler (MemProf) was shared with > llvm-dev in Jun 2020 [1]. Since then Teresa (@tejohnson) has added a > sanitizer based heap profiler which can be enabled with -fmemory-profile. > Today it writes out the data in a text format which can be inspected by > users. We have used this to drive analyses of heap behaviour at Google. > This RFC shares details on a binary serialization format for heap profiling > data which can then be reused by the compiler to guide optimizations > similar to traditional PGO. > > Similar to the existing instrumentation based PGO, the binary heap profile > data for PGHO has two forms. One is the raw data format that is used by the > profiler runtime, and the other is the indexed profile format used by the > compiler. The profile data with the indexed profile data format will be > generated by llvm-profdata from the raw profile data offline. This allows a > single binary profile file to hold the PGO and Memprof profiling data. Fig > 1 below shows the binary format generation and use. > > > ┌──────────────────┐ Raw Profile ┌───────────────┐ Indexed Profile > (v8) > > │ Compiler Runtime ├─────────────► llvm-profdata ├───► with Memprof data > ───► -fprofile-use > > └──────────────────┘ └───────────────┘ > > Fig 1: Memprof binary profile lifecycle > > Raw Binary Format > > —---------------- > > The raw binary format contains 4 sections > > 1. Memprof raw profile header > > 2. Memory mapping layout > > 3. Memory Info Block (MIB) records > > 4. Call stack information > > +----------------------+ > > | Magic | > > +----------------------+ H > > | Version | E > > +----------------------+ A > > | Total Size | D > > +----------------------+ E > > +---------| Map Offset | R > > | +----------------------+ > > | +-----| MIB Offset | > > | | +----------------------+ > > | | | Call Stack Offset |---------+ > > | | +----------------------+ | > > +-------->| Number of | M | > > | | Map Entries | A | > > | +----------------------+ P | > > | | | | > > | | Map Entry | S | > > | +----------------------+ E | > > | | ... | C | > > | +----------------------+ T | > > | | | I | > > | | Map Entry | O | > > | +----------------------+ N | > > | | > > | | > > | +----------------------+ | > > +---->| Number of | M | > > | MIB Entries | I | > > +----------------------+ B | > > | | | > > | MIB Entry | S | > > +----------------------+ E | > > | ... | C | > > +----------------------+ T | > > | | I | > > | MIB Entry | O | > > +----------------------+ N | > > | > > +----------------------+ | > > | Number of |<--------+ > > | Call Stack Entries | S S > > +----------------------+ T E > > | Call Stack Entry | A C > > +----------------------+ C T > > | ... | K I > > +----------------------+ O > > | Call Stack Entry | N > > +----------------------+ > > Fig 2: Memprof Raw Format > > > * Memprof raw profile header > > The header consists of a unique identifier, version number, total size of > the profile as well as offset into the profile for each of the following > sections - memory mapping layout, memprof profile entries and call stack > information. We do not intend to maintain backwards compatibility for the > raw binary format. > > * Memory mapping layout > > The process memory mappings for the executable segment during profiling > are stored in this section. This allows symbolization during post > processing for binaries which are built with position independent code. For > now all read only, executable mappings are recorded, however in the > future, mappings for heap data can also potentially be stored. For each > mapping, we record > > - > > Start (virtual address) > - > > End (virtual address) > - > > Offset (from the file it was mmap-ed from) > - > > buildId (linker generated hash -Wl,build-id > > > * MIB Records > > The profile information we collect is currently defined in [2]. The > section begins with a 8 byte entry containing the number of profile entries > in this section. Each entry is uniquely identified by the dynamic calling > context of the allocation site. For each entry, various metrics such as > access counts, allocation sizes, object lifetimes etc are computed via > profiling. This section may contain multiple entries identified by the same > callstack id. Subsequent processing to convert and merge multiple raw > profiles will deduplicate any such entries. > > * Call stack information > Each memprof profile entry is uniquely identified by its dynamic calling > context. In this section we record the identifier and its corresponding > call stack trace. We use the sanitizer stack depot provided identifier and > serialize the trace for each without deduplication. The section begins with > a 8b entry containing the number of call stack entries. Each call stack > entry contains a 8b field which denotes how many contexts are recorded in > this entry. Each frame is identified by an 8b program counter address which > holds the call instruction virtual address - 1. Further deduplication is > possible though we do not do so at this time. > > * Raw Profile Characteristics > > To understand the characteristics of raw binary profiles generated by > Memprof, we experimented with a clang bootstrap build. We ran 500 > invocations of Memprof-instrumented clang on clang source code. Each > invocation produced a raw binary profile and we present some aggregate > information about them below: > > +---------------------------------+--------+---------+---------+ > > | | Min | Median | Max | > > +---------------------------------+--------+---------+---------+ > > | Unique allocation contexts | 940 | 10661 | 35355 | > > +---------------------------------+--------+---------+---------+ > > | MIB records size (bytes) | 101528 | 1151396 | 3818348 | > > +---------------------------------+--------+---------+---------+ > > | Call stack section size (bytes) | 31080 | 419048 | 1439144 | > > +---------------------------------+--------+---------+---------+ > > | Total Size (bytes) | 133336 | 1571680 | 5258220 | > > +---------------------------------+--------+---------+---------+ > > The size of the header is 48 bytes and the number of read only executable > memory maps is usually small (12 in this case) with each map entry > consuming 64 bytes. We find that the raw profiles are highly compressible, > on average files are compressed by 81%. The largest raw profile in the > dataset is ~5M in size. It is compressed to 975K using zip on default > settings. In contrast for the same clang build, the instrumented PGO raw > profile is ~21M in size (zip compressed 73%). Note that the Memprof profile > size is proportional to the number of allocation contexts during > profiling. > > Since these are profiles from individual invocations, they must be merged > before use. This is performed implicitly during the conversion to indexed > profile format by llvm-profdata. MIBs are merged based on their call stack. > > Memprof extensions for the indexed profile format > > —------------------------------------------------ > > +----------------+ > > | MAGIC | > > +----------------+ > > | VERSION | > > +----------------+ > > | HASHTYPE | > > +--+----------+--+ > > |HASHTAB OFFSET |-------+ > > +--+----------+--+ | > > +----------------+ | > > | | | > > | PROFILE | | > > | SUMMARY | | > > | DATA | | > > +----------------+ | > > +----------------+ <----+ > > | | > > | OnDisk | > > | Chained | > > | HashTable | > > | | > > +----------------+ > > Fig 3: Existing PGO indexed profile format > > During the offline processing step (using llvm-profdata), allocation > contexts are pruned and merged. The end result is a collection of unique > allocation contexts with access, size and lifetime properties. Contexts are > uniquely identified based on the call stack and are stored using a prefix > deduplication scheme described in Section “Symbolized Memprof call stack > section”. > > To fit into the PGO profile format, we need to index the profile using the > function name. The only functions that own Memprof profile data are those > direct callers of the allocator primitive functions. Thus the profile data > mapping in the IR must account for potentially missing frames. Implications > on matching of the profile data with the IR is touched upon in Section > “Profile Data matching in IR” and will be further detailed in an upcoming > RFC. > > The Memprof profile data for a particular function can then be just an > array of MIB entries. One allocation site in the function can have multiple > MIB entries each one of them corresponding to one allocation context. > > The change to the existing PGO indexed format is summarized as: > > - > > Augment the profile record data structure to include an optional MIB > array after the value profile data [3]. > - > > Add one additional section before the existing OnDiskChainedHashtable > to store the allocation stacks (referenced by the MIBs). This section is > after the profile summary data section [4]. > - > > Bump the version number. > > > > Memprof portable entry format > > —---------------------------- > > The raw memprof profile entry format is subject to change with version. > However, the indexed profile entry must be backwards compatible to ensure > that the PGO profile as a whole is backwards compatible. We propose a > schema based format - per function description of a Memprof profile entry. > Each field is identified by a tag. We propose the following schema: > > struct MIBMeta { > > enum MIBFieldTag { > > // The tag ids remain unchanged. > > Unused = 0, > > StackID = 1, > > AllocCount = 2, > > AveSize = 3, > > MinSize = 4, > > MaxSize = 5, > > AveAccessCount = 6, > > MinAccessCount = 7, > > MaxAccessCount = 8, > > AveLifetime = 9, > > MinLifetime = 10, > > MaxLifetime = 11, > > NumMigration = 12, > > NumLifetimeOverlaps = 13, > > NumSameAllocCPU = 14, > > NumSameDeallocCPU = 15 > > }; > > enum MIBFieldType { > > Unused = 0, > > UINT8 = 1, > > UINT16 = 2, > > UINT32 = 3, // Varint encoded > > UINT64 = 4, // Varint encoded > > }; > > }; > > > // Mapping of tags to their descriptive names > > const char *MIBFieldName[] = { > > "", > > "StackID", > > "AllocCount", > > … > > "NumSameDeallocCPU" > > }; > > // Mapping of tags to their types > > uint8 MIBFieldType [] = { > > 0, // unused > > MIBMeta::MIBFieldType::UINT64, > > …. > > }; > > To make the field tag, field name, and field type declarations always in > sync, a shared .inc file will be used. This file will be shared between > compiler-rt and llvm/lib/ProfileData libraries. Dependencies across the > compiler-rt project are not recommended for isolation. > > // MIBDef.inc file > > // define MIBEntryDef(tag, name, type) before inclusion > > MIBEntryDef(StackID = 1, "StackID", > > MIBMeta::MIBFieldType::UINT64) > > MIBEntryDef(AllocCount = 2, "AllocCount", > > MIBMeta::MIBFieldType::UINT32) > > ... > > MIBEntryDef(NumSameDeallocCPU=13,"NumSameDeallocCPU", > > MIBMeta::MIBFieldType:UINT8) > > > enum MIBFieldTag { > > StartTag = 0, > > #define MIBEntryDef(tag, name, type) tag > > #include "MIBDef.inc" > > #undef MIBEntryDef > > }; > > const char *MIBFieldName { > > #define MIBEntryDef(tag, name, type) name > > "", > > #include "MIBEntryDef.inc" > > #undef MIBEntryDef > > }; > > uint8 MIBFieldType { > > #define MIBEntryDef(tag, name, type) type > > 0, // not used > > #include "MIBEntryDef.inc" > > #undef MIBDefEntry > > }; > > The InstrProfRecord for each function will hold the schema and an array of > Memprof info blocks, one for each unique allocation context. > > Symbolized Memprof call stack section > > —------------------------------------ > > This section holds the symbolized version of the call stack section in the > raw profile. This is necessary to enable the compiler to map recorded > runtime PC addresses to source locations during recompilation. For space > efficiency, this section is split into three subsections: 1. stack entry > table 2. file path table 3. string table. > > Fig 4 shows the relationship between the three tables. > > STACK ENTRY FILE PATH STRING > > TABLE TABLE TABLE > > ┌────────┐ ┌──┬──┬──┐ ┌─────────┐ > > │ │ │ │ │ │ │10 abc │ > > │ │ ├──┼──┼──┤ ├─────────┤ > > │ │ │ │ │ │◄┐ │11 def │ > > │ │ ├──┼──┼──┤ │ ├─────────┤ > > ├──┬──┬──┤ │ │ │ │ │ │12 ghi │ > > ┌───┤03│LN│DI│ ├──┼──┼──┤ │ ├─────────┤ > > │ ├──┴──┴──┤ ┌───►│03│13│01├─┘ ┌─►│13 XY.h │ > > │ └────────┘ │ └──┴─┬┴──┘ │ └─────────┘ > > │ │ │ │ > > └────────────────┘ └────────┘ > > Fig 4. The Stack Entry, File Path and String Table. > > LN = Line Number, DI = Discriminator > > * Stack Entry Table: Each uniquely identified symbolized call stack > consists of a variable number of callsites. In the indexed format, each > callsite needs to be represented as file:line:discriminator (as shown in > Fig 4). The call stack location is a 64-bit field, but it is split into > three subfields: file table index, line number, and the discriminator > value. The file table index is a pointer to a leaf node in the prefix > encoded scheme described below. > > * File path table using prefix encoding: Full path filenames have lots of > common substrings due to the directory structure so they can be compressed. > One simple scheme is to use the reverse prefix tree representation. In this > representation, the name string of a directory at each level (not including > prefixes) is represented by a node, and it is linked to its parent node. To > summarize, the file path table is represented as an array of nodes > organized as a forest of reversed tree structures. > > For instance, the strings > “abc/def/ghi/XY.c”, > “abc/def/ghi/XY.h”, > > “abc/def/jkl/UV.c” > > are represented as > > +-----------+<------+ > > | abc | | > > +----->+---->+-----------+ | > > | | | def +-------+ > > | | +-----------+ > > | +-----+ ghi |<-------+----+ > > | +-----------+ | | > > +-+--------->| jkl | | | > > | +-----------+ | | > > | | XY.c +--------+ | > > | +-----------+ | > > +----------+ UV.c | | > > +-----------+ | > > | XY.h +-------------+ > > +-----------+ > > > Fig 5. Prefix tree representation of paths in the file path table > > Each parent link implies a path separator ‘/’. Furthermore we represent > each file or directory string as an integer offset into the string table > (see Fig 4). Thus each node holds an offset into the string table and a > pointer to the parent (interior) directory node. > > * String table: To remove redundancies across prefix tree nodes in the > file path encoding, we use a string table which stores the mapping of > string to a unique id. The id can be simplified as the implicit offset into > the table. > > Thus this representation exploits redundancy in the source file path > prefix where there are a large number of source files in a small number of > deeply nested directories. > > Symbolizing the raw PC addresses in post-processing using llvm-profdata > requires the binary to also be provided as input. As an alternative, we > will also experiment with incrementally generating the symbolized call > stack section as part of the raw profile dump at the cost of increased > profiling overhead. > > > Profile Data matching in IR > > —-------------------------- > > When matching the profile data, we may have already early inlined the > direct caller of the allocation into its caller(s). This means we need to > take some additional steps to identify the matching MIBs. For example, > consider the following partial call graph: > > > > ┌────────────────────┐ ┌────────────────────┐ > > A │ Call B; debug loc1 │ C │ Call B; debug loc2 │ > > └───────┬────────────┘ └───────────┬────────┘ > > │ │ > > │ │ > > │ ┌─────────────────────────┐ │ > > └────► Call malloc; debug loc3 ◄─────┘ > > B └─────────────────────────┘ > > There will be 2 MIB entries, one for each context (A->B and C->B). As > noted earlier, the MIB profile entries will be owned by the function > calling the allocation function. Therefore, we will keep both MIB entries > associated with function B in the profile. > > If early inlining (i.e. before profile matching) inlines B into A but not > into C it will look like the following when we try to match the profile: > > > ┌────────────────────┐ > > ┌────────────────────────┐ C │ Call B; debug loc2 │ > > A │Call malloc; debug loc3 │ └───────────┬────────┘ > > │ ; inlined at │ │ > > │ ; debug loc1 │ ┌──────────────┴───────────┐ > > └────────────────────────┘ B │ Call malloc; debug loc3 │ > > └──────────────────────────┘ > > Because the MIB corresponding to the A->B context is associated with > function B in the profile, we do not find it by looking at function A’s > profile when we see function A’s malloc call during matching. To address > this we need to keep a correspondence from debug locations to the > associated profile information. The details of the design will be shared in > a separate RFC in the future. > > [1] https://lists.llvm.org/pipermail/llvm-dev/2020-June/142744.html > > [2] https://git.io/JzdRa > > [3] https://git.io/JzdRR > > [4] https://git.io/JzdRN > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210929/76dbdcfd/attachment-0001.html>
Andrey Bokhanko via llvm-dev
2021-Oct-01 16:14 UTC
[llvm-dev] RFC: A binary serialization format for MemProf
Hi Snehasish, David and Theresa, I'm really glad to see the steady progress in this area! It looks like the format is pretty much language independent (correct?) -- so it can be applied not only to C/C++, but other languages (Rust) and even toolchains (Go) as well? If you have already considered using data profile for non-C/C++, may I kindly ask you to share your thoughts on this? Yours, Andrey ==Advanced Software Technology Lab Huawei On Thu, Sep 30, 2021 at 1:17 AM Snehasish Kumar <snehasishk at google.com> wrote:> > This RFC contains the following: > > * Proposal to introduce a new raw binary serialization format for heap allocation profiles > > * Proposal to extend the PGO indexed format to hold heap allocation profiles > > We look forward to your feedback on the proposals. > Authors: snehasishk at google.com, davidxl at google.com, tejohnson at google.com > > Introduction > > —----------- > > The design of a sanitizer-based heap profiler (MemProf) was shared with llvm-dev in Jun 2020 [1]. Since then Teresa (@tejohnson) has added a sanitizer based heap profiler which can be enabled with -fmemory-profile. Today it writes out the data in a text format which can be inspected by users. We have used this to drive analyses of heap behaviour at Google. This RFC shares details on a binary serialization format for heap profiling data which can then be reused by the compiler to guide optimizations similar to traditional PGO. > > > Similar to the existing instrumentation based PGO, the binary heap profile data for PGHO has two forms. One is the raw data format that is used by the profiler runtime, and the other is the indexed profile format used by the compiler. The profile data with the indexed profile data format will be generated by llvm-profdata from the raw profile data offline. This allows a single binary profile file to hold the PGO and Memprof profiling data. Fig 1 below shows the binary format generation and use. > > > > ┌──────────────────┐ Raw Profile ┌───────────────┐ Indexed Profile (v8) > > │ Compiler Runtime ├─────────────► llvm-profdata ├───► with Memprof data ───► -fprofile-use > > └──────────────────┘ └───────────────┘ > > > Fig 1: Memprof binary profile lifecycle > > > Raw Binary Format > > —---------------- > > The raw binary format contains 4 sections > > > 1. Memprof raw profile header > > 2. Memory mapping layout > > 3. Memory Info Block (MIB) records > > 4. Call stack information > > > +----------------------+ > > | Magic | > > +----------------------+ H > > | Version | E > > +----------------------+ A > > | Total Size | D > > +----------------------+ E > > +---------| Map Offset | R > > | +----------------------+ > > | +-----| MIB Offset | > > | | +----------------------+ > > | | | Call Stack Offset |---------+ > > | | +----------------------+ | > > +-------->| Number of | M | > > | | Map Entries | A | > > | +----------------------+ P | > > | | | | > > | | Map Entry | S | > > | +----------------------+ E | > > | | ... | C | > > | +----------------------+ T | > > | | | I | > > | | Map Entry | O | > > | +----------------------+ N | > > | | > > | | > > | +----------------------+ | > > +---->| Number of | M | > > | MIB Entries | I | > > +----------------------+ B | > > | | | > > | MIB Entry | S | > > +----------------------+ E | > > | ... | C | > > +----------------------+ T | > > | | I | > > | MIB Entry | O | > > +----------------------+ N | > > | > > +----------------------+ | > > | Number of |<--------+ > > | Call Stack Entries | S S > > +----------------------+ T E > > | Call Stack Entry | A C > > +----------------------+ C T > > | ... | K I > > +----------------------+ O > > | Call Stack Entry | N > > +----------------------+ > > > Fig 2: Memprof Raw Format > > > > * Memprof raw profile header > > The header consists of a unique identifier, version number, total size of the profile as well as offset into the profile for each of the following sections - memory mapping layout, memprof profile entries and call stack information. We do not intend to maintain backwards compatibility for the raw binary format. > > > * Memory mapping layout > > The process memory mappings for the executable segment during profiling are stored in this section. This allows symbolization during post processing for binaries which are built with position independent code. For now all read only, executable mappings are recorded, however in the future, mappings for heap data can also potentially be stored. For each mapping, we record > > Start (virtual address) > > End (virtual address) > > Offset (from the file it was mmap-ed from) > > buildId (linker generated hash -Wl,build-id > > > * MIB Records > > The profile information we collect is currently defined in [2]. The section begins with a 8 byte entry containing the number of profile entries in this section. Each entry is uniquely identified by the dynamic calling context of the allocation site. For each entry, various metrics such as access counts, allocation sizes, object lifetimes etc are computed via profiling. This section may contain multiple entries identified by the same callstack id. Subsequent processing to convert and merge multiple raw profiles will deduplicate any such entries. > > > * Call stack information > Each memprof profile entry is uniquely identified by its dynamic calling context. In this section we record the identifier and its corresponding call stack trace. We use the sanitizer stack depot provided identifier and serialize the trace for each without deduplication. The section begins with a 8b entry containing the number of call stack entries. Each call stack entry contains a 8b field which denotes how many contexts are recorded in this entry. Each frame is identified by an 8b program counter address which holds the call instruction virtual address - 1. Further deduplication is possible though we do not do so at this time. > > > * Raw Profile Characteristics > > To understand the characteristics of raw binary profiles generated by Memprof, we experimented with a clang bootstrap build. We ran 500 invocations of Memprof-instrumented clang on clang source code. Each invocation produced a raw binary profile and we present some aggregate information about them below: > > > +---------------------------------+--------+---------+---------+ > > | | Min | Median | Max | > > +---------------------------------+--------+---------+---------+ > > | Unique allocation contexts | 940 | 10661 | 35355 | > > +---------------------------------+--------+---------+---------+ > > | MIB records size (bytes) | 101528 | 1151396 | 3818348 | > > +---------------------------------+--------+---------+---------+ > > | Call stack section size (bytes) | 31080 | 419048 | 1439144 | > > +---------------------------------+--------+---------+---------+ > > | Total Size (bytes) | 133336 | 1571680 | 5258220 | > > +---------------------------------+--------+---------+---------+ > > > The size of the header is 48 bytes and the number of read only executable memory maps is usually small (12 in this case) with each map entry consuming 64 bytes. We find that the raw profiles are highly compressible, on average files are compressed by 81%. The largest raw profile in the dataset is ~5M in size. It is compressed to 975K using zip on default settings. In contrast for the same clang build, the instrumented PGO raw profile is ~21M in size (zip compressed 73%). Note that the Memprof profile size is proportional to the number of allocation contexts during profiling. > > > Since these are profiles from individual invocations, they must be merged before use. This is performed implicitly during the conversion to indexed profile format by llvm-profdata. MIBs are merged based on their call stack. > > > Memprof extensions for the indexed profile format > > —------------------------------------------------ > > > +----------------+ > > | MAGIC | > > +----------------+ > > | VERSION | > > +----------------+ > > | HASHTYPE | > > +--+----------+--+ > > |HASHTAB OFFSET |-------+ > > +--+----------+--+ | > > +----------------+ | > > | | | > > | PROFILE | | > > | SUMMARY | | > > | DATA | | > > +----------------+ | > > +----------------+ <----+ > > | | > > | OnDisk | > > | Chained | > > | HashTable | > > | | > > +----------------+ > > > Fig 3: Existing PGO indexed profile format > > > During the offline processing step (using llvm-profdata), allocation contexts are pruned and merged. The end result is a collection of unique allocation contexts with access, size and lifetime properties. Contexts are uniquely identified based on the call stack and are stored using a prefix deduplication scheme described in Section “Symbolized Memprof call stack section”. > > > To fit into the PGO profile format, we need to index the profile using the function name. The only functions that own Memprof profile data are those direct callers of the allocator primitive functions. Thus the profile data mapping in the IR must account for potentially missing frames. Implications on matching of the profile data with the IR is touched upon in Section “Profile Data matching in IR” and will be further detailed in an upcoming RFC. > > > The Memprof profile data for a particular function can then be just an array of MIB entries. One allocation site in the function can have multiple MIB entries each one of them corresponding to one allocation context. > > > The change to the existing PGO indexed format is summarized as: > > Augment the profile record data structure to include an optional MIB array after the value profile data [3]. > > Add one additional section before the existing OnDiskChainedHashtable to store the allocation stacks (referenced by the MIBs). This section is after the profile summary data section [4]. > > Bump the version number. > > > > Memprof portable entry format > > —---------------------------- > > The raw memprof profile entry format is subject to change with version. However, the indexed profile entry must be backwards compatible to ensure that the PGO profile as a whole is backwards compatible. We propose a schema based format - per function description of a Memprof profile entry. Each field is identified by a tag. We propose the following schema: > > > struct MIBMeta { > > enum MIBFieldTag { > > // The tag ids remain unchanged. > > Unused = 0, > > StackID = 1, > > AllocCount = 2, > > AveSize = 3, > > MinSize = 4, > > MaxSize = 5, > > AveAccessCount = 6, > > MinAccessCount = 7, > > MaxAccessCount = 8, > > AveLifetime = 9, > > MinLifetime = 10, > > MaxLifetime = 11, > > NumMigration = 12, > > NumLifetimeOverlaps = 13, > > NumSameAllocCPU = 14, > > NumSameDeallocCPU = 15 > > }; > > > enum MIBFieldType { > > Unused = 0, > > UINT8 = 1, > > UINT16 = 2, > > UINT32 = 3, // Varint encoded > > UINT64 = 4, // Varint encoded > > }; > > }; > > > > // Mapping of tags to their descriptive names > > const char *MIBFieldName[] = { > > "", > > "StackID", > > "AllocCount", > > … > > "NumSameDeallocCPU" > > }; > > > // Mapping of tags to their types > > uint8 MIBFieldType [] = { > > 0, // unused > > MIBMeta::MIBFieldType::UINT64, > > …. > > }; > > > To make the field tag, field name, and field type declarations always in sync, a shared .inc file will be used. This file will be shared between compiler-rt and llvm/lib/ProfileData libraries. Dependencies across the compiler-rt project are not recommended for isolation. > > > // MIBDef.inc file > > // define MIBEntryDef(tag, name, type) before inclusion > > MIBEntryDef(StackID = 1, "StackID", > > MIBMeta::MIBFieldType::UINT64) > > MIBEntryDef(AllocCount = 2, "AllocCount", > > MIBMeta::MIBFieldType::UINT32) > > ... > > MIBEntryDef(NumSameDeallocCPU=13,"NumSameDeallocCPU", > > MIBMeta::MIBFieldType:UINT8) > > > > enum MIBFieldTag { > > StartTag = 0, > > #define MIBEntryDef(tag, name, type) tag > > #include "MIBDef.inc" > > #undef MIBEntryDef > > }; > > > const char *MIBFieldName { > > #define MIBEntryDef(tag, name, type) name > > "", > > #include "MIBEntryDef.inc" > > #undef MIBEntryDef > > }; > > > uint8 MIBFieldType { > > #define MIBEntryDef(tag, name, type) type > > 0, // not used > > #include "MIBEntryDef.inc" > > #undef MIBDefEntry > > }; > > > The InstrProfRecord for each function will hold the schema and an array of Memprof info blocks, one for each unique allocation context. > > > Symbolized Memprof call stack section > > —------------------------------------ > > This section holds the symbolized version of the call stack section in the raw profile. This is necessary to enable the compiler to map recorded runtime PC addresses to source locations during recompilation. For space efficiency, this section is split into three subsections: 1. stack entry table 2. file path table 3. string table. > > Fig 4 shows the relationship between the three tables. > > > STACK ENTRY FILE PATH STRING > > TABLE TABLE TABLE > > ┌────────┐ ┌──┬──┬──┐ ┌─────────┐ > > │ │ │ │ │ │ │10 abc │ > > │ │ ├──┼──┼──┤ ├─────────┤ > > │ │ │ │ │ │◄┐ │11 def │ > > │ │ ├──┼──┼──┤ │ ├─────────┤ > > ├──┬──┬──┤ │ │ │ │ │ │12 ghi │ > > ┌───┤03│LN│DI│ ├──┼──┼──┤ │ ├─────────┤ > > │ ├──┴──┴──┤ ┌───►│03│13│01├─┘ ┌─►│13 XY.h │ > > │ └────────┘ │ └──┴─┬┴──┘ │ └─────────┘ > > │ │ │ │ > > └────────────────┘ └────────┘ > > > Fig 4. The Stack Entry, File Path and String Table. > > LN = Line Number, DI = Discriminator > > > * Stack Entry Table: Each uniquely identified symbolized call stack consists of a variable number of callsites. In the indexed format, each callsite needs to be represented as file:line:discriminator (as shown in Fig 4). The call stack location is a 64-bit field, but it is split into three subfields: file table index, line number, and the discriminator value. The file table index is a pointer to a leaf node in the prefix encoded scheme described below. > > > * File path table using prefix encoding: Full path filenames have lots of common substrings due to the directory structure so they can be compressed. One simple scheme is to use the reverse prefix tree representation. In this representation, the name string of a directory at each level (not including prefixes) is represented by a node, and it is linked to its parent node. To summarize, the file path table is represented as an array of nodes organized as a forest of reversed tree structures. > > > For instance, the strings > “abc/def/ghi/XY.c”, > “abc/def/ghi/XY.h”, > > “abc/def/jkl/UV.c” > > are represented as > > > +-----------+<------+ > > | abc | | > > +----->+---->+-----------+ | > > | | | def +-------+ > > | | +-----------+ > > | +-----+ ghi |<-------+----+ > > | +-----------+ | | > > +-+--------->| jkl | | | > > | +-----------+ | | > > | | XY.c +--------+ | > > | +-----------+ | > > +----------+ UV.c | | > > +-----------+ | > > | XY.h +-------------+ > > +-----------+ > > > > Fig 5. Prefix tree representation of paths in the file path table > > > Each parent link implies a path separator ‘/’. Furthermore we represent each file or directory string as an integer offset into the string table (see Fig 4). Thus each node holds an offset into the string table and a pointer to the parent (interior) directory node. > > > * String table: To remove redundancies across prefix tree nodes in the file path encoding, we use a string table which stores the mapping of string to a unique id. The id can be simplified as the implicit offset into the table. > > > Thus this representation exploits redundancy in the source file path prefix where there are a large number of source files in a small number of deeply nested directories. > > > Symbolizing the raw PC addresses in post-processing using llvm-profdata requires the binary to also be provided as input. As an alternative, we will also experiment with incrementally generating the symbolized call stack section as part of the raw profile dump at the cost of increased profiling overhead. > > > > Profile Data matching in IR > > —-------------------------- > > > When matching the profile data, we may have already early inlined the direct caller of the allocation into its caller(s). This means we need to take some additional steps to identify the matching MIBs. For example, consider the following partial call graph: > > > > ┌────────────────────┐ ┌────────────────────┐ > > A │ Call B; debug loc1 │ C │ Call B; debug loc2 │ > > └───────┬────────────┘ └───────────┬────────┘ > > │ │ > > │ │ > > │ ┌─────────────────────────┐ │ > > └────► Call malloc; debug loc3 ◄─────┘ > > B └─────────────────────────┘ > > > There will be 2 MIB entries, one for each context (A->B and C->B). As noted earlier, the MIB profile entries will be owned by the function calling the allocation function. Therefore, we will keep both MIB entries associated with function B in the profile. > > > If early inlining (i.e. before profile matching) inlines B into A but not into C it will look like the following when we try to match the profile: > > > > ┌────────────────────┐ > > ┌────────────────────────┐ C │ Call B; debug loc2 │ > > A │Call malloc; debug loc3 │ └───────────┬────────┘ > > │ ; inlined at │ │ > > │ ; debug loc1 │ ┌──────────────┴───────────┐ > > └────────────────────────┘ B │ Call malloc; debug loc3 │ > > └──────────────────────────┘ > > > Because the MIB corresponding to the A->B context is associated with function B in the profile, we do not find it by looking at function A’s profile when we see function A’s malloc call during matching. To address this we need to keep a correspondence from debug locations to the associated profile information. The details of the design will be shared in a separate RFC in the future. > > > [1] https://lists.llvm.org/pipermail/llvm-dev/2020-June/142744.html > > [2] https://git.io/JzdRa > > [3] https://git.io/JzdRR > > [4] https://git.io/JzdRN > >
Wenlei He via llvm-dev
2021-Oct-07 16:18 UTC
[llvm-dev] RFC: A binary serialization format for MemProf
Thanks for sharing the progress and details on the binary format. Overall this
looks like a clean design that fits current PGO profile format with extensions.
Some high level comments:
* Does memprof/PGHO work together with today's IRPGO today, i.e. can we
have one instrumented build to collect both PGO and PGHO profile, or we will
need separate PGO instrumentation builds for each, in which case CSPGO + PGHO
would need three iterations of training and build, which would be significant
operational cost..
* I think some of the problems memprof faced when dealing with storing
calling context and mapping context to IR is very similar to CSSPGO. I'm
wondering if it makes sense to promote some existing infrastructure to be more
general beyond just serving
CSSPGO<https://lists.llvm.org/pipermail/llvm-dev/2020-August/144101.html>.
One example is the IR mapping you mentioned (quoted below). In CSSPGO, we have
the exact same need, and it's handled by `SampleContextTracker` which
queries a context trie using an instruction/DILocation.
> Because the MIB corresponding to the A->B context is
associated with function B in the profile, we do not find it by looking at
function A’s profile when we see function A’s malloc call during matching. To
address this we need to keep a correspondence from debug locations to the
associated profile information.
* The serialization of calling context, pruning of calling context are also
example of shared problems, and we've put in some effort to have effective
solutions (e.g. offline preinliner<https://reviews.llvm.org/D99146> for
most effective pruning, which I think could be adapted to help keep most
important allocation context). Perhaps some of the frameworks can be merged, so
LLVM has general context aware PGO support that can be leverage by different
kinds of PGO (IRPGO, PGHO, CSSPGO). If you think this is worth pursuing, we’d be
happy to help too.
More on the details:
* I saw that MemInfoBlock contains alloc/dealloc cpuid, does that make
memprof profile non-deterministic in the sense that running memprof twice on the
exact program and input would yield bit-wise different memory profile? I think
IR PGO profile is deterministic?
* Why do we use `file:line:discriminator` instead of
`func:line_offset:discriminator `? The later would be more resilient to source
change. If function name string is too long, we could perhaps leverage the MD5
encoding used by sample PGO?
* Is the design of mmap section (quoted below) trying to support memprof for
multiple binaries in the same process at the same time, or mainly for handling
multiple non-consecutive executable segments for a single binary?
> The process memory mappings for the executable segment during
profiling are stored in this section. This allows symbolization during post
processing for binaries which are built with position independent code. For now
all read only, executable mappings are recorded, however in the future,
mappings for heap data can also potentially be stored.
* Do we need each function record to have its own schema, do we expect
different functions to use different versions/schemas? The is very flexible, but
wondering what’s the use case. If the schema is for compatibility across
versions, perhaps a file level scheme would be enough?
> The InstrProfRecord for each function will hold the schema and
an array of Memprof info blocks, one for each unique allocation context.
Thanks,
Wenlei
From: Snehasish Kumar <snehasishk at google.com>
Date: Wednesday, September 29, 2021 at 3:17 PM
To: llvm-dev <llvm-dev at lists.llvm.org>, Vedant Kumar <vsk at
apple.com>, Wenlei He <wenlei at fb.com>, andreybokhanko at gmail.com
<andreybokhanko at gmail.com>, David Li <davidxl at google.com>,
Teresa Johnson <tejohnson at google.com>
Subject: RFC: A binary serialization format for MemProf
This RFC contains the following:
* Proposal to introduce a new raw binary serialization format for heap
allocation profiles
* Proposal to extend the PGO indexed format to hold heap allocation profiles
We look forward to your feedback on the proposals.
Authors: snehasishk at google.com<mailto:snehasishk at google.com>,
davidxl at google.com<mailto:davidxl at google.com>, tejohnson at
google.com<mailto:tejohnson at google.com>
Introduction
—-----------
The design of a sanitizer-based heap profiler (MemProf) was shared with llvm-dev
in Jun 2020 [1]. Since then Teresa (@tejohnson) has added a sanitizer based heap
profiler which can be enabled with -fmemory-profile. Today it writes out the
data in a text format which can be inspected by users. We have used this to
drive analyses of heap behaviour at Google. This RFC shares details on a binary
serialization format for heap profiling data which can then be reused by the
compiler to guide optimizations similar to traditional PGO.
Similar to the existing instrumentation based PGO, the binary heap profile data
for PGHO has two forms. One is the raw data format that is used by the profiler
runtime, and the other is the indexed profile format used by the compiler. The
profile data with the indexed profile data format will be generated by
llvm-profdata from the raw profile data offline. This allows a single binary
profile file to hold the PGO and Memprof profiling data. Fig 1 below shows the
binary format generation and use.
┌──────────────────┐ Raw Profile ┌───────────────┐ Indexed Profile (v8)
│ Compiler Runtime ├─────────────► llvm-profdata ├───► with Memprof data ───►
-fprofile-use
└──────────────────┘ └───────────────┘
Fig 1: Memprof binary profile lifecycle
Raw Binary Format
—----------------
The raw binary format contains 4 sections
1. Memprof raw profile header
2. Memory mapping layout
3. Memory Info Block (MIB) records
4. Call stack information
+----------------------+
| Magic |
+----------------------+ H
| Version | E
+----------------------+ A
| Total Size | D
+----------------------+ E
+---------| Map Offset | R
| +----------------------+
| +-----| MIB Offset |
| | +----------------------+
| | | Call Stack Offset |---------+
| | +----------------------+ |
+-------->| Number of | M |
| | Map Entries | A |
| +----------------------+ P |
| | | |
| | Map Entry | S |
| +----------------------+ E |
| | ... | C |
| +----------------------+ T |
| | | I |
| | Map Entry | O |
| +----------------------+ N |
| |
| |
| +----------------------+ |
+---->| Number of | M |
| MIB Entries | I |
+----------------------+ B |
| | |
| MIB Entry | S |
+----------------------+ E |
| ... | C |
+----------------------+ T |
| | I |
| MIB Entry | O |
+----------------------+ N |
|
+----------------------+ |
| Number of |<--------+
| Call Stack Entries | S S
+----------------------+ T E
| Call Stack Entry | A C
+----------------------+ C T
| ... | K I
+----------------------+ O
| Call Stack Entry | N
+----------------------+
Fig 2: Memprof Raw Format
* Memprof raw profile header
The header consists of a unique identifier, version number, total size of the
profile as well as offset into the profile for each of the following sections -
memory mapping layout, memprof profile entries and call stack information. We do
not intend to maintain backwards compatibility for the raw binary format.
* Memory mapping layout
The process memory mappings for the executable segment during profiling are
stored in this section. This allows symbolization during post processing for
binaries which are built with position independent code. For now all read only,
executable mappings are recorded, however in the future, mappings for heap data
can also potentially be stored. For each mapping, we record
* Start (virtual address)
* End (virtual address)
* Offset (from the file it was mmap-ed from)
* buildId (linker generated hash -Wl,build-id
* MIB Records
The profile information we collect is currently defined in [2]. The section
begins with a 8 byte entry containing the number of profile entries in this
section. Each entry is uniquely identified by the dynamic calling context of the
allocation site. For each entry, various metrics such as access counts,
allocation sizes, object lifetimes etc are computed via profiling. This section
may contain multiple entries identified by the same callstack id. Subsequent
processing to convert and merge multiple raw profiles will deduplicate any such
entries.
* Call stack information
Each memprof profile entry is uniquely identified by its dynamic calling
context. In this section we record the identifier and its corresponding call
stack trace. We use the sanitizer stack depot provided identifier and serialize
the trace for each without deduplication. The section begins with a 8b entry
containing the number of call stack entries. Each call stack entry contains a 8b
field which denotes how many contexts are recorded in this entry. Each frame is
identified by an 8b program counter address which holds the call instruction
virtual address - 1. Further deduplication is possible though we do not do so at
this time.
* Raw Profile Characteristics
To understand the characteristics of raw binary profiles generated by Memprof,
we experimented with a clang bootstrap build. We ran 500 invocations of
Memprof-instrumented clang on clang source code. Each invocation produced a raw
binary profile and we present some aggregate information about them below:
+---------------------------------+--------+---------+---------+
| | Min | Median | Max |
+---------------------------------+--------+---------+---------+
| Unique allocation contexts | 940 | 10661 | 35355 |
+---------------------------------+--------+---------+---------+
| MIB records size (bytes) | 101528 | 1151396 | 3818348 |
+---------------------------------+--------+---------+---------+
| Call stack section size (bytes) | 31080 | 419048 | 1439144 |
+---------------------------------+--------+---------+---------+
| Total Size (bytes) | 133336 | 1571680 | 5258220 |
+---------------------------------+--------+---------+---------+
The size of the header is 48 bytes and the number of read only executable memory
maps is usually small (12 in this case) with each map entry consuming 64 bytes.
We find that the raw profiles are highly compressible, on average files are
compressed by 81%. The largest raw profile in the dataset is ~5M in size. It is
compressed to 975K using zip on default settings. In contrast for the same clang
build, the instrumented PGO raw profile is ~21M in size (zip compressed 73%).
Note that the Memprof profile size is proportional to the number of allocation
contexts during profiling.
Since these are profiles from individual invocations, they must be merged before
use. This is performed implicitly during the conversion to indexed profile
format by llvm-profdata. MIBs are merged based on their call stack.
Memprof extensions for the indexed profile format
—------------------------------------------------
+----------------+
| MAGIC |
+----------------+
| VERSION |
+----------------+
| HASHTYPE |
+--+----------+--+
|HASHTAB OFFSET |-------+
+--+----------+--+ |
+----------------+ |
| | |
| PROFILE | |
| SUMMARY | |
| DATA | |
+----------------+ |
+----------------+ <----+
| |
| OnDisk |
| Chained |
| HashTable |
| |
+----------------+
Fig 3: Existing PGO indexed profile format
During the offline processing step (using llvm-profdata), allocation contexts
are pruned and merged. The end result is a collection of unique allocation
contexts with access, size and lifetime properties. Contexts are uniquely
identified based on the call stack and are stored using a prefix deduplication
scheme described in Section “Symbolized Memprof call stack section”.
To fit into the PGO profile format, we need to index the profile using the
function name. The only functions that own Memprof profile data are those direct
callers of the allocator primitive functions. Thus the profile data mapping in
the IR must account for potentially missing frames. Implications on matching of
the profile data with the IR is touched upon in Section “Profile Data matching
in IR” and will be further detailed in an upcoming RFC.
The Memprof profile data for a particular function can then be just an array of
MIB entries. One allocation site in the function can have multiple MIB entries
each one of them corresponding to one allocation context.
The change to the existing PGO indexed format is summarized as:
* Augment the profile record data structure to include an optional MIB array
after the value profile data [3].
* Add one additional section before the existing OnDiskChainedHashtable to
store the allocation stacks (referenced by the MIBs). This section is after the
profile summary data section [4].
* Bump the version number.
Memprof portable entry format
—----------------------------
The raw memprof profile entry format is subject to change with version. However,
the indexed profile entry must be backwards compatible to ensure that the PGO
profile as a whole is backwards compatible. We propose a schema based format -
per function description of a Memprof profile entry. Each field is identified by
a tag. We propose the following schema:
struct MIBMeta {
enum MIBFieldTag {
// The tag ids remain unchanged.
Unused = 0,
StackID = 1,
AllocCount = 2,
AveSize = 3,
MinSize = 4,
MaxSize = 5,
AveAccessCount = 6,
MinAccessCount = 7,
MaxAccessCount = 8,
AveLifetime = 9,
MinLifetime = 10,
MaxLifetime = 11,
NumMigration = 12,
NumLifetimeOverlaps = 13,
NumSameAllocCPU = 14,
NumSameDeallocCPU = 15
};
enum MIBFieldType {
Unused = 0,
UINT8 = 1,
UINT16 = 2,
UINT32 = 3, // Varint encoded
UINT64 = 4, // Varint encoded
};
};
// Mapping of tags to their descriptive names
const char *MIBFieldName[] = {
"",
"StackID",
"AllocCount",
…
"NumSameDeallocCPU"
};
// Mapping of tags to their types
uint8 MIBFieldType [] = {
0, // unused
MIBMeta::MIBFieldType::UINT64,
….
};
To make the field tag, field name, and field type declarations always in sync, a
shared .inc file will be used. This file will be shared between compiler-rt and
llvm/lib/ProfileData libraries. Dependencies across the compiler-rt project are
not recommended for isolation.
// MIBDef.inc file
// define MIBEntryDef(tag, name, type) before inclusion
MIBEntryDef(StackID = 1, "StackID",
MIBMeta::MIBFieldType::UINT64)
MIBEntryDef(AllocCount = 2, "AllocCount",
MIBMeta::MIBFieldType::UINT32)
...
MIBEntryDef(NumSameDeallocCPU=13,"NumSameDeallocCPU",
MIBMeta::MIBFieldType:UINT8)
enum MIBFieldTag {
StartTag = 0,
#define MIBEntryDef(tag, name, type) tag
#include "MIBDef.inc"
#undef MIBEntryDef
};
const char *MIBFieldName {
#define MIBEntryDef(tag, name, type) name
"",
#include "MIBEntryDef.inc"
#undef MIBEntryDef
};
uint8 MIBFieldType {
#define MIBEntryDef(tag, name, type) type
0, // not used
#include "MIBEntryDef.inc"
#undef MIBDefEntry
};
The InstrProfRecord for each function will hold the schema and an array of
Memprof info blocks, one for each unique allocation context.
Symbolized Memprof call stack section
—------------------------------------
This section holds the symbolized version of the call stack section in the raw
profile. This is necessary to enable the compiler to map recorded runtime PC
addresses to source locations during recompilation. For space efficiency, this
section is split into three subsections: 1. stack entry table 2. file path table
3. string table.
Fig 4 shows the relationship between the three tables.
STACK ENTRY FILE PATH STRING
TABLE TABLE TABLE
┌────────┐ ┌──┬──┬──┐ ┌─────────┐
│ │ │ │ │ │ │10 abc │
│ │ ├──┼──┼──┤ ├─────────┤
│ │ │ │ │ │◄┐ │11 def │
│ │ ├──┼──┼──┤ │ ├─────────┤
├──┬──┬──┤ │ │ │ │ │ │12 ghi │
┌───┤03│LN│DI│ ├──┼──┼──┤ │ ├─────────┤
│ ├──┴──┴──┤ ┌───►│03│13│01├─┘ ┌─►│13 XY.h │
│ └────────┘ │ └──┴─┬┴──┘ │ └─────────┘
│ │ │ │
└────────────────┘ └────────┘
Fig 4. The Stack Entry, File Path and String Table.
LN = Line Number, DI = Discriminator
* Stack Entry Table: Each uniquely identified symbolized call stack consists of
a variable number of callsites. In the indexed format, each callsite needs to be
represented as file:line:discriminator (as shown in Fig 4). The call stack
location is a 64-bit field, but it is split into three subfields: file table
index, line number, and the discriminator value. The file table index is a
pointer to a leaf node in the prefix encoded scheme described below.
* File path table using prefix encoding: Full path filenames have lots of common
substrings due to the directory structure so they can be compressed. One simple
scheme is to use the reverse prefix tree representation. In this representation,
the name string of a directory at each level (not including prefixes) is
represented by a node, and it is linked to its parent node. To summarize, the
file path table is represented as an array of nodes organized as a forest of
reversed tree structures.
For instance, the strings
“abc/def/ghi/XY.c”,
“abc/def/ghi/XY.h”,
“abc/def/jkl/UV.c”
are represented as
+-----------+<------+
| abc | |
+----->+---->+-----------+ |
| | | def +-------+
| | +-----------+
| +-----+ ghi |<-------+----+
| +-----------+ | |
+-+--------->| jkl | | |
| +-----------+ | |
| | XY.c +--------+ |
| +-----------+ |
+----------+ UV.c | |
+-----------+ |
| XY.h +-------------+
+-----------+
Fig 5. Prefix tree representation of paths in the file path table
Each parent link implies a path separator ‘/’. Furthermore we represent each
file or directory string as an integer offset into the string table (see Fig 4).
Thus each node holds an offset into the string table and a pointer to the parent
(interior) directory node.
* String table: To remove redundancies across prefix tree nodes in the file path
encoding, we use a string table which stores the mapping of string to a unique
id. The id can be simplified as the implicit offset into the table.
Thus this representation exploits redundancy in the source file path prefix
where there are a large number of source files in a small number of deeply
nested directories.
Symbolizing the raw PC addresses in post-processing using llvm-profdata requires
the binary to also be provided as input. As an alternative, we will also
experiment with incrementally generating the symbolized call stack section as
part of the raw profile dump at the cost of increased profiling overhead.
Profile Data matching in IR
—--------------------------
When matching the profile data, we may have already early inlined the direct
caller of the allocation into its caller(s). This means we need to take some
additional steps to identify the matching MIBs. For example, consider the
following partial call graph:
┌────────────────────┐ ┌────────────────────┐
A │ Call B; debug loc1 │ C │ Call B; debug loc2 │
└───────┬────────────┘ └───────────┬────────┘
│ │
│ │
│ ┌─────────────────────────┐ │
└────► Call malloc; debug loc3 ◄─────┘
B └─────────────────────────┘
There will be 2 MIB entries, one for each context (A->B and C->B). As
noted earlier, the MIB profile entries will be owned by the function calling the
allocation function. Therefore, we will keep both MIB entries associated with
function B in the profile.
If early inlining (i.e. before profile matching) inlines B into A but not into C
it will look like the following when we try to match the profile:
┌────────────────────┐
┌────────────────────────┐ C │ Call B; debug loc2 │
A │Call malloc; debug loc3 │ └───────────┬────────┘
│ ; inlined at │ │
│ ; debug loc1 │ ┌──────────────┴───────────┐
└────────────────────────┘ B │ Call malloc; debug loc3 │
└──────────────────────────┘
Because the MIB corresponding to the A->B context is associated with function
B in the profile, we do not find it by looking at function A’s profile when we
see function A’s malloc call during matching. To address this we need to keep a
correspondence from debug locations to the associated profile information. The
details of the design will be shared in a separate RFC in the future.
[1]
https://lists.llvm.org/pipermail/llvm-dev/2020-June/142744.html<https://lists.llvm.org/pipermail/llvm-dev/2020-June/142744.html>
[2] https://git.io/JzdRa<https://git.io/JzdRa>
[3] https://git.io/JzdRR<https://git.io/JzdRR>
[4] https://git.io/JzdRN<https://git.io/JzdRN>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20211007/e73bc201/attachment-0001.html>