南大 ICS

南大 ICS

fetch150zy
  2022-03-13 01:29:46 2022-03-13 01:29:46 创建   2024-03-23 14:53 2024-03-23 14:53 更新    

nju ics

南京大学计算机系统基础习题课 Jyy

C语言拾遗 - 机制

  • 编译、链接
    • .c -> 预编译 -> .i -> 编译 -> .s -> 汇编 -> .o -> 链接 -> a.out
  • 加载执行
    • ./a.out

RTFM: man gcc

better: tldr

一些命令行工具

  • file
  • readelf
  • objdump
  • …

GNU BinUtils

预处理器

#include<> 指令

1
2
#include <stdio.h>
#include "stdio.h"

#include 指令本质上就是在预处理阶段进行粘贴

看看下面这段有趣的代码: 

1
2
3
4
5
6
#include <stdio.h>
int main(void) {
    printf(
    #include "hello.h"
    );
}
1
2
// hello.h
"hello\n"
  • <>: 优先在系统级目录下寻找头文件，如果找不到再到当前目录下寻找
    • 可以使用gcc --verbose来查看到底查找了哪些目录
  • “ “: 优先在当前目录下寻找

上面两种情况假设我们没有在编译时通过 -I 来指定头文件目录

例子

1
2
3
4
5
6
7
8
#include <stdio.h>
int main(void) {
   	#if aa == bb
    printf("Yes\n");
    #else
    printf("No\n");
    #endif
}

上面这段代码会输出 Yes，这是因为在C预处理器中，如果一个宏没有被定义，那么它在条件编译表达式中的值会被视为0

#if aa == bb被替换成了#if 0 == 0，这是一个true条件

如何躲过 Online Judge 的关键字过滤

1
#define SYSTEM sys ## tem

## 宏拼接

如何毁掉一个身边的同学

1
#define true (__LINE__ % 16 != 0)

X-Macros

1
2
3
4
5
6
#define NAMES(X) \
	X(Tom) X(Jerry) X(Tyke) X(Spike)
int main() {
    #define PRINT(x) puts("Hello, " #x "!");
    NAMES(PRINT)
}

发生在实际编译之前

  • 也成为元编程(meta-programming)
    • gcc的预处理器同样可以处理汇编代码
    • C++中的模板元编程，Rust的macros等

编译和链接

C是高级的汇编语言

链接

将多个二进制目标文件拼接到一起

  • C中的编译单元( compilation unit )
  • 甚至可以链接C++, Rust, …

加载

C程序执行的两个视角

静态：C代码的连续一段总能对应到一段连续的机器指令

动态：C代码执行的状态总能对应到机器的状态

  • 源代码视角
    • 函数、变量、指针…
  • 机器指令视角
    • 寄存器、内存、地址

两个视角的共同之处

  • 代码、变量（源代码视角）= 地址 +长度（机器指令视角）
  • （不太严谨的）内存 = 代码 +数据 +堆栈

从main函数开始

谁调用的main？进程执行的第一条指令是什么？

第一个问题，谁调用了main

  • main实际上是由C运行库中的启动代码(startup code)调用的，这个启动代码代码程序的执行入口点(entry point)，通常是名为_start的函数
    程序的执行从_start开始，它负责执行所有必要的运行时初始化，包括设置堆栈、初始化全局和静态变量、调用全局构造函数等，然后调用main函数

第二个问题，进程执行的第一条指令是什么

  • 进程执行的第一条指令是在_start函数中，这是由C运行时库提供的，不是开发者编写的C代码的一部分。_start是程序与操作系统交互的桥梁，它由操作系统在加载程序到内存并准备执行时设置。_start函数的具体职责包括：
    • 初始化程序执行环境
    • 调用全局和静态变量的构造函数（在C++中）
    • 设置参数（argc、argv）以供main函数使用
    • 调用main函数，并传递适当的参数
    • 捕获main函数的返回值，并将其传递给操作系统（通过调用exit函数或类似机制）
1
int main(int argc, cahar *argv[]);
  • argc: 参数个数
  • argv: 参数列表

C Type System

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include <asset.h>

