Sphinx's Notes

Appearance

Linux lib 子系统深度分析 R2 ​

目录 ​

  1. Bitmap 子系统
  2. Radix-Tree 子系统
  3. IDR/IDA 子系统
  4. Command Line 解析器
  5. 知识点关联表格

1. Bitmap 子系统 ​

1.1 数据结构设计 ​

Bitmap 是 Linux 内核中用于管理位图的核心子系统，提供了高效的位操作能力。

内存分配函数架构 (lib/bitmap.c):

c
// 第 723-728 行: 基础内存分配
unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags)
{
    return kmalloc_array(BITS_TO_LONGS(nbits), sizeof(unsigned long), flags);
}

// 第 736-740 行: NUMA aware 节点分配
unsigned long *bitmap_alloc_node(unsigned int nbits, gfp_t flags, int node)
{
    return kmalloc_array_node(BITS_TO_LONGS(nbits), sizeof(unsigned long),
                              flags, node);
}

核心特点:

  • bitmap_alloc 使用 kmalloc_array 分配连续物理内存
  • bitmap_alloc_node 使用 kmalloc_array_node 在指定 NUMA 节点分配内存
  • bitmap_zalloc 在分配时设置 __GFP_ZERO 标志，零初始化 bitmap

1.2 Bitmap Set/Clear 实现分析 ​

__bitmap_set 函数 (lib/bitmap.c 第 364-383 行):

c
void __bitmap_set(unsigned long *map, unsigned int start, int len)
{
    unsigned long *p = map + BIT_WORD(start);  // 计算起始字
    const unsigned int size = start + len;
    int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
    unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);

    while (len - bits_to_set >= 0) {
        *p |= mask_to_set;          // 设置整 word
        len -= bits_to_set;
        bits_to_set = BITS_PER_LONG;
        mask_to_set = ~0UL;         // 全 1 mask
        p++;
    }
    if (len) {
        mask_to_set &= BITMAP_LAST_WORD_MASK(size);
        *p |= mask_to_set;         // 处理尾部不完整的 word
    }
}

算法流程:

  1. 计算起始地址所在的 word 和需要设置的位数
  2. 先处理第一个 word 中不完整的部分
  3. 然后用全 word mask 设置中间完整的 words
  4. 最后处理尾部不完整的 word

并发安全性分析:

  • __bitmap_set/clear 本身不是原子操作
  • 调用者需要使用锁（如 spinlock）保护临界区
  • 对于单 bit 操作（set_bit/clear_bit），在大多数架构上是原子的

1.3 bitmap_find_next_zero_area_off 并发安全搜索 ​

函数实现 (lib/bitmap.c 第 419-442 行):

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;  // 超出范围

    i = find_next_bit(map, end, index);  // 确认连续区域确实为空
    if (i < end) {
        start = i + 1;
        goto again;  // 冲突，重试
    }
    return index;
}

并发安全机制:

  1. 乐观锁策略: 找到候选区域后再次验证
  2. Goto 重试模式: 检测到竞争时从新位置重新开始搜索
  3. 对齐约束: 通过 align_mask 确保分配区域满足对齐要求

1.4 NUMA Aware 实现 ​

NUMA 感知分配路径:

c
// include/linux/bitmap.h 第 135-136 行
unsigned long *bitmap_alloc_node(unsigned int nbits, gfp_t flags, int node);
unsigned long *bitmap_zalloc_node(unsigned int nbits, gfp_t flags, int node);

NUMA 策略:

  • kmalloc_array_node: 在特定节点分配内存，减少跨节点访问
  • 配合 __GFP_THISNODE 强制本节点分配
  • 通过 numa_mem_id() 获取本地节点 ID

2. Radix-Tree 子系统 ​

2.1 分层节点结构 ​

Radix Tree 底层基于 XArray 实现 (include/linux/xarray.h 第 1168-1184 行):

