netfilter中early_drop()函数中的疑问

__dreamcatcher

在netfilter的连接跟踪模块中，初始化一个新链接时需要调用nf_conntrack_alloc()函数，在这个函数中需要判断连接数是否超过连接数的最大值(atomic_read(&net->ct.count) > nf_conntrack_max)，之后调用early_drop()函数。小弟现在对early_drop()函数存在些疑问，请大家指点帮忙！

1. 498 static noinline int early_drop(struct net *net, unsigned int hash)
   
2. 499 {
   
3.                         ...
   
4. 507     rcu_read_lock();
   
5. 508     for (i = 0; i < net->ct.htable_size; i++) {
   
6. 509         hlist_nulls_for_each_entry_rcu(h, n, &net->ct.hash[hash],
   
7. 510                      hnnode) {
   
8. 511             tmp = nf_ct_tuplehash_to_ctrack(h);//为什么要这么做？
   
9. 512             if (!test_bit(IPS_ASSURED_BIT, &tmp->status))
   
10. 513                 ct = tmp;
    
11. 514             cnt++;
    
12. 515         }
    
13. 516
    
14. 517         if (ct != NULL) {
    
15. 518             if (likely(!nf_ct_is_dying(ct) &&
    
16. 519                    atomic_inc_not_zero(&ct->ct_general.use)))
    
17. 520                 break;
    
18. 521             else
    
19. 522                 ct = NULL;
    
20. 523         }
    
21. 524
    
22. 525         if (cnt >= NF_CT_EVICTION_RANGE)
    
23. 526             break;
    
24. 527
    
25. 528         hash = (hash + 1) % net->ct.htable_size;
    
26. 529     }
    
27. 530     rcu_read_unlock();
    
28. 531
    
29. 532     if (!ct)
    
30. 533         return dropped;
    
31. 534
    
32. 535     if (del_timer(&ct->timeout)) {
    
33. 536         death_by_timeout((unsigned long)ct);
    
34. 537         dropped = 1;
    
35. 538         NF_CT_STAT_INC_ATOMIC(net, early_drop);
    
36. 539     }
    
37. 540     nf_ct_put(ct);//ct上的计数减1
    
38. 541     return dropped;
    
39. 542 }

复制代码

在这个函数中的问题是：

hlist_nulls_for_each_entry_rcu(h, n, &net->ct.hash[hash],
510                      hnnode) {
511             tmp = nf_ct_tuplehash_to_ctrack(h);
512             if (!test_bit(IPS_ASSURED_BIT, &tmp->status))
513                 ct = tmp;                 //当test_bit()多次满足时，ct都会发生变化，为什么要这么做？ 还有就是cnt只在初始时被初始化为0，之后一直是cnt++，这样累加到8之后就跳出循环，其作用？
514             cnt++;
515         }            

if (cnt >= NF_CT_EVICTION_RANGE)  //cnt++，这样累加到8之后就跳出循环，不明白其含义
            break;

独孤九贱

1.         rcu_read_lock();
   
2.         for (i = 0; i < nf_conntrack_htable_size; i++) {
   
3.                 hlist_nulls_for_each_entry_rcu(h, n, &net->ct.hash[hash],
   
4.                                          hnnode) {
   
5.                         tmp = nf_ct_tuplehash_to_ctrack(h);
   
6.                         if (!test_bit(IPS_ASSURED_BIT, &tmp->status))
   
7.                                 ct = tmp;
   
8.                         cnt++;
   
9.                 }
   
10. 
    
11.                 if (ct && unlikely(nf_ct_is_dying(ct) ||
    
12.                                    !atomic_inc_not_zero(&ct->ct_general.use)))
    
13.                         ct = NULL;
    
14.                 if (ct || cnt >= NF_CT_EVICTION_RANGE)
    
15.                         break;
    
16.                 hash = (hash + 1) % nf_conntrack_htable_size;
    
17.         }
    
18.         rcu_read_unlock();

复制代码

这段代码的核心功能是，当会话表满了过会，清除一些半连接，为新的会话腾出空间来。它的思路很简单，就是遍历当前hash槽位的链，找到一个半连接。
这段代码由一个双重循环组成，第一重循环：
hlist_nulls_for_each_entry_rcu()遍历指定hash的槽位。当它结束时，有两种结果：
a、通过test_bit，已经找到了，此时ct就是要找的值；
b、没有找到，ct为NULL，cnt是一个计数器，累计在“当前hash槽位的查找次数(事实上，hash会变化，所以它是所有查找次数的总和)”；

如果找到到后，即会判断ct的合法性：

1.                 if (ct && unlikely(nf_ct_is_dying(ct) ||
   
2.                                    !atomic_inc_not_zero(&ct->ct_general.use)))
   
3.                         ct = NULL;

复制代码

结果合法，或者当cnt大于一个常数(NF_CT_EVICTION_RANGE)，则退出外层循环。

1.                 if (ct || cnt >= NF_CT_EVICTION_RANGE)
   
2.                         break;

复制代码

ct找到了退出循环是理所当然的事情。至于cnt超限，也要退出循环，这是和下一句代码紧密相连的：

1. hash = (hash + 1) % nf_conntrack_htable_size;

复制代码

也就是说，如果没有查找，或者cnt没有超限，hash值会往复递增，注意，是“往复”，往复的含义是:

