
/*--------------------------------------------------------------------*/
/*--- An xtree, tree of stacktraces with data            m_xtree.c ---*/
/*--------------------------------------------------------------------*/

/*
   This file is part of Valgrind, a dynamic binary instrumentation
   framework.

   Copyright (C) 2016-2017 Philippe Waroquiers

   This code generalises the XTree idea that was implemented in
   the massif tool in Valgrind versions <= 3.12, which is
      Copyright (C) 2005-2017 Nicholas Nethercote
       njn@valgrind.org

   The XTree implementation in this file is however implemented completely
   differently. Some code has been re-used for the production of the
   massif file header (e.g. FP_cmd function).

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307, USA.

   The GNU General Public License is contained in the file COPYING.
*/

#include "pub_core_basics.h"
#include "pub_core_debuglog.h"
#include "pub_core_clientstate.h"
#include "pub_core_stacktrace.h"
#include "pub_core_execontext.h"
#include "pub_core_libcbase.h"
#include "pub_core_libcassert.h"
#include "pub_core_libcfile.h"
#include "pub_core_libcprint.h"
#include "pub_core_libcproc.h"
#include "pub_core_hashtable.h"
#include "pub_core_mallocfree.h"
#include "pub_core_options.h"
#include "pub_core_debuginfo.h"
#include "pub_core_deduppoolalloc.h"
#include "pub_core_xtree.h"    /* self */

#define DMSG(level, ...) (level <= VG_(debugLog_getLevel)() ?         \
                          VG_(dmsg)(__VA_ARGS__)                      \
                          : 0)

/* Defines the relevant part of an ec. This is shared between an xt
   and its snapshots (see XT_shared XArray of xec). */
typedef
   struct _xec {
     ExeContext* ec;
     UShort top;        // The first ips of ec to take into account.
     UShort n_ips_sel;  // The nr of ips from top to take into account.
   }
   xec;

/* XT_shared maintains the information shared between an XT and all
   its snapshots. */
typedef
   struct _XT_shared {
      UWord nrRef; /* nr of XTrees referencing this shared memory. */

      Alloc_Fn_t alloc_fn;                /* alloc fn (nofail) */
      const HChar* cc;                    /* cost centre for alloc */
      Free_Fn_t free_fn;                  /* free fn */

      /* The data associated to each ec is stored in 2 arrays:
           an xec array, shared between an xt and all its snapshots.
           a  data array, private to each XTree.
         For an ec with an ECU ecu, d4ecu2xecu[ecu/4] gives the offset in
         xec and data arrays where the ec information is located (this
         indirection is used to avoid huge xec and data arrays, in
         case an XTree contains data only for a small number of ec.
         The offset in the xec and data array is used as xtree ec unique
         id i.e. an xecu. */

      UInt  d4ecu2xecu_sz; /* size of d4ecu2xecu (in nr of elements). */
      UInt* d4ecu2xecu;

      /* ec information common to an xt and its snapshots. */
      XArray* xec; /* XArray of xec, indexed by xecu (== d4ecu2xecu[ecu/4]). */
   
      /* XArray of xecu, sorted by StackTrace ips[top..top+n_ips_sel-1].
         See ips_order_cmp. */
      XArray* ips_order_xecu;
   } XT_shared;

/* NO_OFFSET indicates in d4ecu2xecu  there is no data (yet) for this ec
   (with the index ecu/4). */
#define NO_OFFSET 0xffffffff

static XT_shared* new_XT_shared (Alloc_Fn_t alloc_fn,
                                 const  HChar* cc,
                                 void   (*free_fn)(void*))
{
   XT_shared* shared;

   vg_assert(alloc_fn);
   vg_assert(cc);
   vg_assert(free_fn);
   shared = alloc_fn(cc, sizeof(*shared));
   shared->nrRef = 0;
   shared->alloc_fn = alloc_fn;
   shared->cc = cc;
   shared->free_fn = free_fn;

   shared->d4ecu2xecu_sz = 0;
   shared->d4ecu2xecu = NULL;
   shared->xec = VG_(newXA)(alloc_fn, cc, free_fn, sizeof(xec));
   shared->ips_order_xecu = NULL; // Allocated when needed.

   return shared;
}

static void delete_XT_shared (XT_shared* shared)
{
   vg_assert(shared->nrRef == 0);
   shared->free_fn(shared->d4ecu2xecu);
   VG_(deleteXA)(shared->xec);
   if (shared->ips_order_xecu != NULL)
      VG_(deleteXA)(shared->ips_order_xecu);
   shared->free_fn(shared);
}

/* Compare 2 entries in ips_order_xecu by StackTrace elements.
   In case stack traces are of different length, an 'absent' ips is
   considered smaller than any other address. */
