位图（Bitmap）管理在驱动与资源分配中的应用

在驱动开发与资源分配的领域中，高效的资源管理方式至关重要。位图（Bitmap）管理凭借其独特的优势，成为了开发者们手中的得力工具。接下来，让我们深入探究位图管理在其中的应用。

一、为何使用位图？

位图管理之所以备受青睐，源于其显著的特性。首先，内存高效是它的一大亮点，每个资源仅占 1 bit，也就是说 1000 个资源大约只需要 125 B 的存储空间。其次，操作快速也是位图的核心优势，位运算的效率远超数组遍历、链表查找等传统方式。正是因为这些特性，位图在实际应用中应用广泛，无论是管理固定数量的表项、ID 池，还是 Pipe 号、任务标志等场景，它都能发挥出色的作用。

了解了位图的优势后，我们进一步认识一下位图管理中的基础定义与宏，这些是构建位图管理功能的基石。

二、基础定义与宏

#include <stdint.h>

/** \brief 位图单元类型：32 位宽度的小块 */
typedef uint32_t bm_unit_t;

/** \brief 每个单元管理的位数（32） */
#define BITS_PER_UNIT   (sizeof(bm_unit_t) * 8)

/** 
 * \brief 计算管理 n 个资源，需要多少个位图单元 
 * 向上取整：(n + (BITS_PER_UNIT-1)) / BITS_PER_UNIT
 */
#define BITMAP_UNITS(n) (((n) + (BITS_PER_UNIT - 1)) / BITS_PER_UNIT)

/** \brief 可支持的最大资源条目数（可按需调整） */
#define MAX_ENTRIES     256

/** 位图数组实例：用来管理 0～255 共 256 条资源的“占用”状态 */
static bm_unit_t entry_bitmap[BITMAP_UNITS(MAX_ENTRIES)] = {0};

上述代码中的定义和宏是位图管理的基础。其中，bm_unit_t 定义了位图元素的类型为 32 bits；BITS_PER_UNIT 明确了每个元素包含的标志位数量；BITMAP_UNITS(n) 用于算出存放n个标志位所需的 bm_unit_t 单元个数；entry_bitmap 则是实际的位图数组，初始化为全 0，表示全部资源处于空闲状态。

有了基础定义，接下来我们需要掌握位操作的基本接口，这些接口是实现位图管理功能的关键操作。

三、位操作基本接口

/**
 * @brief 设置位图中某位为 1（占用）
 * @param idx    资源索引（0 ~ MAX_ENTRIES-1）
 * @param bm     位图数组
 * @return 0 成功；-1 越界
 */
static inline int bmp_set(int idx, bm_unit_t *bm)
{
    if (idx < 0 || idx >= MAX_ENTRIES) return -1;
    bm[idx / BITS_PER_UNIT] |= ((bm_unit_t)1U << (idx % BITS_PER_UNIT));
    return 0;
}

/**
 * @brief 清除位图中某位为 0（释放）
 * @param idx    资源索引
 * @param bm     位图数组
 * @return 0 成功；-1 越界
 */
static inline int bmp_clear(int idx, bm_unit_t *bm)
{
    if (idx < 0 || idx >= MAX_ENTRIES) return -1;
    bm[idx / BITS_PER_UNIT] &= ~((bm_unit_t)1U << (idx % BITS_PER_UNIT));
    return 0;
}

/**
 * @brief 测试位图中某位是否为 1（被占用）
 * @param idx    资源索引
 * @param bm     位图数组
 * @return 1=占用；0=空闲；-1=越界
 */
static inline int bmp_test(int idx, const bm_unit_t *bm)
{
    if (idx < 0 || idx >= MAX_ENTRIES) return -1;
    return (bm[idx / BITS_PER_UNIT] >> (idx % BITS_PER_UNIT)) & 1U;
}

这些位操作接口的实现包含了几个重要步骤。首先是边界检测，通过判断idx的有效性，一旦越界就直接返回错误，从而避免非法访问。接着是位定位，通过unit = idx / BITS_PER_UNIT确定资源所在单元，通过bit = idx % BITS_PER_UNIT确定单元内的具体位置。最后是位运算，利用|=将目标位置 1，使用&=~将目标位清 0，借助>> &1提取目标位的值。

掌握了基本操作后，在实际的资源分配场景中，我们常常需要查找第一个空闲位，以此来自动分配未被占用的资源索引。

四、查找第一个空闲位

最常见的自动分配场景便是分配一个还未被占用的资源索引，这就需要查找第一个空闲位。

/**
 * @brief 查找并返回第一个空闲位（值为 0）的索引
 * @param bm          位图数组
 * @return >=0: 空闲索引； -1: 无空闲
 */
int bmp_find_first_zero(const bm_unit_t *bm)
{
    unsigned total_units = BITMAP_UNITS(MAX_ENTRIES);
    for (unsigned u = 0; u < total_units; u++) {
        bm_unit_t w = bm[u];
        /* 如果全为 1，跳过整个单元 */
        if (w == ~(bm_unit_t)0U) continue;

        /* 否则逐位查找第一个 0 */
        for (unsigned b = 0; b < BITS_PER_UNIT; b++) {
            unsigned idx = u * BITS_PER_UNIT + b;
            if (idx >= MAX_ENTRIES) break;
            if (((w >> b) & 1U) == 0) {
                return (int)idx;
            }
        }
    }
    return -1;
}

该函数采用了块级跳过和线性查找的策略。当整组位全为 1 时，直接通过continue跳过该单元，从而节省逐位检测的时间；当遇到非全 1 单元时，则进行线性查找，一旦找到第一个 0 就返回对应的索引。

虽然上述方法能够实现查找功能，但在性能上还有优化空间。我们可以借助 GCC/Clang 提供的__builtin_ctz() 函数，进一步提升查找效率。

五、进一步优化：__builtin_ctz()

GCC/Clang 提供的__builtin_ctz(x) 能在一个 32-bit 整数里直接定位最低那一位 1，利用这一特性可以避免内层循环，大幅提升效率。

int bmp_find_first_one_fast(bm_unit_t w)
{
    /* 前提：w ≠ 0，否则结果未定义 */
    return __builtin_ctz(w);
}

int bmp_find_first_zero_fast(const bm_unit_t *bm)
{
    unsigned units = BITMAP_UNITS(MAX_ENTRIES);
    for (unsigned u = 0; u < units; u++) {
        bm_unit_t w = bm[u];
        if (w != ~(bm_unit_t)0U) {
            /* 把空闲 0 转换成有标记的 1：取反 */
            bm_unit_t inv = ~w;
            int bit = __builtin_ctz(inv);
            unsigned idx = u * BITS_PER_UNIT + bit;
            if (idx < MAX_ENTRIES)
                return (int)idx;
        }
    }
    return -1;
}

其优化原理在于，通过inv = ~w将原来为 0 的位置在inv中变为 1，然后利用__builtin_ctz(inv)直接返回最低 1 位偏移。这种方式属于常数时间指令，性能远高于循环方式。

在驱动开发的实际应用中，除了查找空闲位，分页获取已用条目也是常见的需求。接下来我们看看如何实现这一功能。

六、分页获取已用条目示例

在驱动取表项时，常常需要分页查询所有已占用索引并返回对应数据，以下是实现该功能的示例代码。

int get_entries_page(const bm_unit_t *bm,
                     const Entry entries[], 
                     unsigned offset, unsigned max_out,
                     Entry out[], unsigned *out_count)
{
    unsigned copied = 0;
    unsigned total_units = BITMAP_UNITS(MAX_ENTRIES);

    for (unsigned u = offset / BITS_PER_UNIT; u < total_units; u++) {
        bm_unit_t w = bm[u];
        if (w == 0) continue;  // 整组无占用

        /* 如果是首单元，从 offset bit 开始 */
        unsigned start_bit = (u == offset / BITS_PER_UNIT)
                             ? (offset % BITS_PER_UNIT) : 0;

        /* 可用 __builtin_ctz 加速，也可逐位 */
        for (unsigned b = start_bit; b < BITS_PER_UNIT; b++) {
            unsigned idx = u * BITS_PER_UNIT + b;
            if (idx >= MAX_ENTRIES) break;
            if ((w >> b) & 1U) {
                out[copied++] = entries[idx];
                if (copied >= max_out) {
                    *out_count = copied;
                    return 0;
                }
            }
        }
    }
    *out_count = copied;
    return 0;
}

在这个函数中，offset表示分页起始索引，max_out表示本页最大返回条目数。通过跳过空单元以及可选的__builtin_ctz加速，能够高效地实现分页获取已用条目的功能。