当前位置：首页 > 实用文档 > 其他范文> Linux内核分析网络[十一]：ICMP模块

Linux内核分析网络[十一]：ICMP模块

时间：2022-05-06 12:23:12 其他范文收藏本文下载本文

Linux内核分析网络[十一]：ICMP模块(（锦集5篇））由网友“中隐”投稿提供，下面是小编为大家整理后的Linux内核分析网络[十一]：ICMP模块，如果喜欢可以分享给身边的朋友喔!

篇1：Linux内核分析网络[十一]：ICMP模块

内核版本：2.6.34

ICMP模块比较简单，要注意的是icmp的速率限制策略，向IP层传输数据ip_append_data和 ip_push_pending_frames()，

在net/ipv4/af_inet.c中的inet_init()注册icmp协议，从这里也可以看出，ICMP模块是绑定在IP模块之上的。inet_add_protocol()会将icmp_protocol加入到全局量inet_protos中。

if (inet_add_protocol(&icmp_protocol, IPPROTO_ICMP) < 0)printk(KERN_CRIT “inet_init: Cannot add ICMP protocoln”); icmp_protocol定义如下： static const struct net_protocol icmp_protocol = {.handler = icmp_rcv,.no_policy = 1,.netns_ok = 1, };

除了注册icmp协议，还要对icmp模块初始化，这部分由icmp_init()完成。

if (icmp_init() < 0)panic(“Failed to create the ICMP control socket.n”);

icmp_init()函数做的事很简单，register_pernet_subsys(&icmp_sk_ops)，而注册icmp网络子系统过程中会调用 icmp_sk_ops.init(即icmp_sk_init函数)来完成它的初始化，下面具体看icmp_sk_init()函数。

首先为net为配CPU数目 (nr_cpu_ids)个struct sock结构体空间，这里的net是全局的网络名，一般是init_inet。

net->ipv4.icmp_sk = kzalloc(nr_cpu_ids * sizeof(struct sock *), GFP_KERNEL);

每个CPU i，它的sock结构体位于net中的icmp_sk[i]。于每个CPU i，初始化刚刚分配的icmp_sk[i]：

-第一步，inet_ctl_sock_create()创建sk，并在net->ipv4.icmp_sk[i] = sk中将其赋值给icmp_sk[i]。

-第二步：ICMP发送缓存区大小sk_sndbuf设置为128K

for_each_possible_cpu(i) {struct sock *sk;err = inet_ctl_sock_create(&sk, PF_INET, SOCK_RAW, IPPROTO_ICMP, net);if (err < 0) goto fail; net->ipv4.icmp_sk[i] = sk;sk->sk_sndbuf = (2 * ((64 * 1024) + sizeof(struct sk_buff)));sock_set_flag(sk, SOCK_USE_WRITE_QUEUE);inet_sk(sk)->pmtudisc = IP_PMTUDISC_DONT; }

忽略发往广播地址的icmp echo报文；忽略发往广播地址的错误的响应报文；

net->ipv4.sysctl_icmp_echo_ignore_all = 0; net->ipv4.sysctl_icmp_echo_ignore_broadcasts = 1; net->ipv4.sysctl_icmp_ignore_bogus_error_responses = 1;

设置icmp处理速率，这里的ratelimit和ratemask参数在后面限速处理时会具体用到。

net->ipv4.sysctl_icmp_ratelimit = 1 * HZ; net->ipv4.sysctl_icmp_ratemask = 0x1818; net->ipv4.sysctl_icmp_errors_use_inbound_ifaddr = 0;

初始化工作完成后，还是从icmp的接收开始，icmp_rcv 完成icmp报文的处理。

取得icmp报头，此时skb->transport_header是在IP模块处理中的ip_local_deliver_finish() 将其设置为了指向icmp报头的位置。

icmph = icmp_hdr(skb);

根据icmp的类型type交由不同的处理函数去完成。

icmp_pointers[icmph->type].handler(skb);

icmp_pointers是在icmp.c中定义的全局量，部分如下：

static const struct icmp_control icmp_pointers[NR_ICMP_TYPES + 1] = {[ICMP_ECHOREPLY] = { .handler = icmp_discard,},[1] = { .handler = icmp_discard, .error = 1,}, …… }

比如对于收到的icmp报文type为0或1(响应答复或目的不可达)，协议栈要做的就是丢弃掉它 – icmp_discard()。下面以icmp echo和icmp timestamp为例说明。

收到icmp echo报文执行icmp_echo()

icmp_param是回复时信息，它直接拷贝了echo的ICMP报头icmp_hdr(skb)，仅仅改变了报头的type = ICMP_ECHO_REPLY，然后调用icmp_reply()处理发送。

struct icmp_bxm icmp_param; icmp_param.data.icmph = *icmp_hdr(skb); icmp_param.data.icmph.type = ICMP_ECHOREPLY; icmp_param.skb = skb; icmp_param.offset = 0; icmp_param.data_len = skb->len; icmp_param.head_len = sizeof(struct icmphdr); icmp_reply(&icmp_param, skb);

收到icmp timestamp报文后执行icmp_timestamp()

经过IP层处理，skb- >data指向icmp报头的位置，而报头最小为4字节，所以这里判断skb->len < 4，是则丢弃该报文。从这里也可以看出，时间戳请求报文可以只有4节字头部，而没有时间戳信息。

if (skb->len < 4)goto out_err;

这段代码设置时间戳响应的时间戳信息，包括接收时间戳和发送时间戳，两者分别代表主机收到报文的时间，发送响应报文的时间，而从这部分代码也可以看出icmp_param.data.times[2] = icmp_param.data.times[1]协议栈简单的将接收和发送时间戳置为相同的。时间戳的计算很简单，格林尼治时间的当天时间的微秒数。最后skb_copy_bits()从skb的 ICMP报文内容拷贝4节字的时间到icmp_param_data.times[0]，即发起时间戳，所以最后情形如下：

icmp_param_data.times[0] 发起时间戳，从请求报文中拷贝

icmp_param_data.times[0] 接收时间戳，处理ICMP报头时的时间

icmp_param_data.times[0] 发送时间戳，设置为与接收时间戳相同

getnstimeofday(&tv); icmp_param.data.times[1] = htonl((tv.tv_sec % 86400) * MSEC_PER_SEC + tv.tv_nsec / NSEC_PER_MSEC); icmp_param.data.times[2] = icmp_param.data.times[1]; if (skb_copy_bits(skb, 0, &icmp_param.data.times[0], 4))BUG();

前面已经说过，icmp_param就是要发送ICMP报文的内容，上面设置了内容，接下来设置报头，同样是直接拷贝了ICMP请求的报头，改变type为ICMP_TIMESTAMPREPLY。注意这里的data_len设置为0，因为它与icmp echo不同，一定是没有分片的，即没有paged_data部分。head_len设置为icmphdrlen+12，这里是为了调用icmp_reply()回复时的统一，实现表示ICMP部分的长度，主要是有分片时会根据head_len来跳过报头而只拷贝每个分片的内容。

icmp_param.data.icmph = *icmp_hdr(skb); icmp_param.data.icmph.type = ICMP_TIMESTAMPREPLY; icmp_param.data.icmph.code = 0; icmp_param.skb = skb; icmp_param.offset = 0; icmp_param.data_len = 0; icmp_param.head_len = sizeof(struct icmphdr) + 12;

最后调用icmp_reply()回复，这与icmp_echo()是相同的。

icmp_reply(&icmp_param, skb);

注意两者设置icmp_param参数时的区别：

icmp_echo()中 icmp_param.data_len=skb->len;

icmp_param.head_len=sizeof(struct icmphdr);

icmp_timestamp()中icmp_param.data_len=0。

icmp_param.head_len=sizeof(struct icmphdr) +12;

icmp_reply()

通过ip_route_output_key()查找路由信息，存放在rt中。路由项在这里有两个作用：一是限速是针对每个路由项的，在icmpv4_xrlim_allow()中会用到；二是将报文传递给IP层需要用到rt。仔细观察流程可以发现，报文在协议栈传递过程中，在IP层会查找一次路由表获取到了rt，而在这里又查找了一次路由表，似乎是重复了。其实不是，IP层查找是在报文接收阶段，这里的查找是在报文的发送阶段。

{struct flowi fl = { .nl_u = { .ip4_u = { .daddr = daddr, .saddr = rt->rt_spec_dst, .tos = RT_TOS(ip_hdr(skb)->tos) } }, .proto = IPPROTO_ICMP };security_skb_classify_flow(skb, &fl);if (ip_route_output_key(net, &rt, &fl)) goto out_unlock; }

协议栈对于部分ICMP报文进行了限速，但这种限速不是整体的，而是针对每个路由项的，即限制每个地址发送ICMP报文的限率。icmpv4_xrlim_allow()判断该icmp报文是否需要被限速，如果能接收，则调用icmp_puash_reply()发送响应。

if (icmpv4_xrlim_allow(net, rt, icmp_param->data.icmph.type, icmp_param->data.icmph.code))icmp_push_reply(icmp_param, &ipc, &rt);

icmpv4_xrlim_allow() -> xrlim_allow() 限速处理

速率有关的参数是在icmp_init() -> icmp_sk_init()创建ICMP的sock时设置的，ratelimit是限制的速率，即TBF代码段中的 timeout，可以理解成一个令牌；ratemask是被限制速率的ICMP的报文类型，(1 << type & retemask) == 1判断是否限速，type即ICMP类型，可见默认情况下[3]dest unreachable, [4]source quench, [11]time exceeded, [12]parameter problem才会被限速。

net->ipv4.sysctl_icmp_ratelimit = 1 * HZ; net->ipv4.sysctl_icmp_ratemask = 0x1818;

限速使用了Token Bucket Filter(令牌环过滤器)思想，大致是每个到来的令牌从数据队列中收集一个数据包，然后从桶中删除。令牌被耗尽时，数据包将停止发送一段时间。

ICMP的限速使用的就是这种思想，不过时间作为令牌，它的增长是连续的；每来一个报文，拿走一个令牌，则是一个时间段timeout，令牌也限定了最大数目是XRLIM_BURST_FACTOR为6；简单来讲就是每过timeout时间，令牌数就加1，当令牌数达到6时不再增加；而来一个报文，令牌数就减一，当令牌数为空时，不再减少，该报文也被丢弃；在这种情况下，在过timeout时间，才会处理下一个报文。实现的代码段如下：

#define XRLIM_BURST_FACTOR 6 int xrlim_allow(struct dst_entry *dst, int timeout) {unsigned long now, token = dst->rate_tokens;int rc = 0; now = jiffies;token += now - dst->rate_last;dst->rate_last = now;if (token > XRLIM_BURST_FACTOR * timeout) token = XRLIM_BURST_FACTOR * timeout;if (token >= timeout) { token -= timeout; rc = 1;}dst->rate_tokens = token;return rc; }

dst->rate_tokens记录上一次的令牌，dst->rate_last记录上一次访问时间，now – dst->rate_last为经过的时间即增加的令牌数；当token>=timeout时即至少还有一个令牌，反回rc=1表示仍有令牌，不用限速；否则返回rc=0，限速。

icmp_push_reply() 发送回复报文

取出icmp使用的sock sk

sk = icmp_sk(dev_net((*rt)- >u.dst.dev));

if中的ip_append_data()函数表示把数据添加到sk->sk_write_queue，这个函数是用于上层向IP层传输报文，它会进行分片的操作，实际是帮IP层做了分片，

具体函数调用参见后面的ip_append_data()函数分析。正常情况 ip_append_data()返回0,即if的执行语句不会被触发。

if (ip_append_data(sk, icmp_glue_bits, icmp_param, icmp_param->data_len+icmp_param->head_len, icmp_param->head_len, ipc, rt, MSG_DONTWAIT) < 0) ip_flush_pending_frames(sk);

else if进入条件是sk->sk_write_queue中已有数据，显然在if的判断语句中已经将报文添加到了sk->sk_write_queue中，所以会进入else if执行语句调用ip_push_pending_frames()将报文传递给IP层。而在ip_append_data()函数中可以看到，它只是拷贝了报文内容，并没有生成ICMP报头，ICMP报头生成当然也是在通过 ip_push_pending_frames()将报文发给IP层前生成的。取出skb，计算所有分片一起的校验和，然过通过 csum_partial_copy_nocheck()生成新的icmp报头，最后调用ip_push_pending_frames()发送数据到IP层。函数 ip_push_pending_frames()函数分析也参见后文。

else if ((skb = skb_peek(&sk->sk_write_queue)) != NULL) {struct icmphdr *icmph = icmp_hdr(skb);__wsum csum = 0;struct sk_buff *skb1; skb_queue_walk(&sk->sk_write_queue, skb1) { sum = csum_add(csum, skb1->csum);}csum = csum_partial_copy_nocheck((void *)&icmp_param->data, (char *)icmph, icmp_param->head_len, csum);icmph->checksum = csum_fold(csum);skb->ip_summed = CHECKSUM_NONE;ip_push_pending_frames(sk); }

ip_append_data() 添加要传递到IP层的数据

传入参数的解释：

getfrag() – 复制数据，这里使用函数指针隐藏了复制细节，因为针对icmp, udp的复制是不同的；

from – 被复制的数据，在icmp模块中该参数传入的是struct icmp_bxm；

length – IP报文内容长度

transhdrlen – 传输报头长度，尽管ICMP归为网络层协议，但这里的transhdrlen 也是包括它的，所以更好的解释是表示IP上一层的报头，比如ICMP报头，IGMP报头，UDP报头等长度

ip_append_data()函数比较复杂，这里以两个例子来解释这个函数：发送50 Byte的echo报文，发送600 Byte的echo报文。56字节echo报文在IP层不需要分片；600字节echo报文在IP层需要分片。ip_append_data()还可以多次调用来收集数据，而在ICMP模块中这点并不能体现出来，在以后UDP或TCP时再以解释多次调用的情况。

example 1：50 Byte echo报文 [假设MTU=520]

如果 sk_write_queue为空，则证明是第一个分片，50字节的报文只需要一个分片。这里会设置exthdrlen，表示链路层额外的报头长，一般情况下是0，所以此时length和transhdrlen值仍是传入的值。而sk->sk_sndmsg_page和sk->sk_sndmsg_off与发散/ 聚合IO有关，这里先不考虑。

if (skb_queue_empty(&sk->sk_write_queue)) {…. sk->sk_sndmsg_page = NULL;sk->sk_sndmsg_off = 0; if ((exthdrlen = rt->u.dst.header_len) != 0) { length += exthdrlen; transhdrlen += exthdrlen;}… }

设置各种参数的值，hh_len表示以太网报头的长度，16字节对齐；fragheaderlen表示分片报头长度，即IP报头； maxfraglen表示最大分片长度。各参数值：hh_len = 16, fragheaderlen = 20, maxfraglen = 516，注意要求的节字对齐。

hh_len = LL_RESERVED_SPACE(rt->u.dst.dev); fragheaderlen = sizeof(struct iphdr) + (opt ? opt->optlen : 0); maxfraglen = ((mtu - fragheaderlen) & ~7) + fragheaderlen;

此时sk- >sk_write_queue还为空，跳转至alloc_new_skb执行分配新的skb。

if ((skb = skb_peek_tail(&sk->sk_write_queue)) == NULL)goto alloc_new_skb;

fraggap在上一个skb没有8字节对齐时设置为多余的字节数，否则的话fraggap=0；datalen表示 IP报文长度(不包括IP报头)，fraglen表示以太网帧报文长度(不包括以太网头)，alloclen表示要分配的内容长度，下面代码省略了一些内容。各参数值： fraggap=0, datalen=50, fraglen=70, alloclen=70。

fraggap = 0; datalen = length + fraggap; fraglen = datalen + fragheaderlen; alloclen = datalen + fragheaderlen;

分配报文skb空间，大小为alloclen+hh_len+15，alloclen + hh_len就是报文的长度，15个字节为预留部分。

if (transhdrlen) {skb = sock_alloc_send_skb(sk, alloclen + hh_len + 15, (flags & MSG_DONTWAIT), &err); }

skb_reserve()保留skb头的hh_len大小，skb_put()扩展skb大小到fraglen，然后设置network_header和 transport_header指向skb的正确位置，data指向ICMP报头的位置，具体可以看下面的图示：

skb_reserve(skb, hh_len); …… data = skb_put(skb, fraglen); skb_set_network_header(skb, exthdrlen); skb->transport_header = (skb->network_header + fragheaderlen); data += fragheaderlen;

copy是要拷贝的长度，为传输层报头后的内容大小。getfrag()函数实现数据的拷贝，在icmp模块中， getfrag()指向icmp_glue_bits()函数，它从[from] + offset处拷贝copy个字节到data + transhdrlen处。

copy = datalen - transhdrlen - fraggap; if (copy > 0 && getfrag(from, data + transhdrlen, offset, copy, fraggap, skb) < 0) {err = -EFAULT;kfree_skb(skb);goto error; }

偏移offset加上已经拷贝的字节数copy，fraggap=0，length减去的就是IP报文内容长度，由于报文才56字节，一个分片足够，所以length=0，然后把新生成的skb放入sk->sk_write_queue中，然后执行下次while循环。各参数值：copy=42, ffset=42, length=0, 更新transhdrlen=0。

offset += copy; length -= datalen - fraggap; transhdrlen = 0; …… __skb_queue_tail(&sk->sk_write_queue, skb); continue;

while循环判断条件是length > 0，因此跳出循环，完成了向IP层发送的数据生成，结果如下，注意， ICMP报头还是没有填写的：

example 2：600 Byte echo 报文[假设MTU=520]

同样，开始时sk->sk_write_queue()为空，初始的设置与上述例子完全相同，不同处在于datalen此时比最大分片还要大，因此要设置datalen=maxfraglen-fragheaderlen。

if (datalen > mtu - fragheaderlen)datalen = maxfraglen - fragheaderlen;

在完全第一个分片后，同样会将分片skb放入sk_write_queue队列，并进入下一次while循环。此时各参数的值：datalen=496, fraglen=516, alloclen=516, skb->len=516,

copy=488, ffset=488, length=600-496=104, 更新transhdrlen=0。 __skb_queue_tail(&sk->sk_write_queue, skb); continue;

再次进入while循环，此时不同的是length=104，证明还有数据需要拷贝，此时会对待拷贝的数据进行判断，下面所指的填充满是针对maxfraglen而言的。

@copy > 0，表示上个报文未被填充满，这种情况在多次调用 ip_append_data()时会发生，这里都是一次调用ip_append_data()的情况，所以不会出现，此时会填充数据到上个skb中

@copy = 0，表示上个报文被填充满，这个例子现在就是这种情况，此时会分配新的skb

@copy < 0，表示上个报文多填充了数据，这时因为maxfraglen是mtu8字节对齐后的值，所以maxfraglen范围是[mtu-7, mtu]，而在某些特殊情况下，比如上个报文已被填满(实际还可能有[1, 7]字节的空间)，待填充字节数n < 8，这时会把这n个节字补在最后一个报文的尾部。

对这个例子而言，上个skb刚好被填充满，copy=0，此时分配新的skb。

copy = mtu - skb->len; if (copy < length)copy = maxfraglen - skb->len;

分配新skb的流程与上个skb的分配过程相同，变化的只是偏移量offset，另外， icmp报头只存在于第一个分片中，因为它也属于IP内容的一部分，在这次拷贝完成后length=0，函数返回，最后结果如下：

ip_push_pending_frames() 将待发送的报文传递给网络层

待发送的报文分片都在sk->sk_write_queue上，这里要做的就是从sk_write_queue上取出所有分片，合并成一个报文，添加IP报头信息，使用ip_local_out()传递给网络层处理。

要注意的是这里的合并并不是真正的合并，只有第一个分片形成了skb，剩下的分片都放到了skb_shinfo(skb)- >frag_list上，虽然最后向下传递的只是一个skb，并实际上分片工作已经完成了，网络层并不需要再次分片，由网络的上层完成分片是出于效率的考虑，虽然与协议标准有所出入。

首先从sk_write_queue上取出第一个分片，skb是最终向下传递的报文，tail_skb指向skb的frag_list链表尾，即最后一个分片。

if ((skb = __skb_dequeue(&sk->sk_write_queue)) == NULL)goto out; tail_skb = &(skb_shinfo(skb)->frag_list);

将skb->data指向ip报头的位置

if (skb->data < skb_network_header(skb))__skb_pull(skb, skb_network_offset(skb));

tmp_skb表示现在要插入skb的分片，首先通过__skb_pull()除去这些分片的IP报头，因为分片共用skb的IP报头。然后通过tail_skb处理将tmp_skb链入frag_list中；最后增加报文长度计数，以前说明过，skb->len代表linear buffer + paged buffer，skb->data_len代表paged_buffer，这里插入的分片是增加了 paged buffer大小，所以对skb->len和skb->data_len都增加分片的长度。

while ((tmp_skb = __skb_dequeue(&sk->sk_write_queue)) != NULL) {__skb_pull(tmp_skb, skb_network_header_len(skb));*tail_skb = tmp_skb;tail_skb = &(tmp_skb->next);skb->len += tmp_skb->len;skb->data_len += tmp_skb->len;skb->truesize += tmp_skb->truesize;tmp_skb->destructor = NULL;tmp_skb->sk = NULL; }

这里是生成skb的IP报头，设置其中的值

iph = (struct iphdr *)skb->data; iph->version = 4; ……. skb->mark = sk->sk_mark;

最终通过ip_local_out()传递给IP层

err = ip_local_out(skb);

篇2：Linux内核分析网络[四]：路由表

路由表

在内核中存在路由表fib_table_hash和路由缓存表rt_hash_table，路由缓存表主要是为了加速路由的查找，每次路由查询都会先查找路由缓存，再查找路由表。这和cache是一个道理，缓存存储最近使用过的路由项，容量小，查找快速；路由表存储所有路由项，容量大，查找慢。

首先，应该先了解路由表的意义，下面是route命令查看到的路由表：

一条路由其实就是告知主机要到达一个目的地址，下一跳应该走哪里。比如发往192.168.22.3报文通过查路由表，会得到下一跳为192.168.123.254，再将其发送出去。在路由表项中，还有一个很重要的属性-scope，它代表了到目的网络的距离。

路由scope可取值： RT_SCOPE_UNIVERSE, RT_SCOPE_LINK, RT_SCOPE_HOST

在报文的转发过程中，显然是每次转发都要使到达目的网络的距离要越来越小或不变，否则根本到达不了目的网络。上面提到的scope很好的实现这个功能，在查找路由表中，表项的scope一定是更小或相等的scope(比如RT_SCOPE_LINK，则表项scope只能为RT_SCOPE_LINK或RT_SCOPE_HOST)。

路由缓存

路由缓存用于加速路由的查找，当收到报文或发送报文时，首先会查询路由缓存，在内核中被组织成hash表，就是rt_hash_table。

static struct rt_hash_bucket *rt_hash_table __read_mostly; [net/ipv4/route.c]

通过 ip_route_input()进行查询，首先是缓存操作时，通过[src_ip, dst_ip, iif,rt_genid]计算出hash值

hash = rt_hash (daddr, saddr, iif, rt_genid(net));

此时rt_hash_table[hash].chain就是要操作的缓存表项的链表，比如遍历该链表

for (rth = rt_hash_table[hash].chain; rth; rth = rth->u.dst.rt_next)

因此，在缓存中查找一个表项，首先计算出hash值，取出这组表项，然后遍历链表，找出指定的表项，这里需要完全匹配[src_ip, dst_ip, iif, tos, mark, net]，实际上struct rtable中有专门的属性用于缓存的查找键值– struct flowi。

/* Cache lookup keys */

struct flowi fl;

当找到表项后会更新表项的最后访问时间，并取出dst

dst_use (&rth->u.dst, jiffies);

skb_dst_set(skb, &rth->u.dst);

路由缓存的创建

inet_init () -> ip_init() -> ip_rt_init()

rt_hash_table = (struct rt_hash_bucket *)

alloc_large_system_hash(“IP route cache”,

sizeof(struct rt_hash_bucket),

rhash_entries,

(totalram_pages >= 128 * 1024) ?

15 : 17,

&rt_hash_log,

&rt_hash_mask,

rhash_entries ? 0 : 512 * 1024);

其中 rt_hash_mask表示表的大小，rt_hash_log = log(rt_hash_mask)，创建后的结构如图所示：

路由缓存插入条目

函数rt_intern_hash()

要插入的条目是rt，相应散列值是hash，首先通过hash值找到对应的bucket

rthp = &rt_hash_table[hash].chain;

然后对bucket进行一遍查询，这次查询的目的有两个：如果是超时的条目，则直接删除；如果是与rt相同键值的条目，则删除并将rt插入头部返回。

while ((rth = *rthp) != NULL) {

if (rt_is_expired(rth)) { // 超时的条目

*rthp = rth->u.dst.rt_next;

rt_free (rth);

continue;

}

if (compare_keys(&rth->fl, &rt->fl) && compare_netns (rth, rt)) { //重复的条目

*rthp = rth->u.dst.rt_next;

rcu_assign_pointer(rth->u.dst.rt_next, rt_hash_table[hash].chain);

rcu_assign_pointer(rt_hash_table[hash].chain, rth);

……

}

……

rthp = &rth->u.dst.rt_next;

}

在扫描一遍后，如rt还未存在，则将其插入头部

rt ->u.dst.rt_next = rt_hash_table[hash].chain;

rcu_assign_pointer(rt_hash_table[hash].chain, rt);

如果新插入rt满足一定条件，还要与ARP邻居表进行绑定

Hint：缓存的每个bucket是没有头结点的，单向链表，它所使用的插入和删除操作是值得学习的，简单实用。

路由缓存删除条目

rt_del()

要删除的条目是rt，相应散列值是hash，首先通过hash值找到对应的bucket，然后遍历，如果条目超时，或找到rt，则删除它。

rthp = &rt_hash_table[hash].chain;

spin_lock_bh(rt_hash_lock_addr(hash));

ip_rt_put(rt);

while ((aux = *rthp) != NULL) {

if (aux == rt || rt_is_expired(aux)) {

*rthp = aux- >u.dst.rt_next;

rt_free(aux);

continue;

}

rthp = &aux->u.dst.rt_next;

}

spin_unlock_bh(rt_hash_lock_addr(hash));

路由表的创建

inet_init() -> ip_init() -> ip_fib_init() -> fib_net_init() -> ip_fib_net_init()[net/ipv4/fib_frontend.c]

首先为路由表分配空间，这里的每个表项hlist_head实际都会链接一个单独的路由表，FIB_TABLE_HASHSZ表示了分配多少个路由表，一般情况下至少有两个– LOCAL和MAIN。注意这里仅仅是表头的空间分配，还没有真正分配路由表空间。

net->ipv4.fib_table_hash = kzalloc(

sizeof(struct hlist_head)*FIB_TABLE_HASHSZ, GFP_KERNEL);

ip_fib_net_init() -> fib4_rules_init()，这里真正分配了路由表空间

local_table = fib_hash_table(RT_TABLE_LOCAL);

main_table = fib_hash_table(RT_TABLE_MAIN);

然后将local和main表链入之前的fib_table_hash中

hlist_add_head_rcu (&local_table->tb_hlist,

&net->ipv4.fib_table_hash [TABLE_LOCAL_INDEX]);

hlist_add_head_rcu(&main_table->tb_hlist,

&net- >ipv4.fib_table_hash[TABLE_MAIN_INDEX]);

最终生成结构如图，LOCAL表位于fib_table_hash[0]，MAIN表位于 fib_table_hash[1]；两张表通过结构tb_hlist链入链表，而tb_id则标识了功能，255是LOCAL表，254是MAIN表。

关于这里的struct fn_hash，它表示了不同子网掩码长度的hash表[即fn_zone]，对于ipv4，从0~32共33个。而fn_hash的实现则是 fib_table的最后一个参数unsigned char tb_data[0]。

注意到这里fn_zone 还只是空指针，我们还只完成了路由表初始化的一部分。在启动阶段还会调用inet_rtm_newroute() -> fib_table_insert() -> fn_new_zone() [fib_hash.c]来创建fn_zone结构，前面已经讲过，fn_zone一共有33个，其中掩码长度为0[/0]表示为默认路由，fn_zone可以理解为相同掩码的地址集合。

首先为fn_zone分配空间

struct fn_zone *fz = kzalloc (sizeof(struct fn_zone), GFP_KERNEL);

传入参数z代表掩码长度， z = 0的掩码用于默认路由，一般只有一个，所以 fz_centerisor只需设为1；其它设为16；这里要提到fz_centerisor的作用，fz->fz_hash并不是个单链表，而是一个哈希表，而哈希表的大小就是fz_centerisor。

if (z) {

fz->fz_centerisor = 16;

} else {

fz->fz_centerisor = 1;

}

fz_hashmask实际是用于求余数的，当算出hash值，再hash & fz_hashmask就得出了在哈希表的位置；而 fz_hash就是下一层的哈希表了，前面已经提过路由表被多组分层了，这里fz_hash就是根据fz_centerisor大小来创建的；fz_order 就是子网掩码长度；fz_mask就是子网掩码。

fz->fz_hashmask = (fz->fz_centerisor - 1);

fz->fz_hash = fz_hash_alloc(fz->fz_centerisor);

fz->fz_order = z;

fz->fz_mask = inet_make_mask(z);

从子网长度大于新添加fz的fn_zone中挑选一个不为空的fn_zones[i]，将新创建的fz设成fn_zones[i].next；然后将fz根据掩码长度添加到fn_zones[]中相应位置；fn_zone_list始终指向掩码长度最长的fn_zone。

for (i=z+1; i<=32; i++)

if (table->fn_zones[i])

break;

if (i>32) {

fz->fz_next = table- >fn_zone_list;

table->fn_zone_list = fz;

} else {

fz->fz_next = table->fn_zones [i]->fz_next;

table->fn_zones[i]->fz_next = fz;

}

table->fn_zones[z] = fz;

这里的fn_hash是数组与链表的结合体，看下fn_hash定义

struct fn_hash {

struct fn_zone *fn_zones [33];

struct fn_zone *fn_zone_list;

};

fn_hash包含33数组元素，每个元素存放一定掩码长度的 fn_zone，其中fn_zone[i]存储掩码长度为i，

而fn_zone通过内部属性fz_next又彼此串连起来，形成单向链表，其中 fn_zone_list可以看作链表头，而这里链表的组织顺序是倒序的，即从掩码长到短。

到这里，fz_hash所分配的哈希表还没有插入内容，这部分为fib_insert_node()完成。

inet_rtm_newroute() -> fib_table_insert() -> fib_insert_node() [net/ipv4/fib_hash.c]

这里f是fib_node，可以理解为具有相同网络地址的路由项集合。根据fn_key(网络地址)和fz(掩码长度)来计算hash值，决定将f插入fz_hash的哪个项。

struct hlist_head *head = &fz->fz_hash[fn_hash(f->fn_key, fz)];

hlist_add_head(&f->fn_hash, head);

}

