path: root/elf/dl-sort-maps.c

/* Sort array of link maps according to dependencies.
   Copyright (C) 2017-2025 Free Software Foundation, Inc.
   This file is part of the GNU C Library.

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, see
   <https://www.gnu.org/licenses/>.  */

#include <assert.h>
#include <ldsodefs.h>
#include <elf/dl-tunables.h>

/* Note: this is the older, "original" sorting algorithm, being used as
   default up to 2.35.

   Sort array MAPS according to dependencies of the contained objects.
   If FOR_FINI is true, this is called for finishing an object.  */
static void
_dl_sort_maps_original (struct link_map **maps, unsigned int nmaps,
			bool force_first, bool for_fini)
{
  /* Allows caller to do the common optimization of skipping the first map,
     usually the main binary.  */
  maps += force_first;
  nmaps -= force_first;

  /* A list of one element need not be sorted.  */
  if (nmaps <= 1)
    return;

  unsigned int i = 0;
  uint16_t seen[nmaps];
  memset (seen, 0, nmaps * sizeof (seen[0]));
  while (1)
    {
      /* Keep track of which object we looked at this round.  */
      ++seen[i];
      struct link_map *thisp = maps[i];

      if (__glibc_unlikely (for_fini))
	{
	  /* Do not handle ld.so in secondary namespaces and objects which
	     are not removed.  */
	  if (thisp != thisp->l_real || thisp->l_idx == -1)
	    goto skip;
	}

      /* Find the last object in the list for which the current one is
	 a dependency and move the current object behind the object
	 with the dependency.  */
      unsigned int k = nmaps - 1;
      while (k > i)
	{
	  struct link_map **runp = maps[k]->l_initfini;
	  if (runp != NULL)
	    /* Look through the dependencies of the object.  */
	    while (*runp != NULL)
	      if (__glibc_unlikely (*runp++ == thisp))
		{
		move:
		  /* Move the current object to the back past the last
		     object with it as the dependency.  */
		  memmove (&maps[i], &maps[i + 1],
			   (k - i) * sizeof (maps[0]));
		  maps[k] = thisp;

		  if (seen[i + 1] > nmaps - i)
		    {
		      ++i;
		      goto next_clear;
		    }

		  uint16_t this_seen = seen[i];
		  memmove (&seen[i], &seen[i + 1], (k - i) * sizeof (seen[0]));
		  seen[k] = this_seen;

		  goto next;
		}

	  if (__glibc_unlikely (for_fini && maps[k]->l_reldeps != NULL))
	    {
	      unsigned int m = maps[k]->l_reldeps->act;
	      struct link_map **relmaps = &maps[k]->l_reldeps->list[0];

	      /* Look through the relocation dependencies of the object.  */
	      while (m-- > 0)
		if (__glibc_unlikely (relmaps[m] == thisp))
		  {
		    /* If a cycle exists with a link time dependency,
		       preserve the latter.  */
		    struct link_map **runp = thisp->l_initfini;
		    if (runp != NULL)
		      while (*runp != NULL)
			if (__glibc_unlikely (*runp++ == maps[k]))
			  goto ignore;
		    goto move;
		  }
	    ignore:;
	    }

	  --k;
	}

    skip:
      if (++i == nmaps)
	break;
    next_clear:
      memset (&seen[i], 0, (nmaps - i) * sizeof (seen[0]));

    next:;
    }
}

/* We use a recursive function due to its better clarity and ease of
   implementation, as well as faster execution speed. We already use
   alloca() for list allocation during the breadth-first search of
   dependencies in _dl_map_object_deps(), and this should be on the
   same order of worst-case stack usage.

   Note: the '*rpo' parameter is supposed to point to one past the
   last element of the array where we save the sort results, and is
   decremented before storing the current map at each level.  */

static void
dfs_traversal (struct link_map ***rpo, struct link_map *map,
	       bool *do_reldeps)
{
  /* _dl_map_object_deps ignores l_faked objects when calculating the
     number of maps before calling _dl_sort_maps, ignore them as well.  */
  if (map->l_visited || map->l_faked)
    return;

  map->l_visited = 1;

  if (map->l_initfini)
    {
      for (int i = 0; map->l_initfini[i] != NULL; i++)
	{
	  struct link_map *dep = map->l_initfini[i];
	  if (dep->l_visited == 0
	      && dep->l_main_map == 0)
	    dfs_traversal (rpo, dep, do_reldeps);
	}
    }

  if (__glibc_unlikely (do_reldeps != NULL && map->l_reldeps != NULL))
    {
      /* Indicate that we encountered relocation dependencies during
	 traversal.  */
      *do_reldeps = true;

      for (int m = map->l_reldeps->act - 1; m >= 0; m--)
	{
	  struct link_map *dep = map->l_reldeps->list[m];
	  if (dep->l_visited == 0
	      && dep->l_main_map == 0)
	    dfs_traversal (rpo, dep, do_reldeps);
	}
    }

  *</