Ch11. Dynamic Memory Allocation

void addblock(void *p, int len)
{// arithmetic shift, round up to even（远零取整）,两字节对齐int newsize = ((len + 1) >> 1) << 1;  	int oldsize = *p & -2;  // mask out status bit*p = newsize | 1;       // set length and allocted status of new blockif (newsize < oldsize)	// set length of remaining free block*(p + newsize) = oldsize - newsize; 
}  
void * malloc(int len)
{void *p = NULL; p = search_free_block();if(p) addblock(p,len + 4); // header size = 4 Bytesreturn p + 1; // (p + 4 bytes) addresse of payload 
}

• Freeing a Block
  • only clear “allocated” status ? Generating external fragmentation !!
  • Adjacent free blocks need to be coalesced
  • All decent allocator is that contiguous free blocks never exist；
    

void free_block(ptr p)
{*p = *p & -2;   		// clear allocated flagnext = p + (*p)/4;     	// find next block headerif ((*next & 1) == 0)  	// if not allocated*p = *p + *next; 	// add to this block
}

• How to Coalescing previous block
  • remember the previous block while traverse the list，very inefficient !
  • Bidirectional Coalescing
    • Boundary tags [ Don Kunth 1973 ]；
      Replicate header at end of free blocks ( a.k.a. “footer” )，这样 free§ 的时候，p-1 便是 前一个 block 的 “footer”（即 “header”），从而判断是否与前一个 block 进行 Coalescing；缺点是 overhead 变大；
      
      4 cases：
      　　　　
      　　　　

Allocated block 都没有 footer；怎样才能在没有 footer 的条件下判断 previous block 是否 allocated ？
如果 previous block 是 allocated 状态，则它不参与合并，footer也就没有存在的必要 !!
但没有 “footer” 又不能判断 previous block 是否被 allocated，怎么办？
字节对齐导致 header 的低 n 位都是 0 ！
malloc 时在其 后 一个 header 中用一个 低位记录 “allocated” 状态；

11.3 Explicit free lists

Implicit Free List 是由 block 的 length 隐式构建的单向链表，链表节点在虚拟地址上也是连续的；
而 Explicit 则是由 指针 显式构建的双向链表，链表节点间的相对位置随机；

11.3.1 Allocating

只需要更新 4个指针；

11.3.2 Freeing

核心问题：Where to insert the newly freed block ?

• LIFO (last - in - first - out) Policy
  • free list 的开头插入新释放的 block；
  • 实现简单，时间复杂度 O(1)；
  • 研究表明 碎片较 Address-ordered 更多；
• Address-ordered Policy
  • pre 块地址 < newly freed 块地址 < next 块地址；
  • 需要 search，可以通过 平衡树 等方法加速；
  • 碎片较少；

很多程序员会犯 过早优化 ( premature optimization ) 的错误，刚开始就思考奇奇怪怪的场景和对应的优化措施；在解决 allocator 这样复杂的问题的时候，应该本着“先易后难” 的原则，先有基础方案，再找瓶颈 并 逐个优化；

为方便描述，使用 predecessor 和 successor 分别表示 虚拟地址（VA）前后相邻，而用 prev 和 next 表示 free list 中的前后相连；

LIFO Case 1 前后都不用 coalescing；

LIFO Case 2 与 predecessor 进行 coalescing；

LIFO Case 3 与 successor 进行 coalescing；

LIFO Case 4 与 successor、predecessor 同时 coalescing；

11.3.3 Explicit List Summary

• v.s. Implicit List
  • Faster，seaching free list only instead of whole heap ( especially when most of the memory is full )；
  • More complicated splicing business；
  • Extra space for linked list pointers；

11.4 Segregated free lists

Each size class has its own free list；

• To allocato a block of size n:

  • Seach appropriate free lists of blocks of requiring size m ( If the block is not found, try next larger class )；
  • Place split block on appropriate list ( optional, may be class size exactly equal to the requiring size )
  • If no block is found:
    • Request additional heap memory from OS ( sbrk() )；
    • Allocate block of n bytes from this new memory；
    • Place remainder (剩余的块) as a single free block in largest size class；

• To free a block；

  • Coalesce (like before) and place on appropriate list；

