[PATCH proxmox-ve-rs v3 05/45] ve-config: sdn: microseg: add identity allocation for group sets

[Hannes Laimer <h.laimer@proxmox.com>]

A guest interface carries a set of groups, but the wire has room for a
single 16-bit id. Group sets that no rule can tell apart form one
class with one id. So the ids in use grow with what the rules
distinguish, not with the number of distinct group sets.

An id is stamped on one host and may be looked up on another after a
config change. Reusing it for an unrelated class could give a packet
still in flight the wrong verdict. So a class keeps its id while it
exists. A new class takes an id never issued before. Once every id has
been issued, an id unused for an hour can be issued again. Without one
the allocation fails.

Signed-off-by: Hannes Laimer <h.laimer@proxmox.com>
---
 .../src/sdn/microseg/identity.rs              | 459 ++++++++++++++++++
 proxmox-ve-config/src/sdn/microseg/mod.rs     |   9 +
 proxmox-ve-config/src/sdn/mod.rs              |   1 +
 3 files changed, 469 insertions(+)
 create mode 100644 proxmox-ve-config/src/sdn/microseg/identity.rs
 create mode 100644 proxmox-ve-config/src/sdn/microseg/mod.rs

diff --git a/proxmox-ve-config/src/sdn/microseg/identity.rs b/proxmox-ve-config/src/sdn/microseg/identity.rs
new file mode 100644
index 000000000000..24e91402070e
--- /dev/null
+++ b/proxmox-ve-config/src/sdn/microseg/identity.rs
@@ -0,0 +1,459 @@
+//! Signature-based identity allocation for microseg.
+//!
+//! An *identity* is not one group set but a class of group sets that no policy can tell apart. Two
+//! sets share an id when every policy's src and dst predicate fires the same way on both. The class
+//! carries an *id* that is stamped on the wire, and a *representative*, the smallest member set in
+//! sort order. A later split or merge therefore keeps the same survivor, and the ids stay stable.
+//!
+//! Allocation is **fresh-first**. A packet stamped with a number can still be in flight when the
+//! config changes, and rebinding the number to an unrelated class could give it the wrong verdict.
+//! Ids therefore come from a counter that only increases, and a split issues fresh ones. An id no
+//! class carries any more, after a merge or once its sets left the config, retires into a
+//! time-based quarantine (`RETIRE_QUARANTINE_SECS`). Once the counter has issued every number,
+//! allocation reclaims the lowest number whose quarantine has passed. It fails only with all 65535
+//! numbers live or quarantined at the same time.
+
+use std::collections::{BTreeMap, BTreeSet, HashMap};
+
+use serde::{Deserialize, Deserializer, Serialize};
+
+use proxmox_schema::api;
+
+/// The group set assigned to an interface. `BTreeSet`'s `Ord` compares the sorted elements in
+/// order, which is exactly the representative order.
+pub(crate) type GroupSet = BTreeSet<String>;
+
+/// The reserved name of the built-in *untagged* group, the no-group identity. A source predicate
+/// names it to match unstamped traffic, such as gateway, DHCP and ARP replies or cross-node frames
+/// without a GBP tag. It can stand next to real groups, as in `any{untagged, web}`. It is not a
+/// stored group and cannot be used in an assignment.
+pub(crate) const UNTAGGED_GROUP: &str = "untagged";
+
+/// An unstamped frame reads as this id. It is never issued to a class, so a real group set
+/// (even one no policy matches) never collides with it and never inherits its `untagged`
+/// allows. Its representative in the rule fold is the built-in `untagged` group.
+pub(crate) const UNTAGGED_ID: u16 = 0;
+
+/// Reusing a number is only safe once no packet stamped under its old meaning can still exist. The
+/// generous margin also covers nodes that apply a render late. A node cut off from pmxcfs for
+/// longer than this while still passing traffic keeps stamping ids that may by then name another
+/// class. A cluster in that state is broken in worse ways.
+const RETIRE_QUARANTINE_SECS: u64 = 60 * 60;
+
+#[api()]
+#[derive(Debug, Clone, Copy, Default, Serialize, Deserialize, PartialEq, Eq)]
+#[serde(rename_all = "lowercase")]
+/// How a match compares the listed items with the present ones.
+pub enum PredicateMatch {
+    /// Fires when at least one listed item is present.
+    #[default]
+    Any,
+    /// Fires when every listed item is present.
+    All,
+    /// Fires only when the present items are exactly the listed ones.
+    Exact,
+    /// Fires on every set holding a group, nothing is listed.
+    Every,
+}
+
+/// A predicate over group names, the src or dst half of a policy.
+/// Validation refuses an empty `groups` except for `Every`, which lists nothing and never fires
+/// on the untagged identity.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct Predicate {
+    pub(crate) kind: PredicateMatch,
+    pub(crate) groups: GroupSet,
+}
+
+impl Predicate {
+    pub(crate) fn fires(&self, set: &GroupSet) -> bool {
+        match self.kind {
+            PredicateMatch::Any => self.groups.intersection(set).next().is_some(),
+            PredicateMatch::All => self.groups.is_subset(set),
+            PredicateMatch::Exact => &self.groups == set,
+            PredicateMatch::Every => set.iter().any(|group| group != UNTAGGED_GROUP),
+        }
+    }
+}
+
+/// The verdict is not part of identity, it lives in the fold.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct Policy {
+    pub(crate) src: Predicate,
+    pub(crate) dst: Predicate,
+}
+
+/// How a set fires against each policy in order, as `[p0.src, p0.dst, p1.src, ...]`. Only equality
+/// matters, sets with equal signatures get the same verdicts. Signatures compare only under one
+/// policy order.
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub(crate) struct Signature(Vec<bool>);
+
+pub(crate) fn signature(set: &GroupSet, policies: &[Policy]) -> Signature {
+    let mut bits = Vec::with_capacity(policies.len() * 2);
+    for policy in policies {
+        bits.push(policy.src.fires(set));
+        bits.push(policy.dst.fires(set));
+    }
+    Signature(bits)
+}
+
+/// How much of the id space a registry uses. A retired id whose quarantine has passed is counted
+/// until the next allocation drops it.
+#[derive(Debug, Serialize)]
+pub struct IdSpace {
+    pub used: usize,
+    pub retired: usize,
+    /// Every id but the one untagged traffic carries.
+    pub total: usize,
+}
+
+/// Each live id with its representative set, plus the id counter. Only which id each class
+/// carries is kept, the classes themselves come from the policies. Serialized into the running
+/// config so every host reads the same id-to-class naming.
+#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
+pub struct Registry {
+    next: u16,
+    #[serde(deserialize_with = "int_keys")]
+    classes: BTreeMap<u16, GroupSet>,
+    /// Retired id to unix time of retirement. Entries whose quarantine has passed are dropped by
+    /// the next [`allocate`].
+    #[serde(
+        default,
+        deserialize_with = "int_keys",
+        skip_serializing_if = "BTreeMap::is_empty"
+    )]
+    retired: BTreeMap<u16, u64>,
+}
+
+/// A round trip through perlmod hands integer map keys back as strings, which serde does not
+/// accept for a u16 key.
+fn int_keys<'de, D: Deserializer<'de>, V: Deserialize<'de>>(
+    deserializer: D,
+) -> Result<BTreeMap<u16, V>, D::Error> {
+    BTreeMap::<String, V>::deserialize(deserializer)?
+        .into_iter()
+        .map(|(key, value)| {
+            key.parse::<u16>()
+                .map(|key| (key, value))
+                .map_err(serde::de::Error::custom)
+        })
+        .collect()
+}
+
+impl Default for Registry {
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl Registry {
+    /// Ids start at 1, since 0 is the untagged id.
+    pub(crate) fn new() -> Self {
+        Self {
+            next: 1,
+            classes: BTreeMap::new(),
+            retired: BTreeMap::new(),
+        }
+    }
+
+    pub fn classes(&self) -> &BTreeMap<u16, GroupSet> {
+        &self.classes
+    }
+
+    pub fn id_space(&self) -> IdSpace {
+        IdSpace {
+            used: self.classes.len(),
+            retired: self.retired.len(),
+            total: u16::MAX as usize,
+        }
+    }
+}
+
+/// Recompute the registry from the sets the assignments name and the policies, fresh-first against
+/// `prev`.
+///
+/// Sets with the same signature form a class. Each class keeps the id of the previous class whose
+/// representative still lands in it. A merge keeps the id of the smallest representative and
+/// retires the rest. The sets no policy matches share the all-false signature and form one class
+/// with its own id, distinct from `UNTAGGED_ID`. `now` is the render time (unix seconds) the
+/// quarantine runs on.
+pub fn allocate(
+    prev: &Registry,
+    sets: &BTreeSet<GroupSet>,
+    policies: &[Policy],
+    now: u64,
+) -> anyhow::Result<Registry> {
+    // The sets arrive in ascending order, so the first set seen with a signature is the class's
+    // representative and the classes come out in representative order. That order decides which
+    // class gets which fresh number, so the same input issues the same numbers.
+    let mut class_of: HashMap<Signature, usize> = HashMap::new();
+    let mut reps: Vec<&GroupSet> = Vec::new();
+    for set in sets {
+        class_of.entry(signature(set, policies)).or_insert_with(|| {
+            reps.push(set);
+            reps.len() - 1
+        });
+    }
+
+    let mut claims: Vec<Option<(u16, &GroupSet)>> = vec![None; reps.len()];
+    for (&id, rep) in &prev.classes {
+        let Some(&class) = class_of.get(&signature(rep, policies)) else {
+            continue;
+        };
+        if claims[class].is_none_or(|(_, best)| rep < best) {
+            claims[class] = Some((id, rep));
+        }
+    }
+
+    let mut retired: BTreeMap<u16, u64> = prev
+        .retired
+        .iter()
+        .filter(|&(_, &at)| now.saturating_sub(at) < RETIRE_QUARANTINE_SECS)
+        .map(|(&id, &at)| (id, at))
+        .collect();
+
+    let mut next = prev.next;
+    let mut classes = BTreeMap::new();
+    for (rep, claim) in reps.into_iter().zip(claims) {
+        let id = match claim {
+            Some((id, _)) => id,
+            None => {
+                // the counter wrapped to 0, so the fresh space is used up
+                if next == UNTAGGED_ID {
+                    reclaim(prev, &retired, &classes)?
+                } else {
+                    let id = next;
+                    next = next.wrapping_add(1);
+                    id
+                }
+            }
+        };
+        classes.insert(id, rep.clone());
+    }
+
+    for &id in prev.classes.keys() {
+        if !classes.contains_key(&id) {
+            retired.insert(id, now);
+        }
+    }
+
+    Ok(Registry {
+        next,
+        classes,
+        retired,
+    })
+}
+
+/// Called with the fresh space used up, so a number free here was retired and has left its
+/// quarantine. An id that was live until this pass may still be on the wire, so it is kept like one
+/// in quarantine.
+fn reclaim(
+    prev: &Registry,
+    quarantined: &BTreeMap<u16, u64>,
+    taken: &BTreeMap<u16, GroupSet>,
+) -> anyhow::Result<u16> {
+    (1..=u16::MAX)
+        .find(|id| {
+            !prev.classes.contains_key(id)
+                && !quarantined.contains_key(id)
+                && !taken.contains_key(id)
+        })
+        .ok_or_else(|| {
+            anyhow::anyhow!(
+                "microseg identity id space exhausted \
+                 (all 65535 ids are live or recently retired)"
+            )
+        })
+}
+
+#[cfg(test)]
+mod tests {
+    use super::PredicateMatch::*;
+    use super::*;
+
+    fn set(xs: &[&str]) -> GroupSet {
+        xs.iter().map(|x| x.to_string()).collect()
+    }
+
+    fn pred(kind: PredicateMatch, xs: &[&str]) -> Predicate {
+        Predicate {
+            kind,
+            groups: set(xs),
+        }
+    }
+
+    fn id_of(reg: &Registry, set: &GroupSet, policies: &[Policy]) -> Option<u16> {
+        let sig = signature(set, policies);
+        reg.classes
+            .iter()
+            .find(|(_, rep)| signature(rep, policies) == sig)
+            .map(|(&id, _)| id)
+    }
+
+    fn sets(xs: &[&[&str]]) -> BTreeSet<GroupSet> {
+        xs.iter().map(|s| set(s)).collect()
+    }
+
+    #[test]
+    fn unmatched_set_gets_its_own_id_not_the_untagged_id() {
+        let policies = [Policy {
+            src: pred(Any, &["untagged"]),
+            dst: pred(Any, &["b"]),
+        }];
+        let reg = allocate(&Registry::new(), &sets(&[&["e"]]), &policies, 0).unwrap();
+
+        let id = id_of(&reg, &set(&["e"]), &policies).expect("an unmatched set still has a class");
+        assert_ne!(
+            id, UNTAGGED_ID,
+            "an unmatched set must not alias onto the untagged id"
+        );
+
+        let reg = allocate(&Registry::new(), &sets(&[&["e"], &["f"]]), &policies, 0).unwrap();
+        assert_eq!(
+            reg.classes().len(),
+            1,
+            "all unmatched sets collapse to one class"
+        );
+        assert_eq!(
+            id_of(&reg, &set(&["e"]), &policies),
+            id_of(&reg, &set(&["f"]), &policies)
+        );
+    }
+
+    #[test]
+    fn split_keeps_old_rep_subclass_id_and_issues_the_other() {
+        let p1 = [Policy {
+            src: pred(Any, &["b"]),
+            dst: pred(Any, &["i"]),
+        }];
+        let r1 = allocate(&Registry::new(), &sets(&[&["b", "c"], &["b", "d"]]), &p1, 0).unwrap();
+        assert_eq!(id_of(&r1, &set(&["b", "c"]), &p1), Some(1));
+        assert_eq!(id_of(&r1, &set(&["b", "d"]), &p1), Some(1));
+
+        // then EXACT{b,c} is added, which fires only on {b,c}, so the class splits
+        let p2 = [
+            Policy {
+                src: pred(Any, &["b"]),
+                dst: pred(Any, &["i"]),
+            },
+            Policy {
+                src: pred(Exact, &["b", "c"]),
+                dst: pred(Any, &["i"]),
+            },
+        ];
+        let r2 = allocate(&r1, &sets(&[&["b", "c"], &["b", "d"]]), &p2, 0).unwrap();
+
+        assert_eq!(
+            id_of(&r2, &set(&["b", "c"]), &p2),
+            Some(1),
+            "old-rep subclass keeps the id"
+        );
+        assert_eq!(
+            id_of(&r2, &set(&["b", "d"]), &p2),
+            Some(2),
+            "the other subclass issues fresh"
+        );
+        assert_eq!(r2.next, 3);
+    }
+
+    #[test]
+    fn merge_retires_the_fused_id_and_prefers_fresh() {
+        let p_split = [
+            Policy {
+                src: pred(Any, &["b"]),
+                dst: pred(Any, &["i"]),
+            },
+            Policy {
+                src: pred(Exact, &["b", "c"]),
+                dst: pred(Any, &["i"]),
+            },
+        ];
+        let r_split = allocate(
+            &Registry::new(),
+            &sets(&[&["b", "c"], &["b", "d"]]),
+            &p_split,
+            0,
+        )
+        .unwrap();
+        assert_eq!(id_of(&r_split, &set(&["b", "c"]), &p_split), Some(1));
+        assert_eq!(id_of(&r_split, &set(&["b", "d"]), &p_split), Some(2));
+        assert_eq!(r_split.next, 3);
+
+        // Drop the distinguisher, so {b,c} and {b,d} merge.
+        let p_merge = [Policy {
+            src: pred(Any, &["b"]),
+            dst: pred(Any, &["i"]),
+        }];
+        let r_merge = allocate(&r_split, &sets(&[&["b", "c"], &["b", "d"]]), &p_merge, 0).unwrap();
+        assert_eq!(id_of(&r_merge, &set(&["b", "c"]), &p_merge), Some(1));
+        assert_eq!(
+            id_of(&r_merge, &set(&["b", "d"]), &p_merge),
+            Some(1),
+            "merged into the survivor"
+        );
+        assert!(!r_merge.classes().contains_key(&2), "id 2 is retired");
+        assert_eq!(r_merge.retired.get(&2), Some(&0), "id 2 is quarantined");
+        assert_eq!(r_merge.next, 3, "the counter never rewinds");
+
+        let r_next = allocate(
+            &r_merge,
+            &sets(&[&["b", "c"], &["b", "d"], &["i"]]),
+            &p_merge,
+            0,
+        )
+        .unwrap();
+        assert_eq!(
+            id_of(&r_next, &set(&["i"]), &p_merge),
+            Some(3),
+            "new class skips the retired id"
+        );
+    }
+
+    fn exhausted_registry(retired_id: u16, retired_at: u64, free_id: u16) -> Registry {
+        let classes: BTreeMap<u16, GroupSet> = (1..=u16::MAX)
+            .filter(|&id| id != retired_id && id != free_id)
+            .map(|id| (id, set(&[&id.to_string()])))
+            .collect();
+        Registry {
+            next: 0,
+            classes,
+            retired: BTreeMap::from([(retired_id, retired_at)]),
+        }
+    }
+
+    #[test]
+    fn reclaims_a_retired_id_only_after_its_quarantine() {
+        // {b,e} fires both src predicates, no singleton does, so no previous class claims it and it
+        // needs an id with no fresh space left.
+        let policies = [
+            Policy {
+                src: pred(Any, &["b"]),
+                dst: pred(Any, &["i"]),
+            },
+            Policy {
+                src: pred(Any, &["e"]),
+                dst: pred(Any, &["i"]),
+            },
+        ];
+        let retired_at = 1_000;
+        let prev = exhausted_registry(7, retired_at, 11);
+
+        // one number is free outright, so the first issued id takes it regardless of the quarantine
+        let reg = allocate(&prev, &sets(&[&["b", "e"]]), &policies, retired_at + 1).unwrap();
+        assert_eq!(id_of(&reg, &set(&["b", "e"]), &policies), Some(11));
+
+        // with 11 also live, the only candidate is the quarantined 7. Inside the quarantine
+        // issuing must fail rather than rebind a number packets may still carry
+        let mut prev = exhausted_registry(7, retired_at, 11);
+        prev.classes.insert(11, set(&["11"]));
+        let before = retired_at + RETIRE_QUARANTINE_SECS - 1;
+        let err = allocate(&prev, &sets(&[&["b", "e"]]), &policies, before).unwrap_err();
+        assert!(err.to_string().contains("exhausted"), "got: {err:#}");
+
+        let after = retired_at + RETIRE_QUARANTINE_SECS;
+        let reg = allocate(&prev, &sets(&[&["b", "e"]]), &policies, after).unwrap();
+        assert_eq!(id_of(&reg, &set(&["b", "e"]), &policies), Some(7));
+        assert!(!reg.retired.contains_key(&7));
+    }
+}
diff --git a/proxmox-ve-config/src/sdn/microseg/mod.rs b/proxmox-ve-config/src/sdn/microseg/mod.rs
new file mode 100644
index 000000000000..37c4f92ff0c8
--- /dev/null
+++ b/proxmox-ve-config/src/sdn/microseg/mod.rs
@@ -0,0 +1,9 @@
+//! Microseg subsystem of the SDN config.
+//!
+//! Microseg is an identity-based stateless firewall. Each managed guest NIC is assigned a *set* of
+//! *groups*. The render allocates a wire identity for each set (see [`identity`]), and every host
+//! gets the same ids. Each host looks the identities up and compiles the policy *rules* into a
+//! `(src_id, dst_id) -> allow|deny` map. A rule matches traffic by a `src` and a `dst`
+//! *predicate*, each a match kind over a list of groups.
+
+pub mod identity;
diff --git a/proxmox-ve-config/src/sdn/mod.rs b/proxmox-ve-config/src/sdn/mod.rs
index 2133396145bd..f647e872c636 100644
--- a/proxmox-ve-config/src/sdn/mod.rs
+++ b/proxmox-ve-config/src/sdn/mod.rs
@@ -1,6 +1,7 @@
 pub mod config;
 pub mod fabric;
 pub mod ipam;
+pub mod microseg;
 pub mod prefix_list;
 pub mod route_map;
 pub mod wireguard;
-- 
2.47.3