Content

  1. Dynamic Memory Allocation
    1. Memory Allocator
    2. Performance Goals
    3. Fragmentation
    4. Implementation
    5. Garbage Collection
  2. Memory-Related Bugs

Dynamic Memory Allocation

Memory Allocator

  • Explicit memory allocator: malloc & free
  • Implicit memory allocator: garbage collection
  • Provides abstraction of memory as a set of blocks
  • Constraints
    • Alignment
    • No compaction on allocated blocks
    • Only manipulate free memory
  • Goal
    • Good time performance for malloc & free
    • Good space utilization
    • Good locality properties
      • Allocation close in time should be close in space

Performance Goals

  • Throughput: # of completed requests per unit time
  • Peak memory utilization
    • Aggregate payload Pk
    • Current heap size Hk
    • Peak memory utilization Uk = (max_i<k Pi) / Hk

Fragmentation

  • Internal fragmentation
    • Depends on pattern of previous requests
  • External fragmentation
    • Depends on pattern of future requests

Implementation

| size | a | - header
| payload  |
| padding  |
| size | a | - footer
  • Keep track of size
    • Overhead: size + allocated bit
  • Keep track of free blocks
    1. Implicit list: length to link all blocks
    2. Explicit list: pointers to link free blocks
    3. Segregated free list
    4. Blocks sorted by size

Implicit List

  • Placement policy
    • First fit
    • Next fit: fragmentation worse
    • Best fit: slower
  • Coalescing policy
    • Join adjacent free blocks
    • Immediate coalescing
    • Deferred coalescing
      • Until malloc or external fragmentation reaches threshold

Explicit Free List

  • Extra data space for link pointers
  • Need boundary tags for coalescing
  • Insertion policy
    • LIFO
    • Address-ordered

Segragated Free List

  • Each size class has own collection of blocks
    • Separate size class for small sizes
    • Typically size classes for power of 2

Garbage Collection

Mark and Sweep Collecting

  • Mark: scan over blocks, mark all reachable memory
  • Sweep: scan over blocks, free blocks not marked
  • Dereferencing bad pointers
    • scanf("%d", val)
  • Reading uninitialized memory
  • Overwriting memory
    • Allocating wrong sized object
    • Off-by-one error
    • Not checking max string size
    • Referencing a pointer instead of the object it points to: *size--
    • Pointer arithmetic: p += sizeof(int)
  • Referencing nonexistent variables
    • Return pointer to local variable
  • Freeing blocks multiple times
  • Referencing freed blocks
  • Failing to free blocks

results matching ""

    No results matching ""