ELF: use rbtree for symbol searches

Linear searches are evil, so use an llrbtree to search for symbols by
offset.  This doesn't change the preexisting behaviour that we only
look for global symbols.

Signed-off-by: H. Peter Anvin <hpa@zytor.com>

7 files changed, 69 insertions, 96 deletions

diff --git a/Makefile.in b/Makefile.in
index 42f3d963..0471aaf4 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -293,9 +293,11 @@ output/outcoff.$(O): output/outcoff.c compiler.h config.h insnsi.h nasm.h \
 output/outdbg.$(O): output/outdbg.c compiler.h config.h insnsi.h nasm.h \
  nasmlib.h outform.h pptok.h preproc.h regs.h
 output/outelf32.$(O): output/outelf32.c compiler.h config.h insnsi.h nasm.h \
- nasmlib.h outform.h outlib.h pptok.h preproc.h raa.h regs.h saa.h stdscan.h
+ nasmlib.h outform.h outlib.h pptok.h preproc.h raa.h rbtree.h regs.h saa.h \
+ stdscan.h
 output/outelf64.$(O): output/outelf64.c compiler.h config.h insnsi.h nasm.h \
- nasmlib.h outform.h outlib.h pptok.h preproc.h raa.h regs.h saa.h stdscan.h
+ nasmlib.h outform.h outlib.h pptok.h preproc.h raa.h rbtree.h regs.h saa.h \
+ stdscan.h
 output/outieee.$(O): output/outieee.c compiler.h config.h insnsi.h nasm.h \
  nasmlib.h outform.h pptok.h preproc.h regs.h
 output/outmacho.$(O): output/outmacho.c compiler.h config.h insnsi.h nasm.h \
diff --git a/Mkfiles/msvc.mak b/Mkfiles/msvc.mak
index 21b52bcc..a2a51936 100644
--- a/Mkfiles/msvc.mak
+++ b/Mkfiles/msvc.mak
@@ -233,9 +233,9 @@ output/outcoff.$(O): output/outcoff.c compiler.h insnsi.h nasm.h nasmlib.h \
 output/outdbg.$(O): output/outdbg.c compiler.h insnsi.h nasm.h nasmlib.h \
  outform.h pptok.h preproc.h regs.h
 output/outelf32.$(O): output/outelf32.c compiler.h insnsi.h nasm.h nasmlib.h \
- outform.h outlib.h pptok.h preproc.h raa.h regs.h saa.h stdscan.h
+ outform.h outlib.h pptok.h preproc.h raa.h rbtree.h regs.h saa.h stdscan.h
 output/outelf64.$(O): output/outelf64.c compiler.h insnsi.h nasm.h nasmlib.h \
- outform.h outlib.h pptok.h preproc.h raa.h regs.h saa.h stdscan.h
+ outform.h outlib.h pptok.h preproc.h raa.h rbtree.h regs.h saa.h stdscan.h
 output/outieee.$(O): output/outieee.c compiler.h insnsi.h nasm.h nasmlib.h \
  outform.h pptok.h preproc.h regs.h
 output/outmacho.$(O): output/outmacho.c compiler.h insnsi.h nasm.h nasmlib.h \
diff --git a/Mkfiles/netware.mak b/Mkfiles/netware.mak
index d775070a..692206fd 100644
--- a/Mkfiles/netware.mak
+++ b/Mkfiles/netware.mak
@@ -172,9 +172,9 @@ outcoff.o: outcoff.c compiler.h config.h insnsi.h nasm.h nasmlib.h outform.h \
 outdbg.o: outdbg.c compiler.h config.h insnsi.h nasm.h nasmlib.h outform.h \
  pptok.h preproc.h regs.h
 outelf32.o: outelf32.c compiler.h config.h insnsi.h nasm.h nasmlib.h \
- outform.h outlib.h pptok.h preproc.h raa.h regs.h saa.h stdscan.h
+ outform.h outlib.h pptok.h preproc.h raa.h rbtree.h regs.h saa.h stdscan.h
 outelf64.o: outelf64.c compiler.h config.h insnsi.h nasm.h nasmlib.h \
