0

skbuff 内存模型

Posted in Linux Kernel at May 31st, 2014 / No Comments »

众所周知,struct sk_buff 是 Linux 内核网络子系统中最重要的一个结构体,它是内核对网络数据包的一个抽象表示。要了解 Linux 网络子系统除了了解网络协议之外,了解内核如何表示和操作数据包也是至关重要的。Linux 内核中的 struct sk_buff (以下简称 skb)提供了一套非常复杂的内存模型,也对它进行了大量的优化,这也是为什么 Linux 网络如此高效。

我们从最简单的开始,分配一个最普通的 skb:

内核分配 skb 的函数是 __alloc_skb(),它有很多种包装供不同的场景使用。如上图所示,在这里我们分配了两部分内存:1) skb struct 本身,也叫元数据( meta data);2) 实际存放网络数据包的内存。这里你可以把 skb 看作是一堆指针,这些指针指向一块内存的不同区域。下面我们会看到,很多时候我们都是对指针本身进行操作。

注意:其实严格的说上图中所示的指针并不一定都是指针,Linux 内核进行了优化。在 64 位系统上,一个指针也是64位,储存指针的开销太大。而数据包本身不可能太大(以太网 MTU 是 1500 字节,就算是 jumbo frame 也才 9000 字节),因此 Linux 内核仅仅把 head 和 data 保存为指针,其它的只要存储相对于它们的偏移即可。下面的所有图中把它们表示为指针仅仅是为了方便。


而一个完整的网络数据包在内存中的表示通常有四个部分:

1) head room,位于 skb->head 和 skb->data 之间,也就是存放网络协议头的地方,比如 TCP,IP 头,以太网头都是位于此;

2) 用户数据,通常由应用层通过系统调用填充,介于 skb->data 和 skb->tail 之间;

3) tail room,介于 skb->tail 和 skb->end 之间,这部分是内核在用户数据后面填充的一部分;

4) skb->end 之后存放的是一个特殊的结构体 struct skb_shared_info,下面会讲到它。

刚分配出来的 skb 除了 skb->end 指向末尾的 struct skb_shared_info,其它指针都指向了开始处。通常第一步就是初始化 head room,调用 skb_reserve() 这个函数,如下图所示:

比如 TCP 层要发送一个数据包,head room 至少要是 tcphdr + iphdr + ethhdr。然后在协议头的后面开始预留数据区,调用的函数是 skb_put(),如下图所示:

到此为止,前面提到的四个部分才全部初始化完毕,通常情况下,这些操作要么是由传输层完成(发送),要么是由网卡驱动完成(接收)。一点一点往里填充数据或者向外读取数据则是各层协议的事情。数据包入栈时(即接收),数据是一层一层往里读取,协议头是一层一层剥掉。数据包出栈时(发送),协议头则是一层一层往外填写。

内核提供的剥掉协议头的操作函数是 skb_pull(),如名字所示,它是往下拉 skb->data:

类似地,往外推 skb->data 的操作叫做 skb_push():

很形象吧?

好,终于到前面一直默默无闻的 skb_shared_info 出场了。想象这么一种常见的情况:我们用 tcpdump 捕捉一个网卡收到的数据包。此时数据包入栈后会有两个部分同时进行读:一是协议栈本身,另一个就是 tcpdump 了。这种情况下要不要完全复制一份 skb 呢?没有必要,因为两部分都是读,网络数据本身是不变的,变的只是 strcut sk_buff 里面的指针,也就是说,我们只要复制一份 skb 让它指向同样的内存区域就行了!这正是 skb_clone() 所做的:

如图所示,skb_shared_info 此时记录了一些变化,dataref 变成了2,代表有两个 skb 同时指向这块内存区域。由此可见,skb_shared_info 保存的是多个 skb 之间共享的,但又不属于网络数据的数据(也就是不会被传输的数据),所以才放在 skb->end 之后啊。