如何fib_node还不存在，则会创建它，这里的kmem_cache_zalloc()其实就是内存分配

new_f = kmem_cache_zalloc (fn_hash_kmem, GFP_KERNEL);

if (new_f == NULL)

goto out;

INIT_HLIST_NODE(&new_f- >fn_hash);

INIT_LIST_HEAD(&new_f->fn_alias);

new_f->fn_key = key;

f = new_f;

路由表最后一层是fib_info，具体的路由信息都存储在此，它由 fib_create_info()创建。

首先为fib_info分配空间，由于fib_info的最后一个属性是struct fib_nh fib_nh[0]，因此大小是fib_info + nhs * fib_nh，这里的fib_nh代表了下一跳(next hop)的信息，nhs代表了下一跳的数目，一般情况下nhs=1 ，除非配置了支持多路径。

fi = kzalloc(sizeof(*fi)+nhs*sizeof(struct fib_nh), GFP_KERNEL);

设置fi的相关属性

fi->fib_net = hold_net(net);

fi->fib_protocol = cfg->fc_protocol;

fi- >fib_flags = cfg->fc_flags;

fi->fib_priority = cfg->fc_priority;

fi->fib_prefsrc = cfg->fc_prefsrc;

fi->fib_nhs = nhs;

使fi后面所有的nh->nh_parent指向fi，设置后如图所示

