真正的异步--io_uring 闲谈

历史的接口

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

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

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

同步接口

常见的 readwritesyscall 都是同步 IO 的接口.
readwrite 类系统调用也衍生出了带有偏移量的接口 preadpwrite 向量读写的接口 readvwritev 和具有两者特性的 preadvpwritev,后来又出现为 preadvpwritev 加上 flag 字段的 preadv2pwritev2 接口.

说了这些,但究竟什么是同步?

同步接口最鲜明的特征就是应用程序:要么在执行应用程序中的用户代码;要么在因完成 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 是否就绪是一个做法.内核也提供了相关的设施用来完成遍历并轮询的操作(selectpoll) ,但这在同步 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_setupio_uring_enterio_uring_register 看似仅仅只有 3 个系统调用,但它们却都分别支持了十多个 flag 来改变系统调用的行为.

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

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

MoreInfo

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

参考资料

1. Efficient IO with io_uring.[G/OL].https://kernel.dk/io_uring.pdf.
2. What is io_uring?. [G/OL]. Lord of the io_uring, https://unixism.net/loti/what_is_io_uring.html.
3. IO_URING(7). [G/OL]. Linux Programmer’s Manual, https://man.archlinux.org/man/io_uring.7.
4. IO_URING_SETUP(2). [G/OL]. Linux Programmer’s Manual, https://man.archlinux.org/man/io_uring_setup.2.
5. IO_URING_ENTER(2). [G/OL]. Linux Programmer’s Manual, https://man.archlinux.org/man/io_uring_enter.2.
6. IO_URING_REGISTER(2). [G/OL]. Linux Programmer’s Manual, https://man.archlinux.org/man/io_uring_register.2.

Arch Linux 安装指引

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

同理,对 nvme0n1 进行分区操作的指令为:
1
# cfdisk /dev/nvme0n1

在分区时,需要分出 至少 两个分区.

分区名大小Type备注
/越大越好Linux filesystem必选
boot至少 260 MB ,一般不超过 500 MBEFI System必选
swap通常和内存大小近似,可根据喜好适量扩大或缩小Linux swap小内存设备可选,大内存设备不需要
home越大越好Linux filesystem可选
  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
本步骤中请勿直接套用本文中的命令.
在进行格式化操作时,请仔细检查防止错误操作带来不良后果.

笔者推荐使用 ext4xfs作为 /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

其后使用 pacstrap 安装 Arch Linux
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

在日常的操作中不推荐使用 root 用户,因此需要创建一个新的用户.下面的命令讲创建一个叫 username 的用户,并将其加入了 wheel 用户组.
1
# useradd -m -G wheel username

设置用户的密码
1
# passwd username

配置 swap 文件

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

安装桌面环境

安装 KDE

1
# pacman -S plasma sddm

开启 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 的安装步骤全部结束.重启设备享受 Arch Linux 即可.


启用 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-imfcitx5-chinese-addonsfcitx5-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 配置中将 拼音 加入当前输入法.

使用蓝牙

在使用蓝牙前,请安装 bluezbluez-utilspulseaudio-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

参考资料

1. ArchWiki编者. Installation guide (简体中文)[G/OL]. ArchWiki, https://wiki.archlinux.org/index.php/Installation_guide_(简体中文).
2. ArchWiki编者. Installation guide[G/OL]. ArchWiki, https://wiki.archlinux.org/index.php/Installation_guide.
3. ArchWiki编者. pacman (简体中文)[G/OL]. ArchWiki, https://wiki.archlinux.org/index.php/Pacman_(简体中文).
4. ArchWiki编者. Chroot (简体中文)[G/OL]. ArchWiki, https://wiki.archlinux.org/index.php/Chroot_(简体中文).
5. 约伊兹的萌狼乡手札.给 GNU/Linux 萌新的 Arch Linux 安装指南 rev.B[G/OL]. 约伊兹的萌狼乡手札, https://blog.yoitsu.moe/arch-linux/installing_arch_linux_for_complete_newbies.html.

Bitset 和字节序

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;

本例的输出为 00010010001101000101011001111000,可以看到输出并不是按照 bitset 的下标顺序输出,而是按照大端顺序输出.

测试环境

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

C/C++ 调试工具

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

Lint

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

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

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

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

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

动态分析

Sanitizers

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

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.

单元测试

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

C:

C++:

日志

对于一个复杂的软件系统,常常需要在长期在后台静默的运行,那么日志的输出就十分重要,日志也常常被用来定位系统中的 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

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

参考资料

1. google/sanitizers:AddressSanitizer, ThreadSanitizer, MemorySanitizer [G/OL]. https://github.com/google/sanitizers.
2. Clang 13 documentation [G/OL]. https://clang.llvm.org/docs/.
3. Thread Safety Analysis [G/OL]. https://clang.llvm.org/docs/ThreadSafetyAnalysis.html.

x86_64函数调用

x86_64 函数调用

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

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

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

前置知识

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

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

PUSH

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

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

POP

POP 操作与 PUSH 操作相对应.
POP 指令总是:
POP 前

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

tip
TIP
栈顶:当前 rsp 指向的值.

LEAVE

LEAVE 操作是等价于

1
2
mov %rbp , %rsp
pop %rbp

也就是:

  1. 通过执行 mov %rbp , %rsprsp = 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 的调用.callmain() 中下一条语句的地址(也就是「mov $0x0,%eax」这句的地址)压入栈中并修改 rip 的值为 func1() 的地址.
    调用时1
  • func1(),通过将 rbp 压栈的方式,保存 rbp
    调用时2

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

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

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

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

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

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

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

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

可以看到乘法产生的结果通过 mov %ecx,%eax 放在了 rax 的低 32 位(eax)中.返回后,在 main() 有:

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 个参数分别采用 rdirsirdxrcxr8r9 这 6 个寄存器对应的低 32 位部分.而剩余的 4 个参数采取了压栈的方式进行传递.

x86-64 调用约定

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

Microsoft x64 calling convention

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

Parameter typefifth and higherfourththirdsecondleftmost
floating-pointstackXMM3XMM2XMM1XMM0
integerstackR9R8RDXRCX
Aggregates (8, 16, 32, or 64 bits) and __m64stackR9R8RDXRCX
Other aggregates, as pointersstackR9R8RDXRCX
__m128, as a pointerstackR9R8RDXRCX

[3]

System V AMD64 ABI

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

函数的前六个参数(每个参数均小于等于 8 byte 且不为浮点型变量)将由左至右依次存放在 rdirsirdxrcxr8r9 的相应位置,更多的参数将由右向左依次入栈,借助栈完成参数的传递.返回值将保存在 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 wordmov 指令中,目的寄存器的高 32 位会被置为 0.这也使得可以使用将 零扩展复制 一步完成.

info
INFO

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

  • XMM0XMM7 用来放置浮点型变量
  • 对于系统调用,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 bytesstruct 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 bytesstruct test_small 存储在 rdi 中完成了传递.而大小为 24 bytesstruct test_big 则无法存放仅仅能容纳 8 bytesrdi 中,自然没法使用 rdi 进行传递.使用栈完成对 struct test_big 等大于 8 bytes 的结构体(当然也不仅仅只是结构体,联合体、int128_t 等数据也使用类似的方式传递)进行传递成为了仅有的办法.

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

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

即将执行push   -0x20(%rbp)

完成执行call   1152 <func2>

完成执行mov    %rdi,-0x8(%rbp)


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

通过这次的分析,可以发现,大结构体(大于 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 仍然依次采用 rdirsirdxrcxr8r9 进行传递.第 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])() 这类次要问题.请务必注意这只是一个为了方便理解虚函数表,笔者给出的伪代码而已.
可以看到在虚函数的调用中,需要访问虚函数表来完成函数的定位,但除此之外,参数的传递与函数值的返回仍然遵守前文所述的规则.

参考资料

1. 段刚.加密与解密[M].第4版.北京:电子工业出版社.
2. KipIrvine.汇编语言:基于x86处理器[M].原书第7版.贺莲,译.北京:机械工业出版社.
3. Randal E.Bryant.深入理解计算机系统[M].第三版.龚奕利,译.北京:机械工业出版社.
4. x64 calling convention[G/OL]. docs.microsoft.com. https://docs.microsoft.com/en-us/cpp/build/x64-calling-convention?view=msvc-160.
5. 维基百科编者. X86调用约定[G/OL]. 维基百科. 2020(20200922)[2020-09-22]. https://zh.wikipedia.org/zh-hans/X86调用约定.
6. WikipediaContributors. X86调用约定[G/OL]. 维基百科. 2020(20200922)[2020-09-22]. https://en.wikipedia.org/wiki/X86_calling_conventions.

GNU/Linux 环境检测系统限制

GNU/Linux 环境检测系统限制

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

ulimit

通过 which ulimit 便可知晓 ulimitshell 的内建命令.通过 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_MAXPOSIX.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]

参考资料

1. W.RichardStevens.Stephen.UNIX环境高级编程[M].第3版.戚正伟,译.北京:人民邮电出版社
2. ulimit(1p)[G/OL].POSIX Programmer’s Manual,https://man.archlinux.org/man/ulimit.1p.
3. ulimit(3)[G/OL].Linux Programmer’s Manual,https://man.archlinux.org/man/ulimit.3.
4. ulimit(3p)[G/OL].Linux Programmer’s Manual,https://man.archlinux.org/man/ulimit.3p.
5. Unix标准和实现[G/OL]https://klose911.github.io/html/apue/standard.html.
6. Wikipedia contributors. POSIX[G/OL]. Wikipedia, https://en.wikipedia.org/wiki/POSIX.
7. 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;
};

