nginx内存管理浅析与感悟

Fri, Sep 27, 2013

学习过nginx模块开发的基本知识之后,距离真正开发nginx模块还是很有距离的。 后续还需要学习很多nginx源码相关的知识,首先比较感兴趣的是内存管理,都说 既然是c程序猿那么就有必要做好内存管理,而不是抱怨malloc和free的种种不是。 nginx的内存管理就很具有特点,本文虽然标题为浅析和感悟,重点在于感悟以及一点 补充。本文重点介绍nginx的缓存池ngx_pool_t,而ngx_buf_t,ngx_slab_pool_t不作为本文重点。 首先列举一下推荐阅读的文章,我是看着这些文章再结合源码理解nginx这部分: Nginx源代码笔记 – 内存池 基本数据结构 ngx_pool_t nginx基础设施 内存池 第一篇是比较新的文章,我认为解释的面比较多,尤其最后介绍了connection和request 是如何使用内存池的。后两篇是Tegine团队的开源书籍,这里鄙视一下第三篇的作者, 有年头没更新了哦,而且根据作者博文,貌似Tegine团队写书也是上司下达的指令。 NOTE:Tom比较懒,鉴于其他文章已经在整体上写的比较详细了,这里就不会详细写了。 大家还是先去看原文,在来看这篇类似读后感的文章吧。 根据学习,总结以下几个内存池的特点: 1.大部分使用过程,内存池只申请不释放 在nginx完整的处理完一个request请求后会统 释放ngx_pool_t。这是牺牲空间提高处理效率和方便程序管理的折中方案,也要求我们编程时申请空间要慎重,尽量不要出现经常扩容的情况。如果申请 了较大的内存,ngx_pool_t不足以分配,则通过POSIX标准接口分配内存,并以单链表 的形式挂在ngx_pool_t结构上,并且大块内存支持提前释放。 2.灵活的使用指针,榨干结构体的剩余价值。通过灵活使用void指针,粗鲁的虐待 结构体,占用其不需要的空间,将链表头和链表节点合并。即节约了空间使用,又提高了代码的统一度。 3.cleanup回调机制。通过回调函数,增加了内存回收时的灵活性,解决了其他一些 在释放问题上有通病的小伙伴,比如打开文件的关闭。也就是说,内存池的cleanup也可以 负责回收打开的文件哦! 4.最简单的释放机制。刚才说到,大部分内存池中的内存只申请,不释放,比如如果 数组需要扩容,执行类似realloc的操作,那么一般只会申请新的空间,而原来的空间就 浪费了。但是,也有特殊情况,即被释放的结构,恰好就在内存池单节点的末尾处,那么 内存池还是会负责回收这段空间的。不过,估计这种理想情况应该出现次数不多吧。 5.内存池喜新厌旧。ngx_pool_t本身以链表的形式组织起来,当申请一段空间,而 当前节点都没有足够空间分配时,系统会新增加一个ngx_pool_t节点。如果内存池链表 中节点太多,每次新增节点都会有比较大的开销。nginx选择使用一个current指针指向当前可用的内存池节点,每当某个节点多次未能满足申请要求时,就将current指针拨到改节点后面。这些旧的节点就被彻底抛弃了,在内存池未来的生命历程中,current之前的节点 都不会再被请求分配新内存了。

次级指针的灵活使用

Mon, Sep 2, 2013

平时使用C时都不太常用次级指针,即指向指针的指针。我的编程习惯里用次级指针的地方一般是不得不用,比如把一个指针作为参数传递给某个函数,函数执行过程中需要改变该指针变量的值,那么就必须用指向指针的指针了。最近发现pocket里面还有几个压桌脚的文章一直没看,今天翻出看了看,又长了长姿势。首先来看酷壳上的这篇文章,这里介绍了Linus大神对次级指针的点化。 我依稀的印象中很久之前看过这种用法,但是后来记住和使用的都是所谓的教科书版了。可能是偷懒了,感觉次级指针难以理解。但是教科书版确实随着代码复杂暴露的问题会更多。 现在再看这篇文章,理解上比以前快多了,但是还是有些疑问,自己尝试了一下,特此记录。 首先摘率一下Linus的例子: 如果我们需要写一个remove_if(link*, rm_cond_func*)的函数,也就是传入一个单向链表,和一个自定义的是否删除的函数,然后返回处理后的链接。 接下来是教科书版的代码,重点在于需要判断被删除节点是否是头节点,要做if-else的判断执行不同的代码。 typedef struct node { struct node * next; .... } node; typedef bool (* remove_fn)(node const * v); // Remove all nodes from the supplied list for which the // supplied remove function returns true. // Returns the new head of the list. node * remove_if(node * head, remove_fn rm) { for (node * prev = NULL, * curr = head; curr !=

Nginx模块开发入门-补充笔记

Thu, Aug 22, 2013

