kernel/bpf/bpf_lru_list.h

0001 /* SPDX-License-Identifier: GPL-2.0-only */
0002 /* Copyright (c) 2016 Facebook
0003  */
0004 #ifndef __BPF_LRU_LIST_H_
0005 #define __BPF_LRU_LIST_H_
0006
0007 #include <linux/cache.h>
0008 #include <linux/list.h>
0009 #include <linux/spinlock_types.h>
0010
0011 #define NR_BPF_LRU_LIST_T   (3)
0012 #define NR_BPF_LRU_LIST_COUNT   (2)
0013 #define NR_BPF_LRU_LOCAL_LIST_T (2)
0014 #define BPF_LOCAL_LIST_T_OFFSET NR_BPF_LRU_LIST_T
0015
0016 enum bpf_lru_list_type {
0017     BPF_LRU_LIST_T_ACTIVE,
0018     BPF_LRU_LIST_T_INACTIVE,
0019     BPF_LRU_LIST_T_FREE,
0020     BPF_LRU_LOCAL_LIST_T_FREE,
0021     BPF_LRU_LOCAL_LIST_T_PENDING,
0022 };
0023
0024 struct bpf_lru_node {
0025     struct list_head list;
0026     u16 cpu;
0027     u8 type;
0028     u8 ref;
0029 };
0030
0031 struct bpf_lru_list {
0032     struct list_head lists[NR_BPF_LRU_LIST_T];
0033     unsigned int counts[NR_BPF_LRU_LIST_COUNT];
0034     /* The next inactive list rotation starts from here */
0035     struct list_head *next_inactive_rotation;
0036
0037     raw_spinlock_t lock ____cacheline_aligned_in_smp;
0038 };
0039
0040 struct bpf_lru_locallist {
0041     struct list_head lists[NR_BPF_LRU_LOCAL_LIST_T];
0042     u16 next_steal;
0043     raw_spinlock_t lock;
0044 };
0045
0046 struct bpf_common_lru {
0047     struct bpf_lru_list lru_list;
0048     struct bpf_lru_locallist __percpu *local_list;
0049 };
0050
0051 typedef bool (*del_from_htab_func)(void *arg, struct bpf_lru_node *node);
0052
0053 struct bpf_lru {
0054     union {
0055         struct bpf_common_lru common_lru;
0056         struct bpf_lru_list __percpu *percpu_lru;
0057     };
0058     del_from_htab_func del_from_htab;
0059     void *del_arg;
0060     unsigned int hash_offset;
0061     unsigned int nr_scans;
0062     bool percpu;
0063 };
0064
0065 static inline void bpf_lru_node_set_ref(struct bpf_lru_node *node)
0066 {
0067     /* ref is an approximation on access frequency.  It does not
0068      * have to be very accurate.  Hence, no protection is used.
0069      */
0070     if (!node->ref)
0071         node->ref = 1;
0072 }
0073
0074 int bpf_lru_init(struct bpf_lru *lru, bool percpu, u32 hash_offset,
0075          del_from_htab_func del_from_htab, void *delete_arg);
0076 void bpf_lru_populate(struct bpf_lru *lru, void *buf, u32 node_offset,
0077               u32 elem_size, u32 nr_elems);
0078 void bpf_lru_destroy(struct bpf_lru *lru);
0079 struct bpf_lru_node *bpf_lru_pop_free(struct bpf_lru *lru, u32 hash);
0080 void bpf_lru_push_free(struct bpf_lru *lru, struct bpf_lru_node *node);
0081 void bpf_lru_promote(struct bpf_lru *lru, struct bpf_lru_node *node);
0082
0083 #endif