|
From: <sv...@va...> - 2008-08-19 11:20:28
|
Author: sewardj
Date: 2008-08-19 12:20:35 +0100 (Tue, 19 Aug 2008)
New Revision: 8528
Log:
Add the SGcheck tool; now reasonably robust, but can be very slow.
Added:
branches/SGCHECK/exp-sgcheck/
branches/SGCHECK/exp-sgcheck/Makefile.am
branches/SGCHECK/exp-sgcheck/docs/
branches/SGCHECK/exp-sgcheck/docs/Makefile.am
branches/SGCHECK/exp-sgcheck/sg_intercepts.c
branches/SGCHECK/exp-sgcheck/sg_main.c
branches/SGCHECK/exp-sgcheck/tests/
branches/SGCHECK/exp-sgcheck/tests/Makefile.am
Added: branches/SGCHECK/exp-sgcheck/Makefile.am
===================================================================
--- branches/SGCHECK/exp-sgcheck/Makefile.am (rev 0)
+++ branches/SGCHECK/exp-sgcheck/Makefile.am 2008-08-19 11:20:35 UTC (rev 8528)
@@ -0,0 +1,124 @@
+include $(top_srcdir)/Makefile.tool.am
+
+noinst_PROGRAMS =
+if VGP_X86_LINUX
+noinst_PROGRAMS += exp-sgcheck-x86-linux vgpreload_exp-sgcheck-x86-linux.so
+endif
+if VGP_AMD64_LINUX
+noinst_PROGRAMS += exp-sgcheck-amd64-linux vgpreload_exp-sgcheck-amd64-linux.so
+endif
+if VGP_PPC32_LINUX
+noinst_PROGRAMS += exp-sgcheck-ppc32-linux vgpreload_exp-sgcheck-ppc32-linux.so
+endif
+if VGP_PPC64_LINUX
+noinst_PROGRAMS += exp-sgcheck-ppc64-linux vgpreload_exp-sgcheck-ppc64-linux.so
+endif
+if VGP_PPC32_AIX5
+noinst_PROGRAMS += exp-sgcheck-ppc32-aix5 vgpreload_exp-sgcheck-ppc32-aix5.so
+endif
+if VGP_PPC64_AIX5
+noinst_PROGRAMS += exp-sgcheck-ppc64-aix5 vgpreload_exp-sgcheck-ppc64-aix5.so
+endif
+
+
+VGPRELOAD_EXP_SGCHECK_SOURCES_COMMON = sg_intercepts.c
+
+vgpreload_exp_sgcheck_x86_linux_so_SOURCES = $(VGPRELOAD_EXP_SGCHECK_SOURCES_COMMON)
+vgpreload_exp_sgcheck_x86_linux_so_CPPFLAGS = $(AM_CPPFLAGS_X86_LINUX)
+vgpreload_exp_sgcheck_x86_linux_so_CFLAGS = $(AM_CFLAGS_X86_LINUX) $(AM_CFLAGS_PIC) -O2
+vgpreload_exp_sgcheck_x86_linux_so_CCASFLAGS = $(AM_CCASFLAGS_X86_LINUX)
+vgpreload_exp_sgcheck_x86_linux_so_DEPENDENCIES = $(LIBREPLACEMALLOC_X86_LINUX)
+vgpreload_exp_sgcheck_x86_linux_so_LDFLAGS = \
+ $(PRELOAD_LDFLAGS_X86_LINUX) \
+ $(LIBREPLACEMALLOC_LDFLAGS_X86_LINUX)
+
+vgpreload_exp_sgcheck_amd64_linux_so_SOURCES = $(VGPRELOAD_EXP_SGCHECK_SOURCES_COMMON)
+vgpreload_exp_sgcheck_amd64_linux_so_CPPFLAGS = $(AM_CPPFLAGS_AMD64_LINUX)
+vgpreload_exp_sgcheck_amd64_linux_so_CFLAGS = $(AM_CFLAGS_AMD64_LINUX) $(AM_CFLAGS_PIC) -O2
+vgpreload_exp_sgcheck_amd64_linux_so_CCASFLAGS = $(AM_CCASFLAGS_AMD64_LINUX)
+vgpreload_exp_sgcheck_amd64_linux_so_DEPENDENCIES = $(LIBREPLACEMALLOC_AMD64_LINUX)
+vgpreload_exp_sgcheck_amd64_linux_so_LDFLAGS = \
+ $(PRELOAD_LDFLAGS_AMD64_LINUX) \
+ $(LIBREPLACEMALLOC_LDFLAGS_AMD64_LINUX)
+
+vgpreload_exp_sgcheck_ppc32_linux_so_SOURCES = $(VGPRELOAD_EXP_SGCHECK_SOURCES_COMMON)
+vgpreload_exp_sgcheck_ppc32_linux_so_CPPFLAGS = $(AM_CPPFLAGS_PPC32_LINUX)
+vgpreload_exp_sgcheck_ppc32_linux_so_CFLAGS = $(AM_CFLAGS_PPC32_LINUX) $(AM_CFLAGS_PIC) -O2
+vgpreload_exp_sgcheck_ppc32_linux_so_CCASFLAGS = $(AM_CCASFLAGS_PPC32_LINUX)
+vgpreload_exp_sgcheck_ppc32_linux_so_DEPENDENCIES = $(LIBREPLACEMALLOC_PPC32_LINUX)
+vgpreload_exp_sgcheck_ppc32_linux_so_LDFLAGS = \
+ $(PRELOAD_LDFLAGS_PPC32_LINUX) \
+ $(LIBREPLACEMALLOC_LDFLAGS_PPC32_LINUX)
+
+vgpreload_exp_sgcheck_ppc64_linux_so_SOURCES = $(VGPRELOAD_EXP_SGCHECK_SOURCES_COMMON)
+vgpreload_exp_sgcheck_ppc64_linux_so_CPPFLAGS = $(AM_CPPFLAGS_PPC64_LINUX)
+vgpreload_exp_sgcheck_ppc64_linux_so_CFLAGS = $(AM_CFLAGS_PPC64_LINUX) $(AM_CFLAGS_PIC) -O2
+vgpreload_exp_sgcheck_ppc64_linux_so_CCASFLAGS = $(AM_CCASFLAGS_PPC64_LINUX)
+vgpreload_exp_sgcheck_ppc64_linux_so_DEPENDENCIES = $(LIBREPLACEMALLOC_PPC64_LINUX)
+vgpreload_exp_sgcheck_ppc64_linux_so_LDFLAGS = \
+ $(PRELOAD_LDFLAGS_PPC64_LINUX) \
+ $(LIBREPLACEMALLOC_LDFLAGS_PPC64_LINUX)
+
+vgpreload_exp_sgcheck_ppc32_aix5_so_SOURCES = $(VGPRELOAD_EXP_SGCHECK_SOURCES_COMMON)
+vgpreload_exp_sgcheck_ppc32_aix5_so_CPPFLAGS = $(AM_CPPFLAGS_PPC32_AIX5)
+vgpreload_exp_sgcheck_ppc32_aix5_so_CFLAGS = $(AM_CFLAGS_PPC32_AIX5) $(AM_CFLAGS_PIC) -O2
+vgpreload_exp_sgcheck_ppc32_aix5_so_CCASFLAGS = $(AM_CCASFLAGS_PPC32_AIX5)
+vgpreload_exp_sgcheck_ppc32_aix5_so_DEPENDENCIES = $(LIBREPLACEMALLOC_PPC32_AIX5)
+vgpreload_exp_sgcheck_ppc32_aix5_so_LDFLAGS = \
+ $(PRELOAD_LDFLAGS_PPC32_AIX5) \
+ $(LIBREPLACEMALLOC_LDFLAGS_PPC32_AIX5)
+
+vgpreload_exp_sgcheck_ppc64_aix5_so_SOURCES = $(VGPRELOAD_EXP_SGCHECK_SOURCES_COMMON)
+vgpreload_exp_sgcheck_ppc64_aix5_so_CPPFLAGS = $(AM_CPPFLAGS_PPC64_AIX5)
+vgpreload_exp_sgcheck_ppc64_aix5_so_CFLAGS = $(AM_CFLAGS_PPC64_AIX5) $(AM_CFLAGS_PIC) -O2
+vgpreload_exp_sgcheck_ppc64_aix5_so_CCASFLAGS = $(AM_CCASFLAGS_PPC64_AIX5)
+vgpreload_exp_sgcheck_ppc64_aix5_so_DEPENDENCIES = $(LIBREPLACEMALLOC_PPC64_AIX5)
+vgpreload_exp_sgcheck_ppc64_aix5_so_LDFLAGS = \
+ $(PRELOAD_LDFLAGS_PPC64_AIX5) \
+ $(LIBREPLACEMALLOC_LDFLAGS_PPC64_AIX5)
+
+
+
+EXP_SGCHECK_SOURCES_COMMON = sg_main.c
+
+exp_sgcheck_x86_linux_SOURCES = $(EXP_SGCHECK_SOURCES_COMMON)
+exp_sgcheck_x86_linux_CPPFLAGS = $(AM_CPPFLAGS_X86_LINUX)
+exp_sgcheck_x86_linux_CFLAGS = $(AM_CFLAGS_X86_LINUX)
+exp_sgcheck_x86_linux_DEPENDENCIES = $(COREGRIND_LIBS_X86_LINUX)
+exp_sgcheck_x86_linux_LDADD = $(TOOL_LDADD_X86_LINUX)
+exp_sgcheck_x86_linux_LDFLAGS = $(TOOL_LDFLAGS_X86_LINUX)
+
+exp_sgcheck_amd64_linux_SOURCES = $(EXP_SGCHECK_SOURCES_COMMON)
+exp_sgcheck_amd64_linux_CPPFLAGS = $(AM_CPPFLAGS_AMD64_LINUX)
+exp_sgcheck_amd64_linux_CFLAGS = $(AM_CFLAGS_AMD64_LINUX)
+exp_sgcheck_amd64_linux_DEPENDENCIES = $(COREGRIND_LIBS_AMD64_LINUX)
+exp_sgcheck_amd64_linux_LDADD = $(TOOL_LDADD_AMD64_LINUX)
+exp_sgcheck_amd64_linux_LDFLAGS = $(TOOL_LDFLAGS_AMD64_LINUX)
+
+exp_sgcheck_ppc32_linux_SOURCES = $(EXP_SGCHECK_SOURCES_COMMON)
+exp_sgcheck_ppc32_linux_CPPFLAGS = $(AM_CPPFLAGS_PPC32_LINUX)
+exp_sgcheck_ppc32_linux_CFLAGS = $(AM_CFLAGS_PPC32_LINUX)
+exp_sgcheck_ppc32_linux_DEPENDENCIES = $(COREGRIND_LIBS_PPC32_LINUX)
+exp_sgcheck_ppc32_linux_LDADD = $(TOOL_LDADD_PPC32_LINUX)
+exp_sgcheck_ppc32_linux_LDFLAGS = $(TOOL_LDFLAGS_PPC32_LINUX)
+
+exp_sgcheck_ppc64_linux_SOURCES = $(EXP_SGCHECK_SOURCES_COMMON)
+exp_sgcheck_ppc64_linux_CPPFLAGS = $(AM_CPPFLAGS_PPC64_LINUX)
+exp_sgcheck_ppc64_linux_CFLAGS = $(AM_CFLAGS_PPC64_LINUX)
+exp_sgcheck_ppc64_linux_DEPENDENCIES = $(COREGRIND_LIBS_PPC64_LINUX)
+exp_sgcheck_ppc64_linux_LDADD = $(TOOL_LDADD_PPC64_LINUX)
+exp_sgcheck_ppc64_linux_LDFLAGS = $(TOOL_LDFLAGS_PPC64_LINUX)
+
+exp_sgcheck_ppc32_aix5_SOURCES = $(EXP_SGCHECK_SOURCES_COMMON)
+exp_sgcheck_ppc32_aix5_CPPFLAGS = $(AM_CPPFLAGS_PPC32_AIX5)
+exp_sgcheck_ppc32_aix5_CFLAGS = $(AM_CFLAGS_PPC32_AIX5)
+exp_sgcheck_ppc32_aix5_DEPENDENCIES = $(COREGRIND_LIBS_PPC32_AIX5)
+exp_sgcheck_ppc32_aix5_LDADD = $(TOOL_LDADD_PPC32_AIX5)
+exp_sgcheck_ppc32_aix5_LDFLAGS = $(TOOL_LDFLAGS_PPC32_AIX5)
+
+exp_sgcheck_ppc64_aix5_SOURCES = $(EXP_SGCHECK_SOURCES_COMMON)
+exp_sgcheck_ppc64_aix5_CPPFLAGS = $(AM_CPPFLAGS_PPC64_AIX5)
+exp_sgcheck_ppc64_aix5_CFLAGS = $(AM_CFLAGS_PPC64_AIX5)
+exp_sgcheck_ppc64_aix5_DEPENDENCIES = $(COREGRIND_LIBS_PPC64_AIX5)
+exp_sgcheck_ppc64_aix5_LDADD = $(TOOL_LDADD_PPC64_AIX5)
+exp_sgcheck_ppc64_aix5_LDFLAGS = $(TOOL_LDFLAGS_PPC64_AIX5)
Added: branches/SGCHECK/exp-sgcheck/docs/Makefile.am
===================================================================
Added: branches/SGCHECK/exp-sgcheck/sg_intercepts.c
===================================================================
--- branches/SGCHECK/exp-sgcheck/sg_intercepts.c (rev 0)
+++ branches/SGCHECK/exp-sgcheck/sg_intercepts.c 2008-08-19 11:20:35 UTC (rev 8528)
@@ -0,0 +1,164 @@
+
+/*--------------------------------------------------------------------*/
+/*--- sgcheck: a stack/global array overrun checker. ---*/
+/*--- sg_intercepts.c ---*/
+/*--------------------------------------------------------------------*/
+
+/*
+ This file is part of SGcheck, a Valgrind tool for checking
+ overruns in stack and global arrays in programs.
+
+ Copyright (C) 2008-2008 OpenWorks Ltd
+ in...@op...
+
+ 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.
+*/
+
+/* Nothing actually in here. However it appears this file is needed
+ to make malloc intercepting work. (jrs, 2 july 08 -- not sure about
+ that).
+*/
+
+#include "pub_tool_basics.h"
+#include "pub_tool_hashtable.h"
+#include "pub_tool_redir.h"
+#include "pub_tool_tooliface.h"
+#include "valgrind.h"
+
+
+/* The following intercepts are copied verbatim from
+ memcheck/mc_replace_strmem.c. */
+
+/* --------- Some handy Z-encoded names. --------- */
+
+/* --- Soname of the standard C library. --- */
+
+#if defined(VGO_linux)
+# define m_libc_soname libcZdsoZa // libc.so*
+#elif defined(VGP_ppc32_aix5)
+ /* AIX has both /usr/lib/libc.a and /usr/lib/libc_r.a. */
+# define m_libc_soname libcZaZdaZLshrZdoZR // libc*.a(shr.o)
+#elif defined(VGP_ppc64_aix5)
+# define m_libc_soname libcZaZdaZLshrZu64ZdoZR // libc*.a(shr_64.o)
+#else
+# error "Unknown platform"
+#endif
+
+/* --- Sonames for Linux ELF linkers. --- */
+
+#define m_ld_linux_so_2 ldZhlinuxZdsoZd2 // ld-linux.so.2
+#define m_ld_linux_x86_64_so_2 ldZhlinuxZhx86Zh64ZdsoZd2 // ld-linux-x86-64.so.2
+#define m_ld64_so_1 ld64ZdsoZd1 // ld64.so.1
+#define m_ld_so_1 ldZdsoZd1 // ld.so.1
+
+
+
+
+#define STRCMP(soname, fnname) \
+ int VG_REPLACE_FUNCTION_ZU(soname,fnname) \
+ ( const char* s1, const char* s2 ); \
+ int VG_REPLACE_FUNCTION_ZU(soname,fnname) \
+ ( const char* s1, const char* s2 ) \
+ { \
+ register unsigned char c1; \
+ register unsigned char c2; \
+ while (True) { \
+ c1 = *(unsigned char *)s1; \
+ c2 = *(unsigned char *)s2; \
+ if (c1 != c2) break; \
+ if (c1 == 0) break; \
+ s1++; s2++; \
+ } \
+ if ((unsigned char)c1 < (unsigned char)c2) return -1; \
+ if ((unsigned char)c1 > (unsigned char)c2) return 1; \
+ return 0; \
+ }
+
+STRCMP(m_libc_soname, strcmp)
+STRCMP(m_ld_linux_x86_64_so_2, strcmp)
+STRCMP(m_ld64_so_1, strcmp)
+
+
+// Note that this replacement often doesn't get used because gcc inlines
+// calls to strlen() with its own built-in version. This can be very
+// confusing if you aren't expecting it. Other small functions in this file
+// may also be inline by gcc.
+#define STRLEN(soname, fnname) \
+ SizeT VG_REPLACE_FUNCTION_ZU(soname,fnname)( const char* str ); \
+ SizeT VG_REPLACE_FUNCTION_ZU(soname,fnname)( const char* str ) \
+ { \
+ SizeT i = 0; \
+ while (str[i] != 0) i++; \
+ return i; \
+ }
+
+STRLEN(m_libc_soname, strlen)
+STRLEN(m_ld_linux_so_2, strlen)
+STRLEN(m_ld_linux_x86_64_so_2, strlen)
+
+
+#define MEMCPY(soname, fnname) \
+ void* VG_REPLACE_FUNCTION_ZU(soname,fnname) \
+ ( void *dst, const void *src, SizeT sz ); \
+ void* VG_REPLACE_FUNCTION_ZU(soname,fnname) \
+ ( void *dest, const void *src, SizeT sz ) \
+ { \
+ const UChar* s = (const UChar*)src; \
+ UChar* d = (UChar*)dest; \
+ const UWord* sW = (const UWord*)src; \
+ UWord* dW = (UWord*)dest; \
+ const UWord al = sizeof(UWord)-1; \
+ \
+ if (0 == (((UWord)dW) & al) && 0 == (((UWord)sW) & al)) { \
+ while (sz >= 4 * sizeof(UWord)) { \
+ dW[0] = sW[0]; \
+ dW[1] = sW[1]; \
+ dW[2] = sW[2]; \
+ dW[3] = sW[3]; \
+ sz -= 4 * sizeof(UWord); \
+ dW += 4; \
+ sW += 4; \
+ } \
+ if (sz == 0) \
+ return dest; \
+ while (sz >= 1 * sizeof(UWord)) { \
+ dW[0] = sW[0]; \
+ sz -= 1 * sizeof(UWord); \
+ dW += 1; \
+ sW += 1; \
+ } \
+ if (sz == 0) \
+ return dest; \
+ s = (const UChar*)sW; \
+ d = (UChar*)dW; \
+ } \
+ \
+ while (sz--) \
+ *d++ = *s++; \
+ \
+ return dest; \
+ }
+
+MEMCPY(m_libc_soname, memcpy)
+MEMCPY(m_ld_so_1, memcpy) /* ld.so.1 */
+MEMCPY(m_ld64_so_1, memcpy) /* ld64.so.1 */
+
+
+/*--------------------------------------------------------------------*/
+/*--- sg_intercepts.c ---*/
+/*--------------------------------------------------------------------*/
Added: branches/SGCHECK/exp-sgcheck/sg_main.c
===================================================================
--- branches/SGCHECK/exp-sgcheck/sg_main.c (rev 0)
+++ branches/SGCHECK/exp-sgcheck/sg_main.c 2008-08-19 11:20:35 UTC (rev 8528)
@@ -0,0 +1,1908 @@
+
+/*--------------------------------------------------------------------*/
+/*--- sgcheck: a stack/global array overrun checker. ---*/
+/*--- sg_main.c ---*/
+/*--------------------------------------------------------------------*/
+
+/*
+ This file is part of SGcheck, a Valgrind tool for checking
+ overruns in stack and global arrays in programs.
+
+ Copyright (C) 2008-2008 OpenWorks Ltd
+ in...@op...
+
+ 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_libcbase.h"
+#include "pub_tool_libcassert.h"
+#include "pub_tool_libcprint.h"
+
+#include "pub_tool_tooliface.h"
+
+#include "pub_tool_wordfm.h"
+#include "pub_tool_xarray.h"
+#include "pub_tool_threadstate.h"
+#include "pub_tool_mallocfree.h"
+#include "pub_tool_machine.h"
+#include "pub_tool_options.h"
+#include "pub_tool_debuginfo.h"
+#include "pub_tool_replacemalloc.h"
+
+
+static void preen_Invars ( Addr a, SizeT len, Bool isHeap ); /*fwds*/
+
+
+//////////////////////////////////////////////////////////////
+// //
+// Basic Stuff //
+// //
+//////////////////////////////////////////////////////////////
+
+static inline Bool is_sane_TId ( ThreadId tid )
+{
+ return tid >= 0 && tid < VG_N_THREADS
+ && tid != VG_INVALID_THREADID;
+}
+
+static void* pc_malloc ( SizeT n ) {
+ void* p;
+ tl_assert(n > 0);
+ p = VG_(malloc)( n );
+ tl_assert(p);
+ return p;
+}
+
+static void pc_free ( void* p ) {
+ tl_assert(p);
+ VG_(free)(p);
+}
+
+
+//////////////////////////////////////////////////////////////
+// //
+// Management of StackBlocks //
+// //
+//////////////////////////////////////////////////////////////
+
+/* We maintain a set of XArray* of StackBlocks. These are never
+ freed. When a new StackBlock vector is acquired from
+ VG_(di_get_local_blocks_at_ip), we compare it to the existing set.
+ If not present, it is added. If present, the just-acquired one is
+ freed and the copy used.
+
+ This simplifies storage management elsewhere. It allows us to
+ assume that a pointer to an XArray* of StackBlock is valid forever.
+ It also means there are no duplicates anywhere, which could be
+ important from a space point of view for programs that generate a
+ lot of translations, or where translations are frequently discarded
+ and re-made.
+
+ Note that we normalise the arrays by sorting the elements according
+ to an arbitrary total order, so as to avoid the situation that two
+ vectors describe the same set of variables but are not structurally
+ identical. */
+
+static inline Bool StackBlock__sane ( StackBlock* fb ) {
+ if (fb->name[ sizeof(fb->name)-1 ] != 0)
+ return False;
+ if (fb->spRel != False && fb->spRel != True)
+ return False;
+ if (fb->isVec != False && fb->isVec != True)
+ return False;
+ return True;
+}
+
+static Int StackBlock__cmp ( StackBlock* fb1, StackBlock* fb2 ) {
+ Int r;
+ tl_assert(StackBlock__sane(fb1));
+ tl_assert(StackBlock__sane(fb2));
+ /* Hopefully the .base test hits most of the time. For the blocks
+ associated with any particular instruction, if the .base values
+ are the same then probably it doesn't make sense for the other
+ fields to be different. But this is supposed to be a completely
+ general structural total order, so we have to compare everything
+ anyway. */
+ if (fb1->base < fb2->base) return -1;
+ if (fb1->base > fb2->base) return 1;
+ /* compare sizes */
+ if (fb1->szB < fb2->szB) return -1;
+ if (fb1->szB > fb2->szB) return 1;
+ /* compare sp/fp flag */
+ if (fb1->spRel < fb2->spRel) return -1;
+ if (fb1->spRel > fb2->spRel) return 1;
+ /* compare is/is-not array-typed flag */
+ if (fb1->isVec < fb2->isVec) return -1;
+ if (fb1->isVec > fb2->isVec) return 1;
+ /* compare the name */
+ r = VG_(strcmp)(fb1->name, fb2->name);
+ return r;
+}
+
+/* Generate an arbitrary total ordering on vectors of StackBlocks. */
+static Word StackBlocks__cmp ( XArray* fb1s, XArray* fb2s ) {
+ Int r;
+ Word i;
+ Word n1 = VG_(sizeXA)( fb1s );
+ Word n2 = VG_(sizeXA)( fb2s );
+ Word n = n1 > n2 ? n1 : n2; /* max(n1,n2) */
+ for (i = 0; i < n; i++) {
+ StackBlock *fb1, *fb2;
+ if (i >= n1) {
+ /* fb1s ends first, and all previous entries identical. */
+ tl_assert(i < n2);
+ return -1;
+ }
+ if (i >= n2) {
+ /* fb2s ends first, and all previous entries identical. */
+ tl_assert(i < n1);
+ return 1;
+ }
+ tl_assert(i < n1 && i < n2);
+ fb1 = VG_(indexXA)( fb1s, i );
+ fb2 = VG_(indexXA)( fb2s, i );
+ r = StackBlock__cmp( fb1, fb2 );
+ if (r != 0) return r;
+ }
+ tl_assert(n1 == n2);
+ return 0;
+}
+
+
+/* ---------- The StackBlock vector cache ---------- */
+
+static WordFM* /* XArray* of StackBlock -> nothing */
+ frameBlocks_set = NULL;
+
+static void init_StackBlocks_set ( void )
+{
+ tl_assert(!frameBlocks_set);
+ frameBlocks_set = VG_(newFM)( pc_malloc, pc_free,
+ (Word(*)(UWord,UWord))StackBlocks__cmp );
+ tl_assert(frameBlocks_set);
+}
+
+/* Find the given StackBlock-vector in our collection thereof. If
+ found, deallocate the supplied one, and return the address of the
+ copy. If not found, add the supplied one to our collection and
+ return its address. */
+static XArray* /* of StackBlock */
+ StackBlocks__find_and_dealloc__or_add
+ ( XArray* /* of StackBlock */ orig )
+{
+ UWord key, val;
+
+ /* First, normalise, as per comments above. */
+ VG_(setCmpFnXA)( orig, (Int(*)(void*,void*))StackBlock__cmp );
+ VG_(sortXA)( orig );
+
+ /* Now, do we have it already? */
+ if (VG_(lookupFM)( frameBlocks_set, &key, &val, (UWord)orig )) {
+ /* yes */
+ tl_assert(val == 0);
+ tl_assert(key != (UWord)orig);
+ VG_(deleteXA)(orig);
+ return (XArray*)key;
+ } else {
+ /* no */
+ VG_(addToFM)( frameBlocks_set, (UWord)orig, 0 );
+ return orig;
+ }
+}
+
+/* Top level function for getting the StackBlock vector for a given
+ instruction. */
+
+static XArray* /* of StackBlock */ get_StackBlocks_for_IP ( Addr ip )
+{
+ XArray* blocks = VG_(di_get_stack_blocks_at_ip)( ip, False/*!arrays only*/ );
+ tl_assert(blocks);
+ return StackBlocks__find_and_dealloc__or_add( blocks );
+}
+
+
+//////////////////////////////////////////////////////////////
+// //
+// The Global Block Interval Tree //
+// //
+//////////////////////////////////////////////////////////////
+
+/* This tree holds all the currently known-about globals. We must
+ modify it at each mmap that results in debuginfo being read, and at
+ each munmap, as the latter will cause globals to disappear. At
+ each munmap, we must also prune the Invars, since munmaps may cause
+ GlobalBlocks to disappear, and so the Invars may no longer mention
+ them. */
+
+/* Implement an interval tree, containing GlobalBlocks. The blocks
+ must all be non-zero sized and may not overlap. The access
+ functions maintain that invariant.
+
+ Storage management: GlobalBlocks in the tree are copies of ones
+ presented as args to add_GlobalBlock. The originals are never
+ added to the tree. del_GlobalBlocks_in_range frees up the storage
+ allocated by add_GlobalBlock. */
+
+/* The tree */
+static WordFM* globals = NULL; /* WordFM GlobalBlock* void */
+
+static Word cmp_intervals_GlobalBlock ( GlobalBlock* gb1, GlobalBlock* gb2 )
+{
+ tl_assert(gb1 && gb1->szB > 0);
+ tl_assert(gb2 && gb2->szB > 0);
+ if (gb1->addr + gb1->szB <= gb2->addr) return -1;
+ if (gb2->addr + gb2->szB <= gb1->addr) return 1;
+ return 0;
+}
+
+static void init_globals ( void )
+{
+ tl_assert(!globals);
+ globals = VG_(newFM)( pc_malloc, pc_free,
+ (Word(*)(UWord,UWord))cmp_intervals_GlobalBlock );
+ tl_assert(globals);
+}
+
+
+/* Find the block containing 'a', if possible. Returned pointer is
+ only transiently valid; it will become invalid at the next global
+ mapping or unmapping operation. */
+static GlobalBlock* find_GlobalBlock_containing ( Addr a )
+{
+ UWord oldK, oldV;
+ GlobalBlock key;
+ key.addr = a;
+ key.szB = 1;
+ if (VG_(lookupFM)( globals, &oldK, &oldV, (UWord)&key )) {
+ GlobalBlock* res = (GlobalBlock*)oldK;
+ tl_assert(oldV == 0);
+ tl_assert(res->szB > 0);
+ tl_assert(res->addr <= a && a < res->addr + res->szB);
+ return res;
+ } else {
+ return NULL;
+ }
+}
+
+
+/* Add a block to the collection. Presented block is not stored
+ directly; instead a copy is made and stored. If the block overlaps
+ an existing block (it should not, but we need to be robust to such
+ eventualities) it is merged with existing block(s), so as to
+ preserve the no-overlap property of the tree as a whole. */
+static void add_GlobalBlock ( GlobalBlock* gbOrig )
+{
+ UWord keyW, valW;
+ GlobalBlock* gb;
+ tl_assert(gbOrig && gbOrig->szB > 0);
+ gb = pc_malloc( sizeof(GlobalBlock) );
+ *gb = *gbOrig;
+
+ /* Dealing with overlaps. One possibility is to look up the entire
+ interval to be added. If we get something back, it overlaps an
+ existing interval; then delete the existing interval, merge it
+ into the one to be added, and repeat, until the to-be added
+ interval really doesn't intersect any existing interval. */
+
+ while (VG_(lookupFM)( globals, &keyW, &valW, (UWord)gb )) {
+ tl_assert(valW == 0);
+ /* keyW is the overlapping key. Pull it out of the tree, merge
+ into 'gb', free keyW, complain to the user, repeat. */
+ tl_assert(0);
+ }
+
+ VG_(addToFM)(globals, (UWord)gb, (UWord)0);
+}
+
+
+/* Remove all blocks from the tree intersecting [a,a+len), and release
+ associated storage. One way to do it is to simply look up the
+ interval, and if something comes back, delete it on the basis that
+ it must intersect the interval. Keep doing this until the lookup
+ finds nothing. Returns a Bool indicating whether any blocks
+ did actually intersect the range. */
+static Bool del_GlobalBlocks_in_range ( Addr a, SizeT len )
+{
+ UWord oldK, oldV;
+ GlobalBlock key;
+ Bool foundAny = False;
+
+ tl_assert(len > 0);
+ key.addr = a;
+ key.szB = len;
+ while (VG_(delFromFM)( globals, &oldK, &oldV, (UWord)&key )) {
+ GlobalBlock* old;
+ tl_assert(oldV == 0);
+ old = (GlobalBlock*)oldK;
+ /* 'old' will be removed. Preen the Invars now? */
+ pc_free(old);
+ foundAny = True;
+ }
+ return foundAny;
+}
+
+
+//////////////////////////////////////////////////////////////
+
+static void acquire_globals ( ULong di_handle )
+{
+ Word n, i;
+ XArray* /* of GlobalBlock */ gbs;
+
+ if (0) VG_(printf)("ACQUIRE GLOBALS %llu\n", di_handle );
+ gbs = VG_(di_get_global_blocks_from_dihandle)
+ (di_handle, False/*!arrays only*/);
+ if (0) VG_(printf)(" GOT %ld globals\n", VG_(sizeXA)( gbs ));
+
+ n = VG_(sizeXA)( gbs );
+ for (i = 0; i < n; i++) {
+ GlobalBlock* gb = VG_(indexXA)( gbs, i );
+ VG_(printf)(" new Global size %2lu at %#lx: %s %s\n",
+ gb->szB, gb->addr, gb->soname, gb->name );
+ tl_assert(gb->szB > 0);
+ /* Add each global to the map. We can present them
+ indiscriminately to add_GlobalBlock, since that adds copies
+ of presented blocks, not the original. This is important
+ because we are just about to delete the XArray in which we
+ received these GlobalBlocks. */
+ add_GlobalBlock( gb );
+ }
+
+ VG_(deleteXA)( gbs );
+}
+
+
+/* We only intercept these two because we need to see any di_handles
+ that might arise from the mappings/allocations. */
+static void sg_new_mem_mmap( Addr a, SizeT len,
+ Bool rr, Bool ww, Bool xx, ULong di_handle )
+{
+ if (di_handle > 0)
+ acquire_globals(di_handle);
+}
+static void sg_new_mem_startup( Addr a, SizeT len,
+ Bool rr, Bool ww, Bool xx, ULong di_handle )
+{
+ if (di_handle > 0)
+ acquire_globals(di_handle);
+}
+static void sg_die_mem_munmap ( Addr a, SizeT len )
+{
+ Bool debug = 0||False;
+ Bool overlap = False;
+ if (debug) VG_(printf)("MUNMAP %#lx %lu\n", a, len );
+ if (len == 0)
+ return;
+
+ overlap = del_GlobalBlocks_in_range(a, len);
+ if (!overlap)
+ return;
+
+ /* Ok, the range contained some blocks. Therefore we'll need to
+ visit all the Invars in all the thread shadow stacks, and
+ convert all Inv_Global{S,V} entries that intersect [a,a+len) to
+ Inv_Unknown. */
+ tl_assert(len > 0);
+ preen_Invars( a, len, False/*!isHeap*/ );
+}
+
+
+//////////////////////////////////////////////////////////////
+// //
+// The Heap Block Interval Tree //
+// //
+//////////////////////////////////////////////////////////////
+
+/* This tree holds all the currently known-about heap blocks. We must
+ modify it at each malloc/free, and prune the Invars when freeing
+ blocks (since they disappear, the Invars may no longer mention
+ them). */
+
+/* Implement an interval tree, containing HeapBlocks. The blocks must
+ all be non-zero sized and may not overlap, although if they do
+ overlap that must constitute a bug in our malloc/free
+ implementation, and so we might as well just assert.
+
+ There's a nasty kludge. In fact we must be able to deal with zero
+ sized blocks, since alloc_mem_heap/free_mem_heap/pc_replace_malloc
+ use the blocks stored to keep track of what blocks the client has
+ allocated, so there's no avoiding the requirement of having one
+ block in the tree for each client allocated block, even for
+ zero-sized client blocks.
+
+ The kludge is: have two size fields. One is the real size
+ (.realSzB) and can be zero. The other (.fakeSzB) is used, along
+ with .addr to provide the ordering induced by
+ cmp_intervals_HeapBlock. .fakeSzB is the same as .realSzB except
+ in the single case where .realSzB is zero, in which case .fakeSzB
+ is 1. This works because the allocator won't allocate two zero
+ sized blocks at the same location (ANSI C disallows this) and so,
+ from an ordering point of view, it's safe treat zero sized blocks
+ as blocks of size 1. However, we need to keep the real un-kludged
+ size around too (as .realSzB), so that
+ alloc_mem_heap/free_mem_heap/pc_replace_malloc and also
+ classify_block have correct information.
+
+ Storage management: HeapBlocks in the tree are copies of ones
+ presented as args to add_HeapBlock. The originals are never
+ added to the tree. del_HeapBlocks_in_range frees up the storage
+ allocated by add_GlobalBlock. */
+
+typedef
+ struct {
+ Addr addr;
+ SizeT fakeSzB;
+ SizeT realSzB;
+ }
+ HeapBlock;
+
+/* the tree */
+static WordFM* heap = NULL; /* WordFM HeapBlock* void */
+
+static Word cmp_intervals_HeapBlock ( HeapBlock* hb1, HeapBlock* hb2 )
+{
+ tl_assert(hb1);
+ tl_assert(hb2);
+ tl_assert(hb1->fakeSzB > 0);
+ tl_assert(hb2->fakeSzB > 0);
+ if (hb1->addr + hb1->fakeSzB <= hb2->addr) return -1;
+ if (hb2->addr + hb2->fakeSzB <= hb1->addr) return 1;
+ return 0;
+}
+
+
+static void init_heap ( void )
+{
+ tl_assert(!heap);
+ heap = VG_(newFM)( pc_malloc, pc_free,
+ (Word(*)(UWord,UWord))cmp_intervals_HeapBlock );
+ tl_assert(heap);
+}
+
+
+/* Find the heap block containing 'a', if possible. Returned pointer
+ is only transiently valid; it will become invalid at the next
+ client malloc or free operation. */
+static HeapBlock* find_HeapBlock_containing ( Addr a )
+{
+ UWord oldK, oldV;
+ HeapBlock key;
+ key.addr = a;
+ key.fakeSzB = 1;
+ key.realSzB = 0; /* unused, but initialise it anyway */
+ if (VG_(lookupFM)( heap, &oldK, &oldV, (UWord)&key )) {
+ HeapBlock* res = (HeapBlock*)oldK;
+ tl_assert(oldV == 0);
+ tl_assert(res->fakeSzB > 0);
+ tl_assert(res->addr <= a && a < res->addr + res->fakeSzB);
+ /* Now, just one more thing. If the real size is in fact zero
+ then 'a' can't fall within it. No matter what 'a' is. Hence: */
+ if (res->realSzB == 0) {
+ tl_assert(res->fakeSzB == 1);
+ return NULL;
+ }
+ /* Normal case. */
+ return res;
+ } else {
+ return NULL;
+ }
+}
+
+
+/* Add a block to the collection. If the block overlaps an existing
+ block (it should not, but we need to be robust to such
+ eventualities) we simply assert, as that is probably a result of a
+ bug in our malloc implementation. (although could be due to buggy
+ custom allocators?) In any case we must either assert or somehow
+ (as per GlobalBlocks) avoid overlap, so as to preserve the
+ no-overlap property of the tree as a whole. */
+static void add_HeapBlock ( Addr addr, SizeT realSzB )
+{
+ UWord keyW, valW;
+ HeapBlock* hb;
+
+ SizeT fakeSzB = realSzB == 0 ? 1 : realSzB;
+ tl_assert(fakeSzB > 0);
+
+ tl_assert(addr);
+ hb = pc_malloc( sizeof(HeapBlock) );
+ hb->addr = addr;
+ hb->fakeSzB = fakeSzB;
+ hb->realSzB = realSzB;
+ /* Check there's no overlap happening. */
+ while (VG_(lookupFM)( heap, &keyW, &valW, (UWord)hb )) {
+ tl_assert(valW == 0);
+ /* keyW is the overlapping HeapBlock*. Need to handle this
+ case, as per comment above. */
+ tl_assert(0);
+ }
+
+ VG_(addToFM)(heap, (UWord)hb, (UWord)0);
+}
+
+
+/* Delete a heap block at guest address 'addr' from the tree. Ignore
+ if there is no block beginning exactly at 'addr' (means the guest
+ is handing invalid pointers to free() et al). Returns the True if
+ found, in which case the block's size is written to *szB. The
+ shadow block (HeapBlock) is freed, but the payload (what .addr
+ points at) are not. */
+static Bool del_HeapBlock_at ( SizeT* szB, Addr addr )
+{
+ Bool b;
+ UWord oldK, oldV;
+ HeapBlock key, *hb;
+
+ hb = find_HeapBlock_containing(addr);
+ if (!hb) return False;
+ if (hb->addr != addr) return False;
+
+ key.addr = addr;
+ key.fakeSzB = 1;
+ key.realSzB = 0; /* unused, but initialise it anyway */
+ b = VG_(delFromFM)( heap, &oldK, &oldV, (UWord)&key );
+ tl_assert(b); /* we just looked it up, so deletion must succeed */
+ tl_assert(oldV == 0);
+
+ hb = (HeapBlock*)oldK;
+ tl_assert(hb);
+ tl_assert(hb->addr == addr);
+
+ *szB = hb->realSzB;
+ pc_free(hb);
+ return True;
+}
+
+
+//////////////////////////////////////////////////////////////
+static
+void* alloc_mem_heap ( ThreadId tid,
+ SizeT size, SizeT alignment, Bool is_zeroed )
+{
+ Addr p;
+ if ( ((SSizeT)size) < 0)
+ return NULL;
+ p = (Addr)VG_(cli_malloc)(alignment, size);
+ if (p == 0)
+ return NULL;
+ if (is_zeroed)
+ VG_(memset)((void*)p, 0, size);
+ add_HeapBlock( p, size );
+ return (void*)p;
+}
+
+static void free_mem_heap ( ThreadId tid, Addr p )
+{
+ SizeT old_size = 0;
+ Bool found = del_HeapBlock_at( &old_size, p );
+ if (found) {
+ VG_(cli_free)( (void*)p );
+ if (old_size > 0)
+ preen_Invars( p, old_size, True/*isHeap*/ );
+ }
+}
+
+static void* pc_replace_malloc ( ThreadId tid, SizeT n ) {
+ return alloc_mem_heap ( tid, n, VG_(clo_alignment),
+ /*is_zeroed*/False );
+}
+
+static void* pc_replace___builtin_new ( ThreadId tid, SizeT n ) {
+ return alloc_mem_heap ( tid, n, VG_(clo_alignment),
+ /*is_zeroed*/False );
+}
+
+static void* pc_replace___builtin_vec_new ( ThreadId tid, SizeT n ) {
+ return alloc_mem_heap ( tid, n, VG_(clo_alignment),
+ /*is_zeroed*/False );
+}
+
+static void* pc_replace_memalign ( ThreadId tid, SizeT align, SizeT n ) {
+ return alloc_mem_heap ( tid, n, align,
+ /*is_zeroed*/False );
+}
+
+static void* pc_replace_calloc ( ThreadId tid, SizeT nmemb, SizeT size1 ) {
+ return alloc_mem_heap ( tid, nmemb*size1, VG_(clo_alignment),
+ /*is_zeroed*/True );
+}
+
+static void pc_replace_free ( ThreadId tid, void* p ) {
+ free_mem_heap(tid, (Addr)p);
+}
+
+static void pc_replace___builtin_delete ( ThreadId tid, void* p ) {
+ free_mem_heap(tid, (Addr)p);
+}
+
+static void pc_replace___builtin_vec_delete ( ThreadId tid, void* p ) {
+ free_mem_heap(tid, (Addr)p);
+}
+
+static void* pc_replace_realloc ( ThreadId tid, void* p_old, SizeT new_size )
+{
+ Addr p_new;
+
+ /* First try and find the block. */
+ SizeT old_size = 0;
+ Bool found = del_HeapBlock_at( &old_size, (Addr)p_old );
+
+ if (!found)
+ return NULL;
+
+ if (old_size > 0)
+ preen_Invars( (Addr)p_old, old_size, True/*isHeap*/ );
+
+ if (new_size <= old_size) {
+ /* new size is smaller: allocate, copy from old to new */
+ p_new = (Addr)VG_(cli_malloc)(VG_(clo_alignment), new_size);
+ VG_(memcpy)((void*)p_new, p_old, new_size);
+ } else {
+ /* new size is bigger: allocate, copy from old to new */
+ p_new = (Addr)VG_(cli_malloc)(VG_(clo_alignment), new_size);
+ VG_(memcpy)((void*)p_new, p_old, old_size);
+ }
+
+ VG_(cli_free)( (void*)p_old );
+ add_HeapBlock( p_new, new_size );
+ return (void*)p_new;
+}
+
+
+//////////////////////////////////////////////////////////////
+// //
+// Invar //
+// //
+//////////////////////////////////////////////////////////////
+
+/* An invariant, as resulting from watching the destination of a
+ memory referencing instruction. Initially is Inv_Unset until the
+ instruction makes a first access. */
+
+typedef
+ enum {
+ Inv_Unset=1, /* not established yet */
+ Inv_Unknown, /* unknown location */
+ Inv_StackS, Inv_StackV, /* scalar/vector stack block */
+ Inv_GlobalS, Inv_GlobalV, /* scalar/vector global block */
+ Inv_Heap /* a block in the heap */
+ }
+ InvarTag;
+
+typedef
+ struct {
+ InvarTag tag;
+ union {
+ struct {
+ } Unset;
+ struct {
+ } Unknown;
+ struct {
+ /* EQ */ UWord framesBack;
+ /* EQ */ UWord fbIndex;
+ /* EXPO */ HChar name[16]; /* asciiz */
+ /* ReVal */ Addr start;
+ /* ReVal */ SizeT len;
+ } Stack;
+ struct {
+ /* EQ */ HChar name[16]; /* asciiz */
+ /* EQ */ HChar soname[16]; /* asciiz */
+ /* ReVal */ Addr start;
+ /* ReVal */ SizeT len;
+ } Global;
+ struct {
+ /* EQ, ReVal */ Addr start;
+ /* ReVal */ SizeT len;
+ } Heap;
+ }
+ Inv;
+ }
+ Invar;
+
+/* Compare two Invars for equality, based on the EQ fields in the
+ declaration above. */
+static Bool eq_Invar ( Invar* i1, Invar* i2 )
+{
+ tl_assert(i1->tag != Inv_Unset);
+ tl_assert(i2->tag != Inv_Unset);
+ if (i1->tag != i2->tag)
+ return False;
+ switch (i1->tag) {
+ case Inv_Unknown:
+ return True;
+ case Inv_StackS:
+ case Inv_StackV:
+ return i1->Inv.Stack.framesBack == i2->Inv.Stack.framesBack
+ && i1->Inv.Stack.fbIndex == i2->Inv.Stack.fbIndex;
+ case Inv_GlobalS:
+ case Inv_GlobalV:
+ tl_assert(i1->Inv.Global.name[
+ sizeof(i1->Inv.Global.name)-1 ] == 0);
+ tl_assert(i2->Inv.Global.name[
+ sizeof(i2->Inv.Global.name)-1 ] == 0);
+ tl_assert(i1->Inv.Global.soname[
+ sizeof(i1->Inv.Global.soname)-1 ] == 0);
+ tl_assert(i2->Inv.Global.soname[
+ sizeof(i2->Inv.Global.soname)-1 ] == 0);
+ return
+ 0==VG_(strcmp)(i1->Inv.Global.name, i2->Inv.Global.name)
+ && 0==VG_(strcmp)(i1->Inv.Global.soname, i2->Inv.Global.soname);
+ case Inv_Heap:
+ return i1->Inv.Heap.start == i2->Inv.Heap.start
+ && i1->Inv.Heap.len == i2->Inv.Heap.len;
+ default:
+ tl_assert(0);
+ }
+ /*NOTREACHED*/
+ tl_assert(0);
+}
+
+/* Print selected parts of an Invar, suitable for use in error
+ messages. */
+static void show_Invar( HChar* buf, Word nBuf, Invar* inv )
+{
+ HChar* str;
+ tl_assert(nBuf >= 128);
+ buf[0] = 0;
+ switch (inv->tag) {
+ case Inv_Unknown:
+ VG_(sprintf)(buf, "%s", "unknown");
+ break;
+ case Inv_StackS:
+ case Inv_StackV:
+ tl_assert(inv->Inv.Stack.name[sizeof(inv->Inv.Stack.name)-1] == 0);
+ str = inv->tag == Inv_StackS ? "non-array" : "array";
+ if (inv->Inv.Stack.framesBack == 0) {
+ VG_(sprintf)(buf, "stack %s \"%s\" in this frame",
+ str, inv->Inv.Stack.name );
+ } else {
+ VG_(sprintf)(buf, "stack %s \"%s\" in frame %lu back from here",
+ str, inv->Inv.Stack.name,
+ inv->Inv.Stack.framesBack );
+ }
+ break;
+ case Inv_GlobalS:
+ case Inv_GlobalV:
+ str = inv->tag == Inv_GlobalS ? "non-array" : "array";
+ VG_(sprintf)(buf, "global %s \"%s\" in object with soname \"%s\"",
+ str, inv->Inv.Global.name, inv->Inv.Global.soname );
+ break;
+ case Inv_Heap:
+ VG_(sprintf)(buf, "%s", "heap block");
+ break;
+ case Inv_Unset:
+ VG_(sprintf)(buf, "%s", "Unset!");
+ break;
+ default:
+ tl_assert(0);
+ }
+}
+
+
+//////////////////////////////////////////////////////////////
+// //
+// StackFrame //
+// //
+//////////////////////////////////////////////////////////////
+
+static ULong stats__total_accesses = 0;
+static ULong stats__reval_Stack = 0;
+static ULong stats__reval_Global = 0;
+static ULong stats__reval_Heap = 0;
+static ULong stats__classify_Stack = 0;
+static ULong stats__classify_Global = 0;
+static ULong stats__classify_Heap = 0;
+static ULong stats__classify_Unknown = 0;
+static ULong stats__Invars_preened = 0;
+static ULong stats__Invars_changed = 0;
+
+/* A dynamic instance of an instruction */
+typedef
+ struct {
+ /* IMMUTABLE */
+ Addr insn_addr; /* NB! zero means 'not in use' */
+ XArray* blocks; /* XArray* of StackBlock */
+ /* MUTABLE */
+ Invar invar;
+ }
+ IInstance;
+
+
+typedef
+ struct {
+ /* The sp when the frame was created, so we know when to get rid
+ of it. */
+ Addr creation_sp;
+ /* Information for each memory referencing instruction, for this
+ instantiation of the function. The iinstances array is
+ operated as a simple linear-probe hash table, which is
+ dynamically expanded as necessary. Once critical thing is
+ that an IInstance with a .insn_addr of zero is interpreted to
+ mean that hash table slot is unused. This means we can't
+ store an IInstance for address zero. */
+ IInstance* htab;
+ UWord htab_size; /* size of hash table, MAY ONLY BE A POWER OF 2 */
+ UWord htab_used; /* number of hash table slots currently in use */
+ /* If this frame is currently making a call, then the following
+ are relevant. */
+ Addr sp_at_call;
+ Addr fp_at_call;
+ XArray* /* of StackBlock */ blocks_at_call;
+ }
+ StackFrame;
+
+
+/* ShadowStack == XArray of StackFrame */
+
+
+static XArray* shadowStacks[VG_N_THREADS];
+
+static void shadowStacks_init ( void )
+{
+ Int i;
+ for (i = 0; i < VG_N_THREADS; i++) {
+ shadowStacks[i] = NULL;
+ }
+}
+
+
+/* Move this somewhere else? */
+/* Visit all Invars in the entire system. If 'isHeap' is True, change
+ all Inv_Heap Invars that intersect [a,a+len) to Inv_Unknown. If
+ 'isHeap' is False, do the same but to the Inv_Global{S,V} Invars
+ instead. */
+inline
+static Bool rangesOverlap ( Addr a1, SizeT n1, Addr a2, SizeT n2 ) {
+ tl_assert(n1 > 0 && n2 > 0);
+ if (a1 + n1 < a2) return False;
+ if (a2 + n2 < a1) return False;
+ return True;
+}
+
+__attribute__((noinline))
+static void preen_Invar ( Invar* inv, Addr a, SizeT len, Bool isHeap )
+{
+ stats__Invars_preened++;
+ tl_assert(len > 0);
+ tl_assert(inv);
+ switch (inv->tag) {
+ case Inv_Heap:
+ tl_assert(inv->Inv.Heap.len > 0);
+ if (isHeap && rangesOverlap(a, len, inv->Inv.Heap.start,
+ inv->Inv.Heap.len)) {
+ inv->tag = Inv_Unknown;
+ stats__Invars_changed++;
+ }
+ break;
+ case Inv_GlobalS:
+ case Inv_GlobalV:
+ tl_assert(inv->Inv.Global.len > 0);
+ if ((!isHeap)
+ && rangesOverlap(a, len, inv->Inv.Global.start,
+ inv->Inv.Global.len)) {
+ inv->tag = Inv_Unknown;
+ stats__Invars_changed++;
+ }
+ break;
+ case Inv_StackS:
+ case Inv_StackV:
+ case Inv_Unknown:
+ break;
+ default: tl_assert(0);
+ }
+}
+
+__attribute__((noinline))
+static void preen_Invars ( Addr a, SizeT len, Bool isHeap )
+{
+ Int i;
+ Word ixFrames, nFrames;
+ UWord u;
+ XArray* stack; /* XArray* of StackFrame */
+ StackFrame* frame;
+ tl_assert(len > 0);
+ for (i = 0; i < VG_N_THREADS; i++) {
+ stack = shadowStacks[i];
+ if (!stack)
+ continue;
+ nFrames = VG_(sizeXA)( stack );
+ for (ixFrames = 0; ixFrames < nFrames; ixFrames++) {
+ UWord xx = 0; /* sanity check only; count of used htab entries */
+ frame = VG_(indexXA)( stack, ixFrames );
+ tl_assert(frame->htab);
+ for (u = 0; u < frame->htab_size; u++) {
+ IInstance* ii = &frame->htab[u];
+ if (ii->insn_addr == 0)
+ continue; /* not in use */
+ preen_Invar( &ii->invar, a, len, isHeap );
+ xx++;
+ }
+ tl_assert(xx == frame->htab_used);
+ }
+ }
+}
+
+
+__attribute__((noinline))
+static void initialise_hash_table ( StackFrame* sf )
+{
+ UWord i;
+ sf->htab_size = 4; /* initial hash table size */
+ sf->htab = pc_malloc(sf->htab_size * sizeof(IInstance));
+ tl_assert(sf->htab);
+ sf->htab_used = 0;
+ for (i = 0; i < sf->htab_size; i++)
+ sf->htab[i].insn_addr = 0; /* NOT IN USE */
+}
+
+
+__attribute__((noinline))
+static void resize_hash_table ( StackFrame* sf )
+{
+ UWord i, j, ix, old_size, new_size;
+ IInstance *old_htab, *new_htab, *old;
+
+ tl_assert(sf && sf->htab);
+ old_size = sf->htab_size;
+ new_size = 2 * old_size;
+ old_htab = sf->htab;
+ new_htab = pc_malloc( new_size * sizeof(IInstance) );
+ for (i = 0; i < new_size; i++) {
+ new_htab[i].insn_addr = 0; /* NOT IN USE */
+ }
+ for (i = 0; i < old_size; i++) {
+ old = &old_htab[i];
+ if (old->insn_addr == 0 /* NOT IN USE */)
+ continue;
+ ix = (old->insn_addr >> 0) & (new_size - 1);
+ /* find out where to put this, in the new table */
+ j = new_size;
+ while (1) {
+ if (new_htab[ix].insn_addr == 0)
+ break;
+ /* This can't ever happen, because it would mean the new
+ table is full; that isn't allowed -- even the old table is
+ only allowed to become half full. */
+ tl_assert(j > 0);
+ j--;
+ ix++; if (ix == new_size) ix = 0;
+ }
+ /* copy the old entry to this location */
+ tl_assert(ix < new_size);
+ tl_assert(new_htab[ix].insn_addr == 0);
+ new_htab[ix] = *old;
+ tl_assert(new_htab[ix].insn_addr != 0);
+ }
+ /* all entries copied; free old table. */
+ pc_free(old_htab);
+ sf->htab = new_htab;
+ sf->htab_size = new_size;
+ /* check sf->htab_used is correct. Optional and a bit expensive
+ but anyway: */
+ j = 0;
+ for (i = 0; i < new_size; i++) {
+ if (new_htab[i].insn_addr != 0) {
+ j++;
+ }
+ }
+ tl_assert(j == sf->htab_used);
+ if (0) VG_(printf)("resized tab for SF %p to %lu\n", sf, new_size);
+}
+
+
+__attribute__((noinline))
+static IInstance* find_or_create_IInstance (
+ StackFrame* sf,
+ Addr ip,
+ XArray* /* StackBlock */ ip_frameblocks
+ )
+{
+ UWord i, ix;
+ start_over:
+ tl_assert(sf);
+ tl_assert(sf->htab);
+
+ if (0) VG_(printf)("XXX ip %#lx size %lu used %lu\n",
+ ip, sf->htab_size, sf->htab_used);
+ tl_assert(2 * sf->htab_used <= sf->htab_size);
+
+ ix = (ip >> 0) & (sf->htab_size - 1);
+ i = sf->htab_size;
+ while (1) {
+ if (sf->htab[ix].insn_addr == ip)
+ return &sf->htab[ix];
+ if (sf->htab[ix].insn_addr == 0)
+ break;
+ /* If i ever gets to zero and we have found neither what we're
+ looking for nor an empty slot, the table must be full. Which
+ isn't possible -- we monitor the load factor to ensure it
+ doesn't get above say 50%; if that ever does happen the table
+ is resized. */
+ tl_assert(i > 0);
+ i--;
+ ix++;
+ if (ix == sf->htab_size) ix = 0;
+ }
+
+ /* So now we've found a free slot at ix, and we can use that.
+ Except, first check if we need to resize the table. If so,
+ resize it, and start all over again. */
+ tl_assert(sf->htab[ix].insn_addr == 0);
+ if (2 * sf->htab_used >= 1 * sf->htab_size) {
+ resize_hash_table(sf);
+ goto start_over;
+ }
+
+ /* Add a new record in this slot. */
+ tl_assert(ip != 0); /* CAN'T REPRESENT THIS */
+ sf->htab[ix].insn_addr = ip;
+ sf->htab[ix].blocks = ip_frameblocks;
+ sf->htab[ix].invar.tag = Inv_Unset;
+ sf->htab_used++;
+ return &sf->htab[ix];
+}
+
+
+__attribute__((noinline))
+static Bool find_in_StackBlocks ( /*OUT*/UWord* ix,
+ /*OUT*/Bool* isVec,
+ /*OUT*/Addr* blockEA,
+ /*OUT*/SizeT* blockSzB,
+ /*OUT*/HChar** name,
+ Addr ea, Addr sp, Addr fp,
+ UWord szB, XArray* blocks )
+{
+ Word i, n;
+ OffT delta_FP = ea - fp;
+ OffT delta_SP = ea - sp;
+ tl_assert(szB > 0 && szB <= 512);
+ n = VG_(sizeXA)( blocks );
+ for (i = 0; i < n; i++) {
+ OffT delta;
+ StackBlock* block = VG_(indexXA)( blocks, i );
+ delta = block->spRel ? delta_SP : delta_FP;
+ { Word w1 = block->base;
+ Word w2 = delta;
+ Word w3 = (Word)( ((UWord)delta) + ((UWord)szB) );
+ Word w4 = (Word)( ((UWord)block->base) + ((UWord)block->szB) );
+ if (w1 <= w2 && w3 <= w4) {
+ *ix = i;
+ *isVec = block->isVec;
+ *blockEA = block->base + (block->spRel ? sp : fp);
+ *blockSzB = block->szB;
+ *name = &block->name[0];
+ return True;
+ }
+ }
+ }
+ return False;
+}
+
+
+/* Try to classify the block into which a memory access falls, and
+ write the result in 'inv'. This writes all fields of 'inv',
+ including, importantly the ReVal (revalidation) fields. */
+__attribute__((noinline))
+static void classify_address ( /*OUT*/Invar* inv,
+ ThreadId tid,
+ Addr ea, Addr sp, Addr fp,
+ UWord szB,
+ XArray* /* of StackBlock */ thisInstrBlocks,
+ XArray* /* of StackFrame */ thisThreadFrames )
+{
+ tl_assert(szB > 0);
+ /* First, look in the stack blocks accessible in this instruction's
+ frame. */
+ {
+ UWord ix;
+ Bool isVec;
+ Addr blockEA;
+ SizeT blockSzB;
+ HChar* name;
+ Bool b = find_in_StackBlocks(
+ &ix, &isVec, &blockEA, &blockSzB, &name,
+ ea, sp, fp, szB, thisInstrBlocks
+ );
+ if (b) {
+ SizeT nameSzB = sizeof(inv->Inv.Stack.name);
+ inv->tag = isVec ? Inv_StackV : Inv_StackS;
+ inv->Inv.Stack.framesBack = 0;
+ inv->Inv.Stack.fbIndex = ix;
+ inv->Inv.Stack.start = blockEA;
+ inv->Inv.Stack.len = blockSzB;
+ VG_(memcpy)( &inv->Inv.Stack.name[0], name, nameSzB );
+ inv->Inv.Stack.name[ nameSzB-1 ] = 0;
+ stats__classify_Stack++;
+ return;
+ }
+ }
+ /* Perhaps it's a heap block? */
+ { HeapBlock* hb = find_HeapBlock_containing(ea);
+ if (hb) {
+ /* it's not possible for find_HeapBlock_containing to
+ return a block of zero size. Hence: */
+ tl_assert(hb->realSzB > 0);
+ tl_assert(hb->fakeSzB == hb->realSzB);
+ }
+ if (hb && !rangesOverlap(ea, szB, hb->addr, hb->realSzB))
+ hb = NULL;
+ if (hb) {
+ inv->tag = Inv_Heap;
+ inv->Inv.Heap.start = hb->addr;
+ inv->Inv.Heap.len = hb->realSzB;
+ stats__classify_Heap++;
+ return;
+ }
+ }
+ /* Not in a stack block. Try the global pool. */
+ { GlobalBlock* gb2 = find_GlobalBlock_containing(ea);
+ /* We know that [ea,ea+1) is in the block, but we need to
+ restrict to the case where the whole access falls within
+ it. */
+ if (gb2 && !rangesOverlap(ea, szB, gb2->addr, gb2->szB)) {
+ gb2 = NULL;
+ }
+ if (gb2) {
+ inv->tag = gb2->isVec ? Inv_GlobalV : Inv_GlobalS;
+ tl_assert(sizeof(gb2->name) == sizeof(inv->Inv.Global.name));
+ tl_assert(sizeof(gb2->soname) == sizeof(inv->Inv.Global.soname));
+ VG_(memcpy)( &inv->Inv.Global.name[0],
+ gb2->name, sizeof(gb2->name) );
+ VG_(memcpy)( &inv->Inv.Global.soname[0],
+ gb2->soname, sizeof(gb2->soname) );
+ inv->Inv.Global.start = gb2->addr;
+ inv->Inv.Global.len = gb2->szB;
+ stats__classify_Global++;
+ return;
+ }
+ }
+ /* Ok, so it's not a block in the top frame. Perhaps it's a block
+ in some calling frame? Work back down the stack to see if it's
+ an access to an array in any calling frame. */
+ {
+ UWord ix;
+ Bool isVec, b;
+ Addr blockEA;
+ SizeT blockSzB;
+ HChar* name;
+ Word n, i; /* i must remain signed */
+ StackFrame* frame;
+ n = VG_(sizeXA)( thisThreadFrames );
+ tl_assert(n > 0);
+ if (0) VG_(printf)("n = %ld\n", n);
+ i = n - 2;
+ while (1) {
+ if (i < 0) break;
+ frame = VG_(indexXA)( thisThreadFrames, i );
+ if (frame->blocks_at_call == NULL) { i--; continue; }
+ if (0) VG_(printf)("considering %ld\n", i);
+ b = find_in_StackBlocks(
+ &ix, &isVec, &blockEA, &blockSzB, &name,
+ ea, frame->sp_at_call, frame->fp_at_call, szB,
+ frame->blocks_at_call
+ );
+ if (b) {
+ SizeT nameSzB = sizeof(inv->Inv.Stack.name);
+ inv->tag = isVec ? Inv_StackV : Inv_StackS;
+ inv->Inv.Stack.framesBack = n - i - 1;;
+ inv->Inv.Stack.fbIndex = ix;
+ inv->Inv.Stack.start = blockEA;
+ inv->Inv.Stack.len = blockSzB;
+ VG_(memcpy)( &inv->Inv.Stack.name[0], name, nameSzB );
+ inv->Inv.Stack.name[ nameSzB-1 ] = 0;
+ stats__classify_Stack++;
+ return;
+ }
+ if (i == 0) break;
+ i--;
+ }
+ }
+ /* No idea - give up. We have to say it's Unknown. Note that this
+ is highly undesirable because it means we can't cache any ReVal
+ info, and so we have to do this very slow path for every access
+ made by this instruction-instance. That's why we make big
+ efforts to classify all instructions -- once classified, we can
+ do cheap ReVal checks for second and subsequent accesses. */
+ inv->tag = Inv_Unknown;
+ stats__classify_Unknown++;
+}
+
+
+/* CALLED FROM GENERATED CODE */
+static
+VG_REGPARM(3)
+void helperc__mem_access ( /* Known only at run time: */
+ Addr ea, Addr sp, Addr fp,
+ /* Known at translation time: */
+ Word sszB, Addr ip, XArray* ip_frameBlocks )
+{
+ Word n;
+ UWord szB;
+ XArray* /* of StackFrame */ frames;
+ IInstance* iinstance;
+ Invar* inv;
+ Invar new_inv;
+ ThreadId tid = VG_(get_running_tid)();
+ StackFrame* frame;
+ HChar buf[160];
+
+ stats__total_accesses++;
+
+ tl_assert(is_sane_TId(tid));
+ frames = shadowStacks[tid];
+ tl_assert(frames != NULL);
+ n = VG_(sizeXA)( frames );
+ tl_assert(n > 0);
+
+ frame = VG_(indexXA)( frames, n-1 );
+
+ /* Find the instance info for this instruction. */
+ tl_assert(ip_frameBlocks);
+ iinstance = find_or_create_IInstance( frame, ip, ip_frameBlocks );
+ tl_assert(iinstance);
+ tl_assert(iinstance->blocks == ip_frameBlocks);
+
+ szB = (sszB < 0) ? (-sszB) : sszB;
+ tl_assert(szB > 0);
+
+ inv = &iinstance->invar;
+
+ /* Deal with first uses of instruction instances. We hope this is
+ rare, because it's expensive. */
+ if (inv->tag == Inv_Unset) {
+ /* This is the first use of this instance of the instruction, so
+ we can't make any check; we merely record what we saw, so we
+ can compare it against what happens for 2nd and subsequent
+ accesses. */
+ classify_address( inv,
+ tid, ea, sp, fp, szB,
+ iinstance->blocks, frames );
+ tl_assert(inv->tag != Inv_Unset);
+ return;
+ }
+
+ /* Now, try to re-validate (ReVal). What that means is, quickly
+ establish whether or not this instruction is accessing the same
+ block as it was last time. We hope this is the common, fast
+ case. */
+ switch (inv->tag) {
+ case Inv_StackS:
+ case Inv_StackV:
+ if (inv->Inv.Stack.start <= ea
+ && ea + szB <= inv->Inv.Stack.start + inv->Inv.Stack.len) {
+ stats__reval_Stack++;
+ return; /* yay! */
+ }
+ break; /* boo! */
+ case Inv_GlobalS:
+ case Inv_GlobalV:
+ if (inv->Inv.Global.start <= ea
+ && ea + szB <= inv->Inv.Global.start + inv->Inv.Global.len) {
+ stats__reval_Global++;
+ return; /* yay! */
+ }
+ break; /* boo! */
+ case Inv_Heap:
+ if (inv->Inv.Heap.start <= ea
+ && ea + szB <= inv->Inv.Heap.start + inv->Inv.Heap.len) {
+ stats__reval_Heap++;
+ return; /* yay! */
+ }
+ break; /* boo! */
+ case Inv_Unknown:
+ break; /* boo! */
+ /* this is the undesirable case. If the instruction has
+ previously been poking around some place we can't account
+ for, we have to laboriously check all the many places
+ (blocks) we do know about, to check it hasn't transitioned
+ into any of them. */
+ default:
+ tl_assert(0);
+ }
+
+ /* We failed to quickly establish that the instruction is poking
+ around in the same block it was before. So we have to do it the
+ hard way: generate a full description (Invar) of this access,
+ and compare it to the previous Invar, to see if there are really
+ any differences. Note that we will be on this code path if the
+ program has made any invalid transitions, and so we may emit
+ error messages in the code below. */
+ classify_address( &new_inv,
+ tid, ea, sp, fp, szB,
+ iinstance->blocks, frames );
+ tl_assert(new_inv.tag != Inv_Unset);
+
+ /* Did we see something different from before? If no, then there's
+ no error. */
+ if (eq_Invar(&new_inv, inv))
+ return;
+
+ /* The new and old Invars really are different. So report an
+ error. */
+ { Bool v_old = inv->tag == Inv_StackV || inv->tag == Inv_GlobalV;
+ Bool v_new = new_inv.tag == Inv_StackV || new_inv.tag == Inv_GlobalV;
+ if ( (v_old || v_new) && new_inv.tag != inv->tag) {
+ } else {
+ goto noerror;
+ }
+ }
+
+ VG_(message)(Vg_UserMsg, "");
+ VG_(message)(Vg_UserMsg, "Invalid %s of size %lu",
+ sszB < 0 ? "write" : "read", szB );
+ VG_(pp_ExeContext)(
+ VG_(record_ExeContext)( tid, 0/*first_ip_delta*/ ) );
+ // VG_(record_depth_1_ExeContext)( tid ) );
+
+ VG_(message)(Vg_UserMsg, " Address %#lx expected vs actual:", ea);
+
+ VG_(memset)(buf, 0, sizeof(buf));
+ show_Invar( buf, sizeof(buf)-1, inv );
+ VG_(message)(Vg_UserMsg, " Expected: %s", buf );
+
+ VG_(memset)(buf, 0, sizeof(buf));
+ show_Invar( buf, sizeof(buf)-1, &new_inv );
+ VG_(message)(Vg_UserMsg, " Actual: %s", buf );
+
+ noerror:
+ /* And now install the new observation as "standard", so as to
+ make future error messages make more sense. */
+ *inv = new_inv;
+}
+
+
+////////////////////////////////////////
+/* Primary push-a-new-frame routine. Called indirec...
[truncated message content] |