openvm_circuit/system/memory/
mod.rs

1use std::sync::Arc;
2
3use openvm_circuit_primitives::{is_less_than::IsLtSubAir, var_range::VariableRangeCheckerBus};
4use openvm_circuit_primitives_derive::AlignedBorrow;
5use openvm_stark_backend::{
6    config::{StarkGenericConfig, Val},
7    interaction::PermutationCheckBus,
8    p3_field::Field,
9    p3_util::{log2_ceil_usize, log2_strict_usize},
10    AirRef,
11};
12
13pub mod adapter;
14mod controller;
15pub mod merkle;
16pub mod offline_checker;
17pub mod online;
18pub mod persistent;
19#[cfg(test)]
20mod tests;
21pub mod volatile;
22
23pub use controller::*;
24pub use online::{Address, AddressMap, INITIAL_TIMESTAMP};
25
26use crate::{
27    arch::{MemoryConfig, ADDR_SPACE_OFFSET},
28    system::memory::{
29        adapter::AccessAdapterAir, dimensions::MemoryDimensions, interface::MemoryInterfaceAirs,
30        merkle::MemoryMerkleAir, offline_checker::MemoryBridge, persistent::PersistentBoundaryAir,
31        volatile::VolatileBoundaryAir,
32    },
33};
34
35// @dev Currently this is only used for debug assertions, but we may switch to making it constant
36// and removing from MemoryConfig
37pub const POINTER_MAX_BITS: usize = 29;
38
39#[derive(PartialEq, Copy, Clone, Debug, Eq)]
40pub enum OpType {
41    Read = 0,
42    Write = 1,
43}
44
45/// The full pointer to a location in memory consists of an address space and a pointer within
46/// the address space.
47#[derive(Clone, Copy, Debug, PartialEq, Eq, AlignedBorrow)]
48#[repr(C)]
49pub struct MemoryAddress<S, T> {
50    pub address_space: S,
51    pub pointer: T,
52}
53
54impl<S, T> MemoryAddress<S, T> {
55    pub fn new(address_space: S, pointer: T) -> Self {
56        Self {
57            address_space,
58            pointer,
59        }
60    }
61
62    pub fn from<T1, T2>(a: MemoryAddress<T1, T2>) -> Self
63    where
64        T1: Into<S>,
65        T2: Into<T>,
66    {
67        Self {
68            address_space: a.address_space.into(),
69            pointer: a.pointer.into(),
70        }
71    }
72}
73
74#[derive(Clone)]
75pub struct MemoryAirInventory<SC: StarkGenericConfig> {
76    pub bridge: MemoryBridge,
77    pub interface: MemoryInterfaceAirs,
78    pub access_adapters: Vec<AirRef<SC>>,
79}
80
81impl<SC: StarkGenericConfig> MemoryAirInventory<SC> {
82    pub fn new(
83        bridge: MemoryBridge,
84        mem_config: &MemoryConfig,
85        range_bus: VariableRangeCheckerBus,
86        merkle_compression_buses: Option<(PermutationCheckBus, PermutationCheckBus)>,
87    ) -> Self {
88        let memory_bus = bridge.memory_bus();
89        let interface = if let Some((merkle_bus, compression_bus)) = merkle_compression_buses {
90            // Persistent memory
91            let memory_dims = MemoryDimensions {
92                addr_space_height: mem_config.addr_space_height,
93                address_height: mem_config.pointer_max_bits - log2_strict_usize(CHUNK),
94            };
95            let boundary = PersistentBoundaryAir::<CHUNK> {
96                memory_dims,
97                memory_bus,
98                merkle_bus,
99                compression_bus,
100            };
101            let merkle = MemoryMerkleAir::<CHUNK> {
102                memory_dimensions: memory_dims,
103                merkle_bus,
104                compression_bus,
105            };
106            MemoryInterfaceAirs::Persistent { boundary, merkle }
107        } else {
108            // Volatile memory
109            let addr_space_height = mem_config.addr_space_height;
110            assert!(addr_space_height < Val::<SC>::bits() - 2);
111            let addr_space_max_bits =
112                log2_ceil_usize((ADDR_SPACE_OFFSET + 2u32.pow(addr_space_height as u32)) as usize);
113            let boundary = VolatileBoundaryAir::new(
114                memory_bus,
115                addr_space_max_bits,
116                mem_config.pointer_max_bits,
117                range_bus,
118            );
119            MemoryInterfaceAirs::Volatile { boundary }
120        };
121        // Memory access adapters
122        let lt_air = IsLtSubAir::new(range_bus, mem_config.timestamp_max_bits);
123        let maan = mem_config.max_access_adapter_n;
124        assert!(matches!(maan, 2 | 4 | 8 | 16 | 32));
125        let access_adapters: Vec<AirRef<SC>> = [
126            Arc::new(AccessAdapterAir::<2> { memory_bus, lt_air }) as AirRef<SC>,
127            Arc::new(AccessAdapterAir::<4> { memory_bus, lt_air }) as AirRef<SC>,
128            Arc::new(AccessAdapterAir::<8> { memory_bus, lt_air }) as AirRef<SC>,
129            Arc::new(AccessAdapterAir::<16> { memory_bus, lt_air }) as AirRef<SC>,
130            Arc::new(AccessAdapterAir::<32> { memory_bus, lt_air }) as AirRef<SC>,
131        ]
132        .into_iter()
133        .take(log2_strict_usize(maan))
134        .collect();
135
136        Self {
137            bridge,
138            interface,
139            access_adapters,
140        }
141    }
142
143    /// The order of memory AIRs is boundary, merkle (if exists), access adapters
144    pub fn into_airs(self) -> Vec<AirRef<SC>> {
145        let mut airs: Vec<AirRef<SC>> = Vec::new();
146        match self.interface {
147            MemoryInterfaceAirs::Volatile { boundary } => {
148                airs.push(Arc::new(boundary));
149            }
150            MemoryInterfaceAirs::Persistent { boundary, merkle } => {
151                airs.push(Arc::new(boundary));
152                airs.push(Arc::new(merkle));
153            }
154        }
155        airs.extend(self.access_adapters);
156        airs
157    }
158}
159
160/// This is O(1) and returns the length of
161/// [`MemoryAirInventory::into_airs`].
162pub fn num_memory_airs(is_persistent: bool, max_access_adapter_n: usize) -> usize {
163    // boundary + { merkle if is_persistent } + access_adapters
164    1 + usize::from(is_persistent) + log2_strict_usize(max_access_adapter_n)
165}
openvm_circuit/system/memory/mod.rs

openvm_circuit/system/memory/
mod.rs
