
/*--------------------------------------------------------------------*/
/*--- The leak checker.                             mc_leakcheck.c ---*/
/*--------------------------------------------------------------------*/

/*
   This file is part of MemCheck, a heavyweight Valgrind tool for
   detecting memory errors.

   Copyright (C) 2000-2012 Julian Seward 
      jseward@acm.org

   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_tool_basics.h"
#include "pub_tool_vki.h"
#include "pub_tool_aspacehl.h"
#include "pub_tool_aspacemgr.h"
#include "pub_tool_execontext.h"
#include "pub_tool_hashtable.h"
#include "pub_tool_libcbase.h"
#include "pub_tool_libcassert.h"
#include "pub_tool_libcprint.h"
#include "pub_tool_libcsignal.h"
#include "pub_tool_machine.h"
#include "pub_tool_mallocfree.h"
#include "pub_tool_options.h"
#include "pub_tool_oset.h"
#include "pub_tool_poolalloc.h"     
#include "pub_tool_signals.h"       // Needed for mc_include.h
#include "pub_tool_libcsetjmp.h"    // setjmp facilities
#include "pub_tool_tooliface.h"     // Needed for mc_include.h

#include "mc_include.h"

/*------------------------------------------------------------*/
/*--- An overview of leak checking.                        ---*/
/*------------------------------------------------------------*/

// Leak-checking is a directed-graph traversal problem.  The graph has
// two kinds of nodes:
// - root-set nodes:
//   - GP registers of all threads;
//   - valid, aligned, pointer-sized data words in valid client memory,
//     including stacks, but excluding words within client heap-allocated
//     blocks (they are excluded so that later on we can differentiate
//     between heap blocks that are indirectly leaked vs. directly leaked).
// - heap-allocated blocks.  A block is a mempool chunk or a malloc chunk
//   that doesn't contain a mempool chunk.  Nb: the terms "blocks" and
//   "chunks" are used interchangeably below.
//
// There are two kinds of edges:
// - start-pointers, i.e. pointers to the start of a block;
// - interior-pointers, i.e. pointers to the interior of a block.
//
// We use "pointers" rather than "edges" below.
//
// Root set nodes only point to blocks.  Blocks only point to blocks;
// a block can point to itself.
//
// The aim is to traverse the graph and determine the status of each block.
//
// There are 9 distinct cases.  See memcheck/docs/mc-manual.xml for details.
// Presenting all nine categories to the user is probably too much.
// Currently we do this:
// - definitely lost:  case 3
// - indirectly lost:  case 4, 9
// - possibly lost:    cases 5..8
// - still reachable:  cases 1, 2
// 
// It's far from clear that this is the best possible categorisation;  it's
// accreted over time without any central guiding principle.

/*------------------------------------------------------------*/
/*--- XXX: Thoughts for improvement.                       ---*/
/*------------------------------------------------------------*/

// From the user's point of view:
// - If they aren't using interior-pointers, they just have to fix the
//   directly lost blocks, and the indirectly lost ones will be fixed as
//   part of that.  Any possibly lost blocks will just be due to random
//   pointer garbage and can be ignored.
// 
// - If they are using interior-pointers, the fact that they currently are not
//   being told which ones might be directly lost vs. indirectly lost makes
//   it hard to know where to begin.
// 
// All this makes me wonder if new option is warranted:
// --follow-interior-pointers.  By default it would be off, the leak checker
// wouldn't follow interior-pointers and there would only be 3 categories:
// R, DL, IL.
// 
// If turned on, then it would show 7 categories (R, DL, IL, DR/DL, IR/IL,
// IR/IL/DL, IL/DL).  That output is harder to understand but it's your own
// damn fault for using interior-pointers...
//
// ----
//
// Also, why are two blank lines printed between each loss record?
// [bug 197930]
//
// ----
//
// Also, --show-reachable is a bad name because it also turns on the showing
// of indirectly leaked blocks(!)  It would be better named --show-all or
// --show-all-heap-blocks, because that's the end result.
//
// ----
//
// Also, the VALGRIND_LEAK_CHECK and VALGRIND_QUICK_LEAK_CHECK aren't great
// names.  VALGRIND_FULL_LEAK_CHECK and VALGRIND_SUMMARY_LEAK_CHECK would be
// better.
//
// ----
//
// Also, VALGRIND_COUNT_LEAKS and VALGRIND_COUNT_LEAK_BLOCKS aren't great as
// they combine direct leaks and indirect leaks into one.  New, more precise
// ones (they'll need new names) would be good.  If more categories are
// used, as per the --follow-interior-pointers option, they should be
// updated accordingly.  And they should use a struct to return the values.
//
// ----
//
// Also, for this case:
//
//  (4)  p4      BBB ---> AAA
// 
// BBB is definitely directly lost.  AAA is definitely indirectly lost.
// Here's the relevant loss records printed for a full check (each block is
// 16 bytes):
// 
// ==20397== 16 bytes in 1 blocks are indirectly lost in loss record 9 of 15
// ==20397==    at 0x4C2694E: malloc (vg_replace_malloc.c:177)
// ==20397==    by 0x400521: mk (leak-cases.c:49)
// ==20397==    by 0x400578: main (leak-cases.c:72)
// 
// ==20397== 32 (16 direct, 16 indirect) bytes in 1 blocks are definitely
// lost in loss record 14 of 15
// ==20397==    at 0x4C2694E: malloc (vg_replace_malloc.c:177)
// ==20397==    by 0x400521: mk (leak-cases.c:49)
// ==20397==    by 0x400580: main (leak-cases.c:72)
// 
// The first one is fine -- it describes AAA.
// 
// The second one is for BBB.  It's correct in that 16 bytes in 1 block are
// directly lost. It's also correct that 16 are indirectly lost as a result,
// but it means that AAA is being counted twice in the loss records.  (It's
// not, thankfully, counted twice in the summary counts).  Argh.
// 
// This would be less confusing for the second one:
// 
// ==20397== 16 bytes in 1 blocks are definitely lost in loss record 14
// of 15 (and 16 bytes in 1 block are indirectly lost as a result;  they
// are mentioned elsewhere (if --show-reachable=yes is given!))
// ==20397==    at 0x4C2694E: malloc (vg_replace_malloc.c:177)
// ==20397==    by 0x400521: mk (leak-cases.c:49)
// ==20397==    by 0x400580: main (leak-cases.c:72)
// 
// But ideally we'd present the loss record for the directly lost block and
// then the resultant indirectly lost blocks and make it clear the
// dependence.  Double argh.

/*------------------------------------------------------------*/
/*--- The actual algorithm.                                ---*/
/*------------------------------------------------------------*/

// - Find all the blocks (a.k.a. chunks) to check.  Mempool chunks require
//   some special treatment because they can be within malloc'd blocks.
// - Scan every word in the root set (GP registers and valid
//   non-heap memory words).
//   - First, we skip if it doesn't point to valid memory.
//   - Then, we see if it points to the start or interior of a block.  If
//     so, we push the block onto the mark stack and mark it as having been
//     reached.
// - Then, we process the mark stack, repeating the scanning for each block;
//   this can push more blocks onto the mark stack.  We repeat until the
//   mark stack is empty.  Each block is marked as definitely or possibly
//   reachable, depending on whether interior-pointers were required to
//   reach it.
// - At this point we know for every block if it's reachable or not.
// - We then push each unreached block onto the mark stack, using the block
//   number as the "clique" number.
// - We process the mark stack again, this time grouping blocks into cliques
//   in order to facilitate the directly/indirectly lost categorisation.
// - We group blocks by their ExeContexts and categorisation, and print them
//   if --leak-check=full.  We also print summary numbers.
//
// A note on "cliques":
// - A directly lost block is one with no pointers to it.  An indirectly
//   lost block is one that is pointed to by a directly or indirectly lost
//   block.
// - Each directly lost block has zero or more indirectly lost blocks
//   hanging off it.  All these blocks together form a "clique".  The
//   directly lost block is called the "clique leader".  The clique number
//   is the number (in lc_chunks[]) of the clique leader.
// - Actually, a directly lost block may be pointed to if it's part of a
//   cycle.  In that case, there may be more than one choice for the clique
//   leader, and the choice is arbitrary.  Eg. if you have A-->B and B-->A
//   either A or B could be the clique leader.
// - Cliques cannot overlap, and will be truncated to avoid this.  Eg. if we
//   have A-->C and B-->C, the two cliques will be {A,C} and {B}, or {A} and
//   {B,C} (again the choice is arbitrary).  This is because we don't want
//   to count a block as indirectly lost more than once.
//
// A note on 'is_prior_definite': 
// - This is a boolean used in various places that indicates if the chain
//   up to the prior node (prior to the one being considered) is definite.
// - In the clique == -1 case: 
//   - if True it means that the prior node is a root-set node, or that the
//     prior node is a block which is reachable from the root-set via
//     start-pointers.
//   - if False it means that the prior node is a block that is only
//     reachable from the root-set via a path including at least one
//     interior-pointer.
// - In the clique != -1 case, currently it's always True because we treat
//   start-pointers and interior-pointers the same for direct/indirect leak
//   checking.  If we added a PossibleIndirectLeak state then this would
//   change.


