elf/dl-sort-maps.c

   1 /* Sort array of link maps according to dependencies.
   2    Copyright (C) 2017-2020 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 <ldsodefs.h>
  20
  21
  22 /* Sort array MAPS according to dependencies of the contained objects.
  23    Array USED, if non-NULL, is permutated along MAPS.  If FOR_FINI this is
  24    called for finishing an object.  */
  25 void
  26 _dl_sort_maps (struct link_map **maps, unsigned int nmaps, char *used,
  27                bool for_fini)
  28 {
  29   /* A list of one element need not be sorted.  */
  30   if (nmaps <= 1)
  31     return;
  32
  33   unsigned int i = 0;
  34   uint16_t seen[nmaps];
  35   memset (seen, 0, nmaps * sizeof (seen[0]));
  36   while (1)
  37     {
  38       /* Keep track of which object we looked at this round.  */
  39       ++seen[i];
  40       struct link_map *thisp = maps[i];
  41
  42       if (__glibc_unlikely (for_fini))
  43         {
  44           /* Do not handle ld.so in secondary namespaces and objects which
  45              are not removed.  */
  46           if (thisp != thisp->l_real || thisp->l_idx == -1)
  47             goto skip;
  48         }
  49
  50       /* Find the last object in the list for which the current one is
  51          a dependency and move the current object behind the object
  52          with the dependency.  */
  53       unsigned int k = nmaps - 1;
  54       while (k > i)
  55         {
  56           struct link_map **runp = maps[k]->l_initfini;
  57           if (runp != NULL)
  58             /* Look through the dependencies of the object.  */
  59             while (*runp != NULL)
  60               if (__glibc_unlikely (*runp++ == thisp))
  61                 {
  62                 move:
  63                   /* Move the current object to the back past the last
  64                      object with it as the dependency.  */
  65                   memmove (&maps[i], &maps[i + 1],
  66                            (k - i) * sizeof (maps[0]));
  67                   maps[k] = thisp;
  68
  69                   if (used != NULL)
  70                     {
  71                       char here_used = used[i];
  72                       memmove (&used[i], &used[i + 1],
  73                                (k - i) * sizeof (used[0]));
  74                       used[k] = here_used;
  75                     }
  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 }