change_nexthops(fi) {

nexthop_nh->nh_parent = fi;

} endfor_nexthops(fi)

设置fib_nh的属性，这里仅展示了单一路径的情况：

struct fib_nh *nh = fi->fib_nh;

nh->nh_oif = cfg- >fc_oif;

nh->nh_gw = cfg->fc_gw;

nh->nh_flags = cfg->fc_flags;

然后，再根据cfg ->fc_scope值来设置nh的其余属性。如果scope是RT_SCOPE_HOST，则设置下一跳scope为RT_SCOPE_NOWHERE

if (cfg- >fc_scope == RT_SCOPE_HOST) {

struct fib_nh *nh = fi->fib_nh;

nh->nh_scope = RT_SCOPE_NOWHERE;

nh->nh_dev = dev_get_by_index(net, fi->fib_nh->nh_oif);

}

如果scope 是RT_SCOPE_LINK或RT_SCOPE_UNIVERSE，则设置下跳

change_nexthops(fi) {

if ((err = fib_check_nh(cfg, fi, nexthop_nh)) != 0)

goto failure;

} endfor_nexthops(fi)

最后，将fi链入链表中，这里要注意的是所有的fib_info(只要创建了的)都会加入fib_info_hash中，如果路由项使用了优先地址属性，还会加入fib_info_laddrhash 中。

hlist_add_head(&fi->fib_hash,

&fib_info_hash[fib_info_hashfn(fi)]);

if (fi- >fib_prefsrc) {

struct hlist_head *head;

head = &fib_info_laddrhash[fib_laddr_hashfn(fi- >fib_prefsrc)];

hlist_add_head(&fi->fib_lhash, head);

}

无论fib_info在路由表中位于哪个掩码、哪个网段结构下，都与fib_info_hash和fib_info_laddrhash无关，这两个哈希表与路由表独立，主要是用于加速路由信息fib_info的查找。哈希表的大小为fib_hash_size，当超过这个限制时，fib_hash_size * 2(如果哈希函数够好，每个 bucket都有一个fib_info)。fib_info在哈希表的图示如下：

由于路由表信息也可能要以设备dev为键值搜索，因此还存在fib_info_devhash哈希表，用于存储nh的设置dev->ifindex 。

change_nexthops(fi) {

hash = fib_devindex_hashfn(nexthop_nh->nh_dev->ifindex);

head = &fib_info_devhash[hash];

hlist_add_head(&nexthop_nh->nh_hash, head);

} endfor_nexthops (fi)

上面讲过了路由表各个部分的创建，现在来看下它们是如何一起工作的，在fib_table_insert() [net/ipv4/fib_hash.c]完成整个的路由表创建过程。下面来看下fib_table_insert()函数：

从fn_zones中取出掩码长度为fc_dst_len的项，如果该项不存在，则创建它[fn_zone的创建前面已经讲过]。

fz = table->fn_zones[cfg- >fc_dst_len];

if (!fz && !(fz = fn_new_zone(table, cfg->fc_dst_len)))

return - ENOBUFS;

然后创建fib_info结构，[前面已经讲过]

fi = fib_create_info(cfg);

然后在掩码长度相同项里查找指定网络地址key(如145.222.33.0/24)，查找的结果如图所示

f = fib_find_node(fz, key);

如果不存在该网络地址项，则创建相应的fib_node，并加入到链表fz_hash中

if (!f) {

new_f = kmem_cache_zalloc(fn_hash_kmem, GFP_KERNEL);

if (new_f == NULL)

goto out;

INIT_HLIST_NODE(&new_f- >fn_hash);

INIT_LIST_HEAD(&new_f->fn_alias);

new_f->fn_key = key;

f = new_f;

}

……

fib_insert_node(fz, new_f);

如果存在该网络地址项，则在fib_node的属性 fn_alias中以tos和fi->fib_priority作为键值查找。一个fib_node可以有多个fib_alias相对应，这些fib_alias以链表形式存在，并按tos并从大到小的顺序排列。因此，fib_find_alias查找到的是第一个fib_alias->tos不大于tos的fib_alias项。

fa = fib_find_alias(&f->fn_alias, tos, fi->fib_priority);

如果查找到的fa与与要插入的路由项完全相同，则按照设置的标置位进行操作，NLM_F_REPLACE则替换掉旧的，NLM_F_APPEND添加在后面。

设置要插入的 fib_alias的属性，包括最重要的fib_alias->fa_info设置为fi

new_fa->fa_info = fi;

new_fa- >fa_tos = tos;

new_fa->fa_type = cfg->fc_type;

new_fa->fa_scope = cfg- >fc_scope;

new_fa->fa_state = 0;

如果没有要插入路由的网络地址项fib_node，则之前已经创建了新的，现在将它插入到路由表中fib_insert_node()；然后将new_fa链入到fib_node->fn_alias中

if (new_f)

fib_insert_node(fz, new_f);

list_add_tail(&new_fa->fa_list,

(fa ? &fa->fa_list : &f->fn_alias));

