sbitmap (Scalable Bitmap)

Linux 커널의 확장 가능 비트맵(Scalable Bitmap) 자료구조인 sbitmap을 심층 분석합니다. lib/sbitmap.c와 include/linux/sbitmap.h에 정의된 NUMA-aware, per-word hint 기반 비트 할당 메커니즘을 추적하고, blk-mq 태그(Tag) 할당에서의 핵심 역할, sbitmap_queue의 wake-up 전략, I/O 스케줄러(BFQ, mq-deadline)에서의 활용, 그리고 성능 특성과 디버깅 방법까지 커널 소스 코드를 기반으로 종합적으로 다룹니다.

개요

리눅스 커널의 블록 I/O 레이어(blk-mq)에서는 각 I/O 요청(Request)에 고유한 태그(Tag) 번호를 할당해야 합니다. 이 태그는 하드웨어 큐(Hardware Queue)에서 요청을 식별하는 데 사용되며, NVMe의 경우 최대 65,535개의 태그를 지원합니다. 초기 구현에서는 단순한 비트맵(unsigned long 배열)을 사용했지만, 코어 수가 증가하면서 심각한 확장성 문제가 발생했습니다.

일반 비트맵의 확장성 문제

일반 비트맵에서 비트 하나를 설정하거나 해제하려면 해당 비트가 속한 unsigned long 워드에 대해 원자적 연산(test_and_set_bit() 등)을 수행해야 합니다. 문제는 인접한 비트들이 같은 캐시 라인에 위치하는 점입니다.

이 문제를 해결하기 위해 sbitmap은 세 가지 핵심 전략을 사용합니다.

sbitmap 구조체

sbitmap의 핵심은 세 개의 구조체로 구성됩니다. struct sbitmap_word가 개별 워드를 관리하고, struct sbitmap이 워드 배열을 관리하며, struct sbitmap_queue가 대기/wake-up 메커니즘을 추가합니다.

struct sbitmap_word

각 워드는 struct sbitmap_word로 표현되며, ____cacheline_aligned_in_smp 속성으로 별도의 캐시 라인에 배치됩니다.

/* include/linux/sbitmap.h */
struct sbitmap_word {
    unsigned long word;       /* 실제 비트맵 데이터 (atomic 연산 대상) */
    unsigned long cleared;    /* 지연 해제(lazy clear)된 비트 */
} ____cacheline_aligned_in_smp;

struct sbitmap

struct sbitmap은 워드 배열과 메타데이터를 관리하는 메인 구조체입니다.

/* include/linux/sbitmap.h */
struct sbitmap {
    unsigned int depth;           /* 전체 비트 수 (예: 태그 수) */
    unsigned int shift;           /* 워드당 비트 수 = 1 << shift */
    unsigned int map_nr;          /* 워드 개수 = DIV_ROUND_UP(depth, 1 << shift) */
    bool round_robin;             /* true면 항상 다음 워드로 전진 */
    struct sbitmap_word *map;     /* 워드 배열 (NUMA-aware 할당) */
    unsigned int __percpu *alloc_hint; /* per-CPU 할당 힌트 (워드 인덱스) */
};

struct sbitmap_queue

struct sbitmap_queue는 struct sbitmap을 래핑하여 대기/wake-up 기능을 추가합니다. blk-mq 태그 할당에서 실제로 사용하는 것은 이 구조체입니다.

/* include/linux/sbitmap.h */
struct sbq_wait_state {
    atomic_t wait_cnt;            /* 이 대기 큐에서 깨울 남은 횟수 */
    wait_queue_head_t wait;       /* 실제 대기 큐 */
} ____cacheline_aligned_in_smp;

struct sbitmap_queue {
    struct sbitmap sb;             /* 내장 sbitmap */
    unsigned int wake_batch;      /* 한 번에 깨울 비트 수 */
    atomic_t wake_index;          /* 다음에 깨울 대기 큐 인덱스 */
    struct sbq_wait_state *ws;    /* 대기 큐 배열 (SBQ_WAIT_QUEUES개) */
    atomic_t ws_active;           /* 활성 대기자 수 */
    unsigned int min_shallow_depth; /* 얕은 깊이 제한 (throttling) */
};

Per-Word Hint 메커니즘

sbitmap의 핵심 확장성 전략은 per-CPU alloc_hint입니다. 각 CPU는 자신만의 힌트 변수를 갖고, 마지막으로 비트를 할당받은 워드의 인덱스를 기억합니다.

힌트 기반 워드 선택 알고리즘

/* lib/sbitmap.c - sbitmap_get() 핵심 로직 (간략화) */
static int __sbitmap_get(struct sbitmap *sb)
{
    unsigned int hint, depth;
    int nr;

    /* 1. 현재 CPU의 힌트를 읽음 */
    hint = this_cpu_read(*sb->alloc_hint);
    if (hint >= sb->map_nr)
        hint = 0;

    /* 2. 힌트 워드부터 시작하여 모든 워드를 순회 */
    nr = __sbitmap_get_word(&sb->map[hint].word,
                           sb_word_depth(sb, hint),
                           sb->map[hint].cleared);
    if (nr != -1) {
        nr += hint << sb->shift;
        /* 3. 성공 시 힌트 업데이트 (round_robin이면 다음 워드로) */
        if (sb->round_robin)
            hint = (hint + 1) % sb->map_nr;
        this_cpu_write(*sb->alloc_hint, hint);
        return nr;
    }

    /* 4. 힌트 워드 실패 시 나머지 워드 순회 */
    for (unsigned int i = 1; i < sb->map_nr; i++) {
        unsigned int index = (hint + i) % sb->map_nr;
        nr = __sbitmap_get_word(&sb->map[index].word,
                               sb_word_depth(sb, index),
                               sb->map[index].cleared);
        if (nr != -1) {
            nr += index << sb->shift;
            this_cpu_write(*sb->alloc_hint, index);
            return nr;
        }
    }

    return -1; /* 모든 비트가 사용 중 */
}

NUMA 노드 인식

sbitmap은 초기화 시 NUMA 노드를 지정할 수 있습니다. sbitmap_init_node()는 kcalloc_node()를 사용하여 워드 배열을 지정된 NUMA 노드의 로컬 메모리에 할당합니다. 이를 통해 해당 노드의 CPU가 비트맵에 접근할 때 원격 메모리 접근(Remote Memory Access)을 피할 수 있습니다.

/* lib/sbitmap.c - 초기화 시 NUMA 노드 지정 */
int sbitmap_init_node(struct sbitmap *sb,
                      unsigned int depth,
                      int shift,
                      gfp_t flags,
                      int node)
{
    unsigned int bits_per_word;

    if (shift < 0) {
        /* 자동 shift 계산 */
        shift = ilog2(depth);
        if (ilog2(num_possible_cpus()) <= shift)
            shift -= ilog2(num_possible_cpus());
        shift = max(shift, 0);
        /* 최소 shift=0 (워드당 1비트)에서
         * 최대 shift=ilog2(BITS_PER_LONG) (워드당 64비트)까지 */
        shift = min_t(int, shift, ilog2(BITS_PER_LONG));
    }
    bits_per_word = 1U << shift;

    sb->shift = shift;
    sb->depth = depth;
    sb->map_nr = DIV_ROUND_UP(depth, bits_per_word);

    /* NUMA 노드를 지정하여 로컬 메모리에 할당 */
    sb->map = kcalloc_node(sb->map_nr,
                           sizeof(*sb->map),
                           flags, node);

    /* per-CPU 힌트도 NUMA-aware하게 할당 */
    sb->alloc_hint = alloc_percpu_gfp(unsigned int, flags);

    return 0;
}

핵심 API

sbitmap은 초기화, 할당, 해제, 조회를 위한 함수 세트를 제공합니다. 크게 저수준 sbitmap_* API와 대기 기능이 포함된 sbitmap_queue_* API로 나뉩니다.

API 일람

sbitmap_get() 상세

/* lib/sbitmap.c */
int sbitmap_get(struct sbitmap *sb)
{
    int nr;
    unsigned int hint, depth;

    if (unlikely(sb->round_robin))
        return sbitmap_get_round_robin(sb);

    hint = this_cpu_read(*sb->alloc_hint);
    depth = READ_ONCE(sb->depth);
    if (unlikely(hint >= depth)) {
        hint = 0;
        this_cpu_write(*sb->alloc_hint, hint);
    }
    nr = sbitmap_find_bit(sb, depth, hint, 0);
    return nr;
}

sbitmap_put() 상세

/* lib/sbitmap.c */
void sbitmap_put(struct sbitmap *sb, unsigned int bitnr)
{
    unsigned int word_nr = bitnr >> sb->shift;
    unsigned int word_bit = bitnr & ((1U << sb->shift) - 1);

    /* cleared 필드에 비트 설정 (word를 직접 수정하지 않음) */
    set_bit(word_bit, &sb->map[word_nr].cleared);
}

sbitmap_queue_get() 상세

/* lib/sbitmap.c */
int sbitmap_queue_get(struct sbitmap_queue *sbq,
                      struct sbq_wait_state **ws)
{
    int nr;

    /* sbitmap에서 빈 비트를 찾음 */
    nr = sbitmap_get(&sbq->sb);

    /* 실패하면 대기 큐를 반환하여 호출자가 대기할 수 있게 함 */
    if (nr == -1 && ws) {
        unsigned int wake_index = atomic_read(&sbq->wake_index);
        *ws = &sbq->ws[wake_index % SBQ_WAIT_QUEUES];
    }

    return nr;
}

비트 할당 알고리즘

비트 할당의 핵심은 __sbitmap_get_word()와 sbitmap_find_bit() 함수에 있습니다.

__sbitmap_get_word()

/* lib/sbitmap.c */
static int __sbitmap_get_word(unsigned long *word,
                              unsigned long depth,
                              unsigned int hint,
                              bool wrap)
{
    int nr;

    /* hint 위치부터 depth까지에서 0인 비트 탐색 */
    while (1) {
        nr = find_next_zero_bit(word, depth, hint);
        if (unlikely(nr >= depth)) {
            /* wrap이면 처음부터 hint까지 재탐색 */
            if (!wrap)
                return -1;
            nr = find_next_zero_bit(word, hint, 0);
            if (unlikely(nr >= hint))
                return -1;
            wrap = false;
        }

        /* 원자적으로 비트 설정 시도 */
        if (!test_and_set_bit_lock(nr, word))
            return nr;
        hint = nr + 1;
        if (hint >= depth - 1)
            hint = 0;
    }
}

sbitmap_find_bit()

sbitmap_find_bit()은 여러 워드를 순회하면서 __sbitmap_get_word()를 호출합니다. 탐색 전에 각 워드의 cleared 비트를 word에 반영하는 것이 핵심입니다.

/* lib/sbitmap.c - 간략화 */
static int sbitmap_find_bit(struct sbitmap *sb,
                            unsigned int depth,
                            unsigned int alloc_hint,
                            unsigned int shallow_depth)
{
    unsigned int i, index;

    index = SB_NR_TO_INDEX(sb, alloc_hint);

    for (i = 0; i < sb->map_nr; i++) {
        unsigned int map_idx = (index + i) % sb->map_nr;
        unsigned long cleared;
        int nr;

        /* cleared 비트를 word에 반영 (lazy clear 해소) */
        cleared = xchg(&sb->map[map_idx].cleared, 0);
        if (cleared)
            sb->map[map_idx].word &= ~cleared;

        nr = __sbitmap_get_word(&sb->map[map_idx].word,
                               min_t(unsigned int,
                                     sb_word_depth(sb, map_idx),
                                     shallow_depth ? : depth),
                               SB_NR_TO_BIT(sb, alloc_hint),
                               !shallow_depth);
        if (nr != -1) {
            nr += map_idx << sb->shift;
            this_cpu_write(*sb->alloc_hint, nr + 1);
            return nr;
        }
    }

    return -1;
}

Wake-up 메커니즘

모든 비트가 사용 중일 때 프로세스는 sbitmap_queue의 대기 큐에서 슬립합니다. 비트가 해제되면 sbitmap_queue_wake_up()이 대기자를 깨웁니다. 이 과정은 여러 최적화 기법을 사용합니다.

sbq_wait_state와 라운드로빈 대기 큐

단일 대기 큐를 사용하면 비트가 해제될 때마다 모든 대기자가 깨어나 다시 경쟁하는 thundering herd 문제가 발생합니다. sbitmap_queue는 이를 해결하기 위해 SBQ_WAIT_QUEUES(8)개의 대기 큐를 사용합니다.

/* lib/sbitmap.c */
static bool __sbq_wake_up(struct sbitmap_queue *sbq, int *nr)
{
    struct sbq_wait_state *ws;
    unsigned int wake_batch;
    int wake_index, wait_cnt;

    /* 활성 대기자가 없으면 즉시 반환 */
    if (!atomic_read(&sbq->ws_active))
        return false;

    wake_index = atomic_read(&sbq->wake_index);
    ws = &sbq->ws[wake_index % SBQ_WAIT_QUEUES];

    /* wait_cnt를 감소시켜 wake_batch에 도달했는지 확인 */
    wait_cnt = atomic_dec_return(&ws->wait_cnt);
    if (wait_cnt <= 0) {
        /* wake_batch에 도달: 이 대기 큐의 모든 대기자를 깨움 */
        if (waitqueue_active(&ws->wait))
            wake_up_nr(&ws->wait, atomic_read(&ws->wait_cnt) ? : 1);

        /* wait_cnt를 wake_batch로 리셋 */
        wake_batch = READ_ONCE(sbq->wake_batch);
        atomic_set(&ws->wait_cnt, wake_batch);

        /* 다음 대기 큐로 라운드로빈 */
        atomic_inc(&sbq->wake_index);
    }

    return true;
}

void sbitmap_queue_wake_up(struct sbitmap_queue *sbq, int nr)
{
    __sbq_wake_up(sbq, &nr);
}

wake_batch 계산

wake_batch는 sbitmap_queue_recalculate_wake_batch()에서 depth에 따라 자동 계산됩니다.

/* lib/sbitmap.c */
static void sbitmap_queue_update_wake_batch(
    struct sbitmap_queue *sbq,
    unsigned int depth)
{
    unsigned int wake_batch;

    wake_batch = SBQ_WAKE_BATCH;
    if (wake_batch > depth / SBQ_WAIT_QUEUES)
        wake_batch = max(1U, depth / SBQ_WAIT_QUEUES);

    WRITE_ONCE(sbq->wake_batch, wake_batch);
}

blk-mq 태그 할당

sbitmap의 가장 중요한 사용처는 blk-mq(Multi-Queue Block Layer)의 태그 할당입니다. 각 I/O 요청은 하드웨어 큐에 제출되기 전에 고유한 태그 번호를 받아야 하며, 이 태그 할당/해제가 sbitmap_queue를 통해 수행됩니다.

blk_mq_tags 구조체

/* block/blk-mq-tag.h */
struct blk_mq_tags {
    unsigned int nr_tags;         /* 전체 태그 수 */
    unsigned int nr_reserved_tags; /* 예약 태그 수 */

    atomic_t active_queues;       /* 활성 하드웨어 큐 수 */

    struct sbitmap_queue bitmap_tags;   /* 일반 태그 비트맵 */
    struct sbitmap_queue breserved_tags; /* 예약 태그 비트맵 */

    struct request **rqs;              /* 태그 → 요청 매핑 */
    struct request **static_rqs;       /* 정적 할당된 요청 */
    struct list_head page_list;        /* 메모리 페이지 리스트 */
};

blk_mq_get_tag() 호출 경로

/* block/blk-mq-tag.c - 간략화 */
unsigned int blk_mq_get_tag(struct blk_mq_alloc_data *data)
{
    struct blk_mq_tags *tags = blk_mq_tags_from_data(data);
    struct sbitmap_queue *bt;
    struct sbq_wait_state *ws;
    int tag;

    /* 예약 태그 요청인지 확인 */
    if (data->flags & BLK_MQ_REQ_RESERVED)
        bt = &tags->breserved_tags;
    else
        bt = &tags->bitmap_tags;

    /* sbitmap_queue에서 태그 할당 시도 */
    tag = __sbitmap_queue_get(bt);
    if (tag != -1)
        goto found;

    /* 실패 시: 대기 큐에서 슬립하며 재시도 */
    ws = bt_wait_ptr(bt, data->hctx);
    do {
        struct sbitmap_queue *bt_prev;

        prepare_to_wait_exclusive(&ws->wait,
                                  &data->wait,
                                  TASK_UNINTERRUPTIBLE);

        tag = __sbitmap_queue_get(bt);
        if (tag != -1)
            break;

        blk_mq_tag_busy(data->hctx);
        io_schedule();
    } while (1);

found:
    if (data->flags & BLK_MQ_REQ_RESERVED)
        return tag;
    return tag + tags->nr_reserved_tags;
}

blk_mq_put_tag() 해제 경로

/* block/blk-mq-tag.c */
void blk_mq_put_tag(struct blk_mq_tags *tags,
                     struct blk_mq_ctx *ctx,
                     unsigned int tag)
{
    if (!blk_mq_tag_is_reserved(tags, tag)) {
        const int real_tag = tag - tags->nr_reserved_tags;
        sbitmap_queue_clear(&tags->bitmap_tags, real_tag, ctx->cpu);
    } else {
        sbitmap_queue_clear(&tags->breserved_tags, tag, ctx->cpu);
    }
}

