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