ic_memory/
allocation_pool.rs

1use crate::{StableKey, text::validate_diagnostic_text};
2use serde::Serialize;
3#[cfg(any(test, feature = "test-support"))]
4use serde::{Deserialize, Deserializer, de::Error as _};
5
6///
7/// MemoryAuthority
8///
9/// Host-owned permission for one named owner to request keys in a namespace.
10/// The prefix ends in a dot, so `app.` never grants `application.`. This policy
11/// metadata grants neither caller authentication nor a sandbox for linked code.
12///
13/// Construct inputs with [`Self::new`]; serialization is for diagnostic output.
14/// Decoding is available only with `test-support` for explicit fixtures.
15///
16
17#[derive(Clone, Debug, Eq, PartialEq, Serialize)]
18pub struct MemoryAuthority {
19    authority: String,
20    key_prefix: String,
21}
22
23impl MemoryAuthority {
24    /// Validate a host grant. Multiple disjoint prefixes may share an owner.
25    pub fn new(
26        authority: impl Into<String>,
27        key_prefix: impl Into<String>,
28    ) -> Result<Self, MemoryAllocationPoolError> {
29        let authority = authority.into();
30        validate_diagnostic_text(&authority).map_err(|error| {
31            MemoryAllocationPoolError::InvalidAuthority {
32                reason: error.reason(),
33            }
34        })?;
35        if authority == crate::IC_MEMORY_AUTHORITY_OWNER {
36            return Err(MemoryAllocationPoolError::ReservedAuthority);
37        }
38        let key_prefix = key_prefix.into();
39        if !crate::key::is_key_prefix(&key_prefix) {
40            return Err(MemoryAllocationPoolError::InvalidKeyPrefix { key_prefix });
41        }
42        if key_prefix.starts_with(crate::IC_MEMORY_STABLE_KEY_PREFIX) {
43            return Err(MemoryAllocationPoolError::InvalidKeyPrefix { key_prefix });
44        }
45        Ok(Self {
46            authority,
47            key_prefix,
48        })
49    }
50
51    /// The admitted linked-code owner label.
52    #[must_use]
53    pub fn authority(&self) -> &str {
54        &self.authority
55    }
56
57    /// Permanent key namespace admitted by the host.
58    #[must_use]
59    pub fn key_prefix(&self) -> &str {
60        &self.key_prefix
61    }
62}
63
64#[cfg(any(test, feature = "test-support"))]
65impl<'de> Deserialize<'de> for MemoryAuthority {
66    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
67        #[derive(Deserialize)]
68        #[serde(deny_unknown_fields)]
69        struct Grant {
70            authority: String,
71            key_prefix: String,
72        }
73        let grant = Grant::deserialize(deserializer)?;
74        Self::new(grant.authority, grant.key_prefix).map_err(D::Error::custom)
75    }
76}
77
78///
79/// MemoryAllocationPool
80///
81/// One host-wide pool over usable application IDs 10..=254. Governance IDs
82/// 0..=9 remain excluded. Explicit additional exclusions retain physical
83/// custody for unmanaged users; namespace grants never partition this pool.
84///
85/// The pool is immutable bootstrap policy, not durable allocation state.
86/// Every retained ledger record independently retains its ID, including omitted
87/// keys. It is not inferred from application bytes or slot contents.
88///
89/// Construct inputs with [`Self::new`]; serialization is for diagnostic output.
90/// Decoding is available only with `test-support` for explicit fixtures.
91///
92
93#[derive(Clone, Debug, Eq, PartialEq, Serialize)]
94pub struct MemoryAllocationPool {
95    authorities: Vec<MemoryAuthority>,
96    #[serde(rename = "excluded_ids", serialize_with = "serialize_excluded_ids")]
97    excluded: [u64; 4],
98}
99
100impl MemoryAllocationPool {
101    /// Canonicalize host grants and physical exclusions before bootstrap.
102
103    pub fn new(
104        mut authorities: Vec<MemoryAuthority>,
105        exclusions: Vec<u8>,
106    ) -> Result<Self, MemoryAllocationPoolError> {
107        if authorities.len() > 254 || exclusions.len() > 255 {
108            return Err(MemoryAllocationPoolError::TooManyEntries);
109        }
110        crate::sort::sort_unstable_by(&mut authorities, |a, b| a.key_prefix.cmp(&b.key_prefix));
111        for pair in authorities.windows(2) {
112            if pair[1].key_prefix.starts_with(&pair[0].key_prefix) {
113                return Err(MemoryAllocationPoolError::OverlappingNamespaces {
114                    existing_prefix: pair[0].key_prefix.clone(),
115                    candidate_prefix: pair[1].key_prefix.clone(),
116                });
117            }
118        }
119        let mut excluded = [0; 4];
120        for id in exclusions
121            .into_iter()
122            .chain(0..=crate::MEMORY_MANAGER_GOVERNANCE_MAX_ID)
123        {
124            crate::validate_memory_manager_id(id)?;
125            excluded[usize::from(id / 64)] |= 1 << (id % 64);
126        }
127        Ok(Self {
128            authorities,
129            excluded,
130        })
131    }
132
133    /// Current owner grants, in canonical namespace order.
134    #[must_use]
135    pub fn authorities(&self) -> &[MemoryAuthority] {
136        &self.authorities
137    }
138
139    /// Excluded usable IDs, including governance, in ascending order.
140    pub fn excluded_ids(&self) -> impl Iterator<Item = u8> + '_ {
141        (0..crate::MEMORY_MANAGER_INVALID_ID).filter(|id| is_excluded(&self.excluded, *id))
142    }
143
144    /// Whether an ID belongs to the shared application pool.
145    #[must_use]
146    pub fn contains(&self, id: u8) -> bool {
147        id != crate::MEMORY_MANAGER_INVALID_ID && !is_excluded(&self.excluded, id)
148    }
149
150    /// Validate current key ownership independently of numeric placement.
151    pub fn validate_authority(
152        &self,
153        key: &StableKey,
154        authority: &str,
155    ) -> Result<(), MemoryAllocationPoolError> {
156        let admitted_authority =
157            self.authority_for_key(key)
158                .ok_or_else(|| MemoryAllocationPoolError::UnclaimedKey {
159                    stable_key: key.clone(),
160                })?;
161        if admitted_authority != authority {
162            return Err(MemoryAllocationPoolError::AuthorityMismatch {
163                stable_key: key.clone(),
164                requested_authority: authority.to_string(),
165                admitted_authority: admitted_authority.to_string(),
166            });
167        }
168        Ok(())
169    }
170
171    /// Borrow the current namespace grant for a checked key. This does not
172    /// establish commitment, historical ownership or caller authentication.
173    #[must_use]
174    pub fn authority_for_key(&self, key: &StableKey) -> Option<&str> {
175        self.authorities
176            .iter()
177            .find(|grant| key.as_str().starts_with(&grant.key_prefix))
178            .map(MemoryAuthority::authority)
179    }
180
181    /// Validate physical eligibility without granting ownership of a key.
182    pub fn validate_id(&self, id: u8) -> Result<(), MemoryAllocationPoolError> {
183        crate::validate_memory_manager_id(id)?;
184        if !self.contains(id) {
185            return Err(MemoryAllocationPoolError::ExcludedSlot { id });
186        }
187        Ok(())
188    }
189}
190
191#[cfg(any(test, feature = "test-support"))]
192impl<'de> Deserialize<'de> for MemoryAllocationPool {
193    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
194        #[derive(Deserialize)]
195        #[serde(deny_unknown_fields)]
196        struct Pool {
197            authorities: Vec<MemoryAuthority>,
198            #[serde(deserialize_with = "crate::cbor::deserialize_records")]
199            excluded_ids: Vec<u8>,
200        }
201        let pool = Pool::deserialize(deserializer)?;
202        Self::new(pool.authorities, pool.excluded_ids).map_err(D::Error::custom)
203    }
204}
205
206fn is_excluded(excluded: &[u64; 4], id: u8) -> bool {
207    excluded[usize::from(id / 64)] & (1 << (id % 64)) != 0
208}
209
210fn serialize_excluded_ids<S: serde::Serializer>(
211    excluded: &[u64; 4],
212    serializer: S,
213) -> Result<S::Ok, S::Error> {
214    use serde::ser::SerializeSeq as _;
215    let count = excluded.iter().map(|word| word.count_ones() as usize).sum();
216    let mut seq = serializer.serialize_seq(Some(count))?;
217    for id in (0..crate::MEMORY_MANAGER_INVALID_ID).filter(|id| is_excluded(excluded, *id)) {
218        seq.serialize_element(&id)?;
219    }
220    seq.end()
221}
222
223///
224/// MemoryAllocationPoolError
225///
226/// Invalid host configuration or a request outside admitted ownership/custody.
227///
228
229#[non_exhaustive]
230#[derive(Clone, Debug, Eq, PartialEq, thiserror::Error)]
231pub enum MemoryAllocationPoolError {
232    #[error("host allocation policy exceeds the bounded slot domain")]
233    TooManyEntries,
234    #[error("authority {reason}")]
235    InvalidAuthority { reason: &'static str },
236    #[error("ic-memory governance authority cannot be granted externally")]
237    ReservedAuthority,
238    #[error("invalid application key namespace prefix {key_prefix}")]
239    InvalidKeyPrefix { key_prefix: String },
240    #[error("key namespaces {existing_prefix} and {candidate_prefix} overlap")]
241    OverlappingNamespaces {
242        existing_prefix: String,
243        candidate_prefix: String,
244    },
245    #[error("stable key {stable_key} has no host namespace grant")]
246    UnclaimedKey { stable_key: StableKey },
247    #[error(
248        "stable key {stable_key} is granted to {admitted_authority}, not {requested_authority}"
249    )]
250    AuthorityMismatch {
251        stable_key: StableKey,
252        requested_authority: String,
253        admitted_authority: String,
254    },
255    #[error("MemoryManager ID {id} is excluded from the application pool")]
256    ExcludedSlot { id: u8 },
257    #[error(transparent)]
258    Slot(#[from] crate::MemoryManagerSlotError),
259}
260
261#[cfg(test)]
262mod tests {
263    #[test]
264    fn namespace_admission_checks_segments_and_complete_key_length() {
265        for prefix in ["a.", "app.a_0.", "app.v0.", "app.v1."] {
266            let grant = super::MemoryAuthority::new("app", prefix).unwrap();
267            assert_eq!(grant.key_prefix(), prefix);
268        }
269        for prefix in ["", ".", "app", "app..", "app.0.", "App.", "app/a."] {
270            assert!(matches!(
271                super::MemoryAuthority::new("app", prefix),
272                Err(super::MemoryAllocationPoolError::InvalidKeyPrefix { key_prefix })
273                    if key_prefix == prefix
274            ));
275        }
276        for byte in 0..=u8::MAX {
277            let prefix = format!("app.a{}.", char::from(byte));
278            let allowed = byte.is_ascii_lowercase() || byte.is_ascii_digit() || byte == b'_';
279            assert_eq!(super::MemoryAuthority::new("app", prefix).is_ok(), allowed);
280        }
281        assert!(super::MemoryAuthority::new("app", format!("{}.", "a".repeat(125))).is_ok());
282        assert!(matches!(
283            super::MemoryAuthority::new("app", format!("{}.", "a".repeat(126))),
284            Err(super::MemoryAllocationPoolError::InvalidKeyPrefix { .. })
285        ));
286    }
287
288    use super::*;
289
290    #[test]
291    fn canonical_policy_has_one_physical_pool_and_disjoint_namespaces() {
292        let grant = |owner, prefix| MemoryAuthority::new(owner, prefix).unwrap();
293        let pool = MemoryAllocationPool::new(
294            vec![grant("db", "db."), grant("app", "app.")],
295            (20..=25).chain(23..=30).chain(31..=31).collect(),
296        )
297        .unwrap();
298        assert_eq!(pool.authorities()[0].authority(), "app");
299        assert_eq!(
300            pool.excluded_ids().collect::<Vec<_>>(),
301            (0..=9).chain(20..=31).collect::<Vec<_>>()
302        );
303        for id in [0, 9, 20, 31, 255] {
304            assert!(!pool.contains(id));
305        }
306        for id in [10, 19, 32, 254] {
307            assert!(pool.contains(id));
308        }
309        assert!(matches!(
310            MemoryAllocationPool::new(vec![grant("app", "app."), grant("db", "app.db.")], vec![]),
311            Err(MemoryAllocationPoolError::OverlappingNamespaces { .. })
312        ));
313        assert!(
314            pool.validate_authority(&StableKey::parse("application.rows.v1").unwrap(), "app")
315                .is_err()
316        );
317        assert!(
318            pool.validate_authority(&StableKey::parse("app.rows.v1").unwrap(), "db")
319                .is_err()
320        );
321    }
322
323    #[test]
324    fn decoding_cannot_bypass_namespace_or_physical_exclusion_admission() {
325        let pool: MemoryAllocationPool = serde_json::from_str(
326            r#"{
327            "authorities":[{"authority":"app","key_prefix":"app."}],
328            "excluded_ids":[10]
329        }"#,
330        )
331        .unwrap();
332        assert!(!pool.contains(0));
333        assert!(!pool.contains(10));
334        assert!(pool.contains(11));
335        for json in [
336            r#"{"authorities":[{"authority":"ic-memory","key_prefix":"app."}],"excluded_ids":[]}"#,
337            r#"{"authorities":[{"authority":"app","key_prefix":"ic_memory."}],"excluded_ids":[]}"#,
338            r#"{"authorities":[],"excluded_ids":[255]}"#,
339            r#"{"authorities":[],"excluded_ids":[],"unknown":true}"#,
340        ] {
341            assert!(serde_json::from_str::<MemoryAllocationPool>(json).is_err());
342        }
343        assert_eq!(
344            serde_json::from_str::<MemoryAllocationPool>(&serde_json::to_string(&pool).unwrap())
345                .unwrap(),
346            pool
347        );
348    }
349    #[test]
350    fn exclusion_membership_and_wire_projection_cover_every_usable_id() {
351        for ids in [
352            vec![0, 9, 10, 63, 64, 127, 128, 191, 192, 254],
353            (10..=254).step_by(2).collect(),
354            (0..=254).collect(),
355        ] {
356            let pool = MemoryAllocationPool::new(vec![], ids.clone()).unwrap();
357            let reversed =
358                MemoryAllocationPool::new(vec![], ids.iter().rev().copied().collect()).unwrap();
359            assert_eq!(pool, reversed);
360            for id in 0..=u8::MAX {
361                assert_eq!(
362                    pool.contains(id),
363                    id > crate::MEMORY_MANAGER_GOVERNANCE_MAX_ID
364                        && id != u8::MAX
365                        && !ids.contains(&id)
366                );
367            }
368            let projected: Vec<_> = (0..255).filter(|id| !pool.contains(*id)).collect();
369            assert_eq!(pool.excluded_ids().collect::<Vec<_>>(), projected);
370            let json = serde_json::to_value(&pool).unwrap();
371            assert_eq!(json["excluded_ids"], serde_json::json!(projected));
372            assert_eq!(
373                serde_json::from_value::<MemoryAllocationPool>(json).unwrap(),
374                pool
375            );
376            let bytes = crate::test_cbor::to_vec(&pool).unwrap();
377            assert_eq!(
378                crate::cbor::from_slice_exact::<MemoryAllocationPool>(&bytes).unwrap(),
379                pool
380            );
381        }
382        assert!(matches!(
383            MemoryAllocationPool::new(vec![], vec![255]),
384            Err(MemoryAllocationPoolError::Slot(_))
385        ));
386        assert!(matches!(
387            MemoryAllocationPool::new(vec![], vec![10; 256]),
388            Err(MemoryAllocationPoolError::TooManyEntries)
389        ));
390        assert_eq!(
391            MemoryAllocationPool::new(vec![], vec![63, 64, 63]).unwrap(),
392            MemoryAllocationPool::new(vec![], vec![64, 63]).unwrap()
393        );
394    }
395}
ic_memory/allocation_pool.rs

ic_memory/
allocation_pool.rs
