January 3, 2010

午后的声音。Spitz~

对音乐一直保持着先闻声再识人的习惯。往往听一首歌很久很久以后才会去翻歌手的名字找他的履历,至于记住相貌更是几个月以后的事情了。其实不止对歌手吧,对身边的普通人也是这样的。高中的时候花了两年才把全班同学的脸和名字对号入座,结果才保持了一年就又分开了,再到现在,就连名字也有些模糊了。不知道这算不算是我的生理缺陷。

Spitz算是唯一一个我先识人再闻声的。Spitz是一种小狗的名字,狐狸犬类,小型,分布于芬兰、德国、日本。日本银狐犬Japanese Spitz,毛是纯白色的,据说对主人特别地依赖但是对陌生人却神经质地多疑。当年瞎逛的时候见到一文谈到Spitz小犬的育养方法顺便说到了日本有只乐队就叫Spitz。突然就觉得好有趣。于是就。。。恩。

相比L团,Spitz绝对是支朴实无华的乐队,编曲风格也明亮得多,就连行事也低调得一塌糊涂,宣传活动也很少参加。用Vo.草野正宗的话说,“我们不像是一级的乐队”,“是像副食小吃性质的乐队”。虽然也是日本乐届的传奇人物,但就算是在鼎盛时期他们也不曾大红大紫到抽筋的地步,不过还是属于单曲初登场NO.1在公信榜上徘徊的人。

bf6df3da5fcc38c7b6fd48a9[3]

Spitz的歌大多是歌颂青春的。这个主题。。。的确有点老套,但是草野唱来却从没有感到过丝毫的恶俗。就算是俗套,也是完美的俗套,就像白雪公主和白马王子幸福地生活在一起的故事。听歌的时候总觉得有风的感觉,暖暖的,想要闭上眼睛和曲子一起慢慢地左右摇摆。应该叫陶醉吧。Spitz的歌最适合在有阳光的午后听,要走在有树荫的路上,晃着小包;地面有白色的线的话,就沿着一直走下去,看看可以到那里。都是些快乐的歌,轻轻的鼓点,轻轻的吉他声,仿佛他们对于生活从来都没有什么不满,一直都是很乐观的样子;偶尔有些忧伤,也是细细地藏着,不似樱花,倒有风一样的豁达。

草野的声音在众多歌神面前实在不算出众,有点沙,没有太多爆发力;但配上Spitz的音乐,却很神奇地扣人心弦。一曲过后,空白的静音处,总还有些什么东西在那里回荡着。没有震撼,却是动人的温柔。很多的温暖在里面。

给Spitz称号大多是日本民谣摇滚诗人团体。草野的歌词,即使在我这个日语半吊看来,也是美得一塌糊涂的。有人把草野比作歌坛的村上春树,是想赞叹草野的文采吧。但有时却不太能把握词的主线,有种“只是在表达某种情绪,其实什么也不想说”的感觉。草野自己也说过,写歌其实就是带一个小本子在身上想到的句子就随时写下来,再串在一起,再推敲斟酌许许,便就成了,之类的话。听到他这么说的时候觉得很放松,原来草野的歌诞生在停停走走断断续续的旅行中,那么当然,听的时候也可以轻松些,多多地感受它散发出的随意的灵性。

 folder[34] folder[43] folder[45] folder[47] folder[51]


对音乐的执着是好乐队的天性,也往往最能打动人心。Spitz也是,Laruku也是,还有Nirvana、H.I.M、Muse、Green Day等等无法穷举的各位们,个性里都有相当的“固执”在里面。队员间往往会分开好久各自写歌、练习或者汲取灵感,当然还有过私生活,攒到快要满溢的时候再聚到一起,摊开几十首甚至一百多首歌的谱子,边上放着预选录好的小样,然后举手争论再举手,挑不出了就再补,最后留下的10+首才成为下一活动阶段会发布的作品。有的做成单曲,有的收入专辑,流转到我们的手上和耳朵里。对于精致的音乐品质的追求,即使不能打榜也要坚持自己的想法的勇气,相比之下,真的足以让某些平均几个月就发一张专辑的所谓歌手无地自容。


当然,说些题外话,Major乐队的早期作品其实都是市场和他们自己的个性博弈下寻找均衡的产物,只有到后来渐渐大牌了Member们也渐渐想开了成熟了,才有了更多的资本和力量坚持自己的信念,这也就是常说的“听到了成熟的曲风”的时候。

snapshot20060520003516[3] snapshot20060520003549[9]

拿Spitz和L团比较的话,Laruku们多少有些王样的味道,live的时候也要在高高的舞台被膜拜;Spitz则更容易亲近些,有些邻家哥哥谈吉他唱歌的味道。很难说哪种更让人喜欢,事实上,Spitz多的是亲和力,而Laruku多的是控制力,总觉得听他们的歌思想很容易被控制XDD。对Spitz的喜欢可以放在心里一年一年慢慢地发酵,但是换到Laruku身上,其实狂热更多些,不在live上狂喊他们的名字,就实在无法想到其他方法可以表达得淋漓尽致。
好在两者,我都不偏不倚地喜欢着。

※推荐
推荐3首歌。一首做了我将近半年手机铃声Q殿也十分喜欢的[夜を駆ける]。一首质朴温暖单曲封面是只林中的小梅花鹿的[若葉]。最后一首,Spitz的名曲[Robinson],午后红茶CM曲,贴切到美妙的曲子、声音和香味。

 
 


这文章以前在BAIDU空间发过,带来了第一次来自搜索引擎的访问。今年有个很大的愿望就是把“亲爱的人们”写完,这个“宏大的目标”曾经因为BAIDU空间的废弃而一度搁置让我觉得可惜。有爱就要大声说出来。所以,还是从这篇对Spitz的爱开始,谈谈我心里那些无比亲爱的人们。

January 2, 2010

[论文笔记] A Developer's Guide to Silhouette Algorithms for Polygonal Models

Paper: Tobias Isenberg, Bert Freudenberg, Nick Halper, Stefan Schlechtweg, Thomas Strothotte, A Developer's Guide to Silhouette Algorithms for Polygonal Models, IEEE Computer Graphics and Applications, July 2003

本文是一篇就从3D Polygonal模型自动生成轮廓线问题展开的综述。算是读得挺细。断断续续一周有余。

