6.087 Practical Programming in C, lec11

Dynamic memory allocation, mallocand valgrind, garbage collection.

Review: C standard library

Stdio.h

• I/O functions: fopen(), freopen(), fflush(), remove(),rename(), tmpfile(), tmpnam(), fread(), fwrite(), fseek(), ftell(),rewind(), clearerr(), feof(), ferror()

• Character testing functions: isalpha(), isdigit(), isalnum(),iscntrl(), islower(), isprint(), ispunct(), isspace(), isupper()

string.h

• Memory functions: memcpy(), memmove(), memcmp(), memset()

stdlib.h

• Conversion functions: atoi(), atol(), atof(), strtol(),strtoul(), strtod()

• Utility functions: rand(), srand(), abort(), exit(), atexit(),system(), bsearch(), qsort()

assert.h

• Diagnostics: assert() function, __FILE__, __LINE__ macros

stdarg.h

• Variable argument lists:

• Declaration with ... for variableargument list (may be of any type):

int printf (const char ∗ fmt, ...);

• Access using data structureva_list ap, initialized using va_start(), accessed using va_arg(),destroyed at end using va_end()

• Time functions: clock(), time(), difftime(), mktime(),asctime(), localtime(), ctime(), strftime()

这几个库的分工很明确，值得学习和借鉴。

Dynamic memory allocation

• Memory allocated during runtime

• Request to map memory using mmap() function (in <sys/mman.h>)

• Virtual memory can be returned to OS using munmap()

• Virtual memory either backed by a file/device or bydemand-zero memory:

• all bits initialized to zero

• not stored on disk

• used for stack, heap,uninitialized (at compile time) globals

操作系统会为每个进程分配一块虚拟内存，从而隔离各个进程。分配虚拟内存中的一个主要操作就是内存映射，即将物理地址映射为虚拟地址。这个映射操作可以通过mmap()函数实现，类似地munmap()函数将虚拟内存返回给操作系统。demand-zeromemory就是真正的计算机内存，在程序初始化时，需要在这种内存上创建栈、堆和未初始化的全局变量。这些全局变量将在程序运行时进行初始化。虚拟内存不仅包括计算机内存，还包含文件和设备，这样做有很大的优点，使程序在自己的虚拟内存空间即可完成所有的操作，实现了更好的隔离和封装。

Mapping memory

• Mapping memory:

void ∗mmap(void∗ start, size_tlength, int prot, int flags, int fd, off_t offset);

• asks OS to map virtual memory ofspecified length, using specified physical memory (file ordemand-zero)

• fd is file descriptor (integerreferring to a file, not a file stream) for physical memory (i.e.file) to load into memory

• for demand-zero, including theheap, use MMAP_ANON flag

• start – suggested startingaddress of mapped memory, usually NULL

• Unmap memory:

int munmap(void ∗start, size_tlength);

在linux中可以通过manmmap来获得更详细的信息，在这里很关键的一个地方就是fd，这里隐藏着硬盘中的文件加载到内存中的“星际之门”

The heap

• Heap – private section of virtual memory (demand-zero) usedfor dynamic allocation

• Starts empty, zero-sized

• brk – OS pointer to top of heap, moves upwards as heap grows

• To resize heap, can use sbrk() function:

void ∗sbrk(int inc ); /∗ returns old value of brk_ptr ∗/

• Functions like malloc() and new (in C++) manage heap, mappingmemory as needed

• Dynamic memory allocators divide heap into blocks

我想这里的堆应该是对大堆的一种，使用最大堆来实现运行时内存的分配有这几个好处：

1. 最大堆是树（或者说类似树）结构中唯一永远平衡且数据结构简单的数据结构。尽管红黑树、B树等也可以实现永远平衡，但其数据结构复杂，实现比较麻烦，而且实现平衡的操作也复杂。最大堆之所以能这样同时达到这两点，主要原因是堆的满足条件比上面提到的树结构要简单的多，例如最大堆只需要保证父节点的值比子节点的值大即可。

2. 在进行新内存的分配时，所分配的内存必须比需要的内存更大，最大堆这种数据结构可以节省这种查找的时间。

Requirements

• Must be able to allocate, free memory in any order

• Auxiliary data structure must be on heap

• Allocated memory cannot be moved

• Attempt to minimize fragmentation

在最大堆中插入和删除节点的操作都不复杂，时间复杂度为堆高，空间复杂度为n，因为这些操作可以在本地完成（本地是指在堆自身的数据结构中完成，几乎不需要辅助空间）。最小化碎片这个我觉得可以在堆中增加一个标记元素，然后将堆所在空间的内存都分配为同样大小。在回收内存时通过指针算术看相邻的元素块是否在树中，若在，则合并。