最后，由于新插入的路由表项，会发出通告，告知所以加入RTNLGRP_IPV4_ROUTE组的成员，这个功能可以在linux中使用”ip route monitor”来测试。最终的路由表如图所示：

rtmsg_fib(RTM_NEWROUTE, key, new_fa, cfg->fc_dst_len, tb->tb_id, &cfg->fc_nlinfo, 0);

至此，就完成了路由表项的插入，加上之前的路由表的初始化，整个路由表的创建过程就讲解完了，小小总结一下：

路由表的查找效率是第一位的，因此内核在实现时使用了多级索引来进行加速

第一级：fn_zone 按不同掩码长度分类(如/5和/24)

第二级：fib_node 按不同网络地址分类(如124.44.33.0/24)

第三级：fib_info 下一跳路由信息

篇3：Linux内核分析网络[十二]：UDP模块收发

内核版本：2.6.34

UDP报文接收

UDP报文的接收可以分为两个部分：协议栈收到udp报文，插入相应队列中；用户调用recvfrom或recv()系统调用从队列中取出报文，这里的队列就是sk->sk_receive_queue，它是报文中转的纽带，两部分的联系如下图所示，

第一部分：协议栈如何收取udp报文的。

udp模块的注册在inet_init()中，当收到的是udp报文，会调用udp_protocol中的handler函数udp_rcv()。

if (inet_add_protocol(&udp_protocol, IPPROTO_UDP) < 0)printk(KERN_CRIT “inet_init: Cannot add UDP protocoln”);

udp_rcv() -> __udp4_lib_rcv() 完成udp报文接收，初始化udp的校验和，并不验证校验和的正确性。

if (udp4_csum_init(skb, uh, proto))goto csum_error;

在udptable中以套接字的[saddr, sport, daddr, dport]查找相应的sk，在上一篇中已详细讲过” sk的查找”，这里报文的source源端口相当于源主机的端口，dest目的端口相当于本地端口。

sk = __udp4_lib_lookup_skb(skb, uh->source, uh->dest, udptable);

如果udptable中存在相应的sk，即有 socket在接收，则通过udp_queue_rcv_skb()将报文skb入队列，该函数稍后分析，总之，报文会被放到sk- >sk_receive_queue队列上，然后sock_put()减少sk的引用计算，并返回。之后的接收工作的完成将有赖于用户的操作。

if (sk != NULL) {int ret = udp_queue_rcv_skb(sk, skb);sock_put(sk); if (ret > 0) return -ret;return 0; }

当没有在udptable中找到sk时，则本机没有socket会接收它，因此要发送icmp不可达报文，在此之前，还要验证校验和udp_lib_checksum_complete()，如果校验和错误，则直接丢弃报文；如果校验和正确，则会增加mib中的统计，并发送icmp端口不可达报文，然后丢弃该报文。

if (udp_lib_checksum_complete(skb))goto csum_error; UDP_INC_STATS_BH(net, UDP_MIB_NOPORTS, proto == IPPROTO_UDPLITE); icmp_send(skb, ICMP_DEST_UNREACH, ICMP_PORT_UNREACH, 0); kfree_skb(skb);

udp_queue_rcv_skb() 报文入队列

sock_woned_by_user()判断sk- >sk_lock.owned的值，如果等于1，表示sk处于占用状态，此时不能向sk接收队列中添加skb，执行else if部分， sk_add_backlog()将skb添加到sk->sk_backlog队列上；如果等于0，表示sk没被占用，执行if部分，__udp_queue_rcv_skb() 将skb添加到sk->sk_receive_queue队列上。

bh_lock_sock(sk); if (!sock_owned_by_user(sk))rc = __udp_queue_rcv_skb(sk, skb); else if (sk_add_backlog(sk, skb)) {bh_unlock_sock(sk);goto drop; } bh_unlock_sock(sk);

那么何时sk会被占用？何时sk->sk_backlog上的skb被处理的？

创建socket时， sys_socket() -> inet_create() -> sk_alloc() -> sock_lock_init() -> sock_lock_init_class_and_name()初始化sk->sk_lock_owned=0。

比如当销毁socket时，udp_destroy_sock()会调用lock_sock()对sk加锁，操作完后，调用 release_sock()对sk解锁。

void udp_destroy_sock(struct sock *sk) {lock_sock(sk);udp_flush_pending_frames(sk); release_sock(sk); }

实际上，lock_sock()设置sk->sk_lock.owned=1；而release_sock()设置sk->sk_lock.owned=0，并处理sk_backlog队列上的报文，release_sock() -> __release_sock()，对于sk_backlog队列上的每个报文，调用sk_backlog_rcv() -> sk->sk_backlog_rcv()。同样是在socket的创建中，sk->sk_backlog_rcv = sk->sk_prot->backlog_rcv()即 __udp_queue_rcv_skb()，这个函数的作用上面已经讲过，将skb添加到sk_receive_queue，这样，所有的sk_backlog上的报文转移到了sk_receive_queue上。简单来说，sk_backlog队列的作用就是，锁定时报文临时存放在此，解锁时，报文移到 sk_receive_queue队列。

第二部分：用户如何收取报文

用户可以调用sys_recvfrom()或sys_recv()来接收报文，所不同的是，sys_recvfrom()可能通过参数获得报文的来源地址，而sys_recv()则不可以，但对接收报文并没有影响。在用户调用 recvfrom()或recv()接收报文前，发给该socket的报文都会被添加到sk->sk_receive_queue上，recvfrom()和recv()要做的就是从sk_receive_queue上取出报文，拷贝到用户空间，供用户使用。

sys_recv() -> sys_recvfrom()

sys_recvfrom () -> sk->ops->recvmsg()

==> sock_common_recvmsg() -> sk->sk_prot->recvmsg()

==> udp_recvmsg()

sys_recvfrom()

调用sock_recvmsg()接收udp报文，存放在msg中，如果接收到报文，从内核到用户空间拷贝报文的源地址到addr中，addr是recvfrom()调用的传入参数，表示报文源的地址。而报文的内容是在udp_recvmsg()中从内核拷贝到用户空间的。

err = sock_recvmsg(sock, &msg, size, flags); if (err >= 0 && addr != NULL) {err2 = move_addr_to_user((struct sockaddr *)&address, msg.msg_namelen, addr, addr_len);if (err2 < 0) err = err2; }

udp_recvmsg() 接收udp报文

这个函数有三个关键操作：

1. 取到数据包 -- __skb_recv_datagram()

2. 拷贝数据 -- skb_copy_datagram_iovec()或skb_copy_and csum_datagram_iovec()

3. 必要时计算校验和 – skb_copy_and_csum_datagram_iovec()

__skb_recv_datagram()，它会从sk->sk_receive_queue上取出一个skb，前面已经分析到，内核收到发往该socket 的报文会放在sk->sk_receive_queue。

skb = __skb_recv_datagram(sk, flags | (noblock ? MSG_DONTWAIT : 0), &peeked, &err);

如果没有报文，有两种情况：使用了非阻塞接收，且用户接收时还没有报文到来；使用阻塞接收，但之前没有报文，且在sk->sk_rcvtimeo时间内都没有报文到来。没有报文，返回错误值。

if (!skb)goto out;

len是recvfrom()传入buf的大小，ulen是报文内容的长度，如果ulen > len，那么只需要使用buf的 ulen长度就可以了；如果len < ulen，那么buf不够报文填充，只能对报文截断，取前len个字节。

ulen = skb->len - sizeof(struct udphdr); if (len > ulen)len = ulen; else if (len < ulen)msg->msg_flags |= MSG_TRUNC;

如果报文被截断或使用UDP-Lite，那么需要提前验证校验和， udp_lib_checksum_complete()完成校验和计算，函数在下面具体分析。

if (len < ulen || UDP_SKB_CB(skb)->partial_cov) {if (udp_lib_checksum_complete(skb)) goto csum_copy_err; }

如果报文不用验证校验和，那么执行if部分，调用skb_copy_datagram_iovec()直接拷贝报文到buf中就可以了；如果报文需要验证校验和，那么执行else部分，调用skb_copy_and_csum_datagram_iovec()拷贝报文到buf，并在拷贝过程中计算校验和。这也是为什么在内核收到udp报文时为什么先验证校验和再处理的原因，udp报文可能很大，校验和的计算可能很耗时，将其放在拷贝过程中可以节约开销，当然它的代价是一些校验和错误的报文也会被添加到socket的接收队列上，直到用户真正接收时它们才会被丢弃。

if (skb_csum_unnecessary(skb))err = skb_copy_datagram_iovec(skb, sizeof(struct udphdr), msg->msg_iov, len); else {err = skb_copy_and_csum_datagram_iovec(skb, sizeof(struct udphdr), msg->msg_iov);if (err == -EINVAL) goto csum_copy_err; }

拷贝地址到msg->msg_name中，在sys_recvfrom()中msg->msg_name=&address，然后address会从内核拷贝给用户空间的addr。

if (sin) {sin->sin_family = AF_INET;sin->sin_port = udp_hdr(skb)->source;sin->sin_addr.s_addr = ip_hdr(skb)->saddr;memset(sin->sin_zero, 0, sizeof(sin->sin_zero)); }

下面来重点看核心操作的三个函数：

__skb_recv_datagram() 从sk_receive_queue上取一个skb

核心代码段如下，skb_peek()从sk->sk_receive_queue中取出一个skb，如果有的话，则返回skb，作为用户此次接收的报文，当然还有对skb的后续处理，但该函数只是取出一个skb；如果还没有的话，则使用wait_for_packet()等待报文到来，其中参数timeo 代表等待的时间，如果使用非阻塞接收的话，timeo会设置为0(即当前没有skb的话则直接返回，不进行等待)，否则设置为sk- >sk_rcvtimeo。

do {……skb = skb_peek(&sk->sk_receive_queue);if (skb) { *peeked = skb->peeked; if (flags & MSG_PEEK) { skb->peeked = 1; atomic_inc(&skb->users); } else __skb_unlink(skb, &sk->sk_receive_queue);}if (skb) return skb; …… } while (!wait_for_packet(sk, err, &timeo));

skb_copy_datagram_iovec() 拷贝skb内容到msg中

拷贝可以分三部分：线性地址空间的拷贝，聚合/发散地址空间的拷贝，非线性地址空间的拷贝。第二部分需要硬件的支持，这里讨论另两部分。

在skb的buff中的是线性地址空间，在skb的frag_list上的是非线性地址空间；当没有分片发生的，用线性地址空间就足够了，但是当报文过长而分片时，第一个分片会使用线性地址空间，其余的分片将被链到skb的frag_list上，即非线性地址空间，具体可以参考”ipv4模块”中分片部分。

拷贝报文内容时，就要将线性和非线性空间的内容都拷贝过去。下面是拷贝线性地址空间的代码段，start是报文的线性部分长度(skb->len-skb->datalen)，copy是线性地址空间的大小， offset是相对skb的偏移(即此次拷贝从哪里开始)，以udp报文为例，这几个值如下图所示。memcpy_toiovec()拷贝内核到to中，要注意的是它改变了to的成员变量。

int start = skb_headlen(skb); int i, copy = start - offset; if (copy > 0) {if (copy > len) copy = len;if (memcpy_toiovec(to, skb->data + offset, copy)) goto fault;if ((len -= copy) == 0) return 0;offset += copy; }

下面是拷贝非线性地址空间的代码段，遍历skb的frag_list链表，对上面的每个分片，拷贝内容到to中，这里start, end的值不重要，重要的是它们的差值end-start，表示了当前分片frag_iter的长度，使用skb_copy_datagram_iovec()拷贝当前分片内容，即把每个分片都作为单独报文来处理。不过对于分片，感觉只有拷贝的第一部分和第二部分，在IP层分片重组时，并没有将分片链在分片的frag_list上的情况，而都链在头分片的frag_list上。

skb_walk_frags(skb, frag_iter) {int end;end = start + frag_iter->len;if ((copy = end - offset) > 0) { if (copy > len) copy = len; if (skb_copy_datagram_iovec(frag_iter, offset - start, to, copy)) goto fault; if ((len -= copy) == 0) return 0; offset += copy;}start = end; }

还是以一个例子来说明，主机收到一个udp报文，内容长度为4000 bytes，MTU是1500，传入buff数组大小也为4000，

根据MTU，报文会会被分成三片，分片IP报内容大小依次是1480, 1480, 1040。每个分片都有一个20节字的IP报文，第一个分片还有一个8节字的udp报头。接收时数据拷贝情况如下：

