[PATCH proxmox-ebpf v4 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 subsystem's place comes from the list at compile time, and a name
missing from the list fails the build instead of landing somewhere in
the chain.

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

diff --git a/src/subsystem.rs b/src/subsystem.rs
index c740fa8..3bf1634 100644
--- a/src/subsystem.rs
+++ b/src/subsystem.rs
@@ -11,6 +11,11 @@
 //! 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`]. An
+//! attach places its link among the links the other subsystems hold on that interface, which it
+//! finds through their pins. It does that under a lock all subsystems share, so each attach sees
+//! the links pinned before it.
 use std::{
     collections::HashSet,
     fs::File,
@@ -21,7 +26,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},
@@ -32,6 +40,36 @@ use crate::tc::{self, Direction};
 const PIN_ROOT: &str = "/sys/fs/bpf/proxmox-ebpf";
 const RUN_ROOT: &str = "/run/proxmox-ebpf";
 
+/// 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 rank_of(name: &str) -> usize {
+    let mut i = 0;
+    while i < RUN_ORDER.len() {
+        if str_eq(RUN_ORDER[i], name) {
+            return i;
+        }
+        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;
     let mut i = 0;
@@ -44,7 +82,7 @@ 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.
+/// rank and the fingerprint follow from the name and the bytes.
 #[macro_export]
 macro_rules! tc_programs {
     (
@@ -121,6 +159,8 @@ impl std::error::Error for NotLoaded {}
 pub struct TcPrograms {
     /// The subsystem's name, its directory under the pin root.
     name: &'static str,
+    /// Its place in [`RUN_ORDER`].
+    rank: usize,
     /// The embedded BPF object.
     obj: &'static [u8],
     /// FNV-1a of `obj`, the programs are pinned under it.
@@ -145,6 +185,7 @@ impl TcPrograms {
     ) -> Self {
         Self {
             name,
+            rank: rank_of(name),
             obj,
             fingerprint: obj_fingerprint(obj),
             programs,
@@ -221,6 +262,99 @@ impl TcPrograms {
         })
     }
 
+    // one lock for every subsystem. An attach holds it from the neighbor lookup to the pin of its
+    // link, so two attaches to one interface see each other. An install holds it while it moves
+    // its pins to a new schema directory, so a lookup never misses a link in the middle of the
+    // move
+    fn attach_lock(&self) -> anyhow::Result<Flock<File>> {
+        std::fs::create_dir_all(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
+    // ranks. A pin has the same file name in every subsystem, so finding one is a stat of that
+    // name in each of their schema directories, their links directories are never listed
+    fn neighbors(&self, pin: &tc::LinkPin) -> anyhow::Result<Vec<(usize, PathBuf)>> {
+        let mut found = Vec::new();
+        for (rank, name) in RUN_ORDER.iter().enumerate() {
+            if *name == self.name {
+                continue;
+            }
+            let schemas = match std::fs::read_dir(Path::new(PIN_ROOT).join(name)) {
+                Ok(schemas) => schemas,
+                Err(e) if e.kind() == ErrorKind::NotFound => continue,
+                Err(e) => return Err(e).with_context(|| format!("list the pins of {name}")),
+            };
+            for schema in schemas {
+                let path = schema_links_dir(&schema?.path()).join(pin.filename());
+                if path.exists() {
+                    found.push((rank, path));
+                }
+            }
+        }
+        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()?;
+        // under the lock pins only go away, other attaches and the pin moves of an install wait
+        // on it. So a neighbor that cannot be placed against is dropped and the attach tries the
+        // rest without reading the list again
+        let mut neighbors = self.neighbors(pin)?;
+        loop {
+            let (index, before) = match place(self.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 order = 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, order);
+            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
+                // interface is better served 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. So do links
@@ -417,6 +551,7 @@ impl TcPrograms {
         // their interfaces never run without a program and keep their place in the tcx order.
         // One this build has no program for, or that already has a link here, is detached
         // instead. A rebound link whose pin cannot be moved stays where it is
+        let moving = self.attach_lock()?;
         for links_dir in old_links {
             for pin in tc::read_pinned_links(links_dir)? {
                 let old = links_dir.join(pin.filename());
@@ -449,6 +584,7 @@ impl TcPrograms {
                 }
             }
         }
+        drop(moving);
 
         // a run that died after pinning some of the directions left a partial set behind
         match std::fs::remove_dir_all(self.prog_dir()) {
@@ -604,7 +740,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);
@@ -674,7 +810,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);
@@ -706,6 +842,31 @@ fn links_pinned_under(schemas: &[(PathBuf, Option<u32>)]) -> bool {
         .any(|(dir, _)| any_links(&schema_links_dir(dir)))
 }
 
+// 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,
+    }
+}
+
 // whether link pins remain in a links directory. Debris of another kind does not count, it goes
 // with the directory. One that cannot be read may hold anything, a missing one is empty
 fn any_links(links_dir: &Path) -> bool {
@@ -827,3 +988,37 @@ impl ApplyLock<'_, Exclusive> {
         self.programs.tear_down()
     }
 }
+
+#[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");
+    }
+}
diff --git a/src/tc.rs b/src/tc.rs
index 63d3fbf..15da990 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()),
         }
     }
@@ -174,18 +181,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
@@ -200,12 +208,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