Radix Tree
- Dynamic하게 정수 index key에 해당하는 slot에 포인터 값을 저장할 수 있다.
- 처음부터 큰 index key를 사용하면 트리 단계가 확장되어 느려지므로 작은 정수 index key를 사용하는 것이 좋다.
- 커널 버전 2.6.17에서 lockless한 구현을 하였다.
다음 그림은 2단계 Radix Tree의 구조를 표현하였다.
다음 그림은 Radix Tree의 최소 0단계로 index key 0번만을 등록시킬 수 있다. 이 상태에서 다른 번호의 index key를 추가하게 되면 radix 트리 단계(height)가 필요한 단계만큼 확장된다.
다음 그림은 index 값 크기에 따라 Radix Tree의 단계가 결정되는 것을 보여준다. (단계별 6bit 사용)
Radix 트리 선언
Radix 트리를 선언하고 초기화하는 방법은 다음과 같이 두 가지가 준비되어 있다.
- RADIX_TREE(name, mask);
- struct radix_tree_root my_tree; INIT_RADIX_TREE(my_tree, gfp_mask);
include/linux/radix-tree.h
#define RADIX_TREE(name, mask) \
struct radix_tree_root name = RADIX_TREE_INIT(mask)
요청한 name으로 radix_tree_root 구조체를 선언하고 gfp_mask를 대입하여 초기화한다.
include/linux/radix-tree.h
#define RADIX_TREE_INIT(mask) { \
.height = 0, \
.gfp_mask = (mask), \
.rnode = NULL, \
}
include/linux/radix-tree.h
#define INIT_RADIX_TREE(root, mask) \
do { \
(root)->height = 0; \
(root)->gfp_mask = (mask); \
(root)->rnode = NULL; \
} while (0)
Radix 트리 추가 및 삭제
Radix 트리에 항목을 추가하고 삭제하는 명령이 준비되어 있다.
- radix_tree_insert(root, index, item)
- radix_tree_delete(root, index)
radix_tree_insert()
lib/radix-tree.c
/**
* 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;
void **slot;
int error;
BUG_ON(radix_tree_is_indirect_ptr(item));
error = __radix_tree_create(root, index, &node, &slot);
if (error)
return error;
if (*slot != NULL)
return -EEXIST;
rcu_assign_pointer(*slot, item);
if (node) {
node->count++;
BUG_ON(tag_get(node, 0, index & RADIX_TREE_MAP_MASK));
BUG_ON(tag_get(node, 1, index & RADIX_TREE_MAP_MASK));
} else {
BUG_ON(root_tag_get(root, 0));
BUG_ON(root_tag_get(root, 1));
}
return 0;
}
EXPORT_SYMBOL(radix_tree_insert);
radix 트리의 index에 해당하는 슬롯에 item 포인터를 대입한다.
- error = __radix_tree_create(root, index, &node, &slot);
- index 키 번호로 radix 트리 slot을 준비한다.
- if (error) return error;
- 에러 시 에러를 반환한다.
- if (*slot != NULL) return -EEXIST;
- slot이 null이 아니면 이미 존재한다고 에러를 반환한다.
- rcu_assign_pointer(*slot, item);
- slot에 item을 대입한다.
__radix_tree_create()
lib/radix-tree.c
/**
* __radix_tree_create - create a slot in a radix tree
* @root: radix tree root
* @index: index key
* @nodep: returns node
* @slotp: returns slot
*
* Create, if necessary, and return the node and slot for an item
* at position @index in the radix tree @root.
*
* Until there is more than one item in the tree, no nodes are
* allocated and @root->rnode is used as a direct slot instead of
* pointing to a node, in which case *@nodep will be NULL.
*
* Returns -ENOMEM, or 0 for success.
*/
int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
struct radix_tree_node **nodep, void ***slotp)
{
struct radix_tree_node *node = NULL, *slot;
unsigned int height, shift, offset;
int error;
/* 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->path = height;
slot->parent = node;
if (node) {
rcu_assign_pointer(node->slots[offset], slot);
node->count++;
slot->path |= offset << RADIX_TREE_HEIGHT_SHIFT;
} 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 (nodep)
*nodep = node;
if (slotp)
*slotp = node ? node->slots + offset : (void **)&root->rnode;
return 0;
}
index 키에 해당하는 노드와 슬롯을 알아온다. 만일 확장이 필요한 경우 확장도 수행한다.
- if (index > radix_tree_maxindex(root->height)) { error = radix_tree_extend(root, index); if (error) return error; }
- index 키가 최대 값을 넘어가는 경우 radix 트리를 확장시킨다. 만일 에러인 경우 에러를 반환한다.
- slot = indirect_to_ptr(root->rnode);
- ptr에서 RADIX_TREE_INDIRECT_PTR(1)이 위치한 비트(bit0)를 제거한다.
- height = root->height; shift = (height-1) * RADIX_TREE_MAP_SHIFT;
- 현재 radix tree의 height(레벨)로 shift 값을 정한다.
- 예) height=3, RADIX_TREE_MAP_SHIFT=6
- shift=12
- 예) height=3, RADIX_TREE_MAP_SHIFT=6
- 현재 radix tree의 height(레벨)로 shift 값을 정한다.
- while (height > 0) {
- height가 0보다 큰 경우 루프를 돈다.
- if (slot == NULL) {
- slot이 비어 있는 경우
- if (!(slot = radix_tree_node_alloc(root))) return -ENOMEM;
- radix 트리 노드를 할당받는다. 에러가 발생하면 메모리 부족 에러를 반환한다.
- slot->path = height; slot->parent = node;
- slot의 path에 height를 대입하고, parent에 노드를 대입한다.
- if (node) { rcu_assign_pointer(node->slots[offset], slot); node->count++; slot->path |= offset << RADIX_TREE_HEIGHT_SHIFT;
- 루트 노드가 아닌 경우 노드의 slots[offset]에 slot을 대입하고, count를 증가시키며, path에 offset 값을 RADIX_TREE_HEIGHT_SHIFT만큼 좌로 쉬프트한 값을 대입한다.
- } else rcu_assign_pointer(root->rnode, ptr_to_indirect(slot));
- 루트 노드인 경우 root->rnode에 slot 포인터에 RADIX_TREE_INDEIRECT_PTR(1)을 더한 값을 대입한다.
- offset = (index >> shift) & RADIX_TREE_MAP_MASK;
- index 값에서 다음 레벨에 처리할 index bit 만큼을 offset에 대입한다.
- node = slot; slot = node->slots[offset];
- 다음 레벨의 노드를 알아온다.
- shift -= RADIX_TREE_MAP_SHIFT; height–;
- shift를 RADIX_TREE_MAP_SHIFT 만큼 감소시키고 height도 1 감소시킨다.
- if (nodep) *nodep = node;
- 인수 nodep가 주어진 경우 node를 대입한다.
- if (slotp) *slotp = node ? node->slots + offset : (void **)&root->rnode;
- 인수 slotp가 주어진 경우 슬롯을 대입한다.
- node가 null인 경우는 radix_tree_root 노드가 radix_tree_node 없이 직접 leaf를 관리하는 경우이다.
- 인수 slotp가 주어진 경우 슬롯을 대입한다.
다음 그림은 필요한 index key를 추가하기 위해 필요로하는 중간 노드들을 만들고 구성하는 과정을 보여준다.
radix_tree_extend()
lib/radix-tree.c
/*
* Extend a radix tree so it can store key @index.
*/
static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
{
struct radix_tree_node *node;
struct radix_tree_node *slot;
unsigned int height;
int tag;
/* Figure out what the height should be. */
height = root->height + 1;
while (index > radix_tree_maxindex(height))
height++;
if (root->rnode == NULL) {
root->height = height;
goto out;
}
do {
unsigned int newheight;
if (!(node = radix_tree_node_alloc(root)))
return -ENOMEM;
/* Propagate the aggregated tag info into the new root */
for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
if (root_tag_get(root, tag))
tag_set(node, tag, 0);
}
/* Increase the height. */
newheight = root->height+1;
BUG_ON(newheight & ~RADIX_TREE_HEIGHT_MASK);
node->path = newheight;
node->count = 1;
node->parent = NULL;
slot = root->rnode;
if (newheight > 1) {
slot = indirect_to_ptr(slot);
slot->parent = node;
}
node->slots[0] = slot;
node = ptr_to_indirect(node);
rcu_assign_pointer(root->rnode, node);
root->height = newheight;
} while (height > root->height);
out:
return 0;
}
Radix 트리 노드를 확장하기 위해 새로운 루트 노드를 추가하고 기존 노드를 새로 만든 노드의 첫 번째 슬롯에 연결한다. 이러한 과정을 확장이 필요한 단계만큼 수행한다.
- height = root->height + 1; while (index > radix_tree_maxindex(height)) height++;
- 현재 radix tree가 처리할 수 있는 레벨만큼 height 값을 정한다.
- if (root->rnode == NULL) { root->height = height; goto out; }
- 만일 슬롯이 비어 있는 경우 root->height값을 설정하고 함수를 빠져나간다.
- do { unsigned int newheight; if (!(node = radix_tree_node_alloc(root))) return -ENOMEM;
- 새 루트 노드를 생성한다.
- for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) { if (root_tag_get(root, tag)) tag_set(node, tag, 0); }
- 최대 태그 비트 수 만큼 루프를 돌며 루트 노드의 각 태그 비트가 1인 경우 0으로 초기화한다.
- 태그 비트는 gfp_mask의 비트들 중 __GFP_BITS_SHIFT(25) 비트부터 차례대로 사용된다.
- newheight = root->height+1; node->path = newheight;
- 새로운 루트 노드의 path에 height 값을 1 증가시켜 대입한다.
- node->count = 1; node->parent = NULL;
- 루트 노드의 count에 1을 대입하고 부모 노드가 없다고 지정한다.
- slot = root->rnode; if (newheight > 1) { slot = indirect_to_ptr(slot); slot->parent = node; } node->slots[0] = slot;
- 루트 노드의 첫 번째 슬롯에 기존 루트 노드를 연결한다.
- node = ptr_to_indirect(node); rcu_assign_pointer(root->rnode, node);
- root->rnode에
- root->height = newheight;
- 새 루트 노드의 hieght 값을 설정한다.
- } while (height > root->height);
- height가 현재 루트 노드의 height보다 큰 경우 새로운 루트 노드를 생성하기 위해 루프를 반복한다.
다음 그림은 1단계의 radix 트리가 2단계로 확장되는 모습을 보여준다.
radix_tree_node_alloc()
lib/radix-tree.c
/*
* This assumes that the caller has performed appropriate preallocation, and
* that the caller has pinned this thread of control to the current CPU.
*/
static struct radix_tree_node *
radix_tree_node_alloc(struct radix_tree_root *root)
{
struct radix_tree_node *ret = NULL;
gfp_t gfp_mask = root_gfp_mask(root);
/*
* Preload code isn't irq safe and it doesn't make sence to use
* preloading in the interrupt anyway as all the allocations have to
* be atomic. So just do normal allocation when in interrupt.
*/
if (!(gfp_mask & __GFP_WAIT) && !in_interrupt()) {
struct radix_tree_preload *rtp;
/*
* Provided the caller has preloaded here, we will always
* succeed in getting a node here (and never reach
* kmem_cache_alloc)
*/
rtp = this_cpu_ptr(&radix_tree_preloads);
if (rtp->nr) {
ret = rtp->nodes[rtp->nr - 1];
rtp->nodes[rtp->nr - 1] = NULL;
rtp->nr--;
}
/*
* Update the allocation stack trace as this is more useful
* for debugging.
*/
kmemleak_update_trace(ret);
}
if (ret == NULL)
ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
BUG_ON(radix_tree_is_indirect_ptr(ret));
return ret;
}
radix 트리 노드를 할당받아온다.
- radix_tree_preloads에 준비된 노드를 반환한다.
- 만일 radix_tree_preloads에 준비된 노드가 없으면 slub 캐시에서 할당 받아온다.
- gfp_t gfp_mask = root_gfp_mask(root);
- 루트 노드의 gfp_mask에서 태그를 제외한 값을 알아온다.
- if (!(gfp_mask & __GFP_WAIT) && !in_interrupt()) {
- 인터럽트 처리중이 아니면서 __GFP_WAIT 요청도 없는 경우
- rtp = this_cpu_ptr(&radix_tree_preloads); if (rtp->nr) { ret = rtp->nodes[rtp->nr – 1]; rtp->nodes[rtp->nr – 1] = NULL; rtp->nr–; }
- 전역 radix_tree_preloads 구조체가 관리하는 노드가 존재하는 경우 노드 하나를 빼온다.
- if (ret == NULL) ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
- 노드가 preload에 의해 준비되지 않은 경우 slub 캐시로부터 할당받아온다.
radix_tree_delete()
lib/radix-tree.c
/**
* radix_tree_delete - delete an item from a radix tree
* @root: radix tree root
* @index: index key
*
* Remove the item at @index from the radix tree rooted at @root.
*
* Returns the address of the deleted item, or NULL if it was not present.
*/
void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
{
return radix_tree_delete_item(root, index, NULL);
}
EXPORT_SYMBOL(radix_tree_delete);
Radix 트리에서 요청 index 키 항목을 제거한다.
radix_tree_delete_item()
lib/radix-tree.c
/**
* radix_tree_delete_item - delete an item from a radix tree
* @root: radix tree root
* @index: index key
* @item: expected item
*
* Remove @item at @index from the radix tree rooted at @root.
*
* Returns the address of the deleted item, or NULL if it was not present
* or the entry at the given @index was not @item.
*/
void *radix_tree_delete_item(struct radix_tree_root *root,
unsigned long index, void *item)
{
struct radix_tree_node *node;
unsigned int offset;
void **slot;
void *entry;
int tag;
entry = __radix_tree_lookup(root, index, &node, &slot);
if (!entry)
return NULL;
if (item && entry != item)
return NULL;
if (!node) {
root_tag_clear_all(root);
root->rnode = NULL;
return entry;
}
offset = index & RADIX_TREE_MAP_MASK;
/*
* Clear all tags associated with the item to be deleted.
* This way of doing it would be inefficient, but seldom is any set.
*/
for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
if (tag_get(node, tag, offset))
radix_tree_tag_clear(root, index, tag);
}
node->slots[offset] = NULL;
node->count--;
__radix_tree_delete_node(root, node);
return entry;
}
EXPORT_SYMBOL(radix_tree_delete_item);
Radix 트리에서 요청 index 키 항목을 제거하고 제거한 항목을 반환한다.
- entry = __radix_tree_lookup(root, index, &node, &slot);
- Radix 트리에서 요청 index 키 항목을 검색한다.
- if (item && entry != item) return NULL;
- 검색하여 찾은 entry 주소와 item 주소가 다른(mismatch) 경우 null을 반환한다.
- if (!node) { root_tag_clear_all(root); root->rnode = NULL; return entry; }
- 노드가 아닌 경우, 즉 키 인덱스가 0인 경우 루트에서 태그와 ptr 값을 지우고 해당 데이터 ptr 값을 반환한다.
- offset = index & RADIX_TREE_MAP_MASK;
- 현재 노드에서 요청한 인덱스 키에 해당하는 offset
- 0~RADIX_TREE_MAP_SIZE(63)
- for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) { if (tag_get(node, tag, offset)) radix_tree_tag_clear(root, index, tag); }
- offset에 위치한 태그가 설정되어 있는 경우 요청한 인덱스 키에 해당하는 3개 태그를 clear한다. 같은 노드가 관리하는 주변 64개의 태그들도 모두 없는 경우 상위노드로 진행하며 태그를 clear해 나간다.
- node->slots[offset] = NULL; node->count–;
- 슬롯을 비우고 사용 카운터를 1 감소시킨다.
- __radix_tree_delete_node(root, node);
- Radix 트리 노드가 필요 없는 경우 삭제한다.
- return entry;
- 삭제한 엔트리를 반환한다.
__radix_tree_lookup()
lib/radix-tree.c
/**
* __radix_tree_lookup - lookup an item in a radix tree
* @root: radix tree root
* @index: index key
* @nodep: returns node
* @slotp: returns slot
*
* Lookup and return the item at position @index in the radix
* tree @root.
*
* Until there is more than one item in the tree, no nodes are
* allocated and @root->rnode is used as a direct slot instead of
* pointing to a node, in which case *@nodep will be NULL.
*/
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 int height, shift;
void **slot;
node = rcu_dereference_raw(root->rnode);
if (node == NULL)
return NULL;
if (!radix_tree_is_indirect_ptr(node)) {
if (index > 0)
return NULL;
if (nodep)
*nodep = NULL;
if (slotp)
*slotp = (void **)&root->rnode;
return node;
}
node = indirect_to_ptr(node);
height = node->path & RADIX_TREE_HEIGHT_MASK;
if (index > radix_tree_maxindex(height))
return NULL;
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
do {
parent = node;
slot = 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);
if (nodep)
*nodep = parent;
if (slotp)
*slotp = slot;
return node;
}
Radix 트리에서 요청 index 키 항목을 검색한다. 발견되지 않으면 null을 반환한다.
- node = rcu_dereference_raw(root->rnode); if (node == NULL) return NULL;
- 루트에 연결된 노드 주소를 알아온다.
- if (!radix_tree_is_indirect_ptr(node)) {
- 노드가 아니라 직접 데이터 값이 있는 경우
- if (index > 0) return NULL;
- 요청 index가 0보다 크면 못찾은 경우이므로 null을 반환한다.
- 루트가 직접 데이터를 갖는 경우는 key 인덱스가 0인 경우 밖에 없다.
- if (nodep) *nodep = NULL;
- 루트에서 발견된 경우이므로 Radix 트리 노드 없어서 null을 출력인수 nodep에 대입한다.
- if (slotp) *slotp = (void **)&root->rnode; return node;
- 출력인수 slotp에 슬롯 주소(rnode가 단일 슬롯으로 동작) 값을 대입하고 데이터 ptr 값을 반환한다.
- node = indirect_to_ptr(node);
- 불필요한 플래그 비트를 제거하고 실제 노드 주소만 남긴다.
- 현재 node 값은 가장 상위 Radix 트리 노드 주소값이다.
- height = node->path & RADIX_TREE_HEIGHT_MASK; if (index > radix_tree_maxindex(height)) return NULL;
- 요청 인덱스 키값이 최상위 노드의 height 단계가 관리하는 값을 초과하는 경우 null을 반환한다.
- shift = (height-1) * RADIX_TREE_MAP_SHIFT;
- 가장 최상위 노드를 처리하기 위해 쉬프트할 비트 수를 결정한다.
- do { parent = node; slot = 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);
- 가장 상위 노드부터 가장 바닥 노드를 거쳐 leaf까지 루프를 돌며 연결된 노드를 찾아간다.
- if (nodep) *nodep = parent;
- 출력인수 nodep에 leaf를 관리하는 가장 마지막 노드를 대입한다.
- if (slotp) *slotp = slot; return node;
- 출력인수 slotp에 슬롯 주소를 대입하고 데이터 ptr 값을 반환한다.
radix_tree_tag_clear()
lib/radix-tree.c
/**
* radix_tree_tag_clear - clear a tag on a radix tree node
* @root: radix tree root
* @index: index key
* @tag: tag index
*
* Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
* corresponding to @index in the radix tree. If
* this causes the leaf node to have no tags set then clear the tag in the
* next-to-leaf node, etc.
*
* Returns the address of the tagged item on success, else NULL. ie:
* has the same return value and semantics as radix_tree_lookup().
*/
void *radix_tree_tag_clear(struct radix_tree_root *root,
unsigned long index, unsigned int tag)
{
struct radix_tree_node *node = NULL;
struct radix_tree_node *slot = NULL;
unsigned int height, shift;
int uninitialized_var(offset);
height = root->height;
if (index > radix_tree_maxindex(height))
goto out;
shift = height * RADIX_TREE_MAP_SHIFT;
slot = indirect_to_ptr(root->rnode);
while (shift) {
if (slot == NULL)
goto out;
shift -= RADIX_TREE_MAP_SHIFT;
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
node = slot;
slot = slot->slots[offset];
}
if (slot == NULL)
goto out;
while (node) {
if (!tag_get(node, tag, offset))
goto out;
tag_clear(node, tag, offset);
if (any_tag_set(node, tag))
goto out;
index >>= RADIX_TREE_MAP_SHIFT;
offset = index & RADIX_TREE_MAP_MASK;
node = node->parent;
}
/* clear the root's tag bit */
if (root_tag_get(root, tag))
root_tag_clear(root, tag);
out:
return slot;
}
EXPORT_SYMBOL(radix_tree_tag_clear);
요청한 인덱스 키에 해당하는 태그를 clear한다. 같은 노드가 관리하는 64개의 태그들도 모두 없는 경우 상위노드로 진행하며 태그를 clear해 나간다.
- height = root->height; if (index > radix_tree_maxindex(height)) goto out;
- 요청 index 키 값이 Radix 트리가 관리하는 단계를 초과하는 경우 null을 반환한다.
- shift = height * RADIX_TREE_MAP_SHIFT;
- 잠시 후에 루프를 돌며 index 키에서 각 단계별로 필요한 비트만큼을 쉬프트하여 사용할 것이므로 미리 가장 상위보다 한 단계 더 높은 단계로 쉬프트 값을 정해 놓는다.
- slot = indirect_to_ptr(root->rnode);
- 슬롯은 최상위 노드를 가리킨다.
- while (shift) { if (slot == NULL) goto out; shift -= RADIX_TREE_MAP_SHIFT; offset = (index >> shift) & RADIX_TREE_MAP_MASK; node = slot; slot = slot->slots[offset]; }
- 가장 바닥 단계까지 루프를 돌아 node와 slot에 가장 최하단 노드 주소와 슬롯 값을 대입하게 한다.
- if (slot == NULL) goto out;
- slot이 이미 비어 있는 경우 null을 반환한다.
- while (node) { if (!tag_get(node, tag, offset)) goto out; tag_clear(node, tag, offset); if (any_tag_set(node, tag)) goto out; index >>= RADIX_TREE_MAP_SHIFT; offset = index & RADIX_TREE_MAP_MASK; node = node->parent; }
- 가장 하위 노드부터 최상위 노드까지 루프를 돌며 index 키와 관련된 태크를 clear한다.
- 진행도중 현재 노드의 index 키와 관련된 태그가 이미 비어 있는 경우 함수를 빠져나간다.
- 진행도중 현재 노드와 관련된 64개의 다른 태그 비트가 여전히 존재하는 경우 상위로 진행하지 않고 함수를 빠져나간다.
- if (root_tag_get(root, tag)) root_tag_clear(root, tag);
- 여기까지 진행이 되었다는 의미는 최상위 노드마저도 모든 태그가 지워졌다는 의미이므로 루트에 있는 태그도 삭제한다.
다음 그림은 index 129번에 대한 0번 태그를 삭제할 때 하위 노드의 태그를 먼저 지운후 같은 노드의 태그가 모두 없는 경우 그 상위 노드의 태그마저 삭제하는 모습을 보여준다.
__radix_tree_delete_node()
lib/radix-tree.c
/**
* __radix_tree_delete_node - try to free node after clearing a slot
* @root: radix tree root
* @node: node containing @index
*
* After clearing the slot at @index in @node from radix tree
* rooted at @root, call this function to attempt freeing the
* node and shrinking the tree.
*
* Returns %true if @node was freed, %false otherwise.
*/
bool __radix_tree_delete_node(struct radix_tree_root *root,
struct radix_tree_node *node)
{
bool deleted = false;
do {
struct radix_tree_node *parent;
if (node->count) {
if (node == indirect_to_ptr(root->rnode)) {
radix_tree_shrink(root);
if (root->height == 0)
deleted = true;
}
return deleted;
}
parent = node->parent;
if (parent) {
unsigned int offset;
offset = node->path >> RADIX_TREE_HEIGHT_SHIFT;
parent->slots[offset] = NULL;
parent->count--;
} else {
root_tag_clear_all(root);
root->height = 0;
root->rnode = NULL;
}
radix_tree_node_free(node);
deleted = true;
node = parent;
} while (node);
return deleted;
}
요청 노드에 대해 shrink를 해본 후 사용 슬롯이 없는 경우 삭제하고 루프를 돌며 상위 노드로 이동하여 반복한다. 하나 이상 삭제된 경우 true를 반환한다.
- do { struct radix_tree_node *parent; if (node->count) { if (node == indirect_to_ptr(root->rnode)) { radix_tree_shrink(root); if (root->height == 0) deleted = true; } return deleted; }
- 요청한 노드의 count가 0보다 큰 경우 shrink를 시도한 후 결과를 반환한다.
- parent = node->parent; if (parent) { unsigned int offset; offset = node->path >> RADIX_TREE_HEIGHT_SHIFT; parent->slots[offset] = NULL; parent->count–;
- 부모 노드가 있는 경우 부모 노드에서 현재 노드로의 연결을 끊고 count를 줄인다.
- } else { root_tag_clear_all(root); root->height = 0; root->rnode = NULL; }
- 최상위 노드를 제거한다.
- 부모 노드가 없는 경우 루트 태그를 모두 clear하고 height를 0으로 만들고 item 연결을 끊는다.
- radix_tree_node_free(node); deleted = true; node = parent; } while (node);
- 현재 노드를 제거하고 그 상위 노드를 선택한 후 계속 진행한다.
- 상위 노드도 카운트가 0이 된 경우 제거한다.
- 현재 노드를 제거하고 그 상위 노드를 선택한 후 계속 진행한다.
radix_tree_shrink()
lib/radix-tree.c
/**
* radix_tree_shrink - shrink height of a radix tree to minimal
* @root radix tree root
*/
static inline void radix_tree_shrink(struct radix_tree_root *root)
{
/* try to shrink tree height */
while (root->height > 0) {
struct radix_tree_node *to_free = root->rnode;
struct radix_tree_node *slot;
BUG_ON(!radix_tree_is_indirect_ptr(to_free));
to_free = indirect_to_ptr(to_free);
/*
* The candidate node has more than one child, or its child
* is not at the leftmost slot, we cannot shrink.
*/
if (to_free->count != 1)
break;
if (!to_free->slots[0])
break;
/*
* We don't need rcu_assign_pointer(), since we are simply
* moving the node from one part of the tree to another: if it
* was safe to dereference the old pointer to it
* (to_free->slots[0]), it will be safe to dereference the new
* one (root->rnode) as far as dependent read barriers go.
*/
slot = to_free->slots[0];
if (root->height > 1) {
slot->parent = NULL;
slot = ptr_to_indirect(slot);
}
root->rnode = slot;
root->height--;
/*
* We have a dilemma here. The node's slot[0] must not be
* NULLed in case there are concurrent lookups expecting to
* find the item. However if this was a bottom-level node,
* then it may be subject to the slot pointer being visible
* to callers dereferencing it. If item corresponding to
* slot[0] is subsequently deleted, these callers would expect
* their slot to become empty sooner or later.
*
* For example, lockless pagecache will look up a slot, deref
* the page pointer, and if the page is 0 refcount it means it
* was concurrently deleted from pagecache so try the deref
* again. Fortunately there is already a requirement for logic
* to retry the entire slot lookup -- the indirect pointer
* problem (replacing direct root node with an indirect pointer
* also results in a stale slot). So tag the slot as indirect
* to force callers to retry.
*/
if (root->height == 0)
*((unsigned long *)&to_free->slots[0]) |=
RADIX_TREE_INDIRECT_PTR;
radix_tree_node_free(to_free);
}
}
Radix 트리 단계를 줄일 수 있는 경우 불필요한 Radix 트리 노드를 삭제하고 단계를 줄인다.
- 루프를 돌며 최상위 노드를 제거할 수 있는 경우 제거하여 Radix 트리 단계를 줄인다.
- 최상위 노드의 0번 슬롯만 있는 경우 현재 노드를 삭제하고 그 다음 노드를 최상위 노드로 변경한다.
- while (root->height > 0) { struct radix_tree_node *to_free = root->rnode;
- Radix 트리 단계가 1단계 이상인 경우 루트에 연결된 최상위 노드를 가져온다.
- to_free = indirect_to_ptr(to_free);
- 최상위 노드 포인터에서 RADIX_TREE_INDIRECT_PTR 비트를 제거한다.
- if (to_free->count != 1) break;
- 노드가 관리하는 슬롯이 하나가 아니면 그만 shrink를 중지하고 빠져나간다.
- if (!to_free->slots[0]) break;
- 남은 슬롯이 0번이 아닌 경우 그만 shrink를 중지하고 빠져나간다.
- slot = to_free->slots[0]; if (root->height > 1) { slot->parent = NULL; slot = ptr_to_indirect(slot); }root->rnode = slot; root->height–;
- 첫 슬롯에 연결된 다음 노드를 최상위 노드로 만든다.
- parent에 null을 넣고, 루트가 다음 노드를 가리키게 하고 height 값을 감소시킨다.
- if (root->height == 0) *((unsigned long *)&to_free->slots[0]) |= RADIX_TREE_INDIRECT_PTR;
- 루트 height값이 0이면 삭제할 노드의 첫 슬롯에 연결된 값은 item이더라도 RADIX_TREE_INDIRECT_PTR 비트를 더한다.
- radix_tree_node_free(to_free);
- rcu 방식을 사용하여 노드를 제거한다.
radix_tree_node_free()
lib/radix-tree.c
static inline void
radix_tree_node_free(struct radix_tree_node *node)
{
call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
}
Radix 트리 노드를 RCU 방식으로 제거한 후 slub 캐시로 반환한다(free).
radix_tree_node_rcu_free()
lib/radix-tree.c
static void radix_tree_node_rcu_free(struct rcu_head *head)
{
struct radix_tree_node *node =
container_of(head, struct radix_tree_node, rcu_head);
int i;
/*
* must only free zeroed nodes into the slab. radix_tree_shrink
* can leave us with a non-NULL entry in the first slot, so clear
* that here to make sure.
*/
for (i = 0; i < RADIX_TREE_MAX_TAGS; i++)
tag_clear(node, i, 0);
node->slots[0] = NULL;
node->count = 0;
kmem_cache_free(radix_tree_node_cachep, node);
}
Radix 트리 노드의 태그를 제거하고 slots[0]에 null을 대입하고, count를 0으로 만든 후 Radix 트리 노드 slub 캐시에 반환한다.(free)
Preload Radix 트리 노드
radix_tree_preload()
lib/radix-tree.c
/*
* Load up this CPU's radix_tree_node buffer with sufficient objects to
* ensure that the addition of a single element in the tree cannot fail. On
* success, return zero, with preemption disabled. On error, return -ENOMEM
* with preemption not disabled.
*
* To make use of this facility, the radix tree must be initialised without
* __GFP_WAIT being passed to INIT_RADIX_TREE().
*/
int radix_tree_preload(gfp_t gfp_mask)
{
/* Warn on non-sensical use... */
WARN_ON_ONCE(!(gfp_mask & __GFP_WAIT));
return __radix_tree_preload(gfp_mask);
}
EXPORT_SYMBOL(radix_tree_preload);
전역 per-cpu 타입의 radix tree preload 구조체에 빈 radix 트리 노드를 미리 할당받아 가득 채워 준비한다.
__radix_tree_preload()
lib/radix-tree.c
/*
* Load up this CPU's radix_tree_node buffer with sufficient objects to
* ensure that the addition of a single element in the tree cannot fail. On
* success, return zero, with preemption disabled. On error, return -ENOMEM
* with preemption not disabled.
*
* To make use of this facility, the radix tree must be initialised without
* __GFP_WAIT being passed to INIT_RADIX_TREE().
*/
static int __radix_tree_preload(gfp_t gfp_mask)
{
struct radix_tree_preload *rtp;
struct radix_tree_node *node;
int ret = -ENOMEM;
preempt_disable();
rtp = this_cpu_ptr(&radix_tree_preloads);
while (rtp->nr < ARRAY_SIZE(rtp->nodes)) {
preempt_enable();
node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
if (node == NULL)
goto out;
preempt_disable();
rtp = this_cpu_ptr(&radix_tree_preloads);
if (rtp->nr < ARRAY_SIZE(rtp->nodes))
rtp->nodes[rtp->nr++] = node;
else
kmem_cache_free(radix_tree_node_cachep, node);
}
ret = 0;
out:
return ret;
}
전역 per-cpu 타입의 radix tree preload 구조체에 빈 radix 트리 노드를 미리 할당 받아 가득 채워 준비한다.
- 중간에 slub 캐시로 부터 할당이 실패한 경우 preemption이 enable된 채로 빠져나온다. 성공한 경우 preemption이 disable된 채로 빠져나온다.
- 시스템 크기에 따라 최대 radix 트리 노드 수가 정해진다.
- 32bit=11
- 64bit=21
lib/radix-tree.c
/* * The radix tree is variable-height, so an insert operation not only has * to build the branch to its corresponding item, it also has to build the * branch to existing items if the size has to be increased (by * radix_tree_extend). * * The worst case is a zero height tree with just a single item at index 0, * and then inserting an item at index ULONG_MAX. This requires 2 new branches * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared. * Hence: */ #define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1)
- RADIX_TREE_PRELOAD_SIZE
- Radix 트리는 가변 단계(레벨, 높이)로 구성되는데 insert 한 번 수행시 최악의 경우 여러 개의 radix 트리 노드의 할당이 필요하다 따라서 최대 할당이 가능한 수 만큼 미리 radix 트리 프리로드 버퍼에 빈 radix 트리 노드들을 할당 받아 둔다.
- 예) 최악의 32bit 시스템 case
- height가 0인 상태에서 index 키 0xffffffff를 사용하는 경우 최대 11개의 rcu 트리 노드가 필요하다.
- Radix 트리 노드를 6단계까지 6번 확장 시키면서 6개가 필요하다.
- index 키에 맞는 radix 트리 노드를 만들기 위해 6단계를 제외한 1~5단계 각각에 하나씩 하여 5개가 필요하다.
- height가 0인 상태에서 index 키 0xffffffff를 사용하는 경우 최대 11개의 rcu 트리 노드가 필요하다.
- 예) 최악의 32bit 시스템 case
- 따라서 위와 같은 최대로 필요한 수에 맞추어 시스템에 따라 다음과 같이 크기가 결정된다.
- 32bit=11
- 64bit=21
- Radix 트리는 가변 단계(레벨, 높이)로 구성되는데 insert 한 번 수행시 최악의 경우 여러 개의 radix 트리 노드의 할당이 필요하다 따라서 최대 할당이 가능한 수 만큼 미리 radix 트리 프리로드 버퍼에 빈 radix 트리 노드들을 할당 받아 둔다.
다음 그림은 radix_tree_root가 0단계로 동작중에 long 최고 값을 index 키로 요청한 경우 32bit 시스템의 최대 단계인 6단계로 확장되면서 총 11개의 radix_tree_node가 필요한 경우를 보여준다.
기타 함수
ptr_to_indirect()
lib/radix-tree.c
static inline void *ptr_to_indirect(void *ptr)
{
return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);
}
leaf를 가리키지 않고 radix 트리 노드를 가리키는 경우 ptr에 RADIX_TREE_INDIRECT_PTR을 더해 저장한다.
indirect_to_ptr()
lib/radix-tree.c
static inline void *indirect_to_ptr(void *ptr)
{
return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
}
ptr에서 RADIX_TREE_INDIRECT_PTR을 제외한다.
root_gfp_mask()
lib/radix-tree.c
static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
{
return root->gfp_mask & __GFP_BITS_MASK;
}
루트에 저장된 gfp_mask에서 태그 비트를 제외한 순수 gfp_mask를 반환한다.
tag_set()
lib/radix-tree.c
static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
int offset)
{
__set_bit(offset, node->tags[tag]);
}
Radix 트리 노드의 tags[tag]의 offset 비트를 set 한다.
- 최대 태그 배열은 3개
tag_clear()
lib/radix-tree.c
static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
int offset)
{
__clear_bit(offset, node->tags[tag]);
}
Radix 트리 노드의 tags[tag]의 offset 비트를 clear 한다.
- 최대 태그 배열은 3개
tag_get()
lib/radix-tree.c
static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
int offset)
{
return test_bit(offset, node->tags[tag]);
}
Radix 트리 노드의 tags[tag]의 offset 비트 상태를 가져온다.
- 최대 태그 배열은 3개
root_tag_set()
lib/radix-tree.c
static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
{
root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
}
Radix 트리의 루트에 요청한 tag 비트를 설정한다.
root_tag_clear()
lib/radix-tree.c
static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
{
root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
}
Radix 트리의 루트에 요청한 tag 비트를 clear 한다.
root_tag_clear_all()
lib/radix-tree.c
static inline void root_tag_clear_all(struct radix_tree_root *root)
{
root->gfp_mask &= __GFP_BITS_MASK;
}
Radix 트리의 루트에 전체 tag 비트(총 3개)를 clear 한다.
root_tag_get()
lib/radix-tree.c
static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
{
return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
}
Radix 트리의 루트의 요청한 tag 비트 상태를 가져온다.
관련 상수
lib/radix-tree.c
#define RADIX_TREE_MAX_TAGS 3
#ifdef __KERNEL__
#define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6)
#else
#define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */
#endif
#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)
#define RADIX_TREE_TAG_LONGS \
((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
RADIX_TREE_MAP_SHIFT))
/* Height component in node->path */
#define RADIX_TREE_HEIGHT_SHIFT (RADIX_TREE_MAX_PATH + 1)
#define RADIX_TREE_HEIGHT_MASK ((1UL << RADIX_TREE_HEIGHT_SHIFT) - 1)
/* Internally used bits of node->count */
#define RADIX_TREE_COUNT_SHIFT (RADIX_TREE_MAP_SHIFT + 1)
#define RADIX_TREE_COUNT_MASK ((1UL << RADIX_TREE_COUNT_SHIFT) - 1)
아래 값들은 CONFIG_BASE_SMALL 커널 옵션을 사용하지 않을 경우의 값이다.
- RADIX_TREE_MAX_TAGS
- Radix 트리 최대 태그 수
- 3
- RADIX_TREE_MAP_SHIFT
- 6
- RADIX_TREE_MAP_SIZE
- Radix 트리가 사용하는 맵 크기
- 64
- RADIX_TREE_MAP_MASK
- Radix 트리가 사용하는 맵 마스크
- 0x3f
- RADIX_TREE_TAG_LONGS
- Radix 트리 태그 길이
- 32 bit=2, 64 bit=1
- 32 bit 시스템에서 64개의 비트를 위해 2 개의 long 값이 필요
- RADIX_TREE_INDEX_BITS
- Radix 트리 인덱스 비트 수
- 32bit=32, 64bit=64
- Radix 트리 인덱스 비트 수
- RADIX_TREE_MAX_PATH
- Radix 트리 최대 패스 수
- 32 bit=6, 64 bit=11
- Radix 트리 최대 패스 수
- RADIX_TREE_HEIGHT_SHIFT
- Radix 트리 height를 위한 shift 수
- 32 bit=7, 64 bit=12
- RADIX_TREE_HEIGHT_MASK
- Radix 트리 height를 위한 마스크
- 32 bit=0x3f, 64 bit=0x7ff
- RADIX_TREE_COUNT_SHIFT
- Radix 트리 count 쉬프트 수
- 7
- RADIX_TREE_COUNT_MASK
- Radix 트리 count에 사용하는 마스크
- 0x3f
구조체
radix_tree_root 구조체
include/linux/radix-tree.h
/* 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;
};
- height
- radix 트리가 관리하는 단계 수 (0~N)
- 0 단계에서는 Radix 트리 노드없이 오직 index 키 0 번 1개에 대한 슬롯을 직접 제공한다.
- 시스템 크기에 따라 최대 단계 수가 다르다.
- 32bit: 6
- 64bit: 11
- height가 0인 경우 index key가 하나도 등록이 되지 않았거나 하나의 0번 index key만을 등록한 경우이다.
- gfp_mask
- radix_tree_node 할당을 받을 때 마다 slub 캐시에 메모리 할당을 요청하는데 이 때 사용할 gfp_mask를 담고 있다.
- 추가로 3개의 tag 비트를 사용한다.
- rnode
- 노드를 가리키거나 한 개의 0번 index key에 해당하는 슬롯으로 동작하여 leaf의 포인터를 저장한다.
- 가장 상위 노드인 radix_tree_node를 가리키게 할 경우 RADIX_TREE_INDIRECT_PTR 비트를 추가하여 사용한다.
- 하나의 0번 index key만 사용된 경우 radix_tree_node를 만들지 않고 직접 rnode가 단일 슬롯으로 동작하여 item을 직접 저장한다.
- 노드를 가리키거나 한 개의 0번 index key에 해당하는 슬롯으로 동작하여 leaf의 포인터를 저장한다.
radix_tree_node 구조체
include/linux/radix-tree.h
struct radix_tree_node {
unsigned int path; /* Offset in parent & height from the bottom */
unsigned int count;
union {
struct {
/* Used when ascending tree */
struct radix_tree_node *parent;
/* For tree user */
void *private_data;
};
/* Used when freeing node */
struct rcu_head rcu_head;
};
/* For tree user */
struct list_head private_list;
void __rcu *slots[RADIX_TREE_MAP_SIZE];
unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};
- path
- 현재 노드의 레벨
- 가장 바닥 레벨은 1부터 시작한다.
- count
- 사용되고 있는 슬롯 수
- 0~최대 RADIX_TREE_MAP_SIZE(64)개까지
- *parent
- 상위 노드를 가리킨다.
- *private_data
- rcu_head
- rcu를 이용하여 노드를 삭제할 때 사용한다.
- private_list
- *slots[]
- RADIX_TREE_MAP_SIZE(64)개까지 다음 노드를 가리키거나 leaf에 해당하는 item을 저장한다.
- 노드를 가리키게 할 경우 RADIX_TREE_INDIRECT_PTR을 추가하여 사용한다.
- RADIX_TREE_MAP_SIZE(64)개까지 다음 노드를 가리키거나 leaf에 해당하는 item을 저장한다.
- tags[]
- 총 3개의 태그로 구성된 비트맵
- 각 비트맵은 RADIX_TREE_MAP_SIZE(64)개의 비트를 처리할 수 있는 공간을 가졌다.
- tags[][]의 이중 배열중 마지막은 실제 선언 시에만 사용되고 실제 처리 루틴에서는 tags[] 일차원 배열로만 이용한다.
- slot에 item이 저장되었는지 여부를 비트맵을 사용하여 표현한다.
- 태그 비트가 1이면 해당 비트 위치의 슬롯이 사용되었음을 의미한다.
radix_tree_preload 구조체
lib/radix-tree.c
/*
* Per-cpu pool of preloaded nodes
*/
struct radix_tree_preload {
int nr;
struct radix_tree_node *nodes[RADIX_TREE_PRELOAD_SIZE];
};
- nr
- 현재 cpu에 할당받은 빈 radix_tree_node 구조체의 수
- *nodes
- 할당 받은 radix_tree_node 포인터를 순서대로 배열에 가지고 있다.
참고
- Trees I: Radix trees | LWN.net
- radix_tree_init() | 문c
Radix tree공부하다가 참고합니다. 설명과 정리가 깔끔하게 되어있네요. 좋은 자료 감사합니다.
도움이 되었다니 감사합니다.
좋은 자료 감사합니다ㅠㅠ
감사합니다. 좋은 하루 되세요. ^^
정리가 너무 잘 되어 있어서 큰 도움이 되었습니다. 감사합니다.
감사합니다. 즐거운 주말 되세요. ^^