Faster ndxes_of_sym_name

ndxes_of_sym_name used to have an O(s^2) complexity where s was the number
of symbols in the ELF file. It has now been reduced to an O(s*ln(s)) by
pre-computing the sets of symbols corresponding to each normalized symbol
name.

git-svn-id: https://yquem.inria.fr/compcert/svn/compcert/trunk@1875 fca1b0fc-160b-0410-b1d3-a4f43f01ea2e

5 files changed, 51 insertions, 26 deletions

diff --git a/checklink/Check.ml b/checklink/Check.ml
index 3559980..dc010a3 100644
--- a/checklink/Check.ml
+++ b/checklink/Check.ml
@@ -2749,7 +2749,9 @@ let read_sdump file =
 (** Processes a .sdump file.
 *)
 let process_sdump efw sdump: e_framework =
+  if !debug then print_endline ("Beginning reading " ^ sdump);
   let (prog, names, atoms) = read_sdump sdump in
+  if !debug then print_endline "Constructing mapping from idents to symbol indices";
   let ident_to_sym_ndx =
     Hashtbl.fold
       (fun ident name m ->
@@ -2760,6 +2762,7 @@ let process_sdump efw sdump: e_framework =
       names
       PosMap.empty
   in
+  if !debug then print_endline "Constructing worklist";
   let worklist_fundefs =
     List.filter
       (fun f ->
@@ -2778,6 +2781,7 @@ let process_sdump efw sdump: e_framework =
       )
       worklist_fundefs
   in
+  if !debug then print_endline "Beginning processing of the worklist";
   efw
   >>> (fun efw ->
     {
@@ -2790,7 +2794,15 @@ let process_sdump efw sdump: e_framework =
     }
   )
   >>> worklist_process wl
+  >>> (fun sfw ->
+    if !debug then print_endline "Checking stubs";
+    sfw
+  )
   >>> check_stubs
+  >>> (fun sfw ->
+    if !debug then print_endline "Checking data";
+    sfw
+  )
   >>> check_data prog.prog_vars
   >>> (fun sfw -> sfw.ef)
 
@@ -3023,6 +3035,7 @@ let check_elf_nodump elf sdumps =
       ELF_symbol_strtab
     >>> check_sym_tab_zero
   in
+  if !debug then print_endline "Done checking header, beginning processing of .sdumps";
   (* Thread the framework through the processing of all .sdump files *)
   List.fold_left process_sdump efw sdumps
   (* then finally, check the padding in between identified byte chunks *)
@@ -3032,7 +3045,9 @@ let check_elf_nodump elf sdumps =
     If requested, dump the calculated bytes mapping, so that it can be
     reused by the fuzzer. *)
 let check_elf_dump elffilename sdumps =
+  if !debug then print_endline "Beginning ELF parsing";
   let elf = read_elf elffilename in
+  if !debug then print_endline "Beginning ELF checking";
   let efw = check_elf_nodump elf sdumps in
   (* print the elfmap if requested *)
   if !print_elfmap then begin
@@ -3137,4 +3152,4 @@ let check_elf_dump elffilename sdumps =
               )
               (rev efw.log)
       )
-  end;
+  end
diff --git a/checklink/ELF_parsers.ml b/checklink/ELF_parsers.ml
index ba04c68..de72d39 100644
--- a/checklink/ELF_parsers.ml
+++ b/checklink/ELF_parsers.ml
@@ -304,12 +304,7 @@ let read_elf_bs (bs: bitstring): elf =
   in
   check_overlaps e_shdra e_hdr;
   let symtab_sndx = section_ndx_by_name_noelf e_shdra ".symtab" in