static XArray* xec_data_for_sort; // Needed to translate an xecu into an xec
static Int ips_order_cmp(const void* vleft, const void* vright)
{
   const Xecu left_xecu  = *(const Xecu*)vleft;
   const Xecu right_xecu = *(const Xecu*)vright;
   const xec* left  = VG_(indexXA)(xec_data_for_sort, left_xecu);
   const xec* right = VG_(indexXA)(xec_data_for_sort, right_xecu);
   const StackTrace left_ips  = VG_(get_ExeContext_StackTrace)(left->ec)
      + left->top;
   const StackTrace right_ips = VG_(get_ExeContext_StackTrace)(right->ec)
      + right->top;
   UInt i;

   const UInt c_n_ips_sel = left->n_ips_sel < right->n_ips_sel 
      ? left->n_ips_sel : right->n_ips_sel;

   // First see if we have a difference on the common nr of ips selected
   for (i = 0; i < c_n_ips_sel; i++) {
      if (left_ips[i] == right_ips[i]) continue;
      if (left_ips[i] < right_ips[i]) return -1;
      return  1;
   }
   // Common part is equal => compare lengths.
   if (left->n_ips_sel < right->n_ips_sel) return -1;
   if (left->n_ips_sel > right->n_ips_sel) return  1;
   return 0;
}

// If needed, build or refresh shared->ips_order_xecu
static void ensure_ips_order_xecu_valid(XT_shared* shared)
{
   UInt i;
   UInt n_xecu;

   if (shared->ips_order_xecu == NULL) {
      shared->ips_order_xecu = VG_(newXA)(shared->alloc_fn, shared->cc, 
                                          shared->free_fn, sizeof(Xecu));
      VG_(hintSizeXA)(shared->ips_order_xecu, VG_(sizeXA)(shared->xec));
      VG_(setCmpFnXA)(shared->ips_order_xecu, ips_order_cmp);
   }

   if (VG_(sizeXA)(shared->xec) == VG_(sizeXA)(shared->ips_order_xecu))
      return;

   n_xecu = VG_(sizeXA)(shared->xec);
   for (i = VG_(sizeXA)(shared->ips_order_xecu); i < n_xecu; i++)
      VG_(addToXA)(shared->ips_order_xecu, &i);
 
   xec_data_for_sort = shared->xec;
   VG_(sortXA)(shared->ips_order_xecu);
}

static void addRef_XT_shared (XT_shared* shared)
{
   shared->nrRef++;
}

static UWord release_XT_shared(XT_shared* shared)
{
   UWord nrRef;

   vg_assert(shared->nrRef > 0);
   nrRef = --shared->nrRef;
   if (nrRef == 0)
      delete_XT_shared(shared);
   return nrRef;
}

   
struct _XTree {
   Alloc_Fn_t alloc_fn;                /* alloc fn (nofail) */
   const HChar* cc;                    /* cost centre for alloc */
   Free_Fn_t free_fn;                  /* free fn */
   Word  dataSzB;   /* data size in bytes */
   XT_init_data_t init_data_fn;
   XT_add_data_t add_data_fn;
   XT_sub_data_t sub_data_fn;
   XT_filter_IPs_t filter_IPs_fn;

   XT_shared* shared;

   HChar* tmp_data; /* temporary buffer, to insert new elements. */
   XArray* data; /* of elements of size dataSzB */
};


XTree* VG_(XT_create) ( Alloc_Fn_t alloc_fn,
                        const HChar* cc,
                        Free_Fn_t free_fn,
                        Word dataSzB,
                        XT_init_data_t init_data_fn,
                        XT_add_data_t add_data_fn,
                        XT_sub_data_t sub_data_fn,
                        XT_filter_IPs_t filter_IPs_fn)
{
   XTree* xt;

   /* check user-supplied info .. */
   vg_assert(alloc_fn);
   vg_assert(free_fn);
   vg_assert(dataSzB >= 0);
   vg_assert(init_data_fn);
   vg_assert(add_data_fn);
   vg_assert(sub_data_fn);

   xt = alloc_fn(cc, sizeof(struct _XTree) );
   xt->alloc_fn  = alloc_fn;
   xt->cc        = cc;
   xt->free_fn   = free_fn;
   xt->dataSzB   = dataSzB;
   xt->init_data_fn = init_data_fn;
   xt->add_data_fn = add_data_fn;
   xt->sub_data_fn = sub_data_fn;
   xt->filter_IPs_fn = filter_IPs_fn;

   xt->shared = new_XT_shared(alloc_fn, cc, free_fn);
   addRef_XT_shared(xt->shared);
   xt->tmp_data = alloc_fn(cc, xt->dataSzB);
   xt->data =  VG_(newXA)(alloc_fn, cc, free_fn, dataSzB);

   return xt;
}

