My CSAPP Note

double to unsigned long long

1 2	unsigned long long a = (unsinged long long)(2.0); // a==2 unsigned long long a = (unsinged long long)(-2.0); // a==140735559226888

double to long long用的是特殊的指令

以下代码比较奇怪

int main() {
    double a = 18446744073709552000.0;
    unsigned long long b= (unsigned long long)a;
    int p = (b==(double)a);
    printf("%llu, %d, %d\n", b, p, a==(double)(~0ULL)); // output 0, 0, 1
}

原因在于，~0ULL、18446744073709552000.0是无法被double精确表示的，他们转为double都是1<<64
注意，使用IDEA的debugger运行表达式（go程序），计算float64(1<<64-1)==18446744073709551616得到的是false

另外

1
2
3

val3 := 18446744073709551615.0
fmt.Println(int64(val3))
fmt.Println(uint64(val3))

得到的是-9223372036854775808和9223372036854775808

进程

进程是内核定义的抽象实体，并为该实体分配可用以执行程序的各项系统资源
提供一个假象：当前程序是OS中的唯一程序
定义：一个执行中的程序的实例
一个独立的逻辑控制流，一个私有的地址空间
地址空间，从低到高是
- x86-64从0x400000开始，x86-32从0x8048000开始，gcc的-fPIE(Position-independent executables)则会使得EP变成0x10a0，不清楚运行时是否会变
- 只读代码段（.init, .rodata, .text）
- 读/写段（.data, .bss），包含显式初始化的全局变量和静态变量，跟只读代码段一样都是从可执行文件中加载的
- 运行时堆（堆顶由brk指示(brk，由内核维护，进程私有)，向上增长）
- 共享库的内存映射区域（向上增长）
- 用户栈（运行时创建，rsp是栈指针，向下增长）
- 内核虚拟内存（依次为代码、数据、物理内存映射（大小等于DRAM的数目）、页表、task和mm结构、内核栈（内核在进程的上下文中执行代码时使用的栈），用户不可见）

进程的三种状态（从程序员的视角来看）

运行

停止，不会被调度，收到SIGSTOP、SIGTSTP、SIGTTIN，SIGTTOU信号时停止直到收到SIGCONT

SIGSTOP：不是来自终端的停止信号，不能被捕获或忽略
SIGTSTP：来自终端的停止信号，键入Ctrl+Z会发送SIGTSTP给前台job的每个进程，默认是停止（挂起）前台job
SIGTTIN
Only the foreground job receives terminal input. It is not an error for a background job to try to read from the terminal, but the terminal driver detects this and sends a special signal to the background job: SIGTTIN. This signal normally stops the background job; by using the shell, we are notified of this event and can bring the job into the foreground so that it can read from the terminal.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
> $ cat > /tmp/23 &
> [1] 7739
>
> $
> [1] + 7739 suspended (tty input) bat > /tmp/23
>
> $ fg
> [1] + 7739 continued bat > /tmp/23
> testMsg
> ^C
>
> $ /bin/cat /tmp/23
> testMsg
>

SIGTTOU

When we disallow background jobs from writing to the controlling terminal, cat will block when it tries to write to its standard output, because the terminal driver identifies the write as coming from a background process and sends the job the SIGTTOU signal. As with the previous example, when we use the shell’s fg command to bring the job into the foreground, the job completes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
> $ /bin/cat /tmp/23 &
> [1] 8398
> testMsg                                                                                                                                                  >      
> [1]  + 8398 done       /bin/cat /tmp/23
> 
> $ fg
> fg: no current job
> 
> $ stty tostop 
> 
> $ /bin/cat /tmp/23 &
> [1] 8412
> [1]  + 8412 suspended (tty output)  /bin/cat /tmp/23                                                                                             
> 
> $ fg
> [1]  + 8412 continued  /bin/cat /tmp/23
> testMsg
>

终止，永久停止。三种原因：收到一个信号，该信号handler终止该进程，从主程序返回，调用exit函数（exit函数不返回）（可以通过exit(status)终止进程并返回status，也可以通过return status终止进程并返回status）

