Skip to main content

sbpf_assembler/
ast.rs

1use {
2    crate::{
3        CompileError, SbpfArch,
4        astnode::{ASTNode, ROData},
5        dynsym::{DynamicSymbolMap, RelDynMap, RelocationType},
6        header::ProgramHeader,
7        optimizer,
8        parser::{ProgramLayout, Token},
9        section::{CodeSection, DataSection},
10    },
11    either::Either,
12    sbpf_common::{
13        OpcodeGroup, OpcodeTable,
14        errors::SBPFError,
15        inst_param::{Number, Register},
16        instruction::Instruction,
17        opcode::Opcode,
18    },
19    std::{
20        collections::{HashMap, HashSet},
21        path::PathBuf,
22    },
23    syscall_map::murmur3_32,
24};
25
26type LabelOffsetMap = HashMap<String, u64>;
27type NumericLabel = (String, u64, usize);
28
29#[derive(Debug, Clone, PartialEq, Eq)]
30pub struct RodataRelocation {
31    // Offset of the relocation in rodata
32    pub offset: u64,
33    // Target label whose address should be written at the relocation offset
34    pub target: String,
35}
36
37#[derive(Debug, Clone, PartialEq, Eq)]
38pub enum OptimizationConfig {
39    Disabled,
40    /// Runs all optimizations: dead-function elimination, then the ALU32
41    /// extension fix-up. The fix-up assumes the input follows eBPF semantics
42    /// (LLVM / sbpf-linker output), where every ALU32 op zero-extends, and
43    /// rewrites `add32`/`sub32`/`mul32` to keep that behaviour under SBPF.
44    Enabled {
45        cfg_dump_dir: Option<PathBuf>,
46    },
47}
48
49impl Default for OptimizationConfig {
50    fn default() -> Self {
51        Self::disabled()
52    }
53}
54
55impl OptimizationConfig {
56    pub fn disabled() -> Self {
57        Self::Disabled
58    }
59
60    pub fn enabled() -> Self {
61        Self::Enabled { cfg_dump_dir: None }
62    }
63
64    pub fn with_cfg_dump_dir(self, path: impl Into<PathBuf>) -> Self {
65        match self {
66            Self::Enabled { .. } => Self::Enabled {
67                cfg_dump_dir: Some(path.into()),
68            },
69            Self::Disabled => Self::Disabled,
70        }
71    }
72}
73
74#[derive(Default, Debug)]
75pub struct AST {
76    pub nodes: Vec<ASTNode>,
77    pub rodata_nodes: Vec<ASTNode>,
78
79    function_entries: HashSet<String>,
80    text_size: u64,
81    rodata_size: u64,
82    rodata_relocations: Vec<RodataRelocation>,
83}
84
85impl AST {
86    pub fn new() -> Self {
87        Self::default()
88    }
89
90    pub fn add_function_entry(&mut self, name: String) {
91        self.function_entries.insert(name);
92    }
93
94    pub fn add_rodata_relocation(&mut self, offset: u64, target: String) {
95        self.rodata_relocations
96            .push(RodataRelocation { offset, target });
97    }
98
99    pub(crate) fn function_entries(&self) -> &HashSet<String> {
100        &self.function_entries
101    }
102
103    pub(crate) fn rodata_relocations(&self) -> &[RodataRelocation] {
104        &self.rodata_relocations
105    }
106
107    //
108    pub fn set_text_size(&mut self, text_size: u64) {
109        self.text_size = text_size;
110    }
111
112    //
113    pub fn set_rodata_size(&mut self, rodata_size: u64) {
114        self.rodata_size = rodata_size;
115    }
116
117    //
118    pub fn get_instruction_at_offset(&mut self, offset: u64) -> Option<&mut Instruction> {
119        self.nodes
120            .iter_mut()
121            .find(|node| match node {
122                ASTNode::Instruction {
123                    instruction: _,
124                    offset: inst_offset,
125                    ..
126                } => offset == *inst_offset,
127                _ => false,
128            })
129            .map(|node| match node {
130                ASTNode::Instruction { instruction, .. } => instruction,
131                _ => panic!("Expected Instruction node"),
132            })
133    }
134
135    //
136    pub fn get_rodata_at_offset(&self, offset: u64) -> Option<&ROData> {
137        self.rodata_nodes
138            .iter()
139            .find(|node| match node {
140                ASTNode::ROData {
141                    rodata: _,
142                    offset: rodata_offset,
143                    ..
144                } => offset == *rodata_offset,
145                _ => false,
146            })
147            .map(|node| match node {
148                ASTNode::ROData { rodata, .. } => rodata,
149                _ => panic!("Expected ROData node"),
150            })
151    }
152
153    /// Resolve numeric label references (like "2f" or "1b")
154    pub(crate) fn resolve_numeric_label(
155        label_ref: &str,
156        current_idx: usize,
157        numeric_labels: &[NumericLabel],
158    ) -> Option<u64> {
159        if let Some(direction) = label_ref.chars().last()
160            && (direction == 'f' || direction == 'b')
161        {
162            let label_num = &label_ref[..label_ref.len() - 1];
163
164            if direction == 'f' {
165                // search forward from current position
166                for (name, offset, node_idx) in numeric_labels {
167                    if name == label_num && *node_idx > current_idx {
168                        return Some(*offset);
169                    }
170                }
171            } else {
172                // search backward from current position
173                for (name, offset, node_idx) in numeric_labels.iter().rev() {
174                    if name == label_num && *node_idx < current_idx {
175                        return Some(*offset);
176                    }
177                }
178            }
179        }
180        None
181    }
182}
183
184pub fn build_program(
185    mut ast: AST,
186    arch: SbpfArch,
187    optimization: OptimizationConfig,
188) -> Result<ProgramLayout, Vec<CompileError>> {
189    let optimization = run_optimizations(&mut ast, &optimization);
190    let mut errors = optimization.errors;
191
192    let (label_offset_map, numeric_labels) = label_offset_map(&ast);
193    let program_is_static = arch.is_v3()
194        || (ast.rodata_relocations.is_empty()
195            && !ast.nodes.iter().any(|node| {
196                matches!(node, ASTNode::Instruction { instruction: inst, .. }
197                    if inst.is_syscall()
198                    || (inst.opcode == Opcode::Lddw && matches!(&inst.imm, Some(Either::Left(_)))))
199            }));
200
201    let label_resolution = resolve_label_references(
202        &mut ast,
203        arch,
204        program_is_static,
205        &label_offset_map,
206        &numeric_labels,
207    );
208    errors.extend(label_resolution.errors);
209    // Only a program that is otherwise ready to encode is validated, so an
210    // unresolved label is not reported a second time as a malformed operand.
211    if errors.is_empty() {
212        errors.extend(validate_instructions(&ast));
213    }
214
215    optimizer::remove_temp_control_flow_target_labels(
216        &mut ast.nodes,
217        &optimization.labels_to_remove,
218    );
219
220    if !errors.is_empty() {
221        Err(errors)
222    } else {
223        Ok(ProgramLayout {
224            code_section: CodeSection::new(std::mem::take(&mut ast.nodes), ast.text_size)
225                .with_arch(arch),
226            data_section: DataSection::new(std::mem::take(&mut ast.rodata_nodes), ast.rodata_size),
227            dynamic_symbols: label_resolution.dynamic_symbols,
228            relocation_data: label_resolution.relocations,
229            prog_is_static: program_is_static,
230            arch,
231            debug_sections: Vec::default(),
232        })
233    }
234}
235
236/// Checks every instruction's operands against its opcode group before
237/// encoding, so an instruction no pass rewrote (e.g. a signed `div` when the
238/// optimizer is disabled) is rejected instead of encoded with wrong semantics.
239fn validate_instructions(ast: &AST) -> Vec<CompileError> {
240    ast.nodes
241        .iter()
242        .filter_map(|node| match node {
243            ASTNode::Instruction { instruction, .. } => {
244                instruction.opcode.group().validate_fn()(instruction).err()
245            }
246            _ => None,
247        })
248        .map(
249            |SBPFError::BytecodeError {
250                 error,
251                 span,
252                 custom_label,
253             }| CompileError::BytecodeError {
254                error,
255                span,
256                custom_label,
257            },
258        )
259        .collect()
260}
261
262#[derive(Default)]
263struct OptimizationOutcome {
264    labels_to_remove: HashSet<String>,
265    errors: Vec<CompileError>,
266}
267
268fn run_optimizations(ast: &mut AST, config: &OptimizationConfig) -> OptimizationOutcome {
269    let OptimizationConfig::Enabled { cfg_dump_dir } = config else {
270        return OptimizationOutcome::default();
271    };
272
273    // Normalize numeric and relative control-flow targets to labels before running
274    // CFG-based optimizations. Synthetic labels are tracked so they can be removed
275    // after optimization, and the pass is skipped if normalization fails.
276    let canonicalized_targets = optimizer::canonicalize_control_flow_targets(&mut ast.nodes);
277    let labels_to_remove = canonicalized_targets.labels_to_remove;
278    let mut errors = Vec::new();
279
280    if canonicalized_targets.errors.is_empty() {
281        if let Some(dump_dir) = cfg_dump_dir.as_deref() {
282            let mut dump_errors = Vec::new();
283            if let Err(error) = std::fs::create_dir_all(dump_dir) {
284                dump_errors.push((dump_dir.to_path_buf(), error));
285                optimizer::optimize(ast);
286            } else {
287                optimizer::optimize_with_observer(ast, |stage, cfg| {
288                    let path = dump_dir.join(stage.file_name());
289                    if let Err(error) = std::fs::write(&path, sbpf_analyze::dump_cfg(cfg)) {
290                        dump_errors.push((path, error));
291                    }
292                });
293            }
294            for (path, error) in dump_errors {
295                errors.push(CompileError::BytecodeError {
296                    error: format!("failed to write CFG dump '{}': {error}", path.display()),
297                    span: 0..0,
298                    custom_label: None,
299                });
300            }
301        } else {
302            optimizer::optimize(ast);
303        }
304    }
305
306    OptimizationOutcome {
307        labels_to_remove,
308        errors,
309    }
310}
311
312#[derive(Default)]
313struct LabelResolution {
314    dynamic_symbols: DynamicSymbolMap,
315    relocations: RelDynMap,
316    errors: Vec<CompileError>,
317}
318
319fn resolve_label_references(
320    ast: &mut AST,
321    arch: SbpfArch,
322    program_is_static: bool,
323    label_offset_map: &LabelOffsetMap,
324    numeric_labels: &[NumericLabel],
325) -> LabelResolution {
326    let mut relocations = RelDynMap::new();
327    let mut dynamic_symbols = DynamicSymbolMap::new();
328    let mut errors = Vec::new();
329
330    // Resolve both static and dynamic syscalls.
331    for node in ast.nodes.iter_mut() {
332        if let ASTNode::Instruction {
333            instruction: inst,
334            offset,
335        } = node
336            && inst.is_syscall()
337            && let Some(Either::Left(syscall_name)) = &inst.imm
338        {
339            let syscall_name = syscall_name.clone();
340            if arch.is_v3() {
341                // Static syscall: src = 0, imm = hash
342                inst.src = Some(Register { n: 0 });
343                inst.imm = Some(Either::Right(Number::Int(murmur3_32(&syscall_name) as i64)));
344            } else {
345                // Dynamic syscall: src = 1, imm = -1
346                inst.src = Some(Register { n: 1 });
347                inst.imm = Some(Either::Right(Number::Int(-1)));
348
349                // Add relocation for dynamic syscall
350                relocations.add_rel_dyn(*offset, RelocationType::RSbfSyscall, syscall_name.clone());
351                dynamic_symbols.add_call_target(syscall_name.clone(), *offset);
352            }
353        }
354    }
355
356    for (idx, node) in ast.nodes.iter_mut().enumerate() {
357        if let ASTNode::Instruction {
358            instruction: inst,
359            offset,
360            ..
361        } = node
362        {
363            // For jump/call instructions, replace label with relative offsets
364            if inst.is_jump()
365                && let Some(Either::Left(label)) = &inst.off
366            {
367                let target_offset = if let Some(offset) = label_offset_map.get(label) {
368                    Some(*offset)
369                } else {
370                    // Handle numeric label references
371                    AST::resolve_numeric_label(label, idx, numeric_labels)
372                };
373
374                if let Some(target_offset) = target_offset {
375                    let rel_offset = (target_offset as i64 - *offset as i64) / 8 - 1;
376                    inst.off = Some(Either::Right(rel_offset as i16));
377                }
378            } else if inst.opcode == Opcode::Call
379                && let Some(Either::Left(label)) = &inst.imm
380                && let Some(target_offset) = label_offset_map.get(label)
381            {
382                let rel_offset = (*target_offset as i64 - *offset as i64) / 8 - 1;
383                inst.src = Some(Register { n: 1 });
384                inst.imm = Some(Either::Right(Number::Int(rel_offset)));
385            }
386
387            if inst.opcode == Opcode::Lddw
388                && let Some(Either::Left(name)) = &inst.imm
389            {
390                let label = name.clone();
391                // Add relocation for lddw (only for v0)
392                if !arch.is_v3() {
393                    relocations.add_rel_dyn(*offset, RelocationType::RSbf64Relative, label.clone());
394                }
395
396                if let Some(target_offset) = label_offset_map.get(&label) {
397                    let abs_offset = if arch.is_v3() {
398                        if *target_offset >= ast.text_size {
399                            (ProgramHeader::V3_RODATA_VADDR + *target_offset - ast.text_size) as i64
400                        } else {
401                            (ProgramHeader::V3_BYTECODE_VADDR + *target_offset) as i64
402                        }
403                    } else {
404                        let ph_count = if program_is_static { 1 } else { 3 };
405                        let ph_offset = 64 + (ph_count as u64 * 56) as i64;
406                        *target_offset as i64 + ph_offset
407                    };
408                    // Replace label with immediate value
409                    inst.imm = Some(Either::Right(Number::Addr(abs_offset)));
410                }
411            }
412
413            // Check if any identifier in `inst.off` or `inst.imm` is unresolved.
414            if let Some(Either::Left(label)) = &inst.off {
415                errors.push(CompileError::UndefinedLabel {
416                    label: label.clone(),
417                    span: inst.span.clone(),
418                    custom_label: None,
419                });
420            }
421            if let Some(Either::Left(label)) = &inst.imm {
422                errors.push(CompileError::UndefinedLabel {
423                    label: label.clone(),
424                    span: inst.span.clone(),
425                    custom_label: None,
426                });
427            }
428        }
429    }
430
431    // Set entry point offset if a GlobalDecl was specified
432    let entry_label = ast.nodes.iter().find_map(|node| {
433        if let ASTNode::GlobalDecl { global_decl } = node {
434            Some(global_decl.entry_label.clone())
435        } else {
436            None
437        }
438    });
439    if let Some(entry_label) = entry_label
440        && let Some(offset) = label_offset_map.get(&entry_label)
441    {
442        dynamic_symbols.add_entry_point(entry_label, *offset);
443    }
444
445    // Resolve rodata relocations and write their target addresses.
446    for relocation in &ast.rodata_relocations {
447        let Some(&target_offset) = label_offset_map.get(&relocation.target) else {
448            errors.push(CompileError::UndefinedLabel {
449                label: relocation.target.clone(),
450                span: 0..0,
451                custom_label: None,
452            });
453            continue;
454        };
455        let value = if arch.is_v3() {
456            if target_offset >= ast.text_size {
457                ProgramHeader::V3_RODATA_VADDR + target_offset - ast.text_size
458            } else {
459                ProgramHeader::V3_BYTECODE_VADDR + target_offset
460            }
461        } else {
462            let ph_count = if program_is_static { 1 } else { 3 };
463            (64 + ph_count * 56 + target_offset) << 32
464        };
465
466        let mut written = false;
467        for node in &mut ast.rodata_nodes {
468            let ASTNode::ROData { rodata, offset } = node else {
469                continue;
470            };
471            let is_quad = match rodata.args.first() {
472                Some(Token::Directive(directive, _)) => directive == "quad",
473                _ => continue,
474            };
475            let Some(Token::VectorLiteral(bytes, _)) = rodata.args.get_mut(1) else {
476                continue;
477            };
478            let Some(relocation_offset_in_node) = relocation.offset.checked_sub(*offset) else {
479                continue;
480            };
481
482            // Write the target address at the relocation offset.
483            if is_quad {
484                // Replace one 8-byte element
485                if relocation_offset_in_node % 8 == 0
486                    && let Some(relocation_value) =
487                        bytes.get_mut((relocation_offset_in_node / 8) as usize)
488                {
489                    *relocation_value = Number::Int(value as i64);
490                    written = true;
491                    break;
492                }
493            } else {
494                // Replace individual byte elements
495                if let Some(relocation_bytes) = bytes.get_mut(
496                    relocation_offset_in_node as usize..relocation_offset_in_node as usize + 8,
497                ) {
498                    for (byte, value) in relocation_bytes.iter_mut().zip(value.to_le_bytes()) {
499                        *byte = Number::Int(i64::from(value));
500                    }
501                    written = true;
502                    break;
503                }
504            }
505        }
506
507        if !written {
508            errors.push(CompileError::BytecodeError {
509                error: format!(
510                    "could not apply rodata relocation at offset {}",
511                    relocation.offset
512                ),
513                span: 0..0,
514                custom_label: None,
515            });
516            continue;
517        }
518
519        if !arch.is_v3() {
520            relocations.add_rel_dyn(
521                ast.text_size + relocation.offset,
522                RelocationType::RSbf64Relative,
523                String::new(),
524            );
525        }
526    }
527
528    LabelResolution {
529        dynamic_symbols,
530        relocations,
531        errors,
532    }
533}
534
535fn label_offset_map(ast: &AST) -> (LabelOffsetMap, Vec<NumericLabel>) {
536    let mut label_offset_map = HashMap::new();
537    let mut numeric_labels = Vec::new();
538
539    for (idx, node) in ast.nodes.iter().enumerate() {
540        if let ASTNode::Label { label, offset } = node {
541            label_offset_map.insert(label.name.clone(), *offset);
542            numeric_labels.push((label.name.clone(), *offset, idx));
543        }
544    }
545
546    for node in &ast.rodata_nodes {
547        if let ASTNode::ROData { rodata, offset } = node {
548            label_offset_map.insert(rodata.name.clone(), *offset + ast.text_size);
549        }
550    }
551
552    (label_offset_map, numeric_labels)
553}
554
555#[cfg(test)]
556mod tests {
557    use {
558        super::*,
559        crate::{astnode::Label, parser::Token, section::Section},
560    };
561
562    #[test]
563    fn test_ast_new() {
564        let ast = AST::new();
565        assert!(ast.nodes.is_empty());
566        assert!(ast.rodata_nodes.is_empty());
567        assert_eq!(ast.text_size, 0);
568        assert_eq!(ast.rodata_size, 0);
569    }
570
571    #[test]
572    fn test_ast_set_sizes() {
573        let mut ast = AST::new();
574        ast.set_text_size(100);
575        ast.set_rodata_size(50);
576        assert_eq!(ast.text_size, 100);
577        assert_eq!(ast.rodata_size, 50);
578    }
579
580    #[test]
581    fn test_get_instruction_at_offset() {
582        let mut ast = AST::new();
583        ast.nodes
584            .push(instruction_node(Opcode::Exit, 0, None, None));
585
586        let found = ast.get_instruction_at_offset(0);
587        assert!(found.is_some());
588        assert_eq!(found.unwrap().opcode, Opcode::Exit);
589
590        let not_found = ast.get_instruction_at_offset(8);
591        assert!(not_found.is_none());
592    }
593
594    #[test]
595    fn test_get_rodata_at_offset() {
596        let mut ast = AST::new();
597        let rodata = ROData {
598            name: "data".to_string(),
599            args: vec![
600                Token::Directive("ascii".to_string(), 0..5),
601                Token::StringLiteral("test".to_string(), 6..12),
602            ],
603            span: 0..12,
604        };
605        ast.rodata_nodes.push(ASTNode::ROData {
606            rodata: rodata.clone(),
607            offset: 0,
608        });
609
610        let found = ast.get_rodata_at_offset(0);
611        assert!(found.is_some());
612        assert_eq!(found.unwrap().name, "data");
613    }
614
615    #[test]
616    fn test_resolve_numeric_label_forward() {
617        let numeric_labels = vec![("1".to_string(), 16, 2), ("2".to_string(), 32, 4)];
618
619        let result = AST::resolve_numeric_label("1f", 0, &numeric_labels);
620        assert_eq!(result, Some(16));
621
622        let result = AST::resolve_numeric_label("2f", 3, &numeric_labels);
623        assert_eq!(result, Some(32));
624    }
625
626    #[test]
627    fn test_resolve_numeric_label_backward() {
628        let numeric_labels = vec![("1".to_string(), 16, 2), ("2".to_string(), 32, 4)];
629
630        let result = AST::resolve_numeric_label("1b", 3, &numeric_labels);
631        assert_eq!(result, Some(16));
632
633        let result = AST::resolve_numeric_label("2b", 5, &numeric_labels);
634        assert_eq!(result, Some(32));
635    }
636
637    #[test]
638    fn test_canonicalize_numeric_jump_target_to_label() {
639        let mut nodes = vec![
640            instruction_node(Opcode::Ja, 0, Some(Either::Left("1f".to_string())), None),
641            label_node("1", 8),
642            instruction_node(Opcode::Exit, 8, None, None),
643        ];
644
645        let canonicalized = optimizer::canonicalize_control_flow_targets(&mut nodes);
646
647        assert!(canonicalized.errors.is_empty());
648        assert!(canonicalized.labels_to_remove.is_empty());
649        let ASTNode::Instruction { instruction, .. } = &nodes[0] else {
650            panic!("expected instruction");
651        };
652        assert_eq!(instruction.off, Some(Either::Left("1".to_string())));
653    }
654
655    #[test]
656    fn test_canonicalize_relative_jump_target_to_synthetic_label() {
657        let mut nodes = vec![
658            instruction_node(Opcode::Ja, 0, Some(Either::Right(1)), None),
659            instruction_node(Opcode::Exit, 8, None, None),
660            instruction_node(Opcode::Exit, 16, None, None),
661        ];
662
663        let canonicalized = optimizer::canonicalize_control_flow_targets(&mut nodes);
664
665        assert!(canonicalized.errors.is_empty());
666        assert_eq!(canonicalized.labels_to_remove.len(), 1);
667
668        let ASTNode::Instruction { instruction, .. } = &nodes[0] else {
669            panic!("expected instruction");
670        };
671        let Some(Either::Left(label)) = &instruction.off else {
672            panic!("expected canonical label target");
673        };
674        assert!(label.starts_with("temp_"));
675        assert!(canonicalized.labels_to_remove.contains(label));
676        assert!(
677            matches!(&nodes[2], ASTNode::Label { label: target_label, offset }
678                if target_label.name == *label && *offset == 16)
679        );
680    }
681
682    #[test]
683    fn test_canonicalize_rejects_invalid_relative_jump_target() {
684        let mut nodes = vec![
685            instruction_node(Opcode::Ja, 0, Some(Either::Right(1)), None),
686            instruction_node(Opcode::Exit, 8, None, None),
687        ];
688
689        let canonicalized = optimizer::canonicalize_control_flow_targets(&mut nodes);
690
691        assert_eq!(canonicalized.errors.len(), 1);
692        assert!(canonicalized.labels_to_remove.is_empty());
693        assert_eq!(nodes.len(), 2);
694        let ASTNode::Instruction { instruction, .. } = &nodes[0] else {
695            panic!("expected instruction");
696        };
697        assert_eq!(instruction.off, Some(Either::Right(1)));
698    }
699
700    #[test]
701    fn test_dce_recomputes_relative_call_target_after_removing_code() {
702        let mut ast = AST::new();
703        ast.add_function_entry("entrypoint".to_string());
704        ast.add_function_entry("dead".to_string());
705        ast.add_function_entry("target".to_string());
706        ast.nodes = vec![
707            label_node("entrypoint", 0),
708            internal_call_node(0, 2),
709            instruction_node(Opcode::Exit, 8, None, None),
710            label_node("dead", 16),
711            instruction_node(Opcode::Exit, 16, None, None),
712            label_node("target", 24),
713            instruction_node(Opcode::Exit, 24, None, None),
714        ];
715        ast.set_text_size(32);
716
717        let program_layout =
718            build_program(ast, SbpfArch::V0, OptimizationConfig::enabled()).unwrap();
719        let nodes = program_layout.code_section.get_nodes();
720
721        assert_eq!(
722            nodes
723                .iter()
724                .filter(|node| matches!(node, ASTNode::Instruction { .. }))
725                .count(),
726            3
727        );
728        assert!(matches!(
729            &nodes[1],
730            ASTNode::Instruction { instruction, offset }
731                if instruction.opcode == Opcode::Call
732                    && instruction.src == Some(Register { n: 1 })
733                    && instruction.imm == Some(Either::Right(Number::Int(1)))
734                    && *offset == 0
735        ));
736        assert!(matches!(
737            &nodes[3],
738            ASTNode::Label { label, offset } if label.name == "target" && *offset == 16
739        ));
740    }
741
742    #[test]
743    fn test_optimize_ast_removes_temp_jump_target_labels() {
744        let mut ast = AST::new();
745        ast.nodes = vec![
746            instruction_node(Opcode::Ja, 0, Some(Either::Right(1)), None),
747            instruction_node(Opcode::Exit, 8, None, None),
748            instruction_node(Opcode::Exit, 16, None, None),
749        ];
750        ast.set_text_size(24);
751        ast.set_rodata_size(0);
752
753        let result = build_program(ast, SbpfArch::V0, OptimizationConfig::enabled());
754
755        assert!(result.is_ok());
756        let program_layout = result.unwrap();
757        assert!(!program_layout.code_section.get_nodes().iter().any(|node| {
758            matches!(node, ASTNode::Label { label, .. }
759                if label
760                    .name
761                    .starts_with("temp_"))
762        }));
763        let ASTNode::Instruction { instruction, .. } = &program_layout.code_section.get_nodes()[0]
764        else {
765            panic!("expected instruction");
766        };
767        assert_eq!(instruction.off, Some(Either::Right(1)));
768    }
769
770    #[test]
771    fn test_build_program_simple() {
772        for arch in [SbpfArch::V0, SbpfArch::V3] {
773            let mut ast = AST::new();
774            ast.nodes
775                .push(instruction_node(Opcode::Exit, 0, None, None));
776            ast.set_text_size(8);
777            ast.set_rodata_size(0);
778
779            let result = build_program(ast, arch, OptimizationConfig::default());
780            assert!(result.is_ok());
781            let parse_result = result.unwrap();
782            assert!(parse_result.prog_is_static);
783        }
784    }
785
786    #[test]
787    fn test_build_program_undefined_label_error() {
788        for arch in [SbpfArch::V0, SbpfArch::V3] {
789            let mut ast = AST::new();
790            ast.nodes.push(instruction_node(
791                Opcode::Ja,
792                0,
793                Some(Either::Left("undefined_label".to_string())),
794                None,
795            ));
796            ast.set_text_size(8);
797
798            let result = build_program(ast, arch, OptimizationConfig::default());
799            assert!(result.is_err());
800        }
801    }
802
803    #[test]
804    fn test_build_program_static_syscalls_no_relocation() {
805        let mut ast = AST::new();
806
807        ast.nodes.push(instruction_node(
808            Opcode::Call,
809            0,
810            None,
811            Some(Either::Left("sol_log_".to_string())),
812        ));
813        ast.nodes
814            .push(instruction_node(Opcode::Exit, 8, None, None));
815
816        ast.set_text_size(16);
817        ast.set_rodata_size(0);
818
819        let result = build_program(ast, SbpfArch::V3, OptimizationConfig::default());
820        assert!(result.is_ok());
821        let parse_result = result.unwrap();
822
823        assert!(parse_result.prog_is_static);
824        assert!(parse_result.relocation_data.get_rel_dyns().is_empty());
825    }
826
827    #[test]
828    fn test_build_program_dynamic_syscalls_with_relocation() {
829        let mut ast = AST::new();
830
831        ast.nodes.push(instruction_node(
832            Opcode::Call,
833            0,
834            None,
835            Some(Either::Left("sol_log_".to_string())),
836        ));
837        ast.nodes
838            .push(instruction_node(Opcode::Exit, 8, None, None));
839
840        ast.set_text_size(16);
841        ast.set_rodata_size(0);
842
843        let result = build_program(ast, SbpfArch::V0, OptimizationConfig::default());
844        assert!(result.is_ok());
845        let parse_result = result.unwrap();
846
847        assert!(!parse_result.prog_is_static);
848        assert!(!parse_result.relocation_data.get_rel_dyns().is_empty());
849    }
850
851    #[test]
852    fn test_build_program_rodata_data_relocation_v0() {
853        let result = build_program(
854            rodata_data_relocation_ast(),
855            SbpfArch::V0,
856            OptimizationConfig::default(),
857        );
858        assert!(result.is_ok());
859        let layout = result.unwrap();
860        assert!(!layout.prog_is_static);
861        let target_address: u64 = 64 + 3 * 56 + 8 + 8;
862        assert_eq!(
863            &layout.data_section.bytecode()[..8],
864            &(target_address << 32).to_le_bytes()
865        );
866    }
867
868    #[test]
869    fn test_build_program_rodata_data_relocation_v3() {
870        let result = build_program(
871            rodata_data_relocation_ast(),
872            SbpfArch::V3,
873            OptimizationConfig::default(),
874        );
875        assert!(result.is_ok());
876        let layout = result.unwrap();
877        assert!(layout.prog_is_static);
878        assert_eq!(
879            &layout.data_section.bytecode()[..8],
880            &(ProgramHeader::V3_RODATA_VADDR + 8).to_le_bytes()
881        );
882    }
883
884    #[test]
885    fn test_build_program_rodata_fn_relocation_v0() {
886        let result = build_program(
887            rodata_fn_relocation_ast(),
888            SbpfArch::V0,
889            OptimizationConfig::default(),
890        );
891        assert!(result.is_ok());
892        let layout = result.unwrap();
893        assert!(!layout.prog_is_static);
894        let target_address: u64 = 64 + 3 * 56;
895        assert_eq!(
896            &layout.data_section.bytecode()[..8],
897            &(target_address << 32).to_le_bytes()
898        );
899    }
900
901    #[test]
902    fn test_build_program_rodata_fn_relocation_v3() {
903        let result = build_program(
904            rodata_fn_relocation_ast(),
905            SbpfArch::V3,
906            OptimizationConfig::default(),
907        );
908        assert!(result.is_ok());
909        let layout = result.unwrap();
910        assert!(layout.prog_is_static);
911        assert_eq!(
912            &layout.data_section.bytecode()[..8],
913            &ProgramHeader::V3_BYTECODE_VADDR.to_le_bytes()
914        );
915    }
916
917    #[test]
918    fn test_build_program_rodata_relocation_undefined_label() {
919        let mut ast = AST::new();
920        ast.nodes
921            .push(instruction_node(Opcode::Exit, 0, None, None));
922        ast.add_rodata_relocation(8, "invalid".to_string());
923        ast.set_text_size(8);
924        let result = build_program(ast, SbpfArch::V0, OptimizationConfig::default());
925        let Err(errors) = result else {
926            panic!("expected undefined label");
927        };
928        assert!(matches!(
929            &errors[..],
930            [CompileError::UndefinedLabel { label, .. }] if label == "invalid"
931        ));
932    }
933
934    /// `entrypoint: <signed opcode> r0, <src register or imm>; exit`
935    fn signed_div_program(opcode: Opcode, src_or_imm: Either<u8, i64>) -> AST {
936        let mut ast = AST::new();
937        ast.add_function_entry("entrypoint".to_string());
938        ast.nodes = vec![
939            label_node("entrypoint", 0),
940            ASTNode::Instruction {
941                instruction: Instruction {
942                    opcode,
943                    dst: Some(Register { n: 0 }),
944                    src: src_or_imm.left().map(|n| Register { n }),
945                    off: Some(Either::Right(sbpf_common::opcode::SIGNED_DIV_OFF)),
946                    imm: src_or_imm.right().map(|v| Either::Right(Number::Int(v))),
947                    span: 0..8,
948                },
949                offset: 0,
950            },
951            instruction_node(Opcode::Exit, 8, None, None),
952        ];
953        ast.set_text_size(16);
954        ast
955    }
956
957    fn assert_rejected_as_unexpanded(result: Result<ProgramLayout, Vec<CompileError>>) {
958        let Err(errors) = result else {
959            panic!("an unexpanded signed div must not build");
960        };
961        assert!(matches!(
962            &errors[..],
963            [CompileError::BytecodeError { custom_label: Some(label), .. }]
964                if label == "Unexpanded signed division"
965        ));
966    }
967
968    #[test]
969    fn test_build_program_expands_signed_div() {
970        let layout = build_program(
971            signed_div_program(Opcode::Div64Reg, Either::Left(1)),
972            SbpfArch::V3,
973            OptimizationConfig::enabled(),
974        )
975        .unwrap();
976        assert!(!layout.code_section.get_nodes().iter().any(|node| matches!(
977            node,
978            ASTNode::Instruction { instruction, .. } if instruction.is_signed_div_or_mod()
979        )));
980    }
981
982    #[test]
983    fn test_build_program_rejects_unexpanded_signed_div() {
984        assert_rejected_as_unexpanded(build_program(
985            signed_div_program(Opcode::Div64Reg, Either::Left(1)),
986            SbpfArch::V3,
987            OptimizationConfig::disabled(),
988        ));
989    }
990
991    #[test]
992    fn test_build_program_rejects_signed_div_without_expansion() {
993        // The fixup has no expansion for 32-bit immediates, which LLVM never emits.
994        assert_rejected_as_unexpanded(build_program(
995            signed_div_program(Opcode::Div32Imm, Either::Right(-3)),
996            SbpfArch::V3,
997            OptimizationConfig::enabled(),
998        ));
999    }
1000
1001    fn label_node(name: &str, offset: u64) -> ASTNode {
1002        ASTNode::Label {
1003            label: Label {
1004                name: name.to_string(),
1005                span: 0..0,
1006            },
1007            offset,
1008        }
1009    }
1010
1011    fn instruction_node(
1012        opcode: Opcode,
1013        offset: u64,
1014        off: Option<Either<String, i16>>,
1015        imm: Option<Either<String, Number>>,
1016    ) -> ASTNode {
1017        ASTNode::Instruction {
1018            instruction: Instruction {
1019                opcode,
1020                dst: None,
1021                src: None,
1022                off,
1023                imm,
1024                span: 0..0,
1025            },
1026            offset,
1027        }
1028    }
1029
1030    fn internal_call_node(offset: u64, relative_offset: i64) -> ASTNode {
1031        ASTNode::Instruction {
1032            instruction: Instruction {
1033                opcode: Opcode::Call,
1034                dst: None,
1035                src: Some(Register { n: 1 }),
1036                off: None,
1037                imm: Some(Either::Right(Number::Int(relative_offset))),
1038                span: 0..0,
1039            },
1040            offset,
1041        }
1042    }
1043
1044    // Test AST with a rodata relocation targeting data in the rodata section.
1045    fn rodata_data_relocation_ast() -> AST {
1046        let mut ast = AST::new();
1047        ast.nodes
1048            .push(instruction_node(Opcode::Exit, 0, None, None));
1049        ast.rodata_nodes.push(ASTNode::ROData {
1050            rodata: ROData {
1051                name: "ptr".to_string(),
1052                args: vec![
1053                    Token::Directive("byte".to_string(), 0..1),
1054                    Token::VectorLiteral(vec![Number::Int(0); 8], 0..1),
1055                ],
1056                span: 0..1,
1057            },
1058            offset: 0,
1059        });
1060        ast.rodata_nodes.push(ASTNode::ROData {
1061            rodata: ROData {
1062                name: "data".to_string(),
1063                args: vec![
1064                    Token::Directive("byte".to_string(), 0..1),
1065                    Token::VectorLiteral(vec![Number::Int(0); 8], 0..1),
1066                ],
1067                span: 0..1,
1068            },
1069            offset: 8,
1070        });
1071        ast.add_rodata_relocation(0, "data".to_string());
1072        ast.set_text_size(8);
1073        ast.set_rodata_size(16);
1074        ast
1075    }
1076
1077    // Test AST with a rodata relocation targeting a function in the text section.
1078    fn rodata_fn_relocation_ast() -> AST {
1079        let mut ast = AST::new();
1080        ast.nodes.push(label_node("fn", 0));
1081        ast.nodes
1082            .push(instruction_node(Opcode::Exit, 0, None, None));
1083        ast.rodata_nodes.push(ASTNode::ROData {
1084            rodata: ROData {
1085                name: "ptr".to_string(),
1086                args: vec![
1087                    Token::Directive("byte".to_string(), 0..1),
1088                    Token::VectorLiteral(vec![Number::Int(0); 8], 0..1),
1089                ],
1090                span: 0..1,
1091            },
1092            offset: 0,
1093        });
1094        ast.add_rodata_relocation(0, "fn".to_string());
1095        ast.set_text_size(8);
1096        ast.set_rodata_size(8);
1097        ast
1098    }
1099}