aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@zytor.com>2019-01-12 00:35:20 -0800
committerH. Peter Anvin <hpa@zytor.com>2019-01-12 00:35:20 -0800
commit69fa3c2e8e09c1cda8334bec1a7d022cdf877383 (patch)
treedcb3859c85fbefc159028249a55db413d36380b1
parent52266ad42490f48b91a70efb5c2f93ea281eeb60 (diff)
downloadnasm-69fa3c2e8e09c1cda8334bec1a7d022cdf877383.tar.gz
nasm-69fa3c2e8e09c1cda8334bec1a7d022cdf877383.tar.xz
nasm-69fa3c2e8e09c1cda8334bec1a7d022cdf877383.zip
outelf: hash sections for performance
Use a hash table to look up sections by name, and an RAA to look up sections by index; thus remove O(n) searches. This becomes important since ELF uses sections for dead code elimination. Signed-off-by: H. Peter Anvin <hpa@zytor.com>
-rw-r--r--output/outelf.c75
-rw-r--r--output/outelf.h3
-rw-r--r--test/manysecs.asm6
3 files changed, 56 insertions, 28 deletions
diff --git a/output/outelf.c b/output/outelf.c
index c0d19e8b..bd5a3e6d 100644
--- a/output/outelf.c
+++ b/output/outelf.c
@@ -1,6 +1,6 @@
/* ----------------------------------------------------------------------- *
*
- * Copyright 1996-2018 The NASM Authors - All Rights Reserved
+ * Copyright 1996-2019 The NASM Authors - All Rights Reserved
* See the file AUTHORS included with the NASM distribution for
* the specific copyright holders.
*
@@ -50,6 +50,7 @@
#include "outform.h"
#include "outlib.h"
#include "rbtree.h"
+#include "hashtbl.h"
#include "ver.h"
#include "dwarf.h"
@@ -77,6 +78,9 @@ static struct RAA *bsym;
static struct SAA *strs;
static uint32_t strslen;
+static struct RAAPTR *section_by_index;
+static struct hash_table section_by_name;
+
static struct elf_symbol *fwds;
static char elf_module[FILENAME_MAX];
@@ -375,6 +379,11 @@ elf_directive(enum directive directive, char *value, int pass)
static void elf_init(void)
{
+ static const char * const reserved_sections[] = {
+ ".shstrtab", ".strtab", ".symtab", ".symtab_shndx", NULL
+ };
+ const char * const *p;
+
strlcpy(elf_module, inname, sizeof(elf_module));
sects = NULL;
nsects = sectlen = 0;
@@ -391,11 +400,23 @@ static void elf_init(void)
fwds = NULL;
+ hash_init(&section_by_name, HASH_MEDIUM);
+ section_by_index = raa_init_ptr();
+
+ /*
+ * Add reserved section names to the section hash, with NULL
+ * as the data pointer
+ */
+ for (p = reserved_sections; *p; p++) {
+ struct hash_insert hi;
+ hash_find(&section_by_name, *p, &hi);
+ hash_add(&hi, *p, NULL);
+ }
+
/*
* FIXME: tlsie is Elf32 only and
* gottpoff is Elfx32|64 only.
*/
-
elf_gotpc_sect = seg_alloc();
backend_label("..gotpc", elf_gotpc_sect + 1, 0L);
elf_gotoff_sect = seg_alloc();
@@ -431,6 +452,8 @@ static void elf_cleanup(void)
nasm_free(r);
}
}
+ hash_free(&section_by_name);
+ raa_free_ptr(section_by_index);
nasm_free(sects);
saa_free(syms);
raa_free(bsym);
@@ -449,7 +472,8 @@ static void add_sectname(const char *firsthalf, const char *secondhalf)
shstrtablen += len + 1;
}
-static int elf_make_section(char *name, int type, int flags, uint64_t align)
+static struct elf_section *
+elf_make_section(char *name, int type, int flags, uint64_t align)
{
struct elf_section *s;
@@ -468,12 +492,13 @@ static int elf_make_section(char *name, int type, int flags, uint64_t align)
s->type = type;
s->flags = flags;
s->align = align;
+ s->shndx = nsects + 1;
if (nsects >= sectlen)
sects = nasm_realloc(sects, (sectlen += SECT_DELTA) * sizeof(*sects));
sects[nsects++] = s;
- return nsects - 1;
+ return s;
}
static int32_t elf_section_names(char *name, int pass, int *bits)
@@ -481,8 +506,10 @@ static int32_t elf_section_names(char *name, int pass, int *bits)
char *p;
uint32_t flags, flags_and, flags_or;
uint64_t align, entsize;
+ void **hp;
struct elf_section *s;
- int type, i;
+ struct hash_insert hi;
+ int type;
if (!name) {
*bits = ofmt->maxbits;
@@ -497,18 +524,15 @@ static int32_t elf_section_names(char *name, int pass, int *bits)
elf_section_attrib(name, p, pass, &flags_and,
&flags_or, &align, &entsize, &type);
- if (!strcmp(name, ".shstrtab") ||
- !strcmp(name, ".symtab") ||
- !strcmp(name, ".strtab")) {
- nasm_error(ERR_NONFATAL, "attempt to redefine reserved section"
- "name `%s'", name);
- return NO_SEG;
- }
-
- for (i = 0; i < nsects; i++)
- if (!strcmp(name, sects[i]->name))
- break;
- if (i == nsects) {
+ hp = hash_find(&section_by_name, name, &hi);
+ if (hp) {
+ s = *hp;
+ if (!s) {
+ nasm_error(ERR_NONFATAL, "attempt to redefine reserved section"
+ "name `%s'", name);
+ return NO_SEG;
+ }
+ } else {
const struct elf_known_section *ks = elf_known_sections;
while (ks->name) {
@@ -521,11 +545,11 @@ static int32_t elf_section_names(char *name, int pass, int *bits)
align = align ? align : ks->align;
flags = (ks->flags & ~flags_and) | flags_or;
- i = elf_make_section(name, type, flags, align);
+ s = elf_make_section(name, type, flags, align);
+ hash_add(&hi, s->name, s);
+ section_by_index = raa_write_ptr(section_by_index, s->index >> 1, s);
}
- s = sects[i];
-
if (pass == 1) {
if ((type && s->type != type)
|| ((s->flags & flags_and) != flags_or)
@@ -628,7 +652,7 @@ static void elf_deflabel(char *name, int32_t segment, int64_t offset,
if (segment == NO_SEG)
sym->section = SHN_ABS;
else {
- int i;
+ const struct elf_section *s;
sym->section = SHN_UNDEF;
if (segment == def_seg) {
/* we have to be sure at least text section is there */
@@ -636,12 +660,9 @@ static void elf_deflabel(char *name, int32_t segment, int64_t offset,
if (segment != elf_section_names(".text", 2, &tempint))
nasm_panic(0, "strange segment conditions in ELF driver");
}
- for (i = 0; i < nsects; i++) {
- if (segment == sects[i]->index) {
- sym->section = i + 1;
- break;
- }
- }
+ s = raa_read_ptr(section_by_index, segment >> 1);
+ if (s)
+ sym->section = s->shndx;
}
if (is_global == 2) {
diff --git a/output/outelf.h b/output/outelf.h
index 59d8d929..3c4a40c0 100644
--- a/output/outelf.h
+++ b/output/outelf.h
@@ -137,7 +137,8 @@ struct elf_section {
uint64_t len;
uint64_t size;
uint64_t nrelocs;
- int32_t index;
+ int32_t index; /* NASM index */
+ int shndx; /* ELF index */
int type; /* SHT_PROGBITS or SHT_NOBITS */
uint64_t align; /* alignment: power of two */
uint64_t flags; /* section flags */
diff --git a/test/manysecs.asm b/test/manysecs.asm
new file mode 100644
index 00000000..c65c6091
--- /dev/null
+++ b/test/manysecs.asm
@@ -0,0 +1,6 @@
+%assign n 0
+%rep 10000
+ section .text %+ n progbits exec
+ nop
+%assign n n+1
+%endrep