Relocatable objects 2

Important software update today. I have updated my compiler toolchain to support relocatable objects. Even though today’s version does not bring many improvements in code generation, I consider it very important and getting me much closer to my goal of running “real software” on BYTEC/16.

Until now, I only had a retargeted LCC compiler, which I used first in a preprocessor (cpp command) and then in a compiler-proper mode (rcc command), so that it generated output assembly files. Then I manually concatenated the assembly files I needed for a particular program and ran them through my quick & dirty two-pass assembler, which generated a flat binary file with code and data segments concatenated, padding segments with zeros when necessary. This was not the most convenient way of compiling stuff, as it required manual work and was error prone. Local labels in code generated by LCC normally overlap, so I had to manually update them to be able to “link” two (or more) assembly source files.

The answer to all this pain was relocatable objects support. In simple words relocatable objects are binary files which apart from code and data contain also metadata allowing to join them together and locate anywhere in memory. There are many relocatable object file formats out there, like ELF or a.out and multiple articles and blog posts on how linkers work. I have decided to go for the plain old a.out because of its simplicity and because it is the format used by Minix. My current implementation only supports static linking (i.e. there is still no dynamically linked shared libraries support neither in the assembler/linker nor in my rudimentary operating system) but I think it is a good starting point, sufficient for my current needs and with room for expansion.

There are different flavors of a.out files, but they are all very similar. One good description of the format may be found here. I used the a.out.h definition directly from Minix source code. It defines the following a.out header:

struct  exec {                  /* a.out header */
  unsigned char a_magic[2];     /* magic number */
  unsigned char a_flags;        /* flags, see below */
  unsigned char a_cpu;          /* cpu id */
  unsigned char a_hdrlen;       /* length of header */
  unsigned char a_unused;       /* reserved for future use */
  unsigned short a_version;     /* version stamp (not used at present) */
  long          a_text;         /* size of text segment in bytes */
  long          a_data;         /* size of data segment in bytes */
  long          a_bss;          /* size of bss segment in bytes */
  long          a_entry;        /* entry point */
  long          a_total;        /* total memory allocated */
  long          a_syms;         /* size of symbol table */

  /* SHORT FORM ENDS HERE */
  long          a_trsize;       /* text relocation size */
  long          a_drsize;       /* data relocation size */
  long          a_tbase;        /* text relocation base */
  long          a_dbase;        /* data relocation base */
};

A typical a.out header defines the sizes of code and data segments, and their entry addresses. It is followed by the actual code and data, and then by relocation tables and a symbol table.

Symbols are defined as follows:

struct nlist {                  /* symbol table entry */
  char n_name[8];               /* symbol name */
  long n_value;                 /* value */
  unsigned char n_sclass;       /* storage class */
  unsigned char n_numaux;       /* number of auxiliary entries (not used) */
  unsigned short n_type;        /* language base and derived type (not used) */
};

Relocation data structure is also quite simple:

struct reloc {
  long r_vaddr;                 /* virtual address of reference */
  unsigned short r_symndx;      /* internal segnum or extern symbol num */
  unsigned short r_type;        /* relocation type */
};

The only change I introduced to the above original Minix structures was support for long symbol names. Instead of storing a symbol name in char n_name[8], I store a reference in struct nlist to an array of zero terminated strings which I place at the end of the object file. The same approach is used in BSD a.out files.

Symbols and relocation tables are actually the most important elements of any relocatable object file. In a simplest form of any linkable objects one distinguishes between local, global and extern symbols (this is often referred to as storage class). Local symbols are local to the file and there is no intention to use them externally. Global symbols originate from the file but the programmer wishes to make them usable also in other objects the  current object will be linked with (in which the symbol is external). External symbols originate from another file (where they are global), and the programmer wishes to use them in the local file. Storage class is a concept well known to any C/C++ programmer who composes a program from multiple object files.

The relocation table tells the linker how to modify the code or data as soon as it is known where exactly the code and/or data will be placed in a linked executable (which is technically also an object file, only bigger). Relocations distinguish between absolute and relative references to local (global), or extern symbols and contain information about the locations (offsets) in code and data segments which need to be updated if the given object is relocated. For example, if a code segment at address 0x2512 contains an absolute reference data segment’s address 0x5000, then relocation structure will store information about offsets and reference type needed to change the value at code segment’s relative address 0x2512 (wherever this address lands in target object) to a new value resulting from relocating the original data address 0x5000 (which may also ultimately be at an arbitrary location). It get’s even funnier if you consider that such references exist between different linked files. It may seem scary but in reality it is very simple. All it takes is the right amount of bookkeeping during code generation, and that’s exactly what symbol tables and relocation tables are used for. I used this material by Ian Lance Taylor to understand the basics of linkers.

