历史的接口

IO 一直是件麻烦事．对冯诺依曼模型的计算机来说，IO 可以说是计算的开始和结束．因此 IO 十分麻烦，但异常重要．
高效的 IO 方式，是构建高效的应用程序必不可少的，更是计算机科学家与工程师们一直探讨的话题．

在本文中，笔者将简要的回顾 Linux Kernel 已有的 IO 接口．

注：本文不涉及 io_uring 的用法．如需了解 io_uring 的用法请直接查看本文参考资料．

同步接口

常见的 read、write 等 syscall 都是同步 IO 的接口．
read、write 类系统调用也衍生出了带有偏移量的接口 pread、pwrite 向量读写的接口 readv、writev 和具有两者特性的 preadv、pwritev，后来又出现为 preadv、pwritev 加上 flag 字段的 preadv2、pwritev2 接口．

说了这些，但究竟什么是同步？

同步接口最鲜明的特征就是应用程序：要么在执行应用程序中的用户代码；要么在因完成 IO．
听起来可能有人觉得模糊，请看下面这张图．同步 就是「IO 的完成」是在「请求执行 IO 的时候」（Y7n05h 嘴笨实在不知道该怎么组织语言解释了）

在图中：

• 紫色代表应用程序在执行用户代码
• 红色代表应用程序在完成 IO

我们可以看到，紫色块和红色块在时间上没有任何的重叠区域．完成 IO 不会和用户代码同时进行．

Y7n05h 猜测一定有读者想说，为什么都说了这么多了，没有提及 阻塞 和 非阻塞 哪怕一句．

这里请允许 Y7n05h 先说异步 IO．因为很多人把 非阻塞 和 异步 混为一谈．Y7n05h 认为先说明异步 IO 有助于理解这二者的概念．

异步接口

同步的反面是异步．

异步就是应用程序只需要提交一次 IO 的请求，由别的组件（通常是内核）来完成完成这次 IO，并在 IO 完成时告诉应用程序 IO 已经完成．

注：有经验的读者一定发现 Y7n05h 在此处刻意模糊了内核在 IO 中的作用，也未提及系统调用导致的陷入内核态等行为．这是为了使本文对异步的描述也适用于 ASIO 等用户态对异步 IO 的实现．

如下图：应用程序无需间断对代码的执行，只需要提交一次请求，即可静待别人（通常是内核）完成 IO．

对于异步 IO ：这就好比一个聪明的老板（类比应用程序）请了一个高明的助理，收发文书（类比 IO 行为）之类的事情，只需要老板吩咐一声，助理就好办妥当．助理办妥当后，告诉老板这件事办好了即可．老板只需要接着做自己的事（类比执行代码）．

对于同步 IO ：这就好比一个没有助理的老板（类比应用程序），收发文书（类比 IO 行为）之类的事情也得自己干．忙着收发文书就不能做自己的事情（类比执行代码）了．

阻塞与非阻塞

谈阻塞和非阻塞就一定谈谈内核了．
在 Linux 系统中，无论采用阻塞 IO 还是非阻塞 IO，若 IO 已经准备好了，那么会立刻返回．
阻塞和非阻塞的区别仅限于 IO 尚未准备就绪的情况下（例如写管道缓冲区已满、读 socket 但尚无数据到达）．这类场景，在在使用非阻塞 IO 的系统调用时，系统调用会立刻返回，并通过返回值和 errno 告诉调用者出现了错误．但若是使用阻塞 IO 的系统调用，则会继续等待制止 IO 完成．

Q：那么阻塞与否和同步、异步又有什么关系？
A：平日说的阻塞与非阻塞大多数情景是指同步阻塞和同步非阻塞．对于异步 IO 是否阻塞的问题，通常不做探讨．

为什么？那就要接着回顾 IO 接口的发展了．

众所周知，无论是网络 IO 还是硬盘 IO，其速度远低于 CPU 的运行速度．因此，等待 IO 浪费了应用程序原本可以执行很多事务的时间．追求高性能的应用程序自然不肯什么都不做静静的等待 IO 的发生．
在 Y7n05h 看来 同步非阻塞 的 IO 调用就是为了解决应用程序长时间等待 IO 浪费时间的问题．使用阻塞 IO 之后，应用程序自然可以过每过一小段时间尝试一次 IO 是否已经就绪，别的时间继续用来做别的事，这也就是是所谓的 轮询．
倘若一个 IO 密集型应用（例如一个服务器）那么可能需要同时处理大量的 IO 请求，当然遍历并轮询所有的 IO 是否就绪是一个做法．内核也提供了相关的设施用来完成遍历并轮询的操作（select、poll） ，但这在同步 IO 中也不是一个最好的做法．内核还提供了 epoll 这种机制，当内核通过中断机制得知有 IO 时间发生时通知应用程序．这样便避免了遍历之苦也提高了 IO 的效率．这也就是 IO 的多路复用了．

非阻塞 IO 的语义是：试一试，若能完成 IO 就完成；完不成就算了．

说了这么多，我想读者一定发现了：非阻塞 IO 无非是想提高 CPU 的利用率．

谈回异步，既然异步 IO 已经不可能卡住应用程序的代码了．那么阻塞与否就已经没了意义．
不但非阻塞在异步 IO 中没有意义，反而会制造麻烦．何处此言？因为非阻塞 IO 遇到 IO 未就绪时会直接返回．

回到之前老板请助理的例子．老板一定不会希望他请助理去送一份文件，仅仅是因为助理没找到收件人就回来向他报告失败，而是希望他去等收件人回来再把文件交给他．这才是一个聪明的助理．异步 IO 完美的符合了这一切的标准．

io_uring 一统天下

在 io_uring 出现之前，追求高性能 IO 的应用程序有这几种常见做法：

• 针对文件 IO 可采用 AIO 异步接口．
• epoll + 同步非阻塞．
• 使用类似 boost Asio 的方式，使用 IO 线程模拟异步接口．

但这几种方式都有自己的问题：

• AIO 仅支持文件 Direct IO．
• epoll + 同步非阻塞在大量连接的高并发场景中比 io_uring 有更高的开销和更高的延迟．
• boost Asio 与 io_uring 同为异步接口，但 io_uring 的在内核态的实现比在用户态基于多线程模拟异步 IO 更高效．
  可以说，AIO 被 io_uring 最主要是因为 AIO 的应用面太窄．而「epoll 同步非阻塞」和「boost Asio」被 io_uring 打败是因为 io_uring 的性能更好．

但 io_uring 并非没有缺点．

可移植性差．
这是 io_uring 的一个硬伤．io_uring 是 Linux 5.1 中加入的新接口．且 io_uring 还有部分特性在 5.6 才最终加入．因此想体验 io_uring 的一个相对完整的特性可能需要 Linux Kernel 5.6+．（虽然 Linux Kernel 5.6 中的 io_uring 已经相对完整了，但 Linux Kernel 5.10-5.15 中也为 io_uring 添加了更多的新特性）

接口复杂．
注意到了吗？io_uring 代替的是 「epoll + 同步非阻塞」而不仅仅是 epoll．为了支持各种 IO 调用，io_uring 通过庞大 struct io_uring_sqe 描述各种各样的 IO 请求．但 io_uring 接口的复杂性不仅仅体现在这里．io_uring_setup、io_uring_enter、io_uring_register 看似仅仅只有 3 个系统调用，但它们却都分别支持了十多个 flag 来改变系统调用的行为．

那么 io_uring 的性能为什么会好呢？

• 内核和用户态通过 mmap 共享 io_uring 相关的部分数据结构．
• 内核可以并行执行应用程序提交的 IO 请求．
• 节省系统调用次数．将 IO 请求放入提交队列（SQ）即可，无需通过中断陷入内核执行系统调用．

MoreInfo

本文到这里就结束了．读者可能会觉得有点突兀，但 Y7n05h 写本文的意愿本就不是去介绍 io_uring 的用法．本文仅仅是为了科普这几种不同的 IO 的方式的区别，区分 「阻塞」 与 「非阻塞」 这一对概念和 「同步」与「异步」这一堆概念．对于需要详细了解 io_uring 的读者，请看下面的 参考资料．

参考资料

¹. Efficient IO with io_uring.[G/OL].https://kernel.dk/io_uring.pdf. ↩

². What is io_uring?. [G/OL]. Lord of the io_uring, https://unixism.net/loti/what_is_io_uring.html. ↩

³. IO_URING(7). [G/OL]. Linux Programmer’s Manual, https://man.archlinux.org/man/io_uring.7. ↩

⁴. IO_URING_SETUP(2). [G/OL]. Linux Programmer’s Manual, https://man.archlinux.org/man/io_uring_setup.2. ↩

⁵. IO_URING_ENTER(2). [G/OL]. Linux Programmer’s Manual, https://man.archlinux.org/man/io_uring_enter.2. ↩

⁶. IO_URING_REGISTER(2). [G/OL]. Linux Programmer’s Manual, https://man.archlinux.org/man/io_uring_register.2. ↩

info
LICENSE
本文使用 GNU自由文档许可证1.3 发布．

secondary

致谢

• 感谢 VincilLau 指出本文的一处错误．
• 感谢 ZtXavier 指出本文的一处错误．
• 感谢 Celestial 指出本文的一处 Typo．

Arch Linux 安装指引

相信读者们早都听说过了 Arch Linux 的名声，笔者也从接触 Arch Linux 起就被他所具有的特性吸引．

本文中将讲述从 Arch Linux Live CD 中安装 Arch Linux 的方法．本文中假设读者已经完成了 下载、验证 Arch Linux 安装镜像以及将 Arch Linux 安装镜像写入物理介质并使用其介质以 UEFI 模式下完成引导，启动欲安装 Arch Linux 的设备的步骤．如有读者对该部分的操作方式存在疑问，请查阅 Installation guide 获得更多信息．

连接网络

Arch Linux 安装过程必须连接网络．在以 UEFI 模式启动至 Arch Linux 安装环境后，首先要做的便是连接网络．因在「Arch Linux 安装环境」中连接 WiFi 较为麻烦，笔者推荐一下两种方式在「 Arch Linux 安装环境」中连接网络，读者任选其一即可：

• 使用「网线」连接「设备」与「路由器」的 LAN 插口
• 使用「数据线」连接「设备」与「Android 手机」，并在「『系统设置』—『热点和网络共享』」中开启「USB 网络共享共享」

请读者在安装环境中使用

1

# ping archlinux.org

时间校准

在系统中开启时间同步服务：

1

# timedatectl set-ntp true

使用使用 timedatectl status 检查服务状态．
请在进行下一步前确保系统的时间正确．

建立硬盘分区

warn
WARNNING
本步骤中请勿直接套用本文中的命令．
在进行分区操作时，请仔细检查防止错误操作带来不良后果．

使用 lsblk 命令能清晰的看到目前电脑中的硬盘的分区情况．固态硬盘通常以 nvme 开头，机械硬盘通常以 sda 开头．请使用 cfdisk 工具，完成对硬盘的分区．
例如，如需对 /dev/sda 进行分区操作，请使用：

1

# cfdisk /dev/sda

1

# cfdisk /dev/nvme0n1

1. 需要注意的是 swap 即交换空间可以是一个分区（「swap 分区」）也可以是一个文件（「swap 文件」），甚至可以选择不需要 swap．如果读者的设备的内存足够大（例如：32 GB 或以上）那么通常不需要 swap．
2. 笔者十分推荐创建 home 分区，有了它读者在日后重新安装 GNU/Linux 操作系统的时候，就不再需要备份个人的数据，仅需要将 home 分区挂载即可．笔者使用 512 GB 的固态硬盘安装 Arch Linux，对 home 分区和 / 分区的存储空间分配是各占一半，home 分区稍多一些，/ 分区仅有 200 GB 但对笔者而言已经十分充足．
3. 在使用 cfdisk 时请通过界面下方的 Type 栏选择合适的类型（表中已注明）．

选择文件系统 格式化硬盘分区

warn
WARNNING
本步骤中请勿直接套用本文中的命令．
在进行格式化操作时，请仔细检查防止错误操作带来不良后果．

笔者推荐使用 ext4、xfs作为 / 或 home 的文件系统．

如果读者想尝试一下 COW ( Copy-On-Write ) 的文件系统的话，那也可以尝试一下 btrfs．

当然，选择文件系统时也需要充分的考虑文件系统所具有的各种特性和自身的需求，最终还请读者们理性选择．

如果读者不知道如何选择的话，那便使用 ext4 作为 / 或 home 的文件系统吧．

