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