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()) 24struct 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 */ 47struct 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 64struct 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 */ 76struct 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 struct rcu_head rcu; 81 /* 8 bytes hole */ 82 /* The data is stored in another cacheline to minimize 83 * the number of cachelines access during a cache hit. 84 */ 85 struct bpf_local_storage_data sdata ____cacheline_aligned; 86}; 87 88struct bpf_local_storage { 89 struct bpf_local_storage_data __rcu *cache[BPF_LOCAL_STORAGE_CACHE_SIZE]; 90 struct bpf_local_storage_map __rcu *smap; 91 struct hlist_head list; /* List of bpf_local_storage_elem */ 92 void *owner; /* The object that owns the above "list" of 93 * bpf_local_storage_elem. 94 */ 95 struct rcu_head rcu; 96 raw_spinlock_t lock; /* Protect adding/removing from the "list" */ 97}; 98 99/* U16_MAX is much more than enough for sk local storage 100 * considering a tcp_sock is ~2k. 101 */ 102#define BPF_LOCAL_STORAGE_MAX_VALUE_SIZE \ 103 min_t(u32, \ 104 (KMALLOC_MAX_SIZE - MAX_BPF_STACK - \ 105 sizeof(struct bpf_local_storage_elem)), \ 106 (U16_MAX - sizeof(struct bpf_local_storage_elem))) 107 108#define SELEM(_SDATA) \ 109 container_of((_SDATA), struct bpf_local_storage_elem, sdata) 110#define SDATA(_SELEM) (&(_SELEM)->sdata) 111 112#define BPF_LOCAL_STORAGE_CACHE_SIZE 16 113 114struct bpf_local_storage_cache { 115 spinlock_t idx_lock; 116 u64 idx_usage_counts[BPF_LOCAL_STORAGE_CACHE_SIZE]; 117}; 118 119#define DEFINE_BPF_STORAGE_CACHE(name) \ 120static struct bpf_local_storage_cache name = { \ 121 .idx_lock = __SPIN_LOCK_UNLOCKED(name.idx_lock), \ 122} 123 124/* Helper functions for bpf_local_storage */ 125int bpf_local_storage_map_alloc_check(union bpf_attr *attr); 126 127struct bpf_map * 128bpf_local_storage_map_alloc(union bpf_attr *attr, 129 struct bpf_local_storage_cache *cache, 130 bool bpf_ma); 131 132void __bpf_local_storage_insert_cache(struct bpf_local_storage *local_storage, 133 struct bpf_local_storage_map *smap, 134 struct bpf_local_storage_elem *selem); 135/* If cacheit_lockit is false, this lookup function is lockless */ 136static inline struct bpf_local_storage_data * 137bpf_local_storage_lookup(struct bpf_local_storage *local_storage, 138 struct bpf_local_storage_map *smap, 139 bool cacheit_lockit) 140{ 141 struct bpf_local_storage_data *sdata; 142 struct bpf_local_storage_elem *selem; 143 144 /* Fast path (cache hit) */ 145 sdata = rcu_dereference_check(local_storage->cache[smap->cache_idx], 146 bpf_rcu_lock_held()); 147 if (sdata && rcu_access_pointer(sdata->smap) == smap) 148 return sdata; 149 150 /* Slow path (cache miss) */ 151 hlist_for_each_entry_rcu(selem, &local_storage->list, snode, 152 rcu_read_lock_trace_held()) 153 if (rcu_access_pointer(SDATA(selem)->smap) == smap) 154 break; 155 156 if (!selem) 157 return NULL; 158 if (cacheit_lockit) 159 __bpf_local_storage_insert_cache(local_storage, smap, selem); 160 return SDATA(selem); 161} 162 163void bpf_local_storage_destroy(struct bpf_local_storage *local_storage); 164 165void bpf_local_storage_map_free(struct bpf_map *map, 166 struct bpf_local_storage_cache *cache, 167 int __percpu *busy_counter); 168 169int bpf_local_storage_map_check_btf(const struct bpf_map *map, 170 const struct btf *btf, 171 const struct btf_type *key_type, 172 const struct btf_type *value_type); 173 174void bpf_selem_link_storage_nolock(struct bpf_local_storage *local_storage, 175 struct bpf_local_storage_elem *selem); 176 177void bpf_selem_unlink(struct bpf_local_storage_elem *selem, bool reuse_now); 178 179void bpf_selem_link_map(struct bpf_local_storage_map *smap, 180 struct bpf_local_storage_elem *selem); 181 182struct bpf_local_storage_elem * 183bpf_selem_alloc(struct bpf_local_storage_map *smap, void *owner, void *value, 184 bool charge_mem, gfp_t gfp_flags); 185 186void bpf_selem_free(struct bpf_local_storage_elem *selem, 187 struct bpf_local_storage_map *smap, 188 bool reuse_now); 189 190int 191bpf_local_storage_alloc(void *owner, 192 struct bpf_local_storage_map *smap, 193 struct bpf_local_storage_elem *first_selem, 194 gfp_t gfp_flags); 195 196struct bpf_local_storage_data * 197bpf_local_storage_update(void *owner, struct bpf_local_storage_map *smap, 198 void *value, u64 map_flags, gfp_t gfp_flags); 199 200u64 bpf_local_storage_map_mem_usage(const struct bpf_map *map); 201 202#endif /* _BPF_LOCAL_STORAGE_H */ 203