这还没完,Linux 内核开发者觉得还不够,每次 clone 都还要分配一个 skb 结构体,对于要 clone 很多次的情形还可以进行优化——使用 fast clone(缩写为fclone)。fclone 很有技巧性,它在分配 skb 的 cache 里做了手脚,每次分配 skb 时,它都是分配一对,一个紧紧地跟在另一个后面,如下图所示:

不用的时候你完全看不到它,用的时候通过 skb+1 就能找得到!当然了,它需要在 skb 结构体里保存一些状态信息表明这部分到底有没有用到。

在写的情况下我们还是要完全拷贝 skb 及其数据的,调用 skb_copy() :

到此为止都比较简单,我们假设了所有的数据都是放在 skb->head 和 skb->end 之间,也就是所谓的线性(linear)。世界要是这么简单就好了,可惜现实远比这复杂。内核至少还提供了另外三种非线性的 skb 模型。

一种是网卡驱动常用的模型,数据存放在物理页面的不同位置,skb_shared_info 里有一个数组,存放一组 (页面、偏移、大小) 的信息,用来记录这些数据:

另一种是组装 IP 数据包分片(fragment)时用到的 frag_list 模型:

分片的数据有各自的 skb 结构体,它们通过 skb->next 链接成一个单链表,表头是第一个 skb 的 shared_info 中的 frag_list。

最后一种是 GSO 进行分段(segmentation)用到的一种模型,当一个大的 TCP 数据包被切割成几个 MTU 大小的数据时,它们也是通过 skb->next 链接到一起的:

与分片不同的是,相关的信息是记录在最前面一个 skb 的 skb_shared_info 里面的 gso_segs 和 gso_size 里。

正因为存在以上各种复杂的模型,很多 skb API 的实现(比如 skb_segment())非常复杂,其大部分代码都是用来处理非线性的这几种情况,这使得 skbuff.c 里的很多代码都不容易读懂。希望本文能够对你理解这部分代码有所帮助。

参考资料:

1. http://vger.kernel.org/~davem/skb_data.html

3

长期提供 Twitter 内推

Posted in Life at May 6th, 2014 / 3 Comments »

今年断断续续收到不少求内推的邮件,在这里干脆直接写清楚好了,免得每次都得回邮件说明。

任何人都可以找我内推,无论是不是程序员,你只要把你感兴趣的职位链接和你的英文简历发到我的邮箱(xiyou 点 wangcong 在 gmail 点 com)即可。Cover letter 可有可无,你自己掌握。Twitter 公司的空缺职位在这里:https://about.twitter.com/careers,国内需翻墙,因为众所周知的原因。

我不提供修改简历服务,你发给我什么我就上传什么,也不会告诉你简历好不好之类的,那是 HR 的工作,不是我的。另外,网上教你写英文简历的文章一大把,我没义务更没时间告诉你怎么写。如果非得说应聘 Twitter 有何特殊要求,你不觉得简历里有一个你的推特帐号会更好么?:-)

因为 H-1b 签证的原因,国内的应聘者最好在每年的1月份到3月份之间应聘,或者更提前一些。根据这几年的情况来看,H-1b 配额4月份一出来就会被用光,不光如此还得抽签。所以4月份之后根本没戏,除非当年美国经济很差,H-1b 用不完了(这意味着职位空缺也少)。当然了,已经在美国本土的不受此限制。

在 Twitter 工作比较轻松,公司提供免费的三餐,工作时间自由,带薪休假理论上无上限(只要你的上司批准),在这里工作的中国人也很多。欢迎投简历!

40

我的2013:我来到了美国

Posted in Life at January 30th, 2014 / 40 Comments »

对我来说,2013 年有两件大事:一是不顾我爸的反对把婚结了;二是终于肉身翻墙了,而且是到了之前都没想过的美国硅谷,进了更没想过的 Twitter。

我认为结婚是两个人的事,父母当然有权利过问,但无权干涉,尤其是以一个荒唐的理由:她没有工作。我甚至都不好意思在这里写,可这就是我爸反对的理由,难以置信。别怪我没尝试和父母沟通,只是你不会理解和坚持认为周末上班才是正常的人沟通起来是有多么困难。

