Tuesday, 17 January 2012

Switch Blocks & Jump Tables

I didn't know how jump tables were assembled prior to starting this investigation, and as anyone interested in assembly code will testify, using Google doesn't really help very much. Jonathan Bartlett's excellent "Programming From The Ground Up" and Appendix C, "C Idioms In Assembly Language" sadly doesn't cover switch blocks, but Wikipedia turns out to have a good entry.

The gist of implementing a (basic) switch block in assembly is the creation of a jump table, which is basically way of hashing an input onto a target address. This is most easily done where there exists a compact key space, preferably with consecutive integer values - enum values spring to mind.

Wikipedia provides the following pseudo-code:
      validate x           # transform x to 0 (invalid) or 1,2,3, according to value
      y = x*4;             # multiply by branch instruction length (e.g. 4)
      goto next(y);        # branch into 'table' of branch instructions
                           # start of branch table
next: goto codebad;        # x==0  (invalid)
      goto codeone;        # x==1
      goto codetwo;        # x==2
      # ... rest of branch table
codebad:                   # deal with invalid input

The easiest way of seeing how this is done in assembly is to persuade a compiler to generate one for you in a higher-level language, and then poring over the objdump output. It's not great, as it elides labels but you can get a rough idea how it works. It turns out that gcc run with -O3 determined that the jump table was suboptimal and used a set of compare instructions, but using -O1 generated a jump table. Here's the abridged output of objdump -d from the main function:
0000000000400594 :
  400594:    sub    $0x8,%rsp                  # reserve 8 bytes of stack space
  400598:    mov    0x8(%rsi),%rdi             # Store the pointer to argv[0] in RDI
  40059c:    mov    $0xa,%edx                  # Move decimal 10 into EDX
  4005a1:    mov    $0x0,%esi                  # Set EDX = 0
  4005a6:    callq  400498 <strtol@plt>        # invoke strtol
  4005ab:    cmp    $0x4,%eax                  # Compare the result (in RAX) with 4
  4005ae:    ja     400627 <main+0x93>         # if above, jmp to the default case
  4005b0:    mov    %eax,%eax                  # align the instructions?
  4005b2:    jmpq   *0x400758(,%rax,8)         # <--jump to address at (0x400758 + (RAX*8)) 
  4005b9:    mov    $0x40073c,%esi
  4005be:    mov    $0x1,%edi
  4005c3:    mov    $0x0,%eax
  4005c8:    callq  400478 <__printf_chk@plt>
  4005cd:    jmp    40063b <main+0xa7>
  4005cf:    mov    $0x40073f,%esi             # set ESI = address of asciz '1\n'
  4005d4:    mov    $0x1,%edi                  # set EDI = 1
  4005d9:    mov    $0x0,%eax                  # set EAX = 0 (varargs count)
  4005de:    callq  400478 <__printf_chk@plt>  # call __printf_chk: int attribute_hidden __printf_chk (int flag, const char *fmt, ...)
  4005e3:    jmp    40063b <main+0xa7>         # jmp end of switch-block
  4005e5:    mov    $0x400742,%esi
  4005ea:    mov    $0x1,%edi
  4005ef:    mov    $0x0,%eax
  4005f4:    callq  400478 <__printf_chk@plt>
  4005f9:    jmp    40063b <main+0xa7>
  4005fb:    mov    $0x400745,%esi
  400600:    mov    $0x1,%edi
  400605:    mov    $0x0,%eax
  40060a:    callq  400478 <__printf_chk@plt>
  40060f:    jmp    40063b <main+0xa7>
  400611:    mov    $0x400748,%esi             # set ESI = address of asciz '4\n'
  400616:    mov    $0x1,%edi                  # set EDI = 1
  40061b:    mov    $0x0,%eax                  # set EAX = 0 (varargs count)
  400620:    callq  400478 <__printf_chk@plt>  # call __printf_chk
  400625:    jmp    40063b <main+0xa7>
  400627:    mov    $0x40074b,%esi
  40062c:    mov    $0x1,%edi
  400631:    mov    $0x0,%eax
  400636:    callq  400478 <__printf_chk@plt>
  40063b:    mov    $0x0,%eax
  400640:    add    $0x8,%rsp
  400644:    retq   


The line which does the magic is at 4005b2 and gives away the location of the jump table: the address 0x400758. We can examine that in gdb:
(gdb) x/5a 0x400758
0x400758:    0x4005b9 
0x400760:    0x4005cf 
0x400768:    0x4005e5 
0x400780:    0x4005fb 
0x400778:    0x400611 

