1
2 /*--------------------------------------------------------------------*/
3 /*--- Representation of source level types. tytypes.c ---*/
4 /*--------------------------------------------------------------------*/
5
6 /*
7 This file is part of Valgrind, a dynamic binary instrumentation
8 framework.
9
10 Copyright (C) 2008-2017 OpenWorks LLP
11 info@open-works.co.uk
12
13 This program is free software; you can redistribute it and/or
14 modify it under the terms of the GNU General Public License as
15 published by the Free Software Foundation; either version 2 of the
16 License, or (at your option) any later version.
17
18 This program is distributed in the hope that it will be useful, but
19 WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 General Public License for more details.
22
23 You should have received a copy of the GNU General Public License
24 along with this program; if not, write to the Free Software
25 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
26 02111-1307, USA.
27
28 The GNU General Public License is contained in the file COPYING.
29
30 Neither the names of the U.S. Department of Energy nor the
31 University of California nor the names of its contributors may be
32 used to endorse or promote products derived from this software
33 without prior written permission.
34 */
35
36 #include "pub_core_basics.h"
37 #include "pub_core_debuginfo.h"
38 #include "pub_core_libcassert.h"
39 #include "pub_core_libcbase.h"
40 #include "pub_core_libcprint.h"
41 #include "pub_core_xarray.h" /* to keep priv_tytypes.h happy */
42
43 #include "priv_misc.h" /* dinfo_zalloc/free/strdup */
44 #include "priv_d3basics.h" /* ML_(evaluate_Dwarf3_Expr) et al */
45 #include "priv_tytypes.h" /* self */
46
47
48 /* Does this TyEnt denote a type, as opposed to some other kind of
49 thing? */
50
ML_(TyEnt__is_type)51 Bool ML_(TyEnt__is_type)( const TyEnt* te )
52 {
53 switch (te->tag) {
54 case Te_EMPTY: case Te_INDIR: case Te_UNKNOWN:
55 case Te_Atom: case Te_Field: case Te_Bound:
56 return False;
57 case Te_TyBase: case Te_TyPtr: case Te_TyRef:
58 case Te_TyPtrMbr: case Te_TyRvalRef: case Te_TyTyDef:
59 case Te_TyStOrUn: case Te_TyEnum: case Te_TyArray:
60 case Te_TyFn: case Te_TyQual: case Te_TyVoid:
61 return True;
62 default:
63 vg_assert(0);
64 }
65 }
66
67
68 /* Print a TyEnt, debug-style. */
69
pp_XArray_of_cuOffs(const XArray * xa)70 static void pp_XArray_of_cuOffs ( const XArray* xa )
71 {
72 Word i;
73 VG_(printf)("{");
74 for (i = 0; i < VG_(sizeXA)(xa); i++) {
75 UWord cuOff = *(UWord*)VG_(indexXA)(xa, i);
76 VG_(printf)("0x%05lx", cuOff);
77 if (i+1 < VG_(sizeXA)(xa))
78 VG_(printf)(",");
79 }
80 VG_(printf)("}");
81 }
82
ML_(pp_TyEnt)83 void ML_(pp_TyEnt)( const TyEnt* te )
84 {
85 VG_(printf)("0x%05lx ", te->cuOff);
86 switch (te->tag) {
87 case Te_EMPTY:
88 VG_(printf)("EMPTY");
89 break;
90 case Te_INDIR:
91 VG_(printf)("INDIR(0x%05lx)", te->Te.INDIR.indR);
92 break;
93 case Te_UNKNOWN:
94 VG_(printf)("UNKNOWN");
95 break;
96 case Te_Atom:
97 VG_(printf)("Te_Atom(%s%lld,\"%s\")",
98 te->Te.Atom.valueKnown ? "" : "unknown:",
99 te->Te.Atom.value, te->Te.Atom.name);
100 break;
101 case Te_Field:
102 if (te->Te.Field.nLoc == -1)
103 VG_(printf)("Te_Field(ty=0x%05lx,pos.offset=%ld,\"%s\")",
104 te->Te.Field.typeR, te->Te.Field.pos.offset,
105 te->Te.Field.name ? te->Te.Field.name : "");
106 else
107 VG_(printf)("Te_Field(ty=0x%05lx,nLoc=%ld,pos.loc=%p,\"%s\")",
108 te->Te.Field.typeR, te->Te.Field.nLoc,
109 te->Te.Field.pos.loc,
110 te->Te.Field.name ? te->Te.Field.name : "");
111 break;
112 case Te_Bound:
113 VG_(printf)("Te_Bound[");
114 if (te->Te.Bound.knownL)
115 VG_(printf)("%lld", te->Te.Bound.boundL);
116 else
117 VG_(printf)("??");
118 VG_(printf)(",");
119 if (te->Te.Bound.knownU)
120 VG_(printf)("%lld", te->Te.Bound.boundU);
121 else
122 VG_(printf)("??");
123 VG_(printf)("]");
124 break;
125 case Te_TyBase:
126 VG_(printf)("Te_TyBase(%d,%c,\"%s\")",
127 te->Te.TyBase.szB, te->Te.TyBase.enc,
128 te->Te.TyBase.name ? te->Te.TyBase.name
129 : "(null)" );
130 break;
131 case Te_TyPtr:
132 VG_(printf)("Te_TyPtr(%d,0x%05lx)", te->Te.TyPorR.szB,
133 te->Te.TyPorR.typeR);
134 break;
135 case Te_TyRef:
136 VG_(printf)("Te_TyRef(%d,0x%05lx)", te->Te.TyPorR.szB,
137 te->Te.TyPorR.typeR);
138 break;
139 case Te_TyPtrMbr:
140 VG_(printf)("Te_TyMbr(%d,0x%05lx)", te->Te.TyPorR.szB,
141 te->Te.TyPorR.typeR);
142 break;
143 case Te_TyRvalRef:
144 VG_(printf)("Te_TyRvalRef(%d,0x%05lx)", te->Te.TyPorR.szB,
145 te->Te.TyPorR.typeR);
146 break;
147 case Te_TyTyDef:
148 VG_(printf)("Te_TyTyDef(0x%05lx,\"%s\")",
149 te->Te.TyTyDef.typeR,
150 te->Te.TyTyDef.name ? te->Te.TyTyDef.name
151 : "" );
152 break;
153 case Te_TyStOrUn:
154 if (te->Te.TyStOrUn.complete) {
155 VG_(printf)("Te_TyStOrUn(%lu,%c,%p,\"%s\")",
156 te->Te.TyStOrUn.szB,
157 te->Te.TyStOrUn.isStruct ? 'S' : 'U',
158 te->Te.TyStOrUn.fieldRs,
159 te->Te.TyStOrUn.name ? te->Te.TyStOrUn.name
160 : "" );
161 pp_XArray_of_cuOffs( te->Te.TyStOrUn.fieldRs );
162 } else {
163 VG_(printf)("Te_TyStOrUn(INCOMPLETE,\"%s\")",
164 te->Te.TyStOrUn.name);
165 }
166 break;
167 case Te_TyEnum:
168 VG_(printf)("Te_TyEnum(%d,%p,\"%s\")",
169 te->Te.TyEnum.szB, te->Te.TyEnum.atomRs,
170 te->Te.TyEnum.name ? te->Te.TyEnum.name
171 : "" );
172 if (te->Te.TyEnum.atomRs)
173 pp_XArray_of_cuOffs( te->Te.TyEnum.atomRs );
174 break;
175 case Te_TyArray:
176 VG_(printf)("Te_TyArray(0x%05lx,%p)",
177 te->Te.TyArray.typeR, te->Te.TyArray.boundRs);
178 if (te->Te.TyArray.boundRs)
179 pp_XArray_of_cuOffs( te->Te.TyArray.boundRs );
180 break;
181 case Te_TyFn:
182 VG_(printf)("Te_TyFn");
183 break;
184 case Te_TyQual:
185 VG_(printf)("Te_TyQual(%c,0x%05lx)", te->Te.TyQual.qual,
186 te->Te.TyQual.typeR);
187 break;
188 case Te_TyVoid:
189 VG_(printf)("Te_TyVoid%s",
190 te->Te.TyVoid.isFake ? "(fake)" : "");
191 break;
192 default:
193 vg_assert(0);
194 }
195 }
196
197
198 /* Print a whole XArray of TyEnts, debug-style */
199
ML_(pp_TyEnts)200 void ML_(pp_TyEnts)( const XArray* tyents, const HChar* who )
201 {
202 Word i, n;
203 VG_(printf)("------ %s ------\n", who);
204 n = VG_(sizeXA)( tyents );
205 for (i = 0; i < n; i++) {
206 const TyEnt* tyent = VG_(indexXA)( tyents, i );
207 VG_(printf)(" [%5ld] ", i);
208 ML_(pp_TyEnt)( tyent );
209 VG_(printf)("\n");
210 }
211 }
212
213
214 /* Print a TyEnt, C style, chasing stuff as necessary. */
215
pp_TyBound_C_ishly(const XArray * tyents,UWord cuOff)216 static void pp_TyBound_C_ishly ( const XArray* tyents, UWord cuOff )
217 {
218 TyEnt* ent = ML_(TyEnts__index_by_cuOff)( tyents, NULL, cuOff );
219 if (!ent) {
220 VG_(printf)("**bounds-have-invalid-cuOff**");
221 return;
222 }
223 vg_assert(ent->tag == Te_Bound);
224 if (ent->Te.Bound.knownL && ent->Te.Bound.knownU
225 && ent->Te.Bound.boundL == 0) {
226 VG_(printf)("[%lld]", 1 + ent->Te.Bound.boundU);
227 }
228 else
229 if (ent->Te.Bound.knownL && (!ent->Te.Bound.knownU)
230 && ent->Te.Bound.boundL == 0) {
231 VG_(printf)("[]");
232 }
233 else
234 ML_(pp_TyEnt)( ent );
235 }
236
ML_(pp_TyEnt_C_ishly)237 void ML_(pp_TyEnt_C_ishly)( const XArray* /* of TyEnt */ tyents,
238 UWord cuOff )
239 {
240 TyEnt* ent = ML_(TyEnts__index_by_cuOff)( tyents, NULL, cuOff );
241 if (!ent) {
242 VG_(printf)("**type-has-invalid-cuOff**");
243 return;
244 }
245 switch (ent->tag) {
246 case Te_TyBase:
247 if (!ent->Te.TyBase.name) goto unhandled;
248 VG_(printf)("%s", ent->Te.TyBase.name);
249 break;
250 case Te_TyPtr:
251 ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyPorR.typeR);
252 VG_(printf)("*");
253 break;
254 case Te_TyRef:
255 ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyPorR.typeR);
256 VG_(printf)("&");
257 break;
258 case Te_TyPtrMbr:
259 ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyPorR.typeR);
260 VG_(printf)("*");
261 break;
262 case Te_TyRvalRef:
263 ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyPorR.typeR);
264 VG_(printf)("&&");
265 break;
266 case Te_TyEnum:
267 VG_(printf)("enum %s", ent->Te.TyEnum.name ? ent->Te.TyEnum.name
268 : "<anonymous>" );
269 break;
270 case Te_TyStOrUn:
271 VG_(printf)("%s %s",
272 ent->Te.TyStOrUn.isStruct ? "struct" : "union",
273 ent->Te.TyStOrUn.name ? ent->Te.TyStOrUn.name
274 : "<anonymous>" );
275 break;
276 case Te_TyArray:
277 ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyArray.typeR);
278 if (ent->Te.TyArray.boundRs) {
279 Word w;
280 XArray* xa = ent->Te.TyArray.boundRs;
281 for (w = 0; w < VG_(sizeXA)(xa); w++) {
282 pp_TyBound_C_ishly( tyents, *(UWord*)VG_(indexXA)(xa, w) );
283 }
284 } else {
285 VG_(printf)("%s", "[??]");
286 }
287 break;
288 case Te_TyTyDef:
289 VG_(printf)("%s", ent->Te.TyTyDef.name ? ent->Te.TyTyDef.name
290 : "<anonymous>" );
291 break;
292 case Te_TyFn:
293 VG_(printf)("%s", "<function_type>");
294 break;
295 case Te_TyQual:
296 switch (ent->Te.TyQual.qual) {
297 case 'C': VG_(printf)("const "); break;
298 case 'V': VG_(printf)("volatile "); break;
299 case 'R': VG_(printf)("restrict "); break;
300 default: goto unhandled;
301 }
302 ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyQual.typeR);
303 break;
304 case Te_TyVoid:
305 VG_(printf)("%svoid",
306 ent->Te.TyVoid.isFake ? "fake" : "");
307 break;
308 case Te_UNKNOWN:
309 ML_(pp_TyEnt)(ent);
310 break;
311 default:
312 goto unhandled;
313 }
314 return;
315
316 unhandled:
317 VG_(printf)("pp_TyEnt_C_ishly:unhandled: ");
318 ML_(pp_TyEnt)(ent);
319 vg_assert(0);
320 }
321
322
323 /* 'ents' is an XArray of TyEnts, sorted by their .cuOff fields. Find
324 the entry which has .cuOff field as specified. Returns NULL if not
325 found. Asserts if more than one entry has the specified .cuOff
326 value. */
327
ML_(TyEntIndexCache__invalidate)328 void ML_(TyEntIndexCache__invalidate) ( TyEntIndexCache* cache )
329 {
330 Word i;
331 for (i = 0; i < N_TYENT_INDEX_CACHE; i++) {
332 cache->ce[i].cuOff0 = 0; /* not actually necessary */
333 cache->ce[i].ent0 = NULL; /* "invalid entry" */
334 cache->ce[i].cuOff1 = 0; /* not actually necessary */
335 cache->ce[i].ent1 = NULL; /* "invalid entry" */
336 }
337 }
338
ML_(TyEnts__index_by_cuOff)339 TyEnt* ML_(TyEnts__index_by_cuOff) ( const XArray* /* of TyEnt */ ents,
340 TyEntIndexCache* cache,
341 UWord cuOff_to_find )
342 {
343 Bool found;
344 Word first, last;
345 TyEnt key, *res;
346
347 /* crude stats, aggregated over all caches */
348 static UWord cacheQs = 0 - 1;
349 static UWord cacheHits = 0;
350
351 if (0 && 0 == (cacheQs & 0xFFFF))
352 VG_(printf)("cache: %'lu queries, %'lu misses\n",
353 cacheQs, cacheQs - cacheHits);
354
355 if (LIKELY(cache != NULL)) {
356 UWord h = cuOff_to_find % (UWord)N_TYENT_INDEX_CACHE;
357 cacheQs++;
358 // dude, like, way 0, dude.
359 if (cache->ce[h].cuOff0 == cuOff_to_find && cache->ce[h].ent0 != NULL) {
360 // dude, way 0 is a total hit!
361 cacheHits++;
362 return cache->ce[h].ent0;
363 }
364 // dude, check out way 1, dude.
365 if (cache->ce[h].cuOff1 == cuOff_to_find && cache->ce[h].ent1 != NULL) {
366 // way 1 hit
367 UWord tc;
368 TyEnt* te;
369 cacheHits++;
370 // dude, way 1 is the new way 0. move with the times, dude.
371 tc = cache->ce[h].cuOff0;
372 te = cache->ce[h].ent0;
373 cache->ce[h].cuOff0 = cache->ce[h].cuOff1;
374 cache->ce[h].ent0 = cache->ce[h].ent1;
375 cache->ce[h].cuOff1 = tc;
376 cache->ce[h].ent1 = te;
377 return cache->ce[h].ent0;
378 }
379 }
380
381 /* We'll have to do it the hard way */
382 key.cuOff = cuOff_to_find;
383 key.tag = Te_EMPTY;
384 found = VG_(lookupXA)( ents, &key, &first, &last );
385 //found = VG_(lookupXA_UNBOXED)( ents, cuOff_to_find, &first, &last,
386 // offsetof(TyEnt,cuOff) );
387 if (!found)
388 return NULL;
389 /* If this fails, the array is invalid in the sense that there is
390 more than one entry with .cuOff == cuOff_to_find. */
391 vg_assert(first == last);
392 res = (TyEnt*)VG_(indexXA)( ents, first );
393
394 if (LIKELY(cache != NULL) && LIKELY(res != NULL)) {
395 /* this is a bit stupid, computing this twice. Oh well.
396 Perhaps some magic gcc transformation will common them up.
397 re "res != NULL", since .ent of NULL denotes 'invalid entry',
398 we can't cache the result when res == NULL. */
399 UWord h = cuOff_to_find % (UWord)N_TYENT_INDEX_CACHE;
400 cache->ce[h].cuOff1 = cache->ce[h].cuOff0;
401 cache->ce[h].ent1 = cache->ce[h].ent0;
402 cache->ce[h].cuOff0 = cuOff_to_find;
403 cache->ce[h].ent0 = res;
404 }
405
406 return res;
407 }
408
409
410 /* Generates a total ordering on TyEnts based only on their .cuOff
411 fields. */
412
ML_(TyEnt__cmp_by_cuOff_only)413 Word ML_(TyEnt__cmp_by_cuOff_only) ( const TyEnt* te1, const TyEnt* te2 )
414 {
415 if (te1->cuOff < te2->cuOff) return -1;
416 if (te1->cuOff > te2->cuOff) return 1;
417 return 0;
418 }
419
420
421 /* Generates a total ordering on TyEnts based on everything except
422 their .cuOff fields. */
UWord__cmp(UWord a,UWord b)423 static inline Word UWord__cmp ( UWord a, UWord b ) {
424 if (a < b) return -1;
425 if (a > b) return 1;
426 return 0;
427 }
Long__cmp(Long a,Long b)428 static inline Word Long__cmp ( Long a, Long b ) {
429 if (a < b) return -1;
430 if (a > b) return 1;
431 return 0;
432 }
Bool__cmp(Bool a,Bool b)433 static inline Word Bool__cmp ( Bool a, Bool b ) {
434 vg_assert( ((UWord)a) <= 1 );
435 vg_assert( ((UWord)b) <= 1 );
436 if (a < b) return -1;
437 if (a > b) return 1;
438 return 0;
439 }
UChar__cmp(UChar a,UChar b)440 static inline Word UChar__cmp ( UChar a, UChar b ) {
441 if (a < b) return -1;
442 if (a > b) return 1;
443 return 0;
444 }
Int__cmp(Int a,Int b)445 static inline Word Int__cmp ( Int a, Int b ) {
446 if (a < b) return -1;
447 if (a > b) return 1;
448 return 0;
449 }
XArray_of_UWord__cmp(const XArray * a,const XArray * b)450 static Word XArray_of_UWord__cmp ( const XArray* a, const XArray* b ) {
451 Word i, r;
452 Word aN = VG_(sizeXA)( a );
453 Word bN = VG_(sizeXA)( b );
454 if (aN < bN) return -1;
455 if (aN > bN) return 1;
456 for (i = 0; i < aN; i++) {
457 r = UWord__cmp( *(UWord*)VG_(indexXA)( a, i ),
458 *(UWord*)VG_(indexXA)( b, i ) );
459 if (r != 0) return r;
460 }
461 return 0;
462 }
Bytevector__cmp(const UChar * a,const UChar * b,Word n)463 static Word Bytevector__cmp ( const UChar* a, const UChar* b, Word n ) {
464 Word i, r;
465 vg_assert(n >= 0);
466 for (i = 0; i < n; i++) {
467 r = UChar__cmp( a[i], b[i] );
468 if (r != 0) return r;
469 }
470 return 0;
471 }
Asciiz__cmp(const HChar * a,const HChar * b)472 static Word Asciiz__cmp ( const HChar* a, const HChar* b ) {
473 /* A wrapper around strcmp that handles NULL strings safely. */
474 if (a == NULL && b == NULL) return 0;
475 if (a == NULL && b != NULL) return -1;
476 if (a != NULL && b == NULL) return 1;
477 return VG_(strcmp)(a, b);
478 }
479
ML_(TyEnt__cmp_by_all_except_cuOff)480 Word ML_(TyEnt__cmp_by_all_except_cuOff) ( const TyEnt* te1, const TyEnt* te2 )
481 {
482 Word r;
483 if (te1->tag < te2->tag) return -1;
484 if (te1->tag > te2->tag) return 1;
485 switch (te1->tag) {
486 case Te_EMPTY:
487 return 0;
488 case Te_INDIR:
489 r = UWord__cmp(te1->Te.INDIR.indR, te2->Te.INDIR.indR);
490 return r;
491 case Te_Atom:
492 r = Bool__cmp(te1->Te.Atom.valueKnown, te2->Te.Atom.valueKnown);
493 if (r != 0) return r;
494 r = Long__cmp(te1->Te.Atom.value, te2->Te.Atom.value);
495 if (r != 0) return r;
496 r = Asciiz__cmp(te1->Te.Atom.name, te2->Te.Atom.name);
497 return r;
498 case Te_Field:
499 r = Bool__cmp(te1->Te.Field.isStruct, te2->Te.Field.isStruct);
500 if (r != 0) return r;
501 r = UWord__cmp(te1->Te.Field.typeR, te2->Te.Field.typeR);
502 if (r != 0) return r;
503 r = Asciiz__cmp(te1->Te.Field.name, te2->Te.Field.name);
504 if (r != 0) return r;
505 r = UWord__cmp(te1->Te.Field.nLoc, te2->Te.Field.nLoc);
506 if (r != 0) return r;
507 if (te1->Te.Field.nLoc == -1)
508 r = Long__cmp(te1->Te.Field.pos.offset, te2->Te.Field.pos.offset);
509 else
510 r = Bytevector__cmp(te1->Te.Field.pos.loc, te2->Te.Field.pos.loc,
511 te1->Te.Field.nLoc);
512 return r;
513 case Te_Bound:
514 r = Bool__cmp(te1->Te.Bound.knownL, te2->Te.Bound.knownL);
515 if (r != 0) return r;
516 r = Bool__cmp(te1->Te.Bound.knownU, te2->Te.Bound.knownU);
517 if (r != 0) return r;
518 r = Long__cmp(te1->Te.Bound.boundL, te2->Te.Bound.boundL);
519 if (r != 0) return r;
520 r = Long__cmp(te1->Te.Bound.boundU, te2->Te.Bound.boundU);
521 return r;
522 case Te_TyBase:
523 r = UChar__cmp(te1->Te.TyBase.enc, te2->Te.TyBase.enc);
524 if (r != 0) return r;
525 r = Int__cmp(te1->Te.TyBase.szB, te2->Te.TyBase.szB);
526 if (r != 0) return r;
527 r = Asciiz__cmp(te1->Te.TyBase.name, te2->Te.TyBase.name);
528 return r;
529 case Te_TyPtr:
530 case Te_TyRef:
531 case Te_TyPtrMbr:
532 case Te_TyRvalRef:
533 r = Int__cmp(te1->Te.TyPorR.szB, te2->Te.TyPorR.szB);
534 if (r != 0) return r;
535 r = UWord__cmp(te1->Te.TyPorR.typeR, te2->Te.TyPorR.typeR);
536 return r;
537 case Te_TyTyDef:
538 r = UWord__cmp(te1->Te.TyTyDef.typeR, te2->Te.TyTyDef.typeR);
539 if (r != 0) return r;
540 r = Asciiz__cmp(te1->Te.TyTyDef.name, te2->Te.TyTyDef.name);
541 return r;
542 case Te_TyStOrUn:
543 r = Bool__cmp(te1->Te.TyStOrUn.isStruct, te2->Te.TyStOrUn.isStruct);
544 if (r != 0) return r;
545 r = Bool__cmp(te1->Te.TyStOrUn.complete, te2->Te.TyStOrUn.complete);
546 if (r != 0) return r;
547 r = UWord__cmp(te1->Te.TyStOrUn.szB, te2->Te.TyStOrUn.szB);
548 if (r != 0) return r;
549 r = Asciiz__cmp(te1->Te.TyStOrUn.name, te2->Te.TyStOrUn.name);
550 if (r != 0) return r;
551 r = XArray_of_UWord__cmp(te1->Te.TyStOrUn.fieldRs,
552 te2->Te.TyStOrUn.fieldRs);
553 return r;
554 case Te_TyEnum:
555 r = Int__cmp(te1->Te.TyEnum.szB, te2->Te.TyEnum.szB);
556 if (r != 0) return r;
557 r = Asciiz__cmp(te1->Te.TyEnum.name, te2->Te.TyEnum.name);
558 if (r != 0) return r;
559 r = XArray_of_UWord__cmp(te1->Te.TyEnum.atomRs, te2->Te.TyEnum.atomRs);
560 return r;
561 case Te_TyArray:
562 r = UWord__cmp(te1->Te.TyArray.typeR, te2->Te.TyArray.typeR);
563 if (r != 0) return r;
564 r = XArray_of_UWord__cmp(te1->Te.TyArray.boundRs,
565 te2->Te.TyArray.boundRs);
566 return r;
567 case Te_TyFn:
568 return 0;
569 case Te_TyQual:
570 r = UWord__cmp(te1->Te.TyQual.typeR, te2->Te.TyQual.typeR);
571 if (r != 0) return r;
572 r = UChar__cmp(te1->Te.TyQual.qual, te2->Te.TyQual.qual);
573 return r;
574 case Te_TyVoid:
575 r = Bool__cmp(te1->Te.TyVoid.isFake, te2->Te.TyVoid.isFake);
576 return r;
577 default:
578 vg_assert(0);
579 }
580 }
581
582
583 /* Free up all directly or indirectly heap-allocated stuff attached to
584 this TyEnt, and set its tag to Te_EMPTY. The .cuOff field is
585 unchanged. */
586
ML_(TyEnt__make_EMPTY)587 void ML_(TyEnt__make_EMPTY) ( TyEnt* te )
588 {
589 UWord saved_cuOff;
590 /* First, free up any fields in mallocville. */
591 switch (te->tag) {
592 case Te_EMPTY:
593 break;
594 case Te_INDIR:
595 break;
596 case Te_UNKNOWN:
597 break;
598 case Te_Atom:
599 if (te->Te.Atom.name) ML_(dinfo_free)(te->Te.Atom.name);
600 break;
601 case Te_Field:
602 if (te->Te.Field.name) ML_(dinfo_free)(te->Te.Field.name);
603 if (te->Te.Field.nLoc > 0 && te->Te.Field.pos.loc)
604 ML_(dinfo_free)(te->Te.Field.pos.loc);
605 break;
606 case Te_Bound:
607 break;
608 case Te_TyBase:
609 if (te->Te.TyBase.name) ML_(dinfo_free)(te->Te.TyBase.name);
610 break;
611 case Te_TyPtr:
612 case Te_TyRef:
613 case Te_TyPtrMbr:
614 case Te_TyRvalRef:
615 break;
616 case Te_TyTyDef:
617 if (te->Te.TyTyDef.name) ML_(dinfo_free)(te->Te.TyTyDef.name);
618 break;
619 case Te_TyStOrUn:
620 if (te->Te.TyStOrUn.name) ML_(dinfo_free)(te->Te.TyStOrUn.name);
621 VG_(deleteXA)(te->Te.TyStOrUn.fieldRs);
622 break;
623 case Te_TyEnum:
624 if (te->Te.TyEnum.name) ML_(dinfo_free)(te->Te.TyEnum.name);
625 if (te->Te.TyEnum.atomRs) VG_(deleteXA)(te->Te.TyEnum.atomRs);
626 break;
627 case Te_TyArray:
628 if (te->Te.TyArray.boundRs) VG_(deleteXA)(te->Te.TyArray.boundRs);
629 break;
630 case Te_TyFn:
631 break;
632 case Te_TyQual:
633 break;
634 case Te_TyVoid:
635 break;
636 default:
637 vg_assert(0);
638 }
639 /* Now clear it out and set to Te_EMPTY. */
640 saved_cuOff = te->cuOff;
641 VG_(memset)(te, 0, sizeof(*te));
642 te->cuOff = saved_cuOff;
643 te->tag = Te_EMPTY;
644 }
645
646
647 /* How big is this type? If .b in the returned struct is False, the
648 size is unknown. */
649
mk_MaybeULong_Nothing(void)650 static MaybeULong mk_MaybeULong_Nothing ( void ) {
651 MaybeULong mul;
652 mul.ul = 0;
653 mul.b = False;
654 return mul;
655 }
mk_MaybeULong_Just(ULong ul)656 static MaybeULong mk_MaybeULong_Just ( ULong ul ) {
657 MaybeULong mul;
658 mul.ul = ul;
659 mul.b = True;
660 return mul;
661 }
mul_MaybeULong(MaybeULong mul1,MaybeULong mul2)662 static MaybeULong mul_MaybeULong ( MaybeULong mul1, MaybeULong mul2 ) {
663 if (!mul1.b) { vg_assert(mul1.ul == 0); return mul1; }
664 if (!mul2.b) { vg_assert(mul2.ul == 0); return mul2; }
665 mul1.ul *= mul2.ul;
666 return mul1;
667 }
668
ML_(sizeOfType)669 MaybeULong ML_(sizeOfType)( const XArray* /* of TyEnt */ tyents,
670 UWord cuOff )
671 {
672 Word i;
673 MaybeULong eszB;
674 TyEnt* ent = ML_(TyEnts__index_by_cuOff)(tyents, NULL, cuOff);
675 TyEnt* ent2;
676 vg_assert(ent);
677 vg_assert(ML_(TyEnt__is_type)(ent));
678 switch (ent->tag) {
679 case Te_TyBase:
680 vg_assert(ent->Te.TyBase.szB > 0);
681 return mk_MaybeULong_Just( ent->Te.TyBase.szB );
682 case Te_TyQual:
683 return ML_(sizeOfType)( tyents, ent->Te.TyQual.typeR );
684 case Te_TyTyDef:
685 ent2 = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
686 ent->Te.TyTyDef.typeR);
687 vg_assert(ent2);
688 if (ent2->tag == Te_UNKNOWN)
689 return mk_MaybeULong_Nothing(); /*UNKNOWN*/
690 return ML_(sizeOfType)( tyents, ent->Te.TyTyDef.typeR );
691 case Te_TyPtr:
692 case Te_TyRef:
693 case Te_TyPtrMbr:
694 case Te_TyRvalRef:
695 vg_assert(ent->Te.TyPorR.szB == 4 || ent->Te.TyPorR.szB == 8);
696 return mk_MaybeULong_Just( ent->Te.TyPorR.szB );
697 case Te_TyStOrUn:
698 return ent->Te.TyStOrUn.complete
699 ? mk_MaybeULong_Just( ent->Te.TyStOrUn.szB )
700 : mk_MaybeULong_Nothing();
701 case Te_TyEnum:
702 return mk_MaybeULong_Just( ent->Te.TyEnum.szB );
703 case Te_TyArray:
704 ent2 = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
705 ent->Te.TyArray.typeR);
706 vg_assert(ent2);
707 if (ent2->tag == Te_UNKNOWN)
708 return mk_MaybeULong_Nothing(); /*UNKNOWN*/
709 eszB = ML_(sizeOfType)( tyents, ent->Te.TyArray.typeR );
710 for (i = 0; i < VG_(sizeXA)( ent->Te.TyArray.boundRs ); i++) {
711 UWord bo_cuOff
712 = *(UWord*)VG_(indexXA)(ent->Te.TyArray.boundRs, i);
713 TyEnt* bo
714 = ML_(TyEnts__index_by_cuOff)( tyents, NULL, bo_cuOff );
715 vg_assert(bo);
716 vg_assert(bo->tag == Te_Bound);
717 if (!(bo->Te.Bound.knownL && bo->Te.Bound.knownU))
718 return mk_MaybeULong_Nothing(); /*UNKNOWN*/
719 eszB = mul_MaybeULong(
720 eszB,
721 mk_MaybeULong_Just( (ULong)(bo->Te.Bound.boundU
722 - bo->Te.Bound.boundL + 1) ));
723 }
724 return eszB;
725 case Te_TyVoid:
726 return mk_MaybeULong_Nothing(); /*UNKNOWN*/
727 default:
728 VG_(printf)("ML_(sizeOfType): unhandled: ");
729 ML_(pp_TyEnt)(ent);
730 VG_(printf)("\n");
731 vg_assert(0);
732 }
733 }
734
735
736 /* Describe where in the type 'offset' falls. Caller must
737 deallocate the resulting XArray. */
738
copy_UWord_into_XA(XArray * xa,UWord uw)739 static void copy_UWord_into_XA ( XArray* /* of HChar */ xa,
740 UWord uw ) {
741 HChar buf[32]; // large enough
742 VG_(sprintf)(buf, "%lu", uw);
743 VG_(addBytesToXA)( xa, buf, VG_(strlen)(buf));
744 }
745
ML_(describe_type)746 XArray* /*HChar*/ ML_(describe_type)( /*OUT*/PtrdiffT* residual_offset,
747 const XArray* /* of TyEnt */ tyents,
748 UWord ty_cuOff,
749 PtrdiffT offset )
750 {
751 TyEnt* ty;
752 XArray* xa = VG_(newXA)( ML_(dinfo_zalloc), "di.tytypes.dt.1",
753 ML_(dinfo_free),
754 sizeof(HChar) );
755
756 ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL, ty_cuOff);
757
758 while (True) {
759 vg_assert(ty);
760 vg_assert(ML_(TyEnt__is_type)(ty));
761
762 switch (ty->tag) {
763
764 /* These are all atomic types; there is nothing useful we can
765 do. */
766 case Te_TyEnum:
767 case Te_TyFn:
768 case Te_TyVoid:
769 case Te_TyPtr:
770 case Te_TyRef:
771 case Te_TyPtrMbr:
772 case Te_TyRvalRef:
773 case Te_TyBase:
774 goto done;
775
776 case Te_TyStOrUn: {
777 Word i;
778 GXResult res;
779 MaybeULong mul;
780 XArray* fieldRs;
781 UWord fieldR;
782 TyEnt* field = NULL;
783 PtrdiffT offMin = 0, offMax1 = 0;
784 if (!ty->Te.TyStOrUn.isStruct) goto done;
785 fieldRs = ty->Te.TyStOrUn.fieldRs;
786 if (VG_(sizeXA)(fieldRs) == 0
787 && (ty->Te.TyStOrUn.typeR == 0)) goto done;
788 for (i = 0; i < VG_(sizeXA)( fieldRs ); i++ ) {
789 fieldR = *(UWord*)VG_(indexXA)( fieldRs, i );
790 field = ML_(TyEnts__index_by_cuOff)(tyents, NULL, fieldR);
791 vg_assert(field);
792 vg_assert(field->tag == Te_Field);
793 vg_assert(field->Te.Field.nLoc < 0
794 || (field->Te.Field.nLoc > 0
795 && field->Te.Field.pos.loc));
796 if (field->Te.Field.nLoc == -1) {
797 res.kind = GXR_Addr;
798 res.word = field->Te.Field.pos.offset;
799 } else {
800 /* Re data_bias in this call, we should really send in
801 a legitimate value. But the expression is expected
802 to be a constant expression, evaluation of which
803 will not need to use DW_OP_addr and hence we can
804 avoid the trouble of plumbing the data bias through
805 to this point (if, indeed, it has any meaning; from
806 which DebugInfo would we take the data bias? */
807 res = ML_(evaluate_Dwarf3_Expr)(
808 field->Te.Field.pos.loc, field->Te.Field.nLoc,
809 NULL/*fbGX*/, NULL/*RegSummary*/,
810 0/*data_bias*/,
811 True/*push_initial_zero*/);
812 if (0) {
813 VG_(printf)("QQQ ");
814 ML_(pp_GXResult)(res);
815 VG_(printf)("\n");
816 }
817 }
818 if (res.kind != GXR_Addr)
819 continue;
820 mul = ML_(sizeOfType)( tyents, field->Te.Field.typeR );
821 if (mul.b != True)
822 goto done; /* size of field is unknown (?!) */
823 offMin = res.word;
824 offMax1 = offMin + (PtrdiffT)mul.ul;
825 if (offMin == offMax1)
826 continue;
827 vg_assert(offMin < offMax1);
828 if (offset >= offMin && offset < offMax1)
829 break;
830 }
831 /* Did we find a suitable field? */
832 vg_assert(i >= 0 && i <= VG_(sizeXA)( fieldRs ));
833 if (i == VG_(sizeXA)( fieldRs )) {
834 ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
835 ty->Te.TyStOrUn.typeR);
836 vg_assert(ty);
837 if (ty->tag == Te_UNKNOWN) goto done;
838 vg_assert(ML_(TyEnt__is_type)(ty));
839 continue;
840 }
841 /* Yes. 'field' is it. */
842 vg_assert(field);
843 if (!field->Te.Field.name) goto done;
844 VG_(addBytesToXA)( xa, ".", 1 );
845 VG_(addBytesToXA)( xa, field->Te.Field.name,
846 VG_(strlen)(field->Te.Field.name) );
847 offset -= offMin;
848 ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
849 field->Te.Field.typeR );
850 vg_assert(ty);
851 if (ty->tag == Te_UNKNOWN) goto done;
852 /* keep going; look inside the field. */
853 break;
854 }
855
856 case Te_TyArray: {
857 MaybeULong mul;
858 UWord size, eszB, ix;
859 UWord boundR;
860 TyEnt* elemTy;
861 TyEnt* bound;
862 /* Just deal with the simple, common C-case: 1-D array,
863 zero based, known size. */
864 elemTy = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
865 ty->Te.TyArray.typeR);
866 vg_assert(elemTy);
867 if (elemTy->tag == Te_UNKNOWN) goto done;
868 vg_assert(ML_(TyEnt__is_type)(elemTy));
869 if (!ty->Te.TyArray.boundRs)
870 goto done;
871 if (VG_(sizeXA)( ty->Te.TyArray.boundRs ) != 1) goto done;
872 boundR = *(UWord*)VG_(indexXA)( ty->Te.TyArray.boundRs, 0 );
873 bound = ML_(TyEnts__index_by_cuOff)(tyents, NULL, boundR);
874 vg_assert(bound);
875 vg_assert(bound->tag == Te_Bound);
876 if (!(bound->Te.Bound.knownL && bound->Te.Bound.knownU
877 && bound->Te.Bound.boundL == 0
878 && bound->Te.Bound.boundU >= bound->Te.Bound.boundL))
879 goto done;
880 size = bound->Te.Bound.boundU - bound->Te.Bound.boundL + 1;
881 vg_assert(size >= 1);
882 mul = ML_(sizeOfType)( tyents, ty->Te.TyArray.typeR );
883 if (mul.b != True)
884 goto done; /* size of element type not known */
885 eszB = mul.ul;
886 if (eszB == 0) goto done;
887 ix = offset / eszB;
888 VG_(addBytesToXA)( xa, "[", 1 );
889 copy_UWord_into_XA( xa, ix );
890 VG_(addBytesToXA)( xa, "]", 1 );
891 ty = elemTy;
892 offset -= ix * eszB;
893 /* keep going; look inside the array element. */
894 break;
895 }
896
897 case Te_TyQual: {
898 ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
899 ty->Te.TyQual.typeR);
900 vg_assert(ty);
901 if (ty->tag == Te_UNKNOWN) goto done;
902 break;
903 }
904
905 case Te_TyTyDef: {
906 ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
907 ty->Te.TyTyDef.typeR);
908 vg_assert(ty);
909 if (ty->tag == Te_UNKNOWN) goto done;
910 break;
911 }
912
913 default: {
914 VG_(printf)("ML_(describe_type): unhandled: ");
915 ML_(pp_TyEnt)(ty);
916 VG_(printf)("\n");
917 vg_assert(0);
918 }
919
920 }
921 }
922
923 done:
924 *residual_offset = offset;
925 VG_(addBytesToXA)( xa, "\0", 1 );
926 return xa;
927 }
928
929 /*--------------------------------------------------------------------*/
930 /*--- end tytypes.c ---*/
931 /*--------------------------------------------------------------------*/
932