What Is a Jump Table

What is a jump table?

A jump table can be either an array of pointers to functions or an array of machine code jump instructions. If you have a relatively static set of functions (such as system calls or virtual functions for a class) then you can create this table once and call the functions using a simple index into the array. This would mean retrieving the pointer and calling a function or jumping to the machine code depending on the type of table used.

The benefits of doing this in embedded programming are:

1. Indexes are more memory efficient than machine code or pointers, so there is a potential for memory savings in constrained environments.
2. For any particular function the index will remain stable and changing the function merely requires swapping out the function pointer.

If does cost you a tiny bit of performance for accessing the table, but this is no worse than any other virtual function call.

Jump Table Switch Case question

A jump table is an abstract structure used to transfer control to another location. Goto, continue, and break are similar, except they always transfer to a specific location instead of one possibility from many. In particular, this control flow is not the same as a function call. (Wikipedia's article on branch tables is related.)

A switch statement is how to write jump tables in C/C++. Only a limited form is provided (can only switch on integral types) to make implementations easier and faster in this common case. (How to implement jump tables efficiently has been studied much more for integral types than for the general case.) A classic example is Duff's Device.

However, the full capability of a jump table is often not required, such as when every case would have a break statement. These "limited jump tables" are a different pattern, which is only taking advantage of a jump table's well-studied efficiency, and are common when each "action" is independent of the others.

---

Actual implementations of jump tables take different forms, mostly differing in how the key to index mapping is done. That mapping is where terms like "dictionary" and "hash table" come in, and those techniques can be used independently of a jump table. Saying that some code "uses a jump table" doesn't imply by itself that you have O(1) lookup.

The compiler is free to choose the lookup method for each switch statement, and there is no guarantee you'll get one particular implementation; however, compiler options such as optimize-for-speed and optimize-for-size should be taken into account.

You should look into studying data structures to get a handle on the different complexity requirements imposed by them. Briefly, if by "dictionary" you mean a balanced binary tree, then it is O(log n); and a hash table depends on its hash function and collision strategy. In the particular case of switch statements, since the compiler has full information, it can generate a perfect hash function which means O(1) lookup. However, don't get lost by just looking at overall algorithmic complexity: it hides important factors.

JUMP Table close to the end of the .text section

This table is indeed called jump table. Remember that when you compile your code, the compiler doesn't know anything about about the address of the external symbols (like GetCurrentProcessId) in memory. So the op-code of the call will be something like 0xE8 00000000 (E8 is the op-code of the call but you can see that the address is null). However, the compiler creates a symbol table in the object file which is very useful to the linker (e.g., Microsoft linker).

When you link your code, the linker reads the symbol table and reads all the external symbols (like the API calls) and then creates a jump table (like the one you have) often at the end of the .text section. The jump table is in a form of:

jmp dword ptr ds:[Address of the FirstThunk in IMAGE_IMPORT_DESCRIPTOR]

and then, the linker modifies all the call instructions in your code to call the corresponding entry in the jump table.

When you load the binary file into the memory, it's the responsibility of the loader (e.g., Windows loader) to fill the FirstThunk field with the appropriate value in your import table.

With this approach and the collaboration between the compiler, linker, and loader, you can successfully use the external APIs and functions. You can read this post to better understand the jump table.

how can I reference it somehow programmatically, via PE sections or structures?

I don't think you can. This table is part of the .text section and there is no information in the headers about it. However, in a normal PE file (not packed or obfuscated), you can disassemble the .text section (no need to even load the binary into the memory), and look for all the instructions in the form of 0xFF25XXXXXXXX where XXXXXXXX is one of the FirstThunks in your IMPORT_IMAGE_DESCRIPTOR.

Difference between a lookup table and a jump table

If i'm not mistaking, a lookup table has pre calculated results in an array? so instead of writing code to calculate them you just return the array index? Sort of like a HashMap.

Correct. What's stored at that index could be data, or a pointer to data, or a pointer to a function etc etc.

A jump table is simply a look-up table where each index corresponds to a function, most commonly implemented in C as an array of function pointers.

Format of a jump table

Why then are there 3 columns (shouldn't it be 2?)

You didn't paste the real GDB output, which looked something like:

0x123450    0x000000000000134234    0x0000000000005f424
0x123460    0x0000000000001dd1ac    0x000000000000ef327

(the first column is different). In programming, details matter.

If you make the terminal narrower, then you'll get 2 columns, like this:

0x123450    0x000000000000134234
0x123458    0x0000000000005f424
0x123460    0x0000000000001dd1ac
0x123468    0x000000000000ef327

As KerrekSB suggested, read the GDB manual to understand what x does. Hint: the first column doesn't really matter -- it's where the table itself is stored.

---

Related Topics