rucc_object/

section.rs

//! What an object writer is given, which is a section of bytes and what the linker has to be
//! told about them.
//!
//! Design: `spec/11-asm-objects-debug.md` sections 11.1 and 11.3.
//!
//! These types are here rather than beside the assembler that fills them in because they are what
//! an object file is made of, and because a writer cannot depend on the thing that produces its
//! input without the graph going the wrong way round. The assembler at layer rank 11 reaches down
//! to these at rank 9, which is the direction `spec/18-package-layout.md` asks for.

/// What a function is aligned to when nothing asked for more.
///
/// Sixteen because that is what every x86-64 toolchain puts a function at, and because it is what
/// keeps the loop inside one from straddling one more cache line than it has to. Here rather than
/// beside the assembler because the assembler pads to it and the writer records it, and two
/// copies of one number is how the padding and the record come apart.
pub const FUNC_ALIGN: u32 = 16;

/// Whether each function and each variable gets a section to itself.
///
/// Design: `spec/11-asm-objects-debug.md` section 11.3, and `spec/04-driver-and-cli.md` section 4.7
/// for the flags that ask for it.
///
/// A linker can drop a section nothing reaches and cannot drop half of one, so a file whose
/// functions share a section keeps every function that file defines in the output as soon as any
/// one of them is called. Splitting them is what makes `--gc-sections` do anything, which is how an
/// embedded image or a kernel gets small, and it is the whole of what these two flags are for. The
/// cost is a section header per name, which is why it is asked for rather than always done.
///
/// Not one flag, because gcc has two and a build that wants one of them and not the other is a
/// build that measured something. Splitting the code is nearly free at link time; splitting the
/// data can defeat the linker's ordering of what is next to what.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct Sections {
    /// `-ffunction-sections`. Each function in `.text.<name>` rather than all of them in `.text`.
    pub functions: bool,
    /// `-fdata-sections`. Each variable in a section named after it rather than in the one its
    /// contents would otherwise have chosen.
    pub data: bool,
}

impl Sections {
    /// Whether either of them was asked for.
    #[must_use]
    pub const fn any(self) -> bool {
        self.functions || self.data
    }
}

/// What a file says it was built to have checked, which is what `-fcf-protection=` asks for.
///
/// Design: `spec/11-asm-objects-debug.md` section 11.3, and `spec/04-driver-and-cli.md` section 4.7
/// for the flag.
///
/// A machine's control flow checks are turned on for a whole process or not at all, never for one
/// function, so a program made of one object built with them and one built without has to be run
/// one way or the other. What everybody settled on is that each object records what it was built
/// for, the linker keeps only what every input agreed on, and the loader turns on what is left. So
/// an object that records nothing turns the check off for every object it is linked with, which is
/// why this is written even when the flag changed no instruction in the file.
///
/// One number rather than a pair of flags, because that is what the record holds: a word of bits
/// whose meaning is the machine's, and a linker that has never heard of a bit still knows to drop
/// it when one input does not have it.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct Property {
    /// The bits of the x86 feature word, which are [`Self::IBT`] and [`Self::SHSTK`].
    pub features: u32,
}

impl Property {
    /// Which property the feature word is, which is the key the record is written under.
    pub const X86_FEATURES: u32 = 0xc000_0002;
    /// Indirect branch tracking: every indirect call and jump in the file arrives at a landing
    /// pad, so the machine may fault on one that does not.
    pub const IBT: u32 = 1;
    /// The shadow stack: every return in the file goes where a second copy of the return address
    /// says it should, so the machine may fault when the two disagree.
    pub const SHSTK: u32 = 2;

    /// Whether anything is recorded at all, which is whether the record is written.
    #[must_use]
    pub const fn any(self) -> bool {
        self.features != 0
    }
}

/// What the command line decided about the file being written, as against what the code in it
/// decided.
///
/// Answers with nothing to do with each other, together because they arrive together: none of
/// them can be worked out from a function, and the listing and the byte writer have to be handed
/// the same ones or the two outputs of one command line would not be the same file.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct Output {
    /// Whether each function and each variable gets a section to itself.
    pub sections: Sections,
    /// What the file says it was built to have checked.
    pub property: Property,
    /// The extensions the unit is built for, which is what `-march=` said. Only the listing reads
    /// it, since an assembler reading the file has to be told about an extension whose
    /// instructions are in it, and bytes need no telling.
    pub isa: rucc_target::Isa,
    /// What the file says made it, which ELF keeps in `.comment` and gcc writes as `.ident`.
    /// Nothing under `-fno-ident`, and nothing on the formats with no such section.
    pub ident: Option<&'static str>,
}

/// A text section, and what the linker has to be told about it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Text {
    /// The instructions, in the order they were laid out.
    pub bytes: Vec<u8>,
    /// Where each function starts and how long it is, in the order they were written.
    pub funcs: Vec<Extent>,
    /// Every place in the bytes that names something the linker has to find.
    pub relocs: Vec<Reloc>,
    /// Every place inside a function that has a name of its own, in the order they were written.
    pub labels: Vec<Marker>,
    /// What the whole section has to be aligned to, which is the largest alignment any function
    /// in it asked for.
    ///
    /// A function is at a fixed offset inside the section, so a function at a multiple of two
    /// hundred and fifty six is one only if the section itself is at one. The padding between the
    /// functions is the assembler's half of the same job and this is the linker's.
    pub align: u32,
    /// What an unwinder is told about the functions, which is empty for a format that has no such
    /// section or a build that asked for none.
    pub unwind: Unwind,
    /// The jump tables that are read rather than run, and so go in a read only section of data
    /// rather than in these bytes. Empty on a format that keeps its tables after the function.
    pub tables: Vec<Table>,
    /// Where each call to the profiler's hook that `-mrecord-mcount` lists is, in the order they
    /// were written, as offsets into [`Text::bytes`]. Empty unless the flag was given.
    ///
    /// The writer puts one eight byte address per call in a section called `__mcount_loc`, which
    /// is what gcc writes and what a kernel before objtool took this over reads at boot to find
    /// every call it can turn into a nop.
    pub mcount: Vec<usize>,
}

