[PATCH proxmox v9 4/5] ebpf: subsystem: place subsystem links in a fixed order

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

tcx runs the programs on an interface in the order of its chain, and
a new link goes at the end. So whichever subsystem attached first sees
a packet first. To fix the order, a file next to the objects lists
the subsystems in the order they run.

An attach puts its link in that order among the other subsystems'
links on the interface. All subsystems share one lock for this, so
two attaches to one interface see each other. A swap keeps a link's
position, so a changed file only affects links attached after the
change.

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

diff --git a/proxmox-ebpf/src/subsystem.rs b/proxmox-ebpf/src/subsystem.rs
index ed17537e078b..d3a857464769 100644
--- a/proxmox-ebpf/src/subsystem.rs
+++ b/proxmox-ebpf/src/subsystem.rs
@@ -71,10 +71,12 @@
 //! single entry updates and attaches fail with [`NotLoaded`], and their detaches do nothing.
 //!
 //! The programs and maps come from an object file that is shipped as a package of its own, so a
-//! program can be updated without building this library.
+//! program can be updated without building this library. Next to it is the `order` file, which
+//! orders the subsystems on an interface.
 //! ```text
 //! /usr/lib/proxmox-ebpf/
 //!     dhcp.bpf.o                          <subsystem>.bpf.o
+//!     order                               one subsystem name per line
 //! ```
 //! The object has to follow a few rules for us to load it. Every program is a function in the
 //! `classifier` section, under the name given to [`TcPrograms::new`]. Every map the subsystem lists
@@ -113,12 +115,22 @@
 //! ```text
 //! /run/proxmox-ebpf/
 //!     dhcp/lock                           <subsystem>/lock, the apply lock
+//!     attach.lock                         one for all subsystems, held during an attach
 //! ```
 //! A full apply and [`ApplyLock::clear`] take it exclusively, everything else takes it shared. The
 //! caller reads the input of its change under the lock and writes it before it lets go, so changes
 //! reach the kernel in the order they read their input. Two shared holders working on the same
 //! interface can still write in either order. Waiting for the lock fails after 10 seconds, or
 //! earlier when a signal handler without `SA_RESTART` runs.
+//!
+//! The programs of different subsystems on one interface run in the order of the `order` file, the
+//! first name runs first. When we attach a link, we look for the links the other subsystems hold on
+//! the same interface and direction. Ours goes before the first one that runs after us, or after
+//! the last one that runs before us. We find them by their pin names, which are the same in every
+//! subsystem's `links/`, and we do it under `attach.lock`, so two attaches to one interface see
+//! each other. A subsystem the file does not name is attached last with a warning, and the others
+//! ignore its links. A link keeps its place when the file changes, and a swap during a full apply
+//! keeps it as well. Only new links follow the new order.
 use std::{
     cmp::Ordering,
     collections::HashSet,
@@ -132,7 +144,11 @@ use std::{
 };
 
 use anyhow::{Context, Error, bail};
-use aya::{EbpfLoader, maps::MapType, programs::SchedClassifier};
+use aya::{
+    EbpfLoader,
+    maps::MapType,
+    programs::{SchedClassifier, links::LinkOrder},
+};
 use nix::sys::stat::Mode;
 use object::{Object, ObjectSection};
 use proxmox_sys::fs::{CreateOptions, open_file_locked};
@@ -322,6 +338,114 @@ impl TcPrograms {
         })
     }
 
