1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * call-path.h: Manipulate a tree data structure containing function call paths 4 * Copyright (c) 2014, Intel Corporation. 5 */ 6 7 #include <linux/rbtree.h> 8 #include <linux/list.h> 9 10 #include "util.h" 11 #include "call-path.h" 12 13 static void call_path__init(struct call_path *cp, struct call_path *parent, 14 struct symbol *sym, u64 ip, bool in_kernel) 15 { 16 cp->parent = parent; 17 cp->sym = sym; 18 cp->ip = sym ? 0 : ip; 19 cp->db_id = 0; 20 cp->in_kernel = in_kernel; 21 RB_CLEAR_NODE(&cp->rb_node); 22 cp->children = RB_ROOT; 23 } 24 25 struct call_path_root *call_path_root__new(void) 26 { 27 struct call_path_root *cpr; 28 29 cpr = zalloc(sizeof(struct call_path_root)); 30 if (!cpr) 31 return NULL; 32 call_path__init(&cpr->call_path, NULL, NULL, 0, false); 33 INIT_LIST_HEAD(&cpr->blocks); 34 return cpr; 35 } 36 37 void call_path_root__free(struct call_path_root *cpr) 38 { 39 struct call_path_block *pos, *n; 40 41 list_for_each_entry_safe(pos, n, &cpr->blocks, node) { 42 list_del(&pos->node); 43 free(pos); 44 } 45 free(cpr); 46 } 47 48 static struct call_path *call_path__new(struct call_path_root *cpr, 49 struct call_path *parent, 50 struct symbol *sym, u64 ip, 51 bool in_kernel) 52 { 53 struct call_path_block *cpb; 54 struct call_path *cp; 55 size_t n; 56 57 if (cpr->next < cpr->sz) { 58 cpb = list_last_entry(&cpr->blocks, struct call_path_block, 59 node); 60 } else { 61 cpb = zalloc(sizeof(struct call_path_block)); 62 if (!cpb) 63 return NULL; 64 list_add_tail(&cpb->node, &cpr->blocks); 65 cpr->sz += CALL_PATH_BLOCK_SIZE; 66 } 67 68 n = cpr->next++ & CALL_PATH_BLOCK_MASK; 69 cp = &cpb->cp[n]; 70 71 call_path__init(cp, parent, sym, ip, in_kernel); 72 73 return cp; 74 } 75 76 struct call_path *call_path__findnew(struct call_path_root *cpr, 77 struct call_path *parent, 78 struct symbol *sym, u64 ip, u64 ks) 79 { 80 struct rb_node **p; 81 struct rb_node *node_parent = NULL; 82 struct call_path *cp; 83 bool in_kernel = ip >= ks; 84 85 if (sym) 86 ip = 0; 87 88 if (!parent) 89 return call_path__new(cpr, parent, sym, ip, in_kernel); 90 91 p = &parent->children.rb_node; 92 while (*p != NULL) { 93 node_parent = *p; 94 cp = rb_entry(node_parent, struct call_path, rb_node); 95 96 if (cp->sym == sym && cp->ip == ip) 97 return cp; 98 99 if (sym < cp->sym || (sym == cp->sym && ip < cp->ip)) 100 p = &(*p)->rb_left; 101 else 102 p = &(*p)->rb_right; 103 } 104 105 cp = call_path__new(cpr, parent, sym, ip, in_kernel); 106 if (!cp) 107 return NULL; 108 109 rb_link_node(&cp->rb_node, node_parent, p); 110 rb_insert_color(&cp->rb_node, &parent->children); 111 112 return cp; 113 } 114