subetha_pointers/
k_tower_pointer.rs

1//! `KTowerPointer<T>` - recursive pow2-of-pow2 address decomposition.
2//!
3//! Direct analog of quartz's `Tower<T, [K_a, K_b, ...]>` lifted to
4//! pointers. The key idea is RECURSIVE: a pointer is a pow2 block
5//! split into segments where each segment can ITSELF be a pow2 block
6//! split into further segments, all the way down. The hardware MMU
7//! does exactly this (x86_64 page tables are PML4 -> PDPT -> PD -> PT,
8//! four levels of 9-bit indices into nested tables). KTower lifts the
9//! same recursive-table mechanism to userspace, operating on indices
10//! rather than physical pages.
11//!
12//! # Two flat shipped variants (the base cases of the recursion)
13//!
14//! - [`KTower2<T>`]: two-segment `(region_id: u32, offset: u32)`
15//!   packed into a u64. The region table is supplied by the caller
16//!   (typically a `Vec<*mut u8>` of region base pointers). Resolves
17//!   via `region_table[region_id] + offset`. Equivalent to one MMU
18//!   page-table level.
19//!
20//! - [`KTower3<T>`]: three-segment `(zone: u16, region_id: u16,
21//!   offset: u32)` for hierarchical naming (zone -> region -> slot).
22//!   Useful for distributed storage where zones are racks / data
23//!   centers and regions are nodes within a zone. Equivalent to two
24//!   MMU page-table levels packed into one word.
25//!
26//! Both variants are 8 bytes total - same slot size as a native
27//! pointer, but the address space is now multi-segment.
28//!
29//! # The recursive form (KTowerCascade)
30//!
31//! ```text
32//! KTower2<T>     = (region_id: u32, offset: u32)
33//!                = (KTower2<RegionTable<T>>, u32)  // recursive form
34//!                = KTower2<KTower2<KTower2<KTower2<T>>>>  // 4 levels
35//! ```
36//!
37//! Each region_id at level N indexes into a TABLE OF KTower2 pointers
38//! at level N-1. At the leaf (level 0), the offset is the actual byte
39//! offset within a physical region. The depth is a runtime / type-
40//! level choice: shallow towers for dense address spaces, deep towers
41//! for sparse ones.
42//!
43//! # The architectural win
44//!
45//! 1. **Tiered storage**: a native 64-bit pointer can only address
46//!    one tier (the OS virtual address space). With KTower the
47//!    `region_id` selects the tier (RAM / SSD / remote / archive)
48//!    and the `offset` selects within. The dispatch table for "load
49//!    from this pointer" branches on `region_id` (8-256 entries)
50//!    without touching the target.
51//!
52//! 2. **Userspace MMU**: SharedRing is "QUIC over TCP" - userspace
53//!    transport that bypasses the kernel by replicating the kernel's
54//!    mechanism. KTowerCascade is the same shape one layer down: a
55//!    userspace virtual-address translator that does what the
56//!    hardware MMU does, but on indices instead of physical pages,
57//!    and works cross-process because the indices are byte-identical
58//!    in every mapping.
59//!
60//! 3. **Adaptive depth**: hot data uses 1-level (flat index, fastest
61//!    lookup); medium data uses 2-level (recursive but small); cold
62//!    sparse data uses 4-level (deep tree, minimal storage for empty
63//!    regions). The `K_outer` axis from quartz applied to addressing:
64//!    pick the recursion depth at runtime based on observed
65//!    sparsity, like AdaptivePointer migrating between encodings.
66//!
67//! 4. **Position independence is preserved through composition**: a
68//!    `KTower2<KTower2<T>>` is still 8 bytes total because each level's
69//!    region_id is a u32 INDEX into the previous level's table. No
70//!    virtual addresses at any level, so the whole tower resolves
71//!    identically in any process that holds the same region tables.
72
73use std::marker::PhantomData;
74
75/// Two-segment pointer: `(region_id: u32 high, offset: u32 low)`.
76/// Resolution requires a region-base table.
77#[repr(transparent)]
78pub struct KTower2<T> {
79    raw: u64,
80    _phantom: PhantomData<*const T>,
81}
82
83unsafe impl<T: Send> Send for KTower2<T> {}
84unsafe impl<T: Sync> Sync for KTower2<T> {}
85
86impl<T> KTower2<T> {
87    /// Direction signature of `KTower2<T>`. Engages the
88    /// `K_segmented` axis (two-segment `(region_id, offset)` address
89    /// space).
90    pub const SIGNATURE: subetha_core::AxisMask = subetha_core::AxisMask::from_axes(
91        &[subetha_core::Axis::Segmented],
92    );
93
94    #[inline]
95    pub const fn new(region_id: u32, offset: u32) -> Self {
96        let raw = ((region_id as u64) << 32) | (offset as u64);
97        Self { raw, _phantom: PhantomData }
98    }
99
100    #[inline]
101    pub const fn region_id(&self) -> u32 { (self.raw >> 32) as u32 }
102    #[inline]
103    pub const fn offset(&self) -> u32 { (self.raw & 0xFFFF_FFFF) as u32 }
104    #[inline]
105    pub const fn raw(&self) -> u64 { self.raw }
106
107    /// Resolve to a real address using a region-base table.
108    /// `region_table[region_id]` is the base pointer of the region.
109    ///
110    /// # Safety
111    ///
112    /// `region_id` must be a valid index into `region_table`; the
113    /// resulting address `base + offset` must be a valid `T`.
114    pub unsafe fn resolve(&self, region_table: &[*const u8]) -> *const T {
115        let base = region_table[self.region_id() as usize];
116        unsafe { base.add(self.offset() as usize) as *const T }
117    }
118}
119
120impl<T> Clone for KTower2<T> {
121    fn clone(&self) -> Self { *self }
122}
123impl<T> Copy for KTower2<T> {}
124
125impl<T> std::fmt::Debug for KTower2<T> {
126    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
127        write!(f, "KTower2 {{ region: {}, offset: {:#x} }}",
128               self.region_id(), self.offset())
129    }
130}
131
132impl<T> PartialEq for KTower2<T> {
133    fn eq(&self, other: &Self) -> bool { self.raw == other.raw }
134}
135impl<T> Eq for KTower2<T> {}
136
137/// Three-segment pointer: `(zone: u16, region: u16, offset: u32)`.
138/// Hierarchical: zone -> region -> within-region offset.
139#[repr(transparent)]
140pub struct KTower3<T> {
141    raw: u64,
142    _phantom: PhantomData<*const T>,
143}
144
145unsafe impl<T: Send> Send for KTower3<T> {}
146unsafe impl<T: Sync> Sync for KTower3<T> {}
147
148impl<T> KTower3<T> {
149    /// Direction signature of `KTower3<T>`. Engages the
150    /// `K_segmented` axis (three-segment `(zone, region, offset)`
151    /// hierarchical address space).
152    pub const SIGNATURE: subetha_core::AxisMask = subetha_core::AxisMask::from_axes(
153        &[subetha_core::Axis::Segmented],
154    );
155
156    #[inline]
157    pub const fn new(zone: u16, region: u16, offset: u32) -> Self {
158        let raw = ((zone as u64) << 48) | ((region as u64) << 32) | (offset as u64);
159        Self { raw, _phantom: PhantomData }
160    }
161
162    #[inline]
163    pub const fn zone(&self) -> u16 { (self.raw >> 48) as u16 }
164    #[inline]
165    pub const fn region(&self) -> u16 { ((self.raw >> 32) & 0xFFFF) as u16 }
166    #[inline]
167    pub const fn offset(&self) -> u32 { (self.raw & 0xFFFF_FFFF) as u32 }
168    #[inline]
169    pub const fn raw(&self) -> u64 { self.raw }
170}
171
172impl<T> Clone for KTower3<T> {
173    fn clone(&self) -> Self { *self }
174}
175impl<T> Copy for KTower3<T> {}
176
177impl<T> std::fmt::Debug for KTower3<T> {
178    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
179        write!(f, "KTower3 {{ zone: {}, region: {}, offset: {:#x} }}",
180               self.zone(), self.region(), self.offset())
181    }
182}
183
184impl<T> PartialEq for KTower3<T> {
185    fn eq(&self, other: &Self) -> bool { self.raw == other.raw }
186}
187impl<T> Eq for KTower3<T> {}
188
189#[cfg(test)]
190mod tests {
191    use super::*;
192
193    #[test]
194    fn ktower2_layout_is_8_bytes() {
195        assert_eq!(std::mem::size_of::<KTower2<u64>>(), 8);
196    }
197
198    #[test]
199    fn ktower2_segments_round_trip() {
200        let p: KTower2<u64> = KTower2::new(7, 0xCAFE);
201        assert_eq!(p.region_id(), 7);
202        assert_eq!(p.offset(), 0xCAFE);
203    }
204
205    #[test]
206    fn ktower2_resolves_via_region_table() {
207        // Two regions of u64 values.
208        let region_a: Vec<u64> = vec![10, 20, 30, 40];
209        let region_b: Vec<u64> = vec![100, 200, 300, 400];
210        let table: Vec<*const u8> = vec![
211            region_a.as_ptr() as *const u8,
212            region_b.as_ptr() as *const u8,
213        ];
214        // Pointer to region 1, offset 8 bytes (second u64 = 200).
215        let p: KTower2<u64> = KTower2::new(1, 8);
216        let resolved = unsafe { p.resolve(&table) };
217        assert_eq!(unsafe { *resolved }, 200);
218        // Offset 16 bytes = third u64 = 300.
219        let p2: KTower2<u64> = KTower2::new(1, 16);
220        assert_eq!(unsafe { *p2.resolve(&table) }, 300);
221    }
222
223    #[test]
224    fn ktower3_layout_is_8_bytes() {
225        assert_eq!(std::mem::size_of::<KTower3<u64>>(), 8);
226    }
227
228    #[test]
229    fn ktower3_segments_round_trip() {
230        let p: KTower3<u64> = KTower3::new(3, 17, 0xDEAD);
231        assert_eq!(p.zone(), 3);
232        assert_eq!(p.region(), 17);
233        assert_eq!(p.offset(), 0xDEAD);
234    }
235
236    #[test]
237    fn ktower_segments_distinguishable() {
238        let a: KTower2<u64> = KTower2::new(1, 100);
239        let b: KTower2<u64> = KTower2::new(2, 100);
240        let c: KTower2<u64> = KTower2::new(1, 200);
241        assert_ne!(a, b, "different regions");
242        assert_ne!(a, c, "different offsets");
243        assert_eq!(a, KTower2::<u64>::new(1, 100));
244    }
245}
subetha_pointers/k_tower_pointer.rs

subetha_pointers/
k_tower_pointer.rs