nginx是当前性能方面十分出众的Web服务器,之前也只是有所了解,去阿里面试 实习生时被问到了一些相关问题,并且提出如果我去实习就做 nginx module方面的东西。 但是由于实验室不允许外出实习,最终没能去阿里。 所以想自己学习一下nginx module的开发。 学习编程大致都是由hello world开始,我也是看着敲代码的张洋同学的博文 Nginx模块开发入门学习的.还有几个比较经典而丰富的文章 Emiller’s Guide To Nginx Module Development 十分经典,只可惜历史久远某些知识过时了 Tegine Nginx开发从入门到精通 这个书名我十分厌恶,不过内容还算不错, 阿里的团队自己做的 大神agentzh的Nginx教程 内容十分详细,可能由于太精于质量,更新时间比较慢 可以看到agentzh计划写20章,但是现在只完成两章,历时近两年.最新进展情况 可以关注该文章系列的github. nginx module开发的参考文档并不太多,通过查阅资料后发现,我得出的结论 是没有万全的module开发文档供我们使用。由于nginx也在不断开发变化,所以要想 写好module开发,最终级的方法还是要阅读nginx的核心代码。当然,有好多不错的 文章可以指引我们如何了解nginx。 敲代码的张洋同学的文章写的非常有条理通俗易懂,只是为配置文件定义指令集 的部分读的时候比较吃力。所以这里我想该博文作出一些补充说明,也算是 笔记了,所以推荐先看完那篇文章,如有在命令参数解析方面有点不清楚在来看此文。 后文中引用部分表示原博文内容 配置文件可以看做是Nginx的灵魂,Nginx服务在启动时会读入配置文件, 而后续几乎一切动作行为都是按照配置文件中的指令进行的, 因此如果将Nginx本身看做一个计算机,那么Nginx的配置文件可以看成是全部的程序指令。 原问首先介绍了nginx配置文件的组织结构,随后又提出echo模块的编写目的和配置 文件的写法 下面本文展示一个简单的Nginx模块开发全过程,我们开发一个叫echo的handler模块,这个模块功能非常简单,它接收“echo”指令,指令可指定一个字符串参数,模块会输出这个字符串作为HTTP响应。例如,做如下配置: location /echo { echo "hello nginx"; } 则访问http://hostname/echo时会输出hello nginx。 直观来看,要实现这个功能需要三步:1、读入配置文件中echo指令及其参数;2、进行HTTP包装(添加HTTP头等工作);3、将结果返回给客户端。下面本文将分部介绍整个模块的开发过程。 我重点说一下这里的第一个过程,这里我当时看文章时理解了好一会. 看到 echo “hello nginx” 的配置,我们可以联想以下几点。 首先要让nginx知道我们为nginx增加了名为echo的指令. 其次在nginx之中应该定义某种数据结构来存储指令内容”hello world”. 最后,我们应该定制一种方法,将”hello world”文本解析为内存中 可存放的指令内容. 因此, typedef struct { ngx_str_t ed; } ngx_http_echo_loc_conf_t; 定义了指令内容在内存中的存放形式 static ngx_command_t ngx_http_echo_commands[] = { { ngx_string("echo"), NGX_HTTP_LOC_CONF|NGX_CONF_TAKE1, ngx_http_echo, NGX_HTTP_LOC_CONF_OFFSET, offsetof(ngx_http_echo_loc_conf_t, ed), NULL }, ngx_null_command }; 定义了新的指令echo,而根据ngx_command_s结构的原型 struct ngx_command_s { ngx_str_t name; ngx_uint_t type; char *(*set)(ngx_conf_t *cf, ngx_command_t *cmd, void *conf); ngx_uint_t conf; ngx_uint_t offset; void *post; }; 将纯文本的配置转化成内存中的指令内容的函数就是set函数指针所指向的函数了 在本例的echo模块中该函数是ngx_http_echo 每次看回调和函数指针时都会比较吃力,根据与nginx源码对比,才了解set函数中 三个参数的含义: cf是配置文件读取进来的样子,也就是说,cf里的内容是字符串形式的 cmd指针就指向包裹set函数的那个ngx_comman_s结构, 在本例中,就是把ngx_http_echo_commands数组第一个元素的地址会作为cmd指针传入set函数 conf指向的就是我们定义的ngx_http_echo_loc_conf_t.

__builtin_expect(), likely(), and unlikely()

Fri, Jun 21, 2013

最近看libev源码,加上一直在做的OCTEON的项目也有cvmx_likely()这种类似的函数.所以就简单学习了一下. 简要的来说,这是一组优化程序性能的函数,__builtin_expect()是gcc的build-in函数,后两个是linux内核中使用的. 这些函数都以来与具体运行的计算机结构,不同的指令集的cpu会有不同的实现.主要用在条件判断上,比如下面的代码: if( likely(flag)){ /*case true: more likely to get though here*/ }else{ /*case false: */ } if判断引发两个分支,如果走一条分支的概率远大于另一条.那么可以考虑让编译器优化该段代码的机器指令,使进入某一分支时使用尽量少的 机器指令(例子中是进入true分支的概率大).这样代码的执行效率就会有小幅提升(benchmark) stackoverflow上也有一组问答很有参考价值,请看 最后,对于我来说,这些指令除了性能优化还有一个很大的好处.代码可读性显著提升.一般likely的分支是主干部分,unlikely的是些特殊诸如错误处理之类的代码.项目中使用这些 函数更利于阅读代码的人找到代码的主干.

OCTEON SDK Note2: Debugging SE

Tue, Jun 18, 2013

