1 /* Copyright (C) 2021 Free Software Foundation, Inc. 2 Contributed by Oracle. 3 4 This file is part of GNU Binutils. 5 6 This program is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 3, or (at your option) 9 any later version. 10 11 This program is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with this program; if not, write to the Free Software 18 Foundation, 51 Franklin Street - Fifth Floor, Boston, 19 MA 02110-1301, USA. */ 20 21 #ifndef _PATH_TREE_H 22 #define _PATH_TREE_H 23 24 #include <vec.h> 25 #include <Map.h> 26 27 #include "dbe_structs.h" 28 #include "Hist_data.h" 29 #include "Histable.h" 30 #include "Metric.h" 31 32 typedef enum 33 { 34 NORMAL = 0, CANCELED 35 } PtreePhaseStatus; 36 37 class PathTree 38 { 39 public: 40 41 PathTree (DbeView *_dbev, int _indxtype = -1) 42 { 43 construct (_dbev, _indxtype, PATHTREE_MAIN); 44 } 45 46 ~PathTree (); 47 48 static void make_deltas (int vtype, TValue *v1, TValue *v2); 49 static void make_ratios (int vtype, TValue *v1, TValue *v2); 50 51 typedef enum 52 { 53 COMPUTEOPT_NONE = 0, 54 COMPUTEOPT_OMP_CALLEE 55 } PtreeComputeOption; 56 57 Hist_data *compute_metrics (MetricList *, Histable::Type, 58 Hist_data::Mode, Vector<Histable*>*, 59 Histable*, Vector<Histable*>* sel_objs = NULL, 60 PtreeComputeOption flag = COMPUTEOPT_NONE); 61 // Get aggregated callstack data 62 CStack_data *get_cstack_data (MetricList *); 63 64 Vector<Histable*> *get_clr_instr (Histable *); 65 Vector<void*> *get_cle_instr (Histable *, Vector<Histable*>*&); 66 67 int get_status()68 get_status () 69 { 70 return status; 71 } 72 73 int get_depth()74 get_depth () 75 { 76 return depth; 77 } 78 79 int getStackProp()80 getStackProp () 81 { 82 return stack_prop; 83 } 84 85 typedef long NodeIdx; 86 87 struct Node 88 { 89 inline void resetNode90 reset () 91 { 92 ancestor = 0; 93 descendants = NULL; 94 instr = NULL; 95 funclist = 0; 96 } 97 98 NodeIdx ancestor; 99 Vector<NodeIdx> *descendants; 100 Histable *instr; 101 NodeIdx funclist; 102 }; 103 104 static const int CHUNKSZ = 16384; 105 106 inline Node * NODE_IDX(NodeIdx idx)107 NODE_IDX (NodeIdx idx) 108 { 109 return idx ? &chunks[idx / CHUNKSZ][idx % CHUNKSZ] : NULL; 110 } 111 112 // queue for messages (statistics for pathtree processing) 113 Emsg *fetch_stats (void); // fetch the queue of comment messages 114 void delete_stats (void); // delete the queue of stats messages 115 Emsg *fetch_warnings (void); // fetch the queue of warnings messages 116 void delete_warnings (void); // delete the queue of warnings messages 117 118 NodeIdx get_func_nodeidx(Function * func)119 get_func_nodeidx (Function * func) 120 { 121 return fn_map == NULL ? (NodeIdx) 0 : fn_map->get (func); 122 } 123 124 void print (FILE *); 125 void dumpNodes (FILE *, Histable *); 126 127 // flame charts functions - get values from ftree_internal 128 int get_ftree_depth (); // Depth of tree 129 Vector<void*>* get_ftree_level (BaseMetric *bm, int dpth); 130 Vector<void*>* get_ftree_node_children (BaseMetric *bm, NodeIdx node_idx); 131 Vector<Function*>* get_ftree_funcs (); 132 Vector<Function*>* get_funcs (); // Unique functions in tree 133 134 private: 135 136 enum 137 { 138 MAX_DESC_HTABLE_SZ = 65535 139 }; 140 141 typedef struct hash_node 142 { 143 NodeIdx nd; 144 struct hash_node *next; 145 } hash_node_t; 146 147 int desc_htable_size; 148 int desc_htable_nelem; 149 hash_node_t **descHT; 150 151 struct Slot 152 { 153 int id; 154 ValueTag vtype; 155 union 156 { 157 int **mvals; 158 int64_t **mvals64; 159 }; 160 }; 161 162 typedef enum 163 { 164 PATHTREE_MAIN = 0, 165 PATHTREE_INTERNAL_OMP, 166 PATHTREE_INTERNAL_FUNCTREE 167 } PathTreeType; 168 169 DbeView *dbev; 170 int indxtype; 171 int stack_prop; 172 Expression *indx_expr; 173 Histable *total_obj; 174 Map<Function*, NodeIdx> *fn_map; 175 Map<uint64_t, NodeIdx> *pathMap; 176 Map<uint64_t, uint64_t> *hideMap; 177 int status; 178 NodeIdx root_idx; 179 Node *root; 180 int depth; 181 long nodes; 182 long dnodes; 183 long nchunks; 184 Node **chunks; 185 int nslots; 186 Slot *slots; 187 int phaseIdx; 188 int nexps; 189 Emsgqueue *statsq; 190 Emsgqueue *warningq; 191 Hist_data *hist_data; 192 int percent; 193 int ndone; 194 Histable **obj_list; 195 Node **node_list; 196 int *xlate; 197 bool cancel_ok; 198 PathTreeType pathTreeType; 199 PathTree *ptree_internal; 200 PathTree *ftree_internal; // function-based pathtree 201 bool ftree_needs_update; 202 Vector<Vector<NodeIdx>*> *depth_map; // for each depth level, list of nodes 203 204 void init (); 205 void fini (); 206 PtreePhaseStatus reset (); 207 PtreePhaseStatus add_experiment (int); 208 PtreePhaseStatus process_packets (Experiment*, DataView*, int); 209 DataView *get_filtered_events (int exp_index, int data_type); 210 void construct (DbeView *_dbev, int _indxtype, PathTreeType _pathTreeType); 211 PathTree(DbeView * _dbev,int _indxtype,PathTreeType _pathTreeType)212 PathTree (DbeView *_dbev, int _indxtype, PathTreeType _pathTreeType) 213 { 214 construct (_dbev, _indxtype, _pathTreeType); 215 } 216 217 inline int * allocate_chunk(int ** p,NodeIdx idx)218 allocate_chunk (int **p, NodeIdx idx) 219 { 220 int *res = new int[CHUNKSZ]; 221 for (int i = 0; i < CHUNKSZ; i++) 222 res[i] = 0; 223 p[idx] = res; 224 return res; 225 }; 226 227 inline int64_t * allocate_chunk(int64_t ** p,NodeIdx idx)228 allocate_chunk (int64_t **p, NodeIdx idx) 229 { 230 int64_t *res = new int64_t[CHUNKSZ]; 231 for (int i = 0; i < CHUNKSZ; i++) 232 res[i] = 0; 233 p[idx] = res; 234 return res; 235 }; 236 237 inline Node * allocate_chunk(Node ** p,NodeIdx idx)238 allocate_chunk (Node **p, NodeIdx idx) 239 { 240 Node *res = new Node[CHUNKSZ]; 241 for (int i = 0; i < CHUNKSZ; i++) 242 res[i].reset (); 243 p[idx] = res; 244 return res; 245 }; 246 247 inline bool IS_MVAL_ZERO(Slot & slot,NodeIdx idx)248 IS_MVAL_ZERO (Slot& slot, NodeIdx idx) 249 { 250 if (slot.vtype == VT_LLONG || slot.vtype == VT_ULLONG) 251 { 252 int64_t *tmp = slot.mvals64[idx / CHUNKSZ]; 253 return tmp ? tmp[idx % CHUNKSZ] == 0 : true; 254 } 255 else 256 { 257 int *tmp = slot.mvals[idx / CHUNKSZ]; 258 return tmp ? tmp[idx % CHUNKSZ] == 0 : true; 259 } 260 } 261 262 inline void ASN_METRIC_VAL(TValue & v,Slot & slot,NodeIdx idx)263 ASN_METRIC_VAL (TValue& v, Slot& slot, NodeIdx idx) 264 { 265 if (slot.vtype == VT_LLONG) 266 { 267 int64_t *tmp = slot.mvals64[idx / CHUNKSZ]; 268 if (tmp) 269 v.ll = tmp[idx % CHUNKSZ]; 270 } 271 else if (slot.vtype == VT_ULLONG) 272 { 273 uint64_t *tmp = (uint64_t *) slot.mvals64[idx / CHUNKSZ]; 274 if (tmp) 275 v.ull = tmp[idx % CHUNKSZ]; 276 } 277 else 278 { 279 int *tmp = slot.mvals[idx / CHUNKSZ]; 280 if (tmp) 281 v.i = tmp[idx % CHUNKSZ]; 282 } 283 } 284 285 inline void ADD_METRIC_VAL(TValue & v,Slot & slot,NodeIdx idx)286 ADD_METRIC_VAL (TValue& v, Slot& slot, NodeIdx idx) 287 { 288 if (slot.vtype == VT_LLONG) 289 { 290 int64_t *tmp = slot.mvals64[idx / CHUNKSZ]; 291 if (tmp) 292 v.ll += tmp[idx % CHUNKSZ]; 293 } 294 else if (slot.vtype == VT_ULLONG) 295 { 296 uint64_t *tmp = (uint64_t *) slot.mvals64[idx / CHUNKSZ]; 297 if (tmp) 298 v.ull += tmp[idx % CHUNKSZ]; 299 } 300 else 301 { 302 int *tmp = slot.mvals[idx / CHUNKSZ]; 303 if (tmp) v.i += tmp[idx % CHUNKSZ]; 304 } 305 } 306 307 inline void SUB_METRIC_VAL(TValue & v,Slot & slot,NodeIdx idx)308 SUB_METRIC_VAL (TValue& v, Slot& slot, NodeIdx idx) 309 { 310 if (slot.vtype == VT_LLONG) 311 { 312 int64_t *tmp = slot.mvals64[idx / CHUNKSZ]; 313 if (tmp) 314 v.ll -= tmp[idx % CHUNKSZ]; 315 } 316 else if (slot.vtype == VT_ULLONG) 317 { 318 uint64_t *tmp = (uint64_t *) slot.mvals64[idx / CHUNKSZ]; 319 if (tmp) 320 v.ull -= tmp[idx % CHUNKSZ]; 321 } 322 else 323 { 324 int *tmp = slot.mvals[idx / CHUNKSZ]; 325 if (tmp) 326 v.i -= tmp[idx % CHUNKSZ]; 327 } 328 } 329 330 inline void INCREMENT_METRIC(Slot * slot,NodeIdx idx,int64_t val)331 INCREMENT_METRIC (Slot *slot, NodeIdx idx, int64_t val) 332 { 333 if (slot->vtype == VT_LLONG) 334 { 335 int64_t *tmp = slot->mvals64[idx / CHUNKSZ]; 336 if (tmp == NULL) 337 tmp = allocate_chunk (slot->mvals64, idx / CHUNKSZ); 338 tmp[idx % CHUNKSZ] += val; 339 } 340 else if (slot->vtype == VT_ULLONG) 341 { 342 uint64_t *tmp = (uint64_t *) slot->mvals64[idx / CHUNKSZ]; 343 if (tmp == NULL) 344 tmp = (uint64_t *) allocate_chunk (slot->mvals64, idx / CHUNKSZ); 345 tmp[idx % CHUNKSZ] += val; 346 } 347 else 348 { 349 int *tmp = slot->mvals[idx / CHUNKSZ]; 350 if (tmp == NULL) 351 tmp = allocate_chunk (slot->mvals, idx / CHUNKSZ); 352 tmp[idx % CHUNKSZ] += (int) val; 353 } 354 } 355 356 inline Slot * SLOT_IDX(int idx)357 SLOT_IDX (int idx) 358 { 359 if (idx < 0 || idx >= nslots) 360 return NULL; 361 return &slots[idx]; 362 } 363 364 int allocate_slot (int id, ValueTag vtype); 365 void allocate_slots (Slot *slots, int nslots); 366 int find_slot (int); 367 NodeIdx new_Node (NodeIdx, Histable*, bool); 368 NodeIdx find_path (Experiment*, DataView*, long); 369 NodeIdx find_desc_node (NodeIdx, Histable*, bool); 370 NodeIdx find_in_desc_htable (NodeIdx, Histable*, bool); 371 Histable *get_hist_obj (Node *, Histable* = NULL); 372 Histable *get_hist_func_obj (Node *); 373 Histable *get_compare_obj (Histable *obj); 374 void get_metrics (NodeIdx, int); 375 void get_metrics (Vector<Function*> *, Histable *); 376 void get_clr_metrics (Vector<Histable*>*, NodeIdx, int, int); 377 void get_clr_metrics (Vector<Histable*>*); 378 void get_cle_metrics (Vector<Histable*>*, NodeIdx, int, int, int); 379 void get_cle_metrics (Vector<Histable*>*, NodeIdx, int); 380 void get_cle_metrics (Vector<Histable*>*); 381 void get_self_metrics (Vector<Histable*>*, NodeIdx, bool, int); 382 void get_self_metrics (Vector<Histable*>*); 383 void get_self_metrics (Histable *, Vector<Function*> *funclist, 384 Vector<Histable*>* sel_objs = NULL); 385 void get_cstack_list (CStack_data *, NodeIdx, int); 386 387 // Generate PathTree based on Functions instead of Instructions // Used for flame chart 388 void ftree_reset (); 389 void ftree_build (PathTree *mstr); 390 void ftree_build (PathTree *mstr, NodeIdx mstr_node_idx, NodeIdx local_node_idx); 391 void depth_map_build (); 392 void depth_map_build (NodeIdx node_idx, int depth); 393 Vector<void*>* get_level (BaseMetric *bm, int dpth); 394 Vector<void*>* get_nodes (BaseMetric *bm, Vector<NodeIdx> *node_idxs); 395 Vector<void*>* get_node_children (BaseMetric *bm, NodeIdx node_idx); 396 bool ftree_debug_match_hist_data (Hist_data *data, Hist_data *data_tmp); 397 void ftree_dump (); 398 399 // Debugging functions 400 void print (FILE *, PathTree::Node*, int); 401 void printn (FILE *); 402 int dbg_nodes (PathTree::Node*); 403 }; 404 405 #endif /* _PATH_TREE_H */ 406