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