• 格式化 boot 分区，请将 /dev/nvme0nxpy 替换为 boot 分区的位置

  1	# mkfs.fat -F32 /dev/nvme0nxpy

• （如果没有swap分区则跳过）格式化swap分区，请将 请将 /dev/nvme0nxpy 替换为 swap 分区的位置

  1	# mkswap /dev/nvme0nxpy

请根据在上文中选择的文件系统，选择合适的格式化指令．请把 nvme0nxpy 替换成合适的名称．

• 选择 ext4 作为文件系统格式化 /dev/nvme0nxpy

  1	# mkfs.ext4 /dev/nvme0nxpy

• 选择 xfs 作为文件系统格式化 /dev/nvme0nxpy

  1	# mkfs.xfs /dev/nvme0nxpy

• 选择 btrfs 作为文件系统格式化 /dev/nvme0nxpy

  1	# mkfs.btrfs /dev/nvme0nxpy

  请选择合适的文件系统，并用相应的指令格式化「/ 分区」和「home 分区」（如果没有「home 分区」则不需要格式化「home 分区」）．

挂载

1. 挂载 / 分区 ．

   1	# mount /dev/nvme0nxpy /mnt

2. 创建 /boot

   1	# mkdir /mnt/boot

3. 挂载 boot 分区 ．

   1	# mount /dev/nvme0nxpy /mnt/boot

4. 如果读者创建了 swap 分区，那么请挂载 swap 分区

   1	# swapon /dev/nvme0nxpy

5. 如果读者创建了 home 分区，那么请创建 /home 目录

   1	# mkdir /mnt/home

6. 如果读者创建了 home 分区，那么请挂载 home 分区

   1	# mount /dev/nvme0nxpy /mnt/home

tip
TIP

选择 btrfs 作为文件系统的读者，可以考虑笔者在上面提供的方案．
也可以考虑使用 btrfs 的子卷管理功能，将 home 分区作为 btrfs 的子卷．

在使用 btrfs 前请读者务必查阅 Btrfs．

首先将格式化好的 btrfs 分区挂载至 /mnt，然后在创建子卷

1

mount /dev/nvme0nxpy /mnt

@ 子卷将作为新安装的系统的根目录， @home 将作为新安装的系统的 /home 目录．

创建 @ 子卷

1

btrfs subvolume create /mnt/@

创建 @home 子卷

1

btrfs subvolume create /mnt/@home

然后 umount /mnt
将刚才创建的 btrfs 的 @ 子卷 挂载至 /mnt

1

mount -o subvol=@ /dev/nvmen0nxpy /mnt

如果你还想启用透明压缩，那么可以使用（下面以使用 zstd 压缩算法作为演示）

1

mount -o compress=zstd,subvol=@ /dev/nvmen0nxpy /mnt

如需手动指定 zstd 压缩级别可使用（下面指定 zstd 压缩级别为 6 作为演示）：

1

mount -o compress=zstd:6,subvol=@ /dev/nvmen0nxpy /mnt

在 /mnt 下创建 home 文件夹

1

mkdir /mnt/home

将 @home 子卷挂载至 /mnt/home 并使用 zstd 并指定压缩级别为6级的透明压缩：

1

mount -o compress=zstd:6,subvol=@home /nvmen0nxpy /mnt/home

安装

编辑镜像源列表

文件 /etc/pacman.d/mirrorlist 定义了软件包会从哪个镜像源下载．[3]

Arch Linux 在安装过程中会下载大量的软件包，因此选择一个访问速度较快的镜像源是十分重要的．
在执行下载并安装的操作前请使用 nano(推荐) 或 vim 或其他的编辑器修改镜像源．
笔者在此推荐使用 nano ，因为其操作简便对新手更加友好．

1

# nano /etc/pacman.d/mirrorlist

注意：在修改的时候去掉表示内容是注释的#号，将访问速度最快的镜像源的行放在文件的最上面．/etc/pacman.d/mirrorlist 将被从前至后读取，写在前面的镜像源具有更高的优先级．

安装必要的软件包

在完成修改并保存后，请强制同步软件包的数据库．

1

# pacman -Syy

1

# pacstrap /mnt base base-devel linux linux-firmware linux-headers nano

生成 fstab

fstab 用来说明在启动过程中如何挂载硬盘分区．在 Arch Linux 上只需要简单的命令即可生成 fstab

1
2

# genfstab -U /mnt >> /mnt/etc/fstab

chroot

Chroot 就是变更当前进程及其子进程的可见根路径．变更后，程序无法访问可见根目录外文件和命令．这个目录叫作 chroot jail．[4]

1

# arch-chroot /mnt

本地化设置

以中国大陆的用户为例，这条语句在系统层面更改了时区的配置．

1

# ln -sf /usr/share/zoneinfo/Asia/Shanghai /etc/localtime

设置标准时间为世界协调时（UTC）．

1

# hwclock --systohc --utc

这里的配置影响「地域、货币、时区日期的格式、字符排列方式」等．只需要用文版编辑器打开它然后编辑并保存．

1

# nano /etc/locale.gen

需要作的是在文件中找到#en_US.UTF-8 UTF-8、#zh_CN.UTF-8 UTF-8、#zh_TW.UTF-8 UTF-8这三行，并删掉这三行中的#．
然后执行

1

# locale-gen

其后执行

1

# echo LANG=en_US.UTF-8 > /etc/locale.conf

设置主机名

1

# echo myhostname > /etc/hostname

安装引导程序

1

# pacman -S grub  efibootmgr dosfstools

有多系统的需求的读者还需要执行

1

# pacman -S os-prober

并且在 /etc/default/grub 中添加

1

GRUB_DISABLE_OS_PROBER=false

有安装多系统的需求，且多系统中含有 Microsoft Windows 操作系统的，可执行以便在 ArchLinux 中挂在 Microsoft Windows 中的 NTFS 文件系统的分区．

1

# pacman -S ntfs-3g

安装 grub 引导

1
2

# grub-install --target=x86_64-efi --efi-directory=/boot --bootloader-id=grub --recheck
# grub-mkconfig -o /boot/grub/grub.cfg

用户管理

首先配置 sudo，和上面一样，还是使用 nano 作为编辑的工具．但是这次打开方式与以往不太相同．

1

# EDITOR=nano visudo

1

# %wheel ALL=(ALL:ALL) ALL

设置 root 用户密码

1

# passwd

1

# useradd -m -G wheel username

1

# passwd username

配置 swap 文件

• 如果创建了 swap 分区，则跳过本节
• 如果设备的内存大于等于 32 GB，通常也该跳过本节的内容
  正如前文所说的那样： swap 可以是一个硬盘分区也可以是一个文件
  创建 swap 文件的方式本文不在说明，请查阅 Swap．

安装桌面环境

安装 KDE

1

# pacman -S plasma sddm

1

# systemctl enable sddm

安装字体

安装 Google Noto Fonts 字体

1

# pacman -S noto-fonts noto-fonts-cjk noto-fonts-emoji noto-fonts-extra

1

# pacman -S ttf-sarasa-gothic

安装网络管理器

1

# pacman -S networkmanager

启用网络管理器

1

# systemctl enable NetworkManager

启用 Arch Linux 中文社区仓库

使用 nano 编辑 /etc/pacman.conf 在

1
2

#[multilib]
#Include = /etc/pacman.d/mirrorlist

1
2

[archlinuxcn]
Server = https://repo.archlinuxcn.org/$arch

1
2

$ sudo pacman -Syy && sudo pacman -S archlinuxcn-keyring
$ sudo pacman -S archlinuxcn-mirrorlist-git

再次编辑 /etc/pacman.conf
将刚才加入的内容中的 Server = https://repo.archlinuxcn.org/$arch
修改为 Include = /etc/pacman.d/archlinuxcn-mirrorlist

编辑 /etc/pacman.d/archlinuxcn-mirrorlist
为 Arch Linux 中文社区 仓库选择你喜欢的镜像源．如何编辑镜像源请参照前文．

配置中文拼音输入法

安装 fcitx5-im、fcitx5-chinese-addons、fcitx5-pinyin-zhwiki

1

$ sudo pacman -S fcitx5-im fcitx5-chinese-addons fcitx5-pinyin-zhwiki

安装完编辑或创建 /etc/environment 添加以下内容：

1
2
3
4
5

GTK_IM_MODULE=fcitx
QT_IM_MODULE=fcitx
XMODIFIERS=@im=fcitx
SDL_IM_MODULE=fcitx
GLFW_IM_MODULE=ibus

在 fcitx5 配置中将 拼音 加入当前输入法．

使用蓝牙

在使用蓝牙前，请安装 bluez、bluez-utils、pulseaudio-bluetooth．

1
2
3
4

$ sudo pacman -S bluez bluez-utils pulseaudio-bluetooth
$ sudo modprobe btusb
$ sudo systemctl enable bluetooth.service
$ sudo systemctl start bluetooth.service

设置用户 locale

创建或编辑 ~/.config/locale.conf

1
2
3
4
5
6
7
8
9
10
11
12
13
14

LANG=zh_CN.UTF-8
LC_CTYPE="zh_CN.UTF-8"
LC_NUMERIC="zh_CN.UTF-8"
LC_TIME="zh_CN.UTF-8"
LC_COLLATE="zh_CN.UTF-8"
LC_MONETARY="zh_CN.UTF-8"
LC_MESSAGES="zh_CN.UTF-8"
LC_PAPER="zh_CN.UTF-8"
LC_NAME="zh_CN.UTF-8"
LC_ADDRESS="zh_CN.UTF-8"
LC_TELEPHONE="zh_CN.UTF-8"
LC_MEASUREMENT="zh_CN.UTF-8"
LC_IDENTIFICATION="zh_CN.UTF-8"
LC_ALL=

使用 zsh

1
2

$ sudo pacman -S zsh
$ sudo chsh -s /bin/zsh username

参考资料

¹. ArchWiki编者. Installation guide (简体中文)[G/OL]. ArchWiki, https://wiki.archlinux.org/index.php/Installation_guide_(简体中文). ↩

². ArchWiki编者. Installation guide[G/OL]. ArchWiki, https://wiki.archlinux.org/index.php/Installation_guide. ↩

³. ArchWiki编者. pacman (简体中文)[G/OL]. ArchWiki, https://wiki.archlinux.org/index.php/Pacman_(简体中文). ↩

⁴. ArchWiki编者. Chroot (简体中文)[G/OL]. ArchWiki, https://wiki.archlinux.org/index.php/Chroot_(简体中文). ↩

⁵. 约伊兹的萌狼乡手札.给 GNU/Linux 萌新的 Arch Linux 安装指南 rev.B[G/OL]. 约伊兹的萌狼乡手札, https://blog.yoitsu.moe/arch-linux/installing_arch_linux_for_complete_newbies.html. ↩

Bitset 和字节序

近日，笔者希望通过 Bitset 来完成部分繁琐的 bit 级 io 操作，在测试后发现 Bitset 与自己所想有较大的落差．最为重要的问题在于 Bitset 会受到字节序的影响．

字节序

请在继续阅读本文前回想字节序的相关知识．一个多字节的对象将被存储在连续的内存中，但存储的顺序需要区分「小端序」与「大端序」．
例如：一个 4 字节的整形变量 0x12345678 以小端序存储在内存中的存储方法是 0x78 0x56 0x34 0x12（按照每个字节的地址递减顺序排列），而以大端序存储的方式是 0x12 0x34 0x56 0x78（按照每个字节的地址递减顺序排列）．
换句话说：

• 小端序：数据的低位字节存储在变量的高位地址
• 大端序：数据的高位字节存储在变量的低位地址

日常中，广泛使用的 x86_64 架构采取小端序存储变量．

Bitset

Bitset 中（但不限）以下成员是笔者将在本文中着重讨论的：

• 构造函数 constexpr bitset( unsigned long long val ) noexcept;
• to_ulong()、to_ullong()
• to_string()

下标 与 to_ulong()、to_ullong()

请在考虑这个问题的时候不要忽略字节序的问题．
在进行测试之前，笔者认为 bitset<64> 的下标将与一个 uint64_t 进行从高位至低位或者从低位至高位的依次对应．
但 bitset 的却按照字节序和二进制运算中进位顺序排列．
例如：
std::bitset<32> test(0x12345678); 在内存中存储的值实际上是 01111000 01010110 00110100 00010010，而且其为 true 的值对应的下标是 3、4、5、6、9、10、12、14、18、20、21、25、28．这与笔者的预期完全不符．也就是说 bitset 的编号顺序为：7、6、5、4、3、2、1、0、15、14、13、12、11、10、9、8、23、22、21、20、19、18、17、16、31、30、29、28、27、26、25、24、39、38、37、36、35、34、33、32、47、46、45、44、43、42、41、40、55、54、53、52、51、50、49、48、63、62、61、60、59、58、57、56……．
依笔者之见，这种编号顺序极难满足通常的需求．

