Skip to main content

ic_storage/adapter/
region.rs

1//! Operation-local collection access within a retained allocation region.
2use super::bridge::{self, TreeMemory};
3use super::error::{CollectionError as Error, Result as CollectionResult, ensure};
4use super::{Memory, Storable};
5use crate::DefaultMemoryImpl;
6use crate::{RuntimeGrowError, RuntimeMemory, WASM_PAGE_SIZE_BYTES as PAGE_BYTES};
7use std::{marker::PhantomData, ops::Range, ops::RangeBounds, rc::Rc};
8
9const MAX_PAGES: u64 = 4_194_304;
10
11///
12/// `RegionGrowError`
13///
14/// Failure to reserve a governed region's virtual extent, before any writes.
15///
16
17#[derive(Clone, Copy, Debug, Eq, PartialEq, thiserror::Error)]
18pub enum RegionGrowError {
19    /// The requested relative extent exceeds the selected region.
20    #[error("requested region extent {minimum} exceeds {maximum} pages")]
21    LimitExceeded {
22        /// Requested relative page count.
23        minimum: u64,
24        /// Maximum relative page count.
25        maximum: u64,
26    },
27    /// Storage refused to grow the containing allocation.
28    #[error("{0}")]
29    Runtime(#[source] RuntimeGrowError),
30}
31
32/// A B-tree view inside one existing, governed allocation lease.
33///
34/// The caller retains its `Rc<RuntimeMemory>` for disjoint application frames.
35/// Each collection operation loads the current owned tree root and allocator;
36/// multiple views may interleave operations without retaining stale roots.
37/// Key scans return owned snapshots, so no cached tree or iterator escapes.
38/// Applications own namespace bounds, codec admission and recovery policy.
39///
40/// Construction performs no IO. Inspect retained framing with [`Self::read`]
41/// before calling collection operations. Framing admission returns errors;
42/// engine and codec failures trap. Only [`Self::initialize`] creates a tree, and only in an empty
43/// region. No method reinitializes nonempty memory or exports raw backing.
44/// As with ordinary collections, callers must not reenter collection access
45/// from a codec or mutate the tree's bytes through their retained lease.
46pub struct BTreeMapRegion<K: Storable + Ord + Clone, V: Storable, M: Memory = DefaultMemoryImpl> {
47    memory: RegionMemory<M>,
48    record: PhantomData<(K, V)>,
49}
50
51impl<K: Storable + Ord + Clone, V: Storable, M: Memory> BTreeMapRegion<K, V, M> {
52    /// Select an absolute, half-open range of 65,536-byte allocation pages.
53    ///
54    /// Retains the same allocation lease; no allocation or collection is opened.
55    /// Other owners of the `Rc` may access disjoint frames in that allocation.
56    /// Drop every view and the caller's last `Rc` before reopening the lease.
57    ///
58    /// # Panics
59    /// Panics unless `pages.start < pages.end <= 4_194_304`.
60    #[must_use]
61    pub fn new(memory: Rc<RuntimeMemory<M>>, pages: Range<u64>) -> Self {
62        assert!(pages.start < pages.end && pages.end <= MAX_PAGES);
63        Self {
64            memory: RegionMemory { memory, pages },
65            record: PhantomData,
66        }
67    }
68
69    /// Return the currently allocated relative extent in Wasm pages.
70    #[must_use]
71    pub fn allocated_pages(&self) -> u64 {
72        self.memory.size()
73    }
74
75    /// Read relative bytes for the application's retained-framing admission.
76    ///
77    /// # Panics
78    /// Panics before IO if the complete read exceeds the allocated region.
79    /// An empty read is valid at the region's end, but not beyond it.
80    pub fn read(&self, offset: u64, dst: &mut [u8]) {
81        self.memory.read(offset, dst);
82    }
83
84    /// Create an owned tree only when the selected region has zero pages.
85    ///
86    /// Call before reserving extra pages. Retained trees need no initialization:
87    /// admit their framing and use the operations directly.
88    ///
89    /// # Errors
90    /// Rejects a nonempty region or capacity refusal without initializing a replacement.
91    pub fn initialize(&mut self) -> CollectionResult<()> {
92        ensure(self.allocated_pages() == 0, Error::NotEmpty)?;
93        bridge::reserve(&self.memory)?;
94        #[cfg(not(target_arch = "wasm32"))]
95        let _guard = self.memory.memory.poison_on_unwind();
96        bridge::Map::<K, V, _>::new(TreeMemory::Region(self.memory.clone()));
97        Ok(())
98    }
99
100    /// Reserve an absolute relative extent without promising entry capacity.
101    ///
102    /// # Errors
103    /// Returns a region-limit or Storage growth error without changing bytes
104    /// or allocation accounting. A satisfied request performs no growth or IO.
105    /// Callers own byte/page budgets and must qualify them for their codecs.
106    /// Mutations retain the host failure contract; this is not a transaction
107    /// around an insert that later runs out of space or panics in a codec.
108    pub fn reserve_pages(&mut self, minimum: u64) -> Result<(), RegionGrowError> {
109        self.memory.reserve_pages(minimum)
110    }
111
112    /// Read a record using the current retained root.
113    ///
114    /// # Errors
115    /// Refuses foreign framing; engine and stored-codec failures trap.
116    pub fn get(&self, key: &K) -> CollectionResult<Option<V>> {
117        Ok(self.current_map()?.get(key))
118    }
119
120    /// Insert using the current retained root and ordered engine.
121    ///
122    /// # Errors
123    /// Refuses foreign framing. Engine/codec failures trap, possibly after native writes.
124    pub fn insert(&mut self, key: K, value: V) -> CollectionResult<Option<V>> {
125        #[cfg(not(target_arch = "wasm32"))]
126        let _guard = self.memory.memory.poison_on_unwind();
127        Ok(self.current_map()?.insert(key, value))
128    }
129
130    /// Insert or replace without reading or decoding the previous value payload.
131    /// Returns whether an entry was replaced. Callers own old-payload validation;
132    /// stored lengths, key codecs and allocation metadata remain checked.
133    ///
134    /// # Panics
135    /// Invalid new codecs, keys, metadata or growth trap; native owners are poisoned.
136    ///
137    /// # Errors
138    /// Refuses foreign framing. Engine/codec failures trap, possibly after native writes.
139    pub fn insert_discard(&mut self, key: K, value: V) -> CollectionResult<bool> {
140        #[cfg(not(target_arch = "wasm32"))]
141        let _guard = self.memory.memory.poison_on_unwind();
142        Ok(self.current_map()?.insert_discard(key, value))
143    }
144
145    /// Remove using the current retained root and ordered engine.
146    ///
147    /// # Errors
148    /// Refuses foreign framing. Engine/codec failures trap, possibly after native writes.
149    pub fn remove(&mut self, key: &K) -> CollectionResult<Option<V>> {
150        #[cfg(not(target_arch = "wasm32"))]
151        let _guard = self.memory.memory.poison_on_unwind();
152        Ok(self.current_map()?.remove(key))
153    }
154
155    /// Remove without reading or decoding the removed value payload.
156    /// Returns whether an entry was removed. Callers own old-payload validation;
157    /// stored lengths, key codecs and allocation metadata remain checked.
158    ///
159    /// # Panics
160    /// Invalid keys or metadata trap; native owners are poisoned.
161    ///
162    /// # Errors
163    /// Refuses foreign framing. Engine/codec failures trap, possibly after native writes.
164    pub fn remove_discard(&mut self, key: &K) -> CollectionResult<bool> {
165        #[cfg(not(target_arch = "wasm32"))]
166        let _guard = self.memory.memory.poison_on_unwind();
167        Ok(self.current_map()?.remove_discard(key))
168    }
169
170    /// Return the current tree's record count across all namespaces.
171    ///
172    /// # Errors
173    /// Refuses foreign framing; malformed engine state traps.
174    pub fn len(&self) -> CollectionResult<u64> {
175        Ok(self.current_map()?.len())
176    }
177
178    /// Return whether the current tree has no records.
179    ///
180    /// # Errors
181    /// Refuses foreign framing; malformed engine state traps.
182    pub fn is_empty(&self) -> CollectionResult<bool> {
183        Ok(self.current_map()?.len() == 0)
184    }
185
186    /// Snapshot ordered keys within the caller's namespace/range bounds.
187    ///
188    /// The scan completes before returning; the iterator retains owned keys,
189    /// with no collection cache, memory handle or borrow across later mutations.
190    ///
191    /// # Errors
192    /// Refuses foreign framing; invalid ranges, engine state or key codecs can trap.
193    pub fn keys_range(
194        &self,
195        bounds: impl RangeBounds<K>,
196    ) -> CollectionResult<std::vec::IntoIter<K>> {
197        self.keys_range_limited(bounds, usize::MAX)
198    }
199
200    /// Snapshot at most `limit` ordered keys, stopping iteration at that bound.
201    ///
202    /// Unlike `keys_range(bounds).take(limit)`, this bounds collection work before
203    /// allocating the snapshot. Zero returns without loading the tree. Resume
204    /// with an excluded last key; intervening mutations are visible to each call.
205    /// The limit bounds key count, not encoded bytes or instruction cost.
206    ///
207    /// # Errors
208    /// Refuses foreign framing; invalid ranges, engine state or key codecs can trap.
209    pub fn keys_range_limited(
210        &self,
211        bounds: impl RangeBounds<K>,
212        limit: usize,
213    ) -> CollectionResult<std::vec::IntoIter<K>> {
214        if limit == 0 {
215            return Ok(Vec::new().into_iter());
216        }
217        Ok(self
218            .current_map()?
219            .keys_range(bounds)
220            .take(limit)
221            .collect::<Vec<_>>()
222            .into_iter())
223    }
224
225    fn current_map(&self) -> CollectionResult<bridge::Map<K, V, M>> {
226        bridge::Map::load(TreeMemory::Region(self.memory.clone())).ok_or(Error::Format)
227    }
228}
229
230// Private bounded IO over an admitted lease. Reads, writes and growth stay
231// inside the selected region, including initially absent regions.
232pub(super) struct RegionMemory<M: Memory> {
233    memory: Rc<RuntimeMemory<M>>,
234    pages: Range<u64>,
235}
236
237impl<M: Memory> Clone for RegionMemory<M> {
238    fn clone(&self) -> Self {
239        Self {
240            memory: Rc::clone(&self.memory),
241            pages: self.pages.clone(),
242        }
243    }
244}
245impl<M: Memory> RegionMemory<M> {
246    pub(super) fn allocation(&self) -> &RuntimeMemory<M> {
247        &self.memory
248    }
249
250    fn reserve_pages(&self, minimum: u64) -> Result<(), RegionGrowError> {
251        let maximum = self.pages.end - self.pages.start;
252        if minimum > maximum {
253            return Err(RegionGrowError::LimitExceeded { minimum, maximum });
254        }
255        if minimum > self.size() {
256            let additional = self.pages.start + minimum - self.memory.size();
257            self.memory
258                .as_ref()
259                .grow(additional)
260                .map_err(RegionGrowError::Runtime)?;
261        }
262        Ok(())
263    }
264
265    #[inline]
266    fn check_io(&self, offset: u64, count: usize) {
267        // The region owns its static namespace limit; RuntimeMemory admits the
268        // complete live allocation range. Avoid looking up that extent twice.
269        // Empty IO does not delegate, so it must check the current extent here.
270        let extent = if count == 0 {
271            self.size()
272        } else {
273            self.pages.end - self.pages.start
274        } * PAGE_BYTES;
275        assert!(offset <= extent && count as u64 <= extent - offset);
276    }
277}
278
279impl<M: Memory> Memory for RegionMemory<M> {
280    fn size(&self) -> u64 {
281        self.memory.size().clamp(self.pages.start, self.pages.end) - self.pages.start
282    }
283
284    fn grow(&self, delta: u64) -> i64 {
285        let previous = self.size();
286        let Some(minimum) = previous.checked_add(delta) else {
287            return -1;
288        };
289        if self.reserve_pages(minimum).is_ok() {
290            // The selected range is bounded by MAX_PAGES.
291            i64::try_from(previous).unwrap()
292        } else {
293            -1
294        }
295    }
296
297    fn read(&self, offset: u64, dst: &mut [u8]) {
298        self.check_io(offset, dst.len());
299        if !dst.is_empty() {
300            self.memory
301                .read(self.pages.start * PAGE_BYTES + offset, dst);
302        }
303    }
304
305    fn write(&self, offset: u64, src: &[u8]) {
306        self.check_io(offset, src.len());
307        if !src.is_empty() {
308            self.memory
309                .write(self.pages.start * PAGE_BYTES + offset, src);
310        }
311    }
312
313    #[expect(
314        unsafe_code,
315        reason = "Check the region namespace before forwarding the admitted destination"
316    )]
317    unsafe fn read_unsafe(&self, offset: u64, dst: *mut u8, count: usize) {
318        self.check_io(offset, count);
319        if count != 0 {
320            // SAFETY: the destination is unchanged; the lease checks the entire
321            // translated live range before initializing any of its chunks.
322            unsafe {
323                self.memory
324                    .read_unsafe(self.pages.start * PAGE_BYTES + offset, dst, count);
325            }
326        }
327    }
328}