ipt_do_table解析

1.浏览器首先发送给服务器它的SSL的版本号和加密偏好（也就是指他们之间将要使用的symmetric key algorithm）
2.服务器给浏览器发送它的SSL版本号，加密偏好和证书。证书中包括了服务器的RSA公钥，且是由某CA认证的。CA认证指的是这个证书需要由CA的私钥进行签名。
（证书产生的过程是服务器把自己的公钥发送给CA，CA加上自己的私钥签名，保证它的完整性，生成证书）
3.浏览器有一个受信CA的列表，列表中有这些CA的公钥。当它收到证书的时候，它需要检测这个CA是否在列表当中。如果不在列表中，浏览器会警告用户通信的不安全。如果在的话，浏览器就使用这个证书得到服务器的公钥。
（浏览器用有信誉CA的公钥解密证书中的服务器公钥，如果这个CA不可信，可能是由某些不安全机构自设的CA，进行欺骗用）
4.浏览器生成了一个对称的session key，然后用服务器的公钥对它进行加密，然后把加密的session key发送给服务器。
（非对称加解密的方式比较耗时，不能把整个数据由这种方式加解密，而只采用它对对称密钥本身就行加解密，以后就使用对称的密钥进行加解密的工作，保证了密钥传递的安全性）
5.浏览器发送一个信息给服务器说未来我们之间的通信用这个session key进行加密。然后发送一个信息说浏览器端握手过程已经结束。
6.服务器给发送一个信息给浏览器说未来我们用这个session key进行加密。然后发送一个信息说服务器端的握手过程已经结束。
7.SSL session开始，服务器和浏览器之间用session key进行加密解密和验证数据完整性。      一个array中所有的元素先升序排列，后降序排列称之为Unimodal，Unimodal Search就是要找到这个最大的值，O(lgn)的做法就是二分法查询，如果所取的元素大于两边的元素，则是最大值，如果左面大，就在左半边取，右面大，则在右半边取，直到取到为止。应用在convex中找端点的最大x坐标和最大y坐标。找最大的x坐标就是在原本的排列中进行Unimodal Search，找最大的y坐标就是从找到的最大的x坐标那个点开始寻找到第一个点，在这些点中进行Unimodal Search。代码片段如下，写的很挫，不过还是能运行的。

 

 1 int middle(int *UnimodalList,int middlenum)
 2 {
 3         if((UnimodalList[middlenum]>UnimodalList[middlenum-1])&&
              (UnimodalList[middlenum]>UnimodalList[middlenum+1]))
 4                 return 1;
 5         else  
 6                 return 0;
 7 }
 8 int left(int *UnimodalList,int middlenum)
 9 {
10         if((UnimodalList[middlenum]<UnimodalList[middlenum-1])&&
              (UnimodalList[middlenum]>UnimodalList[middlenum+1]))
11                 return 1;
12         else 
13                 return 0;
14 }
15  
16 int UnimodalSearch(int * UnimodalList,int * indexp, int * maximump,int start, int end)
17 {
18         int size=NR_UnimodalList;
19         int middlenum=(start+end)/2;
20         if(middle(UnimodalList,middlenum))
21         {
22                 *indexp=middlenum;
23                 *maximump=UnimodalList[middlenum];
24                 return 0;
25         }
26         else if(left(UnimodalList,middlenum))
27         {
28                 return UnimodalSearch(UnimodalList,indexp,maximump,start,middlenum);
29         }
30         else 
31         {
32                 return UnimodalSearch(UnimodalList,indexp,maximump,middlenum,end);
33         }
34         return 1;
35 }
36  

关键词(Tag): unimodal search

阅读208次 评论1条 个人主页 扔小纸条 文件夹: Algorithm

收藏: QQ书签 del. 订阅: Google 抓虾

内核中的Notification Chains的分析

Damocles 发表于 2007-10-27 17:12:53

       Linux内核中有许多子系统，他们之间有着非常多的依赖与交互关系，当某一个子系统中有事件发生时，就会影响到其他子系统的工作，比如说网卡ip地址的改变，设备的热插拔等等。Linux内核中使用了Notification Chains的方法来处理这类事件，顾名思义，它是一个链表的数据结构，其中链表的表元由回调函数，priority和next指针组成。

 35 struct notifier_block {
 36         int (*notifier_call)(struct notifier_block *, unsigned long, void *);
 37         struct notifier_block *next;
 38         int priority;
 39 };

      当我们初始化子系统的时候，应该知道自己到底对哪些事件比较敏感，也就是说知道哪些事件的发生会对自己的功能发生影响，如果有的话，就注册自己到这个特定的notification chain里面去，我们举一个例子来看看：

