// SPDX-License-Identifier: GPL-2.0
/* Copyright (c) 2025 Isovalent */

#include <linux/bpf.h>
#include <bpf/bpf_helpers.h>
#include "bpf_misc.h"
#include "../../../include/linux/filter.h"

#if defined(__TARGET_ARCH_x86) || defined(__TARGET_ARCH_arm64) || \
	defined(__TARGET_ARCH_powerpc) || \
	(defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64)

#define DEFINE_SIMPLE_JUMP_TABLE_PROG(NAME, SRC_REG, OFF, IMM, OUTCOME)	\
									\
	SEC("socket")							\
	OUTCOME								\
	__naked void jump_table_ ## NAME(void)				\
	{								\
		asm volatile ("						\
		.pushsection .jumptables,\"\",@progbits;		\
	jt0_%=:								\
		.quad ret0_%= - socket;					\
		.quad ret1_%= - socket;					\
		.size jt0_%=, 16;					\
		.global jt0_%=;						\
		.popsection;						\
									\
		r0 = jt0_%= ll;						\
		r0 += 8;						\
		r0 = *(u64 *)(r0 + 0);					\
		.8byte %[gotox_r0];					\
		ret0_%=:						\
		r0 = 0;							\
		exit;							\
		ret1_%=:						\
		r0 = 1;							\
		exit;							\
	"	:							\
		: __imm_insn(gotox_r0, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, (SRC_REG), (OFF) , (IMM))) \
		: __clobber_all);					\
	}

/*
 * The first program which doesn't use reserved fields
 * loads and works properly. The rest fail to load.
 */
DEFINE_SIMPLE_JUMP_TABLE_PROG(ok,                          BPF_REG_0, 0, 0, __success __retval(1))
DEFINE_SIMPLE_JUMP_TABLE_PROG(reserved_field_src_reg,      BPF_REG_1, 0, 0, __failure __msg("BPF_JA|BPF_X uses reserved fields"))
DEFINE_SIMPLE_JUMP_TABLE_PROG(reserved_field_non_zero_off, BPF_REG_0, 1, 0, __failure __msg("BPF_JA|BPF_X uses reserved fields"))
DEFINE_SIMPLE_JUMP_TABLE_PROG(reserved_field_non_zero_imm, BPF_REG_0, 0, 1, __failure __msg("BPF_JA|BPF_X uses reserved fields"))

#define DEFINE_TERMINAL_GOTOX_PROG(NAME, BASE)			\
	__naked void NAME(void)					\
	{							\
	asm volatile ("						\
	.pushsection .jumptables,\"\",@progbits;		\
jt0_%=:							\
	.quad ret0_%= - " BASE ";				\
	.size jt0_%=, 8;					\
	.global jt0_%=;						\
	.popsection;						\
								\
	r0 = jt0_%= ll;						\
	r0 = *(u64 *)(r0 + 0);					\
	goto end_%=;						\
ret0_%=:							\
	r0 = 0;							\
	exit;							\
end_%=:							\
	.8byte %[gotox_r0];					\
"	:							\
	: __imm_insn(gotox_r0, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X,	\
					    BPF_REG_0, 0, 0, 0))	\
	: __clobber_all);					\
	}

SEC("socket")
__success __retval(0)
DEFINE_TERMINAL_GOTOX_PROG(jump_table_terminal_gotox, "socket")

static __noinline __used
DEFINE_TERMINAL_GOTOX_PROG(terminal_gotox_subprog1, ".text")

static __noinline __used int terminal_gotox_subprog2(void)
{
	return 0;
}

SEC("socket")
__success __retval(0)
__naked void jump_table_terminal_gotox_subprog(void)
{
	asm volatile ("						\
	call terminal_gotox_subprog1;				\
	call terminal_gotox_subprog2;				\
	exit;							\
"	::: __clobber_all);
}

/*
 * Gotox is forbidden when there is no jump table loaded
 * which points to the sub-function where the gotox is used
 */
SEC("socket")
__failure __msg("no jump tables found for subprog starting at 0")
__msg(">>> 1 | (0d) gotox r0")
__naked void jump_table_no_jump_table(void)
{
	asm volatile ("						\
	r0 = 0;							\
	.8byte %[gotox_r0];					\
	r0 = 1;							\
	exit;							\
"	:							\
	: __imm_insn(gotox_r0, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, 0, 0 , 0))
	: __clobber_all);
}

/*
 * Incorrect type of the target register, only PTR_TO_INSN allowed
 */
SEC("socket")
__failure __msg("R1 has type scalar, expected PTR_TO_INSN")
__naked void jump_table_incorrect_dst_reg_type(void)
{
	asm volatile ("						\
	.pushsection .jumptables,\"\",@progbits;		\
jt0_%=:								\
	.quad ret0_%= - socket;					\
	.quad ret1_%= - socket;					\
	.size jt0_%=, 16;					\
	.global jt0_%=;						\
	.popsection;						\
								\
	r0 = jt0_%= ll;						\
	r0 += 8;						\
	r0 = *(u64 *)(r0 + 0);					\
	r1 = 42;						\
	.8byte %[gotox_r1];					\
	ret0_%=:						\
	r0 = 0;							\
	exit;							\
	ret1_%=:						\
	r0 = 1;							\
	exit;							\
"	:							\
	: __imm_insn(gotox_r1, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0 , 0))
	: __clobber_all);
}

#define DEFINE_INVALID_SIZE_PROG(READ_SIZE, OUTCOME)			\
									\
	SEC("socket")							\
	OUTCOME								\
	__naked void jump_table_invalid_read_size_ ## READ_SIZE(void)	\
	{								\
		asm volatile ("						\
		.pushsection .jumptables,\"\",@progbits;		\
	jt0_%=:								\
		.quad ret0_%= - socket;					\
		.quad ret1_%= - socket;					\
		.size jt0_%=, 16;					\
		.global jt0_%=;						\
		.popsection;						\
									\
		r0 = jt0_%= ll;						\
		r0 += 8;						\
		r0 = *(" #READ_SIZE " *)(r0 + 0);			\
		.8byte %[gotox_r0];					\
		ret0_%=:						\
		r0 = 0;							\
		exit;							\
		ret1_%=:						\
		r0 = 1;							\
		exit;							\
	"	:							\
		: __imm_insn(gotox_r0, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, 0, 0 , 0)) \
		: __clobber_all);					\
	}

DEFINE_INVALID_SIZE_PROG(u32, __failure __msg("Invalid read of 4 bytes from insn_array"))
DEFINE_INVALID_SIZE_PROG(u16, __failure __msg("Invalid read of 2 bytes from insn_array"))
DEFINE_INVALID_SIZE_PROG(u8,  __failure __msg("Invalid read of 1 bytes from insn_array"))

SEC("socket")
__failure __msg("misaligned value access off 1+0 size 8")
__naked void jump_table_misaligned_access(void)
{
	asm volatile ("						\
	.pushsection .jumptables,\"\",@progbits;		\
jt0_%=:								\
	.quad ret0_%= - socket;					\
	.quad ret1_%= - socket;					\
	.size jt0_%=, 16;					\
	.global jt0_%=;						\
	.popsection;						\
								\
	r0 = jt0_%= ll;						\
	r0 += 1;						\
	r0 = *(u64 *)(r0 + 0);					\
	.8byte %[gotox_r0];					\
	ret0_%=:						\
	r0 = 0;							\
	exit;							\
	ret1_%=:						\
	r0 = 1;							\
	exit;							\
"	:							\
	: __imm_insn(gotox_r0, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, 0, 0 , 0))
	: __clobber_all);
}

SEC("socket")
__failure __msg("invalid access to map value, value_size=16 off=24 size=8")
__naked void jump_table_invalid_mem_acceess_pos(void)
{
	asm volatile ("						\
	.pushsection .jumptables,\"\",@progbits;		\
jt0_%=:								\
	.quad ret0_%= - socket;					\
	.quad ret1_%= - socket;					\
	.size jt0_%=, 16;					\
	.global jt0_%=;						\
	.popsection;						\
								\
	r0 = jt0_%= ll;						\
	r0 += 24;						\
	r0 = *(u64 *)(r0 + 0);					\
	.8byte %[gotox_r0];					\
	ret0_%=:						\
	r0 = 0;							\
	exit;							\
	ret1_%=:						\
	r0 = 1;							\
	exit;							\
"	:							\
	: __imm_insn(gotox_r0, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, 0, 0 , 0))
	: __clobber_all);
}

