writing a jump table

writing a jump table

[Nicolas Bock]

[-- Attachment #1: Type: text/plain, Size: 1620 bytes --]

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


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 262 bytes --]

Re: writing a jump table

[Brian Raiter]

> 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.

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

Re: writing a jump table

[Nicolas Bock]

[-- Attachment #1: Type: text/plain, Size: 772 bytes --]

Hi Brian,

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

nick


On 03/15/11 18:25, Brian Raiter wrote:
>> 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.
> 
> 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
> --
> To unsubscribe from this list: send the line "unsubscribe linux-assembly" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 262 bytes --]

Re: writing a jump table

[Frank Kotler]

Nicolas Bock wrote:
> Hi Brian,
> 
> yes, I compiled it and when I run the code it segfaults.

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

Best,
Frank

Re: writing a jump table

[Nicolas Bock]

[-- Attachment #1: Type: text/plain, Size: 408 bytes --]

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


On Wednesday, March 16, 2011, Frank Kotler <fbkotler@zytor.com> wrote:
> Nicolas Bock wrote:
>
> Hi Brian,
>
> yes, I compiled it and when I run the code it segfaults.
>
>
> Don't you need 64-bit addresses in your jump-table for 64-bit code?
>
> Best,
> Frank
>
>
>


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 262 bytes --]

Re: writing a jump table

[Nicolas Bock]

[-- Attachment #1: Type: text/plain, Size: 1954 bytes --]

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


On 03/15/11 18:25, Brian Raiter wrote:
>> 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.
> 
> 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
> --
> To unsubscribe from this list: send the line "unsubscribe linux-assembly" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 262 bytes --]

Re: writing a jump table

[Nicolas Bock]

[-- Attachment #1: Type: text/plain, Size: 1642 bytes --]

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


On 03/15/11 18:25, Brian Raiter wrote:
>> 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.
> 
> 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
> --
> To unsubscribe from this list: send the line "unsubscribe linux-assembly" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 262 bytes --]

Re: writing a jump table

[Brian Raiter]

> 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.

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

Re: writing a jump table

[Nicolas Bock]

[-- Attachment #1: Type: text/plain, Size: 940 bytes --]

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.

On 03/16/11 20:23, Brian Raiter wrote:
>> 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.
> 
> 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


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 262 bytes --]

Fwd: writing a jump table

[Hendrik Visage]

---------- Forwarded message ----------
From: Hendrik Visage <hvjunk@gmail.com>
Date: Thu, Mar 17, 2011 at 9:49 AM
Subject: Re: writing a jump table
To: Nicolas Bock <nicolasbock@gmail.com>
Cc: Brian Raiter <breadbox@muppetlabs.com>, linux-assembly@vger.kernel.org




On Thu, Mar 17, 2011 at 4:26 AM, Nicolas Bock <nicolasbock@gmail.com> wrote:
>
> 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.

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

>
> 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.

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.



>
> On 03/16/11 20:23, Brian Raiter wrote:
> >> 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.
> >
> > 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
>