From 13f60e80e15dd0657c90bcca372ba045630ed9de Mon Sep 17 00:00:00 2001 From: Peter Zijlstra Date: Fri, 28 Oct 2022 20:29:51 +0200 Subject: objtool: Avoid O(bloody terrible) behaviour -- an ode to libelf Due to how gelf_update_sym*() requires an Elf_Data pointer, and how libelf keeps Elf_Data in a linked list per section, elf_update_symbol() ends up having to iterate this list on each update to find the correct Elf_Data for the index'ed symbol. By allocating one Elf_Data per new symbol, the list grows per new symbol, giving an effective O(n^2) insertion time. This is obviously bloody terrible. Therefore over-allocate the Elf_Data when an extention is needed. Except it turns out libelf disregards Elf_Scn::sh_size in favour of the sum of Elf_Data::d_size. IOW it will happily write out all the unused space and fill it with: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND entries (aka zeros). Which obviously violates the STB_LOCAL placement rule, and is a general pain in the backside for not being the desired behaviour. Manually fix-up the Elf_Data size to avoid this problem before calling elf_update(). This significantly improves performance when adding a significant number of symbols. Signed-off-by: Peter Zijlstra (Intel) Tested-by: Yujie Liu Link: https://lkml.kernel.org/r/20221028194453.461658986@infradead.org --- tools/objtool/include/objtool/elf.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'tools/objtool/include') diff --git a/tools/objtool/include/objtool/elf.h b/tools/objtool/include/objtool/elf.h index d28533106b78..9e96a613c50f 100644 --- a/tools/objtool/include/objtool/elf.h +++ b/tools/objtool/include/objtool/elf.h @@ -38,7 +38,7 @@ struct section { Elf_Data *data; char *name; int idx; - bool changed, text, rodata, noinstr, init; + bool changed, text, rodata, noinstr, init, truncate; }; struct symbol { -- cgit v1.2.3