现象

之前一直稳定运行了很久的内核ko模块突然功能失灵，通过dmesg命令查看内核信息，发现该模块提示内存页分配失败，如下图所示

当时看到 "Failed to allocate memory for ip_entry" 字样，第一反应就是内存不足，直接用命令free -h命令查看系统内存

从图中看到空闲的内存有890M，按道理，空闲内存应该是够用的，ip_entry这个数据结构怎么也不至于用掉890M以上的内存。于是再看堆栈信息，看到一个关键信息：page allocation failure，这个信息表示系统无法分配高阶内存（所谓的高阶内存，指的是大块的连续物理内存，内存分配原理可查看本文下面的“内存分配算法”），使用命令查看内存页的分配情况：cat /proc/buddyinfo

可以看到内存的碎片化情况很严重，存在大量的低阶内存页，但缺少64KB以上的高阶内存页（红框表示64KB以上的内存页数量都为0）

分析ip_entry

既然系统缺少64KB以上的内存页，那么是否说明ip_entry这个数据结构要大于64KB呢，于是写程序用sizeof函数来测试这个数据结构，因为这个数据而机构用到了内核的函数，所以要和系统的源码一起编译成ko文件，不能直接在用户态调用sizeof函数。

• 编写Hello.c

#include <linux/rcupdate.h>
#include <linux/rbtree.h>
#include <linux/init.h>
#include <linux/module.h>
#include <asm/thread_info.h>
#include <linux/sched.h>

struct interval_tree_node {
    struct rb_node rb;
    unsigned long start;    
    unsigned long last;
    unsigned long __subtree_last;
};

struct ip_entry {
    struct rcu_head    rhead;
    struct ip_entry *next;
    struct ip_entry **pprev;
    struct interval_tree_node node;
    int type;
    __be32 saddr;
    __be32 mask;
    ktime_t timestamp;
    u64 nr_hits[NR_CPUS];
};

static int test_init(void)
{
    printk("---Insmod---");
    return 0;
}

static void test_exit(void)
{    
    struct ip_entry e;
    int c;
    printk("sizeof int: %d\n", sizeof(c));
    printk("sizeof ip_entry: %d\n", sizeof(e));
    printk("---Rmmod---");
}

module_init(test_init);
module_exit(test_exit);
MODULE_LICENSE("GPL");

• 编写Makefile

CONFIG_MODULE_SIG=n
obj-m:=Hello.o
KDIR:=/lib/modules/$(shell uname -r)/build
PWD:=$(shell pwd)

default:
    $(MAKE) -C $(KDIR) M=$(PWD) modules

• 编译：执行make命令（注意，在ubuntu20系统上能编译成功，但是在往内核插入模块时会提示错误：insmod: ERROR: could not insert module Hello.ko: Invalid module format，所以只能用ubuntu16来编译）
• 插入内核模块：执行insmod Hello.ko，即可看到输出的内容（卸载内核模块的命令为：rmmod Hello）
  

从上图可以看到，在64位的系统上，int的大小为4Byte，ip_entry的大小为65640Byte，折合为64.1KB，而在本系统中，刚好没有了大于等于64KB的连续内存页，所以导致了内存页分配失败。

解决方法

释放内存

• 释放页缓存：echo 1 > /proc/sys/vm/drop_caches
• 释放目录和索引节点缓存：echo 2 > /proc/sys/vm/drop_caches
• 同时释放页、目录、索引节点缓存：echo 3 > /proc/sys/vm/drop_caches
  
  上述的操作是无害的，因为只会释放完全没有使用的内存对象，脏对象将继续被使用直到他们被写入磁盘中，所以内存中的脏对象并不会被释放。如果如果重复echo 3 > /proc/sys/vm/drop_caches不能再次释放缓存，可以先尝试echo 0 > /proc/sys/vm/drop_caches然后再执行echo 3 > /proc/sys/vm/drop_caches

内存压缩

当上面释放的内存也没有足够的高阶内存时，可以通过命令：echo 1 > /proc/sys/vm/compact_memory 进行内存压缩，但这个步骤比较消耗CPU

可以看到经过内存压缩后，释放了大量的高阶内存

Linux内存

伙伴系统

Linux系统使用了一个名为伙伴系统(buddy system)的内存分配算法，将所有的空闲页表（一个页表的大小为4K）分别链接到包含了11个元素的数组中，数组中的每个元素将大小相同的连续页表组成一个链表，页表的数量为：1,2,4,8,16,32,64,128,256，512,1024，所一次性可以分配的最大连续内存为1024个连续的4k页表，即4MB的内存。假设你想申请一个包括256个页表的内存，系统会首先查找数组中的第9个链表（即大小为256的链表），如果该链表为空，就继续查找大小为512的链表，如果找到了，就将512个页表划分为两个256，一个分配给进程，另一个就挂载到大小为256的链表上。如果大小为512的链表也是空，就会继续查找大小为1024的链表，仍然为空就返回一个错误。当一个页表被释放之后，相邻的两个页表就会合并成一个大的页框。

分配算法

当申请分配页的时候，如果无法从伙伴系统的空闲链表中获得页面，则进入慢速内存分配路径，率先使用低水位线尝试分配，若失败，则说明内存稍有不足，页分配器会唤醒 kswapd 线程异步回收页，然后再尝试使用最低水位线分配页。如果分配失败，说明剩余内存严重不足，会先执行异步的内存规整，若异步规整后仍无法分配页面，则执行直接内存回收，或回收的页面数量仍不满足需求，则进行直接内存规整，若直接内存回收一个页面都未收到，则调用 oom killer 回收内存。

内存碎片

• 内部碎片：假设一个进程需要3KB的物理内存，但是内存页的最小颗粒度是4KB，所以就有1KB的空闲内存无法利用
• 外部碎片：假设系统剩下的页表都不连续，此时系统就无法分配超过4KB的连续物理内存，从而导致内存溢出

参考文档

• 虚拟内存与物理内存 [https://blog.csdn.net/lvyibin890/article/details/82217193]
• Making sense of /proc/buddyinfo[http://andorian.blogspot.com/2014/03/making-sense-of-procbuddyinfo.html]
• 缓存清理[https://huataihuang.gitbooks.io/cloud-atlas/content/os/linux/kernel/memory/drop_caches_and_compact_memory.html]