外部 I/O:文件、格式化与局部存储
gz 函数调用操作系统和 C 库:open、read、write、lseek、close、fcntl、strerror、snprintf 和 vsnprintf。本页说明这些调用的模型:记录 Fs 以及它上面的操作。这个模型是被信任的:内核对照它检查证明,但不对照 Linux 检查它本身(可信基础)。
要点是:每个系统调用都可以返回其 POSIX 契约允许的任何结果,由一个预言选择;gz 接口的安全性是对每一个预言证明的(Goal.gz_sequence_safety;gzip 文件)。这个结果的前提见偏离记录。其中一条与预言有关:只有在描述符的读取预算有限时,才证明了读取类调用会返回(见下文)。
堆之外的世界
文件系统、描述符表和 errno 合成一个记录 Fs,与堆分开。一个 gz 计算的类型是 G α = StateT Fs C.M α:它接受一个世界和一个堆,返回一个值以及新的世界和新的堆,或者返回一个故障。
- 路径是扁平的字节串。节点保存一个文件的字节,或者是一个目录标记。
- 已打开的描述符保存它的节点、一个位置,以及读、写和追加标志。
- 描述符是 C 的
int。 Fs还保存下文说明的预言。
FileSystem fs 是世界的良构条件:描述符和名字指向存在的节点,位置、文件大小和文件大小限制至多为 2^63 - 1,目录不会以写方式打开。它只约束文件部分;预言的每个取值都是允许的。
操作系统预言
read、write、lseek、close 和 open 的每次调用都取下一个调用编号,并询问预言该怎么做。预言要么让这次调用按普通文件的方式进行,要么选择另一种结果。预言的每个取值都被映射到模型给该调用规定的范围之内(截断或钳制,从不拒绝),所以每个世界都是合法的。
| 调用 | 普通文件行为(预言的默认值) | 预言可以选择的其他结果 |
|---|---|---|
open |
读模式或写模式;创建、排他、截断和追加都有表示。无效的模式或模型中的路径失败会设置 errno 并返回 -1。新描述符是从 3 起最小的空闲编号。当 2^31 以下没有空闲编号时:在创建或截断任何东西之前,以 EMFILE 返回 -1。 |
在创建任何东西之前,以任意非零 errno 返回 -1。或者成功,并把新描述符移到 2^31 以下的任一空闲编号。 |
read |
复制所请求的文件字节,至多到文件末尾,并截断到读取预算。无效的描述符、错误的访问模式和目录都会失败。 | 以任意非零 errno 返回 -1。或者,对请求 n 个字节的读取,交付任意数据,字节数是 [0, n] 内的任意 k,并截断到读取预算,不论描述符处于什么状态。 |
write |
在当前位置写入,追加模式下在末尾写入。定位到末尾之后再写入,会用零填充空隙。越过 fsizeLimit 的写入是短写;在该限制处的写入以 EFBIG 失败。 |
以任意非零 errno 返回 -1。或者对非空缓冲区返回 [1, n] 内的任意计数(对空缓冲区返回 0),不改变文件。 |
lseek |
支持相对起点、当前位置和末尾的偏移;负的结果或大于 2^63 - 1 的结果被拒绝。 |
以任意非零 errno 返回 -1。或者返回任意 64 位值,包括负值,不移动描述符。 |
close |
释放描述符;无效的描述符会失败。 | 以任意非零 errno 返回 -1;描述符仍被释放。 |
fcntl |
没有效果。 | 无。 |
成功之后的 errno |
不变。 | 成功的调用可以留下任意 errno。库自己对 errno 的重置是另外的效果。 |
| 读取预算 | 没有上限。 | 对每个非负的描述符编号,给出它还可以交付的字节数;每次 read 都被截断到这个数,并从中扣除。负的描述符没有预算。 |
预言比普通文件宽。它逐次调用地覆盖管道、套接字、设备、信号(EINTR)、非阻塞描述符(EAGAIN)、瞬时失败和并发文件修改所产生的结果,而不表示这些对象本身。普通文件部分不表示权限、目录遍历、链接,也不表示通过复制描述符形成的共享;O_NONBLOCK、O_CLOEXEC 和 O_LARGEFILE 没有普通文件效果。
有两种结果被模型排除。它们是关于系统的假设,不是某个定理的前提:对非空缓冲区的 write 从不返回 0;close 失败时也释放描述符。两条在 Linux 上都成立。lseek 的结果一种也不排除:在 Linux 上,对偏移为无符号数的文件,lseek 可以返回 -1 以外的负值,而预言容许每一个 64 位值。
读取预算是用来说明读取何时结束的。zlib.h 对输入没有设上限,而一个永不结束的输入源在 C 里会让一次 gzread 调用永远运行下去。对那些一直读到输入结束的调用(gzread、gzfread、gzgetc、gzgets、gzungetc),gz 安全目标有两部分。在每个世界上,调用不发生故障,只可能有 Fault.outOfFuel。当描述符的读取预算低于 2^61 字节时(ReadsFinite),调用返回。其他每个 gz 调用都证明了在每个世界上返回(偏离记录)。
预言就是 Fs 的字段 nos、readChoice、writeChoice、lseekChoice、closeFail、openFail、openFd、okErrno 和 readBudget。它们的默认值给出普通文件行为,只供差分测试使用;gz 接口的每个安全目标都对所有世界量化。
错误文本
errno 是世界中的一个整数。strerror 返回一个指向静态文本的指针;模型有一张固定的 Linux 文本表,对其他每个 int 值有一条后备文本。
模型只允许读取最近一次 strerror 返回的指针:每次调用都使先前的指针不可读,即使 errno 相同。这表示的是顺序失效。线程退出、并发调用和语言环境变化没有表示。这个指针是只读视图;它不是一次分配,不改变存活块的集合,也不改变分配预言。
翻译在四处调用 strerror(gzread.c 两处,gzwrite.c 两处)。每一处都立即把指针交给 gz_error;后者把文本复制到自己的消息分配中,既不保存也不释放这个指针。
C 字符串字面量是另一回事:它们是库源码中各字面量组成的一张封闭的只读表,每个字面量有一个固定指针。
外部调用的缓冲区
storeBytes 存放 read 或格式化函数产生的字节。它经由一个临时块复制,然后释放该块,所以它的效果是一次块复制,不是一串字节存储。内存操作和其他地方一样检查对象边界、只读的目的缓冲区和重叠。无效的用户缓冲区是模型故障;模型不重现操作系统的 EFAULT。
格式化输出
可变参数是一个由 VaArg 值组成的列表:有符号和无符号的 32 位、64 位整数,以及字符串指针。gzprintf 接收这个列表,并委托给 gzvprintf。C 的 va_list 的 ABI 存储没有表示。
和 C 一样,模型有两个函数:
snprintf用于gz_error、gz_open和gzdopen的固定格式。它用模型的格式化函数格式化,支持%%、%c、%s、%d、%i、%u、%x、%X和%o,标志-、0、+、空格和#,十进制的宽度和精度,以及长度修饰符l、ll、z、j和t,限于 C 有定义之处。其他一切都是模型故障。它至多写入capacity - 1个文本字节和一个 NUL,返回未截断的长度;该长度超过INT_MAX时返回-1。vsnprintf用于gzvprintf中调用者给出的格式。它是按 C 契约建模的外部调用,和read、write一样:世界预言选择结果(printfRet)和字节(printfOut)。模型不读取格式串中的转换:调用者保证这个调用对其格式串和参数在 C 中有定义,且没有%n。契约见可信基础。
调用之后,gzvprintf 仍然执行自己的长度检查、哨兵检查、缓冲区腾空和错误处理,对契约的每个结果都如此。
gz 翻译中的指针与局部存储
gzFile是指向句柄记录的公开前缀x的指针(GzFilePtr)。castState恢复出这个记录,strmOf指出内嵌的z_stream。一次字段写入加载并存回这同一个记录,所以句柄、它的公开前缀和它的内嵌流始终是一个对象。- 调用者的标量单元是小端字节块:
gzerror的可选参数int *errnum(四字节),以及四个uncompress*函数的长度单元(各八字节)。 gz_load内部的unsigned *have是一个返回值(规范化 1)。每个调用者在成功和失败时都存储它。下面这一解读尚未确认,须由源码审查确认:在每个调用点,这次存储在效果顺序中的位置与 C 相同。- 被取地址的局部变量是一个新分配的对象,它不消耗分配失败预言,并在每条返回路径上被释放:
gzgetc和gzputc的单字节缓冲区;uncompress2_z的局部流,以及它为&stream.reserved准备的八字节块;还有uncompress2、uncompress_z和uncompress的局部长度单元。 z_off64_t上的文件位置运算使用带检查的 64 位操作。
模型接受给每一种指针值加零,包括空指针和悬空指针(模型的限制)。空指针或悬空指针上的其他运算都是故障。
源码是打过补丁的源码
有四个补丁修改 gz 文件(补丁登记表):
| 补丁 | 改动 |
|---|---|
| 0002 | gzseek64 的范围检查 |
| 0003 | 透明模式下,在 gz_load 之前设置 x.next;读取函数把位置 x.pos 保持在 z_off64_t 之内 |
| 0004 | 写入函数把位置 x.pos 保持在 z_off64_t 之内 |
| 0005 | lseek 的结果为负时,gzoffset64 一律返回 -1 |
在打过补丁的源码中,gz_reset 不初始化 x.next,直接读取之后 x.next 指向调用者的缓冲区。gzseek64 和 gz_skip_have 给这些值加零;没有补丁改动这一点,模型接受它。各补丁背后的报告见 gzip 文件。
差分证据
gz 的差分测试把每个操作在临时的真实文件上返回的结果,与在 Fs 上的运行相比较。同一组测试还比较 uncompress2 的字节和长度。
这些测试从默认预言出发,也就是普通文件行为。一个测试用例可以让选定的一次 read 调用失败,也可以让一次使用调用者格式的 vsnprintf 调用失败。预言的其他每一种选择都只由证明覆盖。
结果一致,是把翻译和世界模型合在一起,对照选定的 C 执行做的测试。它是忠实性的证据。它不是编解码器正确性的证明,也不是所有错误路径、所有 POSIX 行为或无泄漏的证明。