OCTEON上的SE程序崩溃时(如空指针引用),OCTEON-SDK提供了内置函数处理该种错误并打印调试信息.但是这种调试信息量十分有限而且难以阅读.所以需要借用OCTEON定制的gdb还原backtrace犯罪现场. 下文中host代表在开发机上操作的指令,target表示在板卡上使用的指令. 启动debug选项的SE程序 首先编译项目时记得加-g选项.而且尽量把-O优化选项设置为-O0. 登录到开发机,通过minicom用串口链接板卡,正常的将SE程序下载到板卡,运行时添加如下debug参数 bootoct 0 coremask=0xff debug=0 debug后的数字表示使用板卡的第几个串口作为调试口.虽然CN68XX芯片提供两个串口但是我们的设备只外接出来一个串口.所以我们必须复用这个串口,因此debug=0,使用第一个串口. 如此启动SE之后,程序会在刚开始运行时阻塞并出现一行乱码,这是正常的. 退出占用串口的进程 由于我们受限于使用一个串口,此时我们需要在开发机上退出minicom进程,否则在使用时会出现问题 使用gdb链接程序 在开发机启动mips64-octeon-linux-gnu-gdb,这是OCTEON定制的gdb. 读取可执行文件,注意是加了-g选项没有strip掉符号表的文件 file [SE-elf] 然后通过串口与板卡上的程序对接 target octeon /dev/ttyUSB0 这里注意占用串口时要保证之前minicom程序退出.而且当前使用gdb的用户有操作串口的权限.链接成功会出现提示信息,remote connection建立成功. 加载符号表和相关组件 load 这里可能没有任何提示信息 设断点并运行程序 注意断点一定要在load命令之后设置,不然是没有意义的.这里先介绍OCTEON对gdb做的改进和增加的多核调试特性. active-cores focus step-all active-cores是一个核的集合,处于该集合中的任意一个核遇到断点,都会阻塞其他处于该集合的其他核的程序.而不在这个集合中的核只会运行到针对他们这是的断点时才会阻塞.active-cores默认为所有运行该SE的核,coremask指定. 基本操作有 show active-cores set active-cores 0,2,4 /*add core 0,2,4 to active set*/ set active-cores 0-4 /*add core 0,1,2,3,4 to active set*/ focus表示当前与gdb直接交互的核,比如如果focus为0,执行break main命令,则表示在mian上设置断点,但该断点只实际针对core 0. show focus set focus 0 step-all是一个开关,只有on和off两个属性,step-all on表示接下来的next,step和continue指令同时发给active-cores集合中的所有core.否则命令只会发给设置 为focus的核. show step-all set step-all on/off 另外,如果针对我们要找空指针是在何处被引用而崩溃的这个场景.需要介绍__cvmx_interrupt_default_exception_handler函数,它是OCTEON默认的异常处理函数,所以空指针引用一定会经过它的处理.

HTC One X(endeavoru)国行(cid:htccn701)刷ROM

Thu, Jun 13, 2013

HTC One X 几个月前就入手了.虽然是国行,入手第一天就被我把ROM刷掉.时间久远, 特此回忆并记录一下整个过程. 关键词:国行 HTCONEX 卡刷 官解 刷HBOOT 独立刷boot.img 刷国外原版第三方ROM Windows环境 注意看关键词,不喜欢的或者不符合的请绕行,如国行,国外ROM,Windows环境. 名词解释: bootloader:关闭手机,同时按住电源和音量下,重启开机,进入bootloader.该模式下音量为选择键,电源为确认键 fastboot:进入bootloader之后,选择fastboot可以进入该模式.该模式是刷机的常用模式. fastboot/adb:google android sdk提供的工具,下载:for win,for linux.Linux版本 解压后,工具在platform-tools目录下.Linux下Android-SDK配置方法请见官网 USB debug mode:开启Debug模式才能在进入Android系统的情况下,使adb和fastboot 命令可以操控手机设备.如何开启 流水帐教程 安装HTC驱动 安装驱动是为了设备能被识别,也就是能使用adb和fastboot对设备进行操作.只能识别USB存储设备可不叫有驱动哦 For Windows. For Linux : Just a Guide 官方解锁Bootloader 官方解锁放心,功能基本没有损失,又能用新ROM,为什么要费力S-OFF呢 官方教程 重点解锁过程中通过email发送了一个unlock_token.bin , 这个东西保留好,后续会用到 准备刷机工具JBFWTOOL 国外友人为了刷机方便,写了一个脚本工具,JBFWTOOL, 实际上是对fastboot和adb指令的封装.脚本是bat的,在Windows下运行的. 如果想在Linux运行,可以看看bat里面的指令 按照需要执行就可以了.(请各位自己研究) 下载解压后,将Unlock_token.bin放入根目录 重启手机进入bootloader,在进入fastboot模式.Windows下会显示新硬件接入,手机上fastboot 模式也会变为fastboot usb.恭喜你已经将手机与PC链接好了,可以进行下一步操作了. 运行JBFWFlasher.bat 出现菜单选项.选择1或2,查看CID,确定输出HTCCN701,OK,手机确实是国行的.再选择4进入所有命令的模式.因为官网解锁之后S-ON依旧不变,所以13-16你永远不会用到. 拷贝ROM到内存卡 作为刷机前的准备,我们先把ROM考到内存卡,方法不限. 刷HBOOT(Optional) 刷HBOOT又可以称作刷固件/firmware,都是一个意思. HTCCN701的HBOOT版本只有1.20,如果不升级到1.36,很多ROM无法支持,比如CM10.1(android 4.2.2).因为采用较新内核的ROM刷的时候会检测HBOOT版本.当然如果不刷HBOOT,基于4.0.X的ROM也可以使用. 我在这里刷了HBoot,因为我想使用4.2.2的CM10.1. 下载HBOOT固件 ,选择HTCCN701_1.36_hboot_firmware.zip. 将zip包放入JBFWTOOL根目录,重命名为firmware.zip.因为JB工具没管我们国行的事,原版里的固件都是欧版港版等等, 我们的国行固件相当与自定义的.而JB工具提供一个刷入其他固件的选项,根据脚本内容来看就是刷如名为fireware.zip的 包.所以我们重命名一下. 运行JBFWFlasher.bat脚本 这里有两个方法,一个是用一键式脚本,一个是一步步完成. 一键式 选择1 Perform the complete Jelly Bean Firmware upgrade process (for S-On Devices) 根据提示一路刷完,在根据CID选择List的步骤,选择7,因为国行悲惨的不在list当中.而我们也说了把国行固件 重命名为fireware.zip.用处就在这里.

OCTEONSDKNote1:配置SimpleExecutive程序

Sat, Jun 8, 2013

