// SPDX-License-Identifier: GPL-2.0
/* Copyright (c) 2024 Meta Platforms, Inc. and affiliates. */

#define BPF_NO_KFUNC_PROTOTYPES
#include <vmlinux.h>
#include <errno.h>
#include <bpf/bpf_helpers.h>
#include <bpf/bpf_tracing.h>
#include "bpf_misc.h"
#include "bpf_experimental.h"
#include <bpf_arena_common.h>

#define private(name) SEC(".bss." #name) __hidden __attribute__((aligned(8)))

#ifdef __TARGET_ARCH_arm64
#define ARENA_VM_START ((1ull << 32) | (~0u - __PAGE_SIZE * 2 + 1))
#else
#define ARENA_VM_START ((1ull << 44) | (~0u - __PAGE_SIZE * 2 + 1))
#endif

struct {
	__uint(type, BPF_MAP_TYPE_ARENA);
	__uint(map_flags, BPF_F_MMAPABLE);
	__uint(max_entries, 2); /* arena of two pages close to 32-bit boundary*/
	__ulong(map_extra, ARENA_VM_START); /* start of mmap() region */
} arena SEC(".maps");

SEC("socket")
__success __retval(0)
int basic_alloc1_nosleep(void *ctx)
{
#if defined(__BPF_FEATURE_ADDR_SPACE_CAST)
	volatile int __arena *page1, *page2, *no_page;

	page1 = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	if (!page1)
		return 1;
	*page1 = 1;
	page2 = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	if (!page2)
		return 2;
	*page2 = 2;
	no_page = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	if (no_page)
		return 3;
	if (*page1 != 1)
		return 4;
	if (*page2 != 2)
		return 5;
	bpf_arena_free_pages(&arena, (void __arena *)page2, 1);
	if (*page1 != 1)
		return 6;
	if (*page2 != 0 && *page2 != 2) /* use-after-free should return 0 or the stored value */
		return 7;
#endif
	return 0;
}

SEC("syscall")
__success __retval(0)
int basic_alloc1(void *ctx)
{
#if defined(__BPF_FEATURE_ADDR_SPACE_CAST)
	volatile int __arena *page1, *page2, *no_page, *page3;

	page1 = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	if (!page1)
		return 1;
	*page1 = 1;
	page2 = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	if (!page2)
		return 2;
	*page2 = 2;
	no_page = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	if (no_page)
		return 3;
	if (*page1 != 1)
		return 4;
	if (*page2 != 2)
		return 5;
	bpf_arena_free_pages(&arena, (void __arena *)page2, 1);
	if (*page1 != 1)
		return 6;
	if (*page2 != 0) /* use-after-free should return 0 */
		return 7;
	page3 = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	if (!page3)
		return 8;
	*page3 = 3;
	if (page2 != page3)
		return 9;
	if (*page1 != 1)
		return 10;
#endif
	return 0;
}

SEC("syscall")
__success __retval(0)
int free_scalar_below_arena(void *ctx)
{
	void __arena *page1, *page2, *page3;
	__u64 bad_addr = ARENA_VM_START - __PAGE_SIZE;

	page1 = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	if (!page1)
		return 1;

	page2 = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	if (!page2)
		return 2;

	page3 = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	if (page3)
		return 3;

	bpf_arena_free_pages(&arena, (void __arena *)bad_addr, 1);

	page3 = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	if (page3)
		return 4;

	return 0;
}

