7d4f89b7cb84167f9ca94b154ae32b3df77cf9f4
[muen/linux.git] / kernel / bpf / bpf_lru_list.h
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