shell log

以前写 shell 做 log 时都比较傻大黑粗，今天看到 Yii 的 Pull Request #2124 时发现他的写法不错

install_memcache > ~/memcache.log || ( echo "=== MEMCACHE BUILD FAILED ==="; cat ~/memcache.log )

OS X 10.6 with SSD 下 brew install git 失败的问题

几日前把 MB133 的光驱拆掉，在光驱位换上了 SSD 。结果在 brew install git 时发现提示以下错误。

mv: cannot resolve index.html: /private/tmp/homebrew-UNKNOWN-1.7.4.4-QvlZ/git.html

上 homebrew issues 里一查，看到有人和我同样错误，也是因为安装了第二块 SSD 的问题。 https://github.com/mxcl/homebrew/issues/5113

只要按以下操作重新设置 homebrew 的临时目录即可解决。

mkdir $HOME/tmp
export HOMEBREW_TEMP=$HOME/tmp

原因很简单，通过 brew doctor 就能看到，OS X 现在不支持跨巻的符号链接。

Mac 下安装 PHP 扩展 vld & xhprof

最近因为经常离线调试，所以开始重新在本机搭环境，还好 Mac 原本就自带了 PHP 。

[515][MacBookPro: /tmp]$ which php
/usr/bin/php
[516][MacBookPro: /tmp]$ php --version
PHP 5.3.3 (cli) (built: Aug 22 2010 19:41:55)
Copyright (c) 1997-2010 The PHP Group
Zend Engine v2.3.0, Copyright (c) 1998-2010 Zend Technologies

既然有 php 那就先试试直接用 pecl 来安装。

sudo pecl install -f vld
sudo pecl install -f xhprof

不过安装 xhprof 时提示说要在扩展的目录里，查了一下 PECL Bug #16438 里面说是 pecl 里 xhprof 包的问题。那么问题也就很好解决了，直接把源码包下载下来安装即可。

wget http://pecl.php.net/get/xhprof-0.9.2.tgz
tar zxf xhprof-0.9.2.tgz
cd xhprof-0.9.2/extension
phpize
./configure
make && make install

然后修改 /etc/php.ini 如果没有这个文件就

sudo cp /etc/php.ini.default /etc/php.ini。

在 php.ini 中增加 extension=vld.so 和 extension=xhprof.so 和针对这两个扩展的详细配置，这个可以在网上搜到。 然后在 ~/.bash_profile 里增加 alias phpo=’php -dvld.active=1’ 以后再打 phpo xxxx.php 就可以看到 vld 的效果了。

MTK平台图片解码方法教程

