跳转至

operating system

Micro2023: Utopia

导言

This blog delves into Onur Mutlu's Address Translation work on Processing-in-Memory (PIM), titled "Utopia1: Fast and Efficient Address Translation via Hybrid Restrictive & Flexible Virtual-to-Physical Address Mappings."

C program compile&run process

编译总流程

编译是指编译器读取源程序（字符流），对之进行词法和语法的分析，将高级语言指令转换为功能等效的汇编代码。

  1. 预处理阶段：
  2. 把#include语句以及一些宏插入程序文本中，得到main.i和sum.i文件。
  3. 编译阶段:
  4. 将文本文件main.i和sum.i编译成文本文件main.s和sum.c的汇编语言程序。 低级的汇编语言为不同的高级语言提供了通用输出语言。
  5. 汇编阶段:
  6. 将main.s和sum.s翻译成机器语言的二进制指令，并打包成一种叫做可重定位目标程序的格式，并将结果保存在main.o和sum.o两个文件中。这种文件格式就比较接近elf格式了。
  7. 链接阶段:
  8. 合并main.o和sum.o，得到可执行目标文件，就是elf格式文件。

目标文件

目标文件有三种形式：

  • 可重定位目标文件。包含二进制代码和数据，其形式可以在编译时与其他可重定位目标文件合并起来，创建一个可执行目标文件。
  • 可执行目标文件。包含二进制代码和数据，其形式可以被直接复制到内存并执行。
  • 共享目标文件。一种特殊类型的可重定位目标文件，可以在加载或者运行时被动态地加载进内存并链接。

1 预处理

  • 预处理器： 将.c 文件转化成 .i文件.

生成预处理文件

  • 使用的gcc命令是：gcc –E filename.cpp -o filename.i
  • -E Preprocess only; do not compile, assemble or link.
  • 通过-C能保留头文件里的注释，如gcc -E -C circle.c -o circle.c
  • 另一种方式 gcc -save-temps -c -o main.o main.c
  • 也可以调用cpp filename.cpp -o filename.i命令

理解预处理文件

  • 输出文件会出现许多名叫 linemarkers类似# linenum filename flags的注释，这些注释是为了让编译器能够定位到源文件的行号，以便于编译器能够在编译错误时给出正确的行号。
  • They mean that the following line originated in file filename at line linenum.
  • flags meaning
    • ‘1’ This indicates the start of a new file.
    • ‘2’ This indicates returning to a file (after having included another file)
    • ‘3’ This indicates that the following text comes from a system header file, so certain warnings should be suppressed
    • ‘4’ This indicates that the following text should be treated as being wrapped in an implicit extern "C" block.
    • ‘4’表示接下来的文本应被视为被包含在隐式的“extern "C"”块中。在C++中，函数名和变量名可以有不同的命名空间，但是使用“extern "C"”修饰时可以取消这种区别，使得函数名和变量名可以在C++和C代码之间共享。因此，在C++中使用“extern "C"”来声明C函数或变量时，需要使用‘4’来指示编译器此处的文本应该被视为C代码，而不是C++代码。[来自chatGPT的解释]

预处理内容(过程)

除开注释被替换成空格，包括代码里的预处理命令：

  1. #error "text" 的作用是在编译时生成一个错误消息，它会导致编译过程中断。 同理有#warning
  2. 宏定义指令，如 #define a b 对于这种伪指令，预编译所要做的是将程序中的所有a用b替换，但作为字符串常量的 a则不被替换。还有 #undef，则将取消对某个宏的定义，使以后该串的出现不再被替换。
  3. 条件编译指令，如#ifdef SNIPER，#if defined SNIPER && SNIPER == 0,#ifndef，#else，#elif，#endif等。 这些伪指令的引入使得程序员可以通过定义不同的宏来决定编译程序对哪些代码进行处理。预编译程序将根据有关的文件，将那些不必要的代码过滤掉
  4. gcc编译使用-DSNIPER=5
  5. 头文件包含指令，如#include "FileName"或者#include 等。 该指令将头文件中的定义统统都加入到它所产生的输出文件中，以供编译程序对之进行处理。
  6. 特殊符号，预编译程序可以识别一些特殊的符号。 例如在源程序中出现的LINE标识将被解释为当前行号（十进制数），FILE则被解释为当前被编译的C源程序的名称。 预编译程序对于在源程序中出现的这些串将用合适的值进行替换。

头文件搜索优先级

#include "" vs #include <> 区别在于前者会在文件的当前目录寻找，但是后者只会在编译器编译的official路径寻找

通常的搜索顺序是：

  • 包含指定源文件的目录（对于在 #include 命令中以引号包括的文件名）。
  • 采用-iquote选项指定的目录，依照出现在命令行中的顺序进行搜索。只对 #include 命令中采用引号的头文件名进行搜索。
  • 所有header file的搜寻会从-I开始, 依照出现在命令行中的顺序进行搜索。（可以使用-I/path/file只添加一个头文件，尤其是在编译的兼容性修改时）
  • 采用环境变量 CPATH 指定的目录。
  • 采用-isystem选项指定的目录，依照出现在命令行中的顺序进行搜索。
  • 然后找环境变量 C_INCLUDE_PATH,CPLUS_INCLUDE_PATH,OBJC_INCLUDE_PATH指定的路径

  • 再找系统默认目录(/usr/include、/usr/local/include、/usr/lib/gcc-lib/i386-linux/2.95.2/include......)

  • 通过如下命令可以查看头文件搜索目录 gcc -xc -E -v - < /dev/null 或者 g++ -xc++ -E -v - < /dev/null*. 如果想改，需要重新编译gcc

  • 或者在编译出错时，g++ -H -v查看是不是项目下的同名头文件优先级高于sys-head-file

2 编译优化Compile

  • 将经过预处理之后的程序转换成特定汇编代码(assembly code)的过程
  • 一般将.c/.h或者.i文件转换成.s文件，

生成汇编代码

  • 使用的gcc命令是：gcc –S filename.cpp -o filename.s，对应于
  • -S Compile only; do not assemble or link.
  • 理论上gcc –S filename.i -o filename.s 也是可行的。但是我遇到头文件冲突的问题error: declaration for parameter ‘__u_char’ but no such parameter
  • 编译命令 cc –S filename.cpp -o filename.s
  • 或者cc1命令

编译内容（过程）

  • 词法分析、语法分析、语意分析、中间代码生成，在语法检查、类型检查之后，将其翻译成等价的中间代码表示或汇编代码
  • 优化（-O3）
  • 常规优化：删除死代码、减少寄存器传输、常量折叠、提取中间量
  • 高阶优化：循环展开、指针优化、函数内联，自动SIMD向量化
  • 关于内联函数
  • 内联函数是在函数定义前加上关键字inline的函数。它用于请求编译器将函数的代码插入到每个调用该函数的地方，而不是通过函数调用来执行。这样可以减少函数调用的开销，提高程序的执行效率。
  • 内联函数一般适用于函数体较小、频繁调用的函数，但最终是编译器决定是否将函数内联，编译器可以忽略对内联函数的请求。

如果想把 C 语言变量的名称作为汇编语言语句中的注释，可以加上 -fverbose-asm 选项：

gcc -S -O3 -fverbose-asm ../src/pivot.c -o pivot_O1.s
objdump -Sd ../build/bin/pivot > pivot1.s

理解汇编文件

请阅读 GNU assembly file一文

3 汇编assemble

汇编器：将.s 文件转化成 .o文件，

生成可重定位目标程序

  • 使用的gcc 命令是：gcc –c，
  • -c Compile and assemble, but do not link.
  • 汇编命令是 as；

汇编过程

  • 汇编实际上指汇编器(as)把汇编语言代码翻译成目标机器指令(二进制)的过程。
  • 目标文件中所存放的也就是与源程序等效的目标的机器语言代码。

  • 目标文件由段组成。通常一个目标文件中至少有两个段：

  • 代码段：该段中所包含的主要是程序的指令。该段一般是可读和可执行的，但一般却不可写。

  • 数据段：主要存放程序中要用到的各种全局变量或静态的数据。一般数据段都是可读，可写，可执行的。

查看理解

  • 查看汇编代码 objdump -Sd ../build/bin/pivot > pivot1.s
  • -S 以汇编代码的形式显示C++原程序代码，如果有debug信息，会显示源代码。
  • nm file.o 查看目标文件中的符号表

注意，这时候的目标文件里的使用的函数可能没定义，需要链接其他目标文件.a .so .o .dll(Dynamic Link Library的缩写，Windows动态链接库)

nm 命令

List symbol names in object files.

no symbols

  • 编译时可能会为了空间优化掉许多符号表，例如 -O3 Release模式
  • 切换成debug模式

常用选项 -CD

  • -C 选项告诉 nm 将 C++ 符号的 mangled 名称转换为原始的、易于理解的名称。
  • -g：仅显示外部符号。
  • -D / --dynamic：显示动态符号，这在查看共享库（如 .so 文件）时非常有用。
  • -l：显示本地（static）符号。
  • --defined-only：仅显示已定义的符号。

输出

  1. 符号值。默认显示十六进制，也可以指定；
  2. 符号类型。小写表示是本地符号，大写表示全局符号(external);
  3. 符号名称， 如下
符号类型 描述
A 符号值是绝对的。在进一步的连接中，不会被改变。
B 符号位于未初始化数据段(known as BSS).
C 共用(common)符号. 共用符号是未初始化的数据。在连接时，多个共用符号可能采用一个同样的名字，如果这个符号在某个地方被定义，共用符号被认为是未定义的引用.
D 已初始化数据段的符号
G 已初始化数据段中的小目标(small objective)符号. 一些目标文件格式允许更有效的访问小目标数据，比如一个全局的int变量相对于一个大的全局数组。
I 其他符号的直接应用，这是GNU扩展的，很少用了. N 调试符号.
R 只读数据段符号. S 未初始化数据段中的小目标(small object)符号.
T 代码段的符号.
U 未定义符号.
V 弱对象(weak object)符号. 当一个已定义的弱符号被连接到一个普通定义符号，普通定义符号可以正常使用，当一个未定义的弱对象被连接到一个未定义的符号，弱符号的值为0.
W 一个没有被指定一个弱对象符号的弱符号(weak symbol)。 - a.out目标文件中的刺符号(stabs symbol). 这种情况下，打印的下一个值是其他字段，描述字段，和类型。刺符号用于保留调试信息.
? 未知符号类型，或者目标文件特有的符号类型.

ldconfig 查找动态库位置

ldconfig 命令用于配置动态链接器的运行时绑定。你可以使用它来查询系统上已知的库文件的位置。

查询 libdw.so 的位置：

ldconfig -p | grep libdw

ldd 检查是否链接成功

ldd会显示动态库的链接关系，中间的nm为U没关系，只需要最终.so对应符号是T即可。

4 链接过程

通过使用ld命令，将编译好的目标文件连接成一个可执行文件或动态库。

  • 链接器的核心工作就是符号表解析、重定位和库文件链接三个部分。(具体细节看CSAPP7.5-7.7)
  • 符号解析
    • 每个可重定位目标程序中都存在符号表的数据结构，包含了一些被声明的函数和变量的符号。依上例，main.o和sum.o都有一个这样的结构。符号表中的每一项都包含一个符号名字和一个符号定义的地址。
    • 符号解析的任务就是将这些符号和它们所在的源文件、库文件中的定义进行匹配。这个过程会生成符号表，用于给链接器在后续的重定位中找到函数所在的地址。
    • 对于符号解析有重载（不同的类，函数名相同）的特殊情况，比如Foo::bar(int,long)会变成bar__3Fooil。其中3是名字字符数
  • 重定位：在符号解析完成后，链接器会把不同的目标文件合并在一起，此时就需要对目标代码进行地址的修正，使得各个目标文件之间的函数调用或者变量访问都可以正确。这个过程叫做重定位。链接器会根据符号表信息，将每个函数调用位置中的符号替换成实际的地址。
  • 库文件链接：链接器还需要为程序链接不同的库文件，包括系统库和用户库。这些库文件可能是静态库或者动态库。
    • 如果是静态库，链接器会从库文件中提取目标代码并将其与目标文件合并成一个可执行文件。
    • 如果是动态库，则需要在运行时动态加载库文件，并将其链接到应用程序中。

符号和符号表

见 Linux Executable file: Structure & Running