int main(int argc, char **argv) {
    int (*f)(int, char *[]) = main;
    if (argc != 0) {
        char ***a = &argv, *first = argv[0], ch = argv[0][0];
        printf("arg = \"%s\"; ch = '%c'\n", first, ch);
        assert(***a == ch);
        f(argc - 1, arhv + 1);
    }
}

C语言拾遗 - 编程实践

例子

人类不可读版本

1
void (*signal(int sig, void (*func)(int)))(int);

人类可读版本

1
2
typedef void (*sighandler_t)(int);
sighandler_t signal(int, sighander_t);

数字逻辑电路模拟器

状态模拟 +计算模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define FORALL_REGS(_) 	_(X) _(Y)
#define LOGIC 	X1 = !X && Y; \
				Y1 = !X && !Y;
#define DEFINE(X)	static int X, X##1;
#define UPDATE(X)	X = X##1;
#define PRINT(X)	printf(#X " = %d; ", X);

int main() {
    FORALL_REGS(DEFINE);
    DEFINE(X) DEF(Y)
    while(1) {
        FORALL_REGS(PRINT); putchar('\n'); sleep(1);
        LOGIC;
        FORALL_REGS(UPDATE);
    }
}

编写代码的准则：降低维护成本

Programs are meant to be read by humans and only incidentally for computers to execute. – D.E.Knuth

Y-Emulator

存储是计算机能实现“计算”的重要基础

  • 寄存器、内存

减少dependencies -> 降低代码耦合程度

代码实现和优化部分建议看原视频

框架代码选讲 - 编译运行

有个叫 -rf的文件如何删除

显然rm -rf不起作用，使用rm -- rf，其中--会将其后参数解释为文件名

大概就是从make（构建工具）的角度来解析项目结构，从有向无环图的角度来解释make构建的目标依赖

UNIX哲学可以帮助你更好的阅读代码

基本原则：任何感到不爽的事情一定有工具能帮你

代码框架选讲 - 代码导读

建议看原视频

数据的机器级表示 - 整数和浮点数

位运算

位运算有很多骚操作，感兴趣的可以做一下cmu 15-213的data lab

这里老师推荐了一本书：Hacker’s Delight

IEEE 754是一个非常复杂的标准，这里Jyy举了一个倒速平方根的例子（出自雷神之锤III）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
float Q_rsqrt( float number ) {
    long i;
    float x2, y;
    const float threehalfs = 1.5F;
    
    x2 = number * 0.5F;
    y = number;
    i = * ( long * ) &y;						// evil floating point bit hack
    i = 0x5f3759df - (i >> 1);					// what the fuck?
    y = * ( float * ) &i;
    y = y * ( threehalfs - ( x2 * y * y ) );	// 1st iteration
 // y = y * ( threehalfs - ( x2 * y * y ) );	// 2nd iteration, can be removed
    
    return y;
}

讲解

汇编 /内联汇编选讲 - x86-64

书籍推荐：Richard.Blum 编程语言程序设计

关于int类型的长度

  • 8 bit computer: 8 bit
  • 16 bit computer: 16bit
  • 32 bit computer: 32 bit
  • 64 bit computer: 32 bit
  • JVM (32/64 bit): 32 bit

ABI

只要遵循某种标准的二进制文件就可以相互调用

区别于API (Application Programming Interface)

  • 程序源代码中的规范

ABI: 约束binary的行为

  • 二进制文件的格式
  • 函数调用、系统调用
    • C语言规范只定义了运行时内存和内存上的计算
    • printf都无法实现，必须借助外部库函数
  • 链接、加载的规范

例子: cdecl 函数调用

caller stack frame:

  • 所有参数以数组的形式保存在堆栈上 (反序压栈)
  • 返回地址
  • 跳转到callee

callee:

  • EAX作为返回寄存器
  • 其他寄存器都是callee save

跳转采用的是相对地址，且相对位置为当前指令的尾部，即下一条指令的开头

e.g.

1
2
3
4
5
void bar(int *);
int foo(int x) {
    bar(&x);
    return x;
}
1
2
gcc -m32 -O2 -fno-pic -c a.c
objdump -d a.o

我们可以得到非常易读的汇编

