sym.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

			top = mid;
		else if(mid != ntxt-1 && val >= txt[mid+1].sym->value)
			bot = mid;
		else
			return mid;
	}
	return -1;
}

/*
 * Find data symbol containing addr; binary search assumes data array is sorted by addr
 */
static int
srchdata(uvlong addr)
{
	uvlong val;
	int top, bot, mid;
	Sym *sp;

	bot = 0;
	top = nglob;
	val = addr;
	for(mid = (bot+top)/2; mid < top; mid = (bot+top)/2) {
		sp = globals[mid];
		if(val < sp->value)
			top = mid;
		else if(mid < nglob-1 && val >= globals[mid+1]->value)
			bot = mid;
		else
			return mid;
	}
	return -1;
}

/*
 * Find symbol containing val in specified search space
 * There is a special case when a value falls beyond the end
 * of the text segment; if the search space is CTEXT, that value
 * (usually etext) is returned.  If the search space is CANY, symbols in the
 * data space are searched for a match.
 */
int
findsym(uvlong val, int type, Symbol *s)
{
	int i;

	if(buildtbls() == 0)
		return 0;

	if(type == CTEXT || type == CANY) {
		i = srchtext(val);
		if(i >= 0) {
			if(type == CTEXT || i != ntxt-1) {
				fillsym(txt[i].sym, s);
				s->handle = (void *) &txt[i];
				s->index = i;
				return 1;
			}
		}
	}
	if(type == CDATA || type == CANY) {
		i = srchdata(val);
		if(i >= 0) {
			fillsym(globals[i], s);
			s->index = i;
			return 1;
		}
	}
	return 0;
}

/*
 *	Find the start and end address of the function containing addr
 */
int
fnbound(uvlong addr, uvlong *bounds)
{
	int i;

	if(buildtbls() == 0)
		return 0;

	i = srchtext(addr);
	if(0 <= i && i < ntxt-1) {
		bounds[0] = txt[i].sym->value;
		bounds[1] = txt[i+1].sym->value;
		return 1;
	}
	return 0;
}

/*
 * get the ith local symbol for a function
 * the input symbol table is reverse ordered, so we reverse
 * accesses here to maintain approx. parameter ordering in a stack trace.
 */
int
localsym(Symbol *s, int index)
{
	Txtsym *tp;

	if(s == 0 || index < 0)
		return 0;
	if(buildtbls() == 0)
		return 0;

	tp = (Txtsym *)s->handle;
	if(tp && tp->locals && index < tp->n) {
		fillsym(tp->locals[tp->n-index-1], s);	/* reverse */
		s->handle = (void *)tp;
		s->index = index;
		return 1;
	}
	return 0;
}

/*
 * get the ith global symbol
 */
int
globalsym(Symbol *s, int index)
{
	if(s == 0)
		return 0;
	if(buildtbls() == 0)
		return 0;

	if(index >=0 && index < nglob) {
		fillsym(globals[index], s);
		s->index = index;
		return 1;
	}
	return 0;
}

/*
 *	find the pc given a file name and line offset into it.
 */
uvlong
file2pc(char *file, long line)
{
	File *fp;
	long i;
	uvlong pc, start, end;
	short *name;

	if(buildtbls() == 0 || files == 0)
		return ~0;
	name = encfname(file);
	if(name == 0) {			/* encode the file name */
		werrstr("file %s not found", file);
		return ~0;
	} 
		/* find this history stack */
	for(i = 0, fp = files; i < nfiles; i++, fp++)
		if (hline(fp, name, &line))
			break;
	free(name);
	if(i >= nfiles) {
		werrstr("line %ld in file %s not found", line, file);
		return ~0;
	}
	start = fp->addr;		/* first text addr this file */
	if(i < nfiles-1)
		end = (fp+1)->addr;	/* first text addr next file */
	else
		end = 0;		/* last file in load module */
	/*
	 * At this point, line contains the offset into the file.
	 * run the state machine to locate the pc closest to that value.
	 */
	if(debug)
		print("find pc for %ld - between: %llux and %llux\n", line, start, end);
	pc = line2addr(line, start, end);
	if(pc == ~0) {
		werrstr("line %ld not in file %s", line, file);
		return ~0;
	}
	return pc;
}

