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/llist.h> 10 #include <asm/rqspinlock.h> 11 12 #define NR_BPF_LRU_LIST_T (3) 13 #define NR_BPF_LRU_LIST_COUNT (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 /* 26 * A node is in at most one list at a time. The free path on the 27 * per-CPU locallist uses an llist, so share storage via a union. 28 */ 29 union { 30 struct list_head list; 31 struct llist_node llist; 32 }; 33 u16 cpu; 34 u8 type; 35 u8 ref; 36 /* 37 * Marks nodes whose *_push_free() lock acquire failed; reclaimed 38 * by flush/shrink which honor the flag instead of del_from_htab(). 39 */ 40 u8 pending_free; 41 }; 42 43 struct bpf_lru_list { 44 struct list_head lists[NR_BPF_LRU_LIST_T]; 45 unsigned int counts[NR_BPF_LRU_LIST_COUNT]; 46 /* The next inactive list rotation starts from here */ 47 struct list_head *next_inactive_rotation; 48 49 rqspinlock_t lock ____cacheline_aligned_in_smp; 50 }; 51 52 struct bpf_lru_locallist { 53 struct list_head pending_list; 54 struct llist_head free_llist; 55 u16 next_steal; 56 rqspinlock_t lock; 57 }; 58 59 struct bpf_common_lru { 60 struct bpf_lru_list lru_list; 61 struct bpf_lru_locallist __percpu *local_list; 62 }; 63 64 typedef bool (*del_from_htab_func)(void *arg, struct bpf_lru_node *node); 65 66 struct bpf_lru { 67 union { 68 struct bpf_common_lru common_lru; 69 struct bpf_lru_list __percpu *percpu_lru; 70 }; 71 del_from_htab_func del_from_htab; 72 void *del_arg; 73 unsigned int hash_offset; 74 unsigned int target_free; 75 unsigned int nr_scans; 76 bool percpu; 77 }; 78 79 static inline void bpf_lru_node_set_ref(struct bpf_lru_node *node) 80 { 81 if (!READ_ONCE(node->ref)) 82 WRITE_ONCE(node->ref, 1); 83 } 84 85 int bpf_lru_init(struct bpf_lru *lru, bool percpu, u32 hash_offset, 86 del_from_htab_func del_from_htab, void *delete_arg); 87 void bpf_lru_populate(struct bpf_lru *lru, void *buf, u32 node_offset, 88 u32 elem_size, u32 nr_elems); 89 void bpf_lru_destroy(struct bpf_lru *lru); 90 struct bpf_lru_node *bpf_lru_pop_free(struct bpf_lru *lru, u32 hash); 91 void bpf_lru_push_free(struct bpf_lru *lru, struct bpf_lru_node *node); 92 93 #endif 94