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 !key_prefix.ends_with('.') || StableKey::parse(format!("{key_prefix}v1")).is_err() {
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        authorities.sort_unstable_by(|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    use super::*;
260
261    #[test]
262    fn canonical_policy_has_one_physical_pool_and_disjoint_namespaces() {
263        let grant = |owner, prefix| MemoryAuthority::new(owner, prefix).unwrap();
264        let pool = MemoryAllocationPool::new(
265            vec![grant("db", "db."), grant("app", "app.")],
266            vec![
267                MemoryManagerIdRange::new(20, 25).unwrap(),
268                MemoryManagerIdRange::new(23, 30).unwrap(),
269                MemoryManagerIdRange::new(31, 31).unwrap(),
270            ],
271        )
272        .unwrap();
273        assert_eq!(pool.authorities()[0].authority(), "app");
274        assert_eq!(
275            pool.excluded_ranges(),
276            &[
277                MemoryManagerIdRange::new(0, 9).unwrap(),
278                MemoryManagerIdRange::new(20, 31).unwrap()
279            ]
280        );
281        for id in [0, 9, 20, 31, 255] {
282            assert!(!pool.contains(id));
283        }
284        for id in [10, 19, 32, 254] {
285            assert!(pool.contains(id));
286        }
287        assert!(matches!(
288            MemoryAllocationPool::new(vec![grant("app", "app."), grant("db", "app.db.")], vec![]),
289            Err(MemoryAllocationPoolError::OverlappingNamespaces { .. })
290        ));
291        assert!(
292            pool.validate_authority(&StableKey::parse("application.rows.v1").unwrap(), "app")
293                .is_err()
294        );
295        assert!(
296            pool.validate_authority(&StableKey::parse("app.rows.v1").unwrap(), "db")
297                .is_err()
298        );
299    }
300
301    #[test]
302    fn decoding_cannot_bypass_namespace_or_physical_exclusion_admission() {
303        let pool: MemoryAllocationPool = serde_json::from_str(
304            r#"{
305            "authorities":[{"authority":"app","key_prefix":"app."}],
306            "excluded_ranges":[{"start":10,"end":10}]
307        }"#,
308        )
309        .unwrap();
310        assert!(!pool.contains(0));
311        assert!(!pool.contains(10));
312        assert!(pool.contains(11));
313        for json in [
314            r#"{"authorities":[{"authority":"ic-memory","key_prefix":"app."}],"excluded_ranges":[]}"#,
315            r#"{"authorities":[{"authority":"app","key_prefix":"ic_memory."}],"excluded_ranges":[]}"#,
316            r#"{"authorities":[],"excluded_ranges":[{"start":254,"end":255}]}"#,
317            r#"{"authorities":[],"excluded_ranges":[],"unknown":true}"#,
318        ] {
319            assert!(serde_json::from_str::<MemoryAllocationPool>(json).is_err());
320        }
321        assert_eq!(
322            serde_json::from_str::<MemoryAllocationPool>(&serde_json::to_string(&pool).unwrap())
323                .unwrap(),
324            pool
325        );
326    }
327}
ic_memory/allocation_pool.rs

ic_memory/
allocation_pool.rs
