Memory management every engineer needs to know
系统启动时，kernel资源以及其他启动进程资源被load进physical memory。对于32位系统来说，进程启动时，它会拥有一块4G大小的virtual memory。我是一个叫Nerd的进程，启动的时候kernel给我这张图片，告诉我：你能使用的User Mode Space只有3G，然后从0xc0000000到0xffffffff是内核地址，你别动它，你没权限。physical memory和virtual memory的关系就是：physical memory是以PAGE的形式Map到virtual memory，kernel管理着所有的page_table,所以你程序启动过多的时候physical memory会吃紧，但是每次新启进程的virtual memory依然是4G。使用top -p <pid>查看进程的resident memory就是进程实际吃掉的physical memory，在检查memory leak的时候非常有用。(TIP:对于纯C程序来说，开启mtrace(),即可统计内存泄漏情况，或者自己用__malloc_hook之类的实现内存检测)。总的来说，virtual memory只是kernel开给每个进程的一张货币而已，physical memory分配过多必然会引发通货膨胀,然后发给我Nerd进程的货币就贬值了，无所谓啦，我是个Nerd。
process switch就是通过置换virtual memory的形式运转的,因为启动着的进程在physical memory里有各自的resident memory，所以这个置换只是暂存了virtual memory的状态，kernel状态，寄存器值等等进程相关的东西。而thread共享process的TEXT段,DATA段,BSS段,HEAP,所以thread switch is much cheaper than process switch。
更加详细的virtual memory是这样的，TEXT段存储所有的代码，DATA段存储所有的已初始化global variables，例如const char *msg="I am a nerd!"，msg就是存储在DATA段, BSS段存储所有的未初始化global variables,并且内存全部初始化为0，例如const char *msg存放在BSS段，但是肯定不是指向"I am a nerd!"，因为它指向NULL。memory allocator的实现有两种方式，其一是通过brk()系统调用(TIPS:sbrk() calls brk())，其二是通过mmap()``ANONYMOUS或者/dev/zero(mmap()实现的calloc()就是这么干的)。brk()是从program break开始向高地址增长(TIPS:sbrk(0)可以获取program break, 任何越过program break的内存读写都是illegal access)，例如sbrk(4096)就表示申请4K的内存，sbrk(-4096)就是释放4K内存，program break向低地址移动4096(TIPS:有些platform不支持sbrk()传入负值)。mmap()申请的内存是由高地址向低地址写的。关于stack，使用ulimit -s显示最大可用栈大小，一般是8192即8K,所以谨慎使用递归算法，很容易造成stack overflow。使用stack的一个好处就是，stack上频繁使用的location很可能会被mirror进CPU L1 cache，但是也不能完全依赖这一点，因为不是我们能控制的，over-use很容易造成stack overflow。(relevant reading:>stack and cache question >c++ stack memory and cpu cache)
如果你是一个细心的读者，可能会问：为什么TEXT段的起始地址是0x08048000。Here is the explain:
使用cat /proc/self/maps查看当前terminal的内存map情况。
对于32位系统是这样的：
001c0000-00317000 r-xp 00000000 08:01 245836 /lib/libc-2.12.1.so
00317000-00318000 ---p 00157000 08:01 245836 /lib/libc-2.12.1.so
00318000-0031a000 r--p 00157000 08:01 245836 /lib/libc-2.12.1.so
0031a000-0031b000 rw-p 00159000 08:01 245836 /lib/libc-2.12.1.so
0031b000-0031e000 rw-p 00000000 00:00 0
00376000-00377000 r-xp 00000000 00:00 0 [vdso]
00852000-0086e000 r-xp 00000000 08:01 245783 /lib/ld-2.12.1.so
0086e000-0086f000 r--p 0001b000 08:01 245783 /lib/ld-2.12.1.so
0086f000-00870000 rw-p 0001c000 08:01 245783 /lib/ld-2.12.1.so
08048000-08051000 r-xp 00000000 08:01 2244617 /bin/cat
08051000-08052000 r--p 00008000 08:01 2244617 /bin/cat
08052000-08053000 rw-p 00009000 08:01 2244617 /bin/cat
09ab5000-09ad6000 rw-p 00000000 00:00 0 [heap]
b7502000-b7702000 r--p 00000000 08:01 4456455 /usr/lib/locale/locale-archive
b7702000-b7703000 rw-p 00000000 00:00 0
b771b000-b771c000 r--p 002a1000 08:01 4456455 /usr/lib/locale/locale-archive
b771c000-b771e000 rw-p 00000000 00:00 0
bfbd9000-bfbfa000 rw-p 00000000 00:00 0 [stack]
0x08048000之前是library kernel maaped for syscalls,事实上呢，你可以map任何你想要的东西到这块内存，128M哟。
对于64位系统是这样的：
00400000-0040b000 r-xp 00000000 ca:01 400116 /bin/cat
0060a000-0060c000 rw-p 0000a000 ca:01 400116 /bin/cat
0062c000-0064d000 rw-p 00000000 00:00 0 [heap]
7f38ab82e000-7f38b1d55000 r--p 00000000 ca:01 454475 /usr/lib/locale/locale-archive
7f38b1d55000-7f38b1f0c000 r-xp 00000000 ca:01 396116 /lib64/libc-2.17.so
7f38b1f0c000-7f38b210c000 ---p 001b7000 ca:01 396116 /lib64/libc-2.17.so
7f38b210c000-7f38b2110000 r--p 001b7000 ca:01 396116 /lib64/libc-2.17.so
7f38b2110000-7f38b2112000 rw-p 001bb000 ca:01 396116 /lib64/libc-2.17.so
7f38b2112000-7f38b2117000 rw-p 00000000 00:00 0
7f38b2117000-7f38b2138000 r-xp 00000000 ca:01 396509 /lib64/ld-2.17.so
7f38b2323000-7f38b2326000 rw-p 00000000 00:00 0
7f38b2337000-7f38b2338000 rw-p 00000000 00:00 0
7f38b2338000-7f38b2339000 r--p 00021000 ca:01 396509 /lib64/ld-2.17.so
7f38b2339000-7f38b233a000 rw-p 00022000 ca:01 396509 /lib64/ld-2.17.so
7f38b233a000-7f38b233b000 rw-p 00000000 00:00 0
7ffcffe94000-7ffcffeb5000 rw-p 00000000 00:00 0 [stack]
7ffcfffa1000-7ffcfffa3000 r-xp 00000000 00:00 0 [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
libc和ld被map到了堆内存，0x00400000以下的地址可能有东西，也可能没东西，你同样可以map你想要的东西到这块内存。
更加细心的读者可能要问：为什么要有random brk offset,random stack offset和random mmap offset?这是为了避免直接算得某个进程的virtual memory详细地址，然后可以利用这个远程PWN(反正我不会，大牛可以教教我^_^)。
这个图是更加详细的解释，const char *msg="I am a nerd!",msg会存在DATA段，"I am a nerd!"存在TEXT段，是只读的。可执行文件大小 = TEXT + DATA！
这个是经典的没有各种offset的virtual memory layout。
我就不解释了，不会kernel，详情自己看relevant reading: How the Kernel Manages Your Memory
struct malloc_chunk {
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;
};
dlmalloc使用malloc_chunk结构体存储每块申请的内存的具体信息，在32位系统里sizeof(malloc_chunk) = 16，在64位系统里sizeof(malloc_chunk) = 32，example:
int main(int argc, char **argv) {
void *mem = malloc(0);
malloc_stats();
return 0;
}
我的机器是64位的，调用malloc(0)其实也申请了内存，这块内存空间大小就是sizeof(malloc_chunk) = 32，运行以上代码将显示如下结果:
Arena 0:
system bytes = 135168
in use bytes = 32
Total (incl. mmap):
system bytes = 135168
in use bytes = 32
max mmap regions = 0
max mmap bytes = 0
所以，你申请的内存看上去是这样子的。
struct malloc_state {
/* The maximum chunk size to be eligible for fastbin */
INTERNAL_SIZE_T max_fast; /* low 2 bits used as flags */
/* Fastbins */
mfastbinptr fastbins[NFASTBINS];
/* Base of the topmost chunk -- not otherwise kept in a bin */
mchunkptr top;
/* The remainder from the most recent split of a small request */
mchunkptr last_remainder;
/* Normal bins packed as described above */
mchunkptr bins[NBINS * 2];
/* Bitmap of bins. Trailing zero map handles cases of largest binned size */
unsigned int binmap[BINMAPSIZE+1];
/* Tunable parameters */
CHUNK_SIZE_T trim_threshold;
INTERNAL_SIZE_T top_pad;
INTERNAL_SIZE_T mmap_threshold;
/* Memory map support */
int n_mmaps;
int n_mmaps_max;
int max_n_mmaps;
/* Cache malloc_getpagesize */
unsigned int pagesize;
/* Track properties of MORECORE */
unsigned int morecore_properties;
/* Statistics */
INTERNAL_SIZE_T mmapped_mem;
INTERNAL_SIZE_T sbrked_mem;
INTERNAL_SIZE_T max_sbrked_mem;
INTERNAL_SIZE_T max_mmapped_mem;
INTERNAL_SIZE_T max_total_mem;
};
typedef struct malloc_state *mstate;
static struct malloc_state av_;
这个名叫av_的结构体就是用来存储内存申请的具体信息的，无论是brk的也好，还是mmap的也好，都会记录在案。
关于malloc
- 当你调用
malloc时，dlmalloc首先确定mstate.fastbins和mstate.bins有没有满足需求的内存块大小，有就可以直接使用。如果malloc申请内存大小超过M_MMAP_THRESHOLD即128 * 1024并且free list里没有满足需要的内存大小，malloc就会调用mmap申请内存。因为有一个header，所以大小为128 * 1024 - 32，具体信息可以man mallopt，我就不贴dlmalloc的源码了，感兴趣可以自己去翻。example:(strace跟踪系统调用)
int main(int argc, char **argv) {
void *mem = malloc(1024 * 128 - 24);
malloc_stats();
return 0;
}
编译以上代码，strace结果：
brk(0) = 0xa2c000
brk(0xa6d000) = 0xa6d000
int main(int argc, char **argv) {
void *mem = malloc(1024 * 128 - 24 + 1);
malloc_stats();
return 0;
}
编译以上代码，strace结果：
mmap(NULL, 135168, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f65339a6000
为什么是24而不是sizeof(malloc_chunk)，我猜glibc修改了dlmalloc实现，因为我看到的dlmalloc源码不是这样子的。
关于malloc_trim
-
malloc_trim用来归还申请的内存给系统，但是只归还通过brk申请的内存块，归还大小为N * PAGE_SZIE，一般linux的PAGE_SIZE为4096Bytes，详情可以man getpagesize。
关于free
-
free归还通过brk申请的内存到mstate.fastbin，如果free的内存是通过brk申请的并且其大小超过了FASTBIN_CONSOLIDATION_THRESHOLD即DEFAULT_TRIM_THRESHOLD >> 1即256 * 1024 / 2即128K，那么这块内存会通过brk缩减program break的方式直接归还给系统，mmap申请的内存直接通过munmap归还给系统。
关于realloc
-
realloc嘛，自己man realloc吧，就是malloc + memcpy，但是此memcpy非彼memcpy，此memcpy是通过宏定义来实现的，代码如下：
#define MALLOC_COPY(dest,src,nbytes) \
do { \
INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) src; \
INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) dest; \
CHUNK_SIZE_T mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T); \
long mcn; \
if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \
switch (mctmp) { \
case 0: for(;;) { *mcdst++ = *mcsrc++; \
case 7: *mcdst++ = *mcsrc++; \
case 6: *mcdst++ = *mcsrc++; \
case 5: *mcdst++ = *mcsrc++; \
case 4: *mcdst++ = *mcsrc++; \
case 3: *mcdst++ = *mcsrc++; \
case 2: *mcdst++ = *mcsrc++; \
case 1: *mcdst++ = *mcsrc++; if(mcn <= 0) break; mcn--; } \
} \
} while(0)
关于memalign
- 不太看得懂，略过吧，反正是通过位运算实现的。
关于calloc
-
calloc先调用malloc，然后调用memset，但是此memset非彼memset，此memset是通过宏定义实现的，代码如下：
#define MALLOC_ZERO(charp, nbytes) \
do { \
INTERNAL_SIZE_T* mzp = (INTERNAL_SIZE_T*)(charp); \
CHUNK_SIZE_T mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T); \
long mcn; \
if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \
switch (mctmp) { \
case 0: for(;;) { *mzp++ = 0; \
case 7: *mzp++ = 0; \
case 6: *mzp++ = 0; \
case 5: *mzp++ = 0; \
case 4: *mzp++ = 0; \
case 3: *mzp++ = 0; \
case 2: *mzp++ = 0; \
case 1: *mzp++ = 0; if(mcn <= 0) break; mcn--; } \
} \
} while(0)
说实话，这个我没看太懂。
结语
- 就到这里吧，大家有什么感兴趣的想学的东西可以发邮件到我的email：charles.cn.bj@gmail.com
- Google有自己的
tcmalloc，GNU有自己通过ptmalloc改编的malloc，市面上还有jemalloc等等其他的memory allocator，写完这篇，我也要去写个charles_malloc了，Byebye……
- Mail: charlesliu.cn.bj@gmail.com
- Status: Can be hired
- 想去BAT～
