chadtmiller.com/monolith
An atproto PDS
0
0
//! Single-use values (`spec/SPACES-CREDENTIALS.md`, "Single-use values"):
//! each taken once, and kept until a time, after which it is forgotten.
//! Spaces' credentials take delegation tokens and client attestations
//! through `SingleUse`, each `key` naming its namespace and value.
//!
//! `Spent` keeps them: a value is taken in memory, under the store's lock,
//! and its entry appended to `accounts.log` under that lock, so that of two
//! takers only one is answered true. The caller answers only once the log is
//! on disk that far, waited for with no lock held. Values are kept as their
//! SHA-256, so that what a client sends bounds nothing kept; each is
//! forgotten once its time has passed, in memory and when the log is
//! replayed.
use crate::Service;
use pds_store::Wal;
use serde_json::{Value as Json, json};
use sha2::{Digest, Sha256};
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};
use std::hash::Hash;
use std::sync::{Mutex, PoisonError};
/// The kind of `accounts.log` entry a value taken is kept in.
pub(crate) const ENTRY: &str = "used";
/// A record of single-use values.
pub(crate) trait SingleUse {
/// Take `key` until `expiry`, in seconds since the epoch: true if it was
/// not taken before, and it is then recorded; false if it was. A value
/// recorded is in `accounts.log` once this answers: the caller answers
/// only once that log is on disk up to there.
fn check_and_record(&self, key: &str, expiry: u64) -> bool;
}
impl SingleUse for Service {
fn check_and_record(&self, key: &str, expiry: u64) -> bool {
self.single_use
.take(&self.log, key, self.sessions.now(), expiry)
}
}
/// Values held until a time each, forgotten once it has passed.
pub(crate) struct Held<K> {
/// Until when each is held, in seconds since the epoch.
until: HashMap<K, u64>,
/// The same, soonest first, to forget them as their times pass.
queue: BinaryHeap<Reverse<(u64, K)>>,
}
impl<K> Default for Held<K> {
fn default() -> Self {
Held {
until: HashMap::new(),
queue: BinaryHeap::new(),
}
}
}
impl<K: Clone + Hash + Ord> Held<K> {
/// Forget every value whose time has passed by `now`.
pub fn forget(&mut self, now: u64) {
while let Some(Reverse((t, _))) = self.queue.peek()
&& *t <= now
{
let Some(Reverse((t, k))) = self.queue.pop() else {
break;
};
if self.until.get(&k) == Some(&t) {
self.until.remove(&k);
}
}
}
/// Whether `k` is held at `now`.
pub fn holds(&self, k: &K, now: u64) -> bool {
self.until.get(k).is_some_and(|t| *t > now)
}
/// Hold `k` until `until`, or longer if it is held longer already.
pub fn hold(&mut self, k: K, until: u64) {
let t = self.until.entry(k.clone()).or_insert(0);
if until > *t {
*t = until;
self.queue.push(Reverse((until, k)));
}
}
/// Every value held at `now`, and until when.
#[cfg(test)]
pub fn snapshot(&self, now: u64) -> std::collections::BTreeMap<K, u64> {
self.until
.iter()
.filter(|(_, t)| **t > now)
.map(|(k, t)| (k.clone(), *t))
.collect()
}
}
/// The single-use values the server took.
#[derive(Default)]
pub(crate) struct Spent {
held: Mutex<Held<[u8; 32]>>,
}
impl Spent {
/// Take `key` at `now` until `until`, logging it in `log`: true if it was
/// not held. A value whose time has passed already is not kept.
pub fn take(&self, log: &Wal, key: &str, now: u64, until: u64) -> bool {
let digest: [u8; 32] = Sha256::digest(key.as_bytes()).into();
let mut h = self.held.lock().unwrap_or_else(PoisonError::into_inner);
h.forget(now);
if h.holds(&digest, now) {
return false;
}
if until > now {
// One the log could not take is not held, and not taken.
if let Err(e) =
log.append(&[json!({ "t": ENTRY, "v": hex::encode(digest), "until": until })])
{
crate::ops::failed("keeping a single-use value failed", e);
return false;
}
h.hold(digest, until);
}
true
}
/// Replay an entry `take` logged, at `now`: one whose time has passed is forgotten.
pub fn replay(&self, e: &Json, now: u64) -> Result<(), String> {
let (Some(v), Some(until)) = (e["v"].as_str(), e["until"].as_u64()) else {
return Err(format!("a used value with no v or until: {e}"));
};
let digest: [u8; 32] = hex::decode(v)
.ok()
.and_then(|d| d.try_into().ok())
.ok_or_else(|| format!("a used value that is not a digest: {e}"))?;
if until > now {
self.held
.lock()
.unwrap_or_else(PoisonError::into_inner)
.hold(digest, until);
}
Ok(())
}
/// Every value held at `now`, to compare across restarts.
#[cfg(test)]
pub fn snapshot(&self, now: u64) -> std::collections::BTreeMap<[u8; 32], u64> {
self.held
.lock()
.unwrap_or_else(PoisonError::into_inner)
.snapshot(now)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn scratch_log(name: &str) -> (std::path::PathBuf, Wal) {
let dir = crate::testing::scratch(name);
let (wal, _) = Wal::open(&dir.join("log"), None).unwrap();
(dir, wal)
}
#[test]
fn values_are_taken_once_until_their_time() {
let (dir, log) = scratch_log("single-use");
let s = Spent::default();
assert!(s.take(&log, "a", 100, 300));
assert!(!s.take(&log, "a", 299, 400));
assert!(s.take(&log, "b", 100, 300));
// Once its time has passed it is forgotten, and may be taken again.
assert!(s.take(&log, "a", 300, 500));
assert!(!s.take(&log, "a", 499, 600));
// One whose time has passed already is taken, and kept by nothing.
let n = log.written();
assert!(s.take(&log, "c", 100, 100));
assert!(s.take(&log, "c", 100, 100));
assert_eq!(log.written(), n);
assert_eq!(s.snapshot(450).len(), 1);
let _ = std::fs::remove_dir_all(dir);
}
#[test]
fn replayed_values_hold_until_their_time() {
let (dir, log) = scratch_log("single-use-replay");
let s = Spent::default();
s.take(&log, "a", 0, 100);
s.take(&log, "b", 0, 1000);
log.wait(log.written()).unwrap();
drop(log);
let (log, frames) = Wal::open(&dir.join("log"), None).unwrap();
let again = Spent::default();
for e in frames.iter().flatten().chain(frames.iter().flatten()) {
again.replay(e, 500).unwrap();
}
assert!(again.take(&log, "a", 500, 600));
assert!(!again.take(&log, "b", 500, 600));
for bad in [
json!({ "t": ENTRY }),
json!({ "t": ENTRY, "v": "short", "until": 5 }),
json!({ "t": ENTRY, "v": hex::encode([0u8; 32]) }),
] {
assert!(again.replay(&bad, 0).is_err(), "{bad}");
}
let _ = std::fs::remove_dir_all(dir);
}
}