From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS17314 8.43.84.0/22 X-Spam-Status: No, score=-3.7 required=3.0 tests=AWL,BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,MAILING_LIST_MULTI, PDS_RDNS_DYNAMIC_FP,RCVD_IN_DNSWL_MED,RDNS_DYNAMIC,SPF_HELO_PASS, SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by dcvr.yhbt.net (Postfix) with ESMTPS id F0B781F953 for ; Wed, 17 Nov 2021 13:41:32 +0000 (UTC) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id DD5BC3858033 for ; Wed, 17 Nov 2021 13:41:31 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org DD5BC3858033 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1637156491; bh=8yeXt/ZhmIS2LBdEVK2gQreVPF46HHOjJa/iGfSvdqA=; h=To:Subject:References:Date:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=xKSkcu87Z9vjnNlpeMr4xMc8xUHTBGRVjCiLXmQH7yfg0aqDhonMlVbNvP4WPZuvg 6G0G8uGYF+SlASyYAVADZnxdkZczbUg4vrdfAi95ULMIfp9lmQBteQ73PCr1EiAeIT QSqVAZcvP1o3hOEn4lhAlGuveycfjqNyR/D/TjQc= Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id E233B3858C27 for ; Wed, 17 Nov 2021 13:40:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E233B3858C27 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-315-cCeMdIXNMNCHrOWhX4rYag-1; Wed, 17 Nov 2021 08:40:08 -0500 X-MC-Unique: cCeMdIXNMNCHrOWhX4rYag-1 Received: from smtp.corp.redhat.com (int-mx03.intmail.prod.int.phx2.redhat.com [10.5.11.13]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 485021023F4E; Wed, 17 Nov 2021 13:40:07 +0000 (UTC) Received: from oldenburg.str.redhat.com (unknown [10.39.194.81]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 7ECE95BB12; Wed, 17 Nov 2021 13:40:05 +0000 (UTC) To: Adhemerval Zanella via Libc-alpha Subject: Re: [PATCH 3/3] elf: Add _dl_find_eh_frame function References: <559832af-f8f2-c14f-95e7-caeebc6e9382@linaro.org> Date: Wed, 17 Nov 2021 14:40:03 +0100 In-Reply-To: <559832af-f8f2-c14f-95e7-caeebc6e9382@linaro.org> (Adhemerval Zanella via Libc-alpha's message of "Tue, 16 Nov 2021 09:42:26 -0300") Message-ID: <87czmy7vf0.fsf@oldenburg.str.redhat.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.2 (gnu/linux) MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.13 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , From: Florian Weimer via Libc-alpha Reply-To: Florian Weimer Cc: Jakub Jelinek , gcc-patches@gcc.gnu.org Errors-To: libc-alpha-bounces+e=80x24.org@sourceware.org Sender: "Libc-alpha" * Adhemerval Zanella via Libc-alpha: > However the code is somewhat complex and I would like to have some feedba= ck > if gcc will be willing to accept this change (I assume it would require > this code merge on glibc beforehand). There's a long review queue on the GCC side due to the stage1 close. It may still be considered for GCC 12. Jakub has also requested that we hold off committing the glibc side until the GCC side is reviewed. I'll flesh out the commit message and NEWS entry once we have agreed upon the interface. >> new file mode 100644 >> index 0000000000..c7313c122d >> --- /dev/null >> +++ b/elf/dl-find_eh_frame.c >> +/* Data for the main executable. There is usually a large gap between >> + the main executable and initially loaded shared objects. Record >> + the main executable separately, to increase the chance that the >> + range for the non-closeable mappings below covers only the shared >> + objects (and not also the gap between main executable and shared >> + objects). */ >> +static uintptr_t _dl_eh_main_map_start attribute_relro; >> +static struct dl_eh_frame_info _dl_eh_main_info attribute_relro; >> + >> +/* Data for initally loaded shared objects that cannot be unlaoded. > > s/initally/initially and s/unlaoded/unloaded. Fixed. > >> + The mapping base addresses are stored in address order in the >> + _dl_eh_nodelete_mappings_bases array (containing >> + _dl_eh_nodelete_mappings_size elements). The EH data for a base >> + address is stored in the parallel _dl_eh_nodelete_mappings_infos. >> + These arrays are not modified after initialization. */ >> +static uintptr_t _dl_eh_nodelete_mappings_end attribute_relro; >> +static size_t _dl_eh_nodelete_mappings_size attribute_relro; >> +static uintptr_t *_dl_eh_nodelete_mappings_bases attribute_relro; >> +static struct dl_eh_frame_info *_dl_eh_nodelete_mappings_infos >> + attribute_relro; >> + >> +/* Mappings created by dlopen can go away with dlclose, so a data >> + dynamic data structure with some synchronization is needed. > > This sounds strange ("a data dynamic data"). I dropped the first data. > >> + Individual segments are similar to the _dl_eh_nodelete_mappings > > Maybe use _dl_eh_nodelete_mappings_*, because '_dl_eh_nodelete_mappings' > itself if not defined anywhere. Right. >> + Adding new elements to this data structure is another source of >> + quadratic behavior for dlopen. If the other causes of quadratic >> + behavior are eliminated, a more complicated data structure will be >> + needed. */ > > This worries me, specially we have reports that python and other dynamic > environments do use a lot of plugin and generates a lot of dlopen() calls= . > What kind of performance implication do you foresee here? The additional overhead is not disproportionate to the other sources of quadratic behavior. With 1,000 dlopen'ed objects, overall run-time seems to be comparable to the strcmp time required soname matching, for example, and is quite difficult to measure. So we could fix the performance regression if we used a hash table for that =E2=80=A6 It's just an undesirable complexity class. The implementation is not actually slow because it's a mostly-linear copy (although a backwards one). Other parts of dlopen involve pointer chasing and are much slower. >> +/* Allocate an empty segment that is at least SIZE large. PREVIOUS */ > > What this PREVIOUS refer to? Oops, it's now: /* Allocate an empty segment that is at least SIZE large. PREVIOUS points to the chain of previously allocated segments and can be NULL. */ >> +/* 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 >> +_dl_eh_mappings_begin_update (void) >> +{ >> + unsigned int v >> + =3D __atomic_wide_counter_fetch_add_relaxed (&_dl_eh_loaded_mapping= s_version, >> + 2); > > Why use an 'unsigned int' for the wide counter here? Because =E2=80=A6 >> + /* Subsequent stores to the TM data must not be reordered before the >> + store above with the version update. */ >> + atomic_thread_fence_release (); >> + return v & 1; >> +} =E2=80=A6 we only need the lower bit. >> + /* Other initially loaded objects. */ >> + if (pc >=3D *_dl_eh_nodelete_mappings_bases >> + && pc < _dl_eh_nodelete_mappings_end) >> + { >> + size_t idx =3D _dl_eh_find_lower_bound (pc, >> + _dl_eh_nodelete_mappings_ba= ses, >> + _dl_eh_nodelete_mappings_si= ze); >> + const struct dl_eh_frame_info *info >> + =3D _dl_eh_nodelete_mappings_infos + idx; > > Ins't a UB if idx is not a valid one? idx is always valid here. >> + bool match; >> + if (idx < _dl_eh_nodelete_mappings_size >> + && pc =3D=3D _dl_eh_nodelete_mappings_bases[idx]) >> + match =3D true; >> + else >> + { >> + /* PC might be in the previous mapping. */ >> + --idx; >> + --info; >> + match =3D pc - _dl_eh_nodelete_mappings_bases[idx] < info->si= ze; >> + } > > It is not clear to me why _dl_eh_find_lower_bound() can not handle this > specific exception, since this is also used in the audit, dlopen case > below. The struct layouts are different. Maybe I should use a segment structure for _dl_eh_nodelete_mappings_bases as well? >> + /* Handle audit modules, dlopen, dlopen objects. This uses software >> + transactional memory, with a retry loop in case the version >> + changes during execution. */ >> + while (true) >> + { >> + retry: >> + ; >> + uint64_t start_version =3D _dl_eh_read_start_version (); >> + for (struct dl_eh_mappings_segment *seg >> + =3D _dl_eh_mappings_active_segment (start_version); >> + seg !=3D NULL && seg->size > 0; seg =3D seg->previous) >> + if (pc >=3D seg->bases[0]) >> + { >> + /* PC may lie within this segment. If it is less than the >> + if (match) >> + { >> + /* Found the right mapping. Copy out the data prior to >> + checking if the read transaction was successful. */ >> + if (_dl_eh_read_success (start_version)) >> + else >> + /* Read transaction failure. */ >> + goto retry; > > Why not 'continue' here? We need to re-run the outer while loop, not the inner segment iteration. >> +/* _dl_eh_process_initial is called twice. First to compute the array >> + sizes from the initial loaded mappings. Second to fill in the >> + bases and infos arrays with the (still unsorted) data. Returns the >> + number of loaded (non-nodelete) mappings. */ > > I usually see this called twice functionn confunsing because it not clear > which is the default patch used for each call (although the comments do > help it). > > Maybe you can add two function, one that calculates the initial size and > another that actually populates it. It allows, for instance, to call=20 > the initial_map _dl_get_eh_frame() once (you will need to keep the > struct dl_eh_frame_info between calls). I started out with this and found it more confusing because of the complicated conditions (apart from the phase distinction). >> +static void >> +_dl_eh_frame_link_map_sort (struct link_map **loaded, size_t size) >> +{ >> + /* Selection sort based on map_start. */ >> + if (size < 2) >> + return; >> + for (size_t i =3D 0; i < size - 1; ++i) >> + { >> + /* Find minimum. */ >> + size_t min_idx =3D i; >> + ElfW(Addr) min_val =3D loaded[i]->l_map_start; >> + for (size_t j =3D i + 1; j < size; ++j) >> + if (loaded[j]->l_map_start < min_val) >> + { >> + min_idx =3D j; >> + min_val =3D loaded[j]->l_map_start; >> + } >> + >> + /* Swap into place. */ >> + struct link_map *tmp =3D loaded[min_idx]; >> + loaded[min_idx] =3D loaded[i]; >> + loaded[i] =3D tmp; >> + } >> +} > > Could this be a problem with programs with a lot of dependencies? I don't see it in profiles. It's quadratic for sure, but mostly linear accesses, and the array fits into the L1 cache. We could optimize it and check if the array is already sorted in reverse order, reflecting the typical kernel mapping behavior. >> +/* Invoked from _dl_eh_frame_frame after sorting. */ >> +static bool >> +_dl_find_eh_frame_update_1 (struct link_map **loaded, size_t count) >> +{ >> + int active_idx =3D _dl_eh_mappings_begin_update (); >> + >> + struct dl_eh_mappings_segment *current_seg >> + =3D _dl_eh_loaded_mappings[active_idx]; >> + size_t current_used =3D _dl_eh_mappings_segment_count_used (current_s= eg); >> + >> + struct dl_eh_mappings_segment *target_seg >> + =3D _dl_eh_loaded_mappings[!active_idx]; >> + size_t remaining_to_add =3D current_used + count; >> + >> + /* Ensure that the new segment chain has enough space. */ >> + { >> + size_t new_allocated >> + =3D _dl_eh_mappings_segment_count_allocated (target_seg); >> + if (new_allocated < remaining_to_add) >> + { >> + size_t more =3D remaining_to_add - new_allocated; >> + target_seg =3D _dl_eh_mappings_segment_allocate (more, target_s= eg); >> + if (target_seg =3D=3D NULL) >> + /* Out of memory. */ >> + return false; > > Shouldn't it have a _dl_eh_mappings_end_update() here? No, we should keep the original version. I added: /* Out of memory. Do not end the update and keep the current version unchanged. */ We could split the counter update and current version access, and start the update only after the malloc, I think. This would make it less likely that a concurrent thread sees multiple version updates, causing multiple retries, I think. >> +bool >> +_dl_find_eh_frame_update (struct link_map *new_map) >> +{ >> + /* Copy the newly-loaded link maps into an array for sorting. */ >> + size_t count =3D 0; >> + for (struct link_map *l =3D new_map; l !=3D NULL; l =3D l->l_next) >> + count +=3D !l->l_eh_frame_processed; >> + struct link_map **map_array =3D malloc (count * sizeof (*map_array)); > > Maybe use a scratch_buffer here? It should cover 128 entries for 64-bit, This is only used for dlopen, and dlopen already has many malloc calls. I don't think it matters. >> diff --git a/elf/dl-find_eh_frame.h b/elf/dl-find_eh_frame.h >> new file mode 100644 >> index 0000000000..4bde9b14db >> --- /dev/null >> +++ b/elf/dl-find_eh_frame.h >> +/* Extract the exception handling data from a link map and writes it >> + to *INFO. If no such data is available INFO->eh_frame will be >> + NULL. */ >> +static void __attribute__ ((unused)) > > Maybe use inline here and let compiler optimize? I don't think inlining is beneficial. > Or move to the be a proper function? It's also used from tests, so it's convenient to have it in a header. >> +/* This function is similar to _dl_find_eh_frame, but travers the link >> + maps directly. It is used from audit modules before >> + _dl_find_eh_frame_init has been called, and for testing. */ >> +static void * >> +_dl_find_eh_frame_slow (void *pc >> +#if DL_FIND_EH_FRAME_DBASE >> + , void **dbase >> +#endif >> + ) >> +{ >> + ElfW(Addr) addr =3D (ElfW(Addr)) pc; >> + for (Lmid_t ns =3D 0; ns < GL(dl_nns); ++ns) >> + for (struct link_map *l =3D GL(dl_ns)[ns]._ns_loaded; l !=3D NULL; >> + l =3D l->l_next) >> + if (addr >=3D l->l_map_start && addr < l->l_map_end >> + && (l->l_contiguous || _dl_addr_inside_object (l, addr))) >> + { >> + assert (ns =3D=3D l->l_ns); >> + struct dl_eh_frame_info info; >> + _dl_get_eh_frame (l, &info); >> +#if DL_FIND_EH_FRAME_DBASE >> + *dbase =3D info.dbase; >> +#endif >> + return info.eh_frame; >> + } >> + >> + /* Object not found. */ >> + return NULL; >> +} > > This is only used on dl-find-eh_frame.c, so there is no much gain in > adding header to define it. I expected it to use it in tests. >> +@deftypefun {void *} _dl_find_eh_frame (void *@var{pc}) >> +@standards{GNU, dlfcn.h} >> +@safety{@mtsafe{}@assafe{}@acsafe{}} >> +This function returns a pointer to the unwinding information for the >> +object that contains the program coder @var{pc}. If the platform uses >> +DWARF unwinding information, this is the in-memory address of the >> +@code{PT_GNU_EH_FRAME} segment. >> + >> +In case @var{pc} resides in an object that lacks unwinding information, >> +the function returns @code{NULL}. If no object matches @var{pc}, >> +@code{NULL} is returned as well. >> + >> +@code{_dl_find_eh_frame} itself is thread-safe. However, if the >> +application invokes @code{dlclose} for the object that contains @var{pc= } >> +concurrently with @code{_dl_find_eh_frame} or after the call returns, >> +accessing the unwinding data for that object is not safe. Therefore, >> +the application needs to ensure by other means (e.g., by convention) >> +that @var{pc} remains a valid code address while the unwinding >> +information is processed. >> + >> +This function is a GNU extension. > > In the code you state this interface should be async-signa-safe, but ther= e it > no explicit documentation about it. It says so in the header: +@safety{@mtsafe{}@assafe{}@acsafe{}} >> diff --git a/sysdeps/i386/bits/dlfcn_eh_frame.h b/sysdeps/i386/bits/dlfc= n_eh_frame.h >> new file mode 100644 >> index 0000000000..98f6b37029 >> --- /dev/null >> +++ b/sysdeps/i386/bits/dlfcn_eh_frame.h >> +#ifndef _DLFCN_H >> +# error "Never use directly; include = instead." >> +#endif >> + >> +/* This implementation uses a DBASE pointer argument in >> + _dl_find_eh_frame. */ >> +#define DL_FIND_EH_FRAME_DBASE 1 > > Maybe move DL_FIND_EH_FRAME_DBASE to its own header and sets the expected > _dl_find_eh_frame() prototype based on it (so you don't need to replicate > it on i386 and nios2). I think I wrote elsewhere that I could glibc/GCC settle on a different interface eventually, e.g. struct dl_object_info { uint64_t flags; /* Would indicate NODELETE/otherwise persistent mappings.= */ struct link_map *map; void *begin; void *end; void *eh_frame; #if DL_OBJECT_INFO_DBASE void *dbase; #endif #if DL_OBJECT_INFO_PCOUNT unsigned long int pcount; /* Used on Arm, see __gnu_Unwind_Find_exidx. = */ #endif }; int _dl_find_object (void *address, struct dl_object_info *result); This interface would allow some additional optimizations in libgcc_s (e.g., cache its own eh_frame value, and the libstdc++ eh_frame value if it's a persistent mapping). The object boundary information could be useful in other cases. And it's trivial to implement _dl_find_dso_for_object on top of it, eliminating a potential bottleneck from caller-sensitive functions. Thanks, Florian