Bitmap

Linux 커널의 가장 기본적인 자료구조인 비트맵의 개념, 비트 연산 최적화, cpumask를 포함한 다양한 API, 페이지 프레임 할당자와 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()는 원자적 연산으로 동기화 비용이 낮습니다.
• 캐시 효율 — 연속 메모리 배치로 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 Bit Operations)

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

/* 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);
}

비트맵 순회 매크로 (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)

간단한 자원 할당자를 비트맵으로 구현하는 커널 모듈입니다. 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가 노드 단위 메모리 토폴로지를 비트맵으로 관리합니다.

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)는 특정 인터럽트를 어떤 CPU에서 처리할지 결정하는 cpumask입니다. 네트워크 성능 최적화, NUMA 친화 I/O, 실시간 시스템 격리 등에서 핵심적인 역할을 합니다.

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) 시간에 가장 높은 우선순위의 실행 가능한 태스크를 찾습니다. 특히 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);
}

메모리 관리 비트맵

리눅스 메모리 관리 서브시스템은 비트맵을 광범위하게 사용합니다. 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 디버깅 실습

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

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과 관련된 다른 주제를 더 깊이 이해하고 싶다면 다음 문서를 참고하세요.

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