On Mon, Sep 21, 2026 at 09:16:21PM -0700, Josh Poimboeuf wrote: > On Thu, Sep 17, 2026 at 05:06:25PM +0100, Lorenzo Stoakes (ARM) wrote: > > This relies upon the entries within a section being sorted, which is the > > case for all sections supplied to objtool by the link step during the > > kernel build. > > This is wrong (or at least actively misleading). Objtool doesn't *only* > run on linked objects. In some configs it runs on individual .o files. > And GCC doesn't sort relocs: > > Relocation section '.rela.text' at offset 0xc0d0 contains 724 entries: > Offset Info Type Symbol's Value > Symbol's Name + Addend > ... > 0000000000005c50 0000009000000004 R_X86_64_PLT32 0000000000000000 > _raw_spin_lock - 4 > 0000000000005c65 0000009100000004 R_X86_64_PLT32 0000000000000000 > _raw_spin_unlock - 4 > 0000000000005c6d 0000019f00000004 R_X86_64_PLT32 0000000000000000 > put_files_struct - 4 > 000000000000004d 0000008f00000004 R_X86_64_PLT32 0000000000000000 > __x86_return_thunk - 4 > 0000000000000075 0000008f00000004 R_X86_64_PLT32 0000000000000000 > __x86_return_thunk - 4 > 00000000000000cd 0000008f00000004 R_X86_64_PLT32 0000000000000000 > __x86_return_thunk - 4 > > (JMP target relocations are emitted in a second pass, for whatever > reason) > > So the hash may actually be needed as a fallback after all. Or some > other scheme.
Ack, that's fair enough. Definitely need something that isn't the linear scan as a truly worst case can be horrible. I think the hash can be avoided though, Do the read_relocs() without ordering, track whether things are in order, on decode if sorted then just read from relocs[], if not can allocate an order[] array and qsort() and build the index over that. So O(n lg n) at that point, but avoids bothering to sort for anything not looked up, works similarly for added sections. So still avoids all of the hash stuff, but efficient when things are actually out of order. > > Either way it's overkill to have more than a single fallback. No second > fallback for "just in case". Attempting to search an unhashed section > (DWARF) can just be a fatal error instead of the "just in case" > WARN+linear fallback thing. Honestly this is what I instinctively preferred, but objtool is not my realm so I worried there'd be some odd outlier thing that it'd somehow break! > > > @@ -1168,19 +1286,26 @@ static int read_relocs(struct elf *elf) > > return -1; > > } > > > > - elf_hash_add(reloc, &reloc->hash, reloc_hash(reloc)); > > set_sym_next_reloc(reloc, sym->relocs); > > sym->relocs = reloc; > > > > nr_reloc++; > > } > > max_reloc = max(max_reloc, nr_reloc); > > + > > + /* DWARF relocs are never looked up, so are not worth indexing. > > */ > > + if (is_dwarf_section(rsec->base)) > > + continue; > > This DWARF reloc skipping is a standalone improvement, can you split > this out to another patch? Ack will do! > > -- > Josh -- Cheers, Lorenzo
