2005年十一月月 发布的文章

APR源代码分析-环篇

APR中少见对数据结构的封装,好像唯一例外的就是其对循环链表,即环(RING)的封装。

在大学的时候学的不是计算机专业,但大三的时候我所学的专业曾开过一门好像叫“计算机软件开发基础”的课,使用的是清华的一本教材,课程的内容包括数据结构。说实话听过几节课,那个老师讲的还不错,只是由于课程目标所限,没讲那么深罢了。当然我接触数据结构要早于这门课的开课时间。早在大一下学期就开始到计算机专业旁听“数据结构”,再说一次实话,虽号称名校名专业,但是那个老师的讲课水平却不敢恭维。

言归正传! 简单说说环(RING):环是一个首尾相连的双向链表,也就是我们所说的循环链表。对应清华的那本经典的《数据结构》一书中线性表一章的内容,按照书中分类其属于线性表中的链式存储的一种。环是很常见也很实用的数据结构,相信在这个世界上环的实现不止成千上万,但是APR RING(按照APR RING源代码中的注释所说,APR RING的实现源自4.4BSD)却是其中较独特的一个,其最大的特点是其所有对RING的操作都由一组宏(大约30个左右)来实现。在这里不能逐个分析,仅说说一些让人印象深刻的方面吧。

1、如何使用APR RING?
我们先来点感性认识! 下面是一个典型的使用APR RING的样例:
假设环节点的结构如下:
struct  elem_t {    /* APR RING链接的元素类型定义 */
    APR_RING_ENTRY(elem_t)  link; /* 链接域 */
    int                                     foo; /* 数据域 */
};

APR_RING_HEAD(elem_head_t, elem_t);

int main() {
    struct elem_head_t  head;
    struct elem_t       *el;

    APR_RING_INIT(&head, elem_t, link);

    /* 使用其他操作宏插入、删除等操作,例如 */
    el = malloc(sizeof(elem_t);
    el->foo = 20051103;
    APR_RING_ELEM_INIT(el, link);
    APR_RING_INSERT_TAIL(&h, el, elem_t, link);
}

2、APR RING的难点–“哨兵”
环是通过头节点来管理的,头节点是这样一种节点,其next指针指向RING的第一个节点,其prev指针指向RING的最后一个节点,即尾节点。但是通过察看源码发现APR RING通过APR_RING_HEAD宏定义的头节点形式如下:
#define APR_RING_HEAD(head, elem)     \
    struct head {       \
             struct elem *next;      \
             struct elem *prev;      \
    }
如果按照上面的例子进行宏展开,其形式如下:
struct elem_head_t {
     struct elem_t *next;
     struct elem_t *prev;
};

而一个普通的元素elem_t展开形式如下:
struct elem_t {
     struct {       \
        struct elem_t *next;     \
        struct elem_t *prev;     \
     } link;

     int foo;
};
通过对比可以看得出头节点仅仅相当于一个elem_t的link域。这样做的话必然带来对普通节点和头节点在处理上的不一致,为了避免这种情况的发生,APR RING引入了“哨兵(sentinel)”节点的概念。我们先看看哨兵节点在整个链表中的位置。

sentinel->next = 链表的第一个节点;
sentinel->prev = 链表的最后一个节点;

但是察看APR RING的源码你会发现sentinel节点只是个虚拟存在的节点,这个虚拟节点既有数据域(虚拟出来的,不能引用)又有链接域,好似与普通节点并无差别。在APR RING的源文件中使用了下面这幅图来说明sentinel的位置,同时也指出了sentinel和head的关系 — head即为sentinel虚拟节点的link域。

 普通节点
+->+——-+<–
   |struct |
   |elem   |
   +——-+
   |prev   |
   |   next|
   +——-+
   | etc.  |
   .       .
   .       .

sentinel节点
+->+——–+<–
   |sentinel|
   |elem    |
   +——–+
   |ring    |
   |   head |
   +——–+

再看看下面APR_RING_INIT的源代码:
#define APR_RING_INIT(hp, elem, link) do {    \
            APR_RING_FIRST((hp)) = APR_RING_SENTINEL((hp), elem, link); \
           APR_RING_LAST((hp))  = APR_RING_SENTINEL((hp), elem, link); \
    } while (0)
你会发现:初始化RING实际上是将head的next和prev指针都指向了sentinel虚拟节点了。从sentinel的角度来说相当于其自己的link域的next和prev都指向了自己。所以判断APR RING是否为空只需要判断RING的首个节点是否为sentinel虚拟节点即可。APR_RING_EMPTY宏就是这么做的:
#define APR_RING_EMPTY(hp, elem, link)     \
    (APR_RING_FIRST((hp)) == APR_RING_SENTINEL((hp), elem, link))

