Interval Tree

Linux 커널의 Interval Tree는 증강(Augmented) Red-Black Tree를 기반으로 구간(interval) 검색을 O(log n) 시간에 수행하는 자료구조입니다. VMA 검색, I/O 스케줄러의 요청 병합, 타이머 관리 등에서 핵심적으로 사용됩니다.

개요 (Overview)

Interval Tree는 다음 문제를 효율적으로 해결합니다:

• 단순 리스트 — O(n) 시간에 모든 구간을 순회해야 합니다.
• Interval Tree — O(log n + k) 시간 (k는 결과 개수)에 찾을 수 있습니다.

증강 Red-Black Tree 개념

일반 Red-Black Tree에 증강 필드를 추가합니다:

/* 일반 rb_node */
struct rb_node {
    unsigned long __rb_parent_color;
    struct rb_node *rb_right;
    struct rb_node *rb_left;
};

/* Interval tree 노드 */
struct interval_tree_node {
    struct rb_node rb;
    unsigned long start;     /* 구간 시작 */
    unsigned long last;      /* 구간 끝 (inclusive) */
    unsigned long __subtree_last;  /* 증강 필드: 서브트리 최대 last */
};

증강 필드의 의미:

• __subtree_last = max(node.last, left.__subtree_last, right.__subtree_last)
• 이 값을 통해 "이 서브트리에 질의 구간과 겹치는 노드가 있는가?"를 O(1)에 판단합니다.

Interval Tree API

기본 연산

/* include/linux/interval_tree_generic.h */

/* 매크로로 타입별 함수 생성 */
INTERVAL_TREE_DEFINE(struct interval_tree_node, rb,
                      unsigned long, __subtree_last,
                      START, LAST, , interval_tree);

/* 생성되는 함수들 */
void interval_tree_insert(struct interval_tree_node *node,
                              struct rb_root_cached *root);

void interval_tree_remove(struct interval_tree_node *node,
                              struct rb_root_cached *root);

/* 점 질의: 주어진 값과 겹치는 첫 번째 구간 */
struct interval_tree_node *
interval_tree_iter_first(struct rb_root_cached *root,
                           unsigned long start, unsigned long last);

/* 다음 겹치는 구간 */
struct interval_tree_node *
interval_tree_iter_next(struct interval_tree_node *node,
                          unsigned long start, unsigned long last);

사용 예제

/* 구간 관리 예제 */
struct rb_root_cached root = RB_ROOT_CACHED;

struct interval_tree_node *node1 = kmalloc(sizeof(*node1), GFP_KERNEL);
node1->start = 10;
node1->last = 20;
interval_tree_insert(node1, &root);

struct interval_tree_node *node2 = kmalloc(sizeof(*node2), GFP_KERNEL);
node2->start = 15;
node2->last = 25;
interval_tree_insert(node2, &root);

/* 18과 겹치는 모든 구간 찾기 */
struct interval_tree_node *iter;
for (iter = interval_tree_iter_first(&root, 18, 18);
     iter; iter = interval_tree_iter_next(iter, 18, 18)) {
    pr_info("Found interval [%lu, %lu]\n", iter->start, iter->last);
}
/* 출력:
 * Found interval [10, 20]
 * Found interval [15, 25]
 */

구간 검색 알고리즘

interval_tree_iter_first()의 내부 동작 원리:

VMA에서의 사용

가장 중요한 사용 사례는 find_vma()입니다:

/* include/linux/mm_types.h */
struct vm_area_struct {
    unsigned long vm_start;
    unsigned long vm_end;
    struct rb_node vm_rb;
    unsigned long rb_subtree_last;  /* 증강 필드 */
    /* ... */
};

struct mm_struct {
    struct rb_root mm_rb;
    /* ... */
};

/* mm/mmap.c */
struct vm_area_struct *find_vma(struct mm_struct *mm,
                                  unsigned long addr)
{
    struct rb_node *rb_node;
    struct vm_area_struct *vma;

    rb_node = mm->mm_rb.rb_node;

    while (rb_node) {
        vma = rb_entry(rb_node, struct vm_area_struct, vm_rb);

        if (vma->rb_subtree_last >= addr) {
            /* 이 서브트리에 답이 있을 수 있음 */
            if (addr < vma->vm_end)
                return vma;
            rb_node = rb_node->rb_left;
        } else {
            rb_node = rb_node->rb_right;
        }
    }

    return NULL;
}

I/O 스케줄러 활용

I/O 요청 병합에도 interval tree를 사용합니다:

/* block/blk-mq.c */
struct request {
    sector_t __sector;     /* 시작 섹터 */
    unsigned int __data_len;  /* 길이 */
    struct rb_node rb_node;
    /* ... */
};

/* 겹치는 I/O 요청 찾기 */
struct request *find_overlapping_request(sector_t sector,
                                           unsigned int len)
{
    return interval_tree_iter_first(&io_tree, sector, sector + len);
}

성능 특성

실제 활용 사례별 성능 비교

구현 세부사항

증강 콜백

Red-Black Tree는 증강 필드를 자동으로 유지하기 위한 콜백을 제공합니다:

/* lib/rbtree.c */
struct rb_augment_callbacks {
    void (*propagate)(struct rb_node *node, struct rb_node *stop);
    void (*copy)(struct rb_node *old, struct rb_node *new);
    void (*rotate)(struct rb_node *old, struct rb_node *new);
};

/* Interval tree의 augment 함수 */
static inline void interval_tree_augment_propagate(
    struct rb_node *node, struct rb_node *stop)
{
    while (node != stop) {
        struct interval_tree_node *itnode =
            rb_entry(node, struct interval_tree_node, rb);

        unsigned long max = itnode->last;

        if (itnode->rb.rb_left) {
            struct interval_tree_node *left =
                rb_entry(itnode->rb.rb_left, struct interval_tree_node, rb);
            if (left->__subtree_last > max)
                max = left->__subtree_last;
        }

        if (itnode->rb.rb_right) {
            struct interval_tree_node *right =
                rb_entry(itnode->rb.rb_right, struct interval_tree_node, rb);
            if (right->__subtree_last > max)
                max = right->__subtree_last;
        }

        if (itnode->__subtree_last == max)
            break;

        itnode->__subtree_last = max;
        node = rb_parent(&itnode->rb);
    }
}

모범 사례

언제 사용하는가:

• 주소 공간 검색 (VMA, page cache)
• I/O 스케줄러 (요청 병합)
• 타이머 관리 (겹치는 타이머 검색)
• 자원 예약 (메모리, CPU 시간)

대안:

• 구간이 극소수 → 선형 리스트
• 정확한 값 검색 → Hash Table
• 순서만 중요 → 일반 rbtree

Interval Tree 적용 체크리스트

Interval Tree는 겹침(overlap) 질의가 핵심일 때만 가치가 큽니다. 단순 exact-match나 작은 데이터셋에서는 일반 rbtree/list가 더 단순하고 빠를 수 있습니다.

augmented max 전파 메커니즘 심화

Interval Tree의 핵심은 __subtree_last 값이 삽입, 삭제, 회전 시마다 정확하게 전파(propagate)되는 메커니즘입니다. 이 섹션에서는 전파 과정을 단계별로 분석합니다.

전파 콜백 상세 분석

augment_callbacks 구조체는 세 가지 콜백을 정의합니다:

• propagate — 변경된 노드에서 루트 방향으로 올라가며 __subtree_last 재계산
• copy — 노드 교체 시 증강 필드를 복사
• rotate — 회전 연산 시 양쪽 노드의 증강 필드 재계산

/* include/linux/interval_tree_generic.h */
/* INTERVAL_TREE_DEFINE 매크로 내부에서 생성되는 propagate 콜백 */

/* RB_DECLARE_CALLBACKS_MAX 매크로로 propagate 구현 */
static inline void
ITPREFIX##_augment_propagate(struct rb_node *rb, struct rb_node *stop)
{
    while (rb != stop) {
        ITSTRUCT *node = rb_entry(rb, ITSTRUCT, ITRB);
        ITTYPE subtree_last = ITLAST(node);

        /* 왼쪽 자식의 __subtree_last와 비교 */
        if (node->ITRB.rb_left) {
            ITSTRUCT *left = rb_entry(node->ITRB.rb_left,
                                         ITSTRUCT, ITRB);
            if (left->ITSUBTREE > subtree_last)
                subtree_last = left->ITSUBTREE;
        }

        /* 오른쪽 자식의 __subtree_last와 비교 */
        if (node->ITRB.rb_right) {
            ITSTRUCT *right = rb_entry(node->ITRB.rb_right,
                                          ITSTRUCT, ITRB);
            if (right->ITSUBTREE > subtree_last)
                subtree_last = right->ITSUBTREE;
        }

        /* 조기 종료: 값이 변하지 않으면 상위 전파 불필요 */
        if (node->ITSUBTREE == subtree_last)
            break;

        node->ITSUBTREE = subtree_last;
        rb = rb_parent(&node->ITRB);
    }
}

회전 시 증강 필드 재계산

Red-Black Tree 회전은 부모-자식 관계를 변경하므로, 증강 필드도 재계산해야 합니다:

/* rotate 콜백: 회전 후 old 노드와 new 노드의 증강 필드 재계산 */
static inline void
ITPREFIX##_augment_rotate(struct rb_node *rb_old,
                            struct rb_node *rb_new)
{
    ITSTRUCT *old = rb_entry(rb_old, ITSTRUCT, ITRB);
    ITSTRUCT *new = rb_entry(rb_new, ITSTRUCT, ITRB);

    /* new가 old의 부모 위치를 대체함 */
    new->ITSUBTREE = old->ITSUBTREE;

    /* old는 이제 new의 자식 → old의 증강 필드 재계산 */
    ITTYPE subtree_last = ITLAST(old);
    if (old->ITRB.rb_left) {
        ITSTRUCT *left = rb_entry(old->ITRB.rb_left,
                                     ITSTRUCT, ITRB);
        if (left->ITSUBTREE > subtree_last)
            subtree_last = left->ITSUBTREE;
    }
    if (old->ITRB.rb_right) {
        ITSTRUCT *right = rb_entry(old->ITRB.rb_right,
                                      ITSTRUCT, ITRB);
        if (right->ITSUBTREE > subtree_last)
            subtree_last = right->ITSUBTREE;
    }
    old->ITSUBTREE = subtree_last;
}

가지치기(Pruning) 최적화

검색 시 __subtree_last를 활용한 가지치기는 Interval Tree의 핵심 성능 비결입니다:

구현 내부 구조 분석

Interval Tree의 내부 구현은 include/linux/interval_tree_generic.h에 정의된 INTERVAL_TREE_DEFINE 매크로를 중심으로 이루어집니다. 이 매크로가 타입별 함수를 자동 생성하는 메커니즘을 분석합니다.

interval_tree_node 메모리 레이아웃

INTERVAL_TREE_DEFINE 매크로 확장

INTERVAL_TREE_DEFINE 매크로는 6개의 핵심 함수를 자동 생성합니다:

/* include/linux/interval_tree_generic.h */
/*
 * INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE,
 *                      ITSTART, ITLAST, ITSTATIC, ITPREFIX)
 *
 * 매크로 인자 설명:
 *   ITSTRUCT  — 노드 구조체 타입 (struct interval_tree_node)
 *   ITRB      — rb_node 필드명 (rb)
 *   ITTYPE    — 구간 값 타입 (unsigned long)
 *   ITSUBTREE — 증강 필드명 (__subtree_last)
 *   ITSTART   — start 접근 매크로
 *   ITLAST    — last 접근 매크로
 *   ITSTATIC  — 함수 접두 지정자 (static 등)
 *   ITPREFIX  — 생성 함수 접두사 (interval_tree)
 */

/* 기본 Interval Tree 정의 (lib/interval_tree.c) */
#define START(node) ((node)->start)
#define LAST(node)  ((node)->last)

INTERVAL_TREE_DEFINE(struct interval_tree_node, rb,
    unsigned long, __subtree_last,
    START, LAST, static inline, interval_tree)

/* 매크로 확장 결과 (생성되는 함수들): */
/*
 * interval_tree_insert(node, root)
 * interval_tree_remove(node, root)
 * interval_tree_iter_first(root, start, last)
 * interval_tree_iter_next(node, start, last)
 * interval_tree_subtree_search(node, start, last)  -- 내부용
 * interval_tree_augment_propagate/copy/rotate       -- 콜백
 */

iter_first / iter_next 내부 동작

interval_tree_iter_first()는 트리에서 질의 구간과 겹치는 첫 번째 노드를 찾고, interval_tree_iter_next()는 그 다음 겹치는 노드를 순회합니다:

/* interval_tree_iter_first 의사코드 (매크로 확장) */
struct interval_tree_node *
interval_tree_iter_first(struct rb_root_cached *root,
                           unsigned long start, unsigned long last)
{
    struct interval_tree_node *node, *leftmost;
    struct rb_node *rb;

    if (!root->rb_root.rb_node)
        return NULL;

    /* 루트에서 시작하여 겹치는 노드 탐색 */
    rb = root->rb_root.rb_node;
    node = rb_entry(rb, struct interval_tree_node, rb);

    /* subtree_search: 증강 필드 기반 가지치기 탐색 */
    while (true) {
        /* 이 서브트리에 겹치는 구간이 없으면 종료 */
        if (node->__subtree_last < start)
            return NULL;

        /* 왼쪽 서브트리에 겹치는 구간이 있을 수 있음 */
        if (node->rb.rb_left) {
            struct interval_tree_node *left =
                rb_entry(node->rb.rb_left,
                         struct interval_tree_node, rb);
            if (left->__subtree_last >= start) {
                node = left;
                continue;
            }
        }

        /* 현재 노드가 겹치는지 확인 */
        if (node->start <= last)  /* 겹침 조건 */
            return node;

        /* 오른쪽 서브트리로 이동 */
        if (node->rb.rb_right) {
            node = rb_entry(node->rb.rb_right,
                             struct interval_tree_node, rb);
        } else {
            return NULL;
        }
    }
}

/* interval_tree_iter_next: in-order 순회로 다음 겹치는 노드 찾기 */
struct interval_tree_node *
interval_tree_iter_next(struct interval_tree_node *node,
                          unsigned long start, unsigned long last)
{
    struct rb_node *rb = node->rb.rb_right, *prev;

    while (true) {
        /* 오른쪽 서브트리에서 겹치는 노드 탐색 */
        if (rb) {
            node = rb_entry(rb, struct interval_tree_node, rb);
            if (node->__subtree_last >= start) {
                /* subtree_search로 재귀적 탐색 */
                return interval_tree_subtree_search(
                    node, start, last);
            }
        }

        /* in-order successor 방향으로 이동 */
        do {
            rb = rb_parent(&node->rb);
            if (!rb)
                return NULL;
            prev = &node->rb;
            node = rb_entry(rb, struct interval_tree_node, rb);
            rb = node->rb.rb_right;
        } while (prev == rb);

        /* start 기준 정렬이므로 query.last 초과 시 종료 */
        if (node->start > last)
            return NULL;

        /* 현재 노드가 겹치면 반환 */
        if (node->last >= start)
            return node;
    }
}

VMA 겹침 탐지 심화

Virtual Memory Area(VMA) 관리에서 Interval Tree는 주소 공간 겹침 탐지의 핵심 메커니즘입니다. 이 섹션에서는 find_vma_intersection()과 익명 VMA(anon_vma)의 interval tree 활용을 분석합니다.

find_vma_intersection() 코드 분석

/* include/linux/mm.h */
static inline struct vm_area_struct *
find_vma_intersection(struct mm_struct *mm,
                       unsigned long start_addr,
                       unsigned long end_addr)
{
    struct vm_area_struct *vma;

    /* find_vma: addr 이상의 vm_end를 가진 첫 VMA */
    vma = find_vma(mm, start_addr);

    /* 겹침 판정:
     * vma->vm_start < end_addr  (VMA 시작이 질의 끝 이전)
     * vma->vm_end > start_addr  (find_vma 보장)
     */
    if (vma && vma->vm_start < end_addr)
        return vma;

    return NULL;
}

anon_vma Interval Tree

익명 페이지(anonymous page)의 역방향 매핑(reverse mapping)에서도 Interval Tree가 핵심적으로 사용됩니다:

/* include/linux/rmap.h */
struct anon_vma_chain {
    struct vm_area_struct *vma;
    struct anon_vma *anon_vma;
    struct list_head same_vma;       /* VMA별 체인 */
    struct rb_node rb;               /* interval tree 노드 */
    unsigned long rb_subtree_last;   /* 증강 필드 */
};

/* mm/rmap.c - anon_vma 전용 Interval Tree 정의 */
INTERVAL_TREE_DEFINE(struct anon_vma_chain, rb,
    unsigned long, rb_subtree_last,
    avc_start_pgoff, avc_last_pgoff,
    static inline, anon_vma_interval_tree)

/* 페이지 회수 시 역방향 매핑 검색 */
static bool page_referenced_anon(
    struct folio *folio,
    struct mem_cgroup *memcg,
    unsigned long *vm_flags)
{
    struct anon_vma *anon_vma = folio->mapping;
    struct anon_vma_chain *avc;
    pgoff_t pgoff_start, pgoff_end;

    /* 이 페이지를 매핑하는 모든 VMA를 interval tree로 검색 */
    pgoff_start = folio->index;
    pgoff_end = pgoff_start + folio_nr_pages(folio) - 1;

    anon_vma_interval_tree_foreach(avc,
        &anon_vma->rb_root, pgoff_start, pgoff_end) {

        struct vm_area_struct *vma = avc->vma;
        /* vma에서 페이지 참조 여부 확인 */
        page_referenced_one(folio, vma, ...);
    }
}

Reverse Mapping 흐름

/* 페이지 회수 전체 흐름에서 interval tree 역할 */

/* 1. kswapd가 메모리 부족 감지 */
kswapd()
  → balance_pgdat()
    → shrink_node()
      → shrink_folio_list()
        → folio_referenced()
          → folio_referenced_anon()
            → anon_vma_interval_tree_foreach()  /* ← Interval Tree 검색 */
              → page_referenced_one()
                → ptep_clear_flush_young()  /* PTE accessed 비트 확인 */

/* 2. interval tree가 없다면?
 * → anon_vma에 연결된 모든 VMA를 선형 탐색
 * → fork 수가 많을수록 O(n) 비용 급증
 * → 페이지 회수 지연 → OOM 위험 증가
 */

DRM/GPU 드라이버 활용

DRM(Direct Rendering Manager) 서브시스템에서는 GPU 메모리 주소 공간 관리에 Interval Tree를 활용합니다. VRAM 할당, GEM 버퍼 객체 관리, TTM(Translation Table Manager) 등에서 핵심적으로 사용됩니다.