「快慢指针方式」的C语言描述为:
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;
}

「单指针方式」的C语言描述为:
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;
}

假设有一条长度为9个节点的链表,使用「快慢指针方式」,快指针完整的遍历链表 9 个节点,慢指针遍历前 5 个节点;使用「单指针方式」首先遍历链表一次共 9 个节点,后再次遍历至中点共 5 个节点.
两种方式都涉及对链表的 14 个节点的内存位置进行访问.其他的差异则可以忽略不计.

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

对比算法的机器代码描述

用 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]

参考资料

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

GNU/Linux_C 开发实战--myshell

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 >./tmpfileB <./tmpfile 的情况,因此管道和重定向符的实现紧密相关.
  • 重定向符有很多种格式,例如:>>>1>1>>2>2>><<<1>&21>>&22>&12>>&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.txtls -al >/dev/null |wc -cls -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行已经对临时文件执行了unlinkclose 后临时文件的引用计数递减为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
int main(void)
{
/* 屏蔽相关信号 */
signal(SIGHUP, SIG_IGN);
signal(SIGINT, SIG_IGN);
signal(SIGTTIN, SIG_IGN);
signal(SIGTTOU, SIG_IGN);
signal(SIGTSTP, SIG_IGN);

read_history(NULL); //调用 readline 库提供的函数,读取历史记录
char Prompt[P_SIZE]; //命令提示符
while (1)
{
strcpy(Prompt, RED);
char *pwd = getcwd(NULL, 0); //getcwd在第一个参数为NULL时会分配内存空间存储工作目录
strncat(Prompt, pwd, 100);
free(pwd);
strcat(Prompt, " MYSHELL$" CLOSE);

char *command = readline(Prompt);
add_history(command); //将读取到的命令添加至历史记录
write_history(NULL);
launch(command); //执行命令
free(command); //readline 为读取的命令分配内存空间,需释放防止内存泄漏
}

if (oldpath != NULL)
{
free(oldpath); //防止内存泄漏和重复释放
}
}

反思

必要说明

笔者在本文中launch()的实现很低效,实际上不先行对管道数量进行计数是完全可行的.
analyze()中不去复制字符串也是完全可行的.
还有,丢弃掉strtok_r(),自己实现查找和分割能比本文中的代码高效不止一点点.
笔者也曾想过是否要把文中的代码做一次重构之后在发出来,这样读者们便能看到一个更好的版本.
但笔者最终没有这样做主要是为了激励自己在日后的程序设计过程中更加深入的思考.当然,笔者相信,这点小小的修改一定难不到聪明的读者们,欢迎读者们修改本文中的代码,实现更高效的程序.

不够友善的错误处理

在本文中,笔者采用了最简单也最不友好的方式处理一切的错误.
但这种处理方式并不总是合理的,例如在myshell中,输入错误的指令导致报错是一个常见但并不致命的错误.但笔者依旧采取了这种最简单的错误处理方式,确实未能人性化的设计程序.

不够合理的调用方式

注意launch()

1
2
3
4
if (BuiltInCommand(&cmd[i]))
{
execute(&cmd[i]);
}

笔者认为此处的设计并不合理,笔者认为更合理的做法可能是将 execute() 交由 BuiltInCommand() 在判断出本段命令不是内置命令之后自动调用,而不是判断BuiltInCommand()的返回至然后在调用execute()


回看近3个月前笔者自己写出的myshell ,笔者不得不承认自己的能力是多么的有限.万幸的是,笔者在这3个月中也得到了足够的提高,才能看出原来写的程序的问题.

测试环境

GNU bash : 5.1.4(1)-release

zsh : 5.8

OS : Arch Linux

Kernel : 5.9.14-arch1-1

附录--完整源码
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
#define NDEBUG
#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>
extern char **environ;
#define P_SIZE 128 //命令提示符长度限制
#define RED "\033[31m" //红色
#define CLOSE "\033[0m" //关闭
struct COMMAND
{
int argc; //参数数量
int Redirect_FD[3]; //标准输入、标准输出、错误输出的重定向情况
char **argv;
};
char *oldpath;
void PathAnalyze(char **path);
int OpenFile(char *string, int flags);
void execute(struct COMMAND *cmd);
_Bool BuiltInCommand(struct COMMAND *cmd);
void launch(char *command);
void myerror(char *string, int line);
_Bool analyze(char *string, struct COMMAND *cmd);
int main(void)
{
/* 屏蔽相关信号 */
signal(SIGHUP, SIG_IGN);
signal(SIGINT, SIG_IGN);
signal(SIGTTIN, SIG_IGN);
signal(SIGTTOU, SIG_IGN);
signal(SIGTSTP, SIG_IGN);
read_history(NULL); //调用 readline 库提供的函数,读取历史记录
char Prompt[P_SIZE]; //命令提示符
while (1)
{
strcpy(Prompt, RED);
char *pwd = getcwd(NULL, 0); //getcwd在第一个参数为NULL时会分配内存空间存储工作目录
strncat(Prompt, pwd, 100);
free(pwd);
strcat(Prompt, " MYSHELL$" CLOSE);

char *command = readline(Prompt);
add_history(command); //将读取到的命令添加至历史记录
write_history(NULL);
launch(command); //执行命令
free(command); //readline 为读取的命令分配内存空间,需释放防止内存泄漏
}

if (oldpath != NULL)
{
free(oldpath); //防止内存泄漏和重复释放
}
}
void launch(char *command)
{
int pipe = 0; //管道计数器
for (char *pr = command; *pr != '\0'; pr++)
{
if (*pr == '|')
{
pipe++;
}
}
struct COMMAND *cmd = (struct COMMAND *)calloc(pipe + 1, sizeof(struct COMMAND));
if (cmd == NULL)
{
myerror("malloc", __LINE__);
}
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;
}
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 (BuiltInCommand(&cmd[i]))
{
execute(&cmd[i]);
}
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);
}

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;
}
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);
}
_Bool analyze(char *OriginString, struct COMMAND *cmd)
{
//string 代表使用管道分割后的「命令段」
//返回值表示重定向情况,0代表无重定向,1代表有重定向

char *string = strdup(OriginString);
if (string == NULL)
{
myerror("malloc", __LINE__);
}
char *end = string + strlen(string);
char *result = NULL;
#ifndef NDEBUG
printf("DEBUG:string:%s\n", string);
#endif
//处理标准输出、错误输出重定向
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);
}
}
//处理输入重定向
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);
}
}

/* 解析命令行参数 */
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);
return 0;
}
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);
}
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__);
}

_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. 童永清.Linux C 编程实战[M].第1版.北京:人民邮电出版社
2. W.RichardStevens.Stephen.UNIX环境高级编程[M].第3版.戚正伟,译.北京:人民邮电出版社
3. Linux Programmer’s Manual
4. General Commands Manual
5. 鸟哥.鸟哥的Linux私房菜[M].第四版.北京:人民邮电出版社

GNU/Linux_C 开发实战--myls

GNU/Linux C 开发实战—myls

需求

  • 对不同类型或不同权限的的文件,输出不同颜色的文字
  • 实现ls的以下7个参数任意组合
    • -a 不隐藏任何以 . 开始的项目
    • -i 显示每个文件的索引编号(inode 号)
    • -l 使用较长格式列出信息
    • -s 以块数形式显示每个文件分配的尺寸
    • -t 按时间排序,最新的最前
    • -r 逆序排列
    • -R 递归显示子目录

必要的头文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <dirent.h>
#include <errno.h>
#include <fcntl.h>
#include <grp.h>
#include <locale.h>
#include <pwd.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <time.h>
#include <unistd.h>

开发过程

获取并解析用户输入

分别声明7个_Bool类型的全局变量存储解析到的各个参数的使用情况

1
2
3
4
5
6
7
_Bool Options_a;
_Bool Options_i; //显示i-node
_Bool Options_l;
_Bool Options_r; //逆序
_Bool Options_R;
_Bool Options_s; //以块数形式显示每个文件分配的尺寸
_Bool Options_t; //时间排序

通过判断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
_Bool p = 0; //表明是否读取到路径
char *path;//指向存储路径字符串的指针
for (int i = 1; i < argc; i++)
{
if (*argv[i] == '-') //判断是参数还是路径
{ //是参数
for (unsigned int n = 1; n < strlen(argv[i]); n++) //遍历每一格字母
switch (argv[i][n])
{
case 'a':
Options_a = 1;
break;
case 'i':
Options_i = 1;
break;
case 'l':
Options_l = 1;
break;
case 'r':
Options_r = 1;
break;
case 'R':
Options_R = 1;
break;
case 's':
Options_s = 1;
break;
case 't':
Options_t = 1;
break;
default: //错误的参数
printf("%s error:Unknow options: %s\n", __FILE__, argv[i]);
exit(EXIT_FAILURE);
break;
}
}
else
{ //是路径
p = 1; //表明已经读到了路径
path = argv[i];
}
}

info

在ls中,如果用户输入了路径,那么应该输出用户输入的路径下的文件,否则路径的缺省值应该为当前目录