问题描述:轮廓线,也就是绘画上说的线稿,用于勾勒物体的形状、阴影等,以区分于背景和其他物体。本文着眼于讨论从Polygonal模型自动生成轮廓线的诸多算法。
文中定义轮廓线为silhouette,分为counter、crease、border和self-intersection四种:counter是前景最外围的轮廓线,区分其于背景;crease指物体上的折皱等,如正方体的边;border针对非闭合的模型,指那些只与一个polygon相邻的边;self-intersection当一个模型的两个polygon相交时出现。轮廓线可以数学地定义为法线与视线相垂直的点集,如下图所示:
   tu015
但不幸的是,我们只有面的法线定义,而边上的点由于被多个面共享,其法线定义是暧昧不清的。因此,从计算的角度,轮廓线被定义为:模型上同时被正向和背向Polygon共享的边的集合(应该是指counter吧)。

轮廓线算法通常需解决两个主要的问题:检测当前视点的轮廓线集合和判断这些轮廓线的可见性。有以下几类算法:

  • Image Space Algorithms
    这类算法通常利用传统渲染技术中的图像缓冲区(如color、z-buffer、normal等),运用图像处理技术扩大其中的不连续性(边缘检测技术),以寻找轮廓线。其结果是一个与成像分辨率相关的像素矩阵。典型算法如:Saito和Takahashi的z-buffer、Hertzmann的normal-buffer以及Deussen和Strothotte在这基础上的应用pen-and-ink等。
    001  # z-buffer
    111  # z&normal-buffer
    这一类的方法易于实现,而且通常很快,并且能够自动地找到self-intersection类的轮廓线,也具有通用性和鲁棒性;但是,用户能够控制的参数很少,并且最后得到的轮廓线没有解析表述,这使得后续处理如风格化等很难展开。
    这类生成的轮廓线没有明确的边界,轮廓线上像素的灰度取决于缓冲区中边界特征的强度,而这也使得这一类的轮廓线无需烦恼线条锯齿的问题;另一个特征是其精确到像素,也就是说一些不足一像素的细节将会被隐藏,但这单从视觉的角度而言是不重要的。

  • Hybrid algorithms 
    这类算法通常需要在物体空间上作一些变换(位移等),然后也是利用渲染过程中的图像缓冲区(z-buffer)生成轮廓线。其结果与上一类方法相同,也是一个像素矩阵。典型算法如:Rustagi的stencil buffer算法,需四次渲染,每次将物体沿正负x/y轴移动一个像素,那么内部的像素就会有4个stencil值,而轮廓线上的像素则会有2-3个stencil值,而外部的像素则为0-1个stencil值,以此为区分,这种方法只能生成contour;
    Rossignac和Emmerik的算法基于z-buffer,通过将物体沿视线方向移动并调整wireframe的线条粗细,分别绘制wireframe和z-buffer来视线,这种方法对其他种类的轮廓线也有效;
    Raskar和Cohen的算法也基于z-buffer,先在白底上画正向面,这样z-buffer中就填充了正向面的深度值,再以轮廓线颜色画背向面,这样只有同时属于正向和背向面的轮廓边能够被画出来(深度值相等),这种方法可以画出指定等宽的轮廓线(通过在第二部放大背向面得到);
    其余还有在三角面片周围增加一圈边缘、基于暗色环境贴图的算法等等。
    221             331
      # Raskar和Cohen的back-front face方法                                 # Gooch的基于暗色环境贴图方法(很有艺术感)
    这类方法具有很高的可控性,也更具风格化。这类方法较上种较慢,需要做物体空间上的变换,但也是实时或准实时的。得到的轮廓线具有明确的边界,但也带来了锯齿走样的问题。并且由于是像素矩阵的表达方式,这些轮廓线只精确到像素,也不能很方便地适用于风格化后处理。此外,这类方法还存在一些由于z-buffer的精度而带来的数值问题。
  • Object space algorithms
    这类方法完全基于物体空间,提供对轮廓线的解析表述,可以方便地应用风格化后处理。这种方法不同于前两种,分轮廓线检测和可见性判断两步进行。

    轮廓边检测:
    - Trivial method  此类算法是轮廓边检测的基础算法,分两步:1. 将polygon分为正向和背向两类;2. 找出那些有且仅被一个正向面和一个背向面共享的边。此算法很简单、易于实现,对正交投影和透视投影都适用,也能找到所有的轮廓线,但是它没一帧都需要查看每一个面的朝向和每一条边,其算法复杂度与模型的复杂度线性相关,在没有硬件支持的情况下,其只能适用于简单模型的渲染。
    - Subpolygon silhouettes  此类算法主要是为了改善多边形轮廓的人工痕迹,使得轮廓线更逼近于真实物体。此算法是以多边形无限逼近的自由曲面为基础来考虑轮廓线的。计算顶点法线与视线间的点积,由于曲面本身法向的连续性,就会存在+/-符号的突变。对于那些两顶点点积符号不同的边,使用线性插值生成点积为零的点,并连成轮廓线。这种方法生成的轮廓线更自然,也更适用于后处理。如下图所示:
    447           556
    # subpolygon silhouette算法示意                                               # 算法结果示意
    - Precomputation methods  此类算法主要是为了改善检测算法的计算速度,通过事先做一些预处理的方式。如:
    Gooch等将模型面的法向量映射到一个高斯球上,并在球的中心放置与视平面平行的面。这样,面间共享的边就可以用法向量连起的弧线表示,而与球中心的面相交的弧线对应的边就是轮廓线。这种方法节省了每帧判断面朝向的时间,只需判断弧与面是否相交(弧本身是预处理的),如下图。为了减少相交判断的计算量,可以采用层级细分、或者将球映射到外切正方体的方法等;
    664              776
    # Gooch的高斯球算法示意                                                       # 算法结果示意
    Sander等人建立了一种存储边信息的层级搜索树(边储存在节点上),面片根据节点间的层级关系成类。每帧搜素完全背向和完全正向的面片类,相关的边则被剔除,剩余的则是轮廓边;
    另外,还有Hertzmann和Zorin、Pop等人基于对偶空间Dual Space的预处理方法(忒高深),以后再作讨论。
    - Stochastic method  此类算法以空间和时间的连续性为前提,先随机选取一些边并用Trial Method检测其中的轮廓边,之后检测这些已知轮廓边附近的边是否为轮廓边直至画出一条完整的轮廓线,下一帧也只检查上一帧附近的边是否轮廓边(短时间内模型不会变化太多)。这种方法速度较快,是实时的,但是只能检出完整轮廓边集中的一部分。

    线条可见性判断:
    可见性判断是计算机图形学的经典问题,一些传统的可见性判断方法(如z-buffer等)在此依旧适用。作者按照对象将这部分的算法分为Image、Object Space以及两者的混合体Hybid这三类。
    - Image space  这类算法基于z-buffer等可见性判断,像素级别精度。
    - Object space  这里有很多算法,不只解决线可见性的问题。作者在此处提到了一个有趣的概念QI(Quantitaitve Invisibility),即对一个点而言挡在它和视点之间的正向面的个数。QI为0的点可见,其他不可见。简单情况下,只有当边与轮廓线相交时QI值才会改变,如下图所示。边的初始QI值可通过光线追踪的方法以某一点为视点建立,根据其是否穿越轮廓线来判断QI值的增加或减少。Markosian、Herzmann和Zorin等人分别就QI做了算法速度和扩展应用方面的研究。这些算法均提供精确的可见性信息,但是其计算复杂度也相比Image space大些。
    88[3]    # 这是一条在物体后方的线
    - Hybrid  这类算法是前两者的结合,提供一种既快又有解析表示的解。如Northrup和Markosian的方法,其对每个三角面片和轮廓边着色,以z-buffer为基础渲染一张ID buffer。每一帧,ID buffer被读出,并搜罗其中所有出现了的轮廓边ID,以此为可见集合。Isenberg基于类似的原理给出了基于z-buffer的算法,并且由于z-buffer在数值上有时并不稳定,其主张将附近8邻加入决策。这类算法是Image space和Object space在速度和精度上的权衡。