// Define to debug the memory-leak-detector.
#define VG_DEBUG_LEAKCHECK 0
#define VG_DEBUG_CLIQUE    0
 

/*------------------------------------------------------------*/
/*--- Getting the initial chunks, and searching them.      ---*/
/*------------------------------------------------------------*/

// Compare the MC_Chunks by 'data' (i.e. the address of the block).
static Int compare_MC_Chunks(void* n1, void* n2)
{
   MC_Chunk* mc1 = *(MC_Chunk**)n1;
   MC_Chunk* mc2 = *(MC_Chunk**)n2;
   if (mc1->data < mc2->data) return -1;
   if (mc1->data > mc2->data) return  1;
   return 0;
}

#if VG_DEBUG_LEAKCHECK
// Used to sanity-check the fast binary-search mechanism.
static 
Int find_chunk_for_OLD ( Addr       ptr, 
                         MC_Chunk** chunks,
                         Int        n_chunks )

{
   Int  i;
   Addr a_lo, a_hi;
   PROF_EVENT(70, "find_chunk_for_OLD");
   for (i = 0; i < n_chunks; i++) {
      PROF_EVENT(71, "find_chunk_for_OLD(loop)");
      a_lo = chunks[i]->data;
      a_hi = ((Addr)chunks[i]->data) + chunks[i]->szB;
      if (a_lo <= ptr && ptr < a_hi)
         return i;
   }
   return -1;
}
#endif

// Find the i such that ptr points at or inside the block described by
// chunks[i].  Return -1 if none found.  This assumes that chunks[]
// has been sorted on the 'data' field.
static 
Int find_chunk_for ( Addr       ptr, 
                     MC_Chunk** chunks,
                     Int        n_chunks )
{
   Addr a_mid_lo, a_mid_hi;
   Int lo, mid, hi, retVal;
   // VG_(printf)("find chunk for %p = ", ptr);
   retVal = -1;
   lo = 0;
   hi = n_chunks-1;
   while (True) {
      // Invariant: current unsearched space is from lo to hi, inclusive.
      if (lo > hi) break; // not found

      mid      = (lo + hi) / 2;
      a_mid_lo = chunks[mid]->data;
      a_mid_hi = chunks[mid]->data + chunks[mid]->szB;
      // Extent of block 'mid' is [a_mid_lo .. a_mid_hi).
      // Special-case zero-sized blocks - treat them as if they had
      // size 1.  Not doing so causes them to not cover any address
      // range at all and so will never be identified as the target of
      // any pointer, which causes them to be incorrectly reported as
      // definitely leaked.
      if (chunks[mid]->szB == 0)
         a_mid_hi++;

      if (ptr < a_mid_lo) {
         hi = mid-1;
         continue;
      } 
      if (ptr >= a_mid_hi) {
         lo = mid+1;
         continue;
      }
      tl_assert(ptr >= a_mid_lo && ptr < a_mid_hi);
      retVal = mid;
      break;
   }

#  if VG_DEBUG_LEAKCHECK
   tl_assert(retVal == find_chunk_for_OLD ( ptr, chunks, n_chunks ));
#  endif
   // VG_(printf)("%d\n", retVal);
   return retVal;
}


static MC_Chunk**
find_active_chunks(UInt* pn_chunks)
{
   // Our goal is to construct a set of chunks that includes every
   // mempool chunk, and every malloc region that *doesn't* contain a
   // mempool chunk.
   MC_Mempool *mp;
   MC_Chunk **mallocs, **chunks, *mc;
   UInt n_mallocs, n_chunks, m, s;
   Bool *malloc_chunk_holds_a_pool_chunk;

   // First we collect all the malloc chunks into an array and sort it.
   // We do this because we want to query the chunks by interior
   // pointers, requiring binary search.
   mallocs = (MC_Chunk**) VG_(HT_to_array)( MC_(malloc_list), &n_mallocs );
   if (n_mallocs == 0) {
      tl_assert(mallocs == NULL);
      *pn_chunks = 0;
      return NULL;
   }
   VG_(ssort)(mallocs, n_mallocs, sizeof(VgHashNode*), compare_MC_Chunks);

   // Then we build an array containing a Bool for each malloc chunk,
   // indicating whether it contains any mempools.
   malloc_chunk_holds_a_pool_chunk = VG_(calloc)( "mc.fas.1",
                                                  n_mallocs, sizeof(Bool) );
   n_chunks = n_mallocs;

   // Then we loop over the mempool tables. For each chunk in each
   // pool, we set the entry in the Bool array corresponding to the
   // malloc chunk containing the mempool chunk.
   VG_(HT_ResetIter)(MC_(mempool_list));
   while ( (mp = VG_(HT_Next)(MC_(mempool_list))) ) {
      VG_(HT_ResetIter)(mp->chunks);
      while ( (mc = VG_(HT_Next)(mp->chunks)) ) {

         // We'll need to record this chunk.
         n_chunks++;

         // Possibly invalidate the malloc holding the beginning of this chunk.
         m = find_chunk_for(mc->data, mallocs, n_mallocs);
         if (m != -1 && malloc_chunk_holds_a_pool_chunk[m] == False) {
            tl_assert(n_chunks > 0);
            n_chunks--;
            malloc_chunk_holds_a_pool_chunk[m] = True;
         }

         // Possibly invalidate the malloc holding the end of this chunk.
         if (mc->szB > 1) {
            m = find_chunk_for(mc->data + (mc->szB - 1), mallocs, n_mallocs);
            if (m != -1 && malloc_chunk_holds_a_pool_chunk[m] == False) {
               tl_assert(n_chunks > 0);
               n_chunks--;
               malloc_chunk_holds_a_pool_chunk[m] = True;
            }
         }
      }
   }
   tl_assert(n_chunks > 0);

   // Create final chunk array.
   chunks = VG_(malloc)("mc.fas.2", sizeof(VgHashNode*) * (n_chunks));
   s = 0;

   // Copy the mempool chunks and the non-marked malloc chunks into a
   // combined array of chunks.
   VG_(HT_ResetIter)(MC_(mempool_list));
   while ( (mp = VG_(HT_Next)(MC_(mempool_list))) ) {
      VG_(HT_ResetIter)(mp->chunks);
      while ( (mc = VG_(HT_Next)(mp->chunks)) ) {
         tl_assert(s < n_chunks);
         chunks[s++] = mc;
      }
   }
   for (m = 0; m < n_mallocs; ++m) {
      if (!malloc_chunk_holds_a_pool_chunk[m]) {
         tl_assert(s < n_chunks);
         chunks[s++] = mallocs[m];
      }
   }
   tl_assert(s == n_chunks);

   // Free temporaries.
   VG_(free)(mallocs);
   VG_(free)(malloc_chunk_holds_a_pool_chunk);

   *pn_chunks = n_chunks;

   return chunks;
}

/*------------------------------------------------------------*/
/*--- The leak detector proper.                            ---*/
/*------------------------------------------------------------*/