/// The section `-mrecord-mcount` lists the calls in. See [`Text::mcount`].
pub const MCOUNT_LOC: &str = "__mcount_loc";

impl Default for Text {
    fn default() -> Self {
        Self {
            bytes: Vec::new(),
            funcs: Vec::new(),
            relocs: Vec::new(),
            labels: Vec::new(),
            align: FUNC_ALIGN,
            unwind: Unwind::default(),
            tables: Vec::new(),
            mcount: Vec::new(),
        }
    }
}

/// The unwind table, as the bytes of the section or two it goes in and what the linker has to be
/// told about them.
///
/// Bytes rather than rows, because what a record is is the platform's answer rather than the object
/// writer's, and the layer that knows what a frame did is the one that can say it in the fewest of
/// them. What is left for the writer is where the sections go and what their relocations are.
///
/// Two of them, because the two platforms lay the same facts out differently. ELF writes one section
/// of records, each a little program an unwinder runs to rebuild the frame at an address, and each
/// carrying its own codes, so [`Self::info`] is empty there. Windows writes a table of fixed rows
/// sorted by address, one per function, each pointing at the description of that function's prologue
/// in a second section, which is what [`Self::info`] holds.
///
/// Every record says where its function is, and where a function is is a number no compilation
/// knows: a function is at a fixed offset inside its own section and the section is placed by the
/// linker. So there are relocations, and which kind they are is the format's answer too.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Unwind {
    /// The records: one shared header and one per function on ELF, and one row per function on
    /// Windows.
    pub bytes: Vec<u8>,
    /// Every place in them that names something the linker has to place, which is the functions
    /// they are about and, where there is a second section, the description each row points at.
    pub relocs: Vec<Reloc>,
    /// What those records point at, on the format that keeps the two apart, and nothing at all on
    /// the one whose records carry their own.
    pub info: Vec<u8>,
    /// The names inside [`Self::info`], one per function that has a description there, which are
    /// what the relocations above ask for.
    ///
    /// Names rather than offsets because a relocation names a symbol, and the record and the thing
    /// it points at are in two different sections, so there is no distance either of them can be
    /// written with instead.
    pub labels: Vec<Marker>,
    /// The table of where each call an unwind lands from goes, which is `.gcc_except_table` and
    /// is empty in a file with no landing pad in it. One header per function that has any, each
    /// found by the record of its function through a relocation against this section, which is
    /// what the name [`EXCEPT_TABLE`] in a relocation of [`Self::relocs`] stands for.
    pub except: Vec<u8>,
}

/// The name of the section the call site tables go in, which is also what a relocation against it
/// names. See [`Unwind::except`].
pub const EXCEPT_TABLE: &str = ".gcc_except_table";

/// The debug information, as the bytes of the sections it goes in.
///
/// Bytes rather than anything shaped like DWARF, for the reason [`Unwind`] is bytes: what a record
/// is is the format's answer and the layer that knows what the program was doing is the one that
/// can say it, and what is left for the writer is where the sections go and what their relocations
/// are. The difference between the two is only that there are more than two sections here and that
/// their names are not the writer's to choose, so each one carries its own.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Info {
    /// One entry per section that has anything in it, in the order they are to be written.
    ///
    /// The order matters because a relocation in one of them can name another, and a name is
    /// resolved against the sections this file already has. Writing them in the order the producer
    /// hands them over keeps that a property of the list rather than of the writer.
    pub chunks: Vec<Chunk>,
    /// How the sections are stored in an ELF file, which is what `-gz` asks. Every other format
    /// gets them as they are.
    pub compress: Compress,
}

/// How an ELF file stores its debug sections.
///
/// A debug section is much larger than the code it describes and is read by a debugger rather than
/// by the program, so it can be stored compressed and unpacked by whatever reads it. A section
/// that would come out no smaller is left as it is, the way gas leaves one.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub enum Compress {
    /// As they are.
    #[default]
    None,
    /// `-gz=zlib`: the section keeps its name, gains `SHF_COMPRESSED`, and starts with an
    /// `Elf_Chdr` saying it is zlib and how large it was.
    Zlib,
    /// `-gz=zlib-gnu`: the older layout, where `.debug_info` becomes `.zdebug_info` and starts with
    /// `ZLIB` and its size as eight big endian bytes.
    ZlibGnu,
    /// `-gz=zstd`: as `Zlib`, with the `Elf_Chdr` saying zstd and a zstd frame after it.
    Zstd,
}

/// One debug section, with the name it goes in the file under.
///
/// A relocation here names either a function this file defines or another section in the same
/// list, and the two are told apart by looking the name up among the sections first. That is safe
/// rather than lucky: every section name in DWARF begins with `.debug_`, which is not the spelling
/// of any name a C program can define.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Chunk {
    /// What the section is called, which is the name DWARF gives it.
    pub name: String,
    /// Its contents.
    pub bytes: Vec<u8>,
    /// Every place in them that names something this file does not place itself.
    pub relocs: Vec<Reloc>,
}

