[Note] 程序员的自我修养——第 4 部分 库与运行库

Posted on In Symbols count in article: 7.1k Reading time ≈ 6 mins.

第 10 章 内存

程序的内存布局

  • 栈：用于维护函数调用的上下文
  • 动态链接库映射区：用于映射装载的动态链接库
  • 堆：用来容纳应用程序动态分配的内存区域，一般比栈大很多
  • 可执行文件映像：存储可执行文件在内存里的映像
  • 保留区：对内存中受到保护而禁止访问的内存区域的总称，例如 NULL

栈与调用惯例

  • 栈保存了一个函数调用所需要的维护信息，称为堆栈帧（Stack Frame）或活动记录（Activate Record），包括：

    • 函数的返回地址和参数
    • 临时变量：包括函数的非静态局部变量以及编译器自动生成的其他临时变量
    • 保存的上下文：包括在函数调用前后需要保持不变的寄存器

  • esp 寄存器始终指向栈的顶部，同时也就指向了当前函数的活动记录的顶部

  • ebp 寄存器指向函数活动记录的一个固定位置，又被称为帧指针（Frame Pointer）

  • 一个 i386 下的函数调用：

    • 把所有或一部分参数压入栈中，如果有其他参数没有入栈，那么使用某些特定的寄存器传递
    • 把当前指令的下一条指令的地址压入栈中，跳转到函数体执行（call 指令）

  • i386 函数体的“标准”开头：

    • push ebp：把 ebp 压入栈中（称为 old ebp），便于在返回时恢复以前的 ebp 值
    • mov ebp, esp： ebp = esp（这时 ebp 指向栈顶，而此时栈顶就是 old ebp）
    • sub esp, x：【可选】在栈上分配 x 字节的临时空间
    • push xxx：【可选】保存名为 xxx 寄存器（可重复多个）

  • 函数返回时的“标准”结尾与“标准”开头正好相反：

    • pop xxx：【可选】恢复保存过的寄存器（可重复多个）
    • mov esp, ebp：恢复 esp 同时回收局部变量空间
    • pop ebp：从栈中恢复保存的 ebp 值
    • ret：从栈中取得返回地址，并跳转到该位置

  • VC 在 Debug 模式下会将栈空间的每一个字节都初始化为 0xCC（0xCCCC 的汉字编码就是“烫”），有助于判断一个变量是否没有初始化

  • 调用惯例（Calling Convention）

    • 函数参数的传递顺序和方式：通过栈还是寄存器传递，参数从左至右还是从右至左压栈
    • 栈的维护方式：参数的弹出由函数调用方还是函数本身完成
    • 名字修饰（Name-mangling）策略：为了链接时对调用惯例进行区分
    调用惯例 出栈方 参数传递 名字修饰
    cdecl 函数调用方 从右至左的顺序压参数入栈 下划线+函数名
    stdcall 函数本身 从右至左的顺序压参数入栈 下划线+函数名+@+参数的字节数
    fastcall 函数本身 头两个 DWORD（4 字节）类型或
    占更少字节的参数被放入寄存器，
    其他剩下的参数按从右到左的顺序压入栈    		 @+函数名+@+参数的字节数
    pascal 函数本身 从左至右的顺序压参数入栈 较为复杂，参见 pascal 文档

  • cdecl 是 C 语言默认的调用惯例

  • naked call 调用惯例用在特殊的场合，其特点是编译器不产生任何保护寄存器的代码

  • C++ 由于支持函数重载以及命名空间和成员函数等，有更加复杂的名字修饰策略；C++ 自己还有一种特殊的调用惯例 thiscall，专用于类成员函数的调用：

    • 对于 VC，this 指针存放于 ecx 寄存器，参数从右到左压栈
    • 对于 gcc，thiscall 和 cdecl 完全一样，只是将 this 看作是函数的第一个参数

  • 函数返回值传递

    • 小等于 4 字节：通过 eax 传递
    • 5~8 字节：eax 存储低 4 字节，edx 存储高 1~4 字节
    • 大于 8 字节：调用方在栈上开辟空间作为传递返回值的临时对象，将其地址作为隐藏参数传递给被调函数，后者将数据拷贝给临时对象并将其地址用 eax 传出，返回后调用方将 eax 指向的临时对象的内容再拷贝到存储返回值的对象里（其中一种实现，不可移植）

    C++ 返回值优化（Return Value Optimization, RVO）：直接将对象构造在传出时使用的临时对象上，减少一次拷贝

