1 /* Copyright (c) 2016 Facebook
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.
8 #include <linux/jhash.h>
9 #include <linux/filter.h>
10 #include <linux/stacktrace.h>
11 #include <linux/perf_event.h>
12 #include <linux/elf.h>
13 #include <linux/pagemap.h>
14 #include <linux/irq_work.h>
15 #include "percpu_freelist.h"
17 #define STACK_CREATE_FLAG_MASK \
18 (BPF_F_NUMA_NODE | BPF_F_RDONLY | BPF_F_WRONLY | \
21 struct stack_map_bucket
{
22 struct pcpu_freelist_node fnode
;
28 struct bpf_stack_map
{
31 struct pcpu_freelist freelist
;
33 struct stack_map_bucket
*buckets
[];
36 /* irq_work to run up_read() for build_id lookup in nmi context */
37 struct stack_map_irq_work
{
38 struct irq_work irq_work
;
39 struct rw_semaphore
*sem
;
42 static void do_up_read(struct irq_work
*entry
)
44 struct stack_map_irq_work
*work
;
46 work
= container_of(entry
, struct stack_map_irq_work
, irq_work
);
51 static DEFINE_PER_CPU(struct stack_map_irq_work
, up_read_work
);
53 static inline bool stack_map_use_build_id(struct bpf_map
*map
)
55 return (map
->map_flags
& BPF_F_STACK_BUILD_ID
);
58 static inline int stack_map_data_size(struct bpf_map
*map
)
60 return stack_map_use_build_id(map
) ?
61 sizeof(struct bpf_stack_build_id
) : sizeof(u64
);
64 static int prealloc_elems_and_freelist(struct bpf_stack_map
*smap
)
66 u32 elem_size
= sizeof(struct stack_map_bucket
) + smap
->map
.value_size
;
69 smap
->elems
= bpf_map_area_alloc(elem_size
* smap
->map
.max_entries
,
74 err
= pcpu_freelist_init(&smap
->freelist
);
78 pcpu_freelist_populate(&smap
->freelist
, smap
->elems
, elem_size
,
79 smap
->map
.max_entries
);
83 bpf_map_area_free(smap
->elems
);
87 /* Called from syscall */
88 static struct bpf_map
*stack_map_alloc(union bpf_attr
*attr
)
90 u32 value_size
= attr
->value_size
;
91 struct bpf_stack_map
*smap
;
95 if (!capable(CAP_SYS_ADMIN
))
96 return ERR_PTR(-EPERM
);
98 if (attr
->map_flags
& ~STACK_CREATE_FLAG_MASK
)
99 return ERR_PTR(-EINVAL
);
101 /* check sanity of attributes */
102 if (attr
->max_entries
== 0 || attr
->key_size
!= 4 ||
103 value_size
< 8 || value_size
% 8)
104 return ERR_PTR(-EINVAL
);
106 BUILD_BUG_ON(sizeof(struct bpf_stack_build_id
) % sizeof(u64
));
107 if (attr
->map_flags
& BPF_F_STACK_BUILD_ID
) {
108 if (value_size
% sizeof(struct bpf_stack_build_id
) ||
109 value_size
/ sizeof(struct bpf_stack_build_id
)
110 > sysctl_perf_event_max_stack
)
111 return ERR_PTR(-EINVAL
);
112 } else if (value_size
/ 8 > sysctl_perf_event_max_stack
)
113 return ERR_PTR(-EINVAL
);
115 /* hash table size must be power of 2 */
116 n_buckets
= roundup_pow_of_two(attr
->max_entries
);
118 cost
= n_buckets
* sizeof(struct stack_map_bucket
*) + sizeof(*smap
);
119 if (cost
>= U32_MAX
- PAGE_SIZE
)
120 return ERR_PTR(-E2BIG
);
122 smap
= bpf_map_area_alloc(cost
, bpf_map_attr_numa_node(attr
));
124 return ERR_PTR(-ENOMEM
);
127 cost
+= n_buckets
* (value_size
+ sizeof(struct stack_map_bucket
));
128 if (cost
>= U32_MAX
- PAGE_SIZE
)
131 bpf_map_init_from_attr(&smap
->map
, attr
);
132 smap
->map
.value_size
= value_size
;
133 smap
->n_buckets
= n_buckets
;
134 smap
->map
.pages
= round_up(cost
, PAGE_SIZE
) >> PAGE_SHIFT
;
136 err
= bpf_map_precharge_memlock(smap
->map
.pages
);
140 err
= get_callchain_buffers(sysctl_perf_event_max_stack
);
144 err
= prealloc_elems_and_freelist(smap
);
151 put_callchain_buffers();
153 bpf_map_area_free(smap
);
157 #define BPF_BUILD_ID 3
159 * Parse build id from the note segment. This logic can be shared between
160 * 32-bit and 64-bit system, because Elf32_Nhdr and Elf64_Nhdr are
163 static inline int stack_map_parse_build_id(void *page_addr
,
164 unsigned char *build_id
,
166 Elf32_Word note_size
)
168 Elf32_Word note_offs
= 0, new_offs
;
170 /* check for overflow */
171 if (note_start
< page_addr
|| note_start
+ note_size
< note_start
)
174 /* only supports note that fits in the first page */
175 if (note_start
+ note_size
> page_addr
+ PAGE_SIZE
)
178 while (note_offs
+ sizeof(Elf32_Nhdr
) < note_size
) {
179 Elf32_Nhdr
*nhdr
= (Elf32_Nhdr
*)(note_start
+ note_offs
);
181 if (nhdr
->n_type
== BPF_BUILD_ID
&&
182 nhdr
->n_namesz
== sizeof("GNU") &&
183 nhdr
->n_descsz
== BPF_BUILD_ID_SIZE
) {
185 note_start
+ note_offs
+
186 ALIGN(sizeof("GNU"), 4) + sizeof(Elf32_Nhdr
),
190 new_offs
= note_offs
+ sizeof(Elf32_Nhdr
) +
191 ALIGN(nhdr
->n_namesz
, 4) + ALIGN(nhdr
->n_descsz
, 4);
192 if (new_offs
<= note_offs
) /* overflow */
194 note_offs
= new_offs
;
199 /* Parse build ID from 32-bit ELF */
200 static int stack_map_get_build_id_32(void *page_addr
,
201 unsigned char *build_id
)
203 Elf32_Ehdr
*ehdr
= (Elf32_Ehdr
*)page_addr
;
207 /* only supports phdr that fits in one page */
209 (PAGE_SIZE
- sizeof(Elf32_Ehdr
)) / sizeof(Elf32_Phdr
))
212 phdr
= (Elf32_Phdr
*)(page_addr
+ sizeof(Elf32_Ehdr
));
214 for (i
= 0; i
< ehdr
->e_phnum
; ++i
)
215 if (phdr
[i
].p_type
== PT_NOTE
)
216 return stack_map_parse_build_id(page_addr
, build_id
,
217 page_addr
+ phdr
[i
].p_offset
,
222 /* Parse build ID from 64-bit ELF */
223 static int stack_map_get_build_id_64(void *page_addr
,
224 unsigned char *build_id
)
226 Elf64_Ehdr
*ehdr
= (Elf64_Ehdr
*)page_addr
;
230 /* only supports phdr that fits in one page */
232 (PAGE_SIZE
- sizeof(Elf64_Ehdr
)) / sizeof(Elf64_Phdr
))
235 phdr
= (Elf64_Phdr
*)(page_addr
+ sizeof(Elf64_Ehdr
));
237 for (i
= 0; i
< ehdr
->e_phnum
; ++i
)
238 if (phdr
[i
].p_type
== PT_NOTE
)
239 return stack_map_parse_build_id(page_addr
, build_id
,
240 page_addr
+ phdr
[i
].p_offset
,
245 /* Parse build ID of ELF file mapped to vma */
246 static int stack_map_get_build_id(struct vm_area_struct
*vma
,
247 unsigned char *build_id
)
254 /* only works for page backed storage */
258 page
= find_get_page(vma
->vm_file
->f_mapping
, 0);
260 return -EFAULT
; /* page not mapped */
263 page_addr
= page_address(page
);
264 ehdr
= (Elf32_Ehdr
*)page_addr
;
266 /* compare magic x7f "ELF" */
267 if (memcmp(ehdr
->e_ident
, ELFMAG
, SELFMAG
) != 0)
270 /* only support executable file and shared object file */
271 if (ehdr
->e_type
!= ET_EXEC
&& ehdr
->e_type
!= ET_DYN
)
274 if (ehdr
->e_ident
[EI_CLASS
] == ELFCLASS32
)
275 ret
= stack_map_get_build_id_32(page_addr
, build_id
);
276 else if (ehdr
->e_ident
[EI_CLASS
] == ELFCLASS64
)
277 ret
= stack_map_get_build_id_64(page_addr
, build_id
);
283 static void stack_map_get_build_id_offset(struct bpf_stack_build_id
*id_offs
,
284 u64
*ips
, u32 trace_nr
, bool user
)
287 struct vm_area_struct
*vma
;
288 bool irq_work_busy
= false;
289 struct stack_map_irq_work
*work
= NULL
;
292 work
= this_cpu_ptr(&up_read_work
);
293 if (work
->irq_work
.flags
& IRQ_WORK_BUSY
)
294 /* cannot queue more up_read, fallback */
295 irq_work_busy
= true;
299 * We cannot do up_read() in nmi context. To do build_id lookup
300 * in nmi context, we need to run up_read() in irq_work. We use
301 * a percpu variable to do the irq_work. If the irq_work is
302 * already used by another lookup, we fall back to report ips.
304 * Same fallback is used for kernel stack (!user) on a stackmap
307 if (!user
|| !current
|| !current
->mm
|| irq_work_busy
||
308 down_read_trylock(¤t
->mm
->mmap_sem
) == 0) {
309 /* cannot access current->mm, fall back to ips */
310 for (i
= 0; i
< trace_nr
; i
++) {
311 id_offs
[i
].status
= BPF_STACK_BUILD_ID_IP
;
312 id_offs
[i
].ip
= ips
[i
];
317 for (i
= 0; i
< trace_nr
; i
++) {
318 vma
= find_vma(current
->mm
, ips
[i
]);
319 if (!vma
|| stack_map_get_build_id(vma
, id_offs
[i
].build_id
)) {
320 /* per entry fall back to ips */
321 id_offs
[i
].status
= BPF_STACK_BUILD_ID_IP
;
322 id_offs
[i
].ip
= ips
[i
];
325 id_offs
[i
].offset
= (vma
->vm_pgoff
<< PAGE_SHIFT
) + ips
[i
]
327 id_offs
[i
].status
= BPF_STACK_BUILD_ID_VALID
;
331 up_read(¤t
->mm
->mmap_sem
);
333 work
->sem
= ¤t
->mm
->mmap_sem
;
334 irq_work_queue(&work
->irq_work
);
338 BPF_CALL_3(bpf_get_stackid
, struct pt_regs
*, regs
, struct bpf_map
*, map
,
341 struct bpf_stack_map
*smap
= container_of(map
, struct bpf_stack_map
, map
);
342 struct perf_callchain_entry
*trace
;
343 struct stack_map_bucket
*bucket
, *new_bucket
, *old_bucket
;
344 u32 max_depth
= map
->value_size
/ stack_map_data_size(map
);
345 /* stack_map_alloc() checks that max_depth <= sysctl_perf_event_max_stack */
346 u32 init_nr
= sysctl_perf_event_max_stack
- max_depth
;
347 u32 skip
= flags
& BPF_F_SKIP_FIELD_MASK
;
348 u32 hash
, id
, trace_nr
, trace_len
;
349 bool user
= flags
& BPF_F_USER_STACK
;
354 if (unlikely(flags
& ~(BPF_F_SKIP_FIELD_MASK
| BPF_F_USER_STACK
|
355 BPF_F_FAST_STACK_CMP
| BPF_F_REUSE_STACKID
)))
358 trace
= get_perf_callchain(regs
, init_nr
, kernel
, user
,
359 sysctl_perf_event_max_stack
, false, false);
361 if (unlikely(!trace
))
362 /* couldn't fetch the stack trace */
365 /* get_perf_callchain() guarantees that trace->nr >= init_nr
366 * and trace-nr <= sysctl_perf_event_max_stack, so trace_nr <= max_depth
368 trace_nr
= trace
->nr
- init_nr
;
370 if (trace_nr
<= skip
)
371 /* skipping more than usable stack trace */
375 trace_len
= trace_nr
* sizeof(u64
);
376 ips
= trace
->ip
+ skip
+ init_nr
;
377 hash
= jhash2((u32
*)ips
, trace_len
/ sizeof(u32
), 0);
378 id
= hash
& (smap
->n_buckets
- 1);
379 bucket
= READ_ONCE(smap
->buckets
[id
]);
381 hash_matches
= bucket
&& bucket
->hash
== hash
;
383 if (hash_matches
&& flags
& BPF_F_FAST_STACK_CMP
)
386 if (stack_map_use_build_id(map
)) {
387 /* for build_id+offset, pop a bucket before slow cmp */
388 new_bucket
= (struct stack_map_bucket
*)
389 pcpu_freelist_pop(&smap
->freelist
);
390 if (unlikely(!new_bucket
))
392 new_bucket
->nr
= trace_nr
;
393 stack_map_get_build_id_offset(
394 (struct bpf_stack_build_id
*)new_bucket
->data
,
395 ips
, trace_nr
, user
);
396 trace_len
= trace_nr
* sizeof(struct bpf_stack_build_id
);
397 if (hash_matches
&& bucket
->nr
== trace_nr
&&
398 memcmp(bucket
->data
, new_bucket
->data
, trace_len
) == 0) {
399 pcpu_freelist_push(&smap
->freelist
, &new_bucket
->fnode
);
402 if (bucket
&& !(flags
& BPF_F_REUSE_STACKID
)) {
403 pcpu_freelist_push(&smap
->freelist
, &new_bucket
->fnode
);
407 if (hash_matches
&& bucket
->nr
== trace_nr
&&
408 memcmp(bucket
->data
, ips
, trace_len
) == 0)
410 if (bucket
&& !(flags
& BPF_F_REUSE_STACKID
))
413 new_bucket
= (struct stack_map_bucket
*)
414 pcpu_freelist_pop(&smap
->freelist
);
415 if (unlikely(!new_bucket
))
417 memcpy(new_bucket
->data
, ips
, trace_len
);
420 new_bucket
->hash
= hash
;
421 new_bucket
->nr
= trace_nr
;
423 old_bucket
= xchg(&smap
->buckets
[id
], new_bucket
);
425 pcpu_freelist_push(&smap
->freelist
, &old_bucket
->fnode
);
429 const struct bpf_func_proto bpf_get_stackid_proto
= {
430 .func
= bpf_get_stackid
,
432 .ret_type
= RET_INTEGER
,
433 .arg1_type
= ARG_PTR_TO_CTX
,
434 .arg2_type
= ARG_CONST_MAP_PTR
,
435 .arg3_type
= ARG_ANYTHING
,
438 BPF_CALL_4(bpf_get_stack
, struct pt_regs
*, regs
, void *, buf
, u32
, size
,
441 u32 init_nr
, trace_nr
, copy_len
, elem_size
, num_elem
;
442 bool user_build_id
= flags
& BPF_F_USER_BUILD_ID
;
443 u32 skip
= flags
& BPF_F_SKIP_FIELD_MASK
;
444 bool user
= flags
& BPF_F_USER_STACK
;
445 struct perf_callchain_entry
*trace
;
450 if (unlikely(flags
& ~(BPF_F_SKIP_FIELD_MASK
| BPF_F_USER_STACK
|
451 BPF_F_USER_BUILD_ID
)))
453 if (kernel
&& user_build_id
)
456 elem_size
= (user
&& user_build_id
) ? sizeof(struct bpf_stack_build_id
)
458 if (unlikely(size
% elem_size
))
461 num_elem
= size
/ elem_size
;
462 if (sysctl_perf_event_max_stack
< num_elem
)
465 init_nr
= sysctl_perf_event_max_stack
- num_elem
;
466 trace
= get_perf_callchain(regs
, init_nr
, kernel
, user
,
467 sysctl_perf_event_max_stack
, false, false);
468 if (unlikely(!trace
))
471 trace_nr
= trace
->nr
- init_nr
;
476 trace_nr
= (trace_nr
<= num_elem
) ? trace_nr
: num_elem
;
477 copy_len
= trace_nr
* elem_size
;
478 ips
= trace
->ip
+ skip
+ init_nr
;
479 if (user
&& user_build_id
)
480 stack_map_get_build_id_offset(buf
, ips
, trace_nr
, user
);
482 memcpy(buf
, ips
, copy_len
);
485 memset(buf
+ copy_len
, 0, size
- copy_len
);
491 memset(buf
, 0, size
);
495 const struct bpf_func_proto bpf_get_stack_proto
= {
496 .func
= bpf_get_stack
,
498 .ret_type
= RET_INTEGER
,
499 .arg1_type
= ARG_PTR_TO_CTX
,
500 .arg2_type
= ARG_PTR_TO_UNINIT_MEM
,
501 .arg3_type
= ARG_CONST_SIZE_OR_ZERO
,
502 .arg4_type
= ARG_ANYTHING
,
505 /* Called from eBPF program */
506 static void *stack_map_lookup_elem(struct bpf_map
*map
, void *key
)
508 return ERR_PTR(-EOPNOTSUPP
);
511 /* Called from syscall */
512 int bpf_stackmap_copy(struct bpf_map
*map
, void *key
, void *value
)
514 struct bpf_stack_map
*smap
= container_of(map
, struct bpf_stack_map
, map
);
515 struct stack_map_bucket
*bucket
, *old_bucket
;
516 u32 id
= *(u32
*)key
, trace_len
;
518 if (unlikely(id
>= smap
->n_buckets
))
521 bucket
= xchg(&smap
->buckets
[id
], NULL
);
525 trace_len
= bucket
->nr
* stack_map_data_size(map
);
526 memcpy(value
, bucket
->data
, trace_len
);
527 memset(value
+ trace_len
, 0, map
->value_size
- trace_len
);
529 old_bucket
= xchg(&smap
->buckets
[id
], bucket
);
531 pcpu_freelist_push(&smap
->freelist
, &old_bucket
->fnode
);
535 static int stack_map_get_next_key(struct bpf_map
*map
, void *key
,
538 struct bpf_stack_map
*smap
= container_of(map
,
539 struct bpf_stack_map
, map
);
542 WARN_ON_ONCE(!rcu_read_lock_held());
548 if (id
>= smap
->n_buckets
|| !smap
->buckets
[id
])
554 while (id
< smap
->n_buckets
&& !smap
->buckets
[id
])
557 if (id
>= smap
->n_buckets
)
560 *(u32
*)next_key
= id
;
564 static int stack_map_update_elem(struct bpf_map
*map
, void *key
, void *value
,
570 /* Called from syscall or from eBPF program */
571 static int stack_map_delete_elem(struct bpf_map
*map
, void *key
)
573 struct bpf_stack_map
*smap
= container_of(map
, struct bpf_stack_map
, map
);
574 struct stack_map_bucket
*old_bucket
;
575 u32 id
= *(u32
*)key
;
577 if (unlikely(id
>= smap
->n_buckets
))
580 old_bucket
= xchg(&smap
->buckets
[id
], NULL
);
582 pcpu_freelist_push(&smap
->freelist
, &old_bucket
->fnode
);
589 /* Called when map->refcnt goes to zero, either from workqueue or from syscall */
590 static void stack_map_free(struct bpf_map
*map
)
592 struct bpf_stack_map
*smap
= container_of(map
, struct bpf_stack_map
, map
);
594 /* wait for bpf programs to complete before freeing stack map */
597 bpf_map_area_free(smap
->elems
);
598 pcpu_freelist_destroy(&smap
->freelist
);
599 bpf_map_area_free(smap
);
600 put_callchain_buffers();
603 const struct bpf_map_ops stack_trace_map_ops
= {
604 .map_alloc
= stack_map_alloc
,
605 .map_free
= stack_map_free
,
606 .map_get_next_key
= stack_map_get_next_key
,
607 .map_lookup_elem
= stack_map_lookup_elem
,
608 .map_update_elem
= stack_map_update_elem
,
609 .map_delete_elem
= stack_map_delete_elem
,
610 .map_check_btf
= map_check_no_btf
,
613 static int __init
stack_map_init(void)
616 struct stack_map_irq_work
*work
;
618 for_each_possible_cpu(cpu
) {
619 work
= per_cpu_ptr(&up_read_work
, cpu
);
620 init_irq_work(&work
->irq_work
, do_up_read
);
624 subsys_initcall(stack_map_init
);