符号解析

  • 局部变量
  • 编译器只允许每个模块中每个局部符号有一个定义。同时确保它们拥有唯一的名字。
  • 全局变量
  • 缺失情况：当编译器遇到一个不是在当前模块中定义的符号（变量或函数名）时，会假设该符号是在其他某个模块中定义的，生成一个链接器符号表条目，并把它交给链接器处理。如果链接器在它的任何输入模块中都找不到这个被引用符号的定义，就输出undefined reference to
  • 同名情况：编译器报错或者选择一个，
    • 函数和已初始化的全局变量是强符号，
    • 未初始化的全局变量是弱符号。
  • 选择规则：
    • 规则 1：不允许有多个同名的强符号。
    • 规则 2：如果有一个强符号和多个弱符号同名，那么选择强符号。
    • 规则 3：如果有多个弱符号同名，那么从这些弱符号中任意选择一个。
    • 规则 2 和规则 3 的应用会造成一些不易察觉的运行时错误，对于不警觉的程序员来说，是很难理解的，尤其是如果重复的符号定义还有不同的类型时。

重定位

一旦链接器完成了符号解析这一步，就把代码中的每个符号引用和正好一个符号定义（即它的一个输入目标模块中的一个符号表条目）关联起来。此时，链接器就知道它的输入目标模块中的代码节和数据节的确切大小。现在就可以开始重定位步骤了，在这个步骤中，将合并输入模块，并为每个符号分配运行时地址。重定位由两步组成：

  • 重定位节和符号定义。
  • 在这一步中，链接器将所有相同类型的节合并为同一类型的新的聚合节。
    • 例如，来自所有输入模块的.data 节被全部合并成一个节，这个节成为输出的可执行目标文件的.data 节。
    • 然后，链接器将运行时内存地址赋给新的聚合节，赋给输入模块定义的每个节，以及赋给输入模块定义的每个符号。
    • 当这一步完成时，程序中的每条指令和全局变量都有唯一的运行时内存地址了。
  • 重定位节中的符号引用。
  • 在这一步中，链接器修改代码节和数据节中对每个符号的引用，使得它们指向正确的运行时地址。
  • 要执行这一步，链接器依赖于可重定位目标模块中称为重定位条目（relocation entry）的数据结构，我们接下来将会描述这种数据结构。
重定位条目

当汇编器生成一个目标模块时，它并不知道数据和代码最终将放在内存中的什么位置。它也不知道这个模块引用的任何外部定义的函数或者全局变量的位置。所以，无论何时汇编器遇到对最终位置未知的目标引用，它就会生成一个重定位条目，告诉链接器在将目标文件合并成可执行文件时如何修改这个引用。

代码的重定位条目放在 .rel.text 中。已初始化数据的重定位条目放在 .rel.data 中。

下面 展示了 ELF 重定位条目的格式。

  1. offset 是需要被修改的引用的节偏移。
  2. symbol 标识被修改引用应该指向的符号。
  3. type 告知链接器如何修改新的引用。
  4. ELF 定义了 32 种不同的重定位类型，有些相当隐秘。我们只关心其中两种最基本的重定位类型：
    1. R_X86_64_PC32。重定位一个使用 32 位 PC 相对地址的引用。回想一下 3.6.3 节，一个 PC 相对地址就是距程序计数器（PC）的当前运行时值的偏移量。当 CPU 执行一条使用 PC 相对寻址的指令时，它就将在指令中编码的 32 位值加上 PC 的当前运行时值，得到有效地址（如 call 指令的目标），PC 值通常是下一条指令在内存中的地址。(将 PC 压入栈中来使用)
    2. R_X86_64_32。重定位一个使用 32 位绝对地址的引用。通过绝对寻址，CPU 直接使用在指令中编码的 32 位值作为有效地址，不需要进一步修改。
  5. addend 是一个有符号常数，一些类型的重定位要使用它对被修改引用的值做偏移调整。
typedef struct {
    long offset;    /* Offset of the reference to relocate */
    long type:32,   /* Relocation type */
         symbol:32; /* Symbol table index */
    long addend;    /* Constant part of relocation expression */
} Elf64_Rela;

目标文件与库的位置

链接器通常从左到右解析依赖项，这意味着如果库 A 依赖于库 B，那么库 B 应该在库 A 之前被链接。

库顺序

假设有三个库 libA, libB, 和 libC，其中 libA 依赖 libB，而 libB 又依赖 libC。在 CMake 中，你应该这样链接它们：

target_link_libraries(your_target libC libB libA)

这样的顺序确保了当链接器处理 libA 时，libB 和 libC 中的符号已经可用。

书上截图

4.1 静态链接

静态库static library就是将相关的目标模块打包形成的单独的文件。使用ar命令。

  • 在Linux系统中，静态库以一种称为存档(archive)的特殊文件格式存放在磁盘中。
  • 存档文件是一组连接起来的可重定位目标文件的集合，有一个头部用来描述每个成员目标文件的大小和位置。
  • 存档文件名由后缀.a标识。

优点与问题

静态库的优点在于：

  • 程序员不需要显式的指定所有需要链接的目标模块，因为指定是一个耗时且容易出错的过程；
  • 链接时，连接程序只从静态库中拷贝被程序引用的目标模块，这样就减小了可执行文件在磁盘和内存中的大小。

问题：

  • 几乎所有程序都需要printf这样的库函数，每个可执行文件都包含该模块的代码段和数据段，浪费磁盘空间。
  • linux采用虚拟内存管理内存分配，每个进程的内存空间是独立的，运行时所有程序都要把这些库函数代码段和数据段加载到自己的内存里，浪费内存。
  • 静态库和所有的软件一样，需要定期维护和更新。如果应用程序员想要使用一个库的最新版本，他们必须以某种方式了解到该库的更新情况，然后显式地将他们的程序与更新了的库重新链接。

静态链接过程

深入理解计算机系统P477,静态库例子

gcc -static -o prog2c main2.o -L. -lvector

图 7-8 概括了链接器的行为。-static 参数告诉编译器驱动程序，链接器应该构建一个完全链接的可执行目标文件，它可以加载到内存并运行，在加载时无须更进一步的链接。-lvector 参数是 libvector.a 的缩写，-L. 参数告诉链接器在当前目录下查找 libvector.a。

  • 当链接器运行时，它判定 main2.o 引用了 addvec.o 定义的 addvec 符号，所以复制 addvec.o 到可执行文件。
  • 因为程序不引用任何由 multvec.o 定义的符号，所以链接器就不会复制这个模块到可执行文件。
  • 链接器还会复制 libc.a 中的 printf.o 模块，以及许多 C 运行时系统中的其他模块。

4.2 动态链接

  • 共享库（shared library）是致力于解决静态库缺陷的一个现代创新产物。共享库是一个目标模块，在运行或加载时，可以加载到任意的内存地址，并和一个在内存中的程序链接起来。
  • 共享库也称为共享目标（shared object），在 Linux 系统中通常用 .so 后缀来表示。微软的操作系统大量地使用了共享库，它们称为 DLL（动态链接库）。
  • 这个过程称为动态链接（dynamic linking），是由一个叫做动态链接器（dynamic linker）的程序来执行的。

共享库是以两种不同的方式来“共享”的：

  • 首先，在任何给定的文件系统中，对于一个库只有一个. so 文件。所有引用该库的可执行目标文件共享这个 .so 文件中的代码和数据，而不是像静态库的内容那样被复制和嵌入到引用它们的可执行的文件中。
  • 其次，在内存中，一个共享库的 .text 节的一个副本可以被不同的正在运行的进程共享

ld-link

如上创建了一个可执行目标文件 prog2l，而此文件的形式使得它在运行时可以和 libvector.so 链接。基本的思路是：

  • 当创建可执行文件时，静态执行一些链接
  • 此时，没有任何 libvector.so 的代码和数据节真的被复制到可执行文件 prog2l 中。反之，链接器复制了一些重定位和符号表信息，它们使得运行时可以解析对 libvector.so 中代码和数据的引用。
  • 然后在程序加载时，动态完成链接过程。
  • 动态链接可以在可执行文件第一次加载和运行时发生（加载时链接）
    • Common case for Linux,handled automatically by the dynamic linker (ld-linux.so).
    • Standard C library (libc.so)usually dynamically linked.
  • 动态链接也可以在程序开始运行后发生（运行时链接）.
    • In Linux,this is done by calls to the dlopen() interface.
    • Distributing software.
    • High-performance web servers.
    • Runtime library interpositioning.

加载情况一

情况：在应用程序被加载后执行前时，动态链接器加载和链接共享库的情景。

核心思想：由动态链接器接管，加载管理和关闭共享库（比如，如果没有其他共享库还在使用这个共享库，dlclose函数就卸载该共享库。）。

  1. 首先，加载部分链接的可执行文件 prog2l。
  2. prog2l 包含一个 .interp 节，这一节包含动态链接器的路径名，动态链接器本身就是一个共享目标（如在 Linux 系统上的 ld-linux.so）. 加载器不会像它通常所做地那样将控制传递给应用，而是加载和运行这个动态链接器。然后，动态链接器通过执行下面的重定位完成链接任务：
  3. 重定位 libc.so 的文本和数据到某个内存段。
  4. 重定位 libvector.so 的文本和数据到另一个内存段。
  5. 重定位 prog2l 中所有对由 libc.so 和 libvector.so 定义的符号的引用。

最后，动态链接器将控制传递给应用程序。从这个时刻开始，共享库的位置就固定了，并且在程序执行的过程中都不会改变。

加载情况二

情况：应用程序在运行时要求动态链接器加载和链接某个共享库，而无需在编译时将那些库链接到应用。

实际应用情况：

  • 分发软件。微软 Wmdows 应用的开发者常常利用共享库来分发软件更新。他们生成一个共库的新版本，然后用户可以下载，并用它替代当前的版本。下一次他们运行应用程序时，应用将自动链接和加载新的共享库。
  • 构建高性能 Web 服务器。
  • 许多 Web 服务器生成动态内容，比如个性化的 Web 页面、账户余额和广告标语
  • 早期的 Web 服务器通过使用 fork 和 execve 创建一个子进程，并在该子进程的上下文中运行 CGI 程序来生成动态内容。
  • 然而，现代高性能的 Web 服务器可以使用基于动态链接的更有效和完善的方法来生成动态内容。

思路是将每个生成动态内容的函数打包在共享库中。

  1. 当一个来自 Web 浏览器的请求到达时，服务器动态地加载和链接适当的函数，然后直接调用它，而不是使用 fork 和 execve 在子进程的上下文中运行函数。
  2. 函数会一直缓存在服务器的地址空间中，所以只要一个简单的函数调用的开销就可以处理随后的请求了。这对一个繁忙的网站来说是有很大影响的。更进一步地说，在运行时无需停止服务器，就可以更新已存在的函数，以及添加新的函数。

动态库的优点

  • 更新动态库，无需重新链接；对于大系统，重新链接是一个非常耗时的过程；
  • 运行中可供多个程序使用，内存中只需要有一份，节省内存。运行时一个共享库的代码段和数据段在物理内存中只有一份，但映射到多个虚拟内存片段上，供不同程序使用。其中代码段是只读的，整个操作系统绝对只有一份。但数据段有可能被修改，在修改的时候则会复制一个副本，每个进程有自己的一个内存副本。
  • 共享库是.so文件，不会和我们自己的代码一起合并成可执行文件，不占磁盘空间。

动态链接

fPIC，fPIE

编译器yasm的参数-DPIE

如果同一份代码可能被加载到进程空间的任意虚拟地址上执行(如共享库和动态加载代码),那么就需要使用-fPIC生成位置无关代码。

如何实现动态链接

  1. 共享库是.so文件，不会和我们自己的代码一起合并成可执行文件，不占磁盘空间。
  2. 运行时一个共享库的代码段和数据段在物理内存中只有一份，但映射到多个虚拟内存片段上，供不同程序使用。
  3. 其中代码段是只读的，整个操作系统绝对只有一份。
  4. 但数据段有可能被修改，在修改的时候则会复制一个副本，每个进程有自己的一个内存副本。
  5. 共享库的代码段和数据段加载到任意的内存段中，位置不固定。
  6. 加载完成后，进行符号重定位。回想一下之前说过的重定位过程，需要修改所有符号引用的地址。
  7. 由于动态链接在运行时才确定共享库代码段和数据段的内存地址，所以在运行时才能进行重定位。
  8. 运行时修改代码，想想就觉得不优雅。而且Linux不允许在运行时修改代码段。
  9. 由此，要完成动态链接，还需要引入了最后一个重要的概念，位置无关代码，即在加载时无需重定位的代码。