/* lib/sbitmap.c */
void sbitmap_queue_clear(struct sbitmap_queue *sbq,
                         unsigned int nr,
                         unsigned int cpu)
{
    /* 1. 비트 해제 (lazy clear) */
    sbitmap_deferred_clear_bit(&sbq->sb, nr);

    /* 2. 완료 CPU 기반으로 힌트 업데이트 */
    if (likely(!sbq->sb.round_robin && cpu < nr_cpu_ids))
        *per_cpu_ptr(sbq->sb.alloc_hint, cpu) = nr;

    /* 3. 대기자 깨우기 */
    sbitmap_queue_wake_up(sbq, 1);
}

I/O 스케줄러 활용

sbitmap은 blk-mq 태그 할당 외에도 I/O 스케줄러(BFQ, mq-deadline)에서 요청 depth 제어에 사용됩니다.

BFQ에서의 sbitmap

BFQ(Budget Fair Queueing) 스케줄러는 각 프로세스 그룹의 I/O 대역폭을 공정하게 분배합니다. sbitmap_queue의 min_shallow_depth 기능을 활용하여 단일 프로세스가 전체 태그를 독점하지 못하도록 제한합니다.

/* block/bfq-iosched.c - 간략화 */
static void bfq_limit_depth(blk_opf_t opf,
                             struct blk_mq_alloc_data *data)
{
    struct bfq_data *bfqd = data->q->elevator->elevator_data;
    unsigned int act_idx = bfq_actuator_index(data->q, data->cmd_flags);
    struct bfq_iocq_classes *bic = bfq_bic_lookup(data->q);

    if (bfqd->word_depths[act_idx][!!op_is_sync(opf)])
        data->shallow_depth =
            bfqd->word_depths[act_idx][!!op_is_sync(opf)];
}

mq-deadline에서의 sbitmap

mq-deadline 스케줄러는 I/O 요청의 데드라인(Deadline)을 보장하는 것이 목표입니다. 비동기(async) 쓰기가 대량으로 발생하면 동기(sync) 읽기의 태그가 부족해질 수 있으므로, shallow_depth를 통해 비동기 요청이 사용할 수 있는 최대 태그 수를 제한합니다. 이 메커니즘은 sbitmap의 sbitmap_get_shallow() API를 활용합니다.

mq-deadline의 async_depth는 sysfs를 통해 사용자가 직접 조절할 수도 있습니다.

# mq-deadline의 async_depth 확인 및 설정
$ cat /sys/block/nvme0n1/queue/iosched/async_depth
64
$ echo 32 > /sys/block/nvme0n1/queue/iosched/async_depth
# 비동기 쓰기가 사용할 수 있는 최대 태그를 32개로 제한
# → 나머지 태그는 동기 읽기에 예약됨

/* block/mq-deadline.c - 간략화 */
static void dd_limit_depth(blk_opf_t opf,
                            struct blk_mq_alloc_data *data)
{
    struct deadline_data *dd = data->q->elevator->elevator_data;

    /* 비동기 요청의 depth를 제한하여 동기 요청을 보호 */
    if (!op_is_sync(opf) && dd->async_depth)
        data->shallow_depth = dd->async_depth;
}

성능 특성

sbitmap의 성능 이점은 CPU 수가 증가할수록 극적으로 나타납니다. 핵심 메트릭은 캐시 라인 전환 횟수와 원자적 연산 경합 비율입니다.

확장성 분석

shift 값에 따른 성능 변화

shift 값은 워드당 비트 수와 워드 개수 사이의 트레이드오프를 결정합니다.

Lazy Clear의 성능 효과

Lazy clear가 없다면 sbitmap_put()에서 clear_bit_unlock()으로 word를 직접 수정해야 합니다. 이 경우 할당 CPU와 해제 CPU가 같은 캐시 라인(word 필드)을 동시에 수정하므로 경합이 발생합니다.

/* lazy clear가 없는 경우 (가상 코드) */
void sbitmap_put_no_lazy(struct sbitmap *sb, int nr)
{
    /* CPU-A에서 word를 수정 → CPU-B의 sbitmap_get과 경합! */
    clear_bit_unlock(nr & ((1U << sb->shift) - 1),
                     &sb->map[nr >> sb->shift].word);
}

/* lazy clear 사용 시 (실제 코드) */
void sbitmap_put(struct sbitmap *sb, int nr)
{
    /* CPU-A에서 cleared만 수정 → word와 별개 캐시 라인 */
    set_bit(nr & ((1U << sb->shift) - 1),
            &sb->map[nr >> sb->shift].cleared);
}

벤치마크 분석

sbitmap 도입 전후의 성능 차이를 NVMe SSD 기준으로 분석합니다. 아래 수치는 Omar Sandoval의 원래 벤치마크와 이후 커널 개발자들의 측정 결과를 종합한 것입니다.

perf를 이용한 sbitmap 경합 프로파일링

# sbitmap 관련 함수에서의 CPU 사이클 프로파일링
$ perf record -g -e cycles:pp -- fio --name=test \
    --filename=/dev/nvme0n1 --ioengine=io_uring \
    --iodepth=256 --rw=randread --bs=4k --runtime=10

$ perf report --no-children --sort=symbol | grep sbitmap
# 예상 출력:
#   0.5%  sbitmap_get
#   0.3%  sbitmap_queue_clear
#   0.1%  sbitmap_queue_wake_up
# → 전체 CPU 사용량의 1% 미만이면 sbitmap은 병목이 아님

# 캐시 미스 프로파일링 (경합 확인)
$ perf stat -e cache-misses,cache-references,instructions \
    -- fio --name=test --filename=/dev/nvme0n1 \
    --ioengine=io_uring --iodepth=256 --rw=randread \
    --bs=4k --numjobs=32 --runtime=10

# Lock contention 분석
$ perf lock record -- fio ...
$ perf lock report
# sbitmap_word.word에 대한 lock contention이 높으면
# → shift 값이 너무 커서 워드 수가 부족한 것

NUMA 효과 측정

NUMA 시스템에서 sbitmap의 로컬/원격 메모리 접근 차이를 측정하는 방법입니다.

# NUMA 토폴로지 확인
$ numactl --hardware
# node 0 cpus: 0-31
# node 1 cpus: 32-63
# node distances:
# node   0   1
#   0:  10  21
#   1:  21  10

# NVMe가 node 0에 연결된 경우
$ cat /sys/block/nvme0n1/device/numa_node
0

# node 0에서 실행 (로컬 접근)
$ numactl --cpunodebind=0 --membind=0 \
    fio --name=local --filename=/dev/nvme0n1 \
    --ioengine=io_uring --iodepth=128 --rw=randread \
    --bs=4k --numjobs=16 --runtime=10

# node 1에서 실행 (원격 접근)
$ numactl --cpunodebind=1 --membind=1 \
    fio --name=remote --filename=/dev/nvme0n1 \
    --ioengine=io_uring --iodepth=128 --rw=randread \
    --bs=4k --numjobs=16 --runtime=10

# 예상 결과: 원격 접근 시 약 10-20% IOPS 감소
# → sbitmap이 NVMe와 같은 NUMA 노드에 할당되어 있어
#   로컬 CPU에서 접근 시 지연 시간이 최소화됨

디버깅과 모니터링

sbitmap의 현재 상태는 debugfs를 통해 확인할 수 있습니다.

debugfs 인터페이스

# 특정 블록 장치의 하드웨어 큐 태그 상태 확인
$ cat /sys/kernel/debug/block/nvme0n1/hctx0/tags

# 출력 예시:
nr_tags=128 nr_reserved_tags=1
active_queues=2
bitmap_tags:
depth=127 busy=45 cached_act=0
# sbitmap 상태
map_nr=2
alloc_hint={cpu0=34, cpu1=78, cpu2=12, cpu3=95}
word[0]: word=0x7fff_ffff_ff80_0000 cleared=0x0000_0000_0040_0000
word[1]: word=0x0000_0000_ffff_ffff cleared=0x0000_0000_0000_ff00

breserved_tags:
depth=1 busy=0

blktrace를 이용한 모니터링

# 태그 할당/해제 이벤트 추적
$ blktrace -d /dev/nvme0n1 -a issue,complete -o - | blkparse -i -

# fio를 사용한 태그 고갈 테스트
$ fio --name=tag-test --filename=/dev/nvme0n1 \
      --ioengine=io_uring --iodepth=256 \
      --rw=randread --bs=4k --numjobs=32 \
      --runtime=10 --time_based

# /proc/diskstats에서 I/O 대기 시간 확인
$ cat /proc/diskstats | grep nvme0n1
# 11번째 필드: weighted time spent doing I/Os (ms)
# 값이 급격히 증가하면 태그 대기가 원인일 수 있음

ftrace를 이용한 sbitmap 추적

# sbitmap 관련 함수 트레이싱
$ echo 'sbitmap_get' > /sys/kernel/debug/tracing/set_ftrace_filter
$ echo 'sbitmap_put' >> /sys/kernel/debug/tracing/set_ftrace_filter
$ echo 'sbitmap_queue_wake_up' >> /sys/kernel/debug/tracing/set_ftrace_filter
$ echo function > /sys/kernel/debug/tracing/current_tracer
$ echo 1 > /sys/kernel/debug/tracing/tracing_on

# 10초 후 중지
$ sleep 10
$ echo 0 > /sys/kernel/debug/tracing/tracing_on
$ cat /sys/kernel/debug/tracing/trace

커널 설정

sbitmap은 blk-mq와 함께 빌드되므로 별도의 CONFIG 옵션이 필요하지 않습니다. 다만, 관련된 설정 항목들을 알아두면 디버깅에 유용합니다.

# 현재 커널의 sbitmap 관련 설정 확인
$ grep -E '(BLK_MQ|BLOCK|SMP|NUMA|IOSCHED)' /boot/config-$(uname -r)

# sbitmap 심볼 존재 확인
$ grep sbitmap /proc/kallsyms | head -10
ffffffffa1234560 T sbitmap_init_node
ffffffffa1234680 T sbitmap_get
ffffffffa1234780 T sbitmap_put
ffffffffa1234880 T sbitmap_queue_init_node
ffffffffa1234980 T sbitmap_queue_get
ffffffffa1234a80 T sbitmap_queue_clear
ffffffffa1234b80 T sbitmap_queue_wake_up

Bitmap과 sbitmap 비교

sbitmap은 기존 비트맵(Bitmap)의 확장입니다. 두 자료구조는 목적과 사용 환경이 다릅니다.

소스 코드 분석

sbitmap_get()의 전체 경로를 커널 소스 기반으로 워크스루합니다. 이 분석은 Linux 커널 v6.x 기준입니다.

sbitmap_get() 전체 워크스루

/* === 1단계: sbitmap_get() 진입 === */
/* lib/sbitmap.c */
int sbitmap_get(struct sbitmap *sb)
{
    int nr;
    unsigned int hint, depth;

    /* round_robin 모드면 별도 경로 */
    if (unlikely(sb->round_robin))
        return sbitmap_get_round_robin(sb);

    /* per-CPU 힌트 읽기 (preemption-safe) */
    hint = this_cpu_read(*sb->alloc_hint);
    depth = READ_ONCE(sb->depth);
    if (unlikely(hint >= depth)) {
        hint = 0;
        this_cpu_write(*sb->alloc_hint, hint);
    }

    /* sbitmap_find_bit()으로 실제 비트 탐색 */
    nr = sbitmap_find_bit(sb, depth, hint, 0);
    return nr;
}

/* === 2단계: sbitmap_find_bit() === */
static int sbitmap_find_bit(struct sbitmap *sb,
                            unsigned int depth,
                            unsigned int alloc_hint,
                            unsigned int shallow_depth)
{
    unsigned int i, index;

    /* 힌트를 워드 인덱스로 변환 */
    index = SB_NR_TO_INDEX(sb, alloc_hint);

    for (i = 0; i < sb->map_nr; i++) {
        unsigned int map_idx = (index + i) % sb->map_nr;
        unsigned int nr_bits = sb_word_depth(sb, map_idx);
        unsigned long cleared;
        int nr;

        /* === 2a: lazy clear 해소 ===
         * xchg()로 cleared를 원자적으로 읽고 0으로 초기화
         * 읽은 값을 word에서 제거하여 비트 해제 완료 */
        cleared = xchg(&sb->map[map_idx].cleared, 0);
        if (cleared)
            sb->map[map_idx].word &= ~cleared;

        /* === 2b: shallow_depth 적용 ===
         * I/O 스케줄러가 제한을 설정했으면 탐색 범위 축소 */
        if (shallow_depth)
            nr_bits = min_t(unsigned int, nr_bits, shallow_depth);

        /* === 2c: 워드 내 비트 탐색 === */
        nr = __sbitmap_get_word(&sb->map[map_idx].word,
                               nr_bits,
                               (i == 0) ? SB_NR_TO_BIT(sb, alloc_hint) : 0,
                               i != 0);

        if (nr != -1) {
            /* 전체 비트 번호 계산 */
            nr += map_idx << sb->shift;
            /* per-CPU 힌트를 다음 비트로 업데이트 */
            this_cpu_write(*sb->alloc_hint, nr + 1);
            return nr;
        }
    }

    return -1;
}

/* === 3단계: __sbitmap_get_word() === */
static int __sbitmap_get_word(unsigned long *word,
                              unsigned long depth,
                              unsigned int hint,
                              bool wrap)
{
    int nr;

    while (1) {
        /* === 3a: 0인 비트 탐색 ===
         * find_next_zero_bit()는 아키텍처별 최적화:
         * x86: BSF/TZCNT, ARM64: CLZ/RBIT,
         * RISC-V: __builtin_ctzl */
        nr = find_next_zero_bit(word, depth, hint);

        if (unlikely(nr >= depth)) {
            /* hint 이후에 없으면 처음부터 재탐색 */
            if (!wrap)
                return -1;
            nr = find_next_zero_bit(word, hint, 0);
            if (unlikely(nr >= hint))
                return -1;
            wrap = false;
        }

        /* === 3b: 원자적 비트 설정 ===
         * test_and_set_bit_lock()은 acquire semantics를 포함:
         * x86: LOCK BTS
         * ARM64: LDAXR/STXR 루프
         * RISC-V: amoor.w.aq */
        if (!test_and_set_bit_lock(nr, word))
            return nr;

        /* 다른 CPU가 먼저 설정 → 다음 비트 시도 */
        hint = nr + 1;
        if (hint >= depth - 1)
            hint = 0;
    }
}

sbitmap_queue_clear() 해제 워크스루

/* === 해제 경로: sbitmap_queue_clear() === */
/* lib/sbitmap.c */
void sbitmap_queue_clear(struct sbitmap_queue *sbq,
                         unsigned int nr,
                         unsigned int cpu)
{
    /* 1. 비트를 cleared에 설정 (lazy clear) */
    sbitmap_deferred_clear_bit(&sbq->sb, nr);

    /* sbitmap_deferred_clear_bit() 내부:
     *   unsigned int word_nr = nr >> sb->shift;
     *   unsigned int word_bit = nr & ((1U << sb->shift) - 1);
     *   set_bit(word_bit, &sb->map[word_nr].cleared);
     * → word가 아닌 cleared에 비트를 설정 */

    /* 2. 완료 CPU의 힌트를 업데이트
     * round_robin이 아니면, 해제된 비트의 워드를 힌트로 설정
     * → 다음에 이 CPU가 할당할 때 방금 해제된 워드부터 탐색 */
    if (likely(!sbq->sb.round_robin && cpu < nr_cpu_ids))
        *per_cpu_ptr(sbq->sb.alloc_hint, cpu) = nr;

    /* 3. 대기자 깨우기
     * ws_active > 0일 때만 실제 wake-up 수행 */
    sbitmap_queue_wake_up(sbq, 1);

    /* sbitmap_queue_wake_up() 내부:
     *   if (!atomic_read(&sbq->ws_active)) return;
     *   → 대기자가 없으면 즉시 반환 (빠른 경로)
     *
     *   ws = &sbq->ws[wake_index % SBQ_WAIT_QUEUES];
     *   wait_cnt = atomic_dec_return(&ws->wait_cnt);
     *   if (wait_cnt <= 0) {
     *       wake_up_nr(&ws->wait, ...);
     *       atomic_set(&ws->wait_cnt, wake_batch);
     *       atomic_inc(&sbq->wake_index);
     *   } */
}

Round-Robin 모드

round_robin = true인 경우 별도의 함수 sbitmap_get_round_robin()이 호출됩니다. 이 모드에서는 per-CPU 힌트를 사용하되, 할당 성공 후 항상 다음 워드로 전진합니다.

/* lib/sbitmap.c */
static int sbitmap_get_round_robin(struct sbitmap *sb)
{
    unsigned int hint, depth;
    int nr;

    hint = this_cpu_read(*sb->alloc_hint);
    depth = READ_ONCE(sb->depth);

    if (hint >= depth)
        hint = 0;

    nr = sbitmap_find_bit(sb, depth, hint, 0);
    if (nr != -1) {
        /* 성공 시 힌트를 할당된 비트의 다음 비트로 설정
         * round_robin이므로 같은 워드를 반복하지 않음 */
        hint = nr + 1;
        if (hint >= depth)
            hint = 0;
        this_cpu_write(*sb->alloc_hint, hint);
    }

    return nr;
}