那么如何计算sentinel虚拟节点的地址呢?
我们这样思考:从普通节点说起,如果我们知道一个普通节点的首地址(elem_addr),那么我们计算其link域的地址(link_addr)的公式就应该为link_addr = elem_addr + offsetof(elem_t, link);前面我们一直在说sentinel虚拟节点看起来和普通节点没什么区别,所以它仍然符合该计算公式。前面我们又说过head_addr是sentinel节点的link域,这样的话我们将head_addr输入到公式中得到head_addr = sentinel_addr + offsetof(elem_t, link),做一下变换即可得到sentinel_addr = head_addr – offsetof(elem_t, link)。看看APR RING源代码就是这样实现的:
#define APR_RING_SENTINEL(hp, elem, link)    \
    (struct elem *)((char *)(hp) – APR_OFFSETOF(struct elem, link))

至此APR RING使用一个虚拟sentinel节点分隔RING的首尾节点,已达到对节点操作一致的目的。

3、使用时注意事项
这里在使用APR RING时有几点限制:
a) 在定义RING的元素结构时,需要把APR_RING_ENTRY放在结构的第一个字段的位置。
b) 链接一种类型的元素就要使用APR_RING_HEAD宏定义该种类型RING的头节点类型。学过C++或者了解泛型的人可能都会体味到这里的设计有那么一点范型的味道。比如:
模板:APR_RING_HEAD(T_HEAD, T) —- 链接—-> T类型元素
实例化:APR_RING_HEAD(elem_head_t, elem_t) — 链接—->elem_t类型元素
 
4、APR RING不足之处
1) 缺少遍历接口
浏览APR RING源码后发现缺少一个遍历宏接口,这里提供一种正向遍历实现:

#define APR_RING_TRAVERSE(ep, hp, elem, link)    \
            for ((ep)  = APR_RING_FIRST((hp));     \
            (ep) != APR_RING_SENTINEL((hp), elem, link);   \
           (ep)  = APR_RING_NEXT((ep), link))
大家还可以模仿写出反向遍历的接口APR_RING_REVERSE_TRAVERSE。

再说内存

离我的上一篇BLOG已经时隔一个月有余,项目忙是一方面原因,最主要的还是自己没什么“收获”。在最近的项目中总是和内存打交道,时间长了,便有了些许问题,原本我就不是不求甚解者,遂趁此机会又复习了些内存相关资料。

其实下面的话题都是源于在实际项目中碰到的问题,我们通过推敲一句话来开始吧!

1、推敲一句话
在《C专家编程》一书中,有这样的说法“Malloced memory is always aligned appropriately for the largest size of atomic access on a machine”,中文版中翻译为“被分配的内存总是经过对齐,以适合机器上最大尺寸的原子访问”。这句话我也不只看过一遍,不过仅在这次我对它作了认真的推敲,其实整篇也都是围绕着这句话写的。
a) 对齐:数据项仅能存储在地址是该数据项整数倍的内存位置上。在不同的平台上对内存对齐的要求不同,比如在Windows平台上数据项也可以存储在非对齐的内存地址上。但在Sun SPARC平台上如果数据地址没对齐,对它的访问就会带来严重后果(CORE DUMP)。稍后继续详说。
b) 最大尺寸:在32为平台上一般为8字节,在64位平台上为16字节。
c) 原子访问:原子,顾名思义,不可拆分的(严格意义上,在科学界原子并不是最小的粒子,是可拆分的,但在我们这里它就是不可拆分的)。原子访问就是不能被中断的访问。

2、虚拟内存与Cache
太古老的就不说了,我们从“虚拟内存”和Cache说起,为什么莫名其妙的谈到“虚拟内存”和Cache了呢?其实真正需要内存地址对齐的就是这“两位”。虚拟内存技术和Cache的出现追其原因都是因为人们的“物质财富”拮据 — 内存条太贵。虚拟内存允许你拿硬盘做内存,这样一来就满足了应用程序对内存地址空间的旺盛需求问题,但随之而来的是大量的磁盘操作,使数据的访问速度下降了。人们遂在CPU内加了Cache。

1) 虚拟内存管理以“页”作为基本传输和保护单位在“物理内存”和“硬磁盘”之间倒腾数据。每页大小是固定的,一般为4KB一页。一旦确定了页的大小那么就相当于给了各原子数据项一个不成文的建议:“你们最好不要跨页存储”。什么是“跨页存储”?举个跨页存储例子如下:有这么一个原子类型为int的变量n = 1,其在进程地址空间的存储方式如下:(按照big-endian,高位存在低地址上)

