一例ubuntu 16内核crash分析：radix tree相关（下）

我们的分布式存储业务遇到了几例宕机，业务方用到fuse文件系统，ubuntu 16系统，内核4.10，宕机现场很奇怪，本文主要总结排查过程和涉及的内核知识。

文章涉及的内容有：radix tree的基本知识和一个特殊使用场景、ubuntu 16 kdump遇到的坑、内存回收等等。

文章的上篇已经发布，上篇分析到，案例与radix tree的一种特殊用法有关，下篇将结合crash日志和radix tree源码进行一次深入分析。前情提要请见：

1. 结合crash日志和radix tree源码深入分析

根据该案例crash现场的栈回溯日志，直观上看crash是由__radix_tree_replace()->delete_sibling_entries()函数struct radix_tree_node *node是NULL导致的，但是一直停留在代码层面，没有从radix tree角度验证。

团队里的内核大牛此时提出了一个疑问，就是本案例的radix tree的radix_tree_root的struct radix_tree_node __rcu *rnode不是一个正常值。分析了一下确实是这样的。首先该怎么获取本案例radix tree的radix_tree_root指针值？看下crash过程的栈回溯信息。

#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

bt -f后在iput ()函数栈的第4片内存找到0xffff950000000000是文件inode指针，过程就不再说了，结合dentry_unlink_inode()和iput()函数汇编指令对rdi、r12寄存器的入栈操作分析出。

crash> struct inode ffff950000000000
struct inode {
  i_mode = 33188, 
  i_opflags = 12, 
  ..............
  i_default_acl = 0xffffffffffffffff, 
  i_op = 0xffffffff8b253700, 
  i_sb = 0xffff950234b48800, 
  i_mapping = 0xffff950000000178, //struct address_space  *i_mapping
  i_security = 0x0, 
 ..............

crash> struct address_space 0xffff950000000178
struct address_space {
  host = 0xffff950000000000, 
  page_tree = {
    gfp_mask = 18350112, 
    rnode = 0x19a8d5005d006//正常是 radix_tree的root node ，但这是一个无效值
  }, 
  ...............
  nrpages = 0, //文件page cache个数是0
  nrexceptional = 1, //exceptional page 有一个，划重点
  writeback_index = 0, 
  a_ops = 0xffffffff8b253ac0, 
 .................
}

由inode指针找到address_space指针，再由address_space指针找到radix tree的radix_tree_root的成员struct radix_tree_node __rcu *rnode指针值，竟然是0x19a8d5005d006，一看就不是个合法的64位系统内核态地址。可是crash现场不是访问0x19a8d5005d006指向的内存导致的crash，虽然有一万个不可能，但这就是事实，这条路暂时走不通。

还有另外一条路，就是__radix_tree_replace()->delete_sibling_entries()函数struct radix_tree_node *node指针真的可能是NULL吗？这个指针是由clear_shadow_entry()函数传入的，它的源码是：

static void clear_shadow_entry(struct address_space *mapping, pgoff_t index,
                               void *entry)
{
        struct radix_tree_node *node;
        void **slot;
        spin_lock_irq(&mapping->tree_lock);
    
    //根据index查找radix tree中保存的对象
        if (!__radix_tree_lookup(&mapping->page_tree, index, &node, &slot))
                goto unlock;
        if (*slot != entry)
                goto unlock;
        //这个函数里发生了crash
        __radix_tree_replace(&mapping->page_tree, node, slot, NULL,
                             workingset_update_node, mapping);
        mapping->nrexceptional--;
unlock:
        spin_unlock_irq(&mapping->tree_lock);
}

分析源码，struct radix_tree_node *node指针其实源头是__radix_tree_lookup()函数传入的，就是那个node局部变量。__radix_tree_lookup()函数找到的node是NULL，但是返回值不是NULL，并且还躲过if (*slot != entry)的限制，最终执行__radix_tree_replace()函数触发crash，这可能吗？

纠结了一段时间后，这是有可能的。把分析的源码注释写下：

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;                   
        ............
    //parent 首先赋值NULL，关键点
        parent = NULL;
        slot = (void **)&root->rnode;//slot首先指向 radix_tree_root 的rnode成员
    //获取root node，node指向root->rnode
        radix_tree_load_root(root, &node, &maxindex);
    
