[PATCH proxmox-ebpf v5 3/5] subsystem: place the links of different subsystems in a fixed order

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

tcx runs the programs on an interface in the order their links were
attached, so without a fixed order the subsystem that sees a packet
first is whichever attached there first. The run order is a list in
the lib. An attach places its link relative to the links the other
subsystems hold on that interface, found through their pins, under
one lock for all subsystems so two attaches to one interface see each
other. Swaps keep a link's slot.

A name missing from the list fails the build instead of landing
somewhere in the chain. A full apply writes the list to /run and an
attach places by the list written last, so a build places its link
right against a subsystem it was not built with, and a release that
adds a subsystem wins over the builds still running.

Signed-off-by: Hannes Laimer <h.laimer@proxmox.com>
---
 src/subsystem.rs | 314 +++++++++++++++++++++++++++++++++++++++++++++--
 src/tc.rs        |  26 ++--
 2 files changed, 323 insertions(+), 17 deletions(-)

diff --git a/src/subsystem.rs b/src/subsystem.rs
index 8233faa31567..977000acc461 100644
--- a/src/subsystem.rs
+++ b/src/subsystem.rs
@@ -13,10 +13,16 @@
 //! single-interface step shared. The holder reads the input of its change under the lock and
 //! writes before it lets go, so a full apply and every step reach the kernel in the order they
 //! read their input. Two steps of one interface do not order each other.