c
struct xa_node {
    unsigned char   shift;      /* 每个 slot 剩余位数 */
    unsigned char   offset;     /* 在父节点中的偏移 */
    unsigned char   count;      /* 条目总数 */
    unsigned char   nr_values;  /* 值条目计数 */
    struct xa_node __rcu *parent;  /* 指向父节点 */
    struct xarray  *array;     /* 所属数组 */
    union {
        struct list_head private_list;  /* 树用户使用 */
        struct rcu_head  rcu_head;     /* 释放时使用 */
    };
    void __rcu  *slots[XA_CHUNK_SIZE];  /* 槽位数组 */
    union {
        unsigned long   tags[XA_MAX_MARKS][XA_MARK_LONGS];
        unsigned long   marks[XA_MAX_MARKS][XA_MARK_LONGS];
    };
};

树形结构图解:

xa_head (根指针)
    │
    ├── NULL (空树)
    │
    ├── 叶子条目 (直接存储指针)
    │
    └── xa_node (内部节点)
            ├── shift = 6 (每层 6 位)
            ├── slots[64] (XA_CHUNK_SIZE = 64)
            ├── tags[3][2] (3 种标签)
            └── parent --> 父节点或 NULL

RADIX_TREE_MAP_SHIFT 定义 (include/linux/radix-tree.h 第 63 行):

c
#define RADIX_TREE_MAP_SHIFT   XA_CHUNK_SHIFT  // 通常为 6
#define RADIX_TREE_MAP_SIZE    (1UL << RADIX_TREE_MAP_SHIFT)  // 64

2.2 标签机制 (Tagged Pointer) ​

条目编码 (include/linux/radix-tree.h 第 37-58 行):

c
/* 底部两位决定条目的解释方式:
 * 00 - 数据指针
 * 10 - 内部条目
 * x1 - 值条目
 */
#define RADIX_TREE_ENTRY_MASK      3UL
#define RADIX_TREE_INTERNAL_NODE   2UL

static inline bool radix_tree_is_internal_node(void *ptr)
{
    return ((unsigned long)ptr & RADIX_TREE_ENTRY_MASK) ==
                    RADIX_TREE_INTERNAL_NODE;
}

标签操作函数 (lib/radix-tree.c):

c
// 第 100-104 行: 设置标签
static inline void tag_set(struct radix_tree_node *node, unsigned int tag, int offset)
{
    __set_bit(offset, node->tags[tag]);
}

// 第 106-110 行: 清除标签
static inline void tag_clear(struct radix_tree_node *node, unsigned int tag, int offset)
{
    __clear_bit(offset, node->tags[tag]);
}

// 第 112-116 行: 获取标签
static inline int tag_get(const struct radix_tree_node *node, unsigned int tag, int offset)
{
    return test_bit(offset, node->tags[tag]);
}

2.3 Concurrent 锁策略 ​

Per-CPU 预加载机制 (lib/radix-tree.c 第 62-65 行):

c
DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = {
    .lock = INIT_LOCAL_LOCK(lock),
};

预加载实现 (lib/radix-tree.c 第 322-354 行):

c
static __must_check int __radix_tree_preload(gfp_t gfp_mask, unsigned nr)
{
    struct radix_tree_preload *rtp;
    struct radix_tree_node *node;
    int ret = -ENOMEM;

    gfp_mask &= ~__GFP_ACCOUNT;  // 不计入 memory cgroup

    local_lock(&radix_tree_preloads.lock);
    rtp = this_cpu_ptr(&radix_tree_preloads);
    while (rtp->nr < nr) {
        local_unlock(&radix_tree_preloads.lock);
        node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
        if (node == NULL)
            goto out;
        local_lock(&radix_tree_preloads.lock);
        rtp = this_cpu_ptr(&radix_tree_preloads);
        if (rtp->nr < nr) {
            node->parent = rtp->nodes;
            rtp->nodes = node;
            rtp->nr++;
        } else {
            kmem_cache_free(radix_tree_node_cachep, node);
        }
    }
    ret = 0;
out:
    return ret;
}

锁策略总结:

操作类型锁机制说明
读操作RCUrcu_read_lock() 下可无锁访问
写操作spinlock通过 xa_lock() 保护
节点分配Per-CPU 预加载避免在原子上下文中的阻塞分配
标签操作依赖树锁标签随树修改而更新

2.4 Iterator 实现细节 ​