SEC("socket")
__success __retval(0)
int basic_alloc2_nosleep(void *ctx)
{
#if defined(__BPF_FEATURE_ADDR_SPACE_CAST)
	volatile char __arena *page1, *page2, *page3, *page4;

	page1 = bpf_arena_alloc_pages(&arena, NULL, 2, NUMA_NO_NODE, 0);
	if (!page1)
		return 1;
	page2 = page1 + __PAGE_SIZE;
	page3 = page1 + __PAGE_SIZE * 2;
	page4 = page1 - __PAGE_SIZE;
	*page1 = 1;
	*page2 = 2;
	*page3 = 3;
	*page4 = 4;
	if (*page1 != 1)
		return 1;
	if (*page2 != 2)
		return 2;
	if (*page3 != 0)
		return 3;
	if (*page4 != 0)
		return 4;
	bpf_arena_free_pages(&arena, (void __arena *)page1, 2);
	if (*page1 != 0 && *page1 != 1)
		return 5;
	if (*page2 != 0 && *page2 != 2)
		return 6;
	if (*page3 != 0)
		return 7;
	if (*page4 != 0)
		return 8;
#endif
	return 0;
}

SEC("syscall")
__success __retval(0)
int basic_alloc2(void *ctx)
{
#if defined(__BPF_FEATURE_ADDR_SPACE_CAST)
	volatile char __arena *page1, *page2, *page3, *page4;

	page1 = bpf_arena_alloc_pages(&arena, NULL, 2, NUMA_NO_NODE, 0);
	if (!page1)
		return 1;
	page2 = page1 + __PAGE_SIZE;
	page3 = page1 + __PAGE_SIZE * 2;
	page4 = page1 - __PAGE_SIZE;
	*page1 = 1;
	*page2 = 2;
	*page3 = 3;
	*page4 = 4;
	if (*page1 != 1)
		return 1;
	if (*page2 != 2)
		return 2;
	if (*page3 != 0)
		return 3;
	if (*page4 != 0)
		return 4;
	bpf_arena_free_pages(&arena, (void __arena *)page1, 2);
	if (*page1 != 0)
		return 5;
	if (*page2 != 0)
		return 6;
	if (*page3 != 0)
		return 7;
	if (*page4 != 0)
		return 8;
#endif
	return 0;
}

struct bpf_arena___l {
        struct bpf_map map;
} __attribute__((preserve_access_index));

SEC("socket")
__success __retval(0) __log_level(2)
int basic_alloc3_nosleep(void *ctx)
{
	struct bpf_arena___l *ar = (struct bpf_arena___l *)&arena;
	volatile char __arena *pages;

	pages = bpf_arena_alloc_pages(&ar->map, NULL, ar->map.max_entries, NUMA_NO_NODE, 0);
	if (!pages)
		return 1;
	return 0;
}

SEC("syscall")
__success __retval(0) __log_level(2)
int basic_alloc3(void *ctx)
{
	struct bpf_arena___l *ar = (struct bpf_arena___l *)&arena;
	volatile char __arena *pages;

	pages = bpf_arena_alloc_pages(&ar->map, NULL, ar->map.max_entries, NUMA_NO_NODE, 0);
	if (!pages)
		return 1;
	return 0;
}

SEC("socket")
__success __retval(0)
int basic_reserve1_nosleep(void *ctx)
{
#if defined(__BPF_FEATURE_ADDR_SPACE_CAST)
	char __arena *page;
	int ret;

	page = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	if (!page)
		return 1;

	page += __PAGE_SIZE;

	/* Reserve the second page */
	ret = bpf_arena_reserve_pages(&arena, page, 1);
	if (ret)
		return 2;

	/* Try to explicitly allocate the reserved page. */
	page = bpf_arena_alloc_pages(&arena, page, 1, NUMA_NO_NODE, 0);
	if (page)
		return 3;

	/* Try to implicitly allocate the page (since there's only 2 of them). */
	page = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	if (page)
		return 4;
#endif
	return 0;
}

