北京之行后记

这次是我第一次去北京,比较奇怪的是去的时候车票1号车厢1号座位,回来时1号车厢11号座位。

比较幸运的是,住的地方离国宾酒店只有三四百米,这个得感谢李阳同学;)。 第一天刚去没有休息,就和许振文、磊子、张斌、李阳他们去天安门广场逛了。等转了一大圈到故宫门口时都累了,于是回去休息了。

第二天和第三天主要是参加Linux World China大会,和意料中一样广告成份很重,不过有几个讲得很精彩。主要是Moblie Linux、嵌入式、虚拟化、云计算,还有市场策略方面的东西。信息量比较大,所以中间我用本子记了很多。会场外的展台也有七八家,微软也有展台,不过展台上的东西貌似都不是开源的。虚拟化方面有个VirtualLogix是做嵌入式虚拟技术的,讲了一些应用实例,主要是用于系统移植的。这次也见到了王开源、程勇,不过都没多聊。程勇讲了一些企业与开源社区方面的东西,不过感觉国内企业实际应用的不会太多。红旗没有摆展台,只是把宣传资料放到Intel那了。Intel展示了一款自己定制的操作系统,是基于Redhat的,本子体积也很小,特点就是快速开机,功能定制。还有一家公司展示的小本子可以在5秒内开机上网,这对办公、商用很实用。不过不能添加新软件,功能比较单一。这些基本都还在研发改进阶段。还见到尚观培训的一个牛人胡国忠,他推荐了两个自己的开源项目,maxwit.googlecode.com(基于Linux的嵌入式操作系统)、g-bios.googlecode.com(Android和普通嵌入式系统开发的bootloader/BIOS),从他的开发经历开来,此人对操作系统、内核很熟悉。而且他有一套很奇特的“教学”方法,话说能将啥都不知道的人,培训的能搞系统开发。

第二天晚上和陈老师的学生康华、郑烨、李小丁他们聊了很长时间,不过多数是康华一个人在讲,连郑烨都插不上话。康华主要作分布式存储方面的东西,不过他对整个行业的把握很深入,从各方面技术细节,到一些市场、行业分析。他们现在针对搜索引擎用户体验下降问题,正在研究一种新的数据检索。
第三天晚上和哲思聚会,第一次见到了Alex Peng、Xia Wu、Xia Qingran、Fang Zhou、Deng Nan,网上没有Xia Wu的照片,其他人都和想象中不一样,没想到Qingran也是个年轻小伙子,看他照片感觉很老成。还有上海Inbel的Yongwei,专门来北京“吵架”,后面包括陈老师在内,围绕自由软件大家进行了极其激烈的辩论。可惜这次自称“自由软件原教旨主义者”的Zoomq没有来,其他人都比较冷静一些无法“对抗”Yongwei对自由软件的N多怀疑。大家一块也对翻译《自由软件,自由社会》这本书,提出了很多建议,看来回来得好好做翻译工作了。其实大家都认为,这种内部辩论也是一种自我考问,我们需要真正理解自由软件,而不是一些教条。如果只接受单一的思想熏陶也可能走向一个极端,相反应该不断的思考,修正自己的思想、行为。Coly、宫民、冯莹等没来,只能等下次了。虽然聊了三个小时多,但还是感觉和很多人没有细细交流,不过这次见面后感觉亲切多了,以后多在网上交流吧。

第四天,陈老师有事出去了,我们准备闲逛一天晚上回西安,先去了清华,没怎么转。后来给周晓炜发短信联系了一下,他中午骑车过来。中午在清华门口等到了他,于是有跟他去中科院玩。晓炜这半年变化不是很大,吃完饭他去上课了,我们又溜到知春路。李阳、张斌去了中关村,磊子去找女人了,我本来想去哲思总部,不过地方不是很清楚,于是和许振文去王府井逛了一下午,买了些东西。其中我买了一个牙签盒,上面是”惜春作画”的图案,本来打算买胭脂盒的。;)六点多磊子他们都也过来了,一起寻找N久才找了家超市,买了些吃的去火车站和老师会合。

第五天早上就到西安了。这几天接受了各个方面的信息和思想,陈老师经常和我们聊天,怕我们受影响太过浮躁。总之回来后要继续,踏实学习、注重基础、重点深入,继续Happy Hacking~

PHOTOS: http://picasaweb.google.com/kongjianjun/LinuxWorldChina2008Beijing

