.githooks/
compiler/
kernel/
lib/
examples/
std/
arch/
bits/
char/
collections/
fs/
hash/
lang/
alloc/
ast/
gen/
il/
binary/
link/
printer/
verify/
binary.rad
14.7 KiB
link.rad
11.8 KiB
printer.rad
31.7 KiB
verify.rad
99.5 KiB
layout/
lower/
manifest/
module/
parser/
resolver/
scanner/
sexpr/
alloc.rad
1.2 KiB
ast.rad
36.0 KiB
gen.rad
513 B
il.rad
48.5 KiB
layout.rad
6.9 KiB
lower.rad
487.6 KiB
manifest.rad
22.5 KiB
module.rad
17.8 KiB
package.rad
1.5 KiB
parser.rad
114.1 KiB
pretty.rad
103.6 KiB
resolver.rad
508.1 KiB
scanner.rad
19.3 KiB
sexpr.rad
7.1 KiB
strings.rad
3.3 KiB
types.rad
620 B
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/lang/il/verify.rad
raw
| 1 | //! RIL verifier. |
| 2 | //! |
| 3 | //! Decides whether a decoded package is safe to compile to native code and run in a |
| 4 | //! domain, whatever produced it. Every RIL input is hostile. The checks keep the memory |
| 5 | //! of a domain type-stable: every object has a layout, the slots of a layout that hold |
| 6 | //! pointers, slices and function values are written only with values of their kind, and |
| 7 | //! every pointer that is accessed is non-null and valid by construction. Pointers are |
| 8 | //! never checked on access. Authority, termination and traps are outside its scope. |
| 9 | //! |
| 10 | //! Registers have one type, fixed at their single definition. A pointer register also |
| 11 | //! tracks a constant offset into its layout, and whether it is derived from a `reserve` |
| 12 | //! of the current function, a local pointer. Only a local pointer can hold non-owning |
| 13 | //! pointers, so they never outlive their frame. An object that a parameter points to |
| 14 | //! can hold them too, a target object: each region of its layout receives only |
| 15 | //! pointers of that region or of sources that the signature names for it. Each region |
| 16 | //! of a borrowed result must come from a source named by its signature: a parameter's |
| 17 | //! storage or a region of its contents (see [`checkBorrow`]). A function that returns |
| 18 | //! a borrowed aggregate writes it to its first parameter, an object of the caller's |
| 19 | //! frame that can hold references. |
| 20 | //! |
| 21 | //! The decoder establishes the structure that the checks rely on: table indices are in |
| 22 | //! range, layouts are well formed (see [`layout`]), argument ranges lie within the pools |
| 23 | //! of their function, and branch targets are blocks of the function. [`verifyProgram`] |
| 24 | //! checks everything else, and [`verifyPackage`] adds the rules of a loadable package. |
| 25 | |
| 26 | export mod layout; |
| 27 | export mod flow; |
| 28 | export mod data; |
| 29 | export mod linking; |
| 30 | @test export mod tests; |
| 31 | |
| 32 | use std::collections::dict; |
| 33 | use std::lang::il; |
| 34 | use std::lang::il::binary; |
| 35 | use std::mem; |
| 36 | use std::mem::heap; |
| 37 | |
| 38 | /////////////// |
| 39 | // Constants // |
| 40 | /////////////// |
| 41 | |
| 42 | /// Rounding of dictionary storage: the table must be a power of two and at most half full. |
| 43 | constant DICT_MINIMUM: u32 = 2; |
| 44 | /// Largest alignment of an object in a frame, which is the alignment of the stack. |
| 45 | constant FRAME_ALIGNMENT: u32 = 16; |
| 46 | /// Largest symbol count that fits a dictionary table size in 32 bits. |
| 47 | constant SYMBOLS_MAX: u32 = 0x3fffffff; |
| 48 | |
| 49 | /////////// |
| 50 | // Types // |
| 51 | /////////// |
| 52 | |
| 53 | /// Limits and parameters of the verifier. |
| 54 | export record Config: Copy { |
| 55 | /// Exclusive upper bound for register numbers in a function. |
| 56 | registers: u32, |
| 57 | /// Maximum number of blocks in a function. |
| 58 | blocks: u32, |
| 59 | /// Maximum size of a layout in bytes. |
| 60 | layoutSize: u32, |
| 61 | /// Maximum nesting of sub and array nodes in a layout. |
| 62 | layoutDepth: u32, |
| 63 | /// Maximum number of parameters of a function, signature or block, and of arguments |
| 64 | /// of a call. Arguments beyond the registers go to the stack of the caller. |
| 65 | params: u32, |
| 66 | /// Size in bytes of the Env record that the kernel passes to the entry function. |
| 67 | envSize: u32, |
| 68 | } |
| 69 | |
| 70 | /// The rule that an error violates. |
| 71 | export union Rule: Copy { |
| 72 | /// The scratch arena is full. |
| 73 | Storage, |
| 74 | /// A count or size exceeds a limit of the configuration. |
| 75 | Limit, |
| 76 | /// A symbol is empty, duplicated, or does not name a definition of the package. |
| 77 | Symbol, |
| 78 | /// The layout or signature table is malformed. |
| 79 | Layout, |
| 80 | /// Blocks, terminators or parameters are malformed. |
| 81 | Structure, |
| 82 | /// A register is out of range, defined twice, or used where its definition does not |
| 83 | /// dominate the use. |
| 84 | Register, |
| 85 | /// An operand has the wrong kind: data where a pointer or function value is needed. |
| 86 | Type, |
| 87 | /// A nullable pointer or function value is used where a non-null one is needed. |
| 88 | Null, |
| 89 | /// An offset, index or region lies outside its layout. |
| 90 | Bounds, |
| 91 | /// A data access overlaps a slot, or a slot access is not at a slot of the right kind. |
| 92 | Slot, |
| 93 | /// A pointer is used as a pointer to a layout that it does not view. |
| 94 | View, |
| 95 | /// A pointer of the wrong class: a non-owning pointer where an owning one is needed or |
| 96 | /// where it could outlive its frame. |
| 97 | Class, |
| 98 | /// A write through a pointer to read-only memory, or a read-only pointer used as writable. |
| 99 | Mutability, |
| 100 | /// The callee of a call, or its return type, is invalid. |
| 101 | Call, |
| 102 | /// The number of arguments does not match the parameters. |
| 103 | Arity, |
| 104 | /// A return type or returned value is invalid. |
| 105 | Return, |
| 106 | /// A data initializer is invalid. |
| 107 | Data, |
| 108 | /// A package-level rule is violated. |
| 109 | Package, |
| 110 | } |
| 111 | |
| 112 | /// Where an error was found. |
| 113 | export union Place: Copy { |
| 114 | /// The package as a whole. |
| 115 | Package, |
| 116 | /// A layout, by index. |
| 117 | Layout(u32), |
| 118 | /// A signature, by index. |
| 119 | Signature(u32), |
| 120 | /// A trait, by index. |
| 121 | Trait(u32), |
| 122 | /// A data definition, by index. |
| 123 | Data(u32), |
| 124 | /// A function, by index. |
| 125 | Fn(u32), |
| 126 | /// An instruction of a function. |
| 127 | Instr { |
| 128 | /// Index of the function. |
| 129 | func: u32, |
| 130 | /// Index of the block. |
| 131 | block: u32, |
| 132 | /// Index of the instruction in the block. |
| 133 | instr: u32, |
| 134 | }, |
| 135 | } |
| 136 | |
| 137 | /// A rule violation and its location. |
| 138 | export record Error: Copy { |
| 139 | /// The rule that is violated. |
| 140 | rule: Rule, |
| 141 | /// Where the violation is. |
| 142 | place: Place, |
| 143 | } |
| 144 | |
| 145 | /// Name of a rule. |
| 146 | export fn ruleName(rule: Rule) -> *[u8] { |
| 147 | match rule { |
| 148 | case Rule::Storage => return "Storage", |
| 149 | case Rule::Limit => return "Limit", |
| 150 | case Rule::Symbol => return "Symbol", |
| 151 | case Rule::Layout => return "Layout", |
| 152 | case Rule::Structure => return "Structure", |
| 153 | case Rule::Register => return "Register", |
| 154 | case Rule::Type => return "Type", |
| 155 | case Rule::Null => return "Null", |
| 156 | case Rule::Bounds => return "Bounds", |
| 157 | case Rule::Slot => return "Slot", |
| 158 | case Rule::View => return "View", |
| 159 | case Rule::Class => return "Class", |
| 160 | case Rule::Mutability => return "Mutability", |
| 161 | case Rule::Call => return "Call", |
| 162 | case Rule::Arity => return "Arity", |
| 163 | case Rule::Return => return "Return", |
| 164 | case Rule::Data => return "Data", |
| 165 | case Rule::Package => return "Package", |
| 166 | } |
| 167 | } |
| 168 | |
| 169 | /// The error for a full scratch arena. |
| 170 | export constant STORAGE: Error = Error { rule: Rule::Storage, place: Place::Package }; |
| 171 | |
| 172 | /// Reference to the signature of a function value. |
| 173 | export union SigRef: Copy { |
| 174 | /// An entry of the signature table of the program. |
| 175 | Table(u32), |
| 176 | /// The signature of a function of the program, by index. |
| 177 | Func(u32), |
| 178 | } |
| 179 | |
| 180 | /// Facts about a pointer register. |
| 181 | record PtrState: Copy { |
| 182 | /// Layout that the pointer views. |
| 183 | layout: u32, |
| 184 | /// Constant byte offset of the pointer inside its layout. |
| 185 | offset: u32, |
| 186 | /// Whether the pointee lives as long as the domain. |
| 187 | own: bool, |
| 188 | /// Whether the pointee can be written. |
| 189 | mutable: bool, |
| 190 | /// Whether the pointer can be zero. |
| 191 | nullable: bool, |
| 192 | /// Whether the pointer is derived from a `reserve` of the current function. |
| 193 | local: bool, |
| 194 | /// Whether the pointer addresses an object that a parameter reaches, whose |
| 195 | /// regions are checked against the signature. |
| 196 | target: bool, |
| 197 | } |
| 198 | |
| 199 | /// Facts about a function value register. |
| 200 | record FnState: Copy { |
| 201 | /// Signature of the function value. |
| 202 | sig: SigRef, |
| 203 | /// Whether the value can be zero. |
| 204 | nullable: bool, |
| 205 | } |
| 206 | |
| 207 | /// Type of a register, fixed at its definition. |
| 208 | union RegState: Copy { |
| 209 | /// Plain data. |
| 210 | Data, |
| 211 | /// A pointer. |
| 212 | Ptr(PtrState), |
| 213 | /// A function value. |
| 214 | Fn(FnState), |
| 215 | /// A heap handle. Zero is a null handle, which `slice.grow` traps on. |
| 216 | Heap(il::HeapType), |
| 217 | } |
| 218 | |
| 219 | /// Owner of a register slot that no function has defined. |
| 220 | constant NO_OWNER: u32 = 0xffffffff; |
| 221 | |
| 222 | /// The definition of a register in the function that is checked. |
| 223 | record Def: Copy { |
| 224 | /// Type of the register. |
| 225 | state: RegState, |
| 226 | /// Block that defines the register. |
| 227 | block: u32, |
| 228 | /// Index of the function that last defined the register. A slot that belongs to another |
| 229 | /// function is free. |
| 230 | owner: u32, |
| 231 | /// Whether the register may hold a pointer that is not reached from the parameter |
| 232 | /// that the result of the function borrows from. Only [`checkBorrow`] sets it. |
| 233 | foreign: bool, |
| 234 | } |
| 235 | |
| 236 | /// Fixed facts about the program under verification. |
| 237 | export record Context { |
| 238 | /// The program. |
| 239 | prog: il::Program, |
| 240 | /// The limits. |
| 241 | config: Config, |
| 242 | /// The checked layout table. |
| 243 | table: layout::Table, |
| 244 | /// Index of each function by name. |
| 245 | fnNames: dict::Dict, |
| 246 | /// Index of each data definition by name. |
| 247 | dataNames: dict::Dict, |
| 248 | /// Number of function definitions supplied by this package. |
| 249 | localFunctions: u32, |
| 250 | /// Number of data initializers supplied by this package. |
| 251 | localData: u32, |
| 252 | } |
| 253 | |
| 254 | /// State of the verification of one function. |
| 255 | record Verifier { |
| 256 | /// Facts about the program. |
| 257 | ctx: Context, |
| 258 | /// Control flow tables of the function. |
| 259 | flow: flow::Flow, |
| 260 | /// Definition of each register number, shared by the functions in turn. |
| 261 | defs: *mut [Def], |
| 262 | /// Whether each register can point only into frame storage. |
| 263 | frame: *mut [bool], |
| 264 | /// Whether each register can point only into target objects. |
| 265 | target: *mut [bool], |
| 266 | /// Foreign provenance of each region, indexed by register and region. |
| 267 | cells: *mut [bool], |
| 268 | /// Number of region facts reserved for each register. |
| 269 | cellWidth: u32, |
| 270 | /// The function that is checked. |
| 271 | func: *il::Fn, |
| 272 | /// Index of the function. |
| 273 | fnIndex: u32, |
| 274 | /// Index of the block that is checked. |
| 275 | block: u32, |
| 276 | /// Index of the instruction that is checked. |
| 277 | instr: u32, |
| 278 | } |
| 279 | |
| 280 | /// Sizes that the per-function tables must cover. |
| 281 | record Sizes: Copy { |
| 282 | /// Number of registers. |
| 283 | registers: u32, |
| 284 | /// Number of blocks. |
| 285 | blocks: u32, |
| 286 | /// Number of control flow edges. |
| 287 | edges: u32, |
| 288 | } |
| 289 | |
| 290 | /// Role of a declared type, which selects the rules for it. |
| 291 | union Role: Copy { |
| 292 | /// Type of a parameter. |
| 293 | Param, |
| 294 | /// Return type. |
| 295 | Return, |
| 296 | } |
| 297 | |
| 298 | //////////////// |
| 299 | // Signatures // |
| 300 | //////////////// |
| 301 | |
| 302 | /// Number of parameters of a signature. |
| 303 | fn sigLen(c: &Context, s: SigRef) -> u32 { |
| 304 | match s { |
| 305 | case SigRef::Table(i) => return c.prog.signatures[i].params.len, |
| 306 | case SigRef::Func(i) => return c.prog.fns[i].params.len, |
| 307 | } |
| 308 | } |
| 309 | |
| 310 | /// Type of parameter `k` of a signature. |
| 311 | fn sigParam(c: &Context, s: SigRef, k: u32) -> il::ValType { |
| 312 | match s { |
| 313 | case SigRef::Table(i) => return c.prog.signatures[i].params[k], |
| 314 | case SigRef::Func(i) => return c.prog.fns[i].params[k].type, |
| 315 | } |
| 316 | } |
| 317 | |
| 318 | /// Return type of a signature. |
| 319 | fn sigRet(c: &Context, s: SigRef) -> il::ValType { |
| 320 | match s { |
| 321 | case SigRef::Table(i) => return c.prog.signatures[i].ret, |
| 322 | case SigRef::Func(i) => return c.prog.fns[i].returnType, |
| 323 | } |
| 324 | } |
| 325 | |
| 326 | /// Borrowed region sources of a signature. |
| 327 | fn sigBorrows(c: &Context, s: SigRef) -> *[il::Borrow] { |
| 328 | match s { |
| 329 | case SigRef::Table(i) => return c.prog.signatures[i].borrows, |
| 330 | case SigRef::Func(i) => return c.prog.fns[i].borrows, |
| 331 | } |
| 332 | } |
| 333 | |
| 334 | /// Whether a signature has borrowed result sources. |
| 335 | fn hasResult(borrows: *[il::Borrow]) -> bool { |
| 336 | for borrow in borrows { |
| 337 | if borrow.target == nil { |
| 338 | return true; |
| 339 | } |
| 340 | } |
| 341 | return false; |
| 342 | } |
| 343 | |
| 344 | /// Whether a borrowed result is written to the first parameter. |
| 345 | fn resultBuffer(ret: il::ValType, borrows: *[il::Borrow]) -> bool { |
| 346 | return ret == il::ValType::Void and hasResult(borrows); |
| 347 | } |
| 348 | |
| 349 | /// Whether two value types are equal. The width of data is not part of its type, and a |
| 350 | /// function value inside a signature is compared by its signature index. |
| 351 | fn typeEq(a: il::ValType, b: il::ValType) -> bool { |
| 352 | match a { |
| 353 | case il::ValType::Void => { |
| 354 | if let case il::ValType::Void = b { |
| 355 | return true; |
| 356 | } |
| 357 | } |
| 358 | case il::ValType::Data(_) => { |
| 359 | if let case il::ValType::Data(_) = b { |
| 360 | return true; |
| 361 | } |
| 362 | } |
| 363 | case il::ValType::Ptr(p) => { |
| 364 | if let case il::ValType::Ptr(q) = b { |
| 365 | return p.layout == q.layout |
| 366 | and p.own == q.own |
| 367 | and p.mutable == q.mutable |
| 368 | and p.nullable == q.nullable; |
| 369 | } |
| 370 | } |
| 371 | case il::ValType::Fn(i) => { |
| 372 | if let case il::ValType::Fn(j) = b { |
| 373 | return i == j; |
| 374 | } |
| 375 | } |
| 376 | case il::ValType::Heap(h) => { |
| 377 | if let case il::ValType::Heap(g) = b { |
| 378 | return h == g; |
| 379 | } |
| 380 | } |
| 381 | } |
| 382 | return false; |
| 383 | } |
| 384 | |
| 385 | /// Whether two signatures are equal: the same parameters and result type. |
| 386 | export fn sigEq(c: &Context, a: SigRef, b: SigRef) -> bool { |
| 387 | let n = sigLen(c, a); |
| 388 | if n <> sigLen(c, b) |
| 389 | or not typeEq(sigRet(c, a), sigRet(c, b)) |
| 390 | or not il::sameBorrows(sigBorrows(c, a), sigBorrows(c, b)) |
| 391 | { |
| 392 | return false; |
| 393 | } |
| 394 | for k in 0 .. n { |
| 395 | if not typeEq(sigParam(c, a, k), sigParam(c, b, k)) { |
| 396 | return false; |
| 397 | } |
| 398 | } |
| 399 | return true; |
| 400 | } |
| 401 | |
| 402 | //////////////////////// |
| 403 | // Declarations pass // |
| 404 | //////////////////////// |
| 405 | |
| 406 | /// Build the error for a violation at function `index`. |
| 407 | fn failFn(index: u32, rule: Rule) -> Error { |
| 408 | return Error { rule, place: Place::Fn(index) }; |
| 409 | } |
| 410 | |
| 411 | /// Check a declared type: a parameter or result of a function or signature, or a block |
| 412 | /// parameter. Pointers to objects with non-owning slots must not own their pointee, and a |
| 413 | /// function returns only owning pointers, because a non-owning pointer can point into |
| 414 | /// the frame that the return discards. |
| 415 | fn checkType(c: &Context, t: il::ValType, role: Role, place: Place) throws (Error) { |
| 416 | match t { |
| 417 | case il::ValType::Void => { |
| 418 | if let case Role::Param = role { |
| 419 | throw Error { rule: Rule::Type, place }; |
| 420 | } |
| 421 | } |
| 422 | case il::ValType::Ptr(p) => { |
| 423 | // A result that holds references needs sources for its regions. |
| 424 | if let case Role::Return = role { |
| 425 | if not p.own or c.table.layouts[p.layout].regions > 0 { |
| 426 | throw Error { rule: Rule::Return, place }; |
| 427 | } |
| 428 | } |
| 429 | } |
| 430 | else => {} |
| 431 | } |
| 432 | } |
| 433 | |
| 434 | /// Check the result type of a signature, and that each region of a borrowed result |
| 435 | /// or target has a source of the right kind. |
| 436 | fn checkResult(c: &Context, s: SigRef, place: Place) throws (Error) { |
| 437 | let borrows = sigBorrows(c, s); |
| 438 | let ret = sigRet(c, s); |
| 439 | let results = hasResult(borrows); |
| 440 | let buffered = results and ret == il::ValType::Void; |
| 441 | let params = sigLen(c, s); |
| 442 | if not results { |
| 443 | try checkType(c, ret, Role::Return, place); |
| 444 | } |
| 445 | let mut count: u32 = 0; |
| 446 | if buffered { |
| 447 | if params == 0 { |
| 448 | throw Error { rule: Rule::Return, place }; |
| 449 | } |
| 450 | let case il::ValType::Ptr(b) = sigParam(c, s, 0) |
| 451 | else throw Error { rule: Rule::Return, place }; |
| 452 | if b.own or not b.mutable or b.nullable { |
| 453 | throw Error { rule: Rule::Return, place }; |
| 454 | } |
| 455 | set count = c.table.layouts[b.layout].regions; |
| 456 | } else if results { |
| 457 | let case il::ValType::Ptr(r) = ret else throw Error { rule: Rule::Return, place }; |
| 458 | set count = (0 if r.own else 1) + c.table.layouts[r.layout].regions; |
| 459 | } |
| 460 | if results and count == 0 { |
| 461 | throw Error { rule: Rule::Return, place }; |
| 462 | } |
| 463 | for borrow in borrows { |
| 464 | let mut limit = count; |
| 465 | if let t = borrow.target { |
| 466 | if t >= params or (buffered and t == 0) { |
| 467 | throw Error { rule: Rule::Return, place }; |
| 468 | } |
| 469 | let case il::ValType::Ptr(p) = sigParam(c, s, t) |
| 470 | else throw Error { rule: Rule::Return, place }; |
| 471 | set limit = c.table.layouts[p.layout].regions; |
| 472 | } |
| 473 | if borrow.result >= limit |
| 474 | or borrow.param >= params |
| 475 | or (buffered and borrow.param == 0) |
| 476 | { |
| 477 | throw Error { rule: Rule::Return, place }; |
| 478 | } |
| 479 | let case il::ValType::Ptr(p) = sigParam(c, s, borrow.param) |
| 480 | else throw Error { rule: Rule::Return, place }; |
| 481 | if let source = borrow.source; source >= c.table.layouts[p.layout].regions { |
| 482 | throw Error { rule: Rule::Return, place }; |
| 483 | } |
| 484 | } |
| 485 | for i in 0 .. count { |
| 486 | let mut found = false; |
| 487 | for borrow in borrows { |
| 488 | if borrow.target == nil and borrow.result == i { |
| 489 | set found = true; |
| 490 | break; |
| 491 | } |
| 492 | } |
| 493 | if not found { |
| 494 | throw Error { rule: Rule::Return, place }; |
| 495 | } |
| 496 | } |
| 497 | } |
| 498 | |
| 499 | /// Check the signature table. |
| 500 | fn checkSignatures(c: &Context) throws (Error) { |
| 501 | for i in 0 .. c.prog.signatures.len { |
| 502 | let sig = c.prog.signatures[i]; |
| 503 | if sig.params.len > c.config.params { |
| 504 | throw Error { rule: Rule::Limit, place: Place::Signature(i) }; |
| 505 | } |
| 506 | for param in sig.params { |
| 507 | try checkType(c, param, Role::Param, Place::Signature(i)); |
| 508 | } |
| 509 | try checkResult(c, SigRef::Table(i), Place::Signature(i)); |
| 510 | } |
| 511 | } |
| 512 | |
| 513 | /// Check the trait table. A method adds its receiver to the parameters of its signature, |
| 514 | /// at a position within them. |
| 515 | fn checkTraits(c: &Context) throws (Error) { |
| 516 | for i in 0 .. c.prog.traits.len { |
| 517 | for method in c.prog.traits[i].methods { |
| 518 | let params = c.prog.signatures[method.sig].params.len; |
| 519 | if params >= c.config.params { |
| 520 | throw Error { rule: Rule::Limit, place: Place::Trait(i) }; |
| 521 | } |
| 522 | if method.receiver > params { |
| 523 | throw Error { rule: Rule::Layout, place: Place::Trait(i) }; |
| 524 | } |
| 525 | } |
| 526 | } |
| 527 | } |
| 528 | |
| 529 | /// Check the declarations and the shape of every function, and measure the largest. |
| 530 | /// Registers are below the limit, every block ends with exactly one terminator, and |
| 531 | /// branch targets are blocks of the function. |
| 532 | fn measure(c: &Context) -> Sizes throws (Error) { |
| 533 | let mut sizes = Sizes { registers: 0, blocks: 0, edges: 0 }; |
| 534 | for fi in 0 .. c.prog.fns.len { |
| 535 | let func = c.prog.fns[fi]; |
| 536 | let mut regs: u32 = 0; |
| 537 | let mut edges: u32 = 0; |
| 538 | if func.params.len > c.config.params { |
| 539 | throw failFn(fi, Rule::Limit); |
| 540 | } |
| 541 | for param in func.params { |
| 542 | try checkType(c, param.type, Role::Param, Place::Fn(fi)); |
| 543 | set regs = try reserveReg(c, regs, param.value, Place::Fn(fi)); |
| 544 | } |
| 545 | try checkResult(c, SigRef::Func(fi), Place::Fn(fi)); |
| 546 | if func.isExtern { |
| 547 | if func.blocks.len > 0 { |
| 548 | throw failFn(fi, Rule::Structure); |
| 549 | } |
| 550 | continue; |
| 551 | } |
| 552 | if func.blocks.len == 0 { |
| 553 | throw failFn(fi, Rule::Structure); |
| 554 | } |
| 555 | if func.blocks.len > c.config.blocks { |
| 556 | throw failFn(fi, Rule::Limit); |
| 557 | } |
| 558 | for b in 0 .. func.blocks.len { |
| 559 | let block = func.blocks[b]; |
| 560 | let at = Place::Instr { func: fi, block: b, instr: 0 }; |
| 561 | if block.instrs.len == 0 or (b == 0 and block.params.len > 0) { |
| 562 | throw Error { rule: Rule::Structure, place: at }; |
| 563 | } |
| 564 | if block.params.len > c.config.params { |
| 565 | throw Error { rule: Rule::Limit, place: at }; |
| 566 | } |
| 567 | for param in block.params { |
| 568 | try checkType(c, param.type, Role::Param, at); |
| 569 | set regs = try reserveReg(c, regs, param.value, at); |
| 570 | } |
| 571 | for i in 0 .. block.instrs.len { |
| 572 | let place = Place::Instr { func: fi, block: b, instr: i }; |
| 573 | if il::isTerminator(&block.instrs[i]) <> (i == block.instrs.len - 1) { |
| 574 | throw Error { rule: Rule::Structure, place }; |
| 575 | } |
| 576 | if let reg = il::instrDst(&block.instrs[i]) { |
| 577 | set regs = try reserveReg(c, regs, reg, place); |
| 578 | } |
| 579 | } |
| 580 | for k in 0 .. il::successorCount(func, b) { |
| 581 | if il::successor(func, b, k) >= func.blocks.len { |
| 582 | throw Error { rule: Rule::Structure, place: at }; |
| 583 | } |
| 584 | } |
| 585 | set edges += il::successorCount(func, b); |
| 586 | } |
| 587 | set sizes.registers = regs if regs > sizes.registers else sizes.registers; |
| 588 | set sizes.blocks = func.blocks.len if func.blocks.len > sizes.blocks else sizes.blocks; |
| 589 | set sizes.edges = edges if edges > sizes.edges else sizes.edges; |
| 590 | } |
| 591 | return sizes; |
| 592 | } |
| 593 | |
| 594 | /// Check that register `r` is below the limit. Return the number of registers needed to |
| 595 | /// hold it, given the `count` needed so far. |
| 596 | fn reserveReg(c: &Context, count: u32, r: il::Reg, place: Place) -> u32 throws (Error) { |
| 597 | if r.n >= c.config.registers { |
| 598 | throw Error { rule: Rule::Limit, place }; |
| 599 | } |
| 600 | if r.n >= count { |
| 601 | return r.n + 1; |
| 602 | } |
| 603 | return count; |
| 604 | } |
| 605 | |
| 606 | ///////////////////// |
| 607 | // Registers // |
| 608 | ///////////////////// |
| 609 | |
| 610 | /// Build the error for a rule violation at the current instruction. |
| 611 | fn fail(v: &Verifier, rule: Rule) -> Error { |
| 612 | return Error { |
| 613 | rule, place: Place::Instr { func: v.fnIndex, block: v.block, instr: v.instr } |
| 614 | }; |
| 615 | } |
| 616 | |
| 617 | /// The register state of a value of a declared type. |
| 618 | fn declared(t: il::ValType) -> RegState { |
| 619 | match t { |
| 620 | case il::ValType::Void, il::ValType::Data(_) => return RegState::Data, |
| 621 | case il::ValType::Ptr(p) => |
| 622 | return RegState::Ptr(PtrState { |
| 623 | layout: p.layout, |
| 624 | offset: 0, |
| 625 | own: p.own, |
| 626 | mutable: p.mutable, |
| 627 | nullable: p.nullable, |
| 628 | local: false, |
| 629 | target: false, |
| 630 | }), |
| 631 | case il::ValType::Fn(sig) => |
| 632 | return RegState::Fn(FnState { |
| 633 | sig: SigRef::Table(sig), nullable: false |
| 634 | }), |
| 635 | case il::ValType::Heap(h) => return RegState::Heap(h), |
| 636 | } |
| 637 | } |
| 638 | |
| 639 | /// The rights of a heap handle operand. |
| 640 | fn heapOperand(v: &Verifier, val: il::Val) -> il::HeapType throws (Error) { |
| 641 | let case RegState::Heap(h) = try operand(v, val) else { |
| 642 | throw fail(v, Rule::Type); |
| 643 | }; |
| 644 | return h; |
| 645 | } |
| 646 | |
| 647 | /// Define register `r` at the current block with state `s`. A register has one definition. |
| 648 | fn define(v: &mut Verifier, r: il::Reg, s: RegState) throws (Error) { |
| 649 | if r.n >= v.defs.len or v.defs[r.n].owner == v.fnIndex { |
| 650 | throw fail(v, Rule::Register); |
| 651 | } |
| 652 | set v.defs[r.n] = Def { |
| 653 | state: s, block: v.block, owner: v.fnIndex, foreign: false |
| 654 | }; |
| 655 | } |
| 656 | |
| 657 | /// The state of a register at its use. Its definition must dominate the use. |
| 658 | fn state(v: &Verifier, r: il::Reg) -> RegState throws (Error) { |
| 659 | if r.n >= v.defs.len |
| 660 | or v.defs[r.n].owner <> v.fnIndex |
| 661 | or not flow::dominates(&v.flow, v.defs[r.n].block, v.block) |
| 662 | { |
| 663 | throw fail(v, Rule::Register); |
| 664 | } |
| 665 | return v.defs[r.n].state; |
| 666 | } |
| 667 | |
| 668 | /// The state of a value, which must be defined. An address of a symbol is data. A function |
| 669 | /// symbol is also a function value. A caller that needs data only ignores the state. |
| 670 | fn operand(v: &Verifier, val: il::Val) -> RegState throws (Error) { |
| 671 | match val { |
| 672 | case il::Val::Reg(r) => return try state(v, r), |
| 673 | case il::Val::Imm(_), il::Val::Undef => return RegState::Data, |
| 674 | case il::Val::DataSym(name) => { |
| 675 | if dict::get(&v.ctx.dataNames, name) == nil { |
| 676 | throw fail(v, Rule::Symbol); |
| 677 | } |
| 678 | return RegState::Data; |
| 679 | } |
| 680 | case il::Val::FnAddr(name) => { |
| 681 | let index = dict::get(&v.ctx.fnNames, name) else { |
| 682 | throw fail(v, Rule::Symbol); |
| 683 | }; |
| 684 | if v.ctx.prog.fns[index as u32].isExtern and index as u32 < v.ctx.localFunctions { |
| 685 | throw fail(v, Rule::Symbol); |
| 686 | } |
| 687 | return RegState::Fn(FnState { sig: SigRef::Func(index as u32), nullable: false }); |
| 688 | } |
| 689 | } |
| 690 | } |
| 691 | |
| 692 | /// Whether a value is the immediate zero. |
| 693 | fn isZero(val: il::Val) -> bool { |
| 694 | if let case il::Val::Imm(n) = val { |
| 695 | return n == 0; |
| 696 | } |
| 697 | return false; |
| 698 | } |
| 699 | |
| 700 | /// The state of a pointer register that can be dereferenced. |
| 701 | fn accessible(v: &Verifier, r: il::Reg) -> PtrState throws (Error) { |
| 702 | let case RegState::Ptr(p) = try state(v, r) else { |
| 703 | throw fail(v, Rule::Type); |
| 704 | }; |
| 705 | if p.nullable { |
| 706 | throw fail(v, Rule::Null); |
| 707 | } |
| 708 | return p; |
| 709 | } |
| 710 | |
| 711 | /// The state of a pointer register that can be dereferenced and written. |
| 712 | fn writable(v: &Verifier, r: il::Reg) -> PtrState throws (Error) { |
| 713 | let p = try accessible(v, r); |
| 714 | if not p.mutable { |
| 715 | throw fail(v, Rule::Mutability); |
| 716 | } |
| 717 | return p; |
| 718 | } |
| 719 | |
| 720 | /// Check that `width` bytes at `delta` bytes from the pointer are inside its layout. |
| 721 | /// Return their offset in the layout. A region can end at the end of the layout. |
| 722 | fn extent(v: &Verifier, p: PtrState, delta: i64, width: u64) -> u64 throws (Error) { |
| 723 | let o = p.offset as i64 + delta; |
| 724 | if o < 0 or o as u64 + width > layout::size(&v.ctx.table, p.layout) { |
| 725 | throw fail(v, Rule::Bounds); |
| 726 | } |
| 727 | return o as u64; |
| 728 | } |
| 729 | |
| 730 | /// Check that a pointer of class `own` and mutability `mutable` may be used where the |
| 731 | /// pointer type `t` is declared. |
| 732 | fn rights(v: &Verifier, t: il::PtrType, own: bool, mutable: bool) throws (Error) { |
| 733 | if t.own and not own { |
| 734 | throw fail(v, Rule::Class); |
| 735 | } |
| 736 | if t.mutable and not mutable { |
| 737 | throw fail(v, Rule::Mutability); |
| 738 | } |
| 739 | } |
| 740 | |
| 741 | /// Check that a pointer fits a declared pointer type. |
| 742 | fn fits(v: &Verifier, p: PtrState, t: il::PtrType) throws (Error) { |
| 743 | if p.nullable and not t.nullable { |
| 744 | throw fail(v, Rule::Null); |
| 745 | } |
| 746 | try rights(v, t, p.own, p.mutable); |
| 747 | // A read-only pointer can view a slot with fewer rights than the slot has. |
| 748 | let o = p.offset as u64; |
| 749 | let visible = layout::view(&v.ctx.table, p.layout, o, t.layout) |
| 750 | if t.mutable |
| 751 | else layout::holds(&v.ctx.table, p.layout, o, t.layout); |
| 752 | if not visible { |
| 753 | throw fail(v, Rule::View); |
| 754 | } |
| 755 | } |
| 756 | |
| 757 | /// Check that a value can be used where a value of type `t` is declared. |
| 758 | fn assign(v: &Verifier, val: il::Val, t: il::ValType) throws (Error) { |
| 759 | try assignState(v, val, try operand(v, val), t); |
| 760 | } |
| 761 | |
| 762 | /// Check a value against its declared type, with the facts that hold at its use. |
| 763 | fn assignState(v: &Verifier, val: il::Val, s: RegState, t: il::ValType) throws (Error) { |
| 764 | match t { |
| 765 | case il::ValType::Void => throw fail(v, Rule::Type), |
| 766 | case il::ValType::Data(_) => {} |
| 767 | case il::ValType::Ptr(want) => { |
| 768 | if let case RegState::Ptr(p) = s { |
| 769 | try fits(v, p, want); |
| 770 | } else if isZero(val) { |
| 771 | if not want.nullable { |
| 772 | throw fail(v, Rule::Null); |
| 773 | } |
| 774 | } else { |
| 775 | throw fail(v, Rule::Type); |
| 776 | } |
| 777 | } |
| 778 | case il::ValType::Fn(sig) => { |
| 779 | let case RegState::Fn(f) = s else { |
| 780 | throw fail(v, Rule::Type); |
| 781 | }; |
| 782 | if f.nullable { |
| 783 | throw fail(v, Rule::Null); |
| 784 | } |
| 785 | if not sigEq(&v.ctx, f.sig, SigRef::Table(sig)) { |
| 786 | throw fail(v, Rule::Type); |
| 787 | } |
| 788 | } |
| 789 | case il::ValType::Heap(want) => { |
| 790 | // The zero handle stands for no heap, like the zero in a heap slot. Using it traps. |
| 791 | if isZero(val) { |
| 792 | return; |
| 793 | } |
| 794 | let case RegState::Heap(h) = s else { |
| 795 | throw fail(v, Rule::Type); |
| 796 | }; |
| 797 | if not layout::heapFits(h, want) { |
| 798 | throw fail(v, Rule::Type); |
| 799 | } |
| 800 | } |
| 801 | } |
| 802 | } |
| 803 | |
| 804 | /// Check that `width` bytes at `offset` from a writable pointer hold no slot. |
| 805 | fn writePlain(v: &Verifier, r: il::Reg, offset: i64, width: u64) throws (Error) { |
| 806 | let p = try writable(v, r); |
| 807 | let o = try extent(v, p, offset, width); |
| 808 | if not layout::plain(&v.ctx.table, p.layout, o, o + width) { |
| 809 | throw fail(v, Rule::Slot); |
| 810 | } |
| 811 | } |
| 812 | |
| 813 | /// Check that a pointer addresses `count` consecutive objects of layout `e`. |
| 814 | fn arrayOf(v: &Verifier, p: PtrState, e: u32, count: u32) throws (Error) { |
| 815 | let t = &v.ctx.table; |
| 816 | let o = try extent(v, p, 0, layout::size(t, e) * count as u64); |
| 817 | if not layout::arrayView(t, p.layout, o, e, count) { |
| 818 | throw fail(v, Rule::View); |
| 819 | } |
| 820 | } |
| 821 | |
| 822 | /// The slice slot that a pointer addresses. |
| 823 | fn sliceAt(v: &Verifier, p: PtrState) -> il::PtrType throws (Error) { |
| 824 | let o = try extent(v, p, 0, 0); |
| 825 | let case il::SlotKind::Slice(slot) = layout::slotAt(&v.ctx.table, p.layout, o) else { |
| 826 | throw fail(v, Rule::Slot); |
| 827 | }; |
| 828 | return slot; |
| 829 | } |
| 830 | |
| 831 | /// The slice slot that a pointer addresses. A plain view must have the same |
| 832 | /// element size as the slot. |
| 833 | fn sliceSlot(v: &Verifier, p: PtrState, e: u32) -> il::PtrType throws (Error) { |
| 834 | let t = &v.ctx.table; |
| 835 | let slot = try sliceAt(v, p); |
| 836 | let same = slot.layout == e or (layout::isPlain(t, slot.layout) |
| 837 | and layout::isPlain(t, e) |
| 838 | and layout::size(t, slot.layout) == layout::size(t, e)); |
| 839 | if not same { |
| 840 | throw fail(v, Rule::View); |
| 841 | } |
| 842 | return slot; |
| 843 | } |
| 844 | |
| 845 | /// Check that a slice provides the alignment required by its element view. |
| 846 | fn sliceSource(v: &Verifier, src: PtrState, e: u32) -> il::PtrType throws (Error) { |
| 847 | let slot = try sliceSlot(v, src, e); |
| 848 | if layout::alignment(&v.ctx.table, slot.layout) < layout::alignment(&v.ctx.table, e) { |
| 849 | throw fail(v, Rule::View); |
| 850 | } |
| 851 | return slot; |
| 852 | } |
| 853 | |
| 854 | /// Require plain one-byte elements, with write permission for a store. |
| 855 | fn byteSlice(v: &Verifier, slice: il::Reg, writing: bool) throws (Error) { |
| 856 | let slot = try sliceAt(v, try accessible(v, slice)); |
| 857 | let t = &v.ctx.table; |
| 858 | if not layout::isPlain(t, slot.layout) or layout::size(t, slot.layout) <> 1 { |
| 859 | throw fail(v, Rule::View); |
| 860 | } |
| 861 | if writing and not slot.mutable { |
| 862 | throw fail(v, Rule::Mutability); |
| 863 | } |
| 864 | } |
| 865 | |
| 866 | /// Whether a pointer addresses an object that can hold non-owning pointers: an |
| 867 | /// object of the current frame, or a target object of a parameter. |
| 868 | fn holds(p: PtrState) -> bool { |
| 869 | return p.local or p.target; |
| 870 | } |
| 871 | |
| 872 | /// Require an argument to address an object that can hold non-owning pointers. |
| 873 | fn holdingArgument(v: &Verifier, val: il::Val) throws (Error) { |
| 874 | let case il::Val::Reg(r) = val else throw fail(v, Rule::Class); |
| 875 | let case RegState::Ptr(p) = v.defs[r.n].state else throw fail(v, Rule::Class); |
| 876 | if not holds(p) { |
| 877 | throw fail(v, Rule::Class); |
| 878 | } |
| 879 | } |
| 880 | |
| 881 | /// Whether objects of layout `l` hold references, directly or through owning |
| 882 | /// pointers, so that they have regions. |
| 883 | fn hasRegions(v: &Verifier, l: u32) -> bool { |
| 884 | return v.ctx.table.layouts[l].regions > 0; |
| 885 | } |
| 886 | |
| 887 | /// A slice slot that the slice instructions write. |
| 888 | record SliceDest: Copy { |
| 889 | /// Type of the slot. |
| 890 | slot: il::PtrType, |
| 891 | /// Whether the slot is in an object that can hold non-owning pointers. |
| 892 | holds: bool, |
| 893 | } |
| 894 | |
| 895 | /// Check a writable slice slot. The element view must provide the alignment |
| 896 | /// required by the slot. |
| 897 | fn sliceDest(v: &Verifier, dst: il::Reg, e: u32) -> SliceDest throws (Error) { |
| 898 | let d = try writable(v, dst); |
| 899 | let slot = try sliceSlot(v, d, e); |
| 900 | if layout::alignment(&v.ctx.table, e) < layout::alignment(&v.ctx.table, slot.layout) { |
| 901 | throw fail(v, Rule::View); |
| 902 | } |
| 903 | return SliceDest { slot, holds: holds(d) }; |
| 904 | } |
| 905 | |
| 906 | /// Check that a slice slot can receive a slice over memory of class `own` and |
| 907 | /// mutability `mutable`. A slot that does not own its pointee keeps it only in the frame. |
| 908 | fn sliceFrom(v: &Verifier, d: SliceDest, own: bool, mutable: bool) throws (Error) { |
| 909 | if not d.slot.own and not own and not d.holds { |
| 910 | throw fail(v, Rule::Class); |
| 911 | } |
| 912 | if own and hasRegions(v, d.slot.layout) and not d.holds { |
| 913 | throw fail(v, Rule::Class); |
| 914 | } |
| 915 | try rights(v, d.slot, own, mutable); |
| 916 | } |
| 917 | |
| 918 | /////////////////// |
| 919 | // Trait objects // |
| 920 | /////////////////// |
| 921 | |
| 922 | /// The trait object slot that a pointer addresses. |
| 923 | fn objectSlot(v: &Verifier, p: PtrState) -> il::ObjectType throws (Error) { |
| 924 | let o = try extent(v, p, 0, 0); |
| 925 | let case il::SlotKind::Trait(object) = layout::slotAt(&v.ctx.table, p.layout, o) else { |
| 926 | throw fail(v, Rule::Slot); |
| 927 | }; |
| 928 | return object; |
| 929 | } |
| 930 | |
| 931 | /// Whether the function type `concrete` is the type of method `m` for a receiver `r`: the |
| 932 | /// signature of the method with a receiver inserted that `r` views, with the rights that |
| 933 | /// the method needs. |
| 934 | fn implements(v: &Verifier, concrete: u32, m: il::Method, r: PtrState) -> bool { |
| 935 | let full = v.ctx.prog.signatures[concrete]; |
| 936 | let erased = v.ctx.prog.signatures[m.sig]; |
| 937 | // A method result does not borrow, so a caller through a trait object passes no |
| 938 | // buffer of its frame. |
| 939 | if full.params.len <> erased.params.len + 1 |
| 940 | or not typeEq(full.ret, erased.ret) |
| 941 | or full.borrows.len > 0 |
| 942 | { |
| 943 | return false; |
| 944 | } |
| 945 | for k in 0 .. full.params.len { |
| 946 | if k == m.receiver { |
| 947 | let case il::ValType::Ptr(p) = full.params[k] else { |
| 948 | return false; |
| 949 | }; |
| 950 | if p.own <> m.own or p.mutable <> m.mutable or p.nullable { |
| 951 | return false; |
| 952 | } |
| 953 | if not layout::view(&v.ctx.table, r.layout, r.offset as u64, p.layout) { |
| 954 | return false; |
| 955 | } |
| 956 | } else { |
| 957 | let j = k if k < m.receiver else k - 1; |
| 958 | if not typeEq(full.params[k], erased.params[j]) { |
| 959 | return false; |
| 960 | } |
| 961 | } |
| 962 | } |
| 963 | return true; |
| 964 | } |
| 965 | |
| 966 | /// Check that `table` is a method table of trait `iface` for the receiver `r`: read-only |
| 967 | /// data that holds one function per method, each of the method's type for the receiver. |
| 968 | fn checkTable(v: &Verifier, table: il::Val, iface: u32, r: PtrState) throws (Error) { |
| 969 | let case il::Val::DataSym(name) = table else { |
| 970 | throw fail(v, Rule::Type); |
| 971 | }; |
| 972 | let index = dict::get(&v.ctx.dataNames, name) else { |
| 973 | throw fail(v, Rule::Symbol); |
| 974 | }; |
| 975 | let item = v.ctx.prog.data[index as u32]; |
| 976 | if not item.readOnly { |
| 977 | throw fail(v, Rule::Mutability); |
| 978 | } |
| 979 | let methods = v.ctx.prog.traits[iface].methods; |
| 980 | let slots = v.ctx.prog.layouts[item.layout].slots; |
| 981 | // The data checks match each function of the initializer with its slot, so a table |
| 982 | // with one function per slot holds no zero. |
| 983 | if slots.len <> methods.len or item.values.len <> methods.len { |
| 984 | throw fail(v, Rule::Type); |
| 985 | } |
| 986 | for k in 0 .. methods.len { |
| 987 | let case il::SlotKind::Fn(sig) = slots[k].kind else { |
| 988 | throw fail(v, Rule::Type); |
| 989 | }; |
| 990 | let case il::DataItem::Fn(_) = item.values[k].item else { |
| 991 | throw fail(v, Rule::Type); |
| 992 | }; |
| 993 | if slots[k].offset <> k * layout::WORD as u32 or item.values[k].count <> 1 { |
| 994 | throw fail(v, Rule::Type); |
| 995 | } |
| 996 | if not implements(v, sig, methods[k], r) { |
| 997 | throw fail(v, Rule::Type); |
| 998 | } |
| 999 | } |
| 1000 | } |
| 1001 | |
| 1002 | /// Check a trait object construction. The slot keeps the receiver, so the receiver has the |
| 1003 | /// class and rights of the slot, as for `store.ptr`. |
| 1004 | fn checkTraitNew(v: &Verifier, dst: il::Reg, recv: il::Reg, table: il::Val) throws (Error) { |
| 1005 | let d = try writable(v, dst); |
| 1006 | let object = try objectSlot(v, d); |
| 1007 | let r = try accessible(v, recv); |
| 1008 | if object.own and not r.own { |
| 1009 | throw fail(v, Rule::Class); |
| 1010 | } |
| 1011 | if not object.own and not r.own and not holds(d) { |
| 1012 | throw fail(v, Rule::Class); |
| 1013 | } |
| 1014 | if object.mutable and not r.mutable { |
| 1015 | throw fail(v, Rule::Mutability); |
| 1016 | } |
| 1017 | try checkTable(v, table, object.iface, r); |
| 1018 | } |
| 1019 | |
| 1020 | /// Check a copy of a trait object into a slot with the same or fewer rights. A slot that |
| 1021 | /// does not own its receiver keeps a borrowed one only in the frame. |
| 1022 | fn checkTraitCopy(v: &Verifier, dst: il::Reg, src: il::Reg) throws (Error) { |
| 1023 | let d = try writable(v, dst); |
| 1024 | let to = try objectSlot(v, d); |
| 1025 | let from = try objectSlot(v, try accessible(v, src)); |
| 1026 | if to.iface <> from.iface { |
| 1027 | throw fail(v, Rule::View); |
| 1028 | } |
| 1029 | if to.own and not from.own { |
| 1030 | throw fail(v, Rule::Class); |
| 1031 | } |
| 1032 | if not to.own and not from.own and not holds(d) { |
| 1033 | throw fail(v, Rule::Class); |
| 1034 | } |
| 1035 | if to.mutable and not from.mutable { |
| 1036 | throw fail(v, Rule::Mutability); |
| 1037 | } |
| 1038 | } |
| 1039 | |
| 1040 | /// Check a method call through a trait object, and define its result. The method needs |
| 1041 | /// no more rights than the object has, and the receiver position holds no argument. |
| 1042 | fn checkTraitCall( |
| 1043 | v: &mut Verifier, |
| 1044 | retTy: il::ValType, |
| 1045 | dst: ?il::Reg, |
| 1046 | obj: il::Reg, |
| 1047 | method: u32, |
| 1048 | receiver: u32, |
| 1049 | args: il::ArgRange |
| 1050 | ) throws (Error) { |
| 1051 | let object = try objectSlot(v, try accessible(v, obj)); |
| 1052 | let methods = v.ctx.prog.traits[object.iface].methods; |
| 1053 | if method >= methods.len { |
| 1054 | throw fail(v, Rule::Call); |
| 1055 | } |
| 1056 | let m = methods[method]; |
| 1057 | if m.own and not object.own { |
| 1058 | throw fail(v, Rule::Class); |
| 1059 | } |
| 1060 | if m.mutable and not object.mutable { |
| 1061 | throw fail(v, Rule::Mutability); |
| 1062 | } |
| 1063 | let erased = SigRef::Table(m.sig); |
| 1064 | if receiver <> m.receiver or not typeEq(retTy, sigRet(&v.ctx, erased)) { |
| 1065 | throw fail(v, Rule::Call); |
| 1066 | } |
| 1067 | let func = v.func; |
| 1068 | let values = il::argVals(func, args); |
| 1069 | if values.len <> sigLen(&v.ctx, erased) + 1 { |
| 1070 | throw fail(v, Rule::Arity); |
| 1071 | } |
| 1072 | for k in 0 .. values.len { |
| 1073 | if k == receiver { |
| 1074 | let case il::Val::Undef = values[k] else { |
| 1075 | throw fail(v, Rule::Call); |
| 1076 | }; |
| 1077 | } else { |
| 1078 | let j = k if k < receiver else k - 1; |
| 1079 | try assign(v, values[k], sigParam(&v.ctx, erased, j)); |
| 1080 | } |
| 1081 | } |
| 1082 | if let reg = dst { |
| 1083 | if let case il::ValType::Void = retTy { |
| 1084 | throw fail(v, Rule::Call); |
| 1085 | } |
| 1086 | try define(v, reg, declared(retTy)); |
| 1087 | } |
| 1088 | } |
| 1089 | |
| 1090 | /////////////////// |
| 1091 | // Instructions // |
| 1092 | /////////////////// |
| 1093 | |
| 1094 | /// Check a store of a pointer or function value into a slot. |
| 1095 | fn checkStorePtr(v: &Verifier, val: il::Val, dst: il::Reg, offset: i32) throws (Error) { |
| 1096 | let s = try operand(v, val); |
| 1097 | let p = try writable(v, dst); |
| 1098 | let o = try extent(v, p, offset as i64, 0); |
| 1099 | let slot = layout::slotAt(&v.ctx.table, p.layout, o) else { |
| 1100 | throw fail(v, Rule::Slot); |
| 1101 | }; |
| 1102 | match slot { |
| 1103 | case il::SlotKind::Ptr(want) => { |
| 1104 | if let case RegState::Ptr(q) = s { |
| 1105 | // A slot that does not own its pointee is written only with owning |
| 1106 | // pointers, or in an object of the current frame. |
| 1107 | if not want.own and not q.own and not holds(p) { |
| 1108 | throw fail(v, Rule::Class); |
| 1109 | } |
| 1110 | // An owning pointer to objects with references carries their regions. |
| 1111 | if q.own and hasRegions(v, want.layout) and not holds(p) { |
| 1112 | throw fail(v, Rule::Class); |
| 1113 | } |
| 1114 | try fits(v, q, want); |
| 1115 | } else if not isZero(val) { |
| 1116 | throw fail(v, Rule::Type); |
| 1117 | } |
| 1118 | } |
| 1119 | case il::SlotKind::Fn(sig) => { |
| 1120 | if let case RegState::Fn(f) = s { |
| 1121 | if not sigEq(&v.ctx, f.sig, SigRef::Table(sig)) { |
| 1122 | throw fail(v, Rule::Type); |
| 1123 | } |
| 1124 | } else if not isZero(val) { |
| 1125 | throw fail(v, Rule::Type); |
| 1126 | } |
| 1127 | } |
| 1128 | case il::SlotKind::Heap(want) => try assignState(v, val, s, il::ValType::Heap(want)), |
| 1129 | else => throw fail(v, Rule::Slot), |
| 1130 | } |
| 1131 | } |
| 1132 | |
| 1133 | /// Check that a writable pointer `d` can receive an object of layout `l`, which a copy |
| 1134 | /// writes. The destination is a plain region, which takes any bytes, or holds such an |
| 1135 | /// object, and then a copy of borrowed slots stays in the frame. Both regions are aligned |
| 1136 | /// for `l`. |
| 1137 | fn checkCopyTo(v: &Verifier, d: PtrState, l: u32) throws (Error) { |
| 1138 | let t = &v.ctx.table; |
| 1139 | let size = layout::size(t, l); |
| 1140 | let od = try extent(v, d, 0, size); |
| 1141 | if layout::plainRegion(t, d.layout, od, size, layout::alignment(t, l)) { |
| 1142 | return; |
| 1143 | } |
| 1144 | if not layout::view(t, d.layout, od, l) { |
| 1145 | throw fail(v, Rule::View); |
| 1146 | } |
| 1147 | if hasRegions(v, l) and not holds(d) { |
| 1148 | throw fail(v, Rule::Class); |
| 1149 | } |
| 1150 | } |
| 1151 | |
| 1152 | /// Check that a pointer `s` addresses an object of layout `l`, which a copy reads, also |
| 1153 | /// through a slot with fewer rights. |
| 1154 | fn checkCopyFrom(v: &Verifier, s: PtrState, l: u32) throws (Error) { |
| 1155 | let t = &v.ctx.table; |
| 1156 | let os = try extent(v, s, 0, layout::size(t, l)); |
| 1157 | if not layout::holds(t, s.layout, os, l) { |
| 1158 | throw fail(v, Rule::View); |
| 1159 | } |
| 1160 | } |
| 1161 | |
| 1162 | /// Check a copy of an object of layout `l`. The source holds such an object, and the |
| 1163 | /// destination can receive one. |
| 1164 | fn checkBlit(v: &Verifier, dst: il::Reg, src: il::Reg, l: u32) throws (Error) { |
| 1165 | let d = try writable(v, dst); |
| 1166 | try checkCopyFrom(v, try accessible(v, src), l); |
| 1167 | try checkCopyTo(v, d, l); |
| 1168 | } |
| 1169 | |
| 1170 | /// A variant found in a union slot, with the byte offset of the payload in the slot. |
| 1171 | record UnionPart: Copy { |
| 1172 | /// Byte offset of the payload from the start of the slot. |
| 1173 | payload: u32, |
| 1174 | /// The variant. |
| 1175 | variant: il::UnionVariant, |
| 1176 | } |
| 1177 | |
| 1178 | /// Find variant `tag` of the union slot that a pointer addresses. |
| 1179 | fn unionVariant(v: &Verifier, p: PtrState, tag: u32) -> UnionPart throws (Error) { |
| 1180 | let o = try extent(v, p, 0, 0); |
| 1181 | let case il::SlotKind::Union { offset: payload, variants, .. } = layout::slotAt( |
| 1182 | &v.ctx.table, p.layout, o |
| 1183 | ) else { |
| 1184 | throw fail(v, Rule::Slot); |
| 1185 | }; |
| 1186 | let variant = layout::variantWith(variants, tag as u64) else throw fail(v, Rule::View); |
| 1187 | return UnionPart { payload, variant }; |
| 1188 | } |
| 1189 | |
| 1190 | /// Check a read of a part of the payload of a union slot into an object of layout `l`. The tag |
| 1191 | /// check is part of the instruction, so the part is the one that the layout of the variant has |
| 1192 | /// at `offset`. |
| 1193 | fn checkUnionGet( |
| 1194 | v: &Verifier, dst: il::Reg, src: il::Reg, tag: u32, offset: u32, l: u32 |
| 1195 | ) throws (Error) { |
| 1196 | let d = try writable(v, dst); |
| 1197 | let found = try unionVariant(v, try accessible(v, src), tag); |
| 1198 | let payload = found.variant.layout else throw fail(v, Rule::View); |
| 1199 | if offset < found.payload or not layout::holds( |
| 1200 | &v.ctx.table, payload, (offset - found.payload) as u64, l |
| 1201 | ) |
| 1202 | { |
| 1203 | throw fail(v, Rule::View); |
| 1204 | } |
| 1205 | try checkCopyTo(v, d, l); |
| 1206 | } |
| 1207 | |
| 1208 | /// Check a write of a variant into a union slot. The tag and the payload are written |
| 1209 | /// together, so a slot never holds the payload of another variant. |
| 1210 | fn checkUnionSet( |
| 1211 | v: &Verifier, dst: il::Reg, tag: u32, offset: u32, src: il::Val, l: ?u32 |
| 1212 | ) throws (Error) { |
| 1213 | let d = try writable(v, dst); |
| 1214 | let found = try unionVariant(v, d, tag); |
| 1215 | if offset <> found.payload or found.variant.layout <> l { |
| 1216 | throw fail(v, Rule::View); |
| 1217 | } |
| 1218 | let payload = found.variant.layout else { |
| 1219 | let case il::Val::Undef = src else { |
| 1220 | throw fail(v, Rule::Type); |
| 1221 | }; |
| 1222 | return; |
| 1223 | }; |
| 1224 | let case il::Val::Reg(r) = src else { |
| 1225 | throw fail(v, Rule::Type); |
| 1226 | }; |
| 1227 | try checkCopyFrom(v, try accessible(v, r), payload); |
| 1228 | if hasRegions(v, payload) and not holds(d) { |
| 1229 | throw fail(v, Rule::Class); |
| 1230 | } |
| 1231 | } |
| 1232 | |
| 1233 | /// Check a call, and define its result. |
| 1234 | fn checkCall( |
| 1235 | v: &mut Verifier, retTy: il::ValType, dst: ?il::Reg, callee: il::Val, args: il::ArgRange |
| 1236 | ) throws (Error) { |
| 1237 | let case RegState::Fn(f) = try operand(v, callee) else { |
| 1238 | throw fail(v, Rule::Call); |
| 1239 | }; |
| 1240 | if f.nullable { |
| 1241 | throw fail(v, Rule::Null); |
| 1242 | } |
| 1243 | if not typeEq(retTy, sigRet(&v.ctx, f.sig)) { |
| 1244 | throw fail(v, Rule::Call); |
| 1245 | } |
| 1246 | let func = v.func; |
| 1247 | let values = il::argVals(func, args); |
| 1248 | if values.len <> sigLen(&v.ctx, f.sig) { |
| 1249 | throw fail(v, Rule::Arity); |
| 1250 | } |
| 1251 | for k in 0 .. values.len { |
| 1252 | try assign(v, values[k], sigParam(&v.ctx, f.sig, k)); |
| 1253 | } |
| 1254 | // A borrowed result written to a buffer holds non-owning pointers, so the buffer is |
| 1255 | // in the frame. |
| 1256 | if resultBuffer(retTy, sigBorrows(&v.ctx, f.sig)) { |
| 1257 | try holdingArgument(v, values[0]); |
| 1258 | } |
| 1259 | // A callee stores the sources of a target contract into the object of its argument. |
| 1260 | for borrow in sigBorrows(&v.ctx, f.sig) { |
| 1261 | if let t = borrow.target { |
| 1262 | try holdingArgument(v, values[t]); |
| 1263 | } |
| 1264 | } |
| 1265 | if let reg = dst { |
| 1266 | if let case il::ValType::Void = retTy { |
| 1267 | throw fail(v, Rule::Call); |
| 1268 | } |
| 1269 | try define(v, reg, declared(retTy)); |
| 1270 | } |
| 1271 | } |
| 1272 | |
| 1273 | /// Check the arguments that a branch passes to block `target`. A comparison with zero |
| 1274 | /// can prove that `present` is non-null on this edge. |
| 1275 | fn checkEdge(v: &Verifier, target: u32, args: il::ArgRange, present: ?il::Reg) throws (Error) { |
| 1276 | let params = v.func.blocks[target].params; |
| 1277 | let func = v.func; |
| 1278 | let values = il::argVals(func, args); |
| 1279 | if values.len <> params.len { |
| 1280 | throw fail(v, Rule::Arity); |
| 1281 | } |
| 1282 | for k in 0 .. values.len { |
| 1283 | let mut s = try operand(v, values[k]); |
| 1284 | if let r = present { |
| 1285 | if values[k] == il::Val::Reg(r) { |
| 1286 | match &mut s { |
| 1287 | case RegState::Ptr(p) => set p.nullable = false, |
| 1288 | case RegState::Fn(f) => set f.nullable = false, |
| 1289 | else => {} |
| 1290 | } |
| 1291 | } |
| 1292 | } |
| 1293 | try assignState(v, values[k], s, params[k].type); |
| 1294 | } |
| 1295 | } |
| 1296 | |
| 1297 | /// Check one instruction, and define its result. |
| 1298 | fn checkInstr(v: &mut Verifier, instr: il::Instr) throws (Error) { |
| 1299 | match instr { |
| 1300 | case il::Instr::Reserve { dst, layout } => { |
| 1301 | if v.ctx.prog.layouts[layout].alignment > FRAME_ALIGNMENT { |
| 1302 | throw fail(v, Rule::Limit); |
| 1303 | } |
| 1304 | try define(v, dst, RegState::Ptr(PtrState { |
| 1305 | layout, |
| 1306 | offset: 0, |
| 1307 | own: false, |
| 1308 | mutable: true, |
| 1309 | nullable: false, |
| 1310 | local: true, |
| 1311 | target: false, |
| 1312 | })); |
| 1313 | } |
| 1314 | case il::Instr::Load { typ, dst, src, offset } => { |
| 1315 | let p = try accessible(v, src); |
| 1316 | try extent(v, p, offset as i64, il::typeSize(typ) as u64); |
| 1317 | try define(v, dst, RegState::Data); |
| 1318 | } |
| 1319 | case il::Instr::Sload { typ, dst, src, offset } => { |
| 1320 | let p = try accessible(v, src); |
| 1321 | try extent(v, p, offset as i64, il::typeSize(typ) as u64); |
| 1322 | try define(v, dst, RegState::Data); |
| 1323 | } |
| 1324 | case il::Instr::Store { typ, src, dst, offset } => { |
| 1325 | try operand(v, src); |
| 1326 | try writePlain(v, dst, offset as i64, il::typeSize(typ) as u64); |
| 1327 | } |
| 1328 | case il::Instr::Blit { dst, src, layout } => { |
| 1329 | try checkBlit(v, dst, src, layout); |
| 1330 | } |
| 1331 | case il::Instr::Copy { dst, val } => { |
| 1332 | if let case il::Val::DataSym(name) = val { |
| 1333 | let index = dict::get(&v.ctx.dataNames, name) else { |
| 1334 | throw fail(v, Rule::Symbol); |
| 1335 | }; |
| 1336 | let item = v.ctx.prog.data[index as u32]; |
| 1337 | if let heap = item.heap { |
| 1338 | try define(v, dst, RegState::Heap(heap)); |
| 1339 | return; |
| 1340 | } |
| 1341 | try define(v, dst, RegState::Ptr(PtrState { |
| 1342 | layout: item.layout, |
| 1343 | offset: 0, |
| 1344 | own: true, |
| 1345 | mutable: not item.readOnly, |
| 1346 | nullable: false, |
| 1347 | local: false, |
| 1348 | target: false, |
| 1349 | })); |
| 1350 | } else { |
| 1351 | try define(v, dst, try operand(v, val)); |
| 1352 | } |
| 1353 | } |
| 1354 | case il::Instr::Field { dst, src, offset } => { |
| 1355 | let p = try accessible(v, src); |
| 1356 | let o = try extent(v, p, offset as i64, 0); |
| 1357 | let mut q = p; |
| 1358 | set q.offset = o as u32; |
| 1359 | try define(v, dst, RegState::Ptr(q)); |
| 1360 | } |
| 1361 | case il::Instr::Elem { dst, base, index, layout: e, count } => { |
| 1362 | try operand(v, index); |
| 1363 | let p = try accessible(v, base); |
| 1364 | try arrayOf(v, p, e, count); |
| 1365 | try define(v, dst, RegState::Ptr(PtrState { |
| 1366 | layout: e, |
| 1367 | offset: 0, |
| 1368 | own: p.own, |
| 1369 | mutable: p.mutable, |
| 1370 | nullable: false, |
| 1371 | local: p.local, |
| 1372 | target: p.target, |
| 1373 | })); |
| 1374 | } |
| 1375 | case il::Instr::BytesLoad { dst, slice, offset, .. } => { |
| 1376 | try byteSlice(v, slice, false); |
| 1377 | try operand(v, offset); |
| 1378 | try define(v, dst, RegState::Data); |
| 1379 | } |
| 1380 | case il::Instr::BytesStore { slice, offset, value, .. } => { |
| 1381 | try byteSlice(v, slice, true); |
| 1382 | try operand(v, offset); |
| 1383 | try operand(v, value); |
| 1384 | } |
| 1385 | case il::Instr::SliceElem { dst, slice, index, layout: e } => { |
| 1386 | try operand(v, index); |
| 1387 | let p = try accessible(v, slice); |
| 1388 | let slot = try sliceSource(v, p, e); |
| 1389 | try define(v, dst, RegState::Ptr(PtrState { |
| 1390 | layout: e, |
| 1391 | offset: 0, |
| 1392 | own: slot.own, |
| 1393 | mutable: slot.mutable, |
| 1394 | nullable: false, |
| 1395 | local: false, |
| 1396 | target: holds(p), |
| 1397 | })); |
| 1398 | } |
| 1399 | case il::Instr::SliceNew { dst, base, layout: e, count, start, end } => { |
| 1400 | let d = try sliceDest(v, dst, e); |
| 1401 | try operand(v, start); |
| 1402 | try operand(v, end); |
| 1403 | let s = try operand(v, base); |
| 1404 | // With no elements, nothing is reachable and the base can be any value. |
| 1405 | if count > 0 { |
| 1406 | let case RegState::Ptr(p) = s else { |
| 1407 | throw fail(v, Rule::Type); |
| 1408 | }; |
| 1409 | if p.nullable { |
| 1410 | throw fail(v, Rule::Null); |
| 1411 | } |
| 1412 | try arrayOf(v, p, e, count); |
| 1413 | try sliceFrom(v, d, p.own, p.mutable); |
| 1414 | } |
| 1415 | } |
| 1416 | case il::Instr::SliceSub { dst, src, layout: e, start, end } => { |
| 1417 | let d = try sliceDest(v, dst, e); |
| 1418 | try operand(v, start); |
| 1419 | try operand(v, end); |
| 1420 | let from = try sliceSource(v, try accessible(v, src), e); |
| 1421 | try sliceFrom(v, d, from.own, from.mutable); |
| 1422 | } |
| 1423 | case il::Instr::SliceLen { dst, layout: e, length } => { |
| 1424 | try sliceDest(v, dst, e); |
| 1425 | try operand(v, length); |
| 1426 | } |
| 1427 | case il::Instr::SliceGrow { ok, slice, heap, layout: e, capacity } => { |
| 1428 | let d = try sliceDest(v, slice, e); |
| 1429 | let h = try heapOperand(v, heap); |
| 1430 | try operand(v, capacity); |
| 1431 | // Memory that holds slots comes only from a heap that is never visible as bytes. |
| 1432 | // Elements with references keep the regions of the slot that owns them. |
| 1433 | if layout::alignment(&v.ctx.table, e) > FRAME_ALIGNMENT as u64 |
| 1434 | or (not layout::isPlain(&v.ctx.table, e) and h <> il::HeapType::Typed) |
| 1435 | { |
| 1436 | throw fail(v, Rule::View); |
| 1437 | } |
| 1438 | // The grown slice replaces the one in the slot, so the slot owns elements and can |
| 1439 | // be written. |
| 1440 | if not d.slot.own { |
| 1441 | throw fail(v, Rule::Class); |
| 1442 | } |
| 1443 | if not d.slot.mutable { |
| 1444 | throw fail(v, Rule::Mutability); |
| 1445 | } |
| 1446 | try define(v, ok, RegState::Data); |
| 1447 | } |
| 1448 | case il::Instr::SliceCopy { dst, src, layout: e } => { |
| 1449 | // Owned slots are duplicated by a copy, which the verifier allows: it checks types, |
| 1450 | // not uniqueness. |
| 1451 | let to = try sliceSource(v, try accessible(v, dst), e); |
| 1452 | try sliceSource(v, try accessible(v, src), e); |
| 1453 | if not to.mutable { |
| 1454 | throw fail(v, Rule::Mutability); |
| 1455 | } |
| 1456 | } |
| 1457 | case il::Instr::LoadPtr { dst, src, offset, nullable } => { |
| 1458 | let p = try accessible(v, src); |
| 1459 | let o = try extent(v, p, offset as i64, 0); |
| 1460 | let slot = layout::slotAt(&v.ctx.table, p.layout, o) else { |
| 1461 | throw fail(v, Rule::Slot); |
| 1462 | }; |
| 1463 | match slot { |
| 1464 | case il::SlotKind::Ptr(t) => |
| 1465 | try define(v, dst, RegState::Ptr(PtrState { |
| 1466 | layout: t.layout, |
| 1467 | offset: 0, |
| 1468 | own: t.own, |
| 1469 | mutable: t.mutable, |
| 1470 | nullable, |
| 1471 | local: false, |
| 1472 | target: holds(p), |
| 1473 | })), |
| 1474 | case il::SlotKind::Fn(sig) => |
| 1475 | try define(v, dst, RegState::Fn(FnState { |
| 1476 | sig: SigRef::Table(sig), nullable |
| 1477 | })), |
| 1478 | case il::SlotKind::Heap(h) => try define(v, dst, RegState::Heap(h)), |
| 1479 | else => throw fail(v, Rule::Slot), |
| 1480 | } |
| 1481 | } |
| 1482 | case il::Instr::StorePtr { src, dst, offset } => { |
| 1483 | try checkStorePtr(v, src, dst, offset); |
| 1484 | } |
| 1485 | case il::Instr::TraitNew { dst, recv, table } => { |
| 1486 | try checkTraitNew(v, dst, recv, table); |
| 1487 | } |
| 1488 | case il::Instr::TraitCopy { dst, src } => { |
| 1489 | try checkTraitCopy(v, dst, src); |
| 1490 | } |
| 1491 | case il::Instr::UnionGet { dst, src, tag, offset, layout } => { |
| 1492 | try checkUnionGet(v, dst, src, tag, offset, layout); |
| 1493 | } |
| 1494 | case il::Instr::UnionSet { dst, tag, offset, src, layout } => { |
| 1495 | try checkUnionSet(v, dst, tag, offset, src, layout); |
| 1496 | } |
| 1497 | case il::Instr::TraitCall { retTy, dst, obj, method, receiver, args } => { |
| 1498 | try checkTraitCall(v, retTy, dst, obj, method, receiver, args); |
| 1499 | } |
| 1500 | case il::Instr::BinOp { op, typ, dst, a, b } => { |
| 1501 | if (op == il::BinOp::RotL or op == il::BinOp::RotR) |
| 1502 | and typ <> il::Type::W32 |
| 1503 | and typ <> il::Type::W64 |
| 1504 | { |
| 1505 | throw fail(v, Rule::Type); |
| 1506 | } |
| 1507 | try operand(v, a); |
| 1508 | try operand(v, b); |
| 1509 | try define(v, dst, RegState::Data); |
| 1510 | } |
| 1511 | case il::Instr::UnOp { op, typ, dst, a } => { |
| 1512 | if (op == il::UnOp::LeadingZeros |
| 1513 | or op == il::UnOp::TrailingZeros |
| 1514 | or op == il::UnOp::PopCount) |
| 1515 | and typ <> il::Type::W32 |
| 1516 | and typ <> il::Type::W64 |
| 1517 | { |
| 1518 | throw fail(v, Rule::Type); |
| 1519 | } |
| 1520 | try operand(v, a); |
| 1521 | try define(v, dst, RegState::Data); |
| 1522 | } |
| 1523 | case il::Instr::Zext { dst, val, .. } => { |
| 1524 | try operand(v, val); |
| 1525 | try define(v, dst, RegState::Data); |
| 1526 | } |
| 1527 | case il::Instr::Sext { dst, val, .. } => { |
| 1528 | try operand(v, val); |
| 1529 | try define(v, dst, RegState::Data); |
| 1530 | } |
| 1531 | case il::Instr::Call { retTy, dst, func: callee, args } => { |
| 1532 | try checkCall(v, retTy, dst, callee, args); |
| 1533 | } |
| 1534 | case il::Instr::Ret { val } => { |
| 1535 | if let x = val { |
| 1536 | try assign(v, x, v.func.returnType); |
| 1537 | } else if not (v.func.returnType == il::ValType::Void) { |
| 1538 | throw fail(v, Rule::Return); |
| 1539 | } |
| 1540 | } |
| 1541 | case il::Instr::Jmp { target, args } => { |
| 1542 | try checkEdge(v, target, args, nil); |
| 1543 | } |
| 1544 | case il::Instr::Br { op, typ, a, b, thenTarget, thenArgs, elseTarget, elseArgs } => { |
| 1545 | try operand(v, a); |
| 1546 | try operand(v, b); |
| 1547 | let mut tested: ?il::Reg = nil; |
| 1548 | if typ == il::Type::W64 and (op == il::CmpOp::Eq or op == il::CmpOp::Ne) { |
| 1549 | if isZero(a) { |
| 1550 | if let case il::Val::Reg(r) = b { |
| 1551 | set tested = r; |
| 1552 | } |
| 1553 | } else if isZero(b) { |
| 1554 | if let case il::Val::Reg(r) = a { |
| 1555 | set tested = r; |
| 1556 | } |
| 1557 | } |
| 1558 | } |
| 1559 | let mut thenNonNull: ?il::Reg = nil; |
| 1560 | let mut elseNonNull: ?il::Reg = nil; |
| 1561 | if op == il::CmpOp::Ne { |
| 1562 | set thenNonNull = tested; |
| 1563 | } else if op == il::CmpOp::Eq { |
| 1564 | set elseNonNull = tested; |
| 1565 | } |
| 1566 | try checkEdge(v, thenTarget, thenArgs, thenNonNull); |
| 1567 | try checkEdge(v, elseTarget, elseArgs, elseNonNull); |
| 1568 | } |
| 1569 | case il::Instr::Switch { val, defaultTarget, defaultArgs, cases } => { |
| 1570 | try operand(v, val); |
| 1571 | try checkEdge(v, defaultTarget, defaultArgs, nil); |
| 1572 | let func = v.func; |
| 1573 | for branch in il::switchCases(func, cases) { |
| 1574 | try checkEdge(v, branch.target, branch.args, nil); |
| 1575 | } |
| 1576 | } |
| 1577 | case il::Instr::Ecall { dst, num, a0, a1, a2, a3, buf } => { |
| 1578 | try operand(v, num); |
| 1579 | try operand(v, a0); |
| 1580 | try operand(v, a1); |
| 1581 | try operand(v, a2); |
| 1582 | try operand(v, a3); |
| 1583 | // The kernel writes the buffer, so it is plain memory of the caller. |
| 1584 | if let b = buf { |
| 1585 | try writePlain(v, b.ptr, 0, b.size as u64); |
| 1586 | } |
| 1587 | try define(v, dst, RegState::Data); |
| 1588 | } |
| 1589 | case il::Instr::PageSlice { err, slot, handle, write, layout: e } => { |
| 1590 | try operand(v, handle); |
| 1591 | let dest = try sliceDest(v, slot, e); |
| 1592 | let to = dest.slot; |
| 1593 | // Page memory is shared and reachable by the kernel, so only plain elements live |
| 1594 | // in it, and the slice must own it with the rights of the access. |
| 1595 | if not to.own { |
| 1596 | throw fail(v, Rule::Class); |
| 1597 | } |
| 1598 | if to.mutable <> write { |
| 1599 | throw fail(v, Rule::Mutability); |
| 1600 | } |
| 1601 | if not layout::isPlain(&v.ctx.table, e) or layout::size(&v.ctx.table, e) == 0 { |
| 1602 | throw fail(v, Rule::View); |
| 1603 | } |
| 1604 | try define(v, err, RegState::Data); |
| 1605 | } |
| 1606 | case il::Instr::PageHeap { err, slot, handle } => { |
| 1607 | try operand(v, handle); |
| 1608 | // The slot is protected memory, so only this instruction and `slice.grow`'s |
| 1609 | // handle loads touch it, and its rights only narrow what the heap offers. |
| 1610 | let p = try writable(v, slot); |
| 1611 | let o = try extent(v, p, 0, 0); |
| 1612 | let kind = layout::slotAt(&v.ctx.table, p.layout, o) else { |
| 1613 | throw fail(v, Rule::Slot); |
| 1614 | }; |
| 1615 | let case il::SlotKind::Heap(want) = kind else { |
| 1616 | throw fail(v, Rule::Slot); |
| 1617 | }; |
| 1618 | if not layout::heapFits(il::HeapType::Typed, want) { |
| 1619 | throw fail(v, Rule::Type); |
| 1620 | } |
| 1621 | try define(v, err, RegState::Data); |
| 1622 | } |
| 1623 | case il::Instr::HeapReset { heap } => { |
| 1624 | // Only a heap of plain elements can be reset, so a pointer into the reused memory |
| 1625 | // reaches plain bytes, and no slot is ever formed from them. |
| 1626 | let h = try heapOperand(v, heap); |
| 1627 | if h <> il::HeapType::Reset { |
| 1628 | throw fail(v, Rule::Type); |
| 1629 | } |
| 1630 | } |
| 1631 | case il::Instr::DeviceRead { dst, handle, offset, .. } => { |
| 1632 | try operand(v, handle); |
| 1633 | try operand(v, offset); |
| 1634 | try define(v, dst, RegState::Data); |
| 1635 | } |
| 1636 | case il::Instr::DeviceWrite { handle, offset, value, .. } => { |
| 1637 | try operand(v, handle); |
| 1638 | try operand(v, offset); |
| 1639 | try operand(v, value); |
| 1640 | } |
| 1641 | case il::Instr::Unreachable, il::Instr::Ebreak, il::Instr::MemoryFence => {} |
| 1642 | } |
| 1643 | } |
| 1644 | |
| 1645 | //////////////// |
| 1646 | // Functions // |
| 1647 | //////////////// |
| 1648 | |
| 1649 | /// Whether register `n` has the frame fact, or the target fact when `target` holds. |
| 1650 | fn addressFact(v: &Verifier, target: bool, n: u32) -> bool { |
| 1651 | return v.target[n] if target else v.frame[n]; |
| 1652 | } |
| 1653 | |
| 1654 | /// Set the frame fact of register `n`, or its target fact when `target` holds. |
| 1655 | fn setAddressFact(v: &mut Verifier, target: bool, n: u32, fact: bool) { |
| 1656 | if target { |
| 1657 | set v.target[n] = fact; |
| 1658 | } else { |
| 1659 | set v.frame[n] = fact; |
| 1660 | } |
| 1661 | } |
| 1662 | |
| 1663 | /// Whether `val` is a register whose address has the fact. |
| 1664 | fn addressValue(v: &Verifier, target: bool, val: il::Val) -> bool { |
| 1665 | let case il::Val::Reg(r) = val else return false; |
| 1666 | return r.n < v.frame.len and addressFact(v, target, r.n); |
| 1667 | } |
| 1668 | |
| 1669 | /// Clear the fact of a join parameter if an incoming address does not have it. |
| 1670 | fn addressEdge(v: &mut Verifier, fact: bool, target: u32, args: il::ArgRange) -> bool |
| 1671 | throws (Error) |
| 1672 | { |
| 1673 | let func = v.func; |
| 1674 | let values = il::argVals(func, args); |
| 1675 | let params = func.blocks[target].params; |
| 1676 | if values.len <> params.len { |
| 1677 | throw fail(v, Rule::Arity); |
| 1678 | } |
| 1679 | let mut changed = false; |
| 1680 | for value, k in values { |
| 1681 | let r = params[k].value; |
| 1682 | if addressFact(v, fact, r.n) and not addressValue(v, fact, value) { |
| 1683 | setAddressFact(v, fact, r.n, false); |
| 1684 | set changed = true; |
| 1685 | } |
| 1686 | } |
| 1687 | return changed; |
| 1688 | } |
| 1689 | |
| 1690 | /// Find addresses that stay in frame storage, and addresses of target objects. |
| 1691 | fn frameAddresses(v: &mut Verifier) throws (Error) { |
| 1692 | try addresses(v, false); |
| 1693 | try addresses(v, true); |
| 1694 | } |
| 1695 | |
| 1696 | /// Find addresses that keep a fact through copies, field and element addresses, |
| 1697 | /// and block arguments: frame storage, or target objects when `target` holds. A |
| 1698 | /// target object also reaches the objects of its non-owning pointers. A join keeps |
| 1699 | /// the fact only if every input has it. Candidates start with the fact and lose it |
| 1700 | /// until no dependency changes. |
| 1701 | fn addresses(v: &mut Verifier, target: bool) throws (Error) { |
| 1702 | let func = v.func; |
| 1703 | let buffered = resultBuffer(func.returnType, func.borrows); |
| 1704 | for param, k in func.params { |
| 1705 | let buffer = k == 0 and buffered; |
| 1706 | // The result buffer is checked as the result, not as a target object. |
| 1707 | let mut fact = buffer and not target; |
| 1708 | if target and not buffer { |
| 1709 | if let case il::ValType::Ptr(p) = param.type { |
| 1710 | set fact = hasRegions(v, p.layout); |
| 1711 | } |
| 1712 | } |
| 1713 | setAddressFact(v, target, param.value.n, fact); |
| 1714 | } |
| 1715 | for block in func.blocks { |
| 1716 | for param in block.params { |
| 1717 | let mut fact = false; |
| 1718 | if let case il::ValType::Ptr(p) = param.type { |
| 1719 | set fact = not p.own; |
| 1720 | } |
| 1721 | setAddressFact(v, target, param.value.n, fact); |
| 1722 | } |
| 1723 | for instr in block.instrs { |
| 1724 | let dst = il::instrDst(&instr) else continue; |
| 1725 | let mut candidate = false; |
| 1726 | match instr { |
| 1727 | case il::Instr::Reserve { .. } => set candidate = not target, |
| 1728 | case |
| 1729 | il::Instr::Field { .. }, |
| 1730 | il::Instr::Elem { .. }, |
| 1731 | il::Instr::Copy { val: il::Val::Reg(_), .. } => |
| 1732 | set candidate = true, |
| 1733 | case il::Instr::LoadPtr { .. }, il::Instr::SliceElem { .. } => |
| 1734 | set candidate = target, |
| 1735 | else => {} |
| 1736 | } |
| 1737 | setAddressFact(v, target, dst.n, candidate); |
| 1738 | } |
| 1739 | } |
| 1740 | let mut changed = true; |
| 1741 | while changed { |
| 1742 | set changed = false; |
| 1743 | for n in 0 .. func.blocks.len { |
| 1744 | set v.block = v.flow.order[n]; |
| 1745 | for instr, i in func.blocks[v.block].instrs { |
| 1746 | set v.instr = i; |
| 1747 | let mut from: ?il::Val = nil; |
| 1748 | let mut loaded = false; |
| 1749 | match instr { |
| 1750 | case il::Instr::Copy { val, .. } => set from = val, |
| 1751 | case il::Instr::Field { src, .. } => set from = il::Val::Reg(src), |
| 1752 | case il::Instr::Elem { base, .. } => set from = il::Val::Reg(base), |
| 1753 | case il::Instr::LoadPtr { src, .. } => { |
| 1754 | set from = il::Val::Reg(src); |
| 1755 | set loaded = true; |
| 1756 | } |
| 1757 | case il::Instr::SliceElem { slice, .. } => { |
| 1758 | set from = il::Val::Reg(slice); |
| 1759 | set loaded = true; |
| 1760 | } |
| 1761 | case il::Instr::Jmp { target: to, args } => { |
| 1762 | if try addressEdge(v, target, to, args) { |
| 1763 | set changed = true; |
| 1764 | } |
| 1765 | } |
| 1766 | case il::Instr::Br { thenTarget, thenArgs, elseTarget, elseArgs, .. } => { |
| 1767 | let a = try addressEdge(v, target, thenTarget, thenArgs); |
| 1768 | let b = try addressEdge(v, target, elseTarget, elseArgs); |
| 1769 | if a or b { |
| 1770 | set changed = true; |
| 1771 | } |
| 1772 | } |
| 1773 | case il::Instr::Switch { defaultTarget, defaultArgs, cases, .. } => { |
| 1774 | if try addressEdge(v, target, defaultTarget, defaultArgs) { |
| 1775 | set changed = true; |
| 1776 | } |
| 1777 | for branch in il::switchCases(func, cases) { |
| 1778 | if try addressEdge(v, target, branch.target, branch.args) { |
| 1779 | set changed = true; |
| 1780 | } |
| 1781 | } |
| 1782 | } |
| 1783 | else => {} |
| 1784 | } |
| 1785 | // A pointer loaded from frame storage or a target object is a target. |
| 1786 | if let value = |
| 1787 | from; |
| 1788 | not addressValue(v, target, value) |
| 1789 | and not (target and loaded and addressValue(v, false, value)) |
| 1790 | { |
| 1791 | let dst = il::instrDst(&instr) else continue; |
| 1792 | if addressFact(v, target, dst.n) { |
| 1793 | setAddressFact(v, target, dst.n, false); |
| 1794 | set changed = true; |
| 1795 | } |
| 1796 | } |
| 1797 | } |
| 1798 | } |
| 1799 | } |
| 1800 | } |
| 1801 | |
| 1802 | /// Check one function body. Blocks are checked in reverse postorder, so a definition that |
| 1803 | /// dominates a use is checked before it. Blocks that cannot be reached follow. |
| 1804 | fn checkFn(v: &mut Verifier) throws (Error) { |
| 1805 | let func = v.func; |
| 1806 | flow::compute(&mut v.flow, func); |
| 1807 | try frameAddresses(v); |
| 1808 | set v.block = 0; |
| 1809 | set v.instr = 0; |
| 1810 | for param in func.params { |
| 1811 | let mut s = declared(param.type); |
| 1812 | if let case RegState::Ptr(p) = &mut s { |
| 1813 | set p.target = v.target[param.value.n]; |
| 1814 | } |
| 1815 | try define(v, param.value, s); |
| 1816 | } |
| 1817 | // The result buffer is an object of the frame of the caller, which outlives the |
| 1818 | // pointers that the result borrows. |
| 1819 | if resultBuffer(func.returnType, func.borrows) { |
| 1820 | if let case RegState::Ptr(p) = &mut v.defs[func.params[0].value.n].state { |
| 1821 | set p.local = true; |
| 1822 | } |
| 1823 | } |
| 1824 | for b in 0 .. func.blocks.len { |
| 1825 | set v.block = b; |
| 1826 | for param in func.blocks[b].params { |
| 1827 | let mut s = declared(param.type); |
| 1828 | if let case RegState::Ptr(p) = &mut s { |
| 1829 | set p.local = v.frame[param.value.n]; |
| 1830 | set p.target = v.target[param.value.n]; |
| 1831 | } |
| 1832 | try define(v, param.value, s); |
| 1833 | } |
| 1834 | } |
| 1835 | for n in 0 .. func.blocks.len { |
| 1836 | let b = v.flow.order[n]; |
| 1837 | set v.block = b; |
| 1838 | let block = func.blocks[b]; |
| 1839 | for i in 0 .. block.instrs.len { |
| 1840 | set v.instr = i; |
| 1841 | try checkInstr(v, block.instrs[i]); |
| 1842 | } |
| 1843 | } |
| 1844 | } |
| 1845 | |
| 1846 | /// Number of regions of the layout addressed by a register. |
| 1847 | fn cellCount(v: &Verifier, r: il::Reg) -> u32 { |
| 1848 | let case RegState::Ptr(p) = v.defs[r.n].state else return 0; |
| 1849 | return v.ctx.table.layouts[p.layout].regions; |
| 1850 | } |
| 1851 | |
| 1852 | /// Whether a region may contain a foreign pointer. |
| 1853 | fn foreignCell(v: &Verifier, r: il::Reg, i: u32) -> bool { |
| 1854 | assert i < cellCount(v, r); |
| 1855 | return v.cells[r.n * v.cellWidth + i]; |
| 1856 | } |
| 1857 | |
| 1858 | /// Add foreign provenance to one region. |
| 1859 | fn markCell(v: &mut Verifier, r: il::Reg, i: u32) -> bool { |
| 1860 | assert i < cellCount(v, r); |
| 1861 | let at = r.n * v.cellWidth + i; |
| 1862 | let changed = not v.cells[at]; |
| 1863 | set v.cells[at] = true; |
| 1864 | return changed; |
| 1865 | } |
| 1866 | |
| 1867 | /// Relation between two region positions. |
| 1868 | union RegionFlow: Copy { |
| 1869 | /// A copied reference value has independent storage. |
| 1870 | Value, |
| 1871 | /// Writes through either position can change their shared referent. |
| 1872 | Alias, |
| 1873 | } |
| 1874 | |
| 1875 | /// Provenance position in a pointer register. |
| 1876 | union RegionPlace: Copy { |
| 1877 | /// Address of the pointer value. |
| 1878 | Address, |
| 1879 | /// One region of the addressed object. |
| 1880 | Cell(u32), |
| 1881 | /// Address and all regions reachable through the pointer. |
| 1882 | Reachable, |
| 1883 | } |
| 1884 | |
| 1885 | /// Propagate region facts through a value copy or a shared referent. |
| 1886 | /// An absent region holds nothing. |
| 1887 | fn flowCell( |
| 1888 | v: &mut Verifier, dst: il::Reg, d: ?u32, src: il::Reg, s: ?u32, flow: RegionFlow |
| 1889 | ) -> bool { |
| 1890 | let to = d else return false; |
| 1891 | let from = s else return false; |
| 1892 | return flowRegion(v, dst, RegionPlace::Cell(to), src, RegionPlace::Cell(from), flow); |
| 1893 | } |
| 1894 | |
| 1895 | /// Whether a provenance position has foreign facts. |
| 1896 | fn foreignRegion(v: &Verifier, r: il::Reg, place: RegionPlace) -> bool { |
| 1897 | match place { |
| 1898 | case RegionPlace::Cell(i) => return foreignCell(v, r, i), |
| 1899 | case RegionPlace::Address => return foreignRef(v, il::Val::Reg(r)), |
| 1900 | case RegionPlace::Reachable => { |
| 1901 | if foreignRef(v, il::Val::Reg(r)) { |
| 1902 | return true; |
| 1903 | } |
| 1904 | for i in 0 .. cellCount(v, r) { |
| 1905 | if foreignCell(v, r, i) { |
| 1906 | return true; |
| 1907 | } |
| 1908 | } |
| 1909 | return false; |
| 1910 | } |
| 1911 | } |
| 1912 | } |
| 1913 | |
| 1914 | /// Mark a provenance position as foreign. |
| 1915 | fn markRegion(v: &mut Verifier, r: il::Reg, place: RegionPlace) -> bool { |
| 1916 | match place { |
| 1917 | case RegionPlace::Cell(i) => return markCell(v, r, i), |
| 1918 | case RegionPlace::Reachable => return markForeign(v, r), |
| 1919 | case RegionPlace::Address => { |
| 1920 | let changed = not v.defs[r.n].foreign; |
| 1921 | set v.defs[r.n].foreign = true; |
| 1922 | return changed; |
| 1923 | } |
| 1924 | } |
| 1925 | } |
| 1926 | |
| 1927 | /// Propagate facts through a copied value or a shared referent. |
| 1928 | fn flowRegion( |
| 1929 | v: &mut Verifier, |
| 1930 | dst: il::Reg, |
| 1931 | to: RegionPlace, |
| 1932 | src: il::Reg, |
| 1933 | from: RegionPlace, |
| 1934 | flow: RegionFlow |
| 1935 | ) -> bool { |
| 1936 | let changed = foreignRegion(v, src, from) and markRegion(v, dst, to); |
| 1937 | let back = flow == RegionFlow::Alias |
| 1938 | and foreignRegion(v, dst, to) |
| 1939 | and markRegion(v, src, from); |
| 1940 | return changed or back; |
| 1941 | } |
| 1942 | |
| 1943 | /// Relation of a region copied from a layout to its source region. |
| 1944 | fn copiedRegion(v: &Verifier, l: u32, region: u32) -> RegionFlow { |
| 1945 | return RegionFlow::Alias |
| 1946 | if v.ctx.table.infos[l].shared[region] |
| 1947 | else RegionFlow::Value; |
| 1948 | } |
| 1949 | |
| 1950 | /// Mark an address and all references reachable through it as foreign. |
| 1951 | fn markForeign(v: &mut Verifier, r: il::Reg) -> bool { |
| 1952 | let mut changed = not v.defs[r.n].foreign; |
| 1953 | set v.defs[r.n].foreign = true; |
| 1954 | for i in 0 .. cellCount(v, r) { |
| 1955 | if markCell(v, r, i) { |
| 1956 | set changed = true; |
| 1957 | } |
| 1958 | } |
| 1959 | return changed; |
| 1960 | } |
| 1961 | |
| 1962 | /// Region of the layout addressed by a register for region `i` of a typed view. |
| 1963 | fn cellOf(v: &Verifier, r: il::Reg, view: u32, i: u32) -> ?u32 { |
| 1964 | let case RegState::Ptr(p) = v.defs[r.n].state else panic "cellOf: expected pointer"; |
| 1965 | return layout::viewRegion(&v.ctx.table, p.layout, p.offset as u64, view, i); |
| 1966 | } |
| 1967 | |
| 1968 | /// Region of the address in an accessible slot, if the slot is non-owning. |
| 1969 | fn cellAt(v: &Verifier, r: il::Reg, offset: i32) -> ?u32 { |
| 1970 | let case RegState::Ptr(p) = v.defs[r.n].state else return nil; |
| 1971 | return layout::addressRegion( |
| 1972 | &v.ctx.table, p.layout, (p.offset as i64 + offset as i64) as u64 |
| 1973 | ); |
| 1974 | } |
| 1975 | |
| 1976 | /// Region for region `i` of the pointee of an accessible pointer or slice slot. |
| 1977 | fn pointeeCell(v: &Verifier, r: il::Reg, offset: i32, i: u32) -> ?u32 { |
| 1978 | let case RegState::Ptr(p) = v.defs[r.n].state else return nil; |
| 1979 | return layout::pointeeRegion( |
| 1980 | &v.ctx.table, p.layout, (p.offset as i64 + offset as i64) as u64, i |
| 1981 | ); |
| 1982 | } |
| 1983 | |
| 1984 | /// Copy the regions of a typed view from one register to another. |
| 1985 | fn flowView(v: &mut Verifier, dst: il::Reg, src: il::Reg, l: u32) -> bool { |
| 1986 | let mut changed = false; |
| 1987 | for i in 0 .. v.ctx.table.layouts[l].regions { |
| 1988 | if flowCell(v, dst, cellOf(v, dst, l, i), src, cellOf(v, src, l, i), copiedRegion( |
| 1989 | v, l, i |
| 1990 | )) { |
| 1991 | set changed = true; |
| 1992 | } |
| 1993 | } |
| 1994 | return changed; |
| 1995 | } |
| 1996 | |
| 1997 | /// Propagate a pointer view and share contents between its local aliases. |
| 1998 | fn flowForeign(v: &mut Verifier, r: il::Reg, from: il::Val) -> bool { |
| 1999 | let case il::Val::Reg(f) = from else return false; |
| 2000 | let mut changed = false; |
| 2001 | if v.defs[f.n].foreign and not v.defs[r.n].foreign { |
| 2002 | set v.defs[r.n].foreign = true; |
| 2003 | set changed = true; |
| 2004 | } |
| 2005 | let case RegState::Ptr(to) = v.defs[r.n].state else return changed; |
| 2006 | let case RegState::Ptr(source) = v.defs[f.n].state else return changed; |
| 2007 | for i in 0 .. cellCount(v, r) { |
| 2008 | // Field addresses keep the layout of the containing object. |
| 2009 | let mut cell: ?u32 = i; |
| 2010 | if source.layout <> to.layout { |
| 2011 | set cell = cellOf(v, f, to.layout, i); |
| 2012 | } |
| 2013 | if flowCell(v, r, i, f, cell, RegionFlow::Alias) { |
| 2014 | set changed = true; |
| 2015 | } |
| 2016 | } |
| 2017 | return changed; |
| 2018 | } |
| 2019 | |
| 2020 | /// Whether a value is a foreign non-owning pointer. |
| 2021 | fn foreignRef(v: &Verifier, val: il::Val) -> bool { |
| 2022 | let case il::Val::Reg(r) = val else return false; |
| 2023 | let case RegState::Ptr(p) = v.defs[r.n].state else return false; |
| 2024 | return v.defs[r.n].foreign and not p.own; |
| 2025 | } |
| 2026 | |
| 2027 | /// Transfer a pointer value into a borrowed slot. |
| 2028 | fn taintSlot(v: &mut Verifier, dst: il::Reg, offset: i32, foreign: bool) -> bool { |
| 2029 | let cell = cellAt(v, dst, offset) else return false; |
| 2030 | return foreign and markCell(v, dst, cell); |
| 2031 | } |
| 2032 | |
| 2033 | /// Follow a borrowed slot, keeping its address and pointee regions apart. A |
| 2034 | /// writable pointer into a target object shares its pointee regions with the |
| 2035 | /// object, so that stores through it reach the regions of the object. |
| 2036 | fn loadSources(v: &mut Verifier, dst: il::Reg, src: il::Reg, offset: i32) -> bool { |
| 2037 | let mut changed = false; |
| 2038 | // An owning slot has no address region, but its pointee has regions. |
| 2039 | if let cell = cellAt(v, src, offset); foreignCell(v, src, cell) and not v.defs[dst.n].foreign { |
| 2040 | set v.defs[dst.n].foreign = true; |
| 2041 | set changed = true; |
| 2042 | } |
| 2043 | let case RegState::Ptr(loaded) = v.defs[dst.n].state else return changed; |
| 2044 | for i in 0 .. cellCount(v, dst) { |
| 2045 | let pointee = pointeeCell(v, src, offset, i); |
| 2046 | let shared = loaded.mutable or v.ctx.table.infos[loaded.layout].shared[i]; |
| 2047 | let flow = RegionFlow::Alias if shared else RegionFlow::Value; |
| 2048 | if flowCell(v, dst, i, src, pointee, flow) { |
| 2049 | set changed = true; |
| 2050 | } |
| 2051 | } |
| 2052 | return changed; |
| 2053 | } |
| 2054 | |
| 2055 | /// Store the address and pointee regions of a pointer or slice value. |
| 2056 | fn storeSources(v: &mut Verifier, dst: il::Reg, offset: i32, from: il::Val) -> bool { |
| 2057 | let mut changed = taintSlot(v, dst, offset, foreignRef(v, from)); |
| 2058 | let case il::Val::Reg(src) = from else return changed; |
| 2059 | let case RegState::Ptr(p) = v.defs[dst.n].state else return changed; |
| 2060 | let slot = layout::slotAt(&v.ctx.table, p.layout, (p.offset as i64 + offset as i64) as u64) |
| 2061 | else return changed; |
| 2062 | let mut view: il::PtrType = undefined; |
| 2063 | match slot { |
| 2064 | case il::SlotKind::Ptr(t) => set view = t, |
| 2065 | case il::SlotKind::Slice(t) => set view = t, |
| 2066 | else => return changed, |
| 2067 | } |
| 2068 | // The slot and the stored pointer then address the same objects. Stores through |
| 2069 | // a copy that can write them reach the facts of the stored pointer. |
| 2070 | for i in 0 .. v.ctx.table.layouts[view.layout].regions { |
| 2071 | let slot = pointeeCell(v, dst, offset, i); |
| 2072 | let value = cellOf(v, src, view.layout, i); |
| 2073 | let shared = view.mutable or v.ctx.table.infos[view.layout].shared[i]; |
| 2074 | let flow = RegionFlow::Alias if shared else RegionFlow::Value; |
| 2075 | if flowCell(v, dst, slot, src, value, flow) { |
| 2076 | set changed = true; |
| 2077 | } |
| 2078 | } |
| 2079 | return changed; |
| 2080 | } |
| 2081 | |
| 2082 | /// Mark block parameters that receive foreign arguments. |
| 2083 | fn flowEdge(v: &mut Verifier, target: u32, args: il::ArgRange) -> bool { |
| 2084 | let params = v.func.blocks[target].params; |
| 2085 | let mut changed = false; |
| 2086 | let func = v.func; |
| 2087 | for val, k in il::argVals(func, args) { |
| 2088 | if flowForeign(v, params[k].value, val) { |
| 2089 | set changed = true; |
| 2090 | } |
| 2091 | } |
| 2092 | return changed; |
| 2093 | } |
| 2094 | |
| 2095 | /// Region of the layout addressed by a register for region `i` of a typed view |
| 2096 | /// at byte `offset` of the payload of variant `tag` of the union it addresses. |
| 2097 | fn unionCell(v: &Verifier, r: il::Reg, tag: u32, offset: u32, view: u32, i: u32) -> ?u32 { |
| 2098 | let case RegState::Ptr(p) = v.defs[r.n].state else panic "unionCell: expected pointer"; |
| 2099 | let case il::SlotKind::Union { offset: payload, variants, .. } = layout::slotAt( |
| 2100 | &v.ctx.table, p.layout, p.offset as u64 |
| 2101 | ) else panic "unionCell: expected union slot"; |
| 2102 | let variant = layout::variantWith(variants, tag as u64) |
| 2103 | else panic "unionCell: expected variant"; |
| 2104 | let l = variant.layout else panic "unionCell: expected payload"; |
| 2105 | let region = layout::viewRegion(&v.ctx.table, l, (offset - payload) as u64, view, i) |
| 2106 | else return nil; |
| 2107 | return layout::variantRegion(&v.ctx.table, p.layout, p.offset as u64, tag, region); |
| 2108 | } |
| 2109 | |
| 2110 | /// Propagate a call source to a pointer result. Mutable result views share |
| 2111 | /// their pointee regions with the sources that the signature permits. |
| 2112 | fn flowResult( |
| 2113 | v: &mut Verifier, r: il::Reg, ret: il::ValType, result: u32, src: il::Reg, source: RegionPlace |
| 2114 | ) -> bool throws (Error) { |
| 2115 | let case il::ValType::Ptr(p) = ret else throw fail(v, Rule::Return); |
| 2116 | let address: u32 = 0 if p.own else 1; |
| 2117 | if result < address { |
| 2118 | return flowRegion(v, r, RegionPlace::Address, src, source, RegionFlow::Value); |
| 2119 | } |
| 2120 | let i = result - address; |
| 2121 | let cell = cellOf(v, r, p.layout, i) else return false; |
| 2122 | let shared = p.mutable or v.ctx.table.infos[p.layout].shared[i]; |
| 2123 | let flow = RegionFlow::Alias if shared else RegionFlow::Value; |
| 2124 | return flowRegion(v, r, RegionPlace::Cell(cell), src, source, flow); |
| 2125 | } |
| 2126 | |
| 2127 | /// Propagate address and region provenance through one instruction. |
| 2128 | fn flowInstr(v: &mut Verifier, instr: il::Instr) -> bool throws (Error) { |
| 2129 | match instr { |
| 2130 | case il::Instr::Reserve { dst, .. } => { |
| 2131 | let changed = not v.defs[dst.n].foreign; |
| 2132 | set v.defs[dst.n].foreign = true; |
| 2133 | return changed; |
| 2134 | } |
| 2135 | case il::Instr::Copy { dst, val } => return flowForeign(v, dst, val), |
| 2136 | case il::Instr::Field { dst, src, .. } => return flowForeign(v, dst, il::Val::Reg(src)), |
| 2137 | case il::Instr::Elem { dst, base, .. } => return flowForeign(v, dst, il::Val::Reg(base)), |
| 2138 | case il::Instr::LoadPtr { dst, src, offset, .. } => |
| 2139 | return loadSources(v, dst, src, offset), |
| 2140 | case il::Instr::SliceElem { dst, slice, .. } => return loadSources(v, dst, slice, 0), |
| 2141 | case il::Instr::StorePtr { dst, src, offset } => |
| 2142 | return storeSources(v, dst, offset, src), |
| 2143 | case il::Instr::SliceNew { dst, base, count, .. } => { |
| 2144 | return count > 0 and storeSources(v, dst, 0, base); |
| 2145 | } |
| 2146 | case il::Instr::SliceSub { dst, src, layout: e, .. } => { |
| 2147 | let d = try sliceDest(v, dst, e); |
| 2148 | let mut changed = flowCell( |
| 2149 | v, dst, cellAt(v, dst, 0), src, cellAt(v, src, 0), RegionFlow::Value |
| 2150 | ); |
| 2151 | for i in 0 .. v.ctx.table.layouts[e].regions { |
| 2152 | let to = pointeeCell(v, dst, 0, i); |
| 2153 | let from = pointeeCell(v, src, 0, i); |
| 2154 | let shared = d.slot.mutable or v.ctx.table.infos[e].shared[i]; |
| 2155 | let flow = RegionFlow::Alias if shared else RegionFlow::Value; |
| 2156 | if flowCell(v, dst, to, src, from, flow) { |
| 2157 | set changed = true; |
| 2158 | } |
| 2159 | } |
| 2160 | return changed; |
| 2161 | } |
| 2162 | case il::Instr::SliceCopy { dst, src, layout: e } => { |
| 2163 | let mut changed = false; |
| 2164 | for i in 0 .. v.ctx.table.layouts[e].regions { |
| 2165 | if flowCell( |
| 2166 | v, |
| 2167 | dst, |
| 2168 | pointeeCell(v, dst, 0, i), |
| 2169 | src, |
| 2170 | pointeeCell(v, src, 0, i), |
| 2171 | copiedRegion(v, e, i) |
| 2172 | ) { |
| 2173 | set changed = true; |
| 2174 | } |
| 2175 | } |
| 2176 | return changed; |
| 2177 | } |
| 2178 | case il::Instr::TraitCopy { dst, src } => { |
| 2179 | let cell = cellAt(v, src, 0) else return false; |
| 2180 | return taintSlot(v, dst, 0, foreignCell(v, src, cell)); |
| 2181 | } |
| 2182 | case il::Instr::TraitNew { dst, recv, .. } => |
| 2183 | return taintSlot(v, dst, 0, foreignRef(v, il::Val::Reg(recv))), |
| 2184 | case il::Instr::Blit { dst, src, layout, .. } => return flowView(v, dst, src, layout), |
| 2185 | case il::Instr::UnionGet { dst, src, tag, offset, layout: l } => { |
| 2186 | let mut changed = false; |
| 2187 | for i in 0 .. v.ctx.table.layouts[l].regions { |
| 2188 | let to = cellOf(v, dst, l, i); |
| 2189 | if flowCell(v, dst, to, src, unionCell(v, src, tag, offset, l, i), copiedRegion( |
| 2190 | v, l, i |
| 2191 | )) { |
| 2192 | set changed = true; |
| 2193 | } |
| 2194 | } |
| 2195 | return changed; |
| 2196 | } |
| 2197 | case il::Instr::UnionSet { dst, src, tag, offset, layout } => { |
| 2198 | let case il::Val::Reg(r) = src else return false; |
| 2199 | let l = layout else return false; |
| 2200 | let mut changed = false; |
| 2201 | for i in 0 .. v.ctx.table.layouts[l].regions { |
| 2202 | let to = unionCell(v, dst, tag, offset, l, i); |
| 2203 | if flowCell(v, dst, to, r, cellOf(v, r, l, i), copiedRegion(v, l, i)) { |
| 2204 | set changed = true; |
| 2205 | } |
| 2206 | } |
| 2207 | return changed; |
| 2208 | } |
| 2209 | case il::Instr::Call { retTy, dst, func: callee, args } => { |
| 2210 | let case RegState::Fn(f) = try operand(v, callee) else return false; |
| 2211 | let borrows = sigBorrows(&v.ctx, f.sig); |
| 2212 | let func = v.func; |
| 2213 | let values = il::argVals(func, args); |
| 2214 | let mut changed = false; |
| 2215 | for borrow in borrows { |
| 2216 | let case il::Val::Reg(a) = values[borrow.param] else continue; |
| 2217 | let mut sourcePlace = RegionPlace::Reachable; |
| 2218 | if let source = borrow.source { |
| 2219 | let case il::ValType::Ptr(p) = sigParam(&v.ctx, f.sig, borrow.param) |
| 2220 | else panic "flowInstr: expected source pointer"; |
| 2221 | let cell = cellOf(v, a, p.layout, source) else continue; |
| 2222 | set sourcePlace = RegionPlace::Cell(cell); |
| 2223 | } |
| 2224 | if let t = borrow.target { |
| 2225 | let case il::Val::Reg(object) = values[t] else continue; |
| 2226 | let case il::ValType::Ptr(p) = sigParam(&v.ctx, f.sig, t) |
| 2227 | else panic "flowInstr: expected target pointer"; |
| 2228 | let cell = cellOf(v, object, p.layout, borrow.result) else continue; |
| 2229 | if flowRegion(v, object, RegionPlace::Cell(cell), a, sourcePlace, copiedRegion( |
| 2230 | v, p.layout, borrow.result |
| 2231 | )) { |
| 2232 | set changed = true; |
| 2233 | } |
| 2234 | } else if resultBuffer(retTy, borrows) { |
| 2235 | let case il::Val::Reg(buffer) = values[0] else continue; |
| 2236 | let case il::ValType::Ptr(p) = sigParam(&v.ctx, f.sig, 0) |
| 2237 | else panic "flowInstr: expected output pointer"; |
| 2238 | let cell = cellOf(v, buffer, p.layout, borrow.result) else continue; |
| 2239 | if flowRegion(v, buffer, RegionPlace::Cell(cell), a, sourcePlace, copiedRegion( |
| 2240 | v, p.layout, borrow.result |
| 2241 | )) { |
| 2242 | set changed = true; |
| 2243 | } |
| 2244 | } else if let r = dst { |
| 2245 | if try flowResult(v, r, retTy, borrow.result, a, sourcePlace) { |
| 2246 | set changed = true; |
| 2247 | } |
| 2248 | } |
| 2249 | } |
| 2250 | return changed; |
| 2251 | } |
| 2252 | case il::Instr::TraitCall { dst, .. } => { |
| 2253 | let reg = dst else return false; |
| 2254 | return markForeign(v, reg); |
| 2255 | } |
| 2256 | case il::Instr::Jmp { target, args } => return flowEdge(v, target, args), |
| 2257 | case il::Instr::Br { thenTarget, thenArgs, elseTarget, elseArgs, .. } => { |
| 2258 | let a = flowEdge(v, thenTarget, thenArgs); |
| 2259 | let b = flowEdge(v, elseTarget, elseArgs); |
| 2260 | return a or b; |
| 2261 | } |
| 2262 | case il::Instr::Switch { defaultTarget, defaultArgs, cases, .. } => { |
| 2263 | let mut changed = flowEdge(v, defaultTarget, defaultArgs); |
| 2264 | let func = v.func; |
| 2265 | for branch in il::switchCases(func, cases) { |
| 2266 | if flowEdge(v, branch.target, branch.args) { |
| 2267 | set changed = true; |
| 2268 | } |
| 2269 | } |
| 2270 | return changed; |
| 2271 | } |
| 2272 | else => return false, |
| 2273 | } |
| 2274 | } |
| 2275 | |
| 2276 | /// Whether typed instructions read or pass on the result buffer. A direct |
| 2277 | /// destination write cannot expose old contents. Address aliases and argument |
| 2278 | /// ranges count as inputs. |
| 2279 | fn readsResultBuffer(func: *il::Fn) -> bool { |
| 2280 | let buffer = func.params[0].value; |
| 2281 | for block in func.blocks { |
| 2282 | for instr in block.instrs { |
| 2283 | let mut input = false; |
| 2284 | match instr { |
| 2285 | case il::Instr::Blit { src, .. } => set input = src == buffer, |
| 2286 | case il::Instr::SliceSub { src, .. } => set input = src == buffer, |
| 2287 | case il::Instr::TraitCopy { src, .. } => set input = src == buffer, |
| 2288 | case il::Instr::UnionGet { src, .. } => set input = src == buffer, |
| 2289 | case il::Instr::StorePtr { src, .. } => set input = src == il::Val::Reg(buffer), |
| 2290 | case il::Instr::UnionSet { src, .. } => set input = src == il::Val::Reg(buffer), |
| 2291 | case il::Instr::SliceNew { base, .. } => set input = base == il::Val::Reg(buffer), |
| 2292 | case il::Instr::TraitNew { recv, .. } => set input = recv == buffer, |
| 2293 | // Data operands observe addresses without following their protected contents. |
| 2294 | // Direct page outputs replace the slot contents. |
| 2295 | case |
| 2296 | il::Instr::Store { .. }, |
| 2297 | il::Instr::BinOp { .. }, |
| 2298 | il::Instr::UnOp { .. }, |
| 2299 | il::Instr::Zext { .. }, |
| 2300 | il::Instr::Sext { .. }, |
| 2301 | il::Instr::PageSlice { .. }, |
| 2302 | il::Instr::PageHeap { .. } => |
| 2303 | {} |
| 2304 | else => set input = il::usesReg(func, &instr, buffer), |
| 2305 | } |
| 2306 | if input { |
| 2307 | return true; |
| 2308 | } |
| 2309 | } |
| 2310 | } |
| 2311 | return false; |
| 2312 | } |
| 2313 | |
| 2314 | /// Start from foreign facts everywhere, except the sources that the signature |
| 2315 | /// permits for region `region` of the result, or of the object of parameter |
| 2316 | /// `target`, which also keeps its own region. Grow the facts to a fixed point. |
| 2317 | fn permit(v: &mut Verifier, target: ?u32, region: u32, bufferInput: bool) throws (Error) { |
| 2318 | let func = v.func; |
| 2319 | for i in 0 .. v.defs.len { |
| 2320 | set v.defs[i].foreign = false; |
| 2321 | } |
| 2322 | for i in 0 .. v.cells.len { |
| 2323 | set v.cells[i] = false; |
| 2324 | } |
| 2325 | for param in func.params { |
| 2326 | set v.defs[param.value.n].foreign = true; |
| 2327 | if bufferInput or not v.frame[param.value.n] { |
| 2328 | for i in 0 .. cellCount(v, param.value) { |
| 2329 | let _ = markCell(v, param.value, i); |
| 2330 | } |
| 2331 | } |
| 2332 | } |
| 2333 | // Each output can retain its own contents. Other input regions need a declared source. |
| 2334 | let mut output = target; |
| 2335 | if output == nil and resultBuffer(func.returnType, func.borrows) { |
| 2336 | set output = 0; |
| 2337 | } |
| 2338 | if let t = output { |
| 2339 | set v.cells[func.params[t].value.n * v.cellWidth + region] = false; |
| 2340 | } |
| 2341 | for borrow in func.borrows { |
| 2342 | if borrow.target <> target or borrow.result <> region { |
| 2343 | continue; |
| 2344 | } |
| 2345 | let r = func.params[borrow.param].value; |
| 2346 | if let source = borrow.source { |
| 2347 | set v.cells[r.n * v.cellWidth + source] = false; |
| 2348 | } else { |
| 2349 | set v.defs[r.n].foreign = false; |
| 2350 | for i in 0 .. cellCount(v, r) { |
| 2351 | set v.cells[r.n * v.cellWidth + i] = false; |
| 2352 | } |
| 2353 | } |
| 2354 | } |
| 2355 | let mut changed = true; |
| 2356 | while changed { |
| 2357 | set changed = false; |
| 2358 | for n in 0 .. func.blocks.len { |
| 2359 | set v.block = v.flow.order[n]; |
| 2360 | for instr in func.blocks[v.block].instrs { |
| 2361 | if try flowInstr(v, instr) { |
| 2362 | set changed = true; |
| 2363 | } |
| 2364 | } |
| 2365 | } |
| 2366 | } |
| 2367 | } |
| 2368 | |
| 2369 | /// Whether a function has an instruction that can write a pointer into an object. |
| 2370 | fn writesPointers(func: *il::Fn) -> bool { |
| 2371 | for block in func.blocks { |
| 2372 | for instr in block.instrs { |
| 2373 | match instr { |
| 2374 | case |
| 2375 | il::Instr::StorePtr { .. }, |
| 2376 | il::Instr::SliceNew { .. }, |
| 2377 | il::Instr::SliceSub { .. }, |
| 2378 | il::Instr::SliceCopy { .. }, |
| 2379 | il::Instr::TraitNew { .. }, |
| 2380 | il::Instr::TraitCopy { .. }, |
| 2381 | il::Instr::Blit { .. }, |
| 2382 | il::Instr::UnionGet { .. }, |
| 2383 | il::Instr::UnionSet { .. }, |
| 2384 | il::Instr::Call { .. } => |
| 2385 | return true, |
| 2386 | else => {} |
| 2387 | } |
| 2388 | } |
| 2389 | } |
| 2390 | return false; |
| 2391 | } |
| 2392 | |
| 2393 | /// Check each region of the result, and of the object of each target parameter, |
| 2394 | /// against the sources that the signature permits for it. |
| 2395 | fn checkBorrow(v: &mut Verifier) throws (Error) { |
| 2396 | let func = v.func; |
| 2397 | let buffered = resultBuffer(func.returnType, func.borrows); |
| 2398 | let bufferInput = buffered and readsResultBuffer(func); |
| 2399 | let mut count: u32 = 0; |
| 2400 | let mut address: u32 = 1; |
| 2401 | let mut pointee: ?u32 = nil; |
| 2402 | if buffered { |
| 2403 | set count = cellCount(v, func.params[0].value); |
| 2404 | } else if let case il::ValType::Ptr(p) = func.returnType; hasResult(func.borrows) { |
| 2405 | // An owning result has the regions of its pointee, and no address region. |
| 2406 | set address = 0 if p.own else 1; |
| 2407 | set count = address + v.ctx.table.layouts[p.layout].regions; |
| 2408 | set pointee = p.layout; |
| 2409 | } |
| 2410 | for region in 0 .. count { |
| 2411 | try permit(v, nil, region, bufferInput); |
| 2412 | for b in 0 .. func.blocks.len { |
| 2413 | set v.block = b; |
| 2414 | for instr, i in func.blocks[b].instrs { |
| 2415 | set v.instr = i; |
| 2416 | let case il::Instr::Ret { val } = instr else continue; |
| 2417 | if region < address { |
| 2418 | if let r = val; foreignRef(v, r) { |
| 2419 | throw fail(v, Rule::Return); |
| 2420 | } |
| 2421 | } else if let case il::Val::Reg(r) = val { |
| 2422 | let l = pointee else panic "checkBorrow: expected pointer result"; |
| 2423 | if let cell = cellOf(v, r, l, region - address); foreignCell(v, r, cell) { |
| 2424 | throw fail(v, Rule::Return); |
| 2425 | } |
| 2426 | } |
| 2427 | } |
| 2428 | } |
| 2429 | if buffered and foreignCell(v, func.params[0].value, region) { |
| 2430 | throw failFn(v.fnIndex, Rule::Return); |
| 2431 | } |
| 2432 | } |
| 2433 | if not writesPointers(func) { |
| 2434 | return; |
| 2435 | } |
| 2436 | for param, k in func.params { |
| 2437 | if not v.target[param.value.n] { |
| 2438 | continue; |
| 2439 | } |
| 2440 | for region in 0 .. cellCount(v, param.value) { |
| 2441 | try permit(v, k, region, bufferInput); |
| 2442 | if foreignCell(v, param.value, region) { |
| 2443 | throw failFn(v.fnIndex, Rule::Return); |
| 2444 | } |
| 2445 | } |
| 2446 | } |
| 2447 | } |
| 2448 | |
| 2449 | ////////////////// |
| 2450 | // Entry points // |
| 2451 | ////////////////// |
| 2452 | |
| 2453 | /// Create an empty name dictionary for `count` names. |
| 2454 | fn newDict(count: u32, a: &heap::Heap) -> dict::Dict throws (Error) { |
| 2455 | if count > SYMBOLS_MAX { |
| 2456 | throw Error { rule: Rule::Limit, place: Place::Package }; |
| 2457 | } |
| 2458 | let mut size = DICT_MINIMUM; |
| 2459 | while size < count * 2 { |
| 2460 | set size *= 2; |
| 2461 | } |
| 2462 | let mut entries: *mut [dict::Entry] = &mut []; |
| 2463 | try entries.resize(size, dict::Entry { key: &[], value: 0 }, a) catch { |
| 2464 | throw STORAGE; |
| 2465 | }; |
| 2466 | return dict::fresh(entries); |
| 2467 | } |
| 2468 | |
| 2469 | /// Check the tables of a program and index its symbols. |
| 2470 | fn prepare(program: &il::Program, config: Config, a: &heap::Heap) -> Context throws (Error) { |
| 2471 | let table = try layout::build(program.layouts, config, a); |
| 2472 | let mut fnNames = try newDict(program.fns.len, a); |
| 2473 | for i in 0 .. program.fns.len { |
| 2474 | let name = program.fns[i].name; |
| 2475 | if name.len == 0 or dict::get(&fnNames, name) <> nil { |
| 2476 | throw failFn(i, Rule::Symbol); |
| 2477 | } |
| 2478 | try dict::insert(&mut fnNames, name, i as i32) catch { |
| 2479 | throw STORAGE; |
| 2480 | }; |
| 2481 | } |
| 2482 | let mut dataNames = try newDict(program.data.len, a); |
| 2483 | for i in 0 .. program.data.len { |
| 2484 | let name = program.data[i].name; |
| 2485 | let at = Place::Data(i); |
| 2486 | if name.len == 0 or dict::get(&dataNames, name) <> nil or dict::get(&fnNames, name) <> nil { |
| 2487 | throw Error { rule: Rule::Symbol, place: at }; |
| 2488 | } |
| 2489 | try dict::insert(&mut dataNames, name, i as i32) catch { |
| 2490 | throw STORAGE; |
| 2491 | }; |
| 2492 | } |
| 2493 | let c = Context { |
| 2494 | prog: *program, |
| 2495 | config, |
| 2496 | table, |
| 2497 | fnNames, |
| 2498 | dataNames, |
| 2499 | localFunctions: program.fns.len, |
| 2500 | localData: program.data.len, |
| 2501 | }; |
| 2502 | try checkSignatures(&c); |
| 2503 | try checkTraits(&c); |
| 2504 | return c; |
| 2505 | } |
| 2506 | |
| 2507 | /// Check data, function declarations and function bodies. |
| 2508 | fn finish(c: Context, a: &heap::Heap) throws (Error) { |
| 2509 | try data::check(&c, a); |
| 2510 | let sizes = try measure(&c); |
| 2511 | if c.prog.fns.len == 0 { |
| 2512 | return; |
| 2513 | } |
| 2514 | let mut defs: *mut [Def] = &mut []; |
| 2515 | try defs.resize( |
| 2516 | sizes.registers, |
| 2517 | Def { |
| 2518 | state: RegState::Data, block: 0, owner: NO_OWNER, foreign: false |
| 2519 | }, |
| 2520 | a |
| 2521 | ) catch { |
| 2522 | throw STORAGE; |
| 2523 | }; |
| 2524 | let tables = try flow::new(sizes.blocks, sizes.edges, a); |
| 2525 | let mut frame: *mut [bool] = &mut []; |
| 2526 | try frame.resize(sizes.registers, false, a) catch { |
| 2527 | throw STORAGE; |
| 2528 | }; |
| 2529 | let mut target: *mut [bool] = &mut []; |
| 2530 | try target.resize(sizes.registers, false, a) catch { |
| 2531 | throw STORAGE; |
| 2532 | }; |
| 2533 | let mut cellWidth: u32 = 0; |
| 2534 | for item in c.table.layouts { |
| 2535 | if item.regions > cellWidth { |
| 2536 | set cellWidth = item.regions; |
| 2537 | } |
| 2538 | } |
| 2539 | let cellSize = cellWidth as u64 * sizes.registers as u64; |
| 2540 | if cellSize > 0xffffffff { |
| 2541 | throw Error { rule: Rule::Limit, place: Place::Package }; |
| 2542 | } |
| 2543 | let mut cells: *mut [bool] = &mut []; |
| 2544 | try cells.resize(cellSize as u32, false, a) catch { |
| 2545 | throw STORAGE; |
| 2546 | }; |
| 2547 | let first = c.prog.fns[0]; |
| 2548 | let mut v = Verifier { |
| 2549 | ctx: c, |
| 2550 | flow: tables, |
| 2551 | defs, |
| 2552 | frame, |
| 2553 | target, |
| 2554 | cells, |
| 2555 | cellWidth, |
| 2556 | func: first, |
| 2557 | fnIndex: 0, |
| 2558 | block: 0, |
| 2559 | instr: 0, |
| 2560 | }; |
| 2561 | for fi in 0 .. v.ctx.prog.fns.len { |
| 2562 | set v.func = v.ctx.prog.fns[fi]; |
| 2563 | if v.func.isExtern { |
| 2564 | continue; |
| 2565 | } |
| 2566 | set v.fnIndex = fi; |
| 2567 | try checkFn(&mut v); |
| 2568 | try checkBorrow(&mut v); |
| 2569 | } |
| 2570 | } |
| 2571 | |
| 2572 | /// Verify the data, layouts and functions of a program. The scratch arena holds the |
| 2573 | /// working tables, and is not reclaimed. |
| 2574 | export fn verifyProgram(program: &il::Program, config: Config, scratch: &heap::Heap) |
| 2575 | throws (Error) |
| 2576 | { |
| 2577 | let c = try prepare(program, config, scratch); |
| 2578 | try finish(c, scratch); |
| 2579 | } |
| 2580 | |
| 2581 | /// Whether a type is data or void. |
| 2582 | fn isData(t: il::ValType) -> bool { |
| 2583 | match t { |
| 2584 | case il::ValType::Void, il::ValType::Data(_) => return true, |
| 2585 | else => return false, |
| 2586 | } |
| 2587 | } |
| 2588 | |
| 2589 | /// Check the rules of a loadable package that [`verifyProgram`] does not cover. |
| 2590 | /// Local definitions have bodies, and the domain entry takes no parameter or one |
| 2591 | /// pointer to the plain Env record. Imports are checked against their providers. |
| 2592 | fn checkPackage(package: &binary::Package, c: &Context) throws (Error) { |
| 2593 | let bad = Error { rule: Rule::Package, place: Place::Package }; |
| 2594 | for i in 0 .. package.program.fns.len { |
| 2595 | if package.program.fns[i].isExtern { |
| 2596 | throw failFn(i, Rule::Package); |
| 2597 | } |
| 2598 | } |
| 2599 | if let name = package.entry { |
| 2600 | let index = dict::get(&c.fnNames, name) else { |
| 2601 | throw bad; |
| 2602 | }; |
| 2603 | if index as u32 >= c.localFunctions { |
| 2604 | throw bad; |
| 2605 | } |
| 2606 | let func = package.program.fns[index as u32]; |
| 2607 | if func.params.len > 1 { |
| 2608 | throw failFn(index as u32, Rule::Package); |
| 2609 | } |
| 2610 | for param in func.params { |
| 2611 | let case il::ValType::Ptr(env) = param.type else { |
| 2612 | throw failFn(index as u32, Rule::Package); |
| 2613 | }; |
| 2614 | if not env.own |
| 2615 | or env.mutable |
| 2616 | or env.nullable |
| 2617 | or not layout::isPlain( |
| 2618 | &c.table, env.layout |
| 2619 | ) |
| 2620 | or layout::size(&c.table, env.layout) > c.config.envSize as u64 |
| 2621 | { |
| 2622 | throw failFn(index as u32, Rule::Package); |
| 2623 | } |
| 2624 | } |
| 2625 | } |
| 2626 | for item, i in package.exports { |
| 2627 | if i > 0 and mem::cmp(package.exports[i - 1].name, item.name) >= 0 { |
| 2628 | throw bad; |
| 2629 | } |
| 2630 | match item.kind { |
| 2631 | case binary::ExportKind::Function(index) => { |
| 2632 | if index >= c.localFunctions |
| 2633 | or not mem::eq(package.program.fns[index].name, item.name) |
| 2634 | { |
| 2635 | throw bad; |
| 2636 | } |
| 2637 | } |
| 2638 | case binary::ExportKind::Data(index) => { |
| 2639 | if index >= c.localData |
| 2640 | or not mem::eq(package.program.data[index].name, item.name) |
| 2641 | { |
| 2642 | throw bad; |
| 2643 | } |
| 2644 | } |
| 2645 | } |
| 2646 | } |
| 2647 | } |
| 2648 | |
| 2649 | /// Number of arguments that the kernel passes to a new context, in registers a0 and a1. |
| 2650 | /// The kernel defines no other argument, and a parameter past the argument registers would |
| 2651 | /// be read from above the fresh stack. |
| 2652 | constant START_ARGS: u32 = 2; |
| 2653 | |
| 2654 | /// Whether an exported function accepts the plain arguments of a fresh context. |
| 2655 | /// The domain entry uses its separate Env contract. |
| 2656 | fn startable(package: &binary::Package, index: u32) -> bool { |
| 2657 | let func = package.program.fns[index]; |
| 2658 | if let entry = package.entry { |
| 2659 | if mem::eq(entry, func.name) { |
| 2660 | return false; |
| 2661 | } |
| 2662 | } |
| 2663 | if func.params.len > START_ARGS or not isData(func.returnType) { |
| 2664 | return false; |
| 2665 | } |
| 2666 | for param in func.params { |
| 2667 | if not isData(param.type) { |
| 2668 | return false; |
| 2669 | } |
| 2670 | } |
| 2671 | return true; |
| 2672 | } |
| 2673 | |
| 2674 | /// Classify public functions for checked library calls and fresh context creation. |
| 2675 | /// The retained export metadata is allocated from keep and must outlive the package. |
| 2676 | fn classifyExports(package: &mut binary::Package, keep: &heap::Heap) throws (Error) { |
| 2677 | let mut kept: *mut [binary::Export] = &mut []; |
| 2678 | try kept.reserve(package.exports.len, keep) catch { |
| 2679 | throw STORAGE; |
| 2680 | }; |
| 2681 | for item in package.exports { |
| 2682 | let mut eligible = false; |
| 2683 | if let case binary::ExportKind::Function(index) = item.kind { |
| 2684 | set eligible = startable(package, index); |
| 2685 | } |
| 2686 | try kept.append( |
| 2687 | binary::Export { |
| 2688 | name: item.name, kind: item.kind, startable: eligible |
| 2689 | }, |
| 2690 | keep |
| 2691 | ) catch { |
| 2692 | throw STORAGE; |
| 2693 | }; |
| 2694 | } |
| 2695 | set package.exports = &kept[..]; |
| 2696 | } |
| 2697 | |
| 2698 | /// Verify a loadable package with a safe domain entry. Public functions retain their |
| 2699 | /// checked call contracts and receive separate fresh-context entry classifications. |
| 2700 | /// Derived export metadata in keep must outlive the package. |
| 2701 | export fn verifyPackage( |
| 2702 | package: &mut binary::Package, |
| 2703 | config: Config, |
| 2704 | scratch: &heap::Heap, |
| 2705 | keep: &heap::Heap |
| 2706 | ) throws (Error) { |
| 2707 | try verifyLinkedPackage(package, &[], config, scratch, keep); |
| 2708 | } |
| 2709 | |
| 2710 | /// Verify local bodies and every import against already verified dependency images. |
| 2711 | /// Providers are in exact dependency order and must describe immutable resident code. |
| 2712 | /// Derived export classifications are retained in keep; scratch holds only temporary data. |
| 2713 | export fn verifyLinkedPackage( |
| 2714 | package: &mut binary::Package, |
| 2715 | providers: &[linking::Provider], |
| 2716 | config: Config, |
| 2717 | scratch: &heap::Heap, |
| 2718 | keep: &heap::Heap |
| 2719 | ) throws (Error) { |
| 2720 | set package.links.verified = false; |
| 2721 | let resolved = try linking::bind(package, providers, scratch); |
| 2722 | let mut c = try prepare(&resolved, config, scratch); |
| 2723 | set c.localFunctions = package.program.fns.len; |
| 2724 | set c.localData = package.program.data.len; |
| 2725 | try checkPackage(package, &c); |
| 2726 | try classifyExports(package, keep); |
| 2727 | try finish(c, scratch); |
| 2728 | set package.links.verified = true; |
| 2729 | } |