Paragraphs below are a quick reference of current capabilities of the assembler, linker and retargeted LCC compiler. Both the assembler and linker are distributed in a package which I called binutils, following the GNU compiler collection naming convention.

Assembler

The assembler was mostly rewritten. I kept most of the flex and bison grammars, but the code generation part was entirely replaced. It is not any more a two-pass assembler. Since I am not generating binaries but relocatable objects, there is no need for the second pass since the linker will do all the forward reference fix-ups (even the ones local to a single file).

Assembler’s input file is an assembly source listing following the grammar. The grammar defines possible assembly tokens and their operands (always in compliance with the current instruction set), allows for the use of labels (which define local symbols) and enables several directives. Assembler directives are prefixed with a dot. Currently the following directives and special commands are supported by the assembler:

Directive	Description
.global symbol_name	Define a global. Global symbol must be defined in code or data somewhere else (as label) and will be exported by an assembler in a.out symbol table to be used by the linker. Attempt to define a global symbol which is not defined elsewhere in the input file will result in an error.
.extern symbol_name	Define an extern. Extern symbol has no defined value but may be used in assembly code (grammar permitting). When it is used, it creates relocation entries which will be exported in a.out relocation table and also used by the linker. Extern symbol may not be defined in the input file.
.const #const_name value	Define a local constant. Constants are used for programmer’s convenience. Their names must start with a hash sign to distinguish them from symbols. Constant are not exported in a.out.
.db [value[:n]|string],...	Emit byte array at current location. Byte array elements may be defined as value or single-quote delimited string, and are separated by a comma. Minimum one array element must be provided. Value may be defined as decimal, hex with 0x prefix, binary with 0b prefix, or constant reference. Value may be also any valid arithmetic expression of the above. If value is postfixed with :n then it is duplicated n times in the binary output.
.dw value[:n],...	Emit word (2-byte) array at current location. Word array elements are separated by a comma. Minimum one array element must be provided. Value may be defined as decimal, hex with 0x prefix, binary with 0b prefix, constant reference, or absolute label reference. Value may be also any valid arithmetic expression of the above. If value is postfixed with :n then it is duplicated n times in the binary output.
.text	Switch to code segment. Starting from this directive until .data or end of file all code is emitted to text (code) segment.
.data	Switch to data segment. Starting from this directive until .text or end of file all code is emitted to text data segment.
;	Defines a comment. All characters starting with semicolon until end of a line are ignored.

BYTEC/16 assembler is a command line tool with the following options:

Usage: as-b16 [options] file
Options:
 -o filename  Set output filename (required)
 -m macro     Specify m4 macro definition to unroll long-op calls (optional)
 -v           Set verbose output (optional)

Output filename is a filename of resulting object file. If it is not provided, the output file will be named ‘a.out’.

Option -v instructs the assembler to be verbose. With this option enabled it prints out information about encountered symbols, created relocation records and details of generated output file. I have found it useful for debugging.

Option -m is used to enable the assembly M4 preprocessor. This is used to unroll the macros used in LCC’s 32- and 64-bit operations (long and float/double types) to subroutine calls (as described in this post). This option requires a file with M4 macro definitions which is also provided as part of binutils (although now it provides only empty macro shells as my long/float/double support in LCC is not not yet mature enough to share it here).

Linker

The linker has been written in C from scratch. It takes multiple object files as input and generates a linked object file as output. The resulting object does not contain undefined symbol references anymore, and can be treated as an executable (although technically it still a a.out file) by OS executable loader. In the future, Minix will do the job of executable loading. In the meantime, I am planning to add support to load and execute programs over serial cable to my simple OS, which will dramatically shorten the development/test cycle (no more continuous ROM burning, or struggling with EPROM emulator cables).

Current BYTEC/16 linker is still a static linker. It means that all required code (including library code) needs to be statically linked. Support for dynamically linked libraries (like DLLs in Windows and shared objects in Unix world) is one of my future goals.

Here is the linker’s workflow:

• Read and concatenate code and data segments from input a.out files (in the order they are provided in command line).
• Read input files symbol and relocation tables.
• Resolve symbols – attempt to match undefined extern symbols with defined global symbols across files; raise an error when a symbol cannot be resolved (undefined reference); raise an error when one symbol is defined more that once (redefined symbol).
• Apply relocations – having all symbols resolved, apply fixups to code and data – e.g. populate values of previously undefined references (which are already known), or update value of absolute references (because they point to addresses which have been relocated).
• Save output a.out file.

The linker is invoked with the following options:

Usage: ld-b16 [options] file...
Options:
 -o filename  Set output filename (default is a.out)
 -f format    Set output format (AOUT and IHEX, default is AOUT)
 -t address   Set relocation address of .text section (address must be hexadecimal)
 -d address   Set relocation address of .data section (address must be hexadecimal)
 -e address   Set entry address of data segment in Intel HEX file (only relevant with -f IHEX)
 -v           Set verbose output

