server/lib/src/exposed/fast_routes.rs
//! Repo-name → backend dispatch table on the gRPC/HTTP hot path.
//!
//! An `ExposedEndpoint` fans out to many repos; every request must resolve the
//! repo name to its `RepositoryBackendTrait` before `fetch()`/`put()`. Rather
//! than a `HashMap` this uses a first-byte bucketed table: routes are sorted by
//! initial byte (then length), and `first_byte_index`/`first_byte_len` give the
//! `[start, len)` slice for a byte in O(1), so `lookup` scans only same-first-byte
//! names with exact `==` compare — no hashing, cache-friendly for the small,
//! fixed route sets the wiring engine attaches.
//!
//! **Swappable, never mutated in place** (lane M4b): a [`RouteTable`] is built once
//! and immutable; [`FastRoutes`] is a shared handle to the CURRENT table. Every
//! clone of a handle reads the same cell, so the gRPC door, the HTTP door and the
//! job runner of one endpoint all see a repository [`FastRoutes::add`]ed at run
//! time (a paid signup's, made by the ONE monetize's `add_principal`) at once, with
//! no restart. A swap builds a NEW table beside the old one; a lookup that already
//! ran keeps the backend it resolved (an owned `Arc`), and [`FastRoutes::snapshot`]
//! hands a caller that needs a consistent view the table as it stood.
//! Gotcha: bucketing is purely on the first byte, and empty names fold into
//! byte 0 (`unwrap_or(0)`), so an empty-string route collides with anything else
//! keyed at index 0 — names are assumed non-empty and unique.
use crate::lock::RwLockOrRecover as _;
use std::sync::Arc;
use traits::RepositoryBackendTrait;
#[derive(Clone)]
pub struct FastRoute {
pub name: String,
// todo make Option
pub backend: Arc<dyn RepositoryBackendTrait>,
}
/// One immutable route table (the first-byte bucketed array described above).
pub struct RouteTable {
pub routes: Vec<FastRoute>,
pub first_byte_index: [usize; 256],
pub first_byte_len: [usize; 256],
}
/// The shared handle to the CURRENT [`RouteTable`]; `Clone` shares the cell.
#[derive(Clone)]
pub struct FastRoutes {
table: Arc<std::sync::RwLock<Arc<RouteTable>>>,
}
impl FastRoutes {
pub fn new(routes: Vec<(String, Arc<dyn RepositoryBackendTrait>)>) -> Self {
Self {
table: Arc::new(std::sync::RwLock::new(Arc::new(RouteTable::new(routes)))),
}
}
/// The table as it stands now: a caller holding it keeps it, whatever is swapped in after.
pub fn snapshot(&self) -> Arc<RouteTable> {
Arc::clone(&self.table.read_or_recover())
}
/// The backend serving `name` in the current table.
pub fn lookup(&self, name: &str) -> Option<Arc<dyn RepositoryBackendTrait>> {
self.table.read_or_recover().lookup(name).cloned()
}
pub fn all_repos(&self) -> Vec<(String, Arc<dyn RepositoryBackendTrait>)> {
self.snapshot().all_repos()
}
/// How many routes the current table holds.
pub fn len(&self) -> usize {
self.snapshot().routes.len()
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
/// **Serve `name` from now on**: a new table (the current one plus this route) is
/// swapped in for every clone of this handle. A name already routed is left as it is
/// (`false`); the first route of a name wins, as in [`RouteTable::lookup`].
pub fn add(&self, name: &str, backend: Arc<dyn RepositoryBackendTrait>) -> bool {
let mut cell = self.table.write_or_recover();
if cell.lookup(name).is_some() {
return false;
}
let mut routes = cell.all_repos();
routes.push((name.to_string(), backend));
*cell = Arc::new(RouteTable::new(routes));
true
}
}
impl RouteTable {
pub fn new(routes: Vec<(String, Arc<dyn RepositoryBackendTrait>)>) -> Self {
let mut routes_vec: Vec<FastRoute> = routes
.into_iter()
.map(|(name, backend)| FastRoute { name, backend })
.collect();
// Sort by first byte then length
routes_vec.sort_by(|a, b| {
let fa = a.name.as_bytes().first().copied().unwrap_or(0);
let fb = b.name.as_bytes().first().copied().unwrap_or(0);
fa.cmp(&fb).then(a.name.len().cmp(&b.name.len()))
});
let mut first_byte_index = [0usize; 256];
let mut first_byte_len = [0usize; 256];
// Build lookup table
let mut i = 0usize;
while i < routes_vec.len() {
let byte = routes_vec[i].name.as_bytes().first().copied().unwrap_or(0);
let start = i;
while i < routes_vec.len()
&& routes_vec[i].name.as_bytes().first().copied().unwrap_or(0) == byte
{
i += 1;
}
first_byte_index[byte as usize] = start;
first_byte_len[byte as usize] = i - start;
}
Self {
routes: routes_vec,
first_byte_index,
first_byte_len,
}
}
pub fn lookup(&self, name: &str) -> Option<&Arc<dyn RepositoryBackendTrait>> {
let bytes = name.as_bytes();
let first = bytes.first().copied().unwrap_or(0) as usize;
let start = self.first_byte_index[first];
let len = self.first_byte_len[first];
if len == 0 {
return None;
}
let bucket = &self.routes[start..start + len];
for r in bucket {
if r.name == name {
return Some(&r.backend);
}
}
None
}
pub fn all_repos(&self) -> Vec<(String, Arc<dyn RepositoryBackendTrait>)> {
self.routes
.iter()
.map(|r| (r.name.clone(), r.backend.clone()))
.collect()
}
}
#[cfg(test)]
mod tests {
use super::*;
use traits::{ArtifactEntry, ArtifactFormat, ArtifactId};
/// A backend that only knows its own name — enough to prove `lookup` resolves
/// a repo name to the RIGHT backend (we assert on `backend.name()`).
struct NamedRepo(&'static str);
#[async_trait::async_trait]
impl RepositoryBackendTrait for NamedRepo {
fn caps(&self) -> traits::Caps {
traits::Caps {
listing: true,
..traits::Caps::NONE
}
}
fn name(&self) -> &str {
self.0
}
fn format(&self) -> ArtifactFormat {
ArtifactFormat::Raw
}
fn is_writable(&self) -> bool {
false
}
fn fetch(&self, _id: &ArtifactId) -> anyhow::Result<Option<traits::Bytes>> {
Ok(None)
}
fn put(&self, _id: &ArtifactId, _data: &[u8]) -> anyhow::Result<()> {
anyhow::bail!("read-only")
}
fn list(&self, _f: Option<&str>, _l: usize) -> anyhow::Result<Vec<ArtifactEntry>> {
Ok(Vec::new())
}
fn handle_http2_request(
&self,
_m: &str,
_s: &str,
_b: &[u8],
) -> anyhow::Result<(u16, Vec<(String, String)>, Vec<u8>)> {
Ok((404, Vec::new(), Vec::new()))
}
}
fn route(name: &'static str) -> (String, Arc<dyn RepositoryBackendTrait>) {
(
name.to_string(),
Arc::new(NamedRepo(name)) as Arc<dyn RepositoryBackendTrait>,
)
}
#[test]
fn lookup_resolves_every_registered_name_to_its_own_backend() {
// Deliberately unsorted input; several share a first byte ('r', 'm').
let fr = FastRoutes::new(vec![
route("rust"),
route("maven"),
route("rust-proxy"),
route("mirror"),
route("pip"),
]);
for name in ["rust", "maven", "rust-proxy", "mirror", "pip"] {
let backend = fr
.lookup(name)
.unwrap_or_else(|| panic!("{name} not found"));
assert_eq!(
backend.name(),
name,
"lookup returned the WRONG backend for {name}"
);
}
}
#[test]
fn same_first_byte_siblings_do_not_alias_and_lengths_are_covered() {
// 'r' bucket holds three names of different lengths — the paginator sorts
// by (first_byte, len), so this exercises the length tiebreak + exact `==`.
let fr = FastRoutes::new(vec![route("r"), route("rust"), route("rust-proxy")]);
assert_eq!(fr.lookup("r").unwrap().name(), "r");
assert_eq!(fr.lookup("rust").unwrap().name(), "rust");
assert_eq!(fr.lookup("rust-proxy").unwrap().name(), "rust-proxy");
// A name in the same bucket that was never registered must miss, not alias
// onto a sibling sharing the first byte.
assert!(
fr.lookup("ruby").is_none(),
"unregistered same-first-byte name misses"
);
assert!(fr.lookup("rustacean").is_none());
}
#[test]
fn lookup_misses_return_none() {
let fr = FastRoutes::new(vec![route("maven"), route("pip")]);
// A first byte with zero routes ('z') short-circuits on first_byte_len==0.
assert!(fr.lookup("zzz").is_none(), "unpopulated first byte → None");
// A populated first byte ('m') but a name not in the bucket.
assert!(fr.lookup("mirror").is_none());
// The empty string folds to byte 0, which has no routes here.
assert!(fr.lookup("").is_none());
}
#[test]
fn empty_route_table_looks_up_nothing() {
let fr = FastRoutes::new(Vec::new());
assert!(fr.lookup("anything").is_none());
assert!(fr.all_repos().is_empty());
}
#[test]
fn all_repos_returns_every_registered_route() {
let fr = FastRoutes::new(vec![route("a"), route("b"), route("c")]);
let mut names: Vec<String> = fr.all_repos().into_iter().map(|(n, _)| n).collect();
names.sort();
assert_eq!(names, vec!["a".to_string(), "b".into(), "c".into()]);
}
/// ★ lane M4b: a route added at run time is seen by EVERY clone of the handle (the
/// gRPC door, the HTTP door and the job runner of one door share it), a name already
/// routed is kept, and a snapshot taken before keeps the table it had.
#[test]
fn an_added_route_is_served_by_every_clone_and_a_snapshot_keeps_its_table() {
let fr = FastRoutes::new(vec![route("crates")]);
let door = fr.clone();
let before = fr.snapshot();
assert!(fr.add("acme", Arc::new(NamedRepo("acme"))));
assert_eq!(
door.lookup("acme").unwrap().name(),
"acme",
"the other clone sees it at once"
);
assert_eq!(door.lookup("crates").unwrap().name(), "crates");
assert!(
before.lookup("acme").is_none(),
"a request's snapshot keeps the table it started with"
);
assert_eq!(before.routes.len(), 1);
assert!(
!fr.add("crates", Arc::new(NamedRepo("other"))),
"a routed name is kept"
);
assert_eq!(fr.lookup("crates").unwrap().name(), "crates");
assert_eq!(fr.len(), 2);
}
/// ★ lane M4b: lookups running at the same moment as the swaps stay correct — every
/// boot route resolves throughout, to its own backend, and every added one is there after.
#[test]
fn lookups_racing_the_swaps_always_resolve_their_own_backend() {
let names: Vec<&'static str> = (0..64)
.map(|i| &*Box::leak(format!("sold-{i}").into_boxed_str()))
.collect();
let fr = FastRoutes::new(vec![route("crates"), route("maven"), route("pip")]);
let stop = Arc::new(std::sync::atomic::AtomicBool::new(false));
let readers: Vec<_> = (0..4)
.map(|_| {
let (fr, stop) = (fr.clone(), stop.clone());
std::thread::spawn(move || {
let mut n = 0u64;
while !stop.load(std::sync::atomic::Ordering::Relaxed) || n == 0 {
for name in ["crates", "maven", "pip"] {
assert_eq!(
fr.lookup(name).expect("a boot route never misses").name(),
name
);
}
let snap = fr.snapshot();
for r in &snap.routes {
assert_eq!(
snap.lookup(&r.name).unwrap().name(),
r.name,
"a snapshot is whole"
);
}
n += 1;
}
n
})
})
.collect();
let writers: Vec<_> = names
.chunks(16)
.map(|chunk| {
let (fr, chunk) = (fr.clone(), chunk.to_vec());
std::thread::spawn(move || {
for name in chunk {
assert!(fr.add(name, Arc::new(NamedRepo(name))));
}
})
})
.collect();
for w in writers {
w.join().unwrap();
}
stop.store(true, std::sync::atomic::Ordering::Relaxed);
for r in readers {
assert!(r.join().unwrap() > 0);
}
for name in &names {
assert_eq!(
fr.lookup(name).unwrap().name(),
*name,
"no add is lost to a racing one"
);
}
assert_eq!(fr.len(), 3 + names.len());
}
#[test]
fn high_byte_names_bucket_correctly() {
// Non-ASCII first byte (>127) must still bucket into the 256-wide table
// without indexing out of range.
let fr = FastRoutes::new(vec![route("æther"), route("rust")]);
assert_eq!(fr.lookup("æther").unwrap().name(), "æther");
assert_eq!(fr.lookup("rust").unwrap().name(), "rust");
assert!(fr.lookup("ähnlich").is_none());
}
}