在很多中国人眼里,我这是不孝。我不这么认为,我觉得任何人首先是为自己活着,孝顺父母当然重要,但是再重要也不如自己的自由重要。生命是父母所给,但自由是上天所赐。如果他们愿意拿走我的生命,我绝对毫无怨言,可是我只要还活着一天,我都不能交出我的自由,尤其是选择我自己幸福的自由。古今中外,自古以来,永远都是歌颂爱情,从来没听说过歌颂父母干涉婚姻的。其实这是也我为什么打算要移民的一个最重要原因。

能来美国完全是靠运气,不是我谦虚,真的如此。我在2月份的时候张罗着找国外的工作机会,澳大利亚、加拿大、美国等都在考虑的范围之中,简历也在 linkedin 上投了不少,也有朋友在看到我的博客后帮我推荐的,无奈很多都是没有消息,最后基本上只收到了 Twitter 的回复。Twitter 的 HR 是我见过的效率最高的,没有之一。电话面试基本上当天就能收到结果,因为时差的原因我在美国西海岸时间晚上12点多还在和 HR 聊天。幸运的是所有面试我都通过了。

更幸运的是我在 H-1b 签证配额被抢光之前就拿到了 offer 并且提交了签证申请。因为今年美国经济复苏的缘故,工作机会特别多,也就是说全球申请 H-1b 的人特别多,多到超出配额一倍,所以只好进行抽签。更更幸运的是我被抽中了。更更更幸运的是我还赶在了 Twitter 上市之前到了。所以这完全归结于人品爆发的原因。

从9月底登陆美国到现在基本上4个月了,过了所谓的“新鲜期”,我想可以谈谈我对美国的感受了。美国其实没有什么伟大的,无非就是把人性的自由释放出来了,虽然它做得还是不够好,但是世界上比它做得更好的国家还真屈指可数,尤其是比起摸着石头过河的国家来说真是好太多了。

我们都知道不少在美国自由成功的故事,来到这里我也不可避免地在街上看到了很多自由失败的人——流浪汉。或许我在《经济为什么会崩溃》一书中读到的一句话最能够概括,“无法自由地失败,也就是无法自由地成功。”这一句的另一种读法就是,自由的代价就是允许你自由的失败。很多别有用心的人喜欢故意夸大自由的代价来让你相信自由多么可怕,可是我们要记得,天下没有免费的午餐,自由也不是天生完美的。

加州税高,但是缴的每一笔税我都清楚,把税交给一个民主透明的政府更让我感到放心,尤其是看到 Batkid这种故事 的时候,生平第一次感受到纳税纳得这么值!湾区虽然房价高,但是比起北京来,显然是一个码农可以承受得起的。

真心希望更多的中国人能亲自到美国来感受一下这究竟是一个怎样的国家,而不是受电视上的新闻报道(不管是好的还是坏的)所干扰。美国的强大不是说它是一个完美的国家,这个星球上没有哪个国家是完美的,甚至也不是说它的国父们设立的制度多么好,而是它有一种纠错能力,不管犯过多大的错误都能改正,尽管可能需要很多年。资本主义的罪恶是显而易见的,人们都能看到并且有自由去纠正它;共产主义的罪恶是欺骗性的、制度性的,它足以扼杀任何企图纠正它的人,无论地位高低。

自由,对于我来说,更主要的选择自己想过的生活不被别人说三道四的自由。相信很多像我这样的年轻人过年回家都有体会,你结婚生孩子的自由在你父母和亲戚们说三道四面前荡然无存,所以一个宽容的社会环境比允许你上街游行或许对于大多人来说在生活中更重要。在这一点上我很欣赏美国的父母们,我也认为孩子成年以后就是独立的个体,如果成年了还需要我们指手画脚地指导,那就是做父母的失败。

