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         node->ref = 1;
  73 }
  74
  75 int bpf_lru_init(struct bpf_lru *lru, bool percpu, u32 hash_offset,
  76                  del_from_htab_func del_from_htab, void *delete_arg);
  77 void bpf_lru_populate(struct bpf_lru *lru, void *buf, u32 node_offset,
  78                       u32 elem_size, u32 nr_elems);
  79 void bpf_lru_destroy(struct bpf_lru *lru);
  80 struct bpf_lru_node *bpf_lru_pop_free(struct bpf_lru *lru, u32 hash);
  81 void bpf_lru_push_free(struct bpf_lru *lru, struct bpf_lru_node *node);
  82 void bpf_lru_promote(struct bpf_lru *lru, struct bpf_lru_node *node);
  83
  84 #endif