/// Where the room a patcher was promised at the top of a function ended up.
///
/// What `-fpatchable-function-entry=` asks for, once it is bytes rather than instructions. Two
/// numbers because the writer has two questions: where the address it records points, and how much
/// of the function is in front of the symbol.
///
/// They are not the same number. The room can be split by the landing pad a function opens with,
/// since the pad has to be the first instruction after the label and the room does not, so the part
/// in front of the label and the part after it are not always next to each other. What is recorded
/// is the front of the whole thing, which is the part in front of the label when there is one.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Patch {
    /// Where the room begins, as an offset into the same bytes [`Extent::start`] is one into.
    pub at: usize,
    /// How many bytes of the function are in front of [`Extent::start`], which is where its symbol
    /// is and where an unwinder is told the function begins.
    pub before: usize,
}

/// Where a place inside a function that has a name of its own ended up.
///
/// What asks for one is GNU's address of a label in the initializer of an object with static
/// storage duration. A label is somewhere a jump goes and a jump is a distance the assembler works
/// out, so no ordinary label is in the symbol table at all. An image is the other case: it is in
/// another section, so what it holds is a relocation, and a relocation names a symbol.
///
/// The name is never one the program wrote, so nothing outside this file looks it up and it is
/// always local: it is here for a relocation in this same file to resolve against, and a linker
/// that offered it to another file would be offering the middle of a function.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Marker {
    /// The name, which is whatever the compiler minted for it.
    pub name: String,
    /// Where it is, as an offset into the same bytes [`Extent::start`] is one into.
    pub at: usize,
}

/// One jump table of one function, kept out of the instructions.
///
/// A table is data the function reads, and gcc and clang put it in `.rodata` rather than in the
/// code. Keeping it there keeps data out of the lines the instruction fetcher reads and keeps the
/// executable sections to what is executed, which is also what a size counted by section is
/// measuring. The cost is that the two ends of every cell are now in different sections, so each
/// cell is a relocation the linker fills in rather than a number the assembler writes, which is
/// what gas does with the same `.long .L3-.L4` when the `.L4` is in `.rodata`.
///
/// Each cell is still the distance from the front of the table to a block, so the code that reads
/// one is the same code wherever the table is.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Table {
    /// The name the instruction that reads it gives it, which is local to this file.
    pub name: String,
    /// Which of [`Text::funcs`] it belongs to.
    pub func: usize,
    /// Where each cell's block is, counted from [`Extent::start`] of that function.
    pub cells: Vec<usize>,
    /// Whether each cell is the block's address in eight bytes rather than its distance from the
    /// table in four, which is the table the kernel code model reads.
    pub absolute: bool,
}

/// Where one function ended up.
///
/// How long a function is is a fact ELF records and Mach-O has no way to, so it is handed over
/// rather than worked out again: the writer that wants it has it and the one that does not
/// ignores it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Extent {
    /// The function's name, as the C program spelled it. The underscore an Apple symbol carries
    /// is the object writer's business, not this one's.
    pub name: String,
    /// Where its first instruction is.
    pub start: usize,
    /// How many bytes of instructions it is, not counting the padding in front of the next one.
    pub len: usize,
    /// What this one function asked to be aligned to, which is not always what the section it is
    /// in was aligned to.
    ///
    /// The two are the same number only when this function is the one that asked for the most.
    /// Under [`Sections::functions`] each function is a section of its own and this is what that
    /// section is aligned to, so the number has to survive the trip rather than be recovered from
    /// the offset, which says nothing once the function is at zero in a section of its own.
    pub align: u32,
    /// How the linker sees the name, which is what the C `static` reaches the object file as.
    pub binding: Binding,
    /// How far outside a shared library holding this the name reaches.
    pub visibility: Visibility,
    /// Where the room a patcher was promised is, or `None` in a function promised none, which is
    /// every function on a command line that did not ask. See [`Patch`].
    pub patch: Option<Patch>,
    /// Each call an unwind lands somewhere from, in the order they are in the function, which is
    /// empty in every function with no cleanup handler to run on the way out. See [`Site`].
    pub landings: Vec<Site>,
}

/// One call an unwind out of lands in a pad, as distances from [`Extent::start`].
///
/// What a row of the call site table in `.gcc_except_table` says, which is the bytes of the call
/// and where the pad is. An unwinder looking up a return address finds the call it is the end of,
/// so the range is the call's own bytes and nothing around it.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Site {
    /// Where the call begins.
    pub start: usize,
    /// How many bytes it is.
    pub len: usize,
    /// Where the pad begins.
    pub pad: usize,
}

/// The variables a file defines, and what the linker has to be told about them.
///
/// One entry per variable rather than one section of everything, because where a variable goes is
/// worked out from what it is and two of them that land in one section still have their own
/// alignment, their own size and their own symbol. Putting them together is the writer's job and
/// is the one part of it the three formats disagree about.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Data {
    /// Every variable this file defines, in the order the module held them.
    pub objects: Vec<Object>,
    /// Every name this file declares weak and does not define, in the order the module held them.
    ///
    /// Each becomes an undefined symbol the linker is allowed to leave undefined, whose references
    /// then read a zero address. A name here is not an object and carries no bytes, which is why
    /// it is a list of names beside the objects rather than one of them.
    pub weak: Vec<String>,
    /// Every distance between two labels an image holds, which the writer fills in once it knows
    /// where the labels are. See [`Apart`].
    pub apart: Vec<Apart>,
    /// Every name this file offers to other DLLs, functions first and then variables, each in the
    /// order the module held them. Only COFF has anywhere to say it and every other format is
    /// handed an empty list. See [`Export`].
    pub exports: Vec<Export>,
}

