An Example of Relocation and Linking

Here are the source code and the symbol table of a short module

jimmy@CSCI250-debian:~$ cat umpsxt/share/umps2/crtso.S
        lw      $k0, BUS_REG_RAM_BASE
        lw      $k1, BUS_REG_RAM_SIZE
        addu    $k0, $k0, $k1
        addiu   $sp, $k0, -8
        lw      $gp, CORE_TEXT_VADDR + (AOUT_HE_GP_VALUE << 2)
        addiu   $sp, $sp, -16
        jal     main
        addiu   $sp, $sp, 16
        li      $a0, BIOS_SRV_HALT

jimmy@CSCI250-debian:~/umpsxt/hello-umps$ mipsel-elf-nm crtso.o 
         U main        # main is used by this module but is undefined
00000000 T __start     # __start is in the text segment and at address 0

And here is the same code after being assembled and then disassembled

jimmy@CSCI250-debian:~/umpsxt/hello-umps$ mipsel-elf-objdump -d crtso.o 
crtso.o:     file format elf32-littlemips
Disassembly of section .text:
00000000 <__start>:
   0:	3c1a1000 	lui	k0,0x1000
   4:	8f5a0000 	lw	k0,0(k0)
   8:	3c1b1000 	lui	k1,0x1000
   c:	8f7b0004 	lw	k1,4(k1)
  10:	00000000 	nop
  14:	035bd021 	addu	k0,k0,k1
  18:	275dfff8 	addiu	sp,k0,-8
  1c:	3c1c2000 	lui	gp,0x2000
  20:	8f9c10a8 	lw	gp,4264(gp)
  24:	27bdfff0 	addiu	sp,sp,-16
  28:	0c000000 	jal	0 <__start>  # disassembler goofed here: this jal calls main, not __start
  2c:	00000000 	nop
  30:	27bd0010 	addiu	sp,sp,16
  34:	24040003 	li	a0,3
  38:	00000000 	nop
  3c:	0000000d 	break
  40:	00000000 	nop

Let's see what we can learn from looking at these displays

Here are the symbol tables for hello.o and libumps.o

jimmy@CSCI250-debian:~/umpsxt/hello-umps$ mipsel-elf-nm hello.o | sort
00000000 d term0_reg
00000000 T main
00000040 t term_puts
000000c4 t term_putchar
000001b8 t tx_status
         U WAIT

jimmy@CSCI250-debian:~/umpsxt/hello-umps$ mipsel-elf-nm libumps.o | sort
00000000 T SYSCALL
00000014 T getINDEX
00000028 T getRANDOM
0000003c T getENTRYLO
00000050 T getBADVADDR
00000064 T getTIMER
00000078 T getENTRYHI
0000008c T getSTATUS
000000a0 T getCAUSE
000000b4 T getEPC
000000c8 T getPRID
000000dc T setINDEX
000000f8 T setENTRYLO
00000114 T setTIMER
00000130 T setENTRYHI
0000014c T setSTATUS
00000168 T setCAUSE
00000184 T TLBWR
00000198 T TLBWI
000001ac T TLBP
000001c0 T TLBR
000001d4 T TLBCLR
000001e8 T WAIT
000001fc T CAS
0000020c T FORK
000002a0 T STST
00000360 T HALT
00000374 T PANIC
00000388 T LDST
000003a0 T INITCPU


Here's the symbol table from "kernel"; it was created by linking hello.o, crtso.o, and libumps.o in that order

Let's see what we can learn from it.

