include/pub_tool_xtree.h

   1
   2 /*--------------------------------------------------------------------*/
   3 /*--- An xtree, tree of stacktraces with data     pub_tool_xtree.h ---*/
   4 /*--------------------------------------------------------------------*/
   5
   6 /*
   7    This file is part of Valgrind, a dynamic binary instrumentation
   8    framework.
   9
  10    Copyright (C) 2015-2017 Philippe Waroquiers
  11
  12    This program is free software; you can redistribute it and/or
  13    modify it under the terms of the GNU General Public License as
  14    published by the Free Software Foundation; either version 2 of the
  15    License, or (at your option) any later version.
  16
  17    This program is distributed in the hope that it will be useful, but
  18    WITHOUT ANY WARRANTY; without even the implied warranty of
  19    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20    General Public License for more details.
  21
  22    You should have received a copy of the GNU General Public License
  23    along with this program; if not, see <http://www.gnu.org/licenses/>.
  24
  25    The GNU General Public License is contained in the file COPYING.
  26 */
  27
  28 #ifndef __PUB_TOOL_XTREE_H
  29 #define __PUB_TOOL_XTREE_H
  30
  31 #include "pub_tool_basics.h"
  32 #include "pub_tool_execontext.h"
  33
  34 //--------------------------------------------------------------------
  35 // PURPOSE: an XTree is conceptually a set of stacktraces organised
  36 // as a tree structure.
  37 // A stacktrace (an Addr* ips, i.e. an array of IPs : Instruction Pointers)
  38 // can be added to the tree once transformed into an execontext (ec).
  39 // Some data (typically one or more integer values) can be attached to
  40 // leafs of the tree.
  41 // Non-leaf nodes data is build by combining (typically adding together)
  42 // the data of their children nodes.
  43 // An XTree can be output in various formats.
  44 //
  45 //--------------------------------------------------------------------
  46
  47
  48 /* It's an abstract type. */
  49 typedef struct _XTree  XTree;
  50
  51 /* 3 functions types used by an xtree to manipulate the data attached to leafs
  52    of an XTree.
  53    XT_init_data_t function is used to initialise (typically to 0) the data
  54    of a new node.
  55    XT_add_data_t function is used to add 'value' to the data 'to'.
  56    XT_sub_data_t function is used to substract 'value' from the data 'from'.
  57
  58    Note that the add/sub functions can do whatever operations to
  59    combine/integrate value with/into to or from. In other words, add/sub
  60    functions are in fact equivalent to 'Reduce' functions. Add/sub is used
  61    as it is assumed that this module will be mostly used to follow
  62    resource consumption, which can be more clearly modelled with add/sub.
  63    For such resource consumption usage, typically, a call to add means that
  64    some additional resource has been allocated or consumed or ... by the
  65    given ExeContext. Similarly, a call to sub means that some resource
  66    has been released/freed/... by the given execontext.
  67
  68    Note however that there is no constraints in what add (or sub) can do. For
  69    example, the add function could maintain Min/Max values, or an histogram of
  70    values, or ... */
  71 typedef void (*XT_init_data_t) (void* value);
  72 typedef void (*XT_add_data_t) (void* to,   const void* value);
  73 typedef void (*XT_sub_data_t) (void* from, const void* value);
  74
  75 /* If not NULL, the XT_filter_IPs_t function is called when a new ec is inserted
  76    in the XTree.
  77    It indicates to the XTree to filter a range of IPs at the top and/or at
  78    the bottom of the ec Stacktrace : *top is the offset of the first IP to take
  79    into account. *n_ips_sel is the nr of IPs selected starting from *top.
  80
  81    If XT_filter_IPs_t gives *n_ips_sel equal to 0, then the inserted ec will
  82    be fully ignored when outputting the xtree:
  83      the ec value(s) will not be counted in the XTree total,
  84      the ec will not be printed/shown.
  85    Note however that the filtering only influences the output of an XTree :
  86      the ec is still inserted in the XTree, and the XT_*_data_t functions are
  87      called in any case for such filtered ec. */
  88 typedef void (*XT_filter_IPs_t) (Addr* ips, Int n_ips,
  89                                  UInt* top, UInt* n_ips_sel);
  90
  91 /* Create new XTree, using given allocation and free function.
  92    This function never returns NULL.
  93    cc is the allocation cost centre.
  94    alloc_fn must not return NULL (that is, if it returns it must have
  95    succeeded.).
  96    See respective typedef for *_fn arguments. */
  97 extern XTree* VG_(XT_create) ( Alloc_Fn_t alloc_fn,
  98                                const HChar* cc,
  99                                Free_Fn_t free_fn,
 100                                Word dataSzB,
 101                                XT_init_data_t init_data_fn,
 102                                XT_add_data_t add_data_fn,
 103                                XT_sub_data_t sub_data_fn,
 104                                XT_filter_IPs_t filter_IPs_fn);
 105
 106
 107 /* General useful filtering functions. */
 108
 109 /* Filter functions below main, unless VG_(clo_show_below_main) is True. */
 110 extern void VG_(XT_filter_maybe_below_main)
 111      (Addr* ips, Int n_ips,
 112       UInt* top, UInt* n_ips_sel);
 113 /* Same as VG_(XT_filter_maybe_below_main) but also filters one top function
 114    (typically to ignore the top level malloc/new/... fn). */
 115 extern void VG_(XT_filter_1top_and_maybe_below_main)
 116      (Addr* ips, Int n_ips,
 117       UInt* top, UInt* n_ips_sel);
 118
 119 /* Search in ips[0..n_ips-1] the first function which is main or below main
 120    and return its offset.
 121    If no main or below main is found, return n_ips-1 */
 122 extern Int VG_(XT_offset_main_or_below_main)(DiEpoch ep, Addr* ips, Int n_ips);
 123
 124
 125 /* Take a (frozen) snapshot of xt.
 126    Note that the resulting XTree is 'read-only' : calls to
 127    VG_(XT_add_to_*)/VG_(XT_sub_from_*) will assert.
 128
 129    Note: to spare memory, some data is shared between an xt and all its
 130    snapshots. This memory is released when the last XTree using this memory
 131    is deleted. */
 132 extern XTree* VG_(XT_snapshot)(XTree* xt);
 133
 134 /*  Non frozen dup currently not needed :
 135     extern XTree* VG_(XT_dup)(XTree* xt); */
 136
 137 /* Free all memory associated with an XTRee. */
 138 extern void VG_(XT_delete)(XTree* xt);
 139
 140 /* an Xecu identifies an exe context+its associated data in an XTree. */
 141 typedef UInt Xecu;
 142
 143 /* If not yet in xt, inserts the provided ec and initialises its
 144    data by calling init_data_fn.
 145    If already present (or after insertion), updates the data by calling
 146    add_data_fn. */
 147 extern Xecu VG_(XT_add_to_ec)(XTree* xt, ExeContext* ec, const void* value);
 148
 149 /* If not yet in xt, inserts the provided ec and initialises its
 150    data by calling init_data_fn.
 151    If already present (or after insertion), updates the data by calling
 152    sub_data_fn to substract value from the data associated to ec. */
 153 extern Xecu VG_(XT_sub_from_ec)(XTree* xt, ExeContext* ec, const void* value);
 154
 155 /* Same as (but more efficient than) VG_(XT_add_to_ec) and VG_(XT_sub_from_ec)
 156    for an ec already inserted in xt. */
 157 extern void VG_(XT_add_to_xecu)(XTree* xt, Xecu xecu, const void* value);
 158 extern void VG_(XT_sub_from_xecu)(XTree* xt, Xecu xecu, const void* value);
 159
 160 /* Return the nr of IPs selected for xecu. 0 means fully filtered. */
 161 extern UInt VG_(XT_n_ips_sel)(XTree* xt, Xecu xecu);
 162
 163 /* Return the ExeContext associated to the Xecu. */
 164 extern ExeContext* VG_(XT_get_ec_from_xecu) (XTree* xt, Xecu xecu);
 165
 166 /* -------------------- CALLGRIND/KCACHEGRIND OUTPUT FORMAT --------------*/
 167 /* Prints xt in outfilename in callgrind/kcachegrind format.
 168    events is a comma separated list of events, used by
 169    kcachegrind/callgrind_annotate/... to name the value various components.
 170    An event can optionally have a longer description, separated from the
 171    event name by " : ", e.g.
 172    "curB : currently allocated Bytes,curBk : Currently allocated Blocks"
 173    img_value returns an image of the value. The image must be a space
 174    separated set of integers, matching the corresponding event in events.
 175    Note that the returned pointer can be static data.
 176    img_value can return NULL if value (and its associated ExeContext) should
 177    not be printed.
 178 */
 179 extern void VG_(XT_callgrind_print)
 180      (XTree* xt,
 181       const HChar* outfilename,
 182       const HChar* events,
 183       const HChar* (*img_value) (const void* value));
 184
 185
 186 /* -------------------- MASSIF OUTPUT FORMAT --------------*/
 187 // Time is measured either in i or ms or bytes, depending on the --time-unit
 188 // option.  It's a Long because it can exceed 32-bits reasonably easily, and
 189 // because we need to allow negative values to represent unset times.
 190 typedef Long Time;
 191
 192 typedef void MsFile;
 193
 194 /* Create a new file or truncate existing file for printing xtrees in
 195    massif format. time_unit is a string describing the unit used
 196    in Massif_Header time.
 197    Produces a user error msg and returns NULL if file cannot be opened.
 198    Caller must VG_(XT_massif_close) the returned file. */
 199 extern MsFile* VG_(XT_massif_open)(const HChar* outfilename,
 200                                    const HChar* desc, // can be NULL
 201                                    const XArray* desc_args, // can be NULL
 202                                    const HChar* time_unit);
 203
 204 extern void VG_(XT_massif_close)(MsFile* fp);
 205
 206 typedef
 207    struct {
 208       int snapshot_n; // starting at 0.
 209       Time time;
 210
 211       ULong sz_B;     // sum of values, only used when printing a NULL xt.
 212       ULong extra_B;
 213       ULong stacks_B;
 214
 215       Bool detailed;
 216       Bool peak;
 217
 218       /*   top_node_desc: description for the top node.
 219            Typically for memory usage, give xt_heap_alloc_functions_desc. */
 220       const HChar* top_node_desc;
 221
 222       /* children with less than sig_threshold * total xt sz will be aggregated
 223          and printed as one single child. */
 224       double sig_threshold;
 225
 226    } Massif_Header;
 227
 228 /* Prints xt in outfilename in massif format.
 229    If a NULL xt is provided, then only the header information is used
 230    to produce the (necessarily not detailed) snapshot.
 231    report_value must return the value to be used for the report production.
 232    It will typically be the nr of bytes allocated stored with the execontext
 233    but it could be anything measured with a ULong (e.g. the nr of blocks
 234    allocated, or a number of calls, ...).
 235 */
 236 extern void VG_(XT_massif_print)
 237      (MsFile* fp,
 238       XTree* xt,
 239       const Massif_Header* header,
 240       ULong (*report_value)(const void* value));
 241
 242 #endif   // __PUB_TOOL_XTREE_H
 243
 244 /*--------------------------------------------------------------------*/
 245 /*--- end                                         pub_tool_xtree.h ---*/
 246 /*--------------------------------------------------------------------*/