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