XTree* VG_(XT_snapshot)(XTree* xt)
{
   XTree* nxt;

   vg_assert(xt);

   nxt = xt->alloc_fn(xt->cc, sizeof(struct _XTree) );

   *nxt = *xt;
   addRef_XT_shared(nxt->shared);
   nxt->tmp_data = nxt->alloc_fn(nxt->cc, nxt->dataSzB);
   nxt->data = VG_(cloneXA)(nxt->cc, xt->data);

   return nxt;
}

void VG_(XT_delete) ( XTree* xt )
{
   vg_assert(xt);

   release_XT_shared(xt->shared);
   xt->free_fn(xt->tmp_data);
   VG_(deleteXA)(xt->data);
   xt->free_fn(xt);
}

static Xecu find_or_insert (XTree* xt, ExeContext* ec)
{

   const UInt d4ecu = VG_(get_ECU_from_ExeContext)(ec) / 4;
   XT_shared* shared = xt->shared;

   /* First grow the d4ecu2xecu array if needed. */
   if (d4ecu >= shared->d4ecu2xecu_sz) {
      UInt old_sz = shared->d4ecu2xecu_sz;
      UInt new_sz = (3 * d4ecu) / 2;

      if (new_sz < 1000)
         new_sz = 1000;
      shared->d4ecu2xecu = VG_(realloc)(xt->cc, shared->d4ecu2xecu,
                                        new_sz * sizeof(UInt));
      shared->d4ecu2xecu_sz = new_sz;
      for (UInt i = old_sz; i < new_sz; i++)
         shared->d4ecu2xecu[i] = NO_OFFSET;
   }

   if (shared->d4ecu2xecu[d4ecu] == NO_OFFSET) {
      xec xe;
     
      xe.ec = ec;
      if (xt->filter_IPs_fn == NULL) {
         xe.top = 0;
         xe.n_ips_sel = (UShort)VG_(get_ExeContext_n_ips)(xe.ec);
      } else {
         UInt top;
         UInt n_ips_sel = VG_(get_ExeContext_n_ips)(xe.ec);
         xt->filter_IPs_fn(VG_(get_ExeContext_StackTrace)(xe.ec), n_ips_sel,
                           &top, &n_ips_sel);
         xe.top = (UShort)top;
         xe.n_ips_sel = (UShort)n_ips_sel;
      }
      xt->init_data_fn(xt->tmp_data);
      VG_(addToXA)(shared->xec, &xe);
      shared->d4ecu2xecu[d4ecu] = (UInt)VG_(addToXA)(xt->data, xt->tmp_data);
   } 

   return shared->d4ecu2xecu[d4ecu];
}

Xecu VG_(XT_add_to_ec) (XTree* xt, ExeContext* ec, const void* value)
{
   Xecu xecu = find_or_insert(xt, ec);
   void* data = VG_(indexXA)(xt->data, xecu);

   xt->add_data_fn(data, value);
   return xecu;
}

Xecu VG_(XT_sub_from_ec) (XTree* xt, ExeContext* ec, const void* value)
{
   Xecu xecu = find_or_insert(xt, ec);
   void* data = VG_(indexXA)(xt->data, xecu);

   xt->sub_data_fn(data, value);
   return xecu;
}

void VG_(XT_add_to_xecu) (XTree* xt, Xecu xecu, const void* value)
{
   void* data = VG_(indexXA)(xt->data, xecu);
   xt->add_data_fn(data, value);
}

void VG_(XT_sub_from_xecu) (XTree* xt, Xecu xecu, const void* value)
{
   void* data = VG_(indexXA)(xt->data, xecu);
   xt->sub_data_fn(data, value);
}

UInt VG_(XT_n_ips_sel) (XTree* xt, Xecu xecu)
{
   xec* xe = (xec*)VG_(indexXA)(xt->shared->xec, xecu);
   return (UInt)xe->n_ips_sel;
}

ExeContext* VG_(XT_get_ec_from_xecu) (XTree* xt, Xecu xecu)
{
   xec* xe = (xec*)VG_(indexXA)(xt->shared->xec, xecu);
   return xe->ec;
}

static VgFile* xt_open (const HChar* outfilename)
{
   VgFile* fp;

   fp = VG_(fopen)(outfilename, VKI_O_CREAT|VKI_O_WRONLY|VKI_O_TRUNC,
                   VKI_S_IRUSR|VKI_S_IWUSR);
   if (fp == NULL) {
      VG_(message)(Vg_UserMsg,
                   "Error: can not open xtree output file `%s'\n",
                   outfilename);
   }
   return fp;
}

#define FP(format, args...) ({ VG_(fprintf)(fp, format, ##args); })

// Print "cmd:" line.
static void FP_cmd(VgFile* fp)
{
   UInt i;

   FP("cmd: ");
   FP("%s", VG_(args_the_exename));
   for (i = 0; i < VG_(sizeXA)(VG_(args_for_client)); i++) {
      HChar* arg = * (HChar**) VG_(indexXA)(VG_(args_for_client), i);
      FP(" %s", arg);
   }
   FP("\n");
}

