Changeset 10814


Ignore:
Timestamp:
Sep 20, 2008, 11:34:59 PM (11 years ago)
Author:
gz
Message:

Propagate r10813 to trunk

Location:
trunk/source
Files:
5 edited

Legend:

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

    r10812 r10814  
    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))
     
    578583;; http://blogs.azulsystems.com/cliff/2007/03/a_nonblocking_h.html.
    579584;;
    580 ;; The modifications have to do with the fact that the goal of the current implementation
    581 ;; is to have thread-safe hash tables with minimal performance penalty on reads, so I don't
    582 ;; bother with aspects of his algorithm that aren't relevant to that goal.
     585;; The modifications have to do with the fact that our goal is just to minimize the
     586;; performance impact of thread-safety, by eliminating the need for locking on every
     587;; read.  I don't bother with aspects of his algorithm that aren't relevant to that goal.
    583588;;
    584589;; The main difference from Click's algorithm is that I don't try to do rehashing
     
    592597;;
    593598;; State      Key               Value
    594 ;; DELETED    object            free-hash-marker
     599;; DELETED1   object            free-hash-marker
     600;; DELETED2   deleted-marker    free-hash-marker
    595601;; IN-USE     object            object
    596602;; FREE       free-hash-marker  free-hash-marker
    597603;; REHASHING  object            rehashing-value-marker
    598604;; REHASHING  free-hash-marker  rehashing-value-marker
     605;; REHASHING  deleted-marker    rehashing-value-marker
    599606;;
    600607;; No other states are allowed - at no point in time can a hash table entry be in any
    601 ;; other state.   In addition, the only transition allowed on the Key slot is
    602 ;; free-hash-marker -> object.  Once a key slot is so claimed, it must never change
    603 ;; again (even after the hash vector has been discarded after rehashing, because
    604 ;; there can be some process still looking at it).
     608;; other state.   In addition, the only transitions allowed on the key slot are
     609;; free-hash-marker -> object/deleted-marker -> deleted-marker.  Once a key slot
     610;; is claimed, it must never change to free or another key value (even after the hash
     611;; vector has been discarded after rehashing, because there some process might still
     612;; be looking at it).
    605613;; In particular, rehashing in place is not an option.  All rehashing creates a new
    606614;; vector and copies into it.  This means it's kinda risky to use lock-free hash
    607615;; tables with address-based keys, because they will thrash in low-memory situations,
    608616;; but we don't disallow it because a particular use might not have this problem.
     617;;
     618;; The following operations may take place:
     619;;
     620;; * gethash: find matching key - if no match, return not found.  Else fetch value,
     621;;   if value is rehashing-value-marker then maybe-rehash and try again;
     622;;   if value is free-hash-marker, return not found, else return found value.
     623;;
     624;; * puthash: find matching key or FREE slot.
     625;;   ** If found key, fetch value.
     626;;      if value is rehashing-value-marker then maybe-rehash and try again;
     627;;      else store-conditional the value -> new value, if fails try again.
     628;;   ** Else have FREE slot, store-key-conditional free-hash-marker -> key,
     629;;      and if that succeeds, store-conditional free-hash-marker -> new value,
     630;;      if either fails, maybe-rehash and try again.
     631;;
     632;; * remhash: find matching key - if no match, done.  Else fetch value,
     633;;   if value is rehashing-value-marker then maybe-rehash and try again;
     634;;   else store-conditional the value -> free-hash-marker, if fails try again.
     635;;
     636;; * rehash: grab a lock, estimate number of entries, make a new vector.  loop over
     637;; old vector, at each entry fetch the old value with atomic swap of
     638;; rehashing-value-marker.  This prevents any further state changes involving the
     639;; value.  It doesn't prevent state changes involving the key, but the only ones that
     640;; can happen is FREE -> DELETED, and DELETED1 <-> DELETED2, all of which are
     641;; equivalent from the point of view of rehashing.  Anyway, if the old value was
     642;; rehashing-value-marker then bug (because we have a lock).  If the old value is
     643;; free-hash-marker then do nothing, else get the entry key and rehash into the new
     644;; vector -- if no more room, start over.  When done, store the new vector in the
     645;; hash table and release lock.
     646;;
     647;; * gc: for weak tables, gc may convert IN-USE states to DELETED2 states.
     648;;   Even for non-weak tables, gc could convert DELETED1 states to DELETED2.
    609649
    610650
     
    714754                       (return-from lock-free-remhash nil))
    715755                     (when (set-hash-value-conditional vector-index vector old-value free-hash-marker)
     756                       ;; We just use this as a flag - tell gc to scan the vector for deleted keys.
     757                       ;; It's just a hint, so don't worry about sync'ing
     758                       (setf (nhash.vector.deleted-count vector) 1)
    716759                       (return-from lock-free-remhash t)))))))
    717760      ;; We're here because the table needs rehashing or it was getting rehashed while we
     
    727770         with vector = (nhash.vector hash)
    728771         for i1 fixnum from (%i+ $nhash.vector_overhead 1) below (uvsize vector) by 2
    729          do (setf (%svref vector i1) free-hash-marker))
     772         do (setf (%svref vector i1) free-hash-marker)
     773         ;; We just use this as a flag - tell gc to scan the vector for deleted keys.
     774         ;; It's just a hint, so don't worry about sync'ing
     775         finally (setf (nhash.vector.deleted-count vector) 1))
    730776       (%unlock-recursive-lock-object lock))))
    731777  hash)
     
    10981144
    10991145(defun general-hash-find-for-put (hash key)
    1100   (%hash-probe hash key t))
     1146  (%hash-probe hash key (if (hash-lock-free-p hash) :free :reuse)))
    11011147
    11021148;;; returns a single value:
     
    11311177                                              -1)))
    11321178                                ((eq table-key deleted-hash-key-marker)
    1133                                  (when (null first-deleted-index)
     1179                                 (when (and (eq for-put-p :reuse)
     1180                                            (null first-deleted-index))
    11341181                                   (setq first-deleted-index vector-index)))
    11351182                                ((,@predicate key table-key)
     
    11491196                                  (return-it (if for-put-p
    11501197                                               (or first-deleted-index
    1151                                                    (error "Bug: no deleted entries in table"))
     1198                                                   (error "Bug: no room in table"))
    11521199                                               -1)))
    11531200                                (test-it ,predicate))))))
     
    12181265                  (progn
    12191266                    (unless (immediate-p-macro key)
    1220                       (let* ((flags (nhash.vector.flags vector)))
    1221                         (declare (fixum flags))
    1222                         (unless (logbitp $nhash_track_keys_bit flags)
    1223                           (setq flags (bitclr $nhash_key_moved_bit flags)))
    1224                         (setf (nhash.vector.flags vector)
    1225                               (logior $nhash-track-keys-mask flags))))
     1267                      (update-hash-flags hash vector :key))
    12261268                    (mixup-hash-code (strip-tag-to-fixnum key))))))))
    12271269         (entries (nhash.vector-size vector))
    12281270         (vector-index (index->vector-index (hash-mod hash-code entries vector)))
    1229          (table-key (%svref vector vector-index)))
     1271         (table-key (%svref vector vector-index))
     1272         (reuse (not (hash-lock-free-p hash))))
    12301273    (declare (fixnum hash-code vector-index))
    12311274    (if (or (eq key table-key)
     
    12351278                                     (logand 7 hash-code)))
    12361279             (initial-index vector-index)             
    1237              (first-deleted-index (if (eq table-key deleted-hash-key-marker)
    1238                                     vector-index))
     1280             (first-deleted-index (and reuse
     1281                                       (eq table-key deleted-hash-key-marker)
     1282                                       vector-index))
    12391283             (count (+ entries entries))
    12401284             (length (+ count $nhash.vector_overhead)))
     
    12471291          (when (= vector-index initial-index)
    12481292            (return (or first-deleted-index
    1249                         (error "Bug: no deleted entries in table"))))
     1293                        (error "Bug: no room in table"))))
    12501294          (if (eq table-key key)
    12511295            (return vector-index)
    12521296            (if (eq table-key free-hash-marker)
    12531297              (return (or first-deleted-index vector-index))
    1254               (if (and (null first-deleted-index)
     1298              (if (and reuse
     1299                       (null first-deleted-index)
    12551300                       (eq table-key deleted-hash-key-marker))
    12561301                (setq first-deleted-index vector-index)))))))))
     
    12951340           (entries (nhash.vector-size vector))
    12961341           (vector-index (index->vector-index (hash-mod hash-code entries vector)))
    1297            (table-key (%svref vector vector-index)))
     1342           (table-key (%svref vector vector-index))
     1343           (reuse (not (hash-lock-free-p hash))))
    12981344      (declare (fixnum hash-code entries vector-index))
    12991345      (if (or (eql key table-key)
     
    13031349                                       (logand 7 hash-code)))
    13041350               (initial-index vector-index)
    1305                (first-deleted-index (if (eq table-key deleted-hash-key-marker)
    1306                                       vector-index))
     1351               (first-deleted-index (and reuse
     1352                                         (eq table-key deleted-hash-key-marker)
     1353                                         vector-index))
    13071354               (count (+ entries entries))
    13081355               (length (+ count $nhash.vector_overhead)))
     
    13151362            (when (= vector-index initial-index)
    13161363              (return (or first-deleted-index
    1317                           (error "Bug: no deleted entries in table"))))
     1364                          (error "Bug: no room in table"))))
    13181365            (if (eql table-key key)
    13191366              (return vector-index)
    13201367              (if (eq table-key free-hash-marker)
    13211368                (return (or first-deleted-index vector-index))
    1322                 (if (and (null first-deleted-index)
     1369                (if (and reuse
     1370                         (null first-deleted-index)
    13231371                         (eq table-key deleted-hash-key-marker))
    13241372                  (setq first-deleted-index vector-index))))))))
     
    13371385;;; and have disabled interrupts.
    13381386(defun %rehash (hash)
     1387  (when (hash-lock-free-p hash)
     1388    (error "How did we get here?"))
    13391389  (let* ((vector (nhash.vector hash))
    13401390         (flags (nhash.vector.flags vector))
     
    18331883                         (lock-free-enumerate-hash-keys-and-values hash keys values)))
    18341884          (unless (eq val free-hash-marker)
     1885            (when (eql key deleted-hash-key-marker)
     1886              (error "Bug: deleted key but not value?"))
    18351887            (when keys (setf (%svref keys out-idx) key))
    18361888            (when values (setf (%svref values out-idx) val))
  • trunk/source/lib/hash.lisp

    r10731 r10814  
    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;;
  • trunk/source/lisp-kernel/gc-common.c

    r10806 r10814  
    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        }
  • trunk/source/lisp-kernel/x86-gc.c

    r10808 r10814  
    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) {
  • trunk/source/xdump/hashenv.lisp

    r10731 r10814  
    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.