elf/dl-sort-maps.c

   1 /* Sort array of link maps according to dependencies.
   2    Copyright (C) 2017-2023 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                         bool force_first, bool for_fini)
  31 {
  32   /* Allows caller to do the common optimization of skipping the first map,
  33      usually the main binary.  */
  34   maps += force_first;
  35   nmaps -= force_first;
  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 /* We use a recursive function due to its better clarity and ease of
 125    implementation, as well as faster execution speed. We already use
 126    alloca() for list allocation during the breadth-first search of
 127    dependencies in _dl_map_object_deps(), and this should be on the
 128    same order of worst-case stack usage.
 129
 130    Note: the '*rpo' parameter is supposed to point to one past the
 131    last element of the array where we save the sort results, and is
 132    decremented before storing the current map at each level.  */
 133
 134 static void
 135 dfs_traversal (struct link_map ***rpo, struct link_map *map,
 136                bool *do_reldeps)
 137 {
 138   /* _dl_map_object_deps ignores l_faked objects when calculating the
 139      number of maps before calling _dl_sort_maps, ignore them as well.  */
 140   if (map->l_visited || map->l_faked)
 141     return;
 142
 143   map->l_visited = 1;
 144
 145   if (map->l_initfini)
 146     {
 147       for (int i = 0; map->l_initfini[i] != NULL; i++)
 148         {
 149           struct link_map *dep = map->l_initfini[i];
 150           if (dep->l_visited == 0
 151               && dep->l_main_map == 0)
 152             dfs_traversal (rpo, dep, do_reldeps);
 153         }
 154     }
 155
 156   if (__glibc_unlikely (do_reldeps != NULL && map->l_reldeps != NULL))
 157     {
 158       /* Indicate that we encountered relocation dependencies during
 159          traversal.  */
 160       *do_reldeps = true;
 161
 162       for (int m = map->l_reldeps->act - 1; m >= 0; m--)
 163         {
 164           struct link_map *dep = map->l_reldeps->list[m];
 165           if (dep->l_visited == 0
 166               && dep->l_main_map == 0)
 167             dfs_traversal (rpo, dep, do_reldeps);
 168         }
 169     }
 170
 171   *rpo -= 1;
 172   **rpo = map;
 173 }
 174
 175 /* Topologically sort array MAPS according to dependencies of the contained
 176    objects.  */
 177
 178 static void
 179 _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps,
 180                    bool force_first, bool for_fini)
 181 {
 182   struct link_map *first_map = maps[0];
 183   for (int i = nmaps - 1; i >= 0; i--)
 184     maps[i]->l_visited = 0;
 185
 186   /* We apply DFS traversal for each of maps[i] until the whole total order
 187      is found and we're at the start of the Reverse-Postorder (RPO) sequence,
 188      which is a topological sort.
 189
 190      We go from maps[nmaps - 1] backwards towards maps[0] at this level.
 191      Due to the breadth-first search (BFS) ordering we receive, going
 192      backwards usually gives a more shallow depth-first recursion depth,
 193      adding more stack usage safety. Also, combined with the natural
 194      processing order of l_initfini[] at each node during DFS, this maintains
 195      an ordering closer to the original link ordering in the sorting results
 196      under most simpler cases.
 197
 198      Another reason we order the top level backwards, it that maps[0] is
 199      usually exactly the main object of which we're in the midst of
 200      _dl_map_object_deps() processing, and maps[0]->l_initfini[] is still
 201      blank. If we start the traversal from maps[0], since having no
 202      dependencies yet filled in, maps[0] will always be immediately
 203      incorrectly placed at the last place in the order (first in reverse).
 204      Adjusting the order so that maps[0] is last traversed naturally avoids
 205      this problem.
 206
 207      To summarize, just passing in the full list, and iterating from back
 208      to front makes things much more straightforward.  */
 209
 210   /* Array to hold RPO sorting results, before we copy back to maps[].  */
 211   struct link_map *rpo[nmaps];
 212
 213   /* The 'head' position during each DFS iteration. Note that we start at
 214      one past the last element due to first-decrement-then-store (see the
 215      bottom of above dfs_traversal() routine).  */
 216   struct link_map **rpo_head = &rpo[nmaps];
 217
 218   bool do_reldeps = false;
 219   bool *do_reldeps_ref = (for_fini ? &do_reldeps : NULL);
 220
 221   for (int i = nmaps - 1; i >= 0; i--)
 222     {
 223       dfs_traversal (&rpo_head, maps[i], do_reldeps_ref);
 224
 225       /* We can break early if all objects are already placed.  */
 226       if (rpo_head == rpo)
 227         goto end;
 228     }
 229   assert (rpo_head == rpo);
 230
 231  end:
 232   /* Here we may do a second pass of sorting, using only l_initfini[]
 233      static dependency links. This is avoided if !FOR_FINI or if we didn't
 234      find any reldeps in the first DFS traversal.
 235
 236      The reason we do this is: while it is unspecified how circular
 237      dependencies should be handled, the presumed reasonable behavior is to
 238      have destructors to respect static dependency links as much as possible,
 239      overriding reldeps if needed. And the first sorting pass, which takes
 240      l_initfini/l_reldeps links equally, may not preserve this priority.
 241
 242      Hence we do a 2nd sorting pass, taking only DT_NEEDED links into account
 243      (see how the do_reldeps argument to dfs_traversal() is NULL below).  */
 244   if (do_reldeps)
 245     {
 246       for (int i = nmaps - 1; i >= 0; i--)
 247         rpo[i]->l_visited = 0;
 248
 249       struct link_map **maps_head = &maps[nmaps];
 250       for (int i = nmaps - 1; i >= 0; i--)
 251         {
 252           dfs_traversal (&maps_head, rpo[i], NULL);
 253
 254           /* We can break early if all objects are already placed.
 255              The below memcpy is not needed in the do_reldeps case here,
 256              since we wrote back to maps[] during DFS traversal.  */
 257           if (maps_head == maps)
 258             return;
 259         }
 260       assert (maps_head == maps);
 261       return;
 262     }
 263
 264   memcpy (maps, rpo, sizeof (struct link_map *) * nmaps);
 265
 266   /* Skipping the first object at maps[0] is not valid in general,
 267      since traversing along object dependency-links may "find" that
 268      first object even when it is not included in the initial order
 269      (e.g., a dlopen'ed shared object can have circular dependencies
 270      linked back to itself).  In such a case, traversing N-1 objects
 271      will create a N-object result, and raise problems.  Instead,
 272      force the object back into first place after sorting.  This naive
 273      approach may introduce further dependency ordering violations
 274      compared to rotating the cycle until the first map is again in
 275      the first position, but as there is a cycle, at least one
 276      violation is already present.  */
 277   if (force_first && maps[0] != first_map)
 278     {
 279       int i;
 280       for (i = 0; maps[i] != first_map; ++i)
 281         ;
 282       assert (i < nmaps);
 283       memmove (&maps[1], maps, i * sizeof (maps[0]));
 284       maps[0] = first_map;
 285     }
 286 }
 287
 288 void
 289 _dl_sort_maps_init (void)
 290 {
 291   int32_t algorithm = TUNABLE_GET (glibc, rtld, dynamic_sort, int32_t, NULL);
 292   GLRO(dl_dso_sort_algo) = algorithm == 1 ? dso_sort_algorithm_original
 293                                           : dso_sort_algorithm_dfs;
 294 }
 295
 296 void
 297 _dl_sort_maps (struct link_map **maps, unsigned int nmaps,
 298                bool force_first, bool for_fini)
 299 {
 300   /* It can be tempting to use a static function pointer to store and call
 301      the current selected sorting algorithm routine, but experimentation
 302      shows that current processors still do not handle indirect branches
 303      that efficiently, plus a static function pointer will involve
 304      PTR_MANGLE/DEMANGLE, further impairing performance of small, common
 305      input cases. A simple if-case with direct function calls appears to
 306      be the fastest.  */
 307   if (__glibc_likely (GLRO(dl_dso_sort_algo) == dso_sort_algorithm_original))
 308     _dl_sort_maps_original (maps, nmaps, force_first, for_fini);
 309   else
 310     _dl_sort_maps_dfs (maps, nmaps, force_first, for_fini);
 311 }