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 #include <asm/rqspinlock.h> 19 20 #define BPF_LOCAL_STORAGE_CACHE_SIZE 16 21 22 struct bpf_local_storage_map_bucket { 23 struct hlist_head list; 24 rqspinlock_t lock; 25 }; 26 27 /* Thp map is not the primary owner of a bpf_local_storage_elem. 28 * Instead, the container object (eg. sk->sk_bpf_storage) is. 29 * 30 * The map (bpf_local_storage_map) is for two purposes 31 * 1. Define the size of the "local storage". It is 32 * the map's value_size. 33 * 34 * 2. Maintain a list to keep track of all elems such 35 * that they can be cleaned up during the map destruction. 36 * 37 * When a bpf local storage is being looked up for a 38 * particular object, the "bpf_map" pointer is actually used 39 * as the "key" to search in the list of elem in 40 * the respective bpf_local_storage owned by the object. 41 * 42 * e.g. sk->sk_bpf_storage is the mini-map with the "bpf_map" pointer 43 * as the searching key. 44 */ 45 struct bpf_local_storage_map { 46 struct bpf_map map; 47 /* Lookup elem does not require accessing the map. 48 * 49 * Updating/Deleting requires a bucket lock to 50 * link/unlink the elem from the map. Having 51 * multiple buckets to improve contention. 52 */ 53 struct bpf_local_storage_map_bucket *buckets; 54 u32 bucket_log; 55 u16 elem_size; 56 u16 cache_idx; 57 }; 58 59 struct bpf_local_storage_data { 60 /* smap is used as the searching key when looking up 61 * from the object's bpf_local_storage. 62 * 63 * Put it in the same cacheline as the data to minimize 64 * the number of cachelines accessed during the cache hit case. 65 */ 66 struct bpf_local_storage_map __rcu *smap; 67 u8 data[] __aligned(8); 68 }; 69 70 #define SELEM_MAP_UNLINKED (1 << 0) 71 #define SELEM_STORAGE_UNLINKED (1 << 1) 72 #define SELEM_UNLINKED (SELEM_MAP_UNLINKED | SELEM_STORAGE_UNLINKED) 73 #define SELEM_TOFREE (1 << 2) 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 atomic_t state; 88 /* 4 bytes hole */ 89 /* The data is stored in another cacheline to minimize 90 * the number of cachelines access during a cache hit. 91 */ 92 struct bpf_local_storage_data sdata ____cacheline_aligned; 93 }; 94 95 struct bpf_local_storage { 96 struct bpf_local_storage_data __rcu *cache[BPF_LOCAL_STORAGE_CACHE_SIZE]; 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 rqspinlock_t lock; /* Protect adding/removing from the "list" */ 103 u64 mem_charge; /* Copy of mem charged to owner. Protected by "lock" */ 104 refcount_t owner_refcnt;/* Used to pin owner when map_free is uncharging */ 105 }; 106 107 /* 108 * Drop a reference got by refcount_inc_not_zero(&local_storage->owner_refcnt). 109 * bpf_local_storage_destroy() may have dropped the owner's reference meanwhile 110 * and wait for the count to reach zero, so this one can be the last. 111 */ 112 static inline void 113 bpf_local_storage_unpin_owner(struct bpf_local_storage *local_storage) 114 { 115 bool last __maybe_unused; 116 117 last = refcount_dec_and_test(&local_storage->owner_refcnt); 118 } 119 120 /* U16_MAX is much more than enough for sk local storage 121 * considering a tcp_sock is ~2k. 122 */ 123 #define BPF_LOCAL_STORAGE_MAX_VALUE_SIZE \ 124 min_t(u32, \ 125 (KMALLOC_MAX_SIZE - MAX_BPF_STACK - \ 126 sizeof(struct bpf_local_storage_elem)), \ 127 (U16_MAX - sizeof(struct bpf_local_storage_elem))) 128 129 #define SELEM(_SDATA) \ 130 container_of((_SDATA), struct bpf_local_storage_elem, sdata) 131 #define SDATA(_SELEM) (&(_SELEM)->sdata) 132 133 #define BPF_LOCAL_STORAGE_CACHE_SIZE 16 134 135 struct bpf_local_storage_cache { 136 spinlock_t idx_lock; 137 u64 idx_usage_counts[BPF_LOCAL_STORAGE_CACHE_SIZE]; 138 }; 139 140 #define DEFINE_BPF_STORAGE_CACHE(name) \ 141 static struct bpf_local_storage_cache name = { \ 142 .idx_lock = __SPIN_LOCK_UNLOCKED(name.idx_lock), \ 143 } 144 145 /* Helper functions for bpf_local_storage */ 146 int bpf_local_storage_map_alloc_check(union bpf_attr *attr); 147 148 struct bpf_map * 149 bpf_local_storage_map_alloc(union bpf_attr *attr, 150 struct bpf_local_storage_cache *cache); 151 152 void __bpf_local_storage_insert_cache(struct bpf_local_storage *local_storage, 153 struct bpf_local_storage_map *smap, 154 struct bpf_local_storage_elem *selem); 155 /* If cacheit_lockit is false, this lookup function is lockless */ 156 static inline struct bpf_local_storage_data * 157 bpf_local_storage_lookup(struct bpf_local_storage *local_storage, 158 struct bpf_local_storage_map *smap, 159 bool cacheit_lockit) 160 { 161 struct bpf_local_storage_data *sdata; 162 struct bpf_local_storage_elem *selem; 163 164 /* Fast path (cache hit) */ 165 sdata = rcu_dereference_check(local_storage->cache[smap->cache_idx], 166 bpf_rcu_lock_held()); 167 if (sdata && rcu_access_pointer(sdata->smap) == smap) 168 return sdata; 169 170 /* Slow path (cache miss) */ 171 hlist_for_each_entry_rcu(selem, &local_storage->list, snode, 172 rcu_read_lock_trace_held()) 173 if (rcu_access_pointer(SDATA(selem)->smap) == smap) 174 break; 175 176 if (!selem) 177 return NULL; 178 if (cacheit_lockit) 179 __bpf_local_storage_insert_cache(local_storage, smap, selem); 180 return SDATA(selem); 181 } 182 183 u32 bpf_local_storage_destroy(struct bpf_local_storage *local_storage); 184 185 void bpf_local_storage_map_free(struct bpf_map *map, 186 struct bpf_local_storage_cache *cache); 187 188 int bpf_local_storage_map_check_btf(struct bpf_map *map, 189 const struct btf *btf, 190 const struct btf_type *key_type, 191 const struct btf_type *value_type); 192 193 void bpf_selem_link_storage_nolock(struct bpf_local_storage *local_storage, 194 struct bpf_local_storage_elem *selem); 195 196 int bpf_selem_unlink(struct bpf_local_storage_elem *selem); 197 198 int bpf_selem_link_map(struct bpf_local_storage_map *smap, 199 struct bpf_local_storage *local_storage, 200 struct bpf_local_storage_elem *selem); 201 202 struct bpf_local_storage_elem * 203 bpf_selem_alloc(struct bpf_local_storage_map *smap, void *owner, void *value, 204 bool swap_uptrs); 205 206 void bpf_selem_free(struct bpf_local_storage_elem *selem, 207 bool reuse_now); 208 209 int 210 bpf_local_storage_alloc(void *owner, 211 struct bpf_local_storage_map *smap, 212 struct bpf_local_storage_elem *first_selem); 213 214 struct bpf_local_storage_data * 215 bpf_local_storage_update(void *owner, struct bpf_local_storage_map *smap, 216 void *value, u64 map_flags, bool swap_uptrs); 217 218 u64 bpf_local_storage_map_mem_usage(const struct bpf_map *map); 219 220 #endif /* _BPF_LOCAL_STORAGE_H */ 221