miri/borrow_tracker/tree_borrows/perms.rs
1use std::cmp::{Ordering, PartialOrd};
2use std::fmt;
3
4use crate::AccessKind;
5use crate::borrow_tracker::tree_borrows::diagnostics::TransitionError;
6use crate::borrow_tracker::tree_borrows::tree::AccessRelatedness;
7
8/// The activation states of a pointer.
9#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
10enum PermissionPriv {
11 /// represents: a shared reference to interior mutable data.
12 /// allows: all foreign and child accesses;
13 /// rejects: nothing
14 Cell,
15 /// represents: a local mutable reference that has not yet been written to;
16 /// allows: child reads, foreign reads;
17 /// affected by: child writes (becomes Active),
18 /// rejects: foreign writes (Disabled).
19 ///
20 /// `ReservedFrz` is mostly for types that are `Freeze` (no interior mutability).
21 /// If the type has interior mutability, see `ReservedIM` instead.
22 /// (Note: since the discovery of `tests/fail/tree_borrows/reservedim_spurious_write.rs`,
23 /// we also use `ReservedFreeze` for mutable references that were retagged with a protector
24 /// independently of interior mutability)
25 ///
26 /// special case: behaves differently when protected, which is where `conflicted`
27 /// is relevant
28 /// - `conflicted` is set on foreign reads,
29 /// - `conflicted` must not be set on child writes (there is UB otherwise).
30 ///
31 /// This is so that the behavior of `Reserved` adheres to the rules of `noalias`:
32 /// - foreign-read then child-write is UB due to `conflicted`,
33 /// - child-write then foreign-read is UB since child-write will activate and then
34 /// foreign-read disables a protected `Active`, which is UB.
35 ReservedFrz { conflicted: bool },
36 /// Alternative version of `ReservedFrz` made for types with interior mutability.
37 /// allows: child reads, foreign reads, foreign writes (extra);
38 /// affected by: child writes (becomes Active);
39 /// rejects: nothing.
40 ReservedIM,
41 /// represents: a unique pointer;
42 /// allows: child reads, child writes;
43 /// rejects: foreign reads (Frozen), foreign writes (Disabled).
44 Active,
45 /// represents: a shared pointer;
46 /// allows: all read accesses;
47 /// rejects child writes (UB), foreign writes (Disabled).
48 Frozen,
49 /// represents: a dead pointer;
50 /// allows: all foreign accesses;
51 /// rejects: all child accesses (UB).
52 Disabled,
53}
54use self::PermissionPriv::*;
55use super::foreign_access_skipping::IdempotentForeignAccess;
56
57impl PartialOrd for PermissionPriv {
58 /// PermissionPriv is ordered by the reflexive transitive closure of
59 /// `Reserved(conflicted=false) < Reserved(conflicted=true) < Active < Frozen < Disabled`.
60 /// `Reserved` that have incompatible `ty_is_freeze` are incomparable to each other.
61 /// This ordering matches the reachability by transitions, as asserted by the exhaustive test
62 /// `permissionpriv_partialord_is_reachability`.
63 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
64 use Ordering::*;
65 Some(match (self, other) {
66 (a, b) if a == b => Equal,
67 // Versions of `Reserved` with different interior mutability are incomparable with each
68 // other.
69 (ReservedIM, ReservedFrz { .. })
70 | (ReservedFrz { .. }, ReservedIM)
71 // `Cell` is not comparable with any other permission
72 // since it never transitions to any other state and we
73 // can never get to `Cell` from another state.
74 | (Cell, _) | (_, Cell) => return None,
75 (Disabled, _) => Greater,
76 (_, Disabled) => Less,
77 (Frozen, _) => Greater,
78 (_, Frozen) => Less,
79 (Active, _) => Greater,
80 (_, Active) => Less,
81 (ReservedIM, ReservedIM) => Equal,
82 (ReservedFrz { conflicted: c1 }, ReservedFrz { conflicted: c2 }) => {
83 // `bool` is ordered such that `false <= true`, so this works as intended.
84 c1.cmp(c2)
85 }
86 })
87 }
88}
89
90impl PermissionPriv {
91 /// Check if `self` can be the initial state of a pointer.
92 fn is_initial(&self) -> bool {
93 matches!(self, ReservedFrz { conflicted: false } | Frozen | ReservedIM | Cell)
94 }
95
96 /// Reject `ReservedIM` that cannot exist in the presence of a protector.
97 fn compatible_with_protector(&self) -> bool {
98 // FIXME(TB-Cell): It is unclear what to do here.
99 // `Cell` will occur with a protector but won't provide the guarantees
100 // of noalias (it will fail the `protected_enforces_noalias` test).
101 !matches!(self, ReservedIM | Cell)
102 }
103
104 /// See `foreign_access_skipping.rs`. Computes the SIFA of a permission.
105 fn strongest_idempotent_foreign_access(&self, prot: bool) -> IdempotentForeignAccess {
106 match self {
107 // Cell survives any foreign access
108 Cell => IdempotentForeignAccess::Write,
109 // A protected non-conflicted Reserved will become conflicted under a foreign read,
110 // and is hence not idempotent under it.
111 ReservedFrz { conflicted } if prot && !conflicted => IdempotentForeignAccess::None,
112 // Otherwise, foreign reads do not affect Reserved
113 ReservedFrz { .. } => IdempotentForeignAccess::Read,
114 // Famously, ReservedIM survives foreign writes. It is never protected.
115 ReservedIM if prot => unreachable!("Protected ReservedIM should not exist!"),
116 ReservedIM => IdempotentForeignAccess::Write,
117 // Active changes on any foreign access (becomes Frozen/Disabled).
118 Active => IdempotentForeignAccess::None,
119 // Frozen survives foreign reads, but not writes.
120 Frozen => IdempotentForeignAccess::Read,
121 // Disabled survives foreign reads and writes. It survives them
122 // even if protected, because a protected `Disabled` is not initialized
123 // and does therefore not trigger UB.
124 Disabled => IdempotentForeignAccess::Write,
125 }
126 }
127}
128
129/// This module controls how each permission individually reacts to an access.
130/// Although these functions take `protected` as an argument, this is NOT because
131/// we check protector violations here, but because some permissions behave differently
132/// when protected.
133mod transition {
134 use super::*;
135 /// A child node was read-accessed: UB on Disabled, noop on the rest.
136 fn child_read(state: PermissionPriv, _protected: bool) -> Option<PermissionPriv> {
137 Some(match state {
138 Disabled => return None,
139 // The inner data `ty_is_freeze` of `Reserved` is always irrelevant for Read
140 // accesses, since the data is not being mutated. Hence the `{ .. }`.
141 readable @ (Cell | ReservedFrz { .. } | ReservedIM | Active | Frozen) => readable,
142 })
143 }
144
145 /// A non-child node was read-accessed: keep `Reserved` but mark it as `conflicted` if it
146 /// is protected; invalidate `Active`.
147 fn foreign_read(state: PermissionPriv, protected: bool) -> Option<PermissionPriv> {
148 Some(match state {
149 // Cell ignores foreign reads.
150 Cell => Cell,
151 // Non-writeable states just ignore foreign reads.
152 non_writeable @ (Frozen | Disabled) => non_writeable,
153 // Writeable states are more tricky, and depend on whether things are protected.
154 // The inner data `ty_is_freeze` of `Reserved` is always irrelevant for Read
155 // accesses, since the data is not being mutated. Hence the `{ .. }`
156
157 // Someone else read. To make sure we won't write before function exit,
158 // we set the "conflicted" flag, which will disallow writes while we are protected.
159 ReservedFrz { .. } if protected => ReservedFrz { conflicted: true },
160 // Before activation and without protectors, foreign reads are fine.
161 // That's the entire point of 2-phase borrows.
162 res @ (ReservedFrz { .. } | ReservedIM) => {
163 // Even though we haven't checked `ReservedIM if protected` separately,
164 // it is a state that cannot occur because under a protector we only
165 // create `ReservedFrz` never `ReservedIM`.
166 assert!(!protected);
167 res
168 }
169 Active =>
170 if protected {
171 // We wrote, someone else reads -- that's bad.
172 // (Since Active is always initialized, this move-to-protected will mean insta-UB.)
173 Disabled
174 } else {
175 // We don't want to disable here to allow read-read reordering: it is crucial
176 // that the foreign read does not invalidate future reads through this tag.
177 Frozen
178 },
179 })
180 }
181
182 /// A child node was write-accessed: `Reserved` must become `Active` to obtain
183 /// write permissions, `Frozen` and `Disabled` cannot obtain such permissions and produce UB.
184 fn child_write(state: PermissionPriv, protected: bool) -> Option<PermissionPriv> {
185 Some(match state {
186 // Cell ignores child writes.
187 Cell => Cell,
188 // If the `conflicted` flag is set, then there was a foreign read during
189 // the function call that is still ongoing (still `protected`),
190 // this is UB (`noalias` violation).
191 ReservedFrz { conflicted: true } if protected => return None,
192 // A write always activates the 2-phase borrow, even with interior
193 // mutability
194 ReservedFrz { .. } | ReservedIM | Active => Active,
195 Frozen | Disabled => return None,
196 })
197 }
198
199 /// A non-child node was write-accessed: this makes everything `Disabled` except for
200 /// non-protected interior mutable `Reserved` which stay the same.
201 fn foreign_write(state: PermissionPriv, protected: bool) -> Option<PermissionPriv> {
202 // There is no explicit dependency on `protected`, but recall that interior mutable
203 // types receive a `ReservedFrz` instead of `ReservedIM` when retagged under a protector,
204 // so the result of this function does indirectly depend on (past) protector status.
205 Some(match state {
206 // Cell ignores foreign writes.
207 Cell => Cell,
208 res @ ReservedIM => {
209 // We can never create a `ReservedIM` under a protector, only `ReservedFrz`.
210 assert!(!protected);
211 res
212 }
213 _ => Disabled,
214 })
215 }
216
217 /// Dispatch handler depending on the kind of access and its position.
218 pub(super) fn perform_access(
219 kind: AccessKind,
220 rel_pos: AccessRelatedness,
221 child: PermissionPriv,
222 protected: bool,
223 ) -> Option<PermissionPriv> {
224 match (kind, rel_pos.is_foreign()) {
225 (AccessKind::Write, true) => foreign_write(child, protected),
226 (AccessKind::Read, true) => foreign_read(child, protected),
227 (AccessKind::Write, false) => child_write(child, protected),
228 (AccessKind::Read, false) => child_read(child, protected),
229 }
230 }
231}
232
233/// Public interface to the state machine that controls read-write permissions.
234/// This is the "private `enum`" pattern.
235#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd)]
236pub struct Permission {
237 inner: PermissionPriv,
238}
239
240/// Transition from one permission to the next.
241#[derive(Debug, Clone, Copy, PartialEq, Eq)]
242pub struct PermTransition {
243 from: PermissionPriv,
244 to: PermissionPriv,
245}
246
247impl Permission {
248 /// Check if `self` can be the initial state of a pointer.
249 pub fn is_initial(&self) -> bool {
250 self.inner.is_initial()
251 }
252 /// Check if `self` is the terminal state of a pointer (is `Disabled`).
253 pub fn is_disabled(&self) -> bool {
254 self.inner == Disabled
255 }
256 /// Check if `self` is the post-child-write state of a pointer (is `Active`).
257 pub fn is_active(&self) -> bool {
258 self.inner == Active
259 }
260 /// Check if `self` is the never-allow-writes-again state of a pointer (is `Frozen`).
261 pub fn is_frozen(&self) -> bool {
262 self.inner == Frozen
263 }
264
265 /// Check if `self` is the shared-reference-to-interior-mutable-data state of a pointer.
266 pub fn is_cell(&self) -> bool {
267 self.inner == Cell
268 }
269
270 /// Default initial permission of the root of a new tree at inbounds positions.
271 /// Must *only* be used for the root, this is not in general an "initial" permission!
272 pub fn new_active() -> Self {
273 Self { inner: Active }
274 }
275
276 /// Default initial permission of a reborrowed mutable reference that is either
277 /// protected or not interior mutable.
278 fn new_reserved_frz() -> Self {
279 Self { inner: ReservedFrz { conflicted: false } }
280 }
281
282 /// Default initial permission of an unprotected interior mutable reference.
283 fn new_reserved_im() -> Self {
284 Self { inner: ReservedIM }
285 }
286
287 /// Wrapper around `new_reserved_frz` and `new_reserved_im` that decides
288 /// which to call based on the interior mutability and the retag kind (whether there
289 /// is a protector is relevant because being protected takes priority over being
290 /// interior mutable)
291 pub fn new_reserved(ty_is_freeze: bool, protected: bool) -> Self {
292 if ty_is_freeze || protected { Self::new_reserved_frz() } else { Self::new_reserved_im() }
293 }
294
295 /// Default initial permission of a reborrowed shared reference.
296 pub fn new_frozen() -> Self {
297 Self { inner: Frozen }
298 }
299
300 /// Default initial permission of the root of a new tree at out-of-bounds positions.
301 /// Must *only* be used for the root, this is not in general an "initial" permission!
302 pub fn new_disabled() -> Self {
303 Self { inner: Disabled }
304 }
305
306 /// Default initial permission of a shared reference to interior mutable data.
307 pub fn new_cell() -> Self {
308 Self { inner: Cell }
309 }
310
311 /// Reject `ReservedIM` that cannot exist in the presence of a protector.
312 pub fn compatible_with_protector(&self) -> bool {
313 self.inner.compatible_with_protector()
314 }
315
316 /// What kind of access to perform before releasing the protector.
317 pub fn protector_end_access(&self) -> Option<AccessKind> {
318 match self.inner {
319 // Do not do perform access if it is a `Cell`, as this
320 // can cause data races when using thread-safe data types.
321 Cell => None,
322 Active => Some(AccessKind::Write),
323 _ => Some(AccessKind::Read),
324 }
325 }
326
327 /// Apply the transition to the inner PermissionPriv.
328 pub fn perform_access(
329 kind: AccessKind,
330 rel_pos: AccessRelatedness,
331 old_perm: Self,
332 protected: bool,
333 ) -> Option<PermTransition> {
334 let old_state = old_perm.inner;
335 transition::perform_access(kind, rel_pos, old_state, protected)
336 .map(|new_state| PermTransition { from: old_state, to: new_state })
337 }
338
339 /// During a provenance GC, we want to compact the tree.
340 /// For this, we want to merge nodes upwards if they have a singleton parent.
341 /// But we need to be careful: If the parent is Frozen, and the child is Reserved,
342 /// we can not do such a merge. In general, such a merge is possible if the parent
343 /// allows similar accesses, and in particular if the parent never causes UB on its
344 /// own. This is enforced by a test, namely `tree_compacting_is_sound`. See that
345 /// test for more information.
346 /// This method is only sound if the parent is not protected. We never attempt to
347 /// remove protected parents.
348 pub fn can_be_replaced_by_child(self, child: Self) -> bool {
349 match (self.inner, child.inner) {
350 // Cell allows all transitions.
351 (Cell, _) => true,
352 // Cell is the most permissive, nothing can be replaced by Cell.
353 // (ReservedIM, Cell) => true,
354 (_, Cell) => false,
355 // ReservedIM can be replaced by anything besides Cell.
356 // ReservedIM allows all transitions, but unlike Cell, a local write
357 // to ReservedIM transitions to Active, while it is a no-op for Cell.
358 (ReservedIM, _) => true,
359 (_, ReservedIM) => false,
360 // Reserved (as parent, where conflictedness does not matter)
361 // can be replaced by all but ReservedIM and Cell,
362 // since ReservedIM and Cell alone would survive foreign writes
363 (ReservedFrz { .. }, _) => true,
364 (_, ReservedFrz { .. }) => false,
365 // Active can not be replaced by something surviving
366 // foreign reads and then remaining writable (i.e., Reserved*).
367 // Replacing a state by itself is always okay, even if the child state is protected.
368 // Active can be replaced by Frozen, since it is not protected.
369 (Active, Active | Frozen | Disabled) => true,
370 (_, Active) => false,
371 // Frozen can only be replaced by Disabled (and itself).
372 (Frozen, Frozen | Disabled) => true,
373 (_, Frozen) => false,
374 // Disabled can not be replaced by anything else.
375 (Disabled, Disabled) => true,
376 }
377 }
378
379 /// Returns the strongest foreign action this node survives (without change),
380 /// where `prot` indicates if it is protected.
381 /// See `foreign_access_skipping`
382 pub fn strongest_idempotent_foreign_access(&self, prot: bool) -> IdempotentForeignAccess {
383 self.inner.strongest_idempotent_foreign_access(prot)
384 }
385}
386
387impl PermTransition {
388 /// All transitions created through normal means (using `perform_access`)
389 /// should be possible, but the same is not guaranteed by construction of
390 /// transitions inferred by diagnostics. This checks that a transition
391 /// reconstructed by diagnostics is indeed one that could happen.
392 fn is_possible(self) -> bool {
393 self.from <= self.to
394 }
395
396 pub fn from(from: Permission, to: Permission) -> Option<Self> {
397 let t = Self { from: from.inner, to: to.inner };
398 t.is_possible().then_some(t)
399 }
400
401 pub fn is_noop(self) -> bool {
402 self.from == self.to
403 }
404
405 /// Extract result of a transition (checks that the starting point matches).
406 pub fn applied(self, starting_point: Permission) -> Option<Permission> {
407 (starting_point.inner == self.from).then_some(Permission { inner: self.to })
408 }
409
410 /// Extract starting point of a transition
411 pub fn started(self) -> Permission {
412 Permission { inner: self.from }
413 }
414
415 /// Determines if this transition would disable the permission.
416 pub fn produces_disabled(self) -> bool {
417 self.to == Disabled
418 }
419}
420
421pub mod diagnostics {
422 use super::*;
423 impl fmt::Display for PermissionPriv {
424 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
425 write!(
426 f,
427 "{}",
428 match self {
429 Cell => "Cell",
430 ReservedFrz { conflicted: false } => "Reserved",
431 ReservedFrz { conflicted: true } => "Reserved (conflicted)",
432 ReservedIM => "Reserved (interior mutable)",
433 Active => "Active",
434 Frozen => "Frozen",
435 Disabled => "Disabled",
436 }
437 )
438 }
439 }
440
441 impl fmt::Display for PermTransition {
442 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
443 write!(f, "from {} to {}", self.from, self.to)
444 }
445 }
446
447 impl fmt::Display for Permission {
448 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
449 write!(f, "{}", self.inner)
450 }
451 }
452
453 impl Permission {
454 /// Abbreviated name of the permission (uniformly 3 letters for nice alignment).
455 pub fn short_name(self) -> &'static str {
456 // Make sure there are all of the same length as each other
457 // and also as `diagnostics::DisplayFmtPermission.uninit` otherwise
458 // alignment will be incorrect.
459 match self.inner {
460 Cell => "Cel ",
461 ReservedFrz { conflicted: false } => "Res ",
462 ReservedFrz { conflicted: true } => "ResC",
463 ReservedIM => "ReIM",
464 Active => "Act ",
465 Frozen => "Frz ",
466 Disabled => "Dis ",
467 }
468 }
469 }
470
471 impl PermTransition {
472 /// Readable explanation of the consequences of an event.
473 /// Fits in the sentence "This transition corresponds to {trans.summary()}".
474 pub fn summary(&self) -> &'static str {
475 assert!(self.is_possible());
476 assert!(!self.is_noop());
477 match (self.from, self.to) {
478 (_, Active) => "the first write to a 2-phase borrowed mutable reference",
479 (_, Frozen) => "a loss of write permissions",
480 (ReservedFrz { conflicted: false }, ReservedFrz { conflicted: true }) =>
481 "a temporary loss of write permissions until function exit",
482 (Frozen, Disabled) => "a loss of read permissions",
483 (_, Disabled) => "a loss of read and write permissions",
484 (old, new) =>
485 unreachable!("Transition from {old:?} to {new:?} should never be possible"),
486 }
487 }
488
489 /// Determines whether `self` is a relevant transition for the error `err`.
490 /// `self` will be a transition that happened to a tag some time before
491 /// that tag caused the error.
492 ///
493 /// Irrelevant events:
494 /// - modifications of write permissions when the error is related to read permissions
495 /// (on failed reads and protected `Frozen -> Disabled`, ignore `Reserved -> Active`,
496 /// `Reserved(conflicted=false) -> Reserved(conflicted=true)`, and `Active -> Frozen`)
497 /// - all transitions for attempts to deallocate strongly protected tags
498 ///
499 /// # Panics
500 ///
501 /// This function assumes that its arguments apply to the same location
502 /// and that they were obtained during a normal execution. It will panic otherwise.
503 /// - all transitions involved in `self` and `err` should be increasing
504 /// (Reserved < Active < Frozen < Disabled);
505 /// - between `self` and `err` the permission should also be increasing,
506 /// so all permissions inside `err` should be greater than `self.1`;
507 /// - `Active`, `Reserved(conflicted=false)`, and `Cell` cannot cause an error
508 /// due to insufficient permissions, so `err` cannot be a `ChildAccessForbidden(_)`
509 /// of either of them;
510 /// - `err` should not be `ProtectedDisabled(Disabled)`, because the protected
511 /// tag should not have been `Disabled` in the first place (if this occurs it means
512 /// we have unprotected tags that become protected)
513 pub(in super::super) fn is_relevant(&self, err: TransitionError) -> bool {
514 // NOTE: `super::super` is the visibility of `TransitionError`
515 assert!(self.is_possible());
516 if self.is_noop() {
517 return false;
518 }
519 match err {
520 TransitionError::ChildAccessForbidden(insufficient) => {
521 // Show where the permission was gained then lost,
522 // but ignore unrelated permissions.
523 // This eliminates transitions like `Active -> Frozen`
524 // when the error is a failed `Read`.
525 match (self.to, insufficient.inner) {
526 (Frozen, Frozen) => true,
527 (Active, Frozen) => true,
528 (Disabled, Disabled) => true,
529 (
530 ReservedFrz { conflicted: true, .. },
531 ReservedFrz { conflicted: true, .. },
532 ) => true,
533 // A pointer being `Disabled` is a strictly stronger source of
534 // errors than it being `Frozen`. If we try to access a `Disabled`,
535 // then where it became `Frozen` (or `Active` or `Reserved`) is the least
536 // of our concerns for now.
537 (ReservedFrz { conflicted: true } | Active | Frozen, Disabled) => false,
538 (ReservedFrz { conflicted: true }, Frozen) => false,
539
540 // `Active`, `Reserved`, and `Cell` have all permissions, so a
541 // `ChildAccessForbidden(Reserved | Active)` can never exist.
542 (_, Active) | (_, ReservedFrz { conflicted: false }) | (_, Cell) =>
543 unreachable!("this permission cannot cause an error"),
544 // No transition has `Reserved { conflicted: false }` or `ReservedIM`
545 // as its `.to` unless it's a noop. `Cell` cannot be in its `.to`
546 // because all child accesses are a noop.
547 (ReservedFrz { conflicted: false } | ReservedIM | Cell, _) =>
548 unreachable!("self is a noop transition"),
549 // All transitions produced in normal executions (using `apply_access`)
550 // change permissions in the order `Reserved -> Active -> Frozen -> Disabled`.
551 // We assume that the error was triggered on the same location that
552 // the transition `self` applies to, so permissions found must be increasing
553 // in the order `self.from < self.to <= insufficient.inner`
554 (Active | Frozen | Disabled, ReservedFrz { .. } | ReservedIM)
555 | (Disabled, Frozen)
556 | (ReservedFrz { .. }, ReservedIM) =>
557 unreachable!("permissions between self and err must be increasing"),
558 }
559 }
560 TransitionError::ProtectedDisabled(before_disabled) => {
561 // Show how we got to the starting point of the forbidden transition,
562 // but ignore what came before.
563 // This eliminates transitions like `Reserved -> Active`
564 // when the error is a `Frozen -> Disabled`.
565 match (self.to, before_disabled.inner) {
566 // We absolutely want to know where it was activated/frozen/marked
567 // conflicted.
568 (Active, Active) => true,
569 (Frozen, Frozen) => true,
570 (
571 ReservedFrz { conflicted: true, .. },
572 ReservedFrz { conflicted: true, .. },
573 ) => true,
574 // If the error is a transition `Frozen -> Disabled`, then we don't really
575 // care whether before that was `Reserved -> Active -> Frozen` or
576 // `Frozen` directly.
577 // The error will only show either
578 // - created as Reserved { conflicted: false },
579 // then Reserved { .. } -> Disabled is forbidden
580 // - created as Reserved { conflicted: false },
581 // then Active -> Disabled is forbidden
582 // A potential `Reserved { conflicted: false }
583 // -> Reserved { conflicted: true }` is inexistant or irrelevant,
584 // and so is the `Reserved { conflicted: false } -> Active`
585 (Active, Frozen) => false,
586 (ReservedFrz { conflicted: true }, _) => false,
587
588 (_, Disabled) =>
589 unreachable!(
590 "permission that results in Disabled should not itself be Disabled in the first place"
591 ),
592 // No transition has `Reserved { conflicted: false }` or `ReservedIM` as its `.to`
593 // unless it's a noop. `Cell` cannot be in its `.to` because all child
594 // accesses are a noop.
595 (ReservedFrz { conflicted: false } | ReservedIM | Cell, _) =>
596 unreachable!("self is a noop transition"),
597
598 // Permissions only evolve in the order `Reserved -> Active -> Frozen -> Disabled`,
599 // so permissions found must be increasing in the order
600 // `self.from < self.to <= forbidden.from < forbidden.to`.
601 (Disabled, Cell | ReservedFrz { .. } | ReservedIM | Active | Frozen)
602 | (Frozen, Cell | ReservedFrz { .. } | ReservedIM | Active)
603 | (Active, Cell | ReservedFrz { .. } | ReservedIM) =>
604 unreachable!("permissions between self and err must be increasing"),
605 }
606 }
607 // We don't care because protectors evolve independently from
608 // permissions.
609 TransitionError::ProtectedDealloc => false,
610 }
611 }
612
613 /// Endpoint of a transition.
614 /// Meant only for diagnostics, use `applied` in non-diagnostics
615 /// code, which also checks that the starting point matches the current state.
616 pub fn endpoint(&self) -> Permission {
617 Permission { inner: self.to }
618 }
619 }
620}
621
622#[cfg(test)]
623impl Permission {
624 pub fn is_reserved_frz_with_conflicted(&self, expected_conflicted: bool) -> bool {
625 match self.inner {
626 ReservedFrz { conflicted } => conflicted == expected_conflicted,
627 _ => false,
628 }
629 }
630}
631
632#[cfg(test)]
633mod propagation_optimization_checks {
634 pub use super::*;
635 use crate::borrow_tracker::tree_borrows::exhaustive::{Exhaustive, precondition};
636
637 impl Exhaustive for PermissionPriv {
638 fn exhaustive() -> Box<dyn Iterator<Item = Self>> {
639 Box::new(
640 vec![Active, Frozen, Disabled, ReservedIM, Cell]
641 .into_iter()
642 .chain(<bool>::exhaustive().map(|conflicted| ReservedFrz { conflicted })),
643 )
644 }
645 }
646
647 impl Exhaustive for Permission {
648 fn exhaustive() -> Box<dyn Iterator<Item = Self>> {
649 Box::new(PermissionPriv::exhaustive().map(|inner| Self { inner }))
650 }
651 }
652
653 impl Exhaustive for AccessKind {
654 fn exhaustive() -> Box<dyn Iterator<Item = Self>> {
655 use AccessKind::*;
656 Box::new(vec![Read, Write].into_iter())
657 }
658 }
659
660 impl Exhaustive for AccessRelatedness {
661 fn exhaustive() -> Box<dyn Iterator<Item = Self>> {
662 use AccessRelatedness::*;
663 Box::new(vec![This, StrictChildAccess, AncestorAccess, CousinAccess].into_iter())
664 }
665 }
666
667 #[test]
668 // For any kind of access, if we do it twice the second should be a no-op.
669 // Even if the protector has disappeared.
670 fn all_transitions_idempotent() {
671 use transition::*;
672 for old in PermissionPriv::exhaustive() {
673 for (old_protected, new_protected) in <(bool, bool)>::exhaustive() {
674 // Protector can't appear out of nowhere: either the permission was
675 // created with a protector (`old_protected = true`) and it then may
676 // or may not lose it (`new_protected = false`, resp. `new_protected = true`),
677 // or it didn't have one upon creation and never will
678 // (`old_protected = new_protected = false`).
679 // We thus eliminate from this test and all other tests
680 // the case where the tag is initially unprotected and later becomes protected.
681 precondition!(old_protected || !new_protected);
682 if old_protected {
683 precondition!(old.compatible_with_protector());
684 }
685 for (access, rel_pos) in <(AccessKind, AccessRelatedness)>::exhaustive() {
686 if let Some(new) = perform_access(access, rel_pos, old, old_protected) {
687 assert_eq!(
688 new,
689 perform_access(access, rel_pos, new, new_protected).unwrap()
690 );
691 }
692 }
693 }
694 }
695 }
696
697 #[test]
698 #[rustfmt::skip]
699 fn foreign_read_is_noop_after_foreign_write() {
700 use transition::*;
701 let old_access = AccessKind::Write;
702 let new_access = AccessKind::Read;
703 for old in PermissionPriv::exhaustive() {
704 for [old_protected, new_protected] in <[bool; 2]>::exhaustive() {
705 precondition!(old_protected || !new_protected);
706 if old_protected {
707 precondition!(old.compatible_with_protector());
708 }
709 for rel_pos in AccessRelatedness::exhaustive() {
710 precondition!(rel_pos.is_foreign());
711 if let Some(new) = perform_access(old_access, rel_pos, old, old_protected) {
712 assert_eq!(
713 new,
714 perform_access(new_access, rel_pos, new, new_protected).unwrap()
715 );
716 }
717 }
718 }
719 }
720 }
721
722 #[test]
723 #[rustfmt::skip]
724 fn permission_sifa_is_correct() {
725 // Tests that `strongest_idempotent_foreign_access` is correct. See `foreign_access_skipping.rs`.
726 for perm in PermissionPriv::exhaustive() {
727 // Assert that adding a protector makes it less idempotent.
728 if perm.compatible_with_protector() {
729 assert!(perm.strongest_idempotent_foreign_access(true) <= perm.strongest_idempotent_foreign_access(false));
730 }
731 for prot in bool::exhaustive() {
732 if prot {
733 precondition!(perm.compatible_with_protector());
734 }
735 let access = perm.strongest_idempotent_foreign_access(prot);
736 // We now assert it is idempotent, and never causes UB.
737 // First, if the SIFA includes foreign reads, assert it is idempotent under foreign reads.
738 if access >= IdempotentForeignAccess::Read {
739 // We use `CousinAccess` here. We could also use `AncestorAccess`, since `transition::perform_access` treats these the same.
740 // The only place they are treated differently is in protector end accesses, but these are not handled here.
741 assert_eq!(perm, transition::perform_access(AccessKind::Read, AccessRelatedness::CousinAccess, perm, prot).unwrap());
742 }
743 // Then, if the SIFA includes foreign writes, assert it is idempotent under foreign writes.
744 if access >= IdempotentForeignAccess::Write {
745 assert_eq!(perm, transition::perform_access(AccessKind::Write, AccessRelatedness::CousinAccess, perm, prot).unwrap());
746 }
747 }
748 }
749 }
750
751 #[test]
752 // Check that all transitions are consistent with the order on PermissionPriv,
753 // i.e. Reserved -> Active -> Frozen -> Disabled
754 fn permissionpriv_partialord_is_reachability() {
755 let reach = {
756 let mut reach = rustc_data_structures::fx::FxHashSet::default();
757 // One-step transitions + reflexivity
758 for start in PermissionPriv::exhaustive() {
759 reach.insert((start, start));
760 for (access, rel) in <(AccessKind, AccessRelatedness)>::exhaustive() {
761 for prot in bool::exhaustive() {
762 if prot {
763 precondition!(start.compatible_with_protector());
764 }
765 if let Some(end) = transition::perform_access(access, rel, start, prot) {
766 reach.insert((start, end));
767 }
768 }
769 }
770 }
771 // Transitive closure
772 let mut finished = false;
773 while !finished {
774 finished = true;
775 for [start, mid, end] in <[PermissionPriv; 3]>::exhaustive() {
776 if reach.contains(&(start, mid))
777 && reach.contains(&(mid, end))
778 && !reach.contains(&(start, end))
779 {
780 finished = false;
781 reach.insert((start, end));
782 }
783 }
784 }
785 reach
786 };
787 // Check that it matches `<`
788 for [p1, p2] in <[PermissionPriv; 2]>::exhaustive() {
789 let le12 = p1 <= p2;
790 let reach12 = reach.contains(&(p1, p2));
791 assert!(
792 le12 == reach12,
793 "`{p1} reach {p2}` ({reach12}) does not match `{p1} <= {p2}` ({le12})"
794 );
795 }
796 }
797}