/*--------------------------------------------------------------------*/
/*--- Memory-related stuff: segment initialisation and tracking,   ---*/
/*--- stack operations                                             ---*/
/*---                                                  vg_memory.c ---*/
/*--------------------------------------------------------------------*/

/*
   This file is part of Valgrind, an extensible x86 protected-mode
   emulator for monitoring program execution on x86-Unixes.

   Copyright (C) 2000-2005 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 "core.h"

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

static const Bool mem_debug = False;

static Char *straddr(void *p)
{
   static Char buf[16];

   VG_(sprintf)(buf, "%p", *(Addr *)p);

   return buf;
}

static SkipList sk_segments = SKIPLIST_INIT(Segment, addr, VG_(cmp_Addr), straddr, VG_AR_CORE);

/*--------------------------------------------------------------*/
/*--- Maintain an ordered list of all the client's mappings  ---*/
/*--------------------------------------------------------------*/

Bool VG_(seg_contains)(const Segment *s, Addr p, SizeT len)
{
   Addr se = s->addr+s->len;
   Addr pe = p+len;

   vg_assert(pe >= p);

   return (p >= s->addr && pe <= se);
}

Bool VG_(seg_overlaps)(const Segment *s, Addr p, SizeT len)
{
   Addr se = s->addr+s->len;
   Addr pe = p+len;

   if (pe < p)
      return False;		/* wrapped */

   return (p < se && pe > s->addr);
}

/* Prepare a Segment structure for recycling by freeing everything
   hanging off it. */
static void recycleseg(Segment *s)
{
   if (s->flags & SF_CODE)
      VG_(invalidate_translations)(s->addr, s->len, False);

   if (s->filename != NULL)
      VG_(arena_free)(VG_AR_CORE, (Char *)s->filename);

   /* keep the SegInfo, if any - it probably still applies */
}

/* When freeing a Segment, also clean up every one else's ideas of
   what was going on in that range of memory */
static void freeseg(Segment *s)
{
   recycleseg(s);
   if (s->symtab != NULL) {
      VG_(symtab_decref)(s->symtab, s->addr);
      s->symtab = NULL;
   }

   VG_(SkipNode_Free)(&sk_segments, s);
}

static inline Segment *allocseg()
{
   Segment *s;

   s = VG_(SkipNode_Alloc)(&sk_segments);

   return s;
}

/* Split a segment at address a, returning the new segment */
Segment *VG_(split_segment)(Addr a)
{
   Segment *s = VG_(SkipList_Find_Before)(&sk_segments, &a);
   Segment *ns;
   Int delta;

   vg_assert((a & (VKI_PAGE_SIZE-1)) == 0);

   /* missed */
   if (s == NULL)
      return NULL;

   /* a at or beyond endpoint */
   if (s->addr == a || a >= (s->addr+s->len))
      return NULL;

   vg_assert(a > s->addr && a < (s->addr+s->len));

   ns = allocseg();

   *ns = *s;

   delta = a - s->addr;
   ns->addr += delta;
   ns->offset += delta;
   ns->len -= delta;
   s->len = delta;

   vg_assert(ns->len > 0);
   vg_assert(s->len > 0);
   vg_assert(ns->addr == (s->addr+s->len));

   if (s->filename != NULL)
      ns->filename = VG_(arena_strdup)(VG_AR_CORE, s->filename);

   if (ns->symtab != NULL)
      VG_(symtab_incref)(ns->symtab);

   VG_(SkipList_Insert)(&sk_segments, ns);

   return ns;
}

/* This unmaps all the segments in the range [addr, addr+len); any
   partial mappings at the ends are truncated. */
void VG_(unmap_range)(Addr addr, SizeT len)
{
   Segment *s;
   Segment *next;
   static const Bool debug = False || mem_debug;
   Addr end;

   if (len == 0)
      return;

   len = PGROUNDUP(len);
   vg_assert(addr == PGROUNDDN(addr));

   if (debug)
      VG_(printf)("unmap_range(%p, %d)\n", addr, len);

   end = addr+len;

   /* Everything must be page-aligned */
   vg_assert((addr & (VKI_PAGE_SIZE-1)) == 0);
   vg_assert((len  & (VKI_PAGE_SIZE-1)) == 0);

   /* For each segment in the range covered by the unmap... */
   for(s = VG_(SkipList_Find_Before)(&sk_segments, &addr); 
       s != NULL && s->addr < (addr+len); 
       s = next) {
      Addr seg_end = s->addr + s->len;

      /* fetch next now in case we end up deleting this segment */
      next = VG_(SkipNode_Next)(&sk_segments, s);

      if (debug)
	 VG_(printf)("unmap: addr=%p-%p s=%p ->addr=%p-%p len=%d\n",
		     addr, end, s, s->addr, seg_end, s->len);

      if (!VG_(seg_overlaps)(s, addr, len)) {
	 if (debug)
	    VG_(printf)("   (no overlap)\n");
	 continue;
      }

      /* 4 cases: */
      if (addr > s->addr &&
	  addr < seg_end &&
	  end >= seg_end) {
	 /* this segment's tail is truncated by [addr, addr+len)
	    -> truncate tail
	 */
	 s->len = addr - s->addr;

	 vg_assert(s->len > 0);

	 if (debug)
	    VG_(printf)("  case 1: s->len=%d\n", s->len);
      } else if (addr <= s->addr && end > s->addr && end < seg_end) {
	 /* this segment's head is truncated by [addr, addr+len)
	    -> truncate head
	 */
	 UInt delta = end - s->addr;

	 if (debug)
	    VG_(printf)("  case 2: s->addr=%p s->len=%d delta=%d\n", s->addr, s->len, delta);

	 s->addr += delta;
	 s->offset += delta;
	 s->len -= delta;

	 vg_assert(s->len > 0);
      } else if (addr <= s->addr && end >= seg_end) {
	 /* this segment is completely contained within [addr, addr+len)
	    -> delete segment
	 */
	 Segment *rs = VG_(SkipList_Remove)(&sk_segments, &s->addr);
	 vg_assert(rs == s);
	 freeseg(s);

	 if (debug)
	    VG_(printf)("  case 3: s==%p deleted\n", s);
      } else if (addr > s->addr && end < seg_end) {
	 /* [addr, addr+len) is contained within a single segment
	    -> split segment into 3, delete middle portion
	  */
	 Segment *middle, *rs;

	 middle = VG_(split_segment)(addr);
	 VG_(split_segment)(addr+len);

	 vg_assert(middle->addr == addr);	 
	 vg_assert(middle->len == len);
	 rs = VG_(SkipList_Remove)(&sk_segments, &addr);
	 vg_assert(rs == middle);

	 freeseg(rs);

	 if (debug)
	    VG_(printf)("  case 4: subrange %p-%p deleted\n",
			addr, addr+len);
      }
   }

   //VG_(sanity_check_memory)();
}