SEC("syscall")
__success __retval(0)
int basic_reserve1(void *ctx)
{
#if defined(__BPF_FEATURE_ADDR_SPACE_CAST)
	char __arena *page;
	int ret;

	page = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	if (!page)
		return 1;

	page += __PAGE_SIZE;

	/* Reserve the second page */
	ret = bpf_arena_reserve_pages(&arena, page, 1);
	if (ret)
		return 2;

	/* Try to explicitly allocate the reserved page. */
	page = bpf_arena_alloc_pages(&arena, page, 1, NUMA_NO_NODE, 0);
	if (page)
		return 3;

	/* Try to implicitly allocate the page (since there's only 2 of them). */
	page = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	if (page)
		return 4;
#endif
	return 0;
}

SEC("socket")
__success __retval(0)
int basic_reserve2_nosleep(void *ctx)
{
#if defined(__BPF_FEATURE_ADDR_SPACE_CAST)
	char __arena *page;
	int ret;

	page = arena_base(&arena);
	ret = bpf_arena_reserve_pages(&arena, page, 1);
	if (ret)
		return 1;

	page = bpf_arena_alloc_pages(&arena, page, 1, NUMA_NO_NODE, 0);
	if ((u64)page)
		return 2;
#endif
	return 0;
}

SEC("syscall")
__success __retval(0)
int basic_reserve2(void *ctx)
{
#if defined(__BPF_FEATURE_ADDR_SPACE_CAST)
	char __arena *page;
	int ret;

	page = arena_base(&arena);
	ret = bpf_arena_reserve_pages(&arena, page, 1);
	if (ret)
		return 1;

	page = bpf_arena_alloc_pages(&arena, page, 1, NUMA_NO_NODE, 0);
	if ((u64)page)
		return 2;
#endif
	return 0;
}

/* Reserve the same page twice, should return -EBUSY. */
SEC("socket")
__success __retval(0)
int reserve_twice_nosleep(void *ctx)
{
#if defined(__BPF_FEATURE_ADDR_SPACE_CAST)
	char __arena *page;
	int ret;

	page = arena_base(&arena);

	ret = bpf_arena_reserve_pages(&arena, page, 1);
	if (ret)
		return 1;

	ret = bpf_arena_reserve_pages(&arena, page, 1);
	if (ret != -EBUSY)
		return 2;
#endif
	return 0;
}

SEC("syscall")
__success __retval(0)
int reserve_twice(void *ctx)
{
#if defined(__BPF_FEATURE_ADDR_SPACE_CAST)
	char __arena *page;
	int ret;

	page = arena_base(&arena);

	ret = bpf_arena_reserve_pages(&arena, page, 1);
	if (ret)
		return 1;

	ret = bpf_arena_reserve_pages(&arena, page, 1);
	if (ret != -EBUSY)
		return 2;
#endif
	return 0;
}

/* Try to reserve past the end of the arena. */
SEC("socket")
__success __retval(0)
int reserve_invalid_region_nosleep(void *ctx)
{
#if defined(__BPF_FEATURE_ADDR_SPACE_CAST)
	char __arena *page;
	int ret;

	/* Try a NULL pointer. */
	ret = bpf_arena_reserve_pages(&arena, NULL, 3);
	if (ret != -EINVAL)
		return 1;

	page = arena_base(&arena);

	ret = bpf_arena_reserve_pages(&arena, page, 3);
	if (ret != -EINVAL)
		return 2;

	ret = bpf_arena_reserve_pages(&arena, page, 4096);
	if (ret != -EINVAL)
		return 3;

	ret = bpf_arena_reserve_pages(&arena, page, (1ULL << 32) - 1);
	if (ret != -EINVAL)
		return 4;
#endif
	return 0;
}

SEC("syscall")
__success __retval(0)
int reserve_invalid_region(void *ctx)
{
#if defined(__BPF_FEATURE_ADDR_SPACE_CAST)
	char __arena *page;
	int ret;

	/* Try a NULL pointer. */
	ret = bpf_arena_reserve_pages(&arena, NULL, 3);
	if (ret != -EINVAL)
		return 1;

	page = arena_base(&arena);

	ret = bpf_arena_reserve_pages(&arena, page, 3);
	if (ret != -EINVAL)
		return 2;

	ret = bpf_arena_reserve_pages(&arena, page, 4096);
	if (ret != -EINVAL)
		return 3;

	ret = bpf_arena_reserve_pages(&arena, page, (1ULL << 32) - 1);
	if (ret != -EINVAL)
		return 4;
#endif
	return 0;
}