고급 내부 구현 상세

이 섹션에서는 앞서 다룬 핵심 메커니즘의 세부 구현과 엣지 케이스를 더 깊이 분석합니다.

sbitmap_deferred_clear_bit() 상세

Lazy clear의 실제 구현을 단계별로 추적합니다. cleared 필드와 word 필드 간의 동기화가 어떻게 정확성을 보장하는지 이해하는 것이 중요합니다.

/* lib/sbitmap.c */
static inline void sbitmap_deferred_clear_bit(
    struct sbitmap *sb,
    unsigned int bitnr)
{
    unsigned int word_nr = bitnr >> sb->shift;
    unsigned int word_bit = bitnr & ((1U << sb->shift) - 1);

    /* set_bit()은 원자적이므로 여러 CPU가
     * 동시에 같은 워드의 cleared에 비트를 설정할 수 있음 */
    set_bit(word_bit, &sb->map[word_nr].cleared);
}

/* sbitmap_find_bit()에서 호출되는 lazy clear 해소 */
static inline bool sbitmap_deferred_clear(
    struct sbitmap_word *map)
{
    unsigned long cleared;

    /* xchg(): cleared를 원자적으로 읽고 0으로 초기화
     * 이 시점에서 다른 CPU가 set_bit(cleared)를 호출해도
     * 그 비트는 다음 번 sbitmap_deferred_clear()에서 처리됨 */
    cleared = xchg(&map->cleared, 0);
    if (!cleared)
        return false;

    /* word에서 cleared 비트들을 한 번에 제거
     * 비원자적 연산이지만, 이 워드의 word 필드를 수정하는 것은
     * sbitmap_find_bit()를 호출한 CPU뿐이므로 안전함
     * (다른 CPU는 test_and_set_bit으로 1→1 설정만 시도) */
    map->word &= ~cleared;
    return true;
}

sb_word_depth() 헬퍼

마지막 워드는 다른 워드보다 적은 비트를 가질 수 있습니다. sb_word_depth()가 이를 처리합니다.

/* include/linux/sbitmap.h */
static inline unsigned int sb_word_depth(
    struct sbitmap *sb,
    unsigned int index)
{
    unsigned int bits_per_word = 1U << sb->shift;

    /* 마지막 워드가 아니면 전체 비트 수 반환 */
    if (index < sb->map_nr - 1)
        return bits_per_word;

    /* 마지막 워드: depth가 bits_per_word로 나누어떨어지지 않을 수 있음
     * 예: depth=200, shift=6 → 마지막 워드는 200 - 3*64 = 8비트 */
    return sb->depth - ((sb->map_nr - 1) << sb->shift);
}

/* 매크로: 비트 번호를 워드 인덱스와 워드 내 오프셋으로 변환 */
#define SB_NR_TO_INDEX(sb, bitnr) ((bitnr) >> (sb)->shift)
#define SB_NR_TO_BIT(sb, bitnr)  ((bitnr) & ((1U << (sb)->shift) - 1))

sbitmap_resize() - 동적 크기 변경

sbitmap은 런타임에 depth를 변경할 수 있습니다. 이는 blk-mq에서 사용자가 /sys/block/*/queue/nr_requests를 통해 큐 depth를 동적으로 조정하거나, SCSI 드라이버가 호스트 어댑터의 큐 깊이를 런타임에 변경할 때 사용됩니다. 중요한 점은 sbitmap_resize()가 워드 배열 자체를 재할당하지 않는다는 것입니다. 기존 배열 내에서 유효한 비트 범위만 조정하므로, 새로운 depth는 초기화 시 할당된 최대 depth를 초과할 수 없습니다.

/* lib/sbitmap.c */
void sbitmap_resize(struct sbitmap *sb, unsigned int depth)
{
    unsigned int bits_per_word = 1U << sb->shift;
    unsigned int i;

    /* 새 depth로 업데이트 */
    sb->depth = depth;
    sb->map_nr = DIV_ROUND_UP(depth, bits_per_word);

    /* 마지막 워드를 넘어서는 비트가 설정되지 않도록
     * 추가 워드들의 word를 전부 1로 설정하여 할당 불가로 표시 */
    for (i = sb->map_nr; i < sb->map_nr; i++) {
        sb->map[i].word = ~0UL;
        sb->map[i].cleared = 0;
    }
}

sbitmap_weight() 구현

/* lib/sbitmap.c */
static unsigned int __sbitmap_weight(
    const struct sbitmap *sb,
    bool set)
{
    unsigned int i, weight = 0;

    for (i = 0; i < sb->map_nr; i++) {
        const struct sbitmap_word *word = &sb->map[i];
        unsigned int depth = sb_word_depth(sb, i);

        if (set)
            /* 설정된 비트 수 (사용 중) */
            weight += bitmap_weight(&word->word, depth);
        else
            /* 해제된 비트 수 (사용 가능) */
            weight += depth - bitmap_weight(&word->word, depth);
    }

    return weight;
}

unsigned int sbitmap_weight(const struct sbitmap *sb)
{
    return __sbitmap_weight(sb, true);
}

sbitmap_any_bit_set() 빠른 검사

/* include/linux/sbitmap.h */
static inline bool sbitmap_any_bit_set(
    const struct sbitmap *sb)
{
    unsigned int i;

    for (i = 0; i < sb->map_nr; i++) {
        /* cleared를 반영하지 않은 빠른 검사
         * word에 설정된 비트가 하나라도 있으면 true */
        if (sb->map[i].word & ~sb->map[i].cleared)
            return true;
    }
    return false;
}

sbitmap_for_each_set() 반복자

사용 중인 모든 비트를 순회하는 반복자입니다. blk-mq에서 타임아웃(Timeout) 처리 시 모든 활성 태그를 검사하는 데 사용됩니다.

/* include/linux/sbitmap.h */
static inline void sbitmap_for_each_set(
    struct sbitmap *sb,
    sb_for_each_fn fn,
    void *data)
{
    unsigned int i;

    for (i = 0; i < sb->map_nr; i++) {
        struct sbitmap_word *word = &sb->map[i];
        unsigned int depth = sb_word_depth(sb, i);
        unsigned long w;

        /* cleared를 반영한 실제 사용 중 비트 */
        w = word->word & ~word->cleared;

        while (w) {
            unsigned int bit = __ffs(w);
            unsigned int nr = (i << sb->shift) + bit;

            if (!fn(nr, data))
                return;
            w &= ~(1UL << bit);
        }
    }
}

/* 사용 예: blk-mq 타임아웃 검사 */
/* block/blk-mq.c */
static void blk_mq_timeout_work(struct work_struct *work)
{
    struct request_queue *q = ...;
    struct blk_mq_hw_ctx *hctx;
    unsigned long i;

    /* 모든 하드웨어 큐의 활성 태그를 순회하여
     * 타임아웃된 요청을 찾음 */
    queue_for_each_hw_ctx(q, hctx, i) {
        sbitmap_for_each_set(
            &hctx->tags->bitmap_tags.sb,
            blk_mq_check_expired, q);
    }
}

sbitmap_queue_init_node() 전체 초기화

/* lib/sbitmap.c */
int sbitmap_queue_init_node(
    struct sbitmap_queue *sbq,
    unsigned int depth,
    int shift,
    bool round_robin,
    gfp_t flags,
    int node)
{
    int ret, i;

    /* 1. 내장 sbitmap 초기화 */
    ret = sbitmap_init_node(&sbq->sb, depth, shift,
                            flags, node,
                            round_robin, true);
    if (ret)
        return ret;

    /* 2. 대기 큐 배열 할당 (NUMA-aware) */
    sbq->ws = kzalloc_node(
        SBQ_WAIT_QUEUES * sizeof(*sbq->ws),
        flags, node);
    if (!sbq->ws) {
        sbitmap_free(&sbq->sb);
        return -ENOMEM;
    }

    /* 3. 각 대기 큐 초기화 */
    for (i = 0; i < SBQ_WAIT_QUEUES; i++)
        init_waitqueue_head(&sbq->ws[i].wait);

    /* 4. wake_batch 계산 및 설정 */
    sbitmap_queue_update_wake_batch(sbq, depth);

    /* 5. 각 대기 큐의 wait_cnt를 wake_batch로 초기화 */
    for (i = 0; i < SBQ_WAIT_QUEUES; i++)
        atomic_set(&sbq->ws[i].wait_cnt, sbq->wake_batch);

    /* 6. 기타 필드 초기화 */
    atomic_set(&sbq->wake_index, 0);
    atomic_set(&sbq->ws_active, 0);
    sbq->min_shallow_depth = UINT_MAX;

    return 0;
}

동시성과 메모리 순서

sbitmap의 정확성은 원자적 연산과 적절한 메모리 순서 보장에 의존합니다. 이 섹션에서는 주요 동시성 시나리오를 분석합니다.

동시 get/put 시나리오

메모리 순서 보장

아키텍처별 원자적 비트 연산

x86: LOCK BTS (test_and_set_bit_lock)

lock bts %eax, (%rdi) — 원자적 비트 테스트+설정을 수행합니다. x86 TSO 모델에 의해 자동으로 acquire semantics가 포함됩니다.

ARM64: LDAXR/STXR 루프

ldaxr x0, [x1](exclusive load-acquire) → orr x0, x0, x2(비트 설정) → stxr w3, x0, [x1](exclusive store, 실패 시 재시도) → cbnz w3, retry

RISC-V: AMO 연산

amoor.w.aq a0, a1, (a2) — 원자적 OR + acquire를 수행합니다.

동시 get/get 시나리오

두 CPU가 같은 워드에서 동시에 비트를 할당하려는 경우입니다.

/* 시나리오: CPU 0과 CPU 1이 동시에 word[0]에서 할당 시도 */

/* CPU 0: */
nr = find_next_zero_bit(&word, 64, 0);  /* → bit 3 */
if (!test_and_set_bit_lock(3, &word))   /* 성공! */
    return 3;

/* CPU 1: */
nr = find_next_zero_bit(&word, 64, 0);  /* → bit 3 (같은 비트) */
if (!test_and_set_bit_lock(3, &word))   /* 실패! (CPU 0이 먼저 설정) */
{
    /* 다음 비트 시도 */
    hint = 4;
    nr = find_next_zero_bit(&word, 64, 4); /* → bit 7 */
    if (!test_and_set_bit_lock(7, &word))  /* 성공! */
        return 7;
}

sbitmap 발전 역사

sbitmap은 커널 v4.9에서 처음 도입된 이후 여러 차례 개선되었습니다.

버전별 성능 개선 요약

초기 설계 동기

Omar Sandoval의 초기 커밋 메시지에서 핵심 동기를 확인할 수 있습니다.

"blk-mq currently uses a set of percpu last_tag variables along with a global bitmap for tag allocation. This suffers from cache line bouncing on the bitmap and doesn't scale to large numbers of CPUs. This patch introduces sbitmap, a scalable bitmap that spreads the bits over multiple cache lines to reduce contention."

— 커밋 메시지 (v4.9, 2016)

요약하면, 기존 blk-mq는 per-CPU last_tag 변수와 전역 비트맵을 사용했으나, 비트맵의 캐시 라인 바운싱이 CPU 수 증가 시 확장성을 제한했습니다. sbitmap은 비트를 여러 캐시 라인에 분산하여 경합을 줄입니다.

Lazy Clear 도입 배경 (v4.14)

초기 sbitmap에서는 sbitmap_put()이 word를 직접 수정했습니다. 이 경우 할당 CPU와 해제 CPU가 같은 캐시 라인을 경쟁적으로 수정하는 문제가 있었습니다. cleared 필드의 도입으로 이 경합을 제거했습니다.

결과적으로 워드당 경합이 약 50% 감소했습니다 (NVMe 벤치마크 기준 15% IOPS 향상).

실전 활용 패턴

sbitmap은 blk-mq 외에도 커널 내 다양한 곳에서 활용될 수 있는 범용 자료구조입니다. 이 섹션에서는 실전 활용 패턴을 분석합니다.

NVMe 드라이버의 태그 할당 전체 흐름

/* 시나리오: fio가 NVMe SSD에 4KB 랜덤 읽기를 제출하는 전체 경로 */

/* 1. 사용자 공간: fio → io_uring → sys_io_uring_enter() */
/* 2. VFS/블록 레이어: bio 할당 → blk_mq_submit_bio() */

/* 3. 태그 할당 */
static struct request *blk_mq_get_request(
    struct request_queue *q,
    struct bio *bio,
    struct blk_mq_alloc_data *data)
{
    /* hctx 선택: bio가 제출된 CPU에 매핑된 하드웨어 큐 */
    data->hctx = blk_mq_map_queue(q, data->cmd_flags,
                                   data->ctx);

    /* I/O 스케줄러가 있으면 shallow_depth 설정 */
    if (q->elevator)
        q->elevator->type->ops.limit_depth(
            data->cmd_flags, data);

    /* sbitmap_queue에서 태그 할당 */
    data->tag = blk_mq_get_tag(data);
    /* → sbitmap_queue_get(&tags->bitmap_tags)
     * → sbitmap_get(&sbq->sb)
     * → sbitmap_find_bit()
     * → __sbitmap_get_word()
     * → test_and_set_bit_lock() */

    /* request 구조체 초기화 */
    struct request *rq = tags->static_rqs[data->tag];
    blk_mq_rq_ctx_init(data, tags, data->cmd_flags, rq);

    return rq;
}

/* 4. NVMe 드라이버에 요청 전달 */
static blk_status_t nvme_queue_rq(
    struct blk_mq_hw_ctx *hctx,
    const struct blk_mq_queue_data *bd)
{
    struct nvme_queue *nvmeq = hctx->driver_data;
    struct request *rq = bd->rq;

    /* NVMe 커맨드 생성: tag가 커맨드 ID로 사용됨 */
    struct nvme_command cmd;
    cmd.common.command_id = rq->tag;  /* sbitmap에서 할당받은 태그 */
    cmd.rw.slba = cpu_to_le64(nvme_sect_to_lba(ns, blk_rq_pos(rq)));

    /* SQ(Submission Queue)에 커맨드 기록 */
    nvme_submit_cmd(nvmeq, &cmd);
    return BLK_STS_OK;
}

/* 5. NVMe 완료 인터럽트 처리 */
static irqreturn_t nvme_irq(int irq, void *data)
{
    struct nvme_queue *nvmeq = data;
    struct nvme_completion cqe;

    /* CQ(Completion Queue)에서 완료 엔트리 읽기 */
    while (nvme_read_cqe(nvmeq, &cqe)) {
        u16 command_id = cqe.command_id;

        /* command_id = sbitmap 태그 → request 찾기 */
        struct request *rq = blk_mq_tag_to_rq(
            nvmeq->tags, command_id);

        /* 요청 완료 처리 */
        blk_mq_end_request(rq, nvme_error_status(cqe.status));
        /* → blk_mq_put_tag()
         * → sbitmap_queue_clear(&tags->bitmap_tags, tag, cpu)
         * → sbitmap_deferred_clear_bit() (cleared에 비트 설정)
         * → sbitmap_queue_wake_up() (대기자 깨우기) */
    }

    return IRQ_HANDLED;
}

SCSI 드라이버에서의 sbitmap

SCSI 드라이버도 blk-mq를 통해 sbitmap을 사용합니다. SCSI의 경우 호스트 어댑터(Host Bus Adapter, HBA)의 큐 depth에 따라 태그 수가 결정됩니다.

/* drivers/scsi/scsi_lib.c - SCSI blk-mq 설정 */
static int scsi_mq_setup_tags(struct Scsi_Host *shost)
{
    unsigned int cmd_size;
    struct blk_mq_tag_set *tag_set = &shost->tag_set;

    tag_set->ops = &scsi_mq_ops;
    tag_set->nr_hw_queues = shost->nr_hw_queues ? : 1;
    tag_set->nr_maps = shost->nr_maps ? : 1;
    tag_set->queue_depth = shost->can_queue;
    /* can_queue = HBA의 최대 동시 명령 수
     * 예: megaraid_sas = 1024, hpsa = 512 */
    tag_set->cmd_size = cmd_size;
    tag_set->numa_node = shost->numa_node;
    /* NUMA 노드: HBA가 연결된 PCI 버스의 NUMA 노드
     * → sbitmap이 이 노드의 로컬 메모리에 할당됨 */
    tag_set->flags = BLK_MQ_F_SHOULD_MERGE;

    return blk_mq_alloc_tag_set(tag_set);
    /* 내부에서 sbitmap_queue_init_node() 호출 */
}

Writeback Throttling과 sbitmap

CONFIG_BLK_WBT(Write Back Throttling)가 활성화된 경우, 커널은 쓰기 요청의 지연 시간을 모니터링하여 동적으로 쓰기 깊이를 조절합니다. 이 메커니즘은 sbitmap_queue의 min_shallow_depth를 활용하여 쓰기 요청이 전체 태그 풀을 독점하지 않도록 합니다. WBT는 읽기 지연 시간(read latency)이 증가하면 쓰기 depth를 줄이고, 지연 시간이 정상으로 돌아오면 점진적으로 늘립니다. 이 과정에서 sbitmap_queue_min_shallow_depth()가 반복적으로 호출되어 wake_batch도 함께 재계산됩니다.