Linux World China

https://i0.wp.com/www.linuxworldchina.com/images/index_03.gif

今天准备去北京参加25~26日的Linux World China大会,估计得去三到四天时间。从会议日程看内容还真不少,也是一次开开眼界的机会。有时候这种技术之外的思想引导也很重要,能让人看得更远、更深一些。

同去的有陈老师、许振文、磊子、张斌、李阳,虽说这个大会有些内容广告性质太浓,但总的来说还是能收获很多东西。

哲思也借这次机会,有一个聚会,平时大家多是邮件交流,面对面的交流也能促进彼此的沟通熟悉,也会商量一些哲思的项目、计划。

另外也是出去逛逛、散散心,成天面对电脑也不行。

Dream of Red Chamber

http://player.youku.com/player.php/sid/XMzg2NTA0MDQ=/v.swf

晴雯歌(Qingwen Song)

http://player.youku.com/player.php/sid/XNDk4ODIxMzI=/v.swf

秋风窗雨夕

第一次看红楼梦,看到晴雯撕扇子,宝玉叫好。不知为啥感觉这女的不是很讨人喜欢。前段时间利用闲时间把86版红楼梦在优酷上看了一遍,后面也看了刘心武的一些分析,发现里边有很多很多东西值得深入!前天从“小景”那拷东西,发现她居然有红楼梦的清晰版(10G多),于是拷了回来,不过还没来的急看。只是把里边艺术人生“红楼梦再聚首”看了一下,看到一个个戏中人物走出“红楼”后的酸甜人生,有点感慨,也有丝惆怅。

其中“贾宝玉”(欧阳奋强)拍完红楼梦,面对人生大的落差并没有放弃自己,而是改行从演习转向作导演,一次去大学深造的机会使他进入了导演生涯的正轨,然而造化弄人,全身心投入事业的他,有遭遇了丧子的沉痛打击。不过后来他还是坚持了下来,现在的导演事业做的还算好。不过他说最令他遗憾的就是,走在大街上别人看到他会说,这是演“贾宝玉”的…,而不说是他是某部好看电视剧的导演。他有句话“既然把这活接下了,咱就给他干好!” 站在观众面前的不是那个男不男女不女的个贵公子,而是一个务实、勤奋,留着两撇小胡子的导演-欧阳奋强。还有林黛玉等的人生发展、事业转变,以及他们对工作、事业、生活的平和心态,同样给人很多感触,很多深思。

不过,最近发现很多插曲都很好听(http://www.youku.com/playlist_show/id_2512870.html),有时间一定要深入研究一下红学。

使用Vim+Ctags+Cscope阅读源代码

--孔建军(Kongove.CN)
2008.11.15

代码阅读工具简介

对于学习Linux内核的人来说,源代码的阅读尤为重要。因为所有设计思想、内部机制都是以代码的形式实现,所有的资料也都是为了更好的诠释代码。那么一个好的阅读工具,能够提高阅读的效率和效果。常见的代码阅读工具有,KScope、Source Navigator、Source Insight、lxr、Cscope等。

* KScope[1]是一款KDE桌面环境下的源代码阅读、浏览工具,自带了编辑功能。比较适合C语言编写的大型项目。KScope底层使用Cscope作为源代码的分析引擎。多数发行版都提供了KScope的安装包。
* “Source Navigator”是红帽子公司的,以GNU GPL发布,可从官方网站[2]下载使用。
* “Source Insight”目前只有Windows平台的,官方网站[3]。需要注册才能使用,或者从网上下载注册机生成注册码。在Linux下通过wine模拟虽然可以方便使用,但它毕竟是Windows平台的东西,并不能很自由的使用。
* lxr(linux cross reference)[4]为程序源代码建立索引数据库,利用perl脚本CGI动态生成包含源码的web页面,你可以用任何一种浏览器查阅。缺点是需要服务器支持,还有速度。
* “Cscope”[5]为终端下的代码阅读工具,资源消耗少,对那些忠于命令行的行操作的人,使用起来更加方便、灵活。这也是这篇文章推荐使用的一个重要原因。也有人把Cscope和Emasc绑定阅读源码。当然工具的选取,也取决于个人习惯。

Vim+Ctags+Cscope

cscope的工作需要vim、ctags的配合,它们都是基于命令行的。在Ubuntu下,用户只需执行“sudo apt-get install cscope cscope-indexer ctags vim”即可完成软件安装。下面只是给出了三种工具的常用方法,更多功能可查看man手册,或者官方文档。
Vim

vim被看作是专门为程序员打造的文本编辑器,其丰富的编辑命令都是常用的简单字符,用户很容易上手。vim可对180多种语言的语法高亮,对C语言自动缩进,真则表达式字符匹配查找,功能强大,并支持多个操作系统平台。关于vim的使用,这里不做讲解。vim中文文档[6]。
Ubuntu系统自带的vim,没有语法加亮功能。上面的安装命令已经更新了vim,在vim 配置文件 ~/.vimrc中 添加一行 “syntax on”,这样在vim中打开的源码就有了语法高亮显示。
vim自带了很多颜色主题,可以直接选取下面一行添加到vim配置文件当中,重新打开vim即可生效。

colorscheme elflord “我使用这个
colorscheme darkblue
colorscheme evening
colorscheme murphy
colorscheme torte
colorscheme desert

Ctags

在源代码根目录下执行 ctags -R 命令用来为程序源代码生成标签文件,其-r选项表示递归操作,同时为子目录也生成标签文件。vim利用生成的标签文件,可以进行相应检索、并在不同的文件C语言元素之间来回切换。

在vim中ctags的简单使用
1) 跳转到指定的函数进入vim后,用 “:tag func_name“ 跳到函数func_name处。使用tag命令时,可以使用TAB键进行匹配查找,继续按TAB键向下切换。
某个函数有多个定义时

