Maximum ebpf instruction count

[dthaler]

Linux apparently has a limit of INT_MAX instructions since 5.2.
Earlier versions had a limit of 4096 instructions.

The ubpf jitter is currently capped at 64k of machine code.
The ubpf interpreter is currently capped at UINT32_MAX of bytes (i.e., UINT32_MAX / 8 instructions).
These are higher than the old Linux limit of 4096, but lower than the newer limit of INT_MAX instructions.

[Alan-Jowett]

Feature Specification: Configurable Instruction Count Limits

Problem Statement

The current ubpf implementation has several hardcoded limits related to instruction counts that may not align with Linux kernel BPF limits or user requirements:

Limit	Current Value	Linux 5.2+	Issue
Max BPF instructions	65,536 (UBPF_MAX_INSTS)	~1 million (INT_MAX)	Programs > 64K fail
JIT buffer size	64KB (DEFAULT_JITTER_BUFFER_SIZE)	Dynamic	Large programs fail JIT
num_insts field	uint16_t (max 65,535)	N/A	Cannot store > 64K

Key Limitation: The num_insts field in struct ubpf_vm is a uint16_t, which fundamentally caps the instruction count at 65,535 regardless of other settings.

---

Background: Linux Kernel Limits

Version	Instruction Limit	Notes
< 4.15	4,096	Original limit
4.15-5.1	1,000,000	Increased for complex programs
5.2+	~2.1 billion (INT_MAX)	Effectively unlimited

Real-world BPF programs:

• Simple XDP: ~100-500 instructions
• Complex networking: 5,000-50,000 instructions
• Cilium/eBPF-based CNI: Can exceed 100,000 instructions
• BPF CO-RE with BTF: Often 10,000+ instructions

---

Goals

1. Allow programs with > 65,536 instructions
2. Make instruction limit configurable at compile time and/or runtime
3. Dynamically size JIT buffer based on program size
4. Maintain backward compatibility (default 64K limit)
5. Allow users to set lower limits for resource-constrained environments

---

Proposed Changes

1. Change num_insts to uint32_t

File: vm/ubpf_int.h

struct ubpf_vm
{
    struct ebpf_inst* insts;
    uint32_t num_insts;  // Changed from uint16_t
    // ...
};

Impact: This is an ABI-breaking change but necessary to support > 64K instructions.

---

2. Make UBPF_MAX_INSTS Configurable

File: vm/inc/ubpf.h (already partially done)

#if !defined(UBPF_MAX_INSTS)
#define UBPF_MAX_INSTS 65536  // Can be overridden at compile time
#endif

Add runtime configuration:

/**
 * @brief Set the maximum number of instructions allowed in a program.
 * @param vm The VM instance
 * @param max_insts Maximum instruction count (0 = use compile-time default)
 * @return 0 on success, -1 on error
 */
int ubpf_set_max_instructions(struct ubpf_vm* vm, uint32_t max_insts);

---

3. Dynamic JIT Buffer Sizing

Current code: vm/ubpf_vm.c:125

vm->jitter_buffer_size = DEFAULT_JITTER_BUFFER_SIZE;  // Fixed 64KB

Proposed approach:

// Estimate: ~20-50 bytes of x86 code per BPF instruction (conservative)
#define JIT_BYTES_PER_INST 50

size_t estimate_jit_buffer_size(uint32_t num_insts) {
    size_t estimated = (size_t)num_insts * JIT_BYTES_PER_INST;
    // Add overhead for prologue/epilogue/helper table
    estimated += 4096;
    // Round up to page size
    size_t page_size = 4096;
    return (estimated + page_size - 1) & ~(page_size - 1);
}

Alternative: Allow retry with larger buffer if initial allocation fails.

---

4. Update Data Structures Using UBPF_MAX_INSTS

Several arrays are sized based on UBPF_MAX_INSTS:

File: vm/ubpf_jit_support.c

state->pc_locs = calloc(UBPF_MAX_INSTS + 1, sizeof(state->pc_locs[0]));
state->jumps = calloc(UBPF_MAX_INSTS, sizeof(state->jumps[0]));
state->loads = calloc(UBPF_MAX_INSTS, sizeof(state->loads[0]));
state->leas = calloc(UBPF_MAX_INSTS, sizeof(state->leas[0]));
state->local_calls = calloc(UBPF_MAX_INSTS, sizeof(state->local_calls[0]));

Proposed: Size based on actual num_insts from loaded program:

state->pc_locs = calloc(vm->num_insts + 1, sizeof(state->pc_locs[0]));
// etc.

File: vm/ubpf_vm.c

vm->local_func_stack_usage = calloc(UBPF_MAX_INSTS, sizeof(struct ubpf_stack_usage));

Proposed: Size based on actual program, or use sparse storage.

---

API Changes

// New configuration function
int ubpf_set_max_instructions(struct ubpf_vm* vm, uint32_t max_insts);

