X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcode%2Ftarget-hash-table.lisp;h=8d652557bc2c92b09a25450b19fd2e810256f5bd;hb=b9a1b17b079d315c1eec194eb4f93f7d058b24cf;hp=20113045045778a5ec06952221bc0b3194c33dae;hpb=e94fe1bcf814af45ca9eeb4721df17c58afa4d76;p=sbcl.git

diff --git a/src/code/target-hash-table.lisp b/src/code/target-hash-table.lisp
index 2011304..8d65255 100644
--- a/src/code/target-hash-table.lisp
+++ b/src/code/target-hash-table.lisp
@@ -14,26 +14,46 @@
 
 ;;;; utilities
 
-;;; Without the locking the next vector can get cyclic causing
-;;; looping in a WITHOUT-GCING form, SHRINK-VECTOR can corrupt memory
-;;; and who knows what else.
-;;;
-;;; WITHOUT-GCING implies WITHOUT-INTERRUPTS.
-(defmacro with-spinlock-and-without-gcing ((spinlock) &body body)
-  #!-sb-thread
-  (declare (ignore spinlock))
-  `(without-gcing
-       (unwind-protect
-            (progn
-              #!+sb-thread
-              (sb!thread::get-spinlock ,spinlock)
-              ,@body)
-         #!+sb-thread
-         (sb!thread::release-spinlock ,spinlock))))
-
 (eval-when (:compile-toplevel :load-toplevel :execute)
   (defconstant max-hash sb!xc:most-positive-fixnum))
 
+;;; Code for detecting concurrent accesses to the same table from
+;;; multiple threads. Only compiled in when the :SB-HASH-TABLE-DEBUG
+;;; feature is enabled. The main reason for the existence of this code
+;;; is to detect thread-unsafe uses of hash-tables in sbcl itself,
+;;; where debugging anythign can be impossible after an important
+;;; internal hash-table has been corrupted. It's plausible that this
+;;; could be useful for some user code too, but the runtime cost is
+;;; really too high to enable it by default.
+(defmacro with-concurrent-access-check (hash-table &body body)
+  (declare (ignorable hash-table))
+  #!-sb-hash-table-debug
+  `(progn ,@body)
+  #!+sb-hash-table-debug
+  (once-only ((hash-table hash-table))
+    `(progn
+       (flet ((body-fun ()
+                ,@body)
+              (error-fun ()
+                ;; Don't signal more errors for this table.
+                (setf (hash-table-concurrent-access-error ,hash-table) nil)
+                (error "Concurrent access to ~A" ,hash-table)))
+         (if (hash-table-concurrent-access-error ,hash-table)
+             (let ((thread (hash-table-accessing-thread ,hash-table)))
+               (unwind-protect
+                    (progn
+                      (when (and thread
+                                 (not (eql thread sb!thread::*current-thread*)))
+                        (error-fun))
+                      (setf (hash-table-accessing-thread ,hash-table)
+                            sb!thread::*current-thread*)
+                      (body-fun))
+                 (unless (eql (hash-table-accessing-thread ,hash-table)
+                              sb!thread::*current-thread*)
+                   (error-fun))
+                 (setf (hash-table-accessing-thread ,hash-table) thread)))
+             (body-fun))))))
+
 (deftype hash ()
   `(integer 0 ,max-hash))
 
@@ -84,17 +104,24 @@
     (t
      (eq-hash key))))
 
-(defun almost-primify (num)
+(defun ceil-power-of-two (num)
   (declare (type index num))
-  #!+sb-doc
-  "Return an almost prime number greater than or equal to NUM."
-  (if (= (rem num 2) 0)
-      (setq num (+ 1 num)))
-  (if (= (rem num 3) 0)
-      (setq num (+ 2 num)))
-  (if (= (rem num 7) 0)
-      (setq num (+ 4 num)))
-  num)
+  (ash 1 (integer-length num)))
+
+(declaim (inline index-for-hashing))
+(defun index-for-hashing (index length)
+  (declare (type index index length))
+  ;; We're using power of two tables which obviously are very
+  ;; sensitive to the exact values of the low bits in the hash
+  ;; value. Do a little shuffling of the value to mix the high bits in
+  ;; there too.
+  (logand (1- length)
+          (+ (logxor #b11100101010001011010100111
+                     index)
+             (ash index -6)
+             (ash index -15)
+             (ash index -23))))
+
 
 ;;;; user-defined hash table tests
 
@@ -119,7 +146,8 @@
                         (size +min-hash-table-size+)
                         (rehash-size 1.5)
                         (rehash-threshold 1)
-                        (weakness nil))
+                        (weakness nil)
+                        (synchronized))
   #!+sb-doc
   "Create and return a new hash table. The keywords are as follows:
      :TEST -- Indicates what kind of test to use.
@@ -133,7 +161,7 @@
        forcing a rehash. Can be any positive number <=1, with density
        approaching zero as the threshold approaches 0. Density 1 means an
        average of one entry per bucket.
-     :WEAKNESS -- IF NIL (the default) it is a normal non-weak hash table.
+     :WEAKNESS -- If NIL (the default) it is a normal non-weak hash table.
        If one of :KEY, :VALUE, :KEY-AND-VALUE, :KEY-OR-VALUE it is a weak
        hash table.
        Depending on the type of weakness the lack of references to the