分片一是第一个分片，包含UDP报文，在拷贝时要跳过，因为使用的是udp socket接收，只要报文内容就可以了。三张图片代表了三次调用 skb_copy_datagram_iovec()的情况，iov是存储内容的buff，最终结果是三个分片共4000字节拷贝到了iov中。

memcpy_toiovec()函数需要注意，不仅因为它改变了iovec的成员值，还因为最后的iov++。在udp socket的接收recvfrom() 中，msg.msg_iov = &iov，而iov定义成struct iovec iov，即传入参数iov实际只有一个的空间，那么在iov++后，iov将指向非法的地址。这里只考虑udp使用时的情况，memcpy_toiovec()调用的前一句是，这里len是接收buff的长度：

if (copy > len)copy = len;

而memcpy_toiovec()中又有int copy = min_t(unsigned int, iov->iov_len, len)，这里len是上面传入的copy，iov_len是接收buff长度，这两句保证了函数中copy值与len相等，即完成一次拷贝后，len-=copy会使len==0，虽然iov++指向了非法内存，但由于while(len > 0)已退出，所以不会使用iov做任何事情。其次，函数中的iov++并不会对参数 iov产生影响，即函数完成iov还是传入的值。最后，拷贝完后会修改iov_len和iov_base的值，iov_len表示可用长度，iov_base 表示起始拷贝位置。

int memcpy_toiovec(struct iovec *iov, unsigned char *kdata, int len) {while (len > 0) { if (iov->iov_len) { int copy = min_t(unsigned int, iov->iov_len, len); if (copy_to_user(iov->iov_base, kdata, copy)) return -EFAULT; kdata += copy; len -= copy; iov->iov_len -= copy; iov->iov_base += copy; } iov++;}return 0; }

skb_copy_and_csum_datagram_iovec() 拷贝skb内容到msg中，同时计算校验和

这个函数提高了校验和计算效率，因为它合并了拷贝与计算操作，这样只要一次遍历操作就可以了。与skb_copy_datagram_iovec()相比，它在每次拷贝 skb内容时，计算下这次拷贝内容的校验和。

csum = csum_partial(skb->data, hlen, skb->csum); if (skb_copy_and_csum_datagram(skb, hlen, iov->iov_base, chunk, &csum))goto fault;

UDP报文发送

发送时有两种调用方式：sys_send()和sys_sendto()，两者的区别在于sys_sendto()需要给入目的地址的参数；而sys_send()调用前需要调用sys_connect()来绑定目的地址信息；两者的后续调用是相同的。如果调用sys_sendto()发送，地址信息在sys_sendto()中从用户空间拷贝到内核空间，而报文内容在udp_sendmsg()中从用户空间拷贝到内核空间。

sys_send() -> sys_sendto()

sys_sendto() -> sock_sendmsg() -> __sock_sendmsg() -> sock->ops->sendmsg()

==> inet_sendmsg() -> sk->sk_prot->sendmsg()

==> udp_sendmsg()

udp_sendmsg()的核心流程如下图所示，只列出了核心的函数调用了参数赋值，大致步骤是：获取信息 -> 获取路由项rt -> 添加数据 -> 发送数据。

udp_sock结构体中的 pending用于标识当前udp_sock上是否有待发送数据，如果有的话，则直接goto do_append_data继续添加数据；否则先要做些初始化工作，再才添加数据。实际上，pending!=0表示此调用前已经有数据在udp_sock中的，每次调和sendto()发送数据时， pending初始等于0；在添加数据时，设置up->pending = AF_INET。直到最后调用udp_push_pending_frames()将数据发送给 IP层或skb_queue_empty(&sk->sk_write_queue)发送链表上为空，这时设置up->pending = 0。因此，这里可以看到，报文发送时pending值的变化：

通常使用sendto()发送都是一次调用对应一个报文，即pending=0->AF_INET->0；但如果调用sendto()时参数用到了MSG_MORE标志，则pending=0->AF_INET，直到调用sendto()时未使用MSG_MORE标志，表示此次发送数据是最后一部分数据时，pending=AF_INET->0。

if (up->pending) { lock_sock(sk); if (likely(up->pending)) { if (unlikely(up->pending != AF_INET)) { release_sock(sk); return -EINVAL; } goto do_append_data; } release_sock(sk);}

如果pending=0没有待发送数据，执行初始化操作：报文长度、地址信息、路由项。

ulen初始为sendto()传入的数据长度，由于是第一部分数据(如果没有后续数据，则就是报文)，ulen要添加udp报头的8字节。

ulen += sizeof(struct udphdr);

这段代码获取要发送数据的目的地址和端口号。一种情况是调用sendto()发送数据，此时目的的信息以参数传入，存储在msg->msg_name中，因此从中取出daddr和dport；另一种情况是调用connect(), send()发送数据，在connect()调用时绑定了目的的信息，存储在inet中，并且由于是调用了connect()，sk->sk_state会设置为 TCP_ESTABLISHED。以后调用send()发送数据时，无需要再给入目的信息参数，因此从inet中取出dadr和dport。而connected表示了该socket是否已绑定目的。

if (msg->msg_name) {struct sockaddr_in * usin = (struct sockaddr_in *)msg->msg_name;if (msg->msg_namelen < sizeof(*usin)) return -EINVAL;if (usin->sin_family != AF_INET) { if (usin->sin_family != AF_UNSPEC) return -EAFNOSUPPORT;} daddr = usin->sin_addr.s_addr;dport = usin->sin_port;if (dport == 0) return -EINVAL; } else {if (sk->sk_state != TCP_ESTABLISHED) return -EDESTADDRREQ;daddr = inet->inet_daddr;dport = inet->inet_dport;connected = 1; }

下一步是获取路由项rt，如果已连接(调用过connect)，则路由信息在connect()时已获取，直接拿就可以了；如果未连接或拿到的路由项已被删除，则需要重新在路由表中查找，还是使用ip_route_output_flow()来查找，如果是连接状态的 socket，则要用新找到的rt来更新socket，当然，前提条件是之前的rt已过期。

if (rt == NULL) {……err = ip_route_output_flow(net, &rt, &fl, sk, 1);……if (connected) sk_dst_set(sk, dst_clone(&rt->u.dst)); }

存储信息daddr, dport, saddr, sport到cork.fl中，它们会在生成udp报头和计算udp校验和时用到。up- >pending=AF_INET标识了数据添加的开始，下面将开始数据的添加工作。

inet->cork.fl.fl4_dst = daddr; inet->cork.fl.fl_ip_dport = dport; inet->cork.fl.fl4_src = saddr; inet->cork.fl.fl_ip_sport = inet->inet_sport; up->pending = AF_INET;

如果pending!=0或执行完初始化操作，则直接执行添加数据操作：

up->len表示要发送数据的总长度，包括udp报头，因此每发送一部分数据就要累加它的长度，在发送后up->len被清0。然后调用ip_append_data()添加数据到sk->sk_write_queue，它会处理数据分片等问题，在 ”ICMP模块” 中有详细分析过。

up->len += ulen; getfrag = is_udplite ? udplite_getfrag : ip_generic_getfrag; err = ip_append_data(sk, getfrag, msg->msg_iov, ulen, sizeof(struct udphdr), &ipc, &rt, corkreq ? msg->msg_flags|MSG_MORE : msg->msg_flags);

ip_append_data()添加数据正确会返回0，否则 udp_flush_pending_frames()丢弃将添加的数据；如果添加数据正确，且没有后续的数据到来(由MSG_MORE来标识)，则 udp_push_pending_frames()将数据发送给IP层，下面将详细分析这个函数。最后一种情况是当sk_write_queue上为空时，它触发的条件必须是发送多个报文且sk_write_queue上为空，而实际上在ip_append_data过后sk_write_queue不会为空的，因此正常情况下并不会发生。哪种情况会发生呢？重置pending值为0就是在这里完成的，三个条件语句都会将pending设置为0。

if (err)udp_flush_pending_frames(sk); else if (!corkreq)err = udp_push_pending_frames(sk); else if (unlikely(skb_queue_empty(&sk->sk_write_queue)))up->pending = 0;

数据已经处理完成，释放取到的路由项rt，如果有IP选项，也释放它。如果发送数据成功，返回发送的长度len；否则根据错误值err进行错误处理并返回err。

ip_rt_put(rt); if (free)kfree(ipc.opt); if (!err)return len; if (err == -ENOBUFS || test_bit(SOCK_NOSPACE, &sk->sk_socket->flags)) {UDP_INC_STATS_USER(sock_net(sk), UDP_MIB_SNDBUFERRORS, is_udplite); } return err;

在 “ICMP模块” 中往IP层发送数据使用的是ip_push_pending_frames()。而在UDP模块中往IP层发送数据使用的是ip_push_pending_frames()。而在UDP模块中往IP层发送数据的udp_push_pending_frames()只是对 ip_push_pending_frames()的封装，主要是增加对UDP的报头的处理。同理，udp_flush_pending_frames()也是，只是它更简单，仅仅重置了up->len和up->pending的值，重置后可以开始一个新报文。那么udp_push_pending_frames()封装了哪些处理呢。

udp_push_pending_frames() 发送数据给IP层

设置udp报头，包括源端口source，目的端口dest，报文长度len 。

uh = udp_hdr(skb); uh->source = fl->fl_ip_sport; uh->dest = fl->fl_ip_dport; uh->len = htons(up->len); uh->check = 0;

计算udp报头中的校验和，包括了伪报头、udp报头和报文内容。

if (is_udplite)csum = udplite_csum_outgoing(sk, skb); else if (sk->sk_no_check == UDP_CSUM_NOXMIT) { /* UDP csum disabled */ skb->ip_summed = CHECKSUM_NONE;goto send; } else if (skb->ip_summed == CHECKSUM_PARTIAL) { /* UDP hardware csum */ udp4_hwcsum_outgoing(sk, skb, fl->fl4_src, fl->fl4_dst, up->len);goto send; } else /* `normal' UDP */ csum = udp_csum_outgoing(sk, skb); uh->check = csum_tcpudp_magic(fl->fl4_src, fl->fl4_dst, up->len, sk->sk_protocol, csum);

将报文发送给IP层，这个函数已经分析过了。

err = ip_push_pending_frames(sk);

同样，在发送完报文后，重置len和pending的值，以便开始下一个报文发送。

up->len = 0; up->pending = 0;

篇4：Linux内核分析网络[九]：邻居表

内核版本：2.6.34

这部分的重点是三个核心的数据结构-邻居表、邻居缓存、代理邻居表，以及NUD状态转移图，

总的来说，要成功添加一条邻居表项，需要满足两个条件：1. 本机使用该表项；2. 对方主机进行了确认。同时，表项的添加引入了NUD(Neighbour Unreachability Detection)机制，从创建NUD_NONE到可用NUD_REACHABLE需要经历一系列状态转移，而根据达到两个条件顺序的不同，可以分为两条路线：

先引用再确认- NUD_NONE -> NUD_INCOMPLETE -> NUD_REACHABLE

先确认再引用- NUD_NONE -> NUD_STALE -> NUD_DELAY -> NUD_PROBE -> NUD_REACHABLE

下面还是从接收函数入手，当匹配号协议号是0x0806，会调用ARP模块的接收函数arp_rcv()。

arp_rcv() ARP接收函数

首先是对arp协议头进行检查，比如大小是否足够，头部各数值是否正确等，这里略过代码，直接向下看。每个协议处理都一样，如果被多个协议占有，则拷贝一份。

if ((skb = skb_share_check(skb, GFP_ATOMIC)) == NULL)goto out_of_mem;

NEIGH_CB(skb)实际就是skb->cb，在skb声明为u8 char[48]，它用作每个协议模块的私有数据区(control buffer)，每个协议模块可以根据自身需求在其中存储私有数据。而arp模块就利用了它存储控制结构neighbour_cb ，它声明如下，占8字节。这个控制结构在代理ARP中使用工作队列时会发挥作用，sched_next代表下次被调度的时间，flags是标志。

memset(NEIGH_CB(skb), 0, sizeof(struct neighbour_cb)); struct neighbour_cb {unsigned long sched_next;unsigned int flags; };

函数最后调用arp_process，其间插入netfilter(关于netfilter，参见前篇：hi.csdn.net/link.php? url=blog.csdn.net%2Fqy532846454)，作为开始处理ARP报文的起点。

return NF_HOOK(NFPROTO_ARP, NF_ARP_IN, skb, dev, NULL, arp_process);

arp_process()