堆与内存管理

  • 运行库向操作系统“批发”一块较大的堆空间，然后“零售”给程序用，当全部“售完”或程序有大量的内存需求时，再根据实际需求向操作系统“进货”，通过堆的分配算法来管理堆空间
  • Linux 进程堆管理
    • 提供两种堆空间分配的方式，即两个系统调用：brk() 和 mmap()
    • brk() 通过设置进程数据段的结束地址来扩大或者缩小数据段
    • mmap() 向操作系统申请一段虚拟地址空间（最初的作用是将其映射到某个文件），当该空间不被映射到文件时又称为匿名空间，可以用来作为堆空间，其起始地址和大小都必须是系统页大小的整数倍
    • glibc 的 malloc 函数实现
      • 对于小于 128KB 的请求，在现有的堆空间里按照堆分配算法分配一块空间并返回
      • 对于大于 128KB 的请求，使用 mmap() 分配一块匿名空间，然后在其中为用户分配空间
  • Windows 进程堆管理
    • 提供 VirtualAlloc() 用来向系统申请空间，与 Linux 下的 mmap 非常相似
    • 分配算法的实现位于堆管理器（Heap Manager），提供一套 API 用来创建、分配、释放和销毁堆空间，malloc 则是对这些函数的包装
    • 进程在创建时有一个默认堆（1MB），如果用户申请的空间超过 1MB，堆管理器会通过 VirtualAlloc 向系统申请更多的空间，扩展堆的大小
    • 由于 Windows 的堆空间不连续，当一个堆的空间无法再扩展时，则会创建一个新的堆
  • 堆分配算法
    • 空闲链表（Free List）
      • 把堆中各个空闲的块按照链表的方式连接起来，当用户请求一块空间时，遍历整个链表直到找到合适大小的块并且将它拆分，当用户释放空间时将它合并到空闲链表中
      • 缺点：一旦链表被破坏，整个堆就无法正常工作
    • 位图（Bitmap）
      • 将整个堆划分为大量大小相同的块（block），当用户请求内存时总是分配整数个块的空间，第一个块称为已分配区域的头（Head），其余的称为已分配区域的主体（Body），使用一个整数数组记录块的使用情况，由于每个块只有头/主体/空闲三种状态，因此仅需要两位即可表示一个块
      • 优点
        • 速度快：由于整个堆的空闲信息存储在一个数组内，因此访问该数组时 cache 容易命中
        • 稳定性好：为了避免用户越界读写破坏数据，只须简单地备份一下位图即可，即使部分数据被破坏，也不会导致整个堆无法工作
        • 块不需要额外信息，易于管理
      • 缺点
        • 分配内存的时候容易产生碎片
        • 如果堆很大或一个块很小（可以减少碎片），那么位图将会很大，可能失去 cache 命中率高的优势，而且也会浪费一定的空间
    • 对象池
      • 如果每次分配的空间大小都一样，就以该大小作为单位把整个堆空间划分为大量的小块，每次请求时只需要找到一个小块即可
      • 对象池的管理方法可以采用空闲链表或位图，与它们的区别仅仅在于假定了每次请求的大小固定，因此实现起来很容易
      • 对于被分配对象的大小较为固定的场合更为高效
    • 实际的堆分配算法往往采取多种算法复合而成，比如 glibc
      • 对于小于 64 字节的空间申请，采用类似于对象池的方法
      • 对于大于 512 字节的空间申请，采用最佳适配算法
      • 对于大于 64 字节而小于 512 字节的，根据情况采取上述方法中的最佳折中策略
      • 对于大于 128KB 的申请，使用 mmap 机制直接向操作系统申请空间

