linux-内存管理

Linux内存管理搜索与算法-引擎开发组-子嘉大纲概念介绍处理器内存模型Linux系统内存管理高级内存管理程序开发注意事项未来发展趋势概念介绍--物理，线性，逻辑地址--虚存--SWAP--MMU--TLB--CACHE--寻址过程第一章概念介绍物理、线性、逻辑地址–物理地址physicaladdress•用于在内存单元(memorycell)中寻址，该地址与内存的针脚(pin)相对应•256M，512M，1G，2G，4G，16G，24G，32G–逻辑地址logicaladdress•机器指令中包含的寻址模式，如存取操作数movax,ds:offset•X86的分段寻址模式–线性地址linearaddress•处理器位数相关•32,64,128位概念介绍虚存(virtualmemory)–定义•把内存与外存有机的结合起来使用，从而得到一个容量很大的“内存”，这是虚拟内存。进程不完全载入，就叫虚存。可以分成按需取页和按需取段两种方式•程序员不考虑实际内存大小，将整个线性地址空间作为自己看到的内存，利用磁盘作为内存后援–特点•看到的内存空间是整个线性空间，大小是2⁶⁴•物理内存不够就存磁盘•程序不必完全载入–本质=吹牛概念介绍MMU(memorymanagementunit)–内存管理单元–作用•将虚拟地址转换为内存实际的物理地址•产生缺页中断pagingfault•涉及寄存器：GDTLDTCR0CR3CSDSESFS概念介绍寻址过程–Phase1根据cs寄存器中的segmentselector获取segmentdescriptor•Segmentselector选择符，存的是索引•Segmentdescriptor描述符，存的是段基址Index13-bitTItableindictor1-bitRPLprivilegelevel2-bit概念介绍寻址过程–Phase1根据cs寄存器中的segmentselector获取segmentdescriptor概念介绍寻址过程–Phase2根据segmentdescriptor和偏移获取线性地址概念介绍寻址过程–Phase3根据线性地址获取物理地址概念介绍TLB(TranslationLookasideBuffer)–并行翻译缓冲区–作用•存放线性地址到物理地址的映射•加快线性地址到物理地址的翻译速度•减少对内存的大量访问•TLB以页还是具体的地址为单位呢？TranslationTLBLinearaddressmisshitphysicaladdress概念介绍cache–Why?•快设备与慢设备的gap•时间本地性，空间本地性•一切皆cacheProc/RegsL1-CacheL2-CacheMemoryDisk,Tape,etc.BiggerrFaster概念介绍cache–作用•缓存指令或者数据•一级cache，二级cachecache物理地址memorymisshit更新CacheIndex0123CacheDataByte00431:CacheTagExample:0x50Ex:0x010x50Storedaspartofthecache“state”ValidBit:31Byte1Byte31:Byte32Byte33Byte63:Byte992Byte1023:CacheTagByteSelectEx:0x009Blockaddress概念介绍cache—directedmapped:CacheDataCacheBlock0CacheTagValid:::CacheDataCacheBlock0CacheTagValid:::CacheIndexMux01Sel1Sel0CacheBlockCompareAdrTagCompareORHit概念介绍Cache—N-wayassociativeway–例子：2-way组关联cache•Index-set•Comparetag概念介绍总流程逻辑地址线性地址物理地址数据memory段表TranslationTLBcache概念介绍SWAP–定义•存放从物理内存中换出的内存页–系统中的SWAP•Linux的swap分区•Windows的虚拟地址处理器内存模型--乱序执行--内存操作与依赖类型--X86第二章处理器内存模型乱序执行outoforder–定义•将机器指令打散执行，非顺序执行–优势•一个clock可以执行更多的指令•充分利用处理器–例子•Readm1,eax•Readm2,ebx•Readm3,ecx处理器内存模型内存操作与依赖类型–操作类型•Read•write–依赖类型•ReadafterRead•ReadafterWrite•WriteafterRead在某些处理器上不属于hazard•WriteafterWrite•Alias•Writeafternon-relativewrite处理器内存模型内存操作与依赖类型•R1+R2-R3•R4+R5-R6•但是逻辑上是相关的•newnode-next=current;•Prev-next=newnode•在某些处理器上要这么写（X86不必）•newnode-next=current;•Memory_Barrier()•Prev-next=newnode处理器内存模型X86&SPARC–强一致性的内存模型内存指令–sfence:在sfence指令前的写操作当必须在sfence指令后的写操作前完成。–lfence：在lfence指令前的读操作当必须在lfence指令后的读操作前完成。–mfence：在mfence指令前的读写操作当必须在mfence指令后的读写操作前完成。LINUX系统内存管理--MEMORYZONE--BUDDYSYSTEM--系统自用内存管理SLAB--非连续内存VMALLOC--进程内存管理--PAGECACHE--系统调用READWRITEMMAP--页面替换算法PFRA第三章Linux系统内存管理Memoryzone–定义•物理内存的一块区域–分区原因•DMA只能访问0~16M的物理内存•32位系统上，系统空间3G~4G，只能访问1G的物理内存–分区•ZONE_DMA0~16M•ZONE_NORMAL16~896M•ZONE_HIGHMEM896M~•NoZONE_HIGHMEMin64bitarchitectureLinux系统内存管理Memoryzone–分布•0-4Kbios4K-640K各种卡640K-16M保留•16M~896M系统Linux系统内存管理Buddysystem–定义•分配单位是block4096字节•每个slot中的连续块个数相同。1,2,4,8,16,32,64,128,256,512,1024•假设某个slot有b个块，空闲块的起始地址都能被b*4096整除–数据结构•Zone_mem_map•Free_area_t•bitmapLinux系统内存管理BuddysystemLinux系统内存管理Buddysystem–分配allocate算法•Alloc_pages(zone,order)•在zone中找到合适的块•调用rmqueue来分配块Linux系统内存管理Buddysystem–释放free算法•__free_pages_ok(page,order)•如果需要做rebalanceing，直接将块插入到对应链表中•正常的话，释放该块–思考•Buddy以页为单位，如何处理小的申请？•对于buddy的分配请求，来自谁？•小物理内存申请来自谁？Linux系统内存管理slab–作用•为内核频繁分配或者释放固定长度小内存•区分内存访问，快者恒快，如processstruct•大小是2的幂，cache优化•减少访问buddy的次数，防止cacheflush–实现•Cache(不是那个cache哦~)withtype•Slab•ObjectLinux系统内存管理slab–图示Linux系统内存管理slab–图示Linux系统内存管理slab–其他•Cache_cache•外部slab•内部slab•Slab着色Linux系统内存管理非连续内存–vmallocLinux系统内存管理进程内存管理–管理的是什么？•虚存or物理内存？•谁来管理？内核态？用户态？•进程内存有多大？•管理的对象是什么？Linux系统内存管理进程内存管理–什么时候产生？变化？•命令行，执行程序•进程调用execve执行新程序•Mmaponfile•栈不够用了•IPC如pipe•扩展堆malloc•程序退出，销毁•接口：brk，sbrk，mmap，munmap，shmat，shmdt，execve，exit，forkLinux系统内存管理进程内存管理–管理单元•Mm_struct/kernelthreadmm_struct•Memoryregionvm_area_structLinux系统内存管理进程内存管理–Memoryregion大小变化Linux系统内存管理进程内存管理–Memoryregion查询管理—红黑树Linux系统内存管理进程内存管理–Memoryregion查找•Find_vma起始地址=查找地址=结束地址•Find_vma_intersection找有交集的第一个memoryregion•arch_get_unmapped_area查找从addr开始的长度为len的空区域–Memoryregion插入•insert_vm_struct插入一个memoryregionLinux系统内存管理进程内存管理–分配一段线性地址空间do_mmap•检查参数合法性•获取空闲区域Arch_get_unmapped_area•计算新的flags•find_vma_prepare•检查内存是否超越限制•分配vm_area_struct•检查是否需要分配页表•返回vm_area_struct的线性地址–释放do_unmapLinux系统内存管理进程内存管理–Pagefault缺页中断Linux系统内存管理进程内存管理–Demandpaging•Handle_pte_fault–Copyonwrite•Fork会产生什么结果？–为页表分配物理页–为所有页分配新的物理页–初始化新的页表–然后将父进程的数据复制到子进程中•只copy_page_tablesLinux系统内存管理进程内存管理–创建进程空间•Clonecopy_mm–销毁进程空间•Mm_releaseLinux系统内存管理进程内存管理–堆管理•Brkmmap系统调用•Malloccallocfreesbrk•Brk以页为单位分配内存•小内存用brk，大内存用mmapLinux系统内存管理Pagecache–定义•内存对磁盘数据的cache•减少对磁盘的访问–场景•存放目录，文件数据•Mmap文件的数据•直接从块设备读出来的数据•Swap出去的数据•IPC共享内存区•主要是和文件相关Linux系统内存管理Pagecache–数据结构•Address_space•Radixtree•BufferpageLinux系统内存管理read–参数•Filpfileobject•Buf用户态buffer•Count•Ppos偏移–步骤用户空间Pagecache磁盘读请求Copy_to_userLinux系统内存管理write–参数•filefileobject•Buf用户态buffer•Count•Ppos偏移–步骤用户空间Pagecache磁盘写请求Copy_from_userLinux系统内存管理mmap–为何需要mmap？–数据结构Linux系统内存管理页面替换算法PFRA–设计哲学•优先回收没有被引用的disk和memorycache，最好不修改页表•所有用户空间的page都是可回收的•回收共享page时解除所有引用•只回收inactivepage，LRU算法Linux系