/* block/blk-wbt.c - writeback throttling */
static void wbt_set_min_lat(struct request_queue *q)
{
    struct rq_qos *rqos = wbt_rq_qos(q);
    struct rq_wb *rwb = RQWB(rqos);

    /* 쓰기 요청의 depth를 동적으로 조절하여
     * 읽기 지연 시간을 보호 */
    if (rwb->min_lat_nsec) {
        /* sbitmap_queue의 min_shallow_depth를 설정하여
         * 쓰기 요청이 사용할 수 있는 최대 태그 수를 제한 */
        sbitmap_queue_min_shallow_depth(
            &q->tag_set->bitmap_tags,
            rwb->wb_normal);
    }
}

주의사항과 흔한 실수

sbitmap을 사용하거나 디버깅할 때 주의해야 할 사항입니다.

depth 불일치

sbitmap_queue_get()이 반환하는 태그 번호는 0부터 depth-1 범위입니다. blk-mq에서 예약 태그와 일반 태그가 별도의 sbitmap_queue를 사용하므로, 최종 태그 번호에 nr_reserved_tags 오프셋을 더해야 합니다.

/* 올바른 태그 번호 계산 */
unsigned int final_tag = sbitmap_tag + tags->nr_reserved_tags;

/* 흔한 실수: 오프셋 없이 직접 사용 */
/* rqs[sbitmap_tag] → 잘못된 request에 접근! */

/* 올바른 접근 */
struct request *rq = tags->rqs[final_tag];

shallow_depth와 wake_batch 불일치

min_shallow_depth를 설정한 후 sbitmap_queue_min_shallow_depth()를 호출하지 않으면, wake_batch가 전체 depth 기준으로 계산되어 대기자가 너무 늦게 깨어날 수 있습니다.

/* 올바른 사용법 */
sbitmap_queue_min_shallow_depth(&sbq, shallow_depth);
/* 이 함수가 내부에서 wake_batch를 shallow_depth 기준으로 재계산 */

/* 잘못된 사용법: min_shallow_depth만 직접 설정 */
sbq.min_shallow_depth = shallow_depth;
/* wake_batch가 재계산되지 않아 대기자가 불필요하게 오래 대기 */

debugfs 상태의 일관성

debugfs에서 읽은 sbitmap 상태는 스냅샷(Snapshot)이므로 읽는 도중에 변경될 수 있습니다. 특히 word와 cleared를 별도로 읽으면 불일치가 발생할 수 있습니다. 이는 디버깅 용도에서는 문제가 되지 않지만, 정확한 통계가 필요한 경우 주의해야 합니다.

/* debugfs 출력 코드 (lib/sbitmap.c) */
void sbitmap_bitmap_show(struct sbitmap *sb,
                         struct seq_file *m)
{
    unsigned int i;

    for (i = 0; i < sb->map_nr; i++) {
        unsigned long word = READ_ONCE(sb->map[i].word);
        unsigned long cleared = READ_ONCE(sb->map[i].cleared);
        /* word와 cleared를 별도로 읽으므로
         * 그 사이에 상태가 변할 수 있음
         * → busy 카운트가 실제보다 크거나 작을 수 있음 */
        unsigned long used = word & ~cleared;
        seq_printf(m, "word[%u]: word=0x%016lx cleared=0x%016lx\n",
                   i, word, cleared);
    }
}

태그 고갈 진단

sbitmap의 모든 비트가 사용 중일 때 프로세스는 대기 큐에서 슬립합니다. 이 상태가 지속되면 I/O 처리량이 급격히 떨어집니다. 태그 고갈의 원인과 진단 방법을 정리합니다.

# 태그 고갈 실시간 모니터링 스크립트
$ while true; do
    for dev in /sys/kernel/debug/block/nvme*; do
        for hctx in $dev/hctx*; do
            if [ -f "$hctx/tags" ]; then
                busy=$(grep 'busy=' $hctx/tags | awk -F= '{print $NF}')
                depth=$(grep 'depth=' $hctx/tags | head -1 | awk -F= '{print $2}' | awk '{print $1}')
                pct=$((busy * 100 / depth))
                echo "$(basename $dev)/$(basename $hctx): $busy/$depth ($pct%)"
            fi
        done
    done
    echo "---"
    sleep 1
done

Preemption과 per-CPU hint

this_cpu_read/write()는 preemption-safe하지만, 읽기와 쓰기 사이에 preemption이 발생하면 다른 CPU에서 실행될 수 있습니다. sbitmap에서는 이것이 정확성에 영향을 주지 않습니다. 힌트가 "최적이 아닌" 워드를 가리킬 수 있지만, 결과적으로 빈 비트를 찾는 것은 보장됩니다.

/* 다음 시나리오에서도 정확성이 보장됨 */
hint = this_cpu_read(*sb->alloc_hint);  /* CPU 0에서 읽음: hint=2 */
/* --- preemption: CPU 3으로 이동 --- */
nr = sbitmap_find_bit(sb, depth, hint, 0); /* CPU 3에서 실행 */
/* hint=2는 CPU 0의 최적값이지 CPU 3의 최적값은 아니지만,
 * sbitmap_find_bit()은 모든 워드를 순회하므로 빈 비트를 반드시 찾음 */
this_cpu_write(*sb->alloc_hint, nr + 1); /* CPU 3의 힌트 업데이트 */
/* CPU 0의 힌트는 여전히 2 → 다음에 CPU 0이 할당할 때 약간 비최적 */

커널 모듈에서 sbitmap 사용하기

sbitmap은 EXPORT_SYMBOL_GPL로 내보내져 있으므로 GPL 라이선스 커널 모듈에서 직접 사용할 수 있습니다.

#include <linux/module.h>
#include <linux/sbitmap.h>

static struct sbitmap_queue my_sbq;

static int __init my_init(void)
{
    int ret;

    /* 256개 비트, 자동 shift, NUMA 노드 0에 할당 */
    ret = sbitmap_queue_init_node(&my_sbq,
                                  256,     /* depth */
                                  -1,      /* shift: 자동 */
                                  false,   /* round_robin */
                                  GFP_KERNEL,
                                  0);      /* NUMA node */
    if (ret) {
        pr_err("sbitmap_queue_init_node failed: %d\n", ret);
        return ret;
    }

    pr_info("sbitmap: depth=%u, shift=%u, map_nr=%u\n",
            my_sbq.sb.depth, my_sbq.sb.shift, my_sbq.sb.map_nr);

    /* 비트 할당 테스트 */
    int tag = sbitmap_queue_get(&my_sbq, NULL);
    if (tag >= 0) {
        pr_info("allocated tag: %d\n", tag);
        /* 사용 후 해제 */
        sbitmap_queue_clear(&my_sbq, tag, raw_smp_processor_id());
    }

    return 0;
}

static void __exit my_exit(void)
{
    sbitmap_queue_free(&my_sbq);
    pr_info("sbitmap freed\n");
}

module_init(my_init);
module_exit(my_exit);
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("sbitmap usage example");

배치 할당 패턴

여러 태그를 한 번에 할당해야 하는 경우의 패턴입니다. sbitmap은 단일 비트 할당 API만 제공하므로, 반복 호출이 필요합니다.

/* 여러 태그를 한 번에 할당하는 유틸리티 함수 */
static int batch_alloc_tags(struct sbitmap_queue *sbq,
                            int *tags, int nr_tags)
{
    int i, allocated = 0;

    for (i = 0; i < nr_tags; i++) {
        tags[i] = sbitmap_queue_get(sbq, NULL);
        if (tags[i] < 0)
            break;
        allocated++;
    }

    /* 부분 실패 시 이미 할당된 태그를 모두 반환 */
    if (allocated < nr_tags) {
        for (i = 0; i < allocated; i++)
            sbitmap_queue_clear(sbq, tags[i],
                                raw_smp_processor_id());
        return -ENOSPC;
    }

    return 0;
}

/* 사용 예 */
int tags[4];
if (batch_alloc_tags(&my_sbq, tags, 4) == 0) {
    /* 4개 태그 모두 할당 성공 */
    pr_info("tags: %d, %d, %d, %d\n",
            tags[0], tags[1], tags[2], tags[3]);
}

API 빠른 참조

sbitmap의 전체 공개 API를 용도별로 정리합니다.

초기화/해제 API

할당/해제 API

조회/순회 API

대기/Wake-up API

sbitmap_get 전체 경로 시각화

sbitmap_get()의 비트 할당은 단순한 비트 탐색이 아니라, per-CPU 힌트 읽기 → 워드 선택 → 비트 설정 → 힌트 갱신이라는 4단계 파이프라인으로 동작합니다. 이 섹션에서는 전체 할당 경로를 단계별로 시각화하고, round-robin 모드와 일반 모드의 차이를 소스 코드 수준에서 추적합니다.

비트 할당 경로는 크게 세 가지 계층으로 나뉩니다.

1. 상위 계층: sbitmap_get() / sbitmap_get_round_robin() — 모드 선택과 hint 관리를 담당합니다.
2. 중간 계층: sbitmap_find_bit() — 워드 순회와 wrap-around 로직을 처리합니다.
3. 하위 계층: __sbitmap_get_word() — 실제 원자적 비트 조작을 수행합니다. lazy clear 반영, 빈 비트 탐색, test_and_set_bit()이 이 함수 안에서 이루어집니다.

각 계층이 분리되어 있으므로, 상위 계층에서 모드(일반/round-robin)에 따른 정책을 변경하더라도 하위 계층의 원자적 비트 조작 코드는 변경할 필요가 없습니다. 이 모듈화된 설계가 sbitmap의 유지보수성을 높이는 핵심 요인입니다.

할당 경로 플로우차트

다음 다이어그램은 sbitmap_get()이 호출된 시점부터 비트 번호를 반환하거나 -1을 반환할 때까지의 전체 흐름을 보여줍니다. 플로우차트의 각 단계는 위에서 설명한 세 계층에 대응합니다.

플로우차트에서 핵심적인 분기점은 두 곳입니다. 첫 번째는 round_robin 모드 여부로, sbitmap_queue가 설정하는 블록 I/O 태그 할당에서는 항상 round-robin이 활성화되어 있습니다. 두 번째는 빈 비트 발견 여부로, 모든 워드를 순회한 후에도 빈 비트가 없으면 -1을 반환합니다.

반환값 -1은 "비트맵이 가득 찼음"을 의미하며, sbitmap_queue_get()을 통해 호출된 경우 호출자(blk-mq)가 대기 큐에 등록하고 io_schedule()을 호출하여 잠들게 됩니다. 이 대기 경로는 다음 섹션(Wake-up 메커니즘 상세)에서 자세히 다룹니다.

일반 모드 vs. round-robin 모드

일반 모드와 round-robin 모드의 핵심 차이는 힌트 갱신 시점에 있습니다.

/* lib/sbitmap.c - 일반 모드: 같은 워드에서 연속 할당 */
static int sbitmap_find_bit(struct sbitmap *sb,
                            unsigned int depth,
                            unsigned int index,
                            unsigned int alloc_hint)
{
    unsigned int i;
    int nr = -1;

    for (i = 0; i < sb->map_nr; i++) {
        nr = __sbitmap_get_word(
                &sb->map[index].word,
                min_t(unsigned int,
                      sb->map[index].depth,
                      depth),
                sb->map[index].cleared);

        if (nr != -1) {
            nr += index << sb->shift;
            /* 일반 모드: 같은 워드에 hint 유지 */
            this_cpu_write(*sb->alloc_hint, index);
            break;
        }
        /* 다음 워드로 진행 */
        index = (index + 1) % sb->map_nr;
    }

    return nr;
}

/* lib/sbitmap.c - round-robin 모드: 워드를 순환하며 분산 */
static int sbitmap_get_round_robin(struct sbitmap *sb)
{
    unsigned int hint, depth;
    int nr;

    hint = this_cpu_read(*sb->alloc_hint);
    depth = READ_ONCE(sb->depth);

    if (unlikely(hint >= depth))
        hint = 0;

    /* 첫 탐색: wrap=false */
    nr = sbitmap_find_bit(sb, depth, hint, 0);

    if (nr == -1) {
        /* 두 번째 탐색: 처음부터 hint까지 다시 탐색 */
        nr = sbitmap_find_bit(sb, depth, 0, hint);
    }

    if (nr != -1) {
        /* round-robin: hint를 찾은 비트 다음 위치로 전진 */
        hint = nr + 1;
        if (hint >= depth)
            hint = 0;
        this_cpu_write(*sb->alloc_hint, hint);
    }

    return nr;
}

할당 모드별 성능 영향

두 모드의 선택은 워크로드 특성에 따라 성능에 큰 영향을 미칩니다. 다음은 각 모드의 적합한 시나리오를 정리합니다.

blk-mq에서 sbitmap_queue를 초기화할 때 round_robin이 true로 설정되는 이유는, 블록 I/O 환경에서 수십~수백 개의 CPU가 동시에 태그를 할당/반환하기 때문입니다. 일반 모드에서는 이런 경우 특정 워드의 캐시 라인이 과열(hotspot)되어 test_and_set_bit()의 CAS 재시도가 급증할 수 있습니다.

Lazy Clear 타이밍과 데이터 흐름

sbitmap의 독특한 특성 중 하나는 비트 해제(sbitmap_put)와 실제 워드 반영이 분리되어 있는 점입니다. 이 lazy clear 메커니즘의 타이밍을 정리하면 다음과 같습니다.

1. 해제 시점 (CPU-B에서): sbitmap_put(sb, bitnr)이 호출되면 set_bit(bit, &map[word].cleared)만 수행합니다. word 필드는 건드리지 않습니다.
2. 반영 시점 (CPU-A에서, 다음 할당 시): __sbitmap_get_word()가 호출될 때, old = xchg(&map[word].cleared, 0)으로 cleared 필드를 원자적으로 읽고 0으로 초기화합니다. 그런 다음 word &= ~old로 실제 비트를 해제합니다.
3. 배치 효과: 여러 비트가 cleared에 누적된 상태에서 한 번의 xchg로 모두 반영됩니다. 예를 들어, CPU-B, CPU-C, CPU-D가 각각 비트 3, 7, 15를 해제하면 cleared = 0x8088이 되고, CPU-A의 다음 할당 시 한 번에 3개 비트가 해제됩니다.

이 설계의 핵심 장점은 할당 경로와 해제 경로가 서로 다른 캐시 라인에서 동작하는 것입니다. word와 cleared는 같은 sbitmap_word 구조체 안에 있지만, 할당은 주로 word를, 해제는 주로 cleared를 수정하므로 false sharing이 제한적입니다.

sbitmap_get_shallow() 변형

일반 sbitmap_get() 외에 sbitmap_get_shallow()라는 변형이 있습니다. 이 함수는 depth를 인위적으로 제한하여 할당을 수행합니다.

sbitmap_get_shallow(sb, shallow_depth)는 각 워드에서 shallow_depth개의 비트만 사용할 수 있도록 제한합니다. 예를 들어, 워드당 16비트(shift=4)인 sbitmap에서 shallow_depth=8로 호출하면, 각 워드의 하위 8비트만 할당 대상이 됩니다. 이 메커니즘은 I/O 스케줄러의 throttling에 핵심적으로 사용됩니다.

• BFQ 스케줄러: bfq_limit_depth() 콜백에서 shallow_depth를 설정하여, 특정 프로세스 그룹이 전체 태그를 독점하지 못하도록 합니다.
• mq-deadline 스케줄러: 읽기와 쓰기에 서로 다른 shallow_depth를 적용하여, 쓰기가 읽기 태그를 고갈시키는 것을 방지합니다.
• WBT(Writeback Throttling): 배경 쓰기(writeback)의 I/O 대역폭을 제한하기 위해 shallow_depth를 동적으로 조정합니다.

sbitmap_get_shallow()의 호출 빈도는 일반 sbitmap_get()과 동일한 O(1) 경로를 따르므로, throttling 적용 시에도 성능 오버헤드가 거의 없습니다. 단, shallow_depth가 매우 작으면 사용 가능한 비트가 줄어들어 태그 부족이 더 빈번하게 발생하고, 이로 인한 io_schedule() 대기가 증가할 수 있습니다.

CAS 재시도 분석

__sbitmap_get_word() 내부의 test_and_set_bit()은 CAS(Compare-And-Swap) 루프로 구현됩니다. 여러 CPU가 같은 워드에 동시 접근하면 CAS 재시도가 발생합니다. 재시도 확률은 다음 요인에 의해 결정됩니다.

sbitmap의 per-CPU hint와 round-robin 모드는 이 CAS 재시도를 최소화하도록 설계되어 있습니다. 힌트가 각 CPU를 서로 다른 워드로 유도하므로, 이상적인 경우(CPU 수 ≤ 워드 수) CAS 재시도 확률이 거의 0에 수렴합니다. 실제 커널에서 bpftrace를 사용하여 CAS 재시도 횟수를 측정할 수 있습니다.

최악의 경우(모든 CPU가 같은 워드에 동시 접근)에도 CAS 재시도는 유한하게 보장됩니다. test_and_set_bit()은 lock-free 연산이므로 데드락이 발생하지 않으며, 워드의 비트 수가 유한하므로(최대 64) 최대 64번의 재시도 안에 반드시 빈 비트를 찾거나 실패를 확정합니다. 다만, 이런 최악의 경우는 per-CPU hint가 제대로 동작하지 않는 극단적인 상황(예: CPU 핫플러그 직후 모든 hint가 0으로 리셋된 순간)에서만 발생합니다.

