Skip to main content

object_log/
bounded_lookup.rs

1//! Incremental lookup bounds metadata copies, not full resident index storage.
2use crate::{IndexEntry, ObjectLogError, PartitionKey, Sequencer};
3
4/// Compile-time native page port; legacy custom sequencers need not implement it.
5pub trait BoundedSequencer: Sequencer {
6    /// Caller reserves `max_metadata_bytes` before calling. Includes vector entry
7    /// headers and cloned full object identifiers. Check retained log_start under
8    /// the same lock as page copying. No unbounded lookup fallback.
9    fn lookup_page(
10        &self,
11        partition: &PartitionKey,
12        offset: i64,
13        max_entries: usize,
14        max_metadata_bytes: usize,
15    ) -> Result<Vec<IndexEntry>, ObjectLogError>;
16}
17fn invalid(message: &str) -> ObjectLogError {
18    ObjectLogError::Sequencer(message.into())
19}
20pub(crate) fn entry_end(entry: &IndexEntry) -> Result<i64, ObjectLogError> {
21    if entry.base_offset < 0 || entry.record_count <= 0 {
22        return Err(invalid("invalid index offset/count"));
23    }
24    entry
25        .base_offset
26        .checked_add(i64::from(entry.record_count))
27        .ok_or_else(|| invalid("index offset overflow"))
28}
29pub(crate) fn validate_index(
30    entries: &[IndexEntry],
31    log_start: i64,
32    next: i64,
33) -> Result<(), ObjectLogError> {
34    if log_start < 0 || next < log_start {
35        return Err(invalid("invalid retained index bounds"));
36    }
37    let mut previous = None;
38    for entry in entries {
39        let end = entry_end(entry)?;
40        if entry.location.object_id.is_empty() {
41            return Err(invalid("index has empty object identifier"));
42        }
43        if let Some(previous) = previous {
44            if entry.base_offset != previous {
45                return Err(invalid("index ranges are not ordered and contiguous"));
46            }
47        } else if entry.base_offset > log_start || end <= log_start {
48            return Err(invalid("index does not cover retained boundary"));
49        }
50        previous = Some(end);
51    }
52    if previous.unwrap_or(log_start) != next {
53        return Err(invalid("index does not cover committed tail"));
54    }
55    Ok(())
56}
57/// Installed indexes already validate; do not rescan the full suffix per page.
58pub(crate) fn page(
59    entries: &[IndexEntry],
60    offset: i64,
61    max_entries: usize,
62    max_bytes: usize,
63) -> Result<Vec<IndexEntry>, ObjectLogError> {
64    if offset < 0 || max_entries == 0 || max_bytes == 0 {
65        return Err(ObjectLogError::InvalidConfig(
66            "positive page limits and nonnegative offset required".into(),
67        ));
68    }
69    let start = entries
70        .partition_point(|entry| entry.base_offset + i64::from(entry.record_count) <= offset);
71    let available = &entries[start..];
72    let mut count = 0;
73    let mut bytes = 0usize;
74    for entry in available.iter().take(max_entries) {
75        let cost = std::mem::size_of::<IndexEntry>()
76            .checked_add(entry.location.object_id.len())
77            .and_then(|n| n.checked_add(64))
78            .ok_or_else(|| invalid("index metadata size overflow"))?;
79        let Some(next) = bytes.checked_add(cost).filter(|next| *next <= max_bytes) else {
80            if count == 0 {
81                return Err(ObjectLogError::BudgetExceeded(
82                    "first index entry exceeds metadata page budget".into(),
83                ));
84            }
85            break;
86        };
87        bytes = next;
88        count += 1;
89    }
90    let mut out = Vec::with_capacity(count);
91    out.extend(available[..count].iter().cloned());
92    Ok(out)
93}
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98    use crate::BatchLocation;
99    fn entry(base: i64, count: i32, name: &str) -> IndexEntry {
100        IndexEntry {
101            base_offset: base,
102            record_count: count,
103            location: BatchLocation {
104                object_id: name.into(),
105                byte_start: 0,
106                byte_len: 1,
107            },
108        }
109    }
110    #[test]
111    fn installed_ranges_are_checked_without_sorting_or_overflow() {
112        let good = [entry(0, 3, "a"), entry(3, 2, "b")];
113        validate_index(&good, 0, 5).unwrap();
114        validate_index(&good, 2, 5).unwrap();
115        for entries in [
116            vec![entry(-1, 1, "a")],
117            vec![entry(0, 0, "a")],
118            vec![entry(i64::MAX, 1, "a")],
119            vec![entry(0, 2, "a"), entry(1, 1, "b")],
120            vec![entry(1, 1, "a")],
121            vec![entry(0, 1, "")],
122        ] {
123            assert!(validate_index(&entries, 0, 2).is_err());
124        }
125        assert!(validate_index(&good, 0, 6).is_err());
126        assert!(validate_index(&[], 0, 1).is_err());
127        validate_index(&[], 5, 5).unwrap();
128    }
129    #[test]
130    fn page_bound_includes_full_object_names_and_mid_batch_offsets() {
131        let entries = [
132            entry(0, 3, &"a".repeat(5000)),
133            entry(3, 2, "b"),
134            entry(5, 1, "c"),
135        ];
136        let cost = std::mem::size_of::<IndexEntry>() + 5000 + 64;
137        assert!(matches!(
138            page(&entries, 2, 3, cost - 1),
139            Err(ObjectLogError::BudgetExceeded(_))
140        ));
141        let first = page(&entries, 2, 3, cost).unwrap();
142        assert_eq!(first, entries[..1]);
143        assert_eq!(page(&entries, 3, 1, 4096).unwrap(), entries[1..2]);
144        assert!(page(&entries, 6, 1, 4096).unwrap().is_empty());
145        assert!(page(&entries, -1, 1, 4096).is_err());
146        assert!(page(&entries, 0, 0, 4096).is_err());
147    }
148}