:tag
跳到第一个定义处,优先跳转到当前文件
:tnext
跳到第一个
:tfirst
跳到前count个
:[count]tprevious
跳到后count个
:[count]tnext
跳到最后一个
:tlast
你也可以在所有tagname中选择:
:tselect tagname

如果想跳到包含block的标识符:“tag /block” 然后用TAB键来选择。这里’/’就是告诉vim ‘block’是一个语句块标签。
2)用“CTRL + ]“快捷键,跳转到光标所在函数标识符的定义处。
3)使用“CTRL + T”退回上层。 如果想在以write_开头的标识符中选择一下, :tselect /^write_ 这里,’^’表示开头,同理,’$’表示末尾。多个同名的标识符
Cscope

运行cscope命令,出现两个面板,上方是一个查找结果的显示面板,下方是一个查找条件指定面板。使用TAB键在两个面板间切换,也可使用上下左右方向件和翻页键在同一面板内贴换位置。选中显示面板的某个项,回车即可进入该文件,这是调用vim打开文件,这时就可以结合ctags使用了。当然也可以直接使用vim打开文件,结合ctags阅读源码。
使用前,必须现使用“cscope-indexer -r”命令递归生成索引信息文件。特殊情况下,还需要用户使用find命令,主动生成索引信息文件,并指定给cscope工具。 cscope提供了如下九种查询方式:

Find this C symbol:
#查找指定的C符号
Find this global definition:
#查找指定的全局定义
Find functions called by this function:
#查找指定函数调用的函数
Find functions calling this function:
#查找调用指定函数的函数
Find this text string:
#查找字符串
Change this text string:
#修改指定字符串
Find this egrep pattern:
#查找匹配字符
Find this file:
#查找指定文件
Find files #including this file:
#指定引用头文件进行查找

在对应某一项中输入查找条件,回车即可进行查询,并将结果显示在显示面板。
应用实例
下面以使用cscope阅读内核源代码为例:

$ wget http://kernel.org/pub/linux/kernel/v2.6/linux-2.6.27.6.tar.bz2
#从Linux内核官网下载内核源代码
$ tar xvfj linux-2.6.27.6.tar.bz2
#解压文件
$ cd linux-2.6.27.6
#进入源代码根目录
$ ctags -R
#递归生成标签文件
$ cscope-indexer -r
#递归生成索引信息文件
$ cscope
#使用cscope阅读源码

对于内核源代码也可以直接使用“make cscope”、“make tags”生成相应的索引信息、标签文件。
标签文件、索引信息文件只需要第一次或者代码发生变动时生成,以后使用直接运行cscope即可。
总结

要达到灵活应用的境界,还必须熟练结合其他工具,如grep、正则表达式等的使用。其中有很多技巧性的东西需要去不断总结、积累。

