[PATCH] elf: Sort only uninitialized objects in _dl_map_object_deps()

[Xiaoming Ni <nixiaoming@huawei.com>]

TIS ELF Version 1.2
Initialization and Termination Functions:
	1. Before the initialization code for any object A is called, the
	   initialization code for any other objects that object A depends
	   on are called.
	2. The order in which the dynamic linker calls termination functions
	   is the exact reverse order of their corresponding initialization
	   functions.
	3. The dynamic linker ensures that it will not execute any
	   initialization or termination functions more than once.

According to 1 and 2: _dl_sort_maps() is used for sorting when dlopen/dlclose.
According to 3: At dlopen, only the uninitialized objects need to be sorted.

Construct 200 dynamic libraries that depend on each other cyclically.
Run the dlopen() for each dynamic library.
Before the patch is installed, it takes 214 seconds.
After patching, it takes 37 seconds.

Signed-off-by: Xiaoming Ni <nixiaoming@huawei.com>
---
 elf/dl-deps.c | 40 +++++++++++++++++++++++++++++++++++++++-
 1 file changed, 39 insertions(+), 1 deletion(-)

diff --git a/elf/dl-deps.c b/elf/dl-deps.c
index b5a43232a7..5df1e32156 100644
--- a/elf/dl-deps.c
+++ b/elf/dl-deps.c
@@ -152,6 +152,43 @@ preload (struct list *known, unsigned int *nlist, struct link_map *map)
   map->l_reserved = 1;
 }
 
+/* TIS  ELF Version 1.2
+ * Initialization and Termination Functions:
+ * 1. Before the initialization code for any object A is called, the
+ *  initialization code for any other objects that object A depends on are called.
+ * 2. The order in which the dynamic linker calls termination functions is the
+ *  exact reverse order of their corresponding initialization functions.
+ * 3. The dynamic linker ensures that it will not execute any initialization
+ *  or termination functions more than once.
+ *
+ * According to 1 and 2, _dl_sort_maps() is used for sorting when dlopen/dlclose.
+ * According to 3, we only need to sort the uninitialized objects.
+ */
+static void
+_dl_sort_uninit_maps (struct link_map **maps, unsigned int nmaps)
+{
+  unsigned int s = 0;
+  unsigned int e = nmaps - 1;
+  struct link_map *tmp;
+
+  while (s < e)
+    {
+      while ((e > 0) && maps[e]->l_init_called)
+        e--;
+      while ((s < nmaps) && maps[s]->l_init_called == 0)
+        s++;
+      if (s >= e)
+        break;
+      tmp = maps[e];
+      maps[e] = maps[s];
+      maps[s] = tmp;
+      s++;
+      e--;
+    }
+
+  _dl_sort_maps (maps, s, NULL, false);
+}
+
 void
 _dl_map_object_deps (struct link_map *map,
 		     struct link_map **preloads, unsigned int npreloads,
@@ -611,7 +648,8 @@ Filters not supported with LD_TRACE_PRELINKING"));
     memcpy (l_initfini, map->l_searchlist.r_list,
 	    nlist * sizeof (struct link_map *));
 
-  _dl_sort_maps (&l_initfini[1], nlist - 1, NULL, false);
+  if (map->l_init_called == 0)
+    _dl_sort_uninit_maps (&l_initfini[1], nlist - 1);
 
   /* Terminate the list of dependencies.  */
   l_initfini[nlist] = NULL;
-- 
2.27.0