MFC_HASH 在 /net/ipmr.c

Question

我正在处理多播并在 linux 代码 (ipmr.c) 中遇到了这个散列。据我了解，散列 table 大小为 64。并且 MFC_HASH 占用最高 8 位的 ip 目标地址和最高 6 位的源 ip 地址。它将和与 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 地址取模？另外，如果我想将散列 table 的大小从 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)

MFC_HASH 在 /net/ipmr.c

MFC_HASH in /net/ipmr.c

c

linux

hash

kernel

linux-kernel