Ch03 - Loaders and Linkers - SystemSoftware | ChienI Kao = Nothing is true, everything is permitted

# Introduction

A loader is a system program that performs the loading function. Many loaders also support relocation and linking.
Some systems have a linker to perform the linking operations and a separate loader to handle relocation and loading.
In most cases all the program translators (ex. assemblers and compilers) on a particular system produce object programs in the same format. Thus one system loader or linker can be used regardless of the original source programming language.

An absolute loader does not need to perform such functions as linking and program relocation, its operation is very simple. All functions are accomplished in a single pass.
When the End record is encountered, the loader jumps to the specified address to begin execution of the loaded program.
從多少開始
每行的 T 的起點都要確認，不是每行都直接接下去，有變數的地方會跳
中間的 xx xxxxx…xxxx 是變數 (包含 array)，沒有常數 (常數是有值的)

When a computer is first turned on or restarted, a special type of absolute loader, called a bootstrap loader, is executed.
The bootstrap loads the first program to be run by the computer — usually an operating system.

The absolute loader is certainly simple and efficient; however, this scheme has several potential disadvantage.
- Writing absolute programs makes it difficult to use subroutine libraries efficiently.

Loaders that allow for program relocation are called relocation loaders or relative loaders.
There are two methods for specifying relocation as part of the object program.
- Modification record (suitable for SIX/XE programs, only some instructions require relocation).
- Relocation by bit mask (suitable for direct addressing and fixed instruction format, such as SIC programs; nearly all instructions require relocation, resulting in an object program more than twice as large as the original one.)
Relocation by bit mask
- There is a relocation bit (1 for relocation) associated with each word of object code (each SIC instruction).
- The relocation bis are gathered together into a bit mask following the length indicator in each Text record.

Relationship between the relocation and linking process.
The general approach taken is for the assembler to evaluate as much of the expression as it can. The remaining terms are passed on to the loader via Modificaion records.

The input to a linking loader consists of a set of object programs (ex. control sections) that are to be linked together.
It is possible (and common) for a control section to make an external reference to a symbol whose definition does not appear until later ini this input stream.
Thus a linking loader usually makes two passes over its input.
- Pass 1 assigns addresses to all external symbols.
- Pass 2 performs the actual loading, relocation, and linking.
The main data structure needed for our linking loader is an external symbol table ESTAB.
Two other important variables are PROGADDR(program load address) and CSADDR(control section address).
- The value of PROGADDR is supplied to the loader by the operating system.

Algorithm for Pass 1
Concerned only with Header and Define record types in the control sections.

	begin
	get PROGADDR from operating system
	set CSADDR to PROGADDR {for first control section}
	while not end of input do
	begin
	read next input record {Header record for control section}
	set CSLTH to control section length
	search ESTAB for control section name
	if found then
	set error flag {duplicate external symbol}
	else
	enter control section name into ESTAB with value CSADDR
	while record type != 'E' do
	begin
	read next input record
	if record type = 'D' then
	for each symbol in the record do
	begin
	search ESTAB for symbol name
	if found then
	set error flag (duplicate external symbol)
	else
	enter symbol into ESTAB with value
	(CSADDR + indicated address)
	end {for}
	end {while != 'E'}
	add CSLTH to CSADDR {starting address for next control section}
	end {while not EOF}
	end {Pass 1}

Algorithm for Pass 2

Perform the actual loading, relocation, and linking of the program.
The END record for each control section may contain the address of the first instruction in that control section to be executed. The loader takes this as the transfer point to begin execution.
- If more than one control section specifies a transfer address, the loader arbitrarily uses the last one encountered.
- If no control section contains a transfer address, the loader uses the beginning of the linked program (ex. PROGADDR) as the transfer point.
- Normally, a transfer address would be placed in the END record for a main program, but not for a subroutine.

	begin
	set CSADDR to PROGADDR
	set EXECADDR to PROGADDR
	while not end of input do
	begin
	read next input record {Header record}
	set CSLTH to control section length
	while record type != 'E' do
	begin
	read next input record
	if record type = 'T' then
	begin
	{if object code is in character form, convert
	into internal representation}
	move object code from record to location
	(CSADDR + specified address)
	end {if 'T'}
	else if record type = 'M' then
	begin
	search ESTAB for modifying symbol name
	if found then
	add or subtract symbol value at location
	(CSADDR + specified address)
	else
	set error flag (undefined external symbol)
	end {if 'M' }
	end {while != 'E' }
	if an address is specified {in End record} then
	set EXECADDR to (CSADDR + specified address)
	add CSLTH to CSADDR
	end {while not EOF}
	jump to location given by EXECADDR {to start execution of loaded program}
	end {Pass 2}

The algorithm can be made more efficient if a slight change is made in the object program format. This modification involves assigning a reference number to each external symbol referred to in a control section.
The main advantage of this reference-number mechanism is that it avoids multiple searches of ESTAB for the same symbol during the loading of a control section.

Automatic library search handles external references. This feature allows a programmer to use standard subroutines without explicitly including them in the program to be loaded. The routines are automatically retrieved from a library as they are needed during linking.