runtime: faster version of findfunc

Use a lookup table to find the function which contains a pc.  It is
faster than the old binary search.  findfunc is used primarily for
stack copying and garbage collection.

benchmark              old ns/op     new ns/op     delta
BenchmarkStackCopy     294746596     255400980     -13.35%

(findfunc is one of several tasks done by stack copy, the findfunc
time itself is about 2.5x faster.)

The lookup table is built at link time.  The table grows the binary
size by about 0.5% of the text segment.

We impose a lower limit of 16 bytes on any function, which should not
have much of an impact.  (The real constraint required is <=256
functions in every 4096 bytes, but 16 bytes/function is easier to
implement.)

Change-Id: Ic315b7a2c83e1f7203cd2a50e5d21a822e18fdca
Reviewed-on: https://go-review.googlesource.com/2097
Reviewed-by: Russ Cox <rsc@golang.org>

4 files changed, 62 insertions, 1 deletions

diff --git a/src/cmd/ld/data.c b/src/cmd/ld/data.c
index 22843b8948..0f287c202f 100644
--- a/src/cmd/ld/data.c
+++ b/src/cmd/ld/data.c
@@ -1315,7 +1315,10 @@ textaddress(void)
 			sub->value += va;
 		if(sym->size == 0 && sym->sub != S)
 			ctxt->cursym = sym;
-		va += sym->size;
+		if(sym->size < MINFUNC)
+			va += MINFUNC; // spacing required for findfunctab
+		else
+			va += sym->size;
 	}
 	sect->len = va - sect->vaddr;
 }
diff --git a/src/cmd/ld/lib.h b/src/cmd/ld/lib.h
index 17483e0b4c..fd84c8bccb 100644
--- a/src/cmd/ld/lib.h
+++ b/src/cmd/ld/lib.h
@@ -35,6 +35,7 @@
 
 enum {
 	MAXIO		= 8192,
+	MINFUNC		= 16,	// minimum size for a function
 };
 
 typedef struct Segment Segment;
@@ -260,6 +261,7 @@ void	patch(void);
 int	pathchar(void);
 void	pcln(void);
 void	pclntab(void);
+void	findfunctab(void);
 void	putelfsectionsym(LSym* s, int shndx);
 void	putelfsymshndx(vlong sympos, int shndx);
 void	putsymb(LSym *s, char *name, int t, vlong v, vlong size, int ver, LSym *typ);
diff --git a/src/cmd/ld/pcln.c b/src/cmd/ld/pcln.c
index 69671c0fc9..f889b2c3ea 100644
--- a/src/cmd/ld/pcln.c
+++ b/src/cmd/ld/pcln.c
@@ -242,3 +242,58 @@ pclntab(void)
 	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,
+};
+
+// 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;
+	int32 idx, bidx, i, j, nbuckets;
+	vlong min, max;
+
+	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;
+
+	// allocate table
+	nbuckets = (max-min+BUCKETSIZE-1)/BUCKETSIZE;
+	symgrow(ctxt, t, nbuckets * (4+SUBBUCKETS));
+
+	// fill in table
+	s = ctxt->textp;
+	idx = 0;
+	for(i = 0; i < nbuckets; i++) {
+		// Find first function which overlaps this bucket.
+		// Only do leaf symbols; skip symbols which are just containers (sub != nil but outer == nil).
+		while(s != nil && (s->value+s->size <= min + i * BUCKETSIZE || s->sub != nil && s->outer == nil)) {
+			s = s->next;
+			idx++;
+		}
+		// record this function in bucket header
+		setuint32(ctxt, t, i*(4+SUBBUCKETS), idx);
+		bidx = idx;
+
+		// compute SUBBUCKETS deltas
+		for(j = 0; j < SUBBUCKETS; j++) {
+			while(s != nil && (s->value+s->size <= min + i * BUCKETSIZE + j * (BUCKETSIZE/SUBBUCKETS) || s->sub != nil && s->outer == nil)) {
+				s = s->next;
+				idx++;
+			}
+			if(idx - bidx >= 256)
+				diag("too many functions in a findfunc bucket! %d %s", idx-bidx, s->name);
+			setuint8(ctxt, t, i*(4+SUBBUCKETS)+4+j, idx-bidx);
+		}
+	}
+}
diff --git a/src/cmd/ld/pobj.c b/src/cmd/ld/pobj.c
index b86ddfe0fe..8ecd18b817 100644
--- a/src/cmd/ld/pobj.c
+++ b/src/cmd/ld/pobj.c
@@ -187,6 +187,7 @@ main(int argc, char *argv[])
 	gentext();		// trampolines, call stubs, etc.
 	textaddress();
 	pclntab();
+	findfunctab();
 	symtab();
 	dodata();
 	address();