对于一个 uint64_t 而言，笔者将其最高位（即 uint64_t中表示 2^7 的 bit）记为第0位按照内存中的顺序依次编号即可通过 8 * (i / 8 * 2 + 1) - 1 - i 将其笔者对 bit 的编号 i 转换为 bitset 的正确下标．

下标与 to_string

回顾刚才的例子：

1
2

std::bitset<32> test(0x12345678);
std::cout << test << std::endl;

测试环境

• OS: Arch Linux
• Kernel: 5.11.7
• GCC: 10.2.0
• clang: 11.1.0

众所周知，计算机程序在开发过程中不出现 Bugs 是困难的，随着程序设计的日益复杂，「Bug Free」也才成为了一种可贵的能力．「Bug Free」通常是困难的，也离不开长期努力的学习和练习．期待先达成「Bug Free」，再开始写程序是不切实际的幻想，Bugs 又必须修复，故此才体现了调试的价值．

Lint

静态分析工具是开发时的良师，静态分析工具常常能在开发过程中发现许多错误或疑似错误问题，并给出 error 或 warning．

有很多自由且功能强大的工具能提供 C/C++ 代码静态分析(按照名称升序排列)：

• Clang-Tidy
• cppcheck
• Flawfinder
• Lizard

当然，编译器在编译代码时，也能提供有关代码错误和警告信息．

静态分析工具常常可通过插件或扩展等方式与 IDE 整合，在开发过程中，自动分析代码错误，并及时修改．静态分析工具不仅能分析代码中的错误，还能给出有关可读性的建议，能促使开发者规范的编码．

需要注意的是：不必「过分的讨好」静态分析工具，只要开发者确认静态分析工具给出了错误的信息，那么请坚持自己的做法，并在静态分析工具中禁用相关 checks．

动态分析

Sanitizers

Google 与 LLVM 为开发者提供了一套内置于 clang 内的动态分析工具用于检测众多代码问题．

• AddressSanitizer:detects addressability issues
• LeakSanitizer:detects memory leaks
• ThreadSanitizer:detects data races and deadlocks
• MemorySanitizer:detects use of uninitialized memory
• Hardware-assisted AddressSanitizer:a newer variant of AddressSanitizer thatconsumes - much less memory
• UndefinedBehaviorSanitizer[1]

Thread Safety Analysis

线程安全的问题时常让人苦恼，虽然编写线程安全的 C/C++ 程序算是 C/C++ 开发者的一项基本功，但时常出现的线程不安全与条件竞争也让人防不胜防．

ThreadSafetyAnalysis

Clang Thread Safety Analysis is a C++ language extension which warns about potential race conditions in code. The analysis is completely static (i.e. compile-time); there is no run-time overhead. The analysis is still under active development, but it is mature enough to be deployed in an industrial setting. It is being developed by Google, in collaboration with CERT/SEI, and is used extensively in Google’s internal code base.

Thread safety analysis works very much like a type system for multi-threaded programs. In addition to declaring the type of data (e.g. int, float, etc.), the programmer can (optionally) declare how access to that data is controlled in a multi-threaded environment. For example, if foo is guarded by the mutex mu, then the analysis will issue a warning whenever a piece of code reads or writes to foo without first locking mu. Similarly, if there are particular routines that should only be called by the GUI thread, then the analysis will warn if other threads call those routines.[3]

Valgrind

valgrind

Valgrind is an instrumentation framework for building dynamic analysis tools. There are Valgrind tools that can automatically detect many memory management and threading bugs, and profile your programs in detail. You can also use Valgrind to build new tools.

The Valgrind distribution currently includes seven production-quality tools: a memory error detector, two thread error detectors, a cache and branch-prediction profiler, a call-graph generating cache and branch-prediction profiler, and two different heap profilers. It also includes an experimental SimPoint basic block vector generator. It runs on the following platforms: X86/Linux, AMD64/Linux, ARM/Linux, ARM64/Linux, PPC32/Linux, PPC64/Linux, PPC64LE/Linux, S390X/Linux, MIPS32/Linux, MIPS64/Linux, X86/Solaris, AMD64/Solaris, ARM/Android (2.3.x and later), ARM64/Android, X86/Android (4.0 and later), MIPS32/Android, X86/Darwin and AMD64/Darwin (Mac OS X 10.12).

• memcheck：内存错误检查
• cachegrind：缓存使用
• callgrind：函数调用
• dhat
• drd
• exp-bbv
• getoff
• helgrind
• lackey：资源泄漏
• massif

网络分析

网络相关的错误常常可以使用 Wireshark 进行调试，Wireshark能直观的查看程序发送或接受的数据，能够为调试带来很多的便利．
Netcat 则是常见的测试工具，方便在终端下直接操作 socket．

• Wireshark
• GNU Netcat
• netcat-openbsd

单元测试

单元测试是一种良好的测试 API 的方式，在编码阶段即可通过单元测试检查 API 是否满足预期．

C:

• CUnit

C++：

• Boost.Test
• GoogleTest

日志

对于一个复杂的软件系统，常常需要在长期在后台静默的运行，那么日志的输出就十分重要，日志也常常被用来定位系统中的 Bugs，高效的记录日志对调试有很大的帮助．

• spdlog:Very fast, header-only/compiled, C++ logging library.
• Google Logging Library:Google Logging (glog) is a C++98 library that implements application-level logging. The library provides logging APIs based on C++-style streams and various helper macros.

Debuger

有时面对的问题是复杂的，调试器也是解决问题的利器．

• GDB
• LLDB

参考资料

¹. google/sanitizers:AddressSanitizer, ThreadSanitizer, MemorySanitizer [G/OL]. https://github.com/google/sanitizers. ↩

². Clang 13 documentation [G/OL]. https://clang.llvm.org/docs/. ↩

³. Thread Safety Analysis [G/OL]. https://clang.llvm.org/docs/ThreadSafetyAnalysis.html. ↩

x86_64 函数调用

本文将讨论 x86_64 平台的函数调用过程，简要介绍部分常见的调用约定．阅读本文需要读者对 x86_64 汇编语言有一些基本的了解．

本文只讨论「长度不大于 64 bit 的整数类型」与「指针类型」作为函数参数、返回值时传递的方式，不涉及「长度大于 64 bit 的整数类型参数」与结构体、浮点数等类型的传递方式．

本文代码为了展示函数调用与返回过程中的汇编语言实现，引入了大量无意义、冗余的代码，本文代码不能作为学习编程语言中写法的推荐或参考．

前置知识

栈

相信很多人都遇到过因函数的递归次数过多，导致程序运行时出现栈溢出的问题．这个溢出的「栈」是本文要关注的重点，函数调用的过程和它密不可分．
栈从高地址向低地址增长．

info
INFO
无特殊说明时，本文中说提及的「栈」均指代程序的「调用栈」或者说「运行时栈」，而不是指数据结构中的「堆栈」．

PUSH

PUSH 操作类似数据结构中的「堆栈」 ．
PUSH 指令总是

1. 递减 rsp
   
2. 将 PUSH 的值存储在 rsp 递减后指向的位置
   
   笔者说明 PUSH 过程意在强调：在 PUSH 操作中， rsp 指向的是最后一个数据的位置，而不是指向栈上待写入数据的位置．
   简单的说：rsp 总是指向有效的数据．

POP

POP 操作与 PUSH 操作相对应．
POP 指令总是：

1. 将栈顶的值取出
2. 递增 rsp
   

tip
TIP
栈顶：当前 rsp 指向的值．

LEAVE

LEAVE 操作是等价于

1
2

mov %rbp , %rsp
pop %rbp

1. 通过执行 mov %rbp , %rsp（rsp = rbp），恢复 rsp 至执行 CALL 后的位置．
2. 通过执行 pop %rbp，恢复 rbp 至原来的栈底．

无返回值与参数的「函数调用与返回过程」

本小节将说明函数无参数、无返回值的函数调用与返回的过程．请读者们将关注点集中理解在函数调用的流程上，不必过多的关注具体的细节．

首先，尝试写出简单的函数调用的示例．

1
2
3
4
5
6
7
8
9

/* call1.c */
void func1()
{
    int v = 0;
}
int main(void)
{
    func1();
}

查看该程序的反汇编代码：
以下代码由 clang 生成并使用 objdump 反编译获得，笔者已删去其中的次要部分（删节部分并未全部标注）．（后同）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

<func1>:
push   %rbp
mov    %rsp,%rbp
sub    $0x10,%rsp
;此处有删节
leave
ret

<main>:
;此处有删节
call   1147 <func1>
mov    $0x0,%eax
pop    %rbp
ret

首先请关注由 main() 到 func1() 的调用过程．

• 在 main()，执行 call 1147 <func1> 就完成了对 func1 的调用．call 将 main() 中下一条语句的地址（也就是「mov $0x0,%eax」这句的地址）压入栈中并修改 rip 的值为 func1() 的地址．
  
• 在 func1()，通过将 rbp 压栈的方式，保存 rbp．
  

tip
TIP
笔者特意删节掉了关于 rbp 里面的值的部分．
也请读者暂时不要关注在执行 call 1147 <func1> 时 rbp 的值是多少．
请读者暂且记住此时 rbp 指向栈的某一个位置，而且 rbp < rsp 即可．

1. 通过执行 mov %rsp,%rbp（rbp = rsp），原来的栈底（rbp 指向的位置）成为了新的栈顶（rsp 指向的位置）

此时调用函数 func1() 的过程结束．现在关注如何从 func1() 返回至 main()．

1. 函数返回时，使用 LEAVE 恢复了先前保存栈底．
   
2. 使用 ret 根据 rsp 指向的位置从栈中弹出 返回位置，并通过修改 rip的值为 返回地址 完成了函数的返回．
   

有返回值和参数的「函数调用与返回过程」上

无返回值与参数的「函数调用与返回过程」可以看作本节要讨论的 有返回值和参数的「函数调用与返回过程」的一种简化情况．

和上一节一样，研究一个简单的函数示例对理解该过程有帮助．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/* call2.c */
void func1()
{
}
int func2(int a, long b, char *c)
{
    *c = a * b;
    func1();
    return a * b;
}
int main()
{
    char value;
    int rc = func2(1, 2, &value);
}

反汇编后得到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

<func1>:
push   %rbp
mov    %rsp,%rbp
pop    %rbp
ret

<func2>:
push   %rbp
mov    %rsp,%rbp
sub    $0x20,%rsp
mov    %edi,-0x4(%rbp)
mov    %rsi,-0x10(%rbp)
mov    %rdx,-0x18(%rbp)
movslq -0x4(%rbp),%rax
imul   -0x10(%rbp),%rax
mov    -0x18(%rbp),%rcx
mov    %al,(%rcx)
call   1140 <func1>
movslq -0x4(%rbp),%rcx
imul   -0x10(%rbp),%rcx
mov    %ecx,%eax
add    $0x20,%rsp
pop    %rbp
ret

<main>:
push   %rbp
mov    %rsp,%rbp
sub    $0x10,%rsp
mov    %fs:0x28,%rax
mov    %rax,-0x8(%rbp)
mov    $0x1,%edi
mov    $0x2,%esi
lea    -0x9(%rbp),%rdx
call   1150 <func2>
mov    %eax,-0x10(%rbp)
mov    %fs:0x28,%rcx
mov    -0x8(%rbp),%rdx
cmp    %rdx,%rcx
jne    11d9 <main+0x49>
xor    %eax,%eax
add    $0x10,%rsp
pop    %rbp
ret

可以清晰的看到，在执行 call 1140 <func2> 之前 main() 进行了如下操作：

1
2
3

mov    $0x1,%edi
mov    $0x2,%esi
lea    -0x9(%rbp),%rdx

事实上，这三条语句意在进行参数的传递．在进行函数调用时，主调函数将参数存储在寄存器中，在被调函数中直接使用，通过这样的方式传递参数．

观察函数调用的实参 1, 2, &value，可以看到：

• 1 使用 rdi 的低 32 位，也就是 edi 来传递．
• 2 使用 rsi 的低 32 位，也就是 esi 来传递．
• &value 使用 rdx 进行传递．

