How to do computations with addresses at compile/linking time?

Question

I wrote some code for initializing the IDT, which stores 32-bit addresses in two non-adjacent 16-bit halves. The IDT can be stored anywhere, and you tell the CPU where by running the LIDT instruction.

This is the code for initializing the table:

void idt_init(void) {
    /* Unfortunately, we can't write this as loops. The first option,
     * initializing the IDT with the addresses, here looping over it, and
     * reinitializing the descriptors didn't work because assigning a
     * a uintptr_t (from (uintptr_t) handler_func) to a descr (a.k.a.
     * uint64_t), according to the compiler, "isn't computable at load
     * time."
     * The second option, storing the addresses as a local array, simply is
     * inefficient (took 0.020ms more when profiling with the "time" command
     * line program!).
     * The third option, storing the addresses as a static local array,
     * consumes too much space (the array will probably never be used again
     * during the whole kernel runtime).
     * But IF my argument against the third option will be invalidated in
     * the future, THEN it's the best option I think. */

    /* Initialize descriptors of exception handlers. */
    idt[EX_DE_VEC] = idt_trap(ex_de);
    idt[EX_DB_VEC] = idt_trap(ex_db);
    idt[EX_NMI_VEC] = idt_trap(ex_nmi);
    idt[EX_BP_VEC] = idt_trap(ex_bp);
    idt[EX_OF_VEC] = idt_trap(ex_of);
    idt[EX_BR_VEC] = idt_trap(ex_br);
    idt[EX_UD_VEC] = idt_trap(ex_ud);
    idt[EX_NM_VEC] = idt_trap(ex_nm);
    idt[EX_DF_VEC] = idt_trap(ex_df);
    idt[9] = idt_trap(ex_res);  /* unused Coprocessor Segment Overrun */
    idt[EX_TS_VEC] = idt_trap(ex_ts);
    idt[EX_NP_VEC] = idt_trap(ex_np);
    idt[EX_SS_VEC] = idt_trap(ex_ss);
    idt[EX_GP_VEC] = idt_trap(ex_gp);
    idt[EX_PF_VEC] = idt_trap(ex_pf);
    idt[15] = idt_trap(ex_res);
    idt[EX_MF_VEC] = idt_trap(ex_mf);
    idt[EX_AC_VEC] = idt_trap(ex_ac);
    idt[EX_MC_VEC] = idt_trap(ex_mc);
    idt[EX_XM_VEC] = idt_trap(ex_xm);
    idt[EX_VE_VEC] = idt_trap(ex_ve);

    /* Initialize descriptors of reserved exceptions.
     * Thankfully we compile with -std=c11, so declarations within
     * for-loops are possible! */
    for (size_t i = 21; i < 32; ++i)
        idt[i] = idt_trap(ex_res);

    /* Initialize descriptors of hardware interrupt handlers (ISRs). */
    idt[INT_8253_VEC] = idt_int(int_8253);
    idt[INT_8042_VEC] = idt_int(int_8042);
    idt[INT_CASC_VEC] = idt_int(int_casc);
    idt[INT_SERIAL2_VEC] = idt_int(int_serial2);
    idt[INT_SERIAL1_VEC] = idt_int(int_serial1);
    idt[INT_PARALL2_VEC] = idt_int(int_parall2);
    idt[INT_FLOPPY_VEC] = idt_int(int_floppy);
    idt[INT_PARALL1_VEC] = idt_int(int_parall1);
    idt[INT_RTC_VEC] = idt_int(int_rtc);
    idt[INT_ACPI_VEC] = idt_int(int_acpi);
    idt[INT_OPEN2_VEC] = idt_int(int_open2);
    idt[INT_OPEN1_VEC] = idt_int(int_open1);
    idt[INT_MOUSE_VEC] = idt_int(int_mouse);
    idt[INT_FPU_VEC] = idt_int(int_fpu);
    idt[INT_PRIM_ATA_VEC] = idt_int(int_prim_ata);
    idt[INT_SEC_ATA_VEC] = idt_int(int_sec_ata);

    for (size_t i = 0x30; i < IDT_SIZE; ++i)
        idt[i] = idt_trap(ex_res);
}

The macros idt_trap and idt_int, and are defined as follows:

#define idt_entry(off, type, priv) \
    ((descr) (uintptr_t) (off) & 0xffff) | ((descr) (KERN_CODE & 0xff) << \
    0x10) | ((descr) ((type) & 0x0f) << 0x28) | ((descr) ((priv) & \
    0x03) << 0x2d) | (descr) 0x800000000000 | \
    ((descr) ((uintptr_t) (off) & 0xffff0000) << 0x30)

#define idt_int(off) idt_entry(off, 0x0e, 0x00)
#define idt_trap(off) idt_entry(off, 0x0f, 0x00)

idt is an array of uint64_t, so these macros are implicitly cast to that type. uintptr_t is the type guaranteed to be capable of holding pointer values as integers and on 32-bit systems usually 32 bits wide. (A 64-bit IDT has 16-byte entries; this code is for 32-bit).