/* Return true if two segments are adjacent and mergable (s1 is
   assumed to have a lower ->addr than s2) */
static inline Bool neighbours(Segment *s1, Segment *s2)
{
   if (s1->addr+s1->len != s2->addr)
      return False;

   if (s1->flags != s2->flags)
      return False;

   if (s1->prot != s2->prot)
      return False;

   if (s1->symtab != s2->symtab)
      return False;

   if (s1->flags & SF_FILE){
      if ((s1->offset + s1->len) != s2->offset)
	 return False;
      if (s1->dev != s2->dev)
	 return False;
      if (s1->ino != s2->ino)
	 return False;
   }
   
   return True;
}

/* If possible, merge segment with its neighbours - some segments,
   including s, may be destroyed in the process */
static void merge_segments(Addr a, SizeT len)
{
   Segment *s;
   Segment *next;

   vg_assert((a   & (VKI_PAGE_SIZE-1)) == 0);
   vg_assert((len & (VKI_PAGE_SIZE-1)) == 0);

   a   -= VKI_PAGE_SIZE;
   len += VKI_PAGE_SIZE;

   for(s = VG_(SkipList_Find_Before)(&sk_segments, &a);
       s != NULL && s->addr < (a+len);) {
      next = VG_(SkipNode_Next)(&sk_segments, s);

      if (next && neighbours(s, next)) {
	 Segment *rs;

	 if (0)
	    VG_(printf)("merge %p-%p with %p-%p\n",
			s->addr, s->addr+s->len,
			next->addr, next->addr+next->len);
	 s->len += next->len;
	 s = VG_(SkipNode_Next)(&sk_segments, next);

	 rs = VG_(SkipList_Remove)(&sk_segments, &next->addr);
	 vg_assert(next == rs);
	 freeseg(next);
      } else
	 s = next;
   }
}

void VG_(map_file_segment)(Addr addr, SizeT len, UInt prot, UInt flags, 
			   UInt dev, UInt ino, ULong off, const Char *filename)
{
   Segment *s;
   static const Bool debug = False || mem_debug;
   Bool recycled;

   if (debug)
      VG_(printf)("map_file_segment(%p, %llu, %x, %x, %4x, %d, %ld, %s)\n",
		  addr, (ULong)len, prot, flags, dev, ino, off, filename);

   if (len == 0)
      return;

   /* Everything must be page-aligned */
   vg_assert((addr & (VKI_PAGE_SIZE-1)) == 0);
   len = PGROUNDUP(len);

   /* First look to see what already exists around here */
   s = VG_(find_segment_containing)(addr);

   if (s != NULL && s->addr == addr && s->len == len) {
      recycled = True;
      recycleseg(s);

      /* If we had a symtab, but the new mapping is incompatible, then
	 free up the old symtab in preparation for a new one. */
      if (s->symtab != NULL		&&
	  (!(s->flags & SF_FILE)	||
	   !(flags & SF_FILE)		||
	   s->dev != dev		||
	   s->ino != ino		||
	   s->offset != off)) {
	 VG_(symtab_decref)(s->symtab, s->addr);
	 s->symtab = NULL;
      }
   } else {
      recycled = False;
      VG_(unmap_range)(addr, len);

      s = allocseg();

      s->addr   = addr;
      s->len    = len;
      s->symtab = NULL;
   }

   s->flags  = flags;
   s->prot   = prot;
   s->dev    = dev;
   s->ino    = ino;
   s->offset = off;
   
   if (filename != NULL)
      s->filename = VG_(arena_strdup)(VG_AR_CORE, filename);
   else
      s->filename = NULL;

   if (debug) {
      Segment *ts;
      for(ts = VG_(SkipNode_First)(&sk_segments);
	  ts != NULL;
	  ts = VG_(SkipNode_Next)(&sk_segments, ts))
	 VG_(printf)("list: %8p->%8p ->%d (0x%x) prot=%x flags=%x\n",
		     ts, ts->addr, ts->len, ts->len, ts->prot, ts->flags);

      VG_(printf)("inserting s=%p addr=%p len=%d\n",
		  s, s->addr, s->len);
   }

   if (!recycled)
      VG_(SkipList_Insert)(&sk_segments, s);

   /* If this mapping is of the beginning of a file, isn't part of
      Valgrind, is at least readable and seems to contain an object
      file, then try reading symbols from it. */
   if ((flags & (SF_MMAP|SF_NOSYMS)) == SF_MMAP	&&
       s->symtab == NULL) {
      if (off == 0									&&
	  filename != NULL								&&
	  (prot & (VKI_PROT_READ|VKI_PROT_EXEC)) == (VKI_PROT_READ|VKI_PROT_EXEC)	&&
	  len >= VKI_PAGE_SIZE							&&
	  s->symtab == NULL								&&
	  VG_(is_object_file)((void *)addr)) 
      {
         s->symtab = VG_(read_seg_symbols)(s);

         if (s->symtab != NULL) {
            s->flags |= SF_DYNLIB;
         }
      } else if (flags & SF_MMAP) {
	 const SegInfo *info;

	 /* Otherwise see if an existing symtab applies to this Segment */
	 for(info = VG_(next_seginfo)(NULL);
	     info != NULL;
	     info = VG_(next_seginfo)(info)) {
	    if (VG_(seg_overlaps)(s, VG_(seg_start)(info), VG_(seg_size)(info)))
            {
	       s->symtab = (SegInfo *)info;
	       VG_(symtab_incref)((SegInfo *)info);
	    }
	 }
      }
   }

   /* Don't merge for now.  The problem is that if we over-merge (we
      merge segments, but the kernel didn't merge the corresponding
      mappings), it confuses the sanity-checking machinery.
      Under-merging (the kernel merges but we don't) is not a problem.
      FIXME: stack growth probably creates lots of mergable segments;
      maybe there should be a separate segment-extending call. */
   if (0)
      merge_segments(addr, len);
}

