Commit the vtable verification feature. This feature is designed to

detect, at run time, if/when the vtable pointer in a C++ object has
been corrupted, before allowing virtual calls through that pointer. 
If pointer corruption is detected, execution of the program is halted.

libstdc++-v3 ChangeLog:
2013-08-06  Caroline Tice  <cmtice@google.com>

        * fragment.am: Add XTEMPLATE_FLAGS.
        * configure.ac: Add definitions for --enable-vtable-verify.
        * acinclude.m4:  Add --enable-vtable-verify and
        --disable-vtable-verify; define --enable-vtable-verify; define
        VTV_CXXFLAGS, VTV_PCH_CXXFLAGS and VTV_CXXLINKFLAGS.
        * config/abi/pre/gnu.ver: Export symbols for vtable verification.
        * libsupc++/Makefile.am: Define vtv_sources and add it to
        libsupc___la_SOURCES and libsupc__convenience_la_SOURCES.
        * libsupc++/vtv_stubs.cc: New file.
        * include/Makefile.am: Add VTV_PCH_CXXFLAGS to PCHFLAGS.
        * src/Makefile.am: Add VTV_CXXFLAGS to AM_CXXFLAGS; add
        VTV_CXXLINKFLAGS to CXXLINK.
        * src/c++98/Makefile.am: Comment out XTEMPLATE_FLAGS; add VTV_CXXFLAGS
        to AM_CXXFLAGS; add VTV_CXXXLINKFLAGS to CXXLINK.
        * src/C++11/Makefile.am: Ditto.
        * doc/xml/manual/configure.xml: Add entry for --enable-vtable-verify.
        * scripts/testsuite_flags.in: Add cxxvtvflags to Usage; cause
        cxxvtvflags to use VTV_CXXFLAGS and VTV_CXXLINKFLAGS.
        * testsuite/lib/libstdc++.exp: Add cxxvtvflags; add code to locate
        libvtv if --enable-vtable-verify was used; set cxxvtvflags; add
        cxxvtvflags to cxx_final.
        * testsuite/18_support/bad_exception/23591_thread-1.c: Add
        -fvtable-verify=none to compiler flags.
        * testsuite/17_intro/freestanding.cc: Add -fvtable-verify=none
        to compiler flags.
        * configure: Regenerated.
        * Makefile.in: Regenerated.
        * python/Makefile.in: Regenerated.
        * include/Makefile.in: Regenerated.
        * libsupc++/Makefile.in: Regenerated.
        * config.h.in: Regenerated.
        * po/Makefile.in: Regenerated.
        * src/Makefile.in: Regenerated.
        * src/c++98/Makefile.in: Regenerated.
        * src/c++11/Makefile.in: Regenerated.
        * doc/Makefile.in: Regenerated.
        * testsuite/Makefile.in: Regenerated.

top level ChangeLog:
2013-08-06  Caroline Tice  <cmtice@google.com>

        * configure.ac: Add target-libvtv to target_libraries; disable libvtv
        on non-linux systems; add target-libvtv to noconfigdirs; add
        libsupc++/.libs to C++ library search paths.
        * configure: Regenerated.
        * Makefile.def: Add libvtv to target_modules; make libvtv depend on
        libstdc++ and libgcc.
        * Makefile.in: Regenerated.

include/ChangeLog:
2013-08-06  Caroline Tice  <cmtice@google.com>

        * vtv-change-permission.h: New file.

contrib/ChangeLog:
2013-08-06  Caroline Tice4  <cmtice@google.com>

        * gcc_update: Add libvtv files.

libgcc/ChangeLog:
2013-08-06  Caroline Tice  <cmtice@google.com>

        config.host (extra_parts): Add vtv_start.o, vtv_end.o
        vtv_start_preinit.o and vtv_end_preinit.o.
        configure.ac: Add code to check/set enable_vtable_verify.
        Makefile.in: Add rules to build vtv_*.o, if enable_vtable_verify is
        true.
        vtv_start_preinit.c: New file.
        vtv_end_preinit.c: New file.
        vtv_start.c: New file.
        vtv_end.c: New file.
        configure: Regenerated.

