Changeset 15504


Ignore:
Timestamp:
Nov 28, 2012, 6:44:49 PM (7 years ago)
Author:
gz
Message:

Fix lock-free hash table handling of the partially-inserted state, and took out gc handling of the partially-deleted state. Bumped image version because kernel and runtime changes need to match. This fixes ticket #993, hopefully without breaking much of anything else.

Location:
trunk/source
Files:
15 edited

Legend:

Unmodified
Added
Removed
  • trunk/source/compiler/ARM/arm-arch.lisp

    r15425 r15504  
    14201420(defconstant fasl-max-version #x62)
    14211421(defconstant fasl-min-version #x62)
    1422 (defparameter *image-abi-version* 1040)
     1422(defparameter *image-abi-version* 1041)
    14231423
    14241424(provide "ARM-ARCH")
  • trunk/source/compiler/PPC/PPC32/ppc32-arch.lisp

    r15191 r15504  
    946946(defconstant fasl-max-version #x5f)
    947947(defconstant fasl-min-version #x5e)
    948 (defparameter *image-abi-version* 1037)
     948(defparameter *image-abi-version* 1038)
    949949
    950950(provide "PPC32-ARCH")
  • trunk/source/compiler/PPC/PPC64/ppc64-arch.lisp

    r15191 r15504  
    10141014(defconstant fasl-max-version #x5f)
    10151015(defconstant fasl-min-version #x5e)
    1016 (defparameter *image-abi-version* 1037)
     1016(defparameter *image-abi-version* 1038)
    10171017
    10181018(provide "PPC64-ARCH")
  • trunk/source/compiler/X86/X8632/x8632-arch.lisp

    r15191 r15504  
    13401340(defconstant fasl-max-version #x5f)
    13411341(defconstant fasl-min-version #x5e)
    1342 (defparameter *image-abi-version* 1037)
     1342(defparameter *image-abi-version* 1038)
    13431343
    13441344(provide "X8632-ARCH")
  • trunk/source/compiler/X86/X8664/x8664-arch.lisp

    r15191 r15504  
    13551355(defconstant fasl-max-version #x5f)
    13561356(defconstant fasl-min-version #x5e)
    1357 (defparameter *image-abi-version* 1037)
     1357(defparameter *image-abi-version* 1038)
    13581358
    13591359(provide "X8664-ARCH")
  • trunk/source/level-0/l0-hash.lisp

    r15459 r15504  
    2626  (require "HASHENV" "ccl:xdump;hashenv")
    2727  (require :number-case-macro)
     28  (assert (and (not (eql (%unbound-marker) (%slot-unbound-marker)))
     29               (not (eql (%unbound-marker) (%illegal-marker)))
     30               (not (eql (%slot-unbound-marker) (%illegal-marker)))))
    2831  (define-symbol-macro deleted-hash-key-marker (%slot-unbound-marker))
     32  (define-symbol-macro deleted-hash-value-marker (%slot-unbound-marker))
    2933  (define-symbol-macro free-hash-marker (%unbound-marker))
    30   (define-symbol-macro rehashing-value-marker (%slot-unbound-marker))
     34  (define-symbol-macro rehashing-value-marker (%illegal-marker))
    3135  (declaim (inline nhash.vector-size))
    3236  (declaim (inline mixup-hash-code))
     
    609613;; to finish.
    610614;;
    611 ;; In addition, I don't have a separate state for partially inserted key, I reuse the
    612 ;; DELETED state for that.  So in our implementation the following are the possible states
    613 ;; of a hash table entry (where "object" means any object other than the special markers):
     615;; In our implementation the following are the possible states of a hash table entry:
     616;;   (where "object" means any object other than the special markers):
    614617;;
    615618;; State      Key               Value
    616 ;; DELETED1   object            free-hash-marker
    617 ;; DELETED2   deleted-marker    free-hash-marker
     619;; FREE       free-hash-marker  free-hash-marker
     620;; INSERTING  object            free-hash-marker
    618621;; IN-USE     object            object
    619 ;; FREE       free-hash-marker  free-hash-marker
     622;; DELETING1  object            deleted-marker
     623;; DELETING2  deleted-marker    object
     624;; DELETED    deleted-marker    deleted-marker
    620625;; REHASHING  object            rehashing-value-marker
    621626;; REHASHING  free-hash-marker  rehashing-value-marker
     
    626631;; free-hash-marker -> object/deleted-marker -> deleted-marker.  Once a key slot
    627632;; is claimed, it must never change to free or another key value (even after the hash
    628 ;; vector has been discarded after rehashing, because there some process might still
    629 ;; be looking at it).
     633;; vector has been discarded after rehashing, because some process might still be
     634;; looking at it).
    630635;; In particular, rehashing in place is not an option.  All rehashing creates a new
    631636;; vector and copies into it.  This means it's kinda risky to use lock-free hash
     
    637642;; * gethash: find matching key - if no match, return not found.  Else fetch value,
    638643;;   if value is rehashing-value-marker then maybe-rehash and try again;
    639 ;;   if value is free-hash-marker, return not found, else return found value.
    640 ;;
     644;;   if value is free-hash-marker or deleted-marker, return not found, else return found value.
    641645;; * puthash: find matching key or FREE slot.
    642646;;   ** If found key, fetch value.
     
    646650;;      and if that succeeds, store-conditional free-hash-marker -> new value,
    647651;;      if either fails, maybe-rehash and try again.
    648 ;;
    649652;; * remhash: find matching key - if no match, done.  Else fetch value,
    650653;;   if value is rehashing-value-marker then maybe-rehash and try again;
    651 ;;   else store-conditional the value -> free-hash-marker, if fails try again.
    652 ;;
     654;;   if value is free-hash-marker or deleted-marker, done.
     655;;   else store-conditional the value -> deleted-marker, if fails try again.
     656;;    if succeeds, clobber key with deleted-marker to allow it to get gc'd.
     657;; * clrhash: grab the rehash lock, then set all slots to DELETED (transitioning through either
     658;;    DELETED1 or DELETED2 state).
    653659;; * rehash: grab a lock, estimate number of entries, make a new vector.  loop over
    654660;; old vector, at each entry fetch the old value with atomic swap of
    655661;; rehashing-value-marker.  This prevents any further state changes involving the
    656662;; value.  It doesn't prevent state changes involving the key, but the only ones that
    657 ;; can happen is FREE -> DELETED, and DELETED1 <-> DELETED2, all of which are
     663;; can happen is FREE -> INSERTING, and DELETINGn -> DELETED, all of which are
    658664;; equivalent from the point of view of rehashing.  Anyway, if the old value was
    659665;; rehashing-value-marker then bug (because we have a lock).  If the old value is
    660 ;; free-hash-marker then do nothing, else get the entry key and rehash into the new
    661 ;; vector -- if no more room, start over.  When done, store the new vector in the
    662 ;; hash table and release lock.
     666;; free-hash-marker or deleted-marker then do nothing, else get the entry key and
     667;; rehash into the new vector -- if no more room, start over.  When done, store the
     668;; new vector in the hash table and release lock.
    663669;;
    664 ;; * gc: for weak tables, gc may convert IN-USE states to DELETED2 states.
    665 ;;   Even for non-weak tables, gc could convert DELETED1 states to DELETED2.
     670;; * gc: for weak tables, gc may convert IN-USE states to DELETED states.
    666671
    667672
     
    714719                    (key (%svref old-vector i)))
    715720               (when (eq value rehashing-value-marker) (error "Who else is doing this?"))
    716                (unless (or (eq value free-hash-marker) (eq key deleted-hash-key-marker))
     721               (unless (or (eq value free-hash-marker)
     722                           (eq value deleted-hash-value-marker)
     723                           (eq key deleted-hash-key-marker))
    717724                 (let* ((new-index (%growhash-probe new-vector hash key))
    718725                        (new-vector-index (index->vector-index new-index)))
     
    765772               (key (%svref vector vector-index)))
    766773          (if (or (eq value free-hash-marker)
     774                  (eq value deleted-hash-value-marker)
    767775                  (eq key deleted-hash-key-marker))
    768776            (unless (eq key free-hash-marker)
     
    786794                    (setf (%svref vector (the fixnum (1+ found-vector-index))) value)
    787795                    (when (or (eq newkey deleted-hash-key-marker)
    788                               (eq newvalue free-hash-marker))
     796                              (eq newvalue free-hash-marker)
     797                              (eq newvalue deleted-hash-value-marker))
    789798                      (return))
    790799                    (when (eq key newkey)
     
    812821              (t (let ((value (%svref vector (%i+ vector-index 1))))
    813822                   (unless (eq value rehashing-value-marker)
    814                      (if (eq value free-hash-marker)
     823                     (if (or (eq value deleted-hash-value-marker)
     824                             (eq value free-hash-marker))
    815825                       (return-from lock-free-gethash (values default nil))
    816826                       (return-from lock-free-gethash (values value t)))))))))
     
    835845              (t (let ((old-value (%svref vector (%i+ vector-index 1))))
    836846                   (unless (eq old-value rehashing-value-marker)
    837                      (when (eq old-value free-hash-marker)
     847                     (when (or (eq old-value deleted-hash-value-marker) ;; deleted
     848                               (eq old-value free-hash-marker)) ;; or about to be added
    838849                       (return-from lock-free-remhash nil))
    839                      (when (set-hash-value-conditional vector-index vector old-value free-hash-marker)
    840                        ;; We just use this as a flag - tell gc to scan the vector for deleted keys.
    841                        ;; It's just a hint, so don't worry about sync'ing
    842                        (setf (nhash.vector.deleted-count vector) 1)
     850                     (when (set-hash-value-conditional vector-index vector old-value deleted-hash-value-marker)
     851                       ;; Clear the key slot so can be gc'd.
     852                       (setf (%svref vector vector-index) deleted-hash-key-marker)
    843853                       (return-from lock-free-remhash t)))))))
    844854      ;; We're here because the table needs rehashing or it was getting rehashed while we
     
    846856      (lock-free-rehash hash))))
    847857
     858;; TODO: might be better (faster, safer) to just create a new all-free vector?
    848859(defun lock-free-clrhash (hash)
    849860  (when (nhash.read-only hash)
     
    855866       (loop
    856867         with vector = (nhash.vector hash)
    857          for i1 fixnum from (%i+ $nhash.vector_overhead 1) below (uvsize vector) by 2
    858          do (setf (%svref vector i1) free-hash-marker)
    859          ;; We just use this as a flag - tell gc to scan the vector for deleted keys.
    860          ;; It's just a hint, so don't worry about sync'ing
    861          finally (setf (nhash.vector.deleted-count vector) 1))
     868         for i fixnum from (%i+ $nhash.vector_overhead 1) below (uvsize vector) by 2
     869         as val = (%svref vector i)
     870         unless (or (eq val free-hash-marker) (eq val deleted-hash-value-marker))
     871         do (setf (%svref vector (%i- i 1)) deleted-hash-key-marker
     872                  (%svref vector i) deleted-hash-value-marker))
    862873       (%unlock-recursive-lock-object lock))))
    863874  hash)
     
    866877  (declare (optimize (speed 3) (safety 0) (debug 0)))
    867878  (when (or (eq value rehashing-value-marker)
    868             (eq value free-hash-marker))
     879            (eq value free-hash-marker)
     880            (eq value deleted-hash-value-marker))
    869881    (error "Illegal value ~s for storing in a hash table" value))
    870882  (when (nhash.read-only hash)
     
    887899                 ;; before the incf), which _could_ be harmful.
    888900                 (atomic-decf (nhash.grow-threshold hash))
    889                  (if (set-hash-key-conditional vector-index vector free-hash-marker key)
     901                 (when (set-hash-key-conditional vector-index vector free-hash-marker key)
    890902                   (when (set-hash-value-conditional vector-index vector free-hash-marker value)
    891903                     (return-from lock-free-puthash value)))))
    892904              (t (let ((old-value (%svref vector (%i+ vector-index 1))))
    893                    (unless (eq old-value rehashing-value-marker)
     905                   (unless (or (eq old-value rehashing-value-marker)
     906                               ;; In theory, could reuse the deleted slot since we know it had this key
     907                               ;; initially, but that would complicate the state machine for very little gain.
     908                               (eq old-value deleted-hash-value-marker))
    894909                     (when (set-hash-value-conditional vector-index vector old-value value)
    895910                       (return-from lock-free-puthash value))))))))
     
    12681283                            ; First probe failed. Iterate on secondary key
    12691284                            (let ((initial-index index)
    1270                                   (secondary-hash (%svref secondary-keys (logand 7 hash-code))))
     1285                                  (secondary-hash (%svref secondary-keys (logand 7 hash-code)))
     1286                                  (DEBUG-COUNT 0))
    12711287                              (declare (fixnum secondary-hash initial-index))
    12721288                              (loop
     1289                                (INCF DEBUG-COUNT)
    12731290                                (incf index secondary-hash)
    12741291                                (when (>= index entries)
     
    12771294                                  (return-it (if for-put-p
    12781295                                               (or first-deleted-index
    1279                                                    (error "Bug: no room in table"))
     1296                                                   #+NOT-SO-HELPFUL (error "Bug: no room in table")
     1297                                                   (bug (format nil "No room in table after ~s tests, ~%initial ~s index ~s entries ~s for-put-p ~s"
     1298                                                                DEBUG-COUNT initial-index index entries for-put-p))
     1299                                                   )
    12801300                                               -1)))
    12811301                                (test-it ,predicate))))))
     
    19571977
    19581978 
    1959 ;; ** TODO: for lock-free hash tables, we don't need to copy,
     1979;; ** TODO: for lock-free hash tables, maybe we don't need to copy,
    19601980;; we could map over the actual hash table vector, because it's
    19611981;; always valid.
     
    19781998            (return-from lock-free-enumerate-hash-keys-and-values
    19791999                         (lock-free-enumerate-hash-keys-and-values hash keys values)))
    1980           (unless (eq val free-hash-marker)
    1981             (when (eql key deleted-hash-key-marker)
    1982               (error "Bug: deleted key but not value?"))
     2000          (unless (or (eq key deleted-hash-key-marker)
     2001                      (eq val deleted-hash-value-marker)
     2002                      (eq val free-hash-marker))
    19832003            (when keys (setf (%svref keys out-idx) key))
    19842004            (when values (setf (%svref values out-idx) val))
  • trunk/source/lisp-kernel/arm-constants.h

    r15425 r15504  
    326326#define FPSCR_IXE_BIT 12                    /* inexact enable */
    327327
    328 #define ABI_VERSION_MIN 1039
    329 #define ABI_VERSION_CURRENT 1040
    330 #define ABI_VERSION_MAX 1040
     328#define ABI_VERSION_MIN 1041
     329#define ABI_VERSION_CURRENT 1041
     330#define ABI_VERSION_MAX 1041
    331331
    332332#define ARM_ARCHITECTURE_v7 7
  • trunk/source/lisp-kernel/arm-gc.c

    r15374 r15504  
    481481        */
    482482        LispObj flags = ((hash_table_vector_header *) base)->flags;
    483 
    484         if ((flags & nhash_keys_frozen_mask) &&
    485             (((hash_table_vector_header *) base)->deleted_count > 0)) {
    486           /* We're responsible for clearing out any deleted keys, since
    487              lisp side can't do it without breaking the state machine
    488           */
    489           LispObj *pairp = base + hash_table_vector_header_count;
    490           natural
    491             npairs = (element_count - (hash_table_vector_header_count - 1)) >> 1;
    492 
    493           while (npairs--) {
    494             if ((pairp[1] == unbound) && (pairp[0] != unbound)) {
    495               pairp[0] = slot_unbound;
    496             }
    497             pairp +=2;
    498           }
    499           ((hash_table_vector_header *) base)->deleted_count = 0;
    500         }
    501 
    502483
    503484        if (flags & nhash_weak_mask) {
  • trunk/source/lisp-kernel/gc-common.c

    r15374 r15504  
    241241  Boolean
    242242    keys_frozen = ((hashp->flags & nhash_keys_frozen_mask) != 0);
     243  // Probably no reason why the non-keys_frozen case couldn't use slot_unbound as well,
     244  // but I don't want to risk it.
     245  LispObj *empty_value = (keys_frozen ? slot_unbound : lisp_nil);
    243246  bitvector markbits = GCmarkbits;
    244247  int tag;
     
    283286      if ((dnode < GCndnodes_in_area) &&
    284287          ! ref_bit(markbits, dnode)) {
    285         pairp[0] = slot_unbound;
    286         if (keys_frozen) {
    287           if (pairp[1] != slot_unbound) {
    288             pairp[1] = unbound;
    289           }
    290         }
    291         else {
    292           pairp[1] = lisp_nil;
    293         }
     288        pairp[0] = slot_unbound;
     289        pairp[1] = empty_value;
    294290        hashp->weak_deletions_count += (1<<fixnumshift);
    295291      }
  • trunk/source/lisp-kernel/ppc-constants32.h

    r15093 r15504  
    329329#define log2_heap_segment_size 16
    330330
    331 #define ABI_VERSION_MIN 1037
    332 #define ABI_VERSION_CURRENT 1037
    333 #define ABI_VERSION_MAX 1037
     331#define ABI_VERSION_MIN 1038
     332#define ABI_VERSION_CURRENT 1038
     333#define ABI_VERSION_MAX 1038
    334334
    335335#endif
  • trunk/source/lisp-kernel/ppc-constants64.h

    r15093 r15504  
    303303#define log2_heap_segment_size 17L
    304304
    305 #define ABI_VERSION_MIN 1037
    306 #define ABI_VERSION_CURRENT 1037
    307 #define ABI_VERSION_MAX 1037
     305#define ABI_VERSION_MIN 1038
     306#define ABI_VERSION_CURRENT 1038
     307#define ABI_VERSION_MAX 1038
  • trunk/source/lisp-kernel/ppc-gc.c

    r15374 r15504  
    558558        */
    559559        LispObj flags = ((hash_table_vector_header *) base)->flags;
    560 
    561         if ((flags & nhash_keys_frozen_mask) &&
    562             (((hash_table_vector_header *) base)->deleted_count > 0)) {
    563           /* We're responsible for clearing out any deleted keys, since
    564              lisp side can't do it without breaking the state machine
    565           */
    566           LispObj *pairp = base + hash_table_vector_header_count;
    567           natural
    568             npairs = (element_count - (hash_table_vector_header_count - 1)) >> 1;
    569 
    570           while (npairs--) {
    571             if ((pairp[1] == unbound) && (pairp[0] != unbound)) {
    572               pairp[0] = slot_unbound;
    573             }
    574             pairp +=2;
    575           }
    576           ((hash_table_vector_header *) base)->deleted_count = 0;
    577         }
    578 
    579560
    580561        if (flags & nhash_weak_mask) {
  • trunk/source/lisp-kernel/x86-constants32.h

    r15147 r15504  
    406406#endif
    407407
    408 #define ABI_VERSION_MIN 1037
    409 #define ABI_VERSION_CURRENT 1037
    410 #define ABI_VERSION_MAX 1037
     408#define ABI_VERSION_MIN 1038
     409#define ABI_VERSION_CURRENT 1038
     410#define ABI_VERSION_MAX 1038
  • trunk/source/lisp-kernel/x86-constants64.h

    r15147 r15504  
    349349#define log2_heap_segment_size 17L
    350350
    351 #define ABI_VERSION_MIN 1037
    352 #define ABI_VERSION_CURRENT 1037
    353 #define ABI_VERSION_MAX 1037
     351#define ABI_VERSION_MIN 1038
     352#define ABI_VERSION_CURRENT 1038
     353#define ABI_VERSION_MAX 1038
  • trunk/source/lisp-kernel/x86-gc.c

    r15374 r15504  
    503503           that rehashing is necessary. */
    504504        LispObj flags = ((hash_table_vector_header *) base)->flags;
    505 
    506         if ((flags & nhash_keys_frozen_mask) &&
    507             (((hash_table_vector_header *) base)->deleted_count > 0)) {
    508           /* We're responsible for clearing out any deleted keys, since
    509              lisp side can't do it without breaking the state machine
    510           */
    511           LispObj *pairp = base + hash_table_vector_header_count;
    512           natural
    513             npairs = (element_count - (hash_table_vector_header_count - 1)) >> 1;
    514 
    515           while (npairs--) {
    516             if ((pairp[1] == unbound) && (pairp[0] != unbound)) {
    517               pairp[0] = slot_unbound;
    518             }
    519             pairp +=2;
    520           }
    521           ((hash_table_vector_header *) base)->deleted_count = 0;
    522         }
    523505
    524506        if (flags & nhash_weak_mask) {
Note: See TracChangeset for help on using the changeset viewer.