liblink: create new library based on linker code

There is an enormous amount of code moving around in this CL,
but the code is the same, and it is invoked in the same ways.
This CL is preparation for the new linker structure, not the new
structure itself.

The new library's definition is in include/link.h.

The main change is the use of a Link structure to hold all the
linker-relevant state, replacing the smattering of global variables.
The Link structure should both make it clearer which state must
be carried around and make it possible to parallelize more easily
later.

The main body of the linker has moved into the architecture-independent
cmd/ld directory. That includes the list of known header types, so the
distinction between Hplan9x32 and Hplan9x64 is removed (no other
header type distinguished 32- and 64-bit formats), and code for unused
formats such as ipaq kernels has been deleted.

The code being deleted from 5l, 6l, and 8l reappears in liblink or in ld.
Because multiple files are being merged in the liblink directory,
it is not possible to show the diffs nicely in hg.

The Prog and Addr structures have been unified into an
architecture-independent form and moved to link.h, where they will
be shared by all tools: the assemblers, the compilers, and the linkers.
The unification makes it possible to write architecture-independent
traversal of Prog lists, among other benefits.

The Sym structures cannot be unified: they are too fundamentally
different between the linker and the compilers. Instead, liblink defines
an LSym - a linker Sym - to be used in the Prog and Addr structures,
and the linker now refers exclusively to LSyms. The compilers will
keep using their own syms but will fill out the corresponding LSyms in
the Prog and Addr structures.

Although code from 5l, 6l, and 8l is now in a single library, the
code has been arranged so that only one architecture needs to
be linked into a particular program: 5l will not contain the code
needed for x86 instruction layout, for example.

The object file writing code in liblink/obj.c is from cmd/gc/obj.c.

Preparation for golang.org/s/go13linker work.

This CL does not build by itself. It depends on 35740044
and will be submitted at the same time.

R=iant
CC=golang-dev
https://codereview.appspot.com/35790044

2 files changed, 569 insertions, 0 deletions