1
2
3
4
5
6
7
8
9
10
11
Disassembly of section .text:

00000000 <foo>:
   0:	83 ec 18             	sub    $0x18,%esp
   3:	8d 44 24 1c          	lea    0x1c(%esp),%eax
   7:	50                   	push   %eax
   8:	e8 fc ff ff ff       	call   9 <foo+0x9>
   d:	8b 44 24 20          	mov    0x20(%esp),%eax
  11:	83 c4 1c             	add    $0x1c,%esp
  14:	c3                   	ret

SAT Solver -> SMT Solver

寄存器与函数调用

Q: 为什么x86-64要采用寄存器传参？

  • 简化代码
  • 减少访存
  • 编译器有了更大的优化空间

Inline Assembly

编译器：把C代码“原样翻译”成汇编代码

1
2
3
4
5
6
7
int foo(int x, int y) {
    x++; y++;
    asm ("endbr64;"
        ".byte 0xf3, 0x0f, 0x1e, 0xfa"
    );
    return x + y;
}
1
gcc -O0 -c a.c -o a.o && objdump -d a.o
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Disassembly of section .text:

0000000000000000 <foo>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   89 7d fc                mov    %edi,-0x4(%rbp)
   7:   89 75 f8                mov    %esi,-0x8(%rbp)
   a:   83 45 fc 01             addl   $0x1,-0x4(%rbp)
   e:   83 45 f8 01             addl   $0x1,-0x8(%rbp)
  12:   f3 0f 1e fa             endbr64
  16:   f3 0f 1e fa             endbr64
  1a:   8b 55 fc                mov    -0x4(%rbp),%edx
  1d:   8b 45 f8                mov    -0x8(%rbp),%eax
  20:   01 d0                   add    %edx,%eax
  22:   5d                      pop    %rbp
  23:   c3                      ret

e.g.

1
2
3
4
5
6
7
8
9
10
11
int foo(int x, int y) {
    int z;
    x++; y++;
    asm (
    	"addl %1, %2; "
        "movl %2, %0; "
        : "=r"(z)			// output
        : "r"(x), "r"(y)	// input
    );
    return z;
}
1
gcc -O0 -c a.c -o a.o && objdump -d a.o
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Disassembly of section .text:

0000000000000000 <foo>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   89 7d ec                mov    %edi,-0x14(%rbp)
   7:   89 75 e8                mov    %esi,-0x18(%rbp)
   a:   83 45 ec 01             addl   $0x1,-0x14(%rbp)
   e:   83 45 e8 01             addl   $0x1,-0x18(%rbp)
  12:   8b 45 ec                mov    -0x14(%rbp),%eax
  15:   8b 55 e8                mov    -0x18(%rbp),%edx
  18:   01 c2                   add    %eax,%edx
  1a:   89 d0                   mov    %edx,%eax
  1c:   89 45 fc                mov    %eax,-0x4(%rbp)
  1f:   8b 45 fc                mov    -0x4(%rbp),%eax
  22:   5d                      pop    %rbp
  23:   c3                      ret

链接和加载

推荐: GNU Binutils

一个最小的可执行程序

e.g.

1
2
3
mov $0xe7, %rax
mov $0x01, %rdi
syscall

返回 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <stdlib.h>

__attribute__((constructor)) void start() {
    printf("Hello\n");
}

__attribute__((destructor)) void end() {
    printf("Bye\n");
}

int main(void) {
    atexit(end);

    printf("This is main func\n");
    return 0;
}

动态链接

Q: 为什么需要动态链接？

  • 静态链接导致可执行文件太大了

操作系统启动动态链接依赖的可执行文件

通过 /lib64/ld-linux-x86-64.so.2

也就是说我们在执行具有动态链接依赖的可执行文件时

./a.out 和 /lib64/ld-linux-x86-64.so.2 ./a.out 是等价的

动态链接的实现

AbstractMachine

主要讲了计算机的发展历史，建议看原视频

I/O设备

两个特殊的I/O设备

总线

  • 系统里可能有很多（甚至是可变的）I/O设备
    • 总线实现了设备的查找、映射、命令/数据的转发
  • CPU可以只直接连接到总线
    • 总线可以连接其他总线
    • 例子：lspci -t, lsusb -t

