Archive Notes

1. malloc & heap allocation

3 min read

Heap allocation is entirely done by user-space processes, and the OS does not dictate how memory should be allocated within a process.

This is usually also abstracted using keywords such as new:

int[] n = new int[42]; // Java
int *pn = new int[42]; // C++

Both of these are equivalent to:

int *pn = malloc(42 * sizeof(int));

We want to understand malloc-like allocators as:

  • they do use the OS to get their memory (in page-sized chunks)
  • the OS kernel will internally have its own implementation of malloc for its own use
  • these allocators exhibit an instance of fragmentation
  • higher-level languages almost always include a malloc-like allocator

malloc() and free()

The OS only cares about pages and larger chunks of memory, while programs deal with smaller chunks. The job of the user-level memory allocator is then to divide up these smaller areas of memory from the ‘heap’ area.

Memory Allocator

A memory allocator works within one or more big blocks of memory (‘arenas’), and tracks which areas are free and which are used.

It may need to request more memory from the OS if the chunk is exhausted. It will need to be able to reclaim chunks when they become unused.

In modern language runtimes, a garbage collector may be provided which provides automatic reclamation of memory once variables fall out of scope. We are only considering manual memory management for the purpose of this.

Link to original

Example Implementation

For example, malloc(42 * sizeof(int)):

  • would find a free range of bytes we could take one of two approaches: first-fit, best-fit both have their drawbacks
  • takes bytes from said range
  • marks them as used
  • returns a pointer to their start

Meanwhile, free(pn) would mark the chunk as free. Marking the chunk as free involves recording this information into whatever data structure the malloc() implementation is using. A simple data structure is a free list which can be ‘threaded through’ the unallocated space.

Each free list node records:

  • the size of the free area
  • a pointer to the next free area

Growing Heap using System Calls

We are now in the situation where the heap is quite full and suffering fragmentation, a large request to malloc() would fail without asking for additional memory from the OS.

brk() syscall

One way we can allocate more memory is by asking the OS to move the program break and hence request more pages from the OS.

// system call to ask for 100 more pages
int ret = brk((char*) crubrk + 100 * PAGE_SIZE);

This will not necessarily allocate more physical memory but will allocate more virtual memory to the process if possible.

brk:
	mov $0xc, %eax         ; syscall 12
	syscall
	
	cmp $-0x1000,%rax      ; small negative result is an error
	ja error_returned
	
	mov __curbrk, %rcx     ; current brk is cached by libc
	mov %rax, (%rcx)       ; update the cache
	
	cmp %rax, %rdi         ; check if we received less than we asked for
	ja less_than_requested
	
	xor %eax, %eax         ; clear eax on success
	retq
 
error_returned:
	[..]
 
less_than_requested:
	[..]

mmap() syscall

A modern OS would provide a more flexible way to allocate more memory which doesn’t care about where the program break is.

void *ret = mmap(
	NULL,
	100 * PAGE_SIZE,             // allocate 100 pages
	PROT_READ | PROT_WRITE,      // specify permissions
	MAP_PRIVATE | MAP_ANONYMOUS, // additional flags
	-1,
	0
);

A malloc() impl might use this and end up with non-contiguous arenas, though this is not a problem as we can still extend our free list. An efficient malloc() would not use just a single free list either.

malloc performance

We measure a bunch of different signals per workload, “(program, input) pair”, including how fast allocation and freeing is, how much external and internal fragmentation appears.

External fragmentation can be measured in bytes as the difference between the total space we have free (across all arenas) and the biggest contiguous chunk we can allocate.

malloc concurrency

A free list, or other data structure, must be concurrent as malloc can be called by many threads at once.

InfOS uses dlmalloc for allocating chunks for the kernel’s own use.

Graph View