Module Name: src
Committed By: roy
Date: Sat Feb 27 11:16:38 UTC 2010
Modified Files:
src/libexec/ld.elf_so: load.c rtld.c rtld.h symbol.c
Log Message:
Implement negative cache checks for symbol lookups.
Uses the Donelist idea from FreeBSD.
To generate a diff of this commit:
cvs rdiff -u -r1.36 -r1.37 src/libexec/ld.elf_so/load.c
cvs rdiff -u -r1.128 -r1.129 src/libexec/ld.elf_so/rtld.c
cvs rdiff -u -r1.88 -r1.89 src/libexec/ld.elf_so/rtld.h
cvs rdiff -u -r1.50 -r1.51 src/libexec/ld.elf_so/symbol.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/libexec/ld.elf_so/load.c
diff -u src/libexec/ld.elf_so/load.c:1.36 src/libexec/ld.elf_so/load.c:1.37
--- src/libexec/ld.elf_so/load.c:1.36 Tue May 19 20:44:52 2009
+++ src/libexec/ld.elf_so/load.c Sat Feb 27 11:16:38 2010
@@ -1,4 +1,4 @@
-/* $NetBSD: load.c,v 1.36 2009/05/19 20:44:52 christos Exp $ */
+/* $NetBSD: load.c,v 1.37 2010/02/27 11:16:38 roy Exp $ */
/*
* Copyright 1996 John D. Polstra.
@@ -40,7 +40,7 @@
#include <sys/cdefs.h>
#ifndef lint
-__RCSID("$NetBSD: load.c,v 1.36 2009/05/19 20:44:52 christos Exp $");
+__RCSID("$NetBSD: load.c,v 1.37 2010/02/27 11:16:38 roy Exp $");
#endif /* not lint */
#include <err.h>
@@ -155,6 +155,7 @@
*_rtld_objtail = obj;
_rtld_objtail = &obj->next;
+ _rtld_objcount++;
#ifdef RTLD_LOADER
_rtld_linkmap_add(obj); /* for GDB */
#endif
Index: src/libexec/ld.elf_so/rtld.c
diff -u src/libexec/ld.elf_so/rtld.c:1.128 src/libexec/ld.elf_so/rtld.c:1.129
--- src/libexec/ld.elf_so/rtld.c:1.128 Sun Jan 10 06:37:32 2010
+++ src/libexec/ld.elf_so/rtld.c Sat Feb 27 11:16:38 2010
@@ -1,4 +1,4 @@
-/* $NetBSD: rtld.c,v 1.128 2010/01/10 06:37:32 skrll Exp $ */
+/* $NetBSD: rtld.c,v 1.129 2010/02/27 11:16:38 roy Exp $ */
/*
* Copyright 1996 John D. Polstra.
@@ -40,7 +40,7 @@
#include <sys/cdefs.h>
#ifndef lint
-__RCSID("$NetBSD: rtld.c,v 1.128 2010/01/10 06:37:32 skrll Exp $");
+__RCSID("$NetBSD: rtld.c,v 1.129 2010/02/27 11:16:38 roy Exp $");
#endif /* not lint */
#include <err.h>
@@ -83,6 +83,7 @@
bool _rtld_trust; /* False for setuid and setgid programs */
Obj_Entry *_rtld_objlist; /* Head of linked list of shared objects */
Obj_Entry **_rtld_objtail; /* Link field of last object in list */
+int _rtld_objcount; /* Number of shared objects */
Obj_Entry *_rtld_objmain; /* The main program shared object */
Obj_Entry _rtld_objself; /* The dynamic linker shared object */
const char _rtld_path[] = _PATH_RTLD;
@@ -271,6 +272,7 @@
/* Make the object list empty again. */
_rtld_objlist = NULL;
_rtld_objtail = &_rtld_objlist;
+ _rtld_objcount = 0;
_rtld_debug.r_brk = _rtld_debug_state;
_rtld_debug.r_state = RT_CONSISTENT;
@@ -705,6 +707,7 @@
_rtld_objlist_remove(&_rtld_list_global, obj);
_rtld_linkmap_delete(obj);
*linkp = obj->next;
+ _rtld_objcount--;
_rtld_obj_free(obj);
} else
linkp = &obj->next;
@@ -810,11 +813,16 @@
unsigned long hash;
const Elf_Sym *def;
const Obj_Entry *obj;
+ DoneList donelist;
hash = _rtld_elf_hash(name);
obj = _rtld_objmain;
+ _rtld_donelist_init(&donelist);
- def = _rtld_symlook_list(name, hash, &_rtld_list_main, &obj, false);
+ def = _rtld_symlook_list(name, hash, &_rtld_list_main, &obj, false,
+ &donelist);
+
+ _rtld_donelist_clear(&donelist);
if (def != NULL)
return obj->relocbase + def->st_value;
@@ -838,6 +846,7 @@
const Elf_Sym *def;
const Obj_Entry *defobj;
void *retaddr;
+ DoneList donelist;
hash = _rtld_elf_hash(name);
def = NULL;
@@ -892,20 +901,28 @@
if ((obj = _rtld_dlcheck(handle)) == NULL)
return NULL;
+ _rtld_donelist_init(&donelist);
+
if (obj->mainprog) {
/* Search main program and all libraries loaded by it */
def = _rtld_symlook_list(name, hash, &_rtld_list_main,
- &defobj, false);
+ &defobj, false, &donelist);
} else {
Needed_Entry fake;
+ DoneList depth;
/* Search the object and all the libraries loaded by it. */
fake.next = NULL;
fake.obj = __UNCONST(obj);
fake.name = 0;
+
+ _rtld_donelist_init(&depth);
def = _rtld_symlook_needed(name, hash, &fake, &defobj,
- false);
+ false, &donelist, &depth);
+ _rtld_donelist_clear(&depth);
}
+
+ _rtld_donelist_clear(&donelist);
break;
}
Index: src/libexec/ld.elf_so/rtld.h
diff -u src/libexec/ld.elf_so/rtld.h:1.88 src/libexec/ld.elf_so/rtld.h:1.89
--- src/libexec/ld.elf_so/rtld.h:1.88 Sun Jan 17 08:04:20 2010
+++ src/libexec/ld.elf_so/rtld.h Sat Feb 27 11:16:38 2010
@@ -1,4 +1,4 @@
-/* $NetBSD: rtld.h,v 1.88 2010/01/17 08:04:20 skrll Exp $ */
+/* $NetBSD: rtld.h,v 1.89 2010/02/27 11:16:38 roy Exp $ */
/*
* Copyright 1996 John D. Polstra.
@@ -59,6 +59,16 @@
#define NEW(type) ((type *) xmalloc(sizeof(type)))
#define CNEW(type) ((type *) xcalloc(sizeof(type)))
+/*
+ * Fill in a DoneList with an allocation large enough to hold all of
+ * the currently-loaded objects.
+ */
+#define _rtld_donelist_init(dlp) \
+ ((dlp)->objs = xmalloc(_rtld_objcount * sizeof((dlp)->objs[0])), \
+ (dlp)->num_alloc = _rtld_objcount, \
+ (dlp)->num_used = 0)
+#define _rtld_donelist_clear(dlp) xfree((dlp)->objs)
+
#endif /* _RTLD_SOURCE */
/*
@@ -198,12 +208,20 @@
void *ehdr;
} Obj_Entry;
+typedef struct Struct_DoneList {
+ const Obj_Entry **objs; /* Array of object pointers */
+ unsigned int num_alloc; /* Allocated size of the array */
+ unsigned int num_used; /* Number of array slots used */
+} DoneList;
+
+
#if defined(_RTLD_SOURCE)
extern struct r_debug _rtld_debug;
extern Search_Path *_rtld_default_paths;
extern Obj_Entry *_rtld_objlist;
extern Obj_Entry **_rtld_objtail;
+extern int _rtld_objcount;
extern Obj_Entry *_rtld_objmain;
extern Obj_Entry _rtld_objself;
extern Search_Path *_rtld_paths;
@@ -276,11 +294,12 @@
const Obj_Entry **, bool);
const Elf_Sym *_rtld_symlook_list(const char *, unsigned long,
- const Objlist *, const Obj_Entry **, bool);
+ const Objlist *, const Obj_Entry **, bool, DoneList *);
const Elf_Sym *_rtld_symlook_default(const char *, unsigned long,
const Obj_Entry *, const Obj_Entry **, bool);
const Elf_Sym *_rtld_symlook_needed(const char *, unsigned long,
- const Needed_Entry *, const Obj_Entry **, bool);
+ const Needed_Entry *, const Obj_Entry **, bool,
+ DoneList *, DoneList *);
#ifdef COMBRELOC
void _rtld_combreloc_reset(const Obj_Entry *);
#endif
Index: src/libexec/ld.elf_so/symbol.c
diff -u src/libexec/ld.elf_so/symbol.c:1.50 src/libexec/ld.elf_so/symbol.c:1.51
--- src/libexec/ld.elf_so/symbol.c:1.50 Wed Jan 13 20:17:21 2010
+++ src/libexec/ld.elf_so/symbol.c Sat Feb 27 11:16:38 2010
@@ -1,4 +1,4 @@
-/* $NetBSD: symbol.c,v 1.50 2010/01/13 20:17:21 christos Exp $ */
+/* $NetBSD: symbol.c,v 1.51 2010/02/27 11:16:38 roy Exp $ */
/*
* Copyright 1996 John D. Polstra.
@@ -40,7 +40,7 @@
#include <sys/cdefs.h>
#ifndef lint
-__RCSID("$NetBSD: symbol.c,v 1.50 2010/01/13 20:17:21 christos Exp $");
+__RCSID("$NetBSD: symbol.c,v 1.51 2010/02/27 11:16:38 roy Exp $");
#endif /* not lint */
#include <err.h>
@@ -60,6 +60,27 @@
typedef void (*fptr_t)(void);
+/*
+ * If the given object is already in the donelist, return true. Otherwise
+ * add the object to the list and return false.
+ */
+static bool
+_rtld_donelist_check(DoneList *dlp, const Obj_Entry *obj)
+{
+ unsigned int i;
+
+ for (i = 0; i < dlp->num_used; i++)
+ if (dlp->objs[i] == obj)
+ return true;
+ /*
+ * Our donelist allocation may not always be sufficient as we're not
+ * thread safe. We'll handle it properly anyway.
+ */
+ if (dlp->num_used < dlp->num_alloc)
+ dlp->objs[dlp->num_used++] = obj;
+ return false;
+}
+
static bool
_rtld_is_exported(const Elf_Sym *def)
{
@@ -108,7 +129,7 @@
const Elf_Sym *
_rtld_symlook_list(const char *name, unsigned long hash, const Objlist *objlist,
- const Obj_Entry **defobj_out, bool in_plt)
+ const Obj_Entry **defobj_out, bool in_plt, DoneList *dlp)
{
const Elf_Sym *symp;
const Elf_Sym *def;
@@ -118,6 +139,8 @@
def = NULL;
defobj = NULL;
SIMPLEQ_FOREACH(elm, objlist, link) {
+ if (_rtld_donelist_check(dlp, elm->obj))
+ continue;
rdbg(("search object %p (%s) for %s", elm->obj, elm->obj->path,
name));
if ((symp = _rtld_symlook_obj(name, hash, elm->obj, in_plt))
@@ -143,7 +166,8 @@
*/
const Elf_Sym *
_rtld_symlook_needed(const char *name, unsigned long hash,
- const Needed_Entry *needed, const Obj_Entry **defobj_out, bool inplt)
+ const Needed_Entry *needed, const Obj_Entry **defobj_out, bool inplt,
+ DoneList *breadth, DoneList *depth)
{
const Elf_Sym *def, *def_w;
const Needed_Entry *n;
@@ -152,8 +176,11 @@
def = def_w = NULL;
defobj = NULL;
for (n = needed; n != NULL; n = n->next) {
- if ((obj = n->obj) == NULL ||
- (def = _rtld_symlook_obj(name, hash, obj, inplt)) == NULL)
+ if ((obj = n->obj) == NULL)
+ continue;
+ if (_rtld_donelist_check(breadth, obj))
+ continue;
+ if ((def = _rtld_symlook_obj(name, hash, obj, inplt)) == NULL)
continue;
defobj = obj;
if (ELF_ST_BIND(def->st_info) != STB_WEAK) {
@@ -169,8 +196,10 @@
for (n = needed; n != NULL; n = n->next) {
if ((obj = n->obj) == NULL)
continue;
+ if (_rtld_donelist_check(depth, obj))
+ continue;
def_w = _rtld_symlook_needed(name, hash, obj->needed, &defobj1,
- inplt);
+ inplt, breadth, depth);
if (def_w == NULL)
continue;
if (def == NULL || ELF_ST_BIND(def_w->st_info) != STB_WEAK) {
@@ -381,9 +410,12 @@
const Objlist_Entry *elm;
def = NULL;
defobj = NULL;
+ DoneList donelist;
+
+ _rtld_donelist_init(&donelist);
/* Look first in the referencing object if linked symbolically. */
- if (refobj->symbolic) {
+ if (refobj->symbolic && !_rtld_donelist_check(&donelist, refobj)) {
rdbg(("search referencing object for %s", name));
symp = _rtld_symlook_obj(name, hash, refobj, in_plt);
if (symp != NULL) {
@@ -396,7 +428,7 @@
if (def == NULL || ELF_ST_BIND(def->st_info) == STB_WEAK) {
rdbg(("search _rtld_list_main for %s", name));
symp = _rtld_symlook_list(name, hash, &_rtld_list_main, &obj,
- in_plt);
+ in_plt, &donelist);
if (symp != NULL &&
(def == NULL || ELF_ST_BIND(symp->st_info) != STB_WEAK)) {
def = symp;
@@ -408,7 +440,7 @@
if (def == NULL || ELF_ST_BIND(def->st_info) == STB_WEAK) {
rdbg(("search _rtld_list_global for %s", name));
symp = _rtld_symlook_list(name, hash, &_rtld_list_global,
- &obj, in_plt);
+ &obj, in_plt, &donelist);
if (symp != NULL &&
(def == NULL || ELF_ST_BIND(symp->st_info) != STB_WEAK)) {
def = symp;
@@ -423,7 +455,7 @@
rdbg(("search DAG with root %p (%s) for %s", elm->obj,
elm->obj->path, name));
symp = _rtld_symlook_list(name, hash, &elm->obj->dagmembers,
- &obj, in_plt);
+ &obj, in_plt, &donelist);
if (symp != NULL &&
(def == NULL || ELF_ST_BIND(symp->st_info) != STB_WEAK)) {
def = symp;
@@ -447,6 +479,8 @@
}
}
+ _rtld_donelist_clear(&donelist);
+
if (def != NULL)
*defobj_out = defobj;
return def;