/* ----------- Callgrind output ------------------------------------------- */

/* Output a callgrind format element in compressed format:
     "name=(pos)" or "name=(pos) value" (if value_new)
   or not compressed format: "name=value"
   VG_(clo_xtree_compress_strings) indicates if the compressed format is used.
   name is the format element (e.g. fl, fn, cfi, cfn, ...).
   pos is the value dictionary position, used for compressed format.
   value_new is True if this is the first usage of value. */
static void FP_pos_str(VgFile* fp, const HChar* name, UInt pos,
                       const HChar* value, Bool value_new)
{
   if (!VG_(clo_xtree_compress_strings))
      FP("%s=%s\n", name, value);
   else if (value_new)
      FP("%s=(%d) %s\n", name, pos, value);
   else
      FP("%s=(%d)\n", name, pos);
}

void VG_(XT_callgrind_print)
     (XTree* xt,
      const HChar* outfilename,
      const HChar* events,
      const HChar* (*img_value)(const void* value))
{
   UInt n_xecu;
   XT_shared* shared = xt->shared;
   VgFile* fp = xt_open(outfilename);
   DedupPoolAlloc* fnname_ddpa;
   DedupPoolAlloc* filename_ddpa;
   HChar* filename_buf = NULL;
   UInt filename_buf_size = 0;
   const HChar* filename_dir;
   const HChar* filename_name;

   if (fp == NULL)
      return;

   fnname_ddpa = VG_(newDedupPA)(16000, 1, xt->alloc_fn,
                                 "XT_callgrind_print.fn", xt->free_fn);
   filename_ddpa = VG_(newDedupPA)(16000, 1, xt->alloc_fn,
                                   "XT_callgrind_print.fl", xt->free_fn);

   FP("# callgrind format\n");
   FP("version: 1\n");
   FP("creator: xtree-1\n");
   FP("pid: %d\n", VG_(getpid)());
   FP_cmd(fp);

   /* Currently, we only need/support line positions. */
   FP("\npositions:%s\n", " line");

   /* Produce one "event:" line for each event, and the "events:" line. */
   {
      HChar strtok_events[VG_(strlen)(events)+1];
      HChar* e;
      HChar* ssaveptr;
      HChar* p;

      VG_(strcpy)(strtok_events, events);
      for (e = VG_(strtok_r)(strtok_events, ",", &ssaveptr); 
           e != NULL; 
           e = VG_(strtok_r)(NULL, ",", &ssaveptr))
         FP("event: %s\n", e);
      FP("events:");
      VG_(strcpy)(strtok_events, events);
      for (e = VG_(strtok_r)(strtok_events, ",", &ssaveptr); 
           e != NULL; 
           e = VG_(strtok_r)(NULL, ",", &ssaveptr)) {
         p = e;
         while (*p) {
            if (*p == ':')
               *p = 0;
            p++;
         }
         FP(" %s", e);
      }
      FP("\n");
   }
   xt->init_data_fn(xt->tmp_data); // to compute totals

   n_xecu = VG_(sizeXA)(xt->data);
   vg_assert (n_xecu <= VG_(sizeXA)(shared->xec));
   for (Xecu xecu = 0; xecu < n_xecu; xecu++) {
      xec* xe = (xec*)VG_(indexXA)(shared->xec, xecu);
      if (xe->n_ips_sel == 0)
         continue;

      const HChar* img = img_value(VG_(indexXA)(xt->data, xecu));
     
      // CALLED_FLF gets the Dir+Filename/Line number/Function name for ips[n]
      // in the variables called_filename/called_linenum/called_fnname.
      // The booleans called_filename_new/called_fnname_new are set to True
      // the first time the called_filename/called_fnname are encountered.
      // The called_filename_nr/called_fnname_nr are numbers identifying
      // the strings  called_filename/called_fnname.
#define CALLED_FLF(n)                                                   \
      if ((n) < 0                                                       \
          || !VG_(get_filename_linenum)(ips[(n)],                       \
                                        &filename_name,                 \
                                        &filename_dir,                  \
                                        &called_linenum)) {             \
         filename_name = "UnknownFile???";                              \
         called_linenum = 0;                                            \
      }                                                                 \
      if ((n) < 0                                                       \
          || !VG_(get_fnname)(ips[(n)], &called_fnname)) {              \
         called_fnname = "UnknownFn???";                                \
      }                                                                 \
      {                                                                 \
         UInt needed_size = VG_(strlen)(filename_dir) + 1               \
            + VG_(strlen)(filename_name) + 1;                           \
         if (filename_buf_size < needed_size) {                         \
            filename_buf_size = needed_size;                            \
            filename_buf = VG_(realloc)(xt->cc, filename_buf,           \
                                        filename_buf_size);             \
         }                                                              \
      }                                                                 \
      VG_(strcpy)(filename_buf, filename_dir);                          \
      if (filename_buf[0] != '\0') {                                    \
         VG_(strcat)(filename_buf, "/");                                \
      }                                                                 \
      VG_(strcat)(filename_buf, filename_name);                         \
      called_filename_nr = VG_(allocStrDedupPA)(filename_ddpa,          \
                                                filename_buf,           \
                                                &called_filename_new);  \
      called_filename = filename_buf;                                   \
      called_fnname_nr = VG_(allocStrDedupPA)(fnname_ddpa,              \
                                              called_fnname,            \
                                              &called_fnname_new);

      /* Instead of unknown fnname ???, CALLED_FLF could use instead:
         VG_(sprintf)(unknown_fn, "%p", (void*)ips[(n)]);
         but that creates a lot of (useless) nodes at least for
         valgrind self-hosting. */
      
      if (img) {
         const HChar* called_filename;
         UInt called_filename_nr;
         Bool called_filename_new; // True the first time we see this filename.
         const HChar* called_fnname;
         UInt called_fnname_nr;
         Bool called_fnname_new; // True the first time we see this fnname.
         UInt called_linenum;
         UInt prev_linenum;

         const Addr* ips = VG_(get_ExeContext_StackTrace)(xe->ec) + xe->top;
         Int ips_idx = xe->n_ips_sel - 1;

         if (0) {
            VG_(printf)("entry img %s\n", img);
            VG_(pp_ExeContext)(xe->ec);
            VG_(printf)("\n");
         }
         xt->add_data_fn(xt->tmp_data, VG_(indexXA)(xt->data, xecu));
         CALLED_FLF(ips_idx);
         for (;
              ips_idx >= 0;
              ips_idx--) {
            FP_pos_str(fp, "fl", called_filename_nr,
                       called_filename, called_filename_new);
            FP_pos_str(fp, "fn", called_fnname_nr,
                       called_fnname, called_fnname_new);
            if (ips_idx == 0)
               FP("%d %s\n", called_linenum, img);
            else
               FP("%d\n", called_linenum); //no self cost.
            prev_linenum = called_linenum;
            if (ips_idx >= 1) {
               CALLED_FLF(ips_idx-1);
               FP_pos_str(fp, "cfi", called_filename_nr,
                          called_filename, called_filename_new);
               FP_pos_str(fp, "cfn", called_fnname_nr,
                          called_fnname, called_fnname_new);
               called_filename_new = False;
               called_fnname_new = False;
               /* Giving a call count of 0 allows kcachegrind to hide the calls
                  column. A call count of 1 means kcachegrind would show in the
                  calls column the nr of stacktrace containing this arc, which
                  is very confusing. So, the less bad is to give a 0 call
                  count. */
               FP("calls=0 %d\n", called_linenum);
               FP("%d %s\n", prev_linenum, img);
            }
         }
         FP("\n");
      }
   }
   /* callgrind format is not really fully supporting (yet?) execution trees:
      in an execution tree, self and inclusive costs are identical, and
      cannot be added together.
      If no totals: line is given, callgrind_annotate calculates the addition
      of all costs, and so gives a wrong totals.
      Giving a totals: line solves this, but the user must give the option
      --inclusive=yes (kind of hack) to have all the functions given
      in the output file. */
   FP("totals: %s\n", img_value(xt->tmp_data));
   VG_(fclose)(fp);
   VG_(deleteDedupPA)(fnname_ddpa);
   VG_(deleteDedupPA)(filename_ddpa);
   VG_(free)(filename_buf);
}


