从qsort的局限性闲话gcc对“闭包”运算的支持以及DEP/NX的影响

一、问题的产生:

前几周/月?在CU论坛闲逛时看到OWO同学出了一道C语言题,由于年代久远细节记不得了,以下是自己对关键问题在记忆中改造后的描述:

//有一个enum表示科目,以0开头,以TYPE_END结尾,其余默认
enum subject_type{CHINESE=0, MATH, ENGLISH, TYPE_END};
#define N 100
//有一结构体表示学生信息
strcut student_t
{
	char*	name;
	int	number;
	float	mark[TYPE_END];
} students[N];

问题、使用qsort对不同科目成绩进行排序?如果以后学校开设了更多科目,对于此问题你会怎样解决?

二、问题的分析与解答:

我们一般有两种解决方案:
方案1、为每个科目写不同的compare函数,这是最容易想到的办法,但是每个compare都很相似,除了mark的下标不同,而且当扩展不同科目的时候需要写不同的compare函数。
方案2、使用 全局/文件 级别的变量来保存下标,这样就只需要写一个compare函数,使用这个下标,这样是的compara和外部进行通信。但是仍然有缺点,这个compare函数是不可重入,也就是说多线程不安全的,多个线程可能会同时更改全局变量,导致compare中出现逻辑错误。

这个问题的出现是目的是为了说明C语言的qsort函数看起来很通用(泛型),但其实却也有隐含缺陷,也就是qsort和compare函数之间传递的信息不足。不过支持lambda(闭包)语义的C++的std::sort可以一句话完成这个问题,示例代码如下:

for(int i = 0; i < TYPE_END; ++i)
{
		std::sort(students, students+N, [i](student_t a, student_t b){return a.mark[i]<b.mark[i];});
}
//觉得不容易看懂的话那就这个样子
std::sort(students, students+N, 
	[i](student_t a, student_t b)
	{
		return a.mark[i]<b.mark[i];
	}
);

此代码一出让人不得不惊叹C++的强大(还有复杂–!)

———————————————————从此过了许多日的分割线———————————————————————

三、问题再次解答:

前两天受到“谭浩强之启示”,发现了一个在gcc下可以用C++类似概念来解决此问题的trick,代码如下:

for(int i = 0; i < TYPE_END; ++i)
{
	//山寨"闭包"函数
	int compare(const void *a, const void *b)
	{
		return ((const struct student_t*)a)->mark[i] - ((const struct student_t*)b)->mark[i];
	}
	qsort(st, N, sizeof(st[0]), compare);
}

此代码山寨味道浓厚,还用了gcc扩展特性——嵌套函数定义,不过它很好的解决了问题。知其然,也要知其所以然,让我们来分析下这个代码到底工作的吧。
从C代码看是compare使用了函数外部for循环的i,从而得到额外信息可以使得任务得到解决。由于函数嵌套是ISO C禁止的,所以我们也不好推测,于是objdump下汇编码得知一下重要情报:
1、compare函数是作为独立函数放到了可执行文件的.text段中
2、qsort中使用的compare并不是.text段中compare函数地址,而是当前函数栈上的一个可疑地址A ??!
3、利用gdb追踪可疑地址A发现这个它的前面保存了变量i的数据,而且更重要的是
4、可疑地址A处竟然有把变量i的地址保存到ecx寄存器(32位机),然后jmp到真正compare函数上的 机器码 !!!
6、compare函数从ecx里面得到i的地址后就可以自然的使用它了。

四、闭包话题的延伸

qsort调用的compare函数看来和C++的lambda神似(除了C不能定义匿名函数外,语法错误原因在于函数的实参列表里面不能有变量声明),那么C的内嵌函数和闭包比起来究竟有几分货色呢,让我们再仔细分析一下。

1、在闭包中在局部函数引用的外部变量有个名词叫做upvalue,在我们的示例中变量i再次不妨把它看作一个"upvalue"。

2、在我们的C代码中 upvalue和部分执行代码是保存在外部函数的栈中的,这样的话多线程运行外部函数不会导致upvalue和运行混乱,这个是标准的闭包行为,很好。

3、也是由于upvalue和部分执行代码存在了函数的栈中,当函数退出的时候栈会被销毁,那么就意味着我们不能使用内部函数,这样一来闭包最大用途之一 "返回内部函数给外边使用" 就不能用了,例如累加器的例子:

//C风格的累加器生成函数
int (*counter_creator(int sed))(void)
{
	int start = sed;
	//累加器函数
	int counter(void)
	{
		return start++;
	}
	return counter;
}
//生成一个conter
int(*cnt)(void) = counter_creater(1);
//使用这个conter
printf("%dn", cnt());

在这里,counter函数使用了counter_creator的局部变量start作为upvalue,但是start在出了counter_creator之后就会失效了,所以这种用法是不正确的,虽然这个代码可能会看似正确的输出值,但是一旦中间有任何操作把counter_creator的栈空间覆盖掉,程序就出错了(不信你可以再printf一次试试)。而且也不能直接把upvalue保存到外部使用,这的确很糟糕。

4、如果我们在局部函数里面修改了外面变量的值,那么这个值会影响到下一次使用,所以用起来一定要小心。

