From patchwork Wed Sep 9 01:22:47 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Lance Taylor X-Patchwork-Id: 1360286 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=gcc.gnu.org Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=c1xsa1OU; dkim-atps=neutral Received: from sourceware.org (server2.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 ozlabs.org (Postfix) with ESMTPS id 4BmPQz5Svpz9sSJ for ; Wed, 9 Sep 2020 11:23:06 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2518E3950C08; Wed, 9 Sep 2020 01:23:03 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2518E3950C08 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1599614583; bh=lNny+qlFl8xxCeWDxudeJ2sVyDZoQW3EJPB+29xfDfQ=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=c1xsa1OU3vPULsJ08cMCkxf6/ADLyh1A+1fNtXrQwQrfupEGnEU8fmTRMP89PhaiC u+UNDQGSsqDD9ZTnNZof0SfO33S0OouBYmeSeFhrqX9Ng+VAoREUIefr0nSdMYEeVV Hrwa2cm3m2l/WiYFt2S5nAaVQcuaunOVyvAerECw= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-ej1-x62f.google.com (mail-ej1-x62f.google.com [IPv6:2a00:1450:4864:20::62f]) by sourceware.org (Postfix) with ESMTPS id 06929385783E for ; Wed, 9 Sep 2020 01:23:00 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 06929385783E Received: by mail-ej1-x62f.google.com with SMTP id z22so1098917ejl.7 for ; Tue, 08 Sep 2020 18:22:59 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=lNny+qlFl8xxCeWDxudeJ2sVyDZoQW3EJPB+29xfDfQ=; b=Q8tINbyfnN+P/sJr/AWpX7x+UOGoGSzIXl1MXUA59Ap1m4xwWMXa4QMNW6W55+QNbi kASK0WQiFoYKmGIRkI16dxC2d7n2xgstTswiR9hwCV5lAA3kxlBn4lojFbTzQo5zTfBO IOovbd5EHhGiS5HgW+xmY5rPCuNVo8DNT70pCYucsOgMRXlBHtxZ0UIk4QHtyXjrvZ3j hU1+LCO7rY82vsc20plkORxJ418jyofgttZvFnVp69GrYQTaJe5SAtknFAtPUdoBsSbz gZzu3i15Ps3cU+cJ0uhZEgfiwdps+gB8HQEDo1uGnCrd5cvISr/Q8YjMuVQdo0KXyxjc X4cQ== X-Gm-Message-State: AOAM532zHAuEuqogi8tmdJeaczdg7/2of9wGY7CUinlSFrZ9FkX9CgXv Rl6O00YoZEPqu1EAtSDqqBoMUalGCfZkoLfs79FaRuXqnb2QbA== X-Google-Smtp-Source: ABdhPJxfFQ5A/0v9w/ldIwlpkx+/4ievZ01CSUMb0C6lMBL43P+IkNjE4FgGthgkInmu96bDAjVD5nuZTw23jWDUVts= X-Received: by 2002:a17:906:2b06:: with SMTP id a6mr1223520ejg.209.1599614578624; Tue, 08 Sep 2020 18:22:58 -0700 (PDT) MIME-Version: 1.0 Date: Tue, 8 Sep 2020 18:22:47 -0700 Message-ID: Subject: libbacktrace patch committed: Avoid ambiguous binary search To: gcc-patches X-Spam-Status: No, score=-10.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Ian Lance Taylor via Gcc-patches From: Ian Lance Taylor Reply-To: Ian Lance Taylor Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" This patch to libbacktrace avoids ambiguous binary searches. Searching for a range match can cause the search order to not match the sort order, which can cause libbacktrace to miss matching entries. This patch allocates an extra entry at the end of function_addrs and unit_addrs vectors, so that we can safely compare to the next entry when searching. It adjusts the matching code accordingly. This fixes https://github.com/ianlancetaylor/libbacktrace/issues/44. Bootstrapped and ran libbacktrace and libgo tests on x86_64-pc-linux-gnu. Committed to mainline. Ian * dwarf.c (function_addrs_search): Compare against the next entry low address, not the high address. (unit_addrs_search): Likewise. (build_address_map): Add a trailing unit_addrs. (read_function_entry): Add a trailing function_addrs. (read_function_info): Likewise. (report_inlined_functions): Search backward for function_addrs match. (dwarf_lookup_pc): Search backward for unit_addrs and function_addrs matches. diff --git a/libbacktrace/dwarf.c b/libbacktrace/dwarf.c index 006c8181622..386701bffea 100644 --- a/libbacktrace/dwarf.c +++ b/libbacktrace/dwarf.c @@ -1164,9 +1164,11 @@ function_addrs_compare (const void *v1, const void *v2) return strcmp (a1->function->name, a2->function->name); } -/* Compare a PC against a function_addrs for bsearch. Note that if - there are multiple ranges containing PC, which one will be returned - is unpredictable. We compensate for that in dwarf_fileline. */ +/* Compare a PC against a function_addrs for bsearch. We always + allocate an entra entry at the end of the vector, so that this + routine can safely look at the next entry. Note that if there are + multiple ranges containing PC, which one will be returned is + unpredictable. We compensate for that in dwarf_fileline. */ static int function_addrs_search (const void *vkey, const void *ventry) @@ -1178,7 +1180,7 @@ function_addrs_search (const void *vkey, const void *ventry) pc = *key; if (pc < entry->low) return -1; - else if (pc >= entry->high) + else if (pc > (entry + 1)->low) return 1; else return 0; @@ -1249,9 +1251,11 @@ unit_addrs_compare (const void *v1, const void *v2) return 0; } -/* Compare a PC against a unit_addrs for bsearch. Note that if there - are multiple ranges containing PC, which one will be returned is - unpredictable. We compensate for that in dwarf_fileline. */ +/* Compare a PC against a unit_addrs for bsearch. We always allocate + an entry entry at the end of the vector, so that this routine can + safely look at the next entry. Note that if there are multiple + ranges containing PC, which one will be returned is unpredictable. + We compensate for that in dwarf_fileline. */ static int unit_addrs_search (const void *vkey, const void *ventry) @@ -1263,7 +1267,7 @@ unit_addrs_search (const void *vkey, const void *ventry) pc = *key; if (pc < entry->low) return -1; - else if (pc >= entry->high) + else if (pc > (entry + 1)->low) return 1; else return 0; @@ -2091,6 +2095,7 @@ build_address_map (struct backtrace_state *state, uintptr_t base_address, size_t i; struct unit **pu; size_t unit_offset = 0; + struct unit_addrs *pa; memset (&addrs->vec, 0, sizeof addrs->vec); memset (&unit_vec->vec, 0, sizeof unit_vec->vec); @@ -2231,6 +2236,17 @@ build_address_map (struct backtrace_state *state, uintptr_t base_address, if (info.reported_underflow) goto fail; + /* Add a trailing addrs entry, but don't include it in addrs->count. */ + pa = ((struct unit_addrs *) + backtrace_vector_grow (state, sizeof (struct unit_addrs), + error_callback, data, &addrs->vec)); + if (pa == NULL) + goto fail; + pa->low = 0; + --pa->low; + pa->high = pa->low; + pa->u = NULL; + unit_vec->vec = units; unit_vec->count = units_count; return 1; @@ -3404,8 +3420,23 @@ read_function_entry (struct backtrace_state *state, struct dwarf_data *ddata, if (fvec.count > 0) { + struct function_addrs *p; struct function_addrs *faddrs; + /* Allocate a trailing entry, but don't include it + in fvec.count. */ + p = ((struct function_addrs *) + backtrace_vector_grow (state, + sizeof (struct function_addrs), + error_callback, data, + &fvec.vec)); + if (p == NULL) + return 0; + p->low = 0; + --p->low; + p->high = p->low; + p->function = NULL; + if (!backtrace_vector_release (state, &fvec.vec, error_callback, data)) return 0; @@ -3439,6 +3470,7 @@ read_function_info (struct backtrace_state *state, struct dwarf_data *ddata, struct function_vector lvec; struct function_vector *pfvec; struct dwarf_buf unit_buf; + struct function_addrs *p; struct function_addrs *addrs; size_t addrs_count; @@ -3470,6 +3502,18 @@ read_function_info (struct backtrace_state *state, struct dwarf_data *ddata, if (pfvec->count == 0) return; + /* Allocate a trailing entry, but don't include it in + pfvec->count. */ + p = ((struct function_addrs *) + backtrace_vector_grow (state, sizeof (struct function_addrs), + error_callback, data, &pfvec->vec)); + if (p == NULL) + return; + p->low = 0; + --p->low; + p->high = p->low; + p->function = NULL; + addrs_count = pfvec->count; if (fvec == NULL) @@ -3506,30 +3550,46 @@ report_inlined_functions (uintptr_t pc, struct function *function, backtrace_full_callback callback, void *data, const char **filename, int *lineno) { - struct function_addrs *function_addrs; + struct function_addrs *p; + struct function_addrs *match; struct function *inlined; int ret; if (function->function_addrs_count == 0) return 0; - function_addrs = ((struct function_addrs *) - bsearch (&pc, function->function_addrs, - function->function_addrs_count, - sizeof (struct function_addrs), - function_addrs_search)); - if (function_addrs == NULL) + p = ((struct function_addrs *) + bsearch (&pc, function->function_addrs, + function->function_addrs_count, + sizeof (struct function_addrs), + function_addrs_search)); + if (p == NULL) return 0; - while (((size_t) (function_addrs - function->function_addrs) + 1 - < function->function_addrs_count) - && pc >= (function_addrs + 1)->low - && pc < (function_addrs + 1)->high) - ++function_addrs; + /* Here pc >= p->low && pc < (p + 1)->low. The function_addrs are + sorted by low, so we are at the end of a range of function_addrs + with the same low alue. Walk backward and use the first range + that includes pc. */ + match = NULL; + while (1) + { + if (pc < p->high) + { + match = p; + break; + } + if (p == function->function_addrs) + break; + if ((p - 1)->low < p->low) + break; + --p; + } + if (match == NULL) + return 0; /* We found an inlined call. */ - inlined = function_addrs->function; + inlined = match->function; /* Report any calls inlined into this one. */ ret = report_inlined_functions (pc, inlined, callback, data, @@ -3562,11 +3622,13 @@ dwarf_lookup_pc (struct backtrace_state *state, struct dwarf_data *ddata, int *found) { struct unit_addrs *entry; + int found_entry; struct unit *u; int new_data; struct line *lines; struct line *ln; - struct function_addrs *function_addrs; + struct function_addrs *p; + struct function_addrs *fmatch; struct function *function; const char *filename; int lineno; @@ -3586,14 +3648,29 @@ dwarf_lookup_pc (struct backtrace_state *state, struct dwarf_data *ddata, return 0; } - /* If there are multiple ranges that contain PC, use the last one, - in order to produce predictable results. If we assume that all - ranges are properly nested, then the last range will be the - smallest one. */ - while ((size_t) (entry - ddata->addrs) + 1 < ddata->addrs_count - && pc >= (entry + 1)->low - && pc < (entry + 1)->high) - ++entry; + /* Here pc >= entry->low && pc < (entry + 1)->low. The unit_addrs + are sorted by low, so we are at the end of a range of unit_addrs + with the same low value. Walk backward and use the first range + that includes pc. */ + found_entry = 0; + while (1) + { + if (pc < entry->high) + { + found_entry = 1; + break; + } + if (entry == ddata->addrs) + break; + if ((entry - 1)->low < entry->low) + break; + --entry; + } + if (!found_entry) + { + *found = 0; + return 0; + } /* We need the lines, lines_count, function_addrs, function_addrs_count fields of u. If they are not set, we need @@ -3629,6 +3706,7 @@ dwarf_lookup_pc (struct backtrace_state *state, struct dwarf_data *ddata, new_data = 0; if (lines == NULL) { + struct function_addrs *function_addrs; size_t function_addrs_count; struct line_header lhdr; size_t count; @@ -3745,24 +3823,36 @@ dwarf_lookup_pc (struct backtrace_state *state, struct dwarf_data *ddata, if (entry->u->function_addrs_count == 0) return callback (data, pc, ln->filename, ln->lineno, NULL); - function_addrs = ((struct function_addrs *) - bsearch (&pc, entry->u->function_addrs, - entry->u->function_addrs_count, - sizeof (struct function_addrs), - function_addrs_search)); - if (function_addrs == NULL) + p = ((struct function_addrs *) + bsearch (&pc, entry->u->function_addrs, + entry->u->function_addrs_count, + sizeof (struct function_addrs), + function_addrs_search)); + if (p == NULL) return callback (data, pc, ln->filename, ln->lineno, NULL); - /* If there are multiple function ranges that contain PC, use the - last one, in order to produce predictable results. */ - - while (((size_t) (function_addrs - entry->u->function_addrs + 1) - < entry->u->function_addrs_count) - && pc >= (function_addrs + 1)->low - && pc < (function_addrs + 1)->high) - ++function_addrs; + /* Here pc >= p->low && pc < (p + 1)->low. The function_addrs are + sorted by low, so we are at the end of a range of function_addrs + with the same low alue. Walk backward and use the first range + that includes pc. */ + fmatch = NULL; + while (1) + { + if (pc < p->high) + { + fmatch = p; + break; + } + if (p == entry->u->function_addrs) + break; + if ((p - 1)->low < p->low) + break; + --p; + } + if (fmatch == NULL) + return callback (data, pc, ln->filename, ln->lineno, NULL); - function = function_addrs->function; + function = fmatch->function; filename = ln->filename; lineno = ln->lineno;