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