cranelift_interpreter/
address.rs

1//! Virtual Addressing Scheme for the Interpreter
2//!
3//! The interpreter uses virtual memory addresses for its memory operations. These addresses
4//! are obtained by the various `_addr` instructions (e.g. `stack_addr`) and can be either 32 or 64
5//! bits.
6//!
7//! Addresses are composed of 3 fields: "region", "entry" and offset.
8//!
9//! "region" refers to the type of memory that this address points to.
10//! "entry" refers to which instance of this memory the address points to (e.g table1 would be
11//! "entry" 1 of a `Table` region address).
12//! The last field is the "offset", which refers to the offset within the entry.
13//!
14//! The address has the "region" field as the 2 most significant bits. The following bits
15//! are the "entry" field, the amount of "entry" bits depends on the size of the address and
16//! the "region" of the address. The remaining bits belong to the "offset" field
17//!
18//! An example address could be a 32 bit address, in the `function` region, which has 1 "entry" bit
19//! this address would have 32 - 1 - 2 = 29 offset bits.
20//!
21//! The only exception to this is the "stack" region, where, because we only have a single "stack"
22//! we have 0 "entry" bits, and thus is all offset.
23//!
24//! | address size | address kind | region value (2 bits) | entry bits (#) | offset bits (#) |
25//! |--------------|--------------|-----------------------|----------------|-----------------|
26//! | 32           | Stack        | 0b00                  | 0              | 30              |
27//! | 32           | Function     | 0b01                  | 1              | 29              |
28//! | 32           | Table        | 0b10                  | 5              | 25              |
29//! | 32           | GlobalValue  | 0b11                  | 6              | 24              |
30//! | 64           | Stack        | 0b00                  | 0              | 62              |
31//! | 64           | Function     | 0b01                  | 1              | 61              |
32//! | 64           | Table        | 0b10                  | 10             | 52              |
33//! | 64           | GlobalValue  | 0b11                  | 12             | 50              |
34
35use crate::state::MemoryError;
36use cranelift_codegen::data_value::DataValue;
37use cranelift_codegen::ir::{types, Type};
38
39#[derive(Debug, Copy, Clone, PartialEq)]
40pub enum AddressSize {
41    _32,
42    _64,
43}
44
45impl AddressSize {
46    pub fn bits(&self) -> u64 {
47        match self {
48            AddressSize::_64 => 64,
49            AddressSize::_32 => 32,
50        }
51    }
52}
53
54impl TryFrom<Type> for AddressSize {
55    type Error = MemoryError;
56
57    fn try_from(ty: Type) -> Result<Self, Self::Error> {
58        match ty {
59            types::I64 => Ok(AddressSize::_64),
60            types::I32 => Ok(AddressSize::_32),
61            _ => Err(MemoryError::InvalidAddressType(ty)),
62        }
63    }
64}
65
66/// Virtual Address region
67#[derive(Debug, Copy, Clone, PartialEq)]
68pub enum AddressRegion {
69    Stack,
70    Function,
71    Table,
72    GlobalValue,
73}
74
75impl AddressRegion {
76    pub fn decode(bits: u64) -> Self {
77        assert!(bits < 4);
78        match bits {
79            0 => AddressRegion::Stack,
80            1 => AddressRegion::Function,
81            2 => AddressRegion::Table,
82            3 => AddressRegion::GlobalValue,
83            _ => unreachable!(),
84        }
85    }
86
87    pub fn encode(self) -> u64 {
88        match self {
89            AddressRegion::Stack => 0,
90            AddressRegion::Function => 1,
91            AddressRegion::Table => 2,
92            AddressRegion::GlobalValue => 3,
93        }
94    }
95}
96
97#[derive(Debug, Clone, PartialEq)]
98pub struct Address {
99    pub size: AddressSize,
100    pub region: AddressRegion,
101    pub entry: u64,
102    pub offset: u64,
103}
104
105impl Address {
106    pub fn from_parts(
107        size: AddressSize,
108        region: AddressRegion,
109        entry: u64,
110        offset: u64,
111    ) -> Result<Self, MemoryError> {
112        let entry_bits = Address::entry_bits(size, region);
113        let offset_bits = Address::offset_bits(size, region);
114
115        let max_entries = (1 << entry_bits) - 1;
116        let max_offset = (1 << offset_bits) - 1;
117
118        if entry > max_entries {
119            return Err(MemoryError::InvalidEntry {
120                entry,
121                max: max_entries,
122            });
123        }
124
125        if offset > max_offset {
126            return Err(MemoryError::InvalidOffset {
127                offset,
128                max: max_offset,
129            });
130        }
131
132        Ok(Address {
133            size,
134            region,
135            entry,
136            offset,
137        })
138    }
139
140    fn entry_bits(size: AddressSize, region: AddressRegion) -> u64 {
141        match (size, region) {
142            // We only have one stack, so the whole address is offset
143            (_, AddressRegion::Stack) => 0,
144
145            // We have two function "entries", one for libcalls, and
146            // another for user functions.
147            (_, AddressRegion::Function) => 1,
148
149            (AddressSize::_32, AddressRegion::Table) => 5,
150            (AddressSize::_32, AddressRegion::GlobalValue) => 6,
151
152            (AddressSize::_64, AddressRegion::Table) => 10,
153            (AddressSize::_64, AddressRegion::GlobalValue) => 12,
154        }
155    }
156
157    fn offset_bits(size: AddressSize, region: AddressRegion) -> u64 {
158        let region_bits = 2;
159        let entry_bits = Address::entry_bits(size, region);
160        size.bits() - entry_bits - region_bits
161    }
162}
163
164impl TryFrom<Address> for DataValue {
165    type Error = MemoryError;
166
167    fn try_from(addr: Address) -> Result<Self, Self::Error> {
168        let entry_bits = Address::entry_bits(addr.size, addr.region);
169        let offset_bits = Address::offset_bits(addr.size, addr.region);
170
171        let entry = addr.entry << offset_bits;
172        let region = addr.region.encode() << (entry_bits + offset_bits);
173
174        let value = region | entry | addr.offset;
175        Ok(match addr.size {
176            AddressSize::_32 => DataValue::I32(value as u32 as i32),
177            AddressSize::_64 => DataValue::I64(value as i64),
178        })
179    }
180}
181
182impl TryFrom<DataValue> for Address {
183    type Error = MemoryError;
184
185    fn try_from(value: DataValue) -> Result<Self, Self::Error> {
186        let addr = match value {
187            DataValue::I32(v) => v as u32 as u64,
188            DataValue::I64(v) => v as u64,
189            _ => {
190                return Err(MemoryError::InvalidAddress(value));
191            }
192        };
193
194        let size = match value {
195            DataValue::I32(_) => AddressSize::_32,
196            DataValue::I64(_) => AddressSize::_64,
197            _ => unreachable!(),
198        };
199
200        let region = AddressRegion::decode(addr >> (size.bits() - 2));
201
202        let entry_bits = Address::entry_bits(size, region);
203        let offset_bits = Address::offset_bits(size, region);
204
205        let entry = (addr >> offset_bits) & ((1 << entry_bits) - 1);
206        let offset = addr & ((1 << offset_bits) - 1);
207
208        Address::from_parts(size, region, entry, offset)
209    }
210}
211
212impl TryFrom<u64> for Address {
213    type Error = MemoryError;
214
215    fn try_from(value: u64) -> Result<Self, Self::Error> {
216        let dv = if value > u32::MAX as u64 {
217            DataValue::I64(value as i64)
218        } else {
219            DataValue::I32(value as i32)
220        };
221
222        Address::try_from(dv)
223    }
224}
225
226#[derive(Debug, Clone, PartialEq)]
227pub enum AddressFunctionEntry {
228    UserFunction = 0,
229    LibCall,
230}
231
232impl From<u64> for AddressFunctionEntry {
233    fn from(bits: u64) -> Self {
234        match bits {
235            0 => AddressFunctionEntry::UserFunction,
236            1 => AddressFunctionEntry::LibCall,
237            _ => unreachable!(),
238        }
239    }
240}
241
242#[cfg(test)]
243mod tests {
244    use super::*;
245
246    #[test]
247    fn address_region_roundtrip_encode_decode() {
248        let all_regions = [
249            AddressRegion::Stack,
250            AddressRegion::Function,
251            AddressRegion::Table,
252            AddressRegion::GlobalValue,
253        ];
254
255        for region in all_regions {
256            assert_eq!(AddressRegion::decode(region.encode()), region);
257        }
258    }
259
260    #[test]
261    fn address_roundtrip() {
262        let test_addresses = [
263            (AddressSize::_32, AddressRegion::Stack, 0, 0),
264            (AddressSize::_32, AddressRegion::Stack, 0, 1),
265            (AddressSize::_32, AddressRegion::Stack, 0, 1024),
266            (AddressSize::_32, AddressRegion::Stack, 0, 0x3FFF_FFFF),
267            (AddressSize::_32, AddressRegion::Function, 0, 0),
268            (AddressSize::_32, AddressRegion::Function, 1, 1),
269            (AddressSize::_32, AddressRegion::Function, 0, 1024),
270            (AddressSize::_32, AddressRegion::Function, 1, 0x0FFF_FFFF),
271            (AddressSize::_32, AddressRegion::Table, 0, 0),
272            (AddressSize::_32, AddressRegion::Table, 1, 1),
273            (AddressSize::_32, AddressRegion::Table, 31, 0x1FF_FFFF),
274            (AddressSize::_32, AddressRegion::GlobalValue, 0, 0),
275            (AddressSize::_32, AddressRegion::GlobalValue, 1, 1),
276            (AddressSize::_32, AddressRegion::GlobalValue, 63, 0xFF_FFFF),
277            (AddressSize::_64, AddressRegion::Stack, 0, 0),
278            (AddressSize::_64, AddressRegion::Stack, 0, 1),
279            (
280                AddressSize::_64,
281                AddressRegion::Stack,
282                0,
283                0x3FFFFFFF_FFFFFFFF,
284            ),
285            (AddressSize::_64, AddressRegion::Function, 0, 0),
286            (AddressSize::_64, AddressRegion::Function, 1, 1),
287            (AddressSize::_64, AddressRegion::Function, 0, 1024),
288            (AddressSize::_64, AddressRegion::Function, 1, 0x0FFF_FFFF),
289            (AddressSize::_64, AddressRegion::Table, 0, 0),
290            (AddressSize::_64, AddressRegion::Table, 1, 1),
291            (AddressSize::_64, AddressRegion::Table, 31, 0x1FF_FFFF),
292            (AddressSize::_64, AddressRegion::GlobalValue, 0, 0),
293            (AddressSize::_64, AddressRegion::GlobalValue, 1, 1),
294            (AddressSize::_64, AddressRegion::GlobalValue, 63, 0xFF_FFFF),
295        ];
296
297        for (size, region, entry, offset) in test_addresses {
298            let original = Address {
299                size,
300                region,
301                entry,
302                offset,
303            };
304
305            let dv: DataValue = original.clone().try_into().unwrap();
306            let addr = dv.try_into().unwrap();
307
308            assert_eq!(original, addr);
309        }
310    }
311}
cranelift_interpreter/address.rs

cranelift_interpreter/
address.rs