void VG_(map_fd_segment)(Addr addr, SizeT len, UInt prot, UInt flags, 
			 Int fd, ULong off, const Char *filename)
{
   struct vki_stat st;
   Char *name = NULL;

   st.st_dev = 0;
   st.st_ino = 0;

   if (fd != -1 && (flags & SF_FILE)) {
      vg_assert((off & (VKI_PAGE_SIZE-1)) == 0);

      if (VG_(fstat)(fd, &st) < 0)
	 flags &= ~SF_FILE;
      else {
	 if (VKI_S_ISCHR(st.st_mode) || VKI_S_ISBLK(st.st_mode))
	    flags |= SF_DEVICE;
      }
   }

   if ((flags & SF_FILE) && filename == NULL && fd != -1)
      name = VG_(resolve_filename)(fd);

   if (filename == NULL)
      filename = name;

   VG_(map_file_segment)(addr, len, prot, flags, st.st_dev, st.st_ino, off, filename);

   if (name)
      VG_(arena_free)(VG_AR_CORE, name);
}

void VG_(map_segment)(Addr addr, SizeT len, UInt prot, UInt flags)
{
   flags &= ~SF_FILE;

   VG_(map_file_segment)(addr, len, prot, flags, 0, 0, 0, 0);
}

/* set new protection flags on an address range */
void VG_(mprotect_range)(Addr a, SizeT len, UInt prot)
{
   Segment *s, *next;
   static const Bool debug = False || mem_debug;
   Segment *s1, *s2;

   if (debug)
      VG_(printf)("mprotect_range(%p, %d, %x)\n", a, len, prot);

   if (len == 0)
      return;

   /* Everything must be page-aligned */
   vg_assert((a & (VKI_PAGE_SIZE-1)) == 0);
   len = PGROUNDUP(len);

   s1 = VG_(split_segment)(a);
   s2 = VG_(split_segment)(a+len);

   if (debug) {
      s = VG_(find_segment_before)(a);
      VG_(printf)("  split: s1=%p-%p s2=%p-%p s(%p)=%p-%p\n",
		  s1 ? s1->addr : 0, s1 ? (s1->addr+s1->len) : 0,
		  s2 ? s2->addr : 0, s2 ? (s2->addr+s2->len) : 0,
		  a,
		  s ? s->addr : 0, s ? (s->addr+s->len) : 0);
   }

   for(s = VG_(find_segment_before)(a);
       s != NULL && s->addr < a+len;
       s = next)
   {
      next = VG_(next_segment)(s);
      if (s->addr < a)
	 continue;

      if (debug)
	 VG_(printf)("  setting s->%p - %p to prot %x\n",
		     s->addr, s->addr+s->len, prot);

      s->prot = prot;
   }

   //merge_segments(a, len);
}