新年

2009年的最后一个晚上。一夜浅眠。做了些梦。
早晨醒来的时候,头有些涨疼。但心里想着新年的第一天要是睡懒觉了这一年都会持续这种恶性循环的生活,于是就起来了。


去了趟邮局。确认它开着。搭讪了帅帅的温柔的邮局的包裹GG。买了3张4块5的邮票。


到实验室的时候房间的门还锁着,我兴奋地摸钱包开门,想着要做2010年出现在教一实验室的第一人。可下一分钟我就发现,我似乎把卡忘在了玻璃门的里面。真窘。辗转各邻居实验室搭讪工作中的GG们帮我开门,无果,这东西真是让人恼火地先进。遂去找老付,说实话我真不想新年见到的第一个熟人是那“关门”的。所以好在没有找到。不过遇见了老付的博士老婆和他的狗,于是我进了实验室。还是幸运的第一个。很开心。


坐下来给阿喵、Qjj、Cmm和我自己写明信片。10点钟的时候冯粮城来了。他是我2010年见到的第一个熟人(我和老付的老婆不熟,和他的狗更不熟)。


中午的时候去寄了卡片。我朝着邮筒说了三声拜托。拜托别寄丢快快地到她们手里保佑她们在海外一切顺利(邮筒君:我又不是土地庙XD)。


2010年,依旧许和去年一样的两个愿望。希望一切顺利。希望世界和平。

December 31, 2009

年末

前几天下了2009年第一场也是最后一场雪,虽然味道不怎么样。杭州是难得下雪的,也许是因的全球变暖,但暖冬也着实不是什么坏事。

今天是2009年的最后一天。午后。微暖。回实验室的路上,阳光有些刺眼。手边有一摞的事情要做,代码、综述、考试,还有头疼的Tomasulo,这个肚皮GG一晚上念叨了三次的名字。今晚怕是要出去的吧,最近也总是一轮接一轮的活动,静不下来。所以元旦过后,“要好好学习杜绝一切腐败活动”,是这么想的。

今年我从bb变成了SS,是正式的,不但签了卖身协议,也上了贼船,没有反悔的机会。当初下这个决定多少有点懒的成分在里面,拿金融危机找不到好工作做挡箭牌,想赖在学校里不走,因为想不好要做什么第一步应该往哪踏。其实现在觉得,读研本身就是一步,踏出去了就已经有很多其他的方向消失了。

当年看《Honey and Clover》,阿久和森田说“人生过于短暂,能打开的盒子是有限的”,就觉得心里面的某种恐惧突然清晰了起来。“是不是在我不知道的时候,真正想要选择的已经消失了”“不要塞给我不想要的啊,快要来不及了”之类的,总觉得时间紧迫,却不知往哪里走。有时候会做这样的梦,白天起来听小田爷爷的声音才觉得安心。老人们都说,迷茫总会过去的,只是迟早。

从去年开始做导致我毕业答辩没有拿优秀寒假只休息了一个礼拜暑假在北京杭州黄岩机场来回奔波了四趟吸了好多粉尘喝再多绿豆汤也没有用的科技馆项目总算结束了,虽然还有些余音袅袅不绝如缕。对于这种在短时间里反复接触的东西,事后只要一碰就觉得恶心,这怕也不是什么好习惯,可是厌恶之请由心而生,我如何改得。

报了明年522的托福,并不为的出国读书,这心思从我妈和我说一亲戚临死都没见到女儿最后一面说的最后一句话是“这辈子最后悔的事是让她女儿去了美国”我抖了抖想起阿四说他子欲养而亲不在的时候就没有了。原因很简单,托福贵,能迫使我学英语,学好英语好看论文、好找工作、好赚钱,也许还能出去短短地转一圈再回来。我十分有毅力地花了两个月按记忆曲线背完了本词汇书,可以小小地骄傲下,虽然不知道记住了多少。

接着,就是些零散的事情,记不太准确。心爱的游戏有些虎头蛇尾,不过总是做完了;体验了次LINUX,看了半个月的内核代码和文档,得了李善平的一句满意,我很满足;本月过马路的时候雨纷纷戴了帽子一不小心碰到了一辆四个轮子的车,撞断了人家的后视镜,相应地我的脚也断断续续地疼到了现在;惹了些不该惹的人,做了些不该做的事,是我不够镇静决断,一定不能让家里那群人知道不然又要说我;过年的时候莹mm要订婚了,祝福她;去年的新年愿望没有实现,今年还是接着许那两个,我要烦死上帝和老天爷直到他答应我。

末了,今年最爱的歌词,“季節は色を変えて幾度巡ろうとも この気持ちは枯れない 花のように揺らめいて 君を想う”,还是这句。
季节改变色彩已几度轮回,如花般摇曳的心情却从未枯萎,想念着你。

December 21, 2009

[专利申请] 发明专利相关信息收集

近日需写某专利,虽无甚意思,然相关知识仍可作傍身之用。遂整理如下,以待来日。

