Yuan Yijun (bbbush) wrote,
Yuan Yijun
bbbush

关于 .gnu.hash

irc://freenode/fedora-cn

gagag 说,fc6 里面 KDE 速度快了。我想他指的应该是 .gnu.hash

http://fedoraproject.org/wiki/Docs/Beats/Devel/Tools

..changes in the ELF .hash section that provides symbols for dynamic linking...It provides an approximately 50% increase in dynamic linking speed.

正好 zhllg 上线,就问了下。果然,他七月份的一篇文章提到了,当时还看过呢。还有几个链接

http://lwn.net/Articles/192082/
http://sourceware.org/ml/libc-alpha/2006-06/msg00095.html
http://forums.gentoo.org/viewtopic-t-435659.html

觉得 gentoo 的 overlay 机制是 fedora 和 deb/ubuntu 系统远远比不上的。overlay 可以创造无限的可能,为不同的用户量身定制。那么好用的 use 是什么时候开发出来的呢。期待 hellwolf 的新作!

那,所谓 .gnu.hash 是使用了新的 hash 算法和 hash 布局。

The .gnu.hash section uses always sh_entsize 4 (so doesn't repeat the
historic mistakes on Alpha/s390x with .hash). The first word there is
nbuckets like in .hash section, followed by nbuckets offsets into the
chains area of the new section. If the offset is 0xffffffff, it means
there are no defined symbol names with hash % nbuckets equal to the
offset's position. Otherwise, offset N means the corresponding chain
starts at offset (1 + nbuckets + N) * 4 into .gnu.hash section. The
chain are does not mirror in size the symbol table anymore.

那个算法没看懂:

The hash function used is

static uint_fast32_t
dl_new_hash (const char *s)
{
uint_fast32_t h = 5381;
for (unsigned char c = *s; c != '\0'; c = *++s)
h = h * 33 + c;
return h & 0xffffffff;
}