SEC("iter.s/bpf_map")
__success __log_level(2)
int iter_maps1(struct bpf_iter__bpf_map *ctx)
{
	struct bpf_map *map = ctx->map;

	if (!map)
		return 0;
	bpf_arena_alloc_pages(map, NULL, map->max_entries, 0, 0);
	return 0;
}

SEC("iter.s/bpf_map")
__failure __msg("expected pointer to STRUCT bpf_map")
int iter_maps2(struct bpf_iter__bpf_map *ctx)
{
	struct seq_file *seq = ctx->meta->seq;

	bpf_arena_alloc_pages((void *)seq, NULL, 1, 0, 0);
	return 0;
}

SEC("iter.s/bpf_map")
__failure __msg("untrusted_ptr_bpf_map")
int iter_maps3(struct bpf_iter__bpf_map *ctx)
{
	struct bpf_map *map = ctx->map;

	if (!map)
		return 0;
	bpf_arena_alloc_pages(map->inner_map_meta, NULL, map->max_entries, 0, 0);
	return 0;
}

private(ARENA_TESTS) struct bpf_spin_lock arena_bpf_test_lock;

/* Use the arena kfunc API while under a BPF lock. */
SEC("syscall")
__success __retval(0)
int arena_kfuncs_under_bpf_lock(void *ctx)
{
#if defined(__BPF_FEATURE_ADDR_SPACE_CAST)
	char __arena *page;
	int ret;

	bpf_spin_lock(&arena_bpf_test_lock);

	/* Get a separate region of the arena. */
	page = arena_base(&arena);
	ret = bpf_arena_reserve_pages(&arena, page, 1);
	if (ret) {
		bpf_spin_unlock(&arena_bpf_test_lock);
		return 1;
	}

	bpf_arena_free_pages(&arena, page, 1);

	page = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	if (!page) {
		bpf_spin_unlock(&arena_bpf_test_lock);
		return 2;
	}

	bpf_arena_free_pages(&arena, page, 1);

	bpf_spin_unlock(&arena_bpf_test_lock);
#endif

	return 0;
}

#if defined(__BPF_FEATURE_ADDR_SPACE_CAST)

/*
 * Test that scalar += PTR_TO_ARENA correctly upgrades the
 * destination register to a PTR_TO_ARENA.
 */
SEC("syscall")
__success __retval(0)
int scalar_add_arena_ptr(void *ctx)
{
	int __arena *scalar, *arena_ptr;

	volatile char __arena *base = arena_base(&arena);

	asm volatile (
		"%[arena_ptr] = 8192;"
		"%[arena_ptr] = addr_space_cast(%[arena_ptr], 0x0, 0x1);"
		"%[scalar] = 12;"
		"%[scalar] += %[arena_ptr];"
		: [scalar] "=r"(scalar),
		  [arena_ptr] "=&r"(arena_ptr)
		: "r"(base)
		:
	);
	return 0;
}

/*
 * Tests that PTR_TO_ARENA + PTR_TO_ARENA is allowed.
 */
SEC("syscall")
__success __retval(0)
int arena_ptr_add_arena_ptr(void *ctx)
{
	int __arena *arena_ptr2, *arena_ptr1;

	/* Needed for the verifier to link the arena to the subprog. */
	volatile char __arena *base = arena_base(&arena);

	asm volatile (
		"%[arena_ptr1] = 8192;"
		"%[arena_ptr1] = addr_space_cast(%[arena_ptr1], 0x0, 0x1);"
		"%[arena_ptr2] = 4096;"
		"%[arena_ptr2] = addr_space_cast(%[arena_ptr2], 0x0, 0x1);"
		"%[arena_ptr2] += %[arena_ptr1];"
		: [arena_ptr2] "=r"(arena_ptr2),
		  [arena_ptr1] "=&r"(arena_ptr1)
		: "r"(base)
		:
	);
	return 0;
}