进程的状态

来自linux内核设计与实现
TASK_RUNNING：进程是可执行的，可能正在执行，或在运行队列中等待执行。这是进程在用户空间中执行的唯一可能状态。内核空间中正在执行的进程也是这种状态
TASK_INTERRUPTIBLE：进程正在睡眠（也就是被阻塞），到达某些条件达成，一旦条件达成，内核就会把进程状态设置为RUNNING。处于此状态的进程会因为接收到信号而提前被唤醒并随时准备投入运行
TASK_UNINTERRUPTIBLE：与TASK_INTERRUPTIBLE的差别在于，就算接受到信号也不会被唤醒（即使是SIGKILL信号）或准备投入运行。通常在进程必须在等待时不受干扰或等待的事件很快就会发生时出现（比如这个任务正在进行重要的操作，甚至可能持有一个信号量）。因为不对信号做响应，所以较之可中断的状态，用的较少。（ps中看到的D状态的进程就是这种状态）
__TASK_TRACED：被其他进程跟踪的进程，比如通过ptrace对调试程序进行跟踪
__TASK_STOPPED：进程停止执行，没有投入运行也不能投入运行。发生在接受到SIGSTOP，SIGTSTP，SIGTTIN，SIGTTOU信号时，调试期间受到任何信号也会使得进程进入这状态
转换图见书P24(41)

Ref: ps manual

the state of a process:
        D    uninterruptible sleep (usually IO)
        I    Idle kernel thread
        R    running or runnable (on run queue)
        S    interruptible sleep (waiting for an event to complete)
        T    stopped by job control signal
        t    stopped by debugger during the tracing
        W    paging (not valid since the 2.6.xx kernel)
        X    dead (should never be seen)
        Z    defunct ("zombie") process, terminated but not reaped by its parent

子进程终止了，需要父进程回收，父进程终止时，子进程没有终止（可以是僵尸进程），则init（pid=1，不终止）为子进程的养父

作业（job）和进程组

unix shell使用job表示为对一条命令行求值而创建的进程
任何时刻，至多只有一个前台作业和0或多个后台作业
例子：ls | sort会创建一个由两个进程组成的前台作业，两个进程通过unix管道连接起来

进程组

shell为每个job创建一个独立的进程组
进程组ID通常取自job中父进程中的一个

daemon

生命周期长，通常在系统启动时就被创建并一直运行到系统关闭
在后台运行并且不拥有任何控制终端，这确保了内核永远不会为daemon自动生成任何任务控制信号以及终端相关的信号
通常以d作为程序名称的后缀
特定的daemon会作为内核线程运行，此类的daemon的代码是内核的一部分，通常在系统启动时被创建，ps列出的线程中，这些daemon会用[]括起来
很多标准的daemon是通过系统关闭时执行特定于应用程序的脚本来关闭的，不以这种方式关闭的daemon会收到SIGTERM信号，因为系统关闭时，init进程会向所有其子进程发送这个信号，默认SIGTERM会终止一个进程，可以为这个信号建立处理器。init在发出SIGTERM信号5s后会发送SIGKILL信号
创建daemon过程，见TLPI 37.2

创建新进程