diff --git a/include/link.h b/include/link.h
new file mode 100644
index 000000000..1d6aec49e
--- /dev/null
+++ b/include/link.h
@@ -0,0 +1,567 @@
+// Derived from Inferno utils/6l/l.h and related files.
+// http://code.google.com/p/inferno-os/source/browse/utils/6l/l.h
+//
+//	Copyright © 1994-1999 Lucent Technologies Inc.  All rights reserved.
+//	Portions Copyright © 1995-1997 C H Forsyth (forsyth@terzarima.net)
+//	Portions Copyright © 1997-1999 Vita Nuova Limited
+//	Portions Copyright © 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com)
+//	Portions Copyright © 2004,2006 Bruce Ellis
+//	Portions Copyright © 2005-2007 C H Forsyth (forsyth@terzarima.net)
+//	Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others
+//	Portions Copyright © 2009 The Go Authors.  All rights reserved.
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+// THE SOFTWARE.
+
+typedef	struct	Addr	Addr;
+typedef	struct	Prog	Prog;
+typedef	struct	LSym	LSym;
+typedef	struct	Reloc	Reloc;
+typedef	struct	Auto	Auto;
+typedef	struct	Hist	Hist;
+typedef	struct	Hist2	Hist2;
+typedef	struct	Link	Link;
+typedef	struct	Plist	Plist;
+typedef	struct	LinkArch	LinkArch;
+typedef	struct	Library	Library;
+
+typedef	struct	Pcln	Pcln;
+typedef	struct	Pcdata	Pcdata;
+
+struct	Addr
+{
+	vlong	offset;
+
+	union
+	{
+		char	sval[8];
+		float64	dval;
+		Prog*	branch;	// for 5g, 6g, 8g
+	} u;
+
+	LSym*	sym;
+	LSym*	gotype;
+	short	type;
+	uint8	index;
+	int8	scale;
+	int8	reg;	// for 5l
+	int8	name; // for 5l
+	int8	class;	// for 5l
+	uint8	etype; // for 5g, 6g, 8g
+	int32	offset2;	// for 5l, 8l
+	struct Node*	node; // for 5g, 6g, 8g
+	int64	width; // for 5g, 6g, 8g
+};
+
+struct	Reloc
+{
+	int32	off;
+	uchar	siz;
+	uchar	done;
+	int32	type;
+	int64	add;
+	int64	xadd;
+	LSym*	sym;
+	LSym*	xsym;
+};
+
+struct	Prog
+{
+	vlong	pc;
+	int32	lineno;
+	Prog*	link;
+	short	as;
+	uchar	reg; // arm only
+	uchar	scond; // arm only
+	Addr	from;
+	Addr	to;
+	
+	// for 5g, 6g, 8g internal use
+	uint32	loc;	// TODO: merge with pc?
+	void*	opt;
+
+	// for 5l, 6l, 8l internal use
+	Prog*	forwd;
+	Prog*	pcond;
+	Prog*	comefrom;	// 6l, 8l
+	Prog*	pcrel;	// 5l
+	int32	spadj;
+	uchar	mark;
+	uchar	back;	// 6l, 8l
+	char	ft;	/* 6l, 8l oclass cache */
+	char	tt;	// 6l, 8l
+	uchar	optab;	// 5l
+
+	char	width;	/* fake for DATA */
+	char	mode;	/* 16, 32, or 64 */
+};
+
+struct	LSym
+{
+	char*	name;
+	char*	extname;	// name used in external object files
+	short	type;
+	short	version;
+	uchar	dupok;
+	uchar	reachable;
+	uchar	cgoexport;
+	uchar	special;
+	uchar	stkcheck;
+	uchar	hide;
+	uchar	leaf;	// arm only
+	uchar	fnptr;	// arm only
+	int16	symid;	// for writing .5/.6/.8 files
+	int32	dynid;
+	int32	sig;
+	int32	plt;
+	int32	got;
+	int32	align;	// if non-zero, required alignment in bytes
+	int32	elfsym;
+	int32	args;	// size of stack frame incoming arguments area
+	int32	locals;	// size of stack frame locals area (arm only?)
+	vlong	value;
+	vlong	size;
+	LSym*	hash;	// in hash table
+	LSym*	allsym;	// in all symbol list
+	LSym*	next;	// in text or data list
+	LSym*	sub;	// in SSUB list
+	LSym*	outer;	// container of sub
+	LSym*	gotype;
+	LSym*	reachparent;
+	LSym*	queue;
+	char*	file;
+	char*	dynimplib;
+	char*	dynimpvers;
+	struct Section*	sect;
+	Hist2*	hist;	// for ATEXT
+	
+	// STEXT
+	Auto*	autom;
+	Prog*	text;
+	Pcln*	pcln;
+
+	// SDATA, SBSS
+	uchar*	p;
+	int32	np;
+	int32	maxp;
+	Reloc*	r;
+	int32	nr;
+	int32	maxr;
+};
+
+// LSym.type
+enum
+{
+	Sxxx,
+
+	/* order here is order in output file */
+	/* readonly, executable */
+	STEXT,
+	SELFRXSECT,
+	
+	/* readonly, non-executable */
+	STYPE,
+	SSTRING,
+	SGOSTRING,
+	SGOFUNC,
+	SRODATA,
+	SFUNCTAB,
+	STYPELINK,
+	SSYMTAB, // TODO: move to unmapped section
+	SPCLNTAB,
+	SELFROSECT,
+	
+	/* writable, non-executable */
+	SMACHOPLT,
+	SELFSECT,
+	SMACHO,	/* Mach-O __nl_symbol_ptr */
+	SMACHOGOT,
+	SNOPTRDATA,
+	SINITARR,
+	SDATA,
+	SWINDOWS,
+	SBSS,
+	SNOPTRBSS,
+	STLSBSS,
+
+	/* not mapped */
+	SXREF,
+	SMACHOSYMSTR,
+	SMACHOSYMTAB,
+	SMACHOINDIRECTPLT,
+	SMACHOINDIRECTGOT,
+	SFILE,
+	SFILEPATH,
+	SCONST,
+	SDYNIMPORT,
+	SHOSTOBJ,
+
+	SSUB = 1<<8,	/* sub-symbol, linked from parent via ->sub list */
+	SMASK = SSUB - 1,
+	SHIDDEN = 1<<9, // hidden or local symbol
+};
+
+struct	Auto
+{
+	LSym*	asym;
+	Auto*	link;
+	int32	aoffset;
+	int16	type;
+	LSym*	gotype;
+};
+
+enum
+{
+	LINKHASH = 100003,
+};
+
+struct	Hist
+{
+	Hist*	link;
+	char*	name;
+	int32	line;
+	int32	offset;
+};
+
+struct	Plist
+{
+	LSym*	name;
+	Prog*	firstpc;
+	int	recur;
+	Plist*	link;
+};
+
+struct	Library
+{
+	char *objref;	// object where we found the reference
+	char *srcref;	// src file where we found the reference
+	char *file;	// object file
+	char *pkg;	// import path
+};
+
+struct Pcdata
+{
+	uchar *p;
+	int n;
+	int m;
+};
+
+struct Pcln
+{
+	Pcdata pcsp;
+	Pcdata pcfile;
+	Pcdata pcline;
+	Pcdata *pcdata;
+	int npcdata;
+	LSym **funcdata;
+	int64 *funcdataoff;
+	int nfuncdata;
+	
+	LSym **file;
+	int nfile;
+	int mfile;
+
+	LSym *lastfile;
+	int lastindex;
+};
+
+enum
+{
+	LinkMaxHist = 40,
+};
+
+// TODO: Replace uses of Hist2 with Hist and delete this.
+struct Hist2
+{
+	int32 line;
+	int32 off;
+	LSym *file;
+};
+
+// symbol version, incremented each time a file is loaded.
+// version==1 is reserved for savehist.
+enum
+{
+	HistVersion = 1,
+};
+
+// Link holds the context for writing object code from a compiler
+// to be linker input or for reading that input into the linker.
+struct	Link
+{
+	int32	thechar; // '5' (arm), '6' (amd64), etc.
+	char*	thestring; // full name of architecture ("arm", "amd64", ..)
+	int32	goarm; // for arm only, GOARM setting
+	int	headtype;
+	int	linkmode;
+
+	LinkArch*	arch;
+	int32	(*ignore)(char*);	// do not emit names satisfying this function
+	int32	debugasm;	// -S flag in compiler
+	int32	debugline;	// -L flag in compiler
+	int32	debughist;	// -O flag in linker
+	int32	debugread;	// -W flag in linker
+	int32	debugvlog;	// -v flag in linker
+	int32	debugstack;	// -K flag in linker
+	int32	debugzerostack;	// -Z flag in linker
+	int32	debugdivmod;	// -M flag in 5l
+	int32	debugfloat;	// -F flag in 5l
+	int32	debugpcln;	// -O flag in linker
+	int32	flag_shared;	// -shared flag in linker
+	int32	iself;
+	Biobuf*	bso;	// for -v flag
+	char*	pathname;
+	int32	windows;
+
+	// hash table of all symbols
+	LSym*	hash[LINKHASH];
+	LSym*	allsym;
+	int32	nsymbol;
+
+	// file-line history
+	Hist*	hist;
+	Hist*	ehist;
+	
+	// all programs
+	Plist*	plist;
+	Plist*	plast;
+	
+	// code generation
+	LSym*	sym_div;
+	LSym*	sym_divu;
+	LSym*	sym_mod;
+	LSym*	sym_modu;
+	LSym*	symmorestack[10];
+	LSym*	gmsym;
+	LSym*	plan9tos;
+	Prog*	curp;
+	Prog*	printp;
+	Prog*	blitrl;
+	Prog*	elitrl;
+	int	rexflag;
+	int	asmode;
+	uchar*	andptr;
+	uchar	and[100];
+	int32	instoffset;
+	int32	autosize;
+	int32	armsize;
+
+	// for reading input files (during linker)
+	vlong	pc;
+	char**	libdir;
+	int32	nlibdir;
+	int32	maxlibdir;
+	Library*	library;
+	int	libraryp;
+	int	nlibrary;
+	int	tlsoffset;
+	void	(*diag)(char*, ...);
+	void	(*dwarfaddfrag)(int, char*);
+	LSym*	histfrog[LinkMaxHist];
+	int	histfrogp;
+	int	histgen;
+	Auto*	curauto;
+	Auto*	curhist;
+	LSym*	cursym;
+	int	version;
+	LSym*	textp;
+	LSym*	etextp;
+	Hist2*	histcopy;
+	Hist2*	hist2;
+	int32	nhist2;
+	int32	maxhist2;
+	int32	histdepth;
+	int32	nhistfile;
+	LSym*	filesyms;
+};
+
+// LinkArch is the definition of a single architecture.
+struct LinkArch
+{
+	char*	name; // "arm", "amd64", and so on
+
+	void	(*addstacksplit)(Link*, LSym*);
+	void	(*assemble)(Link*, LSym*);
+	int	(*datasize)(Prog*);
+	void	(*follow)(Link*, LSym*);
+	int	(*iscall)(Prog*);
+	int	(*isdata)(Prog*);
+	void	(*ldobj)(Link*, Biobuf*, char*, int64, char*);
+	void	(*nopout)(Prog*);
+	Prog*	(*prg)(void);
+	void	(*progedit)(Link*, Prog*);
+	void	(*settextflag)(Prog*, int);
+	int	(*symtype)(Addr*);
+	int	(*textflag)(Prog*);
+	void	(*zfile)(Biobuf*, char*, int);
+	void	(*zhist)(Biobuf*, int, vlong);
+	void	(*zprog)(Link*, Biobuf*, Prog*, int, int, int, int);
+	void (*zname)(Biobuf*, LSym*, int);
+
+	int	minlc;
+	int	ptrsize;
+	
+	// TODO: Give these the same values on all systems.
+	int	D_ADDR;
+	int	D_BRANCH;
+	int	D_CONST;
+	int	D_EXTERN;
+	int	D_FCONST;
+	int	D_NONE;
+	int	D_PCREL;
+	int	D_SCONST;
+	int	D_SIZE;
+
+	int	ACALL;
+	int	AFUNCDATA;
+	int	AJMP;
+	int	ANOP;
+	int	APCDATA;
+	int	ARET;
+	int	ATEXT;
+	int	AUSEFIELD;
+};
+
+/* executable header types */
+enum {
+	Hunknown = 0,
+	Hdarwin,
+	Hdragonfly,
+	Helf,
+	Hfreebsd,
+	Hlinux,
+	Hnetbsd,
+	Hopenbsd,
+	Hplan9,
+	Hwindows,
+};
+
+enum
+{
+	LinkAuto = 0,
+	LinkInternal,
+	LinkExternal,
+};
+
+extern	uchar	fnuxi8[8];
+extern	uchar	fnuxi4[4];
+extern	uchar	inuxi1[1];
+extern	uchar	inuxi2[2];
+extern	uchar	inuxi4[4];
+extern	uchar	inuxi8[8];
+
+// asm5.c
+void	span5(Link *ctxt, LSym *s);
+
+// asm6.c
+void	span6(Link *ctxt, LSym *s);
+
+// asm8.c
+void	span8(Link *ctxt, LSym *s);
+
+// data.c
+vlong	addaddr(Link *ctxt, LSym *s, LSym *t);
+vlong	addaddrplus(Link *ctxt, LSym *s, LSym *t, vlong add);
+vlong	addaddrplus4(Link *ctxt, LSym *s, LSym *t, vlong add);
+vlong	addpcrelplus(Link *ctxt, LSym *s, LSym *t, vlong add);
+Reloc*	addrel(LSym *s);
+vlong	addsize(Link *ctxt, LSym *s, LSym *t);
+vlong	adduint16(Link *ctxt, LSym *s, uint16 v);
+vlong	adduint32(Link *ctxt, LSym *s, uint32 v);
+vlong	adduint64(Link *ctxt, LSym *s, uint64 v);
+vlong	adduint8(Link *ctxt, LSym *s, uint8 v);
+vlong	adduintxx(Link *ctxt, LSym *s, uint64 v, int wid);
+void	mangle(char *file);
+void	savedata(Link *ctxt, LSym *s, Prog *p, char *pn);
+vlong	setaddr(Link *ctxt, LSym *s, vlong off, LSym *t);
+vlong	setaddrplus(Link *ctxt, LSym *s, vlong off, LSym *t, vlong add);
+vlong	setuint16(Link *ctxt, LSym *s, vlong r, uint16 v);
+vlong	setuint32(Link *ctxt, LSym *s, vlong r, uint32 v);
+vlong	setuint64(Link *ctxt, LSym *s, vlong r, uint64 v);
+vlong	setuint8(Link *ctxt, LSym *s, vlong r, uint8 v);
+vlong	setuintxx(Link *ctxt, LSym *s, vlong off, uint64 v, vlong wid);
+void	symgrow(Link *ctxt, LSym *s, int32 siz);
+
+// go.c
+void*	emallocz(long n);
+void*	erealloc(void *p, long n);
+char*	estrdup(char *p);
+char*	expandpkg(char *t0, char *pkg);
+
+// ieee.c
+void	double2ieee(uint64 *ieee, double native);
+
+// ld.c
+void	addhist(Link *ctxt, int32 line, int type);
+void	addlib(Link *ctxt, char *src, char *obj);
+void	addlibpath(Link *ctxt, char *srcref, char *objref, char *file, char *pkg);
+void	collapsefrog(Link *ctxt, LSym *s);
+void	copyhistfrog(Link *ctxt, char *buf, int nbuf);
+int	find1(int32 l, int c);
+Hist2*	gethist(Link *ctxt);
+void	linkgetline(Link *ctxt, Hist2 *h, int32 line, LSym **f, int32 *l);
+void	histtoauto(Link *ctxt);
+void	mkfwd(LSym*);
+void	nuxiinit(void);
+void	savehist(Link *ctxt, int32 line, int32 off);
+Prog*	copyp(Link*, Prog*);
+Prog*	appendp(Link*, Prog*);
+vlong	atolwhex(char*);
+
+// obj.c
+int	linklinefmt(Link *ctxt, Fmt *fp);
+void	linklinehist(Link *ctxt, int lineno, char *f, int offset);
+Plist*	linknewplist(Link *ctxt);
+void	linkouthist(Link *ctxt, Biobuf *b);
+void	linkprfile(Link *ctxt, int32 l);
+void	linkwritefuncs(Link *ctxt, Biobuf *b);
+
+// pass.c
+Prog*	brchain(Link *ctxt, Prog *p);
+Prog*	brloop(Link *ctxt, Prog *p);
+void	linkpatch(Link *ctxt, LSym *sym);
+
+// pcln.c
+void	linkpcln(Link*, LSym*);
+
+// rdobj5.c
+void	ldobj5(Link *ctxt, Biobuf *f, char *pkg, int64 len, char *pn);
+void	nopout5(Prog *p);
+
+// rdobj6.c
+void	ldobj6(Link *ctxt, Biobuf *f, char *pkg, int64 len, char *pn);
+void	nopout6(Prog *p);
+
+// rdobj8.c
+void	ldobj8(Link *ctxt, Biobuf *f, char *pkg, int64 len, char *pn);
+void	nopout8(Prog *p);
+
+// sym.c
+LSym*	linklookup(Link *ctxt, char *name, int v);
+Link*	linknew(LinkArch*);
+LSym*	linknewsym(Link *ctxt, char *symb, int v);
+LSym*	linkrlookup(Link *ctxt, char *name, int v);
+int	linksymfmt(Fmt *f);
+
+extern	char*	anames5[];
+extern	char*	anames6[];
+extern	char*	anames8[];
+
+extern	LinkArch	link386;
+extern	LinkArch	linkamd64;
+extern	LinkArch	linkarm;
diff --git a/include/u.h b/include/u.h
index 44bfcd63b..6b2d50cc1 100644
--- a/include/u.h
+++ b/include/u.h
@@ -188,6 +188,8 @@ typedef u32int uint32;
 typedef s64int int64;
 typedef u64int uint64;
 
+typedef float float32;
+typedef double float64;
 
 #undef _NEEDUCHAR
 #undef _NEEDUSHORT