kernel/bpf/bpf_lru_list.h

   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/spinlock_types.h>
  10
  11 #define NR_BPF_LRU_LIST_T       (3)
  12 #define NR_BPF_LRU_LIST_COUNT   (2)
  13 #define NR_BPF_LRU_LOCAL_LIST_T (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         struct list_head list;
  26         u16 cpu;
  27         u8 type;
  28         u8 ref;
  29 };
  30
  31 struct bpf_lru_list {
  32         struct list_head lists[NR_BPF_LRU_LIST_T];
  33         unsigned int counts[NR_BPF_LRU_LIST_COUNT];
  34         /* The next inactive list rotation starts from here */
  35         struct list_head *next_inactive_rotation;
  36
  37         raw_spinlock_t lock ____cacheline_aligned_in_smp;
  38 };
  39
  40 struct bpf_lru_locallist {
  41         struct list_head lists[NR_BPF_LRU_LOCAL_LIST_T];
  42         u16 next_steal;
  43         raw_spinlock_t lock;
  44 };
  45
  46 struct bpf_common_lru {
  47         struct bpf_lru_list lru_list;
  48         struct bpf_lru_locallist __percpu *local_list;
  49 };
  50
  51 typedef bool (*del_from_htab_func)(void *arg, struct bpf_lru_node *node);
  52
  53 struct bpf_lru {
  54         union {
  55                 struct bpf_common_lru common_lru;
  56                 struct bpf_lru_list __percpu *percpu_lru;
  57         };
  58         del_from_htab_func del_from_htab;
  59         void *del_arg;
  60         unsigned int hash_offset;
  61         unsigned int nr_scans;
  62         bool percpu;
  63 };
  64
  65 static inline void bpf_lru_node_set_ref(struct bpf_lru_node *node)
  66 {
  67         /* ref is an approximation on access frequency.  It does not
  68          * have to be very accurate.  Hence, no protection is used.
  69          */
  70         if (!node->ref)
  71                 node->ref = 1;
  72 }
  73
  74 int bpf_lru_init(struct bpf_lru *lru, bool percpu, u32 hash_offset,
  75                  del_from_htab_func del_from_htab, void *delete_arg);
  76 void bpf_lru_populate(struct bpf_lru *lru, void *buf, u32 node_offset,
  77                       u32 elem_size, u32 nr_elems);
  78 void bpf_lru_destroy(struct bpf_lru *lru);
  79 struct bpf_lru_node *bpf_lru_pop_free(struct bpf_lru *lru, u32 hash);
  80 void bpf_lru_push_free(struct bpf_lru *lru, struct bpf_lru_node *node);
  81 void bpf_lru_promote(struct bpf_lru *lru, struct bpf_lru_node *node);
  82
  83 #endif