第 11 章 运行库

入口函数和程序初始化

  • 程序的入口函数或入口点（Entry Point）是一个程序的初始化和结束部分，往往是运行库的一部分
  • 典型的程序运行步骤
    • 操作系统在创建进程后，把控制权交给程序的入口
    • 入口函数对运行库和程序运行环境进行初始化，包括堆、I/O、线程、全局变量构造等
    • 入口函数在完成初始化后，调用 main 函数，正式开始执行程序主体部分
    • main 函数执行完毕后，返回到入口函数进行清理工作，包括全局变量析构、堆销毁、关闭 I/O 等，然后进行系统调用结束进程
  • 入口函数的实现
    • Glibc: _start -> __libc_start_main -> exit -> _exit
    • MSVC CRT: mainCRTStartup -> _heap_init(), I/O 初始化
  • C 语言通过 FLLE 结构的指针来操作文件，对应操作系统层面的句柄，在 Linux 里叫做描述符（File Descriptor），在 Windows 里叫做句柄（Handle），用于防止用户随意读写操作系统内核的文件对象
  • 在 Linux 中，值为 0、1、2的 fd 分别代表标准输入、标准输出和标准错误输出，在程序中打开文件得到的 fd 从 3 开始增长。内核中每一个进程都有一个私有的“打开文件表”（指针数组），每一个元素都指向一个内核的打开文件对象，而 fd 就是表的下标。由于该表处于内核，用户无法访问到，因此用户即使拥有 fd，也无法得到打开文件对象的地址，只能够通过系统提供的函数来操作
  • Windows 中的句柄与 Linux 中的 fd 大同小异，不过是打开文件表的下标经过某种线性变换之后的结果
  • I/O 初始化函数在用户空间中建立 stdin、stdout、stderr 及其对应的 FILE 结构，使得程序进入 main 之后可以直接使用 printf、scanf 等函数
  • MSVC 的 I/O 初始化工作
    • 建立打开文件表
    • 如果能够继承自父进程，那么从父进程获取继承的句柄
    • 初始化标准输入输出

C/C++ 运行库

  • C 语言运行库（CRT）大致包含如下功能：
    • 启动与退出：包括入口函数及入口函数所依赖的其他函数等
    • 标准函数：由 C 语言标准规定的 C 语言标准库所拥有的函数实现
    • I/O：I/O 功能的封装和实现
    • 堆：堆的封装和实现
    • 语言实现：语言中一些特殊功能的实现
    • 调试：实现调试功能的代码
  • 运行库是平台相关的，是 C 语言程序和不同操作系统平台之间的抽象层，它将不同的操作系统 API 抽象成相同的库函数
  • 有时需要绕过 C 语言运行库直接调用操作系统 API 或使用其他的库（如用户的权限控制、操作系统线程创建等都不属于标准 C 语言运行库），Linux 和 Windows 平台下的两个主要 C 语言运行库分别为 glibc（GNU C Library）和 MSVCRT（Microsoft Visual C Run-time）
  • glibc 的发布版本主要由两部分组成：一部分是头文件，往往位于/usr/include；另外一部分则是库的二进制文件，主要是 C 语言标准库，有静态和动态两个版本，前者位于/usr/lib/libc.a，后者位于 /lib/libc.so.6
  • MSVC CRT 静态版位于 MSVC 安装目录下的 lib/；动态版一般有两个文件，一个用于链接的 .lib 文件，一个用于运行时的 .dll 动态链接库

