Changeset 15525


Ignore:
Timestamp:
Dec 5, 2012, 9:29:15 PM (7 years ago)
Author:
gz
Message:

In lock-free-puthash handle a new key getting relocated just before it's added to the table. Fix %lock-free-rehash-in-place to set both key and value in a free slot. This fixes ticket:993.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/source/level-0/l0-hash.lisp

    r15508 r15525  
    619619;; FREE       free-hash-marker  free-hash-marker
    620620;; INSERTING  object            free-hash-marker
     621;; DELETING0  deleted-marker    free-hash-marker  ;; abandoned insert
    621622;; IN-USE     object            object
    622623;; DELETING1  object            deleted-marker
     
    648649;;      else store-conditional the value -> new value, if fails try again.
    649650;;   ** Else have FREE slot, store-key-conditional free-hash-marker -> key,
    650 ;;      and if that succeeds, store-conditional free-hash-marker -> new value,
    651 ;;      if either fails, maybe-rehash and try again.
     651;;      if that succeeds, check whether key moved (invalidating the hash), if so,
     652;;         back out to DELETED0 and try again,
     653;;      else store-conditional free-hash-marker -> new value,
     654;;      if either store fails, maybe-rehash and try again.
    652655;; * remhash: find matching key - if no match, done.  Else fetch value,
    653656;;   if value is rehashing-value-marker then maybe-rehash and try again;
     
    656659;;    if succeeds, clobber key with deleted-marker to allow it to get gc'd.
    657660;; * clrhash: grab the rehash lock, then set all slots to DELETED (transitioning through either
    658 ;;    DELETED1 or DELETED2 state).
     661;;    DELETING1 or DELETING2 state).
    659662;; * rehash: grab a lock, estimate number of entries, make a new vector.  loop over
    660663;; old vector, at each entry fetch the old value with atomic swap of
     
    705708         (grow-threshold (nhash.grow-threshold hash))
    706709         count new-vector vector-size)
    707     ;; Prevent puthash from adding new entries.  Note this doesn't keep it from undeleting
    708     ;; existing entries, so we might still lose, but this makes the odds much smaller.
     710    ;; Prevent puthash from adding new entries.
    709711    (setf (nhash.grow-threshold hash) 0)
    710712    (setq count (lock-free-count-entries hash))
     
    714716        (compute-hash-size count 1 (nhash.rehash-ratio hash))))
    715717    (setq new-vector (%cons-nhash-vector vector-size inherited-flags))
    716     (loop with full-count = grow-threshold
     718    (loop ;; with full-count = grow-threshold
    717719          for i from $nhash.vector_overhead below (uvsize old-vector) by 2
    718720          do (let* ((value (atomic-swap-gvector (%i+ i 1) old-vector rehashing-value-marker))
     
    728730                   (decf grow-threshold)
    729731                   (when (%i<= grow-threshold 0)
     732                     (error "Bug: undeleted entries?")
     733                     #+obsolete ;; we no longer undelete entries
    730734                     ;; Too many entries got undeleted while we were rehashing (that's the
    731735                     ;; only way we could end up with more than COUNT entries, as adding
     
    769773      (setq vector-index (+ vector-index 2))
    770774      (unless (%already-rehashed-p index rehash-bits)
    771         (let* ((value (%svref vector (%i+ vector-index 1)))
    772                (key (%svref vector vector-index)))
    773           (if (or (eq value free-hash-marker)
    774                   (eq value deleted-hash-value-marker)
    775                   (eq key deleted-hash-key-marker))
    776             (unless (eq key free-hash-marker)
    777               (setf (%svref vector vector-index) free-hash-marker))
     775        (let* ((key (%svref vector vector-index)))
     776          (if (or (eq key free-hash-marker) (eq key deleted-hash-key-marker))
     777            (unless (eq key free-hash-marker)
     778              (setf (%svref vector vector-index) free-hash-marker
     779                    (%svref vector (%i+ vector-index 1)) free-hash-marker))
    778780            (let* ((last-index index)
     781                   (value (%svref vector (%i+ vector-index 1)))
    779782                   (first t))
    780783              (loop
     
    793796                    (%set-hash-table-vector-key vector found-vector-index key)
    794797                    (setf (%svref vector (the fixnum (1+ found-vector-index))) value)
    795                     (when (or (eq newkey deleted-hash-key-marker)
    796                               (eq newvalue free-hash-marker)
    797                               (eq newvalue deleted-hash-value-marker))
     798                    (when (or (eq newkey deleted-hash-key-marker) (eq newkey free-hash-marker))
    798799                      (return))
    799800                    (when (eq key newkey)
     
    883884    (signal-read-only-hash-table-error hash)) ;;continuable
    884885  (loop
    885     (let* ((vector (nhash.vector  hash))
     886    (let* ((vector (nhash.vector hash))
     887           (address (strip-tag-to-fixnum key))
     888           ;; This also makes sure the vector's track_keys bit is set if key is address based (in an eq table),
     889           ;; and component_address bit is set if a key component is address based (in an equal[p] table).
    886890           (vector-index (funcall (nhash.find-new hash) hash key)))
    887891      ;; Need to punt if vector changed because no way to know whether nhash.find-new was
     
    900904                 (atomic-decf (nhash.grow-threshold hash))
    901905                 (when (set-hash-key-conditional vector-index vector free-hash-marker key)
    902                    (when (set-hash-value-conditional vector-index vector free-hash-marker value)
    903                      (return-from lock-free-puthash value)))))
     906                   ;; %needs-rehashing-p is not equite enough in the track_keys case, since gc cannot
     907                   ;; track this key until it's actually added to the table.  Check now.
     908                   (if (and (%ilogbitp $nhash_track_keys_bit (nhash.vector.flags vector))
     909                            (not (eq address (strip-tag-to-fixnum key))))
     910                     (setf (%svref vector vector-index) deleted-hash-key-marker)                       ;; Back out and try again.
     911                     (when (set-hash-value-conditional vector-index vector free-hash-marker value)
     912                       (return-from lock-free-puthash value))))))
    904913              (t (let ((old-value (%svref vector (%i+ vector-index 1))))
    905914                   (unless (or (eq old-value rehashing-value-marker)
Note: See TracChangeset for help on using the changeset viewer.