[Posted on behalf of Jan Newger since discourse limits the number of links and images for new users]
Hi folks,
This RFC proposes a compiler extension (“CopySanitizer”) to identify the creation of unnecessary object copies in C++ applications at runtime.
Would love to hear everybody’s feedback about it.
Authors: Jan Newger (jannewger@google.com), Snehasish Kumar (snehasishk@google.com) with contributions from Brian Suchy, Caslyn Tonelli, Michal Terepeta.
Motivation
There’s reason to believe that in large C++ applications a significant amount of resources is spent on unnecessary/unintended object copies that could be avoided by referring back to the original object instead (e.g. via pointer/reference, extending its lifetime if need be).
Avoiding unnecessary copies generally means less heap traffic, lower peak heap usage and ideally allows for tighter shaping of production workloads. Second order positive effects include reduced pressure on the memory subsystem and lower CPU utilization.
The ongoing DRAM supply shortage further amplifies potential cost savings.
Below is a concrete example that can be identified using CSan (this was actually reported as a performance bug internally at Google):
struct Foo {
std::vector<int> v1;
std::vector<int> v2;
};
Foo GetFoo();
std::vector<int> CopiesTheVector() {
Foo foo = GetFoo();
return foo.v1; // This does not implicitly move.
}
foo.v1 is not a plain id-expression naming a local variable, so it doesn’t qualify for an implicit move and the compiler must perform a copy of the field when returning. CSan detects this and reports foo.v1 as having been copied unnecessarily. Obligatory godbolt link.
Proposal
The proposed CSan compiler extension consists of a few patches to the Clang frontend, an instrumentation pass and a new compiler runtime.
The approach is based on instrumenting special member functions of C++ class types and memory store instructions. Shadow memory is used to mark application memory as either “copy” or “not copy”. A memory store marks the corresponding shadow bits as “not copy” whereas a copy function marks the object and all of its owned memory as “copy”.
A report is generated at the end of an object’s d’tor if all relevant shadow memory was marked as “copy”.
The example below illustrates the basic concepts
struct MyString {
MyString(const char* s);
~MyString();
MyString(const MyString& other);
size_t size;
size_t capacity;
char* buffer;
};
int main() {
MyString my_str = GetString(); // (1)
MyString copied_str = str1; // (2)
} // (3)
In line (1) a new MyString object is created in application memory. The dynamic char array is allocated on the heap and is represented by a memory region external to the object itself. Each byte in application memory has corresponding shadow memory bits which denote whether a block of memory is considered as having been copied (by a copy function).
The shadow memory corresponding to my_str is colored in green, meaning it was not created as a copy.
Line (2) creates a copy of my_str using MyString’s copy c’tor. While the copy c’tor is executing, a new char array is allocated on the heap, and its contents are set by copying from the original char array. Because the allocation and the memory stores happen during the execution of a copy function of MyString, the corresponding shadow memory bits are marked as having been copied (red blocks).
In line (3) the d’tor of both copied_str runs and the char array is deleted. CSan intercepts operator delete and checks the corresponding shadow memory as well as the shadow corresponding to the object itself. A report is generated if all shadow memory is marked as “copy”. Since copied_str was not modified at all, CSan prints a report like this:
[csan] Destroyed unnecessary copy amounting to 28 bytes:
#0 0x5593487d654a in ~vector /usr/lib/gcc/x86_64-linux-gnu/15/../../../../include/c++/15/bits/stl_vector.h:805:7
#1 0x5593487d654a in main /home/jannewger/git/copy_sanitizer/build/../../test.cc:23:3
#2 0x7f5012029f76 in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16
#3 0x7f501202a026 in __libc_start_main csu/../csu/libc-start.c:360:3
#4 0x559348783410 in _start (/home/jannewger/git/copy_sanitizer/build/a.out+0x1a410)
Consider the following example, which demonstrates why it is insufficient to only check the shadow memory of the object itself.
int main() {
MyString my_str = GetString(); // (1)
MyString copied_str = str1; // (2)
copied_str[0] = 'x'; // (3)
}
Note that the object itself stays unmodified and is therefore still marked as “copy”. Due to the string modification, the owned char array is marked as “not copy”. If only the memory corresponding to copied_str itself was checked at destruction time, then CSan would report copied_str as an unnecessary copy. But that’s undesirable since memory owned by the object was indeed modified, making it a unique object that cannot be replaced with a reference to the original my_str.
Inferring ownership semantics of memory allocations is thus essential to prevent false positives.
To determine whether an object copy has remained unmodified (which is what qualifies it as an “unnecessary copy”), the memory comprising the object itself and all transitively owned memory (the memory that “logically” belongs to the object) must have remained unmodified.
This problem decomposes into two questions:
-
Which fields denote an ownership relation?
-
Given that set of fields, what are their concrete memory ranges?
The difficulty is that memory ownership cannot be statically determined by inspecting the type system. For example, consider a (purposely) naive string type vs a string view type:
struct MyString {
MyString(const MyString&) {...};
size_t size;
size_t capacity;
char* buffer;
};
struct MyStringView {
size_t size;
const char* buffer;
};
The type system itself doesn’t provide sufficient information to determine ownership information. Both types contain a char pointer but only the field in MyString denotes ownership of the pointed memory block.
To solve this, CSan uses a heuristic that links spatial proximity to ownership: any memory allocated while the execution flow is within a copy function’s call stack is attributed to the corresponding object. On the flip side, when destroying an object, the shadow memory of all transitively deallocated memory is checked to determine whether to generate a report.
This approach seems to work well in practice but is not precise and may lead to false positives.
Compiler
The frontend adds a string attribute to special member functions of the form csan-[ctor|dtor|copy-ctor|copy-assignment-op]=%static_class_size%.
The attribute is parsed by the instrumentation pass to instrument the code with a call to the corresponding runtime function. The static size of the object is required to mark shadow memory accordingly.
All memory stores are instrumented and the corresponding shadow memory is marked as “not a copy”. This assumes that stores unconditionally modify object memory which may not be true necessarily, and may lead to false negatives.
Runtime and Shadow Memory
The runtime handles callbacks from special member functions of eligible C++ classes, and all memory store operations.
CSan uses a shadow mapping of 1:8, i.e., each byte of application memory corresponds to one bit of shadow memory. The CSan runtime also manages a per-thread state machine that indicates whether control flow is currently inside the call stack of a special member function or not. It controls how shadow memory is updated, or whether it needs to be checked.
Shadow memory is updated based on the current state: if control flow is within the call stack of a copy function, all allocated memory as well as all written memory is marked as “copy”. This state is only left once the top-level copy function is exited. The idea is that anything happening within that function logically contributes to the process of forming a copy. The same concept applies to the construction of new object instances: as part of the top-level c’tor, sub-objects may be copied or destroyed but that doesn’t matter as the overall logical operation is still the creation of the top-level object. Thus, any memory allocated or touched is marked as “not copy”.
During destruction of an object all deallocated memory is checked for being “copy” or “not copy”. Any memory writes in this state are ignored to prevent false negatives (e.g. d’tors clearing fields, inherited d’tors shifting vptrs, etc. that would otherwise render the object as “not copy”) and a report is generated if all such memory is marked as “copy”.
The CSan runtime uses the interception framework to hook into libc heap functions as well as operator new and operator delete to be able to get control when memory is (de-)allocated. Depending on the state of the current thread it then marks (or checks) shadow memory.
Reports
A report calls out the transitive size (i.e. flat object size + all allocations made while the copy was formed) of an unnecessary copy and its stack trace when it was destroyed.
Reports can be dumped to stdout or to a file on disk. The file format is very similar to the one used by memprof and the llvm-profdata tool.
To move reporting out of the critical path of the application code, reports are stored in fixed sized memory buffers. New buffers can be obtained from and returned to a central freelist. A background thread continuously flushes report buffers to disk or stdout. Stack traces are stored in StackDepot.
Not all unnecessary copies are worth reporting on. Eligible class types can be selected by their static size and the default is to not mark classes for instrumentation whose size is <= 16 bytes. Frequently used vocabulary types such as std::string_view, std::span and the like fall into this category, and should not be reported on.
Reports can also be gated on whether memory was allocated (must_allocate=true) while an object copy was formed, or on the total transitive size of memory belonging to the object (flat object size + all transitive allocations).
Runtime Overhead
Running a test application compiled with CSan takes 4.9x as long as the same application compiled w/o it. When built with ASan, the application takes 3.6x as long. Note that the current prototype has not undergone any significant optimizations. It is expected that the performance overhead will ultimately be comparable to that of ASan.
Alternatives Considered
Not much tooling seems to exist that explicitly calls out unnecessary copies.
Clang-tidy has checks for arguments that are unnecessarily passed to a function by value (performance-unnecessary-value-param) and there’s another check (performance-unnecessary-copy-initialization) to catch initialization by value when a reference would suffice. Like all static analysis based checks, they share the problem of having to be very conservative in terms of what is reported due to intractability of precise static analysis.
People seem to mostly rely on indirect metrics such as regular hot path analysis or correlating a lot of heap traffic or peak heap allocations (c.f. memprof).
The proposal relies on compiler instrumentation so the source code must be available for CSan to work. Instrumentation of binaries or existing build artifacts is thus out of scope.
CSan is currently only useful for C++ applications as it relies on instrumenting C++ classes’ special member functions to drive its state machine.
Current Status and Future Direction
CSan currently generates reports only for fully transitive copies, but it could also support partial copies (only some sub-objects being unnecessary copies) or fractional copies where only a small fraction of the owned memory was copied.
Filtering eligible C++ classes is still rather limited and relies purely on static object size. Other useful filters could be by class name or file system path to the translation unit. Also exclusivity filters such as “only instrument protobuf class types”, or letting users specify which types to never instrument could be useful.
The current implementation does not inherently support custom memory allocation schemes such as arenas. Arena allocated objects are often not explicitly destroyed for efficiency reasons (i.e. their d’tors are never invoked), instead the arena as a whole is deleted, or reused. That means CSan does not recognize that an object’s lifetime ends, and thus cannot check the copy status of the corresponding shadow memory. This leads to false negatives. Furthermore, if a copy function uses a custom allocator that is unknown to CSan (i.e. anything that is not malloc or operator new), then CSan won’t be able to infer ownership relations which may lead to false positive reports.
In the future CSan could use source code annotations and/or APIs such that custom allocators could communicate the necessary information to the CSan runtime.
An interesting open question is whether the CSan approach can be generalized to languages other than C++, e.g., by working purely on the LLVM IR level w/o relying on the Clang frontend to mark special member functions.
In multi-threaded code, work is sometimes handed off to worker threads by invoking a copy instead of passing a reference that might need to be locked. CSan currently does no special handling for inter-thread copies. It is presently unclear whether that’s a significant source of false positives, though.
CSan will probably be most useful when combined with other tools that extract runtime aspects of applications. Finding opportunities for optimization via CSan and then intersecting these with hotness information obtained from other tools (e.g. CPU profilers, memprof, etc) seems like a promising approach going forward.