好吧,这是Notes系列,不是episode系列了.episode是想系统性的介绍一些东西. Notes主要是用来做备忘的.今天写程序的时候发现自己以前会的东西忘掉了,为了防止此事发生. 特开notes记录.昨天预告说要写PIP/IPD.今天直接跑出来一个笔记.在此我食言了.Orz. —|||—|||—|||—|||—|||–我是食言的分割线—|||—|||—|||—|||—|||—|||– Simple Executive(SE)程序由于直接运行在板卡上. 程序经常需要操作硬件组件. 如果操作的硬件是非常固定的,比如RX/TX port,则SDK就会提供 相应的抽象去操作这些硬件.再如配置PIP/IPD模块的寄存器也 有相应的宏和结构体来表示每个配置位的含义. 但是,如果程序需要操作FPA这类可供用户自定义使用其中资源 的硬件的话,我们就需要一层抽象来屏蔽直接调用硬件的参数 (如硬件地址,硬件序号等).一般我们都能想到用宏或者枚举 来将冰冷的数字附上有含义的描述,但是如何做到统一可扩展 就需要废一番脑筋了.幸好OCTEON SDK提供了这样一种机制 OCTEON SDK提供的思想是把硬件组件的参数抽象出来的宏和 枚举统一放在项目根目录的config/cvmx-config.h 文件中.而这个文件可以通过cvmx-config shell指令自动生成. 我们只需要用SDK提供的自定义markup language编写一些配置 文件,再调用cvmx-config将这些文件转化为cvmx-config.h就 可以了.此处,我们可以类比由automake 把makefile.in转化成 makefile. 原始的配置信息需要用octeon config markup language书写 ,这些文件只要是文本文件就可以,后缀名没有要求,不过一般用.h. markup语法格式如下 cvmxconfig { ...resource requirement go here... } cvmxconfig表示配置参数的block,同一个文件可以写多个这种 block block中填写配置单元,假设我们要配置fpa硬件资源,则可以 写成如下结构: fpa CVMX_FPA_PACKET_POOL pool =0 size =8 description = "Packet buffers"; fpa: 表示硬件资源,还可以是fau,scratch CVMX_FPA_PACKET_POOL: 生成cvmx-config.h的宏,也就是将来供程序引用的值. 接下来的字段与要配置的硬件资源有关,比如fpa和fau有不同 的参数可配置 pool : fpa pool的编号,我们配置那些pool才会在程序中 真正使用. size : pool中每块内存块的大小.memory pool内存块大小是 固定的.所以可以预先确定 description : 加一点描述而已.

OCTEON SDK ep3 Packet Flow

Fri, Jun 7, 2013

OCTEON SDK已经有段时间没有更新了.一方面最近比较懒,另外最近看的东西比较杂,不太好整理,最后努力找实习,情绪低落中. 不过言归正转,把以前的知识拿出来整理一下当作复习了.主要为了以后再看不会忘记,也不是每次都从700+页的”基本手册”开始找. 有一种人写博客是给自己看的,当作笔记的整理.有人一种是写给别人看的,交流感悟和知识.我属于那一种我也不知道.我励志写出可以相互交流易读的文章 (好吧,其实我就是避讳了”教”这个词,我还不够层次),但是每每发现写出来的东西像是读书笔记,好像只给自己看一样. 所以如果有读者能给我提提建议,我会很感激的,哈哈 —||||—||||—||||—||||—||||-废话的分割线—||||—||||—||||—||||—||||—||||- 废话完了,进入正题.之前说过了OCTEON是个高性能的网络处理器.为什么说高性能呢 我认为是足够纵向,专一.又不是扩展性.许多功能都做在了硬件层面,比如任务调度,压缩解压缩,有穷自动机,甚至packet的验证和解析. 在ep1中介绍了SDK的使用,ep2介绍了多核之间通信的一种机制(具体请翻看前面 的文章).现在是时候看看OCTEON是如何整体的处理packet的了(好吧,我承认这个时间应该更早一些) OCTEON总体结构 首先来一个官方手册的精彩的概念图 图中每个矩形框都是硬件原件.纵横的线是总线.箭头则表示Packet Flow或者逻辑操作. 先来看看每个硬件组件: CORE:OCTEON NPU中的核, 我所使用的CN68XX系列每个NPU有32和核. L2/DRAM:可理解为DDR内存,这里的L2与L1相对,L1指在各个硬件中的缓存 FPA:缓存区池.这个概念搞嵌入式应该不陌生,相对于malloc的可变长度动态分配内存策略,缓冲区池 预先管理一段内存,使用固定的长度分割这段内存, 也就是说向缓冲区池申请内存时的大小是固定的.想象一下 我们收到的每个Packet MTU一般都是1528字节,IP头一般都是 20字节.既然长度比较固定,使用缓冲池申请内存就比较合适了 参考资料 SSO:数据包调度模块.不同与Linux系统,这里为了更高效的 数据包,由硬件实现对包的调度管理,而不是交给程序.这里先 不展开介绍 Interface RX/TX port:实际的物理网口 IPD/PIP: IPD是控制数据包输入的模块,PIP与IPD 关系十分紧密,每当数据包被IPD获取,PIP都会对其做简要解析 如计算CheckSum,判断数据包类型ipv4,tcp,udp等.而且 PIP还会对数据包指定QOS,这个值会决定数据包在被送到SSO时 进入哪个队列,根据不同队列可以通过程序实现队列的优先级. PKO: 负责将数据包从物理网口发送出去. 看过这个结构图,我想与普通linux系统处理网络数据包最大的不同就是中间多 了许多硬件了.linux基本上网卡驱动就是负责把网口(RX/TX port)的数据搬到内核的内存中,在有linux通过调度处理数据. 而OCTEON把中间许多处理过程用硬件做了抽象和分工. OCTEON Packet Flow 看过基本组件,我们来看 一个数据包在OCTEON中的完整旅程是什么样子的: Packet Input RX port接受数据包,交给IPD IPD 将数据包交给PIP做简单解析,得到很多初步的状态信息 .包括了数据包的合法性,类型和五元组Hash值等. IPD 向FPA申请内存空间,一般是两部分:WQE buffer 和 Packet buffer. IPD将数据包信息填入packet buffer,将 PIP处理后的结果信息填入WQE buffer.WQE这个结构下面会 有解释,现在只需要知道他类似于状态信息结构.并且每个 WQE都与一个packet buffer关联.WQE中包含一个只想packet buffer的指针.

Debian 配置 tex-live 并使用moderncv插件做简历

Wed, May 22, 2013

如果latex 形容为linux ,tex-live 就相当与debian.而debian默认的latex发行版就是tex-live,所以其他ctex(基于w)啥的不予考虑。 Debian 安装 latex 发行版 tex-live sudo apt-get install texlive latex-cjk-chinese 安装基本tex-live和中文环境支持latex-cjk-chinese。这里走了不少弯路,在网上搜了很多方法,其实根本没有那么麻烦,可能是由于现在的tex-live做的更好了。 手动安装插件 很不推荐安装texlive-latex-extra包,虽然插件很多一键安装,但是插件内容都十分老旧,不方便使用。而texlive虽然在新版本中加入了自己的包管理命令,但是debian wheezy还没有收拢该版本的texlive。为了不破坏debian纯洁度,决定手动安装,好在为了安装moderncv,依赖不是很多。 首先下载moderncv,解压,如果直接编译例子 pdflatex examples/template.tex 会出现找不到moderncv.sty的错误。其实所有类似错误都说明缺少相应插件。手动安装的方法是在这里学习到的。 下载插件包解压到合适目录(比如刚才下载的moderncv包),一般情况是到/usr/local/share/texmf/tex/latex(如果没有请自行创建).不要放到texlive官方安装目录/usr/share/texlive/texmf-dist/tex/latex的原因是,如果你不小心”升级”了插件包(如texlive-latex-extra),恭喜你,辛辛苦苦手动安装的包全跪了。 到插件目录下编译生成.sty文件,如果下载的就是.sty文件,那就恭喜你了。如果不是,则要先编译.ins,再编译.ins生成的.dtx文件。如果出现新的错误,一般是依赖问题,请继续手动安装依赖包。 更新环境变量。cd /usr/local/share/texmf/ ; sudo mktexlsr 编译示例 一切准备就绪,回到moderncv目录,编译 pdflatex example/template-zh.tex 如果一切顺利,新鲜的简历就生成了。

Upgrade from Squeeze to Wheezy

Mon, May 13, 2013

Finally, Debian Wheezy shows off it’s beauty several days ago. Today , I have some free time to play with it. So, I do the upgrade. There’s lots of new feature and changes compared with squeeze. For convenience , I write down these tips for getting familiar with gnome3 and debian wheezy faster. Install Chinese environment sudo dpkg-reconfigure locales Check zh_CN.UTF-8 and zh_CN.18030 ,then press ok . And a following diglog let’s choose a environment as default.

OCTEON SDK ep2.1 About volatile and memory barrier

Fri, Apr 26, 2013

序 在写完ep2之后,偶然间复习了一下《程序员的自我修养-链接、装载与库》这本书。不得不说这本书是很有营养的,以前看的时候一些知识半懂不懂的,现在终于有实践上的理解了。所以激动的赶紧分享一下 线程安全 OCTEON是多核NPU,编写程序必须考虑线程安全的问题。当然对于OCTEON来说,线程即进程,每个核只有一个进程。保证线程安全有如下几个特性: 同步与锁,保护临界区 线程是可重入的 某些处理要防止过度优化 前两条在众多书籍中都可以找到参考,这里我只重点说最后一条。在自我修养这本书的第28页,介绍了看似安全的实现也会因为过度优化出现问题 过度优化之变量优化 #!c int x = 0 ; spin_lock_t lx; /*Thread1*/ /*Thread2*/ lock(&lx); lock(&lx); x++; x++; unlock(&lx); unlock(&lx); 程序运行的结果看似是x=2 ,其实不一定是这样的。锁之所以起到作用,是由于 我们认定x是全局变量,在内存中被两个线程共享。但是,x有可能被优化为寄存器 变量,这样如果出现上下文切换就会出现问题。如: 1.x初始化为0 2.线程1,将x=0由内存读入寄存器reg=0,获取锁,reg++,reg=1 3.线程1可能因为后续对x还有操作,程序可能认定不着急将reg中的值写回内存, 但是此时线程1释放了锁。 4.线程2获得执行权,上下文切换(寄存器是上下文内容,也随之切换走了),获取锁,将x=0读入寄存器reg=0, reg++ , reg = 1 5.线程1和2在后来某个时刻把reg写回内存,但是x的值缺为1,与我们的预期不同 ep1提到volalite限制符阻止编译器在优化时将变量符号退化掉。而在这里,volalite也有保护作用,它可以防止变量缓存到寄存器而不及时写回,也防止编译器调整volatile变量的指令顺序。 过度优化之指令顺序 很可惜volatile 也不是万能的,他确实能解决编译器过度与优化的问题,但它还不能保护所有cpu过度优化的问题,如乱序执行。请看如下singleton模式的c++代码: #!c++ volatile T* pInst = 0; T * GetInstance(){ if(pInst == NULL){ lock(); if(pInst == NULL){ pInst = new T; } unlock(); } return pInst; }

OCTEON SDK ep2 example-mailbox

Wed, Apr 24, 2013

ep1介绍了如何搭建SDK开发环境,以及如何简单的编译运行实例程序 下面我们将开始选取几个示例程序解读其源码。 进程间通信方式 UNIX系统进程间通信主要通过信号,共享内存实现。具体实现包括邮箱mailbox,队列queue等。 嵌入式系统进程间通信方式与之大同小异,mailbox机制也是被著名的Vxworks所使用的。OCTEON自然也不会放过这个简单有效的通信机制。下面我们来解读OCTEON SDK中的示例程序mailbox。 OCTEON中如果运行SE类型的程序,则每一个核只于一个进程绑定,除了中断处理,没有其他进程与其发生抢占和上下文切换。所以在本文其他介绍中,进程要理解为是与核绑定的。 mailbox 源码 我想学习一下Ricards Stevens的写TCP/IP详解的风格,给出大段代码,逐行解释。So, everybody calm down. Here’s the source code. #!c /***********************license start*************** * Copyright (c) 2003-2010 Cavium Inc. (support@cavium.com). All rights * reserved. * * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are * met: * * * Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer.

编程珠玑算法设计之最大连续子向量的和

Fri, Apr 19, 2013

废话 由于最近要笔试面试,算法又是自己很薄弱的环节,所以恶补一下。算法导论那种经典 恐怕我是不会有勇气读完了。为了能有更好的阅读体验和对专业名词的认识,我选择了 算法程序设计英文版和编程珠玑中文版。编程珠玑书很薄,但是内容丰富,例子生动,有阅读欲望。 算法程序设计比较全面,适合慢慢读。 原著思考路线 说了一些废话,回到正题,说说我看编程珠玑的感想,没有长篇大论,只具体一个实例。原书第二版 第八章介绍了算法设计技术,给出一个问题,求解任意输入向量的连续子向量中的最大和: 31,-41,59,26,-53,58,97,-93,-23,84 ^ ^ |------187-------| 对于该输入向量,输出应该为187。 后续,作者介绍了一种立方算法,我当时就觉很奇怪,直接就能想到平方算法啊。果然,作者把平法算法 作为对立方算法的优化。引出了三条程序设计理念: 保存状态值,避免重复运算 预处理输入,将预处理值保存到数据结构中 累积,sum(x[2…6]) = sum(x[0…6]) - sum(x[0…2]) 作者给出两种平方算法,第一种用了理念一,第二种用了理念二、三。这里不做赘述了。 随后作者提出分治算法将问题分解,将规模为n的问题递归的分解规模近似为n/2的子问题。例如规模为n的 x向量可以分割为a,b两个向量,则x的最大子向量和可能出自三处: a的最大子向量 b的最大子向量 跨越a和b界限的最大子向量 最后一种情况是容易遗忘的。最后作者给出了算法实现,其中定义全为负数的向量的最大子向量和为0. 这里介绍一个c版本实现,完成代码请见bell-labs source code. float recmax(int l, int u) { int i, m; float lmax, rmax, sum; if (l > u) /* zero elements */ return 0; if (l == u) /* one element */ return max(0, x[l]); m = (l+u) / 2; /* find max crossing to left */ lmax = sum = 0; for (i = m; i >= l; i--) { sum += x[i]; if (sum > lmax) lmax = sum; } /* find max crossing to right */ rmax = sum = 0; for (i = m+1; i <= u; i++) { sum += x[i]; if (sum > rmax) rmax = sum; } return max(lmax + rmax, max(recmax(l, m), recmax(m+1, u))); } 分治算法还是不够优秀时间复杂度O(nlogn).作者又提出了扫描算法,假设已知规模为n的问题解,如何扩展到 求规模为n+1的问题解。所以前i个元素的最大子向量和可能出自两处: 前i-1个元素的最大子向量 结尾在第i个元素的最大子向量 也是通过保存状态值避免重复运算的思想,作者给出如下实现: maxsofar = 0;maxending = 0; for i in rang(0,n-1): maxending = max(maxending + x[i],0) maxsofar = max(maxsofar, maxending) 是时候该自己思考了 本章课后习题给出一个问题,如何把分治算法修改为时间复杂度为O(n)的算法? 通过作者的思路引导,我想修改这个算法已经不是困难的事情了,根据之前几个算法设计的理念。要想获得O(n)算法, 就需要把分治算法中的循环叠加求和优化掉。而又因为这个循环在求和时实际做了一些重复工作,所以可以用保存状态值的思想 把中间量保存下来避免重复运算。 接下来再考虑越界最大子向量和其实是左向量的最大最右子向量与右向量的最大最左子向量的和: |-----------|----------| |-rmax-|-lmax-| 而分解的问题在聚合时的重点就在于当前向量rmax与lmax的求解。对于任意a,b向量组合成x向量,x的lmax要么是a的 lmax,要么是b的lmax加全体a向量和。x的rmax也是同理的。 |------a-----|------b----| |-a.lmax-| |-----a+b.lmax---| 理解了这个思路之后就可以写出代码实现了,下面给出我的代码,由于递归计算需要返回的中间量比较多,所以定义一个结构体来保存。 #!c #include <stdio.h> #include <string.h> typedef struct max_vector{ int max; //max subvector int lmax; //max leftmost subvector int rmax; //max rightmost subvector int full; //sum of the whole vector }max_vector_t; max_vector_t max_vector_sum(int data[] , int l , int u){ max_vector_t ret; memset(&ret , 0 , sizeof(max_vector_t)); if(l > u ) return ret; if(l == u){ if(data[l] > 0){ ret.lmax = ret.rmax = ret.max = data[l]; }else{ ret.lmax = ret.rmax = ret.max = 0; } ret.full = data[l]; printf("%3d to %3d , max: %3d lmax: %3d rmax: %3d full:%d\n",l,u,ret.max,ret.lmax,ret.rmax,ret.full); return ret; } int m =(u - l )/ 2 + l; max_vector_t lret,rret ; lret = max_vector_sum(data, l , m); rret = max_vector_sum(data, m+1 , u); ret.max = lret.max > rret.max ?

OCTEON-SDK ep1 quick-start

Wed, Apr 17, 2013

