.githooks/
compiler/
kernel/
lib/
examples/
std/
arch/
rv64/
asm/
image/
shared/
tests/
run.rad
50.3 KiB
catalog.rad
11.6 KiB
tests.rad
22.7 KiB
tests/
asm.rad
32.4 KiB
atomics.rad
5.1 KiB
decode.rad
27.1 KiB
emit.rad
34.6 KiB
encode.rad
30.9 KiB
image.rad
6.1 KiB
isel.rad
138.3 KiB
printer.rad
19.2 KiB
shared.rad
21.1 KiB
tests.rad
73.3 KiB
vector.rad
59.4 KiB
rv64.rad
22.4 KiB
bits/
char/
collections/
fs/
hash/
lang/
mem/
sys/
arch.rad
68 B
bits.rad
1.6 KiB
char.rad
1.5 KiB
collections.rad
39 B
fmt.rad
11.6 KiB
fs.rad
11.0 KiB
hash.rad
41 B
intrinsics.rad
467 B
io.rad
1.7 KiB
lang.rad
335 B
mem.rad
12.0 KiB
mem.ras
919 B
process.rad
6.2 KiB
std.manifest
4.9 KiB
std.rad
349 B
sys.rad
1.0 KiB
testing.rad
2.4 KiB
tests.rad
26.6 KiB
vec.rad
3.2 KiB
scripts/
seed/
sublime/
test/
vim/
.gitignore
333 B
.gitsigners
224 B
AGENTS.md
8.3 KiB
CONTRIBUTING
2.1 KiB
LICENSE
1.1 KiB
Makefile
2.5 KiB
README
3.4 KiB
STYLE
3.2 KiB
std.lib
2.1 KiB
std.lib.test
1.1 KiB
lib/std/arch/rv64/shared/tests/run.rad
raw
| 1 | //! Execution of generated shared code by a small interpreter. |
| 2 | //! |
| 3 | //! A check compiles one function with the shared code generator, runs its machine code on |
| 4 | //! a model of the few instructions it uses, and compares the registers and memory that the |
| 5 | //! function leaves with the semantics of the IL instruction. |
| 6 | |
| 7 | use std::arch::rv64; |
| 8 | use std::arch::rv64::atomics; |
| 9 | use std::arch::rv64::decode; |
| 10 | use std::arch::rv64::shared; |
| 11 | use std::arch::rv64::shared::tests; |
| 12 | use std::lang::gen; |
| 13 | use std::lang::gen::data; |
| 14 | use std::lang::il; |
| 15 | use std::lang::il::binary; |
| 16 | use std::mem::heap; |
| 17 | use std::testing; |
| 18 | |
| 19 | /// Storage for the IL of a check. |
| 20 | static IL: [u8; 65536] = [0; 65536]; |
| 21 | /// Layout table of a blit check, which has the copied layout only. |
| 22 | unsafe static COPIED: [il::Layout; 1] = undefined; |
| 23 | /// Storage for the instructions of a blit check. |
| 24 | static BODY: [u8; 131072] = [0; 131072]; |
| 25 | /// Persistent catalog symbols. |
| 26 | unsafe static SYMBOLS: [shared::Symbol; 8] = undefined; |
| 27 | /// Persistent exported symbols. |
| 28 | unsafe static EXPORTS: [shared::Symbol; 8] = undefined; |
| 29 | /// Data layout workspace. |
| 30 | unsafe static DATA: [data::DataSym; 8] = undefined; |
| 31 | /// Persistent initialized bytes. |
| 32 | static TEMPLATE: [u8; 64] = [0; 64]; |
| 33 | /// Persistent private data relocations. |
| 34 | unsafe static RELOCS: [shared::Relocation; 8] = undefined; |
| 35 | |
| 36 | /// Address of the modeled memory. |
| 37 | constant MEMORY_BASE: u64 = 0x1000; |
| 38 | /// Size of the modeled memory in bytes. |
| 39 | constant MEMORY_SIZE: u32 = 8192; |
| 40 | /// Modeled memory. |
| 41 | static MEMORY: [u8; 8192] = [0; 8192]; |
| 42 | /// Address of the table of package bases, which `gp` holds. |
| 43 | constant TABLE: u64 = 0x1000; |
| 44 | /// Package slot of the checked function. |
| 45 | constant SLOT: u32 = 1; |
| 46 | /// Base address of the private data of the package. It is small, so that the low 32 bits of |
| 47 | /// a data address are an index that the slice instructions accept. |
| 48 | constant PACKAGE_BASE: u64 = 0x10; |
| 49 | /// Address of the slice object that a check writes. |
| 50 | constant RESULT: u64 = 0x1040; |
| 51 | /// Address of the slice object that a check reads. |
| 52 | constant SOURCE: u64 = 0x1080; |
| 53 | /// Value that `ra` holds on entry. Jumping to it ends the run. |
| 54 | constant RETURN: u64 = 0xdead0000; |
| 55 | /// Initial stack pointer. |
| 56 | constant STACK: u64 = 0x3000; |
| 57 | /// Data pointer of the source slice and the array base of a check. |
| 58 | constant POINTER: u64 = 0x5000; |
| 59 | /// Instructions that one run may execute. |
| 60 | constant MAX_STEPS: u32 = 20000; |
| 61 | /// Size in bytes of the element layout of the checks. |
| 62 | constant ELEMENT: u64 = 8; |
| 63 | /// Name of the data symbol at the lower address. |
| 64 | constant FIRST: *[u8] = "p::first"; |
| 65 | /// Name of the data symbol at the higher address. |
| 66 | constant SECOND: *[u8] = "p::second"; |
| 67 | /// Address of the first byte of the area that a blit check copies from. |
| 68 | constant SOURCE_AREA: u64 = 0x1100; |
| 69 | /// Address of the first byte of the area that a blit check copies to. |
| 70 | constant TARGET_AREA: u64 = 0x1a00; |
| 71 | /// Bytes of guard before and after the copied object in an area. The object is aligned to |
| 72 | /// the largest unit of a copy, so the guard has that size. |
| 73 | constant GUARD: u64 = 8; |
| 74 | /// Bytes that another hart takes from a word when it wins a store-conditional. |
| 75 | constant CONTENDED: u64 = 16; |
| 76 | /// Value of the bytes that a blit check must leave alone. |
| 77 | constant UNTOUCHED: u8 = 0xaa; |
| 78 | /// Number of values that stay live across the blit of a check with spilled operands. |
| 79 | constant LIVE: u32 = 30; |
| 80 | |
| 81 | /// How a run ended. |
| 82 | union Outcome: Copy { |
| 83 | /// The function returned `value` in `a0`. |
| 84 | Returned { value: u64 }, |
| 85 | /// The function executed `ebreak`. |
| 86 | Trapped, |
| 87 | /// The function did something that the model does not support. |
| 88 | Faulted, |
| 89 | } |
| 90 | |
| 91 | /// Registers of the modeled machine. |
| 92 | record Machine { |
| 93 | /// General-purpose registers. |
| 94 | regs: [u64; 32], |
| 95 | /// Byte vector group at the minimum 64-bit VLEN, with LMUL=8. |
| 96 | vector: [u8; 64], |
| 97 | /// Number of active bytes in the vector group. |
| 98 | vl: u32, |
| 99 | /// Number of instructions executed. |
| 100 | steps: u32, |
| 101 | /// Address held by the last load-reserved, until a store-conditional or a trap clears it. |
| 102 | reservation: ?u64, |
| 103 | /// Store-conditionals that fail before one can succeed. Each failure models another hart |
| 104 | /// taking [`CONTENDED`] bytes from the word, which changes its value. |
| 105 | contended: u32, |
| 106 | } |
| 107 | |
| 108 | /// Read a register. |
| 109 | fn read(m: &Machine, r: gen::Reg) -> u64 { |
| 110 | return m.regs[*r as u32]; |
| 111 | } |
| 112 | |
| 113 | /// Write a register. `zero` ignores writes. |
| 114 | fn write(m: &mut Machine, r: gen::Reg, value: u64) { |
| 115 | if *r <> 0 { |
| 116 | set m.regs[*r as u32] = value; |
| 117 | } |
| 118 | } |
| 119 | |
| 120 | /// Whether an access of `width` bytes at `address` is inside the modeled memory and aligned to |
| 121 | /// its width. |
| 122 | fn accessible(address: u64, width: u32) -> bool { |
| 123 | return address >= MEMORY_BASE |
| 124 | and address - MEMORY_BASE + width as u64 <= MEMORY_SIZE as u64 |
| 125 | and address % width as u64 == 0; |
| 126 | } |
| 127 | |
| 128 | /// Load `width` bytes at `address`, or `nil` outside the modeled memory or when misaligned. |
| 129 | unsafe fn load(address: u64, width: u32) -> ?u64 { |
| 130 | if not accessible(address, width) { |
| 131 | return nil; |
| 132 | } |
| 133 | let offset = (address - MEMORY_BASE) as u32; |
| 134 | let mut value: u64 = 0; |
| 135 | for i in 0 .. width { |
| 136 | set value |= MEMORY[offset + i] as u64 << (i as u64 * 8); |
| 137 | } |
| 138 | return value; |
| 139 | } |
| 140 | |
| 141 | /// Store the low `width` bytes of `value` at `address`. Returns false outside the memory or |
| 142 | /// when misaligned. |
| 143 | unsafe fn store(address: u64, width: u32, value: u64) -> bool { |
| 144 | if not accessible(address, width) { |
| 145 | return false; |
| 146 | } |
| 147 | let offset = (address - MEMORY_BASE) as u32; |
| 148 | for i in 0 .. width { |
| 149 | set MEMORY[offset + i] = (value >> (i as u64 * 8)) as u8; |
| 150 | } |
| 151 | return true; |
| 152 | } |
| 153 | |
| 154 | /// Sign-extend a 32-bit value to 64 bits. |
| 155 | fn sext32(value: u64) -> u64 { |
| 156 | return value as u32 as i32 as i64 as u64; |
| 157 | } |
| 158 | |
| 159 | /// Sign-extend a 16-bit value to 64 bits. |
| 160 | fn sext16(value: u64) -> u64 { |
| 161 | return value as u16 as i16 as i64 as u64; |
| 162 | } |
| 163 | |
| 164 | /// Sign-extend an 8-bit value to 64 bits. |
| 165 | fn sext8(value: u64) -> u64 { |
| 166 | return value as u8 as i8 as i64 as u64; |
| 167 | } |
| 168 | |
| 169 | /// Run `code` from its first instruction until it returns, traps or leaves the model. |
| 170 | unsafe fn run(code: *[u32], m: &mut Machine) -> Outcome { |
| 171 | let mut pc: u32 = 0; |
| 172 | for _ in 0 .. MAX_STEPS { |
| 173 | if pc >= code.len { |
| 174 | return Outcome::Faulted; |
| 175 | } |
| 176 | set m.steps += 1; |
| 177 | let mut next = pc + 1; |
| 178 | match decode::decode(code[pc]) { |
| 179 | case decode::Instr::Vector { bits } => { |
| 180 | if (bits & 0xfff0707f) == 0x0c307057 { |
| 181 | let count = read(m, rv64::reg(decode::rs1(bits))); |
| 182 | let vl = (count if count < 64 else 64) as u32; |
| 183 | set m.vl = vl; |
| 184 | write(m, rv64::reg(decode::rd(bits)), vl as u64); |
| 185 | } else if bits == 0x5e003457 { |
| 186 | for i in 0 .. m.vl { |
| 187 | set m.vector[i] = 0; |
| 188 | } |
| 189 | } else if (bits & 0xfff07fff) == 0x02000407 { |
| 190 | let address = read(m, rv64::reg(decode::rs1(bits))); |
| 191 | for i in 0 .. m.vl { |
| 192 | let value = load(address + i as u64, 1) else { |
| 193 | return Outcome::Faulted; |
| 194 | }; |
| 195 | set m.vector[i] = value as u8; |
| 196 | } |
| 197 | } else if (bits & 0xfff07fff) == 0x02000427 { |
| 198 | let address = read(m, rv64::reg(decode::rs1(bits))); |
| 199 | for i in 0 .. m.vl { |
| 200 | if not store(address + i as u64, 1, m.vector[i] as u64) { |
| 201 | return Outcome::Faulted; |
| 202 | } |
| 203 | } |
| 204 | } else { |
| 205 | return Outcome::Faulted; |
| 206 | } |
| 207 | } |
| 208 | case decode::Instr::AddUw { rd, rs1, rs2 } => { |
| 209 | write(m, rd, read(m, rs1) as u32 as u64 + read(m, rs2)); |
| 210 | } |
| 211 | case decode::Instr::Sh1add { rd, rs1, rs2 } => { |
| 212 | write(m, rd, (read(m, rs1) << 1) + read(m, rs2)); |
| 213 | } |
| 214 | case decode::Instr::Sh2add { rd, rs1, rs2 } => { |
| 215 | write(m, rd, (read(m, rs1) << 2) + read(m, rs2)); |
| 216 | } |
| 217 | case decode::Instr::Sh3add { rd, rs1, rs2 } => { |
| 218 | write(m, rd, (read(m, rs1) << 3) + read(m, rs2)); |
| 219 | } |
| 220 | case decode::Instr::SextB { rd, rs1 } => { |
| 221 | write(m, rd, sext8(read(m, rs1))); |
| 222 | } |
| 223 | case decode::Instr::SextH { rd, rs1 } => { |
| 224 | write(m, rd, sext16(read(m, rs1))); |
| 225 | } |
| 226 | case decode::Instr::ZextH { rd, rs1 } => { |
| 227 | write(m, rd, read(m, rs1) as u16 as u64); |
| 228 | } |
| 229 | case decode::Instr::Addi { rd, rs1, imm } => { |
| 230 | write(m, rd, read(m, rs1) + imm as i64 as u64); |
| 231 | } |
| 232 | case decode::Instr::Addiw { rd, rs1, imm } => { |
| 233 | write(m, rd, sext32(read(m, rs1) + imm as i64 as u64)); |
| 234 | } |
| 235 | case decode::Instr::Andi { rd, rs1, imm } => { |
| 236 | write(m, rd, read(m, rs1) & imm as i64 as u64); |
| 237 | } |
| 238 | case decode::Instr::Add { rd, rs1, rs2 } => { |
| 239 | write(m, rd, read(m, rs1) + read(m, rs2)); |
| 240 | } |
| 241 | case decode::Instr::Sub { rd, rs1, rs2 } => { |
| 242 | write(m, rd, read(m, rs1) - read(m, rs2)); |
| 243 | } |
| 244 | case decode::Instr::Mul { rd, rs1, rs2 } => { |
| 245 | write(m, rd, read(m, rs1) * read(m, rs2)); |
| 246 | } |
| 247 | case decode::Instr::Jal { rd, imm } => { |
| 248 | set next = (pc as i32 + imm / 4) as u32; |
| 249 | } |
| 250 | case decode::Instr::Slli { rd, rs1, shamt } => { |
| 251 | write(m, rd, read(m, rs1) << shamt as u64); |
| 252 | } |
| 253 | case decode::Instr::Srli { rd, rs1, shamt } => { |
| 254 | write(m, rd, read(m, rs1) >> shamt as u64); |
| 255 | } |
| 256 | case decode::Instr::Lui { rd, imm } => { |
| 257 | write(m, rd, sext32(imm as i64 as u64 << 12)); |
| 258 | } |
| 259 | case decode::Instr::Ld { rd, rs1, imm } => { |
| 260 | let value = load(read(m, rs1) + imm as i64 as u64, 8) else { |
| 261 | return Outcome::Faulted; |
| 262 | }; |
| 263 | write(m, rd, value); |
| 264 | } |
| 265 | case decode::Instr::Lwu { rd, rs1, imm } => { |
| 266 | let value = load(read(m, rs1) + imm as i64 as u64, 4) else { |
| 267 | return Outcome::Faulted; |
| 268 | }; |
| 269 | write(m, rd, value); |
| 270 | } |
| 271 | case decode::Instr::Lw { rd, rs1, imm } => { |
| 272 | let value = load(read(m, rs1) + imm as i64 as u64, 4) else { |
| 273 | return Outcome::Faulted; |
| 274 | }; |
| 275 | write(m, rd, sext32(value)); |
| 276 | } |
| 277 | case decode::Instr::Lhu { rd, rs1, imm } => { |
| 278 | let value = load(read(m, rs1) + imm as i64 as u64, 2) else { |
| 279 | return Outcome::Faulted; |
| 280 | }; |
| 281 | write(m, rd, value); |
| 282 | } |
| 283 | case decode::Instr::Lh { rd, rs1, imm } => { |
| 284 | let value = load(read(m, rs1) + imm as i64 as u64, 2) else { |
| 285 | return Outcome::Faulted; |
| 286 | }; |
| 287 | write(m, rd, sext16(value)); |
| 288 | } |
| 289 | case decode::Instr::Lbu { rd, rs1, imm } => { |
| 290 | let value = load(read(m, rs1) + imm as i64 as u64, 1) else { |
| 291 | return Outcome::Faulted; |
| 292 | }; |
| 293 | write(m, rd, value); |
| 294 | } |
| 295 | case decode::Instr::Lb { rd, rs1, imm } => { |
| 296 | let value = load(read(m, rs1) + imm as i64 as u64, 1) else { |
| 297 | return Outcome::Faulted; |
| 298 | }; |
| 299 | write(m, rd, sext8(value)); |
| 300 | } |
| 301 | case decode::Instr::Sh { rs2, rs1, imm } => { |
| 302 | if not store(read(m, rs1) + imm as i64 as u64, 2, read(m, rs2)) { |
| 303 | return Outcome::Faulted; |
| 304 | } |
| 305 | } |
| 306 | case decode::Instr::Sb { rs2, rs1, imm } => { |
| 307 | if not store(read(m, rs1) + imm as i64 as u64, 1, read(m, rs2)) { |
| 308 | return Outcome::Faulted; |
| 309 | } |
| 310 | } |
| 311 | case decode::Instr::Sd { rs2, rs1, imm } => { |
| 312 | if not store(read(m, rs1) + imm as i64 as u64, 8, read(m, rs2)) { |
| 313 | return Outcome::Faulted; |
| 314 | } |
| 315 | } |
| 316 | case decode::Instr::Sw { rs2, rs1, imm } => { |
| 317 | if not store(read(m, rs1) + imm as i64 as u64, 4, read(m, rs2)) { |
| 318 | return Outcome::Faulted; |
| 319 | } |
| 320 | } |
| 321 | case decode::Instr::Beq { rs1, rs2, imm } => { |
| 322 | if read(m, rs1) == read(m, rs2) { |
| 323 | set next = (pc as i32 + imm / 4) as u32; |
| 324 | } |
| 325 | } |
| 326 | case decode::Instr::Bne { rs1, rs2, imm } => { |
| 327 | if read(m, rs1) <> read(m, rs2) { |
| 328 | set next = (pc as i32 + imm / 4) as u32; |
| 329 | } |
| 330 | } |
| 331 | case decode::Instr::Bltu { rs1, rs2, imm } => { |
| 332 | if read(m, rs1) < read(m, rs2) { |
| 333 | set next = (pc as i32 + imm / 4) as u32; |
| 334 | } |
| 335 | } |
| 336 | case decode::Instr::Bgeu { rs1, rs2, imm } => { |
| 337 | if read(m, rs1) >= read(m, rs2) { |
| 338 | set next = (pc as i32 + imm / 4) as u32; |
| 339 | } |
| 340 | } |
| 341 | case decode::Instr::Jalr { rd, rs1, imm } => { |
| 342 | if read(m, rs1) + imm as i64 as u64 <> RETURN { |
| 343 | return Outcome::Faulted; |
| 344 | } |
| 345 | return Outcome::Returned { value: read(m, rv64::A0) }; |
| 346 | } |
| 347 | case decode::Instr::Ebreak => { |
| 348 | return Outcome::Trapped; |
| 349 | } |
| 350 | else => { |
| 351 | // Only the doubleword forms of load-reserved and store-conditional. |
| 352 | let atomic = atomics::decode(code[pc]) else { |
| 353 | return Outcome::Faulted; |
| 354 | }; |
| 355 | let address = read(m, atomic.rs1); |
| 356 | if atomic.format.width <> 3 or not accessible(address, 8) { |
| 357 | return Outcome::Faulted; |
| 358 | } |
| 359 | if atomic.format.operation == 2 { |
| 360 | let word = load(address, 8) else panic "run: outside memory"; |
| 361 | write(m, atomic.rd, word); |
| 362 | set m.reservation = address; |
| 363 | } else if atomic.format.operation == 3 { |
| 364 | let held = m.reservation == address; |
| 365 | set m.reservation = nil; |
| 366 | if held and m.contended == 0 { |
| 367 | assert store(address, 8, read(m, atomic.rs2)); |
| 368 | write(m, atomic.rd, 0); |
| 369 | } else { |
| 370 | if held { |
| 371 | // Another hart won: its allocation moves the word. |
| 372 | set m.contended -= 1; |
| 373 | let current = load(address, 8) else panic "run: outside memory"; |
| 374 | assert store(address, 8, current + CONTENDED); |
| 375 | } |
| 376 | write(m, atomic.rd, 1); |
| 377 | } |
| 378 | } else { |
| 379 | return Outcome::Faulted; |
| 380 | } |
| 381 | } |
| 382 | } |
| 383 | set pc = next; |
| 384 | } |
| 385 | return Outcome::Faulted; |
| 386 | } |
| 387 | |
| 388 | /// Compile a function of `paramCount` data parameters, one instruction, and a return of |
| 389 | /// `result`, into a package with two data symbols. |
| 390 | unsafe fn compile(instr: il::Instr, paramCount: u32, result: ?il::Val) -> shared::Package |
| 391 | throws (shared::Error) |
| 392 | { |
| 393 | return try compileBody(&[instr, il::Instr::Ret { val: result }], paramCount, &[ |
| 394 | il::Layout { size: ELEMENT as u32, alignment: 8, slots: &[], regions: 0 } |
| 395 | ], &[]); |
| 396 | } |
| 397 | |
| 398 | /// Compile a function of `paramCount` data parameters with the instructions `body`, which end |
| 399 | /// with a return, into a package with two data symbols and the layout table `layouts`. The |
| 400 | /// argument ranges of the instructions select from `vals`. |
| 401 | unsafe fn compileBody( |
| 402 | body: &[il::Instr], paramCount: u32, layouts: *[il::Layout], vals: &[il::Val] |
| 403 | ) -> shared::Package throws (shared::Error) { |
| 404 | let ilArena = heap::over(&mut IL[..]); |
| 405 | let mut params: *mut [il::Param] = &mut []; |
| 406 | for n in 0 .. paramCount { |
| 407 | try! params.append(dataParam(n), ilArena); |
| 408 | } |
| 409 | let mut instrs: *mut [il::Instr] = &mut []; |
| 410 | try! instrs.extend(body, ilArena); |
| 411 | let mut pool: *mut [il::Val] = &mut []; |
| 412 | try! pool.extend(vals, ilArena); |
| 413 | let mut blocks: *mut [il::Block] = &mut []; |
| 414 | try! blocks.append( |
| 415 | il::Block { |
| 416 | label: il::BlockLabel { base: "b", suffix: nil }, |
| 417 | params: &[], |
| 418 | instrs: &instrs[..], |
| 419 | locs: &[], |
| 420 | preds: &[], |
| 421 | loopDepth: 0, |
| 422 | }, |
| 423 | ilArena |
| 424 | ); |
| 425 | let mut funcs: *mut [il::Fn] = &mut []; |
| 426 | try! funcs.append( |
| 427 | il::Fn { |
| 428 | name: "p::f", |
| 429 | params: ¶ms[..], |
| 430 | returnType: il::ValType::Data(il::Type::W64), |
| 431 | isExtern: false, |
| 432 | isLeaf: false, |
| 433 | blocks: &blocks[..], |
| 434 | vals: &pool[..], |
| 435 | cases: &[], |
| 436 | borrows: &[], |
| 437 | }, |
| 438 | ilArena |
| 439 | ); |
| 440 | let mut fns: *mut [*il::Fn] = &mut []; |
| 441 | try! fns.append(&funcs[0], ilArena); |
| 442 | let input = binary::Package { |
| 443 | version: nil, |
| 444 | symbols: &[], |
| 445 | name: "p", |
| 446 | dependencies: &[], |
| 447 | exports: &[ |
| 448 | binary::Export { |
| 449 | name: "p::f", |
| 450 | kind: binary::ExportKind::Function(0), |
| 451 | startable: false, |
| 452 | }, |
| 453 | binary::Export { |
| 454 | name: FIRST, |
| 455 | kind: binary::ExportKind::Data(0), |
| 456 | startable: false, |
| 457 | }, |
| 458 | binary::Export { |
| 459 | name: SECOND, |
| 460 | kind: binary::ExportKind::Data(1), |
| 461 | startable: false, |
| 462 | }, |
| 463 | ], |
| 464 | entry: nil, |
| 465 | program: il::Program { |
| 466 | data: &[ |
| 467 | il::Data { |
| 468 | name: FIRST, |
| 469 | size: 8, |
| 470 | alignment: 8, |
| 471 | layout: 0, |
| 472 | readOnly: false, |
| 473 | heap: nil, |
| 474 | isZeroInit: true, |
| 475 | values: &[], |
| 476 | }, |
| 477 | il::Data { |
| 478 | name: SECOND, |
| 479 | size: 8, |
| 480 | alignment: 8, |
| 481 | layout: 0, |
| 482 | readOnly: false, |
| 483 | heap: nil, |
| 484 | isZeroInit: true, |
| 485 | values: &[], |
| 486 | }, |
| 487 | ], |
| 488 | fns: &fns[..], |
| 489 | layouts, |
| 490 | signatures: &[], |
| 491 | traits: &[], |
| 492 | }, |
| 493 | links: binary::EMPTY_LINKS, |
| 494 | }; |
| 495 | let arena = heap::over(&mut tests::ARENA[..]); |
| 496 | let scratch = heap::over(&mut tests::SCRATCH[..]); |
| 497 | return try shared::compile( |
| 498 | &input, |
| 499 | SLOT, |
| 500 | 0x180000000, |
| 501 | &[], |
| 502 | shared::Storage { |
| 503 | data: &mut DATA[..], |
| 504 | symbols: &mut SYMBOLS[..], |
| 505 | exports: &mut EXPORTS[..], |
| 506 | template: &mut TEMPLATE[..], |
| 507 | relocations: &mut RELOCS[..], |
| 508 | stack: rv64::StackCheck::Off, |
| 509 | }, |
| 510 | arena, |
| 511 | scratch |
| 512 | ); |
| 513 | } |
| 514 | |
| 515 | /// Address of a data symbol of the package once the package is instantiated at the base. |
| 516 | fn address(package: &shared::Package, name: *[u8]) -> u64 { |
| 517 | match shared::lookup(package.exports, name) { |
| 518 | case shared::Target::Data(location) => return PACKAGE_BASE + location.offset as u64, |
| 519 | else => panic "address: not a data symbol", |
| 520 | } |
| 521 | } |
| 522 | |
| 523 | /// The result of running a function that writes a slice object. |
| 524 | record Built { |
| 525 | /// How the run ended. |
| 526 | outcome: Outcome, |
| 527 | /// Data pointer of the slice object. |
| 528 | ptr: u64, |
| 529 | /// Length of the slice object. |
| 530 | len: u64, |
| 531 | /// Capacity of the slice object. |
| 532 | cap: u64, |
| 533 | } |
| 534 | |
| 535 | /// A data parameter of a function. |
| 536 | fn dataParam(n: u32) -> il::Param { |
| 537 | return il::Param { value: il::Reg { n }, type: il::ValType::Data(il::Type::W64) }; |
| 538 | } |
| 539 | |
| 540 | /// Reset the modeled memory, and set up the registers for a call with the arguments. |
| 541 | unsafe fn boot(args: &[u64]) -> Machine { |
| 542 | for i in 0 .. MEMORY_SIZE { |
| 543 | set MEMORY[i] = 0; |
| 544 | } |
| 545 | assert store(TABLE + SLOT as u64 * 8, 8, PACKAGE_BASE); |
| 546 | let mut m = Machine { |
| 547 | regs: [0; 32], vector: [0; 64], vl: 0, steps: 0, reservation: nil, contended: 0 |
| 548 | }; |
| 549 | write(&mut m, rv64::GP, TABLE); |
| 550 | write(&mut m, rv64::SP, STACK); |
| 551 | write(&mut m, rv64::RA, RETURN); |
| 552 | for arg, i in args { |
| 553 | write(&mut m, rv64::ARG_REGS[i], arg); |
| 554 | } |
| 555 | return m; |
| 556 | } |
| 557 | |
| 558 | /// The slice object at [`RESULT`] after a run. |
| 559 | unsafe fn built(outcome: Outcome) -> Built { |
| 560 | let ptr = load(RESULT, 8) else panic "built: result outside memory"; |
| 561 | let len = load(RESULT + 8, 4) else panic "built: result outside memory"; |
| 562 | let cap = load(RESULT + 12, 4) else panic "built: result outside memory"; |
| 563 | return Built { outcome, ptr, len, cap }; |
| 564 | } |
| 565 | |
| 566 | /// Run `slice.new` with the bounds on an array of `count` elements at [`POINTER`]. |
| 567 | unsafe fn sliceNew(first: il::Val, end: il::Val, count: u32) -> Built |
| 568 | throws (testing::TestError) |
| 569 | { |
| 570 | let package = try compile( |
| 571 | il::Instr::SliceNew { |
| 572 | dst: il::Reg { n: 0 }, |
| 573 | base: il::Val::Reg(il::Reg { n: 1 }), |
| 574 | layout: 0, |
| 575 | count, |
| 576 | start: first, |
| 577 | end, |
| 578 | }, |
| 579 | 2, |
| 580 | nil |
| 581 | ) catch { |
| 582 | throw testing::TestError::Failed; |
| 583 | }; |
| 584 | let mut m = boot(&[RESULT, POINTER]); |
| 585 | return built(run(package.code, &mut m)); |
| 586 | } |
| 587 | |
| 588 | /// Run `slice.sub` with the bounds on a source slice at [`POINTER`] of `len` elements and |
| 589 | /// ten more of capacity. |
| 590 | unsafe fn sliceSub(first: il::Val, end: il::Val, len: u32) -> Built |
| 591 | throws (testing::TestError) |
| 592 | { |
| 593 | let package = try compile( |
| 594 | il::Instr::SliceSub { |
| 595 | dst: il::Reg { n: 0 }, src: il::Reg { n: 1 }, layout: 0, start: first, end |
| 596 | }, |
| 597 | 2, |
| 598 | nil |
| 599 | ) catch { |
| 600 | throw testing::TestError::Failed; |
| 601 | }; |
| 602 | let mut m = boot(&[RESULT, SOURCE]); |
| 603 | assert store(SOURCE, 8, POINTER); |
| 604 | assert store(SOURCE + 8, 4, len as u64); |
| 605 | assert store(SOURCE + 12, 4, len as u64 + 10); |
| 606 | return built(run(package.code, &mut m)); |
| 607 | } |
| 608 | |
| 609 | /// Run `elem` of an array of `count` elements at [`POINTER`]. With `inRegister`, the index is |
| 610 | /// passed in a register instead of as an immediate. |
| 611 | unsafe fn elem(index: i64, count: u32, inRegister: bool) -> Outcome |
| 612 | throws (testing::TestError) |
| 613 | { |
| 614 | let mut operand = il::Val::Imm(index); |
| 615 | if inRegister { |
| 616 | set operand = il::Val::Reg(il::Reg { n: 1 }); |
| 617 | } |
| 618 | let package = try compile(il::Instr::Elem { |
| 619 | dst: il::Reg { n: 2 }, base: il::Reg { n: 0 }, index: operand, layout: 0, count |
| 620 | }, 2, il::Val::Reg( |
| 621 | il::Reg { n: 2 } |
| 622 | )) catch { |
| 623 | throw testing::TestError::Failed; |
| 624 | }; |
| 625 | let mut m = boot(&[POINTER, index as u64]); |
| 626 | return run(package.code, &mut m); |
| 627 | } |
| 628 | |
| 629 | /// Whether a run trapped. |
| 630 | fn trapped(outcome: Outcome) -> bool { |
| 631 | match outcome { |
| 632 | case Outcome::Trapped => return true, |
| 633 | else => return false, |
| 634 | } |
| 635 | } |
| 636 | |
| 637 | /// Whether a run returned `value`. |
| 638 | fn returned(outcome: Outcome, value: u64) -> bool { |
| 639 | match outcome { |
| 640 | case Outcome::Returned { value: v } => return v == value, |
| 641 | else => return false, |
| 642 | } |
| 643 | } |
| 644 | |
| 645 | /// Whether a run returned, so that its slice object is complete. |
| 646 | fn finished(outcome: Outcome) -> bool { |
| 647 | match outcome { |
| 648 | case Outcome::Returned { .. } => return true, |
| 649 | else => return false, |
| 650 | } |
| 651 | } |
| 652 | |
| 653 | /// Check that a run built a slice that starts at element `first` of the array at [`POINTER`]. |
| 654 | fn expectBuilt(b: Built, first: u64, len: u64, cap: u64) throws (testing::TestError) { |
| 655 | try testing::expect(finished(b.outcome)); |
| 656 | try testing::expect(b.ptr == POINTER + first * ELEMENT and b.len == len and b.cap == cap); |
| 657 | } |
| 658 | |
| 659 | /// Check that a run of an instruction with a violated bound trapped. |
| 660 | fn expectTrap(b: Built) throws (testing::TestError) { |
| 661 | try testing::expect(trapped(b.outcome)); |
| 662 | } |
| 663 | |
| 664 | /// Addresses of the two data symbols, which are indexes that the slice instructions accept. |
| 665 | record Addresses { |
| 666 | /// Address of [`FIRST`]. |
| 667 | first: u64, |
| 668 | /// Address of [`SECOND`]. |
| 669 | second: u64, |
| 670 | } |
| 671 | |
| 672 | /// Compile a function without code to find the addresses of the data symbols. |
| 673 | unsafe fn addresses() -> Addresses throws (testing::TestError) { |
| 674 | let package = try compile(il::Instr::Ret { val: nil }, 0, nil) catch { |
| 675 | throw testing::TestError::Failed; |
| 676 | }; |
| 677 | return Addresses { first: address(&package, FIRST), second: address(&package, SECOND) }; |
| 678 | } |
| 679 | |
| 680 | /// The bounds of a slice are 32-bit values, and a data symbol is accepted as one: its low 32 |
| 681 | /// bits count. Every pair of operands builds the slice, or traps when a bound is violated. |
| 682 | @test unsafe fn sliceNewBounds() throws (testing::TestError) { |
| 683 | let at = try addresses(); |
| 684 | let one = il::Val::DataSym(FIRST); |
| 685 | let two = il::Val::DataSym(SECOND); |
| 686 | try expectBuilt(try sliceNew(one, two, 64), at.first, at.second - at.first, 64 - at.first); |
| 687 | try expectBuilt(try sliceNew(il::Val::Imm(2), two, 64), 2, at.second - 2, 62); |
| 688 | try expectBuilt( |
| 689 | try sliceNew(one, il::Val::Imm(40), 64), at.first, 40 - at.first, 64 - at.first |
| 690 | ); |
| 691 | try expectBuilt(try sliceNew(il::Val::Imm(0), two, 64), 0, at.second, 64); |
| 692 | try expectBuilt(try sliceNew(two, two, 64), at.second, 0, 64 - at.second); |
| 693 | try expectTrap(try sliceNew(one, two, 20)); |
| 694 | try expectTrap(try sliceNew(two, one, 64)); |
| 695 | try expectTrap(try sliceNew(one, il::Val::Imm(8), 64)); |
| 696 | } |
| 697 | |
| 698 | /// A data symbol is accepted as a bound of `slice.sub`, as of `slice.new`. |
| 699 | @test unsafe fn sliceSubBounds() throws (testing::TestError) { |
| 700 | let at = try addresses(); |
| 701 | let one = il::Val::DataSym(FIRST); |
| 702 | let two = il::Val::DataSym(SECOND); |
| 703 | try expectBuilt(try sliceSub(one, two, 40), at.first, at.second - at.first, 50 - at.first); |
| 704 | try expectBuilt(try sliceSub(il::Val::Imm(2), two, 40), 2, at.second - 2, 48); |
| 705 | try expectBuilt( |
| 706 | try sliceSub(one, il::Val::Imm(40), 40), at.first, 40 - at.first, 50 - at.first |
| 707 | ); |
| 708 | try expectBuilt(try sliceSub(il::Val::Imm(0), two, 40), 0, at.second, 50); |
| 709 | try expectBuilt(try sliceSub(two, two, 40), at.second, 0, 50 - at.second); |
| 710 | try expectTrap(try sliceSub(one, two, 20)); |
| 711 | try expectTrap(try sliceSub(two, one, 40)); |
| 712 | try expectTrap(try sliceSub(one, il::Val::Imm(8), 40)); |
| 713 | } |
| 714 | |
| 715 | /// Write a slice object at `address`. |
| 716 | unsafe fn putSlice(address: u64, ptr: u64, len: u64, cap: u64) { |
| 717 | assert store(address, 8, ptr); |
| 718 | assert store(address + 8, 4, len); |
| 719 | assert store(address + 12, 4, cap); |
| 720 | } |
| 721 | |
| 722 | /// Run `slice.len` on the object at [`RESULT`], which holds three elements and has room for ten. |
| 723 | unsafe fn sliceLen(length: i64, inRegister: bool) -> Built throws (testing::TestError) { |
| 724 | let mut operand = il::Val::Imm(length); |
| 725 | if inRegister { |
| 726 | set operand = il::Val::Reg(il::Reg { n: 1 }); |
| 727 | } |
| 728 | let package = try compile( |
| 729 | il::Instr::SliceLen { dst: il::Reg { n: 0 }, layout: 0, length: operand }, 2, nil |
| 730 | ) catch { |
| 731 | throw testing::TestError::Failed; |
| 732 | }; |
| 733 | let mut m = boot(&[RESULT, length as u64]); |
| 734 | putSlice(RESULT, POINTER, 3, 10); |
| 735 | return built(run(package.code, &mut m)); |
| 736 | } |
| 737 | |
| 738 | /// Run `slice.copy` of `from` elements into a slice of `to` elements. The elements of the |
| 739 | /// source are `1 ..= from`, and the bytes around the target area stay at [`UNTOUCHED`]. |
| 740 | unsafe fn sliceCopy(from: u64, to: u64) -> Outcome throws (testing::TestError) { |
| 741 | let package = try compile( |
| 742 | il::Instr::SliceCopy { dst: il::Reg { n: 0 }, src: il::Reg { n: 1 }, layout: 0 }, 2, nil |
| 743 | ) catch { |
| 744 | throw testing::TestError::Failed; |
| 745 | }; |
| 746 | let mut m = boot(&[RESULT, SOURCE]); |
| 747 | putSlice(SOURCE, SOURCE_AREA, from, from); |
| 748 | putSlice(RESULT, TARGET_AREA, to, to); |
| 749 | for i in 0 .. from { |
| 750 | assert store(SOURCE_AREA + i * ELEMENT, 8, i + 1); |
| 751 | } |
| 752 | for i in 0 .. 8 { |
| 753 | assert store(TARGET_AREA + i * ELEMENT, 8, 0xaaaaaaaaaaaaaaaa); |
| 754 | } |
| 755 | return run(package.code, &mut m); |
| 756 | } |
| 757 | |
| 758 | /// A length up to the capacity is accepted, and a larger one traps without a change. |
| 759 | @test unsafe fn sliceLenBounds() throws (testing::TestError) { |
| 760 | for form in 0 .. 2 { |
| 761 | let reg = form == 1; |
| 762 | let lengths: [u32; 3] = [0, 3, 10]; |
| 763 | for length in lengths { |
| 764 | let b = try sliceLen(length as i64, reg); |
| 765 | try testing::expect(finished(b.outcome)); |
| 766 | try testing::expect(b.ptr == POINTER and b.len == length as u64 and b.cap == 10); |
| 767 | } |
| 768 | let over = try sliceLen(11, reg); |
| 769 | try testing::expect(trapped(over.outcome) and over.len == 3); |
| 770 | try expectTrap(try sliceLen(0x100000000 + 11, reg)); |
| 771 | try expectTrap(try sliceLen(-1, reg)); |
| 772 | } |
| 773 | } |
| 774 | |
| 775 | /// A copy moves exactly the elements of the source, and traps when they do not fit. |
| 776 | @test unsafe fn sliceCopyBounds() throws (testing::TestError) { |
| 777 | let counts: [u64; 4] = [0, 1, 2, 5]; |
| 778 | for n in counts { |
| 779 | let outcome = try sliceCopy(n, 6); |
| 780 | try testing::expect(finished(outcome)); |
| 781 | for i in 0 .. 8 { |
| 782 | let value = load(TARGET_AREA + i * ELEMENT, 8) else panic "copy: outside memory"; |
| 783 | let want: u64 = i + 1 if i < n else 0xaaaaaaaaaaaaaaaa; |
| 784 | try testing::expect(value == want); |
| 785 | } |
| 786 | } |
| 787 | try testing::expect(trapped(try sliceCopy(7, 6))); |
| 788 | let tight = try sliceCopy(6, 6); |
| 789 | try testing::expect(finished(tight)); |
| 790 | } |
| 791 | |
| 792 | /// Address of the header of the heap of a growth check. |
| 793 | constant HEAP: u64 = 0x2000; |
| 794 | /// Address of the pool of the heap of a growth check, which is aligned to sixteen bytes. |
| 795 | constant POOL: u64 = 0x2020; |
| 796 | /// Address of the elements that a growth check starts with. |
| 797 | constant OLD_AREA: u64 = 0x1400; |
| 798 | |
| 799 | /// What `slice.grow` left behind. |
| 800 | record Grown { |
| 801 | /// How the run ended. |
| 802 | outcome: Outcome, |
| 803 | /// Address of the data of the slice. |
| 804 | ptr: u64, |
| 805 | /// Length of the slice. |
| 806 | len: u64, |
| 807 | /// Capacity of the slice. |
| 808 | cap: u64, |
| 809 | /// Bytes that the heap has handed out. |
| 810 | used: u64, |
| 811 | /// Instructions that the run executed. |
| 812 | steps: u32, |
| 813 | } |
| 814 | |
| 815 | /// Layouts of the growth checks: eight bytes aligned to eight, twelve bytes aligned to four, |
| 816 | /// three bytes without alignment, and no bytes aligned to eight. |
| 817 | unsafe fn growLayouts() -> *[il::Layout] { |
| 818 | return &[ |
| 819 | il::Layout { size: 8, alignment: 8, slots: &[], regions: 0 }, |
| 820 | il::Layout { size: 12, alignment: 4, slots: &[], regions: 0 }, |
| 821 | il::Layout { size: 3, alignment: 1, slots: &[], regions: 0 }, |
| 822 | il::Layout { size: 0, alignment: 8, slots: &[], regions: 0 }, |
| 823 | ]; |
| 824 | } |
| 825 | |
| 826 | /// Run `slice.grow` of the slice with `len` elements of layout `layout` and room for `cap`, to |
| 827 | /// room for `capacity`, from a heap that has handed out `used` of `size` bytes. The old |
| 828 | /// elements hold the bytes of `pattern`. The heap is null when `heap` is zero. The result of |
| 829 | /// the check is the flag that the instruction defines. |
| 830 | unsafe fn sliceGrow( |
| 831 | layout: u32, len: u64, cap: u64, capacity: u64, used: u64, size: u64, heap: u64 |
| 832 | ) -> Grown throws (testing::TestError) { |
| 833 | return try growContended(layout, len, cap, capacity, used, size, heap, 0); |
| 834 | } |
| 835 | |
| 836 | /// Like [`sliceGrow`], with `contended` store-conditionals lost to another hart first. |
| 837 | unsafe fn growContended( |
| 838 | layout: u32, len: u64, cap: u64, capacity: u64, used: u64, size: u64, heap: u64, contended: u32 |
| 839 | ) -> Grown throws (testing::TestError) { |
| 840 | let package = try compileBody( |
| 841 | &[ |
| 842 | il::Instr::SliceGrow { |
| 843 | ok: il::Reg { n: 3 }, |
| 844 | slice: il::Reg { n: 0 }, |
| 845 | heap: il::Val::Reg(il::Reg { n: 1 }), |
| 846 | layout, |
| 847 | capacity: il::Val::Reg(il::Reg { n: 2 }), |
| 848 | }, |
| 849 | il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 3 }) }, |
| 850 | ], |
| 851 | 3, |
| 852 | growLayouts(), |
| 853 | &[] |
| 854 | ) catch { |
| 855 | throw testing::TestError::Failed; |
| 856 | }; |
| 857 | let mut m = boot(&[RESULT, heap, capacity]); |
| 858 | set m.contended = contended; |
| 859 | putSlice(RESULT, OLD_AREA, len, cap); |
| 860 | assert store(HEAP, 8, used); |
| 861 | assert store(HEAP + 8, 8, size); |
| 862 | assert store(HEAP + 16, 8, POOL); |
| 863 | let bytes = growLayouts()[layout].size as u64; |
| 864 | for i in 0 .. len * bytes { |
| 865 | assert store(OLD_AREA + i, 1, pattern(i) as u64); |
| 866 | } |
| 867 | for i in 0 .. 512 { |
| 868 | assert store(POOL + i, 1, 0xaa); |
| 869 | } |
| 870 | let outcome = run(package.code, &mut m); |
| 871 | let ptr = load(RESULT, 8) else panic "grow: outside memory"; |
| 872 | let len = load(RESULT + 8, 4) else panic "grow: outside memory"; |
| 873 | let cap = load(RESULT + 12, 4) else panic "grow: outside memory"; |
| 874 | let heapUsed = load(HEAP, 8) else panic "grow: outside memory"; |
| 875 | return Grown { outcome, ptr, len, cap, used: heapUsed, steps: m.steps }; |
| 876 | } |
| 877 | |
| 878 | /// A slice that has room is left alone, and a slice without room gets a pool of the heap, |
| 879 | /// aligned for its elements, that holds the old elements. |
| 880 | @test unsafe fn sliceGrowCarves() throws (testing::TestError) { |
| 881 | // Room: nothing changes. |
| 882 | let enough = try sliceGrow(0, 3, 4, 3, 40, 256, HEAP); |
| 883 | try testing::expect(returned(enough.outcome, 1)); |
| 884 | try testing::expect(enough.ptr == OLD_AREA and enough.len == 3 and enough.cap == 4); |
| 885 | try testing::expect(enough.used == 40); |
| 886 | // The first allocation starts at the pool. |
| 887 | let first = try sliceGrow(0, 0, 0, 4, 0, 256, HEAP); |
| 888 | try testing::expect(returned(first.outcome, 1)); |
| 889 | try testing::expect(first.ptr == POOL and first.len == 0 and first.cap == 4); |
| 890 | try testing::expect(first.used == 32); |
| 891 | // The pointer is aligned in memory, and the old elements are copied. |
| 892 | let moved = try sliceGrow(0, 3, 3, 6, 4, 256, HEAP); |
| 893 | try testing::expect(returned(moved.outcome, 1)); |
| 894 | try testing::expect(moved.ptr == POOL + 8 and moved.len == 3 and moved.cap == 6); |
| 895 | try testing::expect(moved.used == 8 + 48); |
| 896 | for i in 0 .. 24 { |
| 897 | let value = load(moved.ptr + i, 1) else panic "grow: outside memory"; |
| 898 | try testing::expect(value == pattern(i) as u64); |
| 899 | } |
| 900 | let after = load(moved.ptr + 24, 1) else panic "grow: outside memory"; |
| 901 | try testing::expect(after == 0xaa); |
| 902 | } |
| 903 | |
| 904 | /// Sizes that are not powers of two, and elements with less alignment. |
| 905 | @test unsafe fn sliceGrowSizes() throws (testing::TestError) { |
| 906 | let wide = try sliceGrow(1, 2, 2, 5, 3, 256, HEAP); |
| 907 | try testing::expect(returned(wide.outcome, 1)); |
| 908 | try testing::expect(wide.ptr == POOL + 4 and wide.cap == 5 and wide.used == 4 + 60); |
| 909 | for i in 0 .. 24 { |
| 910 | let value = load(wide.ptr + i, 1) else panic "grow: outside memory"; |
| 911 | try testing::expect(value == pattern(i) as u64); |
| 912 | } |
| 913 | let thin = try sliceGrow(2, 3, 3, 7, 5, 256, HEAP); |
| 914 | try testing::expect(returned(thin.outcome, 1)); |
| 915 | try testing::expect(thin.ptr == POOL + 5 and thin.cap == 7 and thin.used == 5 + 21); |
| 916 | for i in 0 .. 9 { |
| 917 | let value = load(thin.ptr + i, 1) else panic "grow: outside memory"; |
| 918 | try testing::expect(value == pattern(i) as u64); |
| 919 | } |
| 920 | } |
| 921 | |
| 922 | /// A store-conditional lost to another hart retries from the new value of the heap: the |
| 923 | /// allocation lands after the memory that the other hart took, and takes the same bytes. |
| 924 | @test unsafe fn sliceGrowRetries() throws (testing::TestError) { |
| 925 | let quiet = try sliceGrow(0, 3, 3, 6, 4, 256, HEAP); |
| 926 | let busy = try growContended(0, 3, 3, 6, 4, 256, HEAP, 2); |
| 927 | try testing::expect(returned(busy.outcome, 1)); |
| 928 | // The two other allocations moved `used` from 4 to 36. The carve aligns that to 40. |
| 929 | try testing::expect(busy.ptr == POOL + 40 and busy.len == 3 and busy.cap == 6); |
| 930 | try testing::expect(busy.used == 40 + 48); |
| 931 | try testing::expect(busy.ptr <> quiet.ptr and busy.steps > quiet.steps); |
| 932 | for i in 0 .. 24 { |
| 933 | let value = load(busy.ptr + i, 1) else panic "grow: outside memory"; |
| 934 | try testing::expect(value == pattern(i) as u64); |
| 935 | } |
| 936 | // The other hart can take the room that this one needs. |
| 937 | let full = try growContended(0, 0, 0, 4, 0, 40, HEAP, 1); |
| 938 | try testing::expect(returned(full.outcome, 0) and full.used == 16); |
| 939 | } |
| 940 | |
| 941 | /// A heap without room fails, and a pool that fits exactly succeeds. Nothing changes on failure. |
| 942 | @test unsafe fn sliceGrowExhausted() throws (testing::TestError) { |
| 943 | let full = try sliceGrow(0, 3, 3, 10, 0, 64, HEAP); |
| 944 | try testing::expect(returned(full.outcome, 0)); |
| 945 | try testing::expect( |
| 946 | full.ptr == OLD_AREA and full.len == 3 and full.cap == 3 and full.used == 0 |
| 947 | ); |
| 948 | // The padding that aligns the pool counts. |
| 949 | let padded = try sliceGrow(0, 0, 0, 4, 4, 39, HEAP); |
| 950 | try testing::expect(returned(padded.outcome, 0) and padded.used == 4); |
| 951 | let fits = try sliceGrow(0, 0, 0, 4, 4, 40, HEAP); |
| 952 | try testing::expect(returned(fits.outcome, 1) and fits.used == 40); |
| 953 | let exact = try sliceGrow(0, 0, 0, 4, 0, 32, HEAP); |
| 954 | try testing::expect(returned(exact.outcome, 1) and exact.used == 32); |
| 955 | let over = try sliceGrow(0, 0, 0, 4, 0, 31, HEAP); |
| 956 | try testing::expect(returned(over.outcome, 0) and over.used == 0); |
| 957 | } |
| 958 | |
| 959 | /// Elements without bytes take nothing from a valid heap. |
| 960 | @test unsafe fn sliceGrowZeroSized() throws (testing::TestError) { |
| 961 | let grown = try sliceGrow(3, 2, 2, 5, 7, 0, HEAP); |
| 962 | try testing::expect(returned(grown.outcome, 1)); |
| 963 | try testing::expect(grown.ptr == 8 and grown.len == 2 and grown.cap == 5 and grown.used == 7); |
| 964 | let enough = try sliceGrow(3, 2, 5, 4, 7, 0, 0); |
| 965 | try testing::expect(returned(enough.outcome, 1) and enough.cap == 5); |
| 966 | } |
| 967 | |
| 968 | /// A capacity above the limit of the elements traps, and so does a null heap. |
| 969 | @test unsafe fn sliceGrowTraps() throws (testing::TestError) { |
| 970 | let over = try sliceGrow(0, 0, 0, 0x20000000, 0, 256, HEAP); |
| 971 | try testing::expect(trapped(over.outcome)); |
| 972 | let limit = try sliceGrow(0, 0, 0, 0x1fffffff, 0, 256, HEAP); |
| 973 | try testing::expect(returned(limit.outcome, 0)); |
| 974 | let zeroNull = try sliceGrow(3, 2, 2, 5, 7, 0, 0); |
| 975 | try testing::expect(trapped(zeroNull.outcome)); |
| 976 | let null = try sliceGrow(0, 0, 0, 4, 0, 256, 0); |
| 977 | try testing::expect(trapped(null.outcome)); |
| 978 | // Only the 32 low bits of the capacity count. |
| 979 | let wrapped = try sliceGrow(0, 0, 0, 0x100000002, 0, 256, HEAP); |
| 980 | try testing::expect(returned(wrapped.outcome, 1) and wrapped.cap == 2); |
| 981 | } |
| 982 | |
| 983 | /// An immediate index is an unsigned 32-bit value, like the same value in a register: only its |
| 984 | /// low 32 bits select the element, and an index at or above the count traps. |
| 985 | @test unsafe fn elemImmediateIndex() throws (testing::TestError) { |
| 986 | let indexes: [i64; 10] = [ |
| 987 | 0, 7, 8, 0xffffffff, 0x100000000, 0x100000001, 0x100000008, -1, -8, 0x7fffffff00000003 |
| 988 | ]; |
| 989 | let elements: [u64; 10] = [0, 7, 8, 0xffffffff, 0, 1, 8, 0xffffffff, 0xfffffff8, 3]; |
| 990 | for i in 0 .. indexes.len { |
| 991 | let index = indexes[i]; |
| 992 | let element = elements[i]; |
| 993 | for form in 0 .. 2 { |
| 994 | let outcome = try elem(index, 8, form == 1); |
| 995 | if element < 8 { |
| 996 | try testing::expect(returned(outcome, POINTER + element * ELEMENT)); |
| 997 | } else { |
| 998 | try testing::expect(trapped(outcome)); |
| 999 | } |
| 1000 | } |
| 1001 | } |
| 1002 | // No index is below a count of zero. |
| 1003 | for form in 0 .. 2 { |
| 1004 | let zero = try elem(0, 0, form == 1); |
| 1005 | let wide = try elem(0x100000000, 0, form == 1); |
| 1006 | try testing::expect(trapped(zero) and trapped(wide)); |
| 1007 | } |
| 1008 | } |
| 1009 | |
| 1010 | /// How a blit check passes its operands. |
| 1011 | union BlitMode: Copy { |
| 1012 | /// The addresses are in registers. |
| 1013 | Registers, |
| 1014 | /// Many values are live across the copy, so the addresses are spilled to the stack. |
| 1015 | Spilled, |
| 1016 | /// The destination is the source. |
| 1017 | Aliased, |
| 1018 | } |
| 1019 | |
| 1020 | /// The byte of the copied object at `index`. |
| 1021 | fn pattern(index: u64) -> u8 { |
| 1022 | return ((index * 7 + 3) & 0xff) as u8; |
| 1023 | } |
| 1024 | |
| 1025 | /// Compile an operation on objects of `size` bytes and `boundary` bytes of alignment. |
| 1026 | /// Return the sum of its two address parameters. With spilled operands, also return the sum |
| 1027 | /// of the values that are live across the operation. |
| 1028 | unsafe fn operationPackage( |
| 1029 | size: u32, boundary: u32, mode: BlitMode, instruction: il::Instr |
| 1030 | ) -> shared::Package throws (shared::Error) { |
| 1031 | let arena = heap::over(&mut BODY[..]); |
| 1032 | let mut body: *mut [il::Instr] = &mut []; |
| 1033 | let mut next: u32 = 2; |
| 1034 | if mode == BlitMode::Spilled { |
| 1035 | for i in 0 .. LIVE { |
| 1036 | try! body.append( |
| 1037 | il::Instr::Copy { |
| 1038 | dst: il::Reg { n: next + i }, val: il::Val::Imm(i as i64 + 1) |
| 1039 | }, |
| 1040 | arena |
| 1041 | ); |
| 1042 | } |
| 1043 | set next += LIVE; |
| 1044 | } |
| 1045 | try! body.append(instruction, arena); |
| 1046 | let mut sum = il::Val::Reg(il::Reg { n: 0 }); |
| 1047 | if mode == BlitMode::Spilled { |
| 1048 | // Use each live value several times, so that spilling the addresses is cheaper. |
| 1049 | for _ in 0 .. 3 { |
| 1050 | for i in 0 .. LIVE { |
| 1051 | try! body.append( |
| 1052 | il::Instr::BinOp { |
| 1053 | op: il::BinOp::Add, |
| 1054 | typ: il::Type::W64, |
| 1055 | dst: il::Reg { n: next }, |
| 1056 | a: il::Val::Reg(il::Reg { n: 2 + i }), |
| 1057 | b: il::Val::Reg(il::Reg { n: 2 + i }), |
| 1058 | }, |
| 1059 | arena |
| 1060 | ); |
| 1061 | try! body.append( |
| 1062 | il::Instr::BinOp { |
| 1063 | op: il::BinOp::Add, |
| 1064 | typ: il::Type::W64, |
| 1065 | dst: il::Reg { n: next + 1 }, |
| 1066 | a: sum, |
| 1067 | b: il::Val::Reg(il::Reg { n: next }), |
| 1068 | }, |
| 1069 | arena |
| 1070 | ); |
| 1071 | set sum = il::Val::Reg(il::Reg { n: next + 1 }); |
| 1072 | set next += 2; |
| 1073 | } |
| 1074 | } |
| 1075 | } |
| 1076 | try! body.append( |
| 1077 | il::Instr::BinOp { |
| 1078 | op: il::BinOp::Add, |
| 1079 | typ: il::Type::W64, |
| 1080 | dst: il::Reg { n: next }, |
| 1081 | a: sum, |
| 1082 | b: il::Val::Reg(il::Reg { n: 1 }), |
| 1083 | }, |
| 1084 | arena |
| 1085 | ); |
| 1086 | try! body.append(il::Instr::Ret { val: il::Val::Reg(il::Reg { n: next }) }, arena); |
| 1087 | set COPIED[0] = il::Layout { size, alignment: boundary, slots: &[], regions: 0 }; |
| 1088 | return try compileBody(&body[..], 2, &COPIED[..] as *[il::Layout], &[]); |
| 1089 | } |
| 1090 | |
| 1091 | /// Slice headers remain valid when address scaling spills both operands. |
| 1092 | @test unsafe fn spilledSliceHeaders() throws (testing::TestError) { |
| 1093 | for size in [16 as u32, 24] { |
| 1094 | for form in 0 .. 2 { |
| 1095 | let mut instruction = il::Instr::SliceSub { |
| 1096 | dst: il::Reg { n: 0 }, |
| 1097 | src: il::Reg { n: 1 }, |
| 1098 | layout: 0, |
| 1099 | start: il::Val::Imm(1), |
| 1100 | end: il::Val::Imm(3), |
| 1101 | }; |
| 1102 | if form == 1 { |
| 1103 | set instruction = il::Instr::SliceNew { |
| 1104 | dst: il::Reg { n: 0 }, |
| 1105 | base: il::Val::Reg(il::Reg { n: 1 }), |
| 1106 | layout: 0, |
| 1107 | count: 10, |
| 1108 | start: il::Val::Imm(1), |
| 1109 | end: il::Val::Imm(3), |
| 1110 | }; |
| 1111 | } |
| 1112 | let package = try operationPackage(size, 8, BlitMode::Spilled, instruction) catch { |
| 1113 | throw testing::TestError::Failed; |
| 1114 | }; |
| 1115 | let source = POINTER if form == 1 else SOURCE; |
| 1116 | let mut m = boot(&[RESULT, source]); |
| 1117 | putSlice(SOURCE, POINTER, 10, 12); |
| 1118 | let result = built(run(package.code, &mut m)); |
| 1119 | assert finished(result.outcome); |
| 1120 | assert result.ptr == POINTER + size as u64; |
| 1121 | assert result.len == 2; |
| 1122 | assert result.cap == (9 if form == 1 else 11); |
| 1123 | } |
| 1124 | } |
| 1125 | } |
| 1126 | |
| 1127 | /// The byte at `address` of the modeled memory. |
| 1128 | unsafe fn byteAt(address: u64) -> u8 { |
| 1129 | let value = load(address, 1) else panic "byteAt: outside memory"; |
| 1130 | return value as u8; |
| 1131 | } |
| 1132 | |
| 1133 | /// The base register of a store instruction, or nil for any other instruction. |
| 1134 | fn storeBase(word: u32) -> ?gen::Reg { |
| 1135 | match decode::decode(word) { |
| 1136 | case decode::Instr::Sd { rs1, .. } => return rs1, |
| 1137 | case decode::Instr::Sw { rs1, .. } => return rs1, |
| 1138 | case decode::Instr::Sh { rs1, .. } => return rs1, |
| 1139 | case decode::Instr::Sb { rs1, .. } => return rs1, |
| 1140 | case decode::Instr::Vector { bits } => { |
| 1141 | if (bits & 0xfff0707f) == 0x02000027 { |
| 1142 | return rv64::reg(decode::rs1(bits)); |
| 1143 | } |
| 1144 | return nil; |
| 1145 | } |
| 1146 | else => return nil, |
| 1147 | } |
| 1148 | } |
| 1149 | |
| 1150 | /// Whether the code reloads both spilled operands from the stack before its first store to |
| 1151 | /// other memory, which is the first store of the copy. |
| 1152 | fn reloadsOperands(code: *[u32]) -> bool { |
| 1153 | let mut destination = false; |
| 1154 | let mut source = false; |
| 1155 | for word in code { |
| 1156 | if let base = storeBase(word) { |
| 1157 | if *base <> *rv64::SP { |
| 1158 | return destination and source; |
| 1159 | } |
| 1160 | } else if let case decode::Instr::Ld { rd, rs1, .. } = decode::decode(word) { |
| 1161 | if *rs1 == *rv64::SP { |
| 1162 | set destination = destination or *rd == *rv64::SCRATCH2; |
| 1163 | set source = source or *rd == *rv64::SCRATCH1; |
| 1164 | } |
| 1165 | } |
| 1166 | } |
| 1167 | return false; |
| 1168 | } |
| 1169 | |
| 1170 | /// Copy `size` bytes between objects with `boundary` bytes of alignment in the given mode, and |
| 1171 | /// check the result: the destination holds the source, the bytes around it and the source are |
| 1172 | /// unchanged, the function returns the sum of the addresses that it was given, and, without |
| 1173 | /// spilled operands, the copy is not slower than a loop over its units. |
| 1174 | unsafe fn expectBlit(size: u32, boundary: u32, mode: BlitMode) throws (testing::TestError) { |
| 1175 | let operand: u32 = 0 if mode == BlitMode::Aliased else 1; |
| 1176 | let package = try operationPackage(size, boundary, mode, il::Instr::Blit { |
| 1177 | dst: il::Reg { n: 0 }, src: il::Reg { n: operand }, layout: 0 |
| 1178 | }) catch { |
| 1179 | throw testing::TestError::Failed; |
| 1180 | }; |
| 1181 | let target = TARGET_AREA + GUARD; |
| 1182 | let source = SOURCE_AREA + GUARD; |
| 1183 | let mut m = boot(&[target, source]); |
| 1184 | for i in 0 .. size as u64 + 2 * GUARD { |
| 1185 | set MEMORY[(SOURCE_AREA - MEMORY_BASE + i) as u32] = UNTOUCHED; |
| 1186 | set MEMORY[(TARGET_AREA - MEMORY_BASE + i) as u32] = UNTOUCHED; |
| 1187 | } |
| 1188 | for i in 0 .. size as u64 { |
| 1189 | set MEMORY[(source - MEMORY_BASE + i) as u32] = pattern(i); |
| 1190 | } |
| 1191 | if mode == BlitMode::Aliased { |
| 1192 | for i in 0 .. size as u64 { |
| 1193 | set MEMORY[(target - MEMORY_BASE + i) as u32] = pattern(i); |
| 1194 | } |
| 1195 | } |
| 1196 | let outcome = run(package.code, &mut m); |
| 1197 | // The sum of the values that are live across the copy: each of them, doubled, three times. |
| 1198 | let mut live: u64 = 0; |
| 1199 | if mode == BlitMode::Spilled { |
| 1200 | set live = 3 * LIVE as u64 * (LIVE as u64 + 1); |
| 1201 | } |
| 1202 | try testing::expect(returned(outcome, target + source + live)); |
| 1203 | for i in 0 .. size as u64 { |
| 1204 | try testing::expect(byteAt(target + i) == pattern(i)); |
| 1205 | if mode <> BlitMode::Aliased { |
| 1206 | try testing::expect(byteAt(source + i) == pattern(i)); |
| 1207 | } |
| 1208 | } |
| 1209 | for i in 0 .. GUARD { |
| 1210 | try testing::expect(byteAt(TARGET_AREA + i) == UNTOUCHED); |
| 1211 | try testing::expect(byteAt(target + size as u64 + i) == UNTOUCHED); |
| 1212 | if mode <> BlitMode::Aliased { |
| 1213 | try testing::expect(byteAt(SOURCE_AREA + i) == UNTOUCHED); |
| 1214 | try testing::expect(byteAt(source + size as u64 + i) == UNTOUCHED); |
| 1215 | } |
| 1216 | } |
| 1217 | if mode == BlitMode::Spilled and size > 0 { |
| 1218 | try testing::expect(reloadsOperands(package.code)); |
| 1219 | } |
| 1220 | if mode == BlitMode::Registers { |
| 1221 | // A copy is a load and a store per unit, or a loop of five instructions per unit. |
| 1222 | let unit = boundary; |
| 1223 | let units = (size + unit - 1) / unit; |
| 1224 | try testing::expect(m.steps <= 5 * units + 16); |
| 1225 | } |
| 1226 | } |
| 1227 | |
| 1228 | /// The blit checks copy every size below this one. |
| 1229 | constant SMALL_SIZES: u32 = 41; |
| 1230 | /// Larger sizes of the blit checks. They include copies that need a loop, with and without a |
| 1231 | /// tail, and a copy longer than an immediate offset reaches. |
| 1232 | constant LARGE_SIZES: [u32; 18] = [ |
| 1233 | 48, 56, 63, 64, 65, 72, 77, 96, 127, 128, 129, 255, 256, 257, |
| 1234 | 511, 520, 2051, 2056, |
| 1235 | ]; |
| 1236 | /// Alignments of the objects of the blit checks. |
| 1237 | constant BOUNDARIES: [u32; 4] = [1, 2, 4, 8]; |
| 1238 | /// The modes of the blit checks. |
| 1239 | constant MODES: [BlitMode; 3] = [BlitMode::Registers, BlitMode::Spilled, BlitMode::Aliased]; |
| 1240 | |
| 1241 | /// A copy moves exactly the bytes of the layout, |
| 1242 | /// for every size from zero to forty and some larger ones, also sizes that the alignment does |
| 1243 | /// not divide. It leaves the addresses intact, also when they are spilled or equal. |
| 1244 | @test unsafe fn blitCopies() throws (testing::TestError) { |
| 1245 | for boundary in BOUNDARIES { |
| 1246 | for mode in MODES { |
| 1247 | if mode == BlitMode::Registers { |
| 1248 | for size in 0 .. SMALL_SIZES { |
| 1249 | try expectBlit(size, boundary, mode); |
| 1250 | } |
| 1251 | for large in LARGE_SIZES { |
| 1252 | try expectBlit(large, boundary, mode); |
| 1253 | } |
| 1254 | } else { |
| 1255 | let loopStart = (rv64::BLIT_UNROLL_UNITS + 1) * boundary; |
| 1256 | // The last unrolled size uses every smaller access width. |
| 1257 | for size in [ |
| 1258 | 0 as u32, 1, boundary, boundary + 1, |
| 1259 | loopStart - 1, loopStart, loopStart + 1, 2051, 2056, |
| 1260 | ] { |
| 1261 | try expectBlit(size, boundary, mode); |
| 1262 | } |
| 1263 | } |
| 1264 | } |
| 1265 | } |
| 1266 | } |
| 1267 | |
| 1268 | /// Address of the trait object of a trait call check. |
| 1269 | constant OBJECT_AT: u64 = 0x1100; |
| 1270 | /// Address of the method table of a trait call check. |
| 1271 | constant TABLE_AT: u64 = 0x1200; |
| 1272 | /// Receiver of the trait object of a trait call check. |
| 1273 | constant RECEIVER: u64 = 0x77; |
| 1274 | |
| 1275 | /// A trait call passes the receiver of the object at its position among the arguments and |
| 1276 | /// calls the method from the table. An object that was never built has a zero table, and |
| 1277 | /// the call traps instead of jumping through it. |
| 1278 | @test unsafe fn traitCallReceiver() throws (testing::TestError) { |
| 1279 | let call = il::Instr::TraitCall { |
| 1280 | retTy: il::ValType::Data(il::Type::W64), |
| 1281 | dst: il::Reg { n: 1 }, |
| 1282 | obj: il::Reg { n: 0 }, |
| 1283 | method: 1, |
| 1284 | receiver: 1, |
| 1285 | args: il::ArgRange { start: 0, len: 2 }, |
| 1286 | }; |
| 1287 | let body = [call, il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 1 }) }]; |
| 1288 | let package = try compileBody( |
| 1289 | &body[..], |
| 1290 | 1, |
| 1291 | &[il::Layout { size: ELEMENT as u32, alignment: 8, slots: &[], regions: 0 }], |
| 1292 | &[il::Val::Imm(5), il::Val::Undef] |
| 1293 | ) catch { |
| 1294 | throw testing::TestError::Failed; |
| 1295 | }; |
| 1296 | let mut m = boot(&[OBJECT_AT]); |
| 1297 | try testing::expect(store(OBJECT_AT, 8, RECEIVER)); |
| 1298 | try testing::expect(store(OBJECT_AT + 8, 8, TABLE_AT)); |
| 1299 | try testing::expect(store(TABLE_AT + 8, 8, RETURN)); |
| 1300 | try testing::expect(returned(run(package.code, &mut m), 5)); |
| 1301 | try testing::expect(read(&m, rv64::A1) == RECEIVER); |
| 1302 | |
| 1303 | let mut zero = boot(&[OBJECT_AT]); |
| 1304 | try testing::expect(trapped(run(package.code, &mut zero))); |
| 1305 | } |