solana-labs / rbpf Goto Github PK

This is ret2HAPPY from BlockSec.

One deadloop problem is found in function control_flow_graph_dominance_hierarchy of solana_rbpf::static_analysis::Analysis.

To reproduce the deadloop, please use the following code snippet:

// path : path_to_test.o
let program = fs::read(&path).unwrap();
let mut functions = std::collections::BTreeMap::new();
register_bpf_function(&mut functions, 0, "entrypoint", false).unwrap();
let mut executable = Executable::<UserError, TestInstructionMeter>::from_text_bytes(program, None, Config::default(), SyscallRegistry::default(), functions).unwrap();
let _ = solana_rbpf::static_analysis::Analysis::from_executable(&executable);

test.o.zip

Since the static analyzer is used for debugging purposes, this issue will not trigger serious security risks.

The winapi dependency is only used when the code is compiled on Windows (#[cfg(target_os = "windows")]), but the Cargo.toml file currently requires it for all platforms.

Feel free to edit.

1. JIT time for Serum, Mango Markets etc.
2. x86 binary size for the same (also table out the bytecode size, I believe for Serum it was 400+KiB

At commit 2e6d571, the disassemble example is broken.

% cargo run --example disassemble
    Finished dev [unoptimized + debuginfo] target(s) in 0.04s
     Running `target/debug/examples/disassemble`
thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: ElfError(InvalidEntrypoint)', examples/disassemble.rs:41:59
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

The error string for this guy is "exceeded maximum number of instructions allowed ({1}) at instruction #{0}"). When you're executing a Solana transaction, it's confusing to encounter this error because you're typically thinking of Solana transaction instructions, not BPF instructions, and it looks like you tried to submit a transaction with 200_000 instructions

Description

Intel CET ("Control-flow Enforcement Technology") is a technology that aims to defend against exploitation techniques that rely on taking over control-flow like ROP.

It is a relatively recent extension that's only supported on recent Intel and AMD CPUs. Certain CET instructions map to the NOP opcode space to allow for backwards compatibility with older CPUs.

Since we are generating code at runtime, we can always conditionally enable new features based on CPUID. This would come at the expense of added complexity (=attack surface) however.

Introducing CET support to the SBF JIT compiler could improve the security of the Solana program sandbox.

Concepts

IBT (Indirect Branch Tracking)

endbr64 is a new instruction that encodes to f3 0f 1e fa, which is a NOP on older machines.
It marks valid indirect branch targets and return sites.

When enabled, the CPU will refuse to follow indirect branches or return addresses that do not have endbr64 as the next instruction.

Shadow Stack

Special stack that only stores return addresses to defend against stack smashing.

Attached is a rust-1.68 core tests loadable EFL file that used to run correctly on RBPF. Now RBPF running this file is killed by the OS.
sample.zip

Program log: test num::int_log::checked_ilog2 ... 
Killed

Instead of using saturating ops, the parser should use checked ops and error out early.

OS-ELF-SUG-00

Fixed in f6c483d

$ rustc --version
rustc 1.64.0 (a55dd71d5 2022-09-19)

$ git clone https://github.com/solana-labs/rbpf
$ cd rbpf
$ cargo build

error[E0658]: use of unstable library feature 'once_cell'
  --> src/jit.rs:36:33
   |
36 | static RUNTIME_ENVIRONMENT_KEY: std::sync::OnceLock<i32> = std::sync::OnceLock::<i32>::new();
   |                                 ^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: see issue #74465 <https://github.com/rust-lang/rust/issues/74465> for more information

error[E0658]: use of unstable library feature 'once_cell'
  --> src/jit.rs:36:60
   |
36 | static RUNTIME_ENVIRONMENT_KEY: std::sync::OnceLock<i32> = std::sync::OnceLock::<i32>::new();
   |                                                            ^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: see issue #74465 <https://github.com/rust-lang/rust/issues/74465> for more information

error[E0658]: use of unstable library feature 'once_cell'
  --> src/jit.rs:36:60
   |
36 | static RUNTIME_ENVIRONMENT_KEY: std::sync::OnceLock<i32> = std::sync::OnceLock::<i32>::new();
   |                                                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: see issue #74465 <https://github.com/rust-lang/rust/issues/74465> for more information

error[E0599]: the method `lookup_by_key` exists for reference `&FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>`, but its trait bounds were not satisfied
   --> src/disassembler.rs:269:48
    |
269 |                 loader.get_function_registry().lookup_by_key(insn.imm as u32).map(|(function_name, _)| String::from_utf8_lossy(function_n...
    |                                                ^^^^^^^^^^^^^ method cannot be called on `&FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>` due to unsatisfied trait bounds
    |
    = note: the following trait bounds were not satisfied:
            `for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>): PartialEq`

error[E0599]: the method `lookup_by_key` exists for reference `&FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>`, but its trait bounds were not satisfied
   --> src/elf.rs:342:51
    |
342 |                 && loader.get_function_registry().lookup_by_key(hash).is_some()
    |                                                   ^^^^^^^^^^^^^ method cannot be called on `&FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>` due to unsatisfied trait bounds
    |
    = note: the following trait bounds were not satisfied:
            `for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>): PartialEq`

error[E0599]: the method `lookup_by_key` exists for reference `&FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>`, but its trait bounds were not satisfied
    --> src/elf.rs:1305:63
     |
1305 | ...                   && loader.get_function_registry().lookup_by_key(hash).is_none()
     |                                                         ^^^^^^^^^^^^^ method cannot be called on `&FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>` due to unsatisfied trait bounds
     |
     = note: the following trait bounds were not satisfied:
             `for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>): PartialEq`

error[E0599]: the method `lookup_by_key` exists for reference `&FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>`, but its trait bounds were not satisfied
   --> src/interpreter.rs:505:116
    |
505 | ....executable.get_loader().get_function_registry().lookup_by_key(insn.imm as u32) {
    |                                                     ^^^^^^^^^^^^^ method cannot be called on `&FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>` due to unsatisfied trait bounds
    |
    = note: the following trait bounds were not satisfied:
            `for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>): PartialEq`

error[E0658]: use of unstable library feature 'once_cell'
   --> src/jit.rs:130:90
    |
130 |                 rbp = in(reg) (vm as *mut _ as *mut u64).offset(*RUNTIME_ENVIRONMENT_KEY.get().unwrap() as isize),
    |                                                                                          ^^^
    |
    = note: see issue #74465 <https://github.com/rust-lang/rust/issues/74465> for more information

error[E0658]: use of unstable library feature 'once_cell'
   --> src/jit.rs:358:64
    |
358 |         let runtime_environment_key = *RUNTIME_ENVIRONMENT_KEY.get_or_init(|| {
    |                                                                ^^^^^^^^^^^
    |
    = note: see issue #74465 <https://github.com/rust-lang/rust/issues/74465> for more information

error[E0599]: the method `lookup_by_key` exists for reference `&FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>`, but its trait bounds were not satisfied
   --> src/jit.rs:659:120
    |
659 | ....executable.get_loader().get_function_registry().lookup_by_key(insn.imm as u32) {
    |                                                     ^^^^^^^^^^^^^ method cannot be called on `&FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>` due to unsatisfied trait bounds
    |
    = note: the following trait bounds were not satisfied:
            `for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>): PartialEq`

error[E0599]: the method `lookup_by_key` exists for reference `&FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut TestContextObject, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>`, but its trait bounds were not satisfied
   --> src/static_analysis.rs:234:26
    |
234 |                         .lookup_by_key(insn.imm as u32)
    |                          ^^^^^^^^^^^^^ method cannot be called on `&FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut TestContextObject, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>` due to unsatisfied trait bounds
    |
    = note: the following trait bounds were not satisfied:
            `for<'r, 's, 't0, 't1> fn(&'r mut TestContextObject, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>): PartialEq`

error[E0599]: the method `eq` exists for struct `FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>`, but its trait bounds were not satisfied
   --> src/vm.rs:105:57
    |
105 |         self.config.eq(&other.config) && self.functions.eq(&other.functions)
    |                                                         ^^ method cannot be called on `FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>` due to unsatisfied trait bounds
    |
   ::: src/elf.rs:277:1
    |
277 | pub struct FunctionRegistry<T> {
    | ------------------------------
    | |
    | method `eq` not found for this struct
    | doesn't satisfy `_: Iterator`
    | doesn't satisfy `_: PartialEq`
    |
note: trait bound `for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>): PartialEq` was not satisfied
   --> src/elf.rs:276:17
    |
276 | #[derive(Debug, PartialEq, Eq)]
    |                 ^^^^^^^^^ unsatisfied trait bound introduced in this `derive` macro
    = note: the following trait bounds were not satisfied:
            `for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>): PartialEq`
            which is required by `FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>: PartialEq`
            `FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>: Iterator`
            which is required by `&mut FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>: Iterator`
note: the following trait must be implemented
   --> /home/adityak/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/iter/traits/iterator.rs:67:1
    |
67  | pub trait Iterator {
    | ^^^^^^^^^^^^^^^^^^

error[E0599]: the method `mem_size` exists for struct `FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>`, but its trait bounds were not satisfied
   --> src/vm.rs:152:30
    |
152 |             + self.functions.mem_size()
    |                              ^^^^^^^^ method cannot be called on `FunctionRegistry<for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>)>` due to unsatisfied trait bounds
    |
   ::: src/elf.rs:277:1
    |
277 | pub struct FunctionRegistry<T> {
    | ------------------------------ method `mem_size` not found for this struct
    |
    = note: the following trait bounds were not satisfied:
            `for<'r, 's, 't0, 't1> fn(&'r mut C, u64, u64, u64, u64, u64, &'s mut MemoryMapping<'t0>, &'t1 mut StableResult<u64, Box<(dyn std::error::Error + 'static)>>): PartialEq`

Some errors have detailed explanations: E0599, E0658.
For more information about an error, try `rustc --explain E0599`.
error: could not compile `solana_rbpf` due to 13 previous errors

We currently retrieve some tables (eg .dynstr) by name instead of looking up their address in the .dynamic table. This is because some programs have the wrong address encoded in the latter, but otherwise the files as a whole are correct and we're able to load them.

We should review what percentage of programs have this problem and consider rejecting them so we can rely on parsing the .dynamic table only.

OS-ELF-SUG-03

I'd like to know what the worst case compilation+static analysis time for an eBPF program of size up to 10MB, by causing the static analysis to become very slow (for instance, jumping randomly on every instruction).

Still, a BTreeMap with 10M entries with integer keys doesn't seem that daunting... Cfg graph also has branching factor at most 2 - this means at most 20M edges.

During loading we used to check that readonly sections didn't start beyond MM_STACK_START but we didn't check that they didn't extend beyond it (start + size). This was fixed in #371 and is behind the reject_rodata_stack_overlap config key.

The bug wasn't actually triggerable since it'd require enable_elf_vaddr=true to be hit, which we haven't enabled yet (it's meant for sbfv2 files).

OS-ELF-ADV-01

rbpf is not on the latest Rust edition: https://doc.rust-lang.org/edition-guide/rust-2018/index.html

Add
edition = "2018"

to Cargo.toml

And fix all the issues

VM is initialized with an Option<[u64; 256]>, cost array that is passed by the runtime.

If the array is not_none(), the cumulative cost table must first be built on an additional first pass over the bytecode (this is because target_pc can be ahead of the jmp's pc). Subsequently, inline the cumulative table value rather than the pc/target_pc when emitting.

Problems:

1. Need to invalidate Bank's executor cache

Attached a sample program that is executed incorrectly by the VM. The third instruction from the entrypoint is a call which should transfer control to instruction 270817. Instead the VM jumps to instruction 834 according to instruction trace.

sample.zip

The new elf parser breaks on a valid ELF input file. The file is attached in this issue.
sample.ZIP

The jit uses unwrap when creating the rng.

        let mut diversification_rng = SmallRng::from_rng(rand::thread_rng()).unwrap();

The current implementation of SmallRng never fails, but to be extra safe we should remove the unwrap.

HAL-02

Experimenting with rbpf I managed to execute spl_token with random data:

rbpf_cli --elf spl_token.so --use interpreter --input 99999

with output:

    Syscall sol_log_: 0x1000233d4, 0x1a, 0x0, 0x0, 0x200001000
    Result: Ok(12)
    Instruction Count: 380

But what exactly should a user pass as the --input argument to make sense? For example, to simulate spl-token-cli create-token operation.

Problem

The new ELF Parser incorrectly reports sections as OutOfBounds if the section ends at the end of the ELF file.

OS-ELF-ADV-00

Proposed Solution

Addressed in 30e2c96

From @seanyoung

The bpf program gets a pointer to the serialized parameters data here https://github.com/solana-labs/solana/blob/master/programs/bpf_loader/src/lib.rs#L246

The program is can then modify this data (e.g. change lamports of an account).

Then the parameters are deserialized here: https://github.com/solana-labs/solana/blob/master/programs/bpf_loader/src/lib.rs#L316

I am not sure if my understanding is correct, since parameter_bytes is not declared mut.

That slice gets thrown into a list of memory regions the program has access to, when the program attempts to access a virtual address the vm translates it to a physical address and operates on that memory via pointers/unsafe. So there is a disconnect between the slice passed in and they eventual read/write. The slice gets added to the list of regions here:

Proposal:
Change the new function to take mem as a &mut to make it clearer that the memory could be mutated.

This is ret2HAPPY from BlockSec.

When the ExceededMaxInstructions exception is triggered in both JIT and interpretation mode, the PC values are inconsistent:

• In Interpreter mode : ExceededMaxInstructions(31, 2240)

• In JIT mode : ExceededMaxInstructions(32, 2240)

To reproduce the different runtime error from the attached exceeded_instructions.o program, use the following code snippet:

// path : path_to_exceeded_instructions.o
let program = fs::read(&path).unwrap();
let mut functions = std::collections::BTreeMap::new();
register_bpf_function(&mut functions, 0, "entrypoint", false).unwrap();
let mut executable = Executable::<UserError, TestInstructionMeter>::from_text_bytes(program, None, Config::default(), SyscallRegistry::default(), functions).unwrap();


// run in interpreter, raise ExceededMaxInstructions(31, 2240)
let mut vm1 = EbpfVm::new(&executable, &mut [], &mut []).unwrap();
vm1.execute_program_interpreted(&mut TestInstructionMeter { remaining: 2240 }).unwrap();

// run in jit, raise ExceededMaxInstructions(32, 2240)
let mut vm2 = EbpfVm::new(&executable, &mut [], &mut []).unwrap();
vm2.execute_program_jit(&mut TestInstructionMeter {remaining: 2040,}).unwrap();

exceed_instructions.o.zip

This issue will not trigger serious security risks.

When overflow-check is enabled, the disassembler would panic in signed_off_str when it tries to negate the 0x8000i16 value in

The text bytes PoC to trigger it:

[0x7b, 0x21, 0x00, 0x80, 0, 0, 0, 0]

The test code to reproduce:

let loader = BuiltinProgram::new_loader(
        Config::default(),
        FunctionRegistry::default(),
    );
let mut executable = Executable::<TestContextObject>::from_text_bytes(
    &[0x7b, 0x21, 0x00, 0x80, 0, 0, 0, 0],
    std::sync::Arc::new(loader),
    solana_rbpf::program::SBPFVersion::V2,
    FunctionRegistry::default(),
).unwrap();
let analysis = Analysis::from_executable(&executable).unwrap();
let mut reasm = Vec::new();
analysis.disassemble(&mut reasm).unwrap();

Running it in debug mode would encounter:

attempt to negate with overflow
thread 'test_store_negate' panicked at 'attempt to negate with overflow', src/disassembler.rs:48:27
stack backtrace:
   0: rust_begin_unwind
             at /rustc/*/library/std/src/panicking.rs:593:5
   1: core::panicking::panic_fmt
             at /rustc/*/library/core/src/panicking.rs:67:14
   2: core::panicking::panic
             at /rustc/*/library/core/src/panicking.rs:117:5
   3: solana_rbpf::disassembler::signed_off_str
             at ./src/disassembler.rs:48:27
   4: solana_rbpf::disassembler::st_reg_str
             at ./src/disassembler.rs:82:9
   5: solana_rbpf::disassembler::disassemble_instruction
             at ./src/disassembler.rs:142:58

In release mode, the disassembler result would be stxdw [r1-0x8000], r2, which doesn't necessarily pose the wrong result.

However, to enhance the robustness of the disassembler, the negate logic of i16 could be restructured in signed_off_str function.

Three least significant bits are operation class:

https://github.com/solana-labs/rbpf/blob/main/src/ebpf.rs#L61

This helps classify instruction at a broad level.

The address translation is known to be the bottleneck of most workloads in the BPF VM at the moment.

Ideas to improve the situation:

• Hoist address translation from loop bodies outside, so that they happen less frequently. This would require the static analyzer to be reliable and secure in order to detect loops. Also an efficient way to bypass the translated results into the body and check if they are still in bounds during the execution would be needed. Finally, a fallback in case the boundcheck fails is required too. Furthermore, dynamic calls must be restricted so that they can not jump into a loop. Either by excluding loops or only allowing registered symbols as jump table.
• Manually optimize the address translation on x86 instruction level to reduce redundant boundchecks and the need for register spilling. This will probably not yield much, maybe a few percent improvement.
• Change the memory model to something simpler, e.g. what WASM is doing. This would be the most radical change, but also the one which might help the most.

An instruction such as:

79a6b0ff00000000

Is disassembled to:

ldxdw r6, [r10+0xffb0]

Whereas I believe it should be:

ldxdw r6, [r10-0x50]

It seems like this applies to all instructions involving offsets.

This command:

rbpf_cli --use disassembler --elf spl_token-3.1.0.so

takes forever to complete with CPU usage = 100%.

The latest rbpf main branch had been used. The input file's location: https://github.com/solana-labs/solana/blob/master/program-test/src/programs/spl_token-3.1.0.so

Whenever a Syscall gets called, there is no way to pass a &mut context. In order to get mutable access to anything outside the virtual machine, you have to wrap a context in a Rc<RefCell<&mut X>> which has runtime overhead and also it's a bit ugly. https://github.com/hyperledger-labs/solang/blob/main/tests/solana.rs#L200

It would be nice if execute_program() had a generic parameter for a mutable reference, which would be passed to any syscall.

Even with the option --use interpreter the jit compiler is called. This causes an error on non-X86 architectures (ARM in my case). Is there a way to disable the jit compiler and run only the interpreter?
I tried by myself but it seems that the jit compiler registers syscalls (among other things) that are needed by the interpreter.

When I try to disassemble trace log in v0.2.38, all call's look like call [invalid]. But in v0.2.37 I didn't see this issue.

For example:

analysis.disassemble_trace_log(&mut std::io::stdout().lock(), trace).unwrap();

Outputs (removed all lines without call):

   14 [0000000000000000, 0000000200002FD0, 0000000000000001, 0000000000000000, 0000000000000030, 0000000000000000, 0000000200000FB8, 0000000000000000, 0000000000000000, 0000000000000000, 0000000200003000]  9189: call [invalid]
...
   64 [0000000000000030, 0000000000000030, 0000000000000008, 0000000000000000, 0000000000000030, 0000000000000000, 0000000200000FB8, 0000000000000008, 0000000000000030, 0000000000000000, 0000000200003000]  9204: call [invalid]
   65 [0000000000000030, 0000000000000030, 0000000000000008, 0000000000000000, 0000000000000030, 0000000000000000, 0000000200000FB8, 0000000000000008, 0000000000000030, 0000000000000000, 0000000200005000]  8955: call [invalid]
...
  119 [0000000300007FD0, 0000000000000020, 0000000000000008, 0000000400000000, 0000000000000000, 0000000000000000, 0000000400000008, 0000000300007FD0, 0000000000000030, 0000000000000008, 0000000200003000]  9348: call [invalid]
...
  158 [0000000300007FB0, 0000000000000028, 0000000000000008, 0000000300007FB0, 0000000300007FD0, 0000000000000000, 0000000400000008, 0000000000000052, 0000000000000030, 0000000000000008, 0000000200003000]  9365: call [invalid]
  159 [0000000300007FB0, 0000000000000028, 0000000000000008, 0000000300007FB0, 0000000300007FD0, 0000000000000000, 0000000400000008, 0000000000000052, 0000000000000030, 0000000000000008, 0000000200005000]  8955: call [invalid]
...
  280 [0000000300007FD0, 0000000200000FB8, 00000004000028EB, 0000000300007FD0, 0000000000000001, 0000000200001000, 0000000000000001, 0000000000000000, 0000000000000001, 0000000000000000, 0000000200001000]  7973: call [invalid]
...
  289 [0000000300007FD0, 0000000200002F88, 00000004000028C8, 0000000000000023, 0000000000000001, 0000000200001000, 0000000000000001, 0000000300007FD0, 00000004000028EB, 0000000200000FB8, 0000000200003000]  5713: call [invalid]
...
  319 [0000000200002F88, 0000000200004FC8, 00000004000028CA, 0000000000000020, 0000000000000014, 0000000200001000, 0000000200004FC8, 00000004000028C8, 0000000000000023, 0000000000000021, 0000000200005000]   355: call [invalid]
...
  364 [0000000200002F88, 0000000200004FC0, 00000004000028EA, 0000000000000001, 0000000000000014, 0000000200001000, 00387D782B39003C, 00000004000028EA, 0000000000000001, 0000000200002F88, 0000000200005000]   391: call [invalid]
...
  389 [0000000200002F88, 0000000200004F98, 0000000200004FC8, 0000000000000028, 0000000000000014, 0000000200001000, 00387D782B39003C, 0000000200004F98, 0000000000000001, 0000000200002F88, 0000000200005000]   400: call [invalid]
...
  454 [0000000200004F98, 0000000200004F5C, 0000000200004F98, 0000000000000024, 0000000000000005, 0000000000000005, 00387D782B39003C, 0000000200004F98, 0000000000000001, 0000000200002F88, 0000000200005000]   405: call [invalid]
...
  567 [0000000200002F88, 0000000200002FA8, 0000000200004F48, 0000000000000038, 0000000200004F7F, 0000000000000009, 0000000200002F88, 0000000200004F98, 00000000000000A8, 0000000200002F88, 0000000200005000]   344: call [invalid]
...
  668 [0000000200002FA8, 0000000200002F61, 0000000200002FB9, 0000000000000027, 0000000000000007, 0000000000000007, 00000000000000C0, 0000000000000014, 00000004000028EB, 387D782B39003C09, 0000000200003000]  5733: call [invalid]
...
  807 [0000000000000000, 0000000200002F88, 0000000200002F64, 0000000000000024, 0000000200002F87, 0000000000000000, 00000000000000C0, 0000000000000014, 00000004000028EB, 0000000200002F88, 0000000200003000]  5813: call [invalid]
... etc...
...
 2554 [0000000000000000, 0000000300007FD0, 0000000000000030, 0000000000000008, 0000000200004FEF, 0000000000000000, 0000000000000030, 0000000300008010, 0000000000000000, 0000000000000000, 0000000200001000]  8142: exit

Problem

ELF mandates the first section header to be SHT_NULL

OS-ELF-SUG-01

Proposed Solution

Fixed in 79209e1

Hi folks,

This is not a regular issue about Solana's rbpf.

I'm writing to let you know that there is an undergoing effort to define a more formal specification of eBPF, and to publish it as a “standard” for eBPF (to be hosted by the eBPF Foundation). This specification tries to account for the different implementations existing to date, including in Linux, ebpf-for-windows, uBPF, and the initial rbpf project too.

I know that Solana has been using eBPF, but there are not many bonds between your community and the rest of the BPF developers/users on other platforms (as far as I know). You are likely the main users of rbpf, so I thought I'd let you know, in case you want to get involved in this effort (if you wanted to be compliant to the standard in the future - the original rbpf may need some adjustments to be compliant, and I have no idea to what extent Solana's fork diverged from it), or at least so that you are aware of it.

Some relevant links:

• The ongoing discussion is on the Linux BPF mailing list here.
• There was a talk on the topic last week at LPC, although mostly addressing technical points raised while writing the doc.

Of course, everybody's welcome to join the discussions.

[EDIT: This issue is just FYI, no action item here, so you can close it anytime.]

generated dot files of even the most simple solana programs are completely unusable:

example of a control flow graph:

There is the error ELFError::MultipleTextSections:

Multiple text sections, consider removing llc option: -function-sections

Which is returned in a single place, here:

The error message and name are misleading, because it can also be thrown when there is no text section at all. @enriquefynn and me just discovered this the hard way.

There seems to be the likelihood that certain ops, especially memory ops (i.e. reg load, jmp which requires a random instruction seek), might need to be charged higher amount of compute units, for the reason that they can be several times slower than an alu op (100ns RAM seek is ~300x slower than an i32 add). At 200_000 compute units, at 100ns per RAM operation, this would result in a program time of at least 20ms, which I think is a lot higher than desired.

This is a good explanation for Serum's bad CU/us ratio, with a median of 7, which is consistent with 100ns per opcode. That's because Serum's critbit tree data structure does a lot of random reads from a 1MB+memory region, which maybe it lives in L3 cache or even loaded cold from RAM - so dominated by opcodes 30-300x slower than ALU opcode.

In the model we consider, the majority of opcodes have a cost of 1, and they dominate.

For every expensive opcode, during emission, we increase the compute_meter by the opcode cost minus 1. Opcode extra costs are stored in an array, so one can index directly into it during instruction emission via the u8 insn.opc. The load and add instruction is not emitted when the extra cost is 0 (obviously).

At the very least, the cost of adding a constant value to the compute meter during execution, being an ALU operation, is at least comparable to the cost of an expensive operation. For instance, a memory operation will probably always have to be at least 30x CUs of an ALU, so the cost of loading the compute meter, probably living in the L1 cache, and adding a constant to it will consume far fewer cycles by comparison.

Another option is if the bpf can be analysed and segmented into basic blocks, thus reducing the need to deal with arbitrary jumps. (Edit: I guess this is ongoing work with static analysis).

For every ordinary opcode, we do nothing as per the constant 1 integral.

The summary:

1. per-address translation time agrees with previous measured results of about 10-20ns.
2. syscall does better than load/stores for above 3-4 address translations.

Here are my results for the program below (in us) for 65535 iterations for n 64-bit memcpys:

1: 4909
2: 7204
3: 9742
4: 12118
5: 14699
6: 17654
7: 20752
8: 22020

Here is the result for size=15 corresponding to 8 load/store:

22171

Taking the delta, this suggests that the time per load/store is around 2800us / (2^16 - 1) / 2 * 1000 = 21.4ns.

Here is the result (in us) with (2^16 - 1) iter and sizes

64: 25869
72: 6792
256: 6940
4096: 10193
8192: 14378

For 255 iterations of a 8192 byte memcpy, we take only 75us, or about 294ns per iteration, or 0.3ns per 64-bit word. This suggests that the syscall is very efficient.

Here is the program used, inlining the memcpy only available on master:
memcpy.zip

fn process_instruction(
    _program_id: &Pubkey,
    accounts: &[AccountInfo],
    _instruction_data: &[u8],
) -> ProgramResult {
    let size = u32::from_le_bytes(accounts[0].data.borrow()[..4].try_into().unwrap()) as usize;
    let iter = u32::from_le_bytes(accounts[0].data.borrow()[4..8].try_into().unwrap());

    unsafe {
        let layout = Layout::from_size_align(size, mem::align_of::<u8>()).unwrap();
        let src1 = alloc::alloc::alloc(layout);
        let src2 = alloc::alloc::alloc(layout);
        let dst = alloc::alloc::alloc(layout);

        let memcpy = |dest: *mut u8, src: *const u8, n: usize| -> *mut u8 {
            let chunks = (n / 8) as isize;
            let nstore = n - (7 * chunks) as usize;
            if nstore > 8 {
                sol_memcpy(
                    std::slice::from_raw_parts_mut(dest as *mut u8, 0),
                    std::slice::from_raw_parts(src, 0),
                    n as usize,
                );
                return dest;
            }
            let mut i: isize = 0;
            if chunks != 0 {
                let dest_64 = dest as *mut _ as *mut u64;
                let src_64 = src as *const _ as *const u64;
                while i < chunks {
                    *dest_64.offset(i) = *src_64.offset(i);
                    i += 1;
                }
                i *= 8;
            }
            while i < n as isize {
                *dest.offset(i) = *src.offset(i);
                i += 1;
            }
            dest
        };

        for it in 0..iter {
            if it & 1 == 1 {
                memcpy(dst, src1, size);
                assert_eq!(*dst, *src1);
            } else {
                memcpy(dst, src2, size);
                assert_eq!(*dst, *src1);
            };
        }
    }

    Ok(())
}

I would like to make interpreter work on 32bit architechtures. Currently there is no compilation error and regular programs seem to work as expected but various memory readings during syscalls like InvokeSignedRust return invalid pointers which results in program fails to complete error.

Going by the comment of

// Memory map regions virtual addresses need to be (1 << VIRTUAL_ADDRESS_BITS) bytes apart.
// Also the region at index 0 should be skipped to catch NULL ptr accesses.

I've played with some of the values like MM_PROGRAM_START and VIRTUAL_ADDRESS_BITS and got some improvements(some of the memory translations ended up being correct during syscalls) but programs still failed to complete on 32bit and worked fine on 64bit after the changes.

And what's the effect of program-runtime-v2 on this? Particularly this part solana-labs/solana#29864:

Dynamic function calls replacing CPI and Syscalls
Replace VM nesting by dynamic linking using two levels of indirection
[Not MVP] Replace syscalls by CPI to built-in programs

A general advice on how to achieve this would be really helpful, thank you!

The JIT only supports non-Windows targets:

This issue is not pressing, nor is it a call to action. Instead, it can be used for tracking in other systems that may be blocked. I imagine a Windows-JIT will be difficult to implement because of all the POSIX-specific parts of the implementation, and yield very little reward.

Related: #193
Here is the x86 generated by rust.godbolt with flag --O from the following source:

const MM_INPUT_START: i64 = 0x400000000;
const MM_HEAP_START: i64 = 0x300000000;

const INPUT_HOST_ADDR: i64 = 500_000;
const HEAP_HOST_ADDR: i64 = 1_000_000;

const OFFSET: i16 = 0;

const INPUT_LEN: i64 = 16;
// 1MiB
const HEAP_LEN: i64 = 100_000;

const TYPE_LEN: i64 = 0x8;

pub fn emit_addr_translation(vm_addr: u64) -> u64 {
    if vm_addr >= (MM_INPUT_START - OFFSET as i64) as u64 {
        if vm_addr < (MM_INPUT_START + INPUT_LEN - OFFSET as i64 - TYPE_LEN) as u64 {
            return (INPUT_HOST_ADDR + OFFSET as i64 - MM_INPUT_START) as u64 + vm_addr;
        } else {
            return u64::MAX;
        }
    } else if vm_addr >= (MM_HEAP_START - OFFSET as i64) as u64 {
        if vm_addr < (MM_HEAP_START + HEAP_LEN - OFFSET as i64 - TYPE_LEN) as u64 {
            return (HEAP_HOST_ADDR + OFFSET as i64 - MM_HEAP_START) as u64 + vm_addr;
        } else {
            return u64::MAX;
        }
    } else {
        return u64::MAX;
    }
}

pub fn main(){
    println!("{:?}", emit_addr_translation(MM_INPUT_START as u64 + 5));
    println!("{:?}", emit_addr_translation(MM_HEAP_START as u64 + 5));
    println!("{:?}", emit_addr_translation(MM_HEAP_START as u64 + 1_000_000));
    println!("{:?}", emit_addr_translation(MM_HEAP_START as u64 + 90_000));
    println!("{:?}", emit_addr_translation(90_000));
}

example::emit_addr_translation:
        mov     rax, rdi
        shr     rax, 34 ; check if vm_addr >= (lower bound: MM_INPUT_START - OFFSET)
        jne     .LBB1_3
        movabs  rax, -12884901888 ; rax <- (lower bound) MM_HEAP_START - OFFSET
        lea     rcx, [rdi + rax] ; vm_addr - lower bound
        
        ; check lower_bound <= vm_addr < upper bound (INPUT_LEN + OFFSET - TYPE_LEN)
        ; i.e. 0 <= vm_addr - lower_bound < upper bound (INPUT_LEN + OFFSET - TYPE_LEN) - lower_bound
        cmp     rcx, 99992
        lea     rcx, [rdi + rax + 1000000] ; rcx <- host_ptr
        jmp     .LBB1_2
.LBB1_3:
        movabs  rax, 17179869184 ; 0x400000000 
        add     rax, 8 ; (upper bound) + INPUT_LEN - OFFSET - TYPE_LEN
        movabs  rcx, -17179369184 ; INPUT_HOST_ADDR + OFFSET - MM_INPUT_START
        add     rcx, rdi ; rcx <- host_ptr
        cmp     rdi, rax ; check vm_addr ptr upper bound
.LBB1_2:
        mov     rax, -1 ; error return address (u64::MAX)
        cmovb   rax, rcx ; if (condition) rax <- host_ptr
        ret

Here is the equivalent with offset = -4:

example::emit_addr_translation:
        movabs  rax, 17179869188
        cmp     rdi, rax
        jae     .LBB1_3
        movabs  rax, -12884901892
        lea     rcx, [rdi + rax]
        cmp     rcx, 99992
        lea     rcx, [rdi + rax + 1000000]
        jmp     .LBB1_2
.LBB1_3:
        add     rax, 8
        movabs  rcx, -17179369188
        add     rcx, rdi
        cmp     rdi, rax
.LBB1_2:
        mov     rax, -1
        cmovb   rax, rcx
        ret

offset = 4:

example::emit_addr_translation:
        movabs  rax, 17179869179
        cmp     rdi, rax
        jbe     .LBB3_1
        add     rax, 9
        movabs  rcx, -17179369180
        add     rcx, rdi
        cmp     rdi, rax
        jmp     .LBB3_2
.LBB3_1:
        movabs  rax, -12884901884
        lea     rcx, [rdi + rax]
        cmp     rcx, 99992
        lea     rcx, [rdi + rax + 1000000]
.LBB3_2:
        mov     rax, -1
        cmovb   rax, rcx
        ret

You will get a different result with -C opt-level=2 and -C opt-level=3

Just to give some basic ideas for how to inline the bounds checks as x86.

As an idea of the overhead, this is about 10 instructions, and at IPC = 1, about 2.5ns. This is compared to the current measured overhead of addr translation of about 9-12ns (4GHz).

So the potential savings here is about 3.6x per addr translation. Which doesn't seem that great.

It does seem like BCE might be necessary here...

I believe that in order to achieve WASM-like performance, you really do need linear memory. The VM address is an offset, which doesn't require any lower bounds checking, so can be directly inlined as a u64 address by adding the base pointer. This makes a WASM bounds check just a single cmp and jmp, which maybe takes 1 or 2 cycles, and makes it easier for the processor to do speculative prefetching.

Problem

A program can be a maximum of 10MB, or roughly 1_250_000 opcodes (8 bytes per opcode). Since there are no compute meter checks for straight line programs, a program can exceed their compute budget willfully.

Solution

Either:

1. Every random noop (or random subset thereof) should be replaced by emit_validate_and_profile_instruction_count
2. When emitting instructions, maintain a counter alongside the cumulative cost. Increment counter by cost of ops encountered. Whenever one does emit_validate_and_profile_instruction_count, reset counter. If counter exceeds STRAIGHT_LINE_VALIDATE_THRESHOLD: u64 = 1000, do emit_validate_and_profile_instruction_count. This ensures that at most, a program will exceed the given budget by 1000.

Misc

This also suggests that 10MB programs may be a little too large to do JIT for on-demand - suggesting that programs of a certain size (> 100_000 opcodes) should be JITed asynchronously and interpreted on-demand until JIT is ready.

Will be interested to see JIT timings for programs of varying length.

The LE/BE instructions are a remnant from the Linux eBPF ISA lineage. They used to allow endianness conversions given unknown host endianness.

Solana mainnet is always little-endian however, regardless of host endianness. Therefore an LE opcode doesn't make much sense.

In practice,

• le16 <reg> is and <reg>, 0xffff
• le32 <reg> is and <reg>, 0xffffffff or mov32 <reg>, <reg>
• le64 does nothing

Therefore I propose renaming the LE mnemonics to avoid confusion.

• le16 into mask16
• le32 into mask32
• le64 into nop