fork后，子进程通过execve调用启动加载器
加载器删除子进程现有的虚拟内存段，并创建一组新的代码、数据、堆、栈段
loader跳转到_start地址，最终会调用main函数
除了一些头部信息，加载过程中没有从磁盘到内存的数据复制，直到被引用时，OS才会使用页面调度机制自动将页面从磁盘传送到内存
fork
- 子进程与父进程的用户级虚拟地址空间相同的（互相独立）的一份副本，包括代码和数据段、堆、共享库、用户栈
- 相同的描述符表（所以可以读写父进程打开的任何文件）
- 最大的区别是有不同的PID
- 父进程返回子进程的pid，子进程返回0（pid总是非零）
vfork
- 在SUSv3已经标记为过时的，SUSv4则从规范中剔除了，CopyOnWrite的fork已经足够快了，并且有些OS还把vfork实现为fork
- 无需为子进程复制虚拟内存或页表，共享父进程的内存，直到成功执行exec或_exit（不是exit）
- 子进程执行exec或_exit之前，暂停执行父进程
- 子进程不应该调用exit退出，因为其会导致父进程stdio的缓冲区刷新和关闭（更详细的见TLPI 25.4）
- 保证子进程先于父进程获得调度获得CPU（fork无法保证这点）
- 系统是在内核空间为每个进程维护文件描述符表的，且在vfork调用期间复制该表，所以子进程对文件描述符表的操作不会影响到父进程（对stdio的操作会，然而虽然文件描述符表是不同的，但是打开文件表不是相同的吗，操作后不就改变了文件位置了吗）
- SUSv3指出，以下行为是未定义的
  - 修改了出用于存储vfork返回值的pid_t变量之外的任何数据
  - 从调用vfork的函数返回（我认为，应该是因为会影响栈）
  - 在成功地调用_exit或执行了exec之前，调用了任何其他函数

IEEE754

最高比特为sign（0为正，1为负），接下来的8bit（float32是8it，double64是11bit）是exp，剩下的是significand（尾数）
规格化：0<exp<255(2047)，此时exp的含义是exp-127(1023)，尾数部分是1.M，M为尾数部分的二进制表达的数值。
非规格化：exp=0，此时exp的含义是exp=-126(-1022)，尾数部分是0.M，要就是没有前缀1，从而，从exp=1到exp=0是平滑的过渡——exp没有变，然后对应的从1.111111....到1到0.11111111111....到0。其用于表示0和非常接近0的数，可能的数值均匀的接近于0.0
无穷大：exp=255(2047)，尾数是全0
NaN：exp=255(2047)，尾数非0
浮点数加法不具有结合律和分配率，有交换律
$1/+0=+\infin$，$1/-0=-\infin$

汇编

参数寄存器：rdi, rsi, rdx, rcx, r8, r9
返回值：rax
栈指针：rsp
对抗缓冲区溢出攻击
- ASLR(Address space layout randomization)（每次运行，程序代码、库代码、栈、全局变量、堆在内存的不同区域）
- 栈破坏检测（金丝雀值，栈帧中任何局部缓冲区和栈状态之间存一个特殊的金丝雀值）
- 限制可执行代码的区域（一些内存页上的东西不允许执行）

数据对齐

计算机系统对基本数据类型的合法地址做出一些限制
对齐简化了处理器和内存系统之间的接口设计——比如，读一个8B东西读一次就行，不必读两次
无论数据是否对齐，x86-64都可以正确工作，但是可以提高系统性能。另外，没有对其，SSE指令可能无法正确执行，AVX对于对齐么有强制性要求
对于struct，为了使得结构内每个字段都对其，会有padding，结尾可能有padding，以满足结构数组内每个struct的对齐要求
页表中，我们可以查询得到PPN（physical page number），但是PPO（物理页内位移）是低k位，这意味着，每个页需要$2^k$对齐，这样子才能使得PPN描述出该页的起始位置——因为我们都是拿到起始位置后加上offset（正数，也是虚拟地址的低k bit）获得target。PPO的12bit刚好与cache的页内偏移位数+组数目的bit数相同，所以可以直接使用PPO去索引相应的组和具体的word，然后等待PPN，与组内的那些tag来查找匹配

优化性能

消除不必要的内存引用，使得可以编译器敢于缓存在寄存器中
循环展开，一方面减少循环控制代码，另一方面可以有更大的优化空间
提高并行性，比如进行累计运算时，使用多个acc变量，从而增加关键路径的数目，比如利用结合律，使得一些运算可以并行执行( $abcd \rightarrow (ab)(cd)$)，后者可以更快
减少读写相关的代码：比如刚写完个一个cell，立刻就又要读了

存储