位置无关代码（Position-Independent Code, PIC）

  • 问题：多个进程是如何共享程序的一个副本的呢？
    • 一种方法是给每个共享库分配一个事先预备的专用的(虚拟)地址空间片，然后要求加载器总是在这个地址加载共享库。
  • 问题。
    • 地址空间的使用效率不高，因为即使一个进程不使用这个库，那部分空间还是会被分配出来。
    • 难以管理。我们必须保证没有片会重叠。
      • 库修改了之后，我们必须确认已分配给它的片还适合它的大小。如果不适合了，必须找一个新的片。
      • 创建了一个新的库，我们还必须为它寻找空间。随着时间的进展，假设在一个系统中有了成百个库和库的各个版本库，就很难避免地址空间分裂成大量小的、未使用而又不再能使用的小洞。
      • 更糟的是，对每个系统而言，库在内存中的分配都是不同的，这就引起了更多令人头痛的管理问题。

  • 可以加载而无需重定位的代码称为位置无关代码（Position-Independent Code，PIC）

    • 无限多个进程可以共享一个共享模块的代码段的单一副本。（当然，每个进程仍然会有它自己的读/写数据块。）

  • 在一个 x86-64 系统中，对同一个目标模块中符号的引用是不需要特殊处理使之成为 PIC。可以用 PC 相对寻址来编译这些引用，构造目标文件时由静态链接器重定位。

  • 然而，对共享模块定义的外部过程和对全局变量的引用需要一些特殊的技巧，接下来我们会谈到。

PIC 数据引用

  • 目标：生成对全局变量的 PIC 引用
  • 思想：无论我们在内存中的何处加载一个目标模块（包括共享目标模块），数据段与代码段的距离总是保持不变。因此，代码段中任何指令和数据段中任何变量之间的距离都是一个运行时常量，与代码段和数据段的绝对内存位置是无关的。由于数据段是可以在运行时修改的，所以可以把对代码段的修改转化为对数据段的修改。
  • 实现：在数据段前面加入一个数据结构，全局偏移量表（Global Offset Table，GOT）。每一个被该模块引用的全局数据目标（过程或全局变量），都在GOT里有一个8字节条目，并为每个条目生成一个重定位条目。
  • 实际使用：在加载时，动态链接器会重定位 GOT 中的每个条目，使得它包含目标的正确的绝对地址。然后程序执行时就能正确访问正确的绝对地址了。

PIC 函数调用

  • 情况：假设程序调用一个由共享库定义的函数。编译器没有办法预测这个函数的运行时地址，因为定义它的共享模块在运行时可以加载到任意位置。
  • 简单方法：为该引用生成一条重定位记录，然后动态链接器在程序加载的时候再解析它。不过，这种方法并不是 PIC，因为它需要链接器修改调用模块的代码段。

解决方法：延迟绑定（lazy binding），将过程地址的绑定推迟到第一次调用该过程时。

动机：使用延迟绑定的动机是对于一个像 libc.so 这样的共享库输出的成百上千个函数中，一个典型的应用程序只会使用其中很少的一部分。把函数地址的解析推迟到它实际被调用的地方，能避免动态链接器在加载时进行成百上千个其实并不需要的重定位。

结果：第一次调用过程的运行时开销很大，但是其后的每次调用都只会花费一条指令和一个间接的内存引用。

实现：延迟绑定是通过两个数据结构之间简洁但又有些复杂的交互来实现的，这两个数据结构是：GOT 和过程链接表（Procedure Linkage Table，PLT）。如果一个目标模块调用定义在共享库中的任何函数，那么它就有自己的 GOT 和 PLT。GOT 是数据段的一部分，而 PLT 是代码段的一部分。

首先，让我们介绍这两个表的内容。

  • 过程链接表（PLT）。PLT 是一个数组，其中每个条目是 16 字节代码。
  • PLT[0] 是一个特殊条目，它跳转到动态链接器中。
  • 每个被可执行程序调用的库函数都有它自己的 PLT 条目。每个条目都负责调用一个具体的函数。
  • PLT[1]（图中未显示）调用系统启动函数（__libc_start_main），它初始化执行环境，调用 main 函数并处理其返回值从 PLT[2] 开始的条目调用用户代码调用的函数。在我们的例子中，PLT[2] 调用 addvec，PLT[3]（图中未显示）调用 printf。
  • 全局偏移量表（GOT）。正如我们看到的，GOT 是一个数组，其中每个条目是 8 字节地址。
  • 和 PLT 联合使用时，GOT[O] 和 GOT[1] 包含动态链接器在解析函数地址时会使用的信息。GOT[2] 是动态链接器在 ld-linux.so 模块中的入口点。
  • 其余的每个条目对应于一个被调用的函数，其地址需要在运行时被解析。每个条目都有一个相匹配的 PLT 条目。例如，GOT[4] 和 PLT[2] 对应于 addvec。初始时，每个 GOT 条目都指向对应 PLT 条目的第二条指令。

PLT

上图a 展示了 GOT 和 PLT 如何协同工作，在 addvec 被第一次调用时，延迟解析它的运行时地址：

  1. 第 1 步。不直接调用 addvec，程序调用进入 PLT[2]，这是 addvec 的 PLT 条目。
  2. 第 2 步。第一条 PLT 指令通过 GOT[4] 进行间接跳转。因为每个 GOT 条目初始时都指向它对应的 PLT 条目的第二条指令，这个间接跳转只是简单地把控制传送回 PLT[2] 中的下一条指令。
  3. 第 3 步。在把 addvec 的 ID（0x1）压入栈中之后，PLT[2] 跳转到 PLT[0]。
  4. 第 4 步。PLT[0] 通过 GOT[1] 间接地把动态链接器的一个参数压入栈中，然后通过 GOT[2] 间接跳转进动态链接器中。动态链接器使用两个栈条目来确定 addvec 的运行时位置，用这个地址重写 GOT[4]，再把控制传递给 addvec。

上图b 给出的是后续再调用 addvec 时的控制流：

  1. 第 1 步。和前面一样，控制传递到 PLT[2]。
  2. 第 2 步。不过这次通过 GOT[4] 的间接跳转会将控制直接转移到 addvec。
库搜索优先级

静态库

  1. gcc先从-L寻找；
  2. 再找环境变量LIBRARY_PATH指定的搜索路径；
  3. 再找内定目录 /lib /usr/lib /usr/local/lib 这是当初compile gcc时写在程序内的。

动态库

  1. 编译目标代码时指定的动态库搜索路径-L；
  2. 环境变量LD_LIBRARY_PATH指定的动态库搜索路径；
  3. 配置文件/etc/ld.so.conf中指定的动态库搜索路径；
  4. 默认的动态库搜索路径/lib /usr/lib/ /usr/local/lib
shaojiemike@snode6 /lib/modules/5.4.0-107-generic/build  [06:32:26]
> gcc -print-search-dirs
install: /usr/lib/gcc/x86_64-linux-gnu/9/
programs: =/usr/lib/gcc/x86_64-linux-gnu/9/:/usr/lib/gcc/x86_64-linux-gnu/9/:/usr/lib/gcc/x86_64-linux-gnu/:/usr/lib/gcc/x86_64-linux-gnu/9/:/usr/lib/gcc/x86_64-linux-gnu/:/usr/lib/gcc/x86_64-linux-gnu/9/../../../../x86_64-linux-gnu/bin/x86_64-linux-gnu/9/:/usr/lib/gcc/x86_64-linux-gnu/9/../../../../x86_64-linux-gnu/bin/x86_64-linux-gnu/:/usr/lib/gcc/x86_64-linux-gnu/9/../../../../x86_64-linux-gnu/bin/
libraries: =/usr/lib/gcc/x86_64-linux-gnu/9/:/usr/lib/gcc/x86_64-linux-gnu/9/../../../../x86_64-linux-gnu/lib/x86_64-linux-gnu/9/:/usr/lib/gcc/x86_64-linux-gnu/9/../../../../x86_64-linux-gnu/lib/x86_64-linux-gnu/:/usr/lib/gcc/x86_64-linux-gnu/9/../../../../x86_64-linux-gnu/lib/../lib/:/usr/lib/gcc/x86_64-linux-gnu/9/../../../x86_64-linux-gnu/9/:/usr/lib/gcc/x86_64-linux-gnu/9/../../../x86_64-linux-gnu/:/usr/lib/gcc/x86_64-linux-gnu/9/../../../../lib/:/lib/x86_64-linux-gnu/9/:/lib/x86_64-linux-gnu/:/lib/../lib/:/usr/lib/x86_64-linux-gnu/9/:/usr/lib/x86_64-linux-gnu/:/usr/lib/../lib/:/usr/lib/gcc/x86_64-linux-gnu/9/../../../../x86_64-linux-gnu/lib/:/usr/lib/gcc/x86_64-linux-gnu/9/../../../:/lib/:/usr/lib/

5. 加载器

加载器：将可执行程序加载到内存并进行执行，loader和ld-linux.so。

将可执行文件加载运行

其他技巧：GNU用于理解和处理目标文件的相关命令

命令 描述
ar 创建静态库，插入、删除、列出和提取成员；
stringd 列出目标文件中所有可以打印的字符串；
strip 从目标文件中删除符号表信息；
nm 列出目标文件符号表中定义的符号；
size 列出目标文件中节的名字和大小；
readelf 显示一个目标文件的完整结构，包括ELF 头中编码的所有信息。
objdump 显示目标文件的所有信息，最有用的功能是反汇编.text节中的二进制指令。
ldd 列出可执行文件在运行时需要的共享库。

动态查看进程调用命令

ltrace 跟踪进程调用库函数过程 strace 系统调用的追踪或信号产生的情况 Relyze 图形化收费试用

debugging symbols

  • 编译时加入-g选项，可以生成调试信息，这样在gdb中可以查看源代码。
  • 但是在复杂的编译过程中，最后可执行文件丢失了debugging symbols，所以研究一下怎么生成debugging symbols， 编译过程中的传递，以及如何查看。

debugging symbols的内容

objdump -g <archive_file>.a
# 如果.o文件有debugging symbols，会输出各section详细信息
Contents of the .debug_aranges section (loaded from predict-c.o):
# 没有则如下
cabac-a.o:     file format elf64-x86-64

dct-a.o:     file format elf64-x86-64

deblock-a.o:     file format elf64-x86-64

生成debugging symbols

  • 预处理过程
  • 应该会保留debugging symbols所需的信息，在实验后发现，执行gcc -E -g testBigExe.cpp -o testDebug.i相对于无-g的命令，只会多一行信息# 1 "/staff/shaojiemike/test/OS//"
  • 编译过程
  • 执行gcc -S -g testBigExe.cpp -o testDebug.s，对比之前的汇编文件，由72行变成9760行。具体解析参考 GNU assembly file一文
  • -g前后
  • 汇编过程：保留了debug信息的汇编代码生成带debug信息的目标文件
  • 链接(Linker)

编译代码中OpenMP实现

简单的#pragma omp for，编译后多出汇编代码如下。当前可以创建多少个线程默认汇编并没有显示的汇编指令。

call omp_get_num_threads@PLT
movl %eax, %ebx
call omp_get_thread_num@PLT
movl %eax, %ecx

call    GOMP_barrier@PLT

某些atomic的导语会变成对应汇编

需要进一步的研究学习

  • chatGPT说：后端阶段（例如汇编器和连接器），则主要是对汇编代码和目标代码进行优化，例如指令调度、地址计算、代码缩减等。但是我持严重怀疑态度, 链接过程有这么多优化吗？

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

基础不牢，地动山摇。ya 了。

参考文献

https://www.cnblogs.com/LiuYanYGZ/p/5574601.html

https://hansimov.gitbook.io/csapp/part2/ch07-linking/7.5-symbols-and-symbol-tables

TLB: real pagewalk overhead

简介

TLB的介绍，请看

页表相关

理论基础

大体上是应用访问越随机， 数据量越大，pgw开销越大。

ISCA 2013 shows the pgw overhead in big memory servers.

Basu 等 - Efficient Virtual Memory for Big Memory Servers.pdf

or ISCA 2020 Guvenilir 和 Patt - 2020 - Tailored Page Sizes.pdf

机器配置

# shaojiemike @ snode6 in ~/github/hugoMinos on git:main x [11:17:05]
$ cpuid -1 -l 2
CPU:
      0x63: data TLB: 2M/4M pages, 4-way, 32 entries
            data TLB: 1G pages, 4-way, 4 entries
      0x03: data TLB: 4K pages, 4-way, 64 entries
      0x76: instruction TLB: 2M/4M pages, fully, 8 entries
      0xff: cache data is in CPUID leaf 4
      0xb5: instruction TLB: 4K, 8-way, 64 entries
      0xf0: 64 byte prefetching
      0xc3: L2 TLB: 4K/2M pages, 6-way, 1536 entries
# if above command turns out empty
cpuid -1 |grep TLB -A 10 -B 5
# will show sth like

L1 TLB/cache information: 2M/4M pages & L1 TLB (0x80000005/eax):
    instruction # entries     = 0x40 (64)
    instruction associativity = 0xff (255)
    data # entries            = 0x40 (64)
    data associativity        = 0xff (255)
L1 TLB/cache information: 4K pages & L1 TLB (0x80000005/ebx):
    instruction # entries     = 0x40 (64)
    instruction associativity = 0xff (255)
    data # entries            = 0x40 (64)
    data associativity        = 0xff (255)
L2 TLB/cache information: 2M/4M pages & L2 TLB (0x80000006/eax):
    instruction # entries     = 0x200 (512)
    instruction associativity = 2-way (2)
    data # entries            = 0x800 (2048)
    data associativity        = 4-way (4)