1242 void __init arp_init(void)
1243 {
1244         neigh_table_init(&arp_tbl);
1245
1246         dev_add_pack(&arp_packet_type);
1247         arp_proc_init();
1248 #ifdef CONFIG_SYSCTL
1249         neigh_sysctl_register(NULL, &arp_tbl.parms, NET_IPV4,
1250                               NET_IPV4_NEIGH, "ipv4", NULL, NULL);
1251 #endif
1252         register_netdevice_notifier(&arp_netdev_notifier);
1253 }

      这个取自arp的初始化，我们注意最后一行的函数register_netdevice_notifier，这个就是注册函数，当然它还会有多层的调用，而arp_netdev_notifier就是一个notifier_block的结构，其中回调函数初始化为arp_netdev_event。我们先来看一下这个回调函数的实现

1201 static int arp_netdev_event(struct notifier_block *this, unsigned long event, void *ptr)
1202 {
1203         struct net_device *dev = ptr;
1204
1205         switch (event) {
1206         case NETDEV_CHANGEADDR:
1207                 neigh_changeaddr(&arp_tbl, dev);
1208                 rt_cache_flush(0);
1209                 break;
1210         default:
1211                 break;
1212         }
1213
1214         return NOTIFY_DONE;
1215 }

      我们看到了，它只关心一种event，那就是NETDEV_CHANGEADDR，其他的事件发生它就并不在意了，当网络设备发生任何已经定义好的事件时，会遍历notification chain来进行遍历通知，如果是我们关心的事件发生，我们就作出相应的反应进行处理，如果不是，那么就当什么都没有发生。
      注册函数有一个通用的类型函数，上文所见到的register_netdevice_notifier经过二层调用之后就会遇到，这个函数就是

105 static int notifier_chain_register(struct notifier_block **nl,
106                 struct notifier_block *n)
107 {
108         while ((*nl) != NULL) {
109                 if (n->priority > (*nl)->priority)
110                         break;
111                 nl = &((*nl)->next);
112         }
113         n->next = *nl;
114         rcu_assign_pointer(*nl, n);
115         return 0;
116 }

      这个函数的作用就是把一个notifier_block加入到chain中去，不过这个链表的插入方法有点诡异，因为它直接利用了二级指针的一个巧妙应用，一般我们插入链表都需要有一个指针来保存前一个位置，然后再插入表元，而在这里，它只利用了一个指针就完成了这些工作，也就是把这个二级指针保存了前一个表元的next指针。
      最后我们来看一下那个事件发生时通知在通知链上的表元的函数

131 static int __kprobes notifier_call_chain(struct notifier_block **nl,
132                 unsigned long val, void *v)
133 {
134         int ret = NOTIFY_DONE;
135         struct notifier_block *nb;
136
137         nb = rcu_dereference(*nl);
138         while (nb) {
139                 ret = nb->notifier_call(nb, val, v);
140                 if ((ret & NOTIFY_STOP_MASK) == NOTIFY_STOP_MASK)
141                         break;
142                 nb = rcu_dereference(nb->next);
143         }
144         return ret;
145 }

      这个函数应该很容易理解，就是调用回调函数进行处理。
      Notification Chains最重要的好处是每个子系统自己来注册到底需要听哪些事件，而不是事件的发生方来遍历各个子系统来问我的改变你们是不是需要进行相应的对策处理，这样效率就提高了，也就是所谓的publish-and-subscribe model。

      这周继续阅读netfilter部分的代码和文档，看了一下netfilter hacking howto和水木上的m文，对前一周一些没有搞懂的问题弄明白了。
      主要的一个问题是netfilter是在内核中，那么它和iptables这个基于user space的工具怎么交互呢？其实我们应该这么想，netfilter和table是分开实现的，我们通过协议类型和挂载点来找到的在二维数组nf_hooks的位置上，是一个链表的头指针，它所指向的这个链表中有对于这个特定协议和特定挂载点的对于各个表中规则的处理，这些表包括像filter，nat和mangle之类的表。我们在用户空间中调用iptables时，我们的参数为所针对的table，针对的处理链chain，match的规则，和最终的处理方式target，而它们中每个都能在内核空间找到对应关系，像chain针对的就是挂载点。
       我们重新回到nf_hooks数组，我们得到一个处理链表，自然进行遍历，在每个节点上都调用hook函数，hook函数指定为ipt_hook之类的函数，具体需要参照加载的函数，我们只是找出一个进行举例。ipt_hook调用ipt_do_table，这个函数是对table进行操作的，函数很长，我们来看一下。      