/*
 *	search for a path component index
 */
static int
pathcomp(char *s, int n)
{
	int i;

	for(i = 0; i <= fmax; i++)
		if(fnames[i] && strncmp(s, fnames[i]->name, n) == 0)
			return i;
	return -1;
}

/*
 *	Encode a char file name as a sequence of short indices
 *	into the file name dictionary.
 */
static short*
encfname(char *file)
{
	int i, j;
	char *cp, *cp2;
	short *dest;

	if(*file == '/')	/* always check first '/' */
		cp2 = file+1;
	else {
		cp2 = strchr(file, '/');
		if(!cp2)
			cp2 = strchr(file, 0);
	}
	cp = file;
	dest = 0;
	for(i = 0; *cp; i++) {
		j = pathcomp(cp, cp2-cp);
		if(j < 0)
			return 0;	/* not found */
		dest = realloc(dest, (i+1)*sizeof(short));
		dest[i] = j;
		cp = cp2;
		while(*cp == '/')	/* skip embedded '/'s */
			cp++;
		cp2 = strchr(cp, '/');
		if(!cp2)
			cp2 = strchr(cp, 0);
	}
	dest = realloc(dest, (i+1)*sizeof(short));
	dest[i] = 0;
	return dest;
}

/*
 *	Search a history stack for a matching file name accumulating
 *	the size of intervening files in the stack.
 */
static int
hline(File *fp, short *name, long *line)
{
	Hist *hp;
	int offset, depth;
	long ln;

	for(hp = fp->hist; hp->name; hp++)		/* find name in stack */
		if(hp->name[1] || hp->name[2]) {
			if(hcomp(hp, name))
				break;
		}
	if(!hp->name)		/* match not found */
		return 0;
	if(debug)
		printhist("hline found ... ", hp, 1);
	/*
	 * unwind the stack until empty or we hit an entry beyond our line
	 */
	ln = *line;
	offset = hp->line-1;
	depth = 1;
	for(hp++; depth && hp->name; hp++) {
		if(debug)
			printhist("hline inspect ... ", hp, 1);
		if(hp->name[1] || hp->name[2]) {
			if(hp->offset){			/* Z record */
				offset = 0;
				if(hcomp(hp, name)) {
					if(*line <= hp->offset)
						break;
					ln = *line+hp->line-hp->offset;
					depth = 1;	/* implicit pop */
				} else
					depth = 2;	/* implicit push */
			} else if(depth == 1 && ln < hp->line-offset)
					break;		/* Beyond our line */
			else if(depth++ == 1)		/* push	*/
				offset -= hp->line;
		} else if(--depth == 1)		/* pop */
			offset += hp->line;	
	}
	*line = ln+offset;
	return 1;
}

/*
 *	compare two encoded file names
 */
static int
hcomp(Hist *hp, short *sp)
{
	uchar *cp;
	int i, j;
	short *s;

	cp = (uchar *)hp->name;
	s = sp;
	if (*s == 0)
		return 0;
	for (i = 1; j = (cp[i]<<8)|cp[i+1]; i += 2) {
		if(j == 0)
			break;
		if(*s == j)
			s++;
		else
			s = sp;
	}
	return *s == 0;
}

/*
 *	Convert a pc to a "file:line {file:line}" string.
 */
long
fileline(char *str, int n, uvlong dot)
{
	long line, top, bot, mid;
	File *f;

	*str = 0;
	if(buildtbls() == 0)
		return 0;
		/* binary search assumes file list is sorted by addr */
	bot = 0;
	top = nfiles;
	for (mid = (bot+top)/2; mid < top; mid = (bot+top)/2) {
		f = &files[mid];
		if(dot < f->addr)
			top = mid;
		else if(mid < nfiles-1 && dot >= (f+1)->addr)
			bot = mid;
		else {
			line = pc2line(dot);
			if(line > 0 && fline(str, n, line, f->hist, 0) >= 0)
				return 1;
			break;
		}
	}
	return 0;
}

/*
 *	Convert a line number within a composite file to relative line
 *	number in a source file.  A composite file is the source
 *	file with included files inserted in line.
 */
