1.简介

在v2.6.0的内核中，为了更好地调试内核，引入新的功能kallsyms.
kallsyms把内核用到的所有函数地址和名称连接进内核文件，当内核启动
后，同时加载到内存中.
当发生oops，例如在内核中访问空地址时，内核就会解析eip位于哪个函
数中，并打印出形如
EIP is at cleanup_module+0xb/0x1d [client]的信息,
调用栈也用可读的方式显示出来.
Call Trace:
[<c013096d>] sys_delete_module+0x191/0x1ce
[<c02dd30a>] do_page_fault+0x189/0x51d
[<c0102bc1>] syscall_call+0x7/0xb

当然功能不仅仅于此，还可以查找某个函数例如的sys_fork的地址，然后
hook它，kprobe就是这么干的。

在v2.6.20中,还可以包含所有符号的地址，应此功能更强大，就相当于内核中
有了System.map了,此时查找sys_call_table的地址易如反掌。

2.sym的生成

内核编译的后阶段,make会执行
nm -n vmlinux|scripts/kallsyms
nm -n vmlinux生成所有的内核符号,并按地址排序,形如
c0100000 T startup_32
c0100000 A _text
c01000c6 t checkCPUtype
c0100147 t is486
c010014e t is386
c010019f t L6
c01001a1 t check_x87
c01001ca t setup_idt
c01001e7 t rp_sidt
c01001f4 t ignore_int
c0100228 T calibrate_delay
c0100228 T stext
c0100228 T _stext
c010036b t rest_init
c0100410 t do_pre_smp_initcalls
c0100415 t run_init_process
v2.6.0的行数是2.5万左右

scripts/kallsyms则处理这个列表，并生成连接所需的S文件kallsyms.S
v2.6.0中形如
#include <asm/*.h>
#if BITS_PER_LONG == 64
#define PTR .quad
#define ALGN .align 8
#else
#define PTR .long
#define ALGN .align 4
#endif
.data
.globl kallsyms_addresses
ALGN
kallsyms_addresses:
PTR 0xc0100228
PTR 0xc010036b
PTR 0xc0100410
PTR 0xc0100415
PTR 0xc010043c
PTR 0xc0100614
...
.globl kallsyms_num_syms
ALGN
kallsyms_num_syms:
PTR 11228

.globl kallsyms_names
ALGN
kallsyms_names:
.byte 0x00
.asciz "calibrate_delay"
.byte 0x00
.asciz "stext"
.byte 0x00
.asciz "_stext"
...
1)kallsyms_addresses数组包含所有内核函数的地址(经过排序的),
v2.6.0中相同的地址在kallsyms_addresses中只允许出现一次，到后面的版本例如
相同的地址可以出现多次，这样就允许同地址函数名的出现。
例如
kallsyms_addresses:
PTR 0xc0100228
PTR 0xc0100228
PTR 0xc0100228
PTR 0xc010036b
kallsyms_names:
.byte 0x00
.asciz "calibrate_delay"
.byte 0x00
.asciz "stext"
.byte 0x00
.asciz "_stext"
.byte 0x00
.asciz "rest_init"
当查找某个地址时所在的函数时，v2.6.0采用的是线性法，从头到尾地找，很低效，后来改成了
了折半查找，效率好多了。

2)kallsyms_num_syms是函数个数

3)kallsyms_names是函数名组成的一个大串,这个大串是有许多小串组成,格式是
.byte len
.asciz 压缩串
len代表本函数名和前一函数名相同前缀的大小，例如
.byte 0x00
.asciz "early_param_test"
.byte 0x06
.asciz "setup_test"
.byte 0x06,说明串setup_test和串early_parm_test有着相同的前缀，长为6，
即early_,所有setup_test终解压后的函数名为early_setup_test.
由于没有其他的辅助手段，函数名的解析过程也很低效,从头一直解析到该函数位置为止。

在后来的版本中，算法有了改善，使用了偏移索引和高频字符串压缩。
先建立token的概念,token就是所有函数名中，出现频率非常高的那些字符串.由于标识符命名
规则的限制，有许多ascii字符是未用到的，那么，可以用这些字符去替代这些高频串。
例如下面的例子
字符值 字符代表的串
190 .asciz "t.text.lock."
191 .asciz "text.lock."
192 .asciz "t.lock."
193 .asciz "lock."
210 .asciz "tex"
229 .asciz "t."
239 .asciz "loc"
249 .asciz "oc"
250 .asciz "te"

例如串.byte 0x03, 0xbe, 0xbc, 0x71的解析
串长3，
0xbe,190 .asciz "t.text.lock."
0xbc,189 .asciz "ir"
0x71,113 .asciz "q"
所以该串解析后的值是 t.text.lock.irq,注意实际的串值是.text.lock.irq,前面的t是类型,这是新版本加入的功能，将类型字符放在符号前

.byte 0x02, 0x08, 0xc2
串长2，
0x08,8 .asciz "Tide_"
0xc2,194 .asciz "init"
所以该串解析后的值是 Tide_init，即ide_init


为了解析而设置了数据结构kallsyms_token_table和kallsyms_token_index
kallsyms_token_table记录每个ascii字符的替代串，kallsyms_token_index
记录每个ascii字符的替代串在kallsyms_token_table中的偏移

而数据结构的改变是，把函数名每256个分一组，用一个数组kallsyms_markers记录这些组在
kallsyms_names中的偏移，这样查找就方便多了，不必从头来。


3.符号解析

