lib/std/lang/il/verify/data.rad 12.4 KiB raw
1
//! Data initializer checks of the RIL verifier.
2
//!
3
//! Static memory starts as the initializer says, and every byte that the initializer
4
//! leaves out or marks undefined is zero. Pointer and function slots may start as zero
5
//! or hold the address of a symbol that fits the slot. Trait object slots start as zero. A union
6
//! slot holds the tag of one of its variants and a payload that fits the layout of that variant,
7
//! including unions nested in a payload. Bytes outside slots are free.
8
9
use std::collections::dict;
10
use std::lang::il;
11
use std::lang::il::verify;
12
use std::lang::il::verify::layout;
13
use std::mem;
14
use std::mem::heap;
15
16
/// Offset of the length within a slice slot.
17
constant SLICE_LEN: u64 = 8;
18
/// Byte offset of the capacity in a slice slot.
19
constant SLICE_CAP: u64 = 12;
20
21
/// A slice slot whose pointer holds a symbol and whose capacity is not checked.
22
record Pending: Copy {
23
    /// Byte offset of the slice slot.
24
    start: u64,
25
    /// Index of the data symbol that the slice points to.
26
    target: u32,
27
    /// Length that the slice has, which its capacity must equal. Zero until the length item.
28
    len: u64,
29
}
30
31
/// The tag byte of the last union slot that the initializer reached.
32
record UnionTag: Copy {
33
    /// Byte offset of the union slot in the data.
34
    start: u64,
35
    /// Tag byte of the union.
36
    tag: u64,
37
}
38
39
/// What the initializer has said about the slots that it passed.
40
record Live {
41
    /// The slice slot whose capacity is not checked.
42
    pending: ?Pending,
43
    /// The last union slot at each payload nesting level.
44
    tags: *mut [?UnionTag],
45
}
46
47
/// Build the error for a rule violation in data `index`.
48
fn fail(index: u32, rule: verify::Rule) -> verify::Error {
49
    return verify::Error { rule, place: verify::Place::Data(index) };
50
}
51
52
/// Width in bytes of one repetition of an item.
53
fn width(item: il::DataItem) -> u64 {
54
    match item {
55
        case il::DataItem::Val { typ, .. }             => return il::typeSize(typ) as u64,
56
        case il::DataItem::Sym(_), il::DataItem::Fn(_) => return layout::WORD,
57
        case il::DataItem::Str(text)                   => return text.len as u64,
58
        case il::DataItem::Undef                       => return 1,
59
    }
60
}
61
62
/// Whether an item is zero. Undefined bytes are zero in the image.
63
fn isZero(item: il::DataItem) -> bool {
64
    match item {
65
        case il::DataItem::Val { val, .. } => return val == 0,
66
        case il::DataItem::Undef           => return true,
67
        else                               => return false,
68
    }
69
}
70
71
/// Check one repetition of an item at byte `pos` of data `index`, including
72
/// slots in nested payload layouts. Each nested layout has a byte offset from
73
/// the start of the data. `symbol` is the index of the data definition or
74
/// function that a symbol item names.
75
fn atom(
76
    c: &verify::Context,
77
    index: u32,
78
    pos: u64,
79
    item: il::DataItem,
80
    symbol: u32,
81
    live: &mut Live
82
) throws (verify::Error) {
83
    let t = &c.table;
84
    let zero = isZero(item);
85
    let mut l = c.prog.data[index].layout;
86
    let mut base: u64 = 0;
87
    let mut pos = pos;
88
    // Payload nesting level of the current layout.
89
    let mut depth: u32 = 0;
90
    // A nonzero length needs an explicit capacity of the same value.
91
    if zero {
92
        if let last = live.pending; last.len <> 0 {
93
            throw fail(index, verify::Rule::Data);
94
        }
95
    }
96
    loop {
97
        let end = pos + width(item);
98
        let leaf = layout::leafAround(t, l, pos) else {
99
            // The item starts in plain bytes, and must not run into a slot. A symbol in the payload
100
            // of a union variant needs a slot of that variant.
101
            if not layout::plain(t, l, pos, end) {
102
                throw fail(index, verify::Rule::Data);
103
            }
104
            if base <> 0 and not zero {
105
                let case il::DataItem::Val { .. } = item else throw fail(index, verify::Rule::Data);
106
            }
107
            return;
108
        };
109
        if end > leaf.start + layout::slotWidth(t, leaf.kind) {
110
            throw fail(index, verify::Rule::Data);
111
        }
112
        if let case il::SlotKind::Union { offset: payload, variants, .. } = leaf.kind {
113
            // Each payload nesting level keeps the tag of its current union.
114
            let start = base + leaf.start;
115
            let rel = pos - leaf.start;
116
            if zero and rel == 0 {
117
                set live.tags[depth] = UnionTag { start, tag: 0 };
118
            }
119
            if zero {
120
                return;
121
            }
122
            if rel >= 1 and rel < payload as u64 {
123
                throw fail(index, verify::Rule::Data);
124
            }
125
            if rel == 0 {
126
                let case il::DataItem::Val { typ: il::Type::W8, val } = item
127
                    else throw fail(index, verify::Rule::Data);
128
                if layout::variantWith(variants, val as u64 & 0xff) == nil {
129
                    throw fail(index, verify::Rule::Data);
130
                }
131
                set live.tags[depth] = UnionTag { start, tag: val as u64 & 0xff };
132
                return;
133
            }
134
            // The payload fits the layout of the variant that the tag names.
135
            let mut tag: u64 = 0;
136
            if let seen = live.tags[depth]; seen.start == start {
137
                set tag = seen.tag;
138
            }
139
            let variant = layout::variantWith(variants, tag)
140
                else throw fail(index, verify::Rule::Data);
141
            let inner = variant.layout else throw fail(index, verify::Rule::Data);
142
            set l = inner;
143
            set base = start + payload as u64;
144
            set pos = rel - payload as u64;
145
            set depth += 1;
146
            continue;
147
        }
148
        if zero {
149
            return;
150
        }
151
        let start = base + leaf.start;
152
        match leaf.kind {
153
            case il::SlotKind::Ptr(p) => {
154
                let case il::DataItem::Sym(_) = item else {
155
                    throw fail(index, verify::Rule::Data);
156
                };
157
                let data = c.prog.data[symbol];
158
                if pos <> leaf.start
159
                    or data.heap <> nil
160
                    or (p.mutable and data.readOnly)
161
                    or not layout::view(t, data.layout, 0, p.layout)
162
                {
163
                    throw fail(index, verify::Rule::Data);
164
                }
165
            }
166
            case il::SlotKind::Fn(sig) => {
167
                let case il::DataItem::Fn(_) = item else {
168
                    throw fail(index, verify::Rule::Data);
169
                };
170
                if pos <> leaf.start or not verify::sigEq(
171
                    c, verify::SigRef::Table(sig), verify::SigRef::Func(symbol)
172
                )
173
                {
174
                    throw fail(index, verify::Rule::Data);
175
                }
176
            }
177
            case il::SlotKind::Slice(p) => {
178
                let offset = pos - leaf.start;
179
                if offset == 0 {
180
                    // The pointer of a slice, which the length that follows must fit.
181
                    let case il::DataItem::Sym(_) = item else {
182
                        throw fail(index, verify::Rule::Data);
183
                    };
184
                    let data = c.prog.data[symbol];
185
                    if data.heap <> nil or (p.mutable and data.readOnly) {
186
                        throw fail(index, verify::Rule::Data);
187
                    }
188
                    set live.pending = Pending { start, target: symbol, len: 0 };
189
                    return;
190
                }
191
                let case il::DataItem::Val { typ: il::Type::W32, val } = item else {
192
                    throw fail(index, verify::Rule::Data);
193
                };
194
                if offset == SLICE_CAP {
195
                    // The capacity bounds the lengths that programs can set, so it is exactly
196
                    // the length.
197
                    let last = live.pending else {
198
                        throw fail(index, verify::Rule::Data);
199
                    };
200
                    if last.start <> start or (val as u64 & mem::U32_MAX as u64) <> last.len {
201
                        throw fail(index, verify::Rule::Data);
202
                    }
203
                    set live.pending = nil;
204
                    return;
205
                }
206
                if offset <> SLICE_LEN {
207
                    throw fail(index, verify::Rule::Data);
208
                }
209
                // A length of zero needs no pointer.
210
                let len = val as u64 & mem::U32_MAX as u64;
211
                if len == 0 {
212
                    return;
213
                }
214
                let last = live.pending else {
215
                    throw fail(index, verify::Rule::Data);
216
                };
217
                if last.start <> start {
218
                    throw fail(index, verify::Rule::Data);
219
                }
220
                set live.pending = Pending { start, target: last.target, len };
221
                let data = c.prog.data[last.target];
222
                if not layout::arrayView(t, data.layout, 0, p.layout, len as u32) {
223
                    throw fail(index, verify::Rule::Data);
224
                }
225
            }
226
            case il::SlotKind::Trait(_), il::SlotKind::Heap(_) =>
227
                throw fail(index, verify::Rule::Data),
228
            else => panic "atom: leaf slot is a nested object",
229
        }
230
        return;
231
    }
232
}
233
234
/// Check the initializer of data `index` against its layout.
235
fn checkData(c: &verify::Context, index: u32, live: &mut Live) throws (verify::Error) {
236
    let t = &c.table;
237
    let data = c.prog.data[index];
238
    let l = c.prog.layouts[data.layout];
239
    if data.size <> l.size or data.alignment <> l.alignment {
240
        throw fail(index, verify::Rule::Data);
241
    }
242
    // A heap region is zero-filled writable bytes that nothing can address.
243
    if data.heap <> nil
244
        and (data.readOnly
245
            or not data.isZeroInit
246
            or data.values.len <> 0
247
            or t.infos[data.layout].first <> nil)
248
    {
249
        throw fail(index, verify::Rule::Data);
250
    }
251
    // Data outlives every region, so it holds no references, also through owned pointers.
252
    // Several contexts can write mutable data, and a racing writer could combine the
253
    // two words of one slice or trait object with those of another. An owned pointer in mutable
254
    // data would carry such an object to every context, so it counts too.
255
    if t.layouts[data.layout].regions > 0
256
        or (not data.readOnly and t.infos[data.layout].reaches)
257
    {
258
        throw fail(index, verify::Rule::Data);
259
    }
260
    let mut pos: u64 = 0;
261
    for i in 0 .. live.tags.len {
262
        set live.tags[i] = nil;
263
    }
264
    set live.pending = nil;
265
    for value in data.values {
266
        // The symbol names local code or a checked import from resident code.
267
        let mut symbol: u32 = 0;
268
        match value.item {
269
            case il::DataItem::Sym(name) => {
270
                let target = dict::get(&c.dataNames, name) else {
271
                    throw fail(index, verify::Rule::Symbol);
272
                };
273
                set symbol = target as u32;
274
            }
275
            case il::DataItem::Fn(name) => {
276
                let target = dict::get(&c.fnNames, name) else {
277
                    throw fail(index, verify::Rule::Symbol);
278
                };
279
                if c.prog.fns[target as u32].isExtern and target as u32 < c.localFunctions {
280
                    throw fail(index, verify::Rule::Symbol);
281
                }
282
                set symbol = target as u32;
283
            }
284
            else => {}
285
        }
286
        let w = width(value.item);
287
        let total = w * value.count as u64;
288
        if pos + total > data.size as u64 {
289
            throw fail(index, verify::Rule::Data);
290
        }
291
        if w == 0 or layout::plain(t, data.layout, pos, pos + total) {
292
            set pos += total;
293
            continue;
294
        }
295
        for _ in 0 .. value.count {
296
            try atom(c, index, pos, value.item, symbol, live);
297
            set pos += w;
298
        }
299
    }
300
    // Omitted bytes are zero, so a nonempty slice needs a checked capacity.
301
    if let last = live.pending; last.len <> 0 {
302
        throw fail(index, verify::Rule::Data);
303
    }
304
}
305
306
/// Check all data initializers with a shared tag table sized to their layout depth.
307
export fn check(c: &verify::Context, a: &heap::Heap) throws (verify::Error) {
308
    let mut depth: u32 = 0;
309
    for data in c.prog.data {
310
        let needed = c.table.infos[data.layout].depth + 1;
311
        if needed > depth {
312
            set depth = needed;
313
        }
314
    }
315
    let mut tags: *mut [?UnionTag] = &mut [];
316
    try tags.resize(depth, nil, a) catch {
317
        throw verify::STORAGE;
318
    };
319
    let mut live = Live { pending: nil, tags };
320
    for i in 0 .. c.localData {
321
        try checkData(c, i, &mut live);
322
    }
323
}