Learning vppinfra：bitmap结构解析

dpdk-vpp源码解读

发布于 2024-04-28 14:57:32

1850

发布于 2024-04-28 14:57:32

Bitmap是一种紧凑的数据结构，它使用一组连续的比特位（bits）来表示一组数据元素的状态或存在性。每个比特位对应一个特定的数据元素，值通常为0或1，表示该元素是否满足某种条件（如是否存在、是否已使用等）。由于比特是最小的存储单位，使用bitmap可以大大节省存储空间，特别适合处理大量整数型数据。

位图一般都使用数组来实现的，数据的每一个元素的二进制位都表示一个数据在或不在的状态。0表示数据不存在，1表示数据存在。

vppinfra--bitmap的实现接口

vppinfra 结构中bitmap 是通过索引set或get bit位的数值；位宽64bits，unsigned long 类型。底层也是一个vector结构。其内存分布结构如下所示：

bitmap结构在vpp中应用很广泛，比如在创建接口时，用于存储接口instace ID是否被占用；在pool数据结构中，用来判断索引是否释放等等。

bitmap 存储区内存申请 1、按照指定的位图数量申请bitmap内存区。

/** 按照指定的位图bits数量申请bitmap内存区。
    @param [out] v - bitmap的首地址
    @param n_bits - 请求的bits数量
*/
#define clib_bitmap_alloc(v,n_bits) \
  v = vec_new (uword, ((n_bits) + BITS (uword) - 1) / BITS (uword)

2、确保bitmap内存区至少有n_bits ,不满足会动态扩充

#define clib_bitmap_validate(v,n_bits) \
  clib_bitmap_vec_validate ((v), ((n_bits) - 1) / BITS (uword)

bitmap 设置指定bit位

/* ai：bitmap的指针
 * i :需要操作d的bit位置
 * value : 设置i对应bit位位的数值，
 * return: 必须注意，当i不在ai内存范围内时，会对ai进行重新mmalloc
 * 可能存在ai执向内存区位置变更。
 */
always_inline uword *
clib_bitmap_set (uword * ai, uword i, uword value）

bitmap 获取指定bit位

/** Gets the ith bit value from a bitmap
    @param ai - bitmap 头指针
    @param i - 要询问的bit位位置
    @returns 返回bit位的数值，存在两种情况
             1、询问的bit位位置超过ai存储区d的大小，返回0
             2、正常返回bit位的数值。
*/
always_inline uword
clib_bitmap_get (uword * ai, uword i)

设置或者获取一段范围内的bitmap数值

/*  n_bits 必须小于等于64。
 * i ：起始bit位置
 */
always_inline uword
clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits）
/* 必须需要注意bitmap位置的变更。
 */
always_inline uword *
clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits）