From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-oi1-x22e.google.com (mail-oi1-x22e.google.com [IPv6:2607:f8b0:4864:20::22e]) by sourceware.org (Postfix) with ESMTPS id BA42A387700A for ; Thu, 12 Mar 2020 18:28:28 +0000 (GMT) Received: by mail-oi1-x22e.google.com with SMTP id k21so6530055oij.5 for ; Thu, 12 Mar 2020 11:28:28 -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:references:in-reply-to:from:date :message-id:subject:to:cc; bh=rhuVDVKSah/F1mEvg5steOQBJFIUMEKQjTS4n1HSTSE=; b=bYk3o29YikDKZhHIyI/wEg0UHifdyV6IO4Y4h1OsZ0rmkPbDjPnmfnEG65m1YoJLIO Yl9ih1HWYLQb2SGTyitYIio6DPcDWFABKDOPCfGK0SdQh0OX4U/A+W9UE2lfDWp0FLdq +0A7QzGwaOBA8UfT1tZeWqed8qzbzWNyeKob8IhdgrmEnhvc70NOE4ZEuxwDv5Wc517p PDP90rCWQrQu8I0pgwZx8bWCkJk0mRG4L8ejDNOQ0GzZry8Tj5SOc4BRU5ozsCzHAqhz 6x/pmNkl7hLqZa83+to0qW0V2Utjxbv7QUoXHcQG1agrWyedz4kfuQ3vMOwe/wAvoiRp 7/oQ== X-Gm-Message-State: ANhLgQ3p0e7DwvC38MffOYLDHTYEBEiJVfXCdPpqb4wP03S+1Nttyc2N KpOtTtndHD6nTvz2k6TmePqZMdDKPL2ZtFsmshYhXQ== X-Google-Smtp-Source: ADFU+vvOL0U5tuLVF9vHd0PSSNwwRBsLzbYdiytZUtP4fkoHOXdtgOT2xc/ghEqqruCkOL3fPQ4zZ9QKlVEJqOSswv8= X-Received: by 2002:aca:c78e:: with SMTP id x136mr3681656oif.116.1584037707630; Thu, 12 Mar 2020 11:28:27 -0700 (PDT) MIME-Version: 1.0 References: <94e33268f64060fc887670f4ee5ed524050cbcc7.1580902412.git.andrew.burgess@embecosm.com> <20200311220231.GJ3317@embecosm.com> In-Reply-To: From: Christian Biesinger Date: Thu, 12 Mar 2020 13:27:51 -0500 Message-ID: Subject: Re: [PATCHv3] Fix range end handling of inlined subroutines To: Bernd Edlinger Cc: Andrew Burgess , "gdb-patches@sourceware.org" Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-42.6 required=5.0 tests=BAYES_00, DKIMWL_WL_MED, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, ENV_AND_HDR_SPF_MATCH, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, USER_IN_DEF_DKIM_WL, USER_IN_DEF_SPF_WL 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: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 12 Mar 2020 18:28:30 -0000 On Thu, Mar 12, 2020 at 1:21 PM Bernd Edlinger wrote: > > On 3/11/20 11:02 PM, Andrew Burgess wrote: > > * Bernd Edlinger [2020-03-08 14:57:35 +0000]: > > > >> On 2/22/20 7:38 AM, Bernd Edlinger wrote: > >>> On 2/9/20 10:07 PM, Bernd Edlinger wrote: > >>>> Hi, > >>>> > >>>> this is based on Andrew's patch here: > >>>> > >>>> https://sourceware.org/ml/gdb-patches/2020-02/msg00092.html > >>>> > >>>> This and adds a heuristic to fix the case where caller > >>>> and callee reside in the same subfile, it uses > >>>> the recorded is-stmt bits and locates end of > >>>> range infos, including the previously ignored empty > >>>> range, and adjusting is-stmt info at this > >>>> same pc, when the last item is not-is-stmt, the > >>>> previous line table entries are dubious and > >>>> we reset the is-stmt bit there. > >>>> This fixes the new test case in Andrew's patch. > >>>> > >>>> It understood, that this is just a heuristic > >>>> approach, since we do not have exactly the data, > >>>> which is needed to determine at which of the identical > >>>> PCs in the line table the subroutine actually ends. > >>>> So, this tries to be as conservative as possible, > >>>> just changing what is absolutely necessary. > >>>> > >>>> This patch itself is preliminary, since the is-stmt patch > >>>> needs to be rebased after the refactoring of > >>>> dwarf2read.c from yesterday, so I will have to rebase > >>>> this patch as well, but decided to wait for Andrew. > >>>> > >>>> > >>> > >>> So, this is an update to my previous patch above: > >>> https://sourceware.org/ml/gdb-patches/2020-02/msg00262.html > >>> > >>> It improves performance on big data, by using binary > >>> search to locate the bogus line table entries. > >>> Otherwise it behaves identical to the previous version, > >>> and is still waiting for Andrew's patch before it can > >>> be applied. > >>> > >>> > >> > >> Rebased to match Andrew's updated patch of today. > > > > > > Bernd, > > > > Thanks for working on this. This looks like a great improvement, but > > I have a could of questions / comment inline below. > > > > Thanks, > > Andrew > > > > > >> > >> > >> Thanks > >> Bernd. > > > >> From 010f1774ec69d5cab48db9b7a5fb9de3d5860f97 Mon Sep 17 00:00:00 2001 > >> From: Bernd Edlinger > >> Date: Sun, 9 Feb 2020 21:13:17 +0100 > >> Subject: [PATCH] Fix range end handling of inlined subroutines > >> > >> Since the is_stmt is now handled, it becomes > >> possible to locate dubious is_stmt line entries > >> at the end of an inlined function, even if the > >> called inline function is in the same subfile. > >> > >> When there is a sequence of line entries at the > >> same address where an inline range ends, and the > >> last item has is_stmt = 0, we force all previous > >> items to have is_stmt = 0 as well. > > > > This describes _what_ we're doing... > > > >> > >> If the last line at that address has is_stmt = 1, > >> there is no need to change anything, since a step > >> over will always stop at that last line from the > >> same address, which is fine, since it is outside > >> the subroutine. > > > > This describes what we're _not_ doing... > > > > ... it just feels like this description would benefit for a bit more > > _why_. How does setting all the is_stmt fields to 0 help us? What > > cases step/next should we expect to see improvement in? > > > > I'm also worried that setting is_stmt to false will mean we loose the > > ability to set breakpoints on some lines using file:line syntax. I > > wonder if we should consider coming up with a solution that both > > preserves the ability to set breakpoints, while also giving the > > benefits for step/next. > > > > Maybe as a followup. The breakpoints on theses lines are *very* > problematic, as the call stack is almost always wrong. From the block > info they appear to be part of the caller, but from the line table they > are located in the subroutine, when you are at this breakpoint, an > ordinary user can't make sense of the call stack, as one call frame is > missing. > > The is-stmt patch does the same, removing line infos that could > in theory be used as breakpoints. See buildsym_compunit::record_line: > > /* Normally, we treat lines as unsorted. But the end of sequence > marker is special. We sort line markers at the same PC by line > number, so end of sequence markers (which have line == 0) appear > first. This is right if the marker ends the previous function, > and there is no padding before the next function. But it is > wrong if the previous line was empty and we are now marking a > switch to a different subfile. We must leave the end of sequence > marker at the end of this group of lines, not sort the empty line > to after the marker. The easiest way to accomplish this is to > delete any empty lines from our table, if they are followed by > end of sequence markers. All we lose is the ability to set > breakpoints at some lines which contain no instructions > anyway. */ > if (line == 0 && subfile->line_vector->nitems > 0) > { > e = subfile->line_vector->item + subfile->line_vector->nitems - 1; > while (subfile->line_vector->nitems > 0 && e->pc == pc) > { > e--; > subfile->line_vector->nitems--; > } > } > > > This is invoked if a is-stmt line is followed by > a non-stmt line of another CU, at the same PC. > This is previously the non-is-stmt lines were all ignored, > but now the non-is-stmt makes an end marker in the current > CU and a non-is-stmt line in the next CU. > This deletion is exactly what makes the other patch work. > > But I think it is not necessary to remove those lines altogether, > instead we can just make them non-is-stmt lines, which would > better match to what this patch does. > > While I write these lines, I see an UB in the above code, > since e-- can decrement the pointer before the beginning of the > line_vector, when nitems becomes 0, the value is not used, but > the pointer value e indeterminate if I see that right. > > I will send a patch for that, when I find time for it. > > >> > >> This is about the best we can do at the moment, > >> unless location view information are added to the > >> block ranges debug info structure, and location > >> views are implemented in gdb in general. > >> > >> gdb: > >> 2020-03-08 Bernd Edlinger > >> > >> * buildsym.c (buildsym_compunit::record_inline_range_end, > >> patch_inline_end_pos): New helper functions. > >> (buildsym_compunit::end_symtab_with_blockvector): Patch line table. > >> (buildsym_compunit::~buildsym_compunit): Cleanup m_inline_end_vector. > >> * buildsym.h (buildsym_compunit::record_inline_range_end): Declare. > >> (buildsym_compunit::m_inline_end_vector, > >> buildsym_compunit::m_inline_end_vector_length, > >> buildsym_compunit::m_inline_end_vector_nitems): New data items. > >> * dwarf2/read.c (dwarf2_rnglists_process, > >> dwarf2_ranges_process): Don't ignore empty ranges here. > >> (dwarf2_ranges_read): Ignore empty ranges here. > >> (dwarf2_record_block_ranges): Pass end of range PC to > >> record_inline_range_end for inline functions. > >> > >> gdb/testsuite: > >> 2020-03-08 Bernd Edlinger > >> > >> * gdb.cp/step-and-next-inline.exp: Adjust test. > >> --- > >> gdb/buildsym.c | 84 +++++++++++++++++++++++++++ > >> gdb/buildsym.h | 11 ++++ > >> gdb/dwarf2/read.c | 22 ++++--- > >> gdb/testsuite/gdb.cp/step-and-next-inline.exp | 17 ------ > >> 4 files changed, 108 insertions(+), 26 deletions(-) > >> > >> diff --git a/gdb/buildsym.c b/gdb/buildsym.c > >> index 24aeba8..f02b7ce 100644 > >> --- a/gdb/buildsym.c > >> +++ b/gdb/buildsym.c > >> @@ -113,6 +113,8 @@ struct pending_block > >> next1 = next->next; > >> xfree ((void *) next); > >> } > >> + > >> + xfree (m_inline_end_vector); > >> } > >> > >> struct macro_table * > >>>> this patch as well, but decided to wait for Andrew. > >> @@ -732,6 +734,84 @@ struct blockvector * > >> } > >> > >> > >> +/* Record a PC where a inlined subroutine ends. */ > >> + > >> +void > >> +buildsym_compunit::record_inline_range_end (CORE_ADDR end) > >> +{ > >> + if (m_inline_end_vector == nullptr) > >> + { > >> + m_inline_end_vector_length = INITIAL_LINE_VECTOR_LENGTH; > >> + m_inline_end_vector = (CORE_ADDR *) > >> + xmalloc (sizeof (CORE_ADDR) * m_inline_end_vector_length); > >> + m_inline_end_vector_nitems = 0; > >> + } > >> + else if (m_inline_end_vector_nitems == m_inline_end_vector_length) > >> + { > >> + m_inline_end_vector_length *= 2; > >> + m_inline_end_vector = (CORE_ADDR *) > >> + xrealloc ((char *) m_inline_end_vector, > >> + sizeof (CORE_ADDR) * m_inline_end_vector_length); > >> + } > >> + > >> + m_inline_end_vector[m_inline_end_vector_nitems++] = end; > >> +} > >> + > >> + > >> +/* Patch the is_stmt bits at the given inline end address. > >> + The line table has to be already sorted. */ > >> + > >> +static void > >> +patch_inline_end_pos (struct linetable *table, CORE_ADDR end) > >> +{ > >> + int a = 2, b = table->nitems - 1; > >> + struct linetable_entry *items = table->item; > >> + > >> + /* We need at least two items with pc = end in the table. > >> + The lowest usable items are at pos 0 and 1, the highest > >> + usable items are at pos b - 2 and b - 1. */ > >> + if (a > b || end < items[1].pc || end > items[b - 2].pc) > >> + return; > >> + > >> + /* Look for the first item with pc > end in the range [a,b]. > >> + The previous element has pc = end or there is no match. > >> + We set a = 2, since we need at least two consecutive elements > >> + with pc = end to do anything useful. > >> + We set b = nitems - 1, since we are not interested in the last > >> + element which should be an end of sequence marker with line = 0 > >> + and is_stmt = 1. */ > >> + while (a < b) > >> + { > >> + int c = (a + b) / 2; > >> + > >> + if (end < items[c].pc) > >> + b = c; > >> + else > >> + a = c + 1; > >> + } > >> + > >> + a--; > >> + if (items[a].pc != end || items[a].is_stmt) > >> + return; > >> + > >> + /* When there is a sequence of line entries at the same address > >> + where an inline range ends, and the last item has is_stmt = 0, > >> + we force all previous items to have is_stmt = 0 as well. > >> + Setting breakpoints at those addresses is currently not > >> + supported, since it is unclear if the previous addresses are > >> + part of the subroutine or the calling program. */ > >> + while (a-- > 0) > > > > I know this is a personal preference, but I really dislike having > > these inc/dec adjustments within expressions like this. I feel it's > > too easy to overlook, and I always end up having to think twice just > > to make sure I've parsed the intention correctly. I'd like to make a > > plea to have the adjustment moved into the body of the loop please. > > > > No problem, I can do that better, the first iteration does > not need to check for a > 0, so I will make that a > do { a--; .... } while (a > 0), so that will be even more > efficient this way. > > >> + { > >> + /* We stop at the first line entry with a different address, > >> + or when we see an end of sequence marker. */ > > > > I think there's a whitespace error at the start of this line. > > Yes, indeed. > > > > >> + if (items[a].pc != end || items[a].line == 0) > >> + break; > >> + > >> + items[a].is_stmt = 0; > >> + } > >> +} > >> + > >> + > >> /* Subroutine of end_symtab to simplify it. Look for a subfile that > >> matches the main source file's basename. If there is only one, and > >> if the main source file doesn't have any symbol or line number > >> @@ -965,6 +1045,10 @@ struct compunit_symtab * > >> subfile->line_vector->item > >> + subfile->line_vector->nitems, > >> lte_is_less_than); > >> + > >> + for (int i = 0; i < m_inline_end_vector_nitems; i++) > >> + patch_inline_end_pos (subfile->line_vector, > >> + m_inline_end_vector[i]); > >> } > >> > >> /* Allocate a symbol table if necessary. */ > >> diff --git a/gdb/buildsym.h b/gdb/buildsym.h > >> index c768a4c..2845789 100644 > >> --- a/gdb/buildsym.h > >> +++ b/gdb/buildsym.h > >> @@ -190,6 +190,8 @@ struct buildsym_compunit > >> void record_line (struct subfile *subfile, int line, CORE_ADDR pc, > >> bool is_stmt); > >> > >> + void record_inline_range_end (CORE_ADDR end); > >> + > >> struct compunit_symtab *get_compunit_symtab () > >> { > >> return m_compunit_symtab; > >> @@ -397,6 +399,15 @@ struct buildsym_compunit > >> > >> /* Pending symbols that are local to the lexical context. */ > >> struct pending *m_local_symbols = nullptr; > >> + > >> + /* Pending inline end range addresses. */ > >> + CORE_ADDR * m_inline_end_vector = nullptr; > >> + > >> + /* Number of allocated inline end range addresses. */ > >> + int m_inline_end_vector_length = 0; > >> + > >> + /* Number of pending inline end range addresses. */ > >> + int m_inline_end_vector_nitems = 0; > >> }; > > > > I think we should probably just use a std::vector for > > m_inline_end_vector - unless I'm missing a good reason. I think this > > would simplify some of the code in buildsym.c. > > > > I am worried that the vector is not as efficient as it is necessary here. > I know for instance that a straight forward > > m_inline_end_vector.push_back(pc); > > has often an O(n^2) complexity alone for this adding new elements, > (and it can throw, which makes error handling a mess). push_back is not O(n^2). See https://en.cppreference.com/w/cpp/container/vector/push_back: "Complexity Amortized constant" That's because it doubles the capacity whenever it has to resize. Christian > But the performance of this table need to be O(n * log(n)) > since n is often around 1.000.000 (when I debug large > apps like gcc). > > A previous version of this patch used O(n^2) and was exactly doubling > the execution time for loading of the debug info (for debugging gcc's cc1). > Although that appears to be already done incrementally. > > > Bernd.