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
_dl_find_object_slow(void * pc,struct dl_find_object * result)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
_dlfo_mappings_segment_count_used(struct dlfo_mappings_segment * seg)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
_dlfo_mappings_segment_count_allocated(struct dlfo_mappings_segment * seg)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 *
_dlfo_mappings_segment_allocate_unpadded(size_t size)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 *
_dlfo_mappings_segment_allocate(size_t size,struct dlfo_mappings_segment * previous)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
_dlfo_read_start_version(void)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
_dlfo_read_version_locked(void)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
_dlfo_mappings_begin_update(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
_dlfo_mappings_end_update(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
_dlfo_read_success(uint64_t start_version)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 *
_dlfo_mappings_active_segment(uint64_t start_version)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 *
_dlfo_lookup(uintptr_t pc,struct dl_find_object_internal * first1,size_t size)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
_dl_find_object(void * pc1,struct dl_find_object * result)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 }
rtld_hidden_def(_dl_find_object)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
_dlfo_sort_mappings(struct dl_find_object_internal * objects,size_t size)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
_dl_find_object_init(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
_dl_find_object_link_map_sort(struct link_map ** loaded,size_t size)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
_dlfo_update_init_seg(struct dlfo_mappings_segment * seg,size_t remaining_to_add)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
_dl_find_object_update_1(struct link_map ** loaded,size_t count)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
_dl_find_object_update(struct link_map * new_map)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
_dl_find_object_dlclose(struct link_map * map)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
_dl_find_object_freeres(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 }
858