我想要移民的理由或许千百条,唯独没有的就是一定要以后的孩子去读名牌大学。虽然我们也会尽力让孩子接受好的教育,但是就算孩子以后高中毕业了选择去做清洁工,只要他/她做得开心,对社会无害,我们也绝对支持。美国的宽容社会至少不让人觉得做清洁工是丢人的一件事,并且还能有保障自己生活的收入,这就已经很足够了。我们甚至还想过,他/她如果是个同性恋,把自己的男朋友/女朋友带回家,我们就当又多了一个儿子或女儿,有何不好?

这才是自由的味道。

libnl 是用户空间对 netlink 包装的一个库,有了它使用 netlink 变得很方便了。你熟悉的 NetworkManager 就使用了它。它的官方网站是:http://www.infradead.org/~tgr/libnl/

对比内核已经实现的 TC classifier 和 TC action,你会发现 libnl 实现了不到其中一半,所以还有不少东西需要做。如果非要我写一个 list 的话,下面几个是优先级比较高的:

1) 添加 skbedit action 的支持;
2) 添加 cgroup classifier 的支持;
3) 添加 tun/tap 设备的支持;
4) 添加 gre tunnel 设备的支持。

通过 libnl 你可以深入了解 netlink,以及内核中的这些 netlink 接口设计,当然了还有 traffic control 的一些东西。感兴趣的话可以联系我:xiyou.wangcong <AT> gmail.com。如果你能直接去贡献补丁,那当然是再好不过了。:)

1

Ingress traffic control

Posted in Linux Kernel at October 22nd, 2013 / 1 Comment »

相信很多人都知道 Linux 内核很难做 ingress 流量控制的,毕竟发送方理论上可以无限制地发送包到达网络接口。即使你控制了从网络接口到达协议栈的流量,你也很难从根源上控制这个流量。

利用 Linux 内核你可以轻松地完成前者,即控制从网络接口到达协议栈的流量。这个是通过一个叫做 ifb 的设备完成的,这个设备如此不起眼以至于很多人不知道它的存在。

它的使用很简单,加载 ifb 模块后,激活 ifbX 设备:

modprobe ifb numifbs=1
ip link set dev ifb0 up # ifb1, ifb2, ... 操作相同

然后就要通过 ingress tc filter 把流入某个网络接口的流量 redirect 到 ifbX 上:

tc qdisc add dev eth0 handle ffff: ingress
tc filter add dev eth0 parent ffff: protocol ip u32 match u32 0 0 action mirred egress redirect dev ifb0

ingress 这个 qdisc 是不能加 class,但是我们这里使用了 ifb0,所以就可以在 ifb0 设备上添加各种 tc class,这样就和 egress 没有多少区别了。

ifb 的实现其实很简单,因为流入网络接口的流量是无法直接控制的,那么我们必须要把流入的包导入(通过 tc action)到一个中间的队列,该队列在 ifb 设备上,然后让这些包重走 tc 层,最后流入的包再重新入栈,流出的包重新出栈。看代码一目了然:

C:
  1. while ((skb = __skb_dequeue(&dp->tq)) != NULL) {
  2.                 u32 from = G_TC_FROM(skb->tc_verd);
  3.  
  4.                 skb->tc_verd = 0;
  5.                 skb->tc_verd = SET_TC_NCLS(skb->tc_verd);
  6.  
  7.                 u64_stats_update_begin(&dp->tsync);
  8.                 dp->tx_packets++;
  9.                 dp->tx_bytes += skb->len;
  10.                 u64_stats_update_end(&dp->tsync);
  11.  
  12.                 rcu_read_lock();
  13.                 skb->dev = dev_get_by_index_rcu(dev_net(_dev), skb->skb_iif);
  14.                 if (!skb->dev) {
  15.                         rcu_read_unlock();
  16.                         dev_kfree_skb(skb);
  17.                         _dev->stats.tx_dropped++;
  18.                         if (skb_queue_len(&dp->tq) != 0)
  19.                                 goto resched;
  20.                         break;
  21.                 }
  22.                 rcu_read_unlock();
  23.                 skb->skb_iif = _dev->ifindex;
  24.  
  25.                 if (from & AT_EGRESS) {
  26.                         dev_queue_xmit(skb);
  27.                 } else if (from & AT_INGRESS) {
  28.                         skb_pull(skb, skb->dev->hard_header_len);
  29.                         netif_receive_skb(skb);
  30.                 } else
  31.                         BUG();
  32.         }

