ic_memory/
allocation_pool.rs

1use crate::{MemoryManagerIdRange, 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    excluded_ranges: Vec<MemoryManagerIdRange>,
88}
89
90impl MemoryAllocationPool {
91    /// Canonicalize host grants and physical exclusions before bootstrap.
92    ///
93    /// # Panics
94    ///
95    /// Panics only if an internal bounded-ID canonicalization invariant is broken.
96    pub fn new(
97        mut authorities: Vec<MemoryAuthority>,
98        exclusions: Vec<MemoryManagerIdRange>,
99    ) -> Result<Self, MemoryAllocationPoolError> {
100        if authorities.len() > 254 || exclusions.len() > 255 {
101            return Err(MemoryAllocationPoolError::TooManyEntries);
102        }
103        crate::sort::sort_unstable_by(&mut authorities, |a, b| a.key_prefix.cmp(&b.key_prefix));
104        for pair in authorities.windows(2) {
105            if pair[1].key_prefix.starts_with(&pair[0].key_prefix) {
106                return Err(MemoryAllocationPoolError::OverlappingNamespaces {
107                    existing_prefix: pair[0].key_prefix.clone(),
108                    candidate_prefix: pair[1].key_prefix.clone(),
109                });
110            }
111        }
112        let mut excluded = [false; 255];
113        for range in exclusions
114            .into_iter()
115            .chain(std::iter::once(crate::memory_manager_governance_range()))
116        {
117            for id in range.start()..=range.end() {
118                excluded[usize::from(id)] = true;
119            }
120        }
121        let mut excluded_ranges = Vec::new();
122        let mut id = 0;
123        while id < 255 {
124            if !excluded[id] {
125                id += 1;
126                continue;
127            }
128            let start = id;
129            while id + 1 < 255 && excluded[id + 1] {
130                id += 1;
131            }
132            excluded_ranges.push(
133                MemoryManagerIdRange::new(
134                    u8::try_from(start).expect("usable start"),
135                    u8::try_from(id).expect("usable end"),
136                )
137                .expect("ordered usable range"),
138            );
139            id += 1;
140        }
141        Ok(Self {
142            authorities,
143            excluded_ranges,
144        })
145    }
146
147    /// Current owner grants, in canonical namespace order.
148    #[must_use]
149    pub fn authorities(&self) -> &[MemoryAuthority] {
150        &self.authorities
151    }
152
153    /// Physical exclusions including the permanent governance reservation.
154    #[must_use]
155    pub fn excluded_ranges(&self) -> &[MemoryManagerIdRange] {
156        &self.excluded_ranges
157    }
158
159    /// Whether an ID belongs to the shared application pool.
160    #[must_use]
161    pub fn contains(&self, id: u8) -> bool {
162        id != crate::MEMORY_MANAGER_INVALID_ID
163            && !self.excluded_ranges.iter().any(|range| range.contains(id))
164    }
165
166    /// Validate current key ownership independently of numeric placement.
167    pub fn validate_authority(
168        &self,
169        key: &StableKey,
170        authority: &str,
171    ) -> Result<(), MemoryAllocationPoolError> {
172        let admitted_authority =
173            self.authority_for_key(key)
174                .ok_or_else(|| MemoryAllocationPoolError::UnclaimedKey {
175                    stable_key: key.clone(),
176                })?;
177        if admitted_authority != authority {
178            return Err(MemoryAllocationPoolError::AuthorityMismatch {
179                stable_key: key.clone(),
180                requested_authority: authority.to_string(),
181                admitted_authority: admitted_authority.to_string(),
182            });
183        }
184        Ok(())
185    }
186
187    // Committed keys were admitted by resolution. Diagnostic and adoption
188    // projections borrow the same host owner instead of retaining another map.
189    pub(crate) fn authority_for_key(&self, key: &StableKey) -> Option<&str> {
190        self.authorities
191            .iter()
192            .find(|grant| key.as_str().starts_with(&grant.key_prefix))
193            .map(MemoryAuthority::authority)
194    }
195
196    /// Validate physical eligibility without granting ownership of a key.
197    pub fn validate_id(&self, id: u8) -> Result<(), MemoryAllocationPoolError> {
198        crate::validate_memory_manager_id(id)?;
199        if !self.contains(id) {
200            return Err(MemoryAllocationPoolError::ExcludedSlot { id });
201        }
202        Ok(())
203    }
204}
205
206impl<'de> Deserialize<'de> for MemoryAllocationPool {
207    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
208        #[derive(Deserialize)]
209        #[serde(deny_unknown_fields)]
210        struct Pool {
211            authorities: Vec<MemoryAuthority>,
212            excluded_ranges: Vec<MemoryManagerIdRange>,
213        }
214        let pool = Pool::deserialize(deserializer)?;
215        Self::new(pool.authorities, pool.excluded_ranges).map_err(D::Error::custom)
216    }
217}
218
219///
220/// MemoryAllocationPoolError
221///
222/// Invalid host configuration or a request outside admitted ownership/custody.
223///
224
225#[non_exhaustive]
226#[derive(Clone, Debug, Eq, PartialEq, thiserror::Error)]
227pub enum MemoryAllocationPoolError {
228    #[error("host allocation policy exceeds the bounded slot domain")]
229    TooManyEntries,
230    #[error("authority {reason}")]
231    InvalidAuthority { reason: &'static str },
232    #[error("ic-memory governance authority cannot be granted externally")]
233    ReservedAuthority,
234    #[error("invalid application key namespace prefix {key_prefix}")]
235    InvalidKeyPrefix { key_prefix: String },
236    #[error("key namespaces {existing_prefix} and {candidate_prefix} overlap")]
237    OverlappingNamespaces {
238        existing_prefix: String,
239        candidate_prefix: String,
240    },
241    #[error("stable key {stable_key} has no host namespace grant")]
242    UnclaimedKey { stable_key: StableKey },
243    #[error(
244        "stable key {stable_key} is granted to {admitted_authority}, not {requested_authority}"
245    )]
246    AuthorityMismatch {
247        stable_key: StableKey,
248        requested_authority: String,
249        admitted_authority: String,
250    },
251    #[error("MemoryManager ID {id} is excluded from the application pool")]
252    ExcludedSlot { id: u8 },
253    #[error(transparent)]
254    Slot(#[from] crate::MemoryManagerSlotError),
255}
256
257#[cfg(test)]
258mod tests {
259    #[test]
260    fn namespace_admission_checks_segments_and_complete_key_length() {
261        for prefix in ["a.", "app.a_0.", "app.v0.", "app.v1."] {
262            let grant = super::MemoryAuthority::new("app", prefix).unwrap();
263            assert_eq!(grant.key_prefix(), prefix);
264        }
265        for prefix in ["", ".", "app", "app..", "app.0.", "App.", "app/a."] {
266            assert!(matches!(
267                super::MemoryAuthority::new("app", prefix),
268                Err(super::MemoryAllocationPoolError::InvalidKeyPrefix { key_prefix })
269                    if key_prefix == prefix
270            ));
271        }
272        for byte in 0..=u8::MAX {
273            let prefix = format!("app.a{}.", char::from(byte));
274            let allowed = byte.is_ascii_lowercase() || byte.is_ascii_digit() || byte == b'_';
275            assert_eq!(super::MemoryAuthority::new("app", prefix).is_ok(), allowed);
276        }
277        assert!(super::MemoryAuthority::new("app", format!("{}.", "a".repeat(125))).is_ok());
278        assert!(matches!(
279            super::MemoryAuthority::new("app", format!("{}.", "a".repeat(126))),
280            Err(super::MemoryAllocationPoolError::InvalidKeyPrefix { .. })
281        ));
282    }
283
284    use super::*;
285
286    #[test]
287    fn canonical_policy_has_one_physical_pool_and_disjoint_namespaces() {
288        let grant = |owner, prefix| MemoryAuthority::new(owner, prefix).unwrap();
289        let pool = MemoryAllocationPool::new(
290            vec![grant("db", "db."), grant("app", "app.")],
291            vec![
292                MemoryManagerIdRange::new(20, 25).unwrap(),
293                MemoryManagerIdRange::new(23, 30).unwrap(),
294                MemoryManagerIdRange::new(31, 31).unwrap(),
295            ],
296        )
297        .unwrap();
298        assert_eq!(pool.authorities()[0].authority(), "app");
299        assert_eq!(
300            pool.excluded_ranges(),
301            &[
302                MemoryManagerIdRange::new(0, 9).unwrap(),
303                MemoryManagerIdRange::new(20, 31).unwrap()
304            ]
305        );
306        for id in [0, 9, 20, 31, 255] {
307            assert!(!pool.contains(id));
308        }
309        for id in [10, 19, 32, 254] {
310            assert!(pool.contains(id));
311        }
312        assert!(matches!(
313            MemoryAllocationPool::new(vec![grant("app", "app."), grant("db", "app.db.")], vec![]),
314            Err(MemoryAllocationPoolError::OverlappingNamespaces { .. })
315        ));
316        assert!(
317            pool.validate_authority(&StableKey::parse("application.rows.v1").unwrap(), "app")
318                .is_err()
319        );
320        assert!(
321            pool.validate_authority(&StableKey::parse("app.rows.v1").unwrap(), "db")
322                .is_err()
323        );
324    }
325
326    #[test]
327    fn decoding_cannot_bypass_namespace_or_physical_exclusion_admission() {
328        let pool: MemoryAllocationPool = serde_json::from_str(
329            r#"{
330            "authorities":[{"authority":"app","key_prefix":"app."}],
331            "excluded_ranges":[{"start":10,"end":10}]
332        }"#,
333        )
334        .unwrap();
335        assert!(!pool.contains(0));
336        assert!(!pool.contains(10));
337        assert!(pool.contains(11));
338        for json in [
339            r#"{"authorities":[{"authority":"ic-memory","key_prefix":"app."}],"excluded_ranges":[]}"#,
340            r#"{"authorities":[{"authority":"app","key_prefix":"ic_memory."}],"excluded_ranges":[]}"#,
341            r#"{"authorities":[],"excluded_ranges":[{"start":254,"end":255}]}"#,
342            r#"{"authorities":[],"excluded_ranges":[],"unknown":true}"#,
343        ] {
344            assert!(serde_json::from_str::<MemoryAllocationPool>(json).is_err());
345        }
346        assert_eq!(
347            serde_json::from_str::<MemoryAllocationPool>(&serde_json::to_string(&pool).unwrap())
348                .unwrap(),
349            pool
350        );
351    }
352}
ic_memory/allocation_pool.rs

ic_memory/
allocation_pool.rs
