Maple Tree 자료구조

Maple Tree는 Linux 6.1에서 VMA 관리를 위해 Red-Black Tree를 대체한 현대적 B-tree 변형 자료구조입니다. 범위(range) 기반 키, RCU lock-free 읽기, 내장 잠금(Lock), 캐시(Cache) 친화적 노드 배치를 통해 mmap 경쟁 상황에서 획기적인 성능 개선을 제공합니다. B-tree 노드 구조(pivot/slot), walk 알고리즘, RCU-safe 연산, 노드 분할/병합, VMA rbtree에서 maple tree로의 마이그레이션 과정, 그리고 실측 성능 비교까지 다룹니다.

개요 및 배경

Maple Tree는 Liam R. Howlett(Oracle)가 개발한 B-tree 변형 자료구조로, Linux 6.1(2022년 12월)에 병합되었습니다. 주된 목표는 VMA(Virtual Memory Area) 관리에서 Red-Black Tree의 한계를 극복하는 것이었습니다.

RB-Tree의 한계

자료구조 구성

struct maple_tree

/* include/linux/maple_tree.h */
struct maple_tree {
    union {
        spinlock_t      ma_lock;       /* 내장 스핀락 (쓰기 보호) */
        lockdep_map_p  ma_external_lock; /* 외부 잠금 사용 시 */
    };
    unsigned int        ma_flags;      /* MT_FLAGS_* 플래그 */
    void __rcu         *ma_root;      /* 루트 노드 포인터 (RCU protected) */
};

/* ma_flags 비트 필드 */
#define MT_FLAGS_ALLOC_RANGE   0x01  /* gap 검색 활성화 (arange_64 사용) */
#define MT_FLAGS_USE_RCU       0x02  /* RCU 보호 모드 */
#define MT_FLAGS_HEIGHT_OFFSET 0x02  /* 높이 정보 오프셋 */
#define MT_FLAGS_HEIGHT_MASK   0x7C  /* 높이 비트마스크 */
#define MT_FLAGS_LOCK_MASK     0x300 /* 잠금 타입 마스크 */

struct ma_state (커서)

struct ma_state {
    struct maple_tree *tree;    /* 대상 트리 */
    unsigned long      index;   /* 현재 검색/삽입 인덱스 (범위 시작) */
    unsigned long      last;    /* 범위의 끝 (범위 검색 시) */
    struct maple_enode *node;   /* 현재 노드 (인코딩된 포인터) */
    unsigned long      min;    /* 현재 노드 최소 범위 */
    unsigned long      max;    /* 현재 노드 최대 범위 */
    struct maple_alloc *alloc;  /* 미리 할당된 노드 풀 (분할용) */
    unsigned char      depth;  /* 현재 트리 깊이 */
    unsigned char      offset; /* 현재 노드 내 슬롯 오프셋 */
    unsigned char      mas_flags; /* 커서 상태 플래그 */
};

/* ma_state 초기화 매크로 — 스택에 할당 */
#define MA_STATE(name, mt, first, end) \
    struct ma_state name = { \
        .tree = mt, \
        .index = first, \
        .last = end, \
        .node = MAS_START, \
        .min = 0, \
        .max = ULONG_MAX, \
        .alloc = NULL, \
        .mas_flags = 0, \
    }

노드 타입과 내부 구조

pivot/slot 관계 상세

/* maple_range_64 노드의 pivot/slot 관계 */
/*
 * 예: 5개 VMA가 저장된 잎 노드
 *
 * pivot[0]=0x1FFF  pivot[1]=0x3FFF  pivot[2]=0x6FFF  pivot[3]=0x9FFF  pivot[4]=ULONG_MAX
 *   |                 |                 |                 |                 |
 * slot[0]=VMA1     slot[1]=VMA2     slot[2]=NULL      slot[3]=VMA3     slot[4]=VMA4
 *   |                 |                 |                 |                 |
 * [0, 0x1FFF]     [0x2000, 0x3FFF] [0x4000, 0x6FFF] [0x7000, 0x9FFF] [0xA000, ...]
 * 사용 중           사용 중           gap (빈 공간)     사용 중           사용 중
 *
 * slot[i]의 범위: [prev_pivot+1, pivot[i]]
 * slot[0]의 범위: [node_min, pivot[0]]
 * slot[i]가 NULL이면 해당 범위는 빈 공간 (gap)
 */

struct maple_range_64 {
    struct maple_pnode *parent;
    unsigned long pivot[MAPLE_RANGE64_SLOTS - 1]; /* 15개 경계값 */
    union {
        void __rcu *slot[MAPLE_RANGE64_SLOTS]; /* 16개 슬롯 */
        struct {
            void __rcu *pad[MAPLE_RANGE64_SLOTS - 1];
            struct rcu_head rcu;
        };
    };
};

/* maple_arange_64 — gap 필드 추가 */
struct maple_arange_64 {
    struct maple_pnode *parent;
    unsigned long pivot[MAPLE_ARANGE64_SLOTS - 1]; /* 9개 경계값 */
    void __rcu *slot[MAPLE_ARANGE64_SLOTS];      /* 10개 슬롯 */
    unsigned long gap[MAPLE_ARANGE64_SLOTS];       /* 10개 gap 값 */
    struct maple_metadata meta;                    /* 끝 슬롯, gap 인덱스 */
};

Walk 알고리즘

Maple Tree의 핵심 연산은 walk입니다. 주어진 인덱스에 해당하는 잎 노드와 슬롯을 찾아가는 과정으로, B-tree의 top-down 탐색과 동일한 원리입니다.

/* lib/maple_tree.c — walk 핵심 로직 (간략화) */
static inline void *mas_walk(struct ma_state *mas)
{
    void *entry;

retry:
    entry = mas_state_walk(mas);
    if (mas_is_start(mas)) {
        /* 초기 상태: 루트에서 시작 */
        mas->node = mas_root(mas);
        mas->min = 0;
        mas->max = ULONG_MAX;
        mas->depth = 0;
        goto retry;
    }

    if (unlikely(mas_is_ptr(mas))) {
        /* 단일 항목 최적화: 루트가 직접 값을 가리킴 */
        if (mas->index == 0)
            return entry;
        return NULL;
    }

    /* 내부 노드 반복 순회 */
    while (!mas_is_leaf(mas)) {
        /* pivot 배열을 선형 스캔하여 적절한 슬롯 찾기 */
        mas_node_walk(mas);
        /* 자식 노드로 내려감 */
        mas->node = mas_get_slot(mas, mas->offset);
        mas->depth++;
    }

    /* 잎 노드에서 최종 슬롯 결정 */
    mas_node_walk(mas);
    return mas_get_slot(mas, mas->offset);
}

/* 노드 내 pivot 스캔 — 캐시 친화적 선형 탐색 */
static inline void mas_node_walk(struct ma_state *mas)
{
    unsigned long *pivots = ma_pivots(mas->node);
    unsigned char count = mt_pivot_count(mas->node);
    unsigned char offset = 0;

    /* pivot[i] >= index 인 첫 번째 i를 찾습니다 */
    while (offset < count && pivots[offset] < mas->index)
        offset++;

    mas->offset = offset;
    /* min/max 범위 갱신 */
    mas->min = offset ? pivots[offset - 1] + 1 : mas->min;
    mas->max = offset < count ? pivots[offset] : mas->max;
}

핵심 API

초기화

/* 정적 초기화 */
DEFINE_MTREE(my_tree);

/* 동적 초기화 */
struct maple_tree mt;
mt_init(&mt);                          /* 기본 초기화 */
mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE); /* 범위 할당 모드 (gap 검색) */
mt_init_flags(&mt, MT_FLAGS_USE_RCU);     /* RCU 모드 (외부 잠금) */

/* 트리 해제 (모든 항목 제거 후 메모리 해제) */
mtree_destroy(&mt);

기본 CRUD 연산

/* 단일 인덱스 저장 */
int ret = mtree_store(&mt, index, entry, GFP_KERNEL);

/* 범위 저장 [first, last] */
ret = mtree_store_range(&mt, first, last, entry, GFP_KERNEL);

/* 조회 (RCU 보호, lock-free) */
void *val = mtree_load(&mt, index);

/* 삭제 */
void *old = mtree_erase(&mt, index);

/* 범위 내 첫 번째 항목 찾기 */
void *entry;
unsigned long idx = 0;
entry = mt_find(&mt, &idx, ULONG_MAX);
/* idx는 in/out: 검색 시작 인덱스 → 결과 인덱스 */

/* 삽입 (중복 키 거부) */
ret = mtree_insert(&mt, index, entry, GFP_KERNEL);
/* 이미 존재하면 -EEXIST 반환 */

ma_state 기반 고급 API

/* ma_state 초기화 (스택 할당) */
MA_STATE(mas, &mt, start_index, end_index);

/* 범위 기반 저장 */
mas_lock(&mas);
ret = mas_store_gfp(&mas, entry, GFP_KERNEL);
mas_unlock(&mas);

/* 순회 (잠금 없이 RCU 읽기) */
rcu_read_lock();
mas_for_each(&mas, entry, ULONG_MAX) {
    /* entry: 현재 값, mas.index/mas.last: 현재 범위 */
    do_something(entry, mas.index, mas.last);
}
rcu_read_unlock();

/* gap 검색: [min_gap] 크기 이상의 빈 공간 찾기 */
ret = mas_empty_area(&mas, min_addr, max_addr, min_gap);
/* 성공 시 mas.index에 빈 공간 시작 주소 */

/* 역방향 gap 검색: 높은 주소부터 */
ret = mas_empty_area_rev(&mas, min_addr, max_addr, min_gap);

ma_state 에러 처리

/* mas_store_gfp 실패 처리 — 표준 패턴 */
MA_STATE(mas, &mt, start, end);
int ret;

retry:
mas_lock(&mas);
ret = mas_store_gfp(&mas, entry, GFP_KERNEL);
mas_unlock(&mas);
if (mas_nomem(&mas, GFP_KERNEL))  /* 노드 사전 할당 후 재시도 */
    goto retry;

mas_destroy(&mas);  /* 미사용 사전 할당 노드 반환 */

if (mas_is_err(&mas))
    return xa_err(mas.node);  /* -ENOMEM, -EEXIST 등 */

순회 매크로

/* mt_for_each: 전체 트리 순회 (가장 간단) */
unsigned long idx = 0;
void *entry;
mt_for_each(&mt, entry, idx, ULONG_MAX) {
    pr_info("idx=%lu entry=%p\n", idx, entry);
}

/* mas_for_each: ma_state로 순회 (범위 정보 접근 가능) */
MA_STATE(mas, &mt, 0, ULONG_MAX);
rcu_read_lock();
mas_for_each(&mas, entry, ULONG_MAX) {
    pr_info("[%lu, %lu] = %p\n", mas.index, mas.last, entry);
}
rcu_read_unlock();

/* mas_find / mas_next / mas_prev: 세밀한 순회 */
MA_STATE(mas, &mt, start, start);
rcu_read_lock();
entry = mas_find(&mas, end);     /* 첫 번째 항목 */
while (entry) {
    process(entry, mas.index, mas.last);
    entry = mas_next(&mas, end);  /* 다음 항목 */
}
rcu_read_unlock();

/* 역방향 순회 */
MA_STATE(mas, &mt, end, end);
entry = mas_find_rev(&mas, start);
while (entry) {
    process(entry, mas.index, mas.last);
    entry = mas_prev(&mas, start);
}

RCU-safe 연산

Maple Tree의 가장 강력한 특성은 쓰기 잠금 없이 읽기가 가능하다는 것입니다. 이는 RCU(Read-Copy-Update) 메커니즘을 통해 구현됩니다.

/* 올바른 동시 접근 패턴 */

/* 읽기 측: 잠금 없이 안전 */
void *concurrent_read(struct maple_tree *mt, unsigned long key)
{
    return mtree_load(mt, key);  /* 내부적으로 RCU 처리 */
}

/* 쓰기 측: 내장 잠금 사용 */
int concurrent_write(struct maple_tree *mt,
                      unsigned long start, unsigned long end,
                      void *val)
{
    MA_STATE(mas, mt, start, end);
    int ret;
retry:
    mas_lock(&mas);
    ret = mas_store_gfp(&mas, val, GFP_KERNEL);
    mas_unlock(&mas);
    if (mas_nomem(&mas, GFP_KERNEL))
        goto retry;
    mas_destroy(&mas);
    return mas_is_err(&mas) ? xa_err(mas.node) : 0;
}

노드 분할과 병합