OCTEON 是Cavium.INC生产的高速网络处理芯片,为思科华为等路由厂商提供芯片支持。由于实验室有项目需要用到,也琢磨了一阵子SDK。但是知识点陌生且繁杂。所以以后会经常记录近期所学的姿势,防止自己忘记。 一、OCTEON-SDK 环境的配置 1.安装sdk 从官网下载最新SDK,官网提供的是rpm,我是debian系统,需要alien这个工具转换以下。安装后sdk跟目录位于/usr/local/Cavium_Networks/OCTEON-SDK/. 以后称该路径为 OCTEON_ROOT.PS.我使用的版本是SDK2.3 2.配置环境变量 编辑.bashrc,增加如下内容 pushd /usr/local/Cavium_Networks/OCTEON-SDK source ./env-setup OCTEON_MODEL --check popd source引入环境变量 env-setup是sdk自带的脚本 OCTEON_MODEL指定OCTEON芯片类型,详细列表请从OCTEON_ROOT中octeon-models.txt查看 –check 开启硬件检查功能,但是该功能大大影响实际处理性能,所以做开发时开启,测试时请去掉该选项。检查的内容包括芯片类型与交叉编译的可执行文件的目标类型是否匹配,空指针检查,和硬件使用检查等。 可能,你不知道厂商给你的板卡的具体型号,就像tom遇到的情况一样?在此给出一个解决方法 首先从octeon-models.txt随便选一个model作为环境,再到exmaple编译queue例子(任何源码中包含cvmx_user_app_init()函数的实例就可以),将程序烧到板卡上运行,看提示信息,应该会返回错误信息(没错?!哥们,你可以买彩票了,你猜对了)。 ERROR: Software not configured for this chip: Expecting ID = 0xxxxxxxx, Chip ID = 0xyyyyyyy 现在拿到Chip ID, 去OCTEON_ROOT/executive/octeon-model.h 中搜索一下这个id就可以找到相应的宏应该是啥了。 3.编译实例程序 进入examples目录,执行 make -DOCTEON_TARGET=cvmx_64 就可以编译所有实例程序。如果你看不懂项目makefile是如何运作的,不用担心,目前你还不许要了解,后续会有详细讨论。OCTEON)TARGET指定以何种ABI形式编译代码。ABI的讨论请看本文第三节。 4.在模拟器运行程序 oct-sim a.out -noperf -quiet -numcores=n -noperf 表示不打印执行效率信息 -quiet 简化输出 -numcores=n n为同时将程序运行在多少核上,核数与芯片类型有关,请具体翻阅相关介绍资料。 5.详细文档:HTML格式 SDK详细文档在OCTEON_ROOT/docs/html/index.html 6.安装其他软件 minicom 串口通信软件 tftp server 用于下载可执行程序到板卡上 二、在OCTEON板卡运行示例程序 1.minicom连接板卡 minicom -s 配置中指定与板卡连接的串口 2.设置板卡环境变量 启动板卡进入u-boot引导系统,如果不能进入u-boot请自行找寻厂商解决或google之。 配置网络环境 setenv ethact octeth0 //选择当前使用的接口,eth0 setenv gatewayip 192.168.1.254 setenv netmask 255.255.255.0 setenv ipaddr 192.168.1.13 //板卡的ip地址 setenv serverip 192.168.1.1 //开发机的ip地址 saveenv //保存设置,否则下次reset板子还要重新设置 2.准备可执行程序 将开发机上一节编译的某个示例程序,如hello放置到tftp根目录下,确保开发机防火墙关闭。 3.下载linux内核到目标板并启动 tftpboot 0 hello /*第二的参数0表示要下载到目标板的内存地址,默认是0,让板子自 己决定,后面是文件名。如果看看到一堆#####的进度条就表示下载 操作ok。如果没有成功,检查网络环境和主机防火墙是否关闭*/ bootoctlinux 0 coremask=0x2 /*第二个参数和上面命令的第二个参数一致,从何内存地址启动程序 coremask=0x2 表示把linux跑在第2个核。Mask是按位表示的,比如 0x3表示前两个核,0x6表示第二三个核。当然这个mask不能超过总 共支持的核数。*/ 4.查看运行结果 恭喜你如果一切顺利,我们熟悉的hello world就会呈现在我们面前了 三、OCTEON ABI OCTEON提供如下几中ABI,在不同应用场景可能选择不同的ABI。总体来看,主要分为SE, SE-UM 和Linux 这三类。SE和SE-UM 又有32位和64位之分。 SE simple executive.

使用ant编译AndEngine

Mon, Apr 8, 2013

最近有童鞋一起想开发android游戏.做做玩玩.找到andengine这个框架,不过它的文档极为不全,但是有丰富的示例程序. android官网也是偏重介绍如何在eclipse下搭建环境.但是鉴于我蜗牛爬的机器,我还是决定用vim+ant作为开发环境.Setup vim for android development基本介绍了配置环境需要的元素.而android dev官网也提供了每一步应该如何做. 下面来说说我得折腾过程. 下载android-sdk 这里无需赘述.Here 为Androi-SDK配置环境变量 export ANT_HOME=/usr/local/share/ant export PATH=${PATH}:${ANT_HOME}/bin export ANDROID_SDK=/path/to/android-SDK PATH="$PATH:$ANDROID_SDK/tools" PATH="$PATH:$ANDROID_SDK/platform-tools" 前三行配置ant和sdk的home目录,后面将android adb等命令加入到path中. 创建Android项目 android create project --target <target-id> --name MyFirstApp --path <path-to-workspace>/MyFirstApp --activity MainActivity --package com.example.myfirstapp –target 表示android api版本,通过 android list target 查看当前安装了哪些api版本. –name是项目名称 –path项目路径 –activity 默认activity类的名称 –package 根据java命名方式定义包名称 编译项目 ant debug 获取AndEngine git clone git@github.com:nicolasgramlich/AndEngine.git 编译AndEngine ant debug 这时应该会报错,根据错误提示,缺少local.properties文件.google了一下,需要这时需要根据本地情况自生成的文件.在项目根目录下使用命令 android update project -p . 此后再使用ant debug就可以顺利编译了. UPDATE: 我的童鞋们使用环境的是eclipse,将来ant和eclipse在项目管理上也是个问题.mark一下这个问题.贴一个可能的解决方案Build eclipse project

