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()类似,但它不分配页框,而是映射非连续内存区中已经分配的页框。