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    /// Borrow the current namespace grant for a checked key. This does not
163    /// establish commitment, historical ownership or caller authentication.
164    #[must_use]
165    pub fn authority_for_key(&self, key: &StableKey) -> Option<&str> {
166        self.authorities
167            .iter()
168            .find(|grant| key.as_str().starts_with(&grant.key_prefix))
169            .map(MemoryAuthority::authority)
170    }
171
172    /// Validate physical eligibility without granting ownership of a key.
173    pub fn validate_id(&self, id: u8) -> Result<(), MemoryAllocationPoolError> {
174        crate::validate_memory_manager_id(id)?;
175        if !self.contains(id) {
176            return Err(MemoryAllocationPoolError::ExcludedSlot { id });
177        }
178        Ok(())
179    }
180}
181
182impl<'de> Deserialize<'de> for MemoryAllocationPool {
183    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
184        #[derive(Deserialize)]
185        #[serde(deny_unknown_fields)]
186        struct Pool {
187            authorities: Vec<MemoryAuthority>,
188            #[serde(deserialize_with = "crate::cbor::deserialize_records")]
189            excluded_ids: Vec<u8>,
190        }
191        let pool = Pool::deserialize(deserializer)?;
192        Self::new(pool.authorities, pool.excluded_ids).map_err(D::Error::custom)
193    }
194}
195
196fn is_excluded(excluded: &[u64; 4], id: u8) -> bool {
197    excluded[usize::from(id / 64)] & (1 << (id % 64)) != 0
198}
199
200fn serialize_excluded_ids<S: serde::Serializer>(
201    excluded: &[u64; 4],
202    serializer: S,
203) -> Result<S::Ok, S::Error> {
204    use serde::ser::SerializeSeq as _;
205    let count = excluded.iter().map(|word| word.count_ones() as usize).sum();
206    let mut seq = serializer.serialize_seq(Some(count))?;
207    for id in (0..crate::MEMORY_MANAGER_INVALID_ID).filter(|id| is_excluded(excluded, *id)) {
208        seq.serialize_element(&id)?;
209    }
210    seq.end()
211}
212
213///
214/// MemoryAllocationPoolError
215///
216/// Invalid host configuration or a request outside admitted ownership/custody.
217///
218
219#[non_exhaustive]
220#[derive(Clone, Debug, Eq, PartialEq, thiserror::Error)]
221pub enum MemoryAllocationPoolError {
222    #[error("host allocation policy exceeds the bounded slot domain")]
223    TooManyEntries,
224    #[error("authority {reason}")]
225    InvalidAuthority { reason: &'static str },
226    #[error("ic-memory governance authority cannot be granted externally")]
227    ReservedAuthority,
228    #[error("invalid application key namespace prefix {key_prefix}")]
229    InvalidKeyPrefix { key_prefix: String },
230    #[error("key namespaces {existing_prefix} and {candidate_prefix} overlap")]
231    OverlappingNamespaces {
232        existing_prefix: String,
233        candidate_prefix: String,
234    },
235    #[error("stable key {stable_key} has no host namespace grant")]
236    UnclaimedKey { stable_key: StableKey },
237    #[error(
238        "stable key {stable_key} is granted to {admitted_authority}, not {requested_authority}"
239    )]
240    AuthorityMismatch {
241        stable_key: StableKey,
242        requested_authority: String,
243        admitted_authority: String,
244    },
245    #[error("MemoryManager ID {id} is excluded from the application pool")]
246    ExcludedSlot { id: u8 },
247    #[error(transparent)]
248    Slot(#[from] crate::MemoryManagerSlotError),
249}
250
251#[cfg(test)]
252mod tests {
253    #[test]
254    fn namespace_admission_checks_segments_and_complete_key_length() {
255        for prefix in ["a.", "app.a_0.", "app.v0.", "app.v1."] {
256            let grant = super::MemoryAuthority::new("app", prefix).unwrap();
257            assert_eq!(grant.key_prefix(), prefix);
258        }
259        for prefix in ["", ".", "app", "app..", "app.0.", "App.", "app/a."] {
260            assert!(matches!(
261                super::MemoryAuthority::new("app", prefix),
262                Err(super::MemoryAllocationPoolError::InvalidKeyPrefix { key_prefix })
263                    if key_prefix == prefix
264            ));
265        }
266        for byte in 0..=u8::MAX {
267            let prefix = format!("app.a{}.", char::from(byte));
268            let allowed = byte.is_ascii_lowercase() || byte.is_ascii_digit() || byte == b'_';
269            assert_eq!(super::MemoryAuthority::new("app", prefix).is_ok(), allowed);
270        }
271        assert!(super::MemoryAuthority::new("app", format!("{}.", "a".repeat(125))).is_ok());
272        assert!(matches!(
273            super::MemoryAuthority::new("app", format!("{}.", "a".repeat(126))),
274            Err(super::MemoryAllocationPoolError::InvalidKeyPrefix { .. })
275        ));
276    }
277
278    use super::*;
279
280    #[test]
281    fn canonical_policy_has_one_physical_pool_and_disjoint_namespaces() {
282        let grant = |owner, prefix| MemoryAuthority::new(owner, prefix).unwrap();
283        let pool = MemoryAllocationPool::new(
284            vec![grant("db", "db."), grant("app", "app.")],
285            (20..=25).chain(23..=30).chain(31..=31).collect(),
286        )
287        .unwrap();
288        assert_eq!(pool.authorities()[0].authority(), "app");
289        assert_eq!(
290            pool.excluded_ids().collect::<Vec<_>>(),
291            (0..=9).chain(20..=31).collect::<Vec<_>>()
292        );
293        for id in [0, 9, 20, 31, 255] {
294            assert!(!pool.contains(id));
295        }
296        for id in [10, 19, 32, 254] {
297            assert!(pool.contains(id));
298        }
299        assert!(matches!(
300            MemoryAllocationPool::new(vec![grant("app", "app."), grant("db", "app.db.")], vec![]),
301            Err(MemoryAllocationPoolError::OverlappingNamespaces { .. })
302        ));
303        assert!(
304            pool.validate_authority(&StableKey::parse("application.rows.v1").unwrap(), "app")
305                .is_err()
306        );
307        assert!(
308            pool.validate_authority(&StableKey::parse("app.rows.v1").unwrap(), "db")
309                .is_err()
310        );
311    }
312
313    #[test]
314    fn decoding_cannot_bypass_namespace_or_physical_exclusion_admission() {
315        let pool: MemoryAllocationPool = serde_json::from_str(
316            r#"{
317            "authorities":[{"authority":"app","key_prefix":"app."}],
318            "excluded_ids":[10]
319        }"#,
320        )
321        .unwrap();
322        assert!(!pool.contains(0));
323        assert!(!pool.contains(10));
324        assert!(pool.contains(11));
325        for json in [
326            r#"{"authorities":[{"authority":"ic-memory","key_prefix":"app."}],"excluded_ids":[]}"#,
327            r#"{"authorities":[{"authority":"app","key_prefix":"ic_memory."}],"excluded_ids":[]}"#,
328            r#"{"authorities":[],"excluded_ids":[255]}"#,
329            r#"{"authorities":[],"excluded_ids":[],"unknown":true}"#,
330        ] {
331            assert!(serde_json::from_str::<MemoryAllocationPool>(json).is_err());
332        }
333        assert_eq!(
334            serde_json::from_str::<MemoryAllocationPool>(&serde_json::to_string(&pool).unwrap())
335                .unwrap(),
336            pool
337        );
338    }
339    #[test]
340    fn exclusion_membership_and_wire_projection_cover_every_usable_id() {
341        for ids in [
342            vec![0, 9, 10, 63, 64, 127, 128, 191, 192, 254],
343            (10..=254).step_by(2).collect(),
344            (0..=254).collect(),
345        ] {
346            let pool = MemoryAllocationPool::new(vec![], ids.clone()).unwrap();
347            let reversed =
348                MemoryAllocationPool::new(vec![], ids.iter().rev().copied().collect()).unwrap();
349            assert_eq!(pool, reversed);
350            for id in 0..=u8::MAX {
351                assert_eq!(
352                    pool.contains(id),
353                    id > crate::MEMORY_MANAGER_GOVERNANCE_MAX_ID
354                        && id != u8::MAX
355                        && !ids.contains(&id)
356                );
357            }
358            let projected: Vec<_> = (0..255).filter(|id| !pool.contains(*id)).collect();
359            assert_eq!(pool.excluded_ids().collect::<Vec<_>>(), projected);
360            let json = serde_json::to_value(&pool).unwrap();
361            assert_eq!(json["excluded_ids"], serde_json::json!(projected));
362            assert_eq!(
363                serde_json::from_value::<MemoryAllocationPool>(json).unwrap(),
364                pool
365            );
366            let bytes = crate::test_cbor::to_vec(&pool).unwrap();
367            assert_eq!(
368                crate::cbor::from_slice_exact::<MemoryAllocationPool>(&bytes).unwrap(),
369                pool
370            );
371        }
372        assert!(matches!(
373            MemoryAllocationPool::new(vec![], vec![255]),
374            Err(MemoryAllocationPoolError::Slot(_))
375        ));
376        assert!(matches!(
377            MemoryAllocationPool::new(vec![], vec![10; 256]),
378            Err(MemoryAllocationPoolError::TooManyEntries)
379        ));
380        assert_eq!(
381            MemoryAllocationPool::new(vec![], vec![63, 64, 63]).unwrap(),
382            MemoryAllocationPool::new(vec![], vec![64, 63]).unwrap()
383        );
384    }
385}
ic_memory/allocation_pool.rs

ic_memory/
allocation_pool.rs
