1 // Inferno libmach/sym.c
2 // http://code.google.com/p/inferno-os/source/browse/utils/libmach/sym.c
3 //
4 // Copyright © 1994-1999 Lucent Technologies Inc.
5 // Power PC support Copyright © 1995-2004 C H Forsyth (forsyth@terzarima.net).
6 // Portions Copyright © 1997-1999 Vita Nuova Limited.
7 // Portions Copyright © 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com).
8 // Revisions Copyright © 2000-2004 Lucent Technologies Inc. and others.
9 // Portions Copyright © 2009 The Go Authors. All rights reserved.
10 //
11 // Permission is hereby granted, free of charge, to any person obtaining a copy
12 // of this software and associated documentation files (the "Software"), to deal
13 // in the Software without restriction, including without limitation the rights
14 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
15 // copies of the Software, and to permit persons to whom the Software is
16 // furnished to do so, subject to the following conditions:
17 //
18 // The above copyright notice and this permission notice shall be included in
19 // all copies or substantial portions of the Software.
20 //
21 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
24 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
26 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
27 // THE SOFTWARE.
28
29 #include <u.h>
30 #include <libc.h>
31 #include <bio.h>
32 #include <mach.h>
33
34 #define HUGEINT 0x7fffffff
35 #define NNAME 20 /* a relic of the past */
36
37 typedef struct txtsym Txtsym;
38 typedef struct file File;
39 typedef struct hist Hist;
40
41 struct txtsym { /* Text Symbol table */
42 int n; /* number of local vars */
43 Sym **locals; /* array of ptrs to autos */
44 Sym *sym; /* function symbol entry */
45 };
46
47 struct hist { /* Stack of include files & #line directives */
48 char *name; /* Assumes names Null terminated in file */
49 int32 line; /* line # where it was included */
50 int32 offset; /* line # of #line directive */
51 };
52
53 struct file { /* Per input file header to history stack */
54 uvlong addr; /* address of first text sym */
55 union {
56 Txtsym *txt; /* first text symbol */
57 Sym *sym; /* only during initilization */
58 };
59 int n; /* size of history stack */
60 Hist *hist; /* history stack */
61 };
62
63 static int debug = 0;
64
65 static Sym **autos; /* Base of auto variables */
66 static File *files; /* Base of file arena */
67 static int fmaxi; /* largest file path index */
68 static Sym **fnames; /* file names path component table */
69 static Sym **globals; /* globals by addr table */
70 static Hist *hist; /* base of history stack */
71 static int isbuilt; /* internal table init flag */
72 static int32 nauto; /* number of automatics */
73 static int32 nfiles; /* number of files */
74 static int32 nglob; /* number of globals */
75 static int32 nhist; /* number of history stack entries */
76 static int32 nsym; /* number of symbols */
77 static int ntxt; /* number of text symbols */
78 static uchar *pcline; /* start of pc-line state table */
79 static uchar *pclineend; /* end of pc-line table */
80 static uchar *spoff; /* start of pc-sp state table */
81 static uchar *spoffend; /* end of pc-sp offset table */
82 static Sym *symbols; /* symbol table */
83 static Txtsym *txt; /* Base of text symbol table */
84 static uvlong txtstart; /* start of text segment */
85 static uvlong txtend; /* end of text segment */
86 static uvlong firstinstr; /* as found from symtab; needed for amd64 */
87
88 static void cleansyms(void);
89 static int32 decodename(Biobuf*, Sym*);
90 static short *encfname(char*);
91 static int fline(char*, int, int32, Hist*, Hist**);
92 static void fillsym(Sym*, Symbol*);
93 static int findglobal(char*, Symbol*);
94 static int findlocvar(Symbol*, char *, Symbol*);
95 static int findtext(char*, Symbol*);
96 static int hcomp(Hist*, short*);
97 static int hline(File*, short*, int32*);
98 static void printhist(char*, Hist*, int);
99 static int buildtbls(void);
100 static int symcomp(const void*, const void*);
101 static int symerrmsg(int, char*);
102 static int txtcomp(const void*, const void*);
103 static int filecomp(const void*, const void*);
104
105 /*
106 * initialize the symbol tables
107 */
108 int
109 syminit(int fd, Fhdr *fp)
110 {
111 Sym *p;
112 int32 i, l, size;
113 vlong vl;
114 Biobuf b;
115 int svalsz;
116
117 if(fp->symsz == 0)
118 return 0;
119 if(fp->type == FNONE)
120 return 0;
121
122 cleansyms();
123 textseg(fp->txtaddr, fp);
124 /* minimum symbol record size = 4+1+2 bytes */
125 symbols = malloc((fp->symsz/(4+1+2)+1)*sizeof(Sym));
126 if(symbols == 0) {
127 werrstr("can't malloc %ld bytes", fp->symsz);
128 return -1;
129 }
130 Binit(&b, fd, OREAD);
131 Bseek(&b, fp->symoff, 0);
132 nsym = 0;
133 size = 0;
134 for(p = symbols; size < fp->symsz; p++, nsym++) {
135 if(fp->_magic && (fp->magic & HDR_MAGIC)){
136 svalsz = 8;
137 if(Bread(&b, &vl, 8) != 8)
138 return symerrmsg(8, "symbol");
139 p->value = beswav(vl);
140 }
141 else{
142 svalsz = 4;
143 if(Bread(&b, &l, 4) != 4)
144 return symerrmsg(4, "symbol");
145 p->value = (u32int)beswal(l);
146 }
147 if(Bread(&b, &p->type, sizeof(p->type)) != sizeof(p->type))
148 return symerrmsg(sizeof(p->value), "symbol");
149
150 i = decodename(&b, p);
151 if(i < 0)
152 return -1;
153 size += i+svalsz+sizeof(p->type);
154
155 if(svalsz == 8){
156 if(Bread(&b, &vl, 8) != 8)
157 return symerrmsg(8, "symbol");
158 p->gotype = beswav(vl);
159 }
160 else{
161 if(Bread(&b, &l, 4) != 4)
162 return symerrmsg(4, "symbol");
163 p->gotype = (u32int)beswal(l);
164 }
165 size += svalsz;
166
167 /* count global & auto vars, text symbols, and file names */
168 switch (p->type) {
169 case 'l':
170 case 'L':
171 case 't':
172 case 'T':
173 ntxt++;
174 break;
175 case 'd':
176 case 'D':
177 case 'b':
178 case 'B':
179 nglob++;
180 break;
181 case 'f':
182 if(strcmp(p->name, ".frame") == 0) {
183 p->type = 'm';
184 nauto++;
185 }
186 else if(p->value > fmaxi)
187 fmaxi = p->value; /* highest path index */
188 break;
189 case 'a':
190 case 'p':
191 case 'm':
192 nauto++;
193 break;
194 case 'z':
195 if(p->value == 1) { /* one extra per file */
196 nhist++;
197 nfiles++;
198 }
199 nhist++;
200 break;
201 default:
202 break;
203 }
204 }
205 if (debug)
206 print("NG: %ld NT: %d NF: %d\n", nglob, ntxt, fmaxi);
207 if (fp->sppcsz) { /* pc-sp offset table */
208 spoff = (uchar *)malloc(fp->sppcsz);
209 if(spoff == 0) {
210 werrstr("can't malloc %ld bytes", fp->sppcsz);
211 return -1;
212 }
213 Bseek(&b, fp->sppcoff, 0);
214 if(Bread(&b, spoff, fp->sppcsz) != fp->sppcsz){
215 spoff = 0;
216 return symerrmsg(fp->sppcsz, "sp-pc");
217 }
218 spoffend = spoff+fp->sppcsz;
219 }
220 if (fp->lnpcsz) { /* pc-line number table */
221 pcline = (uchar *)malloc(fp->lnpcsz);
222 if(pcline == 0) {
223 werrstr("can't malloc %ld bytes", fp->lnpcsz);
224 return -1;
225 }
226 Bseek(&b, fp->lnpcoff, 0);
227 if(Bread(&b, pcline, fp->lnpcsz) != fp->lnpcsz){
228 pcline = 0;
229 return symerrmsg(fp->lnpcsz, "pc-line");
230 }
231 pclineend = pcline+fp->lnpcsz;
232 }
233 return nsym;
234 }
235
236 static int
237 symerrmsg(int n, char *table)
238 {
239 werrstr("can't read %d bytes of %s table", n, table);
240 return -1;
241 }
242
243 static int32
244 decodename(Biobuf *bp, Sym *p)
245 {
246 char *cp;
247 int c1, c2;
248 int32 n;
249 vlong o;
250
251 if((p->type & 0x80) == 0) { /* old-style, fixed length names */
252 p->name = malloc(NNAME);
253 if(p->name == 0) {
254 werrstr("can't malloc %d bytes", NNAME);
255 return -1;
256 }
257 if(Bread(bp, p->name, NNAME) != NNAME)
258 return symerrmsg(NNAME, "symbol");
259 Bseek(bp, 3, 1);
260 return NNAME+3;
261 }
262
263 p->type &= ~0x80;
264 if(p->type == 'z' || p->type == 'Z') {
265 o = Bseek(bp, 0, 1);
266 if(Bgetc(bp) < 0) {
267 werrstr("can't read symbol name");
268 return -1;
269 }
270 for(;;) {
271 c1 = Bgetc(bp);
272 c2 = Bgetc(bp);
273 if(c1 < 0 || c2 < 0) {
274 werrstr("can't read symbol name");
275 return -1;
276 }
277 if(c1 == 0 && c2 == 0)
278 break;
279 }
280 n = Bseek(bp, 0, 1)-o;
281 p->name = malloc(n);
282 if(p->name == 0) {
283 werrstr("can't malloc %ld bytes", n);
284 return -1;
285 }
286 Bseek(bp, -n, 1);
287 if(Bread(bp, p->name, n) != n) {
288 werrstr("can't read %ld bytes of symbol name", n);
289 return -1;
290 }
291 } else {
292 cp = Brdline(bp, '\0');
293 if(cp == 0) {
294 werrstr("can't read symbol name");
295 return -1;
296 }
297 n = Blinelen(bp);
298 p->name = malloc(n);
299 if(p->name == 0) {
300 werrstr("can't malloc %ld bytes", n);
301 return -1;
302 }
303 strcpy(p->name, cp);
304 }
305 return n;
306 }
307
308 /*
309 * free any previously loaded symbol tables
310 */
311 static void
312 cleansyms(void)
313 {
314 if(globals)
315 free(globals);
316 globals = 0;
317 nglob = 0;
318 if(txt)
319 free(txt);
320 txt = 0;
321 ntxt = 0;
322 if(fnames)
323 free(fnames);
324 fnames = 0;
325 fmaxi = 0;
326
327 if(files)
328 free(files);
329 files = 0;
330 nfiles = 0;
331 if(hist)
332 free(hist);
333 hist = 0;
334 nhist = 0;
335 if(autos)
336 free(autos);
337 autos = 0;
338 nauto = 0;
339 isbuilt = 0;
340 if(symbols)
341 free(symbols);
342 symbols = 0;
343 nsym = 0;
344 if(spoff)
345 free(spoff);
346 spoff = 0;
347 if(pcline)
348 free(pcline);
349 pcline = 0;
350 }
351
352 /*
353 * delimit the text segment
354 */
355 void
356 textseg(uvlong base, Fhdr *fp)
357 {
358 txtstart = base;
359 txtend = base+fp->txtsz;
360 }
361
362 /*
363 * symbase: return base and size of raw symbol table
364 * (special hack for high access rate operations)
365 */
366 Sym *
367 symbase(int32 *n)
368 {
369 *n = nsym;
370 return symbols;
371 }
372
373 /*
374 * Get the ith symbol table entry
375 */
376 Sym *
377 getsym(int index)
378 {
379 if(index >= 0 && index < nsym)
380 return &symbols[index];
381 return 0;
382 }
383
384 /*
385 * initialize internal symbol tables
386 */
387 static int
388 buildtbls(void)
389 {
390 int32 i;
391 int j, nh, ng, nt;
392 File *f;
393 Txtsym *tp;
394 Hist *hp;
395 Sym *p, **ap;
396
397 if(isbuilt)
398 return 1;
399 isbuilt = 1;
400 /* allocate the tables */
401 firstinstr = 0;
402 if(nglob) {
403 globals = malloc(nglob*sizeof(*globals));
404 if(!globals) {
405 werrstr("can't malloc global symbol table");
406 return 0;
407 }
408 }
409 if(ntxt) {
410 txt = malloc(ntxt*sizeof(*txt));
411 if (!txt) {
412 werrstr("can't malloc text symbol table");
413 return 0;
414 }
415 }
416 fnames = malloc((fmaxi+1)*sizeof(*fnames));
417 if (!fnames) {
418 werrstr("can't malloc file name table");
419 return 0;
420 }
421 memset(fnames, 0, (fmaxi+1)*sizeof(*fnames));
422 files = malloc(nfiles*sizeof(*files));
423 if(!files) {
424 werrstr("can't malloc file table");
425 return 0;
426 }
427 hist = malloc(nhist*sizeof(Hist));
428 if(hist == 0) {
429 werrstr("can't malloc history stack");
430 return 0;
431 }
432 autos = malloc(nauto*sizeof(Sym*));
433 if(autos == 0) {
434 werrstr("can't malloc auto symbol table");
435 return 0;
436 }
437 /* load the tables */
438 ng = nt = nh = 0;
439 f = 0;
440 tp = 0;
441 i = nsym;
442 hp = hist;
443 ap = autos;
444 for(p = symbols; i-- > 0; p++) {
445 //print("sym %d type %c name %s value %llux\n", p-symbols, p->type, p->name, p->value);
446 switch(p->type) {
447 case 'D':
448 case 'd':
449 case 'B':
450 case 'b':
451 if(debug)
452 print("Global: %s %llux\n", p->name, p->value);
453 globals[ng++] = p;
454 break;
455 case 'z':
456 if(p->value == 1) { /* New file */
457 if(f) {
458 f->n = nh;
459 f->hist[nh].name = 0; /* one extra */
460 hp += nh+1;
461 f++;
462 }
463 else
464 f = files;
465 f->hist = hp;
466 f->sym = 0;
467 f->addr = 0;
468 nh = 0;
469 }
470 /* alloc one slot extra as terminator */
471 f->hist[nh].name = p->name;
472 f->hist[nh].line = p->value;
473 f->hist[nh].offset = 0;
474 if(debug)
475 printhist("-> ", &f->hist[nh], 1);
476 nh++;
477 break;
478 case 'Z':
479 if(f && nh > 0)
480 f->hist[nh-1].offset = p->value;
481 break;
482 case 'T':
483 case 't': /* Text: terminate history if first in file */
484 case 'L':
485 case 'l':
486 tp = &txt[nt++];
487 tp->n = 0;
488 tp->sym = p;
489 tp->locals = ap;
490 if(debug)
491 print("TEXT: %s at %llux\n", p->name, p->value);
492 if (firstinstr == 0 || p->value < firstinstr)
493 firstinstr = p->value;
494 if(f && !f->sym) { /* first */
495 f->sym = p;
496 f->addr = p->value;
497 }
498 break;
499 case 'a':
500 case 'p':
501 case 'm': /* Local Vars */
502 if(!tp)
503 print("Warning: Free floating local var: %s\n",
504 p->name);
505 else {
506 if(debug)
507 print("Local: %s %llux\n", p->name, p->value);
508 tp->locals[tp->n] = p;
509 tp->n++;
510 ap++;
511 }
512 break;
513 case 'f': /* File names */
514 if(debug)
515 print("Fname: %s\n", p->name);
516 fnames[p->value] = p;
517 break;
518 default:
519 break;
520 }
521 }
522 /* sort global and text tables into ascending address order */
523 qsort(globals, nglob, sizeof(Sym*), symcomp);
524 qsort(txt, ntxt, sizeof(Txtsym), txtcomp);
525 qsort(files, nfiles, sizeof(File), filecomp);
526 tp = txt;
527 for(i = 0, f = files; i < nfiles; i++, f++) {
528 for(j = 0; j < ntxt; j++) {
529 if(f->sym == tp->sym) {
530 if(debug) {
531 print("LINK: %s to at %llux", f->sym->name, f->addr);
532 printhist("... ", f->hist, 1);
533 }
534 f->txt = tp++;
535 break;
536 }
537 if(++tp >= txt+ntxt) /* wrap around */
538 tp = txt;
539 }
540 }
541 return 1;
542 }
543
544 /*
545 * find symbol function.var by name.
546 * fn != 0 && var != 0 => look for fn in text, var in data
547 * fn != 0 && var == 0 => look for fn in text
548 * fn == 0 && var != 0 => look for var first in text then in data space.
549 */
550 int
551 lookup(char *fn, char *var, Symbol *s)
552 {
553 int found;
554
555 if(buildtbls() == 0)
556 return 0;
557 if(fn) {
558 found = findtext(fn, s);
559 if(var == 0) /* case 2: fn not in text */
560 return found;
561 else if(!found) /* case 1: fn not found */
562 return 0;
563 } else if(var) {
564 found = findtext(var, s);
565 if(found)
566 return 1; /* case 3: var found in text */
567 } else return 0; /* case 4: fn & var == zero */
568
569 if(found)
570 return findlocal(s, var, s); /* case 1: fn found */
571 return findglobal(var, s); /* case 3: var not found */
572
573 }
574
575 /*
576 * strcmp, but allow '_' to match center dot (rune 00b7 == bytes c2 b7)
577 */
578 int
579 cdotstrcmp(char *sym, char *user) {
580 for (;;) {
581 while (*sym == *user) {
582 if (*sym++ == '\0')
583 return 0;
584 user++;
585 }
586 /* unequal - but maybe '_' matches center dot */
587 if (user[0] == '_' && (sym[0]&0xFF) == 0xc2 && (sym[1]&0xFF) == 0xb7) {
588 /* '_' matches center dot - advance and continue */
589 user++;
590 sym += 2;
591 continue;
592 }
593 break;
594 }
595 return *user - *sym;
596 }
597
598 /*
599 * find a function by name
600 */
601 static int
602 findtext(char *name, Symbol *s)
603 {
604 int i;
605
606 for(i = 0; i < ntxt; i++) {
607 if(cdotstrcmp(txt[i].sym->name, name) == 0) {
608 fillsym(txt[i].sym, s);
609 s->handle = (void *) &txt[i];
610 s->index = i;
611 return 1;
612 }
613 }
614 return 0;
615 }
616 /*
617 * find global variable by name
618 */
619 static int
620 findglobal(char *name, Symbol *s)
621 {
622 int32 i;
623
624 for(i = 0; i < nglob; i++) {
625 if(cdotstrcmp(globals[i]->name, name) == 0) {
626 fillsym(globals[i], s);
627 s->index = i;
628 return 1;
629 }
630 }
631 return 0;
632 }
633
634 /*
635 * find the local variable by name within a given function
636 */
637 int
638 findlocal(Symbol *s1, char *name, Symbol *s2)
639 {
640 if(s1 == 0)
641 return 0;
642 if(buildtbls() == 0)
643 return 0;
644 return findlocvar(s1, name, s2);
645 }
646
647 /*
648 * find the local variable by name within a given function
649 * (internal function - does no parameter validation)
650 */
651 static int
652 findlocvar(Symbol *s1, char *name, Symbol *s2)
653 {
654 Txtsym *tp;
655 int i;
656
657 tp = (Txtsym *)s1->handle;
658 if(tp && tp->locals) {
659 for(i = 0; i < tp->n; i++)
660 if (cdotstrcmp(tp->locals[i]->name, name) == 0) {
661 fillsym(tp->locals[i], s2);
662 s2->handle = (void *)tp;
663 s2->index = tp->n-1 - i;
664 return 1;
665 }
666 }
667 return 0;
668 }
669
670 /*
671 * Get ith text symbol
672 */
673 int
674 textsym(Symbol *s, int index)
675 {
676
677 if(buildtbls() == 0)
678 return 0;
679 if(index < 0 || index >= ntxt)
680 return 0;
681 fillsym(txt[index].sym, s);
682 s->handle = (void *)&txt[index];
683 s->index = index;
684 return 1;
685 }
686
687 /*
688 * Get ith file name
689 */
690 int
691 filesym(int index, char *buf, int n)
692 {
693 Hist *hp;
694
695 if(buildtbls() == 0)
696 return 0;
697 if(index < 0 || index >= nfiles)
698 return 0;
699 hp = files[index].hist;
700 if(!hp || !hp->name)
701 return 0;
702 return fileelem(fnames, (uchar*)hp->name, buf, n);
703 }
704
705 /*
706 * Lookup name of local variable located at an offset into the frame.
707 * The type selects either a parameter or automatic.
708 */
709 int
710 getauto(Symbol *s1, int off, int type, Symbol *s2)
711 {
712 Txtsym *tp;
713 Sym *p;
714 int i, t;
715
716 if(s1 == 0)
717 return 0;
718 if(type == CPARAM)
719 t = 'p';
720 else if(type == CAUTO)
721 t = 'a';
722 else
723 return 0;
724 if(buildtbls() == 0)
725 return 0;
726 tp = (Txtsym *)s1->handle;
727 if(tp == 0)
728 return 0;
729 for(i = 0; i < tp->n; i++) {
730 p = tp->locals[i];
731 if(p->type == t && p->value == off) {
732 fillsym(p, s2);
733 s2->handle = s1->handle;
734 s2->index = tp->n-1 - i;
735 return 1;
736 }
737 }
738 return 0;
739 }
740
741 /*
742 * Find text symbol containing addr; binary search assumes text array is sorted by addr
743 */
744 static int
745 srchtext(uvlong addr)
746 {
747 uvlong val;
748 int top, bot, mid;
749 Sym *sp;
750
751 val = addr;
752 bot = 0;
753 top = ntxt;
754 for (mid = (bot+top)/2; mid < top; mid = (bot+top)/2) {
755 sp = txt[mid].sym;
756 if(val < sp->value)
757 top = mid;
758 else if(mid != ntxt-1 && val >= txt[mid+1].sym->value)
759 bot = mid;
760 else
761 return mid;
762 }
763 return -1;
764 }
765
766 /*
767 * Find data symbol containing addr; binary search assumes data array is sorted by addr
768 */
769 static int
770 srchdata(uvlong addr)
771 {
772 uvlong val;
773 int top, bot, mid;
774 Sym *sp;
775
776 bot = 0;
777 top = nglob;
778 val = addr;
779 for(mid = (bot+top)/2; mid < top; mid = (bot+top)/2) {
780 sp = globals[mid];
781 if(val < sp->value)
782 top = mid;
783 else if(mid < nglob-1 && val >= globals[mid+1]->value)
784 bot = mid;
785 else
786 return mid;
787 }
788 return -1;
789 }
790
791 /*
792 * Find symbol containing val in specified search space
793 * There is a special case when a value falls beyond the end
794 * of the text segment; if the search space is CTEXT, that value
795 * (usually etext) is returned. If the search space is CANY, symbols in the
796 * data space are searched for a match.
797 */
798 int
799 findsym(uvlong val, int type, Symbol *s)
800 {
801 int i;
802
803 if(buildtbls() == 0)
804 return 0;
805
806 if(type == CTEXT || type == CANY) {
807 i = srchtext(val);
808 if(i >= 0) {
809 if(type == CTEXT || i != ntxt-1) {
810 fillsym(txt[i].sym, s);
811 s->handle = (void *) &txt[i];
812 s->index = i;
813 return 1;
814 }
815 }
816 }
817 if(type == CDATA || type == CANY) {
818 i = srchdata(val);
819 if(i >= 0) {
820 fillsym(globals[i], s);
821 s->index = i;
822 return 1;
823 }
824 }
825 return 0;
826 }
827
828 /*
829 * Find the start and end address of the function containing addr
830 */
831 int
832 fnbound(uvlong addr, uvlong *bounds)
833 {
834 int i;
835
836 if(buildtbls() == 0)
837 return 0;
838
839 i = srchtext(addr);
840 if(0 <= i && i < ntxt-1) {
841 bounds[0] = txt[i].sym->value;
842 bounds[1] = txt[i+1].sym->value;
843 return 1;
844 }
845 return 0;
846 }
847
848 /*
849 * get the ith local symbol for a function
850 * the input symbol table is reverse ordered, so we reverse
851 * accesses here to maintain approx. parameter ordering in a stack trace.
852 */
853 int
854 localsym(Symbol *s, int index)
855 {
856 Txtsym *tp;
857
858 if(s == 0 || index < 0)
859 return 0;
860 if(buildtbls() == 0)
861 return 0;
862
863 tp = (Txtsym *)s->handle;
864 if(tp && tp->locals && index < tp->n) {
865 fillsym(tp->locals[tp->n-index-1], s); /* reverse */
866 s->handle = (void *)tp;
867 s->index = index;
868 return 1;
869 }
870 return 0;
871 }
872
873 /*
874 * get the ith global symbol
875 */
876 int
877 globalsym(Symbol *s, int index)
878 {
879 if(s == 0)
880 return 0;
881 if(buildtbls() == 0)
882 return 0;
883
884 if(index >=0 && index < nglob) {
885 fillsym(globals[index], s);
886 s->index = index;
887 return 1;
888 }
889 return 0;
890 }
891
892 /*
893 * find the pc given a file name and line offset into it.
894 */
895 uvlong
896 file2pc(char *file, int32 line)
897 {
898 File *fp;
899 int32 i;
900 uvlong pc, start, end;
901 short *name;
902
903 if(buildtbls() == 0 || files == 0)
904 return ~0;
905 name = encfname(file);
906 if(name == 0) { /* encode the file name */
907 werrstr("file %s not found", file);
908 return ~0;
909 }
910 /* find this history stack */
911 for(i = 0, fp = files; i < nfiles; i++, fp++)
912 if (hline(fp, name, &line))
913 break;
914 free(name);
915 if(i >= nfiles) {
916 werrstr("line %ld in file %s not found", line, file);
917 return ~0;
918 }
919 start = fp->addr; /* first text addr this file */
920 if(i < nfiles-1)
921 end = (fp+1)->addr; /* first text addr next file */
922 else
923 end = 0; /* last file in load module */
924 /*
925 * At this point, line contains the offset into the file.
926 * run the state machine to locate the pc closest to that value.
927 */
928 if(debug)
929 print("find pc for %ld - between: %llux and %llux\n", line, start, end);
930 pc = line2addr(line, start, end);
931 if(pc == ~0) {
932 werrstr("line %ld not in file %s", line, file);
933 return ~0;
934 }
935 return pc;
936 }
937
938 /*
939 * search for a path component index
940 */
941 static int
942 pathcomp(char *s, int n)
943 {
944 int i;
945
946 for(i = 0; i <= fmaxi; i++)
947 if(fnames[i] && strncmp(s, fnames[i]->name, n) == 0)
948 return i;
949 return -1;
950 }
951
952 /*
953 * Encode a char file name as a sequence of short indices
954 * into the file name dictionary.
955 */
956 static short*
957 encfname(char *file)
958 {
959 int i, j;
960 char *cp, *cp2;
961 short *dest;
962
963 if(*file == '/') /* always check first '/' */
964 cp2 = file+1;
965 else {
966 cp2 = strchr(file, '/');
967 if(!cp2)
968 cp2 = strchr(file, 0);
969 }
970 cp = file;
971 dest = 0;
972 for(i = 0; *cp; i++) {
973 j = pathcomp(cp, cp2-cp);
974 if(j < 0)
975 return 0; /* not found */
976 dest = realloc(dest, (i+1)*sizeof(short));
977 dest[i] = j;
978 cp = cp2;
979 while(*cp == '/') /* skip embedded '/'s */
980 cp++;
981 cp2 = strchr(cp, '/');
982 if(!cp2)
983 cp2 = strchr(cp, 0);
984 }
985 dest = realloc(dest, (i+1)*sizeof(short));
986 dest[i] = 0;
987 return dest;
988 }
989
990 /*
991 * Search a history stack for a matching file name accumulating
992 * the size of intervening files in the stack.
993 */
994 static int
995 hline(File *fp, short *name, int32 *line)
996 {
997 Hist *hp;
998 int offset, depth;
999 int32 ln;
1000
1001 for(hp = fp->hist; hp->name; hp++) /* find name in stack */
1002 if(hp->name[1] || hp->name[2]) {
1003 if(hcomp(hp, name))
1004 break;
1005 }
1006 if(!hp->name) /* match not found */
1007 return 0;
1008 if(debug)
1009 printhist("hline found ... ", hp, 1);
1010 /*
1011 * unwind the stack until empty or we hit an entry beyond our line
1012 */
1013 ln = *line;
1014 offset = hp->line-1;
1015 depth = 1;
1016 for(hp++; depth && hp->name; hp++) {
1017 if(debug)
1018 printhist("hline inspect ... ", hp, 1);
1019 if(hp->name[1] || hp->name[2]) {
1020 if(hp->offset){ /* Z record */
1021 offset = 0;
1022 if(hcomp(hp, name)) {
1023 if(*line <= hp->offset)
1024 break;
1025 ln = *line+hp->line-hp->offset;
1026 depth = 1; /* implicit pop */
1027 } else
1028 depth = 2; /* implicit push */
1029 } else if(depth == 1 && ln < hp->line-offset)
1030 break; /* Beyond our line */
1031 else if(depth++ == 1) /* push */
1032 offset -= hp->line;
1033 } else if(--depth == 1) /* pop */
1034 offset += hp->line;
1035 }
1036 *line = ln+offset;
1037 return 1;
1038 }
1039
1040 /*
1041 * compare two encoded file names
1042 */
1043 static int
1044 hcomp(Hist *hp, short *sp)
1045 {
1046 uchar *cp;
1047 int i, j;
1048 short *s;
1049
1050 cp = (uchar *)hp->name;
1051 s = sp;
1052 if (*s == 0)
1053 return 0;
1054 for (i = 1; j = (cp[i]<<8)|cp[i+1]; i += 2) {
1055 if(j == 0)
1056 break;
1057 if(*s == j)
1058 s++;
1059 else
1060 s = sp;
1061 }
1062 return *s == 0;
1063 }
1064
1065 /*
1066 * Convert a pc to a "file:line {file:line}" string.
1067 */
1068 int32
1069 fileline(char *str, int n, uvlong dot)
1070 {
1071 int32 line, top, bot, mid;
1072 File *f;
1073
1074 *str = 0;
1075 if(buildtbls() == 0)
1076 return 0;
1077 /* binary search assumes file list is sorted by addr */
1078 bot = 0;
1079 top = nfiles;
1080 for (mid = (bot+top)/2; mid < top; mid = (bot+top)/2) {
1081 f = &files[mid];
1082 if(dot < f->addr)
1083 top = mid;
1084 else if(mid < nfiles-1 && dot >= (f+1)->addr)
1085 bot = mid;
1086 else {
1087 line = pc2line(dot);
1088 if(line > 0 && fline(str, n, line, f->hist, 0) >= 0)
1089 return 1;
1090 break;
1091 }
1092 }
1093 return 0;
1094 }
1095
1096 /*
1097 * Convert a line number within a composite file to relative line
1098 * number in a source file. A composite file is the source
1099 * file with included files inserted in line.
1100 */
1101 static int
1102 fline(char *str, int n, int32 line, Hist *base, Hist **ret)
1103 {
1104 Hist *start; /* start of current level */
1105 Hist *h; /* current entry */
1106 int32 delta; /* sum of size of files this level */
1107 int k;
1108
1109 start = base;
1110 h = base;
1111 delta = h->line;
1112 while(h && h->name && line > h->line) {
1113 if(h->name[1] || h->name[2]) {
1114 if(h->offset != 0) { /* #line Directive */
1115 delta = h->line-h->offset+1;
1116 start = h;
1117 base = h++;
1118 } else { /* beginning of File */
1119 if(start == base)
1120 start = h++;
1121 else {
1122 k = fline(str, n, line, start, &h);
1123 if(k <= 0)
1124 return k;
1125 }
1126 }
1127 } else {
1128 if(start == base && ret) { /* end of recursion level */
1129 *ret = h;
1130 return 1;
1131 } else { /* end of included file */
1132 delta += h->line-start->line;
1133 h++;
1134 start = base;
1135 }
1136 }
1137 }
1138 if(!h)
1139 return -1;
1140 if(start != base)
1141 line = line-start->line+1;
1142 else
1143 line = line-delta+1;
1144 if(!h->name)
1145 strncpy(str, "<eof>", n);
1146 else {
1147 k = fileelem(fnames, (uchar*)start->name, str, n);
1148 if(k+8 < n)
1149 sprint(str+k, ":%ld", line);
1150 }
1151 /**********Remove comments for complete back-trace of include sequence
1152 * if(start != base) {
1153 * k = strlen(str);
1154 * if(k+2 < n) {
1155 * str[k++] = ' ';
1156 * str[k++] = '{';
1157 * }
1158 * k += fileelem(fnames, (uchar*) base->name, str+k, n-k);
1159 * if(k+10 < n)
1160 * sprint(str+k, ":%ld}", start->line-delta);
1161 * }
1162 ********************/
1163 return 0;
1164 }
1165
1166 /*
1167 * convert an encoded file name to a string.
1168 */
1169 int
1170 fileelem(Sym **fp, uchar *cp, char *buf, int n)
1171 {
1172 int i, j;
1173 char *c, *bp, *end;
1174
1175 bp = buf;
1176 end = buf+n-1;
1177 for(i = 1; j = (cp[i]<<8)|cp[i+1]; i+=2){
1178 c = fp[j]->name;
1179 if(bp != buf && bp[-1] != '/' && bp < end)
1180 *bp++ = '/';
1181 while(bp < end && *c)
1182 *bp++ = *c++;
1183 }
1184 *bp = 0;
1185 i = bp-buf;
1186 if(i > 1) {
1187 cleanname(buf);
1188 i = strlen(buf);
1189 }
1190 return i;
1191 }
1192
1193 /*
1194 * compare the values of two symbol table entries.
1195 */
1196 static int
1197 symcomp(const void *a, const void *b)
1198 {
1199 int i;
1200
1201 i = (*(Sym**)a)->value - (*(Sym**)b)->value;
1202 if (i)
1203 return i;
1204 return strcmp((*(Sym**)a)->name, (*(Sym**)b)->name);
1205 }
1206
1207 /*
1208 * compare the values of the symbols referenced by two text table entries
1209 */
1210 static int
1211 txtcomp(const void *a, const void *b)
1212 {
1213 return ((Txtsym*)a)->sym->value - ((Txtsym*)b)->sym->value;
1214 }
1215
1216 /*
1217 * compare the values of the symbols referenced by two file table entries
1218 */
1219 static int
1220 filecomp(const void *a, const void *b)
1221 {
1222 return ((File*)a)->addr - ((File*)b)->addr;
1223 }
1224
1225 /*
1226 * fill an interface Symbol structure from a symbol table entry
1227 */
1228 static void
1229 fillsym(Sym *sp, Symbol *s)
1230 {
1231 s->type = sp->type;
1232 s->value = sp->value;
1233 s->name = sp->name;
1234 s->index = 0;
1235 switch(sp->type) {
1236 case 'b':
1237 case 'B':
1238 case 'D':
1239 case 'd':
1240 s->class = CDATA;
1241 break;
1242 case 't':
1243 case 'T':
1244 case 'l':
1245 case 'L':
1246 s->class = CTEXT;
1247 break;
1248 case 'a':
1249 s->class = CAUTO;
1250 break;
1251 case 'p':
1252 s->class = CPARAM;
1253 break;
1254 case 'm':
1255 s->class = CSTAB;
1256 break;
1257 default:
1258 s->class = CNONE;
1259 break;
1260 }
1261 s->handle = 0;
1262 }
1263
1264 /*
1265 * find the stack frame, given the pc
1266 */
1267 uvlong
1268 pc2sp(uvlong pc)
1269 {
1270 uchar *c, u;
1271 uvlong currpc, currsp;
1272
1273 if(spoff == 0)
1274 return ~0;
1275 currsp = 0;
1276 currpc = txtstart - mach->pcquant;
1277
1278 if(pc<currpc || pc>txtend)
1279 return ~0;
1280 for(c = spoff; c < spoffend; c++) {
1281 if (currpc >= pc)
1282 return currsp;
1283 u = *c;
1284 if (u == 0) {
1285 currsp += (c[1]<<24)|(c[2]<<16)|(c[3]<<8)|c[4];
1286 c += 4;
1287 }
1288 else if (u < 65)
1289 currsp += 4*u;
1290 else if (u < 129)
1291 currsp -= 4*(u-64);
1292 else
1293 currpc += mach->pcquant*(u-129);
1294 currpc += mach->pcquant;
1295 }
1296 return ~0;
1297 }
1298
1299 /*
1300 * find the source file line number for a given value of the pc
1301 */
1302 int32
1303 pc2line(uvlong pc)
1304 {
1305 uchar *c, u;
1306 uvlong currpc;
1307 int32 currline;
1308
1309 if(pcline == 0)
1310 return -1;
1311 currline = 0;
1312 if (firstinstr != 0)
1313 currpc = firstinstr-mach->pcquant;
1314 else
1315 currpc = txtstart-mach->pcquant;
1316 if(pc<currpc || pc>txtend)
1317 return ~0;
1318
1319 for(c = pcline; c < pclineend && currpc < pc; c++) {
1320 u = *c;
1321 if(u == 0) {
1322 currline += (c[1]<<24)|(c[2]<<16)|(c[3]<<8)|c[4];
1323 c += 4;
1324 }
1325 else if(u < 65)
1326 currline += u;
1327 else if(u < 129)
1328 currline -= (u-64);
1329 else
1330 currpc += mach->pcquant*(u-129);
1331 currpc += mach->pcquant;
1332 }
1333 return currline;
1334 }
1335
1336 /*
1337 * find the pc associated with a line number
1338 * basepc and endpc are text addresses bounding the search.
1339 * if endpc == 0, the end of the table is used (i.e., no upper bound).
1340 * usually, basepc and endpc contain the first text address in
1341 * a file and the first text address in the following file, respectively.
1342 */
1343 uvlong
1344 line2addr(int32 line, uvlong basepc, uvlong endpc)
1345 {
1346 uchar *c, u;
1347 uvlong currpc, pc;
1348 int32 currline;
1349 int32 delta, d;
1350 int found;
1351
1352 if(pcline == 0 || line == 0)
1353 return ~0;
1354
1355 currline = 0;
1356 currpc = txtstart-mach->pcquant;
1357 pc = ~0;
1358 found = 0;
1359 delta = HUGEINT;
1360
1361 for(c = pcline; c < pclineend; c++) {
1362 if(endpc && currpc >= endpc) /* end of file of interest */
1363 break;
1364 if(currpc >= basepc) { /* proper file */
1365 if(currline >= line) {
1366 d = currline-line;
1367 found = 1;
1368 } else
1369 d = line-currline;
1370 if(d < delta) {
1371 delta = d;
1372 pc = currpc;
1373 }
1374 }
1375 u = *c;
1376 if(u == 0) {
1377 currline += (c[1]<<24)|(c[2]<<16)|(c[3]<<8)|c[4];
1378 c += 4;
1379 }
1380 else if(u < 65)
1381 currline += u;
1382 else if(u < 129)
1383 currline -= (u-64);
1384 else
1385 currpc += mach->pcquant*(u-129);
1386 currpc += mach->pcquant;
1387 }
1388 if(found)
1389 return pc;
1390 return ~0;
1391 }
1392
1393 /*
1394 * Print a history stack (debug). if count is 0, prints the whole stack
1395 */
1396 static void
1397 printhist(char *msg, Hist *hp, int count)
1398 {
1399 int i;
1400 uchar *cp;
1401 char buf[128];
1402
1403 i = 0;
1404 while(hp->name) {
1405 if(count && ++i > count)
1406 break;
1407 print("%s Line: %lx (%ld) Offset: %lx (%ld) Name: ", msg,
1408 hp->line, hp->line, hp->offset, hp->offset);
1409 for(cp = (uchar *)hp->name+1; (*cp<<8)|cp[1]; cp += 2) {
1410 if (cp != (uchar *)hp->name+1)
1411 print("/");
1412 print("%x", (*cp<<8)|cp[1]);
1413 }
1414 fileelem(fnames, (uchar *) hp->name, buf, sizeof(buf));
1415 print(" (%s)\n", buf);
1416 hp++;
1417 }
1418 }
1419
1420 #ifdef DEBUG
1421 /*
1422 * print the history stack for a file. (debug only)
1423 * if (name == 0) => print all history stacks.
1424 */
1425 void
1426 dumphist(char *name)
1427 {
1428 int i;
1429 File *f;
1430 short *fname;
1431
1432 if(buildtbls() == 0)
1433 return;
1434 if(name)
1435 fname = encfname(name);
1436 for(i = 0, f = files; i < nfiles; i++, f++)
1437 if(fname == 0 || hcomp(f->hist, fname))
1438 printhist("> ", f->hist, f->n);
1439
1440 if(fname)
1441 free(fname);
1442 }
1443 #endif