writing a jump table

Hello list,

I am trying to write a jump table, but unfortunately with limited success. When I compile the code and disassemble it, the offset of "table" is 0, which I guess means that something didn't work out. Any help would be gratefully appreciated.

The assembly code, jump_table.S:

.text
.global jump_table
.type jump_table, @function

jump_table:
push %rax

mov $0x02, %rax # Move index into rax; 2 is supposed to end up at
label_02.
jmp *table(, %rax, 4) # Jump into the table.

.align 8
table:
.long label_00
.long label_01
.long label_02

label_00:
nop

label_01:
nop

label_02:
nop

done:
pop %rax
ret

.size jump_table, .-jump_table

compiled with: gcc -c -g -o jump_table.o jump_table.S

disassembled code:

(gdb) disassemble jump_table
Dump of assembler code for function jump_table:

   0x0000000000000000 <+0>:     push   %rax
   0x0000000000000001 <+1>:     mov    $0x2,%rax
   0x0000000000000008 <+8>:     jmpq   *0x0(,%rax,4)
   0x000000000000000f <+15>:    nop
   0x0000000000000010 <+16>:    add    %al,(%rax)
   0x0000000000000012 <+18>:    add    %al,(%rax)
   0x0000000000000014 <+20>:    add    %al,(%rax)
   0x0000000000000016 <+22>:    add    %al,(%rax)
   0x0000000000000018 <+24>:    add    %al,(%rax)
   0x000000000000001a <+26>:    add    %al,(%rax)
   0x000000000000001c <+0>:     nop
   0x000000000000001d <+0>:     nop
   0x000000000000001e <+0>:     nop
   0x000000000000001f <+0>:     pop    %rax
   0x0000000000000020 <+1>:     retq

End of assembler dump.

Thanks already, nick

Actually, table appears immediately following your indirect jump instruction, so I would assume that the offset would be zero. Did you actually try this code to verify that it doesn't do what you expect?

b

Hi Brian,

yes, I compiled it and when I run the code it segfaults.

nick

Don't you need 64-bit addresses in your jump-table for 64-bit code?

Best,
Frank

Hi frank

Honestly I don't know. I don't have a lot of assembly experience and this is all pretty new to me.

nick

Using a larger switch statement in C, I looked at the code that gcc produces and changed a few things in my assembly function. It now looks like below. This function works now, it actually jumps to label_02. When I try to put that function into a project that uses libtool to build a dynamic library however, I get the following linking error:

/usr/lib/gcc/x86_64-pc-linux-gnu/4.4.5/../../../../x86_64-pc-linux-gnu/bin/ld:
./.libs/libspamm_kernel.a(jump_table.o): relocation R_X86_64_32S against `.rodata' can not be used when making a shared object; recompile with -fPIC ./.libs/libspamm_kernel.a(jump_table.o): could not read symbols: Bad value

What does this error mean?

Thanks,

nick

jump_table.S:

.text
.global jump_table
.type jump_table, @function

jump_table:
# Push stack pointer so we can make room for local storage. push %rax

mov $0x02, %rax # Move index into rax; 2 is supposed to end up at
label_02.
jmp *table(, %rax, 8) # Jump into the table.

.section .rodata
.align 8
table:
.quad label_00
.quad label_01
.quad label_02

.text
label_00:
jmp done

label_01:
jmp done

label_02:
jmp done

done:
pop %rax
ret

.size jump_table, .-jump_table

I think I figured it out now. I used gcc to compile PIC for the C switch statement and checked what it does. I don't fully understand it to be honest, but it seems to do the job also for non PIC code. For posterity, here is the code:

.text
.global jump_table
.type jump_table, @function

jump_table:
# Push stack pointer so we can make room for local storage. push %rax

mov $0x02, %rax # Move index into rax; 2 is supposed to end up at
label_02.

lea 0(,%rax, 4), %rdx
lea table(%rip), %rax
mov (%rdx, %rax), %edx
movslq %edx, %rdx
lea table(%rip), %rax
lea (%rdx, %rax), %rax
jmp *%rax

.section .rodata
.align 4
table:
.long label_00-table
.long label_01-table
.long label_02-table
.long label_03-table

.text
label_00:
jmp done

label_01:
jmp done

label_02:
jmp done

label_03:
jmp done

done:
pop %rax
ret

.size jump_table, .-jump_table

Of course -- PIC code just means that the code doesn't assume it knows where it's located in memory, which for a shared-object library is a necessary thing. It does mean the code has to jump through a few more hoops, which is why the compiler doesn't make it the default.

b

But how does non-PIC code where it is in memory? When I disassemble the non-PIC version, the address space starts at 0 which must mean that the linker relocates the code. Also, labels represent offsets if I understand this correctly, which is also a relative address and not an absolute. That's what I meant with that I don't fully understand why these extra hoops are necessary.

---------- Forwarded message ----------
From: Hendrik Visage <[email protected]>
Date: Thu, Mar 17, 2011 at 9:49 AM
Subject: Re: writing a jump table
To: Nicolas Bock <[email protected]>
Cc: Brian Raiter <[email protected]>, [email protected]

non-PIC code would typically start at the start of the address space for that platform.

PIC code can be put anywhere in address space. So let's assume a few things:

START_ADDR: The starting point of the platform's address space for code/data/etc.

LABEL_OFFSET: The offset for that LABEL inside the code/data relative from 0 for the code/data when just normally assembled.

Now in the non-PIC case, it is "easy" to find the actual place in address space: START_ADDR + LABEL_OFFSET, and this could be hard coded during the static linking phase.

But in the PIC case, we also have:

PIC_OFFSET_CODE_SEG_A: The offset from START_ADDR where the RUNTIME linker put the code for CODE_SEG_A. This is unknown till the code actually gets executed. Okay, in *nost* cases you would find it is the same place everytime, for a given piece of compiled code, but never bargain on that, especially when you have hardened kernels that would randomly assign address space offsets to frustrate crackers.

Now instead of a fixed calculated START_ADDR+PIC_OFFSET_CODE_SEG_A + LABEL_OFFSET or compile/link time, we now have to calculate that value at RUNTIME, as PIC_OFFSET_CODE_SEG_A could be different for each execution.

That is a layman's description as I understand it, and I definitely miss some other implementation details, but that is the gist of why you need those extra hoops for PIC code.