/* ----------- Massif output ---------------------------------------------- */

/* For Massif output, some functions from the execontext are not output, a.o.
   the allocation functions at the top of the stack and the functions below
   main. So, the StackTrace of the execontexts in the xtree must be filtered.
   Ms_Ec defines the subset of the stacktrace relevant for the report. */
typedef
   struct {
      StackTrace ips; // ips and n_ips provides the subset of the xtree ec
      UInt n_ips;     // to use for a massif report.

      SizeT report_value; // The value to report for this stack trace.
   } Ms_Ec;

/* Ms_Group defines (at a certain depth) a group of ec context that
   have the same IPs at the given depth, and have the same 'parent'.
   total is the sum of the values of all group elements.
   A Ms_Group can also represent a set of ec contexts that do not
   have the same IP, but that have each a total which is below the
   significant size. Such a group has a NULL ms_ec, a zero group_io.
   n_ec is the nr of insignificant ec that have been collected inside this
   insignificant group, and total is the sum of all non significant ec
   at the given depth. */
typedef
   struct {
      Ms_Ec* ms_ec; // The group consists in ms_ec[0 .. n_ec-1]
      Addr group_ip;
      UInt n_ec;
      SizeT total;
   } Ms_Group;

/* Compare 2 groups by total, to have bigger total first. */
static Int ms_group_revcmp_total(const void* vleft, const void* vright)
{
   const Ms_Group* left = (const Ms_Group*)vleft;
   const Ms_Group* right = (const Ms_Group*)vright;

   // First reverse compare total
   if (left->total > right->total) return -1;
   if (left->total < right->total) return  1;

   /* Equal size => compare IPs.
      This (somewhat?) helps to have deterministic test results.
      If this would change between platforms, then we should compare
      function names/filename/linenr */
   if (left->group_ip < right->group_ip) return -1;
   if (left->group_ip > right->group_ip) return  1;
   return 0;
}

