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"

관련 문서

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

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