radix_tree_init()

 

radix_tree_init()

lib/radix-tree.c

void __init radix_tree_init(void)
{
        radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
                        sizeof(struct radix_tree_node), 0,
                        SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
                        radix_tree_node_ctor);
        radix_tree_init_maxindex();
        hotcpu_notifier(radix_tree_callback, 0);
}

radix 트리 사용을 위해 초기화한다.

• raidx_tree_node  구조체용 slub 캐시를 만들고 생성자로 radix_tree_node_ctor 함수를 준비한다.
• height 별로 최대 인덱스 값을 산출하여 전역 height_to_maxindex[] 배열에 저장한다.
• cpu 상태 변화에 따라 radix_tree_callback 함수가 호출되도록 radix_tree_callback_nb를 구성하여 전역 cpu_chain 리스트에 우선 순위 0으로 추가한다.

 

radix_tree_node_ctor()

lib/radix-tree.c

radix_tree_node_ctor(void *arg)
{
        struct radix_tree_node *node = arg;

        memset(node, 0, sizeof(*node));
        INIT_LIST_HEAD(&node->private_list);
}

radix 트리 노드를 0으로 만들고 private_list를 초기화한다.

 

radix_tree_init_maxindex()

lib/radix-tree.c

static __init void radix_tree_init_maxindex(void)
{
        unsigned int i;

        for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
                height_to_maxindex[i] = __maxindex(i);
}

height 별로 최대 인덱스 값을 산출하여 전역 height_to_maxindex[] 배열에 저장한다.

 

다음 그림은 height 별로 최대 인덱스 값을 산출하는 모습을 보여준다.

 

lib/radix-tree.c

/*
 * The height_to_maxindex array needs to be one deeper than the maximum
 * path as height 0 holds only 1 entry.
 */
static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;

 

__maxindex()

lib/radix-tree.c

static __init unsigned long __maxindex(unsigned int height)
{
        unsigned int width = height * RADIX_TREE_MAP_SHIFT;
        int shift = RADIX_TREE_INDEX_BITS - width;

        if (shift < 0)
                return ~0UL;
        if (shift >= BITS_PER_LONG)
                return 0UL;
        return ~0UL >> shift;
}

height에 따른 최대 인덱스 값을 반환한다.

• 예) 32bit, height=2
  • 4095 (0xfff)
• 예) 32bit, height=6
  • 0xffff_ffff

radix_tree_callback()

lib/radix-tree.c

static int radix_tree_callback(struct notifier_block *nfb,
                            unsigned long action,
                            void *hcpu)
{
       int cpu = (long)hcpu;
       struct radix_tree_preload *rtp;

       /* Free per-cpu pool of perloaded nodes */
       if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) {
               rtp = &per_cpu(radix_tree_preloads, cpu);
               while (rtp->nr) {
                       kmem_cache_free(radix_tree_node_cachep,
                                       rtp->nodes[rtp->nr-1]);
                       rtp->nodes[rtp->nr-1] = NULL;
                       rtp->nr--;
               }
       }
       return NOTIFY_OK;
}

cpu가 offline 상태로 변경되는 경우 per-cpu 타입의 전역 radix_tree_preloads 캐시에 미리 준비해둔 radix_tree_node를 slub 캐시에 반환한다.

 

참조

• Radix Tree | 문c