/* Scan the addresses in ms_ec at the given depth.
   On return, 
      *groups points to an array of Ms_Group sorted by total.
      *n_groups is the nr of groups
   The caller is responsible to free the allocated group array. */
static void ms_make_groups (UInt depth, Ms_Ec* ms_ec, UInt n_ec, SizeT sig_sz,
                            UInt* n_groups, Ms_Group** groups)
{
   UInt i, g;
   Addr cur_group_ip = 0;

   *n_groups = 0;

   /* Handle special case somewhat more efficiently */
   if (n_ec == 0) {
      *groups = NULL;
      return;
   }

   /* Compute how many groups we have. */
   for (i = 0; i < n_ec; i++) {
      if (ms_ec[i].n_ips > depth
          && (*n_groups == 0 || cur_group_ip != ms_ec[i].ips[depth])) {
         (*n_groups)++;
         cur_group_ip = ms_ec[i].ips[depth];
      }
   }

   /* make the group array. */
   *groups = VG_(malloc)("ms_make_groups", *n_groups * sizeof(Ms_Group));
   i = 0;
   for (g = 0; g < *n_groups; g++) {
      while (ms_ec[i].n_ips <= depth)
         i++;
      cur_group_ip = ms_ec[i].ips[depth];
      (*groups)[g].group_ip = cur_group_ip;
      (*groups)[g].ms_ec = &ms_ec[i];
      (*groups)[g].n_ec = 1;
      (*groups)[g].total = ms_ec[i].report_value;
      i++;
      while (i < n_ec 
             && ms_ec[i].n_ips > depth
             && cur_group_ip == ms_ec[i].ips[depth]) {
         (*groups)[g].total += ms_ec[i].report_value;
         i++;
         (*groups)[g].n_ec++;
      }
   }

   /* Search for insignificant groups, collect them all together
      in the first insignificant group, and compact the group array. */
   {
      UInt insig1; // Position of first insignificant group.
      UInt n_insig = 0; // Nr of insignificant groups found.
      
      for (g = 0; g < *n_groups; g++) {
         if ((*groups)[g].total < sig_sz) {
            if (n_insig == 0) {
               // First insig group => transform it into the special group
               (*groups)[g].ms_ec = NULL;
               (*groups)[g].group_ip = 0;
               (*groups)[g].n_ec = 0;
               // start the sum of insig total as total
               insig1 = g;
            } else {
               // Add this insig group total into insig1 first group
               (*groups)[insig1].total += (*groups)[g].total;
            }
            n_insig++;
         } else {
            if (n_insig > 1)
               (*groups)[g - n_insig + 1] = (*groups)[g];
         }
      }
      if (n_insig > 0) {
         (*groups)[insig1].n_ec = n_insig;
         *n_groups -= n_insig - 1;
      }
      DMSG(1, "depth %u n_groups %u n_insig %u\n", depth, *n_groups, n_insig);
   }

   /* Sort on total size, bigger size first. */
   VG_(ssort)(*groups, *n_groups, sizeof(Ms_Group), ms_group_revcmp_total);
}

static void ms_output_group (VgFile* fp, UInt depth, Ms_Group* group,
                             SizeT sig_sz, double sig_pct_threshold)
{
   UInt i;
   Ms_Group* groups;
   UInt n_groups;

   // If this is an insignificant group, handle it specially
   if (group->ms_ec == NULL) {
      const HChar* s = ( 1 ==  group->n_ec? "," : "s, all" );
      vg_assert(group->group_ip == 0);
      FP("%*sn0: %lu in %d place%s below massif's threshold (%.2f%%)\n",
         depth+1, "", group->total, group->n_ec, s, sig_pct_threshold);
      return;
   }

   // Normal group => output the group and its subgroups.
   ms_make_groups(depth+1, group->ms_ec, group->n_ec, sig_sz,
                  &n_groups, &groups);

   FP("%*s" "n%u: %ld %s\n", 
      depth + 1, "",
      n_groups, 
      group->total,
      VG_(describe_IP)(group->ms_ec->ips[depth] - 1, NULL));
   /* XTREE??? Massif original code removes 1 to get the IP description. I am
      wondering if this is not something that predates revision r8818,
      which introduced a -1 in the stack unwind (see m_stacktrace.c)
      Kept for the moment to allow exact comparison with massif output, but
      probably we should remove this, as we very probably end up 2 bytes before
      the RA Return Address. */

   /* Output sub groups of this group. */
   for (i = 0; i < n_groups; i++)
      ms_output_group(fp, depth+1, &groups[i], sig_sz, sig_pct_threshold);

   VG_(free)(groups);
}