// Existing (already implemented for JIT buffer)
int ubpf_set_jit_code_size(struct ubpf_vm* vm, size_t code_size);

// Optional: Query current limits
int ubpf_get_max_instructions(struct ubpf_vm* vm, uint32_t* max_insts);

---

Implementation Plan

Phase 1: Type Changes (Breaking Change)

1. Change num_insts from uint16_t to uint32_t
2. Update all code that uses num_insts or assumes 16-bit
3. Update validation to use runtime-configurable limit

Phase 2: Dynamic Sizing

1. Size JIT arrays based on loaded program size, not max
2. Implement dynamic JIT buffer sizing
3. Add ubpf_set_max_instructions() API

Phase 3: Memory Optimization (Optional)

1. Use sparse storage for large programs with few jumps/calls
2. Lazy allocation of JIT data structures
3. Consider mmap for very large programs

---

Files to Modify

File	Changes
vm/ubpf_int.h	Change num_insts to uint32_t
vm/inc/ubpf.h	Add ubpf_set_max_instructions() declaration
vm/ubpf_vm.c	Implement new API, update validation
vm/ubpf_jit_support.c	Dynamic array sizing
vm/ubpf_jit_x86_64.c	Update any uint16_t casts
vm/ubpf_jit_arm64.c	Same
vm/ubpf_jit.c	Dynamic JIT buffer sizing

---

Acceptance Criteria

• Programs with > 65,536 instructions can be loaded
• Programs with > 65,536 instructions can be JIT compiled
• ubpf_set_max_instructions() API allows runtime configuration
• Default behavior unchanged (64K limit) for backward compatibility
• JIT buffer automatically sizes based on program
• No memory waste for small programs (don't allocate 1M-entry arrays)
• All existing tests pass
• New tests for:
  • Program with exactly 65,536 instructions
  • Program with 65,537 instructions (boundary)
  • Program with 100,000 instructions
  • Setting custom max_insts lower than default
  • Setting custom max_insts higher than default

---

Test Cases

// Test: Large program loading
void test_large_program() {
    struct ubpf_vm* vm = ubpf_create();
    ubpf_set_max_instructions(vm, 1000000);  // Allow 1M instructions
    
    // Generate a program with 100K NOPs + exit
    size_t num_insts = 100000;
    struct ebpf_inst* code = malloc(num_insts * sizeof(struct ebpf_inst));
    for (size_t i = 0; i < num_insts - 1; i++) {
        code[i] = (struct ebpf_inst){.opcode = EBPF_OP_JA, .imm = 0};  // NOP-like
    }
    code[num_insts - 1] = (struct ebpf_inst){.opcode = EBPF_OP_EXIT};
    
    char* errmsg = NULL;
    int result = ubpf_load(vm, code, num_insts * 8, &errmsg);
    assert(result == 0);
    assert(errmsg == NULL);
    
    free(code);
    ubpf_destroy(vm);
}

// Test: JIT buffer auto-sizing
void test_jit_autosizing() {
    struct ubpf_vm* vm = ubpf_create();
    ubpf_set_max_instructions(vm, 200000);
    
    // Load 100K instruction program
    // ...
    
    char* errmsg = NULL;
    ubpf_jit_fn fn = ubpf_compile(vm, &errmsg);
    assert(fn != NULL);  // Should auto-size buffer
    
    ubpf_destroy(vm);
}

// Test: Custom lower limit
void test_lower_limit() {
    struct ubpf_vm* vm = ubpf_create();
    ubpf_set_max_instructions(vm, 1000);  // Restrict to 1K
    
    // Try to load 2K instruction program
    // ...
    
    char* errmsg = NULL;
    int result = ubpf_load(vm, code, 2000 * 8, &errmsg);
    assert(result != 0);  // Should fail
    assert(strstr(errmsg, "too many instructions") != NULL);
}

---

Performance Considerations

Change	Impact
uint16_t → uint32_t	Negligible (2 bytes more per VM)
Dynamic array sizing	Reduces memory for small programs
Large program support	More memory for JIT state
JIT buffer auto-sizing	May need realloc on buffer overflow

Memory estimate for 100K instruction program:

• pc_locs: 100K × 4 bytes = 400KB
• jumps: ~10K entries × 8 bytes = 80KB (sparse)
• JIT buffer: 100K × 50 bytes = 5MB
• Total: ~6MB (vs 256KB+ for current 64K limit arrays)

---

Backward Compatibility

1. Default limit unchanged: UBPF_MAX_INSTS remains 65536
2. API addition only: No existing functions change signature
3. Compile-time override: Users can #define UBPF_MAX_INSTS before including header
4. ABI break: num_insts type change affects struct layout - may need major version bump

---

References

• Linux BPF instruction limit history
• BPF complexity limit
• Current limits: vm/inc/ubpf.h lines 38-39
• JIT buffer: vm/ubpf_vm.c line 38, vm/ubpf_jit.c lines 97-100