1
2
3
4
5
6
if (!p) //如果没读取到路径(等价于路径是通过getcwd获得的)
{
path = getcwd(NULL, 0); //获取当前路径
if (path == NULL)
myerror("getcwd", " ", __LINE__);
}

上面的代码调用了笔者为了简化错误处理流程写的myerror()函数,该函数定义如下

1
2
3
4
5
6
void myerror(const char *string1, const char *string2, int line)
{
printf("\033[31mline:%d:file:%s\n%s:%s\033[0m\n", line, string2, string1, strerror(errno));//strerror()需要 string.h

exit(EXIT_FAILURE);
}

笔者相信细致的读者一定会觉得!p的设计时不必要的,因为可以通过预先执行path=NULL;,然后在解析完成后判断if (path==NULL)区分是否已经读取到路径,从而删去p变量,但这样的做法是有缺陷的.

  • 当用户输入路径时,path指向某一个argv中的某一个指针指向的字符串.不需要执行free(path)
  • 当用户不输入路径时,path指向由getcwd函数自动分配内存存储的当前路径.需要执行free(path)

为了区分是否需要执行free,防止产生内存泄漏,笔者设置p变量来完成对是否需要free的检测.

递归打开目录

在需求中的7个参数中,-R的实现无疑是最为困难的.
笔者通过设计一个以存储目标文件夹路径的字符串为参数的函数,并通过递归调用该函数实现 -R 参数.

首先,笔者定义了几个宏:

1
2
3
#define StackPush(x) FileStack[++FileStackTop] = (x)
#define StackTop FileStack[FileStackTop]
#define StackPop free(FileStack[FileStackTop--])

下面是OpenADirectory的大致流程:

warning
TIP
笔者为了方便各位读者理解该函数运行的流程,在下面的代码中笔者省略了很多细节.
请读者们此时更多的关注该函数的「整体流程与思想」,而不是细枝末节.
请不要担心、不要着急,后文中笔者将逐一说明被笔者省略的内容.

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
typedef struct
{
struct stat FileStat;
struct dirent File_di;

} FileInfo;

void OpenADirectory(const char *path)
{
/* 保存原目录 */
char *oldpath = getcwd(NULL, 0);
if (oldpath == NULL)
myerror("getcwd", " ", __LINE__);

DIR *CurrentDir = opendir(path);
/* 此处省略打开目录失败的错误处理 */

/* 切换目录 */
if (chdir(path) == -1)
/* 此处省略切换目录失败的错误处理 */

/* 文件堆 */
FileInfo **FileStack = (FileInfo **)malloc(sizeof(FileInfo *) * FileNumberMax);
if (FileStack == NULL)
myerror("malloc", " ", __LINE__);
int FileStackTop = -1;


/* 文件读取 */
struct dirent *CurrentFile;
while ((CurrentFile = readdir(CurrentDir)) != NULL)
{
FileInfo *temp = (FileInfo *)malloc(sizeof(FileInfo));
if (temp == NULL)
myerror("malloc", "", __LINE__);
temp->File_di = *CurrentFile;
if (lstat(CurrentFile->d_name, &(temp->FileStat)) == -1)
{
printf("\033[31mError:Line:%d: can't get stat of %s,%s\033[0m\n", __LINE__, CurrentFile->d_name, strerror(errno));
free(temp);
continue;
}
if (FileStackTop < FileNumberMax)
StackPush(temp);
else
myerror("\033[31mToo much File\033[0m\n", " ", __LINE__);
}
/* readdir错误检查 */
if (errno) //需要 error.h
printf("\033[31mline:%d:error:%s\033[0m\n", __LINE__, strerror(errno));

该函数在运行的开始,首先保存当前的工作目录的路径,然后打开作为参数的路径中指定的文件夹.

OpenADirectory()新建了一个名叫FileStack的指针,该指针指向指向FileInfo类型的指针,换而言之,FileStack是一个二级指针.由于使用malloc()为其分配了sizeof(FileInfo *) * FileNumberMax字节的空间,即FileNumberMaxFileInfo *类型所占的空间,那么此时,FileStack就相当与一个「内含FileNumberMax个指针元素的数组」.在此,笔者将该数组作为存储path指定的文件夹内每个文件对应的FIleInfo堆栈

danger
ERROR
可能会有读者在想,FileStack不就是个指针数组嘛.直接使用FileInfo (*FileStack)[FileNumberMax];便可以自动分配一个指针数组,何必使用malloc()呢?
这不是笔者在使用二级指针故作高深,而是确有必要.FileInfo (*FileStack)[FileNumberMax];语句定义的是自动变量,占用栈区空间,而栈区空间通常较小,在多层递归中容易出现栈溢出的错误.而malloc()分配的空间在堆区上,堆区远大于栈区,这样才能保证程序的正常运行.
还有人可能会问,那能否这样调用malloc呢?

FileInfo *array=malloc(sizeof(FileInfo) * FileNumberMax);

这样的做法,由FileInfo *类型的指针数组改为FileInfo数组,这样确实也不占用栈区空间,也避免了二级指针带来的理解困难,但却存在着更为严重的内存浪费问题.在绝大多数文件夹中,文件数量远远少于FileNumberMax,在相同的文件夹,如果使用指针数组的方案,浪费的空间仅为多个指针所占据的空间,而使用FileInfo数组的方案却浪费了多个FileInfo的空间,要知道FileInfo所占的空间远大于FileInfo *.所以使用FileInfo的方案也不合理.

假设打开文件夹成功,则将程序的工作目录切换至已打开的文件夹(也就是参数中指定的文件夹),这是因为笔者需要调用lstat函数获取文件夹下每个文件的属性.
lstat以文件路径为参数.切换目录后,笔者便可以以文件名作为相对路径直接调用lstat函数.如不切换目录则会找不到文件,当然也可以采取字符串拼接的做法,但这样做需要对文件夹下每个文件都执行一次字符串拼接,效率较低,而且字符串的长度不定,分配空间也易出现浪费或溢出.笔者直接切换目录避免了这些麻烦,也提升了效率.

在此后笔者使用循环遍历文件夹中的每个文件,获取每个文件的属性,并将每个文件对应的struct statstruct dirent一同存储在的struct FileInfo
这样做的好处有很多,完成了这步后,输出文件信息所必要的所以内容已被集中在了一个struct FileInfo结构体中,为后面对详细信息的输出和文件信息的排序排序给予了极大的便利.

1
qsort(FileStack, FileStackTop + 1, sizeof(FileInfo *), cmp);

之后笔者使用qsort函数对FileStack进行排序处理,作为函数指针传递的cmp函数要如何写,请容笔者在后文交代.
这这里,需要注意的是,真正被排序的是FileInfo *,而每个FileInfo元素都还存储在原来的位置.排序FileInfo *,代替FileInfo是一个十分有用的小技巧,能提升排序的效率.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    for (int i = FileStackTop; i >= 0; i--)
{
/* 此处省略输出文件信息的函数 */
}

while (FileStackTop >= 0)
{
if (Options_R && S_ISDIR(StackTop->FileStat.st_mode) && strcmp(StackTop->File_di.d_name, ".") != 0 && strcmp(StackTop->File_di.d_name, "..") != 0)
OpenADirectory(StackTop->File_di.d_name);
StackPop;
}

if (chdir(oldpath) == -1) //切回目录
myerror("chdir", path, __LINE__);

/* 释放与关闭 */
free(oldpath);
closedir(CurrentDir);
free(FileStack);
}

如上,笔者使用for循环从堆的顶部遍历每个元素,并输出其中的所需的信息,这样便做到了排序输出.

其后,笔者再次从堆顶逐一访问每个元素,在启用了-R参数时,检测堆栈顶部的元素是否为文件夹,如果堆栈顶部为文件夹,且不是...则把堆栈顶部的元素对应的文件夹的路径作为参数递归调用OpenADirectory().完成后对先free堆栈顶的元素所指向的FileInfo分配的空间并对堆栈执行pop操作.
最终释放堆栈空间及其他内存分配.

secondary
SECONDARY

获取文件属性的函数还有stat,为什么要选择lstat而不是stat呢?

原因很简单lstat函数获取符号链接(Symbolic link)本身的属性,而stat获取被链接的文件的属性.

顺带一提,得益于FileStack已经被qsort函数完成了排序,所以接下来通过递归调用打开子文件夹也是有序的.这使得myls程序运行期间所有文件的输出顺序是正确的.

至此,笔者终于完整的描述了OpenADirectory()的运行的流程.

打开目录过程中的细节

首先需要关注的是错误处理.其中readdir()函数的错误处理需要特别的关注.

tip

TIP

readir()在读到目录结尾和出错时返回NULL.仅在出错时设置errno

If the end of the directory stream is reached, NULL is returned and errno is not changed. If an error occurs, NULL is returned and errno is set appropriately. To distinguish end of stream from an error, set errno to zero before calling readdir() and then check the value of errno if NULL is returned.

readdir()的返回值NULL具有双重含义,只能使用检测errno的值是否为0来判断readdir()是否执行正常.
在检测前需保证errno==0


调用opendir时,易因权限不足等原因致使opendir无法正常执行.在发生错误时,笔者并未选择直接退出程序,而是选择报错并跳过打开失败的文件夹.
记得要释放getcwd中为了存储当前工作目录路径的字符串分配的内存空间,清除errno的值.

