[binutils-gdb] gdb: Don't corrupt completions hash when expanding the hash table

[binutils-gdb] gdb: Don't corrupt completions hash when expanding the hash table

[Andrew Burgess]

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=99f1bc6aaa2810fa4600b1cfd13d2d52678e1a66

commit 99f1bc6aaa2810fa4600b1cfd13d2d52678e1a66
Author: Andrew Burgess <andrew.burgess@embecosm.com>
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)
            <hash_name>: 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  <andrew.burgess@embecosm.com>
+
+	* completer.c (class completion_tracker::completion_hash_entry)
+	<hash_name>: 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  <jon.turney@dronecode.org.uk>
 
 	* 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  <andrew.burgess@embecosm.com>
+
+	* gdb.base/many-completions.exp: New file.
+
 2020-04-14  Tom de Vries  <tdevries@suse.de>
 
 	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 <http://www.gnu.org/licenses/>.
+
+# 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"