内存管理内幕
内存管理是计算机编程最为基本的领域之一。在很多脚本语言中，您不必担心内存是如何管理的，这并不能使得内存管理的重要性有一点点降低。对实际编程来说，理解您的内存管理器的能力与 局限性至关重要。在大部分系统语言中，比如 C 和 C++，您必须进行内存管理。 –IBM Dveloper
从malloc谈起
在c语言库里，
malloc：该函数分配给定的字节数，并返回一个指向它们的指针。 如果没有足够的可用内存，那么它返回一个空指针。
void* malloc(size_t nmemb, size_t size);
malloc** returns a void pointer to the allocated space, or NULL if there is insufficient memory available. To return a pointer to a type other than void, use a type cast on the return value. The storage space pointed to by the return value is guaranteed to be suitably aligned for storage of any type of object. If size is 0, malloc allocates a zero-length item in the heap and returns a valid pointer to that item. Always check the return from malloc, even if the amount of memory requested is small.
malloc返回一个指向已分配空间的空指针，如果内存不足，则返回空指针。若要返回指向void以外类型的指针，请对返回值使用类型转换。返回值指向的存储空间保证适当对齐，以存储任何类型的对象。如果大小为0，malloc将在堆中分配一个零长度的项，并返回指向该项的有效指针。始终检查malloc的返回值（是否为NULL），即使请求的内存大小很小。
它从内存池中“拿走一部分内存，并标注可用。
物理内存和虚拟内存
在操作系统之上是一个个程序，操作系统给予了每一个程序一个假像，它让每一个程序都以为自己有所有的内存(在64位，内存为4GB的系统里这个大小大概是4GB)，但是显然系统并没有这么多内存给每一个程序。于是就存在一个叫做mmpMMU的硬件来做虚拟内存地址与物理内存地址的转换。
Memory Management Unit
地址和页
计算机在寻找内存地址时是通过页page为单位。一个内存页是一段固定大小的连续内存地址的总称，具体到Linux中，典型的内存页大小为4k。与段地址不同，它是的大小是可变的，4K，8K都可以作为页的大小。MMU通过页表（page)将两个地址进行转换。在系统内核空间在页表中拥有较高权限，因此非操作系统程序试图访问这些页时会导致一个缺页错误(pagefault)。在Linux中内核空间是持续存在的，并且在所有进程中都映射到同样的物理内存。与此相反，非操作系统地址空间的映射随进程切换的发生而不断变化。
内存页与磁盘页
MMU在工作时，会发现页表表明某个内存页不在物理内存中，此时会触发一个缺页异常（Page Fault），此时系统会到磁
盘中相应的地方将磁盘页载入到内存中，然后重新执行由于缺页而失败的机器指令。这就是brk()函数的原理。
Linux内存管理
在多任务操作系统中，每个进程都运行在属于自己的内存沙盘中。这个沙盘就是虚拟地址空间(Virtual Address Space)，在32位模式下它是一个4GB的内存地址块。在Linux系统中, 内核进程和用户进程所占的虚拟内存比例是1:3，而Windows系统为2:2(通过设置Large-Address-Aware Executables标志也可为1:3)。这并不意味着内核使用那么多物理内存，仅表示它可支配这部分地址空间，根据需要将其映射到物理内存。
根据Linux内核相关文档描述,内存排布如下
========================================================================================================================
Start addr | Offset | End addr | Size | VM area description
========================================================================================================================
| | | |
0000000000000000 | 0 | 00ffffffffffffff | 64 PB | user-space virtual memory, different per mm
__________________|____________|__________________|_________|___________________________________________________________
| | | |
0000800000000000 | +64 PB | ffff7fffffffffff | ~16K PB | ... huge, still almost 64 bits wide hole of non-canonical
| | | | virtual memory addresses up to the -64 PB
| | | | starting offset of kernel mappings.
__________________|____________|__________________|_________|___________________________________________________________
|
| Kernel-space virtual memoryKernel-space virtual memory, shared between all processes:
____________________________________________________________|___________________________________________________________
| | | |
ff00000000000000 | -64 PB | ff0fffffffffffff | 4 PB | ... guard hole, also reserved for hypervisor
ff10000000000000 | -60 PB | ff10ffffffffffff | 0.25 PB | LDT remap for PTI
ff11000000000000 | -59.75 PB | ff90ffffffffffff | 32 PB | direct mapping of all physical memory (page_offset_base)
ff91000000000000 | -27.75 PB | ff9fffffffffffff | 3.75 PB | ... unused hole
ffa0000000000000 | -24 PB | ffd1ffffffffffff | 12.5 PB | vmalloc/ioremap space (vmalloc_base)
ffd2000000000000 | -11.5 PB | ffd3ffffffffffff | 0.5 PB | ... unused hole
ffd4000000000000 | -11 PB | ffd5ffffffffffff | 0.5 PB | virtual memory map (vmemmap_base)
ffd6000000000000 | -10.5 PB | ffdeffffffffffff | 2.25 PB | ... unused hole
ffdf000000000000 | -8.25 PB | fffffdffffffffff | ~8 PB | KASAN shadow memory
__________________|____________|__________________|_________|____________________________________________________________
|
| Identical layout to the 47-bit one from here on:
____________________________________________________________|_____________________________________
| | | |
fffffc0000000000 | -4 TB | fffffdffffffffff | 2 TB | ... unused hole
| | | | vaddr_end for KASLR
fffffe0000000000 | -2 TB | fffffe7fffffffff | 0.5 TB | cpu_entry_area mapping
fffffe8000000000 | -1.5 TB | fffffeffffffffff | 0.5 TB | ... unused hole
ffffff0000000000 | -1 TB | ffffff7fffffffff | 0.5 TB | %esp fixup stacks
ffffff8000000000 | -512 GB | ffffffeeffffffff | 444 GB | ... unused hole
ffffffef00000000 | -68 GB | fffffffeffffffff | 64 GB | EFI region mapping space
ffffffff00000000 | -4 GB | ffffffff7fffffff | 2 GB | ... unused hole
ffffffff80000000 | -2 GB | ffffffff9fffffff | 512 MB | kernel text mapping, mapped to physical address 0
ffffffff80000000 |-2048 MB | | |
ffffffffa0000000 |-1536 MB | fffffffffeffffff | 1520 MB | module mapping space
ffffffffff000000 | -16 MB | | |
FIXADDR_START | ~-11 MB | ffffffffff5fffff | ~0.5 MB | kernel-internal fixmap range, variable size and offset
ffffffffff600000 | -10 MB | ffffffffff600fff | 4 kB | legacy vsyscall ABI
ffffffffffe00000 | -2 MB | ffffffffffffffff | 2 MB | ... unused hole
__________________|____________|__________________|_________|_____________________________________
我们只需要看user-space virtual memory和 Kernel-space virtual memoryKernel即可
地址排布
内核空间
内核总是驻留在内存中，是操作系统的一部分。内核空间为内核保留，不允许应用程序读写该区域的内容或直接调用内核代码定义的函数。
栈(stack)
栈又称堆栈，由编译器自动分配释放，行为类似数据结构中的栈(先进后出)。堆栈主要有三个用途：
- 为函数内部声明的非静态局部变量(C语言中称“自动变量”)提供存储空间。
- 记录函数调用过程相关的维护性信息，称为栈帧(Stack Frame)或过程活动记录(Procedure Activation Record)。它包括函数返回地址，不适合装入寄存器的函数参数及一些寄存器值的保存。除递归调用外，堆栈并非必需。因为编译时可获知局部变量，参数和返回地址所需空间，并将其分配于BSS段。
- 临时存储区，用于暂存长算术表达式部分计算结果或alloca()函数分配的栈内内存。
持续地重用栈空间有助于使活跃的栈内存保持在CPU缓存中，从而加速访问。进程中的每个线程都有属于自己的栈。向栈中不断压入数据时，若超出其容量就会耗尽栈对应的内存区域，从而触发一个页错误。此时若栈的大小低于堆栈最大值RLIMIT_STACK(通常是8M)，则栈会动态增长，程序继续运行。映射的栈区扩展到所需大小后，不再收缩。
Linux中ulimit -s命令可查看和设置堆栈最大值，当程序使用的堆栈超过该值时, 发生栈溢出(Stack Overflow)，程序收到一个段错误(Segmentation Fault)。注意，调高堆栈容量可能会增加内存开销和启动时间。
堆栈既可向下增长(向内存低地址)也可向上增长, 这依赖于具体的实现。本文所述堆栈向下增长。
堆栈的大小在运行时由内核动态调整。
堆(heap)
堆分配的堆内存是经过字节对齐的空间。堆管理器通过链表管理每个申请的内存，由于堆申请和释放是无序的，最终会产生内存碎片。堆内存一般由应用程序分配释放，回收的内存可供重新使用。若程序员不释放，程序结束时操作系统可能会自动回收。堆的末端由break指针标识，当堆管理器需要更多内存时，可通过系统调用brk()和sbrk()来移动break指针以扩张堆，一般由系统自动调用。
BSS段
BSS(Block Started by Symbol)段中通常存放程序中以下符号：
- 未初始化的全局变量和静态局部变量
- 初始值为0的全局变量和静态局部变量(依赖于编译器实现)
- 未定义且初值不为0的符号(该初值即common block的大小)
text段
存放程序执行代码(即CPU执行的机器指令)。一般C语言执行语句都编译成机器代码保存在代码段。通常代码段是可共享的，因此频繁执行的程序只需要在内存中拥有一份拷贝即可。代码段通常属于只读，以防止其他程序意外地修改其指令(对该段的写操作将导致段错误)。
DATA段
数据段通常用于存放程序中已初始化且初值不为0的全局变量和静态局部变量。数据段属于静态内存分配(静态存储区)，可读写。
我们主要看heap段
Heap模型
malloc所申请的内存主要从Heap区域分配（当然也可以用mmap来申请大块内存）.
Linux维护一个break指针，这个指针指向堆空间的某个地址。从堆起始地址到break之间的地址空间为映射好的，可以供进程访问；而从break往上，是未映射的地址空间，如果访问这段空间则程序会报错。
实现 malloc
分析
数据结构
一个简单可行方案是将堆内存空间以块（Block）的形式组织起来，可以使用结构体来实现。由两部分实现，数据区大小、空闲标志位、指针，数据区是真实分配的内存区域，并数据区的第一个字节地址即为malloc返回的地址。
struct mem_control_block
{
int is_available; 是否可用
int size; 大小
};
寻找block
1. If our allocator has not been initialized, initialize it. //如果我们的分配器尚未初始化，请初始化它。
2. Add sizeof(struct mem_control_block) to the size requested.
3. start at managed_memory_start.
4. Are we at last_valid address?
5. If we are:
A. We did not find any existing space that was large enough
-- ask the operating system for more and return that.
6. Otherwise:
A. Is the current space available (check is_available from
the mem_control_block)?
B. If it is:
i) Is it large enough (check "size" from the
mem_control_block)?
ii) If so:
a. Mark it as unavailable
b. Move past mem_control_block and return the
``pointer
iii) Otherwise:
a. Move forward "size" bytes
`b. Go back go step 4
C. Otherwise:
i) Move forward "size" bytes
ii) Go back to step 4
6.A.当前空间是否可用（检查是否来自“内存控制块”？
如果是：
i）它是否足够大（从
“内存控制块”？
“ii”如果是这样：
A.标记为不可用
B.移过mem_control_块并返回其指针
iii）否则：
A.向前移动“大小”字节
B.返回第4步
C.否则：
i）向前移动“大小”字节
ii）回到步骤4
free
void free(void *firstbyte) {
struct mem_control_block *mcb;
mcb = firstbyte - sizeof(struct mem_control_block);
//标记块是可用的
//mcb->is_available = 1;
return;
}
简单实现
#include <unistd.h>
int brk(void *addr);
void *sbrk(intptr_t increment);
void malloc_init(void);
int has_initialized=0;
void *managed_memory_start;
void *last_valid_address;
typedef struct
{
int is_available;// find available memory
int size;
}memory_control_block;
void *malloc(long numbytes);
void malloc_init(void);
void free(void *firstbyte);
void malloc_init(void)
{
last_valid_address=sbrk(0);//grab the last OS memory
//it is seted ,but not be using
managed_memory_start=last_valid_address;
has_initialized=1;
}
void free(void *firstbyte)
{
/*give a pointer to find the free block*/
memory_control_block *mcb;
mcb=firstbyte-sizeof(memory_control_block);
mcb->is_available=1; // marking it is available
return 0;
}
void *malloc(long numbytes)
{
void * current_location;// for find the free block
memory_control_block *current_location_mcb;
/*when find the free block,set the is_available=0
*/
void *memory_location;
if(!has_initialized)
{
malloc_init();
}
numbytes=numbytes+sizeof(memory_control_block);
current_location=managed_memory_start;
memory_location=0;
while(current_location!=last_valid_address) //begin till last
{
current_location_mcb=
(memory_control_block *)current_location;
if(current_location_mcb->is_available)
{
if(current_location_mcb->size>=numbytes) // set type
{
current_location_mcb->is_available=0;
/*set it being used*/
memory_location=current_location;
break;
}
current_location=current_location+current_location_mcb->size;
}
}
if(!memory_location) // exten the memory
{
sbrk(numbytes);// the_last_vaible
memory_location=last_valid_address;
last_valid_address+=numbytes;
current_location_mcb=memory_location;
current_location_mcb->is_available=0;
current_location_mcb->size= numbytes;
}
memory_location=sizeof(memory_control_block)+memory_location;
return memory_location;
}
缺陷
当分配内存时，在最坏的情形下，它将不得不遍历全部进程内存，这意味着操作系统将不得不花时间去向硬盘移入数据和从硬盘中移出数据。
高级管理在下一篇文章更新~~
参考
lea molloc是最流行的内存分配程序之一
内存管理参考中有很多关于内存管理参考资料和技术文章的链接
IBM开发者论坛中也有许多资料可以寻找
