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 
35 use crate::state::MemoryError;
36 use cranelift_codegen::data_value::DataValue;
37 use cranelift_codegen::ir::{Type, types};
38 
39 #[derive(Debug, Copy, Clone, PartialEq)]
40 pub enum AddressSize {
41     _32,
42     _64,
43 }
44 
45 impl AddressSize {
bits(&self) -> u6446     pub fn bits(&self) -> u64 {
47         match self {
48             AddressSize::_64 => 64,
49             AddressSize::_32 => 32,
50         }
51     }
52 }
53 
54 impl TryFrom<Type> for AddressSize {
55     type Error = MemoryError;
56 
try_from(ty: Type) -> Result<Self, Self::Error>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)]
68 pub enum AddressRegion {
69     Stack,
70     Function,
71     Table,
72     GlobalValue,
73 }
74 
75 impl AddressRegion {
decode(bits: u64) -> Self76     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 
encode(self) -> u6487     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)]
98 pub struct Address {
99     pub size: AddressSize,
100     pub region: AddressRegion,
101     pub entry: u64,
102     pub offset: u64,
103 }
104 
105 impl Address {
from_parts( size: AddressSize, region: AddressRegion, entry: u64, offset: u64, ) -> Result<Self, MemoryError>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 
entry_bits(size: AddressSize, region: AddressRegion) -> u64140     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 
offset_bits(size: AddressSize, region: AddressRegion) -> u64157     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 
164 impl TryFrom<Address> for DataValue {
165     type Error = MemoryError;
166 
try_from(addr: Address) -> Result<Self, Self::Error>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 
182 impl TryFrom<DataValue> for Address {
183     type Error = MemoryError;
184 
try_from(value: DataValue) -> Result<Self, Self::Error>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 
212 impl TryFrom<u64> for Address {
213     type Error = MemoryError;
214 
try_from(value: u64) -> Result<Self, Self::Error>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)]
227 pub enum AddressFunctionEntry {
228     UserFunction = 0,
229     LibCall,
230 }
231 
232 impl From<u64> for AddressFunctionEntry {
from(bits: u64) -> Self233     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)]
243 mod tests {
244     use super::*;
245 
246     #[test]
address_region_roundtrip_encode_decode()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]
address_roundtrip()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 }
312