Changeset 10813


Ignore:
Timestamp:
Sep 20, 2008, 9:25:13 PM (11 years ago)
Author:
gz
Message:

Plan B: extend the lock-free states to allow key to be deleted-marker. Lisp can't set it to that because of locking issues, but the gc can (and in fact really really wants to, for weak-on-key tables). As long as have that, make gc clean out the keys in general, not just for weak tables. Use nhash.vector.deleted-count as a hint as to whether it should bother.

Reenable lock-free weak hash tables again as this fixes the problem.

Also, make eq-hash-find-for-put update flags atomically in lock-free case.

Location:
branches/working-0711/ccl
Files:
5 edited

Legend:

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

    r10809 r10813  
    282282                (t (%%eqlhash key)))))))
    283283
     284(defun update-hash-flags (hash vector addressp)
     285  (when addressp
     286    (flet ((new-flags (flags addressp)
     287             (declare (fixnum flags))
     288             (if (eq :key addressp)
     289               ;; hash code depended on key's address
     290               (if (logbitp $nhash_component_address_bit flags)
     291                 flags
     292                 (logior $nhash-track-keys-mask
     293                         (if (logbitp $nhash_track_keys_bit flags)
     294                           flags
     295                           (bitclr $nhash_key_moved_bit flags))))
     296               ;; hash code depended on component address
     297               (bitset $nhash_component_address_bit
     298                       (logand (lognot $nhash-track-keys-mask) flags)))))
     299      (declare (inline new-flags))
     300      (if (hash-lock-free-p hash)
     301        (loop
     302          (let* ((flags (nhash.vector.flags vector))
     303                 (new-flags (new-flags flags addressp)))
     304            (when (or (eq flags new-flags)
     305                      (store-gvector-conditional nhash.vector.flags vector flags new-flags))
     306              (return))))
     307        (setf (nhash.vector.flags vector)
     308              (new-flags (nhash.vector.flags vector) addressp))))))
     309
    284310(defun compute-hash-code (hash key update-hash-flags &optional
    285311                               (vector (nhash.vector hash))) ; vectorp))
     
    302328        ;; EQ hash table - or something eql doesn't do
    303329        (multiple-value-setq (primary addressp) (%%eqhash key))))
    304     (when addressp
    305       (when update-hash-flags
    306         (flet ((new-flags (flags addressp)
    307                  (declare (fixnum flags))
    308                  (if (eq :key addressp)
    309                    ;; hash code depended on key's address
    310                    (if (logbitp $nhash_component_address_bit flags)
    311                      flags
    312                      (logior $nhash-track-keys-mask
    313                              (if (logbitp $nhash_track_keys_bit flags)
    314                                flags
    315                                (bitclr $nhash_key_moved_bit flags))))
    316                    ;; hash code depended on component address
    317                    (bitset $nhash_component_address_bit
    318                            (logand (lognot $nhash-track-keys-mask) flags)))))
    319           (declare (inline new-flags))
    320           (if (hash-lock-free-p hash)
    321             (loop
    322                 (let* ((flags (nhash.vector.flags vector))
    323                        (new-flags (new-flags flags addressp)))
    324                   (when (or (eq flags new-flags)
    325                             (store-gvector-conditional nhash.vector.flags vector flags new-flags))
    326                     (return))))
    327             (setf (nhash.vector.flags vector) (new-flags (nhash.vector.flags vector) addressp))))))
     330    (when update-hash-flags
     331      (when addressp
     332        (update-hash-flags hash vector addressp)))
    328333    (let* ((entries (nhash.vector-size vector)))
    329334      (declare (fixnum entries))
     
    438443    (when (and finalizeable (not weak))
    439444      (error "Only weak hash tables can be finalizeable."))
    440     ;; ** Temporary - there is some kind of a memory corruption
    441     ;; bug that seems to happen with a combination of weak and
    442     ;; lock-free table, so disable until can track this down.
    443     (when weak
    444       (setq lock-free nil))
    445445    (multiple-value-bind (grow-threshold total-size)
    446446        (compute-hash-size (1- size) 1 rehash-threshold)
     
    585585;; http://blogs.azulsystems.com/cliff/2007/03/a_nonblocking_h.html.
    586586;;
    587 ;; The modifications have to do with the fact that the goal of the current implementation
    588 ;; is to have thread-safe hash tables with minimal performance penalty on reads, so I don't
    589 ;; bother with aspects of his algorithm that aren't relevant to that goal.
     587;; The modifications have to do with the fact that our goal is just to minimize the
     588;; performance impact of thread-safety, by eliminating the need for locking on every
     589;; read.  I don't bother with aspects of his algorithm that aren't relevant to that goal.
    590590;;
    591591;; The main difference from Click's algorithm is that I don't try to do rehashing
     
    599599;;
    600600;; State      Key               Value
    601 ;; DELETED    object            free-hash-marker
     601;; DELETED1   object            free-hash-marker
     602;; DELETED2   deleted-marker    free-hash-marker
    602603;; IN-USE     object            object
    603604;; FREE       free-hash-marker  free-hash-marker
    604605;; REHASHING  object            rehashing-value-marker
    605606;; REHASHING  free-hash-marker  rehashing-value-marker
     607;; REHASHING  deleted-marker    rehashing-value-marker
    606608;;
    607609;; No other states are allowed - at no point in time can a hash table entry be in any
    608 ;; other state.   In addition, the only transition allowed on the Key slot is
    609 ;; free-hash-marker -> object.  Once a key slot is so claimed, it must never change
    610 ;; again (even after the hash vector has been discarded after rehashing, because
    611 ;; there can be some process still looking at it).
     610;; other state.   In addition, the only transitions allowed on the key slot are
     611;; free-hash-marker -> object/deleted-marker -> deleted-marker.  Once a key slot
     612;; is claimed, it must never change to free or another key value (even after the hash
     613;; vector has been discarded after rehashing, because there some process might still
     614;; be looking at it).
    612615;; In particular, rehashing in place is not an option.  All rehashing creates a new
    613616;; vector and copies into it.  This means it's kinda risky to use lock-free hash
    614617;; tables with address-based keys, because they will thrash in low-memory situations,
    615618;; but we don't disallow it because a particular use might not have this problem.
     619;;
     620;; The following operations may take place:
     621;;
     622;; * gethash: find matching key - if no match, return not found.  Else fetch value,
     623;;   if value is rehashing-value-marker then maybe-rehash and try again;
     624;;   if value is free-hash-marker, return not found, else return found value.
     625;;
     626;; * puthash: find matching key or FREE slot.
     627;;   ** If found key, fetch value.
     628;;      if value is rehashing-value-marker then maybe-rehash and try again;
     629;;      else store-conditional the value -> new value, if fails try again.
     630;;   ** Else have FREE slot, store-key-conditional free-hash-marker -> key,
     631;;      and if that succeeds, store-conditional free-hash-marker -> new value,
     632;;      if either fails, maybe-rehash and try again.
     633;;
     634;; * remhash: find matching key - if no match, done.  Else fetch value,
     635;;   if value is rehashing-value-marker then maybe-rehash and try again;
     636;;   else store-conditional the value -> free-hash-marker, if fails try again.
     637;;
     638;; * rehash: grab a lock, estimate number of entries, make a new vector.  loop over
     639;; old vector, at each entry fetch the old value with atomic swap of
     640;; rehashing-value-marker.  This prevents any further state changes involving the
     641;; value.  It doesn't prevent state changes involving the key, but the only ones that
     642;; can happen is FREE -> DELETED, and DELETED1 <-> DELETED2, all of which are
     643;; equivalent from the point of view of rehashing.  Anyway, if the old value was
     644;; rehashing-value-marker then bug (because we have a lock).  If the old value is
     645;; free-hash-marker then do nothing, else get the entry key and rehash into the new
     646;; vector -- if no more room, start over.  When done, store the new vector in the
     647;; hash table and release lock.
     648;;
     649;; * gc: for weak tables, gc may convert IN-USE states to DELETED2 states.
     650;;   Even for non-weak tables, gc could convert DELETED1 states to DELETED2.
    616651
    617652
     
    723758                       (return-from lock-free-remhash nil))
    724759                     (when (set-hash-value-conditional vector-index vector old-value free-hash-marker)
     760                       ;; We just use this as a flag - tell gc to scan the vector for deleted keys.
     761                       ;; It's just a hint, so don't worry about sync'ing
     762                       (setf (nhash.vector.deleted-count vector) 1)
    725763                       (return-from lock-free-remhash t)))))))
    726764      ;; We're here because the table needs rehashing or it was getting rehashed while we
     
    738776         with vector = (nhash.vector hash)
    739777         for i1 fixnum from (%i+ $nhash.vector_overhead 1) below (uvsize vector) by 2
    740          do (setf (%svref vector i1) free-hash-marker))
     778         do (setf (%svref vector i1) free-hash-marker)
     779         ;; We just use this as a flag - tell gc to scan the vector for deleted keys.
     780         ;; It's just a hint, so don't worry about sync'ing
     781         finally (setf (nhash.vector.deleted-count vector) 1))
    741782       (%unlock-recursive-lock-object lock))))
    742783  hash)
     
    11111152
    11121153(defun general-hash-find-for-put (hash key)
    1113   (%hash-probe hash key t))
     1154  (%hash-probe hash key (if (hash-lock-free-p hash) :free :reuse)))
    11141155
    11151156;;; returns a single value:
     
    11441185                                              -1)))
    11451186                                ((eq table-key deleted-hash-key-marker)
    1146                                  (when (null first-deleted-index)
     1187                                 (when (and (eq for-put-p :reuse)
     1188                                            (null first-deleted-index))
    11471189                                   (setq first-deleted-index vector-index)))
    11481190                                ((,@predicate key table-key)
     
    11621204                                  (return-it (if for-put-p
    11631205                                               (or first-deleted-index
    1164                                                    (error "Bug: no deleted entries in table"))
     1206                                                   (error "Bug: no room in table"))
    11651207                                               -1)))
    11661208                                (test-it ,predicate))))))
     
    12311273                  (progn
    12321274                    (unless (immediate-p-macro key)
    1233                       (let* ((flags (nhash.vector.flags vector)))
    1234                         (declare (fixum flags))
    1235                         (unless (logbitp $nhash_track_keys_bit flags)
    1236                           (setq flags (bitclr $nhash_key_moved_bit flags)))
    1237                         (setf (nhash.vector.flags vector)
    1238                               (logior $nhash-track-keys-mask flags))))
     1275                      (update-hash-flags hash vector :key))
    12391276                    (mixup-hash-code (strip-tag-to-fixnum key))))))))
    12401277         (entries (nhash.vector-size vector))
    12411278         (vector-index (index->vector-index (hash-mod hash-code entries vector)))
    1242          (table-key (%svref vector vector-index)))
     1279         (table-key (%svref vector vector-index))
     1280         (reuse (not (hash-lock-free-p hash))))
    12431281    (declare (fixnum hash-code vector-index))
    12441282    (if (or (eq key table-key)
     
    12481286                                     (logand 7 hash-code)))
    12491287             (initial-index vector-index)             
    1250              (first-deleted-index (if (eq table-key deleted-hash-key-marker)
    1251                                     vector-index))
     1288             (first-deleted-index (and reuse
     1289                                       (eq table-key deleted-hash-key-marker)
     1290                                       vector-index))
    12521291             (count (+ entries entries))
    12531292             (length (+ count $nhash.vector_overhead)))
     
    12601299          (when (= vector-index initial-index)
    12611300            (return (or first-deleted-index
    1262                         (error "Bug: no deleted entries in table"))))
     1301                        (error "Bug: no room in table"))))
    12631302          (if (eq table-key key)
    12641303            (return vector-index)
    12651304            (if (eq table-key free-hash-marker)
    12661305              (return (or first-deleted-index vector-index))
    1267               (if (and (null first-deleted-index)
     1306              (if (and reuse
     1307                       (null first-deleted-index)
    12681308                       (eq table-key deleted-hash-key-marker))
    12691309                (setq first-deleted-index vector-index)))))))))
     
    13081348           (entries (nhash.vector-size vector))
    13091349           (vector-index (index->vector-index (hash-mod hash-code entries vector)))
    1310            (table-key (%svref vector vector-index)))
     1350           (table-key (%svref vector vector-index))
     1351           (reuse (not (hash-lock-free-p hash))))
    13111352      (declare (fixnum hash-code entries vector-index))
    13121353      (if (or (eql key table-key)
     
    13161357                                       (logand 7 hash-code)))
    13171358               (initial-index vector-index)
    1318                (first-deleted-index (if (eq table-key deleted-hash-key-marker)
    1319                                       vector-index))
     1359               (first-deleted-index (and reuse
     1360                                         (eq table-key deleted-hash-key-marker)
     1361                                         vector-index))
    13201362               (count (+ entries entries))
    13211363               (length (+ count $nhash.vector_overhead)))
     
    13281370            (when (= vector-index initial-index)
    13291371              (return (or first-deleted-index
    1330                           (error "Bug: no deleted entries in table"))))
     1372                          (error "Bug: no room in table"))))
    13311373            (if (eql table-key key)
    13321374              (return vector-index)
    13331375              (if (eq table-key free-hash-marker)
    13341376                (return (or first-deleted-index vector-index))
    1335                 (if (and (null first-deleted-index)
     1377                (if (and reuse
     1378                         (null first-deleted-index)
    13361379                         (eq table-key deleted-hash-key-marker))
    13371380                  (setq first-deleted-index vector-index))))))))
     
    13501393;;; and have disabled interrupts.
    13511394(defun %rehash (hash)
     1395  (when (hash-lock-free-p hash)
     1396    (error "How did we get here?"))
    13521397  (let* ((vector (nhash.vector hash))
    13531398         (flags (nhash.vector.flags vector))
     
    18481893                         (lock-free-enumerate-hash-keys-and-values hash keys values)))
    18491894          (unless (eq val free-hash-marker)
     1895            (when (eql key deleted-hash-key-marker)
     1896              (error "Bug: deleted key but not value?"))
    18501897            (when keys (setf (%svref keys out-idx) key))
    18511898            (when values (setf (%svref values out-idx) val))
  • branches/working-0711/ccl/lib/hash.lisp

    r10776 r10813  
    107107;; question are at offsets $nhash.vector-weak-byte and
    108108;; $nhash.vector-track-keys-byte offsets from the tagged vector.
    109 ;; The 32 bits of the fixnum at nhash.vector.flags look like:
    110 ;;
    111 ;;     TTTTKEC0 00000000 000WVFZ0 00000000
     109;; The raw 32 bits of the fixnum at nhash.vector.flags look like:
     110;;
     111;;     TKEC0000 00000000 WVFZ0000 00000000
    112112;;
    113113;;
  • branches/working-0711/ccl/lisp-kernel/gc-common.c

    r10776 r10813  
    234234      if ((dnode < GCndnodes_in_area) &&
    235235          ! ref_bit(markbits, dnode)) {
     236        pairp[0] = slot_unbound;
    236237        if (keys_frozen) {
    237238          if (pairp[1] != slot_unbound) {
     
    240241        }
    241242        else {
    242           pairp[0] = slot_unbound;
    243243          pairp[1] = lisp_nil;
    244244        }
  • branches/working-0711/ccl/lisp-kernel/x86-gc.c

    r10389 r10813  
    387387           that rehashing is necessary. */
    388388        LispObj flags = ((hash_table_vector_header *) base)->flags;
     389
     390        if ((flags & nhash_keys_frozen_mask) &&
     391            (((hash_table_vector_header *) base)->deleted_count > 0)) {
     392          /* We're responsible for clearing out any deleted keys, since
     393             lisp side can't do it without breaking the state machine
     394          */
     395          LispObj *pairp = base + hash_table_vector_header_count;
     396          natural
     397            npairs = (element_count - (hash_table_vector_header_count - 1)) >> 1;
     398
     399          while (npairs--) {
     400            if ((pairp[1] == unbound) && (pairp[0] != unbound)) {
     401              pairp[0] = slot_unbound;
     402            }
     403            pairp +=2;
     404          }
     405          ((hash_table_vector_header *) base)->deleted_count = 0;
     406        }
    389407
    390408        if (flags & nhash_weak_mask) {
  • branches/working-0711/ccl/xdump/hashenv.lisp

    r10776 r10813  
    3838  nhash.vector.weak-deletions-count     ; incremented when the GC deletes an element
    3939  nhash.vector.hash                     ; back-pointer
    40   nhash.vector.deleted-count            ; number of deleted entries [not maintained if lock-free]
     40  nhash.vector.deleted-count            ; if lock-free, hint to GC to delete marked keys.
     41                                        ; else number of deleted entries
    4142  nhash.vector.count                    ; number of valid entries [not maintained if lock-free]
    4243  nhash.vector.cache-idx                ; index of last cached key/value pair
Note: See TracChangeset for help on using the changeset viewer.