jimmy@CSCI250-debian:~/umpsxt/hello-umps$ mipsel-elf-nm kernel | sort
20001000 T _ftext
200010b0 T main
200010f0 t term_puts
20001174 t term_putchar
20001268 t tx_status
200012a0 T __start
200012e4 T SYSCALL
200012f8 T getINDEX
2000130c T getRANDOM
20001320 T getENTRYLO
20001334 T getBADVADDR
20001348 T getTIMER
2000135c T getENTRYHI
20001370 T getSTATUS
20001384 T getCAUSE
20001398 T getEPC
200013ac T getPRID
200013c0 T setINDEX
200013dc T setENTRYLO
200013f8 T setTIMER
20001414 T setENTRYHI
20001430 T setSTATUS
2000144c T setCAUSE
20001468 T TLBWR
2000147c T TLBWI
20001490 T TLBP
200014a4 T TLBR
200014b8 T TLBCLR
200014cc T WAIT
200014e0 T CAS
200014f0 T FORK
20001584 T STST
20001644 T HALT
20001658 T PANIC
2000166c T LDST
20001684 T INITCPU
20002000 D _fdata
20002000 d term0_reg
20002004 B _end
20002004 D __bss_start
20002004 D _edata
20002004 D _fbss
20002800 D _gp


Here is a disassembly of hello.o

The main thing that we learn from it is that the size of the text segment is 0x1f0.

jimmy@CSCI250-debian:~/umpsxt/hello-umps$ mipsel-elf-objdump -d hello.o
hello.o:     file format elf32-littlemips
Disassembly of section .text:
00000000 <main>:
   0:	27bdffe8 	addiu	sp,sp,-24
   4:	afbf0014 	sw	ra,20(sp)
   8:	afbe0010 	sw	s8,16(sp)
   c:	03a0f025 	move	s8,sp
  10:	3c020000 	lui	v0,0x0
  14:	24440000 	addiu	a0,v0,0
  18:	0c000010 	jal	40 <term_puts>
  1c:	00000000 	nop
  20:	0c000000 	jal	0 <main>  # disassembler goofed here: this jal calls WAIT, not main
  24:	00000000 	nop
  28:	3c021000 	lui	v0,0x1000
  2c:	34420514 	ori	v0,v0,0x514
  30:	240300ff 	li	v1,255
  34:	ac430000 	sw	v1,0(v0)
  38:	1000ffff 	b	38 <main+0x38>
  3c:	00000000 	nop
00000040 <term_puts>:
  40:	27bdffe8 	addiu	sp,sp,-24
  44:	afbf0014 	sw	ra,20(sp)
  48:	afbe0010 	sw	s8,16(sp)
  4c:	03a0f025 	move	s8,sp
  50:	afc40018 	sw	a0,24(s8)
  54:	1000000c 	b	88 <term_puts+0x48>
  58:	00000000 	nop
  5c:	8fc20018 	lw	v0,24(s8)
  60:	00000000 	nop
  64:	24430001 	addiu	v1,v0,1
  68:	afc30018 	sw	v1,24(s8)
  6c:	80420000 	lb	v0,0(v0)
  70:	00000000 	nop
  74:	00402025 	move	a0,v0
  78:	0c000031 	jal	c4 <term_putchar>
  7c:	00000000 	nop
  80:	14400009 	bnez	v0,a8 <term_puts+0x68>
  84:	00000000 	nop
  88:	8fc20018 	lw	v0,24(s8)
  8c:	00000000 	nop
  90:	80420000 	lb	v0,0(v0)
  94:	00000000 	nop
  98:	1440fff0 	bnez	v0,5c <term_puts+0x1c>
  9c:	00000000 	nop
  a0:	10000002 	b	ac <term_puts+0x6c>
  a4:	00000000 	nop
  a8:	00000000 	nop
  ac:	03c0e825 	move	sp,s8
  b0:	8fbf0014 	lw	ra,20(sp)
  b4:	8fbe0010 	lw	s8,16(sp)
  b8:	27bd0018 	addiu	sp,sp,24
  bc:	03e00008 	jr	ra
  c0:	00000000 	nop