运行库与多线程

  • 线程私有存储空间

    • 栈（尽管并非完全无法被其他线程访问）
    • 线程局部存储（Thread Local Storage, TLS），通常尺寸很有限
    • 寄存器（包括 PC 寄存器）

  • 从 C 程序员的角度看数据在线程之间是否私有

    线程私有 线程之间共享（进程所有）
    局部变量
    函数的参数
    TLS 数据    		 全局变量
    堆上的数据
    函数里的静态变量
    程序代码，任何线程都有权利读取并执行任何代码
    打开文件，A 线程打开的文件可以由 B 线程读写

  • 线程相关内容不属于 C/C++ 标准库运行库，而属于系统相关库：

    • Windows：MSVC CRT 提供 _beginthread()、_endthread() 等函数
    • Linux：glibc 提供可选的线程库 pthread（POSIX Thread），包括 pthread_create()、 pthread_exit() 等函数

  • 多线程版本的运行库

    • 使用 TLS：errno 成为各个线程的私有成员，定义为宏 #define errno (*__errno_location())
    • 加锁：线程不安全的函数内部自动加锁（如 malloc、printf），并解决多线程异常处理冲突的问题
    • 改进函数调用方式：修改线程不安全函数的参数列表成为线程安全的版本，如 strtok() -> strtok_r()

  • 线程局部存储

    • 每个线程都会拥有变量的一个副本，任何线程对该变量的修改都不会影响其他线程中该变量的副本
    • 定义一个全局变量为 TLS 类型只需在定义前加上相应的关键字，对于 GCC 是 __thread，对于 MSVC 是 __declspec(thread)
    • Windows TLS 的实现
      • 编译器将 TLS 变量放到 PE 文件的 .tls 段中，当系统启动一个新的线程时，从进程的堆中分配一块足够大小的空间，然后把 .tls 段中的内容复制过去，于是每个线程都有自己独立的一个 .tls 副本
      • TLS 表位于 PE 文件的 .rdata 段中，保存了所有 TLS 变量的构造函数和析构函数的地址，Windows 系统根据 TLS 表中的内容，在每次线程启动或退出时对 TLS 变量进行构造和析构
      • 对于每个 Windows 线程，系统都会建立一个线程环境块（TEB, Thread Environment Block），保存线程的堆栈地址、线程 ID 等相关信息，其中一个域是 TLS 数组，线程通过该数组中的地址来访问 TLS 变量

C++ 全局构造与析构

  • Glibc 全局构造与析构
    • _start -> __libc_start_main -> __libc_csu_init -> _init -> __do_global_ctors_aux
    • 对于每个编译单元(.cpp)，GCC 会遍历其中所有的全局对象，生成一个特殊函数对本编译单元里的所有全局对象进行初始化，并在目标文件(.o)的 .ctors 段里放置指向该函数的指针
    • 链接器将每个目标文件的 .ctors 段合并为一个函数指针数组，每一个元素都指向一个目标文件的全局构造函数
    • 编译器对每个编译单元的全局对象，都会生成一个特殊函数来调用析构函数，其调用顺序与调用构造函数的顺序刚好相反
  • MSVC CRT 的全局构造和析构
    • mainCRTStartup -> _initterm
    • 实现机制与 Glibc 基本相似，略

MSVC 的 fread 实现

  • 最终调用 Windows 系统 API 的 ReadFile() 函数
  • 缓冲（Buffer）
    • 频繁进行系统调用严重影响程序和系统的性能
    • 将连续的多次写入放在一个数组里，等到数组被填满之后再一次性完成系统调用写入，系统崩溃或进程意外退出有可能导致数据丢失
    • 读取数据时，如果缓冲中有数据就直接从缓冲中取；如果缓冲是空的，CRT 就通过操作系统一次性读取文件一块较大的内容填充缓冲
    • flush 将缓冲内的数据全部写入实际的文件，并将缓冲清空，保证文件处于最新的状态
    • 缓冲模式
      • 无缓冲：不适用任何缓冲
      • 行缓冲（Line Buffer）：仅对文本模式打开的文件有效，每收到一个换行符就将缓冲 flush 掉
      • 全缓冲（Full Buffer）：除用户手动调用 flush 外，仅当缓冲满时才进行 flush
  • fread -> fread_s -> _fread_nolock_s -> _read -> ReadFile