/// One name the DLL this file is linked into offers to others, which is `dllexport`, or one it
/// is told to keep to itself, which is a hidden definition.
///
/// What a COFF object says either with is an option for the linker, ` -export:name`, in a section
/// called `.drectve` that holds nothing but options and that the linker reads and then drops. A
/// variable is ` -export:name,data`, which keeps the import library from writing a stub under the
/// plain name for it, since a jump is no use to somebody reading a variable. The list is in the
/// order clang writes it and the options are spelled the way it spells them, which is also what
/// gcc's are, apart from the quotes gcc puts round each name.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Export {
    /// The name as the linker sees it.
    pub name: String,
    /// What the linker is told about it.
    pub kind: Offer,
}

/// What an [`Export`] tells the linker about its name.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Offer {
    /// A function other DLLs may call.
    Function,
    /// A variable other DLLs may read.
    Variable,
    /// A name that is left out when the linker exports every name a DLL defines, which is what it
    /// does for a DLL with no `dllexport` and no `.def` file. `-exclude-symbols:name`, which clang
    /// writes for a hidden definition on a mingw-w64 target and which both lld and GNU ld read.
    /// gcc ignores hidden visibility there. This is how the runtime routines of our own that a
    /// DLL links in stay out of its export table, the way libgcc's do by being named libgcc.
    Hidden,
    /// Not a name at all but a whole option, which [`Export::name`] holds as the linker reads it.
    /// What `#pragma comment(lib)` and `#pragma comment(linker)` ask for, such as
    /// `/DEFAULTLIB:ws2_32.lib`, which goes in the same section for the same linker to read.
    Verbatim,
}

impl Export {
    /// The option the linker is handed for it, with the space in front that holds it apart from
    /// the one before.
    #[must_use]
    pub fn option(&self) -> String {
        match self.kind {
            Offer::Function => format!(" -export:{}", self.name),
            Offer::Variable => format!(" -export:{},data", self.name),
            Offer::Hidden => format!(" -exclude-symbols:{}", self.name),
            Offer::Verbatim => format!(" {}", self.name),
        }
    }
}

/// How far one label is from another, written into a variable's image.
///
/// What `static int b[] = { &&l1 - &&l0 };` asks for. Neither label has an address until the
/// link, and yet both are in the one function's code and the code moves as one piece, so the
/// distance is known as soon as the code is laid out. That makes it a number the writer puts in
/// the bytes itself rather than a relocation it asks the linker for, which is what gas does with
/// `.long .L1-.L0` too, and it is why a label in another function is refused: the two could land
/// in different sections and then no number is right.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Apart {
    /// Which of [`Data::objects`] the distance is written into.
    pub object: usize,
    /// How far into that object's image.
    pub at: usize,
    /// The label measured to, as the image named it.
    pub to: String,
    /// The label measured from.
    pub from: String,
    /// What to add to the distance.
    pub addend: i64,
    /// How many bytes the distance is written in.
    pub bytes: u8,
}

/// A second name for something the same file defines.
///
/// Not a section and not a byte of anything, which is the whole point of it: an alias is a symbol
/// table entry pointing at an address something else already occupies, so a file with one in it is
/// no larger than the same file without. `.set b, a` is what an assembler is told and a second
/// entry at the first one's section, value and size is what a writer produces, and the two say the
/// same thing.
///
/// The target is a name rather than an index into anything above, because the two output paths
/// find it in different places: a listing hands the name to an assembler that resolves it, and a
/// writer looks it up among the symbols it has already added.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Alias {
    /// The name being defined, as the C program spelled it.
    pub name: String,
    /// The name it stands for, which has to be something this same file defines.
    pub target: String,
    /// How the linker sees the new name, which is not always how it sees the old one: the target
    /// of `extern int b __attribute__((alias("a")))` may be a `static`.
    pub binding: Binding,
    /// How far outside a shared library holding this the new name reaches, which is its own
    /// answer for the same reason the binding is: the attribute is written on the alias.
    pub visibility: Visibility,
    /// Whether the new name is an indirect function, `STT_GNU_IFUNC`, rather than a second name
    /// for the target. The target is then a resolver, which the dynamic loader calls once and
    /// whose answer is the address every call to the new name reaches. ELF is the only format with
    /// the type, and a writer for another one refuses it rather than write an ordinary name.
    pub ifunc: bool,
}

/// One global variable, laid out.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Object {
    /// Its name, as the C program spelled it. The underscore an Apple symbol carries is the
    /// object writer's business, not this one's.
    pub name: String,
    /// Its image, and nothing at all when it is zero filled and the file carries none of it.
    pub bytes: Vec<u8>,
    /// How many bytes it occupies, which is the length of the image except when there is none.
    pub size: u64,
    /// What it has to be aligned to, always a power of two.
    pub align: u64,
    /// Which section it goes in.
    pub place: Place,
    /// How the linker sees the name.
    pub binding: Binding,
    /// How far outside a shared library holding this the name reaches.
    pub visibility: Visibility,
    /// Every place in its image that holds the address of a symbol, counted from the start of
    /// the image rather than from the start of the section it lands in.
    pub relocs: Vec<Reloc>,
}

