vppinfra---sparse_vec
vppinfra---sparse_vec
今天来了解一下sparse_vec 结构的使用。目前使用的地方还是挺多的。比如：ethernet-input节点，通过ethernet-type类型获取next索引。（也就是当前节点的slot id）；在ip-local节点通过ip protocols回去next索引等等。下面就来简单介绍下：
Sparsely indexed vectors. 稀疏索引向量。这个结构的基本想法来源于这本书“Hacker's delight”，实现者Eliot 增加了支持范围操作。设计的目的应该是为了节约内存。
1、基本结构及内存分布情况
sparse vec 是基于vector结构来实现的。
typedef struct
{
/* Bitmap one for each sparse index. */
uword *is_member_bitmap;
/* member_counts[i] = total number of members with j < i. */
u16 *member_counts;
#define SPARSE_VEC_IS_RANGE (1 << 0)
#define SPARSE_VEC_IS_VALID_RANGE (1 << 1)
u8 *range_flags;
} sparse_vec_header_t;uword *is_member_bitmap：
每个sparse 索引对应一个bit位。
u16 *member_counter：
按照注释的意思member_counter[i] 等于小于i的全部元素数量的和（有点计数排序算法的策略）。
这里我们取sparse_vec_index_internal()函数的一些片段来讲解一下：
/* 获取sparse_index索引 对应在V的下标索引sparce_vec_index
* V：vector结构存储元素的首指针。
* sparse_index: sparse的索引。比如ethernet_type的数值。
* maybe_range：是否是一段范围，目前不支持。
* insert：是否是新插入的元素。
*/
always_inline uword
sparse_vec_index_internal (void *v,
uword sparse_index,
uword maybe_range, u32 * insert)；
下面主要说明插入新元素时，处理流程。
/* 计算sparse_index 在is_member_bitmap 数组的下标*/
i = sparse_index / BITS (h->is_member_bitmap[0]);
/* 计算sparse_index 在is_member_bitmap[i] 占用第几个bit*/
b = sparse_index % BITS (h->is_member_bitmap[0]);
....
/* 取当前sparse_index对应的bitmap数值。*/
w = h->is_member_bitmap[i];
/* 得到sparse_vec_index；
* 通过当前成员的member_counts[i] + w数值bit位时1的个数
*/
d = h->member_counts[i] + count_set_bits (w & ((1ULL << b) - 1));
is_member = (w & (1ULL << b)) != 0
....
if (insert)
{
uword j;
/* 设置sparse_index对应的bit位*/
w |= 1ULL << b;
h->is_member_bitmap[i] = w;
/* 记录member_counts；需要将i+1之后的所有成员计数都要+1.
* 这样就能快速得到在V[x]下标x。这种计算方式也说明了，
* 所以最好的方式就是初始化的时候要求把需要的sparse_index从递增方式全部初始化完成。
* 如果是初始化完成后，添加新的，可能在存在内存搬移的情况。*/
for (j = i + 1; j < vec_len (h->member_counts); j++)
h->member_counts[j] += 1;
}
/* 默认0是无效的，所有sparse_vec_index 都需要+1*/
return 1 + d;
}下图是具体分别一次存储6，10，65，68，128，对应spares_vec_index索引及sparse_vec头结构成员的数值。
通过上图内存分布情况，很明显的优点：节省了不必要内存的浪费。还有一个优化点，在初始化时，sparse_index根据需要可以设置成网络序，这样在转发流程中可以直接从报文中获取ethernet type使用，而无需转换成主机序。
u8 *range_flags;
rang的标识，还未详细研究。从sparse_vec_new函数来看，并未对其分配内存，所以说vpp还未出现使用range场景。否则也是存在bug的。
2、 简单介绍使用。
我们以gre-input节点为例子，简单介绍使用情况：
1、初始化
这里有个问题需要注意就是sparse_vec_new函数对参数sparse_index_bits有个限制，必须<=16。暂时不清楚具体的限制原因，从使用上看port（16bit）、ethernet_type(16bit)、protocol（8bit），未有超过16bits的大小。
ASSERT (sparse_index_bits <= 16);gm->next_by_protocol 初始化：
gm->next_by_protocol = sparse_vec_new
( /* elt bytes */ sizeof (gm->next_by_protocol[0]),
/* bits in index */ BITS (((gre_header_t *) 0)->protocol));2、添加元素
gre_register_input_protocol 函数完成对ipv4-input节点添加到gre-input后面。
gre_register_input_protocol (vm, GRE_PROTOCOL_ip4,
ip4_input->index, GRE_TUNNEL_TYPE_L3);
/* 添加协议号和next index的映射关系。这里协议号是网络序。
* 在转发流程中可以减少一次转换。
* Setup gre protocol -> next index sparse vector mapping. */
n = sparse_vec_validate (em->next_by_protocol,
clib_host_to_net_u16 (protocol));3、转发过程中使用
通过gre头的protocols获得nidx索引。
⚠️ 主要nidx[0] 为0时，表示未查询到next0。
nidx[0] =
sparse_vec_index (gm->next_by_protocol, gre[0]->protocol)3、总结
本文简单介绍了sparse_vec结构的内存分布及使用实例。虽然编码中还有很多需要注意的地方，但是也是很不错的一个api接口。后续开发有使用场景也是一种不错的参考。