二月 | 2015 | | 重归混沌的BLOG

为什么要使用算法

在接触算法之初, 我为诸如快速排序, 二分查找效率感到惊讶.

随着代码量的增加, 对于如动态规划之类以空间换取时间的算法, 我还能理解. 但是我始终不明白如二分查找这类需要前置条件算法为什么能提高程序效率, 虽然查找快了, 但是开销浪费在了排序上, 使用二分查找的一次读写的开销和, 甚至很可能比不使用算法还要慢.

最近在阅读了一些开源代码之后, 终于有点明白为什么如二分查找这类需要前置条件算法可以提高程序效率了.

在程序设计中, 使用如二分查找这类需要前置条件的算法之所以能够提高效率, 并非是他能够降低所有操作的开销, 而是他可以将某种频繁操作的开销转嫁一部分到生成前置条件的不频繁操作上去.

以二分查找为例, 写入数据时的排序带来的开销, 其实就是在查找数据时使用二分查找所降低的开销转嫁过来的, 当然排序所带来的开销可能会略大于查找所带来的开销.

如果对于一块数据的查询频率远大于其更新速度, 查找操作所省下来的开销, 将远大于写入数据时排序所带来的开销, 那么整个程序对于这块数据的查找, 更新的开销和, 将远小于不使用算法的开销和. 这是一个很容易算的小学数学题:D

相反如果数据的更新频率远大于查询频率, 还硬要去使用二分查找, 那么整个程序对于这块数据的开销要远大于直接暴力查询.

因此算法的使用一定要根据具体情况进行分析, 不然高效的算法也可能会拖慢程序的速度.

为什么会有自动化测试框架

在研究敏捷开发中的TDD过程中, 接触到了UT(UnitTest)框架的概念.The Lego Batman Movie (2017)

在我的印象中, 自动化测试只需要每一个C模块中写一个对应的测试代码文件, 然后在Makefile稍加修改即可完成, 类似下面这样:
//module_a.h int module_a_dosomething(); //module_a_test.c int main() { module_a_dosomething(); } //Makefile .... test:module_a_test ./module_a_test module_a_test:module_a_test.c module_a.c module_a.h gcc -o $@ $^

只要略做扩展不难实现所有模块的自动化测试, 实在想不到UT框架有什么用.

本着存在就是有道理的原则, 研究了一下gtest. 发现我之前的理解并没有什么原则上的错误, 只不过UT框架提供了一些很方便的接口.

在上述不使用UT框架的方案中, 所有的代码测试打印均需要自己处理, 每一个模块的测试代码可能都含有相同的测试逻辑, 造成代码冗余.
将这些相同的测试逻辑抽出来进行整理, 一套UT的框架就可以产生了.

以google开源的UT框架gtest为例.

gtest中的ASSERT_*, EXPECT_*, TEST_F…等宏可以用来格式化输出test case的执行情况，使得测试过程中结果更为清晰，在编写test case时可以专心编写测试逻辑而几乎不需要关注测试打印的问题.

gtest将一些大部分test case代码中都会用到的测试逻辑提练出如事件、参数化、死亡测试, 运行参数等机制, 并导出接口供test case代码使用. 使得test case代码大大缩短, 测试逻辑可以更简单明了.

因此UT框架几乎是自动化测试的发展的必然产物, 当然到底是封装成Framework还是library, 这就要看作者的心意了.

lua_tothread的使用场景

在学习lua虚拟机与C交互过程中, 看到一个很令人奇怪的API, lua_tothread.
lua官方手册上只是说明lua_tothread的作用是将一个thread(coroutine)以lua_State的形式表示出来, 但是总是搞不清这个API应该在什么情况下使用.

在做了一些实验后, 终于有点结论了.

在调用luaL_newstate函数去创建一个lua虚拟机时, lua就会自动在这个状态中创建一个新thread(coroutine), 这个线程被称为主线程. 除了调用lua_close之外, 这个主线程永远不会被回收.

在lua中每个coroutine都有一个lua_State与之关联, 甚至于coroutine.create的返回值其实就是一个lua_State的指针, 这一点可以从实验得到证实, 所以lua_tothread的作用也就是与coroutine相关联的lua_State的指针返回.

