llext: Trampoline table generation

[teburd]

Is your enhancement proposal related to a problem? Please describe. Currently the test case very specifically builds with -mlong-calls for arm and this is because llext doesn't yet support generating a trampoline table when needed.

Many archs, arm, xtensa, x86, support program counter relative function call like ops with reduced operand size, meaning the entire address space isn't accessible from this op codes operand. Linux deals with this by generating a trampoline table (or procedure lookup table, PLT) which lets the functions jump further away when needed while potentially still using fewer opcodes than the long call op codes. Long call opcodes may require several opcodes preceeding them such as loads and adds, only afterward jumping to the function address. This has a cost and is not optimal.

Describe the solution you'd like Provide an architecture specific way of iterating through the relocations that link to external functions, returning a count of the number of trampolines, count of unique trampolines, and the required size in bytes of the trampoline table.

When linking each symbol add or reuse a trampoline for each symbol. Mapping call sites to a particular trampoline entry will need to likely have some mapping of symbol index to trampoline index.

Describe alternatives you've considered Let the compiler always generate a PLT by passing the appropriate compile flags. While nice that we can get the compiler to always generate a procedure lookup table, and then update only that table with the symbols we need to link to, the number of size of op codes required is likely to be higher and less localized. Meaning every external symbol will have a high cost of non-local jumps.

[teburd]

@lyakh @pillo79 please comment or correct me if I'm wrong in any way here