编译AndEngineExamples

Mon, Apr 8, 2013

折腾一下午,终于搞定了AndEngineExamples的编译. 首先到github clone下来AndEngineExamples的代码,然后将根目录下project.properties文件中所需要的所有andengine的库和插件库都clone到同一级目录下. 直接运行ant debug会报几个错误: SplitScreenExample.java:176 和 BoundCameraExample.java:217 cannot convert null pointer 修改 final AnimatedSprite face = new AnimatedSprite(pX, pY, this.mBoxFaceTextureRegion, this.getVertexBufferObjectManager()).animate(100); 替换为 final AnimatedSprite face = new AnimatedSprite(pX, pY, this.mBoxFaceTextureRegion, this.getVertexBufferObjectManager()); face.animate(100); HullAlgorithExample.java: DrawMode not found 修改 import org.andengine.entity.primitive.vbo.DrawMode; 替换为 import org.andengine.entity.primitive.DrawMode; TextBreakExample.java TextOptions not found 这个错误暂时没找到有效解决办法,查看andengine api之后发现这个参数不是构造时必须的.所以删除这个textoptions参数,先保证编译通过. 最后,可能我之前折腾的太多,编译的时候出现了Multiple dex files define的错误,这是dex的错误.到网上搜一搜发现,只要把之前编译的所有bin目录都删掉彻底重新编译就可以了.(题外话:我最讨厌java的一点,可以因为编译出现无法解释的错误,clean再编译就可以了).

SSH远程登录VPS,一直报告locale错误,LC_CTYPE=zh_cn.utf-8notfound

Fri, Mar 8, 2013

今天终于买了linode的vps,ssh远程登录上去,执行命令的时候总是现实这个错误,第一反应是本机的locale设置影响了ssh登录的远程服务器.毕竟远程纯净系统肯定是只有en环境的. g了一下,发现注视掉 /etc/ssh/ssh_config 中的 SendEnv * 就可以了,不要把本机的locale环境应用到远程就可以了

在debian下禁用触摸板,敲代码的时候触摸板真讨厌

Wed, Jan 30, 2013

一条指令搞定 modprobe -r psmouse 想要恢复再把psmouse模块加载上即可 modprobe psmouse 如果想要永久禁用 sudo echo blacklist psmouse >> /etc/modprobe.d/blacklist.conf

WPA Crack

Thu, Nov 29, 2012

前言 去年这个时候,实验室让研究过破解WPA口令的方法。从查阅资料来看建彩虹表暴力字典破解是相对靠谱也有点能力实现的东西。随后根据aircrack和cowpatty的指引,把程序整合了以下,改进了cowpatty把计算彩虹表的过程写成多线程的了。还参阅了德国基友组合Martin Beck和Erik Tews的论文和项目distributed-wpa-cracking. 当时做了一点点工作就交接出去了,也忘记写总结。这里补上。 WPA破解过程 1获得指定网络中连接握手包 使用aircrack抓取握手包,首先要有合适网卡和合适的驱动。并不是所有的网卡都支持monitor mode,也不是所有的驱动都适合使用aircrack,由于跟底层相关紧密,一般搭环境就已经不易了。当然,使用bt的请绕路。 查看自己的网卡芯片类型 lsusb -v | grep Network -A6 google一下网卡芯片,到网上搜如何找到该网卡合适的驱动。我用的是debian自然就到官方wiki上找了。还有一个比较全面的站点是LinuxWireless。在这里可以找到个中芯片的网卡可以安装的驱动,虽然没有傻瓜式的教程,但是提供了宝贵思路。而且推荐使用这里介绍的compat-wireless的驱动,因为后续遇到问题的话,aircrack会对该驱动包做出官方解释并提供补丁。 确认自己装好驱动之后,安装配置aircrack。 之后准备获取握手包。 How to Crack WPA/WPA2. 这里很好的写了基本流程。但是应该注意可能会遇到的几个问题。 1.airodump监听数据包时出现negative channel错误(右上角显示fixed channel -1) 需要给compat-wireless驱动打补丁。zzzely同学说,还可以[看这里]() 2.aireplay发起deauth攻击时,同样出现negative channel的问题。 还是要打补丁,只是这时要为aireplay打了,在这里 打补丁的时候最后一行可能会出问题,我们只要自己手动添加就好了 {"ignore-negative-one", 0, &opt.ignore_negative_one, 1}, 把这句加到相应的参数集合中即可。在打好补丁再使用aireplay的时候记得加入参数 –ignore-negative-one. 2根据字典生成彩虹表 直接make编译cowpatty,生成两个可执行文件cowpatty 和 genpmk,前者用来字典攻击或者查彩虹表攻击,后者用来预先计算彩虹表。 以先计算彩虹表再破解为例: ./genpmk -f dict -d prehash -s SSID -f指定字典路径,-d指定输出,-s所指定的SSID要与_步骤1_抓包的网络SSID相同。 3根据彩虹表比对握手包里的信息,尝试口令破解 ./cowpatty -d prehash -r PCAP -s SSID -2 -d指定 步骤2 中生成的彩虹表 -r指定_步骤1_中抓到的握手包文件,-S指定SSID与之前的都要相同。-2是可选选项,但是推荐开启,破解成功率据说会高,这是选择四次握手中的1,2还是2,3中的值计算pmk来作为查表的对照。 如果字典够好,运气也够好,目标网络够不科学,那就等着出现激动人心的一行小字吧。 PS:bt中整合了一些图形化的界面,操作非常简单。如果不想看代码了解了解原理,那就直接去整bt吧。