这里有两个不太明显的地方值得注意:

1) 不论流入还是流出,tc 层的代码都是工作在 L2 的,也就是说代码是可以重入的,尤其是 skb 里的一些 header pointer;

2) 网络设备上的 ingress 队列只有一个,这也是为啥 ingress qdisc 只能做 filter 的原因,可以看下面的代码:

C:
  1. static int ing_filter(struct sk_buff *skb, struct netdev_queue *rxq)
  2. {
  3.         struct net_device *dev = skb->dev;
  4.         u32 ttl = G_TC_RTTL(skb->tc_verd);
  5.         int result = TC_ACT_OK;
  6.         struct Qdisc *q;
  7.  
  8.         if (unlikely(MAX_RED_LOOP <ttl++)) {
  9.                 net_warn_ratelimited("Redir loop detected Dropping packet (%d->%d)\n",
  10.                                      skb->skb_iif, dev->ifindex);
  11.                 return TC_ACT_SHOT;
  12.         }
  13.  
  14.         skb->tc_verd = SET_TC_RTTL(skb->tc_verd, ttl);
  15.         skb->tc_verd = SET_TC_AT(skb->tc_verd, AT_INGRESS);
  16.  
  17.         q = rxq->qdisc;
  18.         if (q != &noop_qdisc) {
  19.                 spin_lock(qdisc_lock(q));
  20.                 if (likely(!test_bit(__QDISC_STATE_DEACTIVATED, &q->state)))
  21.                         result = qdisc_enqueue_root(skb, q);
  22.                 spin_unlock(qdisc_lock(q));
  23.         }
  24.  
  25.         return result;
  26. }
  27.  
  28. static inline struct sk_buff *handle_ing(struct sk_buff *skb,
  29.                                          struct packet_type **pt_prev,
  30.                                          int *ret, struct net_device *orig_dev)
  31. {
  32.         struct netdev_queue *rxq = rcu_dereference(skb->dev->ingress_queue);
  33.  
  34.         if (!rxq || rxq->qdisc == &noop_qdisc)
  35.                 goto out;
  36.  
  37.         if (*pt_prev) {
  38.                 *ret = deliver_skb(skb, *pt_prev, orig_dev);
  39.                 *pt_prev = NULL;
  40.         }
  41.  
  42.         switch (ing_filter(skb, rxq)) {
  43.         case TC_ACT_SHOT:
  44.         case TC_ACT_STOLEN:
  45.                 kfree_skb(skb);
  46.                 return NULL;
  47.         }
  48.  
  49. out:
  50.         skb->tc_verd = 0;
  51.         return skb;
  52. }

而经过 tc action 后是导入到了 ifb 设备的发送队列,见 net/sched/act_mirred.c 的 tcf_mirred() 函数:

C:
  1. //...
  2.         skb2->skb_iif = skb->dev->ifindex;
  3.         skb2->dev = dev;
  4.         err = dev_queue_xmit(skb2);

也就是说这样就会有多个队列了,可以添加 class 了。:) 这大体也是 ingress traffic control 如何工作的了,可见 ifb 的存在既简单又巧妙地粘合了 egress 上的流量控制。

正如本文一开始讲到的,即使用 ifb 我们所做的流量控制仍然有限,很难从根本上控制发送方的速率。如果双方是通过交换机连接的话,或许通过 L2 上的一些协议可以控制速率,而如果中间经过路由器,那么所能做的就更加有限,只能期待传输层的协议进行控制,而不是靠传输层自身感受到丢包的多少去自动调整速率,因为这可能会花很长时间。

