1 /* Copyright (C) 2021-2023 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
68 get_status ()
69 {
70 return status;
71 }
72
73 int
74 get_depth ()
75 {
76 return depth;
77 }
78
79 int
80 getStackProp ()
81 {
82 return stack_prop;
83 }
84
85 typedef long NodeIdx;
86
87 struct Node
88 {
89 inline void
90 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 *
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
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
212 PathTree (DbeView *_dbev, int _indxtype, PathTreeType _pathTreeType)
213 {
214 construct (_dbev, _indxtype, _pathTreeType);
215 }
216
217 inline int *
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 *
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 *
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
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
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
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
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
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 *
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 */