plist (Priority-Sorted List)

리눅스 커널의 우선순위 정렬 이중 연결 리스트(Priority-Sorted Linked List)인 plist를 심층 분석합니다. include/linux/plist.h와 lib/plist.c에 정의된 이 자료구조는 일반 list_head와 달리 두 개의 리스트(prio_list와 node_list)를 결합하여 우선순위 기반 삽입을 O(K) (K = 고유 우선순위 수)에 수행합니다. RT-Mutex(Real-Time Mutex) 대기자 큐, PM QoS(Power Management Quality of Service) 레이턴시(Latency) 제약, Futex PI(Priority Inheritance) 등 커널의 핵심 실시간 서브시스템에서 활용됩니다.

개요: list_head와의 차이

커널의 표준 struct list_head는 삽입/삭제가 O(1)이지만, 정렬 상태를 유지하지 않습니다. 우선순위 기반 대기열이 필요한 서브시스템에서 list_head를 사용하면, 삽입 시마다 올바른 위치를 찾기 위해 전체 리스트를 순회해야 합니다. 이는 O(N) 복잡도를 가집니다.

plist는 이 문제를 두 개의 리스트를 결합하는 방식으로 해결합니다. 핵심 아이디어는 다음과 같습니다.

실제 커널 사용 패턴에서 대기자의 우선순위 종류 K는 전체 노드 수 N보다 훨씬 적습니다. 예를 들어, RT-Mutex 대기열에서 100개 태스크(Task)가 대기 중이더라도 고유 우선순위 수는 보통 10~20개 이내입니다. 이 경우 plist는 list_head 대비 5~10배 빠른 삽입을 제공합니다.

plist 구조체

plist의 핵심은 두 개의 구조체입니다: struct plist_head(리스트 헤드)와 struct plist_node(개별 노드). 이 구조체들은 include/linux/plist.h에 정의되어 있습니다.

struct plist_head

/* include/linux/plist.h */
struct plist_head {
    struct list_head node_list;
};

struct plist_node

/* include/linux/plist.h */
struct plist_node {
    int                 prio;
    struct list_head    prio_list;
    struct list_head    node_list;
};

초기화 매크로

/* plist_head 초기화 */
#define PLIST_HEAD_INIT(head) { .node_list = LIST_HEAD_INIT((head).node_list) }
#define PLIST_HEAD(head) struct plist_head head = PLIST_HEAD_INIT(head)

static inline void plist_head_init(struct plist_head *head)
{
    INIT_LIST_HEAD(&head->node_list);
}

/* plist_node 초기화 */
#define PLIST_NODE_INIT(node, __prio) {             \
    .prio  = (__prio),                              \
    .prio_list = LIST_HEAD_INIT((node).prio_list),   \
    .node_list = LIST_HEAD_INIT((node).node_list),   \
}

static inline void plist_node_init(struct plist_node *node, int prio)
{
    node->prio = prio;
    INIT_LIST_HEAD(&node->prio_list);
    INIT_LIST_HEAD(&node->node_list);
}

이중 리스트 메커니즘

plist의 핵심 설계는 prio_list와 node_list라는 두 개의 독립적인 연결 리스트를 하나의 노드에 결합한 것입니다. 이 설계가 어떻게 O(K) 삽입을 달성하는지 상세히 분석합니다.

node_list: 전체 노드 정렬 리스트

node_list는 plist에 속한 모든 노드가 우선순위 오름차순으로 연결됩니다. 같은 우선순위의 노드는 삽입 순서(FIFO)를 유지합니다. 이 리스트는 일반 list_head의 이중 연결 리스트와 동일하게 동작하며, 헤드의 node_list가 앵커(Anchor) 역할을 합니다.

prio_list: 고유 우선순위 색인 리스트

prio_list는 각 고유 우선순위 그룹의 첫 번째(대표) 노드만 연결합니다. 같은 우선순위의 두 번째 이후 노드는 prio_list에 연결되지 않고, prio_list가 자기 자신을 가리키는 상태를 유지합니다.

삽입 알고리즘은 prio_list를 순회하여 새 노드의 우선순위보다 높은(값이 큰) 첫 번째 대표 노드를 찾습니다. 이 순회에서 방문하는 노드 수는 고유 우선순위 수 K에 비례하므로, 전체 노드 수 N과 무관하게 O(K) 삽입이 가능합니다.

대표 노드 판별

plist 코드에서 노드가 자신의 우선순위 그룹에서 "대표"인지 판별하는 방법은 prio_list가 비어있지 않은지(자기 자신을 가리키지 않는지) 확인하는 것입니다.

/* 대표 노드 여부 확인: prio_list가 연결되어 있으면 대표 */
static inline int plist_node_on_prio_list(struct plist_node *node)
{
    return !list_empty(&node->prio_list);
}

/* 노드가 plist에 속해있는지 확인 */
static inline int plist_node_empty(const struct plist_node *node)
{
    return list_empty(&node->node_list);
}

핵심 API

plist는 include/linux/plist.h에 인라인(Inline) 함수와 매크로로 정의된 API와, lib/plist.c에 구현된 핵심 함수로 구성됩니다.

API 전체 목록

plist_first / plist_last

/* include/linux/plist.h */
static inline struct plist_node *plist_first(const struct plist_head *head)
{
    return list_entry(head->node_list.next,
                       struct plist_node, node_list);
}

static inline struct plist_node *plist_last(const struct plist_head *head)
{
    return list_entry(head->node_list.prev,
                       struct plist_node, node_list);
}

#define plist_first_entry(head, type, member) \
    container_of(plist_first(head), type, member)

#define plist_last_entry(head, type, member) \
    container_of(plist_last(head), type, member)

순회 매크로

/* 모든 노드를 우선순위 순서대로 순회 */
#define plist_for_each(pos, head) \
    list_for_each_entry(pos, &(head)->node_list, node_list)

/* 안전한 순회 (순회 중 삭제 가능) */
#define plist_for_each_safe(pos, n, head) \
    list_for_each_entry_safe(pos, n, &(head)->node_list, node_list)

/* container_of 순회 */
#define plist_for_each_entry(pos, head, mem) \
    list_for_each_entry(pos, &(head)->node_list, mem.node_list)

/* 안전한 container_of 순회 */
#define plist_for_each_entry_safe(pos, n, head, m) \
    list_for_each_entry_safe(pos, n, &(head)->node_list, m.node_list)

삽입 알고리즘

plist_add()는 plist의 가장 핵심적인 함수입니다. O(K) 복잡도로 우선순위 정렬을 유지하면서 노드를 삽입합니다. lib/plist.c에 구현되어 있습니다.

plist_add() 소스 코드

/* lib/plist.c */
void plist_add(struct plist_node *node, struct plist_head *head)
{
    struct plist_node *first, *iter, *prev = NULL;
    struct list_head *node_next = &head->node_list;

    plist_check_head(head);
    WARN_ON(!plist_node_empty(node));
    WARN_ON(!list_empty(&node->prio_list));

    /* 빈 리스트이면 바로 삽입 */
    if (plist_head_empty(head))
        goto ins_node;

    first = plist_first(head);

    /* prio_list를 순회하여 삽입 위치 결정 (O(K)) */
    do {
        /* 현재 대표 노드보다 우선순위가 높으면(prio가 작으면) */
        if (node->prio < first->prio) {
            node_next = &first->node_list;
            break;
        }

        prev = first;
        /* prio_list의 다음 대표 노드로 이동 */
        iter = list_entry(first->prio_list.next,
                          struct plist_node, prio_list);

        /* prio_list가 한 바퀴 돌아서 첫 노드로 되돌아왔으면 */
        if (&iter->prio_list == &first->prio_list)
            break;

        first = iter;
    } while (1);

ins_node:
    /* node_list에 삽입 */
    list_add_tail(&node->node_list, node_next);

    /* prio_list 연결 결정 */
    if (!prev || prev->prio != node->prio) {
        /* 새로운 고유 우선순위: prio_list에 추가 */
        list_add(&node->prio_list, &iter->prio_list);
    }

    plist_check_head(head);
}

같은 우선순위 노드 삽입

이미 존재하는 우선순위(예: prio=5가 이미 있는데 prio=5 노드를 추가)의 경우, plist_add()의 동작이 달라집니다.

/* plist_add에서 같은 우선순위 처리 부분 */
if (!prev || prev->prio != node->prio) {
    /* 새로운 고유 우선순위: prio_list에 추가 */
    list_add(&node->prio_list, &iter->prio_list);
}
/* else: 같은 우선순위가 이미 존재 → prio_list 변경 없음
 * node의 prio_list는 초기화 상태(자기 자신 가리킴) 유지
 * node_list에만 삽입되어 FIFO 순서로 배치됨 */

삭제 알고리즘

plist_del()은 노드를 리스트에서 제거합니다. 핵심은 삭제되는 노드가 prio_list의 대표 노드인 경우, 같은 우선순위의 다음 노드에게 대표 역할을 승계해야 하는 것입니다.

/* lib/plist.c */
void plist_del(struct plist_node *node, struct plist_head *head)
{
    plist_check_head(head);

    if (!list_empty(&node->prio_list)) {
        /* 대표 노드 삭제: 후속 노드에 대표 역할 승계 */
        if (node->node_list.next != &head->node_list) {
            struct plist_node *next;

            next = list_entry(node->node_list.next,
                              struct plist_node, node_list);

            /* 다음 노드가 같은 우선순위이면 대표 승계 */
            if (next->prio == node->prio)
                list_add(&next->prio_list, &node->prio_list);
        }
        /* 기존 대표의 prio_list 연결 해제 */
        list_del_init(&node->prio_list);
    }

    /* node_list에서 제거 */
    list_del_init(&node->node_list);

    plist_check_head(head);
}

plist_requeue: 우선순위 변경 후 재배치

plist_requeue()는 노드의 prio 값이 변경된 후, 리스트에서의 위치를 올바르게 재조정합니다. 단순히 plist_del() 후 plist_add()를 호출하는 것과 의미적으로 동일하지만, 내부적으로는 약간 더 최적화되어 있습니다.

/* lib/plist.c */
void plist_requeue(struct plist_node *node, struct plist_head *head)
{
    struct plist_node *iter;
    struct list_head *node_next = &head->node_list;

    plist_check_head(head);
    BUG_ON(plist_head_empty(head));
    BUG_ON(plist_node_empty(node));

    if (node == plist_last(head))
        return;

    iter = plist_next(node);

    if (node->prio != iter->prio)
        return;

    plist_del(node, head);

    plist_for_each_continue(iter, head) {
        if (node->prio != iter->prio) {
            node_next = &iter->node_list;
            break;
        }
    }
    list_add_tail(&node->node_list, node_next);

    plist_check_head(head);
}

RT-Mutex 활용

plist의 가장 중요한 활용처는 RT-Mutex(Real-Time Mutex)의 대기자 큐입니다. RT-Mutex는 우선순위 상속(Priority Inheritance) 프로토콜을 구현하며, 가장 높은 우선순위의 대기자를 O(1)에 조회해야 합니다.

struct rt_mutex_waiter

/* kernel/locking/rtmutex_common.h */
struct rt_mutex_waiter {
    struct rb_node        tree_entry;    /* RB-tree 엔트리 (최근 커널) */
    struct rb_node        pi_tree_entry; /* PI chain RB-tree */
    struct task_struct    *task;         /* 대기 중인 태스크 */
    struct rt_mutex       *lock;         /* 대기 중인 mutex */
    int                   prio;          /* 대기자의 우선순위 */
    u64                   deadline;      /* SCHED_DEADLINE 데드라인 */
};

