tech-userlevel archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: [PATCH] ld.elf_so - Cache objects checked



On 02/24/10 13:07, Roy Marples wrote:
As such, I've ported FreeBSD's DoneList cache from their runtime linker
to ours. The main implementation difference is we xmalloc + xfree vs
their alloca + no free needed. They've been using this for a long time,
so the idea + code is pretty solid.

However, I've added a second cache for weak symbols to
_rtld_symlook_needed which is where the real performance gain is made
for my use case. Whilst this doesn't break my system and I cannot see a
flaw in it's design maybe someone can comment?

I've now performed basic performance testing using build.sh -j8 distribution on my Intel QuadCore @ 2.8

-current
real    user    sys
1581.21 4192.03 1251.35
1551.12 4193.71 1261.97
1553.29 4191.63 1264.37

-current + ld.elf_so full cache
1601.38 4192.55 1269.48 *invalid, not cold*
1597.29 4194.84 1268.30
1601.09 4192.46 1269.55

-current + ld.elf_so symbol cache
1578.16 4197.15 1248.08
1550.66 4197.73 1257.49
1550.77 4199.73 1258.35

As you can see, my initial patch which duplicates the FreeBSD donelist and adds the needed cache for weak symbols adds an exrta 50 seconds or so to build.sh.

My new patch (attached, plus build fixes to ldd) just caches symbol lookups and not the inital DAG pass that the first one also did. The overall result is now very slightly faster for build.sh, but the difference is so slight it's not worth talking about. However, the speed gain to Evolution is still there and any other applications that have a large listed of needed libraries and miss symbol lookups.

Unless anyone has any objections I'll commit this soon.

Thanks

Roy
Index: libexec/ld.elf_so/load.c
===================================================================
RCS file: /cvsroot/src/libexec/ld.elf_so/load.c,v
retrieving revision 1.36
diff -u -p -r1.36 load.c
--- libexec/ld.elf_so/load.c    19 May 2009 20:44:52 -0000      1.36
+++ libexec/ld.elf_so/load.c    25 Feb 2010 11:09:12 -0000
@@ -155,6 +155,7 @@ _rtld_load_object(const char *filepath, 
 
                *_rtld_objtail = obj;
                _rtld_objtail = &obj->next;
+               _rtld_objcount++;
 #ifdef RTLD_LOADER
                _rtld_linkmap_add(obj); /* for GDB */
 #endif
Index: libexec/ld.elf_so/rtld.c
===================================================================
RCS file: /cvsroot/src/libexec/ld.elf_so/rtld.c,v
retrieving revision 1.128
diff -u -p -r1.128 rtld.c
--- libexec/ld.elf_so/rtld.c    10 Jan 2010 06:37:32 -0000      1.128
+++ libexec/ld.elf_so/rtld.c    25 Feb 2010 11:09:12 -0000
@@ -83,6 +83,7 @@ struct r_debug  _rtld_debug;  /* for GDB;
 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 @@ _rtld_init(caddr_t mapbase, caddr_t relo
        /* 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_unload_object(Obj_Entry *root, boo
                                _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 @@ _rtld_objmain_sym(const char *name)
        unsigned long hash;
        const Elf_Sym *def;
        const Obj_Entry *obj;
+       DoneList donelist;
 
        hash = _rtld_elf_hash(name);
        obj = _rtld_objmain;
+       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);
+
+       donelist_clear(&donelist);
 
        if (def != NULL)
                return obj->relocbase + def->st_value;
@@ -838,6 +846,7 @@ dlsym(void *handle, const char *name)
        const Elf_Sym *def;
        const Obj_Entry *defobj;
        void *retaddr;
+       DoneList donelist; 
        
        hash = _rtld_elf_hash(name);
        def = NULL;
@@ -892,20 +901,28 @@ dlsym(void *handle, const char *name)
                if ((obj = _rtld_dlcheck(handle)) == NULL)
                        return NULL;
                
+               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 wdonelist;
 
                        /* Search the object and all the libraries loaded by 
it. */
                        fake.next = NULL;
                        fake.obj = __UNCONST(obj);
                        fake.name = 0;
+
+                       donelist_init(&wdonelist);
                        def = _rtld_symlook_needed(name, hash, &fake, &defobj,
-                           false);
+                           false, &donelist, &wdonelist);
+                       donelist_clear(&wdonelist);
                }
+
+               donelist_clear(&donelist);
                break;
        }
        
Index: libexec/ld.elf_so/rtld.h
===================================================================
RCS file: /cvsroot/src/libexec/ld.elf_so/rtld.h,v
retrieving revision 1.88
diff -u -p -r1.88 rtld.h
--- libexec/ld.elf_so/rtld.h    17 Jan 2010 08:04:20 -0000      1.88
+++ libexec/ld.elf_so/rtld.h    25 Feb 2010 11:09:13 -0000
@@ -59,6 +59,16 @@ extern size_t _rtld_pagesz;
 #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 donelist_init(dlp)                                             \
