elf/dl-find_object.c

   1 /* Locating objects in the process image.  ld.so implementation.
   2    Copyright (C) 2021-2022 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 MSB in
 127    _dlfo_loaded_mappings_version determines which array element is the
 128    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, _dlfo_mappings_end_update_no_switch.  */
 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    Returns the index of the currently active segment chain.  */
 266 static inline unsigned int
 267 _dlfo_mappings_begin_update (void)
 268 {
 269   /* The store synchronizes with loads in _dlfo_read_start_version
 270      (also called from _dlfo_read_success).  */
 271   atomic_thread_fence_release ();
 272   return __atomic_wide_counter_fetch_add_relaxed
 273     (&_dlfo_loaded_mappings_version, 2);
 274 }
 275
 276 /* Installs the just-updated version as the active version.  */
 277 static inline void
 278 _dlfo_mappings_end_update (void)
 279 {
 280   /* The store synchronizes with loads in _dlfo_read_start_version
 281      (also called from _dlfo_read_success).  */
 282   atomic_thread_fence_release ();
 283   __atomic_wide_counter_fetch_add_relaxed (&_dlfo_loaded_mappings_version, 1);
 284 }
 285 /* Completes an in-place update without switching versions.  */
 286 static inline void
 287 _dlfo_mappings_end_update_no_switch (void)
 288 {
 289   /* The store synchronizes with loads in _dlfo_read_start_version
 290      (also called from _dlfo_read_success).  */
 291   atomic_thread_fence_release ();
 292   __atomic_wide_counter_fetch_add_relaxed (&_dlfo_loaded_mappings_version, 2);
 293 }
 294
 295 /* Return true if the read was successful, given the start
 296    version.  */
 297 static inline bool
 298 _dlfo_read_success (uint64_t start_version)
 299 {
 300   /* See Hans Boehm, Can Seqlocks Get Along with Programming Language
 301      Memory Models?, Section 4.  This is necessary so that loads in
 302      the TM region are not ordered past the version check below.  */
 303   atomic_thread_fence_acquire ();
 304
 305   /* Synchronizes with stores in _dlfo_mappings_begin_update,
 306      _dlfo_mappings_end_update, _dlfo_mappings_end_update_no_switch.
 307      It is important that all stores from the last update have been
 308      visible, and stores from the next updates are not.
 309
 310      Unlike with seqlocks, there is no check for odd versions here
 311      because we have read the unmodified copy (confirmed to be
 312      unmodified by the unchanged version).  */
 313   return _dlfo_read_start_version () == start_version;
 314 }
 315
 316 /* Returns the active segment identified by the specified start
 317    version.  */
 318 static struct dlfo_mappings_segment *
 319 _dlfo_mappings_active_segment (uint64_t start_version)
 320 {
 321   return _dlfo_loaded_mappings[start_version & 1];
 322 }
 323
 324 /* Searches PC amoung the address-sorted array [FIRST1, FIRST1 +
 325    SIZE).  Assumes PC >= FIRST1->map_start.  Returns a pointer to the
 326    element that contains PC, or NULL if there is no such element.  */
 327 static inline struct dl_find_object_internal *
 328 _dlfo_lookup (uintptr_t pc, struct dl_find_object_internal *first1, size_t size)
 329 {
 330   struct dl_find_object_internal *end = first1 + size;
 331
 332   /* Search for a lower bound in first.  */
 333   struct dl_find_object_internal *first = first1;
 334   while (size > 0)
 335     {
 336       size_t half = size >> 1;
 337       struct dl_find_object_internal *middle = first + half;
 338       if (atomic_load_relaxed (&middle->map_start) < pc)
 339         {
 340           first = middle + 1;
 341           size -= half + 1;
 342         }
 343       else
 344         size = half;
 345     }
 346
 347   if (first != end && pc == atomic_load_relaxed (&first->map_start))
 348     {
 349       if (pc < atomic_load_relaxed (&first->map_end))
 350         return first;
 351       else
 352         /* Zero-length mapping after dlclose.  */
 353         return NULL;
 354     }
 355   else
 356     {
 357       /* Check to see if PC is in the previous mapping.  */
 358       --first;
 359       if (pc < atomic_load_relaxed (&first->map_end))
 360         /* pc >= first->map_start implied by the search above.  */
 361         return first;
 362       else
 363         return NULL;
 364     }
 365 }
 366
 367 int
 368 _dl_find_object (void *pc1, struct dl_find_object *result)
 369 {
 370   uintptr_t pc = (uintptr_t) pc1;
 371
 372   if (__glibc_unlikely (_dlfo_main.map_end == 0))
 373     {
 374       /* Not initialized.  No locking is needed here because this can
 375          only be called from audit modules, which cannot create
 376          threads.  */
 377       return _dl_find_object_slow (pc1, result);
 378     }
 379
 380   /* Main executable.  */
 381   if (pc >= _dlfo_main.map_start && pc < _dlfo_main.map_end)
 382     {
 383       _dl_find_object_to_external (&_dlfo_main, result);
 384       return 0;
 385     }
 386
 387   /* Other initially loaded objects.  */
 388   if (pc >= _dlfo_nodelete_mappings->map_start
 389       && pc < _dlfo_nodelete_mappings_end)
 390     {
 391       struct dl_find_object_internal *obj
 392         = _dlfo_lookup (pc, _dlfo_nodelete_mappings,
 393                         _dlfo_nodelete_mappings_size);
 394       if (obj != NULL)
 395         {
 396           _dl_find_object_to_external (obj, result);
 397           return 0;
 398         }
 399       /* Fall through to the full search.  The kernel may have mapped
 400          the initial mappings with gaps that are later filled by
 401          dlopen with other mappings.  */
 402     }
 403
 404   /* Handle audit modules, dlopen, dlopen objects.  This uses software
 405      transactional memory, with a retry loop in case the version
 406      changes during execution.  */
 407   while (true)
 408     {
 409     retry:
 410       ;
 411       uint64_t start_version = _dlfo_read_start_version ();
 412
 413       /* The read through seg->previous assumes that the CPU
 414          recognizes the load dependency, so that no invalid size
 415          values is read.  Furthermore, the code assumes that no
 416          out-of-thin-air value for seg->size is observed.  Together,
 417          this ensures that the observed seg->size value is always less
 418          than seg->allocated, so that _dlfo_mappings_index does not
 419          read out-of-bounds.  (This avoids intermediate TM version
 420          verification.  A concurrent version update will lead to
 421          invalid lookup results, but not to out-of-memory access.)
 422
 423          Either seg == NULL or seg->size == 0 terminates the segment
 424          list.  _dl_find_object_update does not bother to clear the
 425          size on earlier unused segments.  */
 426       for (struct dlfo_mappings_segment *seg
 427              = _dlfo_mappings_active_segment (start_version);
 428            seg != NULL;
 429            seg = atomic_load_acquire (&seg->previous))
 430         {
 431           size_t seg_size = atomic_load_relaxed (&seg->size);
 432           if (seg_size == 0)
 433             break;
 434
 435           if (pc >= atomic_load_relaxed (&seg->objects[0].map_start))
 436             {
 437               /* PC may lie within this segment.  If it is less than the
 438                  segment start address, it can only lie in a previous
 439                  segment, due to the base address sorting.  */
 440               struct dl_find_object_internal *obj
 441                 = _dlfo_lookup (pc, seg->objects, seg_size);
 442
 443               if (obj != NULL)
 444                 {
 445                   /* Found the right mapping.  Copy out the data prior to
 446                      checking if the read transaction was successful.  */
 447                   struct dl_find_object_internal copy;
 448                   _dl_find_object_internal_copy (obj, &copy);
 449                   if (_dlfo_read_success (start_version))
 450                     {
 451                       _dl_find_object_to_external (&copy, result);
 452                       return 0;
 453                     }
 454                   else
 455                     /* Read transaction failure.  */
 456                     goto retry;
 457                 }
 458               else
 459                 {
 460                   /* PC is not covered by this mapping.  */
 461                   if (_dlfo_read_success (start_version))
 462                     return -1;
 463                   else
 464                     /* Read transaction failure.  */
 465                     goto retry;
 466                 }
 467             } /* if: PC might lie within the current seg.  */
 468         }
 469
 470       /* PC is not covered by any segment.  */
 471       if (_dlfo_read_success (start_version))
 472         return -1;
 473     } /* Transaction retry loop.  */
 474 }
 475 rtld_hidden_def (_dl_find_object)
 476
 477 /* _dlfo_process_initial is called twice.  First to compute the array
 478    sizes from the initial loaded mappings.  Second to fill in the
 479    bases and infos arrays with the (still unsorted) data.  Returns the
 480    number of loaded (non-nodelete) mappings.  */
 481 static size_t
 482 _dlfo_process_initial (void)
 483 {
 484   struct link_map *main_map = GL(dl_ns)[LM_ID_BASE]._ns_loaded;
 485
 486   size_t nodelete = 0;
 487   if (!main_map->l_contiguous)
 488     {
 489       struct dl_find_object_internal dlfo;
 490       _dl_find_object_from_map (main_map, &dlfo);
 491
 492       /* PT_LOAD segments for a non-contiguous are added to the
 493          non-closeable mappings.  */
 494       for (const ElfW(Phdr) *ph = main_map->l_phdr,
 495              *ph_end = main_map->l_phdr + main_map->l_phnum;
 496            ph < ph_end; ++ph)
 497         if (ph->p_type == PT_LOAD)
 498           {
 499             if (_dlfo_nodelete_mappings != NULL)
 500               {
 501                 /* Second pass only.  */
 502                 _dlfo_nodelete_mappings[nodelete] = dlfo;
 503                 _dlfo_nodelete_mappings[nodelete].map_start
 504                   = ph->p_vaddr + main_map->l_addr;
 505                 _dlfo_nodelete_mappings[nodelete].map_end
 506                   = _dlfo_nodelete_mappings[nodelete].map_start + ph->p_memsz;
 507               }
 508             ++nodelete;
 509           }
 510     }
 511
 512   size_t loaded = 0;
 513   for (Lmid_t ns = 0; ns < GL(dl_nns); ++ns)
 514     for (struct link_map *l = GL(dl_ns)[ns]._ns_loaded; l != NULL;
 515          l = l->l_next)
 516       /* Skip the main map processed above, and proxy maps.  */
 517       if (l != main_map && l == l->l_real)
 518         {
 519           /* lt_library link maps are implicitly NODELETE.  */
 520           if (l->l_type == lt_library || l->l_nodelete_active)
 521             {
 522               if (_dlfo_nodelete_mappings != NULL)
 523                 /* Second pass only.  */
 524                 _dl_find_object_from_map
 525                   (l, _dlfo_nodelete_mappings + nodelete);
 526               ++nodelete;
 527             }
 528           else if (l->l_type == lt_loaded)
 529             {
 530               if (_dlfo_loaded_mappings[0] != NULL)
 531                 /* Second pass only.  */
 532                 _dl_find_object_from_map
 533                   (l, &_dlfo_loaded_mappings[0]->objects[loaded]);
 534               ++loaded;
 535             }
 536         }
 537
 538   _dlfo_nodelete_mappings_size = nodelete;
 539   return loaded;
 540 }
 541
 542 /* Selection sort based on mapping start address.  */
 543 void
 544 _dlfo_sort_mappings (struct dl_find_object_internal *objects, size_t size)
 545 {
 546   if (size < 2)
 547     return;
 548
 549   for (size_t i = 0; i < size - 1; ++i)
 550     {
 551       /* Find minimum.  */
 552       size_t min_idx = i;
 553       uintptr_t min_val = objects[i].map_start;
 554       for (size_t j = i + 1; j < size; ++j)
 555         if (objects[j].map_start < min_val)
 556           {
 557             min_idx = j;
 558             min_val = objects[j].map_start;
 559           }
 560
 561       /* Swap into place.  */
 562       struct dl_find_object_internal tmp = objects[min_idx];
 563       objects[min_idx] = objects[i];
 564       objects[i] = tmp;
 565     }
 566 }
 567
 568 void
 569 _dl_find_object_init (void)
 570 {
 571   /* Cover the main mapping.  */
 572   {
 573     struct link_map *main_map = GL(dl_ns)[LM_ID_BASE]._ns_loaded;
 574
 575     if (main_map->l_contiguous)
 576       _dl_find_object_from_map (main_map, &_dlfo_main);
 577     else
 578       {
 579         /* Non-contiguous main maps are handled in
 580            _dlfo_process_initial.  Mark as initialized, but not
 581            coverying any valid PC.  */
 582         _dlfo_main.map_start = -1;
 583         _dlfo_main.map_end = -1;
 584       }
 585   }
 586
 587   /* Allocate the data structures.  */
 588   size_t loaded_size = _dlfo_process_initial ();
 589   _dlfo_nodelete_mappings = malloc (_dlfo_nodelete_mappings_size
 590                                     * sizeof (*_dlfo_nodelete_mappings));
 591   if (loaded_size > 0)
 592     _dlfo_loaded_mappings[0]
 593       = _dlfo_mappings_segment_allocate_unpadded (loaded_size);
 594   if (_dlfo_nodelete_mappings == NULL
 595       || (loaded_size > 0 && _dlfo_loaded_mappings[0] == NULL))
 596     _dl_fatal_printf ("\
 597 Fatal glibc error: cannot allocate memory for find-object data\n");
 598   /* Fill in the data with the second call.  */
 599   _dlfo_nodelete_mappings_size = 0;
 600   _dlfo_process_initial ();
 601
 602   /* Sort both arrays.  */
 603   if (_dlfo_nodelete_mappings_size > 0)
 604     {
 605       _dlfo_sort_mappings (_dlfo_nodelete_mappings,
 606                            _dlfo_nodelete_mappings_size);
 607       size_t last_idx = _dlfo_nodelete_mappings_size - 1;
 608       _dlfo_nodelete_mappings_end = _dlfo_nodelete_mappings[last_idx].map_end;
 609     }
 610   if (loaded_size > 0)
 611     _dlfo_sort_mappings (_dlfo_loaded_mappings[0]->objects,
 612                          _dlfo_loaded_mappings[0]->size);
 613 }
 614
 615 static void
 616 _dl_find_object_link_map_sort (struct link_map **loaded, size_t size)
 617 {
 618   /* Selection sort based on map_start.  */
 619   if (size < 2)
 620     return;
 621   for (size_t i = 0; i < size - 1; ++i)
 622     {
 623       /* Find minimum.  */
 624       size_t min_idx = i;
 625       ElfW(Addr) min_val = loaded[i]->l_map_start;
 626       for (size_t j = i + 1; j < size; ++j)
 627         if (loaded[j]->l_map_start < min_val)
 628           {
 629             min_idx = j;
 630             min_val = loaded[j]->l_map_start;
 631           }
 632
 633       /* Swap into place.  */
 634       struct link_map *tmp = loaded[min_idx];
 635       loaded[min_idx] = loaded[i];
 636       loaded[i] = tmp;
 637     }
 638 }
 639
 640 /* Initializes the segment for writing.  Returns the target write
 641    index (plus 1) in this segment.  The index is chosen so that a
 642    partially filled segment still has data at index 0.  */
 643 static inline size_t
 644 _dlfo_update_init_seg (struct dlfo_mappings_segment *seg,
 645                        size_t remaining_to_add)
 646 {
 647   size_t new_seg_size;
 648   if (remaining_to_add < seg->allocated)
 649     /* Partially filled segment.  */
 650     new_seg_size = remaining_to_add;
 651   else
 652     new_seg_size = seg->allocated;
 653   atomic_store_relaxed (&seg->size, new_seg_size);
 654   return new_seg_size;
 655 }
 656
 657 /* Invoked from _dl_find_object_update after sorting.  Stores to the
 658    shared data need to use relaxed MO.  But plain loads can be used
 659    because the loader lock prevents concurrent stores.  */
 660 static bool
 661 _dl_find_object_update_1 (struct link_map **loaded, size_t count)
 662 {
 663   int active_idx = _dlfo_read_version_locked () & 1;
 664
 665   struct dlfo_mappings_segment *current_seg
 666     = _dlfo_loaded_mappings[active_idx];
 667   size_t current_used = _dlfo_mappings_segment_count_used (current_seg);
 668
 669   struct dlfo_mappings_segment *target_seg
 670     = _dlfo_loaded_mappings[!active_idx];
 671   size_t remaining_to_add = current_used + count;
 672
 673   /* Ensure that the new segment chain has enough space.  */
 674   {
 675     size_t new_allocated
 676       = _dlfo_mappings_segment_count_allocated (target_seg);
 677     if (new_allocated < remaining_to_add)
 678       {
 679         size_t more = remaining_to_add - new_allocated;
 680         target_seg = _dlfo_mappings_segment_allocate (more, target_seg);
 681         if (target_seg == NULL)
 682           /* Out of memory.  Do not end the update and keep the
 683              current version unchanged.  */
 684           return false;
 685
 686         /* Start update cycle. */
 687         _dlfo_mappings_begin_update ();
 688
 689         /* The barrier ensures that a concurrent TM read or fork does
 690            not see a partially initialized segment.  */
 691         atomic_store_release (&_dlfo_loaded_mappings[!active_idx], target_seg);
 692       }
 693     else
 694       /* Start update cycle without allocation.  */
 695       _dlfo_mappings_begin_update ();
 696   }
 697
 698   size_t target_seg_index1 = _dlfo_update_init_seg (target_seg,
 699                                                     remaining_to_add);
 700
 701   /* Merge the current_seg segment list with the loaded array into the
 702      target_set.  Merging occurs backwards, in decreasing l_map_start
 703      order.  */
 704   size_t loaded_index1 = count;
 705   size_t current_seg_index1;
 706   if (current_seg == NULL)
 707     current_seg_index1 = 0;
 708   else
 709     current_seg_index1 = current_seg->size;
 710   while (true)
 711     {
 712       if (current_seg_index1 == 0)
 713         {
 714           /* Switch to the previous segment.  */
 715           if (current_seg != NULL)
 716             current_seg = current_seg->previous;
 717           if (current_seg != NULL)
 718             {
 719               current_seg_index1 = current_seg->size;
 720               if (current_seg_index1 == 0)
 721                 /* No more data in previous segments.  */
 722                 current_seg = NULL;
 723             }
 724         }
 725
 726       if (current_seg != NULL
 727           && (current_seg->objects[current_seg_index1 - 1].map == NULL))
 728         {
 729           /* This mapping has been dlclose'd.  Do not copy it.  */
 730           --current_seg_index1;
 731           continue;
 732         }
 733
 734       if (loaded_index1 == 0 && current_seg == NULL)
 735         /* No more data in either source.  */
 736         break;
 737
 738       /* Make room for another mapping.  */
 739       assert (remaining_to_add > 0);
 740       if (target_seg_index1 == 0)
 741         {
 742           /* Switch segments and set the size of the segment.  */
 743           target_seg = target_seg->previous;
 744           target_seg_index1 = _dlfo_update_init_seg (target_seg,
 745                                                      remaining_to_add);
 746         }
 747
 748       /* Determine where to store the data.  */
 749       struct dl_find_object_internal *dlfo
 750         = &target_seg->objects[target_seg_index1 - 1];
 751
 752       if (loaded_index1 == 0
 753           || (current_seg != NULL
 754               && (loaded[loaded_index1 - 1]->l_map_start
 755                   < current_seg->objects[current_seg_index1 - 1].map_start)))
 756         {
 757           /* Prefer mapping in current_seg.  */
 758           assert (current_seg_index1 > 0);
 759           _dl_find_object_internal_copy
 760             (&current_seg->objects[current_seg_index1 - 1], dlfo);
 761           --current_seg_index1;
 762         }
 763       else
 764         {
 765           /* Prefer newly loaded link map.  */
 766           assert (loaded_index1 > 0);
 767           _dl_find_object_from_map (loaded[loaded_index1 - 1], dlfo);
 768           loaded[loaded_index1 -  1]->l_find_object_processed = 1;
 769           --loaded_index1;
 770         }
 771
 772       /* Consume space in target segment.  */
 773       --target_seg_index1;
 774
 775       --remaining_to_add;
 776     }
 777
 778   /* Everything has been added.  */
 779   assert (remaining_to_add == 0);
 780
 781   /* The segment must have been filled up to the beginning.  */
 782   assert (target_seg_index1 == 0);
 783
 784   /* Prevent searching further into unused segments.  */
 785   if (target_seg->previous != NULL)
 786     atomic_store_relaxed (&target_seg->previous->size, 0);
 787
 788   _dlfo_mappings_end_update ();
 789   return true;
 790 }
 791
 792 bool
 793 _dl_find_object_update (struct link_map *new_map)
 794 {
 795   /* Copy the newly-loaded link maps into an array for sorting.  */
 796   size_t count = 0;
 797   for (struct link_map *l = new_map; l != NULL; l = l->l_next)
 798     /* Skip proxy maps and already-processed maps.  */
 799     count += l == l->l_real && !l->l_find_object_processed;
 800   struct link_map **map_array = malloc (count * sizeof (*map_array));
 801   if (map_array == NULL)
 802     return false;
 803   {
 804     size_t i = 0;
 805     for (struct link_map *l = new_map; l != NULL; l = l->l_next)
 806       if (l == l->l_real && !l->l_find_object_processed)
 807         map_array[i++] = l;
 808   }
 809   if (count == 0)
 810     return true;
 811
 812   _dl_find_object_link_map_sort (map_array, count);
 813   bool ok = _dl_find_object_update_1 (map_array, count);
 814   free (map_array);
 815   return ok;
 816 }
 817
 818 void
 819 _dl_find_object_dlclose (struct link_map *map)
 820 {
 821   uint64_t start_version = _dlfo_read_version_locked ();
 822   uintptr_t map_start = map->l_map_start;
 823
 824
 825   /* Directly patch the size information in the mapping to mark it as
 826      unused.  See the parallel lookup logic in _dl_find_object.  Do
 827      not check for previous dlclose at the same mapping address
 828      because that cannot happen (there would have to be an
 829      intermediate dlopen, which drops size-zero mappings).  */
 830   for (struct dlfo_mappings_segment *seg
 831          = _dlfo_mappings_active_segment (start_version);
 832        seg != NULL && seg->size > 0; seg = seg->previous)
 833     if (map_start >= seg->objects[0].map_start)
 834       {
 835         struct dl_find_object_internal *obj
 836           = _dlfo_lookup (map_start, seg->objects, seg->size);
 837         if (obj == NULL)
 838           /* Ignore missing link maps because of potential shutdown
 839              issues around __libc_freeres.  */
 840             return;
 841
 842         /* The update happens in-place, but given that we do not use
 843            atomic accesses on the read side, update the version around
 844            the update to trigger re-validation in concurrent
 845            readers.  */
 846         _dlfo_mappings_begin_update ();
 847
 848         /* Mark as closed.  */
 849         obj->map_end = obj->map_start;
 850         obj->map = NULL;
 851
 852         _dlfo_mappings_end_update_no_switch ();
 853         return;
 854       }
 855 }
 856
 857 void
 858 _dl_find_object_freeres (void)
 859 {
 860   for (int idx = 0; idx < 2; ++idx)
 861     {
 862       for (struct dlfo_mappings_segment *seg = _dlfo_loaded_mappings[idx];
 863            seg != NULL; )
 864         {
 865           struct dlfo_mappings_segment *previous = seg->previous;
 866           free (seg->to_free);
 867           seg = previous;
 868         }
 869       /* Stop searching in shared objects.  */
 870       _dlfo_loaded_mappings[idx] = 0;
 871     }
 872 }