值得注意的是：即使 &value 的类型是指针，与 整型变量 看似不同，但在传递方式上并无差异．

这是 func2() 的尾部代码片段：

1
2
3
4
5

imul   -0x10(%rbp),%rcx
mov    %ecx,%eax
add    $0x20,%rsp
pop    %rbp
ret

1
2

call   1150 <func2>
mov    %eax,-0x10(%rbp)

请看，此处 eax 中仍是 func2() 中计算的 a * b 的值，但在 main() 却进行了读取．这不就是从 被调函数 中传送给主调函数的值吗？是的，rax 寄存器常常被用来传递返回值．

讨论完了返回值与参数，此时再来看看 func2() 的调用流程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

<func2>:
push   %rbp
mov    %rsp,%rbp
sub    $0x20,%rsp
mov    %edi,-0x4(%rbp)
mov    %rsi,-0x10(%rbp)
mov    %rdx,-0x18(%rbp)
movslq -0x4(%rbp),%rax
imul   -0x10(%rbp),%rax
mov    -0x18(%rbp),%rcx
mov    %al,(%rcx)
call   1140 <func1>
movslq -0x4(%rbp),%rcx
imul   -0x10(%rbp),%rcx
mov    %ecx,%eax
add    $0x20,%rsp
pop    %rbp
ret

相信不难注意到：sub $0x20,%rsp．前文提及过，栈是由高地址向低地址的方向增长的．rsp 减少 0x20 意味着栈增长 0x20．那么栈为什么需要增长呢？因为需要在栈上为 func2() 的局部变量或临时的变量等分配空间．与 sub $0x20,%rsp 对应的操作是 add $0x20,%rsp 在函数返回前需要增加 rsp 以释放栈上的空间．其余步骤与 无返回值与参数的「函数调用与返回过程」 所述并无实质差异，此处不再赘述．

有返回值和参数的「函数调用与返回过程」下

前面的小节中，描述了函数参数较少的情况下参数传递的方式．本节则将关注较多的参数将为函数的调用带来什么变化．
本节采取的示例拥有 10 个参数．

1
2
3
4
5
6
7
8
9
10
11
12
13