-  {
-    e_bitstring = bs      ;
-    e_hdr       = e_hdr   ;
-    e_shdra     = e_shdra ;
-    e_phdra     = Array.init e_hdr.e_phnum (read_elf32_phdr e_hdr bs) ;
-    e_symtab    = (
+  let e_symtab = (
       let symtab_shdr = e_shdra.(symtab_sndx) in
       let symtab_strtab_sndx = symtab_shdr.sh_link in
       let symtab_nb_ent = (Safe32.to_int symtab_shdr.sh_size / 16) in
@@ -317,8 +312,23 @@ let read_elf_bs (bs: bitstring): elf =
         (read_elf32_sym e_hdr
            (section_bitstring_noelf bs e_shdra symtab_sndx)
            (section_bitstring_noelf bs e_shdra (Safe32.to_int symtab_strtab_sndx)))
-    );
+  ) in
+  {
+    e_bitstring = bs;
+    e_hdr       = e_hdr;
+    e_shdra     = e_shdra;
+    e_phdra     = Array.init e_hdr.e_phnum (read_elf32_phdr e_hdr bs);
+    e_symtab    = e_symtab;
     e_symtab_sndx = symtab_sndx;
+    e_syms_by_name = (
+      let m = ref StringMap.empty in
+      for i = 0 to Array.length e_symtab - 1 do
+        let name = strip_versioning e_symtab.(i).st_name in
+        let list = try StringMap.find name !m with Not_found -> [] in
+        m := StringMap.add name (i :: list) !m
+      done;
+      !m
+    );
   }
 
 (** Reads a whole ELF file from a file name *)
diff --git a/checklink/ELF_types.ml b/checklink/ELF_types.ml
index a58b1eb..a6568ed 100644
--- a/checklink/ELF_types.ml
+++ b/checklink/ELF_types.ml
@@ -159,10 +159,11 @@ type elf32_phdr = {
 
 (** ELF *)
 type elf = {
-  e_bitstring:   bitstring;
-  e_hdr:         elf32_ehdr;
-  e_shdra:       elf32_shdr array;
-  e_phdra:       elf32_phdr array;
-  e_symtab:      elf32_sym array;
-  e_symtab_sndx: int; (* to avoid having to find it again when needed *)
+  e_bitstring:    bitstring;
+  e_hdr:          elf32_ehdr;
+  e_shdra:        elf32_shdr array;
+  e_phdra:        elf32_phdr array;
+  e_symtab:       elf32_sym array;
+  e_symtab_sndx:  int; (* to avoid having to find it again when needed *)
+  e_syms_by_name: int list StringMap.t; (* faster lookup *)
 }
diff --git a/checklink/ELF_utils.ml b/checklink/ELF_utils.ml
index d5c205a..5244dc8 100644
--- a/checklink/ELF_utils.ml
+++ b/checklink/ELF_utils.ml
@@ -65,19 +65,16 @@ let strip_mangling (s: string): string =
   with Not_found -> s
 
 (**
-   Returns the index of the first symbol matching the specified name, if it
-   exists.
+   Returns the list of all symbols matching the specified name.
 *)
-let ndx_of_sym_name (e: elf) (name: string): int option =
-  array_exists
-    (fun x -> strip_versioning x.st_name = strip_mangling name)
-    e.e_symtab
+let ndxes_of_sym_name (e: elf) (name: string): int list =
+  try StringMap.find (strip_mangling name) e.e_syms_by_name with Not_found -> []
 
 (**
-   Returns the list of all symbols matching the specified name.
+   Returns the index of the first symbol matching the specified name, if it
+   exists.
 *)
-let ndxes_of_sym_name (e: elf) (name: string): int list =
-  List.map fst
-    (List.filter
-       (fun (_, x) -> strip_versioning x.st_name = strip_mangling name)
-       (Array.to_list (Array.mapi (fun a b -> (a, b)) e.e_symtab)))
+let ndx_of_sym_name (e: elf) (name: string): int option =
+  match ndxes_of_sym_name e name with
+  | [] -> None
+  | h::_ -> Some(h)
diff --git a/checklink/Library.ml b/checklink/Library.ml
index 67d8a45..bb0d217 100644
--- a/checklink/Library.ml
+++ b/checklink/Library.ml
@@ -3,6 +3,8 @@ open BinPos
 
 type bitstring = Bitstring.bitstring
 
+module StringMap = Map.Make (String)
+
 let is_some: 'a option -> bool = function
 | Some(_) -> true
 | None    -> false