또한 __sbitmap_get_word() 내부에서 find_first_zero_bit()은 하드웨어의 비트 스캔 명령(x86의 BSF/TZCNT, ARM64의 CLZ)을 사용하여 O(1)에 빈 비트 위치를 찾습니다. 이 때문에 소프트웨어 루프 없이 빈 비트 탐색이 완료되며, CAS 재시도만이 유일한 반복 요인입니다.

Wake-up 메커니즘 상세

sbitmap_queue의 wake-up 메커니즘은 단순한 대기/통지가 아니라, 라운드 로빈 방식의 대기 큐 선택과 배치(batch) 기반 깨우기를 결합한 정교한 시스템입니다. 이 섹션에서는 wake_index의 순환, wake_batch의 계산 원리, 그리고 thundering herd 방지 전략을 심층 분석합니다.

wake-up 메커니즘이 중요한 이유는 다음과 같습니다. 높은 I/O 부하에서 태그가 부족하면, 수십~수백 개의 프로세스가 동시에 태그를 대기할 수 있습니다. 이 상황에서 비트가 해제될 때마다 모든 대기자를 깨우면(thundering herd), 대부분의 프로세스가 태그를 얻지 못하고 다시 잠들어야 합니다. 이 불필요한 컨텍스트 스위치가 시스템 성능을 크게 저하시킵니다.

sbitmap_queue의 8개 대기 큐 + 배치 깨우기 설계는 이 문제를 정교하게 해결합니다. 대기자를 8개 큐에 분산시키고, 한 번에 하나의 큐에서만 제한된 수의 대기자를 깨움으로써 컨텍스트 스위치 비용을 최소화합니다.

sbq_wait_state 라운드 로빈

sbitmap_queue는 SBQ_WAIT_QUEUES(기본값 8)개의 대기 큐(sbq_wait_state)를 갖습니다. 비트를 해제할 때 모든 대기자를 한꺼번에 깨우는 대신, 현재 wake_index가 가리키는 하나의 대기 큐에서만 제한된 수의 대기자를 깨웁니다.

wake_batch 계산과 동작

wake_batch는 한 번에 깨울 대기자의 수를 제한합니다. 이 값은 sbitmap_queue 초기화 시 전체 깊이(depth)와 대기 큐 수를 기반으로 계산됩니다.

/* lib/sbitmap.c - sbitmap_queue_wake_up() 핵심 로직 */
void sbitmap_queue_wake_up(struct sbitmap_queue *sbq, int nr)
{
    int i, wake_index;

    if (!atomic_read(&sbq->ws_active))
        return;  /* 대기자가 없으면 즉시 반환 */

    wake_index = atomic_read(&sbq->wake_index);

    for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
        struct sbq_wait_state *ws =
            &sbq->ws[wake_index % SBQ_WAIT_QUEUES];

        /* wait_cnt를 nr만큼 감소 */
        if (atomic_sub_return(nr, &ws->wait_cnt) > 0)
            return;  /* 아직 batch에 도달하지 않음 */

        /* wait_cnt가 0 이하: 배치 완료 → 깨우기 */
        atomic_set(&ws->wait_cnt, sbq->wake_batch);

        /* wake_index를 다음 대기 큐로 전진 */
        wake_index = (wake_index + 1) % SBQ_WAIT_QUEUES;
        atomic_set(&sbq->wake_index, wake_index);

        /* 현재 큐의 대기자 깨우기 */
        wake_up_nr(&ws->wait, sbq->wake_batch);
    }
}

/* lib/sbitmap.c - wake_batch 계산 로직 */
static unsigned int sbq_calc_wake_batch(struct sbitmap_queue *sbq,
                                          unsigned int depth)
{
    unsigned int wake_batch;
    unsigned int shallow_depth;

    /* shallow_depth가 설정되어 있으면 실효 깊이를 줄임 */
    shallow_depth = sbq->min_shallow_depth;
    if (shallow_depth != UINT_MAX)
        depth = min(depth, shallow_depth);

    /* 기본 계산: depth / SBQ_WAIT_QUEUES */
    wake_batch = max(depth / SBQ_WAIT_QUEUES, 1U);

    /* 너무 큰 배치는 지연을 유발하므로 상한 제한 */
    return min(wake_batch, 4U);
}

Wake-up 순서 보장

wake-up 메커니즘에서 가장 중요한 보장은 starvation 방지입니다. 대기 큐가 8개이고 라운드 로빈으로 순환하므로, 특정 대기 큐에 등록된 프로세스가 무한히 무시되는 상황은 발생하지 않습니다.

depth가 매우 작을 때(depth <= 8) wake_batch가 1이 되어 비트를 해제할 때마다 대기자를 깨웁니다. 이 경우 배치 최적화의 효과는 줄어들지만, 반응성이 향상됩니다. 반대로 depth가 크더라도 상한값 4로 인해 한 번에 지나치게 많은 프로세스가 깨어나는 것을 방지합니다.

ws_active 최적화

sbq->ws_active는 현재 대기 중인 프로세스가 있는지를 나타내는 원자적 카운터입니다. 이 값이 0이면 sbitmap_queue_wake_up()은 어떤 원자적 연산도 수행하지 않고 즉시 반환합니다.

이 최적화가 중요한 이유는 다음과 같습니다. 대부분의 정상 운영 시나리오에서 태그가 부족한 경우는 드뭅니다. 즉, 비트를 해제할 때마다 sbitmap_queue_wake_up()이 호출되지만, 대기자가 없는 경우가 대부분입니다. ws_active 검사가 없다면 매번 8개의 대기 큐를 순회하면서 atomic_sub_return()을 호출해야 하므로, 불필요한 원자적 연산 비용이 발생합니다.

Wake-up 경쟁 조건과 안전성

wake-up 메커니즘에서 발생할 수 있는 경쟁 조건(race condition)과 이에 대한 커널의 방어 전략을 정리합니다.

이 경쟁 조건들은 모두 일시적 비효율(잠깐 더 깨우거나 한 번 더 순회)을 유발할 뿐, 데드락이나 데이터 손실을 일으키지 않습니다. sbitmap의 wake-up 설계는 "완벽한 동기화보다 비용이 적은 근사적 동기화"를 지향합니다.

sbitmap_queue의 대기 vs. 일반 wait_queue

sbitmap_queue의 대기 메커니즘이 일반적인 wait_queue_head_t와 어떻게 다른지 비교합니다.

sbitmap_queue의 8개 대기 큐 설계는 대기 큐의 스핀락 경합도 분산시킵니다. 일반 wait_queue_head_t에서는 프로세스를 등록/해제할 때 큐의 스핀락을 획득해야 하는데, 대기자가 많으면 이 스핀락이 병목이 될 수 있습니다. 8개 큐에 분산하면 각 큐의 스핀락 경합이 8분의 1로 줄어듭니다.

blk-mq 태그 할당 흐름

블록 I/O의 핵심 경로인 submit_bio()에서 시작하여 sbitmap을 통해 태그를 획득하고, I/O 완료 후 반환하는 전체 흐름을 추적합니다. blk-mq에서 sbitmap은 드라이버 태그(driver tag)와 스케줄러 태그(scheduler tag)라는 두 가지 용도로 사용됩니다.

태그 할당/반환 전체 흐름

blk_mq_get_tag() 코드 추적

/* block/blk-mq-tag.c - 태그 할당 핵심 경로 */
unsigned int blk_mq_get_tag(struct blk_mq_alloc_data *data)
{
    struct blk_mq_tags *tags = blk_mq_tags_from_data(data);
    struct sbitmap_queue *bt;
    struct sbq_wait_state *ws;
    int tag;

    /* 스케줄러 태그 vs 드라이버 태그 선택 */
    if (data->flags & BLK_MQ_REQ_INTERNAL)
        bt = &tags->bitmap_tags;       /* 드라이버 태그 */
    else
        bt = &tags->breserved_tags;     /* 예약 태그 */

    /* 1차 시도: 비대기(non-blocking) 할당 */
    tag = __sbitmap_queue_get(bt);
    if (tag != -1)
        return tag;

    /* 2차 시도: 대기하며 할당 */
    ws = bt_wait_ptr(bt, data->hctx);
    do {
        struct sbq_wait wait;

        sbitmap_prepare_to_wait(bt, ws, &wait,
                               TASK_UNINTERRUPTIBLE);
        tag = __sbitmap_queue_get(bt);
        if (tag != -1)
            break;

        io_schedule();  /* 태그를 받을 때까지 대기 */

        sbitmap_finish_wait(bt, ws, &wait);
        ws = bt_next_ws(bt, ws);  /* 다음 대기 큐 시도 */
    } while (1);

    sbitmap_finish_wait(bt, ws, &wait);
    return tag;
}

/* block/blk-mq-tag.c - 태그 반환 */
void blk_mq_put_tag(struct blk_mq_tags *tags,
                    struct blk_mq_ctx *ctx,
                    unsigned int tag)
{
    if (!blk_mq_tag_is_reserved(tags, tag)) {
        const int real_tag = tag - tags->nr_reserved_tags;

        /* sbitmap의 비트를 해제하고 대기자를 깨움 */
        sbitmap_queue_clear(&tags->bitmap_tags,
                           real_tag, ctx->cpu);
    } else {
        sbitmap_queue_clear(&tags->breserved_tags,
                           tag, ctx->cpu);
    }
}

태그 생명주기 요약

하나의 블록 I/O 요청이 태그를 획득하고 반환하는 전체 생명주기를 단계별로 정리합니다.

1. 요청 할당: submit_bio() → blk_mq_submit_bio() → __blk_mq_alloc_requests()에서 blk_mq_get_tag()가 호출됩니다.
2. 태그 획득: __sbitmap_queue_get()가 sbitmap에서 빈 비트를 찾아 반환합니다. 이 비트 번호가 곧 태그 번호이며, tags->rqs[tag]로 request 구조체에 접근하는 인덱스로 사용됩니다.
3. 요청 처리: 드라이버의 .queue_rq() 콜백이 호출되어 디바이스에 명령을 전달합니다. NVMe의 경우 태그 번호가 command_id로 사용됩니다.
4. 완료 통지: 디바이스가 인터럽트(MSI-X)로 완료를 통지하면, 완료 핸들러가 command_id(=태그)로 해당 request를 찾습니다.
5. 태그 반환: blk_mq_end_request() → __blk_mq_free_request() → blk_mq_put_tag() → sbitmap_queue_clear()가 호출되어 비트를 해제하고 대기 중인 프로세스를 깨웁니다.

이 전체 경로에서 sbitmap의 비트 할당/해제는 O(1)(amortized) 시간에 동작하며, lock-free 원자적 연산만을 사용하므로 스핀락 경합이 없습니다. 태그 기반 인덱싱(rqs[tag])으로 request 조회도 O(1)이어서, blk-mq 전체 경로가 확장성 있게 설계되어 있습니다.

예약 태그(Reserved Tags) 사용 패턴

blk-mq의 blk_mq_tags 구조체에는 일반 태그(bitmap_tags)와 별도로 예약 태그(breserved_tags)용 sbitmap_queue가 있습니다. 예약 태그는 다음과 같은 내부 명령에 사용됩니다.

• Flush 명령: 디바이스 캐시를 디스크에 쓰는 REQ_FLUSH 요청에 사용됩니다.
• 장치 리셋: NVMe abort, SCSI task management 등 디바이스 제어 명령에 사용됩니다.
• 내부 관리 요청: SANITIZE, FORMAT 등 드라이버 내부 관리 명령에 사용됩니다.

예약 태그의 depth는 일반적으로 매우 작습니다(NVMe의 경우 기본값 1~2). 따라서 예약 태그의 sbitmap_queue는 워드 1개로 충분하며, 경합이 발생할 확률도 낮습니다. 핵심은 예약 태그가 일반 태그와 별도의 sbitmap으로 관리되므로, 일반 I/O가 모든 태그를 사용 중이어도 내부 관리 명령은 항상 실행할 수 있는 점입니다.

태그 타임아웃과 에러 처리

blk-mq의 태그에는 타임아웃 메커니즘이 내장되어 있습니다. 요청이 할당된 태그를 반환하지 않는 상황(디바이스 응답 없음, 드라이버 버그 등)에서 sbitmap 비트가 영구히 점유되는 것을 방지합니다.

• 타임아웃 검사: blk-mq 타이머(blk_mq_timeout_work)가 주기적으로 모든 활성 태그의 요청을 순회하며, req->deadline을 초과한 요청을 탐지합니다.
• 태그 순회: blk_mq_tag_busy_iter()는 sbitmap에서 설정된 비트(=활성 태그)를 순회하며 콜백 함수를 실행합니다. 이 함수는 sbitmap_for_each_set()을 사용하여 효율적으로 활성 비트를 찾습니다.
• 타임아웃 처리: 타임아웃된 요청에 대해 드라이버의 .timeout() 콜백이 호출됩니다. 드라이버가 BLK_EH_DONE을 반환하면 요청이 완료 처리되고 태그가 반환됩니다.

sbitmap의 관점에서 중요한 것은, 타임아웃으로 인한 강제 태그 반환도 정상적인 sbitmap_queue_clear() 경로를 통과하는 점입니다. 따라서 wake-up 메커니즘이 정상적으로 동작하며, 타임아웃으로 해제된 태그를 대기 중인 프로세스가 즉시 사용할 수 있습니다.

태그 할당의 공정성 문제

sbitmap의 태그 할당은 본질적으로 공정하지 않습니다. 비대기(non-blocking) 할당이 먼저 시도되고, 실패 시에만 대기 큐에 등록되므로, 새로 도착한 요청이 대기 중인 요청보다 먼저 태그를 획득할 수 있습니다(starvation 위험). 이 문제를 완화하기 위해 커널은 다음과 같은 전략을 사용합니다.

• Batch 깨우기: wake_batch개의 비트가 해제될 때까지 기다린 후 대기자를 깨우므로, 깨어난 대기자가 태그를 획득할 확률이 높아집니다.
• Exclusive wait: prepare_to_wait_exclusive()를 사용하여, wake_up이 정확히 필요한 수의 대기자만 깨웁니다.
• I/O 스케줄러 협력: BFQ와 같은 스케줄러는 shallow_depth를 사용하여 특정 프로세스 그룹의 태그 사용량을 제한합니다. 이를 통해 한 프로세스가 모든 태그를 독점하는 것을 방지합니다.
• cfg 그룹 연계: blk-cgroup(blkcg)과의 연계를 통해 cgroup별 I/O 제한을 적용할 수 있으며, 이는 간접적으로 태그 사용량을 제어합니다.

실제 운영 환경에서 태그 공정성 문제가 두드러지는 경우는, nr_requests가 매우 작고(< 32) 동시에 많은 프로세스가 I/O를 수행하는 상황입니다. 이 경우 일부 프로세스의 I/O 지연이 급증할 수 있습니다. nr_requests를 늘리거나, BFQ 스케줄러의 shallow_depth를 활용하여 공정성을 개선할 수 있습니다.

NUMA 인식 할당

대규모 NUMA 시스템에서 sbitmap의 성능은 메모리 할당의 노드 지역성(Node Locality)에 크게 좌우됩니다. sbitmap은 구조체 자체의 NUMA 배치, per-CPU 힌트의 캐시 라인 분리, 그리고 blk-mq와의 NUMA 정렬을 통해 원격 메모리 접근(Remote Memory Access) 비용을 최소화합니다.

노드별 힌트와 캐시 라인 바운싱

2소켓 NUMA 시스템에서 sbitmap의 메모리 배치를 시각화합니다. 각 노드의 CPU가 로컬 메모리에 있는 힌트를 사용하여 캐시 라인 바운싱을 최소화하는 구조를 보여줍니다.

/* block/blk-mq.c - NUMA-aware 태그 초기화 */
static struct blk_mq_tags *
blk_mq_alloc_rq_map(struct blk_mq_tag_set *set,
                    unsigned int hctx_idx,
                    unsigned int nr_tags,
                    unsigned int reserved_tags)
{
    struct blk_mq_tags *tags;
    int node;

    /* hctx의 NUMA 노드를 가져옴 */
    node = set->map[HCTX_TYPE_DEFAULT].mq_map[hctx_idx];
    node = set->numa_node;

    tags = blk_mq_init_tags(nr_tags, reserved_tags,
                            node,  /* NUMA 노드 전달 */
                            BLK_MQ_FLAG_TO_ALLOC_POLICY(set->flags));

    /* sbitmap_queue_init_node()가 내부적으로 호출되어
     * 지정된 노드의 로컬 메모리에 비트맵 배열을 할당합니다.
     * 이로써 해당 노드의 CPU가 비트맵에 접근할 때
     * 원격 메모리 접근을 피할 수 있습니다. */
    return tags;
}

NUMA 환경 성능 영향 수치

NUMA 시스템에서 sbitmap의 성능 차이를 이해하기 위해, 메모리 접근 지연 시간의 대표적인 수치를 정리합니다.

4소켓 이상의 대규모 NUMA 시스템에서는 sbitmap_word 배열이 특정 노드에 할당되므로, 원격 노드의 CPU가 접근할 때 2-hop 지연이 발생할 수 있습니다. 이 때문에 blk-mq는 가능하면 디바이스가 연결된 NUMA 노드의 CPU에서 I/O를 처리하도록 IRQ 어피니티를 설정합니다. /proc/irq/<irq>/smp_affinity를 통해 확인할 수 있습니다.