专利权,简称专利,分发明、实用新型或外观设计专利,需向国务院专利行政部门提出申请,授予申请者在规定的时间内对该项发明创造享有的专有权(其保护期按专利种类依次为二十年、十年、十年)。
授予专利权要求:1. 未公开、未出版;2. 创造性、优于同类传统技术;3. 实用性。

专利申请审批包括申请、初审、实质审查三个阶段。发明和实用新型专利需向专利局递交以下申请文件:请求书、说明书、说明书附图、权力要求书、说明书摘要及摘要附图(某些可不提交说明书附图和摘要附图)。
以下针对发明专利申请文件各部分展开说明:

  • 专利说明书摘要
    摘要是发明或实用新型说明书内容的简要概括。编写和公布摘要的主要目的是方便公众对专利文献进行检索,方便专业人员及时了解本行业的技术概况。其本身不具有法律效力。

    写法:

    1. 摘要应当写明发明的名称、所属技术领域、要解决的技术问题、主要技术特征和用途。不得有商业性宣传用语和过多的对发明创造优点的描述。
    2. 摘要中可以包含有最能说明发明创造技术特征的数字式或化学式。发明创造有附图的,应当指定并提交一幅最能说明发明创造技术特征的图,作为摘要附图。摘要附图应当画在专门的摘要附图表格上。
    3. 除非经审查员同意,摘要的文字部分一般不得超过300个字,摘要附图的大小和清晰度,应当保证在该图缩小到4×厘米时,仍能清楚地分辩出图中的细节。

  • 专利权利要求
    专利权的保护范围以被批准的权利要求内容为准。权利要求书是专门记载权利要求的文件,它由一项或多项权利要求组成。

    要求:
    1. 文字书写、纸张要求与说明书相同,也应当使用专利局的统一表格。
    2. 与说明书分开书写,单独编页。
    3. 使用的技术名词、术语应与说明书中一致。权利要求书中可以有化学式、数字式,但不能有插图。除绝对必要,不得引用说明书和附图,即不得用“如说明书所述的……”或“如图三所示的……”的方式撰写权利要求。为了表达清楚,权利要求书可以引用设备部件名称和附图标记。
    4. 权利要求应当说明发明的技术特征,清楚、简要地表达请求保护的范围。

    写法:
    1. 一项权利要求要用一句话表达,中间可以有逗号、顿号、分号,但不能有句号,以强调其意思的不可分割的单一性和独立性。
    2. 权利要求起始端不用书写发明名称,可以直接书写第1项独立权利要求,它的从属权利要求从序号2往下顺序排列。
    3. 独立权利要求一般应当分两部分撰写:前序部分、特征部分。
        前序部分:写明发明要求保护的主题名称和该项发明与最接近的现有技术共有的必要技术特征。
       特征部分:写明发明或者实用新型区别于现有技术的技术特征,这是权利要求的核心内容,这部分应紧接前序部分,用“其特征是……”或者“其特征在于……”等类似用语与上文联接。
        独立权利要求的前序部分和特征部分应当包含发明的全部必要的技术特征,共同构成一个完整的技术解决方案,同时限定发明或实用新型的保护范围。
    4. 从属权利要求也应分两部分撰写:引用部分、限定部分。
        引用部分:写明被引用的权利要求的编号及发明或实用新型主题名称,例如“权利要求1所述的间隙式胶合剂喷涂装置……”。
        限定部分:写明发明或者实用新型附加的技术特征。它们是对独立权利要求的补充,以及对引用部分的技术特征的进一步的限定。也应当以“其特征是……”或者“其特征在于……”等类似用语连接上文。
        从属权利要求的引用部分,只能引用排列在前的权利要求。同时引用两项以上权利要求时,只允许使用“或”连接,例如“根据权利要求1或2所述的高光催化活性二氧化钛的制备方法,其特征是:所述的无机酸为硝酸,pH为0.8-1.2。”,这样的权利要求称为多项从属权利要求。一项多项从属权利要求不能作为另一项从属权利要求的引用对象。
    5. 权利要求书应当以说明书为依据,其中的权利要求应当受说明书的支持,其提出的保护范围应当与说明书中公开的内容相适应。

  • 专利说明书
    公开发明的技术内容、支持权利要求的保护范围。

    要求:
    1. 应清楚、工整地写明发明的内容,使所属技术领域的普通专业人员能够根据此内容实施发明创造。说明书中不能隐瞒任何实质性的技术要求。

    2. 说明书中各部分内容,一般以单独段落进行阐述为好。
    3. 说明书中要保持用词的一致性。要使用该技术领域通用的名词和术语,不要使用行话,但是其以特定意义作为定义使用时,不在此限。
    4. 使用国家计量部门规定的国际通用计量单位。
    5. 说明书中可以有化学式、数学式。说明书附图,应附在说明书之后。
    6. 在说明书的题目和正文中,不能使用商业性宣传用语,例如:“最新式的……”,“世界名牌……”。不能使用不确切的语言,例如:“相当轻的……”,“……左右”等。也不允许使用以地点、人名等命名的名词,例如“陆氏工具”、“孝感麻糖”。商标、产品广告、服务标志等也不允许在说明书中出现。说明书中不允许有对他人或他人的发明创造加以诽谤或有意贬低的内容。
    7. 涉及外文技术文献或无统一译名的技术名词时,要在译文后注明原文。

    写法:
    专利法实施细则第18条规定了说明书8个部分的内容及行文的顺序,除发明名称外,一般情况下,各部分应当至少使用一个自然段,但不用加序号和列标题。写论文一般以理论为主,以实验装置和产品为辅,重点说明一种理论的成立,而专利说明书是以具体的技术方案为主,理论说明可有可无。
    1. 发明或实用新型的名称。名称应当与请求书中名称一致,还应尽量反映出发明对象的用途或应用领域。25字内。顶部居中。
    2. 技术领域。一般用一句话说明该发明所属的特定技术领域,或所应用的特定技术领域。可采用“本发明涉及一种……” 的形式。
    3. 背景技术。写明对发明的理解、检索、审查有参考作用的现有技术,并且引证反应这些背景技术的文件。这些现有技术中应包括相近和最接近的已有技术方案,详细分析它的技术特征,客观指出存在的问题或不足。
    4. 发明内容。包括:
        发明的目的,即该发明要解决的技术课题和直接结果。一般采用“本发明的目的在于避免(克服论述……中的不足(缺点)而提供一种…产品(方法)”的描述形式。
        技术方案,应清楚、简明,使所属技术领域的普通技术人员能够理解。写法可采用“本发明的目的是通过如下措施来达到…”语句开始,紧接着用与独立权利要求相一致的措辞,将发明的全部必要技术特征写出。
        优点、特点或积极效果,可以从方法或者产品的性能、成本、效率、使用寿命以及方便安全可靠等诸方面进行比较。
    5. 附图说明。如果必须用图来帮助说明发明创造技术内容时,应有附图并对每一幅图作介绍性说明,首先简要说明附图的编号和名称,例如:“图1是本发明的俯视图”、“图2是本发明A-A的剖视图”,接着可以在此逐一说明附图中的每个标注的符号,或结合附图对发明的技术特征进一步阐述。
    6. 具体实施方式。这一部分应详细描述申请人认为实施发明的最好方式,并将其作为一件典型实例,列出与发明要点相关的参数与条件。必要时,可以列举多个典型、实例,有附图的应对照附图加以说明,关键要支持权利要求,而且要详细、具体。

Reference:
某关于如何撰写专利的PPT http://www.docin.com/p-7508281.html
成文专利申请书参考 http://www.docin.com/p-2828616.html

December 15, 2009

[源码笔记] Linux内核内存检测工具Kmemcheck浅读

Linux内核2.6.31版本发布于2009年9月9日(真是个吉利的日子),其中新加入了两个内核内存管理方面的新工具Kmemcheck和Kmemleak。Kmemcheck工作于内核态,用于检测未初始化等内存非法读写访问并发出警告(类似的编程辅助工具Valgrind也可用于内存检测,但其工作于用户态,对内核态进程无能)。但是由于Kmemcheck会大大地影响内核工作的速度,并消耗较近两倍的内存使用,其将只作为Linux内核的一个调试工具,需要手动开启。

这对于内核开发(如设备驱动程序)者而言,是十分有用的。因为编程习惯或者对未初始化内存的不经意使用(C语言甚至允许访问任意的内存地址),非常可能导致一些难以检查的错误,有时还可能导致系统一直处于无响应状态。Kmemcheck能够帮助定位大多数内存错误的上下文,虽然目前它只支持x86平台,且仍在不断改进中。

1. 实现思路

Kmemcheck记录跟踪内存中每一位的内存状态,并于每次访问时检查其状态是否合法,若判断为非法访问,则给出警告信息。

1.1 分配
当Kmemcheck被开启时,每一块动态申请并要求跟踪的核态内存A都将有一块和其大小相同的影子内存B(其地址记录于每个页描述符的shadow字段中),用于记录A中每个字节的内存状态,这是判断内存访问是否合法的依据:

KMEMCHECK_SHADOW_UNALLOCATED 未分配的(在SLAB中,新分配的slab页面中没有被分配object的部分会被设置成此状态)
KMEMCHECK_SHADOW_UNINITIALIZED 未初始化的(一般情况下,新分配的页面都会被设置成此状态)
KMEMCHECK_SHADOW_FREED 释放的(在SLAB中,当object被释放后,其所占用的内存会被设置成此状态)
KMEMCHECK_SHADOW_INITIALIZED 初始化的(对它的访问是正确的)

以上4中状态,前3种均为非法访问,Kmemcheck会给出相应的警告。

Kmemcheck在页表项的页面属性新定义了一个_PAGE_HIDDEN标志位,在slab_cache中添加SLAB_NOTRACK属性,在GFP中添加__GFP_NOTRACK属性。
当分配内存时,A对应页表项中的_PAGE_PRESENT标志位被清零(表示该页不存在,引起一次缺页中断),并置位_PAGE_HIDDEN标志位以区别于真正的缺页中断;B则置位了__GFP_NOTRACK使得其自身不被Kmemcheck跟踪,并且B中的每个字节都会被标志位uninitialized。另外,为了系统的正常运行,关键的内核代买也被SLAB_NOTRACK和__GFP_NOTRACK保护起来,不受Kmemcheck跟踪。

1.2 操作
当对内存读写操作发生时,被Kmemcheck跟踪的内存将发生一次缺页中断,调用do_page_fault(),Kmemcheck在其中置入的钩子函数就会起作用。如果是读操作,则检查对应shadow中的状态是否为initialized,若否,则启动报错程序;如果是写操作,则将对应shadow置为initialized。
检查完成之后,将这些页的_PAGE_PRESENT置位为“存在”,使其能够返回完成原来的操作;并置位TF(X86_EFLAGS_TF)标志位,使得CPU在执行下一条指令进入单步调试状态,并在之后调用的do_debug()中将以上访问页的_PAGE_PRESENT重新置为“不存在”。那么,当下次读写访问到来时,又可以进入Kmencheck检查。

1.3 释放
除了释放跟踪内存A和shadow,还需将其标记为“存在”和“不隐藏”。

2. 技术细节

2.1 内存管理
Kmemcheck检测内存的功能主要通过对照与跟踪内存紧密相关的影子内存实现。影子内存随着跟踪内存分配而分配并初始化,也随着跟踪内存的释放而释放。Kmemcheck中与内存管理相关的核心函数主要位于mm/kmemcheck.c中,涉及跟踪内存的初始化、影子内存的分配和初始化等。

kmemcheck_alloc_shadow(*page, order, flags, node) 调用alloc_pages_node()分配相同大小的影子内存,其“不被跟踪”(__GFP_NOTRACK);
将影子页的地址赋予每个对应跟踪页描述符中的shadow字段;
将每个跟踪页置位“不存在”(~_PAGE_PRESENT)和“隐藏”(_PAGE_HIDDEN)。
kmemcheck_free_shadow(*page, order) 将每个跟踪页置位“存在”(_PAGE_PRESENT)和“不隐藏”(~_PAGE_HIDDEN);
将每个跟踪页的shadow字段置为NULL;
调用__free_pages()释放对应的影子内存。
kmemcheck_slab_alloc(*kmem_cache, gfpflags, *object, size) 调用kmemcheck_mark_uninitialized()将跟踪对象所对应的影子内存置位“未初始化”。
(Kmemcheck允许被跟踪页中的部分对象为不被跟踪的,这通过将其影子置位为“初始化”来实现)
kmemcheck_slab_free(*kmem_cache, *object, size) 调用kmemcheck_mark_freed()将跟踪对象所对应的影子内存置位为“已释放”。
kmemcheck_pagealloc_alloc(*page, order, gfpflags) 调用kmemcheck_alloc_shadow()分配影子内存并标记跟踪内存;
若此内存需被跟踪,则置位其影子为“未初始化”;否则为“初始化”。

在SLAB/SLUB等通用或专用对象分配机制中:
1) kmemcheck_alloc_shadow()被插入到allocate_slab()的新页成功分配之后,分配影子并标识跟踪页(allocate_slab()负责在slab不够用时添加新页并构造新slab)。此后,若slab已被构造函数 初始化则将影子置为“未初始化”,否则置为“未分配”;
2) kmemcheck_slab_alloc()被插入到slab_alloc()的新object成功分配之后,将对应影子置为“未初始化”(slab_alloc()负责为申请的通用或专用对象申请空间);
3) kmemcheck_slab_free()被插入到slab_free()的object释放之后,将对应影子置为“已释放”(slab_free()负责释放已申请的通过或专用对象);
4) kmemcheck_free_shadow()被插入到__free_slab()的slab被释放后,将对应影子释放(__free_slab()负责释放多余空闲的slab)。

