From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1726) id 99F59384B0C1; Wed, 15 Apr 2020 15:44:18 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 99F59384B0C1 Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Andrew Burgess To: gdb-cvs@sourceware.org Subject: [binutils-gdb] gdb: Don't corrupt completions hash when expanding the hash table X-Act-Checkin: binutils-gdb X-Git-Author: Andrew Burgess X-Git-Refname: refs/heads/master X-Git-Oldrev: a0e9b53238c3033222c53b1654da535c0743ab6e X-Git-Newrev: 99f1bc6aaa2810fa4600b1cfd13d2d52678e1a66 Message-Id: <20200415154418.99F59384B0C1@sourceware.org> Date: Wed, 15 Apr 2020 15:44:18 +0000 (GMT) X-BeenThere: gdb-cvs@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 15 Apr 2020 15:44:18 -0000 https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=99f1bc6aaa2810fa4600b1cfd13d2d52678e1a66 commit 99f1bc6aaa2810fa4600b1cfd13d2d52678e1a66 Author: Andrew Burgess Date: Sat Apr 4 14:54:15 2020 +0100 gdb: Don't corrupt completions hash when expanding the hash table Commit: commit 724fd9ba432a20ef2e3f2c0d6060bff131226816 Date: Mon Jan 27 17:37:20 2020 +0000 gdb: Restructure the completion_tracker class caused the completion hash table to become corrupted if the table ever needed to grow beyond its original size of 200 elements. The hash table stores completion_tracker::completion_hash_entry objects, but hashes them based on their name, which is only one field of the object. When possibly inserting a new element we compute the hash with htab_hash_string of the new elements name, and then lookup matching elements using htab_find_slot_with_hash. If there's not matching element we create a completion_hash_entry object within the hash table. However, when we allocate the hash we pass htab_hash_string to htab_create_alloc as the hash function, and this is not OK. This means that when the hash table needs to grow, existing elements within the hash are re-hashed by passing the completion_hash_entry pointer to htab_hash_string, which obviously does not do what we expect. The solution is to create a new hash function that takes a pointer to a completion_hash_entry, and then calls htab_hash_string on the name of the entry only. This regression was spotted when running the gdb.base/completion.exp test on the aarch64 target. gdb/ChangeLog: * completer.c (class completion_tracker::completion_hash_entry) : New member function. (completion_tracker::discard_completions): New callback to hash a completion_hash_entry, pass this to htab_create_alloc. gdb/testsuite/ChangeLog: * gdb.base/many-completions.exp: New file. Diff: --- gdb/ChangeLog | 7 +++ gdb/completer.c | 18 +++++- gdb/testsuite/ChangeLog | 4 ++ gdb/testsuite/gdb.base/many-completions.exp | 92 +++++++++++++++++++++++++++++ 4 files changed, 120 insertions(+), 1 deletion(-) diff --git a/gdb/ChangeLog b/gdb/ChangeLog index 425c4459922..bb5ddeca70f 100644 --- a/gdb/ChangeLog +++ b/gdb/ChangeLog @@ -1,3 +1,10 @@ +2020-04-15 Andrew Burgess + + * completer.c (class completion_tracker::completion_hash_entry) + : New member function. + (completion_tracker::discard_completions): New callback to hash a + completion_hash_entry, pass this to htab_create_alloc. + 2016-01-20 Jon Turney * windows-nat.c (windows_make_so): Warn rather than stopping with diff --git a/gdb/completer.c b/gdb/completer.c index 67dce30fbe3..0dd91a7195f 100644 --- a/gdb/completer.c +++ b/gdb/completer.c @@ -82,6 +82,12 @@ public: return strcmp (m_name.get (), str) == 0; } + /* Return the hash value based on the name of the entry. */ + hashval_t hash_name () const + { + return htab_hash_string (m_name.get ()); + } + /* A static function that can be passed to the htab hash system to be used as a callback that deletes an item from the hash. */ static void deleter (void *arg) @@ -1602,8 +1608,18 @@ completion_tracker::discard_completions () return entry->is_name_eq (name_str); }; + /* Callback used by the hash table to compute the hash value for an + existing entry. This is needed when expanding the hash table. */ + static auto entry_hash_func + = [] (const void *arg) -> hashval_t + { + const completion_hash_entry *entry + = (const completion_hash_entry *) arg; + return entry->hash_name (); + }; + m_entries_hash = htab_create_alloc (INITIAL_COMPLETION_HTAB_SIZE, - htab_hash_string, entry_eq_func, + entry_hash_func, entry_eq_func, completion_hash_entry::deleter, xcalloc, xfree); } diff --git a/gdb/testsuite/ChangeLog b/gdb/testsuite/ChangeLog index 7259e05d477..e021d3ea7a8 100644 --- a/gdb/testsuite/ChangeLog +++ b/gdb/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2020-04-15 Andrew Burgess + + * gdb.base/many-completions.exp: New file. + 2020-04-14 Tom de Vries PR symtab/25718 diff --git a/gdb/testsuite/gdb.base/many-completions.exp b/gdb/testsuite/gdb.base/many-completions.exp new file mode 100644 index 00000000000..9597963abba --- /dev/null +++ b/gdb/testsuite/gdb.base/many-completions.exp @@ -0,0 +1,92 @@ +# Copyright 2020 Free Software Foundation, Inc. + +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 3 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program. If not, see . + +# Test the case where we have so many completions that we require the +# completions hash table within GDB to grow. Make sure that afte the +# hash table has grown we try to add duplicate entries into the +# hash. This checks that GDB doesn't corrupt the hash table when +# resizing it. +# +# In this case we create a test with more functions than the default +# number of entires in the completion hash table (which is 200), then +# complete on all function names. +# +# GDB will add all the function names from the DWARF, and then from +# the ELF symbol table, this ensures that we should have duplicates +# added after resizing the table. + +# Create a test source file and return the name of the file. COUNT is +# the number of dummy functions to create, this should be more than +# the default number of entries in the completion hash table within +# GDB (see gdb/completer.c). +proc prepare_test_source_file { count } { + global gdb_test_file_name + + set filename [standard_output_file "$gdb_test_file_name.c"] + set outfile [open $filename w] + + puts $outfile " +#define MAKE_FUNC(NUM) \\ + void \\ + func_ ## NUM (void) \\ + { /* Nothing. */ } + +#define CALL_FUNC(NUM) \\ + func_ ## NUM () +" + + for { set i 0 } { $i < $count } { incr i } { + puts $outfile "MAKE_FUNC ([format {%03d} $i])" + } + + puts $outfile "\nint\nmain ()\n{" + for { set i 0 } { $i < $count } { incr i } { + puts $outfile " CALL_FUNC ([format {%03d} $i]);" + } + + puts $outfile " return 0;\n}" + close $outfile + + return $filename +} + +# Build a source file and compile it. +set filename [prepare_test_source_file 250] +standard_testfile $filename +if {[prepare_for_testing "failed to prepare" "$testfile" $srcfile \ + { debug }]} { + return -1 +} + +# Start the test. +if {![runto_main]} { + fail "couldn't run to main" + return +} + +# We don't want to stop gathering completions too early. +gdb_test_no_output "set max-completions unlimited" + +# Collect all possible completions, and check for duplictes. +set completions [capture_command_output "complete break func_" ""] +set duplicates 0 +foreach {-> name} [regexp -all -inline -line {^break (\w+\S*)} $completions] { + incr all_funcs($name) + if { $all_funcs($name) > 1 } { + incr duplicates + verbose -log "Duplicate entry for '$name' found" + } +} +gdb_assert { $duplicates == 0 } "duplicate check"