一例ubuntu 16内核crash分析：radix tree相关（上）
我们的分布式存储业务遇到了几例宕机，业务方用到fuse文件系统，ubuntu 16系统，内核4.10，宕机现场很奇怪，本文主要总结排查过程和涉及的内核知识。
文章涉及的内容有：radix tree的基本知识和一个特殊使用场景、ubuntu 16 kdump遇到的坑、内存回收等等。文章最后还提到了ubuntu 16使用的4.1*版本内核的一些坑，这对使用ubuntu服务器的小伙伴应该有帮助。水平有限，若本文出现什么错误，请各位读者指出。
1. 谁占用了shrinker_rwsem锁
存储同学首先反馈业务工作不正常，ps看到有很多D状态的进程，cat /proc/进程ID/stack查看栈回溯信息。
[] call_rwsem_down_write_failed+0x17/0x30[] register_shrinker+0x3d/0x90[] sget_userns+0x485/0x4a0[] sget+0x7d/0xa0[] mount_nodev+0x30/0xa0[] fuse_mount+0x18/0x20[] mount_fs+0x38/0x160[] vfs_kern_mount+0x67/0x110[] do_mount+0x1e9/0xd20[] SyS_mount+0x95/0xe0[] entry_SYSCALL_64_fastpath+0x1e/0xad[] 0xffffffffffffffff
很明显是在 register_shrinker()函数阻塞在 down_write()锁调用里。shrinker_rwsem锁只在3个函数出现过。
void register_shrinker(struct shrinker *shrinker){down_write(&shrinker_rwsem);list_add_tail(&shrinker->list, &shrinker_list);up_write(&shrinker_rwsem);}void unregister_shrinker(struct shrinker *shrinker){down_write(&shrinker_rwsem);list_del(&shrinker->list);up_write(&shrinker_rwsem);}unsigned long shrink_slab(struct shrink_control *shrink,unsigned long nr_pages_scanned,unsigned long lru_pages){struct shrinker *shrinker;unsigned long ret = 0;if (!down_read_trylock(&shrinker_rwsem)) {............}........do_shrinker_shrink(shrinker, shrink, 0);...........up_read(&shrinker_rwsem);}
根据代码分析，最大可能应该是某个进程执行shrink_slab()回收slab内存，先占有了shrinker_rwsem锁，然后执行do_shrinker_shrink()因为某种原因阻塞在某处。接着一旦有进程执行register_shrinker()函数，就必然阻塞在down_write()->call_rwsem_down_write_failed()（读写锁互斥），并且进程是不可中断的休眠状态，即D状态。
如果这个假设成立，查看系统所有进程栈回溯信息，应该会有所发现。但是在栈回溯信息里搜索"shrink_slab"、"shrink"、"do_shrinker_shrink"等关键字，没有任何发现。难道根本没有进程执行shrink_slab()->do_shrinker_shrink()函数后阻塞？或者这个进程莫名其妙退出？
观察两天前的内核日志有了一个发现，是一个内核crash现场，日志如下：
[] BUG: unable to handle kernel NULL pointer dereference at 0000000000000190[] IP: __radix_tree_replace+0xaa/0x100[] PGD 0[][] Oops: 0000 [............................[] CPU: 59 PID: 474 Comm: kswapd1 Not tainted 4.10.0-28-generic...........................[] task: ffff9755ef2d0000 task.stack: ffffaddbce7e4000[] RIP: 0010:__radix_tree_replace+0xaa/0x100[] RSP: 0018:ffffaddbce7e78c8 EFLAGS: 00010097[] RAX: 000000000000002d RBX: 0000000000000000 RCX: 0000000000000000[] RDX: ffff975800000188 RSI: 000000000000002d RDI: ffff975800000160[] RBP: ffffaddbce7e78e8 R08: 0000000000000000 R09: ffff975800000189[] R10: ffffaddbce7e7918 R11: 0000000000000040 R12: ffffffff8a7e3370[] R13: ffff975800000180 R14: ffff975800000178 R15: 0000000000000001[] FS: 0000000000000000(0000) GS:ffff9765fd740000(0000) knlGS:0000000000000000[] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033[] CR2: 0000000000000190 CR3: 0000000b7bc09000 CR4: 00000000007406e0[] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000[] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400[] PKRU: 55555554[] Call Trace:[] __delete_from_page_cache+0x153/0x3e0[] delete_from_page_cache+0x54/0xe0[] truncate_inode_page+0x8c/0xc0[] truncate_inode_pages_range+0x1b8/0x940[] ? __inode_wait_for_writeback+0x72/0xe0[] truncate_inode_pages_final+0x4d/0x60[] fuse_evict_inode+0x19/0x60[] evict+0xc7/0x1a0[] iput+0x1bb/0x240[] dentry_unlink_inode+0xc1/0x160[] __dentry_kill+0xbe/0x160[] shrink_dentry_list+0x111/0x310[] prune_dcache_sb+0x5a/0x80[] super_cache_scan+0x119/0x1a0[] shrink_slab.part.40+0x1fa/0x430[] shrink_slab+0x29/0x30[] shrink_node+0x108/0x320[] kswapd+0x34b/0x720[] kthread+0x109/0x140[] ? mem_cgroup_shrink_node+0x180/0x180[] ? kthread_create_on_node+0x60/0x60[] ret_from_fork+0x2c/0x40..................[] ---[ end trace a87eeba1d3bec073 ]---[] bash: page allocation stalls for 10068ms, order:1, mode:0x16040c0(GFP_KERNEL|__GFP_COMP|__GFP_NOTRACK)[] CPU: 4 PID: 99290 Comm: bash Tainted: G D 4.10.0-28-generic[] Hardware name: Dell Inc. PowerEdge R740xd/06WXJT, BIOS 2.8.2 08/27/2020
这是一个内存回收过程触发的dentry/inode slab回收环节：遍历dentry链表，释放dentry结构。如果dentry->d_inode对应的inode引用计数为0，还会执行iput()->iput_final()函数释放inode对应的文件占用的内存资源(比如page cache)，最后还释放inode结构。
看栈回溯日志是最后释放文件有关page cache时非法内存访问触发了内核crash。大体一看只是一个常见的内核crash问题，但是实际问题很大。因为内核crash竟然没有重启或者卡死，系统还在正常运行，可以看下紧接着的”bash: page allocation stalls”这行日志的时间。内核crash后系统还正常运行了两天多是怎么做到的？
看下非法内存访问的处理过程一探究竟。首先，非法内存访问后会触发系统异常，然后被强制执行do_page_fault()函数。之后的流程是do_page_fault->__do_page_fault->bad_area_nosemaphore->__bad_area_nosemaphore->no_context，看下源码：
static noinline voidno_context(struct pt_regs *regs, unsigned long error_code,unsigned long address, int signal, int si_code){//这里打印"BUG: unable to handle kernel"show_fault_oops(regs, error_code, address);sig = SIGKILL;if (__die("Oops", regs, error_code))sig = 0;//这里打印CR2: 0000000000000190printk(KERN_DEFAULT "CR2: %016lx\n", address);oops_end(flags, regs, sig);}void __kprobes oops_end(unsigned long flags, struct pt_regs *regs, int signr){//kdump配置情况，应该执行crash_kexec()启动kdump后，就一去不复返了，下边的代码就不会被执行到if (regs && kexec_should_crash(current))crash_kexec(regs);//启动crash//这里打印"---[ end trace %016llx ]---"oops_exit();if (!signr)//signr是SIGKILL，不成立return;if (in_interrupt())//不成立panic("Fatal exception in interrupt");if (panic_on_oops)//ubuntu 16不成立panic("Fatal exception");//这里重启//当前进程退出do_exit(signr);}
重点是panic_on_oops 变量，它默认int panic_on_oops = CONFIG_PANIC_ON_OOPS_VALUE；ubuntu 16系统的 CONFIG_PANIC_ON_OOPS_VALUE 配置是0，查看/boot/config-4.10.0-28-generic文件即可知道。
好的，现在问题基本清楚了，ubuntu 16系统默认没有安装kdump，panic_on_oops也没配置，导致非法内存访问处理的最后oops_end()函数没有启动kdump服务，也没有执行panic("Fatal exception")重启，最后只执行了do_exit(signr)使当前进程退出。
根据以上分析，再结合内核crash的栈回溯日志，做个简单总结：
kswapd1 进程在内存在执行shrink_slab()回收内存时，先执行down_read_trylock(&shrinker_rwsem)占用了shrinker_rwsem锁，然后执行do_shrinker_shrink()一路回收slab内存，但是在释放page cache时触发非法内存访问，又由于ubuntu 16没有安装kdump也没有配置panic_on_oops，导致kswapd1 进程只是执行do_exit进程退出。当然，退出时肯定没有释放shrinker_rwsem锁。之后其他进程执行register_shrinker()函数获取shrinker_rwsem锁失败而被迫D状态休眠。
现在需要明确两点：
问题的根本原因是内存回收最后释放文件资源page cache 发生了非法内存访问.
需要让ubuntu 16 kdump工作起来，保证非法内存访问触发内核crash后，kdump把宕机现场日志保存到vmcore，然后就可以详细分析宕机原因。
当然也得配置panic_on_oops，这个执行echo 1 >/proc/sys/kernel/panic_on_oops 命令即可。
2. ubuntu 16 kdump的那些坑
ubuntu 16安装kdump执行apt install kdump-tools即可(然后需重启一次生效)，配置kdump的预留内存却很容易遇到问题。查看系统预留了多少内存执行cat /proc/cmdline，会有”crashkernel=384M-:128M”类似打印，这表示如果物理机内存大于384M则为kdump预留128M内存，如果物理内存小于384M则不预留内存；如果”crashkernel=384M-2G:128M,2G-:256M”,则表示如果物理内存在384M到2G之间则预留128M内存，如果物理内存大于2G则预留256M内存。
怎么配置kdump的预留内存？需要先修改/etc/default/grub.d/kdump-tools.cfg文件的”crashkernel=384M-:128M”，然后执行update-grub使新的配置文件写入grub的crashkernel相关配置文件。最后重启，新的预留内存才能生效。重启后，执行cat /proc/cmdline，看crashkernl=***是否是自己配置的预留内存。
ubuntu 16系统对kdump预留的内存要求很高，早期测试某业务的ubuntu机器时，需要预留2G内存才能保证宕机后kdump正常运行、成功保存vmcore并重启，否则就宕机后卡死。配置2G预留内存用上边的方法不行，看内核reserve_crashkernel()函数后，需要这样修改”crashkernel=2G,high”。
本次遇到的问题，为kdump预留2G内存，手动触发宕机后会卡死。之后尝试了3G、5G、10G预留内存，发现只有预留10G内存，才能覆盖各个场景，实现宕机后kdump启动正常并成功保存vmcore最后自动重启。有些机器配置3G预留内存，手动触发宕机可以，但是业务运行后触发了宕机竟然又卡死。卡死前的截图找了几个如下：
看着应该是启动服务时卡死的，难道宕机前业务进程启动的一些服务也会影响kdump启动过程的内存分配？之前只了解过，kdump启动过程会因为外设驱动分配过多内存而OOM卡死，现在似乎kdump启动的服务也会分配很多内存？不管事实怎么样，遇到ubuntu宕机后卡死，一直增大kdump的预留内存，应该都是可以解决问题的。
3. 宕机日志vmcore的分析
配置kdump 10G预留内存后，总算抓到了vmocre。启动crash命令分析vmcore，ubuntu系统的vmcore是形如dump.***文件。
KERNEL: /usr/lib/debug/boot/vmlinux-4.10.0-28-generic...................VERSION: #32~16.04.2-Ubuntu SMP Thu Jul 20 10:19:48 UTC 2017MACHINE: x86_64 (3100 Mhz)MEMORY: 127.6 GBPANIC: "BUG: unable to handle kernel NULL pointer dereference at 0000000000000190"PID: 468COMMAND: "kswapd1"TASK: ffff95022f2e8000 [THREAD_INFO: ffff95022f2e8000]CPU: 37STATE: TASK_RUNNING (PANIC)btPID: 468 TASK: ffff95022f2e8000 CPU: 37 COMMAND: "kswapd1"#0 [fffface18e7bb5a0] machine_kexec at ffffffff8a85eef0#1 [fffface18e7bb600] __crash_kexec at ffffffff8a91c74d#2 [fffface18e7bb6c8] __crash_kexec at ffffffff8a91c825#3 [fffface18e7bb6e0] crash_kexec at ffffffff8a91c86b#4 [fffface18e7bb700] oops_end at ffffffff8a83095b#5 [fffface18e7bb728] no_context at ffffffff8a86e76e#6 [fffface18e7bb788] __bad_area_nosemaphore at ffffffff8a86ea31#7 [fffface18e7bb7d8] bad_area_nosemaphore at ffffffff8a86eb84#8 [fffface18e7bb7e8] __do_page_fault at ffffffff8a86ef2e#9 [fffface18e7bb850] do_page_fault at ffffffff8a86f362#10 [fffface18e7bb870] page_fault at ffffffff8b0d52e8RIP: __radix_tree_replace+170]RIP: ffffffff8ac4e58a RSP: fffface18e7bb928 RFLAGS: 00010097RAX: 000000000000002d RBX: 0000000000000000 RCX: 0000000000000000RDX: ffff950000000188 RSI: 000000000000002d RDI: ffff950000000160RBP: fffface18e7bb948 R8: 0000000000000002 R9: ffff950000000189R10: fffface18e7bb960 R11: 0000000000000040 R12: ffffffff8a9e3370R13: ffff950000000180 R14: ffff950000000178 R15: 0000000000000000ORIG_RAX: ffffffffffffffff CS: 0010 SS: 0018#11 [fffface18e7bb950] clear_shadow_entry at ffffffff8a9c3b67#12 [fffface18e7bb9a0] truncate_exceptional_entry at ffffffff8a9c3ba3#13 [fffface18e7bb9b0] truncate_inode_pages_range at ffffffff8a9c45c1#14 [fffface18e7bbb10] truncate_inode_pages_final at ffffffff8a9c4d5d#15 [fffface18e7bbb30] fuse_evict_inode at ffffffff8ab63f59#16 [fffface18e7bbb48] evict at ffffffff8aa61ab7#17 [fffface18e7bbb70] iput at ffffffff8aa61d9b#18 [fffface18e7bbba0] dentry_unlink_inode at ffffffff8aa5bc61#19 [fffface18e7bbbc0] __dentry_kill at ffffffff8aa5d30e#20 [fffface18e7bbbe8] shrink_dentry_list at ffffffff8aa5d8d1#21 [fffface18e7bbc30] prune_dcache_sb at ffffffff8aa5ed2a#22 [fffface18e7bbc68] super_cache_scan at ffffffff8aa47ef9#23 [fffface18e7bbcc0] shrink_slab at ffffffff8a9c655a#24 [fffface18e7bbda0] shrink_slab at ffffffff8a9c67b9#25 [fffface18e7bbdb0] shrink_node at ffffffff8a9cb078#26 [fffface18e7bbe38] kswapd at ffffffff8a9cc0cb#27 [fffface18e7bbf00] kthread at ffffffff8a8a8de9#28 [fffface18e7bbf48] ret_from_fork at ffffffff8b0d413ckmem -iPAGES TOTAL PERCENTAGETOTAL MEM 30215814 115.3 GB ----FREE 1449392 5.5 GB 4% of TOTAL MEMUSED 28766422 109.7 GB 95% of TOTAL MEMSHARED 24071130 91.8 GB 79% of TOTAL MEMBUFFERS 495887 1.9 GB 1% of TOTAL MEMCACHED 25574356 97.6 GB 84% of TOTAL MEMSLAB 1334037 5.1 GB 4% of TOTAL MEM
宕机前内存消耗挺多的并触发了内存回收，并且宕机现场与之前的基本一致，除了栈回溯日志最后的几个函数有差异。
根据宕机是的PC值ffffffff8ac4e58a查看在哪个函数：
sym 0xffffffff8ac4e58affffffff8ac4e58a (T) __radix_tree_replace+170 /build/linux-hwe-vH8Hlo/linux-hwe-4.10.0/lib/radix-tree.c: 1038
是在delete_sibling_entries()函数的if (node->slots[offset + i] != ptr)那一行，相关源码如下：
static inline void delete_sibling_entries(struct radix_tree_node *node,void **slot){bool exceptional = radix_tree_exceptional_entry(*slot);void *ptr = node_to_entry(slot);unsigned offset = get_slot_offset(node, slot);int i;for (i = 1; offset + i < RADIX_TREE_MAP_SIZE; i++) {if (node->slots[offset + i] != ptr)break;node->slots[offset + i] = NULL;node->count--;if (exceptional)node->exceptional--;}}
__radix_tree_replace()函数调用了delete_sibling_entries()，源码如下：
void __radix_tree_replace(struct radix_tree_root *root,struct radix_tree_node *node,void **slot, void *item,radix_tree_update_node_t update_node, void *private){if (!item)delete_sibling_entries(node, slot);replace_slot(root, node, slot, item,!node && slot != (void **)&root->rnode);if (!node)return;if (update_node)update_node(node, private);delete_node(root, node, update_node, private);}
看下汇编代码：
crash> dis __radix_tree_replace0xffffffff8ac4e4e0 <__radix_tree_replace>: push %rbp0xffffffff8ac4e4e1 <__radix_tree_replace+1>: test %rcx,%rcx0xffffffff8ac4e4e4 <__radix_tree_replace+4>: mov %rsp,%rbp........//对应offset = get_slot_offset(node, slot)的return slot-parent->slots那一行，类似rax=parent->slots，struct radix_tree_node *parent的成员slots偏移0x280xffffffff8ac4e55d <__radix_tree_replace+125>: lea 0x28(%rsi),%rax.......//offset + i < RADIX_TREE_MAP_SIZE0xffffffff8ac4e57f <__radix_tree_replace+159>: cmp $0x3f,%eax0xffffffff8ac4e582 <__radix_tree_replace+162>: ja 0xffffffff8ac4e4fc <__radix_tree_replace+28>0xffffffff8ac4e588 <__radix_tree_replace+168>: mov %eax,%esi//这一行发生的crash0xffffffff8ac4e58a <__radix_tree_replace+170>: cmp 0x28(%rbx,%rsi,8),%r90xffffffff8ac4e58f <__radix_tree_replace+175>: jne 0xffffffff8ac4e4fc <__radix_tree_replace+28>.........
导致crash的指令”0x28(%rbx,%rsi,8)”，可以理解成 0x28 + rbx + rsi*8，crash现场，rbx=0,rsi=0x2d，则0x28(%rbx,%rsi,8)=0x28 + 0 + 0x2d*8=0x190。
而crash时打印"BUG: unable to handle kernel NULL pointer dereference at 0000000000000190"，正是非法访问内存0x190导致的crash。这不是巧合，发生了多例crash现场，都是这种情况。
再看导致crash的哪行指令对应的C代码”if (node->slots[offset + i] != ptr)”，struct radix_tree_node *node结构中的成员slots正是偏移0x28，slots是一个指针数组，每个成员占8个字节。
crash> struct radix_tree_node -ostruct radix_tree_node {[] unsigned char shift;[] unsigned char offset;[] unsigned char count;[] unsigned char exceptional;[] struct radix_tree_node *parent;[] void *private_data;union {[] struct list_head private_list;[] struct callback_head callback_head;};[] void *slots[64]; //十进制40十六进制0x28[] unsigned long tags[3][1];}
如果struct radix_tree_node *node=NULL，offset + i=0x2d，node->slots[offset + i]=0x28 + 0 + 0x2d*8=0x190正好成立。证据都指向__radix_tree_replace()和delete_sibling_entries()传递的struct radix_tree_node *node指针是NULL。当然还是有疑问的，如果struct radix_tree_node *node指针是NULL，crash信息应该是”BUG: unable to handle kernel NULL pointer dereference at 0000000000000000”，难道与汇编指令有关？
虽然有疑问，但是struct radix_tree_node *node指针是NULL的可能性还是很大的。查看高版本的内核对比一下？看了4.11版本的内核代码的的__radix_tree_replace()函数，它已经把delete_sibling_entries()函数剔除了，而是在__radix_tree_replace()->replace_slot()->replace_sibling_entries()函数实现了类似功能。这里把代码简单贴下。
void __radix_tree_replace(struct radix_tree_root *root,struct radix_tree_node *node,void __rcu **slot, void *item,radix_tree_update_node_t update_node, void *private){void *old = rcu_dereference_raw(*slot);int exceptional = !!radix_tree_exceptional_entry(item) -!!radix_tree_exceptional_entry(old);int count = calculate_count(root, node, slot, item, old);replace_slot(slot, item, node, count, exceptional);..........}static void replace_slot(void __rcu **slot, void *item,struct radix_tree_node *node, int count, int exceptional){if (node && (count || exceptional)) {node->count += count;node->exceptional += exceptional;replace_sibling_entries(node, slot, count, exceptional);}rcu_assign_pointer(*slot, item);}static inline void replace_sibling_entries(struct radix_tree_node *node,void __rcu **slot, int count, int exceptional){void *ptr = node_to_entry(slot);unsigned offset = get_slot_offset(node, slot) + 1;while (offset < RADIX_TREE_MAP_SIZE) {if (rcu_dereference_raw(node->slots[offset]) != ptr)break;if (count < 0) {node->slots[offset] = NULL;node->count--;}node->exceptional += exceptional;offset++;}}
可以发现，这个版本内核对struct radix_tree_node *node是NULL是做了明确防护的。如果你手里有3.10内核的代码，也可以看下clear_shadow_entry()函数，对struct radix_tree_node *node是NULL的情况也做了明确防护。
说了这么多，其实一直是在代码角度验证struct radix_tree_node *node可能会是NULL，其实从radix tree原理来说，这种情况确实也是存在的。下文将讲解radix tree的基本知识，重点介绍radix tree的一种特殊用法，也是本次内核crash的关键。
4. radix tree基本知识
radix tree一般用来保存page cache的page指针，比如读写文件时产生了一个新的page cache，会执行add_to_page_cache()->add_to_page_cache_locked()->...->page_cache_tree_insert()函数把新的page指针插入到radix tree。每个文件唯一的struct inode的成员struct address_space* i_mapping指向文件对应的struct address_space。struct address_space的成员struct radix_tree_root page_tree维护了radix tree的根节点。
radix tree自身几个关键的数据结构struct radix_tree_root、struct radix_tree_node、void **slot，关键成员源码不再列了，1层radix tree用示意图展示如下：
radix_tree_root 的成员struct radix_tree_node *rnode指向radix tree的root node，即radix tree的第一个struct radix_tree_node结构。在radix tree树高度为1时，struct radix_tree_node的成员slots[64]保存的是64个插入到radix tree的page指针。page的索引page->index唯一决定了该page指针在radix tree的保存位置。如图所以，page0指针的page->index是0，故page0保存在slots[0]，page63的page->index是63，故page63指针保存在slot[63]。
slot的中文翻译是槽，它保存的是插入radix tree的对象，比如page指针，也可以保存子radix_tree_node指针。子radix_tree_node是什么？看下两层radix tree：
可以发现，root node的slots[0~63]保存的不再是page指针，而是子struct radix_tree_node结构指针相关数据node0~node63。node0的slots[0~63]保存的是page指针page0~page63(page后的数字0、63就是page->index索引)，node1的slots[0~63]保存的是page指针page64~page127，其他node类推，一共可以保存64*64个page指针。
可以发现，在两层radix tree，root node的slots[0~63]并不保存实际插入radix tree的page指针，而是子radix_tree_node结构指针相关数据。page0~page63指针保存在子radix_tree_node的node0的slots[0~63],page64~page127指针保存在子radix_tree_node的node1的slots[0~63]，其他可以类推出来。
关于struct radix_tree_node的成员需要说明一下，先列下重要成员：
struct radix_tree_node {unsigned char shift； /* Bits remaining in each slot */unsigned char offset； /* Slot offset in parent */unsigned int count;struct radix_tree_node *parent;void __rcu *slots[RADIX_TREE_MAP_SIZE];}
shift解释起来比较头疼，我的理解是它可以比作倍率。比如在单层radix tree树，root node的shift是0。在2层radix tree树，root node的shift是6，6代表2^6=64，就是说该root node的slots[0~63]中的任一个slot对应的子radix_tree_node，可以保存64个page指针。比如，root node的子radix_tree_node，如node0的slots[0~63]总计保存了page0~page63指针。而子radix_tree_node，如node0、node1等的shift是0，因为他们的slot[0~63]任一个slot只能保存1个page指针。有点绕.....
struct radix_tree_node的其他成员就比较好介绍了。offset表示在该radix_tree_node结构在父radix_tree_node的slots[0~63]数组的偏移。比如子node0的radix_tree_node 结构在父radix_tree_node即root node的slots[0]，偏移是0，node1的偏移是1。count表示当前radix_tree_node的slots[0~63]数组保存了多少个对象，不管是子radix_tree_node还是page指针，都算上。struct radix_tree_node *parent是当前radix_tree_node的父radix_tree_node结构指针。
radix tree的基本知识介绍完了，还有一个隐藏的知识点，对本案例至关重要。
请再看下2层radix tree树，问个问题，假如struct radix_tree_node node0结构的内存首地址是 0xffff910000000100，那struct radix_tree_node root node的slots[0]是0xffff910000000100吗？按照前文的逻辑，root node的slots[0]就应该保存子node0的struct radix_tree_node结构的首地址！实际却是0xffff910000000101，0xffff910000000100的bit0是1。
为什么会这样？这是radix tree的一个规则，只有插入radix tree的有效对象才会原封不动的保存到与该对象索引唯一对应的struct radix_tree_node的slot[0~63]，比如page0指针就是原封不动保存到与page0->index唯一对应的struct radix_tree_node的slot[0]。除此之外还有3种情况，保存到struct radix_tree_node的slot[0~63]时，bit0、bit1要置1，直接把内核的解释贴出来。
/** The bottom two bits of the slot determine how the remaining bits in the* slot are interpreted:** 00 - data pointer-----------------真正的page指针* 01 - internal entry---------------node 节点* 10 - exceptional entry------------exceptional entry* 11 - this bit combination is currently unused/reserved** The internal entry may be a pointer to the next level in the tree, a* sibling entry, or an indicator that the entry in this slot has been moved* to another location in the tree and the lookup should be restarted. While* NULL fits the 'data pointer' pattern, it means that there is no entry in* the tree for this index (no matter what level of the tree it is found at).* This means that you cannot store NULL in the tree as a value for the index.*/
如果是”internal entry”要保存到struct radix_tree_node的slot[0~63]，则要把原始指针的bit0置1然后再保存slot[0~63]。”internal entry”表示子radix_tree_node，比如前文的node0。所以前文node0对应的struct radix_tree_node结构内存首地址是0xffff910000000100时，它在父radix_tree_node即root node的slot[0]中实际却以0xffff910000000101保存。
”exceptional entry”应该跟”shadow entry”含义类似，它的定义是：a recently evicted page, a swap entry from shmem/tmpfs or a DAX entry。当然”exceptional entry”指针在radix tree的struct radix_tree_node的slot[0~63]保存时，它的bit1要置1，这是规则。
以上知识点在分析radix tree源码时至关重要，下一节简单分析下radix tree的关键源码，不长篇大论。
5. radix tree关键源码
一共3点，radix tree的对象插入、radix tree的对象查找、radix tree的对象删除，这些源码来自centos 7.6的3.10.0-957.27.2版本内核，原理相通。
5.1 radix tree的对象插入
static inline int radix_tree_insert(struct radix_tree_root *root,unsigned long index, void *entry){return __radix_tree_insert(root, index, 0, entry);}int __radix_tree_insert(struct radix_tree_root *root, unsigned long index,unsigned order, void *item){/*根据本次插入的对象item的索引index找到在radix tree的保存该对象的radix_tree_node，把该radix_tree_node指针保存到node局部变量。再找到item在该radix_tree_node的slots[0~63]数组中的保存位置，令局部变量slot指向这片内存*/error = __radix_tree_create(root, index, order, &node, &slot);//最终把待插入对象item保存到slot指向的radix tree的radix_tree_node的slots[0~63]rcu_assign_pointer(*slot, item);if (node) {//计算slot在父radix_tree_node->slot[]数组中保存的内存地址与radix_tree_node的slot[0~63]数组首地址的之差，就是slot相对父radix_tree_node的slot[0~63]首地址的偏移unsigned offset = get_slot_offset(node, slot);//node新插入了一个对象node->count++;}}
大部分源码注释已经写过，这里重点说下__radix_tree_create()函数，源码不再列了。它的流程可以这样描述：先找到根radix_tree_node即root node，接着根据待插入对象的索引index，从root node向下遍历找到保存它的子radix_tree_node和在这个子node的slots[0~63]数组中的保存位置。如果中途遇到子radix_tree_node没分配，还要重新分配子radix_tree_node，然后建立子radix_tree_node与父radix_tree_node的关系。
举个例子，就以前文两层radix tree为例，这里再把它的示意图发下
当索引index是0的page0指针要插入radix tree，首先找到的是root node，root node的shift是6。index>>6=0，说明page0要保存在root node的slots[0]或者与slot[0]指向的子node。因为root node的slots[0]保存的node0指针bit0是1，说明这是个”internal entry”，即是个子radix_tree_node。把slots[0]的bit0清0才是node0的radix_tree_node结构真正的内存首地址。
接着要进行下一轮循环，node0的shift是0，index>>0=0,则page0指针要保存在node0的slots[0]。最终找到了保存page0指针的radix_tree_node和在radix_tree_node的slots[0~64]数组的位置。
5.2 radix tree的对象查找
主要看__radix_tree_lookup()函数。
void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index,struct radix_tree_node **nodep, void ***slotp){struct radix_tree_node *node, *parent;unsigned long maxindex;void **slot;restart://parent 首先赋值NULLparent = NULL;slot = (void **)&root->rnode;//slot首先指向root->rnode//获取root node，然后node指向root->rnoderadix_tree_load_root(root, &node, &maxindex);if (index > maxindex)return NULL;//如果node的bit0不是1，则不是internel node，退出while循环while (radix_tree_is_internal_node(node)) {unsigned offset;if (node == RADIX_TREE_RETRY)goto restart;//把node的bit0清0parent = entry_to_node(node);/*根据本次插入对象的index计算保存它的radix_tree_node，返回值是它在radix_tree_node的slots[0~63]数组保存的位置的偏移*/offset = radix_tree_descend(parent, &node, index);//slot指向本次插入对象在radix_tree_node的slots[0~63]数组的保存位置slot = parent->slots + offset;}if (nodep)//保存本次对象的radix_tree_node*nodep = parent;//slot指向本次插入对象在radix_tree_node的slots[0~63]数组的保存位置if (slotp)*slotp = slot;//这里返回值一般是slot指向本次插入对象在radix_tree_node的slots[0~63]数组的保存位置原来的数据return node;}
它的核心环节与对象插入radix tree很像，都是要根据插入对象的索引找到保存它的radix_tree_node(保存到*nodep )和对象实际在radix_tree_node的slots[0~63]数组的保存位置（*slotp指向这片内存）。
5.3 radix tree的对象删除
一般函数流程是：
__delete_from_page_cache->page_cache_tree_delete->__radix_tree_delete_node->__radix_tree_delete_node。
把两个关键函数源码贴上。
bool __radix_tree_delete_node(struct radix_tree_root *root,struct radix_tree_node *node){bool deleted = false;do {struct radix_tree_node *parent;//如果node保存的还有对象if (node->count) {//如果radix tree只剩下一个root nodeif (node == entry_to_node(root->rnode))/*如果只剩下root node这一个node，并且这个node保存的对象只有1个，并且还保存在node的slots[0]，则把保存在node的slots[0]的这个对象直接移动到root->rnode，然后把root node释放，radix tree树高度变为0*/deleted |= radix_tree_shrink(root);return deleted;}/*执行到这里说明该node一个对象都没了，接下来把与这个node有关的全释放了*/parent = node->parent;//如果node有parent，则把node在parent->slots[node->offset]清NULL，并且parent->count减1，parent少了一个nodeif (parent) {parent->slots[node->offset] = NULL;parent->count--;} else {//否则就是只剩下一个root noderoot_tag_clear_all(root);root->rnode = NULL;}//释放noderadix_tree_node_free(node);deleted = true;//node指向parent，下个循环释放parent这个nodenode = parent;} while (node);return deleted;}
该函数的作用是从node所在的radix tree那一层开始，向上循环遍历radix tree，释放node，父node，父父node...一直到root node。释放的规则是看每个node->count是否为0,为0直接释放。如果遍历到root node，发现root node只有slot[0]还有这一个对象，则root->rnode=root node->slot[0]，然后把root node释放掉。此后，该radix tree就没有一个radix_tree_node，唯一的对象保存在struct radix_tree_root的成员struct radix_tree_node __rcu *rnode指针变量里。
static inline bool radix_tree_shrink(struct radix_tree_root *root){bool shrunk = false;for (;;) {//获取root nodestruct radix_tree_node *node = root->rnode;struct radix_tree_node *child;//如果root node不是internal node直接breakif (!radix_tree_is_internal_node(node))break;node = entry_to_node(node);//如果root node保存的对象有多则直接breakif (node->count != 1)break;//root node的node->slots[0]保存了一个对象，正常运行，否则直接breakchild = node->slots[0];if (!child)break;/*如果root node的slots[0]保存的对象不是internal node并且父node->shift不是0则break.但是如果此时radix tree只有一个root node，shift就是0，if不成立*/if (!radix_tree_is_internal_node(child) && node->shift)break;//如果root node的slots[0]保存的是internal node，则 slots[0]->parent=NULLif (radix_tree_is_internal_node(child))entry_to_node(child)->parent = NULL;/*如果root node的slots[0]保存的对象不是internal node，则把 slots[0]保存的对象直接赋于struct radix_tree_root *root的成员rnode*/root->rnode = child;/*如果root node的slots[0]保存的对象不是internal node则对保存它的root node->slots[0]的bit0清0x1。不清楚有啥意义，马上就要把node结构释放了*/if (!radix_tree_is_internal_node(child))node->slots[0] = RADIX_TREE_RETRY;//释放root noderadix_tree_node_free(node);shrunk = true;}return shrunk;}
函数radix_tree_shrink()的作用是：在root node只有slot[0]这一个对象(该对象索引是0)时，把root node的slot[0]保存的对象转移到root->rnode。需要声明一下，本文除了本节讲解radix tree的代码是3.10的内核代码时，其他几节内核代码都是ubuntu 4.10.0的。
前文提过，本案例与radix tree的一种特殊用法有关，这个特殊用法就是该小节提到的radix tree没有一个radix_tree_node，并且只有一个对象保存在radix_tree_root的成员rnode的情况。相信对radix tree熟悉的小伙伴可能已经猜到导致crash的具体的原因了，下篇将结合crash日志和radix tree源码进行一次深入分析。
☆ END ☆
OPPO互联网云平台团队招聘一大波岗位，涵盖Java、容器、Linux内核开发、产品经理、项目经理等多个方向，请在公众号后台回复关键词“云招聘”查看查详细信息。
更多技术干货
扫码关注
OPPO互联网技术