迭代器结构 (include/linux/radix-tree.h 第 92-111 行):

c
struct radix_tree_iter {
    unsigned long   index;      /* 当前 slot 的索引 */
    unsigned long   next_index; /* 此 chunk 的最后索引 + 1 */
    unsigned long   tags;       /* 标签迭代的位掩码 */
    struct xa_node *node;       /* 包含当前 slot 的节点 */
};

radix_tree_next_chunk 实现 (lib/radix-tree.c 第 1154-1239 行):

c
void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root,
                 struct radix_tree_iter *iter, unsigned flags)
{
    unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK;
    struct xa_node *node, *child;
    unsigned long index, offset, maxindex;

    // 标签快速路径
    if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag))
        return NULL;

    index = iter->next_index;
    if (!index && iter->index)
        return NULL;

restart:
    radix_tree_load_root(root, &child, &maxindex);
    if (index > maxindex)
        return NULL;
    if (!child)
        return NULL;

    // 单 slot 树处理
    if (!radix_tree_is_internal_node(child)) {
        iter->index = index;
        iter->next_index = maxindex + 1;
        iter->tags = 1;
        iter->node = NULL;
        return (void __rcu **)&root->xa_head;
    }

    do {
        node = entry_to_node(child);
        offset = radix_tree_descend(node, &child, index);

        // 检测空洞或标签不匹配
        if ((flags & RADIX_TREE_ITER_TAGGED) ?
                !tag_get(node, tag, offset) : !child) {
            if (flags & RADIX_TREE_ITER_CONTIG)
                return NULL;  // CONTIG 模式遇到空洞即停止

            // 找下一个有效位置
            if (flags & RADIX_TREE_ITER_TAGGED)
                offset = radix_tree_find_next_bit(node, tag, offset + 1);
            else
                while (++offset < RADIX_TREE_MAP_SIZE) {
                    void *slot = rcu_dereference_raw(node->slots[offset]);
                    if (slot)
                        break;
                }
            // ... 索引计算和重启逻辑
        }
        // ...
    } while (node->shift && radix_tree_is_internal_node(child));

    // 更新迭代器状态
    iter->index = (index &~ node_maxindex(node)) | offset;
    iter->next_index = (index | node_maxindex(node)) + 1;
    iter->node = node;

    if (flags & RADIX_TREE_ITER_TAGGED)
        set_iter_tags(iter, node, offset, tag);

    return node->slots + offset;
}

迭代宏 (include/linux/radix-tree.h 第 449-470 行):

c
#define radix_tree_for_each_slot(slot, root, iter, start)       \
    for (slot = radix_tree_iter_init(iter, start) ;            \
         slot || (slot = radix_tree_next_chunk(root, iter, 0)) ;\
         slot = radix_tree_next_slot(slot, iter, 0))

#define radix_tree_for_each_tagged(slot, root, iter, start, tag)\
    for (slot = radix_tree_iter_init(iter, start) ;            \
         slot || (slot = radix_tree_next_chunk(root, iter,      \
                  RADIX_TREE_ITER_TAGGED | tag)) ;             \
         slot = radix_tree_next_slot(slot, iter,               \
                RADIX_TREE_ITER_TAGGED | tag))

3. IDR/IDA 子系统 ​

3.1 IDR/IDA 数据结构 ​

IDR 结构 (include/linux/idr.h 第 20-24 行):

c
struct idr {
    struct radix_tree_root  idr_rt;   /* 底层 radix tree */
    unsigned int           idr_base; /* ID 起始值 */
    unsigned int           idr_next; /* 下一个 cyclic 分配候选 */
};

IDA 结构 (include/linux/idr.h 第 259-265 行):

c
struct ida_bitmap {
    unsigned long  bitmap[IDA_BITMAP_LONGS];  // 128 bytes
};

struct ida {
    struct xarray xa;  /* 底层 XArray */
};

IDA_BITMAP_BITS 计算:

c
#define IDA_CHUNK_SIZE     128          /* 每块 128 字节 */
#define IDA_BITMAP_LONGS   (IDA_CHUNK_SIZE / sizeof(long))  // 16 (64-bit) 或 32 (32-bit)
#define IDA_BITMAP_BITS    (IDA_BITMAP_LONGS * BITS_PER_LONG)  // 1024 或 1024