Addr VG_(find_map_space)(Addr addr, SizeT len, Bool for_client)
{
   static const Bool debug = False || mem_debug;
   Segment *s;
   Addr ret;
   Addr limit = (for_client ? VG_(client_end)-1   : VG_(valgrind_last));
   Addr base  = (for_client ? VG_(client_mapbase) : VG_(valgrind_base));

   if (addr == 0)
      addr = base;
   else {
      /* leave space for redzone and still try to get the exact
	 address asked for */
      addr = PGROUNDDN(addr) - VKI_PAGE_SIZE;
   }
   ret = addr;

   /* Everything must be page-aligned */
   vg_assert((addr & (VKI_PAGE_SIZE-1)) == 0);
   len = PGROUNDUP(len);

   len += VKI_PAGE_SIZE * 2; /* leave redzone gaps before and after mapping */

   if (debug)
      VG_(printf)("find_map_space: ret starts as %p-%p client=%d\n",
		  ret, ret+len, for_client);

   s = VG_(SkipList_Find_Before)(&sk_segments, &ret);
   if (s == NULL)
      s = VG_(SkipNode_First)(&sk_segments);

   for( ;
       s != NULL && s->addr < (ret+len);
       s = VG_(SkipNode_Next)(&sk_segments, s))
   {
      if (debug)
	 VG_(printf)("s->addr=%p len=%d (%p) ret=%p\n",
		     s->addr, s->len, s->addr+s->len, ret);

      if (s->addr < (ret + len) && (s->addr + s->len) > ret)
	 ret = s->addr+s->len;
   }

   if (debug) {
      if (s)
	 VG_(printf)("  s->addr=%p ->len=%d\n", s->addr, s->len);
      else
	 VG_(printf)("  s == NULL\n");
   }

   if (((limit - len)+1) < ret)
      ret = 0;			/* no space */
   else
      ret += VKI_PAGE_SIZE; /* skip leading redzone */

   if (debug)
      VG_(printf)("find_map_space(%p, %d, %d) -> %p\n",
		  addr, len, for_client, ret);
   
   return ret;
}

/* Pad the entire process address space, from "start"
   to VG_(valgrind_last) by creating an anonymous and inaccessible
   mapping over any part of the address space which is not covered
   by an entry in the segment list.

   This is designed for use around system calls which allocate
   memory in the process address space without providing a way to
   control its location such as io_setup. By choosing a suitable
   address with VG_(find_map_space) and then adding a segment for
   it and padding the address space valgrind can ensure that the
   kernel has no choice but to put the memory where we want it. */
void VG_(pad_address_space)(Addr start)
{
   Addr addr = (start == 0) ? VG_(client_base) : start;
   Segment *s = VG_(find_segment_after)(addr);
   Addr ret;
   
   while (s && addr <= VG_(valgrind_last)) {
      if (addr < s->addr) {
         PLATFORM_DO_MMAP(ret, addr, s->addr - addr, 0,
                          VKI_MAP_FIXED | VKI_MAP_PRIVATE | 
			  VKI_MAP_ANONYMOUS | VKI_MAP_NORESERVE,
                          -1, 0);
      }
        
      addr = s->addr + s->len;
      s = VG_(next_segment)(s);
   }

   if (addr <= VG_(valgrind_last)) {
      PLATFORM_DO_MMAP(ret, addr, VG_(valgrind_last) - addr + 1, 0,
                       VKI_MAP_FIXED | VKI_MAP_PRIVATE | VKI_MAP_ANONYMOUS,
                       -1, 0);
   }

   return;
}

/* Remove the address space padding added by VG_(pad_address_space)
   by removing any mappings that it created. */
void VG_(unpad_address_space)(Addr start)
{
   Addr addr = (start == 0) ? VG_(client_base) : start;
   Segment *s = VG_(find_segment_after)(addr);
   Int ret;

   while (s && addr <= VG_(valgrind_last)) {
      if (addr < s->addr) {
         ret = VG_(do_syscall)(__NR_munmap, addr, s->addr - addr);
      }
         
      addr = s->addr + s->len;
      s = VG_(next_segment)(s);
   }

   if (addr <= VG_(valgrind_last)) {
      ret = VG_(do_syscall)(__NR_munmap, addr, (VG_(valgrind_last) - addr) + 1);
   }

   return;
}

Segment *VG_(find_segment_before)(Addr a)
{
   return VG_(SkipList_Find_Before)(&sk_segments, &a);
}

/* Return the segment starting at exactly address 'a' */
Segment *VG_(find_segment_containing)(Addr a)
{
   Segment *seg = VG_(find_segment_before)(a);

   if (seg && ((a < seg->addr) || (seg->addr + seg->len) <= a))
      seg = NULL;
   return seg;
}

/* Return the segment which either contains or is after 'a' */
Segment *VG_(find_segment_after)(Addr a)
{
   Segment *seg = VG_(find_segment_before)(a);

   if (seg == NULL) {
      // If there's nothing before the address, then the next segment
      // is the first
      seg = VG_(first_segment)();
   }

   while (seg && a >= (seg->addr+seg->len))
      seg = VG_(next_segment)(seg);

   return seg;
}

Segment *VG_(first_segment)(void)
{
   return VG_(SkipNode_First)(&sk_segments);
}

Segment *VG_(next_segment)(Segment *s)
{
   return VG_(SkipNode_Next)(&sk_segments, s);
}

/*------------------------------------------------------------*/
/*--- Tracking permissions around %esp changes.            ---*/
/*------------------------------------------------------------*/