215 /* Returns one of the generic firewall policies, like NF_ACCEPT. */
216 unsigned int
217 ipt_do_table(struct sk_buff **pskb,
218              unsigned int hook,
219              const struct net_device *in,
220              const struct net_device *out,
221              struct ipt_table *table,//这个是我们要操作的table，如filter
222              void *userdata)                   
223 {
224         static const char nulldevname[IFNAMSIZ] __attribute__((aligned(sizeof(long))));
225         u_int16_t offset;
226         struct iphdr *ip;
227         u_int16_t datalen;
228         int hotdrop = 0;
//hotdrop为1时就直接返回NF_DROP了，这是快速扔包的方法
229         /* Initializing verdict to NF_DROP keeps gcc happy. */
230         unsigned int verdict = NF_DROP;
231         const char *indev, *outdev;
232         void *table_base;
233         struct ipt_entry *e, *back;
234         struct xt_table_info *private = table->private;
//xt_table_info中蕴含了整套规则，以及这些规则的偏移量，使寻找变得容易
235
236         /* Initialization */
237         ip = (*pskb)->nh.iph;
238         datalen = (*pskb)->len - ip->ihl * 4;
239         indev = in ? in->name : nulldevname;
240         outdev = out ? out->name : nulldevname;
241         /* We handle fragments by dealing with the first fragment as
242          * if it was a normal packet.  All other fragments are treated
243          * normally, except that they will NEVER match rules that ask
244          * things we don't know, ie. tcp syn flag or ports).  If the
245          * rule is also a fragment-specific rule, non-fragments won't
246          * match it. */
247         offset = ntohs(ip->frag_off) & IP_OFFSET;
248
249         read_lock_bh(&table->lock);
250         IP_NF_ASSERT(table->valid_hooks & (1 << hook));
251         table_base = (void *)private->entries[smp_processor_id()];
252         e = get_entry(table_base, private->hook_entry[hook]);
//得到这个hook点起始规则的偏移
253
254         /* For return from builtin chain */
255         back = get_entry(table_base, private->underflow[hook]);
//得到这个hook点规则末尾的偏移
256
257         do {
258                 IP_NF_ASSERT(e);
259                 IP_NF_ASSERT(back);
260                 if (ip_packet_match(ip, indev, outdev, &e->ip, offset)) {
261                         struct ipt_entry_target *t;
262
263                         if (IPT_MATCH_ITERATE(e, do_match,
264                                               *pskb, in, out,
265                                               offset, &hotdrop) != 0)
//这个宏用来遍历所有的match，会调用do_match函数
266                                 goto no_match;
//如果没有匹配的规则，则跳转到no_match
267
268                         ADD_COUNTER(e->counters, ntohs(ip->tot_len), 1);
269
270                         t = ipt_get_target(e);//获得target
271                         IP_NF_ASSERT(t->u.kernel.target);
272                         /* Standard target? */
273                         if (!t->u.kernel.target->target) {
//当为NULL时，就是standard target，它是没有模块定义target函数的
274                                 int v;
275
276                                 v = ((struct ipt_standard_target *)t)->verdict;
277                                 if (v < 0) {
278                                         /* Pop from stack? */
279                                         if (v != IPT_RETURN) {
280                                                 verdict = (unsigned)(-v) - 1;
281                                                 break;
282                                         }
283                                         e = back;
284                                         back = get_entry(table_base,
285                                                          back->comefrom);
286                                         continue;
287                                 }
288                                 if (table_base + v != (void *)e + e->next_offset
289                                     && !(e->ip.flags & IPT_F_GOTO)) {
290                                         /* Save old back ptr in next entry */
291                                         struct ipt_entry *next
292                                                 = (void *)e + e->next_offset;
293                                         next->comefrom
294                                                 = (void *)back - table_base;
295                                         /* set back pointer to next entry */
296                                         back = next;
297                                 }
298
299                                 e = get_entry(table_base, v);
300                         } else {
301                                 /* Targets which reenter must return
302                                    abs. verdicts */
303 #ifdef CONFIG_NETFILTER_DEBUG
304                                 ((struct ipt_entry *)table_base)->comefrom
305                                         = 0xeeeeeeec;
306 #endif
307                                 verdict = t->u.kernel.target->target(pskb,
308                                                                      in, out,
309                                                                      hook,
310                                                                      t->u.kernel.target,
311                                                                      t->data,
312                                                                      userdata);
//调用模块中定义的target函数，返回一个verdict
313
314 #ifdef CONFIG_NETFILTER_DEBUG
315                                 if (((struct ipt_entry *)table_base)->comefrom
316                                     != 0xeeeeeeec
317                                     && verdict == IPT_CONTINUE) {
318                                         printk("Target %s reentered!\n",
319                                                t->u.kernel.target->name);
320                                         verdict = NF_DROP;
321                                 }
322                                 ((struct ipt_entry *)table_base)->comefrom
323                                         = 0x57acc001;
324 #endif
325                                 /* Target might have changed stuff. */
326                                 ip = (*pskb)->nh.iph;
327                                 datalen = (*pskb)->len - ip->ihl * 4;
328
329                                 if (verdict == IPT_CONTINUE)
330                                         e = (void *)e + e->next_offset;
331                                 else
332                                         /* Verdict */
333                                         break;
334                         }
335                 } else {
336
337                 no_match:
338                         e = (void *)e + e->next_offset;
//如果没有匹配，则找到下一个ipt_entry
339                 }
340         } while (!hotdrop);
341
342         read_unlock_bh(&table->lock);
343
344 #ifdef DEBUG_ALLOW_ALL
345         return NF_ACCEPT;
346 #else
347         if (hotdrop)
348                 return NF_DROP;
349         else return verdict;
350 #endif
351 }

