gprofng/src/PathTree.h

   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
  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 */