/* Allocate and build an array of Ms_Ec sorted by addresses in the
   Ms_Ec StackTrace. */
static void prepare_ms_ec (XTree* xt,
                           ULong (*report_value)(const void* value),
                           ULong* top_total, Ms_Ec** vms_ec, UInt* vn_ec)
{
   XT_shared* shared = xt->shared;
   const UInt n_xecu = VG_(sizeXA)(shared->xec);
   const UInt n_data_xecu = VG_(sizeXA)(xt->data);
   Ms_Ec* ms_ec = VG_(malloc)("XT_massif_print.ms_ec", n_xecu * sizeof(Ms_Ec));
   UInt n_xecu_sel = 0; // Nr of xecu that are selected for output.

   vg_assert(n_data_xecu <= n_xecu);

   // Ensure we have in shared->ips_order_xecu our xecu sorted by StackTrace.
   ensure_ips_order_xecu_valid(shared);

   *top_total = 0;
   DMSG(1, "iteration %u\n", n_xecu);
   for (UInt i = 0; i < n_xecu; i++) {
      Xecu xecu = *(Xecu*)VG_(indexXA)(shared->ips_order_xecu, i);
      xec* xe = (xec*)VG_(indexXA)(shared->xec, xecu);

      if (xecu >= n_data_xecu)
         continue; // No data for this xecu in xt->data.
      ms_ec[n_xecu_sel].n_ips = xe->n_ips_sel;
      if (ms_ec[n_xecu_sel].n_ips == 0)
         continue;
            
      ms_ec[n_xecu_sel].ips = VG_(get_ExeContext_StackTrace)(xe->ec) + xe->top;
      ms_ec[n_xecu_sel].report_value
         = (*report_value)(VG_(indexXA)(xt->data, xecu));
      *top_total += ms_ec[n_xecu_sel].report_value;

      n_xecu_sel++;
   }
   vg_assert(n_xecu_sel <= n_xecu);
      
   *vms_ec = ms_ec;
   *vn_ec = n_xecu_sel;
}

MsFile* VG_(XT_massif_open)
     (const HChar* outfilename,
      const HChar* desc,
      const XArray* desc_args,
      const HChar* time_unit)
{
   UInt i;
   VgFile* fp = xt_open(outfilename);
   
   if (fp == NULL)
      return NULL; // xt_open reported the error.
   
   /* ------ file header ------------------------------- */
   FP("desc:");
   if (desc)
      FP(" %s", desc);
   i = 0;
   if (desc_args) {
      for (i = 0; i < VG_(sizeXA)(desc_args); i++) {
         HChar* arg = *(HChar**)VG_(indexXA)(desc_args, i);
         FP(" %s", arg);
      }
   }
   if (0 == i && desc == NULL) FP(" (none)");
   FP("\n");

   FP_cmd(fp);

   FP("time_unit: %s\n", time_unit);

   return fp;
}

void VG_(XT_massif_close)(MsFile* fp)
{
   if (fp == NULL)
      return; // Error should have been reported by  VG_(XT_massif_open)

   VG_(fclose)(fp);
}

