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-2012 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)( 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(XArray * xa)70 static void pp_XArray_of_cuOffs ( 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)( 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 : (UChar*)"");
106 else
107 VG_(printf)("Te_Field(ty=0x%05lx,nLoc=%lu,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 : (UChar*)"");
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 : (UChar*)"(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 : (UChar*)"" );
152 break;
153 case Te_TyStOrUn:
154 if (te->Te.TyStOrUn.complete) {
155 VG_(printf)("Te_TyStOrUn(%ld,%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 : (UChar*)"" );
161 if (te->Te.TyStOrUn.fieldRs)
162 pp_XArray_of_cuOffs( te->Te.TyStOrUn.fieldRs );
163 } else {
164 VG_(printf)("Te_TyStOrUn(INCOMPLETE,\"%s\")",
165 te->Te.TyStOrUn.name);
166 }
167 break;
168 case Te_TyEnum:
169 VG_(printf)("Te_TyEnum(%d,%p,\"%s\")",
170 te->Te.TyEnum.szB, te->Te.TyEnum.atomRs,
171 te->Te.TyEnum.name ? te->Te.TyEnum.name
172 : (UChar*)"" );
173 if (te->Te.TyEnum.atomRs)
174 pp_XArray_of_cuOffs( te->Te.TyEnum.atomRs );
175 break;
176 case Te_TyArray:
177 VG_(printf)("Te_TyArray(0x%05lx,%p)",
178 te->Te.TyArray.typeR, te->Te.TyArray.boundRs);
179 if (te->Te.TyArray.boundRs)
180 pp_XArray_of_cuOffs( te->Te.TyArray.boundRs );
181 break;
182 case Te_TyFn:
183 VG_(printf)("Te_TyFn");
184 break;
185 case Te_TyQual:
186 VG_(printf)("Te_TyQual(%c,0x%05lx)", te->Te.TyQual.qual,
187 te->Te.TyQual.typeR);
188 break;
189 case Te_TyVoid:
190 VG_(printf)("Te_TyVoid%s",
191 te->Te.TyVoid.isFake ? "(fake)" : "");
192 break;
193 default:
194 vg_assert(0);
195 }
196 }
197
198
199 /* Print a whole XArray of TyEnts, debug-style */
200
ML_(pp_TyEnts)201 void ML_(pp_TyEnts)( XArray* tyents, HChar* who )
202 {
203 Word i, n;
204 VG_(printf)("------ %s ------\n", who);
205 n = VG_(sizeXA)( tyents );
206 for (i = 0; i < n; i++) {
207 TyEnt* tyent = (TyEnt*)VG_(indexXA)( tyents, i );
208 VG_(printf)(" [%5ld] ", i);
209 ML_(pp_TyEnt)( tyent );
210 VG_(printf)("\n");
211 }
212 }
213
214
215 /* Print a TyEnt, C style, chasing stuff as necessary. */
216
pp_TyBound_C_ishly(XArray * tyents,UWord cuOff)217 static void pp_TyBound_C_ishly ( XArray* tyents, UWord cuOff )
218 {
219 TyEnt* ent = ML_(TyEnts__index_by_cuOff)( tyents, NULL, cuOff );
220 if (!ent) {
221 VG_(printf)("**bounds-have-invalid-cuOff**");
222 return;
223 }
224 vg_assert(ent->tag == Te_Bound);
225 if (ent->Te.Bound.knownL && ent->Te.Bound.knownU
226 && ent->Te.Bound.boundL == 0) {
227 VG_(printf)("[%lld]", 1 + ent->Te.Bound.boundU);
228 }
229 else
230 if (ent->Te.Bound.knownL && (!ent->Te.Bound.knownU)
231 && ent->Te.Bound.boundL == 0) {
232 VG_(printf)("[]");
233 }
234 else
235 ML_(pp_TyEnt)( ent );
236 }
237
ML_(pp_TyEnt_C_ishly)238 void ML_(pp_TyEnt_C_ishly)( XArray* /* of TyEnt */ tyents,
239 UWord cuOff )
240 {
241 TyEnt* ent = ML_(TyEnts__index_by_cuOff)( tyents, NULL, cuOff );
242 if (!ent) {
243 VG_(printf)("**type-has-invalid-cuOff**");
244 return;
245 }
246 switch (ent->tag) {
247 case Te_TyBase:
248 if (!ent->Te.TyBase.name) goto unhandled;
249 VG_(printf)("%s", ent->Te.TyBase.name);
250 break;
251 case Te_TyPtr:
252 ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyPorR.typeR);
253 VG_(printf)("*");
254 break;
255 case Te_TyRef:
256 ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyPorR.typeR);
257 VG_(printf)("&");
258 break;
259 case Te_TyPtrMbr:
260 ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyPorR.typeR);
261 VG_(printf)("*");
262 break;
263 case Te_TyRvalRef:
264 ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyPorR.typeR);
265 VG_(printf)("&&");
266 break;
267 case Te_TyEnum:
268 if (!ent->Te.TyEnum.name) goto unhandled;
269 VG_(printf)("enum %s", ent->Te.TyEnum.name);
270 break;
271 case Te_TyStOrUn:
272 VG_(printf)("%s %s",
273 ent->Te.TyStOrUn.isStruct ? "struct" : "union",
274 ent->Te.TyStOrUn.name ? ent->Te.TyStOrUn.name
275 : (UChar*)"<anonymous>" );
276 break;
277 case Te_TyArray:
278 ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyArray.typeR);
279 if (ent->Te.TyArray.boundRs) {
280 Word w;
281 XArray* xa = ent->Te.TyArray.boundRs;
282 for (w = 0; w < VG_(sizeXA)(xa); w++) {
283 pp_TyBound_C_ishly( tyents, *(UWord*)VG_(indexXA)(xa, w) );
284 }
285 } else {
286 VG_(printf)("%s", "[??]");
287 }
288 break;
289 case Te_TyTyDef:
290 if (!ent->Te.TyTyDef.name) goto unhandled;
291 VG_(printf)("%s", ent->Te.TyTyDef.name);
292 break;
293 case Te_TyFn:
294 VG_(printf)("%s", "<function_type>");
295 break;
296 case Te_TyQual:
297 switch (ent->Te.TyQual.qual) {
298 case 'C': VG_(printf)("const "); break;
299 case 'V': VG_(printf)("volatile "); 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) ( 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) ( TyEnt* te1, 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(XArray * a,XArray * b)450 static Word XArray_of_UWord__cmp ( XArray* a, 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(UChar * a,UChar * b,Word n)463 static Word Bytevector__cmp ( UChar* a, 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(UChar * a,UChar * b)472 static Word Asciiz__cmp ( UChar* a, UChar* 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) ( TyEnt* te1, 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 if (te->Te.TyStOrUn.fieldRs) 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)( 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 UChar */ xa,
740 UWord uw ) {
741 UChar buf[32];
742 VG_(memset)(buf, 0, sizeof(buf));
743 VG_(sprintf)(buf, "%lu", uw);
744 VG_(addBytesToXA)( xa, buf, VG_(strlen)(buf));
745 }
746
ML_(describe_type)747 XArray* /*UChar*/ ML_(describe_type)( /*OUT*/PtrdiffT* residual_offset,
748 XArray* /* of TyEnt */ tyents,
749 UWord ty_cuOff,
750 PtrdiffT offset )
751 {
752 TyEnt* ty;
753 XArray* xa = VG_(newXA)( ML_(dinfo_zalloc), "di.tytypes.dt.1",
754 ML_(dinfo_free),
755 sizeof(UChar) );
756 vg_assert(xa);
757
758 ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL, ty_cuOff);
759
760 while (True) {
761 vg_assert(ty);
762 vg_assert(ML_(TyEnt__is_type)(ty));
763
764 switch (ty->tag) {
765
766 /* These are all atomic types; there is nothing useful we can
767 do. */
768 case Te_TyEnum:
769 case Te_TyFn:
770 case Te_TyVoid:
771 case Te_TyPtr:
772 case Te_TyRef:
773 case Te_TyPtrMbr:
774 case Te_TyRvalRef:
775 case Te_TyBase:
776 goto done;
777
778 case Te_TyStOrUn: {
779 Word i;
780 GXResult res;
781 MaybeULong mul;
782 XArray* fieldRs;
783 UWord fieldR;
784 TyEnt* field = NULL;
785 PtrdiffT offMin = 0, offMax1 = 0;
786 if (!ty->Te.TyStOrUn.isStruct) goto done;
787 fieldRs = ty->Te.TyStOrUn.fieldRs;
788 if ((!fieldRs) || VG_(sizeXA)(fieldRs) == 0) goto done;
789 for (i = 0; i < VG_(sizeXA)( fieldRs ); i++ ) {
790 fieldR = *(UWord*)VG_(indexXA)( fieldRs, i );
791 field = ML_(TyEnts__index_by_cuOff)(tyents, NULL, fieldR);
792 vg_assert(field);
793 vg_assert(field->tag == Te_Field);
794 vg_assert(field->Te.Field.nLoc < 0
795 || (field->Te.Field.nLoc > 0
796 && field->Te.Field.pos.loc));
797 if (field->Te.Field.nLoc == -1) {
798 res.kind = GXR_Addr;
799 res.word = field->Te.Field.pos.offset;
800 } else {
801 /* Re data_bias in this call, we should really send in
802 a legitimate value. But the expression is expected
803 to be a constant expression, evaluation of which
804 will not need to use DW_OP_addr and hence we can
805 avoid the trouble of plumbing the data bias through
806 to this point (if, indeed, it has any meaning; from
807 which DebugInfo would we take the data bias? */
808 res = ML_(evaluate_Dwarf3_Expr)(
809 field->Te.Field.pos.loc, field->Te.Field.nLoc,
810 NULL/*fbGX*/, NULL/*RegSummary*/,
811 0/*data_bias*/,
812 True/*push_initial_zero*/);
813 if (0) {
814 VG_(printf)("QQQ ");
815 ML_(pp_GXResult)(res);
816 VG_(printf)("\n");
817 }
818 }
819 if (res.kind != GXR_Addr)
820 continue;
821 mul = ML_(sizeOfType)( tyents, field->Te.Field.typeR );
822 if (mul.b != True)
823 goto done; /* size of field is unknown (?!) */
824 offMin = res.word;
825 offMax1 = offMin + (PtrdiffT)mul.ul;
826 if (offMin == offMax1)
827 continue;
828 vg_assert(offMin < offMax1);
829 if (offset >= offMin && offset < offMax1)
830 break;
831 }
832 /* Did we find a suitable field? */
833 vg_assert(i >= 0 && i <= VG_(sizeXA)( fieldRs ));
834 if (i == VG_(sizeXA)( fieldRs ))
835 goto done; /* No. Give up. */
836 /* Yes. 'field' is it. */
837 vg_assert(field);
838 if (!field->Te.Field.name) goto done;
839 VG_(addBytesToXA)( xa, ".", 1 );
840 VG_(addBytesToXA)( xa, field->Te.Field.name,
841 VG_(strlen)(field->Te.Field.name) );
842 offset -= offMin;
843 ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
844 field->Te.Field.typeR );
845 tl_assert(ty);
846 if (ty->tag == Te_UNKNOWN) goto done;
847 /* keep going; look inside the field. */
848 break;
849 }
850
851 case Te_TyArray: {
852 MaybeULong mul;
853 UWord size, eszB, ix;
854 UWord boundR;
855 TyEnt* elemTy;
856 TyEnt* bound;
857 /* Just deal with the simple, common C-case: 1-D array,
858 zero based, known size. */
859 elemTy = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
860 ty->Te.TyArray.typeR);
861 vg_assert(elemTy);
862 if (elemTy->tag == Te_UNKNOWN) goto done;
863 vg_assert(ML_(TyEnt__is_type)(elemTy));
864 if (!ty->Te.TyArray.boundRs)
865 goto done;
866 if (VG_(sizeXA)( ty->Te.TyArray.boundRs ) != 1) goto done;
867 boundR = *(UWord*)VG_(indexXA)( ty->Te.TyArray.boundRs, 0 );
868 bound = ML_(TyEnts__index_by_cuOff)(tyents, NULL, boundR);
869 vg_assert(bound);
870 vg_assert(bound->tag == Te_Bound);
871 if (!(bound->Te.Bound.knownL && bound->Te.Bound.knownU
872 && bound->Te.Bound.boundL == 0
873 && bound->Te.Bound.boundU >= bound->Te.Bound.boundL))
874 goto done;
875 size = bound->Te.Bound.boundU - bound->Te.Bound.boundL + 1;
876 vg_assert(size >= 1);
877 mul = ML_(sizeOfType)( tyents, ty->Te.TyArray.typeR );
878 if (mul.b != True)
879 goto done; /* size of element type not known */
880 eszB = mul.ul;
881 if (eszB == 0) goto done;
882 ix = offset / eszB;
883 VG_(addBytesToXA)( xa, "[", 1 );
884 copy_UWord_into_XA( xa, ix );
885 VG_(addBytesToXA)( xa, "]", 1 );
886 ty = elemTy;
887 offset -= ix * eszB;
888 /* keep going; look inside the array element. */
889 break;
890 }
891
892 case Te_TyQual: {
893 ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
894 ty->Te.TyQual.typeR);
895 tl_assert(ty);
896 if (ty->tag == Te_UNKNOWN) goto done;
897 break;
898 }
899
900 case Te_TyTyDef: {
901 ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
902 ty->Te.TyTyDef.typeR);
903 tl_assert(ty);
904 if (ty->tag == Te_UNKNOWN) goto done;
905 break;
906 }
907
908 default: {
909 VG_(printf)("ML_(describe_type): unhandled: ");
910 ML_(pp_TyEnt)(ty);
911 VG_(printf)("\n");
912 vg_assert(0);
913 }
914
915 }
916 }
917
918 done:
919 *residual_offset = offset;
920 VG_(addBytesToXA)( xa, "\0", 1 );
921 return xa;
922 }
923
924 /*--------------------------------------------------------------------*/
925 /*--- end tytypes.c ---*/
926 /*--------------------------------------------------------------------*/
927