Memory Fragmentation Profiler

Question

Are there any good memory fragmentation profilers? (linux gcc version would be nice). Valgrind cannot analyze this because it uses custom malloc/free functions.

Thanks, Andrew

Brooklynese

You could just use gdb or another debugger. – Jobe

using gdb to walk through and produce a profile of the entire memory buffers managed malloc is NOT feasible. – Thebes

Answer 1

I would start with mtrace. When you have a trace, glibc comes with a perl script mtrace(1) which finds leaks. However, the trace format is easy to understand, so it should be straight-forward process this into fragmentation analysis.

Fazio

Answer 2

I'm afraid the answer is Valgrind.

You can tell Valgrind which functions are used to make allocations and how it does it using valgrind extensions to code (so you need to modify and recompile your application, but the changes compile to noops if you're not debugging), the details are in Valgrind manual Memory pools: working with custom allocators.

Once you've done this, you have two tools that allow you to diagnose your heap usage: massif and DHAT (quick reminder, Valgrind is a set of tools, it just runs the one we all know and love, Memcheck, as default).

Massif "is a heap profiler. It measures how much heap memory your program uses. This includes both the useful space, and the extra bytes allocated for book-keeping and alignment purposes. It can also measure the size of your program's stack(s), although it does not do so by default."

It can create "graphs", so it is kind of graphical:

19.63^                                               ###                      
     |                                               #                        
     |                                               #  ::                    
     |                                               #  : :::                 
     |                                      :::::::::#  : :  ::               
     |                                      :        #  : :  : ::             
     |                                      :        #  : :  : : :::          
     |                                      :        #  : :  : : :  ::        
     |                            :::::::::::        #  : :  : : :  : :::     
     |                            :         :        #  : :  : : :  : :  ::   
     |                        :::::         :        #  : :  : : :  : :  : :: 
     |                     @@@:   :         :        #  : :  : : :  : :  : : @
     |                   ::@  :   :         :        #  : :  : : :  : :  : : @
     |                :::: @  :   :         :        #  : :  : : :  : :  : : @
     |              :::  : @  :   :         :        #  : :  : : :  : :  : : @
     |            ::: :  : @  :   :         :        #  : :  : : :  : :  : : @
     |         :::: : :  : @  :   :         :        #  : :  : : :  : :  : : @
     |       :::  : : :  : @  :   :         :        #  : :  : : :  : :  : : @
     |    :::: :  : : :  : @  :   :         :        #  : :  : : :  : :  : : @
     |  :::  : :  : : :  : @  :   :         :        #  : :  : : :  : :  : : @
   0 +----------------------------------------------------------------------->KB     0                                                                   29.48

Number of snapshots: 25
 Detailed snapshots: [9, 14 (peak), 24]

What's more, there's a Massif Visualizer that is produces really pretty graphs.

DHAT allows you to diagnose how exactly the application uses its heap, which parts are short lived, which are kept through whole program's life, but used only in the beginning, etc. Unfortunately it doesn't have any nice graphs or graphical tools that go with it, the output is pure text. Thankfully you can tell it how much data you want to get and how to sort it so it's not as bad as it sounds.

Voyeurism

Answer 3

I have trouble understanding how any tool you might find would understand the segment data structures of your custom memory management. You might be able to get the busy distribution(hooking into malloc/free) but the free distribution (which essentially is the fragmentation) seems up in the air.

So why not add busy/free statistics/histograms to your custom memory manager. If bins are indexed by something proportional to log2(size) its O(1) to keep these statistics as when you split and coalesce you know the sizes and you can find the bin by direct lookup using an index proportional to log2(size)

eg histogram bin intervals

[2^n,2^(n+1) ) ...

(eg if you want finer bins use log base square root 2(size) which can be calculated with 4 integer instructions on x86 [bit scan, compare, set, add])

another set of reasonable bin sizes to use are the following open intervals

[2^n, 2^n+2^(n-1) ),[2^n+2^(n-1),2^(n+1) )...

again easily calculable [bit scan, shift, and, add])

Stagecoach

He doesn't mention a custom allocator. It's not that far fetched that someone e.g. wrote a tool that could walk the internal structures of the glibc allocator on linux. – Thebes

then what does "custom" in "custom malloc/free functions" mean? – Stagecoach

The 'custom' refers to valgrind - it would be silly for valgrind to measure malloc fragmentation as valgrind replaces default allocator (You want to measure the real allocator, not the one valgrind hooked in) – Thebes

Answer 4

nedmalloc is a very good custom allocator, comes with source, optimized to avoid fragmentation.

I would plug that in, and start looking at its internal logging for fragmentation statistics.

Kepler

nedmalloc looks like a great way to speed up the program, but it doesn't come close to solving fragmentation profiling problem without lots of work. Thanks for the info, I'm seriously considering switching to it. – Brooklynese

The idea was that a) nedmalloc handles fragmentation well, so its less of an issue, b) it has built in tuning and source code, so you can roll your own analysis with far more detailed introspection than something like mtrace. – Kepler