// Holds extra info about each block during leak checking.
typedef 
   struct {
      UInt  state:2;    // Reachedness.
      UInt  pending:1;  // Scan pending.  
      union {
         SizeT indirect_szB : (sizeof(SizeT)*8)-3; // If Unreached, how many bytes
                                                   //   are unreachable from here.
         SizeT  clique :  (sizeof(SizeT)*8)-3;      // if IndirectLeak, clique leader
                                                   // to which it belongs.
      } IorC;
   } 
   LC_Extra;

// An array holding pointers to every chunk we're checking.  Sorted by address.
// lc_chunks is initialised during leak search. It is kept after leak search
// to support printing the list of blocks belonging to a loss record.
// lc_chunk array can only be used validly till the next "free" operation
// (as a free operation potentially destroys one or more chunks).
// To detect lc_chunk is valid, we store the nr of frees operations done
// when lc_chunk was build : lc_chunks (and lc_extras) stays valid as
// long as no free operations has been done since lc_chunks building.
static MC_Chunk** lc_chunks;
// How many chunks we're dealing with.
static Int        lc_n_chunks;
static SizeT lc_chunks_n_frees_marker;
// This has the same number of entries as lc_chunks, and each entry
// in lc_chunks corresponds with the entry here (ie. lc_chunks[i] and
// lc_extras[i] describe the same block).
static LC_Extra* lc_extras;

// chunks will be converted and merged in loss record, maintained in lr_table
// lr_table elements are kept from one leak_search to another to implement
// the "print new/changed leaks" client request
static OSet*        lr_table;
// Array of sorted loss record (produced during last leak search).
static LossRecord** lr_array;


// DeltaMode used the last time we called detect_memory_leaks.
// The recorded leak errors must be output using a logic based on this delta_mode.
// The below avoids replicating the delta_mode in each LossRecord.
LeakCheckDeltaMode MC_(detect_memory_leaks_last_delta_mode);


// Records chunks that are currently being processed.  Each element in the
// stack is an index into lc_chunks and lc_extras.  Its size is
// 'lc_n_chunks' because in the worst case that's how many chunks could be
// pushed onto it (actually I think the maximum is lc_n_chunks-1 but let's
// be conservative).
static Int* lc_markstack;
// The index of the top element of the stack; -1 if the stack is empty, 0 if
// the stack has one element, 1 if it has two, etc.
static Int  lc_markstack_top;    

// Keeps track of how many bytes of memory we've scanned, for printing.
// (Nb: We don't keep track of how many register bytes we've scanned.)
static SizeT lc_scanned_szB;


SizeT MC_(bytes_leaked)     = 0;
SizeT MC_(bytes_indirect)   = 0;
SizeT MC_(bytes_dubious)    = 0;
SizeT MC_(bytes_reachable)  = 0;
SizeT MC_(bytes_suppressed) = 0;

SizeT MC_(blocks_leaked)     = 0;
SizeT MC_(blocks_indirect)   = 0;
SizeT MC_(blocks_dubious)    = 0;
SizeT MC_(blocks_reachable)  = 0;
SizeT MC_(blocks_suppressed) = 0;

// Determines if a pointer is to a chunk.  Returns the chunk number et al
// via call-by-reference.
static Bool
lc_is_a_chunk_ptr(Addr ptr, Int* pch_no, MC_Chunk** pch, LC_Extra** pex)
{
   Int ch_no;
   MC_Chunk* ch;
   LC_Extra* ex;

   // Quick filter. Note: implemented with am, not with get_vabits2
   // as ptr might be random data pointing anywhere. On 64 bit
   // platforms, getting va bits for random data can be quite costly
   // due to the secondary map.
   if (!VG_(am_is_valid_for_client)(ptr, 1, VKI_PROT_READ)) {
      return False;
   } else {
      ch_no = find_chunk_for(ptr, lc_chunks, lc_n_chunks);
      tl_assert(ch_no >= -1 && ch_no < lc_n_chunks);

      if (ch_no == -1) {
         return False;
      } else {
         // Ok, we've found a pointer to a chunk.  Get the MC_Chunk and its
         // LC_Extra.
         ch = lc_chunks[ch_no];
         ex = &(lc_extras[ch_no]);

         tl_assert(ptr >= ch->data);
         tl_assert(ptr < ch->data + ch->szB + (ch->szB==0  ? 1  : 0));

         if (VG_DEBUG_LEAKCHECK)
            VG_(printf)("ptr=%#lx -> block %d\n", ptr, ch_no);

         *pch_no = ch_no;
         *pch    = ch;
         *pex    = ex;

         return True;
      }
   }
}

// Push a chunk (well, just its index) onto the mark stack.
static void lc_push(Int ch_no, MC_Chunk* ch)
{
   if (!lc_extras[ch_no].pending) {
      if (0) {
         VG_(printf)("pushing %#lx-%#lx\n", ch->data, ch->data + ch->szB);
      }
      lc_markstack_top++;
      tl_assert(lc_markstack_top < lc_n_chunks);
      lc_markstack[lc_markstack_top] = ch_no;
      tl_assert(!lc_extras[ch_no].pending);
      lc_extras[ch_no].pending = True;
   }
}

// Return the index of the chunk on the top of the mark stack, or -1 if
// there isn't one.
static Bool lc_pop(Int* ret)
{
   if (-1 == lc_markstack_top) {
      return False;
   } else {
      tl_assert(0 <= lc_markstack_top && lc_markstack_top < lc_n_chunks);
      *ret = lc_markstack[lc_markstack_top];
      lc_markstack_top--;
      tl_assert(lc_extras[*ret].pending);
      lc_extras[*ret].pending = False;
      return True;
   }
}


// If 'ptr' is pointing to a heap-allocated block which hasn't been seen
// before, push it onto the mark stack.
static void
lc_push_without_clique_if_a_chunk_ptr(Addr ptr, Bool is_prior_definite)
{
   Int ch_no;
   MC_Chunk* ch;
   LC_Extra* ex;

   if ( ! lc_is_a_chunk_ptr(ptr, &ch_no, &ch, &ex) )
      return;
   
   // Possibly upgrade the state, ie. one of:
   // - Unreached --> Possible
   // - Unreached --> Reachable 
   // - Possible  --> Reachable
   if (ptr == ch->data && is_prior_definite && ex->state != Reachable) {
      // 'ptr' points to the start of the block, and the prior node is
      // definite, which means that this block is definitely reachable.
      ex->state = Reachable;

      // State has changed to Reachable so (re)scan the block to make
      // sure any blocks it points to are correctly marked.
      lc_push(ch_no, ch);

   } else if (ex->state == Unreached) {
      // Either 'ptr' is a interior-pointer, or the prior node isn't definite,
      // which means that we can only mark this block as possibly reachable.
      ex->state = Possible;

      // State has changed to Possible so (re)scan the block to make
      // sure any blocks it points to are correctly marked.
      lc_push(ch_no, ch);
   }
}

static void
lc_push_if_a_chunk_ptr_register(ThreadId tid, HChar* regname, Addr ptr)
{
   lc_push_without_clique_if_a_chunk_ptr(ptr, /*is_prior_definite*/True);
}