I get the warning that the initializer element is not constant due to the address modification in play.
It is absolutely sure that the address is known at linking time.
Is there anything I can do to make this work? Making the idt array automatic would work but this would require the whole kernel to run in the context of one function and this would be some bad hassle, I think.

I could make this work by some additional work at runtime (as Linux 0.01 also does) but it just annoys me that something technically feasible at linking time is actually infeasible.

Answer 1

Related: Solution needed for building a static IDT and GDT at assemble/compile/link time - a linker script for ld can shift and mask to break up link-time-constant addresses. No earlier step has the final addresses, and relocation entries are limited in what they can represent in a .o.

---

The main problem is that function addresses are link-time constants, not strictly compile time constants. The compiler can't just get 32b binary integers and stick that into the data segment in two separate pieces. Instead, it has to use the object file format to indicate to the linker where it should fill in the final value (+ offset) of which symbol when linking is done. The common cases are as an immediate operand to an instruction, a displacement in an effective address, or a value in the data section. (But in all those cases it's still just filling in 32-bit absolute address so all 3 use the same ELF relocation type. There's a different relocation for relative displacements for jump / call offsets.)

It would have been possible for ELF to have been designed to store a symbol reference to be substituted at link time with a complex function of an address (or at least high / low halves like on MIPS for lui $t0, %hi(symbol) / ori $t0, $t0, %lo(symbol) to build address constants from two 16-bit immediates). But in fact the only function allowed is addition/subtraction, for use in things like mov eax, [ext_symbol + 16].

It is of course possible for your OS kernel binary to have a static IDT with fully resolved addresses at build time, so all you need to do at runtime is execute a single lidt instruction. However, the standard build toolchain is an obstacle. You probably can't achieve this without post-processing your executable.

e.g. you could write it this way, to produce a table with the full padding in the final binary, so the data can be shuffled in-place:

#include <stdint.h>

#define PACKED __attribute__((packed))

// Note, this is the 32-bit format.  64-bit is larger    
typedef union idt_entry {

    // we will postprocess the linker output to have this format
    // (or convert at runtime)
    struct PACKED runtime {   // from OSdev wiki
       uint16_t offset_1; // offset bits 0..15
       uint16_t selector; // a code segment selector in GDT or LDT
       uint8_t zero;      // unused, set to 0
       uint8_t type_attr; // type and attributes, see below
       uint16_t offset_2; // offset bits 16..31
    } rt;

    // linker output will be in this format
    struct PACKED compiletime {
       void *ptr; // offset bits 0..31
       uint8_t zero;
       uint8_t type_attr;
       uint16_t selector; // to be swapped with the high16 of ptr
    } ct;
} idt_entry;

// #define idt_ct_entry(off, type, priv) { .ptr = off, .type_attr = type, .selector = priv }
#define idt_ct_trap(off) { .ct = { .ptr = off, .type_attr = 0x0f, .selector = 0x00 } }
// generate an entry in compile-time format

extern void ex_de();  // these are the raw interrupt handlers, written in ASM
extern void ex_db();  // they have to save/restore *all* registers, and end with  iret, rather than the usual C ABI.

// it might be easier to use asm macros to create this static data, 
// just so it can be in the same file and you don't need cross-file prototypes / declarations
// (but all the same limitations about link-time constants apply)
static idt_entry idt[] = {
    idt_ct_trap(ex_de),
    idt_ct_trap(ex_db),
    // ...
};

// having this static probably takes less space than instructions to write it on the fly
// but not much more.  It would be easy to make a lidt function that took a struct pointer.
static const struct PACKED  idt_ptr {
  uint16_t len;  // encoded as bytes - 1, so 0xffff means 65536
  void *ptr;
} idt_ptr = { sizeof(idt) - 1, idt };


/****** functions *********/

// inline
void load_static_idt(void) {
  asm volatile ("lidt  %0"
               : // no outputs
               : "m" (idt_ptr));
  // memory operand, instead of writing the addressing mode ourself, allows a RIP-relative addressing mode in 64bit mode
  // also allows it to work with -masm=intel or not.
}

// Do this once at at run-time
// **OR** run this to pre-process the binary, after link time, as part of your build
void idt_convert_to_runtime(void) {
#ifdef DEBUG
  static char already_done = 0;  // make sure this only runs once
  if (already_done)
    error;
  already_done = 1;
#endif
  const int count = sizeof idt / sizeof idt[0];
  for (int i=0 ; i<count ; i++) {
    uint16_t tmp1 = idt[i].rt.selector;
    uint16_t tmp2 = idt[i].rt.offset_2;
    idt[i].rt.offset_2 = tmp1;
    idt[i].rt.selector = tmp2;
    // or do this swap in fewer insns with SSE or MMX pshufw, but using vector instructions before setting up the IDT may be insane.
  }
}

This does compile. See a diff of the -m32 and -m64 asm output on the Godbolt compiler explorer. Look at the layout in the data section (note that .value is a synonym for .short, and is 16 bits.) (But note that the IDT table format is different for 64-bit mode.)