Maple Tree는 B-tree 규칙에 따라 노드 용량을 관리합니다. 삽입 시 노드가 가득 차면 분할(split)하고, 삭제 시 노드가 희소해지면 병합(coalesce)합니다.

/* lib/maple_tree.c — 노드 분할 핵심 (간략화) */
static int mas_split(struct ma_state *mas,
                      struct maple_big_node *b_node)
{
    struct maple_enode *old = mas->node;
    struct maple_enode *left, *right;
    unsigned char split;

    /* 1. 분할 지점 결정 (대략 중간) */
    split = mas_split_final_node(b_node, mas, &mid_split);

    /* 2. 새 노드 2개 할당 */
    left  = mt_alloc_one(GFP_NOWAIT | __GFP_NOWARN);
    right = mt_alloc_one(GFP_NOWAIT | __GFP_NOWARN);

    /* 3. b_node 데이터를 좌/우로 분배 */
    mab_mas_cp(b_node, 0, split, left, ...);
    mab_mas_cp(b_node, split + 1, b_node->b_end, right, ...);

    /* 4. 부모 노드에 새 pivot과 포인터 삽입 */
    mas_set_parent(mas, left, mas->node, slot);
    mas_set_parent(mas, right, mas->node, slot + 1);

    /* 5. 구 노드 RCU 해제 예약 */
    call_rcu(&old->rcu, mt_free_rcu);

    return 0;
}

VMA 관리에서의 활용

mm_struct 변경 (Linux 6.1)

/* Linux 6.0 이전: RB-Tree 기반 VMA */
struct mm_struct {
    struct rb_root         mm_rb;      /* VMA RB-Tree 루트 */
    struct vm_area_struct  *mmap;      /* VMA 연결 리스트 (순회용) */
    unsigned long          highest_vm_end; /* 별도 augmented 정보 */
    int                    map_count; /* VMA 수 */
    /* ... */
};

/* Linux 6.1+: Maple Tree 기반 VMA */
struct mm_struct {
    struct maple_tree      mm_mt;      /* VMA Maple Tree */
    /* mm_rb, mmap 필드 제거됨 */
    /* highest_vm_end 제거 → arange_64 gap으로 대체 */
    int                    map_count; /* VMA 수 */
    /* ... */
};

/* mm_struct 초기화 시 Maple Tree 설정 */
static inline void mm_init(struct mm_struct *mm)
{
    mt_init_flags(&mm->mm_mt,
                  MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN |
                  MT_FLAGS_USE_RCU);
    /* ALLOC_RANGE: gap 검색 활성화 (arange_64 사용) */
    /* LOCK_EXTERN: mmap_lock으로 외부 잠금 */
    /* USE_RCU: RCU 보호 모드 */
}

VMA 검색 내부

/* mm/mmap.c: find_vma() — Linux 6.1+ */
struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
    struct vm_area_struct *vma;

    /* 1. VMA 캐시 먼저 확인 (per-thread, 대부분 적중) */
    vma = vmacache_find(mm, addr);
    if (likely(vma))
        return vma;

    /* 2. Maple Tree에서 검색 */
    MA_STATE(mas, &mm->mm_mt, addr, addr);
    vma = mas_find(&mas, ULONG_MAX);

    /* 3. VMA 캐시 갱신 */
    if (vma)
        vmacache_update(addr, vma);

    return vma;
}

/* mmap gap 검색: 빈 주소 공간 찾기 */
static unsigned long unmapped_area(struct vm_unmapped_area_info *info)
{
    struct mm_struct *mm = current->mm;
    MA_STATE(mas, &mm->mm_mt, 0, 0);

    /* arange_64 노드의 gap 필드를 이용한 O(log n) 검색 */
    if (info->flags & VM_UNMAPPED_AREA_TOPDOWN)
        ret = mas_empty_area_rev(&mas, info->low_limit,
                                  info->high_limit, info->length);
    else
        ret = mas_empty_area(&mas, info->low_limit,
                              info->high_limit, info->length);

    return mas.index;  /* 사용 가능한 시작 주소 */
}

RB-Tree에서 마이그레이션

Linux 6.1에서 VMA 관리가 RB-Tree에서 Maple Tree로 전환되었습니다. 이 과정에서 수백 개의 파일이 수정되었으며, API 변환이 필요했습니다.

API 대응 표

마이그레이션 코드 예시

/* Linux 6.0 이전: RB-Tree + 연결 리스트로 VMA 삽입 */
static void __vma_link_rb(struct mm_struct *mm,
                            struct vm_area_struct *vma,
                            struct rb_node **rb_link,
                            struct rb_node *rb_parent)
{
    /* RB-Tree에 삽입 */
    rb_link_node(&vma->vm_rb, rb_parent, rb_link);
    rb_insert_augmented(&vma->vm_rb, &mm->mm_rb,
                         &vma_gap_callbacks);
    /* 연결 리스트 업데이트 */
    vma->vm_next = next;
    if (next) next->vm_prev = vma;
    vma->vm_prev = prev;
}

/* Linux 6.1+: Maple Tree로 VMA 삽입 */
static void vma_mt_store(struct mm_struct *mm,
                          struct vm_area_struct *vma)
{
    /* Maple Tree에 범위로 삽입 — 단일 호출로 완료 */
    vma_store(mm, vma);
    /* 내부적으로: mtree_store_range(&mm->mm_mt,
                     vma->vm_start, vma->vm_end - 1, vma, GFP_KERNEL) */
    /* RB-Tree 삽입 + augmented 갱신 + 연결 리스트 갱신을
       단일 범위 저장으로 대체 */
}

vm_area_struct 변경

/* Linux 6.0 이전 */
struct vm_area_struct {
    unsigned long    vm_start;
    unsigned long    vm_end;
    struct vm_area_struct *vm_next, *vm_prev; /* 연결 리스트 */
    struct rb_node   vm_rb;                   /* RB-Tree 노드 */
    unsigned long    rb_subtree_gap;          /* augmented gap */
    /* ... */
};

/* Linux 6.1+ */
struct vm_area_struct {
    unsigned long    vm_start;
    unsigned long    vm_end;
    /* vm_next, vm_prev 제거 */
    /* vm_rb 제거 */
    /* rb_subtree_gap 제거 */
    /* Maple Tree 슬롯에 직접 포인터로 저장 */
    /* ... */
};

성능 특성

벤치마크 비교 (Linux 6.1)

트리 높이 분석

실전 활용 예제

드라이버에서의 범위 맵 구현

/* I/O 주소 범위 → 디바이스 맵핑 예제 */
struct io_region {
    phys_addr_t  base;
    size_t       size;
    struct device *dev;
};

struct maple_tree io_map;

static int register_io_region(phys_addr_t base, size_t size,
                                 struct device *dev)
{
    struct io_region *r = kmalloc(sizeof(*r), GFP_KERNEL);
    if (!r) return -ENOMEM;

    r->base = base;
    r->size = size;
    r->dev  = dev;

    /* [base, base+size-1] 범위에 등록 */
    return mtree_store_range(&io_map, base, base + size - 1, r, GFP_KERNEL);
}

static struct io_region *find_io_region(phys_addr_t addr)
{
    return mtree_load(&io_map, addr); /* addr이 속하는 범위 자동 검색 */
}

ID 범위 할당 예제

/* MT_FLAGS_ALLOC_RANGE: 빈 범위를 자동으로 찾아 할당 */
struct maple_tree id_map;
mt_init_flags(&id_map, MT_FLAGS_ALLOC_RANGE);

unsigned long id;
/* [0, 1023] 범위에서 빈 ID 1개 할당 */
int ret = mtree_alloc_range(&id_map, &id, my_data, 0, 1023, GFP_KERNEL);
if (!ret)
    pr_info("allocated id=%lu\n", id);

/* 해제 */
mtree_erase(&id_map, id);

procfs /proc/pid/maps 구현

/* fs/proc/task_mmu.c: /proc/pid/maps 출력 (Linux 6.1+) */
static void *m_start(struct seq_file *m, loff_t *ppos)
{
    struct proc_maps_private *priv = m->private;
    struct mm_struct *mm = priv->mm;
    struct vm_area_struct *vma;
    unsigned long last_addr = *ppos;

    /* Maple Tree로 /proc/maps 페이지 순회 */
    mmap_read_lock(mm);
    vma = find_vma(mm, last_addr);
    return vma;
}

static void *m_next(struct seq_file *m, void *v, loff_t *ppos)
{
    struct vm_area_struct *vma = v;
    /* 다음 VMA: Maple Tree 순회 (연결 리스트 제거됨) */
    return find_vma(vma->vm_mm, vma->vm_end);
}

잠금 모델 상세

외부 잠금 (VMA 트리)

/* VMA 트리는 외부 잠금(mmap_lock)을 사용 */

/* 읽기 경로: mmap_read_lock + RCU */
mmap_read_lock(mm);
vma = find_vma(mm, addr);      /* 내부: mas_find() */
mmap_read_unlock(mm);

/* 쓰기 경로: mmap_write_lock */
mmap_write_lock(mm);
vma_store(mm, vma);             /* 내부: mas_store_gfp() */
mmap_write_unlock(mm);

/* Speculative 읽기 (Linux 6.4+, per-VMA lock) */
rcu_read_lock();
vma = find_vma(mm, addr);
if (vma && vma_start_read(vma)) {
    /* per-VMA lock 획득 성공 → mmap_lock 없이 접근 */
    handle_vma(vma);
    vma_end_read(vma);
}
rcu_read_unlock();

커널 설정 및 디버깅(Debugging)

/* Kconfig 의존성 */
CONFIG_MAPLE_TREE=y        /* Linux 6.1+: 자동 활성화, 별도 설정 불필요 */
CONFIG_DEBUG_MAPLE_TREE=y  /* 디버그 빌드에서 트리 일관성 검증 활성화 */

# Maple Tree 디버깅 통계 (debugfs)
$ cat /sys/kernel/debug/maple_tree/stats

# Maple Tree 사용 지점 확인
$ grep -rn "mt_init\|mtree_store\|mas_find\|mm_mt" mm/ fs/proc/ --include="*.c"

# CONFIG_DEBUG_MAPLE_TREE 활성화 시 검증 함수
# mt_validate() — 트리 전체 일관성 검사
# mas_wr_state_check() — 쓰기 상태 검증
# 커널 빌드 시: make menuconfig → Kernel hacking → Debug maple tree

# ftrace로 Maple Tree 연산 추적
$ echo 'p:maple_probe mas_walk' > /sys/kernel/debug/tracing/kprobe_events
$ echo 1 > /sys/kernel/debug/tracing/events/kprobes/maple_probe/enable
$ cat /sys/kernel/debug/tracing/trace_pipe

검증 체크리스트

소스 코드 구조

# 소스 코드 탐색
$ wc -l lib/maple_tree.c include/linux/maple_tree.h
  7142 lib/maple_tree.c
   723 include/linux/maple_tree.h

# Maple Tree 셀프 테스트 실행
$ make menuconfig  # CONFIG_TEST_MAPLE_TREE=m
$ modprobe test_maple_tree
$ dmesg | grep "maple_tree"
maple_tree: all tests passed

# 사용자 공간 테스트
$ cd tools/testing/radix-tree
$ make maple
$ ./maple  # 모든 테스트 실행

B-tree 이론적 배경

Maple Tree의 동작 원리를 이해하려면 B-tree의 기본 개념을 알아야 합니다. B-tree는 1970년 Rudolf Bayer와 Edward McCreight가 발명한 자기 균형 탐색 트리로, 디스크 I/O 최소화를 위해 설계되었지만 현대 CPU의 캐시 계층에도 동일한 원리가 적용됩니다.

B-tree 핵심 속성

높이와 검색 비용 분석

B-tree의 높이 h는 항목 수 n과 분기 인자 b에 대해 h = O(log_b n)입니다. 분기 인자가 클수록 높이가 낮아집니다.

/* 높이 공식 (최대 높이) */
h ≤ log_⌈b/2⌉(n) + 1

/* Maple Tree maple_range_64 (b=16) */
n = 100,000 VMA일 때:
h ≤ log_8(100000) + 1 ≈ 5.5 + 1 = 6 (최대)
실제: 4 (노드 활용률이 높음)

/* RB-Tree (b=2) */
n = 100,000 VMA일 때:
h ≤ 2 × log_2(100001) ≈ 2 × 17 = 34 (최대)
실제: 약 17

