Library mcertikos.mm.PTIntroGenPassthrough
This file provide the contextual refinement proof between MAL layer and MPTIntro layer
Require Export PTIntroGenDef.
Require Import PTIntroGenAccessor0.
Require Import PTIntroGenAccessor.
Require Import PTIntroGenAccessor0.
Require Import PTIntroGenAccessor.
Section Refinement.
Context `{real_params: RealParams}.
Context `{multi_oracle_prop: MultiOracleProp}.
Section WITHMEM.
Context `{Hstencil: Stencil}.
Context `{Hmem: Mem.MemoryModelX}.
Context `{Hmwd: UseMemWithData mem}.
Context `{real_params: RealParams}.
Context `{multi_oracle_prop: MultiOracleProp}.
Section WITHMEM.
Context `{Hstencil: Stencil}.
Context `{Hmem: Mem.MemoryModelX}.
Context `{Hmwd: UseMemWithData mem}.
Section Exists.
Lemma meminit_exist:
∀ habd habd´ labd i f,
mem_init0_spec i habd = Some habd´
→ relate_RData f habd labd
→ ∃ labd´, lmem_init_spec i labd = Some labd´ ∧ relate_RData f habd´ labd´
∧ PT habd´ = PT habd
∧ ptpool habd´ = ptpool habd
∧ CR3 labd´ = CR3 labd
∧ pperm habd´ = pperm habd
∧ idpde habd´ = idpde habd.
Proof.
unfold lmem_init_spec, mem_init0_spec; intros until f; exist_simpl.
Qed.
Lemma trapout_exist:
∀ habd habd´ labd f,
trapout_spec habd = Some habd´
→ relate_RData f habd labd
→ ∃ labd´, trapout0_spec labd = Some labd´ ∧ relate_RData f habd´ labd´
∧ PT habd´ = PT habd
∧ ptpool habd´ = ptpool habd
∧ CR3 labd´ = CR3 labd
∧ pperm habd´ = pperm habd
∧ idpde habd´ = idpde habd.
Proof.
unfold trapout_spec, trapout0_spec; intros until f; exist_simpl.
Qed.
Lemma setPG_exist:
∀ habd habd´ labd f,
setPG1_spec habd = Some habd´
→ high_level_invariant habd
→ relate_RData f habd labd
→ ∃ labd´, setPG0_spec labd = Some labd´ ∧ relate_RData f habd´ labd´
∧ PT habd´ = PT habd
∧ ptpool habd´ = ptpool habd
∧ CR3 labd´ = CR3 labd
∧ pperm habd´ = pperm habd
∧ idpde habd´ = idpde habd.
Proof.
unfold setPG0_spec, setPG1_spec; intros until f.
intros HP HINV HR; pose proof HR as HR´; inv HR; revert HP;
subrewrite´; intros HQ; inv HINV. subdestruct.
pose proof relate_PT_re as HPT.
inv HPT. omega.
destruct (CR3_valid_dec (GLOBP PTPool_LOC ofs)).
+ inv HQ; refine_split´; eauto 1.
inv HR´; constructor; trivial.
+ elim n. unfold CR3_valid; eauto.
Qed.
Lemma match_PMapPool_Hide:
∀ s p p´ ptp m f,
(∀ i v1 v2, ZMap.get i p = PGHide (PGPMap v1 v2) → ZMap.get i p´ = PGHide (PGPMap v1 v2)) →
match_PMapPool s ptp p m f →
match_PMapPool s ptp p´ m f.
Proof.
intros. inv H0. econstructor; eauto.
intros. specialize (H1 _ H0). inv H1.
constructor. intros. specialize (H3 _ H1).
destruct H3 as (v & HLD & HV & HM).
refine_split´; eauto.
inv HM; econstructor; eauto 2.
Qed.
Require Import INVLemmaMemory.
Lemma lpalloc_exist:
∀ habd habd´ labd i n s f,
lpalloc_spec n habd = Some (habd´, i)
→ relate_AbData s f habd labd
→ high_level_invariant habd
→ ∃ labd´, lpalloc_spec n labd = Some (labd´, i) ∧ relate_AbData s f habd´ labd´
∧ PT habd´ = PT habd
∧ ptpool habd´ = ptpool habd
∧ CR3 labd´ = CR3 labd
∧ idpde habd´ = idpde habd
∧ (∀ i o, ZMap.get i (pperm habd) = PGHide o →
ZMap.get i (pperm habd´) = PGHide o).
Proof.
unfold lpalloc_spec in *; intros.
revert H. pose proof H0 as HR.
inv H0. subrewrite. simpl.
subdestruct; inv HQ; simpl.
- refine_split´; eauto.
+ inv HR. constructor; trivial; simpl.
intros i´. destruct (zeq i i´); subst.
× repeat rewrite ZMap.gss. constructor.
× repeat rewrite ZMap.gso; eauto.
+ simpl. intros.
destruct (zeq i0 i); subst.
× specialize (valid_pperm_ppage _ H1). intro Hperm.
assert (Hcon: consistent_ppage_log
(ZMap.set lock_AT_start (MultiDef (ZMap.get 0 (multi_oracle habd) (CPU_ID habd) l ++ l))
(multi_log habd)) (pperm habd) (nps habd)).
{
eapply consistent_ppage_log_gss; eauto.
rewrite multi_log_re. trivial.
}
unfold consistent_ppage_log in Hcon.
rewrite ZMap.gss in Hcon.
rewrite <- multi_oracle_re, <- CPU_ID_re in Hdestruct6.
specialize (Hcon _ _ refl_equal Hdestruct6).
unfold weak_consistent_ppage in Hcon.
specialize (Hcon i).
exploit Hcon; eauto.
{ omega. }
{ rewrite H. congruence. }
{
intros HF. destruct a0 as (? & HTrue & ?).
congruence.
}
× rewrite ZMap.gso; auto.
- refine_split´; eauto.
+ inv HR. constructor; trivial; simpl.
- refine_split´; eauto.
+ inv HR. constructor; trivial; simpl.
Qed.
Lemma PageI_4:
∀ i ofs,
i × 4 ≤ ofs < i × 4 + size_chunk Mint32 →
PageI ofs = PageI (i × 4).
Proof.
simpl; intros.
assert (HP: ∃ a, ofs = i × 4 + a
∧ 0≤ a ≤ 3).
{
∃ (ofs - i × 4). split; omega.
}
destruct HP as (a & Heq & Hrange). clear H.
rewrite Heq. unfold PageI. clear Heq.
assert (HP: ∃ b c, i = 1024 × b + c
∧ 0≤ c < 1024).
{
∃ (i/1024), (i mod 1024). split.
apply Z_div_mod_eq. omega.
apply Z_mod_lt. omega.
}
destruct HP as (b & c & Heq & Hrange´).
rewrite Heq. clear Heq.
replace ((1024 × b + c) × 4) with (b × 4096 + c × 4) by omega.
replace (b × 4096 + c × 4 + a) with (b × 4096 + (c × 4 + a)) by omega.
assert (HT: 4096 ≠ 0) by omega.
repeat rewrite Z_div_plus_full_l; try assumption.
clear HT.
repeat rewrite Zdiv_small. reflexivity.
omega. omega.
Qed.
Lemma fload_exist:
∀ habd labd i z f,
fload_spec i habd = Some z
→ relate_RData f habd labd
→ fload´_spec i labd = Some z.
Proof.
unfold fload_spec, fload´_spec; intros.
revert H. inv H0. subrewrite.
assert (HG: ∀ ofs´,
i × 4 ≤ ofs´ < i × 4 + size_chunk Mint32 →
∀ o, ZMap.get (PageI ofs´) (pperm habd) ≠ PGHide o).
{
intros. erewrite PageI_4; eauto 1.
subdestruct.
}
specialize (FlatMem.load_inj _ _ Mint32 (i × 4) _ f flatmem_re refl_equal).
subdestruct. intros (v2 & HLD & HVAL).
rewrite HLD. inv HVAL. assumption.
Qed.
Lemma page_copy_exist:
∀ s habd habd´ labd index i from f,
page_copy_spec index i from habd = Some habd´
→ relate_AbData s f habd labd
→ ∃ labd´, page_copy0_spec index i from labd = Some labd´
∧ relate_AbData s f habd´ labd´
∧ PT habd´ = PT habd
∧ ptpool habd´ = ptpool habd
∧ CR3 labd´ = CR3 labd
∧ pperm habd´ = pperm habd
∧ idpde habd´ = idpde habd.
Proof.
unfold page_copy0_spec, page_copy_spec; intros.
inversion H0.
revert H. subrewrite.
subdestruct. inv HQ.
assert (HW: ZMap.get (PageI from) (pperm labd) = PGAlloc).
{
specialize (pperm_re (PageI from)).
rewrite Hdestruct6 in pperm_re.
inv pperm_re; reflexivity.
}
rewrite HW.
exploit page_copy_aux_exists; eauto.
intros.
rewrite H.
rewrite Hdestruct11.
refine_split´; try trivial.
econstructor; simpl; auto.
rewrite ikern_re; auto.
rewrite ihost_re; auto.
Qed.
Lemma page_copy_back_aux_load_other_plus:
∀ n h h´ pp to buff vadr o,
ZMap.get (PageI to) pp = PGAlloc →
ZMap.get (PageI vadr) pp = PGHide o →
(4 | to) →
PageI to = PageI (to + (Z.of_nat (n + 1)) × 4 - 4) →
PageI (vadr) = PageI (vadr + 3) →
(4 | vadr) →
page_copy_back_aux (n + 1) to buff h = Some h´ →
FlatMem.load Mint32 h vadr = FlatMem.load Mint32 h´ vadr.
Proof.
intros until n.
induction n.
- simpl; intros.
subdestruct. inv H5.
erewrite (FlatMem.load_store_other Mint32 h (FlatMem.store Mint32 h to (Vint i))); eauto 2.
simpl.
assert (¬ ( vadr - 4 < to < vadr + 4)).
{
red; intros.
assert (vadr ≤ to).
{
destruct H1 as (m & He).
destruct H4 as (m´ & He´).
subst.
destruct (zle (m´ -1) m).
- omega.
- omega.
}
assert (vadr ≤ to ≤ vadr + 3) by omega.
exploit PageI_range; eauto.
intros.
assert (vadr ≤ vadr ≤ vadr + 3) by omega.
exploit PageI_range; eauto.
intros. congruence.
}
omega.
- simpl; intros. subdestruct.
exploit (IHn (FlatMem.store Mint32 h to (Vint i))); try eapply H5; try eassumption.
+ erewrite PageI_range; eauto.
eapply to_range.
+ apply to_add_divide; eauto.
+ eapply PageI_eq; eauto.
+ intros. erewrite <- H6.
erewrite (FlatMem.load_store_other Mint32 h (FlatMem.store Mint32 h to (Vint i))); eauto 2.
simpl.
assert (¬ ( vadr - 4 < to < vadr + 4)).
{
red; intros.
assert (vadr ≤ to).
{
destruct H1 as (m & He).
destruct H4 as (m´ & He´).
subst.
destruct (zle (m´ -1) m).
- omega.
- omega.
}
assert (vadr ≤ to ≤ vadr + 3) by omega.
exploit PageI_range; eauto.
intros.
assert (vadr ≤ vadr ≤ vadr + 3) by omega.
exploit PageI_range; eauto.
intros. congruence.
}
omega.
Qed.
Lemma page_copy_back_aux_load_other´:
∀ n h h´ pp to buff o vadr,
ZMap.get (PageI to) pp = PGAlloc →
ZMap.get (PageI vadr) pp = PGHide o →
(PgSize | to) →
Z.of_nat n ≤ one_k →
PageI (vadr) = PageI (vadr + 3) →
(4 | vadr) →
page_copy_back_aux n to buff h = Some h´ →
FlatMem.load Mint32 h vadr = FlatMem.load Mint32 h´ vadr.
Proof.
destruct n; intros.
- simpl in ×. inv H5. trivial.
- replace (S n) with ((n + 1)%nat) in × by omega.
eapply page_copy_back_aux_load_other_plus; eauto.
+ destruct H1 as (i & He).
∃ (i × 1024).
subst. omega.
+ eapply PageI_divide; eauto.
Qed.
Lemma page_copy_back_aux_load_other:
∀ vadr n h h´ pp to buff o,
page_copy_back_aux (Z.to_nat n) to buff h = Some h´ →
ZMap.get (PageI vadr) pp = PGHide o →
ZMap.get (PageI to) pp = PGAlloc →
(PgSize | to) →
0 ≤ n ≤ one_k →
PageI (vadr) = PageI (vadr + 3) →
(4 | vadr) →
FlatMem.load Mint32 h vadr = FlatMem.load Mint32 h´ vadr.
Proof.
intros.
eapply page_copy_back_aux_load_other´; eauto.
rewrite Z2Nat.id; try omega.
Qed.
Lemma page_copy_back_exist:
∀ s habd habd´ labd index i from m f,
page_copy_back_spec index i from habd = Some habd´
→ relate_AbData s f habd labd
→ match_RData s habd m f
→ ∃ labd´, page_copy_back0_spec index i from labd = Some labd´
∧ relate_AbData s f habd´ labd´
∧ PT habd´ = PT habd
∧ ptpool habd´ = ptpool habd
∧ CR3 labd´ = CR3 labd
∧ pperm habd´ = pperm habd
∧ idpde habd´ = idpde habd.
Proof.
unfold page_copy_back0_spec, page_copy_back_spec; intros.
inversion H0.
revert H. subrewrite.
subdestruct. inv HQ.
assert (HW: ZMap.get (PageI from) (pperm labd) = PGAlloc).
{
specialize (pperm_re (PageI from)).
rewrite Hdestruct6 in pperm_re.
inv pperm_re; reflexivity.
}
rewrite HW.
exploit page_copy_back_aux_exists; eauto.
intros.
destruct H as (lh´ & H & Hrel).
rewrite H.
refine_split´; try trivial.
econstructor; simpl; auto.
rewrite ikern_re; auto.
rewrite ihost_re; auto.
-
constructor; intros. inv relate_PMap_re.
specialize (H6 _ H2 _ H3 _ _ H4 _ H5).
inv H1. inv H7. specialize (H1 _ H2).
inv H1. specialize (H7 _ H3).
destruct H7 as (v0 & _ & _ & HMAT).
unfold PMap, ZMap.t, PMap.t in H4, HMAT. rewrite H4 in HMAT.
inv HMAT.
assert (HPA: PageI (pi × 4096 + vadr × 4) = pi).
{
revert H5. clear; intros.
unfold PageI.
rewrite Z_div_plus_full_l; [| omega].
rewrite (Zdiv_small (vadr × 4) PgSize); rewrite_omega.
}
clear HW.
exploit (page_copy_back_aux_load_other (pi × 4096 + vadr × 4)); eauto.
+ rewrite HPA. eassumption.
+ revert H5. clear; intros.
unfold PageI.
replace (pi × 4096 + vadr × 4 + 3)
with (pi × 4096 + (vadr × 4 + 3)) by omega.
repeat (rewrite Z_div_plus_full_l; [| omega]).
rewrite (Zdiv_small (vadr × 4) PgSize); rewrite_omega.
rewrite (Zdiv_small (vadr × 4 + 3) PgSize); rewrite_omega.
+ ∃ (pi × 1024 + vadr); omega.
+ intros.
rewrite <- H1. eauto.
Qed.
End Exists.
Ltac pattern2_refinement_simpl:=
pattern2_refinement_simpl´ (@relate_AbData).
Lemma passthrough_correct:
sim (crel HDATA LDATA) mptintro_passthrough malh.
Proof.
sim_oplus.
-
layer_sim_simpl; compatsim_simpl (@match_AbData); intros.
match_external_states_simpl.
erewrite fload_exist; eauto 1. reflexivity.
-
layer_sim_simpl; compatsim_simpl (@match_AbData); intros.
exploit fstore_exist; eauto 1. intros (labd´ & HP & HM & HN1 & HN2 & HN3 & HN4 & HN5).
match_external_states_simpl.
- layer_sim_simpl; compatsim_simpl (@match_AbData); intros.
exploit page_copy_exist; eauto 1.
intros (labd´ & HP & HM & HN1 & HN2 & HN3 & HN4 & HN5).
match_external_states_simpl.
- layer_sim_simpl; compatsim_simpl (@match_AbData); intros.
exploit page_copy_back_exist; eauto 1.
intros (labd´ & HP & HM & HN1 & HN2 & HN3 & HN4 & HN5).
match_external_states_simpl.
- apply vmxinfo_get_sim.
-
layer_sim_simpl; compatsim_simpl (@match_AbData); intros.
exploit setPG_exist; eauto 1; intros (labd´ & HP & HM & HN1 & HN2 & HN3 & HN4 & HN5).
match_external_states_simpl.
- apply get_at_c_sim.
- apply set_at_c0_sim.
-
layer_sim_simpl; compatsim_simpl (@match_AbData); intros.
exploit lpalloc_exist; eauto 1. intros (labd´ & HP & HM & HN1 & HN2 & HN3 & HN4 & HN5).
refine_split; try econstructor; eauto. econstructor; eauto.
constructor; eauto.
constructor; subrewrite´.
eapply match_PMapPool_Hide; try eassumption.
intros; eapply HN5. assumption.
-
layer_sim_simpl; compatsim_simpl (@match_AbData); intros.
exploit meminit_exist; eauto 1; intros (labd´ & HP & HM & HN1 & HN2 & HN3 & HN4 & HN5).
match_external_states_simpl.
- apply container_get_parent_sim.
- apply container_get_nchildren_sim.
- apply container_get_quota_sim.
- apply container_get_usage_sim.
- apply container_can_consume_sim.
- apply container_split_sim.
- apply get_CPU_ID_sim.
- apply get_curid_sim.
- apply set_curid_sim.
- apply set_curid_init_sim.
- apply (release_lock_sim (valid_arg_imply:= Shared2ID1_imply)).
-
eapply acquire_lock_sim1; eauto.
intros. inv H; trivial. inv H0; trivial. inv H.
- apply cli_sim.
- apply sti_sim.
- apply serial_intr_disable_sim.
- apply serial_intr_enable_sim.
- apply serial_putc_sim.
- apply cons_buf_read_sim.
- apply trapin_sim.
-
layer_sim_simpl; compatsim_simpl (@match_AbData); intros.
inv match_extcall_states.
exploit trapout_exist; eauto 1; intros (labd´ & HP & HM & HN1 & HN2 & HN3 & HN4 & HN5).
inv match_match. match_external_states_simpl.
- apply hostin_sim.
- apply hostout_sim.
- apply proc_create_postinit_sim.
- apply trap_info_get_sim.
- apply trap_info_ret_sim.
- layer_sim_simpl.
+ eapply load_correct.
+ eapply store_correct.
Qed.
End WITHMEM.
End Refinement.
Lemma meminit_exist:
∀ habd habd´ labd i f,
mem_init0_spec i habd = Some habd´
→ relate_RData f habd labd
→ ∃ labd´, lmem_init_spec i labd = Some labd´ ∧ relate_RData f habd´ labd´
∧ PT habd´ = PT habd
∧ ptpool habd´ = ptpool habd
∧ CR3 labd´ = CR3 labd
∧ pperm habd´ = pperm habd
∧ idpde habd´ = idpde habd.
Proof.
unfold lmem_init_spec, mem_init0_spec; intros until f; exist_simpl.
Qed.
Lemma trapout_exist:
∀ habd habd´ labd f,
trapout_spec habd = Some habd´
→ relate_RData f habd labd
→ ∃ labd´, trapout0_spec labd = Some labd´ ∧ relate_RData f habd´ labd´
∧ PT habd´ = PT habd
∧ ptpool habd´ = ptpool habd
∧ CR3 labd´ = CR3 labd
∧ pperm habd´ = pperm habd
∧ idpde habd´ = idpde habd.
Proof.
unfold trapout_spec, trapout0_spec; intros until f; exist_simpl.
Qed.
Lemma setPG_exist:
∀ habd habd´ labd f,
setPG1_spec habd = Some habd´
→ high_level_invariant habd
→ relate_RData f habd labd
→ ∃ labd´, setPG0_spec labd = Some labd´ ∧ relate_RData f habd´ labd´
∧ PT habd´ = PT habd
∧ ptpool habd´ = ptpool habd
∧ CR3 labd´ = CR3 labd
∧ pperm habd´ = pperm habd
∧ idpde habd´ = idpde habd.
Proof.
unfold setPG0_spec, setPG1_spec; intros until f.
intros HP HINV HR; pose proof HR as HR´; inv HR; revert HP;
subrewrite´; intros HQ; inv HINV. subdestruct.
pose proof relate_PT_re as HPT.
inv HPT. omega.
destruct (CR3_valid_dec (GLOBP PTPool_LOC ofs)).
+ inv HQ; refine_split´; eauto 1.
inv HR´; constructor; trivial.
+ elim n. unfold CR3_valid; eauto.
Qed.
Lemma match_PMapPool_Hide:
∀ s p p´ ptp m f,
(∀ i v1 v2, ZMap.get i p = PGHide (PGPMap v1 v2) → ZMap.get i p´ = PGHide (PGPMap v1 v2)) →
match_PMapPool s ptp p m f →
match_PMapPool s ptp p´ m f.
Proof.
intros. inv H0. econstructor; eauto.
intros. specialize (H1 _ H0). inv H1.
constructor. intros. specialize (H3 _ H1).
destruct H3 as (v & HLD & HV & HM).
refine_split´; eauto.
inv HM; econstructor; eauto 2.
Qed.
Require Import INVLemmaMemory.
Lemma lpalloc_exist:
∀ habd habd´ labd i n s f,
lpalloc_spec n habd = Some (habd´, i)
→ relate_AbData s f habd labd
→ high_level_invariant habd
→ ∃ labd´, lpalloc_spec n labd = Some (labd´, i) ∧ relate_AbData s f habd´ labd´
∧ PT habd´ = PT habd
∧ ptpool habd´ = ptpool habd
∧ CR3 labd´ = CR3 labd
∧ idpde habd´ = idpde habd
∧ (∀ i o, ZMap.get i (pperm habd) = PGHide o →
ZMap.get i (pperm habd´) = PGHide o).
Proof.
unfold lpalloc_spec in *; intros.
revert H. pose proof H0 as HR.
inv H0. subrewrite. simpl.
subdestruct; inv HQ; simpl.
- refine_split´; eauto.
+ inv HR. constructor; trivial; simpl.
intros i´. destruct (zeq i i´); subst.
× repeat rewrite ZMap.gss. constructor.
× repeat rewrite ZMap.gso; eauto.
+ simpl. intros.
destruct (zeq i0 i); subst.
× specialize (valid_pperm_ppage _ H1). intro Hperm.
assert (Hcon: consistent_ppage_log
(ZMap.set lock_AT_start (MultiDef (ZMap.get 0 (multi_oracle habd) (CPU_ID habd) l ++ l))
(multi_log habd)) (pperm habd) (nps habd)).
{
eapply consistent_ppage_log_gss; eauto.
rewrite multi_log_re. trivial.
}
unfold consistent_ppage_log in Hcon.
rewrite ZMap.gss in Hcon.
rewrite <- multi_oracle_re, <- CPU_ID_re in Hdestruct6.
specialize (Hcon _ _ refl_equal Hdestruct6).
unfold weak_consistent_ppage in Hcon.
specialize (Hcon i).
exploit Hcon; eauto.
{ omega. }
{ rewrite H. congruence. }
{
intros HF. destruct a0 as (? & HTrue & ?).
congruence.
}
× rewrite ZMap.gso; auto.
- refine_split´; eauto.
+ inv HR. constructor; trivial; simpl.
- refine_split´; eauto.
+ inv HR. constructor; trivial; simpl.
Qed.
Lemma PageI_4:
∀ i ofs,
i × 4 ≤ ofs < i × 4 + size_chunk Mint32 →
PageI ofs = PageI (i × 4).
Proof.
simpl; intros.
assert (HP: ∃ a, ofs = i × 4 + a
∧ 0≤ a ≤ 3).
{
∃ (ofs - i × 4). split; omega.
}
destruct HP as (a & Heq & Hrange). clear H.
rewrite Heq. unfold PageI. clear Heq.
assert (HP: ∃ b c, i = 1024 × b + c
∧ 0≤ c < 1024).
{
∃ (i/1024), (i mod 1024). split.
apply Z_div_mod_eq. omega.
apply Z_mod_lt. omega.
}
destruct HP as (b & c & Heq & Hrange´).
rewrite Heq. clear Heq.
replace ((1024 × b + c) × 4) with (b × 4096 + c × 4) by omega.
replace (b × 4096 + c × 4 + a) with (b × 4096 + (c × 4 + a)) by omega.
assert (HT: 4096 ≠ 0) by omega.
repeat rewrite Z_div_plus_full_l; try assumption.
clear HT.
repeat rewrite Zdiv_small. reflexivity.
omega. omega.
Qed.
Lemma fload_exist:
∀ habd labd i z f,
fload_spec i habd = Some z
→ relate_RData f habd labd
→ fload´_spec i labd = Some z.
Proof.
unfold fload_spec, fload´_spec; intros.
revert H. inv H0. subrewrite.
assert (HG: ∀ ofs´,
i × 4 ≤ ofs´ < i × 4 + size_chunk Mint32 →
∀ o, ZMap.get (PageI ofs´) (pperm habd) ≠ PGHide o).
{
intros. erewrite PageI_4; eauto 1.
subdestruct.
}
specialize (FlatMem.load_inj _ _ Mint32 (i × 4) _ f flatmem_re refl_equal).
subdestruct. intros (v2 & HLD & HVAL).
rewrite HLD. inv HVAL. assumption.
Qed.
Lemma page_copy_exist:
∀ s habd habd´ labd index i from f,
page_copy_spec index i from habd = Some habd´
→ relate_AbData s f habd labd
→ ∃ labd´, page_copy0_spec index i from labd = Some labd´
∧ relate_AbData s f habd´ labd´
∧ PT habd´ = PT habd
∧ ptpool habd´ = ptpool habd
∧ CR3 labd´ = CR3 labd
∧ pperm habd´ = pperm habd
∧ idpde habd´ = idpde habd.
Proof.
unfold page_copy0_spec, page_copy_spec; intros.
inversion H0.
revert H. subrewrite.
subdestruct. inv HQ.
assert (HW: ZMap.get (PageI from) (pperm labd) = PGAlloc).
{
specialize (pperm_re (PageI from)).
rewrite Hdestruct6 in pperm_re.
inv pperm_re; reflexivity.
}
rewrite HW.
exploit page_copy_aux_exists; eauto.
intros.
rewrite H.
rewrite Hdestruct11.
refine_split´; try trivial.
econstructor; simpl; auto.
rewrite ikern_re; auto.
rewrite ihost_re; auto.
Qed.
Lemma page_copy_back_aux_load_other_plus:
∀ n h h´ pp to buff vadr o,
ZMap.get (PageI to) pp = PGAlloc →
ZMap.get (PageI vadr) pp = PGHide o →
(4 | to) →
PageI to = PageI (to + (Z.of_nat (n + 1)) × 4 - 4) →
PageI (vadr) = PageI (vadr + 3) →
(4 | vadr) →
page_copy_back_aux (n + 1) to buff h = Some h´ →
FlatMem.load Mint32 h vadr = FlatMem.load Mint32 h´ vadr.
Proof.
intros until n.
induction n.
- simpl; intros.
subdestruct. inv H5.
erewrite (FlatMem.load_store_other Mint32 h (FlatMem.store Mint32 h to (Vint i))); eauto 2.
simpl.
assert (¬ ( vadr - 4 < to < vadr + 4)).
{
red; intros.
assert (vadr ≤ to).
{
destruct H1 as (m & He).
destruct H4 as (m´ & He´).
subst.
destruct (zle (m´ -1) m).
- omega.
- omega.
}
assert (vadr ≤ to ≤ vadr + 3) by omega.
exploit PageI_range; eauto.
intros.
assert (vadr ≤ vadr ≤ vadr + 3) by omega.
exploit PageI_range; eauto.
intros. congruence.
}
omega.
- simpl; intros. subdestruct.
exploit (IHn (FlatMem.store Mint32 h to (Vint i))); try eapply H5; try eassumption.
+ erewrite PageI_range; eauto.
eapply to_range.
+ apply to_add_divide; eauto.
+ eapply PageI_eq; eauto.
+ intros. erewrite <- H6.
erewrite (FlatMem.load_store_other Mint32 h (FlatMem.store Mint32 h to (Vint i))); eauto 2.
simpl.
assert (¬ ( vadr - 4 < to < vadr + 4)).
{
red; intros.
assert (vadr ≤ to).
{
destruct H1 as (m & He).
destruct H4 as (m´ & He´).
subst.
destruct (zle (m´ -1) m).
- omega.
- omega.
}
assert (vadr ≤ to ≤ vadr + 3) by omega.
exploit PageI_range; eauto.
intros.
assert (vadr ≤ vadr ≤ vadr + 3) by omega.
exploit PageI_range; eauto.
intros. congruence.
}
omega.
Qed.
Lemma page_copy_back_aux_load_other´:
∀ n h h´ pp to buff o vadr,
ZMap.get (PageI to) pp = PGAlloc →
ZMap.get (PageI vadr) pp = PGHide o →
(PgSize | to) →
Z.of_nat n ≤ one_k →
PageI (vadr) = PageI (vadr + 3) →
(4 | vadr) →
page_copy_back_aux n to buff h = Some h´ →
FlatMem.load Mint32 h vadr = FlatMem.load Mint32 h´ vadr.
Proof.
destruct n; intros.
- simpl in ×. inv H5. trivial.
- replace (S n) with ((n + 1)%nat) in × by omega.
eapply page_copy_back_aux_load_other_plus; eauto.
+ destruct H1 as (i & He).
∃ (i × 1024).
subst. omega.
+ eapply PageI_divide; eauto.
Qed.
Lemma page_copy_back_aux_load_other:
∀ vadr n h h´ pp to buff o,
page_copy_back_aux (Z.to_nat n) to buff h = Some h´ →
ZMap.get (PageI vadr) pp = PGHide o →
ZMap.get (PageI to) pp = PGAlloc →
(PgSize | to) →
0 ≤ n ≤ one_k →
PageI (vadr) = PageI (vadr + 3) →
(4 | vadr) →
FlatMem.load Mint32 h vadr = FlatMem.load Mint32 h´ vadr.
Proof.
intros.
eapply page_copy_back_aux_load_other´; eauto.
rewrite Z2Nat.id; try omega.
Qed.
Lemma page_copy_back_exist:
∀ s habd habd´ labd index i from m f,
page_copy_back_spec index i from habd = Some habd´
→ relate_AbData s f habd labd
→ match_RData s habd m f
→ ∃ labd´, page_copy_back0_spec index i from labd = Some labd´
∧ relate_AbData s f habd´ labd´
∧ PT habd´ = PT habd
∧ ptpool habd´ = ptpool habd
∧ CR3 labd´ = CR3 labd
∧ pperm habd´ = pperm habd
∧ idpde habd´ = idpde habd.
Proof.
unfold page_copy_back0_spec, page_copy_back_spec; intros.
inversion H0.
revert H. subrewrite.
subdestruct. inv HQ.
assert (HW: ZMap.get (PageI from) (pperm labd) = PGAlloc).
{
specialize (pperm_re (PageI from)).
rewrite Hdestruct6 in pperm_re.
inv pperm_re; reflexivity.
}
rewrite HW.
exploit page_copy_back_aux_exists; eauto.
intros.
destruct H as (lh´ & H & Hrel).
rewrite H.
refine_split´; try trivial.
econstructor; simpl; auto.
rewrite ikern_re; auto.
rewrite ihost_re; auto.
-
constructor; intros. inv relate_PMap_re.
specialize (H6 _ H2 _ H3 _ _ H4 _ H5).
inv H1. inv H7. specialize (H1 _ H2).
inv H1. specialize (H7 _ H3).
destruct H7 as (v0 & _ & _ & HMAT).
unfold PMap, ZMap.t, PMap.t in H4, HMAT. rewrite H4 in HMAT.
inv HMAT.
assert (HPA: PageI (pi × 4096 + vadr × 4) = pi).
{
revert H5. clear; intros.
unfold PageI.
rewrite Z_div_plus_full_l; [| omega].
rewrite (Zdiv_small (vadr × 4) PgSize); rewrite_omega.
}
clear HW.
exploit (page_copy_back_aux_load_other (pi × 4096 + vadr × 4)); eauto.
+ rewrite HPA. eassumption.
+ revert H5. clear; intros.
unfold PageI.
replace (pi × 4096 + vadr × 4 + 3)
with (pi × 4096 + (vadr × 4 + 3)) by omega.
repeat (rewrite Z_div_plus_full_l; [| omega]).
rewrite (Zdiv_small (vadr × 4) PgSize); rewrite_omega.
rewrite (Zdiv_small (vadr × 4 + 3) PgSize); rewrite_omega.
+ ∃ (pi × 1024 + vadr); omega.
+ intros.
rewrite <- H1. eauto.
Qed.
End Exists.
Ltac pattern2_refinement_simpl:=
pattern2_refinement_simpl´ (@relate_AbData).
Lemma passthrough_correct:
sim (crel HDATA LDATA) mptintro_passthrough malh.
Proof.
sim_oplus.
-
layer_sim_simpl; compatsim_simpl (@match_AbData); intros.
match_external_states_simpl.
erewrite fload_exist; eauto 1. reflexivity.
-
layer_sim_simpl; compatsim_simpl (@match_AbData); intros.
exploit fstore_exist; eauto 1. intros (labd´ & HP & HM & HN1 & HN2 & HN3 & HN4 & HN5).
match_external_states_simpl.
- layer_sim_simpl; compatsim_simpl (@match_AbData); intros.
exploit page_copy_exist; eauto 1.
intros (labd´ & HP & HM & HN1 & HN2 & HN3 & HN4 & HN5).
match_external_states_simpl.
- layer_sim_simpl; compatsim_simpl (@match_AbData); intros.
exploit page_copy_back_exist; eauto 1.
intros (labd´ & HP & HM & HN1 & HN2 & HN3 & HN4 & HN5).
match_external_states_simpl.
- apply vmxinfo_get_sim.
-
layer_sim_simpl; compatsim_simpl (@match_AbData); intros.
exploit setPG_exist; eauto 1; intros (labd´ & HP & HM & HN1 & HN2 & HN3 & HN4 & HN5).
match_external_states_simpl.
- apply get_at_c_sim.
- apply set_at_c0_sim.
-
layer_sim_simpl; compatsim_simpl (@match_AbData); intros.
exploit lpalloc_exist; eauto 1. intros (labd´ & HP & HM & HN1 & HN2 & HN3 & HN4 & HN5).
refine_split; try econstructor; eauto. econstructor; eauto.
constructor; eauto.
constructor; subrewrite´.
eapply match_PMapPool_Hide; try eassumption.
intros; eapply HN5. assumption.
-
layer_sim_simpl; compatsim_simpl (@match_AbData); intros.
exploit meminit_exist; eauto 1; intros (labd´ & HP & HM & HN1 & HN2 & HN3 & HN4 & HN5).
match_external_states_simpl.
- apply container_get_parent_sim.
- apply container_get_nchildren_sim.
- apply container_get_quota_sim.
- apply container_get_usage_sim.
- apply container_can_consume_sim.
- apply container_split_sim.
- apply get_CPU_ID_sim.
- apply get_curid_sim.
- apply set_curid_sim.
- apply set_curid_init_sim.
- apply (release_lock_sim (valid_arg_imply:= Shared2ID1_imply)).
-
eapply acquire_lock_sim1; eauto.
intros. inv H; trivial. inv H0; trivial. inv H.
- apply cli_sim.
- apply sti_sim.
- apply serial_intr_disable_sim.
- apply serial_intr_enable_sim.
- apply serial_putc_sim.
- apply cons_buf_read_sim.
- apply trapin_sim.
-
layer_sim_simpl; compatsim_simpl (@match_AbData); intros.
inv match_extcall_states.
exploit trapout_exist; eauto 1; intros (labd´ & HP & HM & HN1 & HN2 & HN3 & HN4 & HN5).
inv match_match. match_external_states_simpl.
- apply hostin_sim.
- apply hostout_sim.
- apply proc_create_postinit_sim.
- apply trap_info_get_sim.
- apply trap_info_ret_sim.
- layer_sim_simpl.
+ eapply load_correct.
+ eapply store_correct.
Qed.
End WITHMEM.
End Refinement.