drm_mm 코드 분석

/* drivers/gpu/drm/drm_mm.c */

/* drm_mm 전용 interval tree 정의 */
#define START(node) ((node)->start)
#define LAST(node)  ((node)->start + (node)->size - 1)

INTERVAL_TREE_DEFINE(struct drm_mm_node, rb,
    u64, __subtree_last,
    START, LAST, static inline, drm_mm_interval_tree)

/* 할당된 노드 삽입 */
static void drm_mm_interval_tree_add_node(
    struct drm_mm_node *hole_node,
    struct drm_mm_node *node)
{
    struct drm_mm *mm = node->mm;

    node->__subtree_last = LAST(node);
    drm_mm_interval_tree_insert(node, &mm->interval_tree);
}

/* 범위 겹침 검사: 새 할당 전 충돌 확인 */
struct drm_mm_node *
__drm_mm_interval_first(const struct drm_mm *mm,
                         u64 start, u64 last)
{
    return drm_mm_interval_tree_iter_first(
        (struct rb_root_cached *)&mm->interval_tree,
        start, last);
}

/* GPU 드라이버에서의 사용 예 (i915) */
static int i915_gem_evict_something(
    struct i915_address_space *vm,
    u64 min_size, u64 alignment)
{
    struct drm_mm_node *node;

    /* interval tree로 요청 범위와 겹치는 모든 할당 찾기 */
    drm_mm_for_each_node_in_range(node, &vm->mm,
                                    target_start, target_end) {
        /* 겹치는 버퍼를 VRAM에서 시스템 메모리로 이동(evict) */
        i915_gem_object_unbind(node->bo, ...);
    }
}

GPU 메모리 eviction 흐름

GPU VRAM이 부족할 때, DRM 서브시스템은 interval tree를 활용하여 eviction 대상을 효율적으로 선택합니다:

/* drivers/gpu/drm/drm_mm.c */

/* 범위 내 모든 할당 노드 순회 매크로 */
#define drm_mm_for_each_node_in_range(node__, mm__, start__, end__)  \
    for (node__ = __drm_mm_interval_first((mm__), (start__),     \
                                            (end__) - 1);       \
         node__ && node__->start < (end__);                      \
         node__ = list_next_entry(node__, node_list))

/* eviction 예: VRAM 공간 확보 */
static int drm_mm_scan_add_block(
    struct drm_mm_scan *scan,
    struct drm_mm_node *node)
{
    struct drm_mm *mm = scan->mm;
    struct drm_mm_node *hole;
    u64 adj_start, adj_end;

    /* node를 evict한다고 가정하고 결과 hole 크기 계산 */
    adj_start = node->start;
    adj_end = node->start + node->size;

    /* 인접 hole과 병합 가능 여부 확인 */
    hole = list_prev_entry(node, node_list);
    if (hole->allocated == 0)
        adj_start = hole->start;

    hole = list_next_entry(node, node_list);
    if (hole->allocated == 0)
        adj_end = hole->start + hole->size;

    /* 충분한 공간이 확보되는지 확인 */
    if (adj_end - adj_start >= scan->size) {
        scan->hit_start = adj_start;
        scan->hit_end = adj_end;
        return true;
    }

    return false;
}

/* 전체 eviction 흐름 */
/*
 * 1. drm_mm_scan_init() — 스캔 초기화 (요청 크기, 정렬)
 * 2. 우선순위별로 evict 후보 순회:
 *    for_each_candidate:
 *      drm_mm_scan_add_block(scan, node)
 *      → interval tree에서 node 주변 hole 검사
 *      → 충분한 연속 공간 확보 시 true 반환
 * 3. drm_mm_scan_remove_block() — evict 대상 확정
 * 4. 실제 eviction 수행 (GPU 메모리 → 시스템 메모리)
 * 5. drm_mm_insert_node() — 새 할당 수행
 */

GEM/TTM 버퍼 객체 관리

io_uring 활용

io_uring은 고성능 비동기 I/O 인터페이스로, 등록된 버퍼(registered buffers)의 범위 관리에 interval tree 개념을 활용합니다.

고정 버퍼 관리

io_uring에서 IORING_REGISTER_BUFFERS로 등록된 버퍼는 커널이 미리 핀(pin)해두어 I/O 시마다 페이지 테이블 잠금과 GUP(get_user_pages)를 생략할 수 있습니다. 이때 버퍼 간 겹침 검사와 범위 관리가 필요합니다:

/* io_uring/rsrc.c */

/* 등록 버퍼 구조체 */
struct io_mapped_ubuf {
    u64    ubuf;       /* 사용자 공간 버퍼 주소 */
    u64    ubuf_end;   /* 버퍼 끝 주소 */
    unsigned int nr_bvecs;
    struct bio_vec bvec[];  /* 핀된 페이지 정보 */
};

/* 고정 버퍼 등록 흐름 */
static int io_sqe_buffers_register(
    struct io_ring_ctx *ctx,
    void __user *arg, unsigned int nr_args)
{
    struct io_mapped_ubuf *imu;
    int i;

    for (i = 0; i < nr_args; i++) {
        struct iovec iov;

        /* 사용자 공간 버퍼 정보 복사 */
        copy_from_user(&iov, arg + i, sizeof(iov));

        /* 버퍼 범위 설정 */
        imu->ubuf = (u64)iov.iov_base;
        imu->ubuf_end = imu->ubuf + iov.iov_len;

        /* 페이지 핀(pin): GUP으로 물리 페이지 고정 */
        io_buffer_account_pin(ctx, imu, ...);
    }
}

/* I/O 제출 시 등록 버퍼 검색 */
static struct io_mapped_ubuf *
io_buffer_select(struct io_ring_ctx *ctx,
                  u64 buf_addr, size_t len,
                  unsigned int buf_index)
{
    struct io_mapped_ubuf *imu;

    /* 인덱스로 직접 접근 (O(1)) */
    imu = ctx->user_bufs[buf_index];

    /* 범위 검증: 요청 범위가 등록 버퍼 내에 있는지 확인 */
    if (buf_addr < imu->ubuf ||
        buf_addr + len > imu->ubuf_end)
        return ERR_PTR(-EFAULT);

    return imu;
}