    //index 是0，radix tree只有一个对象并且索引是0，if不成立
        if (index > maxindex)
                return NULL;
     
    //while循环第一次都不成立
        while (radix_tree_is_internal_node(node)) {
         .........................
        }
    //给*nodep赋值NULL，因为parent是NULL                    
        if (nodep)
                *nodep = parent;
    //*slotp 指向 root->rnode这片内存
        if (slotp)
                *slotp = slot;
      
    //node 返回值是root->rnode指针值
        return node;
}

就是说，如果radix tree一个node都没有的情况下，__radix_tree_lookup()函数返回的node就是NULL。并且此时各种限制条件都不成立，最终使得顺利执行到__radix_tree_replace()函数，然后触发crash。回到本小节的开头，radix tree的radix_tree_root的成员struct radix_tree_node __rcu *rnode指针值是0x19a8d5005d006 ，这不是正好radix tree一个node都没有！

做一个测试，令root->rnode=0x19a8d5005d006 ，index=0然后去分析clear_shadow_entry()、__radix_tree_lookup()、__radix_tree_replace()几个函数，发现正好会导致__radix_tree_replace()传入的struct radix_tree_node *node是NULL。

回到crash栈回溯前几步执行的几个函数truncate_inode_pages_range()和truncate_exceptional_entry()。如果一个radix tree的radix_tree_root的成员struct radix_tree_node __rcu *rnode指针值是0x19a8d5005d006，发现也是可以正常执行的。把分析的源码truncate_inode_pages_range()注释一下。

void truncate_inode_pages_range(struct address_space *mapping,
                                loff_t lstart, loff_t lend)//本案例 lstart 是0
{
    /*pagevec_lookup_entries() 遍历radix tree 保存的page，本案例radix_tree_root的成员rnode指针值是0x19a8d5005d006，不是一个正常的数据，这种情况也会保存它到pvec.pages[i]吗，验证会的*/
    while (index < end && pagevec_lookup_entries(&pvec, mapping, index,
          min(end - index, (pgoff_t)PAGEVEC_SIZE),//index 初值是0
          indices)) {
            
   //从radix tree 获取的page，不一定是正常的page，该案例是一个 exceptional  entry
      for (i = 0; i < pagevec_count(&pvec); i++) {
          struct page *page = pvec.pages[i];//此时 page=0x19a8d5005d006

          index = indices[i];//indices[i] 是0
          if (index >= end)
              break;
            
     //page 的bit1是1，一个exceptional  entry，if成立
          if (radix_tree_exceptional_entry(page)) {
              truncate_exceptional_entry(mapping, index,
                             page);
              continue;
          }
      }
    }
}

truncate_inode_pages_range()函数中，因为radix_tree_root的成员struct radix_tree_node __rcu *rnode指针值是0x19a8d5005d006，也就是mapping->page_tree->rnode 是 0x19a8d5005d006 ，因为bit1是1，bit0是0，说明这是个 “exceptional entry”，或者说是个 “shadow entry”（radix tree原理那一节有介绍exceptional entry和shadow entry）。然后把 0x19a8d5005d006 保存到 pvec.pages[0]就返回，接着向下执行，顺利执行 truncate_exceptional_entry()函数。

根据上边分析，该radix tree只有一个exceptional entry即0x19a8d5005d006，保存在radix_tree_root的成员rnode 。并且因为address_space结构的nrexceptional是1，nrpages 是0(看下本节开头的crash分析)，所以 truncate_inode_pages_range ()函数只会执行一次for循环。并且，发生crash的函数流程正是:truncate_inode_pages_range()->truncate_exceptional_entry()->clear_shadow_entry()

clear_shadow_entry()函数是清理exceptional entry，按照前文的分析，truncate_inode_pages_range()传递给clear_shadow_entry()函数的entry就是 0x19a8d5005d006。这样就与本节开头的分析完全对上了。这里再列下源码注释。