L2 TLB/cache information: 4K pages & L2 TLB (0x80000006/ebx):
    instruction # entries     = 0x200 (512)
    instruction associativity = 4-way (4)
    data # entries            = 0x800 (2048)
    data associativity        = 8-way (6)

OS config

default there is no hugopage(usually 4MB) to use.

$ cat /proc/meminfo | grep huge -i
AnonHugePages:      8192 kB
ShmemHugePages:        0 kB
FileHugePages:         0 kB
HugePages_Total:       0
HugePages_Free:        0
HugePages_Rsvd:        0
HugePages_Surp:        0
Hugepagesize:       2048 kB
Hugetlb:               0 kB

explained is here.

设置页表大小

other ways: change source code

  1. way1: Linux transparent huge page (THP) support allows the kernel to automatically promote regular memory pages into huge pages, cat /sys/kernel/mm/transparent_hugepage/enabled but achieve this needs some details.
  2. way2: Huge pages are allocated from a reserved pool which needs to change sys-config. for example echo 20 > /proc/sys/vm/nr_hugepages. And you need to write speacial C++ code to use the hugo page
# using mmap system call to request huge page
mount -t hugetlbfs \
    -o uid=<value>,gid=<value>,mode=<value>,pagesize=<value>,size=<value>,\
    min_size=<value>,nr_inodes=<value> none /mnt/huge

without recompile

But there is a blog using unmaintained tool hugeadm and iodlr library to do this.

sudo apt install libhugetlbfs-bin
sudo hugeadm --create-global-mounts
sudo hugeadm --pool-pages-min 2M:64

So meminfo is changed

$ cat /proc/meminfo | grep huge -i
AnonHugePages:      8192 kB
ShmemHugePages:        0 kB
FileHugePages:         0 kB
HugePages_Total:      64
HugePages_Free:       64
HugePages_Rsvd:        0
HugePages_Surp:        0
Hugepagesize:       2048 kB
Hugetlb:          131072 kB

using iodlr library

git clone

应用测量

Measurement tools from code

# shaojiemike @ snode6 in ~/github/PIA_huawei on git:main x [17:40:50]
$ ./investigation/pagewalk/tlbstat -c '/staff/shaojiemike/github/sniper_PIMProf/PIMProf/gapbs/sssp.inj -f /staff/shaojiemike/github/sniper_PIMProf/PIMProf/gapbs/benchmark/kron-20.wsg -n1'
command is /staff/shaojiemike/github/sniper_PIMProf/PIMProf/gapbs/sssp.inj -f /staff/shaojiemike/github/sniper_PIMProf/PIMProf/gapbs/benchmark/kron-20.wsg -n1
K_CYCLES   K_INSTR      IPC DTLB_WALKS ITLB_WALKS K_DTLBCYC  K_ITLBCYC  DTLB% ITLB%
324088     207256      0.64 733758     3276       18284      130         5.64  0.04
21169730   11658340    0.55 11802978   757866     316625     24243       1.50  0.11

平均单次开销(开始到稳定)： dtlb miss read need 24~50 cycle ，itlb miss read need 40~27 cycle

案例的时间分布：

  • 读数据开销占比不大，2.5%左右
  • pagerank等图应用并行计算时，飙升至 22%
  • bfs 最多就是 5%，没有那么随机的访问。
  • 但是gemv 在65000 100000超内存前，即使是全部在计算，都是0.24%
  • 原因：访存模式：图应用的访存模式通常是随机的、不规则的。它们不像矩阵向量乘法（gemv）等应用那样具有良好的访存模式，后者通常以连续的方式访问内存。连续的内存访问可以利用空间局部性，通过预取和缓存块的方式减少TLB缺失的次数。
  • github - GUOPS can achive 90%
  • DAMOV - ligra - pagerank can achive 90% in 20M input case

gemm

  • nomal gemm can achive 100% some situation
  • matrix too big can not be filled in cache, matrix2 access jump lines so always cache miss
  • O3 flag seems no time reduce, beacause there is no SIMD assembly in code
  • memory access time = pgw + tlb access time + load data 2 cache time

gemm

the gemm's core line is

for(int i=0; i<N; i++){
   // ignore the overflow, do not influence the running time.
   for(int j=0; j<N; j++){
      for(int l=0; l<N; l++){
            // gemm
            // ans[i * N + j] += matrix1[i * N + l] * matrix2[l * N + j];

            // for gemm sequantial
            ans[i * N + j] += matrix1[i * N + l] * matrix2[j * N + l];
      }
   }
}

and real time breakdown is as followed. to do

  1. first need to perf get the detail time

bigJump

manual code to test if tlb entries is run out

$ ./tlbstat -c '../../test/manual/bigJump.exe 1 10 100'
command is ../../test/manual/bigJump.exe 1 10 100
K_CYCLES   K_INSTR      IPC DTLB_WALKS ITLB_WALKS K_DTLBCYC  K_ITLBCYC  DTLB% ITLB%
2002404    773981      0.39 104304528  29137      2608079    684        130.25  0.03

$ perf stat -e mem_uops_retired.all_loads -e mem_uops_retired.all_stores -e mem_uops_retired.stlb_miss_loads -e mem_uops_retired.stlb_miss_stores ./bigJump.exe 1 10 500
Number read from command line: 1 10 (N,J should not big, [0,5] is best.)
result 0
 Performance counter stats for './bigJump.exe 1 10 500':

          10736645      mem_uops_retired.all_loads
         532100339      mem_uops_retired.all_stores
             57715      mem_uops_retired.stlb_miss_loads
         471629056      mem_uops_retired.stlb_miss_stores

In this case, tlb miss rate up to 47/53 = 88.6%

Big bucket hash table

using big hash table

other apps

Any algorithm that does random accesses into a large memory region will likely suffer from TLB misses. Examples are plenty: binary search in a big array, large hash tables, histogram-like algorithms, etc.

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。

无

