1 /* SPDX-License-Identifier: GPL-2.0 */ 2 /* 3 * Copyright (c) 2019 Facebook 4 * Copyright 2020 Google LLC. 5 */ 6 7 #ifndef _BPF_LOCAL_STORAGE_H 8 #define _BPF_LOCAL_STORAGE_H 9 10 #include <linux/bpf.h> 11 #include <linux/filter.h> 12 #include <linux/rculist.h> 13 #include <linux/list.h> 14 #include <linux/hash.h> 15 #include <linux/types.h> 16 #include <linux/bpf_mem_alloc.h> 17 #include <uapi/linux/btf.h> 18 19 #define BPF_LOCAL_STORAGE_CACHE_SIZE 16 20 21 #define bpf_rcu_lock_held() \ 22 (rcu_read_lock_held() || rcu_read_lock_trace_held() || \ 23 rcu_read_lock_bh_held()) 24 struct bpf_local_storage_map_bucket { 25 struct hlist_head list; 26 raw_spinlock_t lock; 27 }; 28 29 /* Thp map is not the primary owner of a bpf_local_storage_elem. 30 * Instead, the container object (eg. sk->sk_bpf_storage) is. 31 * 32 * The map (bpf_local_storage_map) is for two purposes 33 * 1. Define the size of the "local storage". It is 34 * the map's value_size. 35 * 36 * 2. Maintain a list to keep track of all elems such 37 * that they can be cleaned up during the map destruction. 38 * 39 * When a bpf local storage is being looked up for a 40 * particular object, the "bpf_map" pointer is actually used 41 * as the "key" to search in the list of elem in 42 * the respective bpf_local_storage owned by the object. 43 * 44 * e.g. sk->sk_bpf_storage is the mini-map with the "bpf_map" pointer 45 * as the searching key. 46 */ 47 struct bpf_local_storage_map { 48 struct bpf_map map; 49 /* Lookup elem does not require accessing the map. 50 * 51 * Updating/Deleting requires a bucket lock to 52 * link/unlink the elem from the map. Having 53 * multiple buckets to improve contention. 54 */ 55 struct bpf_local_storage_map_bucket *buckets; 56 u32 bucket_log; 57 u16 elem_size; 58 u16 cache_idx; 59 struct bpf_mem_alloc selem_ma; 60 struct bpf_mem_alloc storage_ma; 61 bool bpf_ma; 62 }; 63 64 struct bpf_local_storage_data { 65 /* smap is used as the searching key when looking up 66 * from the object's bpf_local_storage. 67 * 68 * Put it in the same cacheline as the data to minimize 69 * the number of cachelines accessed during the cache hit case. 70 */ 71 struct bpf_local_storage_map __rcu *smap; 72 u8 data[] __aligned(8); 73 }; 74 75 /* Linked to bpf_local_storage and bpf_local_storage_map */ 76 struct bpf_local_storage_elem { 77 struct hlist_node map_node; /* Linked to bpf_local_storage_map */ 78 struct hlist_node snode; /* Linked to bpf_local_storage */ 79 struct bpf_local_storage __rcu *local_storage; 80 union { 81 struct rcu_head rcu; 82 struct hlist_node free_node; /* used to postpone 83 * bpf_selem_free 84 * after raw_spin_unlock 85 */ 86 }; 87 /* 8 bytes hole */ 88 /* The data is stored in another cacheline to minimize 89 * the number of cachelines access during a cache hit. 90 */ 91 struct bpf_local_storage_data sdata ____cacheline_aligned; 92 }; 93 94 struct bpf_local_storage { 95 struct bpf_local_storage_data __rcu *cache[BPF_LOCAL_STORAGE_CACHE_SIZE]; 96 struct bpf_local_storage_map __rcu *smap; 97 struct hlist_head list; /* List of bpf_local_storage_elem */ 98 void *owner; /* The object that owns the above "list" of 99 * bpf_local_storage_elem. 100 */ 101 struct rcu_head rcu; 102 raw_spinlock_t lock; /* Protect adding/removing from the "list" */ 103 }; 104 105 /* U16_MAX is much more than enough for sk local storage 106 * considering a tcp_sock is ~2k. 107 */ 108 #define BPF_LOCAL_STORAGE_MAX_VALUE_SIZE \ 109 min_t(u32, \ 110 (KMALLOC_MAX_SIZE - MAX_BPF_STACK - \ 111 sizeof(struct bpf_local_storage_elem)), \ 112 (U16_MAX - sizeof(struct bpf_local_storage_elem))) 113 114 #define SELEM(_SDATA) \ 115 container_of((_SDATA), struct bpf_local_storage_elem, sdata) 116 #define SDATA(_SELEM) (&(_SELEM)->sdata) 117 118 #define BPF_LOCAL_STORAGE_CACHE_SIZE 16 119 120 struct bpf_local_storage_cache { 121 spinlock_t idx_lock; 122 u64 idx_usage_counts[BPF_LOCAL_STORAGE_CACHE_SIZE]; 123 }; 124 125 #define DEFINE_BPF_STORAGE_CACHE(name) \ 126 static struct bpf_local_storage_cache name = { \ 127 .idx_lock = __SPIN_LOCK_UNLOCKED(name.idx_lock), \ 128 } 129 130 /* Helper functions for bpf_local_storage */ 131 int bpf_local_storage_map_alloc_check(union bpf_attr *attr); 132 133 struct bpf_map * 134 bpf_local_storage_map_alloc(union bpf_attr *attr, 135 struct bpf_local_storage_cache *cache, 136 bool bpf_ma); 137 138 void __bpf_local_storage_insert_cache(struct bpf_local_storage *local_storage, 139 struct bpf_local_storage_map *smap, 140 struct bpf_local_storage_elem *selem); 141 /* If cacheit_lockit is false, this lookup function is lockless */ 142 static inline struct bpf_local_storage_data * 143 bpf_local_storage_lookup(struct bpf_local_storage *local_storage, 144 struct bpf_local_storage_map *smap, 145 bool cacheit_lockit) 146 { 147 struct bpf_local_storage_data *sdata; 148 struct bpf_local_storage_elem *selem; 149 150 /* Fast path (cache hit) */ 151 sdata = rcu_dereference_check(local_storage->cache[smap->cache_idx], 152 bpf_rcu_lock_held()); 153 if (sdata && rcu_access_pointer(sdata->smap) == smap) 154 return sdata; 155 156 /* Slow path (cache miss) */ 157 hlist_for_each_entry_rcu(selem, &local_storage->list, snode, 158 rcu_read_lock_trace_held()) 159 if (rcu_access_pointer(SDATA(selem)->smap) == smap) 160 break; 161 162 if (!selem) 163 return NULL; 164 if (cacheit_lockit) 165 __bpf_local_storage_insert_cache(local_storage, smap, selem); 166 return SDATA(selem); 167 } 168 169 void bpf_local_storage_destroy(struct bpf_local_storage *local_storage); 170 171 void bpf_local_storage_map_free(struct bpf_map *map, 172 struct bpf_local_storage_cache *cache, 173 int __percpu *busy_counter); 174 175 int bpf_local_storage_map_check_btf(const struct bpf_map *map, 176 const struct btf *btf, 177 const struct btf_type *key_type, 178 const struct btf_type *value_type); 179 180 void bpf_selem_link_storage_nolock(struct bpf_local_storage *local_storage, 181 struct bpf_local_storage_elem *selem); 182 183 void bpf_selem_unlink(struct bpf_local_storage_elem *selem, bool reuse_now); 184 185 void bpf_selem_link_map(struct bpf_local_storage_map *smap, 186 struct bpf_local_storage_elem *selem); 187 188 struct bpf_local_storage_elem * 189 bpf_selem_alloc(struct bpf_local_storage_map *smap, void *owner, void *value, 190 bool charge_mem, bool swap_uptrs, gfp_t gfp_flags); 191 192 void bpf_selem_free(struct bpf_local_storage_elem *selem, 193 struct bpf_local_storage_map *smap, 194 bool reuse_now); 195 196 int 197 bpf_local_storage_alloc(void *owner, 198 struct bpf_local_storage_map *smap, 199 struct bpf_local_storage_elem *first_selem, 200 gfp_t gfp_flags); 201 202 struct bpf_local_storage_data * 203 bpf_local_storage_update(void *owner, struct bpf_local_storage_map *smap, 204 void *value, u64 map_flags, bool swap_uptrs, gfp_t gfp_flags); 205 206 u64 bpf_local_storage_map_mem_usage(const struct bpf_map *map); 207 208 #endif /* _BPF_LOCAL_STORAGE_H */ 209