title: Linux Heap Fragmentation
body: <p>I have a question that keeps bothering me for the last week.</p>
  
  <p>In Windows debugger there is the <code>!heap -s</code> command that outputs the virtual memory's heap status and calculates the external fragmentation using the formula :</p>
  
  <pre><code>External fragmentation = 1 - (larget free block / total free size)
  </code></pre>
  
  <p>Is there a similar method in linux, that outputs those statistics needed to calculate the effect?</p>
  
  <p>Long story now:
  I have a C application that keeps allocating and deallocating space of different sizes, using malloc and free, each allocation has different life span.
  The platform I am using is Lubuntu, so <code>ptmalloc2</code> algorithm is the default.</p>
  
  <p>I am aware that those allocations are served in the virtual user space heap(except those that are larger than 128Kb, where the allocator uses <code>mmap</code>), and are mapped to physical pages when actually accessed .
  The majority of the allocations is of size &lt; 80 bytes, so they are served from FastBins.</p>
  
  <p>Using <code>Valgrind</code> and <code>Massif</code> I can get the internal fragmentation, since it reports the extra bytes used for each allocation.</p>
  
  <p>However, my main concern is how to figure out the external fragmentation. 
  I am aware of the <code>/proc/[pid]/smaps</code> heap size and the <code>pmap-d[pid] anon</code> statistics, but I find it difficult to interpret them in terms of external fragmentation.</p>
  
  <p>I am also aware of <code>LD_PRELOAD</code> , and I can dynamically connect the <code>/lib/i386-linux-gnu/libmemusage.so</code>. This library outputs the heap total, peak and the distribution of the requested allocation sizes.</p>
  
  <p>I know that <code>__malloc__hook</code> is deprecated now, and I do not really want to rely on implementation specific statistics like <code>malloc_stats()</code> and <code>mallinfo()</code> . However, If you have any suggestions using those two please let me know.</p>
  
  <p>I can tell that the external fragmentation problem, is when a request can not be satisfied, because there is no contiguous space in the heap, but the requested total size is scattered all around that area. </p>
  
  <p>I still have not figured out, how to get the statistics needed so I can calculate this effect. For example different formulas stating that I have to capture the <code>live_memory</code> or get the <code>total_free_pages</code>, or get the size of the <code>largest_free_block</code>. 
  How can I have a function to "traverse" through the heap and gather those statistics?</p>
  
  <p>Thank you everyone in advance. </p>