Fil-C on Nix

Filnix wiki

the formal campaign

rocq/theories/ContractFrame.v

The program logic's frame for external calls (Logic.v, docs/logic.md): what a call through a contract leaves of the ghost heap of Heap.v.

A call changes memory along an effects path of Campaign 4 (ExternalCalls.v): local_effect segments, which write bytes and aux slots only where the call has write_authority and change an object only by freeing a live heap object it may release or allocated itself, and allocations at a fresh base, which join the call's born objects. The program logic owns pieces of memory (agrees with a ghost heap h), and asks what of them survives the call.

The premise is separation by address, not by identity: no address of a contract's writable roots lies in a live object that owns a piece of h (roots_apart), and the contract releases none of h's identities (ids_apart). Then the call's born objects are not the program's, it writes nothing the program owns, and after the whole path h still agrees with memory and live objects are still apart (Logic.v's effects_agrees, prefix_agrees and invoke_agrees, over the language's own call relations). A world's new roots that a call delegates from its old roots and born objects stay apart as well (delegates_apart).

A call may also write blocks the program hands it, such as mbrtowc's output, state and errno cells. Then its roots touch the program's objects only at the addresses of those blocks (roots_out), and every piece but the handed-over ones keeps agreeing (agrees_except, local_agrees_out; Logic.v's effects_agrees_out and prefix_agrees_out).

Byte and aux pieces of an object that is not live need only stay registered, and an aux piece of a live one is known up to aux_holds; regions of old identities change only by being freed, so a freed capability stays freed and one that traps as freed keeps trapping (freed_in_step, traps_as_freed_step). Released or not, no piece but a life token needs its object kept live; a life token does, which is what ids_apart of the releases gives.

From iris.proofmode Require Import proofmode
From Stdlib Require Import ZArith Lia
From Nanofil Require Import Term Syntax Values Memory Runtime Identity ExternalCalls Pieces Heap
Open Scope Z_scope
Open Scope list_scope

Separation of a call from the program's pieces

The address a lies in a live object of m that owns a piece of memory in the ghost heap h.

50Definition owned_liveh : gmappiece pval m : mem a : Z : Prop ≔
∃l v reg, h !! l = Somev ∧ mem_piecel ∧ live_atm piece_idl reg ∧ piece_idl ≤ a < r_endreg

No address of the spans roots lies in a live object owning a piece of h.

56Definition roots_apartroots : listspan h : gmappiece pval m : mem : Prop ≔
∀s a, Ins roots → span_containss a → ¬owned_liveh m a

None of the identities bs is that of a piece of memory in h.

60Definition ids_apartbs : listZ h : gmappiece pval : Prop ≔
∀b l v, Inb bs → h !! l = Somev → mem_piecel → piece_idl ≠ b

A call whose roots are apart from h and whose born objects are none of h's has no write_authority over an address of a live object owning a piece of h: a born live heap object overlapping it would be another live object over the same address.

67Lemma owned_not_authority
∀ roots born h m a
¬write_authorityroots born m a
Explore proof 5 tactics

Initial goal

⊢
∀roots : listspan born : listZ h : gmappiece pval m : mem a : Z, live_disjointm → roots_apartroots h m → ids_apartborn h → owned_liveh m a → ¬write_authorityroots born m a

intros roots born h m a Hd Hr Hb Ho s & Hin & _ & Hs | base & reg & Hin & E & _ & L & Ha

2 open

roots :
listspan
born :
listZ
h :
m :
a :
Z
Hr :
roots_apartroots h m
Hb :
ids_apartborn h
Ho :
s :
Hin :
Ins roots
⊢
False
focused goal
roots :
listspan
born :
listZ
h :
m :
a :
Z
Hr :
roots_apartroots h m
Hb :
ids_apartborn h
Ho :
base :
Z
reg :
Hin :
Inbase born
E :
object_regionbase m_regionsm = Somereg
L :
r_lifereg = Live
Ha :
base ≤ a < r_endreg
⊢
False

–exact Hrs a Hin Hs Ho

deferred goal
roots :
listspan
born :
listZ
h :
m :
a :
Z
Hr :
roots_apartroots h m
Hb :
ids_apartborn h
Ho :
base :
Z
reg :
Hin :
Inbase born
E :
object_regionbase m_regionsm = Somereg
L :
r_lifereg = Live
Ha :
base ≤ a < r_endreg
⊢
False

–destruct Ho as l & v & reg0 & Hl & Hm & Hlive & Ha0

roots :
listspan
born :
listZ
h :
m :
a :
Z
Hr :
roots_apartroots h m
Hb :
ids_apartborn h
v :
reg0 :
Hl :
h !! l = Somev
Hlive :
Ha0 :
piece_idl ≤ a < r_endreg0
base :
Z
reg :
Hin :
Inbase born
E :
object_regionbase m_regionsm = Somereg
L :
r_lifereg = Live
Ha :
base ≤ a < r_endreg
⊢
False

specialize Hbbase l v Hin Hl Hm

roots :
listspan
born :
listZ
h :
m :
a :
Z
Hr :
roots_apartroots h m
base :
Z
Hb :
piece_idl ≠ base
v :
reg0 :
Hl :
h !! l = Somev
Hlive :
Ha0 :
piece_idl ≤ a < r_endreg0
reg :
Hin :
Inbase born
E :
object_regionbase m_regionsm = Somereg
L :
r_lifereg = Live
Ha :
base ≤ a < r_endreg
⊢
False

destruct Hdpiece_idl reg0 base reg Hlive conjE L Hb ; lia

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros roots born h m a Hd Hr Hb Ho s & Hin & _ & Hs | base & reg & Hin & E & _ & L & Ha
–exact Hrs a Hin Hs Ho
–destruct Ho as l & v & reg0 & Hl & Hm & Hlive & Ha0
specialize Hbbase l v Hin Hl Hm
destruct Hdpiece_idl reg0 base reg Hlive conjE L Hb ; lia

Steps that keep old identities

A freed object's capability stays freed across a step that keeps every identity (ids) and changes an object only by ending a live one (region_step).

83Lemma freed_in_step
∀ m m′ c
Explore proof 6 tactics

Initial goal

⊢
∀m m′ : mem c : cap, idsm m′ → region_stepm m′ → freed_inm_regionsm c → freed_inm_regionsm′ c

intros m m′ c Hi Hs b & reg & Hc & E & L

m, m′ :
c :
Hi :
idsm m′
Hs :
b :
Z
reg :
Hc :
c = Objb ∨ c = Rob
E :
L :

destruct Hib reg E as reg′ E′

m, m′ :
c :
Hi :
idsm m′
Hs :
b :
Z
reg :
Hc :
c = Objb ∨ c = Rob
E :
L :
reg′ :
E′ :
object_regionb m_regionsm′ = Somereg′

destruct Hsb reg′ E′ as reg0 & E0 & → | L0 & _ ; rewrite E in E0 ; injection E0 as ←

2 open

m, m′ :
c :
Hi :
idsm m′
Hs :
b :
Z
reg :
Hc :
c = Objb ∨ c = Rob
E :
L :
E′ :
object_regionb m_regionsm′ = Somereg
focused goal
m, m′ :
c :
Hi :
idsm m′
Hs :
b :
Z
reg :
Hc :
c = Objb ∨ c = Rob
E :
L :
reg′ :
E′ :
object_regionb m_regionsm′ = Somereg′
L0 :
r_lifereg = Live

–exists b, reg

2 open

m, m′ :
c :
Hi :
idsm m′
Hs :
b :
Z
reg :
Hc :
c = Objb ∨ c = Rob
E :
L :
E′ :
object_regionb m_regionsm′ = Somereg
⊢
c = Objb ∨ c = Rob ∧ object_regionb m_regionsm′ = Somereg ∧ r_lifereg = Freed
deferred goal
m, m′ :
c :
Hi :
idsm m′
Hs :
b :
Z
reg :
Hc :
c = Objb ∨ c = Rob
E :
L :
reg′ :
E′ :
object_regionb m_regionsm′ = Somereg′
L0 :
r_lifereg = Live

auto

deferred goal
m, m′ :
c :
Hi :
idsm m′
Hs :
b :
Z
reg :
Hc :
c = Objb ∨ c = Rob
E :
L :
reg′ :
E′ :
object_regionb m_regionsm′ = Somereg′
L0 :
r_lifereg = Live

–congruence

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros m m′ c Hi Hs b & reg & Hc & E & L
destruct Hib reg E as reg′ E′
destruct Hsb reg′ E′ as reg0 & E0 & → | L0 & _ ; rewrite E in E0 ; injection E0 as ←
–exists b, reg
auto
–congruence

A capability that traps as a freed one keeps doing so across such a step: its object's region is kept, or emptied.

94Lemma traps_as_freed_step
Explore proof 10 tactics

Initial goal

⊢
∀m m′ : mem c : cap, idsm m′ → region_stepm m′ → traps_as_freedm_regionsm c → traps_as_freedm_regionsm′ c

intros m m′ c Hi Hs H a size r align Hsz

m, m′ :
c :
Hi :
idsm m′
Hs :
a, size :
Z
align :
Z
Hsz :
0 < size
⊢
cap_access_resc m_regionsm′ a size r align = SomeRTrapOutOfBounds

specialize Ha size r align Hsz

m, m′ :
c :
Hi :
idsm m′
Hs :
a, size :
Z
align :
Z
H :
cap_access_resc m_regionsm a size r align = SomeRTrapOutOfBounds
Hsz :
0 < size
⊢
cap_access_resc m_regionsm′ a size r align = SomeRTrapOutOfBounds

assert Hempty : ∀b, b ≤? a && a + size ≤? b = false

2 open

m, m′ :
c :
Hi :
idsm m′
Hs :
a, size :
Z
align :
Z
H :
cap_access_resc m_regionsm a size r align = SomeRTrapOutOfBounds
Hsz :
0 < size
⊢
∀b : Z, b ≤? a && a + size ≤? b = false
focused goal
m, m′ :
c :
Hi :
idsm m′
Hs :
a, size :
Z
align :
Z
H :
cap_access_resc m_regionsm a size r align = SomeRTrapOutOfBounds
Hsz :
0 < size
Hempty :
∀b : Z, b ≤? a && a + size ≤? b = false
⊢
cap_access_resc m_regionsm′ a size r align = SomeRTrapOutOfBounds

{intros b

2 open

m, m′ :
c :
Hi :
idsm m′
Hs :
a, size :
Z
align :
Z
H :
cap_access_resc m_regionsm a size r align = SomeRTrapOutOfBounds
Hsz :
0 < size
b :
Z
⊢
b ≤? a && a + size ≤? b = false
deferred goal
m, m′ :
c :
Hi :
idsm m′
Hs :
a, size :
Z
align :
Z
H :
cap_access_resc m_regionsm a size r align = SomeRTrapOutOfBounds
Hsz :
0 < size
Hempty :
∀b : Z, b ≤? a && a + size ≤? b = false
⊢
cap_access_resc m_regionsm′ a size r align = SomeRTrapOutOfBounds

destruct Z.leb_specb a ; cbn [ andb ] ; apply Z.leb_gt ; lia | reflexivity

deferred goal
m, m′ :
c :
Hi :
idsm m′
Hs :
a, size :
Z
align :
Z
H :
cap_access_resc m_regionsm a size r align = SomeRTrapOutOfBounds
Hsz :
0 < size
Hempty :
∀b : Z, b ≤? a && a + size ≤? b = false
⊢
cap_access_resc m_regionsm′ a size r align = SomeRTrapOutOfBounds

assert Hreg : ∀b reg, object_regionb m_regionsm = Somereg → object_regionb m_regionsm′ = Somereg ∨ object_regionb m_regionsm′ = SomemkRegionb b r_kindreg Freed

2 open

m, m′ :
c :
Hi :
idsm m′
Hs :
a, size :
Z
align :
Z
H :
cap_access_resc m_regionsm a size r align = SomeRTrapOutOfBounds
Hsz :
0 < size
Hempty :
∀b : Z, b ≤? a && a + size ≤? b = false
⊢
∀b : Z reg : region, object_regionb m_regionsm = Somereg → object_regionb m_regionsm′ = Somereg ∨ object_regionb m_regionsm′ = Somer_base ≔ b; r_end ≔ b; r_kind ≔ r_kindreg; r_life ≔ Freed
focused goal
m, m′ :
c :
Hi :
idsm m′
Hs :
a, size :
Z
align :
Z
H :
cap_access_resc m_regionsm a size r align = SomeRTrapOutOfBounds
Hsz :
0 < size
Hempty :
∀b : Z, b ≤? a && a + size ≤? b = false
Hreg :
∀b : Z reg : region, object_regionb m_regionsm = Somereg → object_regionb m_regionsm′ = Somereg ∨ object_regionb m_regionsm′ = Somer_base ≔ b; r_end ≔ b; r_kind ≔ r_kindreg; r_life ≔ Freed
⊢
cap_access_resc m_regionsm′ a size r align = SomeRTrapOutOfBounds

{intros b reg E

2 open

m, m′ :
c :
Hi :
idsm m′
Hs :
a, size :
Z
align :
Z
H :
cap_access_resc m_regionsm a size r align = SomeRTrapOutOfBounds
Hsz :
0 < size
Hempty :
∀b : Z, b ≤? a && a + size ≤? b = false
b :
Z
reg :
E :
⊢
object_regionb m_regionsm′ = Somereg ∨ object_regionb m_regionsm′ = Somer_base ≔ b; r_end ≔ b; r_kind ≔ r_kindreg; r_life ≔ Freed
deferred goal
m, m′ :
c :
Hi :
idsm m′
Hs :
a, size :
Z
align :
Z
H :
cap_access_resc m_regionsm a size r align = SomeRTrapOutOfBounds
Hsz :
0 < size
Hempty :
∀b : Z, b ≤? a && a + size ≤? b = false
Hreg :
∀b : Z reg : region, object_regionb m_regionsm = Somereg → object_regionb m_regionsm′ = Somereg ∨ object_regionb m_regionsm′ = Somer_base ≔ b; r_end ≔ b; r_kind ≔ r_kindreg; r_life ≔ Freed
⊢
cap_access_resc m_regionsm′ a size r align = SomeRTrapOutOfBounds

destruct Hib reg E as reg′ E′

2 open

m, m′ :
c :
Hi :
idsm m′
Hs :
a, size :
Z
align :
Z
H :
cap_access_resc m_regionsm a size r align = SomeRTrapOutOfBounds
Hsz :
0 < size
Hempty :
∀b : Z, b ≤? a && a + size ≤? b = false
b :
Z
reg :
E :
reg′ :
E′ :
object_regionb m_regionsm′ = Somereg′
⊢
object_regionb m_regionsm′ = Somereg ∨ object_regionb m_regionsm′ = Somer_base ≔ b; r_end ≔ b; r_kind ≔ r_kindreg; r_life ≔ Freed
deferred goal
m, m′ :
c :
Hi :
idsm m′
Hs :
a, size :
Z
align :
Z
H :
cap_access_resc m_regionsm a size r align = SomeRTrapOutOfBounds
Hsz :
0 < size
Hempty :
∀b : Z, b ≤? a && a + size ≤? b = false
Hreg :
∀b : Z reg : region, object_regionb m_regionsm = Somereg → object_regionb m_regionsm′ = Somereg ∨ object_regionb m_regionsm′ = Somer_base ≔ b; r_end ≔ b; r_kind ≔ r_kindreg; r_life ≔ Freed
⊢
cap_access_resc m_regionsm′ a size r align = SomeRTrapOutOfBounds

destruct Hsb reg′ E′ as reg0 & E0 & → | _ & → ; rewrite E in E0 ; injection E0 as ← ; auto

deferred goal
m, m′ :
c :
Hi :
idsm m′
Hs :
a, size :
Z
align :
Z
H :
cap_access_resc m_regionsm a size r align = SomeRTrapOutOfBounds
Hsz :
0 < size
Hempty :
∀b : Z, b ≤? a && a + size ≤? b = false
Hreg :
∀b : Z reg : region, object_regionb m_regionsm = Somereg → object_regionb m_regionsm′ = Somereg ∨ object_regionb m_regionsm′ = Somer_base ≔ b; r_end ≔ b; r_kind ≔ r_kindreg; r_life ≔ Freed
⊢
cap_access_resc m_regionsm′ a size r align = SomeRTrapOutOfBounds

destruct c as | b | b | f | n ; cbn [ cap_access_res ] in H |- * ; try exact H ; destruct object_regionb m_regionsm as reg | eqn: E ; | discriminate H ; destruct Hregb reg E as E′ | E′ ; rewrite E' ; exact H | ; cbn [ r_end ] ; rewrite Hempty ; reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros m m′ c Hi Hs H a size r align Hsz
specialize Ha size r align Hsz
assert Hempty : ∀b, b ≤? a && a + size ≤? b = false
{intros b
destruct Z.leb_specb a ; cbn [ andb ] ; apply Z.leb_gt ; lia | reflexivity
assert Hreg : ∀b reg, object_regionb m_regionsm = Somereg → object_regionb m_regionsm′ = Somereg ∨ object_regionb m_regionsm′ = SomemkRegionb b r_kindreg Freed
{intros b reg E
destruct Hib reg E as reg′ E′
destruct Hsb reg′ E′ as reg0 & E0 & → | _ & → ; rewrite E in E0 ; injection E0 as ← ; auto
destruct c as | b | b | f | n ; cbn [ cap_access_res ] in H |- * ; try exact H ; destruct object_regionb m_regionsm as reg | eqn: E ; | discriminate H ; destruct Hregb reg E as E′ | E′ ; rewrite E' ; exact H | ; cbn [ r_end ] ; rewrite Hempty ; reflexivity

A call into owned blocks

Every piece of h but the keys ks agrees with m: a ghost heap whose pieces ks a call may overwrite.

115Definition agrees_exceptks : listpiece m : mem h : gmappiece pval : Prop ≔
∀l v, h !! l = Somev → l ∉ ks → agree_piecem l v

Every address of the spans roots that lies in a live object owning a piece of h is one of the addresses out, which the program hands to the call.

121Definition roots_outroots : listspan h : gmappiece pval m : mem out : Z → Prop : Prop ≔
∀s a, Ins roots → span_containss a → owned_liveh m a → outa

No byte or aux piece of h but the keys ks, of a live object of m and in its bounds, lies at an address out.

126Definition pieces_offks : listpiece h : gmappiece pval m : mem out : Z → Prop : Prop ≔
∀ l v  ,
h !! l = Somev
→
l ∉ ks
→
match l with
PByteb o | PAuxb o
⇒
∀reg, live_atm b reg → 0 ≤ o → b + o < r_endreg → ¬outb + o
_
⇒
True

With nothing out, roots that avoid h's live objects.

134Lemma roots_out_apart
∀ roots h m
roots_apartroots h m
roots_outroots h m λ_ ⇒ False
Explore proof 2 tactics

Initial goal

roots :
listspan
h :
m :
⊢
roots_apartroots h m → roots_outroots h m λ_ : Z ⇒ False

intros Hra s a Hin Hs Ho

roots :
listspan
h :
m :
Hra :
roots_apartroots h m
s :
a :
Z
Hin :
Ins roots
Ho :
⊢
False

exact Hras a Hin Hs Ho

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros Hra s a Hin Hs Ho
exact Hras a Hin Hs Ho

A local effect

One local_effect of a call, from m to m', against the ghost heap h.

140Section Local

The call's sources, roots, releases and born objects, the memories before and after, and the ghost heap.

144Variables sources roots : listspan
144Variables releases born : listZ
144Variables m m' : mem
144Variables h : gmappiece pval

The step is a local_effect.

A live object of m' was live in m with the same region: a local effect only ends objects.

151Lemma local_live_back
∀ b reg
live_atm' b reg
live_atm b reg
Explore proof 3 tactics

Initial goal

sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
⊢
∀b : Z reg : region, live_atm′ b reg → live_atm b reg

intros b reg E L

sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
b :
Z
reg :
E :
object_regionb m_regionsm′ = Somereg
L :
r_lifereg = Live
⊢
live_atm b reg

destruct Hl as _ & Hr & _

sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
b :
Z
reg :
E :
object_regionb m_regionsm′ = Somereg
L :
r_lifereg = Live
Hr :
∀b : Z reg′ : region, object_regionb m_regionsm′ = Somereg′ → ∃reg : region, object_regionb m_regionsm = Somereg ∧ reg′ = reg ∨ Inb releases ++ born ∧ r_kindreg = Heap ∧ r_lifereg = Live ∧ reg′ = r_base ≔ b; r_end ≔ b; r_kind ≔ Heap; r_life ≔ Freed
⊢
live_atm b reg

destruct Hrb reg E as reg0 & E0 & → | _ & _ & _ & → ; split ; assumption | discriminate L

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros b reg E L
destruct Hl as _ & Hr & _
destruct Hrb reg E as reg0 & E0 & → | _ & _ & _ & → ; split ; assumption | discriminate L

A local effect keeps live objects apart.

158Lemma local_live_disjoint
Explore proof 2 tactics

Initial goal

sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′

intros Hd b1 r1 b2 r2 H1 H2

sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
b1 :
Z
r1 :
b2 :
Z
r2 :
H1 :
live_atm′ b1 r1
H2 :
live_atm′ b2 r2
⊢
b1 ≠ b2 → r_endr1 ≤ b2 ∨ r_endr2 ≤ b1

exact Hdb1 r1 b2 r2 local_live_back_ _ H1 local_live_back_ _ H2

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros Hd b1 r1 b2 r2 H1 H2
exact Hdb1 r1 b2 r2 local_live_back_ _ H1 local_live_back_ _ H2

An address of a live owned object of m' was one of m.

164Lemma local_owned_back
Explore proof 5 tactics

Initial goal

sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
⊢
∀a : Z, owned_liveh m′ a → owned_liveh m a

intros a l & v & reg & Hh & Hm & Hlive & Ha

sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
a :
Z
v :
reg :
Hh :
h !! l = Somev
Hlive :
live_atm′ piece_idl reg
Ha :
piece_idl ≤ a < r_endreg
⊢

exists l, v, reg

sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
a :
Z
v :
reg :
Hh :
h !! l = Somev
Hlive :
live_atm′ piece_idl reg
Ha :
piece_idl ≤ a < r_endreg
⊢
h !! l = Somev ∧ mem_piecel ∧ live_atm piece_idl reg ∧ piece_idl ≤ a < r_endreg

split ; exact Hh |

sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
a :
Z
v :
reg :
Hh :
h !! l = Somev
Hlive :
live_atm′ piece_idl reg
Ha :
piece_idl ≤ a < r_endreg
⊢
mem_piecel ∧ live_atm piece_idl reg ∧ piece_idl ≤ a < r_endreg

split ; exact Hm |

sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
a :
Z
v :
reg :
Hh :
h !! l = Somev
Hlive :
live_atm′ piece_idl reg
Ha :
piece_idl ≤ a < r_endreg
⊢
live_atm piece_idl reg ∧ piece_idl ≤ a < r_endreg

split ; exact local_live_back_ _ Hlive | exact Ha

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros a l & v & reg & Hh & Hm & Hlive & Ha
exists l, v, reg
split ; exact Hh |
split ; exact Hm |
split ; exact local_live_back_ _ Hlive | exact Ha

A local effect keeps every piece of h but the keys ks agreeing, where every root address in an object the program owns is out, no piece of h but ks lies at an address out, and the effect releases none of h's identities and was born with none of them. The program hands the call the pieces ks, at the addresses out.

175Lemma local_agrees_out
Proof 55 steps Qed
intros Hd Ha Hra Hoff Hrel Hb l v Hh Hk
pose proof Hal v Hh Hk as Hp
pose proof Hoffl v Hh Hk as Hno
pose proof local_effect_kept_ _ _ _ _ _ Hl as Hs _
pose proof Hl as Hi & Hr & Hw & _

An address of a live object of m owning a piece of h, not out, keeps its byte and aux slot.

assert Hkeep : ∀reg o, mem_piecel → live_atm piece_idl reg → 0 ≤ o → piece_idl + o < r_endreg → ¬outpiece_idl + o → m_bytesm' piece_idl + o = m_bytesm piece_idl + o ∧ m_auxm' piece_idl + o = m_auxm piece_idl + o
{intros reg o Hm Hlive Ho He Hout
apply Hw
assert Hown : owned_liveh m piece_idl + o
{exists l, v, reg
split ; exact Hh |
split ; exact Hm |
split ; exact Hlive | lia
intros s & Hin & _ & Hsp | Hborn
–exact HoutHras _ Hin Hsp Hown
–exact owned_not_authority[ ] born h m _ Hd λs a Hin ⇒ match Hin with end Hb Hown or_introrHborn
destruct l as b | b o | b o | k , v as reg | x | c | | q t | cd | sq sp | ga gi | op ; cbn [ agree_piece piece_id ] in Hp , Hkeep , Hno |- * ; try contradiction ; try exact I
–destruct Hp as E L
destruct Hib reg E as reg′ E′
destruct Hrb reg' E' as reg0 & E0 & → | Hin & _ ; rewrite E in E0 ; injection E0 as ←
+split ; assumption
+exfalso
apply in_app_or in Hin as Hin | Hin ; exact Hrelb PLiveb VLivereg Hin Hh I eq_refl | exact Hbb PLiveb VLivereg Hin Hh I eq_refl
–unfold registered in *
destruct object_regionb m_regionsm as reg | eqn: E ; | contradiction
destruct Hib reg E as reg′ →
discriminate
–destruct Hp as Hreg Hin
split
+unfold registered in *
destruct object_regionb m_regionsm as reg | eqn: E ; | contradiction
destruct Hib reg E as reg′ →
discriminate
+intros reg′ E′ L′
destruct local_live_backb reg' conjE' L' as E L
destruct Hinreg' E L as Ho & He & Hx
split ; exact Ho |
split ; exact He |
rewrite proj1Hkeepreg' o I conjE L Ho He Hnoreg' conjE L Ho He
exact Hx
–destruct Hp as Hreg Hin
split
+unfold registered in *
destruct object_regionb m_regionsm as reg | eqn: E ; | contradiction
destruct Hib reg E as reg′ →
discriminate
+intros reg′ E′ L′
destruct local_live_backb reg' conjE' L' as E L
destruct Hinreg' E L as Ho & He & Hx
split ; exact Ho |
split ; exact He |
unfold aux_holds in *
rewrite proj2Hkeepreg' o I conjE L Ho He Hnoreg' conjE L Ho He
destruct Hx as Hx | Hf Ht ; left ; exact Hx | right
split ; exact freed_in_stepm m' _ Hi Hs Hf | exact traps_as_freed_stepm m' _ Hi Hs Ht

A local effect whose roots are apart from h, that releases none of h's identities and was born with none of them, keeps h agreeing.

Explore proof 6 tactics

Initial goal

sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
⊢
live_disjointm → agreesm h → roots_apartroots h m → ids_apartreleases h → ids_apartborn h → agreesm′ h

intros Hd Ha Hra Hrel Hb l v Hh

sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
Ha :
Hra :
roots_apartroots h m
Hrel :
ids_apartreleases h
Hb :
ids_apartborn h
v :
Hh :
h !! l = Somev
⊢
agree_piecem′ l v

apply local_agrees_out[ ] λ_ ⇒ False Hd ; | exact roots_out_apart_ _ _ Hra | | exact Hrel | exact Hb | exact Hh | apply not_elem_of_nil

2 open

sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
Ha :
Hra :
roots_apartroots h m
Hrel :
ids_apartreleases h
Hb :
ids_apartborn h
v :
Hh :
h !! l = Somev
⊢
focused goal
sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
Ha :
Hra :
roots_apartroots h m
Hrel :
ids_apartreleases h
Hb :
ids_apartborn h
v :
Hh :
h !! l = Somev
⊢
pieces_off[ ] h m λ_ : Z ⇒ False

–intros l′ v′ Hl′ _

2 open

sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
Ha :
Hra :
roots_apartroots h m
Hrel :
ids_apartreleases h
Hb :
ids_apartborn h
v :
Hh :
h !! l = Somev
l′ :
v′ :
Hl′ :
h !! l′ = Somev′
⊢
agree_piecem l′ v′
deferred goal
sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
Ha :
Hra :
roots_apartroots h m
Hrel :
ids_apartreleases h
Hb :
ids_apartborn h
v :
Hh :
h !! l = Somev
⊢
pieces_off[ ] h m λ_ : Z ⇒ False

exact Hal′ v′ Hl′

deferred goal
sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
Ha :
Hra :
roots_apartroots h m
Hrel :
ids_apartreleases h
Hb :
ids_apartborn h
v :
Hh :
h !! l = Somev
⊢
pieces_off[ ] h m λ_ : Z ⇒ False

–intros l′ v′ _ _

sources, roots :
listspan
releases, born :
listZ
m, m′ :
h :
Hl :
local_effectsources roots releases born m m′
Ha :
Hra :
roots_apartroots h m
Hrel :
ids_apartreleases h
Hb :
ids_apartborn h
v :
Hh :
h !! l = Somev
l′ :
v′ :
⊢
match l′ with
PByteb o | PAuxb o
⇒
∀reg : region, live_atm b reg → 0 ≤ o → b + o < r_endreg → ¬False
_
⇒
True

destruct l′ ; auto

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros Hd Ha Hra Hrel Hb l v Hh
apply local_agrees_out[ ] λ_ ⇒ False Hd ; | exact roots_out_apart_ _ _ Hra | | exact Hrel | exact Hb | exact Hh | apply not_elem_of_nil
–intros l′ v′ Hl′ _
exact Hal′ v′ Hl′
–intros l′ v′ _ _
destruct l′ ; auto

An allocation

A live object of m after an allocation at a new base, other than the new object, was live in m with the same region.

242Lemma allocated_live_back
∀ m q base b reg
base ≠ b
live_atallocatedm q base b reg
live_atm b reg
Explore proof 3 tactics

Initial goal

⊢
∀m : mem q : alloc_req base b : Z reg : region, base ≠ b → live_atallocatedm q base b reg → live_atm b reg

intros m q base b reg Hne E L

m :
base, b :
Z
reg :
Hne :
base ≠ b
E :
object_regionb m_regionsallocatedm q base = Somereg
L :
r_lifereg = Live
⊢
live_atm b reg

rewrite object_region_allocated in E

m :
base, b :
Z
reg :
Hne :
base ≠ b
L :
r_lifereg = Live
E :
base =? b
→
Somer_base ≔ base; r_end ≔ base + req_extentq; r_kind ≔ req_kindq; r_life ≔ Live
=
Somereg
⊢
live_atm b reg

destruct Z.eqb_specbase b as [ <-| _ ] ; contradiction | split ; assumption

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros m q base b reg Hne E L
destruct Z.eqb_specbase b as [ <-| _ ] ; contradiction | split ; assumption

An address of a live owned object after an allocation at a base that is no object of m was one of m: owned objects are registered.

251Lemma allocated_owned_back
∀ m q base h a
Explore proof 10 tactics

Initial goal

⊢
∀m : mem q : alloc_req base : Z h : gmappiece pval a : Z, object_regionbase m_regionsm = None → agreesm h → owned_liveh allocatedm q base a → owned_liveh m a

intros m q base h a Hn Ha l & v & reg & Hh & Hm & Hlive & Hr

m :
base :
Z
h :
a :
Z
Hn :
Ha :
v :
reg :
Hh :
h !! l = Somev
Hlive :
Hr :
piece_idl ≤ a < r_endreg
⊢

exists l, v, reg

m :
base :
Z
h :
a :
Z
Hn :
Ha :
v :
reg :
Hh :
h !! l = Somev
Hlive :
Hr :
piece_idl ≤ a < r_endreg
⊢
h !! l = Somev ∧ mem_piecel ∧ live_atm piece_idl reg ∧ piece_idl ≤ a < r_endreg

split ; exact Hh |

m :
base :
Z
h :
a :
Z
Hn :
Ha :
v :
reg :
Hh :
h !! l = Somev
Hlive :
Hr :
piece_idl ≤ a < r_endreg
⊢
mem_piecel ∧ live_atm piece_idl reg ∧ piece_idl ≤ a < r_endreg

split ; exact Hm |

m :
base :
Z
h :
a :
Z
Hn :
Ha :
v :
reg :
Hh :
h !! l = Somev
Hlive :
Hr :
piece_idl ≤ a < r_endreg
⊢
live_atm piece_idl reg ∧ piece_idl ≤ a < r_endreg

split ; | exact Hr

m :
base :
Z
h :
a :
Z
Hn :
Ha :
v :
reg :
Hh :
h !! l = Somev
Hlive :
Hr :
piece_idl ≤ a < r_endreg
⊢

apply allocated_live_backm q base ; | exact Hlive

m :
base :
Z
h :
a :
Z
Hn :
Ha :
v :
reg :
Hh :
h !! l = Somev
Hlive :
Hr :
piece_idl ≤ a < r_endreg
⊢
base ≠ piece_idl

intros E

m :
base :
Z
h :
a :
Z
Hn :
Ha :
v :
reg :
Hh :
h !! l = Somev
Hlive :
Hr :
piece_idl ≤ a < r_endreg
E :
base = piece_idl
⊢
False

apply agree_piece_registeredm l v Hm Hal v Hh

m :
base :
Z
h :
a :
Z
Hn :
Ha :
v :
reg :
Hh :
h !! l = Somev
Hlive :
Hr :
piece_idl ≤ a < r_endreg
E :
base = piece_idl

rewrite <- E

m :
base :
Z
h :
a :
Z
Hn :
Ha :
v :
reg :
Hh :
h !! l = Somev
Hlive :
Hr :
piece_idl ≤ a < r_endreg
E :
base = piece_idl
⊢

exact Hn

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros m q base h a Hn Ha l & v & reg & Hh & Hm & Hlive & Hr
exists l, v, reg
split ; exact Hh |
split ; exact Hm |
split ; | exact Hr
apply allocated_live_backm q base ; | exact Hlive
intros E
apply agree_piece_registeredm l v Hm Hal v Hh
rewrite <- E
exact Hn

A base that is no object of m is none of the identities of a ghost heap that agrees with m.

262Lemma unregistered_apart
∀ m h base bs
ids_apartbase :: bs h
Explore proof 6 tactics

Initial goal

⊢
∀m : mem h : gmappiece pval base : Z bs : listZ, object_regionbase m_regionsm = None → agreesm h → ids_apartbs h → ids_apartbase :: bs h

intros m h base bs Hn Ha Hb b l v [ <-| Hin ] Hh Hm

2 open

m :
h :
base :
Z
bs :
listZ
Hn :
Ha :
Hb :
v :
Hh :
h !! l = Somev
⊢
piece_idl ≠ base
focused goal
m :
h :
base :
Z
bs :
listZ
Hn :
Ha :
Hb :
b :
Z
v :
Hin :
Inb bs
Hh :
h !! l = Somev
⊢
piece_idl ≠ b

–intros E

2 open

m :
h :
base :
Z
bs :
listZ
Hn :
Ha :
Hb :
v :
Hh :
h !! l = Somev
E :
piece_idl = base
⊢
False
deferred goal
m :
h :
base :
Z
bs :
listZ
Hn :
Ha :
Hb :
b :
Z
v :
Hin :
Inb bs
Hh :
h !! l = Somev
⊢
piece_idl ≠ b

apply agree_piece_registeredm l v Hm Hal v Hh

2 open

m :
h :
base :
Z
bs :
listZ
Hn :
Ha :
Hb :
v :
Hh :
h !! l = Somev
E :
piece_idl = base
deferred goal
m :
h :
base :
Z
bs :
listZ
Hn :
Ha :
Hb :
b :
Z
v :
Hin :
Inb bs
Hh :
h !! l = Somev
⊢
piece_idl ≠ b

rewrite E

2 open

m :
h :
base :
Z
bs :
listZ
Hn :
Ha :
Hb :
v :
Hh :
h !! l = Somev
E :
piece_idl = base
⊢
deferred goal
m :
h :
base :
Z
bs :
listZ
Hn :
Ha :
Hb :
b :
Z
v :
Hin :
Inb bs
Hh :
h !! l = Somev
⊢
piece_idl ≠ b

exact Hn

deferred goal
m :
h :
base :
Z
bs :
listZ
Hn :
Ha :
Hb :
b :
Z
v :
Hin :
Inb bs
Hh :
h !! l = Somev
⊢
piece_idl ≠ b

–exact Hbb l v Hin Hh Hm

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros m h base bs Hn Ha Hb b l v [ <-| Hin ] Hh Hm
–intros E
apply agree_piece_registeredm l v Hm Hal v Hh
rewrite E
exact Hn
–exact Hbb l v Hin Hh Hm

Delegated roots

A world's new roots, delegated in m from the old roots and the born objects (stdio_delegates), avoid h's live objects when the old roots do and the born objects are none of h's: every address of a new root is one the call has write_authority over.

276Lemma delegates_apart
∀ roots born m w h
Explore proof 3 tactics

Initial goal

⊢
∀roots : listspan born : listZ m : mem w : stdio_world h : gmappiece pval, stdio_delegatesroots born m w → roots_apartroots h m → ids_apartborn h → live_disjointm → roots_apartstdio_rootsw h m

intros roots born m w h Hdel Hra Hb Hd s a Hin Hs Ho

roots :
listspan
born :
listZ
m :
h :
Hdel :
stdio_delegatesroots born m w
Hra :
roots_apartroots h m
Hb :
ids_apartborn h
s :
a :
Z
Hin :
Ho :
⊢
False

destruct Hdels Hin as _ Hw

roots :
listspan
born :
listZ
m :
h :
Hdel :
stdio_delegatesroots born m w
Hra :
roots_apartroots h m
Hb :
ids_apartborn h
s :
a :
Z
Hin :
Ho :
Hw :
∀a : Z, span_containss a → write_authorityroots born m a
⊢
False

exact owned_not_authorityroots born h m a Hd Hra Hb Ho Hwa Hs

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros roots born m w h Hdel Hra Hb Hd s a Hin Hs Ho
destruct Hdels Hin as _ Hw
exact owned_not_authorityroots born h m a Hd Hra Hb Ho Hwa Hs