入门写的材料，凑一篇o(╥﹏╥)o... 偏简单，偏内存

什么是匿名页和文件页？

匿名页

        匿名页，没有文件背景的页面，如stack，heap，数据段等；他们没有对应的硬盘文件，因此如果要交换，只能交换到虚拟内存 zram或者Linux的swap硬盘分区，此部分页面，如果系统内存不充分，可以被swap到swapfile或者硬盘的swap分区。

（安卓手机上是默认swappiness是60，不过为了减少文件页回收，都会选择上调，更多选择压入ZRAM）

文件页

        有文件背景的页面，比如代码段、比如read/write方法读写的文件、比如mmap读写的文件；他们有对应的硬盘文件，因此如果要交换，可以直接和硬盘对应的文件进行交换。内存紧张时，非dirty的文件页可以直接drop掉，所以这个也算作MemAvailable中。

cache包含文件页（active和inactive）  zram_swap中存的是匿名页

什么是内存碎片?

            造成堆利用率很低的主要原因是就是内存碎片。当虽然有未使用的内存但不能用来满足分配请求时，就会发生该现象。有两种形式的碎片：内部碎片（internal fragmentation）和外部碎片(external fragmentation)。

外部碎片（主要问题）

        当空闲内存合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求。

网上搜了个比喻，挺好理解：

        我们将信息比作货物，将存储空间比作仓库来举例子。假设，我们有编号为1、2、3、4、5、6的6间仓库库房，前天送来了一大宗货，依次装入了1、2、3、4、5号仓库，昨天又因故将4号库房的货物运走了，那么数值上说我们还有两间空仓库的空间，但是如果这时候送来两间仓库容量的货物但要求必须连续存放的话，我们实际上是装不下的。这时的4、6号仓库，就成为一种空间的碎片。由于这样的原因形成的空间碎片，我们称之为外部碎片。从上面的例子我们可以理解，外部碎片是可以通过一些措施来改善或者解决的。对于在硬盘上的外部碎片，我们通常用磁盘碎片整理来解决，对应上面的例子，就是将5号仓库的货物及时移动到新腾出的4号仓库，这样，1-4号仓库都是满的，而5、6号仓库则形成了有效的、连续的空间，能够适应新的应用要求了；对于内存中的外部碎片，我们内存管理中常用的页面管理形式，就是为了解决这个问题的。

内部碎片（这个很少了）

        当一个进程装入到固定大小的分区块（比如页）时，假如进程所需空间小于分区块，则分区块的剩余的空间将无法被系统使用

        还是沿用上面的例子，这次我们的6间仓库目前都是空置的，但是假设我们管理仓库的最小空间单位是间，今天运来了容量为2.5间仓库的货物，那也要占用我们1-3号3间仓库，尽管3号仓库还闲置着一半的空间，但是这半间仓库已经不能再利用了（因为是以间为最小单位么）；这时，我们的仓库中就形成了半间仓库的空间碎片，我们称之为内部碎片。仓库的有效容量只剩下3间仓库了。

内存分配原理及大体流程

内存分配原理

        在NUMA模型中，每个CPU都有自己的本地内存节点（memory node），而且还可以通过QPI总线访问其他CPU下挂的内存节点，访问本地内存要比访问其他CPU下的内存的快约30%。Android只有一个Node 0，这个就比较简单了。

        Linux中对所有的内存进行统一管理，但由于关联不同的CPU导致访问速度不同，因此又将内存划分为节点（node）；在节点内部，又进一步细分为内存域（zone），比如DMA_ZONE，Normal_ZONE，还有虚拟Movable_ZONE

ps: 提一下movable zone，就是设计用来防止碎片化，把Highmem和movable分配需求集中放到这个zone中，使得这个zone中都是可移动页面，方便页面规整。但是实际项目中这个zone基本都是空的

针对不同的用途，Linux内核将所有的物理页面划分到3类内存管理区域中：

ZONE_DMA:    该区域物理页面专供I/O设备的DMA使用，需要连续的缓冲区，不经过MMU使用物理地址访问内存。

ZONE_NORMAL：内核直接映射使用，一般存放kernal、mem_map数组等常用数据。

ZONE_HIGHMEM：高端内存，内核无法直接使用，存放用户数据、页表等不常用数据。安卓无