3.2 IDR 分配算法 ​

idr_alloc_u32 实现 (lib/idr.c 第 33-58 行):

c
int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid,
            unsigned long max, gfp_t gfp)
{
    struct radix_tree_iter iter;
    void __rcu **slot;
    unsigned int base = idr->idr_base;
    unsigned int id = *nextid;

    if (WARN_ON_ONCE(!(idr->idr_rt.xa_flags & ROOT_IS_IDR)))
        idr->idr_rt.xa_flags |= IDR_RT_MARKER;
    if (max < base)
        return -ENOSPC;

    id = (id < base) ? 0 : id - base;
    radix_tree_iter_init(&iter, id);
    slot = idr_get_free(&idr->idr_rt, &iter, gfp, max - base);
    if (IS_ERR(slot))
        return PTR_ERR(slot);

    *nextid = iter.index + base;
    radix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr);
    radix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE);

    return 0;
}

idr_get_free 实现 (lib/radix-tree.c 第 1476-1546 行) - IDR 空闲槽位查找:

c
void __rcu **idr_get_free(struct radix_tree_root *root,
                  struct radix_tree_iter *iter, gfp_t gfp,
                  unsigned long max)
{
    struct radix_tree_node *node = NULL, *child;
    void __rcu **slot = (void __rcu **)&root->xa_head;
    unsigned long maxindex, start = iter->next_index;
    unsigned int shift, offset = 0;

grow:
    shift = radix_tree_load_root(root, &child, &maxindex);
    if (!radix_tree_tagged(root, IDR_FREE))
        start = max(start, maxindex + 1);
    if (start > max)
        return ERR_PTR(-ENOSPC);

    if (start > maxindex) {
        int error = radix_tree_extend(root, gfp, start, shift);
        if (error < 0)
            return ERR_PTR(error);
        shift = error;
        child = rcu_dereference_raw(root->xa_head);
    }
    if (start == 0 && shift == 0)
        shift = RADIX_TREE_MAP_SHIFT;

    while (shift) {
        shift -= RADIX_TREE_MAP_SHIFT;
        if (child == NULL) {
            child = radix_tree_node_alloc(gfp, node, root, shift,
                            offset, 0, 0);
            if (!child)
                return ERR_PTR(-ENOMEM);
            all_tag_set(child, IDR_FREE);  // 新节点标记为全空闲
            rcu_assign_pointer(*slot, node_to_entry(child));
            if (node)
                node->count++;
        } else if (!radix_tree_is_internal_node(child))
            break;

        node = entry_to_node(child);
        offset = radix_tree_descend(node, &child, start);
        if (!tag_get(node, IDR_FREE, offset)) {
            // 找下一个空闲槽
            offset = radix_tree_find_next_bit(node, IDR_FREE, offset + 1);
            start = next_index(start, node, offset);
            if (start > max || start == 0)
                return ERR_PTR(-ENOSPC);
            while (offset == RADIX_TREE_MAP_SIZE) {
                offset = node->offset + 1;
                node = node->parent;
                if (!node)
                    goto grow;
                shift = node->shift;
            }
            child = rcu_dereference_raw(node->slots[offset]);
        }
        slot = &node->slots[offset];
    }

    iter->index = start;
    if (node)
        iter->next_index = 1 + min(max, (start | node_maxindex(node)));
    else
        iter->next_index = 1;
    iter->node = node;
    set_iter_tags(iter, node, offset, IDR_FREE);

    return slot;
}

3.3 旋转缓冲区优化 (Cyclic Allocation) ​

idr_alloc_cyclic 实现 (lib/idr.c 第 119-137 行):

c
int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)
{
    u32 id = idr->idr_next;  // 从上次位置开始
    int err, max = end > 0 ? end - 1 : INT_MAX;

    if ((int)id < start)
        id = start;

    err = idr_alloc_u32(idr, ptr, &id, max, gfp);
    if ((err == -ENOSPC) && (id > start)) {
        id = start;  //  Wrap around
        err = idr_alloc_u32(idr, ptr, &id, max, gfp);
    }
    if (err)
        return err;

    idr->idr_next = id + 1;  // 更新下次起始位置
    return id;
}

