基础知识

计算机原理

冯·诺依曼体系结构

CPU组成

  • 控制单元（Control Unit）：
  • 数据单元
  • 运算单元

寄存器

寄存器是CPU内部用来存放数据的一些小型存储区域，用来暂时存放参与运算的数据和运算结果以及一些CPU运行需要的信息。

下面几个tabs描述了x86-64架构中涉及到的不同类别的寄存器

通用寄存器是程序执行过程中最常用、最基础的寄存器，大部分时间都是在操作这些寄存器完成指令功能。“通用”指的是这些寄存器没有特殊的用途，可以交给程序按照一定的规则（通用不是乱用）去使用。

寄存器 Callee Save 描述
%rax(Accumulator) 结果寄存器，通常用执行加法，存储函数调用的返回值，也会用于idiv和imul指令
%rbx 是 miscellaneous register
%rdi, %rsi, %rdx, %rcx, %r8, %r9 用作传递整型或指针参数到被调用函数，依次对应第1个参数、第2个参数 …。rdx也会用于idiv和imul 指令
%rsp(Stack Pointer) 栈指针寄存器，通常会指向栈顶位置，堆栈的pop和push操作就是通过改变rsp的值即移动堆栈指针的位置来实现的
%rbp(Base Pointer) 是 栈底指针，用于标识当前栈帧的起始位置，通常用rbp+偏移量来存取函数栈中的局部变量
%r10, %r11 miscellaneous registers
%r12, %r13, %r14, %r15 是 miscellaneous registers

从上表我们可以还得出如下结论

  1. 每个寄存器的用途并不是单一的
  2. 在imul指令中，两个64位的乘法最多会产生128位的结果，乘法结果需要%rdx存储高64位%rax存储低64位；在idiv指令中被除数是128位的，同样需要%rax和%rdx共同存储被除数
  3. 被标识为”miscellaneous”的寄存器属于通用性更广泛的寄存器，编译器可以根据需要存储任何数据

Caller Save和Callee Save的区别在于寄存器的值是由调用者负责保存还是被调用者负责保存。当产生函数调用时，子函数内也会使用到通用寄存器进行数据存储，此时这些寄存器中之前保存的父函数的值就会被覆盖。为了避免数据覆盖导致函数返回时寄存器的数据无法恢复，CPU体系结构中就规定了通用寄存器的保存方式。

如果一个寄存器被标识为Caller Save，那么在进行子函数调用前，就需要由调用者提前保存好这些寄存器的值，保存方法通常是把寄存器的值push到堆栈中，调用者保存完成后，在子函数中就可以随意覆盖这些寄存器的值了。如果一个寄存器被标识为Callee Save，那么在函数调用时，调用者就不必保存这些寄存器的值而直接进行子函数调用，进入子函数后，子函数在覆盖这些寄存器之前，需要先保存这些寄存器的值，即这些寄存器的值是由被调用者来保存和恢复的。

用里面的一个一个标记bit位，存放CPU进行算术或逻辑计算的结果，这些标志大多由CPU自动设置和修改

  • 零标志(Zero Flag)：如果运算结果为0，ZF=1，否则ZF=0
  • 符号标志(Sign Flag)：与运算结果的最高位bit值一致
  • 进位标志(Carry Flag)：在无符号运算时，记录了运算结果的最高有效位向更高位的进位值或从更高位借位，产生进位或借位时CF=1，否则CF=0
  • 溢出标志(Overflow Flag)：有符号运算的结果是否发生了溢出，如果发生溢出OF=1,如果没有OF=0。正数+正数，负数+负数有可能发生溢出；正数-正数不可能发生溢出
  • 奇偶标志(Parity Flag)：如果运算结果bit位中有偶数个1，则其值为1，否则其值为0。此指令主要用于检查数据传输过程中是否产生错误，比如典型的奇偶校验

CF和OF的区别：CF是对无符号数运算有意义的标志位，而OF是对有符号数运算有意义的标志位。比如：mov al, $7F; add al $01。add指令执行后CF=0，OF=1。

举几个🌰

              al                 CF    OF    SF    ZF    PF
sub al,al     0x00/0000 0000     0     0     0     1     1
mov al,10h    0x10/0001 0000     0     0     0     1     1  ; mov不会改变任何标志寄存器的值
add al,90h    0xa0/1010 0000     0     0     1     0     1

mov al,80h    0x80/1000 0000     0     0     1     0     1
add al,80h    0x00/0000 0000     1     1     0     0     1

mov al,fch    0xfc/1111 1100     1     1     0     0     1
add al,05h    0x01/0000 0001     1     0     0     0     0

mov al,7dh    0x7d/0111 1101     1     0     0     0     0
add al,0bh    0x88/1000 1000     0     1     1     0     1
  • %rip(Instruction Pointer)：指令指针寄存器，又叫PC(Program Counter)，存放下一条待执行指令的内存地址。CPU的工作其实就是不断取出它指向的指令，然后执行这条指令。

  • CR0：存储了CPU控制标记和工作状态。一些重要的标志位含义如下：
    • PE(Protected Mode Enable)：1代表系统运行在保护模式下，否则为实模式
    • WP(Write Protect)：是否开启内存写保护，若开启，对只读页面进行写入会触发异常，这一机制常常被用于实现写时复制COW功能
    • AM(Alignment Mask)：是否启用内存对齐自动检查
    • CD(Cache Disable)：1代表关闭cache
    • PG(Paging)：1代表启用内存分页，同时使用CR3寄存器，否则不开启内存分页
  • CR1：保留，访问它会导致CPU抛出未定义异常
  • CR2：发生缺页异常时保存导致异常的访问地址
  • CR3：用于存储页目录的物理内存基地址，比如Linux 64位中存储PGD的物理地址，在进程空间切换时，CR3也要同步切换
  • CR4：在保护模式下使用，存储了CPU工作相关以及当前任务的一些信息

CPU指令

指令分类

指令类型 示例 示例汇编代码 含义 解释
算术类指令 add add $s1,$s2,$s3 $s1=$s2+$s3 将寄存器r2和r3中的数值相加后的结果放到寄存器r1中
数据传输类指令 load word load $s1,10($s2) $s1=memory[$s2+10] 取寄存器r2中的数，加上10字节偏移后，取出内存中对应的字(WORD 一般为4字节)，存入r1寄存器中
逻辑类指令 xor xor $s1,$s2$s3 $s1=$s2 ^ $s3 将寄存器r2和r3中的数值按位取异或后的结果放到寄存器r1中
条件分支指令 branch on equal beq $s1,$s2,10 if($s1==$s2) go to PC+10 如果r1和r2寄存器内的值相等，从程序计数器往后跳10
无条件跳转指令 jump j 1000 go to 1000 跳转到1000这个目标地址

机器码的生成

以最简单的MIPS32指令集为例

R指令：用作算术和逻辑运算，rs/rt为读取数据寄存器，rd为写入数据寄存器。如果是逻辑位移操作，则对rs/rt中的数据根据位移量做位移操作，然后写入rd寄存器；否则偏移量为00000。最后的功能码，则是在前面的操作码不够的时候，扩展操作码表示对应的具体指令的。比如add和xor的opcode都是000000，而add的功能码为100000，xor的功能码为100110

I指令：用作数据传输和条件分支，以及在运算时使用的并非变量而是常数。此时没有第三个寄存器、偏移量以及功能码，这三部分被合成了一个16Bit的地址值或常数

J指令：用作跳转，除opcode外的26Bit都是一个跳转后的地址

下面用一个简单的异或指令为例，看看一个机器码如何生成

xor $t0,$s2,$s1

（为了方便，下面的数字都用10进制表示）对应MIPS32指令里，opcode为0，rs代表第一个寄存器s1，地址是17，rt代表第二个寄存器s2，地址是18，rd代表目标的临时寄存器t0，地址是8。因为不是位移操作，所以偏移量是0。功能码通过查表得到二进制为'100110'。

| opcode |   rs  |   rt  |   rd  | shamt | funct  |
| 000000 | 10001 | 10010 | 01000 | 00000 | 100110 |

2进制表示为：0000 0010 0011 0010 0100 0000 0010 0110
16进制表示为： 0x02324026

指令跳转

CPU如何执行指令的？

程序执行时，CPU会根据PC寄存器中的指令内存地址，从内存里把需要执行的指令读取到指令寄存器里面执行，然后根据指令长度自增，开始顺序读取下一条指令，这就要求指令必须是连续存储在内存空间中的。

而有些特殊的指令，比如上一小节提到的J指令，也就是跳转指令，会修改PC寄存器里面的指令内存地址的值。这样下一条要执行的指令就不是顺序加载的了。正是因为有了跳转指令，我们才可以在程序中使用if...else/switch...case条件语句和while/for循环语句。

注：本节汇编代码使用的编译器版本为：Apple clang version 11.0.3 (clang-1103.0.32.59)

if…else + goto

goto属于指令跳转最简单的使用场景。if else通过jne+jmp实现分支跳转。

