Bitmap

Linux 커널의 가장 기본적인 자료구조인 비트맵(Bitmap)의 개념, 비트 연산 최적화, cpumask를 포함한 다양한 API, 페이지 프레임(Page Frame) 할당자와 IRQ 관리 등 실제 활용 사례, 그리고 실습 예제까지 종합적으로 다룹니다.

개요 (Overview)

비트맵(Bitmap)은 각 비트가 하나의 상태나 자원을 나타내는 자료구조입니다. C 언어에서는 unsigned long 배열로 구현되며, 커널은 <linux/bitmap.h>와 <linux/bitops.h>에서 최적화된 API를 제공합니다.

비트맵이 커널에서 광범위하게 사용되는 이유:

• 메모리 효율 — 1비트 = 1상태. 8192개 CPU를 표현하는데 1KB만 필요합니다.
• 고속 연산 — CPU의 비트 스캔 명령어(x86 BSF/BSR, ARM CLZ/CTZ)를 직접 활용합니다.
• 배치 처리 — 64비트 시스템에서 한 번에 64개 상태를 AND/OR로 처리 가능합니다.
• 원자성 — set_bit()/clear_bit()는 원자적 연산(Atomic Operation)으로 동기화 비용이 낮습니다.
• 캐시 효율 — 연속 메모리 배치로 spatial locality가 좋습니다.

비트 연산 기초 (Bit Operations Basics)

커널 비트맵 API를 이해하려면 먼저 C 언어의 비트 연산을 복습해야 합니다:

흔한 비트 조작 패턴

/* 특정 비트 설정 (set) */
unsigned long flags = 0;
flags |= (1UL << 3);  /* 3번 비트를 1로 설정 */

/* 특정 비트 제거 (clear) */
flags &= ~(1UL << 3);  /* 3번 비트를 0으로 */

/* 특정 비트 토글 (flip) */
flags ^= (1UL << 3);  /* 3번 비트 반전 */

/* 특정 비트 테스트 (test) */
if (flags & (1UL << 3))
    pr_info("Bit 3 is set\n");

/* 최하위 1비트 찾기 (find first set) */
int pos = __builtin_ffs(flags) - 1;  /* GCC builtin */

/* 선행 0 개수 세기 (count leading zeros) */
int lz = __builtin_clz(flags);  /* x86: BSR, ARM: CLZ */

커널 비트맵 API (Kernel Bitmap API)

커널은 비트맵 조작을 위한 포괄적인 API를 제공합니다. 크게 세 가지 계층으로 나뉩니다:

원자적(Atomic) 비트 연산 (Atomic Bit Operations)

동시성 안전이 보장되며, 메모리 배리어(Memory Barrier)를 포함합니다:

/* include/linux/bitops.h */

/* 원자적으로 비트 설정 */
void set_bit(unsigned int nr, volatile unsigned long *addr);

/* 원자적으로 비트 제거 */
void clear_bit(unsigned int nr, volatile unsigned long *addr);

/* 원자적으로 비트 변경 (0↔1) */
void change_bit(unsigned int nr, volatile unsigned long *addr);

/* 비트를 설정하고, 이전 값 반환 (atomic test-and-set) */
int test_and_set_bit(unsigned int nr, volatile unsigned long *addr);

/* 비트를 제거하고, 이전 값 반환 */
int test_and_clear_bit(unsigned int nr, volatile unsigned long *addr);

/* 비트를 변경하고, 이전 값 반환 */
int test_and_change_bit(unsigned int nr, volatile unsigned long *addr);

/* 비원자적 버전 (lock으로 보호된 컨텍스트에서만 사용) */
void __set_bit(unsigned int nr, volatile unsigned long *addr);
void __clear_bit(unsigned int nr, volatile unsigned long *addr);
int __test_and_set_bit(unsigned int nr, volatile unsigned long *addr);

비트맵 검색 API (Bitmap Search API)

설정/해제된 비트를 빠르게 찾는 함수들입니다. 하드웨어 명령어를 활용하여 최적화되어 있습니다:

/* include/linux/find.h */

/* 첫 번째로 설정된 비트 찾기 (LSB→MSB) */
unsigned long find_first_bit(const unsigned long *addr, unsigned long size);

/* 첫 번째로 0인 비트 찾기 */
unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size);

/* offset 이후 다음 설정된 비트 찾기 */
unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
                            unsigned long offset);

/* offset 이후 다음 0인 비트 찾기 */
unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
                                  unsigned long offset);

/* 마지막으로 설정된 비트 찾기 (MSB→LSB) */
unsigned long find_last_bit(const unsigned long *addr, unsigned long size);

/* 사용 예: 모든 설정된 비트 순회 */
unsigned long bit;
for (bit = find_first_bit(bitmap, nbits);
     bit < nbits;
     bit = find_next_bit(bitmap, nbits, bit + 1)) {
    pr_info("Bit %lu is set\n", bit);
}

비트맵 순회 매크로(Macro) (Bitmap Iteration Macros)

/* include/linux/find.h - 편의 매크로 */

/* 모든 설정된 비트 순회 */
#define for_each_set_bit(bit, addr, size) \
    for ((bit) = find_first_bit((addr), (size));  \
         (bit) < (size);                            \
         (bit) = find_next_bit((addr), (size), (bit) + 1))

/* 모든 0인 비트 순회 */
#define for_each_clear_bit(bit, addr, size) \
    for ((bit) = find_first_zero_bit((addr), (size)); \
         (bit) < (size);                               \
         (bit) = find_next_zero_bit((addr), (size), (bit) + 1))

/* 사용 예 */
unsigned long cpu;
for_each_set_bit(cpu, cpumask_bits(mask), nr_cpu_ids) {
    pr_info("CPU %lu is online\n", cpu);
}

비트맵 배치 연산 (Bulk Bitmap Operations)

/* include/linux/bitmap.h */

/* 비트맵 초기화 (모든 비트를 0 또는 1로) */
void bitmap_zero(unsigned long *dst, unsigned int nbits);
void bitmap_fill(unsigned long *dst, unsigned int nbits);

/* 비트맵 복사 */
void bitmap_copy(unsigned long *dst, const unsigned long *src, unsigned int nbits);

/* 비트맵 논리 연산 (dst = src1 OP src2) */
void bitmap_and(unsigned long *dst, const unsigned long *src1,
                  const unsigned long *src2, unsigned int nbits);
void bitmap_or(unsigned long *dst, const unsigned long *src1,
                 const unsigned long *src2, unsigned int nbits);
void bitmap_xor(unsigned long *dst, const unsigned long *src1,
                  const unsigned long *src2, unsigned int nbits);

/* 비트맵 비교 */
int bitmap_equal(const unsigned long *src1, const unsigned long *src2,
                   unsigned int nbits);
int bitmap_subset(const unsigned long *src1, const unsigned long *src2,
                    unsigned int nbits);

/* 비트맵 카운팅 */
int bitmap_weight(const unsigned long *src, unsigned int nbits);  /* 설정된 비트 수 */
int bitmap_empty(const unsigned long *src, unsigned int nbits);   /* 모든 비트가 0? */
int bitmap_full(const unsigned long *src, unsigned int nbits);    /* 모든 비트가 1? */

cpumask: CPU 비트맵 (CPU Bitmap)

cpumask_t는 비트맵의 가장 중요한 특화 형태로, CPU 집합을 표현합니다. 커널은 <linux/cpumask.h>에서 cpumask 전용 API를 제공하며, SMP 시스템에서 핵심적인 역할을 합니다.

/* include/linux/cpumask.h */
typedef struct cpumask {
    DECLARE_BITMAP(bits, NR_CPUS);
} cpumask_t;

/* 정적 초기화 */
static DEFINE_CPUMASK(my_cpumask);

/* 주요 API */
void cpumask_set_cpu(unsigned int cpu, struct cpumask *dstp);
void cpumask_clear_cpu(unsigned int cpu, struct cpumask *dstp);
int cpumask_test_cpu(int cpu, const struct cpumask *cpumask);

/* CPU 순회 */
unsigned int cpu;
for_each_cpu(cpu, mask) {
    pr_info("CPU %u is in mask\n", cpu);
}

/* 온라인 CPU만 순회 */
for_each_online_cpu(cpu) {
    pr_info("CPU %u is online\n", cpu);
}

/* CPU affinity 설정 */
struct cpumask new_mask;
cpumask_clear(&new_mask);
cpumask_set_cpu(2, &new_mask);
cpumask_set_cpu(3, &new_mask);
set_cpus_allowed_ptr(current, &new_mask);  /* 현재 태스크를 CPU 2,3에만 바인딩 */

cpumask 동작 시각화

성능 최적화 (Performance Optimization)

하드웨어 가속 (Hardware Acceleration)

커널의 비트 검색 함수는 CPU 명령어를 직접 활용하여 O(1) 또는 O(log n) 성능을 달성합니다:

/* arch/x86/include/asm/bitops.h - x86 구현 예시 */
static __always_inline unsigned long __ffs(unsigned long word)
{
    asm("bsf %1,%0"
        : "=r" (word)
        : "rm" (word));
    return word;
}

/* 소프트웨어 폴백 (하드웨어 명령어 없을 때) */
static inline unsigned long __ffs_generic(unsigned long word)
{
    int num = 0;
    while (!(word & 1)) {
        num++;
        word >>= 1;
    }
    return num;
}

캐시 효율성 (Cache Efficiency)

비트맵의 캐시 성능:

• 공간 지역성: 연속 메모리 배치로 sequential access 시 prefetcher가 효과적으로 동작
• 캐시 라인 활용: 64바이트 캐시 라인에 512비트(64바이트)가 한 번에 로드됨
• False sharing 회피: per-CPU 비트맵을 사용하면 다른 CPU 간 캐시 라인 경합 없음

