Lecture 7 - MERL, Linking

Thursday, June 19, 2014

4:51 PM



    Important Recall:


    •        .word id – add alpha to id

    •        .word constant – do not relocate

    •        anything else – do not relocate (including beq, bne)


    OS 3.0



    P <- next program to run

    $3 <- load-and-relocate (P)

    jalr $3

    beq $0, $0, repeat


    Problem – assembled file is a stream of bits

    • how do we know which come from .word (with an id!) and which are instructions?
    • we cant! We need more info from the assembler. The output of most assemblers is not pure machine code. It is object code.


    Object file – contains binary code AND auxiliary info needed by the loader (and later, the linker)


    Our object file format: MERL

    • (MIPS Executable Relocatable Linkable)


    What do we need to put into our object file?

    • the code
    • which lines of the code (addresses) were originally .word id?


    Important MERL format



    0x1000002                        ;cookie (sanity check: is MERL)

    [size of file]                ;header + MIPS + Symbol table

    [cod length]                ;header + MIPS

    MIPS Binary




    Symbol Table
    (relocation table)

    [format code]                ;= 1 for relocation entries

    [address]                        ;addr in MIPS of relocatable word

    [format code]



    * Note: 0x10000002 is MIPS for beq $0, $0, 2 (the command to skip the header)

    • so MERL files can be executed as ordinary MIPS programs (if loaded at 0x00)
    • want the assembler to generate relocatable object code cs241.relasm


    Assembly language:



    beq $0, $0, 2

    .word endmodule

    .word endnode

    lis $3

    .word 0xabc

    lis $1


    .word A


    jr $31


    beq $0, $0, B


    .word B


    .word 0x1

    .word reloc1


    .word reloc2



    Relocation tool: cs241.merl

    • input: MERL file and relocation address alpha
    • output: non-relocatable MIPS file with MERL header + footer removed, ready to load at alpha.


    mips.twopoints, mips.array – optional 2nd argument = address at which to load the MIPS file.



    – load myobj.merl at 0x10000

    java cs241.merl 0x10000 < myobj.merl > myobj.mips

    java mips.twopoints myobj.mips 0x10000


    Relocation – typically done by the loader


    Loader relocation algorithm

    read()                                        //skip cookie

    endMod <- read()                                //end of MERL file

    codeLen <- read() – 12                //length of code (minus header)

    alpha <- findFreeRAM(codeLen + stack)

    for (i=0, i < codeLen; i+=4)

    MEM[alpha + i] <- read()

    i <- codeLen + 12

    while (i < endMod)

    format <- read()

    if (format == 1)

    rel <- read()                //address to be relocated. This is relative

      //to the header, not start of the code

    MEM[alpha + rel - 12] += alpha – 12

    // alpha + rel – 12 = actual location                                                                   //header not included

    // alpha = adjust forward by alpha

    // backward by header length because header

      //is not loaded

    else ERROR

    i += 8



    If you want reloadable code, always use labels to specific jump targets.

    • Potential problems
      • if you use a label for arithmetic operations


    Important Linkers

    Convenient to split MIPS programs into smaller units

    Issues – how can the assembler resolve a reference to a label in a different file? (a.asm, b.asm, c.asm)


    Solution 1: Concatenate the files and then assemble.

    cat a.asm b.asm c.asm | java cs241.binasm

    • This will work – but… Why should we have to assemble these files more than once?


    Question Can we assemble first + then cat?

    • the output needs to be relocatable – at most one piece can reside at address 0. Therefore we need to assemble to MERL, not just MIPS
    • catting two MERL files doesn’t yield a MERL file


    Solution 2: Need a tool that understands MERL files and puts them together intelligently. A linker.

    • but still – what should the assembler do with references to labels it can’t find?
      • need to change the assembler
    • when the assembler encounters .word id, where label id is not found, output 0, and indicate that the value of id is needed before the program can run.
    • How?





Created with Microsoft OneNote 2010
One place for all your notes and information