V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
beyondstars
V2EX  ›  C++

inetutils-ping 实现的 bitmap

  •  
  •   beyondstars · 298 天前 · 1118 次点击
    这是一个创建于 298 天前的主题,其中的信息可能已经有所发展或是发生改变。

    简介

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

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2493 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 15:50 · PVG 23:50 · LAX 07:50 · JFK 10:50
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.