Memory API

2026-11-18 · virtualisation memory

notes / Operating Systems / 01_vir

OS

Interlude: Memory API

Types of Memory

stack memory is deallocated when you move out of the function call, to keep it permanent allocate on the heap

The stack is a simple runtime stack that's fairly easy to understand. The registers rsp and rbp are used to manipulate the stack. Stack operations are pretty much handled by the compiler and runtime, not much you can do.

The heap however is far more complex and interesting. The heap is a contiguous section of memory placed right after the .bss section or whatever. The contiguous heap is broken into chunks with some associated metadata, namely their size, 3 bit-flags, and forward and next pointers.

chunkey pandey

Free chunks are linked together in arrays of pointers called bins. When the heap needs to grow it does so with the mmap and brk/sbrk syscalls.

malloc()

argument is size_t use sizeof(), which is a compile-time operator. (compile-time -> operator, run-time -> function)

Note

C does not need you to cast the return of malloc back to the correct type, C++ does though

struct_t meow_t* cat = malloc(sizeof(struct meow_t*));

The malloc algorithm2

  1. If there is a suitable (exact match) chunk in the tcache (thread local cache) then return that chunk
  2. If the request is "very large" (above the mmap threshold M_MMAP_THRESHOLD) then more memory is mmap'ed and returned; else
  3. If the appropriate fastbin has a suitable chunk then return that
  4. If the appropriate smallbin has a suitable chunk then return that
  5. If still not found then sort thttps://sourceware.org/glibc/wiki/MallocInternalshe unsorted bin
    1. If the request is "large" then move chunks from the fastbin to the unsorted bin
    2. sort the unsorted bin by moving chunks into the smallbin and large bin, coalescing chunks together
  6. If the request is
    1. "large": search the large bin for a suitable chunk
    2. "small": search the fastbin (consolidate) and the smallbins again
  7. If still not found then split the top chunk (the largest chunk, identified with a separate pointer), possibly enlarging it beforehand

free()

int *x = malloc(10 * sizeof(int));
free(x);

The free algorithm

  1. If there is room in the tcache, store the chunk there and return
  2. If the chunk is small enough, place it in a fastbin
  3. If the chunk was mmap'd, munmap it
  4. If its adjacent to another free chunk, coalesce them together
  5. Place it in the unsorted bin (unless its the top chunk)

Common Errors3

1. Forgetting to Allocate Memory

char* src = "hello";
char* dst; // try char* dst = strdup(src);
strcpy(dst, src); // segfault and die (works on some machines tho)

2. Not Allocating Enough Memory

buffer overflow :) 4

3. Forgetting to Initialize Allocated Memory

uninitialized read, some garbage value

4. Forgetting to Free Memory

memory leak: this remains a problem even in modern languages because if you have a reference to useless memory somewhere it's not going to free on its own

5. Freeing Memory before you are Done with it

dangling pointer

6. Freeing Memory Repeatedly

double free: undefined

7. Calling free() Incorrectly

invalid free

Tip

valgrind and purify

Underlying OS Support

malloc and free are not syscalls, they are library calls. They make use of the brk and sbrk syscalls which change the location of a programs break i.e. the location of the end of the heap, so it can change the size of the heap

There is also the mmap syscall which can create an anonymous memory region associated with main memory space within your program (creates a physicalmem<->virtualmem map)

Other Calls

calloc() realloc()


  1. https://cs341.cs.illinois.edu/coursebook/Malloc memory allocator tutorial↩︎

  2. https://sourceware.org/glibc/wiki/MallocInternals malloc internals↩︎

  3. https://people.cs.umass.edu/~emery/pubs/pldi028-novark.pdf -> tips of memory management↩︎

  4. https://www.cs.cornell.edu/courses/cs5431/2011sp/readings/buffer_overflows_attacks_defenses.pdf↩︎