System Programming

Loading and Linking -1  

Introduction

To execute an object program, we need to:

Relocate: modify the object program so that it can be loaded at a different address. Link Control sections: combine separate object programs and resolve references between them

Allocate and load: allocate required memory and read in the object program into this memory.

Run: transfer control to the first instruction.

Over view

▪ Basic Loader Functions

• Absolute Loaders

• Bootstrap Loaders

▪ Machine Dependent Loader Features

Relocation

• Program Linking

Tables and Logic for a Linking Loader

• Machine Independent Loader Features

▪ Automatic Library Search

• Loader Commands

• Loader Design Options

• Linkage Editors

Dynamic Linking

Bootstrap Loaders

Design of at Absolute Loader

§  Absolute Loaders

Single Pass

Accepts Object File such as that produced by an Assembler or Compiler

Loads program into memory

All address references are Absolute — No relocation is necessary 

Algorithm for an absolute loader  

Begin

read Header record

verify program name and length

read first Text record

while record type is not 'E' do

begin

{if object code is in character form, convert into internal representation}

move object code to specified location in memory read next object program record end

jump to address specified in End record

end

A Simple Bootstrap Loader

Executed when computer is turned on or reset

Loads a predetermined program

Usually (part of) the operating system

• Loads from a specific device.

Loads into predetermined memory locations

When load is complete, jumps to predefined address

Program

The bootstrap itself begins at address 0

It loads the OS starting from address 0x80

No header record or other control information

Object code is consecutive bytes of memory

SIC Bootstrap Loader Logic

Begin

