Clang and GCC 4.9implemented LeakSanitizer in 2013. LeakSanitizer(LSan) is a memory leak detector. It intercepts memory allocationfunctions and by default detects memory leaks at atexittime. The implementation is purely in the runtime(compiler-rt/lib/lsan) and no instrumentation isneeded.

LSan has very little architecture-specific code and supports many64-bit targets. Some 32-bit targets (e.g. Linux arm/x86-32) aresupported as well, but there may be high false negatives becausepointers with fewer bits are more easily confused with integers/floatingpoints/other data of a similar pattern. Every supported operating systemneeds to provide some way to "stop the world".

Usage

LSan can be used in 3 ways.

• Standalone (-fsanitize=leak)
• AddressSanitizer (-fsanitize=address)
• HWAddressSanitizer (-fsanitize=hwaddress)

The most common way to use LSan isclang -fsanitize=address (orgcc -fsanitize=address). For LSan-supported targets(#define CAN_SANITIZE_LEAKS 1), the AddressSanitizer (ASan)runtime enables LSan by default.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

% cat a.c
#include <stdlib.h>
int main() {
  void **p = malloc(42); // leak (categorized as "Direct leak")
  *p = malloc(43);       // leak (categorized as "Indirect leak")
  p = 0;
}
% clang -fsanitize=address a.c -o a
% ./a

=================================================================
==594015==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 42 byte(s) in 1 object(s) allocated from:
    #0 0x55fffef9482e  (/tmp/c/a+0xea82e)
    #1 0x55fffefcf1d1  (/tmp/c/a+0x1251d1)
    #2 0x7f7301626189  (/lib/x86_64-linux-gnu/libc.so.6+0x27189) (BuildId: c4f6727c560b1c33527ff9e0ca0cef13a7db64d2)

Indirect leak of 43 byte(s) in 1 object(s) allocated from:
    #0 0x55fffef9482e  (/tmp/c/a+0xea82e)
    #1 0x55fffefcf1df  (/tmp/c/a+0x1251df)
    #2 0x7f7301626189  (/lib/x86_64-linux-gnu/libc.so.6+0x27189) (BuildId: c4f6727c560b1c33527ff9e0ca0cef13a7db64d2)

SUMMARY: AddressSanitizer: 85 byte(s) leaked in 2 allocation(s).

As a runtime-only feature, -fsanitize=leak is mainly forlink actions. When linking an executable, with the default-static-libsan mode on many targets, Clang Driver passes--whole-archive $resource_dir/lib/$triple/libclang_rt.lsan.a --no-whole-archiveto the linker. GCC and some platforms prefer shared runtime/dynamicruntime. See Allabout sanitizer interceptors.

1
2
3
4

% clang -fsanitize=leak a.o '-###' |& grep --color lsan
... --whole-archive" "/tmp/Rel/lib/clang/17/lib/x86_64-unknown-linux-gnu/libclang_rt.lsan.a" "--no-whole-archive" ...
% gcc -fsanitize=leak a.o '-###' |& grep --color lsan
... /usr/lib/gcc/x86_64-linux-gnu/12/liblsan_preinit.o --push-state --no-as-needed -llsan ...

-fsanitize=leak affects compile actions as well, butonly for the following C/C++ preprocessor feature.

1
2
3
4
5
6
7
8

// Active if -fsanitize=leak
#if __has_feature(leak_sanitizer)
...
#endif

// Active if -fsanitize=leak or -fsanitize=address
#if __has_feature(leak_sanitizer) || __has_feature(address_sanitizer)
#endif

Implementation overview

Standalone LSan intercepts malloc-family and free-family functions.It uses the temporized SizeClassAllocator{32,64} with chunkmetadata. The interceptors record the allocation information (requestedsize, stack trace).

AddressSanitizer and HWAddressSanitizer already interceptmalloc-family functions. Their chunk metadata representations have aflag field for LSan.

By default the common options detect_leaks andleak_check_at_exit are enabled. The runtime installs a hookwith atexit which will perform the leak check.Alternatively, the user can call __lsan_do_leak_check torequest a leak check before the exit time.

Upon a leak check, the runtime performs a job very similar to amark-and-sweep garbage collection algorithm. It suspends all threads("stop the world") and scans the root set to find reachable allocations.The root set includes:

• ignored allocations due to __lsan_ignore_object,__lsan::ScopedDisabler, or __lsan_disable
• global regions (__lsan::ProcessGlobalRegions). OnLinux, these refer to memory mappings due to writablePT_LOAD program headers. This ensures that allocationsreachable by a global variable are not leaks.
• for each thread, general-purpose registers (defaultuse_registers=1), stacks (defaultuse_stacks=1), thread-local storage (defaultuse_tls=1), and additional pointers in the threadcontext
• root regions due to __lsan_register_root_region
• operating system specific allocations. This is currentlymacOS-specific: libdispatch and Foundation memory regions, etc.

(When ASan is used and use_stacks is enabled, fakestacks are also in the root set for use-after-returndetection. Seecompiler-rt/test/lsan/TestCases/use_after_return.cpp.)

The runtimes uses a flood fill algorithm to find reachableallocations from the root set. This done conservatively by finding allaligned bit patterns which look like a pointer. If the word looks like apointer into the heap (many 64-bit targets use[0x600000000000, 0x640000000000) as the allocator space),the runtime checks whether it refers to an allocated chunk. InValgrind's terms, a reference can be a "start-pointer" (a pointer to thestart of the chunk) or an "interior-pointer" (a pointer to the middle ofthe chunk).

Finally, the runtime iterates over all allocated allocations andreports leaks for unmarked allocations.

Metadata

Each allocation reserves 2 bits to record its state:leaked/reachable/ignored. For better diagnostics, "leaked" can be director indirect (Valgrind memcheck's term). If a chunk is marked as leaked,all chunks reachable from it are marked as indirectly leaked.(*p = malloc(43); in the very beginning example is anindirect leak.)

1
2
3
4
5
6

enum ChunkTag {
  kDirectlyLeaked = 0,  // default
  kIndirectlyLeaked = 1,
  kReachable = 2,
  kIgnored = 3
};

The idea may be that after the user fixes all direct leaks, indirectleaks will likely go away if directly leaked objects have destructors todeallocate their references. However, indirect leaks may form a cycleand fixing all direct leaks does not fix these indirect leaks.

1
2
3
4
5
6
7
8

#include <stdlib.h>
#include <stdio.h>
int main() {
  void *x = malloc(8), *y = malloc(8);
  *(void **)x = y;   // in a cycle. Indirect leak
  *(void **)y = x;   // in a cycle. Indirect leak
  printf("%p %p\n", x, y);
}

Standalone LSan uses this chunk metadata struct:

1
2
3
4
5
6
7
8
9
10
11

struct ChunkMetadata {
  u8 allocated : 8;  // Must be first.
  ChunkTag tag : 2;
#if SANITIZER_WORDSIZE == 64
  uptr requested_size : 54;
#else
  uptr requested_size : 32;
  uptr padding : 22;
#endif
  u32 stack_trace_id;
};

ASan just stores a 2-bit ChunkTag in its existing chunkmetadata (__asan::Chunkheader::lsan_tag). Similarly, HWASanstores a 2-bit ChunkTag in its existing chunk metadata(__hwasan::Metadata::lsan_tag).

Allocator

Sanitizers use very similar allocators. To share code,compiler-rt/lib/sanitizer_common defines temporizedSizeClassAllocator{32,64} as allocator factories. Eachsanitizer instantiates one of SizeClassAllocator{32,64} asthe primary allocator and picks a secondary allocator. One templateargument describes the metadata size per chunk. E.g. standalone LSansets the metadata size to sizeof(ChunkMetadata).

One template argument defines size classes(SizeClassMap). A SizeClassAllocator{32,64}(primary allocator) instance has a thread-local cache(SizeClassAllocator{32,64}LocalCache), which maintains afree list for each of these classes. Upon an allocation request, if thefree list for the requested size class is empty, the runtime will callRefill on the cache to grab more chunks fromSizeClassAllocator{32,64}. If the free list is not empty,the cache will hand over a chunk from the free list to the user.

SizeClassAllocator64 has a total allocator space ofkSpaceSize bytes, splitting into multiple regions of thesame size (kSpaceSize), each serving a single size class.Each region is sufficiently large and is assumed to be able toaccommodate all allocations of its size class. When Refillis called on the cache, the runtime takes a lock of theSizeClassAllocator64 region and calls mmap toallocate a new memory mapping (and if kMetadataSize!=0,another memory mapping for metadata). For an active allocation, it isvery efficient to compute its index in the region and its associatedmetadata. Standalone LSan sets the tag to kDirectlyLeakedfor a new allocation which is not ignored. ASan is similar.

SizeClassAllocator32 is mainly for 32-bit address spacesbut can also be used for 64-bit address spaces. Like inSizeClassAllocator64, the address space splits intomultiple regions, but the region size is much smaller(kRegionSize; typically 1MiB). When the cache callsRefill, SizeClassAllocator32 callsmmap to allocate a new region serving the requested sizeclass. The mapping from the region ID to the size class is recorded inpossible_regions_ (which is an array wrapper in the 32-bitaddress space case).

Iterating over SizeClassAllocator64 is simple andefficient. Each size class has just one region. A region consists ofmultiple chunks.

1
2
3
4
5
6
7
8
9
10

void ForEachChunk(ForEachChunkCallback callback, void *arg) {
  for (uptr class_id = 1; class_id < kNumClasses; class_id++) {
    RegionInfo *region = GetRegionInfo(class_id);
    uptr chunk_size = ClassIdToSize(class_id);
    uptr region_beg = SpaceBeg() + class_id * kRegionSize;
    uptr region_allocated_user_size = AddressSpaceView::Load(region)->allocated_user;
    for (uptr chunk = region_beg; chunk < region_beg + region_allocated_user_size; chunk += chunk_size)
      callback(chunk, arg);
  }
}

LSan iterates over chunks to find ignored chunks (they are in theroot set) and leaked chunks (for error reporting).

Iterating over SizeClassAllocator32 is efficient with a32-bit address space (at most 2**32/kSpaceSize = 4096regions) but inefficient with a 64-bit address space. See an issue LSan is almostunusable on AArch64 (fixed by switching toSizeClassAllocator64).

Stop the world

On Linux, the runtime create a tracer thread to suspend all otherthreads. More specifically:

• Invoke the clone syscall to create a new process whichshared the address space with the calling process.
• In the new process, list threads by iterating over/proc/$pid/task/.
• In the new process, call SuspendThread (ptracePTRACE_ATTACH) to suspend a thread.

StopTheWorld returns. The runtime performsmark-and-sweep, reports leaks, and then callsResumeAllThreads (ptrace PTRACE_DETACH).

Note: the implementation cannot call libc functions. It does notperform code injection. The toot set includes static/dynamic TLS blocksfor each thread.

On Fuchsia, the runtime calls__sanitizer_memory_snapshot to stop the world.

Runtime options

LSan provides some runtime options to toggle behaviors. Specify theenvironment variable LSAN_OPTIONS to toggle runtimebehaviors.

LSAN_OPTIONS=use_registers=0:use_stacks=0:use_tls=0 canremove some default root regions. report_objects=1 reportsthe addresses of individual leaked objects.

use_stacks=0: remove stacks from the root set. Thedefault is 1 to prevent false positives for the following early exitcode.

1
2
3
4

int main() {
  std::unique_ptr<XXX> a = ...;
  if (...) exit(0);
}

However, the default can cause LSan to detect fewer leaks as theremay be dangling pointers on the stacks.

1
2

struct C { int x = 0; };
int main() { C *a = new C, *b = new C, *c = new C, *d = new C; }

Some options (below) are implemented as common options(compiler-rt/lib/sanitizer_common/sanitizer_flags.inc).

• Standalone: use LSAN_OPTIONS
• AddressSanitizer: use either LSAN_OPTIONS orASAN_OPTIONS
• HWAddressSanitizer: use either LSAN_OPTIONS orHWASAN_OPTIONS

For standalone LSan, exitcode=23 is the default. Theruntime calls an exit syscall with code 23 upon leaks. ForASan-integrated LSan, exitcode=1 is the default.

verbosity=1 prints some logs.

leak_check_at_exit=0 disables registering anatexit hook for leak checking.

detect_leaks=0 disables all leak checking, includinguser-requested ones due to __lsan_do_leak_check or__lsan_do_recoverable_leak_check. This is similar todefiningextern "C" int __lsan_is_turned_off() { return 1; } in theprogram. Using standalone LSan with detect_leaks=0 has aperformance characteristic similar to using pureSizeClassAllocator{32,64} and has nearly no extra overheadexcept the stack trace. If we can get rid of the stack unwindingoverhead, we will have a simple one benchmarkingSizeClassAllocator{32,64}'s performance.

If __lsan_default_options is defined, the return valuewill be parsed like LSAN_OPTIONS.

False negatives

There are several reasons that may cause false positives.

First, when LSan scans the root set, it finds aligned bit patternswhich look like a pointer to the allocator space. A integer/floatingpoint number may happen to have a similar bit pattern and tricksLSan.

Dangling pointers may trick LSan. The use_stacks=0section above gives an example. Let's see another example:

1
2
3
4
5
6
7
8
9
10

#include <vector>
std::vector<int *> *a;
int main() {
  a = new std::vector<int *>;
  a->push_back(new int[1]);
  a->push_back(new int[2]);
  a->push_back(new int[3]);
  a->pop_back();
  a->pop_back();
}

Issue suppression

The user can call __lsan_ignore_object to ignore anallocation. __lsan::ScopedDisabler is a RAII class forignoring all allocations in the scope. __lsan_disable canbe called to ignore all allocations for the current thread until__lsan_enable is called.

Here are some scenarios that we may want to ignore an allocation.

• a prebuilt library has a known leak
• the program performs a tagged pointer trick and makes a pointer nolonger look like a pointer to the allocation. E.g. LSan added built-in support forObjective-C runtime "camouflaging" pointers on macOS

The runtime scans each ignored allocation. An allocation reachable byan ignored allocation is not considered as a leak.

__lsan_register_root_region registers a region as aroot. The runtime scans the intersection of the region and valid memorymappings (/proc/self/maps on Linux).LSAN_OPTIONS=use_root_regions=0 can disable the registeredregions.

To use the above APIs, include the header#include <sanitizer/lsan_interface.h> first.

The runtime parses suppression rules from 3 sources:

• default suppressions (kStdSuppressions)
• if __lsan_default_suppressions is defined, its returnvalue
• user-specified LSAN_OPTIONS=suppressions=a.supp

A suppression file contains a rule per line, each rule being of theform leak:<pattern>. For a leak, the runtime checksevery frame in the stack trace. A frame has a module name associatedwith the call site address (executable or shared object), and whensymbolization is available, a source file name and a function name. Ifany module name/source file name/function name matches a pattern(substring matching using glob), the leak is suppressed.

Note: symbolization requires debug information and a symbolizer(internal symbolizer (not built by default) or anllvm-symbolizer in a PATH directory).

Let's see an example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

cat > a.c <<'eof'
#include <stdlib.h>
#include <stdio.h>
void *foo();
int main() {
  foo();
  printf("%p\n", malloc(42));
}
eof
cat > b.c <<'eof'
#include <stdlib.h>
void *foo() { return malloc(42); }
eof
clang -fsanitize=leak -fpic -g -shared b.c -o b.so
clang -fsanitize=leak -g a.c ./b.so -o a

which llvm-symbolizer  # available
LSAN_OPTIONS=suppressions=<(printf 'leak:a') ./a      # suppresses both leaks (by module name)
LSAN_OPTIONS=suppressions=<(printf 'leak:a.c') ./a    # suppresses both leaks (by source file name)
LSAN_OPTIONS=suppressions=<(printf 'leak:b.c') ./a    # suppresses the leak in b.so (by source file name)
LSAN_OPTIONS=suppressions=<(printf 'leak:main') ./a   # suppresses both leaks (by function name)
LSAN_OPTIONS=suppressions=<(printf 'leak:foo') ./a    # suppresses the leak in b.so (by function name)

Miscellaneous

Standalone LeakSanitizer can be used with SanitizerCoverage:clang -fsanitize=leak -fsanitize-coverage=func,trace-pc-guard a.c

The testsuite has been moved. Usegit log -- compiler-rt/lib/lsan/lit_tests/TestCases/pointer_to_self.cc(.cc instead of .cpp) to do archaeology forold tests.

I have a pending FreeBSD port https://github.com/MaskRay/llvm-project/tree/rt-freebsd-lsan.Wish that I will find some time to finish it.

Similar tools

Valgrind's Memcheck defaults to --leak-check=yes andperforms leak checking. The feature has been available since the initialrevision (git log -- vg_memory.c) in 2002.

Google open sourced HeapLeakChecker as part of gperftools. It is partof TCMalloc and used with debugallocation.cc.Multi-threading allocations need to grab a global lock and are muchslower than a sanitizer allocator(compiler-rt/test/lsan/TestCases/high_allocator_contention.cpp).heap_check_max_pointer_offset (default: 2048) specifies thelargest offset it scans an allocation for pointers. The default makes itvulnerable to false positives.

heaptrack is a heapmemory profiler which supports leak checking.