Shared Tags의 NUMA 트레이드오프

Shared Tags 모드(BLK_MQ_F_TAG_HCTX_SHARED)에서는 모든 하드웨어 큐가 하나의 sbitmap_queue를 공유합니다. 이 모드의 NUMA 관련 트레이드오프는 다음과 같습니다.

• 장점: 태그 사용률이 높아집니다. 특정 hctx에 태그가 부족하더라도 다른 hctx의 미사용 태그를 활용할 수 있어, 전체 디바이스 처리량이 향상됩니다.
• 단점: 크로스 노드 원자적 연산이 발생합니다. Node 0의 CPU와 Node 1의 CPU가 같은 sbitmap_word에 test_and_set_bit()을 수행하면 캐시 라인 바운싱이 발생합니다.
• 완화: per-CPU hint가 각 CPU를 서로 다른 워드로 유도하므로, 실제로 같은 워드에 동시 접근하는 확률은 낮습니다. shift 값이 작을수록(워드 수가 많을수록) 분산이 잘 됩니다.

IRQ 어피니티와 sbitmap 성능

NUMA 시스템에서 sbitmap의 성능을 극대화하려면, NVMe 디바이스의 IRQ 어피니티가 올바르게 설정되어야 합니다. IRQ 어피니티는 완료 인터럽트를 처리하는 CPU를 결정하며, 이는 태그 반환(sbitmap_queue_clear)이 수행되는 CPU에 직접 영향을 미칩니다.

sbitmap_queue_clear()는 비트 해제 후 this_cpu_write(*sb->alloc_hint, word_idx)를 수행합니다. 즉, 완료 인터럽트를 처리하는 CPU의 hint가 방금 해제된 비트의 워드를 가리키게 됩니다. 이 CPU가 나중에 새로운 태그를 할당할 때 이 hint를 사용하므로, 방금 해제된 비트가 있는(따라서 빈 비트가 있을 확률이 높은) 워드부터 탐색합니다.

이 메커니즘은 "해제된 직후의 비트를 빠르게 재활용"하는 효과를 가지며, 특히 같은 CPU에서 I/O 제출과 완료가 반복되는 패턴(io_uring IOPOLL)에서 캐시 효율이 극대화됩니다.

4소켓 이상 시스템 고려사항

4소켓 이상의 대규모 NUMA 시스템에서는 추가적인 고려사항이 있습니다.

• 2-hop 접근: 4소켓 시스템에서 대각선에 위치한 노드 간의 접근은 2번의 인터커넥트 홉을 거칩니다. 지연 시간이 300ns 이상으로 증가하며, 이는 sbitmap의 원자적 연산 비용을 크게 높입니다.
• HW 큐 분리: NVMe 디바이스의 HW 큐를 NUMA 노드별로 분리하여, 각 노드의 CPU가 자신에게 가까운 HW 큐(와 그 sbitmap)만 사용하도록 설정합니다. blk_mq_map_queues()가 이 매핑을 담당합니다.
• 워드 수 최적화: CPU 수가 64개 이상이면, sbitmap의 자동 shift 계산에 의해 워드 수가 64개 이상이 됩니다. 이렇게 되면 각 CPU가 자신만의 워드를 가질 수 있어 경합이 거의 사라집니다.
• 메모리 인터리빙: 일부 시스템에서는 NUMA 인터리빙 모드(BIOS 설정)를 사용하여 메모리를 모든 노드에 균등 분배합니다. 이 경우 kcalloc_node()의 NUMA 지역성 최적화 효과가 감소하지만, 최악의 경우(2-hop) 접근 지연도 줄어듭니다.

NVMe 통합

NVMe 드라이버는 sbitmap의 가장 대표적인 소비자입니다. NVMe의 Submission Queue(SQ)와 Completion Queue(CQ)는 blk-mq의 하드웨어 큐와 1:1로 매핑되며, 각 큐의 command ID가 곧 sbitmap의 태그 번호입니다. 이 섹션에서는 NVMe I/O 경로에서 sbitmap이 어떻게 활용되는지, 그리고 멀티패스(multipath) 구성에서의 태그 관리를 분석합니다.

NVMe 사양에서 각 SQ/CQ 쌍은 최대 65,535개의 명령을 지원하지만, 실제로는 드라이버가 io_queue_depth 파라미터(기본값 1024)로 제한합니다. 이 값에서 1을 뺀 1023이 sbitmap의 depth가 됩니다(NVMe 컨트롤러가 0번을 예약하기 때문). NVMe 1.3 이후 사양에서는 여러 SQ가 하나의 CQ를 공유할 수 있지만, Linux 커널의 NVMe 드라이버는 SQ:CQ를 1:1로 매핑하며, 각 쌍이 하나의 blk-mq hctx에 대응합니다.

NVMe의 command_id는 16비트(0~65535)이지만, 실제 사용 범위는 sbitmap의 depth(기본 1023)에 의해 제한됩니다. sbitmap의 비트 번호가 곧 command_id이므로, NVMe 컨트롤러가 CQE(Completion Queue Entry)로 반환하는 command_id를 tags->rqs[command_id]로 직접 인덱싱하여 O(1)에 해당 request를 찾을 수 있습니다.

SQ/CQ와 sbitmap의 매핑

command_id와 태그 번호의 관계

/* drivers/nvme/host/pci.c - NVMe 명령 제출 */
static blk_status_t nvme_queue_rq(struct blk_mq_hw_ctx *hctx,
                                    const struct blk_mq_queue_data *bd)
{
    struct nvme_queue *nvmeq = hctx->driver_data;
    struct request *req = bd->rq;
    struct nvme_command *cmnd;

    /* blk-mq가 할당한 태그 = sbitmap 비트 번호 */
    u16 tag = req->tag;

    /* NVMe SQE의 command_id에 태그 번호를 직접 사용 */
    cmnd = &nvmeq->sq_cmds[nvmeq->sq_tail];
    cmnd->common.command_id = tag;

    /* SQ tail doorbell을 울려서 컨트롤러에 통지 */
    nvme_write_sq_db(nvmeq, bd->last);

    return BLK_STS_OK;
}

/* drivers/nvme/host/pci.c - NVMe 완료 처리 (CQ 인터럽트 핸들러) */
static inline struct request *
nvme_find_rq(struct blk_mq_tags *tags, u16 command_id)
{
    /* command_id가 곧 sbitmap 태그 번호이므로 O(1) 조회 */
    return tags->rqs[command_id];
}

static void nvme_handle_cqe(struct nvme_queue *nvmeq,
                             struct nvme_completion *cqe)
{
    struct request *req;

    /* CQE의 command_id로 request를 O(1) 조회 */
    req = nvme_find_rq(nvmeq->tags, cqe->command_id);

    /* request 완료 → blk_mq_put_tag() → sbitmap 비트 해제 */
    nvme_end_req(req, cqe->status);
}

NVMe Multipath에서의 태그 독립성

NVMe multipath 구성에서 각 경로(path)는 독립적인 blk_mq_tags를 가지므로, 경로 간에 sbitmap 태그 경합이 발생하지 않습니다. 이 구조의 핵심 특성을 정리합니다.

멀티패스 failover가 발생하면, 실패한 경로의 미완료 요청은 해당 경로의 sbitmap에서 태그가 해제됩니다. 그런 다음 요청이 다른 경로로 재제출되면서, 새 경로의 sbitmap에서 새로운 태그를 할당받습니다. 이 과정에서 두 경로의 sbitmap은 완전히 독립적으로 동작합니다.

NVMe queue_depth와 sbitmap 메모리 사용량

NVMe 디바이스의 queue_depth가 sbitmap의 메모리 사용량에 미치는 영향을 계산합니다. sbitmap_word 구조체는 word(8바이트)와 cleared(8바이트)로 구성되어 16바이트입니다.

sbitmap 자체의 메모리 사용량은 매우 적습니다. 가장 큰 비용은 sbitmap이 관리하는 request 구조체 배열(tags->rqs[])입니다. 각 struct request는 약 400~500바이트이므로, depth=1023이면 약 400KB~500KB가 필요합니다. sbitmap의 메모리(수백 바이트)는 이에 비해 무시할 수 있는 수준입니다.

io_uring과 sbitmap 태그 경로

io_uring은 비동기 I/O 인터페이스로, NVMe와 결합할 때 sbitmap 태그 할당 경로가 기존 read()/write()와 다릅니다. io_uring의 폴링 모드에서는 태그 할당과 반환이 더 효율적으로 동작합니다.

io_uring의 IORING_SETUP_IOPOLL 모드에서는 완료 인터럽트를 사용하지 않고, 프로세스가 직접 CQ를 폴링합니다. 이 경우 태그 할당(sbitmap_queue_get)과 반환(sbitmap_queue_clear)이 같은 CPU에서 발생할 확률이 높습니다. 결과적으로 per-CPU hint가 더 효과적으로 동작하고, 캐시 라인 바운싱이 최소화됩니다.

특히 io_uring의 배치 제출(SQ에 여러 SQE를 쌓은 후 한 번에 io_uring_enter()) 모드에서는, 연속된 태그 할당이 같은 CPU의 hint를 따라 효율적으로 진행됩니다. round-robin 모드에서도 같은 CPU가 연속으로 할당하면 hint가 순차적으로 전진하여 워드 간 분산이 잘 됩니다.

NVMe Passthrough와 태그

NVMe passthrough 명령(nvme_submit_user_cmd(), io_uring의 IORING_OP_URING_CMD)은 일반 블록 I/O와 다른 태그 경로를 사용합니다.

• Admin Queue: 관리 명령(Identify, Get Features 등)은 Admin SQ/CQ를 사용하며, 별도의 blk_mq_tags와 sbitmap_queue로 관리됩니다. Admin 큐의 depth는 일반적으로 32로 작습니다.
• I/O Passthrough: nvme-io character device를 통한 passthrough 명령은 일반 I/O 큐의 태그를 사용합니다. 따라서 일반 블록 I/O와 같은 sbitmap을 공유하며, 태그 경합이 발생할 수 있습니다.
• io_uring CMD: IORING_OP_URING_CMD를 통한 NVMe passthrough는 커널 6.1 이후 지원되며, 일반 블록 경로를 우회하면서도 blk-mq 태그를 사용합니다.

Passthrough 명령을 빈번하게 사용하는 환경(예: SPDK와 혼합 사용, 벤더 특정 NVMe 관리 도구)에서는 passthrough가 일반 I/O의 태그를 소비하므로, nr_requests를 넉넉하게 설정하는 것이 좋습니다.

NVMe vs. SCSI: 태그 관리 비교

NVMe와 SCSI 디바이스는 모두 blk-mq를 사용하지만, 태그 관리 방식에 차이가 있습니다. 이 차이가 sbitmap 동작에 미치는 영향을 비교합니다.

SCSI 디바이스에서 shared tags를 사용할 때, HW 큐 수가 적으면 여러 CPU가 하나의 sbitmap_queue를 공유하므로 경합이 NVMe보다 높을 수 있습니다. 이 경우 sbitmap의 per-CPU hint와 round-robin 분산 메커니즘이 더욱 중요한 역할을 합니다.

특히 SAS HBA(Host Bus Adapter)의 경우 HW 큐가 1개뿐인 경우가 많아, 모든 CPU가 하나의 sbitmap_queue에서 태그를 할당받습니다. 이런 환경에서 shift 값을 작게(워드 수를 많게) 하여 CPU 간 캐시 라인 분산을 극대화하는 것이 중요합니다.

크기 튜닝

sbitmap의 성능은 queue_depth(전체 비트 수)와 shift(워드당 비트 수)의 설정에 크게 좌우됩니다. 이 섹션에서는 워크로드 특성에 따른 최적 파라미터 선택 가이드와, /sys 파일시스템을 통한 런타임 튜닝 방법을 다룹니다.

sbitmap에서 튜닝 가능한 핵심 파라미터는 다음 세 가지입니다.

1. queue_depth (= sbitmap depth): 동시에 사용할 수 있는 최대 비트(태그) 수입니다. blk-mq에서는 nr_requests sysfs 파라미터로 조정합니다. 이 값이 크면 동시 I/O 처리량이 높아지지만, 태그가 부족한 상황에서 대기 시간이 길어질 수 있습니다.
2. shift (= 워드당 비트 수의 로그): shift=4이면 워드당 2^4 = 16비트입니다. shift가 작을수록 워드 수가 많아져 CPU 간 분산이 잘 되지만, 각 워드의 비트가 적어져 빠르게 소진될 수 있습니다.
3. shallow_depth: I/O 스케줄러가 설정하는 실효 depth 제한입니다. 각 워드에서 shallow_depth개의 비트만 사용할 수 있으므로, 특정 프로세스 그룹의 태그 독점을 방지합니다.

depth와 shift의 관계

자동 shift 계산 알고리즘은 CPU 수와 depth의 비율을 기반으로 최적의 워드 수를 결정합니다. 핵심 원칙은 map_nr ≥ num_possible_cpus()가 되도록 shift를 조정하여, 각 CPU가 고유한 워드를 가질 수 있게 하는 것입니다.

수동으로 shift를 지정할 수도 있습니다. sbitmap_init_node()의 shift 인자에 음수가 아닌 값을 전달하면 자동 계산을 건너뛰고 지정된 값을 사용합니다. 그러나 blk-mq에서는 항상 shift = -1(자동 계산)을 사용하므로, 수동 지정은 커널 모듈에서 sbitmap을 직접 사용할 때만 해당됩니다.

shift 값의 트레이드오프

shift 값을 수동으로 결정해야 하는 경우(커널 모듈 개발 등), 다음 트레이드오프를 고려해야 합니다.

일반적으로 자동 계산(shift = -1)이 최적의 결과를 제공하므로, 특별한 이유가 없는 한 수동 지정을 피하는 것이 좋습니다.

/sys 파라미터 튜닝

# blk-mq 태그 관련 sysfs 파라미터 확인 및 튜닝

# 1. 현재 큐 깊이(queue_depth) 확인
#    NVMe의 경우 HW 큐 깊이와 동일 (보통 1023)
cat /sys/block/nvme0n1/queue/nr_requests
# 출력: 1023

# 2. nr_requests 줄이기 (태그 수 = sbitmap depth 감소)
#    I/O 지연이 중요한 워크로드에서 사용
echo 128 > /sys/block/nvme0n1/queue/nr_requests

# 3. I/O 스케줄러별 깊이 제한 확인
#    mq-deadline: 읽기/쓰기별 큐 깊이
cat /sys/block/nvme0n1/queue/iosched/read_expire
cat /sys/block/nvme0n1/queue/iosched/write_expire

# 4. 하드웨어 큐 수와 sbitmap 상태 확인
#    debugfs를 통해 sbitmap의 실시간 상태 확인
cat /sys/kernel/debug/block/nvme0n1/hctx0/tags_bitmap

# 5. 워크로드별 권장 설정
#    지연 민감(DB): nr_requests=32~128, none 스케줄러
#    처리량 중시(대용량 순차): nr_requests=1023, mq-deadline
#    혼합(VM 호스트): nr_requests=256~512, BFQ (shallow_depth 활용)

# 6. NVMe 드라이버 모듈 파라미터
#    HW 큐 깊이를 제한 (sbitmap depth에 직접 영향)
modinfo nvme | grep io_queue_depth
# parm: io_queue_depth:set io queue depth, should be >= 2 (int)
#    부팅 시 또는 모듈 로드 시:
#    nvme.io_queue_depth=256

워크로드별 튜닝 가이드

각 워크로드 유형에 따른 최적의 sbitmap 관련 파라미터 조합을 정리합니다.

런타임 depth 변경의 영향

nr_requests를 변경하면 blk-mq는 내부적으로 sbitmap을 재초기화합니다. 이 과정에서 다음이 발생합니다.

1. 기존 요청 완료 대기: 진행 중인 모든 I/O 요청이 완료될 때까지 대기합니다.
2. 태그 재할당: 새로운 depth에 맞게 sbitmap_queue가 재초기화됩니다. sbitmap_resize()가 호출되어 워드 배열 크기가 조정됩니다.
3. wake_batch 재계산: 새로운 depth에 맞게 sbq_calc_wake_batch()가 호출됩니다.
4. per-CPU hint 리셋: 모든 CPU의 alloc_hint가 0으로 초기화됩니다.

이 재초기화 과정은 모든 진행 중 I/O가 완료된 후에 수행되므로, 운영 중에도 안전하게 수행할 수 있습니다. 다만, 높은 I/O 부하 상황에서는 기존 요청 완료까지 잠시 지연이 발생할 수 있습니다.

sbitmap 상태 모니터링

운영 중인 시스템에서 sbitmap의 현재 상태를 확인하는 방법을 정리합니다. 특히 태그 부족으로 인한 성능 저하를 진단할 때 유용합니다.

태그 사용률이 지속적으로 depth의 80%를 초과하면, nr_requests를 늘리거나 I/O 패턴을 최적화해야 합니다. 반대로 태그 사용률이 항상 10% 미만이면, depth를 줄여 메모리를 절약하고 wake_batch를 더 작게 만들어 반응성을 향상시킬 수 있습니다.

