Fil-C on Nix

Filnix wiki

the formal campaign

rocq/theories/Panics.v

Campaign 7's property, never_panics: no run of a program from any admissible input ever reaches a failure (formal.md, Campaign 7).

A failure is what formal.md's panic table rules out: a Fil-C trap that is a capability check failing (a panic, in Filip's meaning), an unchecked access, undefined behaviour, an unreachable reached, or a step that leaves the model. A refusal (out_of_memory, too_big), a return, running out of fuel and a process exit are not failures, and neither is a run that never ends: the property speaks of every state a run reaches, not of how it ends.

This file owns the one classification of endings that both the core machine and Campaign 4's labelled machine use: failure for a core outcome, failure_ending for an ExternalMachine.v ending. The program statement never_panics is over Machine.v's machine for a closed module, one with no external calls; a program that calls libc is stated over the labelled machine with the same failure_ending.

Decisions

DecisionWhy
every runtime R, as a functor argumentthe proof may not depend on where objects are placed or when the runtime refuses an allocation (formal.md's statement)
the run starts ready, an antecedentuntil the heap starts above the module's data (rocq.md), as in Campaign 3
every fuel, and every state reacheddivergence and out_of_fuel are allowed; fuel plays no part
an allocation with a negative extent is a failurethe machine has no step there, so the run left the model
the module's initial memory and its entry function must exist, and every admissible input must make a frameotherwise there is no run to speak of, and the program would hold vacuously
no premise about the runtime's safepointsa safepoint changes no region (Runtime.v's collector_live): Fil-C's collector frees nothing, and a signal handler or a thread that could is the program's code; a module that installs one calls an external with no contract, which ends its run as a failure
From Stdlib Require Import String ZArith List Bool Lia Relations
From Nanofil Require Import Term Syntax Values Memory Runtime Ops Semantics Run Machine ExternalCalls ExternalMachine
Import ListNotations
Open Scope Z_scope

Failures

A trap reason that is a refusal, not a panic: the runtime would not hold an allocation (out_of_memory), or the request is over 2^48 - 1 bytes (too_big), which C's malloc would answer with null. These are mbrock's decisions in formal.md's panic table, and ExternalCalls.v's resource_reason for a call (refusal_resource).

46Definition refusalwhy : reason : Prop ≔
why = OutOfMemory ∨ why = TooBig

The outcome o is a failure: a trap that is not a refusal (every capability check, Early traps of a check_ahead included), an unchecked access, undefined behaviour, or unreachable reached. Returns and OutOfFuel are not.

52Definition failureo : outcome : Prop ≔
match o with
Trapwhy
⇒
¬refusalwhy
⇒
True
⇒
False

The configuration c fails in the genv ge: its step ends in a failure, is stuck (the run left the model: an external call, code outside the core subset, an ill-formed word), or asks for an allocation with a negative extent, which the machine cannot take. An allocation the runtime refuses is not a failure: it ends the run with trap(out_of_memory), a refusal.

65Definition failsge : genv c : config : Prop ≔
match stepge c with
⇒
True
⇒
⇒
False

The labelled machine's ending why is a failure: a core failure, a stuck core step, or a contract violation at a call. A process exit is not.

76Definition failure_endingwhy : ending : Prop ≔
match why with

A refusal is a resource ending of a call, and back.

85Lemma refusal_resource
∀ why
Explore proof 3 tactics

Initial goal

⊢
∀why : reason, refusalwhy ↔ resource_reasonwhy

intros why

why :
⊢

unfold refusal , resource_reason

why :
⊢
why = OutOfMemory ∨ why = TooBig ↔ why = OutOfMemory ∨ why = TooBig

tauto

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros why
tauto

A trap that ends a call for lack of resources is not a failure.

89Lemma resource_not_failure
Explore proof 2 tactics

Initial goal

⊢
∀why : reason, resource_reasonwhy → ¬failureTrapwhy

intros why H Hf

⊢
False

apply Hf , refusal_resource , H

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros why H Hf
apply Hf , refusal_resource , H

The step result r, of a configuration in the memory m, is safe for the invariant inv: a next configuration in inv, an ending that is not a failure, or an allocation with a nonnegative extent whose every fresh base in m gives a configuration in inv. Never stuck.

