* DT_GNU_HASH benchmark results [not found] ` <20060705090438.GJ3823@sunsite.mff.cuni.cz> @ 2006-07-06 11:26 ` Jakub Jelinek 2006-07-06 18:22 ` DT_GNU_HASH latest patches Jakub Jelinek 0 siblings, 1 reply; 17+ messages in thread From: Jakub Jelinek @ 2006-07-06 11:26 UTC (permalink / raw) To: binutils; +Cc: djamel anonymous, Ulrich Drepper, Michael Meeks, libc-alpha On Wed, Jul 05, 2006 at 11:04:38AM +0200, Jakub Jelinek wrote: > I'll try to benchmark both of these variants and see if it is really worth > it. I've repeated the same tests as I've reported on Jun, 28th, this time in 2 new different chroots. One had (almost) all the dependent libraries built with --hash-style=both 2006-07-03 layout of .gnu.hash (i.e. nbuckets|symidx|nbuckets*chainoff|hash0&~1|hash1&~1|hash2bitor1|...| ) - take2 in the results, the other had the enlarged buckets array, i.e. nbuckets|symidx|nbuckets*<chainoff|bitmask>|hash0&~1|hash1&~1|hash2bitor1|...| where bitmask would contain bit N set there are any hashes in the chain such that ((hash >> 5) & 31) == N. It is not using the LS bits, because those contain the sum of all characters in the symbol name, which isn't ideal. Binutils guaranteed that nbuckets is at least 2 and never a multiple of 32 - this tree is take3 in the results. take3 reduces a lot the number of L1 misses, on the other side slightly increases L2 misses (supposedly because .gnu.hash is now bigger), but overall it sounds like take3 is desirable. Will now do a few small changes suggested by Uli late last night and then post the final patches. I don't want to make nbuckets a power of two, the division really isn't very expensive on contemporary CPUs and we don't want multiple of 32 nbuckets for the bitmask trick to work properly. cat > a.c <<\EOF cat /tmp/a.c #include <dlfcn.h> const char *libs[] = { "libvclplug_gtk680lx.so", "libvclplug_gen680lx.so", "libnss_files.so.2", "libGL.so.1", "servicemgr.uno.so", "shlibloader.uno.so", "simplereg.uno.so", "nestedreg.uno.so", "typemgr.uno.so", "implreg.uno.so", "security.uno.so", "libreg.so.3", "libstore.so.3", "regtypeprov.uno.so", "configmgr2.uno.so", "typeconverter.uno.so", "gconfbe1.uno.so", "behelper.uno.so", "sax.uno.so", "localebe1.uno.so", "uriproc.uno.so", "libspl680lx.so", "libucb1.so", "ucpgvfs1.uno.so", "libgcc3_uno.so", "libpackage2.so", "libfileacc.so", "libuui680lx.so", "libfilterconfig1.so", "libdtransX11680lx.so", "i18npool.uno.so", "liblocaledata_en.so", "fsstorage.uno.so", "libxstor.so", "libdbtools680lx.so", "libcups.so.2", "libgnutls.so.13", "libgcrypt.so.11", "libgpg-error.so.0", "libmcnttype.so", "libucpchelp1.so", "svtmisc.uno.so" }; int main (int argc, char **argv) { int i; void *h; int flags = RTLD_LAZY; if (argv[1][0] == 'g') flags |= RTLD_GLOBAL; for (i = 0; i < sizeof (libs) / sizeof (libs[0]); ++i) h = dlopen (libs[i], flags); return 0; } EOF gcc -g -O2 -o a a.c -Wl,-rpath,/usr/lib64/openoffice.org2.0/program/ \ -L/usr/lib64/openoffice.org2.0/program/ -lsoffice -lsw680lx -lsvx680lx -lstdc++ -lm -shared-libgcc for V in local global; do for M in '' 'export LD_X=1' 'export LD_BIND_NOW=1' 'export LD_X=1 LD_BIND_NOW=1'; \ do ( for i in 1 2 3 4; do eval $M; time ./a $V; done 2>&1 > /dev/null | \ awk 'BEGIN { printf "'"$V $M"'\t" } /^real/ { printf "%s ", $2 } END { printf "\n" }' ); done; done take2 local 0m0.247s 0m0.244s 0m0.243s 0m0.245s local export LD_X=1 0m0.541s 0m0.541s 0m0.540s 0m0.542s local export LD_BIND_NOW=1 0m0.455s 0m0.451s 0m0.449s 0m0.452s local export LD_X=1 LD_BIND_NOW=1 0m1.102s 0m1.100s 0m1.099s 0m1.101s global 0m0.284s 0m0.281s 0m0.279s 0m0.279s global export LD_X=1 0m0.623s 0m0.621s 0m0.622s 0m0.620s global export LD_BIND_NOW=1 0m0.518s 0m0.514s 0m0.515s 0m0.517s global export LD_X=1 LD_BIND_NOW=1 0m1.250s 0m1.246s 0m1.247s 0m1.246s take3 local 0m0.212s 0m0.211s 0m0.211s 0m0.212s local export LD_X=1 0m0.556s 0m0.579s 0m0.583s 0m0.577s local export LD_BIND_NOW=1 0m0.391s 0m0.385s 0m0.383s 0m0.384s local export LD_X=1 LD_BIND_NOW=1 0m1.124s 0m1.157s 0m1.178s 0m1.169s global 0m0.241s 0m0.240s 0m0.240s 0m0.240s global export LD_X=1 0m0.642s 0m0.665s 0m0.662s 0m0.661s global export LD_BIND_NOW=1 0m0.438s 0m0.438s 0m0.434s 0m0.436s global export LD_X=1 LD_BIND_NOW=1 0m1.280s 0m1.326s 0m1.318s 0m1.321s for V in local global; do for M in '' 'export LD_X=1' 'export LD_BIND_NOW=1' 'export LD_X=1 LD_BIND_NOW=1'; \ do ( echo "$V $M"; eval $M; valgrind --tool=cachegrind ./a $V 2>&1 > /dev/null | sed -n '/== I refs/,$p' ); \ done; done take2 local ==5984== I refs: 206,039,807 ==5984== I1 misses: 11,336 ==5984== L2i misses: 10,079 ==5984== I1 miss rate: 0.00% ==5984== L2i miss rate: 0.00% ==5984== ==5984== D refs: 75,347,721 (58,986,205 rd + 16,361,516 wr) ==5984== D1 misses: 4,444,606 ( 4,290,272 rd + 154,334 wr) ==5984== L2d misses: 506,231 ( 413,982 rd + 92,249 wr) ==5984== D1 miss rate: 5.8% ( 7.2% + 0.9% ) ==5984== L2d miss rate: 0.6% ( 0.7% + 0.5% ) ==5984== ==5984== L2 refs: 4,455,942 ( 4,301,608 rd + 154,334 wr) ==5984== L2 misses: 516,310 ( 424,061 rd + 92,249 wr) ==5984== L2 miss rate: 0.1% ( 0.1% + 0.5% ) local export LD_X=1 ==5988== I refs: 306,750,046 ==5988== I1 misses: 11,334 ==5988== L2i misses: 10,489 ==5988== I1 miss rate: 0.00% ==5988== L2i miss rate: 0.00% ==5988== ==5988== D refs: 127,819,504 (98,014,006 rd + 29,805,498 wr) ==5988== D1 misses: 9,632,662 ( 9,469,418 rd + 163,244 wr) ==5988== L2d misses: 3,029,744 ( 2,924,102 rd + 105,642 wr) ==5988== D1 miss rate: 7.5% ( 9.6% + 0.5% ) ==5988== L2d miss rate: 2.3% ( 2.9% + 0.3% ) ==5988== ==5988== L2 refs: 9,643,996 ( 9,480,752 rd + 163,244 wr) ==5988== L2 misses: 3,040,233 ( 2,934,591 rd + 105,642 wr) ==5988== L2 miss rate: 0.6% ( 0.7% + 0.3% ) local export LD_BIND_NOW=1 ==5992== I refs: 399,954,112 ==5992== I1 misses: 10,955 ==5992== L2i misses: 9,868 ==5992== I1 miss rate: 0.00% ==5992== L2i miss rate: 0.00% ==5992== ==5992== D refs: 149,744,874 (116,766,890 rd + 32,977,984 wr) ==5992== D1 misses: 9,146,137 ( 8,945,587 rd + 200,550 wr) ==5992== L2d misses: 673,564 ( 573,758 rd + 99,806 wr) ==5992== D1 miss rate: 6.1% ( 7.6% + 0.6% ) ==5992== L2d miss rate: 0.4% ( 0.4% + 0.3% ) ==5992== ==5992== L2 refs: 9,157,092 ( 8,956,542 rd + 200,550 wr) ==5992== L2 misses: 683,432 ( 583,626 rd + 99,806 wr) ==5992== L2 miss rate: 0.1% ( 0.1% + 0.3% ) local export LD_X=1 LD_BIND_NOW=1 ==5996== I refs: 612,477,609 ==5996== I1 misses: 10,953 ==5996== L2i misses: 10,129 ==5996== I1 miss rate: 0.00% ==5996== L2i miss rate: 0.00% ==5996== ==5996== D refs: 261,643,870 (199,575,161 rd + 62,068,709 wr) ==5996== D1 misses: 20,389,219 ( 20,198,114 rd + 191,105 wr) ==5996== L2d misses: 6,306,926 ( 6,193,450 rd + 113,476 wr) ==5996== D1 miss rate: 7.7% ( 10.1% + 0.3% ) ==5996== L2d miss rate: 2.4% ( 3.1% + 0.1% ) ==5996== ==5996== L2 refs: 20,400,172 ( 20,209,067 rd + 191,105 wr) ==5996== L2 misses: 6,317,055 ( 6,203,579 rd + 113,476 wr) ==5996== L2 miss rate: 0.7% ( 0.7% + 0.1% ) global ==6000== I refs: 221,176,210 ==6000== I1 misses: 11,605 ==6000== L2i misses: 10,263 ==6000== I1 miss rate: 0.00% ==6000== L2i miss rate: 0.00% ==6000== ==6000== D refs: 82,903,948 (64,808,080 rd + 18,095,868 wr) ==6000== D1 misses: 6,361,596 ( 6,203,856 rd + 157,740 wr) ==6000== L2d misses: 534,670 ( 441,893 rd + 92,777 wr) ==6000== D1 miss rate: 7.6% ( 9.5% + 0.8% ) ==6000== L2d miss rate: 0.6% ( 0.6% + 0.5% ) ==6000== ==6000== L2 refs: 6,373,201 ( 6,215,461 rd + 157,740 wr) ==6000== L2 misses: 544,933 ( 452,156 rd + 92,777 wr) ==6000== L2 miss rate: 0.1% ( 0.1% + 0.5% ) global export LD_X=1 ==6004== I refs: 331,769,024 ==6004== I1 misses: 11,603 ==6004== L2i misses: 10,705 ==6004== I1 miss rate: 0.00% ==6004== L2i miss rate: 0.00% ==6004== ==6004== D refs: 140,927,783 (107,887,754 rd + 33,040,029 wr) ==6004== D1 misses: 12,061,356 ( 11,896,678 rd + 164,678 wr) ==6004== L2d misses: 3,511,000 ( 3,404,823 rd + 106,177 wr) ==6004== D1 miss rate: 8.5% ( 11.0% + 0.4% ) ==6004== L2d miss rate: 2.4% ( 3.1% + 0.3% ) ==6004== ==6004== L2 refs: 12,072,959 ( 11,908,281 rd + 164,678 wr) ==6004== L2 misses: 3,521,705 ( 3,415,528 rd + 106,177 wr) ==6004== L2 miss rate: 0.7% ( 0.7% + 0.3% ) global export LD_BIND_NOW=1 ==6008== I refs: 427,418,120 ==6008== I1 misses: 11,204 ==6008== L2i misses: 10,041 ==6008== I1 miss rate: 0.00% ==6008== L2i miss rate: 0.00% ==6008== ==6008== D refs: 163,419,797 (127,305,645 rd + 36,114,152 wr) ==6008== D1 misses: 12,599,471 ( 12,390,660 rd + 208,811 wr) ==6008== L2d misses: 721,852 ( 621,527 rd + 100,325 wr) ==6008== D1 miss rate: 7.7% ( 9.7% + 0.5% ) ==6008== L2d miss rate: 0.4% ( 0.4% + 0.2% ) ==6008== ==6008== L2 refs: 12,610,675 ( 12,401,864 rd + 208,811 wr) ==6008== L2 misses: 731,893 ( 631,568 rd + 100,325 wr) ==6008== L2 miss rate: 0.1% ( 0.1% + 0.2% ) global export LD_X=1 LD_BIND_NOW=1 ==6012== I refs: 657,379,875 ==6012== I1 misses: 11,204 ==6012== L2i misses: 10,320 ==6012== I1 miss rate: 0.00% ==6012== L2i miss rate: 0.00% ==6012== ==6012== D refs: 285,228,684 (217,319,888 rd + 67,908,796 wr) ==6012== D1 misses: 24,774,666 ( 24,579,918 rd + 194,748 wr) ==6012== L2d misses: 7,207,303 ( 7,093,279 rd + 114,024 wr) ==6012== D1 miss rate: 8.6% ( 11.3% + 0.2% ) ==6012== L2d miss rate: 2.5% ( 3.2% + 0.1% ) ==6012== ==6012== L2 refs: 24,785,870 ( 24,591,122 rd + 194,748 wr) ==6012== L2 misses: 7,217,623 ( 7,103,599 rd + 114,024 wr) ==6012== L2 miss rate: 0.7% ( 0.8% + 0.1% ) take3 local ==5139== I refs: 192,860,473 ==5139== I1 misses: 12,387 ==5139== L2i misses: 10,120 ==5139== I1 miss rate: 0.00% ==5139== L2i miss rate: 0.00% ==5139== ==5139== D refs: 72,521,147 (56,099,943 rd + 16,421,204 wr) ==5139== D1 misses: 3,413,455 ( 3,256,926 rd + 156,529 wr) ==5139== L2d misses: 525,073 ( 433,257 rd + 91,816 wr) ==5139== D1 miss rate: 4.7% ( 5.8% + 0.9% ) ==5139== L2d miss rate: 0.7% ( 0.7% + 0.5% ) ==5139== ==5139== L2 refs: 3,425,842 ( 3,269,313 rd + 156,529 wr) ==5139== L2 misses: 535,193 ( 443,377 rd + 91,816 wr) ==5139== L2 miss rate: 0.2% ( 0.1% + 0.5% ) local export LD_X=1 ==5143== I refs: 307,040,928 ==5143== I1 misses: 12,381 ==5143== L2i misses: 10,684 ==5143== I1 miss rate: 0.00% ==5143== L2i miss rate: 0.00% ==5143== ==5143== D refs: 127,932,904 (98,064,136 rd + 29,868,768 wr) ==5143== D1 misses: 9,484,151 ( 9,320,536 rd + 163,615 wr) ==5143== L2d misses: 3,014,606 ( 2,909,020 rd + 105,586 wr) ==5143== D1 miss rate: 7.4% ( 9.5% + 0.5% ) ==5143== L2d miss rate: 2.3% ( 2.9% + 0.3% ) ==5143== ==5143== L2 refs: 9,496,532 ( 9,332,917 rd + 163,615 wr) ==5143== L2 misses: 3,025,290 ( 2,919,704 rd + 105,586 wr) ==5143== L2 miss rate: 0.6% ( 0.7% + 0.3% ) local export LD_BIND_NOW=1 ==5147== I refs: 371,723,469 ==5147== I1 misses: 11,941 ==5147== L2i misses: 9,909 ==5147== I1 miss rate: 0.00% ==5147== L2i miss rate: 0.00% ==5147== ==5147== D refs: 143,691,228 (110,589,376 rd + 33,101,852 wr) ==5147== D1 misses: 6,960,878 ( 6,773,347 rd + 187,531 wr) ==5147== L2d misses: 721,548 ( 622,166 rd + 99,382 wr) ==5147== D1 miss rate: 4.8% ( 6.1% + 0.5% ) ==5147== L2d miss rate: 0.5% ( 0.5% + 0.3% ) ==5147== ==5147== L2 refs: 6,972,819 ( 6,785,288 rd + 187,531 wr) ==5147== L2 misses: 731,457 ( 632,075 rd + 99,382 wr) ==5147== L2 miss rate: 0.1% ( 0.1% + 0.3% ) local export LD_X=1 LD_BIND_NOW=1 ==5151== I refs: 613,042,464 ==5151== I1 misses: 11,940 ==5151== L2i misses: 10,409 ==5151== I1 miss rate: 0.00% ==5151== L2i miss rate: 0.00% ==5151== ==5151== D refs: 261,868,433 (199,669,277 rd + 62,199,156 wr) ==5151== D1 misses: 20,184,839 ( 19,970,673 rd + 214,166 wr) ==5151== L2d misses: 6,271,011 ( 6,157,540 rd + 113,471 wr) ==5151== D1 miss rate: 7.7% ( 10.0% + 0.3% ) ==5151== L2d miss rate: 2.3% ( 3.0% + 0.1% ) ==5151== ==5151== L2 refs: 20,196,779 ( 19,982,613 rd + 214,166 wr) ==5151== L2 misses: 6,281,420 ( 6,167,949 rd + 113,471 wr) ==5151== L2 miss rate: 0.7% ( 0.7% + 0.1% ) global ==5155== I refs: 206,478,881 ==5155== I1 misses: 12,681 ==5155== L2i misses: 10,302 ==5155== I1 miss rate: 0.00% ==5155== L2i miss rate: 0.00% ==5155== ==5155== D refs: 79,796,888 (61,641,432 rd + 18,155,456 wr) ==5155== D1 misses: 5,204,611 ( 5,046,697 rd + 157,914 wr) ==5155== L2d misses: 551,003 ( 458,783 rd + 92,220 wr) ==5155== D1 miss rate: 6.5% ( 8.1% + 0.8% ) ==5155== L2d miss rate: 0.6% ( 0.7% + 0.5% ) ==5155== ==5155== L2 refs: 5,217,292 ( 5,059,378 rd + 157,914 wr) ==5155== L2 misses: 561,305 ( 469,085 rd + 92,220 wr) ==5155== L2 miss rate: 0.1% ( 0.1% + 0.5% ) global export LD_X=1 ==5159== I refs: 332,044,535 ==5159== I1 misses: 12,675 ==5159== L2i misses: 11,000 ==5159== I1 miss rate: 0.00% ==5159== L2i miss rate: 0.00% ==5159== ==5159== D refs: 141,034,475 (107,932,723 rd + 33,101,752 wr) ==5159== D1 misses: 11,988,824 ( 11,824,286 rd + 164,538 wr) ==5159== L2d misses: 3,491,915 ( 3,385,840 rd + 106,075 wr) ==5159== D1 miss rate: 8.5% ( 10.9% + 0.4% ) ==5159== L2d miss rate: 2.4% ( 3.1% + 0.3% ) ==5159== ==5159== L2 refs: 12,001,499 ( 11,836,961 rd + 164,538 wr) ==5159== L2 misses: 3,502,915 ( 3,396,840 rd + 106,075 wr) ==5159== L2 miss rate: 0.7% ( 0.7% + 0.3% ) global export LD_BIND_NOW=1 ==5165== I refs: 396,437,452 ==5165== I1 misses: 12,211 ==5165== L2i misses: 10,092 ==5165== I1 miss rate: 0.00% ==5165== L2i miss rate: 0.00% ==5165== ==5165== D refs: 156,857,604 (120,619,707 rd + 36,237,897 wr) ==5165== D1 misses: 10,195,672 ( 10,010,304 rd + 185,368 wr) ==5165== L2d misses: 767,253 ( 667,448 rd + 99,805 wr) ==5165== D1 miss rate: 6.4% ( 8.2% + 0.5% ) ==5165== L2d miss rate: 0.4% ( 0.5% + 0.2% ) ==5165== ==5165== L2 refs: 10,207,883 ( 10,022,515 rd + 185,368 wr) ==5165== L2 misses: 777,345 ( 677,540 rd + 99,805 wr) ==5165== L2 miss rate: 0.1% ( 0.1% + 0.2% ) global export LD_X=1 LD_BIND_NOW=1 ==5169== I refs: 657,927,738 ==5169== I1 misses: 12,211 ==5169== L2i misses: 10,669 ==5169== I1 miss rate: 0.00% ==5169== L2i miss rate: 0.00% ==5169== ==5169== D refs: 285,446,109 (217,408,377 rd + 68,037,732 wr) ==5169== D1 misses: 24,704,584 ( 24,488,640 rd + 215,944 wr) ==5169== L2d misses: 7,165,792 ( 7,051,869 rd + 113,923 wr) ==5169== D1 miss rate: 8.6% ( 11.2% + 0.3% ) ==5169== L2d miss rate: 2.5% ( 3.2% + 0.1% ) ==5169== ==5169== L2 refs: 24,716,795 ( 24,500,851 rd + 215,944 wr) ==5169== L2 misses: 7,176,461 ( 7,062,538 rd + 113,923 wr) ==5169== L2 miss rate: 0.7% ( 0.8% + 0.1% ) for V in local global; do for M in '' '-E LD_X=1' '-E LD_BIND_NOW=1' '-E LD_X=1 -E LD_BIND_NOW=1'; \ do ( echo "$V $M"; ./timing $M ./a $V ); done; done take2 local Strip out best and worst realtime result minimum: 0.241084000 sec real / 0.000055769 sec CPU maximum: 0.248671000 sec real / 0.000073555 sec CPU average: 0.242298357 sec real / 0.000064487 sec CPU stdev : 0.001100542 sec real / 0.000003072 sec CPU local -E LD_X=1 optarg="LD_X=1" Strip out best and worst realtime result minimum: 0.537341000 sec real / 0.000066888 sec CPU maximum: 0.545505000 sec real / 0.000082234 sec CPU average: 0.539162642 sec real / 0.000073861 sec CPU stdev : 0.000877479 sec real / 0.000001513 sec CPU local -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.447226000 sec real / 0.000048417 sec CPU maximum: 0.454843000 sec real / 0.000074707 sec CPU average: 0.449379357 sec real / 0.000069658 sec CPU stdev : 0.001006922 sec real / 0.000004595 sec CPU local -E LD_X=1 -E LD_BIND_NOW=1 optarg="LD_X=1" optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 1.096843000 sec real / 0.000057979 sec CPU maximum: 1.108830000 sec real / 0.000072577 sec CPU average: 1.099736928 sec real / 0.000064127 sec CPU stdev : 0.002059076 sec real / 0.000001466 sec CPU global Strip out best and worst realtime result minimum: 0.277778000 sec real / 0.000056801 sec CPU maximum: 0.287137000 sec real / 0.000082176 sec CPU average: 0.279447607 sec real / 0.000072339 sec CPU stdev : 0.001470227 sec real / 0.000004583 sec CPU global -E LD_X=1 optarg="LD_X=1" Strip out best and worst realtime result minimum: 0.618532000 sec real / 0.000065063 sec CPU maximum: 0.637458000 sec real / 0.000085827 sec CPU average: 0.623114250 sec real / 0.000074015 sec CPU stdev : 0.004356701 sec real / 0.000003608 sec CPU global -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.513478000 sec real / 0.000062431 sec CPU maximum: 0.524921000 sec real / 0.000076080 sec CPU average: 0.517233357 sec real / 0.000072163 sec CPU stdev : 0.003029441 sec real / 0.000002879 sec CPU global -E LD_X=1 -E LD_BIND_NOW=1 optarg="LD_X=1" optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 1.243250000 sec real / 0.000055890 sec CPU maximum: 1.252460000 sec real / 0.000073371 sec CPU average: 1.245845642 sec real / 0.000063768 sec CPU stdev : 0.001419068 sec real / 0.000002191 sec CPU take3 local Strip out best and worst realtime result minimum: 0.207072000 sec real / 0.000059167 sec CPU maximum: 0.213904000 sec real / 0.000073101 sec CPU average: 0.208218392 sec real / 0.000064074 sec CPU stdev : 0.001025499 sec real / 0.000001562 sec CPU local -E LD_X=1 optarg="LD_X=1" Strip out best and worst realtime result minimum: 0.544442000 sec real / 0.000065068 sec CPU maximum: 0.575327000 sec real / 0.000083959 sec CPU average: 0.552129321 sec real / 0.000074002 sec CPU stdev : 0.003887680 sec real / 0.000002200 sec CPU local -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.374172000 sec real / 0.000064850 sec CPU maximum: 0.379919000 sec real / 0.000074617 sec CPU average: 0.376311357 sec real / 0.000072356 sec CPU stdev : 0.001204166 sec real / 0.000002292 sec CPU local -E LD_X=1 -E LD_BIND_NOW=1 optarg="LD_X=1" optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 1.101936000 sec real / 0.000059454 sec CPU maximum: 1.177582000 sec real / 0.000070216 sec CPU average: 1.118296642 sec real / 0.000064014 sec CPU stdev : 0.010025261 sec real / 0.000001281 sec CPU global Strip out best and worst realtime result minimum: 0.236546000 sec real / 0.000057142 sec CPU maximum: 0.246220000 sec real / 0.000065733 sec CPU average: 0.239646714 sec real / 0.000063370 sec CPU stdev : 0.002348865 sec real / 0.000002093 sec CPU global -E LD_X=1 optarg="LD_X=1" Strip out best and worst realtime result minimum: 0.630578000 sec real / 0.000063307 sec CPU maximum: 0.662570000 sec real / 0.000079459 sec CPU average: 0.642624142 sec real / 0.000073384 sec CPU stdev : 0.006348274 sec real / 0.000003411 sec CPU global -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.428218000 sec real / 0.000062262 sec CPU maximum: 0.437902000 sec real / 0.000076227 sec CPU average: 0.431983142 sec real / 0.000070362 sec CPU stdev : 0.002499419 sec real / 0.000002465 sec CPU global -E LD_X=1 -E LD_BIND_NOW=1 optarg="LD_X=1" optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 1.255278000 sec real / 0.000059120 sec CPU maximum: 1.337006000 sec real / 0.000072259 sec CPU average: 1.281770035 sec real / 0.000064085 sec CPU stdev : 0.013042264 sec real / 0.000001631 sec CPU /usr/sbin/prelink -vmR ./a for V in local global; do for M in '' 'export LD_X=1' 'export LD_BIND_NOW=1' 'export LD_X=1 LD_BIND_NOW=1'; \ do ( for i in 1 2 3 4; do eval $M; time ./a $V; done 2>&1 > /dev/null | \ awk 'BEGIN { printf "'"$V $M"'\t" } /^real/ { printf "%s ", $2 } END { printf "\n" }' ); done; done take2 local 0m0.134s 0m0.132s 0m0.131s 0m0.131s local export LD_X=1 0m0.270s 0m0.267s 0m0.268s 0m0.267s local export LD_BIND_NOW=1 0m0.228s 0m0.226s 0m0.226s 0m0.226s local export LD_X=1 LD_BIND_NOW=1 0m0.507s 0m0.499s 0m0.500s 0m0.499s global 0m0.167s 0m0.165s 0m0.165s 0m0.166s global export LD_X=1 0m0.347s 0m0.344s 0m0.345s 0m0.344s global export LD_BIND_NOW=1 0m0.289s 0m0.288s 0m0.287s 0m0.286s global export LD_X=1 LD_BIND_NOW=1 0m0.657s 0m0.642s 0m0.641s 0m0.640s take3 local 0m0.112s 0m0.109s 0m0.109s 0m0.108s local export LD_X=1 0m0.268s 0m0.273s 0m0.265s 0m0.264s local export LD_BIND_NOW=1 0m0.183s 0m0.180s 0m0.181s 0m0.180s local export LD_X=1 LD_BIND_NOW=1 0m0.506s 0m0.494s 0m0.504s 0m0.497s global 0m0.140s 0m0.136s 0m0.137s 0m0.137s global export LD_X=1 0m0.353s 0m0.346s 0m0.345s 0m0.343s global export LD_BIND_NOW=1 0m0.235s 0m0.232s 0m0.233s 0m0.231s global export LD_X=1 LD_BIND_NOW=1 0m0.647s 0m0.640s 0m0.645s 0m0.643s # valgrind --tool=cachegrind stats not provided for prelinked testcase, # as valgrind apparently uses LD_PRELOAD internally and thus prevents # prelinking. for V in local global; do for M in '' '-E LD_X=1' '-E LD_BIND_NOW=1' '-E LD_X=1 -E LD_BIND_NOW=1'; \ do ( echo "$V $M"; ./timing $M ./a $V ); done; done take2 local Strip out best and worst realtime result minimum: 0.129763000 sec real / 0.000051852 sec CPU maximum: 0.133951000 sec real / 0.000067645 sec CPU average: 0.130537178 sec real / 0.000062305 sec CPU stdev : 0.000481749 sec real / 0.000001382 sec CPU local -E LD_X=1 optarg="LD_X=1" Strip out best and worst realtime result minimum: 0.264604000 sec real / 0.000062178 sec CPU maximum: 0.274639000 sec real / 0.000085800 sec CPU average: 0.267029107 sec real / 0.000071314 sec CPU stdev : 0.001715647 sec real / 0.000003884 sec CPU local -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.224145000 sec real / 0.000056408 sec CPU maximum: 0.233185000 sec real / 0.000063897 sec CPU average: 0.225996464 sec real / 0.000062388 sec CPU stdev : 0.000731068 sec real / 0.000001113 sec CPU local -E LD_X=1 -E LD_BIND_NOW=1 optarg="LD_X=1" optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.497700000 sec real / 0.000064336 sec CPU maximum: 0.506782000 sec real / 0.000082528 sec CPU average: 0.500931285 sec real / 0.000072029 sec CPU stdev : 0.001461852 sec real / 0.000002125 sec CPU global Strip out best and worst realtime result minimum: 0.163840000 sec real / 0.000054914 sec CPU maximum: 0.170908000 sec real / 0.000069313 sec CPU average: 0.164924250 sec real / 0.000061514 sec CPU stdev : 0.000564632 sec real / 0.000001893 sec CPU global -E LD_X=1 optarg="LD_X=1" Strip out best and worst realtime result minimum: 0.342633000 sec real / 0.000062245 sec CPU maximum: 0.351814000 sec real / 0.000073874 sec CPU average: 0.346293321 sec real / 0.000070698 sec CPU stdev : 0.002620913 sec real / 0.000002831 sec CPU global -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.285191000 sec real / 0.000062101 sec CPU maximum: 0.293454000 sec real / 0.000073980 sec CPU average: 0.287895000 sec real / 0.000071590 sec CPU stdev : 0.002337740 sec real / 0.000001967 sec CPU global -E LD_X=1 -E LD_BIND_NOW=1 optarg="LD_X=1" optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.638814000 sec real / 0.000063557 sec CPU maximum: 0.659667000 sec real / 0.000086187 sec CPU average: 0.643091392 sec real / 0.000073052 sec CPU stdev : 0.003414747 sec real / 0.000002750 sec CPU take3 local Strip out best and worst realtime result minimum: 0.106563000 sec real / 0.000056654 sec CPU maximum: 0.156301000 sec real / 0.000069681 sec CPU average: 0.107375964 sec real / 0.000063363 sec CPU stdev : 0.000376538 sec real / 0.000001826 sec CPU local -E LD_X=1 optarg="LD_X=1" Strip out best and worst realtime result minimum: 0.262108000 sec real / 0.000065873 sec CPU maximum: 0.268947000 sec real / 0.000079329 sec CPU average: 0.265046500 sec real / 0.000074189 sec CPU stdev : 0.001349294 sec real / 0.000002202 sec CPU local -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.178339000 sec real / 0.000058372 sec CPU maximum: 0.180964000 sec real / 0.000070478 sec CPU average: 0.179214142 sec real / 0.000063930 sec CPU stdev : 0.000602966 sec real / 0.000000961 sec CPU local -E LD_X=1 -E LD_BIND_NOW=1 optarg="LD_X=1" optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.492687000 sec real / 0.000064509 sec CPU maximum: 0.509753000 sec real / 0.000090265 sec CPU average: 0.498109571 sec real / 0.000074401 sec CPU stdev : 0.002885770 sec real / 0.000001602 sec CPU global Strip out best and worst realtime result minimum: 0.135356000 sec real / 0.000055916 sec CPU maximum: 0.157524000 sec real / 0.000067681 sec CPU average: 0.137677178 sec real / 0.000062051 sec CPU stdev : 0.001880825 sec real / 0.000003219 sec CPU global -E LD_X=1 optarg="LD_X=1" Strip out best and worst realtime result minimum: 0.341822000 sec real / 0.000064653 sec CPU maximum: 0.396209000 sec real / 0.000080133 sec CPU average: 0.344525392 sec real / 0.000073766 sec CPU stdev : 0.001928640 sec real / 0.000003070 sec CPU global -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.230014000 sec real / 0.000057105 sec CPU maximum: 0.236641000 sec real / 0.000079505 sec CPU average: 0.231364928 sec real / 0.000065419 sec CPU stdev : 0.001134105 sec real / 0.000003888 sec CPU global -E LD_X=1 -E LD_BIND_NOW=1 optarg="LD_X=1" optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.636048000 sec real / 0.000064933 sec CPU maximum: 0.673287000 sec real / 0.000077339 sec CPU average: 0.645732678 sec real / 0.000073476 sec CPU stdev : 0.006697649 sec real / 0.000001922 sec CPU Jakub ^ permalink raw reply [flat|nested] 17+ messages in thread
* DT_GNU_HASH latest patches 2006-07-06 11:26 ` DT_GNU_HASH benchmark results Jakub Jelinek @ 2006-07-06 18:22 ` Jakub Jelinek 2006-07-06 19:53 ` djamel anonymous 2006-07-07 10:07 ` Michael Meeks 0 siblings, 2 replies; 17+ messages in thread From: Jakub Jelinek @ 2006-07-06 18:22 UTC (permalink / raw) To: binutils; +Cc: djamel anonymous, Ulrich Drepper, Michael Meeks, libc-alpha [-- Attachment #1: Type: text/plain, Size: 1455 bytes --] On Thu, Jul 06, 2006 at 01:25:35PM +0200, Jakub Jelinek wrote: > Will now do a few small changes suggested by Uli late last night and then > post the final patches. I don't want to make nbuckets a power of two, > the division really isn't very expensive on contemporary CPUs and we don't > want multiple of 32 nbuckets for the bitmask trick to work properly. And here are the hopefully final patches. Changes today: 1) swapped chainoff and bitmask in the buckets array pairs - bitmask is accessed first by ld.so, so it makes sense to put it first 2) chainoff fields in the bucket array pairs don't contain indexes into the chains area of .gnu.hash section (located at .gnu.hash'VMA + 8 + 8 * nbuckets) but rather dynamic symbol indexes. So the chain location for CHAINOFF is: .gnu.hash'VMA + 8 + 8 * nbuckets + (CHAINOFF - symidx) * 4 The advantage of this is that the bias can be applied once in the ld.so initialization of a library and the inner loop doesn't need to subtract or add it anywhere. 3) added hooks, so that executable PLT slots on i386/x86_64 where the executable never takes address of those functions (and thus the SHN_UNDEF PLT symbols have st_value == 0) are not added to .gnu.hash chains 4) if there are no symbols in the .gnu.hash section at all, the linker sets nbuckets to 0. This will allow in the future to completely remove the executable from symbol search scope. Ok for trunk? Jakub [-- Attachment #2: binutils-hash-style.patch --] [-- Type: text/plain, Size: 38072 bytes --] 2006-07-06 Jakub Jelinek <jakub@redhat.com> include/ * bfdlink.h (struct bfd_link_info): Add emit_hash and emit_gnu_hash bitfields. include/elf/ * common.h (SHT_GNU_HASH, DT_GNU_HASH): Define. ld/ * scripttempl/elf.sc: Add .gnu.hash section. * emultempl/elf32.em (OPTION_HASH_STYLE): Define. (gld${EMULATION_NAME}_add_options): Register --hash-style option. (gld${EMULATION_NAME}_handle_option): Handle it. (gld${EMULATION_NAME}_list_options): Document it. * ldmain.c (main): Initialize emit_hash and emit_gnu_hash. * ld.texinfo: Document --hash-style option. bfd/ * elf.c (_bfd_elf_print_private_bfd_data): Handle DT_GNU_HASH. (bfd_section_from_shdr, elf_fake_sections, assign_section_numbers): Handle SHT_GNU_HASH. (special_sections_g): Include .gnu.hash section. (bfd_elf_gnu_hash): New function. * elf-bfd.h (bfd_elf_gnu_hash, _bfd_elf_hash_symbol): New prototypes. (struct elf_backend_data): Add elf_hash_symbol method. * elflink.c (_bfd_elf_link_create_dynamic_sections): Create .hash only if info->emit_hash, create .gnu.hash section if info->emit_gnu_hash. (struct collect_gnu_hash_codes): New type. (elf_collect_gnu_hash_codes, elf_renumber_gnu_hash_syms, _bfd_elf_hash_symbol): New functions. (compute_bucket_count): Don't compute HASHCODES array, instead add that and NSYMS as arguments. Use bed->s->sizeof_hash_entry instead of bed->s->arch_size / 8. Fix .hash size estimation. When not optimizing, use the number of hashed symbols rather than dynsymcount. (bfd_elf_size_dynamic_sections): Only add DT_HASH if info->emit_hash, and ADD DT_GNU_HASH if info->emit_gnu_hash. (bfd_elf_size_dynsym_hash_dynstr): Size .hash only if info->emit_hash, adjust compute_bucket_count caller. Create and populate .gnu.hash section if info->emit_gnu_hash. (elf_link_output_extsym): Only populate .hash section if finfo->hash_sec != NULL. (bfd_elf_final_link): Adjust assertion. Handle DT_GNU_HASH. * elfxx-target.h (elf_backend_hash_symbol): Define if not yet defined. (elfNN_bed): Add elf_backend_hash_symbol. * elf64-x86-64.c (elf64_x86_64_hash_symbol): New function. (elf_backend_hash_symbol): Define. * elf32-i386.c (elf_i386_hash_symbol): New function. (elf_backend_hash_symbol): Define. binutils/ * readelf.c (get_dynamic_type): Handle DT_GNU_HASH. (get_section_type_name): Handle SHT_GNU_HASH. (dynamic_info_DT_GNU_HASH): New variable. (process_dynamic_section): Handle DT_GNU_HASH. (process_symbol_table): Print also DT_GNU_HASH histogram. --- ld/scripttempl/elf.sc.jj 2006-01-01 01:02:16.000000000 +0100 +++ ld/scripttempl/elf.sc 2006-06-22 11:11:53.000000000 +0200 @@ -260,6 +260,7 @@ SECTIONS ${INITIAL_READONLY_SECTIONS} ${TEXT_DYNAMIC+${DYNAMIC}} .hash ${RELOCATING-0} : { *(.hash) } + .gnu.hash ${RELOCATING-0} : { *(.gnu.hash) } .dynsym ${RELOCATING-0} : { *(.dynsym) } .dynstr ${RELOCATING-0} : { *(.dynstr) } .gnu.version ${RELOCATING-0} : { *(.gnu.version) } --- ld/ldmain.c.jj 2006-06-01 15:50:33.000000000 +0200 +++ ld/ldmain.c 2006-06-22 11:21:11.000000000 +0200 @@ -304,6 +304,8 @@ main (int argc, char **argv) link_info.create_object_symbols_section = NULL; link_info.gc_sym_list = NULL; link_info.base_file = NULL; + link_info.emit_hash = TRUE; + link_info.emit_gnu_hash = FALSE; /* SVR4 linkers seem to set DT_INIT and DT_FINI based on magic _init and _fini symbols. We are compatible. */ link_info.init_function = "_init"; --- ld/ld.texinfo.jj 2006-06-15 14:31:06.000000000 +0200 +++ ld/ld.texinfo 2006-06-22 14:03:21.000000000 +0200 @@ -1883,6 +1883,14 @@ time it takes the linker to perform its increasing the linker's memory requirements. Similarly reducing this value can reduce the memory requirements at the expense of speed. +@kindex --hash-style=@var{style} +@item --hash-style=@var{style} +Set the type of linker's hash table(s). @var{style} can be either +@code{sysv} for classic ELF @code{.hash} section, @code{gnu} for +new style GNU @code{.gnu.hash} section or @code{both} for both +the classic ELF @code{.hash} and new style GNU @code{.gnu.hash} +hash tables. The default is @code{sysv}. + @kindex --reduce-memory-overheads @item --reduce-memory-overheads This option reduces memory requirements at ld runtime, at the expense of --- ld/emultempl/elf32.em.jj 2006-06-20 18:34:24.000000000 +0200 +++ ld/emultempl/elf32.em 2006-06-22 14:39:25.000000000 +0200 @@ -1719,6 +1719,7 @@ cat >>e${EMULATION_NAME}.c <<EOF #define OPTION_GROUP (OPTION_ENABLE_NEW_DTAGS + 1) #define OPTION_EH_FRAME_HDR (OPTION_GROUP + 1) #define OPTION_EXCLUDE_LIBS (OPTION_EH_FRAME_HDR + 1) +#define OPTION_HASH_STYLE (OPTION_EXCLUDE_LIBS + 1) static void gld${EMULATION_NAME}_add_options @@ -1735,6 +1736,7 @@ cat >>e${EMULATION_NAME}.c <<EOF {"enable-new-dtags", no_argument, NULL, OPTION_ENABLE_NEW_DTAGS}, {"eh-frame-hdr", no_argument, NULL, OPTION_EH_FRAME_HDR}, {"exclude-libs", required_argument, NULL, OPTION_EXCLUDE_LIBS}, + {"hash-style", required_argument, NULL, OPTION_HASH_STYLE}, {"Bgroup", no_argument, NULL, OPTION_GROUP}, EOF fi @@ -1791,6 +1793,22 @@ cat >>e${EMULATION_NAME}.c <<EOF add_excluded_libs (optarg); break; + case OPTION_HASH_STYLE: + link_info.emit_hash = FALSE; + link_info.emit_gnu_hash = FALSE; + if (strcmp (optarg, "sysv") == 0) + link_info.emit_hash = TRUE; + else if (strcmp (optarg, "gnu") == 0) + link_info.emit_gnu_hash = TRUE; + else if (strcmp (optarg, "both") == 0) + { + link_info.emit_hash = TRUE; + link_info.emit_gnu_hash = TRUE; + } + else + einfo (_("%P%F: invalid hash style \`%s'\n"), optarg); + break; + case 'z': if (strcmp (optarg, "initfirst") == 0) link_info.flags_1 |= (bfd_vma) DF_1_INITFIRST; @@ -1894,6 +1912,7 @@ cat >>e${EMULATION_NAME}.c <<EOF fprintf (file, _(" --disable-new-dtags\tDisable new dynamic tags\n")); fprintf (file, _(" --enable-new-dtags\tEnable new dynamic tags\n")); fprintf (file, _(" --eh-frame-hdr\tCreate .eh_frame_hdr section\n")); + fprintf (file, _(" --hash-stylle=STYLE\tSet hash style to sysv, gnu or both\n")); fprintf (file, _(" -z combreloc\t\tMerge dynamic relocs into one section and sort\n")); fprintf (file, _(" -z defs\t\tReport unresolved symbols in object files.\n")); fprintf (file, _(" -z execstack\t\tMark executable as requiring executable stack\n")); --- bfd/elf-bfd.h.jj 2006-06-20 18:34:24.000000000 +0200 +++ bfd/elf-bfd.h 2006-07-06 15:48:12.000000000 +0200 @@ -1038,6 +1038,9 @@ struct elf_backend_data bfd_boolean *, bfd_boolean *, bfd *, asection **); + /* Return TRUE if symbol should be hashed in the `.gnu.hash' section. */ + bfd_boolean (*elf_hash_symbol) (struct elf_link_hash_entry *); + /* Used to handle bad SHF_LINK_ORDER input. */ bfd_error_handler_type link_order_error_handler; @@ -1481,6 +1484,8 @@ extern bfd_vma _bfd_elf_section_offset extern unsigned long bfd_elf_hash (const char *); +extern unsigned long bfd_elf_gnu_hash + (const char *); extern bfd_reloc_status_type bfd_elf_generic_reloc (bfd *, arelent *, asymbol *, void *, asection *, bfd *, char **); @@ -1651,6 +1656,8 @@ extern bfd_boolean _bfd_elf_merge_symbol struct elf_link_hash_entry **, bfd_boolean *, bfd_boolean *, bfd_boolean *, bfd_boolean *); +extern bfd_boolean _bfd_elf_hash_symbol (struct elf_link_hash_entry *); + extern bfd_boolean _bfd_elf_add_default_symbol (bfd *, struct bfd_link_info *, struct elf_link_hash_entry *, const char *, Elf_Internal_Sym *, asection **, bfd_vma *, --- bfd/elf64-x86-64.c.jj 2006-06-20 11:57:19.000000000 +0200 +++ bfd/elf64-x86-64.c 2006-07-06 16:54:21.000000000 +0200 @@ -3615,6 +3615,19 @@ elf64_x86_64_additional_program_headers return count; } +/* Return TRUE if symbol should be hashed in the `.gnu.hash' section. */ + +static bfd_boolean +elf64_x86_64_hash_symbol (struct elf_link_hash_entry *h) +{ + if (h->plt.offset != (bfd_vma) -1 + && !h->def_regular + && !h->pointer_equality_needed) + return FALSE; + + return _bfd_elf_hash_symbol (h); +} + static const struct bfd_elf_special_section elf64_x86_64_special_sections[]= { @@ -3688,5 +3701,7 @@ static const struct bfd_elf_special_sect elf64_x86_64_special_sections #define elf_backend_additional_program_headers \ elf64_x86_64_additional_program_headers +#define elf_backend_hash_symbol \ + elf64_x86_64_hash_symbol #include "elf64-target.h" --- bfd/elf.c.jj 2006-06-20 18:34:24.000000000 +0200 +++ bfd/elf.c 2006-06-26 16:17:28.000000000 +0200 @@ -206,6 +206,21 @@ bfd_elf_hash (const char *namearg) return h & 0xffffffff; } +/* DT_GNU_HASH hash function. Do not change this function; you will + cause invalid hash tables to be generated. */ + +unsigned long +bfd_elf_gnu_hash (const char *namearg) +{ + const unsigned char *name = (const unsigned char *) namearg; + unsigned long h = 5381; + unsigned char ch; + + while ((ch = *name++) != '\0') + h = (h << 5) + h + ch; + return h & 0xffffffff; +} + bfd_boolean bfd_elf_mkobject (bfd *abfd) { @@ -1239,6 +1254,7 @@ _bfd_elf_print_private_bfd_data (bfd *ab case DT_AUXILIARY: name = "AUXILIARY"; stringp = TRUE; break; case DT_USED: name = "USED"; break; case DT_FILTER: name = "FILTER"; stringp = TRUE; break; + case DT_GNU_HASH: name = "GNU_HASH"; break; } fprintf (f, " %-11s ", name); @@ -1823,6 +1839,7 @@ bfd_section_from_shdr (bfd *abfd, unsign case SHT_FINI_ARRAY: /* .fini_array section. */ case SHT_PREINIT_ARRAY: /* .preinit_array section. */ case SHT_GNU_LIBLIST: /* .gnu.liblist section. */ + case SHT_GNU_HASH: /* .gnu.hash section. */ return _bfd_elf_make_section_from_shdr (abfd, hdr, name, shindex); case SHT_DYNAMIC: /* Dynamic linking information. */ @@ -2295,6 +2312,7 @@ static const struct bfd_elf_special_sect { ".gnu.version_r", 14, 0, SHT_GNU_verneed, 0 }, { ".gnu.liblist", 12, 0, SHT_GNU_LIBLIST, SHF_ALLOC }, { ".gnu.conflict", 13, 0, SHT_RELA, SHF_ALLOC }, + { ".gnu.hash", 9, 0, SHT_GNU_HASH, SHF_ALLOC }, { NULL, 0, 0, 0, 0 } }; @@ -2811,6 +2829,10 @@ elf_fake_sections (bfd *abfd, asection * case SHT_GROUP: this_hdr->sh_entsize = 4; break; + + case SHT_GNU_HASH: + this_hdr->sh_entsize = 4; + break; } if ((asect->flags & SEC_ALLOC) != 0) @@ -3256,6 +3278,7 @@ assign_section_numbers (bfd *abfd, struc break; case SHT_HASH: + case SHT_GNU_HASH: case SHT_GNU_versym: /* sh_link is the section header index of the symbol table this hash table or version table is for. */ --- bfd/elf32-i386.c.jj 2006-06-23 15:32:34.000000000 +0200 +++ bfd/elf32-i386.c 2006-07-06 16:56:24.000000000 +0200 @@ -3835,6 +3835,18 @@ elf_i386_plt_sym_val (bfd_vma i, const a return plt->vma + (i + 1) * PLT_ENTRY_SIZE; } +/* Return TRUE if symbol should be hashed in the `.gnu.hash' section. */ + +static bfd_boolean +elf_i386_hash_symbol (struct elf_link_hash_entry *h) +{ + if (h->plt.offset != (bfd_vma) -1 + && !h->def_regular + && !h->pointer_equality_needed) + return FALSE; + + return _bfd_elf_hash_symbol (h); +} #define TARGET_LITTLE_SYM bfd_elf32_i386_vec #define TARGET_LITTLE_NAME "elf32-i386" @@ -3875,6 +3887,7 @@ elf_i386_plt_sym_val (bfd_vma i, const a #define elf_backend_size_dynamic_sections elf_i386_size_dynamic_sections #define elf_backend_always_size_sections elf_i386_always_size_sections #define elf_backend_plt_sym_val elf_i386_plt_sym_val +#define elf_backend_hash_symbol elf_i386_hash_symbol #include "elf32-target.h" --- bfd/elflink.c.jj 2006-06-20 18:34:53.000000000 +0200 +++ bfd/elflink.c 2006-07-06 17:09:12.000000000 +0200 @@ -240,12 +240,24 @@ _bfd_elf_link_create_dynamic_sections (b if (!_bfd_elf_define_linkage_sym (abfd, info, s, "_DYNAMIC")) return FALSE; - s = bfd_make_section_with_flags (abfd, ".hash", - flags | SEC_READONLY); - if (s == NULL - || ! bfd_set_section_alignment (abfd, s, bed->s->log_file_align)) - return FALSE; - elf_section_data (s)->this_hdr.sh_entsize = bed->s->sizeof_hash_entry; + if (info->emit_hash) + { + s = bfd_make_section_with_flags (abfd, ".hash", flags | SEC_READONLY); + if (s == NULL + || ! bfd_set_section_alignment (abfd, s, bed->s->log_file_align)) + return FALSE; + elf_section_data (s)->this_hdr.sh_entsize = bed->s->sizeof_hash_entry; + } + + if (info->emit_gnu_hash) + { + s = bfd_make_section_with_flags (abfd, ".gnu.hash", + flags | SEC_READONLY); + if (s == NULL + || ! bfd_set_section_alignment (abfd, s, 3)) + return FALSE; + elf_section_data (s)->this_hdr.sh_entsize = 4; + } /* Let the backend create the rest of the sections. This lets the backend set the right flags. The backend will normally create @@ -4811,6 +4823,125 @@ elf_collect_hash_codes (struct elf_link_ return TRUE; } +struct collect_gnu_hash_codes +{ + bfd *output_bfd; + const struct elf_backend_data *bed; + unsigned long int nsyms; + unsigned long int *hashcodes; + unsigned long int *hashval; + unsigned long int *indx; + unsigned long int *counts; + unsigned long int *bitmask; + bfd_byte *contents; + long int min_dynindx; + unsigned long int bucketcount; + unsigned long int symindx; + long int local_indx; +}; + +/* This function will be called though elf_link_hash_traverse to store + all hash value of the exported symbols in an array. */ + +static bfd_boolean +elf_collect_gnu_hash_codes (struct elf_link_hash_entry *h, void *data) +{ + struct collect_gnu_hash_codes *s = data; + const char *name; + char *p; + unsigned long ha; + char *alc = NULL; + + if (h->root.type == bfd_link_hash_warning) + h = (struct elf_link_hash_entry *) h->root.u.i.link; + + /* Ignore indirect symbols. These are added by the versioning code. */ + if (h->dynindx == -1) + return TRUE; + + /* Ignore also local symbols and undefined symbols. */ + if (! (*s->bed->elf_hash_symbol) (h)) + return TRUE; + + name = h->root.root.string; + p = strchr (name, ELF_VER_CHR); + if (p != NULL) + { + alc = bfd_malloc (p - name + 1); + memcpy (alc, name, p - name); + alc[p - name] = '\0'; + name = alc; + } + + /* Compute the hash value. */ + ha = bfd_elf_gnu_hash (name); + + /* Store the found hash value in the array for compute_bucket_count, + and also for .dynsym reordering purposes. */ + s->hashcodes[s->nsyms] = ha; + s->hashval[h->dynindx] = ha; + ++s->nsyms; + if (s->min_dynindx < 0 || s->min_dynindx > h->dynindx) + s->min_dynindx = h->dynindx; + + if (alc != NULL) + free (alc); + + return TRUE; +} + +/* This function will be called though elf_link_hash_traverse to do + final dynaminc symbol renumbering. */ + +static bfd_boolean +elf_renumber_gnu_hash_syms (struct elf_link_hash_entry *h, void *data) +{ + struct collect_gnu_hash_codes *s = data; + unsigned long int bucket; + unsigned long int val; + + if (h->root.type == bfd_link_hash_warning) + h = (struct elf_link_hash_entry *) h->root.u.i.link; + + /* Ignore indirect symbols. */ + if (h->dynindx == -1) + return TRUE; + + /* Ignore also local symbols and undefined symbols. */ + if (! (*s->bed->elf_hash_symbol) (h)) + { + if (h->dynindx >= s->min_dynindx) + h->dynindx = s->local_indx++; + return TRUE; + } + + bucket = s->hashval[h->dynindx] % s->bucketcount; + val = (s->hashval[h->dynindx] >> 5) & 31; + s->bitmask[bucket] |= ((unsigned long int) 1) << val; + val = s->hashval[h->dynindx] & ~(unsigned long int) 1; + if (s->counts[bucket] == 1) + /* Last element terminates the chain. */ + val |= 1; + bfd_put_32 (s->output_bfd, val, + s->contents + (s->indx[bucket] - s->symindx) * 4); + --s->counts[bucket]; + h->dynindx = s->indx[bucket]++; + return TRUE; +} + +/* Return TRUE if symbol should be hashed in the `.gnu.hash' section. */ + +bfd_boolean +_bfd_elf_hash_symbol (struct elf_link_hash_entry *h) +{ + return !(h->forced_local + || h->root.type == bfd_link_hash_undefined + || h->root.type == bfd_link_hash_undefweak + || ((h->root.type == bfd_link_hash_defined + || h->root.type == bfd_link_hash_defweak) + && h->root.u.def.section->output_section == NULL)); +} + /* Array used to determine the number of hash table buckets to use based on the number of symbols there are. If there are fewer than 3 symbols we use 1 bucket, fewer than 17 symbols we use 3 buckets, @@ -4832,42 +4963,26 @@ static const size_t elf_buckets[] = Therefore the result is always a good payoff between few collisions (= short chain lengths) and table size. */ static size_t -compute_bucket_count (struct bfd_link_info *info) +compute_bucket_count (struct bfd_link_info *info, unsigned long int *hashcodes, + unsigned long int nsyms, int gnu_hash) { size_t dynsymcount = elf_hash_table (info)->dynsymcount; size_t best_size = 0; - unsigned long int *hashcodes; - unsigned long int *hashcodesp; unsigned long int i; bfd_size_type amt; - /* Compute the hash values for all exported symbols. At the same - time store the values in an array so that we could use them for - optimizations. */ - amt = dynsymcount; - amt *= sizeof (unsigned long int); - hashcodes = bfd_malloc (amt); - if (hashcodes == NULL) - return 0; - hashcodesp = hashcodes; - - /* Put all hash values in HASHCODES. */ - elf_link_hash_traverse (elf_hash_table (info), - elf_collect_hash_codes, &hashcodesp); - /* We have a problem here. The following code to optimize the table size requires an integer type with more the 32 bits. If BFD_HOST_U_64_BIT is set we know about such a type. */ #ifdef BFD_HOST_U_64_BIT if (info->optimize) { - unsigned long int nsyms = hashcodesp - hashcodes; size_t minsize; size_t maxsize; BFD_HOST_U_64_BIT best_chlen = ~((BFD_HOST_U_64_BIT) 0); - unsigned long int *counts ; bfd *dynobj = elf_hash_table (info)->dynobj; const struct elf_backend_data *bed = get_elf_backend_data (dynobj); + unsigned long int *counts; /* Possible optimization parameters: if we have NSYMS symbols we say that the hashing table must at least have NSYMS/4 and at most @@ -4876,6 +4991,13 @@ compute_bucket_count (struct bfd_link_in if (minsize == 0) minsize = 1; best_size = maxsize = nsyms * 2; + if (gnu_hash) + { + if (minsize < 2) + minsize = 2; + if ((best_size & 31) == 0) + ++best_size; + } /* Create array where we count the collisions in. We must use bfd_malloc since the size could be large. */ @@ -4883,10 +5005,7 @@ compute_bucket_count (struct bfd_link_in amt *= sizeof (unsigned long int); counts = bfd_malloc (amt); if (counts == NULL) - { - free (hashcodes); - return 0; - } + return 0; /* Compute the "optimal" size for the hash table. The criteria is a minimal chain length. The minor criteria is (of course) the size @@ -4898,6 +5017,9 @@ compute_bucket_count (struct bfd_link_in unsigned long int j; unsigned long int fact; + if (gnu_hash && (i & 31) == 0) + continue; + memset (counts, '\0', i * sizeof (unsigned long int)); /* Determine how often each hash bucket is used. */ @@ -4913,9 +5035,9 @@ compute_bucket_count (struct bfd_link_in # define BFD_TARGET_PAGESIZE (4096) # endif - /* We in any case need 2 + NSYMS entries for the size values and - the chains. */ - max = (2 + nsyms) * (bed->s->arch_size / 8); + /* We in any case need 2 + DYNSYMCOUNT entries for the size values + and the chains. */ + max = (2 + dynsymcount) * bed->s->sizeof_hash_entry; # if 1 /* Variant 1: optimize for short chains. We add the squares @@ -4925,7 +5047,7 @@ compute_bucket_count (struct bfd_link_in max += counts[j] * counts[j]; /* This adds penalties for the overall size of the table. */ - fact = i / (BFD_TARGET_PAGESIZE / (bed->s->arch_size / 8)) + 1; + fact = i / (BFD_TARGET_PAGESIZE / bed->s->sizeof_hash_entry) + 1; max *= fact * fact; # else /* Variant 2: Optimize a lot more for small table. Here we @@ -4936,7 +5058,7 @@ compute_bucket_count (struct bfd_link_in /* The overall size of the table is considered, but not as strong as in variant 1, where it is squared. */ - fact = i / (BFD_TARGET_PAGESIZE / (bed->s->arch_size / 8)) + 1; + fact = i / (BFD_TARGET_PAGESIZE / bed->s->sizeof_hash_entry) + 1; max *= fact; # endif @@ -4959,14 +5081,13 @@ compute_bucket_count (struct bfd_link_in for (i = 0; elf_buckets[i] != 0; i++) { best_size = elf_buckets[i]; - if (dynsymcount < elf_buckets[i + 1]) + if (nsyms < elf_buckets[i + 1]) break; } + if (gnu_hash && best_size < 2) + best_size = 2; } - /* Free the arrays we needed. */ - free (hashcodes); - return best_size; } @@ -5324,7 +5445,10 @@ bfd_elf_size_dynamic_sections (bfd *outp bfd_size_type strsize; strsize = _bfd_elf_strtab_size (elf_hash_table (info)->dynstr); - if (!_bfd_elf_add_dynamic_entry (info, DT_HASH, 0) + if ((info->emit_hash + && !_bfd_elf_add_dynamic_entry (info, DT_HASH, 0)) + || (info->emit_gnu_hash + && !_bfd_elf_add_dynamic_entry (info, DT_GNU_HASH, 0)) || !_bfd_elf_add_dynamic_entry (info, DT_STRTAB, 0) || !_bfd_elf_add_dynamic_entry (info, DT_SYMTAB, 0) || !_bfd_elf_add_dynamic_entry (info, DT_STRSZ, strsize) @@ -5726,8 +5850,6 @@ bfd_elf_size_dynsym_hash_dynstr (bfd *ou asection *s; bfd_size_type dynsymcount; unsigned long section_sym_count; - size_t bucketcount = 0; - size_t hash_entry_size; unsigned int dtagcount; dynobj = elf_hash_table (info)->dynobj; @@ -5778,23 +5900,178 @@ bfd_elf_size_dynsym_hash_dynstr (bfd *ou memset (s->contents, 0, section_sym_count * bed->s->sizeof_sym); } + elf_hash_table (info)->bucketcount = 0; + /* Compute the size of the hashing table. As a side effect this computes the hash values for all the names we export. */ - bucketcount = compute_bucket_count (info); + if (info->emit_hash) + { + unsigned long int *hashcodes; + unsigned long int *hashcodesp; + bfd_size_type amt; + unsigned long int nsyms; + size_t bucketcount; + size_t hash_entry_size; + + /* Compute the hash values for all exported symbols. At the same + time store the values in an array so that we could use them for + optimizations. */ + amt = dynsymcount * sizeof (unsigned long int); + hashcodes = bfd_malloc (amt); + if (hashcodes == NULL) + return FALSE; + hashcodesp = hashcodes; - s = bfd_get_section_by_name (dynobj, ".hash"); - BFD_ASSERT (s != NULL); - hash_entry_size = elf_section_data (s)->this_hdr.sh_entsize; - s->size = ((2 + bucketcount + dynsymcount) * hash_entry_size); - s->contents = bfd_zalloc (output_bfd, s->size); - if (s->contents == NULL) - return FALSE; + /* Put all hash values in HASHCODES. */ + elf_link_hash_traverse (elf_hash_table (info), + elf_collect_hash_codes, &hashcodesp); + + nsyms = hashcodesp - hashcodes; + bucketcount + = compute_bucket_count (info, hashcodes, nsyms, 0); + free (hashcodes); + + if (bucketcount == 0) + return FALSE; + + elf_hash_table (info)->bucketcount = bucketcount; + + s = bfd_get_section_by_name (dynobj, ".hash"); + BFD_ASSERT (s != NULL); + hash_entry_size = elf_section_data (s)->this_hdr.sh_entsize; + s->size = ((2 + bucketcount + dynsymcount) * hash_entry_size); + s->contents = bfd_zalloc (output_bfd, s->size); + if (s->contents == NULL) + return FALSE; + + bfd_put (8 * hash_entry_size, output_bfd, bucketcount, s->contents); + bfd_put (8 * hash_entry_size, output_bfd, dynsymcount, + s->contents + hash_entry_size); + } + + if (info->emit_gnu_hash) + { + size_t i, cnt; + unsigned char *contents; + struct collect_gnu_hash_codes cinfo; + bfd_size_type amt; + size_t bucketcount; + + memset (&cinfo, 0, sizeof (cinfo)); - bfd_put (8 * hash_entry_size, output_bfd, bucketcount, s->contents); - bfd_put (8 * hash_entry_size, output_bfd, dynsymcount, - s->contents + hash_entry_size); + /* Compute the hash values for all exported symbols. At the same + time store the values in an array so that we could use them for + optimizations. */ + amt = dynsymcount * 2 * sizeof (unsigned long int); + cinfo.hashcodes = bfd_malloc (amt); + if (cinfo.hashcodes == NULL) + return FALSE; + + cinfo.hashval = cinfo.hashcodes + dynsymcount; + cinfo.min_dynindx = -1; + cinfo.output_bfd = output_bfd; + cinfo.bed = bed; + + /* Put all hash values in HASHCODES. */ + elf_link_hash_traverse (elf_hash_table (info), + elf_collect_gnu_hash_codes, &cinfo); + + bucketcount + = compute_bucket_count (info, cinfo.hashcodes, cinfo.nsyms, 1); + + if (bucketcount == 0) + { + free (cinfo.hashcodes); + return FALSE; + } + + s = bfd_get_section_by_name (dynobj, ".gnu.hash"); + BFD_ASSERT (s != NULL); + + if (cinfo.nsyms == 0) + { + /* Empty .gnu.hash section is special, we set nbuckets to zero + to tell the dynamic linker it doesn't need to add this + object into search scope at all. */ + BFD_ASSERT (cinfo.min_dynindx == -1); + cinfo.min_dynindx = dynsymcount; + free (cinfo.hashcodes); + s->size = 2 * 4; + contents = bfd_zalloc (output_bfd, s->size); + if (contents == NULL) + return FALSE; + s->contents = contents; + bfd_put_32 (output_bfd, 0, contents); + bfd_put_32 (output_bfd, 0, contents + 4); + } + else + { + BFD_ASSERT (cinfo.min_dynindx != -1); + + amt = bucketcount * sizeof (unsigned long int) * 3; + cinfo.counts = bfd_malloc (amt); + if (cinfo.counts == NULL) + { + free (cinfo.hashcodes); + return FALSE; + } + + /* Determine how often each hash bucket is used. */ + memset (cinfo.counts, 0, + 2 * bucketcount * sizeof (cinfo.counts[0])); + for (i = 0; i < cinfo.nsyms; ++i) + ++cinfo.counts[cinfo.hashcodes[i] % bucketcount]; + + cinfo.bitmask = cinfo.counts + bucketcount; + cinfo.indx = cinfo.counts + 2 * bucketcount; + cinfo.symindx = dynsymcount - cinfo.nsyms; + for (i = 0, cnt = cinfo.symindx; i < bucketcount; ++i) + if (cinfo.counts[i] != 0) + { + cinfo.indx[i] = cnt; + cnt += cinfo.counts[i]; + } + BFD_ASSERT (cnt == dynsymcount); + cinfo.bucketcount = bucketcount; + cinfo.local_indx = cinfo.min_dynindx; + + s->size = (2 + 2 * bucketcount + cinfo.nsyms) * 4; + contents = bfd_zalloc (output_bfd, s->size); + if (contents == NULL) + { + free (cinfo.counts); + free (cinfo.hashcodes); + return FALSE; + } + + s->contents = contents; + bfd_put_32 (output_bfd, bucketcount, contents); + bfd_put_32 (output_bfd, cinfo.symindx, contents + 4); + contents += 4; + + for (i = 0; i < bucketcount; ++i) + { + contents += 8; + if (cinfo.counts[i] == 0) + bfd_put_32 (output_bfd, 0, contents); + else + bfd_put_32 (output_bfd, cinfo.indx[i], contents); + } - elf_hash_table (info)->bucketcount = bucketcount; + cinfo.contents = contents + 4; + + /* Renumber dynamic symbols, populate .gnu.hash section. */ + elf_link_hash_traverse (elf_hash_table (info), + elf_renumber_gnu_hash_syms, &cinfo); + + contents = s->contents + 8; + for (i = 0; i < bucketcount; ++i, contents += 8) + bfd_put_32 (output_bfd, cinfo.bitmask[i], contents); + + free (cinfo.counts); + free (cinfo.hashcodes); + } + } s = bfd_get_section_by_name (dynobj, ".dynstr"); BFD_ASSERT (s != NULL); @@ -6663,9 +6940,6 @@ elf_link_output_extsym (struct elf_link_ { size_t bucketcount; size_t bucket; - size_t hash_entry_size; - bfd_byte *bucketpos; - bfd_vma chain; bfd_byte *esym; sym.st_name = h->dynstr_index; @@ -6679,15 +6953,23 @@ elf_link_output_extsym (struct elf_link_ bucketcount = elf_hash_table (finfo->info)->bucketcount; bucket = h->u.elf_hash_value % bucketcount; - hash_entry_size - = elf_section_data (finfo->hash_sec)->this_hdr.sh_entsize; - bucketpos = ((bfd_byte *) finfo->hash_sec->contents - + (bucket + 2) * hash_entry_size); - chain = bfd_get (8 * hash_entry_size, finfo->output_bfd, bucketpos); - bfd_put (8 * hash_entry_size, finfo->output_bfd, h->dynindx, bucketpos); - bfd_put (8 * hash_entry_size, finfo->output_bfd, chain, - ((bfd_byte *) finfo->hash_sec->contents - + (bucketcount + 2 + h->dynindx) * hash_entry_size)); + + if (finfo->hash_sec != NULL) + { + size_t hash_entry_size; + bfd_byte *bucketpos; + bfd_vma chain; + + hash_entry_size + = elf_section_data (finfo->hash_sec)->this_hdr.sh_entsize; + bucketpos = ((bfd_byte *) finfo->hash_sec->contents + + (bucket + 2) * hash_entry_size); + chain = bfd_get (8 * hash_entry_size, finfo->output_bfd, bucketpos); + bfd_put (8 * hash_entry_size, finfo->output_bfd, h->dynindx, bucketpos); + bfd_put (8 * hash_entry_size, finfo->output_bfd, chain, + ((bfd_byte *) finfo->hash_sec->contents + + (bucketcount + 2 + h->dynindx) * hash_entry_size)); + } if (finfo->symver_sec != NULL && finfo->symver_sec->contents != NULL) { @@ -7861,7 +8143,7 @@ bfd_elf_final_link (bfd *abfd, struct bf { finfo.dynsym_sec = bfd_get_section_by_name (dynobj, ".dynsym"); finfo.hash_sec = bfd_get_section_by_name (dynobj, ".hash"); - BFD_ASSERT (finfo.dynsym_sec != NULL && finfo.hash_sec != NULL); + BFD_ASSERT (finfo.dynsym_sec != NULL); finfo.symver_sec = bfd_get_section_by_name (dynobj, ".gnu.version"); /* Note that it is OK if symver_sec is NULL. */ } @@ -8621,6 +8903,9 @@ bfd_elf_final_link (bfd *abfd, struct bf case DT_HASH: name = ".hash"; goto get_vma; + case DT_GNU_HASH: + name = ".gnu.hash"; + goto get_vma; case DT_STRTAB: name = ".dynstr"; goto get_vma; --- bfd/elfxx-target.h.jj 2006-06-20 18:34:24.000000000 +0200 +++ bfd/elfxx-target.h 2006-07-06 15:38:39.000000000 +0200 @@ -563,6 +563,10 @@ #define elf_backend_merge_symbol NULL #endif +#ifndef elf_backend_hash_symbol +#define elf_backend_hash_symbol _bfd_elf_hash_symbol +#endif + extern const struct elf_size_info _bfd_elfNN_size_info; #ifndef INCLUDED_TARGET_FILE @@ -643,6 +647,7 @@ static struct elf_backend_data elfNN_bed elf_backend_common_section_index, elf_backend_common_section, elf_backend_merge_symbol, + elf_backend_hash_symbol, elf_backend_link_order_error_handler, elf_backend_relplt_name, ELF_MACHINE_ALT1, --- include/elf/common.h.jj 2006-02-17 15:36:26.000000000 +0100 +++ include/elf/common.h 2006-06-22 10:43:21.000000000 +0200 @@ -338,6 +338,7 @@ #define SHT_LOOS 0x60000000 /* First of OS specific semantics */ #define SHT_HIOS 0x6fffffff /* Last of OS specific semantics */ +#define SHT_GNU_HASH 0x6ffffff6 /* GNU style symbol hash table */ #define SHT_GNU_LIBLIST 0x6ffffff7 /* List of prelink dependencies */ /* The next three section types are defined by Solaris, and are named @@ -577,6 +578,7 @@ #define DT_VALRNGHI 0x6ffffdff #define DT_ADDRRNGLO 0x6ffffe00 +#define DT_GNU_HASH 0x6ffffef5 #define DT_TLSDESC_PLT 0x6ffffef6 #define DT_TLSDESC_GOT 0x6ffffef7 #define DT_GNU_CONFLICT 0x6ffffef8 --- include/bfdlink.h.jj 2006-04-07 17:17:29.000000000 +0200 +++ include/bfdlink.h 2006-06-22 11:11:20.000000000 +0200 @@ -324,6 +324,12 @@ struct bfd_link_info /* TRUE if unreferenced sections should be removed. */ unsigned int gc_sections: 1; + /* TRUE if .hash section should be created. */ + unsigned int emit_hash: 1; + + /* TRUE if .gnu.hash section should be created. */ + unsigned int emit_gnu_hash: 1; + /* What to do with unresolved symbols in an object file. When producing executables the default is GENERATE_ERROR. When producing shared libraries the default is IGNORE. The --- binutils/readelf.c.jj 2006-05-30 16:13:54.000000000 +0200 +++ binutils/readelf.c 2006-07-06 17:17:20.000000000 +0200 @@ -135,6 +135,7 @@ static unsigned long dynamic_syminfo_off static unsigned int dynamic_syminfo_nent; static char program_interpreter[64]; static bfd_vma dynamic_info[DT_JMPREL + 1]; +static bfd_vma dynamic_info_DT_GNU_HASH; static bfd_vma version_info[16]; static Elf_Internal_Ehdr elf_header; static Elf_Internal_Shdr *section_headers; @@ -1501,6 +1502,7 @@ get_dynamic_type (unsigned long type) case DT_GNU_CONFLICTSZ: return "GNU_CONFLICTSZ"; case DT_GNU_LIBLIST: return "GNU_LIBLIST"; case DT_GNU_LIBLISTSZ: return "GNU_LIBLISTSZ"; + case DT_GNU_HASH: return "GNU_HASH"; default: if ((type >= DT_LOPROC) && (type <= DT_HIPROC)) @@ -2571,6 +2573,7 @@ get_section_type_name (unsigned int sh_t case SHT_INIT_ARRAY: return "INIT_ARRAY"; case SHT_FINI_ARRAY: return "FINI_ARRAY"; case SHT_PREINIT_ARRAY: return "PREINIT_ARRAY"; + case SHT_GNU_HASH: return "GNU_HASH"; case SHT_GROUP: return "GROUP"; case SHT_SYMTAB_SHNDX: return "SYMTAB SECTION INDICIES"; case SHT_GNU_verdef: return "VERDEF"; @@ -6228,6 +6231,15 @@ process_dynamic_section (FILE *file) } break; + case DT_GNU_HASH: + dynamic_info_DT_GNU_HASH = entry->d_un.d_val; + if (do_dynamic) + { + print_vma (entry->d_un.d_val, PREFIX_HEX); + putchar ('\n'); + } + break; + default: if ((entry->d_tag >= DT_VERSYM) && (entry->d_tag <= DT_VERNEEDNUM)) version_info[DT_VERSIONTAGIDX (entry->d_tag)] = @@ -6903,6 +6915,9 @@ process_symbol_table (FILE *file) bfd_vma nchains = 0; bfd_vma *buckets = NULL; bfd_vma *chains = NULL; + bfd_vma ngnubuckets = 0; + bfd_vma *gnubuckets = NULL; + bfd_vma *gnuchains = NULL; if (! do_syms && !do_histogram) return 1; @@ -7282,6 +7297,157 @@ process_symbol_table (FILE *file) free (chains); } + if (do_histogram && dynamic_info_DT_GNU_HASH) + { + unsigned char nb[8]; + bfd_vma i, maxchain = 0xffffffff, symidx; + unsigned long *lengths; + unsigned long *counts; + unsigned long hn; + unsigned long maxlength = 0; + unsigned long nzero_counts = 0; + unsigned long nsyms = 0; + + if (fseek (file, + (archive_file_offset + + offset_from_vma (file, dynamic_info_DT_GNU_HASH, + sizeof nb)), + SEEK_SET)) + { + error (_("Unable to seek to start of dynamic information")); + return 0; + } + + if (fread (nb, 8, 1, file) != 1) + { + error (_("Failed to read in number of buckets\n")); + return 0; + } + + ngnubuckets = byte_get (nb, 4); + symidx = byte_get (nb + 4, 4); + + if (ngnubuckets == 0) + return 0; + + gnubuckets = get_dynamic_data (file, 2 * ngnubuckets, 4); + + if (gnubuckets == NULL) + return 0; + + for (i = 0; i < ngnubuckets; i++) + if (gnubuckets[2 * i] != 0) + { + if (gnubuckets[2 * i + 1] < symidx) + return 0; + + if (maxchain == 0xffffffff || gnubuckets[2 * i + 1] > maxchain) + maxchain = gnubuckets[2 * i + 1]; + } + + if (maxchain == 0xffffffff) + return 0; + + maxchain -= symidx; + + if (fseek (file, + (archive_file_offset + + offset_from_vma (file, + dynamic_info_DT_GNU_HASH + + 4 * (2 + 2 * ngnubuckets + maxchain), + 4)), + SEEK_SET)) + { + error (_("Unable to seek to start of dynamic information")); + return 0; + } + + do + { + if (fread (nb, 4, 1, file) != 1) + { + error (_("Failed to determine last chain length\n")); + return 0; + } + + if (maxchain + 1 == 0) + return 0; + + ++maxchain; + } + while ((byte_get (nb, 4) & 1) == 0); + + if (fseek (file, + (archive_file_offset + + offset_from_vma (file, + dynamic_info_DT_GNU_HASH + + 4 * (2 + 2 * ngnubuckets), 4)), + SEEK_SET)) + { + error (_("Unable to seek to start of dynamic information")); + return 0; + } + + gnuchains = get_dynamic_data (file, maxchain, 4); + + if (gnuchains == NULL) + return 0; + + lengths = calloc (ngnubuckets, sizeof (*lengths)); + if (lengths == NULL) + { + error (_("Out of memory")); + return 0; + } + + printf (_("\nHistogram for `.gnu.hash' bucket list length (total of %lu buckets):\n"), + (unsigned long) ngnubuckets); + printf (_(" Length Number %% of total Coverage\n")); + + for (hn = 0; hn < ngnubuckets; ++hn) + if (gnubuckets[2 * hn] != 0) + { + bfd_vma off, length = 1; + + for (off = gnubuckets[2 * hn + 1] - symidx; + (gnuchains[off] & 1) == 0; ++off) + ++length; + lengths[hn] = length; + if (length > maxlength) + maxlength = length; + nsyms += length; + } + + counts = calloc (maxlength + 1, sizeof (*counts)); + if (counts == NULL) + { + error (_("Out of memory")); + return 0; + } + + for (hn = 0; hn < ngnubuckets; ++hn) + ++counts[lengths[hn]]; + + if (ngnubuckets > 0) + { + unsigned long j; + printf (" 0 %-10lu (%5.1f%%)\n", + counts[0], (counts[0] * 100.0) / ngnubuckets); + for (j = 1; j <= maxlength; ++j) + { + nzero_counts += counts[j] * j; + printf ("%7lu %-10lu (%5.1f%%) %5.1f%%\n", + j, counts[j], (counts[j] * 100.0) / ngnubuckets, + (nzero_counts * 100.0) / nsyms); + } + } + + free (counts); + free (lengths); + free (gnubuckets); + free (gnuchains); + } + return 1; } [-- Attachment #3: glibc-gnu-hash.patch --] [-- Type: text/plain, Size: 19848 bytes --] 2006-07-06 Ulrich Drepper <drepper@redhat.com> * elf/dl-lookup.c (dl_new_hash): New functions. (_dl_lookup_symbol_x): Rename hash to old_hash and don't compute value here. Compute new-style hash value. Pass new hash value and reference to variable with the old value to do_lookup_x. (_dl_setup_hash): If DT_GNU_HASH is defined, use it and not old-style hash table. (_dl_debug_bindings): Pass new hash value and reference to variable with the old value to do_lookup_x. * elf/do-lookup.h (do_lookup_x): Accept additional parameter with new-style hash value and change old-style hash value parameter to be a reference. Reoganize functions to determine whether new-style hash table is available. Only fall back on old-style table. If old-style hash value is needed, compute it here. * elf/dynamic-link.h (elf_get_dynamic_info): Relocate DT_GNU_HASH entry. * elf/elf.h: Define SHT_GNU_HASH, DT_GNU_HASH, DT_TLSDEC_PLT, DT_TLSDEC_GOT. Adjust DT_ADDRNUM. * include/link.h (struct link_map): Add l_gnu_buckets and l_gnu_chain_zero. * Makeconfig: If linker supports --hash-style option add it to all linker command lines to build DSOs. * config.make.in: Define have-hash-style. * configure.in: Test whether linker supports --hash-style option. --- libc/Makeconfig.~1.318.~ 2006-05-15 11:21:55.000000000 -0700 +++ libc/Makeconfig 2006-07-06 10:13:00.000000000 -0700 @@ -413,11 +413,20 @@ LDFLAGS.so += $(relro-LDFLAGS) LDFLAGS-rtld += $(relro-LDFLAGS) endif +ifeq (yes,$(have-hash-style)) +# For the time being we unconditionally use 'both'. At some time we +# should declare statically linked code as 'out of luck' and compile +# with --hash-style=gnu only. +hashstyle-LDFLAGS = -Wl,--hash-style=both +LDFLAGS.so += $(hashstyle-LDFLAGS) +LDFLAGS-rtld += $(hashstyle-LDFLAGS) +endif + # Command for linking programs with the C library. ifndef +link +link = $(CC) -nostdlib -nostartfiles -o $@ \ $(sysdep-LDFLAGS) $(config-LDFLAGS) $(LDFLAGS) $(LDFLAGS-$(@F)) \ - $(combreloc-LDFLAGS) $(relro-LDFLAGS) \ + $(combreloc-LDFLAGS) $(relro-LDFLAGS) $(hashstyle-LDFLAGS) \ $(addprefix $(csu-objpfx),$(start-installed-name)) \ $(+preinit) $(+prector) \ $(filter-out $(addprefix $(csu-objpfx),start.o \ --- libc/config.make.in.~1.118.~ 2006-04-26 08:17:41.000000000 -0700 +++ libc/config.make.in 2006-06-27 05:38:40.000000000 -0700 @@ -65,6 +65,7 @@ have-libcap = @have_libcap@ have-cc-with-libunwind = @libc_cv_cc_with_libunwind@ fno-unit-at-a-time = @fno_unit_at_a_time@ bind-now = @bindnow@ +have-hash-style = @libc_cv_hashstyle@ static-libgcc = @libc_cv_gcc_static_libgcc@ --- libc/configure.in.~1.460.~ 2006-04-26 08:19:22.000000000 -0700 +++ libc/configure.in 2006-06-26 13:47:01.000000000 -0700 @@ -1589,6 +1589,22 @@ EOF rm -f conftest*]) AC_SUBST(libc_cv_fpie) + + AC_CACHE_CHECK(for --hash-style option, + libc_cv_hashstyle, [dnl + cat > conftest.c <<EOF +int _start (void) { return 42; } +EOF + if AC_TRY_COMMAND([${CC-cc} $CFLAGS $CPPFLAGS $LDFLAGS + -fPIC -shared -o conftest.so conftest.c + -Wl,--hash-style=both -nostdlib 1>&AS_MESSAGE_LOG_FD]) + then + libc_cv_hashstyle=yes + else + libc_cv_hashstyle=no + fi + rm -f conftest*]) + AC_SUBST(libc_cv_hashstyle) fi AC_CACHE_CHECK(for -fno-toplevel-reorder, libc_cv_fno_toplevel_reorder, [dnl --- libc/elf/dl-lookup.c 21 Dec 2005 22:16:20 -0000 1.121 +++ libc/elf/dl-lookup.c 6 Jul 2006 17:40:15 -0000 @@ -1,5 +1,5 @@ /* Look up a symbol in the loaded objects. - Copyright (C) 1995-2002, 2003, 2004, 2005 Free Software Foundation, Inc. + Copyright (C) 1995-2005, 2006 Free Software Foundation, Inc. This file is part of the GNU C Library. The GNU C Library is free software; you can redistribute it and/or @@ -72,6 +72,16 @@ #include "do-lookup.h" +static uint_fast32_t +dl_new_hash (const char *s) +{ + uint_fast32_t h = 5381; + for (unsigned char c = *s; c != '\0'; c = *++s) + h = h * 33 + c; + return h & 0xffffffff; +} + + /* Add extra dependency on MAP to UNDEF_MAP. */ static int internal_function @@ -206,7 +216,8 @@ const struct r_found_version *version, int type_class, int flags, struct link_map *skip_map) { - const unsigned long int hash = _dl_elf_hash (undef_name); + const uint_fast32_t new_hash = dl_new_hash (undef_name); + unsigned long int old_hash = 0xffffffff; struct sym_val current_value = { NULL, NULL }; struct r_scope_elem **scope = symbol_scope; @@ -229,8 +240,9 @@ /* Search the relevant loaded objects for a definition. */ for (size_t start = i; *scope != NULL; start = 0, ++scope) { - int res = do_lookup_x (undef_name, hash, *ref, ¤t_value, *scope, - start, version, flags, skip_map, type_class); + int res = do_lookup_x (undef_name, new_hash, &old_hash, *ref, + ¤t_value, *scope, start, version, flags, + skip_map, type_class); if (res > 0) break; @@ -301,9 +313,9 @@ struct sym_val protected_value = { NULL, NULL }; for (scope = symbol_scope; *scope != NULL; i = 0, ++scope) - if (do_lookup_x (undef_name, hash, *ref, &protected_value, - *scope, i, version, flags, skip_map, - ELF_RTYPE_CLASS_PLT) != 0) + if (do_lookup_x (undef_name, new_hash, &old_hash, *ref, + &protected_value, *scope, i, version, flags, + skip_map, ELF_RTYPE_CLASS_PLT) != 0) break; if (protected_value.s != NULL && protected_value.m != undef_map) @@ -352,6 +364,22 @@ Elf_Symndx *hash; Elf_Symndx nchain; + if (__builtin_expect (map->l_info[DT_ADDRTAGIDX (DT_GNU_HASH) + DT_NUM + + DT_THISPROCNUM + DT_VERSIONTAGNUM + + DT_EXTRANUM + DT_VALNUM] != NULL, 1)) + { + Elf32_Word *hash32 + = (void *) D_PTR (map, l_info[DT_ADDRTAGIDX (DT_GNU_HASH) + DT_NUM + + DT_THISPROCNUM + DT_VERSIONTAGNUM + + DT_EXTRANUM + DT_VALNUM]); + map->l_nbuckets = *hash32++; + Elf32_Word symbias = *hash32++; + map->l_gnu_buckets = hash32; + hash32 += 2 * map->l_nbuckets; + map->l_gnu_chain_zero = hash32 - symbias; + return; + } + if (!map->l_info[DT_HASH]) return; hash = (void *) D_PTR (map, l_info[DT_HASH]); @@ -399,9 +427,10 @@ || GLRO(dl_trace_prelink_map) == GL(dl_ns)[LM_ID_BASE]._ns_loaded) && undef_map != GL(dl_ns)[LM_ID_BASE]._ns_loaded) { - const unsigned long int hash = _dl_elf_hash (undef_name); + const uint_fast32_t new_hash = dl_new_hash (undef_name); + unsigned long int old_hash = 0xffffffff; - do_lookup_x (undef_name, hash, *ref, &val, + do_lookup_x (undef_name, new_hash, &old_hash, *ref, &val, undef_map->l_local_scope[0], 0, version, 0, NULL, type_class); --- libc/elf/do-lookup.h.~1.33.~ 2006-02-26 12:49:30.000000000 -0800 +++ libc/elf/do-lookup.h 2006-07-06 10:39:48.000000000 -0700 @@ -17,32 +17,30 @@ Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. */ + /* Inner part of the lookup functions. We return a value > 0 if we found the symbol, the value 0 if nothing is found and < 0 if something bad happened. */ static int __attribute_noinline__ -do_lookup_x (const char *undef_name, unsigned long int hash, - const ElfW(Sym) *ref, struct sym_val *result, - struct r_scope_elem *scope, size_t i, +do_lookup_x (const char *undef_name, uint_fast32_t new_hash, + unsigned long int *old_hash, const ElfW(Sym) *ref, + struct sym_val *result, struct r_scope_elem *scope, size_t i, const struct r_found_version *const version, int flags, struct link_map *skip, int type_class) { struct link_map **list = scope->r_list; size_t n = scope->r_nlist; - struct link_map *map; + Elf32_Word new_hash_bit = 1 << ((new_hash >> 5) & 31); do { - const ElfW(Sym) *symtab; - const char *strtab; - const ElfW(Half) *verstab; + /* These variables are used in the nested function. */ Elf_Symndx symidx; - const ElfW(Sym) *sym; int num_versions = 0; const ElfW(Sym) *versioned_sym = NULL; - map = list[i]->l_real; + struct link_map *map = list[i]->l_real; /* Here come the extra test needed for `_dl_lookup_symbol_skip'. */ if (map == skip) @@ -63,109 +61,145 @@ do_lookup_x (const char *undef_name, uns map->l_name[0] ? map->l_name : rtld_progname, map->l_ns); - symtab = (const void *) D_PTR (map, l_info[DT_SYMTAB]); - strtab = (const void *) D_PTR (map, l_info[DT_STRTAB]); - verstab = map->l_versyms; + /* If the hash table is empty there is nothing to do here. */ + if (map->l_nbuckets == 0) + continue; - /* Search the appropriate hash bucket in this object's symbol table - for a definition for the same symbol name. */ - for (symidx = map->l_buckets[hash % map->l_nbuckets]; - symidx != STN_UNDEF; - symidx = map->l_chain[symidx]) - { - sym = &symtab[symidx]; + /* The tables for this map. */ + const ElfW(Sym) *symtab = (const void *) D_PTR (map, l_info[DT_SYMTAB]); + const char *strtab = (const void *) D_PTR (map, l_info[DT_STRTAB]); + const ElfW(Half) *verstab = map->l_versyms; - assert (ELF_RTYPE_CLASS_PLT == 1); - if ((sym->st_value == 0 /* No value. */ -#ifdef USE_TLS - && ELFW(ST_TYPE) (sym->st_info) != STT_TLS -#endif - ) - || (type_class & (sym->st_shndx == SHN_UNDEF))) - continue; - if (ELFW(ST_TYPE) (sym->st_info) > STT_FUNC -#ifdef USE_TLS - && ELFW(ST_TYPE) (sym->st_info) != STT_TLS -#endif - ) - /* Ignore all but STT_NOTYPE, STT_OBJECT and STT_FUNC - entries (and STT_TLS if TLS is supported) since these - are no code/data definitions. */ - continue; + /* Nested routine to check whether the symbol matches. */ + const ElfW(Sym) * + __attribute_noinline__ + check_match (const ElfW(Sym) *sym) + { + assert (ELF_RTYPE_CLASS_PLT == 1); + if (__builtin_expect ((sym->st_value == 0 /* No value. */ + && ELFW(ST_TYPE) (sym->st_info) != STT_TLS) + || (type_class & (sym->st_shndx == SHN_UNDEF)), + 0)) + return NULL; - if (sym != ref && strcmp (strtab + sym->st_name, undef_name)) - /* Not the symbol we are looking for. */ - continue; + if (__builtin_expect (ELFW(ST_TYPE) (sym->st_info) > STT_FUNC + && ELFW(ST_TYPE) (sym->st_info) != STT_TLS, 0)) + /* Ignore all but STT_NOTYPE, STT_OBJECT and STT_FUNC + entries (and STT_TLS if TLS is supported) since these + are no code/data definitions. */ + return NULL; - if (version != NULL) - { - if (__builtin_expect (verstab == NULL, 0)) - { - /* We need a versioned symbol but haven't found any. If - this is the object which is referenced in the verneed - entry it is a bug in the library since a symbol must - not simply disappear. + if (sym != ref && strcmp (strtab + sym->st_name, undef_name)) + /* Not the symbol we are looking for. */ + return NULL; - It would also be a bug in the object since it means that - the list of required versions is incomplete and so the - tests in dl-version.c haven't found a problem.*/ - assert (version->filename == NULL - || ! _dl_name_match_p (version->filename, map)); + if (version != NULL) + { + if (__builtin_expect (verstab == NULL, 0)) + { + /* We need a versioned symbol but haven't found any. If + this is the object which is referenced in the verneed + entry it is a bug in the library since a symbol must + not simply disappear. - /* Otherwise we accept the symbol. */ - } - else - { - /* We can match the version information or use the - default one if it is not hidden. */ - ElfW(Half) ndx = verstab[symidx] & 0x7fff; - if ((map->l_versions[ndx].hash != version->hash - || strcmp (map->l_versions[ndx].name, version->name)) - && (version->hidden || map->l_versions[ndx].hash - || (verstab[symidx] & 0x8000))) - /* It's not the version we want. */ - continue; - } - } - else - { - /* No specific version is selected. There are two ways we - can got here: + It would also be a bug in the object since it means that + the list of required versions is incomplete and so the + tests in dl-version.c haven't found a problem.*/ + assert (version->filename == NULL + || ! _dl_name_match_p (version->filename, map)); - - a binary which does not include versioning information - is loaded + /* Otherwise we accept the symbol. */ + } + else + { + /* We can match the version information or use the + default one if it is not hidden. */ + ElfW(Half) ndx = verstab[symidx] & 0x7fff; + if ((map->l_versions[ndx].hash != version->hash + || strcmp (map->l_versions[ndx].name, version->name)) + && (version->hidden || map->l_versions[ndx].hash + || (verstab[symidx] & 0x8000))) + /* It's not the version we want. */ + return NULL; + } + } + else + { + /* No specific version is selected. There are two ways we + can got here: - - dlsym() instead of dlvsym() is used to get a symbol which - might exist in more than one form + - a binary which does not include versioning information + is loaded - If the library does not provide symbol version - information there is no problem at at: we simply use the - symbol if it is defined. + - dlsym() instead of dlvsym() is used to get a symbol which + might exist in more than one form - These two lookups need to be handled differently if the - library defines versions. In the case of the old - unversioned application the oldest (default) version - should be used. In case of a dlsym() call the latest and - public interface should be returned. */ - if (verstab != NULL) - { - if ((verstab[symidx] & 0x7fff) - >= ((flags & DL_LOOKUP_RETURN_NEWEST) ? 2 : 3)) - { - /* Don't accept hidden symbols. */ - if ((verstab[symidx] & 0x8000) == 0 - && num_versions++ == 0) - /* No version so far. */ - versioned_sym = sym; + If the library does not provide symbol version information + there is no problem at at: we simply use the symbol if it + is defined. - continue; - } - } + These two lookups need to be handled differently if the + library defines versions. In the case of the old + unversioned application the oldest (default) version + should be used. In case of a dlsym() call the latest and + public interface should be returned. */ + if (verstab != NULL) + { + if ((verstab[symidx] & 0x7fff) + >= ((flags & DL_LOOKUP_RETURN_NEWEST) ? 2 : 3)) + { + /* Don't accept hidden symbols. */ + if ((verstab[symidx] & 0x8000) == 0 + && num_versions++ == 0) + /* No version so far. */ + versioned_sym = sym; + + return NULL; + } + } + } + + /* There cannot be another entry for this symbol so stop here. */ + return sym; + } + + const ElfW(Sym) *sym; + if (__builtin_expect (map->l_gnu_buckets != NULL, 1)) + { + const Elf32_Word *buckets + = &map->l_gnu_buckets[2 * (new_hash % map->l_nbuckets)]; + if (buckets[0] & new_hash_bit) + { + const Elf32_Word *hasharr = &map->l_gnu_chain_zero[buckets[1]]; + + do + if ((*hasharr & ~1u) == (new_hash & ~1u)) + { + symidx = hasharr - map->l_gnu_chain_zero; + sym = check_match (&symtab[symidx]); + if (sym != NULL) + goto found_it; + } + while ((*hasharr++ & 1u) == 0); } + } + else + { + if (*old_hash == 0xffffffff) + *old_hash = _dl_elf_hash (undef_name); - /* There cannot be another entry for this symbol so stop here. */ - goto found_it; + /* Use the old SysV-style hash table. Search the appropriate + hash bucket in this object's symbol table for a definition + for the same symbol name. */ + for (symidx = map->l_buckets[*old_hash % map->l_nbuckets]; + symidx != STN_UNDEF; + symidx = map->l_chain[symidx]) + { + sym = check_match (&symtab[symidx]); + if (sym != NULL) + goto found_it; + } } /* If we have seen exactly one versioned symbol while we are @@ -213,7 +247,3 @@ do_lookup_x (const char *undef_name, uns /* We have not found anything until now. */ return 0; } - -#undef FCT -#undef ARG -#undef VERSIONED --- libc/elf/dynamic-link.h 15 Mar 2005 22:57:25 -0000 1.54 +++ libc/elf/dynamic-link.h 6 Jul 2006 17:40:59 -0000 @@ -1,5 +1,5 @@ /* Inline functions for dynamic linking. - Copyright (C) 1995-2002, 2003, 2004, 2005 Free Software Foundation, Inc. + Copyright (C) 1995-2005, 2006 Free Software Foundation, Inc. This file is part of the GNU C Library. The GNU C Library is free software; you can redistribute it and/or @@ -143,6 +143,8 @@ # endif ADJUST_DYN_INFO (DT_JMPREL); ADJUST_DYN_INFO (VERSYMIDX (DT_VERSYM)); + ADJUST_DYN_INFO (DT_ADDRTAGIDX (DT_GNU_HASH) + DT_NUM + DT_THISPROCNUM + + DT_VERSIONTAGNUM + DT_EXTRANUM + DT_VALNUM); # undef ADJUST_DYN_INFO assert (cnt <= DL_RO_DYN_TEMP_CNT); } --- libc/elf/elf.h 25 Feb 2006 01:57:44 -0000 1.154 +++ libc/elf/elf.h 6 Jul 2006 17:42:24 -0000 @@ -329,7 +329,8 @@ #define SHT_GROUP 17 /* Section group */ #define SHT_SYMTAB_SHNDX 18 /* Extended section indeces */ #define SHT_NUM 19 /* Number of defined types. */ -#define SHT_LOOS 0x60000000 /* Start OS-specific */ +#define SHT_LOOS 0x60000000 /* Start OS-specific. */ +#define SHT_GNU_HASH 0x6ffffff6 /* GNU-style hash table. */ #define SHT_GNU_LIBLIST 0x6ffffff7 /* Prelink library list */ #define SHT_CHECKSUM 0x6ffffff8 /* Checksum for DSO content. */ #define SHT_LOSUNW 0x6ffffffa /* Sun-specific low bound. */ @@ -699,6 +700,9 @@ If any adjustment is made to the ELF object after it has been built these entries will need to be adjusted. */ #define DT_ADDRRNGLO 0x6ffffe00 +#define DT_GNU_HASH 0x6ffffef5 /* GNU-style hash table. */ +#define DT_TLSDESC_PLT 0x6ffffef6 +#define DT_TLSDESC_GOT 0x6ffffef7 #define DT_GNU_CONFLICT 0x6ffffef8 /* Start of conflict section */ #define DT_GNU_LIBLIST 0x6ffffef9 /* Library list */ #define DT_CONFIG 0x6ffffefa /* Configuration information. */ @@ -709,7 +713,7 @@ #define DT_SYMINFO 0x6ffffeff /* Syminfo table. */ #define DT_ADDRRNGHI 0x6ffffeff #define DT_ADDRTAGIDX(tag) (DT_ADDRRNGHI - (tag)) /* Reverse order! */ -#define DT_ADDRNUM 10 +#define DT_ADDRNUM 11 /* The versioning entry types. The next are defined as part of the GNU extension. */ --- libc/include/link.h 1 Mar 2006 06:18:30 -0000 1.38 +++ libc/include/link.h 6 Jul 2006 17:43:09 -0000 @@ -124,7 +124,7 @@ const ElfW(Phdr) *l_phdr; /* Pointer to program header table in core. */ ElfW(Addr) l_entry; /* Entry point location. */ ElfW(Half) l_phnum; /* Number of program header entries. */ - ElfW(Half) l_ldnum; /* Number of dynamic segment entries. */ + ElfW(Half) l_ldnum; /* Number of dynamic segment entries. */ /* Array of DT_NEEDED dependencies and their dependencies, in dependency order for symbol lookup (with and without @@ -141,7 +141,13 @@ /* Symbol hash table. */ Elf_Symndx l_nbuckets; - const Elf_Symndx *l_buckets, *l_chain; + const Elf32_Word *l_gnu_buckets; + union + { + const Elf32_Word *l_gnu_chain_zero; + const Elf_Symndx *l_chain; + }; + const Elf_Symndx *l_buckets; unsigned int l_direct_opencount; /* Reference count for dlopen/dlclose. */ enum /* Where this object came from. */ [-- Attachment #4: prelink-gnu-hash.patch --] [-- Type: text/plain, Size: 3580 bytes --] --- prelink/src/prelink.h.jj 2006-06-20 15:12:16.000000000 +0200 +++ prelink/src/prelink.h 2006-06-27 21:50:11.000000000 +0200 @@ -44,6 +44,11 @@ #define SHT_GNU_LIBLIST 0x6ffffff7 #endif +#ifndef DT_GNU_HASH +#define DT_GNU_HASH 0x6ffffef5 +#define SHT_GNU_HASH 0x6ffffff6 +#endif + struct prelink_entry; struct prelink_info; struct PLArch; @@ -75,6 +80,7 @@ typedef struct GElf_Addr info_DT_GNU_PRELINKED; GElf_Addr info_DT_CHECKSUM; GElf_Addr info_DT_VERNEED, info_DT_VERDEF, info_DT_VERSYM; + GElf_Addr info_DT_GNU_HASH; #define DT_GNU_PRELINKED_BIT 50 #define DT_CHECKSUM_BIT 51 #define DT_VERNEED_BIT 52 @@ -83,6 +89,7 @@ typedef struct #define DT_FILTER_BIT 55 #define DT_AUXILIARY_BIT 56 #define DT_LOPROC_BIT 57 +#define DT_GNU_HASH_BIT 58 uint64_t info_set_mask; int fd, fdro; int lastscn, dynamic; --- prelink/src/prelink.c.jj 2005-06-10 17:09:06.000000000 +0200 +++ prelink/src/prelink.c 2006-06-27 21:53:20.000000000 +0200 @@ -1,4 +1,4 @@ -/* Copyright (C) 2001, 2002, 2003, 2004, 2005 Red Hat, Inc. +/* Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 Red Hat, Inc. Written by Jakub Jelinek <jakub@redhat.com>, 2001. This program is free software; you can redistribute it and/or modify @@ -424,6 +424,7 @@ prelink_prepare (DSO *dso) switch (dso->shdr[i].sh_type) { case SHT_HASH: + case SHT_GNU_HASH: case SHT_DYNSYM: case SHT_REL: case SHT_RELA: --- prelink/src/dso.c.jj 2006-06-21 11:46:34.000000000 +0200 +++ prelink/src/dso.c 2006-06-27 21:51:01.000000000 +0200 @@ -102,6 +102,11 @@ read_dynamic (DSO *dso) dso->info_set_mask |= (1ULL << DT_AUXILIARY_BIT); else if (dyn.d_tag == DT_LOPROC) dso->info_set_mask |= (1ULL << DT_LOPROC_BIT); + else if (dyn.d_tag == DT_GNU_HASH) + { + dso->info_DT_GNU_HASH = dyn.d_un.d_val; + dso->info_set_mask |= (1ULL << DT_GNU_HASH_BIT); + } } if (ndx < maxndx) break; @@ -1361,6 +1366,7 @@ adjust_dso (DSO *dso, GElf_Addr start, G return 1; break; case SHT_HASH: + case SHT_GNU_HASH: case SHT_NOBITS: case SHT_STRTAB: break; --- prelink/src/exec.c.jj 2006-05-22 16:33:43.000000000 +0200 +++ prelink/src/exec.c 2006-06-27 21:52:39.000000000 +0200 @@ -61,7 +61,11 @@ update_dynamic_tags (DSO *dso, GElf_Shdr || (dynamic_info_is_set (dso, DT_VERSYM_BIT) && dso->info_DT_VERSYM == old_shdr[j].sh_addr && old_shdr[j].sh_type == SHT_GNU_versym - && set_dynamic (dso, DT_VERSYM, shdr[i].sh_addr, 1))) + && set_dynamic (dso, DT_VERSYM, shdr[i].sh_addr, 1)) + || (dynamic_info_is_set (dso, DT_GNU_HASH_BIT) + && dso->info_DT_GNU_HASH == old_shdr[j].sh_addr + && old_shdr[j].sh_type == SHT_GNU_HASH + && set_dynamic (dso, DT_GNU_HASH, shdr[i].sh_addr, 1))) return 1; } --- prelink/src/space.c.jj 2006-05-22 16:27:00.000000000 +0200 +++ prelink/src/space.c 2006-06-27 21:48:06.000000000 +0200 @@ -60,6 +60,7 @@ print_sections (DSO *dso, GElf_Ehdr *ehd { SHT_GNU_verneed, "VERNEED" }, { SHT_GNU_versym, "VERSYM" }, { SHT_GNU_LIBLIST, "LIBLIST" }, + { SHT_GNU_HASH, "GNU_HASH" }, { 0, NULL } }; @@ -181,6 +182,7 @@ readonly_is_movable (DSO *dso, GElf_Ehdr switch (shdr[k].sh_type) { case SHT_HASH: + case SHT_GNU_HASH: case SHT_DYNSYM: case SHT_REL: case SHT_RELA: @@ -527,6 +529,7 @@ find_readonly_space (DSO *dso, GElf_Shdr switch (shdr[j].sh_type) { case SHT_HASH: + case SHT_GNU_HASH: case SHT_DYNSYM: case SHT_STRTAB: case SHT_GNU_verdef: ^ permalink raw reply [flat|nested] 17+ messages in thread
* RE: DT_GNU_HASH latest patches 2006-07-06 18:22 ` DT_GNU_HASH latest patches Jakub Jelinek @ 2006-07-06 19:53 ` djamel anonymous 2006-07-07 14:45 ` Jakub Jelinek 2006-07-07 10:07 ` Michael Meeks 1 sibling, 1 reply; 17+ messages in thread From: djamel anonymous @ 2006-07-06 19:53 UTC (permalink / raw) To: jakub, binutils; +Cc: drepper, michael.meeks, libc-alpha Hello, i am writing you this time about the first variant.after looking at the benchmark results i noted that there have been a reduction in the number of l1 cache misses; a reduction in l1 cache misses means a win of 12 cycles ; the difference between the latency of l2 cache and that of l1 cache 15-3.on the other hand replacing a division by a binary and & is a win of at least 25 cycles, so it think that avoiding tthe division in the common case may improve performance. changing the size of the main hash table is not an ideal solution because it is difficult to choose a good power of 2 size and there is no gurantee that a power of 2 size will give short chains.this also will introduce a great variability in the size nbcukets, they may be oversized which may give a big waste of space.on the other hand the solution of a filter before the main hash table that is a power of 2 has several advantages: 1-it is small: on average its size is nsymbols bytes, which has more chance to fit in the l1 cache than 3*nsymols or 4*nsymbols bytes for tha current hash table. 2-because it is small oversizing or undersizeing will not have a big impact on the overall space utilization. 3-the benchmark of take3 shows an increase in l2 cache misses because of the enlarged size of the hash table; the reduced size of the filter hash table may do less l2 cache misses. 4-in the take3 hash table there is a waste of space because the symbol index word inside the hash table is useless. according to the charts of yesterday there is between 5% and 12% empty buckets inside each hash table.for each empty bucket the symbol index will have no role and will be wasted. with the filter hash table every added word will participate in reducing the probability to go to the second hash table. when an access is done to the filter hash table and the bit is found to be set, there will be an access to the normal hash table.there is still a chance to avoid a third memory access if the bucket is found empty(between 5% and 12 %) so the average number of memeory accesses may not increase too much compared to take3. I think that nbucket must not be a power of two, otherwise every access to the normal hash table will access a non empty bucket and third memory access to the hash chains will be done. the following is a function that computes the nearest power of 2 to a given integer number. static inline unsigned pow2_round(unsigned int input) { unsigned log2=32-__builtin_clz(input); if ((1<<(log2-2))&(input)) return 1<<log2; else return 1<<(log2-1); }; the corresponding size of the filter hash table would be 8*pow2_round(nsymbols) bits or pow2_round(nsymbols)/4 32 bits integers. best regards. _________________________________________________________________ Testez Windows Llive Mail Beta ! http://www.msn.fr/newhotmail/Default.asp?Ath=f ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: DT_GNU_HASH latest patches 2006-07-06 19:53 ` djamel anonymous @ 2006-07-07 14:45 ` Jakub Jelinek 2006-07-07 15:57 ` djamel anonymous ` (4 more replies) 0 siblings, 5 replies; 17+ messages in thread From: Jakub Jelinek @ 2006-07-07 14:45 UTC (permalink / raw) To: djamel anonymous; +Cc: binutils, drepper, michael.meeks, libc-alpha [-- Attachment #1: Type: text/plain, Size: 915 bytes --] On Thu, Jul 06, 2006 at 07:53:29PM +0000, djamel anonymous wrote: > Hello, i am writing you this time about the first variant.after looking at > the benchmark results i noted that there have been a reduction in the > number of l1 cache misses; a reduction in l1 cache misses means a win of 12 > cycles ; the difference between the latency of l2 cache and that of l1 > cache 15-3.on the other hand replacing a division by a binary and & is a > win of at least 25 cycles, so it think that avoiding tthe division in the > common case may improve performance. I don't think it is the modulo that matters, but the smaller footprint of .gnu.hash case in that case. I have implemented what I think you meant and the numbers actually convinced me. So here is the new set of patches and new statistics. take1 is 2006-06-28 state of things, take2 2006-07-03, take3 2006-07-05 and take4 what is attached here. Jakub [-- Attachment #2: binutils-hash-style.patch --] [-- Type: text/plain, Size: 39189 bytes --] 2006-07-07 Jakub Jelinek <jakub@redhat.com> include/ * bfdlink.h (struct bfd_link_info): Add emit_hash and emit_gnu_hash bitfields. include/elf/ * common.h (SHT_GNU_HASH, DT_GNU_HASH): Define. ld/ * scripttempl/elf.sc: Add .gnu.hash section. * emultempl/elf32.em (OPTION_HASH_STYLE): Define. (gld${EMULATION_NAME}_add_options): Register --hash-style option. (gld${EMULATION_NAME}_handle_option): Handle it. (gld${EMULATION_NAME}_list_options): Document it. * ldmain.c (main): Initialize emit_hash and emit_gnu_hash. * ld.texinfo: Document --hash-style option. bfd/ * elf.c (_bfd_elf_print_private_bfd_data): Handle DT_GNU_HASH. (bfd_section_from_shdr, elf_fake_sections, assign_section_numbers): Handle SHT_GNU_HASH. (special_sections_g): Include .gnu.hash section. (bfd_elf_gnu_hash): New function. * elf-bfd.h (bfd_elf_gnu_hash, _bfd_elf_hash_symbol): New prototypes. (struct elf_backend_data): Add elf_hash_symbol method. * elflink.c (_bfd_elf_link_create_dynamic_sections): Create .hash only if info->emit_hash, create .gnu.hash section if info->emit_gnu_hash. (struct collect_gnu_hash_codes): New type. (elf_collect_gnu_hash_codes, elf_renumber_gnu_hash_syms, _bfd_elf_hash_symbol): New functions. (compute_bucket_count): Don't compute HASHCODES array, instead add that and NSYMS as arguments. Use bed->s->sizeof_hash_entry instead of bed->s->arch_size / 8. Fix .hash size estimation. When not optimizing, use the number of hashed symbols rather than dynsymcount. (bfd_elf_size_dynamic_sections): Only add DT_HASH if info->emit_hash, and ADD DT_GNU_HASH if info->emit_gnu_hash. (bfd_elf_size_dynsym_hash_dynstr): Size .hash only if info->emit_hash, adjust compute_bucket_count caller. Create and populate .gnu.hash section if info->emit_gnu_hash. (elf_link_output_extsym): Only populate .hash section if finfo->hash_sec != NULL. (bfd_elf_final_link): Adjust assertion. Handle DT_GNU_HASH. * elfxx-target.h (elf_backend_hash_symbol): Define if not yet defined. (elfNN_bed): Add elf_backend_hash_symbol. * elf64-x86-64.c (elf64_x86_64_hash_symbol): New function. (elf_backend_hash_symbol): Define. * elf32-i386.c (elf_i386_hash_symbol): New function. (elf_backend_hash_symbol): Define. binutils/ * readelf.c (get_dynamic_type): Handle DT_GNU_HASH. (get_section_type_name): Handle SHT_GNU_HASH. (dynamic_info_DT_GNU_HASH): New variable. (process_dynamic_section): Handle DT_GNU_HASH. (process_symbol_table): Print also DT_GNU_HASH histogram. --- ld/scripttempl/elf.sc.jj 2006-01-01 01:02:16.000000000 +0100 +++ ld/scripttempl/elf.sc 2006-06-22 11:11:53.000000000 +0200 @@ -260,6 +260,7 @@ SECTIONS ${INITIAL_READONLY_SECTIONS} ${TEXT_DYNAMIC+${DYNAMIC}} .hash ${RELOCATING-0} : { *(.hash) } + .gnu.hash ${RELOCATING-0} : { *(.gnu.hash) } .dynsym ${RELOCATING-0} : { *(.dynsym) } .dynstr ${RELOCATING-0} : { *(.dynstr) } .gnu.version ${RELOCATING-0} : { *(.gnu.version) } --- ld/ldmain.c.jj 2006-06-01 15:50:33.000000000 +0200 +++ ld/ldmain.c 2006-06-22 11:21:11.000000000 +0200 @@ -304,6 +304,8 @@ main (int argc, char **argv) link_info.create_object_symbols_section = NULL; link_info.gc_sym_list = NULL; link_info.base_file = NULL; + link_info.emit_hash = TRUE; + link_info.emit_gnu_hash = FALSE; /* SVR4 linkers seem to set DT_INIT and DT_FINI based on magic _init and _fini symbols. We are compatible. */ link_info.init_function = "_init"; --- ld/ld.texinfo.jj 2006-06-15 14:31:06.000000000 +0200 +++ ld/ld.texinfo 2006-06-22 14:03:21.000000000 +0200 @@ -1883,6 +1883,14 @@ time it takes the linker to perform its increasing the linker's memory requirements. Similarly reducing this value can reduce the memory requirements at the expense of speed. +@kindex --hash-style=@var{style} +@item --hash-style=@var{style} +Set the type of linker's hash table(s). @var{style} can be either +@code{sysv} for classic ELF @code{.hash} section, @code{gnu} for +new style GNU @code{.gnu.hash} section or @code{both} for both +the classic ELF @code{.hash} and new style GNU @code{.gnu.hash} +hash tables. The default is @code{sysv}. + @kindex --reduce-memory-overheads @item --reduce-memory-overheads This option reduces memory requirements at ld runtime, at the expense of --- ld/emultempl/elf32.em.jj 2006-06-20 18:34:24.000000000 +0200 +++ ld/emultempl/elf32.em 2006-06-22 14:39:25.000000000 +0200 @@ -1719,6 +1719,7 @@ cat >>e${EMULATION_NAME}.c <<EOF #define OPTION_GROUP (OPTION_ENABLE_NEW_DTAGS + 1) #define OPTION_EH_FRAME_HDR (OPTION_GROUP + 1) #define OPTION_EXCLUDE_LIBS (OPTION_EH_FRAME_HDR + 1) +#define OPTION_HASH_STYLE (OPTION_EXCLUDE_LIBS + 1) static void gld${EMULATION_NAME}_add_options @@ -1735,6 +1736,7 @@ cat >>e${EMULATION_NAME}.c <<EOF {"enable-new-dtags", no_argument, NULL, OPTION_ENABLE_NEW_DTAGS}, {"eh-frame-hdr", no_argument, NULL, OPTION_EH_FRAME_HDR}, {"exclude-libs", required_argument, NULL, OPTION_EXCLUDE_LIBS}, + {"hash-style", required_argument, NULL, OPTION_HASH_STYLE}, {"Bgroup", no_argument, NULL, OPTION_GROUP}, EOF fi @@ -1791,6 +1793,22 @@ cat >>e${EMULATION_NAME}.c <<EOF add_excluded_libs (optarg); break; + case OPTION_HASH_STYLE: + link_info.emit_hash = FALSE; + link_info.emit_gnu_hash = FALSE; + if (strcmp (optarg, "sysv") == 0) + link_info.emit_hash = TRUE; + else if (strcmp (optarg, "gnu") == 0) + link_info.emit_gnu_hash = TRUE; + else if (strcmp (optarg, "both") == 0) + { + link_info.emit_hash = TRUE; + link_info.emit_gnu_hash = TRUE; + } + else + einfo (_("%P%F: invalid hash style \`%s'\n"), optarg); + break; + case 'z': if (strcmp (optarg, "initfirst") == 0) link_info.flags_1 |= (bfd_vma) DF_1_INITFIRST; @@ -1894,6 +1912,7 @@ cat >>e${EMULATION_NAME}.c <<EOF fprintf (file, _(" --disable-new-dtags\tDisable new dynamic tags\n")); fprintf (file, _(" --enable-new-dtags\tEnable new dynamic tags\n")); fprintf (file, _(" --eh-frame-hdr\tCreate .eh_frame_hdr section\n")); + fprintf (file, _(" --hash-stylle=STYLE\tSet hash style to sysv, gnu or both\n")); fprintf (file, _(" -z combreloc\t\tMerge dynamic relocs into one section and sort\n")); fprintf (file, _(" -z defs\t\tReport unresolved symbols in object files.\n")); fprintf (file, _(" -z execstack\t\tMark executable as requiring executable stack\n")); --- bfd/elf-bfd.h.jj 2006-06-20 18:34:24.000000000 +0200 +++ bfd/elf-bfd.h 2006-07-06 15:48:12.000000000 +0200 @@ -1038,6 +1038,9 @@ struct elf_backend_data bfd_boolean *, bfd_boolean *, bfd *, asection **); + /* Return TRUE if symbol should be hashed in the `.gnu.hash' section. */ + bfd_boolean (*elf_hash_symbol) (struct elf_link_hash_entry *); + /* Used to handle bad SHF_LINK_ORDER input. */ bfd_error_handler_type link_order_error_handler; @@ -1481,6 +1484,8 @@ extern bfd_vma _bfd_elf_section_offset extern unsigned long bfd_elf_hash (const char *); +extern unsigned long bfd_elf_gnu_hash + (const char *); extern bfd_reloc_status_type bfd_elf_generic_reloc (bfd *, arelent *, asymbol *, void *, asection *, bfd *, char **); @@ -1651,6 +1656,8 @@ extern bfd_boolean _bfd_elf_merge_symbol struct elf_link_hash_entry **, bfd_boolean *, bfd_boolean *, bfd_boolean *, bfd_boolean *); +extern bfd_boolean _bfd_elf_hash_symbol (struct elf_link_hash_entry *); + extern bfd_boolean _bfd_elf_add_default_symbol (bfd *, struct bfd_link_info *, struct elf_link_hash_entry *, const char *, Elf_Internal_Sym *, asection **, bfd_vma *, --- bfd/elf64-x86-64.c.jj 2006-06-20 11:57:19.000000000 +0200 +++ bfd/elf64-x86-64.c 2006-07-06 16:54:21.000000000 +0200 @@ -3615,6 +3615,19 @@ elf64_x86_64_additional_program_headers return count; } +/* Return TRUE if symbol should be hashed in the `.gnu.hash' section. */ + +static bfd_boolean +elf64_x86_64_hash_symbol (struct elf_link_hash_entry *h) +{ + if (h->plt.offset != (bfd_vma) -1 + && !h->def_regular + && !h->pointer_equality_needed) + return FALSE; + + return _bfd_elf_hash_symbol (h); +} + static const struct bfd_elf_special_section elf64_x86_64_special_sections[]= { @@ -3688,5 +3701,7 @@ static const struct bfd_elf_special_sect elf64_x86_64_special_sections #define elf_backend_additional_program_headers \ elf64_x86_64_additional_program_headers +#define elf_backend_hash_symbol \ + elf64_x86_64_hash_symbol #include "elf64-target.h" --- bfd/elf.c.jj 2006-06-20 18:34:24.000000000 +0200 +++ bfd/elf.c 2006-06-26 16:17:28.000000000 +0200 @@ -206,6 +206,21 @@ bfd_elf_hash (const char *namearg) return h & 0xffffffff; } +/* DT_GNU_HASH hash function. Do not change this function; you will + cause invalid hash tables to be generated. */ + +unsigned long +bfd_elf_gnu_hash (const char *namearg) +{ + const unsigned char *name = (const unsigned char *) namearg; + unsigned long h = 5381; + unsigned char ch; + + while ((ch = *name++) != '\0') + h = (h << 5) + h + ch; + return h & 0xffffffff; +} + bfd_boolean bfd_elf_mkobject (bfd *abfd) { @@ -1239,6 +1254,7 @@ _bfd_elf_print_private_bfd_data (bfd *ab case DT_AUXILIARY: name = "AUXILIARY"; stringp = TRUE; break; case DT_USED: name = "USED"; break; case DT_FILTER: name = "FILTER"; stringp = TRUE; break; + case DT_GNU_HASH: name = "GNU_HASH"; break; } fprintf (f, " %-11s ", name); @@ -1823,6 +1839,7 @@ bfd_section_from_shdr (bfd *abfd, unsign case SHT_FINI_ARRAY: /* .fini_array section. */ case SHT_PREINIT_ARRAY: /* .preinit_array section. */ case SHT_GNU_LIBLIST: /* .gnu.liblist section. */ + case SHT_GNU_HASH: /* .gnu.hash section. */ return _bfd_elf_make_section_from_shdr (abfd, hdr, name, shindex); case SHT_DYNAMIC: /* Dynamic linking information. */ @@ -2295,6 +2312,7 @@ static const struct bfd_elf_special_sect { ".gnu.version_r", 14, 0, SHT_GNU_verneed, 0 }, { ".gnu.liblist", 12, 0, SHT_GNU_LIBLIST, SHF_ALLOC }, { ".gnu.conflict", 13, 0, SHT_RELA, SHF_ALLOC }, + { ".gnu.hash", 9, 0, SHT_GNU_HASH, SHF_ALLOC }, { NULL, 0, 0, 0, 0 } }; @@ -2811,6 +2829,10 @@ elf_fake_sections (bfd *abfd, asection * case SHT_GROUP: this_hdr->sh_entsize = 4; break; + + case SHT_GNU_HASH: + this_hdr->sh_entsize = 4; + break; } if ((asect->flags & SEC_ALLOC) != 0) @@ -3256,6 +3278,7 @@ assign_section_numbers (bfd *abfd, struc break; case SHT_HASH: + case SHT_GNU_HASH: case SHT_GNU_versym: /* sh_link is the section header index of the symbol table this hash table or version table is for. */ --- bfd/elf32-i386.c.jj 2006-06-23 15:32:34.000000000 +0200 +++ bfd/elf32-i386.c 2006-07-06 16:56:24.000000000 +0200 @@ -3835,6 +3835,18 @@ elf_i386_plt_sym_val (bfd_vma i, const a return plt->vma + (i + 1) * PLT_ENTRY_SIZE; } +/* Return TRUE if symbol should be hashed in the `.gnu.hash' section. */ + +static bfd_boolean +elf_i386_hash_symbol (struct elf_link_hash_entry *h) +{ + if (h->plt.offset != (bfd_vma) -1 + && !h->def_regular + && !h->pointer_equality_needed) + return FALSE; + + return _bfd_elf_hash_symbol (h); +} #define TARGET_LITTLE_SYM bfd_elf32_i386_vec #define TARGET_LITTLE_NAME "elf32-i386" @@ -3875,6 +3887,7 @@ elf_i386_plt_sym_val (bfd_vma i, const a #define elf_backend_size_dynamic_sections elf_i386_size_dynamic_sections #define elf_backend_always_size_sections elf_i386_always_size_sections #define elf_backend_plt_sym_val elf_i386_plt_sym_val +#define elf_backend_hash_symbol elf_i386_hash_symbol #include "elf32-target.h" --- bfd/elflink.c.jj 2006-06-20 18:34:53.000000000 +0200 +++ bfd/elflink.c 2006-07-07 16:19:55.000000000 +0200 @@ -240,12 +240,24 @@ _bfd_elf_link_create_dynamic_sections (b if (!_bfd_elf_define_linkage_sym (abfd, info, s, "_DYNAMIC")) return FALSE; - s = bfd_make_section_with_flags (abfd, ".hash", - flags | SEC_READONLY); - if (s == NULL - || ! bfd_set_section_alignment (abfd, s, bed->s->log_file_align)) - return FALSE; - elf_section_data (s)->this_hdr.sh_entsize = bed->s->sizeof_hash_entry; + if (info->emit_hash) + { + s = bfd_make_section_with_flags (abfd, ".hash", flags | SEC_READONLY); + if (s == NULL + || ! bfd_set_section_alignment (abfd, s, bed->s->log_file_align)) + return FALSE; + elf_section_data (s)->this_hdr.sh_entsize = bed->s->sizeof_hash_entry; + } + + if (info->emit_gnu_hash) + { + s = bfd_make_section_with_flags (abfd, ".gnu.hash", + flags | SEC_READONLY); + if (s == NULL + || ! bfd_set_section_alignment (abfd, s, 3)) + return FALSE; + elf_section_data (s)->this_hdr.sh_entsize = 4; + } /* Let the backend create the rest of the sections. This lets the backend set the right flags. The backend will normally create @@ -4811,6 +4823,126 @@ elf_collect_hash_codes (struct elf_link_ return TRUE; } +struct collect_gnu_hash_codes +{ + bfd *output_bfd; + const struct elf_backend_data *bed; + unsigned long int nsyms; + unsigned long int maskbits; + unsigned long int *hashcodes; + unsigned long int *hashval; + unsigned long int *indx; + unsigned long int *counts; + unsigned long int *bitmask; + bfd_byte *contents; + long int min_dynindx; + unsigned long int bucketcount; + unsigned long int symindx; + long int local_indx; +}; + +/* This function will be called though elf_link_hash_traverse to store + all hash value of the exported symbols in an array. */ + +static bfd_boolean +elf_collect_gnu_hash_codes (struct elf_link_hash_entry *h, void *data) +{ + struct collect_gnu_hash_codes *s = data; + const char *name; + char *p; + unsigned long ha; + char *alc = NULL; + + if (h->root.type == bfd_link_hash_warning) + h = (struct elf_link_hash_entry *) h->root.u.i.link; + + /* Ignore indirect symbols. These are added by the versioning code. */ + if (h->dynindx == -1) + return TRUE; + + /* Ignore also local symbols and undefined symbols. */ + if (! (*s->bed->elf_hash_symbol) (h)) + return TRUE; + + name = h->root.root.string; + p = strchr (name, ELF_VER_CHR); + if (p != NULL) + { + alc = bfd_malloc (p - name + 1); + memcpy (alc, name, p - name); + alc[p - name] = '\0'; + name = alc; + } + + /* Compute the hash value. */ + ha = bfd_elf_gnu_hash (name); + + /* Store the found hash value in the array for compute_bucket_count, + and also for .dynsym reordering purposes. */ + s->hashcodes[s->nsyms] = ha; + s->hashval[h->dynindx] = ha; + ++s->nsyms; + if (s->min_dynindx < 0 || s->min_dynindx > h->dynindx) + s->min_dynindx = h->dynindx; + + if (alc != NULL) + free (alc); + + return TRUE; +} + +/* This function will be called though elf_link_hash_traverse to do + final dynaminc symbol renumbering. */ + +static bfd_boolean +elf_renumber_gnu_hash_syms (struct elf_link_hash_entry *h, void *data) +{ + struct collect_gnu_hash_codes *s = data; + unsigned long int bucket; + unsigned long int val; + + if (h->root.type == bfd_link_hash_warning) + h = (struct elf_link_hash_entry *) h->root.u.i.link; + + /* Ignore indirect symbols. */ + if (h->dynindx == -1) + return TRUE; + + /* Ignore also local symbols and undefined symbols. */ + if (! (*s->bed->elf_hash_symbol) (h)) + { + if (h->dynindx >= s->min_dynindx) + h->dynindx = s->local_indx++; + return TRUE; + } + + bucket = s->hashval[h->dynindx] % s->bucketcount; + val = (s->hashval[h->dynindx] >> 5) & ((s->maskbits >> 5) - 1); + s->bitmask[val] |= ((unsigned long int) 1) << (s->hashval[h->dynindx] & 31); + val = s->hashval[h->dynindx] & ~(unsigned long int) 1; + if (s->counts[bucket] == 1) + /* Last element terminates the chain. */ + val |= 1; + bfd_put_32 (s->output_bfd, val, + s->contents + (s->indx[bucket] - s->symindx) * 4); + --s->counts[bucket]; + h->dynindx = s->indx[bucket]++; + return TRUE; +} + +/* Return TRUE if symbol should be hashed in the `.gnu.hash' section. */ + +bfd_boolean +_bfd_elf_hash_symbol (struct elf_link_hash_entry *h) +{ + return !(h->forced_local + || h->root.type == bfd_link_hash_undefined + || h->root.type == bfd_link_hash_undefweak + || ((h->root.type == bfd_link_hash_defined + || h->root.type == bfd_link_hash_defweak) + && h->root.u.def.section->output_section == NULL)); +} + /* Array used to determine the number of hash table buckets to use based on the number of symbols there are. If there are fewer than 3 symbols we use 1 bucket, fewer than 17 symbols we use 3 buckets, @@ -4832,42 +4964,26 @@ static const size_t elf_buckets[] = Therefore the result is always a good payoff between few collisions (= short chain lengths) and table size. */ static size_t -compute_bucket_count (struct bfd_link_info *info) +compute_bucket_count (struct bfd_link_info *info, unsigned long int *hashcodes, + unsigned long int nsyms, int gnu_hash) { size_t dynsymcount = elf_hash_table (info)->dynsymcount; size_t best_size = 0; - unsigned long int *hashcodes; - unsigned long int *hashcodesp; unsigned long int i; bfd_size_type amt; - /* Compute the hash values for all exported symbols. At the same - time store the values in an array so that we could use them for - optimizations. */ - amt = dynsymcount; - amt *= sizeof (unsigned long int); - hashcodes = bfd_malloc (amt); - if (hashcodes == NULL) - return 0; - hashcodesp = hashcodes; - - /* Put all hash values in HASHCODES. */ - elf_link_hash_traverse (elf_hash_table (info), - elf_collect_hash_codes, &hashcodesp); - /* We have a problem here. The following code to optimize the table size requires an integer type with more the 32 bits. If BFD_HOST_U_64_BIT is set we know about such a type. */ #ifdef BFD_HOST_U_64_BIT if (info->optimize) { - unsigned long int nsyms = hashcodesp - hashcodes; size_t minsize; size_t maxsize; BFD_HOST_U_64_BIT best_chlen = ~((BFD_HOST_U_64_BIT) 0); - unsigned long int *counts ; bfd *dynobj = elf_hash_table (info)->dynobj; const struct elf_backend_data *bed = get_elf_backend_data (dynobj); + unsigned long int *counts; /* Possible optimization parameters: if we have NSYMS symbols we say that the hashing table must at least have NSYMS/4 and at most @@ -4876,6 +4992,13 @@ compute_bucket_count (struct bfd_link_in if (minsize == 0) minsize = 1; best_size = maxsize = nsyms * 2; + if (gnu_hash) + { + if (minsize < 2) + minsize = 2; + if ((best_size & 31) == 0) + ++best_size; + } /* Create array where we count the collisions in. We must use bfd_malloc since the size could be large. */ @@ -4883,10 +5006,7 @@ compute_bucket_count (struct bfd_link_in amt *= sizeof (unsigned long int); counts = bfd_malloc (amt); if (counts == NULL) - { - free (hashcodes); - return 0; - } + return 0; /* Compute the "optimal" size for the hash table. The criteria is a minimal chain length. The minor criteria is (of course) the size @@ -4898,6 +5018,9 @@ compute_bucket_count (struct bfd_link_in unsigned long int j; unsigned long int fact; + if (gnu_hash && (i & 31) == 0) + continue; + memset (counts, '\0', i * sizeof (unsigned long int)); /* Determine how often each hash bucket is used. */ @@ -4913,9 +5036,9 @@ compute_bucket_count (struct bfd_link_in # define BFD_TARGET_PAGESIZE (4096) # endif - /* We in any case need 2 + NSYMS entries for the size values and - the chains. */ - max = (2 + nsyms) * (bed->s->arch_size / 8); + /* We in any case need 2 + DYNSYMCOUNT entries for the size values + and the chains. */ + max = (2 + dynsymcount) * bed->s->sizeof_hash_entry; # if 1 /* Variant 1: optimize for short chains. We add the squares @@ -4925,7 +5048,7 @@ compute_bucket_count (struct bfd_link_in max += counts[j] * counts[j]; /* This adds penalties for the overall size of the table. */ - fact = i / (BFD_TARGET_PAGESIZE / (bed->s->arch_size / 8)) + 1; + fact = i / (BFD_TARGET_PAGESIZE / bed->s->sizeof_hash_entry) + 1; max *= fact * fact; # else /* Variant 2: Optimize a lot more for small table. Here we @@ -4936,7 +5059,7 @@ compute_bucket_count (struct bfd_link_in /* The overall size of the table is considered, but not as strong as in variant 1, where it is squared. */ - fact = i / (BFD_TARGET_PAGESIZE / (bed->s->arch_size / 8)) + 1; + fact = i / (BFD_TARGET_PAGESIZE / bed->s->sizeof_hash_entry) + 1; max *= fact; # endif @@ -4959,14 +5082,13 @@ compute_bucket_count (struct bfd_link_in for (i = 0; elf_buckets[i] != 0; i++) { best_size = elf_buckets[i]; - if (dynsymcount < elf_buckets[i + 1]) + if (nsyms < elf_buckets[i + 1]) break; } + if (gnu_hash && best_size < 2) + best_size = 2; } - /* Free the arrays we needed. */ - free (hashcodes); - return best_size; } @@ -5324,7 +5446,10 @@ bfd_elf_size_dynamic_sections (bfd *outp bfd_size_type strsize; strsize = _bfd_elf_strtab_size (elf_hash_table (info)->dynstr); - if (!_bfd_elf_add_dynamic_entry (info, DT_HASH, 0) + if ((info->emit_hash + && !_bfd_elf_add_dynamic_entry (info, DT_HASH, 0)) + || (info->emit_gnu_hash + && !_bfd_elf_add_dynamic_entry (info, DT_GNU_HASH, 0)) || !_bfd_elf_add_dynamic_entry (info, DT_STRTAB, 0) || !_bfd_elf_add_dynamic_entry (info, DT_SYMTAB, 0) || !_bfd_elf_add_dynamic_entry (info, DT_STRSZ, strsize) @@ -5726,8 +5851,6 @@ bfd_elf_size_dynsym_hash_dynstr (bfd *ou asection *s; bfd_size_type dynsymcount; unsigned long section_sym_count; - size_t bucketcount = 0; - size_t hash_entry_size; unsigned int dtagcount; dynobj = elf_hash_table (info)->dynobj; @@ -5778,23 +5901,195 @@ bfd_elf_size_dynsym_hash_dynstr (bfd *ou memset (s->contents, 0, section_sym_count * bed->s->sizeof_sym); } + elf_hash_table (info)->bucketcount = 0; + /* Compute the size of the hashing table. As a side effect this computes the hash values for all the names we export. */ - bucketcount = compute_bucket_count (info); + if (info->emit_hash) + { + unsigned long int *hashcodes; + unsigned long int *hashcodesp; + bfd_size_type amt; + unsigned long int nsyms; + size_t bucketcount; + size_t hash_entry_size; + + /* Compute the hash values for all exported symbols. At the same + time store the values in an array so that we could use them for + optimizations. */ + amt = dynsymcount * sizeof (unsigned long int); + hashcodes = bfd_malloc (amt); + if (hashcodes == NULL) + return FALSE; + hashcodesp = hashcodes; - s = bfd_get_section_by_name (dynobj, ".hash"); - BFD_ASSERT (s != NULL); - hash_entry_size = elf_section_data (s)->this_hdr.sh_entsize; - s->size = ((2 + bucketcount + dynsymcount) * hash_entry_size); - s->contents = bfd_zalloc (output_bfd, s->size); - if (s->contents == NULL) - return FALSE; + /* Put all hash values in HASHCODES. */ + elf_link_hash_traverse (elf_hash_table (info), + elf_collect_hash_codes, &hashcodesp); + + nsyms = hashcodesp - hashcodes; + bucketcount + = compute_bucket_count (info, hashcodes, nsyms, 0); + free (hashcodes); + + if (bucketcount == 0) + return FALSE; - bfd_put (8 * hash_entry_size, output_bfd, bucketcount, s->contents); - bfd_put (8 * hash_entry_size, output_bfd, dynsymcount, - s->contents + hash_entry_size); + elf_hash_table (info)->bucketcount = bucketcount; - elf_hash_table (info)->bucketcount = bucketcount; + s = bfd_get_section_by_name (dynobj, ".hash"); + BFD_ASSERT (s != NULL); + hash_entry_size = elf_section_data (s)->this_hdr.sh_entsize; + s->size = ((2 + bucketcount + dynsymcount) * hash_entry_size); + s->contents = bfd_zalloc (output_bfd, s->size); + if (s->contents == NULL) + return FALSE; + + bfd_put (8 * hash_entry_size, output_bfd, bucketcount, s->contents); + bfd_put (8 * hash_entry_size, output_bfd, dynsymcount, + s->contents + hash_entry_size); + } + + if (info->emit_gnu_hash) + { + size_t i, cnt; + unsigned char *contents; + struct collect_gnu_hash_codes cinfo; + bfd_size_type amt; + size_t bucketcount; + + memset (&cinfo, 0, sizeof (cinfo)); + + /* Compute the hash values for all exported symbols. At the same + time store the values in an array so that we could use them for + optimizations. */ + amt = dynsymcount * 2 * sizeof (unsigned long int); + cinfo.hashcodes = bfd_malloc (amt); + if (cinfo.hashcodes == NULL) + return FALSE; + + cinfo.hashval = cinfo.hashcodes + dynsymcount; + cinfo.min_dynindx = -1; + cinfo.output_bfd = output_bfd; + cinfo.bed = bed; + + /* Put all hash values in HASHCODES. */ + elf_link_hash_traverse (elf_hash_table (info), + elf_collect_gnu_hash_codes, &cinfo); + + bucketcount + = compute_bucket_count (info, cinfo.hashcodes, cinfo.nsyms, 1); + + if (bucketcount == 0) + { + free (cinfo.hashcodes); + return FALSE; + } + + s = bfd_get_section_by_name (dynobj, ".gnu.hash"); + BFD_ASSERT (s != NULL); + + if (cinfo.nsyms == 0) + { + /* Empty .gnu.hash section is special. */ + BFD_ASSERT (cinfo.min_dynindx == -1); + free (cinfo.hashcodes); + s->size = 5 * 4; + contents = bfd_zalloc (output_bfd, s->size); + if (contents == NULL) + return FALSE; + s->contents = contents; + /* 1 empty bucket. */ + bfd_put_32 (output_bfd, 1, contents); + /* SYMIDX above the special symbol 0. */ + bfd_put_32 (output_bfd, 1, contents + 4); + /* Just one word for bitmask. */ + bfd_put_32 (output_bfd, 1, contents + 8); + /* No hashes are valid - empty bitmask. */ + bfd_put_32 (output_bfd, 0, contents + 12); + /* No hashes in the only bucket. */ + bfd_put_32 (output_bfd, 0, contents + 16); + } + else + { + BFD_ASSERT (cinfo.min_dynindx != -1); + + cinfo.maskbits = bfd_log2 (cinfo.nsyms) + 1; + if (cinfo.maskbits < 3) + cinfo.maskbits = 1 << 5; + else if ((1 << (cinfo.maskbits - 2)) & cinfo.nsyms) + cinfo.maskbits = 1 << (cinfo.maskbits + 3); + else + cinfo.maskbits = 1 << (cinfo.maskbits + 2); + amt = bucketcount * sizeof (unsigned long int) * 2; + amt += (cinfo.maskbits / 32) * sizeof (unsigned long int); + cinfo.counts = bfd_malloc (amt); + if (cinfo.counts == NULL) + { + free (cinfo.hashcodes); + return FALSE; + } + + /* Determine how often each hash bucket is used. */ + memset (cinfo.counts, 0, + bucketcount * sizeof (cinfo.counts[0])); + for (i = 0; i < cinfo.nsyms; ++i) + ++cinfo.counts[cinfo.hashcodes[i] % bucketcount]; + + cinfo.indx = cinfo.counts + bucketcount; + cinfo.bitmask = cinfo.counts + 2 * bucketcount; + memset (cinfo.bitmask, 0, (cinfo.maskbits / 32) + * sizeof (unsigned long int)); + cinfo.symindx = dynsymcount - cinfo.nsyms; + for (i = 0, cnt = cinfo.symindx; i < bucketcount; ++i) + if (cinfo.counts[i] != 0) + { + cinfo.indx[i] = cnt; + cnt += cinfo.counts[i]; + } + BFD_ASSERT (cnt == dynsymcount); + cinfo.bucketcount = bucketcount; + cinfo.local_indx = cinfo.min_dynindx; + + s->size = (3 + bucketcount + cinfo.nsyms) * 4; + s->size += cinfo.maskbits / 8; + contents = bfd_zalloc (output_bfd, s->size); + if (contents == NULL) + { + free (cinfo.counts); + free (cinfo.hashcodes); + return FALSE; + } + + s->contents = contents; + bfd_put_32 (output_bfd, bucketcount, contents); + bfd_put_32 (output_bfd, cinfo.symindx, contents + 4); + bfd_put_32 (output_bfd, cinfo.maskbits / 32, contents + 8); + contents += 12 + cinfo.maskbits / 8; + + for (i = 0; i < bucketcount; ++i) + { + if (cinfo.counts[i] == 0) + bfd_put_32 (output_bfd, 0, contents); + else + bfd_put_32 (output_bfd, cinfo.indx[i], contents); + contents += 4; + } + + cinfo.contents = contents; + + /* Renumber dynamic symbols, populate .gnu.hash section. */ + elf_link_hash_traverse (elf_hash_table (info), + elf_renumber_gnu_hash_syms, &cinfo); + + contents = s->contents + 12; + for (i = 0; i < cinfo.maskbits / 32; ++i, contents += 4) + bfd_put_32 (output_bfd, cinfo.bitmask[i], contents); + + free (cinfo.counts); + free (cinfo.hashcodes); + } + } s = bfd_get_section_by_name (dynobj, ".dynstr"); BFD_ASSERT (s != NULL); @@ -6663,9 +6958,6 @@ elf_link_output_extsym (struct elf_link_ { size_t bucketcount; size_t bucket; - size_t hash_entry_size; - bfd_byte *bucketpos; - bfd_vma chain; bfd_byte *esym; sym.st_name = h->dynstr_index; @@ -6679,15 +6971,23 @@ elf_link_output_extsym (struct elf_link_ bucketcount = elf_hash_table (finfo->info)->bucketcount; bucket = h->u.elf_hash_value % bucketcount; - hash_entry_size - = elf_section_data (finfo->hash_sec)->this_hdr.sh_entsize; - bucketpos = ((bfd_byte *) finfo->hash_sec->contents - + (bucket + 2) * hash_entry_size); - chain = bfd_get (8 * hash_entry_size, finfo->output_bfd, bucketpos); - bfd_put (8 * hash_entry_size, finfo->output_bfd, h->dynindx, bucketpos); - bfd_put (8 * hash_entry_size, finfo->output_bfd, chain, - ((bfd_byte *) finfo->hash_sec->contents - + (bucketcount + 2 + h->dynindx) * hash_entry_size)); + + if (finfo->hash_sec != NULL) + { + size_t hash_entry_size; + bfd_byte *bucketpos; + bfd_vma chain; + + hash_entry_size + = elf_section_data (finfo->hash_sec)->this_hdr.sh_entsize; + bucketpos = ((bfd_byte *) finfo->hash_sec->contents + + (bucket + 2) * hash_entry_size); + chain = bfd_get (8 * hash_entry_size, finfo->output_bfd, bucketpos); + bfd_put (8 * hash_entry_size, finfo->output_bfd, h->dynindx, bucketpos); + bfd_put (8 * hash_entry_size, finfo->output_bfd, chain, + ((bfd_byte *) finfo->hash_sec->contents + + (bucketcount + 2 + h->dynindx) * hash_entry_size)); + } if (finfo->symver_sec != NULL && finfo->symver_sec->contents != NULL) { @@ -7861,7 +8161,7 @@ bfd_elf_final_link (bfd *abfd, struct bf { finfo.dynsym_sec = bfd_get_section_by_name (dynobj, ".dynsym"); finfo.hash_sec = bfd_get_section_by_name (dynobj, ".hash"); - BFD_ASSERT (finfo.dynsym_sec != NULL && finfo.hash_sec != NULL); + BFD_ASSERT (finfo.dynsym_sec != NULL); finfo.symver_sec = bfd_get_section_by_name (dynobj, ".gnu.version"); /* Note that it is OK if symver_sec is NULL. */ } @@ -8621,6 +8921,9 @@ bfd_elf_final_link (bfd *abfd, struct bf case DT_HASH: name = ".hash"; goto get_vma; + case DT_GNU_HASH: + name = ".gnu.hash"; + goto get_vma; case DT_STRTAB: name = ".dynstr"; goto get_vma; --- bfd/elfxx-target.h.jj 2006-06-20 18:34:24.000000000 +0200 +++ bfd/elfxx-target.h 2006-07-06 15:38:39.000000000 +0200 @@ -563,6 +563,10 @@ #define elf_backend_merge_symbol NULL #endif +#ifndef elf_backend_hash_symbol +#define elf_backend_hash_symbol _bfd_elf_hash_symbol +#endif + extern const struct elf_size_info _bfd_elfNN_size_info; #ifndef INCLUDED_TARGET_FILE @@ -643,6 +647,7 @@ static struct elf_backend_data elfNN_bed elf_backend_common_section_index, elf_backend_common_section, elf_backend_merge_symbol, + elf_backend_hash_symbol, elf_backend_link_order_error_handler, elf_backend_relplt_name, ELF_MACHINE_ALT1, --- include/elf/common.h.jj 2006-02-17 15:36:26.000000000 +0100 +++ include/elf/common.h 2006-06-22 10:43:21.000000000 +0200 @@ -338,6 +338,7 @@ #define SHT_LOOS 0x60000000 /* First of OS specific semantics */ #define SHT_HIOS 0x6fffffff /* Last of OS specific semantics */ +#define SHT_GNU_HASH 0x6ffffff6 /* GNU style symbol hash table */ #define SHT_GNU_LIBLIST 0x6ffffff7 /* List of prelink dependencies */ /* The next three section types are defined by Solaris, and are named @@ -577,6 +578,7 @@ #define DT_VALRNGHI 0x6ffffdff #define DT_ADDRRNGLO 0x6ffffe00 +#define DT_GNU_HASH 0x6ffffef5 #define DT_TLSDESC_PLT 0x6ffffef6 #define DT_TLSDESC_GOT 0x6ffffef7 #define DT_GNU_CONFLICT 0x6ffffef8 --- include/bfdlink.h.jj 2006-04-07 17:17:29.000000000 +0200 +++ include/bfdlink.h 2006-06-22 11:11:20.000000000 +0200 @@ -324,6 +324,12 @@ struct bfd_link_info /* TRUE if unreferenced sections should be removed. */ unsigned int gc_sections: 1; + /* TRUE if .hash section should be created. */ + unsigned int emit_hash: 1; + + /* TRUE if .gnu.hash section should be created. */ + unsigned int emit_gnu_hash: 1; + /* What to do with unresolved symbols in an object file. When producing executables the default is GENERATE_ERROR. When producing shared libraries the default is IGNORE. The --- binutils/readelf.c.jj 2006-05-30 16:13:54.000000000 +0200 +++ binutils/readelf.c 2006-07-07 16:29:42.000000000 +0200 @@ -135,6 +135,7 @@ static unsigned long dynamic_syminfo_off static unsigned int dynamic_syminfo_nent; static char program_interpreter[64]; static bfd_vma dynamic_info[DT_JMPREL + 1]; +static bfd_vma dynamic_info_DT_GNU_HASH; static bfd_vma version_info[16]; static Elf_Internal_Ehdr elf_header; static Elf_Internal_Shdr *section_headers; @@ -1501,6 +1502,7 @@ get_dynamic_type (unsigned long type) case DT_GNU_CONFLICTSZ: return "GNU_CONFLICTSZ"; case DT_GNU_LIBLIST: return "GNU_LIBLIST"; case DT_GNU_LIBLISTSZ: return "GNU_LIBLISTSZ"; + case DT_GNU_HASH: return "GNU_HASH"; default: if ((type >= DT_LOPROC) && (type <= DT_HIPROC)) @@ -2571,6 +2573,7 @@ get_section_type_name (unsigned int sh_t case SHT_INIT_ARRAY: return "INIT_ARRAY"; case SHT_FINI_ARRAY: return "FINI_ARRAY"; case SHT_PREINIT_ARRAY: return "PREINIT_ARRAY"; + case SHT_GNU_HASH: return "GNU_HASH"; case SHT_GROUP: return "GROUP"; case SHT_SYMTAB_SHNDX: return "SYMTAB SECTION INDICIES"; case SHT_GNU_verdef: return "VERDEF"; @@ -6228,6 +6231,15 @@ process_dynamic_section (FILE *file) } break; + case DT_GNU_HASH: + dynamic_info_DT_GNU_HASH = entry->d_un.d_val; + if (do_dynamic) + { + print_vma (entry->d_un.d_val, PREFIX_HEX); + putchar ('\n'); + } + break; + default: if ((entry->d_tag >= DT_VERSYM) && (entry->d_tag <= DT_VERNEEDNUM)) version_info[DT_VERSIONTAGIDX (entry->d_tag)] = @@ -6903,6 +6915,9 @@ process_symbol_table (FILE *file) bfd_vma nchains = 0; bfd_vma *buckets = NULL; bfd_vma *chains = NULL; + bfd_vma ngnubuckets = 0; + bfd_vma *gnubuckets = NULL; + bfd_vma *gnuchains = NULL; if (! do_syms && !do_histogram) return 1; @@ -7282,6 +7297,167 @@ process_symbol_table (FILE *file) free (chains); } + if (do_histogram && dynamic_info_DT_GNU_HASH) + { + unsigned char nb[12]; + bfd_vma i, maxchain = 0xffffffff, symidx, bitmaskwords; + unsigned long *lengths; + unsigned long *counts; + unsigned long hn; + unsigned long maxlength = 0; + unsigned long nzero_counts = 0; + unsigned long nsyms = 0; + + if (fseek (file, + (archive_file_offset + + offset_from_vma (file, dynamic_info_DT_GNU_HASH, + sizeof nb)), + SEEK_SET)) + { + error (_("Unable to seek to start of dynamic information")); + return 0; + } + + if (fread (nb, 12, 1, file) != 1) + { + error (_("Failed to read in number of buckets\n")); + return 0; + } + + ngnubuckets = byte_get (nb, 4); + symidx = byte_get (nb + 4, 4); + bitmaskwords = byte_get (nb + 8, 4); + + if (fseek (file, + (archive_file_offset + + offset_from_vma (file, + dynamic_info_DT_GNU_HASH + + 4 * (3 + bitmaskwords), 4)), + SEEK_SET)) + { + error (_("Unable to seek to start of dynamic information")); + return 0; + } + + gnubuckets = get_dynamic_data (file, ngnubuckets, 4); + + if (gnubuckets == NULL) + return 0; + + for (i = 0; i < ngnubuckets; i++) + if (gnubuckets[i] != 0) + { + if (gnubuckets[i] < symidx) + return 0; + + if (maxchain == 0xffffffff || gnubuckets[i] > maxchain) + maxchain = gnubuckets[i]; + } + + if (maxchain == 0xffffffff) + return 0; + + maxchain -= symidx; + + if (fseek (file, + (archive_file_offset + + offset_from_vma (file, + dynamic_info_DT_GNU_HASH + + 4 * (3 + bitmaskwords + + ngnubuckets + maxchain), 4)), + SEEK_SET)) + { + error (_("Unable to seek to start of dynamic information")); + return 0; + } + + do + { + if (fread (nb, 4, 1, file) != 1) + { + error (_("Failed to determine last chain length\n")); + return 0; + } + + if (maxchain + 1 == 0) + return 0; + + ++maxchain; + } + while ((byte_get (nb, 4) & 1) == 0); + + if (fseek (file, + (archive_file_offset + + offset_from_vma (file, + dynamic_info_DT_GNU_HASH + + 4 * (3 + bitmaskwords + + ngnubuckets), 4)), + SEEK_SET)) + { + error (_("Unable to seek to start of dynamic information")); + return 0; + } + + gnuchains = get_dynamic_data (file, maxchain, 4); + + if (gnuchains == NULL) + return 0; + + lengths = calloc (ngnubuckets, sizeof (*lengths)); + if (lengths == NULL) + { + error (_("Out of memory")); + return 0; + } + + printf (_("\nHistogram for `.gnu.hash' bucket list length (total of %lu buckets):\n"), + (unsigned long) ngnubuckets); + printf (_(" Length Number %% of total Coverage\n")); + + for (hn = 0; hn < ngnubuckets; ++hn) + if (gnubuckets[hn] != 0) + { + bfd_vma off, length = 1; + + for (off = gnubuckets[hn] - symidx; + (gnuchains[off] & 1) == 0; ++off) + ++length; + lengths[hn] = length; + if (length > maxlength) + maxlength = length; + nsyms += length; + } + + counts = calloc (maxlength + 1, sizeof (*counts)); + if (counts == NULL) + { + error (_("Out of memory")); + return 0; + } + + for (hn = 0; hn < ngnubuckets; ++hn) + ++counts[lengths[hn]]; + + if (ngnubuckets > 0) + { + unsigned long j; + printf (" 0 %-10lu (%5.1f%%)\n", + counts[0], (counts[0] * 100.0) / ngnubuckets); + for (j = 1; j <= maxlength; ++j) + { + nzero_counts += counts[j] * j; + printf ("%7lu %-10lu (%5.1f%%) %5.1f%%\n", + j, counts[j], (counts[j] * 100.0) / ngnubuckets, + (nzero_counts * 100.0) / nsyms); + } + } + + free (counts); + free (lengths); + free (gnubuckets); + free (gnuchains); + } + return 1; } [-- Attachment #3: glibc-gnu-hash.patch --] [-- Type: text/plain, Size: 20423 bytes --] 2006-07-07 Ulrich Drepper <drepper@redhat.com> * elf/dl-lookup.c (dl_new_hash): New functions. (_dl_lookup_symbol_x): Rename hash to old_hash and don't compute value here. Compute new-style hash value. Pass new hash value and reference to variable with the old value to do_lookup_x. (_dl_setup_hash): If DT_GNU_HASH is defined, use it and not old-style hash table. (_dl_debug_bindings): Pass new hash value and reference to variable with the old value to do_lookup_x. * elf/do-lookup.h (do_lookup_x): Accept additional parameter with new-style hash value and change old-style hash value parameter to be a reference. Reoganize functions to determine whether new-style hash table is available. Only fall back on old-style table. If old-style hash value is needed, compute it here. * elf/dynamic-link.h (elf_get_dynamic_info): Relocate DT_GNU_HASH entry. * elf/elf.h: Define SHT_GNU_HASH, DT_GNU_HASH, DT_TLSDEC_PLT, DT_TLSDEC_GOT. Adjust DT_ADDRNUM. * include/link.h (struct link_map): Add l_gnu_buckets, l_gnu_chain_zero, l_gnu_bitmask and l_gnu_mask fields. * Makeconfig: If linker supports --hash-style option add it to all linker command lines to build DSOs. * config.make.in: Define have-hash-style. * configure.in: Test whether linker supports --hash-style option. --- libc/Makeconfig.~1.318.~ 2006-05-15 11:21:55.000000000 -0700 +++ libc/Makeconfig 2006-07-06 10:13:00.000000000 -0700 @@ -413,11 +413,20 @@ LDFLAGS.so += $(relro-LDFLAGS) LDFLAGS-rtld += $(relro-LDFLAGS) endif +ifeq (yes,$(have-hash-style)) +# For the time being we unconditionally use 'both'. At some time we +# should declare statically linked code as 'out of luck' and compile +# with --hash-style=gnu only. +hashstyle-LDFLAGS = -Wl,--hash-style=both +LDFLAGS.so += $(hashstyle-LDFLAGS) +LDFLAGS-rtld += $(hashstyle-LDFLAGS) +endif + # Command for linking programs with the C library. ifndef +link +link = $(CC) -nostdlib -nostartfiles -o $@ \ $(sysdep-LDFLAGS) $(config-LDFLAGS) $(LDFLAGS) $(LDFLAGS-$(@F)) \ - $(combreloc-LDFLAGS) $(relro-LDFLAGS) \ + $(combreloc-LDFLAGS) $(relro-LDFLAGS) $(hashstyle-LDFLAGS) \ $(addprefix $(csu-objpfx),$(start-installed-name)) \ $(+preinit) $(+prector) \ $(filter-out $(addprefix $(csu-objpfx),start.o \ --- libc/config.make.in.~1.118.~ 2006-04-26 08:17:41.000000000 -0700 +++ libc/config.make.in 2006-06-27 05:38:40.000000000 -0700 @@ -65,6 +65,7 @@ have-libcap = @have_libcap@ have-cc-with-libunwind = @libc_cv_cc_with_libunwind@ fno-unit-at-a-time = @fno_unit_at_a_time@ bind-now = @bindnow@ +have-hash-style = @libc_cv_hashstyle@ static-libgcc = @libc_cv_gcc_static_libgcc@ --- libc/configure.in.~1.460.~ 2006-04-26 08:19:22.000000000 -0700 +++ libc/configure.in 2006-06-26 13:47:01.000000000 -0700 @@ -1589,6 +1589,22 @@ EOF rm -f conftest*]) AC_SUBST(libc_cv_fpie) + + AC_CACHE_CHECK(for --hash-style option, + libc_cv_hashstyle, [dnl + cat > conftest.c <<EOF +int _start (void) { return 42; } +EOF + if AC_TRY_COMMAND([${CC-cc} $CFLAGS $CPPFLAGS $LDFLAGS + -fPIC -shared -o conftest.so conftest.c + -Wl,--hash-style=both -nostdlib 1>&AS_MESSAGE_LOG_FD]) + then + libc_cv_hashstyle=yes + else + libc_cv_hashstyle=no + fi + rm -f conftest*]) + AC_SUBST(libc_cv_hashstyle) fi AC_CACHE_CHECK(for -fno-toplevel-reorder, libc_cv_fno_toplevel_reorder, [dnl --- libc/elf/dynamic-link.h.jj 2006-03-17 08:55:20.000000000 +0100 +++ libc/elf/dynamic-link.h 2006-07-07 00:00:49.000000000 +0200 @@ -1,5 +1,5 @@ /* Inline functions for dynamic linking. - Copyright (C) 1995-2002, 2003, 2004, 2005 Free Software Foundation, Inc. + Copyright (C) 1995-2005, 2006 Free Software Foundation, Inc. This file is part of the GNU C Library. The GNU C Library is free software; you can redistribute it and/or @@ -143,6 +143,8 @@ elf_get_dynamic_info (struct link_map *l # endif ADJUST_DYN_INFO (DT_JMPREL); ADJUST_DYN_INFO (VERSYMIDX (DT_VERSYM)); + ADJUST_DYN_INFO (DT_ADDRTAGIDX (DT_GNU_HASH) + DT_NUM + DT_THISPROCNUM + + DT_VERSIONTAGNUM + DT_EXTRANUM + DT_VALNUM); # undef ADJUST_DYN_INFO assert (cnt <= DL_RO_DYN_TEMP_CNT); } --- libc/elf/elf.h.jj 2006-02-28 15:13:56.000000000 +0100 +++ libc/elf/elf.h 2006-07-07 00:00:49.000000000 +0200 @@ -329,7 +329,8 @@ typedef struct #define SHT_GROUP 17 /* Section group */ #define SHT_SYMTAB_SHNDX 18 /* Extended section indeces */ #define SHT_NUM 19 /* Number of defined types. */ -#define SHT_LOOS 0x60000000 /* Start OS-specific */ +#define SHT_LOOS 0x60000000 /* Start OS-specific. */ +#define SHT_GNU_HASH 0x6ffffff6 /* GNU-style hash table. */ #define SHT_GNU_LIBLIST 0x6ffffff7 /* Prelink library list */ #define SHT_CHECKSUM 0x6ffffff8 /* Checksum for DSO content. */ #define SHT_LOSUNW 0x6ffffffa /* Sun-specific low bound. */ @@ -699,6 +700,9 @@ typedef struct If any adjustment is made to the ELF object after it has been built these entries will need to be adjusted. */ #define DT_ADDRRNGLO 0x6ffffe00 +#define DT_GNU_HASH 0x6ffffef5 /* GNU-style hash table. */ +#define DT_TLSDESC_PLT 0x6ffffef6 +#define DT_TLSDESC_GOT 0x6ffffef7 #define DT_GNU_CONFLICT 0x6ffffef8 /* Start of conflict section */ #define DT_GNU_LIBLIST 0x6ffffef9 /* Library list */ #define DT_CONFIG 0x6ffffefa /* Configuration information. */ @@ -709,7 +713,7 @@ typedef struct #define DT_SYMINFO 0x6ffffeff /* Syminfo table. */ #define DT_ADDRRNGHI 0x6ffffeff #define DT_ADDRTAGIDX(tag) (DT_ADDRRNGHI - (tag)) /* Reverse order! */ -#define DT_ADDRNUM 10 +#define DT_ADDRNUM 11 /* The versioning entry types. The next are defined as part of the GNU extension. */ --- libc/elf/dl-lookup.c.jj 2005-12-27 11:56:45.000000000 +0100 +++ libc/elf/dl-lookup.c 2006-07-07 16:22:04.000000000 +0200 @@ -1,5 +1,5 @@ /* Look up a symbol in the loaded objects. - Copyright (C) 1995-2002, 2003, 2004, 2005 Free Software Foundation, Inc. + Copyright (C) 1995-2005, 2006 Free Software Foundation, Inc. This file is part of the GNU C Library. The GNU C Library is free software; you can redistribute it and/or @@ -72,6 +72,16 @@ struct sym_val #include "do-lookup.h" +static uint_fast32_t +dl_new_hash (const char *s) +{ + uint_fast32_t h = 5381; + for (unsigned char c = *s; c != '\0'; c = *++s) + h = h * 33 + c; + return h & 0xffffffff; +} + + /* Add extra dependency on MAP to UNDEF_MAP. */ static int internal_function @@ -206,7 +216,8 @@ _dl_lookup_symbol_x (const char *undef_n const struct r_found_version *version, int type_class, int flags, struct link_map *skip_map) { - const unsigned long int hash = _dl_elf_hash (undef_name); + const uint_fast32_t new_hash = dl_new_hash (undef_name); + unsigned long int old_hash = 0xffffffff; struct sym_val current_value = { NULL, NULL }; struct r_scope_elem **scope = symbol_scope; @@ -229,8 +240,9 @@ _dl_lookup_symbol_x (const char *undef_n /* Search the relevant loaded objects for a definition. */ for (size_t start = i; *scope != NULL; start = 0, ++scope) { - int res = do_lookup_x (undef_name, hash, *ref, ¤t_value, *scope, - start, version, flags, skip_map, type_class); + int res = do_lookup_x (undef_name, new_hash, &old_hash, *ref, + ¤t_value, *scope, start, version, flags, + skip_map, type_class); if (res > 0) break; @@ -301,9 +313,9 @@ _dl_lookup_symbol_x (const char *undef_n struct sym_val protected_value = { NULL, NULL }; for (scope = symbol_scope; *scope != NULL; i = 0, ++scope) - if (do_lookup_x (undef_name, hash, *ref, &protected_value, - *scope, i, version, flags, skip_map, - ELF_RTYPE_CLASS_PLT) != 0) + if (do_lookup_x (undef_name, new_hash, &old_hash, *ref, + &protected_value, *scope, i, version, flags, + skip_map, ELF_RTYPE_CLASS_PLT) != 0) break; if (protected_value.s != NULL && protected_value.m != undef_map) @@ -352,6 +364,26 @@ _dl_setup_hash (struct link_map *map) Elf_Symndx *hash; Elf_Symndx nchain; + if (__builtin_expect (map->l_info[DT_ADDRTAGIDX (DT_GNU_HASH) + DT_NUM + + DT_THISPROCNUM + DT_VERSIONTAGNUM + + DT_EXTRANUM + DT_VALNUM] != NULL, 1)) + { + Elf32_Word *hash32 + = (void *) D_PTR (map, l_info[DT_ADDRTAGIDX (DT_GNU_HASH) + DT_NUM + + DT_THISPROCNUM + DT_VERSIONTAGNUM + + DT_EXTRANUM + DT_VALNUM]); + map->l_nbuckets = *hash32++; + Elf32_Word symbias = *hash32++; + Elf32_Word maskwords = *hash32++; + map->l_gnu_bitmask = hash32; + hash32 += maskwords; + map->l_gnu_buckets = hash32; + hash32 += map->l_nbuckets; + map->l_gnu_chain_zero = hash32 - symbias; + map->l_gnu_mask = maskwords - 1; + return; + } + if (!map->l_info[DT_HASH]) return; hash = (void *) D_PTR (map, l_info[DT_HASH]); @@ -399,9 +431,10 @@ _dl_debug_bindings (const char *undef_na || GLRO(dl_trace_prelink_map) == GL(dl_ns)[LM_ID_BASE]._ns_loaded) && undef_map != GL(dl_ns)[LM_ID_BASE]._ns_loaded) { - const unsigned long int hash = _dl_elf_hash (undef_name); + const uint_fast32_t new_hash = dl_new_hash (undef_name); + unsigned long int old_hash = 0xffffffff; - do_lookup_x (undef_name, hash, *ref, &val, + do_lookup_x (undef_name, new_hash, &old_hash, *ref, &val, undef_map->l_local_scope[0], 0, version, 0, NULL, type_class); --- libc/elf/do-lookup.h.jj 2006-02-28 15:13:56.000000000 +0100 +++ libc/elf/do-lookup.h 2006-07-07 16:24:19.000000000 +0200 @@ -17,32 +17,29 @@ Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. */ + /* Inner part of the lookup functions. We return a value > 0 if we found the symbol, the value 0 if nothing is found and < 0 if something bad happened. */ static int __attribute_noinline__ -do_lookup_x (const char *undef_name, unsigned long int hash, - const ElfW(Sym) *ref, struct sym_val *result, - struct r_scope_elem *scope, size_t i, +do_lookup_x (const char *undef_name, uint_fast32_t new_hash, + unsigned long int *old_hash, const ElfW(Sym) *ref, + struct sym_val *result, struct r_scope_elem *scope, size_t i, const struct r_found_version *const version, int flags, struct link_map *skip, int type_class) { struct link_map **list = scope->r_list; size_t n = scope->r_nlist; - struct link_map *map; do { - const ElfW(Sym) *symtab; - const char *strtab; - const ElfW(Half) *verstab; + /* These variables are used in the nested function. */ Elf_Symndx symidx; - const ElfW(Sym) *sym; int num_versions = 0; const ElfW(Sym) *versioned_sym = NULL; - map = list[i]->l_real; + struct link_map *map = list[i]->l_real; /* Here come the extra test needed for `_dl_lookup_symbol_skip'. */ if (map == skip) @@ -63,109 +60,143 @@ do_lookup_x (const char *undef_name, uns map->l_name[0] ? map->l_name : rtld_progname, map->l_ns); - symtab = (const void *) D_PTR (map, l_info[DT_SYMTAB]); - strtab = (const void *) D_PTR (map, l_info[DT_STRTAB]); - verstab = map->l_versyms; - - /* Search the appropriate hash bucket in this object's symbol table - for a definition for the same symbol name. */ - for (symidx = map->l_buckets[hash % map->l_nbuckets]; - symidx != STN_UNDEF; - symidx = map->l_chain[symidx]) - { - sym = &symtab[symidx]; - - assert (ELF_RTYPE_CLASS_PLT == 1); - if ((sym->st_value == 0 /* No value. */ -#ifdef USE_TLS - && ELFW(ST_TYPE) (sym->st_info) != STT_TLS -#endif - ) - || (type_class & (sym->st_shndx == SHN_UNDEF))) - continue; - - if (ELFW(ST_TYPE) (sym->st_info) > STT_FUNC -#ifdef USE_TLS - && ELFW(ST_TYPE) (sym->st_info) != STT_TLS -#endif - ) - /* Ignore all but STT_NOTYPE, STT_OBJECT and STT_FUNC - entries (and STT_TLS if TLS is supported) since these - are no code/data definitions. */ - continue; - - if (sym != ref && strcmp (strtab + sym->st_name, undef_name)) - /* Not the symbol we are looking for. */ - continue; + /* The tables for this map. */ + const ElfW(Sym) *symtab = (const void *) D_PTR (map, l_info[DT_SYMTAB]); + const char *strtab = (const void *) D_PTR (map, l_info[DT_STRTAB]); + const ElfW(Half) *verstab = map->l_versyms; + + /* Nested routine to check whether the symbol matches. */ + const ElfW(Sym) * + __attribute_noinline__ + check_match (const ElfW(Sym) *sym) + { + assert (ELF_RTYPE_CLASS_PLT == 1); + if (__builtin_expect ((sym->st_value == 0 /* No value. */ + && ELFW(ST_TYPE) (sym->st_info) != STT_TLS) + || (type_class & (sym->st_shndx == SHN_UNDEF)), + 0)) + return NULL; + + if (__builtin_expect (ELFW(ST_TYPE) (sym->st_info) > STT_FUNC + && ELFW(ST_TYPE) (sym->st_info) != STT_TLS, 0)) + /* Ignore all but STT_NOTYPE, STT_OBJECT and STT_FUNC + entries (and STT_TLS if TLS is supported) since these + are no code/data definitions. */ + return NULL; + + if (sym != ref && strcmp (strtab + sym->st_name, undef_name)) + /* Not the symbol we are looking for. */ + return NULL; + + if (version != NULL) + { + if (__builtin_expect (verstab == NULL, 0)) + { + /* We need a versioned symbol but haven't found any. If + this is the object which is referenced in the verneed + entry it is a bug in the library since a symbol must + not simply disappear. + + It would also be a bug in the object since it means that + the list of required versions is incomplete and so the + tests in dl-version.c haven't found a problem.*/ + assert (version->filename == NULL + || ! _dl_name_match_p (version->filename, map)); + + /* Otherwise we accept the symbol. */ + } + else + { + /* We can match the version information or use the + default one if it is not hidden. */ + ElfW(Half) ndx = verstab[symidx] & 0x7fff; + if ((map->l_versions[ndx].hash != version->hash + || strcmp (map->l_versions[ndx].name, version->name)) + && (version->hidden || map->l_versions[ndx].hash + || (verstab[symidx] & 0x8000))) + /* It's not the version we want. */ + return NULL; + } + } + else + { + /* No specific version is selected. There are two ways we + can got here: + + - a binary which does not include versioning information + is loaded + + - dlsym() instead of dlvsym() is used to get a symbol which + might exist in more than one form + + If the library does not provide symbol version information + there is no problem at at: we simply use the symbol if it + is defined. + + These two lookups need to be handled differently if the + library defines versions. In the case of the old + unversioned application the oldest (default) version + should be used. In case of a dlsym() call the latest and + public interface should be returned. */ + if (verstab != NULL) + { + if ((verstab[symidx] & 0x7fff) + >= ((flags & DL_LOOKUP_RETURN_NEWEST) ? 2 : 3)) + { + /* Don't accept hidden symbols. */ + if ((verstab[symidx] & 0x8000) == 0 + && num_versions++ == 0) + /* No version so far. */ + versioned_sym = sym; + + return NULL; + } + } + } + + /* There cannot be another entry for this symbol so stop here. */ + return sym; + } - if (version != NULL) + const ElfW(Sym) *sym; + if (__builtin_expect (map->l_gnu_buckets != NULL, 1)) + { + if ((map->l_gnu_bitmask[(new_hash >> 5) & map->l_gnu_mask] + & (1 << (new_hash & 31))) != 0) { - if (__builtin_expect (verstab == NULL, 0)) + Elf32_Word chainoff = map->l_gnu_buckets[new_hash % map->l_nbuckets]; + if (chainoff != 0xffffffff) { - /* We need a versioned symbol but haven't found any. If - this is the object which is referenced in the verneed - entry it is a bug in the library since a symbol must - not simply disappear. - - It would also be a bug in the object since it means that - the list of required versions is incomplete and so the - tests in dl-version.c haven't found a problem.*/ - assert (version->filename == NULL - || ! _dl_name_match_p (version->filename, map)); + const Elf32_Word *hasharr = &map->l_gnu_chain_zero[chainoff]; - /* Otherwise we accept the symbol. */ - } - else - { - /* We can match the version information or use the - default one if it is not hidden. */ - ElfW(Half) ndx = verstab[symidx] & 0x7fff; - if ((map->l_versions[ndx].hash != version->hash - || strcmp (map->l_versions[ndx].name, version->name)) - && (version->hidden || map->l_versions[ndx].hash - || (verstab[symidx] & 0x8000))) - /* It's not the version we want. */ - continue; + do + if ((*hasharr & ~1u) == (new_hash & ~1u)) + { + symidx = hasharr - map->l_gnu_chain_zero; + sym = check_match (&symtab[symidx]); + if (sym != NULL) + goto found_it; + } + while ((*hasharr++ & 1u) == 0); } } - else - { - /* No specific version is selected. There are two ways we - can got here: - - - a binary which does not include versioning information - is loaded - - - dlsym() instead of dlvsym() is used to get a symbol which - might exist in more than one form - - If the library does not provide symbol version - information there is no problem at at: we simply use the - symbol if it is defined. - - These two lookups need to be handled differently if the - library defines versions. In the case of the old - unversioned application the oldest (default) version - should be used. In case of a dlsym() call the latest and - public interface should be returned. */ - if (verstab != NULL) - { - if ((verstab[symidx] & 0x7fff) - >= ((flags & DL_LOOKUP_RETURN_NEWEST) ? 2 : 3)) - { - /* Don't accept hidden symbols. */ - if ((verstab[symidx] & 0x8000) == 0 - && num_versions++ == 0) - /* No version so far. */ - versioned_sym = sym; + } + else + { + if (*old_hash == 0xffffffff) + *old_hash = _dl_elf_hash (undef_name); - continue; - } - } + /* Use the old SysV-style hash table. Search the appropriate + hash bucket in this object's symbol table for a definition + for the same symbol name. */ + for (symidx = map->l_buckets[*old_hash % map->l_nbuckets]; + symidx != STN_UNDEF; + symidx = map->l_chain[symidx]) + { + sym = check_match (&symtab[symidx]); + if (sym != NULL) + goto found_it; } - - /* There cannot be another entry for this symbol so stop here. */ - goto found_it; } /* If we have seen exactly one versioned symbol while we are @@ -213,7 +244,3 @@ do_lookup_x (const char *undef_name, uns /* We have not found anything until now. */ return 0; } - -#undef FCT -#undef ARG -#undef VERSIONED --- libc/include/link.h.jj 2006-03-03 14:31:38.000000000 +0100 +++ libc/include/link.h 2006-07-07 00:03:13.000000000 +0200 @@ -124,7 +124,7 @@ struct link_map const ElfW(Phdr) *l_phdr; /* Pointer to program header table in core. */ ElfW(Addr) l_entry; /* Entry point location. */ ElfW(Half) l_phnum; /* Number of program header entries. */ - ElfW(Half) l_ldnum; /* Number of dynamic segment entries. */ + ElfW(Half) l_ldnum; /* Number of dynamic segment entries. */ /* Array of DT_NEEDED dependencies and their dependencies, in dependency order for symbol lookup (with and without @@ -141,7 +141,18 @@ struct link_map /* Symbol hash table. */ Elf_Symndx l_nbuckets; - const Elf_Symndx *l_buckets, *l_chain; + const Elf32_Word *l_gnu_buckets; + union + { + const Elf32_Word *l_gnu_chain_zero; + const Elf_Symndx *l_chain; + }; + union + { + const Elf32_Word *l_gnu_bitmask; + const Elf_Symndx *l_buckets; + }; + Elf32_Word l_gnu_mask; unsigned int l_direct_opencount; /* Reference count for dlopen/dlclose. */ enum /* Where this object came from. */ [-- Attachment #4: statsn --] [-- Type: text/plain, Size: 14597 bytes --] cat > a.c <<\EOF cat /tmp/a.c #include <dlfcn.h> const char *libs[] = { "libvclplug_gtk680lx.so", "libvclplug_gen680lx.so", "libnss_files.so.2", "libGL.so.1", "servicemgr.uno.so", "shlibloader.uno.so", "simplereg.uno.so", "nestedreg.uno.so", "typemgr.uno.so", "implreg.uno.so", "security.uno.so", "libreg.so.3", "libstore.so.3", "regtypeprov.uno.so", "configmgr2.uno.so", "typeconverter.uno.so", "gconfbe1.uno.so", "behelper.uno.so", "sax.uno.so", "localebe1.uno.so", "uriproc.uno.so", "libspl680lx.so", "libucb1.so", "ucpgvfs1.uno.so", "libgcc3_uno.so", "libpackage2.so", "libfileacc.so", "libuui680lx.so", "libfilterconfig1.so", "libdtransX11680lx.so", "i18npool.uno.so", "liblocaledata_en.so", "fsstorage.uno.so", "libxstor.so", "libdbtools680lx.so", "libcups.so.2", "libgnutls.so.13", "libgcrypt.so.11", "libgpg-error.so.0", "libmcnttype.so", "libucpchelp1.so", "svtmisc.uno.so" }; int main (int argc, char **argv) { int i; void *h; int flags = RTLD_LAZY; if (argv[1][0] == 'g') flags |= RTLD_GLOBAL; for (i = 0; i < sizeof (libs) / sizeof (libs[0]); ++i) h = dlopen (libs[i], flags); return 0; } EOF gcc -g -O2 -o a a.c -Wl,-rpath,/usr/lib64/openoffice.org2.0/program/ \ -L/usr/lib64/openoffice.org2.0/program/ -lsoffice -lsw680lx -lsvx680lx -lstdc++ -lm -shared-libgcc for V in local global; do for M in '' 'export LD_X=1' 'export LD_BIND_NOW=1' 'export LD_X=1 LD_BIND_NOW=1'; \ do ( for i in 1 2 3 4; do eval $M; time ./a $V; done 2>&1 > /dev/null | \ awk 'BEGIN { printf "'"$V $M"'\t" } /^real/ { printf "%s ", $2 } END { printf "\n" }' ); done; done take4 local 0m0.180s 0m0.175s 0m0.174s 0m0.174s local export LD_X=1 0m0.591s 0m0.593s 0m0.593s 0m0.603s local export LD_BIND_NOW=1 0m0.306s 0m0.303s 0m0.309s 0m0.303s local export LD_X=1 LD_BIND_NOW=1 0m1.186s 0m1.188s 0m1.146s 0m1.149s global 0m0.203s 0m0.198s 0m0.201s 0m0.198s global export LD_X=1 0m0.669s 0m0.686s 0m0.673s 0m0.672s global export LD_BIND_NOW=1 0m0.354s 0m0.349s 0m0.347s 0m0.348s global export LD_X=1 LD_BIND_NOW=1 0m1.334s 0m1.347s 0m1.356s 0m1.379s for V in local global; do for M in '' 'export LD_X=1' 'export LD_BIND_NOW=1' 'export LD_X=1 LD_BIND_NOW=1'; \ do ( echo "$V $M"; eval $M; valgrind --tool=cachegrind ./a $V 2>&1 > /dev/null | sed -n '/== I refs/,$p' ); \ done; done take4 local ==22333== I refs: 201,078,072 ==22333== I1 misses: 11,304 ==22333== L2i misses: 9,911 ==22333== I1 miss rate: 0.00% ==22333== L2i miss rate: 0.00% ==22333== ==22333== D refs: 74,797,589 (58,315,275 rd + 16,482,314 wr) ==22333== D1 misses: 3,404,397 ( 3,256,012 rd + 148,385 wr) ==22333== L2d misses: 489,312 ( 398,103 rd + 91,209 wr) ==22333== D1 miss rate: 4.5% ( 5.5% + 0.9% ) ==22333== L2d miss rate: 0.6% ( 0.6% + 0.5% ) ==22333== ==22333== L2 refs: 3,415,701 ( 3,267,316 rd + 148,385 wr) ==22333== L2 misses: 499,223 ( 408,014 rd + 91,209 wr) ==22333== L2 miss rate: 0.1% ( 0.1% + 0.5% ) local export LD_X=1 ==22337== I refs: 311,492,449 ==22337== I1 misses: 11,299 ==22337== L2i misses: 10,321 ==22337== I1 miss rate: 0.00% ==22337== L2i miss rate: 0.00% ==22337== ==22337== D refs: 128,005,658 (98,076,224 rd + 29,929,434 wr) ==22337== D1 misses: 9,559,670 ( 9,395,598 rd + 164,072 wr) ==22337== L2d misses: 3,022,405 ( 2,916,644 rd + 105,761 wr) ==22337== D1 miss rate: 7.4% ( 9.5% + 0.5% ) ==22337== L2d miss rate: 2.3% ( 2.9% + 0.3% ) ==22337== ==22337== L2 refs: 9,570,969 ( 9,406,897 rd + 164,072 wr) ==22337== L2 misses: 3,032,726 ( 2,926,965 rd + 105,761 wr) ==22337== L2 miss rate: 0.6% ( 0.7% + 0.3% ) local export LD_BIND_NOW=1 ==22341== I refs: 389,236,554 ==22341== I1 misses: 10,837 ==22341== L2i misses: 9,717 ==22341== I1 miss rate: 0.00% ==22341== L2i miss rate: 0.00% ==22341== ==22341== D refs: 148,524,589 (115,298,089 rd + 33,226,500 wr) ==22341== D1 misses: 6,929,319 ( 6,754,195 rd + 175,124 wr) ==22341== L2d misses: 657,766 ( 559,064 rd + 98,702 wr) ==22341== D1 miss rate: 4.6% ( 5.8% + 0.5% ) ==22341== L2d miss rate: 0.4% ( 0.4% + 0.2% ) ==22341== ==22341== L2 refs: 6,940,156 ( 6,765,032 rd + 175,124 wr) ==22341== L2 misses: 667,483 ( 568,781 rd + 98,702 wr) ==22341== L2 miss rate: 0.1% ( 0.1% + 0.2% ) local export LD_X=1 LD_BIND_NOW=1 ==22345== I refs: 622,558,758 ==22345== I1 misses: 10,829 ==22345== L2i misses: 9,927 ==22345== I1 miss rate: 0.00% ==22345== L2i miss rate: 0.00% ==22345== ==22345== D refs: 262,006,683 (199,686,725 rd + 62,319,958 wr) ==22345== D1 misses: 20,358,555 ( 20,138,179 rd + 220,376 wr) ==22345== L2d misses: 6,288,581 ( 6,175,041 rd + 113,540 wr) ==22345== D1 miss rate: 7.7% ( 10.0% + 0.3% ) ==22345== L2d miss rate: 2.4% ( 3.0% + 0.1% ) ==22345== ==22345== L2 refs: 20,369,384 ( 20,149,008 rd + 220,376 wr) ==22345== L2 misses: 6,298,508 ( 6,184,968 rd + 113,540 wr) ==22345== L2 miss rate: 0.7% ( 0.7% + 0.1% ) global ==22349== I refs: 216,049,983 ==22349== I1 misses: 11,443 ==22349== L2i misses: 10,043 ==22349== I1 miss rate: 0.00% ==22349== L2i miss rate: 0.00% ==22349== ==22349== D refs: 82,419,601 (64,203,003 rd + 18,216,598 wr) ==22349== D1 misses: 5,154,627 ( 5,004,907 rd + 149,720 wr) ==22349== L2d misses: 500,196 ( 408,675 rd + 91,521 wr) ==22349== D1 miss rate: 6.2% ( 7.7% + 0.8% ) ==22349== L2d miss rate: 0.6% ( 0.6% + 0.5% ) ==22349== ==22349== L2 refs: 5,166,070 ( 5,016,350 rd + 149,720 wr) ==22349== L2 misses: 510,239 ( 418,718 rd + 91,521 wr) ==22349== L2 miss rate: 0.1% ( 0.1% + 0.5% ) global export LD_X=1 ==22353== I refs: 337,282,635 ==22353== I1 misses: 11,425 ==22353== L2i misses: 10,469 ==22353== I1 miss rate: 0.00% ==22353== L2i miss rate: 0.00% ==22353== ==22353== D refs: 141,116,515 (107,952,083 rd + 33,164,432 wr) ==22353== D1 misses: 12,018,123 ( 11,852,619 rd + 165,504 wr) ==22353== L2d misses: 3,503,191 ( 3,396,933 rd + 106,258 wr) ==22353== D1 miss rate: 8.5% ( 10.9% + 0.4% ) ==22353== L2d miss rate: 2.4% ( 3.1% + 0.3% ) ==22353== ==22353== L2 refs: 12,029,548 ( 11,864,044 rd + 165,504 wr) ==22353== L2 misses: 3,513,660 ( 3,407,402 rd + 106,258 wr) ==22353== L2 miss rate: 0.7% ( 0.7% + 0.3% ) global export LD_BIND_NOW=1 ==22359== I refs: 416,388,279 ==22359== I1 misses: 10,963 ==22359== L2i misses: 9,841 ==22359== I1 miss rate: 0.00% ==22359== L2i miss rate: 0.00% ==22359== ==22359== D refs: 162,316,098 (125,953,786 rd + 36,362,312 wr) ==22359== D1 misses: 10,111,441 ( 9,932,496 rd + 178,945 wr) ==22359== L2d misses: 675,000 ( 575,984 rd + 99,016 wr) ==22359== D1 miss rate: 6.2% ( 7.8% + 0.4% ) ==22359== L2d miss rate: 0.4% ( 0.4% + 0.2% ) ==22359== ==22359== L2 refs: 10,122,404 ( 9,943,459 rd + 178,945 wr) ==22359== L2 misses: 684,841 ( 585,825 rd + 99,016 wr) ==22359== L2 miss rate: 0.1% ( 0.1% + 0.2% ) global export LD_X=1 LD_BIND_NOW=1 ==22363== I refs: 668,842,809 ==22363== I1 misses: 10,942 ==22363== L2i misses: 10,052 ==22363== I1 miss rate: 0.00% ==22363== L2i miss rate: 0.00% ==22363== ==22363== D refs: 285,593,622 (217,433,359 rd + 68,160,263 wr) ==22363== D1 misses: 24,793,665 ( 24,570,244 rd + 223,421 wr) ==22363== L2d misses: 7,189,812 ( 7,075,786 rd + 114,026 wr) ==22363== D1 miss rate: 8.6% ( 11.3% + 0.3% ) ==22363== L2d miss rate: 2.5% ( 3.2% + 0.1% ) ==22363== ==22363== L2 refs: 24,804,607 ( 24,581,186 rd + 223,421 wr) ==22363== L2 misses: 7,199,864 ( 7,085,838 rd + 114,026 wr) ==22363== L2 miss rate: 0.7% ( 0.7% + 0.1% ) for V in local global; do for M in '' '-E LD_X=1' '-E LD_BIND_NOW=1' '-E LD_X=1 -E LD_BIND_NOW=1'; \ do ( echo "$V $M"; ./timing $M ./a $V ); done; done take4 local Strip out best and worst realtime result minimum: 0.171330000 sec real / 0.000059879 sec CPU maximum: 0.183637000 sec real / 0.000140912 sec CPU average: 0.173522535 sec real / 0.000065315 sec CPU stdev : 0.000694442 sec real / 0.000000770 sec CPU local -E LD_X=1 optarg="LD_X=1" Strip out best and worst realtime result minimum: 0.575774000 sec real / 0.000053405 sec CPU maximum: 0.595938000 sec real / 0.000079537 sec CPU average: 0.587580821 sec real / 0.000075442 sec CPU stdev : 0.004159043 sec real / 0.000001989 sec CPU local -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.299670000 sec real / 0.000055573 sec CPU maximum: 0.306395000 sec real / 0.000086738 sec CPU average: 0.302749821 sec real / 0.000073164 sec CPU stdev : 0.001761517 sec real / 0.000003183 sec CPU local -E LD_X=1 -E LD_BIND_NOW=1 optarg="LD_X=1" optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 1.162265000 sec real / 0.000055101 sec CPU maximum: 1.209383000 sec real / 0.000073149 sec CPU average: 1.189671071 sec real / 0.000065435 sec CPU stdev : 0.007947359 sec real / 0.000000731 sec CPU global Strip out best and worst realtime result minimum: 0.195825000 sec real / 0.000064238 sec CPU maximum: 0.198755000 sec real / 0.000069930 sec CPU average: 0.197095571 sec real / 0.000065329 sec CPU stdev : 0.000657043 sec real / 0.000000924 sec CPU global -E LD_X=1 optarg="LD_X=1" Strip out best and worst realtime result minimum: 0.658855000 sec real / 0.000052899 sec CPU maximum: 0.693884000 sec real / 0.000084485 sec CPU average: 0.676305857 sec real / 0.000076110 sec CPU stdev : 0.004805411 sec real / 0.000003079 sec CPU global -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.342948000 sec real / 0.000054621 sec CPU maximum: 0.353243000 sec real / 0.000080357 sec CPU average: 0.347779142 sec real / 0.000073702 sec CPU stdev : 0.002035106 sec real / 0.000003696 sec CPU global -E LD_X=1 -E LD_BIND_NOW=1 optarg="LD_X=1" optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 1.314006000 sec real / 0.000053499 sec CPU maximum: 1.400049000 sec real / 0.000070065 sec CPU average: 1.346385214 sec real / 0.000065079 sec CPU stdev : 0.012294494 sec real / 0.000000950 sec CPU /usr/sbin/prelink -vmR ./a for V in local global; do for M in '' 'export LD_X=1' 'export LD_BIND_NOW=1' 'export LD_X=1 LD_BIND_NOW=1'; \ do ( for i in 1 2 3 4; do eval $M; time ./a $V; done 2>&1 > /dev/null | \ awk 'BEGIN { printf "'"$V $M"'\t" } /^real/ { printf "%s ", $2 } END { printf "\n" }' ); done; done take4 local 0m0.110s 0m0.090s 0m0.090s 0m0.089s local export LD_X=1 0m0.287s 0m0.279s 0m0.285s 0m0.277s local export LD_BIND_NOW=1 0m0.147s 0m0.145s 0m0.143s 0m0.143s local export LD_X=1 LD_BIND_NOW=1 0m0.547s 0m0.535s 0m0.533s 0m0.527s global 0m0.115s 0m0.112s 0m0.113s 0m0.113s global export LD_X=1 0m0.368s 0m0.374s 0m0.360s 0m0.356s global export LD_BIND_NOW=1 0m0.187s 0m0.185s 0m0.185s 0m0.185s global export LD_X=1 LD_BIND_NOW=1 0m0.686s 0m0.690s 0m0.667s 0m0.666s # valgrind --tool=cachegrind stats not provided for prelinked testcase, # as valgrind apparently uses LD_PRELOAD internally and thus prevents # prelinking. for V in local global; do for M in '' '-E LD_X=1' '-E LD_BIND_NOW=1' '-E LD_X=1 -E LD_BIND_NOW=1'; \ do ( echo "$V $M"; ./timing $M ./a $V ); done; done take4 local Strip out best and worst realtime result minimum: 0.088558000 sec real / 0.000062737 sec CPU maximum: 0.090857000 sec real / 0.000075048 sec CPU average: 0.089202000 sec real / 0.000064855 sec CPU stdev : 0.000453942 sec real / 0.000002985 sec CPU local -E LD_X=1 optarg="LD_X=1" Strip out best and worst realtime result minimum: 0.274995000 sec real / 0.000055459 sec CPU maximum: 0.291724000 sec real / 0.000085829 sec CPU average: 0.285347750 sec real / 0.000073140 sec CPU stdev : 0.004344181 sec real / 0.000003294 sec CPU local -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.142244000 sec real / 0.000052852 sec CPU maximum: 0.145730000 sec real / 0.000074901 sec CPU average: 0.143050857 sec real / 0.000063817 sec CPU stdev : 0.000588257 sec real / 0.000000572 sec CPU local -E LD_X=1 -E LD_BIND_NOW=1 optarg="LD_X=1" optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.516412000 sec real / 0.000052547 sec CPU maximum: 0.551295000 sec real / 0.000080505 sec CPU average: 0.536137714 sec real / 0.000072925 sec CPU stdev : 0.008204213 sec real / 0.000003287 sec CPU global Strip out best and worst realtime result minimum: 0.111122000 sec real / 0.000057277 sec CPU maximum: 0.113199000 sec real / 0.000072477 sec CPU average: 0.111739535 sec real / 0.000063569 sec CPU stdev : 0.000365911 sec real / 0.000002389 sec CPU global -E LD_X=1 optarg="LD_X=1" Strip out best and worst realtime result minimum: 0.356423000 sec real / 0.000054153 sec CPU maximum: 0.385610000 sec real / 0.000077109 sec CPU average: 0.369770464 sec real / 0.000072567 sec CPU stdev : 0.005942862 sec real / 0.000003175 sec CPU global -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.182965000 sec real / 0.000054313 sec CPU maximum: 0.189492000 sec real / 0.000068199 sec CPU average: 0.184005428 sec real / 0.000063653 sec CPU stdev : 0.000723054 sec real / 0.000001477 sec CPU global -E LD_X=1 -E LD_BIND_NOW=1 optarg="LD_X=1" optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.650583000 sec real / 0.000052562 sec CPU maximum: 0.700625000 sec real / 0.000077906 sec CPU average: 0.680901214 sec real / 0.000073774 sec CPU stdev : 0.011186022 sec real / 0.000002110 sec CPU [-- Attachment #5: statsx --] [-- Type: text/plain, Size: 6251 bytes --] cat > n.c <<\EOF #include <stdlib.h> #include <dlfcn.h> const char *libs[] = { "libvclplug_gtk680lx.so", "libvclplug_gen680lx.so", "libnss_files.so.2", "libGL.so.1", "servicemgr.uno.so", "shlibloader.uno.so", "simplereg.uno.so", "nestedreg.uno.so", "typemgr.uno.so", "implreg.uno.so", "security.uno.so", "libreg.so.3", "libstore.so.3", "regtypeprov.uno.so", "configmgr2.uno.so", "typeconverter.uno.so", "gconfbe1.uno.so", "behelper.uno.so", "sax.uno.so", "localebe1.uno.so", "uriproc.uno.so", "libspl680lx.so", "libucb1.so", "ucpgvfs1.uno.so", "libgcc3_uno.so", "libpackage2.so", "libfileacc.so", "libuui680lx.so", "libfilterconfig1.so", "libdtransX11680lx.so", "i18npool.uno.so", "liblocaledata_en.so", "fsstorage.uno.so", "libxstor.so", "libdbtools680lx.so", "libcups.so.2", "libgnutls.so.13", "libgcrypt.so.11", "libgpg-error.so.0", "libmcnttype.so", "libucpchelp1.so", "svtmisc.uno.so" }; int __attribute__((noinline)) evict_cache (long *array, size_t count) { size_t i; int ret = 0; for (i = 0; i < count; i++) array[i] = i + 1; for (i = 0; i < count; i++) ret += array[i]; return ret; } int main (int argc, char **argv) { int i; void *h; /* Adjust for your L2 cache, mine is 1MB. */ long *array = malloc (256 * 1024 * sizeof (long)); int flags = RTLD_LAZY; if (argv[1][0] == 'g') flags |= RTLD_GLOBAL; for (i = 0; i < sizeof (libs) / sizeof (libs[0]); ++i) { evict_cache (array, 256 * 1024); h = dlopen (libs[i], flags); } return 0; } EOF gcc -g -O2 -o n n.c -Wl,-rpath,/usr/lib64/openoffice.org2.0/program/ \ -L/usr/lib64/openoffice.org2.0/program/ -lsoffice -lsw680lx -lsvx680lx -lstdc++ -lm -shared-libgcc /usr/sbin/prelink -vmR ./n for V in local global; do for M in '' '-E LD_BIND_NOW=1'; do ( echo "$V $M"; ./timing $M ./n $V ); done; done take1 local Strip out best and worst realtime result minimum: 0.252598000 sec real / 0.000068125 sec CPU maximum: 0.255268000 sec real / 0.000084226 sec CPU average: 0.253643142 sec real / 0.000075407 sec CPU stdev : 0.000641286 sec real / 0.000002025 sec CPU local -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.355105000 sec real / 0.000056627 sec CPU maximum: 0.391689000 sec real / 0.000080369 sec CPU average: 0.357542464 sec real / 0.000074811 sec CPU stdev : 0.003493931 sec real / 0.000002581 sec CPU global Strip out best and worst realtime result minimum: 0.289823000 sec real / 0.000065591 sec CPU maximum: 0.292342000 sec real / 0.000089039 sec CPU average: 0.291038785 sec real / 0.000074941 sec CPU stdev : 0.000540335 sec real / 0.000003253 sec CPU global -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.422357000 sec real / 0.000056080 sec CPU maximum: 0.430025000 sec real / 0.000092561 sec CPU average: 0.424305678 sec real / 0.000076960 sec CPU stdev : 0.000848422 sec real / 0.000003468 sec CPU take2 local Strip out best and worst realtime result minimum: 0.244879000 sec real / 0.000062648 sec CPU maximum: 0.249994000 sec real / 0.000088941 sec CPU average: 0.246728928 sec real / 0.000071952 sec CPU stdev : 0.000634173 sec real / 0.000003605 sec CPU local -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.341390000 sec real / 0.000051786 sec CPU maximum: 0.346805000 sec real / 0.000076650 sec CPU average: 0.343283357 sec real / 0.000072815 sec CPU stdev : 0.001045857 sec real / 0.000002876 sec CPU global Strip out best and worst realtime result minimum: 0.280108000 sec real / 0.000064175 sec CPU maximum: 0.288343000 sec real / 0.000086420 sec CPU average: 0.281190142 sec real / 0.000073883 sec CPU stdev : 0.000946847 sec real / 0.000002963 sec CPU global -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.404168000 sec real / 0.000047867 sec CPU maximum: 0.409607000 sec real / 0.000089063 sec CPU average: 0.406042035 sec real / 0.000073105 sec CPU stdev : 0.001200557 sec real / 0.000002313 sec CPU take3 local Strip out best and worst realtime result minimum: 0.219594000 sec real / 0.000063193 sec CPU maximum: 0.221967000 sec real / 0.000069838 sec CPU average: 0.220638857 sec real / 0.000065311 sec CPU stdev : 0.000659280 sec real / 0.000001556 sec CPU local -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.292865000 sec real / 0.000052557 sec CPU maximum: 0.297813000 sec real / 0.000088007 sec CPU average: 0.294272428 sec real / 0.000073999 sec CPU stdev : 0.000734011 sec real / 0.000003457 sec CPU global Strip out best and worst realtime result minimum: 0.248331000 sec real / 0.000065781 sec CPU maximum: 0.251560000 sec real / 0.000083441 sec CPU average: 0.249498928 sec real / 0.000074084 sec CPU stdev : 0.000521804 sec real / 0.000002443 sec CPU global -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.344976000 sec real / 0.000050839 sec CPU maximum: 0.350706000 sec real / 0.000086602 sec CPU average: 0.346507607 sec real / 0.000073651 sec CPU stdev : 0.001035954 sec real / 0.000003688 sec CPU take4 local Strip out best and worst realtime result minimum: 0.199643000 sec real / 0.000063611 sec CPU maximum: 0.207476000 sec real / 0.000072059 sec CPU average: 0.201715642 sec real / 0.000065163 sec CPU stdev : 0.002009911 sec real / 0.000001659 sec CPU local -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.253969000 sec real / 0.000056606 sec CPU maximum: 0.264754000 sec real / 0.000072700 sec CPU average: 0.256445071 sec real / 0.000063609 sec CPU stdev : 0.001690957 sec real / 0.000000905 sec CPU global Strip out best and worst realtime result minimum: 0.222315000 sec real / 0.000063257 sec CPU maximum: 0.231086000 sec real / 0.000078530 sec CPU average: 0.223764642 sec real / 0.000065032 sec CPU stdev : 0.000751210 sec real / 0.000000672 sec CPU global -E LD_BIND_NOW=1 optarg="LD_BIND_NOW=1" Strip out best and worst realtime result minimum: 0.295561000 sec real / 0.000056096 sec CPU maximum: 0.303293000 sec real / 0.000086572 sec CPU average: 0.297082285 sec real / 0.000074283 sec CPU stdev : 0.001047270 sec real / 0.000003516 sec CPU [-- Attachment #6: statsy --] [-- Type: text/plain, Size: 2638 bytes --] /tmp/startup.odt (empty doc with: sub Main Shell("killall sleep") end sub as the Open event macro, Low macro security setting), /tmp/a.sh contains: #!/bin/sh DISPLAY=localhost:0 oowriter /tmp/startup.odt > /dev/null 2>&1 & sleep 1200 and modified timing.c, such that it waits for user input from stdin after every invocation is measured. unprelinked numbers are each from ./timing.modified -c 10 -n /tmp/a.sh, prelinked from ./timing.modified -c 20 -n /tmp/a.sh. unprelinked .hash minimum: 1.715100000 sec real / 0.000051953 sec CPU maximum: 1.774593000 sec real / 0.000058803 sec CPU average: 1.731386200 sec real / 0.000054716 sec CPU stdev : 0.016703570 sec real / 0.000002011 sec CPU take1 minimum: 1.336888000 sec real / 0.000052909 sec CPU maximum: 1.376870000 sec real / 0.000062253 sec CPU average: 1.348290500 sec real / 0.000056337 sec CPU stdev : 0.011036217 sec real / 0.000002695 sec CPU take2 minimum: 1.306500000 sec real / 0.000052635 sec CPU maximum: 1.327990000 sec real / 0.000060805 sec CPU average: 1.316566200 sec real / 0.000056985 sec CPU stdev : 0.007522361 sec real / 0.000002221 sec CPU take3 minimum: 1.229256000 sec real / 0.000051459 sec CPU maximum: 1.330513000 sec real / 0.000057706 sec CPU average: 1.285629900 sec real / 0.000055250 sec CPU stdev : 0.026779805 sec real / 0.000001934 sec CPU take4 minimum: 1.120778000 sec real / 0.000054010 sec CPU maximum: 1.296930000 sec real / 0.000062093 sec CPU average: 1.195947600 sec real / 0.000057423 sec CPU stdev : 0.048721391 sec real / 0.000002233 sec CPU prelinked .hash minimum: 1.338352000 sec real / 0.000050213 sec CPU maximum: 1.358660000 sec real / 0.000059908 sec CPU average: 1.348639650 sec real / 0.000055596 sec CPU stdev : 0.005795022 sec real / 0.000002687 sec CPU take1 minimum: 1.097255000 sec real / 0.000054104 sec CPU maximum: 1.204971000 sec real / 0.000061802 sec CPU average: 1.160938850 sec real / 0.000056718 sec CPU stdev : 0.040502782 sec real / 0.000002018 sec CPU take2 minimum: 1.078807000 sec real / 0.000053083 sec CPU maximum: 1.181643000 sec real / 0.000063952 sec CPU average: 1.147430150 sec real / 0.000056455 sec CPU stdev : 0.034557199 sec real / 0.000002833 sec CPU take3 minimum: 1.056688000 sec real / 0.000046743 sec CPU maximum: 1.161373000 sec real / 0.000070731 sec CPU average: 1.133688450 sec real / 0.000057349 sec CPU stdev : 0.027867890 sec real / 0.000004267 sec CPU take4 minimum: 1.024210000 sec real / 0.000053391 sec CPU maximum: 1.143304000 sec real / 0.000061477 sec CPU average: 1.099958300 sec real / 0.000056757 sec CPU stdev : 0.031722271 sec real / 0.000002175 sec CPU ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: DT_GNU_HASH latest patches 2006-07-07 14:45 ` Jakub Jelinek @ 2006-07-07 15:57 ` djamel anonymous 2006-07-09 22:27 ` Jakub Jelinek 2006-07-08 2:45 ` Eric Christopher ` (3 subsequent siblings) 4 siblings, 1 reply; 17+ messages in thread From: djamel anonymous @ 2006-07-07 15:57 UTC (permalink / raw) To: jakub; +Cc: binutils, drepper, michael.meeks, libc-alpha Hello, first i thank you for testing my suggestion.in the patch, i have noted the current line cinfo.maskbits = bfd_log2 (cinfo.nsyms) + 1; the size of the hash table is between cinfo.nsyms*2 and cindo.nsysm*4 bits which will filter between 1/2 and 1/4 of the unsuccessful queries.perhaps the a size of bfd_log2 (cinfo.nsyms) + 2 or bfd_log2 (cinfo.nsyms) + 3 would give better results. the rounding i was suggesting was to round cinfo.nsyms to the nearest power of two and then multiply by 8 this would have given 8*cinfo.nsyms bits on average . but perhaps with this the table would have been too big ti fit inisde the hash table.the code to do that would have been: tmp=bfd_log2 (cinfo.nsyms)*8; if(tmp&(1<<(bfd_log2(cinfo.nsyms)-2))) cinfo.maskbits = tmp; else cinfo.maskbits = tmp-1; there is perhaps an ideal value for maskbits that would have to be selected by benchmarking differenr value; a large value of maskbits would avoid many accesses to the buckets but reduce the chances of maskbits to fit in the l1 cache. best regards. _________________________________________________________________ MSN Hotmail : créez votre adresse e-mail gratuite & à vie ! http://www.msn.fr/newhotmail/Default.asp?Ath=f ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: DT_GNU_HASH latest patches 2006-07-07 15:57 ` djamel anonymous @ 2006-07-09 22:27 ` Jakub Jelinek 0 siblings, 0 replies; 17+ messages in thread From: Jakub Jelinek @ 2006-07-09 22:27 UTC (permalink / raw) To: djamel anonymous; +Cc: binutils, drepper, michael.meeks, libc-alpha On Fri, Jul 07, 2006 at 03:56:59PM +0000, djamel anonymous wrote: > Hello, first i thank you for testing my suggestion.in the patch, i have > noted the current line > cinfo.maskbits = bfd_log2 (cinfo.nsyms) + 1; bfd_log2 is not 32 - __builtin_clz. cinfo.maskbits = bfd_log2 (cinfo.nsyms) + 1; if (cinfo.maskbits < 3) cinfo.maskbits = 1 << 5; else if ((1 << (cinfo.maskbits - 2)) & cinfo.nsyms) cinfo.maskbits = 1 << (cinfo.maskbits + 3); else cinfo.maskbits = 1 << (cinfo.maskbits + 2); gives you approx. NSYMS bytes in the bitmask (between NSYMS*(2/3)*8 and NSYMS*(4/3)*8 bits). Jakub ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: DT_GNU_HASH latest patches 2006-07-07 14:45 ` Jakub Jelinek 2006-07-07 15:57 ` djamel anonymous @ 2006-07-08 2:45 ` Eric Christopher 2006-07-09 22:35 ` Jakub Jelinek 2006-07-10 14:18 ` Nick Clifton ` (2 subsequent siblings) 4 siblings, 1 reply; 17+ messages in thread From: Eric Christopher @ 2006-07-08 2:45 UTC (permalink / raw) To: Jakub Jelinek; +Cc: binutils Jakub Jelinek wrote: > On Thu, Jul 06, 2006 at 07:53:29PM +0000, djamel anonymous wrote: >> Hello, i am writing you this time about the first variant.after looking at >> the benchmark results i noted that there have been a reduction in the >> number of l1 cache misses; a reduction in l1 cache misses means a win of 12 >> cycles ; the difference between the latency of l2 cache and that of l1 >> cache 15-3.on the other hand replacing a division by a binary and & is a >> win of at least 25 cycles, so it think that avoiding tthe division in the >> common case may improve performance. > > I don't think it is the modulo that matters, but the smaller footprint > of .gnu.hash case in that case. I have implemented what I think you meant > and the numbers actually convinced me. > So here is the new set of patches and new statistics. > take1 is 2006-06-28 state of things, take2 2006-07-03, take3 2006-07-05 > and take4 what is attached here. > A little more documentation on the new method in the code would be helpful though. "Don't change this, you'll break it" is rarely enough :) -eric ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: DT_GNU_HASH latest patches 2006-07-08 2:45 ` Eric Christopher @ 2006-07-09 22:35 ` Jakub Jelinek 0 siblings, 0 replies; 17+ messages in thread From: Jakub Jelinek @ 2006-07-09 22:35 UTC (permalink / raw) To: Eric Christopher; +Cc: binutils On Fri, Jul 07, 2006 at 07:45:30PM -0700, Eric Christopher wrote: > A little more documentation on the new method in the code would be > helpful though. "Don't change this, you'll break it" is rarely enough :) If you mean the comment above the hash function, I think that's sufficient and indeed it is the same as above the SysV hash function. The command just warns that the hash function is part of the object format, so nothing people should try to "improve" (unlike only internally used hash functions)... Jakub ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: DT_GNU_HASH latest patches 2006-07-07 14:45 ` Jakub Jelinek 2006-07-07 15:57 ` djamel anonymous 2006-07-08 2:45 ` Eric Christopher @ 2006-07-10 14:18 ` Nick Clifton 2006-07-10 14:18 ` Nick Clifton 2006-07-10 14:20 ` Nick Clifton 4 siblings, 0 replies; 17+ messages in thread From: Nick Clifton @ 2006-07-10 14:18 UTC (permalink / raw) To: Jakub Jelinek Cc: djamel anonymous, binutils, drepper, michael.meeks, libc-alpha Hi Jakub, > 2006-07-07 Jakub Jelinek <jakub@redhat.com> > > include/ > * bfdlink.h (struct bfd_link_info): Add emit_hash and > emit_gnu_hash bitfields. > include/elf/ > * common.h (SHT_GNU_HASH, DT_GNU_HASH): Define. > ld/ > * scripttempl/elf.sc: Add .gnu.hash section. > * emultempl/elf32.em (OPTION_HASH_STYLE): Define. > (gld${EMULATION_NAME}_add_options): Register --hash-style option. > (gld${EMULATION_NAME}_handle_option): Handle it. > (gld${EMULATION_NAME}_list_options): Document it. > * ldmain.c (main): Initialize emit_hash and emit_gnu_hash. > * ld.texinfo: Document --hash-style option. > bfd/ > * elf.c (_bfd_elf_print_private_bfd_data): Handle DT_GNU_HASH. > (bfd_section_from_shdr, elf_fake_sections, assign_section_numbers): > Handle SHT_GNU_HASH. > (special_sections_g): Include .gnu.hash section. > (bfd_elf_gnu_hash): New function. > * elf-bfd.h (bfd_elf_gnu_hash, _bfd_elf_hash_symbol): New prototypes. > (struct elf_backend_data): Add elf_hash_symbol method. > * elflink.c (_bfd_elf_link_create_dynamic_sections): Create .hash > only if info->emit_hash, create .gnu.hash section if > info->emit_gnu_hash. > (struct collect_gnu_hash_codes): New type. > (elf_collect_gnu_hash_codes, elf_renumber_gnu_hash_syms, > _bfd_elf_hash_symbol): New functions. > (compute_bucket_count): Don't compute HASHCODES array, instead add > that and NSYMS as arguments. Use bed->s->sizeof_hash_entry > instead of bed->s->arch_size / 8. Fix .hash size estimation. > When not optimizing, use the number of hashed symbols rather than > dynsymcount. > (bfd_elf_size_dynamic_sections): Only add DT_HASH if info->emit_hash, > and ADD DT_GNU_HASH if info->emit_gnu_hash. > (bfd_elf_size_dynsym_hash_dynstr): Size .hash only if info->emit_hash, > adjust compute_bucket_count caller. Create and populate .gnu.hash > section if info->emit_gnu_hash. > (elf_link_output_extsym): Only populate .hash section if > finfo->hash_sec != NULL. > (bfd_elf_final_link): Adjust assertion. Handle DT_GNU_HASH. > * elfxx-target.h (elf_backend_hash_symbol): Define if not yet defined. > (elfNN_bed): Add elf_backend_hash_symbol. > * elf64-x86-64.c (elf64_x86_64_hash_symbol): New function. > (elf_backend_hash_symbol): Define. > * elf32-i386.c (elf_i386_hash_symbol): New function. > (elf_backend_hash_symbol): Define. > binutils/ > * readelf.c (get_dynamic_type): Handle DT_GNU_HASH. > (get_section_type_name): Handle SHT_GNU_HASH. > (dynamic_info_DT_GNU_HASH): New variable. > (process_dynamic_section): Handle DT_GNU_HASH. > (process_symbol_table): Print also DT_GNU_HASH histogram. Approved - please apply. Cheers Nick ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: DT_GNU_HASH latest patches 2006-07-07 14:45 ` Jakub Jelinek ` (2 preceding siblings ...) 2006-07-10 14:18 ` Nick Clifton @ 2006-07-10 14:18 ` Nick Clifton 2006-07-10 14:20 ` Nick Clifton 4 siblings, 0 replies; 17+ messages in thread From: Nick Clifton @ 2006-07-10 14:18 UTC (permalink / raw) To: Jakub Jelinek Cc: djamel anonymous, binutils, drepper, michael.meeks, libc-alpha Hi Jakub, > 2006-07-07 Jakub Jelinek <jakub@redhat.com> > > include/ > * bfdlink.h (struct bfd_link_info): Add emit_hash and > emit_gnu_hash bitfields. > include/elf/ > * common.h (SHT_GNU_HASH, DT_GNU_HASH): Define. > ld/ > * scripttempl/elf.sc: Add .gnu.hash section. > * emultempl/elf32.em (OPTION_HASH_STYLE): Define. > (gld${EMULATION_NAME}_add_options): Register --hash-style option. > (gld${EMULATION_NAME}_handle_option): Handle it. > (gld${EMULATION_NAME}_list_options): Document it. > * ldmain.c (main): Initialize emit_hash and emit_gnu_hash. > * ld.texinfo: Document --hash-style option. > bfd/ > * elf.c (_bfd_elf_print_private_bfd_data): Handle DT_GNU_HASH. > (bfd_section_from_shdr, elf_fake_sections, assign_section_numbers): > Handle SHT_GNU_HASH. > (special_sections_g): Include .gnu.hash section. > (bfd_elf_gnu_hash): New function. > * elf-bfd.h (bfd_elf_gnu_hash, _bfd_elf_hash_symbol): New prototypes. > (struct elf_backend_data): Add elf_hash_symbol method. > * elflink.c (_bfd_elf_link_create_dynamic_sections): Create .hash > only if info->emit_hash, create .gnu.hash section if > info->emit_gnu_hash. > (struct collect_gnu_hash_codes): New type. > (elf_collect_gnu_hash_codes, elf_renumber_gnu_hash_syms, > _bfd_elf_hash_symbol): New functions. > (compute_bucket_count): Don't compute HASHCODES array, instead add > that and NSYMS as arguments. Use bed->s->sizeof_hash_entry > instead of bed->s->arch_size / 8. Fix .hash size estimation. > When not optimizing, use the number of hashed symbols rather than > dynsymcount. > (bfd_elf_size_dynamic_sections): Only add DT_HASH if info->emit_hash, > and ADD DT_GNU_HASH if info->emit_gnu_hash. > (bfd_elf_size_dynsym_hash_dynstr): Size .hash only if info->emit_hash, > adjust compute_bucket_count caller. Create and populate .gnu.hash > section if info->emit_gnu_hash. > (elf_link_output_extsym): Only populate .hash section if > finfo->hash_sec != NULL. > (bfd_elf_final_link): Adjust assertion. Handle DT_GNU_HASH. > * elfxx-target.h (elf_backend_hash_symbol): Define if not yet defined. > (elfNN_bed): Add elf_backend_hash_symbol. > * elf64-x86-64.c (elf64_x86_64_hash_symbol): New function. > (elf_backend_hash_symbol): Define. > * elf32-i386.c (elf_i386_hash_symbol): New function. > (elf_backend_hash_symbol): Define. > binutils/ > * readelf.c (get_dynamic_type): Handle DT_GNU_HASH. > (get_section_type_name): Handle SHT_GNU_HASH. > (dynamic_info_DT_GNU_HASH): New variable. > (process_dynamic_section): Handle DT_GNU_HASH. > (process_symbol_table): Print also DT_GNU_HASH histogram. Approved - please apply. Cheers Nick ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: DT_GNU_HASH latest patches 2006-07-07 14:45 ` Jakub Jelinek ` (3 preceding siblings ...) 2006-07-10 14:18 ` Nick Clifton @ 2006-07-10 14:20 ` Nick Clifton 2006-07-10 21:52 ` Jakub Jelinek 4 siblings, 1 reply; 17+ messages in thread From: Nick Clifton @ 2006-07-10 14:20 UTC (permalink / raw) To: Jakub Jelinek Cc: djamel anonymous, binutils, drepper, michael.meeks, libc-alpha Hi Jakub, > 2006-07-07 Jakub Jelinek <jakub@redhat.com> > > include/ > * bfdlink.h (struct bfd_link_info): Add emit_hash and > emit_gnu_hash bitfields. > include/elf/ > * common.h (SHT_GNU_HASH, DT_GNU_HASH): Define. > ld/ > * scripttempl/elf.sc: Add .gnu.hash section. > * emultempl/elf32.em (OPTION_HASH_STYLE): Define. > (gld${EMULATION_NAME}_add_options): Register --hash-style option. > (gld${EMULATION_NAME}_handle_option): Handle it. > (gld${EMULATION_NAME}_list_options): Document it. > * ldmain.c (main): Initialize emit_hash and emit_gnu_hash. > * ld.texinfo: Document --hash-style option. > bfd/ > * elf.c (_bfd_elf_print_private_bfd_data): Handle DT_GNU_HASH. > (bfd_section_from_shdr, elf_fake_sections, assign_section_numbers): > Handle SHT_GNU_HASH. > (special_sections_g): Include .gnu.hash section. > (bfd_elf_gnu_hash): New function. > * elf-bfd.h (bfd_elf_gnu_hash, _bfd_elf_hash_symbol): New prototypes. > (struct elf_backend_data): Add elf_hash_symbol method. > * elflink.c (_bfd_elf_link_create_dynamic_sections): Create .hash > only if info->emit_hash, create .gnu.hash section if > info->emit_gnu_hash. > (struct collect_gnu_hash_codes): New type. > (elf_collect_gnu_hash_codes, elf_renumber_gnu_hash_syms, > _bfd_elf_hash_symbol): New functions. > (compute_bucket_count): Don't compute HASHCODES array, instead add > that and NSYMS as arguments. Use bed->s->sizeof_hash_entry > instead of bed->s->arch_size / 8. Fix .hash size estimation. > When not optimizing, use the number of hashed symbols rather than > dynsymcount. > (bfd_elf_size_dynamic_sections): Only add DT_HASH if info->emit_hash, > and ADD DT_GNU_HASH if info->emit_gnu_hash. > (bfd_elf_size_dynsym_hash_dynstr): Size .hash only if info->emit_hash, > adjust compute_bucket_count caller. Create and populate .gnu.hash > section if info->emit_gnu_hash. > (elf_link_output_extsym): Only populate .hash section if > finfo->hash_sec != NULL. > (bfd_elf_final_link): Adjust assertion. Handle DT_GNU_HASH. > * elfxx-target.h (elf_backend_hash_symbol): Define if not yet defined. > (elfNN_bed): Add elf_backend_hash_symbol. > * elf64-x86-64.c (elf64_x86_64_hash_symbol): New function. > (elf_backend_hash_symbol): Define. > * elf32-i386.c (elf_i386_hash_symbol): New function. > (elf_backend_hash_symbol): Define. > binutils/ > * readelf.c (get_dynamic_type): Handle DT_GNU_HASH. > (get_section_type_name): Handle SHT_GNU_HASH. > (dynamic_info_DT_GNU_HASH): New variable. > (process_dynamic_section): Handle DT_GNU_HASH. > (process_symbol_table): Print also DT_GNU_HASH histogram. Approved - please apply. Cheers Nick ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: DT_GNU_HASH latest patches 2006-07-10 14:20 ` Nick Clifton @ 2006-07-10 21:52 ` Jakub Jelinek 2006-07-11 13:35 ` Hans-Peter Nilsson 0 siblings, 1 reply; 17+ messages in thread From: Jakub Jelinek @ 2006-07-10 21:52 UTC (permalink / raw) To: Nick Clifton Cc: djamel anonymous, binutils, drepper, michael.meeks, libc-alpha On Mon, Jul 10, 2006 at 03:20:01PM +0100, Nick Clifton wrote: > Approved - please apply. Thanks. I have done some small tweaks so that the .gnu.hash section can support (almost) no bloom filter (setting bitmaskwords in the header to 1 and all ones in the bitmask), or 1 bit (that's what the Friday version did, with shift in the header 0) or 2 bit bloom filter (which improves performance by around 3%). Here is what I have committed and Ulrich is now committing the glibc side to the libc CVS. On x86-64, the version from Friday on the oowriter run had: 85.07% - filtered out by the 1 bit bloom filter 3.35% - empty chain (hits just 2 cache lines) 11.58% - chain walk (3 cache lines) This version has: 91.30% - filtered out by 2 bit 64-bit bloom filter (the same size of the bitmask array as before) 1.62% - empty chain 7.08% - chain walk The same with LD_BIND_NOW=1 oowriter, before: 85.17% - bloom filter 3.35% - empty chain 11.48% - chain walk Now: 91.44% - 2 bit 64-bit bloom filter 1.60% - empty chain 6.96% - chain walk We have experimented with making the bitmask array smaller, but that turned to be a bad idea and showed very clearly in the numbers. 2006-07-10 Jakub Jelinek <jakub@redhat.com> include/ * bfdlink.h (struct bfd_link_info): Add emit_hash and emit_gnu_hash bitfields. include/elf/ * common.h (SHT_GNU_HASH, DT_GNU_HASH): Define. ld/ * scripttempl/elf.sc: Add .gnu.hash section. * emultempl/elf32.em (OPTION_HASH_STYLE): Define. (gld${EMULATION_NAME}_add_options): Register --hash-style option. (gld${EMULATION_NAME}_handle_option): Handle it. (gld${EMULATION_NAME}_list_options): Document it. * ldmain.c (main): Initialize emit_hash and emit_gnu_hash. * ld.texinfo: Document --hash-style option. ld/testsuite/ * ld-powerpc/tlsso32.r: Adjust. * ld-powerpc/tlsso32.d: Adjust. * ld-powerpc/tlsso32.g: Adjust. * ld-powerpc/tlsso.r: Adjust. * ld-powerpc/tlsso.g: Adjust. * ld-powerpc/tlstocso.g: Adjust. bfd/ * elf.c (_bfd_elf_print_private_bfd_data): Handle DT_GNU_HASH. (bfd_section_from_shdr, elf_fake_sections, assign_section_numbers): Handle SHT_GNU_HASH. (special_sections_g): Include .gnu.hash section. (bfd_elf_gnu_hash): New function. * elf-bfd.h (bfd_elf_gnu_hash, _bfd_elf_hash_symbol): New prototypes. (struct elf_backend_data): Add elf_hash_symbol method. * elflink.c (_bfd_elf_link_create_dynamic_sections): Create .hash only if info->emit_hash, create .gnu.hash section if info->emit_gnu_hash. (struct collect_gnu_hash_codes): New type. (elf_collect_gnu_hash_codes, elf_renumber_gnu_hash_syms, _bfd_elf_hash_symbol): New functions. (compute_bucket_count): Don't compute HASHCODES array, instead add that and NSYMS as arguments. Use bed->s->sizeof_hash_entry instead of bed->s->arch_size / 8. Fix .hash size estimation. When not optimizing, use the number of hashed symbols rather than dynsymcount. (bfd_elf_size_dynamic_sections): Only add DT_HASH if info->emit_hash, and ADD DT_GNU_HASH if info->emit_gnu_hash. (bfd_elf_size_dynsym_hash_dynstr): Size .hash only if info->emit_hash, adjust compute_bucket_count caller. Create and populate .gnu.hash section if info->emit_gnu_hash. (elf_link_output_extsym): Only populate .hash section if finfo->hash_sec != NULL. (bfd_elf_final_link): Adjust assertion. Handle DT_GNU_HASH. * elfxx-target.h (elf_backend_hash_symbol): Define if not yet defined. (elfNN_bed): Add elf_backend_hash_symbol. * elf64-x86-64.c (elf64_x86_64_hash_symbol): New function. (elf_backend_hash_symbol): Define. * elf32-i386.c (elf_i386_hash_symbol): New function. (elf_backend_hash_symbol): Define. binutils/ * readelf.c (get_dynamic_type): Handle DT_GNU_HASH. (get_section_type_name): Handle SHT_GNU_HASH. (dynamic_info_DT_GNU_HASH): New variable. (process_dynamic_section): Handle DT_GNU_HASH. (process_symbol_table): Print also DT_GNU_HASH histogram. --- ld/scripttempl/elf.sc.jj 2006-01-01 01:02:16.000000000 +0100 +++ ld/scripttempl/elf.sc 2006-06-22 11:11:53.000000000 +0200 @@ -260,6 +260,7 @@ SECTIONS ${INITIAL_READONLY_SECTIONS} ${TEXT_DYNAMIC+${DYNAMIC}} .hash ${RELOCATING-0} : { *(.hash) } + .gnu.hash ${RELOCATING-0} : { *(.gnu.hash) } .dynsym ${RELOCATING-0} : { *(.dynsym) } .dynstr ${RELOCATING-0} : { *(.dynstr) } .gnu.version ${RELOCATING-0} : { *(.gnu.version) } --- ld/ldmain.c.jj 2006-06-01 15:50:33.000000000 +0200 +++ ld/ldmain.c 2006-06-22 11:21:11.000000000 +0200 @@ -304,6 +304,8 @@ main (int argc, char **argv) link_info.create_object_symbols_section = NULL; link_info.gc_sym_list = NULL; link_info.base_file = NULL; + link_info.emit_hash = TRUE; + link_info.emit_gnu_hash = FALSE; /* SVR4 linkers seem to set DT_INIT and DT_FINI based on magic _init and _fini symbols. We are compatible. */ link_info.init_function = "_init"; --- ld/ld.texinfo.jj 2006-06-15 14:31:06.000000000 +0200 +++ ld/ld.texinfo 2006-06-22 14:03:21.000000000 +0200 @@ -1883,6 +1883,14 @@ time it takes the linker to perform its increasing the linker's memory requirements. Similarly reducing this value can reduce the memory requirements at the expense of speed. +@kindex --hash-style=@var{style} +@item --hash-style=@var{style} +Set the type of linker's hash table(s). @var{style} can be either +@code{sysv} for classic ELF @code{.hash} section, @code{gnu} for +new style GNU @code{.gnu.hash} section or @code{both} for both +the classic ELF @code{.hash} and new style GNU @code{.gnu.hash} +hash tables. The default is @code{sysv}. + @kindex --reduce-memory-overheads @item --reduce-memory-overheads This option reduces memory requirements at ld runtime, at the expense of --- ld/emultempl/elf32.em.jj 2006-06-20 18:34:24.000000000 +0200 +++ ld/emultempl/elf32.em 2006-06-22 14:39:25.000000000 +0200 @@ -1719,6 +1719,7 @@ cat >>e${EMULATION_NAME}.c <<EOF #define OPTION_GROUP (OPTION_ENABLE_NEW_DTAGS + 1) #define OPTION_EH_FRAME_HDR (OPTION_GROUP + 1) #define OPTION_EXCLUDE_LIBS (OPTION_EH_FRAME_HDR + 1) +#define OPTION_HASH_STYLE (OPTION_EXCLUDE_LIBS + 1) static void gld${EMULATION_NAME}_add_options @@ -1735,6 +1736,7 @@ cat >>e${EMULATION_NAME}.c <<EOF {"enable-new-dtags", no_argument, NULL, OPTION_ENABLE_NEW_DTAGS}, {"eh-frame-hdr", no_argument, NULL, OPTION_EH_FRAME_HDR}, {"exclude-libs", required_argument, NULL, OPTION_EXCLUDE_LIBS}, + {"hash-style", required_argument, NULL, OPTION_HASH_STYLE}, {"Bgroup", no_argument, NULL, OPTION_GROUP}, EOF fi @@ -1791,6 +1793,22 @@ cat >>e${EMULATION_NAME}.c <<EOF add_excluded_libs (optarg); break; + case OPTION_HASH_STYLE: + link_info.emit_hash = FALSE; + link_info.emit_gnu_hash = FALSE; + if (strcmp (optarg, "sysv") == 0) + link_info.emit_hash = TRUE; + else if (strcmp (optarg, "gnu") == 0) + link_info.emit_gnu_hash = TRUE; + else if (strcmp (optarg, "both") == 0) + { + link_info.emit_hash = TRUE; + link_info.emit_gnu_hash = TRUE; + } + else + einfo (_("%P%F: invalid hash style \`%s'\n"), optarg); + break; + case 'z': if (strcmp (optarg, "initfirst") == 0) link_info.flags_1 |= (bfd_vma) DF_1_INITFIRST; @@ -1894,6 +1912,7 @@ cat >>e${EMULATION_NAME}.c <<EOF fprintf (file, _(" --disable-new-dtags\tDisable new dynamic tags\n")); fprintf (file, _(" --enable-new-dtags\tEnable new dynamic tags\n")); fprintf (file, _(" --eh-frame-hdr\tCreate .eh_frame_hdr section\n")); + fprintf (file, _(" --hash-style=STYLE\tSet hash style to sysv, gnu or both\n")); fprintf (file, _(" -z combreloc\t\tMerge dynamic relocs into one section and sort\n")); fprintf (file, _(" -z defs\t\tReport unresolved symbols in object files.\n")); fprintf (file, _(" -z execstack\t\tMark executable as requiring executable stack\n")); --- bfd/elf-bfd.h.jj 2006-06-20 18:34:24.000000000 +0200 +++ bfd/elf-bfd.h 2006-07-06 15:48:12.000000000 +0200 @@ -1038,6 +1038,9 @@ struct elf_backend_data bfd_boolean *, bfd_boolean *, bfd *, asection **); + /* Return TRUE if symbol should be hashed in the `.gnu.hash' section. */ + bfd_boolean (*elf_hash_symbol) (struct elf_link_hash_entry *); + /* Used to handle bad SHF_LINK_ORDER input. */ bfd_error_handler_type link_order_error_handler; @@ -1481,6 +1484,8 @@ extern bfd_vma _bfd_elf_section_offset extern unsigned long bfd_elf_hash (const char *); +extern unsigned long bfd_elf_gnu_hash + (const char *); extern bfd_reloc_status_type bfd_elf_generic_reloc (bfd *, arelent *, asymbol *, void *, asection *, bfd *, char **); @@ -1651,6 +1656,8 @@ extern bfd_boolean _bfd_elf_merge_symbol struct elf_link_hash_entry **, bfd_boolean *, bfd_boolean *, bfd_boolean *, bfd_boolean *); +extern bfd_boolean _bfd_elf_hash_symbol (struct elf_link_hash_entry *); + extern bfd_boolean _bfd_elf_add_default_symbol (bfd *, struct bfd_link_info *, struct elf_link_hash_entry *, const char *, Elf_Internal_Sym *, asection **, bfd_vma *, --- bfd/elf64-x86-64.c.jj 2006-06-20 11:57:19.000000000 +0200 +++ bfd/elf64-x86-64.c 2006-07-06 16:54:21.000000000 +0200 @@ -3615,6 +3615,19 @@ elf64_x86_64_additional_program_headers return count; } +/* Return TRUE if symbol should be hashed in the `.gnu.hash' section. */ + +static bfd_boolean +elf64_x86_64_hash_symbol (struct elf_link_hash_entry *h) +{ + if (h->plt.offset != (bfd_vma) -1 + && !h->def_regular + && !h->pointer_equality_needed) + return FALSE; + + return _bfd_elf_hash_symbol (h); +} + static const struct bfd_elf_special_section elf64_x86_64_special_sections[]= { @@ -3688,5 +3701,7 @@ static const struct bfd_elf_special_sect elf64_x86_64_special_sections #define elf_backend_additional_program_headers \ elf64_x86_64_additional_program_headers +#define elf_backend_hash_symbol \ + elf64_x86_64_hash_symbol #include "elf64-target.h" --- bfd/elf.c.jj 2006-06-20 18:34:24.000000000 +0200 +++ bfd/elf.c 2006-07-10 19:10:40.000000000 +0200 @@ -206,6 +206,21 @@ bfd_elf_hash (const char *namearg) return h & 0xffffffff; } +/* DT_GNU_HASH hash function. Do not change this function; you will + cause invalid hash tables to be generated. */ + +unsigned long +bfd_elf_gnu_hash (const char *namearg) +{ + const unsigned char *name = (const unsigned char *) namearg; + unsigned long h = 5381; + unsigned char ch; + + while ((ch = *name++) != '\0') + h = (h << 5) + h + ch; + return h & 0xffffffff; +} + bfd_boolean bfd_elf_mkobject (bfd *abfd) { @@ -1239,6 +1254,7 @@ _bfd_elf_print_private_bfd_data (bfd *ab case DT_AUXILIARY: name = "AUXILIARY"; stringp = TRUE; break; case DT_USED: name = "USED"; break; case DT_FILTER: name = "FILTER"; stringp = TRUE; break; + case DT_GNU_HASH: name = "GNU_HASH"; break; } fprintf (f, " %-11s ", name); @@ -1823,6 +1839,7 @@ bfd_section_from_shdr (bfd *abfd, unsign case SHT_FINI_ARRAY: /* .fini_array section. */ case SHT_PREINIT_ARRAY: /* .preinit_array section. */ case SHT_GNU_LIBLIST: /* .gnu.liblist section. */ + case SHT_GNU_HASH: /* .gnu.hash section. */ return _bfd_elf_make_section_from_shdr (abfd, hdr, name, shindex); case SHT_DYNAMIC: /* Dynamic linking information. */ @@ -2295,6 +2312,7 @@ static const struct bfd_elf_special_sect { ".gnu.version_r", 14, 0, SHT_GNU_verneed, 0 }, { ".gnu.liblist", 12, 0, SHT_GNU_LIBLIST, SHF_ALLOC }, { ".gnu.conflict", 13, 0, SHT_RELA, SHF_ALLOC }, + { ".gnu.hash", 9, 0, SHT_GNU_HASH, SHF_ALLOC }, { NULL, 0, 0, 0, 0 } }; @@ -2811,6 +2829,10 @@ elf_fake_sections (bfd *abfd, asection * case SHT_GROUP: this_hdr->sh_entsize = 4; break; + + case SHT_GNU_HASH: + this_hdr->sh_entsize = bed->s->arch_size == 64 ? 0 : 4; + break; } if ((asect->flags & SEC_ALLOC) != 0) @@ -3256,6 +3278,7 @@ assign_section_numbers (bfd *abfd, struc break; case SHT_HASH: + case SHT_GNU_HASH: case SHT_GNU_versym: /* sh_link is the section header index of the symbol table this hash table or version table is for. */ --- bfd/elf32-i386.c.jj 2006-06-23 15:32:34.000000000 +0200 +++ bfd/elf32-i386.c 2006-07-06 16:56:24.000000000 +0200 @@ -3835,6 +3835,18 @@ elf_i386_plt_sym_val (bfd_vma i, const a return plt->vma + (i + 1) * PLT_ENTRY_SIZE; } +/* Return TRUE if symbol should be hashed in the `.gnu.hash' section. */ + +static bfd_boolean +elf_i386_hash_symbol (struct elf_link_hash_entry *h) +{ + if (h->plt.offset != (bfd_vma) -1 + && !h->def_regular + && !h->pointer_equality_needed) + return FALSE; + + return _bfd_elf_hash_symbol (h); +} #define TARGET_LITTLE_SYM bfd_elf32_i386_vec #define TARGET_LITTLE_NAME "elf32-i386" @@ -3875,6 +3887,7 @@ elf_i386_plt_sym_val (bfd_vma i, const a #define elf_backend_size_dynamic_sections elf_i386_size_dynamic_sections #define elf_backend_always_size_sections elf_i386_always_size_sections #define elf_backend_plt_sym_val elf_i386_plt_sym_val +#define elf_backend_hash_symbol elf_i386_hash_symbol #include "elf32-target.h" --- bfd/elflink.c.jj 2006-06-20 18:34:53.000000000 +0200 +++ bfd/elflink.c 2006-07-10 19:01:44.000000000 +0200 @@ -240,12 +240,30 @@ _bfd_elf_link_create_dynamic_sections (b if (!_bfd_elf_define_linkage_sym (abfd, info, s, "_DYNAMIC")) return FALSE; - s = bfd_make_section_with_flags (abfd, ".hash", - flags | SEC_READONLY); - if (s == NULL - || ! bfd_set_section_alignment (abfd, s, bed->s->log_file_align)) - return FALSE; - elf_section_data (s)->this_hdr.sh_entsize = bed->s->sizeof_hash_entry; + if (info->emit_hash) + { + s = bfd_make_section_with_flags (abfd, ".hash", flags | SEC_READONLY); + if (s == NULL + || ! bfd_set_section_alignment (abfd, s, bed->s->log_file_align)) + return FALSE; + elf_section_data (s)->this_hdr.sh_entsize = bed->s->sizeof_hash_entry; + } + + if (info->emit_gnu_hash) + { + s = bfd_make_section_with_flags (abfd, ".gnu.hash", + flags | SEC_READONLY); + if (s == NULL + || ! bfd_set_section_alignment (abfd, s, bed->s->log_file_align)) + return FALSE; + /* For 64-bit ELF, .gnu.hash is a non-uniform entity size section: + 4 32-bit words followed by variable count of 64-bit words, then + variable count of 32-bit words. */ + if (bed->s->arch_size == 64) + elf_section_data (s)->this_hdr.sh_entsize = 0; + else + elf_section_data (s)->this_hdr.sh_entsize = 4; + } /* Let the backend create the rest of the sections. This lets the backend set the right flags. The backend will normally create @@ -4811,6 +4829,131 @@ elf_collect_hash_codes (struct elf_link_ return TRUE; } +struct collect_gnu_hash_codes +{ + bfd *output_bfd; + const struct elf_backend_data *bed; + unsigned long int nsyms; + unsigned long int maskbits; + unsigned long int *hashcodes; + unsigned long int *hashval; + unsigned long int *indx; + unsigned long int *counts; + bfd_vma *bitmask; + bfd_byte *contents; + long int min_dynindx; + unsigned long int bucketcount; + unsigned long int symindx; + long int local_indx; + long int shift1, shift2; + unsigned long int mask; +}; + +/* This function will be called though elf_link_hash_traverse to store + all hash value of the exported symbols in an array. */ + +static bfd_boolean +elf_collect_gnu_hash_codes (struct elf_link_hash_entry *h, void *data) +{ + struct collect_gnu_hash_codes *s = data; + const char *name; + char *p; + unsigned long ha; + char *alc = NULL; + + if (h->root.type == bfd_link_hash_warning) + h = (struct elf_link_hash_entry *) h->root.u.i.link; + + /* Ignore indirect symbols. These are added by the versioning code. */ + if (h->dynindx == -1) + return TRUE; + + /* Ignore also local symbols and undefined symbols. */ + if (! (*s->bed->elf_hash_symbol) (h)) + return TRUE; + + name = h->root.root.string; + p = strchr (name, ELF_VER_CHR); + if (p != NULL) + { + alc = bfd_malloc (p - name + 1); + memcpy (alc, name, p - name); + alc[p - name] = '\0'; + name = alc; + } + + /* Compute the hash value. */ + ha = bfd_elf_gnu_hash (name); + + /* Store the found hash value in the array for compute_bucket_count, + and also for .dynsym reordering purposes. */ + s->hashcodes[s->nsyms] = ha; + s->hashval[h->dynindx] = ha; + ++s->nsyms; + if (s->min_dynindx < 0 || s->min_dynindx > h->dynindx) + s->min_dynindx = h->dynindx; + + if (alc != NULL) + free (alc); + + return TRUE; +} + +/* This function will be called though elf_link_hash_traverse to do + final dynaminc symbol renumbering. */ + +static bfd_boolean +elf_renumber_gnu_hash_syms (struct elf_link_hash_entry *h, void *data) +{ + struct collect_gnu_hash_codes *s = data; + unsigned long int bucket; + unsigned long int val; + + if (h->root.type == bfd_link_hash_warning) + h = (struct elf_link_hash_entry *) h->root.u.i.link; + + /* Ignore indirect symbols. */ + if (h->dynindx == -1) + return TRUE; + + /* Ignore also local symbols and undefined symbols. */ + if (! (*s->bed->elf_hash_symbol) (h)) + { + if (h->dynindx >= s->min_dynindx) + h->dynindx = s->local_indx++; + return TRUE; + } + + bucket = s->hashval[h->dynindx] % s->bucketcount; + val = (s->hashval[h->dynindx] >> s->shift1) + & ((s->maskbits >> s->shift1) - 1); + s->bitmask[val] |= ((bfd_vma) 1) << (s->hashval[h->dynindx] & s->mask); + s->bitmask[val] + |= ((bfd_vma) 1) << ((s->hashval[h->dynindx] >> s->shift2) & s->mask); + val = s->hashval[h->dynindx] & ~(unsigned long int) 1; + if (s->counts[bucket] == 1) + /* Last element terminates the chain. */ + val |= 1; + bfd_put_32 (s->output_bfd, val, + s->contents + (s->indx[bucket] - s->symindx) * 4); + --s->counts[bucket]; + h->dynindx = s->indx[bucket]++; + return TRUE; +} + +/* Return TRUE if symbol should be hashed in the `.gnu.hash' section. */ + +bfd_boolean +_bfd_elf_hash_symbol (struct elf_link_hash_entry *h) +{ + return !(h->forced_local + || h->root.type == bfd_link_hash_undefined + || h->root.type == bfd_link_hash_undefweak + || ((h->root.type == bfd_link_hash_defined + || h->root.type == bfd_link_hash_defweak) + && h->root.u.def.section->output_section == NULL)); +} + /* Array used to determine the number of hash table buckets to use based on the number of symbols there are. If there are fewer than 3 symbols we use 1 bucket, fewer than 17 symbols we use 3 buckets, @@ -4832,42 +4975,26 @@ static const size_t elf_buckets[] = Therefore the result is always a good payoff between few collisions (= short chain lengths) and table size. */ static size_t -compute_bucket_count (struct bfd_link_info *info) +compute_bucket_count (struct bfd_link_info *info, unsigned long int *hashcodes, + unsigned long int nsyms, int gnu_hash) { size_t dynsymcount = elf_hash_table (info)->dynsymcount; size_t best_size = 0; - unsigned long int *hashcodes; - unsigned long int *hashcodesp; unsigned long int i; bfd_size_type amt; - /* Compute the hash values for all exported symbols. At the same - time store the values in an array so that we could use them for - optimizations. */ - amt = dynsymcount; - amt *= sizeof (unsigned long int); - hashcodes = bfd_malloc (amt); - if (hashcodes == NULL) - return 0; - hashcodesp = hashcodes; - - /* Put all hash values in HASHCODES. */ - elf_link_hash_traverse (elf_hash_table (info), - elf_collect_hash_codes, &hashcodesp); - /* We have a problem here. The following code to optimize the table size requires an integer type with more the 32 bits. If BFD_HOST_U_64_BIT is set we know about such a type. */ #ifdef BFD_HOST_U_64_BIT if (info->optimize) { - unsigned long int nsyms = hashcodesp - hashcodes; size_t minsize; size_t maxsize; BFD_HOST_U_64_BIT best_chlen = ~((BFD_HOST_U_64_BIT) 0); - unsigned long int *counts ; bfd *dynobj = elf_hash_table (info)->dynobj; const struct elf_backend_data *bed = get_elf_backend_data (dynobj); + unsigned long int *counts; /* Possible optimization parameters: if we have NSYMS symbols we say that the hashing table must at least have NSYMS/4 and at most @@ -4876,6 +5003,13 @@ compute_bucket_count (struct bfd_link_in if (minsize == 0) minsize = 1; best_size = maxsize = nsyms * 2; + if (gnu_hash) + { + if (minsize < 2) + minsize = 2; + if ((best_size & 31) == 0) + ++best_size; + } /* Create array where we count the collisions in. We must use bfd_malloc since the size could be large. */ @@ -4883,10 +5017,7 @@ compute_bucket_count (struct bfd_link_in amt *= sizeof (unsigned long int); counts = bfd_malloc (amt); if (counts == NULL) - { - free (hashcodes); - return 0; - } + return 0; /* Compute the "optimal" size for the hash table. The criteria is a minimal chain length. The minor criteria is (of course) the size @@ -4898,6 +5029,9 @@ compute_bucket_count (struct bfd_link_in unsigned long int j; unsigned long int fact; + if (gnu_hash && (i & 31) == 0) + continue; + memset (counts, '\0', i * sizeof (unsigned long int)); /* Determine how often each hash bucket is used. */ @@ -4913,9 +5047,9 @@ compute_bucket_count (struct bfd_link_in # define BFD_TARGET_PAGESIZE (4096) # endif - /* We in any case need 2 + NSYMS entries for the size values and - the chains. */ - max = (2 + nsyms) * (bed->s->arch_size / 8); + /* We in any case need 2 + DYNSYMCOUNT entries for the size values + and the chains. */ + max = (2 + dynsymcount) * bed->s->sizeof_hash_entry; # if 1 /* Variant 1: optimize for short chains. We add the squares @@ -4925,7 +5059,7 @@ compute_bucket_count (struct bfd_link_in max += counts[j] * counts[j]; /* This adds penalties for the overall size of the table. */ - fact = i / (BFD_TARGET_PAGESIZE / (bed->s->arch_size / 8)) + 1; + fact = i / (BFD_TARGET_PAGESIZE / bed->s->sizeof_hash_entry) + 1; max *= fact * fact; # else /* Variant 2: Optimize a lot more for small table. Here we @@ -4936,7 +5070,7 @@ compute_bucket_count (struct bfd_link_in /* The overall size of the table is considered, but not as strong as in variant 1, where it is squared. */ - fact = i / (BFD_TARGET_PAGESIZE / (bed->s->arch_size / 8)) + 1; + fact = i / (BFD_TARGET_PAGESIZE / bed->s->sizeof_hash_entry) + 1; max *= fact; # endif @@ -4959,14 +5093,13 @@ compute_bucket_count (struct bfd_link_in for (i = 0; elf_buckets[i] != 0; i++) { best_size = elf_buckets[i]; - if (dynsymcount < elf_buckets[i + 1]) + if (nsyms < elf_buckets[i + 1]) break; } + if (gnu_hash && best_size < 2) + best_size = 2; } - /* Free the arrays we needed. */ - free (hashcodes); - return best_size; } @@ -5324,7 +5457,10 @@ bfd_elf_size_dynamic_sections (bfd *outp bfd_size_type strsize; strsize = _bfd_elf_strtab_size (elf_hash_table (info)->dynstr); - if (!_bfd_elf_add_dynamic_entry (info, DT_HASH, 0) + if ((info->emit_hash + && !_bfd_elf_add_dynamic_entry (info, DT_HASH, 0)) + || (info->emit_gnu_hash + && !_bfd_elf_add_dynamic_entry (info, DT_GNU_HASH, 0)) || !_bfd_elf_add_dynamic_entry (info, DT_STRTAB, 0) || !_bfd_elf_add_dynamic_entry (info, DT_SYMTAB, 0) || !_bfd_elf_add_dynamic_entry (info, DT_STRSZ, strsize) @@ -5726,8 +5862,6 @@ bfd_elf_size_dynsym_hash_dynstr (bfd *ou asection *s; bfd_size_type dynsymcount; unsigned long section_sym_count; - size_t bucketcount = 0; - size_t hash_entry_size; unsigned int dtagcount; dynobj = elf_hash_table (info)->dynobj; @@ -5778,23 +5912,215 @@ bfd_elf_size_dynsym_hash_dynstr (bfd *ou memset (s->contents, 0, section_sym_count * bed->s->sizeof_sym); } + elf_hash_table (info)->bucketcount = 0; + /* Compute the size of the hashing table. As a side effect this computes the hash values for all the names we export. */ - bucketcount = compute_bucket_count (info); + if (info->emit_hash) + { + unsigned long int *hashcodes; + unsigned long int *hashcodesp; + bfd_size_type amt; + unsigned long int nsyms; + size_t bucketcount; + size_t hash_entry_size; + + /* Compute the hash values for all exported symbols. At the same + time store the values in an array so that we could use them for + optimizations. */ + amt = dynsymcount * sizeof (unsigned long int); + hashcodes = bfd_malloc (amt); + if (hashcodes == NULL) + return FALSE; + hashcodesp = hashcodes; - s = bfd_get_section_by_name (dynobj, ".hash"); - BFD_ASSERT (s != NULL); - hash_entry_size = elf_section_data (s)->this_hdr.sh_entsize; - s->size = ((2 + bucketcount + dynsymcount) * hash_entry_size); - s->contents = bfd_zalloc (output_bfd, s->size); - if (s->contents == NULL) - return FALSE; + /* Put all hash values in HASHCODES. */ + elf_link_hash_traverse (elf_hash_table (info), + elf_collect_hash_codes, &hashcodesp); - bfd_put (8 * hash_entry_size, output_bfd, bucketcount, s->contents); - bfd_put (8 * hash_entry_size, output_bfd, dynsymcount, - s->contents + hash_entry_size); + nsyms = hashcodesp - hashcodes; + bucketcount + = compute_bucket_count (info, hashcodes, nsyms, 0); + free (hashcodes); - elf_hash_table (info)->bucketcount = bucketcount; + if (bucketcount == 0) + return FALSE; + + elf_hash_table (info)->bucketcount = bucketcount; + + s = bfd_get_section_by_name (dynobj, ".hash"); + BFD_ASSERT (s != NULL); + hash_entry_size = elf_section_data (s)->this_hdr.sh_entsize; + s->size = ((2 + bucketcount + dynsymcount) * hash_entry_size); + s->contents = bfd_zalloc (output_bfd, s->size); + if (s->contents == NULL) + return FALSE; + + bfd_put (8 * hash_entry_size, output_bfd, bucketcount, s->contents); + bfd_put (8 * hash_entry_size, output_bfd, dynsymcount, + s->contents + hash_entry_size); + } + + if (info->emit_gnu_hash) + { + size_t i, cnt; + unsigned char *contents; + struct collect_gnu_hash_codes cinfo; + bfd_size_type amt; + size_t bucketcount; + + memset (&cinfo, 0, sizeof (cinfo)); + + /* Compute the hash values for all exported symbols. At the same + time store the values in an array so that we could use them for + optimizations. */ + amt = dynsymcount * 2 * sizeof (unsigned long int); + cinfo.hashcodes = bfd_malloc (amt); + if (cinfo.hashcodes == NULL) + return FALSE; + + cinfo.hashval = cinfo.hashcodes + dynsymcount; + cinfo.min_dynindx = -1; + cinfo.output_bfd = output_bfd; + cinfo.bed = bed; + + /* Put all hash values in HASHCODES. */ + elf_link_hash_traverse (elf_hash_table (info), + elf_collect_gnu_hash_codes, &cinfo); + + bucketcount + = compute_bucket_count (info, cinfo.hashcodes, cinfo.nsyms, 1); + + if (bucketcount == 0) + { + free (cinfo.hashcodes); + return FALSE; + } + + s = bfd_get_section_by_name (dynobj, ".gnu.hash"); + BFD_ASSERT (s != NULL); + + if (cinfo.nsyms == 0) + { + /* Empty .gnu.hash section is special. */ + BFD_ASSERT (cinfo.min_dynindx == -1); + free (cinfo.hashcodes); + s->size = 5 * 4 + bed->s->arch_size / 8; + contents = bfd_zalloc (output_bfd, s->size); + if (contents == NULL) + return FALSE; + s->contents = contents; + /* 1 empty bucket. */ + bfd_put_32 (output_bfd, 1, contents); + /* SYMIDX above the special symbol 0. */ + bfd_put_32 (output_bfd, 1, contents + 4); + /* Just one word for bitmask. */ + bfd_put_32 (output_bfd, 1, contents + 8); + /* Only hash fn bloom filter. */ + bfd_put_32 (output_bfd, 0, contents + 12); + /* No hashes are valid - empty bitmask. */ + bfd_put (bed->s->arch_size, output_bfd, 0, contents + 16); + /* No hashes in the only bucket. */ + bfd_put_32 (output_bfd, 0, + contents + 16 + bed->s->arch_size / 8); + } + else + { + BFD_ASSERT (cinfo.min_dynindx != -1); + unsigned long int maskwords, maskbitslog2; + + maskbitslog2 = bfd_log2 (cinfo.nsyms) + 1; + if (maskbitslog2 < 3) + maskbitslog2 = 5; + else if ((1 << (maskbitslog2 - 2)) & cinfo.nsyms) + maskbitslog2 = maskbitslog2 + 3; + else + maskbitslog2 = maskbitslog2 + 2; + if (bed->s->arch_size == 64) + { + if (maskbitslog2 == 5) + maskbitslog2 = 6; + cinfo.shift1 = 6; + } + else + cinfo.shift1 = 5; + cinfo.mask = (1 << cinfo.shift1) - 1; + cinfo.shift2 = maskbitslog2 + cinfo.shift1; + cinfo.maskbits = 1 << maskbitslog2; + maskwords = 1 << (maskbitslog2 - cinfo.shift1); + amt = bucketcount * sizeof (unsigned long int) * 2; + amt += maskwords * sizeof (bfd_vma); + cinfo.bitmask = bfd_malloc (amt); + if (cinfo.bitmask == NULL) + { + free (cinfo.hashcodes); + return FALSE; + } + + cinfo.counts = (void *) (cinfo.bitmask + maskwords); + cinfo.indx = cinfo.counts + bucketcount; + cinfo.symindx = dynsymcount - cinfo.nsyms; + memset (cinfo.bitmask, 0, maskwords * sizeof (bfd_vma)); + + /* Determine how often each hash bucket is used. */ + memset (cinfo.counts, 0, bucketcount * sizeof (cinfo.counts[0])); + for (i = 0; i < cinfo.nsyms; ++i) + ++cinfo.counts[cinfo.hashcodes[i] % bucketcount]; + + for (i = 0, cnt = cinfo.symindx; i < bucketcount; ++i) + if (cinfo.counts[i] != 0) + { + cinfo.indx[i] = cnt; + cnt += cinfo.counts[i]; + } + BFD_ASSERT (cnt == dynsymcount); + cinfo.bucketcount = bucketcount; + cinfo.local_indx = cinfo.min_dynindx; + + s->size = (4 + bucketcount + cinfo.nsyms) * 4; + s->size += cinfo.maskbits / 8; + contents = bfd_zalloc (output_bfd, s->size); + if (contents == NULL) + { + free (cinfo.bitmask); + free (cinfo.hashcodes); + return FALSE; + } + + s->contents = contents; + bfd_put_32 (output_bfd, bucketcount, contents); + bfd_put_32 (output_bfd, cinfo.symindx, contents + 4); + bfd_put_32 (output_bfd, maskwords, contents + 8); + bfd_put_32 (output_bfd, cinfo.shift2, contents + 12); + contents += 16 + cinfo.maskbits / 8; + + for (i = 0; i < bucketcount; ++i) + { + if (cinfo.counts[i] == 0) + bfd_put_32 (output_bfd, 0, contents); + else + bfd_put_32 (output_bfd, cinfo.indx[i], contents); + contents += 4; + } + + cinfo.contents = contents; + + /* Renumber dynamic symbols, populate .gnu.hash section. */ + elf_link_hash_traverse (elf_hash_table (info), + elf_renumber_gnu_hash_syms, &cinfo); + + contents = s->contents + 16; + for (i = 0; i < maskwords; ++i) + { + bfd_put (bed->s->arch_size, output_bfd, cinfo.bitmask[i], + contents); + contents += bed->s->arch_size / 8; + } + + free (cinfo.bitmask); + free (cinfo.hashcodes); + } + } s = bfd_get_section_by_name (dynobj, ".dynstr"); BFD_ASSERT (s != NULL); @@ -6663,9 +6989,6 @@ elf_link_output_extsym (struct elf_link_ { size_t bucketcount; size_t bucket; - size_t hash_entry_size; - bfd_byte *bucketpos; - bfd_vma chain; bfd_byte *esym; sym.st_name = h->dynstr_index; @@ -6679,15 +7002,23 @@ elf_link_output_extsym (struct elf_link_ bucketcount = elf_hash_table (finfo->info)->bucketcount; bucket = h->u.elf_hash_value % bucketcount; - hash_entry_size - = elf_section_data (finfo->hash_sec)->this_hdr.sh_entsize; - bucketpos = ((bfd_byte *) finfo->hash_sec->contents - + (bucket + 2) * hash_entry_size); - chain = bfd_get (8 * hash_entry_size, finfo->output_bfd, bucketpos); - bfd_put (8 * hash_entry_size, finfo->output_bfd, h->dynindx, bucketpos); - bfd_put (8 * hash_entry_size, finfo->output_bfd, chain, - ((bfd_byte *) finfo->hash_sec->contents - + (bucketcount + 2 + h->dynindx) * hash_entry_size)); + + if (finfo->hash_sec != NULL) + { + size_t hash_entry_size; + bfd_byte *bucketpos; + bfd_vma chain; + + hash_entry_size + = elf_section_data (finfo->hash_sec)->this_hdr.sh_entsize; + bucketpos = ((bfd_byte *) finfo->hash_sec->contents + + (bucket + 2) * hash_entry_size); + chain = bfd_get (8 * hash_entry_size, finfo->output_bfd, bucketpos); + bfd_put (8 * hash_entry_size, finfo->output_bfd, h->dynindx, bucketpos); + bfd_put (8 * hash_entry_size, finfo->output_bfd, chain, + ((bfd_byte *) finfo->hash_sec->contents + + (bucketcount + 2 + h->dynindx) * hash_entry_size)); + } if (finfo->symver_sec != NULL && finfo->symver_sec->contents != NULL) { @@ -7861,7 +8192,7 @@ bfd_elf_final_link (bfd *abfd, struct bf { finfo.dynsym_sec = bfd_get_section_by_name (dynobj, ".dynsym"); finfo.hash_sec = bfd_get_section_by_name (dynobj, ".hash"); - BFD_ASSERT (finfo.dynsym_sec != NULL && finfo.hash_sec != NULL); + BFD_ASSERT (finfo.dynsym_sec != NULL); finfo.symver_sec = bfd_get_section_by_name (dynobj, ".gnu.version"); /* Note that it is OK if symver_sec is NULL. */ } @@ -8621,6 +8952,9 @@ bfd_elf_final_link (bfd *abfd, struct bf case DT_HASH: name = ".hash"; goto get_vma; + case DT_GNU_HASH: + name = ".gnu.hash"; + goto get_vma; case DT_STRTAB: name = ".dynstr"; goto get_vma; --- bfd/elfxx-target.h.jj 2006-06-20 18:34:24.000000000 +0200 +++ bfd/elfxx-target.h 2006-07-06 15:38:39.000000000 +0200 @@ -563,6 +563,10 @@ #define elf_backend_merge_symbol NULL #endif +#ifndef elf_backend_hash_symbol +#define elf_backend_hash_symbol _bfd_elf_hash_symbol +#endif + extern const struct elf_size_info _bfd_elfNN_size_info; #ifndef INCLUDED_TARGET_FILE @@ -643,6 +647,7 @@ static struct elf_backend_data elfNN_bed elf_backend_common_section_index, elf_backend_common_section, elf_backend_merge_symbol, + elf_backend_hash_symbol, elf_backend_link_order_error_handler, elf_backend_relplt_name, ELF_MACHINE_ALT1, --- include/elf/common.h.jj 2006-02-17 15:36:26.000000000 +0100 +++ include/elf/common.h 2006-06-22 10:43:21.000000000 +0200 @@ -338,6 +338,7 @@ #define SHT_LOOS 0x60000000 /* First of OS specific semantics */ #define SHT_HIOS 0x6fffffff /* Last of OS specific semantics */ +#define SHT_GNU_HASH 0x6ffffff6 /* GNU style symbol hash table */ #define SHT_GNU_LIBLIST 0x6ffffff7 /* List of prelink dependencies */ /* The next three section types are defined by Solaris, and are named @@ -577,6 +578,7 @@ #define DT_VALRNGHI 0x6ffffdff #define DT_ADDRRNGLO 0x6ffffe00 +#define DT_GNU_HASH 0x6ffffef5 #define DT_TLSDESC_PLT 0x6ffffef6 #define DT_TLSDESC_GOT 0x6ffffef7 #define DT_GNU_CONFLICT 0x6ffffef8 --- include/bfdlink.h.jj 2006-04-07 17:17:29.000000000 +0200 +++ include/bfdlink.h 2006-06-22 11:11:20.000000000 +0200 @@ -324,6 +324,12 @@ struct bfd_link_info /* TRUE if unreferenced sections should be removed. */ unsigned int gc_sections: 1; + /* TRUE if .hash section should be created. */ + unsigned int emit_hash: 1; + + /* TRUE if .gnu.hash section should be created. */ + unsigned int emit_gnu_hash: 1; + /* What to do with unresolved symbols in an object file. When producing executables the default is GENERATE_ERROR. When producing shared libraries the default is IGNORE. The --- binutils/readelf.c.jj 2006-05-30 16:13:54.000000000 +0200 +++ binutils/readelf.c 2006-07-10 18:56:00.000000000 +0200 @@ -135,6 +135,7 @@ static unsigned long dynamic_syminfo_off static unsigned int dynamic_syminfo_nent; static char program_interpreter[64]; static bfd_vma dynamic_info[DT_JMPREL + 1]; +static bfd_vma dynamic_info_DT_GNU_HASH; static bfd_vma version_info[16]; static Elf_Internal_Ehdr elf_header; static Elf_Internal_Shdr *section_headers; @@ -1501,6 +1502,7 @@ get_dynamic_type (unsigned long type) case DT_GNU_CONFLICTSZ: return "GNU_CONFLICTSZ"; case DT_GNU_LIBLIST: return "GNU_LIBLIST"; case DT_GNU_LIBLISTSZ: return "GNU_LIBLISTSZ"; + case DT_GNU_HASH: return "GNU_HASH"; default: if ((type >= DT_LOPROC) && (type <= DT_HIPROC)) @@ -2571,6 +2573,7 @@ get_section_type_name (unsigned int sh_t case SHT_INIT_ARRAY: return "INIT_ARRAY"; case SHT_FINI_ARRAY: return "FINI_ARRAY"; case SHT_PREINIT_ARRAY: return "PREINIT_ARRAY"; + case SHT_GNU_HASH: return "GNU_HASH"; case SHT_GROUP: return "GROUP"; case SHT_SYMTAB_SHNDX: return "SYMTAB SECTION INDICIES"; case SHT_GNU_verdef: return "VERDEF"; @@ -6228,6 +6231,15 @@ process_dynamic_section (FILE *file) } break; + case DT_GNU_HASH: + dynamic_info_DT_GNU_HASH = entry->d_un.d_val; + if (do_dynamic) + { + print_vma (entry->d_un.d_val, PREFIX_HEX); + putchar ('\n'); + } + break; + default: if ((entry->d_tag >= DT_VERSYM) && (entry->d_tag <= DT_VERNEEDNUM)) version_info[DT_VERSIONTAGIDX (entry->d_tag)] = @@ -6903,6 +6915,9 @@ process_symbol_table (FILE *file) bfd_vma nchains = 0; bfd_vma *buckets = NULL; bfd_vma *chains = NULL; + bfd_vma ngnubuckets = 0; + bfd_vma *gnubuckets = NULL; + bfd_vma *gnuchains = NULL; if (! do_syms && !do_histogram) return 1; @@ -7282,6 +7297,166 @@ process_symbol_table (FILE *file) free (chains); } + if (do_histogram && dynamic_info_DT_GNU_HASH) + { + unsigned char nb[16]; + bfd_vma i, maxchain = 0xffffffff, symidx, bitmaskwords; + unsigned long *lengths; + unsigned long *counts; + unsigned long hn; + unsigned long maxlength = 0; + unsigned long nzero_counts = 0; + unsigned long nsyms = 0; + bfd_vma buckets_vma; + + if (fseek (file, + (archive_file_offset + + offset_from_vma (file, dynamic_info_DT_GNU_HASH, + sizeof nb)), + SEEK_SET)) + { + error (_("Unable to seek to start of dynamic information")); + return 0; + } + + if (fread (nb, 16, 1, file) != 1) + { + error (_("Failed to read in number of buckets\n")); + return 0; + } + + ngnubuckets = byte_get (nb, 4); + symidx = byte_get (nb + 4, 4); + bitmaskwords = byte_get (nb + 8, 4); + buckets_vma = dynamic_info_DT_GNU_HASH + 16; + if (is_32bit_elf) + buckets_vma += bitmaskwords * 4; + else + buckets_vma += bitmaskwords * 8; + + if (fseek (file, + (archive_file_offset + + offset_from_vma (file, buckets_vma, 4)), + SEEK_SET)) + { + error (_("Unable to seek to start of dynamic information")); + return 0; + } + + gnubuckets = get_dynamic_data (file, ngnubuckets, 4); + + if (gnubuckets == NULL) + return 0; + + for (i = 0; i < ngnubuckets; i++) + if (gnubuckets[i] != 0) + { + if (gnubuckets[i] < symidx) + return 0; + + if (maxchain == 0xffffffff || gnubuckets[i] > maxchain) + maxchain = gnubuckets[i]; + } + + if (maxchain == 0xffffffff) + return 0; + + maxchain -= symidx; + + if (fseek (file, + (archive_file_offset + + offset_from_vma (file, buckets_vma + + 4 * (ngnubuckets + maxchain), 4)), + SEEK_SET)) + { + error (_("Unable to seek to start of dynamic information")); + return 0; + } + + do + { + if (fread (nb, 4, 1, file) != 1) + { + error (_("Failed to determine last chain length\n")); + return 0; + } + + if (maxchain + 1 == 0) + return 0; + + ++maxchain; + } + while ((byte_get (nb, 4) & 1) == 0); + + if (fseek (file, + (archive_file_offset + + offset_from_vma (file, buckets_vma + 4 * ngnubuckets, 4)), + SEEK_SET)) + { + error (_("Unable to seek to start of dynamic information")); + return 0; + } + + gnuchains = get_dynamic_data (file, maxchain, 4); + + if (gnuchains == NULL) + return 0; + + lengths = calloc (ngnubuckets, sizeof (*lengths)); + if (lengths == NULL) + { + error (_("Out of memory")); + return 0; + } + + printf (_("\nHistogram for `.gnu.hash' bucket list length (total of %lu buckets):\n"), + (unsigned long) ngnubuckets); + printf (_(" Length Number %% of total Coverage\n")); + + for (hn = 0; hn < ngnubuckets; ++hn) + if (gnubuckets[hn] != 0) + { + bfd_vma off, length = 1; + + for (off = gnubuckets[hn] - symidx; + (gnuchains[off] & 1) == 0; ++off) + ++length; + lengths[hn] = length; + if (length > maxlength) + maxlength = length; + nsyms += length; + } + + counts = calloc (maxlength + 1, sizeof (*counts)); + if (counts == NULL) + { + error (_("Out of memory")); + return 0; + } + + for (hn = 0; hn < ngnubuckets; ++hn) + ++counts[lengths[hn]]; + + if (ngnubuckets > 0) + { + unsigned long j; + printf (" 0 %-10lu (%5.1f%%)\n", + counts[0], (counts[0] * 100.0) / ngnubuckets); + for (j = 1; j <= maxlength; ++j) + { + nzero_counts += counts[j] * j; + printf ("%7lu %-10lu (%5.1f%%) %5.1f%%\n", + j, counts[j], (counts[j] * 100.0) / ngnubuckets, + (nzero_counts * 100.0) / nsyms); + } + } + + free (counts); + free (lengths); + free (gnubuckets); + free (gnuchains); + } + return 1; } --- ld/testsuite/ld-powerpc/tlsso32.r.jj 2006-06-29 14:25:12.000000000 +0200 +++ ld/testsuite/ld-powerpc/tlsso32.r 2006-07-10 23:16:16.000000000 +0200 @@ -52,9 +52,9 @@ Relocation section '\.rela\.dyn' at offs [0-9a-f ]+R_PPC_TPREL16 +0+30 +le0 \+ 0 [0-9a-f ]+R_PPC_TPREL16_HA +0+34 +le1 \+ 0 [0-9a-f ]+R_PPC_TPREL16_LO +0+34 +le1 \+ 0 -[0-9a-f ]+R_PPC_TPREL16 +0+1041c +\.tdata \+ 10430 -[0-9a-f ]+R_PPC_TPREL16_HA +0+1041c +\.tdata \+ 10434 -[0-9a-f ]+R_PPC_TPREL16_LO +0+1041c +\.tdata \+ 10434 +[0-9a-f ]+R_PPC_TPREL16 +0+103e4 +\.tdata \+ 103f8 +[0-9a-f ]+R_PPC_TPREL16_HA +0+103e4 +\.tdata \+ 103fc +[0-9a-f ]+R_PPC_TPREL16_LO +0+103e4 +\.tdata \+ 103fc [0-9a-f ]+R_PPC_DTPMOD32 +0+ [0-9a-f ]+R_PPC_DTPREL32 +0+ [0-9a-f ]+R_PPC_DTPMOD32 +0+ --- ld/testsuite/ld-powerpc/tlsso32.d.jj 2005-12-30 13:33:50.000000000 +0100 +++ ld/testsuite/ld-powerpc/tlsso32.d 2006-07-10 23:19:43.000000000 +0200 @@ -42,5 +42,5 @@ Disassembly of section \.got: .* <\.got>: \.\.\. .*: 4e 80 00 21 blrl -.*: 00 01 04 38 .* +.*: 00 01 04 00 .* \.\.\. --- ld/testsuite/ld-powerpc/tlsso32.g.jj 2005-12-30 13:33:50.000000000 +0100 +++ ld/testsuite/ld-powerpc/tlsso32.g 2006-07-10 23:22:06.000000000 +0200 @@ -9,5 +9,5 @@ Contents of section \.got: .* 00000000 00000000 00000000 00000000 .* .* 00000000 00000000 00000000 00000000 .* -.* 00000000 4e800021 00010438 00000000 .* +.* 00000000 4e800021 00010400 00000000 .* .* 00000000 .* --- ld/testsuite/ld-powerpc/tlsso.r.jj 2006-06-29 14:25:12.000000000 +0200 +++ ld/testsuite/ld-powerpc/tlsso.r 2006-07-10 23:32:22.000000000 +0200 @@ -49,9 +49,9 @@ Relocation section '\.rela\.dyn' at offs [0-9a-f ]+R_PPC64_TPREL16 +0+60 le0 \+ 0 [0-9a-f ]+R_PPC64_TPREL16_HA +0+68 le1 \+ 0 [0-9a-f ]+R_PPC64_TPREL16_LO +0+68 le1 \+ 0 -[0-9a-f ]+R_PPC64_TPREL16_DS +0+10668 \.tdata \+ 28 -[0-9a-f ]+R_PPC64_TPREL16_HA +0+10668 \.tdata \+ 30 -[0-9a-f ]+R_PPC64_TPREL16_LO +0+10668 \.tdata \+ 30 +[0-9a-f ]+R_PPC64_TPREL16_DS +0+10630 \.tdata \+ 28 +[0-9a-f ]+R_PPC64_TPREL16_HA +0+10630 \.tdata \+ 30 +[0-9a-f ]+R_PPC64_TPREL16_LO +0+10630 \.tdata \+ 30 [0-9a-f ]+R_PPC64_DTPMOD64 +0+ [0-9a-f ]+R_PPC64_DTPMOD64 +0+ [0-9a-f ]+R_PPC64_DTPREL64 +0+ --- ld/testsuite/ld-powerpc/tlsso.g.jj 2005-12-30 13:33:50.000000000 +0100 +++ ld/testsuite/ld-powerpc/tlsso.g 2006-07-10 23:34:21.000000000 +0200 @@ -7,7 +7,7 @@ .*: +file format elf64-powerpc Contents of section \.got: -.* 00000000 000187f0 00000000 00000000 .* +.* 00000000 000187b8 00000000 00000000 .* .* 00000000 00000000 00000000 00000000 .* .* 00000000 00000000 00000000 00000000 .* .* 00000000 00000000 00000000 00000000 .* --- ld/testsuite/ld-powerpc/tlstocso.g.jj 2005-12-30 13:33:50.000000000 +0100 +++ ld/testsuite/ld-powerpc/tlstocso.g 2006-07-10 23:34:48.000000000 +0200 @@ -7,7 +7,7 @@ .*: +file format elf64-powerpc Contents of section \.got: -.* 00000000 00018738 00000000 00000000 .* +.* 00000000 00018700 00000000 00000000 .* .* 00000000 00000000 00000000 00000000 .* .* 00000000 00000000 00000000 00000000 .* .* 00000000 00000000 00000000 00000000 .* Jakub ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: DT_GNU_HASH latest patches 2006-07-10 21:52 ` Jakub Jelinek @ 2006-07-11 13:35 ` Hans-Peter Nilsson 2006-07-11 13:58 ` Jakub Jelinek 0 siblings, 1 reply; 17+ messages in thread From: Hans-Peter Nilsson @ 2006-07-11 13:35 UTC (permalink / raw) To: jakub; +Cc: binutils > Date: Mon, 10 Jul 2006 23:51:35 +0200 > From: Jakub Jelinek <jakub@redhat.com> > 2006-07-10 Jakub Jelinek <jakub@redhat.com> > > include/ > * bfdlink.h (struct bfd_link_info): Add emit_hash and > emit_gnu_hash bitfields. > include/elf/ > * common.h (SHT_GNU_HASH, DT_GNU_HASH): Define. > ld/ > * scripttempl/elf.sc: Add .gnu.hash section. > * emultempl/elf32.em (OPTION_HASH_STYLE): Define. > (gld${EMULATION_NAME}_add_options): Register --hash-style option. > (gld${EMULATION_NAME}_handle_option): Handle it. > (gld${EMULATION_NAME}_list_options): Document it. > * ldmain.c (main): Initialize emit_hash and emit_gnu_hash. > * ld.texinfo: Document --hash-style option. > ld/testsuite/ > * ld-powerpc/tlsso32.r: Adjust. > * ld-powerpc/tlsso32.d: Adjust. > * ld-powerpc/tlsso32.g: Adjust. > * ld-powerpc/tlsso.r: Adjust. > * ld-powerpc/tlsso.g: Adjust. > * ld-powerpc/tlstocso.g: Adjust. > bfd/ > * elf.c (_bfd_elf_print_private_bfd_data): Handle DT_GNU_HASH. > (bfd_section_from_shdr, elf_fake_sections, assign_section_numbers): > Handle SHT_GNU_HASH. > (special_sections_g): Include .gnu.hash section. > (bfd_elf_gnu_hash): New function. > * elf-bfd.h (bfd_elf_gnu_hash, _bfd_elf_hash_symbol): New prototypes. > (struct elf_backend_data): Add elf_hash_symbol method. > * elflink.c (_bfd_elf_link_create_dynamic_sections): Create .hash > only if info->emit_hash, create .gnu.hash section if > info->emit_gnu_hash. > (struct collect_gnu_hash_codes): New type. > (elf_collect_gnu_hash_codes, elf_renumber_gnu_hash_syms, > _bfd_elf_hash_symbol): New functions. > (compute_bucket_count): Don't compute HASHCODES array, instead add > that and NSYMS as arguments. Use bed->s->sizeof_hash_entry > instead of bed->s->arch_size / 8. Fix .hash size estimation. > When not optimizing, use the number of hashed symbols rather than > dynsymcount. > (bfd_elf_size_dynamic_sections): Only add DT_HASH if info->emit_hash, > and ADD DT_GNU_HASH if info->emit_gnu_hash. > (bfd_elf_size_dynsym_hash_dynstr): Size .hash only if info->emit_hash, > adjust compute_bucket_count caller. Create and populate .gnu.hash > section if info->emit_gnu_hash. > (elf_link_output_extsym): Only populate .hash section if > finfo->hash_sec != NULL. > (bfd_elf_final_link): Adjust assertion. Handle DT_GNU_HASH. > * elfxx-target.h (elf_backend_hash_symbol): Define if not yet defined. > (elfNN_bed): Add elf_backend_hash_symbol. > * elf64-x86-64.c (elf64_x86_64_hash_symbol): New function. > (elf_backend_hash_symbol): Define. > * elf32-i386.c (elf_i386_hash_symbol): New function. > (elf_backend_hash_symbol): Define. > binutils/ > * readelf.c (get_dynamic_type): Handle DT_GNU_HASH. > (get_section_type_name): Handle SHT_GNU_HASH. > (dynamic_info_DT_GNU_HASH): New variable. > (process_dynamic_section): Handle DT_GNU_HASH. > (process_symbol_table): Print also DT_GNU_HASH histogram. Great, great. Though, one of these bits caused, for --target=cris-axis-elf: FAIL: ld-cris/libdso-2 Looks like you forgot to adjust ld/testsuite/ld-cris/libdso-2.d. Is it to be expected that one of your changes (presumably in compute_bucket_count) caused some hash-related section in a DSO to shrink by eight bytes, despite no change in section types (no .gnu.hash)? I see you made some similar adjustments for the powerpc TLS tests, but thought I'd better check as this secondary effect on non-.gnu.hash objects wasn't clearly enough announced as intended. If it was intended, and not a sign of a bug, a proper testsuite adjustment could have looked like this: ;) (will check in when clarified) * ld-cris/libdso-2.d: Adjust for recent hash-related changes. Index: libdso-2.d =================================================================== RCS file: /cvs/src/src/ld/testsuite/ld-cris/libdso-2.d,v retrieving revision 1.13 diff -u -p -r1.13 libdso-2.d --- libdso-2.d 2 Jun 2006 00:31:59 -0000 1.13 +++ libdso-2.d 11 Jul 2006 13:19:27 -0000 @@ -27,14 +27,14 @@ There are 13 section headers.* #... Relocation section '\.rela\.dyn' at offset 0x[0-9a-f]+ contains 1 entries: #... -00002200 0000000c R_CRIS_RELATIVE 00000158 +00002[12][0-9a-f][048c] 0000000c R_CRIS_RELATIVE 00000150 #... Symbol table '\.dynsym' contains 4 entries: Num: Value Size Type Bind Vis Ndx Name 0: 0+ 0 NOTYPE LOCAL DEFAULT UND 1: [0-9a-f]+ 0 SECTION LOCAL DEFAULT 7 2: 0+ 0 OBJECT GLOBAL DEFAULT ABS TST1 - 3: 0+15c 0 FUNC GLOBAL DEFAULT 7 export_1@@TST1 + 3: 0+154 0 FUNC GLOBAL DEFAULT 7 export_1@@TST1 Symbol table '\.symtab' contains 18 entries: Num: Value Size Type Bind Vis Ndx Name @@ -48,11 +48,11 @@ Symbol table '\.symtab' contains 18 entr 7: [0-9a-f]+ 0 SECTION LOCAL DEFAULT 7 8: [0-9a-f]+ 0 SECTION LOCAL DEFAULT 8 9: [0-9a-f]+ 0 SECTION LOCAL DEFAULT 9 - 10: 0+216c 0 OBJECT LOCAL HIDDEN ABS _DYNAMIC - 11: 0+2204 0 NOTYPE LOCAL DEFAULT ABS __bss_start - 12: 0+2204 0 NOTYPE LOCAL DEFAULT ABS _edata - 13: 0+21f4 0 OBJECT LOCAL HIDDEN ABS _GLOBAL_OFFSET_TABLE_ - 14: 0+2220 0 NOTYPE LOCAL DEFAULT ABS _end - 15: 0+158 0 FUNC LOCAL DEFAULT 7 dsofn + 10: 0+2..[046c] 0 OBJECT LOCAL HIDDEN ABS _DYNAMIC + 11: 0+2..[046c] 0 NOTYPE LOCAL DEFAULT ABS __bss_start + 12: 0+2..[046c] 0 NOTYPE LOCAL DEFAULT ABS _edata + 13: 0+2..[046c] 0 OBJECT LOCAL HIDDEN ABS _GLOBAL_OFFSET_TABLE_ + 14: 0+2..[046c] 0 NOTYPE LOCAL DEFAULT ABS _end + 15: 0+150 0 FUNC LOCAL DEFAULT 7 dsofn 16: 0+ 0 OBJECT GLOBAL DEFAULT ABS TST1 - 17: 0+15c 0 FUNC GLOBAL DEFAULT 7 export_1 + 17: 0+154 0 FUNC GLOBAL DEFAULT 7 export_1 brgds, H-P ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: DT_GNU_HASH latest patches 2006-07-11 13:35 ` Hans-Peter Nilsson @ 2006-07-11 13:58 ` Jakub Jelinek 0 siblings, 0 replies; 17+ messages in thread From: Jakub Jelinek @ 2006-07-11 13:58 UTC (permalink / raw) To: Hans-Peter Nilsson; +Cc: binutils On Tue, Jul 11, 2006 at 03:35:01PM +0200, Hans-Peter Nilsson wrote: > Great, great. Though, one of these bits caused, for > --target=cris-axis-elf: > FAIL: ld-cris/libdso-2 Oops, sorry. > Looks like you forgot to adjust ld/testsuite/ld-cris/libdso-2.d. > Is it to be expected that one of your changes (presumably in > compute_bucket_count) caused some hash-related section in a DSO > to shrink by eight bytes, despite no change in section types (no > .gnu.hash)? I see you made some similar adjustments for the > powerpc TLS tests, but thought I'd better check as this > secondary effect on non-.gnu.hash objects wasn't clearly enough > announced as intended. The DT_GNU_HASH patch essentially contained the http://sources.redhat.com/ml/binutils/2006-06/msg00355.html patch (which Alan Modra approved separately, but as I changed that function for DT_GNU_HASH a lot since then, I didn't commit it independently) and that in some cases decreases the size of the .hash section, so what you see is expected. > If it was intended, and not a sign of a bug, a proper testsuite > adjustment could have looked like this: ;) > (will check in when clarified) > > * ld-cris/libdso-2.d: Adjust for recent hash-related changes. Thanks. Jakub ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: DT_GNU_HASH latest patches 2006-07-06 18:22 ` DT_GNU_HASH latest patches Jakub Jelinek 2006-07-06 19:53 ` djamel anonymous @ 2006-07-07 10:07 ` Michael Meeks 2006-07-07 13:43 ` Ulrich Drepper 2006-07-07 13:49 ` Jakub Jelinek 1 sibling, 2 replies; 17+ messages in thread From: Michael Meeks @ 2006-07-07 10:07 UTC (permalink / raw) To: Jakub Jelinek; +Cc: binutils, djamel anonymous, Ulrich Drepper, libc-alpha Hi Jakub, On Thu, 2006-07-06 at 20:21 +0200, Jakub Jelinek wrote: > 1) swapped chainoff and bitmask in the buckets array pairs - bitmask > is accessed first by ld.so, so it makes sense to put it first So - it took a little while to understand your patch :-) from what I see; we insert a 32bit bitmask into the buckets ( in addition to the offset ) whose purpose is to reduce the number of L2 misses incurred by lookups in the 'chain' by seeing if a given bit is set in that mask. Each chain element sets a mask bit using bits 6-10 of the hash as an integer offset / bit-mask (0-31 bits), that is then compared at lookup. So - I guess that's an interesting new twist ;-) I'm not entirely sold on it at 1st glance since it makes the working set larger and the access pattern less predictable - but, if the numbers show it working nicely that's great :-) - [ I found them slightly hard to read side-by-side ]. Some misc. other code questions: + if (buckets[0] & new_hash_bit) Since the average chain length is ~2.5 (say 3) entries; and we have 32 bits to play with here, assuming bits 6-10 are as random as we would like, there is a P(1/10) here that this branch is taken - should we have a __builtin_expect reflecting that ? Similarly is it worth moving some more of the symtab/strtab construction out of the hot path ?, but perhaps the compiler will do it: if ((*hasharr & ~1u) == (new_hash & ~1u)) { symidx = hasharr - map->l_gnu_chain_zero; + /* The tables for this map. */ + const ElfW(Sym) *symtab = (const void *) D_PTR (map, l_info[DT_SYMTAB]); + const char *strtab = (const void *) D_PTR (map, l_info[DT_STRTAB]); + const ElfW(Half) *verstab = map->l_versyms; sym = check_match (&symtab[symidx]); if (sym != NULL) goto found_it; } [ and the same ? for the old style case, AFAIR - I did this in the dynhash patch of old ] Similarly - [ and I've no idea how these 'expect' markups really help on various arches (as no doubt you've guessed by now ;-) ] this is presumably a rather uncommon case: + /* If the hash table is empty there is nothing to do here. */ + if (map->l_nbuckets == 0) + continue; I guess now the common case in this loop is hitting buckets[0] & new_hash_bit and looping, is there anything else we can remove / defer / annotate in that (now much hotter) loop. Otherwise - this looks really interesting to me :-) Thanks, Michael. -- michael.meeks@novell.com <><, Pseudo Engineer, itinerant idiot ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: DT_GNU_HASH latest patches 2006-07-07 10:07 ` Michael Meeks @ 2006-07-07 13:43 ` Ulrich Drepper 2006-07-07 13:49 ` Jakub Jelinek 1 sibling, 0 replies; 17+ messages in thread From: Ulrich Drepper @ 2006-07-07 13:43 UTC (permalink / raw) To: michael.meeks; +Cc: Jakub Jelinek, binutils, libc-alpha [-- Attachment #1: Type: text/plain, Size: 432 bytes --] Michael Meeks wrote: > Some misc. other code questions: > [...] There is no need to scrutinize the libc code here. First of all, this is just the code I tested and not what I have in my sources. And second, I'm very well aware of the generated code. If there are any annotations or changes needed you can be sure I'll add them. -- ➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖ [-- Attachment #2: OpenPGP digital signature --] [-- Type: application/pgp-signature, Size: 251 bytes --] ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: DT_GNU_HASH latest patches 2006-07-07 10:07 ` Michael Meeks 2006-07-07 13:43 ` Ulrich Drepper @ 2006-07-07 13:49 ` Jakub Jelinek 1 sibling, 0 replies; 17+ messages in thread From: Jakub Jelinek @ 2006-07-07 13:49 UTC (permalink / raw) To: Michael Meeks; +Cc: binutils, djamel anonymous, Ulrich Drepper, libc-alpha On Fri, Jul 07, 2006 at 11:10:26AM +0100, Michael Meeks wrote: > + /* If the hash table is empty there is nothing to do here. */ > + if (map->l_nbuckets == 0) > + continue; This is predicted as non-taken by gcc AFAIK, so no need to add __builtin_expect. Jakub ^ permalink raw reply [flat|nested] 17+ messages in thread
end of thread, other threads:[~2006-07-11 13:58 UTC | newest]
Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <44A9D4EB.2040107@redhat.com>
[not found] ` <BAY22-F13B0B8E34EA055F9BF6E50C7710@phx.gbl>
[not found] ` <20060705090438.GJ3823@sunsite.mff.cuni.cz>
2006-07-06 11:26 ` DT_GNU_HASH benchmark results Jakub Jelinek
2006-07-06 18:22 ` DT_GNU_HASH latest patches Jakub Jelinek
2006-07-06 19:53 ` djamel anonymous
2006-07-07 14:45 ` Jakub Jelinek
2006-07-07 15:57 ` djamel anonymous
2006-07-09 22:27 ` Jakub Jelinek
2006-07-08 2:45 ` Eric Christopher
2006-07-09 22:35 ` Jakub Jelinek
2006-07-10 14:18 ` Nick Clifton
2006-07-10 14:18 ` Nick Clifton
2006-07-10 14:20 ` Nick Clifton
2006-07-10 21:52 ` Jakub Jelinek
2006-07-11 13:35 ` Hans-Peter Nilsson
2006-07-11 13:58 ` Jakub Jelinek
2006-07-07 10:07 ` Michael Meeks
2006-07-07 13:43 ` Ulrich Drepper
2006-07-07 13:49 ` Jakub Jelinek
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).