cmd/ld: fix symbol table sorting

runtime: double-check that symbol table is sorted

If the symbol table is unsorted, the binary search in findfunc
will not find its func, which will make stack traces stop early.
When the garbage collector starts using the stack tracer,
that would be a serious problem.

The unsorted symbol addresses came from from two things:

1. The symbols in an ELF object are not necessarily sorted,
   so sort them before adding them to the symbol list.

2. The __i686.get_pc_thunk.bx symbol is present in multiple
   object files and was having its address adjusted multiple
   times, producing an incorrect address in the symbol table.

R=golang-dev, iant
CC=golang-dev
https://golang.org/cl/7440044

1 files changed, 27 insertions, 24 deletions

diff --git a/src/cmd/ld/data.c b/src/cmd/ld/data.c
index 1e0bd2cd0f..6c6b1be433 100644
--- a/src/cmd/ld/data.c
+++ b/src/cmd/ld/data.c
@@ -58,70 +58,73 @@ datcmp(Sym *s1, Sym *s2)
 }
 
 Sym*
-datsort(Sym *l)
+listsort(Sym *l, int (*cmp)(Sym*, Sym*), int off)
 {
 	Sym *l1, *l2, *le;
+	#define NEXT(l) (*(Sym**)((char*)(l)+off))
 
-	if(l == 0 || l->next == 0)
+	if(l == 0 || NEXT(l) == 0)
 		return l;
 
 	l1 = l;
 	l2 = l;
 	for(;;) {
-		l2 = l2->next;
+		l2 = NEXT(l2);
 		if(l2 == 0)
 			break;
-		l2 = l2->next;
+		l2 = NEXT(l2);
 		if(l2 == 0)
 			break;
-		l1 = l1->next;
+		l1 = NEXT(l1);
 	}
 
-	l2 = l1->next;
-	l1->next = 0;
-	l1 = datsort(l);
-	l2 = datsort(l2);
+	l2 = NEXT(l1);
+	NEXT(l1) = 0;
+	l1 = listsort(l, cmp, off);
+	l2 = listsort(l2, cmp, off);
 
 	/* set up lead element */
-	if(datcmp(l1, l2) < 0) {
+	if(cmp(l1, l2) < 0) {
 		l = l1;
-		l1 = l1->next;
+		l1 = NEXT(l1);
 	} else {
 		l = l2;
-		l2 = l2->next;
+		l2 = NEXT(l2);
 	}
 	le = l;
 
 	for(;;) {
 		if(l1 == 0) {
 			while(l2) {
-				le->next = l2;
+				NEXT(le) = l2;
 				le = l2;
-				l2 = l2->next;
+				l2 = NEXT(l2);
 			}
-			le->next = 0;
+			NEXT(le) = 0;
 			break;
 		}
 		if(l2 == 0) {
 			while(l1) {
-				le->next = l1;
+				NEXT(le) = l1;
 				le = l1;
-				l1 = l1->next;
+				l1 = NEXT(l1);
 			}
 			break;
 		}
-		if(datcmp(l1, l2) < 0) {
-			le->next = l1;
+		if(cmp(l1, l2) < 0) {
+			NEXT(le) = l1;
 			le = l1;
-			l1 = l1->next;
+			l1 = NEXT(l1);
 		} else {
-			le->next = l2;
+			NEXT(le) = l2;
 			le = l2;
-			l2 = l2->next;
+			l2 = NEXT(l2);
 		}
 	}
-	le->next = 0;
+	NEXT(le) = 0;
 	return l;
+	
+	#undef NEXT
 }
 
 Reloc*
@@ -1010,7 +1013,7 @@ dodata(void)
 				s->type = SDATARELRO;
 		}
 	}
-	datap = datsort(datap);
+	datap = listsort(datap, datcmp, offsetof(Sym, next));
 
 	/*
 	 * allocate sections.  list is sorted by type,