/// Which section a variable goes in.
///
/// Worked out from what the variable is rather than named by it, except in the one case where the
/// program named it. A reader who wants to know why a variable is in `.rodata` should be able to
/// find the answer in the variable.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Place {
    /// Written to, and its image is not all zeros. `.data`.
    Written,
    /// Never written to, so it can go in a page the loader maps read only and every process
    /// running the program can share. `.rodata`.
    ReadOnly,
    /// Never written to by the program, but written once by the dynamic linker, because its image
    /// holds the address of something and an address is not known until the image is loaded.
    /// `.data.rel.ro`.
    ///
    /// The section has to be writable for that one write and read only afterwards, which is what
    /// the `PT_GNU_RELRO` segment is: the loader maps it, the relocations are applied, and then it
    /// is turned read only before the program starts. Putting the variable in `.rodata` instead
    /// means asking the linker to leave a relocation in a section that is never writable, and what
    /// it does about that is give the whole image `DT_TEXTREL`, which gives up the protection the
    /// section was for. Some hardened toolchains refuse the link outright.
    RelocReadOnly {
        /// Whether every address in the image is of something this file defines and does not
        /// export, which means the link can resolve them all and none can be interposed.
        ///
        /// Those go in `.data.rel.ro.local`, which the linker puts in the first pages of the
        /// segment, so the pages holding them are the ones the loader is done with soonest. It is
        /// a hint about layout rather than a difference in what the section is.
        local: bool,
    },
    /// All zeros, so the file says how big it is and carries none of it. `.bss`.
    Zero,
    /// One copy per thread rather than one copy per program. `.tdata` and `.tbss`.
    ///
    /// What the loader does with these two sections is what makes them different from every other
    /// section here. Their contents are the template of a thread's own block of storage rather than
    /// the storage itself: the image is laid out once, and every thread that starts gets a fresh
    /// copy of it, so the address of a variable in one of them is a different address in every
    /// thread and there is no single address for the link to write down. That is why a reference to
    /// one is not the ordinary distance from the instruction pointer, and why the symbol is marked
    /// as being of this kind so a linker refuses one that is.
    ///
    /// The pair is the same split as `.data` and `.bss` for the same reason, so an image that is
    /// all zeros costs its size in the file and not its bytes.
    Thread {
        /// Whether the image is all zeros, which puts it in `.tbss` rather than `.tdata`.
        zero: bool,
    },
    /// A tentative definition, which is not in a section at all: the linker is asked for that
    /// much zeroed space and merges every definition of the name into one. `.comm`.
    Merged,
    /// The section the program named, from `__attribute__((section(...)))`, and what the
    /// variable put there holds, which is what the section's flags have to say.
    Named(String, Holds),
    /// A pointer to a variable this file only declares, in a read only section of its own that
    /// the linker keeps one copy of whichever objects wrote it. COFF only, where it is called
    /// `.rdata$` and the pointer's name, and every object that reads the variable writes the same
    /// one with the same name, which is why a copy has to be allowed to lose to another.
    ///
    /// What the pointer is for is `rucc_codegen::elsewhere::Slot::Referred`. The runtime may write
    /// it once the DLL the variable turns out to be in is loaded, which is why the section is not
    /// merely read only: the runtime unprotects the page for that one write.
    Pointer,
    /// A string literal, in the section of them the linker keeps one copy of each string in,
    /// whichever objects it came from. `.rodata.str1.` and the alignment, which is where gcc puts
    /// one, flagged `SHF_MERGE` and `SHF_STRINGS` with entries a byte wide.
    ///
    /// Only for a literal of one byte characters whose first zero is its last byte. The linker
    /// reads the section as a run of strings each ended by a zero, so one with a zero inside it
    /// would be cut in two, and a wide one is entries of a different width, which goes in a
    /// section of its own name that nothing here writes yet.
    Strings {
        /// What it is aligned to, which is in the name because two literals aligned differently
        /// cannot be in one run the linker merges.
        align: u64,
    },
}

/// What a variable in a section the program named holds, which is the one thing about the section
/// the name does not say.
///
/// The answers are the ones gcc gives, which a kernel's linker script and `readelf` both see: a
/// section is writable unless the variable is constant and holds no address, and it carries no
/// bytes only when its name is one of the names that always mean zeros and the variable is zeros.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Holds {
    /// Bytes the program or the loader may write. `"aw"` on ELF.
    Written,
    /// Bytes nothing writes, which a loader maps read only. `"a"` on ELF.
    ReadOnly,
    /// Zeros, in a section named for holding nothing else, so the file carries none of them.
    /// `"aw",@nobits` on ELF.
    Zero,
}

impl Holds {
    /// Whether a section of this name is one gcc makes carry no bytes, which is `.bss` and the
    /// names under it, the small data one and the old COMDAT spellings of both. A kernel puts
    /// its page aligned zeros in `.bss..page_aligned` and relies on this.
    #[must_use]
    pub fn nobits(name: &str) -> bool {
        name == ".bss"
            || name.starts_with(".bss.")
            || name.starts_with(".gnu.linkonce.b.")
            || name == ".sbss"
            || name.starts_with(".sbss.")
            || name.starts_with(".gnu.linkonce.sb.")
    }
}

