aboutsummaryrefslogtreecommitdiff
path: root/sysdeps/generic
diff options
context:
space:
mode:
authorUlrich Drepper <drepper@redhat.com>1999-04-10 11:51:27 +0000
committerUlrich Drepper <drepper@redhat.com>1999-04-10 11:51:27 +0000
commit3877d9ea5fc19eb51aeab20c3a085c6ce743696c (patch)
tree8b7ba9d8e700e4b484399fd1d1bf3dac1de02cf7 /sysdeps/generic
parent34df6c305435d96e76456cb98bcdb56363fb918f (diff)
downloadglibc-3877d9ea5fc19eb51aeab20c3a085c6ce743696c.tar
glibc-3877d9ea5fc19eb51aeab20c3a085c6ce743696c.tar.gz
glibc-3877d9ea5fc19eb51aeab20c3a085c6ce743696c.tar.bz2
glibc-3877d9ea5fc19eb51aeab20c3a085c6ce743696c.zip
Update.
1999-04-10 Ulrich Drepper <drepper@cygnus.com> * sysdeps/generic/dl-cache.c (_dl_load_cache_lookup): Rewrite to use binary search. Based on a patch by Jakub Jelinek <jj@sunsite.ms.mff.cuni.cz>. 1999-04-07 H.J. Lu <hjl@gnu.org> * manual/install.texi (Reporting Bugs): Add section about reported
Diffstat (limited to 'sysdeps/generic')
-rw-r--r--sysdeps/generic/dl-cache.c150
1 files changed, 127 insertions, 23 deletions
diff --git a/sysdeps/generic/dl-cache.c b/sysdeps/generic/dl-cache.c
index f14cf96da1..ee7080bc8e 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)