1
2
3
4
5
6
7
8
DIR *CurrentDir = opendir(path);
if (CurrentDir == NULL)
{
printf("\033[31mLine:%d:readfailed:%s/%s\t %s\033[0m\n", __LINE__, oldpath, path, strerror(errno));
errno = 0;
free(oldpath);
return;
}

切换目录过程中,也可能因权限不足而导致切换失败,例如:用户缺少文件夹的x权限时,便无法进入相应的文件夹.因此,这一步的错误检查同样必不可少.
同样不能忘记释放内存空间、清除errno的值,额外的还需要关闭已打开的文件夹.

1
2
3
4
5
6
7
8
9
/* 切换目录 */
if (chdir(path) == -1)
{
printf("\033[31mLine:%d:chdir:%s\t %s\033[0m\n", __LINE__, path, strerror(errno));
errno = 0;
free(oldpath);
closedir(CurrentDir);
return;
}

当然不必笔者多提的就是malloc()的错误处理,相信各位读者一定知道该怎么做,笔者便不再赘述.

OpenADirectory的结尾,笔者将工作目录切换回去,方便递归中打开后续文件夹.

实现文件详细信息输出

格式化输出文件大小

这部分十分容易实现,只需要从相应的struct stat中访问st_size成员,并将其作为参数传递给相应的格式化输出函数即可.

1
2
3
4
5
6
7
8
9
10
11
void FormatBytes(off_t size)
{
char *array[] = {"B", "KB", "MB", "GB", "TB", "PB"};
int n = 0;
while (size >= 1024)
{
n++;
size /= 1024;
}
printf("%ld%s\t", size, array[n]);
}
格式化输出修改时间
1
2
3
4
5
6
7
void FormatTime(time_t mtime)
{
char string[20];
struct tm *timeinfo = gmtime(&mtime);
strftime(string, 17, "%b %e %R", timeinfo);
printf("%s\t", string);
}

文件的修改时间被存储在struct statst_mtim.tv_sec成员中.有必要多说一句的是,为了输出本地时间(UTC +8),还需要设置本地化的时间,笔者将这部分需求在main函数中实现.

1
2
3
/* 本地化时间设置 */
if (setlocale(LC_TIME, "") == NULL)
myerror("setlocale", " ", __LINE__);
格式化输出文件所属的用户和用户组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void FormateUserAndGroup(uid_t userid, gid_t groupid)
{
struct passwd *owner = getpwuid(userid);//#include <pwd.h>

if (owner == NULL)
{
printf("%s\n", getcwd(NULL, 0));
printf("uid:%u\n", userid);
}

struct group *group = getgrgid(groupid);//include <grp.h>
if (group == NULL)
myerror("getgruid", " ", __LINE__);

printf("%s\t%s\t", owner->pw_name, group->gr_name);
}

函数以struct stat中的st_uid成员和st_gid成员为实际参数,分别通过uidgid调用getpwuid()函数和getgrgid()函数,获取相关结构体,并输出其中的用户名和用户组名称.

tip

TIP

  • getpwuid()函数 由 pwd.h 提供
  • getgrgid()函数 由 grp.h 提供
格式化输出文件权限

文件权限的格式化输出最为简单.只是机械的判断并输出即可.

考录到存在SUIDSGIDSBIT 这些特殊权限的存在,笔者并未尝试使用位移运算符来复用部分代码,使得这部分代码显得很长.

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
void prauthority(mode_t mode)
{
if (S_ISREG(mode))
putchar('-');
else if (S_ISDIR(mode))
putchar('d');
else if (S_ISLNK(mode))
putchar('l');
else if (S_ISFIFO(mode))
putchar('f');
else if (S_ISBLK(mode))
putchar('b');
else if (S_ISCHR(mode))
putchar('c');
else if (S_ISSOCK(mode))
putchar('s');
//Owner
if (S_IRUSR & mode)
putchar('r');
else
putchar('-');
if (S_IWUSR & mode)
putchar('w');
else
putchar('-');
if (S_IXUSR & mode)
{
if (S_ISUID & mode)
putchar('s');
else
putchar('x');
}
else
putchar('-');

//group
if (S_IRGRP & mode)
putchar('r');
else
putchar('-');
if (S_IWGRP & mode)
putchar('w');
else
putchar('-');
if (S_IXGRP & mode)
{
if (S_ISGID & mode)
putchar('s');
else
putchar('x');
}
else
putchar('-');

//Other
if (S_IROTH & mode)
putchar('r');
else
putchar('-');
if (S_IWOTH & mode)
putchar('w');
else
putchar('-');
if (S_IXOTH & mode)
{
if (S_ISVTX & mode)
putchar('t');
else
putchar('x');
}
else
putchar('-');
putchar('\t');
}
格式化输出文件的i-node编号和以块为单位文件的大小

直接从struct stat 中读取相关信息并输出即可.

1
2
3
4
if (Options_i)
printf("%-10lu\t", FileStack[i]->FileStat.st_ino);
if (Options_s)
printf("%-8ld\t", FileStack[i]->FileStat.st_blksize);
根据文件的类型和权限输出不同颜色的文件名

根据struct dirent中的char d_name[256]输出即可.无非是根据不同类型输出不同的颜色而已.

1
2
3
4
5
6
7
8
9
10
11
if (S_ISREG(FileStack[i]->FileStat.st_mode) &&
((S_IXUSR & FileStack[i]->FileStat.st_mode) ||
(S_IXGRP & FileStack[i]->FileStat.st_mode) ||
(S_IXOTH & FileStack[i]->FileStat.st_mode)))
printf("\033[32m%s\033[0m\n", FileStack[i]->File_di.d_name);
else if (S_ISREG(FileStack[i]->FileStat.st_mode))
printf("%s\n", FileStack[i]->File_di.d_name);
else if (S_ISDIR(FileStack[i]->FileStat.st_mode))
printf("\033[34m%s\033[0m\n", FileStack[i]->File_di.d_name);
else if (S_ISLNK(FileStack[i]->FileStat.st_mode))
printf("\033[31m%s\033[0m\n", FileStack[i]->File_di.d_name);

实现排序输出

在用OpenADirectory()中笔者调用了qsort().其中,qsort()cmp进行隐式类型转换函数指针,完成了对FileStack这个指针数组的排序.

1
qsort(FileStack, FileStackTop + 1, sizeof(FileInfo *), cmp);

在此,笔者来实现cmp()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int cmp(const void *a, const void *b)
{
const FileInfo *A = *(FileInfo **)a;
const FileInfo *B = *(FileInfo **)b;
int i;
if (Options_t)
{
time_t t = B->FileStat.st_mtim.tv_sec - A->FileStat.st_mtim.tv_sec;
if (t > 0)
i = -1;
else if (t == 0)
i = 0;
else
i = 1;
}
else
i = strcmp(B->File_di.d_name, A->File_di.d_name);
if (Options_r)
i = -i;
return i;
}

其中,根据用户是否输入了参数-r决定是否进行逆序排列,根据用户是否输入了参数-t决定排序的方式.

至此,myls终于完成了,完整的代码见本文末的附录.

反思

动态分配 FileStack

在上面的实现中,笔者粗暴的使用了一个FileNumbertMax作为FileStack中指针的数量,但这并非最优解.

大多数文件夹中,文件数量远远小于 FileNumbertMax 意味着浪费了很多空间.

更合理的做法是,为FileStack设置一个大于「大多数文件夹中存放文件数量」的初始值,在遇到FileStack满后,使用realloc()扩充FileStack的空间即可.

当然,这不可避免的是在一定程度上减缓myls的运行速度,这个运行速度与消耗空间的平衡需要读者自行考量.

获取文件属性

warning

WARNING

该部分内容含较多的笔者的未验证个人观点,不保证正确.欢迎读者们指出错误.

OpenADirectory()中,使用readdir()读取目录的记录项,获取的struct dirent中包含文件名与i-node编号.

然后,使用lstat()根据文件路径(笔者使用文件名作为相对路径)读取文件的属性.

在使用i-node的文件系统中,文件的属性存储在i-node中,lstat()可能的读取文件属性的方式为:

  1. 打开并遍历文件所在目录
  2. 读取目录的记录项,直到找到指定的文件所对应的记录项
  3. 从文件所对应的记录项中得到文件的i-node编号
  4. 根据文件的i-node编号找到对应的i-node,完成读取文件的属性

读者们一定能发现根据获取的struct dirent已经可以读取到i-node编号了,但使用lstat()函数却还要重复上面的1-3步.

笔者未能想到如何更好的读取文件的属性,欢迎对此有了解的读者告诉笔者.

点击三角形展开附录

附录--完整源码
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
/* myls.c */
#include <dirent.h>
#include <errno.h>
#include <fcntl.h>
#include <grp.h>
#include <locale.h>
#include <pwd.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <time.h>
#include <unistd.h>

// #define NDEBUG

#define StackPush(x) FileStack[++FileStackTop] = (x)
#define StackTop FileStack[FileStackTop]
#define StackPop free(FileStack[FileStackTop--])
#define FileNumberMax 40960

_Bool Options_a;
_Bool Options_i; //显示i-node
_Bool Options_l;
_Bool Options_r; //逆序
_Bool Options_R;
_Bool Options_s; //以块数形式显示每个文件分配的尺寸
_Bool Options_t; //时间排序

