1(* 2 * Copyright 2014, General Dynamics C4 Systems 3 * 4 * SPDX-License-Identifier: GPL-2.0-only 5 *) 6 7(* 8Functions for cancelling IPC. 9*) 10 11chapter "IPC Cancelling" 12 13theory IpcCancel_A 14imports ArchIpcCancel_A 15begin 16 17context begin interpretation Arch . 18 19requalify_consts 20 arch_post_cap_deletion 21 arch_gen_obj_refs 22 arch_cap_cleanup_opt 23 faultRegister 24 nextInstructionRegister 25 26requalify_types 27 arch_gen_obj_ref 28 29end 30 31text \<open>Getting and setting endpoint queues.\<close> 32definition 33 get_ep_queue :: "endpoint \<Rightarrow> (obj_ref list,'z::state_ext) s_monad" 34where 35 "get_ep_queue ep \<equiv> case ep of SendEP q \<Rightarrow> return q 36 | RecvEP q \<Rightarrow> return q 37 | _ \<Rightarrow> fail" 38 39primrec (nonexhaustive) 40 update_ep_queue :: "endpoint \<Rightarrow> obj_ref list \<Rightarrow> endpoint" 41where 42 "update_ep_queue (RecvEP q) q' = RecvEP q'" 43| "update_ep_queue (SendEP q) q' = SendEP q'" 44 45 46text \<open>Cancel all message operations on threads currently queued within this 47synchronous message endpoint. Threads so queued are placed in the Restart state. 48Once scheduled they will reattempt the operation that previously caused them 49to be queued here.\<close> 50definition 51 cancel_all_ipc :: "obj_ref \<Rightarrow> (unit,'z::state_ext) s_monad" 52where 53 "cancel_all_ipc epptr \<equiv> do 54 ep \<leftarrow> get_endpoint epptr; 55 case ep of IdleEP \<Rightarrow> return () 56 | _ \<Rightarrow> do 57 queue \<leftarrow> get_ep_queue ep; 58 set_endpoint epptr IdleEP; 59 mapM_x (\<lambda>t. do set_thread_state t Restart; 60 do_extended_op (tcb_sched_action (tcb_sched_enqueue) t) od) $ queue; 61 do_extended_op (reschedule_required) 62 od 63 od" 64 65text \<open>The badge stored by thread waiting on a message send operation.\<close> 66primrec (nonexhaustive) 67 blocking_ipc_badge :: "thread_state \<Rightarrow> badge" 68where 69 "blocking_ipc_badge (BlockedOnSend t payload) = sender_badge payload" 70 71text \<open>Cancel all message send operations on threads queued in this endpoint 72and using a particular badge.\<close> 73definition 74 cancel_badged_sends :: "obj_ref \<Rightarrow> badge \<Rightarrow> (unit,'z::state_ext) s_monad" 75where 76 "cancel_badged_sends epptr badge \<equiv> do 77 ep \<leftarrow> get_endpoint epptr; 78 case ep of 79 IdleEP \<Rightarrow> return () 80 | RecvEP _ \<Rightarrow> return () 81 | SendEP queue \<Rightarrow> do 82 set_endpoint epptr IdleEP; 83 queue' \<leftarrow> (swp filterM queue) (\<lambda> t. do 84 st \<leftarrow> get_thread_state t; 85 if blocking_ipc_badge st = badge then do 86 set_thread_state t Restart; 87 do_extended_op (tcb_sched_action (tcb_sched_enqueue) t); 88 return False od 89 else return True 90 od); 91 ep' \<leftarrow> return (case queue' of 92 [] \<Rightarrow> IdleEP 93 | _ \<Rightarrow> SendEP queue'); 94 set_endpoint epptr ep'; 95 do_extended_op (reschedule_required) 96 od 97 od" 98 99text \<open>Cancel all message operations on threads queued in a notification 100endpoint.\<close> 101 102abbreviation 103 do_unbind_notification :: "obj_ref \<Rightarrow> notification \<Rightarrow> obj_ref \<Rightarrow> (unit,'z::state_ext) s_monad" 104where 105 "do_unbind_notification ntfnptr ntfn tcbptr \<equiv> do 106 ntfn' \<leftarrow> return $ ntfn_set_bound_tcb ntfn None; 107 set_notification ntfnptr ntfn'; 108 set_bound_notification tcbptr None 109 od" 110 111definition 112 unbind_notification :: "obj_ref \<Rightarrow> (unit,'z::state_ext) s_monad" 113where 114 "unbind_notification tcb \<equiv> do 115 ntfnptr \<leftarrow> get_bound_notification tcb; 116 case ntfnptr of 117 Some ntfnptr' \<Rightarrow> do 118 ntfn \<leftarrow> get_notification ntfnptr'; 119 do_unbind_notification ntfnptr' ntfn tcb 120 od 121 | None \<Rightarrow> return () 122 od" 123 124definition 125 unbind_maybe_notification :: "obj_ref \<Rightarrow> (unit, 'z::state_ext) s_monad" 126where 127 "unbind_maybe_notification ntfnptr \<equiv> do 128 ntfn \<leftarrow> get_notification ntfnptr; 129 (case ntfn_bound_tcb ntfn of 130 Some t \<Rightarrow> do_unbind_notification ntfnptr ntfn t 131 | None \<Rightarrow> return ()) 132 od" 133 134definition 135 cancel_all_signals :: "obj_ref \<Rightarrow> (unit,'z::state_ext) s_monad" 136where 137 "cancel_all_signals ntfnptr \<equiv> do 138 ntfn \<leftarrow> get_notification ntfnptr; 139 case ntfn_obj ntfn of WaitingNtfn queue \<Rightarrow> do 140 _ \<leftarrow> set_notification ntfnptr $ ntfn_set_obj ntfn IdleNtfn; 141 mapM_x (\<lambda>t. do set_thread_state t Restart; 142 do_extended_op (tcb_sched_action tcb_sched_enqueue t) od) queue; 143 do_extended_op (reschedule_required) 144 od 145 | _ \<Rightarrow> return () 146 od" 147 148text \<open>The endpoint pointer stored by a thread waiting for a message to be 149transferred in either direction.\<close> 150definition 151 get_blocking_object :: "thread_state \<Rightarrow> (obj_ref,'z::state_ext) s_monad" 152where 153 "get_blocking_object state \<equiv> 154 case state of BlockedOnReceive epptr x \<Rightarrow> return epptr 155 | BlockedOnSend epptr x \<Rightarrow> return epptr 156 | _ \<Rightarrow> fail" 157 158 159text \<open>Cancel whatever IPC operation a thread is engaged in.\<close> 160definition 161 blocked_cancel_ipc :: "thread_state \<Rightarrow> obj_ref \<Rightarrow> (unit,'z::state_ext) s_monad" 162where 163 "blocked_cancel_ipc state tptr \<equiv> do 164 epptr \<leftarrow> get_blocking_object state; 165 ep \<leftarrow> get_endpoint epptr; 166 queue \<leftarrow> get_ep_queue ep; 167 queue' \<leftarrow> return $ remove1 tptr queue; 168 ep' \<leftarrow> return (case queue' of [] \<Rightarrow> IdleEP 169 | _ \<Rightarrow> update_ep_queue ep queue'); 170 set_endpoint epptr ep'; 171 set_thread_state tptr Inactive 172 od" 173 174text \<open>Finalise a capability if the capability is known to be of the kind 175which can be finalised immediately. This is a simplified version of the 176@{text finalise_cap} operation.\<close> 177fun 178 fast_finalise :: "cap \<Rightarrow> bool \<Rightarrow> (unit,'z::state_ext) s_monad" 179where 180 "fast_finalise NullCap final = return ()" 181| "fast_finalise (ReplyCap r m R) final = return ()" 182| "fast_finalise (EndpointCap r b R) final = 183 (when final $ cancel_all_ipc r)" 184| "fast_finalise (NotificationCap r b R) final = 185 (when final $ do 186 unbind_maybe_notification r; 187 cancel_all_signals r 188 od)" 189| "fast_finalise (CNodeCap r bits g) final = fail" 190| "fast_finalise (ThreadCap r) final = fail" 191| "fast_finalise DomainCap final = fail" 192| "fast_finalise (Zombie r b n) final = fail" 193| "fast_finalise IRQControlCap final = fail" 194| "fast_finalise (IRQHandlerCap irq) final = fail" 195| "fast_finalise (UntypedCap dev r n f) final = fail" 196| "fast_finalise (ArchObjectCap a) final = fail" 197 198text \<open>The optional IRQ stored in a capability, presented either as an optional 199value or a set.\<close> 200definition 201 cap_irq_opt :: "cap \<Rightarrow> irq option" where 202 "cap_irq_opt cap \<equiv> case cap of IRQHandlerCap irq \<Rightarrow> Some irq | _ \<Rightarrow> None" 203 204definition 205 cap_irqs :: "cap \<Rightarrow> irq set" where 206 "cap_irqs cap \<equiv> set_option (cap_irq_opt cap)" 207 208text \<open>A generic reference to an object. Used for the purposes of finalisation, 209where we want to be able to compare caps to decide if they refer to the "same object", 210which can be determined in several ways\<close> 211datatype gen_obj_ref = 212 ObjRef obj_ref 213 | IRQRef irq 214 | ArchRef arch_gen_obj_ref 215 216definition 217 arch_cap_set_map :: "(arch_cap \<Rightarrow> 'a set) \<Rightarrow> cap \<Rightarrow> 'a set" 218where 219 "arch_cap_set_map f cap \<equiv> case cap of 220 ArchObjectCap acap \<Rightarrow> f acap 221 | _ \<Rightarrow> {}" 222 223abbreviation 224 arch_gen_refs :: "cap \<Rightarrow> arch_gen_obj_ref set" 225where 226 "arch_gen_refs \<equiv> arch_cap_set_map arch_gen_obj_refs" 227 228definition 229 gen_obj_refs :: "cap \<Rightarrow> gen_obj_ref set" 230where 231 "gen_obj_refs c \<equiv> ObjRef ` (obj_refs c) 232 \<union> IRQRef ` (cap_irqs c) 233 \<union> ArchRef ` (arch_gen_refs c)" 234 235definition 236 cap_cleanup_opt :: "cap \<Rightarrow> cap" 237where 238 "cap_cleanup_opt c \<equiv> case c of 239 IRQHandlerCap _ \<Rightarrow> c 240 | ArchObjectCap acap \<Rightarrow> arch_cap_cleanup_opt acap 241 | _ \<Rightarrow> NullCap" 242 243 244text \<open>Detect whether a capability is the final capability to a given object 245remaining in the system. Finalisation actions need to be taken when the final 246capability to the object is deleted.\<close> 247definition 248 is_final_cap' :: "cap \<Rightarrow> 'z::state_ext state \<Rightarrow> bool" where 249 "is_final_cap' cap s \<equiv> 250 \<exists>cref. {cref. \<exists>cap'. fst (get_cap cref s) = {(cap', s)} 251 \<and> (gen_obj_refs cap \<inter> gen_obj_refs cap' \<noteq> {})} 252 = {cref}" 253 254definition 255 is_final_cap :: "cap \<Rightarrow> (bool,'z::state_ext) s_monad" where 256 "is_final_cap cap \<equiv> gets (is_final_cap' cap)" 257 258text \<open>Actions to be taken after an IRQ handler capability is deleted.\<close> 259definition 260 deleted_irq_handler :: "irq \<Rightarrow> (unit,'z::state_ext) s_monad" 261where 262 "deleted_irq_handler irq \<equiv> set_irq_state IRQInactive irq" 263 264text \<open>Actions to be taken after a cap is deleted\<close> 265definition 266 post_cap_deletion :: "cap \<Rightarrow> (unit, 'z::state_ext) s_monad" 267where 268 "post_cap_deletion cap \<equiv> case cap of 269 IRQHandlerCap irq \<Rightarrow> deleted_irq_handler irq 270 | ArchObjectCap acap \<Rightarrow> arch_post_cap_deletion acap 271 | _ \<Rightarrow> return ()" 272 273text \<open>Empty a capability slot assuming that the capability in it has been 274finalised already.\<close> 275 276definition 277 empty_slot :: "cslot_ptr \<Rightarrow> cap \<Rightarrow> (unit,'z::state_ext) s_monad" 278where 279 "empty_slot slot cleanup_info \<equiv> do 280 cap \<leftarrow> get_cap slot; 281 if cap = NullCap then 282 return () 283 else do 284 slot_p \<leftarrow> gets (\<lambda>s. cdt s slot); 285 cdt \<leftarrow> gets cdt; 286 parent \<leftarrow> return $ cdt slot; 287 set_cdt ((\<lambda>p. if cdt p = Some slot 288 then parent 289 else cdt p) (slot := None)); 290 do_extended_op (empty_slot_ext slot slot_p); 291 set_original slot False; 292 set_cap NullCap slot; 293 294 post_cap_deletion cleanup_info 295 od 296 od" 297 298text \<open>Delete a capability with the assumption that the fast finalisation 299process will be sufficient.\<close> 300definition 301 cap_delete_one :: "cslot_ptr \<Rightarrow> (unit,'z::state_ext) s_monad" where 302 "cap_delete_one slot \<equiv> do 303 cap \<leftarrow> get_cap slot; 304 unless (cap = NullCap) $ do 305 final \<leftarrow> is_final_cap cap; 306 fast_finalise cap final; 307 empty_slot slot NullCap 308 od 309 od" 310 311text \<open>Cancel the message receive operation of a thread waiting for a Reply 312capability it has issued to be invoked.\<close> 313definition 314 reply_cancel_ipc :: "obj_ref \<Rightarrow> (unit,'z::state_ext) s_monad" 315where 316 "reply_cancel_ipc tptr \<equiv> do 317 thread_set (\<lambda>tcb. tcb \<lparr> tcb_fault := None \<rparr>) tptr; 318 cap \<leftarrow> get_cap (tptr, tcb_cnode_index 2); 319 descs \<leftarrow> gets (descendants_of (tptr, tcb_cnode_index 2) o cdt); 320 when (descs \<noteq> {}) $ do 321 assert (\<exists>cslot_ptr. descs = {cslot_ptr}); 322 cslot_ptr \<leftarrow> select descs; 323 cap_delete_one cslot_ptr 324 od 325 od" 326 327text \<open>Cancel the message receive operation of a thread queued in an 328notification object.\<close> 329definition 330 cancel_signal :: "obj_ref \<Rightarrow> obj_ref \<Rightarrow> (unit,'z::state_ext) s_monad" 331where 332 "cancel_signal threadptr ntfnptr \<equiv> do 333 ntfn \<leftarrow> get_notification ntfnptr; 334 queue \<leftarrow> (case ntfn_obj ntfn of WaitingNtfn queue \<Rightarrow> return queue 335 | _ \<Rightarrow> fail); 336 queue' \<leftarrow> return $ remove1 threadptr queue; 337 newNTFN \<leftarrow> return $ ntfn_set_obj ntfn (case queue' of [] \<Rightarrow> IdleNtfn 338 | _ \<Rightarrow> WaitingNtfn queue'); 339 set_notification ntfnptr newNTFN; 340 set_thread_state threadptr Inactive 341 od" 342 343text \<open>Cancel any message operations a given thread is waiting on.\<close> 344definition 345 cancel_ipc :: "obj_ref \<Rightarrow> (unit,'z::state_ext) s_monad" 346where 347 "cancel_ipc tptr \<equiv> do 348 state \<leftarrow> get_thread_state tptr; 349 case state 350 of 351 BlockedOnSend x y \<Rightarrow> blocked_cancel_ipc state tptr 352 | BlockedOnReceive x y \<Rightarrow> blocked_cancel_ipc state tptr 353 | BlockedOnNotification event \<Rightarrow> cancel_signal tptr event 354 | BlockedOnReply \<Rightarrow> reply_cancel_ipc tptr 355 | _ \<Rightarrow> return () 356 od" 357 358text \<open>Currently, @{text update_restart_pc} can be defined generically up to 359the actual register numbers.\<close> 360definition 361 update_restart_pc :: "obj_ref \<Rightarrow> (unit, 'z::state_ext) s_monad" 362where 363 "update_restart_pc thread_ptr = 364 as_user thread_ptr (getRegister nextInstructionRegister 365 >>= setRegister faultRegister)" 366 367text \<open>Suspend a thread, cancelling any pending operations and preventing it 368from further execution by setting it to the Inactive state.\<close> 369definition 370 suspend :: "obj_ref \<Rightarrow> (unit,'z::state_ext) s_monad" 371where 372 "suspend thread \<equiv> do 373 cancel_ipc thread; 374 state \<leftarrow> get_thread_state thread; 375 (if state = Running then update_restart_pc thread else return ()); 376 set_thread_state thread Inactive; 377 do_extended_op (tcb_sched_action (tcb_sched_dequeue) thread) 378 od" 379 380end 381