+//!
+//! The programs of different subsystems on one interface run in the order of [`RUN_ORDER`]. A
+//! full apply writes the list to a file under `/run`, and an attach places its link among the
+//! links the other subsystems hold on that interface by the list written last, so a build places
+//! right against subsystems it was not built with. It finds those links through their pins and
+//! does that under a lock all subsystems share, so each attach sees the links pinned before it.
 use std::{
     collections::HashSet,
     fs::File,
-    io::ErrorKind,
+    io::{ErrorKind, Write},
     marker::PhantomData,
     os::unix::fs::{DirBuilderExt, OpenOptionsExt},
     path::{Path, PathBuf},
@@ -24,7 +30,10 @@ use std::{
 };
 
 use anyhow::Context;
-use aya::{EbpfLoader, programs::SchedClassifier};
+use aya::{
+    EbpfLoader,
+    programs::{SchedClassifier, links::LinkOrder},
+};
 use nix::{
     errno::Errno,
     fcntl::{Flock, FlockArg, RenameFlags, renameat2},
@@ -34,6 +43,37 @@ use crate::tc::{self, Direction};
 
 const PIN_ROOT: &str = "/sys/fs/bpf/proxmox-ebpf";
 const RUN_ROOT: &str = "/run/proxmox-ebpf";
+const ORDER_FILE: &str = "order";
+
+/// The subsystems in the order their programs run on an interface, the first runs first. A name
+/// missing from the list fails the build.
+pub const RUN_ORDER: &[&str] = &[];
+
+const fn check_listed(name: &str) {
+    let mut i = 0;
+    while i < RUN_ORDER.len() {
+        if str_eq(RUN_ORDER[i], name) {
+            return;
+        }
+        i += 1;
+    }
+    panic!("subsystem not in RUN_ORDER");
+}
+
+const fn str_eq(a: &str, b: &str) -> bool {
+    let (a, b) = (a.as_bytes(), b.as_bytes());
+    if a.len() != b.len() {
+        return false;
+    }
+    let mut i = 0;
+    while i < a.len() {
+        if a[i] != b[i] {
+            return false;
+        }
+        i += 1;
+    }
+    true
+}
 
 const fn obj_fingerprint(obj: &[u8]) -> u64 {
     let mut hash = 0xcbf29ce484222325u64;
@@ -47,7 +87,9 @@ const fn obj_fingerprint(obj: &[u8]) -> u64 {
 }
 
 /// A subsystem's [`TcPrograms`] from its name. The object is the build's `<name>.bpf.o`, the
-/// fingerprint follows from the bytes.
+/// fingerprint follows from the bytes. `programs` names the object's program per direction, one
+/// entry each, `maps` names its pinned maps, and `schema_version` goes up with any change to a
+/// map's key or value layout, so no build writes into maps of another layout.
 #[macro_export]
 macro_rules! tc_programs {
     (
@@ -162,6 +204,7 @@ impl TcPrograms {
         maps: &'static [&'static str],
         schema_version: u32,
     ) -> Self {
+        check_listed(name);
         Self {
             name,
             obj,
@@ -185,7 +228,7 @@ impl TcPrograms {
         self.schema_root().join("staging")
     }
     fn links_dir(&self) -> PathBuf {
-        links_dir_of(self.name)
+        self.pin_root().join(LINKS_DIR)
     }
     fn link_pin_path(&self, pin: &tc::LinkPin) -> PathBuf {
         self.links_dir().join(pin.filename())
@@ -264,6 +307,114 @@ impl TcPrograms {
         })
     }
 
+    // one lock for every subsystem. An attach holds it from reading the list and the neighbors to
+    // the pin of its link, so two attaches to one interface see each other, and the list is
+    // written under it
+    fn attach_lock(&self) -> anyhow::Result<Flock<File>> {
+        private_dir(Path::new(RUN_ROOT))?;
+        let path = Path::new(RUN_ROOT).join("attach.lock");
+        flock_within(&path, true, "attach lock", self.name)
+    }
+
+    // the links the other subsystems hold on the interface and direction of `pin`, with their
+    // places in `order`. A pin has the same file name in every subsystem, so finding one is a stat
+    // of that name in each of their links directories, which are never listed. A subsystem the
+    // list does not name cannot be placed against
+    fn neighbors(
+        &self,
+        pin: &tc::LinkPin,
+        order: &[String],
+    ) -> anyhow::Result<Vec<(usize, PathBuf)>> {
+        let mut found = Vec::new();
+        for (root, name) in
+            subsystem_roots().with_context(|| format!("{}: list the subsystems", self.name))?
+        {
+            if name == self.name {
+                continue;
+            }
+            let path = root.join(LINKS_DIR).join(pin.filename());
+            if !path.exists() {
+                continue;
+            }
+            match order.iter().position(|listed| *listed == name) {
+                Some(place) => found.push((place, path)),
+                None => log::warn!(
+                    "{}: {name} is not in the order list, not placed against it",
+                    self.name
+                ),
+            }
+        }
+        Ok(found)
+    }
+
+    // attach `prog` for `pin` in its place among the other subsystems' links, see `RUN_ORDER`,
+    // and pin it under `pin_path`
+    fn attach_link(
+        &self,
+        prog: &mut SchedClassifier,
+        pin: &tc::LinkPin,
+        pin_path: &Path,
+    ) -> Result<(), tc::Error> {
+        let _lock = self.attach_lock()?;
+        let order = read_order()?;
+        // under the lock pins only go away, other attaches wait on it. So a neighbor that cannot
+        // be placed against is dropped and the attach tries the rest without listing them again
+        let mut neighbors = self.neighbors(pin, &order)?;
+        let rank = match order.iter().position(|listed| listed.as_str() == self.name) {
+            Some(rank) => rank,
+            // only a list written by a build that dropped this subsystem lacks it
+            None => {
+                log::warn!("{}: not in the order list, attached last", self.name);
+                neighbors.clear();
+                0
+            }
+        };
+        loop {
+            let (index, before) = match place(rank, &neighbors) {
+                Place::Before(i) => (Some(i), true),
+                Place::After(i) => (Some(i), false),
+                Place::Last => (None, false),
+            };
+            // the order holds only the neighbor's fd, the link stays open until the attach is done
+            let neighbor = match index {
+                Some(i) => match tc::open_pinned_link(&neighbors[i].1) {
+                    Ok(link) => Some(link),
+                    // unpinned since the lookup, its subsystem detached it
+                    Err(tc::Error::PinGone) => {
+                        neighbors.remove(i);
+                        continue;
+                    }
+                    Err(e) => return Err(e),
+                },
+                None => None,
+            };
+            let placement = match (&neighbor, before) {
+                (Some(link), true) => LinkOrder::before_link(link)?,
+                (Some(link), false) => LinkOrder::after_link(link)?,
+                (None, _) => LinkOrder::last(),
+            };
+            let attached = tc::attach_and_pin(prog, pin, pin_path, placement);
+            let Some(i) = index else {
+                return attached;
+            };
+            match attached {
+                // a neighbor's pin may name a link whose interface is gone under a reused index,
+                // nothing can be placed against that one until its subsystem reclaims it. The
+                // program is better attached out of order than not at all
+                Err(tc::Error::NotAttached) => {
+                    log::warn!(
+                        "{}: {} not placed against {}, that link is not attached",
+                        self.name,
+                        pin.filename(),
+                        neighbors[i].1.display()
+                    );
+                    neighbors.remove(i);
+                }
+                result => return result,
+            }
+        }
+    }
+
     /// Whether a link of the interface name is pinned, read without the lock. Most interfaces
     /// never had a link and their unplug must not wait behind a full apply. A miss is a snapshot,
     /// a pin arriving after it is another attach's. A failed listing counts as a hit.
@@ -347,6 +498,28 @@ impl TcPrograms {
         Ok(remove_dir_if_present(&self.pin_root())?)
     }
 
+    // the list every attach places by. A build writes its own when the written one is outdated
+    // for it, see `order_outdated`
+    fn write_order(&self) -> anyhow::Result<()> {
+        let _lock = self.attach_lock()?;
+        if !order_outdated(&read_order()?, RUN_ORDER) {
+            return Ok(());
+        }
+        let path = Path::new(RUN_ROOT).join(ORDER_FILE);
+        let tmp = path.with_extension("tmp");
+        let mut file = File::options()
+            .write(true)
+            .create(true)
+            .truncate(true)
+            .mode(0o600)
+            .open(&tmp)
+            .with_context(|| format!("{}: write the order list", self.name))?;
+        file.write_all((RUN_ORDER.join("\n") + "\n").as_bytes())?;
+        std::fs::rename(&tmp, &path)
+            .with_context(|| format!("{}: move the order list into place", self.name))?;
+        Ok(())
+    }
+
     // this build's object with all of its programs loaded and its maps created and pinned under
     // `set`. Everything is loaded before any link is touched, so a verifier rejection of one
     // direction leaves the old state whole
@@ -408,7 +581,6 @@ impl TcPrograms {
         &self,
         fill: impl FnOnce(&Staged<'_>) -> anyhow::Result<()>,
     ) -> anyhow::Result<()> {
-        let others = self.other_schemas()?;
         // programs pinned under a newer schema mean a newer build runs here and this process is
         // the stale one, so it leaves the state alone
         if let Some(newer) = self.newer_schema_installed()? {
@@ -419,6 +591,7 @@ impl TcPrograms {
                 self.schema_version
             );
         }
+        let others = self.other_schemas()?;
         std::fs::create_dir_all(self.links_dir())?;
         let staging = self.staging_dir();
         // what a run that died left behind, an unfinished fill or the set it retired
@@ -564,6 +737,7 @@ impl TcPrograms {
     }
 
     fn reconcile(&self, desired: &HashSet<u32>) -> anyhow::Result<()> {
+        self.write_order()?;
         // opened before anything is detached, so a missing program fails the full apply before it
         // changes anything
         let mut progs = Vec::new();
@@ -596,7 +770,7 @@ impl TcPrograms {
                     continue;
                 };
                 let pin = tc::LinkPin { ifindex, name, dir };
-                match tc::attach_and_pin(prog, &pin, &self.link_pin_path(&pin)) {
+                match self.attach_link(prog, &pin, &self.link_pin_path(&pin)) {
                     Ok(()) => {}
                     Err(tc::Error::IfaceGone) => {
                         log::info!("{}: {ifindex} vanished before the attach", self.name);
@@ -666,7 +840,7 @@ impl TcPrograms {
             if path.exists() {
                 continue;
             }
-            match tc::attach_and_pin(prog, &pin, &path) {
+            match self.attach_link(prog, &pin, &path) {
                 Ok(()) => {}
                 Err(tc::Error::IfaceGone) => {
                     log::info!("{}: {ifindex} vanished before the attach", self.name);
@@ -686,8 +860,49 @@ impl TcPrograms {
 
 const LINKS_DIR: &str = "links";
 
-fn links_dir_of(subsystem: &str) -> PathBuf {
-    PathBuf::from(PIN_ROOT).join(subsystem).join(LINKS_DIR)
+// the subsystem directories under the pin root, each with its name
+fn subsystem_roots() -> std::io::Result<Vec<(PathBuf, String)>> {
+    let entries = match std::fs::read_dir(PIN_ROOT) {
+        Ok(entries) => entries,
+        Err(e) if e.kind() == ErrorKind::NotFound => return Ok(Vec::new()),
+        Err(e) => return Err(e),
+    };
+    let mut roots = Vec::new();
+    for entry in entries {
+        let entry = entry?;
+        if !entry.file_type()?.is_dir() {
+            continue;
+        }
+        roots.push((
+            entry.path(),
+            entry.file_name().to_string_lossy().into_owned(),
+        ));
+    }
+    Ok(roots)
+}
+
+// the list under /run, one name per line, empty until a full apply wrote one
+fn read_order() -> anyhow::Result<Vec<String>> {
+    match std::fs::read_to_string(Path::new(RUN_ROOT).join(ORDER_FILE)) {
+        Ok(content) => Ok(content.lines().map(str::to_owned).collect()),
+        Err(e) if e.kind() == ErrorKind::NotFound => Ok(Vec::new()),
+        Err(e) => Err(e).context("read the order list"),
+    }
+}
+
+// whether `list` replaces `written`: a name of the list is missing, or the written list is not
+// longer and orders the names differently. A longer list is a newer release's and stays however
+// it orders them, so adding a subsystem wins over the builds still running, while a plain reorder
+// alternates between the two builds until the older one is gone
+fn order_outdated(written: &[String], list: &[&str]) -> bool {
+    let places: Option<Vec<usize>> = list
+        .iter()
+        .map(|name| written.iter().position(|w| w.as_str() == *name))
+        .collect();
+    match places {
+        None => true,
+        Some(places) => written.len() <= list.len() && !places.is_sorted(),
+    }
 }
 
 fn schema_live_dir(schema_root: &Path) -> PathBuf {
@@ -705,6 +920,31 @@ fn remove_dir_if_present(dir: &Path) -> std::io::Result<()> {
     }
 }
 
+// where a new link goes among the neighbors' links, the index names the neighbor
+enum Place {
+    Before(usize),
+    After(usize),
+    Last,
+}
+
+// before the earliest neighbor that runs later, otherwise after the latest one that runs
+// earlier. Each attach inserts into a chain sorted this way, so the chain stays sorted
+fn place(rank: usize, neighbors: &[(usize, PathBuf)]) -> Place {
+    let ranked = neighbors.iter().map(|(r, _)| *r).enumerate();
+    let later = ranked
+        .clone()
+        .filter(|&(_, r)| r > rank)
+        .min_by_key(|&(_, r)| r);
+    if let Some((i, _)) = later {
+        return Place::Before(i);
+    }
+    let earlier = ranked.filter(|&(_, r)| r < rank).max_by_key(|&(_, r)| r);
+    match earlier {
+        Some((i, _)) => Place::After(i),
+        None => Place::Last,
+    }
+}
+
 // a program pin is a file under a fingerprint directory. A run killed between creating that
 // directory and pinning leaves it empty. Like the links, a directory that cannot be read may
 // hold anything, a missing one is empty
@@ -848,3 +1088,59 @@ impl Staged<'_> {
             .hash_map_in(&self.programs.staging_dir(), name)
     }
 }
+
+#[cfg(test)]
+mod test {
+    use super::*;
+
+    fn placed(rank: usize, ranks: &[usize]) -> String {
+        let neighbors: Vec<(usize, PathBuf)> = ranks
+            .iter()
+            .map(|&r| (r, PathBuf::from(format!("link-{r}"))))
+            .collect();
+        match place(rank, &neighbors) {
+            Place::Before(i) => format!("before {}", neighbors[i].1.display()),
+            Place::After(i) => format!("after {}", neighbors[i].1.display()),
+            Place::Last => "last".into(),
+        }
+    }
+
+    #[test]
+    fn a_link_goes_before_the_earliest_later_neighbor() {
+        assert_eq!(placed(1, &[3, 2]), "before link-2");
+        assert_eq!(placed(1, &[0, 3, 2]), "before link-2");
+    }
+
+    #[test]
+    fn a_link_goes_after_the_latest_earlier_neighbor() {
+        assert_eq!(placed(2, &[0, 1]), "after link-1");
+        assert_eq!(placed(3, &[1, 0]), "after link-1");
+    }
+
+    #[test]
+    fn a_link_without_neighbors_goes_last() {
+        assert_eq!(placed(1, &[]), "last");
+    }
+
+    fn written(names: &[&str]) -> Vec<String> {
+        names.iter().map(|&n| n.to_owned()).collect()
+    }
+
+    #[test]
+    fn a_list_with_a_name_not_written_yet_replaces_the_written_one() {
+        assert!(order_outdated(&written(&[]), &["a"]));
+        assert!(order_outdated(&written(&["a", "b"]), &["x", "a", "b"]));
+    }
+
+    #[test]
+    fn a_longer_written_list_stays_whatever_its_order() {
+        assert!(!order_outdated(&written(&["x", "a", "b"]), &["a", "b"]));
+        assert!(!order_outdated(&written(&["b", "a", "x"]), &["a", "b"]));
+    }
+
+    #[test]
+    fn a_reorder_of_the_same_names_replaces_the_written_list() {
+        assert!(order_outdated(&written(&["a", "b"]), &["b", "a"]));
+        assert!(!order_outdated(&written(&["a", "b"]), &["a", "b"]));
+    }
+}
diff --git a/src/tc.rs b/src/tc.rs
index b66d5ab56269..3676a3fbb25e 100644
--- a/src/tc.rs
+++ b/src/tc.rs
@@ -10,7 +10,7 @@ use aya::{
     programs::{
         ProgramError, SchedClassifier, TcAttachType,
         links::{FdLink, LinkError, LinkOrder, PinnedLink},
-        tc::TcAttachOptions,
+        tc::{SchedClassifierLink, TcAttachOptions},
     },
 };
 
@@ -24,6 +24,9 @@ pub(crate) enum Error {
     IfaceGone,
     /// The pin was gone by the time it was opened or removed, another attach or unplug took it.
     PinGone,
+    /// The link the call referred to is not attached to the interface, the neighbor of a
+    /// placement or the link of a swap.
+    NotAttached,
     Other(anyhow::Error),
 }
 
@@ -33,6 +36,7 @@ impl std::fmt::Display for Error {
             Self::AlreadyAttached => f.write_str("link already in place"),
             Self::IfaceGone => f.write_str("interface is gone"),
             Self::PinGone => f.write_str("pin is gone"),
+            Self::NotAttached => f.write_str("link not attached"),
             Self::Other(e) if f.alternate() => write!(f, "{e:#}"),
             Self::Other(e) => write!(f, "{e}"),
         }
@@ -61,6 +65,9 @@ impl From<ProgramError> for Error {
             ProgramError::SyscallError(s) if s.io_error.kind() == ErrorKind::AlreadyExists => {
                 Self::AlreadyAttached
             }
+            ProgramError::SyscallError(s) if s.io_error.kind() == ErrorKind::NotFound => {
+                Self::NotAttached
+            }
             e => Self::Other(e.into()),
         }
     }
@@ -180,18 +187,19 @@ impl LinkPin {
 /// filters on the interface's qdiscs, such as the `ingress` qdisc the rate limiter installs.
 /// `TC_ACT_UNSPEC` hands a packet on to the next program and then to the filters. Any other
 /// verdict ends the chain right there. So a subsystem's program returns `TC_ACT_UNSPEC` for
-/// whatever it leaves alone. Programs of several subsystems run in attach order, each new link
-/// goes last.
+/// whatever it leaves alone. `order` is the link's place among the links already there, see
+/// [`RUN_ORDER`](crate::subsystem::RUN_ORDER).
 pub(crate) fn attach_and_pin(
     prog: &mut SchedClassifier,
     pin: &LinkPin,
     pin_path: &Path,
+    order: LinkOrder,
 ) -> Result<(), Error> {
     let link_id = prog
         .attach_with_options(
             &pin.name,
             pin.dir.aya_type(),
-            TcAttachOptions::TcxOrder(LinkOrder::last()),
+            TcAttachOptions::TcxOrder(order),
         )
         .map_err(|e| match Error::from(e) {
             // the interface can go away between the name lookup and the attach
@@ -210,12 +218,14 @@ pub(crate) fn attach_and_pin(
     Ok(())
 }
 
+pub(crate) fn open_pinned_link(pin_path: &Path) -> Result<SchedClassifierLink, Error> {
+    let fd_link: FdLink = PinnedLink::from_pin(pin_path)?.into();
+    Ok(fd_link.try_into()?)
+}
+
 /// Rebind a pinned link to `prog` via LINK_UPDATE. Atomic, traffic sees no detach/reattach gap.
 pub(crate) fn swap_pinned_link(prog: &mut SchedClassifier, pin_path: &Path) -> Result<(), Error> {
-    let pinned = PinnedLink::from_pin(pin_path)?;
-    let fd_link: FdLink = pinned.into();
-    let link = fd_link.try_into()?;
-    let new_id = prog.attach_to_link(link)?;
+    let new_id = prog.attach_to_link(open_pinned_link(pin_path)?)?;
     // take the handle out of aya's internal tracking, we have the pin
     let _ = prog.take_link(new_id)?;
     Ok(())
-- 
2.47.3