磁盘寻道时，任意时刻读写头都位于同一柱面
SSD的随机写性能较低，因为一个擦除过的块才可能被写
局部性原理的体现：cache、虚拟内存每次加载一个页
cache
- 全相联cache：只有一个组，电路必须并行的搜索许多tag，所以昂贵、难度大，只适合作为非常小的cache，比如TLB
- 组相联：一个组有多路
- 直接映射
- 写：直写，每次都下一级cache，引起总线流量。写回，尽可能推迟更新下一级，但是要维护dirty bit。对于较长的传送时间，通常更倾向于写回而不是直写。
- 写不命中：写分配，加载下一级的块上来，然后更新这个块。非写分配，直接写到下一级。直写cache通常是非写分配的，写会cache通常是写分配的。
- 写、写不命中的细节随系统而变化
- 每次加载、驱逐都是一行一行的来
cache是用物理地址索引的，这就使得我们比较难以判定一段虚拟地址在cache上是否冲突

动态共享库

好处
- 其text段在内存中只需要一份拷贝，可以被映射到不同进程的地址空间
- 可以热更新服务器应用
- 应用无需重新编译，只需要重新分发共享库即可

异常控制流

系统需要对系统状态的变化做出反应，这些状态不一定跟当前正在执行的进程有关。比如IO设备、定时器产生的信号
可以发生在：硬件层（硬件的信号导致转移到异常处理程序）、OS层（比如上下文切换）、应用层（比如一个进程给另一个进程发送信号，从而接受者会突然转去执行信号处理程序，比如非本地跳转）
ECF是计算机系统实现并发的基本机制，并发的例子有
- 中断应用程序执行的异常处理程序
- 中断应用程序执行的信号处理程序
- 在时间上重叠执行的进程和线程

异常

这里的异常包括同步异常（trap、fault、abort）和异步异常（中断），有些厂商的手册中，异常只包括同步事件引起的控制流的改变
异常是控制流中的突变，用来响应处理器状态中的某些变化
异常号
- 每种类型的异常都分配了一个唯一的非负整数的异常号
- 一些由处理器的设计者分配（比如被零除，缺页、内存访问违例、断点、算术运算溢出）
- 其他由OS内核（OS内核：OS常驻内存的那部分）的设计者分配（比如syscall、来自外部IO设备的信号）
异常表
- 系统启动时（计算机重启或加电时）OS分配和初始化的一张跳转表
- 条目k包含异常k的handler的地址
- 异常表的起始地址放在一个叫做异常表基址寄存器的CPU寄存器中
过程
- 在运行时（OS执行某个程序时），处理器检测到发生一个事件（比如page fault、算数溢出、除零、系统定时器产生的信号、IO请求完成等），并确定对应的异常号k
- 随后处理器触发异常，方法是执行间接过程调用，通过异常表的表目k转到相应的handler
- 处理完后可能会返回当前指令、返回给当前指令的下一条指令、终止被中断的程序
调用过程
- 处理器将返回地址入栈，根据异常类型，返回地址可能是当前指令，可能是下一条指令。还需要入栈一些额外的信息，重新开始执行被中断的程序需要这些信息
- When control is being transferred from a user program to the kernel, all of these items are pushed onto the kernel’s stack rather than onto the user’s stack.(我猜，是不是如果是信号handler，则压入用户栈，否则内核栈)
- 异常handler运行在内核模式
- 硬件触发了异常后，剩下的工作都是软件的handler的。handler可以可选的执行“从中断返回”的指令，这将恢复现场并且切换为用户态（如果被中断的是一个用户程序的话），并将控制返回给被中断的程序
异常的类别
- 中断：来自处理器外部的IO设备的信号的结果，异步，总是返回到下一条指令，其Handler常常称为中断处理程序
  - I/O interrupt from external device
  - Hittinng Ctrl-C at the keyboard
  - Arrival of a packet from a network
  - Arrival of data from a disk
    - 过程举例
      
      网络适配器，给处理器芯片的一个引脚发信号，并把中断号放在系统总线上，来触发中断，异常号标志了引起中断的设备
      
      当前指令完成后，处理器注意到中断引脚的电压变高了，就从总线读取中断号，并调用相应的Handler
