gdb: Don't corrupt completions hash when expanding the hash table

Message ID 20200404153729.1547002-1-andrew.burgess@embecosm.com
State New
Headers show
Series
  • gdb: Don't corrupt completions hash when expanding the hash table
Related show

Commit Message

Andrew Burgess April 4, 2020, 3:37 p.m.
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.
---
 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(-)
 create mode 100644 gdb/testsuite/gdb.base/many-completions.exp

-- 
2.25.1

Comments

Tom Tromey April 6, 2020, 8:27 p.m. | #1
>>>>> "Andrew" == Andrew Burgess <andrew.burgess@embecosm.com> writes:


Andrew> gdb/ChangeLog:

Andrew> 	* completer.c (class completion_tracker::completion_hash_entry)
Andrew> 	<hash_name>: New member function.
Andrew> 	(completion_tracker::discard_completions): New callback to hash a
Andrew> 	completion_hash_entry, pass this to htab_create_alloc.

Andrew> gdb/testsuite/ChangeLog:

Andrew> 	* gdb.base/many-completions.exp: New file.

Thanks.  This looks good.

Tom
Andrew Burgess April 15, 2020, 3:46 p.m. | #2
* Tom Tromey <tom@tromey.com> [2020-04-06 14:27:14 -0600]:

> >>>>> "Andrew" == Andrew Burgess <andrew.burgess@embecosm.com> writes:

> 

> Andrew> gdb/ChangeLog:

> 

> Andrew> 	* completer.c (class completion_tracker::completion_hash_entry)

> Andrew> 	<hash_name>: New member function.

> Andrew> 	(completion_tracker::discard_completions): New callback to hash a

> Andrew> 	completion_hash_entry, pass this to htab_create_alloc.

> 

> Andrew> gdb/testsuite/ChangeLog:

> 

> Andrew> 	* gdb.base/many-completions.exp: New file.

> 

> Thanks.  This looks good.


Sorry for the delay.  This is now pushed.

Thanks,
Andrew

Patch

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 @@  class completion_tracker::completion_hash_entry
     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/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"