gcc/ChangeLog:
2013-08-06  Caroline Tice  <cmtice@google.com>

        * gcc.c (VTABLE_VERIFICATION_SPEC): New definition.
        (LINK_COMMAND_SPEC): Add VTABLE_VERIFICATION_SPEC.
        * tree-pass.h: Add pass_vtable_verify.
        * varasm.c (assemble_variable): Add code to properly set the comdat
        section and name for the .vtable_map_vars section.
        (assemble_vtyv_preinit_initializer): New function.
        (default_sectin_type_flags):  Make sure .vtable_map_vars section has
        LINK_ONCE flag.
        * output.h: Add function decl for assemble_vtv_preinit_initializer.
        * vtable-verify.c: New file.
        * vtable-verify.h: New file.
        * flag-types.h (enum vtv_priority): Defintions for flag_vtable_verify
        initialiation levels.
        * timevar.def (TV_VTABLE_VERIFICATION): New definition.
        * passes.def: Insert pass_vtable_verify.
        * aclocal.m4: Reorder includes.
        * doc/invoke.texi: Add documentation for the flags -fvtable-verify=,
	-fvtv-debug and -fvtv-counts.
        * config/gnu-user.h (GNU_USER_TARGET_STARTFILE_SPEC): Add vtv_start*.o,
as appropriate, if -fvtable-verify=... is used.
        (GNU_USER_TARGET_ENDFILE_SPEC): Add vtv_end*.o as appropriate, if
        -fvtable-verify=... is used.
        * Makefile.in (OBJS):  Add vtable-verify.o to list.
        (vtable-verify.o): Add new build rule.
        (GTFILES): Add vtable-verify.c to list.
        * common.opt (fvtable-verify=): New flag.
        (vtv_priority): Values for fvtable-verify= flag.
        (fvtv-counts): New flag.
(fvtv-debug): New flag.
        * tree.h (save_vtable_map_decl): New extern function decl.


gcc/cp/ChangeLog:
2013-08-06  Caroline Tice  <cmtice@google.com>

        * Make-lang.in (*CXX_AND_OBJCXX_OBJS):  Add vtable-class-hierarchy.o to
        list.
        (vtable-class-hierarchy.o): Add build rule.
        * cp-tree.h (vtv_start_verification_constructor_init_function): New
        extern function decl.
        (vtv_finish_verification_constructor_init_function): New extern
        function decl.
        (build_vtbl_address): New extern function decl.
        (get_mangled_vtable_map_var_name): New extern function decl.
        (vtv_compute_class_hierarchy_transitive_closure): New extern function
        decl.
        (vtv_generate_init_routine): New extern function decl.
        (vtv_save_class_info): New extern function decl.
        (vtv_recover_class_info): New extern function decl.
        (vtv_build_vtable_verify_fndecl): New extern function decl.
        * class.c (finish_struct_1): Add call to vtv_save_class_info if
        flag_vtable_verify is true.
        * config-lang.in: Add vtable-class-hierarchy.c to gtfiles list.
        * vtable-class-hierarchy.c: New file.
        * mangle.c (get_mangled_vtable_map_var_name):  New function.
        * decl2.c (start_objects): Update function comment.
        (cp_write_global_declarations): Call vtv_recover_class_info,
        vtv_compute_class_hierarchy_transitive_closure and
        vtv_build_vtable_verify_fndecl, before calling
        finalize_compilation_unit, and call vtv_generate_init_rount after, IFF
        flag_vtable_verify is true.
        (vtv_start_verification_constructor_init_function): New function.
        (vtv_finish_verification_constructor_init_function): New function.
        * init.c (build_vtbl_address): Remove static qualifier from function.