typedef struct
{
struct stat FileStat;
struct dirent File_di;

} FileInfo;
void prauthority(mode_t mode);
void myerror(const char *string, const char *filename, int line);
void OpenADirectory(const char *path);
int cmp(const void *a, const void *b);
void FormateUserAndGroup(uid_t userid, gid_t groupid);
void FormatTime(time_t mtime);
void FormatBytes(off_t size);

int main(int argc, char **argv)
{

/* 本地化时间设置 */
if (setlocale(LC_TIME, "") == NULL)
myerror("setlocale", " ", __LINE__);
signal(SIGTTIN, SIG_IGN); //忽略SIGTTIN信号

_Bool p = 0; //表明是否读取到路径
char *path; //指向存储路径字符串的指针
for (int i = 1; i < argc; i++)
{
if (*argv[i] == '-') //判断是参数还是路径
{ //是参数
for (unsigned int n = 1; n < strlen(argv[i]); n++) //遍历每一格字母
switch (argv[i][n])
{
case 'a':
Options_a = 1;
break;
case 'i':
Options_i = 1;
break;
case 'l':
Options_l = 1;
break;
case 'r':
Options_r = 1;
break;
case 'R':
Options_R = 1;
break;
case 's':
Options_s = 1;
break;
case 't':
Options_t = 1;
break;
default: //错误的参数
printf("%s error:Unknow options: %s\n", __FILE__, argv[i]);
exit(EXIT_FAILURE);
break;
}
}
else
{ //是路径
p = 1; //表明已经读到了路径
path = argv[i];
}
}
if (!p) //如果没读取到路径(等价于路径是通过getcwd获得的)
{
path = getcwd(NULL, 0); //获取当前路径
if (path == NULL)
myerror("getcwd", " ", __LINE__);
}
OpenADirectory(path);
if (!p)
free(path);
}

int cmp(const void *a, const void *b)
{
const FileInfo *A = *(FileInfo **)a;
const FileInfo *B = *(FileInfo **)b;
int i;
if (Options_t)
{
time_t t = B->FileStat.st_mtim.tv_sec - A->FileStat.st_mtim.tv_sec;
if (t > 0)
i = -1;
else if (t == 0)
i = 0;
else
i = 1;
}
else
i = strcmp(B->File_di.d_name, A->File_di.d_name);
if (Options_r)
i = -i;
return i;
}

void OpenADirectory(const char *path)
{
/* 保存原目录 */
char *oldpath = getcwd(NULL, 0);
if (oldpath == NULL)
myerror("getcwd", " ", __LINE__);

DIR *CurrentDir = opendir(path);
if (CurrentDir == NULL)
{
printf("\033[31mLine:%d:readfailed:%s/%s\t %s\033[0m\n", __LINE__, oldpath, path, strerror(errno));
errno = 0;
free(oldpath);
return;
}

/* 切换目录 */
if (chdir(path) == -1)
{
printf("\033[31mLine:%d:chdir:%s\t %s\033[0m\n", __LINE__, path, strerror(errno));
errno = 0;
free(oldpath);
closedir(CurrentDir);
return;
}

/* 文件堆 */
FileInfo **FileStack = (FileInfo **)malloc(sizeof(FileInfo *) * FileNumberMax);
if (FileStack == NULL)
myerror("malloc", " ", __LINE__);
int FileStackTop = -1;

if (Options_R) /* 如果开启了递归显示子目录,则输出切换结果 */
{
char *NewPath = getcwd(NULL, 0);
if (NewPath == NULL)
myerror("getcwd", " ", __LINE__);
printf("%s:\n", NewPath);
free(NewPath);
}

/* 文件读取 */
struct dirent *CurrentFile;
while ((CurrentFile = readdir(CurrentDir)) != NULL)
{
FileInfo *temp = (FileInfo *)malloc(sizeof(FileInfo));
if (temp == NULL)
myerror("malloc", "", __LINE__);
temp->File_di = *CurrentFile;
if (lstat(CurrentFile->d_name, &(temp->FileStat)) == -1)
{
printf("\033[31mError:Line:%d: can't get stat of %s,%s\033[0m\n", __LINE__, CurrentFile->d_name, strerror(errno));
free(temp);
continue;
}
if (FileStackTop < FileNumberMax)
StackPush(temp);
else
myerror("\033[31mToo much File\033[0m\n", " ", __LINE__);
}
/* readdir错误检查 */
if (errno) //需要 error.h
printf("\033[31mline:%d:error:%s\033[0m\n", __LINE__, strerror(errno));

qsort(FileStack, FileStackTop + 1, sizeof(FileInfo *), cmp);

for (int i = FileStackTop; i >= 0; i--)
{
if (Options_a == 0 && *FileStack[i]->File_di.d_name == '.')
continue;
if (Options_l)
{
if (Options_i)
printf("%-10lu\t", FileStack[i]->FileStat.st_ino);
if (Options_s)
printf("%-8ld\t", FileStack[i]->FileStat.st_blksize);
prauthority(FileStack[i]->FileStat.st_mode);
FormateUserAndGroup(FileStack[i]->FileStat.st_uid, FileStack[i]->FileStat.st_gid);
FormatBytes(FileStack[i]->FileStat.st_size);
FormatTime(FileStack[i]->FileStat.st_mtim.tv_sec);
}

if (S_ISREG(FileStack[i]->FileStat.st_mode) &&
((S_IXUSR & FileStack[i]->FileStat.st_mode) ||
(S_IXGRP & FileStack[i]->FileStat.st_mode) ||
(S_IXOTH & FileStack[i]->FileStat.st_mode)))
printf("\033[32m%s\033[0m\n", FileStack[i]->File_di.d_name);
else if (S_ISREG(FileStack[i]->FileStat.st_mode))
printf("%s\n", FileStack[i]->File_di.d_name);
else if (S_ISDIR(FileStack[i]->FileStat.st_mode))
printf("\033[34m%s\033[0m\n", FileStack[i]->File_di.d_name);
else if (S_ISLNK(FileStack[i]->FileStat.st_mode))
printf("\033[31m%s\033[0m\n", FileStack[i]->File_di.d_name);
}

while (FileStackTop >= 0)
{
if (Options_R && S_ISDIR(StackTop->FileStat.st_mode) && strcmp(StackTop->File_di.d_name, ".") != 0 && strcmp(StackTop->File_di.d_name, "..") != 0)
OpenADirectory(StackTop->File_di.d_name);
StackPop;
// FileStackTop--;
}

if (chdir(oldpath) == -1) //切回目录
myerror("chdir", path, __LINE__);

/* 释放与关闭 */
free(oldpath);
closedir(CurrentDir);
free(FileStack);
}
void myerror(const char *string1, const char *string2, int line)
{
printf("\033[31mline:%d:file:%s\n%s:%s\033[0m\n", line, string2, string1, strerror(errno)); //strerror()需要 string.h

exit(EXIT_FAILURE);
}

void FormatBytes(off_t size)
{
char *array[] = {"B", "KB", "MB", "GB", "TB", "PB"};
int n = 0;
while (size >= 1024)
{
n++;
size /= 1024;
}
printf("%ld%s\t", size, array[n]);
}

void FormatTime(time_t mtime)
{
char string[20];
struct tm *timeinfo = gmtime(&mtime);
strftime(string, 17, "%b %e %R", timeinfo);
printf("%s\t", string);
}

void FormateUserAndGroup(uid_t userid, gid_t groupid)
{
struct passwd *owner = getpwuid(userid);//#include <pwd.h>

if (owner == NULL)
{
printf("%s\n", getcwd(NULL, 0));
printf("uid:%u\n", userid);
}

struct group *group = getgrgid(groupid);//include <grp.h>
if (group == NULL)
myerror("getgruid", " ", __LINE__);

printf("%s\t%s\t", owner->pw_name, group->gr_name);
}
void prauthority(mode_t mode)
{
if (S_ISREG(mode))
putchar('-');
else if (S_ISDIR(mode))
putchar('d');
else if (S_ISLNK(mode))
putchar('l');
else if (S_ISFIFO(mode))
putchar('f');
else if (S_ISBLK(mode))
putchar('b');
else if (S_ISCHR(mode))
putchar('c');
else if (S_ISSOCK(mode))
putchar('s');
//Owner
if (S_IRUSR & mode)
putchar('r');
else
putchar('-');
if (S_IWUSR & mode)
putchar('w');
else
putchar('-');
if (S_IXUSR & mode)
{
if (S_ISUID & mode)
putchar('s');
else
putchar('x');
}
else
putchar('-');

//group
if (S_IRGRP & mode)
putchar('r');
else
putchar('-');
if (S_IWGRP & mode)
putchar('w');
else
putchar('-');
if (S_IXGRP & mode)
{
if (S_ISGID & mode)
putchar('s');
else
putchar('x');
}
else
putchar('-');

//Other
if (S_IROTH & mode)
putchar('r');
else
putchar('-');
if (S_IWOTH & mode)
putchar('w');
else
putchar('-');
if (S_IXOTH & mode)
{
if (S_ISVTX & mode)
putchar('t');
else
putchar('x');
}
else
putchar('-');
putchar('\t');
}

参考资料

1. 童永清.Linux C 编程实战[M].第1版.北京:人民邮电出版社
2. W.RichardStevens.Stephen.UNIX环境高级编程[M].第3版.戚正伟,译.北京:人民邮电出版社
3. Linux Programmer’s Manual
4. General Commands Manual
5. 鸟哥.鸟哥的Linux私房菜[M].第四版.北京:人民邮电出版社

浅谈Git的应用