/* 캐시 미스 비교 (L1 miss 기준) */
RB-Tree: 17 × ~4ns = ~68ns  (각 노드가 다른 캐시 라인)
Maple:    4 × ~8ns = ~32ns  (각 노드 256B = 4 캐시 라인, 순차 접근)
→ Maple Tree가 약 2배 빠름 (캐시 프리페치 효과 포함)

메모리 레이아웃과 캐시 효율

Maple Tree의 성능 우위는 캐시 친화적 메모리 레이아웃에서 비롯됩니다. 현대 CPU에서 메모리 접근 패턴이 성능을 좌우합니다.

캐시 라인 분석

/* maple_range_64 메모리 레이아웃 (256 바이트 = 캐시 라인 4개) */

오프셋     필드                   크기      캐시 라인
──────────────────────────────────────────────────────
0x000      parent                 8B   ┐
0x008      pivot[0..6]           56B   ┤ 캐시 라인 #0 (64B)
──────────────────────────────────────────────────────
0x040      pivot[7..14]          64B   │ 캐시 라인 #1 (64B)
──────────────────────────────────────────────────────
0x080      slot[0..7]            64B   │ 캐시 라인 #2 (64B)
──────────────────────────────────────────────────────
0x0C0      slot[8..15]           64B   │ 캐시 라인 #3 (64B)
──────────────────────────────────────────────────────

/* Walk 시 접근 패턴 */
1. pivot[0..6] 읽기  → 캐시 라인 #0 로드 (순차 접근 → 프리페치 활성)
2. pivot[7..14] 읽기 → 캐시 라인 #1 로드 (이미 프리페치됨)
3. slot[offset] 읽기  → 캐시 라인 #2 또는 #3

/* RB-Tree 접근 패턴 (비교) */
1. 노드 A의 key 읽기  → 캐시 라인 X 로드 (랜덤 주소)
2. 노드 A의 left/right 읽기 → 같은 캐시 라인 (포인터 추적)
3. 노드 B의 key 읽기  → 캐시 라인 Y 로드 (전혀 다른 주소)
4. 노드 C의 key 읽기  → 캐시 라인 Z 로드 (또 다른 주소)
→ 매 단계마다 캐시 미스 (프리페치 불가능)

Slab 할당과 노드 크기

/* lib/maple_tree.c — 노드 할당 */
static struct kmem_cache *maple_node_cache;

void maple_tree_init(void)
{
    maple_node_cache = kmem_cache_create(
        "maple_tree_node",
        sizeof(struct maple_node),  /* 256 바이트 */
        sizeof(struct maple_node),  /* 256B 정렬 */
        SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
        NULL);
}

/* 노드 할당 — SLAB에서 256B 정렬된 객체 획득 */
static inline struct maple_node *mt_alloc_one(gfp_t gfp)
{
    return kmem_cache_alloc(maple_node_cache, gfp);
}

/* 노드 해제 — RCU 콜백으로 지연 해제 */
static void mt_free_rcu(struct rcu_head *head)
{
    struct maple_node *node =
        container_of(head, struct maple_node, rcu);
    kmem_cache_free(maple_node_cache, node);
}

노드 포인터 인코딩

Maple Tree는 포인터 하위 비트에 메타데이터를 인코딩하여 추가 메모리 없이 노드 타입을 판별합니다. 이 기법은 XArray에서 그대로 가져온 것입니다.

/* include/linux/maple_tree.h — 포인터 인코딩 */

/* 노드 타입 열거형 */
enum maple_type {
    maple_dense,       /* 0b00 — 밀집 잎 노드 */
    maple_leaf_64,     /* 0b01 — range_64 잎 노드 */
    maple_range_64,    /* 0b10 — range_64 내부 노드 */
    maple_arange_64,   /* 0b11 — arange_64 내부/잎 노드 */
};

/* 포인터 → 인코딩된 노드 (encoded node = enode) */
static inline struct maple_enode *
mt_mk_node(const struct maple_node *node, enum maple_type type)
{
    return (struct maple_enode *)
           ((unsigned long)node | (unsigned long)type);
}

/* 인코딩된 노드 → 실제 노드 포인터 */
static inline struct maple_node *
mte_to_node(const struct maple_enode *enode)
{
    return (struct maple_node *)
           ((unsigned long)enode & ~0x7F);
}

/* 인코딩된 노드 → 타입 추출 */
static inline enum maple_type
mte_node_type(const struct maple_enode *enode)
{
    return (enum maple_type)
           ((unsigned long)enode & 0x7F);
}

/* 잎 노드인지 확인 */
static inline bool ma_is_leaf(enum maple_type type)
{
    return type < maple_range_64;
}

삽입 알고리즘 상세

Maple Tree의 삽입은 B-tree 삽입의 변형으로, big_node 임시 버퍼(Buffer)를 사용하여 분할 결정을 지연(Latency)합니다.

/* lib/maple_tree.c — 삽입 핵심 로직 (간략화) */
static inline int mas_wr_modify(struct ma_wr_state *wr_mas)
{
    struct ma_state *mas = wr_mas->mas;
    unsigned char node_slots = mt_slot_count(mas->node);
    unsigned char new_end;

    /* 덮어쓰기인 경우 (기존 범위에 새 값 저장) */
    if (wr_mas->entry && wr_mas->content) {
        /* 단순 슬롯 교체 — 가장 빠른 경로 */
        rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry);
        return 0;
    }

    /* 새 항목이 기존 범위를 분할하는 경우 */
    new_end = mas_wr_new_end(wr_mas);

    if (new_end < node_slots) {
        /* Fast path: 여유 공간 있음 → 슬롯 시프트 + 삽입 */
        mas_wr_slot_store(wr_mas);
    } else {
        /* Slow path: 노드 가득 참 → big_node → split */
        mas_wr_node_store(wr_mas, new_end);
        /* 내부적으로 mas_split() 호출 가능 */
    }

    return 0;
}

/* big_node: 분할 전 임시 확대 노드 */
struct maple_big_node {
    struct maple_pnode *parent;
    unsigned long pivot[MAPLE_BIG_NODE_SLOTS - 1]; /* 최대 32개 */
    union {
        struct maple_enode *slot[MAPLE_BIG_NODE_SLOTS];
        struct {
            struct maple_enode *slot[MAPLE_BIG_NODE_SLOTS];
            unsigned long gap[MAPLE_BIG_NODE_SLOTS];
        };
    };
    unsigned char b_end;
    enum maple_type type;
};

삭제 알고리즘 상세

삭제는 삽입의 역과정이지만, 추가적인 병합(coalesce) 로직이 필요합니다.

/* lib/maple_tree.c — 삭제 핵심 */
void *mas_erase(struct ma_state *mas)
{
    void *entry;
    MA_WR_STATE(wr_mas, mas, NULL);

    /* 1. 대상 항목 찾기 */
    entry = mas_walk(mas);
    if (!entry)
        return NULL;

    /* 2. 해당 슬롯을 NULL로 설정 (= gap 생성) */
    mas_wr_store_setup(&wr_mas);
    mas_wr_modify(&wr_mas);
    /* entry 값 = NULL → 해당 범위가 빈 공간이 됨 */

    /* 3. 노드가 희소해지면 병합 시도 */
    if (mas_is_underflow(mas))
        mas_coalesce(mas);

    return entry;
}

/* 병합 조건: 인접 형제 노드와 합쳐서 하나의 노드로 */
static bool mas_is_underflow(struct ma_state *mas)
{
    unsigned char end = mas_data_end(mas);
    unsigned char min = mt_min_slots(mas->node);
    return end < min;
    /* range_64: min = 8 (16/2) */
    /* arange_64: min = 5 (10/2) */
}

Gap 검색 알고리즘 상세

mas_empty_area()는 mmap에서 빈 가상 주소 공간을 찾는 핵심 연산입니다. maple_arange_64 노드의 gap[] 배열을 활용하여 O(log n)에 수행됩니다.

/* lib/maple_tree.c — gap 검색 (Bottom-up) */
int mas_empty_area(struct ma_state *mas,
                    unsigned long min, unsigned long max,
                    unsigned long size)
{
    unsigned char offset;
    unsigned long *pivots, *gaps;
    struct maple_node *node;

    /* 1. 루트에서 시작하여 충분한 gap이 있는 자식을 선택 */
    mas_start(mas);

    while (!mas_is_leaf(mas)) {
        node = mte_to_node(mas->node);
        gaps = ma_gaps(node, mte_node_type(mas->node));
        pivots = ma_pivots(node, mte_node_type(mas->node));

        /* 2. gap[i] >= size 인 첫 번째 슬롯 찾기 */
        for (offset = 0; offset <= ma_data_end(node); offset++) {
            if (gaps[offset] >= size &&
                pivots[offset] >= min)
                break;
        }

        /* 3. 해당 자식으로 내려감 */
        mas->offset = offset;
        mas->node = mas_get_slot(mas, offset);
        mas->depth++;
    }

    /* 4. 잎 노드에서 실제 빈 범위 확인 */
    /* NULL 슬롯 = 빈 공간, pivot 간 차이 = 공간 크기 */
    return mas_leaf_empty_area(mas, min, max, size);
}

fork() 시 Maple Tree 복사

fork() 시스템 콜(System Call)은 부모 프로세스(Process)의 전체 VMA 트리를 자식에게 복사해야 합니다. Maple Tree는 이 과정에서 RB-Tree보다 효율적인 벌크 복사를 지원합니다.

/* kernel/fork.c → mm/mmap.c */
static int dup_mmap(struct mm_struct *mm, struct mm_struct *oldmm)
{
    struct vm_area_struct *vma, *new_vma;
    MA_STATE(old_mas, &oldmm->mm_mt, 0, 0);
    MA_STATE(new_mas, &mm->mm_mt, 0, 0);
    int retval;

    /* 1. 부모 VMA 순회 + 자식 트리에 삽입 */
    mas_for_each(&old_mas, vma, ULONG_MAX) {
        /* VMA 복사 */
        new_vma = vm_area_dup(vma);
        if (!new_vma)
            goto fail;

        /* 페이지 테이블 COW 설정 */
        retval = copy_page_range(mm, oldmm, vma, new_vma);

        /* 자식 Maple Tree에 벌크 삽입 */
        new_mas.index = new_vma->vm_start;
        new_mas.last  = new_vma->vm_end - 1;
        mas_store(&new_mas, new_vma);
    }

    return 0;
}

메모리 오버헤드 분석

Maple Tree는 노드 크기가 크지만(256B), 노드당 저장하는 항목 수가 많아 전체 메모리 사용량은 RB-Tree와 비슷하거나 더 작습니다.

/* 1000개 VMA를 저장할 때 메모리 사용량 비교 */

RB-Tree:
  vm_area_struct: 각각 rb_node(24B) + list_head(16B) = 40B 추가
  총: 1000 × 40B = 40,000B = ~39KB

Maple Tree (arange_64):
  노드 수: 1000 / 10 = 100 잎 노드 + ~11 내부 노드 ≈ 111 노드
  총: 111 × 256B = 28,416B = ~28KB
  절감: ~28% 메모리 절약

Maple Tree (range_64):
  노드 수: 1000 / 16 = 63 잎 노드 + ~5 내부 노드 ≈ 68 노드
  총: 68 × 256B = 17,408B = ~17KB
  절감: ~57% 메모리 절약

고급 사용 패턴

노드 사전 할당 (원자적 컨텍스트)

/* 인터럽트 컨텍스트 등에서 GFP_KERNEL 불가 시 */
MA_STATE(mas, &mt, start, end);
int ret;

/* 1. 필요한 노드를 미리 할당 (슬립 가능 컨텍스트에서) */
ret = mas_preallocate(&mas, entry, GFP_KERNEL);
if (ret)
    return ret;

/* 2. 원자적 컨텍스트에서 삽입 (메모리 할당 불필요) */
spin_lock_irqsave(&my_lock, flags);
mas_lock(&mas);
mas_store_prealloc(&mas, entry);  /* GFP 불필요 */
mas_unlock(&mas);
spin_unlock_irqrestore(&my_lock, flags);

/* 3. 미사용 사전 할당 노드 반환 */
mas_destroy(&mas);

벌크 연산

/* 대량 항목을 효율적으로 삽입 */
MA_STATE(mas, &mt, 0, 0);

mas_lock(&mas);
for (int i = 0; i < count; i++) {
    mas.index = ranges[i].start;
    mas.last  = ranges[i].end;

    /* mas가 이전 위치를 기억하므로 연속 삽입이 빠름 */
    mas_store_gfp(&mas, entries[i], GFP_KERNEL);
}
mas_unlock(&mas);
mas_destroy(&mas);