bpftrace를 이용한 sbitmap 성능 추적

bpftrace를 사용하면 sbitmap의 런타임 동작을 실시간으로 관찰할 수 있습니다. 다음은 유용한 추적 스크립트 패턴을 정리합니다.

태그 대기 빈도(sbitmap_prepare_to_wait 호출 수)가 전체 태그 할당의 1%를 초과하면, nr_requests를 늘리거나 I/O 병합(merge)을 활성화하여 요청 수를 줄이는 것을 고려해야 합니다. wake-up 빈도가 지나치게 높다면, wake_batch가 너무 작아서 매 해제마다 깨우기가 발생하는 것일 수 있습니다.

fio 벤치마크와 sbitmap 영향

fio 벤치마크 도구의 주요 파라미터가 sbitmap 동작에 미치는 영향을 정리합니다.

특히 --iodepth를 nr_requests에 가깝게 설정하면 태그 부족으로 인한 io_schedule() 대기가 빈번하게 발생합니다. 이 상황에서 sbitmap의 wake-up 메커니즘의 효율성을 직접 확인할 수 있으며, wake_batch 설정이 꼬리 지연(tail latency)에 미치는 영향을 측정할 수 있습니다.

크기 튜닝 요약 체크리스트

sbitmap 관련 파라미터를 조정할 때 확인해야 할 항목을 체크리스트로 정리합니다.

1. 태그 사용률 확인: debugfs의 tags_bitmap을 통해 평균 사용률이 80% 미만인지 확인합니다. 초과 시 nr_requests를 늘립니다.
2. 태그 대기 빈도 확인: bpftrace로 sbitmap_prepare_to_wait 호출 빈도가 전체 I/O의 1% 미만인지 확인합니다.
3. NUMA 지역성 확인: /proc/irq/<irq>/smp_affinity가 디바이스의 NUMA 노드에 설정되어 있는지 확인합니다.
4. 스케줄러 적합성 확인: 지연 민감 워크로드에서는 none 스케줄러로 sbitmap 오버헤드를 최소화합니다.
5. HW 큐 수 확인: nr_hw_queues가 CPU 수와 일치하는지 확인합니다. 불일치 시 일부 CPU가 원격 hctx의 sbitmap에 접근합니다.
6. io_queue_depth 확인: NVMe의 경우 nvme.io_queue_depth 모듈 파라미터가 워크로드에 적합한지 확인합니다.
7. CAS 재시도 모니터링: bpftrace로 __sbitmap_get_word의 재시도 횟수를 추적하여, 워드 경합이 과도한지 확인합니다.
8. wake-up 효율성 확인: sbitmap_queue_wake_up과 sbitmap_prepare_to_wait의 호출 비율을 비교하여 wake-up이 효율적으로 동작하는지 확인합니다.
9. shallow_depth 영향 확인: BFQ/mq-deadline 사용 시 min_shallow_depth가 워크로드에 적절한지 확인합니다. 너무 작으면 태그 부족이 빈번해집니다.

이 체크리스트를 정기적으로 확인하면, sbitmap 관련 성능 문제를 조기에 발견하고 대응할 수 있습니다. 특히 디바이스 교체, 커널 업그레이드, 또는 워크로드 변경 후에는 반드시 확인하는 것을 권장합니다.

커널 소스 심층 워크스루

이 섹션에서는 sbitmap의 핵심 함수 4개를 커널 소스 기준(v6.x)으로 한 줄 한 줄 추적합니다. 앞선 섹션에서 개별적으로 다룬 함수들을 호출 체인 전체의 맥락에서 재조명하고, 각 분기 조건이 실제 워크로드에서 어떤 경로를 타는지 분석합니다.

sbitmap_get() per-CPU hint 파이프라인 상세

sbitmap_get()의 할당 경로는 4단계 파이프라인으로 구성됩니다. 각 단계에서 어떤 캐시 라인(Cache Line)이 접근되는지, 그리고 어떤 메모리 순서(Memory Ordering) 보장이 필요한지를 함께 추적합니다.

/* lib/sbitmap.c - sbitmap_get() 파이프라인 상세 분석 */

/* === Stage 1: per-CPU hint 읽기 ===
 * this_cpu_read()는 preemption-safe하지만 irq-safe하지 않음.
 * sbitmap_get()은 프로세스 컨텍스트에서만 호출되므로 문제없음.
 *
 * 캐시 라인 접근: CPU-local (per-CPU 영역)
 * 메모리 순서: 단일 CPU 내 순서 보장만 필요 */
int sbitmap_get(struct sbitmap *sb)
{
    int nr;
    unsigned int hint, depth;

    if (unlikely(sb->round_robin))
        return sbitmap_get_round_robin(sb);

    /* hint는 이전 할당이 성공한 워드의 비트 오프셋.
     * 이 값은 0부터 depth-1 범위이며,
     * SB_NR_TO_INDEX()로 워드 인덱스를 계산함 */
    hint = this_cpu_read(*sb->alloc_hint);
    depth = READ_ONCE(sb->depth);
    if (unlikely(hint >= depth)) {
        hint = 0;
        this_cpu_write(*sb->alloc_hint, hint);
    }

    /* === Stage 2: sbitmap_find_bit()으로 워드 순회 ===
     * hint를 기반으로 시작 워드를 결정하고,
     * map_nr개 워드를 순회하며 빈 비트를 탐색함 */
    nr = sbitmap_find_bit(sb, depth, hint, 0);

    /* === Stage 4: hint 갱신 ===
     * 할당 성공 시 다음 CPU의 시작점을 nr+1로 갱신.
     * 실패(-1) 시 hint를 변경하지 않음 */
    if (nr >= 0)
        this_cpu_write(*sb->alloc_hint,
                       (nr + 1) % depth);

    return nr;
}

/* === Stage 2 상세: sbitmap_find_bit() ===
 * 핵심 설계: hint → 워드 인덱스 매핑 후,
 * 해당 워드부터 원형(circular) 순회.
 * 첫 번째 워드에서는 hint의 비트 오프셋부터,
 * 나머지 워드에서는 비트 0부터 탐색 */
static int sbitmap_find_bit(struct sbitmap *sb,
                            unsigned int depth,
                            unsigned int alloc_hint,
                            unsigned int shallow_depth)
{
    unsigned int i, index;

    index = SB_NR_TO_INDEX(sb, alloc_hint);

    for (i = 0; i < sb->map_nr; i++) {
        unsigned int map_idx = (index + i) % sb->map_nr;
        unsigned int nr_bits = sb_word_depth(sb, map_idx);
        unsigned long cleared;
        int nr;

        /* === Stage 2a: lazy clear 해소 ===
         * xchg()는 full memory barrier를 포함.
         * cleared에 축적된 해제 비트를 한 번에 word에 반영.
         *
         * 캐시 라인 접근: sb->map[map_idx] (shared)
         * 핵심: xchg가 cleared를 0으로 만드는 동시에
         *       이전 값을 가져오므로, 다른 CPU의
         *       set_bit(cleared)와 원자적으로 합침 */
        cleared = xchg(&sb->map[map_idx].cleared, 0);
        if (cleared)
            sb->map[map_idx].word &= ~cleared;

        /* === Stage 3: __sbitmap_get_word() 호출 ===
         * 실제 원자적 비트 설정 수행.
         * 첫 워드는 hint의 비트 오프셋부터, wrap=true.
         * 이후 워드는 비트 0부터, wrap=false */
        if (shallow_depth && shallow_depth < nr_bits)
            nr_bits = shallow_depth;

        nr = __sbitmap_get_word(
            &sb->map[map_idx].word, nr_bits,
            (i == 0) ? SB_NR_TO_BIT(sb, alloc_hint) : 0,
            (i == 0));  /* 첫 워드만 wrap 허용 */

        if (nr >= 0)
            return (map_idx << sb->shift) + nr;
    }

    return -1;  /* 모든 워드에서 빈 비트 없음 */
}

__sbitmap_get_word() CAS 루프 심층 분석

__sbitmap_get_word()는 sbitmap 할당 경로의 최하위 함수입니다. 단일 워드 내에서 find_next_zero_bit()와 test_and_set_bit_lock()의 CAS(Compare-And-Swap) 루프를 수행합니다. 이 함수의 성능이 전체 sbitmap 할당 성능을 결정합니다.

/* lib/sbitmap.c - __sbitmap_get_word() 상세 분석 */
static int __sbitmap_get_word(unsigned long *word,
                              unsigned long depth,
                              unsigned int hint,
                              bool wrap)
{
    int nr;

    while (1) {
        /* Step A: 하드웨어 가속 비트 스캔
         * x86에서는 BSF (Bit Scan Forward) 명령어,
         * ARM64에서는 CLZ + bitwise NOT으로 구현됨.
         * O(1) 연산이므로 워드 크기(64비트)에 무관 */
        nr = find_next_zero_bit(word, depth, hint);

        if (unlikely(nr >= depth)) {
            /* Step B: 후반부 소진 → wrap-around
             * hint 이후에 빈 비트가 없으면,
             * 워드 처음(0)부터 hint까지 재탐색.
             * wrap=false이면 이 워드를 포기하고 -1 반환 */
            if (!wrap)
                return -1;
            nr = find_next_zero_bit(word, hint, 0);
            if (unlikely(nr >= hint))
                return -1;
            wrap = false;
            /* wrap을 false로 설정하여 무한 루프 방지.
             * 이후 CAS 실패 시 hint를 전진시키며 순차 탐색 */
        }

        /* Step C: 원자적 비트 설정 (CAS)
         * test_and_set_bit_lock()은 acquire 시맨틱을 가짐:
         * - 성공 시: 이 비트에 대한 모든 후속 접근은
         *   이 시점 이후에 관찰됨 (크리티컬 섹션 진입과 유사)
         * - 실패 시: 다른 CPU가 먼저 설정함 → 다음 비트로 이동
         *
         * x86: LOCK BTS (Bit Test and Set) 명령어
         * ARM64: LDAXR + STLXR 루프 */
        if (!test_and_set_bit_lock(nr, word))
            return nr;

        /* Step D: CAS 실패 시 hint 전진
         * nr+1부터 다시 탐색. depth-1에 도달하면 0으로 리셋.
         * 이 패턴은 높은 경합(contention) 상황에서
         * 다른 CPU와 같은 비트를 반복 시도하는 것을 방지함 */
        hint = nr + 1;
        if (hint >= depth - 1)
            hint = 0;
    }
}

sbitmap_queue_wake_up() 상태 머신 분석

sbitmap_queue_wake_up()의 동작을 상태 머신으로 모델링하면, 복잡한 경쟁 조건을 체계적으로 이해할 수 있습니다. wake-up은 3개의 상태를 순환합니다.

/* lib/sbitmap.c - wake-up 상태 머신 분석
 *
 * 상태 정의:
 *   COUNTING  : wait_cnt > 0, 비트 해제 시 wait_cnt 감소
 *   WAKING    : wait_cnt == 0, 대기자를 깨우는 중
 *   ADVANCING : wake 완료, 다음 대기 큐로 이동
 *
 * 전이 조건:
 *   COUNTING → WAKING    : atomic_dec_return(&wait_cnt) == 0
 *   WAKING   → ADVANCING : wake_up_nr() 호출 완료
 *   ADVANCING → COUNTING : wait_cnt 리셋 + wake_index 증가
 */

static bool __sbq_wake_up(struct sbitmap_queue *sbq, int *nr)
{
    struct sbq_wait_state *ws;
    unsigned int wake_batch;
    int wake_index, wait_cnt;

    /* 빠른 경로: 활성 대기자 없음
     * ws_active는 sbitmap_prepare_to_wait()에서 증가,
     * sbitmap_finish_wait()에서 감소함.
     * 이 검사로 대부분의 put 경로에서 wake-up 로직을 건너뜀 */
    if (!atomic_read(&sbq->ws_active))
        return false;

    /* 현재 서비스 중인 대기 큐 선택
     * wake_index는 0~7 범위를 라운드로빈으로 순환 */
    wake_index = atomic_read(&sbq->wake_index);
    ws = &sbq->ws[wake_index % SBQ_WAIT_QUEUES];

    /* COUNTING → WAKING 전이 시도
     * atomic_dec_return()은 full barrier를 포함.
     * 여러 CPU가 동시에 dec를 수행할 수 있으므로,
     * wait_cnt가 0 이하로 내려갈 수 있음.
     * 예: wake_batch=4, 5개 CPU가 동시 dec → wait_cnt=-1
     * 이 경우 wait_cnt <= 0을 확인하는 첫 번째 CPU만 wake 수행 */
    wait_cnt = atomic_dec_return(&ws->wait_cnt);
    if (wait_cnt <= 0) {
        /* WAKING 상태: 이 대기 큐의 모든 대기자를 깨움
         * wake_up_nr()의 인자는 깨울 프로세스 수.
         * wait_cnt가 음수이면 초과 감소분만큼 더 깨움 */
        int to_wake = max(1, atomic_read(&ws->wait_cnt) + 1);
        if (waitqueue_active(&ws->wait))
            wake_up_nr(&ws->wait, to_wake);

        /* ADVANCING 상태: wait_cnt 리셋 후 다음 큐로 이동
         * 이 시점에서 다른 CPU가 이 ws의 wait_cnt를 dec 중일 수 있음.
         * atomic_set()은 그 dec 결과를 덮어쓰지만,
         * 덮어쓴 CPU의 put은 다음 라운드에서 반영됨 */
        wake_batch = READ_ONCE(sbq->wake_batch);
        atomic_set(&ws->wait_cnt, wake_batch);

        /* 다음 대기 큐로 인덱스 이동 (라운드로빈)
         * atomic_inc()의 반환값은 사용하지 않음.
         * 여러 CPU가 동시에 inc할 수 있지만,
         * 큐를 건너뛰는 것 뿐이므로 정확성에 무관 */
        atomic_inc(&sbq->wake_index);
    }

    return true;
}

/* 외부 진입점: sbitmap_queue_clear()에서 호출됨 */
void sbitmap_queue_wake_up(struct sbitmap_queue *sbq, int nr)
{
    /* nr: 해제된 비트 번호 (현재 구현에서는 사용하지 않지만,
     * 향후 NUMA-aware wake-up 최적화에 활용될 수 있음) */
    __sbq_wake_up(sbq, &nr);
}

sbitmap_init_node() NUMA-aware 초기화 심층 분석

sbitmap_init_node()의 자동 shift 계산 알고리즘은 시스템의 CPU 수와 요청된 depth를 고려하여 최적의 워드 분할을 결정합니다. 이 알고리즘이 왜 ilog2(depth) - ilog2(num_possible_cpus())를 사용하는지, 그리고 경계 조건에서 어떻게 동작하는지를 추적합니다.

/* lib/sbitmap.c - sbitmap_init_node() 전체 분석 */
int sbitmap_init_node(struct sbitmap *sb,
                      unsigned int depth,
                      int shift,
                      gfp_t flags,
                      int node,
                      bool round_robin,
                      bool alloc_hint)
{
    unsigned int bits_per_word;

    if (shift < 0) {
        /* 자동 shift 계산 알고리즘:
         *
         * 목표: 각 CPU가 "전용" 워드를 가지도록 워드 수 ≈ CPU 수
         *
         * 예1: depth=1024, cpus=32
         *   shift = ilog2(1024) = 10
         *   ilog2(32) = 5 ≤ 10 → shift = 10 - 5 = 5
         *   bits_per_word = 2^5 = 32
         *   map_nr = 1024/32 = 32 워드 (= CPU 수)
         *
         * 예2: depth=64, cpus=128
         *   shift = ilog2(64) = 6
         *   ilog2(128) = 7 > 6 → shift 유지 = 6
         *   → max(6, 0) = 6, min(6, 6) = 6
         *   map_nr = 64/64 = 1 워드
         *   (CPU > depth이면 분산 불가, 단일 워드)
         *
         * 예3: depth=4096, cpus=8
         *   shift = ilog2(4096) = 12
         *   ilog2(8) = 3 ≤ 12 → shift = 12 - 3 = 9
         *   → min(9, 6) = 6 (BITS_PER_LONG 제한)
         *   bits_per_word = 64, map_nr = 4096/64 = 64 워드 */
        shift = ilog2(depth);
        if (ilog2(num_possible_cpus()) <= shift)
            shift -= ilog2(num_possible_cpus());
        shift = max(shift, 0);
        shift = min_t(int, shift, ilog2(BITS_PER_LONG));
    }

    bits_per_word = 1U << shift;

    sb->shift = shift;
    sb->depth = depth;
    sb->map_nr = DIV_ROUND_UP(depth, bits_per_word);
    sb->round_robin = round_robin;

    /* NUMA-aware 워드 배열 할당
     * kcalloc_node()는 지정된 NUMA 노드의 로컬 메모리에서 할당.
     * 이 배열이 sbitmap의 "핫 데이터"이므로,
     * 해당 노드의 CPU가 접근할 때 로컬 메모리 대역폭을 사용.
     *
     * sbitmap_word 구조체는 ____cacheline_aligned_in_smp 속성을 가지므로,
     * 각 워드가 별도의 캐시 라인에 배치됨 → false sharing 방지 */
    sb->map = kcalloc_node(sb->map_nr,
                           sizeof(*sb->map),
                           flags, node);
    if (!sb->map)
        return -ENOMEM;

    /* per-CPU hint 할당
     * alloc_percpu_gfp()는 각 CPU의 per-CPU 영역에 unsigned int를 할당.
     * per-CPU 데이터는 CPU별로 다른 캐시 라인에 위치하므로,
     * hint 읽기/쓰기 시 캐시 바운싱이 발생하지 않음.
     *
     * alloc_hint=false인 경우(round_robin 전용 워드 카운터 등)
     * per-CPU 힌트를 할당하지 않아 메모리를 절약 */
    if (alloc_hint) {
        sb->alloc_hint = alloc_percpu_gfp(
            unsigned int, flags);
        if (!sb->alloc_hint) {
            kfree(sb->map);
            return -ENOMEM;
        }
    }

    return 0;
}