浅谈Git的应用

info

INFO

本文内容含有较多的引用,笔者会标注本文中所有引用内容,并在引文末尾使用脚注注明引文出处.
受引用来源的限制,本文将采取较为复杂的许可.

引文部分已全部标注.
笔者尊重所有创作者的知识产权,希望能以合理的方式引用他人的作品,但因笔者的法律知识有限,在操作中可能出现疏忽和错误,如有任何建议,请在文章末尾的评论区中评论.在此也感谢本文的引文的作者.

写在前面的话:笔者写这篇文章并非为了教会读者Git的详细用法,而是为了告诉读者们Git能满足什么需求.笔者期望阅读本文的读者在某一天出现有关版本控制的需求时,能想起曾在某个不知名的博客中看到过Git有个功能可以解决当前遇到的问题.与其说本文在介绍Git的使用方式,不如说本文在介绍Git已有的部分常用功能.至于有意详细的学习Git的用法的读者,本文无法满足你的需求,笔者建议阅读Git Pro Book来满足你的需求.

为什么需要版本控制

你是否曾为误删重要文件而懊悔,你是否曾为数据丢失而苦恼?你是否曾错误改动文件而无法更正?

你丢失的或许是几日的心血,或许是照片中美好的回忆.但对于一个项目而言,任何文件的丢失与错误的修改都可能是致命.

版本控制就如同游戏中的存档,是开发中的后悔药.

我想有的人曾因担心之后的操作把已有的工作搞砸,提前复制或者备份一份已有的文件,然后再进行不太确定的操作.
很多软件为用户提供了撤销的功能,从某种层面上说,这也是一种版本控制,你能想象如WordPowerPointPhotoShop等大型软件不提供撤销功能会造成多么大的不便吗?

当然,版本控制也绝非一个撤销键这样简单.

tip
小故事

客人来到餐厅用餐.
客人:来一份宫保鸡丁
你:这好办.
进入后厨,完成客户的需求中…
客人:孩子喜欢吃牛肉,麻烦你把鸡丁换成牛肉
你:不放鸡丁放牛肉还是宫保鸡丁吗?您确定要这样吗?
客人:这很难吗?无非是把鸡丁换成牛肉,别的该怎么做还是怎么做,这很难吗.
你:好吧.

此时,你默默的从锅中挑出即将炒熟的鸡丁,换成牛肉丁

客人:你怎么这么慢?要不算了,还是放鸡丁吧?我都要饿死了,怎么快怎么来?!
你:……

此时,你默默从锅中挑出即将炒熟的牛肉丁,把鸡丁放回去

据说这很像程序员们遇到的犹豫不定的客户,频繁的改动需求导致项目反复改动.

虽然版本控制无助于开发新的功能,但在使用了版本控制之后,至少在客户改动需求又反悔时,版本控制能让开发者快速的投入新的开发工作,而不是花费大量精力把已有的改动还原回去(当然,这只是使用版本控制的好处之一).

通常来说,大多数软件提供的撤销功能是有很多不足的.

  • 无法直接撤销至任意一步,只能逐步撤销
  • 无法撤销至这次打开软件之前的版本,撤销的步数受限
  • 不能保存撤销和重做的记录
  • 撤销后的修改会影响撤销,无法保留现有修改的同时撤销过去的修改

当然,会有聪明的人说:「何必这么麻烦,我提前复制一份就好.」

不可否认,这通常是一个有效的做法,但也会带来一些麻烦.

一个1MB左右的文件通过复制备份10个版本也才10MB.但1GB的文件通过复制的方式备份10份就要10GB了.

danger
WARNING
虽然笔者用备份作为说明版本控制的一个例子,版本控制在某种程度上来说具有备份的作用,备份在某种程度上来说也实现了版本控制,但这也只是说明两者的作用有交集,切不可混为一谈.笔者此处使用这种说法只是为了帮助对版本控制感到陌生的读者理解版本控制的部分作用,请原谅笔者这种不太严谨的做法.

通过复制备份原文件,手动完成版本控制,在文件大小近似不变的情况下,所需要的空间和复制次数具有线性相关关系,长期依靠复制完成版本控制不是一个好的办法.

secondary
INFO

截至 2020-12-03 03:13:08Linux 内核源码树(Linux kernel source tree)968,247提交(commits),在Github上仅存储了2.94GB的数据.

https://github.com/torvalds/linux

在多人协作的时候,使用版本控制系统具有更多的优势.

  • 保留了每次修改的结果,方便的对比查看不同版本之间的差异
  • 方便的查看他人修改了什么内容
  • 方便的查看文件内容的修改者
  • 允许对所有参与者划分权限,禁止部分人修改部分重要内容
  • 进行代码审核(Code Review)

在网络上,用户能方便的下载同一个软件的不同版本,以Google Chrome为例,在Chrome官网上有ChromeChrome DevChrome Canary这些不同的版本.

Chrome
Chrome Dev
Chrome Canary

将同一个软件根据稳定性和需求分成不同版本提供给不同的群体是十分常见的现象.但在chromium的源码仓库却会发现Google并非把ChromeChrome DevChrome Canary当作三个程序来维护,而是通过使用版本控制轻松的避免了提供三个版本的软件所带来的麻烦,这一切都是这样的理所当然.

为什么选择Git

  • Git 是基于GPLv2自由软件(free software)(Git 的部分内容不是基于GPLv2的,但是也基于一个与GPLv2兼容的协议),Git软件自由保护组织(Software Freedom Conservancy)的子项目
  • Git 是Linus Torvalds为维护Linux Kernel设计的工具

Git本就是为程序开发设计的版本控制系统,比其他的版本控制系统更适合程序开发的需求

除此之外,Git 还拥有这些特点

  • 速度
  • 简单的设计
  • 对非线性开发模式的强力支持(允许成千上万个并行开发的分支)
  • 完全分布式
  • 有能力高效管理类似 Linux 内核一样的超大规模项目(速度和数据量)

Git 日臻成熟完善,在高度易用的同时,仍然保留着初期设定的目标.
它的速度飞快,极其适合管理大项目,有着令人难以置信的非线性分支管理系统[2]

Software Freedom Conservancy的更多信息> 软件自由保护组织(Software Freedom Conservancy,简称SFC)是一个旨在为自由开源软件项目提供支持和基础设施的非营利组织,成立于2006年. [1]

Git 的历史

Linux 内核开源项目有着为数众多的参与者. 绝大多数的 Linux 内核维护工作都花在了提交补丁和保存归档的繁琐事务上(1991-2002年间).到 2002 年,整个项目组开始启用一个专有的分布式版本控制系统 BitKeeper 来管理和维护代码.[2]

因为BitKeeper为专有软件,这个决定在社区中长期遭受质疑.在Linux社区中,特别是理查德·斯托曼与自由软件基金会的成员,主张应该使用开放源代码的软件来作为Linux内核的版本控制系统.林纳斯·托瓦兹曾考虑过采用现成软件作为版本控制系统(例如Monotone),但这些软件都存在一些问题,特别是性能不佳.现成的方案,如CVS的架构,受到林纳斯·托瓦兹的批评.[3]

info

INFO

补充资料1

FSF 遵循这样的规则:我们不能在自己的计算机上安装任何专有软件,除非暂时性地用于一种特定用途,即编写一个自由软件来取代它.除此之外,我们感觉没有任何可能的借口来安装一款专有软件.

例如,在 20 世纪 80 年代,我们认为在我们的计算机上安装 Unix 是合理的,由于我们需要用它编写一个可以取代 Unix 的自由操作系统.而现在,由于自由的操作系统已经有了,因此这一借口不再适用;我们不会使用任何专有操作系统,并且我们所组装的任何一台新计算机都必须运行一款完全自由的操作系统.[4]

补充资料2

Bitkeeper议题
(参看下面的最后更新.)

使用Bitkeeper作为Linux源码的储存工具对于自由软件社区具有重大的影响,因为任何想要密切追踪Linux修定版本的人只能安装该非自由软件才行.肯定至少有数十或甚至数百名的内核黑客已经这么做了.他们之中大部份的人已经渐渐地说服了自己使用非自由软件是没有关系的,以避免在自己电脑上装有Bitkeeper带来的认知冲突造成的不良感觉.对此我们可以做些什么呢?

一个解决方式是为Linux源码设定另一个储存库,使用CVS或其他自由的版本控制系统,并设置新版本自动加载.这样可以使用Bitkeeper来对最新的版本进行存取,然后再将新的版本安装到CVS中.这种更新操作可以自动且频繁地运行.

自由软件基金会不能这样做,因为我们不能在我们的机器上安装Bitkeeper.我们的机器上现在没有非自由的系统或应用程序,而且我们的原则也是必须维持这种方式.运行Bitkeeper储存工具的操作需要某个愿意将Bitkeeper安装在他的机器上的人,除非有人可以找出或做出一个使用自由软件来运作的方式.

Linux源码本身有着更严重的问题:它们实际上包含一些非自由软件.相当多的设备驱动程序包含了代表固件程序的数组,它们会被安装在这些装置内.这些程序不是自由软件.在设备寄存器写入的数据是一件事;大量二进制代码是另外一回事.

在Linux“源码”文件中出现的这些只有二进制形式的程序,造成了另一个问题:那就是,Linux的二进制码到底是否可以合法地再发布.GPL要求“完备的相关源码”,而数字字符串并非源码.按照相同理由,添加这样的二进制码到Linux源码违反了GPL的规定.