/* 대량 삭제: 범위 지정 삭제 */
mtree_store_range(&mt, start, end, NULL, GFP_KERNEL);
/* [start, end] 범위의 모든 항목이 NULL로 덮어씌워짐 */

순회 중 일시 중지/재개

/* RCU 보호 순회에서 오래 걸리는 작업이 있을 때 */
MA_STATE(mas, &mt, 0, 0);
void *entry;

rcu_read_lock();
mas_for_each(&mas, entry, ULONG_MAX) {
    if (need_resched()) {
        /* 순회 일시 중지 */
        mas_pause(&mas);
        rcu_read_unlock();
        cond_resched();
        rcu_read_lock();
        /* 재개: mas_for_each가 자동으로 이전 위치에서 계속 */
        continue;
    }
    process_entry(entry);
}

기타 커널 사용처

VMA 관리 외에도 Maple Tree는 커널 내 여러 서브시스템에서 범위 기반 맵으로 활용됩니다.

per-VMA Lock 연동 (Linux 6.4+)

Maple Tree 도입 이후, Linux 6.4에서는 per-VMA lock이라는 추가 최적화가 도입되었습니다. 이는 Maple Tree의 RCU 읽기 경로를 활용하여, 페이지 폴트 처리 시 mmap_lock 전체를 잡지 않고 개별 VMA만 잠그는 방식입니다.

/* mm/memory.c — per-VMA lock 기반 페이지 폴트 (Linux 6.4+) */
static inline vm_fault_t
do_user_addr_fault(struct pt_regs *regs, unsigned long error_code,
                    unsigned long address)
{
    struct mm_struct *mm = current->mm;
    struct vm_area_struct *vma;

    /* Fast path: per-VMA lock 시도 */
    rcu_read_lock();
    vma = find_vma(mm, address);  /* Maple Tree RCU 읽기 */
    if (vma && vma_start_read(vma)) {
        /* VMA 전용 잠금 획득 성공 → mmap_lock 불필요 */
        rcu_read_unlock();
        fault = handle_mm_fault(vma, address, flags, regs);
        vma_end_read(vma);
        return fault;
    }
    rcu_read_unlock();

    /* Fallback: per-VMA lock 실패 → mmap_lock 사용 */
    mmap_read_lock(mm);
    vma = find_vma(mm, address);
    fault = handle_mm_fault(vma, address, flags, regs);
    mmap_read_unlock(mm);
    return fault;
}

향후 발전

트러블슈팅

일반적인 문제

디버깅 도구

/* CONFIG_DEBUG_MAPLE_TREE=y 활성화 시 사용 가능한 함수 */

/* 트리 전체 일관성 검증 (느림, 디버그 전용) */
mt_validate(&mt);

/* 트리 구조 덤프 (printk 출력) */
mt_dump(&mt, mt_dump_hex);   /* 16진수 모드 */
mt_dump(&mt, mt_dump_dec);   /* 10진수 모드 */

/* 출력 예시: */
/*
 * maple_arange64 0xffff...0000 parent 0 height 2
 *   entry 0: 0xffff...1000 [0 - 0x1FFF]
 *   entry 1: 0xffff...2000 [0x2000 - 0x3FFF]
 *   entry 2: (nil) [0x4000 - 0x6FFF]  ← gap
 *   ...
 */

# ftrace로 Maple Tree 연산 추적
echo 'p:mt_store mtree_store_range mt=%di:x64 start=%si:x64 end=%dx:x64' \
    > /sys/kernel/debug/tracing/kprobe_events
echo 1 > /sys/kernel/debug/tracing/events/kprobes/mt_store/enable
cat /sys/kernel/debug/tracing/trace_pipe

# bpftrace로 삽입/삭제 레이턴시 측정
bpftrace -e '
kprobe:mtree_store_range { @start[tid] = nsecs; }
kretprobe:mtree_store_range /@start[tid]/ {
    @latency = hist(nsecs - @start[tid]);
    delete(@start[tid]);
}
'

# SLAB 통계로 노드 수 확인
cat /proc/slabinfo | grep maple_tree
# maple_tree_node    12345  12800   256   16    1 : ...

API 레퍼런스 요약

라이프사이클 API

CRUD API

ma_state 고급 API

RCU-safe 연산

Maple Tree에서 RCU-safe 연산은 단순한 읽기/쓰기 분리를 넘어, 노드 수준의 원자적 교체와 grace period 관리를 포함합니다. mas_store_gfp()가 RCU 모드에서 동작하는 과정을 상세히 살펴봅니다.

mas_store_gfp() RCU 내부 동작

/* RCU 모드 저장의 핵심: 노드 수준 Copy-on-Write */
static inline void mas_store_rcu(struct ma_state *mas, void *entry)
{
    struct maple_enode *old_node = mas->node;
    struct maple_node *new_node;

    /* 1. 새 노드 할당 */
    new_node = mt_alloc_one(GFP_NOWAIT);
    if (!new_node)
        return;

    /* 2. 기존 노드 내용을 새 노드로 복사 */
    memcpy(new_node, mte_to_node(old_node),
           sizeof(struct maple_node));

    /* 3. 새 노드에 변경 사항 적용 */
    mte_set_slot(new_node, mas->offset, entry);

    /* 4. 부모 슬롯을 원자적으로 교체 (메모리 배리어 포함) */
    rcu_assign_pointer(
        mte_parent_slot(old_node),
        mt_mk_node(new_node, mte_node_type(old_node))
    );

    /* 5. 구 노드를 grace period 후 해제 */
    call_rcu(&mte_to_node(old_node)->rcu, mt_free_rcu);
}

Lock-free 읽기 경로 상세

/* Lock-free 읽기: rcu_dereference()가 핵심 */
static inline void *mas_walk_rcu(struct ma_state *mas)
{
    struct maple_enode *node;
    void *entry;
    unsigned char offset;

retry:
    node = rcu_dereference(mas->tree->ma_root);

    while (!mte_is_leaf(node)) {
        unsigned long *pivots = ma_pivots(mte_to_node(node));
        void __rcu **slots = ma_slots(mte_to_node(node));

        /* pivot 스캔으로 슬롯 결정 */
        offset = 0;
        while (offset < mt_pivot_count(node) &&
               pivots[offset] < mas->index)
            offset++;

        /* RCU 보호 하에 자식 포인터 읽기 */
        node = rcu_dereference(slots[offset]);

        /* 동시 수정 감지: dead 노드면 재시도 */
        if (unlikely(ma_dead_node(node)))
            goto retry;
    }

    /* 잎 노드에서 값 읽기 */
    entry = rcu_dereference(ma_slots(mte_to_node(node))[offset]);
    return entry;
}

노드 타입

Maple Tree의 세 가지 노드 타입(maple_range_64, maple_arange_64, maple_dense)은 각각 다른 사용 패턴에 최적화되어 있습니다. 여기서는 pivot 인코딩 방식과 노드 타입 전환 규칙을 상세히 분석합니다.

Pivot 인코딩

/* maple_range_64 구조에서 pivot 해석 규칙 */

/* 슬롯 i의 범위를 계산하는 내부 함수 */
static inline void mas_slot_range(
    struct ma_state *mas,
    unsigned char offset,
    unsigned long *r_min,
    unsigned long *r_max)
{
    unsigned long *pivots = ma_pivots(mte_to_node(mas->node));

    /* 하한: slot[0]이면 node_min, 아니면 pivot[offset-1] + 1 */
    *r_min = offset ? pivots[offset - 1] + 1 : mas->min;

    /* 상한: 마지막 유효 슬롯이면 node_max, 아니면 pivot[offset] */
    if (offset < mt_pivot_count(mas->node) && pivots[offset])
        *r_max = pivots[offset];
    else
        *r_max = mas->max;
}

/* maple_arange_64의 gap 필드 해석 */
/*
 * gap[i] = slot[i]가 가리키는 서브트리 내 최대 연속 빈 공간 크기
 *
 * 잎 노드:   gap[i] = slot[i]가 NULL인 범위의 크기
 * 내부 노드: gap[i] = max(자식 노드의 모든 gap[j])
 *
 * meta.gap = gap[] 배열에서 최대값을 가진 인덱스
 *            → 빠른 최대 gap 위치 조회용
 */
struct maple_metadata {
    unsigned char end;   /* 마지막 유효 슬롯 인덱스 */
    unsigned char gap;   /* 최대 gap을 가진 슬롯 인덱스 */
};

노드 타입 선택 규칙

벌크 연산과 사전 할당

대량의 항목을 순서대로 삽입해야 하는 경우(예: fork()에서 VMA 복사), Maple Tree는 벌크 연산 최적화를 제공합니다. mas_expected_entries()를 통해 필요한 노드를 미리 할당하면 삽입 중 메모리 할당 실패를 방지할 수 있습니다.

mas_expected_entries() 사전 할당

/* kernel/fork.c — fork() 시 VMA 벌크 복사 */
static int dup_mmap(struct mm_struct *mm, struct mm_struct *oldmm)
{
    MA_STATE(old_mas, &oldmm->mm_mt, 0, 0);
    MA_STATE(mas, &mm->mm_mt, 0, 0);
    struct vm_area_struct *vma, *new_vma;
    int retval;

    /* 핵심: 예상 항목 수만큼 노드 사전 할당
     * oldmm의 VMA 수(map_count)를 기반으로 필요한 노드를 미리 할당
     * → 삽입 루프 중 메모리 할당이 불필요 */
    retval = mas_expected_entries(&mas, oldmm->map_count);
    if (retval)
        goto out;

    /* 기존 VMA를 순서대로 복사하여 새 트리에 삽입 */
    mas_for_each(&old_mas, vma, ULONG_MAX) {
        new_vma = vm_area_dup(vma);
        if (!new_vma)
            goto fail;

        /* 사전 할당된 노드를 사용하여 삽입 (메모리 할당 없음) */
        mas.index = new_vma->vm_start;
        mas.last  = new_vma->vm_end - 1;
        mas_store(&mas, new_vma);
    }

    /* 미사용 사전 할당 노드 반환 (반드시 호출) */
    mas_destroy(&mas);
    return 0;
fail:
    mas_destroy(&mas);
    return -ENOMEM;
}

사전 할당 노드 수 계산

/* lib/maple_tree.c — 필요 노드 수 계산 */
int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries)
{
    int nonleaf_cap = MAPLE_ARANGE64_SLOTS;  /* 10 (arange) 또는 16 (range) */
    int leaf_cap    = MAPLE_RANGE64_SLOTS;   /* 16 */
    int nr_nodes;

    /* 잎 노드 수 = ceil(nr_entries / leaf_cap) */
    nr_nodes = DIV_ROUND_UP(nr_entries, leaf_cap);

    /* 내부 노드 수 = 잎 노드 수에 대한 기하 급수 합
     * level 1: ceil(nr_leaves / nonleaf_cap)
     * level 2: ceil(level1_nodes / nonleaf_cap)
     * ... 루트까지 */
    {
        int level_nodes = nr_nodes;
        while (level_nodes > 1) {
            level_nodes = DIV_ROUND_UP(level_nodes, nonleaf_cap);
            nr_nodes += level_nodes;
        }
    }

    /* 분할/재균형 여분 추가 (약 10~20%) */
    nr_nodes += nr_nodes / 10;

    /* mas->alloc에 미리 할당 */
    mas_node_count_gfp(mas, nr_nodes, GFP_KERNEL);
    return mas_is_err(mas) ? -ENOMEM : 0;
}

커널 자료구조 비교

Linux 커널에는 여러 범위/키-값 자료구조가 공존합니다. 각각의 특성과 적합한 사용 사례를 비교합니다.

VMA 관리 케이스 스터디

mmap, munmap, mremap 시스템 콜이 Maple Tree를 통과하는 경로를 상세히 추적합니다.

mmap() 경로

munmap() 경로

/* mm/mmap.c — munmap 시 Maple Tree 연산 (Linux 6.1+) */
static int do_munmap(struct mm_struct *mm,
                      unsigned long start, size_t len,
                      struct list_head *uf)
{
    MA_STATE(mas, &mm->mm_mt, start, start + len - 1);
    struct vm_area_struct *vma;

    /* 1. 해당 범위의 VMA 찾기 */
    vma = mas_find(&mas, start + len - 1);
    if (!vma)
        return -ENOMEM;

