From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 34846 invoked by alias); 12 Dec 2019 01:30:02 -0000 Mailing-List: contact elfutils-devel-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Post: List-Help: List-Subscribe: Sender: elfutils-devel-owner@sourceware.org Received: (qmail 34718 invoked by uid 89); 12 Dec 2019 01:30:01 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Checked: by ClamAV 0.100.3 on sourceware.org X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 spammy=qsort, 6117, 113,13, 11313 X-Spam-Status: No, score=-26.9 required=5.0 tests=BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on sourceware.org X-Spam-Level: X-HELO: mail-pf1-f196.google.com Received: from mail-pf1-f196.google.com (HELO mail-pf1-f196.google.com) (209.85.210.196) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 12 Dec 2019 01:29:58 +0000 Received: by mail-pf1-f196.google.com with SMTP id 2so219719pfx.6 for ; Wed, 11 Dec 2019 17:29:57 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=osandov-com.20150623.gappssmtp.com; s=20150623; h=from:to:subject:date:message-id:in-reply-to:references:mime-version :content-transfer-encoding; bh=NhR5wfEfrJyc78uIbsDjzPWmHWipbwirrlO77GKbBQQ=; b=brM4qP1c+10k+lp3d1PPZojfk+NXVvDyDnGkeIcUNUkl4ye9W4JSVhdqzen/AsnatJ RlN7hLkGKkugQqc1K1UzHFKn67bnHQyIHOCxGF0IWDxGCbFfzWLLgRymP44MHzE7GIDr 3UR6ckyof7NaLufEilvwc0Wj2LPR2Pl9ntOHrUOzdhaxAhgOsrR1OncFdGXHGnimUhBR iMsTAVDh0ZMDeZJeWVHgEuhLQCHAZMC61NYyNjPzCo+lcpKf8YFdhmgbeMXkLJo9oeK3 IGQLSvO075vlEqJD1lkzyXvn/j6xQQZqdHjcCGwzGAyTHAs5jPW65i+QDuRo16fHpQDH ISiQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=NhR5wfEfrJyc78uIbsDjzPWmHWipbwirrlO77GKbBQQ=; b=KHVtTMfCxHimB8umnn6vKvsL4TlUAFtWVc5soStQhxoAAB+Q84Yi3C9pboHHS6q0gF vlTaC70bjNHdwVXyVtLK/kJQEQ+M5NXM83xqoOIFXbjIML42JV674RCtm5Cstt0bTlKA 9LKTDi3kkTqHhPZCnufUZHdsj1JqBYbdfOM2dOsppkjRt39UXyTA6JZkZWAzrnn25RU8 0qo/O9TZz2UfYqzWQsAbLodpyn7WqV2I2mR0pBk9f0kIhcyzyXZaetsne/OFT1L26L8M nWp1F/jeYBtlebolkvHuGrCXi6ZTLLh2pr3jmbaPoxupfwBauOPKVc9XV9hX1mzE9/t9 xYKg== X-Gm-Message-State: APjAAAUuLh06f0WTUVKDrIz+W+HL1xwcGW8HAc0DHnRpjIpxVGD2x/KE 6YMW7HZoERvG6cAjAbtCvwS9lQVtsqkGEQ== X-Google-Smtp-Source: APXvYqyUqYUKSalXMaGi308CV2OUKWc0nJ5Z6TyT9Zj38L8DOcOtKk95fpNqcIR3Pl31owj9NO8ADw== X-Received: by 2002:aa7:9118:: with SMTP id 24mr7397672pfh.182.1576114195844; Wed, 11 Dec 2019 17:29:55 -0800 (PST) Received: from vader.thefacebook.com ([2620:10d:c090:200::3:19b7]) by smtp.gmail.com with ESMTPSA id d6sm1102556pjl.8.2019.12.11.17.29.54 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Dec 2019 17:29:55 -0800 (PST) From: Omar Sandoval To: elfutils-devel@sourceware.org Subject: [PATCH 3/4] libdwfl: store module lookup table separately from segments Date: Thu, 12 Dec 2019 01:30:00 -0000 Message-Id: <4b97bcfc63d5358b9feebc2f55800cbd161a12ab.1576112311.git.osandov@fb.com> X-Mailer: git-send-email 2.24.0 In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-IsSubscribed: yes X-SW-Source: 2019-q4/txt/msg00265.txt.bz2 From: Omar Sandoval Currently, the address ranges for segments reported with dwfl_report_segment and modules are stored in the same sorted array. This requires complicated logic in reify_segments for splitting up existing segments and inserting into the table, which can have quadratic runtime in the worst case. Simplify it by adding a separate table for the module list, which we can manage much more simply. This will be especially important for the next change. Signed-off-by: Omar Sandoval --- libdwfl/ChangeLog | 14 +++- libdwfl/dwfl_addrmodule.c | 89 +++++++++++++++++++++++- libdwfl/dwfl_getmodules.c | 14 ++-- libdwfl/dwfl_module.c | 11 +-- libdwfl/libdwflP.h | 17 ++++- libdwfl/link_map.c | 7 +- libdwfl/segment.c | 143 +------------------------------------- 7 files changed, 128 insertions(+), 167 deletions(-) diff --git a/libdwfl/ChangeLog b/libdwfl/ChangeLog index 09a4a473..8dc20961 100644 --- a/libdwfl/ChangeLog +++ b/libdwfl/ChangeLog @@ -3,12 +3,24 @@ * libdwflP.h: Add new NOT_LOADED DWFL_ERROR. (Dwfl_Module): Remove coalescing state. Rename lookup_tail_ndx to next_segndx. + Rename segment member to lookup. + (Dwfl): Replace module lookup table with new definition. * relocate.c (__libdwfl_relocate_value): Return DWFL_E_NOT_LOADED if section is not loaded. (relocate): Handle DWFL_E_NOT_LOADED. * dwfl_module_getsym: Ignore DWFL_E_NOT_LOADED. - * segment.c (dwfl_report_segment): Remove coalescing logic. + * segment.c: Remove old module lookup table implementation. + (dwfl_report_segment): Remove coalescing logic. + (dwfl_addrsegment): Use dwfl_addrmodule to get module. * libdwfl.h (dwfl_report_segment): Document that IDENT is now ignored. + * dwfl_addrmodule.c: Add new module lookup table implementation. + (dwfl_addrmodule): Use new module lookup table instead of + dwfl_addrsegment. + * dwfl_getmodules.c (dwfl_getmodules): Use new module lookup table. + * dwfl_module.c (dwfl_report_begin): Clear new module lookup table. + (use): Likewise. + * link_map.c: Use dwfl_addrmodule instead of dwfl_addrsegment when + segment index is not needed. 2019-12-05 Mark Wielaard diff --git a/libdwfl/dwfl_addrmodule.c b/libdwfl/dwfl_addrmodule.c index abf1ff48..21db4883 100644 --- a/libdwfl/dwfl_addrmodule.c +++ b/libdwfl/dwfl_addrmodule.c @@ -32,11 +32,94 @@ #include "libdwflP.h" +static bool append_lookup_module (Dwfl *dwfl, Dwfl_Module *mod, GElf_Addr start, + GElf_Addr end) +{ + if (dwfl->lookup_module_elts >= dwfl->lookup_module_alloc) + { + size_t n = dwfl->lookup_module_alloc; + n = n == 0 ? 16 : n * 2; + struct dwfl_module_segment *tmp; + tmp = realloc (dwfl->lookup_module, n * sizeof (tmp[0])); + if (tmp == NULL) + { + __libdwfl_seterrno (DWFL_E_NOMEM); + return true; + } + dwfl->lookup_module = tmp; + dwfl->lookup_module_alloc = n; + } + size_t i = dwfl->lookup_module_elts++; + dwfl->lookup_module[i].start = start; + dwfl->lookup_module[i].end = end; + dwfl->lookup_module[i].mod = mod; + return false; +} + +static int compare_dwfl_module_segment (const void *a, const void *b) +{ + const struct dwfl_module_segment *seg1 = a; + const struct dwfl_module_segment *seg2 = b; + if (seg1->start < seg2->start) + return -1; + else if (seg1->start > seg2->start) + return 1; + else + return 0; +} + +static bool +create_lookup_module (Dwfl *dwfl) +{ + for (Dwfl_Module *mod = dwfl->modulelist; mod != NULL; mod = mod->next) + if (! mod->gc) + { + GElf_Addr start = __libdwfl_segment_start(dwfl, mod->low_addr); + GElf_Addr end = __libdwfl_segment_end(dwfl, mod->high_addr); + if (append_lookup_module(dwfl, mod, start, end)) + return true; + } + + qsort (dwfl->lookup_module, dwfl->lookup_module_elts, + sizeof (dwfl->lookup_module[0]), compare_dwfl_module_segment); + for (size_t i = 0; i < dwfl->lookup_module_elts; i++) + { + dwfl->lookup_module[i].mod->lookup = i; + /* If the upper boundary of the segment isn't part of the next segment, + treat it as part of the segment. */ + if (i == dwfl->lookup_module_elts - 1 + || dwfl->lookup_module[i].end < dwfl->lookup_module[i + 1].start) + dwfl->lookup_module[i].end++; + } + return false; +} + +static int search_dwfl_module_segment (const void *key, const void *elt) +{ + Dwarf_Addr address = *(Dwarf_Addr *)key; + const struct dwfl_module_segment *seg = elt; + if (address < seg->start) + return -1; + else if (address >= seg->end) + return 1; + else + return 0; +} + Dwfl_Module * dwfl_addrmodule (Dwfl *dwfl, Dwarf_Addr address) { - Dwfl_Module *mod; - (void) INTUSE(dwfl_addrsegment) (dwfl, address, &mod); - return mod; + if (unlikely (dwfl == NULL) + || (unlikely (dwfl->lookup_module_elts == 0) + && unlikely (create_lookup_module (dwfl)))) + return NULL; + + struct dwfl_module_segment *seg = bsearch (&address, dwfl->lookup_module, + dwfl->lookup_module_elts, + sizeof (dwfl->lookup_module[0]), + search_dwfl_module_segment); + if (seg == NULL) + return NULL; + return seg->mod; } INTDEF (dwfl_addrmodule) diff --git a/libdwfl/dwfl_getmodules.c b/libdwfl/dwfl_getmodules.c index 243cb04d..807fe855 100644 --- a/libdwfl/dwfl_getmodules.c +++ b/libdwfl/dwfl_getmodules.c @@ -61,17 +61,17 @@ dwfl_getmodules (Dwfl *dwfl, else m = m->next; } - else if (((offset & 3) == 2) && likely (dwfl->lookup_module != NULL)) + else if (((offset & 3) == 2) && likely (dwfl->lookup_module_elts > 0)) { offset >>= 2; - if ((size_t) offset - 1 == dwfl->lookup_elts) + if ((size_t) offset - 1 == dwfl->lookup_module_elts) return 0; - if (unlikely ((size_t) offset - 1 > dwfl->lookup_elts)) + if (unlikely ((size_t) offset - 1 > dwfl->lookup_module_elts)) return -1; - m = dwfl->lookup_module[offset - 1]; + m = dwfl->lookup_module[offset - 1].mod; if (unlikely (m == NULL)) return -1; } @@ -87,9 +87,9 @@ dwfl_getmodules (Dwfl *dwfl, ++offset; m = m->next; if (ok != DWARF_CB_OK) - return ((dwfl->lookup_module == NULL) ? ((offset << 2) | 1) - : (((m == NULL ? (ptrdiff_t) dwfl->lookup_elts + 1 - : m->segment + 1) << 2) | 2)); + return ((dwfl->lookup_module_elts == 0) ? ((offset << 2) | 1) + : (((m == NULL ? (ptrdiff_t) dwfl->lookup_module_elts + 1 + : m->lookup + 1) << 2) | 2)); } return 0; } diff --git a/libdwfl/dwfl_module.c b/libdwfl/dwfl_module.c index e7dfdace..4aa9aa2c 100644 --- a/libdwfl/dwfl_module.c +++ b/libdwfl/dwfl_module.c @@ -135,8 +135,9 @@ INTDEF (dwfl_report_begin_add) void dwfl_report_begin (Dwfl *dwfl) { - /* Clear the segment lookup table. */ + /* Clear the segment and module lookup tables. */ dwfl->lookup_elts = 0; + dwfl->lookup_module_elts = 0; for (Dwfl_Module *m = dwfl->modulelist; m != NULL; m = m->next) m->gc = true; @@ -150,13 +151,7 @@ use (Dwfl_Module *mod, Dwfl_Module **tailp, Dwfl *dwfl) { mod->next = *tailp; *tailp = mod; - - if (unlikely (dwfl->lookup_module != NULL)) - { - free (dwfl->lookup_module); - dwfl->lookup_module = NULL; - } - + dwfl->lookup_module_elts = 0; return mod; } diff --git a/libdwfl/libdwflP.h b/libdwfl/libdwflP.h index d21471b1..6661cc4c 100644 --- a/libdwfl/libdwflP.h +++ b/libdwfl/libdwflP.h @@ -113,6 +113,13 @@ struct Dwfl_User_Core int fd; /* close if >= 0. */ }; +struct dwfl_module_segment +{ + GElf_Addr start; + GElf_Addr end; + Dwfl_Module *mod; +}; + struct Dwfl { const Dwfl_Callbacks *callbacks; @@ -127,14 +134,18 @@ struct Dwfl GElf_Addr segment_align; /* Smallest granularity of segments. */ - /* Binary search table in three parallel malloc'd arrays. */ + /* Binary search table of segments in two parallel malloc'd arrays. */ size_t lookup_elts; /* Elements in use. */ size_t lookup_alloc; /* Elements allococated. */ GElf_Addr *lookup_addr; /* Start address of segment. */ - Dwfl_Module **lookup_module; /* Module associated with segment, or null. */ int *lookup_segndx; /* User segment index, or -1. */ int next_segndx; + /* Binary search table of module address ranges. */ + struct dwfl_module_segment *lookup_module; + size_t lookup_module_elts; + size_t lookup_module_alloc; + struct Dwfl_User_Core *user_core; }; @@ -216,7 +227,7 @@ struct Dwfl_Module Dwarf_CFI *dwarf_cfi; /* Cached DWARF CFI for this module. */ Dwarf_CFI *eh_cfi; /* Cached EH CFI for this module. */ - int segment; /* Index of first segment table entry. */ + int lookup; /* Index in module lookup table. */ bool gc; /* Mark/sweep flag. */ bool is_executable; /* Use Dwfl::executable_for_core? */ }; diff --git a/libdwfl/link_map.c b/libdwfl/link_map.c index 29307c74..befb39e4 100644 --- a/libdwfl/link_map.c +++ b/libdwfl/link_map.c @@ -175,8 +175,7 @@ integrated_memory_callback (Dwfl *dwfl, int ndx, /* Now look for module text covering this address. */ - Dwfl_Module *mod; - (void) INTUSE(dwfl_addrsegment) (dwfl, vaddr, &mod); + Dwfl_Module *mod = INTUSE(dwfl_addrmodule) (dwfl, vaddr); if (mod == NULL) return false; @@ -588,9 +587,7 @@ consider_executable (Dwfl_Module *mod, GElf_Addr at_phdr, GElf_Addr at_entry, mod->high_addr -= mod_bias; mod->low_addr += bias; mod->high_addr += bias; - - free (mod->dwfl->lookup_module); - mod->dwfl->lookup_module = NULL; + mod->dwfl->lookup_module_elts = 0; } } } diff --git a/libdwfl/segment.c b/libdwfl/segment.c index f6a3e84e..9bf8b282 100644 --- a/libdwfl/segment.c +++ b/libdwfl/segment.c @@ -76,19 +76,6 @@ insert (Dwfl *dwfl, size_t i, GElf_Addr start, GElf_Addr end, int segndx) dwfl->lookup_alloc = n; dwfl->lookup_addr = naddr; dwfl->lookup_segndx = nsegndx; - - if (dwfl->lookup_module != NULL) - { - /* Make sure this array is big enough too. */ - Dwfl_Module **old = dwfl->lookup_module; - dwfl->lookup_module = realloc (dwfl->lookup_module, - sizeof dwfl->lookup_module[0] * n); - if (unlikely (dwfl->lookup_module == NULL)) - { - free (old); - return true; - } - } } if (unlikely (i < dwfl->lookup_elts)) @@ -98,17 +85,12 @@ insert (Dwfl *dwfl, size_t i, GElf_Addr start, GElf_Addr end, int segndx) move * sizeof dwfl->lookup_addr[0]); memmove (&dwfl->lookup_segndx[i + need], &dwfl->lookup_segndx[i], move * sizeof dwfl->lookup_segndx[0]); - if (dwfl->lookup_module != NULL) - memmove (&dwfl->lookup_module[i + need], &dwfl->lookup_module[i], - move * sizeof dwfl->lookup_module[0]); } if (need_start) { dwfl->lookup_addr[i] = start; dwfl->lookup_segndx[i] = segndx; - if (dwfl->lookup_module != NULL) - dwfl->lookup_module[i] = NULL; ++i; } else @@ -118,8 +100,6 @@ insert (Dwfl *dwfl, size_t i, GElf_Addr start, GElf_Addr end, int segndx) { dwfl->lookup_addr[i] = end; dwfl->lookup_segndx[i] = -1; - if (dwfl->lookup_module != NULL) - dwfl->lookup_module[i] = NULL; } dwfl->lookup_elts += need; @@ -154,131 +134,20 @@ lookup (Dwfl *dwfl, GElf_Addr address, int hint) return -1; } -static bool -reify_segments (Dwfl *dwfl) -{ - int hint = -1; - int highest = -1; - bool fixup = false; - for (Dwfl_Module *mod = dwfl->modulelist; mod != NULL; mod = mod->next) - if (! mod->gc) - { - const GElf_Addr start = __libdwfl_segment_start (dwfl, mod->low_addr); - const GElf_Addr end = __libdwfl_segment_end (dwfl, mod->high_addr); - bool resized = false; - - int idx = lookup (dwfl, start, hint); - if (unlikely (idx < 0)) - { - /* Module starts below any segment. Insert a low one. */ - if (unlikely (insert (dwfl, 0, start, end, -1))) - return true; - idx = 0; - resized = true; - } - else if (dwfl->lookup_addr[idx] > start) - { - /* The module starts in the middle of this segment. Split it. */ - if (unlikely (insert (dwfl, idx + 1, start, end, - dwfl->lookup_segndx[idx]))) - return true; - ++idx; - resized = true; - } - else if (dwfl->lookup_addr[idx] < start) - { - /* The module starts past the end of this segment. - Add a new one. */ - if (unlikely (insert (dwfl, idx + 1, start, end, -1))) - return true; - ++idx; - resized = true; - } - - if ((size_t) idx + 1 < dwfl->lookup_elts - && end < dwfl->lookup_addr[idx + 1]) - { - /* The module ends in the middle of this segment. Split it. */ - if (unlikely (insert (dwfl, idx + 1, - end, dwfl->lookup_addr[idx + 1], -1))) - return true; - resized = true; - } - - if (dwfl->lookup_module == NULL) - { - dwfl->lookup_module = calloc (dwfl->lookup_alloc, - sizeof dwfl->lookup_module[0]); - if (unlikely (dwfl->lookup_module == NULL)) - return true; - } - - /* Cache a backpointer in the module. */ - mod->segment = idx; - - /* Put MOD in the table for each segment that's inside it. */ - do - dwfl->lookup_module[idx++] = mod; - while ((size_t) idx < dwfl->lookup_elts - && dwfl->lookup_addr[idx] < end); - assert (dwfl->lookup_module[mod->segment] == mod); - - if (resized && idx - 1 >= highest) - /* Expanding the lookup tables invalidated backpointers - we've already stored. Reset those ones. */ - fixup = true; - - highest = idx - 1; - hint = (size_t) idx < dwfl->lookup_elts ? idx : -1; - } - - if (fixup) - /* Reset backpointer indices invalidated by table insertions. */ - for (size_t idx = 0; idx < dwfl->lookup_elts; ++idx) - if (dwfl->lookup_module[idx] != NULL) - dwfl->lookup_module[idx]->segment = idx; - - return false; -} - int dwfl_addrsegment (Dwfl *dwfl, Dwarf_Addr address, Dwfl_Module **mod) { if (unlikely (dwfl == NULL)) return -1; - if (unlikely (dwfl->lookup_module == NULL) - && mod != NULL - && unlikely (reify_segments (dwfl))) - { - __libdwfl_seterrno (DWFL_E_NOMEM); - return -1; - } - int idx = lookup (dwfl, address, -1); - if (likely (mod != NULL)) - { - if (unlikely (idx < 0) || unlikely (dwfl->lookup_module == NULL)) - *mod = NULL; - else - { - *mod = dwfl->lookup_module[idx]; - - /* If this segment does not have a module, but the address is - the upper boundary of the previous segment's module, use that. */ - if (*mod == NULL && idx > 0 && dwfl->lookup_addr[idx] == address) - { - *mod = dwfl->lookup_module[idx - 1]; - if (*mod != NULL && (*mod)->high_addr != address) - *mod = NULL; - } - } - } - if (likely (idx >= 0)) /* Translate internal segment table index to user segment index. */ idx = dwfl->lookup_segndx[idx]; + if (mod != NULL) + *mod = INTUSE(dwfl_addrmodule) (dwfl, address); + return idx; } INTDEF (dwfl_addrsegment) @@ -301,12 +170,6 @@ dwfl_report_segment (Dwfl *dwfl, int ndx, const GElf_Phdr *phdr, GElf_Addr bias, phdr->p_align < dwfl->segment_align)) dwfl->segment_align = phdr->p_align; - if (unlikely (dwfl->lookup_module != NULL)) - { - free (dwfl->lookup_module); - dwfl->lookup_module = NULL; - } - GElf_Addr start = __libdwfl_segment_start (dwfl, bias + phdr->p_vaddr); GElf_Addr end = __libdwfl_segment_end (dwfl, bias + phdr->p_vaddr + phdr->p_memsz); -- 2.24.0