Basic understanding of the heap

Question

I want to learn more about what happens on the heap. So I look at the following C code. It basically just allocates memory on the heap for two variables:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char* argv[])
{
    char *char_ptr;
    int *int_ptr;
    int mem_size;

    if(argc < 2)
        mem_size = 50;
    else
        mem_size = atoi(argv[1]);

    printf("\t[+] allocating %d bytes of memory on the heap for char_ptr\n", mem_size);
    char_ptr = (char *) malloc(mem_size);
    if(char_ptr == NULL)
    {
        fprintf(stderr, "Error: could not allocate heap memory. \n");
        exit(-1);
    }

    strcpy(char_ptr, "This is memory located on the heap.");
    printf("char_ptr (%p) --> '%s'\n", char_ptr, char_ptr);

    printf("\t[+] allocating 12 bytes of memory on the heap for int_ptr\n");
    int_ptr = (int * ) malloc(12);
    if(int_ptr == NULL)
    {
        fprintf(stderr, "Error: could not allocate heap memory.");
        exit(-1);
    }

    *int_ptr = 31337;
    printf("int_ptr  (%p) --> %d\n", int_ptr, *int_ptr);

    printf("\t[-] freeing char_ptr's heap memory...\n");
    free(char_ptr);

    printf("\t[+] allocating another 15 bytes for char_ptr\n");
    char_ptr = (char *) malloc(15);
    if(char_ptr == NULL)
    {
        fprintf(stderr,"Error: could not allocate heap memory.\n");
        exit(-1);
    }

   strcpy(char_ptr, "new memory");
   printf("char_ptr (%p) --> '%s'\n", char_ptr, char_ptr);

   free(int_ptr);
   free(char_ptr);
}

The output for this code looks like this:

    [+] allocating 50 bytes of memory on the heap for char_ptr
char_ptr (0x8827008) --> 'This is memory located on the heap.'
    [+] allocating 12 bytes of memory on the heap for int_ptr
int_ptr  (0x8827040) --> 31337
    [-] freeing char_ptr's heap memory...
    [+] allocating another 15 bytes for char_ptr
char_ptr (0x8827050) --> 'new memory'

So I'm guessing char_ptr is pointing to the beginning of the allocated memory (0x8827008), right?

Since 50 bytes are allocated, the end of this memory should point at address 0x882702A. The next memory allocation is beginning at address 0x8827040. My question is: why is int_ptr NOT pointing to 0x882702B (the very next address after the first memory allocation)? Or in other terms: what is happening with memory in between 0x772702A and 0x8827040 ?

What makes you think it should point to the next address? `malloc` can allocate items wherever it wants; it's not a stack or bump allocator. — Colonel Thirty Two, Dec 20 '14 at 12:43
Standard Warning : Please [do not cast](http://stackoverflow.com/q/605845/2173917) the return value of `malloc()`. — Sourav Ghosh, Dec 20 '14 at 12:43

score 3 · Answer 1 · answered Dec 20 '14 at 12:45

The specifics depend on your C library (in turn depending on your operating system). There are two factors contributing to the phenomenon you are seeing:

Each memory block you get from malloc is prefixed with a header (often 16 bytes). However, malloc only returns a pointer point to after the header.
Each memory block must be aligned, to a multiple of the maximum alignment unit. Typically (depending on the microprocessor), the maximum alignment is 8 bytes. The bytes that are used to achieve the alignment are called padding.

As a consequence, the block that ends in ...2A gets padded up to ...30, then 16 bytes malloc header get added, and your next block starts at ...40.

score 2 · Accepted Answer · answered Dec 20 '14 at 12:48

malloc() doesn't necessarily allocate at the very next memory address. Here are some reasons why not:

malloc() is only guaranteed to return some allocated memory. How it works is up to malloc() - from an interface definition perspective, it's a black box. Working out what goes on inside may be interesting, but isn't part of the standard.
malloc() will align the allocations to convenient boundaries (normally 64 bit boundaries on a 64 bit platform).
Other library calls may have free()'d blocks before, so you get an allocation within a hole - i.e. within a previously free()'d block of memory.
The internal data structures that describe the heap immediately precede the allocate data structures. In a simple implementation, they would be a linked list.
malloc() gets its memory from multiple places; yes, it uses the heap (and brk/sbrk), but for larger allocations it will use mmap() with MAP_ANON.

All these factors may lead to the allocation not being at the 'very next memory address'.

paxdiablo · Answer 3 · 2014-12-20T12:50:50.053

Probably because the control information for the heap is stored inline.

In other words, each block may have a 'hidden' section just before it that contains the control information like block size, link to the next block, markers to detect corruption and so on.

It may also give you more memory than requested, such as ensuring it's a multiple of sixteen bytes (though you're still only allowed to use what you asked for).

Bottom line is, however, you can't rely on any of that. It may change for a different implementation, different version or the day on which your code is running :-)

All you can be sure of is what it states in the standards - it will give you NULL or a usable address which could be anywhere.

score 1 · Answer 4 · answered Dec 20 '14 at 14:12

Thank you everyone for your answer! They help a lot! I've had a fundamental missunderstandig of the heap's concept.

To summarize what have been said:

Besides the actual values there are "hidden" informations for each memory block
The heap doesn't necessary "string together" the individual memory blocks

Unfortunately I can't give anyone of you a vote up, since I'm not having 15 reputation. I hope you forgive me ;-)

Basic understanding of the heap

4 Answers4