标签 数组 下的文章

挖掘一下C语言中的多维数组

好久没有看技术类的书籍了,今晚恰看到以前不知什么时候下到的一本oreilly的叫’mastering algorithms with c’的书,从书名可以看出这是一本讲算法的书,不过由于是选用了C语言作为讲解语言,所以难免不说说C语言。其中看到一节讲指针和数组,恰好碰到书中说: a[i][j] <=> *(*(a+i) + j),这个等价式看起来显而易见,但是还是有些东西值得挖掘一下的。

我们都知道C语言定义的多维数组是’行主序’的,这意味着越靠右边的下标变换越快。a[i][j]形象的可以看成一个i行j列的矩阵,但是实际在内存中存储时,a[i][j]肯定不是矩阵存储,因为存储器可是线性下来的,至于a[i][j]各元素的存储位置我们可以通过测试获得,结果也验证了’行主序’的规则。

以a[2][3]为例,

#include <stdio.h>

int main() {
 int a[2][3] = {{1,2,3}, {4,5,6}};
 int i;
 int j;
 int k;
 int *p;

 for (i = 0; i < 2; i++) {
  for (j = 0; j < 3; j++) {
   printf("a[%d][%d] = %d; addr = [0x%X]\n", i, j, a[i][j], &a[i][j]);
  }

 }

 return 0;
}

输出结果:

a[0][0] = 1; addr = [0x23FE94]
a[0][1] = 2; addr = [0x23FE98]
a[0][2] = 3; addr = [0x23FE9C]
a[1][0] = 4; addr = [0x23FEA0]
a[1][1] = 5; addr = [0x23FEA4]
a[1][2] = 6; addr = [0x23FEA8]

从结果addr的规律看得出: 先排行元素,再排列元素。也就是说第一行排完,再来排第二行。

我们再来分析一下上面提到的那个等价式:a[i][j] <=> *(*(a+i) + j),其实这里不一定要用常理分析,我们通过实验能得出一些结论:

#include <stdio.h>

int main() {
 int a[2][3] = {{1,2,3}, {4,5,6}};
 int i;
 int j;
 int k;
 int *p;

 for (i = 0; i < 2; i++) {
  for (j = 0; j < 3; j++) {
   printf("a[%d][%d] = %d; addr = [0x%X]\n", i, j, a[i][j], &a[i][j]);
  }

 }

 p = a;
 
 for (k =0 ; k < 6; k++) {
  printf("p[%d] = %d\n", k, p[k]);
 }

 printf("a+1 = 0x%X\n", a+1);
 printf("*(a+1) = 0x%X\n", *(a+1));
 printf("*(*(a+1)+2) = %d\n", *(*(a+1)+2));
 printf("*(a+1)+2 = 0x%X\n", *(a+1)+2);
 return 0;

}

输出结果:

a[0][0] = 1; addr = [0x23FE94]
a[0][1] = 2; addr = [0x23FE98]
a[0][2] = 3; addr = [0x23FE9C]
a[1][0] = 4; addr = [0x23FEA0]
a[1][1] = 5; addr = [0x23FEA4]
a[1][2] = 6; addr = [0x23FEA8]
p[0] = 1
p[1] = 2
p[2] = 3
p[3] = 4
p[4] = 5
p[5] = 6
a+1 = 0x23FEA0
*(a+1) = 0x23FEA0
*(*(a+1)+2) = 6
*(a+1)+2 = 0x23FEA8

这里关键的就是a+1 = 0x23FEA0以及*(a+1) = 0x23FEA0,奇怪了吧,加不加’*'号结果一致;实际上 *(*(a+i) + j)中的a + i是为了取第i行的首地址,按照常理用a+i即可了。但是由于是多维数组,取数组中某一元素的值,不仅要行还要列,那这么写: *((a +i) +j )能行吗?这就是当时C的设计者要考虑到问题了。显然*((a +i) +j )这么做欠妥,依然以上面的例子为例,我们再输出些信息瞧瞧:

printf("*((a+1)+2) = 0x%X\n", *((a+1) +2));

输出结果:
*((a+1)+2) = 0x23FEB8

这显然不是a[1][2]的值,0x23FEB8是什么呢,实际上是第四行的行首地址,当然在我们的程序中只有两行在合法的范围之内。好了,问题既然出现了,当时的C设计者就考虑要区别于这种情况,遂就如是做了: *(*(a+1)+2);这样结果正确了,*(*(a+1)+2) = 6。至于当时C设计者的真实考虑我无从而知,权当逗乐打趣吧。

当数组访问越界后

下午到ChinaUnix C/C++版看了看,发现一个比较有意思的问题,一位兄弟在其帖子中问一段很简单的程序明显有数组越界访问之错误,可程序为什么运行起来却’安然无恙’,我看看了看,也给出了我自己的回复,晚上下班后又想想了这个问题,决定写一篇blog说说。

这位仁兄的程序(据他个人说来源自’GNU/Linux编程指南’)是这样的:

#define BIGNUM 50

void index_to_the_moon(int arr[]);

int main(void)
{
        int intary[10];
        index_to_the_moon(intary);

        exit(EXIT_SUCCESS);
}

void index_to_the_moon(int arr[])
{
        int i;
        for(i=0;i<bignum;i++)
        {
                arr[i]=i;
                printf("%d\n",arr[i]);
        }
}

正如这位楼主所说,这段代码很简单,相信学过2天C程序的人都能看得懂。按照楼主所说我在公司的环境(Solaris 9, Gcc 3.4)编译运行了这段代码,果然让楼主言中了,程序’安然无恙’的运行结束,没有任何异常。在那个帖子的回复中很多人说原因:’C不对数组下标越界进行检查,如果越界访问,其结果未定义’。这些回答其实也没有错,我在Windows XP, mingw Gcc 3.4.2下也试过编译运行该程序,结果是当打印输出到47,程序就中止了,也没有任何提示或者错误出现,估计是Windows OS中途将之Kill掉了。我们还是不说Windows上的东西比较好,我们还是主要以Unix平台为例,为什么Unix平台运行该程序一切OK呢?我们不妨分析一下:

明眼人都看得出来,该程序的确是越界访问数组了,但这只是表面想象或者说是违反了C语言的约束的做法,而更进一步说越界访问的结果是什么呢?Unix OS凭什么知道需要给出错误信息(Dump Core)呢?直截了当地说这个程序里面只是’污染’了用户进程地址空间中的一个叫’栈’的空间,我们回顾一下一个应用程序它的进程地址空间是一个什么样的布局(这个在’C专家编程’一书中有说明):

———— 0xFFFFFFFF(高地址)
栈  (stack bottom)

    (stack top)
————
  |
  |
 \|/
 空洞
 /|\
  |
————

————
数据段
————
文本段
———— 0×00000000(低地址)

按照上面的布局,我们来大致确定一下那个程序中各个变量的位置,当然我们主要聚焦在栈区了,我们要看看index_to_the_moon函数到底污染了栈上的哪些区域?在main函数中程序定义了一个局部数组变量intary,之后调用了函数index_to_the_moon,我们可以得到一个这样的栈布局:
—————————
stack bottom(high addess)
    |
   \|/
————–
main的返回地址
————–
saved %ebp
————–
intary[9]
————–

————–
intary[0]

————–
index_to_the_moon返回地址
….

    |
   \|/
stack top(low address)
————————–

从这个布局中我们可以看得出来,在栈上,intary中的各个元素的排列,通过打印出intary[0]和intary[1]的地址我们即可推导出其伸展方向,这样已经一目了然了,从intary[0]到intary[9]是从低地址到高地址分配的,这样我们可以推断如果有intary[10],其地址应该在intary[9]的高地址方向上,这样在index_to_the_moon中越界修改的栈数据就是沿着高地址方向的污染,而高地址方向存储的是什么呢,继续看图,沿着高地址方向依次是main的返回地址、以及调用main函数的_start函数的访问地址以及他们的参数列表和相关局部变量,当然_start函数究竟是什么样子的我们不得而知。但是污染了这些数据会不会导致core的出现呢?我觉得可能性不大,我想当main函数调用exit或者return后用户进程退出了,OS只是象征性的到栈上取一些返回值罢了,至于这些值是0还是796,意义已经不大。

那是不是这样越界下去就永远不会出问题了呢?当然不是。你把上面程序中的BIGNUM换成1000看看,起码在我的环境上,当printf访问到intary[654]的时候,出现了’段错误 ((主存储器)信息转储)’,这又是为什么呢?我们都知道我们现在的OS采用的都是虚拟存储管理,我们的进程地址空间也是虚拟地址,当我们无限制的沿着高低址方向试图访问数据时,所访问的虚拟地址值就会最终’进入内核空间’或者’溢出当前内存页所能表示的虚拟内存地址’而导致访问违例,当你访问违法的地址时出错就是必然的了。

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! Go语言第一课 Go语言精进之路1 Go语言精进之路2 Go语言编程指南
商务合作请联系bigwhite.cn AT aliyun.com

欢迎使用邮件订阅我的博客

输入邮箱订阅本站,只要有新文章发布,就会第一时间发送邮件通知你哦!

这里是 Tony Bai的个人Blog,欢迎访问、订阅和留言! 订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠 ,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:

如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:

以太币:

如果您喜欢通过微信浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:
本站Powered by Digital Ocean VPS。
选择Digital Ocean VPS主机,即可获得10美元现金充值,可 免费使用两个月哟! 著名主机提供商Linode 10$优惠码:linode10,在 这里注册即可免费获 得。阿里云推荐码: 1WFZ0V立享9折!


View Tony Bai's profile on LinkedIn
DigitalOcean Referral Badge

文章

评论

  • 正在加载...

分类

标签

归档



View My Stats