我会在下周举行的 LinuxCon North America 上讲一下最近在做的 Linux 网络流量控制(traffic control),有机会来参加的朋友欢迎前来捧场!不能参加的朋友也可以在这里看到我的 slides。

网络流量控制是一个非常大的话题,不可能在一个小时的时间内全部讲完,只能选择其中比较重要的来讲。而且它很重要,直接关乎网络性能,可是讲解这部分代码的书几乎没有,已有的讲 Linux 内核网络的书基本上都跳过了这一个部分,所以我也会陆续在这里详细分析一下这些代码,一是弥补这个缺口,二是弥补讲稿中的不足。

1

Ottawa Linux Symposium

Posted in Life at August 1st, 2014 / 1 Comment »

提起 LinuxCon,Kernel Summit 可能大家都知道,Linux 研讨会相比却不是那么知名。至少在我看来,Linux 研讨会的技术含量比我经常参加的LinuxCon 要高。虽然我一次还没参加过,但时常在搜索 Linux 内核的相关的东西时会搜到在这个会议上发布的一些论文。

它是每年一度在加拿大渥太华(也不总是在这里)举行的偏学术性质技术会议,要求参加会议的演讲者都要提交一篇论文,而不是 slides,会后汇总到一起发表。我收到过两次邀请,但都没机会参加,因为一是去加拿大的签证不那么好办,需要准备很多材料;二是我没读过硕士和博士,写论文水平很差。Linux 社区相关的会议多数是偏技术的,这和社区的黑客文化也有关,能有这么一个偏学术的会议实属难得。

光说没用,你可以去读一下之前在这个会议上发表的论文:https://www.kernel.org/doc/ols/ 去感受一下它的含金量。

今年,Linux 研讨会的发起者遇到了资金的困难,需要大家的资助。反正我是不忍心看到这么好的一个会议停办,果断捐了 50 加元尽自己的一份力。希望喜欢这个会议的朋友也可以伸出援助之手,帮助这个会议继续开下去。当然,要是能有哪个土豪公司赞助那就再好不过了。:)

4

skbuff 内存模型

Posted in Linux Kernel at May 31st, 2014 / 4 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 工作比较轻松,公司提供免费的三餐,工作时间自由,带薪休假理论上无上限(只要你的上司批准),在这里工作的中国人也很多。欢迎投简历!

42

我的2013:我来到了美国

Posted in Life at January 30th, 2014 / 42 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。如果你能直接去贡献补丁,那当然是再好不过了。:)