libvtv/ChangeLog:
2013-08-06  Caroline Tice  <cmtice@google.com>

        Initial check-in of new vtable verification feature.
        * configure.ac : New file.
        * acinclude.m4 : New file.
        * Makefile.am : New file.
        * aclocal.m4 : New file.
        * configure.tgt : New file.
        * configure: New file (generated).
        * Makefile.in: New file (generated).
        * vtv_set.h : New file.
        * vtv_utils.cc : New file.
        * vtv_utils.h : New file.
        * vtv_malloc.cc : New file.
        * vtv_rts.cc : New file.
        * vtv_malloc.h : New file.
        * vtv_rts.h : New file.
        * vtv_fail.cc : New file.
        * vtv_fail.h : New file.
        * vtv_map.h : New file.
        * scripts/run-testsuite.sh : New file.
        * scripts/sum-vtv-counts.c : New file.
        * testsuite/parts-test-main.h : New file.
        * testusite/dataentry.cc : New file.
        * testsuite/temp_deriv.cc : New file.
        * testsuite/register_pair.cc : New file.
        * testsuite/virtual_inheritance.cc : New file.
        * testsuite/field-test.cc : New file.
        * testsuite/nested_vcall_test.cc : New file.
        * testsuite/template-list-iostream.cc : New file.
        * testsuite/register_pair_inserts.cc : New file.
        * testsuite/register_pair_inserts_mt.cc : New file.
        * testsuite/event.list : New file.
        * testsuite/parts-test-extra-parts-views.cc : New file.
        * testsuite/parts-test-extra-parts-views.h : New file.
        * testsuite/environment-fail-32.s : New file.
        * testsuite/parts-test-extra-parts.h : New file.
        * testsuite/temp_deriv2.cc : New file.
        * testsuite/dlopen_mt.cc : New file.
        * testsuite/event.h : New file.
        * testsuite/template-list.cc : New file.
        * testsuite/replace-fail.cc : New file.
        * testsuite/Makefile.am : New file.
        * testsuite/Makefile.in: New file (generated).
        * testsuite/mempool_negative.c : New file.
        * testsuite/parts-test-main.cc : New file.
        * testsuite/event-private.cc : New file.
        * testsuite/thunk.cc : New file.
        * testsuite/event-defintiions.cc : New file.
        * testsuite/event-private.h : New file.
        * testsuite/parts-test.list : New file.
        * testusite/register_pair_mt.cc : New file.
        * testsuite/povray-derived.cc : New file.
        * testsuite/event-main.cc : New file.
        * testsuite/environment.cc : New file.
        * testsuite/template-list2.cc : New file.
        * testsuite/thunk_vtable_map_attack.cc : New file.
        * testsuite/parts-test-extra-parts.cc : New file.
        * testsuite/environment-fail-64.s : New file.
        * testsuite/dlopen.cc : New file.
        * testsuite/so.cc : New file.
        * testsuite/temp_deriv3.cc : New file.
        * testsuite/const_vtable.cc : New file.
        * testsuite/mempool_positive.c : New file.
        * testsuite/dup_name.cc : New file.




git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@201555 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 653 insertions, 0 deletions

