openvmm: accepted state-unit dependency cycles hang lifecycle operations past their timeout

UnitBuilder::build accepts edges that close a dependency cycle. Ordered lifecycle operations then have no ready unit to dispatch and can wait indefinitely, including during snapshot quiescence.

In vmm_core/state_unit/src/lib.rs, construction installs both sets of requested edges without checking whether their combination creates a cycle:

            for &dep in &self.dependencies {
                inner.units.get_mut(&dep).unwrap().dependents.insert(id);
            }

            for &dep in &self.dependents {
                inner.units.get_mut(&dep).unwrap().dependencies.insert(id);
            }

For depends_on(&a).dependency_of(&a), the new unit depends on a and a depends on the new unit. An existing dependency path can produce the same cycle indirectly. ReadySet::wait is outside the operation's cancellation future, so the operation timeout does not release a graph in which no unit can become ready.

Trigger

Create unit a, then build x with both depends_on(&a) and dependency_of(&a). Starting the set cannot select its first ready unit. Inserting a cycle into an existing running set can similarly hang quiescence. Normal microVM construction does not create these reciprocal edges.

Fix

Before modifying the inventory, walk existing dependency paths under the inventory lock. Reject the insertion if a requested dependency reaches a requested dependent.

The complete builder-validation patch also rejects removed references before mutation. It is shared with the partial-registration fix and should be applied once.

Proposed patch

Patch against OpenVMM 998b9f2402050cd16d1faa897bc831ef1434be48. Save the contents below as fix.patch and run git apply fix.patch.

fix.patch

diff --git a/vmm_core/state_unit/src/lib.rs b/vmm_core/state_unit/src/lib.rs
index c7081c995..5e5ff4377 100644
--- a/vmm_core/state_unit/src/lib.rs
+++ b/vmm_core/state_unit/src/lib.rs
@@ -55,7 +55,6 @@
 use std::collections::BTreeMap;
 use std::collections::BTreeSet;
 use std::collections::HashMap;
-use std::collections::hash_map;
 use std::fmt::Debug;
 use std::fmt::Display;
 use std::future::Future;
@@ -287,10 +286,22 @@ struct Unit {
     advances_time: bool,
 }
 
-/// An error returned when a state unit name is already in use.
+/// An error returned when a state unit cannot be added.
 #[derive(Debug, Error)]
-#[error("state unit name {0} is in use")]
-pub struct NameInUse(Arc<str>);
+pub enum UnitBuildError {
+    /// The name is already registered.
+    #[error("state unit name {0} is in use")]
+    NameInUse(Arc<str>),
+    /// A referenced unit was removed before construction completed.
+    #[error("state unit {0} references a removed dependency")]
+    MissingDependency(Arc<str>),
+    /// The requested dependency edges would close a cycle.
+    #[error("state unit {0} would create a dependency cycle")]
+    DependencyCycle(Arc<str>),
+}
+
+/// Compatibility name for the error returned by state unit builders.
+pub type NameInUse = UnitBuildError;
 
 #[derive(Debug, Error)]
 #[error("critical unit communication failure: {name}")]
@@ -941,15 +952,37 @@ fn handle_id(&self, handle: &UnitHandle) -> u64 {
     }
 
     /// Adds a new state unit sending requests to `send`.
+    ///
+    /// Rejects removed dependencies and dependency cycles without changing the
+    /// unit inventory.
     pub fn build(self, send: Sender<StateRequest>) -> Result<UnitHandle, NameInUse> {
         let id = {
             let mut inner = self.units.inner.lock();
             let id = inner.next_id;
-            let entry = match inner.names.entry(self.name.clone()) {
-                hash_map::Entry::Occupied(_) => return Err(NameInUse(self.name)),
-                hash_map::Entry::Vacant(e) => e,
-            };
-            entry.insert(id);
+            if inner.names.contains_key(&self.name) {
+                return Err(UnitBuildError::NameInUse(self.name));
+            }
+            if self
+                .dependencies
+                .iter()
+                .chain(&self.dependents)
+                .any(|dep| !inner.units.contains_key(dep))
+            {
+                return Err(UnitBuildError::MissingDependency(self.name));
+            }
+            let mut pending: Vec<_> = self.dependencies.iter().copied().collect();
+            let mut visited = BTreeSet::new();
+            while let Some(dep) = pending.pop() {
+                if !visited.insert(dep) {
+                    continue;
+                }
+                if self.dependents.contains(&dep) {
+                    return Err(UnitBuildError::DependencyCycle(self.name));
+                }
+                pending.extend(inner.units[&dep].dependencies.iter().copied());
+            }
+
+            inner.names.insert(self.name.clone(), id);
 
             for &dep in &self.dependencies {
                 inner.units.get_mut(&dep).unwrap().dependents.insert(id);
@@ -1375,6 +1408,61 @@ fn test_duplicate_dependency_edges() {
         assert_no_dangling_edges(&inner);
     }
 
+    #[test]
+    fn removed_dependencies_do_not_partially_register_a_unit() {
+        for reverse in [false, true] {
+            let units = StateUnits::new();
+            let a = units.add("a").build(mesh::channel().0).unwrap();
+            let b = units.add("b").build(mesh::channel().0).unwrap();
+            let builder = units.add("x").depends_on(&a);
+            let builder = if reverse {
+                builder.dependency_of(&b)
+            } else {
+                builder.depends_on(&b)
+            };
+            drop(b);
+            assert!(builder.build(mesh::channel().0).is_err());
+            {
+                let inner = units.inner.lock();
+                assert!(!inner.names.contains_key("x"));
+                assert!(inner.units[&a.id.id].dependents.is_empty());
+                assert_no_dangling_edges(&inner);
+            }
+            let y = units.add("y").build(mesh::channel().0).unwrap();
+            let x = units.add("x").build(mesh::channel().0).unwrap();
+            assert_ne!(x.id.id, y.id.id);
+        }
+    }
+
+    #[test]
+    fn dependency_cycles_are_rejected_before_registration() {
+        let units = StateUnits::new();
+        let a = units.add("a").build(mesh::channel().0).unwrap();
+        let b = units
+            .add("b")
+            .depends_on(&a)
+            .build(mesh::channel().0)
+            .unwrap();
+        for dependency in [&a, &b] {
+            assert!(
+                units
+                    .add("x")
+                    .depends_on(dependency)
+                    .dependency_of(&a)
+                    .build(mesh::channel().0)
+                    .is_err()
+            );
+            assert!(!units.inner.lock().names.contains_key("x"));
+        }
+        let _x = units
+            .add("x")
+            .depends_on(&a)
+            .dependency_of(&b)
+            .build(mesh::channel().0)
+            .unwrap();
+        assert_no_dangling_edges(&units.inner.lock());
+    }
+
     /// Removing a unit must prune the reverse dependency edges that `build`
     /// created, so no remaining unit references the removed unit's id.
     /// Regression test for a panic ("no entry found for key") when inspecting

state_unit: reject dependency cycles when a unit is added

Navigation Menu

Repository navigation

openvmm: accepted state-unit dependency cycles hang lifecycle operations past their timeout #1155

Trigger

Fix

Proposed patch

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

openvmm: accepted state-unit dependency cycles hang lifecycle operations past their timeout #1155

Description

Trigger

Fix

Activity

tangruize commented on Nov 1, 2026

Proposed patch

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions