1013 异常控制流

Exception Control Flow ECF

1.1 异常处理

启动时生成异常表

运行时检测到异常,确定异常号,查找异常表,进入处理程序

执行完后,执行一条”从中断返回”指令,将控制返回给被中断的程序[如果是一个用户程序被中断]

1.2异常类别

1. 中断

2. 陷阱和系统调用

   陷阱: 有意的异常,用来在用户程序和内核之间提供一个像过程一样的接口–系统调用

3. 故障

   如 除法错误,却也,一般保护故障[程序引用了一个未定义的虚拟内存区域,Linux一般会报告为一个 段故障 Segmentation fault]

4. 终止

   不可恢复的致命错误–通常硬件错误

2 进程

定义

一个执行中程序的实例

维护一个 该程序是系统中当前运行的唯一程序的假象

拥有

• 一个独立的逻辑控制流
  • 提供独占处理器的假象
• 一个私有的地址空间
  • 提供独占内存系统的假象

进程空间

给出通用结构

以x86-64 Linux为例

上下文切换

用于实现多任务

上下文: 重新启动一个被抢占的进程所需的状态

系统调用错误处理

Unix系统级函数遇到错误时,通常会返回-1,并设置全局整数变量errno来表示什么出错了.

进程控制

重点是创建子进程

父进程调用fork函数创建一个子进程

父子进程区别

相同

• 虚拟地址空间
  • 代码
  • 数据段
  • 堆
  • 共享库
  • 用户栈
• 打开描述符
  • 意味着父进程调用fork时,子进程可以读写父进程中打开的任何文件

区别

• Pid
  • 进程id不同
• 并发执行
  • 父进程和子进程是并发运行的独立进程
• 虚拟地址空间
  • 子进程得到的副本和父进程相同,包括打开的文件描述符,但是是一份独立的副本,也就是说,之后的调用,子进程和父进程独立.

fork

• 调用一次返回两次
  • 一次是在调用进程(父进程中)
    • 返回子进程PID(非零)
  • 一次在创建的进程中(子进程中)
    • 返回0
• 可以用来辨认子进程还是父进程

回收子进程

步骤: 终止->分配给init进程作为养父->父进程回收[若父进程没来得及回收,则由init进程回收]

信号

较高层

• 是一个小消息,通知进程系统中发生了一个某种类型的事件.
• 用于通知用户进程发生了一些低层的硬件异常

符号和符号表

static属性声明的全局变量/函数都是模块私有的,任意不被static修饰的全局变量/函数都是公共的,可以被其他模块访问

因此,在每个可重定位目标模块中存在三类符号

• 自己定义的全局符号
• 由其他模块定义并由该模块引用的全局符号
• 自己定义的局部符号–static修饰的函数/全局变量

符号解析

编译器解析符号引用的办法是将每个与它输入的可重定位目标文件中的一个确定的符号定义关联起来

如何解析多重定义的全局符号

区别强弱定义: (我的理解) 强定义是全局定义后有初始值,弱定义没有

1. 不允许有多个同名的强符号
2. 如果有一个强符号和多个弱符号同名,则选择强符号
3. 如果多个弱符号同名,则随机选择一个

6.1 存储技术

• 随机访问存储器 RAM

  • 静态 SRAM

    位存储模式:双稳态存储器单元

    只要有电,就能永远保持值

  • 动态 DRAM

    位存储模式: 电容充电

  • 比较

  • 	每位晶体管数	相对访问时间	持续?	敏感	相对花费	应用
    SRAM	6	1	是	否	1000	高速缓冲存储器
    DRAM	1	10	否	是	1	主存/帧缓冲区

  • 非易失性存储器 ROM

    关电后仍然能保持信息

  • 访问主存

    通过数据总线和主存信息交互

• 磁盘存储

  • 从磁盘读数据的效率是从DRAM读数据的几乎10万倍慢,不过ssd会快的多,不过只是相对于传统磁盘而言

  • 固态磁盘SSD

    • 读SSD比写要快

      • 因为随机写要擦除块,这个动作是毫秒级的
      • 如果试图写一个有数据的块,会先将这块的数据复制到另一个没数据的地方

    • SSD多次重复写后会损坏

6.2局部性

局部性原理

计算机程序倾向于引用邻近与其他最近引用过的数据项的数据项

简单原则

• 重复引用相同变量的程序有良好的时间局部性
• 对于步长为k的引用模式的程序,步长越小,空间局部性越好.
• 对于取指令来说,循环有好的时间和空间局部性.循环体越小,迭代次数越多,局部性越好

6.3 存储器层次结构

• L0 寄存器 –保存着从高速缓存中取出的字
• L1 高速缓存 SRAM –缓存着从L2取出的缓存行 – 速度接近寄存器
• L2 高速缓存 SRAM –缓存着从L3取出的缓存行 – 速度比L1慢
• L3 高速缓存 SRAM –缓存着从主存高速缓存取出的缓存行 –速度比L2慢
• L4 主存 DRAM – 保存着从本地磁盘取出的代码块
• L5 本地耳机存储 本地磁盘 –保存着从远程网络服务器磁盘上读取的文件
• L6 远程二级存储 [分布式文件系统,Web服务器]

6.4 高速缓存存储器

6.4.1 通用的高速缓存存储器组织结构

存储器地址位数: m

存储器地址数: M=2^m

高速缓存组数 S= 2^s

高速缓存组内缓存行: E

缓存行内数据块 B=2^b

高速缓存大小: C=S*E*B

6.4.2 直接映射高速缓存

特征: 每个组只有一行,因此字选择时简单,但容易发生抖动

流程: 假设执行一条读内存字w的指令

组选择:

• 从w中抽取s个组标记位,s由高速缓存组数决定
• 之后查看高速缓存中是否存在该组,如果存在就得到一个缓存命中,不存在就是缓存不命中

字选择:

• 高速缓存中的偏移位标识了字节在块中的偏移

行替换:

• 如果缓存不命中,就需要从层次结构的下一层中取出被请求的块,然后将心的块存储在组索引所示的块中

示例:

• 书P429

冲突不命中:

• 由直接映射的设计可以看出,如果程序访问大小为2的幂的数组,很可能会发生冲突不命中.
• 相同组映射的内存块会不断的来回覆盖–抖动

6.4.3 组相联高速缓存

每个组都有 1<E<C/B 个高速缓存行的 的高速缓存通常称为E路组相联高速缓存

如果E=C/B 称为全相联高速缓存

行匹配

• 检查多个行的标记和有效位,判断是否在缓存中

行替换

• 如果组中有空行,则换到空行上去
• 如果没有,则根据替换策略替换–比如LRU

6.4.4 写回

怎么更新层次结构中,低一层的副本

1. 直写 – write throuth
   • 立即将w的高速缓存块写回到紧接着的第一层
   • 每次写都会引起总线流量
   • 能够使用独立于高速缓存的写缓冲区用来更新内存
   • 读不命中开销小
2. 写回[ 延迟更新] write back
   • 只有当替换算法要驱逐这个块时,将这个块写到低一层
   • 显著减少总线流量
   • 增加复杂性– 需要维护一个新的位[修改位]
   • 允许更多到内存的贷款用于执行DMA的I/O.

如何处理写不命中

就是说,要写的块拿不到

1. 写分配 write-allocate
   • 加载相应的低一层的块到高速缓存中,然后更新这个高速缓存块
   • 写回高速缓存通常是写分配的
2. 非写分配 not-write-allocate
   • 避开高速缓存,直接把这个字写到低一层中
   • 直写高速缓存通常是非写分配的

6.4.7 性能影响

1. 不命中率
   • 执行期间,内存引用不命中的比率 不命中数量/引用数量
2. 命中时间
   • 从高速缓存传送一个字到CPU所需的时间
3. 不命中处罚
   • 不命中所需的额外时间

下列因素提高的影响

• 高速缓存:命中率提高,命中时间提高
• 块大小:命中率提高,不命中处罚提高,损害时间局部性比空间局部性更好的程序的命中率
• 相联度:降低抖动可能,成本提高,增加不命中处罚