在连续页框分配机制中:
1) kmemcheck_pagealloc_alloc()被插入到__alloc_pages_slowpath()连续页分配成功后,分配影子、标识跟踪页并置位影子状态(__alloc_pages_slowpath()负责从全局内存池中分配新页);
2) kmemcheck_free_shadow()被插入到__free_pages_ok()和free_hot_cold_page()等页被释放后,将对应影子释放。

在非连续内存区分配机制中(如vmalloc),由于其页框也是通过调用alloc_page()来分配的,因此也可受到Kmemcheck的监控。

那么,通过这些置入内存管理函数中的钩子函数,当一个动态内存申请函数(如kmalloc)被调用时(分配标志中不包含__GFP_NOTRACK,__GFP_HIGHMEM,对于SLAB内存,cache创建时标志中不包含SLAB_NOTRACK),影子页面就被创建、初始化,而跟踪页面被置位“不存在”和“隐藏”。这样,Kmemcheck就能够结合缺页中断、单步调试等技术跟踪和检查这些内存访问的合法性。当其对应的释放函数(如kfree)被调用时,相应的影子页面被释放,而跟踪页面被置位“存在”和“不隐藏”,使得Kmemcheck停止工作。

2.2 跟踪机制实现
前文提到Kmemcheck通过不断交替标志跟踪页“存在”(kmemcheck_show())和“不存在”(kmemcheck_hide()),使得其对页面的跟踪能始终持续到其被释放。出于进程的并发性、安全性等考虑,Kmemcheck通过kmemcheck_context中的balance字段来同步kmemcheck_show和kmemcheck_hide这一对操作,这是使得Kmemcheck跟踪机制得以顺利工作的关键。核心代码位于/arch/x86/mm/kmemcheck/kmemcheck.c中。