io_uring ↔ VMA Interval Tree 상호작용

/* io_uring이 VMA interval tree를 사용하는 경로 */

/* 1. 버퍼 등록 시 페이지 핀 */
io_sqe_buffers_register()
  → io_buffer_account_pin()
    → pin_user_pages()           /* GUP */
      → __get_user_pages()
        → find_vma(mm, start)    /* ← interval tree 검색! */
          → follow_page_mask()

/* 2. 직접 I/O 시 버퍼 매핑 확인 */
io_read() / io_write()
  → io_import_iovec()
    → io_buffer_select()        /* 등록 버퍼 인덱스 참조 */
  → kiocb_set_rw_flags()
  → call_read_iter() / call_write_iter()
    → direct_IO()
      → bio_iov_iter_get_pages()  /* 이미 핀된 페이지 사용 */

리소스 등록/해제 생명주기

io_uring의 리소스(버퍼, 파일) 등록과 해제 과정에서 VMA interval tree와의 상호작용을 단계별로 분석합니다:

/* io_uring 리소스 관리 생명주기 */

/* 1. 등록 (IORING_REGISTER_BUFFERS) */
io_uring_register()
  → io_sqe_buffers_register(ctx, arg, nr_args)
    → for each buffer:
        → io_buffer_validate(iov)      /* 크기/정렬 검증 */
        → io_sqe_buffer_register(ctx, iov, &imu)
          → pin_user_pages_fast(ubuf, nr_pages, FOLL_WRITE, pages)
            /* ↑ 내부에서 find_vma() → interval tree 검색 */
          → bio_vec 배열에 핀된 페이지 정보 저장
        → ctx->user_bufs[i] = imu

/* 2. I/O 수행 시 (zero-copy 경로) */
io_submit_sqe()
  → io_read() / io_write()
    → io_import_fixed(req, rw, iter, issue_flags)
      → imu = ctx->user_bufs[req->buf_index]  /* O(1) 인덱스 접근 */
      → iov_iter_bvec(iter, rw, imu->bvec, ...)
      /* ↑ VMA interval tree 검색 생략! (이미 핀됨) */

/* 3. 해제 (IORING_UNREGISTER_BUFFERS) */
io_uring_register()
  → io_sqe_buffers_unregister(ctx)
    → for each registered buffer:
        → io_buffer_unmap(ctx, &imu)
          → unpin_user_pages(pages, nr_pages)
          → kfree(imu)

io_uring 버퍼 등록 성능 비교

KVM 메모리 슬롯 관리

KVM(Kernel-based Virtual Machine)에서는 게스트 물리 주소(GPA)와 호스트 가상 주소(HVA) 간의 매핑을 관리하기 위해 interval tree 기반의 메모리 슬롯 구조를 사용합니다.

KVM 메모리 슬롯 코드 분석

/* include/linux/kvm_host.h */
struct kvm_memory_slot {
    gfn_t base_gfn;          /* Guest Frame Number 시작 */
    unsigned long npages;     /* 페이지 수 */
    unsigned long *dirty_bitmap;
    unsigned long userspace_addr;  /* HVA */
    u32 flags;
    short id;

    /* GPA 기반 interval tree 노드 */
    struct {
        struct rb_node gfn_node;
        gfn_t gfn_subtree_last;   /* 증강 필드 */
    } gfn_node[2];  /* [0]: active, [1]: inactive */

    /* HVA 기반 interval tree 노드 */
    struct {
        struct rb_node hva_node;
        unsigned long hva_subtree_last;
    } hva_node[2];
};

/* virt/kvm/kvm_main.c */
/* GPA → 메모리 슬롯 검색 */
static inline struct kvm_memory_slot *
search_memslots(struct kvm_memslots *slots, gfn_t gfn)
{
    struct rb_node *node;

    /* gfn_tree에서 interval tree 검색 */
    node = slots->gfn_tree.rb_node;
    while (node) {
        struct kvm_memory_slot *slot;

        slot = container_of(node, struct kvm_memory_slot,
                              gfn_node[slots->node_idx].gfn_node);

        if (gfn < slot->base_gfn)
            node = node->rb_left;
        else if (gfn >= slot->base_gfn + slot->npages)
            node = node->rb_right;
        else
            return slot;  /* 찾음! */
    }
    return NULL;
}

/* HVA 변경 통지 (mmu_notifier) 시 HVA interval tree 활용 */
static int kvm_mmu_notifier_invalidate_range_start(
    struct mmu_notifier *mn,
    const struct mmu_notifier_range *range)
{
    struct kvm *kvm = container_of(mn, struct kvm, mmu_notifier);
    struct kvm_memory_slot *slot;

    /* HVA 범위와 겹치는 모든 메모리 슬롯 찾기 */
    kvm_for_each_memslot_in_hva_range(kvm,
        range->start, range->end, slot) {
        /* 해당 슬롯의 SPT(Shadow Page Table) 무효화 */
        kvm_mmu_invalidate_range(kvm, slot,
            range->start, range->end);
    }
}

메모리 슬롯 생명주기

KVM 메모리 슬롯의 생성부터 삭제까지 interval tree와의 상호작용을 분석합니다:

/* virt/kvm/kvm_main.c */

/* 메모리 슬롯 추가/변경 */
static int kvm_set_memslot(
    struct kvm *kvm,
    struct kvm_memory_slot *new,
    enum kvm_mr_change change)
{
    struct kvm_memslots *slots;

    /* 1. 슬롯 충돌 검사 (interval tree 기반) */
    if (change == KVM_MR_CREATE) {
        struct kvm_memory_slot *existing;

        /* GPA 범위가 기존 슬롯과 겹치는지 확인 */
        kvm_for_each_memslot_in_gfn_range(&iter,
            slots, new->base_gfn,
            new->base_gfn + new->npages) {
            existing = iter.slot;
            if (existing->id != new->id)
                return -EEXIST;  /* 충돌! */
        }
    }

    /* 2. inactive 슬롯에 변경 적용 */
    kvm_swap_active_memslots(kvm, ...);

    /* 3. interval tree에서 이전 슬롯 제거 */
    if (change == KVM_MR_DELETE || change == KVM_MR_MOVE)
        kvm_erase_gfn_node(slots, old);

    /* 4. interval tree에 새 슬롯 삽입 */
    if (change != KVM_MR_DELETE)
        kvm_insert_gfn_node(slots, new);

