博客

  • dietlibc中的strcpy算法浅析

    我们将代码稍作修改,让一些宏定义变成函数更容易理解一些:

    为了不和标准库的strcpy名字冲突,我将其改为strcpy2.

    如果你把上面的程序编译运行一下就会发现,快的原因在于strcpy2这个函数最后一部分while循环里面的这几行:

    *(unsigned long *) s1 = l;

    s2 += sizeof(unsigned long);

    s1 += sizeof(unsigned long);

    对C语言指针了解的朋友都知道,第一行是把l这个unsigned long类型变量值赋值给s1为地址的一个unsigned long型指针指向的内容。

    在我的i386cpu PC机上,第二第三行分别是将s2以及s1指针增加了4(而不是通常函数实现里面的++)。这也就实现了每次拷贝4个char(也就是一个unsigned long)而不是只拷贝一个char。

    而strcpy2前面的函数就是确保这个拷贝可以正确执行。

    我们先看MyUnaligned这个函数(在dietlibc中原为UNALIGNED宏)。

    先取了一个值是sizeof(unsigned long) – 1,然后将源字符串指针以及目标字符串指针都与这个值做与操作(xPtr & valN1),最后两个结果做一个异或xor操作(xVal ^ yVal)。

    其实说白了很简单,xPtr & valN1相当于一个取模操作,i386 cpu上valN1的值为3,也就是与的结果可能为0,1,2,3,当xPtr或者yPtr的值为4的倍数时候,与操作得到结果为0。两个与操作结果做一下异或,只有都为0或者都为1的时候,返回为0。也就是只要有一个指针没对齐,就老老实实的做一个个char的拷贝(*s1++ = *s2++),然后从strcpy2返回。

    这个算法就是为了保证xPtr以及yPtr指针都是在内存上是对齐的(aligned),如果没有对齐还要一次赋值4个char,那可能导致写入内存出错(参考这篇http://en.wikipedia.org/wiki/Data_structure_alignment)。

    有的同学已经看出来了,如果源指针目标指针都没对齐,xor结果也是零,那不就错了么?

    OK,不还有一段代码么,在STRALIGN里面,会对目标字符串指针地址取模,然后将余数返回,比如我们运行时人为地修改s1以及s2地址将其+1。debug运行如下图,得到p以及str地址,可以看到都是对齐在unsigned long边界上的( p & 3 一定是0)。

    image

    我们在Autos窗口里直接修改地址,让其加一,如下图:

    image

    这样两个指针就都没有对齐了。继续运行:

    image

    果然如我们预计的retVal的值为0。

    image

    xRet返回值为4 – 1,也就是3。

    image

    3个字符串(“aaa”)被拷贝到目标字符串里面,这时候目标字符串指针位置是对齐的了。

    这是如果有编程经验的朋友可能已经有疑问,开头有可能没对齐,也有可能结尾部分没对齐啊,也就是尾巴部分一定是4的倍数么?未必,这时候这一段代码就起作用了。

    unsigned long key1 = MKW(0x1ul);

            unsigned long key2 = MKW(0x80ul);

    运算结果key1是0x01010101,key2结果是0x80808080,如果你看过Tony Bai写的strlen源码分析http://bigwhite.blogbus.com/logs/37753065.html ,就会发现这两个有意思的数字同样出现在glibc标准库当中。

    ((l – key1) & ~l) & key2我就不分析了,可以猜测到,这是对源字符串中NULL结尾符的检测。当检测到有结尾符的时候,就做按char拷贝,然后返回。感兴趣的可以参考TonyBai那篇文章,然后自己写几个test case测试一下。

    整个函数就是这样,分析完毕。

  • 缘分让世界变小

    从1月22日签合同到这个月22号交接,这房子买的,真是费了九牛二虎之力!今天宜家送货的人走后我刚一出门就发现走廊里又有一个送货的车载了好几个纸箱,定睛一看上面赫然写着“培乐”,有这么巧的事儿?我立刻来了精神!难道是经销商的库房?!

    更巧的是那小推车就在我家隔壁门口停住了,他们开门的当会儿我趁机往里面瞟了两眼,一个熟悉的面孔映入眼帘,那不是原来做热线客服的姐姐吗,真是多年未见啊。走进去大大地寒暄一通,感叹这世界简直太小了……

    从那家公司离开整整六年,不但结婚生子而且工作换了两三个,每次写简历的时候都会不自觉地回忆起在雅培那一年的点滴往事,想来刚走出校门就能有那样的工作机会实在幸运,学到的东西不说受用一生也差不多了,至少到现在我经常还在吃那个老本儿,虽然从骨子里不喜欢做销售,却不得不承认它在很多工作中的重要性,跟人打交道的工作不是什么人都能做,也不是什么人都能做好,当初领导说可惜我没有坚持下来,到现在我也搞不懂离开的决定是否正确,反正有一点可以肯定,那就是在职的时候学到那么多东西,真是值得了。

    世界居然会有那么小,绕了一圈还能再碰到一起做邻居,缘分真是大大地啊。电话里跟王老师讲这件事儿的时候我们简直兴奋毁了。跟她的忘年交也要感谢雅培的那段日子呢,领导当时总说公司待我们不薄得好好珍惜,现在总算懂了,公司提供工作环境提供福利待遇也给我们很多锻炼的机会,让我们得以实现自己的价值,更让我们结识那么多人,从同事到朋友,从朋友又到同事,缘分啊,真是妙不可言。

  • 什么时候该用ASSERT?

    —————————————————-
    Michael to pongba

    有下面2种方法:

    方法一:Section *pImageSection = new Section(pImage);

    assert(pImageSection);

    方法二:略

    ps:现在项目组代码用第一方法,并且也不写日志,每一次客户端down了,定位问题都要很久,让人很崩溃。并且到处都是assert。

    我个人认为,用assert的地方,是比较严重的错误,甚至不能够让程序再运行下去。

    如果到处用asset也太残忍了,有的时候应该温柔的跳过,然后写日志,返回。告诉我哪里运行失败了。

    —————————————————-

    下面是我对这个问题的回答:

    首先需要指出一个非常重要、讨论前必须明确的问题,assert一般不应该直接用,而应该包装一下,比如微软就有ASSERT宏,可以跟踪line file这些有用信息,另外可以通过条件编译取消ASSERT。每次定位很久,只能说这种编程common sense还没有建立起来。

    原文虽然说得很简单,其实涉及了几个方面,一个是版本管理发布,一个是错误处理机制,一个是如何写日志,我们一个个讨论。

    首先是什么情况下用ASSERT,什么情况下应该处理wrong case?

    一个成熟的代码里面,大概有百分之三十到七十的代码都是为了查错,fault tolerance。比如你写一个API或者对外使用的函数,别人要调用,你要确保传入的指针不为空,传入的参数合法,这时候都不应该,注意是不应该使用ASSERT,因为这些情况out of your control。

    什么情况可以使用ASSERT,应该是那些绝少发生的例子,而且你可以控制的那些代码段落,比如Object* p = new Object,返回空指针,这种情况下多半是内存申请出错,即使你容错了,后面的逻辑也不会正常,这时候就应该停止运行报错了。还有就是你的内部函数(注意是你程序的内部哦),因为内部函数的代码责任其实是你自己的,你传错参数只能说水平太差怨不得别人。也许有人会说,同组里别的程序员万一也调用了这个函数怎么办?这种情况当然是会有的,其实也没法避免,但可以用ASSERT以及Code review这些手段来规范,同一个程序组里面的问题属于内部矛盾好解决多了。

    所以,大的原则可以是这样:内部函数尽量简化容错机制,稍微苛刻一些,而对外接口则尽量容忍,出错处理也要温柔。

    第二个问题,ASSERT该怎么写?

    我已经提到,不要直接使用assert,最好包装一下,加入#ifdef _DEBUG这种条件编译选项,保证Release版本不弹出ASSERT。这里其实也涉及到版本管理问题,一个商业产品发布一般包含两个版本(Release版以及Debug checked版本),即使是Windows操作系统也是如此。在Release版本要Disasble assert,这时候如果出错可以用后面的Crash Dump机制捕捉跟踪,而且要说明的是Release版本一样要附带PDB文件(或者Linux同类文件),保证Crash Dump可以定位。Debug版本也要发给用户,用户可以通过它返回更详细信息。每个Build出来的Release、Debug都应该妥善备份,将来客户提交Bug,对应版本以及PDB,就可以准确定位,不会出现很难差错的现象。

    另外也可以加入日志log选项。在这里跑一下题,日志记录也是个大问题,要考虑多线程以及性能问题,其实不是加入日志系统就万事大吉了,说句难听的,对于那些2B Number One的人来讲,任何一个好东西都可能被他们用到烂。一般ASSERT跑出来,对于客户来说就等同于Crash了,所以可以参考一下Google的Crash Report开源项目,比如Windows下可使用Crash Dump机制来捕捉崩溃时调用栈,这样即使Fail Soon Fail Fast也不会很难看。这些手段都是common sense的东西,一个正常的软件开发公司应该积累下这些代码财富才对。

  • 奇怪的C语言特性

    Most from http://stackoverflow.com/questions/1995113/strangest-language-feature

    下面列出的特性未必奇怪,有的算是有趣。

    1)a[2] 等价于 2[a]

    "aabbccdd"[5] 等价于 5["aabbccdd"]

    这条特性可以用于使用数组、指针、字符串,但不能用在变量定义时。K&R C Programming language 217页对此有介绍。

    2)二元、三元复合字符

    http://en.wikipedia.org/wiki/Digraphs_and_trigraphs

    字符串字面值??!将被认为是|,所以两个问号同时出现在字符串的时候一定要小心。二元复合字符在C99被引入,如<:等价于[

    3)Duff’s Device

    http://en.wikipedia.org/wiki/Duff%27s_device

    特点是switch与while交错出现。代码类似

    image

    4)同名同姓现象

    image

    在《C陷阱与缺陷》中有详细解释。

    5)a[i++]= i;

    这个好像是依赖特定编译器实现,我在Xcode实验结果为先对a[i]赋值i,然后操作i++。此类代码一定要小心。如果你在做code review发现++ –出现在其它表达式中或者作为参数出现,一定要立刻马上把它移出来作为单独语句,小心驶得万年船。

    6)sizeof

    sizeof(x), x可以是一个表达式或者类型名,如果是表达式,不做运算,int x = 1; size_t sz = sizeof(x++); X不会增加。T *p = NULL; p = malloc(sizeof *p); p并没有提领,K&R圣书也有讲。

    sizeof unary-expr; sizeof(typename);一元表达式可以没有括号,圣书里面语法部分提到。如size_t f = sizeof 99;

    7)宏定义要小心

    例如:#define FOO(a,b) (a+b)/(1-a)如果这样调用FOO(bar++,4),自增两次,当然,把宏展开就非常清楚了。

    参考资料:

    http://www.steike.com/code/useless/evil-c/

    《C陷阱与缺陷》

  • 一些关于c语言中malloc以及free的资料-留存

    Advanced C Programming Memory Management II (malloc, free, alloca, obstacks, garbage collection) http://www.mpi-inf.mpg.de/departments/rg1/teaching/advancedc-ws08/script/lecture09.pdf

    在这个网页上的pdf slide都非常不错,值得推荐http://www.mpi-inf.mpg.de/departments/rg1/teaching/advancedc-ws08/literature.html

     

    A Memory Allocator by Doug Lea

    http://gee.cs.oswego.edu/dl/html/malloc.html

    Simple Memory Allocation Algorithms

    http://www.osdcom.info/content/view/31/39/

    Simple Memory Allocation Algorithms

    http://goog-perftools.sourceforge.net/doc/tcmalloc.html

    http://en.wikipedia.org/wiki/Dynamic_memory_allocation

    http://en.wikipedia.org/wiki/Malloc

    https://users.cs.jmu.edu/bernstdh/web/common/lectures/slides_cpp_dynamic-memory.php

    http://www.flounder.com/inside_storage_allocation.htm

    http://blog.codingnow.com/2010/05/memory_proxy.html#more

    http://www.ibm.com/developerworks/linux/library/l-memory/