在lua中使用coroutine.create或在C中调用lua_newthread来创建出的coroutine在没有被引用时将会被gc机制回收, 实际上也就是回收与这个coroutine(thread)相关联的lua_State内存.

虽然Programming in Lua中说当一个thread的lua_State被回收后, 再去操作这个被回收的lua_State时会导致代码崩溃. 但是为了测试目的的明确性, 测试代码很简单, lua_State所占用的内存释放后, 不会有其他代码去改变这块内存, 那么去使用被释放掉lua_State也就不太可能会存在崩溃的问题.

为了证明不被引用的lua_State确实会被回收, 只好先在lua中创建一个coroutine, 并在此coroutine的最后调用一个C函数. 在这个被coroutine调用的C函数的最后强制执行gc, 并打印出当前的内存使用量. 当此C函数执行完毕时, 这个coroutine也就执行结束了. 然后在C代码的main函数中再次强制执行gc然后打印出当前内存使用量, 发现内存用确实变少了, 由此可证明使用coroutine.create创建的coroutine在执行结束(没有外部引用)时确实可以被gc回收.

假设在lua中的某一个coroutine(不是主线程)去调用C函数来保存当前虚拟机的lua_State以便将来另一段C代码可以使用. 如果在C代码中直接将参数传递过来的lua_State保存下来就可能会出现使用非法的lua_State的问题. 因为此时传入C代码的指针是与这个coroutine相关联的lua_State, 并非是使用luaL_newstate创建的lua_State, 这个coroutine在执行完之后可能就结束了, 那么与之相关联的lua_State就可能会被gc回收掉. 当下次某个函数去使用保存下来的lua_State时, 由于这个被保存下来的lua_State实际上已经被gc回收掉了, 程序就可能会出现各种奇怪的问题.

为了安全起见, 如果要存储某个lua_State以备未来某个时刻使用, 就一定要存储主线程的lua_State. 因为除了调用lua_close外主线程将一直存在.
在当前coroutine环境下获取主线程的lua_State可以使用如下代码:
lua_rawgeti(L, LUA_REGISTRYINDEX, LUA_RIDX_MAINTHREAD);
lua_State *L = lua_tothread(L, -1);
lua_pop(L, 1);

linux下动态库的版本号

据说linux下的动态库管理机制可以避免微软件DLL Hell的问题.

今天抽了点时间研究了一下, 发现其实本质上是利用别名(soname)技术来实现的.

在编译so文件时, 通过参数-soname将别名传入链接器ld(gcc可通过参数-Wl来将-soname参数传入链接器), 那么生成的动态库文件中Dynamic section中的SONAME将会被填入输入的别名. 如果没有-soname参数, 则Dynamic section中将不会有SONAME字段生成.

当使用命令gcc -g -Wall -o main -L. -lver时, 在进行链接时, 链接器ld会首先去当前目录查找libver.so, libver.so也被称为链接名字, 链接器会提取libver.so中的SONAME字段中的名字作为运行时要加载的动态库的名字, 如果没有SONAME字段则使用链接名字作为运行时要加载的动态库的名字(可通过readelf -d file来查看).

linux下为了更方便我们管理动态库, 提供了ldconfig程序. ldconfig的主要功能就是搜索/lib, /usr/lib, /etc/ld.so.conf内所列的目录, 提取动态库的SONAME，并将其作为软链接的名字来建立软链接, 以使程序运行时可以按别名加载.

一个具体例子来说明上述机制是怎么避免DLL Hell问题.

可执行文件main中依赖于一个动态库liba.so.
编译liba.so时可以使用gcc -g -Wall –shared -fPIC -o liba.so sourcefiles -Wl,-soname,liba.so.1来生成liba.so
编译main时可以使用gcc -g -Wall -o main -L. -la, 链接时依来liba.so动态库, 运行时依赖的实际上是liba.so.1文件(liba.so文件的别名)

当main程序发布时, 附带的动态库文件名为liba.so.1.1.3(SONAME为liba.so.1), 安装程序时将liba.so.1.1.3拷贝到/usr/lib/目录下, 然后运行ldconfig, 将会自动生成liba.so.1的软连接指向liba.so.1.1.3.
如果以后liba.so有bug修改且没有接口修改(兼容之前发布的main程序), 那么单独发布liba.so.1.2.1 (SONAME为liba.so.1) 文件并将其拷内到/usr/lib/目录下运行ldconfig, ldconfig会自动更新软连接liba.so.1指向liba.so.1.2.1.