这个函数开始对报文进行处理，首先会从skb中取出arp报头部分的信息，如sha, sip, tha, tip等，这部分可查阅代码，这里略过。ARP不会查询环路地址和组播地址，因为它们没有对应的mac地址，因此遇到这两类地址，直接退出。

if (ipv4_is_loopback(tip) || ipv4_is_multicast(tip))goto out;

如果收到的是重复地址检测报文，并且本机占用了检测了地址，则调用arp_send发送响应。对于重复地址检测报文(ARP报文中源IP为全0)，它所带有的邻居表项信息还没通过检测，此时缓存它显然没有意义，也许下一刻就有其它主机声明它非法，因此，重复地址检测报文中的信息不会加入邻居表中。

if (sip == 0) {if (arp->ar_op == htons(ARPOP_REQUEST) && inet_addr_type(net, tip) == RTN_LOCAL && !arp_ignore(in_dev, sip, tip)) arp_send(ARPOP_REPLY, ETH_P_ARP, sip, dev, tip, sha, dev->dev_addr, sha);goto out; }

下面要处理的地址解析报文，并且要解析的地址在路由表中存在

if (arp->ar_op == htons(ARPOP_REQUEST) &&ip_route_input(skb, tip, sip, 0, dev) == 0)

第一种情况，如果要解析的是本机地址，则调用neigh_event_ns() ，并根据查到的邻居表项n发送ARP响应报文。这里neigh_event_ns的功能是在arp_tbl中查找是否已含有对方主机的地址信息，如果没有，则进行创建，然后会调用neigh_update来更新状态。收到对方主机的请求报文，会导致状态迁移到NUD_STALE。

if (addr_type == RTN_LOCAL) {……if (!dont_send) { n = neigh_event_ns(&arp_tbl, sha, &sip, dev); if (n) { arp_send(ARPOP_REPLY,ETH_P_ARP,sip,dev,tip,sha,dev->dev_addr,sha); neigh_release(n); }}goto out; }

#NUD_INCOMPLETE也迁移到NUD_STALE，作何解释？

第二种情况，如果要解析的不是本机地址，则要判断是否支持转发，是否支持代理ARP(代理ARP是陆由器的功能，因此能转发是先决条件)，如果满足条件，那么按照代理ARP流程处理。首先无论如何，主机得通了存在这样一个邻居，因此要在在arp_tbl中查找并(如果不存在)创建相应邻居表项；然后，对于代理ARP，这个流程实际上会执行两遍，第一遍走else部分，第二遍走if部分。第一次的else代码段会触发定时器，通过定时器引发报文重新执行arp_process函数，并走if部分。

-第一遍的else部分：调用pneigh_enqueue()将报文skb加入tbl->proxy_queue队列，同时设置NEIGH_CB(skb)的值，具体可看后见的代理表项处理。

-第二遍的if部分，发送ARP响应报文，行使代理ARP的功能。

else if (IN_DEV_FORWARD(in_dev)) {if (addr_type == RTN_UNICAST && (arp_fwd_proxy(in_dev, dev, rt) || arp_fwd_pvlan(in_dev, dev, rt, sip, tip) || pneigh_lookup(&arp_tbl, net, &tip, dev, 0))){ n = neigh_event_ns(&arp_tbl, sha, &sip, dev); if (n) neigh_release(n); if (NEIGH_CB(skb)->flags & LOCALLY_ENQUEUED || skb->pkt_type == PACKET_HOST || in_dev->arp_parms->proxy_delay == 0) { arp_send(ARPOP_REPLY,ETH_P_ARP,sip,dev,tip,sha,dev->dev_addr,sha); } else { pneigh_enqueue(&arp_tbl, in_dev->arp_parms, skb); in_dev_put(in_dev); return 0; } goto out;} }

补充：neigh_event_ns()与neigh_release()配套使用并不代表创建后又被释放，neigh被释放的条件是neigh- >refcnt==0，但neigh创建时的refcnt=1，而neigh_event_ns会使refcnt+1，neigh_release会使-1，此时refcnt的值还是1，只有当下次单独调用neigh_release时才会被释放。

查找是否已存在这样一个邻居表项。如果ARP报文是发往本机的响应报文，那么neigh会更新为NUD_REACHABLE状态；否则，维持原状态不变。#个人认为，这段代码是处理 NUD_INCOMPLETE/NUD_PROBE/NUD_DELAY向NUD_REACHABLE迁移的，但如果一台主机A发送一个对本机的ARP响应报文，那么会导致 neigh从NUD_NONE直接迁移到NUD_REACHABLE，当然，按照正常流程，一个ARP响应报文肯定是由于本机发送了ARP请求报文，那样 neigh已经处于NUD_INCOMPLETE状态了。

n = __neigh_lookup(&arp_tbl, &sip, dev, 0); if (n) {int state = NUD_REACHABLE;int override;verride = time_after(jiffies, n->updated + n->parms->locktime); if (arp->ar_op != htons(ARPOP_REPLY) || skb->pkt_type != PACKET_HOST) state = NUD_STALE;neigh_update(n, sha, state, override ? NEIGH_UPDATE_F_OVERRIDE : 0);neigh_release(n); }

实际上，arp_process是接收到ARP报文的处理函数，它涉及到的是邻居表项在收到arp请求和响应的情况，下图反映了arp_process中所涉及的状态转移：收到arp请求，NUD_NONE -> NUD_STALE；收到arp响应， NUD_INCOMPLETE/NUD_DELAY/NUD_PROBE -> NUD_REACHABLE。根据之前分析，我认为还存在NUD_NONE -> NUD_REACHABLE和 NUD_INCOMPLETE -> NUD_STALE的转移，作何解释？

NUD状态

每个邻居表项在生效前都要经历一系列的状态迁移，每个状态都有不同的含义，在前面已经多次提到了NUD状态。要添加一条有效的邻居表项，有效途径有两条：

先引用再确认- NUD_NONE -> NUD_INCOMPLETE -> NUD_REACHABLE

先确认再引用 - NUD_NONE -> NUD_STALE -> NUD_DELAY -> NUD_PROBE -> NUD_REACHABLE

其中neigh_timer_handler定时器、neigh_periodic_work工作队列会异步的更改NUD状态，neigh_timer_handler用于NUD_INCOMPLETE, NUD_DELAY, NUD_PROBE, NUD_REACHABLE状态；neigh_periodic_work用于NUD_STALE。注意neigh_timer_handler是每个表项一个的，而 neigh_periodic_work是唯一的，NUD_STALE状态的表项没必要单独使用定时器，定期检查过期就可以了，这样大大节省了资源。

neigh_update则专门用于更新表项状态，neigh_send_event则是解析表项时的状态更新，能更新表项的函数很多，这里不一一列出。

neigh_timer_handler 定时器函数

当neigh处于NUD_INCOMPLETE, NUD_DELAY, NUD_PEOBE, NUD_REACHABLE时会添加定时器，即neigh_timer_handler，它处理各个状态在定时器到期时的情况。

当neigh处于NUD_REACHABLE状态时，根据NUD 的状态转移图，它有三种转移可能，分别对应下面三个条件语句。neigh->confirmed代表最近收到来自对应邻居项的报文时间，neigh->used代表最近使用该邻居项的时间。

-如果超时，但期间收到对方的报文，不更改状态，并重置超时时间为 neigh->confirmed+reachable_time；

-如果超时，期间未收到对方报文，但主机使用过该项，则迁移至NUD_DELAY状态，并重置超时时间为neigh->used+delay_probe_time；

-如果超时，且既未收到对方报文，也未使用过该项，则怀疑该项可能不可用了，迁移至NUD_STALE状态，而不是立即删除，neigh_periodic_work()会定时的清除NUD_STALE状态的表项。

if (state & NUD_REACHABLE) {if (time_before_eq(now, neigh->confirmed + neigh->parms->reachable_time)) { NEIGH_PRINTK2(“neigh %p is still alive.n”, neigh); next = neigh->confirmed + neigh->parms->reachable_time;} else if (time_before_eq(now, neigh->used + neigh->parms->delay_probe_time)) { NEIGH_PRINTK2(“neigh %p is delayed.n”, neigh); neigh->nud_state = NUD_DELAY; neigh->updated = jiffies; neigh_suspect(neigh); next = now + neigh->parms->delay_probe_time;} else { NEIGH_PRINTK2(“neigh %p is suspected.n”, neigh); neigh->nud_state = NUD_STALE; neigh->updated = jiffies; neigh_suspect(neigh); notify = 1;} }

下图是对上面表项处于NUD_REACHABLE状态时，定时器到期后3种情形的示意图：

当neigh处于 NUD_DELAY状态时，根据NUD的状态转移图，它有二种转移可能，分别对应下面二个条件语句。

-如果超时，期间收到对方报文，迁移至NUD_REACHABLE，记录下次检查时间到next；

-如果超时，期间未收到对方的报文，迁移至NUD_PROBE，记录下次检查时间到next。

在NUD_STALE->NUD_PROBE中间还插入NUD_DELAY状态，是为了减少ARP包的数目，期望在定时时间内会收到对方的确认报文，而不必再进行地址解析。

else if (state & NUD_DELAY) {if (time_before_eq(now, neigh->confirmed + neigh->parms->delay_probe_time)) { NEIGH_PRINTK2(“neigh %p is now reachable.n”, neigh); neigh->nud_state = NUD_REACHABLE; neigh->updated = jiffies; neigh_connect(neigh); notify = 1; next = neigh->confirmed + neigh->parms->reachable_time;} else { NEIGH_PRINTK2(“neigh %p is probed.n”, neigh); neigh->nud_state = NUD_PROBE; neigh->updated = jiffies; atomic_set(&neigh->probes, 0); next = now + neigh->parms->retrans_time;} }

当neigh处于NUD_PROBE或NUD_INCOMPLETE状态时，记录下次检查时间到next，因为这两种状态需要发送ARP解析报文，它们过程的迁移依赖于ARP解析的进程。

else {/* NUD_PROBE|NUD_INCOMPLETE */ next = now + neigh->parms->retrans_time; }

经过定时器超时后的状态转移，如果neigh处于NUD_PROBE或NUD_INCOMPLETE，则会发送ARP报文，先会检查报文发送的次数，如果超过了限度，表明对方主机没有回应，则neigh进入NUD_FAILED，被释放掉。

if ((neigh->nud_state & (NUD_INCOMPLETE | NUD_PROBE)) &&atomic_read(&neigh->probes) >= neigh_max_probes(neigh)) {neigh->nud_state = NUD_FAILED;notify = 1;neigh_invalidate(neigh); }

检查完后，如果还未超过限度，则会发送ARP报文，neigh->ops->solicit在创建表项neigh时被赋值，一般是 arp_solicit，并且增加探测计算neigh->probes。

if (neigh->nud_state & (NUD_INCOMPLETE | NUD_PROBE)) {struct sk_buff *skb = skb_peek(&neigh->arp_queue);/* keep skb alive even if arp_queue overflows */ if (skb) skb = skb_copy(skb, GFP_ATOMIC);write_unlock(&neigh->lock);neigh->ops->solicit(neigh, skb);atomic_inc(&neigh->probes);kfree_skb(skb); }

实际上，neigh_timer_handler处理启用了定时器状态超时的情况，下图反映了neigh_timer_handler中所涉及的状态转移，值得注意的是NUD_DELAY -> NUD_REACHABLE的状态转移，在arp_process中也提到过，收到arp reply时会有表项状态 NUD_DELAY -> NUD_REACHABLE。它们两者的区别在于arp_process处理的是arp的确认报文，而neigh_timer_handler处理的是 4层的确认报文。

neigh_periodic_work NUD_STALE状态的定时函数

当neigh处于NUD_STALE状态时，此时它等待一段时间，主机引用到它，从而转入NUD_DELAY状态；没有引用，则转入NUD_FAIL，被释放。不同于NUD_INCOMPLETE、NUD_DELAY、 NUD_PROBE、NUD_REACHABLE状态时的定时器，这里使用的异步机制，通过定期触发neigh_periodic_work()来检查NUD_STALE状态。

tbl->parms.base_reachable_time = 30 HZ

当初始化邻居表时，添加了neigh_periodic_work工作

neigh_table_init() -> neigh_table_init_no_netlink()：

INIT_DELAYED_WORK_DEFERRABLE(&tbl- >gc_work, neigh_periodic_work);

当neigh_periodic_work执行时，首先计算到达时间(reachable_time)，其中要注意的是

p->reachable_time = neigh_rand_reach_time(p->base_reachable_time); unsigned long neigh_rand_reach_time(unsigned long base) {return (base ? (net_random() % base) + (base >> 1) : 0); }

