6 #define HUGEINT 0x7fffffff
7 #define NNAME 20 /* a relic of the past */
9 typedef struct txtsym Txtsym;
10 typedef struct file File;
11 typedef struct hist Hist;
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 */
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 */
25 struct file { /* Per input file header to history stack */
26 uvlong addr; /* address of first text sym */
28 Txtsym *txt; /* first text symbol */
29 Sym *sym; /* only during initilization */
31 int n; /* size of history stack */
32 Hist *hist; /* history stack */
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 */
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*);
77 * initialize the symbol tables
80 syminit(int fd, Fhdr *fp)
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));
98 werrstr("can't malloc %ld bytes", fp->symsz);
101 Binit(&b, fd, OREAD);
102 Bseek(&b, fp->symoff, 0);
105 if((fp->_magic && (fp->magic & HDR_MAGIC)) || mach->szaddr == 8)
109 for(p = symbols; size < fp->symsz; p++, nsym++) {
111 if(Bread(&b, &vl, 8) != 8)
112 return symerrmsg(8, "symbol");
113 p->value = beswav(vl);
116 if(Bread(&b, &l, 4) != 4)
117 return symerrmsg(4, "symbol");
118 p->value = (u32int)beswal(l);
120 if(Bread(&b, &p->type, sizeof(p->type)) != sizeof(p->type))
121 return symerrmsg(sizeof(p->value), "symbol");
123 i = decodename(&b, p);
126 size += i+svalsz+sizeof(p->type);
128 /* count global & auto vars, text symbols, and file names */
143 if(strcmp(p->name, ".frame") == 0) {
147 else if(p->value > fmax)
148 fmax = p->value; /* highest path index */
156 if(p->value == 1) { /* one extra per file */
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);
171 werrstr("can't malloc %ld bytes", fp->sppcsz);
174 Bseek(&b, fp->sppcoff, 0);
175 if(Bread(&b, spoff, fp->sppcsz) != fp->sppcsz){
177 return symerrmsg(fp->sppcsz, "sp-pc");
179 spoffend = spoff+fp->sppcsz;
181 if (fp->lnpcsz) { /* pc-line number table */
182 pcline = (uchar *)malloc(fp->lnpcsz);
184 werrstr("can't malloc %ld bytes", fp->lnpcsz);
187 Bseek(&b, fp->lnpcoff, 0);
188 if(Bread(&b, pcline, fp->lnpcsz) != fp->lnpcsz){
190 return symerrmsg(fp->lnpcsz, "pc-line");
192 pclineend = pcline+fp->lnpcsz;
198 symerrmsg(int n, char *table)
200 werrstr("can't read %d bytes of %s table", n, table);
205 decodename(Biobuf *bp, Sym *p)
212 if((p->type & 0x80) == 0) { /* old-style, fixed length names */
213 p->name = malloc(NNAME);
215 werrstr("can't malloc %d bytes", NNAME);
218 if(Bread(bp, p->name, NNAME) != NNAME)
219 return symerrmsg(NNAME, "symbol");
225 if(p->type == 'z' || p->type == 'Z') {
228 werrstr("can't read symbol name");
234 if(c1 < 0 || c2 < 0) {
235 werrstr("can't read symbol name");
238 if(c1 == 0 && c2 == 0)
241 n = Bseek(bp, 0, 1)-o;
244 werrstr("can't malloc %ld bytes", n);
248 if(Bread(bp, p->name, n) != n) {
249 werrstr("can't read %ld bytes of symbol name", n);
253 cp = Brdline(bp, '\0');
255 werrstr("can't read symbol name");
261 werrstr("can't malloc %ld bytes", n);
270 * free any previously loaded symbol tables
314 * delimit the text segment
317 textseg(uvlong base, Fhdr *fp)
320 txtend = base+fp->txtsz;
324 * symbase: return base and size of raw symbol table
325 * (special hack for high access rate operations)
335 * Get the ith symbol table entry
340 if(index >= 0 && index < nsym)
341 return &symbols[index];
346 * initialize internal symbol tables
361 /* allocate the tables */
363 globals = malloc(nglob*sizeof(*globals));
365 werrstr("can't malloc global symbol table");
370 txt = malloc(ntxt*sizeof(*txt));
372 werrstr("can't malloc text symbol table");
376 fnames = malloc((fmax+1)*sizeof(*fnames));
378 werrstr("can't malloc file name table");
381 memset(fnames, 0, (fmax+1)*sizeof(*fnames));
382 files = malloc(nfiles*sizeof(*files));
384 werrstr("can't malloc file table");
387 hist = malloc(nhist*sizeof(Hist));
389 werrstr("can't malloc history stack");
392 autos = malloc(nauto*sizeof(Sym*));
394 werrstr("can't malloc auto symbol table");
397 /* load the tables */
404 for(p = symbols; i-- > 0; p++) {
411 print("Global: %s %llux\n", p->name, p->value);
415 if(p->value == 1) { /* New file */
418 f->hist[nh].name = 0; /* one extra */
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;
434 printhist("-> ", &f->hist[nh], 1);
439 f->hist[nh-1].offset = p->value;
442 case 't': /* Text: terminate history if first in file */
450 print("TEXT: %s at %llux\n", p->name, p->value);
451 if(f && !f->sym) { /* first */
458 case 'm': /* Local Vars */
460 print("Warning: Free floating local var: %s\n",
464 print("Local: %s %llux\n", p->name, p->value);
465 tp->locals[tp->n] = p;
470 case 'f': /* File names */
472 print("Fname: %s\n", p->name);
473 fnames[p->value] = p;
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);
484 for(i = 0, f = files; i < nfiles; i++, f++) {
485 for(j = 0; j < ntxt; j++) {
486 if(f->sym == tp->sym) {
488 print("LINK: %s to at %llux", f->sym->name, f->addr);
489 printhist("... ", f->hist, 1);
494 if(++tp >= txt+ntxt) /* wrap around */
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.
508 lookup(char *fn, char *var, Symbol *s)
515 found = findtext(fn, s);
516 if(var == 0) /* case 2: fn not in text */
518 else if(!found) /* case 1: fn not found */
521 found = findtext(var, s);
523 return 1; /* case 3: var found in text */
524 } else return 0; /* case 4: fn & var == zero */
527 return findlocal(s, var, s); /* case 1: fn found */
528 return findglobal(var, s); /* case 3: var not found */
533 * find a function by name
536 findtext(char *name, Symbol *s)
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];
551 * find global variable by name
554 findglobal(char *name, Symbol *s)
558 for(i = 0; i < nglob; i++) {
559 if(strcmp(globals[i]->name, name) == 0) {
560 fillsym(globals[i], s);
569 * find the local variable by name within a given function
572 findlocal(Symbol *s1, char *name, Symbol *s2)
578 return findlocvar(s1, name, s2);
582 * find the local variable by name within a given function
583 * (internal function - does no parameter validation)
586 findlocvar(Symbol *s1, char *name, Symbol *s2)
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;
605 * Get ith text symbol
608 textsym(Symbol *s, int index)
613 if(index < 0 || index >= ntxt)
615 fillsym(txt[index].sym, s);
616 s->handle = (void *)&txt[index];
625 filesym(int index, char *buf, int n)
631 if(index < 0 || index >= nfiles)
633 hp = files[index].hist;
636 return fileelem(fnames, (uchar*)hp->name, buf, n);
640 * Lookup name of local variable located at an offset into the frame.
641 * The type selects either a parameter or automatic.
644 getauto(Symbol *s1, int off, int type, Symbol *s2)
654 else if(type == CAUTO)
660 tp = (Txtsym *)s1->handle;
663 for(i = 0; i < tp->n; i++) {
665 if(p->type == t && p->value == off) {
667 s2->handle = s1->handle;
668 s2->index = tp->n-1 - i;
676 * Find text symbol containing addr; binary search assumes text array is sorted by addr
679 srchtext(uvlong addr)
688 for (mid = (bot+top)/2; mid < top; mid = (bot+top)/2) {
692 else if(mid != ntxt-1 && val >= txt[mid+1].sym->value)
701 * Find data symbol containing addr; binary search assumes data array is sorted by addr
704 srchdata(uvlong addr)
713 for(mid = (bot+top)/2; mid < top; mid = (bot+top)/2) {
717 else if(mid < nglob-1 && val >= globals[mid+1]->value)
726 * Find symbol containing val in specified search space
727 * There is a special case when a value falls beyond the end
728 * of the text segment; if the search space is CTEXT, that value
729 * (usually etext) is returned. If the search space is CANY, symbols in the
730 * data space are searched for a match.
733 findsym(uvlong val, int type, Symbol *s)
740 if(type == CTEXT || type == CANY) {
743 if(type == CTEXT || i != ntxt-1) {
744 fillsym(txt[i].sym, s);
745 s->handle = (void *) &txt[i];
751 if(type == CDATA || type == CANY) {
754 fillsym(globals[i], s);
763 * Find the start and end address of the function containing addr
766 fnbound(uvlong addr, uvlong *bounds)
774 if(0 <= i && i < ntxt-1) {
775 bounds[0] = txt[i].sym->value;
776 bounds[1] = txt[i+1].sym->value;
783 * get the ith local symbol for a function
784 * the input symbol table is reverse ordered, so we reverse
785 * accesses here to maintain approx. parameter ordering in a stack trace.
788 localsym(Symbol *s, int index)
792 if(s == 0 || index < 0)
797 tp = (Txtsym *)s->handle;
798 if(tp && tp->locals && index < tp->n) {
799 fillsym(tp->locals[tp->n-index-1], s); /* reverse */
800 s->handle = (void *)tp;
808 * get the ith global symbol
811 globalsym(Symbol *s, int index)
818 if(index >=0 && index < nglob) {
819 fillsym(globals[index], s);
827 * find the pc given a file name and line offset into it.
830 file2pc(char *file, long line)
834 uvlong pc, start, end;
837 if(buildtbls() == 0 || files == 0)
839 name = encfname(file);
840 if(name == 0) { /* encode the file name */
841 werrstr("file %s not found", file);
844 /* find this history stack */
845 for(i = 0, fp = files; i < nfiles; i++, fp++)
846 if (hline(fp, name, &line))
850 werrstr("line %ld in file %s not found", line, file);
853 start = fp->addr; /* first text addr this file */
855 end = (fp+1)->addr; /* first text addr next file */
857 end = 0; /* last file in load module */
859 * At this point, line contains the offset into the file.
860 * run the state machine to locate the pc closest to that value.
863 print("find pc for %ld - between: %llux and %llux\n", line, start, end);
864 pc = line2addr(line, start, end);
866 werrstr("line %ld not in file %s", line, file);
873 * search for a path component index
876 pathcomp(char *s, int n)
880 for(i = 0; i <= fmax; i++)
881 if(fnames[i] && strncmp(s, fnames[i]->name, n) == 0)
887 * Encode a char file name as a sequence of short indices
888 * into the file name dictionary.
897 if(*file == '/') /* always check first '/' */
900 cp2 = strchr(file, '/');
902 cp2 = strchr(file, 0);
906 for(i = 0; *cp; i++) {
907 j = pathcomp(cp, cp2-cp);
909 return 0; /* not found */
910 dest = realloc(dest, (i+1)*sizeof(short));
913 while(*cp == '/') /* skip embedded '/'s */
915 cp2 = strchr(cp, '/');
919 dest = realloc(dest, (i+1)*sizeof(short));
925 * Search a history stack for a matching file name accumulating
926 * the size of intervening files in the stack.
929 hline(File *fp, short *name, long *line)
935 for(hp = fp->hist; hp->name; hp++) /* find name in stack */
936 if(hp->name[1] || hp->name[2]) {
940 if(!hp->name) /* match not found */
943 printhist("hline found ... ", hp, 1);
945 * unwind the stack until empty or we hit an entry beyond our line
950 for(hp++; depth && hp->name; hp++) {
952 printhist("hline inspect ... ", hp, 1);
953 if(hp->name[1] || hp->name[2]) {
954 if(hp->offset){ /* Z record */
956 if(hcomp(hp, name)) {
957 if(*line <= hp->offset)
959 ln = *line+hp->line-hp->offset;
960 depth = 1; /* implicit pop */
962 depth = 2; /* implicit push */
963 } else if(depth == 1 && ln < hp->line-offset)
964 break; /* Beyond our line */
965 else if(depth++ == 1) /* push */
967 } else if(--depth == 1) /* pop */
975 * compare two encoded file names
978 hcomp(Hist *hp, short *sp)
984 cp = (uchar *)hp->name;
988 for (i = 1; j = (cp[i]<<8)|cp[i+1]; i += 2) {
1000 * Convert a pc to a "file:line {file:line}" string.
1003 fileline(char *str, int n, uvlong dot)
1005 long line, top, bot, mid;
1009 if(buildtbls() == 0)
1011 /* binary search assumes file list is sorted by addr */
1014 for (mid = (bot+top)/2; mid < top; mid = (bot+top)/2) {
1018 else if(mid < nfiles-1 && dot >= (f+1)->addr)
1021 line = pc2line(dot);
1022 if(line > 0 && fline(str, n, line, f->hist, 0) >= 0)
1031 * Convert a line number within a composite file to relative line
1032 * number in a source file. A composite file is the source
1033 * file with included files inserted in line.
1036 fline(char *str, int n, long line, Hist *base, Hist **ret)
1038 Hist *start; /* start of current level */
1039 Hist *h; /* current entry */
1040 long delta; /* sum of size of files this level */
1046 while(h && h->name && line > h->line) {
1047 if(h->name[1] || h->name[2]) {
1048 if(h->offset != 0) { /* #line Directive */
1049 delta = h->line-h->offset+1;
1052 } else { /* beginning of File */
1056 k = fline(str, n, line, start, &h);
1062 if(start == base && ret) { /* end of recursion level */
1065 } else { /* end of included file */
1066 delta += h->line-start->line;
1075 line = line-start->line+1;
1077 line = line-delta+1;
1079 strncpy(str, "<eof>", n);
1081 k = fileelem(fnames, (uchar*)start->name, str, n);
1083 sprint(str+k, ":%ld", line);
1085 /**********Remove comments for complete back-trace of include sequence
1086 * if(start != base) {
1092 * k += fileelem(fnames, (uchar*) base->name, str+k, n-k);
1094 * sprint(str+k, ":%ld}", start->line-delta);
1096 ********************/
1101 * convert an encoded file name to a string.
1104 fileelem(Sym **fp, uchar *cp, char *buf, int n)
1111 for(i = 1; j = (cp[i]<<8)|cp[i+1]; i+=2){
1113 if(bp != buf && bp[-1] != '/' && bp < end)
1115 while(bp < end && *c)
1128 * compare the values of two symbol table entries.
1131 symcomp(void *a, void *b)
1135 i = (*(Sym**)a)->value - (*(Sym**)b)->value;
1138 return strcmp((*(Sym**)a)->name, (*(Sym**)b)->name);
1142 * compare the values of the symbols referenced by two text table entries
1145 txtcomp(void *a, void *b)
1147 return ((Txtsym*)a)->sym->value - ((Txtsym*)b)->sym->value;
1151 * compare the values of the symbols referenced by two file table entries
1154 filecomp(void *a, void *b)
1156 return ((File*)a)->addr - ((File*)b)->addr;
1160 * fill an interface Symbol structure from a symbol table entry
1163 fillsym(Sym *sp, Symbol *s)
1166 s->value = sp->value;
1199 * find the stack frame, given the pc
1205 uvlong currpc, currsp;
1210 currpc = txtstart - mach->pcquant;
1212 if(pc<currpc || pc>txtend)
1214 for(c = spoff; c < spoffend; c++) {
1219 currsp += (c[1]<<24)|(c[2]<<16)|(c[3]<<8)|c[4];
1227 currpc += mach->pcquant*(u-129);
1228 currpc += mach->pcquant;
1234 * find the source file line number for a given value of the pc
1246 currpc = txtstart-mach->pcquant;
1247 if(pc<currpc || pc>txtend)
1250 for(c = pcline; c < pclineend; c++) {
1255 currline += (c[1]<<24)|(c[2]<<16)|(c[3]<<8)|c[4];
1263 currpc += mach->pcquant*(u-129);
1264 currpc += mach->pcquant;
1270 * find the pc associated with a line number
1271 * basepc and endpc are text addresses bounding the search.
1272 * if endpc == 0, the end of the table is used (i.e., no upper bound).
1273 * usually, basepc and endpc contain the first text address in
1274 * a file and the first text address in the following file, respectively.
1277 line2addr(long line, uvlong basepc, uvlong endpc)
1285 if(pcline == 0 || line == 0)
1289 currpc = txtstart-mach->pcquant;
1294 for(c = pcline; c < pclineend; c++) {
1295 if(endpc && currpc >= endpc) /* end of file of interest */
1297 if(currpc >= basepc) { /* proper file */
1298 if(currline >= line) {
1310 currline += (c[1]<<24)|(c[2]<<16)|(c[3]<<8)|c[4];
1318 currpc += mach->pcquant*(u-129);
1319 currpc += mach->pcquant;
1327 * Print a history stack (debug). if count is 0, prints the whole stack
1330 printhist(char *msg, Hist *hp, int count)
1338 if(count && ++i > count)
1340 print("%s Line: %lx (%ld) Offset: %lx (%ld) Name: ", msg,
1341 hp->line, hp->line, hp->offset, hp->offset);
1342 for(cp = (uchar *)hp->name+1; (*cp<<8)|cp[1]; cp += 2) {
1343 if (cp != (uchar *)hp->name+1)
1345 print("%x", (*cp<<8)|cp[1]);
1347 fileelem(fnames, (uchar *) hp->name, buf, sizeof(buf));
1348 print(" (%s)\n", buf);
1355 * print the history stack for a file. (debug only)
1356 * if (name == 0) => print all history stacks.
1359 dumphist(char *name)
1365 if(buildtbls() == 0)
1368 fname = encfname(name);
1369 for(i = 0, f = files; i < nfiles; i++, f++)
1370 if(fname == 0 || hcomp(f->hist, fname))
1371 printhist("> ", f->hist, f->n);