SEC("syscall")
__failure __msg("same insn cannot be used with and without arena pointer")
int mixed_arena_scalar_alu64_scalar_first(void *ctx)
{
	volatile register __u64 reg asm("r3");
	__u32 pick_arena = bpf_get_prandom_u32();

	reg = 1ULL << 32;

	if (pick_arena) {
		asm volatile (
			"r9 = %[arena] ll;"
			"%[reg] = 0;"
			"%[reg] = addr_space_cast(%[reg], 0x0, 0x1);"
			: [reg] "=r"(reg)
			: __imm_addr(arena)
			: "r9"
		);
	}

	reg += 1;

	return 0;
}

SEC("syscall")
__failure __msg("same insn cannot be used with and without arena pointer")
int mixed_arena_scalar_alu64_arena_first(void *ctx)
{
	volatile register __u64 reg asm("r3");
	__u32 pick_scalar = bpf_get_prandom_u32();

	asm volatile (
		"r9 = %[arena] ll;"
		"%[reg] = 0;"
		"%[reg] = addr_space_cast(%[reg], 0x0, 0x1);"
		: [reg] "=r"(reg)
		: __imm_addr(arena)
		: "r9"
	);

	if (pick_scalar)
		reg = 1ULL << 32;

	reg += 1;

	return 0;
}

SEC("syscall")
__description("arena: a number is not an address in arena")
__failure __msg("R6 invalid mem access 'scalar'")
__naked void access_through_number(void)
{
	asm volatile ("					\
	r1 = %[arena] ll;				\
	r6 = 0x100000000000 ll;				\
	r0 = *(u64 *)(r6 + 0);				\
	exit;						\
"	:
	: __imm_addr(arena)
	: __clobber_all);
}

SEC("syscall")
__success __retval(0)
int scalar_xor_arena_ptr(void *ctx)
{
	int __arena *scalar, *arena_ptr;

	volatile char __arena *base = arena_base(&arena);

	asm volatile (
		"%[arena_ptr] = 8192;"
		"%[arena_ptr] = addr_space_cast(%[arena_ptr], 0x0, 0x1);"
		"%[scalar] = 12;"
		"%[scalar] ^= %[arena_ptr];"
		: [scalar] "=r"(scalar),
		  [arena_ptr] "=&r"(arena_ptr)
		: "r"(base)
		:
	);
	return 0;
}

/*
 * Tests that PTR_TO_ARENA and non-arena pointers can be added.
 */
SEC("syscall")
__success __retval(0)
int arena_ptr_add_to_non_arena_ptr(void *ctx)
{
	register int __arena *arena_ptr asm("r3");
	register void *dst asm("r4");

	volatile char __arena *base = arena_base(&arena);

	asm volatile (
		"%[arena_ptr] = 8192;"
		"%[arena_ptr] = addr_space_cast(%[arena_ptr], 0x0, 0x1);"
		"%[dst] = %[ctx];"
		"%[dst] += %[arena_ptr];"
		: [arena_ptr] "=&r"(arena_ptr),
		  [dst] "=&r"(dst)
		: [ctx] "r"(ctx), "r"(base)
		:
	);

	(void)ctx;

	return 0;
}

SEC("syscall")
__success __retval(0)
int non_arena_ptr_add_to_arena_ptr(void *ctx)
{
	register int __arena *arena_ptr asm("r3");
	register void *src asm("r4");

	volatile char __arena *base = arena_base(&arena);

	asm volatile (
		"%[arena_ptr] = 8192;"
		"%[arena_ptr] = addr_space_cast(%[arena_ptr], 0x0, 0x1);"
		"%[src] = %[ctx];"
		"%[arena_ptr] += %[src];"
		: [arena_ptr] "=&r"(arena_ptr),
		  [src] "=&r"(src)
		: [ctx] "r"(ctx), "r"(base)
		:
	);

	(void)ctx;

	return 0;
}