做一些基本的注释，其实我不喜欢一篇技术博客长篇累牍贴代码，尤其是Linux内核源代码，更多的是希望能够进行分析。但往往越是讨厌的事情，自己往往又这么做了。好吧，还是来解释一下这个函数吧。
它是对table进行操作，至于对于哪个table，是由调用函数决定的。调用之后，他的主要工作如下：
1.找到table的地址，其实重要的是找到ipt_entry的地址，因为里面存着match和target。
2.对match进行匹配，如果匹配成功，则获取target。如果失败，跳转到no_match，找到下一个ipt_entry，进行下一轮匹配。
3.成功的话会有两种情况，一是得到初始化时候的standard target，这时候target函数是初始化为NULL的。二是得到一个由用户新加的target，跟据verdict和hotdrop，来决定是怎么返回。
这边有一点需要指出的是，match的匹配原则是如果这个数据包都匹配了，则不再进行比较，直接可以返回了，只有在no match的情况下才继续匹配下一条match。这个和在上文提到的nf_iterate中的处理方式不同，这个要小心区分的。在同一张表中，是只要匹配就返回verdict，而在nf_iterate 调用钩子函数处理中，如果是ACCEPT的情况，则需要继续处理。天哪，其实这个貌似没有什么特别的联系，只是我自己混淆了一开始，我想大家应该不会像我 这样犯这么低级的错误，写出来算是警戒一下自己。

刚才做了个实验，验证了一下。
实验一：
sudo iptables -t filter -A INPUT -j ACCEPT -p tcp
sudo iptables -t filter -A INPUT -j DROP -p tcp -s hk-in-f104.google.com
这时候是能访问google的，因为数据包进入钩子函数之后只匹配了第一条就返回了，第二条规则是没有意义的。

实验二：
sudo iptables -t filter -A INPUT -j DROP -p tcp -s hk-in-f104.google.com
sudo iptables -t filter -A INPUT -j DROP -p tcp
这时候不能访问任何网站，因为google以外任意一个网站第一条不匹配，则进入下一条，然后drop掉，google则第一条就不匹配，直接drop。

        这个在ip_do_table的源代码里面就很清楚了。至于表示table的那些源代码，真的是看了厥倒，这种匪夷所思的数据结构，这些hacker们还胆子真够大的，真不怕内存读写错误啊，要是我我可不敢这么写，他们果然是艺高人胆大，这个下次再分析吧，今天还算是差不多搞清楚了。