[1] http://kscope.sourceforge.net/
[2] http://sourcenav.sourceforge.net/
[3] http://www.sourceinsight.com/
[4] http://lxr.linux.no/
[5] http://cscope.sourceforge.net/
[6] http://vcd.gro.clinux.org/

写给像我一样的Linux内核初学者

--孔建军(Kongove.CN)
2008.11.12

首先,让我们来看几组令人振奋的数据。现在订阅Linux内核邮件列表[1],每天的邮件流量大概在500份左右;执行”grep “^P:” MAINTAINERS |sort -u|wc -l”,对内核子系统维护者进行统计,得到的结果是534人;从2007到2008年,平均每天有4300行代码添加到内核,有1800行代码从内核删 除,有1500行代码被修改[2];内核2.6.27发布以后,内核开发者使用脚本统计内核文件(包括空行、注释),已经超过 10,000,000,000行[3]。那么,有多少人读过内核源代码?又有多少人为内核开发做过贡献? ….

看到这些你或许有尝试一下的冲动,那就从现在开始疯狂的Hacking吧。下面是我自己学习中的一些感受,只是一些学方法或建议,希望能对你有所帮助。

首先,得有具备一些基础知识,如C语言基础、数据结构、微机原理、网络基本原理、操作系统、体系结构等,当然这也和你具体研究内容有关。下来就是习 惯英语,尽管有很多优秀的翻译资料供参考,尽管有很多出色的国内程序员活跃于邮件列表,但英语沟通是每个内核开发人员无法绕过的一个槛。英语里丰富的专业 词汇和广泛的使用群体,会成为沟通的最佳选择。如果你的英语自认为不是很好,那么我或许能给你一些建议。平时经常查阅man手册、 wikipedia[4]、FAQ等在线文档解决遇到的问题,参与合适的国外邮件列表,参与一些英文交友社区(如Facebook等),交笔友、IRC频 道及时聊天都是不错的方法。这些途径基本上都是和技术沾边的,当然也有很多其他方法提高英语水平。

内核的学习,先得对整个有一个全面的认识,了解各个核心部分的工作原理。因为Linux内核的工作是各个部分紧密配合完成的,各子系统之间的逻辑关 系比较复杂。这里建议读一些经典的书,如《Linux内核设计与实现》、《深入理解Linux内核(ULK)》,这样可以少走弯路。这些书都有中文翻译, 如果觉得直接看英文有些吃力,可以先看中文,或者中英文对照着看。这些书都有好几个版本,针对2.4、2.6内核的都有,可以先看针对2.4版本的,然后 再看针对2.6的。这里不得不提一本清华的教材《Linux操作系统原理与应用》,这本书非常适合入门,前面提到的ULK虽然涉及知识全面、讲的深入,但 对于初学者往往会陷入知识点的细节当中。这本教材把很多细枝末节省略掉,展现在读者面前的只有各部分的关键知识块。同时有大量图片说明,搞懂这些图,也就 理解了抽象的内部机制。其中每个章节都附带一个代码实例,通过调试这些程序可以加深对知识的理解,把抽象的东西实例化。你也可以在这本书作者维护的网站内 核之旅[5]中,找到更多的实例代码和相关资料。当然不排除有更好的入门教材,推荐这本只是我看过比较好的一本。

当你对内核已经有了一个初步的认识以后,你就需要围绕某一部分进行深入学习了。这样才能有深入的研究,从而做出实用的东西出来。比如网络设备驱动、 内存管理、文件系统、内核调度、中断异常、内核同步等。这里还是得有经典教材的指导,如果你想搞驱动开发,《Linux设备驱动》是必读的;如果你想深入 内核的网络部分,《Linux网络设计与实现》等等。

在学习内核过程中,源代码是最好的参考资料,你可以从Linux内核官网[6]下载最新的内核源码,也可以选取交老的版本分块阅读。内核源码的阅 读,难就难在整体的一个把握上,所以建议大家先选取局部核心数据结构、代码、文件进行分析,如task_struct结构体、fork.c文件等。在阅读 源码的同时,结合一些较小的实例程序练习,从而真正理解源码。在学习过程中如果遇到问题,最好现查看手头和网上的资料,实在解决不了,可以去邮件列表(中 文内核邮件列表[7])。