MTK在绘制图形的时候使用的是gdi_image_codec_draw这个函数，在这个函数中，MTK会根据img_type这个参数从gdi_image_codecs这个全局数据结构数组中取得相应绘制回调函数。gdi_image_codecs全局变量在gdi_image.c文件中定义。 （1）BMP解析过程 当img_type为GDI_IMAGE_TYPE_BMP_FILE_OFFSET的时候，MTK会调用gdi_image_bmp_draw_handler作为BMP文件解析的处理函数。在这个函数中，MTK会根据程序员指定的显示大小对bmp文件进行放大或者缩小，由于这里我们只是简单研究一下，就不以图片的放大或者缩小为例子了，如果要研究图片的放大或者缩小，请各位自己研究。我们只研究不对bmp进行放大或者缩小的过程——gdi_image_bmp_draw_file函数。 gdi_image_bmp_draw_file这个函数在gdi_image_bmp.c文件中。这个函数一开始首先建立了一个比特流，在我看来就是把这个BMP文件打开，并把BMP的文件的数据放到gdi_bytestream_buffer这个全局数组中，为以后的解码做准备。接下来大家可能就要迷糊了，MTK使用的是gdi_image_bmp_draw_internal_from_file这样一个函数，这个函数是什么呢！说出来下一条，这个函数是个宏！确切的说这个曾经是函数调用的语句实际上被GDI_IMAGE_BMP_DRAW_INTERNAL这个宏所替代，而这个宏在gdi_image_bmp_codec.h中有一个同名函数，这样gdi_image_bmp_draw_internal_from_file就被指示成了GDI_IMAGE_BMP_DRAW_INTERNAL。我第一次就晕菜了，搞不懂为什么MTK要费这么大劲，绕这么多弯。 GDI_IMAGE_BMP_DRAW_INTERNAL就是解码过程，我们可以看到这里面有1，4，8，16，24，32位BMP的解码函数，如果我们解码的不是这些标准的BMP呢！对不起，MTK会重启！ （2）静态GIF图片的解码过程 当img_type为GDI_IMAGE_TYPE_GIF_FILE_OFFSET的时候，MTK会调用gdi_image_gif_draw_handler函数进行解码。在这个函数中同样分为可变大小和不可变大小，数据来源于文件还是来源与内存资源，这4种情况，我们还是只讨论数据来源于文件而且不进行缩放操作的情况——gdi_image_gif_draw_file。 gdi_image_gif_draw_file这个函数有两个分支。在整个函数的实现中，会有一个do{}while(0)的循环，在定义了硬件解码宏之后，在硬件解码结束以后使用一个break；语句跳出循环。软解码的代码在硬解码的代码后面，没有宏控制。当硬解码宏打开后，完全靠硬解码结束后的break来区分软硬解码。这样，如果硬解码出现问题，可能会造成严重的后果。我不清楚MTK为什么这样做，可能是他们认为硬解码的所有返回都已经处理过了，所以才使用这种方式的吧！ 在6226，6228等高端的MTKCPU上，图像都是硬解码的。在这些CPU内部有一组专门的解码电路来对图形进行解码。在硬解码的时候，MTK最终会调用gif_decode_hw这个函数对CPU内部的寄存器进行相关的设置，最后调用GIF_START这个宏函数开始对GIF图形进行解码。 在6225以下的CPU中，所有的图像都是软解码的，这时MTK使用了ret = gdi_image_gif_draw_file_decoders[gdi_act_layer->cf] 这个语句。gdi_image_gif_draw_file_decoders是一个函数指针数组。这个数组定义在gdi_image_gif.c中，这个数组中的元素（例如gdi_image_gif_draw_internal_from_file_8等）其实都指向GDI_IMAGE_GIF_DRAW_INTERNAL这个宏，这个宏又在Gdi_image_gif_codec.h中对应一个同名函数。好像在哪里见过哈！对！BMP就是这样指来指去的。MTK的风格就是这样奇怪而统一。 GDI_IMAGE_GIF_DRAW_INTERNAL就是GIF的解码过程。 一开始，MTK向我们展示了一个catch机制，MTK把最后的2张GIF图片保存在一个gdi_gif_cache的数据结构中，首先检查程序员需要的是不是这两张图片。如果是就不用解析了，不是就要重新解析。解析的算法我们就不讨论了，喜欢研究的可以看看GDI_IMAGE_GIF_CODEC这个函数的实现，GIF由于有动画的设定，所以解析起来要比BMP复杂多了！ （3）JPEG图片解码过程 当img_type为GDI_IMAGE_TYPE_JPG_FILE_OFFSET的时候，MTK会调用gdi_image_jpeg_draw_handler函数进行解码。这个函数最终会调用gdi_image_hwjpeg_draw_internal。MTK把JPEG的软解码和硬解码的接口在这个函数层次统一了起来，gdi_image_hwjpeg_draw_internal会调用gdi_image_hwjpeg_start_decode，gdi_image_hwjpeg_start_decode再调用jpeg_decode_process函数。jpeg_decode_process函数再负责调用JPEG解码核心对JPEG图片进行解码。最后的解码函数为decode_jpeg_file这个函数。无论是软解码还是硬解码都要调用decode_jpeg_file这个函数。在JPEG图形解码这部分，MTK做的还是比较符合中国工程师习惯的。 还有一点，如果我们只想取得JPEG图像的数据，那么我们只要调用gdi_image_jpeg_draw_file_to_buffer或者gdi_image_jpeg_draw_to_buffer这两个函数好了。我们测试过，MTK对这两个函数的封装，封装的比较好。这样就给了我们一个通过JPEG图像传递某种信息的渠道。哦！搞的想干坏事一样，不说了，不说了！ （4）PNG图片解码过程 当img_type为GDI_IMAGE_TYPE_PNG_FILE_OFFSET的时候，MTK会对PNG进行解码，经过了上面的分析，我相信大家都能对MTK的图形解码的流程有了比较深刻的理解了，各位可以自己分析这个过程，我这边就不赘述了

MTK死机问题分析实例

Dear Sir : 下午有看到贵司上传上来的memorydump，但是没有抓全，只有不到1k，正常是External ram Internal Ram的size，至少要5M以上。 请确认在抓的时候 点击 start之后等到Finished Memorydump的对话框自动弹出才可以 新的bin文件download 到手机后: 1、开机进入“信息” 2、选择“短信” 3、按“确定” 4、进入了新的界面，在这个界面选择“收件箱” 5、按“确定” 6、进入了“所有信息”的列表 7、任选择一短信 8、按“确定” 9、进入了“信息内容”的界面 10、按左软键“选项” 11、进入了“信息选项”界面 12、选择11项“使用号码” 13、按“确定” 结果：黑屏重启 开启memory dump显示： [1]Fatal Error: kal buffer pool ID is invalid 1=809 2=770063 MMI 对於共用memory的APP，请务必保证不能有两个APP同时使用这块memory，请贵司检查这部分 这种共用memory的方法，不是很建议用 Dear Customer, May you please update the status of this issue? If we don’t see any issue update in 3 days, we will presume that the problem has been resolved and will close the issue. Thank you for your cooperation. MTK 1、我们正在按你说的做，但是几率比较小不好抓memory dump；现在我个人判断大概是内存不够共享内存出了问题，因为放歌，进WAP，下载都要耗内存，但我们是共享内存的，见scatTET25_GEMINI.txt文件；2、但我不知道此文件中的0×082F99C0，0×00030d40 等数据是如何得来的，如何去修改它，以上仅代表我个人的初步判断。 Memory timing 这边检查过没有什麼问题，请您按照上一条note先消除一下log里面报出的关闭中断过久的问题，然后麻烦您提供一份memorydump，这边再做进一步分析确认，感谢 附上抓memorydump的guide，请参考！ 为了进一步分析问题，请帮忙Dump memory 请您提供以下文件：