- trap：有意的异常(syscall, breakpoint traps, special instructions)，同步，返回到下一条指令
  - syscall：用户执行syscall n，导致到一个异常处理程序的trap，这个handler解析参数，并调用适当的内核程序，syscall可以执行特权指令，并且可以访问内核中的栈
- fault：潜在可恢复的异常（错误情况引起的，比如缺页异常），同步，可能返回到当前指令（否则，Handler返回到内核中的abort例程）。故障发生时，处理器将控制权转移到handler，如果handler可以处理这个错误情况，那么就将控制返回到引起故障的指令，从而重新执行它，否则返回到abort例程
- abort：不可恢复的异常（通常是一些硬件错误），同步，不返回
- 异步异常是由处理器外部的IO设备中的事件产生的，不是由任何一条专门的指令造成的，同步异常是执行一条指令（这种指令叫做故障指令）的产物。（来自百度百科：异步双方不需要共同的时钟，也就是接收方不知道发送方什么时候发送）
一般保护故障（异常13），通常是因为一个程序引用了一个未定义的虚拟内存区域，或者是尝试写一个readOnly的text段，Linux shell把这个报告为Segment fault
linux的syscall
- 每个syscall都有一个唯一的整数号，对应与一个到内核中的跳转表（这个跳转表不同于异常表）的偏移量
- 所有到linux syscall的参数都是通过通用寄存器而不是栈传递的。rax包含syscall号
- C函数库的wrapper需要将参数复制到寄存器
- 参数都是通过通用寄存器传递的，而不是通过栈传递的
- 按照惯例，rax包含系统调用号，rdi、rsi、rdx、r10、r8、r9包含最多的6个参数，以上顺序也是参数的顺序（第一个在rdi，第二个在rsi以此类推）
- 返回时，rcx、r11的内容会被破坏(应该就是caller save)，rax包含返回值，-4095到-1对应于负的errno
- 执行机器指令，引起处理器从用户态切换到内核态，并执行系统中断0x80的中断向量所指向的代码
- 响应中断0x80，内核调用system_call()例程，在内核栈保存寄存器值，根据syscall编号索引服务例程的地址。服务例程执行必要任务时，可能会在用户内存和内核内存之间传送数据，完成后返回给system_call例程
- 从内核栈中回复各寄存器的值，并将syscall的返回值放在栈上，返回wrapper，并切换到用户态
内核态 vs 用户态
- 通常实现为，某个控制寄存器的一个mode bit来指示
- 用户态不允许特权指令，比如停止处理器、改变mode bit、发起IO，不能引用地址空间中内核区内的代码和数据，否则会保护故障
- 从用户态到内核态的唯一方法：通过诸如中断、故障、trap之类的异常。异常发生时，控制传递到处理程序，处理程序运行在内核模式
- /proc可以让用户模式进程访问内核数据结构
- 从2.6开始，/sys文件系统输出系统总线和设备的额外的底层信息
上下文切换
- 一种较高层次的异常控制流，建立在前面讨论过的较低层次的异常机制之上，用来实现多任务
- 上下文：内核重新启动一个被抢占的进程所需的状态，通用目的寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈、各种内核数据结构（比如页表、包含有关当前进程信息的进程表、包含进程已打开文件的信息的文件表）
- 步骤包括：保存当前进程的上下文，恢复某个被抢占的进程的上下文，将控制传递新恢复的进程
- syscall时，可能发生上下文切换，比如wait cond、read阻塞、sleep。即使syscall没有阻塞，内核也可以决定执行上下文切换
- 看起来就像，OS利用三种同步的异常来借机上下文切换，如果没有，就借助定时器的中断

信号

