| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Wed, 02 Nov 2022 09:20:05 -0000
From: "tip-bot2 for Peter Zijlstra" <tip-bot2@...utronix.de>
To: linux-tip-commits@...r.kernel.org
Cc: "Peter Zijlstra (Intel)" <peterz@...radead.org>,
Yujie Liu <yujie.liu@...el.com>, x86@...nel.org,
linux-kernel@...r.kernel.org
Subject: [tip: x86/core] objtool: Avoid O(bloody terrible) behaviour -- an ode
to libelf
The following commit has been merged into the x86/core branch of tip:
Commit-ID: 13f60e80e15dd0657c90bcca372ba045630ed9de
Gitweb: https://git.kernel.org/tip/13f60e80e15dd0657c90bcca372ba045630ed9de
Author: Peter Zijlstra <peterz@...radead.org>
AuthorDate: Fri, 28 Oct 2022 20:29:51 +02:00
Committer: Peter Zijlstra <peterz@...radead.org>
CommitterDate: Tue, 01 Nov 2022 13:44:08 +01:00
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) <peterz@...radead.org>
Tested-by: Yujie Liu <yujie.liu@...el.com>
Link: https://lkml.kernel.org/r/20221028194453.461658986@infradead.org
---
tools/objtool/elf.c | 89 ++++++++++++++++++++++++++--
tools/objtool/include/objtool/elf.h | 2 +-
2 files changed, 84 insertions(+), 7 deletions(-)
diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index 3ad89d9..36dc787 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -634,6 +634,12 @@ static int elf_update_symbol(struct elf *elf, struct section *symtab,
/* end-of-list */
if (!symtab_data) {
+ /*
+ * Over-allocate to avoid O(n^2) symbol creation
+ * behaviour. The down side is that libelf doesn't
+ * like this; see elf_truncate_section() for the fixup.
+ */
+ int num = max(1U, sym->idx/3);
void *buf;
if (idx) {
@@ -647,28 +653,34 @@ static int elf_update_symbol(struct elf *elf, struct section *symtab,
if (t)
shndx_data = elf_newdata(t);
- buf = calloc(1, entsize);
+ buf = calloc(num, entsize);
if (!buf) {
WARN("malloc");
return -1;
}
symtab_data->d_buf = buf;
- symtab_data->d_size = entsize;
+ symtab_data->d_size = num * entsize;
symtab_data->d_align = 1;
symtab_data->d_type = ELF_T_SYM;
- symtab->sh.sh_size += entsize;
symtab->changed = true;
+ symtab->truncate = true;
if (t) {
- shndx_data->d_buf = &sym->sec->idx;
- shndx_data->d_size = sizeof(Elf32_Word);
+ buf = calloc(num, sizeof(Elf32_Word));
+ if (!buf) {
+ WARN("malloc");
+ return -1;
+ }
+
+ shndx_data->d_buf = buf;
+ shndx_data->d_size = num * sizeof(Elf32_Word);
shndx_data->d_align = sizeof(Elf32_Word);
shndx_data->d_type = ELF_T_WORD;
- symtab_shndx->sh.sh_size += sizeof(Elf32_Word);
symtab_shndx->changed = true;
+ symtab_shndx->truncate = true;
}
break;
@@ -770,6 +782,14 @@ non_local:
return NULL;
}
+ symtab->sh.sh_size += symtab->sh.sh_entsize;
+ symtab->changed = true;
+
+ if (symtab_shndx) {
+ symtab_shndx->sh.sh_size += sizeof(Elf32_Word);
+ symtab_shndx->changed = true;
+ }
+
return sym;
}
@@ -1286,6 +1306,60 @@ int elf_write_reloc(struct elf *elf, struct reloc *reloc)
return 0;
}
+/*
+ * When Elf_Scn::sh_size is smaller than the combined Elf_Data::d_size
+ * do you:
+ *
+ * A) adhere to the section header and truncate the data, or
+ * B) ignore the section header and write out all the data you've got?
+ *
+ * Yes, libelf sucks and we need to manually truncate if we over-allocate data.
+ */
+static int elf_truncate_section(struct elf *elf, struct section *sec)
+{
+ u64 size = sec->sh.sh_size;
+ bool truncated = false;
+ Elf_Data *data = NULL;
+ Elf_Scn *s;
+
+ s = elf_getscn(elf->elf, sec->idx);
+ if (!s) {
+ WARN_ELF("elf_getscn");
+ return -1;
+ }
+
+ for (;;) {
+ /* get next data descriptor for the relevant section */
+ data = elf_getdata(s, data);
+
+ if (!data) {
+ if (size) {
+ WARN("end of section data but non-zero size left\n");
+ return -1;
+ }
+ return 0;
+ }
+
+ if (truncated) {
+ /* when we remove symbols */
+ WARN("truncated; but more data\n");
+ return -1;
+ }
+
+ if (!data->d_size) {
+ WARN("zero size data");
+ return -1;
+ }
+
+ if (data->d_size > size) {
+ truncated = true;
+ data->d_size = size;
+ }
+
+ size -= data->d_size;
+ }
+}
+
int elf_write(struct elf *elf)
{
struct section *sec;
@@ -1296,6 +1370,9 @@ int elf_write(struct elf *elf)
/* Update changed relocation sections and section headers: */
list_for_each_entry(sec, &elf->sections, list) {
+ if (sec->truncate)
+ elf_truncate_section(elf, sec);
+
if (sec->changed) {
s = elf_getscn(elf->elf, sec->idx);
if (!s) {
diff --git a/tools/objtool/include/objtool/elf.h b/tools/objtool/include/objtool/elf.h
index d285331..9e96a61 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 {
Powered by blists - more mailing lists