5、总结一下,只读的使用外部变量是很安全的,多线程也依然安全。 不能把局部的东西返回给外部使用,这是"C闭包"和标准闭包的最大差异。不支持这一项的闭包基本上可以算80%残废了,也就是说前面费尽口舌和心思所讨论和理解的东西其使用范围非常有限,而且还是编译器额外支持的特性。看到这点是不是觉得有点挫呢,我也这么觉得,不过好歹也让咱窥探了下C语言实现的一些细节,如果悟性再高一些说不定还能觉察到C语言KISS哲学观。

五、DEP/NX话题的延伸

由于上一个换题太坑爹,所以换个话题,前面的C代码用了栈数据执行,所以如果你在有DEP/NX位保护的机器上用gcc再编译此代码一般会出现以下几种情况。
1、生成的汇编代码和前面描述的一样,运行也依旧。我的Intel T2130+PAE+exec-shield的机器上就是如此,编译链接的时候栈段就是可执行的,而且gcc有链接参数 -z execstack|noexecstack来控制栈是否可执行。大概是自己没有设置好DEP吧,有知情同学麻烦告知,先行谢过。

2、汇编码里面加入了奇怪的调用,用来让系统保护开放这一部分栈的执行权限。我在开了DEP的WINDOWS上观察到了这个结果(mingw编译器),使用了VirtualQuery和VirtualProtect这两个API来取得权限,而且尤为奇怪的是,程序几乎给每个库函数在文本段生成了一小段代码,内容是jmp到真正的库函数上去。

我估计大多数能编译通过此代码后的程序都不会运行出错,除非编译器忘记了DEP这个东西而且用了栈或者其他数据段,也欢迎大家来测试这个例子。同时为了验证你的DEP是否真的有效,这里有段代码拿去测试吧(仅限intel平台)

int main(void){((void (*)(void))"xc3")(); return 0;}

如果你和我一样运行无误,那么恭喜你 DEP没能保护这个程序 — 
你也可以把"xc3"这个字符串保存到栈上运行试试 
最近看到intel又有了新的保护技术叫做TXT(Trusted Execution Technology) ,不会保护的连文本文档都打不开了吧(笑~)
以上

PS:最近没有更新的动力啊,怎么办才好…

This entry was posted in C/C++, 程序设计 and tagged , . Bookmark the permalink.

21 Responses to 从qsort的局限性闲话gcc对“闭包”运算的支持以及DEP/NX的影响

  1. 大D says:

    围观Dave大人。。虽然看不懂,但是感觉好厉害啊~~!!

  2. snail says:

    围观Dave大人。。虽然看不懂,但是感觉好厉害啊~~!!

  3. davelv says:

    楼下你们俩串通好了的吧 –!

  4. kshaoye says:

    围观Dave大人。。虽然看不懂,但是感觉好厉害啊~~!!

  5. Lieo says:

    围观Dave大人。。虽然看不懂,但是感觉好厉害啊~~!!

  6. snail says:

    听说C语言的新标准C11出来了

    • davelv says:

      回复 evilhacker:
      月初出来的,有点不可思议的是,出来之前没啥太大动静,不像C++11那么引人注目,莫非大家都觉得C语言已经足够好,不需要改进了?我这里倒是还有一份C11的草稿,应该跟正式版差不多少。

  7. ForestDB says:

    围观Dave大人。。虽然看不懂,但是感觉好厉害啊~~!!

    要不要保持队形呢,纠结。

    C的强大就在于它的简介,要不要再加入函数式范式呢?也很纠结。

  8. snail says:
    引用 davelv:

    回复 evilhacker:
    月初出来的,有点不可思议的是,出来之前没啥太大动…

    我看一篇博客比较了新标准的变化,好像改动也不是太多,比如去掉gets()函数神马的,其他的就看不懂了…..有些特性挺都没听说过 🙁

  9. xushine says:

    D大~大人 新年快乐~

  10. 老谢 says:

    D大新年快乐~!

  11. W.Veale says:

    要写你同事能看懂的代码,不然只能你一个人写了,没人能帮你,出了问题只能找你,哪怕你再忙,没有同事会帮你顶一会的

    • davelv says:

      谢谢提醒,这个例子是用来讨论语言特性的,真正工程中也不会死抱着qsort或者std:sort不放。

  12. 梦之翼 says:

    看完整篇,已经有点迷糊了,弱弱的问一句,如果要完全看懂,需要哪些知识呢?
    程序代码我慢慢揣摩也读懂了,但是对于其中的机制还是有些模糊,近期正在求职和自学,希望D大给出点建议。

    • davelv says:

      这篇文章是对一个现象的衍生讨论,涉及内容比较多,是容易乱。但主要是三部分
      1、qsort的局限性;
      2、gcc的“闭包”是如何实现的
      3、栈可执行的条件有什么。
      看懂这些呢需要有如下知识:
      1、C系语言长期使用的经验/有比较熟练的建立从问题到计算机语言模型的能力。
      2、程序运行基本原理/汇编知识
      3、CPU/OS对程序运行时的保护机制
      这三个知识,前一个是要靠写代码积累的,后两个你都可以在CS:APP上找到答案。

      求职这个建议不敢多谈,原因我在你的blog也上回复了,不过说下个人感受:
      1、越是大公司,越有稳定的工作,越看重个人基础和长远发展,小公司则更关心技术层次。
      2、只要是自己感兴趣的职位和方向就努力去争取,别放过,机不可失。
      3、大公司和小公司各有利弊,可以根据你当前不同阶段的需要(提高技术深度还是广度)去选择。

      学习上:
      我一般只有一条:看书,思考,读代码,思考,写代码,思考,debug,思考如此往复。

回复 老谢 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注