软件形式的异常，允许进程和内核中断其他进程
底层硬件异常是由内核的Handler处理，对用户进程不可见，而信号就提供了一种机制来通知用户进程发生了这个异常（比如一个进程试图除以0，那么内核就会给它发SIGFPE信号）
发送信号：内核通过更新目的进程的上下文中的某个状态来发送一个信号。两种原因：内核检测到一个系统事件，所以发信号、kill函数（一个进程调用kill函数，显式的要求内核给这个进程发信号，可以给自己发信号）
目的进程被内核强迫以某种方式对信号做出反应时，就接受了信号。内核把进程从内核态切换到用户态时，会强制用户接受信号（如果有的话）
一个发出但是还没有接收的信号叫做待处理信号
一个类型最多只有一个待处理信号
进程可以有选择的阻塞某类信号，如果进程收到被阻塞的信号，那么会把这个信号加入到等待集合中，之后解除锁定后，会随之传递给此进程
每个进程都只属于一个进程组，父进程和子进程同属一个进程组，可以调用setpgid来改变
键入Ctrl+C会导致内核发送一个SIGINT给前台进程组的每个进程，默认情况下结果是终止前台job
键入Ctrl+Z会发送SIGTSTP给前台job的每个进程，默认是停止（挂起）前台job
信号处理程序可以被其他信号处理程序（不是同一个信号的handler）中断
阻塞信号
- 内核默认阻塞当前信号Handler正在处理的信号的那种类型的待处理信号
- sigprocmask函数
编写信号handler的原则
- handler要尽可能简单，比如只是设置一个flag
- handler里只能调用异步信号安全的函数（比如只访问局部变量的函数，比如不能被信号中断的函数）。异步信号安全不同于线程安全，线程安全中，对于非线程安全的函数的调用，可以通过持有同一把锁来实现线程安全；但是因为信号是异步的，所以如果在持有锁时信号到来，handler运行，则会死锁——因为handler调用该函数前也要持有锁，CSAPP 3rd（英文版）的P757有一个异步线程安全的函数的表，其中不包括exit、printf等常见函数
- 保存和恢复errno。因为信号handler中调用的函数可能会在失败时设置errno，所以可能会干扰正常程序中的errno，所以需要在刚进入handler时保存errno，而在退出前恢复errno
- 如果访问了全局的数据结构，那么需要阻塞所有信号
- 使用volatile声明flag，volatile要求编译器每次在代码中引用flag时，都从内存中读取该值
- 使用sig_atomic_t声明变量，对其读或写是原子的，不会中断，因为可以用一条指令来实现，所以不需要暂时的阻塞信号
信号不排队，所以接收到信号后要在循环中处理，而不能一个信号对应一次处理
sigsuspend可以用来显式的等待信号
不对SIGKILL做响应的情况
- 首先，SIGKILL不能被捕获或者忽略（SIGSTOP也是）
- 但是TASK_UNINTERRUPTIBLE的进程是不响应任何信号的，所以SIGKILL也无效
- 僵尸进程无法被SIGKILL杀死，杀死僵尸进程的方法是其父进程终止或其父进程调用wait

虚拟内存

MISC

能力：使得可以把内存看作磁盘的cache；为进程提供一个一直的地址空间；保护进程的地址空间
地址空间：一个非负整数地址的有序集合
TLBI（TLB index）的索引是VPN（virtual page number）的低t bit索引的
需要从cache、主存获得PTE是需要MMU计算PTEA的
Linux中Swap（即：交换分区），类似于Windows的虚拟内存，就是当内存不足的时候，把一部分硬盘空间虚拟成内存使用,从而解决内存容量不足的情况。一旦一个虚拟页面被初始化（被按需页面调度进来，或者已经映射了二进制0页面（有对应的物理页）），则总是在swp space交换来交换去

计算物理地址的过程（不缺页版本）

处理器生成虚拟地址，并传递给MMU
MMU生成PTE（页表条目）地址，并从高速缓存、主存请求得到它
高速缓存、主存向MMU返回PTE
MMU构造物理地址，并传递给高速缓存、主存
高速缓存、主存返回所请求的数据字

计算物理地址的过程（缺页版本）

处理器生成虚拟地址，并传递给MMU
MMU生成PTE（页表条目）地址，并从高速缓存、主存请求得到它
高速缓存、主存向MMU返回PTE
PTE中的有效位是0，所以MMU触发一次异常，传递给CPU中的控制到OS内核的中的缺页处理程序
缺页Handler确定中物理内存中的牺牲页，如果这个页面是dirty，则换出到磁盘
缺页handler把页面调入主存并更新内存中PTE
缺页handler返回原来的进程并再次执行导致缺页的指令