diff --git a/libvtv/vtv_set.h b/libvtv/vtv_set.h
new file mode 100644
index 00000000000..6d0e3c97f9b
--- /dev/null
+++ b/libvtv/vtv_set.h
@@ -0,0 +1,653 @@
+/* Copyright (C) 2012-2013
+   Free Software Foundation
+
+   This file is part of GCC.
+
+   GCC 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, or (at your option)
+   any later version.
+
+   GCC 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.
+
+   Under Section 7 of GPL version 3, you are granted additional
+   permissions described in the GCC Runtime Library Exception, version
+   3.1, as published by the Free Software Foundation.
+
+   You should have received a copy of the GNU General Public License
+   and a copy of the GCC Runtime Library Exception along with this
+   program; see the files COPYING3 and COPYING.RUNTIME respectively.
+   If not, see <http://www.gnu.org/licenses/>.  */
+
+#ifndef _VTV_SET_H
+#define _VTV_SET_H 1
+
+/* Code in this file manages a collection of insert-only sets.  We
+   have only tested the case where Key is uintptr_t, though it
+   theoretically should work for some other cases.  All odd keys are
+   reserved, and must not be inserted into any of the sets.  This code
+   is intended primarily for sets of pointers, and the code is
+   optimized for small sets (including size 0 and 1), but regardless
+   of the set size, insert() and contains() have close to O(1) speed
+   in practice.
+
+   TODO(gpike): fix this comment.
+
+   Recommended multithreaded use of a set:
+
+   For speed, we want to use a lock-free test for set membership.  The
+   code handles simultaneous reads and inserts, as long as at most one
+   insertion is in progress at a time.  After an insert, other threads
+   may not immediately "see" the inserted key if they perform a
+   lock-free read, so we recommend retrying, as explained below.
+
+   Also, to make data corruption less likely, we recommend using a
+   "normal" RW page as well as one or pages that are typically RO
+   but that can be switched to RW and back as needed.  The latter
+   pages should contain sets.  The former should contain a lock, L,
+   and an int or similar, num_writers.  Then, to insert, something
+   like this would be safe:
+    o Acquire L.
+    o Increment num_writers; if that made it 1, change pages to RW.
+    o Release L.
+    o while (there are insertions to do in some set, S) {
+        acquire L;
+        do some insertions in S;
+        release L;
+      }
+    o Acquire L.
+    o Decrement num_writers; if that made it 0, change pages to RO.
+    o Release L.
+
+   And to check if the set contains some key, one could use
+     set.contains(key) ||
+       ({ Acquire L; bool b = set.contains(key); Release L; b; })
+
+   In this scheme, the number of threads with reads in progress isn't
+   tracked, so old sets can never be deleted.  In addition, on some
+   architectures the intentionally racy reads might cause contains()
+   to return true when it should have returned false.  This should be
+   no problem on x86, and most other machines, where reading or
+   writing an aligned uintptr_t is atomic.  E.g., on those machines,
+   if *p is 0 and one thread does *p = x while another reads *p, the
+   read will see either 0 or x.
+
+   To make the above easier, the insert_only_hash_sets class provides
+   an interface to manipulate any number of hash sets.  One shouldn't
+   create objects of that class, as it has no member data and its
+   methods are static.
+
+   So the recommended model is to have a single lock, a single
+   num_writers variable, and some number of sets.  If lock contention
+   becomes a problem then the sets can be divided into k groups, each
+   of which has a lock and a num_writers variable; or each set can be
+   represented as a set of values that equal 0 mod m, a set of values
+   that equal 1 mod m, ..., plus a set of values that equal m-1 mod m.
+
+   However, we expect most or all uses of this code to call contains()
+   much more frequently than anything else, so lock contention is
+   likely to be low.  */
+
+#include <algorithm>
+
+#ifndef HASHTABLE_STATS
+#define HASHTABLE_STATS 0
+#endif
+
+#ifndef HASHTABLE_STATS_ATOMIC
+#define HASHTABLE_STATS_ATOMIC 0
+#endif
+
+#if HASHTABLE_STATS
+#if HASHTABLE_STATS_ATOMIC
+/* Stat counters, with atomics. */
+#include <bits/atomic_word.h>
+
+typedef _Atomic_word _AtomicStatCounter;
+
+void
+inc_by (_AtomicStatCounter &stat, int amount)
+{ 
+  __atomic_add_fetch (&stat, amount,  __ATOMIC_ACQ_REL);
+}
+
+#else
+
+/* Stat counters, but without atomics. */
+typedef int _AtomicStatCounter;
+
+void
+inc_by (_AtomicStatCounter& stat, int amount)
+{ 
+  stat += amount;
+}
+
+#endif
+
+
+/* Number of calls to contains(), insert(), etc. */
+extern _AtomicStatCounter stat_insert;
+extern _AtomicStatCounter stat_contains;
+extern _AtomicStatCounter stat_resize;
+extern _AtomicStatCounter stat_create;
+
+/* Sum of set size over all calls to contains().  */
+extern _AtomicStatCounter stat_contains_sizes;
+
+/* contains() calls in a set whose capacity is more than 1. */
+extern _AtomicStatCounter stat_contains_in_non_trivial_set;
+
+/* Probes in a set whose capacity is more than 1.  Ideally, this will
+   be pretty close to stat_contains_in_non_trivial_set.  That will
+   happen if our hash function is good and/or important keys were
+   inserted before unimportant keys.  */
+extern _AtomicStatCounter stat_probes_in_non_trivial_set;
+
+/* number of calls to contains() with size=0, 1, etc. */
+extern _AtomicStatCounter stat_contains_size0;
+extern _AtomicStatCounter stat_contains_size1;
+extern _AtomicStatCounter stat_contains_size2;
+extern _AtomicStatCounter stat_contains_size3;
+extern _AtomicStatCounter stat_contains_size4;
+extern _AtomicStatCounter stat_contains_size5;
+extern _AtomicStatCounter stat_contains_size6;
+extern _AtomicStatCounter stat_contains_size7;
+extern _AtomicStatCounter stat_contains_size8;
+extern _AtomicStatCounter stat_contains_size9;
+extern _AtomicStatCounter stat_contains_size10;
+extern _AtomicStatCounter stat_contains_size11;
+extern _AtomicStatCounter stat_contains_size12;
+extern _AtomicStatCounter stat_contains_size13_or_more;
+extern _AtomicStatCounter stat_grow_from_size0_to_1;
+extern _AtomicStatCounter stat_grow_from_size1_to_2;
+extern _AtomicStatCounter stat_double_the_number_of_buckets;
+extern _AtomicStatCounter stat_insert_key_that_was_already_present;
+
+/* Hash collisions detected during insert_no_resize().  Only counts
+   hasher(k) == hasher(k'); hasher(k) % tablesize == hasher(k') %
+   tablesize is not sufficient.  Will count collisions that are
+   detected during table resizes etc., so the same two keys may add to
+   this stat multiple times.  */
+extern _AtomicStatCounter stat_insert_found_hash_collision;
+
+#include <string>
+
+struct insert_only_hash_sets_logger
+{
+  static char *
+  log (char c, char *buf)
+  {
+    *buf++ = c;
+    return buf;
+  }
+
+  static char *
+  log (const char *s, char *buf)
+  { return strcpy (buf, s) + strlen (s); }
+
+  static char *
+  log (_AtomicStatCounter i, char *buf)
+  {
+    if (i < 10)
+      return log ((char) ('0' + i), buf);
+    else
+      return log ((char) ('0' + i % 10), log (i / 10, buf));
+  }
+
+  static char *
+  log (const char *label, _AtomicStatCounter i, char *buf)
+  {
+    buf = log (label, buf);
+    buf = log (": ", buf);
+    buf = log (i, buf);
+    return log ('\n', buf);
+  }
+};
+
+// Write stats to the given buffer, which should be at least 4000 bytes.
+static inline void
+insert_only_hash_tables_stats (char *buf)
+{
+  buf = insert_only_hash_sets_logger::log ("insert", stat_insert, buf);
+  buf = insert_only_hash_sets_logger::log ("contains", stat_contains, buf);
+  buf = insert_only_hash_sets_logger::log ("resize", stat_resize, buf);
+  buf = insert_only_hash_sets_logger::log ("create", stat_create, buf);
+  buf = insert_only_hash_sets_logger::log ("insert_key_that_was_already_"
+				      "present",
+				      stat_insert_key_that_was_already_present,
+				      buf);
+  buf = insert_only_hash_sets_logger::log ("contains_sizes",
+					   stat_contains_sizes, buf);
+  buf = insert_only_hash_sets_logger::log ("contains_in_non_trivial_set",
+					   stat_contains_in_non_trivial_set,
+					   buf);
+  buf = insert_only_hash_sets_logger::log ("probes_in_non_trivial_set",
+					   stat_probes_in_non_trivial_set,
+					   buf);
+  buf = insert_only_hash_sets_logger::log ("contains_size0",
+					   stat_contains_size0, buf);
+  buf = insert_only_hash_sets_logger::log ("contains_size1",
+					   stat_contains_size1, buf);
+  buf = insert_only_hash_sets_logger::log ("contains_size2",
+					   stat_contains_size2, buf);
+  buf = insert_only_hash_sets_logger::log ("contains_size3",
+					   stat_contains_size3, buf);
+  buf = insert_only_hash_sets_logger::log ("contains_size4",
+					   stat_contains_size4, buf);
+  buf = insert_only_hash_sets_logger::log ("contains_size5",
+					   stat_contains_size5, buf);
+  buf = insert_only_hash_sets_logger::log ("contains_size6",
+					   stat_contains_size6, buf);
+  buf = insert_only_hash_sets_logger::log ("contains_size7",
+					   stat_contains_size7, buf);
+  buf = insert_only_hash_sets_logger::log ("contains_size8",
+					   stat_contains_size8, buf);
+  buf = insert_only_hash_sets_logger::log ("contains_size9",
+					   stat_contains_size9, buf);
+  buf = insert_only_hash_sets_logger::log ("contains_size10",
+					   stat_contains_size10, buf);
+  buf = insert_only_hash_sets_logger::log ("contains_size11",
+					   stat_contains_size11, buf);
+  buf = insert_only_hash_sets_logger::log ("contains_size12",
+					   stat_contains_size12, buf);
+  buf = insert_only_hash_sets_logger::log ("contains_size13_or_more",
+					   stat_contains_size13_or_more, buf);
+  buf = insert_only_hash_sets_logger::log ("grow_from_size0_to_1",
+					   stat_grow_from_size0_to_1, buf);
+  buf = insert_only_hash_sets_logger::log ("grow_from_size1_to_2",
+					   stat_grow_from_size1_to_2, buf);
+  buf = insert_only_hash_sets_logger::log ("insert_found_hash_collision",
+					   stat_insert_found_hash_collision,
+					   buf);
+  buf = insert_only_hash_sets_logger::log ("double_the_number_of_buckets",
+					   stat_double_the_number_of_buckets,
+					   buf);
+  *buf = '\0';
+}
+
+#else
+
+/* No stats. */
+#define inc_by(statname, amount) do { } while (false && (amount))
+
+#endif
+
+#define inc(statname) inc_by (statname, 1)
+
+template <typename Key, class HashFcn, class Alloc>
+class insert_only_hash_sets
+{
+ public:
+  typedef Key key_type;
+  typedef size_t size_type;
+  typedef Alloc alloc_type;
+  enum { illegal_key = 1 };
+  enum { min_capacity = 4 };
+#if HASHTABLE_STATS
+  enum { stats = true };
+#else
+  enum { stats = false };
+#endif
+
+  /* Do not directly use insert_only_hash_set.  Instead, use the
+     static methods below to create and manipulate objects of the
+     following class.
+  
+     Implementation details: each set is represented by a pointer
+     plus, perhaps, out-of-line data, which would be an object of type
+     insert_only_hash_set.  For a pointer, s, the interpretation is: s
+     == NULL means empty set, lsb(s) == 1 means a set with one
+     element, which is (uintptr_t)s - 1, and otherwise s is a pointer
+     of type insert_only_hash_set*.  So, to increase the size of a set
+     we have to change s and/or *s.  To check if a set contains some
+     key we have to examine s and possibly *s.  */
+  class insert_only_hash_set
+  {
+   public:
+    /* Insert a key.  The key must not be a reserved key.  */
+    static inline insert_only_hash_set *insert (key_type key,
+						insert_only_hash_set *s);
+    
+
+    /* Create an empty set.  */
+    static inline insert_only_hash_set *create (size_type capacity);
+
+    /* Return whether the given key is present.  If key is illegal_key
+       then either true or false may be returned, but for all other
+       reserved keys false will be returned.  */
+    static bool
+    contains (key_type key, const insert_only_hash_set *s)
+    {
+      if (stats)
+	{
+	  inc (stat_contains);
+	  switch (size (s))
+	    {
+	      case 0: inc (stat_contains_size0); break;
+	      case 1: inc (stat_contains_size1); break;
+	      case 2: inc (stat_contains_size2); break;
+	      case 3: inc (stat_contains_size3); break;
+	      case 4: inc (stat_contains_size4); break;
+	      case 5: inc (stat_contains_size5); break;
+	      case 6: inc (stat_contains_size6); break;
+	      case 7: inc (stat_contains_size7); break;
+	      case 8: inc (stat_contains_size8); break;
+	      case 9: inc (stat_contains_size9); break;
+	      case 10: inc (stat_contains_size10); break;
+	      case 11: inc (stat_contains_size11); break;
+	      case 12: inc (stat_contains_size12); break;
+	      default: inc (stat_contains_size13_or_more); break;
+	    }
+          inc_by (stat_contains_sizes, size (s));
+	}
+
+      return (singleton (s) ?
+              singleton_key (key) == s :
+              ((s != NULL) && s->contains (key)));
+    }
+
+    /* Return a set's size.  */
+    static size_type
+    size (const insert_only_hash_set *s)
+    { return (s == NULL) ? 0 : (singleton (s) ? 1 : s->num_entries); }
+
+    static inline insert_only_hash_set *resize (size_type target_num_buckets,
+						insert_only_hash_set *s);
+    
+
+   private:
+    /* Return whether a set has size 1. */
+    static bool
+    singleton (const insert_only_hash_set *s)
+    { return (uintptr_t) s & 1; }
+
+    /* Return the representation of a singleton set containing the
+       given key.  */
+    static insert_only_hash_set *
+    singleton_key (key_type key)
+    { return (insert_only_hash_set *) ((uintptr_t) key + 1); }
+
+    /* Given a singleton set, what key does it contain?  */
+    static key_type
+    extract_singleton_key (const insert_only_hash_set *s)
+    {
+      VTV_DEBUG_ASSERT (singleton (s));
+      return (key_type) ((uintptr_t) s - 1);
+    }
+
+    volatile key_type &
+    key_at_index (size_type index)
+    { return buckets[index]; }
+
+    key_type
+    key_at_index (size_type index) const
+    { return buckets[index]; }
+
+    size_type
+    next_index (size_type index, size_type indices_examined) const
+    { return (index + indices_examined) & (num_buckets - 1); }
+
+    inline void insert_no_resize (key_type key);
+    
+    inline bool contains (key_type key) const;
+    
+    inline insert_only_hash_set *resize_if_necessary (void);
+    
+    size_type num_buckets;  /* Must be a power of 2 not less than
+			       min_capacity.  */
+    volatile size_type num_entries;
+    volatile key_type buckets[0];  /* Actual array size is num_buckets.  */
+  };
+
+  /* Create an empty set with the given capacity.  Requires that n be
+     0 or a power of 2.  If 1 < n < min_capacity then treat n as
+     min_capacity.  Sets *handle.  Returns true unless the allocator
+     fails.  Subsequent operations on this set should use the same
+     handle. */
+
+  static inline bool create (size_type n, insert_only_hash_set **handle);
+
+  /* Force the capacity of a set to be n, unless it was more than n
+     already.  Requires that n be 0 or a power of 2.  Sets *handle
+     unless the current capacity is n or more.  Returns true unless
+     the allocator fails.  */
+
+  static inline bool resize (size_type n, insert_only_hash_set **handle);
+
+  /* Insert a key.  *handle is unmodified unless (1) a resize occurs,
+     or (2) the set was initially empty. Returns true unless the
+     allocator fails during a resize.  If the allocator fails during a
+     resize then the set is reset to be the empty set.  The key must
+     not be a reserved key.  */
+
+  static inline bool insert (key_type key, insert_only_hash_set **handle);
+
+  /* Check for the presence of a key.  If key is illegal_key then
+     either true or false may be returned, but for all other reserved
+     keys false will be returned.  */
+
+  static inline bool
+  contains (key_type key, /* const */ insert_only_hash_set **handle)
+  { return insert_only_hash_set::contains (key, *handle); }
+
+  /* Return the size of the given set.  */
+  static size_type
+  size (const insert_only_hash_set **handle)
+  { return insert_only_hash_set::size (*handle); }
+
+  static bool
+  is_reserved_key (key_type key)
+  { return ((uintptr_t) key % 2) == 1; }
+};
+
+template <typename Key, class HashFcn, class Alloc>
+typename insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set *
+insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set::resize
+                                         (size_type n, insert_only_hash_set *s)
+{
+  if (s == NULL)
+    return create (n);
+
+  size_type capacity = singleton (s) ? 1 : s->num_buckets;
+
+  if (n <= capacity)
+    return s;
+
+  insert_only_hash_set *result =
+                                create (std::max<size_type> (n, min_capacity));
+  if (result != NULL)
+    {
+      if (singleton (s))
+        {
+          result->insert_no_resize (extract_singleton_key (s));
+        }
+      else
+        {
+          for (size_type i = 0; i < s->num_buckets; i++)
+            if (s->buckets[i] != (key_type) illegal_key)
+              result->insert_no_resize (s->buckets[i]);
+        }
+      VTV_DEBUG_ASSERT (size (result) == size (s));
+    }
+  return result;
+}
+
+template <typename Key, class HashFcn, class Alloc>
+typename insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set *
+insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set::insert 
+                                        (key_type key, insert_only_hash_set *s)
+{
+  VTV_DEBUG_ASSERT (!is_reserved_key (key));
+
+  inc_by (stat_grow_from_size0_to_1, s == NULL);
+
+  if (s == NULL)
+    return singleton_key (key);
+
+  if (singleton (s))
+    {
+      const key_type old_key = extract_singleton_key (s);
+      if (old_key == key)
+	return s;
+
+      /* Grow from size 1 to size 2.  */
+      inc (stat_grow_from_size1_to_2);
+      s = create (2);
+      if (s == NULL)
+	return NULL;
+
+      s->insert_no_resize (old_key);
+      s->insert_no_resize (key);
+      VTV_DEBUG_ASSERT (size (s) == 2);
+      return s;
+    }
+  s = s->resize_if_necessary();
+  if (s != NULL)
+    s->insert_no_resize (key);
+  return s;
+}
+
+template <typename Key, class HashFcn, class Alloc>
+typename insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set *
+insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set::create
+                                                           (size_type capacity)
+{
+  if (capacity <= 1)
+    return NULL;
+
+  VTV_DEBUG_ASSERT (capacity > 1 && (capacity & (capacity - 1)) == 0);
+  VTV_DEBUG_ASSERT (sizeof (insert_only_hash_set) == 2 * sizeof (size_type));
+  capacity = std::max <size_type> (capacity, min_capacity);
+  const size_t num_bytes = sizeof (insert_only_hash_set) +
+                                                  sizeof (key_type) * capacity;
+  alloc_type alloc;
+  insert_only_hash_set *result = (insert_only_hash_set *) alloc (num_bytes);
+  result->num_buckets = capacity;
+  result->num_entries = 0;
+  for (size_type i = 0; i < capacity; i++)
+    result->buckets[i] = (key_type) illegal_key;
+  return result;
+}
+
+template <typename Key, class HashFcn, class Alloc>
+void
+insert_only_hash_sets<Key, HashFcn,
+                                 Alloc>::insert_only_hash_set::insert_no_resize
+                                                                 (key_type key)
+{
+  HashFcn hasher;
+  const size_type capacity = num_buckets;
+  VTV_DEBUG_ASSERT (capacity >= min_capacity);
+  VTV_DEBUG_ASSERT (!is_reserved_key (key));
+  size_type index = hasher (key) & (capacity - 1);
+  key_type k = key_at_index (index);
+  size_type indices_examined = 0;
+  while (k != key)
+    {
+      ++indices_examined;
+      if (k == (key_type) illegal_key)
+        {
+          key_at_index (index) = key;
+          ++num_entries;
+          return;
+        }
+      else
+	{
+	  inc_by (stat_insert_found_hash_collision,
+		  hasher (k) == hasher (key));
+	}
+      VTV_DEBUG_ASSERT (indices_examined < capacity);
+      index = next_index (index, indices_examined);
+      k = key_at_index (index);
+    }
+}
+
+template<typename Key, class HashFcn, class Alloc>
+bool
+insert_only_hash_sets<Key, HashFcn, Alloc>::insert_only_hash_set::contains
+                                                           (key_type key) const
+{
+  inc (stat_contains_in_non_trivial_set);
+  HashFcn hasher;
+  const size_type capacity = num_buckets;
+  size_type index = hasher (key) & (capacity - 1);
+  key_type k = key_at_index (index);
+  size_type indices_examined = 0;
+  inc (stat_probes_in_non_trivial_set);
+  while (k != key)
+    {
+      ++indices_examined;
+      if (/*UNLIKELY*/(k == (key_type) illegal_key
+		       || indices_examined == capacity))
+	return false;
+
+      index = next_index (index, indices_examined);
+      k = key_at_index (index);
+      inc (stat_probes_in_non_trivial_set);
+    }
+  return true;
+}
+
+template <typename Key, class HashFcn, class Alloc>
+typename insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set *
+   insert_only_hash_sets<Key, HashFcn,
+                       Alloc>::insert_only_hash_set::resize_if_necessary (void)
+{
+  VTV_DEBUG_ASSERT (num_buckets >= min_capacity);
+  size_type unused = num_buckets - num_entries;
+  if (unused < (num_buckets >> 2))
+    {
+      inc (stat_double_the_number_of_buckets);
+      size_type new_num_buckets = num_buckets * 2;
+      insert_only_hash_set *s = create (new_num_buckets);
+      for (size_type i = 0; i < num_buckets; i++)
+        if (buckets[i] != (key_type) illegal_key)
+          s->insert_no_resize (buckets[i]);
+      VTV_DEBUG_ASSERT (size (this) == size (s));
+      return s;
+    }
+  else
+    return this;
+}
+
+template<typename Key, class HashFcn, class Alloc>
+bool
+insert_only_hash_sets<Key, HashFcn, Alloc>::create (size_type n,
+						 insert_only_hash_set **handle)
+  
+{
+  inc (stat_create);
+  *handle = insert_only_hash_set::create (n);
+  return (n <= 1) || (*handle != NULL);
+}
+
+template<typename Key, class HashFcn, class Alloc>
+bool
+insert_only_hash_sets<Key, HashFcn, Alloc>::resize (size_type n,
+					         insert_only_hash_set **handle)
+{
+  inc (stat_resize);
+  *handle = insert_only_hash_set::resize (n, *handle);
+  return (n <= 1) || (*handle != NULL);
+}
+
+template<typename Key, class HashFcn, class Alloc>
+bool
+insert_only_hash_sets<Key, HashFcn, Alloc>::insert (key_type key,
+                                                 insert_only_hash_set **handle)
+{
+  inc (stat_insert);
+  const size_type old_size = insert_only_hash_set::size (*handle);
+  *handle = insert_only_hash_set::insert (key, *handle);
+  if (*handle != NULL)
+    {
+      const size_type delta = insert_only_hash_set::size (*handle) - old_size;
+      inc_by (stat_insert_key_that_was_already_present, delta == 0);
+    }
+  return *handle != NULL;
+}
+
+#endif /* VTV_SET_H  */