/* 초기 구현에서는 plist를 사용했습니다:
 * struct plist_node  list_entry;   -- mutex의 대기자 리스트
 * struct plist_node  pi_list_entry; -- 소유자의 PI 리스트
 *
 * 커널 3.x에서 plist → rbtree로 전환되었으나,
 * 개념적으로 동일한 우선순위 정렬 메커니즘입니다.
 */

우선순위 상속 체인에서의 plist

RT-Mutex에서 plist(또는 이를 대체한 rbtree)의 핵심 역할은 다음과 같습니다.

• 최고 우선순위 대기자 조회: plist_first()로 O(1)에 가장 높은 우선순위 대기자를 찾아 소유자에게 우선순위를 상속합니다.
• 대기자 추가/제거: 태스크가 mutex 대기를 시작/종료할 때 plist_add() / plist_del()로 대기열을 관리합니다.
• PI Chain 전파: 소유자의 pi_waiters plist에서 최고 우선순위가 변경되면, 해당 소유자가 다른 mutex를 대기 중인 경우 체인을 따라 전파합니다.

PM QoS 활용

PM QoS(Power Management Quality of Service) 서브시스템은 plist를 사용하여 시스템의 전력 관리 제약 조건을 관리합니다. 여러 드라이버와 사용자 공간 프로그램이 CPU 레이턴시, 네트워크 대기 시간 등의 제약을 등록하면, PM QoS는 가장 엄격한(가장 작은) 제약 값을 빠르게 조회합니다.

struct pm_qos_constraints

/* include/linux/pm_qos.h */
struct pm_qos_constraints {
    struct plist_head list;          /* 요청 리스트 (plist) */
    s32              target_value;   /* 현재 활성 제약 값 */
    s32              default_value;  /* 기본값 */
    s32              no_constraint_value; /* 제약 없음 값 */
    enum pm_qos_type type;          /* MIN/MAX/SUM */
    struct blocking_notifier_head *notifiers;
};

struct pm_qos_request {
    struct plist_node node;           /* plist 노드 */
    s32              priority;        /* = node.prio */
};

/* PM QoS 타입별 집계 방식 */
enum pm_qos_type {
    PM_QOS_UNITIALIZED,
    PM_QOS_MAX,   /* plist_last() 사용: 최대값 반환 */
    PM_QOS_MIN,   /* plist_first() 사용: 최소값 반환 */
    PM_QOS_SUM,   /* 전체 합계 계산 */
};

PM QoS 요청 등록 흐름

/* kernel/power/qos.c (단순화) */
void pm_qos_update_target(struct pm_qos_constraints *c,
                          struct plist_node *node,
                          enum pm_qos_req_action action,
                          s32 value)
{
    s32 prev_value, curr_value;

    prev_value = pm_qos_get_value(c);

    switch (action) {
    case PM_QOS_ADD_REQ:
        plist_node_init(node, value);
        plist_add(node, &c->list);     /* O(K) 삽입 */
        break;
    case PM_QOS_REMOVE_REQ:
        plist_del(node, &c->list);     /* O(1) 삭제 */
        break;
    case PM_QOS_UPDATE_REQ:
        plist_del(node, &c->list);
        plist_node_init(node, value);
        plist_add(node, &c->list);
        break;
    }

    curr_value = pm_qos_get_value(c);   /* O(1): plist_first/last */

    if (prev_value != curr_value)
        blocking_notifier_call_chain(c->notifiers,
                                     0, &curr_value);
}

static s32 pm_qos_get_value(struct pm_qos_constraints *c)
{
    if (plist_head_empty(&c->list))
        return c->no_constraint_value;

    switch (c->type) {
    case PM_QOS_MIN:
        return plist_first(&c->list)->prio;  /* O(1) */
    case PM_QOS_MAX:
        return plist_last(&c->list)->prio;   /* O(1) */
    /* ... */
    }
}

Futex 활용

Futex(Fast Userspace Mutex)의 PI(Priority Inheritance) 변형에서도 plist가 사용됩니다. FUTEX_LOCK_PI 시스템 호출은 커널 내부에서 RT-Mutex 메커니즘을 활용하며, 이 과정에서 plist(또는 rbtree)로 대기자를 관리합니다.

futex_pi_state

/* kernel/futex/futex.h */
struct futex_pi_state {
    struct list_head list;          /* 글로벌 해시 체인 */
    struct rt_mutex_base pi_mutex;  /* RT-Mutex (내부적으로 plist/rbtree 사용) */
    struct task_struct *owner;      /* futex 소유자 */
    refcount_t refcount;            /* 참조 카운트 */
    union futex_key key;            /* futex 식별 키 */
};

성능 분석

plist의 성능을 다른 자료구조와 정량적으로 비교합니다. 핵심 메트릭은 삽입, 삭제, 최솟값 접근의 복잡도와 메모리 오버헤드입니다.

복잡도 비교

* rbtree의 최솟값 접근은 rb_root_cached를 사용할 때 O(1)입니다.

plist가 유리한 조건

plist가 다른 자료구조보다 유리한 조건은 다음과 같습니다.

• K « N: 고유 우선순위 수가 전체 노드 수보다 훨씬 적을 때. RT 우선순위(0~99)에서 실제 사용되는 수준은 10~20개가 일반적이므로, 수백 개 태스크가 대기해도 O(K) = O(10~20)입니다.
• 빈번한 삭제: plist의 O(1) 삭제는 rbtree의 O(log N) 삭제보다 빠릅니다. 대기열에서 태스크를 깨우는 연산이 빈번한 경우 유리합니다.
• O(1) 최솟값이 핵심: 최고 우선순위 대기자를 상수 시간에 조회해야 하고, 캐시된 rbtree의 추가 포인터 오버헤드를 원하지 않을 때.

plist가 불리한 조건

• K ≈ N: 모든 노드가 고유 우선순위를 가지면 O(K) = O(N)이 되어 일반 정렬 리스트와 동일합니다.
• 복합 정렬 키: SCHED_DEADLINE의 (priority, deadline) 복합 키처럼 단순 정수 비교로 정렬할 수 없는 경우, rbtree가 적합합니다. 이것이 RT-Mutex가 plist에서 rbtree로 전환된 이유입니다.
• 메모리 제약: 노드당 36바이트(64비트)는 list_head의 16바이트나 min-heap의 8바이트 대비 상당한 오버헤드입니다.

디버깅

CONFIG_DEBUG_PLIST 커널 설정을 활성화하면, plist의 무결성(Integrity)을 삽입/삭제 시마다 검증합니다.

CONFIG_DEBUG_PLIST

/* lib/plist.c - CONFIG_DEBUG_PLIST 활성화 시 */
static void plist_check_prev_next(struct list_head *t,
                                  struct list_head *p,
                                  struct list_head *n)
{
    WARN(n->prev != p || p->next != n,
         "top: %p, move prev: %p, prev->next: %p, "
         "move next: %p, next->prev: %p\n",
         t, p, p->next, n, n->prev);
}

static void plist_check_list(struct list_head *top)
{
    struct list_head *prev = top, *next = top->next;

    while (next != top) {
        plist_check_prev_next(top, prev, next);
        WARN_ON(next == next->next);
        prev = next;
        next = prev->next;
    }
    plist_check_prev_next(top, prev, next);
}

static void plist_check_head(struct plist_head *head)
{
    if (!plist_head_empty(head))
        plist_check_list(&head->node_list);

    /* prio_list도 검증 (생략) */
}

디버깅 기법

# CONFIG_DEBUG_PLIST 활성화
CONFIG_DEBUG_PLIST=y

# plist 관련 WARN 메시지 확인
dmesg | grep -i plist

# ftrace로 plist_add/plist_del 추적
echo plist_add > /sys/kernel/debug/tracing/set_ftrace_filter
echo plist_del >> /sys/kernel/debug/tracing/set_ftrace_filter
echo function > /sys/kernel/debug/tracing/current_tracer
echo 1 > /sys/kernel/debug/tracing/tracing_on
cat /sys/kernel/debug/tracing/trace

# KGDB로 plist 내용 출력 (GDB 명령)
(gdb) p *(struct plist_head *)&pm_qos->constraints.list
(gdb) set $node = pm_qos->constraints.list.node_list.next
(gdb) p ((struct plist_node *)((char *)$node - 16))->prio

소스 코드 워크스루

plist의 핵심 소스 파일을 상세히 추적합니다. 전체 구현은 놀라울 정도로 작습니다: lib/plist.c는 약 130줄에 불과합니다.

plist_add 내부 로직 추적

6개의 노드가 있는 plist에 새 노드(prio=15)를 삽입하는 과정을 소스 코드 수준에서 추적합니다.

/* 초기 상태:
 * node_list: [5]->[5]->[10]->[10]->[20]->[20]->HEAD
 * prio_list: [5]---->[10]---->[20]---->[5] (순환)
 * 삽입할 노드: new_node, prio=15
 */

void plist_add(struct plist_node *node, struct plist_head *head)
{
    /* node = new_node (prio=15) */
    struct plist_node *first, *iter, *prev = NULL;
    struct list_head *node_next = &head->node_list;

    /* 디버그 검증 (CONFIG_DEBUG_PLIST) */
    plist_check_head(head);                 /* 무결성 확인 */
    WARN_ON(!plist_node_empty(node));       /* 이미 다른 리스트에 있으면 경고 */
    WARN_ON(!list_empty(&node->prio_list)); /* prio_list가 비어있어야 함 */

    /* 리스트가 비어있지 않으므로 skip */
    first = plist_first(head);  /* first = [5]의 첫 노드 */

    /* === prio_list 순회 루프 시작 === */

    /* 반복 1: first=[5], 15 >= 5 → 통과 */
    prev = first;               /* prev = [5] */
    iter = prio_list의 다음;    /* iter = [10] */

    /* 반복 2: first=[10], 15 >= 10 → 통과 */
    prev = first;               /* prev = [10] */
    iter = prio_list의 다음;    /* iter = [20] */

    /* 반복 3: first=[20], 15 < 20 → 여기 앞에 삽입! */
    node_next = &first->node_list;  /* [20]의 node_list 앞 */
    break;

    /* === 순회 종료: 3회 비교 (K=3 고유 우선순위) === */

ins_node:
    /* [10]->[10] 뒤, [20] 앞에 삽입 */
    list_add_tail(&node->node_list, node_next);
    /* node_list: [5]->[5]->[10]->[10]->[15]->[20]->[20]->HEAD */

    /* prev=[10], prev->prio(10) != node->prio(15) */
    /* → 새로운 고유 우선순위! prio_list에 추가 */
    list_add(&node->prio_list, &iter->prio_list);
    /* prio_list: [5]---->[10]---->[15]---->[20]---->[5] */

    plist_check_head(head);     /* 최종 무결성 확인 */
}

/* 최종 상태:
 * node_list: [5]->[5]->[10]->[10]->[15]->[20]->[20]->HEAD
 * prio_list: [5]---->[10]---->[15]---->[20]---->[5]
 * K: 3→4, N: 6→7
 */

plist_del 대표 노드 삭제 추적

/* 초기 상태:
 * node_list: [5.A]->[5.B]->[10.C]->HEAD
 * prio_list: [5.A]---->[10.C]---->[5.A]
 * 삭제할 노드: [5.A] (prio=5의 대표 노드)
 */