    /* 2. VMA가 요청 범위와 부분 겹침이면 분할 */
    if (vma->vm_start < start) {
        /* 앞쪽 분할: VMA를 start 위치에서 자르기 */
        __split_vma(mm, vma, start, 0);
        /* Maple Tree: 기존 범위 축소 + 새 VMA 삽입 */
    }
    if (vma->vm_end > start + len) {
        /* 뒤쪽 분할: VMA를 start+len 위치에서 자르기 */
        __split_vma(mm, vma, start + len, 1);
    }

    /* 3. 범위 내 모든 VMA 삭제 */
    mas_set_range(&mas, start, start + len - 1);
    mas_store_prealloc(&mas, NULL);
    /* NULL 저장 = 범위 삭제, gap[] 자동 갱신 */

    return 0;
}

mremap() 경로

/* mm/mremap.c — mremap 시 Maple Tree 연산 */
static unsigned long move_vma(struct vm_area_struct *vma,
                                unsigned long old_addr, unsigned long old_len,
                                unsigned long new_len, unsigned long new_addr)
{
    struct mm_struct *mm = vma->vm_mm;

    /* 1. 새 위치에 빈 공간 확인 (mas_empty_area) */
    /* 2. 구 위치에서 VMA 삭제 (Maple Tree store NULL) */
    do_munmap(mm, old_addr, old_len, &uf);

    /* 3. 새 위치에 VMA 삽입 (Maple Tree store) */
    vma->vm_start = new_addr;
    vma->vm_end   = new_addr + new_len;
    vma_mt_store(mm, vma);

    /* 4. 페이지 테이블 이동 (Maple Tree 무관) */
    move_page_tables(vma, old_addr, ...);

    return new_addr;
}

메모리 컴팩션과 상호작용

메모리 컴팩션(compaction)은 물리 페이지를 재배치(Relocation)하여 연속 빈 페이지를 확보하는 과정입니다. 이 과정에서 VMA 정보를 조회해야 하므로 Maple Tree와 상호작용합니다.

/* mm/compaction.c — 컴팩션 시 VMA 조회 */
static bool suitable_migration_target(
    struct compact_control *cc,
    struct page *page)
{
    struct vm_area_struct *vma;
    struct mm_struct *mm;

    /* 역매핑(rmap)으로 페이지의 VMA 찾기 */
    vma = page_vma(page);
    if (!vma)
        return false;

    mm = vma->vm_mm;

    /* RCU 읽기 경로: Maple Tree에서 VMA 존재 확인
     * 컴팩션은 프로세스 컨텍스트에서 실행되므로
     * mmap_lock을 잡지 않고 RCU 읽기만으로 VMA 조회 가능 */
    rcu_read_lock();
    vma = find_vma(mm, page_address(page));
    /* find_vma() 내부에서 Maple Tree RCU 읽기 수행 */
    rcu_read_unlock();

    return vma != NULL;
}

/* 컴팩션과 Maple Tree의 핵심 상호작용 포인트 */
/*
 * 1. migrate_pages(): 페이지 이동 시 VMA 조회 (RCU 읽기)
 * 2. isolate_migratepages(): 이동 대상 선별 시 VMA 범위 확인
 * 3. compact_zone(): THP 후보 영역 판단 시 VMA 플래그 확인
 *
 * Maple Tree의 RCU lock-free 읽기 덕분에
 * 컴팩션이 mmap_lock 없이도 VMA 정보를 안전하게 조회 가능
 * → 컴팩션과 페이지 폴트가 동시에 진행될 수 있음
 */

반복자 패턴 상세

Maple Tree는 세 가지 수준의 반복자(iterator) 패턴을 제공합니다. 각각의 사용 사례와 성능 특성을 비교합니다.

mt_for_each() — 간편 순회

/* mt_for_each: 가장 간단한 순회 매크로 */
/* 내부적으로 ma_state를 생성하고 관리 */
#define mt_for_each(__tree, __entry, __index, __max)  \
    for (__entry = mt_find(__tree, &(__index), __max); \
         __entry;                                       \
         __entry = mt_find_after(__tree, &(__index), __max))

/* 사용 예: 전체 VMA 출력 */
void dump_all_vmas(struct mm_struct *mm)
{
    struct vm_area_struct *vma;
    unsigned long idx = 0;

    mmap_read_lock(mm);
    mt_for_each(&mm->mm_mt, vma, idx, ULONG_MAX) {
        pr_info("VMA [%lx-%lx] flags=%lx\n",
                vma->vm_start, vma->vm_end, vma->vm_flags);
    }
    mmap_read_unlock(mm);
}

mas_for_each() — 범위 정보 접근

/* mas_for_each: 범위 정보(mas.index, mas.last)에 접근 가능 */
#define mas_for_each(__mas, __entry, __max)         \
    while ((__entry = mas_find(__mas, __max)) != NULL)

/* 사용 예: 특정 범위 내 VMA와 gap 분석 */
void analyze_address_space(struct mm_struct *mm,
                            unsigned long start, unsigned long end)
{
    MA_STATE(mas, &mm->mm_mt, start, start);
    struct vm_area_struct *vma;
    unsigned long prev_end = start;
    unsigned long total_gap = 0, total_mapped = 0;

    rcu_read_lock();
    mas_for_each(&mas, vma, end) {
        /* gap: prev_end ~ mas.index 사이의 미사용 공간 */
        if (mas.index > prev_end)
            total_gap += mas.index - prev_end;

        /* mapped: mas.index ~ mas.last (= vm_start ~ vm_end-1) */
        total_mapped += mas.last - mas.index + 1;
        prev_end = mas.last + 1;

        pr_info("VMA [%lx-%lx] size=%lu KB\n",
                mas.index, mas.last + 1,
                (mas.last - mas.index + 1) >> 10);
    }
    rcu_read_unlock();

    pr_info("Total: mapped=%lu KB, gap=%lu KB\n",
            total_mapped >> 10, total_gap >> 10);
}

mas_find() / mas_next() — 세밀한 제어

/* mas_find + mas_next: 조건부 순회, 조기 종료 가능 */
void find_executable_vmas(struct mm_struct *mm)
{
    MA_STATE(mas, &mm->mm_mt, 0, 0);
    struct vm_area_struct *vma;
    int count = 0;

    rcu_read_lock();
    /* 첫 번째 VMA 검색 */
    vma = mas_find(&mas, ULONG_MAX);
    while (vma) {
        if (vma->vm_flags & VM_EXEC) {
            pr_info("Exec VMA: [%lx-%lx]\n",
                    vma->vm_start, vma->vm_end);
            count++;
            if (count >= 10)
                break;  /* 최대 10개만 출력 */
        }
        /* 다음 VMA로 이동 */
        vma = mas_next(&mas, ULONG_MAX);
    }
    rcu_read_unlock();
}

/* mas_find_rev + mas_prev: 역방향 순회 */
void find_last_n_vmas(struct mm_struct *mm, int n)
{
    MA_STATE(mas, &mm->mm_mt, ULONG_MAX, ULONG_MAX);
    struct vm_area_struct *vma;

    rcu_read_lock();
    vma = mas_find_rev(&mas, 0);
    while (vma && n-- > 0) {
        pr_info("VMA [%lx-%lx]\n", vma->vm_start, vma->vm_end);
        vma = mas_prev(&mas, 0);
    }
    rcu_read_unlock();
}

잠금 경합 분석

Maple Tree 도입의 가장 큰 동기 중 하나는 mmap_lock 경합 감소였습니다. mmap_lock과 per-VMA lock의 상호작용을 분석합니다.

mmap_lock 경합 시나리오

잠금 계층 구조

잠금 계층: 넓은 범위 → 좁은 범위 순으로 획득

Level 0: mmap_write_lock(mm) — mm 전체 독점 (mmap/munmap/mremap) Level 1: mmap_read_lock(mm) — mm 전체 공유 읽기 (fallback 경로) Level 2: rcu_read_lock() — Maple Tree RCU 읽기 (가장 경량) Level 3: vma_start_read(vma) — 개별 VMA 읽기 잠금 (6.4+) Level 4: mas_lock(&mas) — Maple Tree 내장 스핀락 (쓰기)

일반적인 경로:

• 페이지 폴트 (읽기): Level 2 → Level 3 (Level 1 fallback)
• mmap()/munmap(): Level 0 → Level 4
• /proc/pid/maps: Level 1 (또는 Level 2)
• 컴팩션: Level 2

잠금 경합 측정: lockstat 활용

# echo 1 > /proc/lock_stat # cat /proc/lock_stat | grep mmap

class name con-bounces contentions waittime-min ... mmap_lock-W: 12345 67890 0.50 ... mmap_lock-R: 5678 23456 0.10 ...

per-VMA lock 도입 후: mmap_lock-R 경합이 75%+ 감소

디버깅

CONFIG_DEBUG_MAPLE_TREE 활성화 시 사용 가능한 디버깅 기능과 mt_dump/mt_validate의 내부 동작을 상세히 분석합니다.

mt_dump() 출력 해석

/* mt_dump() 사용법과 출력 해석 */
mt_dump(&mt, mt_dump_hex);

/* 출력 예시 (arange_64 트리, 5개 VMA):
 *
 * maple_arange64 0xffff888100a00000 parent 0xffff888100b00001
 *   height 2 flags 0x05 (ALLOC_RANGE|USE_RCU)
 *
 *   [0] 0xffff888100c00000 [0x0 - 0x7fffffffffff]
 *       maple_arange64 0xffff888100c00000 parent 0xffff888100a00001
 *         [0] 0xffff888100d00000 [0x555555554000 - 0x555555558fff]
 *             → VMA: /usr/bin/app (r-xp)
 *         [1] (nil) [0x555555559000 - 0x55555555bfff]
 *             → gap: 0x3000 bytes
 *         [2] 0xffff888100e00000 [0x55555555c000 - 0x55555555dfff]
 *             → VMA: [heap] (rw-p)
 *         ...
 *       gap[0]=0x0  gap[1]=0x3000  gap[2]=0x0  ...
 *       meta: end=4 gap=1
 *
 * 해석 가이드:
 * - 각 [N]은 slot[N]의 값과 해당 범위
 * - (nil) = NULL slot = 빈 공간 (gap)
 * - gap[N] = slot[N] 서브트리의 최대 연속 빈 공간
 * - meta.end = 마지막 유효 슬롯 인덱스
 * - meta.gap = 최대 gap을 가진 슬롯 인덱스
 */

mt_validate() 내부 검증 항목

/* lib/maple_tree.c — mt_validate()가 검증하는 항목들 */
void mt_validate(struct maple_tree *mt)
{
    /* 1. 루트 포인터 유효성 */
    /* ma_root가 NULL이 아니면 유효한 노드 포인터인지 확인 */

    /* 2. 부모 포인터 일관성 */
    /* 모든 노드의 parent가 실제 부모를 가리키는지 확인 */
    /* parent.slot[i] == this_node 인지 교차 검증 */

    /* 3. pivot 정렬 */
    /* pivot[0] < pivot[1] < ... < pivot[end] 단조 증가 확인 */
    /* pivot[i] >= node_min && pivot[i] <= node_max 범위 확인 */

    /* 4. 슬롯 유효성 */
    /* 내부 노드: slot[i]가 유효한 자식 포인터인지 확인 */
    /* 잎 노드: slot[i]가 유효한 사용자 값 또는 NULL인지 확인 */

    /* 5. gap 배열 일관성 (arange_64만) */
    /* gap[i]가 실제 서브트리의 최대 빈 공간과 일치하는지 확인 */
    /* meta.gap이 실제 최대 gap 위치를 가리키는지 확인 */

    /* 6. 높이 일관성 */
    /* 모든 잎 노드가 동일한 깊이에 있는지 확인 (B-tree 속성) */

    /* 7. 노드 타입 일관성 */
    /* 트리 플래그(ALLOC_RANGE 등)에 맞는 노드 타입 사용 확인 */

    /* 8. 범위 연속성 */
    /* 형제 노드 간 범위가 겹치지 않고 빈틈 없이 연속인지 확인 */

    /* 검증 실패 시 WARN_ON + mt_dump() 자동 출력 */
    if (error)
        WARN_ON(1);
}

CONFIG_DEBUG_MAPLE_TREE 세부 옵션

# 커널 빌드 시 디버그 옵션 활성화
make menuconfig
# Kernel hacking → Memory Debugging → Debug maple tree

# 또는 .config에 직접 추가
echo 'CONFIG_DEBUG_MAPLE_TREE=y' >> .config
echo 'CONFIG_MAPLE_TREE_DEBUG=y' >> .config
make -j$(nproc)

