ReZero's Utopia.

# CSAPP

Word count: 5.5kReading time: 26 min
2020/10/01 Share

## Not be the real thing

1. digit might be overfolw

2. float will not be overflow, but could lost precision

## Memory

1. RAM: Random am

## Bit

Exclusive-Or(XOR) A ^ B

Union | //并

Complement ~ //补

Intersection & //交

Symmetric difference ^ //差

## Integer

Unsigned：

$$B2U(X)=\sum_{i=0}^{w-1}x_i*2^i$$

Signed：

$$B2T(X)=-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i$$

### Type Conversion

If not set keyword(unsigned) in C, then must use U follow number to change the default value(signed) such as 15213U

### Conversion mutual

• Byte will not changed, but change the interpreted way.

• Both all will be convert into unsigned if include one unsigned.

### Type extension & Intercept

• Extend: from short to int

• unsigned: plus 0
• signed: plus sign
• Intercept: from unsigned int to unsigned short

• unsigned: mod operation
• signed: almost mod operation

### Calculate & Overflow

Both w bit unsigned number mutual plus, and get a result w+1 bit. Then it will lose the highest bit, just like mod operation:

$$s=UAdd_w(u,v)=u+v ; mod ; 2^w$$

So as signed number, but change the sign symbol.

## Float

$$\sum_{k=-j}^ib_k\times 2^k$$

### IEEE standard

$$(-1)^s ; M ; 2^E$$

s is sign symbol, M always be [1.0, 2.0) decimal, and E is power.

Exp related E(not equal must, as the limit of bit count), frac related M(So as E)

#### Normalized Values

$$v=(-1)^s ; M ; 2^E$$

• E = Exp - Bias
• Exp: exp encode area unsigned digit
• Bias: as k is exp encode count, which means

$$2^{k-1} - 1$$

- single precision: 127 (Exp:1...254,E:-126...127)
- double precision: 1023 (Exp:1...2046, E:-1022...1023)

Note: Exp encode only need unsigned digit to operate.

For M, it must begin with 1: M = 1.xxx…x2, and xxx means frac(frac = 000.00 corresponding minium M = 1.0), when frac=111…1, M will be infinite close to 2.0

For Example: Float F = 15213.0

$$15213_{10}=11101101101101_2=1.1101101101101_2 \times 2^{13}$$

So the frac part is the point behind, and Exp = E + Bias = 12 + 127 = 140 = 10001100(b)

#### Denormalized Values

E = 1 - Bias And M = 0.xxx...x2 But others not changed.

exp = 000…0 & frac = 000…0 : 0
exp = 000…0 & frac != 000…0 : infinite to 0
exp = 111…1 & frac = 000..0 infinite
exp = 111…1 & frac != 000…0 NaN

#### Real sample

Note:

• exp = 0000(Denormalize) 1/8 is the distance

## Data in Memory

Internet: Big Endian

x86 OR ARM: Little Endian

%p: point, %x: Hex, Execute as:

## Basic

### C2M

.c (gcc -0g 0S) -> .s
.s (gcc OR as) -> .o
.o (with lib.a operated by gcc OR ld) execute.

appropriate code:

Processor:

• Storage: Memory & Register
• Calc: Memory & Register
• Transfer: condition call OR condition branch

### Assembly

General purpose register

• %rax(%eax) 用于做累加
• %rcx(%ecx) 用于计数
• %rdx(%edx) 用于保存数据
• %rbx(%ebx) 用于做内存查找的基础地址
• %rsi(%esi) 用于保存源索引值
• %rdi(%edi) 用于保存目标索引值

%rsp(%esp) 和 %rbp(%ebp) 则是作为栈指针和基指针来使用的

movq Sour:[Imm|Reg|Mem], Dest[Reg|Mem] (But No Mem Mem)

D(Rb, Ri, S) -> Mem[Reg[Rb]+S*Reg[Ri]+D]

