.githooks/
compiler/
kernel/
lib/
examples/
std/
arch/
bits/
char/
collections/
fs/
hash/
lang/
alloc/
ast/
gen/
il/
binary/
link/
printer/
verify/
data.rad
12.4 KiB
flow.rad
6.9 KiB
layout.rad
30.9 KiB
linking.rad
7.2 KiB
tests.rad
216.6 KiB
binary.rad
14.7 KiB
link.rad
11.8 KiB
printer.rad
31.7 KiB
verify.rad
99.5 KiB
layout/
lower/
manifest/
module/
parser/
resolver/
scanner/
sexpr/
alloc.rad
1.2 KiB
ast.rad
36.0 KiB
gen.rad
513 B
il.rad
48.5 KiB
layout.rad
6.9 KiB
lower.rad
487.6 KiB
manifest.rad
22.5 KiB
module.rad
17.8 KiB
package.rad
1.5 KiB
parser.rad
114.1 KiB
pretty.rad
103.6 KiB
resolver.rad
508.1 KiB
scanner.rad
19.3 KiB
sexpr.rad
7.1 KiB
strings.rad
3.3 KiB
types.rad
620 B
mem/
sys/
arch.rad
68 B
bits.rad
1.6 KiB
char.rad
1.5 KiB
collections.rad
39 B
fmt.rad
11.6 KiB
fs.rad
11.0 KiB
hash.rad
41 B
intrinsics.rad
467 B
io.rad
1.7 KiB
lang.rad
335 B
mem.rad
12.0 KiB
mem.ras
919 B
process.rad
6.2 KiB
std.manifest
4.9 KiB
std.rad
349 B
sys.rad
1.0 KiB
testing.rad
2.4 KiB
tests.rad
26.6 KiB
vec.rad
3.2 KiB
scripts/
seed/
sublime/
test/
vim/
.gitignore
333 B
.gitsigners
224 B
AGENTS.md
8.3 KiB
CONTRIBUTING
2.1 KiB
LICENSE
1.1 KiB
Makefile
2.5 KiB
README
3.4 KiB
STYLE
3.2 KiB
std.lib
2.1 KiB
std.lib.test
1.1 KiB
lib/std/lang/il/verify/data.rad
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 | } |