1/* SPDX-License-Identifier: GPL-2.0-only */
2/* Copyright (c) 2016 Facebook
3 */
4#ifndef __BPF_LRU_LIST_H_
5#define __BPF_LRU_LIST_H_
6
7#include <linux/cache.h>
8#include <linux/list.h>
9#include <linux/spinlock_types.h>
10
11#define NR_BPF_LRU_LIST_T	(3)
12#define NR_BPF_LRU_LIST_COUNT	(2)
13#define NR_BPF_LRU_LOCAL_LIST_T (2)
14#define BPF_LOCAL_LIST_T_OFFSET NR_BPF_LRU_LIST_T
15
16enum bpf_lru_list_type {
17	BPF_LRU_LIST_T_ACTIVE,
18	BPF_LRU_LIST_T_INACTIVE,
19	BPF_LRU_LIST_T_FREE,
20	BPF_LRU_LOCAL_LIST_T_FREE,
21	BPF_LRU_LOCAL_LIST_T_PENDING,
22};
23
24struct bpf_lru_node {
25	struct list_head list;
26	u16 cpu;
27	u8 type;
28	u8 ref;
29};
30
31struct bpf_lru_list {
32	struct list_head lists[NR_BPF_LRU_LIST_T];
33	unsigned int counts[NR_BPF_LRU_LIST_COUNT];
34	/* The next inactive list rotation starts from here */
35	struct list_head *next_inactive_rotation;
36
37	raw_spinlock_t lock ____cacheline_aligned_in_smp;
38};
39
40struct bpf_lru_locallist {
41	struct list_head lists[NR_BPF_LRU_LOCAL_LIST_T];
42	u16 next_steal;
43	raw_spinlock_t lock;
44};
45
46struct bpf_common_lru {
47	struct bpf_lru_list lru_list;
48	struct bpf_lru_locallist __percpu *local_list;
49};
50
51typedef bool (*del_from_htab_func)(void *arg, struct bpf_lru_node *node);
52
53struct bpf_lru {
54	union {
55		struct bpf_common_lru common_lru;
56		struct bpf_lru_list __percpu *percpu_lru;
57	};
58	del_from_htab_func del_from_htab;
59	void *del_arg;
60	unsigned int hash_offset;
61	unsigned int nr_scans;
62	bool percpu;
63};
64
65static inline void bpf_lru_node_set_ref(struct bpf_lru_node *node)
66{
67	if (!READ_ONCE(node->ref))
68		WRITE_ONCE(node->ref, 1);
69}
70
71int bpf_lru_init(struct bpf_lru *lru, bool percpu, u32 hash_offset,
72		 del_from_htab_func del_from_htab, void *delete_arg);
73void bpf_lru_populate(struct bpf_lru *lru, void *buf, u32 node_offset,
74		      u32 elem_size, u32 nr_elems);
75void bpf_lru_destroy(struct bpf_lru *lru);
76struct bpf_lru_node *bpf_lru_pop_free(struct bpf_lru *lru, u32 hash);
77void bpf_lru_push_free(struct bpf_lru *lru, struct bpf_lru_node *node);
78
79#endif
80