- outform.h outlib.h pptok.h preproc.h raa.h regs.h saa.h stdscan.h
+ outform.h outlib.h pptok.h preproc.h raa.h rbtree.h regs.h saa.h stdscan.h
 outieee.o: outieee.c compiler.h config.h insnsi.h nasm.h nasmlib.h outform.h \
  pptok.h preproc.h regs.h
 outmacho.o: outmacho.c compiler.h config.h insnsi.h nasm.h nasmlib.h \
diff --git a/Mkfiles/openwcom.mak b/Mkfiles/openwcom.mak
index cebc0f0a..5215159b 100644
--- a/Mkfiles/openwcom.mak
+++ b/Mkfiles/openwcom.mak
@@ -262,9 +262,9 @@ output\outcoff.$(O): output\outcoff.c compiler.h insnsi.h nasm.h nasmlib.h &
 output\outdbg.$(O): output\outdbg.c compiler.h insnsi.h nasm.h nasmlib.h &
  outform.h pptok.h preproc.h regs.h
 output\outelf32.$(O): output\outelf32.c compiler.h insnsi.h nasm.h nasmlib.h &
- outform.h outlib.h pptok.h preproc.h raa.h regs.h saa.h stdscan.h
+ outform.h outlib.h pptok.h preproc.h raa.h rbtree.h regs.h saa.h stdscan.h
 output\outelf64.$(O): output\outelf64.c compiler.h insnsi.h nasm.h nasmlib.h &
- outform.h outlib.h pptok.h preproc.h raa.h regs.h saa.h stdscan.h
+ outform.h outlib.h pptok.h preproc.h raa.h rbtree.h regs.h saa.h stdscan.h
 output\outieee.$(O): output\outieee.c compiler.h insnsi.h nasm.h nasmlib.h &
  outform.h pptok.h preproc.h regs.h
 output\outmacho.$(O): output\outmacho.c compiler.h insnsi.h nasm.h nasmlib.h &
diff --git a/Mkfiles/owlinux.mak b/Mkfiles/owlinux.mak
index 94ca28de..be56653c 100644
--- a/Mkfiles/owlinux.mak
+++ b/Mkfiles/owlinux.mak
@@ -272,9 +272,9 @@ output/outcoff.$(O): output/outcoff.c compiler.h insnsi.h nasm.h nasmlib.h \
 output/outdbg.$(O): output/outdbg.c compiler.h insnsi.h nasm.h nasmlib.h \
  outform.h pptok.h preproc.h regs.h
 output/outelf32.$(O): output/outelf32.c compiler.h insnsi.h nasm.h nasmlib.h \
- outform.h outlib.h pptok.h preproc.h raa.h regs.h saa.h stdscan.h
+ outform.h outlib.h pptok.h preproc.h raa.h rbtree.h regs.h saa.h stdscan.h
 output/outelf64.$(O): output/outelf64.c compiler.h insnsi.h nasm.h nasmlib.h \
- outform.h outlib.h pptok.h preproc.h raa.h regs.h saa.h stdscan.h
+ outform.h outlib.h pptok.h preproc.h raa.h rbtree.h regs.h saa.h stdscan.h
 output/outieee.$(O): output/outieee.c compiler.h insnsi.h nasm.h nasmlib.h \
  outform.h pptok.h preproc.h regs.h
 output/outmacho.$(O): output/outmacho.c compiler.h insnsi.h nasm.h nasmlib.h \
diff --git a/output/outelf32.c b/output/outelf32.c
index f5a7d20c..0f9ba10b 100644
--- a/output/outelf32.c
+++ b/output/outelf32.c
@@ -22,6 +22,7 @@
 #include "stdscan.h"
 #include "outform.h"
 #include "outlib.h"
+#include "rbtree.h"
 
 #ifdef OF_ELF32
 
@@ -57,16 +58,15 @@ struct Reloc {
 };
 
 struct Symbol {
-    int32_t strpos;                /* string table position of name */
-    int32_t section;               /* section ID of the symbol */
-    int type;                   /* symbol type */
-    int other;                     /* symbol visibility */
-    int32_t value;                 /* address, or COMMON variable align */
-    int32_t size;                  /* size of symbol */
-    int32_t globnum;               /* symbol table offset if global */
-    struct Symbol *next;        /* list of globals in each section */
-    struct Symbol *nextfwd;     /* list of unresolved-size symbols */
-    char *name;                 /* used temporarily if in above list */
+    struct rbtree symv;	       /* symbol value and symbol rbtree */
+    int32_t strpos;	       /* string table position of name */
+    int32_t section;	       /* section ID of the symbol */
+    int type;                  /* symbol type */
+    int other;		       /* symbol visibility */
+    int32_t size;	       /* size of symbol */
+    int32_t globnum;	       /* symbol table offset if global */
+    struct Symbol *nextfwd;    /* list of unresolved-size symbols */
+    char *name;		       /* used temporarily if in above list */
 };
 
 #define SHT_PROGBITS 1