kmemcheck_show_all() 将每个地址对应的页置为“存在”,并刷新TLB
kmemcheck_hide_all() 将每个地址对应的页置为“不存在”,并刷新TLB
kmemcheck_show(*regs) 调用kmemcheck_show_all();
balance+1;
置位TF(X86_EFLAGS_TF)标志位,开启单步调试。
kmemcheck_hide(*regs) 调用kmemcheck_hide_all();
balance-1,并清空当前跟踪地址;
复位TF标志位,关闭单步调试。


缺页异常处理函数do_page_fault()在大多数情况下只对用户态内存和核态非连续内存区调用,负责为属于进程地址空间但还尚未分配物理页框的页分配物理页框,并交换至物理内存中使得进程可以正常访问(有编程错误而导致的缺页异常不在讨论范围内)。在核态分支中,kmemcheck_fault()调用被插入到正常缺页处理函数vmalloc_fault()之后,包括访问合法性的检查和kmemcheck_show()的调用。之所以选择这个位置,是因为高地址的跟踪页可能被置换出物理内存,插在正常缺页处理之前会引起页面交换的混乱,访问到不相称的内存。

在以上的操作中,为了完成缺页中断使得正常访问得以进行,跟踪页被置为“存在”,那么在后续的操作中,其必须被再次置为“不存在”,才能让Kmemcheck的内存检查得以重复实现。在x86体系结构中,正常情况下指令是乱序执行的。为了避免在重置标志位前跟踪页中的其他地址被再次访问,Kmemcheck在置位“存在”之时开启了CPU的单步调试。这样,CPU就陷入了调试陷阱(Debug Trap),在处理函数do_debug()中,kmemcheck_trap()被调用,其在检查balance值的合法性后,调用kmemcheck_hide()完成单次检测操作标识符的复位。

2.3 读写合法检查
Kmemcheck中的读写合法检查通过对照影子页中对应地址的内存状态值来实现,其核心函数为kmemcheck_access(),位于/arch/x86/mm/kmemcheck/kmemcheck.c中。其流程大致如下:
       a. 检查本次kmemcheck_access的调用合法性(是否与另一kmemcheck_access调用冲突);
       b. 调用kmemcheck_opcode_decode解码指令;
       c. 根据操作码执行不同的合法性检查:读指令执行kmemcheck_read,写指令执行kmemcheck_write,其余还包括一些特殊指令如movs、cmps等,这些特殊指令目前还不甚完善,故不作讨论。

kmemcheck_read_strict(*reg, addr, size) 此函数检查不超过页边界的读操作。
检查对应影子中记录的内存状态是否合法;
如有错,则记录错误信息、出错上下文等;
标记本次检查过的内存影子为“初始化”,避免二次报错。
kmemcheck_read(*reg, addr, size) 此函数通过将需要检查的地址段按页切割,并调用kmemcheck_read_strict()检查其合法性
kmemcheck_write_strict(*reg, addr, size) 此函数处理不超过页边界的写操作,将其对应影子标识为“初始化”。
kmemcheck_write(*reg, addr, size) 此函数通过将需要检查的地址段按页切割,并调用kmemcheck_write_strict()处理。


2.4 错误处理报告
对于捕获到的内存非法读写,Kmemcheck调用kmemcheck_error_save()将其存储在结构体kmemcheck_error的形式存放在一个循环缓冲区error_fifo中,包括警告类型、引发警告的内存地址及其访问长度、各寄存器的值和stack trace,同时还将访问地址附近的跟踪页和其对应影子页拷贝保存在记录中。此后,将预先设置好的一个tasklet(负责错误处理)插入到当前CPU的tasklet队列中,然后去触发一个软中断。这样,当注册的tasklet被调度执行时,会将循环缓冲区中所有的记录都打印出来。其代码位于/arch/x86/mm/kmemcheck/error.c中。

作为一个新加入内核的补丁工具,Kmemcheck存在很多不完善的地方,比如movs指令所触发的kmemcheck_copy()操作虽然包含源地址和目标地址两个操作却只能给出一次警告等等。因此,Kmemcheck的代码中还嵌有很多自身bug的发现和记录代码,与捕获错误共用同一套报告方法和数据结构。

