From 3877d9ea5fc19eb51aeab20c3a085c6ce743696c Mon Sep 17 00:00:00 2001 From: Ulrich Drepper Date: Sat, 10 Apr 1999 11:51:27 +0000 Subject: Update. 1999-04-10 Ulrich Drepper * sysdeps/generic/dl-cache.c (_dl_load_cache_lookup): Rewrite to use binary search. Based on a patch by Jakub Jelinek . 1999-04-07 H.J. Lu * manual/install.texi (Reporting Bugs): Add section about reported --- ChangeLog | 10 ++- FAQ | 14 ++--- sysdeps/generic/dl-cache.c | 150 ++++++++++++++++++++++++++++++++++++++------- 3 files changed, 139 insertions(+), 35 deletions(-) diff --git a/ChangeLog b/ChangeLog index 6a098f2..b15ff9a 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,9 +1,15 @@ +1999-04-10 Ulrich Drepper + + * sysdeps/generic/dl-cache.c (_dl_load_cache_lookup): Rewrite to + use binary search. + Based on a patch by Jakub Jelinek . + 1999-04-08 Andreas Jaeger * scripts/test-installation.pl (installation_problem): Skip libnss1_* libraries from glibc-compat add-on. -Wed Apr 7 22:52:39 1999 H.J. Lu +1999-04-07 H.J. Lu * io/Versions (__dup2, __pipe): Added to GLIBC_2.0 for libstdc++ 2.7.2. @@ -11,7 +17,7 @@ Wed Apr 7 22:52:39 1999 H.J. Lu 1999-04-08 Andreas Jaeger - * manual/install.texi (Reporting Bugs): Add section about reported + * manual/install.texi (Reporting Bugs): Add section about reported bugs and correct email address of glibcbug script. 1999-04-01 Thorsten Kukuk diff --git a/FAQ b/FAQ index dcc6426..65d1e7d 100644 --- a/FAQ +++ b/FAQ @@ -1417,16 +1417,10 @@ completely. the Perl db modules the testsuite is not passed. This did not happen with db-1, gdbm, or ndbm. -{UD} You are using an outdated copy of the DB_File Perl module. In fact db-2 -finally removed the handling of zero-sized keys which was one of the features -tested by the old Perl testsuite and therefore you see an error. But this -never was documented and guaranteed, only broken programs used this feature. - -Consequently db-2 does not need to support this feature and instead signals -an error which leads to easier debugging. The DB_File module maintainer -Paul Marquess acknowledged this change and fixed -the testsuite so that if you use DB_File v1.60 or later you should not have -any more problems with db-2. +{MK} Db-2 does not support zero-sized keys. The Perl testsuite +tests the support for zero-sized keys and therefore fails when db-2 is +used. The Perl folks are looking for a solution, but thus far have +not found a satisfactory one. 3.14. The pow() inline function I get when including is broken. diff --git a/sysdeps/generic/dl-cache.c b/sysdeps/generic/dl-cache.c index f14cf96..ee7080b 100644 --- a/sysdeps/generic/dl-cache.c +++ b/sysdeps/generic/dl-cache.c @@ -1,5 +1,5 @@ /* Support for reading /etc/ld.so.cache files written by Linux ldconfig. - Copyright (C) 1996, 1997, 1998 Free Software Foundation, Inc. + Copyright (C) 1996, 1997, 1998, 1999 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 @@ -52,13 +52,56 @@ static size_t cachesize; binaries. */ int _dl_correct_cache_id = 3; +/* Helper function which must match the one in ldconfig, so that + we rely on the same sort order. */ +static int +_dl_cache_libcmp (const char *p1, const char *p2) +{ + while (*p1 != '\0') + { + if (*p1 >= '0' && *p1 <= '9') + { + if (*p2 >= '0' && *p2 <= '9') + { + /* Must compare this numerically. */ + int val1; + int val2; + + val1 = *p1++ - '0'; + val2 = *p2++ - '0'; + while (*p1 >= '0' && *p1 <= '9') + val1 = val1 * 10 + *p1++ - '0'; + while (*p2 >= '0' && *p2 <= '9') + val2 = val2 * 10 + *p2++ - '0'; + if (val1 != val2) + return val1 - val2; + } + else + return 1; + } + else if (*p2 >= '0' && *p2 <= '9') + return -1; + else if (*p1 != *p2) + return *p1 - *p2; + else + { + ++p1; + ++p2; + } + } + return *p1 - *p2; +} + + /* Look up NAME in ld.so.cache and return the file name stored there, or null if none is found. */ const char * _dl_load_cache_lookup (const char *name) { - unsigned int i; + int left, right, middle; + int cmpres; + const char *cache_data; const char *best; /* Print a message if the loading of libs is traced. */ @@ -87,28 +130,89 @@ _dl_load_cache_lookup (const char *name) /* Previously looked for the cache file and didn't find it. */ return NULL; + /* This is where the strings start. */ + cache_data = (const char *) &cache->libs[cache->nlibs]; + best = NULL; - for (i = 0; i < cache->nlibs; ++i) - if ((cache->libs[i].flags == 1 || - cache->libs[i].flags == 3) && /* ELF library entry. */ - /* Make sure string table indices are not bogus before using them. */ - cache->libs[i].key < cachesize - sizeof *cache && - cache->libs[i].value < cachesize - sizeof *cache && - /* Does the name match? */ - ! strcmp (name, ((const char *) &cache->libs[cache->nlibs] + - cache->libs[i].key))) - { - if ((best == NULL) || (cache->libs[i].flags == _dl_correct_cache_id)) - { - best = ((const char *) &cache->libs[cache->nlibs] - + cache->libs[i].value); - - if (cache->libs[i].flags == _dl_correct_cache_id) - /* We've found an exact match for the shared object and no - general `ELF' release. Stop searching. */ - break; - } - } + + /* We use binary search since the table is sorted in the cache file. + It is important to use the same algorithm as used while generating + the cache file. */ + left = 0; + right = cache->nlibs - 1; + middle = (left + right) / 2; + cmpres = 1; + + while (left <= right) + { + /* Make sure string table indices are not bogus before using them. */ + if (cache->libs[middle].key >= cachesize - sizeof *cache) + { + cmpres = 1; + break; + } + + /* Actually compare the entry with the key. */ + cmpres = _dl_cache_libcmp (name, cache_data + cache->libs[middle].key); + if (cmpres == 0) + /* Found it. */ + break; + + if (cmpres < 0) + left = middle + 1; + else + right = middle - 1; + + middle = (left + right) / 2; + } + + if (cmpres == 0) + { + /* LEFT now marks the last entry for which we know the name is + correct. */ + left = middle; + + /* There might be entries with this name before the one we + found. So we have to find the beginning. */ + while (middle > 0 + /* Make sure string table indices are not bogus before + using them. */ + && cache->libs[middle - 1].key < cachesize - sizeof *cache + /* Actually compare the entry. */ + && strcmp (name, cache_data + cache->libs[middle - 1].key) == 0) + --middle; + + do + { + int flags; + + /* Only perform the name test if necessary. */ + if (middle > left + /* We haven't seen this string so far. Test whether the + index is ok and whether the name matches. Otherwise + we are done. */ + && (cache->libs[middle].key >= cachesize - sizeof *cache + || strcmp (name, cache_data + cache->libs[middle].key) != 0)) + break; + + flags = cache->libs[middle].flags; + if ((flags == 1 || flags == 3) + && cache->libs[middle].value < cachesize - sizeof *cache) + { + if (best == NULL || flags == _dl_correct_cache_id) + { + best = cache_data + cache->libs[middle].value; + + if (flags == _dl_correct_cache_id) + /* We've found an exact match for the shared + object and no general `ELF' release. Stop + searching. */ + break; + } + } + } + while (++middle <= right); + } /* Print our result if wanted. */ if (_dl_debug_libs && best != NULL) -- cgit v1.1