Skip to main content

axcbpf/
program.rs

1use alloc::vec::Vec;
2use core::{fmt, ops::Range};
3
4use crate::{Instruction, opcode};
5
6/// Maximum number of instructions in one verified classic-BPF program.
7pub const MAX_INSTRUCTIONS: usize = 4096;
8
9/// Number of 32-bit scratch words exposed by classic BPF.
10pub const SCRATCH_WORDS: usize = 16;
11
12/// Width requested from a classic-BPF input.
13#[derive(Clone, Copy, Debug, Eq, PartialEq)]
14pub enum LoadWidth {
15    /// One byte.
16    Byte,
17    /// Two bytes.
18    Half,
19    /// Four bytes.
20    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
33/// Read-only data source evaluated by a classic-BPF program.
34///
35/// The input owns load endianness and any domain-specific offset validation.
36/// Returning `None` terminates evaluation with the classic-BPF failure value
37/// zero. The interpreter never exposes A, X, scratch memory, or mutable state
38/// to the input implementation.
39pub trait Input {
40    /// Returns the length value observed by `LD_LEN` and `LDX_LEN`.
41    fn len(&self) -> u32;
42
43    /// Returns whether the input length is zero.
44    fn is_empty(&self) -> bool {
45        self.len() == 0
46    }
47
48    /// Loads one value at an already resolved absolute offset.
49    fn load(&self, offset: u32, width: LoadWidth) -> Option<u32>;
50}
51
52/// Slice adapters and native images share a u32 input-length ABI. A larger
53/// backing slice must not expose bytes beyond its advertised saturated length.
54pub(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/// Failure while validating and owning one classic-BPF program.
78#[derive(Clone, Copy, Debug, Eq, PartialEq)]
79#[non_exhaustive]
80pub enum VerifyError {
81    /// A program must contain at least one instruction.
82    Empty,
83    /// The program exceeds [`MAX_INSTRUCTIONS`].
84    TooLong {
85        /// Supplied instruction count.
86        length: usize,
87    },
88    /// Storage needed for validation or the owned program could not be reserved.
89    NoMemory,
90    /// The opcode is not part of the supported ordinary classic-BPF set.
91    UnsupportedOpcode {
92        /// Instruction index.
93        pc: usize,
94        /// Rejected raw opcode.
95        code: u16,
96    },
97    /// An immediate divisor or modulus was zero.
98    ImmediateDivisionByZero {
99        /// Instruction index.
100        pc: usize,
101    },
102    /// An immediate shift count was outside `0..32`.
103    ImmediateShiftOutOfRange {
104        /// Instruction index.
105        pc: usize,
106        /// Rejected shift count.
107        shift: u32,
108    },
109    /// A scratch-memory index was outside the sixteen-word store.
110    ScratchOutOfRange {
111        /// Instruction index.
112        pc: usize,
113        /// Rejected scratch index.
114        index: u32,
115    },
116    /// A reachable path loads a scratch word not initialized on every path.
117    ScratchUninitialized {
118        /// Instruction index.
119        pc: usize,
120        /// Uninitialized scratch index.
121        index: u32,
122    },
123    /// A jump target was outside the program.
124    JumpOutOfRange {
125        /// Instruction index.
126        pc: usize,
127    },
128    /// The final instruction was not a return.
129    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/// Immutable verified classic-BPF program.
173///
174/// Construction performs all structural checks and fallibly copies the raw
175/// instructions. Evaluation allocates nothing, initializes A and X to zero,
176/// and executes at most `len()` instructions because every accepted jump is
177/// forward-only.
178#[derive(Debug)]
179pub struct Program {
180    instructions: Vec<Instruction>,
181}
182
183impl Program {
184    /// Verifies and fallibly takes an immutable copy of raw instructions.
185    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    /// Verifies and takes ownership of an existing instruction vector.
199    ///
200    /// This path performs no second instruction-buffer allocation or copy. It
201    /// is intended for adapters that already copied an untrusted wire program
202    /// into a fallibly allocated kernel vector. Validation still uses bounded,
203    /// fallible temporary storage for all-path scratch analysis.
204    pub fn try_from_vec(instructions: Vec<Instruction>) -> Result<Self, VerifyError> {
205        verify_program(&instructions)?;
206        Ok(Self { instructions })
207    }
208
209    /// Returns the verified raw instructions.
210    pub fn instructions(&self) -> &[Instruction] {
211        &self.instructions
212    }
213
214    /// Returns the instruction count and maximum evaluation step count.
215    pub fn len(&self) -> usize {
216        self.instructions.len()
217    }
218
219    /// Returns whether the program contains no instructions.
220    ///
221    /// Verified programs are never empty, so this always returns `false`.
222    pub fn is_empty(&self) -> bool {
223        self.instructions.is_empty()
224    }
225
226    /// Translates this verified program into an immutable x86_64 code image.
227    ///
228    /// Translation only produces bytes and metadata. It does not make pages
229    /// executable, patch relocations, or invoke an external function. A
230    /// publisher is responsible for resolving the returned relocations under
231    /// its own W^X and lifetime policy.
232    pub fn translate(&self) -> Result<crate::CodeImage, crate::TranslationError> {
233        self.translate_with_profile(crate::InputProfile::BigEndianBytes)
234    }
235
236    /// Translates using an explicit input ABI profile.
237    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    /// Evaluates the program without allocation.
245    ///
246    /// A failed input load, an indirect-offset overflow, or a run-time X
247    /// divisor of zero terminates evaluation with zero, matching classic-BPF
248    /// failure behavior. A and X start at zero for every call.
249    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}