GNU inetutils 软件包包含了一些常见的实用网络工具,例如 ping ,本文的目的是介绍和讲解 inetutils-2.5 源码包中实现的 bitmap.
bitmap 是一种数据结构,它至少应当支持以下三个操作:
bitmap.is_set(bit_index): bool
: 判断序号为 bit_index
的比特是否已经 set;bitmap.set(bit_index): void
: set 序号为 bit_index
的比特;bitmap.clear(bit_index): void
: unset 序号为 bit_index
的比特;以及初始化、销毁等操作(不在本文范围内)。对于具体的实现,方法(或者函数)的名称可能不一样,但行为基本是如上所述的。
inetutils-ping 在一次连续发送 ICMP ECHOREQUEST 封包以及接收 ICMP ECHOREPLY 封包的过程中,它用一个 bitmap 实例记录并判断 ICMP ECHOREPLY 封包的序号,并通过调用这个 bitmap 的方法来判断是否收到了重复的 ICMP ECHOREPLY 封包并且记录已经收到过的 ICMP ECHOREPLY 封包的序号。
inetutils-ping 的 bitmap 实现大量应用了宏和位运算,读起来第一印象或许是比较晦涩难懂,我们接下来将提供源码展示,以及浅显的讲解。
位于 ping/ping_common.h
L132
#define _C_BIT(p,bit) (p)->ping_cktab[(bit)>>3] /* byte in ck array */
#define _C_MASK(bit) (1 << ((bit) & 0x07))
#define _C_IND(p,bit) ((bit) % (8 * (p)->ping_cktab_size))
#define _PING_SET(p,bit) \
do \
{ \
int n = _C_IND (p,bit); \
_C_BIT (p,n) |= _C_MASK (n); \
} \
while (0)
#define _PING_CLR(p,bit) \
do \
{ \
int n = _C_IND (p,bit); \
_C_BIT (p,n) &= ~_C_MASK (n); \
} \
while (0)
#define _PING_TST(p,bit) \
(_C_BIT (p, _C_IND (p,bit)) & _C_MASK (_C_IND (p,bit)))
其中,_PING_CLR
相当于 bitmap 的 unset
, _PING_TST
相当于 bitmap 的 test
(或者 is_set
),_PINT_SET
顾名思义。
进一步阅读其它源码我们可以发现,bitmap 的存储空间(一段连续的内存)应该是位于以 (p)->ping_cktab
为起始地址的一块连续的内存,它是一个 char*
,这块区域的大小是 N = (p)->ping_cktab_size
(bytes).
一个 char 变量可以存储 8 个 bit 的信息,那么,这整个 bitmap 实际上就可以存储 M = N * 8 = (p)->ping_cktab_size
* 8 这么多个 bits 的信息,于是,_C_IND
所做的实际上就是把它的“输入”映射到 0 到 M-1 的这个范围。它通过取模运算( %
是取余数运算符)来做到这一点。
然后你再把 bitmap 的整个存储区域看作是一个 char[N]
对象,每个 char
有 8 个 bits, 那么,_C_BIT
相当于对输入除以 8 ,然后根据得到的商来选择用 char[N]
中的哪个 char
,相当于在一个大的 bitmap 中选出一个“子 bitmap“,也可以理解为是把输入的除去了最右边 3 个 LSB (least significant bits) 之后剩下的信息映射到用来访问 char[N]
的 index.
例如,假设,_C_BIT
的输入是 0b11010011 ,那么,它去除了 3 个 LSB (也就是 011 )后就剩下了 11010 ,_C_BIT
选择 (p)->cktab[0b11010]
这个子 bitmap 用来进行接下来的进一步判断和操作(无论这个操作是 set 还是 test )。
现在,我们已经知道了 _C_BIT
把输入的除去了 3 个 LSB 之后剩下的 bits 用来映射为子 bitmap 选择子,那么,_C_MASK
利用的正是 _C_BIT
不要的那 3 个 LSB ,并且把这 3 个 LSB 映射到一个 char 内的 bit index 。因为,0x07 的二进制表示就是 0b111 ,让 _C_MASK
的输入对 0b111 进行按位 AND 操作就相当于取它的 3 个 LSB ,显然这个按位 AND 运算结果的范围是 0 到 7 ,也就是说 _C_MASK
相当于根据输入的 3 个 LSB 来决定用在一个 char 内的 mask 是多少。
以 0b11010011 这个输入为例,它的 3 个 LSB 是 011 ,1 << 0b11
就是 0b1000 ,相当于一个 char 内的第 4 个 LSB 的 mask 。
现在我们可以总结如下,对于一个大小为 M = 2^p = N * 8 (bits) 的 bitmap ,输入的 bit 2, bit 1, bit 0 被映射为单个 char 内的 mask ,bit p-1, bit p-2, ..., bit 3 组成的二进制数被映射为 char[N] 的选择子,用来从 char[N] 中选出一个 char 。
理解了 _C_BIT
, _C_IND
和 _C_MASK
之后,_PING_SET
,_PING_CLR
和 _PING_TST
都变得相对容易理解了。