@@ -144,7 +172,15 @@
        is :KEY-AND-VALUE and either the key or the value would otherwise be
        garbage the entry can be removed. If WEAKNESS is :KEY-OR-VALUE and
        both the key and the value would otherwise be garbage the entry can
-       be removed."
+       be removed.
+     :SYNCHRONIZED -- If NIL (the default), the hash-table may have
+       multiple concurrent readers, but results are undefined if a
+       thread writes to the hash-table concurrently with another
+       reader or writer. If T, all concurrent accesses are safe, but
+       note that CLHS 3.6 (Traversal Rules and Side Effects) remains
+       in force. See also: SB-EXT:WITH-LOCKED-HASH-TABLE. This keyword
+       argument is experimental, and may change incompatibly or be
+       removed in the future."
   (declare (type (or function symbol) test))
   (declare (type unsigned-byte size))
   (multiple-value-bind (test test-fun hash-fun)
@@ -193,8 +229,8 @@
            ;; Note that this has not yet been audited for
            ;; correctness. It just seems to work. -- CSR, 2002-11-02
            (scaled-size (truncate (/ (float size+1) rehash-threshold)))
-           (length (almost-primify (max scaled-size
-                                        (1+ +min-hash-table-size+))))
+           (length (ceil-power-of-two (max scaled-size
+                                           (1+ +min-hash-table-size+))))
            (index-vector (make-array length
                                      :element-type
                                      '(unsigned-byte #.sb!vm:n-word-bits)
@@ -224,7 +260,7 @@
                                  :element-type '(unsigned-byte
                                                  #.sb!vm:n-word-bits)
                                  :initial-element +magic-hash-vector-value+))
-                   :spinlock (sb!thread::make-spinlock))))
+                   :synchronized-p synchronized)))
       (declare (type index size+1 scaled-size length))
       ;; Set up the free list, all free. These lists are 0 terminated.
       (do ((i 1 (1+ i)))
@@ -232,7 +268,6 @@
         (setf (aref next-vector i) (1+ i)))
       (setf (aref next-vector size) 0)
       (setf (hash-table-next-free-kv table) 1)
-      (setf (hash-table-needing-rehash table) 0)
       (setf (aref kv-vector 0) table)
       table)))
 
@@ -266,6 +301,13 @@
 (setf (fdocumentation 'hash-table-weakness 'function)
       "Return the WEAKNESS of HASH-TABLE which is one of NIL, :KEY,
 :VALUE, :KEY-AND-VALUE, :KEY-OR-VALUE.")
+
+;;; Called when we detect circular chains in a hash-table.
+(defun signal-corrupt-hash-table (hash-table)
+  (error "Corrupt NEXT-chain in ~A. This is probably caused by ~
+multiple threads accessing the same hash-table without locking."
+         hash-table))
+
 
 ;;;; accessing functions
 
@@ -273,17 +315,19 @@
 ;;; rehash-size.
 (defun rehash (table)
   (declare (type hash-table table))
+  (aver *gc-inhibit*)
   (let* ((old-kv-vector (hash-table-table table))
          (old-next-vector (hash-table-next-vector table))
          (old-hash-vector (hash-table-hash-vector table))
          (old-size (length old-next-vector))
          (new-size
-          (let ((rehash-size (hash-table-rehash-size table)))
-            (etypecase rehash-size
-              (fixnum
-               (+ rehash-size old-size))
-              (float
-               (the index (truncate (* rehash-size old-size)))))))
+          (ceil-power-of-two
+           (let ((rehash-size (hash-table-rehash-size table)))
+             (etypecase rehash-size
+               (fixnum
+                (+ rehash-size old-size))
+               (float
+                (the index (truncate (* rehash-size old-size))))))))
          (new-kv-vector (make-array (* 2 new-size)
                                     :initial-element +empty-ht-slot+))
          (new-next-vector
@@ -295,10 +339,7 @@
             (make-array new-size
                         :element-type '(unsigned-byte #.sb!vm:n-word-bits)
                         :initial-element +magic-hash-vector-value+)))
-         (old-index-vector (hash-table-index-vector table))
-         (new-length (almost-primify
-                      (truncate (/ (float new-size)
-                                   (hash-table-rehash-threshold table)))))
+         (new-length new-size)
          (new-index-vector
           (make-array new-length
                       :element-type '(unsigned-byte #.sb!vm:n-word-bits)
@@ -329,7 +370,6 @@
         (setf (aref new-hash-vector i) (aref old-hash-vector i))))
 
     (setf (hash-table-next-free-kv table) 0)
-    (setf (hash-table-needing-rehash table) 0)
     ;; Rehash all the entries; last to first so that after the pushes
     ;; the chains are first to last.
     (do ((i (1- new-size) (1- i)))
@@ -348,7 +388,7 @@
                             +magic-hash-vector-value+)))
                ;; Can use the existing hash value (not EQ based)
                (let* ((hashing (aref new-hash-vector i))
-                      (index (rem hashing new-length))
+                      (index (index-for-hashing hashing new-length))
                       (next (aref new-index-vector index)))
                  (declare (type index index)
                           (type hash hashing))
@@ -361,7 +401,7 @@
                (set-header-data new-kv-vector
                                 sb!vm:vector-valid-hashing-subtype)
                (let* ((hashing (pointer-hash key))
-                      (index (rem hashing new-length))
+                      (index (index-for-hashing hashing new-length))
                       (next (aref new-index-vector index)))
                  (declare (type index index)
                           (type hash hashing))
@@ -372,18 +412,18 @@
     (setf (hash-table-index-vector table) new-index-vector)
     (setf (hash-table-next-vector table) new-next-vector)
     (setf (hash-table-hash-vector table) new-hash-vector)
-    ;; Shrink the old vectors to 0 size to help the conservative GC.
-    (%shrink-vector old-kv-vector 0)
-    (%shrink-vector old-index-vector 0)
-    (%shrink-vector old-next-vector 0)
-    (when old-hash-vector
-      (%shrink-vector old-hash-vector 0))
-    (setf (hash-table-rehash-trigger table) new-size))
+    ;; Fill the old kv-vector with 0 to help the conservative GC. Even
+    ;; if nothing else were zeroed, it's important to clear the
+    ;; special first cells in old-kv-vector.
+    (fill old-kv-vector 0)
+    (setf (hash-table-rehash-trigger table) new-size)
+    (setf (hash-table-needs-rehash-p table) nil))
   (values))
 
 ;;; Use the same size as before, re-using the vectors.
 (defun rehash-without-growing (table)
   (declare (type hash-table table))
+  (aver *gc-inhibit*)
   (let* ((kv-vector (hash-table-table table))
          (next-vector (hash-table-next-vector table))
          (hash-vector (hash-table-hash-vector table))
@@ -400,7 +440,6 @@
 
     ;; Rehash all the entries.
     (setf (hash-table-next-free-kv table) 0)
-    (setf (hash-table-needing-rehash table) 0)
     (dotimes (i size)
       (setf (aref next-vector i) 0))
     (dotimes (i length)
@@ -419,7 +458,7 @@
                                         +magic-hash-vector-value+)))
                ;; Can use the existing hash value (not EQ based)
                (let* ((hashing (aref hash-vector i))
-                      (index (rem hashing length))
+                      (index (index-for-hashing hashing length))
                       (next (aref index-vector index)))
                  (declare (type index index))
                  ;; Push this slot into the next chain.
@@ -430,275 +469,357 @@
                ;; Enable GC tricks.
                (set-header-data kv-vector sb!vm:vector-valid-hashing-subtype)
                (let* ((hashing (pointer-hash key))
-                      (index (rem hashing length))
+                      (index (index-for-hashing hashing length))
                       (next (aref index-vector index)))
                  (declare (type index index)
                           (type hash hashing))
                  ;; Push this slot into the next chain.
                  (setf (aref next-vector i) next)
                  (setf (aref index-vector index) i)))))))
+  ;; Clear the rehash bit only at the very end, otherwise another thread
+  ;; might see a partially rehashed table as a normal one.
+  (setf (hash-table-needs-rehash-p table) nil)
   (values))
 
-(defun flush-needing-rehash (table)
-  (let* ((kv-vector (hash-table-table table))
-         (index-vector (hash-table-index-vector table))
-         (next-vector (hash-table-next-vector table))
-         (length (length index-vector)))
-    (do ((next (hash-table-needing-rehash table)))
-        ((zerop next))
-      (declare (type index/2 next))
-      (let* ((key (aref kv-vector (* 2 next)))
-             (hashing (pointer-hash key))
-             (index (rem hashing length))
-             (temp (aref next-vector next)))
-        (setf (aref next-vector next) (aref index-vector index))
-        (setf (aref index-vector index) next)
-        (setf next temp))))
-  (setf (hash-table-needing-rehash table) 0)
-  (values))
+(declaim (inline maybe-rehash))
+(defun maybe-rehash (hash-table ensure-free-slot-p)
+  (when (hash-table-weakness hash-table)
+    (aver *gc-inhibit*))
+  (flet ((rehash-p ()
+           (and ensure-free-slot-p
+                (zerop (hash-table-next-free-kv hash-table))))
+         (rehash-without-growing-p ()
+           (hash-table-needs-rehash-p hash-table)))
+    (declare (inline rehash-p rehash-without-growing-p))
+    (cond ((rehash-p)
+           ;; Use recursive spinlocks since for weak tables the
+           ;; spinlock has already been acquired. GC must be inhibited
+           ;; to prevent the GC from seeing a rehash in progress.
+           (sb!thread::with-recursive-system-spinlock
+               ((hash-table-spinlock hash-table) :without-gcing t)
+             ;; Repeat the condition inside the lock to ensure that if
+             ;; two reader threads enter MAYBE-REHASH at the same time
+             ;; only one rehash is performed.
+             (when (rehash-p)
+               (rehash hash-table))))
+          ((rehash-without-growing-p)
+           (sb!thread::with-recursive-system-spinlock
+               ((hash-table-spinlock hash-table) :without-gcing t)
+             (when (rehash-without-growing-p)
+               (rehash-without-growing hash-table)))))))
+
+(declaim (inline update-hash-table-cache))
+(defun update-hash-table-cache (hash-table index)
+  (unless (hash-table-weakness hash-table)
+    (setf (hash-table-cache hash-table) index)))
+
+(defmacro with-hash-table-locks ((hash-table
+                                  &key inline pin
+                                  (synchronized `(hash-table-synchronized-p ,hash-table)))
+                                 &body body)
+  (with-unique-names (body-fun)
+    `(with-concurrent-access-check ,hash-table
+       (flet ((,body-fun ()
+                (locally (declare (inline ,@inline))
+                  ,@body)))
+         (if (hash-table-weakness ,hash-table)
+             (sb!thread::with-recursive-system-spinlock
+                 ((hash-table-spinlock ,hash-table) :without-gcing t)
+               (,body-fun))
+             (with-pinned-objects ,pin
+               (if ,synchronized
+                   ;; We use a "system" spinlock here because it is very
+                   ;; slightly faster, as it doesn't re-enable interrupts.
+                   (sb!thread::with-recursive-system-spinlock
+                       ((hash-table-spinlock ,hash-table))
+                     (,body-fun))
+                   (,body-fun))))))))
 
 (defun gethash (key hash-table &optional default)
   #!+sb-doc
-  "Finds the entry in HASH-TABLE whose key is KEY and returns the associated
-   value and T as multiple values, or returns DEFAULT and NIL if there is no
-   such entry. Entries can be added using SETF."
+  "Finds the entry in HASH-TABLE whose key is KEY and returns the
+associated value and T as multiple values, or returns DEFAULT and NIL
+if there is no such entry. Entries can be added using SETF."
   (declare (type hash-table hash-table)
            (values t (member t nil)))
   (gethash3 key hash-table default))
 
-(defun gethash2 (key hash-table)
-  #!+sb-doc
-  "Two argument version of GETHASH"
+(declaim (maybe-inline %gethash3))
+(defun %gethash3 (key hash-table default)
   (declare (type hash-table hash-table)
+           (optimize speed)
            (values t (member t nil)))
-  (gethash3 key hash-table nil))
+  (tagbody
+   start
+     (let ((start-epoch sb!kernel::*gc-epoch*))
+       (macrolet ((result (value foundp)
+                    ;; When the table has multiple concurrent readers,
+                    ;; it's possible that there was a GC after this
+                    ;; thread called MAYBE-REHASH from %GETHASH3, and
+                    ;; some other thread then rehashed the table. If
+                    ;; this happens, we might not find the key even if
+                    ;; it's in the table. To protect against this,
+                    ;; redo the lookup if the GC epoch counter has changed.
+                    ;; -- JES,  2007-09-30
+                    `(if (and (not ,foundp)
+                              (not (eql start-epoch sb!kernel::*gc-epoch*)))
+                         (go start)
+                         (return-from %gethash3 (values ,value ,foundp))))
+                  (overflow ()
+                    ;; The next-vector chain is circular. This is caused
+                    ;; caused by thread-unsafe mutations of the table.
+                    `(signal-corrupt-hash-table hash-table)))
+         (maybe-rehash hash-table nil)
+         ;; Note that it's OK for a GC + a REHASH-WITHOUT-GROWING to
+         ;; be triggered by another thread after this point, since the
+         ;; GC epoch check will catch it.
+         (let ((cache (hash-table-cache hash-table))
+               (table (hash-table-table hash-table)))
+           ;; First check the cache.  Use EQ here for speed.
+           (if (and cache
+                    (< cache (length table))
+                    (eq (aref table cache) key))
+               (let ((value (aref table (1+ cache))))
+                 (result value t))
+               ;; Search for key in the hash table.
+               (multiple-value-bind (hashing eq-based)
+                   (funcall (hash-table-hash-fun hash-table) key)
+                 (declare (type hash hashing))
+                 (let* ((index-vector (hash-table-index-vector hash-table))
+                        (length (length index-vector))
+                        (index (index-for-hashing hashing length))
+                        (next (aref index-vector index))
+                        (next-vector (hash-table-next-vector hash-table))
+                        (hash-vector (hash-table-hash-vector hash-table))
+                        (test-fun (hash-table-test-fun hash-table)))
+                   (declare (type index index))
+                   ;; Search next-vector chain for a matching key.
+                   (if (or eq-based (not hash-vector))
+                       (do ((next next (aref next-vector next))
+                            (i 0 (1+ i)))
+                           ((zerop next) (result default nil))
+                         (declare (type index/2 next i))
+                         (when (> i length)
+                           (overflow))
+                         (when (eq key (aref table (* 2 next)))
+                           (update-hash-table-cache hash-table (* 2 next))
+                           (let ((value (aref table (1+ (* 2 next)))))
+                             (result value t))))
+                       (do ((next next (aref next-vector next))
+                            (i 0 (1+ i)))
+                           ((zerop next) (result default nil))
+                         (declare (type index/2 next i))
+                         (when (> i length)
+                           (overflow))
+                         (when (and (= hashing (aref hash-vector next))
+                                    (funcall test-fun key
+                                             (aref table (* 2 next))))
+                           ;; Found.
+                           (update-hash-table-cache hash-table (* 2 next))
+                           (let ((value (aref table (1+ (* 2 next)))))
+                             (result value t)))))))))))))
 
 (defun gethash3 (key hash-table default)
-  #!+sb-doc
   "Three argument version of GETHASH"
-  (declare (type hash-table hash-table)
-           (values t (member t nil)))
-  (with-spinlock-and-without-gcing ((hash-table-spinlock hash-table))
-   (cond ((= (get-header-data (hash-table-table hash-table))
-             sb!vm:vector-must-rehash-subtype)
-          (rehash-without-growing hash-table))
-         ((not (zerop (hash-table-needing-rehash hash-table)))
-          (flush-needing-rehash hash-table)))
-
-   ;; First check the cache.  Use EQ here for speed.
-   (let ((cache (hash-table-cache hash-table))
-         (table (hash-table-table hash-table)))
-
-     (if (and cache (< cache (length table)) (eq (aref table cache) key))
-         (values (aref table (1+ cache)) t)
-
-       ;; Search for key in the hash table.
-       (multiple-value-bind (hashing eq-based)
-           (funcall (hash-table-hash-fun hash-table) key)
-         (declare (type hash hashing))
-         (let* ((index-vector (hash-table-index-vector hash-table))
-                (length (length index-vector))
-                (index (rem hashing length))
-                (next (aref index-vector index))
-                (next-vector (hash-table-next-vector hash-table))
-                (hash-vector (hash-table-hash-vector hash-table))
-                (test-fun (hash-table-test-fun hash-table)))
-           (declare (type index index))
-           ;; Search next-vector chain for a matching key.
-           (if (or eq-based (not hash-vector))
-               (do ((next next (aref next-vector next)))
-                   ((zerop next) (values default nil))
-                 (declare (type index/2 next))
-                 (when (eq key (aref table (* 2 next)))
-                   (setf (hash-table-cache hash-table) (* 2 next))
-                   (return (values (aref table (1+ (* 2 next))) t))))
-             (do ((next next (aref next-vector next)))
-                 ((zerop next) (values default nil))
-               (declare (type index/2 next))
-               (when (and (= hashing (aref hash-vector next))
-                          (funcall test-fun key (aref table (* 2 next))))
-                 ;; Found.
-                 (setf (hash-table-cache hash-table) (* 2 next))
-                 (return (values (aref table (1+ (* 2 next))) t)))))))))))
+  (declare (type hash-table hash-table))
+  (with-hash-table-locks (hash-table :inline (%gethash3) :pin (key))
+    (%gethash3 key hash-table default)))
 
 ;;; so people can call #'(SETF GETHASH)
 (defun (setf gethash) (new-value key table &optional default)
   (declare (ignore default))
   (%puthash key table new-value))
 
+(declaim (maybe-inline %%puthash))
+(defun %%puthash (key hash-table value)
+  (declare (optimize speed))
+  ;; We need to rehash here so that a current key can be found if it
+  ;; exists. Check that there is room for one more entry. May not be
+  ;; needed if the key is already present.
+  (maybe-rehash hash-table t)
+  ;; Search for key in the hash table.
+  (multiple-value-bind (hashing eq-based)
+      (funcall (hash-table-hash-fun hash-table) key)
+    (declare (type hash hashing))
+    (let* ((index-vector (hash-table-index-vector hash-table))
+           (length (length index-vector))
+           (index (index-for-hashing hashing length))
+           (next (aref index-vector index))
+           (kv-vector (hash-table-table hash-table))
+           (next-vector (hash-table-next-vector hash-table))
+           (hash-vector (hash-table-hash-vector hash-table))
+           (test-fun (hash-table-test-fun hash-table)))
+      (declare (type index index next))
+      (when (hash-table-weakness hash-table)
+        (set-header-data kv-vector sb!vm:vector-valid-hashing-subtype))
+      (cond ((or eq-based (not hash-vector))
+             (when eq-based
+               (set-header-data kv-vector
+                                sb!vm:vector-valid-hashing-subtype))
+             ;; Search next-vector chain for a matching key.
+             (do ((next next (aref next-vector next))
+                  (i 0 (1+ i)))
+                 ((zerop next))
+               (declare (type index/2 next i))
+               (when (> i length)
+                 (signal-corrupt-hash-table hash-table))
+               (when (eq key (aref kv-vector (* 2 next)))
+                 ;; Found, just replace the value.
+                 (update-hash-table-cache hash-table (* 2 next))
+                 (setf (aref kv-vector (1+ (* 2 next))) value)
+                 (return-from %%puthash value))))
+            (t
+             ;; Search next-vector chain for a matching key.
+             (do ((next next (aref next-vector next))
+                  (i 0 (1+ i)))
+                 ((zerop next))
+               (declare (type index/2 next i))
+               (when (> i length)
+                 (signal-corrupt-hash-table hash-table))
+               (when (and (= hashing (aref hash-vector next))
+                          (funcall test-fun key
+                                   (aref kv-vector (* 2 next))))
+                 ;; Found, just replace the value.
+                 (update-hash-table-cache hash-table (* 2 next))
+                 (setf (aref kv-vector (1+ (* 2 next))) value)
+                 (return-from %%puthash value)))))
+      ;; Pop a KV slot off the free list
+      (let ((free-kv-slot (hash-table-next-free-kv hash-table)))
+        (declare (type index/2 free-kv-slot))
+        ;; Double-check for overflow.
+        (aver (not (zerop free-kv-slot)))
+        (setf (hash-table-next-free-kv hash-table)
+              (aref next-vector free-kv-slot))
+        (incf (hash-table-number-entries hash-table))
+        (update-hash-table-cache hash-table (* 2 free-kv-slot))
+        (setf (aref kv-vector (* 2 free-kv-slot)) key)
+        (setf (aref kv-vector (1+ (* 2 free-kv-slot))) value)
+        ;; Setup the hash-vector if necessary.
+        (when hash-vector
+          (if (not eq-based)
+              (setf (aref hash-vector free-kv-slot) hashing)
+              (aver (= (aref hash-vector free-kv-slot)
+                       +magic-hash-vector-value+))))
+        ;; Push this slot into the next chain.
+        (setf (aref next-vector free-kv-slot) next)
+        (setf (aref index-vector index) free-kv-slot)))
+    value))
+
 (defun %puthash (key hash-table value)
   (declare (type hash-table hash-table))
   (aver (hash-table-index-vector hash-table))
-  (with-spinlock-and-without-gcing ((hash-table-spinlock hash-table))
-   ;; We need to rehash here so that a current key can be found if it
-   ;; exists. Check that there is room for one more entry. May not be
-   ;; needed if the key is already present.
-   (cond ((zerop (hash-table-next-free-kv hash-table))
-          (rehash hash-table))
-         ((= (get-header-data (hash-table-table hash-table))
-             sb!vm:vector-must-rehash-subtype)
-          (rehash-without-growing hash-table))
-         ((not (zerop (hash-table-needing-rehash hash-table)))
-          (flush-needing-rehash hash-table)))
-
-   (let ((cache (hash-table-cache hash-table))
-         (kv-vector (hash-table-table hash-table)))
-
-     ;; Check the cache
-     (if (and cache (< cache (length kv-vector))
-              (eq (aref kv-vector cache) key))
-         ;; If cached, just store here
-         (setf (aref kv-vector (1+ cache)) value)
-
-       ;; Search for key in the hash table.
-       (multiple-value-bind (hashing eq-based)
-           (funcall (hash-table-hash-fun hash-table) key)
-         (declare (type hash hashing))
-         (let* ((index-vector (hash-table-index-vector hash-table))
-                (length (length index-vector))
-                (index (rem hashing length))
-                (next (aref index-vector index))
-                (kv-vector (hash-table-table hash-table))
-                (next-vector (hash-table-next-vector hash-table))
-                (hash-vector (hash-table-hash-vector hash-table))
-                (test-fun (hash-table-test-fun hash-table)))
-           (declare (type index index next))
-           (when (hash-table-weakness hash-table)
-             (set-header-data kv-vector sb!vm:vector-valid-hashing-subtype))
-           (cond ((or eq-based (not hash-vector))
-                  (when eq-based
-                    (set-header-data kv-vector
-                                     sb!vm:vector-valid-hashing-subtype))
-
-                  ;; Search next-vector chain for a matching key.
-                  (do ((next next (aref next-vector next)))
-                      ((zerop next))
-                    (declare (type index/2 next))
-                    (when (eq key (aref kv-vector (* 2 next)))
-                      ;; Found, just replace the value.
-                      (setf (hash-table-cache hash-table) (* 2 next))
-                      (setf (aref kv-vector (1+ (* 2 next))) value)
-                      (return-from %puthash value))))
-                 (t
-                  ;; Search next-vector chain for a matching key.
-                  (do ((next next (aref next-vector next)))
-                      ((zerop next))
-                    (declare (type index/2 next))
-                    (when (and (= hashing (aref hash-vector next))
-                               (funcall test-fun key
-                                        (aref kv-vector (* 2 next))))
-                      ;; Found, just replace the value.
-                      (setf (hash-table-cache hash-table) (* 2 next))
-                      (setf (aref kv-vector (1+ (* 2 next))) value)
-                      (return-from %puthash value)))))
-
-           ;; Pop a KV slot off the free list
-           (let ((free-kv-slot (hash-table-next-free-kv hash-table)))
-             (declare (type index/2 free-kv-slot))
-             ;; Double-check for overflow.
-             (aver (not (zerop free-kv-slot)))
-             (setf (hash-table-next-free-kv hash-table)
-                   (aref next-vector free-kv-slot))
-             (incf (hash-table-number-entries hash-table))
-
-             (setf (hash-table-cache hash-table) (* 2 free-kv-slot))
-             (setf (aref kv-vector (* 2 free-kv-slot)) key)
-             (setf (aref kv-vector (1+ (* 2 free-kv-slot))) value)
-
-             ;; Setup the hash-vector if necessary.
-             (when hash-vector
-               (if (not eq-based)
-                   (setf (aref hash-vector free-kv-slot) hashing)
-                   (aver (= (aref hash-vector free-kv-slot)
-                            +magic-hash-vector-value+))))
-
-             ;; Push this slot into the next chain.
-             (setf (aref next-vector free-kv-slot) next)
-             (setf (aref index-vector index) free-kv-slot)))))))
-  value)
+  (macrolet ((put-it (lockedp)
+               `(let ((cache (hash-table-cache hash-table))
+        (kv-vector (hash-table-table hash-table)))
+    ;; Check the cache
+    (if (and cache
+             (< cache (length kv-vector))
+             (eq (aref kv-vector cache) key))
+        ;; If cached, just store here
+        (setf (aref kv-vector (1+ cache)) value)
+        ;; Otherwise do things the hard way
+                      ,(if lockedp
+                           '(%%puthash key hash-table value)
+                           '(with-hash-table-locks
+                             (hash-table :inline (%%puthash) :pin (key)
+                              :synchronized nil)
+                             (%%puthash key hash-table value)))))))
+    (if (hash-table-synchronized-p hash-table)
+        (with-hash-table-locks (hash-table :pin (key) :synchronized t)
+          (put-it t))
+        (put-it nil))))
+
+(declaim (maybe-inline %remhash))
+(defun %remhash (key hash-table)
+  ;; We need to rehash here so that a current key can be found if it
+  ;; exists.
+  ;;
+  ;; Note that if a GC happens after MAYBE-REHASH returns and another
+  ;; thread the accesses the table (triggering a rehash), we might not
+  ;; find the key even if it is in the table. But that's ok, since the
+  ;; only concurrent case that we safely allow is multiple readers
+  ;; with no writers.
+  (maybe-rehash hash-table nil)
+  ;; Search for key in the hash table.
+  (multiple-value-bind (hashing eq-based)
+      (funcall (hash-table-hash-fun hash-table) key)
+    (declare (type hash hashing))
+    (let* ((index-vector (hash-table-index-vector hash-table))
+           (length (length index-vector))
+           (index (index-for-hashing hashing length))
+           (next (aref index-vector index))
+           (table (hash-table-table hash-table))
+           (next-vector (hash-table-next-vector hash-table))
+           (hash-vector (hash-table-hash-vector hash-table))
+           (test-fun (hash-table-test-fun hash-table)))
+      (declare (type index index)
+               (type index/2 next))
+      (flet ((clear-slot (chain-vector prior-slot-location slot-location)
+               (declare (type index/2 slot-location))
+               ;; Mark slot as empty.
+               (setf (aref table (* 2 slot-location)) +empty-ht-slot+
+                     (aref table (1+ (* 2 slot-location))) +empty-ht-slot+)
+               ;; Update the prior pointer in the chain to skip this.
+               (setf (aref chain-vector prior-slot-location)
+                     (aref next-vector slot-location))
+               ;; Push KV slot onto free chain.
+               (setf (aref next-vector slot-location)
+                     (hash-table-next-free-kv hash-table))
+               (setf (hash-table-next-free-kv hash-table) slot-location)
+               (when hash-vector
+                 (setf (aref hash-vector slot-location)
+                       +magic-hash-vector-value+))
+               (decf (hash-table-number-entries hash-table))
+               t))
+        (cond ((zerop next)
+               nil)
+              ((if (or eq-based (not hash-vector))
+                   (eq key (aref table (* 2 next)))
+                   (and (= hashing (aref hash-vector next))
+                        (funcall test-fun key (aref table (* 2 next)))))
+               (clear-slot index-vector index next))
+              ;; Search next-vector chain for a matching key.
+              ((or eq-based (not hash-vector))
+               ;; EQ based
+               (do ((prior next next)
+                    (i 0 (1+ i))
+                    (next (aref next-vector next) (aref next-vector next)))
+                   ((zerop next) nil)
+                 (declare (type index next))
+                 (when (> i length)
+                   (signal-corrupt-hash-table hash-table))
+                 (when (eq key (aref table (* 2 next)))
+                   (return-from %remhash (clear-slot next-vector prior next)))))
+              (t
+               ;; not EQ based
+               (do ((prior next next)
+                    (i 0 (1+ i))
+                    (next (aref next-vector next) (aref next-vector next)))
+                   ((zerop next) nil)
+                 (declare (type index/2 next))
+                 (when (> i length)
+                   (signal-corrupt-hash-table hash-table))
+                 (when (and (= hashing (aref hash-vector next))
+                            (funcall test-fun key (aref table (* 2 next))))
+                   (return-from %remhash
+                     (clear-slot next-vector prior next))))))))))
 
 (defun remhash (key hash-table)
   #!+sb-doc
-  "Remove the entry in HASH-TABLE associated with KEY. Return T if there
-   was such an entry, or NIL if not."
+  "Remove the entry in HASH-TABLE associated with KEY. Return T if
+there was such an entry, or NIL if not."
   (declare (type hash-table hash-table)
            (values (member t nil)))
-  (with-spinlock-and-without-gcing ((hash-table-spinlock hash-table))
-   ;; We need to rehash here so that a current key can be found if it
-   ;; exists.
-   (cond ((= (get-header-data (hash-table-table hash-table))
-             sb!vm:vector-must-rehash-subtype)
-          (rehash-without-growing hash-table))
-         ((not (zerop (hash-table-needing-rehash hash-table)))
-          (flush-needing-rehash hash-table)))
-
-   ;; For now, just clear the cache
-   (setf (hash-table-cache hash-table) nil)
-
-   ;; Search for key in the hash table.
-   (multiple-value-bind (hashing eq-based)
-       (funcall (hash-table-hash-fun hash-table) key)
-     (declare (type hash hashing))
-     (let* ((index-vector (hash-table-index-vector hash-table))
-            (length (length index-vector))
-            (index (rem hashing length))
-            (next (aref index-vector index))
-            (table (hash-table-table hash-table))
-            (next-vector (hash-table-next-vector hash-table))
-            (hash-vector (hash-table-hash-vector hash-table))
-            (test-fun (hash-table-test-fun hash-table)))
-       (declare (type index index)
-                (type index/2 next))
-       (flet ((clear-slot (chain-vector prior-slot-location slot-location)
-                (declare (type index/2 slot-location))
-                ;; Mark slot as empty.
-                (setf (aref table (* 2 slot-location)) +empty-ht-slot+
-                      (aref table (1+ (* 2 slot-location))) +empty-ht-slot+)
-                ;; Update the prior pointer in the chain to skip this.
-                (setf (aref chain-vector prior-slot-location)
-                      (aref next-vector slot-location))
-                ;; Push KV slot onto free chain.
-                (setf (aref next-vector slot-location)
-                      (hash-table-next-free-kv hash-table))
-                (setf (hash-table-next-free-kv hash-table) slot-location)
-                (when hash-vector
-                  (setf (aref hash-vector slot-location)
-                        +magic-hash-vector-value+))
-                (decf (hash-table-number-entries hash-table))
-                t))
-         (cond ((zerop next)
-                nil)
-               ((if (or eq-based (not hash-vector))
-                    (eq key (aref table (* 2 next)))
-                    (and (= hashing (aref hash-vector next))
-                         (funcall test-fun key (aref table (* 2 next)))))
-                (clear-slot index-vector index next))
-               ;; Search next-vector chain for a matching key.
-               ((or eq-based (not hash-vector))
-                ;; EQ based
-                (do ((prior next next)
-                     (next (aref next-vector next) (aref next-vector next)))
-                    ((zerop next) nil)
-                  (declare (type index next))
-                  (when (eq key (aref table (* 2 next)))
-                    (return-from remhash (clear-slot next-vector prior next)))))
-               (t
-                ;; not EQ based
-                (do ((prior next next)
-                     (next (aref next-vector next) (aref next-vector next)))
-                    ((zerop next) nil)
-                  (declare (type index/2 next))
-                  (when (and (= hashing (aref hash-vector next))
-                             (funcall test-fun key (aref table (* 2 next))))
-                    (return-from remhash
-                      (clear-slot next-vector prior next)))))))))))
+  (with-hash-table-locks (hash-table :inline (%remhash) :pin (key))
+  ;; For now, just clear the cache
+  (setf (hash-table-cache hash-table) nil)
+    (%remhash key hash-table)))
 
 (defun clrhash (hash-table)
   #!+sb-doc
-  "This removes all the entries from HASH-TABLE and returns the hash table
-   itself."
-  (declare (optimize speed))
-  (with-spinlock-and-without-gcing ((hash-table-spinlock hash-table))
+  "This removes all the entries from HASH-TABLE and returns the hash
+table itself."
+  (with-hash-table-locks (hash-table)
     (let* ((kv-vector (hash-table-table hash-table))
            (next-vector (hash-table-next-vector hash-table))
            (hash-vector (hash-table-hash-vector hash-table))
@@ -716,15 +837,15 @@
         (setf (aref next-vector i) (1+ i)))
       (setf (aref next-vector (1- size)) 0)
       (setf (hash-table-next-free-kv hash-table) 1)
-      (setf (hash-table-needing-rehash hash-table) 0)
       ;; Clear the index-vector.
       (fill index-vector 0)
       ;; Clear the hash-vector.
       (when hash-vector
         (fill hash-vector +magic-hash-vector-value+)))
     (setf (hash-table-cache hash-table) nil)
-    (setf (hash-table-number-entries hash-table) 0))
-  hash-table)
+    (setf (hash-table-number-entries hash-table) 0)
+    hash-table))
+
 
 ;;;; MAPHASH
 
@@ -738,7 +859,14 @@
 (defun maphash (function-designator hash-table)
   #!+sb-doc
   "For each entry in HASH-TABLE, call the designated two-argument function on
-the key and value of the entry. Return NIL."
+the key and value of the entry. Return NIL.
+
+Consequences are undefined if HASH-TABLE is mutated during the call to
+MAPHASH, except for changing or removing elements corresponding to the
+current key. The applies to all threads, not just the current one --
+even for synchronized hash-tables. If the table may be mutated by
+another thread during iteration, use eg. SB-EXT:WITH-LOCKED-HASH-TABLE
+to protect the MAPHASH call."
   ;; This essentially duplicates WITH-HASH-TABLE-ITERATOR, so
   ;; any changes here should be reflected there as well.
   (let ((fun (%coerce-callable-to-fun function-designator))
@@ -806,3 +934,5 @@ the key and value of the entry. Return NIL."
   (declare (ignore environment))
   (values `(make-hash-table ,@(%hash-table-ctor-args hash-table))
           `(%stuff-hash-table ,hash-table ',(%hash-table-alist hash-table))))
+
+