Merge branch 'for-next' of git://git.kernel.org/pub/scm/linux/kernel/git/gerg/m68knommu
[linux-block.git] / kernel / bpf / stackmap.c
1 /* Copyright (c) 2016 Facebook
2  *
3  * This program is free software; you can redistribute it and/or
4  * modify it under the terms of version 2 of the GNU General Public
5  * License as published by the Free Software Foundation.
6  */
7 #include <linux/bpf.h>
8 #include <linux/jhash.h>
9 #include <linux/filter.h>
10 #include <linux/stacktrace.h>
11 #include <linux/perf_event.h>
12 #include "percpu_freelist.h"
13
14 struct stack_map_bucket {
15         struct pcpu_freelist_node fnode;
16         u32 hash;
17         u32 nr;
18         u64 ip[];
19 };
20
21 struct bpf_stack_map {
22         struct bpf_map map;
23         void *elems;
24         struct pcpu_freelist freelist;
25         u32 n_buckets;
26         struct stack_map_bucket *buckets[];
27 };
28
29 static int prealloc_elems_and_freelist(struct bpf_stack_map *smap)
30 {
31         u32 elem_size = sizeof(struct stack_map_bucket) + smap->map.value_size;
32         int err;
33
34         smap->elems = bpf_map_area_alloc(elem_size * smap->map.max_entries,
35                                          smap->map.numa_node);
36         if (!smap->elems)
37                 return -ENOMEM;
38
39         err = pcpu_freelist_init(&smap->freelist);
40         if (err)
41                 goto free_elems;
42
43         pcpu_freelist_populate(&smap->freelist, smap->elems, elem_size,
44                                smap->map.max_entries);
45         return 0;
46
47 free_elems:
48         bpf_map_area_free(smap->elems);
49         return err;
50 }
51
52 /* Called from syscall */
53 static struct bpf_map *stack_map_alloc(union bpf_attr *attr)
54 {
55         u32 value_size = attr->value_size;
56         struct bpf_stack_map *smap;
57         u64 cost, n_buckets;
58         int err;
59
60         if (!capable(CAP_SYS_ADMIN))
61                 return ERR_PTR(-EPERM);
62
63         if (attr->map_flags & ~BPF_F_NUMA_NODE)
64                 return ERR_PTR(-EINVAL);
65
66         /* check sanity of attributes */
67         if (attr->max_entries == 0 || attr->key_size != 4 ||
68             value_size < 8 || value_size % 8 ||
69             value_size / 8 > sysctl_perf_event_max_stack)
70                 return ERR_PTR(-EINVAL);
71
72         /* hash table size must be power of 2 */
73         n_buckets = roundup_pow_of_two(attr->max_entries);
74
75         cost = n_buckets * sizeof(struct stack_map_bucket *) + sizeof(*smap);
76         if (cost >= U32_MAX - PAGE_SIZE)
77                 return ERR_PTR(-E2BIG);
78
79         smap = bpf_map_area_alloc(cost, bpf_map_attr_numa_node(attr));
80         if (!smap)
81                 return ERR_PTR(-ENOMEM);
82
83         err = -E2BIG;
84         cost += n_buckets * (value_size + sizeof(struct stack_map_bucket));
85         if (cost >= U32_MAX - PAGE_SIZE)
86                 goto free_smap;
87
88         smap->map.map_type = attr->map_type;
89         smap->map.key_size = attr->key_size;
90         smap->map.value_size = value_size;
91         smap->map.max_entries = attr->max_entries;
92         smap->map.map_flags = attr->map_flags;
93         smap->n_buckets = n_buckets;
94         smap->map.pages = round_up(cost, PAGE_SIZE) >> PAGE_SHIFT;
95         smap->map.numa_node = bpf_map_attr_numa_node(attr);
96
97         err = bpf_map_precharge_memlock(smap->map.pages);
98         if (err)
99                 goto free_smap;
100
101         err = get_callchain_buffers(sysctl_perf_event_max_stack);
102         if (err)
103                 goto free_smap;
104
105         err = prealloc_elems_and_freelist(smap);
106         if (err)
107                 goto put_buffers;
108
109         return &smap->map;
110
111 put_buffers:
112         put_callchain_buffers();
113 free_smap:
114         bpf_map_area_free(smap);
115         return ERR_PTR(err);
116 }
117
118 BPF_CALL_3(bpf_get_stackid, struct pt_regs *, regs, struct bpf_map *, map,
119            u64, flags)
120 {
121         struct bpf_stack_map *smap = container_of(map, struct bpf_stack_map, map);
122         struct perf_callchain_entry *trace;
123         struct stack_map_bucket *bucket, *new_bucket, *old_bucket;
124         u32 max_depth = map->value_size / 8;
125         /* stack_map_alloc() checks that max_depth <= sysctl_perf_event_max_stack */
126         u32 init_nr = sysctl_perf_event_max_stack - max_depth;
127         u32 skip = flags & BPF_F_SKIP_FIELD_MASK;
128         u32 hash, id, trace_nr, trace_len;
129         bool user = flags & BPF_F_USER_STACK;
130         bool kernel = !user;
131         u64 *ips;
132
133         if (unlikely(flags & ~(BPF_F_SKIP_FIELD_MASK | BPF_F_USER_STACK |
134                                BPF_F_FAST_STACK_CMP | BPF_F_REUSE_STACKID)))
135                 return -EINVAL;
136
137         trace = get_perf_callchain(regs, init_nr, kernel, user,
138                                    sysctl_perf_event_max_stack, false, false);
139
140         if (unlikely(!trace))
141                 /* couldn't fetch the stack trace */
142                 return -EFAULT;
143
144         /* get_perf_callchain() guarantees that trace->nr >= init_nr
145          * and trace-nr <= sysctl_perf_event_max_stack, so trace_nr <= max_depth
146          */
147         trace_nr = trace->nr - init_nr;
148
149         if (trace_nr <= skip)
150                 /* skipping more than usable stack trace */
151                 return -EFAULT;
152
153         trace_nr -= skip;
154         trace_len = trace_nr * sizeof(u64);
155         ips = trace->ip + skip + init_nr;
156         hash = jhash2((u32 *)ips, trace_len / sizeof(u32), 0);
157         id = hash & (smap->n_buckets - 1);
158         bucket = READ_ONCE(smap->buckets[id]);
159
160         if (bucket && bucket->hash == hash) {
161                 if (flags & BPF_F_FAST_STACK_CMP)
162                         return id;
163                 if (bucket->nr == trace_nr &&
164                     memcmp(bucket->ip, ips, trace_len) == 0)
165                         return id;
166         }
167
168         /* this call stack is not in the map, try to add it */
169         if (bucket && !(flags & BPF_F_REUSE_STACKID))
170                 return -EEXIST;
171
172         new_bucket = (struct stack_map_bucket *)
173                 pcpu_freelist_pop(&smap->freelist);
174         if (unlikely(!new_bucket))
175                 return -ENOMEM;
176
177         memcpy(new_bucket->ip, ips, trace_len);
178         new_bucket->hash = hash;
179         new_bucket->nr = trace_nr;
180
181         old_bucket = xchg(&smap->buckets[id], new_bucket);
182         if (old_bucket)
183                 pcpu_freelist_push(&smap->freelist, &old_bucket->fnode);
184         return id;
185 }
186
187 const struct bpf_func_proto bpf_get_stackid_proto = {
188         .func           = bpf_get_stackid,
189         .gpl_only       = true,
190         .ret_type       = RET_INTEGER,
191         .arg1_type      = ARG_PTR_TO_CTX,
192         .arg2_type      = ARG_CONST_MAP_PTR,
193         .arg3_type      = ARG_ANYTHING,
194 };
195
196 /* Called from eBPF program */
197 static void *stack_map_lookup_elem(struct bpf_map *map, void *key)
198 {
199         return NULL;
200 }
201
202 /* Called from syscall */
203 int bpf_stackmap_copy(struct bpf_map *map, void *key, void *value)
204 {
205         struct bpf_stack_map *smap = container_of(map, struct bpf_stack_map, map);
206         struct stack_map_bucket *bucket, *old_bucket;
207         u32 id = *(u32 *)key, trace_len;
208
209         if (unlikely(id >= smap->n_buckets))
210                 return -ENOENT;
211
212         bucket = xchg(&smap->buckets[id], NULL);
213         if (!bucket)
214                 return -ENOENT;
215
216         trace_len = bucket->nr * sizeof(u64);
217         memcpy(value, bucket->ip, trace_len);
218         memset(value + trace_len, 0, map->value_size - trace_len);
219
220         old_bucket = xchg(&smap->buckets[id], bucket);
221         if (old_bucket)
222                 pcpu_freelist_push(&smap->freelist, &old_bucket->fnode);
223         return 0;
224 }
225
226 static int stack_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
227 {
228         return -EINVAL;
229 }
230
231 static int stack_map_update_elem(struct bpf_map *map, void *key, void *value,
232                                  u64 map_flags)
233 {
234         return -EINVAL;
235 }
236
237 /* Called from syscall or from eBPF program */
238 static int stack_map_delete_elem(struct bpf_map *map, void *key)
239 {
240         struct bpf_stack_map *smap = container_of(map, struct bpf_stack_map, map);
241         struct stack_map_bucket *old_bucket;
242         u32 id = *(u32 *)key;
243
244         if (unlikely(id >= smap->n_buckets))
245                 return -E2BIG;
246
247         old_bucket = xchg(&smap->buckets[id], NULL);
248         if (old_bucket) {
249                 pcpu_freelist_push(&smap->freelist, &old_bucket->fnode);
250                 return 0;
251         } else {
252                 return -ENOENT;
253         }
254 }
255
256 /* Called when map->refcnt goes to zero, either from workqueue or from syscall */
257 static void stack_map_free(struct bpf_map *map)
258 {
259         struct bpf_stack_map *smap = container_of(map, struct bpf_stack_map, map);
260
261         /* wait for bpf programs to complete before freeing stack map */
262         synchronize_rcu();
263
264         bpf_map_area_free(smap->elems);
265         pcpu_freelist_destroy(&smap->freelist);
266         bpf_map_area_free(smap);
267         put_callchain_buffers();
268 }
269
270 const struct bpf_map_ops stack_map_ops = {
271         .map_alloc = stack_map_alloc,
272         .map_free = stack_map_free,
273         .map_get_next_key = stack_map_get_next_key,
274         .map_lookup_elem = stack_map_lookup_elem,
275         .map_update_elem = stack_map_update_elem,
276         .map_delete_elem = stack_map_delete_elem,
277 };