如果在学习内核的同时,你想尝试参与真正的Linux内核开发,请继续往下读。首先了解内核开发的大牛,搞清楚Linus Torvalds, Andrew Morton, David Miller等主要维护者的工作内容,如果你想作ARM方面的开发,你还得知道Russell King,你可以通过MAINTAINER文件了解更多子系统的维护者,当然不是全部要了解。其次你得理解内核版本的命名规则,以及如何制作和提交补丁。 从而熟悉内核开发的现状和流程,更加有效的跟踪Linux内核开发,同时坚定自己的信心。这样你的工作才能真正进入Linux内核当中。这里推荐一些资 料,内核文档(HOWTO、SubmittingPatches、SubmittingDrivers等,都可以从内核源码Documentation目 录下找到)、Linux内核测试指南[8]。

你得学会利用内核Bug的跟踪系统Bugzilla[9]工作,学会使用Git版本控制工具,理解树的概念。使用Git来跟踪内核的开发,关于 Git的使用请阅读Git的帮助手册[10]。Git工具、邮件列表等的使用,其实质是学会沟通,学会合作,学会高效工作。要时刻记着浪费别人的时间就是 谋财害命!

最后一点,也是最重要的一点,高度认真负责。这是参与开源社区最最关键的一点。

推荐另一篇必读的入门文章[11]。

[1] http://vger.kernel.org/vger-lists.html#linux-kernel
[2] http://www.youtube.com/watch?v=L2SED6sewRw
[3] http://www.heise-online.co.uk/open/Kernel-Log-More-than-10-million-lines-of-Linux-source-files--/news/111759
[4] http://en.wikipedia.org
[5] http://www.kerneltravel.net
[6] http://kernel.org
[7] http://wiki.zh-kernel.org/
[8] http://www.cnkernel.org/note/tester.tar.bz2.pdf (注意:是个压缩包,下载后把.pdf后缀去掉)
[9] http://bugzilla.kernel.org
[10] http://www.kernel.org/pub/software/scm/git/docs/
[11] http://xiyoulinux.cn/wiki/index.php?title=内核入门

祝各位兄弟姐妹光棍节快乐@_@

1111

送上这首经典老歌《单身情歌》--->  天下所有光棍 (Singles all over the world)

http://player.youku.com/player.php/sid/XMjEyMTQ3ODQ=/v.swf

光棍节短信语录

1. 问世间情为何物,我算是大彻大悟。感情上的事儿看来还真不能过于盲目。是你的挡不住,不是你的留也留不住。别人的老婆就是再好也不能轻易接触。有道是皮之不存毛将焉附,我要是over了还上哪儿去找我的贤内助?更何况人生短促,还有很多东西值得我们珍惜和呵护。爱情的光环固然眩目,也毕竟不是生命的全部。 Continue reading “祝各位兄弟姐妹光棍节快乐@_@”

秀一把我的校内狗狗

自从校内网增添N多应用以来,一直很少上,因为这些应用使网页打开很慢,而且上面很多的娱乐看着非常无聊,而且浪费时间。因此所有邀请一律不回应。

前几天看舍友在玩校内狗狗的游戏,发现这个游戏还挺有意思,而且非常简单,就是简单的点点鼠标。于是我也添加了这个应用,由于是flash,开得窗口太多时有点卡。你可以通过喂狗、溜狗等赚取骨头,然后用骨头可以买背景、座垫、狗窝,而且玩的时候还有一些敲门,呵呵这个得从编程的角度思考。才两三天,俺给小狗狗马特(Mutt)把所有“行头”都整齐全了,还咱了129公斤狗粮。

这个吗,也就是偶尔消遣一下 😉 从这里也可以看出web应用的发展很有前途~

5q-dog

A Foreign Friend–Lokesh Babu

几天前高伟在小组的新闻组里发帖,想邀请他一个印度朋友来实验室作客。这当然是好事了,时间定在本周末。今天早上准备去体能测试,跑去体育馆人太多了,而且学生证还在实验室。于是来到实验室,打开邮箱,才知道那位朋友半个小时候就要来了。赶紧组织大家大扫了一下卫生,不一会高伟等带着他到实验室了。于是跑去向他问好,”Welcome to Xiyou Linux Group  🙂 My name is Jianjun Kong.” 他告诉我们他的名字Lokesh,大家都坐下来开始聊。他在华为(南京)工作,原来在华为(深圳)做过几年Linux,很快又要到华为(上海)去工作。他主要作嵌入式Linux、手机操作系统、驱动程序开发方面的工作。这人很随和,开始大家首先建议他说英语慢一些,他很快明白。讲了很多关于他的工作和生活,我们也都提了好多问题,听起来就知道是个Linux狂热分子。于是我问:“Do you have a girl friend? and does she use Linux?”原来他有个女朋友,在美国做web服务器管理员。貌似他会一大堆语言,他比较喜欢QT、Python、C,不喜欢GTK和JAVA。毕业五年时间,也是大学接触Linux,学校有个Linux用户组(JLUG)。这人太牛了~当我们问他用什么发行版时,他说用自己的发行版。原来他自己编译内核,自己定制应用软件。。。。 我首先想到的就是包以来关系问题,不过听起来很新鲜,有点尝试的冲动 😉