• Advantages of seglist allocators

  • Higher throughput，快：
    二分查找 合适大小的空闲块链表，log time for power-of-two size classes；
  • Better memory utilization，省：
    对 seglist 的 First-fit search 几乎等效于 对整个 heap 进行了 best-fit search；

sbrk 是 Syscall，花费约几百微妙，overhead 很大，通过 一次 sbrk 申请一个超大块的方式，amortize (均摊) 时间开销；但同时，memory utilization 将变得很低；又一个 space – time trade – off

Seglist 存放在 heap 的起始位置 (见 malloc Lab)；
More read：
“Dynamic Storage Allocation: A Survey and Critical Review”

11.5 Implicit Memory Management: Garbage Collection

• Automatic reclamation of heap-allocated storage；
• Common in many dynamic languages；
  Python, Ruby, Java, Perl, ML, Lisp, Mathematica；
• Variants (“conservative” garbage collectors) exist for C and C++
  Allocator can’t determine whether these blocks are indeed garbage；

void foo(){int *p = malloc(128); // garbagereturn;
}

11.5.1 Garbage Collection

• Which memory can be freed?
  • 扫描内存，辨别指针及被其指向的块，没有被指向的块，认为是 Garbage；
• Assumptions about pointers
  • Memory Manager 需要能分辨出哪些变量是指针；
  • 假设 指针都指向 块的开头（反例如 指向数组中元素的指针）；
  • 指针必须是静态不可变的?
• Classical GC Algorithms
  • Mark-and-sweep collection (McCarthy, 1960)
  • Reference counting (Collins, 1960)
  • Copying collection (Minsky, 1963)
  • Generational Collectors (Lieberman and Hewitt, 1983)
    • Collection based on lifetimes；
    • Most allocations become garbage very soon；
    • So focus reclamation work on zones of memory recently allocated；

More information “Garbage Collection: Algorithms for Automatic Dynamic Memory”, John Wiley & Sons, 1996.

• Mark-and-sweep collection
  • Each block is a node in graph;
  • Each pointer is a edge in the graph；
  • Locations not in the heap that contain pointers into the heap are calld root nodes (e.g. registers, locations on the stack, global variables)；
  • A node is reachable if there is a path from any root to that node；
    Non-reachable nodes are garbage；
    
  • Implement on top of malloc / free package
    • Allocate using malloc until you “run out of space”；
    • When out of space，use extra mark bit in the head of each block；
    • Sub phase 1，mark，start from all roots and set mark bit on each reachable block（ depth-first traversal ）；
    • Sub phase 2，scan all blocks，and free blocks that are not marked；
  • A Simple Implementation
    

ptr mark(ptr p) 						// pointer to the payload
{if (false == is_ptr(p)) return;     	// do nothing if not pointerif (true == markBitSet(p)) return;	// check if already markedsetMarkBit(p);                 		// set the mark bitfor (i=0; i < length(p); i++)  		// mark() recursivelymark(p[i]); return;
}      
ptr sweep(ptr p, ptr end) 
{while (p < end) 						// scan the whole heap{if(true == markBitSet(p)) clearMarkBit(); 	// 正在被引用的块else if (true == allocateBitSet(p)) free(p);	// 没有被引用的块p += length(p);								// 将 p 指向 next block
}

• How to find the beginning of the block
  • In C，pointers can point to the middle of a block；
  • Use a balanced binary tree to keep track of all allocated blocks (key is start-of-block)；
  • Balanced-tree pointers can be stored in header (use two additional words)；
  • Search the binary tree，a pointer should fall in the beginning and end of some allocated block，and that block is reachable；
  • It’s conservative，because it maybe just an integer，but purportedly points to non-reachable blocks；
    

11.6 Memory-related perils and pitfalls

Errors involving memory are the worst kind of bugs to try to find out，because they are distant in both space and time；You only find out about those errors when you try to reference that data；

• Dereferencing bad pointers
• Reading uninitialized memory
• Overwriting memory
• Referencing nonexistent variables
• Freeing blocks multiple times
• Referencing freed blocks
• Failing to free blocks

C pointers，只要根据声明时 运算符的优先级，就不会认错类型；

*x[3]，[]优先级高，x 是 size 为 3 的数组，其左是*，数组的元素是指针；
*(*x[3])()，数组元素（指针）指向函数，函数的返回值也是指针；
int (*(*x[3])())[5]，函数返回的指针，指向 size 为 5 的 int 数组；