I think I have the size calculation correct (bytes - 1), as documented in http://wiki.osdev.org/Interrupt_Descriptor_Table. Minimum value 100h bytes long (encoded as 0x99). See also https://en.wikibooks.org/wiki/X86_Assembly/Global_Descriptor_Table. (lgdt size/pointer works the same way, although the table itself has a different format.)

---

The other option, instead of having the IDT static in the data section, is to have it in the bss section, with the data stored as immediate constants in a function that will initialize it (or in an array read by that function).

Either way, that function (and its data) can be in a .init section whose memory you re-use after it's done. (Linux does this to reclaim memory from code and data that's only needed once, at startup.) This would give you the optimal tradeoff of small binary size (since 32b addresses are smaller than 64b IDT entries), and no runtime memory wasted on code to set up the IDT. A small loop that runs once at startup is negligible CPU time. (The version on Godbolt fully unrolls because I only have 2 entries, and it embeds the address into each instruction as a 32-bit immediate, even with -Os. With a large enough table (just copy/paste to duplicate a line) you get a compact loop even at -O3. The threshold is lower for -Os.)

Without memory-reuse haxx, probably a tight loop to rewrite 64b entries in place is the way to go. Doing it at build time would be even better, but then you'd need a custom tool to run the tranformation on the kernel binary.

Having the data stored in immediates sounds good in theory, but the code for each entry would probably total more than 64b, because it couldn't loop. The code to split an address into two would have to be fully unrolled (or placed in a function and called). Even if you had a loop to store all the same-for-multiple-entries stuff, each pointer would need a mov r32, imm32 to get the address in a register, then mov word [idt+i + 0], ax / shr eax, 16 / mov word [idt+i + 6], ax. That's a lot of machine-code bytes.

Answer 2

One way would be to use an intermediate jump table that is located at a fixed address. You could initialize the idt with addresses of the locations in this table (which will be compile time constant). The locations in the jump table will contain jump instructions to the actual isr routines.

The dispatch to an isr will be indirect as follows:

trap -> jump to intermediate address in the idt -> jump to isr

One way to create a jump table at a fixed address is as follows.

Step 1: Put jump table in a section

// this is a jump table at a fixed address
void jump(void) __attribute__((section(".si.idt")));

void jump(void) {
    asm("jmp isr0"); // can also be asm("call ...") depending on need
    asm("jmp isr1");
    asm("jmp isr2");
}

Step 2: Instruct the linker to locate the section at a fixed address

SECTIONS
{
  .so.idt 0x600000 :
  {
    *(.si.idt)
  }
}

Put this in the linker script right after the .text section. This will make sure that the executable code in the table will go into a executable memory region.

You can instruct the linker to use your script as follows using the --script option in the Makefile.

LDFLAGS += -Wl,--script=my_script.lds

The following macro gives you the address of the location which contains the jump (or call) instruction to the corresponding isr.

// initialize the idt at compile time with const values
// you can find a cleaner way to generate offsets
#define JUMP_ADDR(off)  ((char*)0x600000 + 4 + (off * 5))

You will then initialize the idt as follows using modified macros.

// your real idt will be initialized as follows

#define idt_entry(addr, type, priv) \
    ( \
        ((descr) (uintptr_t) (addr) & 0xffff) | \
        ((descr) (KERN_CODE & 0xff) << 0x10) | \
        ((descr) ((type) & 0x0f) << 0x28) | \
        ((descr) ((priv) & 0x03) << 0x2d) | \
        ((descr) 0x1 << 0x2F) | \
        ((descr) ((uintptr_t) (addr) & 0xffff0000) << 0x30) \
    )

#define idt_int(off)    idt_entry(JUMP_ADDR(off), 0x0e, 0x00)
#define idt_trap(off)   idt_entry(JUMP_ADDR(off), 0x0f, 0x00)

descr idt[] =
{
    ...
    idt_trap(ex_de),
    ...
    idt_int(int_casc),
    ...
};

A demo working example is below, which shows dispatch to a isr with a non-fixed address from a instruction at a fixed address.

#include <stdio.h>

// dummy isrs for demo
void isr0(void) {
    printf("==== isr0\n");
}

void isr1(void) {
    printf("==== isr1\n");
}

void isr2(void) {
    printf("==== isr2\n");
}

// this is a jump table at a fixed address
void jump(void) __attribute__((section(".si.idt")));

void jump(void) {
    asm("jmp isr0"); // can be asm("call ...")
    asm("jmp isr1");
    asm("jmp isr2");
}

// initialize the idt at compile time with const values
// you can find a cleaner way to generate offsets
#define JUMP_ADDR(off)  ((char*)0x600000 + 4 + (off * 5))

// dummy idt for demo
// see below for the real idt
char* idt[] =
{
    JUMP_ADDR(0),
    JUMP_ADDR(1),
    JUMP_ADDR(2),
};

int main(int argc, char* argv[]) {
    int trap;
    char* addr = idt[trap = argc - 1];
    printf("==== idt[%d]=%p\n", trap, addr);
    asm("jmp *%0\n" : :"m"(addr));
}