• D - 常数偏移量

• Rb - 基寄存器

• Ri - 索引寄存器，不能是 %rsp

• S - 系数

• (Rb, Ri) -> Mem[Reg[Rb]+Reg[Ri]]

• D(Rb, Ri) -> Mem[Reg[Rb]+Reg[Ri]+D]

• (Rb, Ri, S) -> Mem[Reg[Rb]+S*Reg[Ri]]

More orders:

• addq Src, Dest -> Dest = Dest + Src

• subq Src, Dest -> Dest = Dest - Src

• imulq Src, Dest -> Dest = Dest * Src

• salq Src, Dest -> Dest = Dest << Src

• sarq Src, Dest -> Dest = Dest >> Src

• shrq Src, Dest -> Dest = Dest >> Src

• xorq Src, Dest -> Dest = Dest ^ Src

• andq Src, Dest -> Dest = Dest & Src

• orq Src, Dest -> Dest = Dest | Src

• incq Dest -> Dest = Dest + 1

• decq Dest -> Dest = Dest - 1

• negq Dest -> Dest = -Dest

• notq Dest -> Dest = ~Dest

## Flow Control

• 临时数据存放在 (%rax, …)
• 运行时栈的地址存储在 (%rsp) 中
• 目前的代码控制点存储在 (%rip, …) 中
• 目前测试的状态放在 CF, ZF, SF, OF 中

### Condition & Jump

• CF: Carry Flag (针对无符号数)
• ZF: Zero Flag
• SF: Sign Flag (针对有符号数)
• OF: Overflow Flag (针对有符号数)

%rdi save x，%rsi save y， %rax save return.

To Goto

Calc all to avoid the reset assembly line operation

Such as:

Not suited:

• Much more calc in the two branches

• val = p ? *p : 0; some interesting happen

• val = x > 0? x *= 7: x *= 3 x will change

#### Do While

To assembly:

Turn on -01 Optimize option, While will be transfer into Do-While, then transfer into Goto, Because Do-While execute so faster, which much more suit CPU calc model.

Switch:

We will use jump table:
%rdi is x, %rsi is y, %rdx is z, %rax is return

## Process call

• Delivery Control: How to begin, and return back the begin
• Delivery Data: Args and return value.
• Memory Manage: How to free and malloc memory.

### Stack Structure

%rsp is stack point

### Call ways

call: 将当前的IP 或者 CS:IP 压入栈中, 跳转到指定位置
ret : 用栈中所保存的数据赋值给IP的， 跳转回来

A Frame will be assigned to every call process by on stack which include three as follows:

• 返回信息
• 本地存储（如果需要）
• 临时空间（如果需要）

Call then alloc, free when return.

x86_64/Linux, fixed in that:

• Argument Build: 需要使用的参数
• 如果不能保存在寄存器中，会把一些本地变量放在这里
• 已保存的寄存器上下文
• 老的栈帧的指针（可选）

While caller include:

• 返回地址（因为 call 指令被压入栈的）
• 调用所需的参数

## Data Storage

Struct:

Align theory:

Win: 如果数据类型需要 K 个字节，那么地址都必须是 K 的倍数

Linux: 2字节数据类型的地址必须为2的倍数，较大的数据类型（int,double,float）的地址必须是4的倍数

So we could design struct like this(big bit number on the front):

## Cache overflow

Sample:

0x18 not 4, before 4006d6

See, the call_echo frame saved 4006f6 order, and when we type 01234567890123456789012

Cache like this(No Segment Fault):

but more will override the 4006f6 get 400034(the back next order)

## Optimize

To remove quote memory

## Base concept

### Memory Hierarchy

TLB 地址翻译 芯片 TLB 0 内存管理单元
L1 缓存 64 字节的块 芯片 L1 缓存 4 硬件
L2 缓存 64 字节的块 芯片 L2 缓存 10 硬件

Web 缓存 网页 远程服务器磁盘 1,000,000,000 Web 代理服务器