// If ptr is pointing to a heap-allocated block which hasn't been seen
// before, push it onto the mark stack.  Clique is the index of the
// clique leader.
static void
lc_push_with_clique_if_a_chunk_ptr(Addr ptr, Int clique, Int cur_clique)
{
   Int ch_no;
   MC_Chunk* ch;
   LC_Extra* ex;

   tl_assert(0 <= clique && clique < lc_n_chunks);

   if ( ! lc_is_a_chunk_ptr(ptr, &ch_no, &ch, &ex) )
      return;

   // If it's not Unreached, it's already been handled so ignore it.
   // If ch_no==clique, it's the clique leader, which means this is a cyclic
   // structure;  again ignore it because it's already been handled.
   if (ex->state == Unreached && ch_no != clique) {
      // Note that, unlike reachable blocks, we currently don't distinguish
      // between start-pointers and interior-pointers here.  We probably
      // should, though.
      lc_push(ch_no, ch);

      // Add the block to the clique, and add its size to the
      // clique-leader's indirect size.  Also, if the new block was
      // itself a clique leader, it isn't any more, so add its
      // indirect_szB to the new clique leader.
      if (VG_DEBUG_CLIQUE) {
         if (ex->IorC.indirect_szB > 0)
            VG_(printf)("  clique %d joining clique %d adding %lu+%lu\n", 
                        ch_no, clique, (unsigned long)ch->szB,
			(unsigned long)ex->IorC.indirect_szB);
         else
            VG_(printf)("  block %d joining clique %d adding %lu\n", 
                        ch_no, clique, (unsigned long)ch->szB);
      }

      lc_extras[clique].IorC.indirect_szB += ch->szB;
      lc_extras[clique].IorC.indirect_szB += ex->IorC.indirect_szB;
      ex->state = IndirectLeak;
      ex->IorC.clique = (SizeT) cur_clique;
   }
}

static void
lc_push_if_a_chunk_ptr(Addr ptr, Int clique, Int cur_clique, Bool is_prior_definite)
{
   if (-1 == clique) 
      lc_push_without_clique_if_a_chunk_ptr(ptr, is_prior_definite);
   else
      lc_push_with_clique_if_a_chunk_ptr(ptr, clique, cur_clique);
}


static VG_MINIMAL_JMP_BUF(memscan_jmpbuf);

static
void scan_all_valid_memory_catcher ( Int sigNo, Addr addr )
{
   if (0)
      VG_(printf)("OUCH! sig=%d addr=%#lx\n", sigNo, addr);
   if (sigNo == VKI_SIGSEGV || sigNo == VKI_SIGBUS)
      VG_MINIMAL_LONGJMP(memscan_jmpbuf);
}

// lc_scan_memory has 2 modes:
//
// 1. Leak check mode (searched == 0).
// -----------------------------------
// Scan a block of memory between [start, start+len).  This range may
// be bogus, inaccessable, or otherwise strange; we deal with it.  For each
// valid aligned word we assume it's a pointer to a chunk a push the chunk
// onto the mark stack if so.
// clique is the "highest level clique" in which indirectly leaked blocks have
// to be collected. cur_clique is the current "lower" level clique through which
// the memory to be scanned has been found.
// Example: in the below tree if A is leaked, the top level clique will
//   be A, while lower level cliques will be B and C. 
/*
           A
         /   \                          
        B     C
       / \   / \ 
      D   E F   G
*/
// Proper handling of top and lowest level clique allows block_list of a loss
// record to describe the hierarchy of indirectly leaked blocks.
//
// 2. Search ptr mode (searched != 0).
// -----------------------------------
// In this mode, searches for pointers to a specific address range 
// In such a case, lc_scan_memory just scans [start..start+len[ for pointers to searched
// and outputs the places where searched is found. It does not recursively scans the
// found memory.
static void
lc_scan_memory(Addr start, SizeT len, Bool is_prior_definite, Int clique, Int cur_clique,
               Addr searched, SizeT szB)
{
   /* memory scan is based on the assumption that valid pointers are aligned
      on a multiple of sizeof(Addr). So, we can (and must) skip the begin and
      end portions of the block if they are not aligned on sizeof(Addr):
      These cannot be a valid pointer, and calls to MC_(is_valid_aligned_word)
      will assert for a non aligned address. */
   Addr ptr = VG_ROUNDUP(start,     sizeof(Addr));
   Addr end = VG_ROUNDDN(start+len, sizeof(Addr));
   vki_sigset_t sigmask;

   if (VG_DEBUG_LEAKCHECK)
      VG_(printf)("scan %#lx-%#lx (%lu)\n", start, end, len);

   VG_(sigprocmask)(VKI_SIG_SETMASK, NULL, &sigmask);
   VG_(set_fault_catcher)(scan_all_valid_memory_catcher);

   /* Optimisation: the loop below will check for each begin
      of SM chunk if the chunk is fully unaddressable. The idea is to
      skip efficiently such fully unaddressable SM chunks.
      So, we preferrably start the loop on a chunk boundary.
      If the chunk is not fully unaddressable, we might be in
      an unaddressable page. Again, the idea is to skip efficiently
      such unaddressable page : this is the "else" part.
      We use an "else" so that two consecutive fully unaddressable
      SM chunks will be skipped efficiently: first one is skipped
      by this piece of code. The next SM chunk will be skipped inside
      the loop. */
   if ( ! MC_(is_within_valid_secondary)(ptr) ) {
      // Skip an invalid SM chunk till the beginning of the next SM Chunk.
      ptr = VG_ROUNDUP(ptr+1, SM_SIZE);
   } else if (!VG_(am_is_valid_for_client)(ptr, sizeof(Addr), VKI_PROT_READ)) {
      // else we are in a (at least partially) valid SM chunk.
      // We might be in the middle of an unreadable page.
      // Do a cheap check to see if it's valid;
      // if not, skip onto the next page.
      ptr = VG_PGROUNDUP(ptr+1);        // First page is bad - skip it.
   }
   /* This optimisation and below loop is based on some relationships between
      VKI_PAGE_SIZE, SM_SIZE and sizeof(Addr) which are asserted in
      MC_(detect_memory_leaks). */

   while (ptr < end) {
      Addr addr;

      // Skip invalid chunks.
      if (UNLIKELY((ptr % SM_SIZE) == 0)) {
         if (! MC_(is_within_valid_secondary)(ptr) ) {
            ptr = VG_ROUNDUP(ptr+1, SM_SIZE);
            continue;
         }
      }

      // Look to see if this page seems reasonable.
      if (UNLIKELY((ptr % VKI_PAGE_SIZE) == 0)) {
         if (!VG_(am_is_valid_for_client)(ptr, sizeof(Addr), VKI_PROT_READ)) {
            ptr += VKI_PAGE_SIZE;      // Bad page - skip it.
            continue;
         }
         // aspacemgr indicates the page is readable and belongs to client.
         // We still probe the page explicitely in case aspacemgr is
         // desynchronised with the real page mappings.
         // Such a desynchronisation can happen due to an aspacemgr bug.
         // Note that if the application is using mprotect(NONE), then
         // a page can be unreadable but have addressable and defined
         // VA bits (see mc_main.c function mc_new_mem_mprotect).
         if (VG_MINIMAL_SETJMP(memscan_jmpbuf) == 0) {
            // Try a read in the beginning of the page ...
            Addr test = *(volatile Addr *)ptr;
            __asm__ __volatile__("": :"r"(test) : "cc","memory");
         } else {
            // Catch read error ...
            // We need to restore the signal mask, because we were
            // longjmped out of a signal handler.
            VG_(sigprocmask)(VKI_SIG_SETMASK, &sigmask, NULL);
            ptr += VKI_PAGE_SIZE;      // Bad page - skip it.
            continue;
         }
      }

      if ( MC_(is_valid_aligned_word)(ptr) ) {
         lc_scanned_szB += sizeof(Addr);
         addr = *(Addr *)ptr;
         // If we get here, the scanned word is in valid memory.  Now
         // let's see if its contents point to a chunk.
         if (UNLIKELY(searched)) {
            if (addr >= searched && addr < searched + szB) {
               if (addr == searched)
                  VG_(umsg)("*%#lx points at %#lx\n", ptr, searched);
               else
                  VG_(umsg)("*%#lx interior points at %lu bytes inside %#lx\n",
                            ptr, (long unsigned) addr - searched, searched);
               MC_(pp_describe_addr) (ptr);
            }
         } else {
            lc_push_if_a_chunk_ptr(addr, clique, cur_clique, is_prior_definite);
         }
      } else if (0 && VG_DEBUG_LEAKCHECK) {
         VG_(printf)("%#lx not valid\n", ptr);
      }
      ptr += sizeof(Addr);
   }

   VG_(sigprocmask)(VKI_SIG_SETMASK, &sigmask, NULL);
   VG_(set_fault_catcher)(NULL);
}