+    ((dlp)->objs = xmalloc(_rtld_objcount * sizeof((dlp)->objs[0])),   \
+    (dlp)->num_alloc = _rtld_objcount,                                 \
+    (dlp)->num_used = 0)
+#define donelist_clear(dlp)            xfree((dlp)->objs)
+
 #endif /* _RTLD_SOURCE */
 
 /*
@@ -198,12 +208,20 @@ typedef struct Struct_Obj_Entry {
        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 Elf_Sym *_rtld_find_plt_symdef(uns
     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: libexec/ld.elf_so/symbol.c
===================================================================
RCS file: /cvsroot/src/libexec/ld.elf_so/symbol.c,v
retrieving revision 1.50
diff -u -p -r1.50 symbol.c
--- libexec/ld.elf_so/symbol.c  13 Jan 2010 20:17:21 -0000      1.50
+++ libexec/ld.elf_so/symbol.c  25 Feb 2010 11:09:13 -0000
@@ -60,6 +60,29 @@ __RCSID("$NetBSD: symbol.c,v 1.50 2010/0
 
 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
+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 should always be sufficient.  But if
+        * our threads locking isn't working properly, more shared objects
+        * could have been loaded since we allocated the list.  That should
+        * never happen, but we'll handle it properly just in case it does.
+        */
+       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 +131,7 @@ _rtld_elf_hash(const char *name)
 
 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 +141,8 @@ _rtld_symlook_list(const char *name, uns
        def = NULL;
        defobj = NULL;
        SIMPLEQ_FOREACH(elm, objlist, link) {
+               if (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 +168,8 @@ _rtld_symlook_list(const char *name, uns
  */
 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 *ndone, DoneList *wdone)
 {
        const Elf_Sym *def, *def_w;
        const Needed_Entry *n;
@@ -152,8 +178,11 @@ _rtld_symlook_needed(const char *name, u
        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 (donelist_check(ndone, 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 +198,10 @@ _rtld_symlook_needed(const char *name, u
        for (n = needed; n != NULL; n = n->next) {
                if ((obj = n->obj) == NULL)
                        continue;
+               if (donelist_check(wdone, obj))
+                       continue;
                def_w = _rtld_symlook_needed(name, hash, obj->needed, &defobj1,
-                   inplt);
+                   inplt, ndone, wdone);
                if (def_w == NULL)
                        continue;
                if (def == NULL || ELF_ST_BIND(def_w->st_info) != STB_WEAK) {
@@ -381,9 +412,12 @@ _rtld_symlook_default(const char *name, 
        const Objlist_Entry *elm;
        def = NULL;
        defobj = NULL;
+       DoneList donelist;
+
+       donelist_init(&donelist);
 
        /* Look first in the referencing object if linked symbolically. */
-       if (refobj->symbolic) {
+       if (refobj->symbolic && !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 +430,7 @@ _rtld_symlook_default(const char *name, 
        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 +442,7 @@ _rtld_symlook_default(const char *name, 
        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 +457,7 @@ _rtld_symlook_default(const char *name, 
                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 +481,8 @@ _rtld_symlook_default(const char *name, 
                }
        }
 
+       donelist_clear(&donelist);
+
        if (def != NULL)
                *defobj_out = defobj;
        return def;
Index: rescue/list.ldd
===================================================================
RCS file: /cvsroot/src/rescue/list.ldd,v
retrieving revision 1.2
diff -u -p -r1.2 list.ldd
--- rescue/list.ldd     22 Aug 2009 06:52:15 -0000      1.2
+++ rescue/list.ldd     25 Feb 2010 11:09:14 -0000
@@ -8,5 +8,5 @@ LIBS    ${LDD_ELF64DIR}/libldd_elf64.a
 SPECIAL ldd    keepsymbols     _rtld_pagesz _rtld_error _rtld_trust
 SPECIAL ldd    keepsymbols     _rtld_default_paths _rtld_paths 
 SPECIAL ldd    keepsymbols     _rtld_xforms _rtld_objmain
-SPECIAL ldd    keepsymbols     _rtld_objtail _rtld_objlist
+SPECIAL ldd    keepsymbols     _rtld_objtail _rtld_objlist _rtld_objcount
 SPECIAL ldd    keepsymbols     print_needed main_local main_progname
Index: usr.bin/ldd/ldd.c
===================================================================
RCS file: /cvsroot/src/usr.bin/ldd/ldd.c,v
retrieving revision 1.13
diff -u -p -r1.13 ldd.c
--- usr.bin/ldd/ldd.c   23 Feb 2010 08:23:24 -0000      1.13
+++ usr.bin/ldd/ldd.c   25 Feb 2010 11:09:41 -0000
@@ -92,6 +92,7 @@ bool _rtld_trust;             /* False for setuid a
 Obj_Entry *_rtld_objlist;      /* Head of linked list of shared objects */
 Obj_Entry **_rtld_objtail = &_rtld_objlist;
                                /* Link field of last object in list */
+int _rtld_objcount;            /* Number of shared objects */
 Obj_Entry *_rtld_objmain;      /* The main program shared object */
 size_t _rtld_pagesz;
 


Home | Main Index | Thread Index | Old Index