X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcode%2Ftarget-hash-table.lisp;h=8d652557bc2c92b09a25450b19fd2e810256f5bd;hb=6a0601ab48635465ad3400c290e5cfbca28e5367;hp=f35ff7aa5f14532fb9d28b2861f3a1c9dbabef84;hpb=b2a8ffe548795d682af3712fb6dc6307577d1bab;p=sbcl.git diff --git a/src/code/target-hash-table.lisp b/src/code/target-hash-table.lisp index f35ff7a..8d65255 100644 --- a/src/code/target-hash-table.lisp +++ b/src/code/target-hash-table.lisp @@ -146,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. @@ -160,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 @@ -171,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) @@ -221,7 +230,7 @@ ;; correctness. It just seems to work. -- CSR, 2002-11-02 (scaled-size (truncate (/ (float size+1) rehash-threshold))) (length (ceil-power-of-two (max scaled-size - (1+ +min-hash-table-size+)))) + (1+ +min-hash-table-size+)))) (index-vector (make-array length :element-type '(unsigned-byte #.sb!vm:n-word-bits) @@ -251,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))) @@ -313,11 +322,11 @@ multiple threads accessing the same hash-table without locking." (old-size (length old-next-vector)) (new-size (ceil-power-of-two - (let ((rehash-size (hash-table-rehash-size table))) - (etypecase rehash-size - (fixnum - (+ rehash-size old-size)) - (float + (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+)) @@ -497,41 +506,40 @@ multiple threads accessing the same hash-table without locking." (sb!thread::with-recursive-system-spinlock ((hash-table-spinlock hash-table) :without-gcing t) (when (rehash-without-growing-p) - (without-gcing - (rehash-without-growing hash-table)))))))) + (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 inline &rest pin-objects) +(defmacro with-hash-table-locks ((hash-table + &key inline pin + (synchronized `(hash-table-synchronized-p ,hash-table))) &body body) - `(with-concurrent-access-check ,hash-table - ;; Inhibit GC for the duration of BODY if the GC might mutate the - ;; HASH-TABLE in some way (currently true only if the table is - ;; weak). We also need to lock the table to ensure that two - ;; concurrent writers can't create a cyclical vector that would - ;; cause scav_weak_hash_table_chain to loop. - ;; - ;; Otherwise we can avoid the 2x-3x overhead, and just pin the key. - (if (hash-table-weakness ,hash-table) - (sb!thread::with-recursive-system-spinlock - ((hash-table-spinlock hash-table) :without-gcing t) - ,@body) - (with-pinned-objects ,pin-objects - (locally - ;; Inline the implementation function on the fast path - ;; only. (On the slow path it'll just bloat the - ;; generated code with no benefit). - (declare (inline ,@inline)) - ,@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)) @@ -565,35 +573,35 @@ multiple threads accessing the same hash-table without locking." ;; 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))) + (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)) + ;; 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)) + (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))) + (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)))) @@ -603,10 +611,10 @@ multiple threads accessing the same hash-table without locking." (declare (type index/2 next i)) (when (> i length) (overflow)) - (when (and (= hashing (aref hash-vector next)) + (when (and (= hashing (aref hash-vector next)) (funcall test-fun key (aref table (* 2 next)))) - ;; Found. + ;; Found. (update-hash-table-cache hash-table (* 2 next)) (let ((value (aref table (1+ (* 2 next))))) (result value t))))))))))))) @@ -614,7 +622,7 @@ multiple threads accessing the same hash-table without locking." (defun gethash3 (key hash-table default) "Three argument version of GETHASH" (declare (type hash-table hash-table)) - (with-hash-table-locks (hash-table (%gethash3) key) + (with-hash-table-locks (hash-table :inline (%gethash3) :pin (key)) (%gethash3 key hash-table default))) ;;; so people can call #'(SETF GETHASH) @@ -625,82 +633,83 @@ multiple threads accessing the same hash-table without locking." (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. + ;; 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)) + ;; 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. + (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)) + ((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. + (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) + (setf (aref kv-vector (1+ (* 2 next))) value) (return-from %%puthash value)))) - (t - ;; Search next-vector chain for a matching key. + (t + ;; Search next-vector chain for a matching key. (do ((next next (aref next-vector next)) (i 0 (1+ i))) - ((zerop next)) + ((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. + (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) + (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)) + ;; 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 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)) - (let ((cache (hash-table-cache hash-table)) + (macrolet ((put-it (lockedp) + `(let ((cache (hash-table-cache hash-table)) (kv-vector (hash-table-table hash-table))) ;; Check the cache (if (and cache @@ -709,13 +718,21 @@ multiple threads accessing the same hash-table without locking." ;; If cached, just store here (setf (aref kv-vector (1+ cache)) value) ;; Otherwise do things the hard way - (with-hash-table-locks (hash-table (%%puthash) key) - (%%puthash key hash-table value))))) + ,(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. + ;; 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 @@ -723,86 +740,86 @@ multiple threads accessing the same hash-table without locking." ;; 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)) + ;; 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) + (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)) + (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))) + (when (eq key (aref table (* 2 next))) (return-from %remhash (clear-slot next-vector prior next))))) - (t - ;; not EQ based - (do ((prior next 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)) + (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)))) + (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-hash-table-locks (hash-table :inline (%remhash) :pin (key)) ;; For now, just clear the cache (setf (hash-table-cache hash-table) nil) - (with-hash-table-locks (hash-table (%remhash) key) (%remhash key hash-table))) (defun clrhash (hash-table) #!+sb-doc - "This removes all the entries from HASH-TABLE and returns the hash table - itself." - (with-hash-table-locks (hash-table nil) + "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)) @@ -842,7 +859,14 @@ multiple threads accessing the same hash-table without locking." (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))