一例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查看栈回溯信息。

[<ffffffff8aa57a77>] call_rwsem_down_write_failed+0x17/0x30
[<ffffffff8a7c6b8d>] register_shrinker+0x3d/0x90
[<ffffffff8a8478d5>] sget_userns+0x485/0x4a0
[<ffffffff8a84796d>] sget+0x7d/0xa0
[<ffffffff8a8479c0>] mount_nodev+0x30/0xa0
[<ffffffff8a963998>] fuse_mount+0x18/0x20
[<ffffffff8a848688>] mount_fs+0x38/0x160
[<ffffffff8a866917>] vfs_kern_mount+0x67/0x110
[<ffffffff8a868fb9>] do_mount+0x1e9/0xd20
[<ffffffff8a869e25>] SyS_mount+0x95/0xe0
[<ffffffff8aed3ebb>] entry_SYSCALL_64_fastpath+0x1e/0xad
[<ffffffffffffffff>] 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现场，日志如下：

[2609428.025899] BUG: unable to handle kernel NULL pointer dereference at 0000000000000190
[2609428.025933] IP: __radix_tree_replace+0xaa/0x100
[2609428.025945] PGD 0
[2609428.025945]
[2609428.025958] Oops: 0000 [#1] SMP
............................
[2609428.026150] CPU: 59 PID: 474 Comm: kswapd1 Not tainted 4.10.0-28-generic #32~16.04.2-Ubuntu
...........................
[2609428.026184] task: ffff9755ef2d0000 task.stack: ffffaddbce7e4000
[2609428.026199] RIP: 0010:__radix_tree_replace+0xaa/0x100
[2609428.026210] RSP: 0018:ffffaddbce7e78c8 EFLAGS: 00010097
[2609428.026223] RAX: 000000000000002d RBX: 0000000000000000 RCX: 0000000000000000
[2609428.026239] RDX: ffff975800000188 RSI: 000000000000002d RDI: ffff975800000160
[2609428.026254] RBP: ffffaddbce7e78e8 R08: 0000000000000000 R09: ffff975800000189
[2609428.026270] R10: ffffaddbce7e7918 R11: 0000000000000040 R12: ffffffff8a7e3370
[2609428.026286] R13: ffff975800000180 R14: ffff975800000178 R15: 0000000000000001
[2609428.026301] FS:  0000000000000000(0000) GS:ffff9765fd740000(0000) knlGS:0000000000000000
[2609428.026319] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[2609428.026332] CR2: 0000000000000190 CR3: 0000000b7bc09000 CR4: 00000000007406e0
[2609428.026348] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
[2609428.026364] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
[2609428.026380] PKRU: 55555554
[2609428.026388] Call Trace:
[2609428.026401]  __delete_from_page_cache+0x153/0x3e0
[2609428.026412]  delete_from_page_cache+0x54/0xe0
[2609428.026425]  truncate_inode_page+0x8c/0xc0
[2609428.026437]  truncate_inode_pages_range+0x1b8/0x940
[2609428.026451]  ? __inode_wait_for_writeback+0x72/0xe0
[2609428.026463]  truncate_inode_pages_final+0x4d/0x60
[2609428.026476]  fuse_evict_inode+0x19/0x60
[2609428.026488]  evict+0xc7/0x1a0
[2609428.026496]  iput+0x1bb/0x240
[2609428.026506]  dentry_unlink_inode+0xc1/0x160
[2609428.026517]  __dentry_kill+0xbe/0x160
[2609428.026527]  shrink_dentry_list+0x111/0x310
[2609428.026537]  prune_dcache_sb+0x5a/0x80
[2609428.026549]  super_cache_scan+0x119/0x1a0
[2609428.027037]  shrink_slab.part.40+0x1fa/0x430
[2609428.027468]  shrink_slab+0x29/0x30
[2609428.027889]  shrink_node+0x108/0x320
[2609428.028297]  kswapd+0x34b/0x720
[2609428.028696]  kthread+0x109/0x140
[2609428.029091]  ? mem_cgroup_shrink_node+0x180/0x180
[2609428.029493]  ? kthread_create_on_node+0x60/0x60
[2609428.029899]  ret_from_fork+0x2c/0x40
..................
[2609428.031853] ---[ end trace a87eeba1d3bec073 ]---
[2775751.734928] bash: page allocation stalls for 10068ms, order:1, mode:0x16040c0(GFP_KERNEL|__GFP_COMP|__GFP_NOTRACK)
[2775751.735454] CPU: 4 PID: 99290 Comm: bash Tainted: G      D         4.10.0-28-generic #32~16.04.2-Ubuntu
[2775751.735877] 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 void
no_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: 0000000000000190
  printk(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状态休眠。

现在需要明确两点：

1. 问题的根本原因是内存回收最后释放文件资源page cache 发生了非法内存访问.

2. 需要让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 2017
     MACHINE: x86_64  (3100 Mhz)
      MEMORY: 127.6 GB
       PANIC: "BUG: unable to handle kernel NULL pointer dereference at 0000000000000190"
         PID: 468
     COMMAND: "kswapd1"
        TASK: ffff95022f2e8000  [THREAD_INFO: ffff95022f2e8000]
         CPU: 37
       STATE: TASK_RUNNING (PANIC)
crash> bt
PID: 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 ffffffff8b0d52e8
    [exception RIP: __radix_tree_replace+170]
    RIP: ffffffff8ac4e58a  RSP: fffface18e7bb928  RFLAGS: 00010097
    RAX: 000000000000002d  RBX: 0000000000000000  RCX: 0000000000000000
    RDX: ffff950000000188  RSI: 000000000000002d  RDI: ffff950000000160
    RBP: fffface18e7bb948   R8: 0000000000000002   R9: ffff950000000189
    R10: fffface18e7bb960  R11: 0000000000000040  R12: ffffffff8a9e3370
    R13: ffff950000000180  R14: ffff950000000178  R15: 0000000000000000
    ORIG_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 ffffffff8b0d413c
crash> kmem -i
                 PAGES        TOTAL      PERCENTAGE
    TOTAL MEM  30215814     115.3 GB         ----
         FREE  1449392       5.5 GB    4% of TOTAL MEM
         USED  28766422     109.7 GB   95% of TOTAL MEM
       SHARED  24071130      91.8 GB   79% of TOTAL MEM
      BUFFERS   495887       1.9 GB    1% of TOTAL MEM
       CACHED  25574356      97.6 GB   84% of TOTAL MEM
         SLAB  1334037       5.1 GB    4% of TOTAL MEM

宕机前内存消耗挺多的并触发了内存回收，并且宕机现场与之前的基本一致，除了栈回溯日志最后的几个函数有差异。

根据宕机是的PC值ffffffff8ac4e58a查看在哪个函数：

crash> sym 0xffffffff8ac4e58a
ffffffff8ac4e58a (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)
{
#ifdef CONFIG_RADIX_TREE_MULTIORDER
        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--;
        }
#endif
}

__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_replace
0xffffffff8ac4e4e0 <__radix_tree_replace>:      push   %rbp
0xffffffff8ac4e4e1 <__radix_tree_replace+1>:    test   %rcx,%rcx
0xffffffff8ac4e4e4 <__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偏移0x28
0xffffffff8ac4e55d <__radix_tree_replace+125>:  lea    0x28(%rsi),%rax
.......
//offset + i < RADIX_TREE_MAP_SIZE
0xffffffff8ac4e57f <__radix_tree_replace+159>:  cmp    $0x3f,%eax
0xffffffff8ac4e582 <__radix_tree_replace+162>:  ja     0xffffffff8ac4e4fc <__radix_tree_replace+28>
0xffffffff8ac4e588 <__radix_tree_replace+168>:  mov    %eax,%esi
//这一行发生的crash
0xffffffff8ac4e58a <__radix_tree_replace+170>:  cmp    0x28(%rbx,%rsi,8),%r9
0xffffffff8ac4e58f <__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 -o
struct radix_tree_node {
    [0] unsigned char shift;
    [1] unsigned char offset;
    [2] unsigned char count;
    [3] unsigned char exceptional;
    [8] struct radix_tree_node *parent;
   [16] void *private_data;
        union {
   [24]     struct list_head private_list;
   [24]     struct callback_head callback_head;
        };
   [40] void *slots[64]; //十进制40十六进制0x28
  [552] 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)
{
#ifdef CONFIG_RADIX_TREE_MULTIORDER
  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++;
  }
#endif
}

可以发现，这个版本内核对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 首先赋值NULL
        parent = NULL;
        slot = (void **)&root->rnode;//slot首先指向root->rnode
    //获取root node，然后node指向root->rnode
        radix_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清0
                parent = 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 node
      if (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少了一个node
    if (parent) {
      parent->slots[node->offset] = NULL;
      parent->count--;
    } else {
    //否则就是只剩下一个root node
      root_tag_clear_all(root);
      root->rnode = NULL;
    }
    //释放node
    radix_tree_node_free(node);
    deleted = true;

    //node指向parent，下个循环释放parent这个node
    node = 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 node
    struct radix_tree_node *node = root->rnode;
    struct radix_tree_node *child;

    //如果root node不是internal node直接break
    if (!radix_tree_is_internal_node(node))
      break;
    node = entry_to_node(node);
    
    //如果root node保存的对象有多则直接break
    if (node->count != 1)
      break;
        
    //root node的node->slots[0]保存了一个对象，正常运行，否则直接break
    child = 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=NULL
    if (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 node
    radix_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互联网技术

 

我就知道你“在看”