impl Place {
    /// What the section this variable goes in is called under [`Sections::data`], and nothing at
    /// all for a variable that has no section of its own to be given.
    ///
    /// The name is the section it would otherwise have shared with a dot and the variable's name
    /// after it, which is what gcc writes and is not merely a convention: `--gc-sections`, the
    /// linker scripts a kernel and an embedded image are linked with, and the default placement
    /// rules all match on the part in front of the dot, so a section called anything else would be
    /// placed by whatever the catch all rule is.
    ///
    /// Two kinds of variable are left alone. A merged one is a request to the linker for that much
    /// zeroed space rather than an image, so there is no section to split, and one the program put
    /// a name on already has the answer the source gave, which this must not overrule.
    /// A string literal is left alone too, as gcc leaves it: the linker merges the strings of the
    /// section they share, and a section per literal would give it nothing to merge them with.
    ///
    /// Here rather than beside either output path, so that the listing `-S` writes and the object
    /// `-c` writes cannot come to disagree about where a variable went.
    #[must_use]
    pub fn split(&self, name: &str) -> Option<String> {
        Some(format!("{}.{name}", self.base()?))
    }

    /// The section this variable goes in when nothing is being split up, and nothing at all for
    /// the two kinds that are not in one.
    #[must_use]
    pub fn base(&self) -> Option<&'static str> {
        Some(match self {
            Place::Written => ".data",
            Place::ReadOnly => ".rodata",
            Place::RelocReadOnly { local: false } => ".data.rel.ro",
            Place::RelocReadOnly { local: true } => ".data.rel.ro.local",
            Place::Zero => ".bss",
            Place::Thread { zero: false } => ".tdata",
            Place::Thread { zero: true } => ".tbss",
            Place::Merged | Place::Named(..) | Place::Pointer | Place::Strings { .. } => {
                return None;
            }
        })
    }

    /// The section a string literal of that alignment goes in.
    #[must_use]
    pub fn strings(align: u64) -> String {
        format!(".rodata.str1.{align}")
    }
}

/// A section holding function addresses for a C runtime to call rather than data for the program
/// to read.
///
/// ELF has a type for each of the three, and a section of that type is what the startup code walks:
/// the linker gathers every input section of the kind into one run and the CRT calls what it finds
/// between the two ends. A section of the ordinary type with the same name would be gathered the
/// same way and called by nothing, which is why the type is worth writing down rather than leaving
/// to the default.
///
/// Only ELF says it this way. COFF sorts by what follows the `$` in a section name and Mach-O has
/// a section attribute for it, so on those two the name carries the whole of the answer and there
/// is nothing for this to be.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Array {
    /// Run on the way to `main`, in the order the linker sorted the sections into.
    Init,
    /// Run after `main` returns, in the reverse of that order.
    Fini,
    /// Run ahead of `.init_array` and ahead of the shared libraries a program is linked against,
    /// which is a thing only the C library itself has a use for.
    Preinit,
}

impl Array {
    /// Which of them a section of this name is, and [`None`] for a name that is not one of them.
    ///
    /// The name itself or the name with a dot and a priority after it. A numbered `constructor` is
    /// written as the second of those and is the same kind of section as the first: the number is
    /// there so that the linker sorts it, not to make it a different thing.
    #[must_use]
    pub fn of(name: &str) -> Option<Array> {
        let kinds = [
            (".init_array", Array::Init),
            (".fini_array", Array::Fini),
            (".preinit_array", Array::Preinit),
        ];
        kinds.into_iter().find_map(|(base, array)| {
            let rest = name.strip_prefix(base)?;
            (rest.is_empty() || rest.starts_with('.')).then_some(array)
        })
    }

    /// How the type is spelled in a `.section` directive.
    #[must_use]
    pub const fn asm(self) -> &'static str {
        match self {
            Array::Init => "@init_array",
            Array::Fini => "@fini_array",
            Array::Preinit => "@preinit_array",
        }
    }
}

/// How the linker sees a name.
///
/// Three of the five linkages the IR has, because that is how many an object file can say. Which
/// of the two weak ones a symbol had is a fact the optimizer needs and the linker does not.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Binding {
    /// Visible to every other object, and the definition here is the definition.
    Global,
    /// Invisible outside this object, which is what `static` at file scope means.
    Local,
    /// Visible, and allowed to lose to a definition in another object.
    Weak,
}

/// How far outside a shared library a name reaches.
///
/// A different question from [`Binding`] and asked of a different linker. The binding is what the
/// static linker does with a name while it is building the output, and this is what the dynamic
/// linker may do with it once the output is a shared library and is being loaded. A hidden name is
/// still global to the static link, so two files in the same library can call each other by it; it
/// is simply not in the dynamic symbol table afterwards, so nothing outside can name it.
///
/// Written down here as its own thing rather than folded into the binding because it is the
/// mistake tamnd/rucc#733 was: a writer that has one word for both ends up saying something about
/// visibility while it thinks it is saying something about linkage, and what it said was hidden.
///
/// It means nothing for a [`Binding::Local`] name. `static` is already invisible to the whole
/// world outside the file, and ELF records `STV_DEFAULT` for one, which is what gcc writes.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub enum Visibility {
    /// In the dynamic symbol table, and a reference from inside the library may be satisfied by a
    /// definition somewhere else, which is what makes `LD_PRELOAD` work. What a name gets when
    /// nothing said otherwise.
    #[default]
    Default,
    /// Not in the dynamic symbol table at all, so nothing outside the library can name it and
    /// every reference to it from inside binds here. `__attribute__((visibility("hidden")))`.
    Hidden,
    /// In the dynamic symbol table, so something outside can name it, but a reference from inside
    /// the library binds to the definition inside it and cannot be interposed.
    Protected,
}