# 런타임 진단: dmesg에서 maple_tree 관련 경고 확인
dmesg | grep -i 'maple\|mt_validate\|maple_tree'

# KASAN과 함께 사용하면 use-after-free 감지 강화
echo 'CONFIG_KASAN=y' >> .config
# RCU grace period 후 해제된 노드 접근 시 KASAN이 즉시 보고

Android에서의 Maple Tree

Android는 Linux 커널을 기반으로 하며, GKI(Generic Kernel Image) 5.15+ / 6.1+에서 Maple Tree를 사용합니다. 모바일 환경의 특수한 메모리 관리(Memory Management) 요구사항과 Maple Tree의 상호작용을 분석합니다.

Android 메모리 압박과 VMA

Android 앱의 전형적인 VMA 패턴

• 일반 앱: 300~800개 VMA
• 대형 앱 (Chrome, Game): 1,500~3,000개 VMA
• 시스템 서비스 (system_server): 2,000~5,000개 VMA

Android 특수 VMA:

• ashmem (Anonymous Shared Memory) → Maple Tree에서 범위 관리
• ION/DMA-BUF 맵핑 → GPU 메모리 공유용 VMA
• ART GC 힙 → 다수의 mmap/munmap 호출 발생
• Binder 맵핑 → 프로세스 간 통신용 고정 VMA

Android Low Memory Killer Daemon (lmkd) — VMA 순회

lmkd는 /proc/pid/maps를 읽어 프로세스의 메모리 사용량을 추정합니다. Linux 6.1+에서는 Maple Tree의 RCU 읽기 경로를 통해 mmap_lock 경합 없이 VMA 정보를 빠르게 순회할 수 있습니다.

메모리 압박이 심한 Android 환경에서 lmkd의 VMA 순회가 앱의 페이지 폴트 처리를 차단하지 않으며, 사용자 경험(janks) 개선에 직접적으로 기여합니다.

Android에서 Maple Tree의 이점

벤치마킹 방법론

Maple Tree의 삽입, 삭제, 검색 성능을 측정하는 방법과 실측 데이터를 제공합니다.

측정 방법

/* lib/test_maple_tree.c 기반 벤치마크 (커널 모듈) */
static void benchmark_maple_tree(void)
{
    struct maple_tree mt;
    ktime_t start, end;
    int i;

    mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE);

    /* === 삽입 벤치마크 === */
    start = ktime_get();
    for (i = 0; i < 100000; i++) {
        unsigned long s = i * 0x1000;
        unsigned long e = s + 0xFFF;
        mtree_store_range(&mt, s, e,
                          xa_mk_value(i), GFP_KERNEL);
    }
    end = ktime_get();
    pr_info("Insert 100K: %lld ns/op\n",
            ktime_to_ns(ktime_sub(end, start)) / 100000);

    /* === 검색 벤치마크 === */
    start = ktime_get();
    for (i = 0; i < 100000; i++) {
        unsigned long addr = i * 0x1000 + 0x500;
        mtree_load(&mt, addr);
    }
    end = ktime_get();
    pr_info("Lookup 100K: %lld ns/op\n",
            ktime_to_ns(ktime_sub(end, start)) / 100000);

    /* === gap 검색 벤치마크 === */
    start = ktime_get();
    for (i = 0; i < 10000; i++) {
        MA_STATE(mas, &mt, 0, 0);
        mas_empty_area(&mas, 0, ULONG_MAX, 0x2000);
    }
    end = ktime_get();
    pr_info("Gap search 10K: %lld ns/op\n",
            ktime_to_ns(ktime_sub(end, start)) / 10000);

    /* === 삭제 벤치마크 === */
    start = ktime_get();
    for (i = 0; i < 100000; i++) {
        mtree_erase(&mt, i * 0x1000);
    }
    end = ktime_get();
    pr_info("Delete 100K: %lld ns/op\n",
            ktime_to_ns(ktime_sub(end, start)) / 100000);

    mtree_destroy(&mt);
}

실측 성능 데이터

# 유저스페이스 벤치마크 (tools/testing/radix-tree/)
cd tools/testing/radix-tree/
make maple
./maple

# bpftrace로 실시간 레이턴시 히스토그램
bpftrace -e '
kprobe:mtree_store_range {
    @start[tid] = nsecs;
}
kretprobe:mtree_store_range /@start[tid]/ {
    @insert_ns = hist(nsecs - @start[tid]);
    delete(@start[tid]);
}

kprobe:mtree_load {
    @lstart[tid] = nsecs;
}
kretprobe:mtree_load /@lstart[tid]/ {
    @lookup_ns = hist(nsecs - @lstart[tid]);
    delete(@lstart[tid]);
}
' -d 10

# perf로 캐시 미스 비교
perf stat -e cache-misses,cache-references,instructions \
    -p $(pidof target_process) -- sleep 5

내부 재균형 알고리즘

Maple Tree의 재균형(rebalancing)은 B-tree의 전통적인 분할/병합에 기반하되, RCU 호환성과 캐시 효율을 위한 특수한 최적화를 포함합니다.

노드 분할 알고리즘 상세

/* 분할 알고리즘 핵심 — 간략화 */
static int mas_split(struct ma_state *mas,
                      struct maple_big_node *b_node)
{
    unsigned char split_at;
    struct maple_enode *left, *right;

    /* 분할 지점 결정 */
    split_at = b_node->b_end / 2;

    /* 실제로는 더 정교한 휴리스틱:
     * - gap이 큰 쪽을 더 많이 할당 (arange_64)
     * - NULL 슬롯 연속 구간은 한쪽으로 모음
     * - 최소 점유율(MAPLE_MIN_SLOTS) 보장 */
    split_at = mab_calc_split(mas, b_node, &mid_split);

    /* 새 노드 2개 할당 (사전 할당 풀에서) */
    left  = mas_new_ma_node(mas, b_node);
    right = mas_new_ma_node(mas, b_node);

    /* big_node의 [0, split_at]을 left로 복사 */
    mab_mas_cp(b_node, 0, split_at, left, true);

    /* big_node의 [split_at+1, b_end]를 right로 복사 */
    mab_mas_cp(b_node, split_at + 1, b_node->b_end, right, false);

    /* gap 배열 재계산 (arange_64만) */
    if (mt_is_alloc(mas->tree)) {
        mas_update_gap(mas, left);
        mas_update_gap(mas, right);
    }

    /* 부모에 중간 pivot과 두 자식 포인터 삽입 */
    mas_split_parent(mas, left, right,
                      b_node->pivot[split_at]);

    /* 구 노드 RCU 해제 */
    mas_free(mas, old_node);
    return 0;
}

노드 병합 알고리즘

/* 병합(coalesce) 트리거 조건 */
/*
 * 삭제 후 노드의 점유율이 낮아지면 인접 형제 노드와 병합:
 *
 * 조건: node.entries < MAPLE_MIN_SLOTS (약 3~4개)
 *
 * 병합 과정:
 * 1. 현재 노드와 이전/다음 형제 노드의 항목을 합침
 * 2. 합친 결과가 한 노드에 들어가면 → 단순 병합
 * 3. 합친 결과가 초과하면 → 재분배 (rebalance)
 * 4. 부모 노드에서 해당 pivot 제거 → 부모도 희소하면 연쇄 병합
 */

static void mas_coalesce(struct ma_state *mas)
{
    struct maple_enode *node = mas->node;
    struct maple_enode *sibling;
    unsigned char this_end = ma_data_end(node);

    /* 최소 점유율 이상이면 병합 불필요 */
    if (this_end >= MAPLE_MIN_SLOTS)
        return;

    /* 오른쪽 형제와 병합 시도 */
    sibling = mas_next_sibling(mas);
    if (sibling) {
        unsigned char sib_end = ma_data_end(sibling);

        if (this_end + sib_end + 1 <= MAPLE_RANGE64_SLOTS) {
            /* 한 노드에 합칠 수 있음 → 병합 */
            mas_merge_nodes(mas, node, sibling);
        } else {
            /* 초과 → 두 노드 간 재분배 */
            mas_rebalance(mas, node, sibling);
        }
    }

    /* 부모 노드의 점유율도 재검사 */
    mas_ascend(mas);
    mas_coalesce(mas);  /* 재귀적 검사 (실제론 루프) */
}

재균형 트리거 조건 요약

참고 자료

bpftrace 실습 예제

bpftrace를 활용하면 Maple Tree의 내부 동작을 실시간(Real-time)으로 관찰할 수 있습니다. VMA 관련 Maple Tree 연산을 추적하여 삽입/검색/gap 탐색의 빈도와 지연 시간을 측정하고, 트리 재균형 상황을 모니터링할 수 있습니다.

mas_store_gfp 추적: VMA 삽입 모니터링

mas_store_gfp()는 VMA 삽입/갱신 시 호출되는 핵심 함수입니다. mmap, brk, mprotect 등의 시스템 콜 경로에서 이 함수가 트리거됩니다.

# mas_store_gfp 호출 빈도를 프로세스별로 집계
bpftrace -e 'kprobe:mas_store_gfp { @store[comm] = count(); }'

# 출력 예시:
# @store[bash]: 12
# @store[gcc]: 847
# @store[ld]: 2341
# @store[python3]: 156

mas_find 추적: VMA 검색 패턴 분석

# mas_find 호출의 지연 시간 분포 (나노초 단위 히스토그램)
bpftrace -e '
kprobe:mas_find { @start[tid] = nsecs; }
kretprobe:mas_find /@start[tid]/ {
    @find_ns = hist(nsecs - @start[tid]);
    delete(@start[tid]);
}'

# 출력 예시:
# @find_ns:
# [64, 128)         1847 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@  |
# [128, 256)         423 |@@@@@@@@                               |
# [256, 512)          31 |                                       |
# [512, 1K)            2 |                                       |

대부분의 검색이 64~128ns 범위에서 완료되며, 이는 Maple Tree의 B-tree 구조 덕분에 2~3회의 노드 접근만으로 대상 VMA를 찾을 수 있기 때문입니다.

mas_empty_area 추적: Gap 검색 모니터링

# mmap 시 빈 공간(gap) 검색 빈도와 지연 시간
bpftrace -e '
kprobe:mas_empty_area { @start[tid] = nsecs; }
kretprobe:mas_empty_area /@start[tid]/ {
    @gap_ns = hist(nsecs - @start[tid]);
    @gap_count = count();
    delete(@start[tid]);
}'

# 출력 예시:
# @gap_count: 5823
# @gap_ns:
# [128, 256)        3241 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@  |
# [256, 512)        1892 |@@@@@@@@@@@@@@@@@@@@@@@                |
# [512, 1K)          584 |@@@@@@@                                |
# [1K, 2K)           106 |@                                      |

재균형 빈도 모니터링

# 노드 분할(split)과 병합(coalesce) 빈도 추적
bpftrace -e '
kprobe:mas_split { @split[comm] = count(); }
kprobe:mas_rebalance { @rebalance[comm] = count(); }
interval:s:10 { print(@split); print(@rebalance); clear(@split); clear(@rebalance); }'

# 10초 간격 출력 예시:
# @split[gcc]: 47
# @split[ld]: 128
# @rebalance[munmap]: 12

트리 깊이 관찰

# maple_tree의 깊이(ma_meta.depth) 분포 확인
# 커널 tracepoint가 있을 경우 활용, 또는 kprobe 인자 추적
bpftrace -e '
kprobe:mtree_insert_range {
    @tree_ops[comm] = count();
}
interval:s:5 { print(@tree_ops); clear(@tree_ops); }'

# 일반적인 데스크톱 워크로드에서 VMA Maple Tree의 깊이는 3~4입니다.
# 수만 개의 VMA를 가진 대규모 프로세스(예: JVM, Chrome)도 깊이 5를 넘기 어렵습니다.
# 이는 팬아웃 10~16의 B-tree 특성 때문입니다: log16(100000) ≈ 4.2

rbtree 대비 성능 비교

Linux 6.1에서 VMA 관리가 Red-Black Tree에서 Maple Tree로 전환된 핵심 이유는 성능입니다. 아래는 주요 연산별 비교와 실제 워크로드에서의 영향을 정리합니다.

연산별 벤치마크 비교

아래 수치는 10,000개의 VMA를 가진 프로세스에서 측정한 참고값입니다 (Intel Xeon Platinum 8380, DDR4-3200).

VMA 수에 따른 검색 성능 비교

