复习
- 可执行文件:一个描述了状态机的初始状态 (迁移) 的 数据结构
本次课回答的问题
- Q1: 可执行文件是如何被操作系统加载的?
- Q2: 什么是动态链接/动态加载?
本次课主要内容
- 若干真正的静态 ELF 加载器
- 动态链接和加载
可执行文件
- 一个描述了状态机的初始状态 (迁移) 的数据结构
- 不同于内存里的数据结构,“指针” 都被 “偏移量” 代替
- 数据结构各个部分定义:
/usr/include/elf.h
加载器 (loader)
- 解析数据结构 + 复制到内存 + 跳转
- 创建进程运行时初始状态 (argv, envp, ...)
- loader-static.c
- 可以加载任何静态链接的代码 minimal.S, dfs-fork.c
- 并且能正确处理参数/环境变量 env.c
- RTFM: System V ABI Figure 3.9 (Initial Process Stack)
- loader-static.c
// loader-static.c
运行在用户态,最主要的是用 mmap 系统调用,把 elf 文件中的数据搬到内存中的某个位置
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <assert.h>
#include <elf.h>
#include <fcntl.h>
#include <sys/mman.h>
#define STK_SZ (1 << 20)
#define ROUND(x, align) (void *)(((uintptr_t)x) & ~(align - 1))
#define MOD(x, align) (((uintptr_t)x) & (align - 1))
#define push(sp, T, ...) ({ *((T*)sp) = (T)__VA_ARGS__; sp = (void *)((uintptr_t)(sp) + sizeof(T)); })
void execve_(const char *file, char *argv[], char *envp[]) {
// WARNING: This execve_ does not free process resources.
int fd = open(file, O_RDONLY);
assert(fd > 0);
Elf64_Ehdr *h = mmap(NULL, 4096, PROT_READ, MAP_PRIVATE, fd, 0);
assert(h != (void *)-1);
assert(h->e_type == ET_EXEC && h->e_machine == EM_X86_64);
Elf64_Phdr *pht = (Elf64_Phdr *)((char *)h + h->e_phoff);
for (int i = 0; i < h->e_phnum; i++) {
Elf64_Phdr *p = &pht[i];
if (p->p_type == PT_LOAD) {
int prot = 0;
if (p->p_flags & PF_R) prot |= PROT_READ;
if (p->p_flags & PF_W) prot |= PROT_WRITE;
if (p->p_flags & PF_X) prot |= PROT_EXEC;
void *ret = mmap(
ROUND(p->p_vaddr, p->p_align), // addr, rounded to ALIGN
p->p_memsz + MOD(p->p_vaddr, p->p_align), // length
prot, // protection
MAP_PRIVATE | MAP_FIXED, // flags, private & strict
fd, // file descriptor
(uintptr_t)ROUND(p->p_offset, p->p_align)); // offset
assert(ret != (void *)-1);
memset((void *)(p->p_vaddr + p->p_filesz), 0, p->p_memsz - p->p_filesz);
}
}
close(fd);
static char stack[STK_SZ], rnd[16];
void *sp = ROUND(stack + sizeof(stack) - 4096, 16);
void *sp_exec = sp;
int argc = 0;
// argc
while (argv[argc]) argc++;
push(sp, intptr_t, argc);
// argv[], NULL-terminate
for (int i = 0; i <= argc; i++)
push(sp, intptr_t, argv[i]);
// envp[], NULL-terminate
for (; *envp; envp++) {
if (!strchr(*envp, '_')) // remove some verbose ones
push(sp, intptr_t, *envp);
}
// auxv[], AT_NULL-terminate
push(sp, intptr_t, 0);
push(sp, Elf64_auxv_t, { .a_type = AT_RANDOM, .a_un.a_val = (uintptr_t)rnd } );
push(sp, Elf64_auxv_t, { .a_type = AT_NULL } );
asm volatile(
"mov $0, %%rdx;" // required by ABI
"mov %0, %%rsp;"
"jmp *%1" : : "a"(sp_exec), "b"(h->e_entry));
}
int main(int argc, char *argv[], char *envp[]) {
if (argc < 2) {
fprintf(stderr, "Usage: %s file [args...]\n", argv[0]);
exit(1);
}
execve_(argv[1], argv + 1, envp);
}
$ gcc loader-static.c -o loader
$ loader [静态链接的文件]
$ strace loader [静态链接的文件]
# 就开头有些loader的execve的系统调用,后面都没有的
# 在执行hello world前面是些 mmap
意味着使用 loader 不使用 execve ,只使用 mmap 就能加载静态的 ELF 文件
还是在操作系统上实现的,即用 open mmap close 实现了 execve
加载操作系统内核?
- 也是一个 ELF 文件
- 解析数据结构 + 复制到内存 + 跳转
和 elf loader 本质上没区别
bootmain.c (i386/x86-64 通用)
- 之前给大家调试过
- 不花时间调试了
- 马上有重磅主角登场
#include <stdint.h>
#include <elf.h>
#include <x86/x86.h>
#define SECTSIZE 512
#define ARGSIZE 1024
static inline void wait_disk(void) {
while ((inb(0x1f7) & 0xc0) != 0x40);
}
static inline void read_disk(void *buf, int sect) {
wait_disk();
outb(0x1f2, 1);
outb(0x1f3, sect);
outb(0x1f4, sect >> 8);
outb(0x1f5, sect >> 16);
outb(0x1f6, (sect >> 24) | 0xE0);
outb(0x1f7, 0x20);
wait_disk();
for (int i = 0; i < SECTSIZE / 4; i ++) {
((uint32_t *)buf)[i] = inl(0x1f0);
}
}
static inline void copy_from_disk(void *buf, int nbytes, int disk_offset) {
uint32_t cur = (uint32_t)buf & ~(SECTSIZE - 1);
uint32_t ed = (uint32_t)buf + nbytes;
uint32_t sect = (disk_offset / SECTSIZE) + (ARGSIZE / SECTSIZE) + 1;
for(; cur < ed; cur += SECTSIZE, sect ++)
read_disk((void *)cur, sect);
}
static void load_program(uint32_t filesz, uint32_t memsz, uint32_t paddr, uint32_t offset) {
copy_from_disk((void *)paddr, filesz, offset);
char *bss = (void *)(paddr + filesz);
for (uint32_t i = filesz; i != memsz; i++) {
*bss++ = 0;
}
}
static void load_elf64(Elf64_Ehdr *elf) {
Elf64_Phdr *ph = (Elf64_Phdr *)((char *)elf + elf->e_phoff);
for (int i = 0; i < elf->e_phnum; i++, ph++) {
load_program(
(uint32_t)ph->p_filesz,
(uint32_t)ph->p_memsz,
(uint32_t)ph->p_paddr,
(uint32_t)ph->p_offset
);
}
}
static void load_elf32(Elf32_Ehdr *elf) {
Elf32_Phdr *ph = (Elf32_Phdr *)((char *)elf + elf->e_phoff);
for (int i = 0; i < elf->e_phnum; i++, ph++) {
load_program(
(uint32_t)ph->p_filesz,
(uint32_t)ph->p_memsz,
(uint32_t)ph->p_paddr,
(uint32_t)ph->p_offset
);
}
}
void load_kernel(void) {
Elf32_Ehdr *elf32 = (void *)0x8000;
Elf64_Ehdr *elf64 = (void *)0x8000;
int is_ap = boot_record()->is_ap;
if (!is_ap) {
// load argument (string) to memory
copy_from_disk((void *)MAINARG_ADDR, 1024, -1024);
// load elf header to memory
copy_from_disk(elf32, 4096, 0);
if (elf32->e_machine == EM_X86_64) {
load_elf64(elf64);
} else {
load_elf32(elf32);
}
} else {
// everything should be loaded
}
if (elf32->e_machine == EM_X86_64) {
((void(*)())(uint32_t)elf64->e_entry)();
} else {
((void(*)())(uint32_t)elf32->e_entry)();
}
}
loader-static.c, bootmain.c 和 Linux 有本质区别吗?没有!
- 解压缩源码包
make menuconfig
(生成 .config 文件)make bzImage -j8
- 顺便给 Kernel 个补丁 (kernel/exit.c)
编译结果
- vmlinux (ELF 格式的内核二进制代码)
- vmlinuz (压缩的镜像,可以直接被 QEMU 加载)
- readelf 入口地址 0x1000000 (物理内存 16M 位置)
__startup_64
: RTFSC; 调试起来!- 时刻告诉自己:不要怕,就是状态机 (和你们的 lab 完全一样)
fs/binfmt_elf.c
: load_elf_binary
- 这里我们看到了 Linux Kernel 里的面向对象 (同我们的 oslab)
[00:50:00] 开始讲解使用vscode 调试 linux kernel
让我们愉快地打个断点……
- 当然是使用正确的工具了
script/gen_compile_commands.py
- 思考题: 如何实现 “自动” 获得所有编译选项的工具?
- vscode 快捷键
⌃/⌘ + P (@, #)
⌃/⌘ + ⇧ + P
任何你不知道按什么键的时候,搜索!
- Linux Kernel 也不过如此!
- 你们需要一个 “跨过一道坎” 的过程
随着库函数越来越大,希望项目能够 “运行时链接”。
减少库函数的磁盘和内存拷贝
- 每个可执行文件里都有所有库函数的拷贝那也太浪费了
- 只要大家遵守基本约定,不挑库函数的版本
- “Semantic Versioning”
- 否则发布一个新版本就要重新编译全部程序
大型项目的分解
- 编译一部分,不用重新链接
- libjvm.so, libart.so, ...
- NEMU: “把 CPU 插上 board”
和 ELF battle 的每一年:讲着讲着就讲不下去了
- 其实不是讲不清楚,是大家跟不上
- 根本原因:概念上紧密相关的东西在数据结构中被强行 “拆散” 了
GOT[0]
,GOT[1]
, ... ???
- 根本原因:概念上紧密相关的东西在数据结构中被强行 “拆散” 了
换一种方法
- 如果编译器、链接器、加载器都受你控制
- 你怎么设计、实现一个 “最直观” 的动态链接格式?
- 再去考虑怎么改进它,你就得到了 ELF!
- 假设编译器可以为你生成位置无关代码 (PIC)
动态链接的符号查表就行了嘛。
DL_HEAD
LOAD("libc.dl") # 加载动态库
IMPORT(putchar) # 加载外部符号
EXPORT(hello) # 为动态库导出符号
DL_CODE
hello:
...
call DSYM(putchar) # 动态链接符号
...
DL_END
编译器
- 开局一条狗,出门全靠偷 (GCC, GNU as)
binutils
- ld = objcopy (偷来的)
- as = GNU as (偷来的)
- 剩下的就需要自己动手了
- readdl (readelf)
- objdump
- 你同样可以山寨 addr2line, nm, objcopy, ...
和最重要的加载器
- 这个也得自己动手了
头文件
- dl.h (数据结构定义)
“全家桶” 工具集
- dlbox.c (gcc, readdl, objdump, interp)
示例代码
- libc.S - 提供 putchar 和 exit
- libhello.S - 调用 putchar, 提供 hello
- main.S - 调用 hello, 提供 main调用 hello, 提供 main
- (假装你的高级语言编译器可以生成这样的汇编代码)
$ gcc -g dlbox.c -o dlbox
$ ./dlbox gcc libc.S
$ ./dlbox gcc libhello.S
$ ./dlbox gcc main.S
会生成 .dl 格式的可执行文件,这个可执行文件不能在自己的操作系统上执行的,必须用自己的加载器来加载,因为是自己设计的二进制文件格式
$ ./dlbox readdl libc.dl
DLIB file libc.dl:
00000080 putchar
000000a7 exit
$ ./dlbox readdl main.dl
DLIB file main.dl:
LOAD libc.dl
LOAD libhello.dl
EXTERN hello
000000c0 main
$ ./dlbox readdl libhello.dl
DLIB file libhello.dl:
LOAD libc.dl
EXTERN putchar
000000a0 hello
$ ./dlbox objdump *.dl
// dl.h
#define REC_SZ 32
#define DL_MAGIC "\x01\x14\x05\x14"
#ifdef __ASSEMBLER__
#define DL_HEAD __hdr: \
/* magic */ .ascii DL_MAGIC; \
/* file_sz */ .4byte (__end - __hdr); \
/* code_off */ .4byte (__code - __hdr)
#define DL_CODE .fill REC_SZ - 1, 1, 0; \
.align REC_SZ, 0; \
__code:
#define DL_END __end:
#define RECORD(sym, off, name) \
.align REC_SZ, 0; \
sym .8byte (off); .ascii name
#define IMPORT(sym) RECORD(sym:, 0, "?" #sym "\0")
#define EXPORT(sym) RECORD( , sym - __hdr, "#" #sym "\0")
#define LOAD(lib) RECORD( , 0, "+" lib "\0")
#define DSYM(sym) *sym(%rip)
#else
#include <stdint.h>
struct dl_hdr {
char magic[4];
uint32_t file_sz, code_off;
};
struct symbol {
int64_t offset;
char type, name[REC_SZ - sizeof(int64_t) - 1];
};
#endif
// dlbox.c
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdbool.h>
#include <unistd.h>
#include <sys/mman.h>
#include <fcntl.h>
#include "dl.h"
#define SIZE 4096
#define LENGTH(arr) (sizeof(arr) / sizeof(arr[0]))
struct dlib {
struct dl_hdr hdr;
struct symbol *symtab; // borrowed spaces from header
const char *path;
};
static struct dlib *dlopen(const char *path);
struct dlib *dlopen_chk(const char *path) {
struct dlib *lib = dlopen(path);
if (!lib) {
fprintf(stderr, "Not a valid dlib file: %s.\n", path);
exit(1);
}
return lib;
}
// Implementation of binutils
void dl_gcc(const char *path) {
char buf[256], *dot = strrchr(path, '.');
if (dot) {
*dot = '\0';
sprintf(buf, "gcc -m64 -fPIC -c %s.S && "
"objcopy -S -j .text -O binary %s.o %s.dl", path, path, path);
system(buf);
}
}
void dl_readdl(const char *path) {
struct dlib *h = dlopen_chk(path);
printf("DLIB file %s:\n\n", h->path);
for (struct symbol *sym = h->symtab; sym->type; sym++) {
switch (sym->type) {
case '+': printf(" LOAD %s\n", sym->name); break;
case '?': printf(" EXTERN %s\n", sym->name); break;
case '#': printf( "%08lx %s\n", sym->offset, sym->name); break;
}
}
}
void dl_objdump(const char *path) {
struct dlib *h = dlopen_chk(path);
char *hc = (char *)h, cmd[64];
FILE *fp = NULL;
printf("Disassembly of binary %s:\n", h->path);
for (char *code = hc + h->hdr.code_off; code < hc + h->hdr.file_sz; code++) {
for (struct symbol *sym = h->symtab; sym->type; sym++) {
if (hc + sym->offset == code) {
int off = code - hc - h->hdr.code_off;
if (fp) pclose(fp);
sprintf(cmd, "ndisasm - -b 64 -o 0x%08x\n", off);
fp = popen(cmd, "w");
printf("\n%016x <%s>:\n", off, sym->name);
fflush(stdout);
}
}
if (fp) fputc(*code, fp);
}
if (fp) pclose(fp);
}
// binutils: interpreter
void dl_interp(const char *path) {
struct dlib *h = dlopen_chk(path);
int (*entry)() = NULL;
for (struct symbol *sym = h->symtab; sym->type; sym++)
if (strcmp(sym->name, "main") == 0)
entry = (void *)((char *)h + sym->offset);
if (entry) {
exit(entry());
}
}
struct cmd {
const char *cmd;
void (*handler)(const char *path);
} commands[] = {
{ "gcc", dl_gcc },
{ "readdl", dl_readdl },
{ "objdump", dl_objdump },
{ "interp", dl_interp },
{ "", NULL },
};
int main(int argc, char *argv[]) {
if (argc < 3) {
fprintf(stderr, "Usage: %s {gcc|readdl|objdump|interp} FILE...\n", argv[0]);
return 1;
}
for (struct cmd *cmd = &commands[0]; cmd->handler; cmd++) {
for (char **path = &argv[2]; *path && strcmp(argv[1], cmd->cmd) == 0; path++) {
if (path != argv + 2) printf("\n");
cmd->handler(*path);
}
}
}
// Implementation of dlopen()
static struct symbol *libs[16], syms[128];
static void *dlsym(const char *name);
static void dlexport(const char *name, void *addr);
static void dlload(struct symbol *sym);
static struct dlib *dlopen(const char *path) {
struct dl_hdr hdr;
struct dlib *h;
int fd = open(path, O_RDONLY);
if (fd < 0) goto bad;
if (read(fd, &hdr, sizeof(hdr)) < sizeof(hdr)) goto bad;
if (strncmp(hdr.magic, DL_MAGIC, strlen(DL_MAGIC)) != 0) goto bad;
h = mmap(NULL, hdr.file_sz, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE, fd, 0);
if (h == (void *)-1) goto bad;
h->symtab = (struct symbol *)((char *)h + REC_SZ);
h->path = path;
for (struct symbol *sym = h->symtab; sym->type; sym++) {
switch (sym->type) {
case '+': dlload(sym); break; // (recursively) load
case '?': sym->offset = (uintptr_t)dlsym(sym->name); break; // resolve
case '#': dlexport(sym->name, (char *)h + sym->offset); break; // export
}
}
return h;
bad:
if (fd > 0) close(fd);
return NULL;
}
static void *dlsym(const char *name) {
for (int i = 0; i < LENGTH(syms); i++)
if (strcmp(syms[i].name, name) == 0)
return (void *)syms[i].offset;
assert(0);
}
static void dlexport(const char *name, void *addr) {
for (int i = 0; i < LENGTH(syms); i++)
if (!syms[i].name[0]) {
syms[i].offset = (uintptr_t)addr; // load-time offset
strcpy(syms[i].name, name);
return;
}
assert(0);
}
static void dlload(struct symbol *sym) {
for (int i = 0; i < LENGTH(libs); i++) {
if (libs[i] && strcmp(libs[i]->name, sym->name) == 0) return; // already loaded
if (!libs[i]) {
libs[i] = sym;
dlopen(sym->name); // load recursively
return;
}
}
assert(0);
}
// libc.S
#include "dl.h"
#include <sys/syscall.h>
DL_HEAD
EXPORT(putchar)
EXPORT(exit)
DL_CODE
putchar:
mov %dil, buf(%rip)
mov $SYS_write, %rax
mov $1, %rdi
lea buf(%rip), %rsi
mov $1, %rdx
syscall
ret
buf:
.byte 0
exit:
movq $SYS_exit, %rax
syscall
DL_END
// libhello.S
#include "dl.h"
DL_HEAD
LOAD("libc.dl")
IMPORT(putchar)
EXPORT(hello)
DL_CODE
hello:
lea str(%rip), %rdi
mov count(%rip), %eax
push %rbx
mov %rdi, %rbx
inc %eax
mov %eax, count(%rip)
add $0x30, %eax
movb %al, 0x6(%rdi)
loop:
movsbl (%rbx),%edi
test %dil,%dil
je out
call DSYM(putchar)
inc %rbx
jmp loop
out:
pop %rbx
ret
str:
.asciz "Hello X\n"
count:
.int 0
DL_END
// man.S
#include "dl.h"
DL_HEAD
LOAD("libc.dl")
LOAD("libhello.dl")
IMPORT(hello)
EXPORT(main)
DL_CODE
main:
call DSYM(hello)
call DSYM(hello)
call DSYM(hello)
call DSYM(hello)
movq $0, %rax
ret
DL_END
存储保护和加载位置
- 允许将 .dl 中的一部分以某个指定的权限映射到内存的某个位置 (program header table)
允许自由指定加载器 (而不是 dlbox)
- 加入 INTERP
空间浪费
- 字符串存储在常量池,统一通过 “指针” 访问
- 这是带来 ELF 文件难读的最根本原因
$ xxd main.dl
00000000: 0114 0514 e000 0000 c000 0000 0000 0000 ................
00000010: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000020: 0000 0000 0000 0000 2b6c 6962 632e 646c ........+libc.dl
00000030: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000040: 0000 0000 0000 0000 2b6c 6962 6865 6c6c ........+libhell
00000050: 6f2e 646c 0000 0000 0000 0000 0000 0000 o.dl............
00000060: 0000 0000 0000 0000 3f68 656c 6c6f 0000 ........?hello..
00000070: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000080: c000 0000 0000 0000 236d 6169 6e00 0000 ........#main...
00000090: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000c0: ff15 9aff ffff ff15 94ff ffff ff15 8eff ................
000000d0: ffff ff15 88ff ffff 48c7 c000 0000 00c3 ........H.......
其他:不那么重要
- 按需 RTFM/RTFSC
#define DSYM(sym) *sym(%rip)
DSYM 是间接内存访问
extern void foo();
foo();
一种写法,两种情况
- 来自其他编译单元 (静态链接)
- 直接 PC 相对跳转即可
- 动态链接库
- 必须查表 (编译时不能决定)
在写 C 代码的时候,在写 extern void foo();
的时候,在编译的时候不知道 foo 在那里,因为是个外部的符号
我们的 “符号表” 就是 Global Offset Table (GOT)
- 这下你不会理解不了 GOT 的概念了!
- 概念和名字都不重要,发明的过程才重要
统一静态/动态链接:都用静态!
- 增加一层 indirection: Procedure Linkage Table (PLT)
- 所有未解析的符号都统一翻译成 call
- 现代处理器都对这种跳转做了一定的优化 (e.g., BTB)
putchar@PLT:
call DSYM(putchar) # in ELF: jmp *GOT[n]
main:
call putchar@PLT
【1:39:56】
你会发现和我们的 “最小” 二进制文件几乎完全一样!
- ELF 还有一些额外的 hack (比如可以 lazy binding)
00000000000010c0 <printf@plt>:
10c0: endbr64
10c4: bnd jmpq *0x2efd(%rip) # DSYM(printf)
10cb: nopl 0x0(%rax,%rax,1)
00000000000011c9 <main>:
...
1246: callq 10c0 <printf@plt>
如果我们想要引用动态链接库里的数据?
- 数据不能增加一层 indirection
stdout/errno/environ 的麻烦
- 多个库都会用;但应该只有一个副本!
当然是做实验了!
- readelf 看看 stdout 有没有不同
- 再用 gdb 设一个 watch point
- 原来被特殊对待了
- 算是某种 “摆烂” (workaround) 了
#include <errno.h>
#include <stdio.h>
int x;
extern int y;
int main() {
fprintf(stdout, "%d\n", errno);
}
$ gcc a.c
$ readelf -a a.out | less
...
000000201010 000800000005 R_X86_64_COPY 0000000000201010 stdout@GLIBC_2.2.5 + 0
...
R_X86_64_COPY 由加载器保障 stdout 二进制只有唯一的副本
本次课回答的问题
- Q1: 可执行文件是如何被操作系统加载的?
- Q2: 什么是动态链接/动态加载?
Take-away messages
- 加载器
- 借助底层机制把数据结构按 specification “搬运”
- 动态链接/加载
- GOT, PLT 和最小二进制文件
- 啪的一下!很快啊!我们就进入了操作系统内核
- 没什么难的,就是个普通 C 程序