/*
   The stack
   ~~~~~~~~~
   The stack's segment seems to be dynamically extended downwards
   by the kernel as the stack pointer moves down.  Initially, a
   1-page (4k) stack is allocated.  When %esp moves below that for
   the first time, presumably a page fault occurs.  The kernel
   detects that the faulting address is in the range from %esp upwards
   to the current valid stack.  It then extends the stack segment
   downwards for enough to cover the faulting address, and resumes
   the process (invisibly).  The process is unaware of any of this.

   That means that Valgrind can't spot when the stack segment is
   being extended.  Fortunately, we want to precisely and continuously
   update stack permissions around %esp, so we need to spot all
   writes to %esp anyway.

   The deal is: when %esp is assigned a lower value, the stack is
   being extended.  Create a secondary maps to fill in any holes
   between the old stack ptr and this one, if necessary.  Then 
   mark all bytes in the area just "uncovered" by this %esp change
   as write-only.

   When %esp goes back up, mark the area receded over as unreadable
   and unwritable.

   Just to record the %esp boundary conditions somewhere convenient:
   %esp always points to the lowest live byte in the stack.  All
   addresses below %esp are not live; those at and above it are.  
*/

/* Kludgey ... how much does %esp have to change before we reckon that
   the application is switching stacks ? */
#define VG_PLAUSIBLE_STACK_SIZE  8000000
#define VG_HUGE_DELTA            (VG_PLAUSIBLE_STACK_SIZE / 4)

/* This function gets called if new_mem_stack and/or die_mem_stack are
   tracked by the tool, and one of the specialised cases (eg. new_mem_stack_4)
   isn't used in preference */
REGPARM(1)
void VG_(unknown_SP_update)(Addr new_SP)
{
   ThreadState *tst = &VG_(threads)[VG_(get_running_tid)()];
   Addr old_SP = ARCH_STACK_PTR(tst->arch);
   Word delta  = (Word)new_SP - (Word)old_SP;

   if (delta < -(VG_HUGE_DELTA) || VG_HUGE_DELTA < delta) {
      /* %esp has changed by more than HUGE_DELTA.  We take this to mean
         that the application is switching to a new stack, for whatever
         reason. 
       
         JRS 20021001: following discussions with John Regehr, if a stack
         switch happens, it seems best not to mess at all with memory
         permissions.  Seems to work well with Netscape 4.X.  Really the
         only remaining difficulty is knowing exactly when a stack switch is
         happening. */
      if (VG_(clo_verbosity) > 1)
           VG_(message)(Vg_UserMsg, "Warning: client switching stacks?  "
                                    "%%esp: %p --> %p", old_SP, new_SP);
   } else if (delta < 0) {
      VG_TRACK( new_mem_stack, new_SP, -delta );

   } else if (delta > 0) {
      VG_TRACK( die_mem_stack, old_SP,  delta );
   }
}

/* 
   Test if a piece of memory is addressable with at least the "prot"
   protection permissions by examining the underlying segments.
 */
Bool VG_(is_addressable)(Addr p, SizeT size, UInt prot)
{
   Segment *seg;

   if ((p + size) < p)
      return False;

   for(seg = VG_(find_segment_containing)(p); 
       size > 0 &&
       seg &&
       VG_(seg_overlaps)(seg, p, size) &&
       (seg->prot & prot) == prot; 
       seg = VG_(next_segment)(seg)) {
      Addr end = p + size;
      Addr segend = seg->addr + seg->len;

      if (end <= segend)
	 size = 0;
      else {
	 size -= segend - p;
	 p = segend;
      }
   }

   return size == 0;
}

/*--------------------------------------------------------------------*/
/*--- Manage allocation of memory on behalf of the client          ---*/
/*--------------------------------------------------------------------*/

// Returns 0 on failure.
Addr VG_(client_alloc)(Addr addr, SizeT len, UInt prot, UInt sf_flags)
{
   len = PGROUNDUP(len);

   sk_assert(!(sf_flags & SF_FIXED));
   sk_assert(0 == addr);

   addr = (Addr)VG_(mmap)((void *)addr, len, prot, 
                          VKI_MAP_PRIVATE | VKI_MAP_ANONYMOUS | VKI_MAP_CLIENT,
                          sf_flags | SF_CORE, -1, 0);
   if ((Addr)-1 != addr)
      return addr;
   else
      return 0;
}

void VG_(client_free)(Addr addr)
{
   Segment *s = VG_(find_segment_containing)(addr);

   if (s == NULL || s->addr != addr || !(s->flags & SF_CORE)) {
      VG_(message)(Vg_DebugMsg, "VG_(client_free)(%p) - no CORE memory found there", addr);
      return;
   }

   VG_(munmap)((void *)s->addr, s->len);
}

/* We'll call any RW mmaped memory segment, within the client address
   range, which isn't SF_CORE, a root. */
void VG_(find_root_memory)(void (*add_rootrange)(Addr a, SizeT sz))
{
   Segment *s;

   for(s = VG_(first_segment)(); s != NULL; s = VG_(next_segment)(s)) {
      UInt flags = s->flags & (SF_SHARED|SF_MMAP|SF_VALGRIND|SF_CORE|SF_STACK|SF_DEVICE);
      if (flags != SF_MMAP && flags != SF_STACK)
	 continue;
      if ((s->prot & (VKI_PROT_READ|VKI_PROT_WRITE)) != (VKI_PROT_READ|VKI_PROT_WRITE))
	 continue;
      if (!VG_(is_client_addr)(s->addr) ||
	  !VG_(is_client_addr)(s->addr+s->len))
	 continue;

      (*add_rootrange)(s->addr, s->len);
   }
}

/*--------------------------------------------------------------------*/
/*--- Querying memory layout                                       ---*/
/*--------------------------------------------------------------------*/

Bool VG_(is_client_addr)(Addr a)
{
   return a >= VG_(client_base) && a < VG_(client_end);
}

