bpf_local_storage.c 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600
  1. // SPDX-License-Identifier: GPL-2.0
  2. /* Copyright (c) 2019 Facebook */
  3. #include <linux/rculist.h>
  4. #include <linux/list.h>
  5. #include <linux/hash.h>
  6. #include <linux/types.h>
  7. #include <linux/spinlock.h>
  8. #include <linux/bpf.h>
  9. #include <linux/btf_ids.h>
  10. #include <linux/bpf_local_storage.h>
  11. #include <net/sock.h>
  12. #include <uapi/linux/sock_diag.h>
  13. #include <uapi/linux/btf.h>
  14. #define BPF_LOCAL_STORAGE_CREATE_FLAG_MASK (BPF_F_NO_PREALLOC | BPF_F_CLONE)
  15. static struct bpf_local_storage_map_bucket *
  16. select_bucket(struct bpf_local_storage_map *smap,
  17. struct bpf_local_storage_elem *selem)
  18. {
  19. return &smap->buckets[hash_ptr(selem, smap->bucket_log)];
  20. }
  21. static int mem_charge(struct bpf_local_storage_map *smap, void *owner, u32 size)
  22. {
  23. struct bpf_map *map = &smap->map;
  24. if (!map->ops->map_local_storage_charge)
  25. return 0;
  26. return map->ops->map_local_storage_charge(smap, owner, size);
  27. }
  28. static void mem_uncharge(struct bpf_local_storage_map *smap, void *owner,
  29. u32 size)
  30. {
  31. struct bpf_map *map = &smap->map;
  32. if (map->ops->map_local_storage_uncharge)
  33. map->ops->map_local_storage_uncharge(smap, owner, size);
  34. }
  35. static struct bpf_local_storage __rcu **
  36. owner_storage(struct bpf_local_storage_map *smap, void *owner)
  37. {
  38. struct bpf_map *map = &smap->map;
  39. return map->ops->map_owner_storage_ptr(owner);
  40. }
  41. static bool selem_linked_to_storage(const struct bpf_local_storage_elem *selem)
  42. {
  43. return !hlist_unhashed(&selem->snode);
  44. }
  45. static bool selem_linked_to_map(const struct bpf_local_storage_elem *selem)
  46. {
  47. return !hlist_unhashed(&selem->map_node);
  48. }
  49. struct bpf_local_storage_elem *
  50. bpf_selem_alloc(struct bpf_local_storage_map *smap, void *owner,
  51. void *value, bool charge_mem)
  52. {
  53. struct bpf_local_storage_elem *selem;
  54. if (charge_mem && mem_charge(smap, owner, smap->elem_size))
  55. return NULL;
  56. selem = kzalloc(smap->elem_size, GFP_ATOMIC | __GFP_NOWARN);
  57. if (selem) {
  58. if (value)
  59. memcpy(SDATA(selem)->data, value, smap->map.value_size);
  60. return selem;
  61. }
  62. if (charge_mem)
  63. mem_uncharge(smap, owner, smap->elem_size);
  64. return NULL;
  65. }
  66. /* local_storage->lock must be held and selem->local_storage == local_storage.
  67. * The caller must ensure selem->smap is still valid to be
  68. * dereferenced for its smap->elem_size and smap->cache_idx.
  69. */
  70. bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
  71. struct bpf_local_storage_elem *selem,
  72. bool uncharge_mem)
  73. {
  74. struct bpf_local_storage_map *smap;
  75. bool free_local_storage;
  76. void *owner;
  77. smap = rcu_dereference(SDATA(selem)->smap);
  78. owner = local_storage->owner;
  79. /* All uncharging on the owner must be done first.
  80. * The owner may be freed once the last selem is unlinked
  81. * from local_storage.
  82. */
  83. if (uncharge_mem)
  84. mem_uncharge(smap, owner, smap->elem_size);
  85. free_local_storage = hlist_is_singular_node(&selem->snode,
  86. &local_storage->list);
  87. if (free_local_storage) {
  88. mem_uncharge(smap, owner, sizeof(struct bpf_local_storage));
  89. local_storage->owner = NULL;
  90. /* After this RCU_INIT, owner may be freed and cannot be used */
  91. RCU_INIT_POINTER(*owner_storage(smap, owner), NULL);
  92. /* local_storage is not freed now. local_storage->lock is
  93. * still held and raw_spin_unlock_bh(&local_storage->lock)
  94. * will be done by the caller.
  95. *
  96. * Although the unlock will be done under
  97. * rcu_read_lock(), it is more intutivie to
  98. * read if kfree_rcu(local_storage, rcu) is done
  99. * after the raw_spin_unlock_bh(&local_storage->lock).
  100. *
  101. * Hence, a "bool free_local_storage" is returned
  102. * to the caller which then calls the kfree_rcu()
  103. * after unlock.
  104. */
  105. }
  106. hlist_del_init_rcu(&selem->snode);
  107. if (rcu_access_pointer(local_storage->cache[smap->cache_idx]) ==
  108. SDATA(selem))
  109. RCU_INIT_POINTER(local_storage->cache[smap->cache_idx], NULL);
  110. kfree_rcu(selem, rcu);
  111. return free_local_storage;
  112. }
  113. static void __bpf_selem_unlink_storage(struct bpf_local_storage_elem *selem)
  114. {
  115. struct bpf_local_storage *local_storage;
  116. bool free_local_storage = false;
  117. if (unlikely(!selem_linked_to_storage(selem)))
  118. /* selem has already been unlinked from sk */
  119. return;
  120. local_storage = rcu_dereference(selem->local_storage);
  121. raw_spin_lock_bh(&local_storage->lock);
  122. if (likely(selem_linked_to_storage(selem)))
  123. free_local_storage = bpf_selem_unlink_storage_nolock(
  124. local_storage, selem, true);
  125. raw_spin_unlock_bh(&local_storage->lock);
  126. if (free_local_storage)
  127. kfree_rcu(local_storage, rcu);
  128. }
  129. void bpf_selem_link_storage_nolock(struct bpf_local_storage *local_storage,
  130. struct bpf_local_storage_elem *selem)
  131. {
  132. RCU_INIT_POINTER(selem->local_storage, local_storage);
  133. hlist_add_head_rcu(&selem->snode, &local_storage->list);
  134. }
  135. void bpf_selem_unlink_map(struct bpf_local_storage_elem *selem)
  136. {
  137. struct bpf_local_storage_map *smap;
  138. struct bpf_local_storage_map_bucket *b;
  139. if (unlikely(!selem_linked_to_map(selem)))
  140. /* selem has already be unlinked from smap */
  141. return;
  142. smap = rcu_dereference(SDATA(selem)->smap);
  143. b = select_bucket(smap, selem);
  144. raw_spin_lock_bh(&b->lock);
  145. if (likely(selem_linked_to_map(selem)))
  146. hlist_del_init_rcu(&selem->map_node);
  147. raw_spin_unlock_bh(&b->lock);
  148. }
  149. void bpf_selem_link_map(struct bpf_local_storage_map *smap,
  150. struct bpf_local_storage_elem *selem)
  151. {
  152. struct bpf_local_storage_map_bucket *b = select_bucket(smap, selem);
  153. raw_spin_lock_bh(&b->lock);
  154. RCU_INIT_POINTER(SDATA(selem)->smap, smap);
  155. hlist_add_head_rcu(&selem->map_node, &b->list);
  156. raw_spin_unlock_bh(&b->lock);
  157. }
  158. void bpf_selem_unlink(struct bpf_local_storage_elem *selem)
  159. {
  160. /* Always unlink from map before unlinking from local_storage
  161. * because selem will be freed after successfully unlinked from
  162. * the local_storage.
  163. */
  164. bpf_selem_unlink_map(selem);
  165. __bpf_selem_unlink_storage(selem);
  166. }
  167. struct bpf_local_storage_data *
  168. bpf_local_storage_lookup(struct bpf_local_storage *local_storage,
  169. struct bpf_local_storage_map *smap,
  170. bool cacheit_lockit)
  171. {
  172. struct bpf_local_storage_data *sdata;
  173. struct bpf_local_storage_elem *selem;
  174. /* Fast path (cache hit) */
  175. sdata = rcu_dereference(local_storage->cache[smap->cache_idx]);
  176. if (sdata && rcu_access_pointer(sdata->smap) == smap)
  177. return sdata;
  178. /* Slow path (cache miss) */
  179. hlist_for_each_entry_rcu(selem, &local_storage->list, snode)
  180. if (rcu_access_pointer(SDATA(selem)->smap) == smap)
  181. break;
  182. if (!selem)
  183. return NULL;
  184. sdata = SDATA(selem);
  185. if (cacheit_lockit) {
  186. /* spinlock is needed to avoid racing with the
  187. * parallel delete. Otherwise, publishing an already
  188. * deleted sdata to the cache will become a use-after-free
  189. * problem in the next bpf_local_storage_lookup().
  190. */
  191. raw_spin_lock_bh(&local_storage->lock);
  192. if (selem_linked_to_storage(selem))
  193. rcu_assign_pointer(local_storage->cache[smap->cache_idx],
  194. sdata);
  195. raw_spin_unlock_bh(&local_storage->lock);
  196. }
  197. return sdata;
  198. }
  199. static int check_flags(const struct bpf_local_storage_data *old_sdata,
  200. u64 map_flags)
  201. {
  202. if (old_sdata && (map_flags & ~BPF_F_LOCK) == BPF_NOEXIST)
  203. /* elem already exists */
  204. return -EEXIST;
  205. if (!old_sdata && (map_flags & ~BPF_F_LOCK) == BPF_EXIST)
  206. /* elem doesn't exist, cannot update it */
  207. return -ENOENT;
  208. return 0;
  209. }
  210. int bpf_local_storage_alloc(void *owner,
  211. struct bpf_local_storage_map *smap,
  212. struct bpf_local_storage_elem *first_selem)
  213. {
  214. struct bpf_local_storage *prev_storage, *storage;
  215. struct bpf_local_storage **owner_storage_ptr;
  216. int err;
  217. err = mem_charge(smap, owner, sizeof(*storage));
  218. if (err)
  219. return err;
  220. storage = kzalloc(sizeof(*storage), GFP_ATOMIC | __GFP_NOWARN);
  221. if (!storage) {
  222. err = -ENOMEM;
  223. goto uncharge;
  224. }
  225. INIT_HLIST_HEAD(&storage->list);
  226. raw_spin_lock_init(&storage->lock);
  227. storage->owner = owner;
  228. bpf_selem_link_storage_nolock(storage, first_selem);
  229. bpf_selem_link_map(smap, first_selem);
  230. owner_storage_ptr =
  231. (struct bpf_local_storage **)owner_storage(smap, owner);
  232. /* Publish storage to the owner.
  233. * Instead of using any lock of the kernel object (i.e. owner),
  234. * cmpxchg will work with any kernel object regardless what
  235. * the running context is, bh, irq...etc.
  236. *
  237. * From now on, the owner->storage pointer (e.g. sk->sk_bpf_storage)
  238. * is protected by the storage->lock. Hence, when freeing
  239. * the owner->storage, the storage->lock must be held before
  240. * setting owner->storage ptr to NULL.
  241. */
  242. prev_storage = cmpxchg(owner_storage_ptr, NULL, storage);
  243. if (unlikely(prev_storage)) {
  244. bpf_selem_unlink_map(first_selem);
  245. err = -EAGAIN;
  246. goto uncharge;
  247. /* Note that even first_selem was linked to smap's
  248. * bucket->list, first_selem can be freed immediately
  249. * (instead of kfree_rcu) because
  250. * bpf_local_storage_map_free() does a
  251. * synchronize_rcu() before walking the bucket->list.
  252. * Hence, no one is accessing selem from the
  253. * bucket->list under rcu_read_lock().
  254. */
  255. }
  256. return 0;
  257. uncharge:
  258. kfree(storage);
  259. mem_uncharge(smap, owner, sizeof(*storage));
  260. return err;
  261. }
  262. /* sk cannot be going away because it is linking new elem
  263. * to sk->sk_bpf_storage. (i.e. sk->sk_refcnt cannot be 0).
  264. * Otherwise, it will become a leak (and other memory issues
  265. * during map destruction).
  266. */
  267. struct bpf_local_storage_data *
  268. bpf_local_storage_update(void *owner, struct bpf_local_storage_map *smap,
  269. void *value, u64 map_flags)
  270. {
  271. struct bpf_local_storage_data *old_sdata = NULL;
  272. struct bpf_local_storage_elem *selem;
  273. struct bpf_local_storage *local_storage;
  274. int err;
  275. /* BPF_EXIST and BPF_NOEXIST cannot be both set */
  276. if (unlikely((map_flags & ~BPF_F_LOCK) > BPF_EXIST) ||
  277. /* BPF_F_LOCK can only be used in a value with spin_lock */
  278. unlikely((map_flags & BPF_F_LOCK) &&
  279. !map_value_has_spin_lock(&smap->map)))
  280. return ERR_PTR(-EINVAL);
  281. local_storage = rcu_dereference(*owner_storage(smap, owner));
  282. if (!local_storage || hlist_empty(&local_storage->list)) {
  283. /* Very first elem for the owner */
  284. err = check_flags(NULL, map_flags);
  285. if (err)
  286. return ERR_PTR(err);
  287. selem = bpf_selem_alloc(smap, owner, value, true);
  288. if (!selem)
  289. return ERR_PTR(-ENOMEM);
  290. err = bpf_local_storage_alloc(owner, smap, selem);
  291. if (err) {
  292. kfree(selem);
  293. mem_uncharge(smap, owner, smap->elem_size);
  294. return ERR_PTR(err);
  295. }
  296. return SDATA(selem);
  297. }
  298. if ((map_flags & BPF_F_LOCK) && !(map_flags & BPF_NOEXIST)) {
  299. /* Hoping to find an old_sdata to do inline update
  300. * such that it can avoid taking the local_storage->lock
  301. * and changing the lists.
  302. */
  303. old_sdata =
  304. bpf_local_storage_lookup(local_storage, smap, false);
  305. err = check_flags(old_sdata, map_flags);
  306. if (err)
  307. return ERR_PTR(err);
  308. if (old_sdata && selem_linked_to_storage(SELEM(old_sdata))) {
  309. copy_map_value_locked(&smap->map, old_sdata->data,
  310. value, false);
  311. return old_sdata;
  312. }
  313. }
  314. raw_spin_lock_bh(&local_storage->lock);
  315. /* Recheck local_storage->list under local_storage->lock */
  316. if (unlikely(hlist_empty(&local_storage->list))) {
  317. /* A parallel del is happening and local_storage is going
  318. * away. It has just been checked before, so very
  319. * unlikely. Return instead of retry to keep things
  320. * simple.
  321. */
  322. err = -EAGAIN;
  323. goto unlock_err;
  324. }
  325. old_sdata = bpf_local_storage_lookup(local_storage, smap, false);
  326. err = check_flags(old_sdata, map_flags);
  327. if (err)
  328. goto unlock_err;
  329. if (old_sdata && (map_flags & BPF_F_LOCK)) {
  330. copy_map_value_locked(&smap->map, old_sdata->data, value,
  331. false);
  332. selem = SELEM(old_sdata);
  333. goto unlock;
  334. }
  335. /* local_storage->lock is held. Hence, we are sure
  336. * we can unlink and uncharge the old_sdata successfully
  337. * later. Hence, instead of charging the new selem now
  338. * and then uncharge the old selem later (which may cause
  339. * a potential but unnecessary charge failure), avoid taking
  340. * a charge at all here (the "!old_sdata" check) and the
  341. * old_sdata will not be uncharged later during
  342. * bpf_selem_unlink_storage_nolock().
  343. */
  344. selem = bpf_selem_alloc(smap, owner, value, !old_sdata);
  345. if (!selem) {
  346. err = -ENOMEM;
  347. goto unlock_err;
  348. }
  349. /* First, link the new selem to the map */
  350. bpf_selem_link_map(smap, selem);
  351. /* Second, link (and publish) the new selem to local_storage */
  352. bpf_selem_link_storage_nolock(local_storage, selem);
  353. /* Third, remove old selem, SELEM(old_sdata) */
  354. if (old_sdata) {
  355. bpf_selem_unlink_map(SELEM(old_sdata));
  356. bpf_selem_unlink_storage_nolock(local_storage, SELEM(old_sdata),
  357. false);
  358. }
  359. unlock:
  360. raw_spin_unlock_bh(&local_storage->lock);
  361. return SDATA(selem);
  362. unlock_err:
  363. raw_spin_unlock_bh(&local_storage->lock);
  364. return ERR_PTR(err);
  365. }
  366. u16 bpf_local_storage_cache_idx_get(struct bpf_local_storage_cache *cache)
  367. {
  368. u64 min_usage = U64_MAX;
  369. u16 i, res = 0;
  370. spin_lock(&cache->idx_lock);
  371. for (i = 0; i < BPF_LOCAL_STORAGE_CACHE_SIZE; i++) {
  372. if (cache->idx_usage_counts[i] < min_usage) {
  373. min_usage = cache->idx_usage_counts[i];
  374. res = i;
  375. /* Found a free cache_idx */
  376. if (!min_usage)
  377. break;
  378. }
  379. }
  380. cache->idx_usage_counts[res]++;
  381. spin_unlock(&cache->idx_lock);
  382. return res;
  383. }
  384. void bpf_local_storage_cache_idx_free(struct bpf_local_storage_cache *cache,
  385. u16 idx)
  386. {
  387. spin_lock(&cache->idx_lock);
  388. cache->idx_usage_counts[idx]--;
  389. spin_unlock(&cache->idx_lock);
  390. }
  391. void bpf_local_storage_map_free(struct bpf_local_storage_map *smap)
  392. {
  393. struct bpf_local_storage_elem *selem;
  394. struct bpf_local_storage_map_bucket *b;
  395. unsigned int i;
  396. /* Note that this map might be concurrently cloned from
  397. * bpf_sk_storage_clone. Wait for any existing bpf_sk_storage_clone
  398. * RCU read section to finish before proceeding. New RCU
  399. * read sections should be prevented via bpf_map_inc_not_zero.
  400. */
  401. synchronize_rcu();
  402. /* bpf prog and the userspace can no longer access this map
  403. * now. No new selem (of this map) can be added
  404. * to the owner->storage or to the map bucket's list.
  405. *
  406. * The elem of this map can be cleaned up here
  407. * or when the storage is freed e.g.
  408. * by bpf_sk_storage_free() during __sk_destruct().
  409. */
  410. for (i = 0; i < (1U << smap->bucket_log); i++) {
  411. b = &smap->buckets[i];
  412. rcu_read_lock();
  413. /* No one is adding to b->list now */
  414. while ((selem = hlist_entry_safe(
  415. rcu_dereference_raw(hlist_first_rcu(&b->list)),
  416. struct bpf_local_storage_elem, map_node))) {
  417. bpf_selem_unlink(selem);
  418. cond_resched_rcu();
  419. }
  420. rcu_read_unlock();
  421. }
  422. /* While freeing the storage we may still need to access the map.
  423. *
  424. * e.g. when bpf_sk_storage_free() has unlinked selem from the map
  425. * which then made the above while((selem = ...)) loop
  426. * exit immediately.
  427. *
  428. * However, while freeing the storage one still needs to access the
  429. * smap->elem_size to do the uncharging in
  430. * bpf_selem_unlink_storage_nolock().
  431. *
  432. * Hence, wait another rcu grace period for the storage to be freed.
  433. */
  434. synchronize_rcu();
  435. kvfree(smap->buckets);
  436. kfree(smap);
  437. }
  438. int bpf_local_storage_map_alloc_check(union bpf_attr *attr)
  439. {
  440. if (attr->map_flags & ~BPF_LOCAL_STORAGE_CREATE_FLAG_MASK ||
  441. !(attr->map_flags & BPF_F_NO_PREALLOC) ||
  442. attr->max_entries ||
  443. attr->key_size != sizeof(int) || !attr->value_size ||
  444. /* Enforce BTF for userspace sk dumping */
  445. !attr->btf_key_type_id || !attr->btf_value_type_id)
  446. return -EINVAL;
  447. if (!bpf_capable())
  448. return -EPERM;
  449. if (attr->value_size > BPF_LOCAL_STORAGE_MAX_VALUE_SIZE)
  450. return -E2BIG;
  451. return 0;
  452. }
  453. struct bpf_local_storage_map *bpf_local_storage_map_alloc(union bpf_attr *attr)
  454. {
  455. struct bpf_local_storage_map *smap;
  456. unsigned int i;
  457. u32 nbuckets;
  458. u64 cost;
  459. int ret;
  460. smap = kzalloc(sizeof(*smap), GFP_USER | __GFP_NOWARN);
  461. if (!smap)
  462. return ERR_PTR(-ENOMEM);
  463. bpf_map_init_from_attr(&smap->map, attr);
  464. nbuckets = roundup_pow_of_two(num_possible_cpus());
  465. /* Use at least 2 buckets, select_bucket() is undefined behavior with 1 bucket */
  466. nbuckets = max_t(u32, 2, nbuckets);
  467. smap->bucket_log = ilog2(nbuckets);
  468. cost = sizeof(*smap->buckets) * nbuckets + sizeof(*smap);
  469. ret = bpf_map_charge_init(&smap->map.memory, cost);
  470. if (ret < 0) {
  471. kfree(smap);
  472. return ERR_PTR(ret);
  473. }
  474. smap->buckets = kvcalloc(sizeof(*smap->buckets), nbuckets,
  475. GFP_USER | __GFP_NOWARN);
  476. if (!smap->buckets) {
  477. bpf_map_charge_finish(&smap->map.memory);
  478. kfree(smap);
  479. return ERR_PTR(-ENOMEM);
  480. }
  481. for (i = 0; i < nbuckets; i++) {
  482. INIT_HLIST_HEAD(&smap->buckets[i].list);
  483. raw_spin_lock_init(&smap->buckets[i].lock);
  484. }
  485. smap->elem_size =
  486. sizeof(struct bpf_local_storage_elem) + attr->value_size;
  487. return smap;
  488. }
  489. int bpf_local_storage_map_check_btf(const struct bpf_map *map,
  490. const struct btf *btf,
  491. const struct btf_type *key_type,
  492. const struct btf_type *value_type)
  493. {
  494. u32 int_data;
  495. if (BTF_INFO_KIND(key_type->info) != BTF_KIND_INT)
  496. return -EINVAL;
  497. int_data = *(u32 *)(key_type + 1);
  498. if (BTF_INT_BITS(int_data) != 32 || BTF_INT_OFFSET(int_data))
  499. return -EINVAL;
  500. return 0;
  501. }