static int
fline(char *str, int n, long line, Hist *base, Hist **ret)
{
	Hist *start;			/* start of current level */
	Hist *h;			/* current entry */
	long delta;			/* sum of size of files this level */
	int k;

	start = base;
	h = base;
	delta = h->line;
	while(h && h->name && line > h->line) {
		if(h->name[1] || h->name[2]) {
			if(h->offset != 0) {	/* #line Directive */
				delta = h->line-h->offset+1;
				start = h;
				base = h++;
			} else {		/* beginning of File */
				if(start == base)
					start = h++;
				else {
					k = fline(str, n, line, start, &h);
					if(k <= 0)
						return k;
				}
			}
		} else {
			if(start == base && ret) {	/* end of recursion level */
				*ret = h;
				return 1;
			} else {			/* end of included file */
				delta += h->line-start->line;
				h++;
				start = base;
			}
		}
	}
	if(!h)
		return -1;
	if(start != base)
		line = line-start->line+1;
	else
		line = line-delta+1;
	if(!h->name)
		strncpy(str, "<eof>", n);
	else {
		k = fileelem(fnames, (uchar*)start->name, str, n);
		if(k+8 < n)
			sprint(str+k, ":%ld", line);
	}
/**********Remove comments for complete back-trace of include sequence
 *	if(start != base) {
 *		k = strlen(str);
 *		if(k+2 < n) {
 *			str[k++] = ' ';
 *			str[k++] = '{';
 *		}
 *		k += fileelem(fnames, (uchar*) base->name, str+k, n-k);
 *		if(k+10 < n)
 *			sprint(str+k, ":%ld}", start->line-delta);
 *	}
 ********************/
	return 0;
}

/*
 *	convert an encoded file name to a string.
 */
int
fileelem(Sym **fp, uchar *cp, char *buf, int n)
{
	int i, j;
	char *c, *bp, *end;

	bp = buf;
	end = buf+n-1;
	for(i = 1; j = (cp[i]<<8)|cp[i+1]; i+=2){
		c = fp[j]->name;
		if(bp != buf && bp[-1] != '/' && bp < end)
			*bp++ = '/';
		while(bp < end && *c)
			*bp++ = *c++;
	}
	*bp = 0;
	i =  bp-buf;
	if(i > 1) {
		cleanname(buf);
		i = strlen(buf);
	}
	return i;
}

/*
 *	compare the values of two symbol table entries.
 */
static int
symcomp(void *a, void *b)
{
	int i;

	i = (*(Sym**)a)->value - (*(Sym**)b)->value;
	if (i)
		return i;
	return strcmp((*(Sym**)a)->name, (*(Sym**)b)->name);
}

/*
 *	compare the values of the symbols referenced by two text table entries
 */
static int
txtcomp(void *a, void *b)
{
	return ((Txtsym*)a)->sym->value - ((Txtsym*)b)->sym->value;
}

/*
 *	compare the values of the symbols referenced by two file table entries
 */
static int
filecomp(void *a, void *b)
{
	return ((File*)a)->addr - ((File*)b)->addr;
}

/*
 *	fill an interface Symbol structure from a symbol table entry
 */
static void
fillsym(Sym *sp, Symbol *s)
{
	s->type = sp->type;
	s->value = sp->value;
	s->name = sp->name;
	s->index = 0;
	switch(sp->type) {
	case 'b':
	case 'B':
	case 'D':
	case 'd':
		s->class = CDATA;
		break;
	case 't':
	case 'T':
	case 'l':
	case 'L':
		s->class = CTEXT;
		break;
	case 'a':
		s->class = CAUTO;
		break;
	case 'p':
		s->class = CPARAM;
		break;
	case 'm':
		s->class = CSTAB;
		break;
	default:
		s->class = CNONE;
		break;
	}
	s->handle = 0;
}

/*
 *	find the stack frame, given the pc
 */
