1 /* 2 * call-path.h: Manipulate a tree data structure containing function call paths 3 * Copyright (c) 2014, Intel Corporation. 4 * 5 * This program is free software; you can redistribute it and/or modify it 6 * under the terms and conditions of the GNU General Public License, 7 * version 2, as published by the Free Software Foundation. 8 * 9 * This program is distributed in the hope it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 12 * more details. 13 * 14 */ 15 16 #include <linux/rbtree.h> 17 #include <linux/list.h> 18 19 #include "util.h" 20 #include "call-path.h" 21 22 static void call_path__init(struct call_path *cp, struct call_path *parent, 23 struct symbol *sym, u64 ip, bool in_kernel) 24 { 25 cp->parent = parent; 26 cp->sym = sym; 27 cp->ip = sym ? 0 : ip; 28 cp->db_id = 0; 29 cp->in_kernel = in_kernel; 30 RB_CLEAR_NODE(&cp->rb_node); 31 cp->children = RB_ROOT; 32 } 33 34 struct call_path_root *call_path_root__new(void) 35 { 36 struct call_path_root *cpr; 37 38 cpr = zalloc(sizeof(struct call_path_root)); 39 if (!cpr) 40 return NULL; 41 call_path__init(&cpr->call_path, NULL, NULL, 0, false); 42 INIT_LIST_HEAD(&cpr->blocks); 43 return cpr; 44 } 45 46 void call_path_root__free(struct call_path_root *cpr) 47 { 48 struct call_path_block *pos, *n; 49 50 list_for_each_entry_safe(pos, n, &cpr->blocks, node) { 51 list_del(&pos->node); 52 free(pos); 53 } 54 free(cpr); 55 } 56 57 static struct call_path *call_path__new(struct call_path_root *cpr, 58 struct call_path *parent, 59 struct symbol *sym, u64 ip, 60 bool in_kernel) 61 { 62 struct call_path_block *cpb; 63 struct call_path *cp; 64 size_t n; 65 66 if (cpr->next < cpr->sz) { 67 cpb = list_last_entry(&cpr->blocks, struct call_path_block, 68 node); 69 } else { 70 cpb = zalloc(sizeof(struct call_path_block)); 71 if (!cpb) 72 return NULL; 73 list_add_tail(&cpb->node, &cpr->blocks); 74 cpr->sz += CALL_PATH_BLOCK_SIZE; 75 } 76 77 n = cpr->next++ & CALL_PATH_BLOCK_MASK; 78 cp = &cpb->cp[n]; 79 80 call_path__init(cp, parent, sym, ip, in_kernel); 81 82 return cp; 83 } 84 85 struct call_path *call_path__findnew(struct call_path_root *cpr, 86 struct call_path *parent, 87 struct symbol *sym, u64 ip, u64 ks) 88 { 89 struct rb_node **p; 90 struct rb_node *node_parent = NULL; 91 struct call_path *cp; 92 bool in_kernel = ip >= ks; 93 94 if (sym) 95 ip = 0; 96 97 if (!parent) 98 return call_path__new(cpr, parent, sym, ip, in_kernel); 99 100 p = &parent->children.rb_node; 101 while (*p != NULL) { 102 node_parent = *p; 103 cp = rb_entry(node_parent, struct call_path, rb_node); 104 105 if (cp->sym == sym && cp->ip == ip) 106 return cp; 107 108 if (sym < cp->sym || (sym == cp->sym && ip < cp->ip)) 109 p = &(*p)->rb_left; 110 else 111 p = &(*p)->rb_right; 112 } 113 114 cp = call_path__new(cpr, parent, sym, ip, in_kernel); 115 if (!cp) 116 return NULL; 117 118 rb_link_node(&cp->rb_node, node_parent, p); 119 rb_insert_color(&cp->rb_node, &parent->children); 120 121 return cp; 122 } 123