    /* 5. 활성 슬롯 전환 (RCU 유사 메커니즘) */
    kvm_swap_active_memslots(kvm, ...);

    return 0;
}

KVM에서 interval tree 성능 영향

ftrace/perf 디버깅 실습

Interval Tree 관련 커널 동작을 실시간으로 추적하고 성능을 측정하는 방법을 다룹니다.

ftrace로 interval_tree 함수 추적

# interval_tree 관련 함수 목록 확인
cat /sys/kernel/debug/tracing/available_filter_functions | grep interval_tree

# function tracer 설정
echo 0 > /sys/kernel/debug/tracing/tracing_on
echo function > /sys/kernel/debug/tracing/current_tracer

# interval_tree 함수들만 필터링
echo 'interval_tree_*' > /sys/kernel/debug/tracing/set_ftrace_filter

# function graph 모드로 호출 관계까지 확인
echo function_graph > /sys/kernel/debug/tracing/current_tracer
echo 'interval_tree_insert interval_tree_remove' \
  > /sys/kernel/debug/tracing/set_graph_function

# 추적 시작
echo 1 > /sys/kernel/debug/tracing/tracing_on

# ... 워크로드 실행 (mmap/munmap 호출 등) ...

# 결과 확인
cat /sys/kernel/debug/tracing/trace

# 출력 예시:
#  2)               |  interval_tree_insert() {
#  2)   0.450 us    |    rb_insert_augmented_cached();
#  2)   1.230 us    |  }
#  1)   0.380 us    |  interval_tree_iter_first();
#  1)   0.210 us    |  interval_tree_iter_next();

bpftrace로 VMA interval tree 관찰

#!/usr/bin/env bpftrace
/* vma_interval_tree_operations.bt
 * VMA interval tree 삽입/삭제 추적
 */

/* find_vma 호출 빈도 및 지연 측정 */
kprobe:find_vma
{
    @start[tid] = nsecs;
    @find_vma_count = count();
}

kretprobe:find_vma
/@start[tid]/
{
    $duration = nsecs - @start[tid];
    @find_vma_latency_ns = hist($duration);
    delete(@start[tid]);
}

/* VMA 삽입/삭제 시 프로세스 정보 */
kprobe:vma_interval_tree_insert
{
    printf("INSERT vma pid=%d comm=%s\n", pid, comm);
}

kprobe:vma_interval_tree_remove
{
    printf("REMOVE vma pid=%d comm=%s\n", pid, comm);
}

/* 10초 후 통계 출력 */
interval:s:10
{
    printf("\n--- find_vma 지연 분포 (ns) ---\n");
    print(@find_vma_latency_ns);
    printf("총 호출 횟수: ");
    print(@find_vma_count);
}

perf를 이용한 성능 측정

# perf probe로 interval_tree_iter_first에 동적 트레이스포인트 추가
perf probe -a 'interval_tree_iter_first root start last'
perf probe -a 'interval_tree_iter_first%return $retval'

# 10초간 샘플링
perf record -e probe:interval_tree_iter_first \
           -e probe:interval_tree_iter_first__return \
           -ag -- sleep 10

# 결과 분석
perf report --stdio

# perf stat으로 간단한 통계
perf stat -e cache-misses,cache-references,instructions \
         -e 'probe:interval_tree_iter_first' \
         -- stress-ng --vm 4 --vm-bytes 1G --timeout 10s

# 출력 예시:
#  Performance counter stats:
#    12,345    cache-misses     # 2.3% of all cache refs
#   536,890    cache-references
# 8,234,567    instructions
#     4,567    probe:interval_tree_iter_first

# 프로브 정리
perf probe -d 'interval_tree_iter_first*'

성능 분석과 최적화

Interval Tree의 이론적 복잡도와 실제 성능 특성을 심화 분석합니다.

복잡도 분해

O(log n + k) 복잡도는 두 단계로 분해됩니다:

자료구조 비교 분석

캐시 동작 분석

Interval Tree의 실제 성능은 캐시 효율에 크게 의존합니다:

/* 캐시 동작 분석 */

/* 1. interval_tree_node는 48바이트 → L1 캐시라인(64B)에 1개 적합 */
/*    트리 탐색 시 매 레벨마다 캐시라인 1개 로드 */

/* 2. 깊이 h = O(log n)이므로:
 *    n =    1,000 → h ≈ 10 → 캐시라인 10개 (640B)
 *    n =  100,000 → h ≈ 17 → 캐시라인 17개 (1,088B)
 *    n = 1,000,000 → h ≈ 20 → 캐시라인 20개 (1,280B)
 *    → L1 캐시(32-48KB)에 충분히 들어감
 */

/* 3. 자주 접근되는 루트 근처 노드는 캐시에 남아있을 확률 높음 */
/*    → 실제 캐시 미스는 하위 레벨에서만 발생 */

/* 4. prefetch 최적화 가능 */
static inline void interval_tree_search_prefetch(
    struct rb_node *node)
{
    /* 다음 레벨 노드를 미리 캐시에 로드 */
    if (node->rb_left)
        prefetch(node->rb_left);
    if (node->rb_right)
        prefetch(node->rb_right);
}

벤치마크 방법론

# perf stat으로 interval tree 성능 측정

# 1. VMA 집약적 워크로드 실행 + 캐시 통계 수집
perf stat -e cycles,instructions,cache-misses,cache-references \
         -e LLC-load-misses,LLC-store-misses \
         -e dTLB-load-misses \
         -- stress-ng --vm 8 --vm-bytes 2G --vm-method all --timeout 30s

# 2. find_vma 핫스팟 분석
perf record -g -e cycles -- stress-ng --vm 4 --timeout 10s
perf report --stdio --symbol-filter=find_vma

# 3. 커널 모듈 벤치마크 (직접 측정)
# → 아래 "커스텀 Interval Tree 구현" 섹션의 벤치마크 모듈 참조

# 출력 예시 (100K VMA, 1M 검색):
# interval_tree_iter_first: avg 780ns, p99 2.1us
# 선형 검색:                 avg 48us,  p99 95us
# 비율:                      ~61x 차이

커스텀 Interval Tree 구현

INTERVAL_TREE_DEFINE 매크로를 사용하여 커널 모듈에서 자체 Interval Tree를 구현하는 방법을 단계별로 안내합니다.