1. Memorydump.bin
2. Catcher log (*.clg)
3. ELF 文件 (\build\*.elf) 提示：请务必保证抓Memory dump对应的Binary和ELF文件是同一次编译生成的！！！ 您可以按如下步骤进行：
4. 打开makefile(\make.mak)中的-g选项 在makefile中设置CUSTOM_CFLAGS = -g -gtp
5. 对工程作new操作, 然后Download Binary.
6. 打开Memory dump开关； 进入工程模式，选择Misc.\Memory dump, 将其设置为On 提示：该开关默认为关，并且开机时系统会将其恢复成默认值，所以您的设置只对当次开机有效，若需抓Memory dump，请在每次开机的重新开启此开关
7. 连上Catcher(Catcher 的filter设置为Field Trial)，复制问题；
8. 当发生异常时，选择Advance\Memory Dump(在CatcherV3.10.10以前的版本此处为Download DebugInfo)，在弹出的窗口中选择Start按钮开始Memory dump； 提示：发生异常时，LCD上显示错误类型，并且不会重启，若手机直接重启，并且第1步确认正确完成，请将此现象回复给我们 Catcher Dump完成之后，会弹出提示窗口告诉您，请不要在此之前关闭Catcher或者断开手机与PC连接
9. Memory dump完成之后，请同时保存Log (选择File\Save As)；
10. 将以上两步保存下来的文件(.bin, *.clg)及Build\.elf寄给我们。 对於以上第3步打开Memory dump开关，若无法进入工模操作请尝试修改代码来打开，方法如下： 在application_initialize之前extern kal_uint32 INT_MemoryDumpFlag; 在application_initialize中调用mainp的上一行添加INT_MemoryDumpFlag = 0×26409001; 若无法成功抓取memory dump，请先检查以下几项:
11. Download cable driver较旧, 建议更新至最新版本再来尝试 a.Prolific cable latest driver download address: http://www.prolific.com.tw/eng/downloads.asp?ID=31 b.FTDI cable latest driver download address: http://www.ftdichip.com/Drivers/VCP.htm
12. download cable不稳定(通常在set filter时即有catcher error log的话更可佐证) 可尝试更换download cable，也可尝试以下步骤进行重连 a. 先在Catcher tool端执行disconnect b. 拔掉PC端的USB接头 c. 接回PC端的USB接头 d. 在Catcher tool端执行connect e. 连结成功则执行memory dump, 80%均可排除此情况
13. 系统可能完全死机，system service无法回应Catcher tool 的指令, 此种情况只能透过TRACE32调试 另外，提醒一点：之后若有类似死机的问题，请在提交问题时一并提供memory dump，以加速问题的处理 谢谢！ Dear Sir： 麻烦附上 custom/system文件夹，我这边做一下检查。同时请注意调整下面的信息： 请注意Log Sys Trace中如下信息： lr=[return address], du= [duration] lr表示打开中断时函数返回地址，表示与此操作对应的关中断操作关得太久，du表示关闭的时长，单位为Qbit (约为1us)，要求中断不能关超过60 Qbit (约60 us) 对於此类问题，可通过lr查询sym file (build\*.sym)找到相关中断操作所在的函数，地址小於lr且最接近lr对应的函数即为我们要找的 找到相关函数后，请修正至没有warning出现为止 谢谢 我们用的是三星的，是你们公司验证过的，型号为：K5L2731CAM,K5L2731CAA. 我定义的
14. CS0_PART_NUMBER=K5L2731CAM CS1_PART_NUMBER=K5L2731CAM
15. CS0_PART_NUMBER=K5L2731CAM CS1_PART_NUMBER=K5L2731CAA 上述2种情况我都试过，都会出现. 另外我想请教一下，在你们memeorydevicelist.xls中定义的，CS项：0对应的K5L2731CAM，1对应的是K5L2731CAA，但我看到很多人定义的却是： CS0_PART_NUMBER=K5L2731CAM CS1_PART_NUMBER=K5L2731CAM 这些人为什么把两者定义成一样的呢？这个CS0_PART_NUMBER，CS1_PART_NUMBER与memeorydevicelist.xls中对应CS项的0和1不是同一个概念吗？CS0_PART_NUMBER，CS1_PART_NUMBER和硬件的接线有关系吗？能不能具体解释一下，最好是举个例子说明。 MTK 2009-12-17 20:16:03 Dear Customer, 请问贵司使用的 Memory 是哪一颗？ 是否是敝司验证过的? 确实如此，频次是20次就会3次是这样的情况！ Dear Customer, 可否尽快确认一下上一个问题？ 谢谢!

elf文件格式解析