void plist_del(struct plist_node *node, struct plist_head *head)
{
    /* node = [5.A] */
    plist_check_head(head);

    /* [5.A]의 prio_list가 비어있지 않음 → 대표 노드 */
    if (!list_empty(&node->prio_list)) {  /* true */

        /* [5.A]의 다음 노드가 HEAD가 아님 */
        if (node->node_list.next != &head->node_list) {  /* true: next = [5.B] */
            struct plist_node *next;
            next = list_entry(node->node_list.next,
                              struct plist_node, node_list);
            /* next = [5.B] */

            /* [5.B]의 prio(5) == [5.A]의 prio(5) → 대표 승계! */
            if (next->prio == node->prio)  /* true */
                list_add(&next->prio_list, &node->prio_list);
                /* [5.B]가 prio_list에 연결됨 */
        }
        /* [5.A]의 prio_list 연결 해제 */
        list_del_init(&node->prio_list);
    }

    /* [5.A]의 node_list 연결 해제 */
    list_del_init(&node->node_list);

    plist_check_head(head);
}

/* 최종 상태:
 * node_list: [5.B]->[10.C]->HEAD
 * prio_list: [5.B]---->[10.C]---->[5.B]
 * [5.A]: node_list=self, prio_list=self (격리됨)
 */

관련 자료구조 비교

커널에서 우선순위 기반 데이터를 관리하는 다양한 자료구조를 비교합니다. 각 자료구조는 특정 사용 패턴에 최적화되어 있습니다.

종합 비교표

선택 가이드

우선순위 정렬이 필요한가?
├── 아니오 → list_head (가장 단순, O(1) 삽입/삭제)
└── 예
    ├── 복합 정렬 키 (priority + deadline)?
    │   └── 예 → rbtree (유연한 비교 함수)
    ├── K « N (고유 우선순위 ≪ 전체 노드)?
    │   └── 예 → plist (O(K) 삽입, O(1) 삭제)
    ├── 고정 크기 배열 가능?
    │   └── 예 → min-heap (캐시 친화적, 낮은 메모리)
    └── 그 외 → rbtree (범용 O(log N))

실전 사용 패턴

plist를 커널 모듈이나 서브시스템에서 사용하는 실전 패턴을 소개합니다.

기본 사용 패턴

#include <linux/plist.h>

struct my_task {
    struct plist_node pnode;
    char              name[32];
    int               data;
};

static PLIST_HEAD(task_queue);        /* 정적 선언 */
static DEFINE_SPINLOCK(queue_lock);  /* plist 보호용 락 */

/* 태스크 추가: 우선순위 순서 유지 */
void enqueue_task(struct my_task *task, int prio)
{
    plist_node_init(&task->pnode, prio);

    spin_lock(&queue_lock);
    plist_add(&task->pnode, &task_queue);
    spin_unlock(&queue_lock);
}

/* 가장 높은 우선순위 태스크 꺼내기 */
struct my_task *dequeue_highest(void)
{
    struct my_task *task = NULL;

    spin_lock(&queue_lock);
    if (!plist_head_empty(&task_queue)) {
        task = plist_first_entry(&task_queue,
                                  struct my_task, pnode);
        plist_del(&task->pnode, &task_queue);
    }
    spin_unlock(&queue_lock);

    return task;
}

/* 모든 태스크 순회 */
void print_all_tasks(void)
{
    struct my_task *task;

    spin_lock(&queue_lock);
    plist_for_each_entry(task, &task_queue, pnode) {
        pr_info("task: %s, prio: %d\n",
                task->name, task->pnode.prio);
    }
    spin_unlock(&queue_lock);
}

동적 우선순위 변경

/* 태스크의 우선순위를 동적으로 변경 */
void update_task_priority(struct my_task *task, int new_prio)
{
    spin_lock(&queue_lock);

    if (!plist_node_empty(&task->pnode)) {
        /* 리스트에서 제거 후 새 우선순위로 재삽입 */
        plist_del(&task->pnode, &task_queue);
        plist_node_init(&task->pnode, new_prio);
        plist_add(&task->pnode, &task_queue);
    } else {
        /* 리스트에 없으면 prio만 업데이트 */
        task->pnode.prio = new_prio;
    }

    spin_unlock(&queue_lock);
}

/* 최고/최저 우선순위 값 조회 */
int get_highest_priority(void)
{
    int prio = INT_MAX;

    spin_lock(&queue_lock);
    if (!plist_head_empty(&task_queue))
        prio = plist_first(&task_queue)->prio;  /* O(1) */
    spin_unlock(&queue_lock);

    return prio;
}

int get_lowest_priority(void)
{
    int prio = INT_MIN;

    spin_lock(&queue_lock);
    if (!plist_head_empty(&task_queue))
        prio = plist_last(&task_queue)->prio;   /* O(1) */
    spin_unlock(&queue_lock);

    return prio;
}

안전한 순회와 조건부 삭제

/* 특정 우선순위 이하의 모든 태스크 제거 */
void purge_low_priority(int threshold)
{
    struct my_task *task, *tmp;

    spin_lock(&queue_lock);
    plist_for_each_entry_safe(task, tmp, &task_queue, pnode) {
        /* prio가 threshold보다 크면(낮은 우선순위) 제거 */
        if (task->pnode.prio > threshold) {
            plist_del(&task->pnode, &task_queue);
            kfree(task);
        }
    }
    spin_unlock(&queue_lock);
}

커널 소스 분석: 전체 plist.c

lib/plist.c의 전체 구현은 약 130줄로, 커널 자료구조 중 가장 간결한 구현 중 하나입니다. 핵심 함수 3개(plist_add, plist_del, plist_requeue)와 디버그 코드로 구성됩니다.

파일 구조

include/linux/plist.h     ~180줄  구조체, 매크로, 인라인 함수
lib/plist.c               ~130줄  plist_add, plist_del, plist_requeue
lib/Kconfig.debug         CONFIG_DEBUG_PLIST 정의

주요 사용처:
kernel/power/qos.c        PM QoS 제약 관리
kernel/locking/rtmutex.c  RT-Mutex (역사적 사용)
kernel/futex/             Futex PI (간접 사용)

plist.h 헤더 분석

include/linux/plist.h의 주요 구성 요소를 분석합니다.

/* include/linux/plist.h 핵심 구조 */

/* 1. 헤더 가드 및 의존성 */
#ifndef _LINUX_PLIST_H_
#define _LINUX_PLIST_H_

#include <linux/kernel.h>
#include <linux/list.h>

/* 2. 구조체 정의 (앞서 분석) */

/* 3. 유틸리티 인라인 함수 */
static inline int plist_head_empty(const struct plist_head *head)
{
    return list_empty(&head->node_list);
}

static inline int plist_node_empty(const struct plist_node *node)
{
    return list_empty(&node->node_list);
}

/* 4. 외부 함수 선언 */
extern void plist_add(struct plist_node *node, struct plist_head *head);
extern void plist_del(struct plist_node *node, struct plist_head *head);
extern void plist_requeue(struct plist_node *node, struct plist_head *head);

/* 5. plist_next/plist_prev 인라인 */
static inline struct plist_node *plist_next(struct plist_node *pos)
{
    return list_next_entry(pos, node_list);
}

static inline struct plist_node *plist_prev(struct plist_node *pos)
{
    return list_prev_entry(pos, node_list);
}

#endif /* _LINUX_PLIST_H_ */

내부 불변식(Invariant)

plist가 올바르게 동작하기 위해서는 다음 불변식이 항상 유지되어야 합니다. CONFIG_DEBUG_PLIST는 이 불변식을 런타임에 검증합니다.

6가지 핵심 불변식

엣지 케이스 분석

plist 구현이 올바르게 처리해야 하는 엣지 케이스(Edge Case)를 분석합니다. 이 케이스들은 plist 단위 테스트(lib/plist.c의 plist_test_requeue 등)에서 검증됩니다.

빈 리스트에 첫 노드 삽입

/* 엣지 케이스 1: 빈 리스트에 삽입 */
struct plist_head head;
struct plist_node n1;

plist_head_init(&head);
plist_node_init(&n1, 10);

plist_add(&n1, &head);
/* 결과:
 * - plist_head_empty(&head) == false
 * - plist_first(&head) == &n1
 * - plist_last(&head) == &n1
 * - n1이 prio_list 대표 (유일한 노드)
 * - node_list: head <-> n1 <-> head (순환)
 */

/* 유일한 노드 삭제 → 빈 리스트 복원 */
plist_del(&n1, &head);
/* 결과:
 * - plist_head_empty(&head) == true
 * - plist_node_empty(&n1) == true
 */

모든 노드가 같은 우선순위

/* 엣지 케이스 2: 모든 노드가 prio=5 */
struct plist_node n1, n2, n3;

plist_node_init(&n1, 5);
plist_node_init(&n2, 5);
plist_node_init(&n3, 5);

plist_add(&n1, &head);  /* K=1, n1은 대표 */
plist_add(&n2, &head);  /* K=1, n2는 비대표 */
plist_add(&n3, &head);  /* K=1, n3는 비대표 */

/* node_list: n1 -> n2 -> n3 (FIFO)
 * prio_list: n1만 연결 (K=1)
 *
 * 삽입마다 prio_list를 순회하지만 K=1이므로
 * 실질적으로 O(1) 삽입!
 *
 * 대표 n1 삭제 시:
 * - n2가 새 대표로 승계
 * - node_list: n2 -> n3
 * - prio_list: n2만 연결
 */

모든 노드가 고유 우선순위

엣지 케이스 3: 모든 노드가 다른 prio (최악 케이스) prio: 1, 2, 3, 4, 5 -- 5개 노드, 5개 고유 우선순위

K = N = 5 → plist_add는 O(N)으로 퇴화 이 경우 plist의 이점이 없으며, rbtree의 O(log N)이 더 효율적입니다.

그러나 모든 노드가 prio_list 대표이므로:

• prio_list와 node_list가 동일한 순서
• 메모리 오버헤드만 증가 (prio_list 포인터 낭비)

실전에서 이 패턴은 드물지만, SCHED_DEADLINE 태스크는 각각 고유한 deadline을 가지므로 K ≈ N이 될 수 있습니다. 이것이 RT-Mutex가 plist에서 rbtree로 전환된 핵심 이유입니다.

plist_requeue 엣지 케이스

/* 엣지 케이스 4: requeue - 이미 그룹 끝에 있는 경우 */
/* node_list: n1(5) -> n2(5) -> n3(10) */

plist_requeue(&n2, &head);
/* n2는 이미 prio=5 그룹의 마지막 (다음이 n3, prio=10)
 * → node->prio(5) != iter->prio(10)
 * → 즉시 반환 (no-op)
 */

plist_requeue(&n1, &head);
/* n1은 prio=5 그룹의 첫 번째, 다음이 n2(prio=5)
 * → node->prio(5) == iter->prio(5)
 * → n1을 삭제 후, prio=5 그룹 끝(n3 앞)에 재삽입
 * 결과: n2(5) -> n1(5) -> n3(10)
 * n2가 새 대표
 */

역사적 변천

plist는 리눅스 커널에서 10년 이상 사용되어 온 안정적인 자료구조입니다. 도입 배경과 이후 변화를 정리합니다.

주요 이력

RT-Mutex의 plist → rbtree 전환 분석

