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