CopyOnWrite

只要进程没有试图写这些COW的区域，那么就可以共享
如果进程试图写这些区域中的某个页面时，就会触发一个保护故障，从而会在物理内存中创建这个页面的一个新副本，更新页表条目指向这个新副本
把复制副本的工作推迟到了最后时刻，从而最充分的利用了物理内存

Linux的虚拟内存和缺页处理

Linux将虚拟内存组织成区域的集合，一个区域是已经存在的（已分配的）虚拟内存的连续片（比如代码段、数据段、堆等）
每个存在的虚拟页面都保存在某个区域中
区域使得内核无需记录那些不存在的虚拟页
区域链表可以通过位于内核虚拟内存的task_struct中相关信息获得
- mm_struct的mmap：指向一个vm_area_structs的链表，每个vm_area_structs都描述了当前虚拟地址空间的一个区域
- mm_struct的pgd：指向第一级页表（页全局目录）的基址，内核运行这个进程时，把pgd放在CR3控制寄存器
- task_struct：包含或指向内核运行该进程所需要的所有信息，比如PID、指向用户栈的指针、可执行目标文件的名字、程序计数器
Linux虚拟内存的缺页异常的处理程序
- 使用内核为每个进程维护的区域结构的链表来判断是否是
  - 访问不存在的页面(从而段错误)
  - 缺页是因为内存访问不合法（比如写一个只读页面）导致的（从而保护异常）
  - 正常缺页
- 为什么不使用PTE的是否为null来判断呢？这样子就要维护所有的PTE，其中有的有效位为1有的为0有的PTE的某个字段为null标志这是未被映射的虚拟内存页

动态内存分配

碎片
- 内部碎片（一个已分配的块比payload大时发生，只取决于分配器的实现以及以前的请求模式）
- 外部碎片（空闲内存合计起来足以满足一个请求，但是没有单独一块满足时，不仅取决于以前的模式、分配器的工作方式，还取决与未来请求的模式）
分离的空闲链表：比如可以$[2^n-1,2^{n+1}]$这个区间大小的页维护在一个空闲链表中
- 简单分离存储：不分割，不合并
- 分离适配：确定请求的大小类，然后首次适配（找不到就到更大的大小类去找）。可选的分割，剩余部分insert到适当的空闲链表中。实在没有，就请求OS分配，然后从这个新的中分配出Request的那块，剩下的insert到空闲链表中。释放时执行合并，结果放在相应的空闲链表。malloc就是这样做的
buddy
- 每个大小类都是2的幂，为了找到$2^k$，需要找$2^p(k\leq p)$，如果$k<p$，则递归的二分这个块，每次二分时，剩下的另一块都insert到空闲链表中。要释放时，合并空闲的buddy，但遇到一个已分配的buddy时，停止合并。buddy之间的地址差异只是1bit。如果大部分请求不是2的幂大小，则内部碎片多

Linux的文件

内核用三个数据结构来表示打开的文件
- 描述符表
  - 每个进程都有自己的描述符表
  - 由进程打开的文件描述符索引
  - 每个打开的描述符表项指向文件表的一个表项
- 文件表
  - 所有进程共享这个表，表示打开的文件集合
  - 每个表项包含：当前文件位置、引用计数（指向该表项的描述符表项数目），指向v-node表中的对应表项的指针
  - 内核不会删除一个文件表表项，直到其引用计数为0
  - 多个打开文件表的表项可以指向同一个v-node表的表项，比如同一进程两次调用open同一文件，是不同的文件句柄，同样的inode，这样子每个都有自己的文件位置
- v-node表
  - 所有进程共享这张v-node表
  - 每个表项包含stat结构中的大多数信息
  - 包含文件大小、文件类型、file access
fork中，子进程复制父进程的描述符表，所以指向相同的打开文件表表项
io重定向（比如dup2）则是使得两个描述符表项指向同一个打开文件表的表项