1 /* $OpenBSD: parse.c,v 1.20 2024/02/22 13:17:18 claudio Exp $ */
2
3 /*
4 * Copyright (c) 2016-2017 Martin Pieuchot
5 * Copyright (c) 2016 Jasper Lievisse Adriaanse <jasper@openbsd.org>
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 */
19
20 /*
21 * DWARF to IT (internal type) representation parser.
22 */
23
24 #include <sys/queue.h>
25 #include <sys/tree.h>
26 #include <sys/types.h>
27 #include <sys/ctf.h>
28
29 #include <assert.h>
30 #include <limits.h>
31 #include <err.h>
32 #include <stdlib.h>
33 #include <string.h>
34
35 #include "itype.h"
36 #include "xmalloc.h"
37 #include "dwarf.h"
38 #include "dw.h"
39 #include "pool.h"
40
41 #ifdef DEBUG
42 #include <stdio.h>
43 #endif
44
45 #ifndef NOPOOL
46 struct pool it_pool, im_pool, ir_pool;
47 #endif /* NOPOOL */
48
49 #ifndef nitems
50 #define nitems(_a) (sizeof((_a)) / sizeof((_a)[0]))
51 #endif
52
53 #ifdef DEBUG
54 #define DPRINTF(x...) do { printf(x); } while (0)
55 #else
56 #define DPRINTF(x...) do { ; } while (0)
57 #endif
58
59 #define VOID_OFFSET 1 /* Fake offset for generating "void" type. */
60
61 /*
62 * Tree used to resolve per-CU types based on their offset in
63 * the abbrev section.
64 */
65 RB_HEAD(ioff_tree, itype);
66
67 /*
68 * Per-type trees used to merge existing types with the ones of
69 * a newly parsed CU.
70 */
71 RB_HEAD(itype_tree, itype) itypet[CTF_K_MAX];
72
73 /*
74 * Tree of symbols used to build a list matching the order of
75 * the ELF symbol table.
76 */
77 struct isymb_tree isymbt;
78
79 struct itype *void_it; /* no type is emited for void */
80 uint16_t tidx, fidx, oidx; /* type, func & object IDs */
81 uint16_t long_tidx; /* index of "long", for array */
82
83
84 void cu_stat(void);
85 void cu_parse(struct dwcu *, struct itype_queue *,
86 struct ioff_tree *);
87 void cu_resolve(struct dwcu *, struct itype_queue *,
88 struct ioff_tree *);
89 void cu_reference(struct dwcu *, struct itype_queue *);
90 void cu_merge(struct dwcu *, struct itype_queue *);
91
92 struct itype *parse_base(struct dwdie *, size_t);
93 struct itype *parse_refers(struct dwdie *, size_t, int);
94 struct itype *parse_array(struct dwdie *, size_t);
95 struct itype *parse_enum(struct dwdie *, size_t);
96 struct itype *parse_struct(struct dwdie *, size_t, int, size_t);
97 struct itype *parse_function(struct dwdie *, size_t);
98 struct itype *parse_funcptr(struct dwdie *, size_t);
99 struct itype *parse_variable(struct dwdie *, size_t);
100
101 void subparse_subrange(struct dwdie *, size_t, struct itype *);
102 void subparse_enumerator(struct dwdie *, size_t, struct itype *);
103 void subparse_member(struct dwdie *, size_t, struct itype *, size_t);
104 void subparse_arguments(struct dwdie *, size_t, struct itype *);
105
106 size_t dav2val(struct dwaval *, size_t);
107 const char *dav2str(struct dwaval *);
108 const char *enc2name(unsigned short);
109
110 struct itype *it_new(uint64_t, size_t, const char *, uint32_t, uint16_t,
111 uint64_t, uint16_t, unsigned int);
112 void it_merge(struct itype *, struct itype *);
113 void it_reference(struct itype *);
114 void it_free(struct itype *);
115 int it_cmp(struct itype *, struct itype *);
116 int it_name_cmp(struct itype *, struct itype *);
117 int it_off_cmp(struct itype *, struct itype *);
118 void ir_add(struct itype *, struct itype *);
119 void ir_purge(struct itype *);
120 struct imember *im_new(const char *, size_t, size_t);
121
122 RB_GENERATE(itype_tree, itype, it_node, it_cmp);
123 RB_GENERATE(isymb_tree, itype, it_node, it_name_cmp);
124 RB_GENERATE(ioff_tree, itype, it_node, it_off_cmp);
125
126 /*
127 * Construct a list of internal type and functions based on DWARF
128 * INFO and ABBREV sections.
129 *
130 * Multiple CUs are supported.
131 */
132 void
dwarf_parse(const char * infobuf,size_t infolen,const char * abbuf,size_t ablen)133 dwarf_parse(const char *infobuf, size_t infolen, const char *abbuf,
134 size_t ablen)
135 {
136 struct dwbuf info = { .buf = infobuf, .len = infolen };
137 struct dwbuf abbrev = { .buf = abbuf, .len = ablen };
138 struct dwcu *dcu = NULL;
139 struct ioff_tree cu_iofft;
140 struct itype_queue cu_itypeq;
141 struct itype *it;
142 int i;
143
144 for (i = 0; i < CTF_K_MAX; i++)
145 RB_INIT(&itypet[i]);
146 RB_INIT(&isymbt);
147
148 void_it = it_new(++tidx, VOID_OFFSET, "void", 0,
149 CTF_INT_SIGNED, 0, CTF_K_INTEGER, 0);
150 TAILQ_INSERT_TAIL(&itypeq, void_it, it_next);
151
152 while (dw_cu_parse(&info, &abbrev, infolen, &dcu) == 0) {
153 TAILQ_INIT(&cu_itypeq);
154
155 /* We use a tree to speed-up type resolution. */
156 RB_INIT(&cu_iofft);
157
158 /* Parse this CU */
159 cu_parse(dcu, &cu_itypeq, &cu_iofft);
160
161 /* Resolve its types. */
162 cu_resolve(dcu, &cu_itypeq, &cu_iofft);
163 assert(RB_EMPTY(&cu_iofft));
164
165 /* Mark used type as such. */
166 cu_reference(dcu, &cu_itypeq);
167
168 #ifdef DEBUG
169 /* Dump statistics for current CU. */
170 cu_stat();
171 #endif
172
173 /* Merge them with the common type list. */
174 cu_merge(dcu, &cu_itypeq);
175
176 dw_dcu_free(dcu);
177 }
178
179 /* We force array's index type to be 'long', for that we need its ID. */
180 RB_FOREACH(it, itype_tree, &itypet[CTF_K_INTEGER]) {
181 if (it_name(it) == NULL || it->it_size != (8 * sizeof(long)))
182 continue;
183
184 if (strcmp(it_name(it), "unsigned") == 0) {
185 long_tidx = it->it_idx;
186 break;
187 }
188 }
189 }
190
191 struct itype *
it_new(uint64_t index,size_t off,const char * name,uint32_t size,uint16_t enc,uint64_t ref,uint16_t type,unsigned int flags)192 it_new(uint64_t index, size_t off, const char *name, uint32_t size,
193 uint16_t enc, uint64_t ref, uint16_t type, unsigned int flags)
194 {
195 struct itype *it;
196 #ifndef NOPOOL
197 static int it_pool_inited = 0;
198
199 if (!it_pool_inited) {
200 pool_init(&it_pool, "it", 512, sizeof(struct itype));
201 pool_init(&im_pool, "im", 1024, sizeof(struct imember));
202 pool_init(&ir_pool, "ir", 1024, sizeof(struct itref));
203 it_pool_inited = 1;
204 }
205 #endif
206
207 assert((name != NULL) || !(flags & (ITF_FUNC|ITF_OBJ)));
208
209 it = pmalloc(&it_pool, sizeof(*it));
210 SIMPLEQ_INIT(&it->it_refs);
211 TAILQ_INIT(&it->it_members);
212 it->it_off = off;
213 it->it_ref = ref;
214 it->it_refp = NULL;
215 it->it_size = size;
216 it->it_nelems = 0;
217 it->it_enc = enc;
218 it->it_idx = index;
219 it->it_type = type;
220 it->it_flags = flags;
221
222 if (name == NULL) {
223 it->it_flags |= ITF_ANON;
224 } else {
225 size_t n;
226
227 if ((n = strlcpy(it->it_name, name, ITNAME_MAX)) > ITNAME_MAX)
228 warnx("name %s too long %zd > %d", name, n, ITNAME_MAX);
229 }
230
231 return it;
232 }
233
234 struct itype *
it_dup(struct itype * it)235 it_dup(struct itype *it)
236 {
237 struct imember *copim, *im;
238 struct itype *copit;
239
240 copit = it_new(it->it_idx, it->it_off, it_name(it), it->it_size,
241 it->it_enc, it->it_ref, it->it_type, it->it_flags);
242
243 copit->it_refp = it->it_refp;
244 copit->it_nelems = it->it_nelems;
245
246 TAILQ_FOREACH(im, &it->it_members, im_next) {
247 copim = im_new(im_name(im), im->im_ref, im->im_off);
248 copim->im_refp = im->im_refp;
249 TAILQ_INSERT_TAIL(&copit->it_members, copim, im_next);
250 }
251
252 return copit;
253 }
254
255 /*
256 * Merge the content of ``it'', the full type declaration into the
257 * forwarding representation ``fwd''.
258 */
259 void
it_merge(struct itype * fwd,struct itype * it)260 it_merge(struct itype *fwd, struct itype *it)
261 {
262 assert(fwd->it_flags & ITF_FORWARD);
263 assert(fwd->it_type == it->it_type);
264 assert(TAILQ_EMPTY(&fwd->it_members));
265 assert(SIMPLEQ_EMPTY(&it->it_refs));
266
267 fwd->it_off = it->it_off;
268 fwd->it_ref = it->it_ref;
269 fwd->it_refp = it->it_refp;
270 fwd->it_size = it->it_size;
271 fwd->it_nelems = it->it_nelems;
272 fwd->it_enc = it->it_enc;
273 fwd->it_flags = it->it_flags;
274
275 TAILQ_CONCAT(&fwd->it_members, &it->it_members, im_next);
276 assert(TAILQ_EMPTY(&it->it_members));
277 }
278
279 const char *
it_name(struct itype * it)280 it_name(struct itype *it)
281 {
282 if (!(it->it_flags & ITF_ANON))
283 return it->it_name;
284
285 return NULL;
286 }
287
288 void
it_reference(struct itype * it)289 it_reference(struct itype *it)
290 {
291 struct imember *im;
292
293 if (it == NULL || it->it_flags & ITF_USED)
294 return;
295
296 it->it_flags |= ITF_USED;
297
298 it_reference(it->it_refp);
299 TAILQ_FOREACH(im, &it->it_members, im_next)
300 it_reference(im->im_refp);
301 }
302
303 void
it_free(struct itype * it)304 it_free(struct itype *it)
305 {
306 struct imember *im;
307
308 if (it == NULL)
309 return;
310
311 while ((im = TAILQ_FIRST(&it->it_members)) != NULL) {
312 TAILQ_REMOVE(&it->it_members, im, im_next);
313 pfree(&im_pool, im);
314 }
315
316 ir_purge(it);
317 pfree(&it_pool, it);
318 }
319
320 /*
321 * Return 0 if ``a'' matches ``b''.
322 */
323 int
it_cmp(struct itype * a,struct itype * b)324 it_cmp(struct itype *a, struct itype *b)
325 {
326 if (a->it_type > b->it_type)
327 return 1;
328 if (a->it_type < b->it_type)
329 return -1;
330
331 /* Basic types need to have the same encoding and size. */
332 if ((a->it_type == CTF_K_INTEGER || a->it_type == CTF_K_FLOAT)) {
333 if (a->it_enc > b->it_enc)
334 return 1;
335 if (a->it_enc < b->it_enc)
336 return -1;
337 if (a->it_size > b->it_size)
338 return 1;
339 if (a->it_size < b->it_size)
340 return -1;
341 }
342
343 /* Arrays need to have same number of elements */
344 if (a->it_type == CTF_K_ARRAY) {
345 if (a->it_nelems > b->it_nelems)
346 return 1;
347 if (a->it_nelems < b->it_nelems)
348 return -1;
349 }
350
351 /* Match by name */
352 if (!(a->it_flags & ITF_ANON) && !(b->it_flags & ITF_ANON))
353 return strcmp(it_name(a), it_name(b));
354
355 /* Only one of them is anonym */
356 if ((a->it_flags & ITF_ANON) != (b->it_flags & ITF_ANON))
357 return (a->it_flags & ITF_ANON) ? -1 : 1;
358
359 /* Match by reference */
360 if ((a->it_refp != NULL) && (b->it_refp != NULL))
361 return it_cmp(a->it_refp, b->it_refp);
362 if (a->it_refp == NULL)
363 return -1;
364 if (b->it_refp == NULL)
365 return 1;
366
367 return 0;
368 }
369
370 int
it_name_cmp(struct itype * a,struct itype * b)371 it_name_cmp(struct itype *a, struct itype *b)
372 {
373 int diff;
374
375 if ((diff = strcmp(it_name(a), it_name(b))) != 0)
376 return diff;
377
378 return ((a->it_flags|ITF_MASK) - (b->it_flags|ITF_MASK));
379 }
380
381 int
it_off_cmp(struct itype * a,struct itype * b)382 it_off_cmp(struct itype *a, struct itype *b)
383 {
384 return a->it_off - b->it_off;
385 }
386
387 void
ir_add(struct itype * it,struct itype * tmp)388 ir_add(struct itype *it, struct itype *tmp)
389 {
390 struct itref *ir;
391
392 SIMPLEQ_FOREACH(ir, &tmp->it_refs, ir_next) {
393 if (ir->ir_itp == it)
394 return;
395 }
396
397 ir = pmalloc(&ir_pool, sizeof(*ir));
398 ir->ir_itp = it;
399 SIMPLEQ_INSERT_TAIL(&tmp->it_refs, ir, ir_next);
400 }
401
402 void
ir_purge(struct itype * it)403 ir_purge(struct itype *it)
404 {
405 struct itref *ir;
406
407 while ((ir = SIMPLEQ_FIRST(&it->it_refs)) != NULL) {
408 SIMPLEQ_REMOVE_HEAD(&it->it_refs, ir_next);
409 pfree(&ir_pool, ir);
410 }
411 }
412
413 struct imember *
im_new(const char * name,size_t ref,size_t off)414 im_new(const char *name, size_t ref, size_t off)
415 {
416 struct imember *im;
417
418 im = pmalloc(&im_pool, sizeof(*im));
419 im->im_ref = ref;
420 im->im_off = off;
421 im->im_refp = NULL;
422 if (name == NULL) {
423 im->im_flags = IMF_ANON;
424 } else {
425 size_t n;
426
427 n = strlcpy(im->im_name, name, ITNAME_MAX);
428 if (n > ITNAME_MAX)
429 warnx("name %s too long %zd > %d", name, n,
430 ITNAME_MAX);
431 im->im_flags = 0;
432 }
433
434 return im;
435 }
436
437 const char *
im_name(struct imember * im)438 im_name(struct imember *im)
439 {
440 if (!(im->im_flags & IMF_ANON))
441 return im->im_name;
442
443 return NULL;
444 }
445
446 void
cu_stat(void)447 cu_stat(void)
448 {
449 #ifndef NOPOOL
450 pool_dump();
451 #endif
452 }
453
454 /*
455 * Iterate over all types found in a given CU. For all non-resolved types
456 * use their DWARF relative offset to find the relative type they are pointing
457 * to. The CU offset tree, `cuot', is used to speedup relative type lookup.
458 */
459 void
cu_resolve(struct dwcu * dcu,struct itype_queue * cutq,struct ioff_tree * cuot)460 cu_resolve(struct dwcu *dcu, struct itype_queue *cutq, struct ioff_tree *cuot)
461 {
462 struct itype *it, *ref, tmp;
463 struct imember *im;
464 unsigned int toresolve;
465 size_t off = dcu->dcu_offset;
466
467 TAILQ_FOREACH(it, cutq, it_next) {
468 if (!(it->it_flags & (ITF_UNRES|ITF_UNRES_MEMB)))
469 continue;
470
471 /* If this type references another one, try to find it. */
472 if (it->it_flags & ITF_UNRES) {
473 tmp.it_off = it->it_ref + off;
474 ref = RB_FIND(ioff_tree, cuot, &tmp);
475 if (ref != NULL) {
476 it->it_refp = ref;
477 ir_add(it, ref);
478 it->it_flags &= ~ITF_UNRES;
479 }
480 }
481
482 /* If this type has members, resolve all of them. */
483 toresolve = it->it_nelems;
484 if ((it->it_flags & ITF_UNRES_MEMB) && toresolve > 0) {
485 TAILQ_FOREACH(im, &it->it_members, im_next) {
486 tmp.it_off = im->im_ref + off;
487 ref = RB_FIND(ioff_tree, cuot, &tmp);
488 if (ref != NULL) {
489 im->im_refp = ref;
490 ir_add(it, ref);
491 toresolve--;
492 }
493 }
494 if (toresolve == 0)
495 it->it_flags &= ~ITF_UNRES_MEMB;
496 }
497 #if defined(DEBUG)
498 if (it->it_flags & (ITF_UNRES|ITF_UNRES_MEMB)) {
499 printf("0x%zx: %s type=%d unresolved 0x%llx",
500 it->it_off, it_name(it), it->it_type, it->it_ref);
501 if (toresolve)
502 printf(": %d members", toresolve);
503 TAILQ_FOREACH(im, &it->it_members, im_next) {
504 if (im->im_refp != NULL)
505 continue;
506 printf("\n%zu: %s", im->im_ref, im_name(im));
507 }
508 printf("\n");
509 }
510 #endif /* defined(DEBUG) */
511 }
512
513 /* We'll reuse the tree for the next CU, so empty it. */
514 RB_FOREACH_SAFE(it, ioff_tree, cuot, ref)
515 RB_REMOVE(ioff_tree, cuot, it);
516 }
517
518 void
cu_reference(struct dwcu * dcu,struct itype_queue * cutq)519 cu_reference(struct dwcu *dcu, struct itype_queue *cutq)
520 {
521 struct itype *it;
522
523 TAILQ_FOREACH(it, cutq, it_next) {
524 if (it->it_flags & (ITF_OBJ|ITF_FUNC))
525 it_reference(it);
526 }
527 }
528
529 /*
530 * Merge type representation from a CU with already known types.
531 */
532 void
cu_merge(struct dwcu * dcu,struct itype_queue * cutq)533 cu_merge(struct dwcu *dcu, struct itype_queue *cutq)
534 {
535 struct itype *it, *nit, *prev, *first;
536 int diff;
537
538 /* First ``it'' that needs a duplicate check. */
539 first = TAILQ_FIRST(cutq);
540 if (first == NULL)
541 return;
542
543 TAILQ_CONCAT(&itypeq, cutq, it_next);
544
545 /*
546 * First pass: merge types
547 */
548 for (it = first; it != NULL; it = nit) {
549 nit = TAILQ_NEXT(it, it_next);
550
551 /* Move functions & variable to their own list. */
552 if (it->it_flags & (ITF_FUNC|ITF_OBJ)) {
553 /*
554 * FIXME: allow static variables with the same name
555 * to be of different type.
556 */
557 if (RB_FIND(isymb_tree, &isymbt, it) == NULL)
558 RB_INSERT(isymb_tree, &isymbt, it);
559 continue;
560 }
561
562 /* Look if we already have this type. */
563 if (it->it_flags & ITF_USED)
564 prev = RB_FIND(itype_tree, &itypet[it->it_type], it);
565 else
566 prev = NULL;
567
568 if (prev != NULL) {
569 struct itype *old = it;
570 struct itref *ir;
571 struct imember *im;
572
573 /* Substitute references */
574 while ((ir = SIMPLEQ_FIRST(&old->it_refs)) != NULL) {
575 it = ir->ir_itp;
576
577 SIMPLEQ_REMOVE_HEAD(&old->it_refs, ir_next);
578 pfree(&ir_pool, ir);
579
580 if (it->it_refp == old)
581 it->it_refp = prev;
582
583 TAILQ_FOREACH(im, &it->it_members, im_next) {
584 if (im->im_refp == old)
585 im->im_refp = prev;
586 }
587 }
588
589 /* If we first got a forward reference, complete it. */
590 if ((prev->it_flags & ITF_FORWARD) &&
591 (old->it_flags & ITF_FORWARD) == 0)
592 it_merge(prev, old);
593
594 old->it_flags &= ~ITF_USED;
595 } else if (it->it_flags & ITF_USED) {
596 RB_INSERT(itype_tree, &itypet[it->it_type], it);
597 }
598 }
599
600 /*
601 * Second pass: update indexes
602 */
603 diff = 0;
604 for (it = first; it != NULL; it = nit) {
605 nit = TAILQ_NEXT(it, it_next);
606
607 if (it->it_flags & (ITF_FUNC|ITF_OBJ))
608 continue;
609
610 /* Adjust indexes */
611 if (it->it_flags & ITF_USED) {
612 it->it_idx -= diff;
613 continue;
614 }
615
616 /* Remove unused */
617 TAILQ_REMOVE(&itypeq, it, it_next);
618 it_free(it);
619 diff++;
620 }
621
622 /* Update global index to match removed entries. */
623 it = TAILQ_LAST(&itypeq, itype_queue);
624 while (it->it_flags & (ITF_FUNC|ITF_OBJ))
625 it = TAILQ_PREV(it, itype_queue, it_next);
626
627 tidx = it->it_idx;
628 }
629
630 /*
631 * Parse a CU.
632 */
633 void
cu_parse(struct dwcu * dcu,struct itype_queue * cutq,struct ioff_tree * cuot)634 cu_parse(struct dwcu *dcu, struct itype_queue *cutq, struct ioff_tree *cuot)
635 {
636 struct itype *it = NULL;
637 struct dwdie *die;
638 size_t psz = dcu->dcu_psize;
639 size_t off = dcu->dcu_offset;
640
641 assert(RB_EMPTY(cuot));
642
643 SIMPLEQ_FOREACH(die, &dcu->dcu_dies, die_next) {
644 uint64_t tag = die->die_dab->dab_tag;
645
646 switch (tag) {
647 case DW_TAG_array_type:
648 it = parse_array(die, dcu->dcu_psize);
649 break;
650 case DW_TAG_enumeration_type:
651 it = parse_enum(die, dcu->dcu_psize);
652 break;
653 case DW_TAG_pointer_type:
654 it = parse_refers(die, psz, CTF_K_POINTER);
655 break;
656 case DW_TAG_structure_type:
657 it = parse_struct(die, psz, CTF_K_STRUCT, off);
658 if (it == NULL)
659 continue;
660 break;
661 case DW_TAG_typedef:
662 it = parse_refers(die, psz, CTF_K_TYPEDEF);
663 break;
664 case DW_TAG_union_type:
665 it = parse_struct(die, psz, CTF_K_UNION, off);
666 if (it == NULL)
667 continue;
668 break;
669 case DW_TAG_base_type:
670 it = parse_base(die, psz);
671 if (it == NULL)
672 continue;
673 break;
674 case DW_TAG_const_type:
675 it = parse_refers(die, psz, CTF_K_CONST);
676 break;
677 case DW_TAG_volatile_type:
678 it = parse_refers(die, psz, CTF_K_VOLATILE);
679 break;
680 case DW_TAG_restrict_type:
681 it = parse_refers(die, psz, CTF_K_RESTRICT);
682 break;
683 case DW_TAG_subprogram:
684 it = parse_function(die, psz);
685 if (it == NULL)
686 continue;
687 break;
688 case DW_TAG_subroutine_type:
689 it = parse_funcptr(die, psz);
690 break;
691 /*
692 * Children are assumed to be right after their parent in
693 * the list. The parent parsing function takes care of
694 * parsing them.
695 */
696 case DW_TAG_member:
697 assert(it->it_type == CTF_K_STRUCT ||
698 it->it_type == CTF_K_UNION ||
699 it->it_type == CTF_K_ENUM);
700 continue;
701 case DW_TAG_subrange_type:
702 assert(it->it_type == CTF_K_ARRAY);
703 continue;
704 case DW_TAG_formal_parameter:
705 /*
706 * If we skipped the second inline definition,
707 * skip its arguments.
708 */
709 if (it == NULL)
710 continue;
711
712 /* See comment in subparse_arguments(). */
713 if (it->it_type == CTF_K_STRUCT ||
714 it->it_type == CTF_K_UNION ||
715 it->it_type == CTF_K_ENUM ||
716 it->it_type == CTF_K_TYPEDEF)
717 continue;
718
719 if (it->it_flags & ITF_OBJ)
720 continue;
721
722 assert(it->it_type == CTF_K_FUNCTION);
723 continue;
724 case DW_TAG_variable:
725 it = parse_variable(die, psz);
726 /* Unnamed variables are discarded. */
727 if (it == NULL)
728 continue;
729 break;
730 #if 1
731 case DW_TAG_lexical_block:
732 case DW_TAG_inlined_subroutine:
733 continue;
734 #endif
735 case DW_TAG_compile_unit:
736 default:
737 DPRINTF("%s\n", dw_tag2name(tag));
738 continue;
739 }
740
741 TAILQ_INSERT_TAIL(cutq, it, it_next);
742 RB_INSERT(ioff_tree, cuot, it);
743 }
744 }
745
746 struct itype *
parse_base(struct dwdie * die,size_t psz)747 parse_base(struct dwdie *die, size_t psz)
748 {
749 struct itype *it;
750 struct dwaval *dav;
751 uint16_t encoding, enc = 0, bits = 0;
752 int type;
753
754 SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
755 switch (dav->dav_dat->dat_attr) {
756 case DW_AT_encoding:
757 enc = dav2val(dav, psz);
758 break;
759 case DW_AT_byte_size:
760 bits = 8 * dav2val(dav, psz);
761 break;
762 default:
763 DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
764 break;
765 }
766 }
767
768 switch (enc) {
769 case DW_ATE_unsigned:
770 case DW_ATE_address:
771 encoding = 0;
772 type = CTF_K_INTEGER;
773 break;
774 case DW_ATE_unsigned_char:
775 encoding = CTF_INT_CHAR;
776 type = CTF_K_INTEGER;
777 break;
778 case DW_ATE_signed:
779 encoding = CTF_INT_SIGNED;
780 type = CTF_K_INTEGER;
781 break;
782 case DW_ATE_signed_char:
783 encoding = CTF_INT_SIGNED | CTF_INT_CHAR;
784 type = CTF_K_INTEGER;
785 break;
786 case DW_ATE_boolean:
787 encoding = CTF_INT_SIGNED | CTF_INT_BOOL;
788 type = CTF_K_INTEGER;
789 break;
790 case DW_ATE_float:
791 if (bits < psz)
792 encoding = CTF_FP_SINGLE;
793 else if (bits == psz)
794 encoding = CTF_FP_DOUBLE;
795 else
796 encoding = CTF_FP_LDOUBLE;
797 type = CTF_K_FLOAT;
798 break;
799 case DW_ATE_complex_float:
800 if (bits < psz)
801 encoding = CTF_FP_CPLX;
802 else if (bits == psz)
803 encoding = CTF_FP_DCPLX;
804 else
805 encoding = CTF_FP_LDCPLX;
806 type = CTF_K_FLOAT;
807 break;
808 case DW_ATE_imaginary_float:
809 if (bits < psz)
810 encoding = CTF_FP_IMAGRY;
811 else if (bits == psz)
812 encoding = CTF_FP_DIMAGRY;
813 else
814 encoding = CTF_FP_LDIMAGRY;
815 type = CTF_K_FLOAT;
816 break;
817 default:
818 DPRINTF("unknown encoding: %d\n", enc);
819 return (NULL);
820 }
821
822 it = it_new(++tidx, die->die_offset, enc2name(enc), bits,
823 encoding, 0, type, 0);
824
825 return it;
826 }
827
828 struct itype *
parse_refers(struct dwdie * die,size_t psz,int type)829 parse_refers(struct dwdie *die, size_t psz, int type)
830 {
831 struct itype *it;
832 struct dwaval *dav;
833 const char *name = NULL;
834 size_t ref = 0, size = 0;
835
836 SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
837 switch (dav->dav_dat->dat_attr) {
838 case DW_AT_name:
839 name = dav2str(dav);
840 break;
841 case DW_AT_type:
842 ref = dav2val(dav, psz);
843 break;
844 case DW_AT_byte_size:
845 size = dav2val(dav, psz);
846 assert(size < UINT_MAX);
847 break;
848 default:
849 DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
850 break;
851 }
852 }
853
854 it = it_new(++tidx, die->die_offset, name, size, 0, ref, type,
855 ITF_UNRES);
856
857 if (it->it_ref == 0 && (it->it_size == sizeof(void *) ||
858 type == CTF_K_CONST || type == CTF_K_VOLATILE ||
859 type == CTF_K_POINTER || type == CTF_K_TYPEDEF)) {
860 /* Work around GCC/clang not emiting a type for void */
861 it->it_flags &= ~ITF_UNRES;
862 it->it_ref = VOID_OFFSET;
863 it->it_refp = void_it;
864 }
865
866 return it;
867 }
868
869 struct itype *
parse_array(struct dwdie * die,size_t psz)870 parse_array(struct dwdie *die, size_t psz)
871 {
872 struct itype *it;
873 struct dwaval *dav;
874 const char *name = NULL;
875 size_t ref = 0;
876
877 SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
878 switch (dav->dav_dat->dat_attr) {
879 case DW_AT_name:
880 name = dav2str(dav);
881 break;
882 case DW_AT_type:
883 ref = dav2val(dav, psz);
884 break;
885 default:
886 DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
887 break;
888 }
889 }
890
891 it = it_new(++tidx, die->die_offset, name, 0, 0, ref, CTF_K_ARRAY,
892 ITF_UNRES);
893
894 subparse_subrange(die, psz, it);
895
896 return it;
897 }
898
899 struct itype *
parse_enum(struct dwdie * die,size_t psz)900 parse_enum(struct dwdie *die, size_t psz)
901 {
902 struct itype *it;
903 struct dwaval *dav;
904 const char *name = NULL;
905 size_t size = 0;
906
907 SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
908 switch (dav->dav_dat->dat_attr) {
909 case DW_AT_byte_size:
910 size = dav2val(dav, psz);
911 assert(size < UINT_MAX);
912 break;
913 case DW_AT_name:
914 name = dav2str(dav);
915 break;
916 default:
917 DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
918 break;
919 }
920 }
921
922 it = it_new(++tidx, die->die_offset, name, size, 0, 0, CTF_K_ENUM, 0);
923
924 subparse_enumerator(die, psz, it);
925
926 return it;
927 }
928
929 void
subparse_subrange(struct dwdie * die,size_t psz,struct itype * it)930 subparse_subrange(struct dwdie *die, size_t psz, struct itype *it)
931 {
932 struct dwaval *dav;
933
934 assert(it->it_type == CTF_K_ARRAY);
935
936 if (die->die_dab->dab_children == DW_CHILDREN_no)
937 return;
938
939 /*
940 * This loop assumes that the children of a DIE are just
941 * after it on the list.
942 */
943 while ((die = SIMPLEQ_NEXT(die, die_next)) != NULL) {
944 uint64_t tag = die->die_dab->dab_tag;
945 size_t nelems = 0;
946
947 if (tag != DW_TAG_subrange_type)
948 break;
949
950 SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
951 switch (dav->dav_dat->dat_attr) {
952 case DW_AT_count:
953 nelems = dav2val(dav, psz);
954 break;
955 case DW_AT_upper_bound:
956 nelems = dav2val(dav, psz) + 1;
957 break;
958 default:
959 DPRINTF("%s\n",
960 dw_at2name(dav->dav_dat->dat_attr));
961 break;
962 }
963 }
964
965 assert(nelems < UINT_MAX);
966 it->it_nelems = nelems;
967 }
968 }
969
970 void
subparse_enumerator(struct dwdie * die,size_t psz,struct itype * it)971 subparse_enumerator(struct dwdie *die, size_t psz, struct itype *it)
972 {
973 struct imember *im;
974 struct dwaval *dav;
975
976 assert(it->it_type == CTF_K_ENUM);
977
978 if (die->die_dab->dab_children == DW_CHILDREN_no)
979 return;
980
981 /*
982 * This loop assumes that the children of a DIE are just
983 * after it on the list.
984 */
985 while ((die = SIMPLEQ_NEXT(die, die_next)) != NULL) {
986 uint64_t tag = die->die_dab->dab_tag;
987 size_t val = 0;
988 const char *name = NULL;
989
990 if (tag != DW_TAG_enumerator)
991 break;
992
993 SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
994 switch (dav->dav_dat->dat_attr) {
995 case DW_AT_name:
996 name = dav2str(dav);
997 break;
998 case DW_AT_const_value:
999 val = dav2val(dav, psz);
1000 break;
1001 default:
1002 DPRINTF("%s\n",
1003 dw_at2name(dav->dav_dat->dat_attr));
1004 break;
1005 }
1006 }
1007
1008 if (name == NULL) {
1009 warnx("%s with anon member", it_name(it));
1010 continue;
1011 }
1012
1013 im = im_new(name, val, 0);
1014 assert(it->it_nelems < UINT_MAX);
1015 it->it_nelems++;
1016 TAILQ_INSERT_TAIL(&it->it_members, im, im_next);
1017 }
1018 }
1019
1020 struct itype *
parse_struct(struct dwdie * die,size_t psz,int type,size_t off)1021 parse_struct(struct dwdie *die, size_t psz, int type, size_t off)
1022 {
1023 struct itype *it = NULL;
1024 struct dwaval *dav;
1025 const char *name = NULL;
1026 unsigned int flags = 0;
1027 size_t size = 0;
1028 int forward = 0;
1029
1030 SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
1031 switch (dav->dav_dat->dat_attr) {
1032 case DW_AT_declaration:
1033 forward = dav2val(dav, psz);
1034 break;
1035 case DW_AT_byte_size:
1036 size = dav2val(dav, psz);
1037 assert(size < UINT_MAX);
1038 break;
1039 case DW_AT_name:
1040 name = dav2str(dav);
1041 break;
1042 default:
1043 DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
1044 break;
1045 }
1046 }
1047
1048
1049 if (forward)
1050 flags = ITF_FORWARD;
1051 it = it_new(++tidx, die->die_offset, name, size, 0, 0, type, flags);
1052 subparse_member(die, psz, it, off);
1053
1054 return it;
1055 }
1056
1057 void
subparse_member(struct dwdie * die,size_t psz,struct itype * it,size_t offset)1058 subparse_member(struct dwdie *die, size_t psz, struct itype *it, size_t offset)
1059 {
1060 struct imember *im;
1061 struct dwaval *dav;
1062 const char *name;
1063 size_t off = 0, ref = 0, bits = 0;
1064 uint8_t lvl = die->die_lvl;
1065
1066 assert(it->it_type == CTF_K_STRUCT || it->it_type == CTF_K_UNION);
1067
1068 if (die->die_dab->dab_children == DW_CHILDREN_no)
1069 return;
1070
1071 /*
1072 * This loop assumes that the children of a DIE are just
1073 * after it on the list.
1074 */
1075 while ((die = SIMPLEQ_NEXT(die, die_next)) != NULL) {
1076 int64_t tag = die->die_dab->dab_tag;
1077
1078 name = NULL;
1079 if (die->die_lvl <= lvl)
1080 break;
1081
1082 /* Skip members of members */
1083 if (die->die_lvl > lvl + 1)
1084 continue;
1085 /*
1086 * Nested declaration.
1087 *
1088 * This matches the case where a ``struct'', ``union'',
1089 * ``enum'' or ``typedef'' is first declared "inside" a
1090 * union or struct declaration.
1091 */
1092 if (tag == DW_TAG_structure_type || tag == DW_TAG_union_type ||
1093 tag == DW_TAG_enumeration_type || tag == DW_TAG_typedef)
1094 continue;
1095
1096 it->it_flags |= ITF_UNRES_MEMB;
1097
1098 SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
1099 switch (dav->dav_dat->dat_attr) {
1100 case DW_AT_name:
1101 name = dav2str(dav);
1102 break;
1103 case DW_AT_type:
1104 ref = dav2val(dav, psz);
1105 break;
1106 case DW_AT_data_member_location:
1107 off = 8 * dav2val(dav, psz);
1108 break;
1109 case DW_AT_bit_size:
1110 bits = dav2val(dav, psz);
1111 assert(bits < USHRT_MAX);
1112 break;
1113 default:
1114 DPRINTF("%s\n",
1115 dw_at2name(dav->dav_dat->dat_attr));
1116 break;
1117 }
1118 }
1119
1120 /*
1121 * When a structure is declared inside an union, we
1122 * have to generate a reference to make the resolver
1123 * happy.
1124 */
1125 if ((ref == 0) && (tag == DW_TAG_structure_type))
1126 ref = die->die_offset - offset;
1127
1128 im = im_new(name, ref, off);
1129 assert(it->it_nelems < UINT_MAX);
1130 it->it_nelems++;
1131 TAILQ_INSERT_TAIL(&it->it_members, im, im_next);
1132 }
1133 }
1134
1135
1136 void
subparse_arguments(struct dwdie * die,size_t psz,struct itype * it)1137 subparse_arguments(struct dwdie *die, size_t psz, struct itype *it)
1138 {
1139 struct imember *im;
1140 struct dwaval *dav;
1141 size_t ref = 0;
1142
1143 assert(it->it_type == CTF_K_FUNCTION);
1144
1145 if (die->die_dab->dab_children == DW_CHILDREN_no)
1146 return;
1147
1148 /*
1149 * This loop assumes that the children of a DIE are after it
1150 * on the list.
1151 */
1152 while ((die = SIMPLEQ_NEXT(die, die_next)) != NULL) {
1153 uint64_t tag = die->die_dab->dab_tag;
1154
1155 if (tag == DW_TAG_unspecified_parameters) {
1156 /* TODO */
1157 continue;
1158 }
1159
1160 /*
1161 * Nested declaration.
1162 *
1163 * This matches the case where a ``struct'', ``union'',
1164 * ``enum'', ``typedef'' or ``static'' variable is first
1165 * declared inside a function declaration.
1166 */
1167 switch (tag) {
1168 case DW_TAG_structure_type:
1169 case DW_TAG_union_type:
1170 case DW_TAG_enumeration_type:
1171 case DW_TAG_typedef:
1172 case DW_TAG_variable:
1173 continue;
1174 default:
1175 break;
1176 }
1177
1178 if (tag != DW_TAG_formal_parameter)
1179 break;
1180
1181 it->it_flags |= ITF_UNRES_MEMB;
1182
1183 SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
1184 switch (dav->dav_dat->dat_attr) {
1185 case DW_AT_type:
1186 ref = dav2val(dav, psz);
1187 break;
1188 default:
1189 DPRINTF("%s\n",
1190 dw_at2name(dav->dav_dat->dat_attr));
1191 break;
1192 }
1193 }
1194
1195 im = im_new(NULL, ref, 0);
1196 assert(it->it_nelems < UINT_MAX);
1197 it->it_nelems++;
1198 TAILQ_INSERT_TAIL(&it->it_members, im, im_next);
1199 }
1200 }
1201
1202 struct itype *
parse_function(struct dwdie * die,size_t psz)1203 parse_function(struct dwdie *die, size_t psz)
1204 {
1205 struct itype *it;
1206 struct dwaval *dav;
1207 const char *name = NULL;
1208 size_t ref = 0;
1209
1210 SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
1211 switch (dav->dav_dat->dat_attr) {
1212 case DW_AT_name:
1213 name = dav2str(dav);
1214 break;
1215 case DW_AT_type:
1216 ref = dav2val(dav, psz);
1217 break;
1218 case DW_AT_abstract_origin:
1219 /*
1220 * Skip second empty definition for inline
1221 * functions.
1222 */
1223 return NULL;
1224 default:
1225 DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
1226 break;
1227 }
1228 }
1229
1230 /*
1231 * Work around for clang 4.0 generating DW_TAG_subprogram without
1232 * any attribute.
1233 */
1234 if (name == NULL)
1235 return NULL;
1236
1237 it = it_new(++fidx, die->die_offset, name, 0, 0, ref, CTF_K_FUNCTION,
1238 ITF_UNRES|ITF_FUNC);
1239
1240 subparse_arguments(die, psz, it);
1241
1242 if (it->it_ref == 0) {
1243 /* Work around GCC not emiting a type for void */
1244 it->it_flags &= ~ITF_UNRES;
1245 it->it_ref = VOID_OFFSET;
1246 it->it_refp = void_it;
1247 }
1248
1249 return it;
1250 }
1251
1252 struct itype *
parse_funcptr(struct dwdie * die,size_t psz)1253 parse_funcptr(struct dwdie *die, size_t psz)
1254 {
1255 struct itype *it;
1256 struct dwaval *dav;
1257 const char *name = NULL;
1258 size_t ref = 0;
1259
1260 SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
1261 switch (dav->dav_dat->dat_attr) {
1262 case DW_AT_name:
1263 name = dav2str(dav);
1264 break;
1265 case DW_AT_type:
1266 ref = dav2val(dav, psz);
1267 break;
1268 default:
1269 DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
1270 break;
1271 }
1272 }
1273
1274 it = it_new(++tidx, die->die_offset, name, 0, 0, ref, CTF_K_FUNCTION,
1275 ITF_UNRES);
1276
1277 subparse_arguments(die, psz, it);
1278
1279 if (it->it_ref == 0) {
1280 /* Work around GCC not emiting a type for void */
1281 it->it_flags &= ~ITF_UNRES;
1282 it->it_ref = VOID_OFFSET;
1283 it->it_refp = void_it;
1284 }
1285
1286 return it;
1287 }
1288
1289 struct itype *
parse_variable(struct dwdie * die,size_t psz)1290 parse_variable(struct dwdie *die, size_t psz)
1291 {
1292 struct itype *it = NULL;
1293 struct dwaval *dav;
1294 const char *name = NULL;
1295 size_t ref = 0;
1296 int forward = 0, global = 0;
1297
1298 SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next) {
1299 switch (dav->dav_dat->dat_attr) {
1300 case DW_AT_declaration:
1301 forward = dav2val(dav, psz);
1302 break;
1303 case DW_AT_name:
1304 name = dav2str(dav);
1305 break;
1306 case DW_AT_type:
1307 ref = dav2val(dav, psz);
1308 break;
1309 case DW_AT_location:
1310 switch (dav->dav_dat->dat_form) {
1311 case DW_FORM_block:
1312 case DW_FORM_block1:
1313 case DW_FORM_block2:
1314 case DW_FORM_block4:
1315 global = 1;
1316 break;
1317 default:
1318 break;
1319 }
1320 break;
1321 default:
1322 DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr));
1323 break;
1324 }
1325 }
1326
1327
1328 if (global && !forward && name != NULL) {
1329 it = it_new(++oidx, die->die_offset, name, 0, 0, ref, 0,
1330 ITF_UNRES|ITF_OBJ);
1331 }
1332
1333 return it;
1334 }
1335
1336 size_t
dav2val(struct dwaval * dav,size_t psz)1337 dav2val(struct dwaval *dav, size_t psz)
1338 {
1339 uint64_t val = (uint64_t)-1;
1340
1341 switch (dav->dav_dat->dat_form) {
1342 case DW_FORM_addr:
1343 case DW_FORM_ref_addr:
1344 if (psz == sizeof(uint32_t))
1345 val = dav->dav_u32;
1346 else
1347 val = dav->dav_u64;
1348 break;
1349 case DW_FORM_block1:
1350 case DW_FORM_block2:
1351 case DW_FORM_block4:
1352 case DW_FORM_block:
1353 dw_loc_parse(&dav->dav_buf, NULL, &val, NULL);
1354 break;
1355 case DW_FORM_flag:
1356 case DW_FORM_data1:
1357 case DW_FORM_ref1:
1358 val = dav->dav_u8;
1359 break;
1360 case DW_FORM_data2:
1361 case DW_FORM_ref2:
1362 val = dav->dav_u16;
1363 break;
1364 case DW_FORM_data4:
1365 case DW_FORM_ref4:
1366 val = dav->dav_u32;
1367 break;
1368 case DW_FORM_sdata:
1369 case DW_FORM_data8:
1370 case DW_FORM_ref8:
1371 case DW_FORM_udata:
1372 case DW_FORM_ref_udata:
1373 val = dav->dav_u64;
1374 break;
1375 case DW_FORM_strp:
1376 val = dav->dav_u32;
1377 break;
1378 case DW_FORM_flag_present:
1379 val = 1;
1380 break;
1381 default:
1382 break;
1383 }
1384
1385 return val;
1386 }
1387
1388 const char *
dav2str(struct dwaval * dav)1389 dav2str(struct dwaval *dav)
1390 {
1391 const char *str = NULL;
1392 extern const char *dstrbuf;
1393 extern size_t dstrlen;
1394
1395 switch (dav->dav_dat->dat_form) {
1396 case DW_FORM_string:
1397 str = dav->dav_str;
1398 break;
1399 case DW_FORM_strp:
1400 if (dav->dav_u32 >= dstrlen)
1401 str = NULL;
1402 else
1403 str = dstrbuf + dav->dav_u32;
1404 break;
1405 default:
1406 break;
1407 }
1408
1409 return str;
1410 }
1411
1412 const char *
enc2name(unsigned short enc)1413 enc2name(unsigned short enc)
1414 {
1415 static const char *enc_name[] = { "address", "boolean", "complex float",
1416 "float", "signed", "char", "unsigned", "unsigned char",
1417 "imaginary float", "packed decimal", "numeric string", "edited",
1418 "signed fixed", "unsigned fixed", "decimal float" };
1419
1420 if (enc > 0 && enc <= nitems(enc_name))
1421 return enc_name[enc - 1];
1422
1423 return "invalid";
1424 }
1425