17c8199e2SAlexei Starovoitov // SPDX-License-Identifier: GPL-2.0-only 27c8199e2SAlexei Starovoitov /* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ 37c8199e2SAlexei Starovoitov #include <linux/mm.h> 47c8199e2SAlexei Starovoitov #include <linux/llist.h> 57c8199e2SAlexei Starovoitov #include <linux/bpf.h> 67c8199e2SAlexei Starovoitov #include <linux/irq_work.h> 77c8199e2SAlexei Starovoitov #include <linux/bpf_mem_alloc.h> 87c8199e2SAlexei Starovoitov #include <linux/memcontrol.h> 97c8199e2SAlexei Starovoitov #include <asm/local.h> 107c8199e2SAlexei Starovoitov 117c8199e2SAlexei Starovoitov /* Any context (including NMI) BPF specific memory allocator. 127c8199e2SAlexei Starovoitov * 137c8199e2SAlexei Starovoitov * Tracing BPF programs can attach to kprobe and fentry. Hence they 147c8199e2SAlexei Starovoitov * run in unknown context where calling plain kmalloc() might not be safe. 157c8199e2SAlexei Starovoitov * 167c8199e2SAlexei Starovoitov * Front-end kmalloc() with per-cpu per-bucket cache of free elements. 177c8199e2SAlexei Starovoitov * Refill this cache asynchronously from irq_work. 187c8199e2SAlexei Starovoitov * 197c8199e2SAlexei Starovoitov * CPU_0 buckets 207c8199e2SAlexei Starovoitov * 16 32 64 96 128 196 256 512 1024 2048 4096 217c8199e2SAlexei Starovoitov * ... 227c8199e2SAlexei Starovoitov * CPU_N buckets 237c8199e2SAlexei Starovoitov * 16 32 64 96 128 196 256 512 1024 2048 4096 247c8199e2SAlexei Starovoitov * 257c8199e2SAlexei Starovoitov * The buckets are prefilled at the start. 267c8199e2SAlexei Starovoitov * BPF programs always run with migration disabled. 277c8199e2SAlexei Starovoitov * It's safe to allocate from cache of the current cpu with irqs disabled. 287c8199e2SAlexei Starovoitov * Free-ing is always done into bucket of the current cpu as well. 297c8199e2SAlexei Starovoitov * irq_work trims extra free elements from buckets with kfree 307c8199e2SAlexei Starovoitov * and refills them with kmalloc, so global kmalloc logic takes care 317c8199e2SAlexei Starovoitov * of freeing objects allocated by one cpu and freed on another. 327c8199e2SAlexei Starovoitov * 337c8199e2SAlexei Starovoitov * Every allocated objected is padded with extra 8 bytes that contains 347c8199e2SAlexei Starovoitov * struct llist_node. 357c8199e2SAlexei Starovoitov */ 367c8199e2SAlexei Starovoitov #define LLIST_NODE_SZ sizeof(struct llist_node) 377c8199e2SAlexei Starovoitov 387c8199e2SAlexei Starovoitov /* similar to kmalloc, but sizeof == 8 bucket is gone */ 397c8199e2SAlexei Starovoitov static u8 size_index[24] __ro_after_init = { 407c8199e2SAlexei Starovoitov 3, /* 8 */ 417c8199e2SAlexei Starovoitov 3, /* 16 */ 427c8199e2SAlexei Starovoitov 4, /* 24 */ 437c8199e2SAlexei Starovoitov 4, /* 32 */ 447c8199e2SAlexei Starovoitov 5, /* 40 */ 457c8199e2SAlexei Starovoitov 5, /* 48 */ 467c8199e2SAlexei Starovoitov 5, /* 56 */ 477c8199e2SAlexei Starovoitov 5, /* 64 */ 487c8199e2SAlexei Starovoitov 1, /* 72 */ 497c8199e2SAlexei Starovoitov 1, /* 80 */ 507c8199e2SAlexei Starovoitov 1, /* 88 */ 517c8199e2SAlexei Starovoitov 1, /* 96 */ 527c8199e2SAlexei Starovoitov 6, /* 104 */ 537c8199e2SAlexei Starovoitov 6, /* 112 */ 547c8199e2SAlexei Starovoitov 6, /* 120 */ 557c8199e2SAlexei Starovoitov 6, /* 128 */ 567c8199e2SAlexei Starovoitov 2, /* 136 */ 577c8199e2SAlexei Starovoitov 2, /* 144 */ 587c8199e2SAlexei Starovoitov 2, /* 152 */ 597c8199e2SAlexei Starovoitov 2, /* 160 */ 607c8199e2SAlexei Starovoitov 2, /* 168 */ 617c8199e2SAlexei Starovoitov 2, /* 176 */ 627c8199e2SAlexei Starovoitov 2, /* 184 */ 637c8199e2SAlexei Starovoitov 2 /* 192 */ 647c8199e2SAlexei Starovoitov }; 657c8199e2SAlexei Starovoitov 667c8199e2SAlexei Starovoitov static int bpf_mem_cache_idx(size_t size) 677c8199e2SAlexei Starovoitov { 687c8199e2SAlexei Starovoitov if (!size || size > 4096) 697c8199e2SAlexei Starovoitov return -1; 707c8199e2SAlexei Starovoitov 717c8199e2SAlexei Starovoitov if (size <= 192) 727c8199e2SAlexei Starovoitov return size_index[(size - 1) / 8] - 1; 737c8199e2SAlexei Starovoitov 747c8199e2SAlexei Starovoitov return fls(size - 1) - 1; 757c8199e2SAlexei Starovoitov } 767c8199e2SAlexei Starovoitov 777c8199e2SAlexei Starovoitov #define NUM_CACHES 11 787c8199e2SAlexei Starovoitov 797c8199e2SAlexei Starovoitov struct bpf_mem_cache { 807c8199e2SAlexei Starovoitov /* per-cpu list of free objects of size 'unit_size'. 817c8199e2SAlexei Starovoitov * All accesses are done with interrupts disabled and 'active' counter 827c8199e2SAlexei Starovoitov * protection with __llist_add() and __llist_del_first(). 837c8199e2SAlexei Starovoitov */ 847c8199e2SAlexei Starovoitov struct llist_head free_llist; 857c8199e2SAlexei Starovoitov local_t active; 867c8199e2SAlexei Starovoitov 877c8199e2SAlexei Starovoitov /* Operations on the free_list from unit_alloc/unit_free/bpf_mem_refill 887c8199e2SAlexei Starovoitov * are sequenced by per-cpu 'active' counter. But unit_free() cannot 897c8199e2SAlexei Starovoitov * fail. When 'active' is busy the unit_free() will add an object to 907c8199e2SAlexei Starovoitov * free_llist_extra. 917c8199e2SAlexei Starovoitov */ 927c8199e2SAlexei Starovoitov struct llist_head free_llist_extra; 937c8199e2SAlexei Starovoitov 947c8199e2SAlexei Starovoitov struct irq_work refill_work; 957c8199e2SAlexei Starovoitov struct obj_cgroup *objcg; 967c8199e2SAlexei Starovoitov int unit_size; 977c8199e2SAlexei Starovoitov /* count of objects in free_llist */ 987c8199e2SAlexei Starovoitov int free_cnt; 997c266178SAlexei Starovoitov int low_watermark, high_watermark, batch; 100bfc03c15SAlexei Starovoitov int percpu_size; 1018d5a8011SAlexei Starovoitov 1028d5a8011SAlexei Starovoitov struct rcu_head rcu; 1038d5a8011SAlexei Starovoitov struct llist_head free_by_rcu; 1048d5a8011SAlexei Starovoitov struct llist_head waiting_for_gp; 1058d5a8011SAlexei Starovoitov atomic_t call_rcu_in_progress; 1067c8199e2SAlexei Starovoitov }; 1077c8199e2SAlexei Starovoitov 1087c8199e2SAlexei Starovoitov struct bpf_mem_caches { 1097c8199e2SAlexei Starovoitov struct bpf_mem_cache cache[NUM_CACHES]; 1107c8199e2SAlexei Starovoitov }; 1117c8199e2SAlexei Starovoitov 1127c8199e2SAlexei Starovoitov static struct llist_node notrace *__llist_del_first(struct llist_head *head) 1137c8199e2SAlexei Starovoitov { 1147c8199e2SAlexei Starovoitov struct llist_node *entry, *next; 1157c8199e2SAlexei Starovoitov 1167c8199e2SAlexei Starovoitov entry = head->first; 1177c8199e2SAlexei Starovoitov if (!entry) 1187c8199e2SAlexei Starovoitov return NULL; 1197c8199e2SAlexei Starovoitov next = entry->next; 1207c8199e2SAlexei Starovoitov head->first = next; 1217c8199e2SAlexei Starovoitov return entry; 1227c8199e2SAlexei Starovoitov } 1237c8199e2SAlexei Starovoitov 1247c8199e2SAlexei Starovoitov static void *__alloc(struct bpf_mem_cache *c, int node) 1257c8199e2SAlexei Starovoitov { 1267c8199e2SAlexei Starovoitov /* Allocate, but don't deplete atomic reserves that typical 1277c8199e2SAlexei Starovoitov * GFP_ATOMIC would do. irq_work runs on this cpu and kmalloc 1287c8199e2SAlexei Starovoitov * will allocate from the current numa node which is what we 1297c8199e2SAlexei Starovoitov * want here. 1307c8199e2SAlexei Starovoitov */ 1317c8199e2SAlexei Starovoitov gfp_t flags = GFP_NOWAIT | __GFP_NOWARN | __GFP_ACCOUNT; 1327c8199e2SAlexei Starovoitov 133bfc03c15SAlexei Starovoitov if (c->percpu_size) { 134bfc03c15SAlexei Starovoitov void **obj = kmalloc_node(c->percpu_size, flags, node); 1354ab67149SAlexei Starovoitov void *pptr = __alloc_percpu_gfp(c->unit_size, 8, flags); 1364ab67149SAlexei Starovoitov 1374ab67149SAlexei Starovoitov if (!obj || !pptr) { 1384ab67149SAlexei Starovoitov free_percpu(pptr); 1394ab67149SAlexei Starovoitov kfree(obj); 1404ab67149SAlexei Starovoitov return NULL; 1414ab67149SAlexei Starovoitov } 1424ab67149SAlexei Starovoitov obj[1] = pptr; 1434ab67149SAlexei Starovoitov return obj; 1444ab67149SAlexei Starovoitov } 1454ab67149SAlexei Starovoitov 1467c8199e2SAlexei Starovoitov return kmalloc_node(c->unit_size, flags, node); 1477c8199e2SAlexei Starovoitov } 1487c8199e2SAlexei Starovoitov 1497c8199e2SAlexei Starovoitov static struct mem_cgroup *get_memcg(const struct bpf_mem_cache *c) 1507c8199e2SAlexei Starovoitov { 1517c8199e2SAlexei Starovoitov #ifdef CONFIG_MEMCG_KMEM 1527c8199e2SAlexei Starovoitov if (c->objcg) 1537c8199e2SAlexei Starovoitov return get_mem_cgroup_from_objcg(c->objcg); 1547c8199e2SAlexei Starovoitov #endif 1557c8199e2SAlexei Starovoitov 1567c8199e2SAlexei Starovoitov #ifdef CONFIG_MEMCG 1577c8199e2SAlexei Starovoitov return root_mem_cgroup; 1587c8199e2SAlexei Starovoitov #else 1597c8199e2SAlexei Starovoitov return NULL; 1607c8199e2SAlexei Starovoitov #endif 1617c8199e2SAlexei Starovoitov } 1627c8199e2SAlexei Starovoitov 1637c8199e2SAlexei Starovoitov /* Mostly runs from irq_work except __init phase. */ 1647c8199e2SAlexei Starovoitov static void alloc_bulk(struct bpf_mem_cache *c, int cnt, int node) 1657c8199e2SAlexei Starovoitov { 1667c8199e2SAlexei Starovoitov struct mem_cgroup *memcg = NULL, *old_memcg; 1677c8199e2SAlexei Starovoitov unsigned long flags; 1687c8199e2SAlexei Starovoitov void *obj; 1697c8199e2SAlexei Starovoitov int i; 1707c8199e2SAlexei Starovoitov 1717c8199e2SAlexei Starovoitov memcg = get_memcg(c); 1727c8199e2SAlexei Starovoitov old_memcg = set_active_memcg(memcg); 1737c8199e2SAlexei Starovoitov for (i = 0; i < cnt; i++) { 1747c8199e2SAlexei Starovoitov obj = __alloc(c, node); 1757c8199e2SAlexei Starovoitov if (!obj) 1767c8199e2SAlexei Starovoitov break; 1777c8199e2SAlexei Starovoitov if (IS_ENABLED(CONFIG_PREEMPT_RT)) 1787c8199e2SAlexei Starovoitov /* In RT irq_work runs in per-cpu kthread, so disable 1797c8199e2SAlexei Starovoitov * interrupts to avoid preemption and interrupts and 1807c8199e2SAlexei Starovoitov * reduce the chance of bpf prog executing on this cpu 1817c8199e2SAlexei Starovoitov * when active counter is busy. 1827c8199e2SAlexei Starovoitov */ 1837c8199e2SAlexei Starovoitov local_irq_save(flags); 1847c8199e2SAlexei Starovoitov /* alloc_bulk runs from irq_work which will not preempt a bpf 1857c8199e2SAlexei Starovoitov * program that does unit_alloc/unit_free since IRQs are 1867c8199e2SAlexei Starovoitov * disabled there. There is no race to increment 'active' 1877c8199e2SAlexei Starovoitov * counter. It protects free_llist from corruption in case NMI 1887c8199e2SAlexei Starovoitov * bpf prog preempted this loop. 1897c8199e2SAlexei Starovoitov */ 1907c8199e2SAlexei Starovoitov WARN_ON_ONCE(local_inc_return(&c->active) != 1); 1917c8199e2SAlexei Starovoitov __llist_add(obj, &c->free_llist); 1927c8199e2SAlexei Starovoitov c->free_cnt++; 1937c8199e2SAlexei Starovoitov local_dec(&c->active); 1947c8199e2SAlexei Starovoitov if (IS_ENABLED(CONFIG_PREEMPT_RT)) 1957c8199e2SAlexei Starovoitov local_irq_restore(flags); 1967c8199e2SAlexei Starovoitov } 1977c8199e2SAlexei Starovoitov set_active_memcg(old_memcg); 1987c8199e2SAlexei Starovoitov mem_cgroup_put(memcg); 1997c8199e2SAlexei Starovoitov } 2007c8199e2SAlexei Starovoitov 2017c8199e2SAlexei Starovoitov static void free_one(struct bpf_mem_cache *c, void *obj) 2027c8199e2SAlexei Starovoitov { 203bfc03c15SAlexei Starovoitov if (c->percpu_size) { 2044ab67149SAlexei Starovoitov free_percpu(((void **)obj)[1]); 205bfc03c15SAlexei Starovoitov kfree(obj); 2064ab67149SAlexei Starovoitov return; 2074ab67149SAlexei Starovoitov } 2084ab67149SAlexei Starovoitov 2097c8199e2SAlexei Starovoitov kfree(obj); 2107c8199e2SAlexei Starovoitov } 2117c8199e2SAlexei Starovoitov 2128d5a8011SAlexei Starovoitov static void __free_rcu(struct rcu_head *head) 2138d5a8011SAlexei Starovoitov { 2148d5a8011SAlexei Starovoitov struct bpf_mem_cache *c = container_of(head, struct bpf_mem_cache, rcu); 2158d5a8011SAlexei Starovoitov struct llist_node *llnode = llist_del_all(&c->waiting_for_gp); 2168d5a8011SAlexei Starovoitov struct llist_node *pos, *t; 2178d5a8011SAlexei Starovoitov 2188d5a8011SAlexei Starovoitov llist_for_each_safe(pos, t, llnode) 2198d5a8011SAlexei Starovoitov free_one(c, pos); 2208d5a8011SAlexei Starovoitov atomic_set(&c->call_rcu_in_progress, 0); 2218d5a8011SAlexei Starovoitov } 2228d5a8011SAlexei Starovoitov 223dccb4a90SAlexei Starovoitov static void __free_rcu_tasks_trace(struct rcu_head *head) 224dccb4a90SAlexei Starovoitov { 225dccb4a90SAlexei Starovoitov struct bpf_mem_cache *c = container_of(head, struct bpf_mem_cache, rcu); 226dccb4a90SAlexei Starovoitov 227dccb4a90SAlexei Starovoitov call_rcu(&c->rcu, __free_rcu); 228dccb4a90SAlexei Starovoitov } 229dccb4a90SAlexei Starovoitov 2308d5a8011SAlexei Starovoitov static void enque_to_free(struct bpf_mem_cache *c, void *obj) 2318d5a8011SAlexei Starovoitov { 2328d5a8011SAlexei Starovoitov struct llist_node *llnode = obj; 2338d5a8011SAlexei Starovoitov 2348d5a8011SAlexei Starovoitov /* bpf_mem_cache is a per-cpu object. Freeing happens in irq_work. 2358d5a8011SAlexei Starovoitov * Nothing races to add to free_by_rcu list. 2368d5a8011SAlexei Starovoitov */ 2378d5a8011SAlexei Starovoitov __llist_add(llnode, &c->free_by_rcu); 2388d5a8011SAlexei Starovoitov } 2398d5a8011SAlexei Starovoitov 2408d5a8011SAlexei Starovoitov static void do_call_rcu(struct bpf_mem_cache *c) 2418d5a8011SAlexei Starovoitov { 2428d5a8011SAlexei Starovoitov struct llist_node *llnode, *t; 2438d5a8011SAlexei Starovoitov 2448d5a8011SAlexei Starovoitov if (atomic_xchg(&c->call_rcu_in_progress, 1)) 2458d5a8011SAlexei Starovoitov return; 2468d5a8011SAlexei Starovoitov 2478d5a8011SAlexei Starovoitov WARN_ON_ONCE(!llist_empty(&c->waiting_for_gp)); 2488d5a8011SAlexei Starovoitov llist_for_each_safe(llnode, t, __llist_del_all(&c->free_by_rcu)) 2498d5a8011SAlexei Starovoitov /* There is no concurrent __llist_add(waiting_for_gp) access. 2508d5a8011SAlexei Starovoitov * It doesn't race with llist_del_all either. 2518d5a8011SAlexei Starovoitov * But there could be two concurrent llist_del_all(waiting_for_gp): 2528d5a8011SAlexei Starovoitov * from __free_rcu() and from drain_mem_cache(). 2538d5a8011SAlexei Starovoitov */ 2548d5a8011SAlexei Starovoitov __llist_add(llnode, &c->waiting_for_gp); 255dccb4a90SAlexei Starovoitov /* Use call_rcu_tasks_trace() to wait for sleepable progs to finish. 256dccb4a90SAlexei Starovoitov * Then use call_rcu() to wait for normal progs to finish 257dccb4a90SAlexei Starovoitov * and finally do free_one() on each element. 258dccb4a90SAlexei Starovoitov */ 259dccb4a90SAlexei Starovoitov call_rcu_tasks_trace(&c->rcu, __free_rcu_tasks_trace); 2608d5a8011SAlexei Starovoitov } 2618d5a8011SAlexei Starovoitov 2627c8199e2SAlexei Starovoitov static void free_bulk(struct bpf_mem_cache *c) 2637c8199e2SAlexei Starovoitov { 2647c8199e2SAlexei Starovoitov struct llist_node *llnode, *t; 2657c8199e2SAlexei Starovoitov unsigned long flags; 2667c8199e2SAlexei Starovoitov int cnt; 2677c8199e2SAlexei Starovoitov 2687c8199e2SAlexei Starovoitov do { 2697c8199e2SAlexei Starovoitov if (IS_ENABLED(CONFIG_PREEMPT_RT)) 2707c8199e2SAlexei Starovoitov local_irq_save(flags); 2717c8199e2SAlexei Starovoitov WARN_ON_ONCE(local_inc_return(&c->active) != 1); 2727c8199e2SAlexei Starovoitov llnode = __llist_del_first(&c->free_llist); 2737c8199e2SAlexei Starovoitov if (llnode) 2747c8199e2SAlexei Starovoitov cnt = --c->free_cnt; 2757c8199e2SAlexei Starovoitov else 2767c8199e2SAlexei Starovoitov cnt = 0; 2777c8199e2SAlexei Starovoitov local_dec(&c->active); 2787c8199e2SAlexei Starovoitov if (IS_ENABLED(CONFIG_PREEMPT_RT)) 2797c8199e2SAlexei Starovoitov local_irq_restore(flags); 2808d5a8011SAlexei Starovoitov enque_to_free(c, llnode); 2817c266178SAlexei Starovoitov } while (cnt > (c->high_watermark + c->low_watermark) / 2); 2827c8199e2SAlexei Starovoitov 2837c8199e2SAlexei Starovoitov /* and drain free_llist_extra */ 2847c8199e2SAlexei Starovoitov llist_for_each_safe(llnode, t, llist_del_all(&c->free_llist_extra)) 2858d5a8011SAlexei Starovoitov enque_to_free(c, llnode); 2868d5a8011SAlexei Starovoitov do_call_rcu(c); 2877c8199e2SAlexei Starovoitov } 2887c8199e2SAlexei Starovoitov 2897c8199e2SAlexei Starovoitov static void bpf_mem_refill(struct irq_work *work) 2907c8199e2SAlexei Starovoitov { 2917c8199e2SAlexei Starovoitov struct bpf_mem_cache *c = container_of(work, struct bpf_mem_cache, refill_work); 2927c8199e2SAlexei Starovoitov int cnt; 2937c8199e2SAlexei Starovoitov 2947c8199e2SAlexei Starovoitov /* Racy access to free_cnt. It doesn't need to be 100% accurate */ 2957c8199e2SAlexei Starovoitov cnt = c->free_cnt; 2967c266178SAlexei Starovoitov if (cnt < c->low_watermark) 2977c8199e2SAlexei Starovoitov /* irq_work runs on this cpu and kmalloc will allocate 2987c8199e2SAlexei Starovoitov * from the current numa node which is what we want here. 2997c8199e2SAlexei Starovoitov */ 3007c266178SAlexei Starovoitov alloc_bulk(c, c->batch, NUMA_NO_NODE); 3017c266178SAlexei Starovoitov else if (cnt > c->high_watermark) 3027c8199e2SAlexei Starovoitov free_bulk(c); 3037c8199e2SAlexei Starovoitov } 3047c8199e2SAlexei Starovoitov 3057c8199e2SAlexei Starovoitov static void notrace irq_work_raise(struct bpf_mem_cache *c) 3067c8199e2SAlexei Starovoitov { 3077c8199e2SAlexei Starovoitov irq_work_queue(&c->refill_work); 3087c8199e2SAlexei Starovoitov } 3097c8199e2SAlexei Starovoitov 3107c266178SAlexei Starovoitov /* For typical bpf map case that uses bpf_mem_cache_alloc and single bucket 3117c266178SAlexei Starovoitov * the freelist cache will be elem_size * 64 (or less) on each cpu. 3127c266178SAlexei Starovoitov * 3137c266178SAlexei Starovoitov * For bpf programs that don't have statically known allocation sizes and 3147c266178SAlexei Starovoitov * assuming (low_mark + high_mark) / 2 as an average number of elements per 3157c266178SAlexei Starovoitov * bucket and all buckets are used the total amount of memory in freelists 3167c266178SAlexei Starovoitov * on each cpu will be: 3177c266178SAlexei Starovoitov * 64*16 + 64*32 + 64*64 + 64*96 + 64*128 + 64*196 + 64*256 + 32*512 + 16*1024 + 8*2048 + 4*4096 3187c266178SAlexei Starovoitov * == ~ 116 Kbyte using below heuristic. 3197c266178SAlexei Starovoitov * Initialized, but unused bpf allocator (not bpf map specific one) will 3207c266178SAlexei Starovoitov * consume ~ 11 Kbyte per cpu. 3217c266178SAlexei Starovoitov * Typical case will be between 11K and 116K closer to 11K. 3227c266178SAlexei Starovoitov * bpf progs can and should share bpf_mem_cache when possible. 3237c266178SAlexei Starovoitov */ 3247c266178SAlexei Starovoitov 3257c8199e2SAlexei Starovoitov static void prefill_mem_cache(struct bpf_mem_cache *c, int cpu) 3267c8199e2SAlexei Starovoitov { 3277c8199e2SAlexei Starovoitov init_irq_work(&c->refill_work, bpf_mem_refill); 3287c266178SAlexei Starovoitov if (c->unit_size <= 256) { 3297c266178SAlexei Starovoitov c->low_watermark = 32; 3307c266178SAlexei Starovoitov c->high_watermark = 96; 3317c266178SAlexei Starovoitov } else { 3327c266178SAlexei Starovoitov /* When page_size == 4k, order-0 cache will have low_mark == 2 3337c266178SAlexei Starovoitov * and high_mark == 6 with batch alloc of 3 individual pages at 3347c266178SAlexei Starovoitov * a time. 3357c266178SAlexei Starovoitov * 8k allocs and above low == 1, high == 3, batch == 1. 3367c266178SAlexei Starovoitov */ 3377c266178SAlexei Starovoitov c->low_watermark = max(32 * 256 / c->unit_size, 1); 3387c266178SAlexei Starovoitov c->high_watermark = max(96 * 256 / c->unit_size, 3); 3397c266178SAlexei Starovoitov } 3407c266178SAlexei Starovoitov c->batch = max((c->high_watermark - c->low_watermark) / 4 * 3, 1); 3417c266178SAlexei Starovoitov 3427c8199e2SAlexei Starovoitov /* To avoid consuming memory assume that 1st run of bpf 3437c8199e2SAlexei Starovoitov * prog won't be doing more than 4 map_update_elem from 3447c8199e2SAlexei Starovoitov * irq disabled region 3457c8199e2SAlexei Starovoitov */ 3467c8199e2SAlexei Starovoitov alloc_bulk(c, c->unit_size <= 256 ? 4 : 1, cpu_to_node(cpu)); 3477c8199e2SAlexei Starovoitov } 3487c8199e2SAlexei Starovoitov 349bfc03c15SAlexei Starovoitov /* When size != 0 bpf_mem_cache for each cpu. 3507c8199e2SAlexei Starovoitov * This is typical bpf hash map use case when all elements have equal size. 3517c8199e2SAlexei Starovoitov * 3527c8199e2SAlexei Starovoitov * When size == 0 allocate 11 bpf_mem_cache-s for each cpu, then rely on 3537c8199e2SAlexei Starovoitov * kmalloc/kfree. Max allocation size is 4096 in this case. 3547c8199e2SAlexei Starovoitov * This is bpf_dynptr and bpf_kptr use case. 3557c8199e2SAlexei Starovoitov */ 3564ab67149SAlexei Starovoitov int bpf_mem_alloc_init(struct bpf_mem_alloc *ma, int size, bool percpu) 3577c8199e2SAlexei Starovoitov { 3587c8199e2SAlexei Starovoitov static u16 sizes[NUM_CACHES] = {96, 192, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096}; 3597c8199e2SAlexei Starovoitov struct bpf_mem_caches *cc, __percpu *pcc; 3607c8199e2SAlexei Starovoitov struct bpf_mem_cache *c, __percpu *pc; 3617c8199e2SAlexei Starovoitov struct obj_cgroup *objcg = NULL; 362bfc03c15SAlexei Starovoitov int cpu, i, unit_size, percpu_size = 0; 3637c8199e2SAlexei Starovoitov 3647c8199e2SAlexei Starovoitov if (size) { 3657c8199e2SAlexei Starovoitov pc = __alloc_percpu_gfp(sizeof(*pc), 8, GFP_KERNEL); 3667c8199e2SAlexei Starovoitov if (!pc) 3677c8199e2SAlexei Starovoitov return -ENOMEM; 3684ab67149SAlexei Starovoitov 369bfc03c15SAlexei Starovoitov if (percpu) 3704ab67149SAlexei Starovoitov /* room for llist_node and per-cpu pointer */ 371bfc03c15SAlexei Starovoitov percpu_size = LLIST_NODE_SZ + sizeof(void *); 372bfc03c15SAlexei Starovoitov else 3737c8199e2SAlexei Starovoitov size += LLIST_NODE_SZ; /* room for llist_node */ 3744ab67149SAlexei Starovoitov unit_size = size; 3754ab67149SAlexei Starovoitov 3767c8199e2SAlexei Starovoitov #ifdef CONFIG_MEMCG_KMEM 3777c8199e2SAlexei Starovoitov objcg = get_obj_cgroup_from_current(); 3787c8199e2SAlexei Starovoitov #endif 3797c8199e2SAlexei Starovoitov for_each_possible_cpu(cpu) { 3807c8199e2SAlexei Starovoitov c = per_cpu_ptr(pc, cpu); 3814ab67149SAlexei Starovoitov c->unit_size = unit_size; 3827c8199e2SAlexei Starovoitov c->objcg = objcg; 383bfc03c15SAlexei Starovoitov c->percpu_size = percpu_size; 3847c8199e2SAlexei Starovoitov prefill_mem_cache(c, cpu); 3857c8199e2SAlexei Starovoitov } 3867c8199e2SAlexei Starovoitov ma->cache = pc; 3877c8199e2SAlexei Starovoitov return 0; 3887c8199e2SAlexei Starovoitov } 3897c8199e2SAlexei Starovoitov 3904ab67149SAlexei Starovoitov /* size == 0 && percpu is an invalid combination */ 3914ab67149SAlexei Starovoitov if (WARN_ON_ONCE(percpu)) 3924ab67149SAlexei Starovoitov return -EINVAL; 3934ab67149SAlexei Starovoitov 3947c8199e2SAlexei Starovoitov pcc = __alloc_percpu_gfp(sizeof(*cc), 8, GFP_KERNEL); 3957c8199e2SAlexei Starovoitov if (!pcc) 3967c8199e2SAlexei Starovoitov return -ENOMEM; 3977c8199e2SAlexei Starovoitov #ifdef CONFIG_MEMCG_KMEM 3987c8199e2SAlexei Starovoitov objcg = get_obj_cgroup_from_current(); 3997c8199e2SAlexei Starovoitov #endif 4007c8199e2SAlexei Starovoitov for_each_possible_cpu(cpu) { 4017c8199e2SAlexei Starovoitov cc = per_cpu_ptr(pcc, cpu); 4027c8199e2SAlexei Starovoitov for (i = 0; i < NUM_CACHES; i++) { 4037c8199e2SAlexei Starovoitov c = &cc->cache[i]; 4047c8199e2SAlexei Starovoitov c->unit_size = sizes[i]; 4057c8199e2SAlexei Starovoitov c->objcg = objcg; 4067c8199e2SAlexei Starovoitov prefill_mem_cache(c, cpu); 4077c8199e2SAlexei Starovoitov } 4087c8199e2SAlexei Starovoitov } 4097c8199e2SAlexei Starovoitov ma->caches = pcc; 4107c8199e2SAlexei Starovoitov return 0; 4117c8199e2SAlexei Starovoitov } 4127c8199e2SAlexei Starovoitov 4137c8199e2SAlexei Starovoitov static void drain_mem_cache(struct bpf_mem_cache *c) 4147c8199e2SAlexei Starovoitov { 4157c8199e2SAlexei Starovoitov struct llist_node *llnode, *t; 4167c8199e2SAlexei Starovoitov 4179f2c6e96SAlexei Starovoitov /* No progs are using this bpf_mem_cache, but htab_map_free() called 4189f2c6e96SAlexei Starovoitov * bpf_mem_cache_free() for all remaining elements and they can be in 4199f2c6e96SAlexei Starovoitov * free_by_rcu or in waiting_for_gp lists, so drain those lists now. 4208d5a8011SAlexei Starovoitov */ 4218d5a8011SAlexei Starovoitov llist_for_each_safe(llnode, t, __llist_del_all(&c->free_by_rcu)) 4228d5a8011SAlexei Starovoitov free_one(c, llnode); 4238d5a8011SAlexei Starovoitov llist_for_each_safe(llnode, t, llist_del_all(&c->waiting_for_gp)) 4248d5a8011SAlexei Starovoitov free_one(c, llnode); 4257c8199e2SAlexei Starovoitov llist_for_each_safe(llnode, t, llist_del_all(&c->free_llist)) 4267c8199e2SAlexei Starovoitov free_one(c, llnode); 4277c8199e2SAlexei Starovoitov llist_for_each_safe(llnode, t, llist_del_all(&c->free_llist_extra)) 4287c8199e2SAlexei Starovoitov free_one(c, llnode); 4297c8199e2SAlexei Starovoitov } 4307c8199e2SAlexei Starovoitov 4319f2c6e96SAlexei Starovoitov static void free_mem_alloc_no_barrier(struct bpf_mem_alloc *ma) 4329f2c6e96SAlexei Starovoitov { 4339f2c6e96SAlexei Starovoitov free_percpu(ma->cache); 4349f2c6e96SAlexei Starovoitov free_percpu(ma->caches); 4359f2c6e96SAlexei Starovoitov ma->cache = NULL; 4369f2c6e96SAlexei Starovoitov ma->caches = NULL; 4379f2c6e96SAlexei Starovoitov } 4389f2c6e96SAlexei Starovoitov 4399f2c6e96SAlexei Starovoitov static void free_mem_alloc(struct bpf_mem_alloc *ma) 4409f2c6e96SAlexei Starovoitov { 4419f2c6e96SAlexei Starovoitov /* waiting_for_gp lists was drained, but __free_rcu might 4429f2c6e96SAlexei Starovoitov * still execute. Wait for it now before we freeing percpu caches. 4439f2c6e96SAlexei Starovoitov */ 4449f2c6e96SAlexei Starovoitov rcu_barrier_tasks_trace(); 4459f2c6e96SAlexei Starovoitov rcu_barrier(); 4469f2c6e96SAlexei Starovoitov free_mem_alloc_no_barrier(ma); 4479f2c6e96SAlexei Starovoitov } 4489f2c6e96SAlexei Starovoitov 4499f2c6e96SAlexei Starovoitov static void free_mem_alloc_deferred(struct work_struct *work) 4509f2c6e96SAlexei Starovoitov { 4519f2c6e96SAlexei Starovoitov struct bpf_mem_alloc *ma = container_of(work, struct bpf_mem_alloc, work); 4529f2c6e96SAlexei Starovoitov 4539f2c6e96SAlexei Starovoitov free_mem_alloc(ma); 4549f2c6e96SAlexei Starovoitov kfree(ma); 4559f2c6e96SAlexei Starovoitov } 4569f2c6e96SAlexei Starovoitov 4579f2c6e96SAlexei Starovoitov static void destroy_mem_alloc(struct bpf_mem_alloc *ma, int rcu_in_progress) 4589f2c6e96SAlexei Starovoitov { 4599f2c6e96SAlexei Starovoitov struct bpf_mem_alloc *copy; 4609f2c6e96SAlexei Starovoitov 4619f2c6e96SAlexei Starovoitov if (!rcu_in_progress) { 4629f2c6e96SAlexei Starovoitov /* Fast path. No callbacks are pending, hence no need to do 4639f2c6e96SAlexei Starovoitov * rcu_barrier-s. 4649f2c6e96SAlexei Starovoitov */ 4659f2c6e96SAlexei Starovoitov free_mem_alloc_no_barrier(ma); 4669f2c6e96SAlexei Starovoitov return; 4679f2c6e96SAlexei Starovoitov } 4689f2c6e96SAlexei Starovoitov 4699f2c6e96SAlexei Starovoitov copy = kmalloc(sizeof(*ma), GFP_KERNEL); 4709f2c6e96SAlexei Starovoitov if (!copy) { 4719f2c6e96SAlexei Starovoitov /* Slow path with inline barrier-s */ 4729f2c6e96SAlexei Starovoitov free_mem_alloc(ma); 4739f2c6e96SAlexei Starovoitov return; 4749f2c6e96SAlexei Starovoitov } 4759f2c6e96SAlexei Starovoitov 4769f2c6e96SAlexei Starovoitov /* Defer barriers into worker to let the rest of map memory to be freed */ 4779f2c6e96SAlexei Starovoitov copy->cache = ma->cache; 4789f2c6e96SAlexei Starovoitov ma->cache = NULL; 4799f2c6e96SAlexei Starovoitov copy->caches = ma->caches; 4809f2c6e96SAlexei Starovoitov ma->caches = NULL; 4819f2c6e96SAlexei Starovoitov INIT_WORK(©->work, free_mem_alloc_deferred); 4829f2c6e96SAlexei Starovoitov queue_work(system_unbound_wq, ©->work); 4839f2c6e96SAlexei Starovoitov } 4849f2c6e96SAlexei Starovoitov 4857c8199e2SAlexei Starovoitov void bpf_mem_alloc_destroy(struct bpf_mem_alloc *ma) 4867c8199e2SAlexei Starovoitov { 4877c8199e2SAlexei Starovoitov struct bpf_mem_caches *cc; 4887c8199e2SAlexei Starovoitov struct bpf_mem_cache *c; 4899f2c6e96SAlexei Starovoitov int cpu, i, rcu_in_progress; 4907c8199e2SAlexei Starovoitov 4917c8199e2SAlexei Starovoitov if (ma->cache) { 4929f2c6e96SAlexei Starovoitov rcu_in_progress = 0; 4937c8199e2SAlexei Starovoitov for_each_possible_cpu(cpu) { 4947c8199e2SAlexei Starovoitov c = per_cpu_ptr(ma->cache, cpu); 4957c8199e2SAlexei Starovoitov drain_mem_cache(c); 4969f2c6e96SAlexei Starovoitov rcu_in_progress += atomic_read(&c->call_rcu_in_progress); 4977c8199e2SAlexei Starovoitov } 498bfc03c15SAlexei Starovoitov /* objcg is the same across cpus */ 4997c8199e2SAlexei Starovoitov if (c->objcg) 5007c8199e2SAlexei Starovoitov obj_cgroup_put(c->objcg); 5019f2c6e96SAlexei Starovoitov destroy_mem_alloc(ma, rcu_in_progress); 5027c8199e2SAlexei Starovoitov } 5037c8199e2SAlexei Starovoitov if (ma->caches) { 5049f2c6e96SAlexei Starovoitov rcu_in_progress = 0; 5057c8199e2SAlexei Starovoitov for_each_possible_cpu(cpu) { 5067c8199e2SAlexei Starovoitov cc = per_cpu_ptr(ma->caches, cpu); 5077c8199e2SAlexei Starovoitov for (i = 0; i < NUM_CACHES; i++) { 5087c8199e2SAlexei Starovoitov c = &cc->cache[i]; 5097c8199e2SAlexei Starovoitov drain_mem_cache(c); 5109f2c6e96SAlexei Starovoitov rcu_in_progress += atomic_read(&c->call_rcu_in_progress); 5117c8199e2SAlexei Starovoitov } 5127c8199e2SAlexei Starovoitov } 5137c8199e2SAlexei Starovoitov if (c->objcg) 5147c8199e2SAlexei Starovoitov obj_cgroup_put(c->objcg); 5159f2c6e96SAlexei Starovoitov destroy_mem_alloc(ma, rcu_in_progress); 5167c8199e2SAlexei Starovoitov } 5177c8199e2SAlexei Starovoitov } 5187c8199e2SAlexei Starovoitov 5197c8199e2SAlexei Starovoitov /* notrace is necessary here and in other functions to make sure 5207c8199e2SAlexei Starovoitov * bpf programs cannot attach to them and cause llist corruptions. 5217c8199e2SAlexei Starovoitov */ 5227c8199e2SAlexei Starovoitov static void notrace *unit_alloc(struct bpf_mem_cache *c) 5237c8199e2SAlexei Starovoitov { 5247c8199e2SAlexei Starovoitov struct llist_node *llnode = NULL; 5257c8199e2SAlexei Starovoitov unsigned long flags; 5267c8199e2SAlexei Starovoitov int cnt = 0; 5277c8199e2SAlexei Starovoitov 5287c8199e2SAlexei Starovoitov /* Disable irqs to prevent the following race for majority of prog types: 5297c8199e2SAlexei Starovoitov * prog_A 5307c8199e2SAlexei Starovoitov * bpf_mem_alloc 5317c8199e2SAlexei Starovoitov * preemption or irq -> prog_B 5327c8199e2SAlexei Starovoitov * bpf_mem_alloc 5337c8199e2SAlexei Starovoitov * 5347c8199e2SAlexei Starovoitov * but prog_B could be a perf_event NMI prog. 5357c8199e2SAlexei Starovoitov * Use per-cpu 'active' counter to order free_list access between 5367c8199e2SAlexei Starovoitov * unit_alloc/unit_free/bpf_mem_refill. 5377c8199e2SAlexei Starovoitov */ 5387c8199e2SAlexei Starovoitov local_irq_save(flags); 5397c8199e2SAlexei Starovoitov if (local_inc_return(&c->active) == 1) { 5407c8199e2SAlexei Starovoitov llnode = __llist_del_first(&c->free_llist); 5417c8199e2SAlexei Starovoitov if (llnode) 5427c8199e2SAlexei Starovoitov cnt = --c->free_cnt; 5437c8199e2SAlexei Starovoitov } 5447c8199e2SAlexei Starovoitov local_dec(&c->active); 5457c8199e2SAlexei Starovoitov local_irq_restore(flags); 5467c8199e2SAlexei Starovoitov 5477c8199e2SAlexei Starovoitov WARN_ON(cnt < 0); 5487c8199e2SAlexei Starovoitov 5497c266178SAlexei Starovoitov if (cnt < c->low_watermark) 5507c8199e2SAlexei Starovoitov irq_work_raise(c); 5517c8199e2SAlexei Starovoitov return llnode; 5527c8199e2SAlexei Starovoitov } 5537c8199e2SAlexei Starovoitov 5547c8199e2SAlexei Starovoitov /* Though 'ptr' object could have been allocated on a different cpu 5557c8199e2SAlexei Starovoitov * add it to the free_llist of the current cpu. 5567c8199e2SAlexei Starovoitov * Let kfree() logic deal with it when it's later called from irq_work. 5577c8199e2SAlexei Starovoitov */ 5587c8199e2SAlexei Starovoitov static void notrace unit_free(struct bpf_mem_cache *c, void *ptr) 5597c8199e2SAlexei Starovoitov { 5607c8199e2SAlexei Starovoitov struct llist_node *llnode = ptr - LLIST_NODE_SZ; 5617c8199e2SAlexei Starovoitov unsigned long flags; 5627c8199e2SAlexei Starovoitov int cnt = 0; 5637c8199e2SAlexei Starovoitov 5647c8199e2SAlexei Starovoitov BUILD_BUG_ON(LLIST_NODE_SZ > 8); 5657c8199e2SAlexei Starovoitov 5667c8199e2SAlexei Starovoitov local_irq_save(flags); 5677c8199e2SAlexei Starovoitov if (local_inc_return(&c->active) == 1) { 5687c8199e2SAlexei Starovoitov __llist_add(llnode, &c->free_llist); 5697c8199e2SAlexei Starovoitov cnt = ++c->free_cnt; 5707c8199e2SAlexei Starovoitov } else { 5717c8199e2SAlexei Starovoitov /* unit_free() cannot fail. Therefore add an object to atomic 5727c8199e2SAlexei Starovoitov * llist. free_bulk() will drain it. Though free_llist_extra is 5737c8199e2SAlexei Starovoitov * a per-cpu list we have to use atomic llist_add here, since 5747c8199e2SAlexei Starovoitov * it also can be interrupted by bpf nmi prog that does another 5757c8199e2SAlexei Starovoitov * unit_free() into the same free_llist_extra. 5767c8199e2SAlexei Starovoitov */ 5777c8199e2SAlexei Starovoitov llist_add(llnode, &c->free_llist_extra); 5787c8199e2SAlexei Starovoitov } 5797c8199e2SAlexei Starovoitov local_dec(&c->active); 5807c8199e2SAlexei Starovoitov local_irq_restore(flags); 5817c8199e2SAlexei Starovoitov 5827c266178SAlexei Starovoitov if (cnt > c->high_watermark) 5837c8199e2SAlexei Starovoitov /* free few objects from current cpu into global kmalloc pool */ 5847c8199e2SAlexei Starovoitov irq_work_raise(c); 5857c8199e2SAlexei Starovoitov } 5867c8199e2SAlexei Starovoitov 5877c8199e2SAlexei Starovoitov /* Called from BPF program or from sys_bpf syscall. 5887c8199e2SAlexei Starovoitov * In both cases migration is disabled. 5897c8199e2SAlexei Starovoitov */ 5907c8199e2SAlexei Starovoitov void notrace *bpf_mem_alloc(struct bpf_mem_alloc *ma, size_t size) 5917c8199e2SAlexei Starovoitov { 5927c8199e2SAlexei Starovoitov int idx; 5937c8199e2SAlexei Starovoitov void *ret; 5947c8199e2SAlexei Starovoitov 5957c8199e2SAlexei Starovoitov if (!size) 5967c8199e2SAlexei Starovoitov return ZERO_SIZE_PTR; 5977c8199e2SAlexei Starovoitov 5987c8199e2SAlexei Starovoitov idx = bpf_mem_cache_idx(size + LLIST_NODE_SZ); 5997c8199e2SAlexei Starovoitov if (idx < 0) 6007c8199e2SAlexei Starovoitov return NULL; 6017c8199e2SAlexei Starovoitov 6027c8199e2SAlexei Starovoitov ret = unit_alloc(this_cpu_ptr(ma->caches)->cache + idx); 6037c8199e2SAlexei Starovoitov return !ret ? NULL : ret + LLIST_NODE_SZ; 6047c8199e2SAlexei Starovoitov } 6057c8199e2SAlexei Starovoitov 6067c8199e2SAlexei Starovoitov void notrace bpf_mem_free(struct bpf_mem_alloc *ma, void *ptr) 6077c8199e2SAlexei Starovoitov { 6087c8199e2SAlexei Starovoitov int idx; 6097c8199e2SAlexei Starovoitov 6107c8199e2SAlexei Starovoitov if (!ptr) 6117c8199e2SAlexei Starovoitov return; 6127c8199e2SAlexei Starovoitov 613*1e660f7eSAlexei Starovoitov idx = bpf_mem_cache_idx(ksize(ptr - LLIST_NODE_SZ)); 6147c8199e2SAlexei Starovoitov if (idx < 0) 6157c8199e2SAlexei Starovoitov return; 6167c8199e2SAlexei Starovoitov 6177c8199e2SAlexei Starovoitov unit_free(this_cpu_ptr(ma->caches)->cache + idx, ptr); 6187c8199e2SAlexei Starovoitov } 6197c8199e2SAlexei Starovoitov 6207c8199e2SAlexei Starovoitov void notrace *bpf_mem_cache_alloc(struct bpf_mem_alloc *ma) 6217c8199e2SAlexei Starovoitov { 6227c8199e2SAlexei Starovoitov void *ret; 6237c8199e2SAlexei Starovoitov 6247c8199e2SAlexei Starovoitov ret = unit_alloc(this_cpu_ptr(ma->cache)); 6257c8199e2SAlexei Starovoitov return !ret ? NULL : ret + LLIST_NODE_SZ; 6267c8199e2SAlexei Starovoitov } 6277c8199e2SAlexei Starovoitov 6287c8199e2SAlexei Starovoitov void notrace bpf_mem_cache_free(struct bpf_mem_alloc *ma, void *ptr) 6297c8199e2SAlexei Starovoitov { 6307c8199e2SAlexei Starovoitov if (!ptr) 6317c8199e2SAlexei Starovoitov return; 6327c8199e2SAlexei Starovoitov 6337c8199e2SAlexei Starovoitov unit_free(this_cpu_ptr(ma->cache), ptr); 6347c8199e2SAlexei Starovoitov } 635