| blob | cdb491a927585dd566913b6fdfe554fac0d4f88a |
1 ;;;; This software is part of the SBCL system. See the README file for
2 ;;;; more information.
3 ;;;;
4 ;;;; This software is derived from the CMU CL system, which was
5 ;;;; written at Carnegie Mellon University and released into the
6 ;;;; public domain. The software is in the public domain and is
7 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
8 ;;;; files for more information.
12 ;;;; This file implements abstract types which map globaldb Info-Number/Name
13 ;;;; pairs to data values. The database itself is defined in 'globaldb'.
15 ;;; Quasi-lockfree concurrent hashtable
16 ;;; ===================================
18 ;; References:
19 ;; http://trac.clozure.com/ccl/wiki/Internals/LockFreeHashTables
20 ;; https://github.com/boundary/high-scale-lib/blob/master/src/main/java/org/cliffc/high_scale_lib/NonBlockingHashMap.java
22 ;; The basic hashable is a lightweight one using prime number sizing strategy,
23 ;; and a secondary hash for re-probing that is not necessarily co-prime with
24 ;; the table size (as it would be, ideally), and no support for deletion.
26 ;; The lock-free logic differs from each of the preceding reference algorithms.
27 ;; The Java algorithm is truly lock-free: death of any thread will never impede
28 ;; progress in other threads. The CCL algorithm is only quasi-lock-free, as is
29 ;; ours. Were a rehashing thread to terminate abnormally while holding the
30 ;; rehash mutex, all other threads will likely starve at some point.
31 ;;
32 ;; Unlike the CCL algorithm, we allow reading/writing concurrently with rehash.
33 ;; Most operations will never notice that the rehasher has acquired a mutex,
34 ;; because the only case where writers compete for the mutex is in trying
35 ;; to claim a new cell in a storage vector that is being transported, and where
36 ;; the rehasher has already visited the desired cell. Since the rehasher will
37 ;; never re-visit a cell, it disallows updates that it could not perceive.
38 ;; The Java algorithm has additional complexity imposed upon it by the
39 ;; feature that rehashing work is parceling out fairly to threads,
40 ;; whereas we avoid that by having one rehasher transport all cells.
42 ;; A marker for cells that may be claimed by a writer
44 ;; A marker for cells that may NOT be claimed by a writer.
47 ;; We have a 24-bit cell index. This is generous,
48 ;; allowing for ~5 million Names assuming 60% load factor.
51 ;; An INFO-STORAGE is a vector of a 3-element header followed by all keys
52 ;; and then all values. This way we can simply use FILL to set all keys to 0
53 ;; and all values to NIL.
56 ;; Capacity refers to pairs of vector elements. The lower bound is to
57 ;; try (in vain) to elide a check for division by 0 in the secondary hash.
58 ;; The upper bound is harmlessly wrong by a factor of 2 because
59 ;; INFO-CELL-INDEX should be the max physical cell that can be addressed.
60 ;; No problem - you'll run out of memory before hitting the edge anyway.
62 ;; Make a new storage if count exceeds this
65 ;; keys ... data ...
66 )
70 primify))
72 ;; If you ask for 40 entries at 50% load, you get (PRIMIFY 80) entries.
77 ;; The threshold should be approximately the same as
78 ;; the number you asked for in the first place.
83 a))
86 globaldb-sxhashoid))
92 ;; COUNT is always at *least* as large as the key count.
93 ;; If no insertions are in progress, it is exactly right.
102 ;; We can't assume that the host lisp supports a CAS operation for info-gethash
103 ;; or info-puthash, but that's fine because there's only one thread.
105 #+sb-xc-host
107 #-sb-xc-host
110 ;; Similarly we need a way to atomically adjust the hashtable count.
113 #+sb-xc-host
115 #-sb-xc-host
116 ;; Inform the compiler that this is not possibly a bignum,
117 ;; since it's true upper bound is the info storage threshold.
121 info-forwarding-pointer-target
122 info-value-moved-p)
126 ;; Concurrent access relies on a forwarding pointer being placed into
127 ;; transported value cells. Since this is not a fully general hashtable,
128 ;; we can use fixnums as forwarding pointers, as they're otherwise
129 ;; never present as a value.
130 #+sb-xc-host
141 ;; However, here is a forwarding-pointer representation that allows fixnums
142 ;; as legal values in the table, so, since it's more general, ... why not?
143 #-sb-xc-host
154 ;; The common skeleton of {Get, Put, Rehash} operations. Probe key cells until
155 ;; either a hit occurs, in which case the :HIT form is executed and looping
156 ;; stops; or an empty slot is seen in which case the :MISS code is executed.
157 ;; :MISS should contain a GO or RETURN on success, otherwise probing continues.
158 ;; No precaution exists against probing forever, such as could happen if the
159 ;; probing strategy fails to visit all candidate free cells.
160 ;;
161 ;; Stepping is done by subtracting a secondary hash rather than adding,
162 ;; as this allows testing for wraparound by comparison to a constant
163 ;; instead of against storage capacity. Nonlinear probing jumps around in
164 ;; the L1 cache regardless, as they key space is a ring so the "direction"
165 ;; of probing is irrelevant. [In contrast, linear probing usually benefits
166 ;; from scanning physically forward, preferably within a cache line,
167 ;; but for practical purposes linear probing is worse.]
168 ;;
184 ;; Optimistically test for hit first, then markers
198 ;; only need the second hash if didn't hit on first try
200 :loop
204 next)))
210 ;; Wait for ENV's storage to change to something other than STORAGE, and
211 ;; return the new one. As long as rehash finishes in finite time, every thread
212 ;; makes progess. We don't protect against untimely death of the thread
213 ;; that holds the lock.
214 ;;
216 ;; kinda spin, except not quite that bad
219 ;; Grab and release the mutex for no other reason than to
220 ;; observe that a rehasher doesn't (for the moment) have it.
224 ;; Look in info-environment ENV for the name KEY. Arguments are like GETHASH.
225 ;;
226 ;; Invariant: any KEY's value is present in at most 1 storage.
227 ;; Uniqueness of the location ensures that when writing with CAS, the place is
228 ;; either current, or CAS fails in a way that informs the writer of a new place.
229 ;; At most one probing sequence occurs, in that hitting a key might entail
230 ;; more than one forwarding but never a re-probing.
231 ;; The same is not true on insert, for which probing restart is quite common.
232 ;; When chasing values, INFO-STORAGE-NEXT may or may not be EQ to what is in
233 ;; INFO-ENV-STORAGE, depending whether rehash is still running, has completed,
234 ;; or started all over again before the reader got a chance to chase one time.
235 ;;
239 ;; With 99% certainty the :READ barrier is needed for non-x86, and if not,
240 ;; it can't hurt. 'info-storage-next' can be empty until at least one cell
241 ;; has been forwarded, but in general an unsynchronized read might be
242 ;; perceived as executing before a conditional that guards whether the
243 ;; read should happen at all. 'storage-next' has the deceptive look of a
244 ;; data dependency but it's not - it's a control dependency which as per
245 ;; the 'memory-barriers.txt' document at kernel.org, demands a barrier.
246 ;; The subsequent ref to storage (if the loop iterates) has a
247 ;; data-dependency, and will never be reordered except on an Alpha :-(
248 ;; so we _don't_ need a barrier after resetting 'storage' and 'index'.
257 ;; ENV and KEY are as above. UPDATE-PROC is invoked with the old value stored
258 ;; for KEY and it should return the possibly-unchanged new value to put.
259 ;;
260 ;; Note a tiny problem of semantics on 'miss' - for an instant after winning
261 ;; CAS of a new key, that key appears to exist with the default value NIL,
262 ;; causing readers to think "FOUND-P" = T which might have a different sense
263 ;; from "not found". If a Name is transiently "found" despite having no data,
264 ;; nobody cares, at least for globaldb. Remedies, if desired, involve either:
265 ;; 1. Making a "no value" marker that is distinct from NIL.
266 ;; 2. Placing keys/value pairs in adjacent cells and using double-wide CAS.
267 ;; The reason we don't care about this anomaly is that we have to
268 ;; look in an Info-Vector [q.v.] anyway to get the whole picture.
269 ;;
280 ;; invariant: OLDVAL is not a forwarding pointer.
283 oldval ; forgo update
286 ;; Unlike above, this read of storage-next can not
287 ;; be perceived as having occurred prior to CAS.
288 ;; x86 synchronizes at every locked instruction, and our
289 ;; PPC CAS vops sync as a nececessity of performing CAS.
300 :miss
306 ;; any thread could have beaten us to rehashing
311 ;; Attempt to claim KEY-INDEX
314 ;; Optimistically assume that nobody else rewrote the value
317 ;; The fallthrough branch of this COND is ordinary CAS failure where
318 ;; somebody else wanted this slot, and won. Looping tries again.
322 ;; as preemptive check up above ensured no rehash needed.
326 ;; Rehash ENV to a larger storage. When writing a key into new storage,
327 ;; key cells are uniquely owned by this thread without contention.
328 ;; Other threads may not look in new storage without first observing that
329 ;; a key's value was definitely moved.
330 ;; The rehasher marks empty cells as unusable so that writers can't insert
331 ;; into the subsequence of storage already visited. The rehasher must of
332 ;; course vie for the cell it is trying to mark as unusable.
333 ;;
337 ;; the new storage begins life at ~50% capacity
347 ;; If the indexed cell is not in use, try once to prevent subsequent
348 ;; writes by changing the empty marker to 'unavailable'. The outcome
349 ;; determines whether to continue transporting the cell's value.
354 key))
365 ;; Copy the current value into the new storage,
366 ;; and CAS in a forwarding pointer. Repeat until successful.
368 ;; Force VALUE to memory before publishing relocated status
373 old-storage old-value-index value
379 ;; Typical of most lockfree algorithms, we've no idea when
380 ;; the old storage can be freed. GC will figure it out.
381 ;; No write barrier needed. Threads still looking at old storage
382 ;; will eventually find all cells unavailable or forwarded.
385 ;; This maphash implementation is not threadsafe.
386 ;; It can be made threadsafe by following forwarded values
387 ;; and skipping over unavailable keys.
388 ;;
401 ;; CAS is the primitive operation on an info hashtable,
402 ;; and SETF is implemented in terms of CAS. For the most part it is
403 ;; inadvisable to use this for anything other than tinkering at the REPL.
404 ;;
412 ;;;; Info-Vectors
413 ;;;; ============
415 ;;; Info for a Name (an arbitrary object) is stored in an Info-Vector,
416 ;;; which is like is a 2-level association list. Info-Vectors are stored in
417 ;;; symbols for most names, or in the global hashtable for "complicated" names.
419 ;;; Such vectors exists in two variations: packed and unpacked.
420 ;;; The representations are nearly equivalent for lookup, but the packed format
421 ;;; is more space-efficient, though difficult to manipulate except by unpacking.
423 ;;; Consider a family of Names whose "root" is SB-MOP:STANDARD-INSTANCE-ACCESS.
424 ;;; 1. SB-MOP:STANDARD-INSTANCE-ACCESS
425 ;;; 2. (SETF SB-MOP:STANDARD-INSTANCE-ACCESS)
426 ;;; 3. (CAS SB-MOP:STANDARD-INSTANCE-ACCESS)
427 ;;;
428 ;;; Those three names share one Info-Vector. Conceptually the outer alist key
429 ;;; is NIL for the first of those names, and SETF/CAS for the latter two.
430 ;;; The inner alist key is a number identifying a type of info.
431 ;;; If it were actually an alist, it would look like this:
432 ;;;
433 ;;; ((nil (63 . #<fdefn SB-MOP:STANDARD-INSTANCE-ACCESS>) (1 . :FUNCTION) ...)
434 ;;; (SETF (63 . #<fdefn (SETF SB-MOP:STANDARD-INSTANCE-ACCESS)>) ...)
435 ;;; (CAS (63 . #<fdefn (CAS SB-MOP:STANDARD-INSTANCE-ACCESS)>) ...)
436 ;;; ...)
437 ;;;
438 ;;; Note:
439 ;;; * The root name is exogenous to the vector - it is not stored.
440 ;;; * The info-number for (:FUNCTION :DEFINITION) is 63, :KIND is 1, etc.
441 ;;; * Names which are lists of length other than 2, or improper lists,
442 ;;; or whose elements are not both symbols, are disqualified.
444 ;;; Packed vector layout
445 ;;; --------------------
446 ;;; Because the keys to the inner lists are integers in the range 0 to 63,
447 ;;; either 5 or 10 keys will fit into a fixnum depending on word size.
448 ;;; This permits one memory read to retrieve a collection of keys. In packed
449 ;;; format, an ordered set of keys ("fields") is called a "descriptor".
450 ;;;
451 ;;; Descriptors are stored from element 0 upward in the packed vector,
452 ;;; and data are indexed downward from the last element of the vector.
453 ;;;
454 ;;; #(descriptor0 descriptor1 ... descriptorN valueN ... value1 value0)
455 ;;;
456 ;;; e.g. The field at absolute index 3 - vector element 0, bit position 18 -
457 ;;; will find its data at index (- END 3). In this manner, it doesn't matter
458 ;;; how many more descriptors exist.
460 ;;; A "group" comprises all the info for a particular Name, and its list
461 ;;; of types may may span descriptors, though rarely.
462 ;;; An "auxilliary key" is the first element of a 2-list Name. It is interposed
463 ;;; within the data portion of the vector after the preceding info group.
464 ;;; Descriptors are self-delimiting in that the first field in a group
465 ;;; indicates the number of additional fields in the group.
467 ;;; Unpacked vector layout
468 ;;; ----------------------
469 ;;; This representation is used transiently during insertion/deletion.
470 ;;; It is a concatenation of plists as a vector, interposing at the splice
471 ;;; points the auxilliary key for the group, except for the root name which
472 ;;; does not store an auxilliary key.
473 ;;;
474 ;;; Unpacked vector format looks like:
475 ;;;
476 ;;; /- next group starts here
477 ;;; v
478 ;;; #(length type val type val ... KEY length type val ... KEY length ...)
479 ;;; ^
480 ;;; info group for the primary Name, a/k/a "root symbol", starts here
481 ;;;
482 ;;; One can envision that the first info group stores its auxilliary key
483 ;;; at vector index -1 when thinking about the correctness of algorithms
484 ;;; that process unpacked info-vectors.
485 ;;; See !TEST-PACKIFY-INFOS for examples of each format.
487 ;;;;; Some stuff moved from 'globaldb.lisp':
491 ;; Using 6 bits per packed field, 5 infos can be described in a 30-bit fixnum,
492 ;; or 10 in a fixnum on 64-bit machines (regardless of n-fixnum-tag-bits).
493 ;; The eval-when seems to be necessary for building with CCL as host.
497 ;; Descriptors are target fixnums
500 ;; An empty info-vector. Its 0th field describes that there are no more fields.
503 ;; FDEFINITIONs have an info-number that admits slightly clever logic
504 ;; for INFO-VECTOR-FDEFN. Do not change this constant without
505 ;; careful examination of that function.
508 ;; Extract a field from a packed info descriptor.
509 ;; A field is either a count of info-numbers, or an info-number.
516 ;; Compute the number of elements needed to hold unpacked VECTOR after packing.
517 ;; This is not "compute-packed-info-size" since that could be misconstrued
518 ;; and wanting the vector to be already packed.
519 ;;
526 ;; 'length' is the number of vector elements in this info group,
527 ;; including itself but not including its auxilliary key.
529 ;; Divide by 2 because we only count one field for the entry, but the
530 ;; input vector had 2 cells per entry. Add 1 because the group's field
531 ;; count is accounted for in the total packed field count.
535 ;; The first info group lacks an aux-key, making n-fields 1 too high
536 ;; in terms of data cells used, but correct for packed fields.
539 ;; MAKE-INFO-DESCRIPTOR is basically ASH-LEFT-MODFX, shifting VAL by SHIFT.
540 ;; It is important that info descriptors be target fixnums, but 'cross-modular'
541 ;; isn't loaded early enough to use 'mask-signed-field'.
542 ;; It's not needed on 64-bit host/target combination because 10 fields (60 bits)
543 ;; never touch the sign bit.
544 ;; FIXME: figure out why the definition of ash-left-modfx is
545 ;; conditionalized out for platforms other than x86[-64].
546 ;; It looks like it ought to work whether or not there are vops.
553 ;; Convert unpacked vector to packed vector.
554 ;; 'pack-infos' would be a hypothetical accessor for the 'infos' of a 'pack'
555 ;; (whatever that is ...) so verbifying as such makes it more mnemonic to me.
556 ;;
567 field-shift)
575 ;; Truncating divide by 2: count = n-elements in the group @ 2 per entry,
576 ;; +1 for count itself but not including its aux-key.
588 output))
590 ;; Within the scope of BODY, bind GENERATOR to a local function which
591 ;; returns the next field from a descriptor in INPUT-VAR, a packed vector.
592 ;; The generator uses DESCRIPTOR-INDEX and updates it as a side-effect.
593 ;;
615 ;; Iterate over VECTOR, binding DATA-INDEX to the index of each aux-key in turn.
616 ;; TOTAL-N-FIELDS is deliberately exposed to invoking code.
617 ;;
628 ;; Loop through the descriptors in random-access fashion.
629 ;; Skip 1+ n-infos each time, because the 'n-infos' is itself a field
630 ;; that is not accounted for in its own value.
637 ;; Done when the ascending index and descending index meet
642 ;; Return all function names that are stored in SYMBOL's info-vector.
643 ;; As an example, (INFO-VECTOR-NAME-LIST 'SB-PCL::DIRECT-SUPERCLASSES) =>
644 ;; ((SB-PCL::SLOT-ACCESSOR :GLOBAL SB-PCL::DIRECT-SUPERCLASSES SB-PCL::READER)
645 ;; (SB-PCL::SLOT-ACCESSOR :GLOBAL SB-PCL::DIRECT-SUPERCLASSES BOUNDP)
646 ;; (SB-PCL::SLOT-ACCESSOR :GLOBAL SB-PCL::DIRECT-SUPERCLASSES SB-PCL::WRITER))
653 list))
657 ;; Compute the number of elements needed to hold packed VECTOR after unpacking.
658 ;; The unpacked size is the number of auxilliary keys plus the number of entries
659 ;; @ 2 cells per entry, plus the number of length cells which indicate the
660 ;; number of data cells used (including length cells but not aux key cells).
661 ;; Equivalently, it's the number of packed fields times 2 minus 1.
662 ;;
666 ;; off-by-one: the first info group's auxilliary key is imaginary
669 ;; Convert packed INPUT vector to unpacked.
670 ;; If optional OUTPUT is supplied, it is used, otherwise output is allocated.
671 ;; For efficiency the OUTPUT should be provided as a dynamic-extent array.
672 ;;
682 ;; store the info group length, including the length cell in the length
691 ;; Return the index of the 'length' item for an info group having
692 ;; auxilliary-key KEY in unpacked VECTOR bounded by END (exclusive),
693 ;; or NIL if not found.
694 ;;
702 ;; skip 'length' cells plus the next aux-key
706 ;; backward a cell is where the aux-key resides.
710 ;; In packed info VECTOR try to find the auxilliary key SYMBOL.
711 ;; If found, return indices of its data, info descriptor word, and field.
712 ;; If not found, the first value is NIL and the descriptor indices
713 ;; arbitrarily point to the next available descriptor field.
714 ;;
716 ;; explicit bounds checking is done by the code below
721 ;; On each iteration DATA-IDX points to an aux-key cell
722 ;; The first group's imaginary aux-key cell is past the end.
726 ;; Efficiently skip past N-INFOS infos. If decrementing the data index
727 ;; hits the descriptor index, we're done. Otherwise increment the field
728 ;; index and maybe descriptor index and check again for loop termination.
731 ;; descriptor-idx < data-idx, so potentially more data.
732 ;; If current descriptor has another field, continue.
740 ;; While this could compare aux-keys with #'EQUAL, it is not obvious how
741 ;; in general one would pick a symbol from the name as that which
742 ;; is delegated as the one to hold the info-vector.
744 ;; At least one aux key is present.
746 ;; aux-key order invariant allows early fail on SETF
751 field-idx)))
757 ;; Take a packed info-vector INPUT and insert (AUX-KEY,INFO-NUMBER,VALUE).
758 ;; Packed info-vectors are immutable. Any alteration must create a copy.
759 ;; This is done by unpacking/repacking - it's easy enough and fairly
760 ;; efficient since the temporary vector is stack-allocated.
761 ;;
765 ;; Test if the aux-key has been seen before or needs to be added.
782 ;; creating a new aux key. SETF immediately follows the data
783 ;; for the primary Name. All other aux-keys go to the end.
790 aux-key new old-size)))
791 ;; it had better be found - it was in the packed vector
793 ;; fdefn must be the first piece of info for any name.
794 ;; This facilitates implementing SYMBOL-FUNCTION without
795 ;; without completely decoding the vector.
798 info-number value)
799 ;; add 2 cells, and verify that re-packing won't
800 ;; overflow the 'count' for this info group.
805 ;; Return T if INFO-VECTOR admits quicker insertion logic - it must have
806 ;; exactly one descriptor for the root name, space for >= 1 more field,
807 ;; and no aux-keys.
811 ;; We can easily determine if the no-aux-keys constraint is satisfied,
812 ;; because a secondary name's info occupies at least two cells,
813 ;; one for its aux-key and >= 1 for info values.
817 ;; Take a packed info-vector INPUT and return a new one with INFO-NUMBER/VALUE
818 ;; added for the root name. The vector must satisfy INFO-QUICKLY-INSERTABLE-P.
819 ;; This code is separate from PACKED-INFO-INSERT to facilitate writing
820 ;; a unit test of this logic against the complete logic.
821 ;;
823 ;; Because INPUT contains 1 descriptor and its corresponding values,
824 ;; the current length is exactly NEW-N, the new number of fields.
828 ;; Two cases: we're either inserting info for the fdefn, or not.
830 ;; fdefn, if present, must remain the first packed field.
831 ;; Replace the lowest field (the count) with +fdefn-info-num+,
832 ;; shift everything left 6 bits, then OR in the new count.
837 ;; Packed vectors are indexed "backwards". The first
838 ;; field's info is in the highest numbered cell.
843 ;; Add a field on the high end and increment the count.
849 ;; Slide the old data up 1 cell.
852 new-vect))
861 ;; Search packed VECTOR for AUX-KEY and INFO-NUMBER, returning
862 ;; the index of the data if found, or NIL if not found.
863 ;;
874 ;; Fetch a descriptor and shift out trailing bits that won't be scanned.
878 ;; Compute n things in this descriptor after extracting one field. e.g.
879 ;; if starting index = 2, there's space for 7 more fields in 60 bits.
881 ;; Type inference on n-infos deems it to have no lower bound due to DECF.
885 ;; Repeatedly shift and mask, which is quicker than extracting a field at
886 ;; varying positions. Start by shifting out the n-infos field.
902 ;; Helper for CLEAR-INFO-VALUES when Name has the efficient form.
903 ;; Given packed info-vector INPUT and auxilliary key KEY2
904 ;; return a new vector in which TYPE-NUMS are absent.
905 ;; When none of TYPE-NUMs were present to begin with, return NIL.
906 ;;
907 ;; While this could determine whether it would do anything before unpacking,
908 ;; clearing does not happen often enough to warrant the pre-check.
909 ;;
929 return probe)))
930 ;; N.B. the early termination checks aren't just optimizations,
931 ;; they're requirements, because otherwise the loop could smash
932 ;; data that does not belong to this auxilliary key.
934 ;; Squash out 2 cells if deleting an info for primary name,
935 ;; or for secondary name with at least one more entry.
940 ;; the group is now comprised solely of its length cell
943 ;; Delete the sole entry for a secondary name
944 ;; by removing aux-key, length, and one entry (a cell pair).
950 ;; All empty info-vectors are equivalent, so if
951 ;; unpacked vector has no data, return a constant.
955 ;; We need a few magic constants to be shared between the next two functions.
960 ;; PCL names are physically 4-lists (see "pcl/slot-name")
961 ;; that get treated as 2-component names for globaldb's purposes.
962 ;; Return the kind of PCL slot accessor name that NAME is, if it is one.
963 ;; i.e. it matches (SLOT-ACCESSOR :GLOBAL <sym> READER|WRITER|BOUNDP)
964 ;; When called, NAME is already known to start with 'SLOT-ACCESSOR.
965 ;; This has to be defined before building PCL.
968 kind)
974 ;; Return symbols that can't conflict, in case somebody
975 ;; legitimates (BOUNDP <f>) via DEFINE-FUNCTION-NAME-SYNTAX.
976 ;; Especially important since BOUNDP is an external of CL.
981 ;; The first return value is what matters to WITH-GLOBALDB-NAME
982 ;; for deciding whether the name is "simple".
983 ;; Return the KIND first, just in case somehow we end up with
984 ;; (SLOT-ACCESSOR :GLOBAL NIL WRITER) as a name.
985 ;; [It "can't happen" since NIL is a constant though]
989 ;; Construct a name from its parts.
990 ;; For PCL global accessors, produce the real name, not the 2-part name.
991 ;; This operation is not invoked in normal use of globaldb.
992 ;; It is only for mapping over all names.
999 ;; Call FUNCTION with each piece of info in packed VECT using ROOT-SYMBOL
1000 ;; as the primary name. FUNCTION must accept 3 values (NAME INFO-NUMBER VALUE).
1014 #|
1020 =>
1027 Which is interpreted as:
1036 This is interpreted as
1040 |#
1042 ;; Reshape inputs per the above commented example to a packed vector.
1043 ;; The info for a symbol's fdefn must precede other info-numbers.
1044 ;; and SETF must be the first aux key if other aux keys are present.
1045 ;; The test function does not enforce these invariants.
1046 ;; N.B. As this function starts with "!", is is omitted from the target image.
1068 ;; Given a NAME naming a globaldb object, decide whether the NAME has
1069 ;; an efficient or "simple" form, versus a general or "hairy" form.
1070 ;; The efficient form is either a symbol, a (CONS SYMBOL (CONS SYMBOL NULL)),
1071 ;; or a PCL global slot {reader, writer, boundp} function name.
1072 ;;
1073 ;; If NAME is "simple", bind KEY2 and KEY1 to the elements
1074 ;; in that order, and execute the SIMPLE code, otherwise execute the HAIRY code.
1075 ;; If ALLOW-ATOM is T - the default - then NAME can be just a symbol
1076 ;; in which case its second component is +NO-AUXILLIARY-KEY+.
1077 ;;
1092 ,simple
1093 ;; The KEYs remain bound, but they should not be used for anything.
1096 ;; Given Info-Vector VECT, return the fdefn that it contains for its root name,
1097 ;; or nil if there is no value. NIL input is acceptable and will return NIL.
1101 ;; This is safe: Info-Vector invariant requires that it have length >= 1.
1103 ;; Test that the first info-number is +fdefn-info-num+ and its n-infos
1104 ;; field is nonzero. These conditions can be tested simultaneously
1105 ;; using a SIMD-in-a-register idea. The low 6 bits must be nonzero
1106 ;; and the next 6 must be exactly #b111111, so considered together
1107 ;; as a 12-bit unsigned integer it must be >= #b111111000001
1110 ;; DATA-REF-WITH-OFFSET doesn't know the info-vector length invariant,
1111 ;; so depite (safety 0) eliding bounds check, FOLD-INDEX-ADDRESSING
1112 ;; wasn't kicking in without (TRULY-THE (INTEGER 1 *)).
1115 ;;; Some of this stuff might belong in 'symbol.lisp', but can't be,
1116 ;;; because 'symbol.lisp' is :NOT-HOST in build-order.
1118 ;; In the target, UPDATE-SYMBOL-INFO is defined in 'symbol.lisp'.
1119 #+sb-xc-host
1121 ;; Never pass NIL to an update-fn. Pass the minimal info-vector instead,
1122 ;; a vector describing 0 infos and 0 auxilliary keys.
1129 ;; Return the globaldb info for SYMBOL. With respect to the state diagram
1130 ;; presented at the definition of SYMBOL-PLIST, if the object in SYMBOL's
1131 ;; info slot is LISTP, it is in state 1 or 3. Either way, take the CDR.
1132 ;; Otherwise, it is in state 2 so return the value as-is.
1133 ;; In terms of this function being named "-vector", implying always a vector,
1134 ;; it is understood that NIL is a proxy for +NIL-PACKED-INFOS+, a vector.
1135 ;;
1136 #-sb-xc-host
1144 ;;; The current *INFO-ENVIRONMENT*, a structure of type INFO-HASHTABLE.
1145 ;;; Cheat by setting to nil before the type is proclaimed
1146 ;;; so that we can then also proclaim ALWAYS-BOUND.
1148 #-sb-xc-host
1152 ;;; Update the INFO-NUMBER for NAME in the global environment,
1153 ;;; setting it to NEW-VALUE. This is thread-safe in the presence
1154 ;;; of multiple readers/writers. Threads simultaneously writing data
1155 ;;; for the same NAME will succeed if the info type numbers differ,
1156 ;;; and the winner is indeterminate if the type numbers are the same.
1157 ;;;
1158 ;;; It is not usually a good idea to think of globaldb as an arbitrary
1159 ;;; key-to-value map supporting rapid or frequent update for a key.
1160 ;;; This is because each update must shallow-copy any data that existed
1161 ;;; for NAME, as a consequence of the very minimal lockfree protocol.
1162 ;;;
1163 ;;; If, for example, you wanted to track how many times a full-call to
1164 ;;; each global function was emitted during compilation, you could create
1165 ;;; an info-type (:function :full-calls) and the value of that info-type
1166 ;;; could be a cons cell holding an integer. In this way incrementing
1167 ;;; the cell contents does not affecting the globaldb. In contrast,
1168 ;;; (INCF (INFO :function :full-calls myname)) would perform poorly.
1169 ;;;
1170 ;;; See also ATOMIC-SET-INFO-VALUE and GET-INFO-VALUE-INITIALIZING
1171 ;;; for atomic read/modify/write operations.
1172 ;;;
1173 ;;; Return the new value so that this can be conveniently used in a
1174 ;;; SETF function.
1179 ;; Storage of FAST-METHOD and SLOW-METHOD compiler info is largely pointless.
1180 ;; Why? Because the compiler can't even resolve the "name" of the function in
1181 ;; many cases. If there are EQL specializers involved, it's clearly impossible
1182 ;; because the form X in (EQL x) needs to be evaluated. So most of the data
1183 ;; can't be computed until the file defining the method is loaded. At that
1184 ;; point, you know that the :KIND is :FUNCTION, and :WHERE-FROM is :DEFINED
1185 ;; - they can't be anything else. And you also pretty much know the signature,
1186 ;; since it is based on the specializers, so storing again is a total waste.
1187 ;;
1188 ;; FIXME: figure out a way not to store these, or else have globaldb ignore
1189 ;; the calls to set-info-value, and mock any calls to get-info-value
1190 ;; so that it looks like the data were stored, if someone tries to read it.
1191 ;: Or store the data in the method object somehow so that at least dropping
1192 ;; a method can drop the data. This would work because as mentioned above,
1193 ;; there is mostly no such thing as purely compile-time info for methods.
1203 ;; If the INFO-NUMBER already exists in VECT, then copy it and
1204 ;; alter one cell; otherwise unpack it, grow the vector, and repack.
1213 copy)))))
1215 :simple
1216 ;; UPDATE-SYMBOL-INFO never supplies OLD-INFO as NIL.
1219 :hairy
1220 ;; INFO-PUTHASH supplies NIL for OLD-INFO if NAME was absent.
1225 new-value)
1227 ;; Instead of accepting a new-value, call NEW-VALUE-FUN to compute it
1228 ;; from the existing value. The function receives two arguments:
1229 ;; if there was already a value, that value and T; otherwise two NILs.
1230 ;; Return the newly-computed value. If NEW-VALUE-FUN returns the old value
1231 ;; (compared by EQ) when there was one, then no globaldb update is made.
1243 vect aux-key info-number
1248 vect ; return the old vector
1251 copy)))))))
1253 :simple
1254 ;; UPDATE-SYMBOL-INFO never supplies OLD-INFO as NIL.
1257 :hairy
1258 ;; INFO-PUTHASH supplies NIL for OLD-INFO if NAME was absent.
1263 new-value))
1265 ;; %GET-INFO-VALUE-INITIALIZING is provided as a low-level operation similar
1266 ;; to the above because it does not require info metadata for defaulting,
1267 ;; nor deal with the keyword-based info type designators at all.
1268 ;; In contrast, GET-INFO-VALUE requires metadata.
1269 ;; For this operation to make sense, the objects produced should be permanently
1270 ;; assigned to their name, such as are fdefns and classoid-cells.
1271 ;; Note also that we do not do an initial attempt to read once with INFO,
1272 ;; followed up by a double-checking get-or-set operation. It is assumed that
1273 ;; the user of this already did an initial check, if such is warranted.
1278 result)
1286 ;; Update conflicts possibly for unrelated info-number
1287 ;; can force re-execution. (UNLESS result ...) tries
1288 ;; to avoid calling the thunk more than once.
1292 result))))))
1294 :simple
1295 ;; UPDATE-SYMBOL-INFO never supplies OLD-INFO as NIL.
1298 :hairy
1299 ;; INFO-PUTHASH supplies NIL for OLD-INFO if NAME was absent.
1303 ;; Return OLD-INFO to elide writeback. Unlike for
1304 ;; UPDATE-SYMBOL-INFO, NIL is not a no-op marker.
1305 old-info)))
1307 result))