/* 좋은 패턴: per-CPU 비트맵으로 false sharing 회피 */
static DEFINE_PER_CPU(unsigned long[16], local_bitmap);

void process_data(void)
{
    unsigned long *bitmap = this_cpu_ptr(local_bitmap);
    /* 각 CPU가 독립적인 캐시 라인에서 작업 */
    set_bit(42, bitmap);
}

실측 성능 비교

실사용 사례 (Real-World Usage)

페이지 프레임 할당자 (Page Frame Allocator)

Buddy allocator는 각 order별로 비트맵을 사용하여 free 페이지 프레임을 추적합니다:

/* mm/page_alloc.c - 간략화된 개념 */
struct zone {
    struct free_area free_area[MAX_ORDER];  /* order 0-10 */
};

struct free_area {
    struct list_head free_list[MIGRATE_TYPES];
    unsigned long  *map;  /* 비트맵: 페이지 블록 상태 */
};

/* 빠른 할당: 첫 번째 free 블록 찾기 */
unsigned long find_free_block(struct zone *zone, int order)
{
    struct free_area *area = &zone->free_area[order];
    return find_first_zero_bit(area->map, zone->spanned_pages >> order);
}

IRQ 디스크립터 (IRQ Descriptors)

/* kernel/irq/irqdesc.c */
static DECLARE_BITMAP(allocated_irqs, IRQ_BITMAP_BITS);

/* 사용 가능한 IRQ 번호 할당 */
int irq_alloc_descs(int irq, unsigned int from, unsigned int cnt,
                    int node)
{
    int start;

    if (irq >= 0)
        start = irq;
    else
        start = find_next_zero_bit(allocated_irqs, IRQ_BITMAP_BITS, from);

    if (start + cnt > IRQ_BITMAP_BITS)
        return -ENOSPC;

    /* 비트맵에 할당 표시 */
    bitmap_set(allocated_irqs, start, cnt);
    return start;
}

블록 디바이스 비트맵 (Block Device Bitmap)

/* fs/ext4/balloc.c - ext4 블록 할당 비트맵 */
ext4_fsblk_t ext4_new_meta_blocks(struct inode *inode)
{
    struct buffer_head *bitmap_bh;
    ext4_group_t group;
    ext4_grpblk_t grp_blk;

    /* 블록 그룹의 블록 비트맵 읽기 */
    bitmap_bh = ext4_read_block_bitmap(sb, group);

    /* 비어있는 첫 번째 블록 찾기 */
    grp_blk = find_next_zero_bit((unsigned long *)bitmap_bh->b_data,
                                      EXT4_BLOCKS_PER_GROUP(sb), 0);

    /* 비트맵에 할당 표시 */
    ext4_set_bit(grp_blk, bitmap_bh->b_data);
    mark_buffer_dirty(bitmap_bh);

    return ext4_group_first_block_no(sb, group) + grp_blk;
}

네트워크 포트 비트맵 (Network Port Bitmap)

/* net/ipv4/inet_hashtables.c - ephemeral port 할당 */
static DEFINE_BITMAP(port_bitmap, 65536);

int inet_get_local_port_range(int *low, int *high)
{
    *low = 32768;   /* sysctl_ip_local_port_range[0] */
    *high = 60999;  /* sysctl_ip_local_port_range[1] */
    return 0;
}

__be16 inet_select_random_port(void)
{
    int low, high, remaining, port;

    inet_get_local_port_range(&low, &high);
    remaining = high - low + 1;

    /* 사용 가능한 포트 찾기 */
    port = find_next_zero_bit(port_bitmap, high + 1, low);
    if (port > high)
        port = find_first_zero_bit(port_bitmap + low / BITS_PER_LONG,
                                    remaining);

    set_bit(port, port_bitmap);
    return htons(port);
}

실습 예제 (Hands-On Example)

간단한 자원 할당자를 비트맵으로 구현하는 커널 모듈(Kernel Module)입니다. 128개의 자원(예: DMA 채널)을 관리합니다.

/* resource_bitmap.c - 비트맵 기반 자원 할당자 */
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/bitmap.h>
#include <linux/spinlock.h>

#define MAX_RESOURCES 128

/* 자원 비트맵 (0 = free, 1 = allocated) */
static DECLARE_BITMAP(resource_bitmap, MAX_RESOURCES);
static DEFINE_SPINLOCK(resource_lock);

/* 자원 할당 */
static int alloc_resource(void)
{
    unsigned long flags;
    int id;

    spin_lock_irqsave(&resource_lock, flags);

    /* 첫 번째 빈 자원 찾기 */
    id = find_first_zero_bit(resource_bitmap, MAX_RESOURCES);
    if (id >= MAX_RESOURCES) {
        spin_unlock_irqrestore(&resource_lock, flags);
        pr_warn("No free resources\n");
        return -ENOSPC;
    }

    /* 할당 표시 */
    set_bit(id, resource_bitmap);

    spin_unlock_irqrestore(&resource_lock, flags);

    pr_info("Allocated resource %d\n", id);
    return id;
}

/* 자원 해제 */
static void free_resource(int id)
{
    unsigned long flags;

    if (id < 0 || id >= MAX_RESOURCES) {
        pr_err("Invalid resource ID %d\n", id);
        return;
    }

    spin_lock_irqsave(&resource_lock, flags);

    if (!test_bit(id, resource_bitmap)) {
        pr_warn("Resource %d is already free\n", id);
        spin_unlock_irqrestore(&resource_lock, flags);
        return;
    }

    clear_bit(id, resource_bitmap);
    spin_unlock_irqrestore(&resource_lock, flags);

    pr_info("Freed resource %d\n", id);
}

/* 할당된 자원 출력 */
static void print_allocated_resources(void)
{
    unsigned long id;
    int count = 0;

    pr_info("=== Allocated Resources ===\n");
    for_each_set_bit(id, resource_bitmap, MAX_RESOURCES) {
        pr_info("  Resource %lu\n", id);
        count++;
    }

    pr_info("Total: %d/%d allocated\n", count, MAX_RESOURCES);
    pr_info("Free: %d\n", MAX_RESOURCES - count);
}

/* 통계 정보 */
static void print_statistics(void)
{
    int allocated = bitmap_weight(resource_bitmap, MAX_RESOURCES);
    int is_empty = bitmap_empty(resource_bitmap, MAX_RESOURCES);
    int is_full = bitmap_full(resource_bitmap, MAX_RESOURCES);

    pr_info("Statistics: %d allocated, empty=%d, full=%d\n",
            allocated, is_empty, is_full);
}

/* 모듈 초기화 */
static int __init resource_bitmap_init(void)
{
    int ids[5];
    int i;

    pr_info("Resource Bitmap Module: Initializing\n");

    /* 비트맵 초기화 (모든 비트를 0으로) */
    bitmap_zero(resource_bitmap, MAX_RESOURCES);

    /* 테스트: 5개 자원 할당 */
    for (i = 0; i < 5; i++) {
        ids[i] = alloc_resource();
    }

    print_allocated_resources();
    print_statistics();

    /* 일부 해제 */
    free_resource(ids[1]);
    free_resource(ids[3]);

    print_allocated_resources();
    print_statistics();

    /* 나머지 해제는 exit에서 */
    return 0;
}

/* 모듈 종료 */
static void __exit resource_bitmap_exit(void)
{
    unsigned long id;

    pr_info("Resource Bitmap Module: Cleaning up\n");

    /* 남은 모든 자원 해제 */
    for_each_set_bit(id, resource_bitmap, MAX_RESOURCES) {
        pr_info("Cleaning up resource %lu\n", id);
        clear_bit(id, resource_bitmap);
    }

    pr_info("All resources freed\n");
}