中断控制器

  • 管理多个产生中断的设备
    • 汇总成一个中断的设备
    • 支持中断表的屏蔽、优先级管理等

调试：理论与实践

已知程序有bug，如何找到？

调试理论

实际中的调试：通过观察程序执行的轨迹(trace)

  • 缩小错误状态 (error) 可能产生的位置
  • 作出适当的假设
  • 再进行细粒度的定位和诊断

最重要的两个工具

  • printf -> 自定义log的trace
    • 灵活可控、能快速定位问题大概位置、适用于大型软件
    • 无法精确定位、大量的logs管理起来比较麻烦
  • gdb -> 指令/语句级trace
    • 精确、指令级定位、任意查看程序内部状态
    • 耗费大量时间

调试理论：应用

问题诊断其实也是调试

需求 -> 设计 -> 代码 -> Fault -> Error -> Failure

什么是好的程序？

  • 不言自明：能知道是做什么的(specification)
    • 代码风格很重要
  • 不言自证：能确认代码和specification一致
    • 代码中的逻辑流很重要

程序首先是给人读的，其次才是被机器执行的

  1. 写好读、易验证的代码
  2. 在代码中添加更多的断言

断言的意义

把代码中隐藏的 specification 写出来

  • Fault -> Error (靠测试)
  • Error -> Failure (靠断言)
    • Erro 暴露的越晚，越难调试
    • 追溯导致assert failure的变量值(slice)通常可以快速定位到bug

例子：维护父亲节点的平衡树

e.g.

1
2
3
4
5
6
7
8
9
10
// 结构约束
assert(u->parent == u ||
       u->parent->left == u ||
       u->parent->right == u);
assert(!u->left || u->left->parent == u);
assert(!u->right || u->right->parent == u);

// 数值约束
assert(!u->left || u->left->val < u->val);
assert(!u->right || u->right->val > u->val);

一个神奇的编译选项

  • -fsanitize-address
    • Address Sanitizer，动态程序分析

系统编程与基础设施

论软件自动化可以帮你节省多少时间

gdb有外部接口，可以远程调试

Differential Testing

感觉和对拍差不多

中断与分时多任务

有时把异常成为同步中断

x86-64中断过程

比函数调用复杂一些

  • 函数调用需要保存PC到堆栈 (%rsp)
    • 但中断不仅要保存PC (尤其是在有特权级切换的时候)

中断处理

  • 自动保存 RIP, CS, RFLAGS, RSP, SS (Error Code)
  • 根据中断/异常号跳转到处理程序（特权级切换会触发堆栈切换）
    • int &$0x80指令可以产生128号异常
    • 时钟会产生32号中断
    • 键盘会产生33号中断
    • …

虚拟存储

此页目录
南大 ICS
  1. nju ics
    1. C语言拾遗 - 机制
      1. 一些命令行工具
    2. 预处理器
      1. #include<> 指令
      2. 例子
    3. 编译和链接
      1. 链接
    4. 加载
      1. C程序执行的两个视角
      2. 从main函数开始
      3. C Type System
  2. C语言拾遗 - 编程实践
    1. 例子
    2. 编写代码的准则：降低维护成本
  3. Y-Emulator
  • 框架代码选讲 - 编译运行
  • 代码框架选讲 - 代码导读
  • 数据的机器级表示 - 整数和浮点数
    1. 位运算
  • 汇编 /内联汇编选讲 - x86-64
    1. ABI
    2. 例子: cdecl 函数调用
    3. 寄存器与函数调用
    4. Inline Assembly
  • 链接和加载
    1. 一个最小的可执行程序
    2. 动态链接
      1. 动态链接的实现
  • AbstractMachine
  • I/O设备
    1. 两个特殊的I/O设备
      1. 总线
      2. 中断控制器
  • 调试：理论与实践
    1. 调试理论
    2. 调试理论：应用
      1. 断言的意义
      2. 例子：维护父亲节点的平衡树
  • 系统编程与基础设施
    1. Differential Testing
  • 中断与分时多任务
    1. x86-64中断过程
  • 虚拟存储