动态内存分配

1 . Binghamton University Dynamic Memory Alloca/on Slides credit: Presenta/on based on slides by Dave O’halloran/CSAPP 1 

2 . Binghamton University Dynamic memory alloca/on ¢  Where is this important? §  Heap §  Kernel heap §  Physical memory allocator §  Problems are similar, but specific some/mes force different solu/ons 2 

3 . Binghamton University Dynamic Memory Alloca/on ¢  Programmers use Applica/on dynamic memory Dynamic Memory Allocator allocators (such as Heap malloc) to acquire VM at run /me. §  For data structures whose User stack size is only known at run/me. Top of heap ¢  Dynamic memory (brk ptr) Heap (via malloc) allocators manage an area of process virtual Unini/alized data (.bss) memory known as the Ini/alized data (.data) heap. Program text (.text) 0 3 

4 . Binghamton University Dynamic Memory Alloca/on ¢  Allocator maintains heap as collec/on of variable sized blocks, which are either allocated or free ¢  Types of allocators §  Explicit allocator: applica/on allocates and frees space §  E.g., malloc and free in C §  Implicit allocator: applica/on allocates, but does not free space §  E.g. garbage collec/on in Java, ML, and Lisp ¢  Will discuss explicit memory alloca/on 4 

5 . Binghamton University The malloc Package #include <stdlib.h> void *malloc(size_t size) §  Successful: §  Returns a pointer to a memory block of at least size bytes (typically) aligned to 8-byte 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 func/ons §  calloc: Version of malloc that ini/alizes allocated block to zero. §  realloc: Changes the size of a previously allocated block. §  sbrk: Used internally by allocators to grow or shrink the heap 5 

6 . Binghamton University Alloca/on Example p1 = malloc(4) p2 = malloc(5) p3 = malloc(6) free(p2) p4 = malloc(2) 6 

7 . Binghamton University Constraints ¢  Applica/ons §  Can issue arbitrary sequence of malloc and free requests §  free request must be to a malloc’d block ¢  Allocators §  Can’t control number or size of allocated blocks §  Must respond immediately to malloc requests §  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 sa/sfy all alignment requirements §  8 byte alignment for GNU malloc (libc malloc) on Linux boxes §  Can manipulate and modify only free memory §  Can’t move the allocated blocks once they are malloc’d §  i.e., compac/on is not allowed 7 

8 . Binghamton University Goals ¢  Given some sequence of malloc and free requests: §  R0, R1, ..., Rk, ... , Rn-1 ¢  Goals: maximize throughput and peak memory u/liza/on §  These goals are o\en conflic/ng ¢  Throughput: §  Number of completed requests per unit /me ¢  U/liza/on: §  Percentage of the heap that is u/lized §  Poor memory u/liza/on caused by fragmenta/on, or poor alloca/on policies 8 

9 . Binghamton University Implementa/on Issues ¢  How do we know how much memory to free given just a pointer? ¢  How do we keep track of the free blocks? ¢  What do we do with the extra space when alloca/ng a structure that is smaller than the free block it is placed in? ¢  How do we pick a block to use for alloca/on -- many might fit? ¢  How do we reinsert freed block? 9 

10 . Binghamton University Knowing How Much to Free ¢  Standard method §  Keep the length of a block in the word preceding the block. § This word is o\en called the header field or header §  Requires an extra word for every allocated block p0 p0 = malloc(4) 5 block size data free(p0) 10 

11 . Binghamton University Keeping Track of Free Blocks ¢  Method 1: Implicit list using length—links all blocks 5 4 6 2 ¢  Method 2: Explicit list among the free blocks using pointers 5 4 6 2 ¢  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 11 

12 . Binghamton University Method 1: Implicit List ¢  For each block we need both size and alloca/on status §  Could store this informa/on in two words: wasteful! ¢  Standard trick §  If blocks are aligned, some low-order address bits are always 0 §  Instead of storing an always-0 bit, use it as a allocated/free flag §  When reading size word, must mask out this bit 1 word Size a a = 1: Allocated block a = 0: Free block Format of allocated and Payload Size: block size free blocks Payload: applica/on data (allocated blocks only) Op/onal padding 12 

13 . Binghamton University Detailed Implicit Free List Example Unused Start of 8/0 16/1 32/0 16/1 0/1 heap Double-word Allocated blocks: shaded aligned Free blocks: unshaded Headers: labeled with size in bytes/allocated bit 13 

14 . Binghamton University Implicit List: Finding a Free Block ¢  First fit: §  Search list from beginning, choose first free block that fits: p = start; while ((p < end) && \\ not passed end ((*p & 1) || \\ already allocated (*p <= len))) \\ too small p = p + (*p & -2); \\ goto next block (word addressed) §  Can take linear /me in total number of blocks (allocated and free) §  In prac/ce it can cause “splinters” at beginning of list ¢  Next fit: §  Like first fit, but search list star/ng where previous search finished §  Should o\en be faster than first fit: avoids re-scanning unhelpful blocks §  Some research suggests that fragmenta/on is worse ¢  Best fit: §  Search the list, choose the best free block: fits, with fewest bytes le\ over §  Keeps fragments small—usually helps fragmenta/on §  Will typically run slower than first fit 14 

