基樹(shù)

內(nèi)核中的基樹(shù)的節(jié)點(diǎn)，使用struct radix_tree_node來(lái)表示，其源代碼如下：

struct radix_tree_node {
    unsigned int    height;     /* Height from the bottom */
    unsigned int    count;      /* 子節(jié)點(diǎn)的個(gè)數(shù) */
    union {
        struct radix_tree_node *parent; /* Used when ascending tree */
        struct rcu_head rcu_head;   /* Used when freeing node */
    };
    void __rcu  *slots[RADIX_TREE_MAP_SIZE];
    unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

/* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */
struct radix_tree_root {
    unsigned int        height;
    gfp_t           gfp_mask;
    struct radix_tree_node  __rcu *rnode;
};

slots是指向各個(gè)孩子節(jié)點(diǎn)的指針，RADIX_TREE_MAP_SIZE通常為64（跟宏定義有關(guān)，我們以64為例來(lái)說(shuō)明）。

tags顧名思義是標(biāo)簽，代表此節(jié)點(diǎn)的所有孩子節(jié)點(diǎn)的標(biāo)簽。tags是二維數(shù)組，RADIX_TREE_MAX_TAGS定義為3，即最多支持3種標(biāo)簽。RADIX_TREE_TAG_LONGS的長(zhǎng)度使得可以放下所有子節(jié)點(diǎn)的tag（一個(gè)tag占1位）。

一個(gè)典型的基樹(shù)如下圖所示：

height=3的基樹(shù)

不得不說(shuō)，本來(lái)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，加上了RCU的機(jī)制后，總是有點(diǎn)難以理解。

初始化

跟Linux內(nèi)核中其它的數(shù)據(jù)結(jié)構(gòu)類(lèi)似，兩種初始化方式：

#define RADIX_TREE(name, mask) \
    struct radix_tree_root name = RADIX_TREE_INIT(mask)

#define INIT_RADIX_TREE(root, mask)                 \
do {                                    \
    (root)->height = 0;                     \
    (root)->gfp_mask = (mask);                  \
    (root)->rnode = NULL;                       \
} while (0)

查找

/*
 * is_slot == 1 : search for the slot.
 * is_slot == 0 : search for the node.
 */
static void *radix_tree_lookup_element(struct radix_tree_root *root,
                unsigned long index, int is_slot)
{
    unsigned int height, shift;
    struct radix_tree_node *node, **slot;

    node = rcu_dereference_raw(root->rnode);
    if (node == NULL)
        return NULL;

    if (!radix_tree_is_indirect_ptr(node)) {
        if (index > 0)
            return NULL;
        return is_slot ? (void *)&root->rnode : node;
    }
    node = indirect_to_ptr(node);

    height = node->height;
    if (index > radix_tree_maxindex(height))
        return NULL;

    shift = (height-1) * RADIX_TREE_MAP_SHIFT;

    do {
        slot = (struct radix_tree_node **)
            (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
        node = rcu_dereference_raw(*slot);
        if (node == NULL)
            return NULL;

        shift -= RADIX_TREE_MAP_SHIFT;
        height--;
    } while (height > 0);

    return is_slot ? (void *)slot : indirect_to_ptr(node);
}

/**
 *  radix_tree_lookup    -    perform lookup operation on a radix tree
 *  @root:      radix tree root
 *  @index:     index key
 *
 *  Lookup the item at the position @index in the radix tree @root.
 *
 *  This function can be called under rcu_read_lock, however the caller
 *  must manage lifetimes of leaf nodes (eg. RCU may also be used to free
 *  them safely). No RCU barriers are required to access or modify the
 *  returned item, however.
 */
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
{
    return radix_tree_lookup_element(root, index, 0);
}

查找的過(guò)程，就是把index從高位開(kāi)始，每6位（以64位機(jī)器為例）為一個(gè)單位，分隔成一個(gè)個(gè)的slot index，然后從radix樹(shù)的根往下搜索的過(guò)程，整體還是比較好理解的。暫時(shí)忽略indirect_to_prt，rcu_dereference_raw這幾個(gè)函數(shù)，這不影響對(duì)整體流程的理解。

插入

/**
 *  radix_tree_insert    -    insert into a radix tree
 *  @root:      radix tree root
 *  @index:     index key
 *  @item:      item to insert
 *
 *  Insert an item into the radix tree at position @index.
 */
int radix_tree_insert(struct radix_tree_root *root,
            unsigned long index, void *item)
{
    struct radix_tree_node *node = NULL, *slot;
    unsigned int height, shift;
    int offset;
    int error;

    BUG_ON(radix_tree_is_indirect_ptr(item));

    /* Make sure the tree is high enough.  */
    if (index > radix_tree_maxindex(root->height)) {
        error = radix_tree_extend(root, index);
        if (error)
            return error;
    }

    slot = indirect_to_ptr(root->rnode);

    height = root->height;
    shift = (height-1) * RADIX_TREE_MAP_SHIFT;

    offset = 0;         /* uninitialised var warning */
    while (height > 0) {
        if (slot == NULL) {
            /* Have to add a child node.  */
            if (!(slot = radix_tree_node_alloc(root)))
                return -ENOMEM;
            slot->height = height;
            slot->parent = node;
            if (node) {
                rcu_assign_pointer(node->slots[offset], slot);
                node->count++;
            } else
                rcu_assign_pointer(root->rnode, ptr_to_indirect(slot));
        }

        /* Go a level down */
        offset = (index >> shift) & RADIX_TREE_MAP_MASK;
        node = slot;
        slot = node->slots[offset];
        shift -= RADIX_TREE_MAP_SHIFT;
        height--;
    }

    if (slot != NULL)
        return -EEXIST;

    if (node) {
        node->count++;
        rcu_assign_pointer(node->slots[offset], item);
        BUG_ON(tag_get(node, 0, offset));
        BUG_ON(tag_get(node, 1, offset));
    } else {
        rcu_assign_pointer(root->rnode, item);
        BUG_ON(root_tag_get(root, 0));
        BUG_ON(root_tag_get(root, 1));
    }

    return 0;
}

插入的過(guò)程跟查找的過(guò)程非常相似其實(shí)，就是沿著樹(shù)從上到下地找，某個(gè)位置沒(méi)有元素就創(chuàng)建元素，直到出錯(cuò)或者把元素放到指定的slot中。

Tag

內(nèi)核的radix tree支持Tag功能，就是給某個(gè)元素打一個(gè)tag。這個(gè)tag會(huì)影響該元素到基樹(shù)根上所有元素。這樣通過(guò)查看根元素是否有這個(gè)tag，就能判斷根元素下的子元素中是否存在這種tag的元素。另外內(nèi)核的基樹(shù)提供了迭代所有設(shè)置過(guò)tag的元素的方法：radix_tree_for_each_tagged。