(Dan Bernstein's string hash function posted eons ago on comp.lang.c.)



扩大了 hash 之后,冲突也就变少了;即使冲突,需要比较的内容也少了;最后,因为新的布局是把可选的值放在相邻的地址里,局部性更好了。所以才说在动态链接的查找符号时有了 50% 性能提升。预先编译的符号表是什么?<- 这说明,我根本就没懂~~ 睡了睡了。



zhllg 动态连接的时候需要解析符号
需要在本进程所加载的所有so文件里查找undefined Symbol
有了hash table,查找速度会加快
gnu hash style 是一种新的hash style
每个so里都有hash table
hers 怎么提高 hash 的速度呢..
仅仅扩大 hash 表么。
zhllg gnu hash style是把hash值相同的symbol放在一起
hers zhllg~ 升级到 --hash-style=GNU 的时候,是不是需要编译两次系统呢
zhllg~ http://udrepper.livejournal.com/
zhllg 我还没具体实践过,:P <- 骗人,gentoo 最近的 glibc 2.5 已经默认用它了。


hash 的 key 和 value 分别是什么

符号解析的目的,是把在程序里未定义的函数名解析为运行时该函数的内存地址。解析的过程就是查hash表,按惯常做法表里hash值相同的符号(就是未定义的函数名)组成链表。文章提到目前已经有的一个策略,就是prelink,这种方法的本质是修改二进制程序文件,在程序运行前就确定下来每个共享库文件在程序执行时的地址空间里的位置,当然包括每个函数的地址。但是 prelink有一定的安全隐患。同一个共享库在prelink过的所有程序的地址空间里的位置都是一样的。



zhllg hers, 比如你写个helloworld
用c
里面有个printf
hers 然后它会怎么找这个符号呢?
zhllg 这个printf函数本身是在libc里的
你的程序里并没有printf的代码
一丁点都没有
hers 先在自己的 hash table 里面找?找不到然后怎么就知道是在 libc 里面了?
zhllg 只有一个未解析的符号
不,只在so里找
自己肯定是没有的
不用找
所有的so被加载后会组成一个链表
hers 为什么不用找?
zhllg 然后就挨个找
hers .. /me 一窍不通的说
zhllg 可执行程序本身肯定没有printf的定义
除非是静态连接
就是把libc.so给包括在可执行程序里,这是静态连接
一般都是动态的
运行时才会知道 printf这个函数在内存里的地址
hers 哦,那,预编译的符号表,就是说先用 printf 计算出 hash key,不管在哪个 so 里面,hash key 都是一样的,是吧。
就是两次 hash,是吧。
“根据”,不是“用”
:p
过去怎么计算 hash key 的呢?
zhllg~ 是不是有那么个表,加载程序的时候就把 unresolved symbol 先列在里面,然后再加载 so,加载之后,重新解析一次符号?
* hers 打算重启试验一下..
zhllg 预编译符号表?
precomputed hashtable?
hers zhllg~ 反汇编是用什么命令?
zhllg~ 对,不明白那里.. 其实都不怎么明白
zhllg objdump -d



update:
又看了 zhllg 八月的一篇文章,讲 objdump -d 输出的分析。原来 .plt 段是这个样子~~ 虽然还是不懂。哎~~ 自己太笨了。

作实验ing

#include <stdio.h>
int main()
{
puts("ab");
}



Disassembly of section .plt:

08048264 <__gmon_start__@plt-0x10>:
8048264: ff 35 3c 95 04 08 pushl 0x804953c
804826a: ff 25 40 95 04 08 jmp *0x8049540
8048270: 00 00 add %al,(%eax)
...

08048274 <__gmon_start__@plt>:
8048274: ff 25 44 95 04 08 jmp *0x8049544
804827a: 68 00 00 00 00 push $0x0
804827f: e9 e0 ff ff ff jmp 8048264 <_init+0x18>

08048284 <__libc_start_main@plt>:
8048284: ff 25 48 95 04 08 jmp *0x8049548
804828a: 68 08 00 00 00 push $0x8
804828f: e9 d0 ff ff ff jmp 8048264 <_init+0x18>

08048294 <puts@plt>:
8048294: ff 25 4c 95 04 08 jmp *0x804954c
804829a: 68 10 00 00 00 push $0x10
804829f: e9 c0 ff ff ff jmp 8048264 <_init+0x18>




[yuan@mstar workspace]$ gdb -q a.out
(no debugging symbols found)
Using host libthread_db library "/lib/libthread_db.so.1".
(gdb) disas main
Dump of assembler code for function main:
0x08048354 <main+0>: lea 0x4(%esp),%ecx
0x08048358 <main+4>: and $0xfffffff0,%esp
0x0804835b <main+7>: pushl 0xfffffffc(%ecx)
0x0804835e <main+10>: push %ebp
0x0804835f <main+11>: mov %esp,%ebp
0x08048361 <main+13>: push %ecx
0x08048362 <main+14>: sub $0x4,%esp
0x08048365 <main+17>: movl $0x8048450,(%esp)
0x0804836c <main+24>: call 0x8048294 <puts@plt>
0x08048371 <main+29>: add $0x4,%esp
0x08048374 <main+32>: pop %ecx
0x08048375 <main+33>: pop %ebp
0x08048376 <main+34>: lea 0xfffffffc(%ecx),%esp
0x08048379 <main+37>: ret
0x0804837a <main+38>: nop
0x0804837b <main+39>: nop
0x0804837c <main+40>: nop
0x0804837d <main+41>: nop
0x0804837e <main+42>: nop
0x0804837f <main+43>: nop
End of assembler dump.
(gdb) disas 0x8048294
Dump of assembler code for function puts@plt:
0x08048294 <puts@plt+0>: jmp *0x804954c
0x0804829a <puts@plt+6>: push $0x10
0x0804829f <puts@plt+11>: jmp 0x8048264
End of assembler dump.
(gdb) x 0x804954c
0x804954c <_GLOBAL_OFFSET_TABLE_+20>: 0x0804829a
(gdb) disas 0x8048264
No function contains specified address.
(gdb) x 0x8048264
0x8048264: 0x953c35ff
(gdb) x 0x8049540
0x8049540 <_GLOBAL_OFFSET_TABLE_+8>: 0x00000000


做不下去了.. GOT 从 0x08049538 开始,因此 .plt 的第一项,pushl 推入的参数是 GOT 第二项,接下去 jump 的地址是 GOT 的第三项,就是加载 so 的时机。就是做不下去.. 因为第三项 *0x8049540 是 0 :(
JMPREL 第一项是指向 GOT 的第 4 项呢。当年操作系统课讲到这些的时候,咱们可是一个实验都没有做.. 追悔莫及 :(
Tags: fedora, 转载
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 3 comments