title: Linux heap structure and the behaviour with malloc() and free()
body: <p>I have a Debian with a Linux 2.6 Kernel, and I try to understand how the heap works/behaves with <code>malloc()</code> and <code>free()</code>. I tried to search for <code>malloc()</code> and <code>free()</code> algorithm and heap structure, but I couldn't find anything helpful. And unfortunately, I know too less about Linux and how memory works, to understand the source code of <code>free()</code> and <code>malloc()</code>.</p>
  
  <p>This is an example code:</p>
  
  <pre><code>int main(int argc, char **argv)
  {
      char *a, *b, *c;
  
      a = malloc(32);
      b = malloc(32);
      c = malloc(32);
  
      strcpy(a, argv[1]);
      strcpy(b, argv[2]);
      strcpy(c, argv[3]);
  
      free(c);
      free(b);
      free(a);
  }
  </code></pre>
  
  <p>With <code>gdb</code> and <code>run AAAA BBBB CCCC</code> I can examine the heap. This is the state after the <code>strcpys</code> but before the <code>frees</code>:</p>
  
  <pre><code>(gdb) x/32x 0x804c000
  0x804c000:  0x00000000  0x00000029  0x41414141  0x00000000
  0x804c010:  0x00000000  0x00000000  0x00000000  0x00000000
  0x804c020:  0x00000000  0x00000000  0x00000000  0x00000029
  0x804c030:  0x42424242  0x00000000  0x00000000  0x00000000
  0x804c040:  0x00000000  0x00000000  0x00000000  0x00000000
  0x804c050:  0x00000000  0x00000029  0x43434343  0x00000000
  0x804c060:  0x00000000  0x00000000  0x00000000  0x00000000
  0x804c070:  0x00000000  0x00000000  0x00000000  0x00000f89
  </code></pre>
  
  <p>You can see the char arrays very good. Then I tried to figure out why there are <strong>0x29</strong> (dec 41). I would expect something like <strong>0x20</strong> (dec 32) or <strong>0x24</strong> (dec 36). </p>
  
  <ul>
  <li>Why does the malloc algorithm <em>wastes</em> this space?</li>
  <li>How is it decided that it is 0x29?</li>
  <li>And what does the <strong>0xf89</strong> at the end stands for? </li>
  <li>How does the program keep track on what's allocated and what is free?</li>
  </ul>
  
  <p>Especially I want to understand how <code>free()</code> works. After the three frees, the heap looks like this:</p>
  
  <pre><code>(gdb) x/32x 0x804c000
  0x804c000:  0x00000000  0x00000029  0x0804c028  0x00000000
  0x804c010:  0x00000000  0x00000000  0x00000000  0x00000000
  0x804c020:  0x00000000  0x00000000  0x00000000  0x00000029
  0x804c030:  0x0804c050  0x00000000  0x00000000  0x00000000
  0x804c040:  0x00000000  0x00000000  0x00000000  0x00000000
  0x804c050:  0x00000000  0x00000029  0x00000000  0x00000000
  0x804c060:  0x00000000  0x00000000  0x00000000  0x00000000
  0x804c070:  0x00000000  0x00000000  0x00000000  0x00000f89
  </code></pre>
  
  <ul>
  <li>Why is the char array replaced with this specific adress?</li>
  <li>What is the pseudo code what free does?</li>
  </ul>
  
  <p>Look at this example:</p>
  
  <pre><code>(gdb) run AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADDDDD BBBB CCCC
  ...
  (gdb) x/32x 0x804c000
  0x804c000:  0x00000000  0x00000029  0x41414141  0x41414141
  0x804c010:  0x41414141  0x41414141  0x41414141  0x41414141
  0x804c020:  0x41414141  0x41414141  0x44444444  0x00000044
  0x804c030:  0x42424242  0x00000000  0x00000000  0x00000000
  0x804c040:  0x00000000  0x00000000  0x00000000  0x00000000
  0x804c050:  0x00000000  0x00000029  0x43434343  0x00000000
  0x804c060:  0x00000000  0x00000000  0x00000000  0x00000000
  0x804c070:  0x00000000  0x00000000  0x00000000  0x00000f89
  ...
  (gdb) c
  Program exited with code 021.
  </code></pre>
  
  <p>I have overwritten the 0x29, but the program exits normally.
  But when I add another byte, I run into a Segmentation Fault:</p>
  
  <pre><code>(gdb) run AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADDDDD BBBB CCCC
  ...
  (gdb) x/32x 0x804c000
  0x804c000:  0x00000000  0x00000029  0x41414141  0x41414141
  0x804c010:  0x41414141  0x41414141  0x41414141  0x41414141
  0x804c020:  0x41414141  0x41414141  0x44444444  0x00004444
  0x804c030:  0x42424242  0x00000000  0x00000000  0x00000000
  0x804c040:  0x00000000  0x00000000  0x00000000  0x00000000
  0x804c050:  0x00000000  0x00000029  0x43434343  0x00000000
  0x804c060:  0x00000000  0x00000000  0x00000000  0x00000000
  0x804c070:  0x00000000  0x00000000  0x00000000  0x00000f89
  ...
  (gdb) c
  Program received signal SIGSEGV, Segmentation fault.
  0x080498b9 in free (mem=0x804c030) at common/malloc.c:3631
  </code></pre>
  
  <p>The most important question for me is:</p>
  
  <ul>
  <li>Why do you get a Segmentation fault in <code>free()</code> when you overwrite more bytes?</li>
  <li>and how does the <code>free()</code> algorithm work?</li>
  <li>and how do malloc and free keep track on the adresses?</li>
  </ul>
  
  <p>Thank you very much for reading,
  kind regards</p>