15 . Binghamton University Implicit List: Alloca/ng in Free Block ¢  Alloca/ng in a free block: spli?ng §  Since allocated space might be smaller than free space, we might want to split the block 4 4 6 2 p addblock(p, 4) 4 4 4 2 2 void addblock(ptr p, int len) { int newsize = ((len + 1) >> 1) << 1; // round up to even int oldsize = *p & -2; // mask out low bit *p = newsize | 1; // set new length if (newsize < oldsize) *(p+newsize) = oldsize - newsize; // set length in remaining } // part of block 15 

16 . Binghamton University Implicit List: Freeing a Block ¢  Simplest implementa/on: §  Need only clear the “allocated” flag void free_block(ptr p) { *p = *p & -2 } §  But can lead to “false fragmenta/on” 4 4 4 2 2 free(p) p 4 4 4 2 2 malloc(5) Oops! There is enough free space, but the allocator won’t be able to find it 16 

17 . Binghamton University Implicit List: Coalescing ¢  Join (coalesce) with next/previous blocks, if they are free §  Coalescing with next block 4 4 4 2 2 logically p free(p) gone 4 4 6 2 2 void free_block(ptr p) { *p = *p & -2; // clear allocated flag next = p + *p; // find next block if ((*next & 1) == 0) *p = *p + *next; // add to this block if } // not allocated §  But how do we coalesce with previous block? 17 

18 . Binghamton University Implicit List: Bidirec/onal Coalescing ¢  Boundary tags [Knuth73] §  Replicate size/allocated word at “boiom” (end) of free blocks §  Allows us to traverse the “list” backwards, but requires extra space §  Important and general technique! 4 4 4 4 6 6 4 4 Header Size a a = 1: Allocated block a = 0: Free block Format of Size: Total block size allocated and Payload and padding free blocks Payload: Applica/on data (allocated blocks only) Boundary tag Size a (footer) 18 

19 . Binghamton University Constant Time Coalescing Case 1 Case 2 Case 3 Case 4 Allocated Allocated Free Free Block being freed Allocated Free Allocated Free 19 

20 . Binghamton University Constant Time Coalescing (Case 1) m1 1 m1 1 m1 1 m1 1 n 1 n 0 n 1 n 0 m2 1 m2 1 m2 1 m2 1 20 

21 . Binghamton University Constant Time Coalescing (Case 2) m1 1 m1 1 m1 1 m1 1 n 1 n+m2 0 n 1 m2 0 m2 0 n+m2 0 21 

22 . Binghamton University Constant Time Coalescing (Case 3) m1 0 n+m1 0 m1 0 n 1 n 1 n+m1 0 m2 1 m2 1 m2 1 m2 1 22 

23 . Binghamton University Constant Time Coalescing (Case 4) m1 0 n+m1+m2 0 m1 0 n 1 n 1 m2 0 m2 0 n+m1+m2 0 23 

24 . Binghamton University Keeping Track of Free Blocks ¢  Method 1: Implicit free list using length—links all blocks 5 4 6 2 ¢  Method 2: Explicit free list among the free blocks using pointers 5 4 6 2 ¢  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 24 

25 . Binghamton University Explicit Free Lists Allocated (as before) Free Size a Size a Next Payload and Prev padding Size a Size a ¢  Maintain list(s) of free blocks, not all blocks §  The “next” free block could be anywhere §  So we need to store forward/back pointers, not just sizes §  S/ll need boundary tags for coalescing §  Luckily we track only free blocks, so we can use payload area 25 

26 . Binghamton University Explicit Free Lists ¢  Logically: A B C ¢  Physically: blocks can be in any order Forward (next) links A B 4 4 4 4 6 6 4 4 4 4 C Back (prev) links 26 

27 . Binghamton University Alloca/ng From Explicit Free Lists conceptual graphic Before AKer (with spli?ng) = malloc(…) 27 

28 . Binghamton University Freeing With Explicit Free Lists ¢  InserMon policy: Where in the free list do you put a newly freed block? §  LIFO (last-in-first-out) policy §  Insert freed block at the beginning of the free list §  Pro: simple and constant /me §  Con: studies suggest fragmenta/on is worse than address ordered §  Address-ordered policy §  Insert freed blocks so that free list blocks are always in address order: addr(prev) < addr(curr) < addr(next) §  Con: requires search §  Pro: studies suggest fragmenta/on is lower than LIFO 28 

29 . Binghamton University Freeing With a LIFO Policy (Case 1) conceptual graphic Before free( ) Root ¢  Insert the freed block at the root of the list AKer Root 29