编译、重定位、装入和链接

• 
  • 编译是得到单个的程序模块
  • 链接是将程序中用到的模块链接在一起，组合他们的虚拟地址（逻辑地址）
  • 装入是得到真正的物理地址

    可重定位文件的结构

    Elf Header部分

• 存放文件的基本信息

  .text段

• 存放编译好的机器代码

  .data段

• 存放已经初始化的全局变量和静态变量

  .bss段

• 未初始化的全局变量和静态变量以及初始化为0的全局变量和静态变量
• better save space
• 并不占据实际的空间，只是一个占位符
• 系统真正运行的时候会分配空间并且初始化为0

  COMMON

• 存放未初始化的全局变量

  .rodata

• 存放只读数据
• 比如字符串和switch的跳转表

  .rel.text

• 存放需要重定位的代码

  .rel.data

• 存放已初始化的数据的重定位

  可执行文件的结构

  ELF Header

• 文件的总体格式

  .init

• 初始化用的代码

  .text .rodata和.data

• 与可重定位文件类似

强符号和弱符号

• 强符号
  • 函数和已经初始化的全局变量
• 弱符号
  • 未初始化的全局变量
• 多个同名的强符号一起出现的时候会引起链接器错误
• 强符号和弱符号一起出现的时候会同意认为是强符号，而不会报错
  • 类型不同的强弱符号，在弱符号出现的模块中，类型会保留弱符号的类型，尽管实际上内存中存储的是强符号的类型
  • 给编译器-fno-common选项，会在多重定义时报错防止上述错误
• 多个弱符号也会认为是同一个变量

  运行时的内存映像

• 
• 代码段，数据段和堆是相邻的
• 栈在最大可用地址的位置，从大到小，堆从小到大
• 程序运行加载的过程
  • 
• 只编译不链接就得到可重定位目标文件

  一个指令序列加载的例子

  // Generated by GPT-4; unmodified #include <stdio.h> #include <stdlib.h> #include <sys/mman.h> #include <fcntl.h> #include <unistd.h> int main(int argc, char *argv[]) { if (argc != 2) { printf("Usage: %s <binary_file>\n", argv[0]); return 1; } // Open the binary file int fd = open(argv[1], O_RDONLY); if (fd < 0) { perror("open"); return 1; } // Get the file size off_t file_size = lseek(fd, 0, SEEK_END); lseek(fd, 0, SEEK_SET); // Allocate memory for the binary void *mem = mmap(NULL, file_size, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE, fd, 0); if (mem == MAP_FAILED) { perror("mmap"); close(fd); return 1; } // Close the file close(fd); // Cast the memory address to a function pointer and call it void (*binary_func)() = (void (*)())mem; binary_func(); // Clean up munmap(mem, file_size); return 0; }

• 也就是打开文件，创建文件和内存位置之间大小等于文件大小的映射关系(mmap)，将指定大小的文件映射到内存空间中，然后将映射到的内存地址强制类型转换为函数指针，然后从这个位置开始执行

  一个应用程序加载的例子

• 应用程序在内存中除了代码段.text，数据段.data和BSS段.bss以外，还包含动态分配内存用的堆和栈空间

  #include <stdint.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <unistd.h> #include <assert.h> #include <elf.h> #include <fcntl.h> #include <sys/mman.h> #define STK_SZ (1 << 20) #define ROUND(x, align) (((uintptr_t)x) & ~(align - 1)) #define MOD(x, align) (((uintptr_t)x) & (align - 1)) #define push(sp, T, ...) ({ *((T*)sp) = (T)__VA_ARGS__; \ sp = (void *)((uintptr_t)(sp) + sizeof(T)); }) void execve_(const char *file, char *argv[], char *envp[]) { // WARNING: This execve_ does not free process resources. // **NOT** all process states are properly initialized. int fd = open(file, O_RDONLY); assert(fd > 0); // Map ELF header to memory Elf64_Ehdr *h = mmap(NULL, 4096, PROT_READ, MAP_PRIVATE, fd, 0); assert(h != MAP_FAILED); assert(h->e_type == ET_EXEC && h->e_machine == EM_X86_64); Elf64_Phdr *pht = (Elf64_Phdr *)((char *)h + h->e_phoff); for (int i = 0; i < h->e_phnum; i++) { Elf64_Phdr *p = &pht[i]; if (p->p_type == PT_LOAD) { // Memory map region uintptr_t map_beg = ROUND(p->p_vaddr, p->p_align); uintptr_t map_end = map_beg + p->p_memsz; while (map_end % p->p_align != 0) map_end++; // Memory map flags int prot = 0; if (p->p_flags & PF_R) prot |= PROT_READ; if (p->p_flags & PF_W) prot |= PROT_WRITE; if (p->p_flags & PF_X) prot |= PROT_EXEC; // Memory map size int map_sz = p->p_filesz + (p->p_vaddr % p->p_align); while (map_sz % p->p_align != 0) map_sz++; // Map file contents to memory void *ret = mmap( (void *)map_beg, // addr, rounded to ALIGN map_sz, // length prot, // protection MAP_PRIVATE | MAP_FIXED, // flags, private & strict fd, // file descriptor ROUND(p->p_offset, p->p_align) // offset ); assert(ret != MAP_FAILED); // Map extra anonymous memory (e.g., bss) intptr_t extra_sz = p->p_memsz - p->p_filesz; if (extra_sz > 0) { uintptr_t extra_beg = map_beg + map_sz; ret = mmap( (void *)extra_beg, extra_sz, prot, // addr, length, protection MAP_ANONYMOUS | MAP_PRIVATE | MAP_FIXED, // flags -1, 0 // no file ); assert(ret != MAP_FAILED); } } } close(fd); static char stack[STK_SZ], rnd[16]; void *sp = (void *)ROUND(stack + sizeof(stack) - 4096, 16); void *sp_exec = sp; int argc = 0; // argc while (argv[argc]) argc++; push(sp, intptr_t, argc); // argv[], NULL-terminate for (int i = 0; i <= argc; i++) push(sp, intptr_t, argv[i]); // envp[], NULL-terminate for (; *envp; envp++) { if (!strchr(*envp, '_')) // remove some verbose ones push(sp, intptr_t, *envp); } // auxv[], AT_NULL-terminate push(sp, intptr_t, 0); push(sp, Elf64_auxv_t, { .a_type = AT_RANDOM, .a_un.a_val = (uintptr_t)rnd } ); push(sp, Elf64_auxv_t, { .a_type = AT_NULL } ); asm volatile( "mov $0, %%rdx;" // required by ABI "mov %0, %%rsp;" "jmp *%1" : : "a"(sp_exec), "b"(h->e_entry)); } int main(int argc, char *argv[], char *envp[]) { if (argc < 2) { fprintf(stderr, "Usage: %s file [args...]\n", argv[0]); exit(1); } execve_(argv[1], argv + 1, envp); }

• 手动实现了一个应用程序的加载器
• 先加载了ELF的文件头（header）到内存中
• 
• ELF文件中有一些LOAD标记，指示文件中的某个位置的规定大小的部分需要加载到内存中指定的位置上，还原程序执行的初始状态
• 然后给程序准备初始状态下的栈中的内容
  • 
  • 操作就是分配一个栈大小的变量，然后向其中push变量，所谓push也就是存入东西然后移动指针
  • 然后跳转指针即可

    Linux提供了一个在程序执行的过程中加载共享库的函数

    void* dlopen(const char *filename, int flag);