优化原理:

  • 记录 idr_next 作为下次分配的起点
  • 分配失败时回绕到 start 重试
  • 避免低 ID 碎片化，提高缓存局部性

3.4 IDA 分配算法 ​

ida_alloc_range 实现 (lib/idr.c 第 382-478 行):

c
int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max, gfp_t gfp)
{
    XA_STATE(xas, &ida->xa, min / IDA_BITMAP_BITS);
    unsigned bit = min % IDA_BITMAP_BITS;
    unsigned long flags;
    struct ida_bitmap *bitmap, *alloc = NULL;

retry:
    xas_lock_irqsave(&xas, flags);  // IDA 内部加锁
next:
    bitmap = xas_find_marked(&xas, max / IDA_BITMAP_BITS, XA_FREE_MARK);
    if (xas.xa_index > min / IDA_BITMAP_BITS)
        bit = 0;
    if (xas.xa_index * IDA_BITMAP_BITS + bit > max)
        goto nospc;

    if (xa_is_value(bitmap)) {
        // 小值优化：低 ID 用单 long 存储
        unsigned long tmp = xa_to_value(bitmap);
        if (bit < BITS_PER_XA_VALUE) {
            bit = find_next_zero_bit(&tmp, BITS_PER_XA_VALUE, bit);
            // ...
            tmp |= 1UL << bit;
            xas_store(&xas, xa_mk_value(tmp));
            goto out;
        }
        bitmap = alloc;
        if (!bitmap)
            bitmap = kzalloc_obj(*bitmap, GFP_NOWAIT);
        if (!bitmap)
            goto alloc;
        bitmap->bitmap[0] = tmp;
        xas_store(&xas, bitmap);
        // ...
    }

    if (bitmap) {
        bit = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, bit);
        if (bit == IDA_BITMAP_BITS)
            goto next;  // 此块满了，尝试下一块

        __set_bit(bit, bitmap->bitmap);
        if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS))
            xas_clear_mark(&xas, XA_FREE_MARK);  // 满块清除 FREE 标记
    }
    // ...
out:
    xas_unlock_irqrestore(&xas, flags);
    // ...
    return xas.xa_index * IDA_BITMAP_BITS + bit;

nospc:
    xas_unlock_irqrestore(&xas, flags);
    kfree(alloc);
    return -ENOSPC;
}

3.5 IDA 线程安全机制 ​

IDA 锁策略:

c
#define IDA_INIT_FLAGS  (XA_FLAGS_LOCK_IRQ | XA_FLAGS_ALLOC)
特性说明
内部锁IDA 函数内部使用 xas_lock_irqsave() 自保护
无需外部锁调用者不需要额外同步
中断安全IRQ 安全的锁
RCU 不可用因 bitmap 释放需要复杂 RCU 同步

4. Command Line 解析器 ​

4.1 get_option 解析器实现 ​

get_option 函数 (lib/cmdline.c 第 56-79 行):

c
int get_option(char **str, int *pint)
{
    char *cur = *str;
    int value;

    if (!cur || !(*cur))
        return 0;
    if (*cur == '-')
        value = -simple_strtoull(++cur, str, 0);  // 负数处理
    else
        value = simple_strtoull(cur, str, 0);
    if (pint)
        *pint = value;
    if (cur == *str)
        return 0;                    // 无整数
    if (**str == ',') {
        (*str)++;
        return 2;                    // 带逗号
    }
    if (**str == '-')
        return 3;                    // 范围开始

    return 1;                        // 普通整数
}

返回值语义:

返回值含义
0字符串中无整数
1找到整数，后无逗号
2找到整数，后有逗号
3遇到连字符，表示范围 (M-N)

4.2 get_options 批量解析 ​

get_options 函数 (lib/cmdline.c 第 107-138 行):

