SBCL

1.2.1. ed functions

Although SBCL does not provide a resident editor, the ed function can
be customized to hook into user-provided editing mechanisms as
follows:

Function: ed [cl] &optional x

    Starts the editor (on a file or a function if named). Functions
    from the list *ed-functions* are called in order with x as an
    argument until one of them returns non-NIL; these functions are
    responsible for signalling a file-error to indicate failure to
    perform an operation on the file system.

Variable: *ed-functions* [sb-ext]

    See function documentation for ed. 

1.2.2. Concurrency

(defvar *buffer-queue* (make-waitqueue))
(defvar *buffer-lock* (make-mutex :name "buffer lock"))

(defvar *buffer* (list nil))

(defun reader ()
  (with-mutex (*buffer-lock*)
    (loop
      (condition-wait *buffer-queue* *buffer-lock*)
      (loop
        (unless *buffer* (return))
        (let ((head (car *buffer*)))
          (setf *buffer* (cdr *buffer*))
          (format t "reader ~A woke, read ~A~%"
                  *current-thread* head))))))

(defun writer ()
  (loop
    (sleep (random 5))
    (with-mutex (*buffer-lock*)
      (let ((el (intern
                 (string (code-char
                          (+ (char-code #\A) (random 26)))))))
        (setf *buffer* (cons el *buffer*)))
      (condition-notify *buffer-queue*))))

(make-thread #'writer)
(make-thread #'reader)
(make-thread #'reader)

#<THREAD tid=0 RUNNING {100C873E73}>

(defvar *data* nil)
(defvar *queue* (make-waitqueue))
(defvar *lock* (make-mutex))

;; Consumer
(defun pop-data (&optional timeout)
  (with-mutex (*lock*)
    (loop until *data*
          do (or (condition-wait *queue* *lock* :timeout timeout)
                 ;; Lock not held, must unwind without touching *data*.
                 (return-from pop-data nil)))
    (pop *data*)))

;; Producer
(defun push-data (data)
  (with-mutex (*lock*)
    (push data *data*)
    (condition-notify *queue*)))

PUSH-DATA

1. Barriers
   
   properties

   ID: dc91fb4a-adee-44ec-9bd8-cbfa10db8dca
   CREATED: <2025-03-06 Thu 14:19>
   

   These are based on the Linux kernel barrier design, which is in turn based on the Alpha CPU memory model. They are presently implemented for x86, x86-64, PPC, ARM64, and RISC-V systems, and behave as compiler barriers on all other CPUs.

   In addition to explicit use of the sb-thread:barrier macro, the following functions and macros also serve as :memory barriers:

   • sb-ext:atomic-decf, sb-ext:atomic-incf, sb-ext:atomic-push, and sb-ext:atomic-pop.
   • sb-ext:compare-and-swap.
   • sb-thread:grab-mutex, sb-thread:release-mutex, sb-thread:with-mutex and sb-thread:with-recursive-lock.
   • sb-thread:signal-semaphore, sb-thread:try-semaphore and sb-thread:wait-on-semaphore.
   • sb-thread:condition-wait, sb-thread:condition-notify and sb-thread:condition-broadcast.

2. Timers
   
   properties

   ID: 6ff7096f-a666-4103-8f32-1dc62c04cb35
   CREATED: <2025-03-06 Thu 14:19>
   

   edges

   [2025-03-06 Thu 14:19] – info
   

   
   
3. sb-thread
   
   properties

   ID: 7bf0993f-6212-4635-a071-bf2e7d9ba7f9
   CREATED: <2025-03-06 Thu 14:06>
   

   edges

   [2025-03-06 Thu 14:07] -> Asynchrony
   [2025-03-06 Thu 14:08] – info
   

   
   

   (make-thread (lambda () (write-line "Hello, world")))
   

   #<THREAD tid=0 RUNNING {100933AD93}>
   

   • sync primitives
   • no thread-pools supplied by default, handled by user code.
   • sb-thread:*current-thread*

   • what is an ephemeral thread?

     (describe (function sb-thread::%make-thread))
     

     #<FUNCTION SB-THREAD::%MAKE-THREAD>
       [compiled function]
     
     
     A constructor for SB-THREAD:THREAD
     Lambda-list: (%NAME EPHEMERAL-P SEMAPHORE)
     Derived type: (FUNCTION (T T T) (VALUES SB-THREAD:THREAD &OPTIONAL))
     Source file: SYS:SRC;CODE;THREAD-STRUCTS.LISP
     

     NB: ephemeral threads must terminate strictly before the test of NTHREADS>1
     in DEINIT, i.e. this is not a promise that the thread will terminate
     just-in-time for the final call out to save, but rather by an earlier time.
     

     (describe (function sb-thread::thread-ephemeral-p))
     

     #<FUNCTION THREAD-EPHEMERAL-P>
       [compiled function]
     
     
     An accessor for SB-THREAD:THREAD
     Lambda-list: (INSTANCE)
     Derived type: (FUNCTION (T) (VALUES BOOLEAN &OPTIONAL))
     Documentation:
       Return T if THREAD is `ephemeral', which indicates that this thread is
       used by SBCL for internal purposes, and specifically that our runtime knows how
       to terminate this thread cleanly prior to core file saving without signalling
       an error in that case.
     Source file: SYS:SRC;CODE;THREAD-STRUCTS.LISP
     

     • see handle-thread-exit
4. Atomics
   
   properties

   ID: bb27d9c3-513a-4ac6-8780-580c09257040
   CREATED: <2025-03-06 Thu 14:11>
   

   edges

   [2025-03-06 Thu 14:13] – info
   

   
   

   • sb-ext:compare-and-swap (sb-ext:cas)

   • sb-ext:atomic-update

           ;;; Conses T to the head of FOO-LIST.
     (defstruct foo list)
     (defvar *foo* (make-foo))
     (sb-ext:atomic-update (foo-list *foo*) #'cons t)
     
     (let ((x (cons :count 0)))
       (mapc #'sb-thread:join-thread
         (loop repeat 1000
               collect (sb-thread:make-thread
                    (lambda ()
                  (loop repeat 1000
                        do (sb-ext:atomic-update (cdr x) #'1+)
                       (sleep 0.00001))))))
       ;; Guaranteed to be (:COUNT . 1000000) -- if you replace
       ;; atomic update with (INCF (CDR X)) above, the result becomes
       ;; unpredictable.
       x)
     

     (:COUNT . 1000000)
     

1.2.3. Sequence Protocol

1. Iterator Protocol
   
   properties

   ID: 5a3debd1-9b38-48f0-bbcd-8cf3f18e8407
   CREATED: <2025-11-26 Wed 21:41>
   

   The iterator protocol is a bit clunky and doesn't appear that useful out of context. Upon investigation it seems the most effective context is in fact the standard LOOP macro where there is a built-in ELEMENTS iteration path.

1.2.4. global vars

(describe 'sb-ext:defglobal)

SB-EXT:DEFGLOBAL
  [symbol]

DEFGLOBAL names a macro:
  Lambda-list: (NAME VALUE &OPTIONAL (DOC NIL))
  Documentation:
    Defines NAME as a global variable that is always bound. VALUE is evaluated
    and assigned to NAME both at compile- and load-time, but only if NAME is not
    already bound.
    
    Global variables share their values between all threads, and cannot be
    locally bound, declared special, defined as constants, and neither bound
    nor defined as symbol macros.
    
    See also the declarations SB-EXT:GLOBAL and SB-EXT:ALWAYS-BOUND.
  Source file: SYS:SRC;CODE;MACROS.LISP

(describe 'sb-ext:define-load-time-global)

SB-EXT:DEFINE-LOAD-TIME-GLOBAL
  [symbol]

DEFINE-LOAD-TIME-GLOBAL names a macro:
  Lambda-list: (NAME VALUE &OPTIONAL (DOC NIL))
  Documentation:
    Defines NAME as a global variable that is always bound. VALUE is evaluated
    and assigned to NAME at load-time, but only if NAME is not already bound.
    
    Attempts to read NAME at compile-time will signal an UNBOUND-VARIABLE error
    unless it has otherwise been assigned a value.
    
    See also DEFGLOBAL which assigns the VALUE at compile-time too.
  Source file: SYS:SRC;CODE;MACROS.LISP

1.3.1. SB-LOOP

(print (sb-loop::loop-translate (sb-loop::make-loop '(for i from 0 below 4) nil sb-loop::*loop-ansi-universe*)))

(BLOCK NIL
  (LET ((I 0))
    (DECLARE (IGNORABLE I)
             (TYPE (AND REAL NUMBER) I))
    (TAGBODY
     SB-LOOP::NEXT-LOOP
      (WHEN (>= I '4) (GO SB-LOOP::END-LOOP))
      (SB-LOOP::LOOP-DESETQ I (1+ I))
      (GO SB-LOOP::NEXT-LOOP)
     SB-LOOP::END-LOOP)))

1. Loop Paths
   
   properties

   ID: d3503f8e-eebb-4c8c-8ebe-a343dbc9e0e0
   CREATED: <2025-11-26 Wed 21:33>
   

   • loop paths tie in with the sequence and in particular the iterator/simple-iterator protocols
   • historically ANSI CL supports 'inclusive' iteration, although very uncommon/extinct in modern code
   • for X being the Y of Z
   • for X being Z and its Ys
   • built-in paths implemented for:
     • hash-table-keys
     • hash-table-values
     • external-symbols/present-symbols
     • elements (sequences)

1.3.2. FREEZE-TYPE

1.3.3. CTYPE

1.3.4. DEFTRANSFORM

(sb-c:defknown wat (T T) *)
(sb-c:deftransform wat ((x y) (string string) *) 
  `(string-wat x y))
(defun wat (x y)
  (if (and (numberp x)
           (numberp y))
      (+ x y)
      (concatenate 'string x y)))

(defun string-wat (x y)
  (declare (optimize (speed 3) (safety 0))
           (string x y))
  (concatenate 'string x y "watpow"))

(let ((a (concatenate 'string "bo" "b"))
      (b (concatenate 'string "dole")))
  (wat a b))

bobdole

1.3.5. Heap Object Layout

1.3.6. Code Component

1.3.7. Type Tags

1. Low Tags
   
   properties

   CREATED: <2025-01-17 Fri 15:50>
   ID: fd50e430-8a51-406a-96bd-ae6a1cf73bdd
   

   Tags for the main low-level types are stored in the low n (usually three) bits to identify the type of a machine word. Certain constraints apply: ,* EVEN-FIXNUM-LOWTAG and ODD-FIXNUM-LOWTAG must be 0 and 4: code which shifts left two places to convert raw integers to tagged fixnums is ubiquitous. ,* LIST-POINTER-LOWTAG + N-WORD-BYTES = OTHER-POINTER-LOWTAG: NIL is both a cons and a symbol (at the same address) and depends on this. See the definition of SYMBOL in objdef.lisp ,* OTHER-IMMEDIATE-0-LOWTAG are spaced 4 apart: various code wants to iterate through these. (This is not true on PPC64) (These are just the ones we know about as of sbcl-0.7.1.22. There might easily be more, since these values have stayed highly constrained for more than a decade, an inviting target for inventive abstraction-phobic maintainers.:-)

   Another way to look at lowtags is that there is no one lowtag length. On 32-bit platforms, fixnums and other-immediates have a lowtag length of two bits, and pointers have a lowtag length of three bits. On 64-bit platforms, fixnums and pointers gain an extra bit, and six "pad" lowtags waste the extra encoding space so obtained.

   x00 – fixnum x10 – other-immediate 001 – instance-pointer 011 – list-pointer 101 – fun-pointer 111 – other-pointer

   If you change the tag layout, check the various functions in src/runtime/runtime.h to see if they need to be updated, along with print_obj() in src/runtime/print.c, possibly 'late-objdef.lisp' and possibly the code in src/code/room.

   • see early-objdef.lisp

   #define SBCL_GENESIS_CONSTANTS
   #define FIXNUM_TAG_MASK 1 /* 0x1 */
   #define N_FIXNUM_TAG_BITS 1 /* 0x1 */
   #define N_LOWTAG_BITS 4 /* 0x4 */
   #define N_WIDETAG_BITS 8 /* 0x8 */
   #define N_WORD_BYTES 8 /* 0x8 */
   #define LOWTAG_MASK 15 /* 0xF */
   #define N_WORD_BITS 64 /* 0x40 */
   #define WIDETAG_MASK 255 /* 0xFF */
   #define SHORT_HEADER_MAX_WORDS 32767 /* 0x7FFF */
   
   #define EVEN_FIXNUM_LOWTAG 0 /* 0x0 */
   #define OTHER_IMMEDIATE_0_LOWTAG 1 /* 0x1 */
   #define PAD0_LOWTAG 2 /* 0x2 */
   #define INSTANCE_POINTER_LOWTAG 3 /* 0x3 */
   #define PAD1_LOWTAG 4 /* 0x4 */
   #define OTHER_IMMEDIATE_1_LOWTAG 5 /* 0x5 */
   #define PAD2_LOWTAG 6 /* 0x6 */
   #define LIST_POINTER_LOWTAG 7 /* 0x7 */
   #define ODD_FIXNUM_LOWTAG 8 /* 0x8 */
   #define OTHER_IMMEDIATE_2_LOWTAG 9 /* 0x9 */
   #define PAD3_LOWTAG 10 /* 0xA */
   #define FUN_POINTER_LOWTAG 11 /* 0xB */
   #define PAD4_LOWTAG 12 /* 0xC */
   #define OTHER_IMMEDIATE_3_LOWTAG 13 /* 0xD */
   #define PAD5_LOWTAG 14 /* 0xE */
   #define OTHER_POINTER_LOWTAG 15 /* 0xF */
   

   Objects allocated on the Lisp heap are aligned to a double-word boundary, leaving the low-order bits (which would normally identify a particular octet within the first two words) available for use to hold type information. This turns out to be three bits on 32-bit systems and four bits on 64-bit systems.

   Of these 8 or 16 tags, we have some constraints for allocation:

   We need 6 of the low 8 bits of the word for widetags, meaning that one out of every four lowtags must be an other-immediate lowtag.

   We have four pointer types. Instance (struct and CLOS) pointers, function pointers, list pointers, and other pointers.

   fixnums are required to have their lowtags be comprised entirely of zeros.

   There are additional constraints around the ordering of the pointer types, particularly with respect to list pointers (the NIL-cons hack).

   Complicating this issue is that while the lowtag space is three or four bits wide, some of the lowtags are effectively narrower. The other-immediate tags effectively have a two-bit lowtag, and fixnums have historically been one bit narrower than the other lowtags (thus even-fixnum-lowtag and odd-fixnum-lowtag) though with the recent work on wider fixnums on 64-bit systems this is no longer necessarily so.

   +lowtags+
   

   SB-VM:EVEN-FIXNUM-LOWTAG

   SB-VM:OTHER-IMMEDIATE-0-LOWTAG

   SB-VM:PAD0-LOWTAG

   SB-VM:INSTANCE-POINTER-LOWTAG

   SB-VM:PAD1-LOWTAG

   SB-VM:OTHER-IMMEDIATE-1-LOWTAG

   SB-VM:PAD2-LOWTAG

   SB-VM:LIST-POINTER-LOWTAG

   SB-VM:ODD-FIXNUM-LOWTAG

   SB-VM:OTHER-IMMEDIATE-2-LOWTAG

   SB-VM:PAD3-LOWTAG

   SB-VM:FUN-POINTER-LOWTAG

   SB-VM:PAD4-LOWTAG

   SB-VM:OTHER-IMMEDIATE-3-LOWTAG

   SB-VM:PAD5-LOWTAG

   SB-VM:OTHER-POINTER-LOWTAG

   1. The NIL-cons Hack
      
      properties

      ID: e345e677-e9e1-496f-8f58-2f77e3a44000
      CREATED: <2025-06-10 Tue 13:09>
      

      As an “optimization”, the symbol nil has list-pointer-lowtag rather than other-pointer-lowtag, and is aligned in memory so that the value and hash slots are the car and cdr of the cons, with both slots containing nil. This allows for car and cdr to simply do a lowtag test and slot access instead of having to explicitly test for nil, at the cost of requiring all symbol type tests and slot accesses to test for nil.

2. Wide Tags
   
   properties

   ID: 57ff5711-3cb1-4602-bb74-5c6e46e152e7
   CREATED: <2025-06-10 Tue 13:04>
   

   • bits = 8 (full octet)
   • mask = 255 ^
   • see early-objdef.lisp

   As a widetag is only eight bits wide but a heap object header takes a full machine word, there is an extra 24 or 56 bits of space available for unboxed data storage in each heap object. This space is called the “header value”, and is used for various purposes depending on the type of heap object in question.

   Widetags are used for three purposes. First, to provide type information for immediate (non-pointer) data such as characters. Second, to provide “marker” values for things such as unbound slots. Third, to provide type information for objects stored on the heap.

   Because widetags are used for immediate data they must have a lowtag component. This ends up being the other-immediate lowtags. For various reasons it was deemed convenient for widetags to be no more than eight bits wide, and with 27 or more distinct array types (depending on build-time configuration), seven numeric types, markers, and non-numeric heap object headers there ends up being more than 32 widetags required (though less than 64). This combination of factors leads to the requirement that one out of every four lowtags be an other-immediate lowtag.

   Other-immediates are the lowtag part of widetag values. Due to the constraints of widetag allocation, one out of every four lowtags must be a widetag (alternately, the width of the other-immediate lowtag is two bits).

   +widetags+
   

   SB-VM:UNBOUND-MARKER-WIDETAG

   SB-VM:BIGNUM-WIDETAG

   SB-VM:RATIO-WIDETAG

   SB-VM:SINGLE-FLOAT-WIDETAG

   SB-VM:DOUBLE-FLOAT-WIDETAG

   SB-VM:COMPLEX-RATIONAL-WIDETAG

   SB-VM:COMPLEX-SINGLE-FLOAT-WIDETAG

   SB-VM:COMPLEX-DOUBLE-FLOAT-WIDETAG

   SB-VM:SYMBOL-WIDETAG

   SB-VM:SAP-WIDETAG

   SB-VM:CODE-HEADER-WIDETAG

   SB-VM:INSTANCE-WIDETAG

   SB-VM:FUNCALLABLE-INSTANCE-WIDETAG

   SB-VM:SIMPLE-FUN-WIDETAG

   SB-VM:CLOSURE-WIDETAG

   SB-VM:VALUE-CELL-WIDETAG

   SB-VM:CHARACTER-WIDETAG

   SB-VM:WEAK-POINTER-WIDETAG

   SB-VM:FDEFN-WIDETAG

   SB-VM:SIMD-PACK-WIDETAG

   SB-VM:SIMD-PACK-256-WIDETAG

   SB-VM:FILLER-WIDETAG

   SB-VM:SIMPLE-ARRAY-WIDETAG

   SB-VM:SIMPLE-ARRAY-NIL-WIDETAG

   SB-VM:SIMPLE-VECTOR-WIDETAG

   SB-VM:SIMPLE-BIT-VECTOR-WIDETAG

   SB-VM:SIMPLE-ARRAY-UNSIGNED-BYTE-2-WIDETAG

   SB-VM:SIMPLE-ARRAY-UNSIGNED-BYTE-4-WIDETAG

   SB-VM:SIMPLE-ARRAY-UNSIGNED-BYTE-7-WIDETAG

   SB-VM:SIMPLE-ARRAY-UNSIGNED-BYTE-8-WIDETAG

   SB-VM:SIMPLE-ARRAY-UNSIGNED-BYTE-15-WIDETAG

   SB-VM:SIMPLE-ARRAY-UNSIGNED-BYTE-16-WIDETAG

   SB-VM:SIMPLE-ARRAY-UNSIGNED-BYTE-31-WIDETAG

   SB-VM:SIMPLE-ARRAY-UNSIGNED-BYTE-32-WIDETAG

   SB-VM:SIMPLE-ARRAY-UNSIGNED-FIXNUM-WIDETAG

   SB-VM:SIMPLE-ARRAY-UNSIGNED-BYTE-63-WIDETAG

   SB-VM:SIMPLE-ARRAY-UNSIGNED-BYTE-64-WIDETAG

   SB-VM:SIMPLE-ARRAY-SIGNED-BYTE-8-WIDETAG

   SB-VM:SIMPLE-ARRAY-SIGNED-BYTE-16-WIDETAG

   SB-VM:SIMPLE-ARRAY-SIGNED-BYTE-32-WIDETAG

   SB-VM:SIMPLE-ARRAY-FIXNUM-WIDETAG

   SB-VM:SIMPLE-ARRAY-SIGNED-BYTE-64-WIDETAG

   SB-VM:SIMPLE-ARRAY-SINGLE-FLOAT-WIDETAG

   SB-VM:SIMPLE-ARRAY-DOUBLE-FLOAT-WIDETAG

   SB-VM:SIMPLE-ARRAY-COMPLEX-SINGLE-FLOAT-WIDETAG

   SB-VM:SIMPLE-ARRAY-COMPLEX-DOUBLE-FLOAT-WIDETAG

   SB-VM:SIMPLE-BASE-STRING-WIDETAG

   SB-VM:SIMPLE-CHARACTER-STRING-WIDETAG

   SB-VM:COMPLEX-BASE-STRING-WIDETAG

   SB-VM:COMPLEX-CHARACTER-STRING-WIDETAG

   SB-VM:COMPLEX-BIT-VECTOR-WIDETAG

   SB-VM:COMPLEX-VECTOR-WIDETAG

   SB-VM:COMPLEX-ARRAY-WIDETAG

1.3.8. Bindings

1.3.9. Data Structures

1. Trees
   
   properties

   ID: ce61d665-fb20-44fb-990b-2ebdd11a038a
   CREATED: <2025-08-17 Sun 17:41>
   

   edges

   nil
   1. Brother Tree
      
      properties

      ID: 39a7e730-9190-4ad1-a309-aef4c9af2d4a
      CREATED: <2025-08-17 Sun 17:41>
      

      edges

      [2025-08-17 Sun 17:41] – 1-2 Brother Trees
      

      
      

      in general these are better than redblack trees

      An element of type Tree T is called a brother tree iff:

      a

      all nullary nodes have the same depth (height condition)

      b

      each unary node has a binary brother (brother condition)

      This implies that the root of a brother tree is not unary and that a unary node has not a unary child. Put positively, a unary node only occurs as the child of a binary node.

      – Ralf Hinze, Purely Functional 1-2 Brother Trees

   2. AVL Tree
      
      properties

      ID: 21d645aa-940e-454d-8f86-4df8d9084a8c
      CREATED: <2025-08-17 Sun 17:41>
      
   3. Red-Black Tree
      
      properties

      ID: 32e166aa-add7-490c-83da-246d2cccd011
      CREATED: <2025-08-17 Sun 17:42>
      

      edges

      [2025-08-17 Sun 17:42] – UPenn Red-Black Trees Lecture
      

      
      
2. SB-LOCKLESS
   
   properties

   ID: 7ce03245-5fe3-4e8a-90b5-833fd4c53803
   CREATED: <2025-08-17 Sun 18:21>
   
   1. Lockfree List
      
      properties

      ID: 2a85508c-7f32-4dca-98e8-e89b2ffde3ff
      CREATED: <2025-08-17 Sun 18:21>
      

      • target-lflist.lisp

        Lockfree singly-linked lists using the algorithm of https://timharris.uk/papers/2001-disc.pdf. The algorithm as described requires being able to change the low-order bit of a pointer from 0 to 1 to mark pending deletions. Java implementations support this through a wrapper object known as AtomicMarkableReference. SBCL directly supports the mark bit by using the lowtag.

        The changes to GC to support this code were as follows:

        ,* If an instance is flagged as being a LFlist node, then the first data slot is treated as an instance pointer even if it missing its tag bits.

        ,* Since you can't pin an object that you don't a-priori have a tagged pointer to, pinning a lockfree list node may implicitly pin not only that node but also the successor node, since there would otherwise be no way to reconstruct (in Lisp) a tagged pointer to the successor of a node pending deletion. Pinning a node always binds PINNED-OBJECTS and never relies on conservative stack scan even for the architectures that have conservative stack. arm64 and x86-64 uses PSEUDO-ATOMIC, which produces shorter code than WITH-PINNED-OBJECTS.

        ,* Copying a lockfree list node tries to copy the successor nodes into adjacent memory just like copying a chain of cons cells. This is inessential but nice.

        ,* verify_range() knows how to verify the 'next' pointer even when it looks like a fixnum. Without this it would have been more difficult to test the above.

        The remaining issue is relatively unimportant: neither traceroot nor DO-REFERENCED-OBJECT can follow untagged pointers. This is potentially more of an annoyance than it is a bug.

   2. Lockfree Hash Tables
      
      properties

      ID: 618f6721-594c-42a5-8d7d-61445861e4d8
      CREATED: <2025-08-17 Sun 18:21>
      

      • target-lfhash.lisp http://trac.clozure.com/ccl/wiki/Internals/LockFreeHashTables https://github.com/boundary/high-scale-lib/blob/master/src/main/java/org/cliffc/high_scale_lib/NonBlockingHashMap.java

        The basic hashable is a lightweight one using prime number sizing strategy, and a secondary hash for re-probing that is not necessarily co-prime with the table size (as it would be, ideally), and no support for deletion.

        The lock-free logic differs from each of the preceding reference algorithms. The Java algorithm is truly lock-free: death of any thread will never impede progress in other threads. The CCL algorithm is only quasi-lock-free, as is ours. Were a rehashing thread to terminate abnormally while holding the rehash mutex, all other threads will likely starve at some point.

        Unlike the CCL algorithm, we allow reading/writing concurrently with rehash. Most operations will never notice that the rehasher has acquired a mutex, because the only case where writers compete for the mutex is in trying to claim a new cell in a storage vector that is being transported, and where the rehasher has already visited the desired cell. Since the rehasher will never re-visit a cell, it disallows updates that it could not perceive. The Java algorithm has additional complexity imposed upon it by the feature that rehashing work is parceling out fairly to threads, whereas we avoid that by having one rehasher transport all cells.

      1. Split Ordered List
         
         properties

         ID: 9c11fbb6-0e98-4e46-9248-b706ae1624a1
         CREATED: <2025-08-17 Sun 18:29>
         

         • solist.lisp

           Lockfree hash table and hash set based on Shalev & Shavit paper https://www.cs.tau.ac.il/~afek/SplitOrderListHashSS03.pdf

           This table never uses a mutex for any operation, including resizing. The paper does not describe in detail how to deal with hash collisions, so this implementation imposes a requirement that either there be no hash collisions, or there be a partial order on keys such that any keys whose hashes collide can be ordered. Usually there would be a total order.

           Also we change the way a hash implies a bucket. Instead of reversing the bits of the hash, we use bits from left-to-right, so that as the bucket vector doubles, one more bit of lesser significance comes into play.

           Some possible uses: ,* classoid -> layout hash-tables in classoid-subclasses will maybe fix some deadlock issues by removing locks? total ordering by an opaque globally unique ID. (These are currently not created as :synchronized because access is guarded by the world lock) If all of the table are replaced by split-ordered lists, the net memory used decreases, although at larger sizes the split-ordered list consumes more memory.

           ,* exact remembered sets for GC in immobile space

1.3.10. Symbols of Interest

sb-sys:*runtime-dlhandle*
sb-fasl:+fasl-file-version+
sb-fasl:+backend-fasl-file-implementation+
sb-debug:print-backtrace
sb-debug:map-backtrace
sb-pretty:pprint-dispatch-table
sb-lockless:
sb-ext:simd-pack
sb-walker:define-walker-template
sb-walker:macroexpand-all
sb-walker:walk-form
sb-kernel:empty-type
sb-kernel:*eval-calls*
sb-kernel:*gc-pin-code-pages*
sb-kernel:*restart-clusters*
sb-kernel:*save-lisp-clobbered-globals*
sb-kernel:*top-level-form-p*
sb-kernel:*universal-fun-type*
sb-kernel:*universal-type*
sb-kernel:*wild-type*
sb-kernel:+simd-pack-element-types+
(sb-vm:memory-usage)
(sb-vm:boxed-context-register)
(sb-vm:c-find-heap->arena)
(sb-vm:copy-number-to-heap)
(sb-vm:dump-arena-objects)
(sb-vm:fixnumize)
(sb-vm:rewind-arena)
(sb-vm:show-heap->arena)
(sb-vm:with/without-arena)
(sb-cltl2:{augment-environment,compiler-let,define-declaration,parse-macro})
(sb-cltl2:{declaration-information, variable-information, function-information})
sb-di:
sb-assem:
sb-md5:
sb-regalloc:
sb-disassem:

1.3.11. Core Format

1.3.12. Arenas

1.3.13. Early Extensions

1. Binding*
   
   properties

   ID: 36fc490c-6af2-477b-9d69-67aec305bb26
   CREATED: <2025-11-27 Thu 21:01>
   

   (binding* ({(names initial-value [flag])}*) body) FLAG may be NIL or :EXIT-IF-NULL

   This form unites LET*, MULTIPLE-VALUE-BIND and AWHEN. Any name in a list of names may be NIL to ignore the respective value. If NAMES itself is nil, the initial-value form is evaluated only for effect.

   Clauses with no flag and one binding are equivalent to LET.

   Caution: don't use declarations of the form (<non-builtin-type-id> <var>) before the INFO database is set up in building the cross-compiler, or you will probably lose. Of course, since some other host Lisps don't seem to think that's acceptable syntax anyway, you're pretty much prevented from writing it.

2. Hash Cache Utility
   
   properties

   ID: f66c31eb-099e-4245-aab1-b397c1dda900
   CREATED: <2025-11-27 Thu 20:50>
   

   • src/code/early-extensions.lisp

     Define a hash cache that associates some number of argument values with a result value. The TEST-FUNCTION paired with each ARG-NAME is used to compare the value for that arg in a cache entry with a supplied arg. The TEST-FUNCTION must not error when passed NIL as its first arg, but need not return any particular value. TEST-FUNCTION may be any thing that can be placed in CAR position.

     This code used to store all the arguments / return values directly in the cache vector. This was both interrupt- and thread-unsafe, since it was possible that *-CACHE-ENTER would scribble over a region of the cache vector which *-CACHE-LOOKUP had only partially processed. Instead we now store the contents of each cache bucket as a separate array, which is stored in the appropriate cell in the cache vector. A new bucket array is created every time *-CACHE-ENTER is called, and the old ones are never modified. This means that *-CACHE-LOOKUP will always work with a set of consistent data. The overhead caused by consing new buckets seems to be insignificant on the grand scale of things. – JES, 2006-11-02

     NAME is used to define these functions: <name>-CACHE-LOOKUP Arg* See whether there is an entry for the specified ARGs in the cache. If not present, the :DEFAULT keyword (default NIL) determines the result(s). <name>-CACHE-ENTER Arg* Value* Encache the association of the specified args with VALUE. <name>-CACHE-CLEAR Reinitialize the cache, invalidating all entries and allowing the arguments and result values to be GC'd.

     These other keywords are defined: :HASH-BITS <n> The size of the cache as a power of 2. :HASH-FUNCTION function Some thing that can be placed in CAR position which will compute a fixnum with at least (* 2 <hash-bits>) of information in it. :VALUES <n> the number of return values cached for each function call

     • !DEFINE-HASH-CACHE, WITH-CACHE, DEFUN-CACHED aren't exported but various other symbols are:
       • DROP-ALL-HASH-CACHES
       • ALLOC-HASH-CACHE

1.3.14. DEFINE-VOP

;;; Define the symbol NAME to be a Virtual OPeration in the compiler.
;;; If specified, INHERITS is the name of a VOP that we default
;;; unspecified information from. Each SPEC is a list beginning with a
;;; keyword indicating the interpretation of the other forms in the
;;; SPEC:
;;;
;;; :ARGS {(Name {Key Value}*)}*
;;; :RESULTS {(Name {Key Value}*)}*
;;;     The Args and Results are specifications of the operand TNs passed
;;;     to the VOP. If there is an inherited VOP, any unspecified options
;;;     are defaulted from the inherited argument (or result) of the same
;;;     name. The following operand options are defined:
;;;
;;;     :SCs (SC*)
;;;         :SCs specifies good SCs for this operand. Other SCs will
;;;         be penalized according to move costs. A load TN will be
;;;         allocated if necessary, guaranteeing that the operand is
;;;         always one of the specified SCs.
;;;
;;;     :LOAD-TN Load-Name
;;;         Load-Name is bound to the load TN allocated for this
;;;         operand, or to NIL if no load TN was allocated.
;;;
;;;     :LOAD-IF EXPRESSION
;;;         Controls whether automatic operand loading is done.
;;;         EXPRESSION is evaluated with the fixed operand TNs bound.
;;;         If EXPRESSION is true, then loading is done and the variable
;;;         is bound to the load TN in the generator body. Otherwise,
;;;         loading is not done, and the variable is bound to the actual
;;;         operand.
;;;
;;;     :MORE T-or-NIL
;;;         If specified, NAME is bound to the TN-REF for the first
;;;         argument or result following the fixed arguments or results.
;;;         A :MORE operand must appear last, and cannot be targeted or
;;;         restricted.
;;;
;;;     :TARGET Operand
;;;         This operand is targeted to the named operand, indicating a
;;;         desire to pack in the same location. Not legal for results.
;;;
;;;     :FROM Time-Spec
;;;     :TO Time-Spec
;;;         Specify the beginning or end of the operand's lifetime.
;;;         :FROM can only be used with results, and :TO only with
;;;         arguments. The default for the N'th argument/result is
;;;         (:ARGUMENT N)/(:RESULT N). These options are necessary
;;;         primarily when operands are read or written out of order.
;;;
;;; :CONDITIONAL [Condition-descriptor+]
;;;     This is used in place of :RESULTS with conditional branch VOPs.
;;;     There are no result values: the result is a transfer of control.
;;;     The target label is passed as the first :INFO arg. The second
;;;     :INFO arg is true if the sense of the test should be negated.
;;;     A side effect is to set the PREDICATE attribute for functions
;;;     in the :TRANSLATE option.
;;;
;;;     If some condition descriptors are provided, this is a flag-setting
;;;     VOP. Descriptors are interpreted in an architecture-dependent
;;;     manner. See the BRANCH-IF VOP in $ARCH/pred.lisp.
;;;
;;; :TEMPORARY ({Key Value}*) Name*
;;;     Allocate a temporary TN for each Name, binding that variable to
;;;     the TN within the body of the generators. In addition to :TARGET
;;;     (which is is the same as for operands), the following options are
;;;     defined:
;;;
;;;     :SC SC-Name
;;;     :OFFSET SB-Offset
;;;         Force the temporary to be allocated in the specified SC
;;;         with the specified offset. Offset is evaluated at
;;;         macroexpand time. If Offset is omitted, the register
;;;         allocator chooses a free location in SC. If both SC and
;;;         Offset are omitted, then the temporary is packed according
;;;         to its primitive type.
;;;
;;;     :FROM Time-Spec
;;;     :TO Time-Spec
;;;         Similar to the argument/result option, this specifies the
;;;         start and end of the temporaries' lives. The defaults are
;;;         :LOAD and :SAVE, i.e. the duration of the VOP. The other
;;;         intervening phases are :ARGUMENT, :EVAL and :RESULT.
;;;         Non-zero sub-phases can be specified by a list, e.g. by
;;;         default the second argument's life ends at (:ARGUMENT 1).
;;;
;;; :GENERATOR Cost Form*
;;;     Specifies the translation into assembly code. Cost is the
;;;     estimated cost of the code emitted by this generator. The body
;;;     is arbitrary Lisp code that emits the assembly language
;;;     translation of the VOP. An ASSEMBLE form is wrapped around
;;;     the body, so code may be emitted by using the local INST macro.
;;;     During the evaluation of the body, the names of the operands
;;;     and temporaries are bound to the actual TNs.
;;;
;;; :INFO Name*
;;;     Define some magic arguments that are passed directly to the code
;;;     generator. The corresponding trailing arguments to VOP or
;;;     %PRIMITIVE are stored in the VOP structure. Within the body
;;;     of the generators, the named variables are bound to these
;;;     values. Except in the case of :CONDITIONAL VOPs, :INFO arguments
;;;     cannot be specified for VOPS that are the direct translation
;;;     for a function (specified by :TRANSLATE).
;;;
;;; :IGNORE Name*
;;;     Causes the named variables to be declared IGNORE in the
;;;     generator body.
;;;
;;; :VARIANT Thing*
;;; :VARIANT-VARS Name*
;;;     These options provide a way to parameterize families of VOPs
;;;     that differ only trivially. :VARIANT makes the specified
;;;     evaluated Things be the "variant" associated with this VOP.
;;;     :VARIANT-VARS causes the named variables to be bound to the
;;;     corresponding Things within the body of the generator.
;;;
;;; :VARIANT-COST Cost
;;;     Specifies the cost of this VOP, overriding the cost of any
;;;     inherited generator.
;;;
;;; :NOTE {String | NIL}
;;;     A short noun-like phrase describing what this VOP "does", i.e.
;;;     the implementation strategy. If supplied, efficiency notes will
;;;     be generated when type uncertainty prevents :TRANSLATE from
;;;     working. NIL inhibits any efficiency note.
;;;
;;; :ARG-TYPES    {* | PType | (:OR PType*) | (:CONSTANT Type)}*
;;; :RESULT-TYPES {* | PType | (:OR PType*)}*
;;;     Specify the template type restrictions used for automatic
;;;     translation. If there is a :MORE operand, the last type is the
;;;     more type. :CONSTANT specifies that the argument must be a
;;;     compile-time constant of the specified Lisp type. The constant
;;;     values of :CONSTANT arguments are passed as additional :INFO
;;;     arguments rather than as :ARGS.
;;;
;;; :TRANSLATE Name*
;;;     This option causes the VOP template to be entered as an IR2
;;;     translation for the named functions.
;;;
;;; :POLICY {:SMALL | :SMALL-SAFE | :FAST | :SAFE | :FAST-SAFE}
;;;     Specifies the policy under which this VOP is the best translation.
;;;
;;; :GUARD Form
;;;     Specifies a Form that is evaluated in the global environment.
;;;     If form returns NIL, then emission of this VOP is prohibited
;;;     even when all other restrictions are met.
;;;     As an additional possibility, if Form is a lambda expression,
;;;     then it is funcalled with the node under consideration.
;;;
;;; :VOP-VAR Name
;;; :NODE-VAR Name
;;;     In the generator, bind the specified variable to the VOP or
;;;     the Node that generated this VOP.
;;;
;;; :SAVE-P {NIL | T | :COMPUTE-ONLY | :FORCE-TO-STACK}
;;;     Indicates how a VOP wants live registers saved.
;;;
;;; :MOVE-ARGS {NIL | :FULL-CALL | :LOCAL-CALL | :KNOWN-RETURN}
;;;     Indicates if and how the more args should be moved into a
;;;     different frame.
(defmacro define-vop ((&optional name inherits) &body specs)
  (%define-vop name inherits specs t))

1.3.15. Aliens   ffi

1. Implementation
   
   properties

   ID: 4614d042-f2ae-49ea-a7d9-a29c4aed3210
   CREATED: <2025-11-22 Sat 20:37>
   

   The implementation of Aliens in SBCL is extremely complex and not well documented. It has received minor updates over the years and is derived from the CMU CL alien internals. Much of the original CMU documentation does not apply or is missing.

   • files
     • compiler/saptrans.lisp,{target}/sap.lisp (sap)
     • compiler/aliencomp.lisp
     • type-class.lisp (alien-type)
     • globaldb.lisp (info)
     • alien-type.lisp (earlyish alien-type def)
     • alieneval.lisp (Alien parts which are not part of the compiler)
     • alien-callback.lisp (Callback-specific parts which are not part of the compiler)

   notes

   • type-class.lisp

     • alien-type (struct)

       (defstruct (alien-type
                   (:copier nil)
                   (:constructor make-alien-type
                       (&key hash bits alignment
                        &aux (alignment
                              (or alignment (guess-alignment bits))))))
         ;; HASH is a derived from the contents, not just a pseudo-random number.
         ;; The highest 5 bits of it imply the alien-type-class.
         ;; (There are curretly 16 type-classes with room for expansion)
         ;; These slots should be read-only, but alas they get modified by
         ;; the parsers for ENUM and RECORD types.
         ;; Maybe the sign bit could be used to indicate hash-consed versus non-hash-consed
         ;; and so we can know whether it is a safe operation to mutate the thing?
         (hash 0 :type (and sb-xc:fixnum unsigned-byte))
         ;; It's quasi-bogus that these can be NULL - it occurs when and only when parsing
         ;; a structure type that involves self-recursion I think. The :type option is inadequate
         ;; to enforce that atoms like {SINGLE,DOUBLE-}FLOAT always have an integer here.
         (bits nil :type (or null unsigned-byte))
         (alignment nil :type (or null unsigned-byte)))
       

     • alien-type-type (type-model)
       • from what I understand this is effectively the 'ctype' designator for 'alien' specifically - see *type-class-list*
   • globaldb.lisp
     • heap-alien-info (struct)
       • type, alien-name, datap (data or code?)
     • :alien-info (info-type)
       • :kind (:primitive (in sbcl) :defined (user) or :unknown)

       • :translator

         (info :alien-type :translator '*)
         

         #<FUNCTION SB-ALIEN::ALIEN-*-TYPE-TRANSLATOR>
         T
         

       • :definition (only for user defined types)

         (info :alien-type :definition 'rocksdb:rocksdb)
         

         #<SB-ALIEN-INTERNALS:ALIEN-TYPE (:STRUCT ROCKSDB::ROCKSDB-T) NIL {1203FE4073}>
         T
         

       • :source-location :alien-type

         (info :source-location :alien-type 'rocksdb:rocksdb)
         

         #S(SB-C:DEFINITION-SOURCE-LOCATION
            :NAMESTRING "/home/ellis/comp/core/ffi/rocksdb/types.lisp"
            :INDICES 98305)
         T
         

       • :variable :kind (eq kind :alien)
       • info :variable :alien-info form
   • alieneval.lisp
     • alien-type (these are defined by the user via DEFINE-ALIEN-TYPE)
       • ROOT (inaccessible)
     • alien-type-class (class templates for ALIEN-TYPE)
       • alien-value (most alien-types include this)

       • *

         (define-alien-type-translator * (to &environment env)
           (make-alien-pointer-type :to (if (eq to t) nil (parse-alien-type to env))))
         

       • pointer, c-string
       • mem-block (includes alien-value)
         • array
         • record
           • alien-record-field (a plain struct with name,type,offset)
           • *struct-type-cache*, *union-type-cache*
           • type-translators: struct union

         • function/values

           ;;; not documented in CMU CL:-(
           ;;;
           ;;; reverse engineering observations:
           ;;;   * seems to be set when translating return values
           ;;;   * seems to enable the translation of (VALUES), which is the
           ;;;     Lisp idiom for C's return type "void" (which is likely
           ;;;     why it's set when when translating return values)
           (defvar *values-type-okay* nil)
           
           ;;; Calling-convention spec, typically one of predefined keywords.
           ;;; Add or remove as needed for target platform.  It makes sense to
           ;;; support :cdecl everywhere.
           ;;;
           ;;; Null convention is supposed to be platform-specific most-universal
           ;;; callout convention. For x86, SBCL calls foreign functions in a way
           ;;; allowing them to be either stdcall or cdecl; null convention is
           ;;; appropriate here, as it is for specifying callbacks that could be
           ;;; accepted by foreign code both in cdecl and stdcall form.
           (def!type calling-convention () `(or null (member :stdcall :cdecl)))
           ;;; ...
           ;;; The safe default is to assume that everything is varargs.
           ;;; On x86-64 we have to emit a spurious instruction because of it.
           ;;; So until all users fix their lambda lists to be explicit about &REST
           ;;; (which is never gonna happen), be backward-compatible, unless
           ;;; locally toggled to get rid of noise instructions if so inclined.
           (defglobal *alien-fun-type-varargs-default* :unspecified)
           

           • function type-class inherits from mem-block
             • type-translator for function
           • values does not
             • type-translator for values
       • alien variables
         • (uses heap-alien-info from globaldb.lisp)
         • local-alien-info (plain struct)
           • info about local aliens (stack or register) - WITH-ALIEN builds one of these structs and LOCAL-ALIEN and friends communicate info about how it is represented.
       • cas-alien
       • sb-sys:extern-alien-name
       • caching constructors (hashsets) - one for each alien-type
       • acyclic-type-p

       • helpers

         (defun integer-type (bits signed) ; trivial helpers
           (make-alien-integer-type :bits bits :signed signed))
         (defun boolean-type (bits)
           (make-alien-boolean-type :bits bits :signed nil))
         (defun single-float-type () (parse-alien-type 'single-float nil))
         (defun double-float-type () (parse-alien-type 'double-float nil))
         (defun sap-type () (parse-alien-type 'system-area-pointer nil))
         

       • make-type-load-form
         • emit single sexpr to handle all levels of structure nesting
   • alien-callback.lisp
     • *alien-callbacks* *alien-callback-functions*
     • free-alien-callable
     • parse-alien-fun-type
     • alien-lambda2 ?
     • *alien-callables* (lisp symbols -> alien callable functions)
     • define-alien-callable / with-alien-callable
     • make-alien-callable-function-unbound alien-callable-function
     • sb-thread::enter-foreign-callback

   • KINDS are KEYWORDS

     (defun unparse-alien-record-kind (kind)
       (case kind
         (:struct 'struct)
         (:union 'union)
         (t '???)))
     

     • i guess just for alien-enum-type-kind (vector or alist) and alien-record-type-kind

   (let ((atyp (sb-alien::parse-alien-type 'sb-alien:int nil)))
     (print atyp)
     (print (sb-alien::unparse-alien-type atyp))
     ;; second arg accepts :NORMAL (the default) or :RESULT (alien function
     ;; return values) - see :ALIEN-REP method for INTEGER (listed below).
     (print (sb-alien::compute-alien-rep-type atyp))
     (print (sb-alien::compute-lisp-rep-type atyp)))
   

   
   #<ALIEN-TYPE (SB-ALIEN:SIGNED 32)> 
   (SB-ALIEN:SIGNED 32) 
   (SIGNED-BYTE 32) 
   (SIGNED-BYTE 32) 
   

   (define-alien-type-method (integer :alien-rep) (type context)
     ;; When returning integer values that are narrower than a machine
     ;; register from a function, some platforms leave the higher bits of
     ;; the register uninitialized.  On those platforms, we use an
     ;; alien-rep of the full register width when checking for purposes
     ;; of return values and override the naturalize method to perform
     ;; the sign extension (in compiler/{arch}/c-call.lisp).
     (ecase context
       ((:normal #-(or x86 x86-64) :result)
        (list (if (alien-integer-type-signed type) 'signed-byte 'unsigned-byte)
              (alien-integer-type-bits type)))
       #+(or x86 x86-64)
       (:result
        (list (if (alien-integer-type-signed type) 'signed-byte 'unsigned-byte)
              (max (alien-integer-type-bits type)
                   sb-vm:n-machine-word-bits)))))
   
   ;;; As per the comment in the :ALIEN-REP method above, this is defined
   ;;; elsewhere for x86oids.
   #-(or x86 x86-64)
   (define-alien-type-method (integer :naturalize-gen) (type alien)
     (declare (ignore type))
     alien)
   

   (defconstant-eqx +method-slot-alist+
       '((:unparse . alien-type-class-unparse)
         (:type= . alien-type-class-type=)
         (:subtypep . alien-type-class-subtypep)
         (:lisp-rep . alien-type-class-lisp-rep)
         (:alien-rep . alien-type-class-alien-rep)
         (:extract-gen . alien-type-class-extract-gen)
         (:deposit-gen . alien-type-class-deposit-gen)
         (:naturalize-gen . alien-type-class-naturalize-gen)
         (:deport-gen . alien-type-class-deport-gen)
         (:deport-alloc-gen . alien-type-class-deport-alloc-gen)
         (:deport-pin-p . alien-type-class-deport-pin-p)
         ;; cast?
         (:arg-tn . alien-type-class-arg-tn)
         (:result-tn . alien-type-class-result-tn))
     #'equal)
   

   • compute-extract-lambda

     (sb-alien::compute-extract-lambda (parse-alien-type 'c-string nil))
     

     (LAMBDA (SB-ALIEN::SAP SB-ALIEN::OFFSET IGNORE)
       (DECLARE (TYPE SYSTEM-AREA-POINTER SB-ALIEN::SAP)
                (TYPE UNSIGNED-BYTE SB-ALIEN::OFFSET)
                (IGNORE IGNORE))
       (SB-ALIEN-INTERNALS:NATURALIZE
        (SB-SYS:SAP-REF-SAP SB-ALIEN::SAP (/ SB-ALIEN::OFFSET SB-VM:N-BYTE-BITS))
        '#<ALIEN-TYPE C-STRING>))
     

   • compute-naturalize-lambda

     (sb-alien::compute-naturalize-lambda (parse-alien-type 'c-string nil))
     

     (LAMBDA (ALIEN IGNORE)
       (DECLARE (IGNORE IGNORE))
       (IF (ZEROP (SB-SYS:SAP-INT ALIEN))
           NIL
           (SB-ALIEN::C-STRING-TO-STRING ALIEN
                                         (SB-ALIEN::C-STRING-EXTERNAL-FORMAT
                                          #<ALIEN-TYPE C-STRING>)
                                         (SB-ALIEN::ALIEN-C-STRING-TYPE-ELEMENT-TYPE
                                          #<ALIEN-TYPE C-STRING>))))
     

   • compute-deposit-lambda

     (sb-alien::compute-deposit-lambda (parse-alien-type 'c-string nil))
     

     (LAMBDA (SB-ALIEN::VALUE SB-ALIEN::SAP SB-ALIEN::OFFSET IGNORE)
       (DECLARE (TYPE SYSTEM-AREA-POINTER SB-ALIEN::SAP)
            (TYPE UNSIGNED-BYTE SB-ALIEN::OFFSET)
            (IGNORE IGNORE))
       (LET ((SB-ALIEN::ALLOC-TMP
          (SB-ALIEN-INTERNALS:DEPORT-ALLOC SB-ALIEN::VALUE
       				    '#<ALIEN-TYPE C-STRING>)))
         (SB-ALIEN-INTERNALS:MAYBE-WITH-PINNED-OBJECTS (SB-ALIEN::ALLOC-TMP)
         (#<ALIEN-TYPE C-STRING>)
       (LET ((SB-ALIEN::VALUE
              (SB-ALIEN-INTERNALS:DEPORT SB-ALIEN::ALLOC-TMP
       				  '#<ALIEN-TYPE C-STRING>)))
         (SETF (SB-SYS:SAP-REF-SAP SB-ALIEN::SAP
       			    (/ SB-ALIEN::OFFSET SB-VM:N-BYTE-BITS))
       	  SB-ALIEN::VALUE)
         (SB-ALIEN-INTERNALS:NATURALIZE SB-ALIEN::VALUE
       				 '#<ALIEN-TYPE C-STRING>)))))
     

   • compute-deport-lambda

     (print (sb-alien::compute-deport-lambda (parse-alien-type 'c-string nil)))
     

     
     (LAMBDA (SB-ALIEN::VALUE IGNORE)
       (DECLARE
        (TYPE
         (OR NULL SIMPLE-STRING (ALIEN (* CHAR)) (SIMPLE-ARRAY (UNSIGNED-BYTE 8)))
         SB-ALIEN::VALUE)
        (IGNORE IGNORE))
       (ETYPECASE SB-ALIEN::VALUE
         (NULL (INT-SAP 0))
         ((ALIEN (* CHAR)) (SB-ALIEN:ALIEN-SAP SB-ALIEN::VALUE))
         (VECTOR (SB-SYS:VECTOR-SAP SB-ALIEN::VALUE)))) 
     

   • compute-deport-alloc-lambda

     (sb-alien::compute-deport-alloc-lambda (parse-alien-type 'c-string nil))
     

     (LAMBDA (SB-ALIEN::VALUE IGNORE)
       (DECLARE (IGNORE IGNORE))
       (ETYPECASE SB-ALIEN::VALUE
         (NULL NIL)
         ((ALIEN (* CHAR)) SB-ALIEN::VALUE)
         (T
          (SB-ALIEN::STRING-TO-C-STRING SB-ALIEN::VALUE
                                        (SB-ALIEN::C-STRING-EXTERNAL-FORMAT
                                         #<ALIEN-TYPE C-STRING>)))))
     

   • DEPORT and NATURALIZE translate between SAPs and lisp rep?
   • when no COMPUTE-ALIEN-LISP-TYPE is found (returns nil) - value is naturalized as an ALIEN-VALUE?
   • COMPUTE-ALIEN-REP-TYPE seems to default to SYSTEM-AREA-POINTER (unidentified memory)

1.3.16. SB-ASSEM   asm

1.3.17. Compiler   comp

1. derive-function-types
   
   properties

   ID: 76c64438-4db7-4318-8701-241d4f253782
   CREATED: <2025-03-23 Sun 15:05>
   

   DERIVE-FUNCTION-TYPES names a special variable: Value: NIL Documentation: Should the compiler assume that function types will never change, so that it can use type information inferred from current definitions to optimize code which uses those definitions? Setting this true gives non-ANSI, early-CMU-CL behavior. It can be useful for improving the efficiency of stable code.

2. Stack Allocation
   
   properties

   ID: 77d8f492-2707-43d5-893f-aeb14338568d
   CREATED: <2025-06-27 Fri 18:50>
   

   edges

   [2025-06-27 Fri 18:52] – info
   

   
   

   – Variable: stack-allocate-dynamic-extent If true (the default), the compiler believes ‘dynamic-extent’ declarations and stack allocates otherwise inaccessible parts of the object whenever possible.

   SBCL implements stack alloc for these calues when they're recognized as having dynamic extent:

   • ‘&rest’ lists

   • the results of ‘cons’, ‘list’, ‘list*’, and ‘vector’

   • the result of simple forms of ‘make-array’: stack allocation is possible only if the resulting array is known to be both simple and one-dimensional, and has a constant ‘:element-type’.

   Note: stack space is limited, so allocation of a large vector may cause stack overflow. Stack overflow checks are done except in zero ‘safety’ policies.

   • closures defined with ‘flet’ or ‘labels’ with a bound ‘dynamic-extent’ declaration.

   • anonymous closures defined with ‘lambda’

   • user-defined structures when the structure constructor defined using ‘defstruct’ has been declared ‘inline’

   Note: structures with "raw" slots can currently be stack-allocated only on x86 and x86-64. A "raw" slot is one whose declared type is a subtype of exactly one of: ‘double-float’, ‘single-float’, ‘(complex double-float)’, ‘(complex single-float)’, or ‘sb-ext:word’; but as an exception to the preceding, any subtype of ‘fixnum’ is not stored as raw despite also being a subtype of ‘sb-ext:word’.

   • otherwise-inaccessible parts of objects recognized to be dynamic extent. The support for detecting when this applies is very sophisticated. The compiler can do this detection when any value form for a variable contains conditional allocations, function calls, inlined functions, anonymous closures, or even other variables. This allows stack allocation of complex structures.

   ;;; Declaiming a structure constructor inline before definition makes
   ;;; stack allocation possible.
   (declaim (inline make-thing))
   (defstruct thing obj next)
   
   ;;; Stack allocation of various objects bound to DYNAMIC-EXTENT
   ;;; variables.
   (let* ((list (list 1 2 3))
          (nested (cons (list 1 2) (list* 3 4 (list 5))))
          (vector (make-array 3 :element-type 'single-float))
          (thing (make-thing :obj list
                 :next (make-thing :obj (make-array 3))))
          (closure (let ((y ...)) (lambda () y))))
     (declare (dynamic-extent list nested vector thing closure))
     ...)
   
   ;;; Stack allocation of objects assigned to DYNAMIC-EXTENT variables.
   (let ((x nil))
     (declare (dynamic-extent x))
     (setq x (list 1 2 3))
     (dotimes (i 10)
       (setq x (cons i x)))
     ...)
   
   ;;; Stack allocation of arguments to a local function is equivalent
   ;;; to stack allocation of local variable values.
   (flet ((f (x)
        (declare (dynamic-extent x))
        ...))
     ...
     (f (list 1 2 3))
     (f (cons (cons 1 2) (cons 3 4)))
     ...)
   
   ;;; Stack allocation of &REST lists
   (defun foo (&rest args)
     (declare (dynamic-extent args))
     ...)
   
   

   As a notable exception to recognizing otherwise inaccessible parts of other recognized dynamic extent values, SBCL does not as of 1.0.48.21 propagate dynamic-extentness through ‘&rest’ arguments - but another conforming implementation might, so portable code should not rely on this.

   (declaim (inline foo)) (defun foo (fun &rest arguments) (declare (dynamic-extent arguments)) (apply fun arguments))

   (defun bar (a) ;; SBCL will heap allocate the result of (LIST A), and stack allocate ;; only the spine of the &rest list – so this is safe, but unportable. ;; ;; Another implementation, including earlier versions of SBCL might consider ;; (LIST A) to be otherwise inaccessible and stack-allocate it as well! (foo #'car (list a)))

   If dynamic extent constraints specified in the Common Lisp standard are violated, the best that can happen is for the program to have garbage in variables and return values; more commonly, the system will crash.

   In particular, it is important to realize that this can interact in suprising ways with the otherwise inaccessible parts criterion:

   (let* ((a (list 1 2 3))
          (b (cons a a)))
     (declare (dynamic-extent b))
     ;; Unless A is accessed elsewhere as well, SBCL will consider
     ;; it to be otherwise inaccessible -- it can only be accessed
     ;; through B, after all -- and stack allocate it as well.
     ;;
     ;; Hence returning (CAR B) here is unsafe.
     ...)
   
   
   

3. Inlining
   
   properties

   ID: b260f2db-6eec-4f79-9f4f-f6e080062442
   

   ;;; An INLINEP value describes how a function is called. The values
   ;;; have these meanings:
   ;;;     NIL     No declaration seen: do whatever you feel like, but don't
   ;;;             dump an inline expansion.
   ;;; NOTINLINE  NOTINLINE declaration seen: always do full function call.
   ;;;    INLINE  INLINE declaration seen: save expansion, expanding to it
   ;;;             if policy favors.
   ;;; MAYBE-INLINE
   ;;;             Retain expansion, but only use it opportunistically.
   ;;;             MAYBE-INLINE is quite different from INLINE. As explained
   ;;;             by APD on #lisp 2005-11-26: "MAYBE-INLINE lambda is
   ;;;             instantiated once per component, INLINE - for all
   ;;;             references (even under #'without FUNCALL)."
   (deftype inlinep () '(member inline maybe-inline notinline nil))
   

1.3.18. LVARs

1.3.19. SB-KERNEL

1.5.1. sb-bsd-sockets

(defvar *protocols*
  `((:tcp ,sockint::ipproto_tcp "tcp" "TCP")
    (:udp ,sockint::ipproto_udp "udp" "UDP")
    (:ip ,sockint::ipproto_ip "ip" "IP")
    (:ipv6 ,sockint::ipproto_ipv6 "ipv6" "IPV6")
    (:icmp ,sockint::ipproto_icmp "icmp" "ICMP")
    (:igmp ,sockint::ipproto_igmp "igmp" "IGMP")
    (:raw ,sockint::ipproto_raw "raw" "RAW")))

1.5.2. sb-grovel

1.5.3. WAIT sb-fibers

1.5.4. sb-cltl2