RT-Mutex가 plist에서 rbtree로 전환된 핵심 이유를 분석합니다.

/* SCHED_DEADLINE 이전: plist로 충분 */
struct rt_mutex_waiter {
    struct plist_node list_entry;    /* prio 기반 정렬 */
    struct plist_node pi_list_entry; /* PI chain 정렬 */
};

/* SCHED_DEADLINE 도입 후: 복합 키 필요 */
/* waiter 비교: (prio, deadline) 순서
 * plist의 prio는 단일 int → deadline 비교 불가
 * rbtree의 비교 함수로 (prio, deadline) 복합 정렬 가능
 *
 * 예: Task A (prio=49, deadline=100ms)
 *     Task B (prio=49, deadline=50ms)
 * plist: 같은 prio → FIFO (A 먼저) ← 부적절!
 * rbtree: deadline 비교 → B 먼저 (올바른 EDF 순서)
 */

/* 전환 후 구조 */
struct rt_mutex_waiter {
    struct rb_node tree_entry;      /* rbtree 엔트리 */
    struct rb_node pi_tree_entry;   /* PI chain rbtree */
    struct task_struct *task;
    struct rt_mutex *lock;
    int prio;
    u64 deadline;                   /* SCHED_DEADLINE 지원 */
};

/* 비교 함수 */
static inline bool rt_mutex_waiter_less(
    struct rt_mutex_waiter *left,
    struct rt_mutex_waiter *right)
{
    if (left->prio < right->prio)
        return 1;
    if (left->prio > right->prio)
        return 0;
    /* 같은 prio: deadline이 작은 것이 우선 */
    if (dl_prio(left->prio))
        return dl_time_before(left->deadline, right->deadline);
    return 0;
}

커널 모듈 테스트 예제

plist의 동작을 검증하는 간단한 커널 모듈 예제입니다. dmesg로 출력을 확인할 수 있습니다.

/* plist_test.c - plist 기능 검증 커널 모듈 */
#include <linux/module.h>
#include <linux/plist.h>
#include <linux/slab.h>

MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("plist test module");

struct test_item {
    struct plist_node node;
    int               id;
};

static void dump_plist(struct plist_head *head, const char *label)
{
    struct test_item *item;

    pr_info("[plist_test] %s:\n", label);
    if (plist_head_empty(head)) {
        pr_info("  (empty)\n");
        return;
    }
    plist_for_each_entry(item, head, node) {
        pr_info("  id=%d prio=%d rep=%s\n",
                item->id, item->node.prio,
                !list_empty(&item->node.prio_list) ? "YES" : "no");
    }
    pr_info("  first: id=%d prio=%d\n",
            plist_first_entry(head, struct test_item, node)->id,
            plist_first(head)->prio);
    pr_info("  last:  id=%d prio=%d\n",
            plist_last_entry(head, struct test_item, node)->id,
            plist_last(head)->prio);
}

static int __init plist_test_init(void)
{
    PLIST_HEAD(head);
    struct test_item items[6];
    int prios[] = { 10, 5, 20, 5, 10, 15 };
    int i;

    pr_info("[plist_test] === plist test start ===\n");

    /* 1. 순차 삽입 */
    for (i = 0; i < 6; i++) {
        items[i].id = i;
        plist_node_init(&items[i].node, prios[i]);
        plist_add(&items[i].node, &head);
    }
    dump_plist(&head, "after 6 insertions");
    /* 기대 순서: [5,1] [5,3] [10,0] [10,4] [15,5] [20,2] */

    /* 2. 대표 노드 삭제 */
    plist_del(&items[1].node, &head);  /* id=1, prio=5 (대표) 삭제 */
    dump_plist(&head, "after del id=1(prio=5 rep)");
    /* id=3이 prio=5의 새 대표 */

    /* 3. 비대표 노드 삭제 */
    plist_del(&items[4].node, &head);  /* id=4, prio=10 (비대표) 삭제 */
    dump_plist(&head, "after del id=4(prio=10 non-rep)");

    /* 4. first/last 확인 */
    pr_info("[plist_test] first prio=%d, last prio=%d\n",
            plist_first(&head)->prio,
            plist_last(&head)->prio);

    /* 5. 전체 삭제 */
    plist_del(&items[3].node, &head);
    plist_del(&items[0].node, &head);
    plist_del(&items[5].node, &head);
    plist_del(&items[2].node, &head);
    dump_plist(&head, "after all deletions");

    pr_info("[plist_test] === plist test done ===\n");
    return 0;
}

static void __exit plist_test_exit(void)
{
    pr_info("[plist_test] module unloaded\n");
}

module_init(plist_test_init);
module_exit(plist_test_exit);

빌드 Makefile

obj-m += plist_test.o

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

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

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

예상 출력

# 모듈 로드 후 dmesg 확인
$ sudo insmod plist_test.ko
$ dmesg | tail -30

[plist_test] === plist test start ===
[plist_test] after 6 insertions:
  id=1 prio=5 rep=YES
  id=3 prio=5 rep=no
  id=0 prio=10 rep=YES
  id=4 prio=10 rep=no
  id=5 prio=15 rep=YES
  id=2 prio=20 rep=YES
  first: id=1 prio=5
  last:  id=2 prio=20
[plist_test] after del id=1(prio=5 rep):
  id=3 prio=5 rep=YES           ← id=3이 새 대표!
  id=0 prio=10 rep=YES
  id=4 prio=10 rep=no
  id=5 prio=15 rep=YES
  id=2 prio=20 rep=YES
  first: id=3 prio=5
  last:  id=2 prio=20
[plist_test] after del id=4(prio=10 non-rep):
  id=3 prio=5 rep=YES
  id=0 prio=10 rep=YES          ← id=0은 여전히 대표
  id=5 prio=15 rep=YES
  id=2 prio=20 rep=YES
  first: id=3 prio=5
  last:  id=2 prio=20
[plist_test] first prio=5, last prio=20
[plist_test] after all deletions:
  (empty)
[plist_test] === plist test done ===

PM QoS 심층 분석

PM QoS에서 plist가 어떻게 활용되는지 더 깊이 분석합니다. CPU idle governor가 PM QoS 제약을 기반으로 idle 상태를 선택하는 전체 경로를 추적합니다.

CPU Latency QoS

/* 드라이버에서 CPU 레이턴시 제약 등록 */
struct pm_qos_request my_req;

/* 네트워크 드라이버: 패킷 처리 시 50us 이하 깨어남 보장 요청 */
cpu_latency_qos_add_request(&my_req, 50);
/* 내부: plist_node_init(&my_req.node, 50);
 *       plist_add(&my_req.node, &cpu_latency_constraints.list);
 * plist에 prio=50 노드 삽입 */

/* USB 드라이버: 100us 이하 레이턴시 요청 */
struct pm_qos_request usb_req;
cpu_latency_qos_add_request(&usb_req, 100);
/* plist에 prio=100 노드 삽입 */

/* 오디오 드라이버: 20us 이하 레이턴시 요청 */
struct pm_qos_request audio_req;
cpu_latency_qos_add_request(&audio_req, 20);
/* plist에 prio=20 노드 삽입 */

/* 현재 활성 제약 = plist_first()->prio = 20us
 * CPU idle governor는 탈출 레이턴시가 20us 이하인 idle 상태만 선택
 */

/* 오디오 재생 종료 → 제약 해제 */
cpu_latency_qos_remove_request(&audio_req);
/* plist_del → 새 first = 50us (네트워크 제약)
 * CPU idle governor가 더 깊은 idle 상태를 선택 가능 → 전력 절감
 */

Device PM QoS와 per-device plist

/* 디바이스별 PM QoS 제약도 plist를 사용합니다 */
struct dev_pm_qos {
    struct pm_qos_constraints resume_latency;  /* plist 사용 */
    struct pm_qos_constraints latency_tolerance;
    struct pm_qos_flags flags;
};

/* 예: eMMC 컨트롤러 resume latency 제약 */
dev_pm_qos_add_request(mmc_dev, &mmc_qos_req,
                       DEV_PM_QOS_RESUME_LATENCY, 100);
/* mmc_dev의 resume_latency plist에 prio=100 삽입
 * 이 디바이스가 100us 이내에 resume 가능한 전력 상태만 사용 */

/* 사용자 공간에서도 제약 가능 */
/* /sys/devices/.../power/pm_qos_resume_latency_us */
/* echo 50 > pm_qos_resume_latency_us */

메모리 오버헤드 상세 분석

plist의 메모리 오버헤드를 아키텍처별로 정량 분석합니다.

노드당 오버헤드

/* 64비트 plist_node 메모리 레이아웃 상세 */
struct plist_node {
    int  prio;                /* 오프셋 0, 4 bytes */
    /* 4 bytes 패딩 (8바이트 정렬) */
    struct list_head prio_list; /* 오프셋 8, 16 bytes (prev+next) */
    struct list_head node_list; /* 오프셋 24, 16 bytes (prev+next) */
};                              /* 총: 4 + 4(pad) + 16 + 16 = 40 bytes */

/* 실제 크기 확인 */
pr_info("sizeof(plist_node) = %zu\n", sizeof(struct plist_node));
/* x86_64: 40 bytes (컴파일러 패딩 포함)
 * arm64:  40 bytes
 * 32-bit: 20 bytes
 */

/* 실전 오버헤드 계산 예시:
 * PM QoS에서 동시 활성 요청 20개 가정
 * 추가 메모리 = 20 * (40 - 16) = 480 bytes (list_head 대비)
 * → 무시할 수 있는 수준
 *
 * RT-Mutex 대기열에서 100개 태스크 가정
 * 추가 메모리 = 100 * (40 - 16) = 2,400 bytes
 * → 여전히 무시할 수 있는 수준
 */

캐시 동작 특성

plist의 캐시 동작 분석

캐시 라인 크기: 일반적으로 64 bytes

plist_node (40 bytes) → 1개 캐시 라인에 1개 노드 plist_add의 prio_list 순회:

• K개 캐시 라인 접근 (각 대표 노드)
• 대표 노드가 인접하지 않으므로 캐시 미스 가능

list_head (16 bytes) → 1개 캐시 라인에 4개 노드

• 순차 순회에서 더 캐시 친화적

min-heap (연속 배열) → 가장 캐시 친화적

• 배열 내 연속 메모리 → 프리페치 최적화

rbtree (노드 포인터) → 트리 구조로 캐시 미스 빈번

• 단, 높이 O(log N)으로 접근 횟수 제한

결론: 캐시 효율은 min-heap > list_head > plist ≈ rbtree 그러나 plist의 순회 거리 K가 작으므로 실측 영향은 미미합니다

흔한 실수와 주의사항

동시성 보호 누락

/* ✗ 잘못된 사용: 락 없이 plist 조작 */
plist_add(&node, &head);  /* 레이스 조건 발생 가능! */

/* ✓ 올바른 사용: 반드시 외부 락으로 보호 */
spin_lock(&lock);
plist_add(&node, &head);
spin_unlock(&lock);

이중 삽입

/* ✗ 잘못된 사용: 이미 삽입된 노드를 다시 삽입 */
plist_add(&node, &head);
plist_add(&node, &head);  /* WARN_ON 발생! 리스트 손상! */

/* ✓ 올바른 사용: 삽입 전 empty 확인 */
if (plist_node_empty(&node))
    plist_add(&node, &head);

삽입 후 prio 직접 변경

