Pass 1 of Two-Pass Linking Loader

A linking loader is software that combines object code (machine code) modules and prepares them for execution. The process occurs in two passes:

Pass 1 gathers essential information about the program, resolves external references, and prepares tables for the linking and loading in Pass 2. It does not perform memory allocation or code generation but prepares data structures necessary for the linking process.

Description of Pass 1 of Two-Pass Linking Loader

Pass 1 analyzes the object code modules, resolves external references, and builds the necessary information for the final linking and loading in Pass 2. The tasks during Pass 1 include:

• Read and Analyze Object Code: The loader reads object code modules, including machine code and relocation information, and prepares them for further processing.

• Build the Symbol Table: A symbol table is created, storing all the symbols (such as variables and functions) along with their memory addresses or offsets. This table also records undefined symbols for later resolution.

• Identify External References: The loader identifies and records external references—symbols or addresses that are defined in other modules, which will be resolved during Pass 2.

• Resolve Internal References: Internal references (symbols defined within the same module) are assigned relative addresses. These addresses are adjusted later in Pass 2.

• Prepare Relocation Information: The loader generates relocation information, which specifies the instructions and data that need to be modified to reflect final memory addresses.

• Generate the Load Map: A load map is created, which details where each module, symbol, and piece of data will reside in memory once the program is loaded.

Pass 1 prepares all the necessary data structures and resolves references between modules, ensuring that linking and loading can proceed in Pass 2.

Algorithm

Pass 1:

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}

Code Example:

#include

#include

struct estab

{

    char csname[10];

    char extsym[10];

    int address;

    int length;

} es[20];

void main()

{

    char input[10], name[10], symbol[10], ch;  

    int count = 0, progaddr, csaddr, add, len;

    FILE *fp1, *fp2;

    fp1 = fopen("input.txt", "r");

    fp2 = fopen("output.txt", "w");

    printf("\n\nEnter the address where the program has to be loaded : ");

    scanf("%x", &progaddr);

    csaddr = progaddr;

    fscanf(fp1, "%s", input);

    while (strcmp(input, "END") != 0)

    {

        if (strcmp(input, "H") == 0)

        {

            fscanf(fp1, "%s", name);

            strcpy(es[count].csname, name);

            strcpy(es[count].extsym, "  ");

            fscanf(fp1, "%x", &add);

            es[count].address = add + csaddr;

            fscanf(fp1, "%x", &len);

            es[count].length = len;

            fprintf(fp2, "%s ** %x %x\n", es[count].csname, es[count].address, es[count].length);

            count++;

        }

        else if (strcmp(input, "D") == 0)

        {

            fscanf(fp1, "%s", input);

            while (strcmp(input, "R") != 0)

            {

                strcpy(es[count].csname, "  ");

                strcpy(es[count].extsym, input);

                fscanf(fp1, "%x", &add);

                es[count].address = add + csaddr;

                es[count].length = 0;

                fprintf(fp2, "** %s %x\n", es[count].extsym, es[count].address);

                count++;

                fscanf(fp1, "%s", input);

            }

            csaddr = csaddr + len;

        }

        else if (strcmp(input, "T") == 0)

        {

            while (strcmp(input, "E") != 0)

                fscanf(fp1, "%s", input);

        }

        fscanf(fp1, "%s", input);

    }

    fclose(fp1);

    fclose(fp2);

    fp2 = fopen("output.txt", "r");

    ch = fgetc(fp2);

    while (ch != EOF)

    {

        printf("%c", ch);

        ch = fgetc(fp2);

    }

    fclose(fp2);

}

Sample Input and Output Cases

Input:

H PROGA 000000 000063

D LISTA 000054 ENDA 000064

R LISTB ENDB LISTC ENDC

T 000020 0A 03201D 77100004 050014

T 000054 0F 100014 000008 004051 000004 100000

M 000024 05 +LISTA

M 000054 06 +LISTC

M 000060 06 +LISTB

M 000060 06 -LISTA

E 000020

H PROGB 000000 00007F

D LISTB 000060 ENDB 000070

R LISTA LISTC ENDY

T 000036 0B 03100000 772027 05100000

T 000070 OF 100000 000008 004051 000004 100060

M 000037 05 +LISTA

M 00003E 05 -LISTA

M 000070 06 -LISTA

M 000070 06 +LISTC

M 00007C 06 +PROGB

M 00007C 06 -LISTA

E 000000

H PROGC 000000 000051

D LISTC 000030 ENDC 000042

R LISTA LISTB ENDB

T 000018 0C 03100000 77100004 05100000

T 000042 OF 100030 000008 004051 000004 100000

M 00001D 05 +LISTB

M 000021 05 -LISTA

M 000042 06 -LISTA

M 000042 06 +PROGC

M 00004E 06 +LISTB

M 00004E 06 -LISTA

E

END

Output:

** PROGA 000000 000063

** LISTA 000054

** ENDA 000064

** LISTB 000060

** ENDB 000070

** LISTC 000030

** ENDC 000042

** PROGB 000000 00007F

** LISTB 000060

** ENDB 000070

** LISTA 000036

** LISTC 000070

** ENDY 000036

** PROGC 000000 000051

** LISTC 000030

** ENDC 000042