Bool VG_(is_shadow_addr)(Addr a)
{
   return a >= VG_(shadow_base) && a < VG_(shadow_end);
}

Bool VG_(is_valgrind_addr)(Addr a)
{
   return a >= VG_(valgrind_base) && a <= VG_(valgrind_last);
}

Addr VG_(get_client_base)(void)
{
   return VG_(client_base);
}

Addr VG_(get_client_end)(void)
{
   return VG_(client_end);
}

Addr VG_(get_client_size)(void)
{
   return VG_(client_end)-VG_(client_base);
}

Addr VG_(get_shadow_base)(void)
{
   return VG_(shadow_base);
}

Addr VG_(get_shadow_end)(void)
{
   return VG_(shadow_end);
}

Addr VG_(get_shadow_size)(void)
{
   return VG_(shadow_end)-VG_(shadow_base);
}

/*--------------------------------------------------------------------*/
/*--- Handling shadow memory                                       ---*/
/*--------------------------------------------------------------------*/

void VG_(init_shadow_range)(Addr p, UInt sz, Bool call_init)
{
   if (0)
      VG_(printf)("init_shadow_range(%p, %d)\n", p, sz);

   vg_assert(VG_(needs).shadow_memory);
   vg_assert(VG_(defined_init_shadow_page)());

   sz = PGROUNDUP(p+sz) - PGROUNDDN(p);
   p = PGROUNDDN(p);

   VG_(mprotect)((void *)p, sz, VKI_PROT_READ|VKI_PROT_WRITE);
   
   if (call_init) 
      while(sz) {
	 /* ask the tool to initialize each page */
	 VG_TRACK( init_shadow_page, PGROUNDDN(p) );
	 
	 p  += VKI_PAGE_SIZE;
	 sz -= VKI_PAGE_SIZE;
      }
}

static Addr shadow_alloc = 0;
void *VG_(shadow_alloc)(UInt size)
{
   void *ret;

   vg_assert(VG_(needs).shadow_memory);
   vg_assert(!VG_(defined_init_shadow_page)());

   size = PGROUNDUP(size);

   if (shadow_alloc == 0) {
      shadow_alloc = VG_(shadow_base);
      vg_assert(VG_(is_addressable)(VG_(shadow_base), VG_(shadow_end)-VG_(shadow_base), 
				    VKI_PROT_NONE));
   }

   if (shadow_alloc >= VG_(shadow_end))
       return 0;

   if (0)
      VG_(printf)("shadow_base=%p shadow_alloc=%p alloc %d\n",
		  VG_(shadow_base), shadow_alloc, size);

   ret = (void *)shadow_alloc;
   VG_(mprotect)(ret, size, VKI_PROT_READ|VKI_PROT_WRITE);

   shadow_alloc += size;

   return ret;
}

void VG_(print_shadow_stats)()
{
   SizeT used = (shadow_alloc ? shadow_alloc : VG_(shadow_base)) - VG_(shadow_base);
   SizeT total = VG_(shadow_end) - VG_(shadow_base);

   VG_(message)(Vg_DebugMsg, "Total shadow reserved: %d Mbytes, %d Mbytes used (%d%%)",
		total / (1024*1024), used / (1024*1024), (UInt)(total ? (used * 100ull / total) : 0));
}

/*--------------------------------------------------------------------*/
/*--- Sync maps                                                    ---*/
/*--------------------------------------------------------------------*/

/* Search /proc/self/maps looking for changes which aren't reflected
   in the segment list */

static Segment *next_segment;
static UInt sync_maps_flags;

static void sync_maps(Addr addr, SizeT len, UInt prot,
		      UInt dev, UInt ino, ULong foff, const UChar *filename)
{
   static const Bool debug = 0;

   Addr end = addr+len;
   Segment *seg, *first, *last;   
   UInt flags = sync_maps_flags;

   flags |= (addr < VG_(client_end)) ? 0 : SF_VALGRIND;

   seg = next_segment;

   if (debug)
      VG_(printf)("SYNC: map %p-%p\n", addr, end);

   /* Traverse any segments which are before this mapping... */
   first = seg;
   while(seg && (seg->addr < addr))
      seg = VG_(next_segment)(seg);

   /* ...and remove them */
   if (first && first->addr < addr) {
      if (debug)
	 VG_(printf)("SYNC: removing %p-%p\n", first->addr, addr-first->addr);
      VG_(unmap_range)(first->addr, addr - first->addr);
      VG_TRACK( die_mem_munmap, first->addr, addr-first->addr );

      seg = VG_(find_segment_after)(addr);
   }

   if (seg == NULL || end <= seg->addr) {
      /* floating mapping with no segments */
      if (debug)
	 VG_(printf)("SYNC: inserting %p-%p %s\n", addr, end, VG_(prot_str)(prot));
      VG_(map_file_segment)(addr, len, prot, flags, dev, ino, foff, filename);

      VG_TRACK ( new_mem_mmap, addr, len, 
		 prot & VKI_PROT_READ, prot & VKI_PROT_WRITE, prot & VKI_PROT_EXEC );

      if (addr >= VG_(client_end) && VG_(clo_pointercheck)) {
	 VG_(message)(Vg_UserMsg, "Warning: inserted mapping at %p-%p, but it is",
		      addr, addr+len);
	 VG_(message)(Vg_UserMsg, "  inaccessible because pointer-checking is enabled "
		      "(expect a SIGSEGV)");
      }
   }

   /* traverse segments covering mapping */
   for(last = NULL; seg && seg->addr < end;
       last = seg, seg = VG_(next_segment)(seg)) {
      if (last && (last->addr+last->len) > addr && (last->addr+last->len) != seg->addr) {
	 /* gap fill */
	 if (debug)
	    VG_(printf)("SYNC: gap-fill %p-%p\n", last->addr+last->len, seg->addr);
	 VG_(map_file_segment)(last->addr+last->len, seg->addr - (last->addr+last->len),
			       prot, flags | SF_MMAP, dev, ino, foff, filename);
	 last = VG_(find_segment_containing)(last->addr+last->len);
      }
      seg->prot = prot;
   }

   next_segment = seg;
}