static void clear_shadow_entry(struct address_space *mapping, pgoff_t index,//是0
                               void *entry)//entry 就是page指针即 0x19a8d5005d006
{
        struct radix_tree_node *node;
        void **slot;

        spin_lock_irq(&mapping->tree_lock);
    
    //__radix_tree_lookup()返回值是 0x19a8d5005d006，if不成立。并且node是NULL，*slot是0x19a8d5005d006
        if (!__radix_tree_lookup(&mapping->page_tree, index, &node, &slot))
                goto unlock;
      
    //*slot == entry，if不成立
        if (*slot != entry)
                goto unlock;
    
    //执行 __radix_tree_replace 传入的node是NULL，由于没有对node对NULL做防护，导致内核crash
        __radix_tree_replace(&mapping->page_tree, node, slot, NULL,
                             workingset_update_node, mapping);
        mapping->nrexceptional--;
unlock:
        spin_unlock_irq(&mapping->tree_lock);
} 

总算把前期的疑问都解答了，但是还有疑问，radix tree的radix_tree_root成员rnode被赋值0x19a8d5005d006是怎么来的？

2. radix_tree_root的成员rnode被赋值0x19a8d5005d006的过程

首先提一点，本案例的crash是在内存回收过程触发的，栈回溯信息很明确。在执行这一步前，还有这个过程，看下这个函数流程：

shrink_node()->shrink_node_memcg()->shrink_list()->shrink_page_list()->__remove_mapping()->__delete_from_page_cache()->page_cache_tree_delete()

shrink_page_list()计算要回收的page，它会执行__remove_mapping()函数把page cache从radix tree中剔除，并在该page所在的radix tree中的对应位置标记为”shadow entry”，看下源码：

static int __remove_mapping(struct address_space *mapping, struct page *page,
                            bool reclaimed)
{
  ...............
  //if成立，执行 workingset_eviction ()计算shadow，看了这个函数源码，shadow=0x19a8d5005d006 是有可能的
  if (reclaimed && page_is_file_cache(page) &&
    !mapping_exiting(mapping) && !dax_mapping(mapping))
      shadow = workingset_eviction(mapping, page);
  
  //shadow = 0x19a8d5005d006
  __delete_from_page_cache(page, shadow);
  ...............
}

__delete_from_page_cache()函数中执行了page_cache_tree_delete()函数。在page_cache_tree_delete()函数中，如果此时radix tree只有索引是0的page指针保存在root node的slot[0]，则会执行__radix_tree_replace()->replace_slot()把0x19a8d5005d006保存到root node的slot[0]，接着是执行__radix_tree_replace()->delete_node()，把root node的slot[0]保存的0x19a8d5005d006移动到radix_tree_root的rnode成员，然后把root node释放掉。

这样radix tree就成了一个没有radix_tree_node且只有一个索引是0的对象保存在radix_tree_root的rnode的奇怪的树，并且radix_tree_root的rnode值是0x19a8d5005d006。

下边把相关源码分析贴下，觉得繁琐可以直接跳过，后边紧挨着有总结。

static void page_cache_tree_delete(struct address_space *mapping,
                                   struct page *page, void *shadow)//shadow 是 0x19a8d5005d006
{
        int i, nr;
       /* hugetlb pages are represented by one entry in the radix tree */
        nr = PageHuge(page) ? 1 : hpage_nr_pages(page);
       
        for (i = 0; i < nr; i++) {
                struct radix_tree_node *node;
                void **slot;
      //此时这个radix tree只有一个page cache，且只有一个root node，并且page->index是0，这样node指向root node，slot指向 root node->slot[0]
                __radix_tree_lookup(&mapping->page_tree, page->index + i,
                                    &node, &slot);
                
     //不成立
                VM_BUG_ON_PAGE(!node && nr != 1, page);

                radix_tree_clear_tags(&mapping->page_tree, node, slot);
     //这个是重点，源码在下方
                __radix_tree_replace(&mapping->page_tree, node, slot, shadow,
                                     workingset_update_node, mapping);
        }

        if (shadow) {
    // mapping->nrexceptional 加1变为1
                mapping->nrexceptional += nr;
                smp_wmb();
        }
    //mapping->nrpages 减1变为0
        mapping->nrpages -= nr;
}

    /*node 是root node，该radix tree只有一个root node，该node只有一个page保存在root node->slot[0]，slot指向 root node->slot[0]*/
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)
{
    //item 指向shadow ，不为NULL
        if (!item)
                delete_sibling_entries(node, slot);
      
    //把 shadow 0x19a8d5005d006 保存到 root node->slot[0]，源码在下方
        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);
}

