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/list.h>
8 #include <linux/spinlock_types.h>
9
10 #define NR_BPF_LRU_LIST_T (3)
11 #define NR_BPF_LRU_LIST_COUNT (2)
12 #define NR_BPF_LRU_LOCAL_LIST_T (2)
13 #define BPF_LOCAL_LIST_T_OFFSET NR_BPF_LRU_LIST_T
14
15 enum bpf_lru_list_type {
16 BPF_LRU_LIST_T_ACTIVE,
17 BPF_LRU_LIST_T_INACTIVE,
18 BPF_LRU_LIST_T_FREE,
19 BPF_LRU_LOCAL_LIST_T_FREE,
20 BPF_LRU_LOCAL_LIST_T_PENDING,
21 };
22
23 struct bpf_lru_node {
24 struct list_head list;
25 u16 cpu;
26 u8 type;
27 u8 ref;
28 };
29
30 struct bpf_lru_list {
31 struct list_head lists[NR_BPF_LRU_LIST_T];
32 unsigned int counts[NR_BPF_LRU_LIST_COUNT];
33 /* The next inacitve list rotation starts from here */
34 struct list_head *next_inactive_rotation;
35
36 raw_spinlock_t lock ____cacheline_aligned_in_smp;
37 };
38
39 struct bpf_lru_locallist {
40 struct list_head lists[NR_BPF_LRU_LOCAL_LIST_T];
41 u16 next_steal;
42 raw_spinlock_t lock;
43 };
44
45 struct bpf_common_lru {
46 struct bpf_lru_list lru_list;
47 struct bpf_lru_locallist __percpu *local_list;
48 };
49
50 typedef bool (*del_from_htab_func)(void *arg, struct bpf_lru_node *node);
51
52 struct bpf_lru {
53 union {
54 struct bpf_common_lru common_lru;
55 struct bpf_lru_list __percpu *percpu_lru;
56 };
57 del_from_htab_func del_from_htab;
58 void *del_arg;
59 unsigned int hash_offset;
60 unsigned int nr_scans;
61 bool percpu;
62 };
63
bpf_lru_node_set_ref(struct bpf_lru_node * node)64 static inline void bpf_lru_node_set_ref(struct bpf_lru_node *node)
65 {
66 /* ref is an approximation on access frequency. It does not
67 * have to be very accurate. Hence, no protection is used.
68 */
69 if (!node->ref)
70 node->ref = 1;
71 }
72
73 int bpf_lru_init(struct bpf_lru *lru, bool percpu, u32 hash_offset,
74 del_from_htab_func del_from_htab, void *delete_arg);
75 void bpf_lru_populate(struct bpf_lru *lru, void *buf, u32 node_offset,
76 u32 elem_size, u32 nr_elems);
77 void bpf_lru_destroy(struct bpf_lru *lru);
78 struct bpf_lru_node *bpf_lru_pop_free(struct bpf_lru *lru, u32 hash);
79 void bpf_lru_push_free(struct bpf_lru *lru, struct bpf_lru_node *node);
80 void bpf_lru_promote(struct bpf_lru *lru, struct bpf_lru_node *node);
81
82 #endif
83