@@ -83,12 +83,12 @@ struct Section {
     int32_t index;
     int type;                   /* SHT_PROGBITS or SHT_NOBITS */
     int align;                  /* alignment: power of two */
-    uint32_t flags;        /* section flags */
+    uint32_t flags;		/* section flags */
     char *name;
     struct SAA *rel;
     int32_t rellen;
     struct Reloc *head, **tail;
-    struct Symbol *gsyms;       /* global symbols in section */
+    struct rbtree *gsyms;       /* global symbols in section */
 };
 
 #define SECT_DELTA 32
@@ -629,7 +629,7 @@ static void elf_deflabel(char *name, int32_t segment, int64_t offset,
 
     if (is_global == 2) {
         sym->size = offset;
-        sym->value = 0;
+        sym->symv.key = 0;
         sym->section = SHN_COMMON;
         /*
          * We have a common variable. Check the special text to see
@@ -638,17 +638,18 @@ static void elf_deflabel(char *name, int32_t segment, int64_t offset,
          */
         if (special) {
             bool err;
-            sym->value = readnum(special, &err);
+            sym->symv.key = readnum(special, &err);
             if (err)
                 error(ERR_NONFATAL, "alignment constraint `%s' is not a"
                       " valid number", special);
-            else if ((sym->value | (sym->value - 1)) != 2 * sym->value - 1)
+            else if ((sym->symv.key | (sym->symv.key - 1))
+		     != 2 * sym->symv.key - 1)
                 error(ERR_NONFATAL, "alignment constraint `%s' is not a"
                       " power of two", special);
         }
         special_used = true;
     } else
-        sym->value = (sym->section == SHN_UNDEF ? 0 : offset);
+        sym->symv.key = (sym->section == SHN_UNDEF ? 0 : offset);
 
     if (sym->type == SYM_GLOBAL) {
         /*
@@ -665,16 +666,14 @@ static void elf_deflabel(char *name, int32_t segment, int64_t offset,
             bsym = raa_write(bsym, segment, nglobs);
         } else if (sym->section != SHN_ABS) {
             /*
-             * This is a global symbol; so we must add it to the linked
-             * list of global symbols in its section. We'll push it on
-             * the beginning of the list, because it doesn't matter
-             * much which end we put it on and it's easier like this.
+             * This is a global symbol; so we must add it to the rbtree
+             * of global symbols in its section.
              *
              * In addition, we check the special text for symbol
              * type and size information.
              */
-            sym->next = sects[sym->section - 1]->gsyms;
-            sects[sym->section - 1]->gsyms = sym;
+	    sects[sym->section-1]->gsyms =
+		rb_insert(sects[sym->section-1]->gsyms, &sym->symv);
 
             if (special) {
                 int n = strcspn(special, " \t");
@@ -805,12 +804,13 @@ static void elf_add_reloc(struct Section *sect, int32_t segment, int type)
  * isn't even necessarily sorted.
  */
 static int32_t elf_add_gsym_reloc(struct Section *sect,
-                               int32_t segment, int32_t offset,
+                               int32_t segment, uint32_t offset,
                                int type, bool exact)
 {
     struct Reloc *r;
     struct Section *s;
-    struct Symbol *sym, *sm;
+    struct Symbol *sym;
+    struct rbtree *srb;
     int i;
 
     /*
@@ -835,27 +835,13 @@ static int32_t elf_add_gsym_reloc(struct Section *sect,
         return offset;
     }
 
-    if (exact) {
-        /*
-         * Find a symbol pointing _exactly_ at this one.
-         */
-        for (sym = s->gsyms; sym; sym = sym->next)
-            if (sym->value == offset)
-                break;
-    } else {
-        /*
-         * Find the nearest symbol below this one.
-         */
-        sym = NULL;
-        for (sm = s->gsyms; sm; sm = sm->next)
-            if (sm->value <= offset && (!sym || sm->value > sym->value))
-                sym = sm;
-    }
-    if (!sym && exact) {
-        error(ERR_NONFATAL, "unable to find a suitable global symbol"
-              " for this reference");
-        return 0;
+    srb = rb_search(s->gsyms, offset);
+    if (!srb || (exact && srb->key != offset)) {
+	error(ERR_NONFATAL, "unable to find a suitable global symbol"
+	      " for this reference");
+	return 0;
     }
+    sym = container_of(srb, struct Symbol, symv);
 
     r = *sect->tail = nasm_malloc(sizeof(struct Reloc));
     sect->tail = &r->next;
@@ -867,7 +853,7 @@ static int32_t elf_add_gsym_reloc(struct Section *sect,
 
     sect->nrelocs++;
 
-    return offset - sym->value;
+    return offset - sym->symv.key;
 }
 
 static void elf_out(int32_t segto, const void *data,
@@ -1311,7 +1297,7 @@ static struct SAA *elf_build_symtab(int32_t *len, int32_t *local)
             continue;
         p = entry;
         WRITELONG(p, sym->strpos);
-        WRITELONG(p, sym->value);
+        WRITELONG(p, sym->symv.key);
         WRITELONG(p, sym->size);
         WRITECHAR(p, sym->type);        /* type and binding */
         WRITECHAR(p, sym->other);       /* visibility */
@@ -1367,7 +1353,7 @@ static struct SAA *elf_build_symtab(int32_t *len, int32_t *local)
             continue;
         p = entry;
         WRITELONG(p, sym->strpos);
-        WRITELONG(p, sym->value);
+        WRITELONG(p, sym->symv.key);
         WRITELONG(p, sym->size);
         WRITECHAR(p, sym->type);        /* type and binding */
         WRITECHAR(p, sym->other);       /* visibility */
diff --git a/output/outelf64.c b/output/outelf64.c
index 4254585c..259d7d53 100644
--- a/output/outelf64.c
+++ b/output/outelf64.c
@@ -21,6 +21,7 @@
 #include "stdscan.h"
 #include "outform.h"
 #include "outlib.h"
+#include "rbtree.h"
 
 /* Definitions in lieu of elf.h */
 #define SHT_NULL 0			/* Inactive section header */
@@ -141,19 +142,17 @@ struct Reloc {
 };
 
 struct Symbol {
+    struct rbtree symv;	        /* symbol value and rbtree of globals */
     int32_t strpos;             /* string table position of name */
     int32_t section;            /* section ID of the symbol */
     int type;			/* symbol type */
     int other;                  /* symbol visibility */
-    int64_t value;              /* address, or COMMON variable align */
     int32_t size;               /* size of symbol */
     int32_t globnum;            /* symbol table offset if global */
-    struct Symbol *next;       	/* list of globals in each section */
     struct Symbol *nextfwd;     /* list of unresolved-size symbols */
     char *name;			/* used temporarily if in above list */
 };
 
-
 struct Section {
     struct SAA *data;
     uint64_t len, size;
@@ -166,7 +165,7 @@ struct Section {
     struct SAA *rel;
     uint64_t rellen;
     struct Reloc *head, **tail;
-    struct Symbol *gsyms;       /* global symbols in section */
+    struct rbtree *gsyms;       /* global symbols in section */
 };
 
 #define SECT_DELTA 32
@@ -666,7 +665,7 @@ static void elf_deflabel(char *name, int32_t segment, int64_t offset,
 
     if (is_global == 2) {
         sym->size = offset;
-        sym->value = 0;
+        sym->symv.key = 0;
         sym->section = SHN_COMMON;
         /*
          * We have a common variable. Check the special text to see
@@ -675,17 +674,18 @@ static void elf_deflabel(char *name, int32_t segment, int64_t offset,
          */
         if (special) {
             bool err;
-            sym->value = readnum(special, &err);
+            sym->symv.key = readnum(special, &err);
             if (err)
                 error(ERR_NONFATAL, "alignment constraint `%s' is not a"
                       " valid number", special);
-            else if ((sym->value | (sym->value - 1)) != 2 * sym->value - 1)
+            else if ((sym->symv.key | (sym->symv.key - 1))
+		     != 2 * sym->symv.key - 1)
                 error(ERR_NONFATAL, "alignment constraint `%s' is not a"
                       " power of two", special);
         }
         special_used = true;
     } else
-        sym->value = (sym->section == SHN_UNDEF ? 0 : offset);
+        sym->symv.key = (sym->section == SHN_UNDEF ? 0 : offset);
 
     if (sym->type == SYM_GLOBAL) {
         /*
@@ -702,16 +702,14 @@ static void elf_deflabel(char *name, int32_t segment, int64_t offset,
             bsym = raa_write(bsym, segment, nglobs);
         } else if (sym->section != SHN_ABS) {
             /*
-             * This is a global symbol; so we must add it to the linked
-             * list of global symbols in its section. We'll push it on
-             * the beginning of the list, because it doesn't matter
-             * much which end we put it on and it's easier like this.
+             * This is a global symbol; so we must add it to the rbtree
+             * of global symbols in its section.
              *
              * In addition, we check the special text for symbol
              * type and size information.
              */
-            sym->next = sects[sym->section - 1]->gsyms;
-            sects[sym->section - 1]->gsyms = sym;
+	    sects[sym->section-1]->gsyms =
+		rb_insert(sects[sym->section-1]->gsyms, &sym->symv);
 
             if (special) {
                 int n = strcspn(special, " \t");
@@ -843,12 +841,13 @@ static void elf_add_reloc(struct Section *sect, int32_t segment,
  * isn't even necessarily sorted.
  */
 static void elf_add_gsym_reloc(struct Section *sect,
-                               int32_t segment, int64_t offset, int64_t pcrel,
+                               int32_t segment, uint64_t offset, int64_t pcrel,
 			       int type, bool exact)
 {
     struct Reloc *r;
     struct Section *s;
-    struct Symbol *sym, *sm;
+    struct Symbol *sym;
+    struct rbtree *srb;
     int i;
 
     /*
@@ -873,34 +872,20 @@ static void elf_add_gsym_reloc(struct Section *sect,
 	return;
     }
 
-    if (exact) {
-        /*
-         * Find a symbol pointing _exactly_ at this one.
-         */
-        for (sym = s->gsyms; sym; sym = sym->next)
-            if (sym->value == offset)
-                break;
-	if (!sym) {
-	    error(ERR_NONFATAL, "unable to find a suitable global symbol"
-		  " for this reference");
-	    return;
-	}
-    } else {
-        /*
-         * Find the nearest symbol below this one.
-         */
-        sym = NULL;
-        for (sm = s->gsyms; sm; sm = sm->next)
-            if (sm->value <= offset && (!sym || sm->value > sym->value))
-                sym = sm;
+    srb = rb_search(s->gsyms, offset);
+    if (!srb || (exact && srb->key != offset)) {
+	error(ERR_NONFATAL, "unable to find a suitable global symbol"
+	      " for this reference");
+	return;
     }
+    sym = container_of(srb, struct Symbol, symv);
 
     r = *sect->tail = nasm_malloc(sizeof(struct Reloc));
     sect->tail = &r->next;
     r->next = NULL;
 
     r->address = sect->len;
-    r->offset = offset - pcrel - sym->value;
+    r->offset = offset - pcrel - sym->symv.key;
     r->symbol = GLOBAL_TEMP_BASE + sym->globnum;
     r->type = type;
 
@@ -1432,7 +1417,7 @@ static struct SAA *elf_build_symtab(int32_t *len, int32_t *local)
         WRITECHAR(p, sym->type);        /* type and binding */
         WRITECHAR(p, sym->other);	/* visibility */
         WRITESHORT(p, sym->section);    /* index into section header table */
-        WRITEDLONG(p, (int64_t)sym->value); /* value of symbol */
+        WRITEDLONG(p, (int64_t)sym->symv.key); /* value of symbol */
         WRITEDLONG(p, (int64_t)sym->size);  /* size of symbol */
         saa_wbytes(s, entry, 24L);
         *len += 24;
@@ -1487,7 +1472,7 @@ static struct SAA *elf_build_symtab(int32_t *len, int32_t *local)
         WRITECHAR(p, sym->type);        /* type and binding */
         WRITECHAR(p, sym->other);       /* visibility */
         WRITESHORT(p, sym->section);
-        WRITEDLONG(p, (int64_t)sym->value);
+        WRITEDLONG(p, (int64_t)sym->symv.key);
         WRITEDLONG(p, (int64_t)sym->size);
         saa_wbytes(s, entry, 24L);
         *len += 24;