Dynamic Memory - tnballo/notebook GitHub Wiki

References:

1. Bryant, Randal E, and David R. O'Hallaron. Computer Systems: A Programmer's Perspective. Pearson, 2015. Print.

---

• Dynamic Memory Allocators - used by applications to allocate and free chunks of virtual memory maintained in the heap. For data structures whose size is only known at runtime.

  • Explicit Allocator - application explicitly allocates and frees the memory, ex. malloc and free in C.

  • Implicit Allocator - application allocates memory, but doesn’t have to free, ex. garbage collection in Java.

  • Allocator constraints:

    1. Can’t control the size of allocated blocks.

    2. Must respond to malloc requests immediately (i.e. can’t re-order or buffer requests).

    3. Must allocate blocks from free memory (implication: no movement or compaction of blocks, once it’s been allocated it’s place is fixed).

    4. Must align blocks to satisfy alignment requirements (8-byte for x86, 16-byte for x86-64).

  • Throughput vs utilization tradeoff - allocator design decisions are a tradeoff between speed (throughput, number of completed requests per unit of time) and space (peak memory utilization, measure of how effectively the allocator uses the heap, ratio of payload bytes to total bytes used with overhead included).

• Fragmentation - inefficiencies in memory utilization. Some are unavoidable, others can be decreased with good allocation strategies.

  • Internal fragmentation - for a given block, the payload is smaller than the block size. Can be caused by padding for alignment, overhead data structures (headers, footers, etc), or explicit policy decisions (ex. Setting a minimum size to avoid splintering). Depends only on the pattern of previous requests, easy to measure.

  • External fragmentation - occurs when there is enough free memory in the heap to satisfy a request, but no single free block is large enough to satisfy the request. Since the allocator can’t move blocks, it has to request more virtual memory and extend the heap. Depends on future requests, difficult to measure.

• Garbage collection (implicit memory management) - automatic reclamation of heap-allocated storage, the application never has to explicitly free. If there are no pointers to a block it can never be referenced again, it’s essentially “orphaned”, and can be considered garbage.

  • Why accurate garbage collection isn't possible in in C - the memory manager would have to be able to distinguish pointers from non-pointers, all pointers would have to point to the start of a block, and pointers would have to be static (no casting pointer-to-non-pointer or vice versa).

    • In C you can only implement “conservative” garbage collectors. You need to check if a word is a pointer by checking if it points to an allocated block in memory. Sometimes is will by coincidence, say an integer values that just happens to be the same as the address of an allocated block. That’s OK, it just means some non-reachable blocks will be treated as reachable and not all garbage will be collected. This is inefficient, but does not break functionality.

  • Garbage collectors view memory as a graph, each node is a block and each edge is a pointer to a block. Root nodes contain pointers into the heap but are not part of the heap (ex. In registers or the stack). A block (node) is reachable is there is path from a root node to the block. Non-reachable nodes are garbage.

  • Mark and sweep garbage collection - an old, simple algorithm. Marking involves starting at all the roots and traversing the set of reachable nodes, setting the mark bit. The sweep through the entire heap and free any allocated blocked that isn’t marked (since that implies they're unreachable, garbage).

---

• Free lists - a mechanism to keep track of free blocks:

  • Implicit free list - put a header in front of every block in the heap, allocated or free. Since the header marks a block as either free or allocated, you can traverse all free blocks in a heap by traversing all blocks. Implicit since there’s no separate listing of free blocks.

  • Explicit list - use some of the words in a free block to store pointers, creating a single or doubly linked list. This is creates more efficient traversals.

  • Segregated free list - have multiple free lists, each containing blocks of different sizes or different ranges of sizes.

  • Balanced tree free list - use a balanced tree, ex. A red-black tree, with pointers within each free block, and the length used as a key.

  • Allocation policy - strategies for finding a suitable free block:

    • First fit - search from beginning, choose first block that can fit a request. Linear time, but can cause splinters at the start of the list.

    • Next fit - like first fit, except start where previous block finished. A little faster then first fit, but can have worse fragmentation.

    • Best fit - search entire list and find the fit that results in the fewest bytes left over. Keeps fragmentation small, improves memory utilization, but will have a slower runtime then first fit. If you’re using a segregated freelist approach, the more lists you use the closer you’ll approximate best-fit.

  • Free List Insertion policy - where in the free list should a newly freed block go?

    • LIFO (last-in-first-out) policy - insert it at beginning, simple and fast (constant time) but prone to fragmentation.

    • Address-ordered - insert so that it’s always address sorted: addr(prev) < addr(curr) < addr(next). Requires search (linear time) but has lower fragmentation the LIFO.

• Explicit vs implicit list - allocation time is linear relative to number of free blocks instead of all blocks (much faster when memory is full). More complicated allocation since you need to splice blocks in/out of list, also extra overhead for pointers

• Splitting - since allocated space might be smaller than free space, we might want to split a block. Fill the first portion of the block to satisfy the request, then convert the remainder into a new free block.

  • It’s extremely important to coalesce blocks, if portions of a split block both become free, we want to ensure that those contiguous portions are coalesced into a single free block. Otherwise the allocator will fail to satisfy requests it has enough space for.

    • Immediate Coalescing - coalesce each time free is called.

    • Deferred Coalescing- try to improve free performance by deferring coalescing until a later time, such as when you scan free lists for malloc requests or when external fragmentation reaches a threshold.

• Boundary tags - replicate the header block at the end of a block, creating a footer. This requires extra space but allows us to traverse the “list” backwards - given a pointer to the header of any block, looking one word back gives the size and allocation status of the previous block. This is important for coalescing.

  • Keep in mind that when you’re looking for a block that satisfies a request, you now have to factor in the size of headers and footers, in addition to any padding you might need.

  • Optimization: since footers are only needed in coalescing, only use footers for free blocks, not allocated blocks. This reduces internal fragmentation. We can use one of the 3 free bits (assuming 8-byte aligned blocks) in any given block to store the allocation status of the previous block, so we can still tell if a previous block is allocated/free whether or not it has a footer.

• Segregated list in practice - each class of block sizes has it’s own free list, can be a specific size or a range of sizes. Typically you’d use single byte increments for the first couple of sizes, and power of 2 range classes beyond that.

  • Example allocator design - for high throughput (log time for power-of-two classes) and good memory utilization, first fit search of segregated lists approximates a best-fit search of the entire heap. Dedicated (non-range) block sizes are best fit.

  • Block allocation algorithm - identify the appropriately sized free list, search for a free block in that list. If found place the block, split the remain space , and insert the split result into the appropriate class free list. If no block found, try the next largest sized class list until a block is found. If all classes searched and no match, call for more memory by calling sbrk.

  • Block freeing algorithm - to free a block, first coalesce and then insert in the appropriate class list.

• Any 8-byte aligned block will always have the 3 low-order bits set to zero (makes sense conceptually, the bit encoding of your number is a multiple of 8). Thus, these bits can be used for allocation overhead information. The last bit typically denotes allocation status (1 = allocated, 0 = free).

• Prologue and Epilogue blocks (think of them as special overhead bytes at the beginning and end of a heap) eliminate the the need to check for edge cases when coalescing. The epilogue blocks also marks the end of the free list.