uvlong
pc2sp(uvlong pc)
{
	uchar *c, u;
	uvlong currpc, currsp;

	if(spoff == 0)
		return ~0;
	currsp = 0;
	currpc = txtstart - mach->pcquant;

	if(pc<currpc || pc>txtend)
		return ~0;
	for(c = spoff; c < spoffend; c++) {
		if (currpc >= pc)
			return currsp;
		u = *c;
		if (u == 0) {
			currsp += (c[1]<<24)|(c[2]<<16)|(c[3]<<8)|c[4];
			c += 4;
		}
		else if (u < 65)
			currsp += 4*u;
		else if (u < 129)
			currsp -= 4*(u-64);
		else 
			currpc += mach->pcquant*(u-129);
		currpc += mach->pcquant;
	}
	return ~0;
}

/*
 *	find the source file line number for a given value of the pc
 */
long
pc2line(uvlong pc)
{
	uchar *c, u;
	uvlong currpc;
	long currline;

	if(pcline == 0)
		return -1;
	currline = 0;
	currpc = txtstart-mach->pcquant;
	if(pc<currpc || pc>txtend)
		return ~0;

	for(c = pcline; c < pclineend; c++) {
		if(currpc >= pc)
			return currline;
		u = *c;
		if(u == 0) {
			currline += (c[1]<<24)|(c[2]<<16)|(c[3]<<8)|c[4];
			c += 4;
		}
		else if(u < 65)
			currline += u;
		else if(u < 129)
			currline -= (u-64);
		else 
			currpc += mach->pcquant*(u-129);
		currpc += mach->pcquant;
	}
	return ~0;
}

/*
 *	find the pc associated with a line number
 *	basepc and endpc are text addresses bounding the search.
 *	if endpc == 0, the end of the table is used (i.e., no upper bound).
 *	usually, basepc and endpc contain the first text address in
 *	a file and the first text address in the following file, respectively.
 */
uvlong
line2addr(long line, uvlong basepc, uvlong endpc)
{
	uchar *c,  u;
	uvlong currpc, pc;
	long currline;
	long delta, d;
	int found;

	if(pcline == 0 || line == 0)
		return ~0;

	currline = 0;
	currpc = txtstart-mach->pcquant;
	pc = ~0;
	found = 0;
	delta = HUGEINT;

	for(c = pcline; c < pclineend; c++) {
		if(endpc && currpc >= endpc)	/* end of file of interest */
			break;
		if(currpc >= basepc) {		/* proper file */
			if(currline >= line) {
				d = currline-line;
				found = 1;
			} else
				d = line-currline;
			if(d < delta) {
				delta = d;
				pc = currpc;
			}
		}
		u = *c;
		if(u == 0) {
			currline += (c[1]<<24)|(c[2]<<16)|(c[3]<<8)|c[4];
			c += 4;
		}
		else if(u < 65)
			currline += u;
		else if(u < 129)
			currline -= (u-64);
		else 
			currpc += mach->pcquant*(u-129);
		currpc += mach->pcquant;
	}
	if(found)
		return pc;
	return ~0;
}

/*
 *	Print a history stack (debug). if count is 0, prints the whole stack
 */
static void
printhist(char *msg, Hist *hp, int count)
{
	int i;
	uchar *cp;
	char buf[128];

	i = 0;
	while(hp->name) {
		if(count && ++i > count)
			break;
		print("%s Line: %lx (%ld)  Offset: %lx (%ld)  Name: ", msg,
			hp->line, hp->line, hp->offset, hp->offset);
		for(cp = (uchar *)hp->name+1; (*cp<<8)|cp[1]; cp += 2) {
			if (cp != (uchar *)hp->name+1)
				print("/");
			print("%x", (*cp<<8)|cp[1]);
		}
		fileelem(fnames, (uchar *) hp->name, buf, sizeof(buf));
		print(" (%s)\n", buf);
		hp++;
	}
}

#ifdef DEBUG
/*
 *	print the history stack for a file. (debug only)
 *	if (name == 0) => print all history stacks.
 */
void
dumphist(char *name)
{
	int i;
	File *f;
	short *fname;

	if(buildtbls() == 0)
		return;
	if(name)
		fname = encfname(name);
	for(i = 0, f = files; i < nfiles; i++, f++)
		if(fname == 0 || hcomp(f->hist, fname))
			printhist("> ", f->hist, f->n);

	if(fname)
		free(fname);
}
#endif