It takes multiple a.out files as an input. They are processed in the exact order of the command line. The option -o defines the output filename. If it is not provided, the output will be named ‘a.out’.

Options -t and -d define the entry (beginning) addresses for code and data, respectively. Their address parameters must be provided as hexadecimal numbers. For example, the following generates an a.out file with code segment starting at 0x0100 and data segment starting at 0x3000:

ld-b16 <input files...> -o <output file> -t 0x0100 -d 0x3000

Option -f defines the format of the output file and has two possible arguments, AOUT and IHEX. Default is to produce a.out but one may also chose to generate an Intel HEX format for an EPROM programmer. In this case the resulting Intel HEX will be composed of two segments – a code segment followed by a data segment. Code segment always starts at zero address. An arbitrary start address of the data segment may be chosen with -e option. For example in order to generate a 128kB ROM Intel HEX file with code segment starting at 0x0000 and data segment starting at 0x10000 one would execute:

ld-b16 <input files...> -o <output file> -f IHEX -e 0x10000

LCC driver

There is an update to LCC port, too. LCC comes with a program that wraps the assembler, C preprocessor, C compiler and linker. It is similar to GNU’s gcc which is merely a wrapper of different programs from the compiler collection. Using gcc one does not have to individually execute the preprocessor (cpp), assembly code generation (cc -S), the GNU assembler (as) and the GNU linker (ld). The gcc program does it all for you.

LCC also has its wrapper. It is called driver in the LCC book. The command to execute the LCC driver is lcc. Depending on the options, the driver executes cpp (LCC preprocessor) and rcc (compiler proper) with the right options behind the scenes, creating and removing temporary files whenever necessary.

LCC driver is build per target architecture. I haven’t built one before for BYTEC/16 because I didn’t have all required components it uses. Now that I have the assembler with relocatable objects support and the linker, I have extended my LCC port to use the driver, too. Having executed the preprocessor and compiler proper, the driver completes its job by executing BYTEC/16 custom assembler and linker, producing a final BYTEC/16 executable.

Here is what the LCC driver can do by invoking options of underlying tools (extract):

lcc [ option | file ]...
-A                  warn about nonANSI usage; 2nd -A warns more
-c                  compile only
-Dname -Dname=def   define the preprocessor symbol `name'
-E                  run only the preprocessor on the named C programs and unsuffixed files
-help or -?         print this message on standard error
-Idir               add `dir' to the beginning of the list of #include directories
-M                  emit makefile dependencies; implies -E
-N                  do not search the standard directories for #include files
-o                  file    leave the output in `file'
-P                  print ANSI-style declarations for globals on standard error
-S                  compile to assembly language
-t -tname           emit function tracing calls to printf or to `name'
-tempdir=dir        place temporary files in `dir/'; default=/tmp
-Uname              undefine the preprocessor symbol `name'
-v                  show commands as they are executed; 2nd -v suppresses execution
-w                  suppress warnings
-W[pfal]arg         pass `arg' to the preprocessor, compiler, assembler, or linker

Porting the driver was actually trivial and required creating a host file based on a provided template. My host file is called bytec16.c and resides in LCC’s etc folder. Installation procedure for LCC with the driver is now the following:

1. Download off-the-shelf LCC ver. 4.2. It is available here.
2. Download the most recent BYTEC/16 patches from downloads page.
3. Unzip LCC to a dedicated directory, e.g. lcc.
4. Unzip the patch file to LCC root directory by invoking gunzip patchfilename.gz.
5. Apply patches by invoking patch -p0 < patchfilename. This will update src/gen.c, src/bind.c, the makefile, and create src/bytec16.md (the machine description).
6. Create LCC build directory, e.g. lcc/bin by invoking mkdir -p bin from within LCC root directory.
7. Set BUILDDIR environment variable to point to the build directory by invoking export BUILDDIR=`pwd`/bin from within LCC root directory.
8. Invoke make HOSTFILE=etc/bytec16.c lcc to build LCC driver.
9. Invoke make all to build the rest of LCC, including compiler proper.

Note the change of the HOSTFILE parameter. It is important to mention here also, that LCC driver will look for BYTEC/16 assembler and linker in the /usr/local/bin directory, so as-b16 and ld-b16 must exist there or at least be symlinked to their respective directories.

Instruction set

Finally, I have another instruction set update to share. Trying to free up some opcode space I have removed a few redundant opcodes – POP PC (same as RET), STI and CLI (same can be done by manipulating the MSW). Instead, I have added more LEA instructions which are very useful in compiler generated assembly.

The new software release has been posted to the downloads page with today’s date.