Gzip files: the invariant, histories and the OS oracle
The gzip file interface (gzopen, gzread, gzwrite, gzseek, gzclose and the other gz
functions) is safe on every history of a handle, whatever the operating system returns. This
page gives the statement, separates what it assumes, and explains the shape of the proof.
Sources: gzlib.c, gzread.c, gzwrite.c, gzclose.c, gzguts.h and the gzgetc macro of
zlib.h. The API pages give the caller-visible behaviour. Terms:
glossary.
The result
| Goal | Theorem |
|---|---|
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 goals |
GzCallSafetyProof.<function>_safety |
All are safety results, and all are done.
Each of the 31 documented gz functions has its own safety goal, and so has gzvprintf, which
zlib.h lists as undocumented and gzprintf goes through. Each goal is a clause of the
sequence goal for the calls of one function:
- a function that takes a handle and does not close it: clause 2, with that function's clause
of
Goal.gz_refusal, so aNULLhandle is refused with nothing changed.Goal.gzgetc_safetyalso has clause 3, the macro;Goal.gzerror_safetyalso has clause 4, the string it returns; gzclose,gzclose_randgzclose_w: clause 5, with the refusal of aNULLhandle;gzopenandgzopen64: clause 6.gzdopen: clause 7.
The proofs apply gz_sequence_safety_public; the NULL refusals hold by evaluation. So the rest
of this page, which is about the sequence goal, is also the proof of the one-function goals.
Each function also has a functional contract Goal.<function>. These contracts are not
required; the last section says which have a theorem.
The sequence goal covers a program such as this one. The comments name the clause of the goal that covers each call.
gzFile f = gzopen(path, "rb"); /* clause 6: the open returns; no leak when it fails */
n = gzread(f, buf, len); /* clause 2; that it returns needs a finite source */
c = gzgetc(f); /* clause 3: the macro of zlib.h */
msg = gzerror(f, &err); /* clauses 2 and 4: msg is a readable string */
gzclose(f); /* clause 5: everything is freed, also when close fails */
Between two calls the program may change its own memory, and anyone may change the file system. The goal holds for all such histories.
What the goal states
A world is a state of the file system, the descriptor table, errno and the oracle that
chooses the results of system calls (below). A history of a
handle is a sequence of steps that starts at a successful open (below).
Goal.gz_sequence_safety has seven clauses.
- Invariant. After every history the world is well formed (
FileSystem) and the handle satisfies the representation invariantGzInv. - One more call. For every history, every next public call on the handle with permitted arguments, and every world, three parts hold.
- (a) No undefined behaviour and no memory error. The run does not end in
Fault.ub. This part has no further premise. - (b) Termination. The run does not end in
Fault.outOfFuel, so with (a) the call returns. For the six reading callsgzread,gzfread,gzgetc,gzgetc_,gzgetsandgzungetcthis part needs the read-budget premiseReadsFinite. For every other call it holds in every world. - (c) Effect of a call that returned. The set of open descriptors is the same
(
FdsKept). The handle is inGzInvagain, with the same mode and descriptor. The call wrote only the handle's blocks and the caller regions declared for that call. The live blocks changed only by blocks the handle owns: every new live block is owned by the handle, and every block that is gone was owned by it (GzStepPost). So nothing leaks. - The
gzgetc()macro. A use of the macro has the same three parts, with its own termination split (see the macro). - The string of
gzerror. The pointergzerrorreturns is a NUL-terminated string that is readable in the heap after the call: a literal or the handle's message. - Close. Every close call returns. It refuses on the wrong mode and changes nothing, or it
frees the record and every owned block and releases the descriptor, also when
closereports-1(GzReleased). - Open.
gzopenandgzopen64return. A failed open leaves no new block and no new open descriptor. A successful open gives a handle inGzInvthat owns exactly the new blocks. Its descriptor number is not negative and was not open before the call, and no other descriptor number was opened or closed (GzOpenSafe). The clause does not state that the handle's descriptor is open after the call. gzdopen. It returns and opens or closes no descriptor (GzDopenSafe).
Without ReadsFinite, part (a) still holds for a reading call. It is then partial
correctness: no undefined behaviour in any run of fewer than 2^64 trips of each loop. No
real execution reaches that count.
What is assumed
Three different things stand behind the result: premises, a trusted model, and patches to the source. Only the first is in the Lean statement.
Premises in the statement
Each is explicit in Goal.gz_sequence_safety or in GzHistory, the histories it quantifies
over. The rows are in deviations.
| Premise | Where | Meaning |
|---|---|---|
| Caller heap and world at an open | GzHistory.open, open64, dopen; GzOpenSafe, GzDopenSafe |
The heap is well formed (Fresh, Uniq, LibraryGlobals), every byte object has fewer than 2^63 bytes (ByteObjectsFit), the world is well formed (FileSystem), and path and mode are NUL-terminated strings (or NULL, in clauses 6 and 7). |
| Caller buffers | GzArguments, through GzRange |
The buffers of gzread, gzfread, gzwrite, gzfwrite, gzputs, gzgets and gzerror are readable for the requested length, writable where the call stores into them, and lie apart from the blocks the handle owns. The argument of gzputs is a NUL-terminated string. A request of length 0, a request that the C refuses for its size, a gzgets call with a NULL buffer or a length below 1, and a NULL errnum of gzerror carry no buffer premise. |
Arguments of gzprintf and gzvprintf |
GzArguments |
On a file open for writing and not in error, the format is a NUL-terminated string and every pointer argument points into a block that is not freed. The format and every pointer argument lie apart from the handle's blocks. That the vsnprintf call is defined in C for the format and the arguments, with no %n, is the caller's: no premise states it, and the model does not read the conversions of the format (trusted base). |
| Read budget | ReadsFinite |
The handle's descriptor can still deliver fewer than 2^61 bytes. It is a premise of part (b) only, and only for the six reading calls. The premise also says that the descriptor number is not negative. Every handle the library returns has such a number: GzOpenSafe states it for gzopen, and gzdopen returns NULL for a negative descriptor. |
| Caller step between two calls | GzHistory.caller: GzCallerFrame, ByteObjectsFit |
The caller changes only blocks that the handle does not own. The heap after the change is well formed (Fresh, Uniq, LibraryGlobals), and every byte object in it has fewer than 2^63 bytes. |
| World step between two calls | GzHistory.world: GzWorldStep |
The new world is well formed (FileSystem). Nothing else is asked. |
Trusted, not in the statement: the world model
The world and its oracle are a model of Linux written in Lean (external I/O). The kernel checks the proof against that model. It does not check the model against Linux (trusted base). Two facts of the model carry weight in the proof:
- a
writeof a nonempty buffer never returns 0; closereleases the descriptor also when it fails.
The source is the patched source
The statements are about the C with patches 0002 to 0005 applied. The unpatched C has undefined behaviour on some histories: see source reports and patches.
Why the read budget
An endless source makes one gzread call run forever in C: an endless FNAME field, or
endless empty gzip members.
zlib.h does not promise that a read returns on such a source.
The figure 2^61 is the model's limit. A loop of the model has 2^64 trips of fuel. The
reading loops are bounded by measures built from the input left, the read budget and the
bytes still to deliver. A budget below 2^61 keeps those measures below 2^64.
The premise goes by call name (NeedsReadBound). So it is also asked where the C returns at
once: a reading call on a writer, or a request of length 0. gzdirect has no reading loop
and needs no budget. gzseek defers its skip and needs none either.
Source reports and patches
Patches 0002 to 0005 fix five defects of the unpatched C; patch 0003 fixes two of them. The
first table has one row for each. Findings lists them with their evidence, and patches/README.md is
the authoritative list of patches. Each of the four patches is submitted upstream, and each of the
pull requests is open. The invariant has its form because of the first four defects and
because of the two cases of the second table, which no patch changes.
| Case | Behaviour of the unpatched C | Evidence and fix |
|---|---|---|
| Negative seek position | After an initial gzungetc, GZ_OFF_MAX - pos or a later position difference overflowed signed 64-bit arithmetic. |
Reproduced under a sanitizer (findings). Patch 0002, upstream PR 1361. |
| Partial read, then an error | In the COPY case of gz_fetch, gz_load could leave a nonzero x.have on error before x.next = out ran; gz_read then copied from a stale pointer. |
Reproduced under a sanitizer (findings). Patch 0003, upstream PR 1405. |
| Read position overflow | A transparent seek on a device whose lseek succeeds without moving set x.pos to GZ_OFF_MAX; the next read overflowed it. |
Reproduced under a sanitizer (findings). Patch 0003, upstream PR 1405, keeps x.pos + x.have ≤ GZ_OFF_MAX on return from every call. |
| Write position overflow | A forward seek of a transparent writer to near GZ_OFF_MAX, then a write, overflowed x.pos. |
Reproduced under a sanitizer (findings). Patch 0004, upstream PR 1406, refuses a write that would pass GZ_OFF_MAX. |
| Negative descriptor offset | gzoffset64 took only -1 from lseek as a failure. Another negative result, less the buffered input of a reader, overflowed signed 64-bit arithmetic. |
Reproduced under a sanitizer (findings). Patch 0005, upstream PR 1404, returns -1 for every negative result of lseek. |
| Case | Behaviour of the C, patched or not | How the proof treats it |
|---|---|---|
| Unwritten pointer | gz_reset leaves x.next unwritten; gzseek64 and gz_skip_have add zero to it. |
Undefined by the letter of C; no sanitizer reports it. The model accepts adding zero to every pointer value (model limits). |
| Caller-buffer lifetime | A direct read sets x.next into the caller's buffer and keeps it with x.have = 0. After the caller has freed the buffer, gzseek64 and gz_skip_have add zero to it. |
Undefined by the letter of C; no sanitizer reports it. The same rule of the model applies. gzseek64_dangling_next_ok shows that a forward seek of a reader with nothing buffered does not fault, whatever x.next holds. |
Histories
GzHistory h fs i says that heap h and world fs are reached by some actual history of
handle i. It has seven constructors; the table puts the three opens in one row.
| Constructor | Step |
|---|---|
open, open64, dopen |
A successful gzopen, gzopen64 or gzdopen from a caller heap and a world that satisfy the first row of the premise table, with string arguments that are not NULL. |
step |
A public call on the handle (GzOperation) with permitted arguments (GzArguments) that returned. |
getcMacro |
A use of the gzgetc() macro that returned. |
caller |
The caller changes its own memory: any block the handle does not own. It may free its buffers, including the last gzread buffer. The heap after the change is well formed (GzCallerFrame: Fresh, Uniq, LibraryGlobals) and its byte objects fit (ByteObjectsFit). The world is unchanged. |
world |
Another party changes the world (GzWorldStep): to any well-formed file-system state. The heap is unchanged. |
The world step is deliberately wide. Another handle or the application may close the
handle's descriptor, or open another file under its number. The next read or write then gets
an error or reaches the other file, as in C. The step may also replace the oracle.
GzHistory has no budget premise, so clause 1 holds on every history. The functional gz goals
are stated over a different predicate, GzReachable; the safety goal does not use it.
The world and its oracle
The world is a record Fs beside the heap. A gz computation takes a
world and a heap and returns a value and both, or a fault. The world holds files, the
descriptor table, errno, and an oracle that chooses the result of every read, write,
lseek, close, open and caller-format vsnprintf within the contract of that call.
External I/O has the table of what the oracle may
choose.
The oracle is wider than a regular file: for example, a read may succeed whatever the descriptor's state. Every clause quantifies over all worlds, so no proof step can depend on the file being a regular file.
The external calls fall into two groups.
- The five system calls leave the heap alone. The model functions
fsRead,fsWrite,fsLseek,fsCloseandfsOpentake a world and return a result and a new world. For every oracle value each ispureof a result that depends on the world only: it never faults and never changes the heap (fsRead_pure,fsWrite_pure,fsLseek_pure,fsClose_pure,fsOpen_pure).fsReadreturns the bytes it read as a value. The translation ofgz_loadthen stores them atbuf(storeBytes); that store is a checked heap copy, and it is a step of the translated C, not of the system call. The copy goes through a temporary block that it creates and frees, so it also advances the heap's block counter (nextBlk). - Two library calls change the heap.
vsnprintfstores into its destination: the formatted bytes and a NUL, or, when the call fails, bytes of the oracle's choice and a NUL, in both cases inside thesizebytes it was given. The call fails when the oracle says so, and also when the formatted output is longer thanINT_MAXbytes. It faults when the format is not a string or is one the model's formatter does not represent, or when the destination is not writable for those bytes.vsnprintf_inshows that the call ingzvprintf, whose destination is in the handle'sinbuffer, returns for every oracle value, keepsGzInvand writes only blocks the handle owns.zstrerror, the model ofstrerror(errno), allocates nothing and returns a borrowed string that is not a heap block. It changes one heap field,libcErrorBorrow, which records which error text is on loan; no block, liveness flag or allocator field changes (zstrerror_run,zstrerror_no_malloc).
The contract of read is fsRead_contract, with its budget accounting (BudgetAcc,
fsRead_budget). The contract of write for every oracle value is fsWrite_contract.
Proof structure
flowchart TD
G["gz_sequence_safety_public"] --> A["gz_sequence_safety_of: assembly"]
A --> H["history_inv: induction on GzHistory"]
A --> O["operation_safe: dispatch over the call"]
A --> C["close_safe"]
A --> E["gzerror_string"]
A --> P["gzopen_safe, gzopen64_safe, gzdopen_safe"]
O --> Q["queries, seek, rewind, clearerr"]
O --> W["write leaves"]
O --> R["six read leaves: GzReadLeaves"]
A --> M["gzgetc_macro_safe"]
M --> R
Safety of one call has one shape, GzCallSafe i call: for every heap, well-formed world and record in
GzInv and every permitted argument, the three parts of clause 2 hold. A leaf is a lemma
that proves GzCallSafe for one public function.
The assembly gz_sequence_safety_of has two steps.
history_invgoes by induction onGzHistory. The open constructors use the open lemmas. Astepuses part (c) of the call's leaf. Acallerstep usesGzInv.caller: the invariant reads the handle's blocks, which the step keeps, and the well-formedness and byte-object size of the whole heap, which the step supplies for the new heap. Aworldstep changes no heap, and the invariant does not mention the world.operation_safedispatches a call to its leaf.close_safedoes the same for the three close calls.
The leaves of the read side are bundled in GzReadLeaves: gzread_step, gzfread_step,
gzgetc_step, gzungetc_step, gzgets_step and gzdirect_step. gzgetc_ is gzgetc by
definition, so it has no leaf of its own. (gzdirect is on the read side but is not one of the
six calls that need the read budget.) gz_sequence_safety_of takes the bundle as its only argument, and
gz_sequence_safety_public supplies it. Every leaf is a theorem with no premise.
The invariant GzInv
GzInv h i s is the representation invariant of an open handle i with record s. It has a
common part and a part per mode. The proofs use it through its interface lemmas
(GzInv.common, GzInv.reader, GzInv.writer, GzInv.state_eq, GzInv.pos_lower).
The fields it speaks about are those of gz_state in gzguts.h:
| Field | Meaning in the C |
|---|---|
x.have, x.next, x.pos |
The public prefix gzFile_s: bytes of output buffered at x.next, and the position in the uncompressed data. The gzgetc macro reads and writes them directly |
mode, fd, path |
Read or write; the descriptor; the name for error messages |
size, want |
The buffer size, 0 while the buffers do not exist; the requested size |
in, out |
The input and output buffers |
strm |
The embedded z_stream; below, "the codec" is the inflate or deflate state behind it |
how |
Reader: LOOK (look for a gzip header), COPY (copy the input unchanged, "transparent"), GZIP (inflate a gzip member) |
direct |
0 when processing gzip, 1 when transparent. A reader opened for gzip only (mode letter G) holds -1 until gz_look selects gzip decoding |
junk |
Reader: -1 at the start, 1 for a junk candidate, 0 inside gzip data |
eof, past, again |
The input ended; a read was asked past the end; the last I/O was refused with EAGAIN |
skip |
The distance of a pending seek |
err, msg |
The error code and message |
On the LP64 build, offsets are signed 64-bit with GZ_OFF_MAX = 2^63 - 1, and one I/O request
is at most 2^30 bytes.
The three lists below are a summary in plain words. Clause names are in parentheses where the page uses them later.
Common part (GzCommon).
- The record is in the heap and the mode is read or write.
- The heap is well formed (
Fresh,Uniq,LibraryGlobals) and every byte object has fewer than2^63bytes (ByteObjectsFit). The embedded codec needs both at each of its calls. pathis an owned NUL-terminated string.msgisNULLor an owned string, and isNULLafterZ_MEM_ERROR.8 ≤ want < 2^31, andsizeis 0 orwant.size = 0means that the buffers and the codec do not exist yet.- The owned blocks are live, distinct, different from the record, and not owned by the embedded codec. The codec does not own the record block.
- Positions:
0 ≤ skip,x.pos + skip ≤ GZ_OFF_MAX, and0 ≤ x.pos + x.have. x.next: with buffered output (x.have ≠ 0) it points into an owned block other than the record and the message, withx.havebytes after it (next). Withx.have = 0the invariant says nothing about where it points. ANULLx.nexthasx.have = 0.
Reader part (GzReadInv).
howisLOOK,COPYorGZIP, with the permitted values ofdirect,junkand the flagseof,past,again.- Without buffers (
size = 0) there is no codec (strm.state = NULL), no buffered output and no pending input;howisLOOKandagainis 0. - With buffers (
size ≠ 0),inis a writable block of exactlysizebytes andoutone of exactly2·size. - Pending input (
avail_in ≠ 0) lies inin:next_in = in + awitha + avail_in ≤ size. Buffered output lies inout:x.next = out + cwithc + x.have ≤ 2·size. - With buffers, the embedded stream is in the inflate history (
StreamReachable .inflate), with no header record. x.pos + x.have ≤ GZ_OFF_MAX(posHave).- Buffered output means no pending skip (
haveSkip). - A reader that stalled at the end of its input has no pending input (
againEof). erris neverZ_STREAM_END.COPYhas no pending input. With buffers, the stream's message isNULLor a literal.
Writer part (GzWriteInv).
x.have = 0. Thegzgetcmacro readsx.haveon any handle.directis 0 (a compressing writer) or 1 (a transparent writer), andresetis 0 or 1.- Without buffers there is no codec (
strm.state = NULL). - With buffers,
inis a writable block of exactly2·sizebytes. A compressing writer hasoutwith exactlysizebytes. A transparent writer has no codec, and the invariant does not countoutamong its owned blocks; it says nothing else of that field. next_inisNULLwithavail_in = 0, or the buffers exist and the pending input lies in the first half ofin:next_in = in + awitha + avail_in ≤ size.- For a compressing writer with buffers,
next_out = out + bandx.next = out + cwithc ≤ b ≤ size, andavail_out = size - b. The embedded stream is in the deflate history, with no gzip header record.
The complete statement is the definition GzInv, with its
parts GzCommon, GzReadInv and GzWriteInv; where this summary and the definition differ,
the definition holds.
Each clause exists because a call needs it. Three examples show the pattern.
- Without
posHave, the buffered path ofgzgetcoverflowsx.pos. - Without
haveSkip,gzgetcreturns a buffered byte while a skip is pending and movesx.pospastGZ_OFF_MAX - skip. - Without
againEof,gz_readloops forever:gz_availreads nothing ateof, andgz_lookreturns 0.
Two weaker forms hold inside a reading call. GzInvUpToOutput is GzInv of the record with
its buffered output cleared: a direct read leaves x.next in the caller's buffer.
GzInvUpToSkip is GzInv without haveSkip: gz_look and gz_fetch may buffer output
while a skip is pending, and the caller consumes it before it returns.
Pointer fields of a fresh record
gz_open does not write strm.state, strm.next_in or x.next. In the model a fresh
pointer is NULL. In C it is indeterminate, and reading it is undefined
(safety, uninitialised memory).
strm.stateandstrm.next_in: the invariant statesstrm.state = NULLwhilesize = 0. The proof shows safety for the translation. It does not show that C code which read an indeterminate pointer would be caught: that is the model gap of trusted base, section 2. not yet confirmed by source review: the C never readsstrm.stateorstrm.next_inbeforegz_lookorgz_initwrites them.x.next: the invariant claims nothing about it whilex.have = 0. Every read throughx.nextand every advance of it by a nonzero count happens withx.have ≠ 0. Withx.have = 0,gzseek64andgz_skip_haveadd zero to it, which the model accepts for every pointer value (model limits).
Read side
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 accumulates bytes until the request is filled or a read stops it. A positive read
advances have; zero sets eof; a blocking refusal sets again; another failure sets an
error. A failure can follow successful partial reads.
gz_look sets up the buffers and the codec on its first call, then decides how to read. It
recognises gzip only with at least four available bytes: magic 31, 139, method 8 and a
flags byte below 32. Otherwise the input is transparent when the mode allows it.
gz_decomp runs inflate on the embedded stream until the output is full, the member ends,
the input ends or an error occurs. The member-end path returns to detection, for
concatenated members.
gz_read has three data paths: consume buffered output, read transparent data directly into
the caller's buffer, or inflate directly into a large enough caller buffer.
The read helpers compose in this order:
| Lemma | Statement |
|---|---|
gz_look_safe |
gz_look is safe. |
gz_decomp_safe_of |
gz_decomp is safe, given that an inflate call from mode BAD or MEM moves neither buffer. That fact is inflateStuckNoOutput_holds. |
gz_fetch_safe_of |
gz_fetch is safe, given gz_look and gz_decomp. |
gzSkipRead_holds |
gz_skip is safe, given gz_fetch. |
gz_read_safe_of |
gz_read is safe, given gz_skip, gz_fetch and gz_decomp. |
gzread_step, gzfread_step |
The public calls, from gz_read. |
Each embedded inflate call uses the stream results of stream decoding: the
embedded stream is reachable, so the full contract of one call applies.
Termination of the read loops
Every reading loop has a measure, a natural number computed from the world and the handle.
With ReadsFinite the measure starts below 2^64 and falls on every trip that continues. The
table gives the shape of each measure; the exact definitions are fetchMeasure,
fetchRank and readMeasure.
Write inputLeft for the read budget of the descriptor plus avail_in. gz_avail raises
avail_in by the bytes it reads, and the budget falls by the same bytes (gz_avail_budget). So inputLeft never rises.
| Loop | Measure | Why it falls |
|---|---|---|
gz_decomp |
inputLeft + avail_out |
It falls on each trip that continues. |
gz_fetch |
4 · inputLeft + c, with c = 2 for LOOK, 1 for GZIP at the head of a member, 0 for COPY, 3 otherwise |
It falls on each trip that continues. An empty gzip member costs input, so endless empty members are excluded by the budget. |
gz_read |
readMeasure: with L = min(len, GZ_OFF_MAX - pos), it is L / 8 + Q + 2·E + 3·R + fetchRank. Q is 1 with no buffered output; 2 with fewer than 16 buffered bytes, err = Z_OK and x.pos + x.have < GZ_OFF_MAX; 0 otherwise. E is 0 at the end of the input and 1 before it. R is 1 while pos is below GZ_OFF_MAX. fetchRank is 4 · inputLeft, plus the read budget, plus 2 while a gzip member is under way past its head, plus 2 until how is COPY |
It falls on each trip that continues. Neither gz_decomp nor gz_fetch raises fetchRank. |
gzgets |
Its loop variable left |
It falls on each trip that continues. |
gz_skip |
skipMeasureF |
gzSkipTerminates_holds, from GzInvUpToSkip. |
Reader wrappers
The wrappers keep the check order of the C. gzread checks that its unsigned request fits
int. gzfread checks the size_t product before it divides. gzgets reserves room for
the NUL, bounds its memchr by min(have, left), and writes the final NUL at buf[len - 1]
at most. gzungetc runs gz_look and gz_skip first, then pushes back inside out; it can
set x.pos = -1 at the start of a file, which is why the invariant bounds x.pos + x.have
and not x.pos.
The gzgetc macro
zlib.h defines gzgetc as a macro:
#define gzgetc(g) \
((g)->have ? ((g)->have--, (g)->pos++, *((g)->next)++) : (gzgetc)(g))
It is the default way an application calls gzgetc, so the history has a constructor for it
(GzHistory.getcMacro) and the goal has a clause for it. The translation is
Zlib.ZlibH.gzgetc; the proof is gzgetc_macro_safe.
The macro has two branches.
- Buffered output (
x.have ≠ 0). The macro changesx.have,x.posandx.nextinline, with no library call. Unlike the function, it does not clearerrandmsgwhenagainis set. This branch returns with no premise on the world.GzCommon.nextputsx.nextinside an owned buffer withx.havebytes after it,posHavekeepsx.pos + 1representable, andhaveSkipgivesskip = 0. A writer hasx.have = 0, so the inline branch runs only on a reader. - No buffered output (
x.have = 0). The macro calls the functiongzgetc. This branch is the read leafgzgetc_step, and it returns underReadsFinite.
In both branches the effect is that of the function, which writes no caller region.
On a NULL handle the macro reads (g)->have first, which is undefined behaviour in C.
Goal.gz_refusal states the NULL case for the function (gzgetc)(file) only.
Write side
gz_init allocates the double input buffer and, for compressed output, the output buffer
and the codec. gz_comp writes the input directly for transparent output, or alternates
deflate calls and output writes. gz_write copies small input into in, or points
next_in at the caller's large buffer and resets it afterwards. gz_zero resolves a pending
forward seek by writing zeros. gz_vacate compresses pending data and moves the rest to the
front.
The write leaves are gzwrite_step, gzfwrite_step, gzputc_step, gzputs_step,
gzprintf_step, gzvprintf_step, gzflush_step, gzsetparams_step and gzclose_w_step.
They use the facts of gz_error, which follow from the invariant.
The loops of gz_comp terminate in every world, with no budget. The write-out loop is measured
by the bytes still to write, and the transparent loop by the pending input. Both fall because a
write of a nonempty buffer returns -1 or a count between 1 and the length
(fsWrite_contract). That is the trusted fact about write
above. The deflate loop has its own measure,
which falls whenever the loop continues.
Not covered: a system whose write returns 0 for a nonempty buffer. not yet confirmed: by a
reading of the C, a write that returned 0 forever would make gz_comp loop forever, because
neither write loop advances on a count of 0.
gzvprintf writes a sentinel at next[size - 1] and formats with capacity size. A length
outside 1..size-1, or a lost sentinel, makes gzvprintf refuse the result.
gzsetparams flushes pending data, calls deflateParams, then stores the requested level
and strategy. It ignores the callee's result. The safety proof does not need that result.
Positions, seeking and error ownership
gztell64 reports the logical position plus a pending skip; when past is set it leaves the
skip out.
gzoffset64 queries the descriptor position and subtracts buffered compressed input in read
mode. It returns -1 for every negative result of lseek (patch 0005), so the subtraction
does not overflow. These are different positions.
gzseek64_step and gzseek_step hold for every world. The
paths are:
- a refusal (a serious error, a bad
whence, a target outside the range of patch 0002):-1, nothing changes; - a writer:
skipbecomes the distance; for a target behindx.posthe call returns-1; - a reader in transparent mode: one
lseek. The displacementpos - x.pos - havedoes not overflow, byposHave; - a reader going back:
gzrewind, then the whole distance becomesskip; - a reader going forward, also from a negative
x.posaftergzungetc: buffered bytes are consumed and the rest becomesskip.
haveSkip holds after each path. lseek may return anything the oracle chooses. It changes
only the call counter, errno and, for a regular file, the position of the one descriptor.
So the world stays well formed and the open descriptors are kept.
gz_error frees the old owned message first. A memory error allocates no new message; any
other message owns the allocation path + ": " + text. gzerror returns the memory-error
literal, the current message or the empty literal, and may store the code into the caller's
four-byte cell. gzerror_step and gzerror_string show
that the store keeps the invariant and that the returned pointer is a string in the heap
after the call. The string is freed by the next call that reaches gz_error; the caller
premise on gzprintf arguments excludes passing it back to the same handle.
Open and close
gzopen_safe, gzopen64_safe and gzdopen_safe show that a fresh handle is in GzInv. An open gives size = 0, so
every clause about buffers or buffered output holds vacuously.
gzclose reads the mode and runs gzclose_r or gzclose_w. A handle in GzInv is a reader or a writer, so gzclose
never refuses. gzclose_r ends the codec when it exists, frees the buffers, the message, the
path and the record, and closes the descriptor. gzclose_w also resolves pending zeros and
finishes the output first. Cleanup happens also when those operations fail. A successful
gzdopen takes over the descriptor; a failed one leaves it with the caller.
The NULL handle
Goal.gz_sequence_safety runs only on a real handle. Goal.gz_refusal states the NULL
case for 29 functions: for every heap, every world and every other argument, the call
returns its documented value and changes neither the heap nor the world. It has no
precondition. Each clause holds by evaluation, because each function tests file == NULL
first.
Non-vacuity
Goal.gz_sequence_nonvacuity shows that the premises of the sequence goal can be met. It
gives two concrete histories, each from a caller heap and a world that satisfy every premise
of the opening constructor, with no allocation failure.
gzopengives a reading handle inGzInvwhose descriptor has a finite read budget. A one-bytegzreadinto a caller buffer satisfiesGzArguments.gzdopenon an open descriptor gives a writing handle inGzInvthat keeps the descriptor. A one-bytegzwritefrom a caller buffer satisfiesGzArguments.
So clause 2, and its part (b) for a reading call, apply to a real call with a nonzero length.
Functional results
There is one functional contract Goal.<function> for each of the 31 documented gz functions
and for gzvprintf: 32 goals. None is required for the safety results. Eight of them have a
theorem:
Goal.gzbuffer,Goal.gzeof,Goal.gzerror,Goal.gzclearerr,Goal.gzdopen: the full contract of each function: the sizegzbufferstores (at least 8) and its refusals, the value ofgzeof, the code and borrowed message ofgzerror, the stategzclearerrresets, and the refusal or ownership of the descriptor bygzdopen.Goal.gzoffset64,Goal.gzoffsetandGoal.gzrewind: the descriptor position minus the compressed input a reader has buffered, and the seek back to the start with the reset of the reader's state. They are stated for the regular-file world (premiseRegularOs fs).
No theorem states these:
- the other 24 functional contracts:
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.gztellandGoal.gztell64; Goal.gz_sequence, the functional sequence goal;Goal.gz_initialisation_domain:gzopenreturns a handle in its initial state when the mode string is valid, theopenof the world succeeds and no allocation fails; and every valid mode has a concrete successful open.