SEC("socket")
__failure __msg("R0 min value is negative")
__naked void jump_table_invalid_mem_acceess_neg(void)
{
	asm volatile ("						\
	.pushsection .jumptables,\"\",@progbits;		\
jt0_%=:								\
	.quad ret0_%= - socket;					\
	.quad ret1_%= - socket;					\
	.size jt0_%=, 16;					\
	.global jt0_%=;						\
	.popsection;						\
								\
	r0 = jt0_%= ll;						\
	r0 -= 24;						\
	r0 = *(u64 *)(r0 + 0);					\
	.8byte %[gotox_r0];					\
	ret0_%=:						\
	r0 = 0;							\
	exit;							\
	ret1_%=:						\
	r0 = 1;							\
	exit;							\
"	:							\
	: __imm_insn(gotox_r0, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, 0, 0 , 0))
	: __clobber_all);
}

SEC("socket")
__success __retval(1)
__naked void jump_table_add_sub_ok(void)
{
	asm volatile ("						\
	.pushsection .jumptables,\"\",@progbits;		\
jt0_%=:								\
	.quad ret0_%= - socket;					\
	.quad ret1_%= - socket;					\
	.size jt0_%=, 16;					\
	.global jt0_%=;						\
	.popsection;						\
								\
	r0 = jt0_%= ll;						\
	r0 -= 24;						\
	r0 += 32;						\
	r0 = *(u64 *)(r0 + 0);					\
	.8byte %[gotox_r0];					\
	ret0_%=:						\
	r0 = 0;							\
	exit;							\
	ret1_%=:						\
	r0 = 1;							\
	exit;							\
"	:							\
	: __imm_insn(gotox_r0, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, 0, 0 , 0))
	: __clobber_all);
}

SEC("socket")
__failure __msg("write into map forbidden, value_size=16 off=8 size=8")
__naked void jump_table_no_writes(void)
{
	asm volatile ("						\
	.pushsection .jumptables,\"\",@progbits;		\
jt0_%=:								\
	.quad ret0_%= - socket;					\
	.quad ret1_%= - socket;					\
	.size jt0_%=, 16;					\
	.global jt0_%=;						\
	.popsection;						\
								\
	r0 = jt0_%= ll;						\
	r0 += 8;						\
	r1 = 0xbeef;						\
	*(u64 *)(r0 + 0) = r1;					\
	.8byte %[gotox_r0];					\
	ret0_%=:						\
	r0 = 0;							\
	exit;							\
	ret1_%=:						\
	r0 = 1;							\
	exit;							\
"	:							\
	: __imm_insn(gotox_r0, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, 0, 0 , 0))
	: __clobber_all);
}