module_init(resource_bitmap_init);
module_exit(resource_bitmap_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("MINZKN");
MODULE_DESCRIPTION("Bitmap-based resource allocator");

예상 출력

# 모듈 로드
sudo insmod resource_bitmap.ko
dmesg | tail -20

# 예상 출력:
# Resource Bitmap Module: Initializing
# Allocated resource 0
# Allocated resource 1
# Allocated resource 2
# Allocated resource 3
# Allocated resource 4
# === Allocated Resources ===
#   Resource 0
#   Resource 1
#   Resource 2
#   Resource 3
#   Resource 4
# Total: 5/128 allocated
# Free: 123
# Statistics: 5 allocated, empty=0, full=0
# Freed resource 1
# Freed resource 3
# === Allocated Resources ===
#   Resource 0
#   Resource 2
#   Resource 4
# Total: 3/128 allocated
# Free: 125
# Statistics: 3 allocated, empty=0, full=0

주의사항 (Common Pitfalls)

1. 비트 인덱스 범위 초과

/* 잘못된 코드 */
DECLARE_BITMAP(my_bitmap, 64);
set_bit(100, my_bitmap);  /* BUG: 범위 초과 → 메모리 손상 */

/* 올바른 코드 */
#define BITMAP_SIZE 64
DECLARE_BITMAP(my_bitmap, BITMAP_SIZE);
int bit = 100;
if (bit < BITMAP_SIZE)
    set_bit(bit, my_bitmap);

2. 원자성 오해

/* 잘못된 가정: test_bit()도 원자적일 것입니다? */
if (!test_bit(id, bitmap))  /* ← 원자적이지만... */
    set_bit(id, bitmap);      /* ← 여기 사이에 다른 CPU가 개입 가능! */

/* 올바른 패턴: test_and_set_bit 사용 */
if (!test_and_set_bit(id, bitmap)) {
    /* 이 CPU가 비트를 설정했음을 보장 */
    pr_info("Successfully allocated %d\n", id);
}

3. BITS_PER_LONG 가정

/* 나쁜 코드: 64비트를 가정 */
unsigned long bitmap[2];  /* 128비트? 32비트에서는 64비트! */

/* 좋은 코드: BITS_TO_LONGS 사용 */
#define NBITS 128
unsigned long bitmap[BITS_TO_LONGS(NBITS)];  /* 아키텍처 독립 */

4. 초기화 누락

/* BUG: 초기화 없이 사용 */
unsigned long bitmap[4];
if (find_first_zero_bit(bitmap, 256))  /* 쓰레기 값! */

/* 올바른 코드 */
unsigned long bitmap[4];
bitmap_zero(bitmap, 256);
int bit = find_first_zero_bit(bitmap, 256);  /* OK: 0 반환 */

Bitmap 운영 플레이북

비트맵은 빠르지만 경계/원자성 실수에 취약합니다. 특히 멀티코어 환경에서는 test-then-set 패턴을 반드시 원자 연산으로 묶어야 합니다.

# 비트맵 관련 핵심 점검 패턴
git grep -n "test_bit(.*)\\s*.*set_bit" -- "*.c"
git grep -n "find_first_zero_bit" -- "*.c"
git grep -n "BITS_TO_LONGS\\|DECLARE_BITMAP" -- "*.c" "*.h"

cpumask/nodemask 레이아웃

대규모 서버 시스템에서는 128개, 256개, 심지어 4096개 이상의 CPU를 관리해야 합니다. cpumask_t는 이런 환경에서도 효율적으로 CPU 집합을 표현하며, NUMA 시스템에서는 nodemask_t가 노드 단위 메모리 토폴로지(Topology)를 비트맵으로 관리합니다.

cpumask 내부 구현

/* include/linux/cpumask.h - 핵심 구현 */

/* cpumask_t는 DECLARE_BITMAP의 래퍼 */
typedef struct cpumask {
    DECLARE_BITMAP(bits, NR_CPUS);
} cpumask_t;

/* cpumask_set_cpu: 특정 CPU 비트 설정 */
static inline void cpumask_set_cpu(unsigned int cpu,
                                     struct cpumask *dstp)
{
    set_bit(cpumask_check(cpu), cpumask_bits(dstp));
}

/* cpumask_test_cpu: 특정 CPU 비트 테스트 */
static inline int cpumask_test_cpu(int cpu,
                                    const struct cpumask *cpumask)
{
    return test_bit(cpumask_check(cpu), cpumask_bits(cpumask));
}

/* for_each_cpu: 매크로 확장 */
#define for_each_cpu(cpu, mask)                            \
    for ((cpu) = -1;                                      \
         (cpu) = cpumask_next((cpu), (mask)),              \
         (cpu) < nr_cpu_ids;)

/* cpumask_next: 다음 설정된 CPU 찾기 */
static inline unsigned int cpumask_next(int n,
                                        const struct cpumask *srcp)
{
    if (n != -1)
        cpumask_check(n);
    return find_next_bit(cpumask_bits(srcp), nr_cpu_ids, n + 1);
}

nodemask API

/* include/linux/nodemask.h - NUMA 노드 비트맵 */

typedef struct {
    DECLARE_BITMAP(bits, MAX_NUMNODES);
} nodemask_t;

/* 주요 API */
void node_set(int node, nodemask_t *dstp);
void node_clear(int node, nodemask_t *dstp);
int  node_isset(int node, nodemask_t src);

/* 노드 순회 */
int nid;
for_each_online_node(nid) {
    struct pglist_data *pgdat = NODE_DATA(nid);
    pr_info("Node %d: %lu pages\n", nid,
            pgdat->node_present_pages);
}

/* NUMA 친화적 메모리 할당 */
nodemask_t mask = node_to_cpumask_map[target_node];
struct page *page = alloc_pages_node(nid, GFP_KERNEL, 0);

cpumask와 nodemask의 관계

비트맵 탐색 알고리즘

커널의 비트맵 탐색 함수는 단순한 비트 스캔이 아니라, word 단위 건너뛰기와 하드웨어 가속을 결합한 다층 최적화 알고리즘입니다. 이 섹션에서는 find_first_bit()부터 bitmap_find_next_zero_area()까지 내부 구현을 상세히 분석합니다.

find_first_bit / find_next_bit 구현

/* lib/find_bit.c - find_first_bit 구현 (간략화) */

unsigned long _find_first_bit(const unsigned long *addr,
                              unsigned long size)
{
    unsigned long idx;

    /* word 단위로 스캔 — 0이 아닌 word를 찾을 때까지 */
    for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
        if (addr[idx]) {
            /* word 내에서 첫 번째 설정 비트 찾기 */
            unsigned long val = addr[idx];
            unsigned long bit = idx * BITS_PER_LONG + __ffs(val);
            return min(bit, size);
        }
    }
    return size;  /* 설정된 비트 없음 */
}

/* find_next_bit: offset부터 탐색 (부분 word 처리 포함) */
unsigned long _find_next_bit(const unsigned long *addr,
                             unsigned long size,
                             unsigned long offset)
{
    unsigned long tmp;

    if (offset >= size)
        return size;

    /* 첫 번째 부분 word: offset 이전 비트를 마스킹 */
    tmp = addr[offset / BITS_PER_LONG];
    tmp &= BITMAP_FIRST_WORD_MASK(offset);

    while (!tmp) {
        offset = round_up(offset + 1, BITS_PER_LONG);
        if (offset >= size)
            return size;
        tmp = addr[offset / BITS_PER_LONG];
    }

    return min(offset + __ffs(tmp), size);
}

하드웨어 가속: __ffs / __fls / ffz

/* arch/x86/include/asm/bitops.h */

/* __ffs: 최하위 1비트 위치 (BSF 명령어) */
static __always_inline unsigned long __ffs(unsigned long word)
{
    asm volatile("rep; bsf %1,%0"
        : "=r" (word)
        : "rm" (word));
    return word;
}

/* __fls: 최상위 1비트 위치 (BSR 명령어) */
static __always_inline unsigned long __fls(unsigned long word)
{
    asm("bsr %1,%0"
        : "=r" (word)
        : "rm" (word));
    return word;
}

/* ffz: 최하위 0비트 위치 = __ffs(~word) */
static inline unsigned long ffz(unsigned long word)
{
    return __ffs(~word);
}

/* ARM64: CLZ 기반 구현 */
/* arch/arm64/include/asm/bitops.h */
static inline unsigned long __ffs(unsigned long word)
{
    return __builtin_ctzl(word);  /* GCC builtin → CLZ+RBIT */
}

/* RISC-V: Zbb 확장 활용 */
/* arch/riscv/include/asm/bitops.h */
static inline unsigned long __ffs(unsigned long word)
{
    return __builtin_ctzl(word);  /* → ctz 명령어 */
}

bitmap_find_next_zero_area 구현

/* lib/bitmap.c - 연속된 빈 영역 탐색 */
unsigned long bitmap_find_next_zero_area_off(
    unsigned long *map,
    unsigned long size,
    unsigned long start,
    unsigned int  nr,       /* 필요한 연속 비트 수 */
    unsigned long align_mask,
    unsigned long align_offset)
{
    unsigned long index, end, i;

again:
    index = find_next_zero_bit(map, size, start);

    /* 정렬 조건 적용 */
    index = __ALIGN_MASK(index + align_offset, align_mask)
            - align_offset;

    end = index + nr;
    if (end > size)
        return end;  /* 공간 부족 */

    /* index~end 범위에 설정된 비트가 있는지 확인 */
    i = find_next_bit(map, end, index);
    if (i < end) {
        /* 중간에 설정된 비트 발견 → 그 뒤부터 재탐색 */
        start = i + 1;
        goto again;
    }

    return index;  /* 성공: 연속 nr비트 빈 영역 */
}

비트맵 메모리 레이아웃

비트맵은 unsigned long 배열로 구현됩니다. 아키텍처에 따라 BITS_PER_LONG이 32 또는 64이며, 이에 따라 메모리 레이아웃이 달라집니다. 이 차이를 이해하지 못하면 이식성 버그가 발생합니다.

비트맵 레이아웃 관련 핵심 매크로

/* include/linux/bits.h */
#define BIT(nr)           (1UL << (nr))
#define BIT_ULL(nr)       (1ULL << (nr))
#define BIT_MASK(nr)      (1UL << ((nr) % BITS_PER_LONG))
#define BIT_WORD(nr)      ((nr) / BITS_PER_LONG)

/* include/linux/bitmap.h */
#define BITS_PER_BYTE     8
#define BITS_PER_TYPE(type) (sizeof(type) * BITS_PER_BYTE)
#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_LONG)
#define BITS_TO_BYTES(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE)

/* 정적 비트맵 선언 */
#define DECLARE_BITMAP(name, bits) \
    unsigned long name[BITS_TO_LONGS(bits)]

/* 동적 비트맵 할당 */
unsigned long *bitmap = bitmap_zalloc(nbits, GFP_KERNEL);
if (!bitmap)
    return -ENOMEM;

/* 사용 후 해제 */
bitmap_free(bitmap);

/* 주의: 비트 수가 BITS_PER_LONG의 배수가 아닐 때 */
/* 마지막 word의 사용하지 않는 상위 비트는 0이어야 함 */
DECLARE_BITMAP(bmp, 100);  /* unsigned long bmp[2] */
/* bmp[1]의 bit 36~63은 항상 0으로 유지해야 함 */
/* bitmap_zero()는 이를 자동 처리 */

원자적 비트 연산

커널은 동일한 비트 조작에 대해 원자적(atomic) 버전과 비원자적(non-atomic) 버전을 모두 제공합니다. 성능과 안전성 사이의 올바른 선택은 코드의 동시성 모델에 달려 있습니다.

x86 원자적 비트 연산 구현

