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

ic_memory/
allocation_pool.rs
