Heap management is an important component that affects program performance.

Need to balance: –

• Speed & performance of allocation/deallocation
• Memory utilization (reduce wasted areas)
• Ease of usage by the programmer

C Dynamic Memory Allocation

Functions from stdlib.h

• void *malloc(size_t size) – Allocates size bytes and returns a pointer to the block.

• void *calloc(size_t nmemb, size_t size) – Allocates nmemb*size bytes, sets the memory to 0, returns a pointer to the block.

• void free(void *ptr) function – Frees the block at address ptr (returned by malloc/calloc), returns it to the system for re-use by subsequent malloc calls.

Source Code :

Memory Map:

OS & the Heap

The OS kernel maintains the brk pointer.

• The virtual address of the top of the heap.
• Per process (threads share the heap).

brk pointer is updated via a system call (see Linux example below)

#include<unistd.h>

void *sbrk(intptr_t increment);

• Increments the brk pointer (up or down) and returns the old brk pointer on success.

• Newly allocated memory is zero-initialized.

• malloc/free allows the reuse of blocks allocated on the heap with sbrk.

intptr_t is a signed integer type that will match the size of pointers (32- or 64-bits)

A First Look at malloc :

The C-library implementation will provide an implementation to manage the heap.

At startup, the C-Library will allocate an initialize size of the heap via sbrk.

void *heap_init;

heap_init = sbrk(1 << 20); // 1 MB

 

• The C-library implementation will provide an implementation to manage the heap.
• At startup, the C-Library will allocate an initialize size of the heap via sbrk.
• Subsequent requests by malloc (or new) will give out portions of the heap.
• Calls to free or delete will reclaim those memory areas.

• The C-library implementation will provide an implementation to manage the heap.

• At startup, the C-Library will allocate an initialize size of the heap via sbrk.

• Subsequent requests by malloc (or new) will give out portions of the heap.

• Calls to free or delete will reclaim those memory areas.

If there is not enough contiguous free heap memory to satisfy a call to malloc/new then the library will use sbrk to increase the size of the heap.

When no memory exists, an exception or NULL pointer will be returned and the program may fail.

Allocators and Garbage Collection

An allocator will manage the free space of the heap•

Types: –

Explicit Allocator:

Requires the programmer to explicitly free memory when it is no longer used.

• Exemplified by malloc/new in C/C++.

Implicit Allocator:

Requires the allocator to determine when memory can be reclaimed and freed (i.e., known as garbage collection).

• Used by Java, Python, etc.