\f
;;;; utilities
-(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
;;; 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))
+(defmacro with-concurrent-access-check (hash-table operation &body body)
+ (declare (ignorable hash-table operation)
+ (type (member :read :write) operation))
#!-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)))
+ (let ((thread-slot-accessor (if (eq operation :read)
+ 'hash-table-reading-thread
+ 'hash-table-writing-thread)))
+ (once-only ((hash-table hash-table))
+ `(progn
+ (flet ((body-fun ()
+ ,@body)
+ (error-fun ()
+ ;; Don't signal more errors for this table.
+ (setf (hash-table-signal-concurrent-access ,hash-table) nil)
+ (cerror "Ignore the concurrent access"
+ "Concurrent access to ~A" ,hash-table)))
+ (declare (inline body-fun))
+ (if (hash-table-signal-concurrent-access ,hash-table)
(unwind-protect
(progn
- (when (and thread
- (not (eql thread sb!thread::*current-thread*)))
+ (unless (and (null (hash-table-writing-thread
+ ,hash-table))
+ ,@(when (eq operation :write)
+ `((null (hash-table-reading-thread
+ ,hash-table)))))
(error-fun))
- (setf (hash-table-accessing-thread ,hash-table)
+ (setf (,thread-slot-accessor ,hash-table)
sb!thread::*current-thread*)
(body-fun))
- (unless (eql (hash-table-accessing-thread ,hash-table)
- sb!thread::*current-thread*)
+ (unless (and ,@(when (eq operation :read)
+ `((null (hash-table-writing-thread
+ ,hash-table))))
+ ,@(when (eq operation :write)
+ ;; no readers are allowed while writing
+ `((null (hash-table-reading-thread
+ ,hash-table))
+ (eq (hash-table-writing-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))
-
-;;; FIXME: Does this always make a nonnegative FIXNUM? If so, then
-;;; explain why. If not (or if the reason it always makes a
-;;; nonnegative FIXNUM is only the accident that pointers in supported
-;;; architectures happen to be in the lower half of the address
-;;; space), then fix it.
-#!-sb-fluid (declaim (inline pointer-hash))
-(defun pointer-hash (key)
- (declare (values hash))
- (truly-the hash (%primitive sb!c:make-fixnum key)))
+ (when (eq (,thread-slot-accessor ,hash-table)
+ sb!thread::*current-thread*)
+ ;; this is not 100% correct here and may hide
+ ;; concurrent access in rare circumstances.
+ (setf (,thread-slot-accessor ,hash-table) nil)))
+ (body-fun)))))))
#!-sb-fluid (declaim (inline eq-hash))
(defun eq-hash (key)
(t
(eq-hash key))))
-(defun ceil-power-of-two (num)
- (declare (type index num))
- (ash 1 (integer-length num)))
-
(declaim (inline index-for-hashing))
-(defun index-for-hashing (index length)
- (declare (type index index length))
+(defun index-for-hashing (hash length)
+ (declare (type hash hash 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))))
+ (truly-the index
+ (logand (1- length)
+ (+ (logxor #b11100101010001011010100111
+ hash)
+ (ash hash -3)
+ (ash hash -12)
+ (ash hash -20)))))
\f
;;;; user-defined hash table tests
(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.
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
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)
;; 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 (ceil-power-of-two (max scaled-size
- (1+ +min-hash-table-size+))))
+ (length (power-of-two-ceiling (max scaled-size
+ (1+ +min-hash-table-size+))))
(index-vector (make-array length
:element-type
'(unsigned-byte #.sb!vm:n-word-bits)
: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)))
(old-hash-vector (hash-table-hash-vector table))
(old-size (length old-next-vector))
(new-size
- (ceil-power-of-two
+ (power-of-two-ceiling
(let ((rehash-size (hash-table-rehash-size table)))
(etypecase rehash-size
(fixnum
(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 (operation :write) 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)))))
+ (declare (type (member :read :write) operation))
+ (with-unique-names (body-fun)
+ `(flet ((,body-fun ()
+ (with-concurrent-access-check ,hash-table ,operation
+ (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))
;; 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*)))
+ (not (eq start-epoch sb!kernel::*gc-epoch*)))
(go start)
(return-from %gethash3 (values ,value ,foundp))))
(overflow ()
(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 :operation :read :inline (%gethash3)
+ :pin (key))
(%gethash3 key hash-table default)))
;;; so people can call #'(SETF GETHASH)
(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))
- (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
- (with-hash-table-locks (hash-table (%%puthash) key)
- (%%puthash key hash-table 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)
(when hash-vector
(setf (aref hash-vector slot-location)
+magic-hash-vector-value+))
+ ;; On parallel accesses this may turn out to be a
+ ;; type-error, so don't turn down the safety!
(decf (hash-table-number-entries hash-table))
t))
(cond ((zerop 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)))
- ;; For now, just clear the cache
- (setf (hash-table-cache hash-table) nil)
- (with-hash-table-locks (hash-table (%remhash) key)
+ (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."
- (with-hash-table-locks (hash-table nil)
- (let* ((kv-vector (hash-table-table hash-table))
- (next-vector (hash-table-next-vector hash-table))
- (hash-vector (hash-table-hash-vector hash-table))
- (size (length next-vector))
- (index-vector (hash-table-index-vector hash-table)))
- ;; Disable GC tricks.
- (set-header-data kv-vector sb!vm:vector-normal-subtype)
- ;; Mark all slots as empty by setting all keys and values to magic
- ;; tag.
- (aver (eq (aref kv-vector 0) hash-table))
- (fill kv-vector +empty-ht-slot+ :start 2)
- ;; Set up the free list, all free.
- (do ((i 1 (1+ i)))
- ((>= i (1- size)))
- (setf (aref next-vector i) (1+ i)))
- (setf (aref next-vector (1- size)) 0)
- (setf (hash-table-next-free-kv hash-table) 1)
- ;; 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))
+ "This removes all the entries from HASH-TABLE and returns the hash
+table itself."
+ (when (plusp (hash-table-number-entries hash-table))
+ (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))
+ (size (length next-vector))
+ (index-vector (hash-table-index-vector hash-table)))
+ ;; Disable GC tricks.
+ (set-header-data kv-vector sb!vm:vector-normal-subtype)
+ ;; Mark all slots as empty by setting all keys and values to magic
+ ;; tag.
+ (aver (eq (aref kv-vector 0) hash-table))
+ (fill kv-vector +empty-ht-slot+ :start 2)
+ ;; Set up the free list, all free.
+ (do ((i 1 (1+ i)))
+ ((>= i (1- size)))
+ (setf (aref next-vector i) (1+ i)))
+ (setf (aref next-vector (1- size)) 0)
+ (setf (hash-table-next-free-kv hash-table) 1)
+ ;; 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)
\f
;;;; MAPHASH
(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))
(cond ((or (not *print-readably*) (not *read-eval*))
(print-unreadable-object (hash-table stream :type t :identity t)
(format stream
- ":TEST ~S :COUNT ~S"
+ ":TEST ~S :COUNT ~S~@[ :WEAKNESS ~S~]"
(hash-table-test hash-table)
- (hash-table-count hash-table))))
+ (hash-table-count hash-table)
+ (hash-table-weakness hash-table))))
(t
- (with-standard-io-syntax
- (format stream
- "#.~W"
- `(%stuff-hash-table (make-hash-table ,@(%hash-table-ctor-args
+ (write-string "#." stream)
+ (write `(%stuff-hash-table (make-hash-table ,@(%hash-table-ctor-args
hash-table))
- ',(%hash-table-alist hash-table)))))))
+ ',(%hash-table-alist hash-table))
+ :stream stream))))
(def!method make-load-form ((hash-table hash-table) &optional environment)
(declare (ignore environment))
projects / sbcl.git / blobdiff