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 <uapi/linux/btf.h>
17 
18 #define BPF_LOCAL_STORAGE_CACHE_SIZE	16
19 
20 #define bpf_rcu_lock_held()                                                    \
21 	(rcu_read_lock_held() || rcu_read_lock_trace_held() ||                 \
22 	 rcu_read_lock_bh_held())
23 struct bpf_local_storage_map_bucket {
24 	struct hlist_head list;
25 	raw_spinlock_t lock;
26 };
27 
28 /* Thp map is not the primary owner of a bpf_local_storage_elem.
29  * Instead, the container object (eg. sk->sk_bpf_storage) is.
30  *
31  * The map (bpf_local_storage_map) is for two purposes
32  * 1. Define the size of the "local storage".  It is
33  *    the map's value_size.
34  *
35  * 2. Maintain a list to keep track of all elems such
36  *    that they can be cleaned up during the map destruction.
37  *
38  * When a bpf local storage is being looked up for a
39  * particular object,  the "bpf_map" pointer is actually used
40  * as the "key" to search in the list of elem in
41  * the respective bpf_local_storage owned by the object.
42  *
43  * e.g. sk->sk_bpf_storage is the mini-map with the "bpf_map" pointer
44  * as the searching key.
45  */
46 struct bpf_local_storage_map {
47 	struct bpf_map map;
48 	/* Lookup elem does not require accessing the map.
49 	 *
50 	 * Updating/Deleting requires a bucket lock to
51 	 * link/unlink the elem from the map.  Having
52 	 * multiple buckets to improve contention.
53 	 */
54 	struct bpf_local_storage_map_bucket *buckets;
55 	u32 bucket_log;
56 	u16 elem_size;
57 	u16 cache_idx;
58 };
59 
60 struct bpf_local_storage_data {
61 	/* smap is used as the searching key when looking up
62 	 * from the object's bpf_local_storage.
63 	 *
64 	 * Put it in the same cacheline as the data to minimize
65 	 * the number of cachelines accessed during the cache hit case.
66 	 */
67 	struct bpf_local_storage_map __rcu *smap;
68 	u8 data[] __aligned(8);
69 };
70 
71 /* Linked to bpf_local_storage and bpf_local_storage_map */
72 struct bpf_local_storage_elem {
73 	struct hlist_node map_node;	/* Linked to bpf_local_storage_map */
74 	struct hlist_node snode;	/* Linked to bpf_local_storage */
75 	struct bpf_local_storage __rcu *local_storage;
76 	struct rcu_head rcu;
77 	/* 8 bytes hole */
78 	/* The data is stored in another cacheline to minimize
79 	 * the number of cachelines access during a cache hit.
80 	 */
81 	struct bpf_local_storage_data sdata ____cacheline_aligned;
82 };
83 
84 struct bpf_local_storage {
85 	struct bpf_local_storage_data __rcu *cache[BPF_LOCAL_STORAGE_CACHE_SIZE];
86 	struct hlist_head list; /* List of bpf_local_storage_elem */
87 	void *owner;		/* The object that owns the above "list" of
88 				 * bpf_local_storage_elem.
89 				 */
90 	struct rcu_head rcu;
91 	raw_spinlock_t lock;	/* Protect adding/removing from the "list" */
92 };
93 
94 /* U16_MAX is much more than enough for sk local storage
95  * considering a tcp_sock is ~2k.
96  */
97 #define BPF_LOCAL_STORAGE_MAX_VALUE_SIZE				       \
98 	min_t(u32,                                                             \
99 	      (KMALLOC_MAX_SIZE - MAX_BPF_STACK -                              \
100 	       sizeof(struct bpf_local_storage_elem)),                         \
101 	      (U16_MAX - sizeof(struct bpf_local_storage_elem)))
102 
103 #define SELEM(_SDATA)                                                          \
104 	container_of((_SDATA), struct bpf_local_storage_elem, sdata)
105 #define SDATA(_SELEM) (&(_SELEM)->sdata)
106 
107 #define BPF_LOCAL_STORAGE_CACHE_SIZE	16
108 
109 struct bpf_local_storage_cache {
110 	spinlock_t idx_lock;
111 	u64 idx_usage_counts[BPF_LOCAL_STORAGE_CACHE_SIZE];
112 };
113 
114 #define DEFINE_BPF_STORAGE_CACHE(name)				\
115 static struct bpf_local_storage_cache name = {			\
116 	.idx_lock = __SPIN_LOCK_UNLOCKED(name.idx_lock),	\
117 }
118 
119 u16 bpf_local_storage_cache_idx_get(struct bpf_local_storage_cache *cache);
120 void bpf_local_storage_cache_idx_free(struct bpf_local_storage_cache *cache,
121 				      u16 idx);
122 
123 /* Helper functions for bpf_local_storage */
124 int bpf_local_storage_map_alloc_check(union bpf_attr *attr);
125 
126 struct bpf_local_storage_map *bpf_local_storage_map_alloc(union bpf_attr *attr);
127 
128 struct bpf_local_storage_data *
129 bpf_local_storage_lookup(struct bpf_local_storage *local_storage,
130 			 struct bpf_local_storage_map *smap,
131 			 bool cacheit_lockit);
132 
133 void bpf_local_storage_map_free(struct bpf_local_storage_map *smap,
134 				int __percpu *busy_counter);
135 
136 int bpf_local_storage_map_check_btf(const struct bpf_map *map,
137 				    const struct btf *btf,
138 				    const struct btf_type *key_type,
139 				    const struct btf_type *value_type);
140 
141 void bpf_selem_link_storage_nolock(struct bpf_local_storage *local_storage,
142 				   struct bpf_local_storage_elem *selem);
143 
144 bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
145 				     struct bpf_local_storage_elem *selem,
146 				     bool uncharge_omem, bool use_trace_rcu);
147 
148 void bpf_selem_unlink(struct bpf_local_storage_elem *selem, bool use_trace_rcu);
149 
150 void bpf_selem_link_map(struct bpf_local_storage_map *smap,
151 			struct bpf_local_storage_elem *selem);
152 
153 void bpf_selem_unlink_map(struct bpf_local_storage_elem *selem);
154 
155 struct bpf_local_storage_elem *
156 bpf_selem_alloc(struct bpf_local_storage_map *smap, void *owner, void *value,
157 		bool charge_mem, gfp_t gfp_flags);
158 
159 int
160 bpf_local_storage_alloc(void *owner,
161 			struct bpf_local_storage_map *smap,
162 			struct bpf_local_storage_elem *first_selem,
163 			gfp_t gfp_flags);
164 
165 struct bpf_local_storage_data *
166 bpf_local_storage_update(void *owner, struct bpf_local_storage_map *smap,
167 			 void *value, u64 map_flags, gfp_t gfp_flags);
168 
169 void bpf_local_storage_free_rcu(struct rcu_head *rcu);
170 
171 #endif /* _BPF_LOCAL_STORAGE_H */
172