static void replace_slot(struct radix_tree_root *root,
                         struct radix_tree_node *node,
                         void **slot, void *item,
                         bool warn_typeswitch)
{
        void *old = rcu_dereference_raw(*slot);
        int count, exceptional;

        WARN_ON_ONCE(radix_tree_is_internal_node(item));

        //item 指向shadow，old 是slot原本保存的数据，两次取反后都是1，计算出的count是0
        count = !!item - !!old;
        exceptional = !!radix_tree_exceptional_entry(item) -
                      !!radix_tree_exceptional_entry(old);

        WARN_ON_ONCE(warn_typeswitch && (count || exceptional));

        if (node) {
                node->count += count;//count是0
                if (exceptional) {
                        exceptional *= slot_count(node, slot);
                        node->exceptional += exceptional;
                }
        }
        //这里把 shadow 0x19a8d5005d006 保存slot，即root node->slot[0]=0x19a8d5005d006
        rcu_assign_pointer(*slot, item);
}

        /*从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],然后整个radix tree全部释放。这是个极端情况，本案例就是把 root node->slot[0]保存的0x19a8d5005d006移动到root->rnode，root->rnode=0x19a8d5005d006就是从这里来的*/
static void delete_node(struct radix_tree_root *root,
                        struct radix_tree_node *node,
                        radix_tree_update_node_t update_node, void *private)
{
        do {
                struct radix_tree_node *parent;

                if (node->count) {
       /*如果node是root node，并且只保存了 root node->slot[0] 一个对象，则 root->rnode=root node->slot[0]，然后释放掉整个radix tree。之后相当于 root->rnode 保存了root node->slot[0]，这是 root->rnode 是 0x19a8d5005d006的根本原因*/
                        if (node == entry_to_node(root->rnode))
                                radix_tree_shrink(root, update_node, private);
                        return;
                }

                parent = node->parent;
        //如果node有父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;
                }
                WARN_ON_ONCE(!list_empty(&node->private_list));
         //释放node
                radix_tree_node_free(node);
        //node指向parent，下个循环还是释放parent这个node
                node = parent;
        } while (node);
}

如果你对这个过程不理解，可以再看下讲解radix tree原理那一节最后，从radix tree删除一个对象的过程，与__radix_tree_replace()->delete_node()的过程是一样的。

总之核心就是：如果从radix tree删除radix_tree_node时，只有root node的slots[0]保存了一个索引是0的对象，则把slot[0]的值移动到radix_tree_root的rnode成员,然后把root node释放掉。这样radix tree就成了一个没有一个radix_tree_node且只有一个索引是0的对象保存在radix_tree_root的成员rnode的奇怪的树。

之后执行__radix_tree_lookup()该radix tree找索引是0的page指针时，返回的node(就是radix_tree_node)是NULL，4.10内核没有对node NULL做防护，导致了后续执行clear_shadow_entry()->__radix_tree_replace()->delete_sibling_entries()函数时，发生内核crash。

这里有必要再介绍一下exceptional entry/shadow entry，这与缺页异常refault现象有关。当内存回收把一个inactive list链表上的page交换到磁盘后，紧接着进程又访问这个page，将发生缺页异常，从磁盘再读取该page的数据，称之为refault，与正常的缺页异常不一样。如果refault频繁发生，对性能有不良影响。

内核开发者想了一个方法，定义一个计数变量，每一个page从inactive list链表被交换出去时，这个计数变量都会加1,同时将这个计数变量记录到该page在radix tree对应的radix_tree_node的slot[0~63]，0x19a8d5005d006 应该就与这个计算变量有关，这个过程可以参考上边内存回收shrink_node()->shrink_node_memcg()->shrink_list()->shrink_page_list()->__remove_mapping()的讲解。

等该page再次被访问，发生refault，会从radix tree该page对应的radix_tree_node的slot[0~63]取出这个老的计数变量，与当前计数变量计算一个差值，这个差值将影响到增大inactive list链表的长度。只有处于inactive list链表尾的page才会被首先交换出去，增大inactive list链表的长度将增大该page被访问的概率，一旦该page被访问了，将会避免被交换出去，从而避免该page频繁refault，这是个人理解，可能不太准确。

更准确的描述可以参考http://tinylab.org/lwn-495543/

3. 又一例类似crash分析

分析的差不多时，最早的crash场景也生成了vmcore。

