lib/std/lang/il/verify.rad 99.5 KiB 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
}