/* Locating objects in the process image. ld.so implementation.
- Copyright (C) 2021-2022 Free Software Foundation, Inc.
+ Copyright (C) 2021-2023 Free Software Foundation, Inc.
This file is part of the GNU C Library.
The GNU C Library is free software; you can redistribute it and/or
<https://www.gnu.org/licenses/>. */
#include <assert.h>
+#include <atomic.h>
#include <atomic_wide_counter.h>
#include <dl-find_object.h>
#include <dlfcn.h>
struct dl_find_object_internal internal;
_dl_find_object_from_map (l, &internal);
_dl_find_object_to_external (&internal, result);
- return 1;
+ return 0;
}
/* Object not found. */
over all segments, even though the data is not stored in one
contiguous array.
- During updates, the segments are overwritten in place, and a
- software transactional memory construct (involving the
+ During updates, the segments are overwritten in place. A software
+ transactional memory construct (involving the
_dlfo_loaded_mappings_version variable) is used to detect
- concurrent modification, and retry as necessary. The memory
- allocations are never deallocated, but slots used for objects that
- have been dlclose'd can be reused by dlopen. The memory can live
- in the regular C malloc heap.
+ concurrent modification, and retry as necessary. (This approach is
+ similar to seqlocks, except that two copies are used, and there is
+ only one writer, ever, due to the loader lock.) Technically,
+ relaxed MO loads and stores need to be used for the shared TM data,
+ to avoid data races.
+
+ The memory allocations are never deallocated, but slots used for
+ objects that have been dlclose'd can be reused by dlopen. The
+ memory can live in the regular C malloc heap.
The segments are populated from the start of the list, with the
mappings with the highest address. Only if this segment is full,
needed. */
struct dlfo_mappings_segment
{
- /* The previous segment has lower base addresses. */
+ /* The previous segment has lower base addresses. Constant after
+ initialization; read in the TM region. */
struct dlfo_mappings_segment *previous;
/* Used by __libc_freeres to deallocate malloc'ed memory. */
void *to_free;
/* Count of array elements in use and allocated. */
- size_t size;
+ size_t size; /* Read in the TM region. */
size_t allocated;
- struct dl_find_object_internal objects[];
+ struct dl_find_object_internal objects[]; /* Read in the TM region. */
};
/* To achieve async-signal-safety, two copies of the data structure
are used, so that a signal handler can still use this data even if
- dlopen or dlclose modify the other copy. The the MSB in
- _dlfo_loaded_mappings_version determines which array element is the
- currently active region. */
+ dlopen or dlclose modify the other copy. The the least significant
+ bit in _dlfo_loaded_mappings_version determines which array element
+ is the currently active region. */
static struct dlfo_mappings_segment *_dlfo_loaded_mappings[2];
/* Returns the number of actually used elements in all segments
_dlfo_read_start_version (void)
{
/* Acquire MO load synchronizes with the fences at the beginning and
- end of the TM update region. */
+ end of the TM update region in _dlfo_mappings_begin_update,
+ _dlfo_mappings_end_update. */
return __atomic_wide_counter_load_acquire (&_dlfo_loaded_mappings_version);
}
}
/* Update the version to reflect that an update is happening. This
- does not change the bit that controls the active segment chain.
- Returns the index of the currently active segment chain. */
-static inline unsigned int
+ does not change the bit that controls the active segment chain. */
+static inline void
_dlfo_mappings_begin_update (void)
{
- unsigned int v
- = __atomic_wide_counter_fetch_add_relaxed (&_dlfo_loaded_mappings_version,
- 2);
- /* Subsequent stores to the TM data must not be reordered before the
- store above with the version update. */
+ /* The fence synchronizes with loads in _dlfo_read_start_version
+ (also called from _dlfo_read_success). */
atomic_thread_fence_release ();
- return v & 1;
}
/* Installs the just-updated version as the active version. */
static inline void
_dlfo_mappings_end_update (void)
{
- /* The previous writes to the TM data must not be reordered after
- the version update below. */
- atomic_thread_fence_release ();
- __atomic_wide_counter_fetch_add_relaxed (&_dlfo_loaded_mappings_version,
- 1);
-}
-/* Completes an in-place update without switching versions. */
-static inline void
-_dlfo_mappings_end_update_no_switch (void)
-{
- /* The previous writes to the TM data must not be reordered after
- the version update below. */
+ /* The fence synchronizes with loads in _dlfo_read_start_version
+ (also called from _dlfo_read_success). */
atomic_thread_fence_release ();
- __atomic_wide_counter_fetch_add_relaxed (&_dlfo_loaded_mappings_version,
- 2);
+ /* No atomic read-modify-write update needed because of the loader
+ lock. */
+ __atomic_wide_counter_add_relaxed (&_dlfo_loaded_mappings_version, 1);
}
/* Return true if the read was successful, given the start
static inline bool
_dlfo_read_success (uint64_t start_version)
{
+ /* See Hans Boehm, Can Seqlocks Get Along with Programming Language
+ Memory Models?, Section 4. This is necessary so that loads in
+ the TM region are not ordered past the version check below. */
+ atomic_thread_fence_acquire ();
+
+ /* Synchronizes with the fences in _dlfo_mappings_begin_update,
+ _dlfo_mappings_end_update. It is important that all stores from
+ the last update have become visible, and stores from the next
+ update to this version are not before the version number is
+ updated.
+
+ Unlike with seqlocks, there is no check for odd versions here
+ because we have read the unmodified copy (confirmed to be
+ unmodified by the unchanged version). */
return _dlfo_read_start_version () == start_version;
}
return _dlfo_loaded_mappings[start_version & 1];
}
-/* Searches PC amoung the address-sorted array [FIRST1, FIRST1 +
+/* Searches PC among the address-sorted array [FIRST1, FIRST1 +
SIZE). Assumes PC >= FIRST1->map_start. Returns a pointer to the
element that contains PC, or NULL if there is no such element. */
static inline struct dl_find_object_internal *
{
size_t half = size >> 1;
struct dl_find_object_internal *middle = first + half;
- if (middle->map_start < pc)
+ if (atomic_load_relaxed (&middle->map_start) < pc)
{
first = middle + 1;
size -= half + 1;
size = half;
}
- if (first != end && pc == first->map_start)
+ if (first != end && pc == atomic_load_relaxed (&first->map_start))
{
- if (pc < first->map_end)
+ if (pc < atomic_load_relaxed (&first->map_end))
return first;
else
/* Zero-length mapping after dlclose. */
{
/* Check to see if PC is in the previous mapping. */
--first;
- if (pc < first->map_end)
+ if (pc < atomic_load_relaxed (&first->map_end))
/* pc >= first->map_start implied by the search above. */
return first;
else
size on earlier unused segments. */
for (struct dlfo_mappings_segment *seg
= _dlfo_mappings_active_segment (start_version);
- seg != NULL && seg->size > 0; seg = seg->previous)
- if (pc >= seg->objects[0].map_start)
- {
- /* PC may lie within this segment. If it is less than the
- segment start address, it can only lie in a previous
- segment, due to the base address sorting. */
- struct dl_find_object_internal *obj
- = _dlfo_lookup (pc, seg->objects, seg->size);
+ seg != NULL;
+ seg = atomic_load_acquire (&seg->previous))
+ {
+ size_t seg_size = atomic_load_relaxed (&seg->size);
+ if (seg_size == 0)
+ break;
- if (obj != NULL)
- {
- /* Found the right mapping. Copy out the data prior to
- checking if the read transaction was successful. */
- struct dl_find_object_internal copy = *obj;
- if (_dlfo_read_success (start_version))
- {
- _dl_find_object_to_external (©, result);
- return 0;
- }
- else
- /* Read transaction failure. */
- goto retry;
- }
- else
- {
- /* PC is not covered by this mapping. */
- if (_dlfo_read_success (start_version))
- return -1;
- else
- /* Read transaction failure. */
- goto retry;
- }
- } /* if: PC might lie within the current seg. */
+ if (pc >= atomic_load_relaxed (&seg->objects[0].map_start))
+ {
+ /* PC may lie within this segment. If it is less than the
+ segment start address, it can only lie in a previous
+ segment, due to the base address sorting. */
+ struct dl_find_object_internal *obj
+ = _dlfo_lookup (pc, seg->objects, seg_size);
+
+ if (obj != NULL)
+ {
+ /* Found the right mapping. Copy out the data prior to
+ checking if the read transaction was successful. */
+ struct dl_find_object_internal copy;
+ _dl_find_object_internal_copy (obj, ©);
+ if (_dlfo_read_success (start_version))
+ {
+ _dl_find_object_to_external (©, result);
+ return 0;
+ }
+ else
+ /* Read transaction failure. */
+ goto retry;
+ }
+ else
+ {
+ /* PC is not covered by this mapping. */
+ if (_dlfo_read_success (start_version))
+ return -1;
+ else
+ /* Read transaction failure. */
+ goto retry;
+ }
+ } /* if: PC might lie within the current seg. */
+ }
/* PC is not covered by any segment. */
if (_dlfo_read_success (start_version))
_dlfo_update_init_seg (struct dlfo_mappings_segment *seg,
size_t remaining_to_add)
{
+ size_t new_seg_size;
if (remaining_to_add < seg->allocated)
/* Partially filled segment. */
- seg->size = remaining_to_add;
+ new_seg_size = remaining_to_add;
else
- seg->size = seg->allocated;
- return seg->size;
+ new_seg_size = seg->allocated;
+ atomic_store_relaxed (&seg->size, new_seg_size);
+ return new_seg_size;
}
-/* Invoked from _dl_find_object_update after sorting. */
+/* Invoked from _dl_find_object_update after sorting. Stores to the
+ shared data need to use relaxed MO. But plain loads can be used
+ because the loader lock prevents concurrent stores. */
static bool
_dl_find_object_update_1 (struct link_map **loaded, size_t count)
{
{
/* Prefer mapping in current_seg. */
assert (current_seg_index1 > 0);
- *dlfo = current_seg->objects[current_seg_index1 - 1];
+ _dl_find_object_internal_copy
+ (¤t_seg->objects[current_seg_index1 - 1], dlfo);
--current_seg_index1;
}
else
/* Prevent searching further into unused segments. */
if (target_seg->previous != NULL)
- target_seg->previous->size = 0;
+ atomic_store_relaxed (&target_seg->previous->size, 0);
_dlfo_mappings_end_update ();
return true;
for (struct link_map *l = new_map; l != NULL; l = l->l_next)
/* Skip proxy maps and already-processed maps. */
count += l == l->l_real && !l->l_find_object_processed;
+ if (count == 0)
+ return true;
+
struct link_map **map_array = malloc (count * sizeof (*map_array));
if (map_array == NULL)
return false;
if (l == l->l_real && !l->l_find_object_processed)
map_array[i++] = l;
}
- if (count == 0)
- return true;
_dl_find_object_link_map_sort (map_array, count);
bool ok = _dl_find_object_update_1 (map_array, count);
issues around __libc_freeres. */
return;
- /* The update happens in-place, but given that we do not use
- atomic accesses on the read side, update the version around
- the update to trigger re-validation in concurrent
- readers. */
- _dlfo_mappings_begin_update ();
-
- /* Mark as closed. */
- obj->map_end = obj->map_start;
- obj->map = NULL;
-
- _dlfo_mappings_end_update_no_switch ();
+ /* Mark as closed. This does not change the overall data
+ structure, so no TM cycle is needed. */
+ atomic_store_relaxed (&obj->map_end, obj->map_start);
+ atomic_store_relaxed (&obj->map, NULL);
return;
}
}