内核根据价值（HIGHMEM内存无依赖最廉价，DMA最昂贵数量少易用尽）为内存域定义了优先级，从高到低为：ZONE_HIGHMEM > ZONE_NORMAL > ZONE_DMA。优先选择距离较近的node，再选择优先级较高的zone。

      如果从某个zone申请内存失败，就使用node_zonelists，它定义了一个zone搜索列表（每一项代表一个zone），当从某个node的某个zone申请内存失败后，会搜索该列表，查找一个合适的zone继续分配内存。

      每个zone都有自己的伙伴系统（buddy system）。伙伴系统是基于内存块的内存管理策略，它将物理内存分成许多大小为2^n个page的内存块（其中n=0,1,2.....10，即最大内存块为4M），相同大小的内存块被链入同一个链表中。管理区描述符(struct zone)中，struct free_area用于描述伙伴系统。

      假设要分配一个n=3即2^3=8个page的内存块，算法首先搜索free_area[3]指定的链表，检查是否有空闲的内存块。如果有，直接从链表上摘取一个内存块；如果没有，算法会检查更大内存块的链表，即free_area[4]指定的链表，如果该链表有空闲块，则摘取一个空闲块并分割为大小相同的两部分（伙伴），一部分返回给内存申请者，另一部分加入到free_area[3]指定的链表中。如果free_area[4]指定的链表中也没有空闲块，则继续搜索更大的内存块链表，直至free_area[10]。

在分配页框的方式有两种：快速分配和慢速分配：

快速分配：会根据zonelist链表的优先级顺序，以zone的low阀值从相应zone的 伙伴系统中分配连续页框。

慢速分配：在快速分配失败之后执行，会根据zonelist链表的优先级顺序，以zone 的min阀值从相应zone的伙伴系统中分配连续页框。如果失败，会唤醒kswapd 内核线程，进行异步压缩、直接内存回收、oom以及轻同步压缩，进行内存回收，在这些内存回收操作的过程当中，几乎每一步会进行快速分配尝试获取内存，快速满足内存分配请求才是第一位。

内存分配流程

内存分配入口：alloc_pages(gfp_t gfp_mask, unsigned int order)

调用函数struct page *alloc_pages_current(gfp_t gfp, unsigned order)

再往下调用核心函数__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, int preferred_nid,nodemask_t *nodemask)

看下核心方法的具体流程： //参考kernel-4.19代码

1、先开始快速分配，调用get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,const struct alloc_context *ac) ac上下文包含里面的zonelist，遍历扫描zonelist，根据每个zone的水线watermark，zone_watermark_ok()查找到足够空闲的zone，在try_this_zone中查找可使用的页面返回，完成分配。在一些急迫的事务中，可以指定ALLOC_NO_WATERMARKS，这样会不会对水位进行验证。

2、 快速分配失败时，调用慢速分配方法__alloc_pages_slowpath(gfp_t gfp_mask,unsigned int order,struct  alloc_context *ac)。

3、慢速分配先进入retry_cpuset:首先调用wake_all_kswapds(order,ac),唤醒所有kswapd守护进程进行物理页面的回收（一般1-2个，linux可以设置为2个，Android考虑到功耗，一般只能设置为1个）。

4、再次调用get_page_from_freelist()进行快速分配。

5、还是分不出页面就调用__alloc_pages_direct_compact(gfp _mask, order,alloc_flags, ac,INIT_COMPACT_PRIORITY,&compact_result);在函数中继续调用 try_to_compact_pages()，继续调用for_each_zone_zonelist_nodemask()对zonelist中的每个zone进行内存压缩。在__alloc_pages_direct_compact()中再次调用get_page_from_freelist()，如果成功，函数返回page。

6、还是失败的话进入retry过程：首先唤醒所有回收线程，确保不会意外睡去。

7、尝试进行get_page_from_freelist()。

8、做一些校验，如果不能回收(reclaim)，就返回nopage。

9、调用回收方法__alloc_pages_direct_reclaim(gfp_mask, order, alloc_flags, ac,&did_some_progress)成功就返回page。

10、不成功就调用__alloc_pages_direct_compact()压缩内存，成功就返回page

11、参数判定决定是否重新从retry或者retry_cpuset开始执行。

12、到这步还是无法找到空闲页面，准备oom杀进程，调用方法__alloc_pages_may_oom(gfp_mask, order, ac, &did_some_progress)。