/* call3.c */
void func1()
{
}
int func3(int a, int b, int c, int d, int e, int f, int g, int h, int i, int j)
{
    func1();
    return a * 1 + b * 2 + c * 3 + d * 4 + e * 5 + f * 6 + g * 7 + h * 8 + i * 9 + j * 10;
}
int main()
{
    func3(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
}

反汇编得到了较长的汇编代码．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

<func1>:
push   %rbp
mov    %rsp,%rbp
pop    %rbp
ret

<func3>:
push   %rbp
mov    %rsp,%rbp
push   %rbx
sub    $0x28,%rsp
mov    0x28(%rbp),%eax
mov    0x20(%rbp),%r10d
mov    0x18(%rbp),%r11d
mov    0x10(%rbp),%ebx
mov    %edi,-0xc(%rbp)
mov    %esi,-0x10(%rbp)
mov    %edx,-0x14(%rbp)
mov    %ecx,-0x18(%rbp)
mov    %r8d,-0x1c(%rbp)
mov    %r9d,-0x20(%rbp)
mov    %eax,-0x24(%rbp)
mov    %r10d,-0x28(%rbp)
mov    %r11d,-0x2c(%rbp)
mov    %ebx,-0x30(%rbp)
call   1120 <func1>
mov    -0xc(%rbp),%eax
shl    $0x0,%eax
mov    -0x10(%rbp),%ecx
shl    $0x1,%ecx
add    %ecx,%eax
imul   $0x3,-0x14(%rbp),%ecx
add    %ecx,%eax
mov    -0x18(%rbp),%ecx
shl    $0x2,%ecx
add    %ecx,%eax
imul   $0x5,-0x1c(%rbp),%ecx
add    %ecx,%eax
imul   $0x6,-0x20(%rbp),%ecx
add    %ecx,%eax
imul   $0x7,0x10(%rbp),%ecx
add    %ecx,%eax
mov    0x18(%rbp),%ecx
shl    $0x3,%ecx
add    %ecx,%eax
imul   $0x9,0x20(%rbp),%ecx
add    %ecx,%eax
imul   $0xa,0x28(%rbp),%ecx
add    %ecx,%eax
add    $0x28,%rsp
pop    %rbx
pop    %rbp
ret
<main>:
push   %rbp
mov    %rsp,%rbp
sub    $0x30,%rsp
mov    $0x1,%edi
mov    $0x2,%esi
mov    $0x3,%edx
mov    $0x4,%ecx
mov    $0x5,%r8d
mov    $0x6,%r9d
movl   $0x7,(%rsp)
movl   $0x8,0x8(%rsp)
movl   $0x9,0x10(%rsp)
movl   $0xa,0x18(%rsp)
call   1130 <func3>
xor    %ecx,%ecx
mov    %eax,-0x4(%rbp)
mov    %ecx,%eax
add    $0x30,%rsp
pop    %rbp
ret

笔者首先关注的是 main() 的这个部分：

1
2
3
4
5
6
7
8
9
10
11

mov    $0x1,%edi
mov    $0x2,%esi
mov    $0x3,%edx
mov    $0x4,%ecx
mov    $0x5,%r8d
mov    $0x6,%r9d
movl   $0x7,(%rsp)
movl   $0x8,0x8(%rsp)
movl   $0x9,0x10(%rsp)
movl   $0xa,0x18(%rsp)
call   1130 <func3>

可以发现．在进行参数的传递时，第 1 个参数（从 1 开始计数）至第 6 个参数分别采用 rdi、rsi、rdx、rcx、r8、r9 这 6 个寄存器对应的低 32 位部分．而剩余的 4 个参数采取了压栈的方式进行传递．

x86-64 调用约定

首先，笔者要声明的是：调用约定与设备的 ABI（application binary interface）有关，而 ABI 依赖「硬件特性」与「操作系统」．在 x86-64 上也不只有一种调用约定．

Microsoft x64 calling convention

这张表展示了 Microsoft x64 calling convention 的部分内容，笔者展示这张表的目的不在于向读者介绍 Microsoft x64 calling convention 的具体内容，仅仅是为了说明调用约定不止一种．当遇到与笔者接下来介绍的 System V AMD64 ABI 不同的调用约定时，也不要对此感到惊奇和诧异．

Parameter type	fifth and higher	fourth	third	second	leftmost
floating-point	stack	XMM3	XMM2	XMM1	XMM0
integer	stack	R9	R8	RDX	RCX
Aggregates (8, 16, 32, or 64 bits) and __m64	stack	R9	R8	RDX	RCX
Other aggregates, as pointers	stack	R9	R8	RDX	RCX
__m128, as a pointer	stack	R9	R8	RDX	RCX

[3]

System V AMD64 ABI

本节中将介绍 System V AMD64 ABI 的部分特性．

函数的前六个参数（每个参数均小于等于 8 byte 且不为浮点型变量）将由左至右依次存放在 rdi、rsi、rdx、rcx、r8、r9 的相应位置，更多的参数将由右向左依次入栈，借助栈完成参数的传递．返回值将保存在 rax 中．

请看代码：

1
2
3
4
5

int func4(int a, unsigned b, long c, unsigned long d, long long e, unsigned long long f);
int main()
{
    func4(1, 2U, 3L, 4UL, 5LL, 6ULL);
}

通过编译器与反汇编工具可以得到这段代码的汇编语言描述．

1
2
3
4
5
6
7
8
9
10
11
12
13

<main>:
push   %rbp
mov    %rsp,%rbp
mov    $0x6,%r9d
mov    $0x5,%r8d
mov    $0x4,%ecx
mov    $0x3,%edx
mov    $0x2,%esi
mov    $0x1,%edi
call   29 <main+0x29>
mov    $0x0,%eax
pop    %rbp
ret

可以看到常量（更准确的叫法是「立即数」）0x1 被存放在 edi、0x2 被存放在 esi、0x3 被存放在 edx、0x4 被存放在 ecx、0x5 被存放在 r8d、0x6 被存放在 r9d．
此时，可能有读者为此感到疑惑：「不是说第一个参数放在 rdi 吗？怎么放在 edi 里了？（后面的几个参数也会有雷同的疑惑）」
事实上，这并非是什么错误．edi 在 x86_64 上是 rdi 的低 32 位；类似的，esi 在 x86_64 上是 rsi 的低 32 位；edx 在 x86_64 上是 rdx 的低 32 位；ecx 在 x86_64 上是 rcx 的低 32 位，r8d 在 x86_64 上是 r8 的低 32 位；r9d 在 x86_64 上是 r9 的低 32 位．

值的注意的还有一点：在 x86_64 平台上，例如： mov $0x1,%edi 等源操作数为 double word 的 mov 指令中，目的寄存器的高 32 位会被置为 0．这也使得可以使用将 零扩展 与 复制 一步完成．

info
INFO

本文将不会给予进一步说明的是：

• XMM0 到 XMM7 用来放置浮点型变量
• 对于系统调用，R10 用来替代 RCX [4]

回看上文中给出的示例，将会发现文中示例无不符合了 System V AMD64 ABI 的要求．

结构体的按值传递

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

struct test_small
{
    int a;
    char ch[4];
};

struct test_small func1(struct test_small arg)
{
    arg.a = 0;
    arg.ch[0] = 3;
    return arg;
}
struct test_big
{
    long a, b, c;
};
struct test_big func2(struct test_big arg)
{
    arg.a = arg.b + arg.c;
    return arg;
}

int main()
{
    struct test_small s;
    func1(s);
    struct test_big b;
    b.a = 1;
    b.b = 2;
    b.c = 3;
    func2(b);
}

可以看到源码中定义了两个结构体．其中 struct test_small 大小为 8 bytes，struct test_big 大小为 24 bytes．
大小对结构体按值传递的方式有及其重要的影响．

通过反汇编可以得到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

<func1>:
push   %rbp
mov    %rsp,%rbp
mov    %rdi,-0x8(%rbp) # 将 rdi 中的 strcut test_small arg 复制到 rbp - 0x8
movl   $0x0,-0x8(%rbp) # arg.a = 0 ;
movb   $0x3,-0x4(%rbp) # arg.ch[0] = 3 ;
mov    -0x8(%rbp),%rax # 将 arg 复制在 rax 中返回
pop    %rbp
ret

<func2>:
push   %rbp
mov    %rsp,%rbp
mov    %rdi,-0x8(%rbp) # rdi 里存放的是 arg 的地址，把 arg 的地址复制到 rbp - 0x8
mov    0x18(%rbp),%rdx # 把 在 main() 中复制到栈上的 b.c 复制到 rdx
mov    0x20(%rbp),%rax # 把 在 main() 中复制到栈上的 b.b 复制到 rax
add    %rdx,%rax # arg.b + arg.c
mov    %rax,0x10(%rbp) # arg.a = arg.b + arg.c
mov    -0x8(%rbp),%rcx # arg 的地址被放在了 rcx 里
mov    0x10(%rbp),%rax
mov    0x18(%rbp),%rdx
mov    %rax,(%rcx) # 本行开始是为返回 arg 作准备 arg.a = arg.a
mov    %rdx,0x8(%rcx) # arg.b = arg.b
mov    0x20(%rbp),%rax # 把 rbp + 0x20 指向的值复制到 rax
mov    %rax,0x10(%rcx) # arg.c = arg.c
mov    -0x8(%rbp),%rax # 把 arg 的地址放在 rax 里返回
pop    %rbp
ret

<main>:
push   %rbp
mov    %rsp,%rbp # rbp = rsp
sub    $0x50,%rsp # rsp -= 0x50 所以 rsp == rbp - 0x50
mov    %fs:0x28,%rax
mov    %rax,-0x8(%rbp)
xor    %eax,%eax
mov    -0x10(%rbp),%rax # 将 rbp - 0x10 处的 Quad Word 复制到 rax．rbp - 0x10 存放的是 s．
mov    %rax,%rdi # 将 rax 里的 s 复制到 rdi．作为 struct test_small arg 实参传递给 func1()．
call   1139 <func1> # 调用 func1()
movq   $0x1,-0x30(%rbp) # b.a = 1 ;
movq   $0x2,-0x28(%rbp) # b.b = 2 ;
movq   $0x3,-0x20(%rbp) # b.c = 3 ;
lea    -0x50(%rbp),%rax # 当前栈顶的地址为 rbp - 0x50，将栈顶的地址复制到 rax
push   -0x20(%rbp) # 将 b.c 压入栈
push   -0x28(%rbp) # 将 b.b 压入栈
push   -0x30(%rbp) # 将 b.a 压入栈，这三次压栈完成了对 结构体 struct test_big b 的复制，且 struct test_big b 的副本的地址已存放在了 rax
mov    %rax,%rdi # 将 struct test_big b 的副本的地址复制给 rdi．
call   1152 <func2> # 调用 func2()
add    $0x18,%rsp
mov    $0x0,%eax
mov    -0x8(%rbp),%rdx
sub    %fs:0x28,%rdx
je     11f7 <main+0x6d>
call   1030 <__stack_chk_fail@plt>
leave
ret

可以看到大小为 8 bytes 的 struct test_small 存储在 rdi 中完成了传递．而大小为 24 bytes 的struct test_big 则无法存放仅仅能容纳 8 bytes 的 rdi 中，自然没法使用 rdi 进行传递．使用栈完成对 struct test_big 等大于 8 bytes 的结构体（当然也不仅仅只是结构体，联合体、int128_t 等数据也使用类似的方式传递）进行传递成为了仅有的办法．

本段代码中，func2 的逻辑较为复杂，可能需要读者将 main() 与 func2() 相互参考才能明白其中的逻辑．
当遇到困难时，读者可通过画出栈的图示的方式进行分析．（可参考笔者在本文开始处的做法）

笔者也画了三张图用来表示 struct test_big 的传递过程，供读者参考．

需要提醒一下的是：结构体的大小并不是结构体的各个成员的大小的代数和．结构体的大小还需要考虑内存对齐的因素．在判断结构体的按值传递方式时，内存对齐将是一个不容忽略的因素．

通过这次的分析，可以发现，大结构体（大于 8 bytes）的按值传递的效率较低．当对程序的运行效率有较高的要求时，应当首先考虑传址而不是传值．

C++ 与参数传递

在 x86_64 Linux 平台上，C++ 的程序的普通函数调用过程与上文中所述并无差异．

将上文代码使用 g++ 编译后重新反汇编得到的代码为：

1
2
3
4
5

int func4(int a, unsigned b, long c, unsigned long d, long long e, unsigned long long f);
int main()
{
    func4(1, 2U, 3L, 4UL, 5LL, 6ULL);
}

1
2
3
4
5
6
7
8
9
10
11
12
13

<main>:
push   %rbp
mov    %rsp,%rbp
mov    $0x6,%r9d
mov    $0x5,%r8d
mov    $0x4,%ecx
mov    $0x3,%edx
mov    $0x2,%esi
mov    $0x1,%edi
call   29 <main+0x29>
mov    $0x0,%eax
pop    %rbp
ret

但类的非静态成员函数的调用与上文有较多不同．在不同中，又可分为两类：

• 非虚成员函数
• 虚成员函数

非虚成员函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <cstdio>
class test
{
    int a, b;

public:
    test() = default;
    int sum()
    {
        return a + b;
    }
};
int main()
{
    test t;
    int s = t.sum();
    printf("%d\n", s);
}

C++ 语言通过 g++ 生成的程序反汇编得到的代码可能没有 C 语言通过 gcc 生成的程序反汇编的得到的代码那么简单易懂．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

<main>:
push   %rbp
mov    %rsp,%rbp
sub    $0x20,%rsp
mov    %fs:0x28,%rax
mov    %rax,-0x8(%rbp)
xor    %eax,%eax
lea    -0x10(%rbp),%rax # -0x10(%rbp) 是个局部变量，本指令将局部变量的地址存储在了 rax
mov    %rax,%rdi # 将 rax 拷贝至 rdi
call   11a0 <_ZN4test3sumEv> # 调用 sum() 函数
mov    %eax,-0x14(%rbp)
mov    -0x14(%rbp),%eax
mov    %eax,%esi
lea    0xe89(%rip),%rdi
mov    $0x0,%eax
call   1030 <printf@plt>
mov    $0x0,%eax
mov    -0x8(%rbp),%rdx
sub    %fs:0x28,%rdx
je     119e <main+0x55>
call   1040 <__stack_chk_fail@plt>
leave
ret

<_ZN4test3sumEv>:
push   %rbp
mov    %rsp,%rbp
mov    %rdi,-0x8(%rbp) # 把 rdi 中存放的地址拷贝至局部变量
mov    -0x8(%rbp),%rax # 将局部变量中存储的地址拷贝至 rax
mov    (%rax),%edx # 将 rax 指向的 一个 double word 拷贝至 edx
mov    -0x8(%rbp),%rax # 再次将局部变量中存储的地址拷贝至 rax
mov    0x4(%rax),%eax # 将 (rax + 0x4) 的一个 double word 拷贝至 eax
add    %edx,%eax # 将 edx 加在 eax 上
pop    %rbp
ret

众所周知，C++ 的非静态成员函数有一个隐式的参数就是 *this 指向成员函数所在的类的类型的指针．
例如：
在考虑 C++ 与汇编代码的关系时，可以将本例中 sum 的理解为：

1
2
3
4

int sum(class test *this)
{
    return this->a + this->b;
}

简而言之，C++ 非静态非虚成员函数含有一个隐式的 this 指针参数，作为第一个参数传递．

这与上文所说的一致．

「第一个小于等于 8 bytes 的整形参数在 System V AMD64 ABI」通过 rdi 传递

好，现在尝试增多 C++ 非静态非虚成员函数 的参数数量．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <cstdio>
class test
{
    int a, b;

public:
    test() = default;
    int sum2(int u, int v, int w, int x, int y, int z)
    {
        return a + b + u + v + w + x + y + z;
    }
};
int main()
{
    test t;
    int s = t.sum2(1, 2, 3, 4, 5, 6);
    printf("%d\n", s);
}

反汇编得到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

<main>:
push   %rbp
mov    %rsp,%rbp
sub    $0x20,%rsp
mov    %fs:0x28,%rax
mov    %rax,-0x8(%rbp)
xor    %eax,%eax
lea    -0x10(%rbp),%rax # -0x10(%rbp) 是个局部变量，本指令将局部变量的地址存储在了 rax
sub    $0x8,%rsp
push   $0x6 # 注意 这个参数使用了 栈 进行传递
mov    $0x5,%r9d # 参数传递
mov    $0x4,%r8d # 参数传递
mov    $0x3,%ecx # 参数传递
mov    $0x2,%edx # 参数传递
mov    $0x1,%esi # 参数传递
mov    %rax,%rdi # 将 rax 里保存的指针 拷贝至 rdi
call   11c6 <_ZN4test4sum2Eiiiiii> # 调用 sum2() 函数
add    $0x10,%rsp
mov    %eax,-0x14(%rbp)
mov    -0x14(%rbp),%eax
mov    %eax,%esi
lea    0xe64(%rip),%rdi
mov    $0x0,%eax
call   1030 <printf@plt>
mov    $0x0,%eax
mov    -0x8(%rbp),%rdx
sub    %fs:0x28,%rdx
je     11c3 <main+0x7a>
call   1040 <__stack_chk_fail@plt>
leave
ret

<_ZN4test4sum2Eiiiiii>:
push   %rbp
mov    %rsp,%rbp
mov    %rdi,-0x8(%rbp) # 在栈上保存 rdi，rdi
mov    %esi,-0xc(%rbp) # 在栈上保存 esi
mov    %edx,-0x10(%rbp) # 在栈上保存 edx
mov    %ecx,-0x14(%rbp) # 在栈上保存 ecx
mov    %r8d,-0x18(%rbp) # 在栈上保存 r8d
mov    %r9d,-0x1c(%rbp) # 在栈上保存 r8d
mov    -0x8(%rbp),%rax # rdi 里保存的指针 复制到 rax
mov    (%rax),%edx # rdi 里保存的指针 指向的 double word 复制到 edx
mov    -0x8(%rbp),%rax # rdi 里保存的指针 复制到 rax
mov    0x4(%rax),%eax # rdi 里保存的指针+0x4 的 double word 复制到 eax
add    %eax,%edx # eax 加到 edx
mov    -0xc(%rbp),%eax # -0xc(%rbp) 里是之前 esi 里的值，也就是 形参 int u 的值
add    %eax,%edx # eax 加到 edx
mov    -0x10(%rbp),%eax # -0x10(%rbp) 里是之前 edx 里的值，也就是 形参 int v 的值
add    %eax,%edx # eax 加到 edx
mov    -0x14(%rbp),%eax # -0x14(%rbp) 里是之前 ecx 里的值，也就是 形参 int w 的值
add    %eax,%edx # eax 加到 edx
mov    -0x18(%rbp),%eax # -0x18(%rbp) 里是之前 r8d 里的值，也就是 形参 int x 的值
add    %eax,%edx # eax 加到 edx
mov    -0x1c(%rbp),%eax # -0x1c(%rbp) 里是之前 r9d 里的值，也就是 形参 int y 的值
add    %eax,%edx # eax 加到 edx
mov    0x10(%rbp),%eax # 0x10(%rbp) 之前被 push 在了栈上，也就是 形参 int z 的值
add    %edx,%eax # eax 加到 edx
pop    %rbp
ret

可以看到：算上隐式的 this 指针，函数 sum2() 共有 7 个参数．参数 1-6 仍然依次采用 rdi、rsi、rdx、rcx、r8、r9 进行传递．第 7 个参数 int z 也正常的使用了栈进行传递．

总结一下，C++ 非静态非虚函数成员的调用过程与 C 语言函数的唯一差别在于需要把 *this 理解为一个参数．

虚成员函数

在给出本节的示例之前，笔者认为有必要再次强调下面的代码只是为了演示虚成员函数的调用过程．如果有人在实际的程序设计的情景中仿照笔者给出的这些示例，那么请允许笔者借用 Scott Meyers 的一句话：

把他们隔离起来直到他们保证不再这样做为止

（笔者在Effective C++ 或是 More Effective C++ 中看到过这句话，但找不到具体出处了，这句只是根据自己的回忆写出的）．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <cstdio>
class test1
{
protected:
    int a;
    int b;

public:
    test1(int A, int B) : a(A), b(B) {}
    virtual void info()
    {
        printf("max=%d\n", a > b ? a : b);
    }
};
class test2 : public test1
{
public:
    test2(int x, int y) : test1(x, y) {}
    void info() override
    {
        printf("min=%d\n", a < b ? a : b);
    }
};
int main()
{
    test1 t1(1, 2);
    test2 t2(3, 4);
    test1 *pr1 = &t1;
    pr1->info();
    test2 *pr2 = &t2;
    pr2->info();
}

编译后反汇编得到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

<main>:
push   %rbp
mov    %rsp,%rbp
sub    $0x40,%rsp
mov    %fs:0x28,%rax
mov    %rax,-0x8(%rbp)
xor    %eax,%eax
lea    -0x30(%rbp),%rax # 把 rbp - 0x30
mov    $0x2,%edx # 参数
mov    $0x1,%esi # 参数
mov    %rax,%rdi # 参数 this 指针
call   11de <_ZN5test1C1Eii> # 构造 t1
lea    -0x20(%rbp),%rax
mov    $0x4,%edx # 参数
mov    $0x3,%esi # 参数
mov    %rax,%rdi # 参数 this 指针
call   1256 <_ZN5test2C1Eii> # 构造 t2
lea    -0x30(%rbp),%rax # t1 的地址存放在 rax 里
mov    %rax,-0x40(%rbp) # t1 的地址从 rax 里复制到 rbp - 0x40．rbp - 0x40 存储的是 pr1
mov    -0x40(%rbp),%rax # 把 pr1 复制到 rax
mov    (%rax),%rax # 把 pr1 指向的 Quad Word 复制到 rax
mov    (%rax),%rdx # 把 pr1 指向的 Quad Word 指向的 Quad Word 复制到 rdx
mov    -0x40(%rbp),%rax # 把 pr1 复制到 rax
mov    %rax,%rdi # 传递参数，把 this 指针从 rax 复制到 rdi．pr2 的值就是 this 指针的实参．
call   *%rdx # 调用 rdx 指向的函数指针
lea    -0x20(%rbp),%rax # t2 的地址存放在 rax 里
mov    %rax,-0x38(%rbp) # t2 的地址从 rax 里复制到 rbp - 0x38．rbp - 0x38 存储的是 pr2
mov    -0x38(%rbp),%rax # 把 pr2 复制到 rax
mov    (%rax),%rax # 把 pr2 指向的 Quad Word 复制到 rax
mov    (%rax),%rdx # 把 pr2 指向的 Quad Word 指向的 Quad Word 复制到 rdx
mov    -0x38(%rbp),%rax# 把 pr2 复制到 rax
mov    %rax,%rdi # 传递参数，把 this 指针从 rax 复制到 rdi．pr2 的值就是 this 指针的实参．
call   *%rdx # 调用 rdx 指向的函数指针
mov    $0x0,%eax
mov    -0x8(%rbp),%rcx
sub    %fs:0x28,%rcx
je     11db <main+0x92>
call   1040 <__stack_chk_fail@plt>
leave
ret

<_ZN5test1C1Eii>: # test1 构造函数
push   %rbp
mov    %rsp,%rbp
mov    %rdi,-0x8(%rbp)
mov    %esi,-0xc(%rbp)
mov    %edx,-0x10(%rbp)
lea    0x2ba5(%rip),%rdxs
mov    -0x8(%rbp),%rax
mov    %rdx,(%rax)
mov    -0x8(%rbp),%rax
mov    -0xc(%rbp),%edx
mov    %edx,0x8(%rax)
mov    -0x8(%rbp),%rax
mov    -0x10(%rbp),%edx
mov    %edx,0xc(%rax)
pop    %rbp
ret

<_ZN5test14infoEv>: # test1::info()
push   %rbp
mov    %rsp,%rbp
sub    $0x10,%rsp
mov    %rdi,-0x8(%rbp)
mov    -0x8(%rbp),%rax
mov    0x8(%rax),%edx
mov    -0x8(%rbp),%rax
mov    0xc(%rax),%eax
cmp    %eax,%edx
jle    1239 <_ZN5test14infoEv+0x27>
mov    -0x8(%rbp),%rax
mov    0x8(%rax),%eax
jmp    1240 <_ZN5test14infoEv+0x2e>
mov    -0x8(%rbp),%rax
mov    0xc(%rax),%eax
mov    %eax,%esi
lea    0xdbb(%rip),%rdi
mov    $0x0,%eax
call   1030 <printf@plt>
leave
ret

<_ZN5test2C1Eii>: # test2 构造函数
push   %rbp
mov    %rsp,%rbp
sub    $0x10,%rsp
mov    %rdi,-0x8(%rbp)
mov    %esi,-0xc(%rbp)
mov    %edx,-0x10(%rbp)
mov    -0x8(%rbp),%rax
mov    -0x10(%rbp),%edx
mov    -0xc(%rbp),%ecx
mov    %ecx,%esi
mov    %rax,%rdi
call   11de <_ZN5test1C1Eii>
lea    0x2afd(%rip),%rdx
mov    -0x8(%rbp),%rax
mov    %rdx,(%rax)
leave
ret

<_ZN5test24infoEv>: # test2::info()
push   %rbp
mov    %rsp,%rbp
sub    $0x10,%rsp
mov    %rdi,-0x8(%rbp)
mov    -0x8(%rbp),%rax
mov    0x8(%rax),%edx
mov    -0x8(%rbp),%rax
mov    0xc(%rax),%eax
cmp    %eax,%edx
jge    12b5 <_ZN5test24infoEv+0x27>
mov    -0x8(%rbp),%rax
mov    0x8(%rax),%eax
jmp    12bc <_ZN5test24infoEv+0x2e>
mov    -0x8(%rbp),%rax
mov    0xc(%rax),%eax
mov    %eax,%esi
lea    0xd47(%rip),%rdi
mov    $0x0,%eax
call   1030 <printf@plt>
leave
ret

笔者本段代码中 main() 的汇编语言描述提供了十分详细的注释，相信读者可根据注释自行理解．

C++ 众多编译器都采用虚函数表的方式实现了 C++ 的虚函数调用．在本例中，gcc 自然也没有什么例外的使用虚函数表实现 C++ 的虚函数功能．

虚函数表可以理解为一个函数指针的数组．编译器需要为含有虚函数的类型生成一张虚函数表，而同一个类型的多个实例将通过存储虚函数表的首元素的地址共享同一张虚函数表．

1
2
3
4
5
6
7

/* 下面的是伪代码，只是为了展示虚函数表的与类的关系 */
class test1
{
    static const void *virtualFunctionTable[SIZE];
    int a;
    int b;
};

此处只是一个粗略的描述，所以笔者采用了 void *virtualFunctionTable[SIZE]; 这种写法，实际上这种写法很不严谨．
写成 void (*virtualFunctionTable[SIZE])(); 这种写法并不能更好．写成 void* 首先较为方便，并且避免读者纠结于类似「void (*func)(int *a,int b);」这种函数指针不能存放在 void (*virtualFunctionTable[SIZE])() 这类次要问题．请务必注意这只是一个为了方便理解虚函数表，笔者给出的伪代码而已．
可以看到在虚函数的调用中，需要访问虚函数表来完成函数的定位，但除此之外，参数的传递与函数值的返回仍然遵守前文所述的规则．

参考资料

¹. 段刚.加密与解密[M].第4版.北京:电子工业出版社. ↩

². KipIrvine.汇编语言：基于x86处理器[M].原书第7版.贺莲,译.北京:机械工业出版社. ↩

³. Randal E.Bryant.深入理解计算机系统[M].第三版.龚奕利,译.北京:机械工业出版社. ↩

⁴. x64 calling convention[G/OL]. docs.microsoft.com. https://docs.microsoft.com/en-us/cpp/build/x64-calling-convention?view=msvc-160. ↩

⁵. 维基百科编者. X86调用约定[G/OL]. 维基百科. 2020(20200922)[2020-09-22]. https://zh.wikipedia.org/zh-hans/X86调用约定. ↩

⁶. WikipediaContributors. X86调用约定[G/OL]. 维基百科. 2020(20200922)[2020-09-22]. https://en.wikipedia.org/wiki/X86_calling_conventions. ↩

GNU/Linux 环境检测系统限制

为了充分保证程序的可移植性，开发人员通常该在 「POSIX」、「X/Open Curses Issue 4」等主流标准的范围内小心的使用 GNU/Linux 系统资源．
话虽如此，但标准一旦制定就已经代表着过去，随着计算机硬件的飞速发展，过去的标准 可能 难以反映今日计算机所拥有的资源．
如果愿意放弃些许可移植性，那么开发人员 或许能 够更大程度的利用 GNU/Linux 所能提供和管理的资源．那么，作为开发人员，该如何查询系统资源的限制呢？

ulimit

通过 which ulimit 便可知晓 ulimit 是 shell 的内建命令．通过 ulimit 命令能设置 shell 的资源限制，该限制在调用 fork() 是，将被其子进程继承．

标准限制

POSIX

The Portable Operating System Interface (POSIX) is a family of standards specified by the IEEE Computer Society for maintaining compatibility between operating systems. POSIX defines the application programming interface (API), along with command line shells and utility interfaces, for software compatibility with variants of Unix and other operating systems.[6]

POSIX.1 定义了很多涉及操作系统实现限制的常量，遗憾的是，这是 POSIX.1 中最令人迷惑不解的部分之一．虽然POSIX.1定义了大量限制和常量，我们只关心与基本 POSIX.1接口有关的部分．
在这些限制和常量中，某些可能定义在中，其余的则按具体条件可定义、可不定义．[1]

在 POSIX.1 中，定义了 _POSIX_OPEN_MAX 的值为 20 ．可想而志，这难以满足当今应用程序开发的需求．
而 CHILD_MAX 在 POSIX.1 的标准中，是一个与设备资源有关「运行时不变值」，POSIX.1 仅保证了其最小值为 _POSIX_CHILD_MAX ．

XSI

The Single UNIX Specification (SUS) is the collective name of a family of standards for computer operating systems, compliance with which is required to qualify for using the “UNIX” trademark. The core specifications of the SUS are developed and maintained by the Austin Group, which is a joint working group of IEEE, ISO JTC 1 SC22 and The Open Group. If an operating system is submitted to The Open Group for certification, and passes conformance tests, then it is deemed to be compliant with a UNIX standard such as UNIX 98 or UNIX 03.[7]

XSI定义了代表实现限制的几个常量．[1]

操作系统的资源限制

上文只是从各项标准层面十分简单的叙述各项标准中的要求，但操作系统实际上能提供的资源 可能 远比标准中要求的多．因此，在运行时进行对系统能提供的资源的限制的查询是有必要的．

获取操作系统资源限制

1
2
3
4

#include <unistd.h>
long sysconf(int name);
long pathconf(const char *pathname, int name);
log fpathconf(int fd, int name);

这几个函数的接口都十分简单，更多信息请查看 Linux Programmer's Manual．

更改系统资源限制

每个进程都有一组资源限制，其中一些可以用getrlimit和setrlimit函数查询和更改．

1 2 3

#include <sys/resource.h> int getrlimit(int resource, struct rlimit *rlptr); int setrlimit(int resource, const struct rlimit *rlptr);

两个函数返回值：若成功，返回0；若出错，返回非0
这两个函数在Single UNIX Specification的XSI扩展中定义．进程的资源限制通常是在系统初始化时由0进程建立的，然后由后续进程继承．每种实现都可以用自己的方法对资源限制做出调整．
对这两个函数的每一次调用都指定一个资源以及一个指向下列结构的指针．

1 2 3 4

struct rlimit { rlim_t rlim_cur; /* soft limit: current limit */ rlim_t rlim_max; /* hard limit: maximum value for rlim_cur */ };

在更改资源限制时，须遵循下列3条规则．

1. 任何一个进程都可将一个软限制值更改为小于或等于其硬限制值．
2. 任何一个进程都可降低其硬限制值，但它必须大于或等于其软限制值．这种降低，对普通用户而言是不可逆的．
3. 只有超级用户进程可以提高硬限制值．[1]

参考资料

¹. W.RichardStevens.Stephen.UNIX环境高级编程[M].第3版.戚正伟,译.北京:人民邮电出版社 ↩

². ulimit(1p)[G/OL].POSIX Programmer’s Manual,https://man.archlinux.org/man/ulimit.1p. ↩

³. ulimit(3)[G/OL].Linux Programmer’s Manual,https://man.archlinux.org/man/ulimit.3. ↩

⁴. ulimit(3p)[G/OL].Linux Programmer’s Manual,https://man.archlinux.org/man/ulimit.3p. ↩

⁵. Unix标准和实现[G/OL]https://klose911.github.io/html/apue/standard.html. ↩

⁶. Wikipedia contributors. POSIX[G/OL]. Wikipedia, https://en.wikipedia.org/wiki/POSIX. ↩

⁷. Wikipedia contributors. Single UNIX Specification[G/OL]. Wikipedia, https://en.wikipedia.org/wiki/Single_UNIX_Specification. ↩

尝试定性分析「快慢指针」寻找链表中点

warning
WARNING
本文不是成熟可靠、达成普遍共识的结论，也不是有可靠数据支撑的学术研究成果．
本文只是笔者根据从书中学到的知识分析和猜测遇到的现实问题，并尝试着给予答案的过程，并不能作为真正可靠的结论使用．
笔者在目前尚未具有验证自己得到的分析结果的能力．

相信看本文的读者已经熟悉这道经典的算法题目了．说实话，自从笔者接触这道题目的「快慢指针」题解之后产生的想法是疑惑：「为什么『快慢指针』的方式来取链表的中点比单指针遍历两遍能更快？」
众所周知，这两种不同的算法拥有相同的时间复杂度 O(N)，此时无法仅根据时间复杂度对这两种算法在相同规模的数据下的运行速度作出判断．

测试结果

当然，两种算法究竟哪种更优应该让数据来证明，而不仅仅是纸面上的分析．但十分遗憾，笔者无法提供一个较为可靠的数据．笔者的机器上运行着众多的应用，机器的性能受各种因素影响较多，性能波动较大，无法提供一个数据．在 leetcode 上以两种方式的提交结果中也未见差异．而没有可靠的数据证实的分析也是本文标题中含有「尝试」的原因．

对比算法的 C 语言描述

首先，作为链表节点的结构体为：

1
2
3
4
5

struct ListNode
{
    int val;
    struct ListNode *next;
};

1
2
3
4
5
6
7
8
9
10
11
12

struct ListNode *middleNode(struct ListNode *head)
{
    struct ListNode *slow, *fast, *tmp;
    slow = head;
    fast = head;
    while (fast != NULL && (tmp = fast->next) != NULL)
    {
        fast = tmp->next;
        slow = slow->next;
    }
    return slow;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

struct ListNode *middleNode(struct ListNode *head)
{
    struct ListNode *cur = head;
    int n = 0;
    while (cur != NULL)
    {
        ++n;
        cur = cur->next;
    }
    int k = 0;
    cur = head;
    while (k < n / 2)
    {
        ++k;
        cur = cur->next;
    }
    return cur;
}

那么，只好首先从汇编语言的层面对两种算法进行分析．

对比算法的机器代码描述

用 GCC 分别编译两个文件后便可得到下文中的汇编代码（GCC 的参数中添加 -S 对文件只执行「编译」，-Og 禁用编译器优化，防止代码变形）．
info
INFO
下文的汇编代码较 GCC 产生的代码，省略了无关的内容．
注意：下文为 AT&T 格式的汇编语言代码．

「快慢指针方式」的汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

	movq	%rdi, %rax
	jmp	.L2
.L4:
	movq	8(%rax), %rax //fast = tmp->next
	movq	8(%rdi), %rdi //slow = slow->next
.L2:
	testq	%rax, %rax //判断 fast == 0 ？ 也就是判断 fast == NULL ？
	je	.L3 // 如果 fast == NULL 就跳转至 .L3
	movq	8(%rax), %rax //把 tmp = fast->next
	testq	%rax, %rax //判断 tmp == NULL ?
	jne	.L4 //如果 tmp != NULL 就跳转至 .L4
.L3:
	movq	%rdi, %rax //把返回值复制至 %rax
	ret// 函数返回

「单指针方式」的汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

	movq	%rdi, %rax // cur = head
	movl	$0, %edx //n = 0
	jmp	.L2
.L3:
	addl	$1, %edx // ++n
	movq	8(%rax), %rax // cur = cur->next
.L2:
	testq	%rax, %rax // cur == NULL ?
	jne	.L3//如果  cur  != NULL 就跳转至 .L3
	movl	$0, %ecx // k = 0
	jmp	.L4
.L5:
	addl	$1, %ecx // ++k
	movq	8(%rdi), %rdi // cur = cur->next
.L4:
	movl	%edx, %eax //int tmp = n
	shrl	$31, %eax //tmp = tmp < 0 ? 1 : 0
	addl	%edx, %eax // tmp +=n
	sarl	%eax // tmp >>= 1
	cmpl	%ecx, %eax// tmp - k
	jg	.L5
	movq	%rdi, %rax //把返回值复制至 %rax
	ret // 函数返回

「单指针方式」的汇编代码中，第 16 行至第 19 行的代码可能在理解上有些难度，这些指令是为了计算 n / 2 的结果，因为除数是 2 的幂，那么除法总是可以用偏置和右移运算来代替．

可能有人会关注到在循环中，反复的进行了对 n /2 求值，甚至求值中的偏置是不必要的（因为 k 不可能为负值）．但这些问题在更高阶的编译优化中消失，并不能真正的影响 release 版本时的性能，那么这两种算法存在性能差异吗？笔者认为仍旧存在性能差异．

存储器的层次结构

在真正的说明笔者自己认为的两种算法的性能差异之前，还需要在回顾一下「存储器的层次结构」．
首先，程序运行中的数据和代码被加载至「DRAM」之中．
为解决 「CPU」 频率与 「DRAM」频率的巨大差异并权衡制造的成本，计算机学家们引入 「SRAM」 分 「L3 cache」、「L2 cache」、「L1 cache」三层，逐层的进行缓存，加速「CPU」访问「DRAM」中的内容的时间．
当 CPU 试图访问的数据不在缓存中时，即发生了 缓存不命中时，将触发「不命中惩罚」，造成程序效率的降低．「缓存不命中」是不可避免的，但可以通过一定的优化方式来减少「缓存不命中」．
当然，关于「存储器的层次结构」这庞大的知识非笔者只言片语能说明，在本文不再方便展开．

一个编写良好的计算机程序常常具有良好的局部性．也就是，它们倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身．这种倾向性被称为「局部性原理」．[1]
具有良好的局部性的程序能有效的减少「缓存不命中」，也就是更好的利用「存储器的层次结构」，使「CPU」更快速的访问所需的数据．

局部性通常有两种不同的形式：「时间局部性」和「空间局部性」．在一个具有良好时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来再被多次引用．在一个具有良好空间局部性的程序中，如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置．[1]

• 从空间局部性来考虑：
  链表中的节点存储的位置并无规律，每个节点是分散的，都具有较差的空间局部性．可大致认为两种算法的空间局部性相同．
• 从时间据局部性来考虑：
  • 「快慢指针方式」中：在一次循环中，链表的前半部分中，快指针访问完成之后循环结束之前慢指针已经访问了相同的节点．同一个节点被两次访问的时间间隔较近．
  • 「单指针方式」中：在一次循环中，链表的前半部分中，同一个节点的第二次访问在第一次遍历完成之后，同一个节点被两次访问的时间间隔较远．

可见，「快慢指针方式」具有更好的时间局部性，单指针第二次遍历链表时，可供其利用的「前半段链表中的节点」的缓存有更大的概率被链表的「后半段链表中的节点」的缓存所替换，由此将更频繁的触发「不命中处罚」．
更严重的是，若链表的节点增大，则在相同的缓存中能缓存的节点更少，缓存的替换将更频繁，「单指针方式」的性能想较「快慢指针方式」遍历可能下降更多．
同样的，若链表的长度增加，也会导致前半段的链表的节点的缓存被更多的替换．

循环展开

此时更换一个角度，再次回看「单指针方式」的 C语言代码，忽略次要部分后，可以视为使用一个循环 1.5 倍链表节点个数次，而「快慢指针方式」循环 1 倍节点个数次．
而「快慢指针」方式可视为由「单指针方式」进行「循环展开」得到的代码．

循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数．[1]

循环展开能够从两个方面改进程序的性能．首先，它减少了不直接有助于程序结果的操作数量，例如循环索引计算和条件分支．第二它提供了一些方法，可以进一步变化代码，减少整个计算中关键路径上的操作数量．[1]

参考资料

¹. Randal E.Bryant.深入理解计算机系统[M].第三版.龚奕利,译.北京:机械工业出版社 ↩

Linux C 开发实战—myshell

时间过的飞快，不知不觉中离笔者写完myshell已经过了不少时间了．为了进一步的巩固笔者当初从开发实战中学习到的知识，笔者决定还是补上这篇拖延了很久的博客．

需求

• 支持使用任意数量的 管道
• 支持使用命令调用其他程序
• 支持使用任意数量的重定向输入输出
• 内置 cd 命令
• 内置 history 命令
• 支持Tab键 补全
• 实现光标移动
• 屏蔽相关信号，防止 Ctrl+C 杀死
• 界面美观

开发过程

头文件

1
2
3
4
5
6
7
8
9
10

#include <ctype.h>
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/wait.h>
#include <unistd.h>
#include <readline/history.h>
#include <readline/readline.h>

宏和全局变量

1
2
3
4
5
6
7
8

extern char **environ;
struct COMMAND
{
    int argc;           //参数数量
    int Redirect_FD[3]; //标准输入、标准输出、错误输出的重定向情况
    char **argv;
};
char *oldpath;

错误处理

1
2
3
4
5
6

void myerror(char *string, int line)
{
    fprintf(stderr, "\aLine:%d,error:\a\n", line);
    fprintf(stderr, "%s:%s\n", string, strerror(errno));
    exit(EXIT_FAILURE);
}

开发前的分析

• 多重管道可以使用 分治 的思想逐层处理，化简为单重管道的情况，而单重管道可视为先后发生A >./tmpfile和 B <./tmpfile 的情况，因此管道和重定向符的实现紧密相关．
• 重定向符有很多种格式，例如：> 、 >> 、 1> 、 1>> 、 2> 、 2>> 、< 、 << 、 1>&2 、 1>>&2 、 2>&1 、 2>>&1 ，但这次练习的重点不是字符串的解析，故此笔者不计划实现最后的五种．
• Tab键 补全、历史记录的存放等功能均由 readline 库实现(感谢GNU Project为此作出的贡献)．
• 界面美观的要求通过输出带有颜色的文字和输出对齐的文本来实现
• 调用其他程序则涉及进程控制的相关内容

获取并解析用户输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int main(void)
{
    read_history(NULL);

    while (1)
    {
        char *command = readline("MYSHELL$");
        add_history(command);
        write_history(NULL);
        launch(command);
        free(command);
    }

    if (oldpath != NULL)
    {
        free(oldpath);
    }
}

通过 readline 库提供的 readline() 函数，便可轻松的输出 命令提示符 并获取用户输入．

将命令拆分成多段

此时，笔者运用著名的 分治 思想，将形如 A -b cde -f | g -hi | j -k lmn >123.txt 的命令以 | 为界线拆成多段，分别处理．

笔者在前文分析过 管道 可以用两个输入输出重定向来实现．
下面分析实现的具体方法，取一条以|符号为界分为 $n$段的命令( $\forall n \in\mathbb N^+, n \geq 3$ )

1. 考察该命令的第 $1$ 段．管道要求第二段命令的输入为第一段命令的输出．因此可将第 $1$ 段命令的标准输出重定向至临时文件，并将第 $2$ 段命令的标准输入重定向至该临时文件．
2. 考察该命令的第 $i$ 段( $\forall i \in\mathbb N, 1 < i < n $)．该段命令的输入为第 $i-1$ 段的输出，可将第 $i-1$ 段的标准输出重定向至临时文件，并将第 $i$ 段的标准输入重定向至该临时文件；该段命令的输出为第 $i+1$ 段的输入，可将第 $i$ 段的标准输出重定向至临时文件，并将第 $i+1$ 段的标准输入重定向至该临时文件
3. 考察该命令的第 $n$ 段．该段的输入为第 $n-1$ 段的输出．因此可将第 $n-1$ 段的标准输出重定向至临时文件，并将第 $n$ 段的标准输入重定向至该临时文件．

这就是实现管道的全部流程．

但问题来了，如何处理形如 A -b cde -f >./log.txt | g -hi | j -k lmn <123.txt 的命令？在上段中，笔者分析了第 $1$ 段的标准输入要重定向至临时文件，但命令中却要求重定向至 log.txt ．
笔者曾考虑复制一份重定向中产生的临时文件至 ./log.txt 或者用 log.txt 代替临时文件的功能，这样就能上例中的冲突．但是请思考这个例子 ls -al >/dev/null |wc -c ．
这个命令中wc -c命令读的结果根据实现方法会有不同．在笔者的环境中使用 zsh 执行该命令的结果不为 0 ，但使用 GNU bash 执行该命令的结果为 0 ．笔者认为类似上面的命令具有 二义性 ，故此笔者的 myshell 实现中对形如 A -b cde -f >./log.txt | g -hi | j -k lmn >123.txt 、ls -al >/dev/null |wc -c 、ls -alR / |grep test <./result.md 这类命令做报错处理，欢迎读者们在评论区留言和笔者讨论这个问题．

好了，至此笔者说明了本程序的绝大部分设定和思想，下面就可以来讨论 launch() 函数的具体实现了．

首先遍历一遍命令，计算命令中的管道数量．

1
2
3
4
5
6
7
8

int pipe = 0; //管道计数器
for (char *pr = command; *pr != '\0'; pr++)
{
    if (*pr == '|')
    {
        pipe++;
    }
}

计算出了管道的数量也就知道了命令需要被分成几段．那么就可以根据分段的数量创建一个 COMMAND 的数组．

1
2
3
4
5

struct COMMAND *cmd = (struct COMMAND *)calloc(pipe + 1, sizeof(struct COMMAND));
if (cmd == NULL)
{
    myerror("malloc", __LINE__);
}

然后就是将命令分段的实现了．

1
2
3
4
5
6
7
8
9

char *remain = NULL;
char *part = strtok_r(command, "|", &remain);
for (int i = 0; i <= pipe; i++)
{
    /* 初始化 */
    cmd[i].Redirect_FD[STDIN_FILENO] = -1;
    cmd[i].Redirect_FD[STDOUT_FILENO] = -1;
    cmd[i].Redirect_FD[STDERR_FILENO] = -1;
}

还记得吗？笔者用 Redirect_FD 表示每段命令中重定向的文件的文件描述符．因为合法的文件描述符都是非负的，那么笔者必须要将 Redirect_FD 中的每个元素都初始化为 -1 才能表达不需要重定向的情况．

tip

TIP

笔者猜会有读者对strtok_r()函数的使用产生疑惑．strtok_r()函数的用法与strtok()函数的用法类似，只是多了一个参数．

这两个函数的函数原型为：

char strtok(char str, const char delim);
char strtok_r(char str, const char delim, char **saveptr);

简单的说，strtok_r() 是可重入版本的 strtok() ，就是将使用 static 变量保存的数据保存在了参数里，实现了可重入的需求．
至于为什么要用 strtok_r() 而不是 strtok() ？因为后文还有一处有分割字符串的需求，如果都用 strtok() 来实现，那么在第2处调用(指第一个参数不为NULL的第2处调用)会覆盖先前保存在 static 变量中的数据，无法满足笔者的需求．后文会再次重复该问题．

在这之后，分别处理每段命令．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

    for (int i = 0; i <= pipe; i++)
    {

        if (pipe && i < pipe)
        {
            /* 生成临时文件 */
            char TempFile[] = "/tmp/MyShell_XXXXXX";
            int TempFile_FD = mkstemp(TempFile);
            /* 检测生成临时文件是否成功 */
            if (TempFile_FD == -1)
            {
                myerror("mkstemp", __LINE__);
            }
            /* 将本段命令的标准输出重定向至临时文件 */
            cmd[i].Redirect_FD[STDOUT_FILENO] = TempFile_FD;
            /* 将下段命令的标准输入重定向至临时文件 */
            cmd[i + 1].Redirect_FD[STDIN_FILENO] = TempFile_FD;
            unlink(TempFile);
            //删除临时文件（临时文件在被close前依然可用，不会被立即删除）
        }
        analyze(part, &cmd[i]);//分析与检测本段命令中的参数与重定向符
        if (不是内置命令)
        {
            执行本段命令
        }
        if (pipe && i < pipe)
        {
            lseek(cmd[i].Redirect_FD[STDOUT_FILENO], 0, SEEK_SET);
            cmd[i].Redirect_FD[STDOUT_FILENO] = -1;
        }
        part = strtok_r(NULL, "|", &remain);
        for (int IO_Steam = 0; IO_Steam < 3; IO_Steam++)
        {
            if (cmd[i].Redirect_FD[IO_Steam] >= 0)
            {
                close(cmd[i].Redirect_FD[IO_Steam]);
                //关闭文件，释放相关资源
            }
        }

        for (int j = 0; j < cmd[i].argc; j++)
        {
            free(cmd[i].argv[j]);
        }
        free(cmd[i].argv);
    }
    free(cmd);
}

为了便于读者们阅读和理解，第22行和第23行笔者使用了伪码来描述其中的逻辑．具体的实现将在后文说明．

请读者们注意第28 行，该行将文件的读取位置重置为0．以便下一段命令从文件头读取内容．

第29 行，在本段命令执行结束后，将因实现管道产生的重定向中的输出重定向设为-1．为什么要这样做？为了避免 close 临时文件，在第18行已经对临时文件执行了unlink ，close 后临时文件的引用计数递减为0，会导致临时文件被真正的删除，下一段命令将无法完成输入重定向．故此，临时文件只能在完成输入重定向的使命之后关闭．

最终，所有打开的重定向文件都该被将被close．

分析处理命令段

首先将正在处理的命令段复制一份，因为在分析中会更改命令段的值．

1
2
3
4
5

char *string = strdup(OriginString);
if (string == NULL)
{
    myerror("malloc", __LINE__);
}

tip

TIP

strdup()的用法等于用strlen()计算源字符串的长度后分配为新字符串分配内存空间并完成复制最终返回原字符串的副本的地址．

srdup() 的函数签名为：

char *strdup(const char *s);

在这之后定义变量char *end = string + strlen(string); 作为一个哨兵指向\0，标记string的结束位置，防止指针越界．

下面就是查找命令段中是否含有输入输出重定向，重定向是否合法，以及解析命令行的参数，将其转换为char **argv; 的形式．

处理标准输出、错误输出重定向

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

char *result = NULL;
while ((result = strchr(string, '>')) != NULL)
{
    *result = ' ';
    int IO_Steam = 1;

    result--;
    if (result > string && isdigit(*result))
    {
        if (*result - '0' != STDOUT_FILENO && *result - '0' != STDERR_FILENO)
        {
            printf("Unknow COMMAND\n");
            exit(EXIT_FAILURE);
        }
        else
        {
            IO_Steam = *result - '0';
            *result = ' ';
        }
    }
    if (cmd->Redirect_FD[IO_Steam] >= 0)
    {
        printf("Unknow COMMAND\n");
        exit(EXIT_FAILURE);
    }
    result += 2;
    _Bool Append = 0;
    if (result < end && *result == '>')
    {
        Append = 1; //附加模式
        *result = ' ';
    }
    while (result < end && isspace(*result))
    {
        result++;
    }

    if (result < end)
    {
        cmd->Redirect_FD[IO_Steam] = OpenFile(result, O_WRONLY | O_CREAT | (Append ? O_APPEND : O_TRUNC));
    }
    else
    {
        printf("Unknow COMMAND\n");
        exit(EXIT_FAILURE);
    }
}

处理输入重定向

有了标准输出、错误输出重定向的处理方式，那标准输入重定向的处理方式也不会很难．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

while ((result = strchr(string, '<')) != NULL)
{
    *result = ' ';
    if (cmd->Redirect_FD[STDIN_FILENO] >= 0)
    {
        printf("Unknow COMMAND\n");
        exit(EXIT_FAILURE);
    }
    while (result < end && isspace(*result))
    {
        result++;
    }
    if (result < end)
    {
        cmd->Redirect_FD[STDIN_FILENO] = OpenFile(result, O_RDONLY);
    }
    else
    {
        printf("Unknow COMMAND\n");
        exit(EXIT_FAILURE);
    }
}

解析命令行参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

int arg_max = 16; //参数上限，在无法满足需求时会自动增加

cmd->argv = (char **)calloc(arg_max, sizeof(char *));
if (cmd->argv == NULL)
{
    myerror("malloc", __LINE__);
}
char *remain = NULL;
result = strtok_r(string, " ", &remain);
while (result != NULL)
{
    if (arg_max < cmd->argc)
    {
        arg_max *= 2;                                                      //参数数量上限扩充至原来的2倍
        cmd->argv = (char **)realloc(cmd->argv, arg_max * sizeof(char *)); //扩充指针数组大小
    }
    cmd->argv[cmd->argc++] = strdup(result);
    if (cmd->argv == NULL)
    {
        myerror("malloc", __LINE__);
    }
    result = strtok_r(NULL, " ", &remain);
}
if (arg_max < cmd->argc)
{
    arg_max++;
    cmd->argv = (char **)realloc(cmd->argv, arg_max * sizeof(char *)); //扩充指针数组大小
    if (cmd->argv == NULL)
    {
        myerror("malloc", __LINE__);
    }
}
cmd->argv[cmd->argc] = NULL; //argv[argv]的值为NULL

好了，这段命令的解析终于是结束了．当然还有一点小小的工作需要完成．free(string); 释放命令段的副本所占用的内存．

打开重定文件

临时文件的打开笔者在上文中已经实现完成．但用户在命令行中指定的重定向文件的打开还需要单独实现．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int OpenFile(char *string, int flags)
{

    size_t len = 0;
    char *pr = string;
    while (!isspace(*pr) && *pr++ != '\0')
    {
        len++;
    }

    char *dest = malloc((len + 1) * sizeof(char));
    if (dest == NULL)
    {
        myerror("malloc failed", __LINE__);
    }
    strncpy(dest, string, len);
    dest[len] = '\0';
    memset(string, ' ', sizeof(char) * len);
    PathAnalyze(&dest);
    int fd = open(dest, flags, S_IRUSR | S_IWUSR);
    if (fd == -1)
    {
        printf("error:fd:%d  path:%s\n", fd, string);
        myerror("open", __LINE__);
    }
    free(dest);
    return fd;
}

传入的string是命令段的副本，这意味着重定向文件的路径后面可能还有以空格分隔的其他参数，这意味这不能直接使用string调用open()．

此处，笔者通过计算空格前的字符数量并将其复制到新的字符串中使字符串中只含有重定向文件的路径．

转换相对路径

遗憾的是，至此依然不能把dest字符串直接当作参数去调用open() ．莫着急，请听笔者慢慢道来．

在此时，string是重定向文件的路径是毫无疑问的．但路径并不都是可被open() 直接使用的．请参考笔者的前作（命令行参数的误区），文中说明了函数接受的路径只能是绝对路径或以.开头的相对路径．但用户输入的路径却不总是符合这里的要求．而将其他的相对路径格式转换为绝对路径是shell的任务．

思考需要转换的两种相对路径格式．

• ~/123.md 该类相对路径只需要读取HOME环境变量然后通过简单的字符串拼接就可完成转换．
• ~root/123.md 该类相对路径的处理更加简单，直接完成拼接即可完成转换．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

void PathAnalyze(char **path) //处理~开头的相对路径
{
    char *RelativePath = *path;
    if (isalpha(*(RelativePath + 1)))
    {
        *path = malloc(strlen(RelativePath) + 1 + strlen("/home/") + 1);
        if (*path == NULL)
        {
            myerror("malloc", __LINE__);
        }
        strcpy(*path, "/home/");
    }
    else
    {
        char *home = getenv("HOME"); //获得HOME环境变量的值
        *path = malloc(strlen(RelativePath) + 1 + strlen(home) + 1);
        if (*path == NULL)
        {
            myerror("malloc", __LINE__);
        }
        strcpy(*path, home);
    }
    strcat(*path, RelativePath + 1);
    free(RelativePath);
}

至此，只需要根据传入的参数直接调用open()函数便可完成打开．

执行命令段

有了刚才的准备工作，现在是万事俱备了，只需要真正的执行命令段中的命令．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

void execute(struct COMMAND *cmd)
{

    pid_t pid = fork();
    if (pid > 0)
    {
        wait(NULL);
        return;
    }
    for (int i = 1; i < cmd->argc; i++)
    {
#ifndef NDEBUG
        printf("DEBUG,pid: %d LINE:%d\n", pid, __LINE__);
#endif
        if (*cmd->argv[i] == '~')
        {
            PathAnalyze(&cmd->argv[i]);
        }
    }
#ifndef NDEBUG
    printf("DEBUG:argv[0]:%s\n", cmd->argv[0]);
#endif
    for (int IO_Steam = 0; IO_Steam < 3; IO_Steam++)
    {
        if (cmd->Redirect_FD[IO_Steam] >= 0 && dup2(cmd->Redirect_FD[IO_Steam], IO_Steam) == -1)
        {
            myerror("dup2", __LINE__);
        }
    }
    execvp(cmd->argv[0], cmd->argv);
    myerror("exec", __LINE__);
}

首先执行fork()，创建子进程，然后子进程根据struct COMMAND的指示完成输入输出的重定向，并在struct COMMAND中找到作为新的进程的调用参数的argv．好了，直接调用即可．如果在未出错的情况下，程序不该执行到 第31行，故在执行到第31行时说明程序已出错．

内置命令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

_Bool BuiltInCommand(struct COMMAND *cmd)
{
    /* 内建 历史记录命令 */
    if (strcmp(cmd->argv[0], "history") == 0)
    {
        HIST_ENTRY **history = NULL;
        history = history_list();
        for (int i = 0; history[i] != NULL; i++)
        {
            printf("%s\n", history[i]->line);
        }
        return 0;
    }
    /* 内建 切换工作目录命令 */
    if (strcmp(cmd->argv[0], "cd") == 0)
    {
        if (*cmd->argv[1] == '-')
        {
            chdir(oldpath);
        }
        else if (*cmd->argv[1] == '~')
        {
            PathAnalyze(&cmd->argv[1]);
        }
        oldpath = getcwd(NULL, 0);
        chdir(cmd->argv[1]);
        return 0;
    }
    /* 内建 退出命令 */
    if (strcmp(cmd->argv[0], "exit") == 0 || strcmp(cmd->argv[0], "q") == 0)
    {
        exit(EXIT_SUCCESS);
    }
    return 1;
}

收尾工作

屏蔽相关信号

1
2
3
4
5

signal(SIGHUP, SIG_IGN);
signal(SIGINT, SIG_IGN);
signal(SIGTTIN, SIG_IGN);
signal(SIGTTOU, SIG_IGN);
signal(SIGTSTP, SIG_IGN);

输出颜色

在 main() 中，笔者希望命令提示符和当前工作目录的输出为红色．因此对代码做了如下的改动:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31