crash> bt
PID: 475    TASK: ffff910cf34a8000  CPU: 5   COMMAND: "kswapd1"
..............
    [exception RIP: __radix_tree_replace+170]
    RIP: ffffffff9624e58a  RSP: ffffa563ce7f38c8  RFLAGS: 00010097
    RAX: 000000000000002d  RBX: 0000000000000000  RCX: 0000000000000000
    RDX: ffff910000000188  RSI: 000000000000002d  RDI: ffff910000000160
    RBP: ffffa563ce7f38e8   R8: 0000000000000000   R9: ffff910000000189
    R10: ffffa563ce7f3918  R11: 0000000000000040  R12: ffffffff95fe3370
    R13: ffff910000000180  R14: ffff910000000178  R15: 0000000000000001
    ORIG_RAX: ffffffffffffffff  CS: 0010  SS: 0018
#11 [ffffa563ce7f38f0] __delete_from_page_cache at ffffffff95fb1353
#12 [ffffa563ce7f3958] delete_from_page_cache at ffffffff95fb1634
#13 [ffffa563ce7f3988] truncate_inode_page at ffffffff95fc433c
#14 [ffffa563ce7f39b0] truncate_inode_pages_range at ffffffff95fc4568
#15 [ffffa563ce7f3b10] truncate_inode_pages_final at ffffffff95fc4d5d
#16 [ffffa563ce7f3b30] fuse_evict_inode at ffffffff96163f59
#17 [ffffa563ce7f3b48] evict at ffffffff96061ab7
#18 [ffffa563ce7f3b70] iput at ffffffff96061d9b
#19 [ffffa563ce7f3ba0] dentry_unlink_inode at ffffffff9605bc61
#20 [ffffa563ce7f3bc0] __dentry_kill at ffffffff9605d30e
#21 [ffffa563ce7f3be8] shrink_dentry_list at ffffffff9605d8d1
#22 [ffffa563ce7f3c30] prune_dcache_sb at ffffffff9605ed2a
#23 [ffffa563ce7f3c68] super_cache_scan at ffffffff96047ef9
#24 [ffffa563ce7f3cc0] shrink_slab at ffffffff95fc655a
#25 [ffffa563ce7f3da0] shrink_slab at ffffffff95fc67b9
#26 [ffffa563ce7f3db0] shrink_node at ffffffff95fcb078
#27 [ffffa563ce7f3e38] kswapd at ffffffff95fcc0cb
#28 [ffffa563ce7f3f00] kthread at ffffffff95ea8de9
#29 [ffffa563ce7f3f48] ret_from_fork at ffffffff966d413c

用同样的方法查到 inode 是 ffff910000000000。

crash> struct inode ffff910000000000
struct inode {
  i_mode = 33188, 
  ................ 
  i_acl = 0xffffffffffffffff, 
  i_default_acl = 0xffffffffffffffff, 
  i_op = 0xffffffff96853700, 
  i_sb = 0xffff910ce8951000, 
  i_mapping = 0xffff910000000178, 
  ............

显然这个场景的address_space 是 0xffff910000000178 ，后3位竟然也是178。

crash> struct address_space 0xffff910000000178
struct address_space {
  host = 0xffff910000000000, 
  page_tree = {
    gfp_mask = 18350112, 
    rnode = 0xffffd94ee4a2e6c0 //这个 root->rnode 是 0xffffd94ee4a2e6c0 ，看着是个正常的指针
  }, 
.................  
  nrpages = 1, //是有一个 page cache，没有 exceptional page
  nrexceptional = 0,
.................

这个场景 root->rnode 是 0xffffd94ee4a2e6c0 ，看着是个正常的指针，为什么也会crash？根据前文的经验，我认为这个crash场景也是因为radix tree 没有node(即radix_tree_node)，而 root->rnode 保存的 0xffffd94ee4a2e6c0 并不是radix_tree_node，而是一个page指针。验证一下就知分晓。

crash>  struct page 0xffffd94ee4a2e6c0           
struct page {
  flags = 24769796876795949, 
  {
    mapping = 0xffff910000000178, //这里的 0xffff910000000178 进一步说明该page属于 address_space 0xffff910000000178
    s_mem = 0xffff910000000178, 
    compound_mapcount = {
      counter = 376
    }
  }

那么问题来了，这个场景是发生的？想了多个情况后，认为是如下的一个过程：address_space 0xffff910000000178 的radix tree现在只有一个node，即root node。保存了两个page指针，有一个index是0的page指针保存在 root node的slots[0]，另外一个page指针保存在 root node的slots[] 数组另一个位置，假设是root node的slots[2]。现在发生了脏页回写或者内存回收或者其他操作，执行__delete_from_page_cache->page_cache_tree_delete 把root node的slots[2] 保存的page 从page cache里剔除。

具体的删除过程是：page_cache_tree_delete()->__radix_tree_replace->replace_slot()把root node的slots[2]保存的page指针置NULL，并且root node的count由2变为1，然后执行delete_node()尝试把root node释放掉。因为此时root node只有一个slots[0]还保存了一个page指针，则把它移动到radix_tree_root的成员rnode，这样就出现一个没有一个node且只有一个索引是0的page指针保存在radix_tree_root的rnode奇怪的radix tree。

同样的，把这段源码贴下，可以直接跳过。

static void page_cache_tree_delete(struct address_space *mapping,
                                   struct page *page, void *shadow)//shadow 此时是NULL，因为是page cache
{
        int i, nr;