/* arch/x86/include/asm/bitops.h */

/* set_bit: 원자적으로 비트 설정 */
static __always_inline void
arch_set_bit(long nr, volatile unsigned long *addr)
{
    if (__builtin_constant_p(nr)) {
        /* 컴파일 시점 상수: 최적화된 경로 */
        asm volatile(LOCK_PREFIX "orb %b1,%0"
            : CONST_MASK_ADDR(nr, addr)
            : "iq" (CONST_MASK(nr))
            : "memory");
    } else {
        /* 런타임 변수: BTS 명령어 */
        asm volatile(LOCK_PREFIX "bts %1,%0"
            : BITOP_ADDR(addr)
            : "Ir" (nr)
            : "memory");
    }
}

/* __set_bit: 비원자적 버전 — LOCK 접두사 없음 */
static __always_inline void
arch___set_bit(unsigned long nr, volatile unsigned long *addr)
{
    asm volatile("bts %1,%0"  /* LOCK 없음! */
        : BITOP_ADDR(addr)
        : "Ir" (nr)
        : "memory");
}

/* test_and_set_bit: 원자적 test-and-set */
static __always_inline bool
arch_test_and_set_bit(long nr, volatile unsigned long *addr)
{
    return GEN_BINARY_RMWcc(LOCK_PREFIX "bts",
                             *addr, "Ir", nr, "%0", c);
    /* Carry flag가 이전 비트 값을 나타냄 */
}

Lock-free 플래그 관리 패턴

/* 패턴 1: 원자적 플래그로 일회성 초기화 */
static unsigned long init_flags;
#define FLAG_INITIALIZED 0

void lazy_init(void)
{
    /* 여러 CPU가 동시에 호출해도 정확히 한 번만 초기화 */
    if (test_and_set_bit(FLAG_INITIALIZED, &init_flags))
        return;  /* 이미 다른 CPU가 초기화함 */

    /* 이 CPU만 여기에 도달 — 초기화 수행 */
    do_initialization();
}

/* 패턴 2: 비트 플래그로 상태 머신 구현 */
#define DEV_RUNNING    0
#define DEV_SUSPENDED  1
#define DEV_ERROR      2

struct my_device {
    unsigned long flags;
};

int device_suspend(struct my_device *dev)
{
    /* RUNNING → SUSPENDED 전환 (원자적) */
    if (!test_and_clear_bit(DEV_RUNNING, &dev->flags))
        return -EINVAL;  /* 실행 중이 아님 */

    set_bit(DEV_SUSPENDED, &dev->flags);
    return 0;
}

/* 패턴 3: wait_on_bit — 비트 기반 대기 */
#define PAGE_LOCKED  0

void lock_page(struct page *page)
{
    while (test_and_set_bit(PAGE_LOCKED, &page->flags))
        wait_on_bit(&page->flags, PAGE_LOCKED,
                    TASK_UNINTERRUPTIBLE);
}

void unlock_page(struct page *page)
{
    clear_bit_unlock(PAGE_LOCKED, &page->flags);
    wake_up_bit(&page->flags, PAGE_LOCKED);
}

IRQ 어피니티 비트맵

IRQ 어피니티(affinity)는 특정 인터럽트(Interrupt)를 어떤 CPU에서 처리할지 결정하는 cpumask입니다. 네트워크 성능 최적화, NUMA 친화 I/O, 실시간(Real-time) 시스템 격리(Isolation) 등에서 핵심적인 역할을 합니다.

IRQ 어피니티 커널 API

/* kernel/irq/manage.c - IRQ 어피니티 설정 */

int irq_set_affinity(unsigned int irq,
                     const struct cpumask *mask)
{
    struct irq_desc *desc = irq_to_desc(irq);
    struct irq_chip *chip = desc->irq_data.chip;
    int ret;

    /* 온라인 CPU와 교집합 */
    struct cpumask *effective = irq_data_get_effective_affinity(
                                    &desc->irq_data);

    if (!cpumask_intersects(mask, cpu_online_mask))
        return -EINVAL;

    /* 하드웨어 칩에 어피니티 전달 */
    ret = chip->irq_set_affinity(&desc->irq_data, mask, false);

    if (ret == IRQ_SET_MASK_OK) {
        cpumask_copy(desc->irq_common_data.affinity, mask);
    }

    return ret;
}

/* 드라이버에서의 사용 예: MSI-X 큐별 어피니티 */
static void setup_queue_affinity(struct my_device *dev)
{
    int i;

    for (i = 0; i < dev->num_queues; i++) {
        struct cpumask mask;
        int target_cpu = i % num_online_cpus();

        cpumask_clear(&mask);
        cpumask_set_cpu(target_cpu, &mask);
        irq_set_affinity_hint(dev->irqs[i], &mask);
    }
}

/proc/irq 인터페이스 실습

# IRQ 목록과 현재 어피니티 확인
cat /proc/interrupts | head -20

# 특정 IRQ의 어피니티 확인 (비트마스크 형식)
cat /proc/irq/30/smp_affinity
# 출력 예: 0f (CPU 0-3 모두)

# CPU 리스트 형식으로 확인
cat /proc/irq/30/smp_affinity_list
# 출력 예: 0-3

# IRQ 30을 CPU 0에만 바인딩
echo 1 > /proc/irq/30/smp_affinity

# IRQ 31을 CPU 2,3에 바인딩
echo 0c > /proc/irq/31/smp_affinity

# 리스트 형식으로 설정 (더 직관적)
echo 2-3 > /proc/irq/31/smp_affinity_list

# NIC 큐별 분산 설정 스크립트
for irq in $(grep eth0 /proc/interrupts | awk '{print $1}' | tr -d ':'); do
    cpu=$((irq % $(nproc)))
    echo $cpu > /proc/irq/$irq/smp_affinity_list
    echo "IRQ $irq -> CPU $cpu"
done

스케줄러 비트맵 활용

리눅스 스케줄러는 비트맵을 활용하여 O(1) 시간에 가장 높은 우선순위(Priority)의 실행 가능한 태스크(Task)를 찾습니다. 특히 RT(Real-Time) 스케줄러에서 비트맵은 핵심 자료구조입니다.

rt_prio_array 구조

/* kernel/sched/rt.c - RT 스케줄러 우선순위 배열 */

struct rt_prio_array {
    DECLARE_BITMAP(bitmap, MAX_RT_PRIO + 1);
    struct list_head queue[MAX_RT_PRIO];
};

/* 가장 높은 우선순위 태스크 찾기 */
static inline int sched_find_first_bit(const unsigned long *b)
{
    /* 100비트 비트맵에서 첫 번째 설정된 비트 찾기 */
    return find_first_bit(b, MAX_RT_PRIO);
}

/* RT 태스크 enqueue 시 비트맵 업데이트 */
static void enqueue_rt_entity(struct sched_rt_entity *rt_se)
{
    struct rt_prio_array *array = &rt_rq->active;
    int prio = rt_se->prio;

    list_add_tail(&rt_se->run_list, &array->queue[prio]);
    __set_bit(prio, array->bitmap);  /* 비원자적: rq lock 보호 */
}

/* RT 태스크 dequeue 시 비트맵 업데이트 */
static void dequeue_rt_entity(struct sched_rt_entity *rt_se)
{
    struct rt_prio_array *array = &rt_rq->active;
    int prio = rt_se->prio;

    list_del_init(&rt_se->run_list);

    /* 해당 우선순위 큐가 비면 비트 해제 */
    if (list_empty(&array->queue[prio]))
        __clear_bit(prio, array->bitmap);
}

CPU 선택 비트맵

/* kernel/sched/fair.c - CFS 로드 밸런싱에서의 비트맵 활용 */

/* select_task_rq_fair: 태스크를 실행할 CPU 선택 */
static int select_task_rq_fair(struct task_struct *p, int prev_cpu,
                              int wake_flags)
{
    struct cpumask *cpus = this_cpu_cpumask_var_ptr(select_rq_mask);
    int new_cpu;

    /* 태스크의 허용 CPU와 온라인 CPU의 교집합 */
    cpumask_and(cpus, p->cpus_ptr, cpu_active_mask);

    /* 같은 LLC(Last Level Cache)를 공유하는 CPU 선호 */
    struct cpumask *llc_mask = per_cpu(sd_llc_shared->span, prev_cpu);
    cpumask_and(cpus, cpus, llc_mask);

    /* idle CPU 우선 선택 */
    new_cpu = cpumask_any_and_distribute(cpus, idle_mask);
    if (new_cpu < nr_cpu_ids)
        return new_cpu;

    /* idle CPU가 없으면 가장 부하가 낮은 CPU */
    return find_idlest_cpu(cpus);
}

메모리 관리(Memory Management) 비트맵

리눅스 메모리 관리 서브시스템은 비트맵을 광범위하게 사용합니다. Buddy allocator의 페이지 추적, CMA(Contiguous Memory Allocator)의 연속 영역 관리, 그리고 각 페이지의 플래그(PG_locked, PG_dirty 등)까지 모두 비트맵 기반입니다.

Buddy Allocator 비트맵

/* mm/page_alloc.c - 페이지 할당 시 비트맵 활용 */

/* buddy 상태 토글: 비트 XOR로 추적 */
static inline void __free_one_page(
    struct page *page,
    unsigned long pfn,
    struct zone *zone,
    unsigned int order)
{
    unsigned long buddy_pfn;
    struct page *buddy;

    while (order < MAX_ORDER - 1) {
        buddy_pfn = __find_buddy_pfn(pfn, order);
        buddy = page + (buddy_pfn - pfn);

        /* buddy 비트맵으로 양쪽 블록 상태 확인 */
        if (!page_is_buddy(page, buddy, order))
            break;

        /* 병합: 두 블록을 상위 order로 합침 */
        list_del(&buddy->lru);
        zone->free_area[order].nr_free--;

        /* 비트맵 업데이트 */
        __change_bit(pfn >> (order + 1),
                     zone->free_area[order].map);

        order++;
        pfn &= ~(1UL << order);  /* 정렬된 PFN */
    }
}

