acyclic_fs/kernel/
mutation.rs

1//! Bounded atomic mutation contracts and shared-prefix execution plans.
2
3use super::{FileRecord, MetadataField, NamespacePath};
4use crate::foundation::FileId;
5use crate::model::VolumeLimits;
6use crate::performance::{OperationFailure, WorkBudget, WorkCounters, WorkError};
7use crate::storage::{ObjectId, ObjectKind};
8use std::cell::Cell;
9use std::mem::size_of;
10use thiserror::Error;
11
12/// One ordered mutation within a single-volume atomic batch.
13#[derive(Clone, Debug, Eq, PartialEq)]
14pub enum Mutation {
15    /// Binds a new path-independent file record at an absent path.
16    Create {
17        /// New namespace path.
18        path: NamespacePath,
19        /// Complete immutable initial record.
20        record: FileRecord,
21    },
22    /// Restores one exact immutable record at a path while preserving any
23    /// additional live hard-link bindings to the same identity. Unlike
24    /// `Create`, the identity may already exist in the candidate generation.
25    Restore {
26        /// Namespace path to restore.
27        path: NamespacePath,
28        /// Exact source record. Its link count is adapted to the live binding
29        /// topology; all other representable facts are restored verbatim.
30        record: FileRecord,
31    },
32    /// Removes one namespace binding.
33    Remove {
34        /// Existing namespace path.
35        path: NamespacePath,
36        /// Optional exact file identity precondition.
37        expected_file_id: MetadataField<FileId>,
38    },
39    /// Atomically moves one binding within the volume.
40    Rename {
41        /// Existing source path.
42        source: NamespacePath,
43        /// Destination path.
44        destination: NamespacePath,
45        /// Whether an existing destination may be replaced.
46        replace: bool,
47    },
48    /// Creates another namespace binding to an existing non-directory file.
49    Link {
50        /// Existing source path.
51        source: NamespacePath,
52        /// New link path.
53        destination: NamespacePath,
54    },
55    /// Replaces the complete canonical metadata object.
56    SetMetadata {
57        /// Existing path.
58        path: NamespacePath,
59        /// Authenticated metadata object.
60        metadata: ObjectId,
61    },
62    /// Replaces one logical byte interval with authenticated content.
63    Write {
64        /// Existing regular-file path.
65        path: NamespacePath,
66        /// Inclusive destination offset.
67        offset: u64,
68        /// Positive byte count.
69        length: u64,
70        /// Authenticated blob containing source bytes.
71        content: ObjectId,
72        /// Inclusive source offset in `content`.
73        content_offset: u64,
74    },
75    /// Validates that one existing path names a regular file without changing it.
76    ValidateRegular {
77        /// Existing regular-file path.
78        path: NamespacePath,
79    },
80    /// Changes logical file length while preserving sparse semantics.
81    Resize {
82        /// Existing regular-file path.
83        path: NamespacePath,
84        /// New logical byte length.
85        logical_bytes: u64,
86    },
87    /// Replaces a range with a hole or physically allocated zeros.
88    ZeroRange {
89        /// Existing regular-file path.
90        path: NamespacePath,
91        /// Inclusive logical offset.
92        offset: u64,
93        /// Positive byte count.
94        length: u64,
95        /// Preserve physical allocation instead of punching a hole.
96        allocated: bool,
97        /// Whether the replacement may extend logical file length.
98        extend: bool,
99    },
100    /// Allocates sparse holes without replacing existing content.
101    Preallocate {
102        /// Existing regular-file path.
103        path: NamespacePath,
104        /// Inclusive logical offset.
105        offset: u64,
106        /// Positive byte count.
107        length: u64,
108        /// Preserve logical file length.
109        keep_size: bool,
110    },
111    /// Clones one logical range without materializing unchanged content.
112    CloneRange {
113        /// Existing source regular file.
114        source: NamespacePath,
115        /// Inclusive source offset.
116        source_offset: u64,
117        /// Existing destination regular file.
118        destination: NamespacePath,
119        /// Inclusive destination offset.
120        destination_offset: u64,
121        /// Positive byte count.
122        length: u64,
123    },
124    /// Mutates one existing file through its stable path-independent identity.
125    File {
126        /// Existing authenticated file-table identity.
127        file_id: FileId,
128        /// Ordered record mutation.
129        mutation: FileMutation,
130    },
131    /// Clones one logical range between stable file identities.
132    CloneFileRange {
133        /// Existing source regular-file identity.
134        source_file_id: FileId,
135        /// Inclusive source offset.
136        source_offset: u64,
137        /// Existing destination regular-file identity.
138        destination_file_id: FileId,
139        /// Inclusive destination offset.
140        destination_offset: u64,
141        /// Positive byte count.
142        length: u64,
143    },
144}
145
146/// One ordered mutation of an existing path-independent file record.
147#[derive(Clone, Debug, Eq, PartialEq)]
148pub enum FileMutation {
149    /// Replaces one authenticated file record without changing its live bindings.
150    /// The current identity and link count remain authoritative.
151    ReplaceRecord {
152        /// Complete replacement record for the same file identity and kind.
153        record: FileRecord,
154    },
155    /// Replaces the complete canonical metadata object.
156    SetMetadata {
157        /// Authenticated metadata object.
158        metadata: ObjectId,
159    },
160    /// Replaces one logical byte interval with authenticated content.
161    Write {
162        /// Inclusive destination offset.
163        offset: u64,
164        /// Positive byte count.
165        length: u64,
166        /// Authenticated blob containing source bytes.
167        content: ObjectId,
168        /// Inclusive source offset in `content`.
169        content_offset: u64,
170    },
171    /// Validates that the existing identity is a regular file without changing it.
172    ValidateRegular,
173    /// Changes logical file length while preserving sparse semantics.
174    Resize {
175        /// New logical byte length.
176        logical_bytes: u64,
177    },
178    /// Replaces a range with a hole or physically allocated zeros.
179    ZeroRange {
180        /// Inclusive logical offset.
181        offset: u64,
182        /// Positive byte count.
183        length: u64,
184        /// Preserve physical allocation instead of punching a hole.
185        allocated: bool,
186        /// Whether the replacement may extend logical file length.
187        extend: bool,
188    },
189    /// Allocates sparse holes without replacing existing content.
190    Preallocate {
191        /// Inclusive logical offset.
192        offset: u64,
193        /// Positive byte count.
194        length: u64,
195        /// Preserve logical file length.
196        keep_size: bool,
197    },
198}
199
200impl Mutation {
201    pub(crate) fn paths(&self) -> Option<[&NamespacePath; 2]> {
202        let paths = match self {
203            Self::Create { path, .. }
204            | Self::Restore { path, .. }
205            | Self::Remove { path, .. }
206            | Self::SetMetadata { path, .. }
207            | Self::Write { path, .. }
208            | Self::ValidateRegular { path }
209            | Self::Resize { path, .. }
210            | Self::ZeroRange { path, .. }
211            | Self::Preallocate { path, .. } => [path, path],
212            Self::Rename {
213                source,
214                destination,
215                ..
216            }
217            | Self::Link {
218                source,
219                destination,
220            }
221            | Self::CloneRange {
222                source,
223                destination,
224                ..
225            } => [source, destination],
226            Self::File { .. } | Self::CloneFileRange { .. } => return None,
227        };
228        Some(paths)
229    }
230
231    fn validate(&self) -> Result<(), MutationPlanError> {
232        if let Some([first, second]) = self.paths()
233            && (first.is_root() || second.is_root())
234        {
235            return Err(MutationPlanError::RootMutation);
236        }
237        match self {
238            Self::Create { record, .. } | Self::Restore { record, .. }
239                if record.validate().is_err() =>
240            {
241                Err(MutationPlanError::InvalidInitialRecord)
242            }
243            Self::File {
244                file_id,
245                mutation: FileMutation::ReplaceRecord { record },
246            } if record.validate().is_err() || record.file_id != *file_id => {
247                Err(MutationPlanError::InvalidInitialRecord)
248            }
249            Self::Rename {
250                source,
251                destination,
252                ..
253            }
254            | Self::Link {
255                source,
256                destination,
257            } if source == destination => Err(MutationPlanError::SameSourceAndDestination),
258            Self::Write {
259                offset,
260                length,
261                content,
262                content_offset,
263                ..
264            }
265            | Self::File {
266                mutation:
267                    FileMutation::Write {
268                        offset,
269                        length,
270                        content,
271                        content_offset,
272                    },
273                ..
274            } => {
275                validate_range(*offset, *length)?;
276                validate_range(*content_offset, *length)?;
277                if content.kind != ObjectKind::Blob {
278                    return Err(MutationPlanError::WrongContentKind);
279                }
280                Ok(())
281            }
282            Self::ZeroRange { offset, length, .. } | Self::Preallocate { offset, length, .. } => {
283                validate_range(*offset, *length)
284            }
285            Self::CloneRange {
286                source_offset,
287                destination_offset,
288                length,
289                ..
290            }
291            | Self::CloneFileRange {
292                source_offset,
293                destination_offset,
294                length,
295                ..
296            } => {
297                validate_range(*source_offset, *length)?;
298                validate_range(*destination_offset, *length)
299            }
300            Self::SetMetadata { metadata, .. } if metadata.kind != ObjectKind::Metadata => {
301                Err(MutationPlanError::WrongMetadataKind)
302            }
303            Self::File {
304                mutation: FileMutation::SetMetadata { metadata },
305                ..
306            } if metadata.kind != ObjectKind::Metadata => Err(MutationPlanError::WrongMetadataKind),
307            Self::File {
308                mutation:
309                    FileMutation::ZeroRange { offset, length, .. }
310                    | FileMutation::Preallocate { offset, length, .. },
311                ..
312            } => validate_range(*offset, *length),
313            Self::Create { .. }
314            | Self::Restore { .. }
315            | Self::Remove { .. }
316            | Self::Rename { .. }
317            | Self::Link { .. }
318            | Self::SetMetadata { .. }
319            | Self::ValidateRegular { .. }
320            | Self::Resize { .. }
321            | Self::File {
322                mutation:
323                    FileMutation::SetMetadata { .. }
324                    | FileMutation::ReplaceRecord { .. }
325                    | FileMutation::ValidateRegular
326                    | FileMutation::Resize { .. },
327                ..
328            } => Ok(()),
329        }
330    }
331}
332
333#[derive(Clone, Copy, Debug, Eq, PartialEq)]
334struct PathUse {
335    operation: u32,
336    endpoint: u8,
337}
338
339/// One normalized mutation batch and its shared-prefix execution plan.
340#[derive(Clone, Debug, Eq, PartialEq)]
341pub struct MutationPlan {
342    operations: Vec<Mutation>,
343    ordered_paths: Vec<PathUse>,
344    path_nodes: u64,
345    retained_allocation_bytes: u64,
346    work: WorkCounters,
347}
348
349impl MutationPlan {
350    /// Compiles an ordered batch once before any immutable page is written.
351    ///
352    /// # Errors
353    ///
354    /// Rejects empty/excessive batches, invalid roots/object classes/ranges,
355    /// index overflow, and work outside the admitted budget.
356    pub fn compile(
357        operations: Vec<Mutation>,
358        limits: VolumeLimits,
359        budget: WorkBudget,
360    ) -> Result<Self, MutationPlanFailure> {
361        if operations.is_empty() {
362            return Err(OperationFailure::before_work(MutationPlanError::Empty));
363        }
364        if u32::try_from(operations.len()).unwrap_or(u32::MAX) > limits.maximum_mutations_per_batch
365        {
366            return Err(OperationFailure::before_work(
367                MutationPlanError::TooManyMutations,
368            ));
369        }
370        let mut work = WorkCounters::default();
371        for operation in &operations {
372            operation
373                .validate()
374                .map_err(|error| OperationFailure::new(error, work))?;
375        }
376
377        let maximum_uses = path_use_count(&operations)
378            .ok_or_else(|| OperationFailure::new(MutationPlanError::IndexOverflow, work))?;
379        let allocation_bytes = maximum_uses
380            .checked_mul(size_of::<PathUse>())
381            .map(crate::foundation::usize_to_u64)
382            .ok_or_else(|| OperationFailure::new(MutationPlanError::IndexOverflow, work))?;
383        let mut ordered_paths = Vec::new();
384        if maximum_uses != 0 {
385            let attempted = work
386                .checked_add(WorkCounters {
387                    allocation_operations: 1,
388                    ..WorkCounters::default()
389                })
390                .map_err(|error| OperationFailure::new(error.into(), work))?;
391            attempted
392                .verify(budget)
393                .map_err(|error| OperationFailure::new(error.into(), work))?;
394            let mut allocated = attempted;
395            allocated.peak_allocation_bytes = allocated.peak_allocation_bytes.max(allocation_bytes);
396            allocated
397                .verify(budget)
398                .map_err(|error| OperationFailure::new(error.into(), work))?;
399            ordered_paths.try_reserve_exact(maximum_uses).map_err(|_| {
400                OperationFailure::new(MutationPlanError::AllocationFailed, attempted)
401            })?;
402            work = allocated;
403        }
404        for (index, operation) in operations.iter().enumerate() {
405            let operation_index = u32::try_from(index)
406                .map_err(|_| OperationFailure::new(MutationPlanError::IndexOverflow, work))?;
407            let Some(paths) = operation.paths() else {
408                continue;
409            };
410            ordered_paths.push(PathUse {
411                operation: operation_index,
412                endpoint: 0,
413            });
414            if paths[1] != paths[0] {
415                ordered_paths.push(PathUse {
416                    operation: operation_index,
417                    endpoint: 1,
418                });
419            }
420        }
421        let comparisons = Cell::new(0_u64);
422        ordered_paths.sort_unstable_by(|left, right| {
423            comparisons.set(comparisons.get().saturating_add(1));
424            path_for(&operations, *left)
425                .cmp(path_for(&operations, *right))
426                .then_with(|| left.operation.cmp(&right.operation))
427                .then_with(|| left.endpoint.cmp(&right.endpoint))
428        });
429        let mut path_nodes = 1_u64;
430        let mut prior: Option<&NamespacePath> = None;
431        let mut component_visits = 0_u64;
432        for path_use in &ordered_paths {
433            let path = path_for(&operations, *path_use);
434            component_visits = component_visits
435                .checked_add(u64::try_from(path.depth()).unwrap_or(u64::MAX))
436                .ok_or_else(|| OperationFailure::new(MutationPlanError::IndexOverflow, work))?;
437            let shared = prior.map_or(0, |previous| shared_prefix(previous, path));
438            path_nodes = path_nodes
439                .checked_add(u64::try_from(path.depth() - shared).unwrap_or(u64::MAX))
440                .ok_or_else(|| OperationFailure::new(MutationPlanError::IndexOverflow, work))?;
441            prior = Some(path);
442        }
443        work = work
444            .checked_add(WorkCounters {
445                items_examined: component_visits
446                    .checked_add(comparisons.get())
447                    .ok_or_else(|| OperationFailure::new(MutationPlanError::IndexOverflow, work))?,
448                ..WorkCounters::default()
449            })
450            .map_err(|error| OperationFailure::new(error.into(), work))?;
451        work.verify(budget)
452            .map_err(|error| OperationFailure::new(error.into(), work))?;
453        Ok(Self {
454            operations,
455            ordered_paths,
456            path_nodes,
457            retained_allocation_bytes: allocation_bytes,
458            work,
459        })
460    }
461
462    /// Ordered operations retained for atomic replay.
463    #[must_use]
464    pub fn operations(&self) -> &[Mutation] {
465        &self.operations
466    }
467
468    /// Borrowed operation endpoints in canonical path order.
469    ///
470    /// Repeated paths are retained because operation ordering remains semantic;
471    /// consumers can group adjacent equal paths without cloning names.
472    #[must_use]
473    pub fn ordered_paths(&self) -> impl ExactSizeIterator<Item = &NamespacePath> {
474        self.ordered_paths
475            .iter()
476            .map(|path_use| path_for(&self.operations, *path_use))
477    }
478
479    /// Canonically ordered endpoints with their operation and endpoint indices.
480    ///
481    /// Endpoint zero is the sole or source path; endpoint one is a distinct
482    /// destination. The executor uses these stable indices to restore semantic
483    /// operation order after one shared borrowed-path lookup.
484    #[must_use]
485    pub fn ordered_operation_paths(
486        &self,
487    ) -> impl ExactSizeIterator<Item = (usize, usize, &NamespacePath)> {
488        self.ordered_paths.iter().map(|path_use| {
489            (
490                usize::try_from(path_use.operation).unwrap_or(usize::MAX),
491                usize::from(path_use.endpoint),
492                path_for(&self.operations, *path_use),
493            )
494        })
495    }
496
497    /// Distinct path-prefix nodes; shared ancestors count once.
498    #[must_use]
499    pub const fn path_nodes(&self) -> u64 {
500        self.path_nodes
501    }
502
503    /// Logical flat-plan capacity retained until generation execution finishes.
504    #[must_use]
505    pub const fn retained_allocation_bytes(&self) -> u64 {
506        self.retained_allocation_bytes
507    }
508
509    /// Exact compilation work.
510    #[must_use]
511    pub const fn work(&self) -> WorkCounters {
512        self.work
513    }
514
515    pub(crate) fn into_operations(self) -> Vec<Mutation> {
516        self.operations
517    }
518}
519
520// `PathUse` is private and is constructed only after `Mutation::paths`
521// returns `Some`; retaining that proof here avoids cloning every path.
522#[allow(clippy::expect_used)]
523#[allow(
524    clippy::indexing_slicing,
525    reason = "PathUse is private and is only ever constructed in MutationPlan::compile as `operation: u32::try_from(index)` for `index` in `operations.iter().enumerate()`; operations and ordered_paths are stored together in MutationPlan and neither is mutated afterward, so path_use.operation as usize is always < operations.len()"
526)]
527fn path_for(operations: &[Mutation], path_use: PathUse) -> &NamespacePath {
528    let operation = &operations[usize::try_from(path_use.operation).unwrap_or(usize::MAX)];
529    let [first, second] = operation
530        .paths()
531        .expect("path use must reference a path mutation");
532    // PathUse::endpoint is only ever constructed as 0 or 1 (see `compile`),
533    // selecting between the two fixed positions of `Mutation::paths`.
534    match path_use.endpoint {
535        0 => first,
536        _ => second,
537    }
538}
539
540fn shared_prefix(left: &NamespacePath, right: &NamespacePath) -> usize {
541    left.components()
542        .iter()
543        .zip(right.components())
544        .take_while(|(left, right)| left == right)
545        .count()
546}
547
548fn path_use_count(operations: &[Mutation]) -> Option<usize> {
549    operations.iter().try_fold(0_usize, |count, operation| {
550        let uses = operation
551            .paths()
552            .map_or(0, |[first, second]| if first == second { 1 } else { 2 });
553        count.checked_add(uses)
554    })
555}
556
557fn validate_range(offset: u64, length: u64) -> Result<(), MutationPlanError> {
558    if length == 0 {
559        return Err(MutationPlanError::EmptyRange);
560    }
561    offset
562        .checked_add(length)
563        .ok_or(MutationPlanError::RangeOverflow)?;
564    Ok(())
565}
566
567/// Mutation-plan failure preserving exact compilation work.
568pub type MutationPlanFailure = OperationFailure<MutationPlanError>;
569
570/// Stable mutation-plan admission failures.
571#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
572pub enum MutationPlanError {
573    /// Atomic batches contain at least one operation.
574    #[error("mutation batch is empty")]
575    Empty,
576    /// Batch exceeds the volume's admitted operation bound.
577    #[error("mutation batch exceeds the volume limit")]
578    TooManyMutations,
579    /// Initial create record violates canonical file-table invariants.
580    #[error("created file record is invalid")]
581    InvalidInitialRecord,
582    /// The volume root cannot be created, removed, linked, renamed, or rewritten as a file.
583    #[error("mutation cannot target the volume root")]
584    RootMutation,
585    /// Two-ended namespace operation used one identical path.
586    #[error("mutation source and destination are identical")]
587    SameSourceAndDestination,
588    /// Byte range must be non-empty.
589    #[error("mutation byte range is empty")]
590    EmptyRange,
591    /// Byte-range arithmetic overflowed.
592    #[error("mutation byte range overflowed")]
593    RangeOverflow,
594    /// Write source is not an authenticated blob.
595    #[error("mutation content object is not a blob")]
596    WrongContentKind,
597    /// Metadata replacement is not a canonical metadata object.
598    #[error("mutation metadata object has the wrong kind")]
599    WrongMetadataKind,
600    /// Stable operation/path index cannot be represented.
601    #[error("mutation-plan index overflowed")]
602    IndexOverflow,
603    /// Bounded flat-plan storage could not be allocated.
604    #[error("mutation-plan allocation failed")]
605    AllocationFailed,
606    /// Exact compilation work exceeded or overflowed its budget.
607    #[error(transparent)]
608    Work(#[from] WorkError),
609}
610
611#[cfg(test)]
612#[path = "tests/mutation.rs"]
613mod tests;
acyclic_fs/kernel/mutation.rs

acyclic_fs/kernel/
mutation.rs