        /* hugetlb pages are represented by one entry in the radix tree */
        nr = PageHuge(page) ? 1 : hpage_nr_pages(page);
       
        for (i = 0; i < nr; i++) {
                struct radix_tree_node *node;
                void **slot;
                //此时这个radix tree有2个page指针，且只有一个root node，并且page->index是2，这样node指向root node，slot指向root node->slot[2]
                __radix_tree_lookup(&mapping->page_tree, page->index + i,
                                    &node, &slot);
                
        //不成立
                VM_BUG_ON_PAGE(!node && nr != 1, page);

                radix_tree_clear_tags(&mapping->page_tree, node, slot);
        //源码在下方
                __radix_tree_replace(&mapping->page_tree, node, slot, shadow,
                                     workingset_update_node, mapping);
        }

        if (shadow) {//不成立
                mapping->nrexceptional += nr;
                smp_wmb();
        }
         //mapping->nrpages 减1由2变为1
        mapping->nrpages -= nr;
}

         //node 是root node，该radix tree只有一个root node，slot指向 root node->slot[2]
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)
{
         //item 指向shadow ，不为NULL
        if (!item)
                delete_sibling_entries(node, slot);
      
        //shadow 此时是NULL，node->count 减1由2变为1，且root node->slot[2]=NULL
        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);
}
static void replace_slot(struct radix_tree_root *root,
                         struct radix_tree_node *node,
                         void **slot, void *item,
                         bool warn_typeswitch)
{
        void *old = rcu_dereference_raw(*slot);
        int count, exceptional;

        WARN_ON_ONCE(radix_tree_is_internal_node(item));
        //item 是NULL，old是page指针，计算后 count是-1
        count = !!item - !!old;
        exceptional = !!radix_tree_exceptional_entry(item) -
                      !!radix_tree_exceptional_entry(old);

        WARN_ON_ONCE(warn_typeswitch && (count || exceptional));

        if (node) {
                node->count += count;//node->count 减1由2变为1
                if (exceptional) {
                        exceptional *= slot_count(node, slot);
                        node->exceptional += exceptional;
                }
        }
        //root node->slot[2]=NULL
        rcu_assign_pointer(*slot, item);
}

static void delete_node(struct radix_tree_root *root,
                        struct radix_tree_node *node,
                        radix_tree_update_node_t update_node, void *private)
{
        do {
                struct radix_tree_node *parent;
                /*本场景执行到这里，node是root node，且 node->count 已经是1。并且 radix tree 只有一个index是0的page指针保存在root node->slot[0]，执行 radix_tree_shrink 函数把这个page指针保存到 root->rnode，然后把root node 释放掉。这样就又变成了只保存了一个page指针且没有node的radix tree*/
                if (node->count) {
                        if (node == entry_to_node(root->rnode))
                                radix_tree_shrink(root, update_node, private);
                        return;
                }

                parent = node->parent;
                if (parent) {
                        parent->slots[node->offset] = NULL;
                        parent->count--;
                } else {
                        root_tag_clear_all(root);
                        root->rnode = NULL;
                }

                WARN_ON_ONCE(!list_empty(&node->private_list));
                radix_tree_node_free(node);

                node = parent;
        } while (node);
}

好的，等内存消耗过多而内存回收时执行shrink_slab()->...->truncate_inode_page()->delete_from_page_cache()->__delete_from_page_cache()->page_cache_tree_delete() 函数从address_space 0xffff910000000178 的radix tree 剔除 node时。radix tree 是一个"只保存了一个page指针且没有node的radix tree"。在 page_cache_tree_delete() 函数中，执行 __radix_tree_lookup() 查找index是0的page所在node，但是找到的node是NULL，然后执行__radix_tree_replace()->delete_sibling_entries()时，因为没有对node NULL做防护而crash。

下边把page_cache_tree_delete()函数源码贴下，这个代码不多。

static void page_cache_tree_delete(struct address_space *mapping,
                                   struct page *page, void *shadow)
{               
        int i, nr;
                
