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 inputThe 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
10x400758: 0x4005b9
0x400760: 0x4005cf
0x400768: 0x4005e5
0x400780: 0x4005fb
0x400778: 0x400611 - 1
-
address to jump to, i.e.
0x4005b9
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
.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
syscallOf 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
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