在MTK平台上实现 支持全部变量的动态加载必读。 1 Executable and Linkable Format(ELF)初稿，图请参考ELF_Format手册 1.1 Preface ELF-可执行链接格式最初是由UNIX系统实验室(USL)作为应用程序二进制接口(ABI)开发和发行。工具接口标准委员会TIS已经将ELF作为运 行在Intel32位架构之上的各类型操作系统的可导出对象文件格式标准。ELF标准为开发者提供了一组横跨多运行环境的二进制接口定义来组织软件开发。 1.2 对象文件 $leads……………. 1.2.1 介绍 本部分描述了iABI对象文件格式，也称之为ELF。有三种主要类型的对象文件：

1. 可重组(relocatable)文件包含了适合用来链接其他对象文件的代码和数据，从而创建出可执行或可共享的对象文件；
2. 可执行(executable)文件包含了用于执行的程序，该文件规定了exec如何创建一个程序的进程映像；
3. 可共享对象(shared object)文件包含了用来在两个上下文之间链接的代码和数据。首先，链接器ld将该文件和其他的可重组文件或可共享对象文件进行处理后，创建出新对象 文件，其次，动态链接器将该新对象文件与可执行文件或共享对象组合，来共同创建一个进程映像； 经过汇编器以及链接器创建成的对象文件，其是在处理器上可直接执行的程序的二进制代表。本部分主要描述文件格式以及其如何用来构建程序。后一部分也描述了对象文件，集中在程序执行所必须的信息上。 1.2.1.1 文件格式 在程序链接和程序执行过程都涉及到对象文件。出于方便和效率，对象文件格式图从链接和运行两个视角来展示文件的内容。 ELF header位于文件的开始处，其用来描述文件的组织结构。Section包含了大量的对象文件信息，从链接的视角来看就是指令、数据、符号表、重组信息等等。Segment和Program是从程序执行视角来观看的，这将在下部分讲解。 如果存在Program Header table的话，其将告诉操作系统如何创建进程映像。用来创建进程映像（执行程序）的文件必须包含program header table。可重组(relocatable)文件可以没有该信息。Section header table包含了用来描述文件section的信息。每个section在该表中都有一个对应的表项，每个表项给出了诸如section名称、尺寸等等信 息。用于链接的文件必须有section header table，其他的对象文件可有可无。 这里需要注意的是，虽然图中Program header table紧接着ELF header，section header table紧接着sections，实际的文件中并不一定是这样。而且，sections和segments也可以不按次序排放，只有ELF header是固定在文件的首部。 1.2.1.2 数据的表示 对象文件格式支持8位、32位等架构的大量处理器。然而，为了保证其容易扩展到更多的体系架构，因此对象文件提供了一些机器独立的控制数据，用来按照统一 的方式标明和解释对象文件的内容。对象文件中其余的数据都是按照目标处理器硬编码的，当然不用考虑该文件是在哪个文件上创建的。 对象文件格式中定义的所有数据结构定义都沿守自然尺寸以及对齐原则。必要时，数据结构可以包含填补内容来保证4字节对象的4字节对齐。数据也可以相对于文 件起始位置对齐，例如，包含Elf32_Addr成员的数据结构在文件中将会按照4字节对齐。为了保证可移植性，EFL中不使用bit域。 1.2.2 ELF Header 1.2.2.1 ELF Header结构 一些对象文件控制结构可能会增长，因为ELF header包含了这些结构的实际尺寸。如果对象文件格式发生改变，那么程序有可能会碰到控制结构比原来大或者比原来小的情况，这样，程序有可能就会忽略一些额外的信息。至于这些丢失的信息如何处理，则依赖于上下文环境。 e_ident 这段最先开始的字节标识该文件为对象文件，并且提供了机器独立的数据，其用来解释文件内容。完整的描述见下面的ELF Identification。 e_type 该成员指定了对象文件的类型。虽然核心文件内容没有明确的规定，但是ET_CORE类型则专门为该文件保留。 从0xFF00到0xFFFF，为特定处理器保留。剩余所有其他的值也是保留的，用于新类型的对象文件。 ET_NONE 0 No ET_REL 1 Relocatable ET_EXEC 2 Executable ET_DYN 3 Shared ET_CORE 4 Core ET_LOPROC 0xff00 Processor-specific ET_HIPROC 0xffff Processor-specific e_machine 该成员指定了文件适用的计算机架构。除了定义的值之外，其他的值保留，在必要时用于新的计算机架构。 EM_NONE 0 No EM_M32 1 AT&T EM_SPARC 2 SPARC EM_386 3 Intel EM_68K 4 Motorola EM_88K 5 Motorola EM_860 7 Intel EM_MIPS 8 MIPS e_version 该成员指定了对象文件版本，1表示该文件为最初文件格式。如果扩展了，则使用更高的编号。 EV_NONE 0 Invalid EV_CURRENT 1 Current e_entry 该成员标明了系统接管该进程控制的第一条指令的逻辑地址，从而开始了该进程。如果没有关联切入点，则默认为0。 e_phoff 该成员包含了program header table的文件偏移地址（按字节），如果该文件没有program header table，则该成员为0。 e_shoff 该成员包含了section header table的文件偏移地址（按字节），如果该文件没有section header tables，则该成员为0。 e_flags 该成员包含了文件与处理器相关的标识。 e_ehsize 该成员包含了ELF header的尺寸（按字节）。 e_phentsize 包含了program header table中一条表项的字节数，所有表项大小相等。 e_phnum 包含了program header table中表项的数目。如果该文件没有program header table，则该值为0。 e_shentsize 包含了section header table中一条表项的字节数，所有表项大小相等。 e_shnum 包含了section header table中表项的数目。如果该文件不含section header table，则该值为0。 e_shstrndx section name string table（段名称字符串表）独立构成一个section。 e_shstrndx成员包含了该section在section header table中表项的索引号。如果该文件不含section name string table，该成员中填充的值为SHN_UNDEF，见‘‘Sections’’和 ‘‘String Table’’。 1.2.2.2 ELF HeaderELF Identification 像上面提及到的一样，ELF提供了对象文件框架来支持多处理器、多数据编码、多类型的机器。为了支持这些对象文件家族，文件的初始字节必须指明如何解析本文件，而且该指明过程必须和处理器（查询解析信息就是通过该处理器进行的）无关以及和该文件剩余的内容无关。 EFL Header的初始字节也就是e_ident成员。 每个字节的具体值及其含义如下： EI_MAG0 到EI_MAG3 文件的头4个字节包含了特征码，其用来表明该文件是一个ELF对象文件 ELFMAG0 0x7f e_ident[EI_MAG0] ELFMAG1 ’E’ e_ident[EI_MAG1] ELFMAG2 ’L’ e_ident[EI_MAG2] ELFMAG3 ’F’ e_ident[EI_MAG3] EI_CLASS e_ident[EI_CLASS]指明了文件的种类或容量。 ELF文件格式在设计时就考虑到了在不同总线宽度的机器中通用，而不用考虑到诸如把最大总线宽度的机器码强加到最小机器上去。 类别ELFCLASS 32支持高达4GB的虚拟地址空间和文件尺寸，其使用上面定义的基本类型。 类别ELFCLASS64为64位架构保留，其也表明了对象文件可能的改变，不过64位格式还没有定义。 其他的类别也会在需要时定义，相应的基本类型和尺寸也会发生变化。 ELFCLASSNONE 0 Invalid ELFCLASS32 1 32-bit ELFCLASS64 2 64-bit EI_DATA e_ident[EI_DATA]规定了对象文件中和处理器相关的数据的如何编码。更多的下面会详解。 ELFDATANONE 0 Invalid ELFDATA2LSB 1 See below ELFDATA2MSB 2 See below EI_VERSION e_ident[EI_DATA]指定了EFL header版本号。当前情况下，必须是EV_CURRENT，后面会详细解释。 EI_PAD 该值标明了在e_ident中无用字节的开始，这些字节被设置为0，为保留；读取对象文件的进程应该忽略这些字节。如果未来某些未用字节派上用场了，该值在也许会改变。 文件的数据解码规定了如何翻译文件中的基本对象。如上所述，类别ELFCLASS32文件使用占用1、2、4字节的对象。在编码的前提下，对象的排布如下图所示，序号在每个单元的左上角。 ELFDATA2LSB编码规范规定了最末端字节占用最低地址： ELFDATA2MSB编码规范规定了最末端字节占用最高地址： 1.2.2.3 ELF Header机器信息 对于32位Intel体系架构而言，文件标识e_ident中相关成员的值应该如下： e_ident[EI_CLASS]= ELFCLASS32 e_ident[EI_DATA]= ELFDATA2LSB 同时在ELF header中的e_machine成员必须为EM_286。ELF header中的e_flags成员包含了和文件相关的比特标志位。32位Intel体系架构不需要任何标志位，因此该值为0。 1.2.3 Section header table及section特征 1.2.3.1 section header table概述 对象文件的section header tables使得可以轻而易举的定位所有的section，section header table 是一个Elf32_Shdr结构的数组。section header table index是数组中某个元素的下标。ELF header中的e_shoff成员给出了section header table到文件头的偏移（按字节），e_shnum给出了section header table中包含多少个表项，e_shentsize给出了每个表项的字节数。 1.2.3.2 section header table特殊的section index 某些section header table index是保留的，对象文件中的section不应该占用这些特殊index。 SHN_UNDEF 该值标明了一个没有定义的、丢失的、或者没有意义的section引用，例如，一个“已经定义了”的符号引用了SHN_UNDEF section序号的，则该符号实际被当作为未定义符号。 注意：虽然索引0被保留为一个未定义的值，但是section header table仍然包含了用于0索引的表项，也就是说，如果e_shnum=6，则索引为0-5 。 SHN_LORESERVE 该值指定了保留索引的低端。 SHN_LOPROC 至SHN_HIPROC 此范围内的索引用于特定的处理器，也是保留的。 SHN_ABS 该值指定了相应引用的绝对值。例如，引用了SHN_ABS section序号的已定义符号，其地址将是绝对的，不会被重组所影响。 SHN_COMMON 引用该section的符号都是常用的符号，例如FORTRAN COMMON或没有分配的C外部变量。 SHN_HIRESERVE 该值指定了保留索引高端，系统保留索引在SHN_LORESERVE和SHN_HIRESERVE范围之间（包含SHN_LORESERVE和 SHN_HIRESERVE）。Section head table中不会包含这些保留索引的表项。 1.2.3.3 section的特征 除了ELF header、program header table、section header table之外，Section包含了对象文件中的所有信息。另外，对象文件的section还必须满足以下几个要求：
4. 对象文件中的每个section在section header table中都必须有一个表项来描述它。即使一个section都没有，section header table也可以存在；
5. 每个section在文件中都占用一段连续字节的空间（当然也可以为空）；
6. 一个文件中的sections不能重叠，文件中的一个字节不能同时位于一个以上的section中；
7. 对象文件中可以有不活动的空间，大量的Headers以及sections不一定会覆盖对象文件的每个字节，不活动数据的内容是不确定的。 1.2.4 section header tablesection header 1.2.4.1 section header结构 section header的结构如下：
8. sh_name: 该成员指定了section的名称，其值为section “section header string table”（注意section header string table本身构成了一个Section）中某一表项的索引，该索引中为一个以nul终止的字符串；
9. sh_type: 该成员一句section的内容和语义将section分类。section类型及其描述下面将会有详细描述；
10. sh_flags: Section支持使用1bit标志来描述大量的属性，下面将会详细描述；
11. sh_addr: 如果某个section将会出现在进程的内存映射中，该成员给出的就是该section第一个字节驻留在内存中的地址。否则，该成员将会为0；
12. sh_offsect: 该成员给出了从文件开始处到section中第一个字节的偏移（按字节）。这里需要提到的SHT_NOBITS类型的section，其在文件中不占用任何空间，其sh_offsect则为其在文件中的虚位置；
13. sh_size: 该成员给出了section的大小尺寸（按字节），如果该section类型不是SHT_NOBITS，则该size即为该section在文件中所占的字节数。如果是，则即使该值不为0，但是其也不会在文件中占用任何空间；
14. sh_link: 该成员包含了一个section header table的索引链接，其如何解释依赖于该section的类型，下面将会详细描述；
15. sh_info: 该成员包含了些额外的信息，其如何解释也依赖于section的类型；
16. sh_addralign: 一些section可能会有地址对齐约束，例如我们要求，如果section包含了一个双字，则系统必须确保整个section按照双字对齐。也就是 说，sh_addr取模sh_addralign的值必须为0。目前只有0和2的整数次幂值可以在此处使用，0和1意味着无需对齐；
17. sh_entsize: 有些section包含的是一组固定大小表项的表，例如符号表，对于这样的section，该成员给出了每个表项的尺寸大小。如果section不包括这样的内容，则该值为0 。 1.2.4.2 section headersection type section header的sh_type成员包含了如下的语义：
18. SHT_NULL: 该值表示该section header是不活动的，其没有对应的section，此时section header中其他的成员都没有意义；
19. SHT_PROGBITS: 该section包含了程序自定义信息，其格式和含义由程序自行决定；
20. SHT_SYMTAB和SHT_DYNSYM: 该section包含了符号表。当前每种类型的section在对象文件中只能有一个，该限制在未来有望被放开。SHT_SYMTAB为连接器提供了符 号，当然其也包含了用于动态链接的符号。但是由于一个完整的符号表可能会包含了大量的对于动态链接没有用的符号，所以，对象文件或许也应该包含一个 SHT_DYNSYM section，其中包含了一组最小化的动态链接符号，用来节省空间；
21. SHT_STRTAB: 该section包含了一个string table。一个对象文件可以有多个string table sections；
22. SHT_RELA: 该section包含了重组表项（with explicit addends）；
23. SHT_HASH: 该section包含了符号hash表，所有参与动态链接的对象都必须包含一个符号hash表；
24. SHT_DYNAMIC: 该section包含了动态链接信息；
25. SHT_NOTE: 该section包含了特定的信息，详见Note Section；
26. SHT_NOBITS: 该section在文件中不占用空间，但是其类似与SHT_PROGBITS，虽然该section不包含任何字节，但是其sh_offset成员仍然包含了概念上的相对文件起始的偏移地址；
27. SHT_REL: 该section包含了重组表项（without explicit addends）；
28. SHT_SHLIB: 该section类型是保留的，还没有被指定语义，和ABI一致的程序不应该包含该section；
29. SHT_LOPROC到SHT_HIPROC: 该范围内的值是为特定处理器语义保留的；
30. SHT_LOUSER: 该值指定了为应用程序编程者保留的索引范围的低端；
31. SHT_HIUSER: 该值指定了为应用程序编程者保留的索引范围的高端，在SHT_LOUSER到SHT_HIUSER之间的类型的section可以被应用程序使用，而不会同当前的或者未来的为系统定义的类型起冲突； 除上述类型之以外，剩余所有的类型值统统保留， 1.2.4.3 section headersection flag属性 section header的sh_flags成员包含了1比特标志，用来描述该section的属性，定义的值如下： 如果sh_flags中其中一个标志bit位被设置，则该属性就为section打开了。
32. SHF_WRITE: 该section包含了在进程执行期间可写的数据；
33. SHF_ALLOC: 该section在进程执行期间会占用内存。一些控制section不会驻留在对象文件的内存映像里，对于这些section，该属性就为OFF；
34. SHF_EXECINSTR: 该section包含了可执行的机器指令；
35. SHF_MASKPROC: 所有包含在该mask中的属性都用于特定处理器的语义； 1.2.4.4 section header sh_link和sh_info属性 section header中的sh_link和sh_info成员根据section type的不同，包含了不同的特殊信息。 Figure1-13: sh_link和sh_info说明 sh_type sh_link sh_info SHT_DYNAMIC 对于当前的sh_type，该属性的值即为该section所使用的string table section在section header table中的索引 0 SHT_HASH 对于当前的sh_type，该属性的值即为该hash表 section所使用的符号表section在section header table中的索引 0 SHT_REL SHT_RELA 对于当前的sh_type，该属性的值即为该section所相关的符号表section在section header table中的索引 对于当前的sh_type，该属性的值即为该section将要应用重组的section在section header table中的索引 SHT_SYMTAB SHT_DYNSYM 对于当前的sh_type，该属性的值即为该section所相关的符号表string在section header table中的索引 比符号表中最后一个Local符号（STB_LOCAL）索引还要大的数值 other SHN_UNDEF 0 1.2.4.5 section header特殊的section 几个特殊的sections说明：
36. .bss，该section包含了在内存中的程序的未初始化的数据，当程序开始运行时，系统将用0来初始化该区域。该section不占用文件空间，该section type = SHT_NOBITS；
37. .comment，该section包含了版本控制信息；
38. .data和.data1，该section包含了在内存中的程序的初始化数据；
39. .debug，该section包含了符号调试信息，其中内容没有硬性规定；
40. .dynamic，该section包含了动态链接信息，该section属性将包含SHF_ALLOC比特位，而SHF_WRITE比特位是否为1取决于处理器；
41. .dynstr，该section包含了用于动态链接的字符串，通常是符号表项名称字符串；
42. .dynsym，该section包含了动态链接符号表；
43. .fini，该section包含了用于终止进程可执行指令代码；
44. .got，该section包含了全局偏移表；
45. .hash，该section包含了符号hash表；
46. .init，该section包含了用于初始化进程的可执行代码，也就是说，当一个程序开始运行的时候，系统将会执行在该section中的代码，然后才会调用程序的入口点（对于C程序而言就是main）；
47. .interp，该section包含了程序解释其的路径；
48. .line，该section包含了符号调试信息的行号，其用于描述程序源代码和机器码之间的相应关系；
49. .note，该section包含了供应商及程序兼容信息等；
50. .plt，该section包含了程序链接表；
51. .relname和.relaname，该section包含了relocation信息，该section的属性包括了SHF_ALLOC比特位，通 常，name为将要被重组的section的名称，例如如果要重组.text，那么名称就为.rel.text或者.rela.text；
52. .rodata和.rodata1，该section包含了只读数据，通常进程中的不可写段，例如Program Header；
53. .shstrtab，该section包含了section名称；
54. .strtab，该section包含了符号表项名称字符串，如果文件包含了一个可加载的并且包含了符号字符串表的segment，则section的SHF_ALLOC比特位属性将被设置；
55. .symtab，该section包含了符号表，如果文件包含了一个可加载的并且包含了符号表的segment，则section的SHF_ALLOC比特位属性将被设置；
56. .text，该section包含了程序的可执行指令。

