Changeset 10912


Ignore:
Timestamp:
Sep 28, 2008, 2:05:53 PM (11 years ago)
Author:
gz
Message:

Fix some boundary cases in %lock-free-rehash (they were trying to restart the rehash after addressing the issue, forgetting that the original vector is now clobbered!).

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/working-0711/ccl/level-0/l0-hash.lisp

    r10868 r10912  
    116116        (not (eql (the fixnum (%get-gc-count)) (the fixnum (nhash.vector.gc-count vector))))))))
    117117
    118 (defun %set-does-not-need-rehashing (hash)
    119   (let* ((vector (nhash.vector hash))
    120          (flags (nhash.vector.flags vector)))
     118(defun %set-does-not-need-rehashing (vector)
     119  (let* ((flags (nhash.vector.flags vector)))
    121120    (declare (fixnum flags))
    122121    (setf (nhash.vector.gc-count vector) (%get-gc-count))
     
    681680;; old and new vectors.
    682681(defun %lock-free-rehash (hash)
    683   ;; Prevent puthash from adding new entries.  Note this doesn't keep it from undeleting
    684   ;; existing entries, so we might still lose, but this makes the odds much smaller.
    685   (setf (nhash.grow-threshold hash) 0)
    686682  (let* ((old-vector (nhash.vector hash))
    687683         (inherited-flags (logand $nhash_weak_flags_mask (nhash.vector.flags old-vector)))
    688          count new-vector grow-threshold vector-size)
    689     (tagbody
    690      RESTART
    691      (setq count (lock-free-count-entries hash))
    692      (multiple-value-setq (grow-threshold vector-size)
    693        (compute-hash-size count (nhash.rehash-size hash) (nhash.rehash-ratio hash)))
    694      (setq new-vector (%cons-nhash-vector vector-size inherited-flags))
    695      REHASH
    696      (loop for i from $nhash.vector_overhead below (uvsize old-vector) by 2
    697        do (let ((value (atomic-swap-gvector (%i+ i 1) old-vector rehashing-value-marker)))
    698             (when (eq value rehashing-value-marker) (error "Who else is doing this?"))
    699             (unless (eq value free-hash-marker)
    700               (let* ((key (%svref old-vector i))
    701                      (new-index (%growhash-probe new-vector hash key))
    702                      (new-vector-index (index->vector-index new-index)))
    703                 (setf (%svref new-vector new-vector-index) key)
    704                 (setf (%svref new-vector (%i+ new-vector-index 1)) value)
    705                 (when (%i<= (decf grow-threshold) 0)
    706                   ;; Too many entries got undeleted while we were rehashing!
    707                   (go RESTART))))))
    708      (when (%needs-rehashing-p new-vector) ;; keys moved, but at least can use the same new-vector.
    709        (%init-misc free-hash-marker new-vector)
    710        (%init-nhash-vector new-vector inherited-flags)
    711        (go REHASH)))
     684         (grow-threshold (nhash.grow-threshold hash))
     685         count new-vector vector-size)
     686    ;; Prevent puthash from adding new entries.  Note this doesn't keep it from undeleting
     687    ;; existing entries, so we might still lose, but this makes the odds much smaller.
     688    (setf (nhash.grow-threshold hash) 0)
     689    (setq count (lock-free-count-entries hash))
     690    (multiple-value-setq (grow-threshold vector-size)
     691      (if (%i<= grow-threshold 0) ; if ran out of room, grow, else get just enough.
     692        (compute-hash-size count (nhash.rehash-size hash) (nhash.rehash-ratio hash))
     693        (compute-hash-size count 1 (nhash.rehash-ratio hash))))
     694    (setq new-vector (%cons-nhash-vector vector-size inherited-flags))
     695    (loop with full-count = grow-threshold
     696          for i from $nhash.vector_overhead below (uvsize old-vector) by 2
     697          do (let* ((value (atomic-swap-gvector (%i+ i 1) old-vector rehashing-value-marker))
     698                    (key (%svref old-vector i)))
     699               (when (eq value rehashing-value-marker) (error "Who else is doing this?"))
     700               (unless (or (eq value free-hash-marker) (eq key deleted-hash-key-marker))
     701                 (let* ((new-index (%growhash-probe new-vector hash key))
     702                        (new-vector-index (index->vector-index new-index)))
     703                   (%set-hash-table-vector-key new-vector new-vector-index key)
     704                   (setf (%svref new-vector (%i+ new-vector-index 1)) value)
     705                   (decf grow-threshold)
     706                   (when (%i<= grow-threshold 0)
     707                     ;; Too many entries got undeleted while we were rehashing (that's the
     708                     ;; only way we could end up with more than COUNT entries, as adding
     709                     ;; new entries is blocked).  Grow the output vector.
     710                     (multiple-value-bind (bigger-threshold bigger-vector-size)
     711                         (compute-hash-size full-count (nhash.rehash-size hash) (nhash.rehash-ratio hash))
     712                       (assert (> bigger-vector-size vector-size))
     713                       (let ((bigger-vector (%cons-nhash-vector bigger-vector-size 0)))
     714                         (%copy-gvector-to-gvector new-vector
     715                                                   $nhash.vector_overhead
     716                                                   bigger-vector
     717                                                   $nhash.vector_overhead
     718                                                   (%i- (uvsize new-vector) $nhash.vector_overhead))
     719                         (setf (nhash.vector.flags bigger-vector) (nhash.vector.flags new-vector))
     720                         (%lock-free-rehash-in-place hash bigger-vector)
     721                         (setq grow-threshold (- bigger-threshold full-count))
     722                         (setq full-count bigger-threshold)
     723                         (setq new-vector bigger-vector)
     724                         (setq vector-size bigger-vector-size))))))))
     725    (when (%needs-rehashing-p new-vector) ;; keys moved, but at least can use the same new-vector.
     726      (%lock-free-rehash-in-place hash new-vector))
    712727    (setf (nhash.vector.hash new-vector) hash)
    713728    (setf (nhash.grow-threshold hash) grow-threshold)
     
    716731    ;; no big deal.
    717732    (setf (nhash.vector hash) new-vector)))
     733
     734;; This is called on a new vector that hasn't been installed yet, so no other thread is
     735;; accessing it.  However, gc might be deleting stuff from it, which is why it tests
     736;; key for deleted-hash-key-marker in addition to free-hash-marker value
     737(defun %lock-free-rehash-in-place (hash vector)
     738  (let* ((vector-index (- $nhash.vector_overhead 2))
     739         (size (nhash.vector-size vector))
     740         (rehash-bits (%make-rehash-bits hash size))
     741         (index -1))
     742    (declare (fixnum size index vector-index))
     743    (%set-does-not-need-rehashing vector)
     744    (loop
     745      (when (>= (incf index) size) (return))
     746      (setq vector-index (+ vector-index 2))
     747      (unless (%already-rehashed-p index rehash-bits)
     748        (let* ((value (%svref vector (%i+ vector-index 1)))
     749               (key (%svref vector vector-index)))
     750          (if (or (eq value free-hash-marker)
     751                  (eq key deleted-hash-key-marker))
     752            (unless (eq key free-hash-marker)
     753              (setf (%svref vector vector-index) free-hash-marker))
     754            (let* ((last-index index)
     755                   (first t))
     756              (loop
     757                (let ((found-index (%rehash-probe rehash-bits hash key vector)))
     758                  (%set-already-rehashed-p found-index rehash-bits)
     759                  (when (eq last-index found-index)
     760                    (return))
     761                  (let* ((found-vector-index (index->vector-index found-index))
     762                         (newvalue (%svref vector (the fixnum (1+ found-vector-index))))
     763                         (newkey (%svref vector found-vector-index)))
     764                    (declare (fixnum found-vector-index))
     765                    (when first         ; or (eq last-index index) ?
     766                      (setq first nil)
     767                      (setf (%svref vector (the fixnum (1+ vector-index))) free-hash-marker)
     768                      (setf (%svref vector vector-index) free-hash-marker))
     769                    (%set-hash-table-vector-key vector found-vector-index key)
     770                    (setf (%svref vector (the fixnum (1+ found-vector-index))) value)
     771                    (when (or (eq newkey deleted-hash-key-marker)
     772                              (eq newvalue free-hash-marker))
     773                      (return))
     774                    (when (eq key newkey)
     775                      (cerror "Delete one of the entries." "Duplicate key: ~s in ~s ~s ~s ~s ~s"
     776                              key hash value newvalue index found-index)                       
     777                      (return))
     778                    (setq key newkey
     779                          value newvalue
     780                          last-index found-index))))))))))
     781  t )
    718782
    719783
     
    820884    (lock-free-rehash hash)))
    821885
    822 
    823886(defun lock-free-count-entries (hash)
    824887  ;; Other threads could be adding/removing entries while we count, some of
     
    830893    with vector = (nhash.vector hash)
    831894    for i fixnum from $nhash.vector_overhead below (uvsize vector) by 2
    832     count (and (neq (%svref vector i) free-hash-marker)
    833                (let ((value (%svref vector (%i+ i 1))))
    834                  (when (eq value rehashing-value-marker)
    835                    ;; This table is being rehashed.  Wait for it to be
    836                    ;; done and try again.
    837                    (lock-free-rehash hash)
    838                    (return-from lock-free-count-entries (lock-free-count-entries hash)))
    839                  (neq value free-hash-marker)))))
     895    count (let ((value (%svref vector (%i+ i 1))))
     896            (when (eq value rehashing-value-marker)
     897              ;; This table is being rehashed.  Wait for it to be
     898              ;; done and try again.
     899              (lock-free-rehash hash)
     900              (return-from lock-free-count-entries (lock-free-count-entries hash)))
     901            (neq value free-hash-marker))))
    840902
    841903;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
     
    14061468    (setf (nhash.vector.cache-key vector) free-hash-marker
    14071469          (nhash.vector.cache-value vector) nil)
    1408     (%set-does-not-need-rehashing hash)
     1470    (%set-does-not-need-rehashing vector)
    14091471    (loop
    14101472      (when (>= (incf index) size) (return))
     
    14731535;;; Hash to an index that is not set in rehash-bits
    14741536 
    1475 (defun %rehash-probe (rehash-bits hash key)
     1537(defun %rehash-probe (rehash-bits hash key &optional (vector (nhash.vector hash)))
    14761538  (declare (optimize (speed 3)(safety 0))) 
    1477   (multiple-value-bind (hash-code index entries)(compute-hash-code hash key t)
     1539  (multiple-value-bind (hash-code index entries)(compute-hash-code hash key t vector)
    14781540    (declare (fixnum hash-code index entries))
    14791541    (when (null hash-code)(cerror "nuts" "Nuts"))
    1480     (let* ((vector (nhash.vector hash))
    1481            (vector-index (index->vector-index  index)))
     1542    (let* ((vector-index (index->vector-index index)))
    14821543      (if (or (not (%already-rehashed-p index rehash-bits))
    14831544              (eq key (%svref vector vector-index)))
Note: See TracChangeset for help on using the changeset viewer.