// Process the mark stack until empty.
static void lc_process_markstack(Int clique)
{
   Int  top = -1;    // shut gcc up
   Bool is_prior_definite;

   while (lc_pop(&top)) {
      tl_assert(top >= 0 && top < lc_n_chunks);

      // See comment about 'is_prior_definite' at the top to understand this.
      is_prior_definite = ( Possible != lc_extras[top].state );

      lc_scan_memory(lc_chunks[top]->data, lc_chunks[top]->szB,
                     is_prior_definite, clique, (clique == -1 ? -1 : top),
                     /*searched*/ 0, 0);
   }
}

static Word cmp_LossRecordKey_LossRecord(const void* key, const void* elem)
{
   LossRecordKey* a = (LossRecordKey*)key;
   LossRecordKey* b = &(((LossRecord*)elem)->key);

   // Compare on states first because that's fast.
   if (a->state < b->state) return -1;
   if (a->state > b->state) return  1;
   // Ok, the states are equal.  Now compare the locations, which is slower.
   if (VG_(eq_ExeContext)(
            MC_(clo_leak_resolution), a->allocated_at, b->allocated_at))
      return 0;
   // Different locations.  Ordering is arbitrary, just use the ec pointer.
   if (a->allocated_at < b->allocated_at) return -1;
   if (a->allocated_at > b->allocated_at) return  1;
   VG_(tool_panic)("bad LossRecord comparison");
}

static Int cmp_LossRecords(void* va, void* vb)
{
   LossRecord* lr_a = *(LossRecord**)va;
   LossRecord* lr_b = *(LossRecord**)vb;
   SizeT total_szB_a = lr_a->szB + lr_a->indirect_szB;
   SizeT total_szB_b = lr_b->szB + lr_b->indirect_szB;

   // First compare by sizes.
   if (total_szB_a < total_szB_b) return -1;
   if (total_szB_a > total_szB_b) return  1;
   // If size are equal, compare by states.
   if (lr_a->key.state < lr_b->key.state) return -1;
   if (lr_a->key.state > lr_b->key.state) return  1;
   // If they're still equal here, it doesn't matter that much, but we keep
   // comparing other things so that regtests are as deterministic as
   // possible.  So:  compare num_blocks.
   if (lr_a->num_blocks < lr_b->num_blocks) return -1;
   if (lr_a->num_blocks > lr_b->num_blocks) return  1;
   // Finally, compare ExeContext addresses... older ones are likely to have
   // lower addresses.
   if (lr_a->key.allocated_at < lr_b->key.allocated_at) return -1;
   if (lr_a->key.allocated_at > lr_b->key.allocated_at) return  1;
   return 0;
}

// allocates or reallocates lr_array, and set its elements to the loss records
// contains in lr_table.
static Int get_lr_array_from_lr_table(void) {
   Int          i, n_lossrecords;
   LossRecord*  lr;

   n_lossrecords = VG_(OSetGen_Size)(lr_table);

   // (re-)create the array of pointers to the loss records.
   // lr_array is kept to allow producing the block list from gdbserver.
   if (lr_array != NULL)
      VG_(free)(lr_array);
   lr_array = VG_(malloc)("mc.pr.2", n_lossrecords * sizeof(LossRecord*));
   i = 0;
   VG_(OSetGen_ResetIter)(lr_table);
   while ( (lr = VG_(OSetGen_Next)(lr_table)) ) {
      lr_array[i++] = lr;
   }
   tl_assert(i == n_lossrecords);
   return n_lossrecords;
}


static void get_printing_rules(LeakCheckParams* lcp,
                               LossRecord*  lr,
                               Bool* count_as_error,
                               Bool* print_record)
{
   // Rules for printing:
   // - We don't show suppressed loss records ever (and that's controlled
   //   within the error manager).
   // - We show non-suppressed loss records that are not "reachable" if 
   //   --leak-check=yes.
   // - We show all non-suppressed loss records if --leak-check=yes and
   //   --show-reachable=yes.
   //
   // Nb: here "reachable" means Reachable *or* IndirectLeak;  note that
   // this is different to "still reachable" used elsewhere because it
   // includes indirectly lost blocks!

   Bool delta_considered;

   switch (lcp->deltamode) {
   case LCD_Any: 
      delta_considered = lr->num_blocks > 0;
      break;
   case LCD_Increased:
      delta_considered 
         = lr->szB > lr->old_szB
         || lr->indirect_szB > lr->old_indirect_szB
         || lr->num_blocks > lr->old_num_blocks;
      break;
   case LCD_Changed: 
      delta_considered = lr->szB != lr->old_szB
         || lr->indirect_szB != lr->old_indirect_szB
         || lr->num_blocks != lr->old_num_blocks;
      break;
   default:
      tl_assert(0);
   }

   *print_record = lcp->mode == LC_Full && delta_considered &&
      ( lcp->show_reachable ||
        Unreached == lr->key.state || 
        ( lcp->show_possibly_lost && 
          Possible  == lr->key.state ) );
   // We don't count a leaks as errors with lcp->mode==LC_Summary.
   // Otherwise you can get high error counts with few or no error
   // messages, which can be confusing.  Also, you could argue that
   // indirect leaks should be counted as errors, but it seems better to
   // make the counting criteria similar to the printing criteria.  So we
   // don't count them.
   *count_as_error = lcp->mode == LC_Full && delta_considered &&
      ( Unreached == lr->key.state || 
        Possible  == lr->key.state );
}