原来他和高伟已经认识三年了,他们经常通过网络交流。高伟今天还专门请了个翻译(英语专业一同学),他还开玩笑说,以前跟高伟多是邮件交流觉得他英语不错,见面才发现高伟的英语有待进一步提高 😉 他还有一个很专业的相机,总是喜欢时不时拿出来拍照。我还给他提及了Herbert Xu和 Richard Stallman都来过我们实验室,他听了很惊讶。还给他介绍了哲思自由软件社区等和我们的交流,他也很感兴趣。最后我还搞笑了一把,把我用Python做得查询汉字拼音的工具,”送”给了他,他很高兴。

中午我们一块吃了个饭,高伟为他专门准备了些饺子,还有一些美味的菜,他都很喜欢。中间宋飞等都忙于用手机查找菜的名字,很是搞笑~ 🙂

最后他们打算下午带他去大唐芙蓉院,我还得体能测试于是没去,把他一直送到学校东门,结果没坐上车,于是又去前门坐600。其中我说了两句现在还不太确信是否合适的英语:

1. It’s the end of this road but the the beginning of our communication.

2. The buses want to leave you in our school like us.(等了好几趟320都人多,坐不上)

然后回去体测,呵呵,都高分通过~ 🙂

今天照的照片随后传到小组相册。

Linux 2.6 内核中新的锁机制 RCU(Read-Copy Update)

本文详细地介绍了 Linux 2.6 内核中新的锁机制 RCU(Read-Copy Update) 的实现机制,使用要求与典型应用。

一、 引言

众所周知,为了保护共享数据,需要一些同步机制,如自旋锁(spinlock),读写锁(rwlock),它们使用起来非常简单,而且是一种很有效 的同步机制,在UNIX系统和Linux系统中得到了广泛的使用。但是随着计算机硬件的快速发展,获得这种锁的开销相对于CPU的速度在成倍地增加,原因 很简单,CPU的速度与访问内存的速度差距越来越大,而这种锁使用了原子操作指令,它需要原子地访问内存,也就说获得锁的开销与访存速度相关,另外在大部 分非x86架构上获取锁使用了内存栅(Memory Barrier),这会导致处理器流水线停滞或刷新,因此它的开销相对于CPU速度而言就越来越大。表1数据证明了这一点。
表1 在700MHz奔腾III机器上一些操作的开销

表1是在700MHz的奔腾III机器上的基本操作的开销,在该机器上一个时钟周期能够执行两条整数指令。在1.8GHz的奔腾4机器上, 原子加1指令的开销要比700MHz的奔腾III机器慢75纳秒(ns),尽管CPU速度快两倍多。

这种锁机制的另一个问题在于其可扩展性,在多处理器系统上,可扩展性非常重要,否则根本无法发挥其性能。图1表明了Linux上各种锁的扩展性。
图 1 Linux的4种锁机制的扩展性
图 1  Linux的4种锁机制的扩展性

注:refcnt表示自旋锁与引用记数一起使用。

读写锁rwlock在两个CPU的情况下性能反倒比一个CPU的差,在四个CPU的情况下,refcnt的性能要高于rwlock,refcnt大 约是理论性能的45%,而rwlock是理论性能的39%,自旋缩spinlock的性能明显好于refcnt和rwlock,但它也只达到了理性性能的 57%,brlock(Big Reader Lock)性能可以线性扩展。Brlock是由Redhat的Ingo Molnar实现的一个高性能的rwlock,它适用于读特多而写特少的情况,读者获得brlock的开销很低,但写者获得锁的开销非常大,而且它只预定 义了几个锁,用户无法随便定义并使用这种锁,它也需要为每个CPU定义一个锁状态数组,因此这种锁并没有被作为rwlock的替代方案广泛使用,只是在一 些特别的地方使用到。

