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