Linux内核中的红黑树

引用链接：http://www.kerneltravel.net/jiaoliu/kern-rbtree.html

红黑树是平衡二叉树的一种，它有很好的性质，树中的结点都是有序的，而且因为它本身就是平衡的，所以查找也不会出现非常恶劣的情况，基于二叉树的操作的时间复杂度是O(log(N))。Linux内核在管理vm_area_struct时就是采用了红黑树来维护内存块的。 先到include/linux/rbtree.h中看一下红黑树的一些定义，如下：

    struct rb_node
    {
    	unsigned long  rb_parent_color;
    #define	RB_RED		0
    #define	RB_BLACK	1
    	struct rb_node *rb_right;
    	struct rb_node *rb_left;
    } __attribute__((aligned(sizeof(long))));

struct rb_root只是struct rb_node*的一个包装，这样做的好处是看起来不用传递二级指针了。不错，很简单。再看一下下面几个重要的宏，细心的你一定会发现，rb_parent_color其实没那么简单，Andrea Arcangeli在这里使用了一个小的技巧，不过非常棒。正如名字所暗示，这个成员其实包含指向parent的指针和此结点的颜色！它是怎么做到的呢？很简单，对齐起了作用。既然是sizeof(long)大小的对齐，那么在IA-32上，任何rb_node结构体的地址的低两位肯定都是零，与其空着不用，还不如用它们表示颜色，反正颜色就两种，其实一位就已经够了。

