12025cf9eSThomas Gleixner /* SPDX-License-Identifier: GPL-2.0-only */ 2451db126SChris Phlipot /* 3451db126SChris Phlipot * call-path.h: Manipulate a tree data structure containing function call paths 4451db126SChris Phlipot * Copyright (c) 2014, Intel Corporation. 5451db126SChris Phlipot */ 6451db126SChris Phlipot 7451db126SChris Phlipot #ifndef __PERF_CALL_PATH_H 8451db126SChris Phlipot #define __PERF_CALL_PATH_H 9451db126SChris Phlipot 10451db126SChris Phlipot #include <sys/types.h> 11451db126SChris Phlipot 12451db126SChris Phlipot #include <linux/types.h> 13451db126SChris Phlipot #include <linux/rbtree.h> 14451db126SChris Phlipot 15451db126SChris Phlipot /** 16451db126SChris Phlipot * struct call_path - node in list of calls leading to a function call. 17451db126SChris Phlipot * @parent: call path to the parent function call 18451db126SChris Phlipot * @sym: symbol of function called 19451db126SChris Phlipot * @ip: only if sym is null, the ip of the function 20451db126SChris Phlipot * @db_id: id used for db-export 21451db126SChris Phlipot * @in_kernel: whether function is a in the kernel 22451db126SChris Phlipot * @rb_node: node in parent's tree of called functions 23451db126SChris Phlipot * @children: tree of call paths of functions called 24451db126SChris Phlipot * 25451db126SChris Phlipot * In combination with the call_return structure, the call_path structure 26*4d39c89fSIngo Molnar * defines a context-sensitive call-graph. 27451db126SChris Phlipot */ 28451db126SChris Phlipot struct call_path { 29451db126SChris Phlipot struct call_path *parent; 30451db126SChris Phlipot struct symbol *sym; 31451db126SChris Phlipot u64 ip; 32451db126SChris Phlipot u64 db_id; 33451db126SChris Phlipot bool in_kernel; 34451db126SChris Phlipot struct rb_node rb_node; 35451db126SChris Phlipot struct rb_root children; 36451db126SChris Phlipot }; 37451db126SChris Phlipot 38451db126SChris Phlipot #define CALL_PATH_BLOCK_SHIFT 8 39451db126SChris Phlipot #define CALL_PATH_BLOCK_SIZE (1 << CALL_PATH_BLOCK_SHIFT) 40451db126SChris Phlipot #define CALL_PATH_BLOCK_MASK (CALL_PATH_BLOCK_SIZE - 1) 41451db126SChris Phlipot 42451db126SChris Phlipot struct call_path_block { 43451db126SChris Phlipot struct call_path cp[CALL_PATH_BLOCK_SIZE]; 44451db126SChris Phlipot struct list_head node; 45451db126SChris Phlipot }; 46451db126SChris Phlipot 47451db126SChris Phlipot /** 48451db126SChris Phlipot * struct call_path_root - root of all call paths. 49451db126SChris Phlipot * @call_path: root call path 50451db126SChris Phlipot * @blocks: list of blocks to store call paths 51451db126SChris Phlipot * @next: next free space 52451db126SChris Phlipot * @sz: number of spaces 53451db126SChris Phlipot */ 54451db126SChris Phlipot struct call_path_root { 55451db126SChris Phlipot struct call_path call_path; 56451db126SChris Phlipot struct list_head blocks; 57451db126SChris Phlipot size_t next; 58451db126SChris Phlipot size_t sz; 59451db126SChris Phlipot }; 60451db126SChris Phlipot 61451db126SChris Phlipot struct call_path_root *call_path_root__new(void); 62451db126SChris Phlipot void call_path_root__free(struct call_path_root *cpr); 63451db126SChris Phlipot 64451db126SChris Phlipot struct call_path *call_path__findnew(struct call_path_root *cpr, 65451db126SChris Phlipot struct call_path *parent, 66451db126SChris Phlipot struct symbol *sym, u64 ip, u64 ks); 67451db126SChris Phlipot 68451db126SChris Phlipot #endif 69