/* 페이지 할당: 빈 블록 탐색 */
static struct page *__rmqueue_smallest(
    struct zone *zone,
    unsigned int order,
    int migratetype)
{
    unsigned int current_order;
    struct free_area *area;
    struct page *page;

    for (current_order = order;
         current_order < MAX_ORDER; current_order++) {
        area = &zone->free_area[current_order];
        page = get_page_from_free_area(area, migratetype);
        if (!page)
            continue;

        del_page_from_free_list(page, zone, current_order);
        expand(zone, page, order, current_order, area);
        return page;
    }
    return NULL;
}

CMA 비트맵

/* mm/cma.c - CMA 연속 메모리 할당 */

struct cma {
    unsigned long  base_pfn;
    unsigned long  count;        /* 총 페이지 수 */
    unsigned long *bitmap;       /* 할당 추적 비트맵 */
    unsigned int   order_per_bit;
    struct mutex   lock;
};

/* CMA 영역에서 연속 페이지 할당 */
struct page *cma_alloc(struct cma *cma, size_t count,
                      unsigned int align, bool no_warn)
{
    unsigned long bitmap_count = cma_bitmap_pages_to_bits(cma, count);
    unsigned long start;

    mutex_lock(&cma->lock);

    /* 연속된 빈 비트 영역 탐색 */
    start = bitmap_find_next_zero_area_off(
        cma->bitmap,
        cma_bitmap_maxno(cma),
        0,              /* 탐색 시작 위치 */
        bitmap_count,   /* 필요한 비트 수 */
        mask,           /* 정렬 마스크 */
        offset);

    if (start >= cma_bitmap_maxno(cma)) {
        mutex_unlock(&cma->lock);
        return NULL;  /* 연속 공간 부족 */
    }

    /* 비트맵에 할당 표시 */
    bitmap_set(cma->bitmap, start, bitmap_count);
    mutex_unlock(&cma->lock);

    /* PFN → struct page 변환 */
    return pfn_to_page(cma->base_pfn + (start << cma->order_per_bit));
}

페이지 플래그 비트맵

/* include/linux/page-flags.h - 페이지 플래그 매크로 */

/* 플래그 정의 */
enum pageflags {
    PG_locked,        /* bit 0: 페이지 잠금 */
    PG_referenced,    /* bit 1: 최근 접근됨 */
    PG_uptodate,      /* bit 2: 최신 데이터 */
    PG_dirty,         /* bit 4: 수정됨 */
    PG_lru,           /* bit 5: LRU 리스트 */
    PG_active,        /* bit 6: 활성 리스트 */
    PG_slab,          /* bit 7: SLAB 페이지 */
    PG_reserved,      /* bit 10: 예약됨 */
    PG_compound,      /* bit 14: 복합 페이지 */
    /* ... */
};