因此，reachable_time实际取值是1/2 base ~ 2/3 base，而base = base_reachable_time，当表项处于 NUD_REACHABLE状态时，会启动一个定时器，时长为reachable_time，即一个表项在不被使用时存活时间是1/2 base_reachable_time ~ 2/3 base_reachable_time。

然后它会遍历整个邻居表，每个hash_buckets的每个表项，如果在 gc_staletime内仍未被引用过，则会从邻居表中清除。

for (i = 0 ; i <= tbl->hash_mask; i++) {np = &tbl->hash_buckets[i];while ((n = *np) != NULL) { ….. if (atomic_read(&n->refcnt) == 1 && (state == NUD_FAILED || time_after(jiffies, n->used + n->parms->gc_staletime))) { *np = n->next; n->dead = 1; write_unlock(&n->lock); neigh_cleanup_and_release(n); continue;}…… }

在工作最后，再次添加该工作到队列中，并延时1/2 base_reachable_time开始执行，这样，完成了 neigh_periodic_work工作每隔1/2 base_reachable_time执行一次。

schedule_delayed_work(&tbl->gc_work, tbl- >parms.base_reachable_time >> 1);

neigh_periodic_work定期执行，但要保证表项不会刚添加就被 neigh_periodic_work清理掉，这里的策略是：gc_staletime大于1/2 base_reachable_time。默认的，gc_staletime = 30， base_reachable_time = 30。也就是说，neigh_periodic_work会每15HZ执行一次，但表项在NUD_STALE的存活时间是30HZ，这样，保证了每项在最差情况下也有(30 - 15)HZ的生命周期。

neigh_update 邻居表项状态更新

如果新状态是非有效(! NUD_VALID)，那么要做的就是删除该表项：停止定时器neigh_del_timer，设置neigh状态nud_state为新状态new。除此之外，当是NUD_INCOMPLETE或NUD_PROBE状态时，可能有暂时因为地址没有解析而暂存在neigh->arp_queue中的报文，而现在表项更新到NUD_FAILED，即解析无法成功，那么这么暂存的报文也只能被丢弃neigh_invalidate。

if (!(new & NUD_VALID)) {neigh_del_timer(neigh);if (old & NUD_CONNECTED) neigh_suspect(neigh);neigh->nud_state = new;err = 0;notify = old & NUD_VALID;if ((old & (NUD_INCOMPLETE | NUD_PROBE)) && (new & NUD_FAILED)) { neigh_invalidate(neigh); notify = 1;}goto out; }

中间这段代码是对比表项的地址是否发生了变化，略过，

#个人认为NUD_REACHABLE状态时，新状态为NUD_STALE是在下面这段代码里面除去了，因为NUD_REACHABLE状态更好，不应该回退到NUD_STALE状态。但是当是NUD_DELAY, NUD_PROBE, NUD_INCOMPLETE时仍会被更新到NUD_STALE状态，对此很不解???

else {if (lladdr == neigh->ha && new == NUD_STALE && ((flags & NEIGH_UPDATE_F_WEAK_OVERRIDE) || (old & NUD_CONNECTED))) new = old; }

新旧状态不同时，首先删除定时器，如果新状态需要定时器，则重新设置定时器，最后设置表项neigh为新状态new。

if (new != old) {neigh_del_timer(neigh);if (new & NUD_IN_TIMER) neigh_add_timer(neigh, (jiffies + ((new & NUD_REACHABLE) ? neigh->parms->reachable_time : 0)));neigh->nud_state = new; }

如果邻居表项中的地址发生了更新，有了新的地址值lladdr，那么更新表项地址neigh->ha，并更新与此表项相关的所有缓存表项neigh_update_hhs。

if (lladdr != neigh->ha) {memcpy(&neigh->ha, lladdr, dev->addr_len);neigh_update_hhs(neigh);if (!(new & NUD_CONNECTED)) neigh->confirmed = jiffies - (neigh->parms->base_reachable_time << 1);notify = 1; }

如果表项状态从非有效(!NUD_VALID)迁移到有效(NUD_VALID)，且此表项上的arp_queue上有项，表明之前有报文因为地址无法解析在暂存在了arp_queue上。此时表项地址解析完成，变为有效状态，从arp_queue中取出所有待发送的报文skb，发送出去n1->output(skb)，并清空表项的arp_queue。

if (!(old & NUD_VALID)) {struct sk_buff *skb; while (neigh->nud_state & NUD_VALID && (skb = __skb_dequeue(&neigh->arp_queue)) != NULL) { struct neighbour *n1 = neigh; write_unlock_bh(&neigh->lock); /* On shaper/eql skb->dst->neighbour != neigh :( */ if (skb_dst(skb) && skb_dst(skb)->neighbour) n1 = skb_dst(skb)->neighbour; n1->output(skb); write_lock_bh(&neigh->lock);}skb_queue_purge(&neigh->arp_queue); }

neigh_event_send

当主机需要解析地址，会调用neigh_resolve_output，主机引用表项明显会涉及到表项的NUD状态迁移，NUD_NONE->NUD_INCOMPLETE，NUD_STALE->NUD_DELAY。

neigh_event_send -> __neigh_event_send

只处理nud_state在NUD_NONE, NUD_STALE, NUD_INCOMPLETE状态时的情况：

if (neigh->nud_state & (NUD_CONNECTED | NUD_DELAY | NUD_PROBE)) goto out_unlock_bh;

不处于NUD_STALE和NUD_INCOMPLETE状态，则只能是NUD_NONE。此时主机要用到该邻居表项(注意是通过neigh_resolve_output进入的)，但还没有，因此要通过ARP进行解析，并且此时没有收到对方发来的任何报文，要进行的ARP是广播形式。

在发送ARP报文时有3个参数- ucast_probes, mcast_probes, app_probes，分别代表单播次数，广播次数，app_probes比较特殊，一般情况下为0，当使用了arpd守护进程时才会设置它的值。如果已经收到过对方的报文，即知道了对方的MAC-IP，ARP解析会使用单播形式，次数由ucast_probes决定；如果未收到过对方报文，此时ARP解析只能使用广播形式，次数由mcasat_probes决定。

当mcast_probes有值时，neigh进入NUD_INCOMPLETE状态，设置定时器，注意此时neigh_probes(表示已经进行探测的次数)初始化为ucast_probes，目的是只进行mcast_probes次广播；当mcast_probes值为0时(表明当前配置不允许解析)，neigh进入NUD_FAILED状态，被清除。

if (!(neigh->nud_state & (NUD_STALE | NUD_INCOMPLETE))) {if (neigh->parms->mcast_probes + neigh->parms->app_probes) { atomic_set(&neigh->probes, neigh->parms->ucast_probes); neigh->nud_state = NUD_INCOMPLETE; neigh->updated = jiffies; neigh_add_timer(neigh, now + 1);} else { neigh->nud_state = NUD_FAILED; neigh->updated = jiffies; write_unlock_bh(&neigh->lock); kfree_skb(skb); return 1;} }

当neigh处于NUD_STALE状态时，根据NUD的状态转移图，主机引用到了该邻居表项，neigh转移至NUD_DELAY状态，设置定时器。

else if (neigh->nud_state & NUD_STALE) { NEIGH_PRINTK2(“neigh %p is delayed.n”, neigh); neigh->nud_state = NUD_DELAY; neigh->updated = jiffies; neigh_add_timer(neigh, jiffies + neigh->parms->delay_probe_time);}

当neigh处于NUD_INCOMPLETE状态时，需要发送ARP报文进行地址解析，__skb_queue_tail(&neigh->arp_queue, skb) 的作用就是先把要发送的报文缓存起来，放到neigh->arp_queue链表中，当完成地址解析，再从neigh->arp_queue取出报文，并发送出去。

if (neigh->nud_state == NUD_INCOMPLETE) {if (skb) { if (skb_queue_len(&neigh->arp_queue) >= neigh->parms->queue_len) { struct sk_buff *buff; buff = __skb_dequeue(&neigh->arp_queue); kfree_skb(buff); NEIGH_CACHE_STAT_INC(neigh->tbl, unres_discards); } __skb_queue_tail(&neigh->arp_queue, skb);}rc = 1; }

邻居表的操作

neigh_create 创建邻居表项

首先为新的邻居表项struct neighbour分配空间，并做一些初始化。传入的参数tbl就是全局量arp_tbl，分配空间的大小是tbl->entry_size，而这个值在声明arp_tbl时初始化为sizeof (struct neighbour) + 4，多出的4个字节就是key值存放的地方。

n = neigh_alloc(tbl);

拷贝key(即IP地址) 到primary_key，而primary_key就是紧接neighbour的4个字节，看下struct neighbor的声明 - u8 primary_key[0]；设置n- >dev指向接收到报文的网卡设备dev。

memcpy(n->primary_key, pkey, key_len); n->dev = dev;

哈希表是牺牲空间换时间，保证均匀度很重要，一旦某个表项的值过多，链表查找会降低性能。因此当表项数目entries大于初始分配大小hash_mask+1时，执行neigh_hash_grow将哈希表空间倍增，这也是内核使用哈希表时常用的方法，可变大小的哈希表。

if (atomic_read(&tbl->entries) > (tbl->hash_mask + 1))neigh_hash_grow(tbl, (tbl->hash_mask + 1) << 1);

通过pkey和dev计算哈希值，决定插入tbl- >hash_buckets的表项。

hash_val = tbl->hash(pkey, dev) & tbl->hash_mask;

搜索tbl- >hash_buckets[hash_val]项，如果创建的新ARP表项已存在，则退出；否则将其n插入该项的链表头。

for (n1 = tbl->hash_buckets[hash_val]; n1; n1 = n1->next) {if (dev == n1->dev && !memcmp(n1->primary_key, pkey, key_len)) { neigh_hold(n1); rc = n1; goto out_tbl_unlock;} } n->next = tbl->hash_buckets[hash_val]; tbl->hash_buckets[hash_val] = n;

附一张创建ARP表项并插入到hash_buckets的图：

neigh_lookup 查找 ARP表项

查找函数很简单，以IP地址和网卡设备(即pkey和dev)计算哈希值hash_val，然后在tbl->hash_buckets查找相应项。

hash_val = tbl->hash(pkey, dev); for (n = tbl->hash_buckets[hash_val & tbl->hash_mask]; n; n = n->next) {if (dev == n->dev && !memcmp(n->primary_key, pkey, key_len)) { neigh_hold(n); NEIGH_CACHE_STAT_INC(tbl, hits); break;} }

代理ARP

代理ARP的相关知识查阅google。要明确代理ARP功能是针对陆由器的(或者说是具有转发功能的主机)。开启ARP代理后，会对查询不在本网段的ARP请求包回应。

回到之前的arp_process代码，处理代理ARP的情况，这实际就是进行代理ARP的条件，IN_DEV_FORWARD是支持转发，RTN_UNICAST是与路由直连，arp_fwd_proxy表示设备支持代理行为， arp_fwd_pvlan表示支持代理同设备进出，pneigh_lookup表示目的地址的代理。这两种arp_fwd_proxy和arp_fwd_pvlan都只是网卡设备的一种性质，pneigh_lookup则是一张代理邻居表，它的内容都是手动添加或删除的，三种策略任一一种满足都可以进行代理ARP。

else if (IN_DEV_FORWARD(in_dev)) {if (addr_type == RTN_UNICAST && (arp_fwd_proxy(in_dev, dev, rt) || arp_fwd_pvlan(in_dev, dev, rt, sip, tip) || pneigh_lookup(&arp_tbl, net, &tip, dev, 0)))

pneigh_lookup 查找或添加代理邻居表项[proxy neighbour]

以[pkey=tip, key_len=4]计算hash值，执行__pneigh_lookup_1在phash_buckets中查找。

u32 hash_val = pneigh_hash(pkey, key_len); n = __pneigh_lookup_1(tbl->phash_buckets[hash_val], net, pkey, key_len, dev);

如果在phash_buckets中查找到，或者不需要创建新表项，则函数返回，此时它的功能仅仅是lookup。

if (n || !creat)goto out;

而当传入参数create=1时，则它的功能不仅是lookup，还会在表项不存在时create。同neighbour结构一样，键值pkey存储在pneigh结构的后面，这样当pkey变化时，修改十分容易。创建操作很直观，为pneigh和pkey分配空间，初始化些变量，最后插入phash_buckets。

n = kmalloc(sizeof(*n) + key_len, GFP_KERNEL); …… write_pnet(&n->net, hold_net(net)); memcpy(n->key, pkey, key_len); …… n->next = tbl->phash_buckets[hash_val]; tbl->phash_buckets[hash_val] = n;

pneigh_enqueue 将报文加入代理队列

首先计算下次调度的时间，这是一个随机值，记录到sched_next中；设置flags|=LOCALLY_ENQUEUED表明报文是本地加入的。

unsigned long sched_next = now + (net_random() % p->proxy_delay); …… NEIGH_CB(skb)->sched_next = sched_next; NEIGH_CB(skb)->flags |= LOCALLY_ENQUEUED;

然后将报文加入proxy_queue，并设置定时器proxy_timer，下次超时时间为刚计算的值sched_next，这样，下次超时时就会处理proxy_queue队列中的报文。

__skb_queue_tail(&tbl->proxy_queue, skb); mod_timer(&tbl->proxy_timer, sched_next);

这里的tbl当然是arp_tbl，它的proxy_timer是在初始化时设置的arp_init() -> neigh_table_init_no_netlink()中：

setup_timer(&tbl->proxy_timer, neigh_proxy_process, (unsigned long)tbl);

neigh_proxy_process 代理ARP的定时器

skb_queue_walk_safe如同 for循环一样，它遍历proxy_queue，一个个取出其中的报文skb，查看报文的调度时间sched_next与当前时间now的差值。

如果tdif<=0则表明调度时间已到或已过，报文要被处理了，从proxy_queue上取出该报文，调用tbl->proxy_redo重新发送报文，tbl->proxy_redo也是在arp初始化时赋值的，实际上就是arp_process()函数。结合上面的分析，它会执行 arp_process中代理ARP处理的else部分，发送响应报文。

如果tdif>0则表明调度时间还未到，else if部分的功能就是记录下最近要过期的调度时间到sched_next。

skb_queue_walk_safe(&tbl->proxy_queue, skb, n) {long tdif = NEIGH_CB(skb)->sched_next - now; if (tdif <= 0) { struct net_device *dev = skb->dev; __skb_unlink(skb, &tbl->proxy_queue); if (tbl->proxy_redo && netif_running(dev)) tbl->proxy_redo(skb); else kfree_skb(skb); dev_put(dev);} else if (!sched_next || tdif < sched_next) sched_next = tdif; }

重新设置proxy_timer的定时器，下次超时时间为刚刚记录下的最近要调度的时间sched_next + 当前时间jiffies。

del_timer(&tbl->proxy_timer); if (sched_next)mod_timer(&tbl->proxy_timer, jiffies + sched_next);

以一张简单的图来说明ARP代理的处理过程，过程一是入队列等待，过程二是出队列发送。不立即处理ARP代理请求报文的原因是为了性能，收到报文后会启动定时器，超时时间是一个随机变量，保证了在大量主机同时进行此类请求时不会形成太大的负担。

邻居表缓存

邻居表缓存中存储的就是二层报头，如果缓存的报头正好被用到，那么直接从邻居表缓存中取出报文就行了，而不用再额外的构造报头，加快了协议栈的响应速度。

neigh_hh_init 创建新的邻居表缓存

当发送报文时，如果还没有对方主机MAC地址，则调用neigh_resove_output进行地址解析，此时会判断dst->hh为NULL时，就会调用neigh_hh_init创建邻居表缓存，加速下次的报文发送。

首先在邻居表项所链的所有邻居表缓存项n->hh匹配协议号protocol，找到，则说明已有缓存，不必再创建， neigh_hh_init会直接返回；未找到，则会创建新的缓存项hh。

for (hh = n->hh; hh; hh = hh->hh_next)if (hh->hh_type == protocol) break;

下面代码段创建了新的缓存项hh，并初始化了hh的内容，其中dev->header_ops->cache会赋值hh- >hh_data，即[SRCMAC, DSTMAC, TYPE]。如果赋值失败，释放掉刚才分配的hh；如果赋值成功，将hh链入n->hh的链表，并根据NUD状态赋值hh->hh_output。

if (!hh && (hh = kzalloc(sizeof(*hh), GFP_ATOMIC)) != NULL) {seqlock_init(&hh->hh_lock);hh->hh_type = protocol;atomic_set(&hh->hh_refcnt, 0);hh->hh_next = NULL; if (dev->header_ops->cache(n, hh)) { kfree(hh); hh = NULL;} else { atomic_inc(&hh->hh_refcnt); hh->hh_next = n->hh; n->hh = hh; if (n->nud_state & NUD_CONNECTED) hh->hh_output = n->ops->hh_output; else hh->hh_output = n->ops->output;} }

最后，创建成功的hh，陆由缓存dst->hh指向新创建的hh。

if (hh) {atomic_inc(&hh->hh_refcnt);dst->hh = hh; }

从hh的创建过程可以看出，通过邻居表项neighbour的缓存hh可以遍历所有的与neighbour相关的缓存(即目的MAC相同，但协议不同)；通过dst的缓存hh只能指向相关的一个缓存(尽管dst->hh->hh_next也许有值，但只会使用dst->hh)。

这里解释了为什么neighbour和dst都有hh指针指向缓存项，可以这么说，neighbour指向的hh是全部的，dst指向的hh是特定一个。两者的作用：在发送报文时查找完陆由表找到dst后，会直接用dst->hh，得到以太网头；而当远程主机MAC地址变更时，通过dst->neighbour->hh可以遍历所有缓存项，从而全部更改，而用dst->hh得一个个查找，几乎是无法完成的。可以这么说，dst->hh是使用时用的，neigh->hh是管理时用的。

neigh_update_hhs 更新缓存项

更新缓存项更新的实际就是缓存项的MAC地址。比如当收到一个报文，以它源IP为键值在邻居表中查找到的neighbour表项的n->ha与报文源MAC值不同时，说明对方主机的MAC地址发生了变更，此时就需要更新所有以旧MAC生成的hh为新MAC。

邻居表项是以IP为键值查找的，因此通过IP可以查找相关的邻居表项neigh，前面说过neigh- >hh可以遍历所有以之相关的缓存项，所以遍历它，并调用update函数。以以太网卡为例，update = neigh->dev- >header_ops->cache_update ==> eth_header_cache_update，而eth_header_cache_update函数就是用新的MAC地址覆盖hh->data中的旧MAC地址。

neigh_update_hhs函数也说明了neighbour->hh指针的作用。

for (hh = neigh->hh; hh; hh = hh->hh_next) { write_seqlock_bh(&hh->hh_lock); update(hh, neigh->dev, neigh->ha); write_sequnlock_bh(&hh->hh_lock);}

补充：缓存项hh的生命期从创建时起，会一直持续到邻居表项被删除，也就是调用neigh_destroy时，删除neigh->hh指向的所有缓存项。

参考：《Understanding Linux Network Internals》

篇5：Linux内核分析网络[四补]：路由表补充

内核版本：2.6.34

前篇路由表blog.csdn.net/qy532846454/article/details/6423496说明了路由表的结构及路由表的创建，下面是一些路由表的使用的细枝末节，作补充说明。

路由可以分为两部分：路由缓存(rt_hash_table)和路由表 ()

路由缓存顾名思义就是加速路由查找的，路由缓存的插入是由内核控制的，而非人为的插入，与之相对比的是路由表是人为插入的，而非内核插入的。在内核中，路由缓存组织成rt_hash_table的结构。

下面是一段IP层协议的代码段 [net/ipv4/route.c]，传入IP层的协议在查找路由时先在路由缓存中查找，如果已存在，则skb_dst_set(skb, &rth- >u.dst)并返回；否则在路由表中查询。

[cpp] view plaincopy hash = rt_hash(daddr, saddr, iif, rt_genid(net)); rcu_read_lock(); for (rth = rcu_dereference(rt_hash_table[hash].chain); rth; rth = rcu_dereference(rth->u.dst.rt_next)) { if (((rth->fl.fl4_dst ^ daddr) |(rth->fl.fl4_src ^ saddr) |(rth->fl.iif ^ iif) |rth->fl.oif |(rth->fl.fl4_tos ^ tos)) == 0 && rth->fl.mark == skb->mark && net_eq(dev_net(rth->u.dst.dev), net) && !rt_is_expired(rth)) { dst_use(&rth->u.dst, jiffies); RT_CACHE_STAT_INC(in_hit); rcu_read_unlock(); skb_dst_set(skb, &rth->u.dst); return 0; } RT_CACHE_STAT_INC(in_hlist_search); } rcu_read_unlock();

在ip_route_input()中查询完陆由缓存后会处理组播地址，如果是组播地址，则下面判断会成功：ipv4_is_multicast(daddr)。

然后执行ip_route_input_mc()，它的主要作用就是生成路由缓存项rth，并插入缓存。rth的生成与初始化只给出了input函数的，其它略去了，可以看出组播报文会通过ip_local_deliver()继续向上传递。

rth->u.dst.input= ip_local_deliver; hash = rt_hash(daddr, saddr, dev->ifindex, rt_genid(dev_net(dev))); return rt_intern_hash(hash, rth, NULL, skb, dev->ifindex);

路由表又可以分为两个：RT_TABLE_LOCAL和 RT_TABLE_MAIN

RT_TABLE_LOCAL存储目的地址是本机的路由表项，这些目的地址就是为各个网卡配置的IP地址；

RT_TABLE_MAIN存储到其它主机的路由表项；

显然，RT_TABLE_MAIN路由表只有当主机作为路由器时才有作用，一般主机该表是空的，因为主机不具有转发数据包的功能，

RT_TABLE_LOCAL对主机就足够了，为各个网卡配置的IP地址都会加入 RT_TABLE_LOCAL中，如为eth1配置了1.2.3.4的地址，则RT_TABLE_LOCAL中会存在1.2.3.4的路由项。只有本地的网卡地址会被加入，比如lo、eth1。IP模块在初始化时ip_init() -> ip_rt_init() - > ip_fib_init()会注册notifier机制，当为网卡地址配置时会执行fib_netdev_notifier和fib_inetaddr_notifier，使更改反映到RT_TABLE_LOCAL中。

register_netdevice_notifier(&fib_netdev_notifier); register_inetaddr_notifier(&fib_inetaddr_notifier);

而当在路由缓存中没有查找到缓存项时，会进行路由表查询，还是以IP层协议中的代码段为例[net/ipv4/route.c]，fib_lookup()会在MAIN和LOCAL两张表中进行查找。

if ((err = fib_lookup(net, &fl, &res)) != 0) { if (!IN_DEV_FORWARD(in_dev)) goto e_hostunreach; goto no_route; }

如果主机配置成了支持转发，则无论在路由表中找到与否，都会生成这次查询的一个缓存，包括源IP、目的IP、接收的网卡，插入路由缓存中：

hash = rt_hash(daddr, saddr, fl.iif, rt_genid(net)); err = rt_intern_hash(hash, rth, NULL, skb, fl.iif);

不同的是，如果在路由表中查询失败，即数据包不是发往本机，也不能被本机转发，则会设置插入路由缓存的缓存项u.dst.input=ip_error，而u.dst.input即为IP层处理完后向上传递的函数，而ip_error()会丢弃数据包，被发送相应的ICMP错误报文。不在路由表中的路由项也要插入路由缓存，这可以看作路由学习功能，下次就可以直接在路由缓存中找到。

rth->u.dst.input= ip_error; rth->u.dst.error= -err; rth->rt_flags &= ~RTCF_LOCAL;

但如果主机不支持转发，即没有路由功能，则只有在找到时才会添加路由缓存项，都不会生成路由缓存项。这是因为在LOCAL表中没有找到，表明数据包不是发往本机的，此时缓存这样的路由项对于主机的数据包传输没有一点意义。它只需要知道哪些数据包是发给它的，其余的一律不管！

路由查询整合起来，就是由 ip_route_input()引入，然后依次进行路由缓存和路由表查询，并对路由缓存进行更新。路由缓存在每个数据包到来时都可能发生更新，但路由表则不一样，只能通过RTM机制更新，LOCAL表是在网卡配置时更新的，MAIN表则是由人工插入的 (inet_rtm_newroute)。

ip_route_input()

- 路由缓存查询

- 路由表查询：ip_route_input_slow() -> fib_lookup()

★ linux目录简单介绍Linux

★ Linux操作系统中的防火墙技术及其应用

★ SA399第四章读书笔记Windows系统

★ 网络管理员协议书

★ 内核完全注释1makefileUnix系统

★ 防火墙设计原则及重点方案选择

★ 计算机四级网络工程师试题及答案

★ DSP与单片机的一种高速通信实现方案

★ 基于组态软件的电动汽车CAN总线网络设计