bpf_local_storage.h

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