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 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