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