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}