static void print_results(ThreadId tid, LeakCheckParams* lcp)
{
   Int          i, n_lossrecords, start_lr_output_scan;
   LossRecord*  lr;
   Bool         is_suppressed;
   SizeT        old_bytes_leaked      = MC_(bytes_leaked); /* to report delta in summary */
   SizeT        old_bytes_indirect    = MC_(bytes_indirect); 
   SizeT        old_bytes_dubious     = MC_(bytes_dubious); 
   SizeT        old_bytes_reachable   = MC_(bytes_reachable); 
   SizeT        old_bytes_suppressed  = MC_(bytes_suppressed); 
   SizeT        old_blocks_leaked     = MC_(blocks_leaked);
   SizeT        old_blocks_indirect   = MC_(blocks_indirect);
   SizeT        old_blocks_dubious    = MC_(blocks_dubious);
   SizeT        old_blocks_reachable  = MC_(blocks_reachable);
   SizeT        old_blocks_suppressed = MC_(blocks_suppressed);

   if (lr_table == NULL)
      // Create the lr_table, which holds the loss records.
      // If the lr_table already exists, it means it contains
      // loss_records from the previous leak search. The old_*
      // values in these records are used to implement the
      // leak check delta mode
      lr_table =
         VG_(OSetGen_Create)(offsetof(LossRecord, key),
                             cmp_LossRecordKey_LossRecord,
                             VG_(malloc), "mc.pr.1",
                             VG_(free));

   // If we have loss records from a previous search, reset values to have
   // proper printing of the deltas between previous search and this search.
   n_lossrecords = get_lr_array_from_lr_table();
   for (i = 0; i < n_lossrecords; i++) {
      if (lr_array[i]->num_blocks == 0) {
         // remove from lr_table the old loss_records with 0 bytes found
         VG_(OSetGen_Remove) (lr_table, &lr_array[i]->key);
         VG_(OSetGen_FreeNode)(lr_table, lr_array[i]);
      } else {
         // move the leak sizes to old_* and zero the current sizes
         // for next leak search
         lr_array[i]->old_szB          = lr_array[i]->szB;
         lr_array[i]->old_indirect_szB = lr_array[i]->indirect_szB;
         lr_array[i]->old_num_blocks   = lr_array[i]->num_blocks;
         lr_array[i]->szB              = 0;
         lr_array[i]->indirect_szB     = 0;
         lr_array[i]->num_blocks       = 0;
      }
   }
   // lr_array now contains "invalid" loss records => free it.
   // lr_array will be re-created below with the kept and new loss records.
   VG_(free) (lr_array);
   lr_array = NULL;

   // Convert the chunks into loss records, merging them where appropriate.
   for (i = 0; i < lc_n_chunks; i++) {
      MC_Chunk*     ch = lc_chunks[i];
      LC_Extra*     ex = &(lc_extras)[i];
      LossRecord*   old_lr;
      LossRecordKey lrkey;
      lrkey.state        = ex->state;
      lrkey.allocated_at = ch->where;

      old_lr = VG_(OSetGen_Lookup)(lr_table, &lrkey);
      if (old_lr) {
         // We found an existing loss record matching this chunk.  Update the
         // loss record's details in-situ.  This is safe because we don't
         // change the elements used as the OSet key.
         old_lr->szB          += ch->szB;
         if (ex->state == Unreached)
            old_lr->indirect_szB += ex->IorC.indirect_szB;
         old_lr->num_blocks++;
      } else {
         // No existing loss record matches this chunk.  Create a new loss
         // record, initialise it from the chunk, and insert it into lr_table.
         lr = VG_(OSetGen_AllocNode)(lr_table, sizeof(LossRecord));
         lr->key              = lrkey;
         lr->szB              = ch->szB;
         if (ex->state == Unreached)
            lr->indirect_szB     = ex->IorC.indirect_szB;
         else
            lr->indirect_szB     = 0;
         lr->num_blocks       = 1;
         lr->old_szB          = 0;
         lr->old_indirect_szB = 0;
         lr->old_num_blocks   = 0;
         VG_(OSetGen_Insert)(lr_table, lr);
      }
   }

   // (re-)create the array of pointers to the (new) loss records.
   n_lossrecords = get_lr_array_from_lr_table ();
   tl_assert(VG_(OSetGen_Size)(lr_table) == n_lossrecords);

   // Sort the array by loss record sizes.
   VG_(ssort)(lr_array, n_lossrecords, sizeof(LossRecord*),
              cmp_LossRecords);

   // Zero totals.
   MC_(blocks_leaked)     = MC_(bytes_leaked)     = 0;
   MC_(blocks_indirect)   = MC_(bytes_indirect)   = 0;
   MC_(blocks_dubious)    = MC_(bytes_dubious)    = 0;
   MC_(blocks_reachable)  = MC_(bytes_reachable)  = 0;
   MC_(blocks_suppressed) = MC_(bytes_suppressed) = 0;

   // If there is a maximum nr of loss records we can output, then first
   // compute from where the output scan has to start.
   // By default, start from the first loss record. Compute a higher
   // value if there is a maximum to respect. We need to print the last
   // records, as the one with the biggest sizes are more interesting.
   start_lr_output_scan = 0;
   if (lcp->mode == LC_Full && lcp->max_loss_records_output < n_lossrecords) {
      Int nr_printable_records = 0;
      for (i = n_lossrecords - 1; i >= 0 && start_lr_output_scan == 0; i--) {
         Bool count_as_error, print_record;
         lr = lr_array[i];
         get_printing_rules (lcp, lr, &count_as_error, &print_record);
         // Do not use get_printing_rules results for is_suppressed, as we
         // only want to check if the record would be suppressed.
         is_suppressed = 
            MC_(record_leak_error) ( tid, i+1, n_lossrecords, lr, 
                                     False /* print_record */,
                                     False /* count_as_error */);
         if (print_record && !is_suppressed) {
            nr_printable_records++;
            if (nr_printable_records == lcp->max_loss_records_output)
               start_lr_output_scan = i;
         }
      }
   }

   // Print the loss records (in size order) and collect summary stats.
   for (i = start_lr_output_scan; i < n_lossrecords; i++) {
      Bool count_as_error, print_record;
      lr = lr_array[i];
      get_printing_rules(lcp, lr, &count_as_error, &print_record);
      is_suppressed = 
         MC_(record_leak_error) ( tid, i+1, n_lossrecords, lr, print_record,
                                  count_as_error );

      if (is_suppressed) {
         MC_(blocks_suppressed) += lr->num_blocks;
         MC_(bytes_suppressed)  += lr->szB;

      } else if (Unreached == lr->key.state) {
         MC_(blocks_leaked)     += lr->num_blocks;
         MC_(bytes_leaked)      += lr->szB;

      } else if (IndirectLeak == lr->key.state) {
         MC_(blocks_indirect)   += lr->num_blocks;
         MC_(bytes_indirect)    += lr->szB;

      } else if (Possible == lr->key.state) {
         MC_(blocks_dubious)    += lr->num_blocks;
         MC_(bytes_dubious)     += lr->szB;

      } else if (Reachable == lr->key.state) {
         MC_(blocks_reachable)  += lr->num_blocks;
         MC_(bytes_reachable)   += lr->szB;

      } else {
         VG_(tool_panic)("unknown loss mode");
      }
   }

   if (VG_(clo_verbosity) > 0 && !VG_(clo_xml)) {
      char d_bytes[20];
      char d_blocks[20];

      VG_(umsg)("LEAK SUMMARY:\n");
      VG_(umsg)("   definitely lost: %'lu%s bytes in %'lu%s blocks\n",
                MC_(bytes_leaked), 
                MC_(snprintf_delta) (d_bytes, 20, MC_(bytes_leaked), old_bytes_leaked, lcp->deltamode),
                MC_(blocks_leaked),
                MC_(snprintf_delta) (d_blocks, 20, MC_(blocks_leaked), old_blocks_leaked, lcp->deltamode));
      VG_(umsg)("   indirectly lost: %'lu%s bytes in %'lu%s blocks\n",
                MC_(bytes_indirect), 
                MC_(snprintf_delta) (d_bytes, 20, MC_(bytes_indirect), old_bytes_indirect, lcp->deltamode),
                MC_(blocks_indirect),
                MC_(snprintf_delta) (d_blocks, 20, MC_(blocks_indirect), old_blocks_indirect, lcp->deltamode) );
      VG_(umsg)("     possibly lost: %'lu%s bytes in %'lu%s blocks\n",
                MC_(bytes_dubious), 
                MC_(snprintf_delta) (d_bytes, 20, MC_(bytes_dubious), old_bytes_dubious, lcp->deltamode), 
                MC_(blocks_dubious),
                MC_(snprintf_delta) (d_blocks, 20, MC_(blocks_dubious), old_blocks_dubious, lcp->deltamode) );
      VG_(umsg)("   still reachable: %'lu%s bytes in %'lu%s blocks\n",
                MC_(bytes_reachable), 
                MC_(snprintf_delta) (d_bytes, 20, MC_(bytes_reachable), old_bytes_reachable, lcp->deltamode), 
                MC_(blocks_reachable),
                MC_(snprintf_delta) (d_blocks, 20, MC_(blocks_reachable), old_blocks_reachable, lcp->deltamode) );
      VG_(umsg)("        suppressed: %'lu%s bytes in %'lu%s blocks\n",
                MC_(bytes_suppressed), 
                MC_(snprintf_delta) (d_bytes, 20, MC_(bytes_suppressed), old_bytes_suppressed, lcp->deltamode), 
                MC_(blocks_suppressed),
                MC_(snprintf_delta) (d_blocks, 20, MC_(blocks_suppressed), old_blocks_suppressed, lcp->deltamode) );
      if (lcp->mode != LC_Full &&
          (MC_(blocks_leaked) + MC_(blocks_indirect) +
           MC_(blocks_dubious) + MC_(blocks_reachable)) > 0) {
         if (lcp->requested_by_monitor_command)
            VG_(umsg)("To see details of leaked memory, give 'full' arg to leak_check\n");
         else
            VG_(umsg)("Rerun with --leak-check=full to see details "
                      "of leaked memory\n");
      }
      if (lcp->mode == LC_Full &&
          MC_(blocks_reachable) > 0 && !lcp->show_reachable)
      {
         VG_(umsg)("Reachable blocks (those to which a pointer "
                   "was found) are not shown.\n");
         if (lcp->requested_by_monitor_command)
            VG_(umsg)("To see them, add 'reachable any' args to leak_check\n");
         else
            VG_(umsg)("To see them, rerun with: --leak-check=full "
                      "--show-reachable=yes\n");
      }
      VG_(umsg)("\n");
   }
}

