//! Write notifications, the writer set and syncers, as `spec/SPACES-SYNC.md` //! says: the repo host telling a space's host of each commit of a space repo //! here (`notifyRepoUpdate`, sent, and retried); the space host taking those //! notifications into the writer set (`notifyRepoUpdate`, served), taking //! writers out of it (`remove_writers`) and serving it (`listWriters`); and //! syncers' registrations, made by `authorizeSpaceSync` and confirmed with //! `confirmRegistration`, each told of every change of the writer set, of //! its expiry and of the space's deletion (`notifySpaceUpdate`, sent; the //! expiry and deletion notices retried). //! //! What this part keeps is each account's, in its `repo.log` (`ENTRIES`), //! changed under its lock: a writer's notifications that failed for now //! (the retry queue, at most one per space, the latest commit's), and an //! authority's registrations and the notices it keeps to send again (the //! notice queue, at most one per registration). A change is applied as its //! entry says, so that replaying the log makes the same. The writer set is //! kept with its space (`space_authority`), and changed by this part alone: //! its entries are logged here, in the same frame as what the change owes //! the registrations. //! //! Sending is in the background, at most `IN_FLIGHT` at once, with no lock //! held across a send: an attempt is marked as being sent, made, and then //! settled under its account's lock. One scheduler (`start`) sends retries //! when due, from hints of when each account next has one; a hint is //! checked against what the account keeps when it comes. use crate::space_authority::{Space, Status, Writer, status, writer_removed, writer_tracked}; use crate::space_authz::{Lifecycle, SpaceState, endpoint, service_auth}; use crate::space_credentials::{presents_credential, verify_space_credential}; use crate::{ Account, Call, Handler, Resp, Service, Shared, Store, XrpcError, durable, err, invalid, read, required, write, }; use pds_lexicon::Method; use pds_repo::data::{V, from_json, to_json}; use pds_repo::valid_tid; use pds_space::{Commit, SpaceRef}; use pds_store::Wal; use serde_json::{Value as Json, json}; use std::collections::{BTreeMap, BTreeSet, HashSet}; use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering}; use std::sync::{Arc, Mutex, MutexGuard, PoisonError}; use std::time::{Duration, SystemTime, UNIX_EPOCH}; use tokio::sync::Semaphore; use tokio::task::JoinHandle; /// The kinds of `repo.log` entry this part keeps, each naming its space by /// `space`. pub(crate) const ENTRIES: &[&str] = &[ QUEUED, UNQUEUED, REGISTERED, DROPPED, NOTICED, EMPTIED, NOTICE, NOTICE_DONE, ]; /// A notification kept to be sent again, replacing any of its space. const QUEUED: &str = "notifyQueued"; /// The notification of its space taken out, if its `rev` is not later. const UNQUEUED: &str = "notifyUnqueued"; /// A registration made or renewed, to lapse at `expires`. const REGISTERED: &str = "syncRegistered"; /// A registration dropped. const DROPPED: &str = "syncDropped"; /// A lapsed registration sent its expiry notice. const NOTICED: &str = "syncNoticed"; /// Every registration of a deleted space dropped. const EMPTIED: &str = "syncEmptied"; /// A notice kept in the notice queue, in place of any of its registration. const NOTICE: &str = "syncNotice"; /// A registration's notice taken out of the notice queue. const NOTICE_DONE: &str = "syncNoticeDone"; pub(crate) const NOTIFY_REPO_UPDATE: &str = "com.atproto.space.notifyRepoUpdate"; const LIST_WRITERS: &str = "com.atproto.space.listWriters"; const NOTIFY_SPACE_UPDATE: &str = "com.atproto.space.notifySpaceUpdate"; const CONFIRM: &str = "com.atproto.space.confirmRegistration"; /// The updates' and notices' types. const REPO_WRITE: &str = "com.atproto.space.defs#repoWrite"; const REPO_REMOVED: &str = "com.atproto.space.defs#repoRemoved"; const SPACE_DELETED: &str = "com.atproto.space.notifySpaceUpdate#spaceDeleted"; const EXPIRED: &str = "com.atproto.space.notifySpaceUpdate#registrationExpired"; /// Times, in milliseconds. const MINUTE: u64 = 60_000; const HOUR: u64 = 60 * MINUTE; /// A notification not delivered this long after its commit is dropped. const HORIZON: u64 = 24 * HOUR; /// A notice that fails for now this long after it was kept is given up. const NOTICE_HORIZON: u64 = 72 * HOUR; /// The delay before each retry of a notice, in seconds: the fifth's for /// every one after. const NOTICE_DELAYS: [u64; 5] = [60, 600, 3600, 21600, 43200]; /// The most active registrations a space has. pub(crate) const SPACE_REGISTRATIONS: usize = 64; /// How far ahead of now a notified `repoRev` may be. const FUTURE: u64 = 5 * MINUTE; /// How long an answer is waited for, and a DID document. const ANSWER_WAIT: Duration = crate::outbound::WAIT; const RESOLVE_WAIT: Duration = crate::outbound::WAIT; /// The most sends at once, across every account. const IN_FLIGHT: usize = 32; /// The most updates waiting to be sent, across every account. const UPDATES_WAITING: usize = 1024; /// The longest the scheduler sleeps between looks at what is due. const NAP: Duration = Duration::from_secs(5); /// The statuses that fail a send for now, besides a redirect, which is as /// no answer (`spec/SPACES-SYNC.md`, "Environment"); any other but `2xx` /// refuses it. const FAILING: [u16; 9] = [408, 425, 429, 500, 502, 503, 504, 522, 524]; fn lock(m: &Mutex) -> MutexGuard<'_, T> { m.lock().unwrap_or_else(PoisonError::into_inner) } // ---- What an account keeps ------------------------------------------------------ /// When a send is next made: `n` is which attempt it is (0 the first, then /// each retry), `due` when, and `until` its horizon; in milliseconds since /// the epoch. #[derive(Clone, Copy, Debug, PartialEq, Eq)] pub(crate) struct Schedule { pub n: u32, pub due: u64, pub until: u64, } /// A write notification that failed for now: its commit's `rev` and `data`. #[derive(Clone, Debug, PartialEq, Eq)] pub(crate) struct Pending { pub rev: String, pub data: Vec, pub at: Schedule, } /// A registration's endpoint and token, each the exact string the syncer gave. pub(crate) type Pair = (String, String); /// A registration: when it lapses (the `exp` of the credential its latest /// authorization was answered with), and whether it was sent its expiry /// notice since it last lapsed. #[derive(Clone, Copy, Debug, PartialEq, Eq)] pub(crate) struct Registration { pub expires: u64, pub noticed: bool, } /// What a notice tells: the space's deletion, or the registration's expiry, /// at the change's `spaceRev`, owed it for its lapse at `lapse` (the expiry /// it then had). #[derive(Clone, Debug, PartialEq, Eq)] pub(crate) enum Owed { Deleted, Expired { space_rev: String, lapse: u64 }, } /// A notice kept to be sent again: what it tells, and when. Its `until` is /// 72 hours after it was kept. #[derive(Clone, Debug, PartialEq, Eq)] pub(crate) struct Notice { pub owed: Owed, pub at: Schedule, } /// What an account keeps of this part. #[derive(Clone, Debug, Default, PartialEq, Eq)] pub(crate) struct Kept { /// Its notifications that failed for now, by space: the retry queue. pub queue: BTreeMap, /// The registrations of the spaces it is the authority of: by space, /// each pair and its registration. pub registered: BTreeMap>, /// The notices it keeps to send again, by space and pair: the notice queue. pub notices: BTreeMap<(String, Pair), Notice>, /// How many registrations `registered` holds, of every space. registrations: usize, } impl Kept { /// Replay an entry of `repo.log` of the kinds in `ENTRIES`. pub fn replay(&mut self, e: &Json) -> Result<(), String> { self.apply(e).map_err(|why| format!("{why}: {e}")) } /// About the bytes it holds in memory: its queues and registrations, /// each by how many there are. pub(crate) fn cost(&self) -> u64 { ((self.queue.len() + self.notices.len()) * 224 + self.registered.len() * 120 + self.registrations * 200) as u64 } /// Hold `pair`'s registration for `space`, in place of any it had. pub(crate) fn register(&mut self, space: String, pair: Pair, r: Registration) { if self .registered .entry(space) .or_default() .insert(pair, r) .is_none() { self.registrations += 1; } } fn drop_registration(&mut self, space: &str, pair: &Pair) { if let Some(r) = self.registered.get_mut(space) { if r.remove(pair).is_some() { self.registrations -= 1; } if r.is_empty() { self.registered.remove(space); } } } /// Make the change an entry records. pub(crate) fn apply(&mut self, e: &Json) -> Result<(), String> { let text = |k: &str| e[k].as_str().ok_or_else(|| format!("no {k}")); let number = |k: &str| e[k].as_u64().ok_or_else(|| format!("no {k}")); let space = text("space")?; if SpaceRef::parse(space).is_none() { return Err("a space that is no space-ref".into()); } let schedule = || -> Result { let n = u32::try_from(number("n")?).map_err(|_| "an attempt too many")?; Ok(Schedule { n, due: number("due")?, until: number("until")?, }) }; let pair = || Ok::<_, String>((text("endpoint")?.to_string(), text("token")?.to_string())); match text("t")? { QUEUED => { let rev = text("rev")?; if !valid_tid(rev) { return Err("a rev that is no TID".into()); } let data = hex::decode(text("data")?).map_err(|_| "data that is no hex")?; self.queue.insert( space.to_string(), Pending { rev: rev.to_string(), data, at: schedule()?, }, ); } UNQUEUED => { let rev = text("rev")?; if self.queue.get(space).is_some_and(|p| p.rev.as_str() <= rev) { self.queue.remove(space); } } REGISTERED => { let r = Registration { expires: number("expires")?, noticed: false, }; self.register(space.to_string(), pair()?, r); } DROPPED => self.drop_registration(space, &pair()?), NOTICED => { let pair = pair()?; let r = self .registered .get_mut(space) .and_then(|r| r.get_mut(&pair)) .ok_or("an expiry notice of no registration")?; r.noticed = true; } EMPTIED => { if let Some(r) = self.registered.remove(space) { self.registrations -= r.len(); } } NOTICE => { let owed = match text("update")? { "deleted" => Owed::Deleted, "expired" => Owed::Expired { space_rev: text("spaceRev")?.to_string(), lapse: number("lapse")?, }, u => return Err(format!("a notice of no known kind {u}")), }; let at = schedule()?; self.notices .insert((space.to_string(), pair()?), Notice { owed, at }); } NOTICE_DONE => { self.notices.remove(&(space.to_string(), pair()?)); } t => return Err(format!("an entry of no known type {t}")), } Ok(()) } /// When the first of its sends is due. pub(crate) fn next_due(&self) -> Option { self.dues().min() } /// When the first of its sends due after `now` is due: those due /// already are being sent, and hint again when settled. fn next_due_after(&self, now: u64) -> Option { self.dues().filter(|due| *due > now).min() } fn dues(&self) -> impl Iterator + '_ { self.queue .values() .map(|p| p.at.due) .chain(self.notices.values().map(|n| n.at.due)) } /// Where `pair` stands for `space` at `now`, as `authorizeSpaceSync`'s /// step 10 asks (`spec/SPACES-SYNC.md`, "Registering"). pub(crate) fn standing(&self, space: &str, endpoint: &str, token: &str, now: u64) -> Standing { let Some(registered) = self.registered.get(space) else { return Standing::New; }; let mine = registered .iter() .find(|((e, t), _)| e == endpoint && t == token) .map(|(_, r)| r); if mine.is_some_and(|r| r.expires > now) { return Standing::Active; } if registered.values().filter(|r| r.expires > now).count() >= SPACE_REGISTRATIONS { return Standing::Full; } if mine.is_some() { Standing::Lapsed } else { Standing::New } } } /// Where a pair stands for a space: registered and active; registered and /// lapsed; or not registered, with room for it or not. #[derive(Clone, Copy, Debug, PartialEq, Eq)] pub(crate) enum Standing { Active, Lapsed, New, Full, } fn registered(space: &str, pair: (&str, &str), expires: u64) -> Json { json!({ "t": REGISTERED, "space": space, "endpoint": pair.0, "token": pair.1, "expires": expires }) } fn dropped(space: &str, pair: &Pair) -> Json { json!({ "t": DROPPED, "space": space, "endpoint": pair.0, "token": pair.1 }) } fn noticed(space: &str, pair: &Pair) -> Json { json!({ "t": NOTICED, "space": space, "endpoint": pair.0, "token": pair.1 }) } fn queued(space: &str, rev: &str, data: &[u8], at: Schedule) -> Json { json!({ "t": QUEUED, "space": space, "rev": rev, "data": hex::encode(data), "n": at.n, "due": at.due, "until": at.until }) } fn unqueued(space: &str, rev: &str) -> Json { json!({ "t": UNQUEUED, "space": space, "rev": rev }) } fn notice(space: &str, pair: &Pair, owed: &Owed, at: Schedule) -> Json { let mut e = json!({ "t": NOTICE, "space": space, "endpoint": pair.0, "token": pair.1, "n": at.n, "due": at.due, "until": at.until }); match owed { Owed::Deleted => e["update"] = json!("deleted"), Owed::Expired { space_rev, lapse } => { e["update"] = json!("expired"); e["spaceRev"] = json!(space_rev); e["lapse"] = json!(lapse); } } e } fn notice_done(space: &str, pair: &Pair) -> Json { json!({ "t": NOTICE_DONE, "space": space, "endpoint": pair.0, "token": pair.1 }) } /// Log `changes` to the writer set (`space_authority`) and `entries` of /// this part's in one frame, then make the changes they record: a frame the /// log could not take changes nothing (`spec/LIMITS.md`, "Disk"). Answers /// whether it was taken. An account left with sends due is marked for a /// start to load first, and one left with none unmarked (`cache`). fn log_with(st: &mut Store, changes: &[Json], entries: &[Json]) -> bool { if changes.is_empty() && entries.is_empty() { return true; } let mut after = st.notify.clone(); for e in entries { after.apply(e).expect("an entry made to apply"); } let did = st.repo.did.clone(); if after.next_due().is_some() && let Err(e) = st.ctx.eager.mark(&did) { crate::ops::failed_for( crate::ops::Level::Error, "marking an account failed", &did, e, ); return false; } let frame: Vec = changes.iter().chain(entries).cloned().collect(); if let Err(e) = st.wal.append(&frame) { crate::ops::failed("logging write notifications failed", e); return false; } for c in changes { st.authority .apply(c) .expect("a change checked before it is logged"); } st.notify = after; if !st.needs_start() && st.ctx.eager.is_marked(&did) { st.ctx.eager.relax(&did, None); } true } fn log(st: &mut Store, entries: &[Json]) -> bool { log_with(st, &[], entries) } /// The schedule after attempt `tried` of a notification failed at `now`: /// retry `n` is due `min(60 · 2^(n−1), 3600)` seconds, times a random /// factor from 0.5 to 1, after it; None if that is past `until`. fn retry(now: u64, tried: u32, until: u64) -> Option { let n = tried + 1; let full = (60_000u64 << (n - 1).min(6)).min(3_600_000); let due = now + full / 2 + rand::random::() % (full / 2 + 1); (due <= until).then_some(Schedule { n, due, until }) } /// The schedule after attempt `tried` of a notice failed at `now`: retry /// `n` is due `NOTICE_DELAYS[n − 1]` seconds (the last for every one /// after), times a random factor from 0.5 to 1, after it; None, given up, /// once `until` has come. fn notice_retry(now: u64, tried: u32, until: u64) -> Option { if now >= until { return None; } let n = tried + 1; let full = NOTICE_DELAYS[(n as usize - 1).min(NOTICE_DELAYS.len() - 1)] * 1000; let due = now + full / 2 + rand::random::() % (full / 2 + 1); Some(Schedule { n, due, until }) } /// A notice given up, kept or not: an expiry notice drops its /// registration, unless that was renewed since (or dropped already). fn given_up(kept: &Kept, space: &str, pair: &Pair, owed: &Owed) -> Option { let Owed::Expired { lapse, .. } = owed else { return None; }; kept.registered .get(space) .and_then(|r| r.get(pair)) .filter(|r| r.expires == *lapse) .map(|_| dropped(space, pair)) } // ---- TIDs --------------------------------------------------------------------------- const TID_CHARS: &[u8; 32] = b"234567abcdefghijklmnopqrstuvwxyz"; fn tid_value(tid: &str) -> u64 { tid.bytes().fold(0u64, |n, c| { (n << 5) | TID_CHARS.iter().position(|&x| x == c).unwrap_or(0) as u64 }) } fn tid_of(value: u64) -> String { (0..13) .rev() .map(|i| TID_CHARS[((value >> (i * 5)) & 31) as usize] as char) .collect() } /// A new `spaceRev`: the TID of `now`, or, if that is not later than the /// space's revision `prev`, the TID one microsecond after it. fn next_space_rev(now: u64, prev: Option<&str>) -> String { let at = (now * 1000) << 10; tid_of(match prev.map(tid_value) { Some(p) if at <= p => ((p >> 10) + 1) << 10, _ => at, }) } /// A space's revision: the greatest `spaceRev` of its writer set, removed /// entries included; none while the set is empty. pub(crate) fn revision(space: &Space) -> Option<&str> { space.writers.values().map(|w| w.space_rev.as_str()).max() } // ---- The server's part ---------------------------------------------------------------- /// What is being sent, for an account: a commit's notification, a kept /// notice, or a notice's first attempt, kept only if it fails for now. #[derive(Clone, Debug, Hash, PartialEq, Eq)] enum Sending { Write { space: String, rev: String }, Notice { space: String, pair: Pair }, Once(u64), } /// What this part shares across accounts. pub(crate) struct Notify { /// When each account next has a send due, and its DID: a hint, which /// may be stale, checked against what the account keeps when it comes. hints: Mutex>, /// The sends being made, by account, so that none is made twice at once. sending: Mutex>, /// Wakes the scheduler when a hint is given. wake: tokio::sync::Notify, slots: Semaphore, /// The updates waiting to be sent, or being sent. updates: Waiting, /// Names each notice's first attempt. attempts: AtomicU64, /// Milliseconds added to the clock, for tests to see retries come due. #[cfg(test)] pub skew: AtomicU64, } /// How many of something wait, up to a bound: a place is had while one is /// free, and given back when it is dropped. pub(crate) struct Waiting { n: Arc, max: usize, } /// A place among those waiting, given back when dropped. pub(crate) struct Place(Arc); impl Waiting { pub fn new(max: usize) -> Waiting { Waiting { n: Arc::default(), max, } } /// A place, if fewer than its bound wait. pub fn enter(&self) -> Option { self.n .fetch_update(Ordering::SeqCst, Ordering::SeqCst, |n| { (n < self.max).then_some(n + 1) }) .ok()?; Some(Place(self.n.clone())) } } impl Drop for Place { fn drop(&mut self) { self.0.fetch_sub(1, Ordering::SeqCst); } } impl Notify { pub fn new() -> Notify { Notify { hints: Mutex::default(), sending: Mutex::default(), wake: tokio::sync::Notify::new(), slots: Semaphore::new(IN_FLIGHT), updates: Waiting::new(UPDATES_WAITING), attempts: AtomicU64::new(0), #[cfg(test)] skew: Default::default(), } } /// The time, in milliseconds since the epoch. pub fn now(&self) -> u64 { let now = SystemTime::now() .duration_since(UNIX_EPOCH) .unwrap_or_default() .as_millis() as u64; #[cfg(test)] let now = now + self.skew.load(Ordering::SeqCst); now } /// Note when `did` next has a send due, and wake the scheduler. fn hint(&self, did: &str, due: Option) { if let Some(due) = due { lock(&self.hints).insert((due, did.to_string())); self.wake.notify_one(); } } } /// Join the space repo, and take up the sends kept when the server stopped: /// those of the accounts loaded, which a start loads every one with sends /// due of (`cache`). pub(crate) fn resume(svc: &Service) { svc.space_hooks.on_commit(Box::new(on_commit)); for (did, a) in &read(&svc.directory).by_did { if a.store.is_loaded() { lock(&svc.space_notify.hints).extend( read(&a.store) .notify .next_due() .map(|due| (due, did.clone())), ); } } } /// Send what comes due, from now until the server stops. pub(crate) fn start(svc: &Shared) { let svc = svc.clone(); tokio::spawn(async move { loop { let (_, next) = run_due(&svc); let now = svc.space_notify.now(); let nap = next.map_or(NAP, |due| { Duration::from_millis(due.saturating_sub(now)).min(NAP) }); tokio::select! { () = tokio::time::sleep(nap) => {} () = svc.space_notify.wake.notified() => {} } } }); } /// Look now at what `did` has due, as after a space of its is deleted. pub(crate) fn poke(svc: &Service, did: &str) { svc.space_notify.hint(did, Some(svc.space_notify.now())); } /// One send: a write notification's attempt, or a notice's. A notice with /// `once`, which names the attempt, is an expiry notice's first attempt, /// not kept in the notice queue. #[derive(Clone, Debug)] enum Job { Write { did: String, space: String, rev: String, data: Vec, n: u32, until: u64, }, Notice { did: String, space: String, pair: Pair, owed: Owed, n: u32, until: u64, once: Option, }, } impl Job { fn key(&self) -> (String, Sending) { match self { Job::Write { did, space, rev, .. } => ( did.clone(), Sending::Write { space: space.clone(), rev: rev.clone(), }, ), Job::Notice { did, once: Some(attempt), .. } => (did.clone(), Sending::Once(*attempt)), Job::Notice { did, space, pair, .. } => ( did.clone(), Sending::Notice { space: space.clone(), pair: pair.clone(), }, ), } } } /// Start every send due now, of each account hinted as having one: a /// notification past its horizon is dropped instead; a notice whose /// registration was renewed or dropped, or whose space is live again, is /// dropped; and one whose authority is not active is rescheduled unsent. /// Answers the sends started, and when the next is due. fn run_due(svc: &Shared) -> (Vec>, Option) { let n = &svc.space_notify; let now = n.now(); let dids: BTreeSet = { let mut hints = lock(&n.hints); let later = hints.split_off(&(now + 1, String::new())); std::mem::replace(&mut *hints, later) .into_iter() .map(|(_, did)| did) .collect() }; let mut sends = Vec::new(); for did in dids { let Some(a) = svc.account(&did) else { continue }; let active = status(&a) == Status::Active; let (jobs, wal, written) = { let mut guard = write(&a.store); let st = &mut *guard; let mut sending = lock(&n.sending); let (mut jobs, mut done) = (Vec::new(), Vec::new()); for (space, p) in &st.notify.queue { let key = ( did.clone(), Sending::Write { space: space.clone(), rev: p.rev.clone(), }, ); if sending.contains(&key) || p.at.due > now { } else if now >= p.at.until { done.push(unqueued(space, &p.rev)); } else { sending.insert(key); jobs.push(Job::Write { did: did.clone(), space: space.clone(), rev: p.rev.clone(), data: p.data.clone(), n: p.at.n, until: p.at.until, }); } } for ((space, pair), kept) in &st.notify.notices { let key = ( did.clone(), Sending::Notice { space: space.clone(), pair: pair.clone(), }, ); let stale = match &kept.owed { Owed::Deleted => st.authority.state(space) == SpaceState::Live, Owed::Expired { lapse, .. } => st .notify .registered .get(space) .and_then(|r| r.get(pair)) .is_none_or(|r| r.expires != *lapse || r.expires > now), }; if sending.contains(&key) || kept.at.due > now { } else if stale { done.push(notice_done(space, pair)); } else if !active { match notice_retry(now, kept.at.n, kept.at.until) { Some(at) => done.push(notice(space, pair, &kept.owed, at)), None => { done.push(notice_done(space, pair)); done.extend(given_up(&st.notify, space, pair, &kept.owed)); } } } else { sending.insert(key); jobs.push(Job::Notice { did: did.clone(), space: space.clone(), pair: pair.clone(), owed: kept.owed.clone(), n: kept.at.n, until: kept.at.until, once: None, }); } } drop(sending); log(st, &done); (jobs, st.wal.clone(), st.wal.written()) }; n.hint(&did, read(&a.store).notify.next_due_after(now)); // What a send rests on is on disk before it goes. sends .extend(jobs.into_iter().map(|job| { crate::ops::spawn(send(svc.clone(), job, Some((wal.clone(), written)))) })); } let next = lock(&n.hints).first().map(|(due, _)| *due); (sends, next) } /// How a send ended. #[derive(Clone, Copy, Debug, PartialEq, Eq)] enum Outcome { /// A `2xx`. Delivered, /// No answer, or a status worth trying again. Failed, /// Any other answer: not sent again. Refused, } /// Make a send, once `after` is on disk, then settle it. async fn send(svc: Shared, job: Job, after: Option<(Arc, u64)>) { if let Some((wal, n)) = after && durable(wal, n).await.is_err() { return settle(&svc, &job, Outcome::Failed); } let outcome = match &job { Job::Write { did, space, rev, data, .. } => { let Some(sr) = SpaceRef::parse(space) else { return settle(&svc, &job, Outcome::Refused); }; let body = json!({ "space": space, "repo": did, "repoRev": rev, "data": to_json(&V::Bytes(data.clone())) }); post_write(&svc, &sr.authority, did, &body).await } Job::Notice { space, pair, owed, .. } => { let update = match owed { Owed::Deleted => json!({ "$type": SPACE_DELETED }), Owed::Expired { space_rev, .. } => { json!({ "$type": EXPIRED, "spaceRev": space_rev }) } }; let body = json!({ "space": space, "token": pair.1, "update": update }); post_to(&svc, &pair.0, NOTIFY_SPACE_UPDATE, &body).await } }; settle(&svc, &job, outcome); } /// Settle a send under its account's lock. A write notification delivered /// or refused takes out the entry of its space if that entry's `rev` is /// not later; one failed for now is kept, rescheduled, if it is the latest /// commit's, until its horizon. A kept notice delivered is taken out; one /// refused, or failed for now once 72 hours have passed since it was kept, /// is given up; another failed for now is rescheduled. A notice's first /// attempt failed for now is kept, unless a notice is kept for its /// registration already; refused, it is given up. fn settle(svc: &Service, job: &Job, outcome: Outcome) { let n = &svc.space_notify; let now = n.now(); let (did, key) = job.key(); let next = svc.account(&did).map(|a| { let mut guard = write(&a.store); let st = &mut *guard; let entries: Vec = match (job, outcome) { (Job::Write { space, rev, .. }, Outcome::Delivered | Outcome::Refused) => st .notify .queue .get(space) .filter(|p| p.rev <= *rev) .map(|_| unqueued(space, rev)) .into_iter() .collect(), ( Job::Write { space, rev, data, n: tried, until, .. }, Outcome::Failed, ) => { let kept = st.notify.queue.get(space).map(|p| p.rev.as_str()); let head = st.spaces.get(space).map(|r| r.commit(&did, space).rev); let latest = kept == Some(rev.as_str()) || (kept.is_none_or(|k| k < rev.as_str()) && head.as_deref() == Some(rev.as_str())); let e = match retry(now, *tried, *until) { _ if !latest => None, Some(at) => Some(queued(space, rev, data, at)), None => kept.map(|_| unqueued(space, rev)), }; e.into_iter().collect() } ( Job::Notice { space, pair, owed, n: tried, until, once, .. }, outcome, ) => { let held = st.notify.notices.get(&(space.clone(), pair.clone())); let mut entries = Vec::new(); if once.is_none() { // A kept notice replaced since is the other's to settle. if held.is_some_and(|h| h.owed == *owed && h.at.until == *until) { let retried = (outcome == Outcome::Failed) .then(|| notice_retry(now, *tried, *until)) .flatten(); match retried { Some(at) => entries.push(notice(space, pair, owed, at)), None => { entries.push(notice_done(space, pair)); if outcome != Outcome::Delivered { entries.extend(given_up(&st.notify, space, pair, owed)); } } } } } else { match outcome { Outcome::Delivered => {} Outcome::Refused => entries.extend(given_up(&st.notify, space, pair, owed)), // One kept for its registration already: this one is dropped. Outcome::Failed if held.is_some() => {} Outcome::Failed => { let at = notice_retry(now, 0, now + NOTICE_HORIZON) .expect("a horizon ahead"); entries.push(notice(space, pair, owed, at)); } } } entries } }; log(st, &entries); st.notify.next_due() }); lock(&n.sending).remove(&(did.clone(), key)); n.hint(&did, next.flatten()); } /// POST `body`, a write notification, to the space host of `authority`: /// at the origin of the endpoint of its `#atproto_pds`, with service auth /// from `iss`, as SSRF protection allows (`spec/SPACES-SYNC.md`, /// "Environment"). No document, no endpoint, one with a user name or /// password, a URL it will not send to, no connection, a redirect, or no /// answer within `ANSWER_WAIT`, each fail it for now. async fn post_write(svc: &Service, authority: &str, iss: &str, body: &Json) -> Outcome { let Ok(_slot) = svc.space_notify.slots.acquire().await else { return Outcome::Failed; }; let Ok(Some(endpoint)) = tokio::time::timeout(RESOLVE_WAIT, endpoint(svc, authority)).await else { return Outcome::Failed; }; let Some(url) = xrpc_url(&endpoint, NOTIFY_REPO_UPDATE) else { return Outcome::Failed; }; // An account gone can sign nothing again. let Some(jwt) = service_auth( svc, iss, &format!("{authority}#atproto_pds"), NOTIFY_REPO_UPDATE, ) else { return Outcome::Refused; }; let request = svc .outbound .client() .post(url) .bearer_auth(jwt) .header(reqwest::header::CONTENT_TYPE, "application/json") .body(body.to_string()); match svc .outbound .send(crate::ops::Target::Space, request, ANSWER_WAIT) .await { Ok(status) => outcome(status), Err(_) => Outcome::Failed, } } /// POST `body` to method `nsid` at a syncer's endpoint, with no /// `Authorization`, as `post_write` sends: an endpoint that is no /// endpoint fails it for now, as getting no answer. async fn post_to(svc: &Service, endpoint: &str, nsid: &str, body: &Json) -> Outcome { let Ok(_slot) = svc.space_notify.slots.acquire().await else { return Outcome::Failed; }; let Some(url) = xrpc_url(&Json::from(endpoint), nsid) else { return Outcome::Failed; }; let request = svc .outbound .client() .post(url) .header(reqwest::header::CONTENT_TYPE, "application/json") .body(body.to_string()); match svc .outbound .send(crate::ops::Target::Space, request, ANSWER_WAIT) .await { Ok(status) => outcome(status), Err(_) => Outcome::Failed, } } /// `/xrpc/` of an endpoint (`outbound::origin`); None for /// one that is no endpoint, or has a user name or password. fn xrpc_url(endpoint: &Json, nsid: &str) -> Option { crate::outbound::origin(endpoint).and_then(|o| o.join(&format!("/xrpc/{nsid}")).ok()) } fn outcome(status: u16) -> Outcome { match status { 200..=299 => Outcome::Delivered, 300..=399 => Outcome::Failed, s if FAILING.contains(&s) => Outcome::Failed, _ => Outcome::Refused, } } // ---- Telling the space host ---------------------------------------------------------- /// A commit of a space repo here, durable: its space's host is told at /// once, in the background. An authority here takes it directly; any /// other is sent it, and kept in the retry queue if that fails for now. fn on_commit(svc: &Shared, c: &Commit) { let Some(sr) = SpaceRef::parse(&c.space) else { return; }; let (svc, c) = (svc.clone(), c.clone()); if svc.account(&sr.authority).is_some() { // A refusal changes nothing, and is not retried. crate::ops::spawn(async move { let _ = take(&svc, &sr, &c.repo, &c.rev, &c.data).await; }); return; } let Some(a) = svc.account(&c.repo) else { return; }; let n = &svc.space_notify; let until = n.now() + HORIZON; { let mut st = write(&a.store); // A later commit replaces the entry kept, whatever its schedule: // only the latest state is sent again, after a restart too. if let Some(at) = retry(n.now(), 0, until) .filter(|_| st.notify.queue.get(&c.space).is_some_and(|p| p.rev < c.rev)) { log(&mut st, &[queued(&c.space, &c.rev, &c.data, at)]); } lock(&n.sending).insert(( c.repo.clone(), Sending::Write { space: c.space.clone(), rev: c.rev.clone(), }, )); } let job = Job::Write { did: c.repo, space: c.space, rev: c.rev, data: c.data.to_vec(), n: 0, until, }; crate::ops::spawn(send(svc.clone(), job, None)); } // ---- Taking a notification ----------------------------------------------------------- pub(crate) fn handler(nsid: &str) -> Option { Some(match nsid { NOTIFY_REPO_UPDATE => Handler::Call(|s, c, m| Box::pin(notify_repo_update(s, c, m))), LIST_WRITERS => Handler::Call(|s, c, m| Box::pin(list_writers(s, c, m))), _ => return None, }) } fn not_found() -> Result { err(400, "SpaceNotFound", "Space not found") } fn forbidden(message: &str) -> Result { err(403, "Forbidden", message) } /// `notifyRepoUpdate`: its service auth, its input, who sent it and to /// whom, then the notification taken. async fn notify_repo_update( s: &Shared, call: &Call<'_>, m: &'static Method, ) -> Result { let (iss, aud) = crate::space_credentials::service_auth(s, call, NOTIFY_REPO_UPDATE).await?; let b = crate::input(call, m)?; crate::limits::guard(s, call, None, Some(&b))?; let (space, repo, rev) = ( required(&b, "space")?, required(&b, "repo")?, required(&b, "repoRev")?, ); let Some(sr) = SpaceRef::parse(space) else { return invalid("space must be a valid space-ref"); }; let Ok(V::Bytes(data)) = from_json(&b["data"]) else { return invalid("data must be bytes"); }; if iss != repo { return forbidden("The token's issuer is not the repo notified of"); } let authority = sr.authority.as_str(); if !aud .is_some_and(|aud| aud == authority || aud.strip_suffix("#atproto_pds") == Some(authority)) { return forbidden("The token is not addressed to the space's authority"); } take(s, &sr, repo, rev, &data).await?; Ok(Resp::Nothing) } /// Take a notification of `repo`'s commit `rev` in `sr`, from the /// authority's account on: refused if that is not here, if `rev` is too far /// ahead, if the space is not live, or if its policy does not authorize the /// writer. Then a `rev` not later than the writer's entry's, removed or /// not, changes nothing; a later one becomes its entry, not removed, with a /// new `spaceRev`, and is sent to the space's registrations. Answers once /// the change is on disk. async fn take( svc: &Shared, sr: &SpaceRef, repo: &str, rev: &str, data: &[u8], ) -> Result<(), XrpcError> { let Some(a) = svc.account(&sr.authority) else { return not_found(); }; let now = svc.space_notify.now(); if (tid_value(rev) >> 10) / 1000 > now + FUTURE { return err(400, "FutureRev", "The repo rev is too far in the future"); } if svc.space_state(sr) != SpaceState::Live { return not_found(); } if !svc .authorize_write(sr, repo) .await .or_else(crate::space_authz::Undecided::answer)? { return forbidden("The writer may not write to the space"); } let uri = sr.uri(); let (sends, wal, written) = { let mut guard = write(&a.store); let st = &mut *guard; let Some(space) = st.authority.live(&uri) else { return not_found(); }; let sends = if space .writers .get(repo) .is_some_and(|w| w.rev.as_str() >= rev) { None } else { let prev = revision(space).map(str::to_string); let space_rev = next_space_rev(now, prev.as_deref()); let w = Writer { rev: rev.to_string(), data: data.to_vec(), space_rev: space_rev.clone(), removed: false, }; let change = writer_tracked(&uri, repo, &w); let mut update = json!({ "$type": REPO_WRITE, "repo": repo, "repoRev": rev, "data": to_json(&V::Bytes(data.to_vec())), "spaceRev": space_rev }); if let Some(p) = prev { update["prevSpaceRev"] = json!(p); } let mut sends = Sends::new(&sr.authority, &uri); let mut entries = Vec::new(); sends.tell(&st.notify, update, &space_rev, now, &mut entries); if !log_with(st, &[change], &entries) { return crate::internal(); } Some(sends) }; (sends, st.wal.clone(), st.wal.written()) }; // The change is in the log: the rest happens even if the caller goes away. let svc = svc.clone(); let finish = crate::ops::spawn(async move { let synced = durable(wal, written).await; if let (Ok(()), Some(sends)) = (&synced, sends) { sends.go(&svc); } synced }); finish.await.unwrap_or_else(|_| crate::internal()) } // ---- Sending updates -------------------------------------------------------------------- /// What changes of a space's writer set owe its registrations, to send /// once the changes are on disk: an update to each active registration, /// and an expiry notice to each lapsed one not told since it lapsed. pub(crate) struct Sends { authority: String, space: String, updates: Vec<(String, Json)>, notices: Vec<(Pair, Owed)>, } impl Sends { pub(crate) fn new(authority: &str, space: &str) -> Sends { Sends { authority: authority.to_string(), space: space.to_string(), updates: Vec::new(), notices: Vec::new(), } } /// What a change whose new `spaceRev` is `space_rev` owes each /// registration of `kept` at `now`, `update` to the active ones; the /// entries noting each expiry notice owed go in `entries`, to log with /// the change. fn tell( &mut self, kept: &Kept, update: Json, space_rev: &str, now: u64, entries: &mut Vec, ) { for (pair, r) in kept.registered.get(&self.space).into_iter().flatten() { if r.expires > now { let body = json!({ "space": self.space, "token": pair.1, "update": update }); self.updates.push((pair.0.clone(), body)); } else if !r.noticed && !self.notices.iter().any(|(p, _)| p == pair) { entries.push(noticed(&self.space, pair)); let owed = Owed::Expired { space_rev: space_rev.to_string(), lapse: r.expires, }; self.notices.push((pair.clone(), owed)); } } } /// Send them, in the background: each update one attempt, given up /// after `ANSWER_WAIT`, or at once if `UPDATES_WAITING` wait already; /// each expiry notice as "Notices" says. pub(crate) fn go(self, svc: &Shared) { for (endpoint, body) in self.updates { let Some(place) = svc.space_notify.updates.enter() else { continue; }; let svc = svc.clone(); crate::ops::spawn(async move { let _place = place; let _ = tokio::time::timeout( ANSWER_WAIT, post_to(&svc, &endpoint, NOTIFY_SPACE_UPDATE, &body), ) .await; }); } for (pair, owed) in self.notices { let attempt = svc.space_notify.attempts.fetch_add(1, Ordering::SeqCst); let job = Job::Notice { did: self.authority.clone(), space: self.space.clone(), pair, owed, n: 0, until: 0, once: Some(attempt), }; lock(&svc.space_notify.sending).insert(job.key()); crate::ops::spawn(send(svc.clone(), job, None)); } } } // ---- Removing a writer ------------------------------------------------------------------ /// Writers taken out of a space's writer set: the entries of the writer /// set (`space_authority`'s) and of this part's to log in the change's /// frame, in order, and what to send once it is on disk. pub(crate) struct Removal { pub changes: Vec, pub entries: Vec, pub sends: Sends, } /// `remove_writer(space, did)` for each of `dids`, as `st` holds the space /// `uri` (`spec/SPACES-SYNC.md`, "Removing a writer"): an entry there and /// not removed is marked removed with a new `spaceRev`, each after the one /// before, and the removal is sent to the space's registrations; an /// account with no entry, or one removed already, changes nothing. pub(crate) fn remove_writers<'a>( svc: &Service, st: &Store, uri: &str, dids: impl IntoIterator, ) -> Removal { let now = svc.space_notify.now(); let mut r = Removal { changes: Vec::new(), entries: Vec::new(), sends: Sends::new(&st.repo.did, uri), }; let Some(space) = st.authority.live(uri) else { return r; }; let mut prev = revision(space).map(str::to_string); let mut taken = HashSet::new(); for did in dids { if !space.writers.get(did).is_some_and(|w| !w.removed) || !taken.insert(did) { continue; } let space_rev = next_space_rev(now, prev.as_deref()); r.changes.push(writer_removed(uri, did, &space_rev)); let mut update = json!({ "$type": REPO_REMOVED, "repo": did, "spaceRev": space_rev }); if let Some(p) = &prev { update["prevSpaceRev"] = json!(p); } r.sends .tell(&st.notify, update, &space_rev, now, &mut r.entries); prev = Some(space_rev); } r } // ---- Registrations ---------------------------------------------------------------------- /// A challenge: 16 random bytes in base32, RFC 4648's alphabet in lower /// case, unpadded: 26 characters. fn challenge() -> String { const ALPHABET: &[u8; 32] = b"abcdefghijklmnopqrstuvwxyz234567"; let bytes: [u8; 16] = rand::random(); let mut out = String::with_capacity(26); let (mut acc, mut bits) = (0u32, 0u32); for b in bytes { acc = (acc << 8) | u32::from(b); bits += 8; while bits >= 5 { bits -= 5; out.push(ALPHABET[((acc >> bits) & 31) as usize] as char); } acc &= (1 << bits) - 1; } if bits > 0 { out.push(ALPHABET[((acc << (5 - bits)) & 31) as usize] as char); } out } /// Ask `endpoint` to confirm the registration of `token` for `space` /// (`spec/SPACES-SYNC.md`, "Registering"): confirmed by a `2xx` of /// `application/json`, a JSON object whose `challenge` is the one sent. /// Nothing is sent to an endpoint that is no endpoint, has a user name or /// password, or that the guard will not send to; a redirect is not /// followed, an answer is read up to `JSON_DOC_MAX` bytes, and given up /// after `ANSWER_WAIT`. pub(crate) async fn confirm(svc: &Service, space: &str, endpoint: &str, token: &str) -> bool { let Some(url) = xrpc_url(&Json::from(endpoint), CONFIRM) else { return false; }; let challenge = challenge(); let body = json!({ "space": space, "token": token, "challenge": challenge }); let request = svc .outbound .client() .post(url) .header(reqwest::header::CONTENT_TYPE, "application/json") .body(body.to_string()); let Ok(got) = svc .outbound .fetch_limited( crate::ops::Target::Space, request, crate::outbound::JSON_DOC_MAX, ANSWER_WAIT, ) .await else { return false; }; let json_typed = got .headers .get(reqwest::header::CONTENT_TYPE) .and_then(|v| v.to_str().ok()) .is_some_and(|t| { t.split(';') .next() .unwrap_or_default() .trim() .eq_ignore_ascii_case("application/json") }); (200..300).contains(&got.status) && json_typed && serde_json::from_slice::(&got.body) .ok() .is_some_and(|v| v.get("challenge").and_then(Json::as_str) == Some(challenge.as_str())) } /// Drop the registration of `endpoint` and `token` for `uri`, active or /// lapsed, if there is one, as a refusal at `authorizeSpaceSync`'s step 8 /// or 9 does; answered once that is on disk. pub(crate) async fn withdraw( a: &Account, uri: &str, endpoint: &str, token: &str, ) -> Result<(), XrpcError> { let pair = (endpoint.to_string(), token.to_string()); change(a, |st| { let held = st .notify .registered .get(uri) .is_some_and(|r| r.contains_key(&pair)); if held && !log(st, &[dropped(uri, &pair)]) { return crate::internal(); } Ok(()) }) .await } /// Make or renew the registration of `endpoint` and `token` for `sr`, to /// lapse at `expires` (milliseconds), as `authorizeSpaceSync`'s step 11 /// does; and answer the space's revision then, as its step 12 does. /// Answered once on disk. Refused as step 10 refuses if the space filled /// up since it was asked; and as the space is if it is not live. pub(crate) async fn register( svc: &Service, a: &Account, sr: &SpaceRef, endpoint: &str, token: &str, expires: u64, ) -> Result, XrpcError> { let uri = sr.uri(); let now = svc.space_notify.now(); let mut rev = None; change(a, |st| { let Some(space) = st.authority.live(&uri) else { return match st.authority.state(&uri) { SpaceState::Deleted => err(400, "SpaceDeleted", "Space has been deleted"), _ => not_found(), }; }; rev = revision(space).map(str::to_string); if st.notify.standing(&uri, endpoint, token, now) == Standing::Full { return too_many(); } if !log(st, &[registered(&uri, (endpoint, token), expires)]) { return crate::internal(); } Ok(()) }) .await?; Ok(rev) } pub(crate) fn too_many() -> Result { err( 400, "TooManyRegistrations", "The space has too many active registrations", ) } /// Make a change under the account's lock, answered once its log is on disk. async fn change( a: &Account, f: impl FnOnce(&mut Store) -> Result<(), XrpcError>, ) -> Result<(), XrpcError> { let (wal, written) = { let mut st = write(&a.store); f(&mut st)?; (st.wal.clone(), st.wal.written()) }; durable(wal, written).await?; Ok(()) } // ---- The writer set: listWriters --------------------------------------------------------- /// The space a space host's method names, and its authority's account: the /// credential, verified for the authority, must be of this space, and the /// authority an account here. The call pays its rate limits as the /// credential is verified, and a write checks the free space /// (`limits::guard`). async fn host_of( s: &Shared, call: &Call<'_>, space: &str, ) -> Result<(SpaceRef, Arc), XrpcError> { let Some(sr) = SpaceRef::parse(space) else { return invalid("space must be a valid space-ref"); }; if !presents_credential(call.headers) { return err(401, "MissingJwt", "Missing jwt"); } let credential = verify_space_credential(s, call, &sr.authority).await?; if credential.space != space { return err( 400, "InvalidCredential", "The credential is for another space", ); } crate::limits::guard(s, call, None, None)?; let Some(a) = s.account(&sr.authority) else { return not_found(); }; Ok((sr, a)) } /// `listWriters`: the writer set, in ascending order of `spaceRev`, a page /// at a time, each entry a `#repoWrite` or, removed, a `#repoRemoved`. async fn list_writers(s: &Shared, call: &Call<'_>, m: &'static Method) -> Result { let p = m .parse_params(call.params.iter().map(|(k, v)| (k.as_str(), v.as_str()))) .or_else(|e| invalid(e.0))?; let (sr, a) = host_of(s, call, required(&p, "space")?).await?; match status(&a) { Status::TakenDown => return err(400, "RepoTakendown", "Repo has been takendown"), Status::Deactivated => return err(400, "RepoDeactivated", "Repo has been deactivated"), Status::Active => {} } let limit = p.get("limit").and_then(Json::as_u64).unwrap_or(100) as usize; let cursor = p.get("cursor").and_then(Json::as_str); let (repos, wal) = { let st = read(&a.store); let Some(space) = st.authority.live(&sr.uri()) else { return not_found(); }; let mut page: Vec<(&String, &Writer)> = space .writers .iter() .filter(|(_, w)| cursor.is_none_or(|c| w.space_rev.as_str() > c)) .collect(); let by_space_rev = |x: &(&String, &Writer), y: &(&String, &Writer)| x.1.space_rev.cmp(&y.1.space_rev); if page.len() > limit { page.select_nth_unstable_by(limit, by_space_rev); page.truncate(limit); } page.sort_unstable_by(by_space_rev); let repos: Vec = page .into_iter() .map(|(did, w)| { if w.removed { json!({ "$type": REPO_REMOVED, "repo": did, "spaceRev": w.space_rev }) } else { json!({ "$type": REPO_WRITE, "repo": did, "repoRev": w.rev, "data": to_json(&V::Bytes(w.data.clone())), "spaceRev": w.space_rev }) } }) .collect(); (repos, st.wal.clone()) }; durable(wal.clone(), wal.written()).await?; let cursor = repos.last().map(|r| r["spaceRev"].clone()); let mut out = json!({ "repos": repos }); if let Some(last) = cursor { out["cursor"] = last; } Ok(Resp::Json(out)) } // ---- Deletion --------------------------------------------------------------------------- /// A live space of `st`'s account deleted: its registrations, lapsed ones /// too, dropped, each owed a deletion notice, kept in the notice queue in /// place of any kept for it and sent at once once the deletion is on disk /// (`poke`). The entries to log in the deletion's frame, which the /// deletion makes once the frame is written (`Kept::apply`); refused if /// the account cannot be marked for a start to load (`log_with`). pub(crate) fn space_deleted(svc: &Service, st: &Store, uri: &str) -> Result, XrpcError> { let now = svc.space_notify.now(); let Some(registered) = st.notify.registered.get(uri) else { return Ok(Vec::new()); }; if let Err(e) = st.ctx.eager.mark(&st.repo.did) { crate::ops::failed_for( crate::ops::Level::Error, "marking an account failed", &st.repo.did, e, ); return crate::internal(); } let at = Schedule { n: 0, due: now, until: now + NOTICE_HORIZON, }; let mut entries = vec![json!({ "t": EMPTIED, "space": uri })]; entries.extend( registered .keys() .map(|pair| notice(uri, pair, &Owed::Deleted, at)), ); Ok(entries) } #[cfg(test)] pub(crate) mod tests;