inetutils-ping 实现的 bitmap

21次阅读

共计 1841 个字符，预计需要花费 5 分钟才能阅读完成。

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 都变得相对容易理解了。

正文完