1use alloc::vec::Vec;
2use core::{fmt, ops::Range};
3
4use crate::{Instruction, opcode};
5
6pub const MAX_INSTRUCTIONS: usize = 4096;
8
9pub const SCRATCH_WORDS: usize = 16;
11
12#[derive(Clone, Copy, Debug, Eq, PartialEq)]
14pub enum LoadWidth {
15 Byte,
17 Half,
19 Word,
21}
22
23impl LoadWidth {
24 const fn bytes(self) -> usize {
25 match self {
26 Self::Byte => 1,
27 Self::Half => 2,
28 Self::Word => 4,
29 }
30 }
31}
32
33pub trait Input {
40 fn len(&self) -> u32;
42
43 fn is_empty(&self) -> bool {
45 self.len() == 0
46 }
47
48 fn load(&self, offset: u32, width: LoadWidth) -> Option<u32>;
50}
51
52pub(crate) fn input_range(length: usize, offset: u32, width: LoadWidth) -> Option<Range<usize>> {
55 let end = offset.checked_add(width.bytes() as u32)?;
56 if end > u32::try_from(length).unwrap_or(u32::MAX) {
57 return None;
58 }
59 Some(usize::try_from(offset).ok()?..usize::try_from(end).ok()?)
60}
61
62impl Input for [u8] {
63 fn len(&self) -> u32 {
64 u32::try_from(<[u8]>::len(self)).unwrap_or(u32::MAX)
65 }
66
67 fn load(&self, offset: u32, width: LoadWidth) -> Option<u32> {
68 let bytes = self.get(input_range(<[u8]>::len(self), offset, width)?)?;
69 match width {
70 LoadWidth::Byte => Some(u32::from(bytes[0])),
71 LoadWidth::Half => Some(u32::from(u16::from_be_bytes([bytes[0], bytes[1]]))),
72 LoadWidth::Word => Some(u32::from_be_bytes([bytes[0], bytes[1], bytes[2], bytes[3]])),
73 }
74 }
75}
76
77#[derive(Clone, Copy, Debug, Eq, PartialEq)]
79#[non_exhaustive]
80pub enum VerifyError {
81 Empty,
83 TooLong {
85 length: usize,
87 },
88 NoMemory,
90 UnsupportedOpcode {
92 pc: usize,
94 code: u16,
96 },
97 ImmediateDivisionByZero {
99 pc: usize,
101 },
102 ImmediateShiftOutOfRange {
104 pc: usize,
106 shift: u32,
108 },
109 ScratchOutOfRange {
111 pc: usize,
113 index: u32,
115 },
116 ScratchUninitialized {
118 pc: usize,
120 index: u32,
122 },
123 JumpOutOfRange {
125 pc: usize,
127 },
128 MissingFinalReturn,
130}
131
132impl fmt::Display for VerifyError {
133 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
134 match self {
135 Self::Empty => formatter.write_str("classic-BPF program is empty"),
136 Self::TooLong { length } => write!(
137 formatter,
138 "classic-BPF program has {length} instructions, limit is {MAX_INSTRUCTIONS}"
139 ),
140 Self::NoMemory => formatter.write_str("classic-BPF allocation failed"),
141 Self::UnsupportedOpcode { pc, code } => {
142 write!(
143 formatter,
144 "unsupported classic-BPF opcode {code:#x} at {pc}"
145 )
146 }
147 Self::ImmediateDivisionByZero { pc } => {
148 write!(formatter, "zero classic-BPF immediate divisor at {pc}")
149 }
150 Self::ImmediateShiftOutOfRange { pc, shift } => write!(
151 formatter,
152 "classic-BPF immediate shift {shift} is out of range at {pc}"
153 ),
154 Self::ScratchOutOfRange { pc, index } => write!(
155 formatter,
156 "classic-BPF scratch index {index} is out of range at {pc}"
157 ),
158 Self::ScratchUninitialized { pc, index } => write!(
159 formatter,
160 "classic-BPF scratch index {index} is not initialized on every path at {pc}"
161 ),
162 Self::JumpOutOfRange { pc } => {
163 write!(formatter, "classic-BPF jump leaves the program at {pc}")
164 }
165 Self::MissingFinalReturn => {
166 formatter.write_str("classic-BPF program does not end in a return")
167 }
168 }
169 }
170}
171
172#[derive(Debug)]
179pub struct Program {
180 instructions: Vec<Instruction>,
181}
182
183impl Program {
184 pub fn verify(instructions: &[Instruction]) -> Result<Self, VerifyError> {
186 verify_program(instructions)?;
187
188 let mut owned = Vec::new();
189 owned
190 .try_reserve_exact(instructions.len())
191 .map_err(|_| VerifyError::NoMemory)?;
192 owned.extend_from_slice(instructions);
193 Ok(Self {
194 instructions: owned,
195 })
196 }
197
198 pub fn try_from_vec(instructions: Vec<Instruction>) -> Result<Self, VerifyError> {
205 verify_program(&instructions)?;
206 Ok(Self { instructions })
207 }
208
209 pub fn instructions(&self) -> &[Instruction] {
211 &self.instructions
212 }
213
214 pub fn len(&self) -> usize {
216 self.instructions.len()
217 }
218
219 pub fn is_empty(&self) -> bool {
223 self.instructions.is_empty()
224 }
225
226 pub fn translate(&self) -> Result<crate::CodeImage, crate::TranslationError> {
233 self.translate_with_profile(crate::InputProfile::BigEndianBytes)
234 }
235
236 pub fn translate_with_profile(
238 &self,
239 profile: crate::InputProfile,
240 ) -> Result<crate::CodeImage, crate::TranslationError> {
241 crate::translate::translate_program(self.instructions(), profile)
242 }
243
244 pub fn evaluate<I: Input + ?Sized>(&self, input: &I) -> u32 {
250 self.evaluate_counted(input).0
251 }
252
253 fn evaluate_counted<I: Input + ?Sized>(&self, input: &I) -> (u32, usize) {
254 let mut accumulator = 0_u32;
255 let mut index = 0_u32;
256 let mut scratch = [0_u32; SCRATCH_WORDS];
257 let mut pc = 0_usize;
258 let mut steps = 0_usize;
259
260 while steps < self.instructions.len() {
261 let instruction = self.instructions[pc];
262 steps += 1;
263
264 match instruction.code {
265 opcode::LD_IMM => accumulator = instruction.k,
266 opcode::LD_W_ABS => {
267 let Some(value) = input.load(instruction.k, LoadWidth::Word) else {
268 return (0, steps);
269 };
270 accumulator = value;
271 }
272 opcode::LD_H_ABS => {
273 let Some(value) = input.load(instruction.k, LoadWidth::Half) else {
274 return (0, steps);
275 };
276 accumulator = value;
277 }
278 opcode::LD_B_ABS => {
279 let Some(value) = input.load(instruction.k, LoadWidth::Byte) else {
280 return (0, steps);
281 };
282 accumulator = value;
283 }
284 opcode::LD_W_IND | opcode::LD_H_IND | opcode::LD_B_IND => {
285 let Some(offset) = index.checked_add(instruction.k) else {
286 return (0, steps);
287 };
288 let width = match instruction.code {
289 opcode::LD_W_IND => LoadWidth::Word,
290 opcode::LD_H_IND => LoadWidth::Half,
291 opcode::LD_B_IND => LoadWidth::Byte,
292 _ => unreachable!(),
293 };
294 let Some(value) = input.load(offset, width) else {
295 return (0, steps);
296 };
297 accumulator = value;
298 }
299 opcode::LD_MEM => accumulator = scratch[instruction.k as usize],
300 opcode::LD_LEN => accumulator = input.len(),
301 opcode::LDX_IMM => index = instruction.k,
302 opcode::LDX_MEM => index = scratch[instruction.k as usize],
303 opcode::LDX_LEN => index = input.len(),
304 opcode::LDX_B_MSH => {
305 let Some(value) = input.load(instruction.k, LoadWidth::Byte) else {
306 return (0, steps);
307 };
308 index = (value & 0x0f) << 2;
309 }
310 opcode::ST => scratch[instruction.k as usize] = accumulator,
311 opcode::STX => scratch[instruction.k as usize] = index,
312 opcode::ALU_ADD_K => accumulator = accumulator.wrapping_add(instruction.k),
313 opcode::ALU_ADD_X => accumulator = accumulator.wrapping_add(index),
314 opcode::ALU_SUB_K => accumulator = accumulator.wrapping_sub(instruction.k),
315 opcode::ALU_SUB_X => accumulator = accumulator.wrapping_sub(index),
316 opcode::ALU_MUL_K => accumulator = accumulator.wrapping_mul(instruction.k),
317 opcode::ALU_MUL_X => accumulator = accumulator.wrapping_mul(index),
318 opcode::ALU_DIV_K => accumulator /= instruction.k,
319 opcode::ALU_DIV_X => {
320 if index == 0 {
321 return (0, steps);
322 }
323 accumulator /= index;
324 }
325 opcode::ALU_OR_K => accumulator |= instruction.k,
326 opcode::ALU_OR_X => accumulator |= index,
327 opcode::ALU_AND_K => accumulator &= instruction.k,
328 opcode::ALU_AND_X => accumulator &= index,
329 opcode::ALU_LSH_K => accumulator = accumulator.wrapping_shl(instruction.k),
330 opcode::ALU_LSH_X => accumulator = accumulator.wrapping_shl(index & 31),
331 opcode::ALU_RSH_K => accumulator = accumulator.wrapping_shr(instruction.k),
332 opcode::ALU_RSH_X => accumulator = accumulator.wrapping_shr(index & 31),
333 opcode::ALU_NEG => accumulator = accumulator.wrapping_neg(),
334 opcode::ALU_MOD_K => accumulator %= instruction.k,
335 opcode::ALU_MOD_X => {
336 if index == 0 {
337 return (0, steps);
338 }
339 accumulator %= index;
340 }
341 opcode::ALU_XOR_K => accumulator ^= instruction.k,
342 opcode::ALU_XOR_X => accumulator ^= index,
343 opcode::JMP_JA => {
344 pc += 1 + instruction.k as usize;
345 continue;
346 }
347 opcode::JMP_JEQ_K
348 | opcode::JMP_JEQ_X
349 | opcode::JMP_JGT_K
350 | opcode::JMP_JGT_X
351 | opcode::JMP_JGE_K
352 | opcode::JMP_JGE_X
353 | opcode::JMP_JSET_K
354 | opcode::JMP_JSET_X => {
355 let operand = if matches!(
356 instruction.code,
357 opcode::JMP_JEQ_X
358 | opcode::JMP_JGT_X
359 | opcode::JMP_JGE_X
360 | opcode::JMP_JSET_X
361 ) {
362 index
363 } else {
364 instruction.k
365 };
366 let condition = match instruction.code {
367 opcode::JMP_JEQ_K | opcode::JMP_JEQ_X => accumulator == operand,
368 opcode::JMP_JGT_K | opcode::JMP_JGT_X => accumulator > operand,
369 opcode::JMP_JGE_K | opcode::JMP_JGE_X => accumulator >= operand,
370 opcode::JMP_JSET_K | opcode::JMP_JSET_X => accumulator & operand != 0,
371 _ => unreachable!(),
372 };
373 pc += 1 + usize::from(if condition {
374 instruction.jt
375 } else {
376 instruction.jf
377 });
378 continue;
379 }
380 opcode::RET_K => return (instruction.k, steps),
381 opcode::RET_A => return (accumulator, steps),
382 opcode::MISC_TAX => index = accumulator,
383 opcode::MISC_TXA => accumulator = index,
384 _ => unreachable!("verified program contains an unsupported opcode"),
385 }
386
387 pc += 1;
388 }
389
390 unreachable!("verified program exhausted its step bound without returning")
391 }
392}
393
394fn verify_program(instructions: &[Instruction]) -> Result<(), VerifyError> {
395 verify_structure(instructions)?;
396 verify_scratch_initialization(instructions)
397}
398
399fn verify_structure(instructions: &[Instruction]) -> Result<(), VerifyError> {
400 if instructions.is_empty() {
401 return Err(VerifyError::Empty);
402 }
403 if instructions.len() > MAX_INSTRUCTIONS {
404 return Err(VerifyError::TooLong {
405 length: instructions.len(),
406 });
407 }
408
409 for (pc, instruction) in instructions.iter().copied().enumerate() {
410 if !is_supported(instruction.code) {
411 return Err(VerifyError::UnsupportedOpcode {
412 pc,
413 code: instruction.code,
414 });
415 }
416
417 match instruction.code {
418 opcode::ALU_DIV_K | opcode::ALU_MOD_K if instruction.k == 0 => {
419 return Err(VerifyError::ImmediateDivisionByZero { pc });
420 }
421 opcode::ALU_LSH_K | opcode::ALU_RSH_K if instruction.k >= 32 => {
422 return Err(VerifyError::ImmediateShiftOutOfRange {
423 pc,
424 shift: instruction.k,
425 });
426 }
427 opcode::LD_MEM | opcode::LDX_MEM | opcode::ST | opcode::STX
428 if instruction.k >= SCRATCH_WORDS as u32 =>
429 {
430 return Err(VerifyError::ScratchOutOfRange {
431 pc,
432 index: instruction.k,
433 });
434 }
435 opcode::JMP_JA => {
436 let Some(target) = pc
437 .checked_add(1)
438 .and_then(|next| next.checked_add(instruction.k as usize))
439 else {
440 return Err(VerifyError::JumpOutOfRange { pc });
441 };
442 if target >= instructions.len() {
443 return Err(VerifyError::JumpOutOfRange { pc });
444 }
445 }
446 opcode::JMP_JEQ_K
447 | opcode::JMP_JEQ_X
448 | opcode::JMP_JGT_K
449 | opcode::JMP_JGT_X
450 | opcode::JMP_JGE_K
451 | opcode::JMP_JGE_X
452 | opcode::JMP_JSET_K
453 | opcode::JMP_JSET_X => {
454 let true_target = pc + 1 + usize::from(instruction.jt);
455 let false_target = pc + 1 + usize::from(instruction.jf);
456 if true_target >= instructions.len() || false_target >= instructions.len() {
457 return Err(VerifyError::JumpOutOfRange { pc });
458 }
459 }
460 _ => {}
461 }
462 }
463
464 if !matches!(
465 instructions.last().map(|instruction| instruction.code),
466 Some(opcode::RET_K | opcode::RET_A)
467 ) {
468 return Err(VerifyError::MissingFinalReturn);
469 }
470
471 Ok(())
472}
473
474fn verify_scratch_initialization(instructions: &[Instruction]) -> Result<(), VerifyError> {
475 let mut incoming = Vec::new();
476 incoming
477 .try_reserve_exact(instructions.len())
478 .map_err(|_| VerifyError::NoMemory)?;
479 incoming.resize(instructions.len(), None);
480 incoming[0] = Some(0_u16);
481
482 for (pc, instruction) in instructions.iter().copied().enumerate() {
483 let Some(mut initialized) = incoming[pc] else {
484 continue;
485 };
486
487 match instruction.code {
488 opcode::LD_MEM | opcode::LDX_MEM => {
489 let bit = 1_u16 << instruction.k;
490 if initialized & bit == 0 {
491 return Err(VerifyError::ScratchUninitialized {
492 pc,
493 index: instruction.k,
494 });
495 }
496 }
497 opcode::ST | opcode::STX => initialized |= 1_u16 << instruction.k,
498 _ => {}
499 }
500
501 match instruction.code {
502 opcode::RET_K | opcode::RET_A => {}
503 opcode::JMP_JA => {
504 let target = pc + 1 + instruction.k as usize;
505 merge_initialized(&mut incoming[target], initialized);
506 }
507 opcode::JMP_JEQ_K
508 | opcode::JMP_JEQ_X
509 | opcode::JMP_JGT_K
510 | opcode::JMP_JGT_X
511 | opcode::JMP_JGE_K
512 | opcode::JMP_JGE_X
513 | opcode::JMP_JSET_K
514 | opcode::JMP_JSET_X => {
515 let true_target = pc + 1 + usize::from(instruction.jt);
516 let false_target = pc + 1 + usize::from(instruction.jf);
517 merge_initialized(&mut incoming[true_target], initialized);
518 merge_initialized(&mut incoming[false_target], initialized);
519 }
520 _ => merge_initialized(&mut incoming[pc + 1], initialized),
521 }
522 }
523
524 Ok(())
525}
526
527fn merge_initialized(slot: &mut Option<u16>, incoming: u16) {
528 *slot = Some(match *slot {
529 Some(existing) => existing & incoming,
530 None => incoming,
531 });
532}
533
534const fn is_supported(code: u16) -> bool {
535 matches!(
536 code,
537 opcode::LD_IMM
538 | opcode::LD_W_ABS
539 | opcode::LD_H_ABS
540 | opcode::LD_B_ABS
541 | opcode::LD_W_IND
542 | opcode::LD_H_IND
543 | opcode::LD_B_IND
544 | opcode::LD_MEM
545 | opcode::LD_LEN
546 | opcode::LDX_IMM
547 | opcode::LDX_MEM
548 | opcode::LDX_LEN
549 | opcode::LDX_B_MSH
550 | opcode::ST
551 | opcode::STX
552 | opcode::ALU_ADD_K
553 | opcode::ALU_ADD_X
554 | opcode::ALU_SUB_K
555 | opcode::ALU_SUB_X
556 | opcode::ALU_MUL_K
557 | opcode::ALU_MUL_X
558 | opcode::ALU_DIV_K
559 | opcode::ALU_DIV_X
560 | opcode::ALU_OR_K
561 | opcode::ALU_OR_X
562 | opcode::ALU_AND_K
563 | opcode::ALU_AND_X
564 | opcode::ALU_LSH_K
565 | opcode::ALU_LSH_X
566 | opcode::ALU_RSH_K
567 | opcode::ALU_RSH_X
568 | opcode::ALU_NEG
569 | opcode::ALU_MOD_K
570 | opcode::ALU_MOD_X
571 | opcode::ALU_XOR_K
572 | opcode::ALU_XOR_X
573 | opcode::JMP_JA
574 | opcode::JMP_JEQ_K
575 | opcode::JMP_JEQ_X
576 | opcode::JMP_JGT_K
577 | opcode::JMP_JGT_X
578 | opcode::JMP_JGE_K
579 | opcode::JMP_JGE_X
580 | opcode::JMP_JSET_K
581 | opcode::JMP_JSET_X
582 | opcode::RET_K
583 | opcode::RET_A
584 | opcode::MISC_TAX
585 | opcode::MISC_TXA
586 )
587}
588
589#[cfg(test)]
590mod tests {
591 use super::*;
592
593 #[test]
594 fn slice_load_ranges_never_exceed_the_advertised_u32_length() {
595 let limit = u32::MAX as usize;
596 for length in [limit, usize::MAX] {
597 assert_eq!(
598 input_range(length, u32::MAX - 1, LoadWidth::Byte),
599 Some(limit - 1..limit)
600 );
601 assert_eq!(
602 input_range(length, u32::MAX - 4, LoadWidth::Word),
603 Some(limit - 4..limit)
604 );
605 assert_eq!(input_range(length, u32::MAX, LoadWidth::Byte), None);
606 assert_eq!(input_range(length, u32::MAX - 1, LoadWidth::Half), None);
607 assert_eq!(input_range(length, u32::MAX - 3, LoadWidth::Word), None);
608 }
609 assert_eq!(input_range(3, 0, LoadWidth::Word), None);
610 assert_eq!(input_range(4, 0, LoadWidth::Word), Some(0..4));
611 }
612
613 #[test]
614 fn verified_execution_never_exceeds_program_length() {
615 let program = Program::verify(&[
616 Instruction::statement(opcode::LD_IMM, 1),
617 Instruction::jump(opcode::JMP_JEQ_K, 1, 1, 0),
618 Instruction::statement(opcode::RET_K, 0),
619 Instruction::statement(opcode::RET_K, 1),
620 ])
621 .unwrap();
622 let (_, steps) = program.evaluate_counted(&[][..]);
623 assert!(steps <= program.len());
624 assert_eq!(steps, 3);
625 }
626}