.ai/
compiler/
lib/
examples/
std/
arch/
collections/
lang/
alloc/
ast/
gen/
il/
printer.rad
16.3 KiB
verify.rad
11.9 KiB
module/
parser/
resolver/
scanner/
alloc.rad
4.2 KiB
ast.rad
22.6 KiB
gen.rad
489 B
il.rad
18.0 KiB
lower.rad
261.8 KiB
module.rad
13.4 KiB
package.rad
1.2 KiB
parser.rad
79.7 KiB
resolver.rad
246.8 KiB
scanner.rad
18.1 KiB
sexpr.rad
6.3 KiB
strings.rad
2.2 KiB
sys/
arch.rad
65 B
collections.rad
36 B
fmt.rad
3.8 KiB
intrinsics.rad
399 B
io.rad
1.2 KiB
lang.rad
222 B
mem.rad
2.1 KiB
sys.rad
167 B
testing.rad
2.3 KiB
tests.rad
11.6 KiB
vec.rad
3.1 KiB
std.rad
231 B
scripts/
seed/
test/
vim/
.gitignore
353 B
.gitsigners
112 B
LICENSE
1.1 KiB
Makefile
3.0 KiB
README
2.5 KiB
std.lib
1.0 KiB
std.lib.test
252 B
lib/std/lang/il/verify.rad
raw
| 1 | //! RIL type verifier. |
| 2 | //! |
| 3 | //! Walks each function's blocks and checks pointer-provenance rules: |
| 4 | //! |
| 5 | //! 1. Every register is assigned a type (W8/W16/W32/W64/Ptr) based on |
| 6 | //! its defining instruction. |
| 7 | //! 2. Load/Store/Blit base registers must have type Ptr. |
| 8 | //! 3. MakePtr is flagged as a provenance violation. |
| 9 | //! 4. BinOp::Add with Ptr type requires exactly one Ptr operand. |
| 10 | //! 5. Copy(DataSym)/Copy(FnAddr) produces Ptr; Copy(Imm) produces W64. |
| 11 | //! 6. Reserve always produces Ptr. |
| 12 | //! 7. Static offset checks: field access at constant offsets is validated |
| 13 | //! against the known allocation size when available. |
| 14 | |
| 15 | use std::fmt; |
| 16 | use std::io; |
| 17 | use std::lang::alloc; |
| 18 | |
| 19 | /// Maximum SSA registers per function (must match regalloc). |
| 20 | const MAX_REGS: u32 = 8192; |
| 21 | |
| 22 | /// Unknown bound sentinel. When a pointer's bound is zero, bounds |
| 23 | /// checking is skipped (the allocation size is not statically known). |
| 24 | const UNKNOWN_BOUND: u32 = 0; |
| 25 | |
| 26 | /// A verification error found in an IL function. |
| 27 | pub record VerifyError { |
| 28 | /// Name of the function containing the error. |
| 29 | fnName: *[u8], |
| 30 | /// Block index where the error occurred. |
| 31 | blockIdx: u32, |
| 32 | /// Instruction index within the block. |
| 33 | instrIdx: u32, |
| 34 | /// Description of the error. |
| 35 | message: *[u8], |
| 36 | } |
| 37 | |
| 38 | /// Result of verifying a program. |
| 39 | pub record VerifyResult { |
| 40 | /// Errors found during verification. |
| 41 | errors: *mut [VerifyError], |
| 42 | /// Number of MakePtr instructions found (provenance escapes). |
| 43 | makePtrCount: u32, |
| 44 | } |
| 45 | |
| 46 | /// Verify pointer-type safety of an IL program. |
| 47 | /// |
| 48 | /// Returns a list of errors. An empty list means the program passes |
| 49 | /// all checks. MakePtr instructions are counted but not treated as |
| 50 | /// errors (they are legal in unsafe code). |
| 51 | pub fn verifyProgram(program: *super::Program, arena: *mut alloc::Arena) -> VerifyResult { |
| 52 | let a = alloc::arenaAllocator(arena); |
| 53 | let mut errors: *mut [VerifyError] = &mut []; |
| 54 | let mut makePtrCount: u32 = 0; |
| 55 | |
| 56 | for func in program.fns { |
| 57 | if func.isExtern { |
| 58 | continue; |
| 59 | } |
| 60 | verifyFn(func, &mut errors, &mut makePtrCount, a); |
| 61 | } |
| 62 | return VerifyResult { errors, makePtrCount }; |
| 63 | } |
| 64 | |
| 65 | /// Inferred type of an SSA register: either a word width or pointer. |
| 66 | union RegType { |
| 67 | /// Not yet defined. |
| 68 | Undef, |
| 69 | /// Word type (W8, W16, W32, W64). |
| 70 | Word(super::Type), |
| 71 | /// Pointer type with known bound. Bound of 0 means unknown. |
| 72 | Ptr(u32), |
| 73 | } |
| 74 | |
| 75 | /// Check if a register type is Ptr (any bound). |
| 76 | fn isPtr(t: RegType) -> bool { |
| 77 | if let case RegType::Ptr(_) = t { return true; } |
| 78 | return false; |
| 79 | } |
| 80 | |
| 81 | /// Get the bound of a Ptr register type, or 0 if not Ptr. |
| 82 | fn ptrBound(t: RegType) -> u32 { |
| 83 | if let case RegType::Ptr(b) = t { return b; } |
| 84 | return UNKNOWN_BOUND; |
| 85 | } |
| 86 | |
| 87 | /// Create a Ptr RegType from an IL type. Non-Ptr types produce Word. |
| 88 | fn regTypeFromIl(typ: super::Type) -> RegType { |
| 89 | if let case super::Type::Ptr = typ { |
| 90 | return RegType::Ptr(UNKNOWN_BOUND); |
| 91 | } |
| 92 | return RegType::Word(typ); |
| 93 | } |
| 94 | |
| 95 | /// Infer the type of a Val without looking at the register map. |
| 96 | /// Returns nil for Reg values (caller must look up the map). |
| 97 | fn valType(val: super::Val) -> ?RegType { |
| 98 | match val { |
| 99 | case super::Val::Imm(_) => return RegType::Word(super::Type::W64), |
| 100 | case super::Val::DataSym(_), |
| 101 | super::Val::FnAddr(_) => return RegType::Ptr(UNKNOWN_BOUND), |
| 102 | case super::Val::Undef => return RegType::Word(super::Type::W64), |
| 103 | case super::Val::Reg(_) => return nil, |
| 104 | } |
| 105 | } |
| 106 | |
| 107 | /// Look up the type of a Val, consulting the register map for Reg values. |
| 108 | fn resolveValType(val: super::Val, regs: *[RegType]) -> RegType { |
| 109 | if let vt = valType(val) { |
| 110 | return vt; |
| 111 | } |
| 112 | let case super::Val::Reg(r) = val else return RegType::Word(super::Type::W64); |
| 113 | if r.n < regs.len { |
| 114 | return regs[r.n]; |
| 115 | } |
| 116 | return RegType::Undef; |
| 117 | } |
| 118 | |
| 119 | /// Extract a constant i64 from a Val, if it is an immediate. |
| 120 | fn immVal(val: super::Val) -> ?i64 { |
| 121 | if let case super::Val::Imm(v) = val { return v; } |
| 122 | return nil; |
| 123 | } |
| 124 | |
| 125 | /// Verify a single function. |
| 126 | fn verifyFn( |
| 127 | func: *super::Fn, |
| 128 | errors: *mut *mut [VerifyError], |
| 129 | makePtrCount: *mut u32, |
| 130 | a: alloc::Allocator, |
| 131 | ) { |
| 132 | // Type map: regId -> RegType. |
| 133 | let mut regTypes: [RegType; MAX_REGS] = undefined; |
| 134 | for i in 0..MAX_REGS { |
| 135 | regTypes[i] = RegType::Undef; |
| 136 | } |
| 137 | |
| 138 | // Type function parameters. |
| 139 | for param in func.params { |
| 140 | setReg(&mut regTypes[..], param.value, regTypeFromIl(param.type)); |
| 141 | } |
| 142 | |
| 143 | // Walk blocks. |
| 144 | for block, blockIdx in func.blocks { |
| 145 | // Type block parameters. |
| 146 | for param in block.params { |
| 147 | setReg(&mut regTypes[..], param.value, regTypeFromIl(param.type)); |
| 148 | } |
| 149 | |
| 150 | // Check each instruction. |
| 151 | for instr, instrIdx in block.instrs { |
| 152 | let mut ctx = VerifyCtx { |
| 153 | func, |
| 154 | blockIdx: blockIdx as u32, |
| 155 | instrIdx: instrIdx as u32, |
| 156 | regs: &mut regTypes[..], |
| 157 | errors, |
| 158 | a, |
| 159 | }; |
| 160 | verifyInstr(&mut ctx, instr, makePtrCount); |
| 161 | } |
| 162 | } |
| 163 | } |
| 164 | |
| 165 | /// Verify a single instruction: assign dst type and check operands. |
| 166 | fn verifyInstr(ctx: *mut VerifyCtx, instr: super::Instr, makePtrCount: *mut u32) { |
| 167 | match instr { |
| 168 | case super::Instr::Reserve { dst, size, .. } => { |
| 169 | let bound = immVal(size) else { |
| 170 | setReg(ctx.regs, dst, RegType::Ptr(UNKNOWN_BOUND)); |
| 171 | return; |
| 172 | }; |
| 173 | setReg(ctx.regs, dst, RegType::Ptr(bound as u32)); |
| 174 | } |
| 175 | case super::Instr::Load { typ, dst, src, offset } => { |
| 176 | checkPtrBase(ctx, src, "load base"); |
| 177 | checkAccess(ctx, src, offset, super::typeSize(typ)); |
| 178 | setReg(ctx.regs, dst, regTypeFromIl(typ)); |
| 179 | } |
| 180 | case super::Instr::Sload { typ, dst, src, offset } => { |
| 181 | checkPtrBase(ctx, src, "sload base"); |
| 182 | checkAccess(ctx, src, offset, super::typeSize(typ)); |
| 183 | setReg(ctx.regs, dst, regTypeFromIl(typ)); |
| 184 | } |
| 185 | case super::Instr::Store { typ, dst, offset, .. } => { |
| 186 | checkPtrBase(ctx, dst, "store base"); |
| 187 | checkAccess(ctx, dst, offset, super::typeSize(typ)); |
| 188 | } |
| 189 | case super::Instr::Blit { dst, src, size } => { |
| 190 | checkPtrBase(ctx, dst, "blit dst"); |
| 191 | checkPtrBase(ctx, src, "blit src"); |
| 192 | if let sz = immVal(size) { |
| 193 | checkAccess(ctx, dst, 0, sz as u32); |
| 194 | checkAccess(ctx, src, 0, sz as u32); |
| 195 | } |
| 196 | } |
| 197 | case super::Instr::Copy { dst, val } => { |
| 198 | setReg(ctx.regs, dst, resolveValType(val, ctx.regs)); |
| 199 | } |
| 200 | case super::Instr::BinOp { op, typ, dst, a: va, b: vb } => { |
| 201 | if let case super::Type::Ptr = typ { |
| 202 | let aIsPtr = isPtr(resolveValType(va, ctx.regs)); |
| 203 | let bIsPtr = isPtr(resolveValType(vb, ctx.regs)); |
| 204 | |
| 205 | if let case super::BinOp::Add = op { |
| 206 | if not (aIsPtr or bIsPtr) { |
| 207 | emitError(ctx.func, ctx.blockIdx, ctx.instrIdx, ctx.errors, ctx.a, |
| 208 | "ptr add: neither operand is Ptr"); |
| 209 | } |
| 210 | } |
| 211 | setReg(ctx.regs, dst, RegType::Ptr(derivePtrAdd(va, vb, ctx.regs))); |
| 212 | } else { |
| 213 | setReg(ctx.regs, dst, RegType::Word(typ)); |
| 214 | } |
| 215 | } |
| 216 | case super::Instr::UnOp { typ, dst, .. } => |
| 217 | setReg(ctx.regs, dst, RegType::Word(typ)), |
| 218 | case super::Instr::Zext { dst, .. } => |
| 219 | setReg(ctx.regs, dst, RegType::Word(super::Type::W64)), |
| 220 | case super::Instr::Sext { dst, .. } => |
| 221 | setReg(ctx.regs, dst, RegType::Word(super::Type::W64)), |
| 222 | case super::Instr::MakePtr { dst, .. } => { |
| 223 | *makePtrCount += 1; |
| 224 | setReg(ctx.regs, dst, RegType::Ptr(UNKNOWN_BOUND)); |
| 225 | } |
| 226 | case super::Instr::Call { retTy, dst, .. } => { |
| 227 | if let d = dst { |
| 228 | setReg(ctx.regs, d, regTypeFromIl(retTy)); |
| 229 | } |
| 230 | } |
| 231 | case super::Instr::Ecall { dst, .. } => |
| 232 | setReg(ctx.regs, dst, RegType::Word(super::Type::W64)), |
| 233 | case super::Instr::Elem { dst, base, stride, .. } => { |
| 234 | checkPtrBase(ctx, base, "elem base"); |
| 235 | // After Elem, the pointer is valid for `stride` bytes. |
| 236 | setReg(ctx.regs, dst, RegType::Ptr(stride)); |
| 237 | } |
| 238 | case super::Instr::Ret { .. }, |
| 239 | super::Instr::Jmp { .. }, |
| 240 | super::Instr::Br { .. }, |
| 241 | super::Instr::Switch { .. }, |
| 242 | super::Instr::Unreachable, |
| 243 | super::Instr::Ebreak => {} |
| 244 | } |
| 245 | } |
| 246 | |
| 247 | /// Derive the remaining bound after `ptr + offset`. |
| 248 | /// If the pointer operand has a known bound and the offset is a constant, |
| 249 | /// returns `bound - offset`. Otherwise returns UNKNOWN_BOUND. |
| 250 | fn derivePtrAdd(va: super::Val, vb: super::Val, regs: *[RegType]) -> u32 { |
| 251 | // Find which operand is the pointer and which is the offset. |
| 252 | let aType = resolveValType(va, regs); |
| 253 | let bType = resolveValType(vb, regs); |
| 254 | |
| 255 | let mut bound: u32 = UNKNOWN_BOUND; |
| 256 | let mut offset: ?i64 = nil; |
| 257 | |
| 258 | if isPtr(aType) { |
| 259 | bound = ptrBound(aType); |
| 260 | offset = immVal(vb); |
| 261 | } else if isPtr(bType) { |
| 262 | bound = ptrBound(bType); |
| 263 | offset = immVal(va); |
| 264 | } |
| 265 | if bound == UNKNOWN_BOUND { |
| 266 | return UNKNOWN_BOUND; |
| 267 | } |
| 268 | let off = offset else return UNKNOWN_BOUND; |
| 269 | if off < 0 or off as u32 >= bound { |
| 270 | return UNKNOWN_BOUND; |
| 271 | } |
| 272 | return bound - (off as u32); |
| 273 | } |
| 274 | |
| 275 | /// Set a register's type in the map. |
| 276 | fn setReg(regs: *mut [RegType], reg: super::Reg, typ: RegType) { |
| 277 | if reg.n < regs.len { |
| 278 | regs[reg.n] = typ; |
| 279 | } |
| 280 | } |
| 281 | |
| 282 | /// Check that a register used as a memory base has type Ptr. |
| 283 | fn checkPtrBase(ctx: *mut VerifyCtx, reg: super::Reg, context: *[u8]) { |
| 284 | if reg.n >= ctx.regs.len { |
| 285 | return; |
| 286 | } |
| 287 | if not isPtr(ctx.regs[reg.n]) { |
| 288 | emitError(ctx.func, ctx.blockIdx, ctx.instrIdx, ctx.errors, ctx.a, context); |
| 289 | } |
| 290 | } |
| 291 | |
| 292 | /// Check that a memory access at `base + offset` of `size` bytes is |
| 293 | /// within the known bounds of the pointer. Skipped when the bound is |
| 294 | /// unknown (UNKNOWN_BOUND). |
| 295 | fn checkAccess( |
| 296 | ctx: *mut VerifyCtx, |
| 297 | base: super::Reg, |
| 298 | offset: i32, |
| 299 | size: u32, |
| 300 | ) { |
| 301 | if base.n >= ctx.regs.len { |
| 302 | return; |
| 303 | } |
| 304 | let bound = ptrBound(ctx.regs[base.n]); |
| 305 | if bound == UNKNOWN_BOUND { |
| 306 | return; |
| 307 | } |
| 308 | if offset < 0 { |
| 309 | emitError(ctx.func, ctx.blockIdx, ctx.instrIdx, ctx.errors, ctx.a, "negative offset"); |
| 310 | return; |
| 311 | } |
| 312 | let end = (offset as u32) + size; |
| 313 | if end > bound { |
| 314 | emitError(ctx.func, ctx.blockIdx, ctx.instrIdx, ctx.errors, ctx.a, "access out of bounds"); |
| 315 | } |
| 316 | } |
| 317 | |
| 318 | /// Context passed to verification helpers to avoid parameter bloat. |
| 319 | record VerifyCtx { |
| 320 | func: *super::Fn, |
| 321 | blockIdx: u32, |
| 322 | instrIdx: u32, |
| 323 | regs: *mut [RegType], |
| 324 | errors: *mut *mut [VerifyError], |
| 325 | a: alloc::Allocator, |
| 326 | } |
| 327 | |
| 328 | /// Record a verification error. |
| 329 | fn emitError( |
| 330 | func: *super::Fn, |
| 331 | blockIdx: u32, |
| 332 | instrIdx: u32, |
| 333 | errors: *mut *mut [VerifyError], |
| 334 | a: alloc::Allocator, |
| 335 | message: *[u8], |
| 336 | ) { |
| 337 | errors.append(VerifyError { |
| 338 | fnName: func.name, |
| 339 | blockIdx, |
| 340 | instrIdx, |
| 341 | message, |
| 342 | }, a); |
| 343 | } |
| 344 | |
| 345 | /// Print verification results to stderr. |
| 346 | pub fn printResult(result: *VerifyResult) { |
| 347 | if result.errors.len == 0 and result.makePtrCount == 0 { |
| 348 | io::printError("verify: ok\n"); |
| 349 | return; |
| 350 | } |
| 351 | let mut buf: [u8; 10] = undefined; |
| 352 | |
| 353 | if result.makePtrCount > 0 { |
| 354 | io::printError("verify: "); |
| 355 | io::printError(fmt::formatU32(result.makePtrCount, &mut buf[..])); |
| 356 | io::printError(" MakePtr instruction(s) found\n"); |
| 357 | } |
| 358 | for err in result.errors { |
| 359 | io::printError("verify: "); |
| 360 | io::printError(err.fnName); |
| 361 | io::printError(" block "); |
| 362 | io::printError(fmt::formatU32(err.blockIdx, &mut buf[..])); |
| 363 | io::printError(" instr "); |
| 364 | io::printError(fmt::formatU32(err.instrIdx, &mut buf[..])); |
| 365 | io::printError(": "); |
| 366 | io::printError(err.message); |
| 367 | io::printError("\n"); |
| 368 | } |
| 369 | } |