96Definition safe_stepinv : config → Prop m : mem r : step_result : Prop ≔
match r with
Nextc′
⇒
invc′
⇒
0 ≤ req_extentq ∧ ∀base, freshm q base → invkbase
⇒
False

The property

The property over any runtime R.

107Module Panics R : Runtime
108Module RM ≔ Machine R

The genv of the module md with its globals, whose free is R's.

111Definition program_genvmd : module globals : listname × ptr : genv ≔
mkGenvmd globals R.free

The closed module md never panics when its function entry is called with any arguments xs that input admits: its initial memory exists and the entry is a function of the core subset; every admissible xs makes the entry's frame; and, where R is ready in the initial memory at its start, no state a run reaches from that call, with any fuel, fails. A run is Machine.v's: any fresh base R grants, and anything R does at a safepoint. This is run/5's start (Driver's run).

122Definition never_panicsmd : module entry : name input : listword → Prop : Prop ≔
∃globals m f, initial_memorymd = Someglobals, m ∧ find_fnprogram_genvmd globals entry = SomeDefinedf ∧ ∀xs, inputxs → ∃fr, call_framef xs = Somefr ∧ R.readyR.start m → ∀fuel st, RM.mreachableprogram_genvmd globals mkConfigfr [ ] m fuel, R.start st → ¬failsprogram_genvmd globals fstst

The proof rule for never_panics: an invariant inv of configurations that holds where every admissible call starts, whose every step is safe_step, and that what R does at a due safepoint keeps, where R is ready. Then no state a run reaches fails. Readiness is what makes an allocation's base fresh (R's fresh_allocation); the invariant is the program's own, as Cycle.v's and Buffer.v's assertions at each point.

140Lemma never_panics_by_invariant
∀ md entry input globals m f inv : config → Prop
initial_memorymd = Someglobals, m
find_fnprogram_genvmd globals entry = SomeDefinedf
∀xs, inputxs → ∃fr, call_framef xs = Somefr ∧ ∀fuel, invmkConfigfr [ ] m fuel
∀c s, invc → R.readys c_memc → safe_stepinv c_memc stepprogram_genvmd globals c
∀c s s′ m′, invc → R.readys c_memc → RM.safepoint_dueprogram_genvmd globals c = true → R.safepoints c_memc s′ m′ → invRM.with_memc m′
never_panicsmd entry input
Proof 27 steps Qed
intros md entry input globals m f inv Hm Hf Hin Hstep Hsp
exists globals, m, f
split ; exact Hm |
split ; exact Hf |
intros xs Hxs
destruct Hinxs Hxs as fr & Hfr & Hinv
exists fr
split ; exact Hfr |
intros Hready fuel st Hreach
assert Hgen : ∀st1 st2, RM.mreachableprogram_genvmd globals st1 st2 → invfstst1 ∧ RM.ready_statest1 → invfstst2 ∧ RM.ready_statest2
{intros st1 st2 H
induction H as st1 st2 Hs | st1 | st1 st2 st3 _ IH1 _ IH2 ; auto
intros H0 Hr0
split ; | exact RM.mstep_readyprogram_genvmd globals _ _ eq_refl Hs Hr0
destruct Hs as c c′ s E | c q k s base s′ E He Hal | c s s′ m′ Hdue Hsp′ ; unfold RM.ready_state in Hr0 ; cbn [ fst snd ] in H0 , Hr0 |- * ; pose proof Hstep_ _ H0 Hr0 as Hr
–rewrite E in Hr
exact Hr
–rewrite E in Hr
destruct step_fresh_kept_ _ _ _ E as Ha _
destruct R.fresh_allocation_ _ _ _ _ Hr0 Ha He Hal as Hfresh _
exact proj2Hr base Hfresh
–exact Hspc s s' m' H0 Hr0 Hdue Hsp'
destruct Hgen_ _ Hreach conjHinvfuel Hready as Hst Hrs
unfold fails
pose proof Hstep_ _ Hst Hrs as Hr
destruct stepprogram_genvmd globals fstst ; cbn [ safe_step ] in Hr ; try tauto
lia