Linux开发者有个项目是将这些固件程序转移到单独的文件中;该项目需要数年的时间才会成熟,不过当其完成时将会解决这个问题;我们可以作出一个“自由的Linux”版本,而其中不包括任何非自由的固件程序.但是如果大多数人都在使用非自由的“官方”Linux版本,那么该项目本身并没有什么用处.这很有可能发生,因为自由版本在许多平台上,如果没有非自由的固件都将无法运行.“自由的Linux”工程将不得不弄明白这些固件究竟做些什么,并且为它之编写源码,也许要以汇编语言为要运行的嵌入式处理器平台来撰写.这将会是件极其艰巨的工作.但是如果我们在早几年就开始一点一滴地进行,而不是等它堆积起来,它就不那么艰巨了.通过招募人员来进行这项工作,我们将不得不克服由某些Linux开发者所散播的“这件工作是不必要的”观念.

作为内核的Linux通常被视为自由软件的旗舰,然而它目前的版本却有一部份是非自由的.为什么会这样?就像决定使用Bitkeeper的问题一样,这个问题反应出了Linux原始开发者的态度,就是认为“技术上更好”比自由更重要.

历史告诉我们:珍惜你的自由,否则你将会失去它.以“不要以政治来烦我们”作为回应的人,是那些不愿接受教训的人.

最后更新:从2005年起,Linux内核的源代码不再使用BitKeeper管理.参看文章,致谢Larry McVoy.Linux源代码仍然含有非自由的固件blobs,但是在2008年1月,我们维护了一个自由版的Linux,并被自由的GNU/Linux发行版使用.[5]

Free Software Foundation的更多信息>「自由软件基金会(FSF)是一个非盈利组织.我们的使命是在全球范围内促进计算机用户的自由.我们捍卫所有软件用户的权利.」[6]

生活在当今的人们可能难以体会自由软件运动中对软件自由的向往和追求.即使在当时,也有很多人自由软件运动中追求的自由表示不解与不懈,但笔者身为GNU/LinuxGit的使用者和受益者,凭借自己对Open Free Share的些许感悟对他们曾经作出的一切表示挚诚的感谢和深深的敬意.

2005年,安德鲁·垂鸠写了一个简单程序,可以连接BitKeeper的存储库,BitKeeper著作权拥有者拉里·麦沃伊认为安德鲁·垂鸠对BitKeeper内部使用的协议进行逆向工程,决定收回无偿使用BitKeeper的许可.Linux内核开发团队与BitMover公司进行磋商,但无法解决他们之间的歧见.林纳斯·托瓦兹决定自行开发版本控制系统替代BitKeeper,以十天的时间编写出git第一个版本.[3]

使用Git

本文不介绍如何通过图形化界面来使用Git,本文只讨论Git在终端中的使用.

Git 基础

Git项目的不同阶段[13]

Git有三种状态,你的文件可能处于其中之一:已提交(committed)、已修改(modified)和已暂存(staged).
已修改表示修改了文件,但还没保存到数据库中.
已暂存表示对一个已修改文件的当前版本做了标记,使之包含在下次提交的快照中.
已提交表示数据已经安全地保存在本地数据库中.[13]

文件的状态变化周期[2]

  • init

为了在没有使用过Git的项目中使用Git,首先需要完成初始化Git仓库

在终端内,将工作目录切换至项目的目录,便可使用git init命令完成对Git仓库的初始化.

  • clone

任何人都可以从Github或者其他平台上获取使用Git版本控制的项目.

只需要使用git clone <url>就可以完整的获取url所对应的项目的所有源码以及所有的改动历史.

  • status

使用git status能查看git仓库的修改状态.

  • log

使用git log能查看git仓库的日志.日志中包括了很多信息.

  • diff

该命令会显示Git仓库中和上次提交相比已被修改的文件.

  • add

使用命令 git add 开始跟踪一个文件. 所以,要跟踪 README 文件,运行:

$ git add README
此时再运行 git status 命令,会看到 README 文件已被跟踪,并处于暂存状态:

$ git status
On branch master
Your branch is up-to-date with ‘origin/master’.
Changes to be committed:
(use “git restore —staged…” to unstage)

new file: README
只要在 Changes to be committed 这行下面的,就说明是已暂存状态. 如果此时提交,那么该文件在你运行 git add 时的版本将被留存在后续的历史记录中. 你可能会想起之前我们使用 git init 后就运行了 git add命令,开始跟踪当前目录下的文件. git add 命令使用文件或目录的路径作为参数;如果参数是目录的路径,该命令将递归地跟踪该目录下的所有文件.[2]

  • commit

git commit命令用来提交已经暂存的更改.

参数 -m message 附加提交信息
参数 -S 在提交中,使用GnuPG签名

Git 进阶用法

上面的那些操作只是Git的基础用法,不能发挥Git的功能的绝大部分功能.
下面笔者来介绍Git的高阶用法.

检出
  • 清空暂存区

git checkout HEAD

  • 检出至某一版本

git checkout <ref>
git checkout <commit>

1
2
3
graph LR
C5-->C4-->C3-->C2-->C1-->C0;
F((master))-->C4;

<ref>可以是一个分支名称,也可以是一个相对引用,下面是相对引用的语法

使用 A^ 指代 A 之前的第 1 个提交记录,如 master^master的前驱,即C3
使用 A^^ 指代 A 之前的第 2 个提交记录,如 master^^master的前驱的前驱,即C2
使用 A^^^ 指代 A 之前的第 3 个提交记录,如 master^^^master的前驱的前驱的前驱,即C1

……

笔者相信读者们不会喜欢用A^^^^指代 A 之前的第 4 个提交记录,因为这个命令实在太长了,下面有更简单的命令

使用 A~n 指代 A 之前的 n 个提交记录,如 master~2master的前驱的前驱,等价于A^^,即C2master~4master的前驱的前驱的前驱的前驱,等价于A^^^^,即C0

分支管理

为什么需要分支管理?开发中常常会有突发事件,加入你正在开发新的功能,但突然发现已有的程序存在严重的bug,你不得不紧急修复它.在开发中,提交不完整的代码会对项目的其他参与者造成巨大的影响.这不是一个正确的行为.那么你该怎么办?
如果没有分支管理,你可能会将未完成的代码删除,或者回退至过去的版本,但这可是你的心血.你还有可能复制一份现在的代码作为备份,然后把代码回退至过去的版本
但有了分支管理,这些问题都消失了.

实际工作中你可能会用到类似的工作流. 你将经历如下步骤:

  1. 开发某个网站.
  2. 为实现某个新的用户需求,创建一个分支.
  3. 在这个分支上开展工作.
    正在此时,你突然接到一个电话说有个很严重的问题需要紧急修补.
    你将按照如下方式来处理:
  4. 切换到你的线上分支(production branch).
  5. 为这个紧急任务新建一个分支,并在其中修复它.
  6. 在测试通过之后,切换回线上分支,然后合并这个修补分支,最后将改动推送到线上分支.
  7. 切换回你最初工作的分支上,继续工作.[9]
  • git branch <branch>创建新的分支
  • git checkout <branch>切换至已创建的新分支

这两条命令连续使用的情况可简化为:git checkout -b <branch> 创建并切换至新的分支

  • git branch -d <branch>删除一个分支
合并(merge)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
gitGraph:
options
{
"nodeSpacing": 150,
"nodeRadius": 10
}
end
commit
branch dev
checkout dev
commit
checkout master
commit
commit
merge dev
commit

如图,上图中dev分支的内容被合并至了master分支.

使用git merge <branch>可以指定的分支合并至当前分支.
Git在无冲突的情况下可以自动合并两个分支的更改.但Git并不总是能自动完成合并,当遇到合并冲突时,需要手动解决冲突才能完成合并.

变基(rebase)
1
2
3
4
5
graph LR
C3-->C2-->C1-->C0;
C5-->C4-->C2;
F((master))-->C3;
G((dev))-->C5;

Git的rebase功能允许使用者修改过去的Git提交历史,也提供一种比 merge 更易理解的方式处理提交内容的合并的需求.例如上图中,通过git rebase master dev指令,Git能分析dev分支中C4C5中的改动,并在master分支上重复这些改动,实现下图中的效果.

1
2
3
4
5
6
graph LR
C3-->C2-->C1-->C0;
C5-->C4-->C2;
C5'-->C4'-->C3;
F((master))-->C3;
G((dev))-->C5';

cherry-pick

通过git cherry-pick <commit>便可将一次提交复制至HEAD所指向的位置之后.

1
2
3
4
5
graph LR
C3-->C2-->C1-->C0;
C5-->C4-->C2;
F((master*))-->C3;
G((dev))-->C5;

在上图的情况中,使用git cherry-pick C4便可以将C4的提交内容复制至C3之后.实现下图中的效果.

1
2
3
4
5
graph LR
C4'-->C3-->C2-->C1-->C0;
C5-->C4-->C2;
F((master))-->C4';
G((dev))-->C5;

远程分支

远程引用是对远程仓库的引用(指针),包括分支、标签等等. 你可以通过 git ls-remote来显式地获得远程引用的完整列表, 或者通过 git remote show获得远程分支的更多信息. 然而,一个更常见的做法是利用远程跟踪分支.