shift 자동 계산 실전 예시

다양한 시스템 구성에서 sbitmap_init_node()의 자동 shift 계산 결과를 비교합니다.

표에서 볼 수 있듯이, 자동 shift 알고리즘은 대부분의 경우 워드:CPU 비율을 1:1에 가깝게 유지합니다. depth가 CPU 수보다 작은 극단적인 경우(32 depth, 64 CPU)에서만 단일 워드에 다수 CPU가 경합하게 됩니다. 이런 상황은 실제로는 NVMe의 기본 io_queue_depth(1024)나 SCSI의 기본 큐 깊이(64~256)에서는 거의 발생하지 않습니다.

심층 시각화

이 섹션에서는 앞서 분석한 커널 소스의 동작을 SVG 다이어그램으로 시각화합니다. 텍스트로는 이해하기 어려운 per-word 구조, wake-up 체인, 확장성 비교를 그래픽으로 표현합니다.

per-word 구조와 alloc_hint 매핑

다음 다이어그램은 4개의 CPU가 depth=128, shift=5(워드당 32비트, 4워드) 구성의 sbitmap에 동시에 접근하는 시나리오를 보여줍니다. 각 CPU의 alloc_hint가 어떻게 서로 다른 워드를 가리키는지, 그리고 __sbitmap_get_word()가 각 워드 내에서 독립적으로 동작하는지를 시각화합니다.

sbitmap_queue wake-up 체인

다음 다이어그램은 sbitmap_queue_clear()에서 시작하여 sbitmap_queue_wake_up() → __sbq_wake_up() → wake_up_nr()으로 이어지는 wake-up 체인의 전체 흐름을 보여줍니다. 특히 wait_cnt 감소와 wake_index 라운드로빈의 타이밍을 시간 순서대로 추적합니다.

bitmap vs. sbitmap 확장성 비교

다음 다이어그램은 일반 비트맵과 sbitmap의 확장성을 CPU 수 증가에 따라 비교합니다. 일반 비트맵은 단일 캐시 라인에 모든 접근이 집중되어 CPU 수가 증가할수록 성능이 저하되는 반면, sbitmap은 per-word 분산과 per-CPU hint 덕분에 거의 선형적으로 확장됩니다.

blk-mq의 sbitmap 실전 활용 패턴

sbitmap의 가장 중요한 소비자는 blk-mq 태그 할당 시스템입니다. 이 섹션에서는 실제 I/O 경로에서 sbitmap이 어떻게 사용되는지, 그리고 드라이버 개발자와 시스템 관리자가 알아야 할 실전 패턴을 다룹니다.

태그 할당의 전체 호출 체인

사용자 공간의 I/O 요청이 sbitmap까지 도달하는 전체 경로를 커널 소스 기반으로 추적합니다.

/* block/blk-mq.c - I/O 제출에서 태그 할당까지의 전체 경로
 *
 * 호출 체인:
 * submit_bio()
 *   → blk_mq_submit_bio()
 *     → __blk_mq_alloc_requests()
 *       → blk_mq_get_tag()          [block/blk-mq-tag.c]
 *         → __sbitmap_queue_get()    [lib/sbitmap.c]
 *           → sbitmap_get()
 *             → sbitmap_find_bit()
 *               → __sbitmap_get_word()
 */

/* block/blk-mq-tag.c */
unsigned int blk_mq_get_tag(struct blk_mq_alloc_data *data)
{
    struct blk_mq_tags *tags = blk_mq_tags_from_data(data);
    struct sbitmap_queue *bt;
    struct sbq_wait_state *ws;
    DEFINE_SBQ_WAIT(wait);
    unsigned int tag_offset;
    int tag;

    /* 예약 태그 vs. 일반 태그 선택
     * REQ_OP_DRV_IN/OUT 등 드라이버 내부 명령은
     * breserved_tags에서 할당하여 일반 I/O와 격리 */
    if (data->flags & BLK_MQ_REQ_RESERVED) {
        bt = &tags->breserved_tags;
        tag_offset = 0;
    } else {
        bt = &tags->bitmap_tags;
        tag_offset = tags->nr_reserved_tags;
    }

    /* 1차 시도: 바로 태그 획득 시도 (대부분 여기서 성공) */
    tag = __sbitmap_queue_get(bt);
    if (tag != -1)
        goto found_tag;

    /* 2차 시도: 태그 부족 시 대기
     * sbitmap_prepare_to_wait()로 대기 큐에 등록 후
     * I/O 스케줄러 flush 시도 → 재할당 → 슬립 루프 */
    ws = sbq_wait_ptr(bt, &wait);
    do {
        /* I/O 스케줄러에 dispatch 요청하여 태그 회수 시도 */
        blk_mq_run_hw_queue(data->hctx, false);

        sbitmap_prepare_to_wait(bt, ws, &wait,
                                TASK_UNINTERRUPTIBLE);

        tag = __sbitmap_queue_get(bt);
        if (tag != -1)
            break;

        /* 여전히 태그 없음: I/O_schedule()로 슬립
         * sbitmap_queue_wake_up()이 호출될 때까지 대기 */
        io_schedule();
    } while (1);

    sbitmap_finish_wait(bt, ws, &wait);

found_tag:
    return tag + tag_offset;
}

태그 반환과 wake-up 전파

I/O 완료 시 태그를 반환하고 대기 중인 프로세스를 깨우는 경로입니다.

/* block/blk-mq-tag.c - 태그 반환 경로
 *
 * 호출 체인:
 * blk_mq_end_request()
 *   → __blk_mq_free_request()
 *     → blk_mq_put_tag()
 *       → sbitmap_queue_clear()      [lib/sbitmap.c]
 *         → sbitmap_deferred_clear_bit()
 *         → sbitmap_queue_wake_up()
 */

/* lib/sbitmap.c */
void sbitmap_queue_clear(struct sbitmap_queue *sbq,
                         unsigned int nr,
                         unsigned int cpu)
{
    /* 핵심 1: lazy clear 패턴
     * word에서 직접 비트를 끄지 않고,
     * cleared 필드에 비트를 설정.
     * 이렇게 하면 같은 워드에서 할당 중인 다른 CPU와
     * word 필드에서 경합하지 않음 */
    sbitmap_deferred_clear_bit(&sbq->sb, nr);

    /* 핵심 2: hint 갱신 (반환한 CPU 기준)
     * 비트를 반환한 CPU가 다음에 다시 이 근처에서
     * 할당받을 수 있도록 hint를 해제된 비트로 설정.
     * 이는 캐시 라인 지역성(locality)을 높여줌 */
    this_cpu_write(*sbq->sb.alloc_hint, nr);

    /* 핵심 3: 대기자 깨우기
     * wake_batch만큼 누적되면 대기 큐의 프로세스를 깨움 */
    sbitmap_queue_wake_up(sbq, nr);
}

/* 사용 예: NVMe 완료 인터럽트 핸들러 */
static void nvme_complete_rq(struct request *req)
{
    /* ... 에러 처리, 통계 갱신 ... */
    blk_mq_end_request(req, status);
    /* → __blk_mq_free_request()
     *   → blk_mq_put_tag()
     *     → sbitmap_queue_clear()
     *       → sbitmap_deferred_clear_bit() + wake_up */
}

Shared Tags 패턴

여러 하드웨어 큐가 하나의 sbitmap_queue를 공유하는 shared tags 패턴은 단일 태그 풀을 여러 큐가 나누어 사용하는 시나리오에서 사용됩니다. 이 패턴은 태그 낭비를 줄이지만 NUMA 지역성이 희생됩니다.

/* block/blk-mq-tag.c - shared tags 할당 패턴 */

/* shared tags 사용 시 태그 할당 경로:
 * 1. 먼저 per-hctx tags에서 시도 (로컬 NUMA 노드)
 * 2. 실패하면 shared tags에서 시도 (전역 풀)
 *
 * 이 2단계 전략의 이유:
 * - per-hctx tags: NUMA 지역성 최적, 경합 최소
 * - shared tags: per-hctx가 소진되었을 때 백업
 *   다른 큐의 미사용 태그를 빌려올 수 있음 */

struct blk_mq_tags {
    unsigned int nr_tags;
    unsigned int nr_reserved_tags;

    /* 일반 태그와 예약 태그 각각 별도의 sbitmap_queue */
    struct sbitmap_queue bitmap_tags;
    struct sbitmap_queue breserved_tags;

    /* 태그 번호 → request 포인터 매핑 배열
     * rqs[tag] = &request 구조체
     * NVMe CQE의 command_id로 O(1) 조회 가능 */
    struct request **rqs;
    struct request **static_rqs;
};

/* blk_mq_tag_set에서 shared sbitmap 초기화 */
int blk_mq_init_shared_sbitmap(
    struct blk_mq_tag_set *set)
{
    int alloc_policy = BLK_TAG_ALLOC_RR;

    /* shared tags는 round-robin 정책 사용
     * 여러 hctx가 공유하므로 per-CPU hint 대신
     * 라운드로빈으로 워드를 순회하여 공정성 보장 */
    return sbitmap_queue_init_node(
        &set->__bitmap_tags,
        set->queue_depth,
        -1,  /* shift 자동 계산 */
        alloc_policy == BLK_TAG_ALLOC_RR,
        GFP_KERNEL,
        cpu_to_node(raw_smp_processor_id()));
}

디바이스 드라이버의 sbitmap 간접 사용

디바이스 드라이버는 sbitmap API를 직접 호출하지 않습니다. 대신 blk_mq_tag_set을 설정하면 blk-mq 프레임워크가 자동으로 sbitmap을 초기화하고 관리합니다.

/* drivers/nvme/host/pci.c - NVMe 드라이버의 태그 세트 설정 예시 */
static int nvme_alloc_admin_tag_set(
    struct nvme_dev *dev,
    struct blk_mq_tag_set *set)
{
    /* 드라이버가 설정하는 것은 이 파라미터들뿐.
     * blk-mq가 이 값들을 기반으로 sbitmap_queue를 초기화함 */
    memset(set, 0, sizeof(*set));
    set->ops = &nvme_mq_admin_ops;
    set->queue_depth = NVME_AQ_MQ_TAG_DEPTH;  /* 기본 32 */
    set->reserved_tags = 2;  /* 관리 명령용 예약 */
    set->numa_node = dev->ctrl.numa_node;
    set->flags = BLK_MQ_F_NO_SCHED;  /* 관리 큐는 스케줄러 없음 */
    set->cmd_size = sizeof(struct nvme_iod);
    set->driver_data = dev;
    set->nr_hw_queues = 1;
    set->timeout = NVME_ADMIN_TIMEOUT;

    /* blk_mq_alloc_tag_set() 내부에서:
     * 1. sbitmap_queue_init_node(&tags->bitmap_tags,
     *      queue_depth - reserved_tags, ...)
     * 2. sbitmap_queue_init_node(&tags->breserved_tags,
     *      reserved_tags, ...)
     * 3. tags->rqs = kcalloc(queue_depth, sizeof(struct request *))
     *
     * 결과: depth=30인 일반 sbitmap + depth=2인 예약 sbitmap */
    return blk_mq_alloc_tag_set(set);
}

/* I/O 큐의 태그 세트 설정 */
static int nvme_alloc_io_tag_set(
    struct nvme_dev *dev,
    struct blk_mq_tag_set *set)
{
    set->ops = &nvme_mq_ops;
    set->queue_depth = min_t(unsigned,
        dev->ctrl.sqsize + 1,
        dev->q_depth);  /* 기본 1024 */
    set->reserved_tags = 1;  /* reset용 예약 */
    set->numa_node = dev->ctrl.numa_node;
    set->nr_hw_queues = dev->online_queues - 1;
    set->nr_maps = 3;  /* default, read, poll */

    /* blk_mq_alloc_tag_set() →
     * sbitmap_queue_init_node() with:
     *   depth = 1023 (1024 - 1 reserved)
     *   shift = auto (CPU 수 기반 계산)
     *   node = dev->ctrl.numa_node
     *   round_robin = false (기본 hint 모드)
     *
     * NVMe PCIe Gen4 SSD (128 CPU 시스템):
     *   shift = ilog2(1023) - ilog2(128) ≈ 10 - 7 = 3
     *   bits_per_word = 8
     *   map_nr = 128 (≈ CPU 수) */
    return blk_mq_alloc_tag_set(set);
}

참고 자료

• include/linux/sbitmap.h — Bootlin Elixir — sbitmap 헤더 파일: 구조체 정의, 인라인 함수, 매크로가 포함되어 있습니다.
• lib/sbitmap.c — Bootlin Elixir — sbitmap 구현 코드: 초기화, 할당, 해제, wake-up 로직의 전체 구현입니다.
• block/blk-mq-tag.c — Bootlin Elixir — blk-mq 태그 할당/해제 코드: blk_mq_get_tag(), blk_mq_put_tag()의 구현입니다.
• block/blk-mq-tag.h — Bootlin Elixir — struct blk_mq_tags 정의: sbitmap_queue를 포함하는 태그 관리 구조체입니다.
• block/blk-mq.c — Bootlin Elixir — blk-mq 핵심 코드: 요청 제출부터 완료까지의 전체 흐름입니다.
• Kernel Docs — Multi-Queue Block IO Queueing Mechanism — blk-mq의 공식 문서로, 태그 할당과 sbitmap의 역할을 설명합니다.
• LWN: A block layer introduction part 2: the request layer (2016) — blk-mq 아키텍처와 태그 관리의 배경을 설명합니다.
• LWN: Block-layer I/O scheduling improvements (2017) — BFQ와 mq-deadline의 sbitmap 활용을 다룹니다.
• Git commit: lib/sbitmap: introduce sbitmap — Omar Sandoval이 sbitmap을 처음 도입한 커밋입니다.
• Bitmap — sbitmap의 기반이 되는 일반 비트맵 자료구조를 다루는 페이지입니다.
• 블록 I/O — blk-mq의 전체 아키텍처를 다루는 페이지입니다.
• Atomic 연산 — sbitmap이 사용하는 원자적 비트 연산의 기초 개념입니다.
• 메모리 배리어(Memory Barrier) — sbitmap의 메모리 순서 보장 메커니즘의 이론적 배경입니다.
• Linux Block IO: Introducing Multi-queue SSD Access on Multi-core Systems (Björling et al., 2013) — blk-mq 아키텍처의 원래 논문으로, 태그 할당의 확장성 문제가 처음 논의되었습니다.
• USENIX FAST'17: LightNVM: The Linux Open-Channel SSD Subsystem — NVMe 및 고성능 스토리지에서의 blk-mq 태그 관리 실전 사례입니다.
• block/bfq-iosched.c — Bootlin Elixir — BFQ 스케줄러의 sbitmap shallow_depth 활용 코드입니다.
• block/mq-deadline.c — Bootlin Elixir — mq-deadline 스케줄러의 태그 제한 구현 코드입니다.
• block/blk-wbt.c — Bootlin Elixir — Writeback Throttling의 sbitmap_queue 활용 코드입니다.
• linux-block 메일링 리스트 — sbitmap 패치와 논의가 이루어지는 메일링 리스트입니다.

관련 커널 자료구조

추가 학습 자료

sbitmap의 이해를 심화하기 위해 다음 주제를 추가로 학습하는 것을 권장합니다.

• Per-CPU 변수: sbitmap의 alloc_hint가 per-CPU 변수로 구현되어 있으므로, include/linux/percpu.h의 per-CPU 메커니즘을 이해하면 힌트 동작을 더 깊이 파악할 수 있습니다.
• 캐시 일관성(Cache Coherence) 프로토콜: MESI/MOESI 프로토콜이 sbitmap의 캐시 라인 분리 전략의 이론적 배경입니다. 특히 Modified 상태에서의 무효화(Invalidation) 비용이 sbitmap이 해결하려는 핵심 문제입니다.
• Lock-Free 자료구조: sbitmap의 lazy clear 패턴은 lock-free 알고리즘의 "split counter" 기법과 유사합니다. CAS(Compare-And-Swap) 기반 lock-free 큐/스택의 설계 패턴을 이해하면 sbitmap의 동시성 전략을 더 잘 이해할 수 있습니다.
• NUMA 아키텍처: kcalloc_node()와 NUMA 노드 인식 할당의 배경이 되는 NUMA 메모리 아키텍처를 학습하세요.
• Wait Queue: sbitmap_queue의 대기 메커니즘은 커널의 표준 wait_queue_head_t 위에 구축되어 있습니다. prepare_to_wait_exclusive(), wake_up_nr() 등의 API를 이해하면 wake-up 최적화를 깊이 파악할 수 있습니다.