X=0x80 (the address of the next memory location to be loaded

Loop

A←GETC (and convert it from the ASCII character, code to the value of the hexadecimal digit) save the value in the high-order 4 bits of S.

A←GETC combine the value to form one byte A← (A+S)

store the value (in A) to the address in register X

X←X+1

End

ASCII codes

0~9 : 30~39

 A~F : 41~46

GETC

A←read one character

 if A=0x04 then jump to 0x80

if A<48 then GETC

A ←A-48 (0x30)

if A<10 then return A ←A-7

return

Relocating Loaders

Determine load address at load time, not assembly time.

Motivation

Increase efficiency on machine with larger memory by having several independent programs loaded at the same time in memory.

• support the use of subroutine libraries.

Object File

• All addresses are zero-based

• As if the program were to be loaded at address 0

Actual load point is an input to the loader

Comes from the Operating System

Load Point address is added to all

addresses indicated on Text records, before loading

• All absolute address references in the code are now incorrect! 

Modification Records

• Modification Record

• Each absolute address reference may be fixed by a Modification Record in the Object File

Indicates relative address within the program of data to be modified

Indicates (symbolic) value to be added to (or subtracted from) the contents of memory at that relative address

Modification record

col 1:M

col 2-7: relocation address

col 8-9: length (halfbyte)

col 10: flag(+/-)

col 11-17: segment name

M00000705+COPY

Also called RLD specification

Relocation and Linkage Directory

Modification Records - Algorithm

Algorithm

Pass 1: Process all H, D and R records in the object file, computing the addresses of all External Symbols

Pass 2: Process all T and M records

• Relocate data in T records

• Compute M record values

Jump to the Starting Address given in the End record

Relocation Bit — Alternative

. For SIC type machines

• Relocation bit

0: no modification is necessary

1: modification is needed

each instruction is associated with one relocation bit

relocation bits in a Text record are gathered into a bit mask

• Twelve-bit mask is used in each Text record

Each text record contains less than 12 words

• unused words are set to 0

any value that is to be modified during relocation must coincide with one of these 3-byte segments 

Program Linking

Goal

• Resolve the problems with EXTREF and EXTDEF from different control sections Example

Use modification records for both relocation and linking 

Program Linking Example

• Load address for control sections

PROGA 004000 63

PROGB 004063 7F

PROGC 0040E2 51

• Load address for symbols.

LISTA: PROGA+0040=4040

LISTB: PROGB+0060=40C3

LISTC: PROGC+0030=4112

REF4 in PROGA

ENDA-LISTA+LISTC=14+4112=4126 . T0000540F000014FFFFF600003F000014FFFFC0

M00005406+LISTC

Program- Logic and Data Structure

▪ Two Pass Logic

 Pass 1: assign addresses to all external symbols

Pass 2: perform the actual loading, relocation, and linking

ESTAB (external symbol table)

Control Section	Symbol	Address	Length
PROGA		4000	63
	LISTA  ENDA	4040 4054
PROGB		4063	7F
	LISTB ENDB	40C3 40D3
PROGC		40E2	51
	LISTC ENDC	4112 4124

Pass 1 Program Logic

Pass 1:

• assign addresses to all external symbols

• Variables & Data structures

• PROGADDR (program load address) from OS

• CSADDR (control section address)

• CSLTH (control section length)

·        ESTAB

 Process Define Record

Pass 2 Program Logic

▪Pass 2:

Perform the actual loading, relocation, and linking

Modification record

• lookup the symbol in ESTAB

End record for a main program

transfer address

Process Text record and Modification record 

Improve Efficiency

• Use local searching instead of multiple searches of ESTAB for the same symbol

• assign a reference number to each external symbol

• the reference number is used in Modification records

Implementation

• 01: control section name

 • other: external reference symbols 

Improve Efficiency

• Use local searching instead of multiple searches of ESTAB for the same symbol

• assign a reference number to each external symbol

• the reference number is used in Modification records

Implementation

• 01: control section name

 • other: external reference symbols

Example: PROGA

Ref No.	Symbol	Address
1	PROGA	4000
2	LISTB	40C3
3	ENDB	40D3
4	LISTC	4112
5	ENDC	4124

PROGB

Ref No.	Symbol	Address
1	PROGB	4063
2	LISTA	4040
3	ENDA	4054
4	LISTC	4112
5	ENDC	4124

PROGC

Ref No.	Symbol	Address
1	PROGB	4063
2	LISTA	4040
3	ENDA	4054
4	LISTC	40C3
5	ENDC	40D3

  Automatic Library Search

Subprogram Libraries

• Standard Libraries -- known to loader

• Other libraries -- specified by control statements to the loader

CSECTs from Library

• External references in Source Program

• Automatically retrieved from Library and linked (automatic library call, or library search)

SOEN 229

Searching Algorithms

For all symbols from REFER records

• Enter into ESTAB (if not already there)

• Mark them as "undefined" initially

For all symbols from DEFINE records or HEADER records

• Enter into ESTAB (if not already there)

• Mark as "defined"

At the end of Pass 1

• Symbols in ESTAB still marked are unresolved external references

• Search Program Libraries for these symbols

• When found, link in the defining CSECT

Repeat above steps for all REFER, DEFINE and HEADER records in Library CSECTs

If any entries in ESTAB still undefined— then report error

Overriding Library Search

If symbols with the same name appear in both the loader input and in the library, the loader input takes precedence

Thus it is possible to override automatic library search by including a CSECT in the loader input that defines some of the same external symbols as ones in the library For example, you could write your own I/O routines and override the ones normally retrieved from the library.

Searching the Library

Library contents = object programs

Linear search for symbols is inefficient;

Solution: Directory containing pairs:

- Name of symbol defined in DEFINE or header record

- Location in the file of CSECT containing the definition

Aliases - duplicate names

- All names are stored in the directory

- Aliases point to the same CSECT

Loader Commands

• Mechanisms

- Command file

- Job Control Language

- Incorporate in Object File

• INCLUDE <ProgName>(<LibraryName>)

 - Read program from Library and treat it as part of the input stream

• DELETE <CSECT-Name>

- Delete a CSECT from the set of programs in the loader input

• CHANGE <Namel> <Name2>

- Change the name of an external symbol every time it appears in object programs • LIBRARY <LibraryName>

- Search indicated library before searching the automatic library

Loader Commands (cont.)

NOCALL <NameList>

- Don't resolve external references to the names in <NameList>

 - Avoids linking in CSECTs you know you won't be needing for the current run

- May result in an error if statements containing references to the names in <NameList> are executed

- Useful during program development

• MAP

- Generate a load map

- Possible information in a load map:

o Control Section names & addresses

o Other external symbol names and addresses

o Cross reference showing where references to symbols appear 

Loader Command - Example

A square root function, SQRT, is called from several places the object program being presented to the loader.

SQRT is in the loader input file

Another version of square root, SQROOT, is available in a brary called ALTLIB

We wish to replace calls to SQRT by calls to SQROOT without recompiling the source

We pass the following sequence of commands to the loader:

INCLUDE SQROOT (ALTLIB)

DELETE SQRT

CHANGE SQRT, SQROOT

Loader Design Option

Linkage Editors

Dynamic Linking

Bootstrap Loaders

Linkage Editors

Same function as linking loader except the linked program is written to a file rather than loaded into memory and executed

File is called a load module or executable image

Usually relocatable

A Relocating Loader is then needed to load and execute the load module

Advantages and Disadvantages of Linkage Editors

Advantages

• Low overhead if the program is to be executed frequently (without change)

• Even greater savings if the load address is known at link-edit time -- an absolute load module can be generated and no relocation needs to be done at load time Disadvantages

• Load modules take up space

• Extra steps required can be inconvenient if the program is recompiled frequently (e.g., during testing) 

Building Subroutine Packages

Use the Linkage Editor to link a collection of routines that normally appear together, into a subroutine package

The Subroutine Package is linked with a using program with a linking loader when the using program is loaded

Saves the cost of linking routines in the package every time they are needed in a using program

Dynamic Linking

Run time linking -- occurs when a call is made to a CSECT that is currently not in memory

Overhead of linking is not incurred unless the CSECT is actually called — savings for infrequently called CSECTs

Useful also for interactive programs in which the decision to call a CSECT depends on the input

Usually done with an Operating System Service Request

In high level languages, dynamic linking may require the use of a Runtime Environment that is language sensitive.

For example, Parameter passing (call by address, call by value, etc.)

Type checking of parameters

Dynamic Linking Example

Through

(a ) Pass symbolic name of routine to be called to the Operating System  

(b) O.S. does a table lookup in the Library and loads (links) the routine into the program

(c ) O.S. passes control to the routine

(d) Routine executes and returns control back to the operating system.

This is so the O.S. can know that the memory is again available

• O.S. then returns back to the calling program

(e)If there are no intervening dynamic loads, another call to the routine does not require another load and link

Bootstrap Loaders

On initial power up (or reset) a very small absolute loader is available (e.g., on ROM) This loader loads additional code

This, in turn, loads additional loader or operating system code

Eventually the entire operating system is loaded and executing

The name comes from the expression "pulling yourself up by your bootstraps"

Thus, when starting an operating system, we say that we are "booting" the system

 

 

 

     

Macro Processors

Introduction

• Concept

A macro instruction is a notational convenience for the programmer.

It allows the programmer to write shorthand version of a program.

The macro processor replaces each macro invocation with the corresponding sequence of statements (a process known as macro expansion)

Macro Processor Tasks

• Recognize macro definitions

• Save the macro definition

• Recognize macro calls

• Expand macro calls

Macro Definition

• Simple string substitution

• parameter substitution

conditional macro expansion

• macro instruction defining macros 

 Macro vs. Subroutine

Macro

• the expansion is done in place each time the macro is invoked; so source statements repeat

• Subroutine

• the source statements in a subroutine appear in only one place.

 One Pass Macro Processor

Prerequisite

Every macro must be defined before it is called

Sub-procedures

macro definition: DEFINE

macro invocation: EXPAND 

begin {macro processor}

EXPANDING := FALSE

while OPCODE = 'END' do

begin GETLINE

PROCESSLINE

end {while}

end (macro processor)

procedure PROCESSLINE

begin

search NAMTAB for OPCODE

if found then

 EXPAND

else if OPCODE = 'MACRO' then

DEFINE

else write source line to expanded file

end {PROCESSLINE}

Nested Macros Definition

• Macro definition within macros

process macro definition during expansion time 

Allowing Nested Macro Definition

• Sub-procedures

Macro definition: DEFINE

 Macro invocation: EXPAND

• EXPAND may invoke DEFINE when it encounters a macro definition

procedure DEFINE

begin

enter macro name into NAMTAB

 enter macro prototype into DEFTAB

LEVEL: - 1

while LEVEL > 0 do

begin

GETLINE

 if this is not a comment line then

begin

substitute positional notation for perameters

enter line into DEFTAB

if OPCODE ='MACRO' than

LEVEL := LEVEL + 1

else if OPCODE: - 'MEND' then

LEVEL:= LEVEL - 1

end (l not comment)

and (while)

store in NAMTAD pointers to beginning and end of definition end (DEFINE)

procedure EXPAND

begin

EXPAND:- TRUE

get first Line  of macro definition [prototype) from DEFTAB

set up arguments from macro invocation in ARGTAB

while macro invocation to expanded file as a comment

while no: end of macro definition do

begin GETLINE

PROCESSLINE

end (while)

EXPANDING:= FALSE

end (EXPAND)

procedure GETLNE

begin

if EXPANDING then

begin

 get next line of macro definition from DEFTAB

 substitute arguments from ARGTAB for positional notation

and {if)

 else

read next line from input  file

end (GETLINE)

Conditional Macro Expansion

• Macro-time conditional statements

• IF-ELSE-ENDIF

 Macro-time variables

• any symbol that begins with the character & and that is not a macro parameter

• macro-time variables are initialized to 0

·         macro-time variables can be changed with their values using SET

&EORCK SET 1