Step 1: 노드 구조체 정의

/* my_interval_tree.h */
#include <linux/interval_tree_generic.h>
#include <linux/rbtree_augmented.h>

/* 커스텀 구간 노드 */
struct my_interval_node {
    struct rb_node rb;           /* rbtree 노드 */
    unsigned long start;         /* 구간 시작 */
    unsigned long last;          /* 구간 끝 (inclusive) */
    unsigned long __subtree_last; /* 증강 필드 */

    /* 사용자 데이터 */
    void *data;
    u32 flags;
};

Step 2: 매크로로 함수 생성

/* my_interval_tree.c */
#include "my_interval_tree.h"

/* start/last 접근 매크로 */
#define MY_START(node) ((node)->start)
#define MY_LAST(node)  ((node)->last)

/* Interval Tree 함수 생성
 * 생성되는 함수:
 *   my_itree_insert(node, root)
 *   my_itree_remove(node, root)
 *   my_itree_iter_first(root, start, last)
 *   my_itree_iter_next(node, start, last)
 */
INTERVAL_TREE_DEFINE(struct my_interval_node, rb,
    unsigned long, __subtree_last,
    MY_START, MY_LAST,
    static, my_itree)

Step 3: 커널 모듈 구현

/* my_interval_module.c — 완전한 커널 모듈 예제 */
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/ktime.h>
#include "my_interval_tree.h"

static struct rb_root_cached my_tree = RB_ROOT_CACHED;

/* 구간 노드 생성 및 삽입 */
static struct my_interval_node *
my_interval_add(unsigned long start, unsigned long last,
                 void *data)
{
    struct my_interval_node *node;

    node = kmalloc(sizeof(*node), GFP_KERNEL);
    if (!node)
        return ERR_PTR(-ENOMEM);

    node->start = start;
    node->last = last;
    node->data = data;
    node->flags = 0;

    my_itree_insert(node, &my_tree);

    pr_info("inserted [%lu, %lu]\n", start, last);
    return node;
}

/* 겹치는 구간 검색 */
static int my_interval_query(unsigned long start,
                              unsigned long last)
{
    struct my_interval_node *node;
    int count = 0;

    for (node = my_itree_iter_first(&my_tree, start, last);
         node;
         node = my_itree_iter_next(node, start, last)) {

        pr_info("  overlap: [%lu, %lu] data=%p\n",
                node->start, node->last, node->data);
        count++;
    }

    pr_info("query [%lu, %lu]: %d overlaps found\n",
            start, last, count);
    return count;
}

/* 벤치마크: 삽입 + 검색 성능 측정 */
static void my_interval_benchmark(int n)
{
    struct my_interval_node **nodes;
    ktime_t start, end;
    s64 insert_ns, search_ns;
    int i;

    nodes = kmalloc_array(n, sizeof(*nodes), GFP_KERNEL);
    if (!nodes)
        return;

    /* 삽입 벤치마크 */
    start = ktime_get();
    for (i = 0; i < n; i++) {
        nodes[i] = my_interval_add(
            i * 100,          /* start */
            i * 100 + 50,     /* last */
            NULL);
    }
    end = ktime_get();
    insert_ns = ktime_to_ns(ktime_sub(end, start));

    /* 검색 벤치마크 */
    start = ktime_get();
    for (i = 0; i < n; i++) {
        my_itree_iter_first(&my_tree,
            i * 100 + 25, i * 100 + 25);
    }
    end = ktime_get();
    search_ns = ktime_to_ns(ktime_sub(end, start));

    pr_info("Benchmark (n=%d):\n", n);
    pr_info("  Insert: %lld ns total, %lld ns/op\n",
            insert_ns, insert_ns / n);
    pr_info("  Search: %lld ns total, %lld ns/op\n",
            search_ns, search_ns / n);

    /* 정리 */
    for (i = 0; i < n; i++) {
        my_itree_remove(nodes[i], &my_tree);
        kfree(nodes[i]);
    }
    kfree(nodes);
}

static int __init my_interval_init(void)
{
    pr_info("my_interval_tree module loaded\n");

    /* 테스트 */
    my_interval_add(10, 20, NULL);
    my_interval_add(15, 25, NULL);
    my_interval_add(30, 40, NULL);

    my_interval_query(18, 18);  /* [10,20], [15,25] 찾음 */
    my_interval_query(35, 35);  /* [30,40] 찾음 */

    /* 벤치마크: 10K 노드 */
    my_interval_benchmark(10000);

    return 0;
}

static void __exit my_interval_exit(void)
{
    pr_info("my_interval_tree module unloaded\n");
}

module_init(my_interval_init);
module_exit(my_interval_exit);
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("Custom Interval Tree Example");

Step 4: 검증 및 테스트

/* 커스텀 interval tree 단위 테스트 */
static void test_basic_operations(void)
{
    struct rb_root_cached root = RB_ROOT_CACHED;
    struct my_interval_node *n1, *n2, *n3, *found;

    pr_info("=== Basic Operations Test ===\n");

    /* 삽입 테스트 */
    n1 = my_interval_add(10, 20, NULL);
    n2 = my_interval_add(15, 25, NULL);
    n3 = my_interval_add(30, 40, NULL);

    /* 점 질의 테스트 */
    found = my_itree_iter_first(&root, 12, 12);
    BUG_ON(!found);  /* [10,20] 찾아야 함 */
    BUG_ON(found->start != 10);

    /* 겹침 없는 질의 */
    found = my_itree_iter_first(&root, 26, 29);
    BUG_ON(found != NULL);  /* 결과 없어야 함 */

    /* 다중 결과 질의 */
    int count = 0;
    for (found = my_itree_iter_first(&root, 18, 18);
         found;
         found = my_itree_iter_next(found, 18, 18))
        count++;
    BUG_ON(count != 2);  /* [10,20]과 [15,25] 두 개 */

    /* 삭제 테스트 */
    my_itree_remove(n2, &root);
    found = my_itree_iter_first(&root, 22, 22);
    BUG_ON(found != NULL);  /* [15,25] 삭제되었으므로 */

    /* 경계값 테스트 */
    found = my_itree_iter_first(&root, 20, 20);
    BUG_ON(!found);  /* [10,20] inclusive이므로 겹침 */

    found = my_itree_iter_first(&root, 10, 10);
    BUG_ON(!found);  /* 시작점도 inclusive */

    /* 정리 */
    my_itree_remove(n1, &root);
    my_itree_remove(n3, &root);
    kfree(n1); kfree(n2); kfree(n3);

    pr_info("=== All tests passed ===\n");
}