/* ✗ 잘못된 사용: prio를 직접 수정 → 정렬 깨짐 */
plist_add(&node, &head);
node.prio = 5;  /* 불변식 I1 위반! 정렬 순서 깨짐! */

/* ✓ 올바른 사용: del → init → add 또는 requeue */
plist_del(&node, &head);
plist_node_init(&node, 5);
plist_add(&node, &head);

안전하지 않은 순회 중 삭제

/* ✗ 잘못된 사용: 일반 순회 중 삭제 */
plist_for_each_entry(item, &head, node) {
    if (should_remove(item))
        plist_del(&item->node, &head);  /* 순회 깨짐! */
}

/* ✓ 올바른 사용: _safe 변형 사용 */
plist_for_each_entry_safe(item, tmp, &head, node) {
    if (should_remove(item))
        plist_del(&item->node, &head);  /* 안전! */
}

API 빠른 참조

plist API의 사용 패턴을 한눈에 파악할 수 있는 빠른 참조표입니다.

/* ============================================================
 *  plist API Quick Reference
 * ============================================================ */

/* --- 선언 및 초기화 --- */
PLIST_HEAD(name);                              /* 정적 선언 + 초기화 */
plist_head_init(&head);                        /* 동적 초기화 */
PLIST_NODE_INIT(node, prio);                   /* 노드 정적 초기화 */
plist_node_init(&node, prio);                  /* 노드 동적 초기화 */

/* --- 삽입/삭제/재배치 --- */
plist_add(&node, &head);                       /* O(K) 정렬 삽입 */
plist_del(&node, &head);                       /* O(1) 삭제 */
plist_requeue(&node, &head);                   /* O(K) FIFO 재배치 */

/* --- 상태 확인 --- */
plist_head_empty(&head);                       /* 리스트 비어있는지 */
plist_node_empty(&node);                       /* 노드가 미연결인지 */

/* --- 최솟값/최댓값 접근 --- */
plist_first(&head);                             /* O(1) 최솟값 plist_node* */
plist_last(&head);                              /* O(1) 최댓값 plist_node* */
plist_first_entry(&head, type, member);        /* O(1) 외부 구조체* */
plist_last_entry(&head, type, member);         /* O(1) 외부 구조체* */

/* --- 순회 --- */
plist_for_each(pos, &head);                    /* plist_node 순회 */
plist_for_each_safe(pos, n, &head);            /* 안전한 순회 */
plist_for_each_entry(pos, &head, mem);         /* 외부 구조체 순회 */
plist_for_each_entry_safe(pos, n, &head, m);   /* 안전한 외부 순회 */

/* --- 이동 --- */
plist_next(&node);                              /* 다음 노드 */
plist_prev(&node);                              /* 이전 노드 */

plist_add 시각화

plist_add()는 삽입 위치에 따라 세 가지 대표적인 케이스로 분류됩니다. 각 케이스에서 prio_list와 node_list가 어떻게 변화하는지 Before/After 상태를 시각적으로 비교합니다.

/* 케이스 1: 새로운 고유 우선순위 삽입 — plist_add() 내부 핵심 경로 */
/* lib/plist.c — plist_add 핵심 루프 */
void plist_add(struct plist_node *node, struct plist_head *head)
{
    struct plist_node *first, *iter, *prev = NULL;
    struct list_head *node_next = &head->node_list;

    /* 1단계: prio_list 순회 — O(K) */
    if (!plist_head_empty(head)) {
        first = iter = plist_first(head);
        do {
            if (node->prio < iter->prio) {
                node_next = &iter->node_list;
                break;     /* 삽입 위치 발견 */
            }
            prev = iter;
            iter = list_entry(iter->prio_list.next,
                              struct plist_node, prio_list);
        } while (iter != first);
    }

    /* 2단계: node_list 삽입 (FIFO) */
    list_add_tail(&node->node_list, node_next);

    /* 3단계: 새 고유 우선순위이면 prio_list에도 추가 */
    if (!prev || prev->prio != node->prio)
        list_add_tail(&node->prio_list, &iter->prio_list);
    /* 기존 prio와 같으면 prio_list는 변경 없음 (INIT_LIST_HEAD 상태 유지) */
}

/* 케이스별 삽입 동작 검증 코드 */
PLIST_HEAD(head);
struct plist_node a, b, c, new_node;

/* 초기 상태 구축: A(5), B(5), C(20) */
plist_node_init(&a, 5);
plist_node_init(&b, 5);
plist_node_init(&c, 20);
plist_add(&a, &head);
plist_add(&b, &head);
plist_add(&c, &head);
/* 상태: node_list = [A(5), B(5), C(20)]
 *        prio_list = [A(5), C(20)]           */

/* 케이스 1: 새 고유 우선순위 10 삽입 */
plist_node_init(&new_node, 10);
plist_add(&new_node, &head);
/* 결과: node_list = [A(5), B(5), NEW(10), C(20)]
 *        prio_list = [A(5), NEW(10), C(20)]
 *        NEW가 prio=10의 대표 노드                */

/* 케이스 2: 기존 우선순위 5에 합류 */
struct plist_node d;
plist_node_init(&d, 5);
plist_add(&d, &head);
/* 결과: node_list = [A(5), B(5), D(5), NEW(10), C(20)]
 *        prio_list = [A(5), NEW(10), C(20)]
 *        A가 여전히 prio=5의 대표 노드 (D는 비대표)   */

plist_del 시각화

plist_del()의 핵심 복잡성은 대표 노드 삭제 시 승격(Promotion)에 있습니다. 삭제할 노드가 해당 우선순위 그룹의 대표 노드(prio_list에 연결된 노드)라면, 같은 우선순위의 다음 노드가 새 대표로 승격되어야 합니다.

/* lib/plist.c — plist_del 핵심 로직: 대표 노드 승격 */
void plist_del(struct plist_node *node, struct plist_head *head)
{
    if (!list_empty(&node->prio_list)) {
        /* 대표 노드 삭제 — 승격 필요 여부 확인 */
        struct plist_node *next;

        next = list_entry(node->node_list.next,
                          struct plist_node, node_list);

        /* 다음 노드가 같은 prio이면 대표 승격 */
        if (node->node_list.next != &head->node_list &&
            next->prio == node->prio) {
            /* next의 prio_list를 node의 prio_list 위치에 교체 */
            list_add(&next->prio_list, &node->prio_list);
        }
        /* 다른 prio이면 해당 그룹의 마지막 노드 → prio_list 엔트리 자체 제거 */
        list_del_init(&node->prio_list);
    }

    /* node_list에서 제거 */
    list_del_init(&node->node_list);
}

/* 대표 노드 삭제 → 승격 검증 */
PLIST_HEAD(head);
struct plist_node a, b, c, d, e;

plist_node_init(&a, 5);   /* prio=5 대표 */
plist_node_init(&b, 5);   /* prio=5 비대표 */
plist_node_init(&c, 5);   /* prio=5 비대표 */
plist_node_init(&d, 10);  /* prio=10 대표 */
plist_node_init(&e, 20);  /* prio=20 대표 */
plist_add(&a, &head);
plist_add(&b, &head);
plist_add(&c, &head);
plist_add(&d, &head);
plist_add(&e, &head);

/* A 삭제 — 대표 노드, B가 승격 */
plist_del(&a, &head);
WARN_ON(list_empty(&b.prio_list));  /* B가 prio_list에 연결됨 확인 */
WARN_ON(plist_first(&head)->prio != 5);  /* 첫 노드는 여전히 prio=5 */

/* B도 삭제 — 대표 노드, C가 승격 */
plist_del(&b, &head);
WARN_ON(list_empty(&c.prio_list));  /* C가 새 대표 */

/* C 삭제 — 그룹의 마지막 노드, prio_list에서도 제거 */
plist_del(&c, &head);
WARN_ON(plist_first(&head)->prio != 10);  /* 이제 D(10)가 첫 노드 */

RT-Mutex PI 체인

우선순위 역전(Priority Inversion)은 높은 우선순위 태스크가 낮은 우선순위 태스크가 보유한 잠금을 기다릴 때 발생합니다. RT-Mutex는 우선순위 상속(Priority Inheritance, PI) 프로토콜로 이를 해결하며, plist는 이 메커니즘의 핵심 자료구조로 pi_waiters 관리에 사용됩니다.

/* PI 체인에서 plist를 사용하는 유효 우선순위 계산 (개념적 코드) */
static int effective_prio(struct task_struct *task)
{
    int prio = task->normal_prio;  /* 기본 우선순위 */

    /* pi_waiters가 비어 있지 않으면 최고 대기자 확인 */
    if (!plist_head_empty(&task->pi_waiters)) {
        int pi_prio = plist_first(&task->pi_waiters)->prio;
        if (pi_prio < prio)   /* 낮은 값 = 높은 우선순위 */
            prio = pi_prio;   /* 우선순위 부스트 */
    }
    return prio;
}

/* PI 전파 시 plist 재정렬 — rt_mutex_adjust_prio_chain 핵심 로직 */
static int rt_mutex_adjust_prio_chain(struct task_struct *task, ...)
{
    /* 체인을 따라가며 각 단계에서: */
    while (task) {
        struct rt_mutex *lock = task->pi_blocked_on;
        struct task_struct *owner;

        if (!lock)
            break;  /* 체인 종료 */

        owner = rt_mutex_owner(lock);

        /* 대기자의 우선순위가 변경되었으므로 plist 재정렬 */
        plist_del(&waiter->list_entry, &lock->wait_list);
        waiter->list_entry.prio = task->prio;
        plist_add(&waiter->list_entry, &lock->wait_list);

        /* owner의 pi_waiters도 재정렬 */
        plist_del(&waiter->pi_list_entry, &owner->pi_waiters);
        waiter->pi_list_entry.prio = task->prio;
        plist_add(&waiter->pi_list_entry, &owner->pi_waiters);

        /* owner의 유효 우선순위 업데이트 */
        __rt_mutex_adjust_prio(owner);

        /* 체인의 다음 단계로 */
        task = owner;
    }
    return 0;
}

/* PI 관련 plist 검증 모듈 */
static void test_pi_plist(void)
{
    PLIST_HEAD(pi_waiters);
    struct plist_node w1, w2, w3;

    /* 대기자 3개: prio 50, 10, 30 */
    plist_node_init(&w1, 50);
    plist_node_init(&w2, 10);
    plist_node_init(&w3, 30);
    plist_add(&w1, &pi_waiters);
    plist_add(&w2, &pi_waiters);
    plist_add(&w3, &pi_waiters);

    /* plist_first = w2(10) → 유효 prio = min(기본, 10) */
    pr_info("highest waiter prio: %d\n",
            plist_first(&pi_waiters)->prio);  /* 10 */

    /* w2의 prio 변경: 10 → 60 (우선순위 하락) */
    plist_del(&w2, &pi_waiters);
    plist_node_init(&w2, 60);
    plist_add(&w2, &pi_waiters);

    /* 새로운 plist_first = w3(30) */
    pr_info("after reprio: %d\n",
            plist_first(&pi_waiters)->prio);  /* 30 */
}

PM QoS 상세

PM QoS(Power Management Quality of Service)는 장치 드라이버와 사용자 공간이 전력 관리에 대한 레이턴시 제약(Latency Constraint)을 등록하는 프레임워크입니다. cpu_dma_latency가 대표적인 PM QoS 매개변수이며, 등록된 모든 제약 중 최소값(가장 엄격한 제약)을 plist_first()로 O(1)에 조회합니다.