第 12 章 系统调用与 API

系统调用介绍

  • 系统调用（System Call）是应用程序与操作系统内核之间的接口
  • 为了让应用程序有能力访问系统资源，或借助操作系统做一些必须由操作系统支持的行为，每个操作系统都会提供一套接口以供应用程序使用，这些接口往往通过中断来实现
  • 在 Linux x86 下，系统调用由 0x80 中断完成，各个通用寄存器用于传递参数，EAX 寄存器用于表示系统调用的接口号；当系统调用返回时，EAX 又作为调用结果的返回值
  • 系统调用的弊端
    • 使用不便，接口过于原始，需要了解很多与操作系统相关的细节
    • 各个操作系统之间系统调用不兼容
  • 运行库作为系统调用与程序之间的抽象层，将不同操作系统的系统调用包装为统一固定的接口，使用简便，形式统一（标准库）

系统调用原理

  • 特权级别
    • 用户模式/用户态（User Mode）
    • 内核模式/内核态（Kernel Mode）
  • 操作系统可以让不同的代码运行在不同的模式上，以限制它们的权力，提高稳定性和安全性
  • 系统调用运行在内核态；普通应用程序运行在用户态，诸多操作将受到限制，包括访问硬件设备、开关中断、改变特权模式等
  • 操作系统一般通过中断 （Interrupt）从用户态切换到内核态
  • 不同的中断具有不同的中断号（从0开始），一个中断处理程序（Interrupt Service Routine, ISR）对应一个中断号
  • 在内核中，中断向量表（Interrupt Vector Table）的第 n 项包含了指向第 n 号中断的中断处理程序的指针
  • 当中断到来时，CPU 会暂停当前执行的代码，根据中断号在中断向量表中找到对应的中断处理程序并调用它，完成之后继续执行之前的代码
  • 中断的两种类型
    • 硬件中断：自于硬件的异常或其他事件的发生，如电源掉电、键盘被按下等
    • 软件中断：通常是一条指令，带有一个参数记录中断号，使用这条指令用户可以手动触发某个中断并执行其中断处理程序，例如 i386 下 Windows 系统调用由 int 0x2e 触发，Linux 则由 int 0x80 触发
  • 系统调用都有一个系统调用号，通常是其在系统调用表中的位置，在执行 int 指令前被放置在某个固定的寄存器里，中断服务程序会取得这个系统调用号，进而调用对应的函数
  • 基于 int 的 Linux 的经典系统调用实现
    1. 触发中断
    2. 将程序的当前栈由用户栈切换为内核栈
    3. 中断处理程序调用系统调用函数
  • Linux 的新型系统调用机制：由于基于 int 指令的系统调用在奔腾 4 代处理器上性能不佳，Linux 在 2.5 版本起开始支持一种新型的系统调用机制，这种新机制使用 Intel 在奔腾 2 代处理器就开始支持的一组专门针对系统调用的指令——sysenter 和 sysexit

Windows API

  • Windows API 是指 Windows 操作系统提供给应用程序开发者的最底层的、最直接与 Windows 打交道的接口
  • 微软并没有将 Windows 的系统调用公开，程序员只能调用 API 层的函数，而不是如 Linux 一般直接使用系统调用
  • Windows API 作为 CRT 和系统调用之间的中间层，防止内核系统调用层发生变化导致用户程序也必须随之变化
  • Windows 子系统（Subsystem）是架设在 API 和应用程序之间的另一个中间层，用来为各种不同平台的应用程序创建与它们兼容的运行环境

第 13 章 运行库实现

略