elf/dl-find_object.c

   1 /* Locating objects in the process image.  ld.so implementation.
   2    Copyright (C) 2021-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 <atomic.h>
  21 #include <atomic_wide_counter.h>
  22 #include <dl-find_object.h>
  23 #include <dlfcn.h>
  24 #include <ldsodefs.h>
  25 #include <link.h>
  26 #include <stdbool.h>
  27 #include <stddef.h>
  28 #include <stdint.h>
  29
  30 /* Fallback implementation of _dl_find_object.  It uses a linear
  31    search, needs locking, and is not async-signal-safe.  It is used in
  32    _dl_find_object prior to initialization, when called from audit
  33    modules.  It also serves as the reference implementation for
  34    _dl_find_object.  */
  35 static int
  36 _dl_find_object_slow (void *pc, struct dl_find_object *result)
  37 {
  38   ElfW(Addr) addr = (ElfW(Addr)) pc;
  39   for (Lmid_t ns = 0; ns < GL(dl_nns); ++ns)
  40     for (struct link_map *l = GL(dl_ns)[ns]._ns_loaded; l != NULL;
  41          l = l->l_next)
  42       if (addr >= l->l_map_start && addr < l->l_map_end
  43           && (l->l_contiguous || _dl_addr_inside_object (l, addr)))
  44         {
  45           assert (ns == l->l_ns);
  46           struct dl_find_object_internal internal;
  47           _dl_find_object_from_map (l, &internal);
  48           _dl_find_object_to_external (&internal, result);
  49           return 1;
  50         }
  51
  52   /* Object not found.  */
  53   return -1;
  54 }
  55
  56 /* Data for the main executable.  There is usually a large gap between
  57    the main executable and initially loaded shared objects.  Record
  58    the main executable separately, to increase the chance that the
  59    range for the non-closeable mappings below covers only the shared
  60    objects (and not also the gap between main executable and shared
  61    objects).  */
  62 static struct dl_find_object_internal _dlfo_main attribute_relro;
  63
  64 /* Data for initially loaded shared objects that cannot be unloaded.
  65    (This may also contain non-contiguous mappings from the main
  66    executable.)  The mappings are stored in address order in the
  67    _dlfo_nodelete_mappings array (containing
  68    _dlfo_nodelete_mappings_size elements).  It is not modified after
  69    initialization.  */
  70 static uintptr_t _dlfo_nodelete_mappings_end attribute_relro;
  71 static size_t _dlfo_nodelete_mappings_size attribute_relro;
  72 static struct dl_find_object_internal *_dlfo_nodelete_mappings
  73   attribute_relro;
  74
  75 /* Mappings created by dlopen can go away with dlclose, so a dynamic
  76    data structure with some synchronization is needed.  Individual
  77    segments are similar to the _dlfo_nodelete_mappings array above.
  78    The previous segment contains lower addresses and is at most half
  79    as long.  Checking the address of the base address of the first
  80    element during a lookup can therefore approximate a binary search
  81    over all segments, even though the data is not stored in one
  82    contiguous array.
  83
  84    During updates, the segments are overwritten in place.  A software
  85    transactional memory construct (involving the
  86    _dlfo_loaded_mappings_version variable) is used to detect
  87    concurrent modification, and retry as necessary.  (This approach is
  88    similar to seqlocks, except that two copies are used, and there is
  89    only one writer, ever, due to the loader lock.)  Technically,
  90    relaxed MO loads and stores need to be used for the shared TM data,
  91    to avoid data races.
  92
  93    The memory allocations are never deallocated, but slots used for
  94    objects that have been dlclose'd can be reused by dlopen.  The
  95    memory can live in the regular C malloc heap.
  96
  97    The segments are populated from the start of the list, with the
  98    mappings with the highest address.  Only if this segment is full,
  99    previous segments are used for mappings at lower addresses.  The
 100    remaining segments are populated as needed, but after allocating
 101    further segments, some of the initial segments (at the end of the
 102    linked list) can be empty (with size 0).
 103
 104    Adding new elements to this data structure is another source of
 105    quadratic behavior for dlopen.  If the other causes of quadratic
 106    behavior are eliminated, a more complicated data structure will be
 107    needed.  */
 108 struct dlfo_mappings_segment
 109 {
 110   /* The previous segment has lower base addresses.  Constant after
 111      initialization; read in the TM region.  */
 112   struct dlfo_mappings_segment *previous;
 113
 114   /* Used by __libc_freeres to deallocate malloc'ed memory.  */
 115   void *to_free;
 116
 117   /* Count of array elements in use and allocated.  */
 118   size_t size;                  /* Read in the TM region.  */
 119   size_t allocated;
 120
 121   struct dl_find_object_internal objects[]; /* Read in the TM region.  */
 122 };
 123
 124 /* To achieve async-signal-safety, two copies of the data structure
 125    are used, so that a signal handler can still use this data even if
 126    dlopen or dlclose modify the other copy.  The the least significant
 127    bit in _dlfo_loaded_mappings_version determines which array element
 128    is the currently active region.  */
 129 static struct dlfo_mappings_segment *_dlfo_loaded_mappings[2];
 130
 131 /* Returns the number of actually used elements in all segments
 132    starting at SEG.  */
 133 static inline size_t
 134 _dlfo_mappings_segment_count_used (struct dlfo_mappings_segment *seg)
 135 {
 136   size_t count = 0;
 137   for (; seg != NULL && seg->size > 0; seg = seg->previous)
 138     for (size_t i = 0; i < seg->size; ++i)
 139       /* Exclude elements which have been dlclose'd.  */
 140       count += seg->objects[i].map != NULL;
 141   return count;
 142 }
 143
 144 /* Compute the total number of available allocated segments linked
 145    from SEG.  */
 146 static inline size_t
 147 _dlfo_mappings_segment_count_allocated (struct dlfo_mappings_segment *seg)
 148 {
 149   size_t count = 0;
 150   for (; seg != NULL; seg = seg->previous)
 151     count += seg->allocated;
 152   return count;
 153 }
 154
 155 /* This is essentially an arbitrary value.  dlopen allocates plenty of
 156    memory anyway, so over-allocated a bit does not hurt.  Not having
 157    many small-ish segments helps to avoid many small binary searches.
 158    Not using a power of 2 means that we do not waste an extra page
 159    just for the malloc header if a mapped allocation is used in the
 160    glibc allocator.  */
 161 enum { dlfo_mappings_initial_segment_size = 63 };
 162
 163 /* Allocate an empty segment.  This used for the first ever
 164    allocation.  */
 165 static struct dlfo_mappings_segment *
 166 _dlfo_mappings_segment_allocate_unpadded (size_t size)
 167 {
 168   if (size < dlfo_mappings_initial_segment_size)
 169     size = dlfo_mappings_initial_segment_size;
 170   /* No overflow checks here because the size is a mapping count, and
 171      struct link_map is larger than what we allocate here.  */
 172   enum
 173     {
 174       element_size = sizeof ((struct dlfo_mappings_segment) {}.objects[0])
 175     };
 176   size_t to_allocate = (sizeof (struct dlfo_mappings_segment)
 177                         + size * element_size);
 178   struct dlfo_mappings_segment *result = malloc (to_allocate);
 179   if (result != NULL)
 180     {
 181       result->previous = NULL;
 182       result->to_free = NULL; /* Minimal malloc memory cannot be freed.  */
 183       result->size = 0;
 184       result->allocated = size;
 185     }
 186   return result;
 187 }
 188
 189 /* Allocate an empty segment that is at least SIZE large.  PREVIOUS
 190    points to the chain of previously allocated segments and can be
 191    NULL.  */
 192 static struct dlfo_mappings_segment *
 193 _dlfo_mappings_segment_allocate (size_t size,
 194                                  struct dlfo_mappings_segment * previous)
 195 {
 196   /* Exponential sizing policies, so that lookup approximates a binary
 197      search.  */
 198   {
 199     size_t minimum_growth;
 200     if (previous == NULL)
 201       minimum_growth = dlfo_mappings_initial_segment_size;
 202     else
 203       minimum_growth = 2* previous->allocated;
 204     if (size < minimum_growth)
 205       size = minimum_growth;
 206   }
 207   enum { cache_line_size_estimate = 128 };
 208   /* No overflow checks here because the size is a mapping count, and
 209      struct link_map is larger than what we allocate here.  */
 210   enum
 211     {
 212       element_size = sizeof ((struct dlfo_mappings_segment) {}.objects[0])
 213     };
 214   size_t to_allocate = (sizeof (struct dlfo_mappings_segment)
 215                         + size * element_size
 216                         + 2 * cache_line_size_estimate);
 217   char *ptr = malloc (to_allocate);
 218   if (ptr == NULL)
 219     return NULL;
 220   char *original_ptr = ptr;
 221   /* Start and end at a (conservative) 128-byte cache line boundary.
 222      Do not use memalign for compatibility with partially interposing
 223      malloc implementations.  */
 224   char *end = PTR_ALIGN_DOWN (ptr + to_allocate, cache_line_size_estimate);
 225   ptr = PTR_ALIGN_UP (ptr, cache_line_size_estimate);
 226   struct dlfo_mappings_segment *result
 227     = (struct dlfo_mappings_segment *) ptr;
 228   result->previous = previous;
 229   result->to_free = original_ptr;
 230   result->size = 0;
 231   /* We may have obtained slightly more space if malloc happened
 232      to provide an over-aligned pointer.  */
 233   result->allocated = (((uintptr_t) (end - ptr)
 234                         - sizeof (struct dlfo_mappings_segment))
 235                        / element_size);
 236   assert (result->allocated >= size);
 237   return result;
 238 }
 239
 240 /* Monotonic counter for software transactional memory.  The lowest
 241    bit indicates which element of the _dlfo_loaded_mappings contains
 242    up-to-date data.  */
 243 static __atomic_wide_counter _dlfo_loaded_mappings_version;
 244
 245 /* TM version at the start of the read operation.  */
 246 static inline uint64_t
 247 _dlfo_read_start_version (void)
 248 {
 249   /* Acquire MO load synchronizes with the fences at the beginning and
 250      end of the TM update region in _dlfo_mappings_begin_update,
 251      _dlfo_mappings_end_update.  */
 252   return __atomic_wide_counter_load_acquire (&_dlfo_loaded_mappings_version);
 253 }
 254
 255 /* Optimized variant of _dlfo_read_start_version which can be called
 256    when the loader is write-locked.  */
 257 static inline uint64_t
 258 _dlfo_read_version_locked (void)
 259 {
 260   return __atomic_wide_counter_load_relaxed (&_dlfo_loaded_mappings_version);
 261 }
 262
 263 /* Update the version to reflect that an update is happening.  This
 264    does not change the bit that controls the active segment chain.  */
 265 static inline void
 266 _dlfo_mappings_begin_update (void)
 267 {
 268   /* The fence synchronizes with loads in _dlfo_read_start_version
 269      (also called from _dlfo_read_success).  */
 270   atomic_thread_fence_release ();
 271 }
 272
 273 /* Installs the just-updated version as the active version.  */
 274 static inline void
 275 _dlfo_mappings_end_update (void)
 276 {
 277   /* The fence synchronizes with loads in _dlfo_read_start_version
 278      (also called from _dlfo_read_success).  */
 279   atomic_thread_fence_release ();
 280   /* No atomic read-modify-write update needed because of the loader
 281      lock.  */
 282   __atomic_wide_counter_add_relaxed (&_dlfo_loaded_mappings_version, 1);
 283 }
 284
 285 /* Return true if the read was successful, given the start
 286    version.  */
 287 static inline bool
 288 _dlfo_read_success (uint64_t start_version)
 289 {
 290   /* See Hans Boehm, Can Seqlocks Get Along with Programming Language
 291      Memory Models?, Section 4.  This is necessary so that loads in
 292      the TM region are not ordered past the version check below.  */
 293   atomic_thread_fence_acquire ();
 294
 295   /* Synchronizes with the fences in _dlfo_mappings_begin_update,
 296      _dlfo_mappings_end_update.  It is important that all stores from
 297      the last update have become visible, and stores from the next
 298      update to this version are not before the version number is
 299      updated.
 300
 301      Unlike with seqlocks, there is no check for odd versions here
 302      because we have read the unmodified copy (confirmed to be
 303      unmodified by the unchanged version).  */
 304   return _dlfo_read_start_version () == start_version;
 305 }
 306
 307 /* Returns the active segment identified by the specified start
 308    version.  */
 309 static struct dlfo_mappings_segment *
 310 _dlfo_mappings_active_segment (uint64_t start_version)
 311 {
 312   return _dlfo_loaded_mappings[start_version & 1];
 313 }
 314
 315 /* Searches PC amoung the address-sorted array [FIRST1, FIRST1 +
 316    SIZE).  Assumes PC >= FIRST1->map_start.  Returns a pointer to the
 317    element that contains PC, or NULL if there is no such element.  */
 318 static inline struct dl_find_object_internal *
 319 _dlfo_lookup (uintptr_t pc, struct dl_find_object_internal *first1, size_t size)
 320 {
 321   struct dl_find_object_internal *end = first1 + size;
 322
 323   /* Search for a lower bound in first.  */
 324   struct dl_find_object_internal *first = first1;
 325   while (size > 0)
 326     {
 327       size_t half = size >> 1;
 328       struct dl_find_object_internal *middle = first + half;
 329       if (atomic_load_relaxed (&middle->map_start) < pc)
 330         {
 331           first = middle + 1;
 332           size -= half + 1;
 333         }
 334       else
 335         size = half;
 336     }
 337
 338   if (first != end && pc == atomic_load_relaxed (&first->map_start))
 339     {
 340       if (pc < atomic_load_relaxed (&first->map_end))
 341         return first;
 342       else
 343         /* Zero-length mapping after dlclose.  */
 344         return NULL;
 345     }
 346   else
 347     {
 348       /* Check to see if PC is in the previous mapping.  */
 349       --first;
 350       if (pc < atomic_load_relaxed (&first->map_end))
 351         /* pc >= first->map_start implied by the search above.  */
 352         return first;
 353       else
 354         return NULL;
 355     }
 356 }
 357
 358 int
 359 _dl_find_object (void *pc1, struct dl_find_object *result)
 360 {
 361   uintptr_t pc = (uintptr_t) pc1;
 362
 363   if (__glibc_unlikely (_dlfo_main.map_end == 0))
 364     {
 365       /* Not initialized.  No locking is needed here because this can
 366          only be called from audit modules, which cannot create
 367          threads.  */
 368       return _dl_find_object_slow (pc1, result);
 369     }
 370
 371   /* Main executable.  */
 372   if (pc >= _dlfo_main.map_start && pc < _dlfo_main.map_end)
 373     {
 374       _dl_find_object_to_external (&_dlfo_main, result);
 375       return 0;
 376     }
 377
 378   /* Other initially loaded objects.  */
 379   if (pc >= _dlfo_nodelete_mappings->map_start
 380       && pc < _dlfo_nodelete_mappings_end)
 381     {
 382       struct dl_find_object_internal *obj
 383         = _dlfo_lookup (pc, _dlfo_nodelete_mappings,
 384                         _dlfo_nodelete_mappings_size);
 385       if (obj != NULL)
 386         {
 387           _dl_find_object_to_external (obj, result);
 388           return 0;
 389         }
 390       /* Fall through to the full search.  The kernel may have mapped
 391          the initial mappings with gaps that are later filled by
 392          dlopen with other mappings.  */
 393     }
 394
 395   /* Handle audit modules, dlopen, dlopen objects.  This uses software
 396      transactional memory, with a retry loop in case the version
 397      changes during execution.  */
 398   while (true)
 399     {
 400     retry:
 401       ;
 402       uint64_t start_version = _dlfo_read_start_version ();
 403
 404       /* The read through seg->previous assumes that the CPU
 405          recognizes the load dependency, so that no invalid size
 406          values is read.  Furthermore, the code assumes that no
 407          out-of-thin-air value for seg->size is observed.  Together,
 408          this ensures that the observed seg->size value is always less
 409          than seg->allocated, so that _dlfo_mappings_index does not
 410          read out-of-bounds.  (This avoids intermediate TM version
 411          verification.  A concurrent version update will lead to
 412          invalid lookup results, but not to out-of-memory access.)
 413
 414          Either seg == NULL or seg->size == 0 terminates the segment
 415          list.  _dl_find_object_update does not bother to clear the
 416          size on earlier unused segments.  */
 417       for (struct dlfo_mappings_segment *seg
 418              = _dlfo_mappings_active_segment (start_version);
 419            seg != NULL;
 420            seg = atomic_load_acquire (&seg->previous))
 421         {
 422           size_t seg_size = atomic_load_relaxed (&seg->size);
 423           if (seg_size == 0)
 424             break;
 425
 426           if (pc >= atomic_load_relaxed (&seg->objects[0].map_start))
 427             {
 428               /* PC may lie within this segment.  If it is less than the
 429                  segment start address, it can only lie in a previous
 430                  segment, due to the base address sorting.  */
 431               struct dl_find_object_internal *obj
 432                 = _dlfo_lookup (pc, seg->objects, seg_size);
 433
 434               if (obj != NULL)
 435                 {
 436                   /* Found the right mapping.  Copy out the data prior to
 437                      checking if the read transaction was successful.  */
 438                   struct dl_find_object_internal copy;
 439                   _dl_find_object_internal_copy (obj, &copy);
 440                   if (_dlfo_read_success (start_version))
 441                     {
 442                       _dl_find_object_to_external (&copy, result);
 443                       return 0;
 444                     }
 445                   else
 446                     /* Read transaction failure.  */
 447                     goto retry;
 448                 }
 449               else
 450                 {
 451                   /* PC is not covered by this mapping.  */
 452                   if (_dlfo_read_success (start_version))
 453                     return -1;
 454                   else
 455                     /* Read transaction failure.  */
 456                     goto retry;
 457                 }
 458             } /* if: PC might lie within the current seg.  */
 459         }
 460
 461       /* PC is not covered by any segment.  */
 462       if (_dlfo_read_success (start_version))
 463         return -1;
 464     } /* Transaction retry loop.  */
 465 }
 466 rtld_hidden_def (_dl_find_object)
 467
 468 /* _dlfo_process_initial is called twice.  First to compute the array
 469    sizes from the initial loaded mappings.  Second to fill in the
 470    bases and infos arrays with the (still unsorted) data.  Returns the
 471    number of loaded (non-nodelete) mappings.  */
 472 static size_t
 473 _dlfo_process_initial (void)
 474 {
 475   struct link_map *main_map = GL(dl_ns)[LM_ID_BASE]._ns_loaded;
 476
 477   size_t nodelete = 0;
 478   if (!main_map->l_contiguous)
 479     {
 480       struct dl_find_object_internal dlfo;
 481       _dl_find_object_from_map (main_map, &dlfo);
 482
 483       /* PT_LOAD segments for a non-contiguous are added to the
 484          non-closeable mappings.  */
 485       for (const ElfW(Phdr) *ph = main_map->l_phdr,
 486              *ph_end = main_map->l_phdr + main_map->l_phnum;
 487            ph < ph_end; ++ph)
 488         if (ph->p_type == PT_LOAD)
 489           {
 490             if (_dlfo_nodelete_mappings != NULL)
 491               {
 492                 /* Second pass only.  */
 493                 _dlfo_nodelete_mappings[nodelete] = dlfo;
 494                 _dlfo_nodelete_mappings[nodelete].map_start
 495                   = ph->p_vaddr + main_map->l_addr;
 496                 _dlfo_nodelete_mappings[nodelete].map_end
 497                   = _dlfo_nodelete_mappings[nodelete].map_start + ph->p_memsz;
 498               }
 499             ++nodelete;
 500           }
 501     }
 502
 503   size_t loaded = 0;
 504   for (Lmid_t ns = 0; ns < GL(dl_nns); ++ns)
 505     for (struct link_map *l = GL(dl_ns)[ns]._ns_loaded; l != NULL;
 506          l = l->l_next)
 507       /* Skip the main map processed above, and proxy maps.  */
 508       if (l != main_map && l == l->l_real)
 509         {
 510           /* lt_library link maps are implicitly NODELETE.  */
 511           if (l->l_type == lt_library || l->l_nodelete_active)
 512             {
 513               if (_dlfo_nodelete_mappings != NULL)
 514                 /* Second pass only.  */
 515                 _dl_find_object_from_map
 516                   (l, _dlfo_nodelete_mappings + nodelete);
 517               ++nodelete;
 518             }
 519           else if (l->l_type == lt_loaded)
 520             {
 521               if (_dlfo_loaded_mappings[0] != NULL)
 522                 /* Second pass only.  */
 523                 _dl_find_object_from_map
 524                   (l, &_dlfo_loaded_mappings[0]->objects[loaded]);
 525               ++loaded;
 526             }
 527         }
 528
 529   _dlfo_nodelete_mappings_size = nodelete;
 530   return loaded;
 531 }
 532
 533 /* Selection sort based on mapping start address.  */
 534 void
 535 _dlfo_sort_mappings (struct dl_find_object_internal *objects, size_t size)
 536 {
 537   if (size < 2)
 538     return;
 539
 540   for (size_t i = 0; i < size - 1; ++i)
 541     {
 542       /* Find minimum.  */
 543       size_t min_idx = i;
 544       uintptr_t min_val = objects[i].map_start;
 545       for (size_t j = i + 1; j < size; ++j)
 546         if (objects[j].map_start < min_val)
 547           {
 548             min_idx = j;
 549             min_val = objects[j].map_start;
 550           }
 551
 552       /* Swap into place.  */
 553       struct dl_find_object_internal tmp = objects[min_idx];
 554       objects[min_idx] = objects[i];
 555       objects[i] = tmp;
 556     }
 557 }
 558
 559 void
 560 _dl_find_object_init (void)
 561 {
 562   /* Cover the main mapping.  */
 563   {
 564     struct link_map *main_map = GL(dl_ns)[LM_ID_BASE]._ns_loaded;
 565
 566     if (main_map->l_contiguous)
 567       _dl_find_object_from_map (main_map, &_dlfo_main);
 568     else
 569       {
 570         /* Non-contiguous main maps are handled in
 571            _dlfo_process_initial.  Mark as initialized, but not
 572            coverying any valid PC.  */
 573         _dlfo_main.map_start = -1;
 574         _dlfo_main.map_end = -1;
 575       }
 576   }
 577
 578   /* Allocate the data structures.  */
 579   size_t loaded_size = _dlfo_process_initial ();
 580   _dlfo_nodelete_mappings = malloc (_dlfo_nodelete_mappings_size
 581                                     * sizeof (*_dlfo_nodelete_mappings));
 582   if (loaded_size > 0)
 583     _dlfo_loaded_mappings[0]
 584       = _dlfo_mappings_segment_allocate_unpadded (loaded_size);
 585   if (_dlfo_nodelete_mappings == NULL
 586       || (loaded_size > 0 && _dlfo_loaded_mappings[0] == NULL))
 587     _dl_fatal_printf ("\
 588 Fatal glibc error: cannot allocate memory for find-object data\n");
 589   /* Fill in the data with the second call.  */
 590   _dlfo_nodelete_mappings_size = 0;
 591   _dlfo_process_initial ();
 592
 593   /* Sort both arrays.  */
 594   if (_dlfo_nodelete_mappings_size > 0)
 595     {
 596       _dlfo_sort_mappings (_dlfo_nodelete_mappings,
 597                            _dlfo_nodelete_mappings_size);
 598       size_t last_idx = _dlfo_nodelete_mappings_size - 1;
 599       _dlfo_nodelete_mappings_end = _dlfo_nodelete_mappings[last_idx].map_end;
 600     }
 601   if (loaded_size > 0)
 602     _dlfo_sort_mappings (_dlfo_loaded_mappings[0]->objects,
 603                          _dlfo_loaded_mappings[0]->size);
 604 }
 605
 606 static void
 607 _dl_find_object_link_map_sort (struct link_map **loaded, size_t size)
 608 {
 609   /* Selection sort based on map_start.  */
 610   if (size < 2)
 611     return;
 612   for (size_t i = 0; i < size - 1; ++i)
 613     {
 614       /* Find minimum.  */
 615       size_t min_idx = i;
 616       ElfW(Addr) min_val = loaded[i]->l_map_start;
 617       for (size_t j = i + 1; j < size; ++j)
 618         if (loaded[j]->l_map_start < min_val)
 619           {
 620             min_idx = j;
 621             min_val = loaded[j]->l_map_start;
 622           }
 623
 624       /* Swap into place.  */
 625       struct link_map *tmp = loaded[min_idx];
 626       loaded[min_idx] = loaded[i];
 627       loaded[i] = tmp;
 628     }
 629 }
 630
 631 /* Initializes the segment for writing.  Returns the target write
 632    index (plus 1) in this segment.  The index is chosen so that a
 633    partially filled segment still has data at index 0.  */
 634 static inline size_t
 635 _dlfo_update_init_seg (struct dlfo_mappings_segment *seg,
 636                        size_t remaining_to_add)
 637 {
 638   size_t new_seg_size;
 639   if (remaining_to_add < seg->allocated)
 640     /* Partially filled segment.  */
 641     new_seg_size = remaining_to_add;
 642   else
 643     new_seg_size = seg->allocated;
 644   atomic_store_relaxed (&seg->size, new_seg_size);
 645   return new_seg_size;
 646 }
 647
 648 /* Invoked from _dl_find_object_update after sorting.  Stores to the
 649    shared data need to use relaxed MO.  But plain loads can be used
 650    because the loader lock prevents concurrent stores.  */
 651 static bool
 652 _dl_find_object_update_1 (struct link_map **loaded, size_t count)
 653 {
 654   int active_idx = _dlfo_read_version_locked () & 1;
 655
 656   struct dlfo_mappings_segment *current_seg
 657     = _dlfo_loaded_mappings[active_idx];
 658   size_t current_used = _dlfo_mappings_segment_count_used (current_seg);
 659
 660   struct dlfo_mappings_segment *target_seg
 661     = _dlfo_loaded_mappings[!active_idx];
 662   size_t remaining_to_add = current_used + count;
 663
 664   /* Ensure that the new segment chain has enough space.  */
 665   {
 666     size_t new_allocated
 667       = _dlfo_mappings_segment_count_allocated (target_seg);
 668     if (new_allocated < remaining_to_add)
 669       {
 670         size_t more = remaining_to_add - new_allocated;
 671         target_seg = _dlfo_mappings_segment_allocate (more, target_seg);
 672         if (target_seg == NULL)
 673           /* Out of memory.  Do not end the update and keep the
 674              current version unchanged.  */
 675           return false;
 676
 677         /* Start update cycle. */
 678         _dlfo_mappings_begin_update ();
 679
 680         /* The barrier ensures that a concurrent TM read or fork does
 681            not see a partially initialized segment.  */
 682         atomic_store_release (&_dlfo_loaded_mappings[!active_idx], target_seg);
 683       }
 684     else
 685       /* Start update cycle without allocation.  */
 686       _dlfo_mappings_begin_update ();
 687   }
 688
 689   size_t target_seg_index1 = _dlfo_update_init_seg (target_seg,
 690                                                     remaining_to_add);
 691
 692   /* Merge the current_seg segment list with the loaded array into the
 693      target_set.  Merging occurs backwards, in decreasing l_map_start
 694      order.  */
 695   size_t loaded_index1 = count;
 696   size_t current_seg_index1;
 697   if (current_seg == NULL)
 698     current_seg_index1 = 0;
 699   else
 700     current_seg_index1 = current_seg->size;
 701   while (true)
 702     {
 703       if (current_seg_index1 == 0)
 704         {
 705           /* Switch to the previous segment.  */
 706           if (current_seg != NULL)
 707             current_seg = current_seg->previous;
 708           if (current_seg != NULL)
 709             {
 710               current_seg_index1 = current_seg->size;
 711               if (current_seg_index1 == 0)
 712                 /* No more data in previous segments.  */
 713                 current_seg = NULL;
 714             }
 715         }
 716
 717       if (current_seg != NULL
 718           && (current_seg->objects[current_seg_index1 - 1].map == NULL))
 719         {
 720           /* This mapping has been dlclose'd.  Do not copy it.  */
 721           --current_seg_index1;
 722           continue;
 723         }
 724
 725       if (loaded_index1 == 0 && current_seg == NULL)
 726         /* No more data in either source.  */
 727         break;
 728
 729       /* Make room for another mapping.  */
 730       assert (remaining_to_add > 0);
 731       if (target_seg_index1 == 0)
 732         {
 733           /* Switch segments and set the size of the segment.  */
 734           target_seg = target_seg->previous;
 735           target_seg_index1 = _dlfo_update_init_seg (target_seg,
 736                                                      remaining_to_add);
 737         }
 738
 739       /* Determine where to store the data.  */
 740       struct dl_find_object_internal *dlfo
 741         = &target_seg->objects[target_seg_index1 - 1];
 742
 743       if (loaded_index1 == 0
 744           || (current_seg != NULL
 745               && (loaded[loaded_index1 - 1]->l_map_start
 746                   < current_seg->objects[current_seg_index1 - 1].map_start)))
 747         {
 748           /* Prefer mapping in current_seg.  */
 749           assert (current_seg_index1 > 0);
 750           _dl_find_object_internal_copy
 751             (&current_seg->objects[current_seg_index1 - 1], dlfo);
 752           --current_seg_index1;
 753         }
 754       else
 755         {
 756           /* Prefer newly loaded link map.  */
 757           assert (loaded_index1 > 0);
 758           _dl_find_object_from_map (loaded[loaded_index1 - 1], dlfo);
 759           loaded[loaded_index1 -  1]->l_find_object_processed = 1;
 760           --loaded_index1;
 761         }
 762
 763       /* Consume space in target segment.  */
 764       --target_seg_index1;
 765
 766       --remaining_to_add;
 767     }
 768
 769   /* Everything has been added.  */
 770   assert (remaining_to_add == 0);
 771
 772   /* The segment must have been filled up to the beginning.  */
 773   assert (target_seg_index1 == 0);
 774
 775   /* Prevent searching further into unused segments.  */
 776   if (target_seg->previous != NULL)
 777     atomic_store_relaxed (&target_seg->previous->size, 0);
 778
 779   _dlfo_mappings_end_update ();
 780   return true;
 781 }
 782
 783 bool
 784 _dl_find_object_update (struct link_map *new_map)
 785 {
 786   /* Copy the newly-loaded link maps into an array for sorting.  */
 787   size_t count = 0;
 788   for (struct link_map *l = new_map; l != NULL; l = l->l_next)
 789     /* Skip proxy maps and already-processed maps.  */
 790     count += l == l->l_real && !l->l_find_object_processed;
 791   if (count == 0)
 792     return true;
 793
 794   struct link_map **map_array = malloc (count * sizeof (*map_array));
 795   if (map_array == NULL)
 796     return false;
 797   {
 798     size_t i = 0;
 799     for (struct link_map *l = new_map; l != NULL; l = l->l_next)
 800       if (l == l->l_real && !l->l_find_object_processed)
 801         map_array[i++] = l;
 802   }
 803
 804   _dl_find_object_link_map_sort (map_array, count);
 805   bool ok = _dl_find_object_update_1 (map_array, count);
 806   free (map_array);
 807   return ok;
 808 }
 809
 810 void
 811 _dl_find_object_dlclose (struct link_map *map)
 812 {
 813   uint64_t start_version = _dlfo_read_version_locked ();
 814   uintptr_t map_start = map->l_map_start;
 815
 816
 817   /* Directly patch the size information in the mapping to mark it as
 818      unused.  See the parallel lookup logic in _dl_find_object.  Do
 819      not check for previous dlclose at the same mapping address
 820      because that cannot happen (there would have to be an
 821      intermediate dlopen, which drops size-zero mappings).  */
 822   for (struct dlfo_mappings_segment *seg
 823          = _dlfo_mappings_active_segment (start_version);
 824        seg != NULL && seg->size > 0; seg = seg->previous)
 825     if (map_start >= seg->objects[0].map_start)
 826       {
 827         struct dl_find_object_internal *obj
 828           = _dlfo_lookup (map_start, seg->objects, seg->size);
 829         if (obj == NULL)
 830           /* Ignore missing link maps because of potential shutdown
 831              issues around __libc_freeres.  */
 832             return;
 833
 834         /* Mark as closed.  This does not change the overall data
 835            structure, so no TM cycle is needed.  */
 836         atomic_store_relaxed (&obj->map_end, obj->map_start);
 837         atomic_store_relaxed (&obj->map, NULL);
 838         return;
 839       }
 840 }
 841
 842 void
 843 _dl_find_object_freeres (void)
 844 {
 845   for (int idx = 0; idx < 2; ++idx)
 846     {
 847       for (struct dlfo_mappings_segment *seg = _dlfo_loaded_mappings[idx];
 848            seg != NULL; )
 849         {
 850           struct dlfo_mappings_segment *previous = seg->previous;
 851           free (seg->to_free);
 852           seg = previous;
 853         }
 854       /* Stop searching in shared objects.  */
 855       _dlfo_loaded_mappings[idx] = 0;
 856     }
 857 }