如果是使用dlopen动态加载则直接使用dlopen(“liba.so.1”, xxx)来指定所需要的动态库的主版本号即可.

这样就避免了多个版本的动态库相互覆盖的问题, 也就从根本上避免了DLL Hell的问题.

linux下动态库

今天无意间发现在linux下share object(dynamic library)中的函数竟然可以不通过回调的方式直接访问主程序中的函数，瞬间颠覆以前对于动态库的观念.

如代码所示libhi.so中有一个函数hello, 主程序main中有一个函数hi_out, 那么在main中调用libhi.so中的hello时，hello会自动找到main程序中的hi_output函数地址，然后进行调用.

在感叹linux下动态库强大的同时, 对于其实现机制也产生了好奇. 经过一番努力终于在程序员的自我修养中第7.6.2章找到答案.
“动态链接器在完成基本自举后, 动态链接器将可执行文件和链接器本身的符号表都合并到一个符号表中, 我们可以称它为全局符号表(Global Symbol Table)…..当一个新的share object被装载进来的时侯, 它的符号表会被合并到全局符号表中”, 因此其实libhi.so在调用hello函数时实际上是从全局符号表中找到hi_out函数的地址并进行调用, 本质上libhi.so并不知道这个hi_out是属于另一个share object还是属于main程序中.

但当我使用dlopen系列函数动态加载libhi.so时, 却总是加载失败提示找不到hi_out函数. 理论上静态加载与动态加载上的行为应该是一样的, 只不过静态加载时dlopen将会被隐式调用而已.

在ld的手册找到了答案, ld在生成可执行文件时, 默认只导出被其他动态库使用的符号. 因为是使用dlopen去动态加载libhi.so, 那么链接时ld并不知道可执行文件中的hi_out会被外部引用, 也就不会导出hi_out到动态符号表去. 当dlopen打开libhi.so时, 动态链接器在全局符号表中找不到hi_out符号, 理所当然就报错了.

要解决这个问题只要给链接器加上参数-E将主程序中所有全局符号放到动态符号表中即可, 由于生成可执行文件一般都是gcc直接生成, 因此可以使用gcc -Wl,-E来将-E参数传给ld来完成创建一个可以被动态链接的可执行文件.

setjmp的使用

以前对于C语言的setjmp和longjmp从来都是知道有这么个函数, 但是不知道什么情况下要使用, 甚至于不知道setjmp的实现机制是什么样子的.

这次在实现coroutine的过程中虽然没有使用setjmp来实现, 但是由于setjmp来实现coroutine的所有操作都是可以在用户态进行的, 因此顺便研究了一下setjmp的实现机制.

与我猜测大致一样, 在call stack上来讲setjmp一定先于或等于longjmp处于的位置, 这样其实longjmp所做的不过就是将当前寄存器上下文恢复成setjmp函数保存的值即可. 调用longjmp的函数与调用setjmp的函数共用一个栈空间, 因此longjmp恢复完寄存器后造成的结果就是恢复寄存器上下文并将栈空间释放到setjmp位于的地方.

那么这就很好解释为什么不能将setjmp使用函数再封装一层了, 假设使用函数封装setjmp代码如下:
int try(jmp_buf jmp) { int err; err = setjmp(jmp); printf("%d\n", err); return err; }


void execption(jmp_buff j, int err)

{

        return longjmp(j, err)

}

int main() { jmp_buff j; try(j); execption(j, 2); }
如上代码其实try函数与execption共用部分栈空间, 当longjmp回到try函数时, 即使用寄存器被恢复了, 但是事实上try函数的栈结构已经被破坏了, 此时longjmp之后try函数的行为是无法预料的.

------------------------
|        main          |
|-----------------------
|     try |  excption  |
|---------|            |
|---------|------------|

在使用setjmp时一定要注意栈是否被覆盖的问题, 即调用setjmp时所保存的esp的信息直到调用前longjmp之前, 不应该会出更有比setjmp保存esp时更多的空闲空间(如栈是自顶向下增加, 则setjmp到longjmp之间出现的esp的值绝不能大于setjmp保存的esp的值.