+  ..       + 0×0000 (0000)<——–第一页
|            |
|  ..        |
+——-+
|            |
+——-+ 0x0ffd
|   0       |
+——-+ 0x0ffe
|   0      |
+——-+ 0x0fff (4095)
|   0      |
+——-+ 0×1000 (4096)<——– 第二页
|   1      |
+——-+ 0×1001 (4097)
|            |
|  ..        |

上图中变量n的存储空间横跨两个内存“页”。那么为什么最好不要跨页存储呢?如上例一旦int n跨页存储,那么程序在访问该变量的时候就必须通过两次换页才能完整的访问该数据,这照比不跨页存储的数据多了一次换页的工作。像这样如果不做约束的话,那么像n这样的数据将会到处都是,那么将会系统的性能很差。在Sun SPARC平台上像这样跨页存储会导致BUS ERROR,在Windows平台上也会带来性能上的下降。相反如果每个数据都是按照页边界对齐的话就不会带来上面的问题。

2) 除了虚拟内存的机制,Cache也是一个要求内存对齐的重要原因。一个Cache由若干Cache Line组成,每个Line中包括一个标签(tag)和一个数据块(Cache Block)组成,CPU在读写Cache时一般是按照Cache Line整行读写的,Cache结构如下图:

tag  |                block
       | 0              8              16              31
—–+—————+—————+—————
       | 32             |                    |                                     Line 0
—–+—————+—————+—————
       | 64             |                    |                                     Line 1
—–+—————+—————+—————

同虚拟内存一样,原子类型数据项不应该跨Cache Line边界存储。具体不详述了。

3、编译器甜头
如果上述问题都让应用程序员自己来解决的话,那就太困难了。庆幸的是我们尝到了“编译器甜头”,编译器通过自动分配和填充数据(在内存中)来进行对齐。对数据进行对齐可以迫使每个内存访问局限在一个cache line或一个单独的页面(page)内。这样就极大简化了cache controller和MMC这样的硬件设计和实现,并且大大提高了访存速度。总结一下:要求数据对齐,从另一个角度说就是不允许原子类型数据项跨越页面或者Cache边界。

4、常见操作未对齐内存的问题
在Sun的Solaris SPARC Runtime Check文档中列出了常见的几种操作未对齐内存的问题:(在Sun SPARC Solaris 9下测试,GCC 3.4.2)
1) 未对齐读(Misaligned Read)
例子:
   int  j;
   char *s = "hello world";
   int  *i = (int *)&s[1];
   j = *i; /* Dump Core */

分析:s指向的字符串中每个字符地址仅仅能满足1字节对齐,而读该数据项时却要求8字节对齐(GCC默认),&s[1]显然不满足对齐要求,运行出Core。

2) 未对齐写(Misaligned Write)
例子:
   char *s = "hello world";
   int  *i = (int *)&s[1];
   *i      = 'm' ; /* Dump Core */

分析:s指向的字符串中每个字符地址仅仅能满足1字节对齐,而上面程序却向该地址写数据时却要求8字节对齐(GCC默认),&s[1]显然不满足对齐要求,运行出Core。

3) 未对齐Free
例子:
   char *ptr = (char *)malloc(4);
   ptr++;
   free(ptr); /* Misaligned free */
分析:略

5、什么时候需要考虑到内存对齐
考虑内存对齐的一个典型情况就是“在异构平台间以C结构体的方式进行数据交互”。举个简单的例子:“现需要在Windows平台将一个test_t类型的数据写入一个二进制文件并将该二进制文件在Linux平台下解析,在不指定对齐系数的前提下:Windows平台默认对齐系数为8,而Linux平台默认对齐系数为4”。(暂不考虑字节序的影响)

假设test_t结构如下:
struct test_t {
    double d;
    char   c;
};

在Windows平台下将一个test_t写入二进制文件,由于对齐后test_t大小为16,所以该二进制文件大小为16;将该文件传到Linux上并解析,由于Linux上对齐后的test_t大小为12,导致Linux上的程序验证该二进制文件的完整性失败,解析失败。解决方案:在两个平台使用相同的对齐系数。如对其系数为8:
#pragma pack(8)
struct test_t {
    double d;
    char   c;
};
#pragma pack()
这样两边就能完美对正了。

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! Go语言第一课 Go语言精进之路1 Go语言精进之路2 商务合作请联系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

文章

评论

  • 正在加载...

分类

标签

归档



View My Stats