/// One reference to something this file does not contain.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Reloc {
    /// Where the bytes the linker writes over begin.
    pub at: usize,
    /// What is wanted, as the C program spelled it.
    pub symbol: String,
    /// What the linker is being asked for.
    pub kind: Reference,
    /// What to add to the distance, which is the constant the instruction already meant plus the
    /// bytes between the hole and the end of the instruction, negated. An instruction counts from
    /// where it ends and a relocation counts from where it starts, and this is the difference.
    pub addend: i64,
    /// How many bytes of the instruction come after the four the linker writes over, which is zero
    /// for everything except an instruction carrying an immediate behind its displacement.
    ///
    /// Already inside [`Self::addend`] and written down again because the two formats disagree about
    /// which of the two numbers they want. ELF takes the one number and counts from where the hole
    /// starts, so the difference between that and where the instruction ends is the writer's to fold
    /// in and nothing after it ever has to be told apart again. COFF counts from where the
    /// instruction ends and says how far that is in the relocation type itself, which is what
    /// `IMAGE_REL_AMD64_REL32_1` through `REL32_5` are, so it needs the two apart. A writer cannot
    /// recover one from the other, since a displacement of minus four and no trailing bytes and a
    /// displacement of zero and four of them are the same sum.
    ///
    /// Zero for a relocation in an image, where there is no instruction and the question does not
    /// arise.
    pub after: u8,
}

/// Which of the i386 thread-local relocations a [`Reference::Tls`] is, named after what the four
/// bytes end up holding.
///
/// The suffix gcc writes for each is beside it. The linker may rewrite the instruction around the
/// first three into a cheaper model once it knows where the variable ends up, which is why each
/// kind is kept apart from the others rather than folded into an address or an offset.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Tls {
    /// The pair of slots of the global offset table `___tls_get_addr` takes, as a distance from the
    /// table. `@TLSGD`, `R_386_TLS_GD`.
    General,
    /// The same pair for the module as a whole rather than one variable. `@TLSLDM`,
    /// `R_386_TLS_LDM`.
    Module,
    /// How far into its module's block a variable is, which is what goes with the address
    /// [`Tls::Module`] found. `@DTPOFF`, `R_386_TLS_LDO_32`.
    InModule,
    /// A slot of the global offset table holding where the variable is from the thread pointer, as
    /// a distance from the table. `@GOTNTPOFF`, `R_386_TLS_GOTIE`.
    Slot,
    /// The same slot by its address, for code that is not position independent. `@INDNTPOFF`,
    /// `R_386_TLS_IE`.
    SlotAddress,
    /// A slot holding the distance the other way round, from the variable up to the thread
    /// pointer, as a distance from the table. `@GOTTPOFF`, `R_386_TLS_IE_32`.
    SlotNegated,
    /// Where the variable is from the thread pointer, which is below it and so negative.
    /// `@NTPOFF`, `R_386_TLS_LE`.
    Offset,
    /// The same distance the other way round, which is positive. `@TPOFF`, `R_386_TLS_LE_32`.
    Negated,
}