void VG_(XT_massif_print) 
     (MsFile* fp,
      XTree* xt,
      const Massif_Header* header,
      ULong (*report_value)(const void* value))
{
   UInt i;

   if (fp == NULL)
      return; // Normally  VG_(XT_massif_open) already reported an error.

   /* Compute/prepare Snapshot totals/data/... */
   ULong top_total;

   /* Following variables only used for detailed snapshot. */
   UInt n_ec = 0;
   Ms_Ec* ms_ec = NULL;
   const HChar* kind = 
      header->detailed ? (header->peak ? "peak" : "detailed") : "empty";

   DMSG(1, "XT_massif_print %s\n", kind);
   if (header->detailed) {
      /* Prepare the Ms_Ec sorted array of stacktraces and the groups
         at level 0. */
      prepare_ms_ec(xt, report_value, &top_total, &ms_ec, &n_ec);
      DMSG(1, "XT_print_massif ms_ec n_ec %u\n", n_ec);
   } else if (xt == NULL) {
      /* Non detailed, no xt => use the sz provided in the header. */
      top_total = header->sz_B;
   } else {
      /* For non detailed snapshot, compute total directly from the xec. */
      const XT_shared* shared = xt->shared;
      const UInt n_xecu = VG_(sizeXA)(xt->data);
      top_total = 0;
      
      for (UInt xecu = 0; xecu < n_xecu; xecu++) {
         xec* xe = (xec*)VG_(indexXA)(shared->xec, xecu);
         if (xe->n_ips_sel == 0)
            continue;
         top_total += (*report_value)(VG_(indexXA)(xt->data, xecu));
      }
   }

   /* ------ snapshot header --------------------------- */
   FP("#-----------\n");
   FP("snapshot=%d\n", header->snapshot_n);
   FP("#-----------\n");
   FP("time=%lld\n", header->time);
   
   FP("mem_heap_B=%llu\n", top_total); // without extra_B and without stacks_B
   FP("mem_heap_extra_B=%llu\n", header->extra_B);
   FP("mem_stacks_B=%llu\n", header->stacks_B);
   FP("heap_tree=%s\n", kind);

   /* ------ detailed snapshot data ----------------------------- */
   if (header->detailed) {
      UInt n_groups;
      Ms_Group* groups;

      ULong sig_sz;
      // Work out how big a child must be to be significant.  If the current
      // top_total is zero, then we set it to 1, which means everything will be
      // judged insignificant -- this is sensible, as there's no point showing
      // any detail for this case.  Unless they used threshold=0, in which
      // case we show them everything because that's what they asked for.
      //
      // Nb: We do this once now, rather than once per child, because if we do
      // that the cost of all the divisions adds up to something significant.
      if (0 == top_total && 0 != header->sig_threshold)
         sig_sz = 1;
      else
         sig_sz = ((top_total + header->extra_B + header->stacks_B) 
                   * header->sig_threshold) / 100;

      /* Produce the groups at depth 0 */
      DMSG(1, "XT_massif_print producing depth 0 groups\n");
      ms_make_groups(0, ms_ec, n_ec, sig_sz, &n_groups, &groups);

      /* Output the top node. */
      FP("n%u: %llu %s\n", n_groups, top_total, header->top_node_desc);

      /* Output depth 0 groups. */
      DMSG(1, "XT_massif_print outputing %u depth 0 groups\n", n_groups);
      for (i = 0; i < n_groups; i++)
         ms_output_group(fp, 0, &groups[i], sig_sz, header->sig_threshold);

      VG_(free)(groups);
      VG_(free)(ms_ec);
   }
}

Int VG_(XT_offset_main_or_below_main)(Addr* ips, Int n_ips)
{
   /* Search for main or below main function.
      To limit the nr of ips to examine, we maintain the deepest
      offset where main was found, and we first search main
      from there.
      If no main is found, we will then do a search for main or
      below main function till the top. */
   static Int deepest_main = 0;
   Vg_FnNameKind kind = Vg_FnNameNormal;
   Int mbm = n_ips - 1; // Position of deepest main or below main.
   Vg_FnNameKind mbmkind = Vg_FnNameNormal;
   Int i;

   for (i = n_ips - 1 - deepest_main;
        i < n_ips;
        i++) {
      mbmkind = VG_(get_fnname_kind_from_IP)(ips[i]);
      if (mbmkind != Vg_FnNameNormal) {
         mbm = i;
         break;
      }
   }

   /* Search for main or below main function till top. */
   for (i = mbm - 1;
        i >= 0 && mbmkind != Vg_FnNameMain;
        i--) {
      kind = VG_(get_fnname_kind_from_IP)(ips[i]);
      if (kind != Vg_FnNameNormal) {
         mbm = i;
         mbmkind = kind;
      }
   }
   if (Vg_FnNameMain == mbmkind || Vg_FnNameBelowMain == mbmkind) {
      if (mbmkind == Vg_FnNameMain && (n_ips - 1 - mbm) > deepest_main)
         deepest_main = n_ips - 1 - mbm;
      return mbm;
   } else
      return n_ips-1;
}

void VG_(XT_filter_1top_and_maybe_below_main)
     (Addr* ips, Int n_ips,
      UInt* top, UInt* n_ips_sel)
{
   Int mbm;

   *n_ips_sel = n_ips;
   if (n_ips == 0) {
      *top = 0;
      return;
   }

   /* Filter top function. */
   *top = 1;

   if (VG_(clo_show_below_main))
      mbm = n_ips - 1;
   else
      mbm = VG_(XT_offset_main_or_below_main)(ips, n_ips);

   *n_ips_sel = mbm - *top + 1;
}

void VG_(XT_filter_maybe_below_main)
     (Addr* ips, Int n_ips,
      UInt* top, UInt* n_ips_sel)
{
   Int mbm;

   *n_ips_sel = n_ips;
   *top = 0;
   if (n_ips == 0)
      return;

   if (VG_(clo_show_below_main))
      mbm = n_ips - 1;
   else
      mbm = VG_(XT_offset_main_or_below_main)(ips, n_ips);

   *n_ips_sel = mbm - *top + 1;
}

/*--------------------------------------------------------------------*/
/*--- end                                                m_xtree.c ---*/
/*--------------------------------------------------------------------*/