参考资料:

1. http://serverfault.com/questions/350023/tc-ingress-policing-and-ifb-mirroring
2. http://stackoverflow.com/questions/15881921/why-tc-cannot-do-ingress-shaping-does-ingress-shaping-make-sense

43

人生就是Moving On……

Posted in Life at September 21st, 2013 / 43 Comments »

最近很忙一直没有时间写博客,一半是因为工作时间没得闲,即使在大理这种休闲安逸的地方我也难得在工作时间偷个懒出去看看对面的明哥今天有没有新把的妹子;一半是因为我们准备去万恶的美帝体验水深火热去了。要准备的东西实在太多,毕竟我天朝物产极大丰富,去美帝这种大农村必须做好长期吃苦的准备,看了我媳妇收拾的东西你会觉得我们简直是要去非洲打猎……

半年多前我发了一篇求职的博客,之后收到好几个朋友的邮件邀请,但因为种种原因都没去成,人艰不拆,其实悲催到了连面试的机会都没有。好在后来我自己偶然间看到了下面一个让人眼前一亮的招聘:

身为一个逼格稍高的伪 geek,怎么能不被这逼格如此高的 JD 感动得潸然泪下?!没错,这就是 Twitter 招聘的一个内核开发职位。

再后来,心惊胆颤地经过一轮又一轮的面试,好不容易拿到 offer,然后又碰上了几年一遇的美帝万恶的 H-1b 抽签。好在之前快用光的运气原地满血复活了,我侥幸抽中,之后去成都领事馆面签也都挺顺利的。所以,我早就说过,找工作其实和找媳妇是一样一样的:你追的女神追了很久还是跟高富帅走了,正当你累感不爱的时候,你突然发现,其实有一个把你当男神的妹纸正在暗恋你。这都是靠缘分啊!

Twitter 给的待遇相当厚道,起码我算着够养活我和我媳妇两个人的。而且提供的 relocation 服务也相当好:搬家给提供一个集装箱,运一张床过去也足够了。机票给订好,到了旧金山之后提供临时住处,还有人专门带你去看要租的房子…… 至少这一点比红帽公司要厚道很多。

本月 25 号将会是我在红帽的最后一天,这么算下来一共待了4年4个月零21天。刚去的时候是做比较 general 的东西,说白了就是啥脏活累活都干,之后就开始做 kdump,最近一年多开始转做内核网络。这些年来用公司的邮箱一共给 Linux 内核提交了 323 个补丁。当然,我也跟红帽的大牛们学到很多很多的东西,技术上的和非技术上的。虽然很悲伤地发现自己现在依然不是大牛,但至少我认为我在成为大牛的路上,哪怕未来路途依旧遥远……总的来说,红帽在中国的待遇可能不是很好,但做的东西绝对是 Linux 内核领域最好的,至少我在的这个内核网络 team 如此。那些能够潜心做技术的同学还是很值得来试试的。

当然,也非常感谢我在红帽的两个美国经理,允许我长期在云南大理工作,免去了在北京忍受污染空气之毒。这是你给我再高的薪水也换不来的,我自认为至少在这一点上我比你们很多人明白什么更重要。:-) 我对比别人多活几年不感兴趣,我只是不想以后痛苦地死于肺癌,仅次而已。

在大理的这一年多的时间是我人生最好的时光之一,除了邂逅了我现在的媳妇,还有那“生命终究难舍蓝蓝的白云天”。虽然大理现在人也越来越多,但毫无疑问,大理依旧是我在国内可以找到的最适合居住的小城,没有之一!我也始终相信我的好运很大程度上是拜大理这个神奇的地方所赐。

27 号就要飞旧金山了,希望加州的阳光会像大理的一样灿烂!我们这次走得比较仓促,走之前无法和所有朋友见面一一道别,所以在此衷心祝愿国内的各位朋友,愿你们可以活得像梦一样自由!

P.S. 我的 twitter :https://twitter.com/bitstream