Fragmentation

• Two types – internal and external

• Internal – block size larger than allocated variable inblock

• External – free blocks spread out on heap

• Minimize external fragmentation by preferring fewer largerfree blocks

这几个就不清楚了，以后看编译原理的时候仔细看看，应该是那里面的内容。

Design choices

• Data structure to track blocks

• Algorithm for positioning a new allocation

• Splitting/joining free blocks

前面两个使用最大堆即可很容易地实现，最后一个我想在数据结构上有独特的设计才行。

Tracking blocks

• Implicit free list: no data structure required

• Explicit free list: heap divided into fixed-size blocks;

maintain a linked list of free blocks

• allocating memory: removeallocated block from list

• freeing memory: add block back tofree list

• Linked list iteration in linear time

• Segregated free list: multiple linked lists for blocks ofdifferent sizes

• Explicit lists stored within blocks (pointers in payloadsection of free blocks)

Positioning allocations

• Block must be large enough for allocation

• First fit: start at beginning of list, use first block

• Next fit: start at end of last search, use next block

• Best fit: examines entire free list, uses smallest block

• First fit and next fit can fragment beginning of heap, butrelatively fast

• Best fit can have best memory utilization, but at cost ofexamining entire list

Splitting and joining blocks

• At allocation, can use entire free block, or part of it,splitting the block in two

• Splitting reduces internal fragmentation, but more complicatedto implement

• Similarly, can join adjacent free blocks during (or after)freeing to reduce external fragmentation

• To join (coalesce) blocks, need to know address of adjacentblocks

• Footer with pointer to head of block – enable successiveblock to find address of previous block

A simple memory allocator

• Code in Computer Systems: A Programmer’s Perspective

• Payload 8 byte alignment; 16 byte minimum block size

• Implicit free list

• Coalescence with boundary tags; only split if remaining blockspace ≥ 16 bytes

Initialization

1. Allocate 16 bytes for padding, prologue, epilogue

2. Insert 4 byte padding and prologue block (header + footeronly, no payload) at beginning

3. Add an epilogue block (header only, no payload)

4. Insert a new free chunk (extend the heap)

Allocating data

1. Compute total block size (header+payload+footer)

2. Locate free block large enough to hold data (using first ornext fit for speed)

3. If block found, add data to block and split if padding ≥16bytes

4. Otherwise, insert a new free chunk (extending the heap), andadd data to that

5. If could not add large enough free chunk, out of memory

Freeing data

1. Mark block as free (bit flag in header/footer)

2. If previous block free, coalesce with previous block (updatesize of previous)

3. If next block free, coalesce with next block (update size)

Explicit free list

• Maintain pointer to head, tail of free list (not in addressorder)

• When freeing, add free block to end of list; set pointer tonext, previous block in free list at beginning of payload sectionof block

• When allocating, iterate through free list, remove from listwhen allocating block

• For segregated free lists, allocator maintains array of listsfor different sized free blocks

malloc() for the real world

• Used in GNU libc version of malloc()

• Details have changed, but nice general discussion can befound at

http://g.oswego.edu/dl/html/malloc.html

• Chunks implemented as in segregated free list, with pointersto previous/next chunks in free list in payload of free blocks

• Lists segregated into bins according to size; bin sizesspaced logarithmically

• Placement done in best-fit order

• Deferred coalescing and splitting performed to minimizeoverhead

Using malloc()

• Minimize overhead – use fewer, larger allocations

• Minimize fragmentation – reuse memory allocations as muchas possible

• Growing memory – using realloc() can reduce fragmentation

• Repeated allocation and freeing of variables can lead to poorperformance from unnecessary splitting/coalescing (depending onimplementation of malloc())

现在逐渐明白realloc的作用，以前一直觉得是鸡肋，在实际程序中也没用过这个函数。

Using valgrind to detect memory leaks

• A simple tutorial:http://cs.ecs.baylor.edu/~donahoo/tools/valgrind/

• valgrind program provides several performance tools,including memcheck:

athena% valgrind --tool=memcheck--leak-check=yes program.o

• memcheck runs program using virtual machine and tracks memoryleaks

• Does not trigger on out-of-bounds index errors for arrays onthe stack

valgrind使用虚拟机来检查内存泄漏，我想可以带来这些好处：可以在更多的环境中测试，并能更好地记录程序的运行状态。

Other valgrind tools

• Can use to profile code to measure memory usage, identifyexecution bottlenecks

• valgrind tools (use name in -tool= flag):

• cachegrind – counts cache misses for each line of code

• callgrind – counts function calls and costs in program

• massif – tracks overall heap usage