elf/dl-sort-maps.c

   1 /* Sort array of link maps according to dependencies.
   2    Copyright (C) 2017-2022 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    The GNU C Library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, see
  17    <https://www.gnu.org/licenses/>.  */
  18
  19 #include <assert.h>
  20 #include <ldsodefs.h>
  21 #include <elf/dl-tunables.h>
  22
  23 /* Note: this is the older, "original" sorting algorithm, being used as
  24    default up to 2.35.
  25
  26    Sort array MAPS according to dependencies of the contained objects.
  27    If FOR_FINI is true, this is called for finishing an object.  */
  28 static void
  29 _dl_sort_maps_original (struct link_map **maps, unsigned int nmaps,
  30                         unsigned int skip, bool for_fini)
  31 {
  32   /* Allows caller to do the common optimization of skipping the first map,
  33      usually the main binary.  */
  34   maps += skip;
  35   nmaps -= skip;
  36
  37   /* A list of one element need not be sorted.  */
  38   if (nmaps <= 1)
  39     return;
  40
  41   unsigned int i = 0;
  42   uint16_t seen[nmaps];
  43   memset (seen, 0, nmaps * sizeof (seen[0]));
  44   while (1)
  45     {
  46       /* Keep track of which object we looked at this round.  */
  47       ++seen[i];
  48       struct link_map *thisp = maps[i];
  49
  50       if (__glibc_unlikely (for_fini))
  51         {
  52           /* Do not handle ld.so in secondary namespaces and objects which
  53              are not removed.  */
  54           if (thisp != thisp->l_real || thisp->l_idx == -1)
  55             goto skip;
  56         }
  57
  58       /* Find the last object in the list for which the current one is
  59          a dependency and move the current object behind the object
  60          with the dependency.  */
  61       unsigned int k = nmaps - 1;
  62       while (k > i)
  63         {
  64           struct link_map **runp = maps[k]->l_initfini;
  65           if (runp != NULL)
  66             /* Look through the dependencies of the object.  */
  67             while (*runp != NULL)
  68               if (__glibc_unlikely (*runp++ == thisp))
  69                 {
  70                 move:
  71                   /* Move the current object to the back past the last
  72                      object with it as the dependency.  */
  73                   memmove (&maps[i], &maps[i + 1],
  74                            (k - i) * sizeof (maps[0]));
  75                   maps[k] = thisp;
  76
  77                   if (seen[i + 1] > nmaps - i)
  78                     {
  79                       ++i;
  80                       goto next_clear;
  81                     }
  82
  83                   uint16_t this_seen = seen[i];
  84                   memmove (&seen[i], &seen[i + 1], (k - i) * sizeof (seen[0]));
  85                   seen[k] = this_seen;
  86
  87                   goto next;
  88                 }
  89
  90           if (__glibc_unlikely (for_fini && maps[k]->l_reldeps != NULL))
  91             {
  92               unsigned int m = maps[k]->l_reldeps->act;
  93               struct link_map **relmaps = &maps[k]->l_reldeps->list[0];
  94
  95               /* Look through the relocation dependencies of the object.  */
  96               while (m-- > 0)
  97                 if (__glibc_unlikely (relmaps[m] == thisp))
  98                   {
  99                     /* If a cycle exists with a link time dependency,
 100                        preserve the latter.  */
 101                     struct link_map **runp = thisp->l_initfini;
 102                     if (runp != NULL)
 103                       while (*runp != NULL)
 104                         if (__glibc_unlikely (*runp++ == maps[k]))
 105                           goto ignore;
 106                     goto move;
 107                   }
 108             ignore:;
 109             }
 110
 111           --k;
 112         }
 113
 114     skip:
 115       if (++i == nmaps)
 116         break;
 117     next_clear:
 118       memset (&seen[i], 0, (nmaps - i) * sizeof (seen[0]));
 119
 120     next:;
 121     }
 122 }
 123
 124 #if !HAVE_TUNABLES
 125 /* In this case, just default to the original algorithm.  */
 126 strong_alias (_dl_sort_maps_original, _dl_sort_maps);
 127 #else
 128
 129 /* We use a recursive function due to its better clarity and ease of
 130    implementation, as well as faster execution speed. We already use
 131    alloca() for list allocation during the breadth-first search of
 132    dependencies in _dl_map_object_deps(), and this should be on the
 133    same order of worst-case stack usage.
 134
 135    Note: the '*rpo' parameter is supposed to point to one past the
 136    last element of the array where we save the sort results, and is
 137    decremented before storing the current map at each level.  */
 138
 139 static void
 140 dfs_traversal (struct link_map ***rpo, struct link_map *map,
 141                bool *do_reldeps)
 142 {
 143   /* _dl_map_object_deps ignores l_faked objects when calculating the
 144      number of maps before calling _dl_sort_maps, ignore them as well.  */
 145   if (map->l_visited || map->l_faked)
 146     return;
 147
 148   map->l_visited = 1;
 149
 150   if (map->l_initfini)
 151     {
 152       for (int i = 0; map->l_initfini[i] != NULL; i++)
 153         {
 154           struct link_map *dep = map->l_initfini[i];
 155           if (dep->l_visited == 0
 156               && dep->l_main_map == 0)
 157             dfs_traversal (rpo, dep, do_reldeps);
 158         }
 159     }
 160
 161   if (__glibc_unlikely (do_reldeps != NULL && map->l_reldeps != NULL))
 162     {
 163       /* Indicate that we encountered relocation dependencies during
 164          traversal.  */
 165       *do_reldeps = true;
 166
 167       for (int m = map->l_reldeps->act - 1; m >= 0; m--)
 168         {
 169           struct link_map *dep = map->l_reldeps->list[m];
 170           if (dep->l_visited == 0
 171               && dep->l_main_map == 0)
 172             dfs_traversal (rpo, dep, do_reldeps);
 173         }
 174     }
 175
 176   *rpo -= 1;
 177   **rpo = map;
 178 }
 179
 180 /* Topologically sort array MAPS according to dependencies of the contained
 181    objects.  */
 182
 183 static void
 184 _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps,
 185                    unsigned int skip __attribute__ ((unused)), bool for_fini)
 186 {
 187   for (int i = nmaps - 1; i >= 0; i--)
 188     maps[i]->l_visited = 0;
 189
 190   /* We apply DFS traversal for each of maps[i] until the whole total order
 191      is found and we're at the start of the Reverse-Postorder (RPO) sequence,
 192      which is a topological sort.
 193
 194      We go from maps[nmaps - 1] backwards towards maps[0] at this level.
 195      Due to the breadth-first search (BFS) ordering we receive, going
 196      backwards usually gives a more shallow depth-first recursion depth,
 197      adding more stack usage safety. Also, combined with the natural
 198      processing order of l_initfini[] at each node during DFS, this maintains
 199      an ordering closer to the original link ordering in the sorting results
 200      under most simpler cases.
 201
 202      Another reason we order the top level backwards, it that maps[0] is
 203      usually exactly the main object of which we're in the midst of
 204      _dl_map_object_deps() processing, and maps[0]->l_initfini[] is still
 205      blank. If we start the traversal from maps[0], since having no
 206      dependencies yet filled in, maps[0] will always be immediately
 207      incorrectly placed at the last place in the order (first in reverse).
 208      Adjusting the order so that maps[0] is last traversed naturally avoids
 209      this problem.
 210
 211      Further, the old "optimization" of skipping the main object at maps[0]
 212      from the call-site (i.e. _dl_sort_maps(maps+1,nmaps-1)) is in general
 213      no longer valid, since traversing along object dependency-links
 214      may "find" the main object even when it is not included in the initial
 215      order (e.g. a dlopen()'ed shared object can have circular dependencies
 216      linked back to itself). In such a case, traversing N-1 objects will
 217      create a N-object result, and raise problems.
 218
 219      To summarize, just passing in the full list, and iterating from back
 220      to front makes things much more straightforward.  */
 221
 222   /* Array to hold RPO sorting results, before we copy back to maps[].  */
 223   struct link_map *rpo[nmaps];
 224
 225   /* The 'head' position during each DFS iteration. Note that we start at
 226      one past the last element due to first-decrement-then-store (see the
 227      bottom of above dfs_traversal() routine).  */
 228   struct link_map **rpo_head = &rpo[nmaps];
 229
 230   bool do_reldeps = false;
 231   bool *do_reldeps_ref = (for_fini ? &do_reldeps : NULL);
 232
 233   for (int i = nmaps - 1; i >= 0; i--)
 234     {
 235       dfs_traversal (&rpo_head, maps[i], do_reldeps_ref);
 236
 237       /* We can break early if all objects are already placed.  */
 238       if (rpo_head == rpo)
 239         goto end;
 240     }
 241   assert (rpo_head == rpo);
 242
 243  end:
 244   /* Here we may do a second pass of sorting, using only l_initfini[]
 245      static dependency links. This is avoided if !FOR_FINI or if we didn't
 246      find any reldeps in the first DFS traversal.
 247
 248      The reason we do this is: while it is unspecified how circular
 249      dependencies should be handled, the presumed reasonable behavior is to
 250      have destructors to respect static dependency links as much as possible,
 251      overriding reldeps if needed. And the first sorting pass, which takes
 252      l_initfini/l_reldeps links equally, may not preserve this priority.
 253
 254      Hence we do a 2nd sorting pass, taking only DT_NEEDED links into account
 255      (see how the do_reldeps argument to dfs_traversal() is NULL below).  */
 256   if (do_reldeps)
 257     {
 258       for (int i = nmaps - 1; i >= 0; i--)
 259         rpo[i]->l_visited = 0;
 260
 261       struct link_map **maps_head = &maps[nmaps];
 262       for (int i = nmaps - 1; i >= 0; i--)
 263         {
 264           dfs_traversal (&maps_head, rpo[i], NULL);
 265
 266           /* We can break early if all objects are already placed.
 267              The below memcpy is not needed in the do_reldeps case here,
 268              since we wrote back to maps[] during DFS traversal.  */
 269           if (maps_head == maps)
 270             return;
 271         }
 272       assert (maps_head == maps);
 273       return;
 274     }
 275
 276   memcpy (maps, rpo, sizeof (struct link_map *) * nmaps);
 277 }
 278
 279 void
 280 _dl_sort_maps_init (void)
 281 {
 282   int32_t algorithm = TUNABLE_GET (glibc, rtld, dynamic_sort, int32_t, NULL);
 283   GLRO(dl_dso_sort_algo) = algorithm == 1 ? dso_sort_algorithm_original
 284                                           : dso_sort_algorithm_dfs;
 285 }
 286
 287 void
 288 _dl_sort_maps (struct link_map **maps, unsigned int nmaps,
 289                unsigned int skip, bool for_fini)
 290 {
 291   /* It can be tempting to use a static function pointer to store and call
 292      the current selected sorting algorithm routine, but experimentation
 293      shows that current processors still do not handle indirect branches
 294      that efficiently, plus a static function pointer will involve
 295      PTR_MANGLE/DEMANGLE, further impairing performance of small, common
 296      input cases. A simple if-case with direct function calls appears to
 297      be the fastest.  */
 298   if (__glibc_likely (GLRO(dl_dso_sort_algo) == dso_sort_algorithm_original))
 299     _dl_sort_maps_original (maps, nmaps, skip, for_fini);
 300   else
 301     _dl_sort_maps_dfs (maps, nmaps, skip, for_fini);
 302 }
 303
 304 #endif /* HAVE_TUNABLES.  */