Bug 26179 - _dl_map_object_deps re-walking transitive deps of already loaded DSOs
Summary: _dl_map_object_deps re-walking transitive deps of already loaded DSOs
Status: RESOLVED DUPLICATE of bug 17645
Alias: None
Product: glibc
Classification: Unclassified
Component: libc (show other bugs)
Version: 2.33
: P2 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2020-06-28 00:27 UTC by Andrew
Modified: 2020-07-07 08:16 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Last reconfirmed:
fweimer: security-


Attachments
fix_dl_map_object_deps (1.36 KB, patch)
2020-06-28 00:27 UTC, Andrew
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Andrew 2020-06-28 00:27:58 UTC
Created attachment 12665 [details]
fix_dl_map_object_deps

In workflows with lots of DSOs which are independently `dlopen`d but which have several common dependency DSOs, each `_dl_map_object_deps` call will re-walk these common transitive deps, doing O(N) `strcmp`s in `_dl_map_object` for each one, which can become costly.

I noticed this while looking into some workflows where Python code `dlopen`s a lot of DSOs, each of which shares a lot of transitive deps with the others.  Profiling shows a significant time is spent in `strcmp`. 

It looks like much of this work can be avoided having each call to `_dl_map_object` also return whether that DSO was already loaded, and terminate the recursion if so.  An example of an attempt at this is attached which removed most of this overhead (but I'm not entirely sure it's safe).
Comment 1 Carlos O'Donell 2020-07-03 16:18:27 UTC
(In reply to Andrew from comment #0)
> Created attachment 12665 [details]
> fix_dl_map_object_deps
> 
> In workflows with lots of DSOs which are independently `dlopen`d but which
> have several common dependency DSOs, each `_dl_map_object_deps` call will
> re-walk these common transitive deps, doing O(N) `strcmp`s in
> `_dl_map_object` for each one, which can become costly.
> 
> I noticed this while looking into some workflows where Python code `dlopen`s
> a lot of DSOs, each of which shares a lot of transitive deps with the
> others.  Profiling shows a significant time is spent in `strcmp`. 
> 
> It looks like much of this work can be avoided having each call to
> `_dl_map_object` also return whether that DSO was already loaded, and
> terminate the recursion if so.  An example of an attempt at this is attached
> which removed most of this overhead (but I'm not entirely sure it's safe).

We are already working on resolving this as part of bug 17645.

We are only v2.1 of the fix that switches to a full DFS RPO sort with "use" tracking per link map to avoid visiting nodes again, and terminating the sort early if the list was already sorted.

I'm marking this as a duplicate of bug 17645.

*** This bug has been marked as a duplicate of bug 17645 ***