/* PAGEFLAG 매크로: 접근 함수 자동 생성 */
#define PAGEFLAG(uname, lname, policy)              \
static __always_inline                             \
bool folio_test_##lname(struct folio *folio)     \
{ return test_bit(PG_##lname, folio_flags(folio)); } \
static __always_inline                             \
void folio_set_##lname(struct folio *folio)      \
{ set_bit(PG_##lname, folio_flags(folio)); }       \
static __always_inline                             \
void folio_clear_##lname(struct folio *folio)    \
{ clear_bit(PG_##lname, folio_flags(folio)); }

/* 사용 예 */
PAGEFLAG(Dirty, dirty, PF_HEAD)
/* → folio_test_dirty(), folio_set_dirty(), folio_clear_dirty() 생성 */

ftrace/perf 디버깅(Debugging) 실습

비트맵 관련 커널 동작을 추적하고 성능을 분석하는 실전 기법입니다. ftrace, bpftrace, perf를 활용하여 비트맵 연산의 호출 빈도와 지연(Latency) 시간을 측정합니다.

ftrace로 비트맵 연산 추적

# ftrace: cpumask 관련 함수 추적
cd /sys/kernel/debug/tracing

# function tracer 활성화
echo function > current_tracer

# cpumask 관련 함수 필터
echo 'cpumask_*' > set_ftrace_filter
echo 'irq_set_affinity' >> set_ftrace_filter

# 추적 시작
echo 1 > tracing_on

# IRQ 어피니티 변경으로 트리거
echo 3 > /proc/irq/30/smp_affinity_list

# 추적 결과 확인
cat trace | head -30
# 예상 출력:
#  irq/30-xxx  [003] ... irq_set_affinity
#  irq/30-xxx  [003] ... cpumask_test_cpu
#  irq/30-xxx  [003] ... cpumask_set_cpu

# 추적 중지 및 정리
echo 0 > tracing_on
echo nop > current_tracer

bpftrace로 cpumask 모니터링

# bpftrace: set_bit 호출 빈도 모니터링
sudo bpftrace -e '
kprobe:irq_set_affinity {
    @irq_affinity_calls = count();
    @irq_nums = hist(arg0);
}

interval:s:10 {
    print(@irq_affinity_calls);
    print(@irq_nums);
}
'

# bpftrace: 비트맵 할당 추적 (CMA)
sudo bpftrace -e '
kprobe:cma_alloc {
    @cma_allocs = count();
    @alloc_sizes = hist(arg1);  /* 요청 페이지 수 */
    printf("CMA alloc: %d pages\n", arg1);
}

kretprobe:cma_alloc {
    @cma_results[retval != 0 ? "success" : "fail"] = count();
}
'

# bpftrace: RT 스케줄러 비트맵 활동
sudo bpftrace -e '
kprobe:enqueue_rt_entity {
    @rt_enqueue = count();
}
kprobe:dequeue_rt_entity {
    @rt_dequeue = count();
}
interval:s:5 {
    printf("RT enqueue: %lld, dequeue: %lld\n",
           @rt_enqueue, @rt_dequeue);
}
'

perf probe 예제

# perf: find_first_bit 성능 프로파일링
sudo perf probe --add 'find_first_bit addr size'
sudo perf record -e probe:find_first_bit -a -- sleep 5
sudo perf report

# perf stat: 비트맵 관련 캐시 성능
sudo perf stat -e cache-misses,cache-references,instructions \
    -p $(pgrep my_bitmap_module) -- sleep 10

# perf: IRQ 처리 지연 시간
sudo perf trace -e irq:irq_handler_entry,irq:irq_handler_exit \
    --duration 100 -- sleep 5

# probe 정리
sudo perf probe --del find_first_bit

성능 분석과 최적화

비트맵은 범용적으로 빠르지만, 사용 패턴에 따라 성능 차이가 크게 납니다. 이 섹션에서는 비트맵, 비트필드, 플래그 변수의 비교와 대규모 비트맵 최적화 기법을 다룹니다.

상세 성능 비교

캐시 최적화 코드 패턴

/* 캐시 라인 정렬된 비트맵 */
struct optimized_bitmap {
    DECLARE_BITMAP(hot_bits, 512);    /* 자주 접근: 1 캐시 라인 */
    DECLARE_BITMAP(cold_bits, 4096);  /* 드물게 접근 */
} ____cacheline_aligned;

/* per-CPU 비트맵: false sharing 완전 방지 */
struct per_cpu_bitmap {
    DECLARE_BITMAP(local, 256);
    unsigned long stats[4];
} ____cacheline_aligned_in_smp;

static DEFINE_PER_CPU(struct per_cpu_bitmap, cpu_bitmaps);

/* 벌크 연산으로 lock 횟수 최소화 */
void batch_allocate(int *ids, int count)
{
    unsigned long flags;
    int i;

    spin_lock_irqsave(&lock, flags);
    for (i = 0; i < count; i++) {
        ids[i] = find_first_zero_bit(bitmap, MAX);
        if (ids[i] < MAX)
            __set_bit(ids[i], bitmap);  /* lock 내부: 비원자적 OK */
    }
    spin_unlock_irqrestore(&lock, flags);
}

/* prefetch 활용 (대규모 비트맵 순회) */
void scan_large_bitmap(unsigned long *bitmap, int nbits)
{
    unsigned long bit;
    int word_idx = 0;

    for_each_set_bit(bit, bitmap, nbits) {
        int new_word = bit / BITS_PER_LONG;
        if (new_word != word_idx) {
            word_idx = new_word;
            /* 다음 캐시 라인 미리 로드 */
            prefetch(&bitmap[word_idx + 8]);
        }
        process_bit(bit);
    }
}

비트맵 활용 패턴 모음

커널 전반에서 반복적으로 사용되는 비트맵 패턴을 정리합니다. 이 패턴들을 이해하면 새로운 서브시스템을 분석할 때 비트맵 활용 방식을 빠르게 파악할 수 있습니다.

커널 서브시스템별 비트맵 패턴

흔한 안티패턴과 해결책

비트맵 코드 리뷰 체크리스트

/*
 * 비트맵 코드 리뷰 시 확인할 사항:
 *
 * 1. 초기화: bitmap_zero() 또는 DEFINE_BITMAP()으로 초기화했는가?
 * 2. 범위 검사: set_bit(nr, bmp)에서 nr < 비트맵_크기인가?
 * 3. 원자성: 멀티코어 접근 시 set_bit() vs __set_bit() 올바른가?
 * 4. 이식성: DECLARE_BITMAP() 사용했는가? (unsigned long[] 직접 X)
 * 5. 순회: for_each_set_bit() 사용했는가? (수동 루프 X)
 * 6. 해제: bitmap_zalloc()이면 bitmap_free() 짝 맞는가?
 * 7. 캐시: 대규모 비트맵은 cacheline_aligned인가?
 * 8. 스택: 큰 비트맵을 스택에 두지 않았는가?
 */

/* 올바른 비트맵 관리 템플릿 */
struct my_subsystem {
    DECLARE_BITMAP(resource_map, MAX_RESOURCES);
    DEFINE_SPINLOCK(lock);
    int max_resources;
};

static int my_alloc(struct my_subsystem *sys)
{
    unsigned long flags;
    int id;

    spin_lock_irqsave(&sys->lock, flags);
    id = find_first_zero_bit(sys->resource_map, sys->max_resources);
    if (id < sys->max_resources)
        __set_bit(id, sys->resource_map);
    spin_unlock_irqrestore(&sys->lock, flags);

    return (id < sys->max_resources) ? id : -ENOSPC;
}

static void my_free(struct my_subsystem *sys, int id)
{
    if (WARN_ON(id < 0 || id >= sys->max_resources))
        return;
    clear_bit(id, sys->resource_map);  /* 원자적: lock 없이 안전 */
}

배치 연산 내부 구현 분석

bitmap_and(), bitmap_or() 등의 배치 연산은 word 단위 루프로 구현되어 있으며, 컴파일러 최적화(Compiler Optimization)와 결합하여 극도로 효율적인 코드를 생성합니다. 이 섹션에서는 실제 커널 소스의 구현 전략을 상세히 분석합니다.

bitmap_and() / bitmap_or() 구현

/* lib/bitmap.c - bitmap_and 구현 */

int __bitmap_and(unsigned long *dst,
                 const unsigned long *bitmap1,
                 const unsigned long *bitmap2,
                 unsigned int nbits)
{
    unsigned int k;
    unsigned int lim = nbits / BITS_PER_LONG;
    unsigned long result = 0;

    /* word 단위 AND — 64비트씩 처리 */
    for (k = 0; k < lim; k++)
        result |= (dst[k] = bitmap1[k] & bitmap2[k]);

    /* 마지막 부분 word 처리: 사용하지 않는 상위 비트 마스킹 */
    if (nbits % BITS_PER_LONG) {
        result |= (dst[k] = bitmap1[k] & bitmap2[k] &
                   BITMAP_LAST_WORD_MASK(nbits));
    }

    /* 결과가 모두 0이면 0 반환 (empty), 아니면 비영(non-zero) 반환 */
    return result != 0;
}

/* bitmap_or 구현 — 반환값 없음 (항상 empty가 아님) */
void __bitmap_or(unsigned long *dst,
                 const unsigned long *bitmap1,
                 const unsigned long *bitmap2,
                 unsigned int nbits)
{
    unsigned int k;
    unsigned int nr = BITS_TO_LONGS(nbits);

    for (k = 0; k < nr; k++)
        dst[k] = bitmap1[k] | bitmap2[k];
}

/* include/linux/bitmap.h - small_const_nbits 최적화 */
static inline int bitmap_and(
    unsigned long *dst,
    const unsigned long *src1,
    const unsigned long *src2,
    unsigned int nbits)
{
    /* 비트 수가 컴파일 시점 상수이고 1 word에 들어가면
     * 함수 호출 없이 단일 AND 연산으로 최적화 */
    if (small_const_nbits(nbits))
        return (*dst = *src1 & *src2 &
                BITMAP_LAST_WORD_MASK(nbits)) != 0;

    return __bitmap_and(dst, src1, src2, nbits);
}

bitmap_complement() / bitmap_xor() 구현

/* lib/bitmap.c - bitmap_xor 구현 */
void __bitmap_xor(unsigned long *dst,
                  const unsigned long *bitmap1,
                  const unsigned long *bitmap2,
                  unsigned int nbits)
{
    unsigned int k;
    unsigned int nr = BITS_TO_LONGS(nbits);

    for (k = 0; k < nr; k++)
        dst[k] = bitmap1[k] ^ bitmap2[k];
}

/* bitmap_complement: 모든 비트 반전 */
void __bitmap_complement(unsigned long *dst,
                        const unsigned long *src,
                        unsigned int nbits)
{
    unsigned int k;
    unsigned int nr = BITS_TO_LONGS(nbits);

    for (k = 0; k < nr; k++)
        dst[k] = ~src[k];
    /* 주의: 마지막 word의 잔여 비트는 호출자가 마스킹해야 합니다 */
}

/* bitmap_weight: popcount(설정된 비트 수) — hweight 활용 */
unsigned int __bitmap_weight(const unsigned long *bitmap,
                            unsigned int nbits)
{
    unsigned int k, w = 0, lim = nbits / BITS_PER_LONG;

    for (k = 0; k < lim; k++)
        w += hweight_long(bitmap[k]);
        /* hweight_long: x86에서 POPCNT 명령어 활용 */

    if (nbits % BITS_PER_LONG)
        w += hweight_long(bitmap[k] &
                           BITMAP_LAST_WORD_MASK(nbits));
    return w;
}

ARM64 원자적 비트 연산 분석

x86의 LOCK BTS 명령어와 달리, ARM64는 LSE(Large System Extensions) 유무에 따라 두 가지 구현 경로를 사용합니다. LSE가 있으면 단일 원자 명령어(LDSET/LDCLR)를, 없으면 LL/SC (Load-Link/Store-Conditional) 루프를 사용합니다.

ARM64 set_bit() — LSE vs LL/SC

/* arch/arm64/include/asm/bitops.h */

/*
 * ARM64 set_bit 구현: 두 가지 경로
 * 1) LSE 확장이 있으면: LDSET 단일 명령어
 * 2) LSE가 없으면: LDXR/STXR 루프 (Load-Exclusive/Store-Exclusive)
 */

/* LSE 경로: arch/arm64/include/asm/lse.h + atomic_ll_sc.h */
static inline void arch_set_bit(unsigned int nr,
                               volatile unsigned long *p)
{
    unsigned long mask = BIT_MASK(nr);

    p += BIT_WORD(nr);

    /* LSE 지원 시: 단일 원자 OR 명령어 */
    asm volatile(
        "  ldset   %[mask], xzr, %[addr]\n"
        : [addr] "+Q" (*p)
        : [mask] "r" (mask)
        : "memory"
    );
}

/* LL/SC 경로: LSE 미지원 시 (ARMv8.0) */
static inline void arch_set_bit_llsc(unsigned int nr,
                                    volatile unsigned long *p)
{
    unsigned long mask = BIT_MASK(nr);
    unsigned long tmp;

    p += BIT_WORD(nr);

    asm volatile(
        "1: ldxr   %[tmp], %[addr]\n"     /* 배타적 로드 */
        "   orr    %[tmp], %[tmp], %[mask]\n" /* OR 연산 */
        "   stxr   %w[res], %[tmp], %[addr]\n" /* 배타적 저장 */
        "   cbnz   %w[res], 1b\n"         /* 실패 시 재시도 */
        : [addr] "+Q" (*p),
          [tmp] "=&r" (tmp),
          [res] "=&r" (tmp)
        : [mask] "r" (mask)
        : "memory"
    );
}

ARM64 test_and_set_bit()

/* ARM64 test_and_set_bit: 이전 비트 값을 반환 */
static inline int arch_test_and_set_bit(unsigned int nr,
                                       volatile unsigned long *p)
{
    unsigned long mask = BIT_MASK(nr);
    unsigned long old;

    p += BIT_WORD(nr);

    /* LSE: LDSET는 이전 값을 반환 */
    asm volatile(
        "  ldset   %[mask], %[old], %[addr]\n"
        : [addr] "+Q" (*p),
          [old] "=r" (old)
        : [mask] "r" (mask)
        : "memory"
    );

    /* 이전 값에서 해당 비트가 설정되어 있었는지 확인 */
    return !!(old & mask);
}

/* clear_bit: LSE LDCLR 사용 */
static inline void arch_clear_bit(unsigned int nr,
                                 volatile unsigned long *p)
{
    unsigned long mask = BIT_MASK(nr);

    p += BIT_WORD(nr);

    /* LDCLR: 원자적으로 지정 비트 제거 */
    asm volatile(
        "  ldclr   %[mask], xzr, %[addr]\n"
        : [addr] "+Q" (*p)
        : [mask] "r" (mask)
        : "memory"
    );
}

/* test_bit: 비원자적 읽기 — 배리어 불필요 */
static inline int arch_test_bit(unsigned int nr,
                               const volatile unsigned long *p)
{
    /* test_bit은 읽기 전용 — 원자 명령어 불필요 */
    return 1UL & (p[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG - 1)));
}

cpumask 래퍼 내부 구현 분석

cpumask_t는 비트맵의 가장 중요한 래퍼(wrapper)로, 단순히 비트맵 API를 호출하는 것 이상의 최적화와 안전 장치를 포함합니다. 이 섹션에서는 cpumask 래퍼가 비트맵을 어떻게 감싸는지 내부 구현을 상세히 분석합니다.

cpumask 래퍼 구현 패턴

/* include/linux/cpumask.h - cpumask 핵심 래퍼 */

/* cpumask_t 구조: 비트맵 배열을 감싼 구조체 */
typedef struct cpumask {
    DECLARE_BITMAP(bits, NR_CPUS);
    /* 확장: unsigned long bits[BITS_TO_LONGS(NR_CPUS)] */
} cpumask_t;

/* cpumask_bits: 내부 비트맵 배열 접근자 */
static inline unsigned long *cpumask_bits(struct cpumask *maskp)
{
    return maskp->bits;
}

/* cpumask_set_cpu: set_bit 래퍼 */
static inline void cpumask_set_cpu(unsigned int cpu,
                                   struct cpumask *dstp)
{
    set_bit(cpumask_check(cpu), cpumask_bits(dstp));
}

/* cpumask_check: CONFIG_DEBUG_PER_CPU_MAPS에서 범위 검사 */
static inline unsigned int cpumask_check(unsigned int cpu)
{
#ifdef CONFIG_DEBUG_PER_CPU_MAPS
    WARN_ON_ONCE(cpu >= nr_cpu_ids);
#endif
    return cpu;
}

/* cpumask_and: bitmap_and를 감싸면서 nr_cpumask_bits 사용 */
static inline int cpumask_and(struct cpumask *dstp,
                             const struct cpumask *src1p,
                             const struct cpumask *src2p)
{
    return bitmap_and(cpumask_bits(dstp),
                      cpumask_bits(src1p),
                      cpumask_bits(src2p),
                      nr_cpumask_bits);
    /* nr_cpumask_bits = NR_CPUS (정적) 또는 nr_cpu_ids (동적) */
}

/* for_each_cpu: find_next_bit 기반 CPU 순회 */
#define for_each_cpu(cpu, mask)                    \
    for ((cpu) = -1;                                \
         (cpu) = cpumask_next((cpu), (mask)),       \
         (cpu) < nr_cpu_ids; )

static inline unsigned int cpumask_next(int n,
                                       const struct cpumask *srcp)
{
    /* n+1 위치부터 다음 설정 비트 탐색 */
    return find_next_bit(cpumask_bits(srcp),
                         nr_cpumask_bits, n + 1);
}

cpumask_var_t: 동적 할당 패턴

/* include/linux/cpumask.h - cpumask_var_t 구현 */

/*
 * NR_CPUS가 작으면(≤ CPUMASK_OFFSTACK_THRESHOLD) 스택에 할당,
 * 크면 동적 할당하여 스택 오버플로 방지
 */

#if NR_CPUS > CPUMASK_OFFSTACK_THRESHOLD
/* 대규모 시스템: 동적 할당 (포인터) */
typedef struct cpumask *cpumask_var_t;

static inline bool alloc_cpumask_var(cpumask_var_t *mask,
                                     gfp_t flags)
{
    *mask = kmalloc(cpumask_size(), flags);
    return *mask != NULL;
}

static inline void free_cpumask_var(cpumask_var_t mask)
{
    kfree(mask);
}

#else
/* 소규모 시스템: 스택에 직접 할당 (배열) */
typedef struct cpumask cpumask_var_t[1];

static inline bool alloc_cpumask_var(cpumask_var_t *mask,
                                     gfp_t flags)
{
    return true;  /* 스택 할당이므로 항상 성공 */
}

static inline void free_cpumask_var(cpumask_var_t mask)
{
    /* 아무것도 하지 않음 — 스택이 자동 해제 */
}
#endif

/* 사용 예: NR_CPUS에 관계없이 동일한 코드 */
int my_function(void)
{
    cpumask_var_t tmp_mask;

    if (!alloc_cpumask_var(&tmp_mask, GFP_KERNEL))
        return -ENOMEM;

    cpumask_and(tmp_mask, cpu_online_mask, task->cpus_ptr);
    /* ... tmp_mask 사용 ... */

    free_cpumask_var(tmp_mask);
    return 0;
}

find_first_bit 스캔 알고리즘 시각화

find_first_bit()은 비트맵에서 가장 먼저 설정된 비트를 찾는 핵심 함수입니다. 이 알고리즘은 word 단위로 건너뛰며 0이 아닌 word를 발견하면 하드웨어 명령어(__ffs)로 word 내 첫 번째 비트를 즉시 찾아냅니다. 아래 다이어그램은 256비트 비트맵에서의 스캔 과정을 보여줍니다.

실습: 비트맵 기반 자원 추적 커널 모듈

비트맵을 활용한 자원 관리의 실전 패턴을 보여주는 커널 모듈 예제입니다. 가상 장치의 채널(Channel) 할당/해제를 비트맵으로 추적하며, 연속 채널 할당, 통계 조회, proc 인터페이스까지 완전한 구현을 포함합니다.

채널 할당자 커널 모듈

/*
 * bitmap_tracker.c — 비트맵 기반 채널 자원 추적 모듈
 *
 * 기능:
 *   - 개별 채널 할당/해제 (find_first_zero_bit + set_bit)
 *   - 연속 채널 할당 (bitmap_find_next_zero_area)
 *   - /proc/bitmap_tracker 통계 조회
 *   - 디버깅용 비트맵 덤프
 */

#include <linux/module.h>
#include <linux/bitmap.h>
#include <linux/spinlock.h>
#include <linux/proc_fs.h>
#include <linux/seq_file.h>

#define MAX_CHANNELS  256
#define DEVICE_NAME   "bitmap_tracker"

struct channel_tracker {
    DECLARE_BITMAP(channel_map, MAX_CHANNELS);
    spinlock_t     lock;
    unsigned int   total_allocs;
    unsigned int   total_frees;
    unsigned int   peak_usage;
};

static struct channel_tracker tracker;

/* 단일 채널 할당: 가장 낮은 빈 채널 반환 */
static int channel_alloc(void)
{
    unsigned long flags;
    int ch, usage;

    spin_lock_irqsave(&tracker.lock, flags);

    ch = find_first_zero_bit(tracker.channel_map, MAX_CHANNELS);
    if (ch >= MAX_CHANNELS) {
        spin_unlock_irqrestore(&tracker.lock, flags);
        pr_warn("%s: no free channels\n", DEVICE_NAME);
        return -ENOSPC;
    }

    __set_bit(ch, tracker.channel_map);
    tracker.total_allocs++;

    /* 피크 사용량 갱신 */
    usage = bitmap_weight(tracker.channel_map, MAX_CHANNELS);
    if (usage > tracker.peak_usage)
        tracker.peak_usage = usage;

    spin_unlock_irqrestore(&tracker.lock, flags);

    pr_info("%s: allocated channel %d\n", DEVICE_NAME, ch);
    return ch;
}

/* 연속 채널 할당: count개의 연속 채널 확보 */
static int channel_alloc_contiguous(unsigned int count)
{
    unsigned long flags;
    int start, i, usage;

    if (count == 0 || count > MAX_CHANNELS)
        return -EINVAL;

    spin_lock_irqsave(&tracker.lock, flags);

    /* bitmap_find_next_zero_area: 연속 빈 영역 탐색 */
    start = bitmap_find_next_zero_area(
        tracker.channel_map, MAX_CHANNELS,
        0,     /* 시작 위치 */
        count, /* 필요한 연속 비트 수 */
        0      /* 정렬 마스크 (0 = 정렬 무관) */
    );

    if (start + count > MAX_CHANNELS) {
        spin_unlock_irqrestore(&tracker.lock, flags);
        pr_warn("%s: no %u contiguous channels\n",
                DEVICE_NAME, count);
        return -ENOSPC;
    }

    /* 연속 채널 일괄 설정 */
    bitmap_set(tracker.channel_map, start, count);
    tracker.total_allocs += count;

    usage = bitmap_weight(tracker.channel_map, MAX_CHANNELS);
    if (usage > tracker.peak_usage)
        tracker.peak_usage = usage;

    spin_unlock_irqrestore(&tracker.lock, flags);

    pr_info("%s: allocated channels %d-%d\n",
            DEVICE_NAME, start, start + count - 1);
    return start;
}

/* 채널 해제 */
static void channel_free(int ch)
{
    if (ch < 0 || ch >= MAX_CHANNELS) {
        pr_err("%s: invalid channel %d\n", DEVICE_NAME, ch);
        return;
    }

    /* 원자적 clear: lock 없이도 안전 (단일 비트 연산) */
    if (!test_and_clear_bit(ch, tracker.channel_map)) {
        pr_warn("%s: channel %d was not allocated\n",
                DEVICE_NAME, ch);
        return;
    }

    spin_lock(&tracker.lock);
    tracker.total_frees++;
    spin_unlock(&tracker.lock);

    pr_info("%s: freed channel %d\n", DEVICE_NAME, ch);
}

/* /proc/bitmap_tracker: 상태 조회 */
static int tracker_show(struct seq_file *m, void *v)
{
    unsigned long flags;
    int used, ch;

    spin_lock_irqsave(&tracker.lock, flags);

    used = bitmap_weight(tracker.channel_map, MAX_CHANNELS);

    seq_printf(m, "Channel Bitmap Tracker\n");
    seq_printf(m, "======================\n");
    seq_printf(m, "Total channels: %d\n", MAX_CHANNELS);
    seq_printf(m, "Used:           %d\n", used);
    seq_printf(m, "Free:           %d\n", MAX_CHANNELS - used);
    seq_printf(m, "Peak usage:     %u\n", tracker.peak_usage);
    seq_printf(m, "Total allocs:   %u\n", tracker.total_allocs);
    seq_printf(m, "Total frees:    %u\n", tracker.total_frees);

    /* 할당된 채널 목록 출력 */
    seq_printf(m, "\nAllocated channels: ");
    for_each_set_bit(ch, tracker.channel_map, MAX_CHANNELS) {
        seq_printf(m, "%d ", ch);
    }
    seq_printf(m, "\n");

    /* 비트맵 16진수 덤프 */
    seq_printf(m, "\nBitmap hex dump:\n");
    seq_printf(m, "  ");
    bitmap_print_to_pagebuf(true, m->buf + m->count,
                            tracker.channel_map, MAX_CHANNELS);

    spin_unlock_irqrestore(&tracker.lock, flags);
    return 0;
}

static int tracker_open(struct inode *inode, struct file *file)
{
    return single_open(file, tracker_show, NULL);
}

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

/* 모듈 초기화: 테스트용 할당 수행 */
static int __init tracker_init(void)
{
    int ch1, ch2, ch_block;

    spin_lock_init(&tracker.lock);
    bitmap_zero(tracker.channel_map, MAX_CHANNELS);

    /* 테스트: 개별 채널 할당 */
    ch1 = channel_alloc();       /* → 채널 0 */
    ch2 = channel_alloc();       /* → 채널 1 */

    /* 테스트: 연속 4채널 할당 */
    ch_block = channel_alloc_contiguous(4);  /* → 채널 2~5 */

    /* 테스트: 중간 채널 해제 후 재할당 */
    channel_free(ch1);            /* 채널 0 해제 */
    ch1 = channel_alloc();       /* → 채널 0 (재사용) */

    /* proc 인터페이스 생성 */
    proc_create(DEVICE_NAME, 0444, NULL, &tracker_pops);

    pr_info("%s: initialized (%d channels)\n",
            DEVICE_NAME, MAX_CHANNELS);
    return 0;
}

static void __exit tracker_exit(void)
{
    int remaining;

    remove_proc_entry(DEVICE_NAME, NULL);

    remaining = bitmap_weight(tracker.channel_map, MAX_CHANNELS);
    if (remaining)
        pr_warn("%s: %d channels still allocated!\n",
                DEVICE_NAME, remaining);

    pr_info("%s: unloaded\n", DEVICE_NAME);
}

module_init(tracker_init);
module_exit(tracker_exit);
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("Bitmap-based channel resource tracker");

Makefile과 실행 결과

# Makefile
obj-m := bitmap_tracker.o
KDIR := /lib/modules/$(shell uname -r)/build

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

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

# 빌드 및 적재
make
sudo insmod bitmap_tracker.ko

# dmesg로 할당 과정 확인
dmesg | tail -10
# [  xxx] bitmap_tracker: allocated channel 0
# [  xxx] bitmap_tracker: allocated channel 1
# [  xxx] bitmap_tracker: allocated channels 2-5
# [  xxx] bitmap_tracker: freed channel 0
# [  xxx] bitmap_tracker: allocated channel 0
# [  xxx] bitmap_tracker: initialized (256 channels)

# proc 인터페이스로 상태 확인
cat /proc/bitmap_tracker
# Channel Bitmap Tracker
# ======================
# Total channels: 256
# Used:           6
# Free:           250
# Peak usage:     6
# Total allocs:   7
# Total frees:    1
#
# Allocated channels: 0 1 2 3 4 5

# 정리
sudo rmmod bitmap_tracker

per-CPU 비트맵 활용 예제

/*
 * percpu_bitmap.c — per-CPU 비트맵으로 lock-free 자원 관리
 *
 * 각 CPU가 독립적인 비트맵을 보유하여 lock 경합 없이
 * 자원을 할당/해제합니다. 전체 통계 조회 시에만 모든
 * CPU의 비트맵을 합산합니다.
 */

#include <linux/module.h>
#include <linux/bitmap.h>
#include <linux/percpu.h>
#include <linux/cpumask.h>

#define SLOTS_PER_CPU  64

struct percpu_slots {
    DECLARE_BITMAP(bitmap, SLOTS_PER_CPU);
    unsigned int   alloc_count;
};

static DEFINE_PER_CPU(struct percpu_slots, cpu_slots);

/* 현재 CPU에서 슬롯 할당 (preemption 비활성 필요) */
static int slot_alloc_local(void)
{
    struct percpu_slots *slots;
    int bit;

    /* preempt_disable로 CPU 마이그레이션 방지 */
    preempt_disable();
    slots = this_cpu_ptr(&cpu_slots);

    bit = find_first_zero_bit(slots->bitmap, SLOTS_PER_CPU);
    if (bit < SLOTS_PER_CPU) {
        /* 비원자적 __set_bit: per-CPU이므로 안전 */
        __set_bit(bit, slots->bitmap);
        slots->alloc_count++;
    }

    preempt_enable();
    return (bit < SLOTS_PER_CPU) ?
           smp_processor_id() * SLOTS_PER_CPU + bit : -ENOSPC;
}

/* 전체 CPU 통계 합산 */
static int slot_count_total(void)
{
    int cpu, total = 0;

    for_each_online_cpu(cpu) {
        struct percpu_slots *slots = per_cpu_ptr(&cpu_slots, cpu);
        total += bitmap_weight(slots->bitmap, SLOTS_PER_CPU);
    }

    return total;
}

/* cpumask 활용: 사용 중인 슬롯이 있는 CPU 집합 */
static void slot_get_active_cpus(struct cpumask *result)
{
    int cpu;

    cpumask_clear(result);
    for_each_online_cpu(cpu) {
        struct percpu_slots *slots = per_cpu_ptr(&cpu_slots, cpu);

        /* 해당 CPU에 할당된 슬롯이 있으면 마스크에 추가 */
        if (!bitmap_empty(slots->bitmap, SLOTS_PER_CPU))
            cpumask_set_cpu(cpu, result);
    }
}

비트맵과 캐시 라인(Cache Line) 관계

비트맵의 성능을 제대로 이해하려면 캐시 라인과의 관계를 알아야 합니다. 64바이트 캐시 라인은 512비트를 담을 수 있으므로, 512개 이하의 자원을 관리하는 비트맵은 단 하나의 캐시 라인에 완전히 들어갑니다. 이는 비트맵의 캐시 친화성이 뛰어난 핵심 이유입니다.

/* 캐시 라인 정렬된 비트맵 선언 */
struct aligned_bitmap {
    DECLARE_BITMAP(bits, 1024);
} ____cacheline_aligned;
/* ____cacheline_aligned: 캐시 라인 경계에 정렬하여
 * false sharing 방지 및 prefetch 효율 최대화 */

/* 대규모 비트맵 순회 시 prefetch 활용 패턴 */
static void scan_large_bitmap(const unsigned long *bitmap,
                              unsigned long nbits)
{
    unsigned long bit;
    unsigned int next_cacheline = 0;

    for_each_set_bit(bit, bitmap, nbits) {
        unsigned int word = bit / BITS_PER_LONG;

        /* 다음 캐시 라인에 진입할 때마다 미리 로드 */
        if (word >= next_cacheline) {
            /* 8 words = 1 cache line ahead */
            prefetch(&bitmap[word + 8]);
            next_cacheline = word + 8;
        }

        process_bit(bit);
    }
}

Linux 6.12 ~ 7.0 Bitmap 동향

Bitmap API는 2024~2026년 사이에 임의 비트 범위에 대한 제네릭 접근자, sparse 복사, 결합 population-count 같은 고수준 연산이 꾸준히 추가되었습니다. 수작업 shift·mask 패턴을 표준 API로 대체하는 흐름이 주축이며, 대규모 CPU 시스템에서 마스크 검색 핫패스도 벡터화되었습니다. 6.18에서는 커널 메모리 서브시스템의 플래그(flags) 워드 자체가 비트맵으로 전환되는 중요한 변화가 이루어졌습니다.

관련 문서

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

• Linked List — list_head 자료구조
• Red-Black Tree — 정렬된 자료구조
• Hash Table — 해시 테이블(Hash Table)
• 메모리 관리 개요 — 페이지 프레임 할당
• 동기화 기법 — 원자적 연산

참고자료

• include/linux/bitmap.h — Bootlin Elixir — 비트맵 인라인 함수(Inline Function)와 매크로가 정의된 핵심 헤더 파일입니다.
• lib/bitmap.c — Bootlin Elixir — bitmap_parselist(), bitmap_print_to_pagebuf() 등 비트맵 라이브러리 함수의 구현 코드입니다.
• include/linux/cpumask.h — Bootlin Elixir — 비트맵 기반 CPU 마스크 자료구조의 정의와 조작 API입니다.
• include/linux/nodemask.h — Bootlin Elixir — NUMA 노드 마스크 자료구조로, cpumask와 유사한 비트맵 래퍼입니다.
• include/asm-generic/bitops/ — Bootlin Elixir — find_bit, atomic, non-atomic 등 아키텍처 독립적 비트 연산의 제네릭 구현입니다.
• lib/find_bit.c — Bootlin Elixir — find_first_bit(), find_next_bit() 등 비트 탐색 함수의 구현 코드입니다.
• Kernel API — Bitmap Operations — 커널 공식 문서에서 제공하는 비트맵 연산 API 레퍼런스입니다.
• LWN: Modernizing cpumask (2016) — cpumask의 내부 구현 변경과 비트맵 활용 방식의 발전 과정을 다룬 기사입니다.
• LWN: Optimizing find_bit() (2012) — find_first_bit(), find_next_bit() 등 비트 탐색 함수의 성능 최적화 논의입니다.
• LWN: Dynamic per-CPU cpumasks (2010) — 동적 할당 cpumask와 cpumask_var_t 도입 배경을 설명하는 기사입니다.
• LWN Kernel Index — Bitmaps — LWN에서 비트맵 관련 기사를 모아 놓은 색인 페이지입니다.
• LWN: md/llbitmap — introduce a new lockless bitmap (2025) — 6.18에 도입된 MD 소프트웨어 RAID용 잠금(Lock) 없는 비트맵(md-llbitmap)의 설계와 구현을 다루는 LWN 기사입니다. CONFIG_MD_LLBITMAP 구성과 RAID 재동기화 경로의 잠금 경합(Lock Contention) 제거 배경을 설명합니다.
• Phoronix: Linux 6.18 Block Code Introduces Lockless Bitmap For Software RAID — 6.18의 MD 잠금 없는 비트맵 도입을 소개하는 기사입니다. io_uring 블록 코드 변경과 함께 다룹니다.
• CPU Hotplug — Kernel Docs — cpumask를 활용한 CPU 핫플러그 메커니즘의 공식 문서입니다.