1 #include "hist.h" 2 3 struct rb_root hist; 4 struct rb_root collapse_hists; 5 struct rb_root output_hists; 6 int callchain; 7 8 struct callchain_param callchain_param = { 9 .mode = CHAIN_GRAPH_REL, 10 .min_percent = 0.5 11 }; 12 13 /* 14 * histogram, sorted on item, collects counts 15 */ 16 17 struct hist_entry *__hist_entry__add(struct addr_location *al, 18 struct symbol *sym_parent, 19 u64 count, bool *hit) 20 { 21 struct rb_node **p = &hist.rb_node; 22 struct rb_node *parent = NULL; 23 struct hist_entry *he; 24 struct hist_entry entry = { 25 .thread = al->thread, 26 .map = al->map, 27 .sym = al->sym, 28 .ip = al->addr, 29 .level = al->level, 30 .count = count, 31 .parent = sym_parent, 32 }; 33 int cmp; 34 35 while (*p != NULL) { 36 parent = *p; 37 he = rb_entry(parent, struct hist_entry, rb_node); 38 39 cmp = hist_entry__cmp(&entry, he); 40 41 if (!cmp) { 42 *hit = true; 43 return he; 44 } 45 46 if (cmp < 0) 47 p = &(*p)->rb_left; 48 else 49 p = &(*p)->rb_right; 50 } 51 52 he = malloc(sizeof(*he)); 53 if (!he) 54 return NULL; 55 *he = entry; 56 rb_link_node(&he->rb_node, parent, p); 57 rb_insert_color(&he->rb_node, &hist); 58 *hit = false; 59 return he; 60 } 61 62 int64_t 63 hist_entry__cmp(struct hist_entry *left, struct hist_entry *right) 64 { 65 struct sort_entry *se; 66 int64_t cmp = 0; 67 68 list_for_each_entry(se, &hist_entry__sort_list, list) { 69 cmp = se->cmp(left, right); 70 if (cmp) 71 break; 72 } 73 74 return cmp; 75 } 76 77 int64_t 78 hist_entry__collapse(struct hist_entry *left, struct hist_entry *right) 79 { 80 struct sort_entry *se; 81 int64_t cmp = 0; 82 83 list_for_each_entry(se, &hist_entry__sort_list, list) { 84 int64_t (*f)(struct hist_entry *, struct hist_entry *); 85 86 f = se->collapse ?: se->cmp; 87 88 cmp = f(left, right); 89 if (cmp) 90 break; 91 } 92 93 return cmp; 94 } 95 96 void hist_entry__free(struct hist_entry *he) 97 { 98 free(he); 99 } 100 101 /* 102 * collapse the histogram 103 */ 104 105 void collapse__insert_entry(struct hist_entry *he) 106 { 107 struct rb_node **p = &collapse_hists.rb_node; 108 struct rb_node *parent = NULL; 109 struct hist_entry *iter; 110 int64_t cmp; 111 112 while (*p != NULL) { 113 parent = *p; 114 iter = rb_entry(parent, struct hist_entry, rb_node); 115 116 cmp = hist_entry__collapse(iter, he); 117 118 if (!cmp) { 119 iter->count += he->count; 120 hist_entry__free(he); 121 return; 122 } 123 124 if (cmp < 0) 125 p = &(*p)->rb_left; 126 else 127 p = &(*p)->rb_right; 128 } 129 130 rb_link_node(&he->rb_node, parent, p); 131 rb_insert_color(&he->rb_node, &collapse_hists); 132 } 133 134 void collapse__resort(void) 135 { 136 struct rb_node *next; 137 struct hist_entry *n; 138 139 if (!sort__need_collapse) 140 return; 141 142 next = rb_first(&hist); 143 while (next) { 144 n = rb_entry(next, struct hist_entry, rb_node); 145 next = rb_next(&n->rb_node); 146 147 rb_erase(&n->rb_node, &hist); 148 collapse__insert_entry(n); 149 } 150 } 151 152 /* 153 * reverse the map, sort on count. 154 */ 155 156 void output__insert_entry(struct hist_entry *he, u64 min_callchain_hits) 157 { 158 struct rb_node **p = &output_hists.rb_node; 159 struct rb_node *parent = NULL; 160 struct hist_entry *iter; 161 162 if (callchain) 163 callchain_param.sort(&he->sorted_chain, &he->callchain, 164 min_callchain_hits, &callchain_param); 165 166 while (*p != NULL) { 167 parent = *p; 168 iter = rb_entry(parent, struct hist_entry, rb_node); 169 170 if (he->count > iter->count) 171 p = &(*p)->rb_left; 172 else 173 p = &(*p)->rb_right; 174 } 175 176 rb_link_node(&he->rb_node, parent, p); 177 rb_insert_color(&he->rb_node, &output_hists); 178 } 179 180 void output__resort(u64 total_samples) 181 { 182 struct rb_node *next; 183 struct hist_entry *n; 184 struct rb_root *tree = &hist; 185 u64 min_callchain_hits; 186 187 min_callchain_hits = 188 total_samples * (callchain_param.min_percent / 100); 189 190 if (sort__need_collapse) 191 tree = &collapse_hists; 192 193 next = rb_first(tree); 194 195 while (next) { 196 n = rb_entry(next, struct hist_entry, rb_node); 197 next = rb_next(&n->rb_node); 198 199 rb_erase(&n->rb_node, tree); 200 output__insert_entry(n, min_callchain_hits); 201 } 202 } 203