~ knotless Search/
↑↓ move↵ open⇧↵ all results
0
0
209 lines · 7.2 KB Raw History
//! 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);
    }
}