Gzip 文件:不变量、历史与操作系统预言
gzip 文件接口(gzopen、gzread、gzwrite、gzseek、gzclose 以及其他 gz
函数)在句柄的每一个历史上都是安全的,无论操作系统返回什么。本页给出这个命题,分清它假设了哪些东西,并解释证明的形状。
源文件:gzlib.c、gzread.c、gzwrite.c、gzclose.c、gzguts.h,以及 zlib.h 中的 gzgetc
宏。API 页面给出调用者可见的行为。术语见术语表。
结论
| 目标 | 定理 |
|---|---|
Goal.gz_sequence_safety |
gz_sequence_safety_public |
Goal.gz_refusal |
gz_refusal |
Goal.gz_sequence_nonvacuity |
gz_sequence_nonvacuity_public |
Goal.<function>_safety,共 32 个目标 |
GzCallSafetyProof.<function>_safety |
它们都是安全结论,并且都已完成。
31 个有文档的 gz 函数各有自己的安全目标;gzvprintf 也有,它在 zlib.h 中属于未文档化的函数,而 gzprintf 经由它实现。
每个目标是序列目标的一个子句,限制到一个函数的调用上:
- 接受句柄而不关闭它的函数:子句 2,连同
Goal.gz_refusal中属于该函数的子句,所以NULL句柄被拒绝,什么都不改变。Goal.gzgetc_safety还有子句 3(宏);Goal.gzerror_safety还有子句 4(它返回的字符串); gzclose、gzclose_r和gzclose_w:子句 5,连同对NULL句柄的拒绝;gzopen和gzopen64:子句 6。gzdopen:子句 7。
这些证明使用 gz_sequence_safety_public;对 NULL 的拒绝通过求值成立。所以本页余下讲序列目标的内容,同时也就是单函数目标的证明。
每个函数另有一个功能契约 Goal.<function>。这些契约不是必需的;哪些有定理,见最后一节。
序列目标覆盖下面这样的程序。注释指出覆盖每个调用的是目标的哪个子句。
gzFile f = gzopen(path, "rb"); /* 子句 6:打开会返回;失败时不泄漏 */
n = gzread(f, buf, len); /* 子句 2;它会返回,这需要输入源有限 */
c = gzgetc(f); /* 子句 3:zlib.h 中的宏 */
msg = gzerror(f, &err); /* 子句 2 和 4:msg 是可读的字符串 */
gzclose(f); /* 子句 5:全部释放,close 失败时也一样 */
在两次调用之间,程序可以改动它自己的内存,任何人都可以改动文件系统。目标对所有这样的历史成立。
目标陈述了什么
一个世界是文件系统、描述符表、errno 以及预言的一个状态;预言选择系统调用的结果(见下文)。句柄的一个历史是一串步骤,从一次成功的打开开始(见下文)。
Goal.gz_sequence_safety 有七个子句。
- 不变量。 每个历史之后,世界是良构的(
FileSystem),句柄满足表示不变量GzInv。 - 再调用一次。 对每个历史、每个世界,以及句柄上参数符合要求的每一次后续公开调用,以下三部分都成立。
- (a) 没有未定义行为,没有内存错误。 运行不以
Fault.ub结束。这一部分没有别的前提。 - (b) 终止。 运行不以
Fault.outOfFuel结束,所以连同 (a),调用会返回。对六个读调用gzread、gzfread、gzgetc、gzgetc_、gzgets和gzungetc,这一部分需要读取预算前提ReadsFinite。对其他每个调用,它在每个世界中成立。 - (c) 已返回的调用的效果。 已打开描述符的集合不变(
FdsKept)。句柄再次满足GzInv,模式和描述符不变。调用只写了句柄的块和为该调用声明的调用者区域。存活块的变化只涉及句柄拥有的块:每个新的存活块都归句柄所有,每个消失的块原先也归它所有(GzStepPost)。所以没有泄漏。 gzgetc()宏。 使用这个宏同样有这三部分,终止性的划分是它自己的(见宏)。gzerror的字符串。gzerror返回的指针是一个以 NUL 结尾的字符串,在调用之后的堆中可读:它是字面量,或者是句柄的消息。- 关闭。 每个关闭调用都会返回。它要么因模式不对而拒绝,什么都不改;要么释放记录和每个拥有的块,并释放描述符,
close报告-1时也是如此(GzReleased)。 - 打开。
gzopen和gzopen64会返回。失败的打开不留下新块,也不留下新打开的描述符。成功的打开给出一个满足GzInv的句柄,它恰好拥有那些新块。它的描述符的编号不为负,在调用之前没有打开,其他描述符编号都没有被打开或关闭(GzOpenSafe)。这个子句没有说句柄的描述符在调用之后是打开的。 gzdopen。 它会返回,不打开也不关闭任何描述符(GzDopenSafe)。
没有 ReadsFinite 时,(a) 部分对读调用仍然成立。这时它是部分正确性:在每个循环少于 2^64
轮的任何运行中都没有未定义行为。真实的执行达不到这个轮数。
假设了什么
这个结论的背后有三样不同的东西:前提、一个可信的模型,以及对源码的补丁。只有第一样在 Lean 命题里。
命题中的前提
每一条都明确写在 Goal.gz_sequence_safety 中,或者写在它所量化的历史 GzHistory 中。对应的行在偏离记录里。
| 前提 | 位置 | 含义 |
|---|---|---|
| 打开时的调用者堆和世界 | GzHistory.open、open64、dopen;GzOpenSafe、GzDopenSafe |
堆是良构的(Fresh、Uniq、LibraryGlobals),每个字节对象少于 2^63 字节(ByteObjectsFit),世界是良构的(FileSystem),path 和 mode 是以 NUL 结尾的字符串(在子句 6 和 7 中也可以是 NULL)。 |
| 调用者缓冲区 | GzArguments,经由 GzRange |
gzread、gzfread、gzwrite、gzfwrite、gzputs、gzgets 和 gzerror 的缓冲区在请求的长度内可读,在调用要向其中存入数据时可写,并且与句柄拥有的块不重叠。gzputs 的参数是以 NUL 结尾的字符串。长度为 0 的请求、C 因大小而拒绝的请求、缓冲区为 NULL 或长度小于 1 的 gzgets 调用,以及 gzerror 的 errnum 为 NULL 的情形,都没有缓冲区前提。 |
gzprintf 和 gzvprintf 的参数 |
GzArguments |
文件以写方式打开且不处于错误状态时,格式串是以 NUL 结尾的字符串,每个指针参数都指向未被释放的块。格式串和每个指针参数都与句柄的块不重叠。vsnprintf 调用对格式串和参数在 C 中有定义、且没有 %n,由调用者保证:没有前提陈述这一点,而模型不读取格式串中的转换(可信基础)。 |
| 读取预算 | ReadsFinite |
句柄的描述符还能交付的字节少于 2^61。它只是 (b) 部分的前提,并且只针对六个读调用。这个前提还说描述符的编号不为负。库返回的每个句柄都有这样的编号:GzOpenSafe 对 gzopen 写明了这一点,而 gzdopen 对负的描述符返回 NULL。 |
| 两次调用之间的调用者步骤 | GzHistory.caller:GzCallerFrame、ByteObjectsFit |
调用者只改动句柄不拥有的块。改动之后的堆是良构的(Fresh、Uniq、LibraryGlobals),其中每个字节对象少于 2^63 字节。 |
| 两次调用之间的世界步骤 | GzHistory.world:GzWorldStep |
新的世界是良构的(FileSystem)。此外没有别的要求。 |
受信任而不在命题中:世界模型
世界及其预言是用 Lean 写的一个 Linux 模型(外部 I/O)。内核对照这个模型检查证明。它不对照 Linux 检查这个模型(可信基础)。证明倚重模型的两个事实:
- 对非空缓冲区的
write从不返回 0; close失败时也释放描述符。
源码是打过补丁的源码
这些命题说的是应用了补丁 0002 到 0005 的 C。未打补丁的 C 在某些历史上有未定义行为:见源码报告与补丁。
为什么要读取预算
一个无穷的输入源会让一次 gzread 调用在 C 中永远运行:无穷的 FNAME
字段,或者无穷多个空的 gzip 成员。zlib.h 没有承诺读调用在这样的输入源上会返回。
2^61 这个数字是模型的限制。模型的一个循环有 2^64 轮燃料。读循环由度量界定,度量由剩余输入、读取预算和还要交付的字节构成。低于
2^61 的预算使这些度量保持在 2^64 以下。
这个前提按调用名给出(NeedsReadBound)。所以在 C 立即返回的地方也要求它:在写句柄上的读调用,或者长度为 0 的请求。gzdirect
没有读循环,不需要预算。gzseek 把跳过推迟,也不需要预算。
源码报告与补丁
补丁 0002 到 0005 修复未打补丁的 C 的五处缺陷;补丁 0003 修复其中两处。第一张表每处一行。发现列出它们及其证据;补丁以
patches/README.md 中的列表为准。这四个补丁都已提交上游,各拉取请求都处于打开状态。不变量之所以是这个形式,是因为前四处缺陷,以及第二张表中的两种情形,后者没有补丁改动。
| 情形 | 未打补丁的 C 的行为 | 证据与修复 |
|---|---|---|
| 负的定位位置 | 在一开始的 gzungetc 之后,GZ_OFF_MAX - pos 或者后来的位置差使有符号 64 位算术溢出。 |
已在 sanitizer 下复现(发现)。补丁 0002,上游 PR 1361。 |
| 部分读取之后出错 | 在 gz_fetch 的 COPY 分支中,gz_load 出错时可能在 x.next = out 执行之前留下非零的 x.have;gz_read 随后从一个过时的指针复制。 |
已在 sanitizer 下复现(发现)。补丁 0003,上游 PR 1405。 |
| 读位置溢出 | 在一个 lseek 成功却不移动的设备上,透明模式的定位把 x.pos 设为 GZ_OFF_MAX;下一次读取使它溢出。 |
已在 sanitizer 下复现(发现)。补丁 0003,上游 PR 1405,在每个调用返回时保持 x.pos + x.have ≤ GZ_OFF_MAX。 |
| 写位置溢出 | 透明写句柄向前定位到接近 GZ_OFF_MAX,然后写入,使 x.pos 溢出。 |
已在 sanitizer 下复现(发现)。补丁 0004,上游 PR 1406,拒绝会越过 GZ_OFF_MAX 的写入。 |
| 负的描述符偏移 | gzoffset64 只把 lseek 返回的 -1 当作失败。别的负值减去读句柄已缓冲的输入,使有符号 64 位算术溢出。 |
已在 sanitizer 下复现(发现)。补丁 0005,上游 PR 1404,对 lseek 的每个负结果都返回 -1。 |
| 情形 | C 的行为,打不打补丁都一样 | 证明如何处理 |
|---|---|---|
| 未写入的指针 | gz_reset 没有写 x.next;gzseek64 和 gz_skip_have 给它加零。 |
按 C 的条文是未定义的;没有 sanitizer 报告它。模型接受给每一种指针值加零(模型的限制)。 |
| 调用者缓冲区的生命期 | 直接读取把 x.next 指进调用者的缓冲区,并在 x.have = 0 时保留它。调用者释放缓冲区之后,gzseek64 和 gz_skip_have 给它加零。 |
按 C 的条文是未定义的;没有 sanitizer 报告它。适用模型的同一条规则。gzseek64_dangling_next_ok 表明:读句柄在没有已缓冲输出时向前定位,无论 x.next 是什么值都不出故障。 |
历史
GzHistory h fs i 说的是:堆 h 和世界 fs 由句柄 i 的某个实际历史到达。它有七个构造子;下表把三个打开构造子放在同一行。
| 构造子 | 步骤 |
|---|---|
open、open64、dopen |
一次成功的 gzopen、gzopen64 或 gzdopen,出发的调用者堆和世界满足前提表的第一行,字符串参数都不是 NULL。 |
step |
句柄上的一次公开调用(GzOperation),参数符合要求(GzArguments),并且已返回。 |
getcMacro |
对 gzgetc() 宏的一次使用,并且已返回。 |
caller |
调用者改动它自己的内存:句柄不拥有的任何块。它可以释放自己的缓冲区,包括上一次 gzread 的缓冲区。改动之后的堆是良构的(GzCallerFrame:Fresh、Uniq、LibraryGlobals),它的字节对象都在大小上限之内(ByteObjectsFit)。世界不变。 |
world |
另一方改动世界(GzWorldStep):变成任何良构的文件系统状态。堆不变。 |
world 步骤有意定得很宽。另一个句柄或应用程序可以关闭这个句柄的描述符,或者在它的编号下打开另一个文件。下一次读或写于是得到错误,或者落到那个文件上,与
C 中一样。这个步骤还可以替换预言。
GzHistory 没有预算前提,所以子句 1 在每个历史上成立。gz 的功能目标是在另一个谓词 GzReachable 上表述的;安全目标不使用它。
世界及其预言
世界是堆旁边的一个记录 Fs。一个 gz
计算接受一个世界和一个堆,返回一个值和这两者,或者返回一个故障。世界里有文件、描述符表、errno,还有一个预言:它在每个
read、write、lseek、close、open 和调用者格式的 vsnprintf 的契约之内选择该调用的结果。预言可以选择什么,见外部 I/O
中的表。
预言比普通文件宽:例如,无论描述符处于什么状态,读取都可以成功。每个子句都对所有世界量化,所以没有哪个证明步骤能依赖文件是普通文件。
外部调用分成两组。
- 五个系统调用不碰堆。 模型函数
fsRead、fsWrite、fsLseek、fsClose和fsOpen接受一个世界,返回一个结果和一个新的世界。对每个预言值,它们各自都是对一个只依赖世界的结果取pure:从不产生故障,也从不改动堆(fsRead_pure、fsWrite_pure、fsLseek_pure、fsClose_pure、fsOpen_pure)。fsRead把读到的字节作为一个值返回。随后gz_load的翻译把它们存到buf处(storeBytes);这次存入是一次受检查的堆复制,它是被翻译的 C 的一步,不是系统调用的一步。这次复制经过一个它自己创建并释放的临时块,所以它还会推进堆的块计数器(nextBlk)。 - 两个库调用改动堆。
vsnprintf向它的目的地址存入数据:格式化出的字节和一个 NUL;调用失败时,则是预言选择的字节和一个 NUL。两种情况下都在交给它的size个字节之内。预言让它失败时调用失败,格式化输出超过INT_MAX字节时调用也失败。格式串不是字符串,或者是模型的格式化器不能表示的格式,或者目的地址对这些字节不可写时,它产生故障。vsnprintf_in表明:gzvprintf中的那次调用(目的地址在句柄的in缓冲区内)对每个预言值都会返回,保持GzInv,并且只写句柄拥有的块。zstrerror是strerror(errno)的模型,它不分配任何东西,返回一个借用的字符串,这个字符串不是堆块。它改动堆的一个字段libcErrorBorrow,这个字段记录当前借出的是哪一段错误文本;块、存活标志和分配器字段都不变(zstrerror_run、zstrerror_no_malloc)。
read 的契约是 fsRead_contract,连同它的预算记账(BudgetAcc、fsRead_budget)。write
对每个预言值的契约是 fsWrite_contract。
证明结构
flowchart TD
G["gz_sequence_safety_public"] --> A["gz_sequence_safety_of:组装"]
A --> H["history_inv:对 GzHistory 归纳"]
A --> O["operation_safe:按调用分派"]
A --> C["close_safe"]
A --> E["gzerror_string"]
A --> P["gzopen_safe, gzopen64_safe, gzdopen_safe"]
O --> Q["查询、定位、倒回、clearerr"]
O --> W["写叶引理"]
O --> R["六个读叶引理:GzReadLeaves"]
A --> M["gzgetc_macro_safe"]
M --> R
一个调用的安全性只有一种形状,GzCallSafe i call:对每个堆、每个良构的世界、每个满足 GzInv
的记录和每个符合要求的参数,子句 2 的三部分成立。叶引理是为一个公开函数证明 GzCallSafe 的引理。
组装 gz_sequence_safety_of 有两步。
history_inv对GzHistory归纳。打开的构造子使用打开引理。step使用该调用的叶引理的 (c) 部分。caller步骤使用GzInv.caller:不变量读的是句柄的块(这一步保持它们),以及整个堆的良构性和字节对象大小(这一步为新的堆提供它们)。world步骤不改动堆,而不变量不提世界。operation_safe把一个调用分派给它的叶引理。close_safe对三个关闭调用做同样的事。
读取一侧的叶引理打包在 GzReadLeaves 中:gzread_step、gzfread_step、gzgetc_step、gzungetc_step、gzgets_step 和
gzdirect_step。按定义,gzgetc_ 就是 gzgetc,所以它没有自己的叶引理。(gzdirect 属于读取一侧,但不在需要读取预算的六个调用之内。)gz_sequence_safety_of 以这个包为唯一的参数,gz_sequence_safety_public
提供它。每个叶引理都是没有前提的定理。
不变量 GzInv
GzInv h i s 是记录为 s 的已打开句柄 i
的表示不变量。它有一个公共部分,每种模式各有一个部分。证明通过它的接口引理使用它(GzInv.common、GzInv.reader、GzInv.writer、GzInv.state_eq、GzInv.pos_lower)。
它谈到的字段是 gzguts.h 中 gz_state 的字段:
| 字段 | 在 C 中的含义 |
|---|---|
x.have、x.next、x.pos |
公开前缀 gzFile_s:缓冲在 x.next 处的输出字节数,以及在未压缩数据中的位置。gzgetc 宏直接读写它们 |
mode、fd、path |
读或写;描述符;用于错误消息的名字 |
size、want |
缓冲区大小,缓冲区还不存在时为 0;请求的大小 |
in、out |
输入缓冲区和输出缓冲区 |
strm |
内嵌的 z_stream;下文的“编解码器”指它背后的 inflate 或 deflate 状态 |
how |
读句柄:LOOK(寻找 gzip 头)、COPY(原样复制输入,即“透明”)、GZIP(解压一个 gzip 成员) |
direct |
处理 gzip 时为 0,透明时为 1。只接受 gzip 的读句柄(模式字母 G)在 gz_look 选定 gzip 解码之前为 -1 |
junk |
读句柄:开始时为 -1,垃圾候选为 1,在 gzip 数据内部为 0 |
eof、past、again |
输入已结束;有一次读取请求越过了末尾;上一次 I/O 被 EAGAIN 拒绝 |
skip |
待处理的定位的距离 |
err、msg |
错误码和消息 |
在 LP64 构建上,偏移是有符号 64 位的,GZ_OFF_MAX = 2^63 - 1,一次 I/O 请求至多 2^30 字节。
下面三个列表是用白话写的摘要。本页后面用到的子句,名字写在括号里。
公共部分(GzCommon)。
- 记录在堆中,模式是读或写。
- 堆是良构的(
Fresh、Uniq、LibraryGlobals),每个字节对象少于2^63字节(ByteObjectsFit)。内嵌的编解码器在它的每次调用时都需要这两点。 path是一个被拥有的、以 NUL 结尾的字符串。msg是NULL或一个被拥有的字符串,在Z_MEM_ERROR之后是NULL。8 ≤ want < 2^31,size是 0 或want。size = 0表示缓冲区和编解码器还不存在。- 被拥有的块是存活的、两两不同的、不同于记录的,并且不归内嵌的编解码器所有。编解码器不拥有记录块。
- 位置:
0 ≤ skip,x.pos + skip ≤ GZ_OFF_MAX,0 ≤ x.pos + x.have。 x.next:有已缓冲的输出时(x.have ≠ 0),它指进一个被拥有的块,这个块不是记录也不是消息,其后有x.have字节(next)。x.have = 0时,不变量不说它指向哪里。x.next为NULL时x.have = 0。
读句柄部分(GzReadInv)。
how是LOOK、COPY或GZIP,direct、junk以及标志eof、past、again取相应许可的值。- 没有缓冲区时(
size = 0),没有编解码器(strm.state = NULL),没有已缓冲的输出,也没有待处理的输入;how是LOOK,again是 0。 - 有缓冲区时(
size ≠ 0),in是一个恰有size字节的可写块,out是一个恰有2·size字节的可写块。 - 待处理的输入(
avail_in ≠ 0)在in中:next_in = in + a,且a + avail_in ≤ size。已缓冲的输出在out中:x.next = out + c,且c + x.have ≤ 2·size。 - 有缓冲区时,内嵌的流在 inflate 历史中(
StreamReachable .inflate),没有头记录。 x.pos + x.have ≤ GZ_OFF_MAX(posHave)。- 有已缓冲的输出就没有待处理的跳过(
haveSkip)。 - 在输入末尾停住的读句柄没有待处理的输入(
againEof)。 err从不是Z_STREAM_END。COPY没有待处理的输入。有缓冲区时,流的消息是NULL或字面量。
写句柄部分(GzWriteInv)。
x.have = 0。gzgetc宏在任何句柄上都读x.have。direct是 0(压缩的写句柄)或 1(透明的写句柄),reset是 0 或 1。- 没有缓冲区时,没有编解码器(
strm.state = NULL)。 - 有缓冲区时,
in是一个恰有2·size字节的可写块。压缩的写句柄有恰好size字节的out。透明的写句柄没有编解码器,不变量也不把out算作它拥有的块;关于这个字段,不变量没有说别的。 next_in是NULL且avail_in = 0;否则缓冲区存在,待处理的输入在in的前一半中:next_in = in + a,且a + avail_in ≤ size。- 对有缓冲区的压缩写句柄,
next_out = out + b,x.next = out + c,其中c ≤ b ≤ size,并且avail_out = size - b。内嵌的流在 deflate 历史中,没有 gzip 头记录。
完整的命题是定义 GzInv,以及它的三个部分 GzCommon、GzReadInv 和
GzWriteInv;这份摘要与定义不一致的地方,以定义为准。
每个子句之所以存在,是因为有某个调用需要它。下面三个例子说明这一点。
- 没有
posHave,gzgetc的缓冲路径会使x.pos溢出。 - 没有
haveSkip,gzgetc会在有跳过待处理时返回一个已缓冲的字节,并把x.pos移过GZ_OFF_MAX - skip。 - 没有
againEof,gz_read会永远循环:gz_avail在eof处什么都读不到,而gz_look返回 0。
在一次读调用的内部,有两个较弱的形式成立。GzInvUpToOutput 是把已缓冲的输出清空之后的记录的 GzInv:直接读取会把 x.next
留在调用者的缓冲区里。GzInvUpToSkip 是去掉 haveSkip 的 GzInv:gz_look 和 gz_fetch
可以在有跳过待处理时缓冲输出,而调用它们的函数在返回之前把它消耗掉。
新分配的记录的指针字段
gz_open 不写 strm.state、strm.next_in 和 x.next。在模型中,新分配的指针是 NULL。在 C
中它是不确定的,读它是未定义的(安全性,未初始化内存)。
strm.state和strm.next_in:不变量写明size = 0时strm.state = NULL。证明表明的是翻译的安全性。它没有表明读取了不确定指针的 C 代码会被发现:这是可信基础第 2 节的模型缺口。尚未确认,须由源码审查确认:在gz_look或gz_init写入strm.state和strm.next_in之前,C 从不读它们。x.next:x.have = 0时不变量对它不作任何断言。通过x.next的每次读取,以及对它的每次非零推进,都发生在x.have ≠ 0时。x.have = 0时,gzseek64和gz_skip_have给它加零,模型对每一种指针值都接受这一操作(模型的限制)。
读的一侧
flowchart LR
A["gz_read"] --> S["gz_skip"]
A --> B["gz_fetch"]
S --> B
B --> L["gz_look"]
B --> D["gz_decomp"]
B --> R["gz_load"]
D --> V["gz_avail"]
V --> R
A --> D
A --> R
gz_load 累积字节,直到请求被填满或者某次读取让它停下。正数的读取结果推进 have;零设置 eof;阻塞造成的拒绝设置
again;其他失败设置一个错误。失败可以跟在成功的部分读取之后。
gz_look 在第一次调用时创建缓冲区和编解码器,然后决定怎么读。它只在至少有四个可用字节时才认出 gzip:魔数 31, 139、方法 8,以及小于
32 的标志字节。否则,在模式允许时,输入按透明处理。
gz_decomp 在内嵌的流上运行 inflate,直到输出已满、成员结束、输入结束或者出现错误。成员结束的路径回到检测,以处理连接在一起的多个成员。
gz_read 有三条数据路径:消耗已缓冲的输出,把透明数据直接读进调用者的缓冲区,或者直接解压到足够大的调用者缓冲区中。
读辅助函数按下面的顺序组合起来:
| 引理 | 命题 |
|---|---|
gz_look_safe |
gz_look 是安全的。 |
gz_decomp_safe_of |
gz_decomp 是安全的,条件是从模式 BAD 或 MEM 出发的 inflate 调用不移动两个缓冲区中的任何一个。这个事实是 inflateStuckNoOutput_holds。 |
gz_fetch_safe_of |
gz_fetch 是安全的,条件是 gz_look 和 gz_decomp。 |
gzSkipRead_holds |
gz_skip 是安全的,条件是 gz_fetch。 |
gz_read_safe_of |
gz_read 是安全的,条件是 gz_skip、gz_fetch 和 gz_decomp。 |
gzread_step、gzfread_step |
公开调用,由 gz_read 得出。 |
每个内嵌的 inflate 调用都使用流式解码中关于流的结论:内嵌的流是可达的,所以单次调用的完整契约适用。
读循环的终止
每个读循环都有一个度量,它是由世界和句柄算出的一个自然数。有了 ReadsFinite,度量从 2^64
以下开始,并在每一个继续下去的轮次下降。下表给出每个度量的形状;准确的定义是
fetchMeasure、fetchRank 和 readMeasure。
把描述符的读取预算加上 avail_in 记作 inputLeft。gz_avail 读到多少字节,就把 avail_in
提高多少,预算则下降同样多的字节(gz_avail_budget)。所以 inputLeft 从不上升。
| 循环 | 度量 | 为什么下降 |
|---|---|---|
gz_decomp |
inputLeft + avail_out |
它在每一个继续下去的轮次下降。 |
gz_fetch |
4 · inputLeft + c,其中 c 对 LOOK 为 2,对位于成员开头的 GZIP 为 1,对 COPY 为 0,其他情况为 3 |
它在每一个继续下去的轮次下降。空的 gzip 成员要耗费输入,所以预算排除了无穷多个空成员。 |
gz_read |
readMeasure:令 L = min(len, GZ_OFF_MAX - pos),它是 L / 8 + Q + 2·E + 3·R + fetchRank。Q 在没有已缓冲的输出时为 1;已缓冲的字节少于 16 个、err = Z_OK 且 x.pos + x.have < GZ_OFF_MAX 时为 2;其他情况为 0。E 在输入末尾为 0,在此之前为 1。R 在 pos 低于 GZ_OFF_MAX 时为 1。fetchRank 是 4 · inputLeft,加上读取预算,在一个 gzip 成员已过开头、正在进行时加 2,在 how 变成 COPY 之前再加 2 |
它在每一个继续下去的轮次下降。gz_decomp 和 gz_fetch 都不提高 fetchRank。 |
gzgets |
它的循环变量 left |
它在每一个继续下去的轮次下降。 |
gz_skip |
skipMeasureF |
gzSkipTerminates_holds,由 GzInvUpToSkip 得出。 |
读的包装函数
包装函数保持 C 的检查顺序。gzread 检查它的无符号请求能放进 int。gzfread 在做除法之前检查 size_t 乘积。gzgets 为
NUL 留出位置,用 min(have, left) 界定它的 memchr,写最后的 NUL 的位置至多是 buf[len - 1]。gzungetc 先运行 gz_look 和
gz_skip,然后在 out 之内回推;在文件开头它可以造成 x.pos = -1,这就是不变量界定 x.pos + x.have 而不是 x.pos 的原因。
gzgetc 宏
zlib.h 把 gzgetc 定义为宏:
#define gzgetc(g) \
((g)->have ? ((g)->have--, (g)->pos++, *((g)->next)++) : (gzgetc)(g))
它是应用程序调用 gzgetc 的默认方式,所以历史为它设了一个构造子(GzHistory.getcMacro),目标为它设了一个子句。翻译是
Zlib.ZlibH.gzgetc;证明是 gzgetc_macro_safe。
这个宏有两个分支。
- 有已缓冲的输出(
x.have ≠ 0)。 宏就地改动x.have、x.pos和x.next,没有库调用。与函数不同,again置位时它不清除err和msg。这个分支的返回对世界没有任何前提。GzCommon.next把x.next放在一个被拥有的缓冲区内,其后有x.have字节;posHave保证x.pos + 1可表示;haveSkip给出skip = 0。写句柄有x.have = 0,所以就地分支只在读句柄上运行。 - 没有已缓冲的输出(
x.have = 0)。 宏调用函数gzgetc。这个分支就是读叶引理gzgetc_step,它在ReadsFinite下返回。
在两个分支中,效果都是函数的效果,而函数不写任何调用者区域。
在 NULL 句柄上,宏先读 (g)->have,这在 C 中是未定义行为。Goal.gz_refusal 只对函数 (gzgetc)(file) 说明 NULL 的情形。
写的一侧
gz_init 分配双倍的输入缓冲区,对压缩输出还分配输出缓冲区和编解码器。gz_comp
对透明输出直接写出输入,否则交替进行 deflate 调用和输出写入。gz_write 把小的输入复制进 in,或者把 next_in
指向调用者的大缓冲区,事后再把它复位。gz_zero 通过写零来完成待处理的向前定位。gz_vacate 压缩待处理的数据,并把其余的移到前面。
写叶引理是 gzwrite_step、gzfwrite_step、gzputc_step、gzputs_step、gzprintf_step、gzvprintf_step、gzflush_step、gzsetparams_step
和 gzclose_w_step。它们使用 gz_error 的事实,这些事实由不变量推出。
gz_comp 的循环在每个世界中都终止,不需要预算。写出循环以还要写的字节为度量,透明循环以待处理的输入为度量。两者都下降,因为对非空缓冲区的
write 返回 -1,或者返回 1 到长度之间的一个计数(fsWrite_contract)。这就是上文关于
write 的受信任事实。deflate 循环有它自己的度量,只要循环继续,它就下降。
不涵盖:write 会对非空缓冲区返回 0 的系统。尚未由证明确认:按对 C 的解读,一个永远返回 0 的 write 会让 gz_comp
永远循环,因为两个写循环在计数为 0 时都不前进。
gzvprintf 在 next[size - 1] 处写一个哨兵,并以容量 size 做格式化。长度落在 1..size-1 之外,或者哨兵丢失,gzvprintf 就拒绝这个结果。
gzsetparams 刷新待处理的数据,调用 deflateParams,然后存入请求的级别和策略。它忽略被调用函数的结果。安全证明不需要那个结果。
位置、定位与错误消息的归属
gztell64 报告逻辑位置加上待处理的跳过;past 置位时不加这段跳过。gzoffset64 查询描述符的位置,在读模式下再减去已缓冲的压缩输入。lseek 的结果为负时它一律返回 -1(补丁 0005),所以这次减法不溢出。这是两个不同的位置。
gzseek64_step 和 gzseek_step 对每个世界成立。路径有:
- 拒绝(严重错误、坏的
whence、目标落在补丁 0002 的范围之外):返回-1,什么都不变; - 写句柄:
skip变成那段距离;目标在x.pos之前时,调用返回-1; - 透明模式的读句柄:一次
lseek。由posHave,位移pos - x.pos - have不溢出; - 向后退的读句柄:先
gzrewind,然后整段距离变成skip; - 向前走的读句柄,也包括
gzungetc之后从负的x.pos出发:已缓冲的字节被消耗,其余的变成skip。
每条路径之后 haveSkip 都成立。lseek 可以返回预言选择的任何值。它只改动调用计数器、errno,以及(对普通文件)那一个描述符的位置。所以世界保持良构,已打开的描述符保持不变。
gz_error 先释放旧的被拥有的消息。内存错误不分配新消息;其他任何消息都拥有 path + ": " + text 这次分配。gzerror
返回内存错误的字面量、当前消息或者空字面量,并且可以把错误码存进调用者的四字节单元。gzerror_step 和
gzerror_string 表明这次存入保持不变量,并且返回的指针是调用之后的堆中的一个字符串。这个字符串由下一个到达
gz_error 的调用释放;关于 gzprintf 参数的调用者前提排除了把它传回同一个句柄。
打开与关闭
gzopen_safe、gzopen64_safe 和 gzdopen_safe 表明新打开的句柄满足
GzInv。打开给出 size = 0,所以每个关于缓冲区或已缓冲输出的子句都空洞地成立。
gzclose 读出模式,然后运行 gzclose_r 或 gzclose_w。满足 GzInv 的句柄是读句柄或写句柄,所以
gzclose 从不拒绝。gzclose_r 在编解码器存在时结束它,释放缓冲区、消息、路径和记录,并关闭描述符。gzclose_w
还要先写出待处理的零并完成输出。这些操作失败时,清理照样进行。成功的 gzdopen 接管描述符;失败的则把它留给调用者。
NULL 句柄
Goal.gz_sequence_safety 只在真实的句柄上运行。Goal.gz_refusal 对 29 个函数说明 NULL
的情形:对每个堆、每个世界和其他每个参数,调用返回它文档规定的值,既不改动堆也不改动世界。它没有前置条件。每个子句通过求值成立,因为每个函数都先测试
file == NULL。
非空性
Goal.gz_sequence_nonvacuity 表明序列目标的前提可以被满足。它给出两个具体的历史,各自从满足打开构造子每个前提的调用者堆和世界出发,没有分配失败。
gzopen给出一个满足GzInv的读句柄,它的描述符有有限的读取预算。向调用者缓冲区做一次一字节的gzread满足GzArguments。- 在一个已打开的描述符上,
gzdopen给出一个满足GzInv的写句柄,它保留这个描述符。从调用者缓冲区做一次一字节的gzwrite满足GzArguments。
所以子句 2,以及它对读调用的 (b) 部分,适用于一次长度非零的真实调用。
功能结论
31 个有文档的 gz 函数和 gzvprintf 各有一个功能契约 Goal.<function>:共 32
个目标。安全结论不需要其中任何一个。其中八个有定理:
Goal.gzbuffer、Goal.gzeof、Goal.gzerror、Goal.gzclearerr、Goal.gzdopen:各函数的完整契约:gzbuffer存入的大小(至少为 8)及其拒绝,gzeof的返回值,gzerror的错误码和借用的消息,gzclearerr复位的状态,以及gzdopen对描述符的拒绝或接管。Goal.gzoffset64、Goal.gzoffset和Goal.gzrewind:描述符的位置减去读句柄已缓冲的压缩输入,以及定位回起点并复位读句柄的状态。它们针对普通文件的世界表述(前提RegularOs fs)。
没有定理陈述下面这些:
- 其余 24 个功能契约:
Goal.gzopen、Goal.gzopen64、Goal.gzclose、Goal.gzclose_r、Goal.gzclose_w、Goal.gzread、Goal.gzfread、Goal.gzgetc、Goal.gzgetc_、Goal.gzungetc、Goal.gzgets、Goal.gzdirect、Goal.gzwrite、Goal.gzfwrite、Goal.gzputc、Goal.gzputs、Goal.gzprintf、Goal.gzvprintf、Goal.gzflush、Goal.gzsetparams、Goal.gzseek、Goal.gzseek64、Goal.gztell和Goal.gztell64; - 功能序列目标
Goal.gz_sequence; Goal.gz_initialisation_domain:模式串有效、世界的open成功且没有分配失败时,gzopen返回一个处于初始状态的句柄;并且每个有效的模式都有一次具体的成功打开。