ic_memory/
allocation_pool.rs

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

ic_memory/
allocation_pool.rs
