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