sg_main.c revision b3a1e4bffbdbbf38304f216af405009868f43628
1024598e40c84666cc311a42c256bbf880db3ac99sewardj 2024598e40c84666cc311a42c256bbf880db3ac99sewardj/*--------------------------------------------------------------------*/ 3024598e40c84666cc311a42c256bbf880db3ac99sewardj/*--- Ptrcheck: a pointer-use checker. ---*/ 4024598e40c84666cc311a42c256bbf880db3ac99sewardj/*--- This file checks stack and global array accesses. ---*/ 5024598e40c84666cc311a42c256bbf880db3ac99sewardj/*--- sg_main.c ---*/ 6024598e40c84666cc311a42c256bbf880db3ac99sewardj/*--------------------------------------------------------------------*/ 7024598e40c84666cc311a42c256bbf880db3ac99sewardj 8024598e40c84666cc311a42c256bbf880db3ac99sewardj/* 9024598e40c84666cc311a42c256bbf880db3ac99sewardj This file is part of Ptrcheck, a Valgrind tool for checking pointer 10024598e40c84666cc311a42c256bbf880db3ac99sewardj use in programs. 11024598e40c84666cc311a42c256bbf880db3ac99sewardj 12b3a1e4bffbdbbf38304f216af405009868f43628sewardj Copyright (C) 2008-2015 OpenWorks Ltd 13024598e40c84666cc311a42c256bbf880db3ac99sewardj info@open-works.co.uk 14024598e40c84666cc311a42c256bbf880db3ac99sewardj 15024598e40c84666cc311a42c256bbf880db3ac99sewardj This program is free software; you can redistribute it and/or 16024598e40c84666cc311a42c256bbf880db3ac99sewardj modify it under the terms of the GNU General Public License as 17024598e40c84666cc311a42c256bbf880db3ac99sewardj published by the Free Software Foundation; either version 2 of the 18024598e40c84666cc311a42c256bbf880db3ac99sewardj License, or (at your option) any later version. 19024598e40c84666cc311a42c256bbf880db3ac99sewardj 20024598e40c84666cc311a42c256bbf880db3ac99sewardj This program is distributed in the hope that it will be useful, but 21024598e40c84666cc311a42c256bbf880db3ac99sewardj WITHOUT ANY WARRANTY; without even the implied warranty of 22024598e40c84666cc311a42c256bbf880db3ac99sewardj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 23024598e40c84666cc311a42c256bbf880db3ac99sewardj General Public License for more details. 24024598e40c84666cc311a42c256bbf880db3ac99sewardj 25024598e40c84666cc311a42c256bbf880db3ac99sewardj You should have received a copy of the GNU General Public License 26024598e40c84666cc311a42c256bbf880db3ac99sewardj along with this program; if not, write to the Free Software 27024598e40c84666cc311a42c256bbf880db3ac99sewardj Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 28024598e40c84666cc311a42c256bbf880db3ac99sewardj 02111-1307, USA. 29024598e40c84666cc311a42c256bbf880db3ac99sewardj 30024598e40c84666cc311a42c256bbf880db3ac99sewardj The GNU General Public License is contained in the file COPYING. 31024598e40c84666cc311a42c256bbf880db3ac99sewardj 32024598e40c84666cc311a42c256bbf880db3ac99sewardj Neither the names of the U.S. Department of Energy nor the 33024598e40c84666cc311a42c256bbf880db3ac99sewardj University of California nor the names of its contributors may be 34024598e40c84666cc311a42c256bbf880db3ac99sewardj used to endorse or promote products derived from this software 35024598e40c84666cc311a42c256bbf880db3ac99sewardj without prior written permission. 36024598e40c84666cc311a42c256bbf880db3ac99sewardj*/ 37024598e40c84666cc311a42c256bbf880db3ac99sewardj 38024598e40c84666cc311a42c256bbf880db3ac99sewardj#include "pub_tool_basics.h" 39024598e40c84666cc311a42c256bbf880db3ac99sewardj#include "pub_tool_libcbase.h" 40024598e40c84666cc311a42c256bbf880db3ac99sewardj#include "pub_tool_libcassert.h" 41024598e40c84666cc311a42c256bbf880db3ac99sewardj#include "pub_tool_libcprint.h" 42024598e40c84666cc311a42c256bbf880db3ac99sewardj#include "pub_tool_tooliface.h" 43024598e40c84666cc311a42c256bbf880db3ac99sewardj#include "pub_tool_wordfm.h" 44024598e40c84666cc311a42c256bbf880db3ac99sewardj#include "pub_tool_xarray.h" 45024598e40c84666cc311a42c256bbf880db3ac99sewardj#include "pub_tool_threadstate.h" 46024598e40c84666cc311a42c256bbf880db3ac99sewardj#include "pub_tool_mallocfree.h" 47024598e40c84666cc311a42c256bbf880db3ac99sewardj#include "pub_tool_machine.h" 48024598e40c84666cc311a42c256bbf880db3ac99sewardj#include "pub_tool_debuginfo.h" 49024598e40c84666cc311a42c256bbf880db3ac99sewardj#include "pub_tool_options.h" 50024598e40c84666cc311a42c256bbf880db3ac99sewardj 51024598e40c84666cc311a42c256bbf880db3ac99sewardj#include "pc_common.h" 52024598e40c84666cc311a42c256bbf880db3ac99sewardj 53024598e40c84666cc311a42c256bbf880db3ac99sewardj#include "sg_main.h" // self 54024598e40c84666cc311a42c256bbf880db3ac99sewardj 55024598e40c84666cc311a42c256bbf880db3ac99sewardj 56024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic 579e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardjvoid preen_global_Invars ( Addr a, SizeT len ); /*fwds*/ 58024598e40c84666cc311a42c256bbf880db3ac99sewardj 59024598e40c84666cc311a42c256bbf880db3ac99sewardj 60024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 61024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 62024598e40c84666cc311a42c256bbf880db3ac99sewardj// Basic Stuff // 63024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 64024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 65024598e40c84666cc311a42c256bbf880db3ac99sewardj 66024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic inline Bool is_sane_TId ( ThreadId tid ) 67024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 68024598e40c84666cc311a42c256bbf880db3ac99sewardj return tid >= 0 && tid < VG_N_THREADS 69024598e40c84666cc311a42c256bbf880db3ac99sewardj && tid != VG_INVALID_THREADID; 70024598e40c84666cc311a42c256bbf880db3ac99sewardj} 71024598e40c84666cc311a42c256bbf880db3ac99sewardj 7254fe2021b87b9e5edb8ec8070f47b86d5cafb8aaflorianstatic void* sg_malloc ( const HChar* cc, SizeT n ) { 73024598e40c84666cc311a42c256bbf880db3ac99sewardj void* p; 74024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(n > 0); 75024598e40c84666cc311a42c256bbf880db3ac99sewardj p = VG_(malloc)( cc, n ); 76024598e40c84666cc311a42c256bbf880db3ac99sewardj return p; 77024598e40c84666cc311a42c256bbf880db3ac99sewardj} 78024598e40c84666cc311a42c256bbf880db3ac99sewardj 79024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void sg_free ( void* p ) { 80024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(p); 81024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(free)(p); 82024598e40c84666cc311a42c256bbf880db3ac99sewardj} 83024598e40c84666cc311a42c256bbf880db3ac99sewardj 84024598e40c84666cc311a42c256bbf880db3ac99sewardj 85024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Compare the intervals [a1,a1+n1) and [a2,a2+n2). Return -1 if the 86024598e40c84666cc311a42c256bbf880db3ac99sewardj first interval is lower, 1 if the first interval is higher, and 0 87024598e40c84666cc311a42c256bbf880db3ac99sewardj if there is any overlap. Redundant paranoia with casting is there 88024598e40c84666cc311a42c256bbf880db3ac99sewardj following what looked distinctly like a bug in gcc-4.1.2, in which 89024598e40c84666cc311a42c256bbf880db3ac99sewardj some of the comparisons were done signedly instead of 90024598e40c84666cc311a42c256bbf880db3ac99sewardj unsignedly. */ 91024598e40c84666cc311a42c256bbf880db3ac99sewardjinline 92024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic Word cmp_nonempty_intervals ( Addr a1, SizeT n1, 93024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr a2, SizeT n2 ) { 94024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord a1w = (UWord)a1; 95024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord n1w = (UWord)n1; 96024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord a2w = (UWord)a2; 97024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord n2w = (UWord)n2; 98024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(n1w > 0 && n2w > 0); 99024598e40c84666cc311a42c256bbf880db3ac99sewardj if (a1w + n1w <= a2w) return -1L; 100024598e40c84666cc311a42c256bbf880db3ac99sewardj if (a2w + n2w <= a1w) return 1L; 101024598e40c84666cc311a42c256bbf880db3ac99sewardj return 0; 102024598e40c84666cc311a42c256bbf880db3ac99sewardj} 103024598e40c84666cc311a42c256bbf880db3ac99sewardj 104024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Return true iff [aSmall,aSmall+nSmall) is entirely contained 105024598e40c84666cc311a42c256bbf880db3ac99sewardj within [aBig,aBig+nBig). */ 106024598e40c84666cc311a42c256bbf880db3ac99sewardjinline 107024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic Bool is_subinterval_of ( Addr aBig, SizeT nBig, 108024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr aSmall, SizeT nSmall ) { 109024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(nBig > 0 && nSmall > 0); 110024598e40c84666cc311a42c256bbf880db3ac99sewardj return aBig <= aSmall && aSmall + nSmall <= aBig + nBig; 111024598e40c84666cc311a42c256bbf880db3ac99sewardj} 112024598e40c84666cc311a42c256bbf880db3ac99sewardj 113024598e40c84666cc311a42c256bbf880db3ac99sewardjinline 114024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic Addr Addr__min ( Addr a1, Addr a2 ) { 115024598e40c84666cc311a42c256bbf880db3ac99sewardj return a1 < a2 ? a1 : a2; 116024598e40c84666cc311a42c256bbf880db3ac99sewardj} 117024598e40c84666cc311a42c256bbf880db3ac99sewardj 118024598e40c84666cc311a42c256bbf880db3ac99sewardjinline 119024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic Addr Addr__max ( Addr a1, Addr a2 ) { 120024598e40c84666cc311a42c256bbf880db3ac99sewardj return a1 < a2 ? a2 : a1; 121024598e40c84666cc311a42c256bbf880db3ac99sewardj} 122024598e40c84666cc311a42c256bbf880db3ac99sewardj 123024598e40c84666cc311a42c256bbf880db3ac99sewardj 124024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 125024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 126024598e40c84666cc311a42c256bbf880db3ac99sewardj// StackBlocks Persistent Cache // 127024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 128024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 129024598e40c84666cc311a42c256bbf880db3ac99sewardj 130024598e40c84666cc311a42c256bbf880db3ac99sewardj/* We maintain a set of XArray* of StackBlocks. These are never 131024598e40c84666cc311a42c256bbf880db3ac99sewardj freed. When a new StackBlock vector is acquired from 132024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(di_get_local_blocks_at_ip), we compare it to the existing set. 133024598e40c84666cc311a42c256bbf880db3ac99sewardj If not present, it is added. If present, the just-acquired one is 134024598e40c84666cc311a42c256bbf880db3ac99sewardj freed and the copy used. 135024598e40c84666cc311a42c256bbf880db3ac99sewardj 136024598e40c84666cc311a42c256bbf880db3ac99sewardj This simplifies storage management elsewhere. It allows us to 137024598e40c84666cc311a42c256bbf880db3ac99sewardj assume that a pointer to an XArray* of StackBlock is valid forever. 138024598e40c84666cc311a42c256bbf880db3ac99sewardj It also means there are no duplicates anywhere, which could be 139024598e40c84666cc311a42c256bbf880db3ac99sewardj important from a space point of view for programs that generate a 140024598e40c84666cc311a42c256bbf880db3ac99sewardj lot of translations, or where translations are frequently discarded 141024598e40c84666cc311a42c256bbf880db3ac99sewardj and re-made. 142024598e40c84666cc311a42c256bbf880db3ac99sewardj 143024598e40c84666cc311a42c256bbf880db3ac99sewardj Note that we normalise the arrays by sorting the elements according 144024598e40c84666cc311a42c256bbf880db3ac99sewardj to an arbitrary total order, so as to avoid the situation that two 145024598e40c84666cc311a42c256bbf880db3ac99sewardj vectors describe the same set of variables but are not structurally 146024598e40c84666cc311a42c256bbf880db3ac99sewardj identical. */ 147024598e40c84666cc311a42c256bbf880db3ac99sewardj 1486bd9dc18c043927c1196caba20a327238a179c42florianstatic inline Bool StackBlock__sane ( const StackBlock* fb ) 149024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 150024598e40c84666cc311a42c256bbf880db3ac99sewardj if (fb->name[ sizeof(fb->name)-1 ] != 0) 151024598e40c84666cc311a42c256bbf880db3ac99sewardj return False; 152024598e40c84666cc311a42c256bbf880db3ac99sewardj if (fb->spRel != False && fb->spRel != True) 153024598e40c84666cc311a42c256bbf880db3ac99sewardj return False; 154024598e40c84666cc311a42c256bbf880db3ac99sewardj if (fb->isVec != False && fb->isVec != True) 155024598e40c84666cc311a42c256bbf880db3ac99sewardj return False; 156024598e40c84666cc311a42c256bbf880db3ac99sewardj return True; 157024598e40c84666cc311a42c256bbf880db3ac99sewardj} 158024598e40c84666cc311a42c256bbf880db3ac99sewardj 159024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Generate an arbitrary total ordering on StackBlocks. */ 1606bd9dc18c043927c1196caba20a327238a179c42florianstatic Word StackBlock__cmp ( const StackBlock* fb1, const StackBlock* fb2 ) 161024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 162024598e40c84666cc311a42c256bbf880db3ac99sewardj Word r; 163024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(StackBlock__sane(fb1)); 164024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(StackBlock__sane(fb2)); 165024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Hopefully the .base test hits most of the time. For the blocks 166024598e40c84666cc311a42c256bbf880db3ac99sewardj associated with any particular instruction, if the .base values 167024598e40c84666cc311a42c256bbf880db3ac99sewardj are the same then probably it doesn't make sense for the other 168024598e40c84666cc311a42c256bbf880db3ac99sewardj fields to be different. But this is supposed to be a completely 169024598e40c84666cc311a42c256bbf880db3ac99sewardj general structural total order, so we have to compare everything 170024598e40c84666cc311a42c256bbf880db3ac99sewardj anyway. */ 171024598e40c84666cc311a42c256bbf880db3ac99sewardj if (fb1->base < fb2->base) return -1; 172024598e40c84666cc311a42c256bbf880db3ac99sewardj if (fb1->base > fb2->base) return 1; 173024598e40c84666cc311a42c256bbf880db3ac99sewardj /* compare sizes */ 174024598e40c84666cc311a42c256bbf880db3ac99sewardj if (fb1->szB < fb2->szB) return -1; 175024598e40c84666cc311a42c256bbf880db3ac99sewardj if (fb1->szB > fb2->szB) return 1; 176024598e40c84666cc311a42c256bbf880db3ac99sewardj /* compare sp/fp flag */ 177024598e40c84666cc311a42c256bbf880db3ac99sewardj if (fb1->spRel < fb2->spRel) return -1; 178024598e40c84666cc311a42c256bbf880db3ac99sewardj if (fb1->spRel > fb2->spRel) return 1; 179024598e40c84666cc311a42c256bbf880db3ac99sewardj /* compare is/is-not array-typed flag */ 180024598e40c84666cc311a42c256bbf880db3ac99sewardj if (fb1->isVec < fb2->isVec) return -1; 181024598e40c84666cc311a42c256bbf880db3ac99sewardj if (fb1->isVec > fb2->isVec) return 1; 182024598e40c84666cc311a42c256bbf880db3ac99sewardj /* compare the name */ 183024598e40c84666cc311a42c256bbf880db3ac99sewardj r = (Word)VG_(strcmp)(fb1->name, fb2->name); 184024598e40c84666cc311a42c256bbf880db3ac99sewardj return r; 185024598e40c84666cc311a42c256bbf880db3ac99sewardj} 186024598e40c84666cc311a42c256bbf880db3ac99sewardj 187024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Returns True if all fields except .szB are the same. szBs may or 188024598e40c84666cc311a42c256bbf880db3ac99sewardj may not be the same; they are simply not consulted. */ 189024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic Bool StackBlock__all_fields_except_szB_are_equal ( 190024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock* fb1, 191024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock* fb2 192024598e40c84666cc311a42c256bbf880db3ac99sewardj ) 193024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 194024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(StackBlock__sane(fb1)); 195024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(StackBlock__sane(fb2)); 196024598e40c84666cc311a42c256bbf880db3ac99sewardj return fb1->base == fb2->base 197024598e40c84666cc311a42c256bbf880db3ac99sewardj && fb1->spRel == fb2->spRel 198024598e40c84666cc311a42c256bbf880db3ac99sewardj && fb1->isVec == fb2->isVec 199024598e40c84666cc311a42c256bbf880db3ac99sewardj && 0 == VG_(strcmp)(fb1->name, fb2->name); 200024598e40c84666cc311a42c256bbf880db3ac99sewardj} 201024598e40c84666cc311a42c256bbf880db3ac99sewardj 202024598e40c84666cc311a42c256bbf880db3ac99sewardj 203024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Generate an arbitrary total ordering on vectors of StackBlocks. */ 204024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic Word StackBlocks__cmp ( XArray* fb1s, XArray* fb2s ) 205024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 206024598e40c84666cc311a42c256bbf880db3ac99sewardj Word i, r, n1, n2; 207024598e40c84666cc311a42c256bbf880db3ac99sewardj n1 = VG_(sizeXA)( fb1s ); 208024598e40c84666cc311a42c256bbf880db3ac99sewardj n2 = VG_(sizeXA)( fb2s ); 209024598e40c84666cc311a42c256bbf880db3ac99sewardj if (n1 < n2) return -1; 210024598e40c84666cc311a42c256bbf880db3ac99sewardj if (n1 > n2) return 1; 211024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < n1; i++) { 212024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock *fb1, *fb2; 213024598e40c84666cc311a42c256bbf880db3ac99sewardj fb1 = VG_(indexXA)( fb1s, i ); 214024598e40c84666cc311a42c256bbf880db3ac99sewardj fb2 = VG_(indexXA)( fb2s, i ); 215024598e40c84666cc311a42c256bbf880db3ac99sewardj r = StackBlock__cmp( fb1, fb2 ); 216024598e40c84666cc311a42c256bbf880db3ac99sewardj if (r != 0) return r; 217024598e40c84666cc311a42c256bbf880db3ac99sewardj } 218024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(i == n1 && i == n2); 219024598e40c84666cc311a42c256bbf880db3ac99sewardj return 0; 220024598e40c84666cc311a42c256bbf880db3ac99sewardj} 221024598e40c84666cc311a42c256bbf880db3ac99sewardj 222024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void pp_StackBlocks ( XArray* sbs ) 223024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 224024598e40c84666cc311a42c256bbf880db3ac99sewardj Word i, n = VG_(sizeXA)( sbs ); 225c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj VG_(message)(Vg_DebugMsg, "<<< STACKBLOCKS\n" ); 226024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < n; i++) { 227f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj StackBlock* sb = (StackBlock*)VG_(indexXA)( sbs, i ); 228f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj VG_(message)(Vg_DebugMsg, 229c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj " StackBlock{ off %ld szB %lu spRel:%c isVec:%c \"%s\" }\n", 230f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj sb->base, sb->szB, sb->spRel ? 'Y' : 'N', 231f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj sb->isVec ? 'Y' : 'N', &sb->name[0] 232f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj ); 233024598e40c84666cc311a42c256bbf880db3ac99sewardj } 234c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj VG_(message)(Vg_DebugMsg, ">>> STACKBLOCKS\n" ); 235024598e40c84666cc311a42c256bbf880db3ac99sewardj} 236024598e40c84666cc311a42c256bbf880db3ac99sewardj 237024598e40c84666cc311a42c256bbf880db3ac99sewardj 238024598e40c84666cc311a42c256bbf880db3ac99sewardj/* ---------- The StackBlock vector cache ---------- */ 239024598e40c84666cc311a42c256bbf880db3ac99sewardj 240024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic WordFM* /* XArray* of StackBlock -> nothing */ 241024598e40c84666cc311a42c256bbf880db3ac99sewardj frameBlocks_set = NULL; 242024598e40c84666cc311a42c256bbf880db3ac99sewardj 243024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void init_StackBlocks_set ( void ) 244024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 245024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(!frameBlocks_set); 246024598e40c84666cc311a42c256bbf880db3ac99sewardj frameBlocks_set 247024598e40c84666cc311a42c256bbf880db3ac99sewardj = VG_(newFM)( sg_malloc, "di.sg_main.iSBs.1", sg_free, 248024598e40c84666cc311a42c256bbf880db3ac99sewardj (Word(*)(UWord,UWord))StackBlocks__cmp ); 249024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(frameBlocks_set); 250024598e40c84666cc311a42c256bbf880db3ac99sewardj} 251024598e40c84666cc311a42c256bbf880db3ac99sewardj 252024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Find the given StackBlock-vector in our collection thereof. If 253024598e40c84666cc311a42c256bbf880db3ac99sewardj found, deallocate the supplied one, and return the address of the 254024598e40c84666cc311a42c256bbf880db3ac99sewardj copy. If not found, add the supplied one to our collection and 255024598e40c84666cc311a42c256bbf880db3ac99sewardj return its address. */ 256024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic XArray* /* of StackBlock */ 257024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlocks__find_and_dealloc__or_add 258024598e40c84666cc311a42c256bbf880db3ac99sewardj ( XArray* /* of StackBlock */ orig ) 259024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 260024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord key, val; 261024598e40c84666cc311a42c256bbf880db3ac99sewardj 262024598e40c84666cc311a42c256bbf880db3ac99sewardj /* First, normalise, as per comments above. */ 2636bd9dc18c043927c1196caba20a327238a179c42florian VG_(setCmpFnXA)( orig, (XACmpFn_t)StackBlock__cmp ); 264024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(sortXA)( orig ); 265024598e40c84666cc311a42c256bbf880db3ac99sewardj 266024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Now get rid of any exact duplicates. */ 267024598e40c84666cc311a42c256bbf880db3ac99sewardj nuke_dups: 268024598e40c84666cc311a42c256bbf880db3ac99sewardj { Word r, w, nEQ, n = VG_(sizeXA)( orig ); 269024598e40c84666cc311a42c256bbf880db3ac99sewardj if (n >= 2) { 270024598e40c84666cc311a42c256bbf880db3ac99sewardj w = 0; 271024598e40c84666cc311a42c256bbf880db3ac99sewardj nEQ = 0; 272024598e40c84666cc311a42c256bbf880db3ac99sewardj for (r = 0; r < n; r++) { 273024598e40c84666cc311a42c256bbf880db3ac99sewardj if (r+1 < n) { 274024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock* pR0 = VG_(indexXA)( orig, r+0 ); 275024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock* pR1 = VG_(indexXA)( orig, r+1 ); 276024598e40c84666cc311a42c256bbf880db3ac99sewardj Word c = StackBlock__cmp(pR0,pR1); 277024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(c == -1 || c == 0); 278024598e40c84666cc311a42c256bbf880db3ac99sewardj if (c == 0) { nEQ++; continue; } 279024598e40c84666cc311a42c256bbf880db3ac99sewardj } 280024598e40c84666cc311a42c256bbf880db3ac99sewardj if (w != r) { 281024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock* pW = VG_(indexXA)( orig, w ); 282024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock* pR = VG_(indexXA)( orig, r ); 283024598e40c84666cc311a42c256bbf880db3ac99sewardj *pW = *pR; 284024598e40c84666cc311a42c256bbf880db3ac99sewardj } 285024598e40c84666cc311a42c256bbf880db3ac99sewardj w++; 286024598e40c84666cc311a42c256bbf880db3ac99sewardj } 287024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(r == n); 288024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(w + nEQ == n); 289024598e40c84666cc311a42c256bbf880db3ac99sewardj if (w < n) { 290024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(dropTailXA)( orig, n-w ); 291024598e40c84666cc311a42c256bbf880db3ac99sewardj } 292024598e40c84666cc311a42c256bbf880db3ac99sewardj if (0) VG_(printf)("delta %ld\n", n-w); 293024598e40c84666cc311a42c256bbf880db3ac99sewardj } 294024598e40c84666cc311a42c256bbf880db3ac99sewardj } 295024598e40c84666cc311a42c256bbf880db3ac99sewardj 296024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Deal with the following strangeness, where two otherwise 297024598e40c84666cc311a42c256bbf880db3ac99sewardj identical blocks are claimed to have different sizes. In which 298024598e40c84666cc311a42c256bbf880db3ac99sewardj case we use the larger size. */ 299024598e40c84666cc311a42c256bbf880db3ac99sewardj /* StackBlock{ off 16 szB 66 spRel:Y isVec:Y "sz" } 300024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock{ off 16 szB 130 spRel:Y isVec:Y "sz" } 301024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock{ off 208 szB 16 spRel:Y isVec:Y "ar" } 302024598e40c84666cc311a42c256bbf880db3ac99sewardj */ 303024598e40c84666cc311a42c256bbf880db3ac99sewardj { Word i, n = VG_(sizeXA)( orig ); 304024598e40c84666cc311a42c256bbf880db3ac99sewardj if (n >= 2) { 305024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < n-1; i++) { 306024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock* sb0 = VG_(indexXA)( orig, i+0 ); 307024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock* sb1 = VG_(indexXA)( orig, i+1 ); 308024598e40c84666cc311a42c256bbf880db3ac99sewardj if (StackBlock__all_fields_except_szB_are_equal(sb0, sb1)) { 309024598e40c84666cc311a42c256bbf880db3ac99sewardj /* They can't be identical because the previous tidying 310024598e40c84666cc311a42c256bbf880db3ac99sewardj pass would have removed the duplicates. And they 311024598e40c84666cc311a42c256bbf880db3ac99sewardj can't be > because the earlier sorting pass would 312024598e40c84666cc311a42c256bbf880db3ac99sewardj have ordered otherwise-identical descriptors 313024598e40c84666cc311a42c256bbf880db3ac99sewardj according to < on .szB fields. Hence: */ 314024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(sb0->szB < sb1->szB); 315024598e40c84666cc311a42c256bbf880db3ac99sewardj sb0->szB = sb1->szB; 316024598e40c84666cc311a42c256bbf880db3ac99sewardj /* This makes the blocks identical, at the size of the 317024598e40c84666cc311a42c256bbf880db3ac99sewardj larger one. Rather than go to all the hassle of 318024598e40c84666cc311a42c256bbf880db3ac99sewardj sliding the rest down, simply go back to the 319024598e40c84666cc311a42c256bbf880db3ac99sewardj remove-duplicates stage. The assertion guarantees 320024598e40c84666cc311a42c256bbf880db3ac99sewardj that we eventually make progress, since the rm-dups 321024598e40c84666cc311a42c256bbf880db3ac99sewardj stage will get rid of one of the blocks. This is 322024598e40c84666cc311a42c256bbf880db3ac99sewardj expected to happen only exceedingly rarely. */ 323024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(StackBlock__cmp(sb0,sb1) == 0); 324024598e40c84666cc311a42c256bbf880db3ac99sewardj goto nuke_dups; 325024598e40c84666cc311a42c256bbf880db3ac99sewardj } 326024598e40c84666cc311a42c256bbf880db3ac99sewardj } 327024598e40c84666cc311a42c256bbf880db3ac99sewardj } 328024598e40c84666cc311a42c256bbf880db3ac99sewardj } 329024598e40c84666cc311a42c256bbf880db3ac99sewardj 330f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj /* If there are any blocks which overlap and have the same 331f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj fpRel-ness, junk the whole descriptor; it's obviously bogus. 332f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj Icc11 certainly generates bogus info from time to time. 333f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj 334f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj This check is pretty weak; really we ought to have a stronger 335f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj sanity check. */ 336024598e40c84666cc311a42c256bbf880db3ac99sewardj { Word i, n = VG_(sizeXA)( orig ); 337f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj static Int moans = 3; 338024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < n-1; i++) { 339024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock* sb1 = (StackBlock*)VG_(indexXA)( orig, i ); 340024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock* sb2 = (StackBlock*)VG_(indexXA)( orig, i+1 ); 341f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj if (sb1->spRel == sb2->spRel 342f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj && (sb1->base >= sb2->base 343f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj || sb1->base + sb1->szB > sb2->base)) { 344f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj if (moans > 0 && !VG_(clo_xml)) { 345f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj moans--; 346f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj VG_(message)(Vg_UserMsg, "Warning: bogus DWARF3 info: " 347c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj "overlapping stack blocks\n"); 348f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj if (VG_(clo_verbosity) >= 2) 349f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj pp_StackBlocks(orig); 350f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj if (moans == 0) 351f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj VG_(message)(Vg_UserMsg, "Further instances of this " 352c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj "message will not be shown\n" ); 353f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj } 354f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj VG_(dropTailXA)( orig, VG_(sizeXA)( orig )); 355f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj break; 356f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj } 357024598e40c84666cc311a42c256bbf880db3ac99sewardj } 358024598e40c84666cc311a42c256bbf880db3ac99sewardj } 359024598e40c84666cc311a42c256bbf880db3ac99sewardj 360024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Now, do we have it already? */ 361024598e40c84666cc311a42c256bbf880db3ac99sewardj if (VG_(lookupFM)( frameBlocks_set, &key, &val, (UWord)orig )) { 362024598e40c84666cc311a42c256bbf880db3ac99sewardj /* yes */ 363024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* res; 364024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(val == 0); 365024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(key != (UWord)orig); 366024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(deleteXA)(orig); 367024598e40c84666cc311a42c256bbf880db3ac99sewardj res = (XArray*)key; 368024598e40c84666cc311a42c256bbf880db3ac99sewardj return res; 369024598e40c84666cc311a42c256bbf880db3ac99sewardj } else { 370024598e40c84666cc311a42c256bbf880db3ac99sewardj /* no */ 371024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(addToFM)( frameBlocks_set, (UWord)orig, 0 ); 372024598e40c84666cc311a42c256bbf880db3ac99sewardj return orig; 373024598e40c84666cc311a42c256bbf880db3ac99sewardj } 374024598e40c84666cc311a42c256bbf880db3ac99sewardj} 375024598e40c84666cc311a42c256bbf880db3ac99sewardj 376024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Top level function for getting the StackBlock vector for a given 377024598e40c84666cc311a42c256bbf880db3ac99sewardj instruction. It is guaranteed that the returned pointer will be 378024598e40c84666cc311a42c256bbf880db3ac99sewardj valid for the entire rest of the run, and also that the addresses 379024598e40c84666cc311a42c256bbf880db3ac99sewardj of the individual elements of the array will not change. */ 380024598e40c84666cc311a42c256bbf880db3ac99sewardj 381024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic XArray* /* of StackBlock */ get_StackBlocks_for_IP ( Addr ip ) 382024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 383024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* blocks = VG_(di_get_stack_blocks_at_ip)( ip, True/*arrays only*/ ); 384024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(blocks); 385024598e40c84666cc311a42c256bbf880db3ac99sewardj return StackBlocks__find_and_dealloc__or_add( blocks ); 386024598e40c84666cc311a42c256bbf880db3ac99sewardj} 387024598e40c84666cc311a42c256bbf880db3ac99sewardj 388024598e40c84666cc311a42c256bbf880db3ac99sewardj 389024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 390024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 391024598e40c84666cc311a42c256bbf880db3ac99sewardj// GlobalBlocks Persistent Cache // 392024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 393024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 394024598e40c84666cc311a42c256bbf880db3ac99sewardj 395024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Generate an arbitrary total ordering on GlobalBlocks. */ 396024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic Word GlobalBlock__cmp ( GlobalBlock* gb1, GlobalBlock* gb2 ) 397024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 398024598e40c84666cc311a42c256bbf880db3ac99sewardj Word r; 399024598e40c84666cc311a42c256bbf880db3ac99sewardj /* compare addrs */ 400024598e40c84666cc311a42c256bbf880db3ac99sewardj if (gb1->addr < gb2->addr) return -1; 401024598e40c84666cc311a42c256bbf880db3ac99sewardj if (gb1->addr > gb2->addr) return 1; 402024598e40c84666cc311a42c256bbf880db3ac99sewardj /* compare sizes */ 403024598e40c84666cc311a42c256bbf880db3ac99sewardj if (gb1->szB < gb2->szB) return -1; 404024598e40c84666cc311a42c256bbf880db3ac99sewardj if (gb1->szB > gb2->szB) return 1; 405024598e40c84666cc311a42c256bbf880db3ac99sewardj /* compare is/is-not array-typed flag */ 406024598e40c84666cc311a42c256bbf880db3ac99sewardj if (gb1->isVec < gb2->isVec) return -1; 407024598e40c84666cc311a42c256bbf880db3ac99sewardj if (gb1->isVec > gb2->isVec) return 1; 408024598e40c84666cc311a42c256bbf880db3ac99sewardj /* compare the name */ 409024598e40c84666cc311a42c256bbf880db3ac99sewardj r = (Word)VG_(strcmp)(gb1->name, gb2->name); 410024598e40c84666cc311a42c256bbf880db3ac99sewardj if (r != 0) return r; 411024598e40c84666cc311a42c256bbf880db3ac99sewardj /* compare the soname */ 412024598e40c84666cc311a42c256bbf880db3ac99sewardj r = (Word)VG_(strcmp)(gb1->soname, gb2->soname); 413024598e40c84666cc311a42c256bbf880db3ac99sewardj return r; 414024598e40c84666cc311a42c256bbf880db3ac99sewardj} 415024598e40c84666cc311a42c256bbf880db3ac99sewardj 416024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic WordFM* /* GlobalBlock* -> nothing */ 417024598e40c84666cc311a42c256bbf880db3ac99sewardj globalBlock_set = NULL; 418024598e40c84666cc311a42c256bbf880db3ac99sewardj 419024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void init_GlobalBlock_set ( void ) 420024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 421024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(!globalBlock_set); 422024598e40c84666cc311a42c256bbf880db3ac99sewardj globalBlock_set 423024598e40c84666cc311a42c256bbf880db3ac99sewardj = VG_(newFM)( sg_malloc, "di.sg_main.iGBs.1", sg_free, 424024598e40c84666cc311a42c256bbf880db3ac99sewardj (Word(*)(UWord,UWord))GlobalBlock__cmp ); 425024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(globalBlock_set); 426024598e40c84666cc311a42c256bbf880db3ac99sewardj} 427024598e40c84666cc311a42c256bbf880db3ac99sewardj 428024598e40c84666cc311a42c256bbf880db3ac99sewardj 429024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Top level function for making GlobalBlocks persistent. Call here 430024598e40c84666cc311a42c256bbf880db3ac99sewardj with a non-persistent version, and the returned one is guaranteed 431024598e40c84666cc311a42c256bbf880db3ac99sewardj to be valid for the entire rest of the run. The supplied one is 432024598e40c84666cc311a42c256bbf880db3ac99sewardj copied, not stored, so can be freed after the call. */ 433024598e40c84666cc311a42c256bbf880db3ac99sewardj 434024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic GlobalBlock* get_persistent_GlobalBlock ( GlobalBlock* orig ) 435024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 436024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord key, val; 437024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Now, do we have it already? */ 438024598e40c84666cc311a42c256bbf880db3ac99sewardj if (VG_(lookupFM)( globalBlock_set, &key, &val, (UWord)orig )) { 439024598e40c84666cc311a42c256bbf880db3ac99sewardj /* yes, return the copy */ 440024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalBlock* res; 441024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(val == 0); 442024598e40c84666cc311a42c256bbf880db3ac99sewardj res = (GlobalBlock*)key; 443024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(res != orig); 444024598e40c84666cc311a42c256bbf880db3ac99sewardj return res; 445024598e40c84666cc311a42c256bbf880db3ac99sewardj } else { 446024598e40c84666cc311a42c256bbf880db3ac99sewardj /* no. clone it, store the clone and return the clone's 447024598e40c84666cc311a42c256bbf880db3ac99sewardj address. */ 448024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalBlock* clone = sg_malloc( "di.sg_main.gpGB.1", 449024598e40c84666cc311a42c256bbf880db3ac99sewardj sizeof(GlobalBlock) ); 450024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(clone); 451024598e40c84666cc311a42c256bbf880db3ac99sewardj *clone = *orig; 452024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(addToFM)( globalBlock_set, (UWord)clone, 0 ); 453024598e40c84666cc311a42c256bbf880db3ac99sewardj return clone; 454024598e40c84666cc311a42c256bbf880db3ac99sewardj } 455024598e40c84666cc311a42c256bbf880db3ac99sewardj} 456024598e40c84666cc311a42c256bbf880db3ac99sewardj 457024598e40c84666cc311a42c256bbf880db3ac99sewardj 458024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 459024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 460024598e40c84666cc311a42c256bbf880db3ac99sewardj// Interval tree of StackTreeBlock // 461024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 462024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 463024598e40c84666cc311a42c256bbf880db3ac99sewardj 464024598e40c84666cc311a42c256bbf880db3ac99sewardj/* A node in a stack interval tree. Zero length intervals (.szB == 0) 465024598e40c84666cc311a42c256bbf880db3ac99sewardj are not allowed. 466024598e40c84666cc311a42c256bbf880db3ac99sewardj 467024598e40c84666cc311a42c256bbf880db3ac99sewardj A stack interval tree is a (WordFM StackTreeNode* void). There is 468024598e40c84666cc311a42c256bbf880db3ac99sewardj one stack interval tree for each thread. 469024598e40c84666cc311a42c256bbf880db3ac99sewardj*/ 470024598e40c84666cc311a42c256bbf880db3ac99sewardjtypedef 471024598e40c84666cc311a42c256bbf880db3ac99sewardj struct { 472024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr addr; 473024598e40c84666cc311a42c256bbf880db3ac99sewardj SizeT szB; /* copied from .descr->szB */ 474024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock* descr; /* it's an instance of this block */ 475024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord depth; /* depth of stack at time block was pushed */ 476024598e40c84666cc311a42c256bbf880db3ac99sewardj } 477024598e40c84666cc311a42c256bbf880db3ac99sewardj StackTreeNode; 478024598e40c84666cc311a42c256bbf880db3ac99sewardj 47954fe2021b87b9e5edb8ec8070f47b86d5cafb8aaflorianstatic void pp_StackTree ( WordFM* sitree, const HChar* who ) 480024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 481024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord keyW, valW; 482024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)("<<< BEGIN pp_StackTree %s\n", who ); 483024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(initIterFM)( sitree ); 484024598e40c84666cc311a42c256bbf880db3ac99sewardj while (VG_(nextIterFM)( sitree, &keyW, &valW )) { 485024598e40c84666cc311a42c256bbf880db3ac99sewardj StackTreeNode* nd = (StackTreeNode*)keyW; 486024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)(" [%#lx,+%lu) descr=%p %s %lu\n", nd->addr, nd->szB, 487024598e40c84666cc311a42c256bbf880db3ac99sewardj nd->descr, nd->descr->name, nd->descr->szB); 488024598e40c84666cc311a42c256bbf880db3ac99sewardj } 489024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)(">>> END pp_StackTree %s\n", who ); 490024598e40c84666cc311a42c256bbf880db3ac99sewardj} 491024598e40c84666cc311a42c256bbf880db3ac99sewardj 492024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Interval comparison function for StackTreeNode */ 493024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic Word cmp_intervals_StackTreeNode ( StackTreeNode* sn1, 494024598e40c84666cc311a42c256bbf880db3ac99sewardj StackTreeNode* sn2 ) 495024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 496024598e40c84666cc311a42c256bbf880db3ac99sewardj return cmp_nonempty_intervals(sn1->addr, sn1->szB, 497024598e40c84666cc311a42c256bbf880db3ac99sewardj sn2->addr, sn2->szB); 498024598e40c84666cc311a42c256bbf880db3ac99sewardj} 499024598e40c84666cc311a42c256bbf880db3ac99sewardj 500024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Find the node holding 'a', if any. */ 501024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic StackTreeNode* find_StackTreeNode ( WordFM* sitree, Addr a ) 502024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 503024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord keyW, valW; 504024598e40c84666cc311a42c256bbf880db3ac99sewardj StackTreeNode key; 505024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(sitree); 506024598e40c84666cc311a42c256bbf880db3ac99sewardj key.addr = a; 507024598e40c84666cc311a42c256bbf880db3ac99sewardj key.szB = 1; 508024598e40c84666cc311a42c256bbf880db3ac99sewardj if (VG_(lookupFM)( sitree, &keyW, &valW, (UWord)&key )) { 509024598e40c84666cc311a42c256bbf880db3ac99sewardj StackTreeNode* res = (StackTreeNode*)keyW; 510024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(valW == 0); 511024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(res != &key); 512024598e40c84666cc311a42c256bbf880db3ac99sewardj return res; 513024598e40c84666cc311a42c256bbf880db3ac99sewardj } else { 514024598e40c84666cc311a42c256bbf880db3ac99sewardj return NULL; 515024598e40c84666cc311a42c256bbf880db3ac99sewardj } 516024598e40c84666cc311a42c256bbf880db3ac99sewardj} 517024598e40c84666cc311a42c256bbf880db3ac99sewardj 518024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Note that the supplied XArray of FrameBlock must have been 519024598e40c84666cc311a42c256bbf880db3ac99sewardj made persistent already. */ 520024598e40c84666cc311a42c256bbf880db3ac99sewardj__attribute__((noinline)) 521024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void add_blocks_to_StackTree ( 522024598e40c84666cc311a42c256bbf880db3ac99sewardj /*MOD*/WordFM* sitree, 523024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* /* FrameBlock */ descrs, 524024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* /* Addr */ bases, 525024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord depth 526024598e40c84666cc311a42c256bbf880db3ac99sewardj ) 527024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 528024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool debug = (Bool)0; 529024598e40c84666cc311a42c256bbf880db3ac99sewardj Word i, nDescrs, nBases; 530024598e40c84666cc311a42c256bbf880db3ac99sewardj 531024598e40c84666cc311a42c256bbf880db3ac99sewardj nDescrs = VG_(sizeXA)( descrs ), 532024598e40c84666cc311a42c256bbf880db3ac99sewardj nBases = VG_(sizeXA)( bases ); 533024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(nDescrs == nBases); 534024598e40c84666cc311a42c256bbf880db3ac99sewardj 535024598e40c84666cc311a42c256bbf880db3ac99sewardj if (nDescrs == 0) return; 536024598e40c84666cc311a42c256bbf880db3ac99sewardj 537024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(sitree); 538024598e40c84666cc311a42c256bbf880db3ac99sewardj if (debug) { 539b103a55a34f2d4d2eff50541ecaa4cf72b6969e5sewardj VG_(printf)("\ndepth = %lu\n", depth); 540024598e40c84666cc311a42c256bbf880db3ac99sewardj pp_StackTree( sitree, "add_blocks_to_StackTree-pre" ); 541b103a55a34f2d4d2eff50541ecaa4cf72b6969e5sewardj pp_StackBlocks(descrs); 542024598e40c84666cc311a42c256bbf880db3ac99sewardj } 543024598e40c84666cc311a42c256bbf880db3ac99sewardj 544024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < nDescrs; i++) { 545024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool already_present; 546024598e40c84666cc311a42c256bbf880db3ac99sewardj StackTreeNode* nyu; 547024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr addr = *(Addr*)VG_(indexXA)( bases, i ); 548024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock* descr = (StackBlock*)VG_(indexXA)( descrs, i ); 549024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(descr->szB > 0); 550024598e40c84666cc311a42c256bbf880db3ac99sewardj nyu = sg_malloc( "di.sg_main.abtST.1", sizeof(StackTreeNode) ); 551024598e40c84666cc311a42c256bbf880db3ac99sewardj nyu->addr = addr; 552024598e40c84666cc311a42c256bbf880db3ac99sewardj nyu->szB = descr->szB; 553024598e40c84666cc311a42c256bbf880db3ac99sewardj nyu->descr = descr; 554024598e40c84666cc311a42c256bbf880db3ac99sewardj nyu->depth = depth; 555024598e40c84666cc311a42c256bbf880db3ac99sewardj if (debug) VG_(printf)("ADD %#lx %lu\n", addr, descr->szB); 556024598e40c84666cc311a42c256bbf880db3ac99sewardj already_present = VG_(addToFM)( sitree, (UWord)nyu, 0 ); 557024598e40c84666cc311a42c256bbf880db3ac99sewardj /* The interval can't already be there; else we have 558024598e40c84666cc311a42c256bbf880db3ac99sewardj overlapping stack blocks. */ 559024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(!already_present); 560024598e40c84666cc311a42c256bbf880db3ac99sewardj if (debug) { 561024598e40c84666cc311a42c256bbf880db3ac99sewardj pp_StackTree( sitree, "add_blocks_to_StackTree-step" ); 562024598e40c84666cc311a42c256bbf880db3ac99sewardj } 563024598e40c84666cc311a42c256bbf880db3ac99sewardj } 564024598e40c84666cc311a42c256bbf880db3ac99sewardj if (debug) { 565024598e40c84666cc311a42c256bbf880db3ac99sewardj pp_StackTree( sitree, "add_blocks_to_StackTree-post" ); 566024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)("\n"); 567024598e40c84666cc311a42c256bbf880db3ac99sewardj } 568024598e40c84666cc311a42c256bbf880db3ac99sewardj} 569024598e40c84666cc311a42c256bbf880db3ac99sewardj 570024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void del_blocks_from_StackTree ( /*MOD*/WordFM* sitree, 571024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* /* Addr */ bases ) 572024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 573024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord oldK, oldV; 574024598e40c84666cc311a42c256bbf880db3ac99sewardj Word i, nBases = VG_(sizeXA)( bases ); 575024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < nBases; i++) { 576024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool b; 577024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr addr = *(Addr*)VG_(indexXA)( bases, i ); 578024598e40c84666cc311a42c256bbf880db3ac99sewardj StackTreeNode* nd = find_StackTreeNode(sitree, addr); 579024598e40c84666cc311a42c256bbf880db3ac99sewardj /* The interval must be there; we added it earlier when 580024598e40c84666cc311a42c256bbf880db3ac99sewardj the associated frame was created. */ 581024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(nd); 582024598e40c84666cc311a42c256bbf880db3ac99sewardj b = VG_(delFromFM)( sitree, &oldK, &oldV, (UWord)nd ); 583024598e40c84666cc311a42c256bbf880db3ac99sewardj /* we just found the block! */ 584024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(b); 585024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(oldV == 0); 586024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(nd == (StackTreeNode*)oldK); 587024598e40c84666cc311a42c256bbf880db3ac99sewardj sg_free(nd); 588024598e40c84666cc311a42c256bbf880db3ac99sewardj } 589024598e40c84666cc311a42c256bbf880db3ac99sewardj} 590024598e40c84666cc311a42c256bbf880db3ac99sewardj 591024598e40c84666cc311a42c256bbf880db3ac99sewardj 592024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void delete_StackTree__kFin ( UWord keyW ) { 593024598e40c84666cc311a42c256bbf880db3ac99sewardj StackTreeNode* nd = (StackTreeNode*)keyW; 594024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(nd); 595024598e40c84666cc311a42c256bbf880db3ac99sewardj sg_free(nd); 596024598e40c84666cc311a42c256bbf880db3ac99sewardj} 597024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void delete_StackTree__vFin ( UWord valW ) { 598024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(valW == 0); 599024598e40c84666cc311a42c256bbf880db3ac99sewardj} 600024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void delete_StackTree ( WordFM* sitree ) 601024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 602024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(deleteFM)( sitree, 603024598e40c84666cc311a42c256bbf880db3ac99sewardj delete_StackTree__kFin, delete_StackTree__vFin ); 604024598e40c84666cc311a42c256bbf880db3ac99sewardj} 605024598e40c84666cc311a42c256bbf880db3ac99sewardj 606024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic WordFM* new_StackTree ( void ) { 607024598e40c84666cc311a42c256bbf880db3ac99sewardj return VG_(newFM)( sg_malloc, "di.sg_main.nST.1", sg_free, 608024598e40c84666cc311a42c256bbf880db3ac99sewardj (Word(*)(UWord,UWord))cmp_intervals_StackTreeNode ); 609024598e40c84666cc311a42c256bbf880db3ac99sewardj} 610024598e40c84666cc311a42c256bbf880db3ac99sewardj 611024598e40c84666cc311a42c256bbf880db3ac99sewardj 612024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 613024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 614024598e40c84666cc311a42c256bbf880db3ac99sewardj// Interval tree of GlobalTreeBlock // 615024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 616024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 617024598e40c84666cc311a42c256bbf880db3ac99sewardj 618024598e40c84666cc311a42c256bbf880db3ac99sewardj/* A node in a global interval tree. Zero length intervals 619024598e40c84666cc311a42c256bbf880db3ac99sewardj (.szB == 0) are not allowed. 620024598e40c84666cc311a42c256bbf880db3ac99sewardj 621024598e40c84666cc311a42c256bbf880db3ac99sewardj A global interval tree is a (WordFM GlobalTreeNode* void). There 622024598e40c84666cc311a42c256bbf880db3ac99sewardj is one global interval tree for the entire process. 623024598e40c84666cc311a42c256bbf880db3ac99sewardj*/ 624024598e40c84666cc311a42c256bbf880db3ac99sewardjtypedef 625024598e40c84666cc311a42c256bbf880db3ac99sewardj struct { 626024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr addr; /* copied from .descr->addr */ 627024598e40c84666cc311a42c256bbf880db3ac99sewardj SizeT szB; /* copied from .descr->szB */ 628024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalBlock* descr; /* it's this block */ 629024598e40c84666cc311a42c256bbf880db3ac99sewardj } 630024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalTreeNode; 631024598e40c84666cc311a42c256bbf880db3ac99sewardj 632024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void GlobalTreeNode__pp ( GlobalTreeNode* nd ) { 633024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(nd->descr); 63416eef85229a8d8a00dd8edd8f32a4a91cb6ba7a8florian VG_(printf)("GTNode [%#lx,+%lu) %s", 635024598e40c84666cc311a42c256bbf880db3ac99sewardj nd->addr, nd->szB, nd->descr->name); 636024598e40c84666cc311a42c256bbf880db3ac99sewardj} 637024598e40c84666cc311a42c256bbf880db3ac99sewardj 638024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void GlobalTree__pp ( WordFM* /* of (GlobalTreeNode,void) */ gitree, 63954fe2021b87b9e5edb8ec8070f47b86d5cafb8aaflorian const HChar* who ) 640024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 641024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord keyW, valW; 642024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalTreeNode* nd; 643024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)("<<< GlobalBlockTree (%s)\n", who); 644024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(initIterFM)( gitree ); 645024598e40c84666cc311a42c256bbf880db3ac99sewardj while (VG_(nextIterFM)( gitree, &keyW, &valW )) { 646024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(valW == 0); 647024598e40c84666cc311a42c256bbf880db3ac99sewardj nd = (GlobalTreeNode*)keyW; 648024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)(" "); 649024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalTreeNode__pp(nd); 650024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)("\n"); 651024598e40c84666cc311a42c256bbf880db3ac99sewardj } 652024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(doneIterFM)( gitree ); 653024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)(">>>\n"); 654024598e40c84666cc311a42c256bbf880db3ac99sewardj} 655024598e40c84666cc311a42c256bbf880db3ac99sewardj 656024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Interval comparison function for GlobalTreeNode */ 657024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic Word cmp_intervals_GlobalTreeNode ( GlobalTreeNode* gn1, 658024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalTreeNode* gn2 ) 659024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 660024598e40c84666cc311a42c256bbf880db3ac99sewardj return cmp_nonempty_intervals( gn1->addr, gn1->szB, 661024598e40c84666cc311a42c256bbf880db3ac99sewardj gn2->addr, gn2->szB ); 662024598e40c84666cc311a42c256bbf880db3ac99sewardj} 663024598e40c84666cc311a42c256bbf880db3ac99sewardj 664024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Find the node holding 'a', if any. */ 665024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic GlobalTreeNode* find_GlobalTreeNode ( WordFM* gitree, Addr a ) 666024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 667024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord keyW, valW; 668024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalTreeNode key; 669024598e40c84666cc311a42c256bbf880db3ac99sewardj key.addr = a; 670024598e40c84666cc311a42c256bbf880db3ac99sewardj key.szB = 1; 671024598e40c84666cc311a42c256bbf880db3ac99sewardj if (VG_(lookupFM)( gitree, &keyW, &valW, (UWord)&key )) { 672024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalTreeNode* res = (GlobalTreeNode*)keyW; 673024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(valW == 0); 674024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(res != &key); 675024598e40c84666cc311a42c256bbf880db3ac99sewardj return res; 676024598e40c84666cc311a42c256bbf880db3ac99sewardj } else { 677024598e40c84666cc311a42c256bbf880db3ac99sewardj return NULL; 678024598e40c84666cc311a42c256bbf880db3ac99sewardj } 679024598e40c84666cc311a42c256bbf880db3ac99sewardj} 680024598e40c84666cc311a42c256bbf880db3ac99sewardj 681024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Note that the supplied GlobalBlock must have been made persistent 682024598e40c84666cc311a42c256bbf880db3ac99sewardj already. */ 683024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void add_block_to_GlobalTree ( 684024598e40c84666cc311a42c256bbf880db3ac99sewardj /*MOD*/WordFM* gitree, 685024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalBlock* descr 686024598e40c84666cc311a42c256bbf880db3ac99sewardj ) 687024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 688024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool already_present; 689024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalTreeNode *nyu, *nd; 690024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord keyW, valW; 691f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj static Int moans = 3; 692024598e40c84666cc311a42c256bbf880db3ac99sewardj 693024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(descr->szB > 0); 694024598e40c84666cc311a42c256bbf880db3ac99sewardj nyu = sg_malloc( "di.sg_main.abtG.1", sizeof(GlobalTreeNode) ); 695024598e40c84666cc311a42c256bbf880db3ac99sewardj nyu->addr = descr->addr; 696024598e40c84666cc311a42c256bbf880db3ac99sewardj nyu->szB = descr->szB; 697024598e40c84666cc311a42c256bbf880db3ac99sewardj nyu->descr = descr; 698024598e40c84666cc311a42c256bbf880db3ac99sewardj 699024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Basically it's an error to add a global block to the tree that 700024598e40c84666cc311a42c256bbf880db3ac99sewardj is already in the tree. However, detect and ignore attempts to 701024598e40c84666cc311a42c256bbf880db3ac99sewardj insert exact duplicates; they do appear for some reason 702024598e40c84666cc311a42c256bbf880db3ac99sewardj (possible a bug in m_debuginfo?) */ 703024598e40c84666cc311a42c256bbf880db3ac99sewardj already_present = VG_(lookupFM)( gitree, &keyW, &valW, (UWord)nyu ); 704024598e40c84666cc311a42c256bbf880db3ac99sewardj if (already_present) { 705024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(valW == 0); 706024598e40c84666cc311a42c256bbf880db3ac99sewardj nd = (GlobalTreeNode*)keyW; 707024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(nd); 708024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(nd != nyu); 709024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(nd->descr); 710024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(nyu->descr); 711024598e40c84666cc311a42c256bbf880db3ac99sewardj if (nd->addr == nyu->addr && nd->szB == nyu->szB 712024598e40c84666cc311a42c256bbf880db3ac99sewardj /* && 0 == VG_(strcmp)(nd->descr->name, nyu->descr->name) */ 713024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Although it seems reasonable to demand that duplicate 714024598e40c84666cc311a42c256bbf880db3ac99sewardj blocks have identical names, that is too strict. For 715024598e40c84666cc311a42c256bbf880db3ac99sewardj example, reading debuginfo from glibc produces two 716024598e40c84666cc311a42c256bbf880db3ac99sewardj otherwise identical blocks with names "tzname" and 717024598e40c84666cc311a42c256bbf880db3ac99sewardj "__tzname". A constraint of the form "must be identical, 718024598e40c84666cc311a42c256bbf880db3ac99sewardj or one must be a substring of the other" would fix that. 719024598e40c84666cc311a42c256bbf880db3ac99sewardj However, such trickery is scuppered by the fact that we 720024598e40c84666cc311a42c256bbf880db3ac99sewardj truncate all variable names to 15 characters to make 721024598e40c84666cc311a42c256bbf880db3ac99sewardj storage management simpler, hence giving pairs like 722024598e40c84666cc311a42c256bbf880db3ac99sewardj "__EI___pthread_" (truncated) vs "__pthread_keys". So 723024598e40c84666cc311a42c256bbf880db3ac99sewardj it's simplest just to skip the name comparison 724024598e40c84666cc311a42c256bbf880db3ac99sewardj completely. */ 725024598e40c84666cc311a42c256bbf880db3ac99sewardj && 0 == VG_(strcmp)(nd->descr->soname, nyu->descr->soname)) { 726024598e40c84666cc311a42c256bbf880db3ac99sewardj /* exact duplicate; ignore it */ 727024598e40c84666cc311a42c256bbf880db3ac99sewardj sg_free(nyu); 728024598e40c84666cc311a42c256bbf880db3ac99sewardj return; 729024598e40c84666cc311a42c256bbf880db3ac99sewardj } 730024598e40c84666cc311a42c256bbf880db3ac99sewardj /* else fall through; the assertion below will catch it */ 731024598e40c84666cc311a42c256bbf880db3ac99sewardj } 732024598e40c84666cc311a42c256bbf880db3ac99sewardj 733024598e40c84666cc311a42c256bbf880db3ac99sewardj already_present = VG_(addToFM)( gitree, (UWord)nyu, 0 ); 734024598e40c84666cc311a42c256bbf880db3ac99sewardj /* The interval can't already be there; else we have 735024598e40c84666cc311a42c256bbf880db3ac99sewardj overlapping global blocks. */ 736f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj /* Unfortunately (25 Jan 09) at least icc11 has been seen to 737f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj generate overlapping block descriptions in the Dwarf3; clearly 738f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj bogus. */ 739f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj if (already_present && moans > 0 && !VG_(clo_xml)) { 740f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj moans--; 741f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj VG_(message)(Vg_UserMsg, "Warning: bogus DWARF3 info: " 742c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj "overlapping global blocks\n"); 743f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj if (VG_(clo_verbosity) >= 2) { 744f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj GlobalTree__pp( gitree, 745f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj "add_block_to_GlobalTree: non-exact duplicate" ); 746f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj VG_(printf)("Overlapping block: "); 747f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj GlobalTreeNode__pp(nyu); 748f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj VG_(printf)("\n"); 749f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj } 750f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj if (moans == 0) 751f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj VG_(message)(Vg_UserMsg, "Further instances of this " 752c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj "message will not be shown\n" ); 753024598e40c84666cc311a42c256bbf880db3ac99sewardj } 754f22ab4a5093b46ed680a8a7ea13553fd57fceaadsewardj /* tl_assert(!already_present); */ 755024598e40c84666cc311a42c256bbf880db3ac99sewardj} 756024598e40c84666cc311a42c256bbf880db3ac99sewardj 757024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic Bool del_GlobalTree_range ( /*MOD*/WordFM* gitree, 758024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr a, SizeT szB ) 759024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 760024598e40c84666cc311a42c256bbf880db3ac99sewardj /* One easy way to do this: look up [a,a+szB) in the tree. That 761024598e40c84666cc311a42c256bbf880db3ac99sewardj will either succeed, producing a block which intersects that 762024598e40c84666cc311a42c256bbf880db3ac99sewardj range, in which case we delete it and repeat; or it will fail, 763024598e40c84666cc311a42c256bbf880db3ac99sewardj in which case there are no blocks intersecting the range, and we 764024598e40c84666cc311a42c256bbf880db3ac99sewardj can bring the process to a halt. */ 765024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord keyW, valW, oldK, oldV; 766024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalTreeNode key, *nd; 767024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool b, anyFound; 768024598e40c84666cc311a42c256bbf880db3ac99sewardj 769024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(szB > 0); 770024598e40c84666cc311a42c256bbf880db3ac99sewardj 771024598e40c84666cc311a42c256bbf880db3ac99sewardj anyFound = False; 772024598e40c84666cc311a42c256bbf880db3ac99sewardj 773024598e40c84666cc311a42c256bbf880db3ac99sewardj key.addr = a; 774024598e40c84666cc311a42c256bbf880db3ac99sewardj key.szB = szB; 775024598e40c84666cc311a42c256bbf880db3ac99sewardj 776024598e40c84666cc311a42c256bbf880db3ac99sewardj while (VG_(lookupFM)( gitree, &keyW, &valW, (UWord)&key )) { 777024598e40c84666cc311a42c256bbf880db3ac99sewardj anyFound = True; 778024598e40c84666cc311a42c256bbf880db3ac99sewardj nd = (GlobalTreeNode*)keyW; 779024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(valW == 0); 780024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(nd != &key); 781024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(cmp_nonempty_intervals(a, szB, nd->addr, nd->szB) == 0); 782024598e40c84666cc311a42c256bbf880db3ac99sewardj 783024598e40c84666cc311a42c256bbf880db3ac99sewardj b = VG_(delFromFM)( gitree, &oldK, &oldV, (UWord)&key ); 784024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(b); 785024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(oldV == 0); 786024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(oldK == keyW); /* check we deleted the node we just found */ 787024598e40c84666cc311a42c256bbf880db3ac99sewardj } 788024598e40c84666cc311a42c256bbf880db3ac99sewardj 789024598e40c84666cc311a42c256bbf880db3ac99sewardj return anyFound; 790024598e40c84666cc311a42c256bbf880db3ac99sewardj} 791024598e40c84666cc311a42c256bbf880db3ac99sewardj 792024598e40c84666cc311a42c256bbf880db3ac99sewardj 793024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 794024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 795024598e40c84666cc311a42c256bbf880db3ac99sewardj// Invar // 796024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 797024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 798024598e40c84666cc311a42c256bbf880db3ac99sewardj 799024598e40c84666cc311a42c256bbf880db3ac99sewardj/* An invariant, as resulting from watching the destination of a 800024598e40c84666cc311a42c256bbf880db3ac99sewardj memory referencing instruction. Initially is Inv_Unset until the 801024598e40c84666cc311a42c256bbf880db3ac99sewardj instruction makes a first access. */ 802024598e40c84666cc311a42c256bbf880db3ac99sewardj 803024598e40c84666cc311a42c256bbf880db3ac99sewardjtypedef 804024598e40c84666cc311a42c256bbf880db3ac99sewardj enum { 805024598e40c84666cc311a42c256bbf880db3ac99sewardj Inv_Unset=1, /* not established yet */ 806024598e40c84666cc311a42c256bbf880db3ac99sewardj Inv_Unknown, /* unknown location */ 807024598e40c84666cc311a42c256bbf880db3ac99sewardj Inv_Stack0, /* array-typed stack block in innermost frame */ 808024598e40c84666cc311a42c256bbf880db3ac99sewardj Inv_StackN, /* array-typed stack block in non-innermost frame */ 809024598e40c84666cc311a42c256bbf880db3ac99sewardj Inv_Global, /* array-typed global block */ 810024598e40c84666cc311a42c256bbf880db3ac99sewardj } 811024598e40c84666cc311a42c256bbf880db3ac99sewardj InvarTag; 812024598e40c84666cc311a42c256bbf880db3ac99sewardj 813024598e40c84666cc311a42c256bbf880db3ac99sewardjtypedef 814024598e40c84666cc311a42c256bbf880db3ac99sewardj struct { 815024598e40c84666cc311a42c256bbf880db3ac99sewardj InvarTag tag; 816024598e40c84666cc311a42c256bbf880db3ac99sewardj union { 817024598e40c84666cc311a42c256bbf880db3ac99sewardj struct { 818024598e40c84666cc311a42c256bbf880db3ac99sewardj } Unset; 819024598e40c84666cc311a42c256bbf880db3ac99sewardj struct { 820024598e40c84666cc311a42c256bbf880db3ac99sewardj } Unknown; 821024598e40c84666cc311a42c256bbf880db3ac99sewardj struct { 822024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr addr; 823024598e40c84666cc311a42c256bbf880db3ac99sewardj SizeT szB; 824024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock* descr; 825024598e40c84666cc311a42c256bbf880db3ac99sewardj } Stack0; /* innermost stack frame */ 826024598e40c84666cc311a42c256bbf880db3ac99sewardj struct { 827024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Pointer to a node in the interval tree for 828024598e40c84666cc311a42c256bbf880db3ac99sewardj this thread. */ 829024598e40c84666cc311a42c256bbf880db3ac99sewardj StackTreeNode* nd; 830024598e40c84666cc311a42c256bbf880db3ac99sewardj } StackN; /* non-innermost stack frame */ 831024598e40c84666cc311a42c256bbf880db3ac99sewardj struct { 832024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Pointer to a GlobalBlock in the interval tree of 833024598e40c84666cc311a42c256bbf880db3ac99sewardj global blocks. */ 834024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalTreeNode* nd; 835024598e40c84666cc311a42c256bbf880db3ac99sewardj } Global; 836024598e40c84666cc311a42c256bbf880db3ac99sewardj } 837024598e40c84666cc311a42c256bbf880db3ac99sewardj Inv; 838024598e40c84666cc311a42c256bbf880db3ac99sewardj } 839024598e40c84666cc311a42c256bbf880db3ac99sewardj Invar; 840024598e40c84666cc311a42c256bbf880db3ac99sewardj 841024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Partial debugging printing for an Invar. */ 842024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void pp_Invar ( Invar* i ) 843024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 844024598e40c84666cc311a42c256bbf880db3ac99sewardj switch (i->tag) { 845024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_Unset: 846024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)("Unset"); 847024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 848024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_Unknown: 849024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)("Unknown"); 850024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 851024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_Stack0: 852024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)("Stack0 [%#lx,+%lu)", 853024598e40c84666cc311a42c256bbf880db3ac99sewardj i->Inv.Stack0.addr, i->Inv.Stack0.szB); 854024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 855024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_StackN: 856024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)("StackN [%#lx,+%lu)", 857024598e40c84666cc311a42c256bbf880db3ac99sewardj i->Inv.StackN.nd->addr, i->Inv.StackN.nd->szB); 858024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 859024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_Global: 860024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)("Global [%#lx,+%lu)", 861024598e40c84666cc311a42c256bbf880db3ac99sewardj i->Inv.Global.nd->addr, i->Inv.Global.nd->szB); 862024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 863024598e40c84666cc311a42c256bbf880db3ac99sewardj default: 864024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(0); 865024598e40c84666cc311a42c256bbf880db3ac99sewardj } 866024598e40c84666cc311a42c256bbf880db3ac99sewardj} 867024598e40c84666cc311a42c256bbf880db3ac99sewardj 868024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Compare two Invars for equality. */ 869024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic Bool eq_Invar ( Invar* i1, Invar* i2 ) 870024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 871024598e40c84666cc311a42c256bbf880db3ac99sewardj if (i1->tag != i2->tag) 872024598e40c84666cc311a42c256bbf880db3ac99sewardj return False; 873024598e40c84666cc311a42c256bbf880db3ac99sewardj switch (i1->tag) { 874110e0f8e7effba90dc43d9763ebacdc61e4ae678florian case Inv_Unset: 875110e0f8e7effba90dc43d9763ebacdc61e4ae678florian return True; 876024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_Unknown: 877024598e40c84666cc311a42c256bbf880db3ac99sewardj return True; 878024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_Stack0: 879024598e40c84666cc311a42c256bbf880db3ac99sewardj return i1->Inv.Stack0.addr == i2->Inv.Stack0.addr 880024598e40c84666cc311a42c256bbf880db3ac99sewardj && i1->Inv.Stack0.szB == i2->Inv.Stack0.szB; 881024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_StackN: 882024598e40c84666cc311a42c256bbf880db3ac99sewardj return i1->Inv.StackN.nd == i2->Inv.StackN.nd; 883024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_Global: 884024598e40c84666cc311a42c256bbf880db3ac99sewardj return i1->Inv.Global.nd == i2->Inv.Global.nd; 885024598e40c84666cc311a42c256bbf880db3ac99sewardj default: 886024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(0); 887024598e40c84666cc311a42c256bbf880db3ac99sewardj } 888024598e40c84666cc311a42c256bbf880db3ac99sewardj /*NOTREACHED*/ 889024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(0); 890024598e40c84666cc311a42c256bbf880db3ac99sewardj} 891024598e40c84666cc311a42c256bbf880db3ac99sewardj 892f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj/* Generate a piece of text showing 'ea' is relative to 'invar', if 893f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj known. If unknown, generate an empty string. 'buf' must be at 894f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj least 32 bytes in size. Also return the absolute value of the 895f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj delta, if known, or zero if not known. 896f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj*/ 897f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardjstatic void gen_delta_str ( /*OUT*/HChar* buf, 898f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj /*OUT*/UWord* absDelta, 899f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj Invar* inv, Addr ea ) 900f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj{ 901f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj Addr block = 0; 902f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj SizeT szB = 0; 903f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj 904f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj buf[0] = 0; 905f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj *absDelta = 0; 906f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj 907f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj switch (inv->tag) { 908f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj case Inv_Unknown: 909f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj case Inv_Unset: 910f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj return; /* unknown */ 911f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj case Inv_Stack0: 912f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj block = inv->Inv.Stack0.addr; 913f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj szB = inv->Inv.Stack0.szB; 914f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj break; 915f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj case Inv_StackN: 916f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj block = inv->Inv.StackN.nd->addr; 917f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj szB = inv->Inv.StackN.nd->szB; 918f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj break; 919f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj case Inv_Global: 920f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj block = inv->Inv.Global.nd->addr; 921f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj szB = inv->Inv.Global.nd->szB; 922f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj break; 923f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj default: 924f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj tl_assert(0); 925f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj } 926f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj tl_assert(szB > 0); 927f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj if (ea < block) { 928f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj *absDelta = block - ea; 929f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj VG_(sprintf)(buf, "%'lu before", *absDelta); 930f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj } 931f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj else if (ea >= block + szB) { 932f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj *absDelta = ea - (block + szB); 933f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj VG_(sprintf)(buf, "%'lu after", *absDelta); 934f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj } 935f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj else { 936f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj // Leave *absDelta at zero. 937f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj VG_(sprintf)(buf, "%'lu inside", ea - block); 938f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj } 939f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj} 940f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj 941f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj 942024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Print selected parts of an Invar, suitable for use in error 943024598e40c84666cc311a42c256bbf880db3ac99sewardj messages. */ 944024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void show_Invar( HChar* buf, Word nBuf, Invar* inv, Word depth ) 945024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 9466bd9dc18c043927c1196caba20a327238a179c42florian const HChar* str; 947f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj tl_assert(nBuf >= 128); 948024598e40c84666cc311a42c256bbf880db3ac99sewardj buf[0] = 0; 949024598e40c84666cc311a42c256bbf880db3ac99sewardj switch (inv->tag) { 950024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_Unknown: 951024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(sprintf)(buf, "%s", "unknown"); 952024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 953024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_Stack0: 954024598e40c84666cc311a42c256bbf880db3ac99sewardj str = "array"; 955f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj VG_(sprintf)(buf, "stack %s \"%s\" of size %'lu in this frame", 956f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj str, inv->Inv.Stack0.descr->name, 957f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj inv->Inv.Stack0.szB ); 958024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 959024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_StackN: 960024598e40c84666cc311a42c256bbf880db3ac99sewardj str = "array"; 961f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj VG_(sprintf)(buf, "stack %s \"%s\" of size %'lu in frame %lu back from here", 962024598e40c84666cc311a42c256bbf880db3ac99sewardj str, inv->Inv.StackN.nd->descr->name, 963f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj inv->Inv.StackN.nd->descr->szB, 964024598e40c84666cc311a42c256bbf880db3ac99sewardj depth - inv->Inv.StackN.nd->depth ); 965024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 966024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_Global: 967024598e40c84666cc311a42c256bbf880db3ac99sewardj str = "array"; 968f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj VG_(sprintf)(buf, "global %s \"%s\" of size %'lu in object with soname \"%s\"", 969024598e40c84666cc311a42c256bbf880db3ac99sewardj str, inv->Inv.Global.nd->descr->name, 970f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj inv->Inv.Global.nd->descr->szB, 971024598e40c84666cc311a42c256bbf880db3ac99sewardj inv->Inv.Global.nd->descr->soname ); 972024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 973024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_Unset: 974024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(sprintf)(buf, "%s", "Unset!"); 975024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 976024598e40c84666cc311a42c256bbf880db3ac99sewardj default: 977024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(0); 978024598e40c84666cc311a42c256bbf880db3ac99sewardj } 979024598e40c84666cc311a42c256bbf880db3ac99sewardj} 980024598e40c84666cc311a42c256bbf880db3ac99sewardj 981024598e40c84666cc311a42c256bbf880db3ac99sewardj 982024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 983024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 984024598e40c84666cc311a42c256bbf880db3ac99sewardj// our globals // 985024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 986024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 987024598e40c84666cc311a42c256bbf880db3ac99sewardj 988024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 989024598e40c84666cc311a42c256bbf880db3ac99sewardj/// 990024598e40c84666cc311a42c256bbf880db3ac99sewardj 991024598e40c84666cc311a42c256bbf880db3ac99sewardj#define N_QCACHE 16 992024598e40c84666cc311a42c256bbf880db3ac99sewardj 993024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Powers of two only, else the result will be chaos */ 994024598e40c84666cc311a42c256bbf880db3ac99sewardj#define QCACHE_ADVANCE_EVERY 16 995024598e40c84666cc311a42c256bbf880db3ac99sewardj 996024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Per-thread query cache. Note that the invar can only be Inv_StackN 997024598e40c84666cc311a42c256bbf880db3ac99sewardj (but not Inv_Stack0), Inv_Global or Inv_Unknown. */ 998024598e40c84666cc311a42c256bbf880db3ac99sewardjtypedef 999024598e40c84666cc311a42c256bbf880db3ac99sewardj struct { 1000024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr addr; 1001024598e40c84666cc311a42c256bbf880db3ac99sewardj SizeT szB; 1002024598e40c84666cc311a42c256bbf880db3ac99sewardj Invar inv; 1003024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1004024598e40c84666cc311a42c256bbf880db3ac99sewardj QCElem; 1005024598e40c84666cc311a42c256bbf880db3ac99sewardj 1006024598e40c84666cc311a42c256bbf880db3ac99sewardjtypedef 1007024598e40c84666cc311a42c256bbf880db3ac99sewardj struct { 1008024598e40c84666cc311a42c256bbf880db3ac99sewardj Word nInUse; 1009024598e40c84666cc311a42c256bbf880db3ac99sewardj QCElem elems[N_QCACHE]; 1010024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1011024598e40c84666cc311a42c256bbf880db3ac99sewardj QCache; 1012024598e40c84666cc311a42c256bbf880db3ac99sewardj 1013024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void QCache__invalidate ( QCache* qc ) { 1014024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(qc->nInUse >= 0); 1015024598e40c84666cc311a42c256bbf880db3ac99sewardj qc->nInUse = 0; 1016024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1017024598e40c84666cc311a42c256bbf880db3ac99sewardj 101854fe2021b87b9e5edb8ec8070f47b86d5cafb8aaflorianstatic void QCache__pp ( QCache* qc, const HChar* who ) 1019024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1020024598e40c84666cc311a42c256bbf880db3ac99sewardj Word i; 1021024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)("<<< QCache with %ld elements (%s)\n", qc->nInUse, who); 1022024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < qc->nInUse; i++) { 1023024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)(" [%#lx,+%#lx) ", qc->elems[i].addr, qc->elems[i].szB); 1024024598e40c84666cc311a42c256bbf880db3ac99sewardj pp_Invar(&qc->elems[i].inv); 1025024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)("\n"); 1026024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1027024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)(">>>\n"); 1028024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1029024598e40c84666cc311a42c256bbf880db3ac99sewardj 1030024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic ULong stats__qcache_queries = 0; 1031024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic ULong stats__qcache_misses = 0; 1032024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic ULong stats__qcache_probes = 0; 1033024598e40c84666cc311a42c256bbf880db3ac99sewardj 1034024598e40c84666cc311a42c256bbf880db3ac99sewardj/// 1035024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 1036024598e40c84666cc311a42c256bbf880db3ac99sewardj 1037024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Each thread has: 1038024598e40c84666cc311a42c256bbf880db3ac99sewardj * a shadow stack of StackFrames, which is a double-linked list 1039024598e40c84666cc311a42c256bbf880db3ac99sewardj * an stack block interval tree 1040024598e40c84666cc311a42c256bbf880db3ac99sewardj*/ 10411e802b6a8d0d4b7b630d2a1dd9683c7c889b01a3florianstatic struct _StackFrame** shadowStacks; 1042024598e40c84666cc311a42c256bbf880db3ac99sewardj 10431e802b6a8d0d4b7b630d2a1dd9683c7c889b01a3florianstatic WordFM** /* StackTreeNode */ siTrees; 1044024598e40c84666cc311a42c256bbf880db3ac99sewardj 10451e802b6a8d0d4b7b630d2a1dd9683c7c889b01a3florianstatic QCache* qcaches; 1046024598e40c84666cc311a42c256bbf880db3ac99sewardj 1047024598e40c84666cc311a42c256bbf880db3ac99sewardj 1048024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Additionally, there is one global variable interval tree 1049024598e40c84666cc311a42c256bbf880db3ac99sewardj for the entire process. 1050024598e40c84666cc311a42c256bbf880db3ac99sewardj*/ 1051024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic WordFM* /* GlobalTreeNode */ giTree; 1052024598e40c84666cc311a42c256bbf880db3ac99sewardj 1053024598e40c84666cc311a42c256bbf880db3ac99sewardj 1054024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void invalidate_all_QCaches ( void ) 1055024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1056024598e40c84666cc311a42c256bbf880db3ac99sewardj Word i; 1057024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < VG_N_THREADS; i++) { 1058024598e40c84666cc311a42c256bbf880db3ac99sewardj QCache__invalidate( &qcaches[i] ); 1059024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1060024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1061024598e40c84666cc311a42c256bbf880db3ac99sewardj 1062024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void ourGlobals_init ( void ) 1063024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1064024598e40c84666cc311a42c256bbf880db3ac99sewardj Word i; 10651e802b6a8d0d4b7b630d2a1dd9683c7c889b01a3florian 10661e802b6a8d0d4b7b630d2a1dd9683c7c889b01a3florian shadowStacks = sg_malloc( "di.sg_main.oGi.2", 10671e802b6a8d0d4b7b630d2a1dd9683c7c889b01a3florian VG_N_THREADS * sizeof shadowStacks[0] ); 10681e802b6a8d0d4b7b630d2a1dd9683c7c889b01a3florian siTrees = sg_malloc( "di.sg_main.oGi.3", VG_N_THREADS * sizeof siTrees[0] ); 10691e802b6a8d0d4b7b630d2a1dd9683c7c889b01a3florian qcaches = sg_malloc( "di.sg_main.oGi.4", VG_N_THREADS * sizeof qcaches[0] ); 10701e802b6a8d0d4b7b630d2a1dd9683c7c889b01a3florian 1071024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < VG_N_THREADS; i++) { 1072024598e40c84666cc311a42c256bbf880db3ac99sewardj shadowStacks[i] = NULL; 1073024598e40c84666cc311a42c256bbf880db3ac99sewardj siTrees[i] = NULL; 10741e802b6a8d0d4b7b630d2a1dd9683c7c889b01a3florian qcaches[i] = (QCache){}; 1075024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1076024598e40c84666cc311a42c256bbf880db3ac99sewardj invalidate_all_QCaches(); 1077024598e40c84666cc311a42c256bbf880db3ac99sewardj giTree = VG_(newFM)( sg_malloc, "di.sg_main.oGi.1", sg_free, 1078024598e40c84666cc311a42c256bbf880db3ac99sewardj (Word(*)(UWord,UWord))cmp_intervals_GlobalTreeNode ); 1079024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1080024598e40c84666cc311a42c256bbf880db3ac99sewardj 1081024598e40c84666cc311a42c256bbf880db3ac99sewardj 1082024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 1083024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 1084024598e40c84666cc311a42c256bbf880db3ac99sewardj// Handle global variable load/unload events // 1085024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 1086024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 1087024598e40c84666cc311a42c256bbf880db3ac99sewardj 1088024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void acquire_globals ( ULong di_handle ) 1089024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1090024598e40c84666cc311a42c256bbf880db3ac99sewardj Word n, i; 1091024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* /* of GlobalBlock */ gbs; 1092024598e40c84666cc311a42c256bbf880db3ac99sewardj if (0) VG_(printf)("ACQUIRE GLOBALS %llu\n", di_handle ); 1093024598e40c84666cc311a42c256bbf880db3ac99sewardj gbs = VG_(di_get_global_blocks_from_dihandle) 1094024598e40c84666cc311a42c256bbf880db3ac99sewardj (di_handle, True/*arrays only*/); 1095024598e40c84666cc311a42c256bbf880db3ac99sewardj if (0) VG_(printf)(" GOT %ld globals\n", VG_(sizeXA)( gbs )); 1096024598e40c84666cc311a42c256bbf880db3ac99sewardj 1097024598e40c84666cc311a42c256bbf880db3ac99sewardj n = VG_(sizeXA)( gbs ); 1098024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < n; i++) { 1099024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalBlock* gbp; 1100024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalBlock* gb = VG_(indexXA)( gbs, i ); 1101024598e40c84666cc311a42c256bbf880db3ac99sewardj if (0) VG_(printf)(" new Global size %2lu at %#lx: %s %s\n", 1102024598e40c84666cc311a42c256bbf880db3ac99sewardj gb->szB, gb->addr, gb->soname, gb->name ); 1103024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(gb->szB > 0); 1104024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Make a persistent copy of each GlobalBlock, and add it 1105024598e40c84666cc311a42c256bbf880db3ac99sewardj to the tree. */ 1106024598e40c84666cc311a42c256bbf880db3ac99sewardj gbp = get_persistent_GlobalBlock( gb ); 1107024598e40c84666cc311a42c256bbf880db3ac99sewardj add_block_to_GlobalTree( giTree, gbp ); 1108024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1109024598e40c84666cc311a42c256bbf880db3ac99sewardj 1110024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(deleteXA)( gbs ); 1111024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1112024598e40c84666cc311a42c256bbf880db3ac99sewardj 1113024598e40c84666cc311a42c256bbf880db3ac99sewardj 1114024598e40c84666cc311a42c256bbf880db3ac99sewardj/* We only intercept these two because we need to see any di_handles 1115024598e40c84666cc311a42c256bbf880db3ac99sewardj that might arise from the mappings/allocations. */ 1116024598e40c84666cc311a42c256bbf880db3ac99sewardjvoid sg_new_mem_mmap( Addr a, SizeT len, 1117024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool rr, Bool ww, Bool xx, ULong di_handle ) 1118024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1119024598e40c84666cc311a42c256bbf880db3ac99sewardj if (di_handle > 0) 1120024598e40c84666cc311a42c256bbf880db3ac99sewardj acquire_globals(di_handle); 1121024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1122024598e40c84666cc311a42c256bbf880db3ac99sewardjvoid sg_new_mem_startup( Addr a, SizeT len, 1123024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool rr, Bool ww, Bool xx, ULong di_handle ) 1124024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1125024598e40c84666cc311a42c256bbf880db3ac99sewardj if (di_handle > 0) 1126024598e40c84666cc311a42c256bbf880db3ac99sewardj acquire_globals(di_handle); 1127024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1128024598e40c84666cc311a42c256bbf880db3ac99sewardjvoid sg_die_mem_munmap ( Addr a, SizeT len ) 1129024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1130024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool debug = (Bool)0; 1131024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool overlap = False; 1132024598e40c84666cc311a42c256bbf880db3ac99sewardj 1133024598e40c84666cc311a42c256bbf880db3ac99sewardj if (debug) VG_(printf)("MUNMAP %#lx %lu\n", a, len ); 1134024598e40c84666cc311a42c256bbf880db3ac99sewardj 1135024598e40c84666cc311a42c256bbf880db3ac99sewardj if (len == 0) 1136024598e40c84666cc311a42c256bbf880db3ac99sewardj return; 1137024598e40c84666cc311a42c256bbf880db3ac99sewardj 1138024598e40c84666cc311a42c256bbf880db3ac99sewardj overlap = del_GlobalTree_range(giTree, a, len); 1139024598e40c84666cc311a42c256bbf880db3ac99sewardj 1140024598e40c84666cc311a42c256bbf880db3ac99sewardj { /* redundant sanity check */ 1141024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord keyW, valW; 1142024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(initIterFM)( giTree ); 1143024598e40c84666cc311a42c256bbf880db3ac99sewardj while (VG_(nextIterFM)( giTree, &keyW, &valW )) { 1144024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalTreeNode* nd = (GlobalTreeNode*)keyW; 1145024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(valW == 0); 1146024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(nd->szB > 0); 1147024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(nd->addr + nd->szB <= a 1148024598e40c84666cc311a42c256bbf880db3ac99sewardj || a + len <= nd->addr); 1149024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1150024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(doneIterFM)( giTree ); 1151024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1152024598e40c84666cc311a42c256bbf880db3ac99sewardj 1153024598e40c84666cc311a42c256bbf880db3ac99sewardj if (!overlap) 1154024598e40c84666cc311a42c256bbf880db3ac99sewardj return; 1155024598e40c84666cc311a42c256bbf880db3ac99sewardj 1156024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Ok, the range contained some blocks. Therefore we'll need to 1157024598e40c84666cc311a42c256bbf880db3ac99sewardj visit all the Invars in all the thread shadow stacks, and 11589e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj convert all Inv_Global entries that intersect [a,a+len) to 1159024598e40c84666cc311a42c256bbf880db3ac99sewardj Inv_Unknown. */ 1160024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(len > 0); 11619e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj preen_global_Invars( a, len ); 1162024598e40c84666cc311a42c256bbf880db3ac99sewardj invalidate_all_QCaches(); 1163024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1164024598e40c84666cc311a42c256bbf880db3ac99sewardj 1165024598e40c84666cc311a42c256bbf880db3ac99sewardj 1166024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 1167024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 1168024598e40c84666cc311a42c256bbf880db3ac99sewardj// StackFrame // 1169024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 1170024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 1171024598e40c84666cc311a42c256bbf880db3ac99sewardj 1172024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic ULong stats__total_accesses = 0; 1173024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic ULong stats__classify_Stack0 = 0; 1174024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic ULong stats__classify_StackN = 0; 1175024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic ULong stats__classify_Global = 0; 1176024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic ULong stats__classify_Unknown = 0; 1177024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic ULong stats__Invars_preened = 0; 1178024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic ULong stats__Invars_changed = 0; 1179024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic ULong stats__t_i_b_empty = 0; 1180024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic ULong stats__htab_fast = 0; 1181024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic ULong stats__htab_searches = 0; 1182024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic ULong stats__htab_probes = 0; 1183024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic ULong stats__htab_resizes = 0; 1184024598e40c84666cc311a42c256bbf880db3ac99sewardj 1185024598e40c84666cc311a42c256bbf880db3ac99sewardj 1186024598e40c84666cc311a42c256bbf880db3ac99sewardj/* A dynamic instance of an instruction */ 1187024598e40c84666cc311a42c256bbf880db3ac99sewardjtypedef 1188024598e40c84666cc311a42c256bbf880db3ac99sewardj struct { 1189024598e40c84666cc311a42c256bbf880db3ac99sewardj /* IMMUTABLE */ 1190024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr insn_addr; /* NB! zero means 'not in use' */ 1191024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* blocks; /* XArray* of StackBlock, or NULL if none */ 1192024598e40c84666cc311a42c256bbf880db3ac99sewardj /* MUTABLE */ 1193024598e40c84666cc311a42c256bbf880db3ac99sewardj Invar invar; 1194024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1195024598e40c84666cc311a42c256bbf880db3ac99sewardj IInstance; 1196024598e40c84666cc311a42c256bbf880db3ac99sewardj 1197024598e40c84666cc311a42c256bbf880db3ac99sewardj 1198024598e40c84666cc311a42c256bbf880db3ac99sewardj#define N_HTAB_FIXED 64 1199024598e40c84666cc311a42c256bbf880db3ac99sewardj 1200024598e40c84666cc311a42c256bbf880db3ac99sewardjtypedef 1201024598e40c84666cc311a42c256bbf880db3ac99sewardj struct _StackFrame { 1202024598e40c84666cc311a42c256bbf880db3ac99sewardj /* The sp when the frame was created, so we know when to get rid 1203024598e40c84666cc311a42c256bbf880db3ac99sewardj of it. */ 1204024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr creation_sp; 1205024598e40c84666cc311a42c256bbf880db3ac99sewardj /* The stack frames for a thread are arranged as a doubly linked 1206024598e40c84666cc311a42c256bbf880db3ac99sewardj list. Obviously the outermost frame in the stack has .outer 1207024598e40c84666cc311a42c256bbf880db3ac99sewardj as NULL and the innermost in theory has .inner as NULL. 1208024598e40c84666cc311a42c256bbf880db3ac99sewardj However, when a function returns, we don't delete the 1209024598e40c84666cc311a42c256bbf880db3ac99sewardj just-vacated StackFrame. Instead, it is retained in the list 1210024598e40c84666cc311a42c256bbf880db3ac99sewardj and will be re-used when the next call happens. This is so 1211024598e40c84666cc311a42c256bbf880db3ac99sewardj as to avoid constantly having to dynamically allocate and 1212024598e40c84666cc311a42c256bbf880db3ac99sewardj deallocate frames. */ 1213024598e40c84666cc311a42c256bbf880db3ac99sewardj struct _StackFrame* inner; 1214024598e40c84666cc311a42c256bbf880db3ac99sewardj struct _StackFrame* outer; 1215024598e40c84666cc311a42c256bbf880db3ac99sewardj Word depth; /* 0 for outermost; increases inwards */ 1216024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Information for each memory referencing instruction, for this 1217024598e40c84666cc311a42c256bbf880db3ac99sewardj instantiation of the function. The iinstances array is 1218024598e40c84666cc311a42c256bbf880db3ac99sewardj operated as a simple linear-probe hash table, which is 1219024598e40c84666cc311a42c256bbf880db3ac99sewardj dynamically expanded as necessary. Once critical thing is 1220024598e40c84666cc311a42c256bbf880db3ac99sewardj that an IInstance with a .insn_addr of zero is interpreted to 1221024598e40c84666cc311a42c256bbf880db3ac99sewardj mean that hash table slot is unused. This means we can't 1222024598e40c84666cc311a42c256bbf880db3ac99sewardj store an IInstance for address zero. */ 1223024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Note that htab initially points to htab_fixed. If htab_fixed 1224024598e40c84666cc311a42c256bbf880db3ac99sewardj turns out not to be big enough then htab is made to point to 1225024598e40c84666cc311a42c256bbf880db3ac99sewardj dynamically allocated memory. But it's often the case that 1226024598e40c84666cc311a42c256bbf880db3ac99sewardj htab_fixed is big enough, so this optimisation saves a huge 1227024598e40c84666cc311a42c256bbf880db3ac99sewardj number of sg_malloc/sg_free call pairs. */ 1228024598e40c84666cc311a42c256bbf880db3ac99sewardj IInstance* htab; 1229024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord htab_size; /* size of hash table, MAY ONLY BE A POWER OF 2 */ 1230024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord htab_used; /* number of hash table slots currently in use */ 1231024598e40c84666cc311a42c256bbf880db3ac99sewardj /* If this frame is currently making a call, then the following 1232024598e40c84666cc311a42c256bbf880db3ac99sewardj are relevant. */ 1233024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr sp_at_call; 1234024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr fp_at_call; 1235024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* /* of Addr */ blocks_added_by_call; 1236024598e40c84666cc311a42c256bbf880db3ac99sewardj /* See comment just above */ 1237024598e40c84666cc311a42c256bbf880db3ac99sewardj IInstance htab_fixed[N_HTAB_FIXED]; 1238024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1239024598e40c84666cc311a42c256bbf880db3ac99sewardj StackFrame; 1240024598e40c84666cc311a42c256bbf880db3ac99sewardj 1241024598e40c84666cc311a42c256bbf880db3ac99sewardj 1242024598e40c84666cc311a42c256bbf880db3ac99sewardj 1243024598e40c84666cc311a42c256bbf880db3ac99sewardj 1244024598e40c84666cc311a42c256bbf880db3ac99sewardj 1245024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Move this somewhere else? */ 1246024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Visit all Invars in the entire system. If 'isHeap' is True, change 1247024598e40c84666cc311a42c256bbf880db3ac99sewardj all Inv_Heap Invars that intersect [a,a+len) to Inv_Unknown. If 1248024598e40c84666cc311a42c256bbf880db3ac99sewardj 'isHeap' is False, do the same but to the Inv_Global{S,V} Invars 1249024598e40c84666cc311a42c256bbf880db3ac99sewardj instead. */ 1250024598e40c84666cc311a42c256bbf880db3ac99sewardj 1251024598e40c84666cc311a42c256bbf880db3ac99sewardj__attribute__((noinline)) 12529e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardjstatic void preen_global_Invar ( Invar* inv, Addr a, SizeT len ) 1253024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1254024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__Invars_preened++; 1255024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(len > 0); 1256024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(inv); 1257024598e40c84666cc311a42c256bbf880db3ac99sewardj switch (inv->tag) { 12589e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj case Inv_Global: 12599e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj tl_assert(inv->Inv.Global.nd); 12609e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj tl_assert(inv->Inv.Global.nd->szB > 0); 12619e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj if (0) VG_(printf)("preen_Invar Global %#lx %lu\n", 12629e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj inv->Inv.Global.nd->addr, 12639e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj inv->Inv.Global.nd->szB); 12649e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj if (0 == cmp_nonempty_intervals(a, len, inv->Inv.Global.nd->addr, 12659e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj inv->Inv.Global.nd->szB)) { 1266024598e40c84666cc311a42c256bbf880db3ac99sewardj inv->tag = Inv_Unknown; 1267024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__Invars_changed++; 1268024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1269024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 12709e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj case Inv_Stack0: 12719e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj case Inv_StackN: 1272024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_Unknown: 1273024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 1274110e0f8e7effba90dc43d9763ebacdc61e4ae678florian case Inv_Unset: /* this should never happen */ 1275110e0f8e7effba90dc43d9763ebacdc61e4ae678florian /* fallthrough */ 12769e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj default: 12779e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj tl_assert(0); 1278024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1279024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1280024598e40c84666cc311a42c256bbf880db3ac99sewardj 1281024598e40c84666cc311a42c256bbf880db3ac99sewardj__attribute__((noinline)) 12829e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardjstatic void preen_global_Invars ( Addr a, SizeT len ) 1283024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1284024598e40c84666cc311a42c256bbf880db3ac99sewardj Int i; 1285024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord u; 1286024598e40c84666cc311a42c256bbf880db3ac99sewardj StackFrame* frame; 1287024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(len > 0); 1288024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < VG_N_THREADS; i++) { 12899e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj frame = shadowStacks[i]; 12909e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj if (!frame) 12919e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj continue; /* no frames for this thread */ 12929e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj /* start from the innermost frame */ 12939e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj while (frame->inner) 12949e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj frame = frame->inner; 12959e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj tl_assert(frame->outer); 12969e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj /* work through the frames from innermost to outermost. The 12979e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj order isn't important; we just need to ensure we visit each 12989e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj frame once (including those which are not actually active, 12999e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj more 'inner' than the 'innermost active frame', viz, just 13009e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj hanging around waiting to be used, when the current innermost 13019e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj active frame makes more calls. See comments on definition of 13029e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj struct _StackFrame. */ 13039e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj for (; frame; frame = frame->outer) { 1304024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord xx = 0; /* sanity check only; count of used htab entries */ 13059e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj if (!frame->htab) 13069e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj continue; /* frame not in use. See shadowStack_unwind(). */ 1307024598e40c84666cc311a42c256bbf880db3ac99sewardj for (u = 0; u < frame->htab_size; u++) { 1308024598e40c84666cc311a42c256bbf880db3ac99sewardj IInstance* ii = &frame->htab[u]; 1309024598e40c84666cc311a42c256bbf880db3ac99sewardj if (ii->insn_addr == 0) 1310024598e40c84666cc311a42c256bbf880db3ac99sewardj continue; /* not in use */ 13119e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj if (0) { pp_Invar(&ii->invar); VG_(printf)(" x\n"); } 13129e1bed8b5c657d276d3b6410edce3aa1f3877d0bsewardj preen_global_Invar( &ii->invar, a, len ); 1313024598e40c84666cc311a42c256bbf880db3ac99sewardj xx++; 1314024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1315024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(xx == frame->htab_used); 1316024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1317024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1318024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1319024598e40c84666cc311a42c256bbf880db3ac99sewardj 1320024598e40c84666cc311a42c256bbf880db3ac99sewardj 1321024598e40c84666cc311a42c256bbf880db3ac99sewardj/* XXX this should be >> 2 on ppc32/64 since the bottom two bits 1322024598e40c84666cc311a42c256bbf880db3ac99sewardj of the ip are guaranteed to be zero */ 1323024598e40c84666cc311a42c256bbf880db3ac99sewardjinline static UWord compute_II_hash ( Addr ip, UWord htab_size ) { 1324024598e40c84666cc311a42c256bbf880db3ac99sewardj return (ip >> 0) & (htab_size - 1); 1325024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1326024598e40c84666cc311a42c256bbf880db3ac99sewardj 1327024598e40c84666cc311a42c256bbf880db3ac99sewardj__attribute__((noinline)) 1328024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void initialise_II_hash_table ( StackFrame* sf ) 1329024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1330024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord i; 1331024598e40c84666cc311a42c256bbf880db3ac99sewardj sf->htab_size = N_HTAB_FIXED; /* initial hash table size */ 1332024598e40c84666cc311a42c256bbf880db3ac99sewardj sf->htab = &sf->htab_fixed[0]; 1333024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(sf->htab); 1334024598e40c84666cc311a42c256bbf880db3ac99sewardj sf->htab_used = 0; 1335024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < sf->htab_size; i++) 1336024598e40c84666cc311a42c256bbf880db3ac99sewardj sf->htab[i].insn_addr = 0; /* NOT IN USE */ 1337024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1338024598e40c84666cc311a42c256bbf880db3ac99sewardj 1339024598e40c84666cc311a42c256bbf880db3ac99sewardj 1340024598e40c84666cc311a42c256bbf880db3ac99sewardj__attribute__((noinline)) 1341024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void resize_II_hash_table ( StackFrame* sf ) 1342024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1343024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord i, j, ix, old_size, new_size; 1344024598e40c84666cc311a42c256bbf880db3ac99sewardj IInstance *old_htab, *new_htab, *old; 1345024598e40c84666cc311a42c256bbf880db3ac99sewardj 1346024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(sf && sf->htab); 1347024598e40c84666cc311a42c256bbf880db3ac99sewardj old_size = sf->htab_size; 1348024598e40c84666cc311a42c256bbf880db3ac99sewardj new_size = 2 * old_size; 1349024598e40c84666cc311a42c256bbf880db3ac99sewardj old_htab = sf->htab; 1350024598e40c84666cc311a42c256bbf880db3ac99sewardj new_htab = sg_malloc( "di.sg_main.rIht.1", 1351024598e40c84666cc311a42c256bbf880db3ac99sewardj new_size * sizeof(IInstance) ); 1352024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < new_size; i++) { 1353024598e40c84666cc311a42c256bbf880db3ac99sewardj new_htab[i].insn_addr = 0; /* NOT IN USE */ 1354024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1355024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < old_size; i++) { 1356024598e40c84666cc311a42c256bbf880db3ac99sewardj old = &old_htab[i]; 1357024598e40c84666cc311a42c256bbf880db3ac99sewardj if (old->insn_addr == 0 /* NOT IN USE */) 1358024598e40c84666cc311a42c256bbf880db3ac99sewardj continue; 1359024598e40c84666cc311a42c256bbf880db3ac99sewardj ix = compute_II_hash(old->insn_addr, new_size); 1360024598e40c84666cc311a42c256bbf880db3ac99sewardj /* find out where to put this, in the new table */ 1361024598e40c84666cc311a42c256bbf880db3ac99sewardj j = new_size; 1362024598e40c84666cc311a42c256bbf880db3ac99sewardj while (1) { 1363024598e40c84666cc311a42c256bbf880db3ac99sewardj if (new_htab[ix].insn_addr == 0) 1364024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 1365024598e40c84666cc311a42c256bbf880db3ac99sewardj /* This can't ever happen, because it would mean the new 1366024598e40c84666cc311a42c256bbf880db3ac99sewardj table is full; that isn't allowed -- even the old table is 1367024598e40c84666cc311a42c256bbf880db3ac99sewardj only allowed to become half full. */ 1368024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(j > 0); 1369024598e40c84666cc311a42c256bbf880db3ac99sewardj j--; 1370024598e40c84666cc311a42c256bbf880db3ac99sewardj ix++; if (ix == new_size) ix = 0; 1371024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1372024598e40c84666cc311a42c256bbf880db3ac99sewardj /* copy the old entry to this location */ 1373024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(ix < new_size); 1374024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(new_htab[ix].insn_addr == 0); 1375024598e40c84666cc311a42c256bbf880db3ac99sewardj new_htab[ix] = *old; 1376024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(new_htab[ix].insn_addr != 0); 1377024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1378024598e40c84666cc311a42c256bbf880db3ac99sewardj /* all entries copied; free old table. */ 1379024598e40c84666cc311a42c256bbf880db3ac99sewardj if (old_htab != &sf->htab_fixed[0]) 1380024598e40c84666cc311a42c256bbf880db3ac99sewardj sg_free(old_htab); 1381024598e40c84666cc311a42c256bbf880db3ac99sewardj sf->htab = new_htab; 1382024598e40c84666cc311a42c256bbf880db3ac99sewardj sf->htab_size = new_size; 1383024598e40c84666cc311a42c256bbf880db3ac99sewardj /* check sf->htab_used is correct. Optional and a bit expensive 1384024598e40c84666cc311a42c256bbf880db3ac99sewardj but anyway: */ 1385024598e40c84666cc311a42c256bbf880db3ac99sewardj j = 0; 1386024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < new_size; i++) { 1387024598e40c84666cc311a42c256bbf880db3ac99sewardj if (new_htab[i].insn_addr != 0) { 1388024598e40c84666cc311a42c256bbf880db3ac99sewardj j++; 1389024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1390024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1391024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(j == sf->htab_used); 1392024598e40c84666cc311a42c256bbf880db3ac99sewardj if (0) VG_(printf)("resized tab for SF %p to %lu\n", sf, new_size); 1393024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1394024598e40c84666cc311a42c256bbf880db3ac99sewardj 1395024598e40c84666cc311a42c256bbf880db3ac99sewardj 1396024598e40c84666cc311a42c256bbf880db3ac99sewardj__attribute__((noinline)) 1397024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic IInstance* find_or_create_IInstance_SLOW ( 1398024598e40c84666cc311a42c256bbf880db3ac99sewardj StackFrame* sf, 1399024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr ip, 1400024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* /* StackBlock */ ip_frameblocks 1401024598e40c84666cc311a42c256bbf880db3ac99sewardj ) 1402024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1403024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord i, ix; 1404024598e40c84666cc311a42c256bbf880db3ac99sewardj 1405024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__htab_searches++; 1406024598e40c84666cc311a42c256bbf880db3ac99sewardj 1407024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(sf); 1408024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(sf->htab); 1409024598e40c84666cc311a42c256bbf880db3ac99sewardj 1410024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Make sure the table loading doesn't get too high. */ 1411024598e40c84666cc311a42c256bbf880db3ac99sewardj if (UNLIKELY(2 * sf->htab_used >= 1 * sf->htab_size)) { 1412024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__htab_resizes++; 1413024598e40c84666cc311a42c256bbf880db3ac99sewardj resize_II_hash_table(sf); 1414024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1415024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(2 * sf->htab_used <= sf->htab_size); 1416024598e40c84666cc311a42c256bbf880db3ac99sewardj 1417024598e40c84666cc311a42c256bbf880db3ac99sewardj ix = compute_II_hash(ip, sf->htab_size); 1418024598e40c84666cc311a42c256bbf880db3ac99sewardj i = sf->htab_size; 1419024598e40c84666cc311a42c256bbf880db3ac99sewardj while (1) { 1420024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__htab_probes++; 1421024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Note that because of the way the fast-case handler works, 1422024598e40c84666cc311a42c256bbf880db3ac99sewardj these two tests are actually redundant in the first iteration 1423024598e40c84666cc311a42c256bbf880db3ac99sewardj of this loop. (Except they aren't redundant if the code just 1424024598e40c84666cc311a42c256bbf880db3ac99sewardj above resized the table first. :-) */ 1425024598e40c84666cc311a42c256bbf880db3ac99sewardj if (sf->htab[ix].insn_addr == ip) 1426024598e40c84666cc311a42c256bbf880db3ac99sewardj return &sf->htab[ix]; 1427024598e40c84666cc311a42c256bbf880db3ac99sewardj if (sf->htab[ix].insn_addr == 0) 1428024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 1429024598e40c84666cc311a42c256bbf880db3ac99sewardj /* If i ever gets to zero and we have found neither what we're 1430024598e40c84666cc311a42c256bbf880db3ac99sewardj looking for nor an empty slot, the table must be full. Which 1431024598e40c84666cc311a42c256bbf880db3ac99sewardj isn't possible -- we monitor the load factor to ensure it 1432024598e40c84666cc311a42c256bbf880db3ac99sewardj doesn't get above say 50%; if that ever does happen the table 1433024598e40c84666cc311a42c256bbf880db3ac99sewardj is resized. */ 1434024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(i > 0); 1435024598e40c84666cc311a42c256bbf880db3ac99sewardj i--; 1436024598e40c84666cc311a42c256bbf880db3ac99sewardj ix++; 1437024598e40c84666cc311a42c256bbf880db3ac99sewardj if (ix == sf->htab_size) ix = 0; 1438024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1439024598e40c84666cc311a42c256bbf880db3ac99sewardj 1440024598e40c84666cc311a42c256bbf880db3ac99sewardj /* So now we've found a free slot at ix, and we can use that. */ 1441024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(sf->htab[ix].insn_addr == 0); 1442024598e40c84666cc311a42c256bbf880db3ac99sewardj 1443024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Add a new record in this slot. */ 1444024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(ip != 0); /* CAN'T REPRESENT THIS */ 1445024598e40c84666cc311a42c256bbf880db3ac99sewardj sf->htab[ix].insn_addr = ip; 1446024598e40c84666cc311a42c256bbf880db3ac99sewardj sf->htab[ix].blocks = ip_frameblocks; 1447024598e40c84666cc311a42c256bbf880db3ac99sewardj sf->htab[ix].invar.tag = Inv_Unset; 1448024598e40c84666cc311a42c256bbf880db3ac99sewardj sf->htab_used++; 1449024598e40c84666cc311a42c256bbf880db3ac99sewardj return &sf->htab[ix]; 1450024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1451024598e40c84666cc311a42c256bbf880db3ac99sewardj 1452024598e40c84666cc311a42c256bbf880db3ac99sewardj 1453024598e40c84666cc311a42c256bbf880db3ac99sewardjinline 1454024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic IInstance* find_or_create_IInstance ( 1455024598e40c84666cc311a42c256bbf880db3ac99sewardj StackFrame* sf, 1456024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr ip, 1457024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* /* StackBlock */ ip_frameblocks 1458024598e40c84666cc311a42c256bbf880db3ac99sewardj ) 1459024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1460024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord ix = compute_II_hash(ip, sf->htab_size); 1461024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Is it in the first slot we come to? */ 1462024598e40c84666cc311a42c256bbf880db3ac99sewardj if (LIKELY(sf->htab[ix].insn_addr == ip)) { 1463024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__htab_fast++; 1464024598e40c84666cc311a42c256bbf880db3ac99sewardj return &sf->htab[ix]; 1465024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1466024598e40c84666cc311a42c256bbf880db3ac99sewardj /* If the first slot we come to is empty, bag it. */ 1467024598e40c84666cc311a42c256bbf880db3ac99sewardj if (LIKELY(sf->htab[ix].insn_addr == 0)) { 1468024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__htab_fast++; 1469024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(ip != 0); 1470024598e40c84666cc311a42c256bbf880db3ac99sewardj sf->htab[ix].insn_addr = ip; 1471024598e40c84666cc311a42c256bbf880db3ac99sewardj sf->htab[ix].blocks = ip_frameblocks; 1472024598e40c84666cc311a42c256bbf880db3ac99sewardj sf->htab[ix].invar.tag = Inv_Unset; 1473024598e40c84666cc311a42c256bbf880db3ac99sewardj sf->htab_used++; 1474024598e40c84666cc311a42c256bbf880db3ac99sewardj return &sf->htab[ix]; 1475024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1476024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Otherwise we hand off to the slow case, which searches other 1477024598e40c84666cc311a42c256bbf880db3ac99sewardj slots, and optionally resizes the table if necessary. */ 1478024598e40c84666cc311a42c256bbf880db3ac99sewardj return find_or_create_IInstance_SLOW( sf, ip, ip_frameblocks ); 1479024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1480024598e40c84666cc311a42c256bbf880db3ac99sewardj 1481024598e40c84666cc311a42c256bbf880db3ac99sewardj 1482024598e40c84666cc311a42c256bbf880db3ac99sewardj__attribute__((noinline)) 1483024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic Addr calculate_StackBlock_EA ( StackBlock* descr, 1484024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr sp, Addr fp ) { 1485024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord w1 = (UWord)descr->base; 1486024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord w2 = (UWord)(descr->spRel ? sp : fp); 1487024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord ea = w1 + w2; 1488024598e40c84666cc311a42c256bbf880db3ac99sewardj return ea; 1489024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1490024598e40c84666cc311a42c256bbf880db3ac99sewardj 1491024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Given an array of StackBlocks, return an array of Addrs, holding 1492024598e40c84666cc311a42c256bbf880db3ac99sewardj their effective addresses. Caller deallocates result array. */ 1493024598e40c84666cc311a42c256bbf880db3ac99sewardj__attribute__((noinline)) 1494024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic XArray* /* Addr */ calculate_StackBlock_EAs ( 1495024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* /* StackBlock */ blocks, 1496024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr sp, Addr fp 1497024598e40c84666cc311a42c256bbf880db3ac99sewardj ) 1498024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1499024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* res; 1500024598e40c84666cc311a42c256bbf880db3ac99sewardj Word i, n = VG_(sizeXA)( blocks ); 1501024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(n > 0); 1502024598e40c84666cc311a42c256bbf880db3ac99sewardj res = VG_(newXA)( sg_malloc, "di.sg_main.cSBE.1", sg_free, sizeof(Addr) ); 1503024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < n; i++) { 1504024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock* blk = VG_(indexXA)( blocks, i ); 1505024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr ea = calculate_StackBlock_EA( blk, sp, fp ); 1506024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(addToXA)( res, &ea ); 1507024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1508024598e40c84666cc311a42c256bbf880db3ac99sewardj return res; 1509024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1510024598e40c84666cc311a42c256bbf880db3ac99sewardj 1511024598e40c84666cc311a42c256bbf880db3ac99sewardj 1512024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Try to classify the block into which a memory access falls, and 1513024598e40c84666cc311a42c256bbf880db3ac99sewardj write the result in 'inv'. This writes all relevant fields of 1514024598e40c84666cc311a42c256bbf880db3ac99sewardj 'inv'. */ 1515024598e40c84666cc311a42c256bbf880db3ac99sewardj__attribute__((noinline)) 1516024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void classify_address ( /*OUT*/Invar* inv, 1517024598e40c84666cc311a42c256bbf880db3ac99sewardj ThreadId tid, 1518024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr ea, Addr sp, Addr fp, 1519024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord szB, 1520024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* /* of StackBlock */ thisInstrBlocks ) 1521024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1522024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(szB > 0); 1523024598e40c84666cc311a42c256bbf880db3ac99sewardj /* First, look in the stack blocks accessible in this instruction's 1524024598e40c84666cc311a42c256bbf880db3ac99sewardj frame. */ 1525024598e40c84666cc311a42c256bbf880db3ac99sewardj { 1526024598e40c84666cc311a42c256bbf880db3ac99sewardj Word i, nBlocks = VG_(sizeXA)( thisInstrBlocks ); 1527024598e40c84666cc311a42c256bbf880db3ac99sewardj if (nBlocks == 0) stats__t_i_b_empty++; 1528024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < nBlocks; i++) { 1529024598e40c84666cc311a42c256bbf880db3ac99sewardj StackBlock* descr = VG_(indexXA)( thisInstrBlocks, i ); 1530024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr bea = calculate_StackBlock_EA( descr, sp, fp ); 1531024598e40c84666cc311a42c256bbf880db3ac99sewardj if (bea <= ea && ea + szB <= bea + descr->szB) { 1532024598e40c84666cc311a42c256bbf880db3ac99sewardj /* found it */ 1533024598e40c84666cc311a42c256bbf880db3ac99sewardj inv->tag = Inv_Stack0; 1534024598e40c84666cc311a42c256bbf880db3ac99sewardj inv->Inv.Stack0.addr = bea; 1535024598e40c84666cc311a42c256bbf880db3ac99sewardj inv->Inv.Stack0.szB = descr->szB; 1536024598e40c84666cc311a42c256bbf880db3ac99sewardj inv->Inv.Stack0.descr = descr; 1537024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__classify_Stack0++; 1538024598e40c84666cc311a42c256bbf880db3ac99sewardj return; 1539024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1540024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1541024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1542024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Look in this thread's query cache */ 1543024598e40c84666cc311a42c256bbf880db3ac99sewardj { Word i; 1544024598e40c84666cc311a42c256bbf880db3ac99sewardj QCache* cache = &qcaches[tid]; 1545024598e40c84666cc311a42c256bbf880db3ac99sewardj static UWord ctr = 0; 1546024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__qcache_queries++; 1547024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = 0; i < cache->nInUse; i++) { 1548024598e40c84666cc311a42c256bbf880db3ac99sewardj if (0) /* expensive in a loop like this */ 1549024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(cache->elems[i].addr + cache->elems[i].szB != 0); 1550024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__qcache_probes++; 1551024598e40c84666cc311a42c256bbf880db3ac99sewardj if (is_subinterval_of(cache->elems[i].addr, 1552024598e40c84666cc311a42c256bbf880db3ac99sewardj cache->elems[i].szB, ea, szB)) { 1553024598e40c84666cc311a42c256bbf880db3ac99sewardj if (i > 0 1554024598e40c84666cc311a42c256bbf880db3ac99sewardj && (ctr++ & (QCACHE_ADVANCE_EVERY-1)) == 0) { 1555024598e40c84666cc311a42c256bbf880db3ac99sewardj QCElem tmp; 1556024598e40c84666cc311a42c256bbf880db3ac99sewardj tmp = cache->elems[i-1]; 1557024598e40c84666cc311a42c256bbf880db3ac99sewardj cache->elems[i-1] = cache->elems[i]; 1558024598e40c84666cc311a42c256bbf880db3ac99sewardj cache->elems[i] = tmp; 1559024598e40c84666cc311a42c256bbf880db3ac99sewardj i--; 1560024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1561024598e40c84666cc311a42c256bbf880db3ac99sewardj *inv = cache->elems[i].inv; 1562024598e40c84666cc311a42c256bbf880db3ac99sewardj return; 1563024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1564024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1565024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__qcache_misses++; 1566024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1567024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Ok, so it's not a block in the top frame. Perhaps it's a block 1568024598e40c84666cc311a42c256bbf880db3ac99sewardj in some calling frame? Consult this thread's stack-block 1569024598e40c84666cc311a42c256bbf880db3ac99sewardj interval tree to find out. */ 1570024598e40c84666cc311a42c256bbf880db3ac99sewardj { StackTreeNode* nd = find_StackTreeNode( siTrees[tid], ea ); 1571024598e40c84666cc311a42c256bbf880db3ac99sewardj /* We know that [ea,ea+1) is in the block, but we need to 1572024598e40c84666cc311a42c256bbf880db3ac99sewardj restrict to the case where the whole access falls within 1573024598e40c84666cc311a42c256bbf880db3ac99sewardj it. */ 1574024598e40c84666cc311a42c256bbf880db3ac99sewardj if (nd && !is_subinterval_of(nd->addr, nd->szB, ea, szB)) { 1575024598e40c84666cc311a42c256bbf880db3ac99sewardj nd = NULL; 1576024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1577024598e40c84666cc311a42c256bbf880db3ac99sewardj if (nd) { 1578024598e40c84666cc311a42c256bbf880db3ac99sewardj /* found it */ 1579024598e40c84666cc311a42c256bbf880db3ac99sewardj inv->tag = Inv_StackN; 1580024598e40c84666cc311a42c256bbf880db3ac99sewardj inv->Inv.StackN.nd = nd; 1581024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__classify_StackN++; 1582024598e40c84666cc311a42c256bbf880db3ac99sewardj goto out; 1583024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1584024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1585024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Not in a stack block. Try the global pool. */ 1586024598e40c84666cc311a42c256bbf880db3ac99sewardj { GlobalTreeNode* nd = find_GlobalTreeNode(giTree, ea); 1587024598e40c84666cc311a42c256bbf880db3ac99sewardj /* We know that [ea,ea+1) is in the block, but we need to 1588024598e40c84666cc311a42c256bbf880db3ac99sewardj restrict to the case where the whole access falls within 1589024598e40c84666cc311a42c256bbf880db3ac99sewardj it. */ 1590024598e40c84666cc311a42c256bbf880db3ac99sewardj if (nd && !is_subinterval_of(nd->addr, nd->szB, ea, szB)) { 1591024598e40c84666cc311a42c256bbf880db3ac99sewardj nd = NULL; 1592024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1593024598e40c84666cc311a42c256bbf880db3ac99sewardj if (nd) { 1594024598e40c84666cc311a42c256bbf880db3ac99sewardj /* found it */ 1595024598e40c84666cc311a42c256bbf880db3ac99sewardj inv->tag = Inv_Global; 1596024598e40c84666cc311a42c256bbf880db3ac99sewardj inv->Inv.Global.nd = nd; 1597024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__classify_Global++; 1598024598e40c84666cc311a42c256bbf880db3ac99sewardj goto out; 1599024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1600024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1601024598e40c84666cc311a42c256bbf880db3ac99sewardj /* No idea - give up. */ 1602024598e40c84666cc311a42c256bbf880db3ac99sewardj inv->tag = Inv_Unknown; 1603024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__classify_Unknown++; 1604024598e40c84666cc311a42c256bbf880db3ac99sewardj 1605024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Update the cache */ 1606024598e40c84666cc311a42c256bbf880db3ac99sewardj out: 1607024598e40c84666cc311a42c256bbf880db3ac99sewardj { Addr toadd_addr = 0; 1608024598e40c84666cc311a42c256bbf880db3ac99sewardj SizeT toadd_szB = 0; 1609024598e40c84666cc311a42c256bbf880db3ac99sewardj QCache* cache = &qcaches[tid]; 1610024598e40c84666cc311a42c256bbf880db3ac99sewardj 1611024598e40c84666cc311a42c256bbf880db3ac99sewardj static UWord ctr = 0; 1612024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool show = False; 1613024598e40c84666cc311a42c256bbf880db3ac99sewardj if (0 && 0 == (ctr++ & 0x1FFFFF)) show = True; 1614024598e40c84666cc311a42c256bbf880db3ac99sewardj 1615024598e40c84666cc311a42c256bbf880db3ac99sewardj if (show) QCache__pp(cache, "before upd"); 1616024598e40c84666cc311a42c256bbf880db3ac99sewardj 1617024598e40c84666cc311a42c256bbf880db3ac99sewardj switch (inv->tag) { 1618024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_Global: 1619024598e40c84666cc311a42c256bbf880db3ac99sewardj toadd_addr = inv->Inv.Global.nd->addr; 1620024598e40c84666cc311a42c256bbf880db3ac99sewardj toadd_szB = inv->Inv.Global.nd->szB; 1621024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 1622024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_StackN: 1623024598e40c84666cc311a42c256bbf880db3ac99sewardj toadd_addr = inv->Inv.StackN.nd->addr; 1624024598e40c84666cc311a42c256bbf880db3ac99sewardj toadd_szB = inv->Inv.StackN.nd->szB; 1625024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 1626024598e40c84666cc311a42c256bbf880db3ac99sewardj case Inv_Unknown: { 1627024598e40c84666cc311a42c256bbf880db3ac99sewardj /* This is more complex. We need to figure out the 1628024598e40c84666cc311a42c256bbf880db3ac99sewardj intersection of the "holes" in the global and stack 1629024598e40c84666cc311a42c256bbf880db3ac99sewardj interval trees into which [ea,ea+szB) falls. This is 1630024598e40c84666cc311a42c256bbf880db3ac99sewardj further complicated by the fact that [ea,ea+szB) might 1631024598e40c84666cc311a42c256bbf880db3ac99sewardj not fall cleanly into a hole; it may instead fall across 1632024598e40c84666cc311a42c256bbf880db3ac99sewardj the boundary of a stack or global block. In that case 1633024598e40c84666cc311a42c256bbf880db3ac99sewardj we just ignore it and don't update the cache, since we 1634024598e40c84666cc311a42c256bbf880db3ac99sewardj have no way to represent this situation precisely. */ 1635024598e40c84666cc311a42c256bbf880db3ac99sewardj StackTreeNode sNegInf, sPosInf, sKey, *sLB, *sUB; 1636024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalTreeNode gNegInf, gPosInf, gKey, *gLB, *gUB; 1637024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr gMin, gMax, sMin, sMax, uMin, uMax; 1638024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool sOK, gOK; 1639024598e40c84666cc311a42c256bbf880db3ac99sewardj sNegInf.addr = 0; 1640024598e40c84666cc311a42c256bbf880db3ac99sewardj sNegInf.szB = 1; 1641024598e40c84666cc311a42c256bbf880db3ac99sewardj sPosInf.addr = ~(UWord)0; 1642024598e40c84666cc311a42c256bbf880db3ac99sewardj sPosInf.szB = 1; 1643024598e40c84666cc311a42c256bbf880db3ac99sewardj gNegInf.addr = 0; 1644024598e40c84666cc311a42c256bbf880db3ac99sewardj gNegInf.szB = 1; 1645024598e40c84666cc311a42c256bbf880db3ac99sewardj gPosInf.addr = ~(UWord)0; 1646024598e40c84666cc311a42c256bbf880db3ac99sewardj gPosInf.szB = 1; 1647024598e40c84666cc311a42c256bbf880db3ac99sewardj sKey.addr = ea; 1648024598e40c84666cc311a42c256bbf880db3ac99sewardj sKey.szB = szB; 1649024598e40c84666cc311a42c256bbf880db3ac99sewardj gKey.addr = ea; 1650024598e40c84666cc311a42c256bbf880db3ac99sewardj gKey.szB = szB; 165116eef85229a8d8a00dd8edd8f32a4a91cb6ba7a8florian if (0) VG_(printf)("Tree sizes %lu %lu\n", 1652024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(sizeFM)(siTrees[tid]), VG_(sizeFM)(giTree)); 1653024598e40c84666cc311a42c256bbf880db3ac99sewardj sOK = VG_(findBoundsFM)( siTrees[tid], 16549520845eeeb59e9eafa5c6fb0d68b4a392e94f41sewardj (UWord*)&sLB, NULL/*unused*/, 16559520845eeeb59e9eafa5c6fb0d68b4a392e94f41sewardj (UWord*)&sUB, NULL/*unused*/, 16569520845eeeb59e9eafa5c6fb0d68b4a392e94f41sewardj (UWord)&sNegInf, 0/*unused*/, 16579520845eeeb59e9eafa5c6fb0d68b4a392e94f41sewardj (UWord)&sPosInf, 0/*unused*/, 1658024598e40c84666cc311a42c256bbf880db3ac99sewardj (UWord)&sKey ); 1659024598e40c84666cc311a42c256bbf880db3ac99sewardj gOK = VG_(findBoundsFM)( giTree, 16609520845eeeb59e9eafa5c6fb0d68b4a392e94f41sewardj (UWord*)&gLB, NULL/*unused*/, 16619520845eeeb59e9eafa5c6fb0d68b4a392e94f41sewardj (UWord*)&gUB, NULL/*unused*/, 16629520845eeeb59e9eafa5c6fb0d68b4a392e94f41sewardj (UWord)&gNegInf, 0/*unused*/, 16639520845eeeb59e9eafa5c6fb0d68b4a392e94f41sewardj (UWord)&gPosInf, 0/*unused*/, 1664024598e40c84666cc311a42c256bbf880db3ac99sewardj (UWord)&gKey ); 1665024598e40c84666cc311a42c256bbf880db3ac99sewardj if (!(sOK && gOK)) { 1666024598e40c84666cc311a42c256bbf880db3ac99sewardj /* If this happens, then [ea,ea+szB) partially overlaps 1667024598e40c84666cc311a42c256bbf880db3ac99sewardj a heap or stack block. We can't represent that, so 1668024598e40c84666cc311a42c256bbf880db3ac99sewardj just forget it (should be very rare). However, do 1669024598e40c84666cc311a42c256bbf880db3ac99sewardj maximum sanity checks first. In such a 1670024598e40c84666cc311a42c256bbf880db3ac99sewardj partial overlap case, it can't be the case that both 1671024598e40c84666cc311a42c256bbf880db3ac99sewardj [ea] and [ea+szB-1] overlap the same block, since if 1672024598e40c84666cc311a42c256bbf880db3ac99sewardj that were indeed the case then it wouldn't be a 1673024598e40c84666cc311a42c256bbf880db3ac99sewardj partial overlap; rather it would simply fall inside 1674024598e40c84666cc311a42c256bbf880db3ac99sewardj that block entirely and we shouldn't be inside this 1675024598e40c84666cc311a42c256bbf880db3ac99sewardj conditional at all. */ 1676024598e40c84666cc311a42c256bbf880db3ac99sewardj if (!sOK) { 1677024598e40c84666cc311a42c256bbf880db3ac99sewardj StackTreeNode *ndFirst, *ndLast; 1678024598e40c84666cc311a42c256bbf880db3ac99sewardj ndFirst = find_StackTreeNode( siTrees[tid], ea ); 1679024598e40c84666cc311a42c256bbf880db3ac99sewardj ndLast = find_StackTreeNode( siTrees[tid], ea+szB-1 ); 1680024598e40c84666cc311a42c256bbf880db3ac99sewardj /* if both ends of the range fall inside a block, 1681024598e40c84666cc311a42c256bbf880db3ac99sewardj they can't be in the same block. */ 1682024598e40c84666cc311a42c256bbf880db3ac99sewardj if (ndFirst && ndLast) 1683024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(ndFirst != ndLast); 1684024598e40c84666cc311a42c256bbf880db3ac99sewardj /* for each end of the range, if it is in a block, 1685024598e40c84666cc311a42c256bbf880db3ac99sewardj the range as a whole can't be entirely within the 1686024598e40c84666cc311a42c256bbf880db3ac99sewardj block. */ 1687024598e40c84666cc311a42c256bbf880db3ac99sewardj if (ndFirst) 1688024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(!is_subinterval_of(ndFirst->addr, 1689024598e40c84666cc311a42c256bbf880db3ac99sewardj ndFirst->szB, ea, szB)); 1690024598e40c84666cc311a42c256bbf880db3ac99sewardj if (ndLast) 1691024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(!is_subinterval_of(ndLast->addr, 1692024598e40c84666cc311a42c256bbf880db3ac99sewardj ndLast->szB, ea, szB)); 1693024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1694024598e40c84666cc311a42c256bbf880db3ac99sewardj if (!gOK) { 1695024598e40c84666cc311a42c256bbf880db3ac99sewardj GlobalTreeNode *ndFirst, *ndLast; 1696024598e40c84666cc311a42c256bbf880db3ac99sewardj ndFirst = find_GlobalTreeNode( giTree, ea ); 1697024598e40c84666cc311a42c256bbf880db3ac99sewardj ndLast = find_GlobalTreeNode( giTree, ea+szB-1 ); 1698024598e40c84666cc311a42c256bbf880db3ac99sewardj /* if both ends of the range fall inside a block, 1699024598e40c84666cc311a42c256bbf880db3ac99sewardj they can't be in the same block. */ 1700024598e40c84666cc311a42c256bbf880db3ac99sewardj if (ndFirst && ndLast) 1701024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(ndFirst != ndLast); 1702024598e40c84666cc311a42c256bbf880db3ac99sewardj /* for each end of the range, if it is in a block, 1703024598e40c84666cc311a42c256bbf880db3ac99sewardj the range as a whole can't be entirely within the 1704024598e40c84666cc311a42c256bbf880db3ac99sewardj block. */ 1705024598e40c84666cc311a42c256bbf880db3ac99sewardj if (ndFirst) 1706024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(!is_subinterval_of(ndFirst->addr, 1707024598e40c84666cc311a42c256bbf880db3ac99sewardj ndFirst->szB, ea, szB)); 1708024598e40c84666cc311a42c256bbf880db3ac99sewardj if (ndLast) 1709024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(!is_subinterval_of(ndLast->addr, 1710024598e40c84666cc311a42c256bbf880db3ac99sewardj ndLast->szB, ea, szB)); 1711024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1712024598e40c84666cc311a42c256bbf880db3ac99sewardj if (0) VG_(printf)("overlapping blocks in cache\n"); 1713024598e40c84666cc311a42c256bbf880db3ac99sewardj return; 1714024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1715024598e40c84666cc311a42c256bbf880db3ac99sewardj sMin = sLB == &sNegInf ? 0 : (sLB->addr + sLB->szB); 1716024598e40c84666cc311a42c256bbf880db3ac99sewardj sMax = sUB == &sPosInf ? ~(UWord)0 : (sUB->addr - 1); 1717024598e40c84666cc311a42c256bbf880db3ac99sewardj gMin = gLB == &gNegInf ? 0 : (gLB->addr + gLB->szB); 1718024598e40c84666cc311a42c256bbf880db3ac99sewardj gMax = gUB == &gPosInf ? ~(UWord)0 : (gUB->addr - 1); 1719024598e40c84666cc311a42c256bbf880db3ac99sewardj if (0) VG_(printf)("sMin %lx sMax %lx gMin %lx gMax %lx\n", 1720024598e40c84666cc311a42c256bbf880db3ac99sewardj sMin, sMax, gMin, gMax); 1721024598e40c84666cc311a42c256bbf880db3ac99sewardj /* [sMin,sMax] and [gMin,gMax] must both contain 1722024598e40c84666cc311a42c256bbf880db3ac99sewardj [ea,ea+szB) (right?) That implies they must overlap at 1723024598e40c84666cc311a42c256bbf880db3ac99sewardj at least over [ea,ea+szB). */ 1724024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(sMin <= ea && ea+szB-1 <= sMax); 1725024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(gMin <= ea && ea+szB-1 <= gMax); 1726024598e40c84666cc311a42c256bbf880db3ac99sewardj /* So now compute their intersection. */ 1727024598e40c84666cc311a42c256bbf880db3ac99sewardj uMin = Addr__max( sMin, gMin ); 1728024598e40c84666cc311a42c256bbf880db3ac99sewardj uMax = Addr__min( sMax, gMax ); 1729024598e40c84666cc311a42c256bbf880db3ac99sewardj if (0) VG_(printf)("uMin %lx uMax %lx\n", uMin, uMax); 1730024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(uMin <= uMax); 1731024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(uMin <= ea && ea+szB-1 <= uMax); 1732024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Finally, we can park [uMin,uMax] in the cache. However, 1733024598e40c84666cc311a42c256bbf880db3ac99sewardj if uMax is ~0, we can't represent the difference; hence 1734024598e40c84666cc311a42c256bbf880db3ac99sewardj fudge uMax. */ 1735024598e40c84666cc311a42c256bbf880db3ac99sewardj if (uMin < uMax && uMax == ~(UWord)0) 1736024598e40c84666cc311a42c256bbf880db3ac99sewardj uMax--; 1737024598e40c84666cc311a42c256bbf880db3ac99sewardj toadd_addr = uMin; 1738024598e40c84666cc311a42c256bbf880db3ac99sewardj toadd_szB = uMax - uMin + 1; 1739024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 1740024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1741024598e40c84666cc311a42c256bbf880db3ac99sewardj default: 1742024598e40c84666cc311a42c256bbf880db3ac99sewardj /* We should only be caching info for the above 3 cases */ 1743024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(0); 1744024598e40c84666cc311a42c256bbf880db3ac99sewardj } /* switch (inv->tag) */ 1745024598e40c84666cc311a42c256bbf880db3ac99sewardj 1746024598e40c84666cc311a42c256bbf880db3ac99sewardj { /* and actually add this to the cache, finally */ 1747024598e40c84666cc311a42c256bbf880db3ac99sewardj Word i; 1748024598e40c84666cc311a42c256bbf880db3ac99sewardj Word ip = cache->nInUse / 2; /* doesn't seem critical */ 1749024598e40c84666cc311a42c256bbf880db3ac99sewardj 1750024598e40c84666cc311a42c256bbf880db3ac99sewardj if (cache->nInUse < N_QCACHE) 1751024598e40c84666cc311a42c256bbf880db3ac99sewardj cache->nInUse++; 1752024598e40c84666cc311a42c256bbf880db3ac99sewardj for (i = cache->nInUse-1; i > ip; i--) { 1753024598e40c84666cc311a42c256bbf880db3ac99sewardj cache->elems[i] = cache->elems[i-1]; 1754024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1755024598e40c84666cc311a42c256bbf880db3ac99sewardj 1756024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(toadd_szB > 0); 1757024598e40c84666cc311a42c256bbf880db3ac99sewardj cache->elems[ip].addr = toadd_addr; 1758024598e40c84666cc311a42c256bbf880db3ac99sewardj cache->elems[ip].szB = toadd_szB; 1759024598e40c84666cc311a42c256bbf880db3ac99sewardj cache->elems[ip].inv = *inv; 1760024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1761024598e40c84666cc311a42c256bbf880db3ac99sewardj 1762024598e40c84666cc311a42c256bbf880db3ac99sewardj if (show) QCache__pp(cache, "after upd"); 1763024598e40c84666cc311a42c256bbf880db3ac99sewardj 1764024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1765024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1766024598e40c84666cc311a42c256bbf880db3ac99sewardj 1767024598e40c84666cc311a42c256bbf880db3ac99sewardj 1768024598e40c84666cc311a42c256bbf880db3ac99sewardj/* CALLED FROM GENERATED CODE */ 1769024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic 1770024598e40c84666cc311a42c256bbf880db3ac99sewardjVG_REGPARM(3) 1771024598e40c84666cc311a42c256bbf880db3ac99sewardjvoid helperc__mem_access ( /* Known only at run time: */ 1772024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr ea, Addr sp, Addr fp, 1773024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Known at translation time: */ 1774024598e40c84666cc311a42c256bbf880db3ac99sewardj Word sszB, Addr ip, XArray* ip_frameBlocks ) 1775024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1776024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord szB; 1777024598e40c84666cc311a42c256bbf880db3ac99sewardj IInstance* iinstance; 1778024598e40c84666cc311a42c256bbf880db3ac99sewardj Invar* inv; 1779024598e40c84666cc311a42c256bbf880db3ac99sewardj Invar new_inv; 1780024598e40c84666cc311a42c256bbf880db3ac99sewardj ThreadId tid = VG_(get_running_tid)(); 1781024598e40c84666cc311a42c256bbf880db3ac99sewardj StackFrame* frame; 1782f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj HChar bufE[160], bufA[160], bufD[32]; 1783024598e40c84666cc311a42c256bbf880db3ac99sewardj 1784024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__total_accesses++; 1785024598e40c84666cc311a42c256bbf880db3ac99sewardj 1786024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(is_sane_TId(tid)); 1787024598e40c84666cc311a42c256bbf880db3ac99sewardj frame = shadowStacks[tid]; 1788024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(frame); 1789024598e40c84666cc311a42c256bbf880db3ac99sewardj 1790024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Find the instance info for this instruction. */ 1791024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(ip_frameBlocks); 1792024598e40c84666cc311a42c256bbf880db3ac99sewardj iinstance = find_or_create_IInstance( frame, ip, ip_frameBlocks ); 1793024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(iinstance); 1794024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(iinstance->blocks == ip_frameBlocks); 1795024598e40c84666cc311a42c256bbf880db3ac99sewardj 1796024598e40c84666cc311a42c256bbf880db3ac99sewardj szB = (sszB < 0) ? (-sszB) : sszB; 1797024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(szB > 0); 1798024598e40c84666cc311a42c256bbf880db3ac99sewardj 1799024598e40c84666cc311a42c256bbf880db3ac99sewardj inv = &iinstance->invar; 1800024598e40c84666cc311a42c256bbf880db3ac99sewardj 1801024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Deal with first uses of instruction instances. */ 1802024598e40c84666cc311a42c256bbf880db3ac99sewardj if (inv->tag == Inv_Unset) { 1803024598e40c84666cc311a42c256bbf880db3ac99sewardj /* This is the first use of this instance of the instruction, so 1804024598e40c84666cc311a42c256bbf880db3ac99sewardj we can't make any check; we merely record what we saw, so we 1805024598e40c84666cc311a42c256bbf880db3ac99sewardj can compare it against what happens for 2nd and subsequent 1806024598e40c84666cc311a42c256bbf880db3ac99sewardj accesses. */ 1807024598e40c84666cc311a42c256bbf880db3ac99sewardj classify_address( inv, 1808024598e40c84666cc311a42c256bbf880db3ac99sewardj tid, ea, sp, fp, szB, iinstance->blocks ); 1809024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(inv->tag != Inv_Unset); 1810024598e40c84666cc311a42c256bbf880db3ac99sewardj return; 1811024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1812024598e40c84666cc311a42c256bbf880db3ac99sewardj 1813024598e40c84666cc311a42c256bbf880db3ac99sewardj /* So generate an Invar and see if it's different from what 1814024598e40c84666cc311a42c256bbf880db3ac99sewardj we had before. */ 1815024598e40c84666cc311a42c256bbf880db3ac99sewardj classify_address( &new_inv, 1816024598e40c84666cc311a42c256bbf880db3ac99sewardj tid, ea, sp, fp, szB, iinstance->blocks ); 1817024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(new_inv.tag != Inv_Unset); 1818024598e40c84666cc311a42c256bbf880db3ac99sewardj 1819024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Did we see something different from before? If no, then there's 1820024598e40c84666cc311a42c256bbf880db3ac99sewardj no error. */ 1821110e0f8e7effba90dc43d9763ebacdc61e4ae678florian tl_assert(inv->tag != Inv_Unset); 1822110e0f8e7effba90dc43d9763ebacdc61e4ae678florian 1823f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj if (LIKELY(eq_Invar(&new_inv, inv))) 1824024598e40c84666cc311a42c256bbf880db3ac99sewardj return; 1825024598e40c84666cc311a42c256bbf880db3ac99sewardj 1826024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(memset)(bufE, 0, sizeof(bufE)); 1827024598e40c84666cc311a42c256bbf880db3ac99sewardj show_Invar( bufE, sizeof(bufE)-1, inv, frame->depth ); 1828024598e40c84666cc311a42c256bbf880db3ac99sewardj 1829024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(memset)(bufA, 0, sizeof(bufA)); 1830024598e40c84666cc311a42c256bbf880db3ac99sewardj show_Invar( bufA, sizeof(bufA)-1, &new_inv, frame->depth ); 1831024598e40c84666cc311a42c256bbf880db3ac99sewardj 1832f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj VG_(memset)(bufD, 0, sizeof(bufD)); 1833f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj UWord absDelta; 1834f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj gen_delta_str( bufD, &absDelta, inv, ea ); 1835f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj 1836f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj if (absDelta < 1024) 1837f5b019fb45b52a26fefa40b8fa5b518f0686dd99sewardj sg_record_error_SorG( tid, ea, sszB, bufE, bufA, bufD ); 1838024598e40c84666cc311a42c256bbf880db3ac99sewardj 1839024598e40c84666cc311a42c256bbf880db3ac99sewardj /* And now install the new observation as "standard", so as to 1840024598e40c84666cc311a42c256bbf880db3ac99sewardj make future error messages make more sense. */ 1841024598e40c84666cc311a42c256bbf880db3ac99sewardj *inv = new_inv; 1842024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1843024598e40c84666cc311a42c256bbf880db3ac99sewardj 1844024598e40c84666cc311a42c256bbf880db3ac99sewardj 1845024598e40c84666cc311a42c256bbf880db3ac99sewardj//////////////////////////////////////// 1846024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Primary push-a-new-frame routine. Called indirectly from 1847024598e40c84666cc311a42c256bbf880db3ac99sewardj generated code. */ 1848024598e40c84666cc311a42c256bbf880db3ac99sewardj 1849024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic UWord stats__max_sitree_size = 0; 1850024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic UWord stats__max_gitree_size = 0; 1851024598e40c84666cc311a42c256bbf880db3ac99sewardj 1852024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic 1853024598e40c84666cc311a42c256bbf880db3ac99sewardjvoid shadowStack_new_frame ( ThreadId tid, 1854024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr sp_at_call_insn, 1855024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr sp_post_call_insn, 1856024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr fp_at_call_insn, 1857024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr ip_post_call_insn, 1858024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* descrs_at_call_insn ) 1859024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1860024598e40c84666cc311a42c256bbf880db3ac99sewardj StackFrame *callee, *caller; 1861024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(is_sane_TId(tid)); 1862024598e40c84666cc311a42c256bbf880db3ac99sewardj 1863024598e40c84666cc311a42c256bbf880db3ac99sewardj caller = shadowStacks[tid]; 1864024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(caller); 1865024598e40c84666cc311a42c256bbf880db3ac99sewardj 1866024598e40c84666cc311a42c256bbf880db3ac99sewardj if (caller->outer) { /* "this is not the outermost frame" */ 1867024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(caller->outer->inner == caller); 1868024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(caller->outer->depth >= 0); 1869024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(1 + caller->outer->depth == caller->depth); 1870024598e40c84666cc311a42c256bbf880db3ac99sewardj } else { 1871024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(caller->depth == 0); 1872024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1873024598e40c84666cc311a42c256bbf880db3ac99sewardj 1874024598e40c84666cc311a42c256bbf880db3ac99sewardj caller->sp_at_call = sp_at_call_insn; 1875024598e40c84666cc311a42c256bbf880db3ac99sewardj caller->fp_at_call = fp_at_call_insn; 1876024598e40c84666cc311a42c256bbf880db3ac99sewardj 1877024598e40c84666cc311a42c256bbf880db3ac99sewardj if (descrs_at_call_insn) { 1878024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert( VG_(sizeXA)(descrs_at_call_insn) > 0 ); 1879024598e40c84666cc311a42c256bbf880db3ac99sewardj caller->blocks_added_by_call 1880024598e40c84666cc311a42c256bbf880db3ac99sewardj = calculate_StackBlock_EAs( descrs_at_call_insn, 1881024598e40c84666cc311a42c256bbf880db3ac99sewardj sp_at_call_insn, fp_at_call_insn ); 1882024598e40c84666cc311a42c256bbf880db3ac99sewardj if (caller->blocks_added_by_call) 1883024598e40c84666cc311a42c256bbf880db3ac99sewardj add_blocks_to_StackTree( siTrees[tid], 1884024598e40c84666cc311a42c256bbf880db3ac99sewardj descrs_at_call_insn, 1885024598e40c84666cc311a42c256bbf880db3ac99sewardj caller->blocks_added_by_call, 1886024598e40c84666cc311a42c256bbf880db3ac99sewardj caller->depth /* stack depth at which 1887024598e40c84666cc311a42c256bbf880db3ac99sewardj these blocks are 1888024598e40c84666cc311a42c256bbf880db3ac99sewardj considered to exist*/ ); 1889024598e40c84666cc311a42c256bbf880db3ac99sewardj if (1) { 1890024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord s = VG_(sizeFM)( siTrees[tid] ); 1891024598e40c84666cc311a42c256bbf880db3ac99sewardj UWord g = VG_(sizeFM)( giTree ); 1892024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool sb = s > stats__max_sitree_size; 1893024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool gb = g > stats__max_gitree_size; 1894024598e40c84666cc311a42c256bbf880db3ac99sewardj if (sb) stats__max_sitree_size = s; 1895024598e40c84666cc311a42c256bbf880db3ac99sewardj if (gb) stats__max_gitree_size = g; 1896024598e40c84666cc311a42c256bbf880db3ac99sewardj if (0 && (sb || gb)) 1897024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(message)(Vg_DebugMsg, 1898024598e40c84666cc311a42c256bbf880db3ac99sewardj "exp-sgcheck: new max tree sizes: " 189916eef85229a8d8a00dd8edd8f32a4a91cb6ba7a8florian "StackTree %lu, GlobalTree %lu\n", 1900024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__max_sitree_size, stats__max_gitree_size ); 1901024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1902024598e40c84666cc311a42c256bbf880db3ac99sewardj } else { 1903024598e40c84666cc311a42c256bbf880db3ac99sewardj caller->blocks_added_by_call = NULL; 1904024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1905024598e40c84666cc311a42c256bbf880db3ac99sewardj 1906024598e40c84666cc311a42c256bbf880db3ac99sewardj /* caller->blocks_added_by_call is used again (and then freed) when 1907024598e40c84666cc311a42c256bbf880db3ac99sewardj this frame is removed from the stack. */ 1908024598e40c84666cc311a42c256bbf880db3ac99sewardj 1909024598e40c84666cc311a42c256bbf880db3ac99sewardj if (caller->inner) { 1910024598e40c84666cc311a42c256bbf880db3ac99sewardj callee = caller->inner; 1911024598e40c84666cc311a42c256bbf880db3ac99sewardj } else { 1912024598e40c84666cc311a42c256bbf880db3ac99sewardj callee = sg_malloc("di.sg_main.sSnf.1", sizeof(StackFrame)); 1913024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(memset)(callee, 0, sizeof(StackFrame)); 1914024598e40c84666cc311a42c256bbf880db3ac99sewardj callee->outer = caller; 1915024598e40c84666cc311a42c256bbf880db3ac99sewardj caller->inner = callee; 1916024598e40c84666cc311a42c256bbf880db3ac99sewardj callee->depth = 1 + caller->depth; 1917024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(callee->inner == NULL); 1918024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1919024598e40c84666cc311a42c256bbf880db3ac99sewardj 1920024598e40c84666cc311a42c256bbf880db3ac99sewardj /* This sets up .htab, .htab_size and .htab_used */ 1921024598e40c84666cc311a42c256bbf880db3ac99sewardj initialise_II_hash_table( callee ); 1922024598e40c84666cc311a42c256bbf880db3ac99sewardj 1923024598e40c84666cc311a42c256bbf880db3ac99sewardj callee->creation_sp = sp_post_call_insn; 1924024598e40c84666cc311a42c256bbf880db3ac99sewardj callee->sp_at_call = 0; // not actually required .. 1925024598e40c84666cc311a42c256bbf880db3ac99sewardj callee->fp_at_call = 0; // .. these 3 initialisations are .. 1926024598e40c84666cc311a42c256bbf880db3ac99sewardj callee->blocks_added_by_call = NULL; // .. just for cleanness 1927024598e40c84666cc311a42c256bbf880db3ac99sewardj 1928024598e40c84666cc311a42c256bbf880db3ac99sewardj /* record the new running stack frame */ 1929024598e40c84666cc311a42c256bbf880db3ac99sewardj shadowStacks[tid] = callee; 1930024598e40c84666cc311a42c256bbf880db3ac99sewardj 1931024598e40c84666cc311a42c256bbf880db3ac99sewardj /* and this thread's query cache is now invalid */ 1932024598e40c84666cc311a42c256bbf880db3ac99sewardj QCache__invalidate( &qcaches[tid] ); 1933024598e40c84666cc311a42c256bbf880db3ac99sewardj 1934024598e40c84666cc311a42c256bbf880db3ac99sewardj if (0) 1935024598e40c84666cc311a42c256bbf880db3ac99sewardj { Word d = callee->depth; 193646cc04521acf2827eb33310fadc119bf2dc039e4florian const HChar *fnname; 1937024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool ok; 1938024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr ip = ip_post_call_insn; 193946cc04521acf2827eb33310fadc119bf2dc039e4florian ok = VG_(get_fnname_w_offset)( ip, &fnname ); 1940024598e40c84666cc311a42c256bbf880db3ac99sewardj while (d > 0) { 1941024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)(" "); 1942024598e40c84666cc311a42c256bbf880db3ac99sewardj d--; 1943024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1944024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)("> %s %#lx\n", ok ? fnname : "???", ip); 1945024598e40c84666cc311a42c256bbf880db3ac99sewardj } 1946024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1947024598e40c84666cc311a42c256bbf880db3ac99sewardj 1948024598e40c84666cc311a42c256bbf880db3ac99sewardj/* CALLED FROM GENERATED CODE */ 1949024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic 1950024598e40c84666cc311a42c256bbf880db3ac99sewardjVG_REGPARM(3) 1951024598e40c84666cc311a42c256bbf880db3ac99sewardjvoid helperc__new_frame ( Addr sp_post_call_insn, 1952024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr fp_at_call_insn, 1953024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr ip_post_call_insn, 1954024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* blocks_at_call_insn, 1955024598e40c84666cc311a42c256bbf880db3ac99sewardj Word sp_adjust ) 1956024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1957024598e40c84666cc311a42c256bbf880db3ac99sewardj ThreadId tid = VG_(get_running_tid)(); 1958024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr sp_at_call_insn = sp_post_call_insn + sp_adjust; 1959024598e40c84666cc311a42c256bbf880db3ac99sewardj shadowStack_new_frame( tid, 1960024598e40c84666cc311a42c256bbf880db3ac99sewardj sp_at_call_insn, 1961024598e40c84666cc311a42c256bbf880db3ac99sewardj sp_post_call_insn, 1962024598e40c84666cc311a42c256bbf880db3ac99sewardj fp_at_call_insn, 1963024598e40c84666cc311a42c256bbf880db3ac99sewardj ip_post_call_insn, 1964024598e40c84666cc311a42c256bbf880db3ac99sewardj blocks_at_call_insn ); 1965024598e40c84666cc311a42c256bbf880db3ac99sewardj} 1966024598e40c84666cc311a42c256bbf880db3ac99sewardj 1967024598e40c84666cc311a42c256bbf880db3ac99sewardj 1968024598e40c84666cc311a42c256bbf880db3ac99sewardj//////////////////////////////////////// 1969024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Primary remove-frame(s) routine. Called indirectly from 1970024598e40c84666cc311a42c256bbf880db3ac99sewardj generated code. */ 1971024598e40c84666cc311a42c256bbf880db3ac99sewardj 1972024598e40c84666cc311a42c256bbf880db3ac99sewardj__attribute__((noinline)) 1973024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void shadowStack_unwind ( ThreadId tid, Addr sp_now ) 1974024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 1975024598e40c84666cc311a42c256bbf880db3ac99sewardj StackFrame *innermost, *innermostOrig; 1976024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(is_sane_TId(tid)); 1977024598e40c84666cc311a42c256bbf880db3ac99sewardj innermost = shadowStacks[tid]; 1978024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(innermost); 1979024598e40c84666cc311a42c256bbf880db3ac99sewardj innermostOrig = innermost; 1980024598e40c84666cc311a42c256bbf880db3ac99sewardj //VG_(printf)("UNWIND sp_new = %p\n", sp_now); 1981024598e40c84666cc311a42c256bbf880db3ac99sewardj while (1) { 1982024598e40c84666cc311a42c256bbf880db3ac99sewardj if (!innermost->outer) 1983024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 1984024598e40c84666cc311a42c256bbf880db3ac99sewardj if (innermost->inner) 1985024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(innermost->inner->outer == innermost); 1986024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(innermost->outer->inner == innermost); 1987024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(innermost->blocks_added_by_call == NULL); 1988024598e40c84666cc311a42c256bbf880db3ac99sewardj if (sp_now <= innermost->creation_sp) break; 1989024598e40c84666cc311a42c256bbf880db3ac99sewardj //VG_(printf)("UNWIND dump %p\n", innermost->creation_sp); 1990024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(innermost->htab); 1991024598e40c84666cc311a42c256bbf880db3ac99sewardj if (innermost->htab != &innermost->htab_fixed[0]) 1992024598e40c84666cc311a42c256bbf880db3ac99sewardj sg_free(innermost->htab); 1993024598e40c84666cc311a42c256bbf880db3ac99sewardj /* be on the safe side */ 1994024598e40c84666cc311a42c256bbf880db3ac99sewardj innermost->creation_sp = 0; 1995024598e40c84666cc311a42c256bbf880db3ac99sewardj innermost->htab = NULL; 1996024598e40c84666cc311a42c256bbf880db3ac99sewardj innermost->htab_size = 0; 1997024598e40c84666cc311a42c256bbf880db3ac99sewardj innermost->htab_used = 0; 1998024598e40c84666cc311a42c256bbf880db3ac99sewardj innermost->sp_at_call = 0; 1999024598e40c84666cc311a42c256bbf880db3ac99sewardj innermost->fp_at_call = 0; 2000024598e40c84666cc311a42c256bbf880db3ac99sewardj innermost->blocks_added_by_call = NULL; 2001024598e40c84666cc311a42c256bbf880db3ac99sewardj innermost = innermost->outer; 2002024598e40c84666cc311a42c256bbf880db3ac99sewardj 2003024598e40c84666cc311a42c256bbf880db3ac99sewardj /* So now we're "back" in the calling frame. Remove from this 2004024598e40c84666cc311a42c256bbf880db3ac99sewardj thread's stack-interval-tree, the blocks added at the time of 2005024598e40c84666cc311a42c256bbf880db3ac99sewardj the call. */ 2006024598e40c84666cc311a42c256bbf880db3ac99sewardj 2007024598e40c84666cc311a42c256bbf880db3ac99sewardj if (innermost->outer) { /* not at the outermost frame */ 2008024598e40c84666cc311a42c256bbf880db3ac99sewardj if (innermost->blocks_added_by_call == NULL) { 2009024598e40c84666cc311a42c256bbf880db3ac99sewardj } else { 2010024598e40c84666cc311a42c256bbf880db3ac99sewardj del_blocks_from_StackTree( siTrees[tid], 2011024598e40c84666cc311a42c256bbf880db3ac99sewardj innermost->blocks_added_by_call ); 2012024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(deleteXA)( innermost->blocks_added_by_call ); 2013024598e40c84666cc311a42c256bbf880db3ac99sewardj innermost->blocks_added_by_call = NULL; 2014024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2015024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2016024598e40c84666cc311a42c256bbf880db3ac99sewardj /* That completes the required tidying of the interval tree 2017024598e40c84666cc311a42c256bbf880db3ac99sewardj associated with the frame we just removed. */ 2018024598e40c84666cc311a42c256bbf880db3ac99sewardj 2019024598e40c84666cc311a42c256bbf880db3ac99sewardj if (0) { 2020024598e40c84666cc311a42c256bbf880db3ac99sewardj Word d = innermost->depth; 2021024598e40c84666cc311a42c256bbf880db3ac99sewardj while (d > 0) { 2022024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)(" "); 2023024598e40c84666cc311a42c256bbf880db3ac99sewardj d--; 2024024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2025024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(printf)("X\n"); 2026024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2027024598e40c84666cc311a42c256bbf880db3ac99sewardj 2028024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2029024598e40c84666cc311a42c256bbf880db3ac99sewardj 2030024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(innermost); 2031024598e40c84666cc311a42c256bbf880db3ac99sewardj 2032024598e40c84666cc311a42c256bbf880db3ac99sewardj if (innermost != innermostOrig) { 2033024598e40c84666cc311a42c256bbf880db3ac99sewardj shadowStacks[tid] = innermost; 2034024598e40c84666cc311a42c256bbf880db3ac99sewardj /* this thread's query cache is now invalid */ 2035024598e40c84666cc311a42c256bbf880db3ac99sewardj QCache__invalidate( &qcaches[tid] ); 2036024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2037024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2038024598e40c84666cc311a42c256bbf880db3ac99sewardj 2039024598e40c84666cc311a42c256bbf880db3ac99sewardj 2040024598e40c84666cc311a42c256bbf880db3ac99sewardj 2041024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 2042024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 2043024598e40c84666cc311a42c256bbf880db3ac99sewardj// Instrumentation // 2044024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 2045024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 2046024598e40c84666cc311a42c256bbf880db3ac99sewardj 2047024598e40c84666cc311a42c256bbf880db3ac99sewardj/* What does instrumentation need to do? 2048024598e40c84666cc311a42c256bbf880db3ac99sewardj 2049024598e40c84666cc311a42c256bbf880db3ac99sewardj - at each Call transfer, generate a call to shadowStack_new_frame 2050024598e40c84666cc311a42c256bbf880db3ac99sewardj do this by manually inspecting the IR 2051024598e40c84666cc311a42c256bbf880db3ac99sewardj 2052024598e40c84666cc311a42c256bbf880db3ac99sewardj - at each sp change, if the sp change is negative, 2053024598e40c84666cc311a42c256bbf880db3ac99sewardj call shadowStack_unwind 2054024598e40c84666cc311a42c256bbf880db3ac99sewardj do this by asking for SP-change analysis 2055024598e40c84666cc311a42c256bbf880db3ac99sewardj 2056024598e40c84666cc311a42c256bbf880db3ac99sewardj - for each memory referencing instruction, 2057024598e40c84666cc311a42c256bbf880db3ac99sewardj call helperc__mem_access 2058024598e40c84666cc311a42c256bbf880db3ac99sewardj*/ 2059024598e40c84666cc311a42c256bbf880db3ac99sewardj 2060024598e40c84666cc311a42c256bbf880db3ac99sewardj/* A complication: sg_ instrumentation and h_ instrumentation need to 2061024598e40c84666cc311a42c256bbf880db3ac99sewardj be interleaved. Since the latter is a lot more complex than the 2062024598e40c84666cc311a42c256bbf880db3ac99sewardj former, we split the sg_ instrumentation here into four functions 2063024598e40c84666cc311a42c256bbf880db3ac99sewardj and let the h_ instrumenter call the four functions as it goes. 2064024598e40c84666cc311a42c256bbf880db3ac99sewardj Hence the h_ instrumenter drives the sg_ instrumenter. 2065024598e40c84666cc311a42c256bbf880db3ac99sewardj 2066024598e40c84666cc311a42c256bbf880db3ac99sewardj To make this viable, the sg_ instrumenter carries what running 2067024598e40c84666cc311a42c256bbf880db3ac99sewardj state it needs in 'struct _SGEnv'. This is exported only 2068024598e40c84666cc311a42c256bbf880db3ac99sewardj abstractly from this file. 2069024598e40c84666cc311a42c256bbf880db3ac99sewardj*/ 2070024598e40c84666cc311a42c256bbf880db3ac99sewardj 2071024598e40c84666cc311a42c256bbf880db3ac99sewardjstruct _SGEnv { 2072024598e40c84666cc311a42c256bbf880db3ac99sewardj /* the current insn's IP */ 2073f466eef8e53aafcb617997e1ca18b7c829168db8florian Addr curr_IP; 2074024598e40c84666cc311a42c256bbf880db3ac99sewardj /* whether the above is actually known */ 2075024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool curr_IP_known; 2076024598e40c84666cc311a42c256bbf880db3ac99sewardj /* if we find a mem ref, is it the first for this insn? Used for 2077024598e40c84666cc311a42c256bbf880db3ac99sewardj detecting insns which make more than one memory ref, a situation 2078024598e40c84666cc311a42c256bbf880db3ac99sewardj we basically can't really handle properly; and so we ignore all 2079024598e40c84666cc311a42c256bbf880db3ac99sewardj but the first ref. */ 2080024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool firstRef; 2081e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj /* READONLY */ 2082e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj IRTemp (*newIRTemp_cb)(IRType,void*); 2083e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj void* newIRTemp_opaque; 2084024598e40c84666cc311a42c256bbf880db3ac99sewardj}; 2085024598e40c84666cc311a42c256bbf880db3ac99sewardj 2086024598e40c84666cc311a42c256bbf880db3ac99sewardj 2087024598e40c84666cc311a42c256bbf880db3ac99sewardj/* --- Helper fns for instrumentation --- */ 2088024598e40c84666cc311a42c256bbf880db3ac99sewardj 2089e6451332ee19f6d70821bf8e24781ff8868bdb3csewardjstatic IRTemp gen_Get_SP ( struct _SGEnv* sge, 2090e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj IRSB* bbOut, 20913c0c94777f547bcb5eadbe8cb4328debf0f51875florian const VexGuestLayout* layout, 2092024598e40c84666cc311a42c256bbf880db3ac99sewardj Int hWordTy_szB ) 2093024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 2094024598e40c84666cc311a42c256bbf880db3ac99sewardj IRExpr* sp_expr; 2095024598e40c84666cc311a42c256bbf880db3ac99sewardj IRTemp sp_temp; 2096024598e40c84666cc311a42c256bbf880db3ac99sewardj IRType sp_type; 2097024598e40c84666cc311a42c256bbf880db3ac99sewardj /* This in effect forces the host and guest word sizes to be the 2098024598e40c84666cc311a42c256bbf880db3ac99sewardj same. */ 2099024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(hWordTy_szB == layout->sizeof_SP); 2100024598e40c84666cc311a42c256bbf880db3ac99sewardj sp_type = layout->sizeof_SP == 8 ? Ity_I64 : Ity_I32; 2101024598e40c84666cc311a42c256bbf880db3ac99sewardj sp_expr = IRExpr_Get( layout->offset_SP, sp_type ); 2102e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj sp_temp = sge->newIRTemp_cb( sp_type, sge->newIRTemp_opaque ); 2103024598e40c84666cc311a42c256bbf880db3ac99sewardj addStmtToIRSB( bbOut, IRStmt_WrTmp( sp_temp, sp_expr ) ); 2104024598e40c84666cc311a42c256bbf880db3ac99sewardj return sp_temp; 2105024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2106024598e40c84666cc311a42c256bbf880db3ac99sewardj 2107e6451332ee19f6d70821bf8e24781ff8868bdb3csewardjstatic IRTemp gen_Get_FP ( struct _SGEnv* sge, 2108e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj IRSB* bbOut, 21093c0c94777f547bcb5eadbe8cb4328debf0f51875florian const VexGuestLayout* layout, 2110024598e40c84666cc311a42c256bbf880db3ac99sewardj Int hWordTy_szB ) 2111024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 2112024598e40c84666cc311a42c256bbf880db3ac99sewardj IRExpr* fp_expr; 2113024598e40c84666cc311a42c256bbf880db3ac99sewardj IRTemp fp_temp; 2114024598e40c84666cc311a42c256bbf880db3ac99sewardj IRType fp_type; 2115024598e40c84666cc311a42c256bbf880db3ac99sewardj /* This in effect forces the host and guest word sizes to be the 2116024598e40c84666cc311a42c256bbf880db3ac99sewardj same. */ 2117024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(hWordTy_szB == layout->sizeof_SP); 2118024598e40c84666cc311a42c256bbf880db3ac99sewardj fp_type = layout->sizeof_FP == 8 ? Ity_I64 : Ity_I32; 2119024598e40c84666cc311a42c256bbf880db3ac99sewardj fp_expr = IRExpr_Get( layout->offset_FP, fp_type ); 2120e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj fp_temp = sge->newIRTemp_cb( fp_type, sge->newIRTemp_opaque ); 2121024598e40c84666cc311a42c256bbf880db3ac99sewardj addStmtToIRSB( bbOut, IRStmt_WrTmp( fp_temp, fp_expr ) ); 2122024598e40c84666cc311a42c256bbf880db3ac99sewardj return fp_temp; 2123024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2124024598e40c84666cc311a42c256bbf880db3ac99sewardj 2125e6451332ee19f6d70821bf8e24781ff8868bdb3csewardjstatic void instrument_mem_access ( struct _SGEnv* sge, 2126e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj IRSB* bbOut, 2127024598e40c84666cc311a42c256bbf880db3ac99sewardj IRExpr* addr, 2128024598e40c84666cc311a42c256bbf880db3ac99sewardj Int szB, 2129024598e40c84666cc311a42c256bbf880db3ac99sewardj Bool isStore, 2130024598e40c84666cc311a42c256bbf880db3ac99sewardj Int hWordTy_szB, 2131024598e40c84666cc311a42c256bbf880db3ac99sewardj Addr curr_IP, 21323c0c94777f547bcb5eadbe8cb4328debf0f51875florian const VexGuestLayout* layout ) 2133024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 2134024598e40c84666cc311a42c256bbf880db3ac99sewardj IRType tyAddr = Ity_INVALID; 2135024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* frameBlocks = NULL; 2136024598e40c84666cc311a42c256bbf880db3ac99sewardj 2137024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(isIRAtom(addr)); 2138024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(hWordTy_szB == 4 || hWordTy_szB == 8); 2139024598e40c84666cc311a42c256bbf880db3ac99sewardj 2140024598e40c84666cc311a42c256bbf880db3ac99sewardj tyAddr = typeOfIRExpr( bbOut->tyenv, addr ); 2141024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(tyAddr == Ity_I32 || tyAddr == Ity_I64); 2142024598e40c84666cc311a42c256bbf880db3ac99sewardj 2143024598e40c84666cc311a42c256bbf880db3ac99sewardj#if defined(VGA_x86) 2144024598e40c84666cc311a42c256bbf880db3ac99sewardj { UChar* p = (UChar*)curr_IP; 2145024598e40c84666cc311a42c256bbf880db3ac99sewardj // pop %ebp; RET 2146777db6cec27d5d0edbe43ea8c6c596b88f9a4489sewardj if (p[0] == 0xc3 && p[-1] == 0x5d) return; 2147024598e40c84666cc311a42c256bbf880db3ac99sewardj // pop %ebp; RET $imm16 2148777db6cec27d5d0edbe43ea8c6c596b88f9a4489sewardj if (p[0] == 0xc2 && p[-1] == 0x5d) return; 2149024598e40c84666cc311a42c256bbf880db3ac99sewardj // PUSH %EBP; mov %esp,%ebp 2150024598e40c84666cc311a42c256bbf880db3ac99sewardj if (p[0] == 0x55 && p[1] == 0x89 && p[2] == 0xe5) return; 2151024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2152024598e40c84666cc311a42c256bbf880db3ac99sewardj#endif 2153024598e40c84666cc311a42c256bbf880db3ac99sewardj 2154024598e40c84666cc311a42c256bbf880db3ac99sewardj /* First off, find or create the StackBlocks for this instruction. */ 2155024598e40c84666cc311a42c256bbf880db3ac99sewardj frameBlocks = get_StackBlocks_for_IP( curr_IP ); 2156024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(frameBlocks); 2157024598e40c84666cc311a42c256bbf880db3ac99sewardj //if (VG_(sizeXA)( frameBlocks ) == 0) 2158024598e40c84666cc311a42c256bbf880db3ac99sewardj // frameBlocks = NULL; 2159024598e40c84666cc311a42c256bbf880db3ac99sewardj 2160024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Generate a call to "helperc__mem_access", passing: 2161024598e40c84666cc311a42c256bbf880db3ac99sewardj addr current_SP current_FP szB curr_IP frameBlocks 2162024598e40c84666cc311a42c256bbf880db3ac99sewardj */ 2163e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj { IRTemp t_SP = gen_Get_SP( sge, bbOut, layout, hWordTy_szB ); 2164e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj IRTemp t_FP = gen_Get_FP( sge, bbOut, layout, hWordTy_szB ); 2165024598e40c84666cc311a42c256bbf880db3ac99sewardj IRExpr** args 2166024598e40c84666cc311a42c256bbf880db3ac99sewardj = mkIRExprVec_6( addr, 2167024598e40c84666cc311a42c256bbf880db3ac99sewardj IRExpr_RdTmp(t_SP), 2168024598e40c84666cc311a42c256bbf880db3ac99sewardj IRExpr_RdTmp(t_FP), 2169024598e40c84666cc311a42c256bbf880db3ac99sewardj mkIRExpr_HWord( isStore ? (-szB) : szB ), 2170024598e40c84666cc311a42c256bbf880db3ac99sewardj mkIRExpr_HWord( curr_IP ), 2171024598e40c84666cc311a42c256bbf880db3ac99sewardj mkIRExpr_HWord( (HWord)frameBlocks ) ); 2172024598e40c84666cc311a42c256bbf880db3ac99sewardj IRDirty* di 2173024598e40c84666cc311a42c256bbf880db3ac99sewardj = unsafeIRDirty_0_N( 3/*regparms*/, 2174024598e40c84666cc311a42c256bbf880db3ac99sewardj "helperc__mem_access", 2175e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj VG_(fnptr_to_fnentry)( &helperc__mem_access ), 2176024598e40c84666cc311a42c256bbf880db3ac99sewardj args ); 2177024598e40c84666cc311a42c256bbf880db3ac99sewardj 2178024598e40c84666cc311a42c256bbf880db3ac99sewardj addStmtToIRSB( bbOut, IRStmt_Dirty(di) ); 2179024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2180024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2181024598e40c84666cc311a42c256bbf880db3ac99sewardj 2182024598e40c84666cc311a42c256bbf880db3ac99sewardj 2183024598e40c84666cc311a42c256bbf880db3ac99sewardj/* --- Instrumentation main (4 fns) --- */ 2184024598e40c84666cc311a42c256bbf880db3ac99sewardj 2185e6451332ee19f6d70821bf8e24781ff8868bdb3csewardjstruct _SGEnv * sg_instrument_init ( IRTemp (*newIRTemp_cb)(IRType,void*), 2186e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj void* newIRTemp_opaque ) 2187024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 2188024598e40c84666cc311a42c256bbf880db3ac99sewardj struct _SGEnv * env = sg_malloc("di.sg_main.sii.1", 2189024598e40c84666cc311a42c256bbf880db3ac99sewardj sizeof(struct _SGEnv)); 2190024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(env); 2191e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj env->curr_IP = 0; 2192e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj env->curr_IP_known = False; 2193e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj env->firstRef = True; 2194e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj env->newIRTemp_cb = newIRTemp_cb; 2195e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj env->newIRTemp_opaque = newIRTemp_opaque; 2196024598e40c84666cc311a42c256bbf880db3ac99sewardj return env; 2197024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2198024598e40c84666cc311a42c256bbf880db3ac99sewardj 2199024598e40c84666cc311a42c256bbf880db3ac99sewardjvoid sg_instrument_fini ( struct _SGEnv * env ) 2200024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 2201024598e40c84666cc311a42c256bbf880db3ac99sewardj sg_free(env); 2202024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2203024598e40c84666cc311a42c256bbf880db3ac99sewardj 2204024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Add instrumentation for 'st' to 'sbOut', and possibly modify 'env' 2205024598e40c84666cc311a42c256bbf880db3ac99sewardj as required. This must be called before 'st' itself is added to 2206024598e40c84666cc311a42c256bbf880db3ac99sewardj 'sbOut'. */ 2207024598e40c84666cc311a42c256bbf880db3ac99sewardjvoid sg_instrument_IRStmt ( /*MOD*/struct _SGEnv * env, 2208024598e40c84666cc311a42c256bbf880db3ac99sewardj /*MOD*/IRSB* sbOut, 2209024598e40c84666cc311a42c256bbf880db3ac99sewardj IRStmt* st, 22103c0c94777f547bcb5eadbe8cb4328debf0f51875florian const VexGuestLayout* layout, 2211024598e40c84666cc311a42c256bbf880db3ac99sewardj IRType gWordTy, IRType hWordTy ) 2212024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 22134815eb5cc0e96a3b76aae246e3ca7a8b3394c46csewardj if (!sg_clo_enable_sg_checks) 22144815eb5cc0e96a3b76aae246e3ca7a8b3394c46csewardj return; 22154815eb5cc0e96a3b76aae246e3ca7a8b3394c46csewardj 2216024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(st); 2217024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(isFlatIRStmt(st)); 2218024598e40c84666cc311a42c256bbf880db3ac99sewardj switch (st->tag) { 2219024598e40c84666cc311a42c256bbf880db3ac99sewardj case Ist_NoOp: 2220024598e40c84666cc311a42c256bbf880db3ac99sewardj case Ist_AbiHint: 2221024598e40c84666cc311a42c256bbf880db3ac99sewardj case Ist_Put: 2222024598e40c84666cc311a42c256bbf880db3ac99sewardj case Ist_PutI: 2223024598e40c84666cc311a42c256bbf880db3ac99sewardj case Ist_MBE: 2224024598e40c84666cc311a42c256bbf880db3ac99sewardj /* None of these can contain any memory references. */ 2225024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 2226024598e40c84666cc311a42c256bbf880db3ac99sewardj 2227024598e40c84666cc311a42c256bbf880db3ac99sewardj case Ist_Exit: 2228024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(st->Ist.Exit.jk != Ijk_Call); 2229024598e40c84666cc311a42c256bbf880db3ac99sewardj /* else we must deal with a conditional call */ 2230024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 2231024598e40c84666cc311a42c256bbf880db3ac99sewardj 2232024598e40c84666cc311a42c256bbf880db3ac99sewardj case Ist_IMark: 2233024598e40c84666cc311a42c256bbf880db3ac99sewardj env->curr_IP_known = True; 2234f466eef8e53aafcb617997e1ca18b7c829168db8florian env->curr_IP = st->Ist.IMark.addr; 2235024598e40c84666cc311a42c256bbf880db3ac99sewardj env->firstRef = True; 2236024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 2237024598e40c84666cc311a42c256bbf880db3ac99sewardj 2238024598e40c84666cc311a42c256bbf880db3ac99sewardj case Ist_Store: 2239024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(env->curr_IP_known); 2240024598e40c84666cc311a42c256bbf880db3ac99sewardj if (env->firstRef) { 2241024598e40c84666cc311a42c256bbf880db3ac99sewardj instrument_mem_access( 2242e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj env, sbOut, 2243024598e40c84666cc311a42c256bbf880db3ac99sewardj st->Ist.Store.addr, 2244024598e40c84666cc311a42c256bbf880db3ac99sewardj sizeofIRType(typeOfIRExpr(sbOut->tyenv, st->Ist.Store.data)), 2245024598e40c84666cc311a42c256bbf880db3ac99sewardj True/*isStore*/, 2246024598e40c84666cc311a42c256bbf880db3ac99sewardj sizeofIRType(hWordTy), 2247024598e40c84666cc311a42c256bbf880db3ac99sewardj env->curr_IP, layout 2248024598e40c84666cc311a42c256bbf880db3ac99sewardj ); 2249024598e40c84666cc311a42c256bbf880db3ac99sewardj env->firstRef = False; 2250024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2251024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 2252024598e40c84666cc311a42c256bbf880db3ac99sewardj 2253024598e40c84666cc311a42c256bbf880db3ac99sewardj case Ist_WrTmp: { 2254024598e40c84666cc311a42c256bbf880db3ac99sewardj IRExpr* data = st->Ist.WrTmp.data; 2255024598e40c84666cc311a42c256bbf880db3ac99sewardj if (data->tag == Iex_Load) { 2256024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(env->curr_IP_known); 2257024598e40c84666cc311a42c256bbf880db3ac99sewardj if (env->firstRef) { 2258024598e40c84666cc311a42c256bbf880db3ac99sewardj instrument_mem_access( 2259e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj env, sbOut, 2260024598e40c84666cc311a42c256bbf880db3ac99sewardj data->Iex.Load.addr, 2261024598e40c84666cc311a42c256bbf880db3ac99sewardj sizeofIRType(data->Iex.Load.ty), 2262024598e40c84666cc311a42c256bbf880db3ac99sewardj False/*!isStore*/, 2263024598e40c84666cc311a42c256bbf880db3ac99sewardj sizeofIRType(hWordTy), 2264024598e40c84666cc311a42c256bbf880db3ac99sewardj env->curr_IP, layout 2265024598e40c84666cc311a42c256bbf880db3ac99sewardj ); 2266024598e40c84666cc311a42c256bbf880db3ac99sewardj env->firstRef = False; 2267024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2268024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2269024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 2270024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2271024598e40c84666cc311a42c256bbf880db3ac99sewardj 2272024598e40c84666cc311a42c256bbf880db3ac99sewardj case Ist_Dirty: { 2273024598e40c84666cc311a42c256bbf880db3ac99sewardj Int dataSize; 2274024598e40c84666cc311a42c256bbf880db3ac99sewardj IRDirty* d = st->Ist.Dirty.details; 2275024598e40c84666cc311a42c256bbf880db3ac99sewardj if (d->mFx != Ifx_None) { 2276024598e40c84666cc311a42c256bbf880db3ac99sewardj /* This dirty helper accesses memory. Collect the 2277024598e40c84666cc311a42c256bbf880db3ac99sewardj details. */ 2278024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(env->curr_IP_known); 2279024598e40c84666cc311a42c256bbf880db3ac99sewardj if (env->firstRef) { 2280024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(d->mAddr != NULL); 2281024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(d->mSize != 0); 2282024598e40c84666cc311a42c256bbf880db3ac99sewardj dataSize = d->mSize; 2283024598e40c84666cc311a42c256bbf880db3ac99sewardj if (d->mFx == Ifx_Read || d->mFx == Ifx_Modify) { 2284024598e40c84666cc311a42c256bbf880db3ac99sewardj instrument_mem_access( 2285e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj env, sbOut, d->mAddr, dataSize, False/*!isStore*/, 2286024598e40c84666cc311a42c256bbf880db3ac99sewardj sizeofIRType(hWordTy), env->curr_IP, layout 2287024598e40c84666cc311a42c256bbf880db3ac99sewardj ); 2288024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2289024598e40c84666cc311a42c256bbf880db3ac99sewardj if (d->mFx == Ifx_Write || d->mFx == Ifx_Modify) { 2290024598e40c84666cc311a42c256bbf880db3ac99sewardj instrument_mem_access( 2291e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj env, sbOut, d->mAddr, dataSize, True/*isStore*/, 2292024598e40c84666cc311a42c256bbf880db3ac99sewardj sizeofIRType(hWordTy), env->curr_IP, layout 2293024598e40c84666cc311a42c256bbf880db3ac99sewardj ); 2294024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2295024598e40c84666cc311a42c256bbf880db3ac99sewardj env->firstRef = False; 2296024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2297024598e40c84666cc311a42c256bbf880db3ac99sewardj } else { 2298024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(d->mAddr == NULL); 2299024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(d->mSize == 0); 2300024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2301024598e40c84666cc311a42c256bbf880db3ac99sewardj break; 2302024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2303024598e40c84666cc311a42c256bbf880db3ac99sewardj 23041c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj case Ist_CAS: { 23051c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj /* We treat it as a read and a write of the location. I 23061c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj think that is the same behaviour as it was before IRCAS 23071c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj was introduced, since prior to that point, the Vex front 23081c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj ends would translate a lock-prefixed instruction into a 23091c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj (normal) read followed by a (normal) write. */ 23101c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj if (env->firstRef) { 23111c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj Int dataSize; 23121c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj IRCAS* cas = st->Ist.CAS.details; 23131c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj tl_assert(cas->addr != NULL); 23141c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj tl_assert(cas->dataLo != NULL); 23151c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj dataSize = sizeofIRType(typeOfIRExpr(sbOut->tyenv, cas->dataLo)); 23161c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj if (cas->dataHi != NULL) 23171c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj dataSize *= 2; /* since it's a doubleword-CAS */ 23181c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj instrument_mem_access( 2319e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj env, sbOut, cas->addr, dataSize, False/*!isStore*/, 23201c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj sizeofIRType(hWordTy), env->curr_IP, layout 23211c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj ); 23221c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj instrument_mem_access( 2323e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj env, sbOut, cas->addr, dataSize, True/*isStore*/, 23241c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj sizeofIRType(hWordTy), env->curr_IP, layout 23251c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj ); 23261c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj env->firstRef = False; 23271c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj } 23281c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj break; 23291c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj } 23301c0ce7a9edf8772773f6216dbad4bb04317d23b6sewardj 2331024598e40c84666cc311a42c256bbf880db3ac99sewardj default: 2332024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(0); 2333024598e40c84666cc311a42c256bbf880db3ac99sewardj 2334024598e40c84666cc311a42c256bbf880db3ac99sewardj } /* switch (st->tag) */ 2335024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2336024598e40c84666cc311a42c256bbf880db3ac99sewardj 2337024598e40c84666cc311a42c256bbf880db3ac99sewardj 2338024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Add instrumentation for the final jump of an IRSB 'sbOut', and 2339024598e40c84666cc311a42c256bbf880db3ac99sewardj possibly modify 'env' as required. This must be the last 2340024598e40c84666cc311a42c256bbf880db3ac99sewardj instrumentation statement in the block. */ 2341024598e40c84666cc311a42c256bbf880db3ac99sewardjvoid sg_instrument_final_jump ( /*MOD*/struct _SGEnv * env, 2342024598e40c84666cc311a42c256bbf880db3ac99sewardj /*MOD*/IRSB* sbOut, 2343024598e40c84666cc311a42c256bbf880db3ac99sewardj IRExpr* next, 2344024598e40c84666cc311a42c256bbf880db3ac99sewardj IRJumpKind jumpkind, 23453c0c94777f547bcb5eadbe8cb4328debf0f51875florian const VexGuestLayout* layout, 2346024598e40c84666cc311a42c256bbf880db3ac99sewardj IRType gWordTy, IRType hWordTy ) 2347024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 23484815eb5cc0e96a3b76aae246e3ca7a8b3394c46csewardj if (!sg_clo_enable_sg_checks) 23494815eb5cc0e96a3b76aae246e3ca7a8b3394c46csewardj return; 23504815eb5cc0e96a3b76aae246e3ca7a8b3394c46csewardj 2351024598e40c84666cc311a42c256bbf880db3ac99sewardj if (jumpkind == Ijk_Call) { 2352024598e40c84666cc311a42c256bbf880db3ac99sewardj // Assumes x86 or amd64 2353024598e40c84666cc311a42c256bbf880db3ac99sewardj IRTemp sp_post_call_insn, fp_post_call_insn; 2354024598e40c84666cc311a42c256bbf880db3ac99sewardj XArray* frameBlocks; 2355024598e40c84666cc311a42c256bbf880db3ac99sewardj IRExpr** args; 2356024598e40c84666cc311a42c256bbf880db3ac99sewardj IRDirty* di; 2357024598e40c84666cc311a42c256bbf880db3ac99sewardj sp_post_call_insn 2358e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj = gen_Get_SP( env, sbOut, layout, sizeofIRType(hWordTy) ); 2359024598e40c84666cc311a42c256bbf880db3ac99sewardj fp_post_call_insn 2360e6451332ee19f6d70821bf8e24781ff8868bdb3csewardj = gen_Get_FP( env, sbOut, layout, sizeofIRType(hWordTy) ); 2361024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(env->curr_IP_known); 2362024598e40c84666cc311a42c256bbf880db3ac99sewardj frameBlocks = get_StackBlocks_for_IP( env->curr_IP ); 2363024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(frameBlocks); 2364024598e40c84666cc311a42c256bbf880db3ac99sewardj if (VG_(sizeXA)(frameBlocks) == 0) 2365024598e40c84666cc311a42c256bbf880db3ac99sewardj frameBlocks = NULL; 2366024598e40c84666cc311a42c256bbf880db3ac99sewardj args 2367024598e40c84666cc311a42c256bbf880db3ac99sewardj = mkIRExprVec_5( 2368024598e40c84666cc311a42c256bbf880db3ac99sewardj IRExpr_RdTmp(sp_post_call_insn), 2369024598e40c84666cc311a42c256bbf880db3ac99sewardj IRExpr_RdTmp(fp_post_call_insn), 2370024598e40c84666cc311a42c256bbf880db3ac99sewardj /* assume the call doesn't change FP */ 2371024598e40c84666cc311a42c256bbf880db3ac99sewardj next, 2372024598e40c84666cc311a42c256bbf880db3ac99sewardj mkIRExpr_HWord( (HWord)frameBlocks ), 2373024598e40c84666cc311a42c256bbf880db3ac99sewardj mkIRExpr_HWord( sizeofIRType(gWordTy) ) 2374024598e40c84666cc311a42c256bbf880db3ac99sewardj ); 2375024598e40c84666cc311a42c256bbf880db3ac99sewardj di = unsafeIRDirty_0_N( 2376024598e40c84666cc311a42c256bbf880db3ac99sewardj 3/*regparms*/, 2377024598e40c84666cc311a42c256bbf880db3ac99sewardj "helperc__new_frame", 2378024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(fnptr_to_fnentry)( &helperc__new_frame ), 2379024598e40c84666cc311a42c256bbf880db3ac99sewardj args ); 2380024598e40c84666cc311a42c256bbf880db3ac99sewardj addStmtToIRSB( sbOut, IRStmt_Dirty(di) ); 2381024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2382024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2383024598e40c84666cc311a42c256bbf880db3ac99sewardj 2384024598e40c84666cc311a42c256bbf880db3ac99sewardj 2385024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 2386024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 2387024598e40c84666cc311a42c256bbf880db3ac99sewardj// end Instrumentation // 2388024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 2389024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 2390024598e40c84666cc311a42c256bbf880db3ac99sewardj 2391024598e40c84666cc311a42c256bbf880db3ac99sewardj 2392024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 2393024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 2394024598e40c84666cc311a42c256bbf880db3ac99sewardj// misc // 2395024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 2396024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 2397024598e40c84666cc311a42c256bbf880db3ac99sewardj 2398024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Make a new empty stack frame that is suitable for being the 2399024598e40c84666cc311a42c256bbf880db3ac99sewardj outermost frame in a stack. It has a creation_sp of effectively 2400024598e40c84666cc311a42c256bbf880db3ac99sewardj infinity, so it can never be removed. */ 2401024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic StackFrame* new_root_StackFrame ( void ) 2402024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 2403024598e40c84666cc311a42c256bbf880db3ac99sewardj StackFrame* sframe = sg_malloc("di.sg_main.nrS.1", sizeof(StackFrame)); 2404024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(memset)( sframe, 0, sizeof(*sframe) ); 2405024598e40c84666cc311a42c256bbf880db3ac99sewardj sframe->creation_sp = ~0UL; 2406024598e40c84666cc311a42c256bbf880db3ac99sewardj 2407024598e40c84666cc311a42c256bbf880db3ac99sewardj /* This sets up .htab, .htab_size and .htab_used */ 2408024598e40c84666cc311a42c256bbf880db3ac99sewardj initialise_II_hash_table( sframe ); 2409024598e40c84666cc311a42c256bbf880db3ac99sewardj 2410024598e40c84666cc311a42c256bbf880db3ac99sewardj /* ->depth, ->outer, ->inner are 0, NULL, NULL */ 2411024598e40c84666cc311a42c256bbf880db3ac99sewardj 2412024598e40c84666cc311a42c256bbf880db3ac99sewardj return sframe; 2413024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2414024598e40c84666cc311a42c256bbf880db3ac99sewardj 2415024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Primary routine for setting up the shadow stack for a new thread. 2416024598e40c84666cc311a42c256bbf880db3ac99sewardj Note that this is used to create not only child thread stacks, but 2417024598e40c84666cc311a42c256bbf880db3ac99sewardj the root thread's stack too. We create a new stack with 2418024598e40c84666cc311a42c256bbf880db3ac99sewardj .creation_sp set to infinity, so that the outermost frame can never 2419024598e40c84666cc311a42c256bbf880db3ac99sewardj be removed (by shadowStack_unwind). The core calls this function 2420024598e40c84666cc311a42c256bbf880db3ac99sewardj as soon as a thread is created. We cannot yet get its SP value, 2421024598e40c84666cc311a42c256bbf880db3ac99sewardj since that may not yet be set. */ 2422024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void shadowStack_thread_create ( ThreadId parent, ThreadId child ) 2423024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 2424024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(is_sane_TId(child)); 2425024598e40c84666cc311a42c256bbf880db3ac99sewardj if (parent == VG_INVALID_THREADID) { 2426024598e40c84666cc311a42c256bbf880db3ac99sewardj /* creating the main thread's stack */ 2427024598e40c84666cc311a42c256bbf880db3ac99sewardj } else { 2428024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(is_sane_TId(parent)); 2429024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(parent != child); 2430024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(shadowStacks[parent] != NULL); 2431024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(siTrees[parent] != NULL); 2432024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2433024598e40c84666cc311a42c256bbf880db3ac99sewardj 2434024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Create the child's stack. Bear in mind we may be re-using 2435024598e40c84666cc311a42c256bbf880db3ac99sewardj it. */ 2436024598e40c84666cc311a42c256bbf880db3ac99sewardj if (shadowStacks[child] == NULL) { 2437024598e40c84666cc311a42c256bbf880db3ac99sewardj /* First use of this stack. Just allocate an initial frame. */ 2438024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(siTrees[child] == NULL); 2439024598e40c84666cc311a42c256bbf880db3ac99sewardj } else { 2440024598e40c84666cc311a42c256bbf880db3ac99sewardj StackFrame *frame, *frame2; 2441024598e40c84666cc311a42c256bbf880db3ac99sewardj /* re-using a stack. */ 2442024598e40c84666cc311a42c256bbf880db3ac99sewardj /* get rid of the interval tree */ 2443024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(siTrees[child] != NULL); 2444024598e40c84666cc311a42c256bbf880db3ac99sewardj delete_StackTree( siTrees[child] ); 2445024598e40c84666cc311a42c256bbf880db3ac99sewardj siTrees[child] = NULL; 2446024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Throw away all existing frames. */ 2447024598e40c84666cc311a42c256bbf880db3ac99sewardj frame = shadowStacks[child]; 2448024598e40c84666cc311a42c256bbf880db3ac99sewardj while (frame->outer) 2449024598e40c84666cc311a42c256bbf880db3ac99sewardj frame = frame->outer; 2450024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(frame->depth == 0); 2451024598e40c84666cc311a42c256bbf880db3ac99sewardj while (frame) { 2452024598e40c84666cc311a42c256bbf880db3ac99sewardj frame2 = frame->inner; 2453024598e40c84666cc311a42c256bbf880db3ac99sewardj if (frame2) tl_assert(1 + frame->depth == frame2->depth); 2454024598e40c84666cc311a42c256bbf880db3ac99sewardj sg_free(frame); 2455024598e40c84666cc311a42c256bbf880db3ac99sewardj frame = frame2; 2456024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2457024598e40c84666cc311a42c256bbf880db3ac99sewardj shadowStacks[child] = NULL; 2458024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2459024598e40c84666cc311a42c256bbf880db3ac99sewardj 2460024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(shadowStacks[child] == NULL); 2461024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(siTrees[child] == NULL); 2462024598e40c84666cc311a42c256bbf880db3ac99sewardj 2463024598e40c84666cc311a42c256bbf880db3ac99sewardj /* Set up the initial stack frame. */ 2464024598e40c84666cc311a42c256bbf880db3ac99sewardj shadowStacks[child] = new_root_StackFrame(); 2465024598e40c84666cc311a42c256bbf880db3ac99sewardj 2466024598e40c84666cc311a42c256bbf880db3ac99sewardj /* and set up the child's stack block interval tree. */ 2467024598e40c84666cc311a42c256bbf880db3ac99sewardj siTrees[child] = new_StackTree(); 2468024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2469024598e40c84666cc311a42c256bbf880db3ac99sewardj 2470024598e40c84666cc311a42c256bbf880db3ac99sewardj/* Once a thread is ready to go, the core calls here. We take the 2471024598e40c84666cc311a42c256bbf880db3ac99sewardj opportunity to push a second frame on its stack, with the 2472024598e40c84666cc311a42c256bbf880db3ac99sewardj presumably valid SP value that is going to be used for the thread's 2473024598e40c84666cc311a42c256bbf880db3ac99sewardj startup. Hence we should always wind up with a valid outermost 2474024598e40c84666cc311a42c256bbf880db3ac99sewardj frame for the thread. */ 2475024598e40c84666cc311a42c256bbf880db3ac99sewardjstatic void shadowStack_set_initial_SP ( ThreadId tid ) 2476024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 2477024598e40c84666cc311a42c256bbf880db3ac99sewardj StackFrame* sf; 2478024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(is_sane_TId(tid)); 2479024598e40c84666cc311a42c256bbf880db3ac99sewardj sf = shadowStacks[tid]; 2480024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(sf != NULL); 2481024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(sf->outer == NULL); 2482024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(sf->inner == NULL); 2483024598e40c84666cc311a42c256bbf880db3ac99sewardj tl_assert(sf->creation_sp == ~0UL); 2484024598e40c84666cc311a42c256bbf880db3ac99sewardj shadowStack_new_frame( tid, 0, VG_(get_SP)(tid), 2485024598e40c84666cc311a42c256bbf880db3ac99sewardj 0, VG_(get_IP)(tid), NULL ); 2486024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2487024598e40c84666cc311a42c256bbf880db3ac99sewardj 2488024598e40c84666cc311a42c256bbf880db3ac99sewardj 2489024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 2490024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 2491024598e40c84666cc311a42c256bbf880db3ac99sewardj// main-ish // 2492024598e40c84666cc311a42c256bbf880db3ac99sewardj// // 2493024598e40c84666cc311a42c256bbf880db3ac99sewardj////////////////////////////////////////////////////////////// 2494024598e40c84666cc311a42c256bbf880db3ac99sewardj 2495024598e40c84666cc311a42c256bbf880db3ac99sewardj/* CALLED indirectly FROM GENERATED CODE. Calls here are created by 2496024598e40c84666cc311a42c256bbf880db3ac99sewardj sp-change analysis, as requested in pc_pre_clo_int(). */ 2497024598e40c84666cc311a42c256bbf880db3ac99sewardjvoid sg_die_mem_stack ( Addr old_SP, SizeT len ) { 2498024598e40c84666cc311a42c256bbf880db3ac99sewardj ThreadId tid = VG_(get_running_tid)(); 2499024598e40c84666cc311a42c256bbf880db3ac99sewardj shadowStack_unwind( tid, old_SP+len ); 2500024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2501024598e40c84666cc311a42c256bbf880db3ac99sewardj 2502024598e40c84666cc311a42c256bbf880db3ac99sewardjvoid sg_pre_clo_init ( void ) { 2503024598e40c84666cc311a42c256bbf880db3ac99sewardj ourGlobals_init(); 2504024598e40c84666cc311a42c256bbf880db3ac99sewardj init_StackBlocks_set(); 2505024598e40c84666cc311a42c256bbf880db3ac99sewardj init_GlobalBlock_set(); 2506024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2507024598e40c84666cc311a42c256bbf880db3ac99sewardj 2508024598e40c84666cc311a42c256bbf880db3ac99sewardjvoid sg_post_clo_init ( void ) { 2509024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2510024598e40c84666cc311a42c256bbf880db3ac99sewardj 2511024598e40c84666cc311a42c256bbf880db3ac99sewardjvoid sg_pre_thread_ll_create ( ThreadId parent, ThreadId child ) { 2512024598e40c84666cc311a42c256bbf880db3ac99sewardj shadowStack_thread_create(parent, child); 2513024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2514024598e40c84666cc311a42c256bbf880db3ac99sewardj 2515024598e40c84666cc311a42c256bbf880db3ac99sewardjvoid sg_pre_thread_first_insn ( ThreadId tid ) { 2516024598e40c84666cc311a42c256bbf880db3ac99sewardj shadowStack_set_initial_SP(tid); 2517024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2518024598e40c84666cc311a42c256bbf880db3ac99sewardj 2519024598e40c84666cc311a42c256bbf880db3ac99sewardjvoid sg_fini(Int exitcode) 2520024598e40c84666cc311a42c256bbf880db3ac99sewardj{ 25212d9e874b7a628ada216f09cc4f065798c65fffa4sewardj if (VG_(clo_stats)) { 2522024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(message)(Vg_DebugMsg, 2523c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj " sg_: %'llu total accesses, of which:\n", stats__total_accesses); 2524024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(message)(Vg_DebugMsg, 2525c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj " sg_: stack0: %'12llu classify\n", 2526024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__classify_Stack0); 2527024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(message)(Vg_DebugMsg, 2528c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj " sg_: stackN: %'12llu classify\n", 2529024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__classify_StackN); 2530024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(message)(Vg_DebugMsg, 2531c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj " sg_: global: %'12llu classify\n", 2532024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__classify_Global); 2533024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(message)(Vg_DebugMsg, 2534c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj " sg_: unknown: %'12llu classify\n", 2535024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__classify_Unknown); 2536024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(message)(Vg_DebugMsg, 2537c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj " sg_: %'llu Invars preened, of which %'llu changed\n", 2538024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__Invars_preened, stats__Invars_changed); 2539024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(message)(Vg_DebugMsg, 2540c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj " sg_: t_i_b_MT: %'12llu\n", stats__t_i_b_empty); 2541024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(message)(Vg_DebugMsg, 2542c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj " sg_: qcache: %'llu searches, %'llu probes, %'llu misses\n", 2543024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__qcache_queries, stats__qcache_probes, stats__qcache_misses); 2544024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(message)(Vg_DebugMsg, 2545c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj " sg_: htab-fast: %'llu hits\n", 2546024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__htab_fast); 2547024598e40c84666cc311a42c256bbf880db3ac99sewardj VG_(message)(Vg_DebugMsg, 2548c1bc9d1214d8c057eb2e96f3e96454688e5488c4sewardj " sg_: htab-slow: %'llu searches, %'llu probes, %'llu resizes\n", 2549024598e40c84666cc311a42c256bbf880db3ac99sewardj stats__htab_searches, stats__htab_probes, stats__htab_resizes); 2550024598e40c84666cc311a42c256bbf880db3ac99sewardj } 2551024598e40c84666cc311a42c256bbf880db3ac99sewardj} 2552024598e40c84666cc311a42c256bbf880db3ac99sewardj 2553024598e40c84666cc311a42c256bbf880db3ac99sewardj 2554024598e40c84666cc311a42c256bbf880db3ac99sewardj/*--------------------------------------------------------------------*/ 2555024598e40c84666cc311a42c256bbf880db3ac99sewardj/*--- end sg_main.c ---*/ 2556024598e40c84666cc311a42c256bbf880db3ac99sewardj/*--------------------------------------------------------------------*/ 2557