v2.6.20
当发生oops时，
fastcall void __kprobes do_page_fault(struct pt_regs *regs,
unsigned long error_code)
{
...
die("Oops", regs, error_code);
...
}


void die(const char * str, struct pt_regs * regs, long err)
{
...
print_symbol("%s", regs->eip);//解析
...
}


static inline void print_symbol(const char *fmt, unsigned long addr)
{
__check_printsym_format(fmt, "");
__print_symbol(fmt, (unsigned long)
__builtin_extract_return_addr((void *)addr));
}


void __print_symbol(const char *fmt, unsigned long address)
{
char *modname;
const char *name;
unsigned long offset, size;
char namebuf[KSYM_NAME_LEN+1];
char buffer[sizeof("%s+%#lx/%#lx [%s]") + KSYM_NAME_LEN +
2*(BITS_PER_LONG*3/10) + MODULE_NAME_LEN + 1];
//解析地址，返回函数起始地址，大小，偏移，函数名
name = kallsyms_lookup(address, &size, &offset, &modname, namebuf);

if (!name)
sprintf(buffer, "0x%lx", address);
else {
if (modname)
//EIP is at cleanup_module+0xb/0x1d [client]
sprintf(buffer, "%s+%#lx/%#lx [%s]", name, offset,
size, modname);
else
sprintf(buffer, "%s+%#lx/%#lx", name, offset, size);
}
printk(fmt, buffer);
}

const char *kallsyms_lookup(unsigned long addr,
unsigned long *symbolsize,
unsigned long *offset,
char **modname, char *namebuf)
{
const char *msym;

namebuf[KSYM_NAME_LEN] = 0;
namebuf[0] = 0;

if (is_ksym_addr(addr)) {
unsigned long pos;
//取得大小和便宜
pos = get_symbol_pos(addr, symbolsize, offset);
/* Grab name */
//解析函数名
kallsyms_expand_symbol(get_symbol_offset(pos), namebuf);
*modname = NULL;
return namebuf;
}

/* see if it's in a module */
msym = module_address_lookup(addr, symbolsize, offset, modname);
if (msym)
return strncpy(namebuf, msym, KSYM_NAME_LEN);

return NULL;
}


static unsigned long get_symbol_pos(unsigned long addr,
unsigned long *symbolsize,
unsigned long *offset)
{
unsigned long symbol_start = 0, symbol_end = 0;
unsigned long i, low, high, mid;

/* This kernel should never had been booted. */
BUG_ON(!kallsyms_addresses);

/* do a binary search on the sorted kallsyms_addresses array */
low = 0;
high = kallsyms_num_syms;
//折半查找
while (high - low > 1) {
mid = (low + high) / 2;
if (kallsyms_addresses[mid] <= addr)
low = mid;
else
high = mid;
}

/*
* search for the first aliased symbol. Aliased
* symbols are symbols with the same address
*/
//找到个对齐的符号，即相同地址中的个
while (low && kallsyms_addresses[low-1] == kallsyms_addresses[low])
--low;

symbol_start = kallsyms_addresses[low];

/* Search for next non-aliased symbol */
//找到下一个不同的地址
for (i = low + 1; i < kallsyms_num_syms; i++) {
if (kallsyms_addresses > symbol_start) {
symbol_end = kallsyms_addresses;
break;
}
}

/* if we found no next symbol, we use the end of the section */
if (!symbol_end) {
if (is_kernel_inittext(addr))
symbol_end = (unsigned long)_einittext;
else if (all_var)
symbol_end = (unsigned long)_end;
else
symbol_end = (unsigned long)_etext;
}

*symbolsize = symbol_end - symbol_start;
*offset = addr - symbol_start;

return low;//返回个
}

//返回符号在kallsyms_names中的偏移
static unsigned int get_symbol_offset(unsigned long pos)
{
const u8 *name;
int i;

/* use the closest marker we have. We have markers every 256 positions,
* so that should be close enough */
//找到该组在kallsyms_names中的偏移
name = &kallsyms_names[ kallsyms_markers[pos>>8] ];

/* sequentially scan all the symbols up to the point we're searching for.
* Every symbol is stored in a [<len>][<len> bytes of data] format, so we
* just need to add the len to the current pointer for every symbol we
* wish to skip */
for(i = 0; i < (pos&0xFF); i++)
name = name + (*name) + 1;//在组中查找该符号的偏移

return name - kallsyms_names;//返回该符号的偏移
}

static unsigned int kallsyms_expand_symbol(unsigned int off, char *result)
{
int len, skipped_first = 0;
const u8 *tptr, *data;

/* get the compressed symbol length from the first symbol byte */
data = &kallsyms_names[off];//取该sym的首地址
len = *data;//取sym压缩后的长度
data++;//指向压缩串

/* update the offset to return the offset for the next symbol on
* the compressed stream */
off += len + 1;//指向下一个压缩串偏移

/* for every byte on the compressed symbol data, copy the table
entry for that byte */
while(len) {
//对于*data指向的字符，在token_index查找该字符所代表的解压串偏移，并从token_table中找到该解压串
tptr = &kallsyms_token_table[ kallsyms_token_index[*data] ];
data++;
len--;

while (*tptr) {
if(skipped_first) {//跳过类型字符，例如t,T
*result = *tptr;//拷贝解压串
result++;
} else
skipped_first = 1;
tptr++;
}
}

*result = '\0';

/* return to offset to the next symbol */
return off;//返回下一个压缩串偏移
}

文章来源CU社区：kallsyms的分析