위 차트에서 볼 수 있듯이, VMA 수가 증가할수록 두 자료구조의 성능 격차가 크게 벌어집니다. RB-Tree는 노드당 1개의 키만 저장하므로 트리 높이가 log₂(n)으로 증가하지만, Maple Tree는 팬아웃 10~16 덕분에 log₁₆(n) 수준의 낮은 높이를 유지합니다.

캐시 친화성이 핵심인 이유

현대 CPU에서 L1 캐시 미스 한 번의 비용은 ~4ns, L2 미스는 ~12ns, L3 미스는 ~40ns입니다. RB-Tree의 14단계 포인터 추적은 거의 매번 L1 캐시 미스를 유발하지만, Maple Tree의 3~4단계 노드 접근은 각 노드 내부에서 pivot 배열을 순차 스캔하므로 하드웨어 프리페처가 효과적으로 동작합니다.

실제 워크로드 영향

커널 소스 분석: mtree_insert() 삽입 경로

mtree_insert()와 mtree_insert_range()는 Maple Tree의 외부 삽입 API입니다. 내부적으로 mas_insert()를 거쳐 mas_wr_modify()에 도달하는 전체 호출 경로를 커널 소스 수준에서 추적합니다.

mtree_insert() 진입점

/* lib/maple_tree.c — mtree_insert() 전체 경로 */
int mtree_insert(struct maple_tree *mt, unsigned long index,
                  void *entry, gfp_t gfp)
{
    return mtree_insert_range(mt, index, index, entry, gfp);
}

int mtree_insert_range(struct maple_tree *mt,
                        unsigned long first, unsigned long last,
                        void *entry, gfp_t gfp)
{
    MA_STATE(mas, mt, first, last);
    int ret = 0;

retry:
    /* 1. 내장 스핀락 획득 */
    mas_lock(&mas);

    /* 2. 삽입 시도 — 이미 항목이 존재하면 -EEXIST */
    mas_insert(&mas, entry);
    if (mas_is_err(&mas))
        ret = xa_err(mas.node);

    /* 3. 잠금 해제 */
    mas_unlock(&mas);

    /* 4. 메모리 부족 시 재시도 (노드 사전 할당 후 다시 시도) */
    if (mas_nomem(&mas, gfp))
        goto retry;

    mas_destroy(&mas);
    return ret;
}

/* mas_insert: 기존 항목 존재 여부 확인 후 store */
static inline void mas_insert(struct ma_state *mas, void *entry)
{
    MA_WR_STATE(wr_mas, mas, entry);

    /* Walk: 대상 위치까지 트리를 내려감 */
    mas_wr_preallocate_one(&wr_mas);
    mas_wr_walk(&wr_mas);

    /* 기존 항목이 있으면 에러 (insert는 덮어쓰기 불가) */
    if (wr_mas.content) {
        mas_set_err(mas, -EEXIST);
        return;
    }

    /* 실제 삽입: mas_wr_modify()로 진행 */
    mas_wr_modify(&wr_mas);
}

mas_wr_modify() 분기 로직

/* lib/maple_tree.c — mas_wr_modify() 핵심 분기 */
static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
{
    struct ma_state *mas = wr_mas->mas;
    unsigned char new_end;

    /* Case 1: 단순 덮어쓰기 — 기존 슬롯의 값만 교체 */
    if (mas_wr_try_rebalance(wr_mas))
        return;

    /* Case 2: 확장/축소 필요 — 새 슬롯 수 계산 */
    new_end = mas_wr_new_end(wr_mas);

    /* Case 3: 빈 트리에 첫 항목 삽입 */
    if (!mas->index && mas->last == ULONG_MAX) {
        mas_new_root(mas, wr_mas->entry);
        return;
    }

    /* Case 4: 현재 노드에 여유 있음 — 슬롯 시프트 삽입 */
    if (new_end < mt_slot_count(mas->node)) {
        mas_wr_slot_store(wr_mas);
        return;
    }

    /* Case 5: 노드 가득 참 — big_node 경유 분할 */
    mas_wr_node_store(wr_mas, new_end);
    /* 내부적으로 mas_wr_bnode()→mas_commit_b_node()→mas_split() */
}

메모리 부족 재시도 패턴

/* mas_nomem(): 노드 할당 실패 시 재시도 로직 */
/*
 * 삽입/분할 중 mt_alloc_one()이 실패하면 mas에 에러가 설정됩니다.
 * mas_nomem()은 이를 감지하고 GFP 플래그로 재할당을 시도합니다.
 *
 * 핵심 흐름:
 * 1. mas_lock() — 잠금 획득
 * 2. mas_insert() — 삽입 시도 (노드 할당 필요 시 GFP_NOWAIT)
 * 3. mas_unlock() — 잠금 해제 (GFP_NOWAIT 실패해도 안전)
 * 4. mas_nomem(GFP_KERNEL) — 잠금 없이 슬립 가능한 할당
 *    → 노드를 사전 할당하여 mas->alloc에 저장
 * 5. goto retry → 다시 시도 (이번엔 사전 할당된 노드 사용)
 */

bool mas_nomem(struct ma_state *mas, gfp_t gfp)
{
    if (likely(!mas_is_err(mas)))
        return false;  /* 에러 없음 → 재시도 불필요 */

    if (unlikely(xa_err(mas->node) != -ENOMEM))
        return false;  /* 메모리 에러가 아님 */

    /* 상태 초기화 후 노드 사전 할당 */
    mas_reset(mas);
    if (mas_alloc_req(mas) > 0) {
        /* 필요한 노드 수만큼 미리 할당 (슬립 가능) */
        mas_node_count(mas, mas_alloc_req(mas));
    }
    return true;  /* 재시도 필요 */
}

커널 소스 분석: mas_walk() / mas_find() 상태 전이

ma_state는 Maple Tree 순회의 핵심 커서입니다. mas_walk()와 mas_find()가 내부 상태를 어떻게 전이하며 트리를 탐색하는지 상세히 분석합니다.

ma_state 필드별 역할

/* include/linux/maple_tree.h — ma_state 구조체 */
struct ma_state {
    struct maple_tree *tree;   /* 소속 트리 포인터 */
    unsigned long index;       /* 검색/삽입 시작 인덱스 */
    unsigned long last;        /* 검색/삽입 끝 인덱스 */
    struct maple_enode *node;  /* 현재 위치의 노드 포인터
                                  * MAS_START: 초기 상태
                                  * MAS_ROOT: 루트 진입
                                  * MAS_NONE: 순회 종료
                                  * 실제 노드: 내부/잎 노드 */
    unsigned long min;         /* 현재 노드의 관할 범위 하한 */
    unsigned long max;         /* 현재 노드의 관할 범위 상한 */
    struct maple_alloc *alloc; /* 사전 할당된 노드 목록 */
    unsigned char depth;       /* 현재 트리 깊이 (루트=0) */
    unsigned char offset;      /* 현재 노드 내 슬롯 오프셋 */
    unsigned char mas_flags;   /* 내부 상태 플래그 */
};

/* MA_STATE 매크로: 스택에 ma_state 할당 + 초기화 */
#define MA_STATE(name, mt, first, end) \
    struct ma_state name = {       \
        .tree = mt,                  \
        .index = first,              \
        .last = end,                 \
        .node = MAS_START,           \
        .min = 0,                     \
        .max = ULONG_MAX,            \
        .alloc = NULL,               \
        .depth = 0,                   \
    }

/* MA_WR_STATE: 쓰기 전용 확장 상태 */
#define MA_WR_STATE(name, ma_state, wr_entry) \
    struct ma_wr_state name = {               \
        .mas = ma_state,                        \
        .content = NULL,                       \
        .entry = wr_entry,                      \
    }

mas_find() 내부 동작

/* lib/maple_tree.c — mas_find() 핵심 로직 */
void *mas_find(struct ma_state *mas, unsigned long max)
{
    /* 범위 초과 검사 */
    if (unlikely(mas->index > max))
        return NULL;

    /* 초기 상태면 첫 walk 수행 */
    if (unlikely(mas_is_start(mas))) {
        mas_walk(mas);
        entry = mas_get_slot(mas, mas->offset);
        if (entry)
            return entry;  /* 첫 위치에 항목 존재 */
    }

    /* 현재 위치에 값이 없으면 → 다음 항목 검색 */
    /* 노드 내에서 offset++로 다음 슬롯 확인 */
    /* 노드 끝이면 mas_next_node()로 다음 잎 노드 이동 */
    return mas_next_slot(mas, max, false);
}

/* mas_next_slot: 현재 잎 노드 내에서 다음 non-NULL 슬롯 탐색 */
static inline void *mas_next_slot(struct ma_state *mas,
                                     unsigned long max, bool empty)
{
    void __rcu **slots = ma_slots(mas_mn(mas));
    unsigned long *pivots = ma_pivots(mas_mn(mas));
    unsigned char count = ma_data_end(mas->node);
    void *entry;

    /* 현재 노드 내에서 다음 슬롯 검색 */
    while (++mas->offset <= count) {
        /* min/max 범위 갱신 */
        mas->min = pivots[mas->offset - 1] + 1;
        if (mas->offset <= count)
            mas->max = pivots[mas->offset];

        /* max 초과 시 중단 */
        if (mas->min > max)
            return NULL;

        entry = rcu_dereference(slots[mas->offset]);
        if (entry || empty)
            return entry;
        /* NULL 슬롯은 건너뜀 (gap) */
    }

    /* 노드 끝 도달 → 다음 잎 노드로 이동 */
    return mas_next_node(mas, max);
}

커널 소스 분석: 노드 메모리 레이아웃

Maple Tree의 모든 노드 타입은 256바이트(B)로 통일되어 kmem_cache_alloc()의 슬랩(slab) 할당과 캐시 라인 정렬에 최적화되어 있습니다. 각 노드 타입의 물리적 메모리 배치를 바이트(Byte) 단위로 분석합니다.

maple_dense 잎 노드

/* include/linux/maple_tree.h — maple_dense 노드 */
/*
 * 밀집(dense) 잎 노드: pivot 없이 slot만 보유
 * 인덱스 0..63을 직접 인덱싱하는 배열
 *
 * 메모리 레이아웃:
 *   offset 0x00: parent (8B)
 *   offset 0x08: slot[64] (512B... 하지만 실제로는 노드 크기 256B 내)
 *
 * 실제 64비트 시스템에서는 MAPLE_NODE_SLOTS = 31 (256B 제약)
 * slot[i]는 인덱스 i에 직접 매핑 → pivot 스캔 불필요
 *
 * 사용 조건:
 * - 트리에 항목이 매우 적고 (< 31개)
 * - 인덱스가 0부터 연속적일 때
 * - 루트 근처의 shallow tree에서 자동 선택
 */
struct maple_node {
    union {
        struct {
            struct maple_pnode *parent;
            void __rcu *slot[MAPLE_NODE_SLOTS];
        };
        struct maple_range_64 mr64;
        struct maple_arange_64 ma64;
    };
};

커널 소스 분석: 노드 분할 연산

노드 분할은 Maple Tree에서 가장 복잡한 연산입니다. big_node를 사용한 지연 분할(deferred split) 패턴의 실제 커널 코드 흐름을 추적합니다.

분할 지점 결정: mab_calc_split()

/* lib/maple_tree.c — 분할 지점 계산 (간략화) */
static inline unsigned char mab_calc_split(
    struct ma_state *mas,
    struct maple_big_node *bn,
    unsigned char *mid_split)
{
    unsigned char b_end = bn->b_end;
    unsigned char split = b_end / 2;

    /* Allocation 모드 (arange_64): gap 균형 고려 */
    if (mt_is_alloc(mas->tree)) {
        /*
         * gap이 큰 쪽에 더 많은 슬롯을 배분합니다.
         * mmap 패턴에서 새 VMA는 보통 큰 gap 근처에 삽입되므로
         * 큰 gap 쪽 노드에 여유를 두면 다음 삽입 시
         * 분할 확률이 줄어듭니다.
         */
        unsigned long left_gap = 0, right_gap = 0;
        unsigned char i;

        for (i = 0; i <= split; i++)
            if (!bn->slot[i])
                left_gap += mab_gap_size(bn, i);
        for (i = split + 1; i <= b_end; i++)
            if (!bn->slot[i])
                right_gap += mab_gap_size(bn, i);

        /* gap 비율에 따라 분할 지점 조정 */
        if (right_gap > left_gap * 2)
            split = b_end / 3;  /* 우측에 더 많은 공간 할당 */
        else if (left_gap > right_gap * 2)
            split = b_end * 2 / 3;
    }

    /* 최소 점유율 보장 */
    if (split < MAPLE_MIN_SLOTS)
        split = MAPLE_MIN_SLOTS;
    if (b_end - split < MAPLE_MIN_SLOTS)
        split = b_end - MAPLE_MIN_SLOTS;

    return split;
}