2.5 内核选项配置
由于Kmemcheck启用的代价很高(需要近2倍的内存并降低运行速度),它被严格地限定为linux内核的debug工具,在普通模式下是默认不被开启的。只有当程序员需要调试内核代码时,才可手动开启。
下面例举了重新编译内核时选项中针对 Kmemcheck 的配置选项,以及它们应该被设置的值(或推荐值):

CONFIG_CC_OPTIMIZE_FOR_SIZE=n 禁止gcc对数据长度进行优化。
例如在32位的机器中,为了提高内存访问速度,gcc 可能会将一些16位的数据访问提升至32位(真正使用时会舍弃高16位),这样kmemcheck 可能就会对高16位中数据内容访问发出警告(这种警告成为伪警告)。这个选项是配置kmemcheck的前提,否则kmemcheck不会出现在配置选项中。
默认是y,在选项"General setup"中。
CONFIG_SLAB=y or CONFIG_SLUB=y 使用slab 或者slub 机制。
默认是CONFIG_SLUB=y,在选项"General setup" 中。
CONFIG_FUNCTION_TRACER=n 防止嵌套的页面异常。
默认是n,在选项"General setup"中。
CONFIG_DEBUG_PAGEALLOC=n 关闭页面分配调试功能。
默认是 n,在选项"Kernel hacking"中。
CONFIG_DEBUG_INFO=y (推荐值) 打开内核调试信息,方便内核调试。
在选项"Kernel hacking" 中。
CONFIG_KMEMCHECK=y (必然推荐值) 决定内核是否包含kmemcheck 功能。
在选项"Kernel hacking" 中。
CONFIG_KMEMCHECK_[DISABLED|ENABLED| ONESHOT]_BY_DEFAULT 定义Kmemcheck 在机器启动时的状态。
DISABLED为不启动,ENABLED为启动但它会降低启动的速度,ONESHOT 将在第一次警告之后关闭Kmemcheck功能。Kmemcheck的状态是可以在系统启动后通过修改/proc/sys/kernel/kmemcheck的值来进行动态调整的。
默认是ENABLED,在选项"Kernel hacking" 中。
CONFIG_KMEMCHECK_QUEUE_SIZE 出错循环缓冲区大小,默认是64,即最多一次可以保存64条警告记录,推荐保留默认值。
CONFIG_KMEMCHECK_SHADOW_COPY_SHIFT 当发生警告时,保存下来的内存数据大小,默认是5,即可以保存32字节的数据,推荐保留默认值。
CONFIG_KMEMCHECK_PARTIAL_OK 为了解决gcc对数据长度的优化,默认是y,推荐保留默认值。
CONFIG_KMEMCHECK_BITOPS_OK 针对位域的访问,默认是n,推荐保留默认值(如果需要用到Kmemcheck来对位域的访问进行跟踪,推荐使用其提供的Bitfield annotations)。

 

3. 验证实验

为了验证Kmemcheck的性能,我们编写了几种核态下非法访问内存的例子,并在linux2.6.31版本下开启Kmemcheck功能调试。

系统环境:
WindowXP sp3 + VMware® Workstation 7.0 + Fedora 12 (v2.6.31) + gcc 4.4.2

3.1 alloc_page
先用alloc_pages分配了两个页面大小的内存,然后在未初始化的情况下对其中的内容进行访问。Kmemcheck给出内存未初始化警告信息(即KMEMCHECK_SHADOW_UNINITIALIZED类型的错误信息)。

部分代码示意:
  code01_thumb16

Kmemcheck给出的警告信息:
 re01[5]
其中,A行给出非法访问的内存地址和错误类型;
B行给出了跟踪页中访问地址附近的32个字节;
C行给出了对应影子页上这32个字节的内存状态,u表示KMEMCHECK_SHADOW_UNINITIALIZED,a表示KMEMCHECK_SHADOW_UNALLOCATED,f表示KMEMCHECK_SHADOW_FREED;
D行指向非法访问内存所在的位置;
E行以下记录的是当时stack trace和寄存器信息,其中EIP记录引发警告的指令地址。

3.2 slab
先创建了一个slab cache,然后对slab中未分配的对象进行访问。Kmemcheck会发出内存未分配警告信息(即KMEMCHECK_SHADOW_UNALLOCATED类型的错误信息)。

部分代码示意:
 code02_thumb2

Kmemcheck给出的警告信息:
 re02_thumb2

3.3 kmalloc
先用kmalloc分配内存,完毕后释放该内存,然后再去访问被释放了的内存空间。Kmemcheck给出访问内存已释放警告信息(即 KMEMCHECK_SHADOW_FREED 类型的错误信息)。

部分代码示意:
 code03_thumb2

Kmemcheck给出的警告信息:
 re03[4]

4. 总结

Kmemcheck作为开源的测试工具,其性能是完全可以接受的。它能够检测出对动态分配的核态的未初始化、未分配和已释放内存的非法访问,但偶尔也会给出伪警告信息。虽然目前,Kmemcheck还在不断完善中,相关指令的检测处理还不全面,对其他体系平台的支撑还有待探究。并且由于其与内存、调度、进程管理、中断处理等其他子系统的关系非常紧密,Kmemcheck的稳定性受到很多外来因素的影响。但是无疑,它的检测过程显得十分大胆、有趣,而且有效。

最后,引用一名知名的linux内核开发者Ingo Molnár对Kmemcheck的评价:
it should also be made clear that not only does kmemcheck consume half of the RAM to do byte granular tracking of the other half of RAM, it's also slow, very slow, because almost every kernel-space instruction will generate a pagefault and then it will be single-stepped and it takes a debug fault as well. That's of course totally crazy, but that's also OK and it's what makes the feature so interesting and powerful.

5. 参考资料

来自IBM Linux技术文档库的文章《Linux 内核内存检测工具 - Kmemcheck》及相关
源码来源:http://lxr.linux.no/ (2.6.31)
《深入理解LINUX内核》一书

December 8, 2009

[读书笔记] Linux内核动态内存分配

Book:Daniel P. Bovet, Marco Cesati, Understanding the Linux Kernel(中译版,陈莉君等),  O'Reilly

