acyclic_fs/kernel/
read.rs

1//! Sparse authenticated reads with exact implementation-work receipts.
2
3use super::frontier;
4use super::persistent_batch;
5use super::tree_mutation::TreeFormat;
6use super::{
7    CanonicalDecodeError, DecodeLimits, LogicalName, TreeEntry, TreePage, decode_tree_page,
8};
9use crate::async_storage::AsyncObjectStore;
10use crate::cancellation::CancellationToken;
11use crate::performance::{OperationFailure, WorkBudget, WorkCounters, WorkError};
12use crate::storage::{
13    ObjectId, ObjectKind, ObjectRead, ObjectReceipt, ObjectStore, ObjectStoreError,
14};
15use std::collections::HashSet;
16use thiserror::Error;
17
18/// Exact lookup result and work evidence.
19#[derive(Clone, Debug, Eq, PartialEq)]
20pub struct TreeLookup {
21    /// Matching entry, or explicit authenticated absence.
22    pub entry: Option<TreeEntry>,
23    /// Exact kernel-visible work performed.
24    pub work: WorkCounters,
25}
26
27/// Original-order results from one shared authenticated frontier batch.
28#[derive(Clone, Debug, Eq, PartialEq)]
29pub struct TreeBatchLookup {
30    /// One explicit present/absent result for every requested name.
31    pub entries: Vec<Option<TreeEntry>>,
32    /// Exact shared traversal, backend, copy, and allocation work.
33    pub work: WorkCounters,
34}
35
36/// Looks up an arbitrary name batch while reading each distinct tree frontier once.
37///
38/// Input order and duplicate requests are preserved in the returned vector.
39/// Internally, borrowed keys are deterministically ordered and queries sharing
40/// ancestors or leaves are routed together.
41///
42/// # Errors
43///
44/// Rejects empty/oversized batches, malformed routing, cycles, invalid limits,
45/// backend failures, and work outside the admitted budget.
46pub fn lookup_tree_entries<S: crate::ImmediateObjectStore>(
47    store: &S,
48    root: ObjectId,
49    names: &[LogicalName],
50    maximum_queries: u32,
51    limits: DecodeLimits,
52    budget: WorkBudget,
53) -> Result<TreeBatchLookup, TreeReadFailure> {
54    persistent_batch::lookup::<S, TreeFormat>(store, root, names, maximum_queries, limits, budget)
55        .map(to_batch)
56        .map_err(map_batch_failure)
57}
58
59/// Asynchronously executes the same shared-frontier batch as [`lookup_tree_entries`].
60///
61/// # Errors
62///
63/// Returns the same failures, including cancellation before every backend read.
64pub async fn lookup_tree_entries_async<S: AsyncObjectStore>(
65    store: &S,
66    root: ObjectId,
67    names: &[LogicalName],
68    maximum_queries: u32,
69    limits: DecodeLimits,
70    budget: WorkBudget,
71    cancellation: &CancellationToken,
72) -> Result<TreeBatchLookup, TreeReadFailure> {
73    persistent_batch::lookup_async::<S, TreeFormat>(
74        store,
75        root,
76        names,
77        maximum_queries,
78        limits,
79        budget,
80        cancellation,
81    )
82    .await
83    .map(to_batch)
84    .map_err(map_batch_failure)
85}
86
87fn to_batch(receipt: persistent_batch::Receipt<TreeEntry>) -> TreeBatchLookup {
88    TreeBatchLookup {
89        entries: receipt.values,
90        work: receipt.work,
91    }
92}
93
94fn map_batch_failure(failure: persistent_batch::Failure) -> TreeReadFailure {
95    OperationFailure::new(map_batch_error(failure.error), *failure.work)
96}
97
98fn map_batch_error(error: persistent_batch::Error) -> TreeReadError {
99    match error {
100        persistent_batch::Error::Cancelled => TreeReadError::Cancelled,
101        persistent_batch::Error::Empty => TreeReadError::EmptyBatch,
102        persistent_batch::Error::TooManyQueries => TreeReadError::TooManyQueries,
103        persistent_batch::Error::WrongRootKind => TreeReadError::WrongRootKind,
104        persistent_batch::Error::InvalidLimits => TreeReadError::InvalidHeightLimit,
105        persistent_batch::Error::HeightExceeded => TreeReadError::HeightExceeded,
106        persistent_batch::Error::CycleOrAlias => TreeReadError::Cycle,
107        persistent_batch::Error::ChildBoundsMismatch => TreeReadError::ChildBoundsMismatch,
108        persistent_batch::Error::InvalidRouting => TreeReadError::InvalidRouting,
109        persistent_batch::Error::AllocationFailed => TreeReadError::AllocationFailed,
110        persistent_batch::Error::Storage(error) => error.into(),
111        persistent_batch::Error::Decode(error) => error.into(),
112        persistent_batch::Error::Work(error) => error.into(),
113    }
114}
115
116/// Looks up one exact name through an authenticated directory B+tree.
117///
118/// # Errors
119///
120/// Fails on wrong object classes, corrupt pages, cycles, excessive height,
121/// backend failures, or a work budget that would be exceeded. The function
122/// never enumerates unrelated leaf entries or reads file bodies.
123pub fn lookup_tree_entry<S: ObjectStore>(
124    store: &S,
125    root: ObjectId,
126    name: &LogicalName,
127    limits: DecodeLimits,
128    budget: WorkBudget,
129) -> Result<TreeLookup, TreeReadFailure> {
130    let mut machine = LookupMachine::new(root, name, limits, budget)?;
131    frontier::drive_sync(store, &mut machine)
132}
133
134/// Asynchronous tree lookup driven by the same semantic machine as the native
135/// synchronous fast path.
136///
137/// # Errors
138///
139/// Returns the same typed semantic, storage, decode, work, and cancellation
140/// failures as [`lookup_tree_entry`].
141pub async fn lookup_tree_entry_async<S: AsyncObjectStore>(
142    store: &S,
143    root: ObjectId,
144    name: &LogicalName,
145    limits: DecodeLimits,
146    budget: WorkBudget,
147    cancellation: &CancellationToken,
148) -> Result<TreeLookup, TreeReadFailure> {
149    let mut machine = LookupMachine::new(root, name, limits, budget)?;
150    frontier::drive_async(store, &mut machine, cancellation).await
151}
152
153struct LookupMachine<'a> {
154    name: &'a LogicalName,
155    limits: DecodeLimits,
156    budget: WorkBudget,
157    page: ObjectId,
158    expected_lower: Option<LogicalName>,
159    expected_upper: Option<LogicalName>,
160    visited: HashSet<ObjectId>,
161    work: WorkCounters,
162}
163
164impl<'a> LookupMachine<'a> {
165    fn new(
166        root: ObjectId,
167        name: &'a LogicalName,
168        limits: DecodeLimits,
169        budget: WorkBudget,
170    ) -> Result<Self, TreeReadFailure> {
171        if root.kind != ObjectKind::TreePage {
172            return Err(tree_failed(
173                TreeReadError::WrongRootKind,
174                WorkCounters::default(),
175            ));
176        }
177        if !limits.page_limits_valid(1) {
178            return Err(tree_failed(
179                TreeReadError::InvalidHeightLimit,
180                WorkCounters::default(),
181            ));
182        }
183
184        Ok(Self {
185            name,
186            limits,
187            budget,
188            page: root,
189            expected_lower: None,
190            expected_upper: None,
191            visited: HashSet::new(),
192            work: WorkCounters::default(),
193        })
194    }
195
196    fn prepare_read(&mut self) -> Result<frontier::ReadRequest, TreeReadFailure> {
197        if self.visited.len() >= usize::from(self.limits.maximum_page_height) {
198            return Err(tree_failed(TreeReadError::HeightExceeded, self.work));
199        }
200        if !self.visited.insert(self.page) {
201            return Err(tree_failed(TreeReadError::Cycle, self.work));
202        }
203        let semantic = WorkCounters {
204            page_reads: 1,
205            ..WorkCounters::default()
206        };
207        let prospective = self
208            .work
209            .checked_add(semantic)
210            .map_err(|error| tree_failed(TreeReadError::Work(error), self.work))?;
211        let remaining = prospective
212            .remaining(self.budget)
213            .map_err(|error| tree_failed(TreeReadError::Work(error), self.work))?;
214        Ok(frontier::ReadRequest {
215            page: self.page,
216            maximum_bytes: self.limits.maximum_page_object_bytes(),
217            remaining,
218            prospective,
219        })
220    }
221
222    fn accept(
223        &mut self,
224        prospective: WorkCounters,
225        receipt: &ObjectReceipt<ObjectRead>,
226    ) -> Result<Option<TreeLookup>, TreeReadFailure> {
227        self.work = prospective
228            .checked_add(receipt.work)
229            .map_err(|error| tree_failed(TreeReadError::Work(error), prospective))?;
230        self.work
231            .verify(self.budget)
232            .map_err(|error| tree_failed(TreeReadError::Work(error), self.work))?;
233
234        match decode_tree_page(&receipt.value, self.limits)
235            .map_err(|error| tree_failed(TreeReadError::Decode(error), self.work))?
236        {
237            TreePage::Leaf(entries) => {
238                validate_leaf_bounds(
239                    &entries,
240                    self.expected_lower.as_ref(),
241                    self.expected_upper.as_ref(),
242                )
243                .map_err(|error| tree_failed(error, self.work))?;
244                let entry = entries
245                    .binary_search_by(|entry| entry.name.cmp(self.name))
246                    .ok()
247                    .and_then(|index| entries.get(index).cloned());
248                Ok(Some(TreeLookup {
249                    entry,
250                    work: self.work,
251                }))
252            }
253            TreePage::Internal(children) => {
254                validate_internal_bounds(
255                    &children,
256                    self.expected_lower.as_ref(),
257                    self.expected_upper.as_ref(),
258                )
259                .map_err(|error| tree_failed(error, self.work))?;
260                let child_index = children.partition_point(|child| child.first_name <= *self.name);
261                let selected = child_index.saturating_sub(1);
262                let child = children
263                    .get(selected)
264                    .ok_or_else(|| tree_failed(TreeReadError::InvalidRouting, self.work))?
265                    .clone();
266                self.expected_lower = Some(child.first_name);
267                self.expected_upper = children
268                    .get(selected + 1)
269                    .map(|next| next.first_name.clone())
270                    .or(self.expected_upper.take());
271                self.page = child.page;
272                Ok(None)
273            }
274        }
275    }
276}
277
278impl frontier::Machine for LookupMachine<'_> {
279    type Output = TreeLookup;
280    type Failure = TreeReadFailure;
281
282    fn complete(&mut self) -> Result<Option<Self::Output>, Self::Failure> {
283        Ok(None)
284    }
285
286    fn prepare_read(&mut self) -> Result<frontier::ReadRequest, Self::Failure> {
287        LookupMachine::prepare_read(self)
288    }
289
290    fn accept(
291        &mut self,
292        prospective: WorkCounters,
293        receipt: &ObjectReceipt<ObjectRead>,
294    ) -> Result<Option<Self::Output>, Self::Failure> {
295        LookupMachine::accept(self, prospective, receipt)
296    }
297
298    fn storage_failure(
299        &self,
300        prospective: WorkCounters,
301        failure: crate::storage::ObjectFailure,
302    ) -> Self::Failure {
303        match prospective.checked_add(*failure.work) {
304            Ok(spent) => tree_failed(TreeReadError::Storage(failure.error), spent),
305            Err(error) => tree_failed(TreeReadError::Work(error), prospective),
306        }
307    }
308
309    fn cancelled(&self) -> Self::Failure {
310        tree_failed(TreeReadError::Cancelled, self.work)
311    }
312}
313
314/// Sparse authenticated tree failure retaining exact spent work.
315pub type TreeReadFailure = OperationFailure<TreeReadError>;
316
317fn tree_failed(error: TreeReadError, work: WorkCounters) -> TreeReadFailure {
318    OperationFailure::new(error, work)
319}
320
321fn validate_leaf_bounds(
322    entries: &[TreeEntry],
323    lower: Option<&LogicalName>,
324    upper: Option<&LogicalName>,
325) -> Result<(), TreeReadError> {
326    if let Some(lower) = lower
327        && entries.first().map(|entry| &entry.name) != Some(lower)
328    {
329        return Err(TreeReadError::ChildBoundsMismatch);
330    }
331    if let Some(upper) = upper
332        && entries.last().is_some_and(|entry| entry.name >= *upper)
333    {
334        return Err(TreeReadError::ChildBoundsMismatch);
335    }
336    Ok(())
337}
338
339fn validate_internal_bounds(
340    children: &[super::TreeChild],
341    lower: Option<&LogicalName>,
342    upper: Option<&LogicalName>,
343) -> Result<(), TreeReadError> {
344    if let Some(lower) = lower
345        && children.first().map(|child| &child.first_name) != Some(lower)
346    {
347        return Err(TreeReadError::ChildBoundsMismatch);
348    }
349    if let Some(upper) = upper
350        && children
351            .last()
352            .is_some_and(|child| child.first_name >= *upper)
353    {
354        return Err(TreeReadError::ChildBoundsMismatch);
355    }
356    Ok(())
357}
358
359/// Sparse authenticated tree-read failures.
360#[derive(Debug, Error)]
361pub enum TreeReadError {
362    /// Cooperative cancellation occurred before the next storage boundary.
363    #[error("tree lookup was cancelled")]
364    Cancelled,
365    /// Batch lookup requires at least one requested name.
366    #[error("tree lookup batch is empty")]
367    EmptyBatch,
368    /// Batch lookup exceeds its explicit query limit.
369    #[error("tree lookup batch exceeds its admitted query bound")]
370    TooManyQueries,
371    /// Root object is not an authenticated tree page.
372    #[error("tree lookup root is not a tree page")]
373    WrongRootKind,
374    /// Page-height bound must be positive.
375    #[error("tree page height limit must be non-zero")]
376    InvalidHeightLimit,
377    /// A child graph referenced an ancestor.
378    #[error("tree page graph contains a cycle")]
379    Cycle,
380    /// Traversal did not reach a leaf within its hard height bound.
381    #[error("tree page height exceeds its admitted bound")]
382    HeightExceeded,
383    /// Internal routing state was structurally impossible.
384    #[error("tree page routing invariant failed")]
385    InvalidRouting,
386    /// Parent routing bounds do not match the authenticated child frontier.
387    #[error("tree child bounds do not match its page")]
388    ChildBoundsMismatch,
389    /// A bounded batch scratch allocation failed.
390    #[error("tree lookup allocation failed")]
391    AllocationFailed,
392    /// Stored page exceeds the decode/work bound.
393    #[error("tree page has {observed} bytes; maximum is {maximum}")]
394    PageTooLarge {
395        /// Observed canonical bytes.
396        observed: u64,
397        /// Admitted maximum.
398        maximum: u64,
399    },
400    /// Immutable-object backend failed.
401    #[error(transparent)]
402    Storage(#[from] ObjectStoreError),
403    /// Canonical page failed decoding or semantic validation.
404    #[error(transparent)]
405    Decode(#[from] CanonicalDecodeError),
406    /// Exact implementation work exceeded or overflowed its budget.
407    #[error(transparent)]
408    Work(#[from] WorkError),
409}
410
411#[cfg(all(test, feature = "memory"))]
412#[path = "tests/read.rs"]
413mod tests;
acyclic_fs/kernel/read.rs

acyclic_fs/kernel/
read.rs