000000c4 <term_putchar>:
  c4:	27bdffe0 	addiu	sp,sp,-32
  c8:	afbf001c 	sw	ra,28(sp)
  cc:	afbe0018 	sw	s8,24(sp)
  d0:	03a0f025 	move	s8,sp
  d4:	00801025 	move	v0,a0
  d8:	a3c20020 	sb	v0,32(s8)
  dc:	3c020000 	lui	v0,0x0
  e0:	8c420000 	lw	v0,0(v0)
  e4:	00000000 	nop
  e8:	00402025 	move	a0,v0
  ec:	0c00006e 	jal	1b8 <tx_status>
  f0:	00000000 	nop
  f4:	afc20010 	sw	v0,16(s8)
  f8:	8fc30010 	lw	v1,16(s8)
  fc:	24020001 	li	v0,1
 100:	10620008 	beq	v1,v0,124 <term_putchar+0x60>
 104:	00000000 	nop
 108:	8fc30010 	lw	v1,16(s8)
 10c:	24020005 	li	v0,5
 110:	10620004 	beq	v1,v0,124 <term_putchar+0x60>
 114:	00000000 	nop
 118:	2402ffff 	li	v0,-1
 11c:	10000020 	b	1a0 <term_putchar+0xdc>
 120:	00000000 	nop
 124:	3c020000 	lui	v0,0x0
 128:	8c420000 	lw	v0,0(v0)
 12c:	83c30020 	lb	v1,32(s8)
 130:	00000000 	nop
 134:	00031a00 	sll	v1,v1,0x8
 138:	34630002 	ori	v1,v1,0x2
 13c:	ac43000c 	sw	v1,12(v0)
 140:	00000000 	nop
 144:	3c020000 	lui	v0,0x0
 148:	8c420000 	lw	v0,0(v0)
 14c:	00000000 	nop
 150:	00402025 	move	a0,v0
 154:	0c00006e 	jal	1b8 <tx_status>
 158:	00000000 	nop
 15c:	afc20010 	sw	v0,16(s8)
 160:	8fc30010 	lw	v1,16(s8)
 164:	24020003 	li	v0,3
 168:	1062fff6 	beq	v1,v0,144 <term_putchar+0x80>
 16c:	00000000 	nop
 170:	3c020000 	lui	v0,0x0
 174:	8c420000 	lw	v0,0(v0)
 178:	24030001 	li	v1,1
 17c:	ac43000c 	sw	v1,12(v0)
 180:	8fc30010 	lw	v1,16(s8)
 184:	24020005 	li	v0,5
 188:	10620004 	beq	v1,v0,19c <term_putchar+0xd8>
 18c:	00000000 	nop
 190:	2402ffff 	li	v0,-1
 194:	10000002 	b	1a0 <term_putchar+0xdc>
 198:	00000000 	nop
 19c:	00001025 	move	v0,zero
 1a0:	03c0e825 	move	sp,s8
 1a4:	8fbf001c 	lw	ra,28(sp)
 1a8:	8fbe0018 	lw	s8,24(sp)
 1ac:	27bd0020 	addiu	sp,sp,32
 1b0:	03e00008 	jr	ra
 1b4:	00000000 	nop
000001b8 <tx_status>:
 1b8:	27bdfff8 	addiu	sp,sp,-8
 1bc:	afbe0004 	sw	s8,4(sp)
 1c0:	03a0f025 	move	s8,sp
 1c4:	afc40008 	sw	a0,8(s8)
 1c8:	8fc20008 	lw	v0,8(s8)
 1cc:	00000000 	nop
 1d0:	8c420008 	lw	v0,8(v0)
 1d4:	00000000 	nop
 1d8:	304200ff 	andi	v0,v0,0xff
 1dc:	03c0e825 	move	sp,s8
 1e0:	8fbe0004 	lw	s8,4(sp)
 1e4:	27bd0008 	addiu	sp,sp,8
 1e8:	03e00008 	jr	ra
 1ec:	00000000 	nop


Here's a picture, constructed from the information on this page, of the executable module named "kernel". Notice how all the numbers match up with that information.

Now let's satisfy ourselves about the jal instructions:

jimmy@CSCI250-debian:~/umpsxt/hello-umps$ mipsel-elf-objdump -d kernel | grep jal
200010c8:       0c00043c        jal     200010f0 <term_puts>
200010d0:       0c000533        jal     200014cc <WAIT>
20001128:       0c00045d        jal     20001174 <term_putchar>
2000119c:       0c00049a        jal     20001268 <tx_status>
20001204:       0c00049a        jal     20001268 <tx_status>
200012c8:       0c00042c        jal     200010b0 <main>