Commit | Line | Data |
---|---|---|
3a08c2fd MKL |
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 | struct bpf_common_lru common_lru; | |
57 | del_from_htab_func del_from_htab; | |
58 | void *del_arg; | |
59 | unsigned int hash_offset; | |
60 | unsigned int nr_scans; | |
61 | }; | |
62 | ||
63 | static inline void bpf_lru_node_set_ref(struct bpf_lru_node *node) | |
64 | { | |
65 | /* ref is an approximation on access frequency. It does not | |
66 | * have to be very accurate. Hence, no protection is used. | |
67 | */ | |
68 | node->ref = 1; | |
69 | } | |
70 | ||
71 | int bpf_lru_init(struct bpf_lru *lru, u32 hash_offset, | |
72 | del_from_htab_func del_from_htab, void *delete_arg); | |
73 | void bpf_lru_populate(struct bpf_lru *lru, void *buf, u32 node_offset, | |
74 | u32 elem_size, u32 nr_elems); | |
75 | void bpf_lru_destroy(struct bpf_lru *lru); | |
76 | struct bpf_lru_node *bpf_lru_pop_free(struct bpf_lru *lru, u32 hash); | |
77 | void bpf_lru_push_free(struct bpf_lru *lru, struct bpf_lru_node *node); | |
78 | void bpf_lru_promote(struct bpf_lru *lru, struct bpf_lru_node *node); | |
79 | ||
80 | #endif |