/* 스트레스 테스트: 대량 삽입/삭제/검색 */
static void test_stress(int n)
{
    struct rb_root_cached root = RB_ROOT_CACHED;
    struct my_interval_node **nodes;
    int i, total_found = 0;

    nodes = kvmalloc_array(n, sizeof(*nodes), GFP_KERNEL);
    if (!nodes) return;

    /* 겹치는 구간 대량 삽입 */
    for (i = 0; i < n; i++) {
        nodes[i] = kmalloc(sizeof(*nodes[i]), GFP_KERNEL);
        nodes[i]->start = i * 10;
        nodes[i]->last = i * 10 + 50;  /* 겹침 발생 */
        my_itree_insert(nodes[i], &root);
    }

    /* 범위 검색 스트레스 */
    for (i = 0; i < n; i++) {
        struct my_interval_node *it;
        for (it = my_itree_iter_first(&root, i*10+5, i*10+5);
             it;
             it = my_itree_iter_next(it, i*10+5, i*10+5))
            total_found++;
    }

    pr_info("stress test: %d nodes, %d total overlaps found\n",
            n, total_found);

    /* 정리 */
    for (i = 0; i < n; i++) {
        my_itree_remove(nodes[i], &root);
        kfree(nodes[i]);
    }
    kvfree(nodes);
}

Makefile

# Makefile
obj-m += my_interval_module.o

KDIR ?= /lib/modules/$(shell uname -r)/build

all:
	make -C $(KDIR) M=$(PWD) modules

clean:
	make -C $(KDIR) M=$(PWD) clean

# 사용법:
# make
# sudo insmod my_interval_module.ko
# dmesg | tail -20
# sudo rmmod my_interval_module

커스텀 구현 시 흔한 실수

Interval Tree 연산 상태 머신

Interval Tree의 삽입, 검색, 삭제 연산을 상태 머신 관점에서 분석합니다. 특히 동시 접근 패턴과 오류 처리를 중점적으로 다룹니다.

오류 처리 패턴

/* Interval Tree 사용 시 일반적인 오류 처리 패턴 */

/* 1. 메모리 할당 실패 */
struct my_interval_node *node;
node = kmalloc(sizeof(*node), GFP_KERNEL);
if (!node)
    return -ENOMEM;
/* 실패 시 rollback 필요 없음 (삽입 전이므로) */

/* 2. 중복 삽입 방지 */
static int safe_interval_insert(
    struct rb_root_cached *root,
    struct my_interval_node *new_node)
{
    struct my_interval_node *existing;

    /* 정확히 같은 구간이 이미 있는지 확인 */
    existing = my_itree_iter_first(root,
        new_node->start, new_node->last);

    while (existing) {
        if (existing->start == new_node->start &&
            existing->last == new_node->last) {
            pr_warn("duplicate interval [%lu, %lu]\n",
                    new_node->start, new_node->last);
            return -EEXIST;
        }
        existing = my_itree_iter_next(existing,
            new_node->start, new_node->last);
    }

    my_itree_insert(new_node, root);
    return 0;
}

/* 3. 안전한 삭제 (이중 삭제 방지) */
static void safe_interval_remove(
    struct rb_root_cached *root,
    struct my_interval_node *node)
{
    /* RB_EMPTY_NODE 확인으로 이중 삭제 방지 */
    if (RB_EMPTY_NODE(&node->rb)) {
        pr_warn("node already removed\n");
        return;
    }

    my_itree_remove(node, root);
    RB_CLEAR_NODE(&node->rb);  /* 빈 노드로 표시 */
}

RCU 기반 동시 접근 패턴

/* RCU를 활용한 읽기-쓰기 동시성 패턴 */

struct my_interval_tree {
    struct rb_root_cached root;
    struct rw_semaphore rwsem;  /* 쓰기 보호 */
};

/* 읽기 경로: RCU 보호 (빠른 경로) */
static struct my_interval_node *
my_interval_search_rcu(struct my_interval_tree *tree,
                        unsigned long point)
{
    struct my_interval_node *node;

    rcu_read_lock();
    node = my_itree_iter_first(&tree->root, point, point);
    /* 주의: rcu_read_unlock() 후 node 사용 불가
     * → 필요한 데이터를 미리 복사하거나
     * → 참조 카운트 증가 필요 */
    rcu_read_unlock();

    return node;
}

/* 쓰기 경로: rwsem 보호 (느린 경로) */
static int my_interval_insert_locked(
    struct my_interval_tree *tree,
    struct my_interval_node *node)
{
    down_write(&tree->rwsem);
    my_itree_insert(node, &tree->root);
    up_write(&tree->rwsem);

    /* RCU grace period 대기 (이전 읽기 완료 보장) */
    synchronize_rcu();

    return 0;
}

lockdep 활용 디버깅

Interval Tree 동시성 문제를 lockdep으로 검증하는 방법입니다:

/* lockdep 어노테이션 예제 */
struct my_interval_tree {
    struct rb_root_cached root;
    struct rw_semaphore rwsem;
#ifdef CONFIG_DEBUG_LOCK_ALLOC
    struct lockdep_map dep_map;
#endif
};

/* 검색 시 읽기 잠금 검증 */
static struct my_interval_node *
my_interval_search_safe(struct my_interval_tree *tree,
                         unsigned long start,
                         unsigned long last)
{
    /* lockdep: rwsem을 읽기 잠금했는지 검증 */
    lockdep_assert_held_read(&tree->rwsem);

    return my_itree_iter_first(&tree->root, start, last);
}

/* 삽입 시 쓰기 잠금 검증 */
static void my_interval_insert_safe(
    struct my_interval_tree *tree,
    struct my_interval_node *node)
{
    /* lockdep: rwsem을 쓰기 잠금했는지 검증 */
    lockdep_assert_held_write(&tree->rwsem);

    my_itree_insert(node, &tree->root);
}

상태 머신 요약

관련 문서

• Red-Black Tree — 기반 자료구조
• VMA / mmap — VMA 관리
• 블록 I/O — I/O 스케줄러
• 메모리 관리 — 주소 공간