Intel SDM(Software Developer's Manual)

Introduction

This set consists of

volume Descriptions pages(size)
volume 1 Basic Architecture 500 pages(3MB)
volume 2 (combined 2A, 2B, 2C, and 2D) full instruction set reference 2522 pages(10.8MB)
volume 3 (combined 3A, 3B, 3C, and 3D) system programming guide 1534 pages(8.5MB)
volume 4 MODEL-SPECIFIC REGISTERS (MSRS) 520 pages

volume3: Memory management(paging), protection, task management, interrupt and exception handling, multi-processor support, thermal and power management features, debugging, performance monitoring, system management mode, virtual machine extensions (VMX) instructions, Intel® Virtualization Technology (Intel® VT), and Intel® Software Guard Extensions (Intel® SGX).

AMD64 Architecture Programmer's Manual (3336 pages)

more graph and easier to read.

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。

https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html

Linux Executable file: Structure & Running 2

可执行文件的运行

要运行可执行目标文件 prog，我们可以在 Linux shell 的命令行中输入它的名字： linux> ./prog 因为 prog 不是一个内置的 shell 命令，所以 shell 会认为 prog 是一个可执行目标文件。

进程的启动

  • Linux进程的启动是通过父进程复制一个子进程，子进程通过execve系统调用启动加载器。
  • 加载器（loader）删除子进程已有的虚拟存储段，
  • 通过将虚拟地址空间中的页映射到可执行文件的页大小组块，
  • 并创建一组新的代码、数据、堆、栈段，
  • 同时新的堆和栈被初始化为零。
  • 新的代码和数据段被初始化为可执行文件的内容，
  • 最后将CUP指令寄存器设置成可执行文件入口，启动运行。

执行完上述操作后，其实可执行文件的真正指令和数据都没有别装入内存中。操作系统只是通过可执行文件头部的信息建立起可执行文件和进程虚拟内存之间的映射关系而已。

memory map

除了一些头部信息，在加载过程中没有任何从磁盘到内存的数据复制。直到 CPU 引用一个被映射的虚拟页时才会进行复制，此时，操作系统利用它的页面调度机制自动将页面从磁盘传送到内存。

比如，现在程序的入口地址为 0x08048000 ，刚好是代码段的起始地址。当CPU打算执行这个地址的指令时，发现页面 0x8048000 ~ 0x08049000 (一个页面一般是4K)是个空页面，于是它就认为是个页错误。此时操作系统根据虚拟地址空间与可执行文件间的映射关系找到页面在可执行文件中的偏移，然后在物理内存中分配一个物理页面，并在虚拟地址页面与物理页面间建立映射，最后把EXE文件中页面拷贝到内存的物理页面，进程重新开始执行。该过程如下图所示：

接下来，加载器跳转到程序的入口点，也就是 _start函数的地址。这个函数是在系统目标文件 ctrl.o 中定义的，对所有的 C 程序都是一样的。_start 函数调用系统启动函数 __libc_start_main，该函数定义在 libc.so 中。它初始化执行环境，调用用户层的 main 函数，处理 main 函数的返回值，并且在需要的时候把控制返回给内核。

fork 和 execve 函数的差异

  • fork 函数在新的子进程中运行相同的程序，新的子进程是父进程的一个复制品。
  • execve 函数在当前进程的上下文中加载并运行一个新的程序。
  • 它会覆盖当前进程的地址空间，但并没有创建一个新进程。
  • 新的程序仍然有相同的 PID，并且继承了调用 execve 函数时已打开的所有文件描述符。

程序运行途中修改exe程序

  • 由于操作系统使用页表和虚拟内存机制来实现按需加载。按需加载意味着只有在程序执行到需要访问某个代码段时，才会将该代码段从可执行文件加载到内存中。
  • 那么如果我在程序运行的途中重新编译程序，修改了代码段，那么程序会怎么样呢？
  • Chatgpt：运行中的程序尝试执行新的代码时，会发生未定义的行为，因为操作系统不会自动将新的代码加载到正在运行的进程的内存中。
  • 一个页表4KB，一个程序的代码段可能有如下100KB甚至几十MB，不可能全部加载。
# shaojiemike @ snode6 in ~/github/sniper_PIMProf/PIMProf/gapbs on git:dev o [15:15:29]
$ size /usr/lib/llvm-10/bin/llvm-mca
   text    data     bss     dec     hex filename
 144530    6056    8089  158675   26bd3 /usr/lib/llvm-10/bin/llvm-mca

# shaojiemike @ snode6 in ~/github/sniper_PIMProf/PIMProf/gapbs on git:dev o [15:18:14]
$ l /usr/lib/llvm-10/bin/llvm-mca
-rwxr-xr-x 1 root root 153K Apr 20  2020 /usr/lib/llvm-10/bin/llvm-mca

程序运行途中修改python代码

  • 虽然修改python代码类似修改C代码，按理来说不会影响程序进行。但是python是逐行解释执行的，很难让人不思考会不会影响正在运行中的程序。
  • 答案是不会，原因有二：
  • python代码在运行时，会被编译成字节码，然后再执行字节码。修改python代码后，其对应的字节码会在下一次运行程序时，Python解释器对比文件时间戳时更新。
  • Python解释器在运行时，会将所需的文件提前加载到内存里

GDB调试修改

Memalloc

2

Buddy 内存分配

是一种用于管理计算机内存的算法，旨在有效地分配和释放内存块，以防止碎片化并提高内存的使用效率。这种算法通常用于操作系统中，以管理系统内核和进程的内存分配。

Buddy 内存分配算法的基本思想是将物理内存划分为大小相等的块，每个块大小都是 2 的幂次方。每个块可以分配给一个正在运行的进程或内核。当内存被分配出去后，它可以被分割成更小的块，或者合并成更大的块，以适应不同大小的内存需求。

算法的名称 "Buddy" 来自于分配的块之间的关系，其中一个块被称为 "buddy"，它是另一个块的大小相等的邻居。这种关系使得在释放内存时，可以尝试将相邻的空闲块合并成更大的块，从而减少内存碎片。

Buddy 内存分配算法的工作流程大致如下：

  1. 初始时，整个可用内存被视为一个大块，大小是 2 的幂次方。

  2. 当一个进程请求内存分配时，算法会搜索可用的块，找到大小合适的块来满足请求。如果找到的块比所需的稍大，它可以被分割成两个相等大小的 "buddy" 块，其中一个分配给请求的进程。

  3. 当一个进程释放内存时，该块会与其 "buddy" 块合并，形成一个更大的块。然后，这个更大的块可以与其它相邻的块继续合并，直到达到较大的块。

Buddy 内存分配算法在一些操作系统中用于管理内核和进程的物理内存，尤其在嵌入式系统和实时操作系统中，以提高内存使用效率和避免碎片化问题。

ucore（Micro-kernel Operating System for Education）

是一个用于教育目的的微内核操作系统

linux遇到问题

我们可window写程序占满16G内存

但是linux,用了3GB就会seg fault

猜想是不是有单进程内存限制 https://www.imooc.com/wenda/detail/570992

而且malloc alloc的空间在堆区，我们可以明显的发现这个空间是被栈区包住的，有限的。windows是如何解决这个问题的呢？ 1. 首先这个包住是虚拟地址，通过页表映射到的物理地址是分开的 2. 根据第一点，可以实现高地址动态向上移动

动态数据区一般就是“堆栈”。“栈 (stack)”和“堆(heap)”是两种不同的动态数据区，栈是一种线性结构，堆是一种链式结构。进程的每个线程都有私有的“栈”，所以每个线程虽然 代码一样，但本地变量的数据都是互不干扰。一个堆栈可以通过“基地址”和“栈顶”地址来描述。全局变量和静态变量分配在静态数据区，本地变量分配在动态数 据区，即堆栈中。程序通过堆栈的基地址和偏移量来访问本地变量。

当进程初始化时，系统会自动为进程创建一个默认堆，这个堆默认所占内存的大小为1M。堆对象由系统进行管理，它在内存中以链式结构存在。

Linux 单进程内存限制

/etc/security/limits.conf

# shaojiemike @ node5 in ~ [6:35:51]
$ ulimit -a
-t: cpu time (seconds)              unlimited
-f: file size (blocks)              unlimited
-d: data seg size (kbytes)          unlimited
-s: stack size (kbytes)             8192
-c: core file size (blocks)         0
-m: resident set size (kbytes)      unlimited
-u: processes                       513967
-n: file descriptors                1024
-l: locked-in-memory size (kbytes)  65536
-v: address space (kbytes)          unlimited
-x: file locks                      unlimited
-i: pending signals                 513967
-q: bytes in POSIX msg queues       819200
-e: max nice                        0
-r: max rt priority                 0
-N 15:                              unlimited

ulimit -HSn 4096 # H指定了硬性大小，S指定了软性大小，n表示设定单个进程最大的打开文件句柄数量。硬限制是实际的限制，而软限制，是warnning限制，只会做出warning

lsof
文件描述符

文件句柄数

这些限制一般不会限制内存。

超算登录节点任务限制的实现

GNU malloc()

调用malloc(size_t size)函数分配内存成功，总会分配size字节VM（再次强调不是RAM），并返回一个指向刚才所分配内存区域的开端地址。分配的内存会为进程一直保留着，直到你显示地调用free()释放它（当然，整个进程结束，静态和动态分配的内存都会被系统回收）。

GNU libc库提供了二个内存分配函数,分别是malloc()和calloc()。glibc函数malloc()总是通过brk()或mmap()系统调用来满足内存分配需求。函数malloc()，根据不同大小内存要求来选择brk()，还是mmap()，阈值 MMAP_THRESHOLD=128Kbytes是临界值。小块内存(<=128kbytes)，会调用brk()，它将数据段的最高地址往更高处推（堆从底部向上增长）。大块内存，则使用mmap()进行匿名映射(设置标志MAP_ANONYMOUS)来分配内存，与堆无关，在堆之外。

malloc不是直接分配内存的，是第一次访问的时候才分配的？

https://www.zhihu.com/question/20836462

问题

  1. 堆区和栈区是进程唯一的吗？
  2. 是的，而且栈主要是为一个线程配备，小可以保证基本在cache里
  3. 两个操作系统的malloc的是物理内存还是虚拟内存
  4. Linux采用的是copy-on-write机制

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

每次都是6008这里，40000*6008*3/1024/1024=687MB 733448/1024=716MB 问了大师兄，问题竟然是malloc的传入参数错误的类型是int,导致存不下3*40*1024*40*1024。应该用size_t类型。（size_t是跨平台的非负整数安全类型）

参考文献

https://blog.csdn.net/shenzi/article/details/3972437?utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.base&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.base

程序（进程）内存空间分布深入理解

Linux Executable file: Structure & Running

可执行文件历史溯源

  • COFF是32位System V平台上使用的一种格式。
  • 它允许使用共享库和调试信息。
  • 然而，它在节的最大数量和节名称的长度限制方面存在缺陷。
  • 它也不能提供C++等语言的符号调试信息。
  • 然而，像XCOFF(AIX)和ECOFF(DEC，SGI)这样的扩展克服了这些弱点，并且有一些版本的Unix使用这些格式。
  • Windows的PE+格式也是基于COFF的。 可见可执行文件在不同平台上的规则还是有所不同的，后续会以UNIX ELF来分析

ELF 可执行目标文件

exe

可执行目标文件的格式类似于可重定位目标文件的格式。

  1. ELF 头描述文件的总体格式。它还包括程序的入口点（entry point），也就是当程序运行时要执行的第一条指令的地址。
  2. .text、.rodata 和 .data 节与可重定位目标文件中的节是相似的，除了这些节已经被重定位到它们最终的运行时内存地址以外。
  3. .init 节定义了一个小函数，叫做 _init，程序的初始化代码会调用它。
  4. 因为可执行文件是完全链接的（已被重定位），所以它不再需要 .rel 节。

可重定位目标文件

  • 下面内容来自 深入理解计算机系统（CSAPP）的7.4 可重定位目标文件一节
  • 图 7-3 展示了一个典型的 ELF 可重定位目标文件的格式。ELF 可重定位目标文件的格式
  • ELF 头（Executable Linkable Format header）Executable Linkable Format
  • 以一个 16 字节的序列开始，这个序列描述了生成该文件的系统的字的大小和字节顺序。
  • ELF 头剩下的部分包含帮助链接器语法分析和解释目标文件的信息。
    • 其中包括 ELF 头的大小、目标文件的类型（如可重定位、可执行或者共享的）、机器类型（如 X86-64）、节头部表（section header table）的文件偏移，以及节头部表中条目的大小和数量。
  • 节头部表描述不同节的位置和大小，其中目标文件中每个节都有一个固定大小的条目（entry）。

夹在 ELF 头和节头部表之间的都是节。一个典型的 ELF 可重定位目标文件包含下面几个节：

  • .text：已编译程序的机器代码。
  • 通常代码区是可共享的（即另外的执行程序可以调用它），使其可共享的目的是对于频繁被执行的程序，只需要在内存中有一份代码即可。
  • 代码区通常是只读的，使其只读的原因是防止程序意外地修改了它的指令。
  • .rodata：只读数据，比如 printf 语句中的格式串和开关语句的跳转表。
  • .data：已初始化的全局和静态 C 变量。
  • 已经初始化的全局变量、已经初始化?的静态变量（包括全局静态变量和局部静态变量）和常量数据（如字符串常量）。
  • 局部 C 变量在运行时被保存在栈中，既不岀现在 .data 节中，也不岀现在 .bss 节中。
  • .bss：未初始化的全局和静态 C 变量，以及所有被初始化为 0 的全局或静态变量。
  • 在目标文件中这个节不占据实际的空间，它仅仅是一个占位符。
  • 目标文件格式区分已初始化和未初始化变量是为了空间效率：在目标文件中，未初始化变量不需要占据任何实际的磁盘空间。运行时，在内存中分配这些变量，初始值为 0。
    • 用术语 .bss 来表示未初始化的数据是很普遍的。它起始于 IBM 704 汇编语言（大约在 1957 年）中“块存储开始（Block Storage Start）”指令的首字母缩写，并沿用至今。
  • 区分 .data 和 .bss 节的简单方法是把 “bss” 看成是“更好地节省空间（Better Save Space）” 的缩写。
  • .symtab：一个符号表，它存放在程序中定义和引用的函数和全局变量的信息。
  • 一些程序员错误地认为必须通过 -g 选项来编译一个程序，才能得到符号表信息。实际上，每个可重定位目标文件在 .symtab 中都有一张符号表（除非程序员特意用 STRIP 命令去掉它）。
  • 然而，和编译器中的符号表不同，.symtab 符号表不包含局部变量的条目。
  • .rel.text：一个 .text 节中位置的列表，当链接器把这个目标文件和其他文件组合时，需要修改这些位置。
  • 一般而言，任何调用外部函数或者引用全局变量的指令都需要修改。另一方面，调用本地函数的指令则不需要修改。
  • 注意，可执行目标文件中并不需要重定位信息，因此通常省略，除非用户显式地指示链接器包含这些信息。
  • .rel.data：被模块引用或定义的所有全局变量的重定位信息。
  • 一般而言，任何已初始化的全局变量，如果它的初始值是一个全局变量地址或者外部定义函数的地址，都需要被修改。
  • .debug：一个调试符号表，其条目是
  • 程序中定义的局部变量和类型定义，
  • 程序中定义和引用的全局变量，
  • 以及原始的 C 源文件。
  • 只有以 -g 选项调用编译器驱动程序时，才会得到这张表。
  • .line：原始 C 源程序中的行号和 .text 节中机器指令之间的映射。
  • 只有以 -g 选项调用编译器驱动程序时，才会得到这张表。
  • .strtab：一个字符串表，其内容包括 .symtab 和 .debug 节中的符号表，以及节头部中的节名字。字符串表就是以 null 结尾的字符串的序列。

符号和符号表

每个可重定位目标模块 m 都有一个符号表.symtab，它包含 m 定义和引用的符号的信息。在链接器的上下文中，有三种不同的符号：

  • (出)由模块 m 定义并能被其他模块引用的全局符号。
  • 全局链接器符号对应于非静态的 C 函数和全局变量。
  • (入)由其他模块定义并被模块 m 引用的全局符号。
  • 这些符号称为外部符号，对应于在其他模块中定义的非静态 C 函数和全局变量。
  • 只被模块 m 定义和引用的局部符号。

  • 对应于带 static 属性的 C 函数和全局变量。这些符号在模块 m 中任何位置都可见，但是不能被其他模块引用。

  • 本地链接器符号和本地程序变量的不同是很重要的。

  • .symtab 中的符号表不包含对应于本地非静态程序变量的任何符号。
  • 这些符号在运行时在栈中被管理，链接器对此类符号不感兴趣。
  • 有趣的是，定义为带有 C static 属性的本地过程变量是不在栈中管理的。
  • 相反，编译器在 .data 或 .bss 中为每个定义分配空间，并在符号表中创建一个有唯一名字的本地链接器符号。

实践：readelf

使用命令readelf -s simple.o 可以读取符号表的内容。

示例程序的可重定位目标文件 main.o 的符号表中的最后三个条目。

  • 开始的 8 个条目没有显示出来，它们是链接器内部使用的局部符号。
  • 全局符号 main 定义的条目，
  • 它是一个位于 .text 节
  • 偏移量为 0（即 value 值）处的 24 字节函数。
  • 其后跟随着的是全局符号 array 的定义
  • 位于 .data 节
  • 偏移量为 0 处的 8 字节目标。

  • 外部符号 sum 的引用。

  • type 通常要么是数据，要么是函数。

  • 符号表还可以包含各个节的条目，以及对应原始源文件的路径名的条目。
  • binding 字段表示符号是本地的还是全局的。
  • Ndx=1 表示 .text 节
  • Ndx=3 表示 .data 节。
  • ABS 代表不该被重定位的符号；
  • UNDEF 代表未定义的符号，也就是在本目标模块中引用，但是却在其他地方定义的符号；

实践: 查看exe信息相关命令

file test

# read ELF header
readelf -h naive

进一步思考

  • 小结：开辟局部变量、全局变量、malloc空间会影响可执行文件大小吗？对应汇编如何？存放的位置？运行时如何？
  • 设计一个代码量小但是占空间很大的可执行文件。
    • 因为已经初始化的全局变量、已经初始化的静态变量（包括全局静态变量和局部静态变量）会存储在data段，所以这些变量的大小会影响可执行文件的大小。
  • static 与 const效果一样。
  • 设计一个代码量小但是运行时占内存空间很大的可执行文件。
    • malloc的空间会影响运行时的内存空间，但是不会影响可执行文件的大小。
  • 将exe各节内容可视化解释(虽然现在是二进制)

  • 编译的时候，头文件是怎么处理的？

  • data 与 bbs在存储时怎么区分全局与静态变量

  • 符号表为什么有全局变量的符号，这些静态局部变量不需要吗？应该是需要的
  • 请给出 .rel.text .rel.data的实例分析

线程与进程

  • 调度：进程是资源管理的基本单位，线程是程序执行的基本单位。
  • 切换：线程上下文切换比进程上下文切换要快得多。
    • TLB是每个核私有的，如果一个核从一个进程切换到另一个进程，TLB要全部清空。
    • 但是线程不需要，因为线程共享相同的虚拟地址空间。
    • 所以线程切换开销远小于进程切换开销。
  • 拥有资源： 进程是拥有资源的一个独立单位，线程不拥有系统资源，但是可以访问隶属于进程的资源。
  • 系统开销： 创建或撤销进程时，系统都要为之分配或回收系统资源，如内存空间，I/O设备等，OS所付出的开销显著大于在创建或撤销线程时的开销，进程切换的开销也远大于线程切换的开销。

（软件）多线程与（CPU）超线程

线程和进程都可以用多核，但是线程共享进程内存（比如，openmp）

超线程注意也是为了提高核心的利用率，当有些轻量级的任务时（读写任务）核心占用很少，可以利用超线程把一个物理核心当作多个逻辑核心，一般是两个，来使用更多线程。AMD曾经尝试过4个。

单核多进程切换

进程结构

正在运行的程序，叫进程。每个进程都有完全属于自己的，独立的，不被干扰的内存空间。此空间，被分成几个段(Segment),分别是Text, Data, BSS, Heap, Stack。

esp ebp

  • push pop %ebp 涉及到编译器调用函数的处理方式 application binary interface (ABI).
  • 如何保存和恢复寄存器
  • 比如：cdecl（代表 C 声明）是 C 编程语言的调用约定，被许多 C 编译器用于 x86 体系结构。 在 cdecl 中，子例程参数在堆栈上传递。整数值和内存地址在 EAX 寄存器中返回，浮点值在 ST0 x87 寄存器中返回。寄存器 EAX、ECX 和 EDX 由调用方保存，其余寄存器由被叫方保存。x87 浮点寄存器 调用新函数时，ST0 到 ST7 必须为空（弹出或释放），退出函数时ST1 到 ST7 必须为空。ST0 在未用于返回值时也必须为空。

0000822c <func>:
    822c: e52db004  push {fp}  ; (str fp, [sp, #-4]!) 如果嵌套调用 push {fp,lr}
    8230: e28db000  add fp, sp, #0
    8234: e24dd014  sub sp, sp, #20
    8238: e50b0010  str r0, [fp, #-16]
    823c: e3a03002  mov r3, #2
    8240: e50b3008  str r3, [fp, #-8]
    8244: e51b3008  ldr r3, [fp, #-8]
    8248: e51b2010  ldr r2, [fp, #-16]
    824c: e0030392  mul r3, r2, r3
    8250: e1a00003  mov r0, r3
    8254: e24bd000  sub sp, fp, #0
    8258: e49db004  pop {fp}  ; (ldr fp, [sp], #4) 如果嵌套调用 pop {fp,lr}
    825c: e12fff1e  bx lr          ; MOV PC,LR

00008260 <main>:
    8260: e92d4800  push {fp, lr}
    8264: e28db004  add fp, sp, #4
    8268: e24dd008  sub sp, sp, #8
    826c: e3a03019  mov r3, #25
    8270: e50b3008  str r3, [fp, #-8]
    8274: e51b0008  ldr r0, [fp, #-8]
    8278: ebffffeb  bl 822c <func>
    827c: e3a03000  mov r3, #0
    8280: e1a00003  mov r0, r3
    8284: e24bd004  sub sp, fp, #4
    8288: e8bd8800  pop {fp, pc}

arm PC = x86 EIP ARM 为什么这么设计，就是为了返回地址不存栈，而是存在寄存器里。但是面对嵌套的时候，还是需要压栈。

栈区（stack）

由编译器自动分配释放，存放函数的参数值、返回值、局部变量等。在程序运行过程中实时加载和释放，因此，局部变量的生存周期为申请到释放该段栈空间。

WIndow系统一般是2MB。Linux可以查看ulimit -s ，通常是8M

栈空间最好保持在cache里，太大会存入内存。持续地重用栈空间有助于使活跃的栈内存保持在CPU缓存中，从而加速访问。进程中的每个线程都有属于自己的栈。向栈中不断压入数据时，若超出其容量就会耗尽栈对应的内存区域，从而触发一个页错误。

函数参数传递一般通过寄存器，太多了就存入栈内。

大数组seg fault

栈区(stack segment)：由编译器自动分配释放，存放函数的参数的值，局部变量的值等。

局部变量空间是很小的，我们开一个a[1000000]就会导致栈溢出；而全局变量空间在Win 32bit 下可以达到4GB，因此不会溢出。

或者malloc使用堆的区域，但是记得free。

堆区（heap）

用于动态内存分配。堆在内存中位于BSS区和栈区之间。一般由程序员分配和释放，若程序员不释放，程序结束时有可能由OS回收。

分配的堆内存是经过字节对齐的空间，以适合原子操作。堆管理器通过链表管理每个申请的内存，由于堆申请和释放是无序的，最终会产生内存碎片。堆内存一般由应用程序分配释放，回收的内存可供重新使用。若程序员不释放，程序结束时操作系统可能会自动回收。

用户堆，每个进程有一个，进程中的每个线程都从这个堆申请内存，这个堆在用户空间。所谓内训耗光，一般就是这个用户堆申请不到内存了，申请不到分两种情况，一种是你 malloc 的比剩余的总数还大，这个是肯定不会给你了。第二种是剩余的还有，但是都不连续，最大的一块都没有你 malloc 的大，也不会给你。解决办法，直接申请一块儿大内存，自己管理。

除非特殊设计，一般你申请的内存首地址都是偶地址，也就是说你向堆申请一个字节，堆也会给你至少4个字节或者8个字节。

堆有一个堆指针（break brk），也是按照栈的方式运行的。内存映射段是存在在break brk指针与esp指针之间的一段空间。

在Linux中当动态分配内存大于128K时，会调用mmap函数在esp到break brk之间找一块相应大小的区域作为内存映射段返回给用户。

当小于128K时，才会调用brk或者sbrk函数，将break brk向上增长（break brk指针向高地址移动）相应大小，增长出来的区域便作为内存返回给用户。

两者的区别是

内存映射段销毁时，会释放其映射到的物理内存，

而break brk指向的数据被销毁时，不释放其物理内存，只是简单将break brk回撤，其虚拟地址到物理地址的映射依旧存在，这样使的当再需要分配小额内存时，只需要增加break brk的值，由于这段虚拟地址与物理地址的映射还存在，于是不会触发缺页中断。只有在break brk减少足够多，占据物理内存的空闲虚拟内存足够多时，才会真正释放它们。

栈堆的区别

  1. 产生碎片不同 对堆来说，频繁的new/delete或者malloc/free势必会造成内存空间的不连续，造成大量的碎片，使程序效率降低。

对栈而言，则不存在碎片问题，因为栈是先进后出的队列，永远不可能有一个内存块从栈中间弹出。

设计考虑

  1. 代码段和数据段分开，运行时便于分开加载，在哈佛体系结构的处理器将取得更好得流水线效率。
  2. 代码时依次执行的，是由处理器 PC 指针依次读入，而且代码可以被多个程序共享，数据在整个运行过程中有可能多次被调用，如果将代码和数据混合在一起将造成空间的浪费。
  3. 临时数据以及需要再次使用的代码在运行时放入栈中，生命周期短，便于提高资源利用率。
  4. 堆区可以由程序员分配和释放，以便用户自由分配，提高程序的灵活性。

缓冲区溢出攻击（代码注入攻击

  • 缓冲区溢出（Buffer Overflow）是一种常见的软件漏洞，它发生在程序中使用缓冲区（一块内存区域）来存储数据时，输入的数据超过了缓冲区的容量，导致多余的数据溢出到相邻的内存区域。
  • 常见栈上分配空间，然后溢出直接覆盖前面的返回地址，使得返回到任意代码片段执行。如果开启了栈上执行代码，甚至能栈上注入代码并执行。

虚拟内存

用户进程内存空间，也是系统内核分配给该进程的VM(虚拟内存)，但并不表示这个进程占用了这么多的RAM(物理内存)。这个空间有多大？命令top输出的VIRT值告诉了我们各个进程内存空间的大小（进程内存空间随着程序的执行会增大或者缩小）。

Linux虚拟地址空间分布

虚拟地址空间在32位模式下它是一个4GB的内存地址块。在Linux系统中, 内核进程和用户进程所占的虚拟内存比例是1:3,如下图。而Windows系统为2:2(通过设置Large-Address-Aware Executables标志也可为1:3)。这并不意味着内核使用那么多物理内存，仅表示它可支配这部分地址空间，根据需要将其映射到物理内存。

值得注意的是，每个进程的内核虚拟地址空间都是映射到相同的真实物理地址上，因为都是共享同一份物理内存上的内核代码。除此之外还要注意内核虚拟地址空间总是存放在虚拟内存的地址最高处。

其中，用户地址空间中的蓝色条带对应于映射到物理内存的不同内存段，灰白区域表示未映射的部分。这些段只是简单的内存地址范围，与Intel处理器的段没有关系。

上图中Random stack offset和Random mmap offset等随机值意在防止恶意程序。Linux通过对栈、内存映射段、堆的起始地址加上随机偏移量来打乱布局，以免恶意程序通过计算访问栈、库函数等地址。

execve(2)负责为进程代码段和数据段建立映射，真正将代码段和数据段的内容读入内存是由系统的缺页异常处理程序按需完成的。另外，execve(2)还会将BSS段清零。

top

VIRT = SWAP + RES # 总虚拟内存=动态 + 静态

RES >= CODE + DATA + SHR. # 静态内存 = 代码段 + 静态数据段 + 共享内存

MEM = RES / RAM

                          DATA CODE  RES VIRT
before allocation:         124    4  408 3628
after 5MB allocation:     5008    4  476 8512           //malloc 5M, DATA和VIRT增加5M, RES不变
after 2MB initialization: 5008    4 2432 8512           //初始化 2M, DATA和VIRT不变， RES增加2M


//如果最后加上free(data),  DATA, RES, VIRT又都会相应的减少，回到最初的状态

top 里按f 可以选择要显示的内容。

SWAP

  • Swapping的大部分时间花在数据传输上，交换的数据也越多，意味时间开销也随之增加。对于进程而言，这个过程是透明的。
  • so(swap out)：由于RAM资源不足，PFRA会将部分匿名页框的数据写入到交换区(swap area)，备份之。
  • si(swap in) : 当发生内存缺页异常的时候，缺页异常处理程序会将交换区(磁盘)的页面又读回物理内存。
  • 每次Swapping，都有可能不只是一页数据，不管是si，还是so。Swapping意味着磁盘操作，更新页表等操作，这些操作开销都不小，会阻塞用户态进程。所以，持续飚高的si/so意味着物理内存资源是性能瓶颈。
  • 在内存空间设计早期只有分段没有分页时，SWAP还可以用来内存交换(暂存内存数据，重新排列内存)，来消除内存碎片。

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

Light-weight Contexts: An OS Abstraction for Safety and Performance

https://blog.csdn.net/zy986718042/article/details/73556012

https://blog.csdn.net/qq_38769551/article/details/103099014

https://blog.csdn.net/ywcpig/article/details/52303745

https://zhuanlan.zhihu.com/p/23643064

https://www.bilibili.com/video/BV1N3411y7Mr?spm_id_from=444.41.0.0

Library

GLIBC

GLIBC（GNU C Library）是Linux系统中的标准C库，它提供了许多与程序执行和系统交互相关的功能。GLIBC是应用程序与操作系统之间的接口，提供了许多系统调用的包装函数和其他基础功能，使应用程序能够访问操作系统提供的服务和资源。

GLIBC的主要功能包括：

  1. 标准C函数：GLIBC实现了C语言的标准库函数，例如字符串处理、内存操作、文件操作、数学函数等。它为应用程序提供了基础的编程功能和操作接口。
  2. 系统调用封装：GLIBC封装了许多底层的系统调用，例如文件I/O、进程管理、网络通信等。它提供了更高级别的API函数，使开发者能够更方便地进行系统编程。
  3. 内存管理：GLIBC提供了内存分配和管理的函数，例如malloc、free、realloc等。这些函数允许应用程序在运行时动态分配和释放内存，提供了对内存资源的灵活控制。
  4. 多线程支持：GLIBC提供了对多线程编程的支持，包括线程创建、同步原语、线程局部存储等功能。它使得开发者能够编写多线程的并发程序。

与上下文切换开销的关系

上下文切换与GLIBC之间没有直接关系。上下文切换是操作系统的概念，是在进程或线程之间切换执行权的过程。GLIBC作为C库，封装了一些系统调用和基础功能，但并不直接参与上下文切换的过程。

然而，GLIBC的性能和效率可以影响上下文切换的开销。GLIBC的实现方式、性能优化以及与操作系统内核的协作方式，可能会对上下文切换的效率产生影响。例如，GLIBC的线程库（如pthread）的设计和性能特性，以及对锁、条件变量等同步原语的实现方式，都可能会影响多线程上下文切换的开销。

因此，尽管GLIBC本身不直接执行上下文切换，但它的设计和实现对于多线程编程和系统性能仍然具有重要的影响。

安装最新版本

ubuntu换源

在PPA。改系统的glibc十分的危险，ssh连接，ls命令等，都需要用到。会导致ssh连接中断等问题。

从源码安装

不推荐，可能会遇到库依赖。比如缺少bison和gawk。详细依赖见

mkdir $HOME/glibc/ && cd $HOME/glibc
wget http://ftp.gnu.org/gnu/libc/glibc-2.32.tar.gz
tar -xvzf glibc-2.32.tar.gz
mkdir build 
mkdir glibc-2.32-install
cd build
~/glibc/glibc-2.32/configure --prefix=$HOME/glibc/glibc-2.32-install
make
make install

寻找动态链接库

您可以使用以下方法来查找libstdc++库的位置：

  1. 使用g++或gcc命令查找：如果您的系统上安装了g++或gcc编译器，您可以使用以下命令来查找libstdc++库的位置：
g++ -print-file-name=libstdc++.so

或者

gcc -print-file-name=libstdc++.so
  1. 使用ldconfig命令查找：ldconfig是Linux系统中用于配置动态链接器的命令。您可以运行以下命令来查找libstdc++库的路径：
ldconfig -p | grep libstdc++.so
  1. 在默认路径下查找：libstdc++通常位于标准的系统库路径中。在大多数Linux发行版中，libstdc++的默认安装路径为/usr/lib或/usr/lib64。您可以在这些目录中查找libstdc++的库文件。

如果您找到了libstdc++库的路径，您可以将其添加到CMakeLists.txt中的CMAKE_CXX_FLAGS变量中，如之前的回答中所示。

请注意，如果您正在使用的是Clang编译器（clang++），则默认情况下它将使用libc++作为C++标准库，而不是libstdc++。如果您确实希望使用libstdc++，需要显式指定使用-stdlib=libstdc++标志。例如：

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -stdlib=libstdc++")

希望这些方法能够帮助您找到libstdc++库并解决您的问题。如有更多问题，请随时向我询问。

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。

无

Context Switch

上下文切换

  • 根据geekculture的博客的说法
  • 上下文主要指的是CPU的寄存器状态，状态越多(上下文越多)，切换时开销就越大。
  • 包括程序计数器(program counters,PC)，栈指针SP，通用寄存器等。还有virtual memory mappings, file descriptor bindings, and credentials.虚拟内存映射、文件描述符绑定和凭据？
  • 类型可以分成三类
  • to do

上下文切换的开销

According to 2007 paper

  1. direct costs
  2. The processor registers need to be saved and restored,
  3. the OS kernel code (scheduler) must execute,
  4. the TLB entries need to be reloaded,
  5. and processor pipeline must be flushed
  6. cache interference cost or indirect cost of context switch.
  7. context switch leads to cache sharing between multiple processes, which may result in performance degradation.

何时上下文切换

进程或线程的上下文切换可以在多种情况下发生，下面列举了一些常见的情况：

  1. 抢占调度：当操作系统采用抢占式调度算法时，更高优先级的进程或线程可能会抢占当前运行的进程或线程的CPU时间片，从而导致上下文切换。
  2. 时间片耗尽：操作系统通常使用时间片轮转算法来分配CPU时间。当进程或线程的时间片用尽时，操作系统会进行上下文切换，将CPU分配给其他进程或线程。
  3. 阻塞和等待：当一个进程或线程发起阻塞的系统调用（如I/O操作）或等待某个事件发生时，操作系统会将其从运行状态切换到阻塞状态，并切换到另一个可运行的进程或线程。
  4. 中断处理：当发生硬件中断（如时钟中断、设备中断）或软件中断（如异常、信号），操作系统会中断当前进程或线程的执行，保存其上下文，并转而处理中断服务例程。完成中断处理后，操作系统会恢复中断前的进程或线程的上下文，继续其执行。
  5. 多核处理器间的迁移：在多核处理器系统中，进程或线程可能会从一个核心切换到另一个核心，以实现负载均衡或遵循其他调度策略。

需要注意的是，上下文切换是操作系统内核的责任，它根据调度策略和内核的算法来管理进程和线程的切换。上下文切换的具体发生时机和行为取决于操作系统的设计和实现。

进程上下文切换 context switch

保存下来的上下文，会存储在系统内核中，并在任务重新调度执行时再次加载进来。这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行。

基本原理

  • 由于操作系统的抽象: 进程间需要隔离(地址空间，使用的文件描述符，访问权限等) 和执行状态。
  • 所以进程间的切换和通讯会触发内核调度器。
  • 正如线程Threads将执行单元与进程分离一样，如果将内存隔离、执行状态和特权分离与进程解耦也有好处。

主要的开销

  • 进程的状态越多(上下文越多)，切换时开销就越大
  • virtual memory mappings, file descriptor bindings, and credentials.虚拟内存映射、文件描述符绑定和凭据？
  • 线程就是共享了大部分
  • 硬件实现的isolation and privilege separation开销是很小的
  • 如果TLB中的页表条目带有地址空间标识符,那么切换上下文只需要一个系统调用和加载一个CPU寄存器就可以完成。
  • 也就是说,硬件实现的内存和特权隔离所需要的实际开销是很小的,主要只是: 1. 一个系统调用,通知OS进行上下文切换 2. 加载一个CPU寄存器,该寄存器包含新的地址空间ID 3. TLB中的对应页表条目标记为无效
  • 随后的指令访问会自动加载新的地址转换信息到TLB。

进程上下文切换的开销

包括以下几个方面：

  • 寄存器保存和恢复：在上下文切换过程中，当前进程的寄存器状态需要保存到内存中，包括程序计数器、堆栈指针、通用寄存器等。而切换到新进程时，之前保存的寄存器状态需要重新加载到寄存器中。
  • 缓存的数据一致性：需要确保数据的一致性，通常会通过缓冲区刷新、写回操作或者使用写时复制等技术来保证数据的完整性。
  • 内存映射切换：每个进程都有自己的内存空间，包括代码、数据和堆栈。在上下文切换时，需要切换内存映射，将当前进程的内存空间从物理内存中解除映射，同时将新进程的内存空间映射到物理内存中。
  • 虚拟内存切换：如果系统使用虚拟内存管理，上下文切换还需要涉及虚拟内存的切换，包括页表的更新和TLB（转换后备缓冲器）的刷新。
  • 当虚拟内存更新后，TLB 也需要刷新，内存的访问也会随之变慢。特别是在多处理器系统上，缓存是被多个处理器共享的，刷新缓存不仅会影响当前处理器的进程，还会影响共享缓存的其他处理器的进程。
  • I/O状态切换：当前进程可能涉及到正在进行的I/O操作，如读取或写入文件、网络通信等。在上下文切换时，需要保存和恢复与I/O相关的状态，以确保之后能够正确地继续进行这些I/O操作。
  • 调度和管理开销：上下文切换过程本身需要一定的调度和管理开销，包括选择下一个要执行的进程、更新进程控制块、维护就绪队列等。

进程切换到不同核时保持数据一致

  1. CL-DM：核的私有缓存之间,通过缓存一致性协议 MESI协议
  2. REG-DM：寄存器的数据：在进程上下文切换的过程中，系统会保存当前进程的状态，包括进程的程序计数器、寄存器、CPU标志寄存器和堆栈指针等等。

线程切换

线程与进程上下文切换开销的不同

  • 当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源。这些资源在上下文切换时是不需要修改的。
  • 另外，线程也有自己的私有数据，比如栈和寄存器等，这些在上下文切换时也是需要保存的。

相对于进程上下文切换，线程上下文切换通常更快，这是因为线程共享相同的地址空间和其他资源，因此上下文切换只需要切换线程的执行状态和部分寄存器，省去了一些额外的开销。

以下是线程上下文切换相对于进程上下文切换的一些优势和省去的时间开销：

  1. 虚拟内存和页表切换：在进程切换时，由于每个进程都有自己独立的虚拟地址空间和页表，切换进程需要切换虚拟内存映射和页表，这会涉及到TLB的刷新和地址空间切换。而线程切换时，线程共享相同的地址空间和页表，因此无需切换虚拟内存和页表，节省了这部分开销。
  2. 上下文切换时间：进程切换通常需要保存和恢复更多的上下文信息，包括寄存器、堆栈指针、文件描述符表等。而线程切换只需要切换线程的执行状态和部分寄存器，上下文切换时间相对较短。
  3. 内核数据结构切换：进程切换时，可能涉及到一些内核数据结构的切换和更新，例如进程描述符、文件表等。而线程切换通常只需要更新线程控制块（Thread Control Block，TCB），而无需更新其他内核数据结构，减少了额外的开销。

尽管线程上下文切换相对较快，但仍然需要一些时间和开销，包括以下方面：

  1. 寄存器切换：线程上下文切换仍然需要保存和恢复部分寄存器的状态，尤其是通用寄存器和程序计数器。
  2. 栈切换：线程切换时，可能需要切换线程的栈空间，包括用户态栈和内核态栈。这涉及到栈指针的调整和栈的切换。
  3. 调度开销：线程切换通常是由操作系统的调度器进行调度和管理的，因此线程上下文切换可能涉及到调度算法的执行和调度队列的操作。

需要注意的是，线程上下文切换的快速性是相对于进程上下文切换而言的，具体的开销和时间取决于系统的设计、硬件的性能和操作系统的实现。不同的操作系统和硬件平台可能会有不同的上下文切换开销。

流程与原理

如果要能清晰的回答这一点，需要对OS的页表管理和上下午切换的流程十分了解。

基本概念

Page Table Isolation

Page Table Isolation(页面表隔离)是一种为了解决Meltdown等CPU安全漏洞而提出的硬件优化机制。

其主要思想是将操作系统内核和用户空间的页面表隔离开来,实现内核地址空间与用户地址空间的隔离。

具体来说,Page Table Isolation 主要包括以下措施:

  • 为内核空间维护单独的页面表,不与任何用户程序共享。
  • 在切换到用户模式时,切换到用户程序自己的页面表。
  • 这样内核和用户程序的地址翻译是完全隔离的。
  • 当用户程序请求切换到内核模式时,切换回内核专用的页面表。
  • 硬件禁止用户模式程序访问内核空间的虚拟地址。

这种机制可以阻止用户程序直接读取内核内存,防止Meltdown类攻击获得内核敏感信息。

当前主流的x86处理器通过在TLB中添加PTI(Page Table Isolation)位实现了此机制,来隔离内核地址空间。这成为了重要的安全优化之一。

页表管理 under PTI

由于PTI的存在，内核维护了两套 页表。

用户态切换的额外开销包括：

  1. 改变页面表基地址。改变CR3寄存器需要100cycle
  2. TLBmisses 可能增多,因为用户态和内核态不再共享TLB项,可能导致缓存本地化的下降。

PCID

进程上下文标识符（PCID） 是一项 CPU 功能，它允许我们在切换页表时通过在 CR3 中设置一个特殊位来跳过刷新整个 TLB。这使得切换页表（在上下文切换或内核进入/退出时）更便宜。但是，在支持 PCID 的系统上，上下文切换代码必须将用户和内核条目都从 TLB 中清除。用户 PCID TLB 刷新将推迟到退出到用户空间，从而最大限度地降低成本。有关PCID / INVPCID详细信息，请参阅 intel.com/sdm。

在没有 PCID 支持的系统上，每个 CR3 写入都会刷新整个 TLB。这意味着每个系统调用、中断或异常都会刷新 TLB

不同核上同一个进程的不同线程的Intel PCID 是相同的吗

对于同一个进程的不同线程,当它们运行在不同的物理核心上时,其Intel PCID (进程上下文ID)是相同的。

主要原因如下:

PCID是用于区分不同进程地址空间的标识符。同一进程的线程共享相同的地址空间。 所以操作系统会为同一进程的所有线程分配相同的PCID,无论它们运行在哪个物理核心上。 当线程在物理核心之间迁移时,不需要改变PCID,因为地址空间没有改变。 线程迁移后,新的核心会重新使用原有的PCID加载地址翻译表,而不是分配新的PCID。 这确保了同进程不同线程使用统一的地址映射,TLB内容可以直接重用,无需刷新。 相反,不同进程之间必须使用不同的PCID,才能隔离地址映射,避免TLB冲突。 所以操作系统只会在进程切换时改变PCID,而线程切换保持PCID不变。

综上,对于同一进程的不同线程,无论运行在哪个物理核心,其PCID都是相同的。这使线程可以重用TLB项,是多线程架构的重要优化手段。同进程线程使用统一PCID,不同进程必须使用独立PCID。

PCID vs ASID

PCID（Process Context Identifier）和 ASID（Address Space Identifier）都是用于优化页表切换的技术

  • PCID使用一个全局的PCID寄存器，用于标识页表项。而ASID则是在每个页表项中直接包含ASID字段。
  • 作用范围：PCID主要用于标识整个页表缓存（TLB）中的页表项。ASID则是用于标识每个页表项。

量化

测量的理论基础

Quantifying the cost of context switch

  • 设计实验：对照实验，来剔除时间段内 system call 和 cache degradation的影响。
  • sched setaffinity() and sched setscheduler()
  • SCHED FIFO and give them the maximum priority.
  • repeat to avg/erase the error

可用代码

# shaojiemike @ hades0 in ~/github/contextSwitch2007 on git:master x [15:59:39] C:10
$ sudo ./measureSwitch
time2 with context swith:       1.523668        1.509177        1.507308
measureSwitch: array_size = 0, stride = 0, min time2 = 1.507308008149266

# shaojiemike @ hades0 in ~/github/contextSwitch2007 on git:master x [16:04:15]
$ sudo ./measureSingle
time1 without context switch:   0.727125        0.655041        0.689502
measureSingle: array_size = 0, stride = 0, min time1 = 0.655041355639696
  • 阅读代码后时间单位是us microseconds, 论文里是3.8 us,我们的机器是0.85 us。
  • 小问题：这个跨核了吗？

实践测试

Tsuna的2010年的博客 code in https://github.com/tsuna/contextswitch 机器配置在实验结果后。

  • syscalls 使用 gettid()
  • 进程上下文切换使用futex来切换。包含futex system calls.开销
  • sched_yield让出CPU使用权,强制发生进程切换.
  • 线程切换还是使用的futex.只不过线程通过 pthread_create创建来执行函数, 而不是fork
  • 线程切换只使用shed_yield().并且设置SCHED_FIFO 和 sched_priority
  • sched_yield()函数的作用是使当前进程放弃CPU使用权,将其重新排入就绪队列尾部。但是如果就绪队列中只有这一个进程,那么该进程会立即再次获得CPU时间片而继续执行。必须有其他等待进程且满足调度条件才会真正发生切换。
  • 如果使用了taskset绑定1个核组，应该就能测量上下文切换。
# snode6
$ sudo taskset 0x3 ./timetctxsw2
2000000  thread context switches in 486078214ns (243.0ns/ctxsw)
$ sudo taskset 0x1 ./timetctxsw2
2000000  thread context switches in 1071542621ns (535.8ns/ctxsw)
# hades0
$ sudo taskset 0x3 ./timetctxsw2
2000000  thread context switches in 89479052ns (44.7ns/ctxsw)
$ sudo taskset 0x1 ./timetctxsw2
2000000  thread context switches in 566817108ns (283.4ns/ctxsw)

如上，snode6应该是550ns

machine| system calls | process context switches | thread context switches | thread context switches 2 ---|---|---|---|---| snode6| 428.6| 2520.3| 2606.3(1738.9)| 277.8| snode6| 427.7| 2419.8| 2249.0(2167.9)| 401.1| snode6| 436.0| 2327.1| 2358.8(1727.8)| 329.3| hades| 65.8| 1806.4| 1806.4| 64.6| hades| 65.5| 1416.4| 1311.6| 282.7| hades| 80.8| 2153.1| 1903.4| 64.3| icarus| 74.1| 1562.3| 1622.3| 51.0| icarus| 74.1| 1464.6| 1274.1| 232.6| icarus| 73.9| 1671.8| 1302.1| 38.0| vlab| 703.4| 5126.3| 4897.7| 826.1| vlab| x| x| x| x| vlab| 697.1| 10651.4| 4476.0| 843.9*| docker ｜｜｜｜ docker ｜｜｜｜ docker ｜｜｜｜

说明:

  1. 同名机器从上到下为：No CPU affinity 和 With CPU affinity 和 With CPU affinity to CPU 0
  2. ()内为。额外添加设置SCHED_FIFO 和 sched_priority的结果。
  3. * 意味着没有sudo权限。报错sched_setscheduler(): Operation not permitted
  4. x 报错taskset: 设置 pid 30727 的亲和力失败: 无效的参数
  5. system calls 理解成 用户态和内核态转换的开销
  6. 根据博客的数据，虚拟化会使得开销增大2～3倍。

问题：

  1. 两个thread context的区别是什么？ 只使用shed_yield().并且设置SCHED_FIFO 和 sched_priority
  2. taskset 限制了能运行的核。
  3. 这个实验测量了 在两个核间的线程切换吗？没绑定应该是多核
  4. 为什么taskset绑定在同一个核反而变慢了呢。snode6
    1. timetctxsw2 340 -> 550
    2. timetctxsw 括号内数据 1712 -> 2225
  5. 同一个核有资源竞争吗？

运行strace -ff -tt -v taskset -a 1 ./timetctxsw2. 应该是不需要strace的，为什么需要记录syscall的信息呢？

# snode6 
2000000  thread context switches in 22987942914ns (11494.0ns/ctxsw)

# snode6 without strace
$ sudo taskset -c 1 ./timetctxsw2
2000000  thread context switches in 1073826309ns (536.9ns/ctxsw)
$ sudo taskset -a 1 ./timetctxsw2
2000000  thread context switches in 1093753292ns (546.9ns/ctxsw)
$ sudo taskset 1 ./timetctxsw2
2000000  thread context switches in 1073456816ns (536.7ns/ctxsw)

# hades
2000000  thread context switches in 20945815905ns (10472.9ns/ctxsw)
# icarus
2000000  thread context switches in 19053536242ns (9526.8ns/ctxsw)
2000000  thread context switches in 17573109017ns (8786.6ns/ctxsw)
2000000  thread context switches in 18538271021ns (9269.1ns/ctxsw)
尝试解释不同机器的差异

猜想：

  1. Intel新产品的硬件确实有特殊设计
 shaojiemike @ snode6 in ~/github/contextswitch on git:master o [19:46:27]
$ sudo ./cpubench.sh
model name : Intel(R) Xeon(R) CPU E5-2695 v4 @ 2.10GHz
2 physical CPUs, 18 cores/CPU, 2 hardware threads/core = 72 hw threads total

hades1# ./cpubench.sh
model name : AMD EPYC 7543 32-Core Processor 1.5 ~ 3.7GHz
2 physical CPUs, 32 cores/CPU, 2 hardware threads/core = 128 hw threads total

# shaojiemike @ icarus0 in ~/github/contextswitch on git:master o [20:41:39] C:1
$ ./cpubench.sh
model name : Intel(R) Xeon(R) Platinum 8358 CPU @ 2.60GHz
2 physical CPUs, 32 cores/CPU, 1 hardware threads/core = 64 hw threads total

ubuntu@VM7096-huawei:~/github/contextswitch$ sudo ./cpubench.sh 
model name : Intel(R) Xeon(R) Silver 4110 CPU @ 2.10GHz
2 physical CPUs, 8 cores/CPU, 2 hardware threads/core = 32 hw threads total
  1. 软件的不同

machine| OS | linux kernel | compile | glibc ---|---|---|---|---| snode6|Ubuntu 20.04.6 LTS|5.4.0-148-generic|gcc 9.4.0|GLIBC 2.31 hades|Ubuntu 22.04.2 LTS|5.15.0-76-generic|gcc 11.3.0|GLIBC 2.35-0ubuntu3.1 icarus|Ubuntu 22.04.2 LTS|5.15.0-75-generic|gcc 11.3.0|GLIBC 2.35-0ubuntu3.1 vlab|Ubuntu 22.04.2 LTS|5.15.81-1-pve|gcc 11.3.0|GLIBC 2.35-0ubuntu3.1

glic 版本使用ldd --version获得。OS影响调度算法，内核影响切换机制，编译器影响代码优化，GLIBC影响系统调用开销。

代码分析
  1. sched_setscheduler() 是一个用于设置进程调度策略的函数。它允许您更改进程的调度策略以及与之相关的参数。具体来说，sched_setscheduler() 函数用于将当前进程（通过 getpid() 获取进程ID）的调度策略设置为实时调度策略（SCHED_FIFO）。实时调度策略是一种优先级调度策略，它将进程分配给一个固定的时间片，并且仅当进程主动释放 CPU 或者其他高优先级的实时进程出现时，才会进行上下文切换。
  2. /sys/bus/node/devices/node0/cpumap 存储了与特定 NUMA 节点（NUMA node）关联的 CPU 核心映射信息。cpumap 文件中的内容表示与 node0 相关的 CPU 核心的映射。每个位置上的值表示相应 CPU 核心的状态，常见的取值有：
  3. 0：表示该 CPU 核心不属于 node0。
  4. 1：表示该 CPU 核心属于 node0。 这种映射信息可以帮助系统管理员和开发人员了解系统的 NUMA 结构，以及每个 NUMA 节点上的 CPU 核心分布情况。通过查看这些信息，可以更好地优化任务和进程的分配，以提高系统的性能和效率。
# shaojiemike @ snode6 in ~/github/contextswitch on git:master x [22:37:41] C:1
$ cat /sys/bus/node/devices/node0/cpumap
00,003ffff0,0003ffff
# shaojiemike @ snode6 in ~/github/contextswitch on git:master x [23:13:41]
$ cat /sys/bus/node/devices/node1/cpumap
ff,ffc0000f,fffc0000
# 与taskset结合 设置 亲和性
taskset `sed 's/,//g;s/^/0x/' /sys/bus/node/devices/node0/cpumap` exe
taskset 0x00003ffff00003ffff exe

基于lmbench

根据1996的论文，需要考虑几个方面的内容：

  1. 传统的测量取最小值当作是两进程只进行上下文切换的开销。作者认为真实应用有更大的working set (cache footprint)影响。
  2. 在调用context switches时，传统的会包含syscall。比如 write read。这部分pipe overhead varies between 30% and 300% of the context switch time
  3. to do

http://lmbench.sourceforge.net/cgi-bin/man?keyword=lmbench&section=8

实践代码

别人实验结果

知乎实验 5 微秒左右

  • 进程切换实验设计：基于#include <unistd.h> /pipe()的父子进程的write和read system calls
  • 被1996年文章批判了，syscall开销过大。
  • 线程切换实验设计：使用pthread代替fork 其余一样。

论文数据

实验环境：

  • 处理器：Intel Xeon X5650 2.66 GHz 6 core CPUs
  • 操作系统：FreeBSD 11.0 (amd64)
  • 基于信号量semaphore实现会比基于互斥锁mutex快

根据Light-weight Contexts的数据：

  • 进程切换：4.25 微秒 (0.86)，4250*2.66=11305 cycles
  • kernel线程切换：4.12 (0.98)
  • user线程切换 - 基于系统调用：1.71 (0.06) ～ 4548 cycles
  • 内核态用户态切换开销： ～ 1.5 微秒 ～ 4000 cycles
  • user线程切换 - 基于glibc的用户汇编：0.2472 ~ 657 cycles

注意，括号内为十次执行的标准差

解释与组成

  • 0.25 微秒 寄存器信息传递
  • 2 微秒 虚拟地址映射（TLB flush all？）
  • 2 微秒 同步与调度（进程切换）
  • 原因是同一进程或不同进程中的两个内核线程之间切换时执行的内核代码基本上是相同的。

需要进一步的研究学习

  1. 在测量上下文开销的时候，进程和线程的上下午切换开销往往差不多，这是为什么，是因为TLBflush的占比小没有拉开差距吗

在测量上下文切换开销时，进程和线程的切换开销可能会相对接近，这可能是由于以下几个原因：

  1. TLB（Translation Lookaside Buffer）的刷新：TLB是用于高速缓存虚拟地址到物理地址映射的硬件结构。当发生进程或线程切换时，TLB中的缓存项可能需要刷新，以确保新的地址映射有效。虽然线程切换只涉及部分的TLB刷新，但刷新的开销相对较小，因此在总的上下文切换开销中可能没有明显拉开差距。

  2. 寄存器和上下文切换：无论是进程切换还是线程切换，都需要保存和恢复一部分寄存器的状态和执行上下文。这部分的开销在进程和线程切换中是相似的。

  3. 内核操作和调度开销：无论是进程还是线程切换，都需要涉及内核的操作和调度。这包括切换内核栈、更新调度信息、切换上下文等操作，这些开销在进程和线程切换中也是相似的。

需要注意的是，实际上下文切换的开销是受到多个因素的影响，如处理器架构、操作系统的实现、硬件性能等。具体的开销和差距会因系统的不同而有所差异。在某些情况下，线程切换的开销可能会稍微小一些，但在其他情况下，可能会存在较大的差距。因此，一般情况下，不能简单地将进程和线程的上下文切换开销归为相同或明显不同，具体的测量和评估需要结合实际系统和应用场景进行。

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

PIM 最优调度遇到的问题

  1. 理解上下文切换的具体过程，linux内核的角度
  2. 理解相关概念的使用 ASID PCID
  3. 用户态，内核态的概念，切换的细节以及开销
    1. 内核态的代码是共享的吗？内核态的操作有什么？
  4. 各部分的时间占比
  5. 学会测量时间

参考文献

上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。

Quantifying The Cost of Context Switch 2007，ExpCS

lmbench: Portable tools for performance analysis，1996 USENIX ATC

Light-weight Contexts: An OS Abstraction for Safety and Performance

参考 kernel 文档