xref: /openbmc/linux/kernel/bpf/bpf_local_storage.c (revision 0a09a2f933c73dc76ab0b72da6855f44342a8903)
1450af8d0SKP Singh // SPDX-License-Identifier: GPL-2.0
2450af8d0SKP Singh /* Copyright (c) 2019 Facebook  */
3450af8d0SKP Singh #include <linux/rculist.h>
4450af8d0SKP Singh #include <linux/list.h>
5450af8d0SKP Singh #include <linux/hash.h>
6450af8d0SKP Singh #include <linux/types.h>
7450af8d0SKP Singh #include <linux/spinlock.h>
8450af8d0SKP Singh #include <linux/bpf.h>
9450af8d0SKP Singh #include <linux/btf_ids.h>
10450af8d0SKP Singh #include <linux/bpf_local_storage.h>
11450af8d0SKP Singh #include <net/sock.h>
12450af8d0SKP Singh #include <uapi/linux/sock_diag.h>
13450af8d0SKP Singh #include <uapi/linux/btf.h>
140fe4b381SKP Singh #include <linux/rcupdate.h>
150fe4b381SKP Singh #include <linux/rcupdate_trace.h>
160fe4b381SKP Singh #include <linux/rcupdate_wait.h>
17450af8d0SKP Singh 
18450af8d0SKP Singh #define BPF_LOCAL_STORAGE_CREATE_FLAG_MASK (BPF_F_NO_PREALLOC | BPF_F_CLONE)
19450af8d0SKP Singh 
20450af8d0SKP Singh static struct bpf_local_storage_map_bucket *
21450af8d0SKP Singh select_bucket(struct bpf_local_storage_map *smap,
22450af8d0SKP Singh 	      struct bpf_local_storage_elem *selem)
23450af8d0SKP Singh {
24450af8d0SKP Singh 	return &smap->buckets[hash_ptr(selem, smap->bucket_log)];
25450af8d0SKP Singh }
26450af8d0SKP Singh 
27450af8d0SKP Singh static int mem_charge(struct bpf_local_storage_map *smap, void *owner, u32 size)
28450af8d0SKP Singh {
29450af8d0SKP Singh 	struct bpf_map *map = &smap->map;
30450af8d0SKP Singh 
31450af8d0SKP Singh 	if (!map->ops->map_local_storage_charge)
32450af8d0SKP Singh 		return 0;
33450af8d0SKP Singh 
34450af8d0SKP Singh 	return map->ops->map_local_storage_charge(smap, owner, size);
35450af8d0SKP Singh }
36450af8d0SKP Singh 
37450af8d0SKP Singh static void mem_uncharge(struct bpf_local_storage_map *smap, void *owner,
38450af8d0SKP Singh 			 u32 size)
39450af8d0SKP Singh {
40450af8d0SKP Singh 	struct bpf_map *map = &smap->map;
41450af8d0SKP Singh 
42450af8d0SKP Singh 	if (map->ops->map_local_storage_uncharge)
43450af8d0SKP Singh 		map->ops->map_local_storage_uncharge(smap, owner, size);
44450af8d0SKP Singh }
45450af8d0SKP Singh 
46450af8d0SKP Singh static struct bpf_local_storage __rcu **
47450af8d0SKP Singh owner_storage(struct bpf_local_storage_map *smap, void *owner)
48450af8d0SKP Singh {
49450af8d0SKP Singh 	struct bpf_map *map = &smap->map;
50450af8d0SKP Singh 
51450af8d0SKP Singh 	return map->ops->map_owner_storage_ptr(owner);
52450af8d0SKP Singh }
53450af8d0SKP Singh 
54*0a09a2f9SKumar Kartikeya Dwivedi static bool selem_linked_to_storage_lockless(const struct bpf_local_storage_elem *selem)
55*0a09a2f9SKumar Kartikeya Dwivedi {
56*0a09a2f9SKumar Kartikeya Dwivedi 	return !hlist_unhashed_lockless(&selem->snode);
57*0a09a2f9SKumar Kartikeya Dwivedi }
58*0a09a2f9SKumar Kartikeya Dwivedi 
59450af8d0SKP Singh static bool selem_linked_to_storage(const struct bpf_local_storage_elem *selem)
60450af8d0SKP Singh {
61450af8d0SKP Singh 	return !hlist_unhashed(&selem->snode);
62450af8d0SKP Singh }
63450af8d0SKP Singh 
64*0a09a2f9SKumar Kartikeya Dwivedi static bool selem_linked_to_map_lockless(const struct bpf_local_storage_elem *selem)
65*0a09a2f9SKumar Kartikeya Dwivedi {
66*0a09a2f9SKumar Kartikeya Dwivedi 	return !hlist_unhashed_lockless(&selem->map_node);
67*0a09a2f9SKumar Kartikeya Dwivedi }
68*0a09a2f9SKumar Kartikeya Dwivedi 
69450af8d0SKP Singh static bool selem_linked_to_map(const struct bpf_local_storage_elem *selem)
70450af8d0SKP Singh {
71450af8d0SKP Singh 	return !hlist_unhashed(&selem->map_node);
72450af8d0SKP Singh }
73450af8d0SKP Singh 
74450af8d0SKP Singh struct bpf_local_storage_elem *
75450af8d0SKP Singh bpf_selem_alloc(struct bpf_local_storage_map *smap, void *owner,
76b00fa38aSJoanne Koong 		void *value, bool charge_mem, gfp_t gfp_flags)
77450af8d0SKP Singh {
78450af8d0SKP Singh 	struct bpf_local_storage_elem *selem;
79450af8d0SKP Singh 
80450af8d0SKP Singh 	if (charge_mem && mem_charge(smap, owner, smap->elem_size))
81450af8d0SKP Singh 		return NULL;
82450af8d0SKP Singh 
83e9aae8beSRoman Gushchin 	selem = bpf_map_kzalloc(&smap->map, smap->elem_size,
84b00fa38aSJoanne Koong 				gfp_flags | __GFP_NOWARN);
85450af8d0SKP Singh 	if (selem) {
86450af8d0SKP Singh 		if (value)
87836e49e1SXu Kuohai 			copy_map_value(&smap->map, SDATA(selem)->data, value);
88450af8d0SKP Singh 		return selem;
89450af8d0SKP Singh 	}
90450af8d0SKP Singh 
91450af8d0SKP Singh 	if (charge_mem)
92450af8d0SKP Singh 		mem_uncharge(smap, owner, smap->elem_size);
93450af8d0SKP Singh 
94450af8d0SKP Singh 	return NULL;
95450af8d0SKP Singh }
96450af8d0SKP Singh 
970fe4b381SKP Singh void bpf_local_storage_free_rcu(struct rcu_head *rcu)
980fe4b381SKP Singh {
990fe4b381SKP Singh 	struct bpf_local_storage *local_storage;
1000fe4b381SKP Singh 
101d39d1445SHou Tao 	/* If RCU Tasks Trace grace period implies RCU grace period, do
102d39d1445SHou Tao 	 * kfree(), else do kfree_rcu().
103d39d1445SHou Tao 	 */
1040fe4b381SKP Singh 	local_storage = container_of(rcu, struct bpf_local_storage, rcu);
105d39d1445SHou Tao 	if (rcu_trace_implies_rcu_gp())
106d39d1445SHou Tao 		kfree(local_storage);
107d39d1445SHou Tao 	else
1080fe4b381SKP Singh 		kfree_rcu(local_storage, rcu);
1090fe4b381SKP Singh }
1100fe4b381SKP Singh 
1110fe4b381SKP Singh static void bpf_selem_free_rcu(struct rcu_head *rcu)
1120fe4b381SKP Singh {
1130fe4b381SKP Singh 	struct bpf_local_storage_elem *selem;
1140fe4b381SKP Singh 
1150fe4b381SKP Singh 	selem = container_of(rcu, struct bpf_local_storage_elem, rcu);
116d39d1445SHou Tao 	if (rcu_trace_implies_rcu_gp())
117d39d1445SHou Tao 		kfree(selem);
118d39d1445SHou Tao 	else
1190fe4b381SKP Singh 		kfree_rcu(selem, rcu);
1200fe4b381SKP Singh }
1210fe4b381SKP Singh 
122450af8d0SKP Singh /* local_storage->lock must be held and selem->local_storage == local_storage.
123450af8d0SKP Singh  * The caller must ensure selem->smap is still valid to be
124450af8d0SKP Singh  * dereferenced for its smap->elem_size and smap->cache_idx.
125450af8d0SKP Singh  */
126c83597faSYonghong Song static bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
127450af8d0SKP Singh 					    struct bpf_local_storage_elem *selem,
128dcf456c9SKP Singh 					    bool uncharge_mem, bool use_trace_rcu)
129450af8d0SKP Singh {
130450af8d0SKP Singh 	struct bpf_local_storage_map *smap;
131450af8d0SKP Singh 	bool free_local_storage;
132450af8d0SKP Singh 	void *owner;
133450af8d0SKP Singh 
1340fe4b381SKP Singh 	smap = rcu_dereference_check(SDATA(selem)->smap, bpf_rcu_lock_held());
135450af8d0SKP Singh 	owner = local_storage->owner;
136450af8d0SKP Singh 
137450af8d0SKP Singh 	/* All uncharging on the owner must be done first.
138450af8d0SKP Singh 	 * The owner may be freed once the last selem is unlinked
139450af8d0SKP Singh 	 * from local_storage.
140450af8d0SKP Singh 	 */
141450af8d0SKP Singh 	if (uncharge_mem)
142450af8d0SKP Singh 		mem_uncharge(smap, owner, smap->elem_size);
143450af8d0SKP Singh 
144450af8d0SKP Singh 	free_local_storage = hlist_is_singular_node(&selem->snode,
145450af8d0SKP Singh 						    &local_storage->list);
146450af8d0SKP Singh 	if (free_local_storage) {
147450af8d0SKP Singh 		mem_uncharge(smap, owner, sizeof(struct bpf_local_storage));
148450af8d0SKP Singh 		local_storage->owner = NULL;
149450af8d0SKP Singh 
150450af8d0SKP Singh 		/* After this RCU_INIT, owner may be freed and cannot be used */
151450af8d0SKP Singh 		RCU_INIT_POINTER(*owner_storage(smap, owner), NULL);
152450af8d0SKP Singh 
153450af8d0SKP Singh 		/* local_storage is not freed now.  local_storage->lock is
154450af8d0SKP Singh 		 * still held and raw_spin_unlock_bh(&local_storage->lock)
155450af8d0SKP Singh 		 * will be done by the caller.
156450af8d0SKP Singh 		 *
157450af8d0SKP Singh 		 * Although the unlock will be done under
158c561d110STom Rix 		 * rcu_read_lock(),  it is more intuitive to
1590fe4b381SKP Singh 		 * read if the freeing of the storage is done
160450af8d0SKP Singh 		 * after the raw_spin_unlock_bh(&local_storage->lock).
161450af8d0SKP Singh 		 *
162450af8d0SKP Singh 		 * Hence, a "bool free_local_storage" is returned
1630fe4b381SKP Singh 		 * to the caller which then calls then frees the storage after
1640fe4b381SKP Singh 		 * all the RCU grace periods have expired.
165450af8d0SKP Singh 		 */
166450af8d0SKP Singh 	}
167450af8d0SKP Singh 	hlist_del_init_rcu(&selem->snode);
168450af8d0SKP Singh 	if (rcu_access_pointer(local_storage->cache[smap->cache_idx]) ==
169450af8d0SKP Singh 	    SDATA(selem))
170450af8d0SKP Singh 		RCU_INIT_POINTER(local_storage->cache[smap->cache_idx], NULL);
171450af8d0SKP Singh 
172dcf456c9SKP Singh 	if (use_trace_rcu)
1730fe4b381SKP Singh 		call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
174dcf456c9SKP Singh 	else
175dcf456c9SKP Singh 		kfree_rcu(selem, rcu);
176dcf456c9SKP Singh 
177450af8d0SKP Singh 	return free_local_storage;
178450af8d0SKP Singh }
179450af8d0SKP Singh 
180dcf456c9SKP Singh static void __bpf_selem_unlink_storage(struct bpf_local_storage_elem *selem,
181dcf456c9SKP Singh 				       bool use_trace_rcu)
182450af8d0SKP Singh {
183450af8d0SKP Singh 	struct bpf_local_storage *local_storage;
184450af8d0SKP Singh 	bool free_local_storage = false;
185a10787e6SSong Liu 	unsigned long flags;
186450af8d0SKP Singh 
187*0a09a2f9SKumar Kartikeya Dwivedi 	if (unlikely(!selem_linked_to_storage_lockless(selem)))
188450af8d0SKP Singh 		/* selem has already been unlinked from sk */
189450af8d0SKP Singh 		return;
190450af8d0SKP Singh 
1910fe4b381SKP Singh 	local_storage = rcu_dereference_check(selem->local_storage,
1920fe4b381SKP Singh 					      bpf_rcu_lock_held());
193a10787e6SSong Liu 	raw_spin_lock_irqsave(&local_storage->lock, flags);
194450af8d0SKP Singh 	if (likely(selem_linked_to_storage(selem)))
195450af8d0SKP Singh 		free_local_storage = bpf_selem_unlink_storage_nolock(
196dcf456c9SKP Singh 			local_storage, selem, true, use_trace_rcu);
197a10787e6SSong Liu 	raw_spin_unlock_irqrestore(&local_storage->lock, flags);
198450af8d0SKP Singh 
199dcf456c9SKP Singh 	if (free_local_storage) {
200dcf456c9SKP Singh 		if (use_trace_rcu)
2010fe4b381SKP Singh 			call_rcu_tasks_trace(&local_storage->rcu,
2020fe4b381SKP Singh 				     bpf_local_storage_free_rcu);
203dcf456c9SKP Singh 		else
204dcf456c9SKP Singh 			kfree_rcu(local_storage, rcu);
205dcf456c9SKP Singh 	}
206450af8d0SKP Singh }
207450af8d0SKP Singh 
208450af8d0SKP Singh void bpf_selem_link_storage_nolock(struct bpf_local_storage *local_storage,
209450af8d0SKP Singh 				   struct bpf_local_storage_elem *selem)
210450af8d0SKP Singh {
211450af8d0SKP Singh 	RCU_INIT_POINTER(selem->local_storage, local_storage);
21270b97111SMartin KaFai Lau 	hlist_add_head_rcu(&selem->snode, &local_storage->list);
213450af8d0SKP Singh }
214450af8d0SKP Singh 
215450af8d0SKP Singh void bpf_selem_unlink_map(struct bpf_local_storage_elem *selem)
216450af8d0SKP Singh {
217450af8d0SKP Singh 	struct bpf_local_storage_map *smap;
218450af8d0SKP Singh 	struct bpf_local_storage_map_bucket *b;
219a10787e6SSong Liu 	unsigned long flags;
220450af8d0SKP Singh 
221*0a09a2f9SKumar Kartikeya Dwivedi 	if (unlikely(!selem_linked_to_map_lockless(selem)))
222450af8d0SKP Singh 		/* selem has already be unlinked from smap */
223450af8d0SKP Singh 		return;
224450af8d0SKP Singh 
2250fe4b381SKP Singh 	smap = rcu_dereference_check(SDATA(selem)->smap, bpf_rcu_lock_held());
226450af8d0SKP Singh 	b = select_bucket(smap, selem);
227a10787e6SSong Liu 	raw_spin_lock_irqsave(&b->lock, flags);
228450af8d0SKP Singh 	if (likely(selem_linked_to_map(selem)))
229450af8d0SKP Singh 		hlist_del_init_rcu(&selem->map_node);
230a10787e6SSong Liu 	raw_spin_unlock_irqrestore(&b->lock, flags);
231450af8d0SKP Singh }
232450af8d0SKP Singh 
233450af8d0SKP Singh void bpf_selem_link_map(struct bpf_local_storage_map *smap,
234450af8d0SKP Singh 			struct bpf_local_storage_elem *selem)
235450af8d0SKP Singh {
236450af8d0SKP Singh 	struct bpf_local_storage_map_bucket *b = select_bucket(smap, selem);
237a10787e6SSong Liu 	unsigned long flags;
238450af8d0SKP Singh 
239a10787e6SSong Liu 	raw_spin_lock_irqsave(&b->lock, flags);
240450af8d0SKP Singh 	RCU_INIT_POINTER(SDATA(selem)->smap, smap);
241450af8d0SKP Singh 	hlist_add_head_rcu(&selem->map_node, &b->list);
242a10787e6SSong Liu 	raw_spin_unlock_irqrestore(&b->lock, flags);
243450af8d0SKP Singh }
244450af8d0SKP Singh 
245dcf456c9SKP Singh void bpf_selem_unlink(struct bpf_local_storage_elem *selem, bool use_trace_rcu)
246450af8d0SKP Singh {
247450af8d0SKP Singh 	/* Always unlink from map before unlinking from local_storage
248450af8d0SKP Singh 	 * because selem will be freed after successfully unlinked from
249450af8d0SKP Singh 	 * the local_storage.
250450af8d0SKP Singh 	 */
251450af8d0SKP Singh 	bpf_selem_unlink_map(selem);
252dcf456c9SKP Singh 	__bpf_selem_unlink_storage(selem, use_trace_rcu);
253450af8d0SKP Singh }
254450af8d0SKP Singh 
255e8b02296SMartin KaFai Lau /* If cacheit_lockit is false, this lookup function is lockless */
256450af8d0SKP Singh struct bpf_local_storage_data *
257450af8d0SKP Singh bpf_local_storage_lookup(struct bpf_local_storage *local_storage,
258450af8d0SKP Singh 			 struct bpf_local_storage_map *smap,
259450af8d0SKP Singh 			 bool cacheit_lockit)
260450af8d0SKP Singh {
261450af8d0SKP Singh 	struct bpf_local_storage_data *sdata;
262450af8d0SKP Singh 	struct bpf_local_storage_elem *selem;
263450af8d0SKP Singh 
264450af8d0SKP Singh 	/* Fast path (cache hit) */
2650fe4b381SKP Singh 	sdata = rcu_dereference_check(local_storage->cache[smap->cache_idx],
2660fe4b381SKP Singh 				      bpf_rcu_lock_held());
267450af8d0SKP Singh 	if (sdata && rcu_access_pointer(sdata->smap) == smap)
268450af8d0SKP Singh 		return sdata;
269450af8d0SKP Singh 
270450af8d0SKP Singh 	/* Slow path (cache miss) */
2710fe4b381SKP Singh 	hlist_for_each_entry_rcu(selem, &local_storage->list, snode,
2720fe4b381SKP Singh 				  rcu_read_lock_trace_held())
273450af8d0SKP Singh 		if (rcu_access_pointer(SDATA(selem)->smap) == smap)
274450af8d0SKP Singh 			break;
275450af8d0SKP Singh 
276450af8d0SKP Singh 	if (!selem)
277450af8d0SKP Singh 		return NULL;
278450af8d0SKP Singh 
279450af8d0SKP Singh 	sdata = SDATA(selem);
280450af8d0SKP Singh 	if (cacheit_lockit) {
281a10787e6SSong Liu 		unsigned long flags;
282a10787e6SSong Liu 
283450af8d0SKP Singh 		/* spinlock is needed to avoid racing with the
284450af8d0SKP Singh 		 * parallel delete.  Otherwise, publishing an already
285450af8d0SKP Singh 		 * deleted sdata to the cache will become a use-after-free
286450af8d0SKP Singh 		 * problem in the next bpf_local_storage_lookup().
287450af8d0SKP Singh 		 */
288a10787e6SSong Liu 		raw_spin_lock_irqsave(&local_storage->lock, flags);
289450af8d0SKP Singh 		if (selem_linked_to_storage(selem))
290450af8d0SKP Singh 			rcu_assign_pointer(local_storage->cache[smap->cache_idx],
291450af8d0SKP Singh 					   sdata);
292a10787e6SSong Liu 		raw_spin_unlock_irqrestore(&local_storage->lock, flags);
293450af8d0SKP Singh 	}
294450af8d0SKP Singh 
295450af8d0SKP Singh 	return sdata;
296450af8d0SKP Singh }
297450af8d0SKP Singh 
298450af8d0SKP Singh static int check_flags(const struct bpf_local_storage_data *old_sdata,
299450af8d0SKP Singh 		       u64 map_flags)
300450af8d0SKP Singh {
301450af8d0SKP Singh 	if (old_sdata && (map_flags & ~BPF_F_LOCK) == BPF_NOEXIST)
302450af8d0SKP Singh 		/* elem already exists */
303450af8d0SKP Singh 		return -EEXIST;
304450af8d0SKP Singh 
305450af8d0SKP Singh 	if (!old_sdata && (map_flags & ~BPF_F_LOCK) == BPF_EXIST)
306450af8d0SKP Singh 		/* elem doesn't exist, cannot update it */
307450af8d0SKP Singh 		return -ENOENT;
308450af8d0SKP Singh 
309450af8d0SKP Singh 	return 0;
310450af8d0SKP Singh }
311450af8d0SKP Singh 
312450af8d0SKP Singh int bpf_local_storage_alloc(void *owner,
313450af8d0SKP Singh 			    struct bpf_local_storage_map *smap,
314b00fa38aSJoanne Koong 			    struct bpf_local_storage_elem *first_selem,
315b00fa38aSJoanne Koong 			    gfp_t gfp_flags)
316450af8d0SKP Singh {
317450af8d0SKP Singh 	struct bpf_local_storage *prev_storage, *storage;
318450af8d0SKP Singh 	struct bpf_local_storage **owner_storage_ptr;
319450af8d0SKP Singh 	int err;
320450af8d0SKP Singh 
321450af8d0SKP Singh 	err = mem_charge(smap, owner, sizeof(*storage));
322450af8d0SKP Singh 	if (err)
323450af8d0SKP Singh 		return err;
324450af8d0SKP Singh 
325e9aae8beSRoman Gushchin 	storage = bpf_map_kzalloc(&smap->map, sizeof(*storage),
326b00fa38aSJoanne Koong 				  gfp_flags | __GFP_NOWARN);
327450af8d0SKP Singh 	if (!storage) {
328450af8d0SKP Singh 		err = -ENOMEM;
329450af8d0SKP Singh 		goto uncharge;
330450af8d0SKP Singh 	}
331450af8d0SKP Singh 
332450af8d0SKP Singh 	INIT_HLIST_HEAD(&storage->list);
333450af8d0SKP Singh 	raw_spin_lock_init(&storage->lock);
334450af8d0SKP Singh 	storage->owner = owner;
335450af8d0SKP Singh 
336450af8d0SKP Singh 	bpf_selem_link_storage_nolock(storage, first_selem);
337450af8d0SKP Singh 	bpf_selem_link_map(smap, first_selem);
338450af8d0SKP Singh 
339450af8d0SKP Singh 	owner_storage_ptr =
340450af8d0SKP Singh 		(struct bpf_local_storage **)owner_storage(smap, owner);
341450af8d0SKP Singh 	/* Publish storage to the owner.
342450af8d0SKP Singh 	 * Instead of using any lock of the kernel object (i.e. owner),
343450af8d0SKP Singh 	 * cmpxchg will work with any kernel object regardless what
344450af8d0SKP Singh 	 * the running context is, bh, irq...etc.
345450af8d0SKP Singh 	 *
346450af8d0SKP Singh 	 * From now on, the owner->storage pointer (e.g. sk->sk_bpf_storage)
347450af8d0SKP Singh 	 * is protected by the storage->lock.  Hence, when freeing
348450af8d0SKP Singh 	 * the owner->storage, the storage->lock must be held before
349450af8d0SKP Singh 	 * setting owner->storage ptr to NULL.
350450af8d0SKP Singh 	 */
351450af8d0SKP Singh 	prev_storage = cmpxchg(owner_storage_ptr, NULL, storage);
352450af8d0SKP Singh 	if (unlikely(prev_storage)) {
353450af8d0SKP Singh 		bpf_selem_unlink_map(first_selem);
354450af8d0SKP Singh 		err = -EAGAIN;
355450af8d0SKP Singh 		goto uncharge;
356450af8d0SKP Singh 
357450af8d0SKP Singh 		/* Note that even first_selem was linked to smap's
358450af8d0SKP Singh 		 * bucket->list, first_selem can be freed immediately
359450af8d0SKP Singh 		 * (instead of kfree_rcu) because
360450af8d0SKP Singh 		 * bpf_local_storage_map_free() does a
3610fe4b381SKP Singh 		 * synchronize_rcu_mult (waiting for both sleepable and
3620fe4b381SKP Singh 		 * normal programs) before walking the bucket->list.
363450af8d0SKP Singh 		 * Hence, no one is accessing selem from the
364450af8d0SKP Singh 		 * bucket->list under rcu_read_lock().
365450af8d0SKP Singh 		 */
366450af8d0SKP Singh 	}
367450af8d0SKP Singh 
368450af8d0SKP Singh 	return 0;
369450af8d0SKP Singh 
370450af8d0SKP Singh uncharge:
371450af8d0SKP Singh 	kfree(storage);
372450af8d0SKP Singh 	mem_uncharge(smap, owner, sizeof(*storage));
373450af8d0SKP Singh 	return err;
374450af8d0SKP Singh }
375450af8d0SKP Singh 
376450af8d0SKP Singh /* sk cannot be going away because it is linking new elem
377450af8d0SKP Singh  * to sk->sk_bpf_storage. (i.e. sk->sk_refcnt cannot be 0).
378450af8d0SKP Singh  * Otherwise, it will become a leak (and other memory issues
379450af8d0SKP Singh  * during map destruction).
380450af8d0SKP Singh  */
381450af8d0SKP Singh struct bpf_local_storage_data *
382450af8d0SKP Singh bpf_local_storage_update(void *owner, struct bpf_local_storage_map *smap,
383b00fa38aSJoanne Koong 			 void *value, u64 map_flags, gfp_t gfp_flags)
384450af8d0SKP Singh {
385450af8d0SKP Singh 	struct bpf_local_storage_data *old_sdata = NULL;
386b00fa38aSJoanne Koong 	struct bpf_local_storage_elem *selem = NULL;
387450af8d0SKP Singh 	struct bpf_local_storage *local_storage;
388a10787e6SSong Liu 	unsigned long flags;
389450af8d0SKP Singh 	int err;
390450af8d0SKP Singh 
391450af8d0SKP Singh 	/* BPF_EXIST and BPF_NOEXIST cannot be both set */
392450af8d0SKP Singh 	if (unlikely((map_flags & ~BPF_F_LOCK) > BPF_EXIST) ||
393450af8d0SKP Singh 	    /* BPF_F_LOCK can only be used in a value with spin_lock */
394450af8d0SKP Singh 	    unlikely((map_flags & BPF_F_LOCK) &&
395db559117SKumar Kartikeya Dwivedi 		     !btf_record_has_field(smap->map.record, BPF_SPIN_LOCK)))
396450af8d0SKP Singh 		return ERR_PTR(-EINVAL);
397450af8d0SKP Singh 
398b00fa38aSJoanne Koong 	if (gfp_flags == GFP_KERNEL && (map_flags & ~BPF_F_LOCK) != BPF_NOEXIST)
399b00fa38aSJoanne Koong 		return ERR_PTR(-EINVAL);
400b00fa38aSJoanne Koong 
4010fe4b381SKP Singh 	local_storage = rcu_dereference_check(*owner_storage(smap, owner),
4020fe4b381SKP Singh 					      bpf_rcu_lock_held());
403450af8d0SKP Singh 	if (!local_storage || hlist_empty(&local_storage->list)) {
404450af8d0SKP Singh 		/* Very first elem for the owner */
405450af8d0SKP Singh 		err = check_flags(NULL, map_flags);
406450af8d0SKP Singh 		if (err)
407450af8d0SKP Singh 			return ERR_PTR(err);
408450af8d0SKP Singh 
409b00fa38aSJoanne Koong 		selem = bpf_selem_alloc(smap, owner, value, true, gfp_flags);
410450af8d0SKP Singh 		if (!selem)
411450af8d0SKP Singh 			return ERR_PTR(-ENOMEM);
412450af8d0SKP Singh 
413b00fa38aSJoanne Koong 		err = bpf_local_storage_alloc(owner, smap, selem, gfp_flags);
414450af8d0SKP Singh 		if (err) {
415450af8d0SKP Singh 			kfree(selem);
416450af8d0SKP Singh 			mem_uncharge(smap, owner, smap->elem_size);
417450af8d0SKP Singh 			return ERR_PTR(err);
418450af8d0SKP Singh 		}
419450af8d0SKP Singh 
420450af8d0SKP Singh 		return SDATA(selem);
421450af8d0SKP Singh 	}
422450af8d0SKP Singh 
423450af8d0SKP Singh 	if ((map_flags & BPF_F_LOCK) && !(map_flags & BPF_NOEXIST)) {
424450af8d0SKP Singh 		/* Hoping to find an old_sdata to do inline update
425450af8d0SKP Singh 		 * such that it can avoid taking the local_storage->lock
426450af8d0SKP Singh 		 * and changing the lists.
427450af8d0SKP Singh 		 */
428450af8d0SKP Singh 		old_sdata =
429450af8d0SKP Singh 			bpf_local_storage_lookup(local_storage, smap, false);
430450af8d0SKP Singh 		err = check_flags(old_sdata, map_flags);
431450af8d0SKP Singh 		if (err)
432450af8d0SKP Singh 			return ERR_PTR(err);
433*0a09a2f9SKumar Kartikeya Dwivedi 		if (old_sdata && selem_linked_to_storage_lockless(SELEM(old_sdata))) {
434450af8d0SKP Singh 			copy_map_value_locked(&smap->map, old_sdata->data,
435450af8d0SKP Singh 					      value, false);
436450af8d0SKP Singh 			return old_sdata;
437450af8d0SKP Singh 		}
438450af8d0SKP Singh 	}
439450af8d0SKP Singh 
440b00fa38aSJoanne Koong 	if (gfp_flags == GFP_KERNEL) {
441b00fa38aSJoanne Koong 		selem = bpf_selem_alloc(smap, owner, value, true, gfp_flags);
442b00fa38aSJoanne Koong 		if (!selem)
443b00fa38aSJoanne Koong 			return ERR_PTR(-ENOMEM);
444b00fa38aSJoanne Koong 	}
445b00fa38aSJoanne Koong 
446a10787e6SSong Liu 	raw_spin_lock_irqsave(&local_storage->lock, flags);
447450af8d0SKP Singh 
448450af8d0SKP Singh 	/* Recheck local_storage->list under local_storage->lock */
449450af8d0SKP Singh 	if (unlikely(hlist_empty(&local_storage->list))) {
450450af8d0SKP Singh 		/* A parallel del is happening and local_storage is going
451450af8d0SKP Singh 		 * away.  It has just been checked before, so very
452450af8d0SKP Singh 		 * unlikely.  Return instead of retry to keep things
453450af8d0SKP Singh 		 * simple.
454450af8d0SKP Singh 		 */
455450af8d0SKP Singh 		err = -EAGAIN;
456450af8d0SKP Singh 		goto unlock_err;
457450af8d0SKP Singh 	}
458450af8d0SKP Singh 
459450af8d0SKP Singh 	old_sdata = bpf_local_storage_lookup(local_storage, smap, false);
460450af8d0SKP Singh 	err = check_flags(old_sdata, map_flags);
461450af8d0SKP Singh 	if (err)
462450af8d0SKP Singh 		goto unlock_err;
463450af8d0SKP Singh 
464450af8d0SKP Singh 	if (old_sdata && (map_flags & BPF_F_LOCK)) {
465450af8d0SKP Singh 		copy_map_value_locked(&smap->map, old_sdata->data, value,
466450af8d0SKP Singh 				      false);
467450af8d0SKP Singh 		selem = SELEM(old_sdata);
468450af8d0SKP Singh 		goto unlock;
469450af8d0SKP Singh 	}
470450af8d0SKP Singh 
471b00fa38aSJoanne Koong 	if (gfp_flags != GFP_KERNEL) {
472450af8d0SKP Singh 		/* local_storage->lock is held.  Hence, we are sure
473450af8d0SKP Singh 		 * we can unlink and uncharge the old_sdata successfully
474450af8d0SKP Singh 		 * later.  Hence, instead of charging the new selem now
475450af8d0SKP Singh 		 * and then uncharge the old selem later (which may cause
476450af8d0SKP Singh 		 * a potential but unnecessary charge failure),  avoid taking
477450af8d0SKP Singh 		 * a charge at all here (the "!old_sdata" check) and the
478450af8d0SKP Singh 		 * old_sdata will not be uncharged later during
479450af8d0SKP Singh 		 * bpf_selem_unlink_storage_nolock().
480450af8d0SKP Singh 		 */
481b00fa38aSJoanne Koong 		selem = bpf_selem_alloc(smap, owner, value, !old_sdata, gfp_flags);
482450af8d0SKP Singh 		if (!selem) {
483450af8d0SKP Singh 			err = -ENOMEM;
484450af8d0SKP Singh 			goto unlock_err;
485450af8d0SKP Singh 		}
486b00fa38aSJoanne Koong 	}
487450af8d0SKP Singh 
488450af8d0SKP Singh 	/* First, link the new selem to the map */
489450af8d0SKP Singh 	bpf_selem_link_map(smap, selem);
490450af8d0SKP Singh 
491450af8d0SKP Singh 	/* Second, link (and publish) the new selem to local_storage */
492450af8d0SKP Singh 	bpf_selem_link_storage_nolock(local_storage, selem);
493450af8d0SKP Singh 
494450af8d0SKP Singh 	/* Third, remove old selem, SELEM(old_sdata) */
495450af8d0SKP Singh 	if (old_sdata) {
496450af8d0SKP Singh 		bpf_selem_unlink_map(SELEM(old_sdata));
497450af8d0SKP Singh 		bpf_selem_unlink_storage_nolock(local_storage, SELEM(old_sdata),
498dcf456c9SKP Singh 						false, true);
499450af8d0SKP Singh 	}
500450af8d0SKP Singh 
501450af8d0SKP Singh unlock:
502a10787e6SSong Liu 	raw_spin_unlock_irqrestore(&local_storage->lock, flags);
503450af8d0SKP Singh 	return SDATA(selem);
504450af8d0SKP Singh 
505450af8d0SKP Singh unlock_err:
506a10787e6SSong Liu 	raw_spin_unlock_irqrestore(&local_storage->lock, flags);
507b00fa38aSJoanne Koong 	if (selem) {
508b00fa38aSJoanne Koong 		mem_uncharge(smap, owner, smap->elem_size);
509b00fa38aSJoanne Koong 		kfree(selem);
510b00fa38aSJoanne Koong 	}
511450af8d0SKP Singh 	return ERR_PTR(err);
512450af8d0SKP Singh }
513450af8d0SKP Singh 
514c83597faSYonghong Song static u16 bpf_local_storage_cache_idx_get(struct bpf_local_storage_cache *cache)
515450af8d0SKP Singh {
516450af8d0SKP Singh 	u64 min_usage = U64_MAX;
517450af8d0SKP Singh 	u16 i, res = 0;
518450af8d0SKP Singh 
519450af8d0SKP Singh 	spin_lock(&cache->idx_lock);
520450af8d0SKP Singh 
521450af8d0SKP Singh 	for (i = 0; i < BPF_LOCAL_STORAGE_CACHE_SIZE; i++) {
522450af8d0SKP Singh 		if (cache->idx_usage_counts[i] < min_usage) {
523450af8d0SKP Singh 			min_usage = cache->idx_usage_counts[i];
524450af8d0SKP Singh 			res = i;
525450af8d0SKP Singh 
526450af8d0SKP Singh 			/* Found a free cache_idx */
527450af8d0SKP Singh 			if (!min_usage)
528450af8d0SKP Singh 				break;
529450af8d0SKP Singh 		}
530450af8d0SKP Singh 	}
531450af8d0SKP Singh 	cache->idx_usage_counts[res]++;
532450af8d0SKP Singh 
533450af8d0SKP Singh 	spin_unlock(&cache->idx_lock);
534450af8d0SKP Singh 
535450af8d0SKP Singh 	return res;
536450af8d0SKP Singh }
537450af8d0SKP Singh 
538c83597faSYonghong Song static void bpf_local_storage_cache_idx_free(struct bpf_local_storage_cache *cache,
539450af8d0SKP Singh 					     u16 idx)
540450af8d0SKP Singh {
541450af8d0SKP Singh 	spin_lock(&cache->idx_lock);
542450af8d0SKP Singh 	cache->idx_usage_counts[idx]--;
543450af8d0SKP Singh 	spin_unlock(&cache->idx_lock);
544450af8d0SKP Singh }
545450af8d0SKP Singh 
546c83597faSYonghong Song int bpf_local_storage_map_alloc_check(union bpf_attr *attr)
547c83597faSYonghong Song {
548c83597faSYonghong Song 	if (attr->map_flags & ~BPF_LOCAL_STORAGE_CREATE_FLAG_MASK ||
549c83597faSYonghong Song 	    !(attr->map_flags & BPF_F_NO_PREALLOC) ||
550c83597faSYonghong Song 	    attr->max_entries ||
551c83597faSYonghong Song 	    attr->key_size != sizeof(int) || !attr->value_size ||
552c83597faSYonghong Song 	    /* Enforce BTF for userspace sk dumping */
553c83597faSYonghong Song 	    !attr->btf_key_type_id || !attr->btf_value_type_id)
554c83597faSYonghong Song 		return -EINVAL;
555c83597faSYonghong Song 
556c83597faSYonghong Song 	if (!bpf_capable())
557c83597faSYonghong Song 		return -EPERM;
558c83597faSYonghong Song 
559c83597faSYonghong Song 	if (attr->value_size > BPF_LOCAL_STORAGE_MAX_VALUE_SIZE)
560c83597faSYonghong Song 		return -E2BIG;
561c83597faSYonghong Song 
562c83597faSYonghong Song 	return 0;
563c83597faSYonghong Song }
564c83597faSYonghong Song 
565c83597faSYonghong Song static struct bpf_local_storage_map *__bpf_local_storage_map_alloc(union bpf_attr *attr)
566c83597faSYonghong Song {
567c83597faSYonghong Song 	struct bpf_local_storage_map *smap;
568c83597faSYonghong Song 	unsigned int i;
569c83597faSYonghong Song 	u32 nbuckets;
570c83597faSYonghong Song 
571c83597faSYonghong Song 	smap = bpf_map_area_alloc(sizeof(*smap), NUMA_NO_NODE);
572c83597faSYonghong Song 	if (!smap)
573c83597faSYonghong Song 		return ERR_PTR(-ENOMEM);
574c83597faSYonghong Song 	bpf_map_init_from_attr(&smap->map, attr);
575c83597faSYonghong Song 
576c83597faSYonghong Song 	nbuckets = roundup_pow_of_two(num_possible_cpus());
577c83597faSYonghong Song 	/* Use at least 2 buckets, select_bucket() is undefined behavior with 1 bucket */
578c83597faSYonghong Song 	nbuckets = max_t(u32, 2, nbuckets);
579c83597faSYonghong Song 	smap->bucket_log = ilog2(nbuckets);
580c83597faSYonghong Song 
581ddef81b5SYafang Shao 	smap->buckets = bpf_map_kvcalloc(&smap->map, sizeof(*smap->buckets),
582ddef81b5SYafang Shao 					 nbuckets, GFP_USER | __GFP_NOWARN);
583c83597faSYonghong Song 	if (!smap->buckets) {
584c83597faSYonghong Song 		bpf_map_area_free(smap);
585c83597faSYonghong Song 		return ERR_PTR(-ENOMEM);
586c83597faSYonghong Song 	}
587c83597faSYonghong Song 
588c83597faSYonghong Song 	for (i = 0; i < nbuckets; i++) {
589c83597faSYonghong Song 		INIT_HLIST_HEAD(&smap->buckets[i].list);
590c83597faSYonghong Song 		raw_spin_lock_init(&smap->buckets[i].lock);
591c83597faSYonghong Song 	}
592c83597faSYonghong Song 
593552d42a3SMartin KaFai Lau 	smap->elem_size = offsetof(struct bpf_local_storage_elem,
594552d42a3SMartin KaFai Lau 				   sdata.data[attr->value_size]);
595c83597faSYonghong Song 
596c83597faSYonghong Song 	return smap;
597c83597faSYonghong Song }
598c83597faSYonghong Song 
599c83597faSYonghong Song int bpf_local_storage_map_check_btf(const struct bpf_map *map,
600c83597faSYonghong Song 				    const struct btf *btf,
601c83597faSYonghong Song 				    const struct btf_type *key_type,
602c83597faSYonghong Song 				    const struct btf_type *value_type)
603c83597faSYonghong Song {
604c83597faSYonghong Song 	u32 int_data;
605c83597faSYonghong Song 
606c83597faSYonghong Song 	if (BTF_INFO_KIND(key_type->info) != BTF_KIND_INT)
607c83597faSYonghong Song 		return -EINVAL;
608c83597faSYonghong Song 
609c83597faSYonghong Song 	int_data = *(u32 *)(key_type + 1);
610c83597faSYonghong Song 	if (BTF_INT_BITS(int_data) != 32 || BTF_INT_OFFSET(int_data))
611c83597faSYonghong Song 		return -EINVAL;
612c83597faSYonghong Song 
613c83597faSYonghong Song 	return 0;
614c83597faSYonghong Song }
615c83597faSYonghong Song 
616c83597faSYonghong Song bool bpf_local_storage_unlink_nolock(struct bpf_local_storage *local_storage)
617450af8d0SKP Singh {
618450af8d0SKP Singh 	struct bpf_local_storage_elem *selem;
619c83597faSYonghong Song 	bool free_storage = false;
620c83597faSYonghong Song 	struct hlist_node *n;
621c83597faSYonghong Song 
622c83597faSYonghong Song 	/* Neither the bpf_prog nor the bpf_map's syscall
623c83597faSYonghong Song 	 * could be modifying the local_storage->list now.
624c83597faSYonghong Song 	 * Thus, no elem can be added to or deleted from the
625c83597faSYonghong Song 	 * local_storage->list by the bpf_prog or by the bpf_map's syscall.
626c83597faSYonghong Song 	 *
627c83597faSYonghong Song 	 * It is racing with bpf_local_storage_map_free() alone
628c83597faSYonghong Song 	 * when unlinking elem from the local_storage->list and
629c83597faSYonghong Song 	 * the map's bucket->list.
630c83597faSYonghong Song 	 */
631c83597faSYonghong Song 	hlist_for_each_entry_safe(selem, n, &local_storage->list, snode) {
632c83597faSYonghong Song 		/* Always unlink from map before unlinking from
633c83597faSYonghong Song 		 * local_storage.
634c83597faSYonghong Song 		 */
635c83597faSYonghong Song 		bpf_selem_unlink_map(selem);
636c83597faSYonghong Song 		/* If local_storage list has only one element, the
637c83597faSYonghong Song 		 * bpf_selem_unlink_storage_nolock() will return true.
638c83597faSYonghong Song 		 * Otherwise, it will return false. The current loop iteration
639c83597faSYonghong Song 		 * intends to remove all local storage. So the last iteration
640c83597faSYonghong Song 		 * of the loop will set the free_cgroup_storage to true.
641c83597faSYonghong Song 		 */
642c83597faSYonghong Song 		free_storage = bpf_selem_unlink_storage_nolock(
643c83597faSYonghong Song 			local_storage, selem, false, false);
644c83597faSYonghong Song 	}
645c83597faSYonghong Song 
646c83597faSYonghong Song 	return free_storage;
647c83597faSYonghong Song }
648c83597faSYonghong Song 
649c83597faSYonghong Song struct bpf_map *
650c83597faSYonghong Song bpf_local_storage_map_alloc(union bpf_attr *attr,
651c83597faSYonghong Song 			    struct bpf_local_storage_cache *cache)
652c83597faSYonghong Song {
653c83597faSYonghong Song 	struct bpf_local_storage_map *smap;
654c83597faSYonghong Song 
655c83597faSYonghong Song 	smap = __bpf_local_storage_map_alloc(attr);
656c83597faSYonghong Song 	if (IS_ERR(smap))
657c83597faSYonghong Song 		return ERR_CAST(smap);
658c83597faSYonghong Song 
659c83597faSYonghong Song 	smap->cache_idx = bpf_local_storage_cache_idx_get(cache);
660c83597faSYonghong Song 	return &smap->map;
661c83597faSYonghong Song }
662c83597faSYonghong Song 
663c83597faSYonghong Song void bpf_local_storage_map_free(struct bpf_map *map,
664c83597faSYonghong Song 				struct bpf_local_storage_cache *cache,
665c83597faSYonghong Song 				int __percpu *busy_counter)
666c83597faSYonghong Song {
667450af8d0SKP Singh 	struct bpf_local_storage_map_bucket *b;
668c83597faSYonghong Song 	struct bpf_local_storage_elem *selem;
669c83597faSYonghong Song 	struct bpf_local_storage_map *smap;
670450af8d0SKP Singh 	unsigned int i;
671450af8d0SKP Singh 
672c83597faSYonghong Song 	smap = (struct bpf_local_storage_map *)map;
673c83597faSYonghong Song 	bpf_local_storage_cache_idx_free(cache, smap->cache_idx);
674c83597faSYonghong Song 
675450af8d0SKP Singh 	/* Note that this map might be concurrently cloned from
676450af8d0SKP Singh 	 * bpf_sk_storage_clone. Wait for any existing bpf_sk_storage_clone
677450af8d0SKP Singh 	 * RCU read section to finish before proceeding. New RCU
678450af8d0SKP Singh 	 * read sections should be prevented via bpf_map_inc_not_zero.
679450af8d0SKP Singh 	 */
680450af8d0SKP Singh 	synchronize_rcu();
681450af8d0SKP Singh 
682450af8d0SKP Singh 	/* bpf prog and the userspace can no longer access this map
683450af8d0SKP Singh 	 * now.  No new selem (of this map) can be added
684450af8d0SKP Singh 	 * to the owner->storage or to the map bucket's list.
685450af8d0SKP Singh 	 *
686450af8d0SKP Singh 	 * The elem of this map can be cleaned up here
687450af8d0SKP Singh 	 * or when the storage is freed e.g.
688450af8d0SKP Singh 	 * by bpf_sk_storage_free() during __sk_destruct().
689450af8d0SKP Singh 	 */
690450af8d0SKP Singh 	for (i = 0; i < (1U << smap->bucket_log); i++) {
691450af8d0SKP Singh 		b = &smap->buckets[i];
692450af8d0SKP Singh 
693450af8d0SKP Singh 		rcu_read_lock();
694450af8d0SKP Singh 		/* No one is adding to b->list now */
695450af8d0SKP Singh 		while ((selem = hlist_entry_safe(
696450af8d0SKP Singh 				rcu_dereference_raw(hlist_first_rcu(&b->list)),
697450af8d0SKP Singh 				struct bpf_local_storage_elem, map_node))) {
698bc235cdbSSong Liu 			if (busy_counter) {
699bc235cdbSSong Liu 				migrate_disable();
700197827a0SHou Tao 				this_cpu_inc(*busy_counter);
701bc235cdbSSong Liu 			}
702dcf456c9SKP Singh 			bpf_selem_unlink(selem, false);
703bc235cdbSSong Liu 			if (busy_counter) {
704197827a0SHou Tao 				this_cpu_dec(*busy_counter);
705bc235cdbSSong Liu 				migrate_enable();
706bc235cdbSSong Liu 			}
707450af8d0SKP Singh 			cond_resched_rcu();
708450af8d0SKP Singh 		}
709450af8d0SKP Singh 		rcu_read_unlock();
710450af8d0SKP Singh 	}
711450af8d0SKP Singh 
712450af8d0SKP Singh 	/* While freeing the storage we may still need to access the map.
713450af8d0SKP Singh 	 *
714450af8d0SKP Singh 	 * e.g. when bpf_sk_storage_free() has unlinked selem from the map
715450af8d0SKP Singh 	 * which then made the above while((selem = ...)) loop
716450af8d0SKP Singh 	 * exit immediately.
717450af8d0SKP Singh 	 *
718450af8d0SKP Singh 	 * However, while freeing the storage one still needs to access the
719450af8d0SKP Singh 	 * smap->elem_size to do the uncharging in
720450af8d0SKP Singh 	 * bpf_selem_unlink_storage_nolock().
721450af8d0SKP Singh 	 *
722450af8d0SKP Singh 	 * Hence, wait another rcu grace period for the storage to be freed.
723450af8d0SKP Singh 	 */
724450af8d0SKP Singh 	synchronize_rcu();
725450af8d0SKP Singh 
726450af8d0SKP Singh 	kvfree(smap->buckets);
72773cf09a3SYafang Shao 	bpf_map_area_free(smap);
728450af8d0SKP Singh }
729