这样，提取parent指针只要把rb_parent_color成员的低两位清零即可：

    #define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))

取颜色只要看最后一位即可：

    #define rb_color(r) ((r)->rb_parent_color & 1)

测试颜色和设置颜色也是水到渠成的事了。需要特别指出的是下面的一个内联函数：

static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link);

它把parent设为node的父结点，并且让rb_link指向node。 我们把重点集中在lib/rbtree.c上，看看一些和红黑树相关的重要算法。开始之前我们一起回忆一下红黑树的规则：

1. 每个结点要么是红色要么是黑色；
2. 根结点必须是黑色；
3. 红结点如果有孩子，其孩子必须都是黑色；
4. 从根结点到叶子的每条路径必须包含相同数目的黑结点。 这四条规则可以限制一棵排序树是平衡的。 __rb_rotate_left是把以root为根的树中的node结点进行左旋，__rb_rotate_right是进行右旋。这两个函数是为后面的插入和删除服务，而不是为外部提供接口。 新插入的结点都设为叶子，染成红色，插入后如果破坏了上述规则，通过调整颜色和旋转可以恢复，二叉树又重新平衡。插入操作的接口函数是

    void rb_insert_color(struct rb_node *node, struct rb_root *root);

它把已确定父结点的node结点融入到以root为根的红黑树中，具体算法的分析可以参考[1]中第14.3节，这里的实现和书中的讲解几乎完全一样。怎么确定node的父结点应该在调用rb_insert_color之前通过手工迭带完成。值得指出的一点是，虽然插入操作需要一个循环迭代，但是总的旋转次数不会超过两次！所以效率还是很乐观的。 删除操作多多少少都有点麻烦，它要先执行像普通二叉查找树的“删除”，然后根据删除结点的颜色来判断是否执行进一步的操作。删除的接口是：

    void rb_erase(struct rb_node *node, struct rb_root *root);