You can see here how 8-byte (quadword) increments from 0x400758 contain the addresses of the target instructions in the above code. Match them up if you like to the instruction addresses on the left.

We can get the same information by using objdump (albeit in awkward the little-endian format). Note the values from address 0x400758. You can see almost more clearly here how the target addresses are arranged consecutively in memory:
$ objdump -s -j .rodata switch

switch:     file format elf64-x86-64

Contents of section .rodata:
 400738 01000200 300a0031 0a00320a 00330a00  ....0..1..2..3..
 400748 340a0044 65666175 6c740a00 00000000  4..Default......
 400758 b9054000 00000000 cf054000 00000000  ..@.......@.....
 400768 e5054000 00000000 fb054000 00000000  ..@.......@.....
 400778 11064000 00000000                    ..@.....   

Well, that's how it's arranged in memory, and we can see the technique used to construct the jmp target, but how do you write that? Well, here's one I put together to find out:

asmswitch.s
-------------------------------8<-------------------------------
.section .rodata
output_str:
 .asciz   "Multiple is %d\n"
default_str:
 .asciz   "Argument value '%d' is out of range.\n"

.section .text

.globl _start

_start:

 movq     %rsp, %rbp           # Store base pointer
 
 # Convert first program argument to integer
 leaq     0x10(%rbp), %rdi     # set RDI = RBP + sizeof(2 quadwords)
 movq     (%rdi), %rdi         # dereference argv[0]: set RDI = address of first character
 call     atoi                 # convert input string to integer
 
 # Some pseudo-code to help understand what's going on
 # if arg > max || arg <= 0 then goto default
 # address = lookup(arg)
 # jump address
 # default: 
 #    default_stuff
 #    jump end
 # option_1:
 #    option_1_stuff
 #    jump print
 # ...
 # print value
 # end

 cmp      $0, %rax             # Test whether less than or equal to zero
 jle      .Ldefault

 cmp      $4, %rax             # Test whether above 4
 ja       .Ldefault          
 
 jmp      *branch_tbl(,%rax,8) # branch to the address stored at this memory location

.section .rodata
branch_tbl:
 .quad    0                    # base + (0 * 8) are padding-bytes
 .quad    .Loption_1_impl      # base + (1 * 8) references label .Loption_1_impl     
 .quad    .Loption_2_impl      # base + (2 * 8) references label .Loption_2_impl     
 .quad    .Loption_3_impl      # Can you see where this is going? 
 .quad    .Loption_4_impl
.section .text

.Ldefault:
        # print the alternate out-of-range message. 
        # call printf(char* msg, ...)
 movq     $default_str, %rdi   # RDI: address of default_str[0]
 movq     %rax, %rsi           # RSI: the input value
 movq     $1, %rax             #  AL: the number of varargs
 call     printf
 jmp      .Lswitch_block_end   # Jump past the switch block
 
.Loption_1_impl:
 movq     $10, %rsi            # set RSI = 10
 jmp      .Lprint_stmt         # Jump to the call to printf
 
.Loption_2_impl:
 movq     $20, %rsi            # set RSI = 20, as above
 jmp      .Lprint_stmt         # Jump to the call to printf
 
.Loption_3_impl:
 movq     $30, %rsi            # ... etc
 jmp      .Lprint_stmt
 
.Loption_4_impl:
 movq     $40, %rsi            # Fall-through (no jmp) to .Lprint_stmt
 
.Lprint_stmt:
 # Print the message for values 1-4 inclusive, using the 
 # argument set in the switch block
 movq   $output_str, %rdi
 movq   $1, %rax               # varargs count
 call   printf
 
.Lswitch_block_end:
        
        # Call sys_exit
 movq     $60, %rax            #   RAX: id of sys_exit
 movq     $0, %rdi             #   RDI: exit-status
 syscall
-------------------------------8<-------------------------------

Of course, you don't have to interrupt your .text section with another .rodata section, but in larger programs it's likely to be easier to keep the jump table near the relevant code. So it seems that the key is to use a label to identify a position in the instructions and have the compiler write that value into an offset from a symbol. Do that repeatedly in a deterministic way and you can write a function to map input values onto them.

Makefile
-------------------------------8<-------------------------------

all: asmswitch

asmswitch: asmswitch.o
 ld --dynamic-linker /lib/ld-linux-x86-64.so.2 -o asmswitch asmswitch.o -lc

asmswitch.o: asmswitch.s
 as -gstabs -o asmswitch.o asmswitch.s

clean:
 rm -f *.o asmswitch

-------------------------------8<-------------------------------

No comments:

Post a Comment