/// What kind of thing a relocation is asking the linker for.
///
/// The first four are the distance from the end of an instruction to something, which is what every
/// reference the code makes is, because this compiler generates position independent code and
/// nothing else. They are told apart by what the linker is allowed to do about each one. The last
/// two are not distances from an instruction at all and are what a table of data asks for: the
/// address itself, which is what an initializer holding the address of something holds, and how far
/// something is from the front of the image, which is what a table the runtime reads holds.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Reference {
    /// A call, which the linker may satisfy with a stub that reaches further than the four bytes
    /// would. `R_X86_64_PLT32` on ELF, and the same relocation a branch gets on the other two.
    Call,
    /// A datum, reached from the instruction pointer. `R_X86_64_PC32` on ELF.
    Data,
    /// A slot of the global offset table, reached from the instruction pointer, holding the
    /// address of something another object may be the one that defines.
    ///
    /// The distance to the slot rather than to the thing, which is the whole difference: the
    /// distance to the thing is a number only a link that puts the thing in this program can
    /// work out, and a shared library is a link that does not. `R_X86_64_REX_GOTPCRELX` on ELF,
    /// which says the instruction is a `mov` with a REX prefix and lets the linker turn it back
    /// into the `lea` it would have been if the symbol had been here all along.
    Got,
    /// A slot of the global offset table read by an instruction the linker may rewrite that has
    /// no REX prefix, `call *f@GOTPCREL(%rip)` or a 32 bit `mov`. `R_X86_64_GOTPCRELX` on ELF.
    GotBare,
    /// A slot of the global offset table read by an instruction the linker has to leave as it is,
    /// because it is not one of the few it knows how to rewrite: a store into the slot, or a load
    /// into a vector register. `R_X86_64_GOTPCREL` on ELF.
    GotKept,
    /// A slot of the global offset table, reached from the instruction pointer, holding how far
    /// into a thread's own block of storage a thread-local variable sits.
    ///
    /// An offset and not an address, which is what makes it a different relocation from the one
    /// above rather than the same one against a different symbol: a thread-local variable has one
    /// copy per thread and therefore no address for a link to write down, and what every copy has
    /// in common is where it sits inside the block. Adding the block's own address, which the
    /// machine keeps in a segment register, is what turns one into the other, and that addition is
    /// in the code rather than in the relocation. `R_X86_64_GOTTPOFF` on ELF, which the linker
    /// turns into a constant in the instruction when it is making an executable and therefore
    /// knows how the blocks are laid out.
    Thread,
    /// The address itself, written into an image. `int *p = &y;` and nothing else in C.
    Address {
        /// How many bytes of it are written, which is the pointer width except on a target with
        /// a narrower relocation for it. `R_X86_64_64` and `R_X86_64_32` on ELF.
        bytes: u8,
    },
    /// The address itself in four bytes of an x86-64 instruction that sign extends them to eight,
    /// which is an immediate on sixty four bits and a displacement. `R_X86_64_32S` on ELF, which
    /// is what code that is not position independent reaches its data with: `table(,%rax,4)` and
    /// `movq $.LC0, %rdi`. The linker checks the address fits in the lower two gigabytes, where
    /// `R_X86_64_32` would let one between two and four through to come out negative.
    Signed,
    /// How far the thing is from where the four bytes holding the answer are, written into an
    /// image rather than reached by an instruction. `.long target - .` in an `asm` at file scope,
    /// which is how a table of places in a program says where each of them is in four bytes rather
    /// than eight and says it without anything having to be written into the table at startup.
    ///
    /// The same relocation a load makes, with nothing after the hole, because what a load asks is
    /// the same question about the same four bytes. It is a kind of its own here all the same, and
    /// not [`Reference::Data`] with `after` left at zero, because the two formats count the answer
    /// from different ends: ELF counts from the front of the hole, which is what this wants, and
    /// COFF counts from the byte after it, which is what an instruction wants. Saying which is
    /// meant is what lets each writer answer for itself rather than one of them be quietly four
    /// out.
    Away,
    /// The same distance written into eight bytes, which is `.quad target - .`. The kernel's jump
    /// label table says where each key is that way on x86-64, and the key is in another section
    /// from the table, so it is a relocation. `R_X86_64_PC64` on ELF.
    AwayWide,
    /// How far the thing is from the front of the loaded image, written into four bytes.
    ///
    /// What every field of a Windows unwind table is. The table is read at run time by code that
    /// already has the image's own address, so four bytes of distance from it reach anything in an
    /// image a linker will build, which eight bytes of address would have cost twice as much to say
    /// and a distance from the table itself could not have said at all: a row is looked up by
    /// address in a sorted table, and a row whose meaning depended on where the row was would not
    /// sort. `IMAGE_REL_AMD64_ADDR32NB`.
    ///
    /// ELF has no relocation of this kind because nothing it writes asks the question. Its unwind
    /// records are found by walking rather than by binary search, and what they hold is the ordinary
    /// distance from the record to the function.
    Image,
    /// How far the thing is from the front of the section it is in, written into the four bytes
    /// of displacement of an address that is counted from a register.
    ///
    /// What a Windows thread finds its copy of a thread-local variable with. Every thread has a
    /// copy of the image's `.tls` section, the register holds where this thread's copy is, and the
    /// variable is as far into the copy as it is into the section. `IMAGE_REL_AMD64_SECREL`, and
    /// nothing on ELF or Mach-O, which reach thread-local storage through a table slot instead.
    Section,
    /// How far the thing is from the front of the global offset table, in four bytes.
    ///
    /// What position independent code on i386 reaches its own data with. That machine has no
    /// addressing from the instruction pointer, so a function finds the table once, keeps its
    /// address in a register, and reaches everything this file defines as that register plus a
    /// constant: `leal .LC0@GOTOFF(%ebx), %eax`. `R_386_GOTOFF` on ELF.
    GotOffset,
    /// How far the front of the global offset table is from the four bytes themselves, which is how
    /// i386 code finds the table in the first place.
    ///
    /// `addl $_GLOBAL_OFFSET_TABLE_, %ebx` straight after a call that left its own return address
    /// in `%ebx`. The addend makes up the difference between where the four bytes are and where the
    /// instruction starts, which is the address the call left behind. `R_386_GOTPC` on ELF.
    GotFront,
    /// Where a slot of the global offset table is, as a distance from the front of the table, read
    /// by an instruction the linker may rewrite into one that does not go through the slot at all.
    ///
    /// The i386 counterpart of [`Reference::Got`], counted from the register holding the table
    /// rather than from the instruction pointer: `movl foo@GOT(%ebx), %eax` and
    /// `call *foo@GOT(%ebx)`. `R_386_GOT32X` on ELF.
    Slot,
    /// The same slot read or written by an instruction the linker has to leave as it is, because it
    /// is not one of the few it knows how to rewrite. `R_386_GOT32` on ELF.
    SlotKept,
    /// One of the ways i386 code reaches a thread-local variable, which the model says which.
    ///
    /// Apart from [`Reference::Thread`] because this machine has a relocation for each step of each
    /// model rather than the one x86-64 needs from a compiler that only writes one of them, and a
    /// file of assembly may use any of them. See [`Tls`].
    Tls(Tls),
    /// Some bits of an AArch64 instruction, which the fixup says which and how to fill in.
    ///
    /// Its own kind rather than one of the above, because on this machine a reference is not four
    /// bytes of distance: it is a field of a word, and a name takes two instructions to reach,
    /// `adrp` for its page and an `add` or a load for the low twelve bits of it. Each of those is
    /// its own relocation, and the fixup is already the name of one.
    Field(rucc_target::aarch64::Fixup),
}