// print recursively all indirectly leaked blocks collected in clique.
static void print_clique (Int clique, UInt level)
{
   Int ind;
   Int i,  n_lossrecords;;

   n_lossrecords = VG_(OSetGen_Size)(lr_table);

   for (ind = 0; ind < lc_n_chunks; ind++) {
      LC_Extra*     ind_ex = &(lc_extras)[ind];
      if (ind_ex->state == IndirectLeak && ind_ex->IorC.clique == (SizeT) clique) {
         MC_Chunk*    ind_ch = lc_chunks[ind];
         LossRecord*  ind_lr;
         LossRecordKey ind_lrkey;
         Int lr_i;
         ind_lrkey.state = ind_ex->state;
         ind_lrkey.allocated_at = ind_ch->where;
         ind_lr = VG_(OSetGen_Lookup)(lr_table, &ind_lrkey);
         for (lr_i = 0; lr_i < n_lossrecords; lr_i++)
            if (ind_lr == lr_array[lr_i])
               break;
         for (i = 0; i < level; i++)
            VG_(umsg)("  ");
         VG_(umsg)("%p[%lu] indirect loss record %d\n",
                   (void *)ind_ch->data, (unsigned long)ind_ch->szB,
                   lr_i+1); // lr_i+1 for user numbering.
         if (lr_i >= n_lossrecords)
            VG_(umsg)
               ("error: no indirect loss record found for %p[%lu]?????\n",
                (void *)ind_ch->data, (unsigned long)ind_ch->szB);
         print_clique(ind, level+1);
      }
   }
 }

Bool MC_(print_block_list) ( UInt loss_record_nr)
{
   Int          i,  n_lossrecords;
   LossRecord*  lr;

   if (lr_table == NULL || lc_chunks == NULL || lc_extras == NULL) {
      VG_(umsg)("Can't print block list : no valid leak search result\n");
      return False;
   }

   if (lc_chunks_n_frees_marker != MC_(get_cmalloc_n_frees)()) {
      VG_(umsg)("Can't print obsolete block list : redo a leak search first\n");
      return False;
   }

   n_lossrecords = VG_(OSetGen_Size)(lr_table);
   if (loss_record_nr >= n_lossrecords)
      return False; // Invalid loss record nr.

   tl_assert (lr_array);
   lr = lr_array[loss_record_nr];
   
   // (re-)print the loss record details.
   // (+1 on loss_record_nr as user numbering for loss records starts at 1).
   MC_(pp_LossRecord)(loss_record_nr+1, n_lossrecords, lr);

   // Match the chunks with loss records.
   for (i = 0; i < lc_n_chunks; i++) {
      MC_Chunk*     ch = lc_chunks[i];
      LC_Extra*     ex = &(lc_extras)[i];
      LossRecord*   old_lr;
      LossRecordKey lrkey;
      lrkey.state        = ex->state;
      lrkey.allocated_at = ch->where;

      old_lr = VG_(OSetGen_Lookup)(lr_table, &lrkey);
      if (old_lr) {
         // We found an existing loss record matching this chunk.
         // If this is the loss record we are looking for, then output the pointer.
         if (old_lr == lr_array[loss_record_nr]) {
            VG_(umsg)("%p[%lu]\n",
                      (void *)ch->data, (unsigned long) ch->szB);
            if (ex->state != Reachable) {
               // We can print the clique in all states, except Reachable.
               // In Unreached state, lc_chunk[i] is the clique leader.
               // In IndirectLeak, lc_chunk[i] might have been a clique leader
               // which was later collected in another clique.
               // For Possible, lc_chunk[i] might be the top of a clique
               // or an intermediate clique.
               print_clique(i, 1);
            }
         }
      } else {
         // No existing loss record matches this chunk ???
         VG_(umsg)("error: no loss record found for %p[%lu]?????\n",
                   (void *)ch->data, (unsigned long) ch->szB);
      }
   }
   return True;
}

// If searched = 0, scan memory root set, pushing onto the mark stack the blocks
// encountered.
// Otherwise (searched != 0), scan the memory root set searching for ptr pointing
// inside [searched, searched+szB[.
static void scan_memory_root_set(Addr searched, SizeT szB)
{
   Int   i;
   Int   n_seg_starts;
   Addr* seg_starts = VG_(get_segment_starts)( &n_seg_starts );

   tl_assert(seg_starts && n_seg_starts > 0);

   lc_scanned_szB = 0;

   // VG_(am_show_nsegments)( 0, "leakcheck");
   for (i = 0; i < n_seg_starts; i++) {
      SizeT seg_size;
      NSegment const* seg = VG_(am_find_nsegment)( seg_starts[i] );
      tl_assert(seg);

      if (seg->kind != SkFileC && seg->kind != SkAnonC) continue;
      if (!(seg->hasR && seg->hasW))                    continue;
      if (seg->isCH)                                    continue;

      // Don't poke around in device segments as this may cause
      // hangs.  Exclude /dev/zero just in case someone allocated
      // memory by explicitly mapping /dev/zero.
      if (seg->kind == SkFileC 
          && (VKI_S_ISCHR(seg->mode) || VKI_S_ISBLK(seg->mode))) {
         HChar* dev_name = VG_(am_get_filename)( (NSegment*)seg );
         if (dev_name && 0 == VG_(strcmp)(dev_name, "/dev/zero")) {
            // Don't skip /dev/zero.
         } else {
            // Skip this device mapping.
            continue;
         }
      }

      if (0)
         VG_(printf)("ACCEPT %2d  %#lx %#lx\n", i, seg->start, seg->end);

      // Scan the segment.  We use -1 for the clique number, because this
      // is a root-set.
      seg_size = seg->end - seg->start + 1;
      if (VG_(clo_verbosity) > 2) {
         VG_(message)(Vg_DebugMsg,
                      "  Scanning root segment: %#lx..%#lx (%lu)\n",
                      seg->start, seg->end, seg_size);
      }
      lc_scan_memory(seg->start, seg_size, /*is_prior_definite*/True,
                     /*clique*/-1, /*cur_clique*/-1,
                     searched, szB);
   }
   VG_(free)(seg_starts);
}

/*------------------------------------------------------------*/
/*--- Top-level entry point.                               ---*/
/*------------------------------------------------------------*/