/* kernel/power/qos.c — PM QoS plist 핵심 구조 */
struct pm_qos_constraints {
    struct plist_head list;       /* 모든 request의 plist */
    s32              target_value; /* 현재 적용 중인 값 */
    s32              default_value;
    s32              no_constraint_value;
    enum pm_qos_type type;        /* MIN, MAX, SUM */
    struct blocking_notifier_head *notifiers;
};

/* pm_qos_update_target — plist 갱신 후 notifier 호출 */
static int pm_qos_update_target(
    struct pm_qos_constraints *c,
    struct plist_node *node,
    enum pm_qos_req_action action,
    s32 value)
{
    s32 prev_value, curr_value;

    prev_value = pm_qos_get_value(c);  /* 갱신 전 값 */

    switch (action) {
    case PM_QOS_ADD_REQ:
        plist_add(node, &c->list);
        break;
    case PM_QOS_UPDATE_REQ:
        plist_del(node, &c->list);
        node->prio = value;
        plist_add(node, &c->list);
        break;
    case PM_QOS_REMOVE_REQ:
        plist_del(node, &c->list);
        break;
    }

    curr_value = pm_qos_get_value(c);  /* 갱신 후 값 */

    /* 값이 변경되면 notifier 체인 호출 → cpuidle 거버너 알림 */
    if (prev_value != curr_value) {
        c->target_value = curr_value;
        blocking_notifier_call_chain(c->notifiers,
            (unsigned long)curr_value, NULL);
    }
    return prev_value != curr_value;
}

/* pm_qos_get_value — type에 따라 plist_first/last 사용 */
static s32 pm_qos_get_value(struct pm_qos_constraints *c)
{
    if (plist_head_empty(&c->list))
        return c->no_constraint_value;

    switch (c->type) {
    case PM_QOS_MIN:
        return plist_first(&c->list)->prio;  /* O(1) 최솟값 */
    case PM_QOS_MAX:
        return plist_last(&c->list)->prio;   /* O(1) 최댓값 */
    default:
        return c->no_constraint_value;
    }
}

/* 사용자 공간에서 PM QoS 제약 등록 예시 (/dev/cpu_dma_latency) */
#include <fcntl.h>
#include <stdint.h>
#include <unistd.h>

int main(void)
{
    int fd;
    int32_t latency_us = 100;  /* 100μs 제약 */

    /* fd를 열고 write하면 pm_qos_add_request() 호출
     * → plist에 prio=100인 노드 삽입
     * → plist_first()가 100이면 cpuidle 거버너에 통보 */
    fd = open("/dev/cpu_dma_latency", O_WRONLY);
    write(fd, &latency_us, sizeof(latency_us));

    /* fd가 열려 있는 동안 제약 유지 */
    sleep(60);

    /* close() → pm_qos_remove_request() → plist_del()
     * → 제약 해제 → 깊은 C-state 허용 */
    close(fd);
    return 0;
}

메모리 레이아웃

plist 자료구조의 실제 메모리 배치와 크기를 분석합니다. struct plist_node는 두 개의 list_head와 하나의 정수 필드로 구성되며, 아키텍처에 따라 패딩(Padding)이 발생할 수 있습니다.

/* plist_node 크기 분석 — pahole 출력 재현 */
struct plist_node {
    int                prio;         /*     0     4 */

    /* XXX 4 bytes hole, try to pack */

    struct list_head   prio_list;    /*     8    16 */
    struct list_head   node_list;    /*    24    16 */

    /* size: 40, cachelines: 1, members: 3 */
    /* sum members: 36, holes: 1, sum holes: 4 */
    /* last cacheline: 40 bytes */
};

struct plist_head {
    struct list_head   node_list;    /*     0    16 */

    /* size: 16, cachelines: 1, members: 1 */
    /* last cacheline: 16 bytes */
};

/* 캐시라인 분석: 64B 캐시라인 기준
 * plist_node 1개 = 40B → 1 캐시라인에 들어갑니다
 * plist_head + 첫 노드 = 16 + 40 = 56B → 1 캐시라인
 * → plist_first() 접근 시 head와 첫 노드가 같은 캐시라인에
 *   들어갈 수 있어 캐시 효율이 좋습니다 */

모듈 예제

plist의 동작을 /proc 파일 시스템을 통해 확인할 수 있는 커널 모듈 예제입니다. 모듈 로드 시 plist를 구성하고, /proc/plist_lab에서 현재 상태를 읽을 수 있습니다.

/* plist_lab.c — /proc 인터페이스 plist 실습 모듈 */
#include <linux/module.h>
#include <linux/proc_fs.h>
#include <linux/seq_file.h>
#include <linux/plist.h>
#include <linux/slab.h>

MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("plist /proc lab module");

struct task_entry {
    struct plist_node node;
    char              name[16];
    int               id;
};

static PLIST_HEAD(task_plist);
static struct task_entry entries[8];
static int nr_entries;

static const struct {
    const char *name;
    int         prio;
} init_data[] = {
    { "audio-rt",     1  },
    { "network-irq",  10 },
    { "usb-poll",     10 },
    { "display-vsync", 5 },
    { "gpu-render",   20 },
    { "disk-flush",   15 },
    { "timer-tick",   1  },
    { "idle-bg",      99 },
};

/* /proc/plist_lab 출력 */
static int plist_lab_show(struct seq_file *m, void *v)
{
    struct task_entry *entry;
    int idx = 0;

    seq_puts(m, "=== plist 상태 ===\n");
    seq_printf(m, "비어 있음: %s\n",
               plist_head_empty(&task_plist) ? "예" : "아니오");

    if (!plist_head_empty(&task_plist)) {
        struct task_entry *first, *last;
        first = plist_first_entry(&task_plist, struct task_entry, node);
        last  = plist_last_entry(&task_plist, struct task_entry, node);
        seq_printf(m, "최고 우선순위: %s (prio=%d)\n",
                   first->name, first->node.prio);
        seq_printf(m, "최저 우선순위: %s (prio=%d)\n",
                   last->name, last->node.prio);
    }

    seq_puts(m, "\n순서  이름             prio  대표\n");
    seq_puts(m, "----  ---------------  ----  ----\n");
    plist_for_each_entry(entry, &task_plist, node) {
        seq_printf(m, "%4d  %-15s  %4d  %s\n",
                   idx++, entry->name, entry->node.prio,
                   !list_empty(&entry->node.prio_list) ?
                       "YES" : "no");
    }

    seq_printf(m, "\n총 노드 수: %d\n", idx);
    seq_printf(m, "plist_node 크기: %zu bytes\n",
               sizeof(struct plist_node));
    seq_printf(m, "plist_head 크기: %zu bytes\n",
               sizeof(struct plist_head));
    seq_printf(m, "task_entry 크기: %zu bytes\n",
               sizeof(struct task_entry));
    return 0;
}

static int plist_lab_open(struct inode *inode, struct file *file)
{
    return single_open(file, plist_lab_show, NULL);
}

static const struct proc_ops plist_lab_ops = {
    .proc_open    = plist_lab_open,
    .proc_read    = seq_read,
    .proc_lseek   = seq_lseek,
    .proc_release = single_release,
};

static int __init plist_lab_init(void)
{
    int i;

    for (i = 0; i < ARRAY_SIZE(init_data); i++) {
        plist_node_init(&entries[i].node, init_data[i].prio);
        strscpy(entries[i].name, init_data[i].name,
                sizeof(entries[i].name));
        entries[i].id = i;
        plist_add(&entries[i].node, &task_plist);
    }
    nr_entries = ARRAY_SIZE(init_data);

    proc_create("plist_lab", 0444, NULL, &plist_lab_ops);
    pr_info("plist_lab: loaded with %d entries\n", nr_entries);
    return 0;
}

static void __exit plist_lab_exit(void)
{
    int i;

    remove_proc_entry("plist_lab", NULL);
    for (i = 0; i < nr_entries; i++)
        plist_del(&entries[i].node, &task_plist);
    pr_info("plist_lab: unloaded\n");
}

module_init(plist_lab_init);
module_exit(plist_lab_exit);

# 모듈 빌드 및 테스트
# Makefile:
# obj-m += plist_lab.o
# make -C /lib/modules/$(uname -r)/build M=$(pwd) modules

$ sudo insmod plist_lab.ko
$ cat /proc/plist_lab
=== plist 상태 ===
비어 있음: 아니오
최고 우선순위: audio-rt (prio=1)
최저 우선순위: idle-bg (prio=99)

순서  이름             prio  대표
----  ---------------  ----  ----
   0  audio-rt            1  YES
   1  timer-tick           1  no
   2  display-vsync        5  YES
   3  network-irq         10  YES
   4  usb-poll            10  no
   5  disk-flush          15  YES
   6  gpu-render          20  YES
   7  idle-bg             99  YES

총 노드 수: 8
plist_node 크기: 40 bytes
plist_head 크기: 16 bytes
task_entry 크기: 64 bytes

$ sudo rmmod plist_lab

커널 소스 심층 분석

plist의 핵심 구현을 소스 코드 수준에서 더 깊이 분석합니다. plist_add()의 이중 리스트 조작, plist_del()의 대표 노드 승계 메커니즘, 그리고 plist_first() / plist_last()의 O(1) 접근 원리를 추적합니다.

plist_add(): prio_list + node_list 이중 구조 유지

plist_add()의 가장 정교한 부분은 두 리스트를 동시에 올바르게 조작하는 것입니다. 삽입 시 prio_list를 순회하여 위치를 결정하고, node_list에는 FIFO 순서를 유지하며, 새로운 고유 우선순위인 경우에만 prio_list에 노드를 추가합니다.