它们以/的形式命名. 例如,如果你想要看你最后一次与远程仓库 origin 通信时 master 分支的状态,你可以查看 origin/master 分支. 你与同事合作解决一个问题并且他们推送了一个 iss53 分支,你可能有自己的本地 iss53 分支, 然而在服务器上的分支会以 origin/iss53 来表示.[10]

  • git remote add <remote>添加远程仓库
  • git fetch <remote> 从远程仓库拉取数据并更新远程分支所指向的位置,但不更新本地分支所指向的位置
  • git pull从远程仓库获取数据并与本地分支合并.等价于执行git fetch <remote>之后执行git merge <branch>
  • git push <remote> <branch>将分支推送至远程仓库
  • git checkout --track <remote>/<branch>为当前的本地分支设置上游分支
  • git push <remote> --delete <branch>删除远程分支

版本回退

本地版本回退
git reset <commit>
git reset <ref>

读者可能会感到这个命令与checkout十分相似,事实确实如此,不但命令相似,作用也是相似的.在checkout命令中,命令仅改变了HEAD所指向的位置,但在reset命令中命令还会改变HEAD所指向的分支的位置.

远程版本的回退

已经推送至远程仓库的提交并不能使用reset进行回退,如果你尝试过这样做就会发现Git会提示你,你的本地分支落后与远程分支,让你拉取远程的提交记录.拉取之后被reset的记录又被恢复了,所以不该使用reset去回退远程的分支.

git revert <commit>
git revert <ref>

正确的做法是使用使用revert功能.这个功能并不像reset那样,他会保留revert的记录和revert之前commit的记录.读者们可以理解为revert不是回退,而是把用新的提交把原来提交的内容改回去.

Git 练习

与别的技术一样,想要灵活的掌握Git的用法离不开适当的练习.在个人的开发中使用Git只是一个方面,笔者推荐完成learngitbranching上面的练习,这是学习Git的有效途径.

Git 原理

Git 存储文件的快照

Git存储文件的快照[13]

Git更像是把数据看作是对小型文件系统的一系列快照.在Git中,每当你提交更新或保存项目状态时,它基本上就会对当时的全部文件创建一个快照并保存这个快照的索引.为了效率,如果文件没有修改,Git不再重新存储该文件,而是只保留一个链接指向之前存储的文件.Git对待数据更像是一个快照流.[13]

Git 引用

如果你对仓库中从一个提交(比如 1a410e)开始往前的历史感兴趣,那么可以运行 git log 1a410e 这样的命令来显示历史,不过你需要记得 1a410e 是你查看历史的起点提交. 如果我们有一个文件来保存 SHA-1 值,而该文件有一个简单的名字, 然后用这个名字指针来替代原始的 SHA-1 值的话会更加简单.

在 Git 中,这种简单的名字被称为「引用(references,或简写为 refs)」. 你可以在 .git/refs 目录下找到这类含有 SHA-1 值的文件. 在目前的项目中,这个目录没有包含任何文件,但它包含了一个简单的目录结构:

1
2
3
4
5
$ find .git/refs
.git/refs
.git/refs/heads
.git/refs/tags
$ find .git/refs -type f

[8]

Git 的分支的本质就是:

一个指向某一系列提交之首的指针或引用[8]

最近公共祖先(LCA,Lowest Common Ancestor)

Git 在执行rabase操作时,涉及寻找两个分支的最近公共祖先的问题.

1
2
3
4
5
graph LR
C3-->C2-->C1-->C0;
C5-->C4-->C2;
F((master))-->C3;
G((dev))-->C5;

例如在使用git rebase master dev 时查找C3C5找到的最近公共祖先,才能实现下图的效果.

1
2
3
4
5
6
graph LR
C3-->C2-->C1-->C0;
C5-->C4-->C2;
C5'-->C4'-->C3;
F((master))-->C3;
G((dev))-->C5';

请看 LeetCode-236.二叉树中的最近公共祖先

实现如下:

我描述一下lowestCommonAncestor这个函数的「定义」吧.

描述:给该函数输入三个参数rootpq,它会返回一个节点.
情况 1,如果pq都在以root为根的树中,函数返回的即使pq最近公共祖先节点
情况 2,那如果pq都不在以root为根的树中怎么办呢?函数理所当然地返回null呗.
情况 3,那如果pq只有一个存在于root为根的树中呢?函数就会返回那个节点.

题目说了输入的pq一定存在于以root为根的树中,但是递归过程中,以上三种情况都有可能发生,所以说这里要定义清楚,后续这些定义都会在代码中体现.
OK,第一个问题就解决了,把这个定义记在脑子里,无论发生什么,都不要怀疑这个定义的正确性,这是我们写递归函数的基本素养.
然后来看第二个问题,这个函数的参数中,变量是什么?或者说,你描述一个这个函数的「状态」吧.
描述:函数参数中的变量是root,因为根据框架,lowestCommonAncestor(root)会递归调用root.leftroot.right;至于pq,我们要求它俩的公共祖先,它俩肯定不会变化的.
第二个问题也解决了,你也可以理解这是「状态转移」,每次递归在做什么?不就是在把「以root为根」转移成「以root子节点为根」,不断缩小问题规模嘛?
最后来看第三个问题,得到函数的递归结果,你该干嘛?或者说,得到递归调用的结果后,你做什么「选择」?
这就像动态规划系列问题,怎么做选择,需要观察问题的性质,找规律.那么我们就得分析这个「最近公共祖先节点」有什么特点呢?刚才说了函数中的变量是root参数,所以这里都要围绕root节点的情况来展开讨论.
先想 base case,如果root为空,肯定得返回null.如果root本身就是p或者q,比如说root就是p节点吧,如果q存在于以root为根的树中,显然root就是最近公共祖先;即使q不存在于以root为根的树中,按照情况 3 的定义,也应该返回root节点.
以上两种情况的 base case 就可以把框架代码填充一点了:

1
2
3
4
5
6
7
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 两种情况的 base case
if (root == null) return null;
if (root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
}

现在就要面临真正的挑战了,用递归调用的结果leftright来搞点事情.根据刚才第一个问题中对函数的定义,我们继续分情况讨论:
情况 1,如果pq都在以root为根的树中,那么leftright一定分别是pq(从 base case 看出来的).
情况 2,如果pq都不在以root为根的树中,直接返回null
情况 3,如果pq只有一个存在于root为根的树中,函数返回该节点.
明白了上面三点,可以直接看解法代码了:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// base case
if (root == null) return null;
if (root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 情况 1
if (left != null && right != null) {
return root;
}
// 情况 2
if (left == null && right == null) {
return null;
}
// 情况 3
return left == null ? right : left;
}

对于情况 1,你肯定有疑问,leftright非空,分别是pq,可以说明root是它们的公共祖先,但能确定root就是「最近」公共祖先吗?
这就是一个巧妙的地方了,因为这里是二叉树的后序遍历啊!前序遍历可以理解为是从上往下,而后序遍历是从下往上,就好比从pq出发往上走,第一次相交的节点就是这个root,你说这是不是最近公共祖先呢?[7]

参考资料

1. 维基百科编者. 软件自由保护组织[G/OL]. 维基百科, 2019(20191114)[2019-11-14]. https://zh.wikipedia.org/w/index.php?title=%E8%BD%AF%E4%BB%B6%E8%87%AA%E7%94%B1%E4%BF%9D%E6%8A%A4%E7%BB%84%E7%BB%87&oldid=56869590.
2. 起步- Git 简史.[G/OL].Git Book. https://git-scm.com/book/zh/v2/%E8%B5%B7%E6%AD%A5-Git-%E7%AE%80%E5%8F%B2
3. 维基百科编者. Git[G/OL]. 维基百科, 2020(20201106)[2020-11-06]. https://zh.wikipedia.org/w/index.php?title=Git&oldid=62682388.
4. 自由与非自由软件的分类 https://www.gnu.org/philosophy/categories.zh-cn.html
5. Linux、GNU和自由 https://www.gnu.org/philosophy/linux-gnu-freedom.zh-cn.html
6. https://www.gnu.org/
7. labuladong. 用 Git 来讲讲二叉树最近公共祖先[G/OL]. 微信公众号—labuladong, 2020(20200609)[2020-06-09]. http://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247485561&idx=1&sn=a394ba978283819da1eb34a256f6915b
8. Git 内部原理 - Git 引用.[G/OL].Git Book. https://git-scm.com/book/zh/v2/Git-%E5%86%85%E9%83%A8%E5%8E%9F%E7%90%86-Git-%E5%BC%95%E7%94%A8
9. Git 分支 - 分支的新建与合并.[G/OL].Git Book. https://git-scm.com/book/zh/v2/Git-%E5%88%86%E6%94%AF-%E5%88%86%E6%94%AF%E7%9A%84%E6%96%B0%E5%BB%BA%E4%B8%8E%E5%90%88%E5%B9%B6
10. Git 分支 - 远程分支.[G/OL].Git Book. https://git-scm.com/book/zh/v2/Git-%E5%88%86%E6%94%AF-%E8%BF%9C%E7%A8%8B%E5%88%86%E6%94%AF
11. https://learngitbranching.js.org/?locale=zh_CN
12. https://github.com/pcottle/learnGitBranching
13. 起步- Git 是什么?.[G/OL].Git Book.https://git-scm.com/book/zh/v2/%E8%B5%B7%E6%AD%A5-Git-%E6%98%AF%E4%BB%80%E4%B9%88%EF%BC%9F