正是在这种背景下,一个高性能的锁机制RCU呼之欲出,它克服了以上锁的缺点,具有很好的扩展性,但是这种锁机制的使用范围比较窄,它只适用于读多写少的情况,如网络路由表的查询更新、设备状态表的维护、数据结构的延迟释放以及多径I/O设备的维护等。

RCU并不是新的锁机制,它只是对Linux内核而言是新的。早在二十世纪八十年代就有了这种机制,而且在生产系

统中使用了这种机制,但这种早期的实现并不太好,在二十世纪九十年代出现了一个比较高效的实现,而在linux中是在开发内核2.5.43中引入该技术的并正式包含在2.6内核中。


二、RCU的原理

RCU(Read-Copy Update),顾名思义就是读-拷贝修改,它是基于其原理命名的。对于被RCU保护的共享数据结构,读者不需要获得任何锁就可以访问它,但写者在访问它 时首先拷贝一个副本,然后对副本进行修改,最后使用一个回调(callback)机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据。这个时 机就是所有引用该数据的CPU都退出对共享数据的操作。

因此RCU实际上是一种改进的rwlock,读者几乎没有什么同步开销,它不需要锁,不使用原子指令,而且在除alpha的所有架构上也不需要内存 栅(Memory Barrier),因此不会导致锁竞争,内存延迟以及流水线停滞。不需要锁也使得使用更容易,因为死锁问题就不需要考虑了。写者的同步开销比较大,它需要 延迟数据结构的释放,复制被修改的数据结构,它也必须使用某种锁机制同步并行的其它写者的修改操作。读者必须提供一个信号给写者以便写者能够确定数据可以 被安全地释放或修改的时机。有一个专门的垃圾收集器来探测读者的信号,一旦所有的读者都已经发送信号告知它们都不在使用被RCU保护的数据结构,垃圾收集 器就调用回调函数完成最后的数据释放或修改操作。 RCU与rwlock的不同之处是:它既允许多个读者同时访问被保护的数据,又允许多个读者和多个写者同时访问被保护的数据(注意:是否可以有多个写者并 行访问取决于写者之间使用的同步机制),读者没有任何同步开销,而写者的同步开销则取决于使用的写者间同步机制。但RCU不能替代rwlock,因为如果 写比较多时,对读者的性能提高不能弥补写者导致的损失。

读者在访问被RCU保护的共享数据期间不能被阻塞,这是RCU机制得以实现的一个基本前提,也就说当读者在引用被RCU保护的共享数据期间,读者所 在的CPU不能发生上下文切换,spinlock和rwlock都需要这样的前提。写者在访问被RCU保护的共享数据时不需要和读者竞争任何锁,只有在有 多于一个写者的情况下需要获得某种锁以与其他写者同步。写者修改数据前首先拷贝一个被修改元素的副本,然后在副本上进行修改,修改完毕后它向垃圾回收器注 册一个回调函数以便在适当的时机执行真正的修改操作。等待适当时机的这一时期称为grace period,而CPU发生了上下文切换称为经历一个quiescent state,grace period就是所有CPU都经历一次quiescent state所需要的等待的时间。垃圾收集器就是在grace period之后调用写者注册的回调函数来完成真正的数据修改或数据释放操作的。

以下以链表元素删除为例详细说明这一过程。

写者要从链表中删除元素 B,它首先遍历该链表得到指向元素 B 的指针,然后修改元素 B 的前一个元素的 next 指针指向元素 B 的 next 指针指向的元素C,修改元素 B 的 next 指针指向的元素 C 的 prep 指针指向元素 B 的 prep指针指向的元素 A,在这期间可能有读者访问该链表,修改指针指向的操作是原子的,所以不需要同步,而元素 B 的指针并没有去修改,因为读者可能正在使用 B 元素来得到下一个或前一个元素。写者完成这些操作后注册一个回调函数以便在 grace period 之后删除元素 B,然后就认为已经完成删除操作。垃圾收集器在检测到所有的CPU不在引用该链表后,即所有的 CPU 已经经历了 quiescent state,grace period 已经过去后,就调用刚才写者注册的回调函数删除了元素 B。
图 2 使用 RCU 进行链表删除操作
图 2  使用 RCU 进行链表删除操作


三、RCU 实现机制 Continue reading “Linux 2.6 内核中新的锁机制 RCU(Read-Copy Update)”