xref: /linux/kernel/bpf/stackmap.c (revision a08ba2ab79dffd92c32d3f2dadfc7eba03625a2b)
1 // SPDX-License-Identifier: GPL-2.0-only
2 /* Copyright (c) 2016 Facebook
3  */
4 #include <linux/bpf.h>
5 #include <linux/jhash.h>
6 #include <linux/filter.h>
7 #include <linux/kernel.h>
8 #include <linux/stacktrace.h>
9 #include <linux/perf_event.h>
10 #include <linux/btf_ids.h>
11 #include <linux/buildid.h>
12 #include <linux/mmap_lock.h>
13 #include "percpu_freelist.h"
14 #include "mmap_unlock_work.h"
15 
16 #define STACK_CREATE_FLAG_MASK					\
17 	(BPF_F_NUMA_NODE | BPF_F_RDONLY | BPF_F_WRONLY |	\
18 	 BPF_F_STACK_BUILD_ID)
19 
20 struct stack_map_bucket {
21 	struct pcpu_freelist_node fnode;
22 	u32 hash;
23 	u32 nr;
24 	u64 data[];
25 };
26 
27 struct bpf_stack_map {
28 	struct bpf_map map;
29 	void *elems;
30 	struct pcpu_freelist freelist;
31 	u32 n_buckets;
32 	struct stack_map_bucket *buckets[] __counted_by(n_buckets);
33 };
34 
35 static inline bool stack_map_use_build_id(struct bpf_map *map)
36 {
37 	return (map->map_flags & BPF_F_STACK_BUILD_ID);
38 }
39 
40 static inline int stack_map_data_size(struct bpf_map *map)
41 {
42 	return stack_map_use_build_id(map) ?
43 		sizeof(struct bpf_stack_build_id) : sizeof(u64);
44 }
45 
46 /**
47  * stack_map_calculate_max_depth - Calculate maximum allowed stack trace depth
48  * @size:  Size of the buffer/map value in bytes
49  * @elem_size:  Size of each stack trace element
50  * @flags:  BPF stack trace flags (BPF_F_USER_STACK, BPF_F_USER_BUILD_ID, ...)
51  *
52  * Return: Maximum number of stack trace entries that can be safely stored
53  */
54 static u32 stack_map_calculate_max_depth(u32 size, u32 elem_size, u64 flags)
55 {
56 	u32 skip = flags & BPF_F_SKIP_FIELD_MASK;
57 	u32 max_depth;
58 	u32 curr_sysctl_max_stack = READ_ONCE(sysctl_perf_event_max_stack);
59 
60 	max_depth = size / elem_size;
61 	max_depth += skip;
62 	if (max_depth > curr_sysctl_max_stack)
63 		return curr_sysctl_max_stack;
64 
65 	return max_depth;
66 }
67 
68 static int prealloc_elems_and_freelist(struct bpf_stack_map *smap)
69 {
70 	u64 elem_size = sizeof(struct stack_map_bucket) +
71 			(u64)smap->map.value_size;
72 	int err;
73 
74 	smap->elems = bpf_map_area_alloc(elem_size * smap->map.max_entries,
75 					 smap->map.numa_node);
76 	if (!smap->elems)
77 		return -ENOMEM;
78 
79 	err = pcpu_freelist_init(&smap->freelist);
80 	if (err)
81 		goto free_elems;
82 
83 	pcpu_freelist_populate(&smap->freelist, smap->elems, elem_size,
84 			       smap->map.max_entries);
85 	return 0;
86 
87 free_elems:
88 	bpf_map_area_free(smap->elems);
89 	return err;
90 }
91 
92 /* Called from syscall */
93 static struct bpf_map *stack_map_alloc(union bpf_attr *attr)
94 {
95 	u32 value_size = attr->value_size;
96 	struct bpf_stack_map *smap;
97 	u64 cost, n_buckets;
98 	int err;
99 
100 	if (attr->map_flags & ~STACK_CREATE_FLAG_MASK)
101 		return ERR_PTR(-EINVAL);
102 
103 	/* check sanity of attributes */
104 	if (attr->max_entries == 0 || attr->key_size != 4 ||
105 	    value_size < 8 || value_size % 8)
106 		return ERR_PTR(-EINVAL);
107 
108 	BUILD_BUG_ON(sizeof(struct bpf_stack_build_id) % sizeof(u64));
109 	if (attr->map_flags & BPF_F_STACK_BUILD_ID) {
110 		if (value_size % sizeof(struct bpf_stack_build_id) ||
111 		    value_size / sizeof(struct bpf_stack_build_id)
112 		    > sysctl_perf_event_max_stack)
113 			return ERR_PTR(-EINVAL);
114 	} else if (value_size / 8 > sysctl_perf_event_max_stack)
115 		return ERR_PTR(-EINVAL);
116 
117 	/* hash table size must be power of 2; roundup_pow_of_two() can overflow
118 	 * into UB on 32-bit arches, so check that first
119 	 */
120 	if (attr->max_entries > 1UL << 31)
121 		return ERR_PTR(-E2BIG);
122 
123 	n_buckets = roundup_pow_of_two(attr->max_entries);
124 
125 	cost = n_buckets * sizeof(struct stack_map_bucket *) + sizeof(*smap);
126 	smap = bpf_map_area_alloc(cost, bpf_map_attr_numa_node(attr));
127 	if (!smap)
128 		return ERR_PTR(-ENOMEM);
129 
130 	bpf_map_init_from_attr(&smap->map, attr);
131 	smap->n_buckets = n_buckets;
132 
133 	err = get_callchain_buffers(sysctl_perf_event_max_stack);
134 	if (err)
135 		goto free_smap;
136 
137 	err = prealloc_elems_and_freelist(smap);
138 	if (err)
139 		goto put_buffers;
140 
141 	return &smap->map;
142 
143 put_buffers:
144 	put_callchain_buffers();
145 free_smap:
146 	bpf_map_area_free(smap);
147 	return ERR_PTR(err);
148 }
149 
150 static int fetch_build_id(struct vm_area_struct *vma, unsigned char *build_id, bool may_fault)
151 {
152 	return may_fault ? build_id_parse(vma, build_id, NULL)
153 			 : build_id_parse_nofault(vma, build_id, NULL);
154 }
155 
156 static inline void stack_map_build_id_set_ip(struct bpf_stack_build_id *id)
157 {
158 	id->status = BPF_STACK_BUILD_ID_IP;
159 	memset(id->build_id, 0, BUILD_ID_SIZE_MAX);
160 }
161 
162 static inline u64 stack_map_build_id_offset(unsigned long vm_pgoff,
163 					    unsigned long vm_start, u64 ip)
164 {
165 	return (vm_pgoff << PAGE_SHIFT) + ip - vm_start;
166 }
167 
168 static inline void stack_map_build_id_set_valid(struct bpf_stack_build_id *id,
169 						u64 offset,
170 						const unsigned char *build_id)
171 {
172 	id->status = BPF_STACK_BUILD_ID_VALID;
173 	id->offset = offset;
174 	if (id->build_id != build_id)
175 		memcpy(id->build_id, build_id, BUILD_ID_SIZE_MAX);
176 }
177 
178 /*
179  * A cached VMA lookup result. The range [vm_start, vm_end) is always set.
180  * vm_pgoff, file, build_id are set only when the build ID was resolved.
181  * Zero vm_end marks the slot empty. build_id aliases the id_offs[] entry.
182  */
183 struct stack_map_cached_vma {
184 	unsigned long vm_start;
185 	unsigned long vm_end;
186 	unsigned long vm_pgoff;
187 	struct file *file; /* pinned in the sleepable path; NULL otherwise */
188 	const unsigned char *build_id;
189 };
190 
191 /*
192  * Per stack_map_get_build_id_offset() call cache of the last VMA with a build ID
193  * resolved and the last VMA with no usable build ID. Adjacent stack frames tend
194  * to land in the same VMA or the same backing file, so caching the last result
195  * of each kind lets us skip unnecessary VMA lookups and build ID parse calls.
196  * Keeping the two slots independent means a build-ID-less VMA doesn't evict the
197  * last resolved build ID.
198  */
199 struct stack_map_build_id_cache {
200 	struct stack_map_cached_vma resolved;
201 	struct stack_map_cached_vma unresolved;
202 };
203 
204 /*
205  * Fill @id from a cached range covering @ip. On a hit this writes @id (resolved
206  * range -> build ID + offset, unresolved range -> raw ip) and returns 0; on a
207  * miss it leaves @id untouched and returns -ENOENT.
208  */
209 static int stack_map_build_id_set_from_cache(struct stack_map_build_id_cache *cache,
210 					     struct bpf_stack_build_id *id, u64 ip)
211 {
212 	unsigned long vm_start, vm_end, vm_pgoff;
213 	u64 offset;
214 
215 	vm_start = cache->resolved.vm_start;
216 	vm_end = cache->resolved.vm_end;
217 	if (vm_end && ip >= vm_start && ip < vm_end) {
218 		vm_pgoff = cache->resolved.vm_pgoff;
219 		offset = stack_map_build_id_offset(vm_pgoff, vm_start, ip);
220 		stack_map_build_id_set_valid(id, offset, cache->resolved.build_id);
221 		return 0;
222 	}
223 
224 	vm_start = cache->unresolved.vm_start;
225 	vm_end = cache->unresolved.vm_end;
226 	if (vm_end && ip >= vm_start && ip < vm_end) {
227 		stack_map_build_id_set_ip(id);
228 		return 0;
229 	}
230 
231 	return -ENOENT;
232 }
233 
234 /*
235  * Record @vma's build ID as the last resolved one. @file is the pinned backing
236  * file in the sleepable path (released when evicted), or NULL otherwise.
237  */
238 static void stack_map_build_id_cache_set_resolved(struct stack_map_build_id_cache *cache,
239 						  struct file *file,
240 						  const unsigned char *build_id,
241 						  unsigned long vm_start,
242 						  unsigned long vm_end,
243 						  unsigned long vm_pgoff)
244 {
245 	if (cache->resolved.file)
246 		fput(cache->resolved.file);
247 	cache->resolved = (struct stack_map_cached_vma){
248 		.vm_start = vm_start,
249 		.vm_end = vm_end,
250 		.vm_pgoff = vm_pgoff,
251 		.file = file,
252 		.build_id = build_id,
253 	};
254 }
255 
256 /* Record [vm_start, vm_end) as a range with no usable build ID. */
257 static void stack_map_build_id_cache_set_unresolved(struct stack_map_build_id_cache *cache,
258 						    unsigned long vm_start,
259 						    unsigned long vm_end)
260 {
261 	cache->unresolved = (struct stack_map_cached_vma){
262 		.vm_start = vm_start,
263 		.vm_end = vm_end,
264 	};
265 }
266 
267 struct stack_map_vma_lock {
268 	struct vm_area_struct *vma;
269 	struct mm_struct *mm;
270 };
271 
272 /*
273  * Acquire a stable read-side reference on the VMA covering @ip.
274  *
275  * On NOMMU configurations, returns with the mmap_lock held.  If the MMU
276  * is enabled, the per-VMA lock will be held instead.  The lock
277  * should be released with stack_map_unlock_vma() which will release the
278  * appropriate lock.  Once the lock is released, the VMA may be freed.
279  *
280  * Returns NULL on failure, in which case no lock is held.
281  */
282 static struct vm_area_struct *
283 stack_map_lock_vma(struct stack_map_vma_lock *lock, unsigned long ip)
284 {
285 	struct mm_struct *mm = lock->mm;
286 	struct vm_area_struct *vma;
287 
288 	vma = lock_vma_under_rcu(mm, ip);
289 	if (vma) {
290 		lock->vma = vma;
291 		return vma;
292 	}
293 
294 	/*
295 	 * Taking mmap_read_lock() is unsafe here, because the caller BPF
296 	 * program might already hold it, causing a deadlock.
297 	 */
298 	if (!mmap_read_trylock(mm))
299 		return NULL;
300 
301 	vma = vma_lookup(mm, ip);
302 	if (!vma) {
303 		mmap_read_unlock(mm);
304 		return NULL;
305 	}
306 
307 #ifdef CONFIG_MMU
308 	if (!vma_start_read_locked(vma)) {
309 		mmap_read_unlock(mm);
310 		return NULL;
311 	}
312 	mmap_read_unlock(mm);
313 #endif
314 	lock->vma = vma;
315 	return vma;
316 }
317 
318 static void stack_map_unlock_vma(struct stack_map_vma_lock *lock)
319 {
320 #ifdef CONFIG_MMU
321 	vma_end_read(lock->vma);
322 #else
323 	mmap_read_unlock(lock->mm);
324 #endif
325 	lock->vma = NULL;
326 }
327 
328 static void stack_map_get_build_id_offset_sleepable(struct bpf_stack_build_id *id_offs,
329 						    u32 trace_nr)
330 {
331 	struct stack_map_vma_lock lock = { .mm = current->mm };
332 	struct stack_map_build_id_cache cache = {};
333 	struct stack_map_cached_vma *res = &cache.resolved;
334 	unsigned long vm_pgoff, vm_start, vm_end;
335 	struct vm_area_struct *vma;
336 	struct file *file;
337 	u64 offset;
338 	u64 ip;
339 
340 	for (u32 i = 0; i < trace_nr; i++) {
341 		ip = READ_ONCE(id_offs[i].ip);
342 
343 		if (!stack_map_build_id_set_from_cache(&cache, &id_offs[i], ip))
344 			continue;
345 
346 		vma = stack_map_lock_vma(&lock, ip);
347 		if (!vma) {
348 			stack_map_build_id_set_ip(&id_offs[i]);
349 			continue;
350 		}
351 
352 		vm_pgoff = vma->vm_pgoff;
353 		vm_start = vma->vm_start;
354 		vm_end = vma->vm_end;
355 
356 		if (vma_is_anonymous(vma) || !vma->vm_file) {
357 			stack_map_unlock_vma(&lock);
358 			stack_map_build_id_set_ip(&id_offs[i]);
359 			stack_map_build_id_cache_set_unresolved(&cache, vm_start, vm_end);
360 			continue;
361 		}
362 
363 		file = vma->vm_file;
364 		offset = stack_map_build_id_offset(vm_pgoff, vm_start, ip);
365 
366 		/*
367 		 * Same backing file as the last resolved VMA (another mapping
368 		 * of the same ELF binary): reuse its build_id without re-parsing.
369 		 */
370 		if (file == res->file) {
371 			stack_map_unlock_vma(&lock);
372 			stack_map_build_id_set_valid(&id_offs[i], offset, res->build_id);
373 			res->vm_start = vm_start;
374 			res->vm_end = vm_end;
375 			res->vm_pgoff = vm_pgoff;
376 			continue;
377 		}
378 
379 		file = get_file(file);
380 		stack_map_unlock_vma(&lock);
381 
382 		/* build_id_parse_file() may block on filesystem reads */
383 		if (build_id_parse_file(file, id_offs[i].build_id, NULL)) {
384 			stack_map_build_id_set_ip(&id_offs[i]);
385 			fput(file);
386 			stack_map_build_id_cache_set_unresolved(&cache, vm_start, vm_end);
387 			continue;
388 		}
389 
390 		stack_map_build_id_set_valid(&id_offs[i], offset, id_offs[i].build_id);
391 		stack_map_build_id_cache_set_resolved(&cache, file, id_offs[i].build_id,
392 						      vm_start, vm_end, vm_pgoff);
393 	}
394 
395 	if (res->file)
396 		fput(res->file);
397 }
398 
399 /*
400  * Expects all id_offs[i].ip values to be set to correct initial IPs.
401  * They will be subsequently:
402  *   - either adjusted in place to a file offset, if build ID fetching
403  *     succeeds; in this case id_offs[i].build_id is set to correct build ID,
404  *     and id_offs[i].status is set to BPF_STACK_BUILD_ID_VALID;
405  *   - or IP will be kept intact, if build ID fetching failed; in this case
406  *     id_offs[i].build_id is zeroed out and id_offs[i].status is set to
407  *     BPF_STACK_BUILD_ID_IP.
408  */
409 static void stack_map_get_build_id_offset(struct bpf_stack_build_id *id_offs,
410 					  u32 trace_nr, bool user, bool may_fault)
411 {
412 	struct mmap_unlock_irq_work *work;
413 	bool has_user_ctx = user && current && current->mm;
414 	struct stack_map_build_id_cache cache = {};
415 	struct vm_area_struct *vma;
416 	int i;
417 
418 	if (may_fault && has_user_ctx) {
419 		stack_map_get_build_id_offset_sleepable(id_offs, trace_nr);
420 		return;
421 	}
422 
423 	if (!has_user_ctx)
424 		goto fallback;
425 
426 	work = bpf_mmap_unlock_guard_get();
427 	if (IS_ERR(work))
428 		goto fallback;
429 
430 	if (!mmap_read_trylock(current->mm)) {
431 		bpf_mmap_unlock_guard_put(work);
432 		goto fallback;
433 	}
434 
435 	for (i = 0; i < trace_nr; i++) {
436 		u64 ip = READ_ONCE(id_offs[i].ip);
437 
438 		if (!stack_map_build_id_set_from_cache(&cache, &id_offs[i], ip))
439 			continue;
440 
441 		vma = find_vma(current->mm, ip);
442 		if (!vma || vma_is_anonymous(vma) ||
443 		    fetch_build_id(vma, id_offs[i].build_id, may_fault)) {
444 			/* per entry fall back to ips; cache build-ID-less range */
445 			stack_map_build_id_set_ip(&id_offs[i]);
446 			if (vma)
447 				stack_map_build_id_cache_set_unresolved(&cache,
448 						vma->vm_start, vma->vm_end);
449 			continue;
450 		}
451 		/*
452 		 * mmap_lock is held for the whole loop, so the cached VMA
453 		 * fields stay valid; no file pinning is needed here.
454 		 */
455 		stack_map_build_id_set_valid(&id_offs[i],
456 			stack_map_build_id_offset(vma->vm_pgoff, vma->vm_start, ip),
457 			id_offs[i].build_id);
458 		stack_map_build_id_cache_set_resolved(&cache, NULL, id_offs[i].build_id,
459 						      vma->vm_start, vma->vm_end,
460 						      vma->vm_pgoff);
461 	}
462 	bpf_mmap_unlock_mm(work, current->mm);
463 	return;
464 
465 fallback:
466 	/* cannot access current->mm, fall back to ips */
467 	for (i = 0; i < trace_nr; i++)
468 		stack_map_build_id_set_ip(&id_offs[i]);
469 }
470 
471 static struct perf_callchain_entry *
472 get_callchain_entry_for_task(struct task_struct *task, u32 max_depth)
473 {
474 #ifdef CONFIG_STACKTRACE
475 	struct perf_callchain_entry *entry;
476 	int rctx;
477 
478 	entry = get_callchain_entry(&rctx);
479 
480 	if (!entry)
481 		return NULL;
482 
483 	entry->nr = stack_trace_save_tsk(task, (unsigned long *)entry->ip,
484 					 max_depth, 0);
485 
486 	/* stack_trace_save_tsk() works on unsigned long array, while
487 	 * perf_callchain_entry uses u64 array. For 32-bit systems, it is
488 	 * necessary to fix this mismatch.
489 	 */
490 	if (__BITS_PER_LONG != 64) {
491 		unsigned long *from = (unsigned long *) entry->ip;
492 		u64 *to = entry->ip;
493 		int i;
494 
495 		/* copy data from the end to avoid using extra buffer */
496 		for (i = entry->nr - 1; i >= 0; i--)
497 			to[i] = (u64)(from[i]);
498 	}
499 
500 	put_callchain_entry(rctx);
501 
502 	return entry;
503 #else /* CONFIG_STACKTRACE */
504 	return NULL;
505 #endif
506 }
507 
508 struct stackid {
509 	struct stack_map_bucket *bucket;
510 	const u64 *ips;
511 	u32  nr;
512 	u32  len;
513 	u32  hash;
514 	u32  id;
515 	bool hash_matches;
516 };
517 
518 static int stackid_init(struct stackid *stackid, struct bpf_map *map,
519 			const struct perf_callchain_entry *trace, u32 trace_nr, u64 flags)
520 {
521 	struct bpf_stack_map *smap = container_of(map, struct bpf_stack_map, map);
522 	u32 skip = flags & BPF_F_SKIP_FIELD_MASK;
523 	u32 max_depth;
524 
525 	max_depth = stack_map_calculate_max_depth(map->value_size, stack_map_data_size(map), flags);
526 	/* trace_nr can be above max_depth and max_depth below skip: clamp first */
527 	trace_nr = min_t(u32, trace_nr, max_depth);
528 	if (trace_nr <= skip)
529 		/* skipping more than usable stack trace */
530 		return -EFAULT;
531 
532 	stackid->nr = trace_nr - skip;
533 	stackid->len = stackid->nr * sizeof(u64);
534 	stackid->ips = trace->ip + skip;
535 	stackid->hash = jhash2((const u32 *)stackid->ips, stackid->len / sizeof(u32), 0);
536 	stackid->id = stackid->hash & (smap->n_buckets - 1);
537 	stackid->bucket = READ_ONCE(smap->buckets[stackid->id]);
538 	stackid->hash_matches = stackid->bucket && stackid->bucket->hash == stackid->hash;
539 	return 0;
540 }
541 
542 static int stackid_fastpath(struct stackid *stackid, struct bpf_map *map,
543 			    const struct perf_callchain_entry *trace, u32 trace_nr,
544 			    u64 flags)
545 {
546 	int err;
547 
548 	err = stackid_init(stackid, map, trace, trace_nr, flags);
549 	if (err)
550 		return err;
551 
552 	/* fast cmp */
553 	if (stackid->hash_matches && flags & BPF_F_FAST_STACK_CMP)
554 		return stackid->id;
555 
556 	if (stack_map_use_build_id(map))
557 		return -ENOENT;
558 	if (stackid->hash_matches && stackid->bucket->nr == stackid->nr &&
559 	    memcmp(stackid->bucket->data, stackid->ips, stackid->len) == 0)
560 		return stackid->id;
561 	if (stackid->bucket && !(flags & BPF_F_REUSE_STACKID))
562 		return -EEXIST;
563 	return -ENOENT;
564 }
565 
566 static struct stack_map_bucket *
567 stackid_new_bucket(struct stackid *stackid, struct bpf_map *map)
568 {
569 	struct bpf_stack_map *smap = container_of(map, struct bpf_stack_map, map);
570 	struct bpf_stack_build_id *id_offs;
571 	struct stack_map_bucket *bucket;
572 	u32 i;
573 
574 	bucket = (struct stack_map_bucket *) pcpu_freelist_pop(&smap->freelist);
575 	if (unlikely(!bucket))
576 		return NULL;
577 
578 	if (stack_map_use_build_id(map)) {
579 		id_offs = (struct bpf_stack_build_id *)bucket->data;
580 		for (i = 0; i < stackid->nr; i++)
581 			id_offs[i].ip = stackid->ips[i];
582 	} else {
583 		memcpy(bucket->data, stackid->ips, stackid->len);
584 	}
585 
586 	bucket->hash = stackid->hash;
587 	bucket->nr = stackid->nr;
588 	return bucket;
589 }
590 
591 static long stackid_install(struct stackid *stackid, struct bpf_map *map,
592 			    struct stack_map_bucket *new_bucket, u64 flags)
593 {
594 	struct bpf_stack_map *smap = container_of(map, struct bpf_stack_map, map);
595 	bool user = flags & BPF_F_USER_STACK;
596 	struct stack_map_bucket *old_bucket;
597 	u32 trace_len;
598 
599 	if (stack_map_use_build_id(map)) {
600 		struct bpf_stack_build_id *id_offs;
601 
602 		id_offs = (struct bpf_stack_build_id *)new_bucket->data;
603 		stack_map_get_build_id_offset(id_offs, stackid->nr, user, false /* !may_fault */);
604 		trace_len = stackid->nr * sizeof(struct bpf_stack_build_id);
605 		if (stackid->hash_matches && stackid->bucket->nr == stackid->nr &&
606 		    memcmp(stackid->bucket->data, new_bucket->data, trace_len) == 0) {
607 			pcpu_freelist_push(&smap->freelist, &new_bucket->fnode);
608 			return stackid->id;
609 		}
610 		if (stackid->bucket && !(flags & BPF_F_REUSE_STACKID)) {
611 			pcpu_freelist_push(&smap->freelist, &new_bucket->fnode);
612 			return -EEXIST;
613 		}
614 	}
615 
616 	old_bucket = xchg(&smap->buckets[stackid->id], new_bucket);
617 	if (old_bucket)
618 		pcpu_freelist_push(&smap->freelist, &old_bucket->fnode);
619 	return stackid->id;
620 }
621 
622 BPF_CALL_3(bpf_get_stackid, struct pt_regs *, regs, struct bpf_map *, map,
623 	   u64, flags)
624 {
625 	u32 elem_size = stack_map_data_size(map);
626 	bool user = flags & BPF_F_USER_STACK;
627 	struct stack_map_bucket *new_bucket;
628 	struct perf_callchain_entry *trace;
629 	struct stackid stackid;
630 	bool kernel = !user;
631 	u32 max_depth;
632 	int err;
633 
634 	if (unlikely(flags & ~(BPF_F_SKIP_FIELD_MASK | BPF_F_USER_STACK |
635 			       BPF_F_FAST_STACK_CMP | BPF_F_REUSE_STACKID)))
636 		return -EINVAL;
637 
638 	max_depth = stack_map_calculate_max_depth(map->value_size, elem_size, flags);
639 
640 	scoped_guard(preempt) {
641 		trace = get_perf_callchain(regs, kernel, user, max_depth,
642 					   false, false, 0);
643 		if (unlikely(!trace))
644 			/* couldn't fetch the stack trace */
645 			return -EFAULT;
646 
647 		/* the entry is released already, an NMI can change trace->nr */
648 		err = stackid_fastpath(&stackid, map, trace, READ_ONCE(trace->nr), flags);
649 		if (err != -ENOENT)
650 			return err;
651 
652 		new_bucket = stackid_new_bucket(&stackid, map);
653 		if (!new_bucket)
654 			return -ENOMEM;
655 	}
656 
657 	return stackid_install(&stackid, map, new_bucket, flags);
658 }
659 
660 const struct bpf_func_proto bpf_get_stackid_proto = {
661 	.func		= bpf_get_stackid,
662 	.gpl_only	= true,
663 	.ret_type	= RET_INTEGER,
664 	.arg1_type	= ARG_PTR_TO_CTX,
665 	.arg2_type	= ARG_CONST_MAP_PTR,
666 	.arg3_type	= ARG_ANYTHING,
667 };
668 
669 static __u64 count_kernel_ip(const struct perf_callchain_entry *trace)
670 {
671 	__u64 nr_kernel = 0;
672 
673 	while (nr_kernel < trace->nr) {
674 		if (trace->ip[nr_kernel] == PERF_CONTEXT_USER)
675 			break;
676 		nr_kernel++;
677 	}
678 	return nr_kernel;
679 }
680 
681 BPF_CALL_3(bpf_get_stackid_pe, struct bpf_perf_event_data_kern *, ctx,
682 	   struct bpf_map *, map, u64, flags)
683 {
684 	const struct perf_callchain_entry *trace;
685 	struct perf_event *event = ctx->event;
686 	struct stack_map_bucket *new_bucket;
687 	struct stackid stackid;
688 	bool kernel, user;
689 	__u64 nr_kernel;
690 	u32 trace_nr;
691 	int ret;
692 
693 	/* perf_sample_data doesn't have callchain, use bpf_get_stackid */
694 	if (!(event->attr.sample_type & PERF_SAMPLE_CALLCHAIN))
695 		return bpf_get_stackid((unsigned long)(ctx->regs),
696 				       (unsigned long) map, flags, 0, 0);
697 
698 	if (unlikely(flags & ~(BPF_F_SKIP_FIELD_MASK | BPF_F_USER_STACK |
699 			       BPF_F_FAST_STACK_CMP | BPF_F_REUSE_STACKID)))
700 		return -EINVAL;
701 
702 	user = flags & BPF_F_USER_STACK;
703 	kernel = !user;
704 
705 	trace = ctx->data->callchain;
706 	if (unlikely(!trace))
707 		return -EFAULT;
708 
709 	nr_kernel = count_kernel_ip(trace);
710 
711 	if (kernel) {
712 		trace_nr = nr_kernel;
713 	} else { /* user */
714 		u64 skip = flags & BPF_F_SKIP_FIELD_MASK;
715 
716 		trace_nr = trace->nr;
717 		skip += nr_kernel;
718 		if (skip > BPF_F_SKIP_FIELD_MASK)
719 			return -EFAULT;
720 
721 		flags = (flags & ~BPF_F_SKIP_FIELD_MASK) | skip;
722 	}
723 
724 	ret = stackid_fastpath(&stackid, map, trace, trace_nr, flags);
725 	if (ret != -ENOENT)
726 		return ret;
727 
728 	new_bucket = stackid_new_bucket(&stackid, map);
729 	if (new_bucket)
730 		return stackid_install(&stackid, map, new_bucket, flags);
731 	return -ENOMEM;
732 }
733 
734 const struct bpf_func_proto bpf_get_stackid_proto_pe = {
735 	.func		= bpf_get_stackid_pe,
736 	.gpl_only	= false,
737 	.ret_type	= RET_INTEGER,
738 	.arg1_type	= ARG_PTR_TO_CTX,
739 	.arg2_type	= ARG_CONST_MAP_PTR,
740 	.arg3_type	= ARG_ANYTHING,
741 };
742 
743 static u32 callchain_store(const struct perf_callchain_entry *trace, u32 trace_nr,
744 			   void *buf, u32 elem_size, u64 flags)
745 {
746 	bool user_build_id = flags & BPF_F_USER_BUILD_ID;
747 	u32 skip = flags & BPF_F_SKIP_FIELD_MASK;
748 	const u64 *ips;
749 	u32 copy_len;
750 
751 	trace_nr = trace_nr - skip;
752 	copy_len = trace_nr * elem_size;
753 
754 	ips = trace->ip + skip;
755 	if (user_build_id) {
756 		struct bpf_stack_build_id *id_offs = buf;
757 
758 		for (u32 i = 0; i < trace_nr; i++)
759 			id_offs[i].ip = ips[i];
760 	} else {
761 		memcpy(buf, ips, copy_len);
762 	}
763 	return trace_nr;
764 }
765 
766 static long callchain_finalize(void *buf, u32 size, u32 trace_nr, u32 elem_size,
767 			       u64 flags, bool may_fault)
768 {
769 	bool user_build_id = flags & BPF_F_USER_BUILD_ID;
770 	bool user = flags & BPF_F_USER_STACK;
771 	u32 copy_len = trace_nr * elem_size;
772 
773 	if (user_build_id)
774 		stack_map_get_build_id_offset(buf, trace_nr, user, may_fault);
775 
776 	if (size > copy_len)
777 		memset(buf + copy_len, 0, size - copy_len);
778 	return copy_len;
779 }
780 
781 static long __bpf_get_stack(struct pt_regs *regs, struct task_struct *task,
782 			    void *buf, u32 size, u64 flags, bool may_fault)
783 {
784 	bool user_build_id = flags & BPF_F_USER_BUILD_ID;
785 	bool crosstask = task && task != current;
786 	u32 skip = flags & BPF_F_SKIP_FIELD_MASK;
787 	bool user = flags & BPF_F_USER_STACK;
788 	struct perf_callchain_entry *trace;
789 	u32 trace_nr, elem_size, max_depth;
790 	bool kernel = !user;
791 	int err = -EINVAL;
792 
793 	if (unlikely(flags & ~(BPF_F_SKIP_FIELD_MASK | BPF_F_USER_STACK |
794 			       BPF_F_USER_BUILD_ID)))
795 		goto clear;
796 	if (kernel && user_build_id)
797 		goto clear;
798 
799 	elem_size = user_build_id ? sizeof(struct bpf_stack_build_id) : sizeof(u64);
800 	if (unlikely(size % elem_size))
801 		goto clear;
802 
803 	/* cannot get valid user stack for task without user_mode regs */
804 	if (task && user && !user_mode(regs))
805 		goto err_fault;
806 
807 	/* get_perf_callchain does not support crosstask user stack walking
808 	 * but returns an empty stack instead of NULL.
809 	 */
810 	if (crosstask && user) {
811 		err = -EOPNOTSUPP;
812 		goto clear;
813 	}
814 
815 	max_depth = stack_map_calculate_max_depth(size, elem_size, flags);
816 
817 	preempt_disable();
818 	if (may_fault)
819 		rcu_read_lock(); /* need RCU for perf's callchain below */
820 
821 	if (kernel && task) {
822 		trace = get_callchain_entry_for_task(task, max_depth);
823 	} else {
824 		trace = get_perf_callchain(regs, kernel, user, max_depth,
825 					   crosstask, false, 0);
826 	}
827 
828 	if (unlikely(!trace))
829 		goto err_unlock;
830 
831 	/*
832 	 * trace->nr can be above max_depth. The per-CPU entry is released
833 	 * already: a tracing program or an NMI which takes a callchain in the
834 	 * same context before the copy below reuses it. And the unwinders of
835 	 * PowerPC store context markers on top of max_depth.
836 	 */
837 	trace_nr = min_t(u32, READ_ONCE(trace->nr), max_depth);
838 	if (trace_nr < skip)
839 		goto err_unlock;
840 
841 	trace_nr = callchain_store(trace, trace_nr, buf, elem_size, flags);
842 
843 	/* trace should not be dereferenced after this point */
844 	if (may_fault)
845 		rcu_read_unlock();
846 	preempt_enable();
847 
848 	return callchain_finalize(buf, size, trace_nr, elem_size, flags, may_fault);
849 
850 err_unlock:
851 	if (may_fault)
852 		rcu_read_unlock();
853 	preempt_enable();
854 err_fault:
855 	err = -EFAULT;
856 clear:
857 	memset(buf, 0, size);
858 	return err;
859 }
860 
861 BPF_CALL_4(bpf_get_stack, struct pt_regs *, regs, void *, buf, u32, size,
862 	   u64, flags)
863 {
864 	return __bpf_get_stack(regs, NULL, buf, size, flags, false /* !may_fault */);
865 }
866 
867 const struct bpf_func_proto bpf_get_stack_proto = {
868 	.func		= bpf_get_stack,
869 	.gpl_only	= true,
870 	.ret_type	= RET_INTEGER,
871 	.arg1_type	= ARG_PTR_TO_CTX,
872 	.arg2_type	= ARG_PTR_TO_UNINIT_MEM,
873 	.arg3_type	= ARG_MEM_SIZE_OR_ZERO,
874 	.arg4_type	= ARG_ANYTHING,
875 };
876 
877 BPF_CALL_4(bpf_get_stack_sleepable, struct pt_regs *, regs, void *, buf, u32, size,
878 	   u64, flags)
879 {
880 	return __bpf_get_stack(regs, NULL, buf, size, flags, true /* may_fault */);
881 }
882 
883 const struct bpf_func_proto bpf_get_stack_sleepable_proto = {
884 	.func		= bpf_get_stack_sleepable,
885 	.gpl_only	= true,
886 	.might_sleep	= true,
887 	.ret_type	= RET_INTEGER,
888 	.arg1_type	= ARG_PTR_TO_CTX,
889 	.arg2_type	= ARG_PTR_TO_UNINIT_MEM,
890 	.arg3_type	= ARG_MEM_SIZE_OR_ZERO,
891 	.arg4_type	= ARG_ANYTHING,
892 };
893 
894 static long __bpf_get_task_stack(struct task_struct *task, void *buf, u32 size,
895 				 u64 flags, bool may_fault)
896 {
897 	struct pt_regs *regs;
898 	long res = -EINVAL;
899 
900 	if (!try_get_task_stack(task)) {
901 		memset(buf, 0, size);
902 		return -EFAULT;
903 	}
904 
905 	regs = task_pt_regs(task);
906 	if (regs)
907 		res = __bpf_get_stack(regs, task, buf, size, flags, may_fault);
908 	else
909 		memset(buf, 0, size);
910 	put_task_stack(task);
911 	return res;
912 }
913 
914 BPF_CALL_4(bpf_get_task_stack, struct task_struct *, task, void *, buf,
915 	   u32, size, u64, flags)
916 {
917 	return __bpf_get_task_stack(task, buf, size, flags, false /* !may_fault */);
918 }
919 
920 const struct bpf_func_proto bpf_get_task_stack_proto = {
921 	.func		= bpf_get_task_stack,
922 	.gpl_only	= false,
923 	.ret_type	= RET_INTEGER,
924 	.arg1_type	= ARG_PTR_TO_BTF_ID,
925 	.arg1_btf_id	= &btf_tracing_ids[BTF_TRACING_TYPE_TASK],
926 	.arg2_type	= ARG_PTR_TO_UNINIT_MEM,
927 	.arg3_type	= ARG_MEM_SIZE_OR_ZERO,
928 	.arg4_type	= ARG_ANYTHING,
929 };
930 
931 BPF_CALL_4(bpf_get_task_stack_sleepable, struct task_struct *, task, void *, buf,
932 	   u32, size, u64, flags)
933 {
934 	return __bpf_get_task_stack(task, buf, size, flags, true /* !may_fault */);
935 }
936 
937 const struct bpf_func_proto bpf_get_task_stack_sleepable_proto = {
938 	.func		= bpf_get_task_stack_sleepable,
939 	.gpl_only	= false,
940 	.might_sleep	= true,
941 	.ret_type	= RET_INTEGER,
942 	.arg1_type	= ARG_PTR_TO_BTF_ID,
943 	.arg1_btf_id	= &btf_tracing_ids[BTF_TRACING_TYPE_TASK],
944 	.arg2_type	= ARG_PTR_TO_UNINIT_MEM,
945 	.arg3_type	= ARG_MEM_SIZE_OR_ZERO,
946 	.arg4_type	= ARG_ANYTHING,
947 };
948 
949 static int __bpf_get_stack_pe(const struct perf_callchain_entry *trace, u32 trace_nr,
950 			      void *buf, u32 size, u64 flags)
951 {
952 	bool user_build_id = flags & BPF_F_USER_BUILD_ID;
953 	u64 skip = flags & BPF_F_SKIP_FIELD_MASK;
954 	bool user = flags & BPF_F_USER_STACK;
955 	u32 elem_size, max_depth, nr_trace;
956 	bool kernel = !user;
957 
958 	if (kernel && user_build_id)
959 		return -EINVAL;
960 
961 	elem_size = user_build_id ? sizeof(struct bpf_stack_build_id) : sizeof(u64);
962 	if (unlikely(size % elem_size))
963 		return -EINVAL;
964 
965 	max_depth = stack_map_calculate_max_depth(size, elem_size, flags);
966 	trace_nr = min_t(u32, trace_nr, max_depth);
967 
968 	if (trace_nr < skip)
969 		return -EFAULT;
970 
971 	nr_trace = callchain_store(trace, trace_nr, buf, elem_size, flags);
972 	return callchain_finalize(buf, size, nr_trace, elem_size, flags, false /* !may_fault */);
973 }
974 
975 BPF_CALL_4(bpf_get_stack_pe, struct bpf_perf_event_data_kern *, ctx,
976 	   void *, buf, u32, size, u64, flags)
977 {
978 	struct pt_regs *regs = (struct pt_regs *)(ctx->regs);
979 	const struct perf_callchain_entry *trace;
980 	struct perf_event *event = ctx->event;
981 	bool kernel, user;
982 	int err = -EINVAL;
983 	__u64 nr_kernel;
984 
985 	if (!(event->attr.sample_type & PERF_SAMPLE_CALLCHAIN))
986 		return __bpf_get_stack(regs, NULL, buf, size, flags, false /* !may_fault */);
987 
988 	if (unlikely(flags & ~(BPF_F_SKIP_FIELD_MASK | BPF_F_USER_STACK |
989 			       BPF_F_USER_BUILD_ID)))
990 		goto clear;
991 
992 	user = flags & BPF_F_USER_STACK;
993 	kernel = !user;
994 
995 	err = -EFAULT;
996 	trace = ctx->data->callchain;
997 	if (unlikely(!trace))
998 		goto clear;
999 
1000 	nr_kernel = count_kernel_ip(trace);
1001 
1002 	if (kernel) {
1003 		err = __bpf_get_stack_pe(trace, nr_kernel, buf, size, flags);
1004 	} else { /* user */
1005 		u64 skip = flags & BPF_F_SKIP_FIELD_MASK;
1006 
1007 		skip += nr_kernel;
1008 		if (skip > BPF_F_SKIP_FIELD_MASK)
1009 			goto clear;
1010 		flags = (flags & ~BPF_F_SKIP_FIELD_MASK) | skip;
1011 		err = __bpf_get_stack_pe(trace, trace->nr, buf, size, flags);
1012 	}
1013 
1014 clear:
1015 	if (err < 0)
1016 		memset(buf, 0, size);
1017 	return err;
1018 
1019 }
1020 
1021 const struct bpf_func_proto bpf_get_stack_proto_pe = {
1022 	.func		= bpf_get_stack_pe,
1023 	.gpl_only	= true,
1024 	.ret_type	= RET_INTEGER,
1025 	.arg1_type	= ARG_PTR_TO_CTX,
1026 	.arg2_type	= ARG_PTR_TO_UNINIT_MEM,
1027 	.arg3_type	= ARG_MEM_SIZE_OR_ZERO,
1028 	.arg4_type	= ARG_ANYTHING,
1029 };
1030 
1031 /* Called from eBPF program */
1032 static void *stack_map_lookup_elem(struct bpf_map *map, void *key)
1033 {
1034 	return ERR_PTR(-EOPNOTSUPP);
1035 }
1036 
1037 /* Called from syscall */
1038 static int stack_map_lookup_and_delete_elem(struct bpf_map *map, void *key,
1039 					    void *value, u64 flags)
1040 {
1041 	return bpf_stackmap_extract(map, key, value, true);
1042 }
1043 
1044 /* Called from syscall */
1045 int bpf_stackmap_extract(struct bpf_map *map, void *key, void *value,
1046 			 bool delete)
1047 {
1048 	struct bpf_stack_map *smap = container_of(map, struct bpf_stack_map, map);
1049 	struct stack_map_bucket *bucket, *old_bucket;
1050 	u32 id = *(u32 *)key, trace_len;
1051 
1052 	if (unlikely(id >= smap->n_buckets))
1053 		return -ENOENT;
1054 
1055 	bucket = xchg(&smap->buckets[id], NULL);
1056 	if (!bucket)
1057 		return -ENOENT;
1058 
1059 	trace_len = bucket->nr * stack_map_data_size(map);
1060 	memcpy(value, bucket->data, trace_len);
1061 	memset(value + trace_len, 0, map->value_size - trace_len);
1062 
1063 	if (delete)
1064 		old_bucket = bucket;
1065 	else
1066 		old_bucket = xchg(&smap->buckets[id], bucket);
1067 	if (old_bucket)
1068 		pcpu_freelist_push(&smap->freelist, &old_bucket->fnode);
1069 	return 0;
1070 }
1071 
1072 static int stack_map_get_next_key(struct bpf_map *map, void *key,
1073 				  void *next_key)
1074 {
1075 	struct bpf_stack_map *smap = container_of(map,
1076 						  struct bpf_stack_map, map);
1077 	u32 id;
1078 
1079 	WARN_ON_ONCE(!rcu_read_lock_held());
1080 
1081 	if (!key) {
1082 		id = 0;
1083 	} else {
1084 		id = *(u32 *)key;
1085 		if (id >= smap->n_buckets || !smap->buckets[id])
1086 			id = 0;
1087 		else
1088 			id++;
1089 	}
1090 
1091 	while (id < smap->n_buckets && !smap->buckets[id])
1092 		id++;
1093 
1094 	if (id >= smap->n_buckets)
1095 		return -ENOENT;
1096 
1097 	*(u32 *)next_key = id;
1098 	return 0;
1099 }
1100 
1101 static long stack_map_update_elem(struct bpf_map *map, void *key, void *value,
1102 				  u64 map_flags)
1103 {
1104 	return -EINVAL;
1105 }
1106 
1107 /* Called from syscall or from eBPF program */
1108 static long stack_map_delete_elem(struct bpf_map *map, void *key)
1109 {
1110 	struct bpf_stack_map *smap = container_of(map, struct bpf_stack_map, map);
1111 	struct stack_map_bucket *old_bucket;
1112 	u32 id = *(u32 *)key;
1113 
1114 	if (unlikely(id >= smap->n_buckets))
1115 		return -E2BIG;
1116 
1117 	old_bucket = xchg(&smap->buckets[id], NULL);
1118 	if (old_bucket) {
1119 		pcpu_freelist_push(&smap->freelist, &old_bucket->fnode);
1120 		return 0;
1121 	} else {
1122 		return -ENOENT;
1123 	}
1124 }
1125 
1126 /* Called when map->refcnt goes to zero, either from workqueue or from syscall */
1127 static void stack_map_free(struct bpf_map *map)
1128 {
1129 	struct bpf_stack_map *smap = container_of(map, struct bpf_stack_map, map);
1130 
1131 	bpf_map_area_free(smap->elems);
1132 	pcpu_freelist_destroy(&smap->freelist);
1133 	bpf_map_area_free(smap);
1134 	put_callchain_buffers();
1135 }
1136 
1137 static u64 stack_map_mem_usage(const struct bpf_map *map)
1138 {
1139 	struct bpf_stack_map *smap = container_of(map, struct bpf_stack_map, map);
1140 	u64 value_size = map->value_size;
1141 	u64 n_buckets = smap->n_buckets;
1142 	u64 enties = map->max_entries;
1143 	u64 usage = sizeof(*smap);
1144 
1145 	usage += n_buckets * sizeof(struct stack_map_bucket *);
1146 	usage += enties * (sizeof(struct stack_map_bucket) + value_size);
1147 	return usage;
1148 }
1149 
1150 BTF_ID_LIST_SINGLE(stack_trace_map_btf_ids, struct, bpf_stack_map)
1151 const struct bpf_map_ops stack_trace_map_ops = {
1152 	.map_meta_equal = bpf_map_meta_equal,
1153 	.map_alloc = stack_map_alloc,
1154 	.map_free = stack_map_free,
1155 	.map_get_next_key = stack_map_get_next_key,
1156 	.map_lookup_elem = stack_map_lookup_elem,
1157 	.map_lookup_and_delete_elem = stack_map_lookup_and_delete_elem,
1158 	.map_update_elem = stack_map_update_elem,
1159 	.map_delete_elem = stack_map_delete_elem,
1160 	.map_check_btf = map_check_no_btf,
1161 	.map_mem_usage = stack_map_mem_usage,
1162 	.map_btf_id = &stack_trace_map_btf_ids[0],
1163 };
1164