From 23b04dd211287eb1c841c129705af39afbe0ab15 Mon Sep 17 00:00:00 2001 From: varobert Date: Thu, 12 Apr 2012 11:31:33 +0000 Subject: 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 --- checklink/Check.ml | 17 ++++++++++++++++- checklink/ELF_parsers.ml | 24 +++++++++++++++++------- checklink/ELF_types.ml | 13 +++++++------ checklink/ELF_utils.ml | 21 +++++++++------------ checklink/Library.ml | 2 ++ 5 files changed, 51 insertions(+), 26 deletions(-) (limited to 'checklink') 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 -- cgit v1.2.3