Dynamic Memory Allocation Overview

Dynamic Memory Allocation Free-Space Management e.g., malloc() CSAPP Book Chapter 9.9 Instructor: Haryadi Gunawi REAL EXAMPLES / NUMBERS A lot of code. Please just follow the illustration. Digest the code later. NOTE: The slides that are marked with the above label are slides with real examples/numbers. Slides that don t have the label only focus on the high-level concepts (conceptual numbers for illustrations only). CMSC 15400 1

int main() { int *p = malloc(4); int *q = malloc(4); int *r = malloc(4); Logical View 2^n Stack printf( p points to %08x \n", p); printf( q points to %08x \n", q); printf( r points to %08x \n", r); } // Run in CSIL linux.cs.uchicago.edu (unused) Q1: How does malloc() decide what address to return? R = 0160f050 50 Heap Q = 0160f030 30 Q2: Why is there a gap? P = 0160f010 10 0x50 -- 0x30 = 0x20 bytes = 32 bytes (but I asked for 4 bytes) (all hex numbers) Code 0 CMSC 15400 2

2^n Stack (Horizontal view of the heap) (unused) P = 0160f010 R = 0160f050 Heap Q = 0160f030 Start of heap Code 0 CMSC 15400 3

Assumptions Made in This Lecture [IMPORTANT!!] Memory is word addressed A box = a word = integer size = 4 bytes In lecture: malloc(X) means malloc (X words), i.e., malloc (X * 4 bytes) In actual C code: malloc(Y) means Y bytes A block = a sequence of words allocated by malloc() 1 word (4 bytes) An allocated block (4 words) A free block (3 words) Free word Allocated word 16 bytes 12 bytes CMSC 15400 4

Allocation Example p1 = malloc(4) An allocated block p2 = malloc(5) Another allocated block p3 = malloc(6) free(p2) A free block Another free block p4 = malloc(2) CMSC 15400 5

How to manage free blocks? Method 1: Implicit list using length links all blocks Method 2: Explicit list among the free blocks using pointers CMSC 15400 6

Outline Basic concepts Implicit free lists CMSC 15400 7

Managing free and allocated blocks Need block headers Keep the size and status (free/allocated) of a block in the word preceding the block. This word is often called the header fieldorheader Requires an extra word for every block p0 = malloc(4) 5 block header payload A free block CMSC 15400 8

Method 1: Implicit List For each block we need both size and allocation status p1 = malloc(4) a Payload Size 1 word p1 a = 1: Allocated block a = 0: Free block a Size An allocated block Size: block size (in bytes) Payload Format of allocated and free blocks: Payload: application data (in allocated blocks only) CMSC 15400 9

Detailed Implicit Free List Example Unused Start of heap 8/0 16/1 32/0 16/1 byteSize=8 / alloc=0 P=malloc(3 words) Q=malloc(3 words) Allocated blocks: shaded Free blocks: unshaded Headers: labeled with size in bytes/allocated bit REAL EXAMPLES / CMSC 15400 NUMBERS 10

Forms an implicit list Unused Start of heap 8/0 16/1 32/0 16/1 Word#: 0 1 1 2 3 4 5 6 7 7 8 9 10 11 13 15 16 17 Implicit List of Free blocks Pos: w0 Sz: 8 bytes Pos: w6 Sz: 32 bytes Does malloc() management suffer from internal or external fragmentation? CMSC 15400 11

Outline Basic concepts Implicit free lists How to find a free block? Which free block to return? Policies: Best fit Worst fit First fit Next fit CMSC 15400 12

Best fit Best fit: Search the list, choose the fully-fit or with fewest bytes left over Example: malloc (15 bytes) There are 3 free blocks Return which block? (for simplicity of illustration, the size below does not include header size) Implicit List of Free blocks Pos: .. Sz: 5 Pos: .. Sz: 20 Pos: .. Sz: 10 Pos: .. Sz: 30 For simplicity, these sizes (E.g. 30 bytes) exclude the 4-byte header. e.g. sizeInSlide = header.size 4; Cons: (-) Slow (must iterate through all free blocks) (-) Leftover blocks are small (a lot of small holes in long runs) CMSC 15400 13

Worst fit Worst fit: Search the list, choose the largest free block Example: malloc (15 bytes) Return which block? Pos: .. Sz: 15 Implicit List of Free blocks Pos: .. Sz: 20 Pos: .. Sz: 10 Pos: .. Sz: 30 Cons: (-) Slow (must iterate through all free blocks) Pros: (+) Keep leftover blocks large (for future allocations) CMSC 15400 14

First fit First fit: Search list from beginning, choose first free block that fits Example: Malloc(15 bytes) Return which block? Pos: .. Sz: 15 Implicit List of Free blocks Pos: .. Sz: 20 Pos: .. Sz: 10 Pos: .. Sz: 30 Pros/cons: (+) Faster than best/worst fit (-) Still slow: can take linear time in total number of blocks (allocated and free) Most early parts of the heap have been allocated CMSC 15400 15

Next fit Next fit: Like first fit, but search list starting where previous search finished Example: Malloc(15 bytes), return which one? Malloc(10 bytes), return which one? Pos: .. Sz: 10 Pos: .. Sz: 5 Implicit List of Free blocks Pos: .. Sz: 20 Pos: .. Sz: 20 Pos: .. Sz: 10 Say, last search ends here Pros: (+) Faster than first fit: avoids re-scanning un-fit blocks CMSC 15400 16

Policies Which policy should I use? Depends No single best policy for all workloads Must know your customer s malloc()/free() patterns In systems, best performance is based on experimental research / empirical evaluation (not theoretical) CMSC 15400 17

Outline Basic concepts Implicit free lists Details of allocating/freeing For SIMPLICITY of illustration, in the following slides, we will *not* show the block header CMSC 15400 18

Allocating in Free Block Allocating in a free block: splitting Since allocated space might be smaller than free space, we might want to split the block 4 4 6 2 malloc(4 words) p A free block 2 4 4 4 2 A new free block A new allocated block CMSC 15400 19

Freeing a Block Simplest/na ve implementation: Need only clear the allocated flag bit from 1 0 4 4 4 2 2 p free(p) 4 4 4 2 2 1 0 Size = 4w Payload (3 words) But can lead to false fragmentation Malloc(5)? error! Oops! There is enough free space, but the allocator won t be able to find it (or must check the next block more complex) CMSC 15400 20

Freeing and Coalescing Join (coalesce) with next/previous blocks, if they are free Coalescing with next block 4 4 4 2 2 p logically gone free(p) 4 4 6 2 2 CMSC 15400 21

Coalescing But how do we coalesce with previous block? 4 4 4 2 2 p How to merge with this free block? free(p) Must iterate from beginning?? O(N), not O(1)/constant-time ?? No, we use back pointer to previous block The problem so far: single, one-directional linked list. Must use: bi-directional linked list CMSC 15400 22

Bidirectional Coalescing Boundary tags[Knuth73] Add block footer: replicate block header at bottom (end) of free blocks Allows us to traverse the list backwards 4 4 4 4 6 6 4 4 a a Payload Format of allocated and free blocks Size Size REAL EXAMPLES / NUMBERS (in words Boundary tag (footer) Header CMSC 15400 Not bytes) 23

Constant Time Coalescing Case 1 Case 2 Case 3 Case 4 Allocated Allocated Free Free p p Block being freed free(p) Allocated Free Free Allocated (FYI, above is a reversed vertical view of the heap) Bottom block means right neighbor. Top block means left neighbor. CMSC 15400 24

Coalescing or not (Case 1)? is it Case 1? 1 word Wordline Pos: p-2words p-8bytes This is called Pointer arithmetic m1 1 allocated block // inside free(p) implementation m1 1 // get the wordline prevFoot = (void*) p 8; nextHead = (void*) p 4 + n; (real C code) n 1 free (p) n 1 m2 1 // get the allocation bit isPrevAlloc = *prevFoot & 1UL; isNextAlloc = *nextHead & 1UL; allocated block m2 1 if (isPrevAlloc == true && isNextAlloc == true) it is case1 !! Wordline Pos: p - 1 word + n bytes p 4 bytes + n bytes REAL EXAMPLES / CMSC 15400 NUMBERS 25

Coalescing (Case 1) 1 word m1 1 m1 1 Must Modify: allocated block m1 1 m1 1 Your Head n 0 n 1 free (p) Your Foot n 0 n 1 m2 1 m2 1 allocated block m2 1 // get the wordline of P s head myHead = (void*) p ???; myFoot = (void*) p + ???; m2 1 Becomes an unallocated block // clear the allocated bit *myHead &= ~ 1UL; *myFoot &= ~ 1UL; REAL EXAMPLES / // ~1 UL 111 1110 CMSC 15400 NUMBERS 26

Coalescing (Case 2) m1 1 m1 1 allocated Modify: m1 1 m1 1 n+m2 0 n 1 Your Head free (p) n 1 m2 0 Non- allocated Right s Foot n+m2 0 m2 0 CMSC 15400 27

Coalescing (Case 3) Modify Left s Head m1 0 n+m1 0 Non-allocated m1 0 n 1 free (p) Your Foot n 1 n+m1 0 m2 1 m2 1 Allocated m2 1 m2 1 CMSC 15400 28

Coalescing (Case 4) Modify Left s Head m1 0 n+m1+m2 0 Non-allocated m1 0 n 1 free (p) n 1 m2 0 Non-allocated Right s Foot m2 0 n+m1+m2 0 CMSC 15400 29

Outline Basic concepts Implicit free lists Explicit free lists (built on top of implicit free lists, i.e., you still need implicit lists, but explicit will make find-free-holes much faster) CMSC 15400 30

Disadvantages of implicit free list? Why traverse the allocated blocks to find a free block?? Waste of time!! Method 1: Implicit free list using length links all blocks Malloc(5) Not fit, Go next Allocated, Go Next Fit! 4 4 6 2 Method 2: Explicit free listamong the free blocks using pointers No need to hop to allocated blocks Not fit, Go to next free Fit! 4 4 6 2 CMSC 15400 31

Block format Payload is unused anyway. Let s add it with more info Allocated block (same as before) Free block Size 1 Size 0 Next free addr Important note: These are pointers to prev/next free blocks (explicit) Prev free addr Payload Size 1 Size 0 They are not sizes (implicit) Maintain list(s) of free blocks ( not all blocks) Goal of malloc() is to manage free space, so it s about the free list Luckily we track only free blocks, so we can use payload area REAL EXAMPLES / CMSC 15400 NUMBERS 32

Explicit Free Lists Double linked list of free blocks (logical view) With explicit pointers Forward (next) links 4 4 4 4 6 6 4 4 4 4 Back (prev) links CMSC 15400 33

Explicit Free Lists Logically: 6 words Free (C) 4 words Free (A) 4 words Free (B) Physically: free blocks can be linked in any order (Explicit pointers allow different orderings of free blocks) More powerful Forward (next) links A B 4 4 4 4 6 6 4 4 4 4 C Back (prev) links CMSC 15400 34

Allocation (and splitting) conceptual graphic Before A free block After (with splitting) allocated P = malloc( ) CMSC 15400 35

Freeing? Free-block insertion policy: Where in the free list do you put a newly freed block? One possible policy: LIFO (last-in-first-out) Insert a newly freed block at the beginning of the free list CMSC 15400 36

Freeing With a LIFO Policy (Case 1) Before Points to the head of the free list free( ) Root Insert the freed block at the root of the list After Root FYI, the back pointer here is just for illustration. It looks wrong because back pointer actually should always point to the first word of a block, not the last word. CMSC 15400 37

Freeing With a LIFO Policy (Case 2) Next adjacent block is also free Before free( ) Root Splice out successor block, coalesce both memory blocks and insert the new block at the root of the list After Root CMSC 15400 38

Freeing With a LIFO Policy (Case 3) conceptual graphic Before free( ) Root Previous adjacent block is also free After Root CMSC 15400 39

Freeing With a LIFO Policy (Case 4) conceptual graphic Before free( ) Root Both adjacent blocks are free Splice out predecessor and successor blocks, coalesce all 3 memory blocks and insert the new block at the root of the list After Root CMSC 15400 40

Free-block Insertion policy LIFO Pro: simple and constant time Con: studies suggest fragmentation is worse than address ordered But other policies are possible (see book if you re interested) CMSC 15400 41

Other Free-space management solutions (FYI only) Method 3: Segregated free list Different free lists for different size classes Method 4: Blocks sorted by size Can use a balanced tree (e.g. Red-Black tree) with pointers within each free block, and the length used as a key CMSC 15400 42

Regarding padding (FYI) The book describes padding inside a block, which is not necessary in this class This class assumes a 1-word alignment The book describes a 2-word alignment Why is padding / alignment needed? Depends on unit of memory line (low-level DRAM property) Aligned 1 line access No-aligned 2 lines accesses worse performance 2 words My data is here P 0x 04 In 2-word alignment: Returned pointer by malloc must be 8-byte aligned Ex: 0x 00, 08, 10, 18, E.g. the last 3 bits of the pointer must be always 000 | My data Is here | CMSC 15400 43

EXTRAS Basic concepts Implicit free lists Explicit free lists EXTRA: CMSC 15400 44

Constraints Applications Can issue arbitrary sequence of malloc and free requests free request must be to a malloc d block A low-level memory management (Unlike high- level data structures) Allocators Can t control number or size of allocated blocks Must respond immediately to mallocrequests i.e., can t reorder or buffer requests Must allocate blocks from free memory i.e., can only place allocated blocks in free memory Must align blocks so they satisfy all alignment requirements 8-byte (x86) or 16-byte (x86-64) alignment on Linux boxes Can manipulate and modify only free memory Can t move the allocated blocks once they are malloc d i.e., compaction is not allowed CMSC 15400 45

Performance Goal: Throughput Given some sequence of malloc and free requests: R0, R1, ..., Rk, ... , Rn-1 Goals: maximize throughput and peak memory utilization These goals are often conflicting Malloc() and free() must be fast Throughput: Number of completed requests per unit time Example: 5,000 malloc calls and 5,000 freecalls in 10 seconds Throughput is 1,000 operations/second CMSC 15400 46

Performance Goal: Peak Memory Utilization Given some sequence of malloc and free requests: R0, R1, ..., Rk, ... , Rn-1 Def: Aggregate payload Pk malloc(p) results in a block with a payload of p bytes After request Rk has completed, the aggregate payload Pk is the sum of currently allocated payloads Def: Current heap size Hk Assume Hk is monotonically nondecreasing i.e., heap only grows when allocator uses sbrk Def: Peak memory utilization after k+1 requests Uk = ( maxi<=k Pi ) / Hk CMSC 15400 47

External Fragmentation Occurs when there is enough aggregate heap memory, but no single free block is large enough p1 = malloc(4) p2 = malloc(5) p3 = malloc(6) free(p2) Error! Oops! Can t proceed! Must increase heap size. p4 = malloc(6) Must have good allocation policy Depends on the pattern of future requests Thus, difficult to measure CMSC 15400 48

EXTRA CMSC 15400 49

The malloc Package #include <stdlib.h> void *malloc(size_t size) Successful: Returns a pointer to a memory block of at least size bytes aligned to an 8-byte (x86) or 16-byte (x86-64) boundary If size == 0, returns NULL Unsuccessful: returns NULL (0) and sets errno void free(void *p) Returns the block pointed at by p to pool of available memory p must come from a previous call to malloc or realloc Other functions calloc: Version of malloc that initializes allocated block to zero. realloc: Changes the size of a previously allocated block. sbrk: Used internally by allocators to grow or shrink the heap CMSC 15400 50