void VG_(sync_segments)(UInt flags)
{
   static const Bool debug = 0;
   Segment *seg;

   next_segment = VG_(first_segment)();

   sync_maps_flags = flags;

   VG_(parse_procselfmaps)(sync_maps);

   if (next_segment != NULL) {
      /* Found some segments after the end of the mappings */
      Addr first, last;
      
      first = next_segment->addr;
      last = next_segment->addr + next_segment->len;

      for(seg = next_segment; seg; seg = VG_(next_segment)(seg))
	 last = seg->addr + seg->len;

      if (debug)
	 VG_(printf)("SYNC: remove tail %p-%p\n", first, last);
      VG_(unmap_range)(first, last-first);
   }

   if (debug)
      VG_(sanity_check_memory)();
}

/*--------------------------------------------------------------------*/
/*--- Sanity checking                                              ---*/
/*--------------------------------------------------------------------*/

const Char *VG_(prot_str)(UInt prot)
{
   static const Char *str[] = {
      "---",
      "r--",
      "-w-",
      "rw-",
      "--x",
      "r-x",
      "-wx",
      "rwx",
   };

   vg_assert(VKI_PROT_READ  == 1);
   vg_assert(VKI_PROT_WRITE == 2);
   vg_assert(VKI_PROT_EXEC  == 4);

   return str[prot & 7];
}

static Bool segment_maps_ok;
static Addr prevmapstart, prevmapend;
static Bool check_verbose;

static void check_segment_maps(Addr addr, SizeT len, UInt prot,
			       UInt dev, UInt ino, ULong foff, const UChar *filename)
{
   const Bool debug = 0 || check_verbose;

   Addr segend;
   Addr end = addr+len;
   Segment *seg, *prev;

   if (addr >= VG_(valgrind_last))
      return;			/* don't care */

   if (addr < prevmapend) {
      VG_(printf)("KERNEL BUG: mapping %p-%p <= prevmap %p-%p !?\n",
		  addr, end, prevmapstart, prevmapend);
      return;
   }

   prevmapstart = addr;
   prevmapend = end;

   /* 
      The invariants here are:
      1. all mappings from /proc/self/maps must be completely covered by Segments
          - there may be multiple Segments per map
      2. a Segment may never overlap the ends of a map
      3. all Segments must be backed by mappings
      4. Segment permissions must not be a superset of mapping permissions (subset OK)

      The most important thing is that all the mappings are covered by
      Segments, since violating that invariant could cause new
      mappings to be put over existing mappings.

      Inv 4 is not so important, since the worst that could happen is
      that Valgrind may mis-report some information.  This can happen
      in practice because some device driver mmap functions create
      mappings with protections which don't match the requested
      protections.  It is therefore not considered a fatal error.
   */

   /* 
      Check invariant 3: this segment must have the same start address
      as the mapping.  If we find a floating Segment (ie, has no
      mapping backing it), then skip forward through list until we
      find a Segment which could overlap this mapping.

      And inv 2: if it doesn't start at the beginnging of the mapping,
      it should be some completely floating segment; it must not
      overlap the mapping.
   */

   seg = next_segment;

   if (seg == NULL) {
      VG_(printf)("INV 1 FAILED: no segment for mapping %p-%p\n",
		  addr, end);
      segment_maps_ok = False;
      return;
   }

   segend = seg->addr + seg->len;

   if (debug && 0)
      VG_(printf)("mapping %p-%p seg: %p-%p %s\n", addr, end, 
		  seg->addr, segend, seg->addr < addr ? "LT" : "");

   prev = NULL;

   /* Sync up - skip all the Segments which are between the previous
      mapping and this one (there should be none) */
   while (seg && (seg->addr < addr)) {
      VG_(printf)("INV 3 FAILED: seg %p-%p %4x doesn't start at beginning of mapping %p-%p\n",
		  seg->addr, segend, seg->flags, addr, end);
      if (VG_(seg_overlaps)(seg, addr, len))
	 VG_(printf)("    2 FAILED: seg %p-%p overlaps of mapping %p-%p\n",
		     seg->addr, segend, addr, end);
      segment_maps_ok = False;
      prev = seg;
      seg = VG_(next_segment)(seg);
   }

   if (seg == NULL)
      return;			/* no more segments */

   if (end <= seg->addr) {
      /* check if this mapping is floating before the segment */
      VG_(printf)("INV 1 FAILED: mapping %p-%p (prot=%s file=%s) is before %p-%p\n",
		  addr, end, VG_(prot_str)(prot), filename,
		  seg->addr, seg->addr+seg->len);
      segment_maps_ok = False;
   }

   /* Iterate over all Segments covering the mapping */
   for (; seg && (seg->addr < end); 
	prev = seg, seg = VG_(next_segment)(seg)) {
      segend = seg->addr + seg->len;

      if (prev && (prev->addr + prev->len) != seg->addr) {
	 VG_(printf)("INV 1 FAILED: prev segment %p-%p seg %p-%p doesn't cover map %p-%p\n",
		     prev->addr, prev->addr+prev->len, seg->addr, segend, addr, end);
	 segment_maps_ok = False;
	 break;
      }

      if (debug)
	 VG_(printf)("seg: %p-%p (%s) %4x  mapping %p-%p %s %s%s %s\n",
		     seg->addr, segend, 
		     VG_(prot_str)(seg->prot),
		     seg->flags,
		     addr, end, VG_(prot_str)(prot),
		     (addr == seg->addr && segend == end) ? "" : " !!!",
		     (seg->prot & prot) != seg->prot ? " ???" : "",
		     seg->filename ? seg->filename : (const Char *)"");

      vg_assert(VG_(seg_overlaps)(seg, addr, len));

      if ((seg->addr < addr) || (segend > end)) {
	 VG_(printf)("INV 2 FAILED: seg %p-%p crosses boundaries of mapping %p-%p\n",
		     seg->addr, segend,
		     addr, end);
	 segment_maps_ok = False;
      }

      if ((seg->prot & prot) != seg->prot) {
	 if (VG_(clo_verbosity) > 2)
	    VG_(printf)("INV 4 FAILED: seg %p-%p permissions %s not subset of mapping %p-%p permissions %s\n",
			seg->addr, segend,
			VG_(prot_str)(seg->prot),
			addr, end,
			VG_(prot_str)(prot));
	 seg->prot = prot;
      }

      if (filename != NULL) {
	 Int delta;

	 if (!(seg->flags & SF_FILE)) {
	    if (VG_(clo_verbosity) > 2)
	       VG_(printf)("seg %p-%p flags %x does't have SF_FILE\n",
			   seg->addr, segend, seg->flags);
	 }

	 delta = seg->addr - addr;
	 if ((seg->offset - delta) != foff) {
	    if (VG_(clo_verbosity) > 2)
	       VG_(printf)("seg %p-%p file %s delta %d offset %lld != (%p-%p) %lld %s\n",
			   seg->addr, segend, seg->filename, delta, seg->offset, 
			   addr, end, foff, filename);
	 }
      }
   }
   
   if (seg)
      segend = seg->addr + seg->len;

   if (debug && 0)
      VG_(printf)("loop done next-seg=%p-%p map=%p-%p\n",
		  seg ? seg->addr : 0, seg ? (seg->addr+seg->len) : 0,
		  addr, end);

   /* otherwise the loop exited too early */
   vg_assert(seg == NULL || seg->addr >= end);

   if (prev && (prev->addr+prev->len) != end) {
      VG_(printf)("INV 1 FAILED: seg -%p does not end at mapping %p-%p end\n",
		  prev->addr, prev->addr+prev->len, addr, end);
      segment_maps_ok = False;
   }

   next_segment = seg;
}