Cache miss

• 强制性失效(Cold/compulsory Miss): CPU 第一次访问相应缓存块，缓存中肯定没有对应数据，这是不可避免的
• 冲突失效(Confilict Miss): 在直接相联或组相联的缓存中，不同的缓存块由于索引相同相互替换，引起的失效叫做冲突失效
• 假设这里有 32KB 直接相联的缓存
• 如果有两个 8KB 的数据需要来回访问，但是这两个数组都映射到相同的地址，缓存大小足够存储全部的数据，但是因为相同地址发生了冲突需要来回替换，发生的失效则全都是冲突失效（第一次访问失效依旧是强制性失效），这时缓存并没有存满
• 容量失效(Capacity Miss): 有限的缓存容量导致缓存放不下而被替换，被替换出去的缓存块再被访问，引起的失效叫做容量失效
• 假设这里有 32KB 直接相联的缓存
• 如果有一个 64KB 的数组需要重复访问，数组的大小远远大于缓存大小，没办法全部放入缓存。第一次访问数组发生的失效全都是强制性失效。之后再访问数组，再发生的失效则全都是容量失效，这时缓存已经存满，容量不足以存储全部数据

## Cache Memory

• S 表示集合(set)数量
• E 表示数据行(line)的数量
• B 表示每个缓存块(block)保存的字节数目

C = E * S * B

set index: set; tag: compare to every line; block offset: line offset

If E = 1: Direct Mapped Cache

| 寻址空间是 M=16 字节，也就是 4 位的地址，对应 B=2, S=4, E=1

## Complie

1. 所有头文件的搜寻会从 -I 开始
2. 然后找环境变量 C_INCLUDE_PATH, CPLUS_INCLUDE_PATH, OBJC_INCLUDE_PATH 指定的路径
3. 再找默认目录(/usr/include, /usr/local/include, /usr/lib/gcc-lib/i386-linux/2.95.2/include 等等)

### Object files

• 可重定位目标文件 Relocatable object file (.o file)
• 每个 .o 文件都是由对应的 .c 文件通过编译器和汇编器生成，包含代码和数据，可以与其他可重定位目标文件合并创建一个可执行或共享的目标文件
• 可执行目标文件 Executable object file (a.out file)
• 由链接器生成，可以直接通过加载器加载到内存中充当进程执行的文件，包含代码和数据
• 共享目标文件 Shared object file (.so file)
• 在 windows 中被称为 Dynamic Link Libraries(DLLs)，是类特殊的可重定位目标文件，可以在链接(静态共享库)时加入目标文件或加载时或运行时(动态共享库)被动态的加载到内存并执行

### Object format

• 包含 word size, byte ordering, file type (.o, exec, .so), machine type, etc

• 包含 page size, virtual addresses memory segments(sections), segment sizes

.text section

• 代码部分

.rodata section

• 只读数据部分，例如跳转表

.data section

• 初始化的全局变量

.bss section

• 未初始化的全局变量

.symtab section

• 包含 symbol table, procudure 和 static variable names 以及 section names 和 location

.rel.txt section

• .text section 的重定位信息

.rel.data section

• .data section 的重定位信息

.debug section

• 包含 symbolic debugging (gcc -g) 的信息

• 每个 section 的大小和偏移量

• 全局符号 Global symbols
• 在当前模块中定义，且可以被其他代码引用的符号，例如非静态 C 函数和非静态全局变量
• 外部符号 External symbols
• 同样是全局符号，但是是在其他模块（也就是其他的源代码）中定义的，但是可以在当前模块中引用
• 本地符号 Local symbols
• 在当前模块中定义，只能被当前模块引用的符号，例如静态函数和静态全局变量
• 注意，Local linker symbol 并不是 local program variables

• 局部非静态变量会保存在栈中
• 局部静态变量会保存在 .bss 或 .data 中

Author：ReZero