Branch data     Line data    Source code

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