其实它并没有真正删除node，而只是让它和以root为根的树脱离关系，最后它还要判断是否调用__rb_erase_color来调整。具体算法的讲解看参考[1]中第13.3和14.4节，__rb_erase_color对应书中的RB-DELETE-FIXUP，此处的实现和书上也基本上一致。 其余的几个接口就比较简单了。

    struct rb_node *rb_first(struct rb_root *root);

在以root为根的树中找出并返回最小的那个结点，只要从根结点一直向左走就是了。

    struct rb_node *rb_last(struct rb_root *root);

是找出并返回最大的那个，一直向右走。

    struct rb_node *rb_next(struct rb_node *node);

返回node在树中的后继，这个稍微复杂一点。如果node的右孩子不为空，它只要返回node的右子树中最小的结点即可；如果为空，它要向上查找，找到迭带结点是其父亲的左孩子的结点，返回父结点。如果一直上述到了根结点，返回NULL。

    struct rb_node *rb_prev(struct rb_node *node);

返回node的前驱，和rb_next中的操作对称。

    void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root);

用new替换以root为根的树中的victim结点。 红黑树接口使用的一个典型例子如下：

    static inline struct page * rb_search_page_cache(struct inode * inode,
    						 unsigned long offset)
    {
    	struct rb_node * n = inode->i_rb_page_cache.rb_node;
    	struct page * page;
    	while (n)
    	{
    		page = rb_entry(n, struct page, rb_page_cache);
    		if (offset < page->offset)
    			n = n->rb_left;
    		else if (offset > page->offset)
    			n = n->rb_right;
    		else
    			return page;
    	}
    	return NULL;
    }
    static inline struct page * __rb_insert_page_cache(struct inode * inode,
    						   unsigned long offset,
    						   struct rb_node * node)
    {
    	struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
    	struct rb_node * parent = NULL;
    	struct page * page;
    	while (*p)
    	{
    		parent = *p;
    		page = rb_entry(parent, struct page, rb_page_cache);
    		if (offset < page->offset)
    			p = &(*p)->rb_left;
    		else if (offset > page->offset)
    			p = &(*p)->rb_right;
    		else
    			return page;
    	}
    	rb_link_node(node, parent, p);
    	return NULL;
    }
    static inline struct page * rb_insert_page_cache(struct inode * inode,
    						 unsigned long offset,
    						 struct rb_node * node)
    {
    	struct page * ret;
    	if ((ret = __rb_insert_page_cache(inode, offset, node)))
    		goto out;
    	rb_insert_color(node, &inode->i_rb_page_cache);
     out:
    	return ret;
    }

因为红黑树的这些良好性质和实现中接口的简易性，它被广泛应用到内核编程中，大大提高了内核的效率。

参考资料：

1. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, MIT Press.
2. Understanding the Linux Kernel, 3rd Edition, Daniel P. Bovet, Marco Cesati, O’Reilly.
3. Linux Kernel 2.6.19 source code.

42

[转至: http://hi.baidu.com/nebulabox/blog/item/e10720f4d04e1e68ddc474da.html] 自从Douglas Adams的银河系漫游指南系列中给出42这个答案以来，似乎没看到一个合理的解释。这部科幻系列在西方如此风靡，甚至连google搜索“the answer to life, the universe, and everything”，也会看到结果=42。