+    // one lock for every subsystem. An attach holds it from reading the `order` and determining the
+    // neighbor to attach next to, until it is done. Because of the specified order, we can't have
+    // attaches run concurrently
+    fn attach_lock(&self) -> Result<File, Error> {
+        private_dir(Path::new(RUN_ROOT))
+            .with_context(|| format!("{}: create the run directory {RUN_ROOT}", self.name))?;
+        let path = Path::new(RUN_ROOT).join("attach.lock");
+        open_locked(&path, true, "attach lock", self.name)
+    }
+
+    // returns a list of links on the same interface and direction of other subsystems with their
+    // rank the `order` gives them. When attaching we can tell the kernel to attach a program before
+    // or after a link reference we give it. This list allows us to find this neighbor we need to
+    // attach in the correct order. These links are named the same in all subsystems, so we just
+    // have to list the present subsystems and stat the one relevant link file they contain.
+    fn neighbors(
+        &self,
+        pin: &tc::LinkPin,
+        order: &[String],
+    ) -> Result<Vec<(usize, PathBuf)>, Error> {
+        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, ignoring its links",
+                    self.name
+                ),
+            }
+        }
+        Ok(found)
+    }
+
+    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
+        // used 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,
+            // with no relevant links left, we attach last
+            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),
+            };
+            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, fine but we can't use
+                    // it to place ourselves against anymore
+                    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 {
+                // the neighbor's pin may outlive its interface and match a new one of the same
+                // index and name. Its link is not attached anywhere, so attaching next to it fails
+                // and we try the other neighbors
+                Err(tc::Error::NotAttached) => {
+                    log::warn!(
+                        "{}: {} not placed next to {}, that link is not attached",
+                        self.name,
+                        pin.filename(),
+                        neighbors[i].1.display()
+                    );
+                    neighbors.remove(i);
+                }
+                result => return result,
+            }
+        }
+    }
+
     /// Check if the link of the interface name is pinned. Fails if the links in links/ could not be
     /// listed.
     pub fn is_link_pinned(&self, name: &str) -> Result<bool, Error> {
@@ -584,7 +708,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);
@@ -773,7 +897,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);
@@ -793,6 +917,43 @@ impl TcPrograms {
 
 const LINKS_DIR: &str = "links";
 
+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)
+}
+
+fn read_order() -> Result<Vec<String>, Error> {
+    match std::fs::read_to_string(Path::new(OBJECT_DIR).join("order")) {
+        Ok(content) => Ok(parse_order(&content)),
+        Err(e) if e.kind() == ErrorKind::NotFound => Ok(Vec::new()),
+        Err(e) => Err(e).context("read the order list"),
+    }
+}
+
+fn parse_order(content: &str) -> Vec<String> {
+    content
+        .lines()
+        .map(str::trim)
+        .filter(|line| !line.is_empty())
+        .map(str::to_owned)
+        .collect()
+}
+
 fn object_schema(bytes: &[u8]) -> Result<u32, Error> {
     let file = object::File::parse(bytes).context("not an object")?;
     let section = file
@@ -834,6 +995,31 @@ fn remove_dir_if_present(dir: &Path) -> std::io::Result<()> {
     }
 }
 
+// where a new link goes relative to the other tcx programs on the interface
+enum Place {
+    Before(usize),
+    After(usize),
+    Last,
+}
+
+// before the earliest neighbor that should run after, or after the latest one that should run
+// before us
+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,
+    }
+}
+
 /// Marker for a guard holding the apply lock shared.
 pub struct Shared;
 
@@ -1013,6 +1199,42 @@ impl<K, V> DerefMut for MapHandle<'_, K, V> {
 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");
+    }
+
+    #[test]
+    fn the_order_file_holds_one_name_per_line() {
+        assert_eq!(parse_order("a\nb\n"), ["a", "b"]);
+        assert_eq!(parse_order("\na\n\n  \nb"), ["a", "b"]);
+        assert!(parse_order("").is_empty());
+    }
+
     fn object_with_section(name: &str, data: &[u8]) -> Vec<u8> {
         let mut object = object::write::Object::new(
             object::BinaryFormat::Elf,
diff --git a/proxmox-ebpf/src/tc.rs b/proxmox-ebpf/src/tc.rs
index 58eb468acba6..612db58fc0f1 100644
--- a/proxmox-ebpf/src/tc.rs
+++ b/proxmox-ebpf/src/tc.rs
@@ -28,6 +28,8 @@ pub(crate) enum Error {
     IfaceGone,
     /// The pin was gone by the time it was opened or removed.
     PinGone,
+    /// The link the call referred to is not attached to the interface.
+    NotAttached,
     Other(anyhow::Error),
 }
 
@@ -37,6 +39,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}"),
         }
@@ -65,6 +68,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()),
         }
     }
@@ -186,17 +192,19 @@ impl LinkPin {
 }
 
 /// Attach `prog` on the interface and direction of `pin` as a tcx link and pin it at `pin_path`.
-/// Programs of several subsystems run in attach order, each new link goes last.
+/// `order` describes where to place it relative to links of other subsystems that may already be
+/// attached to the interface.
 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
-- 
2.47.3