c
char *get_options(const char *str, int nints, int *ints)
{
    bool validate = (nints == 0);
    int res, i = 1;

    while (i < nints || validate) {
        int *pint = validate ? ints : ints + i;

        res = get_option((char **)&str, pint);
        if (res == 0)
            break;
        if (res == 3) {
            int n = validate ? 0 : nints - i;
            int range_nums;

            range_nums = get_range((char **)&str, pint, n);
            if (range_nums < 0)
                break;
            i += (range_nums - 1);  // 范围展开
        }
        i++;
        if (res == 1)
            break;  // 无逗号，解析结束
    }
    ints[0] = i - 1;  // 第一个元素存储个数
    return (char *)str;
}

范围展开实现 (lib/cmdline.c 第 23-33 行):

c
static int get_range(char **str, int *pint, int n)
{
    int x, inc_counter, upper_range;

    (*str)++;  // 跳过 '-'
    upper_range = simple_strtol(*str, NULL, 0);
    inc_counter = upper_range - *pint;
    for (x = *pint; n && x < upper_range; x++, n--)
        *pint++ = x;  // 展开 M, M+1, ..., N
    return inc_counter;
}

4.3 memparse 内存单位解析 ​

memparse 函数 (lib/cmdline.c 第 150-190 行):

c
unsigned long long memparse(const char *ptr, char **retptr)
{
    char *endptr;
    unsigned long long ret = simple_strtoull(ptr, &endptr, 0);

    switch (*endptr) {
    case 'E':
    case 'e':
        ret <<= 10;  // 乘以 1024
        fallthrough;
    case 'P':
    case 'p':
        ret <<= 10;
        fallthrough;
    case 'T':
    case 't':
        ret <<= 10;
        fallthrough;
    case 'G':
    case 'g':
        ret <<= 10;
        fallthrough;
    case 'M':
    case 'm':
        ret <<= 10;
        fallthrough;
    case 'K':
    case 'k':
        ret <<= 10;
        endptr++;
        fallthrough;
    default:
        break;
    }

    if (retptr)
        *retptr = endptr;
    return ret;
}

支持的单位: K(k), M, G, T, P, E (每级 1024 倍)

4.4 parse_option_str 选项检查 ​

parse_option_str 函数 (lib/cmdline.c 第 203-220 行):

c
bool parse_option_str(const char *str, const char *option)
{
    while (*str) {
        // 检查前缀匹配
        if (!strncmp(str, option, strlen(option))) {
            str += strlen(option);
            // 确认是完整选项（后面是逗号或结束）
            if (!*str || *str == ',')
                return true;
        }

        // 跳到下一个逗号
        while (*str && *str != ',')
            str++;

        if (*str == ',')
            str++;
    }

    return false;
}

4.5 next_arg 参数解析 ​

next_arg 函数 (lib/cmdline.c 第 227-274 行):

c
char *next_arg(char *args, char **param, char **val)
{
    unsigned int i, equals = 0;
    int in_quote = 0, quoted = 0;

    // 处理开头引号
    if (*args == '"') {
        args++;
        in_quote = 1;
        quoted = 1;
    }

    // 扫描参数
    for (i = 0; args[i]; i++) {
        if (isspace(args[i]) && !in_quote)
            break;  // 空白字符分隔参数
        if (equals == 0) {
            if (args[i] == '=')
                equals = i;  // 记录 '=' 位置
        }
        if (args[i] == '"')
            in_quote = !in_quote;
    }

    *param = args;
    if (!equals)
        *val = NULL;
    else {
        args[equals] = '\0';
        *val = args + equals + 1;

        // 去除值两端的引号
        if (**val == '"') {
            (*val)++;
            if (args[i-1] == '"')
                args[i-1] = '\0';
        }
    }
    if (quoted && i > 0 && args[i-1] == '"')
        args[i-1] = '\0';

    // 移动到下一个参数
    if (args[i]) {
        args[i] = '\0';
        args += i + 1;
    } else
        args += i;

    return skip_spaces(args);
}

特性:

  • 支持引号包围的值（含空格）
  • 等号 = 分隔参数名和值
  • 连字符和下划线在参数名中等价
  • 返回指向下一个参数的指针

5. 知识点关联表格 ​

5.1 各子系统对比 ​

特性BitmapRadix-TreeIDR/IDACommand Line
核心用途位操作稀疏索引映射ID 分配命令行解析
内存模型连续位数组分层树节点Radix/XArray字符串处理
分配单位bitpointerID numbertoken
并发机制外部锁RCU + spinlock内部锁/XArray不适用
NUMA 支持bitmap_alloc_nodeN/AN/AN/A
迭代方式for_each_set_bitradix_tree_for_each_*idr_for_eachstrsep
典型应用内存管理, CPU mask页面缓存, 进程映射设备号, 文件描述符内核参数

5.2 关键函数索引 ​

Bitmap (lib/bitmap.c):

函数行号说明
bitmap_alloc723-727分配 bitmap
bitmap_zalloc730-733零初始化分配
bitmap_alloc_node736-740NUMA 感知分配
__bitmap_set364-383设置位范围
__bitmap_clear385-404清除位范围
bitmap_find_next_zero_area_off419-442查找连续零区域

Radix-Tree (lib/radix-tree.c):

函数行号说明
radix_tree_insert703-730插入条目
radix_tree_lookup817-820查找条目
radix_tree_delete1445-1448删除条目
radix_tree_next_chunk1154-1239迭代器核心
radix_tree_tag_set967-992设置标签
radix_tree_tag_clear1029-1052清除标签
radix_tree_node_alloc232-288节点分配

IDR/IDA (lib/idr.c):

函数行号说明
idr_alloc_u3233-58IDR 分配
idr_alloc_cyclic119-137循环分配
idr_find174-177IDR 查找
idr_remove154-157IDR 删除
ida_alloc_range382-478IDA 分配
ida_free556-595IDA 释放
ida_destroy610-623IDA 销毁

Command Line (lib/cmdline.c):

函数行号说明
get_option56-79解析单个整数
get_options107-138批量解析整数
memparse150-190解析内存单位
parse_option_str203-220检查选项存在
next_arg227-274解析 param=value

5.3 内部节点结构对比 ​

xa_node (Radix-Tree/IDR 共享)
├── shift: 6          # 每层位数
├── offset: 0-63      # 父节点中的偏移
├── count: 条目数     # 非空槽位数
├── nr_values: 值条目数
├── parent --> 父节点
├── slots[64] --> 子节点或数据指针
└── tags[3][2] --> 标签位图

ida_bitmap (IDA 专用)
└── bitmap[16/32] --> 1024/1024 位物理 bitmap

5.4 内存分配路径 ​

Bitmap 分配:
  bitmap_alloc() --> kmalloc_array()
  bitmap_alloc_node() --> kmalloc_array_node()

Radix-Tree 节点:
  radix_tree_node_alloc()
  ├── Per-CPU 预加载池 (非中断上下文)
  └── kmem_cache_alloc() (通用路径)

IDA Bitmap:
  ida_alloc_range()
  └── kzalloc_obj() / kmalloc()

5.5 同步原语使用 ​

组件读操作写操作特殊机制
Bitmap无锁外部 spinlockN/A
Radix-TreeRCUxa_lockRCU 延迟释放
IDRRCU (idr_find)xa_lock预加载优化
IDA内部 xas_lockxas_lock_irqsave全函数加锁
Command Line不适用不适用不适用

总结 ​

Linux lib 子系统提供了内核必备的基础数据结构和算法:

  1. Bitmap 提供了高效的位操作能力，通过 kmalloc_array_node 支持 NUMA 感知分配
  2. Radix-Tree 基于 XArray 实现，支持 RCU 无锁读取和高效的标签机制
  3. IDR/IDA 构建在 Radix-Tree 之上，提供了 ID 分配器功能，IDA 通过位图优化空间
  4. Command Line 解析器提供了灵活的命令行参数处理能力

这些子系统在 Linux 内核中被广泛使用，是理解内核设计的重要基础。

文档信息:

  • 源码版本: Linux kernel
  • 分析文件: lib/bitmap.c, lib/radix-tree.c, lib/idr.c, lib/cmdline.c
  • 生成日期: 2026-04-26

基于 VitePress 构建

Copyright © 2024-present Sphinx