Potentially related thread:

Debugging ld.so in gdb
https://sourceware.org/pipermail/gdb/2022-February/049884.html

I think the issue is _dl_map_object_deps ignores l_faked objects (set if the underlying file can't be opened at _dl_map_object):

490   for (nlist = 0, runp = known; runp; runp = runp->next)
491     {
492       if (__builtin_expect (trace_mode, 0) && runp->map->l_faked)         
493         /* This can happen when we trace the loading.  */                 
494         --map->l_searchlist.r_nlist;                                      
495       else
496         {                                                                 
497           if (runp->map == map)
498             map_index = nlist;                                            
499           map->l_searchlist.r_list[nlist++] = runp->map;                  
500         } 
501         
502       /* Now clear all the mark bits we set in the objects on the search list
503          to avoid duplicates, so the next call starts fresh.  */
504       runp->map->l_reserved = 0;
505     }    

Using the example the 'nlist' prior the call it set to 6, however after it will be 4 because of the libmissing1.so and libmissing2.so. The 'nlist' is used then on:

614   /* If libc.so.6 is the main map, it participates in the sort, so
615      that the relocation order is correct regarding libc.so.6.  */
616   _dl_sort_maps (l_initfini, nlist,
617                  (l_initfini[0] != GL (dl_ns)[l_initfini[0]->l_ns].libc_map),
618                  false);

To indicate the maximum number of link_map objects on l_initfini.  It then used on _dl_sort_maps_dfs on the stack allocated working maps:

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];

However while transversing the 'l_initfini' on dfs_traversal it will still considere the l_faked maps and thus update rpo more times than the allocated working 'rpo'.  I think the straighforward solution is just to ignore l_faked link_maps on new algorithm and there is no need to check if audit mode is set because l_faked in only set on this mode:

---
diff --git a/elf/dl-sort-maps.c b/elf/dl-sort-maps.c
index 9e9d53ec47..f049178ac3 100644
--- a/elf/dl-sort-maps.c
+++ b/elf/dl-sort-maps.c
@@ -140,7 +140,7 @@ static void
 dfs_traversal (struct link_map ***rpo, struct link_map *map,
               bool *do_reldeps)
 {
-  if (map->l_visited)
+  if (map->l_visited || map->l_faked)
     return;
 
   map->l_visited = 1;
---

With the patch applied:

$ GLIBC_TUNABLES=glibc.rtld.dynamic_sort=1 LD_LIBRARY_PATH="$PWD" LD_TRACE_LOADED_OBJECTS=1 ./elf//ld-linux-x86-64.so.2 --library-path . ./libtest.so
        linux-vdso.so.1 (0x00007ffcdad3c000)
        libexists.so.0 => ./libexists.so.0 (0x00007f371960a000)
        libc.so.6 => ./libc.so.6 (0x00007f37193eb000)
        ./elf//ld-linux-x86-64.so.2 (0x00007f3719616000)
        libmissing1.so => not found
        libmissing2.so => not found

$ GLIBC_TUNABLES=glibc.rtld.dynamic_sort=2 LD_LIBRARY_PATH="$PWD" LD_TRACE_LOADED_OBJECTS=1 ./elf//ld-linux-x86-64.so.2 --library-path . ./libtest.so
        linux-vdso.so.1 (0x00007ffd0bd51000)
        libexists.so.0 => ./libexists.so.0 (0x00007f2645d7a000)
        libc.so.6 => ./libc.so.6 (0x00007f2645b5b000)
        ./elf//ld-linux-x86-64.so.2 (0x00007f2645d86000)
        libmissing1.so => not found
        libmissing2.so => not found

(In reply to Adhemerval Zanella from comment #2)
> I think the issue is _dl_map_object_deps ignores l_faked objects (set if the
> underlying file can't be opened at _dl_map_object):

That's what I concluded as well.

I suppose we need the dependency sorting in trace mode for DL_DEBUG_UNUSED support? But maybe we can skip the sorting (and shrinking of the dependency list) altogether in tracing mode.

(In reply to Florian Weimer from comment #3)
> (In reply to Adhemerval Zanella from comment #2)
> > I think the issue is _dl_map_object_deps ignores l_faked objects (set if the
> > underlying file can't be opened at _dl_map_object):
> 
> That's what I concluded as well.
> 
> I suppose we need the dependency sorting in trace mode for DL_DEBUG_UNUSED
> support? But maybe we can skip the sorting (and shrinking of the dependency
> list) altogether in tracing mode.

I think so since loader realocated the objects in this case.  And I think it shold be ok to skip sorting for trace, I am not sure if it would be better to handle l_faked maps on _dl_sort_maps_dfs or just skip sorting for trace mode.

(In reply to Adhemerval Zanella from comment #4)
> I think so since loader realocated the objects in this case.  And I think it
> shold be ok to skip sorting for trace, I am not sure if it would be better
> to handle l_faked maps on _dl_sort_maps_dfs or just skip sorting for trace
> mode.

Are you going to send a patch? I planned to put something together tomorrow.

(In reply to Florian Weimer from comment #5)
> (In reply to Adhemerval Zanella from comment #4)
> > I think so since loader realocated the objects in this case.  And I think it
> > shold be ok to skip sorting for trace, I am not sure if it would be better
> > to handle l_faked maps on _dl_sort_maps_dfs or just skip sorting for trace
> > mode.
> 
> Are you going to send a patch? I planned to put something together tomorrow.

I will send the above fix, I think ignoring l_faked on sorting still make sense. We can discuss on maillist if this is the best approach.

*** Bug 28920 has been marked as a duplicate of this bug. ***

Fixed on master.