c -/net/ipmr.c中的MFC_HASH

Question

我正在处理多播并在 linux 代码 (ipmr.c) 中遇到了这个散列。据我所知，哈希表的大小是 64。MFC_HASH 占用 ip 目标地址的最高 8 位和源 ip 地址的最高 6 位。它将 和 与 63 进行异或运算。因此结果必然在 0-63 之间。

请查看以下代码了解更多信息。

struct mr_table {
          struct list_head        list;
          possible_net_t          net;
          u32                     id;
          struct sock __rcu       *mroute_sk;
          struct timer_list       ipmr_expire_timer;
          struct list_head        mfc_unres_queue;
          struct list_head        mfc_cache_array[MFC_LINES];
...
...
}

 #define MFC_LINES               64

 #ifdef __BIG_ENDIAN
 #define MFC_HASH(a,b)   ((((a)>>24)^((b)>>26))&(MFC_LINES-1))
 #else
 #define MFC_HASH(a,b)   (((a)^((b)>>2))&(MFC_LINES-1))
 #endif

这个散列有什么特别之处？它比仅添加两个 ip 地址并以 63 取模更好。或者仅对组 ip 地址取模？另外，如果我想将哈希表大小从 64 增加到 128，那么将 MFC_LINE 更改为 128 就足够了吗？或者我是否需要更改 MFC_HASH 使用的 group-ip 和 source-ip 的位数？有人可以帮忙吗？我的机器是大端。

谢谢。

Answer 1

How is it better than just adding the two ip addresses and doing a modulo by 63.?

如果您添加两个 IP 地址并取模 64(它应该是 64，而不是 63)，那么更高的字节将被忽略，因为它们是 0x40 的倍数。此散列的目的是根据最高地址位来区分地址。这就是为什么它首先对它们进行异或运算，然后才将它们放入 [0, 63] 范围内。

例子:

一个:255.0.0.0

b: 54.0.0.0

(a + b) = 35.0.0.2(忽略 unsigned int 溢出 - 硬件将丢弃最左边的位)

35.0.0.0 % 64 = 0(35.0.0.0 = 889192448 = 13893632 * 64 + 0)