• flag可以设置为RTLD_LASY，将代码推迟到执行的时候再符号解析
• 还提供了一个获取共享库的符号地址的方法

  void* dlsym(void* handle, char* symbol);

• 其中的handle就是前面打开的共享库
• symbol就是其中的符号名称

  int dlclose(void* handle);

• 卸载共享库

  中断

• 异步中断
  • 不是当前程序引起的，比如I/O操作引起的
• 同步中断
  • CPU中执行的指令引起的中断
• 

  程序异常

• 
• 所谓的段错误（Segmentation Fault）就是程序试图访问一块未申请的内存空间引起的，也就是图中的13号
• 18号异常时机器检查，一般是硬件错误引起的
• 
  • Linux系统调用号对应的是跳转表中内存的偏移量

    fork和execve

• fork调用一次返回两次
  • 父进程和子进程各一次
• execve调用一次不返回

  程序执行的传参argv

• 
  • argv的第一个是可执行文件的名字
  • argc是参数的数量
• 
  • 环境变量是envp，也类似
  • execve的作用就是调用加载器如图
    • 

      僵尸进程

• 终止运行但是没有被父进程回收的进程就是zombie进程

  回收进程

  pid_t waitpid(pid_t pid,int *statusp,int options);

• 如果pid>0，则回收该pid指定的某个确定的进程
• 如果pid=-1，则回收该进程创建的所有子进程
• 第二个参数是导致返回的子进程的状态信息（终止的原因是正常返回还是异常终止还是其他）
• waitpid程序不会按照任何特定顺序回收子进程，除非明确指定

  发送信号

  int kill(pid_t pid,int sig);

• 如果pid为0，则发送信号给调用进程所在进程组中的所有进程，包括自己
• 如果pid>0，则发送信号给pid指定的进程
• 如果pid<0，则发送信号给进程组-pid的每个进程

  unsigned int alarm(unsigned int secs);

• 进程可以用alarm给自己发送信号，参数是在 secs秒之后给调用进程发送一个SIGALRM
• secs为0就不会调用新的闹钟了

  信号处理

• 一个进程最多只有一个同类型的信号，等待处理的信号超过一个的时候会被直接丢弃
• 处理多个信号
  • 

安装环境

• 参考
• 微软应用商店安装iTunes
• 安装scoop
  • powershell输入iwr -useb get.scoop.sh | iex
• 安装插件和环境
  • scoop bucket add extras
  • scoop install ios-webkit-debug-proxy
• 安装调试器（需要node.js）
  • npm install remotedebug-ios-webkit-adapter -g

    开始调试

• 打开iOS设备的设置—>Safari浏览器—>高级—>将网页检查器打开
• 启动iTunes
• 使用iPad数据线链接电脑的Type-C接口和iPad
• 首次连接可能需要在iOS设备上信任本电脑
• 开启插件remotedebug_ios_webkit_adapter --port=9000
  • 
• 添加上面监听的端口9000
  • 
  • 
• 连接上iPad设备
  • 
  • 点击inspect查看网页
  • 

    控制台传输问题

• 有时候safari无法捕捉到网页的控制台输出，导致chrome远程调试的时候无法输出JavaScript中的console.log()信息
• 
• console.error()一样无法输出，此时只能在html中创建一个元素手动修改其innerHTML来显示输出

  DOM元素参考

• w3school

  safari(iPad)端播放MP4的编码注意事项

• H.264 视频编码和 AAC 音频编码
• MP4 文件的元数据（称为 moov box）应该位于文件的开头
  • ffmpeg选项为-movflags faststart
• 将视频的声道设置为双声道（某些多声道的视频即使视频编码无问题也无法播放）
  • ffmpeg选项-ac 2
• html播放器遇到不支持的视频的时候可能会出现video标签的
  • networkState为3
  • readyState为0
  • error.code为4也就是MEDIA_ERR_SRC_NOT_SUPPORTED

问题与解决

• 报错
  • git clone时虽然已经挂了clash全局，但是仍然访问github 443端口超时
• 解决
  • 使用命令git config --global http.proxy "localhost:<clash端口号>"
  • 

git clone时permission denied的问题

• 可能原因很多，一个是本地的ssh密钥已经无法使用，需要本地生成之后在github上重新添加一个ssh密钥
• 另一个是需要clone入的文件夹没有写入权限，此时需要使用管理员权限打开控制台即可

  pip代理配置

• pip config set global.HTTPS_PROXY https://127.0.0.1:<端口号>
• pip config set global.HTTP_PROXY https://127.0.0.1:<端口号>
• 如果遇到WARNING: Retrying (Retry(total=4, connect=None, read=None, redirect=None, status=None)) after connection broken by 'ProxyError('Cannot connect to proxy.', RemoteDisconnected('Remote end closed connection without response'))'之类的错误，一般是因为代理配置有问题导致的，重新设置正确的端口号即可

解决Windows下Powershell无法执行脚本或者无法运行conda指令的问题

• 报错：
  • 
• 参考
• 在当前powershell中输入get-ExecutionPolicy查看，一般结果是Restricted
• 输入Set-ExecutionPolicy -Scope CurrentUser
• 输入RemoteSigned切换模式
• 然后重启powershell即可
• 此时假如遇到conda命令无法执行的问题，只需要conda init powershell然后重启即可

出错实例

>>> /etc/sudoers: syntax error near line 21 <<<
sudo: parse error in /etc/sudoers near line 21
sudo: no valid sudoers sources found, quitting
sudo: unable to initialize policy plugin

之后尝试使用

