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 
16 enum 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 
24 struct bpf_lru_node {
25 	struct list_head list;
26 	u16 cpu;
27 	u8 type;
28 	u8 ref;
29 };
30 
31 struct 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 
40 struct 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 
46 struct bpf_common_lru {
47 	struct bpf_lru_list lru_list;
48 	struct bpf_lru_locallist __percpu *local_list;
49 };
50 
51 typedef bool (*del_from_htab_func)(void *arg, struct bpf_lru_node *node);
52 
53 struct 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 
bpf_lru_node_set_ref(struct bpf_lru_node * node)65 static inline void bpf_lru_node_set_ref(struct bpf_lru_node *node)
66 {
67 	/* ref is an approximation on access frequency.  It does not
68 	 * have to be very accurate.  Hence, no protection is used.
69 	 */
70 	if (!node->ref)
71 		node->ref = 1;
72 }
73 
74 int bpf_lru_init(struct bpf_lru *lru, bool percpu, u32 hash_offset,
75 		 del_from_htab_func del_from_htab, void *delete_arg);
76 void bpf_lru_populate(struct bpf_lru *lru, void *buf, u32 node_offset,
77 		      u32 elem_size, u32 nr_elems);
78 void bpf_lru_destroy(struct bpf_lru *lru);
79 struct bpf_lru_node *bpf_lru_pop_free(struct bpf_lru *lru, u32 hash);
80 void bpf_lru_push_free(struct bpf_lru *lru, struct bpf_lru_node *node);
81 void bpf_lru_promote(struct bpf_lru *lru, struct bpf_lru_node *node);
82 
83 #endif
84