在Linux中内核获取动态内存的方式相对进程是相当直接了当的。作为操作系统中优先级最高的成分,其内存请求不会被推迟,也不会插入任何针对编程错误的保护措施。其内存分配按其对象大致可分为三类:1. 连续页框;2. 专用或通用对象;3. 非连续的内存区。如果所请求的内存区得以满足,将返回一个页描述符地址或线性地址;否则,返回NULL。

第一类:连续页框【Buddy Allocator】

Buddy算法将内存划分为2的幂次方个分区,并使用best-fit方法来分配内存请求。当用户释放内存时,就会检查buddy块,查看其相邻的内存块是否也已经被释放。如果是的话,将合并内存块以最小化内存碎片。

__rmqueue(*zone, order):此函数用于在管理区zone中找到一个适配当前请求大小为2^order的最小空闲块。
在管理区描述符中维护着一个类型为free_area的数组,其第k个元素标识所有大小为2^k的空闲块(其中free_area中的free_list双向循环链表通过lru字段链接这些空闲块对应的起始页框页描述符,nr_free记录这些空闲块的个数)。__rmqueue()函数从所请求order的链表开始,扫描每个可用块链表:
       若找到合适的空闲块,则从链表中删除它,并减少此free_area中的nr_free值,后执行expand函数,将找到块中多出的部分切割大小为2的幂次的块,插入相应的free_area中;若直到循环结束还找不到(free_area全空),则返回NULL。

buffered_rmqueue():此函数应用“每CPU”页框高速缓存per_cpu_pages,当只需要分配一个页(order=0)时,首先在缓存中查找,如果缓存中已经没有预先分配好的内存页了,则从内存中取一些页放在缓存中,再从缓存中分配(若缓存中页框个数高过上界,则释放一些到Buddy系统中);对于大于2个页的情况,则直接调用__rmqueue()进行分配。

__alloc_pages(gfp_mask, order, *zonelist):此函数是Buddy Allocator的核心。gfp_mask标识指明如何寻找空闲页,如要求页框处于ZONE_DMA内、一次内存分配失败将不会产生警告信息等;order传入请求分配的内存大小;*zonelist按优先序列描述了适于内存分配的内存管理区。__alloc_pages函数循环扫描zonelist,若内存尚有盈余,调用buffered_rmqueue()进行分配;否则,调用以下策略充盈内存后进行分配:1. 回收页框;2. 消耗为内存不足预留的页;3. 阻塞当前进程;4. 杀死另外的进程释放一些内存。当然没有办法的办法就是返回NULL提示调用者内存分配失败。
常用的alloc_pages宏通过依次调用__alloc_pages实现。
__get_free_pages也通过调用alloc_pages实现,但它返回的是页的线性地址。

第二类:专用或通用对象【SLAB/SLUB/SLOB Allocator】

SLAB算法是面向对象的。内核对对象的初始化是十分耗时的,尤其对于小通用对象,甚至超过了对其进行分配和释放内存所需的时间。那么当它被析构时,就不应该将内存释放回一个全局的内存池,而是将内存保持为针对特定目的而初始化的状态,这样后续的内存分配就不需要再执行初始化函数了。SLAB算法就是基于以上思想提出的。下图给出了SLAB的组织结构。
      figure1[11]  
kmem_cache定义了一个要管理的给定大小的对象池;
其包含了一个slab列表,有三种slab:slab_full(完全分配)、salbs_partial(部分分配)、slabs_empty(空);
每一个slab列表都指向一些slab,slab通常是一段连续的内存块,被分配给多个object。
当slab不足时,需再分配内存初始化为slab;当空闲slab过多时,则释放一些内存到全局内存池中。

SLUB在保留SLAB基本思想的同时, 简化了kmem_cache,slab 等相关的管理数据结构,摒弃了SLAB 分配器中众多的队列概念,并针对多处理器、NUMA 系统进行优化,从而提高了性能和可扩展性并降低了内存的浪费;
SLOB则针对嵌入式系统,是内存受限系统中的一个SLAB 缓存实现。为保证内核模块的无缝迁移,其接口API函数与SLAB无异。

kmem_cache_alloc(*cachep, flags):此函数从一个命名的缓存中分配一个对象。若当前缓存为空,则调用kmem_cache_file向缓存中填充本地高速缓存并获得一个空闲对象。flags字段标识内存分配的具体细节,如为用户分配内存、从高端内存中分配等。

kmem_cache_zalloc(*cachep, flags):此函数与kmem_cache_alloc类似,但它在对象返回前对其进行清除操作。

kmalloc(size, flags):此函数是内核中最常用的内存管理函数。如果对存储区的请求不频繁,就用一组普通高速缓存来处理,无需创建新slab缓存。kmalloc没有为要从中分配对象的某个slab 缓存命名,而是循环遍历可用缓存来查找可以满足大小限制的缓存。找到之后,就调用__cache_alloc(kmem_cache_alloc的核心)分配一个对象。

第三类:非连续的内存区

当对内存区的请求不是很频繁,那么通过连续的线性地址访问非连续的页框这种分配方式就会十分有意义。这种做法避免了外碎片,但必须打乱内核页表。此外,非连续内存区还提供了另一种是用高端内存页框的方法。

get_vm_area(size, flags):此函数在线性地址VMALLOC_START和VMALLOC_END之间查找一个空闲的线性地址空间。它首先调用kmalloc()为非连续内存区对应的vm_struct类型描述符分配一个内存区;再通扫描纪录所有vm_struct的vmlist链表来查找一块满足(size+安全区间)大小要求的线性地址空间(每个vm_struct都记录其占据的VMALLOC可用线性地址空间,那么它们之间的空洞就是当前可用的)。如果成功,则返回该描述符地址,否则释放该描述符,返回NULL。

vmalloc(size):此函数为内核分配一个非连续内存区,并将其映射到一个连续的线性地址空间。它首先调用gei_vm_area创建一个新的描述符,并返回分配给这个内存区的线性地址;然后调用kmalloc()分配一组连续页框用于存储一个页描述符指针数组,并调用memset()初始化这些指针为NULL;接着重复nr_page次调用alloc_page()分配非连续的页框,并将其页描述符指针存入上一步分配好的数组area->pages中去;最后调用map_vm_area()修改内核页表,为此非连续内存区的每个页框建立页表层级目录,最后在页表中标识所其对应的线性地址,这些线性地址取自第一步get_vm_area找到的区域。
vmalloc_32()函数与vmalloc()类似,但它只从ZONE_NORMAL和ZONE_DMA内存管理区中分配页框,不使用高端内存页框。
2.6版本内核中的vmap()也与vmalloc()类似,但它不分配页框,而是映射非连续内存区中已经分配的页框。