13、只要oom循环就一直进行retry直到找到空闲页面，进程结束就返回null。

内存回收原理及大体流程

内存回收原理

页面回收的方式（没有ZRAM，ZRAM的匿名页压缩放入ZRAM区域）

    1、页回写 存在脏页，即文件页在内存中有改动，将内存同步到设备

    2、页交换 匿名页，交换到swap分区，再次访问时换回内存

    3、页丢弃 文件页没有改动，或者不能修改，可直接丢弃

页面回收的时机

wartermark：水线，分为【WMARK_HIGH】、【WMARK_LOW】、【WMARK_MIN】。内核线程kswapd检测到不同的水线值会进行不同的处理，当空闲page数大于high时，不需要进行内存回收；当空闲page数低于low时，开始进行内存回收，将page换出到硬盘；当空闲page数低于min时，表示内存回收的压力很重，可用page数已经很少了，必须加快进行内存回收。

WMARK_MIN= min_free（单位为page），假设为min_free。（因为是每个zone各有一套watermark参数，实际计算效果是根据各个zone大小所占内存总大小的比例，而算出来的每个zone的min_free）

WMARK_LOW = WMARK_MIN * 5 / 4 + extra_free_kbytes

WMARK_HIGH = WMARK_MIN * 3 / 2

LRU(Least Recently Used)，近期最少使用链表，按照近期的使用情况排列，最少使用的存在链表末尾。每个zone有5个LRU链表：

        LRU_INACTIVE_ANON 非活动匿名页lru链表，PG_active=0

        LRU_ACTIVE_ANON 活动匿名页lru链表,PG_active=1

        LRU_INACTIVE_FILE  非活动文件页lru链表，PG_active=0

        LRU_ACTIVE_FILE 活动文件页lru链表，PG_active=0

        LRU_UNEVICTABLE zone中所有禁止换出的页

页面回收时，优先回收INACTIVE的页面。

        当内存块被释放时，算法首先会检查它的伙伴是否存在，如果不存在，直接将内存块加入到对应的链表中；如果存在，将两个伙伴合并为一个更大的内存块，并继续检查该内存块的伙伴是否存在，如果存在，继续向上合并，否则链入相应的链表。

        slab缓存回收相对比较灵活，所有注册到shrinker_list中的方法都会被执行。内核默认针对每个文件系统都注册了prune_super方法，这个函数用来回收文件系统中不再使用的dentry和inode缓存；android的lowmemorykiller机制注册了选择性杀死进程的方法，回收进程使用的内存。

页面回收具体流程见shrink_zone()。

内存回收流程

        shink_zone()可以将某些页面从active链表移到inactive链表，由shrink_active_list()实现的。接着从inactive链表中选定一定数目的页面，将其放到一个临时链表中，这由函数shrink_inactive_list()完成。该函数最终会调用shrink_page_list()去回收这些页面。函数shrink_page_list()返回的是回收成功的页面数目。函数shrink_slab()会遍历shrinker链表，从而对所有注册了shrinker函数的磁盘缓存进行处理。

shrink_zone()函数的流程：

先从root_memcg开始遍历memcg：

        1、获取memcg的lru链表描述符lruvec

        2、获取memcg的swapiness（会影响扫描页框的数量）

        3、调用shrink_lruvec()对此memcg的lru链表进行处理

shrink_lruvec()函数处理文件页和匿名页lru链表的流程为：

1. 调用get_scan_count()计算每个lru链表需要扫描的页框数量，保存到nr数组中

2. 循环判断nr数组中是否还有lru链表没有扫描完成

        以活动匿名页lru链表、非活动匿名页lru链表、活动文件页lru链表、非活动文件页lru链表的顺序作为一轮扫描，每次每个lru链表扫描32个页框，并且在nr数组中减去lru链表对应扫描的数量，扫描过程中，调用shrink_list()

      一轮扫描结束后判断是否回收到了足够页框，没有回收到足够页框则跳到 2 继续循环判断nr数组

        已经回收到了足够页框，当nr数组有剩余时，判断是否要对lru链表继续扫描，如果要继续扫描，则跳到2

3. 如果非活动匿名页lru链表中页数量太少，则对活动匿名页进行一个32个页框的扫描

4. 如果太多脏页正在进行回写，则睡眠

shrink_list()在处理过程如下：