; int main() {
 0: 55                      pushq   %rbp            ; 将父函数栈帧的起始地址压入栈顶，即当前函数栈帧
 1: 48 89 e5                movq    %rsp, %rbp      ; 将栈指针的值复制到rbp里，而rsp始终会指向栈顶
 4: 48 83 ec 10             subq    $16, %rsp       ; 栈顶向下扩展16个字节（栈是从高地址向低地址生长的），用于在发生函数调用时，存储当前函数内的局部变量
 8: 31 c0                   xorl    %eax, %eax      ; rax的低4字节置0
 a: 89 c7                   movl    %eax, %edi      ; 将rax的低4字节（即0）复制到rdi寄存器的低4字节。[寄存器](#寄存器)一节有学到rdi是用于存储函数调用的第1个参数值
 c: c7 45 fc 00 00 00 00    movl    $0, -4(%rbp)    ; 将[rbp-4, rbp]内存空间置0，暂时不知道用处
;  srand(time(NULL));
13: e8 00 00 00 00          callq   0 <_main+0x18>  ; 调用time函数，参数的值存在edi寄存器，即0(NULL)
18: 89 c7                   movl    %eax, %edi      ; 将time函数的返回值复制到rdi寄存器的低4字节，作为srand函数的第1个参数
1a: e8 00 00 00 00          callq   0 <_main+0x1f>  ; 调用srand函数
;  int r = rand() % 2;
1f: e8 00 00 00 00          callq   0 <_main+0x24>  ; 调用rand函数，返回值存到rax指针
24: 99                      cltd                    ; 将eax寄存器的值符号扩展32位到%edx寄存器，也就是说，如果eax寄存器的二进制序列的最高位为0，则cltd指令将把edx置为32个0，相反，如果%eax寄存器的二进制序列最高位为1，则cltd指令将会自从填充edx寄存器为32个1
25: b9 02 00 00 00          movl    $2, %ecx        ; 将rcx的低4字节值置为2
2a: f7 f9                   idivl   %ecx            ; 将edx（高32位和eax（低32位）中的64位数作为被除数，ecx值作为除数。指令将商存储在eax中，余数存储在edx中。
2c: 89 55 f8                movl    %edx, -8(%rbp)  ; 将edx中存储的余数的值复制到[rbp-8, rpb-4]内存空间，即变量r的栈地址
;  if (r == 0) {
2f: 83 7d f8 00             cmpl    $0, -8(%rbp)    ; 判断r的值是否为0，并根据结果更新ZF/OF/SF标志寄存器，如果r==0，则ZF=1
33: 0f 85 05 00 00 00       jne     5 <_main+0x3e>  ; Jump if not equal，即当ZF!=1时，将PC寄存器值改为0x3e
;      goto label1;
39: e9 05 00 00 00          jmp     5 <_main+0x43>  ; 如果r==0，将PC寄存器值改为0x43
;      goto label2;
3e: e9 09 00 00 00          jmp     9 <_main+0x4c>  ; 将PC寄存器值改为0x4c
;  r += 1;
43: 8b 45 f8                movl    -8(%rbp), %eax  ; r==0会执行到这一条指令，将r的值复制到eax寄存器
46: 83 c0 01                addl    $1, %eax        ; eax寄存器累加1
49: 89 45 f8                movl    %eax, -8(%rbp)  ; 将eax的值复制到变量r的栈地址空间
;  r += 2;
4c: 8b 45 f8                movl    -8(%rbp), %eax  ; 将r的值复制到eax寄存器
4f: 83 c0 02                addl    $2, %eax        ; eax寄存器累加2
52: 89 45 f8                movl    %eax, -8(%rbp)  ; 将eax的值复制到变量r的栈地址空间
;  return r;
55: 8b 45 f8                movl    -8(%rbp), %eax  ; 将r的值复制到eax寄存器，作为函数的返回值
58: 48 83 c4 10             addq    $16, %rsp       ; 栈顶向上缩减16个字节，即恢复刚开始开辟的16字节栈内存空间
5c: 5d                      popq    %rbp            ; 将父函数栈帧的起始地址恢复到rbp寄存器
5d: c3                      retq                    ; 弹出当前栈顶元素（即父函数执行call指令时压入的PC寄存器的下一条指令地址），更新到PC寄存器中，将程序控制权返回到出栈后的栈顶
#include <time.h>
#include <stdlib.h>

int main() {
    srand(time(NULL));
    int r = rand() % 2;
    if (r == 0) {
        goto label1;
    } else {
        goto label2;
    }
label1:
    r += 1;
label2:
    r += 2;
    return r;
}
while & for
  • for： 先用cmp+jg判断是否满足if条件，不满足则跳出循环，否则执行if内代码，最后用jmp实现执行完if内代码后跳回cmp+jg
  • while： 和for一样
  • do...while： 先执行do内代码，然后用cmp+jle判断是否满足while条件，满足则用jmp跳回do，否则结束循环
; int main() {
 0: 55                      pushq   %rbp            
 1: 48 89 e5                movq    %rsp, %rbp
 4: c7 45 fc 00 00 00 00    movl    $0, -4(%rbp)      ; 这里发现了个有意思的现象，由于代码里没有调用其他函数，所以没有扩展栈顶的指令，具体原因下面的[函数调用及栈帧](#函数调用及栈帧)一节会分析
;  int a = 1;
 b: c7 45 f8 01 00 00 00    movl    $1, -8(%rbp)      ; 将栈地址[rbp-8, rpb-4]内存空间，即变量a赋值为1
;  for (int i = 1; i <= 3; ++i) {                     ; 下面3条指令对应的是 i = 1; i <= 3
12: c7 45 f4 01 00 00 00    movl    $1, -12(%rbp)     ; 将栈地址[rbp-12, rpb-8]内存空间，即变量i赋值为1
19: 83 7d f4 03             cmpl    $3, -12(%rbp)     ; 比较i和3，并根据结果更新ZF/OF/SF标志寄存器，如果i<=3，则ZF=1 SF!=OF
1d: 0f 8f 17 00 00 00       jg      23 <_main+0x3a>   ; Jump if greater，即当i > 3时，将PC寄存器值改为0x3a
;      a += i;
23: 8b 45 f4                movl    -12(%rbp), %eax   ; 将i的值复制到eax寄存器  
26: 03 45 f8                addl    -8(%rbp), %eax    ; 将a的值累加到eax寄存器
29: 89 45 f8                movl    %eax, -8(%rbp)    ; 将eax的值复制到变量a的栈地址空间
;  for (int i = 1; i <= 3; ++i) {                     ; 下面4条指令对应的是 ++i
2c: 8b 45 f4                movl    -12(%rbp), %eax   ; 将i的值复制到eax寄存器
2f: 83 c0 01                addl    $1, %eax          ; eax寄存器累加1
32: 89 45 f4                movl    %eax, -12(%rbp)   ; 将eax的值复制到变量i的栈地址空间
35: e9 df ff ff ff          jmp     -33 <_main+0x19>  ; 将PC寄存器值改为0x19，即跳回判断 i <= 3的逻辑
;  while (a <= 10) {
3a: e9 00 00 00 00          jmp     0 <_main+0x3f>
3f: 83 7d f8 0a             cmpl    $10, -8(%rbp)     ; 比较a和10
43: 0f 8f 0e 00 00 00       jg      14 <_main+0x57>   ; 当 i > 10时，将PC寄存器值改为0x57
;      ++a;
49: 8b 45 f8                movl    -8(%rbp), %eax    ; 将a的值复制到eax寄存器
4c: 83 c0 01                addl    $1, %eax          ; eax寄存器累加1
4f: 89 45 f8                movl    %eax, -8(%rbp)    ; 将eax的值复制到变量a的栈地址空间
;  while (a <= 10) {
52: e9 e8 ff ff ff          jmp     -24 <_main+0x3f>  ; 将PC寄存器的值改为0x3f，即跳回判断 i <= 10的逻辑
;  do {
57: e9 00 00 00 00          jmp     0 <_main+0x5c>
;      a += 1;
5c: 8b 45 f8                movl    -8(%rbp), %eax    ; 下面3句对应a+1，这里就不赘述了
5f: 83 c0 01                addl    $1, %eax
62: 89 45 f8                movl    %eax, -8(%rbp)
;  } while (a <= 10);
65: 83 7d f8 0a             cmpl    $10, -8(%rbp)     ; 比较a和10
69: 0f 8e ed ff ff ff       jle     -19 <_main+0x5c>  ; 当 a <= 10时，将PC寄存器值改为0x5c，即跳回a+1操作
;  return a;
6f: 8b 45 f8                movl    -8(%rbp), %eax    ; 将a的值复制到eax寄存器作为函数返回值
72: 5d                      popq    %rbp
73: c3                      retq
int main() {
    int a = 1;
    for (int i = 1; i <= 3; ++i) {
        a += i;
    }

    while (a <= 10) {
        ++a;
    }

    do {
        a += 1;
    } while (a <= 10);
    return a;
}
switch…case

从逻辑上来讲，switch...case能实现的功能都可以用if...else替换。但是有一点区别在于，编译器会根据case的数量和值的稀疏程度，来编译优化switch语句生成不同的机器码，具体的规则为：

  • 如果case分支数 < 4（default不算），或者每两个case之间的差值 > 阈值，此时生成的汇编代码和if…else逻辑类似，都是对每一个条件进行cmp，然后je/jne进行跳转
  • 否则，编译器会在目标文件的代码段中增加一个jump table。其本质上是一个数组，index对应case值与case最小值的差值，value对应数组起始地址与case代码块起始地址的差值（之所以要存相对值而非绝对值是因为指令的地址只有在加载到内存后才能确定）。通过计算switch值相对的index，取出跳转表对应的相对地址，然后jmp到代码块，实现O(1)时间复杂度的条件跳转，是典型的以空间换时间的优化方法。

switch语句适用场景

  1. 判断的case条件针对同一个变量，且有确切值
  2. 分支较多，大于等于4个
  3. case条件的值在一个较小的、连续的范围内，且跨度小于等于6

if…else语句适用场景

  1. 分支较少，小于4个
  2. case条件值较为稀疏
  3. 判断的case条件不止有一个变量，或基于数值范围判断
; void switch_demo(int x) {
 8: 89 7d fc                movl    %edi, -4(%rbp)          ; 将入参x的值复制到[rbp - 4, rbp]栈内存，因为rdi寄存器在调用其他函数时还要用到所以必须要把值保存到内存中
;  switch(x) {
 b: 8b 45 fc                movl    -4(%rbp), %eax
 e: 83 c0 fe                addl    $-2, %eax               ; eax寄存器中的值-2，2为case最小值，这里是计算变量x对应跳转表的index
11: 89 c1                   movl    %eax, %ecx              ; 将index的值写入ecx寄存器
13: 83 e8 05                subl    $5, %eax                ; 将变量x减去case的最大值，如果大于0则跳转到default，无需查询跳转表
16: 48 89 4d f0             movq    %rcx, -16(%rbp)         ; 保存index的值到[rbp - 16, rbp - 8]栈内存
1a: 0f 87 5b 00 00 00       ja      91 <_switch_demo+0x7b>  ; 无符号跳转，如果eax中的值大于0，即x - 2 - 5 > 0，则修改PC寄存器的值为0x7b，即跳转到default分支
20: 48 8d 05 69 00 00 00    leaq    105(%rip), %rax         ; 将PC寄存器中的值加0x69并复制到rax寄存器，PC寄存器存的是下一条待执行指令的地址即0x27，所以rax中的值为0x90即跳转表首地址。leaq是对地址进行运算，并将计算出的地址存入目标寄存器中；movq是对地址中的数据进行计算
27: 48 8b 4d f0             movq    -16(%rbp), %rcx         ; 将index的值复制到rcx寄存器
2b: 48 63 14 88             movslq  (%rax,%rcx,4), %rdx     ; 跳转表首地址 + index * 4，这里是计算变量x对应的跳转表中的地址
2f: 48 01 c2                addq    %rax, %rdx              ; 跳转表中地址存储的值为`case代码块相对于跳转表首地址的差值`， 加上跳转表首地址后，rbx中存的即为变量x对应的case代码块首地址
32: ff e2                   jmpq    *%rdx                   ; 修改PC寄存器值为rdx中存的地址值
;          printf("Got 3");
34: 48 8d 3d 6d 00 00 00    leaq    109(%rip), %rdi         ; data段中"Got 3"常量对应的地址
3b: b0 00                   movb    $0, %al
3d: e8 00 00 00 00          callq   0 <_switch_demo+0x42>
;          break;
42: e9 42 00 00 00          jmp     66 <_switch_demo+0x89>  ; break跳出循环 
;          printf("Got 6");
47: 48 8d 3d 60 00 00 00    leaq    96(%rip), %rdi
4e: b0 00                   movb    $0, %al
50: e8 00 00 00 00          callq   0 <_switch_demo+0x55>
;          printf("Got 7");
55: 48 8d 3d 58 00 00 00    leaq    88(%rip), %rdi          ; go through
5c: b0 00                   movb    $0, %al
5e: e8 00 00 00 00          callq   0 <_switch_demo+0x63>
;          break;
63: e9 21 00 00 00          jmp     33 <_switch_demo+0x89>
;          printf("Got 2 or 4");
68: 48 8d 3d 4b 00 00 00    leaq    75(%rip), %rdi
6f: b0 00                   movb    $0, %al
71: e8 00 00 00 00          callq   0 <_switch_demo+0x76>
;          break;
76: e9 0e 00 00 00          jmp     14 <_switch_demo+0x89>
;          printf("Got default");
7b: 48 8d 3d 43 00 00 00    leaq    67(%rip), %rdi
82: b0 00                   movb    $0, %al
84: e8 00 00 00 00          callq   0 <_switch_demo+0x89>
; }

小端模式，即低地址存低字节。值为补码。

index/switch值 asm 补码 原码 case代码块首地址 对应代码
0/2 90: d8 ff ff ff 0xffffffd8 0x80000028 0x68 printf(“Got 2 or 4”);
1/3 94: a4 ff ff ff 0xffffffa4 0x8000005c 0x34 printf(“Got 3”);
2/4 98: d8 ff ff ff 0xffffffd8 0x80000028 0x68 printf(“Got 2 or 4”);
3/5 9c: eb ff ff ff 0xffffffeb 0x80000015 0x7b printf(“Got default”);
4/6 a0: b7 ff ff ff 0xffffffb7 0x80000049 0x47 printf(“Got 6”);
5/7 a4: c5 ff ff ff 0xffffffc5 0x8000003b 0x55 printf(“Got 7”); 
void switch_demo(int x) {
    switch(x) {
        case 3:
            printf("Got 3");
            break;
        case 6:
            printf("Got 6");
        case 7:
            printf("Got 7");
            break;
        case 4:
        case 2:
            printf("Got 2 or 4");
            break;
        default:
            printf("Got default");
    }
}

函数调用及栈帧

上一小节分析指令跳转汇编代码时提到了函数调用、压栈相关知识，这一节重点学习下。首先思考个问题，函数A在调用函数B之前，需要保存哪些信息，保存到哪？需要传递哪些信息，如何传递？调用结束后如何恢复信息并继续执行呢？

函数栈帧起源

如果让我来设计指令实现函数调用，最先想到的是什么方法呢？

  • 用goto能实现吗，函数B执行结束后利用goto回到函数A中调用函数B的下一条指令的地址。但是细想一下有诸多问题，如果依赖了第三方的库，我们没办法改它的源代码，也就没办法让Callee执行结束后goto回Caller继续执行，所以用goto实现不了函数调用。
  • 那既然在这种场景下没办法跳回，能不能在编译时用函数B的指令替换掉函数A的call指令？这样无需跳转顺序执行即可。但是细想一下还是有问题，如果函数A调用函数B，函数B又调用了函数A，这样一直循环调用就会产生无穷无尽的替换。所以把Callee的指令直接插入到调用处这个方法也实现不了函数调用。
  • 既然函数调用必须要跳回继续执行，但又不能修改被调用函数的指令，那能不能把要跳回执行的指令记录下来，然后大家约定下：比如函数调用结束后都从r15寄存器中取出跳回地址，继续执行就好了。但是在多层函数调用里，需要记录每一层函数的跳回地址，而CPU中的寄存器数量并不多（x86-64只有16个通用寄存器），调用层级一多就存不下了。
  • 既然寄存器存不下跳回地址，那能不能把地址存到内存空间中呢？考虑到函数调用有递归的特性，即先调用的后返回，这和栈的数据结构（LIFO，Last In First Out）相同。这样我们在内存中开辟一段空间，每次函数调用之前把跳回后要继续执行的指令地址压栈，在被调用函数返回时将栈顶地址出栈，然后jmp跳转到对应指令地址。

通过上面的推演，我们初步确定了函数调用的方法。当然在真实的程序里，需要压栈的不止有函数调用完成后的返回地址。

为了保证调用前后变量和函数在Caller中的相对地址不变，在函数返回时要能把Caller栈底的地址恢复到寄存器中，所以Caller的栈底地址（即%rbp寄存器中的值）也需要保存到栈空间。考虑到函数传参可以有很多，而寄存器个数有限，所以当参数超过6个（在寄存器一节有讲过）后，多出的参数数据也要压入栈中（从右到左依次压入Caller栈）。那么函数的栈空间目前可以确定的结构如下：

通过寄存器传递到Callee的参数值也需要保存到栈空间，以免寄存器参与之后的计算或函数调用导致其内的值被覆盖。同时局部变量在函数调用返回后还需要继续使用，所以局部变量的值也需要保存到栈空间，那么函数的栈帧空间最终就确定为：

汇编代码分析

注：汇编代码使用的编译器版本为：gcc version 6.3.0 20170516 (Debian 6.3.0-18+deb9u1)

汇编代码中涉及到的几个小知识，这里提前说明下

  1. lea（Load Effective Address）是对地址进行运算，并将计算出的地址存入目标寄存器中；mov是对地址中的数据进行计算。举个例子：%rbp=0x30， mov -0x10(%rbp),rax将0x20~0x28内存地址中的数据复制到rax寄存器；lea -0x10(%rbp),rax将0x20这个值复制到rax寄存器
  2. 栈地址对齐：某些型号的Intel和AMD处理器对于SSE指令，如果数据没有对齐的话，就无法正确执行。这些指令对16字节内存进行操作，在SSE单元和内存之间传送数据的指令要求内存地址必须是16的倍数。对齐的字节数可以通过gcc的-mpreferred-stack-boundary参数配置，取值范围为4~12即64byte~4096byte
0000000000000072 <main>:
int main() {
72:  55                push   %rbp              ; 将上一栈帧的rbp值压栈。这里有一个疑惑：main函数不是整个函数的入口吗？难道说main也有父函数？这个谜题将在[程序链接与装载](#程序连接与装载)一节揭晓
73:  48 89 e5          mov    %rsp,%rbp         ; 将rsp的值复制到rbp寄存器，即将rbp指向当前函数的栈底，而rsp始终会指向栈顶
76:  48 83 ec 10       sub    $0x10,%rsp        ; 栈顶向下扩展16个字节（栈是从高地址向低地址生长的），用于存储局部变量
		long x = 10, y = 20;
7a:  48 c7 45 f8 0a 00 movq   $0xa,-0x8(%rbp)   ; 将栈地址[rbp-8, rbp]内存空间，即变量x赋值为10
81:  00 
82:  48 c7 45 f0 14 00 movq   $0x14,-0x10(%rbp) ; 将栈地址[rbp-16, rbp-8]内存空间，即变量y赋值为20
89:  00 
		x = calc('l', 2, 3, x, 15, y, y + 1);
8a:  48 8b 45 f0       mov    -0x10(%rbp),%rax  ; 将变量y的值复制到rax寄存器，用于后续计算y+1
8e:  48 8d 48 01       lea    0x1(%rax),%rcx    ; 将y+1的值复制到rcx寄存器，这里为什么用lea而不用add呢？因为rax中存储y的值还要用于后续传参，用add会改变rax中的值，这里用lea可以将运算后的值存到另一个寄存器中
92:  48 8b 55 f0       mov    -0x10(%rbp),%rdx  ; 将变量y的值复制到rbx寄存器
96:  48 8b 45 f8       mov    -0x8(%rbp),%rax   ; 将变量x的值复制到rax寄存器
9a:  48 83 ec 08       sub    $0x8,%rsp         ; 栈顶向下扩展8个字节，用于保证栈帧的边界是16字节对齐的
9e:  51                push   %rcx              ; 第七个参数压栈，
9f:  49 89 d1          mov    %rdx,%r9          ; r9寄存器，存第六个参数y，y的值在0x92指令中被复制到了rdx寄存器
a2:  41 b8 0f 00 00 00 mov    $0xf,%r8d         ; r8寄存器，存第五个参数15
a8:  48 89 c1          mov    %rax,%rcx         ; rcx寄存器，存第四个参数x，x的值在0x96指令中被复制到了rax寄存器
ab:  ba 03 00 00 00    mov    $0x3,%edx         ; rdx寄存器，存第三个参数3
b0:  be 02 00 00 00    mov    $0x2,%esi         ; rsi寄存器，存第二个参数2
b5:  bf 6c 00 00 00    mov    $0x6c,%edi        ; rdi寄存器，存第一个参数'l'
ba:  e8 00 00 00 00    callq  bf <main+0x4d>    ; 调用calc方法，call指令会把rip寄存器里的下一条指令的地址压栈，保留函数调用结束后要执行的指令地址，然后把被调函数的地址更新到rip寄存器中实现函数跳转
bf:  48 83 c4 10       add    $0x10,%rsp        ; 栈顶向上缩减16个字节，即恢复push第七个参数+Padding的16个字节空间
c3:  48 89 45 f8       mov    %rax,-0x8(%rbp)   ; 将calc函数的返回值赋值给变量x
		return x;
c7:  48 8b 45 f8       mov    -0x8(%rbp),%rax   ; 将变量x的值复制到rax寄存器作为main函数的返回值
}
cb:  c9                leaveq                   ; 相当于 mov %rbp %rsp; pop %rbp，与函数开头的 push %rbp; mov %rsp, %rbp 对应。将rbp的值复制到rsp寄存器，即rsp和rbp此时都指向当前函数的栈底；将栈顶元素出栈，即上一栈帧的栈底地址赋值到rbp中，也就是将rbp指向caller的栈底
cc:  c3                retq                     ; 相当于 pop %rip，与call指令的 push %rip 对应。将栈顶元素出栈，即将返回地址的值复制到rip指令地址寄存器，以实现继续执行caller中的指令


0000000000000000 <calc>:
long calc(char a, short b, int c, long d, long e, long f, long g) {
 0:  55                push   %rbp              ; 将main函数栈帧的rbp值压栈
 1:  48 89 e5          mov    %rsp,%rbp         ; main函数解释过了
 4:  48 83 ec 40       sub    $0x40,%rsp        ;	栈顶向下扩展64个字节，用于存储局部变量和寄存器中的值
 8:  89 f0             mov    %esi,%eax         ; 6个用于传参的寄存器值按顺序压栈
 a:  89 55 e4          mov    %edx,-0x1c(%rbp)
 d:  48 89 4d d8       mov    %rcx,-0x28(%rbp)
11:  4c 89 45 d0       mov    %r8,-0x30(%rbp)
15:  4c 89 4d c8       mov    %r9,-0x38(%rbp)
19:  40 88 7d ec       mov    %dil,-0x14(%rbp)
1d:  66 89 45 e8       mov    %ax,-0x18(%rbp)
		srand(time(NULL));
21:  bf 00 00 00 00    mov    $0x0,%edi         ; rdi寄存器赋值为0，对应NULL
26:  e8 00 00 00 00    callq  2b <calc+0x2b>
2b:  89 c7             mov    %eax,%edi
2d:  e8 00 00 00 00    callq  32 <calc+0x32>
		int h = rand();
32:  e8 00 00 00 00    callq  37 <calc+0x37>
37:  89 45 fc          mov    %eax,-0x4(%rbp)   ; rand函数返回值赋值到栈地址[rbp - 4, rbp]
		return a + b + c + d + e + f + g + h;
3a:  0f be 55 ec       movsbl -0x14(%rbp),%edx  ; 将变量a的值1字节带符号扩展成4字节，并存到rdx寄存器
3e:  0f bf 45 e8       movswl -0x18(%rbp),%eax  ; 将变量b的值2字节带符号扩展成4字节，并存到rax寄存器
42:  01 c2             add    %eax,%edx         ; rdx = rax + rdx
44:  8b 45 e4          mov    -0x1c(%rbp),%eax  ; 将变量c的值复制到rax寄存器
47:  01 d0             add    %edx,%eax         ; rax = rdx + rax
49:  48 63 d0          movslq %eax,%rdx         ; 将rax中的4字节带符号扩展成8字节，并存到rdx寄存器
4c:  48 8b 45 d8       mov    -0x28(%rbp),%rax  ; 将变量d的值复制到rax寄存器
50:  48 01 c2          add    %rax,%rdx         ; rdx = rax + rdx
53:  48 8b 45 d0       mov    -0x30(%rbp),%rax  ; 将变量e的值复制到rax寄存器
57:  48 01 c2          add    %rax,%rdx         ; rdx = rax + rdx
5a:  48 8b 45 c8       mov    -0x38(%rbp),%rax  ; 将变量f的值复制到rax寄存器
5e:  48 01 c2          add    %rax,%rdx         ; rdx = rax + rdx
61:  48 8b 45 10       mov    0x10(%rbp),%rax   ; 将变量g的值（在caller的栈帧中）复制到rax寄存器
65:  48 01 c2          add    %rax,%rdx         ; rdx = rax + rdx
68:  8b 45 fc          mov    -0x4(%rbp),%eax   ; 将局部变量h的值复制到eax寄存器
6b:  48 98             cltq                     ; 将eax的值带符号扩展成8字节存到rax寄存器
6d:  48 01 d0          add    %rdx,%rax         ; rax = rbx + rax

70:  c9                leaveq                   ; main函数解释过了
71:  c3                retq                     ; main函数解释过了
x86_64常用指令
相关知识延展
函数内联优劣

如果被调函数中没有再调用其他函数（这种函数通常被称为叶子函数），可以通过将被调函数指令直接替换到调用处来实现函数调用的。这也是常见的编译器自动优化的手段，叫做函数内联（Inline）。除了靠编译器自动优化，也可以在函数定义前加上inline关键字，来提示编译器对函数进行内联。

我们来看一段代码

#include <time.h>
#include <stdlib.h>

int add(int a, int b) {
    return a + b;
}

int main() {
    srand(time(NULL));
    int x = rand() % 3;
    int y = rand() % 7;
    return add(x, y);
}

使用gcc -O编译出来的汇编代码，并没有把add函数单独编译成一段指令顺序，而是在调用add(x, y)的时候，直接替换成了一个add指令

      6d: 01 c8                         addl    %ecx, %eax
;     return a + b;
      6f: 01 d8                         addl    %ebx, %eax

内联可以减少函数调用过程中保存寄存器值，数据压栈出栈等开销，提升调用性能。

不过这也是有代价的，内联把可以复用的指令在调用它的地方完全展开了，这就会导致程序的代码段指令数增加，占用空间变大。

Stack Overflow

一般是由于递归调用，或调用链过深，或在栈空间里创建非常占内存的变量（比如一个巨大的数组）导致的。

  1. Linux：默认栈空间大小为8MiB，在task_struct创建时（Linux不区分进程和线程）alloc并memset为0，具体代码见alloc_thread_stack_node。
  2. JVM：默认栈空间大小为1MiB，可以由-Xss指定
  3. Go：goroutine初始栈空间大小为2Kib，上限取决于操作系统位数，64位为1GiB，32位为250MiB
  4. Python：没有限制栈空间，不过有最大递归调用次数限制，可以通过sys.getrecursionlimit()获取，默认为1000
栈溢出攻击

栈溢出利用程序的漏洞，通过构造精心设计的数据，来覆盖函数的返回地址，进而打乱原有函数执行流程，跳入黑客预先设计好的恶意代码中。

栈溢出攻击基于以下几个原理：

  1. 函数栈帧保存了函数调用返回后下一条待执行指令的内存地址
  2. 程序的代码和数据都在内存中，直接从内存的二进制形式上是无法区分哪些是数据哪些是代码
  3. 局部变量存储在栈中，如果局部变量是一个数组，那么通过构造一个溢出当前栈帧的数据，就有可能覆盖上一栈帧的函数返回地址，进而跳转执行恶意代码

例如下面这段代码

void counter(char *data, char c) {
  char buffer[BUF_LEN];
  strcpy(buffer, data);
  ...
}

这就是一个典型的栈溢出代码，使用了不安全的strcpy函数，系统会盲目的将data的全部数据拷贝到栈空间的buffer上，而buffer的长度是有限的，一旦data的数据长度超过BUF_LEN，就会产生栈溢出。

基本原理就如上图所示，但实际上直接修改函数返回地址将其指向恶意代码是很难实现的，因为操作系统每次加载可执行文件到进程空间的位置都不是固定的，因此栈的位置实际是不固定的。为了解决这个问题，有了通过跳板(jmp esp)进行栈溢出的方式，这里就不展开了，感兴趣的可以看这篇文章。

栈溢出攻击的防护

  1. 栈不可执行：利用cpu硬件的特性，将栈设置为不可执行，禁止执行栈上的数据
  2. 栈保护：编译时打开栈保护开关，则会在函数的进入和返回的地方增加一些检测指令，在数据被修改时终止程序运行
  3. 内存布局随机化：将程序的加载位置、堆栈位置以及动态链接库的映射位置随机化
尾递归优化

尾递归是指在一个方法内部，递归调用后直接return，没有任何多余的指令。从函数栈帧角度来想，当前栈帧的所有数据在发生递归调用后都已经无用了，此时就无需将其保存到当前栈帧，只需将参数存入指定寄存器，goto到函数开始的指令继续执行就好了。

比如下面这种求阶乘的写法就不是一个尾递归，因为函数调用结束后还要拿到结果计算乘法

int factorial(int n) {
  if (n == 1) return 1;
  return n * factorial(n - 1);
}

而改写成下面这种写法就可以进行尾递归优化

int factorial(int n, int sum) {
  if (n == 1) return sum + 1;
  return factorial(n - 1, sum + n)
}
协程的函数栈切换

从CPU指令层面理解一些问题

LLVM
混淆编译
Compare And Swap原子操作

https://dslztx.github.io/blog/2020/01/14/CAS/

https://dslztx.github.io/blog/2019/06/08/%E6%B1%87%E7%BC%96%E6%8C%87%E4%BB%A4%E7%9A%84LOCK%E6%8C%87%E4%BB%A4%E5%89%8D%E7%BC%80/

超线程 hyperthreading

现代CPU一般声称有4核8线程、8核16线程等，这是什么意思呢？

考虑到CPU同内存、IO设备之间存取速度的严重不匹配，出现了乱序执行、分支预测等优化让CPU利用数据装载等待的时间，尽量多的执行后面的指令。但是某些指令必须要等到数据加载完成才能执行，比如数值求和比较等，此时CPU仍有大量空闲时间浪费。

为了提高CPU的利用率，聪明的工程师们想到了在CPU中额外增加一组寄存器，这样可以不覆盖当前线程的寄存器数据，同时执行另一个线程的指令，最大程度的利用计算单元，在可控的成本内（没有增加ALU等运算单元）提升了CPU利用率，这就是超线程。

有趣的优化

  1. 为什么将循环求和的结果放到一个局部变量中，会比将其放到一个通过指针传递过来的参数中，运行起来更快呢？

    1. 放到局部变量相当于将结果保存在rax寄存器中；而放到指针传递过来的参数相当于每次都要先根据内存地址读取上一个栈帧中的内存数据到寄存器，求和之后再把寄存器的值保存回内存中。CPU操作寄存器相比于内存耗时不在一个量级。

CPU运算

算术逻辑单元（ALU Arithmetic Logic Unit）

门电路

异或：A XOR B = (A & ~B) | (~A & B)

加法器

二进制的加法与十进制加法本质上并无差异，只不过二进制是逢2进1。拿个位举例，有4种组合，00/01/10/11，00和11个位相加的结果为0，01和10个位相加结果为1，这个输入和输出的关系就是异或门计算逻辑；同时对于11相加后需要向上一位进位，也就是与门计算逻辑。

所以通过一个异或门计算出个位，通过一个与门计算出是否进位，就通过电路算出了一个一位数的加法。

之所以叫半加器是因为这里只能处理个位加法，对于二位的加法除了加数和被加数之外，还要加上来自个位的进位信号，一共需要3个bit进行相加。要想实现3个数相加，可以通过组合2个半加器和1个或门组成一个全加器。

加法器优化
乘法器
减法运算
为什么减法器效率低
为什么负数的补码要按位取反并加1？
浮点运算

提升CPU利用率

流水线
乱序执行

好处：可以充分利用CPU，在等待内存操作返回的同时，执行其他指令

分支预测
Linux中的likely/unlikely
并行计算：SIMD
一些有趣小🌰
  • 找出一个数组中小于某数x的个数。排序后的数组运行更快
  • 两个for循环嵌套，循环次数多的写里面

内存

MMU与TLB

M(Modified) E(Exclusive) S(Shared) I(Invalid)协议

缓存行有4种不同的状态

  1. 已修改Modified（M）：缓存行是脏的，与主存的值不同。如果别的CPU内核要读主存这块数据，该缓存行必须回写到主存，状态变为共享（S）
  2. 独占Exclusive（E）：缓存行只在当前缓存中，而且与主存值相同。当别的缓存读取它时，状态变为共享；当前写数据时，变为已修改状态
  3. 共享Shared（S）：缓存行也存在与其他缓存中且是干净的，缓存行可以在任意时刻抛弃
  4. 无效Invalid（I）：缓存行是无效的

上图为4中状态间的有限状态机转换，有两种场景会触发状态的转换：

  1. 缓存所在CPU的读写（上图中左半部黑实线）
    1. PrRd：处理器请求读一个缓存块
    2. PrWr：处理器请求写一个缓存块
  2. 其他CPU的读写，通过总线发送信号，然后被其他总线snooper嗅探到（上图中右半部红虚线）
    1. BusRd：嗅探到其他处理器请求读一个缓存块
    2. BusRdX：嗅探到其他处理器请求写一个该处理器不拥有的缓存块
    3. BusUpgr：嗅探到其他处理器请求写一个该处理器拥有的缓存块
    4. Flush：snooper请求回写整个缓存到主存
    5. FlushOpt：snooper请求将整个缓存块发送到另一个处理器（缓存到缓存的赋复制）

CacheLine与伪共享

一个CacheLine包含：标识位、和内存匹配tag、数据块。其中标识位包含：V（Valid）表示这个缓存块是否被使用，M（Modified）表示这个缓存块是否被写过。数据块大小一般为64Byte。

# getconf -a | grep CACHE

LEVEL1_ICACHE_SIZE                 32768
LEVEL1_ICACHE_ASSOC                8
LEVEL1_ICACHE_LINESIZE             64
LEVEL1_DCACHE_SIZE                 32768
LEVEL1_DCACHE_ASSOC                8
LEVEL1_DCACHE_LINESIZE             64
LEVEL2_CACHE_SIZE                  2097152
LEVEL2_CACHE_ASSOC                 8
LEVEL2_CACHE_LINESIZE              64
LEVEL3_CACHE_SIZE                  16777216
LEVEL3_CACHE_ASSOC                 16
LEVEL3_CACHE_LINESIZE              64
LEVEL4_CACHE_SIZE                  0
LEVEL4_CACHE_ASSOC                 0
LEVEL4_CACHE_LINESIZE              0

L1 数据Cache大小为32K，包含32 * 1024 / 64 = 512个CacheLine，标识为和tag有专门的电路，不占用缓存块的空间。

https://itimetraveler.github.io/2018/09/09/CPU%20Cache%E4%B8%8E%E7%BC%93%E5%AD%98%E8%A1%8C/

存储与I/O设备

DMA

INT中断

  • 地址总线、数据总线
  • ext3/ext4文件系统

为什么ARM架构在移动互联网时代大行其道

操作系统

  • FUTEX(Fast Userspace muTEX)系统调用

内存管理

物理内存管理

伙伴系统
小对象分配

虚拟内存管理

页表布局

https://github.com/lorenzo-stoakes/linux-vm-notes/blob/master/sections/page-tables.md

Linux中有4级页表，每级由pXXval_t包装而成的 pXX_t类型的数组组成

  1. Page Global Directory (PGD)
  2. Page Upper Directory (PUD)
  3. Page Middle Directory (PMD)
  4. Page Table Entry Directory (PTE)

这些类型的具体定义取决于不同的arch，比如在x86架构下的定义为：

typedef unsigned long   pgdval_t;
typedef unsigned long   pudval_t;
typedef unsigned long   pmdval_t;
typedef unsigned long   pteval_t;

typedef struct { pgdval_t pgd; } pgd_t;
typedef struct { pudval_t pud; } pud_t;
typedef struct { pmdval_t pmd; } pmd_t;
typedef struct { pteval_t pte; } pte_t;

  • p[gum]d_t结构定义在arch/x86/include/asm/pgtable_types.h中，而pte_t和pXXval_t类型定义在arch/x86/include/asm/pgtable_64_types.h中，通过宏定义在pgtable_types文件中被include，这样是为了尽量复用32和64位x86代码。

  • 在64位x86架构，以及4KB页大小情况下，每个PGD/PUD/PMD/PTE页表均包含512个指针，指向下一级页表的地址，每个指针8byte，即每个页表占用4KB内存空间，刚好一个内存页。每个页表可包含的指针个数使用宏定义PTRS_PER_XXX，例如PTRS_PER_PGD，PTRS_PER_PTE

  • 虚拟地址对应的每个页表的下标需要先通过>>然后& MASK计算得出

    • 右移位数：PGDIR_SHIFT=39, PUD_SHIFT=30, PMD_SHIFT=21, PAGE_SHIFT=12
    • MASK：以PTRS_PER_XXX - 1为掩码，将所有高于第9位的位全部置0

  • 计算每个页表的index被定义成了inline函数，比如下面这个计算pte在pmd中的index的方法

static inline unsigned long pte_index(unsigned long address)
{
	return (address >> PAGE_SHIFT) & (PTRS_PER_PTE - 1);
}
  • 通过页表基地址+index可以获得下一级页表的基地址
static inline pte_t *pte_offset_kernel(pmd_t *pmd, unsigned long address)
{
	return (pte_t *)pmd_page_vaddr(*pmd) + pte_index(address);
}
0000000000000000 000000010 000000101 000000110 100100101 000000100100
[   RESERVED   ] [  PGD  ] [  PUD  ] [  PMD  ] [  PTE  ] [  OFFSET  ]

PGD offset =    000000010 = 2
PUD offset =    000000101 = 5
PMD offset =    000000110 = 6
PTE offset =    100100101 = 293
phy offset = 000000100100 = 36

         PGD
        -----   
      0 |   |         PUD
      . |   |        -----   
      2 |~~~|----->0 |   |   
      . |   |      . |   |         PMD
      . |   |      . |   |        -----   
      . |   |      5 |~~~|----->0 |   |   
      . |   |      . |   |      . |   |         PTE
      . |   |      . |   |      . |   |        -----   
    512 -----      . |   |      6 |~~~|----->0 |   |   
                   . |   |      . |   |      . |   |   
                 512 -----      . |   |      . |   |   
                                . |   |      . |   |   
                                . |   |      . |   |     physical page
                              512 -----      . |   |        -----
                                           293 |~~~|----->0 |   |
                                             . |   |      . |   |
                                           512 -----     36 | h |
                                                          . | e |
                                                          . | l |
                                                          . | l |
                                                          . | o |
                                                         41 | ! |
                                                          . |   |
                                                        4096-----
Page Table Entry Flags
  • 由于每个页目录项是页对齐的，所以每个页表首地址的低PAGE_SHIFT位都是0，也就是说PGD/PUD/PMD/PTE中指针的值低PAGE_SHIFT位是没用到的，这样就可以将这些位作为标志位存储page的配置信息。另外在x86-64架构中，只有46个可寻址位，所以不参与寻址的高位也可以存储标志位
  • 这样做的影响是：计算页目录index时需要忽略标志位。在页大小为4KB情况下，是通过PTE_PFN_MASK和PTE_FLAGS_MASK两个宏定义计算的。更大的页大小需要些特殊处理，这里先不赘述了，会在[Huge Page](#Huge Page)一节详述。
PAGE_MASK = ~((1UL << 12) - 1) = 
1111111111111111111111111111111111111111111111111111000000000000

__PHYSICAL_MASK = ((1UL << 52) - 1) = 
0000000000001111111111111111111111111111111111111111111111111111

PTE_PFN_MASK = PAGE_MASK & __PHYSICAL_MASK = 
1111111111111111111111111111111111111111111111111111000000000000
0000000000001111111111111111111111111111111111111111111111111111 = 
0000000000001111111111111111111111111111111111111111000000000000

PTE_FLAGS_MASK = ~PTE_PFN_MASK =
1111111111110000000000000000000000000000000000000000111111111111
  
static inline pteval_t pte_flags(pte_t pte)
{
	return native_pte_val(pte) & PTE_FLAGS_MASK;
}
  • 这些额外的标志位用于表示页表项中的页的各种状态，有一点需要弄清楚：PGD中的 pdg_t条目的标志位代表的是其指向的PUD页的状态，所以每一个pXX_t条目的标志位实际上表示的是下一级PXX页的状态
  • 标志位的取值通过(pXX_FLAGS_MASK & pXX_val) & (((pteval_t)1) << FLAG_OFFSET)计算，比如pte_write = pte_flags(pte) & (1UL << 1)
  • 一些常用的标志位含义（全部定义可见arch/x86/include/asm/pgtable_types.h）
    • _PAGE_PRESENT: 用于确定页在内存中是否可用，还是由于页换出或其他原因导致不可用
    • _PAGE_RW: 如果清除该标志，则内存页是只读的（常用语Copy On Write）
    • _PAGE_USER: 如果清除该标志，则只有内核态能访问内存页
    • _PAGE_ACCESSED: 页面已被访问，如果在创建页面时将其清除，则对该页面的首次访问将设置该标志，并且该标志将保持设置状态，直到手动清除为止
    • _PAGE_DIRTY: 页面已被修改，如果在创建页面时将其清除，则对该页面的首次写入将设置该标志，并且该标志将保持设置状态，直到手动清除为止
    • _PAGE_PSE: 为1则表示该页是一个Huge Page，即1GB或2MB而不是4KB
    • _PAGE_GLOBAL: 为1则表示普通的TLB缓存刷新不会驱逐该页
PGD与进程切换
Huge Page

编译原理

程序链接与装载

  1. Preprocess -> Compile -> Assemble -> Link

库打桩机制

  • 编译时打桩：利用编译器的-I参数，以及宏定义，在编译时将目标函数的声明替换掉。典型的应用有：
    • Redis中根据不同的编译参数选择使用不同的内存分配器，并将malloc, free等函数利用宏定义替换成不同内存分配器的函数声明，比如je_malloc, je_free
  • 链接时打桩
  • 运行时打桩

链接

链接的接口——符号

  • C++中namespace与函数重载在符号表中的体现：编译器根据函数签名中的函数名、参数类型以及所在类和命名空间生成修饰后名称，保证链接时不会出现函数重复定义。下面是GCC编译器生成修饰后名称，

    函数签名 修饰后名称
    int func(int) _Z4funci
    float func(float) _Z4funcf
    int ClassA::func(int) _ZN6ClassA4funcEi
    int ClassA::ClassB::func(int) _ZN6ClassA6ClassB4funcEi
    int NamespaceA::ClassC::func(int) _ZN10NamespaceA6ClassC4funcEi

  • C++中extern "C"用途：告知C++编译器，对于其修饰的代码块，不要按照C++函数修饰规则生成符号。这在C++程序调用C库函数，或C++程序暴露C函数接口时是非常有必要的，否则在链接时会报undefined reference错误

  • 弱符号：库中定义的弱符号可以被用户定义的强符号所覆盖，弱符号相当于函数的默认实现，用户可以在链接时使用自定义的实现覆盖它，进而使得依赖此函数的第三方在不改动代码的情况下替换函数的功能

  • 弱引用：程序中声明的弱引用在链接时如果没有找到对应的符号，不会报链接错，其函数地址为0。利用此特性，程序可以选择性使用某些扩展功能模块，当链接扩展模块时则使用对应函数，否则也不影响程序正常运行

动态链接

GOT与C++中的虚函数表
  • C++中的虚函数也是在运行时通过修改对象的虚函数表地址来实现多态的
函数的入口一定是main吗

还有一个衍生问题，为什么main函数在Java中一定要是static的？

程序真正执行的入口是main吗？（glibc中main函数地址并不是ELF中的entry）

计算机网络

相关资料

数据链路层

FDB(Fowarding dataase)

网络层

ARP(Address Resolution Protocol)

IP

IPv6
一些小问题
  • 为什么IPv6在http请求的路径中需要加[]？
    • IPv6可以使用双冒号::表示一组0或多组连续的0，但只能出现一次
    • http url可以使用ip:port作为domain，也可以省略port，此时http默认为80端口，https默认为443端口
    • 如果不用[]扩起，则形如https://2021:0216::1234:6789/path/to的url就没办法区分请求的是2021:0216:0000:0000:0000:0000:0000:1234地址的6789端口还是2021:0216:0000:0000:0000:0000:1234:6789地址的443端口

TUN/TAP及其应用

socket

UnixDomain Socket

传输层

Packet Filtering & iptables

应用层协议

HTTP家族

HTTP2特性
  1. Headers压缩：HPACK算法
  2. 二进制分帧
  3. 多路复用，一个TCP连接能同时承载多个请求。每个流都有一个ID, 即可以同时发送多个请求，不再依赖多个 TCP 连接去实现多流并行了。
  4. 解决HTTP头部阻塞（仍未解决TCP头部阻塞）
    • HTTP头部阻塞：前一个请求未收到响应时，不能使用该TCP连接发送下一个请求。根本原因还是请求和响应的每一个packet之间缺乏一个key进行关联，导致如果要支持同一个TCP连接同时发送多个请求，在收到不同请求的响应数据包后，无法找到它们对应的是哪个请求以及无法组装同一个响应的不同数据包。而HTTP2引入分帧后，在每个帧中增加了StreamID以串联同一个TCP连接中不同的流。
    • TCP头部阻塞：由于TCP需要保证消息的有序性，所以一个数据包丢包后，其后面的数据包就算接收到也不会回复ack。意味着后面的数据包都被这个丢失的数据包阻塞了。
  5. 服务端推送：服务端可以在客户端的某个请求之后，主动向客户端推送其他资源。这也得益于二进制分帧，通过StreamID可以区分不同的流。而在HTTP中，没办法实现服务端推送，因为客户端区分不了是某个请求的响应还是服务端主动推送的。
QUIC

DNS

SSH

SSH原理： https://mp.weixin.qq.com/s/E05ZSzJQFc6efXtvs5sf1g

更多内容详见RFC4251

SSH(Secure Shell)是为了在不安全的网络上提供安全的远程登录和其他网络服务，用来替代不安全的终端访问方式，例如telnet 。

SSH协议可以理解为一组协议规范，主要包括3个部分：

  1. 传输层协议[SSH-TRANS]：
  2. 用户认证协议[SSH-USERAUTH]：
  3. 会话连接协议[SSH-CONNECT]：

在传输层依赖于TCP协议，采用非对称加密（非对称加密详见）实现身份认证

SSH使用账号密码认证原理
SSH使用秘钥认证原理

平常使用ssh user@ip默认使用当前用户的id_rsa秘钥文件，当然也可以通过ssh -i rsa指定私钥。

  1. 私钥中包含了公钥，也就是说通过私钥可以计算出公钥，公私钥计算公式如下，具体可见 RFC3447。通过ssh-keygen -yf ~/.ssh/id_rsa可以提取公钥

    RSAPublicKey ::= SEQUENCE {

          modulus           INTEGER,  -- n
      publicExponent    INTEGER   -- e
  }

    RSAPrivateKey ::= SEQUENCE {

          version           Version,
      modulus           INTEGER,  -- n
      publicExponent    INTEGER,  -- e
      privateExponent   INTEGER,  -- d
      prime1            INTEGER,  -- p
      prime2            INTEGER,  -- q
      exponent1         INTEGER,  -- d mod (p-1)
      exponent2         INTEGER,  -- d mod (q-1)
      coefficient       INTEGER,  -- (inverse of q) mod p
      otherPrimeInfos   OtherPrimeInfos OPTIONAL
  }

  2. 公钥和私钥计算出的秘钥指纹是相同的。通过ssh-keygen -lf ~/.ssh/id_rsa可以计算fingerprint，秘钥指纹生成算法如下（bigendian）

    00 00 00 07  ssh-rsa 00 00 00 03 01 00 01 00 00 01 01 00 01 ... 63 25
    [tag length] [ tag ] [e length ] [   e  ] [n length ] [      n      ]

    *.pub文件中的第二段就是通过：先将公钥按照上面的算法生成的字节，再用base64编码

    ssh-keygen -lf ~/.ssh/id_rsa.pub生成的SHA256摘要指纹是通过：先将公钥按照上面的算法生成的字节，再用sha256算法生成digest，再用base64编码

ssh -i鉴权流程：

  1. 客户端与服务端协商产生会话密钥
  2. 客户端向服务端发送登录请求（如 root@192.168.0.2），发送的信息包括用户名root以及根据公/私钥计算的公钥指纹，且所有的数据都是经过会话秘钥加密过的
  3. 服务端收到数据后使用会话秘钥解密得到登录的用户名root以及秘钥指纹，然后读取/root/.ssh/autorized_keys文件中的所有公钥数据，通过上述算法生成指纹与客户端发送的指纹对比，从而找到客户端对应的公钥
  4. 服务端使用找到的客户端公钥对一个随机数进行加密然后发送到客户端
  5. 客户端使用私钥对服务的发送的随机数密文进行解密，然后把解密后的结果发给服务端
  6. 服务端验证客户端解密后的随机数与之前发送的数据一致，则对客户端的身份验证通过
SSH tunneling原理及使用

数据结构与算法

后端技能

数据库

MySQL

InnoDB的Page Structure

  • 为什么User Records要以单链表形式存储而非数组呢？
    • 插入记录O(1)时间复杂度，无需移动数据；而向数组中间插入记录必须挪动后面所有的记录，成本太高
    • 每条记录的大小是不固定的

分库分表

一致性哈希

缓存

缓存技术总览

缓存淘汰策略

TinyLFU
W-TinyLFU

Redis

Redis数据结构

Redis编码
Redis对象
0            3 4                7 8          31 32              63 64         127
|<-- type -->| |<-- encoding -->| |<-- lru -->| |<-- refcount -->| |<-- prt -->|

type: Redis对象类型，String, List, Set, Sorted set, Hash
encoding: 对象的编码类型，Raw, Integer, Hash table, Skiplist, Embstr等
lru: 表示与lru_clock的相对值（用于LRU驱逐策略）；或LFU的数据，低8bit表示frequency，高16bit表示最后访问时间（以分钟为单位）
refcount: 此对象的引用计数
ptr: 指向对象值的指针
String Object

字符串长度<= 44使用embstr，否则使用raw string。之所以根据字符串长度有不同的实现，是因为embstr只需要一次内存分配，而raw string需要2次内存分配，而且会产生内存碎片，另外重要的一点是String对象作为最基础的对象，通常长度不会太长（作为command、key等）。

而44这个数字，是因为String Object中一个robj对象占用16字节，sdshdr8占用3字节，\0占用1字节，也就是说就算是一个空字符串也要占用20字节。Redis使用的内存分配器默认是jemalloc，根据class_size向上取整理应要分配32字节，但是这样的话字符串最大长度只有12字节，没办法适用大部分场景。所以就扩大了限制以适配64字节这个size。

Redis通信协议

RESP（REdis Serialization Protocol）

用于Redis Client和Server通信，RESP可以兼顾以下几个优点：1. 实现简单 2. 解析速度快 3. Human readable。

RESP尽量遵循简单的请求-响应模型，即Client发送不同参数组成的命令，Server接收到后处理并响应。但是有2个例外的场景：

  1. Pipeline：客户端会一次性发送多个请求命令，然后等待批量的响应（多个请求之间用\r\n分隔）
  2. Pub/Sub：不再需要客户端主动请求，因为服务端会在Channel有新Message时主动通知客户端

RESP支持多种数据类型并可以用一个字节枚举，请求和响应的数据由多种不同数据类型的part组成。每个part的数据以一个字节表示的数据类型开头，\r\n(CRLF)结尾。

RESP3在RESP2的基础上额外增加了多种数据类型，同时协议向后兼容。RESP3在Redis 6.0及以上版本引入，但是为了保证Client的兼容默认是关闭的，可以通过HELLO 3命令升级为RESP3，当然也可以通过HELLO 2降级回RESP2。

数据类型 first byte 说明 示例
Simple String + +<string>\r\n。字符串中不能包含CR或LF，所以不是二进制安全的 +PONG\r\n
Simple Error - 规则与Simple String相同。第一个大写单词代表错误码，客户端会把字符串当成异常信息来处理 -Error message\r\n
Number : 64位有符号整数，:<number>\r\n。INCR, LLEN等命令会返回具体的数值，而SETNX, EXISTS等命令会返回1代表true/实际执行了操作 或 0代表false/没有执行操作 :666\r\n
Blob String $ $<length>\r\n<bytes>\r\n，因为有字节长度，所以是二进制安全的。在RESP2中使用$-1\r\n表示Null，比如GET的key不存在 $3\r\nfoo\r\n
Array * Client使用数组来发送命令，某些命令Server也会返回数组，例如SMEMBERS。”*” 后面跟着数组长度N，随后是CRLF，接着是N个任何类型的元素（可以是不同类型） *2\r\n$3\r\nfoo\r\n$3\r\nbar\r\n
数据类型 first byte 说明 示例
Null _ _\r\n _\r\n
Double , ,<floating-point-number>\r\n，inf表示正无穷，-inf表示负无穷 ,3.1415926\r\n
Boolean # #t\r\n代表True，#\f\r\n代表False
Blob Error ! 规则与Blob String相同。第一个大写单词代表错误码，客户端会把字符串当成异常信息来处理 !21\r\nSYNTAX invalid syntax\r\n
Verbatim String = 规则上与Blob String类似，前三个字节表示富文本类型，比如txt/mkd，第四个字节为:，然后是真正的字符串 =8\r\ntxt:test\r\n
Big Number ( 用来代表超过有符号64整数的数字，(<big number>\r\n。大数可以是正数或负数，但不能包含小数部分 (3492890328409238509324850943850943825024385\r\n
Map % 与Array类似，”%”后跟着键值对的个数N，随后是CRLF，接着是N个任何类型的Key-Value对 %2\r\n+foo\r\n:1\r\n+bar\r\n#t\r\n
Set ~ 与Array类似，不过语义上稍有不同，Set返回的元素是无序的。协议上并没有强制保证Set内的元素不重复，Client需要处理这种情况 ~3\r\n+foo\r\n:1\r\n#f\r\n

下面我们通过nc命令，使用RESP协议尝试不同的请求命令，加深下理解。

Tips：当我们需要在线上环境定位问题时，可能没有易用的redis-cli命令，此时可以使用nc命令按照RESP规范进行请求。当然Redis也提供了另一种简化的使用方式，叫做内联命令(Inline Commands)， 可以通过空格分隔的参数进行请求。

echo '*1\r\n$7\r\nUNKNOWN\r\n' | nc redis 6379
-ERR unknown command `UNKNOWN`, with args beginning with: 

echo '*2\r\n$3\r\nGET\r\n$3\r\nfoo\r\n' | nc redis 6379
$-1

echo '*3\r\n$3\r\nSET\r\n$3\r\nfoo\r\n$6\r\nfooval\r\n' | nc redis 6379
+OK

echo '*2\r\n$3\r\nGET\r\n$3\r\nfoo\r\n' | nc redis 6379
$6
fooval

echo '*3\r\n$5\r\nSETNX\r\n$3\r\nfoo\r\n$6\r\nfooval\r\n' | nc redis 6379
:0	# SETNX，此时foo已经存在，所以返回:0表示没有执行操作

echo '*5\r\n$5\r\nLPUSH\r\n$3\r\nbar\r\n$2\r\nv1\r\n$2\r\nv2\r\n$2\r\nv3\r\n' | nc redis 6379
:3

echo '*4\r\n$6\r\nLRANGE\r\n$3\r\nbar\r\n$1\r\n0\r\n$2\r\n-1\r\n' | nc redis 6379 
*3
$2
v3
$2
v2
$2
v1
echo 'UNKNOWN' | nc redis 6379
-ERR unknown command `UNKNOWN`, with args beginning with:

echo 'GET foo' | nc redis 6379
$-1

echo 'SET foo foovalue' | nc redis 6379
+OK

echo 'SET foo foovalue NX' | nc redis 6379
$-1

echo 'lpush bar v1 v2 v3' | nc redis 6379
:3

echo 'lrange bar 0 -1' | nc redis 6379
*3
$2
v3
$2
v2
$2
v1

淘汰机制

  • 每次lookupKey都会更新robj的lru值
  • LFU的低16位存储上次访问的时间戳对应的分钟数

内存缓存

消息队列

编码 & 压缩 & 加密

编码

编码的本质就是双方根据一定的规则对数据进行处理

字符编码

  • 字符：各种文字和符号的总称，包括各国家文字、标点符号、图形符号、数字等。 也就是说，它是一个信息单位，一个数字是一个字符，一个文字是一个字符，一个标点符号也是一个字符。
  • 字符集：字符的集合，不同集合支持的字符范围自然也不一样，譬如ASCII只支持英文，GB18030支持中文等等。在字符集中存在一个码表，每个字符在各自字符集对应着唯一一个码。但是同一个字符在不同的字符集中对应的码不同，比如字符“世”在Unicode中为U+4e16，在GBK中为0xcac0
  • 字符编码：定义字符集中的字符如何编码为特定的二进制数，以便在计算机中存储。字符集与字符编码通常是一一对应的，比如GB18030既可以代表字符集也可以代表字符编码，它为了兼容ASCII码，编码方式为大于255采用两字节来代表一个字符，否则就是兼容模式，一个字节代表一个字符。当然也存在特例，比如Unicode字符集就有多种编码实现（UTF-8，UTF-16等）
字符集与字符编码发展史
  • 最早的计算机只需要使用英文符号，加上数字和一些特殊符号，然后用8位二进制映射到128个不同的字符串里，这样就能表示日常需要的所有字符了，这就是我们常说的ASCII码（American Standard Code for Information Interchange，美国信息交换标准代码）。在ASCII码中，031是控制字符如换行删除等，32126是可打印字符可以通过键盘输出并显示出来。
  • 后来计算机传入欧洲，一些欧洲国家决定对ASCII编码进行适当的“改造”：利用字节中闲置的最高位编入新的符号，这样一来可以表示最多256个符号。但是欧洲的语言体系有个特点：小国家特别多，每个国家可能都有自己的语言体系，因此即便有256个字符也没办法统一欧洲的语言环境。后来大家想了一个折中的方案：在256个字符中，前128字符和ASCII编码表示的字符完全一样，后128个字符每个国家或地区都有自己的编码标准。根据这个规则，形成了很多子标准：ISO-8859-1、ISO-8859-2。。。
  • 计算机传入亚洲后，国际标准已被完全不够用，各个国家根据自己的地区特色，发明了适用自身的字符集与编码，譬如中国大陆的GB2312，日本的Shift JIS等等 这些编码都是用双字节来进行存储，它们对外有一个统称ANSI（American National Standards Institute），也就是说GB2312或Shift JIS等都是ANSI在各自地区的不同标准。
  • 到了全球互联网时代，不同国家需要在互联网上进行信息交互，这时候由于各自编码标准都不一样，彼此之间都是乱码，无法良好的沟通交流。于是这时候ISO组织与统一码联盟整合推出了Unicode字符集，它使用4字节的数字来表达每个字符。每个数字代表唯一的至少在某种语言中使用的字符。这时候所有的字符都可以采用同一个字符集，有着相同的编码，可以愉快的进行交流了。
UTF-8编码规则

UTF-8（8-bit Unicode Transformation Format）是一种针对Unicode的可变长度字符编码。它可以用来表示Unicode标准中的任何字符，且其编码中的第一个字节仍与ASCII兼容。

UTF-8 的编码规则很简单：

  1. 对于单字节字符，与ASCII编码完全相同
  2. 对于n字节的字符，第一个字节的前n个bit都置为1，第n+1个bit置为0，后面字节的前两位一律置为10，剩余的bit用于从左至右依次存储Unicode的码点

Unicode与UTF-8转换关系表

Unicode码点位数 Unicode码点范围 UTF-8字节序
[0, 7] U+0000~U+007F 0xxxxxxx
[8, 11] U+0080~U+07FF 110xxxxx 10xxxxxx
[12, 16] U+0800~U+FFFF 1110xxxx 10xxxxxx 10xxxxxx
[17, 21] U+10000~U+1FFFFF 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
[22, 26] U+200000~U+3FFFFFF 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
[27, 31] U+4000000~U+7FFFFFFF 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx

举几个例子

字符 Unicode UTF-8
Ā U+0100 11000100 10000000 = C4 80
世 U+4E16 11100100 10111000 10010110 = E4 B8 96
🎅 U+1F385 11110000 10011111 10001110 10000101 = F0 9F 8E 85
手持两把锟斤拷，口中疾呼烫烫烫
MySQL中的utf8mb4

utf8无法存储emoji，因为MySQL中的utf8最多只用3字节存储，而emoji使用4字节编码，比如🎅的16进制编码为0xF09F8E85

Python2中讨厌的编码

Protobuf

varint
zigzag

JSON

simdjson是何方神圣

Base64家族

压缩

GZip

LZ4

Snappy

加密

非对称加密

RSA算法的数学原理

分布式

http://thesecretlivesofdata.com/raft/

RPC

内存分配与回收

分配器多种多样，比如通用的jemalloc、tcmalloc，或者各个语言自己实现的比如pymalloc，但是他们的目标是一样的：

  1. 基本功能：将一块内存根据固定单位的页定义出来，然后区分对象大小分别管理内存，小内存分成若干类，专门用来分配固定大小的内存块，并用一个表管理起来，降低内部碎片，减少Page Fault，提升内存分配速度。大内存则以页为单位管理，配合小对象所在页， 降低碎片。
  2. 回收：当释放内存时，要能够合并小内存为大内存，根据一些条件，该保留的就保留下来，在下次使用时可以快速响应
  3. 多线程下性能优化：每个线程独占一段内存，被称为TLS，这样线程内操作时可以不加锁，提高性能。当独占的内存不够用时再从全局的内存中分配。但随之而来的也有些待解决的问题：
    1. 如何尽量减少到全局内存池中分配导致锁冲突
    2. 如何解决不同线程内存利用率不一致导致的overhead
    3. 如何在空闲时将线程独占内存释放回全局内存中以便其他线程使用

当占用内存的对象不再可能被使用的时候，需要对其使用的内存进行回收，常见的回收算法有引用计数法，标记清除法，它们的目标是：

  1. 尽可能多的识别出不使用的内存空间
  2. 减少内存回收导致的外部碎片
  3. 降低内存回收对程序运行的影响，耗时尽量短

eBPF

编程语言

C

C++

Python

  • 内存管理

底层实现

一切皆对象

int

https://www.dongwm.com/post/python-memory-usage-1/

import

import原理详细解读

奇淫巧技

__new__与__init__

__new__用于创建对象；__init__用于初始化对象。

__new__会在使用ClassName()创建对象时自动调用，__init__会在new返回创建的实例后被调用，并把返回的实例传入__init__，对应入参self。

如果重写了父类的__new__但是并没有返回实例，则不会调用__init__

类方法与实例方法

类方法对应的地址全局唯一，不同的对象对应的类方法id都是相同的。

不同的对象对应的实例方法id是不同的，实例方法也可以通过Class.method(object)调用，实例方法第一个参数是self也就是实例，我们平常用的object.method(args)本质上就是在对象创建时通过Class.method生成一个新的偏函数(partial)，将第一个参数绑定成实例，然后重新setattr(object, method, partialed_method)。

mock的原理

  1. Python中一切都是对象，module是对象，class是对象，function也是对象
  2. globals() 和 locals()
  3. setattr()

Java

JVM

Object Header

Scala

Go

为什么Go的可执行文件特别小还不需要依赖so

内功心法

可维护性 = 当依赖变化时，有多少代码需要随之改变

可扩展性 = 做新需求或改逻辑时，需要新增/修改多少代码

可测试性 = 运行每个测试用例所花费的时间 * 每个需求所需要增加的测试用例数量 * 编写测试用例的难易程度

面向对象思想

  • 四大特性：封装、抽象、继承、多态
  • 与面向过程的区别于联系
  • 接口与抽象类
  • 基于接口而非实现编程
  • 多用组合少用继承
  • 面向过程的贫血模型与面向对象的充血模型

设计原则

  • S(Single Responsibility Principle)：单一职责原则
  • O(Open Close Principle)：开闭原则
  • L(Liskov Substitution Principle)：里氏替换原则
  • I(Interface Segregation Principle)：接口隔离原则
  • D(Dependency Inversion Principle)：依赖导致原则
  • DRY(Don’t Repeat Yourself)
  • KISS(Keep It Simple, Silly)
  • YAGNI(You Aren’t Gonna Need It)
  • LOD(Law Of Demeter): 迪米特法则，又叫做最少知识原则

设计模式

  • 创建型

    • 常用：单例模式、建造者模式、工厂模式（简单工厂、工厂方法）
    • 不常用：抽象工厂、原型模式

  • 结构型

    • 常用：代理模式、桥接模式、装饰器模式、适配器模式
    • 不常用：门面模式、组合模式、享元模式

  • 行为型

    • 常用：观察者模式、模板模式、策略模式、职责链模式、迭代器模式、空对象模式
    • 状态：访问者模式、备忘录模式、命令模式、解释器模式、中介模式

    编码规范

  • 命名，命名，还是命名

  • 函数

  • 对象和数据结构

  • 错误处理

  • 类

接口设计规范

RESTful接口设计可以参照Google的这篇指南

https://cloud.google.com/apis/design

具体应用可以参考K8S的接口设计

https://kubernetes.io/docs/reference/generated/kubernetes-api/v1.18/#-strong-api-overview-strong-

代码重构

  • 重构的目的（Why）、对象（What）、时机（When）、方法（How）
  • 保证重构不出错的技术手段：单元测试、代码可测试性

领域驱动设计

大数据

批流处理

存储

实时分析

云原生

虚拟化技术

KVM

ioctl syscall -> ksys_ioctl -> do_vfs_ioctl -> vfs_ioctl -> unlocked_ioctl -> kvm_vm_ioctl ->

容器技术

容器底层核心技术

Namespace

CGroup

  • OOM Kill进程的日志可以在/var/log/kern.log中查看，

Docker

Docker网络

Podman

Kubernetes

K8S网络

Flannel网络原理

https://blog.laputa.io/kubernetes-flannel-networking-6a1cb1f8ec7c

  • node的annotation中有flannel相关的信息，比如Vtep MAC、PublicIP、podCIDR等
  • flannel会通过IndexerInformer watch k8s node的变更
  • 对于node的变更，flannel会调用netlink包中的FDB、ARP接口，更新fdb表和路由表

http://just4coding.com/2020/04/20/vxlan-fdb/

Helm

三大概念

  1. Chart：代表一个helm包，包含了运行一个应用/工具/服务所需要的所有资源定义，比如在k8s中部署MySQL需要Deployment定义、Service定义、PVC定义等
  2. Repository：存储共享各种Charts的地方
  3. Release：在k8s集群中运行Chart实例，一个Chart可以多次安装到同一集群中，每次安装时都会创建一个新版本。比如在一个集群中运行两个不同版本的MySQL实例

常用操作

  1. helm repo add NAME URL，可以到https://artifacthub.io搜索各种Chart对应的repo。`helm search repo NAME`，在已经添加的repo中模糊搜索Chart
  2. helm install NAME CHART Flags，部署Chart到k8s集群，可以指定-f config.yaml或--set key=value覆盖Chart中的配置值。helm upgrade RELEASE CHART，更新Release的配置，一般用于更新配置值
  3. helm rollback RELEASE REVISION，回滚Release到指定版本，可以通过helm history RELEASE查看发布历史
  4. helm list查看部署的releases，helm uninstall RELEASE将release从集群中卸载
  5. helm create NAME创建一个新的Chart，你可以定义自己的Chart，helm lint PATH用于校验写的chart是不是合法的

ServiceMesh

系统设计

代码之外的软技能

效率工具

性能分析

火焰图