#define DEFINE_JUMP_TABLE_USE_REG(REG)					\
	SEC("socket")							\
	__success __retval(1)						\
	__naked void jump_table_use_reg_r ## REG(void)			\
	{								\
		asm volatile ("						\
		.pushsection .jumptables,\"\",@progbits;		\
	jt0_%=:								\
		.quad ret0_%= - socket;					\
		.quad ret1_%= - socket;					\
		.size jt0_%=, 16;					\
		.global jt0_%=;						\
		.popsection;						\
									\
		r0 = jt0_%= ll;						\
		r0 += 8;						\
		r" #REG " = *(u64 *)(r0 + 0);				\
		.8byte %[gotox_rX];					\
		ret0_%=:						\
		r0 = 0;							\
		exit;							\
		ret1_%=:						\
		r0 = 1;							\
		exit;							\
	"	:							\
		: __imm_insn(gotox_rX, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_ ## REG, 0, 0 , 0)) \
		: __clobber_all);					\
	}

DEFINE_JUMP_TABLE_USE_REG(0)
DEFINE_JUMP_TABLE_USE_REG(1)
DEFINE_JUMP_TABLE_USE_REG(2)
DEFINE_JUMP_TABLE_USE_REG(3)
DEFINE_JUMP_TABLE_USE_REG(4)
DEFINE_JUMP_TABLE_USE_REG(5)
DEFINE_JUMP_TABLE_USE_REG(6)
DEFINE_JUMP_TABLE_USE_REG(7)
DEFINE_JUMP_TABLE_USE_REG(8)
DEFINE_JUMP_TABLE_USE_REG(9)

__used static int test_subprog(void)
{
	return 0;
}

SEC("socket")
__failure __msg("jump table of subprog starting at 0 spans multiple subprogs")
__naked void jump_table_outside_subprog(void)
{
	asm volatile ("						\
	.pushsection .jumptables,\"\",@progbits;		\
jt0_%=:								\
	.quad ret0_%= - socket;					\
	.quad ret1_%= - socket;					\
	.quad ret_out_%= - socket;				\
	.size jt0_%=, 24;					\
	.global jt0_%=;						\
	.popsection;						\
								\
	r0 = jt0_%= ll;						\
	r0 += 8;						\
	r0 = *(u64 *)(r0 + 0);					\
	.8byte %[gotox_r0];					\
	ret0_%=:						\
	r0 = 0;							\
	exit;							\
	ret1_%=:						\
	r0 = 1;							\
	call test_subprog;					\
	exit;							\
	ret_out_%=:						\
"	:							\
	: __imm_insn(gotox_r0, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, 0, 0 , 0))
	: __clobber_all);
}

SEC("socket")
__success __retval(1)
__naked void jump_table_contains_non_unique_values(void)
{
	asm volatile ("						\
	.pushsection .jumptables,\"\",@progbits;		\
jt0_%=:								\
	.quad ret0_%= - socket;					\
	.quad ret1_%= - socket;					\
	.quad ret0_%= - socket;					\
	.quad ret1_%= - socket;					\
	.quad ret0_%= - socket;					\
	.quad ret1_%= - socket;					\
	.quad ret0_%= - socket;					\
	.quad ret1_%= - socket;					\
	.quad ret0_%= - socket;					\
	.quad ret1_%= - socket;					\
	.size jt0_%=, 80;					\
	.global jt0_%=;						\
	.popsection;						\
								\
	r0 = jt0_%= ll;						\
	r0 += 8;						\
	r0 = *(u64 *)(r0 + 0);					\
	.8byte %[gotox_r0];					\
	ret0_%=:						\
	r0 = 0;							\
	exit;							\
	ret1_%=:						\
	r0 = 1;							\
	exit;							\
"	:							\
	: __imm_insn(gotox_r0, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, 0, 0 , 0))
	: __clobber_all);
}

/* check valid spill/fill, ptr to insn */
SEC("socket")
__success
__naked void spill_fill_ptr_to_insn(void)
{
	asm volatile (
	".pushsection .jumptables,\"\",@progbits;"
	"jt0_%=:"
	".quad ret0_%= - socket;"
	".size jt0_%=, 8;"
	".global jt0_%=;"
	".popsection;"
	"r0 = jt0_%= ll;"
	"r0 = *(u64 *)(r0 + 0);"
	"*(u64 *)(r10 - 8) = r0;"
	"r0 = *(u64 *)(r10 - 8);"
	".8byte %[gotox_r0];"
	"ret0_%=:"
	"r0 = 0;"
	"exit;"
	:
	: __imm_insn(gotox_r0, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, 0, 0, 0))
	: __clobber_all);
}

/*
 * Emit each table entry next to the instruction it targets. Numeric labels
 * can be reused by .rept, while %= keeps table symbols unique per asm block.
 * BASE is the code section: libbpf relocates section-relative byte offsets
 * to instruction offsets in the loaded program.
 */
#define GOTOX_TABLE_BEGIN(COUNT) \
	".pushsection .jumptables,\"\",@progbits;" \
	"jt_%=:;" \
	".global jt_%=;" \
	".size jt_%=, 8 * (" #COUNT ");" \
	".popsection;" \
	"r1 = jt_%= ll;"