Bool VG_(sanity_check_memory)(void)
{
   Segment *seg;
   Addr prev;
   Bool ok = True;

   /* First, walk the segment list and make sure it looks internally OK */
   prev = 0;
   for(seg = VG_(first_segment)(); 
       seg != NULL; 
       seg = VG_(next_segment)(seg)) {
      Addr end = seg->addr + seg->len;

      if (end <= seg->addr) {
	 ok = False;
	 VG_(printf)("Segment %p: %p-%p has bad size %d\n",
		     seg, seg->addr, end, seg->len);
      }

      if (seg->addr < prev) {
	 ok = False;
	 VG_(printf)("Segment %p: %p-%p is before previous seg (ending at %p)\n",
		     seg, seg->addr, end, prev);
      }

      if (!!(seg->flags & SF_VALGRIND) != (seg->addr >= VG_(client_end))) {
	 ok = False;
	 VG_(printf)("Segment %p: %p-%p has flags (%x) inconsistent with client_end=%p\n",
		     seg, seg->addr, seg->addr+seg->len, seg->flags, VG_(client_end));
      }

      if (prev < end)
	 prev = end;
   }

   check_verbose = False;
   segment_maps_ok = True;
   next_segment = VG_(first_segment)();
   prevmapstart = prevmapend = 0;
   VG_(parse_procselfmaps)(check_segment_maps);

   while(next_segment) {
      VG_(printf)("INV 3 FAILED: floating segment %p-%p without backing mapping\n",
		  next_segment->addr, next_segment->addr + next_segment->len);
      next_segment = VG_(next_segment)(next_segment);
      segment_maps_ok = False;
   }

   if (!segment_maps_ok) {
      VG_(printf)("\n\nvvvvv SEGMENT MAPS NOT OK vvvvv\n");
      check_verbose = True;
      next_segment = VG_(first_segment)();
      prevmapstart = prevmapend = 0;
      VG_(parse_procselfmaps)(check_segment_maps);
      VG_(printf)("^^^^^ SEGMENT MAPS NOT OK ^^^^^\n\n");
   }

   ok = ok && segment_maps_ok;

   if (0) {
      if (ok)
	 VG_(printf)("(memory segments OK)\n");
      else
	 VG_(printf)("(problem)\n");
   }
   return ok;
}

/*--------------------------------------------------------------------*/
/*--- end                                              vg_memory.c ---*/
/*--------------------------------------------------------------------*/