1. hash = (hash + 1) % nf_conntrack_htable_size

复制代码

而不是

1. hash = hash + 1;
   
2. if(hash > XXX)  break;

复制代码

。也就是说，周而复始的在下一个hash链中再找空位……这样一来，引入cnt的理由就显而意见了：必须得有一个变量来决定，如果ct一直找不到，得有一种决定退出外层循环的条件，cnt就是这个条件。所以，它只有初值会0，后面就一直递加了。作者认为，当查找的次数超过NF_CT_EVICTION_RANGE次，就必须得退出来了，不能一直占着CPU不放。你也可以自定义这个常数，4，16，32（当然，从效率的角度来讲，它不能太大了）……可以多做一些实现来得到一个经验值。我个人倒是认为8是一个比较好的值。

再退一步讲，个人认为，即使hash值不是一个“周而复始的值”，也应该有也一变量来决定查找的次数，不能长时间地占着hash表来查找……

kwest

你内核版本是多少？我的内核没有cnt累加。

独孤九贱

你内核版本是多少？我的内核没有cnt累加。
kwest 发表于 2010-09-17 10:43

楼上的版本out啦！至于没有cnt，应该跟其释放的思路有关，以2.6.12为例：

1.         READ_LOCK(&ip_conntrack_lock);
   
2.         h = LIST_FIND_B(chain, unreplied, struct ip_conntrack_tuple_hash *);
   
3.         if (h) {
   
4.                 ct = tuplehash_to_ctrack(h);
   
5.                 atomic_inc(&ct->ct_general.use);
   
6.         }
   
7.         READ_UNLOCK(&ip_conntrack_lock);

复制代码

老的释放方式是，仅释放对应的hash槽位。因为hash槽位的链长有限，所以，也就没有做cnt计数。

而新的释放方式是，如果当前hash槽位没有找到合适的值，就“顺便”去清理下一个hash位，这是因为调用early_drop时，是会话表已满，这回不释放，下次也要再来调用，反正来都来了，就顺便搞一下吧(除非再也没有新建会话的到来，这种机率太小了)。这样就少一次函数调用啦，作者真是煞费苦心呀！！

__dreamcatcher

刚看到回帖，谢谢九贱大哥和各位大虾，我继续研究研究！

__dreamcatcher

这段代码的核心功能是，当会话表满了过会，清除一些半连接，为新的会话腾出空间来。它的思路很简单，就是遍历当前hash槽位的链，找到一个半连接。
这段代码由一个双重循环组成，第一重循环：
hlist_nulls_for_each_entry_rcu()遍历指定hash的槽位。当它结束时，有两种结果：
a、通过test_bit，已经找到了，此时ct就是要找的值；
b、没有找到，ct为NULL，cnt是一个计数器，累计在“当前hash槽位的查找次数(事实上，hash会变化，所以它是所有查找次数的总和)”；

独孤九贱 发表于 2010-09-17 10:05

谢谢九贱大哥的指点，在这里还是有点疑问：
     1、在第一层循环里面通过test_bit，查找合适的ct，但是不明白的是在找到了合适的ct后为什么没又跳出第一层循环，而是继续的进行test_bit？
     2、如果在同一个hash槽位的链中找到两个或者更多的半连接状态的ct，那样的话，程序却只对最后一个ct进行del_timer(&ct->timeout)以及death_by_timeout((unsigned long)ct)等，没有对之前查找到的半连接进行处理，感觉这样是不是有点低效和浪费资源？
可能是我理解不正确，请大虾指点！

独孤九贱

这是作者实现的机制方面的问题了。
“程序却只对最后一个ct进行del_timer(&ct->timeout)以及death_by_timeout((unsigned long)ct)等，没有对之前查找到的半连接进行处理，感觉这样是不是有点低效和浪费资源？”

因为新建的时候满了，需要释放一个，所以，不存在“释放多个”。所以，作者之所以不退出循环，找到“最后一个”，而不是第一个，是不是基于如下理由（我大致看了一下，没有仔细看）：

在向hash槽位的链追加新节点的时候，每个节点，是被加入到链的首部(head)：

1. static void __nf_conntrack_hash_insert(struct nf_conn *ct,
   
2.                                        unsigned int hash,
   
3.                                        unsigned int repl_hash)
   
4. {
   
5.         struct net *net = nf_ct_net(ct);
   
6. 
   
7.         hlist_nulls_add_head_rcu(&ct->tuplehash[IP_CT_DIR_ORIGINAL].hnnode,
   
8.                            &net->ct.hash[hash]);
   
9.         hlist_nulls_add_head_rcu(&ct->tuplehash[IP_CT_DIR_REPLY].hnnode,
   
10.                            &net->ct.hash[repl_hash]);
    
11. }

复制代码

所以释放的时候，是想尽量找到时间久远的节点，所以要找最后一个。呵呵，仅供讨论哈！

__dreamcatcher

谢谢九贱大哥，

释放的时候，是想尽量找到时间久远的节点，所以要找最后一个

这个理由我也想过了，但是感觉这个理由不是很充分。
      既然是双向链表，那么想找到最早到达的链接，直接从first->pprev指针开始通过pprev往前找，寻找到第一个符合条件的就应该可以跳出循环了，但是这里却用for循环扫描一遍，是不是有点低效了呀？是不是还有其他原因？