src/cmd/ld/pcln.c - go - Git at Google

 // Copyright 2013 The Go Authors.  All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 #include	<u.h>
 #include	<libc.h>
 #include	<bio.h>
 #include	<link.h>
 #include	"lib.h"
 #include	"../../runtime/funcdata.h"

 static void
 addvarint(Pcdata *d, uint32 val)
 {
 	int32 n;
 	uint32 v;
 	uchar *p;

 	n = 0;
 	for(v = val; v >= 0x80; v >>= 7)
 		n++;
 	n++;

 	if(d->n + n > d->m) {
 		d->m = (d->n + n)*2;
 		d->p = erealloc(d->p, d->m);
 	}

 	p = d->p + d->n;
 	for(v = val; v >= 0x80; v >>= 7)
 		*p++ = v | 0x80;
 	*p = v;
 	d->n += n;
 }

 static int32
 addpctab(LSym *ftab, int32 off, Pcdata *d)
 {
 	int32 start;

 	start = ftab->np;
 	symgrow(ctxt, ftab, start + d->n);
 	memmove(ftab->p + start, d->p, d->n);

 	return setuint32(ctxt, ftab, off, start);
 }

 static int32
 ftabaddstring(LSym *ftab, char *s)
 {
 	int32 n, start;

 	n = strlen(s)+1;
 	start = ftab->np;
 	symgrow(ctxt, ftab, start+n+1);
 	strcpy((char*)ftab->p + start, s);
 	return start;
 }

 static void
 renumberfiles(Link *ctxt, LSym **files, int nfiles, Pcdata *d)
 {
 	int i;
 	LSym *f;
 	Pcdata out;
 	Pciter it;
 	uint32 v;
 	int32 oldval, newval, val, dv;

 	// Give files numbers.
 	for(i=0; i<nfiles; i++) {
 		f = files[i];
 		if(f->type != SFILEPATH) {
 			f->value = ++ctxt->nhistfile;
 			f->type = SFILEPATH;
 			f->next = ctxt->filesyms;
 			ctxt->filesyms = f;
 		}
 	}

 	newval = -1;
 	memset(&out, 0, sizeof out);

 	for(pciterinit(ctxt, &it, d); !it.done; pciternext(&it)) {
 		// value delta
 		oldval = it.value;
 		if(oldval == -1)
 			val = -1;
 		else {
 			if(oldval < 0 || oldval >= nfiles)
 				sysfatal("bad pcdata %d", oldval);
 			val = files[oldval]->value;
 		}
 		dv = val - newval;
 		newval = val;
 		v = ((uint32)dv<<1) ^ (uint32)(int32)(dv>>31);
 		addvarint(&out, v);

 		// pc delta
 		addvarint(&out, (it.nextpc - it.pc) / it.pcscale);
 	}

 	// terminating value delta
 	addvarint(&out, 0);

 	free(d->p);
 	*d = out;
 }

 static int
 container(LSym *s)
 {
 	// We want to generate func table entries only for the "lowest level" symbols,
 	// not containers of subsymbols.
 	if(s != nil && s->sub != nil)
 		return 1;
 	return 0;
 }

 // pclntab initializes the pclntab symbol with
 // runtime function and file name information.
 void
 pclntab(void)
 {
 	int32 i, nfunc, start, funcstart;
 	LSym *ftab, *s, *last;
 	int32 off, end, frameptrsize;
 	int64 funcdata_bytes;
 	Pcln *pcln;
 	Pciter it;
 	static Pcln zpcln;

 	funcdata_bytes = 0;
 	ftab = linklookup(ctxt, "runtime.pclntab", 0);
 	ftab->type = SPCLNTAB;
 	ftab->reachable = 1;

 	// See golang.org/s/go12symtab for the format. Briefly:
 	//	8-byte header
 	//	nfunc [thearch.ptrsize bytes]
 	//	function table, alternating PC and offset to func struct [each entry thearch.ptrsize bytes]
 	//	end PC [thearch.ptrsize bytes]
 	//	offset to file table [4 bytes]
 	nfunc = 0;
 	for(ctxt->cursym = ctxt->textp; ctxt->cursym != nil; ctxt->cursym = ctxt->cursym->next) {
 		if(!container(ctxt->cursym))
 			nfunc++;
 	}
 	symgrow(ctxt, ftab, 8+thearch.ptrsize+nfunc*2*thearch.ptrsize+thearch.ptrsize+4);
 	setuint32(ctxt, ftab, 0, 0xfffffffb);
 	setuint8(ctxt, ftab, 6, thearch.minlc);
 	setuint8(ctxt, ftab, 7, thearch.ptrsize);
 	setuintxx(ctxt, ftab, 8, nfunc, thearch.ptrsize);

 	nfunc = 0;
 	last = nil;
 	for(ctxt->cursym = ctxt->textp; ctxt->cursym != nil; ctxt->cursym = ctxt->cursym->next) {
 		last = ctxt->cursym;
 		if(container(ctxt->cursym))
 			continue;
 		pcln = ctxt->cursym->pcln;
 		if(pcln == nil)
 			pcln = &zpcln;

 		funcstart = ftab->np;
 		funcstart += -ftab->np & (thearch.ptrsize-1);

 		setaddr(ctxt, ftab, 8+thearch.ptrsize+nfunc*2*thearch.ptrsize, ctxt->cursym);
 		setuintxx(ctxt, ftab, 8+thearch.ptrsize+nfunc*2*thearch.ptrsize+thearch.ptrsize, funcstart, thearch.ptrsize);

 		// fixed size of struct, checked below
 		off = funcstart;
 		end = funcstart + thearch.ptrsize + 3*4 + 5*4 + pcln->npcdata*4 + pcln->nfuncdata*thearch.ptrsize;
 		if(pcln->nfuncdata > 0 && (end&(thearch.ptrsize-1)))
 			end += 4;
 		symgrow(ctxt, ftab, end);

 		// entry uintptr
 		off = setaddr(ctxt, ftab, off, ctxt->cursym);

 		// name int32
 		off = setuint32(ctxt, ftab, off, ftabaddstring(ftab, ctxt->cursym->name));

 		// args int32
 		// TODO: Move into funcinfo.
 		off = setuint32(ctxt, ftab, off, ctxt->cursym->args);

 		// frame int32
 		// TODO: Remove entirely. The pcsp table is more precise.
 		// This is only used by a fallback case during stack walking
 		// when a called function doesn't have argument information.
 		// We need to make sure everything has argument information
 		// and then remove this.
 		frameptrsize = thearch.ptrsize;
 		if(ctxt->cursym->leaf)
 			frameptrsize = 0;
 		off = setuint32(ctxt, ftab, off, ctxt->cursym->locals + frameptrsize);

 		if(pcln != &zpcln) {
 			renumberfiles(ctxt, pcln->file, pcln->nfile, &pcln->pcfile);
 			if(0) {
 				// Sanity check the new numbering
 				for(pciterinit(ctxt, &it, &pcln->pcfile); !it.done; pciternext(&it)) {
 					if(it.value < 1 || it.value > ctxt->nhistfile) {
 						diag("bad file number in pcfile: %d not in range [1, %d]\n", it.value, ctxt->nhistfile);
 						errorexit();
 					}
 				}
 			}
 		}

 		// pcdata
 		off = addpctab(ftab, off, &pcln->pcsp);
 		off = addpctab(ftab, off, &pcln->pcfile);
 		off = addpctab(ftab, off, &pcln->pcline);
 		off = setuint32(ctxt, ftab, off, pcln->npcdata);
 		off = setuint32(ctxt, ftab, off, pcln->nfuncdata);
 		for(i=0; i<pcln->npcdata; i++)
 			off = addpctab(ftab, off, &pcln->pcdata[i]);

 		// funcdata, must be pointer-aligned and we're only int32-aligned.
 		// Missing funcdata will be 0 (nil pointer).
 		if(pcln->nfuncdata > 0) {
 			if(off&(thearch.ptrsize-1))
 				off += 4;
 			for(i=0; i<pcln->nfuncdata; i++) {
 				if(pcln->funcdata[i] == nil)
 					setuintxx(ctxt, ftab, off+thearch.ptrsize*i, pcln->funcdataoff[i], thearch.ptrsize);
 				else {
 					// TODO: Dedup.
 					funcdata_bytes += pcln->funcdata[i]->size;
 					setaddrplus(ctxt, ftab, off+thearch.ptrsize*i, pcln->funcdata[i], pcln->funcdataoff[i]);
 				}
 			}
 			off += pcln->nfuncdata*thearch.ptrsize;
 		}

 		if(off != end) {
 			diag("bad math in functab: funcstart=%d off=%d but end=%d (npcdata=%d nfuncdata=%d ptrsize=%d)", funcstart, off, end, pcln->npcdata, pcln->nfuncdata, thearch.ptrsize);
 			errorexit();
 		}

 		nfunc++;
 	}
 	// Final entry of table is just end pc.
 	setaddrplus(ctxt, ftab, 8+thearch.ptrsize+nfunc*2*thearch.ptrsize, last, last->size);

 	// Start file table.
 	start = ftab->np;
 	start += -ftab->np & (thearch.ptrsize-1);
 	setuint32(ctxt, ftab, 8+thearch.ptrsize+nfunc*2*thearch.ptrsize+thearch.ptrsize, start);

 	symgrow(ctxt, ftab, start+(ctxt->nhistfile+1)*4);
 	setuint32(ctxt, ftab, start, ctxt->nhistfile);
 	for(s = ctxt->filesyms; s != nil; s = s->next)
 		setuint32(ctxt, ftab, start + s->value*4, ftabaddstring(ftab, s->name));

 	ftab->size = ftab->np;

 	if(debug['v'])
 		Bprint(&bso, "%5.2f pclntab=%lld bytes, funcdata total %lld bytes\n", cputime(), (vlong)ftab->size, (vlong)funcdata_bytes);
 }

 enum {
 	BUCKETSIZE = 256*MINFUNC,
 	SUBBUCKETS = 16,
 	SUBBUCKETSIZE = BUCKETSIZE/SUBBUCKETS,
 	NOIDX = 0x7fffffff
 };

 // findfunctab generates a lookup table to quickly find the containing
 // function for a pc.  See src/runtime/symtab.go:findfunc for details.
 void
 findfunctab(void)
 {
 	LSym *t, *s, *e;
 	int32 idx, i, j, nbuckets, n, base;
 	vlong min, max, p, q;
 	int32 *indexes;

 	t = linklookup(ctxt, "runtime.findfunctab", 0);
 	t->type = SRODATA;
 	t->reachable = 1;

 	// find min and max address
 	min = ctxt->textp->value;
 	max = 0;
 	for(s = ctxt->textp; s != nil; s = s->next)
 		max = s->value + s->size;

 	// for each subbucket, compute the minimum of all symbol indexes
 	// that map to that subbucket.
 	n = (max-min+SUBBUCKETSIZE-1)/SUBBUCKETSIZE;
 	indexes = (int32*)malloc(n*4);
 	if(indexes == nil) {
 		diag("out of memory");
 		errorexit();
 	}
 	for(i = 0; i < n; i++)
 		indexes[i] = NOIDX;
 	idx = 0;
 	for(s = ctxt->textp; s != nil; s = s->next) {
 		if(container(s))
 			continue;
 		p = s->value;
 		e = s->next;
 		while(container(e))
 			e = e->next;
 		if(e != nil)
 			q = e->value;
 		else
 			q = max;

 		//print("%d: [%lld %lld] %s\n", idx, p, q, s->name);
 		for(; p < q; p += SUBBUCKETSIZE) {
 			i = (p - min) / SUBBUCKETSIZE;
 			if(indexes[i] > idx)
 				indexes[i] = idx;
 		}
 		i = (q - 1 - min) / SUBBUCKETSIZE;
 		if(indexes[i] > idx)
 			indexes[i] = idx;
 		idx++;
 	}

 	// allocate table
 	nbuckets = (max-min+BUCKETSIZE-1)/BUCKETSIZE;
 	symgrow(ctxt, t, 4*nbuckets + n);

 	// fill in table
 	for(i = 0; i < nbuckets; i++) {
 		base = indexes[i*SUBBUCKETS];
 		if(base == NOIDX)
 			diag("hole in findfunctab");
 		setuint32(ctxt, t, i*(4+SUBBUCKETS), base);
 		for(j = 0; j < SUBBUCKETS && i*SUBBUCKETS+j < n; j++) {
 			idx = indexes[i*SUBBUCKETS+j];
 			if(idx == NOIDX)
 				diag("hole in findfunctab");
 			if(idx - base >= 256) {
 				diag("too many functions in a findfunc bucket! %d/%d %d %d", i, nbuckets, j, idx-base);
 			}
 			setuint8(ctxt, t, i*(4+SUBBUCKETS)+4+j, idx-base);
 		}
 	}
 	free(indexes);
 }
	// Copyright 2013 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	#include <u.h>
	#include <libc.h>
	#include <bio.h>
	#include <link.h>
	#include "lib.h"
	#include "../../runtime/funcdata.h"

	static void
	addvarint(Pcdata *d, uint32 val)
	{
	int32 n;
	uint32 v;
	uchar *p;

	n = 0;
	for(v = val; v >= 0x80; v >>= 7)
	n++;
	n++;

	if(d->n + n > d->m) {
	d->m = (d->n + n)*2;
	d->p = erealloc(d->p, d->m);
	}

	p = d->p + d->n;
	for(v = val; v >= 0x80; v >>= 7)
	*p++ = v \| 0x80;
	*p = v;
	d->n += n;
	}

	static int32
	addpctab(LSym ftab, int32 off, Pcdata d)
	{
	int32 start;

	start = ftab->np;
	symgrow(ctxt, ftab, start + d->n);
	memmove(ftab->p + start, d->p, d->n);

	return setuint32(ctxt, ftab, off, start);
	}

	static int32
	ftabaddstring(LSym ftab, char s)
	{
	int32 n, start;

	n = strlen(s)+1;
	start = ftab->np;
	symgrow(ctxt, ftab, start+n+1);
	strcpy((char*)ftab->p + start, s);
	return start;
	}

	static void
	renumberfiles(Link ctxt, LSym files, int nfiles, Pcdata d)
	{
	int i;
	LSym *f;
	Pcdata out;
	Pciter it;
	uint32 v;
	int32 oldval, newval, val, dv;

	// Give files numbers.
	for(i=0; i<nfiles; i++) {
	f = files[i];
	if(f->type != SFILEPATH) {
	f->value = ++ctxt->nhistfile;
	f->type = SFILEPATH;
	f->next = ctxt->filesyms;
	ctxt->filesyms = f;
	}
	}

	newval = -1;
	memset(&out, 0, sizeof out);

	for(pciterinit(ctxt, &it, d); !it.done; pciternext(&it)) {
	// value delta
	oldval = it.value;
	if(oldval == -1)
	val = -1;
	else {
	if(oldval < 0 \|\| oldval >= nfiles)
	sysfatal("bad pcdata %d", oldval);
	val = files[oldval]->value;
	}
	dv = val - newval;
	newval = val;
	v = ((uint32)dv<<1) ^ (uint32)(int32)(dv>>31);
	addvarint(&out, v);

	// pc delta
	addvarint(&out, (it.nextpc - it.pc) / it.pcscale);
	}

	// terminating value delta
	addvarint(&out, 0);

	free(d->p);
	*d = out;
	}

	static int
	container(LSym *s)
	{
	// We want to generate func table entries only for the "lowest level" symbols,
	// not containers of subsymbols.
	if(s != nil && s->sub != nil)
	return 1;
	return 0;
	}

	// pclntab initializes the pclntab symbol with
	// runtime function and file name information.
	void
	pclntab(void)
	{
	int32 i, nfunc, start, funcstart;
	LSym ftab, s, *last;
	int32 off, end, frameptrsize;
	int64 funcdata_bytes;
	Pcln *pcln;
	Pciter it;
	static Pcln zpcln;

	funcdata_bytes = 0;
	ftab = linklookup(ctxt, "runtime.pclntab", 0);
	ftab->type = SPCLNTAB;
	ftab->reachable = 1;

	// See golang.org/s/go12symtab for the format. Briefly:
	// 8-byte header
	// nfunc [thearch.ptrsize bytes]
	// function table, alternating PC and offset to func struct [each entry thearch.ptrsize bytes]
	// end PC [thearch.ptrsize bytes]
	// offset to file table [4 bytes]
	nfunc = 0;
	for(ctxt->cursym = ctxt->textp; ctxt->cursym != nil; ctxt->cursym = ctxt->cursym->next) {
	if(!container(ctxt->cursym))
	nfunc++;
	}
	symgrow(ctxt, ftab, 8+thearch.ptrsize+nfunc2thearch.ptrsize+thearch.ptrsize+4);
	setuint32(ctxt, ftab, 0, 0xfffffffb);
	setuint8(ctxt, ftab, 6, thearch.minlc);
	setuint8(ctxt, ftab, 7, thearch.ptrsize);
	setuintxx(ctxt, ftab, 8, nfunc, thearch.ptrsize);

	nfunc = 0;
	last = nil;
	for(ctxt->cursym = ctxt->textp; ctxt->cursym != nil; ctxt->cursym = ctxt->cursym->next) {
	last = ctxt->cursym;
	if(container(ctxt->cursym))
	continue;
	pcln = ctxt->cursym->pcln;
	if(pcln == nil)
	pcln = &zpcln;

	funcstart = ftab->np;
	funcstart += -ftab->np & (thearch.ptrsize-1);

	setaddr(ctxt, ftab, 8+thearch.ptrsize+nfunc2thearch.ptrsize, ctxt->cursym);
	setuintxx(ctxt, ftab, 8+thearch.ptrsize+nfunc2thearch.ptrsize+thearch.ptrsize, funcstart, thearch.ptrsize);

	// fixed size of struct, checked below
	off = funcstart;
	end = funcstart + thearch.ptrsize + 34 + 54 + pcln->npcdata4 + pcln->nfuncdatathearch.ptrsize;
	if(pcln->nfuncdata > 0 && (end&(thearch.ptrsize-1)))
	end += 4;
	symgrow(ctxt, ftab, end);

	// entry uintptr
	off = setaddr(ctxt, ftab, off, ctxt->cursym);

	// name int32
	off = setuint32(ctxt, ftab, off, ftabaddstring(ftab, ctxt->cursym->name));

	// args int32
	// TODO: Move into funcinfo.
	off = setuint32(ctxt, ftab, off, ctxt->cursym->args);

	// frame int32
	// TODO: Remove entirely. The pcsp table is more precise.
	// This is only used by a fallback case during stack walking
	// when a called function doesn't have argument information.
	// We need to make sure everything has argument information
	// and then remove this.
	frameptrsize = thearch.ptrsize;
	if(ctxt->cursym->leaf)
	frameptrsize = 0;
	off = setuint32(ctxt, ftab, off, ctxt->cursym->locals + frameptrsize);

	if(pcln != &zpcln) {
	renumberfiles(ctxt, pcln->file, pcln->nfile, &pcln->pcfile);
	if(0) {
	// Sanity check the new numbering
	for(pciterinit(ctxt, &it, &pcln->pcfile); !it.done; pciternext(&it)) {
	if(it.value < 1 \|\| it.value > ctxt->nhistfile) {
	diag("bad file number in pcfile: %d not in range [1, %d]\n", it.value, ctxt->nhistfile);
	errorexit();
	}
	}
	}
	}

	// pcdata
	off = addpctab(ftab, off, &pcln->pcsp);
	off = addpctab(ftab, off, &pcln->pcfile);
	off = addpctab(ftab, off, &pcln->pcline);
	off = setuint32(ctxt, ftab, off, pcln->npcdata);
	off = setuint32(ctxt, ftab, off, pcln->nfuncdata);
	for(i=0; i<pcln->npcdata; i++)
	off = addpctab(ftab, off, &pcln->pcdata[i]);

	// funcdata, must be pointer-aligned and we're only int32-aligned.
	// Missing funcdata will be 0 (nil pointer).
	if(pcln->nfuncdata > 0) {
	if(off&(thearch.ptrsize-1))
	off += 4;
	for(i=0; i<pcln->nfuncdata; i++) {
	if(pcln->funcdata[i] == nil)
	setuintxx(ctxt, ftab, off+thearch.ptrsize*i, pcln->funcdataoff[i], thearch.ptrsize);
	else {
	// TODO: Dedup.
	funcdata_bytes += pcln->funcdata[i]->size;
	setaddrplus(ctxt, ftab, off+thearch.ptrsize*i, pcln->funcdata[i], pcln->funcdataoff[i]);
	}
	}
	off += pcln->nfuncdata*thearch.ptrsize;
	}

	if(off != end) {
	diag("bad math in functab: funcstart=%d off=%d but end=%d (npcdata=%d nfuncdata=%d ptrsize=%d)", funcstart, off, end, pcln->npcdata, pcln->nfuncdata, thearch.ptrsize);
	errorexit();
	}

	nfunc++;
	}
	// Final entry of table is just end pc.
	setaddrplus(ctxt, ftab, 8+thearch.ptrsize+nfunc2thearch.ptrsize, last, last->size);

	// Start file table.
	start = ftab->np;
	start += -ftab->np & (thearch.ptrsize-1);
	setuint32(ctxt, ftab, 8+thearch.ptrsize+nfunc2thearch.ptrsize+thearch.ptrsize, start);

	symgrow(ctxt, ftab, start+(ctxt->nhistfile+1)*4);
	setuint32(ctxt, ftab, start, ctxt->nhistfile);
	for(s = ctxt->filesyms; s != nil; s = s->next)
	setuint32(ctxt, ftab, start + s->value*4, ftabaddstring(ftab, s->name));

	ftab->size = ftab->np;

	if(debug['v'])
	Bprint(&bso, "%5.2f pclntab=%lld bytes, funcdata total %lld bytes\n", cputime(), (vlong)ftab->size, (vlong)funcdata_bytes);
	}

	enum {
	BUCKETSIZE = 256*MINFUNC,
	SUBBUCKETS = 16,
	SUBBUCKETSIZE = BUCKETSIZE/SUBBUCKETS,
	NOIDX = 0x7fffffff
	};

	// findfunctab generates a lookup table to quickly find the containing
	// function for a pc. See src/runtime/symtab.go:findfunc for details.
	void
	findfunctab(void)
	{
	LSym t, s, *e;
	int32 idx, i, j, nbuckets, n, base;
	vlong min, max, p, q;
	int32 *indexes;

	t = linklookup(ctxt, "runtime.findfunctab", 0);
	t->type = SRODATA;
	t->reachable = 1;

	// find min and max address
	min = ctxt->textp->value;
	max = 0;
	for(s = ctxt->textp; s != nil; s = s->next)
	max = s->value + s->size;

	// for each subbucket, compute the minimum of all symbol indexes
	// that map to that subbucket.
	n = (max-min+SUBBUCKETSIZE-1)/SUBBUCKETSIZE;
	indexes = (int32)malloc(n4);
	if(indexes == nil) {
	diag("out of memory");
	errorexit();
	}
	for(i = 0; i < n; i++)
	indexes[i] = NOIDX;
	idx = 0;
	for(s = ctxt->textp; s != nil; s = s->next) {
	if(container(s))
	continue;
	p = s->value;
	e = s->next;
	while(container(e))
	e = e->next;
	if(e != nil)
	q = e->value;
	else
	q = max;

	//print("%d: [%lld %lld] %s\n", idx, p, q, s->name);
	for(; p < q; p += SUBBUCKETSIZE) {
	i = (p - min) / SUBBUCKETSIZE;
	if(indexes[i] > idx)
	indexes[i] = idx;
	}
	i = (q - 1 - min) / SUBBUCKETSIZE;
	if(indexes[i] > idx)
	indexes[i] = idx;
	idx++;
	}

	// allocate table
	nbuckets = (max-min+BUCKETSIZE-1)/BUCKETSIZE;
	symgrow(ctxt, t, 4*nbuckets + n);

	// fill in table
	for(i = 0; i < nbuckets; i++) {
	base = indexes[i*SUBBUCKETS];
	if(base == NOIDX)
	diag("hole in findfunctab");
	setuint32(ctxt, t, i*(4+SUBBUCKETS), base);
	for(j = 0; j < SUBBUCKETS && i*SUBBUCKETS+j < n; j++) {
	idx = indexes[i*SUBBUCKETS+j];
	if(idx == NOIDX)
	diag("hole in findfunctab");
	if(idx - base >= 256) {
	diag("too many functions in a findfunc bucket! %d/%d %d %d", i, nbuckets, j, idx-base);
	}
	setuint8(ctxt, t, i*(4+SUBBUCKETS)+4+j, idx-base);
	}
	}
	free(indexes);
	}