• pkexec visudo又报错

  ==== AUTHENTICATING FOR org.freedesktop.policykit.exec === Authentication is needed to run `/usr/sbin/visudo' as the super user Authenticating as: ubuntu,,, (ubuntu) Password: polkit-agent-helper-1: error response to PolicyKit daemon: GDBus.Error:org.freedesktop.PolicyKit1.Error.Failed: No session for cookie ==== AUTHENTICATION FAILED === Error executing command as another user: Not authorized

  解决方案

• 参考链接

bootloader

8086芯片

• reset引脚跳变的时候
• CS（代码段寄存器）和IP（指令指针寄存器）分别初始化为0xffff和0x0000，组合成一个20位的长度地址，再从这个地址跳转到其他地址

  ARM芯片

• 
• PC直接复位到0地址，然后从中断向量表的Reset位置获取下一步跳转的地址
• 直接将代码搬运到内存中执行
• 之后再以此为基础运行别的代码
• 出场写好的，用于启动用户软件的软件称为boot ROM

  修改这部分代码

• 
  • 大部分芯片是用外部电路手动配置的方式
  • 拨码开关的信号会被记录下来控制部分启动信息
  • 对于电脑而言就是BIOS

    二次至多次引导代码(bootloader)

• 一般bootloader是说这个

  为什么需要

• boot rom不够灵活
• 用户可控bootloader
• MCU
  • 单核或者多核同构
  • 主频小于1GHz
  • 没有MMU
  • 最多运行RTOS
  • 
  • 程序运行基本都是NOR Flash
    • 有分离的地址线和数据线
    • 运行不需要拷贝到RAM中
  • STM32的启动
    • 启动时会固定跳转到0地址位置
    • 通过两个boot引脚控制启动的代码映射
      • 引脚01的时候可以映射system boot（arm中的boot rom）
      • 第二位是0的时候，可以把存放用户代码的internal Flash映射到0
      • 引脚11的时候将internal SRAM映射到0
  • boot loader需要完成的任务
    • 关闭看门狗，初始化中断和trap向量表，进行时钟和外设初始化，让芯片正常运行起来
    • 提供CAN、UART、ETH等用于通讯功能的驱动，能够接收外部数据传输请求
    • 提供FLASH的读写与擦除驱动，设计服务来对通讯端口接收到的更新代码进行校验、存储，以及跳转操作系统或后续应用程序代码
    • 如有必要，还会开发一些基础诊断服务，串口交互程序等等
• 嵌入式Linux的SoC和计算机
  • 系统一般存储在NAND Flash中（计算机一般是硬盘），运行前需要先将代码搬运到SRAM中
  • 主要任务就是将代码从NAND Flash或者硬盘中搬运到SRAM中
  • 转移的这部分内容就是bootloader
  • 转移的内容包括SPL和uBoot
    • SPL是接力赛中的第二棒，初始化更大的外部DRAM，再将uBoot搬运到外部RAM中运行
    • uBoot运行初始化程序，再将系统环境变量将OS内核搬运到DRAM中执行
    • OS再完成根文件系统的加载等等

      总结

• boot rom
  • 硬件自检，部分初始化，提供外部配置引脚
• 自己写的boot loader
  • 可以访问外部RAM，NAND Flash
  • 初始化时钟，通讯等
  • 接收，存储以及跳转代码
• application层
  • 操作系统，文件系统
  • 用户应用程序
  • 方便更新

在操作系统上实现进程

Thread OS

#include <am.h>
#include <klib.h>
#include <klib-macros.h>

#define NTASK 2

typedef union task {
  struct {
    union task *next;
    void      (*entry)(void *);
    Context    *context;
  };
  uint8_t stack[8192];
} Task;

Task *current, tasks[NTASK];

void thread_entry(void *arg) {
  while (1) {
    yield();
  }
}

Context *on_interrupt(Event ev, Context *ctx) {
  if (!current) {
    current = &tasks[0];  // First trap
  } else {
    current->context = ctx;
    current = current->next;
  }
  return current->context;
}

int main() {
  cte_init(on_interrupt);

  for (int i = 0; i < LENGTH(tasks); i++) {
    Task *task    = &tasks[i];
    Area stack    = (Area) { &task->context + 1, task + 1 };
    task->context = kcontext(stack, thread_entry, NULL);
    task->next    = &tasks[(i + 1) % LENGTH(tasks)];
  }
  yield();
}

上面的系统与真实的进程有什么区别

• 每个进程都能看到所有变量
• 进程的地址空间不是独立的

  如何解决

• 硬件对内存地址进行翻译，将虚拟内存地址翻译为物理内存地址
• 
• 用户态的程序不能够访问上述映射的数据结构
• 系统虚拟地址空间映射到实际地址空间可能不是全部的（可能没有分配物理页面）
  • 访问的没有分配的页面的时候会有缺页异常被调用
  • 只是在地址空间上做了一个标记
• 使用二叉搜索树找到某一个内存空间的位置（一个有序的集合）

  多个进程的不同虚拟地址映射到同一个位置

• 比如很多进程都用到libc，但是所有进程都用的是同一个而且只读
• 证明：找到映射的物理地址是同一个
• 复制的不同进程中使用malloc分配的是不同的，但是代码部分的地址是相同的，不会真的复制

  fork()写时复制

• 
• 防止fork之后直接执行execve浪费时间
• 只读的部分就不需要拷贝
• 写的时候触发一个缺页中断，写这个位置的进程在检查权限之后会拷贝一次这个页面
• 注意是按页面拷贝的，而不是按变量拷贝的，比如在一个巨大的数组中修改一个值，只拷贝被修改的这个页面

  利用fork()创建内存的历史记录

• 一个长期执行的应用程序防止出现bug导致crash，可以每隔一段时间fork()一次，相当于记录了一个快照，如果出错的话可以回退

  进程调度

• 

  手动控制CPU的调度

• Linux没有硬实时的机制，只能体现在CPU资源获得的控制上
• 使用nice分配CPU

  多级反馈调度队列

• 如果一个程序是计算密集的，可以往后排，但是如果这个程序需要与用户交互那就需要往前排
• 实现的方式是如果一个程序没有用完时间片就主动交出CPU，就提高它的优先级，否则降低

  尽量公平分配CPU

• 
• 中断的时候补偿获得过CPU最少的进程
• 使用红黑树把所有可以调度的进程的时间排序

  如何在公平的调度之下实现不同的优先级

• 不同进程运行的时间的计算方式不同，不同的人的时钟不一样快即可，优先级高的人的时钟慢，否则就快一些

  真实的CPU调度

• 低优先级的进程持有锁的时候被高优先级打断了怎么办
• 实时操作系统的操作就是高优先级的进程可以无条件抢占低优先级的进程
• 操作系统需要知道到底谁获得了什么锁，在什么时候释放
• 优先级继承：
  • 低优先级的任务阻碍了高优先级的任务，则低优先级的任务会继承高优先级任务的优先级
  • 优先级反转
    • 

      多处理器调度

• 
• 
• 处理器逻辑门跳变的时候会发热产生功耗，也就是所谓的动态功耗（另外还有静态功耗）

  什么是core dump

• 将程序crash的时候的内存保存成elf文件，事后可以用gdb调试

  输入输出设备

• I/O是什么
• 设备抽象成寄存器
  • 
• 将设备寄存器映射到内粗地址上
• CPU像访问内存一样访问寄存器

  设备树

• 告诉系统任何设备在什么位置
• 

  总线

• 如何在不增加系统IO设计的基础上扩展其他设备
• 通过总线连接设备
• 连接其他总线
• 将所有的IO设备统一管理起来的设备
• 
• PCI可以连接USB总线
• 速度快的设备是直接连接在PCI总线上的
  • 显卡是直接挂载PCI总线上的
  • 千兆网卡
  • 桥接USB、SATA等控制器也可以

    中断

• 什么是中断？
• 中断就是CPU上的一根线
• 处理重要的中断的时候需要屏蔽掉其他的中断

  DMA

• 大量的内存拷贝需要占用很长的CPU时间
• 
• 此时引入一个专门的拷贝控制器
• 
• 此时内存复制不再需要CPU的直接参与，节约时间
• 用于控制内存和设备之间传输数据

  GPU

• 
• 将通用计算简化，得到可以大量并行的计算

  如何绘制三维画面

• 任何一个多边形都可以分为n-2个三角形
• 为每个三角形贴图
• 将三角形投射到摄像机的平面上
• 

  IO设备的抽象和分类

• 

  分类

• 字节流，读取字符然后丢弃
• 块设备，读取字节数组按块访问

  设备驱动是什么

• 
• 就是一段内核代码
• 将系统对设备的read，write等操作翻译成设备对应的操作
• 设备驱动程序完成的就是设备的通讯协议
• /dev下就是设备文件
  • /dev/stdout就是标准输出，还有/dev/stdin, /dev/stderr
  • echo Hello > /dev/tty这句话会把Hello输出到命令行上
  • /dev/tty就是命令行
  • 但是用户实际使用的是虚拟终端，也就是所谓的/dev/pts/数字序号
    • 不同的终端数字不同
  • /dev/zero是一个0设备，不断生成0
  • /dev/null设备是一个NULL设备，将其他设备的输出重定向给这个设备，就会直接被扔掉
    • 这个设备的weite函数什么都不做
  • /dev/random生成随机数，认为是真的随机数
  • /dev/urandom是随机性不太高的随机数
• 
• 
  • 将一切额外的复杂性都丢给了控制，也就是ioctl
  • 将所有的复杂性都丢给了文件系统
  • 导致系统存在很多隐形的依赖关系，比如/proc等等

    字符设备

• 内核模块实例

  #include <linux/module.h> #include <linux/kernel.h> #include <linux/init.h> #include <linux/cdev.h> #include <linux/device.h> #include <linux/fs.h> #include <linux/uaccess.h> #define MAX_DEV 2 static int dev_major = 0; static struct class *lx_class = NULL; static struct cdev cdev; static ssize_t lx_read(struct file *, char __user *, size_t, loff_t *); static ssize_t lx_write(struct file *, const char __user *, size_t, loff_t *); static struct file_operations fops = { .owner = THIS_MODULE, .read = lx_read, .write = lx_write, }; static struct nuke { struct cdev cdev; } devs[MAX_DEV]; static int __init lx_init(void) { dev_t dev; int i; // allocate device range alloc_chrdev_region(&dev, 0, 1, "nuke"); // create device major number dev_major = MAJOR(dev); // create class lx_class = class_create(THIS_MODULE, "nuke"); for (i = 0; i < MAX_DEV; i++) { // register device cdev_init(&devs[i].cdev, &fops); cdev.owner = THIS_MODULE; cdev_add(&devs[i].cdev, MKDEV(dev_major, i), 1); device_create(lx_class, NULL, MKDEV(dev_major, i), NULL, "nuke%d", i); } return 0; } static void __exit lx_exit(void) { device_destroy(lx_class, MKDEV(dev_major, 0)); class_unregister(lx_class); class_destroy(lx_class); unregister_chrdev_region(MKDEV(dev_major, 0), MINORMASK); } static ssize_t lx_read(struct file *file, char __user *buf, size_t count, loff_t *offset) { if (*offset != 0) { return 0; } else { uint8_t *data = "This is dangerous!\n"; size_t datalen = strlen(data); if (count > datalen) { count = datalen; } if (copy_to_user(buf, data, count)) { return -EFAULT; } *offset += count; return count; } } static ssize_t lx_write(struct file *file, const char __user *buf, size_t count, loff_t *offset) { char databuf[4] = "\0\0\0\0"; if (count > 4) { count = 4; } copy_from_user(databuf, buf, count); if (strncmp(databuf, "\x01\x14\x05\x14", 4) == 0) { const char *EXPLODE[] = { " ⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⣀⣀⠀⠀⣀⣤⣤⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀", " ⠀⠀⠀⣀⣠⣤⣤⣾⣿⣿⣿⣿⣷⣾⣿⣿⣿⣿⣿⣶⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀", " ⠀⢠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⠀⠀⠀⠀", " ⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⡀⠀", " ⠀⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀", " ⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠟⠁⠀", " ⠀⠀⠻⢿⡿⢿⣿⣿⣿⣿⠟⠛⠛⠋⣀⣀⠙⠻⠿⠿⠋⠻⢿⣿⣿⠟⠀⠀⠀⠀", " ⠀⠀⠀⠀⠀⠀⠈⠉⣉⣠⣴⣷⣶⣿⣿⣿⣿⣶⣶⣶⣾⣶⠀⠀⠀⠀⠀⠀⠀⠀", " ⠀⠀⠀⠀⠀⠀⠀⠀⠉⠛⠋⠈⠛⠿⠟⠉⠻⠿⠋⠉⠛⠁⠀⠀⠀⠀⠀⠀⠀⠀", " ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣶⣷⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀", " ⠀⠀⠀⠀⠀⠀⢀⣀⣠⣤⣤⣤⣤⣶⣿⣿⣷⣦⣤⣤⣤⣤⣀⣀⠀⠀⠀⠀⠀⠀", " ⠀⠀⠀⠀⢰⣿⠛⠉⠉⠁⠀⠀⠀⢸⣿⣿⣧⠀⠀⠀⠀⠉⠉⠙⢻⣷⠀⠀⠀⠀", " ⠀⠀⠀⠀⠀⠙⠻⠷⠶⣶⣤⣤⣤⣿⣿⣿⣿⣦⣤⣤⣴⡶⠶⠟⠛⠁⠀⠀⠀⠀", " ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⣿⣿⣿⣿⣿⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀", " ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠒⠛⠛⠛⠛⠛⠛⠛⠛⠛⠛⠓⠀⠀⠀⠀⠀⠀⠀⠀⠀", }; int i; for (i = 0; i < sizeof(EXPLODE) / sizeof(EXPLODE[0]); i++) { printk("\033[01;31m%s\033[0m\n", EXPLODE[i]); } } else { printk("nuke: incorrect secret, cannot lanuch.\n"); } return count; } module_init(lx_init); module_exit(lx_exit); MODULE_LICENSE("GPL"); MODULE_AUTHOR("jyy");

• 更多file operations
  • 

    块设备

• 
• 是一种共享的设备
• 不能直接写入字节，必须先把所在范围内的全部擦除，然后才能写入
• 一次写入的大小是一个block，不是随机访问的
• 在文件系统和磁盘设备之间
  • 
  • 
• 因此通过隔离实现了虚拟化保障安全
  • 
  • 文件系统是磁盘的虚拟化
  • 将一个磁盘变成多个可扩展的动态字节序列（虚拟磁盘）
• 将虚拟磁盘映射到进程的地址空间
  • 
  • 可以改变虚拟磁盘（文件）的大小
• fork的时候会继承偏移量
  • 
  • 假如父子进程一起write一个文件100字节，会共享同一个偏移量，互相不覆盖但是顺序会竞争

    文件系统

• Unix系统的文件系统只有一个根/
• 外接存储设备
  • 可以将任何一个磁盘上的文件系统挂载到文件系统中的任何一个节点上
  • 可以把各种各样的文件系统挂载到任何一个节点上
  • 目录拼接
  • 磁盘分区也可以通过挂载将其包含到文件系统中
  • mount方法，mount 设备 要挂载到的地址
    • 
• loop是回环设备，将文件变为磁盘设备
• 

  切换根文件系统

• 使用switch_root命令
• 执行的内容包括
  • 删除根文件系统的全部内容，节省空间
  • 安装新的文件系统并切换到这个文件系统
  • 把stdin, stdout, stderr附加到新的/dev/console，然后执行新文件系统的init程序
• 命令格式
• switch_root [-c /dev/console] NEW_ROOT NEW_INIT [ARGUMENTS_TO_INIT]
  • 其中NEW_ROOT是实际的根文件系统的挂载目录，执行switch_root命令前需要挂载到系统中
  • NEW_INIT是实际根文件系统的init程序的路径，一般是/sbin/init
  • -c /dev/console是可选参数，用于重定向实际的根文件系统的设备文件，一般情况我们不会使用
  • 而ARGUMENTS_TO_INIT则是传递给实际的根文件系统的init程序的参数，也是可选的

    将一个磁盘映像文件挂载到文件系统之中

• .img文件
• mnt xxx.img /路径
• 系统将这个文件使用一个loop创建为一个设备
• 然后挂载这个设备
  • 

    Linux文件系统的标准

• 

  使用python访问目录

  from pathlib import Path for f in Path('/proc').glob('*/status'): print(f.parts[-2], \ (f.parent / 'cmdline').read_text() or '[kernel]')

  创建链接

  硬链接

• ln [参数] [源文件或目录] [目标文件或目录]
• 创建的是硬链接，实际上指向的是同一个文件，文件的编号都是相同的
• 修改一个就是修改所有
• 完全不可区分
• 便于节省空间
• 仅仅存储指向实际文件数据的指针
• 不可链接目录
• 不可跨文件系统

  软链接

• 类似于快捷方式
• 本身就是一个文件
• 当引用这个文件时，去找另一个文件
• 另一个文件的绝对/相对路径以文本形式存储在文件里
• 可以跨文件系统、可以链接目录
• 链接指向的位置当前不存在也没关系
• ln -s 目标 快捷方式
• 允许创建一个到上一级目录的软连接
• 允许成环
  • 无限递归
  • 使用find寻找的时候，会报错检测到了文件系统回环

一些shell技巧

xxd

• 命令行工具，作用是把二进制文件变成文本可读的文件

• xxd是二进制转文本

• xxd -r是转换过的文本再转换回去

  vim调用外部程序

• 使用命令%!

• 比如vim调用xxd，是使用%!xxd实现

  读取可执行文件的信息

• 

• readelf

  binutils工具集

• 参考链接

• nm命令可以显示一个可执行文件中的符号

• addr2line可以将一个代码的地址转换为行号

  设定从一个特定的内存地址开始执行代码

• 

• 将一个内存地址指针赋值给void (*指针名)()，然后执行这个函数即可

  什么是加载器

• 将内存需要的空间搬到内存里

• 给正确的权限

• 配置初始状态

  // Generated by GPT-4; unmodified #include <stdio.h> #include <stdlib.h> #include <sys/mman.h> #include <fcntl.h> #include <unistd.h> int main(int argc, char *argv[]) { if (argc != 2) { printf("Usage: %s <binary_file>\n", argv[0]); return 1; } // Open the binary file int fd = open(argv[1], O_RDONLY); if (fd < 0) { perror("open"); return 1; } // Get the file size off_t file_size = lseek(fd, 0, SEEK_END); lseek(fd, 0, SEEK_SET); // Allocate memory for the binary void *mem = mmap(NULL, file_size, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE, fd, 0); if (mem == MAP_FAILED) { perror("mmap"); close(fd); return 1; } // Close the file close(fd); // Cast the memory address to a function pointer and call it void (*binary_func)() = (void (*)())mem; binary_func(); // Clean up munmap(mem, file_size); return 0; }

  静态链接

• 找到文件，前4kb映射到内存里

• 里面有header

• 解析header

• 命令行readelf命令可以实现这个功能

  • -h读的是header
  • -a读所有的

• 检查执行的环境对不对，比如CPU架构是不是吻合

• 加载的时候需要将程序中标记了LOAD的位置搬到内存中程序声明的相应的位置即可

  • 计算开始位置，结束位置，权限等
  • 然后将文件映射到上述的空间中

• 初始化栈

  • 
  • 在程序内存中直接定义一个静态的stack

    #include <stdint.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <unistd.h> #include <assert.h> #include <elf.h> #include <fcntl.h> #include <sys/mman.h> #define STK_SZ (1 << 20) #define ROUND(x, align) (((uintptr_t)x) & ~(align - 1)) #define MOD(x, align) (((uintptr_t)x) & (align - 1)) #define push(sp, T, ...) ({ *((T*)sp) = (T)__VA_ARGS__; \ sp = (void *)((uintptr_t)(sp) + sizeof(T)); }) void execve_(const char *file, char *argv[], char *envp[]) { // WARNING: This execve_ does not free process resources. // **NOT** all process states are properly initialized. int fd = open(file, O_RDONLY); assert(fd > 0); // Map ELF header to memory Elf64_Ehdr *h = mmap(NULL, 4096, PROT_READ, MAP_PRIVATE, fd, 0); assert(h != MAP_FAILED); assert(h->e_type == ET_EXEC && h->e_machine == EM_X86_64); Elf64_Phdr *pht = (Elf64_Phdr *)((char *)h + h->e_phoff); for (int i = 0; i < h->e_phnum; i++) { Elf64_Phdr *p = &pht[i]; if (p->p_type == PT_LOAD) { // Memory map region uintptr_t map_beg = ROUND(p->p_vaddr, p->p_align); uintptr_t map_end = map_beg + p->p_memsz; while (map_end % p->p_align != 0) map_end++; // Memory map flags int prot = 0; if (p->p_flags & PF_R) prot |= PROT_READ; if (p->p_flags & PF_W) prot |= PROT_WRITE; if (p->p_flags & PF_X) prot |= PROT_EXEC; // Memory map size int map_sz = p->p_filesz + (p->p_vaddr % p->p_align); while (map_sz % p->p_align != 0) map_sz++; // Map file contents to memory void *ret = mmap( (void *)map_beg, // addr, rounded to ALIGN map_sz, // length prot, // protection MAP_PRIVATE | MAP_FIXED, // flags, private & strict fd, // file descriptor ROUND(p->p_offset, p->p_align) // offset ); assert(ret != MAP_FAILED); // Map extra anonymous memory (e.g., bss) intptr_t extra_sz = p->p_memsz - p->p_filesz; if (extra_sz > 0) { uintptr_t extra_beg = map_beg + map_sz; ret = mmap( (void *)extra_beg, extra_sz, prot, // addr, length, protection MAP_ANONYMOUS | MAP_PRIVATE | MAP_FIXED, // flags -1, 0 // no file ); assert(ret != MAP_FAILED); } } } close(fd); static char stack[STK_SZ], rnd[16]; void *sp = (void *)ROUND(stack + sizeof(stack) - 4096, 16); void *sp_exec = sp; int argc = 0; // argc while (argv[argc]) argc++; push(sp, intptr_t, argc); // argv[], NULL-terminate for (int i = 0; i <= argc; i++) push(sp, intptr_t, argv[i]); // envp[], NULL-terminate for (; *envp; envp++) { if (!strchr(*envp, '_')) // remove some verbose ones push(sp, intptr_t, *envp); } // auxv[], AT_NULL-terminate push(sp, intptr_t, 0); push(sp, Elf64_auxv_t, { .a_type = AT_RANDOM, .a_un.a_val = (uintptr_t)rnd } ); push(sp, Elf64_auxv_t, { .a_type = AT_NULL } ); asm volatile( "mov $0, %%rdx;" // required by ABI "mov %0, %%rsp;" "jmp *%1" : : "a"(sp_exec), "b"(h->e_entry)); } int main(int argc, char *argv[], char *envp[]) { if (argc < 2) { fprintf(stderr, "Usage: %s file [args...]\n", argv[0]); exit(1); } execve_(argv[1], argv + 1, envp); }

• 当一个程序中引用了声明过但是尚未定义的函数的时候，原始程序

  • 
  • 编译结果
  • 
  • 在readelf中可以看到需要重定位的部分
  • 

    动态链接

• 拆解应用程序的需求

• 将运行库和程序代码分离

  • 

• 静态链接的程序很大，动态链接较小

• 方便通过升级库的方式来实现升级，而不需要一旦升级就整个编译所有程序

• 同时还可以实现部分程序的重新编译，其他程序与之链接即可，不需要重新编译

• 类似地，遇到调用声明过但是没有定义的函数的时候，运行时会存在一个位置需要将其地址修改为函数定义的位置

  • 编译器将一个现在未知的地址翻译为一个动态的位置

  • 

  • DSYM是动态的位置

  • 前半部分是需要加载的库和符号

    • DSYM需要一张表，从名字映射到地址

  • dl.h

    #define REC_SZ 32 #define DL_MAGIC "\x01\x14\x05\x14" #ifdef __ASSEMBLER__ #define DL_HEAD __hdr: \ /* magic */ .ascii DL_MAGIC; \ /* file_sz */ .4byte (__end - __hdr); \ /* code_off */ .4byte (__code - __hdr) #define DL_CODE .fill REC_SZ - 1, 1, 0; \ .align REC_SZ, 0; \ __code: #define DL_END __end: #define RECORD(sym, off, name) \ .align REC_SZ, 0; \ sym .8byte (off); .ascii name #define IMPORT(sym) RECORD(sym:, 0, "?" #sym "\0") #define EXPORT(sym) RECORD( , sym - __hdr, "#" #sym "\0") #define LOAD(lib) RECORD( , 0, "+" lib "\0") #define DSYM(sym) *sym(%rip) #else #include <stdint.h> struct dl_hdr { char magic[4]; uint32_t file_sz, code_off; }; struct symbol { int64_t offset; char type, name[REC_SZ - sizeof(int64_t) - 1]; }; #endif

• dlbox.c

  #include <stdio.h> #include <string.h> #include <assert.h> #include <stdint.h> #include <stdlib.h> #include <stdbool.h> #include <unistd.h> #include <sys/mman.h> #include <fcntl.h> #include "dl.h" #define SIZE 4096 #define LENGTH(arr) (sizeof(arr) / sizeof(arr[0])) struct dlib { struct dl_hdr hdr; struct symbol *symtab; // borrowed spaces from header const char *path; }; static struct dlib *dlopen(const char *path); struct dlib *dlopen_chk(const char *path) { struct dlib *lib = dlopen(path); if (!lib) { fprintf(stderr, "Not a valid dlib file: %s.\n", path); exit(1); } return lib; } // Implementation of binutils void dl_gcc(const char *path) { char buf[256], *dot = strrchr(path, '.'); if (dot) { *dot = '\0'; sprintf(buf, "gcc -m64 -fPIC -c %s.S && " "objcopy -S -j .text -O binary %s.o %s.dl", path, path, path); system(buf); } } void dl_readdl(const char *path) { struct dlib *h = dlopen_chk(path); printf("DLIB file %s:\n\n", h->path); for (struct symbol *sym = h->symtab; sym->type; sym++) { switch (sym->type) { case '+': printf(" LOAD %s\n", sym->name); break; case '?': printf(" EXTERN %s\n", sym->name); break; case '#': printf( "%08lx %s\n", sym->offset, sym->name); break; } } } void dl_objdump(const char *path) { struct dlib *h = dlopen_chk(path); char *hc = (char *)h, cmd[64]; FILE *fp = NULL; printf("Disassembly of binary %s:\n", h->path); for (char *code = hc + h->hdr.code_off; code < hc + h->hdr.file_sz; code++) { for (struct symbol *sym = h->symtab; sym->type; sym++) { if (hc + sym->offset == code) { int off = code - hc - h->hdr.code_off; if (fp) pclose(fp); sprintf(cmd, "ndisasm - -b 64 -o 0x%08x\n", off); fp = popen(cmd, "w"); printf("\n%016x <%s>:\n", off, sym->name); fflush(stdout); } } if (fp) fputc(*code, fp); } if (fp) pclose(fp); } // binutils: interpreter void dl_interp(const char *path) { struct dlib *h = dlopen_chk(path); int (*entry)() = NULL; for (struct symbol *sym = h->symtab; sym->type; sym++) if (strcmp(sym->name, "main") == 0) entry = (void *)((char *)h + sym->offset); if (entry) { exit(entry()); } } struct cmd { const char *cmd; void (*handler)(const char *path); } commands[] = { { "gcc", dl_gcc }, { "readdl", dl_readdl }, { "objdump", dl_objdump }, { "interp", dl_interp }, { "", NULL }, }; int main(int argc, char *argv[]) { if (argc < 3) { fprintf(stderr, "Usage: %s {gcc|readdl|objdump|interp} FILE...\n", argv[0]); return 1; } for (struct cmd *cmd = &commands[0]; cmd->handler; cmd++) { for (char **path = &argv[2]; *path && strcmp(argv[1], cmd->cmd) == 0; path++) { if (path != argv + 2) printf("\n"); cmd->handler(*path); } } } // Implementation of dlopen() static struct symbol *libs[16], syms[128]; static void *dlsym(const char *name); static void dlexport(const char *name, void *addr); static void dlload(struct symbol *sym); static struct dlib *dlopen(const char *path) { struct dl_hdr hdr; struct dlib *h; int fd = open(path, O_RDONLY); if (fd < 0) goto bad; if (read(fd, &hdr, sizeof(hdr)) < sizeof(hdr)) goto bad; if (strncmp(hdr.magic, DL_MAGIC, strlen(DL_MAGIC)) != 0) goto bad; h = mmap(NULL, hdr.file_sz, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE, fd, 0); if (h == (void *)-1) goto bad; h->symtab = (struct symbol *)((char *)h + REC_SZ); h->path = path; for (struct symbol *sym = h->symtab; sym->type; sym++) { switch (sym->type) { case '+': dlload(sym); break; // (recursively) load case '?': sym->offset = (uintptr_t)dlsym(sym->name); break; // resolve case '#': dlexport(sym->name, (char *)h + sym->offset); break; // export } } return h; bad: if (fd > 0) close(fd); return NULL; } static void *dlsym(const char *name) { for (int i = 0; i < LENGTH(syms); i++) if (strcmp(syms[i].name, name) == 0) return (void *)syms[i].offset; assert(0); } static void dlexport(const char *name, void *addr) { for (int i = 0; i < LENGTH(syms); i++) if (!syms[i].name[0]) { syms[i].offset = (uintptr_t)addr; // load-time offset strcpy(syms[i].name, name); return; } assert(0); } static void dlload(struct symbol *sym) { for (int i = 0; i < LENGTH(libs); i++) { if (libs[i] && strcmp(libs[i]->name, sym->name) == 0) return; // already loaded if (!libs[i]) { libs[i] = sym; dlopen(sym->name); // load recursively return; } } assert(0); }

• 多次依赖的库只会加载一次

  位置无关代码

• 

• 将定位从绝对位置更改为相对pc指针的位置，防止不同模块重叠地址

• 每一段代码除了代码和数据之外还有一个TABLE

  • 

• 引用外部函数的时候，先访问TABLE上对应的位置，再从此处查到真正的位置

• 

  • C语言代码的角度无法区分这两者的区别
  • 外部库的调用没有内部那么频繁
  • 
  • 实际上只有涉及外部调用的时候才会查表，程序执行的都是都是CALL
  • 
    • 以上是真正查表的位置

虚拟地址空间映射

• 
• 操作系统对于只读的代码，只分配一次内存，不会因为创建了多个副本就映射多次浪费内存
• fork()时对于虚拟地址的复制
  • 
  • 一个内存只要不写，就可以不复制
  • 只读的内存是不复制的

parfor中使用分支和循环语句的一些问题

• 参考链接
• 使用if语句和循环控制语句比如continue和break可能会有问题

如何控制进程的数量

• Cluster会默认指定一个最大的并行计算的上限，一般是CPU的物理核心数
  • 
  • 点击第三个更换
  • 
  • 点击此处可以修改默认值为自己需要的数值比如CPU的逻辑处理器的数量，可能是物理核心的2倍
• 然后使用如下代码设置线程的数量

  CoreNum=16; %设定机器CPU核心数量 if isempty(gcp('nocreate')) %如果并行未开启 parpool(CoreNum); end

• 终止的时候使用

  delete(gcp)

• 循环套循环的时候最好是内层循环是parfor

Linux操作系统

Linux Kernel

• 
• 初始化完了之后就会变成一个中断（系统调用）的处理工具
• systemd是所有进程的根进程

  构件最小的Linux系统

• initramfs：
  • 

    系统启动的第一个程序init

• busybox是Linux中所有工具的集合打包，可以变成ls, vi等等（使用busybox [程序名]）即可
  • 所有工具打包在一个二进制文件里
  • 功能较全面的工具包
  • 
  • 如何实现不需要手动打busybox就使用所有命令？

    for cmd in $($BB --list); do $BB ln -s $BB /bin/$cmd done mkdir -p /tmp mkdir -p /proc && mount -t proc none /proc mkdir -p /sys && mount -t sysfs none /sys mknod /dev/tty c 4 1 setsid /bin/sh </dev/tty >/dev/tty 2>&1

• 循环是将busybox支持的所有命令，以这个命令的名字作为文件名，创建一个符号链接到/bin下，这样的话就可以实现命令行直接使用，实际上文件都是busybox
  • busy如何知道是哪个命令调用的自己？
    • 每个命令行调用传入的第一个参数都是调用的名称
• 下面是挂载各种目录
• proc有所有进程的信息
• setsid:
  • 在新的会话中运行程序，也就是setsid命令 子进程从父进程继承了：SessionID、进程组ID和打开的终端。子进程如果要脱离这些，代码中可通过调用setsid来实现。，而命令行或脚本中可以通过使用命令setsid来运行程序实现。setsid帮助一个进程脱离从父进程继承而来的已打开的终端、隶属进程组和隶属的会话。
  • 给Linux内核传参rdinit=，即可修改启动的进程是init还是别的
• init执行后会调用pivot_root函数
• 
• /usr/sbin/init：
  • 
• 需要在此之前挂在好根文件系统，将需要放入内核的模块（比如驱动）放入并且启动，例如网卡驱动
• 创建完成之后再调换root，切换到systemd，进入正常的启动流程
• 
  • 第一句话是创建一个节点，主设备号是8次设备号是0，是磁盘
  • 第二句创建一个/newroot文件目录
  • 第三句将磁盘挂载到/newroot
  • 第四句switch root
• systemd执行完后续的初始化之后，再将系统的权限交给窗口管理器
• 窗口管理器完成用户界面的显示之后，将权限交给用户

  进程地址空间

  pmap

• pmap [进程号]得到进程地址空间中的内容
• 可以用gdb将一个程序暂停，使用info inferiors得到进程号，然后使用pmap得到空间内容
  • 
• 应用程序的内存是段组成的（带权限的连续的内存块）
  • 
  • 第一个4k只读，第二个4k可读可执行
  • 16k只读

    cat /proc/进程号/maps

• 
• 实际上pmap是通过读取/proc/进程号/maps实现的

操作系统API

• 操作系统是API+对象

• API+对象构成了内核

• 但是用户不太可能跟内核直接交互，所以需要一个shell方便交互

• bash中的``和 $()很多时候可以互换

• bash中可以使用<将命令行的输入重定向

  • 

• vim支持将某一个程序的输出直接作为文件编辑，-的意思是标准输入

  • 

• 使用vim <(ls)这句命令可以将ls的输出传递给vim

• 与ls | vim -效果类似

• shell支持程序前后台切换

  • 可以使用jobs命令查看
  • 使用fg %序号将这个程序切换回前台
  • 使用Ctrl Z将一个现在在前台的程序转移到后台并且暂停

• shell（或者bash）可以用-x选项在执行脚本文件的时候将脚本的执行过程打印出来，否则不容易调试

  shell实现管道

• 查看运行的进程打开的文件描述符

  • 

• 文件描述符

  • 0 —— stdin （标准输入）
  • 1 —— stdout （标准输出）
  • 2 —— stderr （标准错误）

// Linux port of xv6-riscv shell (no libc)

#include "lib.h"
#include <fcntl.h>

// Parsed command representation
enum { EXEC = 1, REDIR, PIPE, LIST, BACK };

#define MAXARGS 10
#define NULL ((void *)0)

struct cmd {
  int type;
};

struct execcmd {
  int type;
  char *argv[MAXARGS], *eargv[MAXARGS];
};

struct redircmd {
  int type, fd, mode;
  char *file, *efile;
  struct cmd* cmd;
};

struct pipecmd {
  int type;
  struct cmd *left, *right;
};

struct listcmd {
  int type;
  struct cmd *left, *right;
};

struct backcmd {
  int type;
  struct cmd* cmd;
};

struct cmd* parsecmd(char*);

// Execute cmd.  Never returns.
void runcmd(struct cmd* cmd) {
  int p[2];
  struct backcmd* bcmd;
  struct execcmd* ecmd;
  struct listcmd* lcmd;
  struct pipecmd* pcmd;
  struct redircmd* rcmd;

  if (cmd == 0) syscall(SYS_exit, 1);

  switch (cmd->type) {
    case EXEC:
      ecmd = (struct execcmd*)cmd;
      if (ecmd->argv[0] == 0) syscall(SYS_exit, 1);
      syscall(SYS_execve, ecmd->argv[0], ecmd->argv, NULL);
      print("fail to exec ", ecmd->argv[0], "\n", NULL);
      break;

    case REDIR:
      rcmd = (struct redircmd*)cmd;
      syscall(SYS_close, rcmd->fd);
      if (syscall(SYS_open, rcmd->file, rcmd->mode, 0644) < 0) {
        print("fail to open ", rcmd->file, "\n", NULL);
        syscall(SYS_exit, 1);
      }
      runcmd(rcmd->cmd);
      break;

    case LIST:
      lcmd = (struct listcmd*)cmd;
      if (syscall(SYS_fork) == 0) runcmd(lcmd->left);
      syscall(SYS_wait4, -1, 0, 0, 0);
      runcmd(lcmd->right);
      break;

    case PIPE:
      pcmd = (struct pipecmd*)cmd;
      assert(syscall(SYS_pipe, p) >= 0);
      if (syscall(SYS_fork) == 0) {
        syscall(SYS_close, 1);
        syscall(SYS_dup, p[1]);
        syscall(SYS_close, p[0]);
        syscall(SYS_close, p[1]);
        runcmd(pcmd->left);
      }
      if (syscall(SYS_fork) == 0) {
        syscall(SYS_close, 0);
        syscall(SYS_dup, p[0]);
        syscall(SYS_close, p[0]);
        syscall(SYS_close, p[1]);
        runcmd(pcmd->right);
      }
      syscall(SYS_close, p[0]);
      syscall(SYS_close, p[1]);
      syscall(SYS_wait4, -1, 0, 0, 0);
      syscall(SYS_wait4, -1, 0, 0, 0);
      break;

    case BACK:
      bcmd = (struct backcmd*)cmd;
      if (syscall(SYS_fork) == 0) runcmd(bcmd->cmd);
      break;

    default:
      assert(0);
  }
  syscall(SYS_exit, 0);
}

int getcmd(char* buf, int nbuf) {
  print("(sh-xv6) > ", NULL);
  for (int i = 0; i < nbuf; i++) buf[i] = '\0';

  while (nbuf-- > 1) {
    int nread = syscall(SYS_read, 0, buf, 1);
    if (nread <= 0) return -1;
    if (*(buf++) == '\n') break;
  }
  return 0;
}

void _start() {
  static char buf[100];

  // Read and run input commands.
  while (getcmd(buf, sizeof(buf)) >= 0) {
    if (buf[0] == 'c' && buf[1] == 'd' && buf[2] == ' ') {
      // Chdir must be called by the parent, not the child.
      buf[strlen(buf) - 1] = 0;  // chop \n
      if (syscall(SYS_chdir, buf + 3) < 0)
        print("cannot cd ", buf + 3, "\n", NULL);
      continue;
    }
    if (syscall(SYS_fork) == 0) runcmd(parsecmd(buf));
    syscall(SYS_wait4, -1, 0, 0, 0);
  }
  syscall(SYS_exit, 0);
}

// Constructors

struct cmd* execcmd(void) {
  struct execcmd* cmd;

  cmd = zalloc(sizeof(*cmd));
  cmd->type = EXEC;
  return (struct cmd*)cmd;
}

struct cmd* redircmd(struct cmd* subcmd, char* file, char* efile, int mode,
                     int fd) {
  struct redircmd* cmd;

  cmd = zalloc(sizeof(*cmd));
  cmd->type = REDIR;
  cmd->cmd = subcmd;
  cmd->file = file;
  cmd->efile = efile;
  cmd->mode = mode;
  cmd->fd = fd;
  return (struct cmd*)cmd;
}

struct cmd* pipecmd(struct cmd* left, struct cmd* right) {
  struct pipecmd* cmd;

  cmd = zalloc(sizeof(*cmd));
  cmd->type = PIPE;
  cmd->left = left;
  cmd->right = right;
  return (struct cmd*)cmd;
}

struct cmd* listcmd(struct cmd* left, struct cmd* right) {
  struct listcmd* cmd;

  cmd = zalloc(sizeof(*cmd));
  cmd->type = LIST;
  cmd->left = left;
  cmd->right = right;
  return (struct cmd*)cmd;
}

struct cmd* backcmd(struct cmd* subcmd) {
  struct backcmd* cmd;

  cmd = zalloc(sizeof(*cmd));
  cmd->type = BACK;
  cmd->cmd = subcmd;
  return (struct cmd*)cmd;
}

// Parsing

char whitespace[] = " \t\r\n\v";
char symbols[] = "<|>&;()";

int gettoken(char** ps, char* es, char** q, char** eq) {
  char* s;
  int ret;

  s = *ps;
  while (s < es && strchr(whitespace, *s)) s++;
  if (q) *q = s;
  ret = *s;
  switch (*s) {
    case 0:
      break;
    case '|': case '(': case ')': case ';': case '&': case '<':
      s++;
      break;
    case '>':
      s++;
      if (*s == '>') {
        ret = '+'; s++;
      }
      break;
    default:
      ret = 'a';
      while (s < es && !strchr(whitespace, *s) && !strchr(symbols, *s)) s++;
      break;
  }
  if (eq) *eq = s;

  while (s < es && strchr(whitespace, *s)) s++;
  *ps = s;
  return ret;
}

int peek(char** ps, char* es, char* toks) {
  char* s;

  s = *ps;
  while (s < es && strchr(whitespace, *s)) s++;
  *ps = s;
  return *s && strchr(toks, *s);
}

struct cmd* parseline(char**, char*);
struct cmd* parsepipe(char**, char*);
struct cmd* parseexec(char**, char*);
struct cmd* nulterminate(struct cmd*);

struct cmd* parsecmd(char* s) {
  char* es;
  struct cmd* cmd;

  es = s + strlen(s);
  cmd = parseline(&s, es);
  peek(&s, es, "");
  assert(s == es);
  nulterminate(cmd);
  return cmd;
}

struct cmd* parseline(char** ps, char* es) {
  struct cmd* cmd;

  cmd = parsepipe(ps, es);
  while (peek(ps, es, "&")) {
    gettoken(ps, es, 0, 0);
    cmd = backcmd(cmd);
  }
  if (peek(ps, es, ";")) {
    gettoken(ps, es, 0, 0);
    cmd = listcmd(cmd, parseline(ps, es));
  }
  return cmd;
}

struct cmd* parsepipe(char** ps, char* es) {
  struct cmd* cmd;

  cmd = parseexec(ps, es);
  if (peek(ps, es, "|")) {
    gettoken(ps, es, 0, 0);
    cmd = pipecmd(cmd, parsepipe(ps, es));
  }
  return cmd;
}

struct cmd* parseredirs(struct cmd* cmd, char** ps, char* es) {
  int tok;
  char *q, *eq;

  while (peek(ps, es, "<>")) {
    tok = gettoken(ps, es, 0, 0);
    assert(gettoken(ps, es, &q, &eq) == 'a');
    switch (tok) {
      case '<':
        cmd = redircmd(cmd, q, eq, O_RDONLY, 0);
        break;
      case '>':
        cmd = redircmd(cmd, q, eq, O_WRONLY | O_CREAT | O_TRUNC, 1);
        break;
      case '+':  // >>
        cmd = redircmd(cmd, q, eq, O_WRONLY | O_CREAT, 1);
        break;
    }
  }
  return cmd;
}

struct cmd* parseblock(char** ps, char* es) {
  struct cmd* cmd;

  assert(peek(ps, es, "("));
  gettoken(ps, es, 0, 0);
  cmd = parseline(ps, es);
  assert(peek(ps, es, ")"));
  gettoken(ps, es, 0, 0);
  cmd = parseredirs(cmd, ps, es);
  return cmd;
}

struct cmd* parseexec(char** ps, char* es) {
  char *q, *eq;
  int tok, argc;
  struct execcmd* cmd;
  struct cmd* ret;

  if (peek(ps, es, "(")) return parseblock(ps, es);

  ret = execcmd();
  cmd = (struct execcmd*)ret;

  argc = 0;
  ret = parseredirs(ret, ps, es);
  while (!peek(ps, es, "|)&;")) {
    if ((tok = gettoken(ps, es, &q, &eq)) == 0) break;
    assert(tok == 'a');
    cmd->argv[argc] = q;
    cmd->eargv[argc] = eq;
    assert(++argc < MAXARGS);
    ret = parseredirs(ret, ps, es);
  }
  cmd->argv[argc] = 0;
  cmd->eargv[argc] = 0;
  return ret;
}

// NUL-terminate all the counted strings.
struct cmd* nulterminate(struct cmd* cmd) {
  int i;
  struct backcmd* bcmd;
  struct execcmd* ecmd;
  struct listcmd* lcmd;
  struct pipecmd* pcmd;
  struct redircmd* rcmd;

  if (cmd == 0) return 0;

  switch (cmd->type) {
    case EXEC:
      ecmd = (struct execcmd*)cmd;
      for (i = 0; ecmd->argv[i]; i++) *ecmd->eargv[i] = 0;
      break;

    case REDIR:
      rcmd = (struct redircmd*)cmd;
      nulterminate(rcmd->cmd);
      *rcmd->efile = 0;
      break;

    case PIPE:
      pcmd = (struct pipecmd*)cmd;
      nulterminate(pcmd->left);
      nulterminate(pcmd->right);
      break;

    case LIST:
      lcmd = (struct listcmd*)cmd;
      nulterminate(lcmd->left);
      nulterminate(lcmd->right);
      break;

    case BACK:
      bcmd = (struct backcmd*)cmd;
      nulterminate(bcmd->cmd);
      break;
  }
  return cmd;
}

• 实际上的操作是使用一系列的syscall实现创建一个管道，将标准输出指向管道的输入，将标准输入指向管道的输出等等，从而将两个不同的进程通过管道连接起来
• 管道里的一切都是文本
• 上文中的p是指针（文件描述符）