#define GOTOX_TABLE_ENTRY(LABEL, BASE) \
	".pushsection .jumptables,\"\",@progbits;" \
	".quad " LABEL " - " BASE ";" \
	".popsection;"

/* N gotox instructions, each targeting all N gotox plus the final block. */
#define GOTOX_SELF_TARGETS(N, BASE) \
	GOTOX_TABLE_BEGIN(N + 1) \
	"r0 = 0;" \
	".rept " #N ";" \
		GOTOX_TABLE_ENTRY("1f", BASE) \
		"1:; .8byte %[gotox];" \
	".endr;" \
	GOTOX_TABLE_ENTRY("2f", BASE) \
	"2:;"

#define GOTOX_OPERAND \
	__imm_insn(gotox, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, 0, 0, 0))

/*
 * Count edges even when their targets are already discovered. These
 * programs deliberately use a scalar: the CFG edge limit must reject them
 * before symbolic verification reaches the invalid gotox operand.
 */
SEC("socket")
__description("too-many-gotox-edges")
__failure __msg("number of indirect jump edges in the program exceeds")
__naked void too_many_gotox_edges(void)
{
	asm volatile (
		/* 1000 * 1001 = 1,001,000 edges. */
		GOTOX_SELF_TARGETS(1000, "socket")
		"r0 = 0; exit;"
		: : GOTOX_OPERAND : __clobber_all);
}

SEC("socket")
__description("gotox-edges-at-limit")
__failure __msg("Too many nested loops")
__naked void gotox_edges_at_limit(void)
{
	asm volatile (
		/*
		 * 1000 gotox * 1000 targets = 1,000,000 CFG edges. At run
		 * time, each block loads the next table entry and jumps to
		 * the following block, so the program terminates.
		 *
		 * Every block can jump to every later block, so the CFG is
		 * a nest of ~1000 irreducible loops, deeper than the
		 * verifier's loop stack; the program is rejected.
		 */
		GOTOX_TABLE_BEGIN(1000)
		".rept 1000;"
			GOTOX_TABLE_ENTRY("1f", "socket")
			"r0 = *(u64 *)(r1 + 0);"
			"r1 += 8;"
			".8byte %[gotox];"
			"1:;"
		".endr;"
		"r0 = 0; exit;"
		: : GOTOX_OPERAND : __clobber_all);
}

static __noinline __used __naked void gotox_edges_subprog(void)
{
	asm volatile (
		GOTOX_SELF_TARGETS(750, ".text")
		"r0 = 0; exit;"
		: : GOTOX_OPERAND : __clobber_all);
}

SEC("socket")
__description("gotox-edges-across-subprogs")
__failure __msg("number of indirect jump edges in the program exceeds")
__naked void gotox_edges_across_subprogs(void)
{
	asm volatile (
		/* Each subprog has 563,250 edges; together, 1,126,500. */
		GOTOX_SELF_TARGETS(750, "socket")
		"call gotox_edges_subprog;"
		"exit;"
		: : GOTOX_OPERAND : __clobber_all);
}

/*
 * The gotox target is a ja +0, which the nop removal pass must keep as the
 * jump table still names it.
 */
SEC("socket")
__success __retval(0)
__xlated("goto pc+0")
__naked void jump_table_target_nop(void)
{
	asm volatile ("						\
	.pushsection .jumptables,\"\",@progbits;		\
jt0_%=:								\
	.quad nop_%= - socket;					\
	.size jt0_%=, 8;					\
	.global jt0_%=;						\
	.popsection;						\
								\
	r0 = jt0_%= ll;						\
	r0 = *(u64 *)(r0 + 0);					\
	.8byte %[gotox_r0];					\
nop_%=:								\
	goto +0;						\
	r0 = 0;							\
	exit;							\
"	:
	: __imm_insn(gotox_r0, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, 0, 0, 0))
	: __clobber_all);
}

#endif /* gotox: x86, arm64, powerpc, riscv64 */

char _license[] SEC("license") = "GPL";