/* lib/plist.c - plist_add 핵심 로직 상세 분석 */
void plist_add(struct plist_node *node, struct plist_head *head)
{
    struct plist_node *first, *iter, *prev = NULL;
    struct list_head *node_next = &head->node_list;

    /* [Phase 0] 디버그 검증
     * CONFIG_DEBUG_PLIST 활성화 시 6개 불변식 검증.
     * 프로덕션에서는 빈 인라인 함수로 컴파일됩니다. */
    plist_check_head(head);
    WARN_ON(!plist_node_empty(node));
    WARN_ON(!list_empty(&node->prio_list));

    /* [Phase 1] 빈 리스트 처리
     * head->node_list가 자기 자신을 가리키면 빈 리스트.
     * 첫 노드는 node_list와 prio_list 모두의 유일한 엔트리가 됩니다. */
    if (plist_head_empty(head))
        goto ins_node;

    /* [Phase 2] prio_list 순회 - O(K) 핵심 루프
     * prio_list는 각 고유 우선순위의 대표 노드만 연결합니다.
     * 이 루프에서 방문하는 노드 수 = K (고유 우선순위 수).
     *
     * 불변식: prio_list는 prio 오름차순으로 정렬되어 있으므로,
     * node->prio보다 큰 첫 대표 노드를 찾으면 그 앞이 삽입 위치입니다. */
    first = plist_first(head);

    do {
        /* 현재 대표 노드의 prio보다 새 노드의 prio가 작으면
         * (= 더 높은 우선순위이면) 이 대표 노드 앞에 삽입합니다. */
        if (node->prio < first->prio) {
            node_next = &first->node_list;
            break;
        }

        /* prev를 갱신: 나중에 같은 prio인지 판별하는 데 사용됩니다.
         * prev->prio == node->prio이면 기존 그룹에 합류 (prio_list 변경 없음).
         * prev->prio != node->prio이면 새 고유 prio (prio_list에 추가). */
        prev = first;

        /* prio_list의 다음 대표 노드로 이동.
         * prio_list.next가 자기 자신(first)의 prio_list를 가리키면
         * 순환(circular) 리스트를 한 바퀴 돈 것이므로 루프를 종료합니다. */
        iter = list_entry(first->prio_list.next,
                          struct plist_node, prio_list);

        if (&iter->prio_list == &first->prio_list)
            break;  /* 순환 완료: 리스트 끝에 삽입 */

        first = iter;
    } while (1);

ins_node:
    /* [Phase 3] node_list 삽입
     * list_add_tail()은 node_next 바로 앞에 삽입합니다.
     *
     * 같은 prio 그룹이 이미 있을 때:
     *   node_next = 다음 prio 그룹의 첫 노드의 node_list
     *   → 현재 prio 그룹의 마지막 뒤, 다음 그룹 앞에 삽입 = FIFO
     *
     * 새 prio일 때:
     *   node_next = first(다음으로 큰 prio)의 node_list
     *   → 정확히 올바른 정렬 위치에 삽입 */
    list_add_tail(&node->node_list, node_next);

    /* [Phase 4] prio_list 연결 결정
     * prev == NULL: 빈 리스트에 삽입하거나, 모든 기존 노드보다
     *               높은 우선순위 → 새로운 고유 prio → prio_list에 추가
     * prev->prio != node->prio: 새로운 고유 prio → prio_list에 추가
     * prev->prio == node->prio: 기존 그룹 합류 → prio_list 변경 없음
     *                           node의 prio_list는 self-pointing 유지 */
    if (!prev || prev->prio != node->prio) {
        list_add(&node->prio_list, &iter->prio_list);
    }

    plist_check_head(head);
}

plist_del(): 대표 노드 승계의 정확한 메커니즘

plist_del()에서 가장 미묘한 부분은 대표 노드가 삭제될 때 후속 노드에게 prio_list 연결을 정확히 이관하는 과정입니다. 이 과정에서 list_add()를 사용하여 원자적으로(Atomically) 승계합니다.

/* lib/plist.c - plist_del 대표 승계 메커니즘 상세 분석 */
void plist_del(struct plist_node *node, struct plist_head *head)
{
    plist_check_head(head);

    /* [Step 1] 대표 노드 여부 판별
     * list_empty()는 prio_list가 자기 자신을 가리키는지 확인합니다.
     * - 대표 노드: prio_list가 이전/다음 대표 노드를 가리킴 → !empty
     * - 비대표 노드: prio_list가 자기 자신을 가리킴 → empty */
    if (!list_empty(&node->prio_list)) {
        /* 대표 노드 삭제 처리 */

        /* [Step 2] 후속 노드 존재 여부 확인
         * node_list.next가 head의 node_list이면 이 노드가 리스트의
         * 마지막 노드입니다. 이 경우 승계할 후속 노드가 없습니다. */
        if (node->node_list.next != &head->node_list) {
            struct plist_node *next;

            /* node_list의 다음 노드를 plist_node로 변환 */
            next = list_entry(node->node_list.next,
                              struct plist_node, node_list);

            /* [Step 3] 같은 우선순위 승계 판별
             * 다음 노드의 prio가 현재 노드와 같으면:
             *   → 해당 그룹이 여전히 존재하므로 다음 노드가 새 대표
             *   → list_add()로 next의 prio_list를 node의 prio_list 위치에 삽입
             *
             * 다음 노드의 prio가 다르면:
             *   → 이 prio 그룹의 유일한 노드였으므로 그룹 자체가 소멸
             *   → prio_list에서 단순 제거 */
            if (next->prio == node->prio)
                list_add(&next->prio_list, &node->prio_list);
                /* list_add의 효과:
                 * next->prio_list.prev = node->prio_list.prev (이전 대표)
                 * next->prio_list.next = node->prio_list.next (다음 대표)
                 * → next가 prio_list 체인에 node의 자리를 그대로 이어받음 */
        }
        /* [Step 4] 기존 대표의 prio_list 연결 해제
         * list_del_init()은 node의 prio_list를 체인에서 제거하고,
         * self-pointing 상태로 복원합니다.
         * Step 3에서 승계가 이루어졌다면 next가 이미 체인에 들어갔으므로
         * node를 제거해도 체인이 끊어지지 않습니다. */
        list_del_init(&node->prio_list);
    }

    /* [Step 5] node_list에서 제거
     * 대표/비대표 모두 node_list에서는 단순 제거합니다.
     * list_del_init()으로 self-pointing 상태를 복원하여
     * plist_node_empty()가 올바르게 true를 반환하도록 합니다. */
    list_del_init(&node->node_list);

    plist_check_head(head);
}

plist_first() / plist_last(): O(1) 접근의 원리

plist_first()와 plist_last()가 O(1)에 동작하는 이유는 node_list가 항상 정렬 상태를 유지하기 때문입니다. head의 node_list.next는 최소 prio, node_list.prev는 최대 prio를 가진 노드를 가리킵니다.

/* include/linux/plist.h - O(1) 접근 함수 */

/* plist_first: 가장 높은 우선순위(최소 prio) 노드
 *
 * head->node_list 는 이중 연결 순환 리스트의 앵커입니다.
 * node_list.next는 항상 가장 작은 prio를 가진 노드의 node_list를 가리킵니다.
 *
 * 이 불변식은 plist_add()가 올바른 위치에 삽입하고,
 * plist_del()이 정렬을 깨뜨리지 않으므로 항상 유지됩니다.
 *
 * 메모리 접근: 1회 포인터 추적 + container_of 오프셋 계산
 * = 순수 O(1), 분기(branch) 없음 */
static inline struct plist_node *plist_first(
    const struct plist_head *head)
{
    return list_entry(head->node_list.next,
                       struct plist_node, node_list);
}

/* plist_last: 가장 낮은 우선순위(최대 prio) 노드
 *
 * node_list.prev는 항상 가장 큰 prio를 가진 노드를 가리킵니다.
 * PM QoS의 PM_QOS_MAX 타입에서 사용됩니다. */
static inline struct plist_node *plist_last(
    const struct plist_head *head)
{
    return list_entry(head->node_list.prev,
                       struct plist_node, node_list);
}

/* 활용 예: RT-Mutex에서 최고 우선순위 대기자 조회
 *
 * struct plist_node *top = plist_first(&mutex->wait_list);
 * int top_prio = top->prio;
 * // 소유자의 실행 우선순위를 top_prio로 부스트
 *
 * 이 조회가 O(1)이므로 우선순위 상속 프로토콜의
 * 실시간 보장(Real-Time Guarantee)을 충족합니다. */

PI(Priority Inheritance) Mutex에서의 plist 활용

RT-Mutex의 초기 구현에서 plist가 우선순위 상속 체인을 관리하는 방식을 소스 코드 수준에서 분석합니다. 현재 커널은 rbtree를 사용하지만, 개념적 메커니즘은 동일합니다.

/* kernel/locking/rtmutex.c (2.6.x~3.x 시절 plist 기반 구현) */

/* 태스크가 RT-Mutex를 기다릴 때:
 * 1. waiter 구조체의 plist_node를 태스크 prio로 초기화
 * 2. mutex의 wait_list(plist)에 삽입
 * 3. 소유자의 pi_waiters(plist)에도 삽입
 * 4. pi_waiters의 first가 변경되면 소유자 prio 부스트 */

static int rt_mutex_adjust_prio_chain(
    struct task_struct *task,
    int deadlock_detect,
    struct rt_mutex *orig_lock,
    struct rt_mutex_waiter *orig_waiter,
    struct task_struct *top_task)
{
    struct rt_mutex_waiter *waiter, *top_waiter;
    struct rt_mutex *lock;

    /* PI 체인을 따라 올라가며 우선순위를 전파합니다.
     * 각 단계에서 plist_first()로 최고 대기 우선순위를 O(1)에 조회합니다. */

    while (1) {
        /* task가 대기 중인 mutex의 소유자를 찾습니다 */
        lock = task->pi_blocked_on->lock;

        /* 소유자의 pi_waiters plist에서 최고 우선순위 조회 */
        if (!plist_head_empty(&task->pi_waiters)) {
            top_waiter = plist_first_entry(
                &task->pi_waiters,
                struct rt_mutex_waiter, pi_list_entry);
            /* O(1)에 최고 대기 우선순위 획득 */

            /* 소유자의 실행 우선순위를 부스트 */
            if (top_waiter->pi_list_entry.prio < task->prio)
                rt_mutex_setprio(task, top_waiter->pi_list_entry.prio);
        }

        /* 체인의 다음 단계로 이동 (소유자가 대기 중인 다른 mutex) */
        if (!task->pi_blocked_on)
            break;
        task = lock->owner;
    }
    return 0;
}

plain list_sort 접근 방식과의 비교

plist 대신 일반 list_head에 list_sort()를 사용하는 접근 방식과 비교합니다.

/* 대안 1: list_head + list_sort() (비추천) */
struct waiter_simple {
    struct list_head list;
    int              prio;
};

/* 삽입 후 매번 전체 리스트를 재정렬
 * list_sort(): 머지 소트 O(N log N)
 * → 삽입마다 O(N log N) 비용! */
list_add_tail(&waiter->list, &head);
list_sort(NULL, &head, compare_prio);

/* 대안 2: list_head + 정렬 삽입 O(N) */
struct waiter_simple *pos;
list_for_each_entry(pos, &head, list) {
    if (waiter->prio < pos->prio) {
        list_add_tail(&waiter->list, &pos->list);
        goto done;
    }
}
list_add_tail(&waiter->list, &head);
done:

/* 비교:
 * 방식         삽입      삭제   최솟값  메모리(노드)
 * list_sort   O(NlogN)  O(1)   O(1)    16 bytes
 * list 정렬삽입 O(N)     O(1)   O(1)    16 bytes
 * plist       O(K)      O(1)   O(1)    40 bytes
 *
 * N=100, K=10일 때:
 * list_sort: ~660회 비교 (삽입마다)
 * list 정렬삽입: 최대 100회 비교
 * plist: 최대 10회 비교
 *
 * plist는 메모리 24 bytes 추가로 삽입 성능 10배 향상을 달성합니다.
 * 대기열 크기가 작고 고유 우선순위가 제한적인 RT 환경에서 최적입니다. */

plist_add 삽입 위치 결정 다이어그램

plist_add가 새 노드의 삽입 위치를 결정하는 과정을 단계별로 시각화합니다. prio_list를 따라 이동하며 node->prio < first->prio 조건을 검사하는 핵심 루프의 동작을 보여줍니다.

RT-Mutex PI 체인과 plist 상세 다이어그램

RT-Mutex의 우선순위 상속(Priority Inheritance) 체인에서 plist가 어떻게 사용되는지 상세하게 시각화합니다. 복수의 mutex와 태스크가 연쇄적으로 연결된 PI 체인에서 plist의 O(1) 최고 우선순위 조회가 실시간 성능을 보장하는 원리를 보여줍니다.

구현 예제: RT-Mutex 대기자 큐

RT-Mutex의 대기자 큐를 plist로 구현하는 패턴을 소스 코드 수준에서 재현합니다. 이 예제는 커널 2.6.x~3.x 시절의 실제 RT-Mutex 구현을 단순화한 것입니다.