void MC_(detect_memory_leaks) ( ThreadId tid, LeakCheckParams* lcp)
{
   Int i, j;
   
   tl_assert(lcp->mode != LC_Off);

   // Verify some assertions which are used in lc_scan_memory.
   tl_assert((VKI_PAGE_SIZE % sizeof(Addr)) == 0);
   tl_assert((SM_SIZE % sizeof(Addr)) == 0);
   // Above two assertions are critical, while below assertion
   // ensures that the optimisation in the loop is done in the
   // correct order : the loop checks for (big) SM chunk skipping
   // before checking for (smaller) page skipping.
   tl_assert((SM_SIZE % VKI_PAGE_SIZE) == 0);


   MC_(detect_memory_leaks_last_delta_mode) = lcp->deltamode;

   // Get the chunks, stop if there were none.
   if (lc_chunks) {
      VG_(free)(lc_chunks);
      lc_chunks = NULL;
   }
   lc_chunks = find_active_chunks(&lc_n_chunks);
   lc_chunks_n_frees_marker = MC_(get_cmalloc_n_frees)();
   if (lc_n_chunks == 0) {
      tl_assert(lc_chunks == NULL);
      if (lr_table != NULL) {
         // forget the previous recorded LossRecords as next leak search
         // can in any case just create new leaks.
         // Maybe it would be better to rather call print_result ?
         // (at least when leak decreases are requested)
         // This will then output all LossRecords with a size decreasing to 0
         VG_(OSetGen_Destroy) (lr_table);
         lr_table = NULL;
      }
      if (VG_(clo_verbosity) >= 1 && !VG_(clo_xml)) {
         VG_(umsg)("All heap blocks were freed -- no leaks are possible\n");
         VG_(umsg)("\n");
      }
      return;
   }

   // Sort the array so blocks are in ascending order in memory.
   VG_(ssort)(lc_chunks, lc_n_chunks, sizeof(VgHashNode*), compare_MC_Chunks);

   // Sanity check -- make sure they're in order.
   for (i = 0; i < lc_n_chunks-1; i++) {
      tl_assert( lc_chunks[i]->data <= lc_chunks[i+1]->data);
   }

   // Sanity check -- make sure they don't overlap.  The one exception is that
   // we allow a MALLOCLIKE block to sit entirely within a malloc() block.
   // This is for bug 100628.  If this occurs, we ignore the malloc() block
   // for leak-checking purposes.  This is a hack and probably should be done
   // better, but at least it's consistent with mempools (which are treated
   // like this in find_active_chunks).  Mempools have a separate VgHashTable
   // for mempool chunks, but if custom-allocated blocks are put in a separate
   // table from normal heap blocks it makes free-mismatch checking more
   // difficult.
   //
   // If this check fails, it probably means that the application
   // has done something stupid with VALGRIND_MALLOCLIKE_BLOCK client
   // requests, eg. has made overlapping requests (which are
   // nonsensical), or used VALGRIND_MALLOCLIKE_BLOCK for stack locations;
   // again nonsensical.
   //
   for (i = 0; i < lc_n_chunks-1; i++) {
      MC_Chunk* ch1 = lc_chunks[i];
      MC_Chunk* ch2 = lc_chunks[i+1];

      Addr start1    = ch1->data;
      Addr start2    = ch2->data;
      Addr end1      = ch1->data + ch1->szB - 1;
      Addr end2      = ch2->data + ch2->szB - 1;
      Bool isCustom1 = ch1->allockind == MC_AllocCustom;
      Bool isCustom2 = ch2->allockind == MC_AllocCustom;

      if (end1 < start2) {
         // Normal case - no overlap.

      // We used to allow exact duplicates, I'm not sure why.  --njn
      //} else if (start1 == start2 && end1 == end2) {
         // Degenerate case: exact duplicates.

      } else if (start1 >= start2 && end1 <= end2 && isCustom1 && !isCustom2) {
         // Block i is MALLOCLIKE and entirely within block i+1.
         // Remove block i+1.
         for (j = i+1; j < lc_n_chunks-1; j++) {
            lc_chunks[j] = lc_chunks[j+1];
         }
         lc_n_chunks--;

      } else if (start2 >= start1 && end2 <= end1 && isCustom2 && !isCustom1) {
         // Block i+1 is MALLOCLIKE and entirely within block i.
         // Remove block i.
         for (j = i; j < lc_n_chunks-1; j++) {
            lc_chunks[j] = lc_chunks[j+1];
         }
         lc_n_chunks--;

      } else {
         VG_(umsg)("Block 0x%lx..0x%lx overlaps with block 0x%lx..0x%lx\n",
                   start1, end1, start2, end2);
         VG_(umsg)("Blocks allocation contexts:\n"),
         VG_(pp_ExeContext)( ch1->where);
         VG_(umsg)("\n"),
         VG_(pp_ExeContext)( ch2->where);
         VG_(umsg)("This is usually caused by using VALGRIND_MALLOCLIKE_BLOCK");
         VG_(umsg)("in an inappropriate way.\n");
         tl_assert (0);
      }
   }

   // Initialise lc_extras.
   if (lc_extras) {
      VG_(free)(lc_extras);
      lc_extras = NULL;
   }
   lc_extras = VG_(malloc)( "mc.dml.2", lc_n_chunks * sizeof(LC_Extra) );
   for (i = 0; i < lc_n_chunks; i++) {
      lc_extras[i].state        = Unreached;
      lc_extras[i].pending      = False;
      lc_extras[i].IorC.indirect_szB = 0;
   }

   // Initialise lc_markstack.
   lc_markstack = VG_(malloc)( "mc.dml.2", lc_n_chunks * sizeof(Int) );
   for (i = 0; i < lc_n_chunks; i++) {
      lc_markstack[i] = -1;
   }
   lc_markstack_top = -1;

   // Verbosity.
   if (VG_(clo_verbosity) > 1 && !VG_(clo_xml)) {
      VG_(umsg)( "Searching for pointers to %'d not-freed blocks\n",
                 lc_n_chunks );
   }

   // Scan the memory root-set, pushing onto the mark stack any blocks
   // pointed to.
   scan_memory_root_set(/*searched*/0, 0);

   // Scan GP registers for chunk pointers.
   VG_(apply_to_GP_regs)(lc_push_if_a_chunk_ptr_register);

   // Process the pushed blocks.  After this, every block that is reachable
   // from the root-set has been traced.
   lc_process_markstack(/*clique*/-1);

   if (VG_(clo_verbosity) > 1 && !VG_(clo_xml)) {
      VG_(umsg)("Checked %'lu bytes\n", lc_scanned_szB);
      VG_(umsg)( "\n" );
   }

   // Trace all the leaked blocks to determine which are directly leaked and
   // which are indirectly leaked.  For each Unreached block, push it onto
   // the mark stack, and find all the as-yet-Unreached blocks reachable
   // from it.  These form a clique and are marked IndirectLeak, and their
   // size is added to the clique leader's indirect size.  If one of the
   // found blocks was itself a clique leader (from a previous clique), then
   // the cliques are merged.
   for (i = 0; i < lc_n_chunks; i++) {
      MC_Chunk* ch = lc_chunks[i];
      LC_Extra* ex = &(lc_extras[i]);

      if (VG_DEBUG_CLIQUE)
         VG_(printf)("cliques: %d at %#lx -> Loss state %d\n",
                     i, ch->data, ex->state);

      tl_assert(lc_markstack_top == -1);

      if (ex->state == Unreached) {
         if (VG_DEBUG_CLIQUE)
            VG_(printf)("%d: gathering clique %#lx\n", i, ch->data);
         
         // Push this Unreached block onto the stack and process it.
         lc_push(i, ch);
         lc_process_markstack(/*clique*/i);

         tl_assert(lc_markstack_top == -1);
         tl_assert(ex->state == Unreached);
      }
   }
      
   print_results( tid, lcp);

   VG_(free) ( lc_markstack );
   lc_markstack = NULL;
   // lc_chunks, lc_extras, lr_array and lr_table are kept (needed if user
   // calls MC_(print_block_list)). lr_table also used for delta leak reporting
   // between this leak search and the next leak search.
}

static Addr searched_wpa;
static SizeT searched_szB;
static void
search_address_in_GP_reg(ThreadId tid, HChar* regname, Addr addr_in_reg)
{
   if (addr_in_reg >= searched_wpa 
       && addr_in_reg < searched_wpa + searched_szB) {
      if (addr_in_reg == searched_wpa)
         VG_(umsg)
            ("tid %d register %s pointing at %#lx\n",
             tid, regname, searched_wpa);  
      else
         VG_(umsg)
            ("tid %d register %s interior pointing %lu bytes inside %#lx\n",
             tid, regname, (long unsigned) addr_in_reg - searched_wpa,
             searched_wpa);
   }
}

void MC_(who_points_at) ( Addr address, SizeT szB)
{
   MC_Chunk** chunks;
   Int        n_chunks;
   Int        i;

   if (szB == 1)
      VG_(umsg) ("Searching for pointers to %#lx\n", address);
   else
      VG_(umsg) ("Searching for pointers pointing in %lu bytes from %#lx\n",
                 szB, address);

   // Scan memory root-set, searching for ptr pointing in address[szB]
   scan_memory_root_set(address, szB);

   // Scan active malloc-ed chunks
   chunks = find_active_chunks(&n_chunks);
   for (i = 0; i < n_chunks; i++) {
      lc_scan_memory(chunks[i]->data, chunks[i]->szB,
                     /*is_prior_definite*/True,
                     /*clique*/-1, /*cur_clique*/-1,
                     address, szB);
   }
   VG_(free) ( chunks );

   // Scan GP registers for pointers to address range.
   searched_wpa = address;
   searched_szB = szB;
   VG_(apply_to_GP_regs)(search_address_in_GP_reg);

}

/*--------------------------------------------------------------------*/
/*--- end                                                          ---*/
/*--------------------------------------------------------------------*/