Skip to content

Index

Allocation Types: * Static * Layout is known at compile time * No runtime allocation * Fixed size data structures * No recursion * Stack * Allows recursion * Automatic stack allocation * Fixed size data structures * Stack overflow - once runtime allocation is introduced, the robustness is decreased * Heap * Any chunk pass around (callee -> caller) * Consume memory only when needed * Variable size data structures * Memory leak and dangling pointers -- forgot to free an object or free too early

Memory Layout

  • process memory

First the code is loaded at the very code -- this are the byte code Data segment - initialized data known at compile time BSS - uninitialized data

Command line argument/ Env variables are stored at the top of the stack Stack are used for recursive function calls, as a storage for local variable, and parameters via stack frame - Stack allocation are automatic for higher level languages like C and all.

Heap is used for dynamic memory allocation, when callee's allocated data outlives caller's activation

Memory mapping segment- maps virtual memory of the process to physical memory addresses. -- this is done by MMU (memory management unit)

These are segment lie together in virtaul memory space. They are not contiguous in physical memory. Operating system may provide a virtual address space that is larger than the physical memory available on the computer. It may also allocate more memory to heap than the physical memory (RAM) available. This is called swap memory.

Mutator, Collector and Allocator

Mutator - the main User program -- creates objects through allocator Allocator - allocate memory for objects. Handles dynamic memory requests Collector - reclaims memory, preserves Mutator View

Mutator and Collector communication -- "Stop the world" - the state of the Mutator is put when the Collector starts its work; all the threads of the mutator are blocked.

Allocators

  • bump allocator -- simple increase the allocator pointer, leaving the garbage behind.
    • Example: Mark and Compact GC, Copying GC, Generational GC
  • free list allocator -- reused the freed block of memmory, tracking them in a linked-list data structure.
    • Example: Reference Counting GC, Mark and Sweep GC, Manual
    • Strategies: First fit, next fit, best fit, segregated fit

GC Types: 1. Tracing - we find all the live objects in the heap and mark them as live and the rest as dead. Then we delete the dead objects. 2. Direct Collector - we keep track of the number of references to an object. When the reference count reaches 0, we delete the object.

GC Algorithms: 1. Mark and Sweep - Tracing 2. Mark and Compact- Tracing 3. Copying GC - Tracing 4. Reference Counting - Direct collector

Mark and Sweep

Type: Tracing

Two phases: 1. Mark - trace for live objects 2. Sweep - reclaim the garbage

  • Non-moving collector - objects stay at the same location after GC
  • Allocation - Linked list of "free block" of memory: slower allocation
  • Issues: Fragmentation - next free block might be in a different location: bad cache locality

Mark and Compact

Type: Tracing

Two phases: 1. Mark - trace for live objects 2. Compact - move live objects to the beginning of the heap

  • Moving collector - objects move to a new location after GC This means it can't be used by languages exposing pointer semantics (C, C++, Rust)
  • Allocation - bump pointer: faster allocation
  • Issues - upto 3x heap traversal, 2x memory usage

Copying GC

Type: Tracing

Two heaps: 1. From space - where objects are allocated 2. To space - where objects are copied to

Four phases: 1. Copy - evacuate live objects from from space to to space 2. Forward - keep forwarding address 3. Fix pointers - update child reference 4. Swap - swap the two heaps

Moving collector - objects move to a new location after GC Allocation: bump pointer Issues: reserved half of the heap

Reference Counting

Type: Direct collector

Two phases: 1. Increment/Decrement - increment reference count when a reference is created 2. Update (Recursively)

Moving collector - Nope

Allocation: Free list (slow) Issues: Cant handle cycles - memory leak

Next time: we will discuss more advance garbage collector which doesn't block the mutator.