先判断是否为活动lru链表，如果是，判断非活动lru链表的页数是否过少，过少就调用shrink_active_list()，否则调用shrink_inactive_list()处理非活动链表：

活动lru链表处理流程：

1、将本地cpu的lru缓存全部清空，将lru缓存的页放到lru链表中，而其他CPU的则不处理

2、根据sc->may_writepage与sc->may_unmap从链表尾部选择要隔离的页

3、如果结点buffer_heads数量超过限制值，则会尝试对扫描到的文件页进行buffer_heads的释放，进行释放后的文件页的page->_count--

4、将所有映射了隔离页的页表项Accessed都清0

5、将最近被访问过的代码段的页移动到活动lru链表头部，其余页都移动到非活动lru链表头

6、将page->_count = 0的页进行释放

        非活动lru链表处理流程与shrink_inactive_list()函数流程差不多，首先要求当前CPU的所有lru缓存将页放入到lru链表中，然后通过isolate_lru_pages()函数从活动lru链表末尾扫描出符合要求的页，这些页会通过page->lru加入到page_list链表中，然后调用shrink_page_list()对这个page_list链表中的页进行回收处理，之后将page_list链表中剩余的页放回到它们应该放入到链表中。

shrink_page_list()主要逻辑：

1、如果页面被锁住了，放入继续将页面保留在inactive list中，后就再扫描到底时候再试图回收这些page

2、如果回写控制结构体标记了不允许进行unmap操作，将那些在pte表项中有映射到页面保留在inactive list中。

3、对于正在回写中的页面，如果是同步操作，等待页面回写完成。如果是异步操作，将page继续留在inactive list中，等待以后扫描再回收释放。

4、如果检查到page又被访问了，这个时候page有一定的机会回到active list链表中。必须满足

    a. page被访问，page_referenced检查

    b. order小于3，也就是系统趋向于回收较大的页面。对于较小的页面 趋向于保留在active list中

    c. page_mapping_inuse检查

5、如果是匿名页面，并且不在swap缓冲区中，将page加入到swap的缓冲区

6、如果页面被映射了，调用unmap函数

7、如果页面是脏页，需要向将页面内容换出，调用pateout

8、如果页面和buffer相关联，将buffer释放掉，调用try_to_release_page函数，调用__remove_mapping 将页面回收归还伙伴系统

为何需要文件系统？手机主流文件系统概况（f2fs/ext4）

文件系统：

        Linux以文件的形式对计算机中的数据和硬件资源进行管理，也就是彻底的一切皆文件，反映在Linux的文件类型上就是：普通文件、目录文件（也就是文件夹）、设备文件、链接文件、管道文件、套接字文件（数据通信的接口）等等。而这些种类繁多的文件被Linux使用目录树进行管理， 所谓的目录树就是以根目录（/）为主，向下呈现分支状的一种文件结构。不同于纯粹的ext2之类的文件系统，我把它称为文件体系，一切皆文件和文件目录树的资源管理方式一起构成了Linux的文件系统，让Linux操作系统可以方便使用系统资源。

手机主流文件系统概况：

        文件系统的作用是确定如何在本地存储中存储和检索数据。Android操作系统通常使用ext4文件系统，相较于前代ext3文件系统，ext4能快速更新文件存储。

ext4:

        ext4文件系统从ext3/ext2文件系统继承发展而来，ext4相较于前代，Ext4的文件系统容量达到1EB，而文件容量则达到16TB；采用新的数据分配方式（持久性预分配、延时分配、多块分配）以及在线碎片整理来减少磁盘碎片化，此外还增加了元数据校验和，改进了时间戳和快速文件检查等功能。常用作存放系统文件，这种IO读写少的。

主要属性介绍：

Superblock:超级块，一个文件系统有一个，每个块组也会包含超级块的副本。含有文件系统的属性和接口：

    属性：文件系统的一些参数；

    接口：mount和umount接口等。

Inode：每个文件（包括文件夹）都有一个Inode，含有文件的属性和文件属性的接口。

    属性：文件名，创建时间，修改时间，访问权限，文件保存的LBA等；

    接口：创建，删除文件夹等。

Dentry ：每个目录都有一个，用来方便目录查找等。访问文件的时候，用户传递文件路径，VFS通过Hash树查找的方法直接通过路径查到最终Dentry，并找到inode，通过hash查找，最快一次就能找到，不需要逐级查找。

    属性：目录名等；

    接口：查找文件路径等。