越往层次下面走,传送时间增加,减少传送的数量就更为重要.

6.5 编写高速缓存友好的代码

两个原则

• 让最常见的情况运行的最快
• 尽量减少,每个循环内部的缓存不命中数量.

5.1 编译器优化能力的局限性

• 编译器只做安全的优化–优化后和未优化的版本有一样的行为

限制

• 内存别名使用

编译器并不知道指针指向哪里,因此它必须假设指针可能指向同一个位置.

• 函数调用

大多数编译器不会去判断一个函数是否有副作用,因此它们倾向于将函数的调用保持不变

内联

包含函数调用的代码可以用内联函数替换过程进行优化,就是将函数内部的执行步骤内联到一起

在gcc中,只尝试单文件的内联,不会尝试多文件的内联(比如一组函数在其他文件内的函数中被调用)

5.2 表示程序性能

标准:CPE

每元素的周期数

5.3 消除低效循环

例如 :可以拿出来的拿出来

5.4减少过程调用

例: 如果一个循环中不断从结构体中的列表中获取值,而同时,结构体会不断对列表中值的存在进行判断

则可在保证安全的情况下,直接获取结构体中的列表进行访问.

5.5消除不必要的内存引用

例如

1 2 3 4 5 6 7 8 9

{// for loop *dest=*dest+1; } // 将dest这个不断访问内存的东西挪到寄存器里 val tmp=*dest; { tmp=tmp+1; } *dest=tmp

5.6 了解现代处理器

• 延迟界限

  当一系列操作必须按照严格顺序执行时会碰到

  因为下一条指令开始前,这一条必须结束

  代码中的数据相关限制了处理器利用指令级并行的能力时会碰到延迟界限

• 吞吐量界限

  是处理器功能单元的原始计算能力,是程序性能的终极限制

5.7 循环展开

• 比如n长的循环,2个一组展开之后,循环长度/2,这种称之为1*2循环展开

对一个n长的循环,进行k级别的展开,就需要将上限设置为n-k+1,这样最大循环索引会小于n

5.8 提高并行性

5.8.1 多个累积变量

例: 见书P370

上面的例子称之为2*2循环展开

5.8.2重新结合变换

该例子为2*1a循环展开

例

// slow version

acc= (acc * data[i]) * data[i+1]

//fast version

acc = acc * ( data[i] * data[i+1])

slow版里,每次计算都需要等之前的计算结果出来之后才能继续进行

fast版里,data[i]*& data[i+1]不受约束,因此可以被CPU并行优化,故效率高

5.9 一些限制因素

书P378

5.9.1 寄存器溢出

当用到的临时变量过多,使得寄存器不够用的时候,会调用栈来存储这些变量,这会使得程序效率变低.

5.9.2 分支预测和预测错误处罚

预测错误会导致较大的错误处罚,那么有什么办法来保证这个处罚对程序效率影响较小呢

1. 不过分关心可预测的分支

   例如,大部分结束循环的语句判断都是不结束,预测时一般都按照不结束来判断. 这时候只在最后一次会导致预测错误处罚.

2. 书写适合使用条件传送实现的代码

   最好使用条件数据传送而非条件控制转移.

   数据传送示例:

   max=a>b?a:b;

   这种形式适合流水线并行操作.

5.10 应用 性能提高技术

1. 高级设计: 为遇到的问题选择适当的算法和数据结构
2. 基本编码原则. 避免限制优化的因素
   1. 消除连续的函数调用
      • 在可能时,将计算一道循环外
   2. 消除不必要的内存引用
      • 引入临时变量来保存中间结果,只有在最后的值计算出来时,才将结果存放到数组和全局变量中.
3. 低级优化. 结构化代码以利用硬件性能
   1. 展开循环,降低开销
   2. 使用多个累计变量和重新结合技术,找到方法提高指令级并行
   3. 用功能性的风格重写条件操作,使编译采用条件数据传送.

C 语言 基础属性

数组的指针运算– 数组存储的是它的指针,其指针++ 会跳过存储数据量的位置(如 int a[10],a++ ,arr[a]会+4)

struct的对齐

由于会根据struct中的最大的基本结构类型[int,double,float 之类的,和列表没关系]来进行对齐[例如,struct中存在double就会按照8byte对齐,如果最大只有int,就按照4byte对齐],因此,最好将结构合理组织,

如

1 2 3 4 5 6 7 8 9 10

struct S4{//char :1 byte, int : 4byte char c;// 产生3个用于对齐的内存浪费 int i; char d;// 产生3个用于对齐的浪费 }// waste 3+3 byte struct S5{ int i; char c; char d;//c,d一并存储,产生2个用于对齐的浪费 }

Memory Layout

IMG:

Buffer OverFlow

• 注: 内存是按照0x7FFFFFFFFFFF 也就是2^47来作为地址的,所以各位置之间可能会有较大的差距[因为暂时,硬件条件并不会使得整块可供分配的内存id映射被用尽]

stack:

• 8MB
• 向下拓展[地址高标号低]

Data:

• 用于存放程序开始时分配的数据
  • 存放全局变量

Heap:

• 存放通过malloc/相关函数申请的变量,会动态变化
• 大的数据块会出现在靠近stack的位置,并向下增长,小的数据块会出现在靠近Data的位置,并向上增长

SharedLibraries:

• 存放库函数代码[一般在磁盘上]
• 在运行时动态加载到内存中

Unions

BufferOverFlow

代码注入攻击详解

举例: gets 会不断读取字符串,直至收到一个’\0’

1 2 3 4 5 6

void echo() { char buf[4];/* Way too small*/ gets(buf); puts(buf); }

此时,若输入大于4个字符,echo还是可以接收

查看汇编代码可以看到,调用echo的时候给stackFrame分配了24byte的空间

如果输入大于23个字符,就会报出 segment fault

• 这时候该函数的返回位置可能被溢出的字符串覆盖,使得函数不会到main这个接口,而是进入一个新的地区
• 这就是代码注入攻击

小于23就没事,

How to Avoid

1. 使用安全的替代
   1. fgets-> gets
   2. strncopy-> strcopy
   3. scanf(“%ns”)-> scanf(“%s”)
2. Randomized stack offsets– 地址空间布局随机化
   1. 使得每次程序运行的时候,它分配到的缓冲区长度都是变化的
3. None executable code segments
   1. 在可读/可写等内存标识之外增加一个 “execute” 权限
4. stack canary 栈保护机制
   1. 
   2. 程序会检测到栈溢出的问题并返回

A Skill to Avoid Randomized stack offset/None executable code segments

• 但是躲不开canary

Gadget

A Example:

p后面的值恰好和mov rax rdi 相等,结尾又是一个c3,因此这一段额外的代码会在p赋值之后执行,并返回.

这样就实现了在代码中插入一定量的自己的小代码,返回后就可以通过获取rsp栈中的代码,来将之前的代码块拼接一起执行.

GDB Trick

disass [FUNC_NAME]

解析对应函数的汇编代码

浮点数

基础知识

浮点通过移动二进制小数点来表示尽可能大的取值范围

数字公式

$$
(-1)^S M 2^E
$$

符号位{S} 表示正负

小数{M} 一般是一个1~2之间的小数值

指数位{E} 指的是乘2的E次方

IEEE浮点数标准

single 单精度

1位符号位，8位指数位，23位小数位

Double 双精度

1位符号位，11位指数位，52位小数位

小数位的特殊表示

由于小数位永远是1.010101这样的模式

因此前面的1不放入存储，只记录后面的01010101这种

同时，在计算时，会刻意维持小数位为1.010111这样的模式，就是说维持小数位在1~2之间

零表示法

$$
(-1)^S M 2^E
$$

此时E为1-Bias，之前为0-Bias

由于之前无法表示0，将M设置为0.110101010这种模式，此时可以表示0

当E全0，小数位全0的时候

表示0

这会导致正负0的出现

当E为0，小数位不为0的时候，可以表示一些很接近0的东西

如果E为111111….1 ，frac 不为0，

则代表一个极大值，不代表数字