커널 소스 분석: vma_mt_store() VMA 트리 연산

vma_mt_store()는 VMA 구조체를 Maple Tree에 저장하는 핵심 함수입니다. mmap(), munmap(), mremap(), vma_merge() 등 모든 VMA 조작의 최종 경로가 여기를 통과합니다.

vma_mt_store() 구현

/* mm/internal.h 또는 mm/mmap.c — vma_mt_store() */
static inline void vma_mt_store(struct mm_struct *mm,
                                    struct vm_area_struct *vma)
{
    /* Maple Tree에 [vm_start, vm_end-1] 범위로 VMA 저장 */
    mtree_store_range(&mm->mm_mt,
                       vma->vm_start,
                       vma->vm_end - 1,
                       vma,
                       GFP_KERNEL);
}

/* mtree_store_range → mas_store_gfp 호출 경로 */
int mtree_store_range(struct maple_tree *mt,
                       unsigned long first, unsigned long last,
                       void *entry, gfp_t gfp)
{
    MA_STATE(mas, mt, first, last);
    int ret = 0;

retry:
    mas_lock(&mas);
    mas_store_gfp(&mas, entry, GFP_NOWAIT | __GFP_NOWARN);
    mas_unlock(&mas);

    /* GFP_NOWAIT 실패 시 → 잠금 해제 후 슬립 가능 할당 */
    if (mas_nomem(&mas, gfp))
        goto retry;

    if (mas_is_err(&mas))
        ret = xa_err(mas.node);

    mas_destroy(&mas);
    return ret;
}

mmap() 시 VMA 삽입 전체 경로

/* mm/mmap.c — mmap_region() 내 Maple Tree 관련 호출 경로 (간략화) */
unsigned long mmap_region(struct file *file,
                           unsigned long addr, unsigned long len,
                           vm_flags_t vm_flags, unsigned long pgoff,
                           struct list_head *uf)
{
    struct mm_struct *mm = current->mm;
    struct vm_area_struct *vma, *prev, *merge;
    MA_STATE(mas, &mm->mm_mt, addr, addr + len - 1);

    /* 1단계: 빈 주소 공간 확보 (MAP_FIXED가 아닌 경우) */
    if (!(vm_flags & MAP_FIXED)) {
        /* arange_64의 gap 필드로 O(log n) 검색 */
        addr = mas_empty_area_rev(&mas, 0,
                                    mm->mmap_base, len);
    }

    /* 2단계: 이전 VMA와 병합 시도 */
    prev = mas_prev(&mas, 0);
    merge = vma_merge(mm, prev, addr, addr + len,
                       vm_flags, file, pgoff, ...);
    if (merge) {
        /* 병합 성공: vma_merge 내부에서 Maple Tree 갱신 완료 */
        vma = merge;
        goto out;
    }

    /* 3단계: 새 VMA 할당 및 초기화 */
    vma = vm_area_alloc(mm);
    vma->vm_start = addr;
    vma->vm_end   = addr + len;
    vma->vm_flags = vm_flags;
    vma->vm_file  = file;
    vma->vm_pgoff = pgoff;

    /* 4단계: Maple Tree에 VMA 삽입 */
    mas_set_range(&mas, vma->vm_start, vma->vm_end - 1);
    mas_store(&mas, vma);
    /*
     * mas_store()는 외부 잠금 모드 (MT_FLAGS_LOCK_EXTERN)
     * mmap_write_lock이 이미 보유 중이므로 내장 잠금 불필요
     *
     * 내부 동작:
     * a) mas_wr_walk(): 대상 잎 노드까지 walk
     * b) 기존 범위와 겹치면 기존 항목을 새 VMA로 교체
     * c) 노드 가득 차면 분할 (split)
     * d) arange_64: gap[] 배열 자동 갱신
     */

    mm->map_count++;

out:
    return addr;
}

munmap() 시 VMA 삭제 상세

/* mm/mmap.c — do_vmi_munmap() (Linux 6.4+ VMA iterator 사용) */
int do_vmi_munmap(struct vma_iterator *vmi,
                   struct mm_struct *mm,
                   unsigned long start, size_t len,
                   struct list_head *uf, bool unlock)
{
    struct vm_area_struct *vma;

    /* 1. 삭제 대상 VMA 검색 */
    vma = vma_find(vmi, start + len);
    if (!vma)
        return -ENOMEM;

    /* 2. VMA 부분 겹침 → 분할
     *    [====VMA====]
     *        [--삭제--]
     *    [=A=]        [=B=]  ← 분할 후 */
    if (vma->vm_start < start) {
        /* 전방 분할: [vm_start, start)를 남김 */
        __split_vma(vmi, vma, start, 0);
        /* Maple Tree: 기존 범위 pivot 축소 + 새 VMA 삽입 */
    }

    /* 3. Maple Tree에서 범위 제거
     *    mas_store(NULL)은 해당 범위를 gap으로 표시합니다.
     *    arange_64 노드: gap[] 배열이 자동으로 재계산됩니다. */
    vma_iter_set(vmi, start);
    vma_iter_store(vmi, NULL);
    /* NULL 저장 → 슬롯이 NULL이 됨 → gap 크기 증가 */

    /* 4. VMA 해제 및 페이지 테이블 정리 */
    unmap_region(mm, vma, ...);
    mm->map_count--;

    return 0;
}

커널 소스 분석: mas_for_each 반복 패턴

커널 코드에서 mas_for_each()를 사용하는 실제 패턴을 분석합니다. 특히 /proc/pid/maps 구현과 fork() 시 VMA 복사가 Maple Tree 반복자를 어떻게 활용하는지 추적합니다.

proc/pid/maps 순회

/* fs/proc/task_mmu.c — /proc/pid/maps 출력
 * 프로세스의 모든 VMA를 순서대로 출력하는 경로 */
static int show_map(struct seq_file *m, void *v)
{
    struct vm_area_struct *vma = v;

    /* vma는 m_start()/m_next()에서 Maple Tree 순회로 획득 */
    seq_printf(m, "%08lx-%08lx %c%c%c%c %08llx %s\n",
               vma->vm_start, vma->vm_end,
               vma->vm_flags & VM_READ  ? 'r' : '-',
               vma->vm_flags & VM_WRITE ? 'w' : '-',
               vma->vm_flags & VM_EXEC  ? 'x' : '-',
               vma->vm_flags & VM_MAYSHARE ? 's' : 'p',
               (unsigned long long)vma->vm_pgoff << PAGE_SHIFT,
               file_path(vma));
    return 0;
}

/* m_start/m_next: seq_file 콜백으로 VMA 순회
 * 내부적으로 vma_iterator (= ma_state wrapper) 사용 */
static void *m_start(struct seq_file *m, loff_t *ppos)
{
    struct proc_maps_private *priv = m->private;
    struct mm_struct *mm = priv->mm;
    struct vm_area_struct *vma;

    mmap_read_lock(mm);

    /* VMA iterator로 n번째 VMA까지 건너뛰기 */
    vma_iter_init(&priv->iter, mm, 0);
    for (loff_t n = *ppos; n > 0; n--) {
        vma = vma_next(&priv->iter);
        if (!vma) {
            mmap_read_unlock(mm);
            return NULL;
        }
    }

    return vma_next(&priv->iter);
}

static void *m_next(struct seq_file *m, void *v, loff_t *ppos)
{
    struct proc_maps_private *priv = m->private;
    (*ppos)++;
    return vma_next(&priv->iter);
    /* vma_next() → mas_find() → 다음 non-NULL 슬롯 반환 */
}

fork() 시 VMA 복사

/* kernel/fork.c → mm/mmap.c — dup_mmap()
 * fork() 시 부모 프로세스의 전체 VMA를 자식에게 복사 */
static inline int dup_mmap(struct mm_struct *mm,
                              struct mm_struct *oldmm)
{
    struct vm_area_struct *mpnt, *tmp;
    VMA_ITERATOR(old_vmi, oldmm, 0);
    int retval;

    /* 부모의 mmap_write_lock 보유 상태 */

    /* 부모의 모든 VMA를 순회하며 복사 */
    for_each_vma(old_vmi, mpnt) {
        /* 1. 새 VMA 할당 + 부모 VMA 내용 복사 */
        tmp = vm_area_dup(mpnt);
        if (!tmp)
            goto fail_nomem;

        /* 2. 자식의 Maple Tree에 삽입 */
        retval = vma_iter_bulk_store(&vmi, tmp);
        /*
         * vma_iter_bulk_store: mas_store()의 벌크 최적화 버전
         * - 연속 삽입이 예상되므로 노드 사전 할당
         * - 순차적 삽입 패턴에 최적화 (항상 다음 슬롯)
         * - 분할이 필요할 때만 실제 분할 수행
         */

        /* 3. COW 설정 (부모/자식 모두) */
        if (!(tmp->vm_flags & (VM_DONTCOPY | VM_IO))) {
            if (tmp->vm_flags & VM_SHARED)
                vma_set_anon_shared(tmp);
            else
                copy_page_range(tmp, mpnt);
        }

        mm->map_count++;
    }

    /* 벌크 삽입 완료 후 gap 일괄 갱신 */
    mas_destroy(&vmi.mas);
    return 0;
}

대량 순회 시 mas_pause() 패턴

/* mas_pause(): RCU 순회 중 preemption 허용
 * 대량의 VMA를 순회할 때 RCU 임계 구역을 너무 오래
 * 점유하면 다른 CPU의 grace period가 지연됩니다.
 * mas_pause()는 현재 위치를 저장한 채 RCU 구간을 해제합니다. */

void large_vma_scan(struct mm_struct *mm)
{
    MA_STATE(mas, &mm->mm_mt, 0, 0);
    struct vm_area_struct *vma;
    int batch = 0;

    rcu_read_lock();
    mas_for_each(&mas, vma, ULONG_MAX) {
        /* VMA 처리 로직 */
        process_vma(vma);

        if (++batch >= 256) {
            batch = 0;
            /* RCU 구간 해제 + 스케줄 포인트 */
            rcu_read_unlock();
            mas_pause(&mas);
            cond_resched();
            rcu_read_lock();
            /*
             * mas_pause()가 현재 위치를 기억하므로
             * 다음 mas_for_each 반복에서 중단 지점부터 재개합니다.
             * mas.node = MAS_PAUSE 상태로 설정되며,
             * 재개 시 mas_find()가 루트부터 다시 walk합니다.
             */
        }
    }
    rcu_read_unlock();
}

관련 문서

참고 자료

• include/linux/maple_tree.h — Maple Tree 핵심 자료구조 및 API 선언부입니다
• lib/maple_tree.c — Maple Tree 구현 전체 소스로, 삽입·삭제·분할·병합·walk 알고리즘이 포함되어 있습니다
• lib/test_maple_tree.c — 커널 내장 Maple Tree 단위 테스트 코드입니다
• Documentation/core-api/maple_tree.rst — 커널 공식 문서에서 제공하는 Maple Tree API 가이드입니다
• LWN: The Maple Tree, a modern data structure for a complex problem (2021) — Liam R. Howlett가 Maple Tree를 처음 제안한 배경과 설계 철학을 다룬 LWN 기사입니다
• LWN: The Maple Tree lands in 6.1 (2022) — Linux 6.1에 Maple Tree가 최종 병합된 과정을 설명하는 기사입니다
• LWN: Introducing maple trees (2020) — VMA 관리에 RB-Tree를 대체할 새로운 자료구조의 초기 논의를 정리한 기사입니다
• Linux Plumbers Conference 2022: Maple Tree — Liam R. Howlett가 발표한 Maple Tree 설계 및 성능 분석 세션입니다
• Oracle Blog: The Maple Tree — Oracle Linux 팀에서 작성한 Maple Tree 기술 블로그 포스트입니다
• LKML: Maple Tree 패치 시리즈 v14 — 메인라인에 병합된 최종 패치 시리즈로, 70개 이상의 패치로 구성되어 있습니다
• mm/mmap.c — VMA 관리에서 Maple Tree를 실제로 사용하는 mmap 구현부입니다
• LWN: Memory-management changes in 6.1 (2022) — Linux 6.1의 메모리 관리 변경 사항을 종합 정리한 기사로, RB-Tree에서 Maple Tree로의 마이그레이션이 포함되어 있습니다