File ：对文件进行操作的接口，常用于读写操作。

    属性：文件锁，当前访问的偏移地址等；

    接口：fopen，fclose，fwrite，fread，fsync，异步读写等。

inode bitmap：标签分布表，表示标签表inode table哪些条目是占用的，用一个bit是0或者1表示空或者非空。

block bitmap：盒子分布表，表示哪些盒子里面有数据，用一个bit是0或者1表示空或者非空

For example：

查找文件 example:/root/test/a.txt

（一）通过内核找到根目录/的inode

1、根据根目录/的inode，到inode table中找到根目录/的块指针

2、通过块指针找到根目录/的数据块，根据其中的数据找到下级目录/root/对应的inode

3、根据/root/对应的inode，到inode table中找到目录/root/的元数据及块指针

4、通过块指针找到存放目录/root/的数据块，根据其中数据找到/root/test/目录对应的inode

5、根据/root/test/目录对应的inode，到inode table中找到目录/root/test/的元数据及块指针

6、通过块指针找到存放目录/root/test/的数据块，根据其中数据找到文件/root/test/a.txt对应的inode

7、根据文件/root/test/a.txt对应的inode到inode table中找到文件/root/test/a.txt的元数据及块指针

8、通过块指针找到存放文件/root/test/a.txt的数据块

II.创建文件 example:/root/test/b.txt

1、扫描inode bitmap，找到一个空闲的inode，将其标记为占用，获取其对应的inode number

2、查找目录/root/test/的数据（过程参考I），并在其中添加一条目录项（dirent）记录，文件名为/root/test/b.txt，inode number在步骤1中已经获得

3、根据inode number，在inode table中找到该inode，记录文件/root/test/b.txt的部分元数据，如inode number、权限等等

4、扫描block bitmap，找到可分配的空闲块，标记为占用，并在文件/root/test/b.txt的元数据中记录块指针

5、在数据块中写入文件数据。

III.删除文件 example:/root/test/c.txt

1、查找文件/root/test/c.txt使用的元数据信息（过程参考I）

2、查找目录/root/test/的数据（过程参考I），并删除文件/root/test/c.txt的目录项（dirent）记录

3、修改文件/root/test/c.txt的元数据，将其链接数-1

4、如果此时文件/root/test/c.txt的链接数≤0，扫描block bitmap，将分配给文件的块节点标记为空闲

5、如果此时文件/root/test/c.txt的链接数≤0，扫描inode bitmap，将其中对应的节点标记为空闲

f2fs：

        f2fs全名为“Flash Friendly File System”这是一种专门为闪存而生的，较为新型的支持Linux内核的文件系统。最早是由三星在2012年研发设计的，其目的就是为了更好的适应 NAND 一类的闪存设备（例如固态硬盘、eMMC和SD卡等），在f2fs中三星应用了日志结构档案系统的概念，使它更适合用于储存设备。f2fs的优势通俗来说就是小文件的传输速率变快了。不过问题也很明显，将相同文件存储到f2fs文件格式下相较于ext4会占用1.1倍到1.5倍的空间。

        f2fs选择 log-structured文件系统方案，并使之更加适应新的存储介质(NAND)。同时，修复了旧式日志结构文件系统的一些已知问题，如wandering tree 的滚雪球效应和高清理开销。

        根据内部几何结构和闪存管理机制(FTL)，闪存存储设备有很多不同的属性，所以F2FS的设计者增加了多种参数，不仅用于配置磁盘布局，还可以选择分配和清理算法，优化性能(并行IO提高性能)。

ION内存概述

        ION是Google在Android4.0以后，为了解决内存碎片管理而引入的通用内存管理器。用户空间、内核驱动均可以使用ION分配内存，除此之外，ION也提供多个Client之间共享内存。SurfaceFlinger/Camera/Audio都常使用ION。

从2^8次方内存开始分配，一次就是1M。没有的话就是2^4，然后是2^0。本身有池

android S开始采用DMA_BUF替换ION，主要是为了让kernel社区接纳ion维护...其他变化不大

zsmalloc 用于内核内存压缩

dma_alloc_coherent DMA内存分配N个pages，目前kernel实现是从CMA中分配，物理连续