miden_tx/host/
link_map.rs

1use alloc::vec::Vec;
2use core::cmp::Ordering;
3
4use miden_objects::{Felt, LexicographicWord, Word, ZERO};
5use miden_processor::{AdviceMutation, ContextId, EventError, ProcessState};
6
7// LINK MAP
8// ================================================================================================
9
10/// A map based on a sorted linked list.
11///
12/// This type enables access to the list in kernel memory.
13///
14/// See link_map.masm for docs.
15///
16/// # Warning
17///
18/// The functions on this type assume that the provided map_ptr points to a valid map in the
19/// provided process. If those assumptions are violated, the functions may panic.
20#[derive(Debug, Clone, Copy)]
21pub struct LinkMap<'process> {
22    map_ptr: u32,
23    process: &'process ProcessState<'process>,
24}
25
26impl<'process> LinkMap<'process> {
27    // CONSTRUCTOR
28    // --------------------------------------------------------------------------------------------
29
30    /// Creates a new link map from the provided map_ptr in the provided process.
31    pub fn new(map_ptr: Felt, process: &'process ProcessState<'process>) -> Self {
32        let map_ptr: u32 = map_ptr.try_into().expect("map_ptr must be a valid u32");
33
34        Self { map_ptr, process }
35    }
36
37    // PUBLIC METHODS
38    // --------------------------------------------------------------------------------------------
39
40    /// Handles a `LINK_MAP_SET_EVENT` emitted from a VM.
41    ///
42    /// Expected operand stack state before: [map_ptr, KEY, NEW_VALUE]
43    /// Advice stack state after: [set_operation, entry_ptr]
44    pub fn handle_set_event(process: &ProcessState<'_>) -> Result<Vec<AdviceMutation>, EventError> {
45        let map_ptr = process.get_stack_item(0);
46        let map_key = Word::from([
47            process.get_stack_item(4),
48            process.get_stack_item(3),
49            process.get_stack_item(2),
50            process.get_stack_item(1),
51        ]);
52
53        let link_map = LinkMap::new(map_ptr, process);
54
55        let (set_op, entry_ptr) = link_map.compute_set_operation(LexicographicWord::from(map_key));
56
57        Ok(vec![AdviceMutation::extend_stack([
58            Felt::from(set_op as u8),
59            Felt::from(entry_ptr),
60        ])])
61    }
62
63    /// Handles a `LINK_MAP_GET_EVENT` emitted from a VM.
64    ///
65    /// Expected operand stack state before: [map_ptr, KEY]
66    /// Advice stack state after: [get_operation, entry_ptr]
67    pub fn handle_get_event(process: &ProcessState<'_>) -> Result<Vec<AdviceMutation>, EventError> {
68        let map_ptr = process.get_stack_item(0);
69        let map_key = Word::from([
70            process.get_stack_item(4),
71            process.get_stack_item(3),
72            process.get_stack_item(2),
73            process.get_stack_item(1),
74        ]);
75
76        let link_map = LinkMap::new(map_ptr, process);
77        let (get_op, entry_ptr) = link_map.compute_get_operation(LexicographicWord::from(map_key));
78
79        Ok(vec![AdviceMutation::extend_stack([
80            Felt::from(get_op as u8),
81            Felt::from(entry_ptr),
82        ])])
83    }
84
85    /// Returns `true` if the map is empty, `false` otherwise.
86    pub fn is_empty(&self) -> bool {
87        self.head().is_none()
88    }
89
90    /// Returns an iterator over the link map entries.
91    pub fn iter(&self) -> impl Iterator<Item = Entry> {
92        LinkMapIter {
93            current_entry_ptr: self.head().unwrap_or(0),
94            map: *self,
95        }
96    }
97
98    // PRIVATE METHODS
99    // --------------------------------------------------------------------------------------------
100
101    /// Returns the entry pointer at the head of the map or `None` if the map is empty.
102    fn head(&self) -> Option<u32> {
103        // Returns None if the value was either not yet initialized or points to 0.
104        // It can point to 0 for example if a get operation is executed before a set operation,
105        // which initializes the value in memory to 0 but does not change it.
106        self.get_kernel_mem_value(self.map_ptr).and_then(|head_ptr| {
107            if head_ptr == ZERO {
108                None
109            } else {
110                Some(u32::try_from(head_ptr).expect("head ptr should be a valid ptr"))
111            }
112        })
113    }
114
115    /// Returns the [`Entry`] at the given pointer.
116    fn entry(&self, entry_ptr: u32) -> Entry {
117        let key = self.key(entry_ptr);
118        let (value0, value1) = self.value(entry_ptr);
119        let metadata = self.metadata(entry_ptr);
120
121        Entry {
122            ptr: entry_ptr,
123            metadata,
124            key,
125            value0,
126            value1,
127        }
128    }
129
130    /// Returns the key of the entry at the given pointer.
131    fn key(&self, entry_ptr: u32) -> LexicographicWord {
132        LexicographicWord::from(
133            self.get_kernel_mem_word(entry_ptr + 4).expect("entry pointer should be valid"),
134        )
135    }
136
137    /// Returns the values of the entry at the given pointer.
138    fn value(&self, entry_ptr: u32) -> (Word, Word) {
139        let value0 =
140            self.get_kernel_mem_word(entry_ptr + 8).expect("entry pointer should be valid");
141        let value1 =
142            self.get_kernel_mem_word(entry_ptr + 12).expect("entry pointer should be valid");
143        (value0, value1)
144    }
145
146    /// Returns the metadata of the entry at the given pointer.
147    fn metadata(&self, entry_ptr: u32) -> EntryMetadata {
148        let entry_metadata =
149            self.get_kernel_mem_word(entry_ptr).expect("entry pointer should be valid");
150
151        let map_ptr = entry_metadata[0];
152        let map_ptr = map_ptr.try_into().expect("entry_ptr should point to a u32 map_ptr");
153
154        let prev_entry_ptr = entry_metadata[1];
155        let prev_entry_ptr = prev_entry_ptr
156            .try_into()
157            .expect("entry_ptr should point to a u32 prev_entry_ptr");
158
159        let next_entry_ptr = entry_metadata[2];
160        let next_entry_ptr = next_entry_ptr
161            .try_into()
162            .expect("entry_ptr should point to a u32 next_entry_ptr");
163
164        EntryMetadata { map_ptr, prev_entry_ptr, next_entry_ptr }
165    }
166
167    /// Computes what needs to be done to insert the given key into the link map.
168    ///
169    /// If the key already exists in the map, then its value must be updated and
170    /// [`SetOperation::Update`] and the pointer to the existing entry are returned.
171    ///
172    /// If the key does not exist in the map, find the place where it has to be inserted. This can
173    /// be at the head of the list ([`SetOperation::InsertAtHead`]) if the key is smaller than all
174    /// existing keys or if the map is empty. Otherwise it is after an existing entry
175    /// ([`SetOperation::InsertAfterEntry`]) in which case the key must be greater than the entry's
176    /// key after which it is inserted and smaller than the entry before which it is inserted
177    /// (unless it is the end of the map).
178    fn compute_set_operation(&self, key: LexicographicWord) -> (SetOperation, u32) {
179        let Some(current_head) = self.head() else {
180            return (SetOperation::InsertAtHead, 0);
181        };
182
183        let mut last_entry_ptr: u32 = current_head;
184
185        for entry in self.iter() {
186            match key.cmp(&entry.key) {
187                Ordering::Equal => {
188                    return (SetOperation::Update, entry.ptr);
189                },
190                Ordering::Less => {
191                    if entry.ptr == current_head {
192                        return (SetOperation::InsertAtHead, entry.ptr);
193                    }
194
195                    break;
196                },
197                Ordering::Greater => {
198                    last_entry_ptr = entry.ptr;
199                },
200            }
201        }
202
203        (SetOperation::InsertAfterEntry, last_entry_ptr)
204    }
205
206    /// Computes a get operation for a key in a link map.
207    ///
208    /// If the key exists, then [`GetOperation::Found`] is returned and the pointer to it.
209    ///
210    /// If it does not exist, its absence must be proven, otherwise the host could lie. To do that,
211    /// the in-kernel link map validates that the key is not in the list, so this function returns
212    /// information pointing to the entry where the key would be if it existed.
213    ///
214    /// The way to compute this is the same as a set operation, so this function simply remaps its
215    /// output.
216    fn compute_get_operation(&self, key: LexicographicWord) -> (GetOperation, u32) {
217        let (set_op, entry_ptr) = self.compute_set_operation(key);
218        let get_op = match set_op {
219            SetOperation::Update => GetOperation::Found,
220            SetOperation::InsertAtHead => GetOperation::AbsentAtHead,
221            SetOperation::InsertAfterEntry => GetOperation::AbsentAfterEntry,
222        };
223        (get_op, entry_ptr)
224    }
225
226    // HELPER METHODS
227    // --------------------------------------------------------------------------------------------
228
229    fn get_kernel_mem_value(&self, addr: u32) -> Option<Felt> {
230        self.process.get_mem_value(ContextId::root(), addr)
231    }
232
233    fn get_kernel_mem_word(&self, addr: u32) -> Option<Word> {
234        self.process
235            .get_mem_word(ContextId::root(), addr)
236            .expect("address should be word-aligned")
237    }
238}
239
240// LINK MAP ITER
241// ================================================================================================
242
243/// An iterator over a [`LinkMap`].
244struct LinkMapIter<'process> {
245    current_entry_ptr: u32,
246    map: LinkMap<'process>,
247}
248
249impl<'process> Iterator for LinkMapIter<'process> {
250    type Item = Entry;
251
252    fn next(&mut self) -> Option<Self::Item> {
253        if self.current_entry_ptr == 0 {
254            return None;
255        }
256
257        let current_entry = self.map.entry(self.current_entry_ptr);
258
259        self.current_entry_ptr = current_entry.metadata.next_entry_ptr;
260
261        Some(current_entry)
262    }
263}
264
265// LINK MAP TYPES
266// ================================================================================================
267
268/// An entry in a [`LinkMap`].
269///
270/// Exposed for testing purposes only.
271#[derive(Debug, Clone, Copy)]
272pub struct Entry {
273    pub ptr: u32,
274    pub metadata: EntryMetadata,
275    pub key: LexicographicWord,
276    pub value0: Word,
277    pub value1: Word,
278}
279
280/// An entry's metadata in a [`LinkMap`].
281///
282/// Exposed for testing purposes only.
283#[derive(Debug, Clone, Copy)]
284pub struct EntryMetadata {
285    pub map_ptr: u32,
286    pub prev_entry_ptr: u32,
287    pub next_entry_ptr: u32,
288}
289
290// HELPER TYPES
291// ================================================================================================
292
293/// The operation needed to get a key or prove its absence.
294#[derive(Debug, Clone, Copy)]
295#[repr(u8)]
296enum GetOperation {
297    Found = 0,
298    AbsentAtHead = 1,
299    AbsentAfterEntry = 2,
300}
301
302/// The operation needed to set a key.
303#[derive(Debug, Clone, Copy)]
304#[repr(u8)]
305enum SetOperation {
306    Update = 0,
307    InsertAtHead = 1,
308    InsertAfterEntry = 2,
309}
miden_tx/host/link_map.rs

miden_tx/host/
link_map.rs