        /* hugetlb pages are represented by one entry in the radix tree */
        nr = PageHuge(page) ? 1 : hpage_nr_pages(page);
                
        VM_BUG_ON_PAGE(!PageLocked(page), page);
        VM_BUG_ON_PAGE(PageTail(page), page);
        VM_BUG_ON_PAGE(nr != 1 && shadow, page);

        for (i = 0; i < nr; i++) {
                struct radix_tree_node *node;
                void **slot;
                /*查找page->index 是0的page所在的node，但是这个page指针保存在 mapping->page_tree->rnode，没有node，则找到的node是NULL*/
                __radix_tree_lookup(&mapping->page_tree, page->index + i,
                                    &node, &slot);
                //node是NULL，但是nr是1，不成立
                VM_BUG_ON_PAGE(!node && nr != 1, page);

                radix_tree_clear_tags(&mapping->page_tree, node, slot);
        //因为node是NULL，执行该函数的delete_sibling_entries()时，因为没有对node NULL做防护而crash
                __radix_tree_replace(&mapping->page_tree, node, slot, shadow,
                                     workingset_update_node, mapping);
        }
..................    
}

4. 总结

两个crash场景其实都是因为radix tree的一种特殊用法：只有一个索引是0的对象保存在radix_tree_root的成员rnode。这样如果lookup该radix tree，查找索引是0的对象时，获取的struct radix_tree_node *node就是NULL，4.10内核__radix_tree_replace()->delete_sibling_entries（）没有对node NULL做防护，导致了crash。

既然是内核bug，当然升级内核可以解决，升级内核到4.11就可以解决__radix_tree_replace()->delete_sibling_entries()没有对node NULL做防护而导致的crash。

但是！但是！但是！重要的事说3遍，升级内核就能保证万事大吉吗？

首先一点，新的内核可能会引入新的bug，这是不可避免的。并且，4.10~4.18的内核，radix tree还有一处没有对node NULL做防护的bug，是在calculate_count()->get_slot_offset()函数，上源码：

static inline unsigned long get_slot_offset(struct radix_tree_node *parent,
                                                 void **slot)
{
        return slot - parent->slots;
}

4.19内核的是：

static inline unsigned long
get_slot_offset(const struct radix_tree_node *parent, void __rcu **slot)
{
  return parent ? slot - parent->slots : 0;
}

但是有一件更坑的事：4.19内核cifs模块有一个bug，导致我们的ubuntu服务器多次宕机。4.10~4.19版本内核有风险，在不确定哪个内核版本稳定时，升级内核不是最优的解决方法。

其实是有规避方法的，该问题触发场景是：page cache太多而可直接分配内存太少而触发了内存回收，然后回收dentry slab发现有一个文件inode的引用计数是0，然后释放该文件的page cache。

而保存该文件page cache的page指针的radix tree又比较特殊：只有一个索引是0的page对象保存在radix tree的radix_tree_root的rnode，没有一个radix_tree_node，故lookup到的node为NULL，最后触发了node NULL内核crash。

如果减少page cache的使用(业务方大量使用fuse write cache)，避免触发与该场景类似的内存回收，应该可以一定程度规避该crash，毕竟该问题的crash条件还是挺苛刻的。

☆ END ☆

招聘信息

OPPO互联网云平台团队招聘一大波岗位，涵盖Java、容器、Linux内核开发、产品经理、项目经理等多个方向，请在公众号后台回复关键词“云招聘”查看查详细信息。

你可能还喜欢

更多技术干货

扫码关注

OPPO互联网技术

 

我就知道你“在看”