From 2d643429defea3c00819c1d9a288d424ad76a825 Mon Sep 17 00:00:00 2001 From: Nick Clifton Date: Fri, 21 May 2004 15:38:04 +0000 Subject: [PATCH] Add --hash-size switch to the linker --- bfd/ChangeLog | 12 +++++++++++ bfd/Makefile.am | 2 +- bfd/Makefile.in | 2 +- bfd/bfd-in.h | 5 +++++ bfd/bfd-in2.h | 5 +++++ bfd/hash.c | 55 +++++++++++++++++++++++++++++++++++-------------- ld/ChangeLog | 15 ++++++++++++++ ld/NEWS | 8 +++++++ ld/ld.h | 5 ++++- ld/ld.texinfo | 18 ++++++++++++++-- ld/ldmain.c | 4 ++++ ld/lexsup.c | 22 ++++++++++++++++++-- 12 files changed, 131 insertions(+), 22 deletions(-) diff --git a/bfd/ChangeLog b/bfd/ChangeLog index 56dbeeb4a02..824a23c42ed 100644 --- a/bfd/ChangeLog +++ b/bfd/ChangeLog @@ -1,3 +1,15 @@ +2004-05-21 Andy Chittenden + + * hash.c (bfd_default_hash_table_size): New variable. + (bfd_hash_table_init): Use new variable instead of DEFAULT_SIZE. + (bfd_hash_set_default_size): New function. Set the default size + to a selected prime number close to the argument. Document new + function. + * bfd-in.h: Add prototype for bfd_hash_set_default_size. + * bfd-in2.h: Regenerate. + * Makefile.am (hash.lo): Add dependency upon libiberty.h. + * Makefile.in: Regenerate. + 2004-05-21 Mark Kettenis * libaout.h (machine_type): Add M_88K_OPENBSD and M_HPPA_OPENBSD. diff --git a/bfd/Makefile.am b/bfd/Makefile.am index c395d3275b7..29abed03e91 100644 --- a/bfd/Makefile.am +++ b/bfd/Makefile.am @@ -894,7 +894,7 @@ syms.lo: syms.c $(INCDIR)/filenames.h $(INCDIR)/safe-ctype.h \ $(INCDIR)/bfdlink.h $(INCDIR)/aout/stab_gnu.h $(INCDIR)/aout/stab.def targets.lo: targets.c $(INCDIR)/filenames.h $(INCDIR)/fnmatch.h \ targmatch.h -hash.lo: hash.c $(INCDIR)/filenames.h $(INCDIR)/objalloc.h +hash.lo: hash.c $(INCDIR)/filenames.h $(INCDIR)/objalloc.h $(INCDIR)/libiberty.h linker.lo: linker.c $(INCDIR)/filenames.h $(INCDIR)/bfdlink.h \ genlink.h srec.lo: srec.c $(INCDIR)/filenames.h $(INCDIR)/libiberty.h \ diff --git a/bfd/Makefile.in b/bfd/Makefile.in index 4d4d784cc96..8ee31d220ae 100644 --- a/bfd/Makefile.in +++ b/bfd/Makefile.in @@ -1431,7 +1431,7 @@ syms.lo: syms.c $(INCDIR)/filenames.h $(INCDIR)/safe-ctype.h \ $(INCDIR)/bfdlink.h $(INCDIR)/aout/stab_gnu.h $(INCDIR)/aout/stab.def targets.lo: targets.c $(INCDIR)/filenames.h $(INCDIR)/fnmatch.h \ targmatch.h -hash.lo: hash.c $(INCDIR)/filenames.h $(INCDIR)/objalloc.h +hash.lo: hash.c $(INCDIR)/filenames.h $(INCDIR)/objalloc.h $(INCDIR)/libiberty.h linker.lo: linker.c $(INCDIR)/filenames.h $(INCDIR)/bfdlink.h \ genlink.h srec.lo: srec.c $(INCDIR)/filenames.h $(INCDIR)/libiberty.h \ diff --git a/bfd/bfd-in.h b/bfd/bfd-in.h index a3330e871b7..e7ed04afa7f 100644 --- a/bfd/bfd-in.h +++ b/bfd/bfd-in.h @@ -433,6 +433,11 @@ extern void bfd_hash_traverse bfd_boolean (*) (struct bfd_hash_entry *, void *), void *info); +/* Allows the default size of a hash table to be configured. New hash + tables allocated using bfd_hash_table_init will be created with + this size. */ +extern void bfd_hash_set_default_size (bfd_size_type); + #define COFF_SWAP_TABLE (void *) &bfd_coff_std_swap_table /* User program access to BFD facilities. */ diff --git a/bfd/bfd-in2.h b/bfd/bfd-in2.h index 3f38b6a5b45..1336f3664ec 100644 --- a/bfd/bfd-in2.h +++ b/bfd/bfd-in2.h @@ -440,6 +440,11 @@ extern void bfd_hash_traverse bfd_boolean (*) (struct bfd_hash_entry *, void *), void *info); +/* Allows the default size of a hash table to be configured. New hash + tables allocated using bfd_hash_table_init will be created with + this size. */ +extern void bfd_hash_set_default_size (bfd_size_type); + #define COFF_SWAP_TABLE (void *) &bfd_coff_std_swap_table /* User program access to BFD facilities. */ diff --git a/bfd/hash.c b/bfd/hash.c index 58fa5327bee..6a4bd702d73 100644 --- a/bfd/hash.c +++ b/bfd/hash.c @@ -1,28 +1,29 @@ /* hash.c -- hash table routines for BFD - Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003 + Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004 Free Software Foundation, Inc. Written by Steve Chamberlain -This file is part of BFD, the Binary File Descriptor library. + This file is part of BFD, the Binary File Descriptor library. -This program is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2 of the License, or -(at your option) any later version. + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. -This program is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. -You should have received a copy of the GNU General Public License -along with this program; if not, write to the Free Software -Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #include "bfd.h" #include "sysdep.h" #include "libbfd.h" #include "objalloc.h" +#include "libiberty.h" /* SECTION @@ -53,6 +54,7 @@ SECTION @* Looking Up or Entering a String:: @* Traversing a Hash Table:: @* Deriving a New Hash Table Type:: +@* Changing the default Hash Table Size:: @end menu INODE @@ -87,6 +89,10 @@ SUBSECTION been allocated for a hash table. This will not free up the <> itself, which you must provide. +@findex bfd_hash_set_default_size + Use <> to set the default size of + hash table to use. + INODE Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables SUBSECTION @@ -295,7 +301,8 @@ SUBSUBSECTION */ /* The default number of entries to use when creating a hash table. */ -#define DEFAULT_SIZE (4051) +#define DEFAULT_SIZE 4051 +static size_t bfd_default_hash_table_size = DEFAULT_SIZE; /* Create a new hash table, given a number of entries. */ @@ -339,7 +346,7 @@ bfd_hash_table_init (table, newfunc) struct bfd_hash_table *, const char *)); { - return bfd_hash_table_init_n (table, newfunc, DEFAULT_SIZE); + return bfd_hash_table_init_n (table, newfunc, bfd_default_hash_table_size); } /* Free a hash table. */ @@ -495,6 +502,24 @@ bfd_hash_traverse (table, func, info) } } +void +bfd_hash_set_default_size (bfd_size_type hash_size) +{ + int index; + /* Extend this prime list if you want more granularity of hash table size. */ + static bfd_size_type hash_size_primes[] = + { + 1021, 4051, 8599, 16699 + }; + + /* Work out best prime number near the hash_size. */ + for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index) + if (hash_size <= hash_size_primes[index]) + break; + + bfd_default_hash_table_size = hash_size_primes[index]; +} + /* A few different object file formats (a.out, COFF, ELF) use a string table. These functions support adding strings to a string table, returning the byte offset, and writing out the table. diff --git a/ld/ChangeLog b/ld/ChangeLog index 38bbbe772fd..46e48656ee9 100644 --- a/ld/ChangeLog +++ b/ld/ChangeLog @@ -1,3 +1,18 @@ +2004-05-21 Andy Chittenden + + * ld.h (ld_config_type): Add new field: hash_table_size. + * ldmain.c: Initialise the new field to zero. If it is non-zero + after parsing the linker's command line call + bfd_hash_set_default_size. + * lexsup.c (option_values): Add OPTION_HASH_SIZE. + (ld_options): Add hash-size. + (parse_args): Parse --hash-size option. Allow + --reduce-memory-overheads to set the default hash table size as + well. + * ld.texinfo: Document the new switch. Also mention that + --reduce-memory-overheads can affect the hash table size. + * NEWS: Mention the new feature. + 2004-05-19 J"orn Rennecke * NEWS: Mention new linker map file generation and the diff --git a/ld/NEWS b/ld/NEWS index a33c6dc70cb..1d07084e2aa 100644 --- a/ld/NEWS +++ b/ld/NEWS @@ -1,11 +1,19 @@ -*- text -*- +* A new linker command line switch has been added which allows the hash table + size to be set to a suitable prime value near to its argument. This switch + is --hash-size=. Also if the switch --reduce-memory-overheads is + used, and --hash-size has not been used, then the default value will be set + to 1021. + * Linker map files are now generated with an O(N) algorithm for finding symbols that are defined in each section. This uses about 40% more memory for symbols than the old O(N^2) algorithm. You can use the new --reduce-memory-overheads option to select the old algorithm; this option might also be used in the future to select similar tradeoffs. +Changes in 2.15: + * New PE --large-address-aware option to indicate executables support virtual addresses greater than 2 gigabytes. diff --git a/ld/ld.h b/ld/ld.h index 1061c359686..2bcf7d27acb 100644 --- a/ld/ld.h +++ b/ld/ld.h @@ -1,5 +1,5 @@ /* ld.h -- general linker header file - Copyright 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2002 + Copyright 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2002, 2004 Free Software Foundation, Inc. This file is part of GLD, the Gnu Linker. @@ -241,6 +241,9 @@ typedef struct { /* If set, only search library directories explicitly selected on the command line. */ bfd_boolean only_cmd_line_lib_dirs; + + /* The size of the hash table to use. */ + bfd_size_type hash_table_size; } ld_config_type; extern ld_config_type config; diff --git a/ld/ld.texinfo b/ld/ld.texinfo index b78d1b02680..db87e3fbbf1 100644 --- a/ld/ld.texinfo +++ b/ld/ld.texinfo @@ -1734,13 +1734,27 @@ If you specify @option{--disable-new-dtags}, no new dynamic tags will be created. By default, the new dynamic tags are not created. Note that those options are only available for ELF systems. +@kindex --hash-size=@var{number} +Set the default size of the linker's hash tables to a prime number +close to @var{number}. Increasing this value can reduce the length of +time it takes the linker to perform its tasks, at the expense of +increasing the linker's memory requirements. Similarly reducing this +value can reduce the memory requirements at the expense of speed. + @kindex --reduce-memory-overheads @item --reduce-memory-overheads This option reduces memory requirements at ld runtime, at the expense of linking speed. This was introduced to to select the old O(n^2) algorithm for link map file generation, rather than the new O(n) algorithm which uses -about 40% more memory for symbol storage. It may be also be used for -similar such tradeoffs in the future. +about 40% more memory for symbol storage. + +Another affect of the switch is to set the default hash table size to +1021, which again saves memory at the cost of lengthening the linker's +run time. This is not done however if the *option{--hash-size} switch +has been used. + +The @option{--reduce-memory-overheads} switch may be also be used to +enable other tradeoffs in future versions of the linker. @end table diff --git a/ld/ldmain.c b/ld/ldmain.c index f3df44ff9e0..f1804c438a0 100644 --- a/ld/ldmain.c +++ b/ld/ldmain.c @@ -267,6 +267,7 @@ main (int argc, char **argv) config.has_shared = FALSE; config.split_by_reloc = (unsigned) -1; config.split_by_file = (bfd_size_type) -1; + config.hash_table_size = 0; command_line.force_common_definition = FALSE; command_line.inhibit_common_definition = FALSE; command_line.interpreter = NULL; @@ -344,6 +345,9 @@ main (int argc, char **argv) lang_has_input_file = FALSE; parse_args (argc, argv); + if (config.hash_table_size != 0) + bfd_hash_set_default_size (config.hash_table_size); + ldemul_set_symbols (); if (link_info.relocatable) diff --git a/ld/lexsup.c b/ld/lexsup.c index fcca4d33dbc..51373413f10 100644 --- a/ld/lexsup.c +++ b/ld/lexsup.c @@ -118,6 +118,7 @@ enum option_values OPTION_FORCE_EXE_SUFFIX, OPTION_GC_SECTIONS, OPTION_NO_GC_SECTIONS, + OPTION_HASH_SIZE, OPTION_CHECK_SECTIONS, OPTION_NO_CHECK_SECTIONS, OPTION_NO_UNDEFINED, @@ -328,6 +329,8 @@ static const struct ld_option ld_options[] = { {"no-gc-sections", no_argument, NULL, OPTION_NO_GC_SECTIONS}, '\0', NULL, N_("Don't remove unused sections (default)"), TWO_DASHES }, + { {"hash-size=", required_argument, NULL, OPTION_HASH_SIZE}, + '\0', NULL, N_("Set default hash table size close to "), TWO_DASHES }, { {"help", no_argument, NULL, OPTION_HELP}, '\0', NULL, N_("Print option help"), TWO_DASHES }, { {"init", required_argument, NULL, OPTION_INIT}, @@ -364,6 +367,8 @@ static const struct ld_option ld_options[] = '\0', N_("TARGET"), N_("Specify target of output file"), EXACTLY_TWO_DASHES }, { {"qmagic", no_argument, NULL, OPTION_IGNORE}, '\0', NULL, N_("Ignored for Linux compatibility"), ONE_DASH }, + { {"reduce-memory-overheads", no_argument, NULL, OPTION_REDUCE_MEMORY_OVERHEADS}, + '\0', NULL, N_("Reduce memory overheads, possibly taking much longer"), TWO_DASHES }, { {"relax", no_argument, NULL, OPTION_RELAX}, '\0', NULL, N_("Relax branches on certain targets"), TWO_DASHES }, { {"retain-symbols-file", required_argument, NULL, @@ -447,8 +452,6 @@ static const struct ld_option ld_options[] = '\0', NULL, N_("Always set DT_NEEDED for following dynamic libs"), TWO_DASHES }, { {"wrap", required_argument, NULL, OPTION_WRAP}, '\0', N_("SYMBOL"), N_("Use wrapper functions for SYMBOL"), TWO_DASHES }, - { {"reduce-memory-overheads", no_argument, NULL, OPTION_REDUCE_MEMORY_OVERHEADS}, - '\0', NULL, N_("reduce memory overheads, possibly taking much longer"), TWO_DASHES }, }; #define OPTION_COUNT ARRAY_SIZE (ld_options) @@ -1224,9 +1227,24 @@ parse_args (unsigned argc, char **argv) case OPTION_FINI: link_info.fini_function = optarg; break; + case OPTION_REDUCE_MEMORY_OVERHEADS: command_line.reduce_memory_overheads = TRUE; + if (config.hash_table_size == 0) + config.hash_table_size = 1021; break; + + case OPTION_HASH_SIZE: + { + bfd_size_type new_size; + + new_size = strtoul (optarg, NULL, 0); + if (new_size) + config.hash_table_size = new_size; + else + einfo (_("%P%X: --hash-size needs a numeric argument\n")); + } + break; } } -- 2.30.2