#include <linux/plist.h>
#include <linux/spinlock.h>
#include <linux/sched.h>

/* RT-Mutex 대기자 구조체 (plist 기반) */
struct rt_waiter {
    struct plist_node    list_entry;    /* mutex의 wait_list에 연결 */
    struct plist_node    pi_list_entry; /* 소유자의 pi_waiters에 연결 */
    struct task_struct   *task;         /* 대기 중인 태스크 */
};

/* RT-Mutex 구조체 */
struct my_rt_mutex {
    struct plist_head    wait_list;     /* 대기자 plist (prio 정렬) */
    struct task_struct   *owner;        /* 현재 소유자 */
    raw_spinlock_t       wait_lock;     /* wait_list 보호용 락 */
};

/* mutex 초기화 */
static inline void my_rt_mutex_init(struct my_rt_mutex *lock)
{
    plist_head_init(&lock->wait_list);
    lock->owner = NULL;
    raw_spin_lock_init(&lock->wait_lock);
}

/* 대기자 등록: 태스크를 mutex의 대기열에 추가 */
static void rt_mutex_enqueue_waiter(
    struct my_rt_mutex *lock,
    struct rt_waiter *waiter)
{
    /* waiter의 plist_node를 태스크의 현재 우선순위로 초기화 */
    plist_node_init(&waiter->list_entry,
                    waiter->task->prio);

    /* mutex의 wait_list에 우선순위 순서로 삽입 (O(K)) */
    plist_add(&waiter->list_entry, &lock->wait_list);

    /* 소유자의 pi_waiters에도 등록하여 PI 추적 */
    if (lock->owner) {
        plist_node_init(&waiter->pi_list_entry,
                        waiter->task->prio);
        /* 소유자의 pi_waiters plist에 삽입
         * (실제 코드에서는 task_struct 내부의 pi_waiters 사용) */
    }
}

/* 우선순위 상속: 소유자의 우선순위를 부스트 */
static void rt_mutex_adjust_prio(
    struct my_rt_mutex *lock)
{
    struct task_struct *owner = lock->owner;
    int top_prio;

    if (!owner || plist_head_empty(&lock->wait_list))
        return;

    /* O(1)에 가장 높은 대기 우선순위 조회 */
    top_prio = plist_first(&lock->wait_list)->prio;

    /* 대기자의 우선순위가 소유자보다 높으면 부스트 */
    if (top_prio < owner->prio) {
        /* 소유자의 실행 우선순위를 대기자 수준으로 상승 */
        pr_info("PI boost: task %s prio %d -> %d\n",
                owner->comm, owner->prio, top_prio);
        /* rt_mutex_setprio(owner, top_prio); */
    }
}

/* 대기자 제거: mutex 해제 또는 대기 취소 시 */
static void rt_mutex_dequeue_waiter(
    struct my_rt_mutex *lock,
    struct rt_waiter *waiter)
{
    /* wait_list에서 O(1) 삭제 */
    plist_del(&waiter->list_entry, &lock->wait_list);

    /* PI 우선순위 재조정 필요 여부 확인 */
    rt_mutex_adjust_prio(lock);
}

/* mutex unlock: 최고 우선순위 대기자를 깨움 */
static struct rt_waiter *rt_mutex_top_waiter(
    struct my_rt_mutex *lock)
{
    if (plist_head_empty(&lock->wait_list))
        return NULL;

    /* O(1)에 최고 우선순위 대기자 반환 */
    return plist_first_entry(&lock->wait_list,
                             struct rt_waiter, list_entry);
}

구현 예제: PM QoS 제약 관리

PM QoS(Power Management Quality of Service)에서 plist를 활용하여 다수의 드라이버가 등록한 전력 관리 제약 조건을 효율적으로 집계하는 패턴을 구현합니다.

#include <linux/plist.h>
#include <linux/spinlock.h>
#include <linux/notifier.h>

/* PM QoS 제약 집계 타입 */
enum qos_type {
    QOS_MIN,  /* 최솟값: 가장 엄격한 제약 (CPU latency) */
    QOS_MAX,  /* 최댓값: 가장 관대한 제약 */
};

/* 제약 관리 구조체 */
struct qos_constraints {
    struct plist_head    list;             /* 요청 plist */
    s32                  target_value;     /* 현재 활성 제약 */
    s32                  default_value;    /* 제약 없을 때 기본값 */
    enum qos_type       type;             /* 집계 방식 */
    spinlock_t           lock;
};

/* 개별 요청 구조체 */
struct qos_request {
    struct plist_node    node;             /* plist 엔트리 */
    const char           *name;            /* 요청자 이름 (디버그용) */
};

/* 제약 초기화 */
static void qos_constraints_init(
    struct qos_constraints *c,
    s32 default_val, enum qos_type type)
{
    plist_head_init(&c->list);
    c->target_value = default_val;
    c->default_value = default_val;
    c->type = type;
    spin_lock_init(&c->lock);
}

/* 현재 활성 제약 값 조회 (O(1)) */
static s32 qos_get_value(struct qos_constraints *c)
{
    if (plist_head_empty(&c->list))
        return c->default_value;

    switch (c->type) {
    case QOS_MIN:
        /* 가장 작은 값 = plist_first()->prio
         * PM QoS에서는 prio 필드에 제약 값(예: us)을 저장합니다.
         * plist가 오름차순 정렬이므로 first가 최솟값입니다. */
        return plist_first(&c->list)->prio;
    case QOS_MAX:
        /* 가장 큰 값 = plist_last()->prio */
        return plist_last(&c->list)->prio;
    }
    return c->default_value;
}

/* 제약 요청 추가 */
static void qos_add_request(
    struct qos_constraints *c,
    struct qos_request *req,
    s32 value)
{
    s32 prev_value, new_value;

    plist_node_init(&req->node, value);

    spin_lock(&c->lock);
    prev_value = qos_get_value(c);

    /* O(K) 삽입: prio=value로 정렬 위치에 삽입 */
    plist_add(&req->node, &c->list);

    new_value = qos_get_value(c);
    c->target_value = new_value;
    spin_unlock(&c->lock);

    if (prev_value != new_value) {
        pr_info("[PM QoS] %s: constraint changed %d -> %d\n",
                req->name, prev_value, new_value);
        /* 실제 커널에서는 notifier_call_chain()으로
         * idle governor 등에 변경을 알립니다. */
    }
}

/* 제약 요청 제거 */
static void qos_remove_request(
    struct qos_constraints *c,
    struct qos_request *req)
{
    s32 prev_value, new_value;

    spin_lock(&c->lock);
    prev_value = qos_get_value(c);

    /* O(1) 삭제 */
    plist_del(&req->node, &c->list);

    new_value = qos_get_value(c);
    c->target_value = new_value;
    spin_unlock(&c->lock);

    if (prev_value != new_value)
        pr_info("[PM QoS] %s removed: constraint %d -> %d\n",
                req->name, prev_value, new_value);
}

/* 제약 값 업데이트 */
static void qos_update_request(
    struct qos_constraints *c,
    struct qos_request *req,
    s32 new_value)
{
    spin_lock(&c->lock);
    if (!plist_node_empty(&req->node)) {
        /* del + reinit + add 패턴으로 위치 재조정 */
        plist_del(&req->node, &c->list);
    }
    plist_node_init(&req->node, new_value);
    plist_add(&req->node, &c->list);

    c->target_value = qos_get_value(c);
    spin_unlock(&c->lock);
}

/* 사용 예시: CPU Latency QoS */
static struct qos_constraints cpu_lat_qos;
static struct qos_request audio_req, net_req, usb_req;

static void pm_qos_example(void)
{
    /* QOS_MIN: 가장 엄격한(가장 작은) 레이턴시 제약을 활성화 */
    qos_constraints_init(&cpu_lat_qos, S32_MAX, QOS_MIN);

    /* 세 드라이버가 각각 제약 등록 */
    audio_req.name = "audio";
    qos_add_request(&cpu_lat_qos, &audio_req, 20);
    /* plist: [20(audio)], target=20 */

    net_req.name = "network";
    qos_add_request(&cpu_lat_qos, &net_req, 50);
    /* plist: [20(audio)] → [50(network)], target=20 */

    usb_req.name = "usb";
    qos_add_request(&cpu_lat_qos, &usb_req, 100);
    /* plist: [20(audio)] → [50(network)] → [100(usb)], target=20 */

    pr_info("current CPU latency target: %d us\n",
            cpu_lat_qos.target_value);
    /* 출력: 20 (가장 엄격한 오디오 제약) */

    /* 오디오 재생 종료 → 제약 해제 */
    qos_remove_request(&cpu_lat_qos, &audio_req);
    /* plist: [50(network)] → [100(usb)], target=50
     * → idle governor가 더 깊은 절전 상태 허용 */

    pr_info("after audio stop: target = %d us\n",
            cpu_lat_qos.target_value);
    /* 출력: 50 (네트워크 제약이 새 활성 제약) */

    /* 네트워크 드라이버가 제약 완화 */
    qos_update_request(&cpu_lat_qos, &net_req, 200);
    /* plist: [100(usb)] → [200(network)], target=100 */
}

참고 자료

• 커널 소스 코드
  • include/linux/plist.h — 구조체 정의, 매크로, 인라인 함수
  • lib/plist.c — plist_add, plist_del, plist_requeue 구현
  • kernel/power/qos.c — PM QoS plist 활용
  • include/linux/pm_qos.h — PM QoS 구조체와 API 선언
  • kernel/locking/rtmutex.c — RT-Mutex 대기자 관리 (rbtree 전환 후)
  • kernel/locking/rtmutex_common.h — rt_mutex_waiter 구조체
  • kernel/futex/ — Futex PI 상태 관리
  • lib/Kconfig.debug — CONFIG_DEBUG_PLIST 설정
• 커널 문서
  • Documentation/core-api/plist.rst — 커널 공식 plist API 문서
  • Documentation/power/pm_qos_interface.rst — PM QoS 인터페이스 문서
• 관련 논문
  • Sha, L., Rajkumar, R. & Lehoczky, J. P. "Priority Inheritance Protocols: An Approach to Real-Time Synchronization" (1990) — 우선순위 상속 이론
  • Perez-Gonzalez, I. "Priority-Sorted Lists for the Linux Kernel" (2006) — plist 설계 원문
• 관련 커밋
  • 77ba89c5cf2e "plist: Remove the need for plist_head_init()" — plist_head 구조 단순화
  • fb00aca47440 "rtmutex: Turn the plist into an rb-tree" — RT-Mutex plist→rbtree 전환
  • d209d74d52a5 "futex: Add PI futex support" — PI futex 도입 (plist 최초 활용)

관련 문서

plist와 관련된 다른 주제를 더 깊이 이해하고 싶다면 다음 문서를 참고하세요.

• Linked List — plist의 기반인 struct list_head 이중 연결 리스트
• Red-Black Tree — plist를 대체한 RT-Mutex의 현재 자료구조
• Min-Heap — 배열 기반 우선순위 큐, perf_event/hrtimer 활용
• RT Mutex — 우선순위 상속 프로토콜과 대기자 관리
• Futex — 유저 공간 동기화와 PI futex
• 동기화 기법 — 전체 동기화 프리미티브 비교
• Real-Time Linux — PREEMPT_RT와 우선순위 관리
• 스케줄러 — 태스크 우선순위와 스케줄링 정책