SEC("socket")
__description("arena and stack atomic at the same instruction")
__failure __msg("same insn cannot be used with different pointers")
__arch_x86_64
__load_if_JITed()
__naked void mixed_arena_stack_atomic(void)
{
	asm volatile ("					\
	r1 = %[arena] ll;				\
	r6 = r10;					\
	r6 += -8;					\
	r9 = 0;						\
	*(u64 *)(r6 + 0) = r9;				\
	r7 = 8192;					\
	r7 = addr_space_cast(r7, 0, 1);			\
	call %[bpf_get_prandom_u32];			\
	if w0 != 0 goto 1f;				\
	r8 = r6;					\
	goto 2f;					\
1:	r8 = r7;					\
2:	r9 = 1;						\
	lock *(u64 *)(r8 + 0) += r9;			\
	r0 = 0;						\
	exit;						\
"	:
	: __imm_addr(arena),
	  __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

#endif /* defined(__BPF_FEATURE_ADDR_SPACE_CAST) */

static __noinline
u32 __arena *check_arena_arg_nonglobal(u32 __arena *arg)
{
	volatile u32 val = *arg;

	*arg = val + 1;

	return arg;
}

__weak
u32 __arena *check_arena_arg_global(u32 __arena *arg)
{
	volatile u32 val = *arg;

	*arg = val + 1;

	return arg;
}

__weak
u32 volatile __arena *check_arena_arg_quals1(u32 volatile __arena *arg1, u32 __arena volatile *arg2)
{
	*arg1 = *arg1 + 1;
	*arg2 = *arg1 + 1;

	return arg2;
}

__weak
u32 __arena volatile *check_arena_arg_quals2(u32 volatile __arena *arg1, u32 __arena volatile *arg2)
{
	*arg1 = *arg1 + 1;
	*arg2 = *arg2 + 1;

	return arg2;
}

SEC("syscall")
__success __retval(0)
int check_arena_arg_ret(void *ctx)
{
	u32 __arena *page = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	u32 __arena *arg = page;
	u32 __arena volatile *arg1;
	u32 __arena volatile *ret1;
	u32 volatile __arena *arg2;
	u32 volatile __arena *ret2;

	if (!arg)
		return 1;

	/* Make sure we use {arg, ret}{1, 2}. */

	arg = check_arena_arg_nonglobal(page);
	arg = check_arena_arg_global(arg);

	arg1 = arg2 = page;
	ret1 = check_arena_arg_quals1(arg1, arg2);
	ret2 = check_arena_arg_quals2(arg1, arg2);

	if (!(*ret1 ||*ret2))
		return -EINVAL;

	return 0;
}

#if defined(__clang_major__) && __clang_major__ >= 23

struct arena_word_pair {
	u32 __arena *first;
	u32 __arena *second;
};

__weak struct arena_word_pair arena_word_pair(u32 __arena *page)
{
	struct arena_word_pair pair;

	pair.first = page;
	pair.second = page + 1;

	return pair;
}

SEC("syscall")
__load_if_JITed()
__success __retval(0)
int check_arena_struct_ret(void *ctx)
{
	u32 __arena *page = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
	u32 volatile __arena *first, *second;
	struct arena_word_pair pair;

	if (!page)
		return 1;

	pair = arena_word_pair(page);
	if (!pair.first || !pair.second)
		return 2;

	/* Both halves of the pair must still be usable as arena pointers. */
	first = pair.first;
	second = pair.second;
	*first = 1;
	*second = 2;
	if (*first != 1)
		return 3;
	if (*second != 2)
		return 4;

	return 0;
}

#endif

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