Initial revision
[sbcl.git] / doc / cmucl / internals / internal-design.txt
1
2 \f
3 ;;;; Terminology.
4
5 OBJECT
6    An object is one of the following:
7       a single word containing immediate data (characters, fixnums, etc)
8       a single word pointing to an object     (structures, conses, etc.)
9    These are tagged with three low-tag bits as described in the section
10    "Tagging".  This is synonymous with DESCRIPTOR.
11
12 LISP OBJECT
13    A Lisp object is a high-level object discussed as a data type in Common
14    Lisp: The Language.
15
16 DATA-BLOCK
17    A data-block is a dual-word aligned block of memory that either manifests a
18    Lisp object (vectors, code, symbols, etc.) or helps manage a Lisp object on
19    the heap (array header, function header, etc.).
20
21 DESCRIPTOR
22    A descriptor is a tagged, single-word object.  It either contains immediate
23    data or a pointer to data.  This is synonymous with OBJECT.
24
25 WORD
26    A word is a 32-bit quantity.
27
28
29 \f
30 ;;;; Tagging.
31
32 The following is a key of the three bit low-tagging scheme:
33    000 even fixnum
34    001 function pointer
35    010 other-immediate (header-words, characters, symbol-value trap value, etc.)
36    011 list pointer
37    100 odd fixnum
38    101 structure pointer
39    110 unused
40    111 other-pointer to data-blocks (other than conses, structures,
41                                      and functions)
42
43 This taging scheme forces a dual-word alignment of data-blocks on the heap, but
44 this can be pretty negligible:
45    RATIOS and COMPLEX must have a header-word anyway since they are not a
46       major type.  This wastes one word for these infrequent data-blocks since
47       they require two words for the data.
48    BIGNUMS must have a header-word and probably contain only one other word
49       anyway, so we probably don't waste any words here.  Most bignums just
50       barely overflow fixnums, that is by a bit or two.
51    Single and double FLOATS?
52       no waste
53       one word wasted
54    SYMBOLS are dual-word aligned with the header-word.
55    Everything else is vector-like including code, so these probably take up
56       so many words that one extra one doesn't matter.
57
58
59 \f
60 ;;;; GC Comments.
61
62 Data-Blocks comprise only descriptors, or they contain immediate data and raw
63 bits interpreted by the system.  GC must skip the latter when scanning the
64 heap, so it does not look at a word of raw bits and interpret it as a pointer
65 descriptor.  These data-blocks require headers for GC as well as for operations
66 that need to know how to interpret the raw bits.  When GC is scanning, and it
67 sees a header-word, then it can determine how to skip that data-block if
68 necessary.  Header-Words are tagged as other-immediates.  See the sections
69 "Other-Immediates" and "Data-Blocks and Header-Words" for comments on
70 distinguishing header-words from other-immediate data.  This distinction is
71 necessary since we scan through data-blocks containing only descriptors just as
72 we scan through the heap looking for header-words introducing data-blocks.
73
74 Data-Blocks containing only descriptors do not require header-words for GC
75 since the entire data-block can be scanned by GC a word at a time, taking
76 whatever action is necessary or appropriate for the data in that slot.  For
77 example, a cons is referenced by a descriptor with a specific tag, and the
78 system always knows the size of this data-block.  When GC encounters a pointer
79 to a cons, it can transport it into the new space, and when scanning, it can
80 simply scan the two words manifesting the cons interpreting each word as a
81 descriptor.  Actually there is no cons tag, but a list tag, so we make sure the
82 cons is not nil when appropriate.  A header may still be desired if the pointer
83 to the data-block does not contain enough information to adequately maintain
84 the data-block.  An example of this is a simple-vector containing only
85 descriptor slots, and we attach a header-word because the descriptor pointing
86 to the vector lacks necessary information -- the type of the vector's elements,
87 its length, etc.
88
89 There is no need for a major tag for GC forwarding pointers.  Since the tag
90 bits are in the low end of the word, a range check on the start and end of old
91 space tells you if you need to move the thing.  This is all GC overhead.
92
93
94 \f
95 ;;;; Structures.
96
97 Structures comprise a word for each slot in the definition in addition to one
98 word, a type slot which is a pointer descriptor.  This points to a structure
99 describing the data-block as a structure, a defstruct-descriptor object.  When
100 operating on a structure, doing a structure test can be done by simply checking
101 the tag bits on the pointer descriptor referencing it.  As described in section
102 "GC Comments", data-blocks such as those representing structures may avoid
103 having a header-word since they are GC-scanable without any problem.  This
104 saves two words for every structure instance.
105
106
107 \f
108 ;;;; Fixnums.
109
110 A fixnum has one of the following formats in 32 bits:
111     -------------------------------------------------------
112     |        30 bit 2's complement even integer   | 0 0 0 |
113     -------------------------------------------------------
114 or
115     -------------------------------------------------------
116     |        30 bit 2's complement odd integer    | 1 0 0 |
117     -------------------------------------------------------
118
119 Effectively, there is one tag for immediate integers, two zeros.  This buys one
120 more bit for fixnums, and now when these numbers index into simple-vectors or
121 offset into memory, they point to word boundaries on 32-bit, byte-addressable
122 machines.  That is, no shifting need occur to use the number directly as an
123 offset.
124
125 This format has another advantage on byte-addressable machines when fixnums are
126 offsets into vector-like data-blocks, including structures.  Even though we
127 previously mentioned data-blocks are dual-word aligned, most indexing and slot
128 accessing is word aligned, and so are fixnums with effectively two tag bits.
129
130 Two tags also allow better usage of special instructions on some machines that
131 can deal with two low-tag bits but not three.
132
133 Since the two bits are zeros, we avoid having to mask them off before using the
134 words for arithmetic, but division and multiplication require special shifting.
135
136
137 \f
138 ;;;; Other-immediates.
139
140 An other-immediate has the following format:
141    ----------------------------------------------------------------
142    |   Data (24 bits)        | Type (8 bits with low-tag) | 0 1 0 |
143    ----------------------------------------------------------------
144
145 The system uses eight bits of type when checking types and defining system
146 constants.  This allows allows for 32 distinct other-immediate objects given
147 the three low-tag bits tied down.
148
149 The system uses this format for characters, SYMBOL-VALUE unbound trap value,
150 and header-words for data-blocks on the heap.  The type codes are laid out to
151 facilitate range checks for common subtypes; for example, all numbers will have
152 contiguous type codes which are distinct from the contiguous array type codes.
153 See section "Data-Blocks and Other-immediates Typing" for details.
154
155
156 \f
157 ;;;; Data-Blocks and Header-Word Format.
158
159 Pointers to data-blocks have the following format:
160    ----------------------------------------------------------------
161    |      Dual-word address of data-block (29 bits)       | 1 1 1 |
162    ----------------------------------------------------------------
163
164 The word pointed to by the above descriptor is a header-word, and it has the
165 same format as an other-immediate:
166    ----------------------------------------------------------------
167    |   Data (24 bits)        | Type (8 bits with low-tag) | 0 1 0 |
168    ----------------------------------------------------------------
169
170 This is convenient for scanning the heap when GC'ing, but it does mean that
171 whenever GC encounters an other-immediate word, it has to do a range check on
172 the low byte to see if it is a header-word or just a character (for example).
173 This is easily acceptable performance hit for scanning.
174
175 The system interprets the data portion of the header-word for non-vector
176 data-blocks as the word length excluding the header-word.  For example, the
177 data field of the header for ratio and complex numbers is two, one word each
178 for the numerator and denominator or for the real and imaginary parts.
179
180 For vectors and data-blocks representing Lisp objects stored like vectors, the
181 system ignores the data portion of the header-word:
182    ----------------------------------------------------------------
183    | Unused Data (24 bits)   | Type (8 bits with low-tag) | 0 1 0 |
184    ----------------------------------------------------------------
185    |           Element Length of Vector (30 bits)           | 0 0 | 
186    ----------------------------------------------------------------
187
188 Using a separate word allows for much larger vectors, and it allows LENGTH to
189 simply access a single word without masking or shifting.  Similarly, the header
190 for complex arrays and vectors has a second word, following the header-word,
191 the system uses for the fill pointer, so computing the length of any array is
192 the same code sequence.
193
194
195 \f
196 ;;;; Data-Blocks and Other-immediates Typing.
197
198 These are the other-immediate types.  We specify them including all low eight
199 bits, including the other-immediate tag, so we can think of the type bits as
200 one type -- not an other-immediate major type and a subtype.  Also, fetching a
201 byte and comparing it against a constant is more efficient than wasting even a
202 small amount of time shifting out the other-immediate tag to compare against a
203 five bit constant.
204
205            Number   (< 30)
206 00000 010      bignum                                           10
207 00000 010      ratio                                            14
208 00000 010      single-float                                     18
209 00000 010      double-float                                     22
210 00000 010      complex                                          26
211
212            Array   (>= 30 code 86)
213               Simple-Array   (>= 20 code 70)
214 00000 010           simple-array                                30
215                  Vector  (>= 34 code 82)
216 00000 010           simple-string                               34
217 00000 010           simple-bit-vector                           38
218 00000 010           simple-vector                               42
219 00000 010           (simple-array (unsigned-byte 2) (*))        46
220 00000 010           (simple-array (unsigned-byte 4) (*))        50
221 00000 010           (simple-array (unsigned-byte 8) (*))        54
222 00000 010           (simple-array (unsigned-byte 16) (*))       58
223 00000 010           (simple-array (unsigned-byte 32) (*))       62
224 00000 010           (simple-array single-float (*))             66
225 00000 010           (simple-array double-float (*))             70
226 00000 010        complex-string                                 74
227 00000 010        complex-bit-vector                             78
228 00000 010        (array * (*))   -- general complex vector.     82
229 00000 010     complex-array                                     86
230
231 00000 010  code-header-type                                     90
232 00000 010  function-header-type                                 94
233 00000 010  closure-header-type                                  98
234 00000 010  funcallable-instance-header-type                     102
235 00000 010  unused-function-header-1-type                        106
236 00000 010  unused-function-header-2-type                        110
237 00000 010  unused-function-header-3-type                        114
238 00000 010  closure-function-header-type                         118
239 00000 010  return-pc-header-type                                122
240 00000 010  value-cell-header-type                               126
241 00000 010  symbol-header-type                                   130
242 00000 010  base-character-type                                  134
243 00000 010  system-area-pointer-type (header type)               138
244 00000 010  unbound-marker                                       142
245 00000 010  weak-pointer-type                                    146
246
247
248 \f
249 ;;;; Strings.
250
251 All strings in the system are C-null terminated.  This saves copying the bytes
252 when calling out to C.  The only time this wastes memory is when the string
253 contains a multiple of eight characters, and then the system allocates two more
254 words (since Lisp objects are dual-word aligned) to hold the C-null byte.
255 Since the system will make heavy use of C routines for systems calls and
256 libraries that save reimplementation of higher level operating system
257 functionality (such as pathname resolution or current directory computation),
258 saving on copying strings for C should make C call out more efficient.
259
260 The length word in a string header, see section "Data-Blocks and Header-Word
261 Format", counts only the characters truly in the Common Lisp string.
262 Allocation and GC will have to know to handle the extra C-null byte, and GC
263 already has to deal with rounding up various objects to dual-word alignment.
264
265
266 \f
267 ;;;; Symbols and NIL.
268
269 Symbol data-block has the following format:
270     -------------------------------------------------------
271     |     5 (data-block words)     | Symbol Type (8 bits) |
272     -------------------------------------------------------
273     |                   Value Descriptor                  |
274     -------------------------------------------------------
275     |                   Function Pointer                  |
276     -------------------------------------------------------
277     |                 Raw Function Address                |
278     -------------------------------------------------------
279     |                    Setf Function                    |
280     -------------------------------------------------------
281     |                    Property List                    |
282     -------------------------------------------------------
283     |                      Print Name                     |
284     -------------------------------------------------------
285     |                       Package                       |
286     -------------------------------------------------------
287
288 Most of these slots are self-explanatory given what symbols must do in Common
289 Lisp, but a couple require comments.  We added the Raw Function Address slot to
290 speed up named call which is the most common calling convention.  This is a
291 non-descriptor slot, but since objects are dual word aligned, the value
292 inherently has fixnum low-tag bits.  The GC method for symbols must know to
293 update this slot.  The Setf Function slot is currently unused, but we had an
294 extra slot due to adding Raw Function Address since objects must be dual-word
295 aligned.
296
297 The issues with nil are that we want it to act like a symbol, and we need list
298 operations such as CAR and CDR to be fast on it.  CMU Common Lisp solves this
299 by putting nil as the first object in static space, where other global values
300 reside, so it has a known address in the system:
301     -------------------------------------------------------  <-- start static
302     |                           0                         |      space
303     -------------------------------------------------------
304     |     5 (data-block words)     | Symbol Type (8 bits) |
305     -------------------------------------------------------  <-- nil
306     |                       Value/CAR                     |
307     -------------------------------------------------------
308     |                     Definition/CDR                  |
309     -------------------------------------------------------
310     |                  Raw Function Address               |
311     -------------------------------------------------------
312     |                     Setf Function                   |
313     -------------------------------------------------------
314     |                     Property List                   |
315     -------------------------------------------------------
316     |                       Print Name                    |
317     -------------------------------------------------------
318     |                        Package                      |
319     -------------------------------------------------------
320     |                          ...                        |
321     -------------------------------------------------------
322 In addition, we make the list typed pointer to nil actually point past the
323 header word of the nil symbol data-block.  This has usefulness explained below.
324 The value and definition of nil are nil.  Therefore, any reference to nil used
325 as a list has quick list type checking, and CAR and CDR can go right through
326 the first and second words as if nil were a cons object.
327
328 When there is a reference to nil used as a symbol, the system adds offsets to
329 the address the same as it does for any symbol.  This works due to a
330 combination of nil pointing past the symbol header-word and the chosen list and
331 other-pointer type tags.  The list type tag is four less than the other-pointer
332 type tag, but nil points four additional bytes into its symbol data-block.
333
334
335 \f
336 ;;;; Array Headers.
337
338 The array-header data-block has the following format:
339    ----------------------------------------------------------------
340    | Header Len (24 bits) = Array Rank +5   | Array Type (8 bits) |
341    ----------------------------------------------------------------
342    |               Fill Pointer (30 bits)                   | 0 0 | 
343    ----------------------------------------------------------------
344    |               Available Elements (30 bits)             | 0 0 | 
345    ----------------------------------------------------------------
346    |               Data Vector (29 bits)                  | 1 1 1 | 
347    ----------------------------------------------------------------
348    |               Displacement (30 bits)                   | 0 0 | 
349    ----------------------------------------------------------------
350    |               Displacedp (29 bits) -- t or nil       | 1 1 1 | 
351    ----------------------------------------------------------------
352    |               Range of First Index (30 bits)           | 0 0 | 
353    ----------------------------------------------------------------
354                                   .
355                                   .
356                                   .
357
358 The array type in the header-word is one of the eight-bit patterns from section
359 "Data-Blocks and Other-immediates Typing", indicating that this is a complex
360 string, complex vector, complex bit-vector, or a multi-dimensional array.  The
361 data portion of the other-immediate word is the length of the array header
362 data-block.  Due to its format, its length is always five greater than the
363 array's number of dimensions.  The following words have the following
364 interpretations and types:
365    Fill Pointer
366       This is a fixnum indicating the number of elements in the data vector
367       actually in use.  This is the logical length of the array, and it is
368       typically the same value as the next slot.  This is the second word, so
369       LENGTH of any array, with or without an array header, is just four bytes
370       off the pointer to it.
371    Available Elements
372       This is a fixnum indicating the number of elements for which there is
373       space in the data vector.  This is greater than or equal to the logical
374       length of the array when it is a vector having a fill pointer.
375    Data Vector
376       This is a pointer descriptor referencing the actual data of the array.
377       This a data-block whose first word is a header-word with an array type as
378       described in sections "Data-Blocks and Header-Word Format" and
379       "Data-Blocks and Other-immediates Typing"
380    Displacement
381       This is a fixnum added to the computed row-major index for any array.
382       This is typically zero.
383    Displacedp
384       This is either t or nil.  This is separate from the displacement slot, so
385       most array accesses can simply add in the displacement slot.  The rare
386       need to know if an array is displaced costs one extra word in array
387       headers which probably aren't very frequent anyway.
388    Range of First Index
389       This is a fixnum indicating the number of elements in the first dimension
390       of the array.  Legal index values are zero to one less than this number
391       inclusively.  IF the array is zero-dimensional, this slot is
392       non-existent.
393    ... (remaining slots)
394       There is an additional slot in the header for each dimension of the
395       array.  These are the same as the Range of First Index slot.
396
397
398 \f
399 ;;;; Bignums.
400
401 Bignum data-blocks have the following format:
402     -------------------------------------------------------
403     |      Length (24 bits)        | Bignum Type (8 bits) |
404     -------------------------------------------------------
405     |                 least significant bits              |
406     -------------------------------------------------------
407                                 .
408                                 .
409                                 .
410
411 The elements contain the two's complement representation of the integer with
412 the least significant bits in the first element or closer to the header.  The
413 sign information is in the high end of the last element.
414
415
416
417 \f
418 ;;;; Code Data-Blocks.
419
420 A code data-block is the run-time representation of a "component".  A component
421 is a connected portion of a program's flow graph that is compiled as a single
422 unit, and it contains code for many functions.  Some of these functions are
423 callable from outside of the component, and these are termed "entry points".
424
425 Each entry point has an associated user-visible function data-block (of type
426 FUNCTION).  The full call convention provides for calling an entry point
427 specified by a function object.
428
429 Although all of the function data-blocks for a component's entry points appear
430 to the user as distinct objects, the system keeps all of the code in a single
431 code data-block.  The user-visible function object is actually a pointer into
432 the middle of a code data-block.  This allows any control transfer within a
433 component to be done using a relative branch.
434
435 Besides a function object, there are other kinds of references into the middle
436 of a code data-block.  Control transfer into a function also occurs at the
437 return-PC for a call.  The system represents a return-PC somewhat similarly to
438 a function, so GC can also recognize a return-PC as a reference to a code
439 data-block.
440
441 It is incorrect to think of a code data-block as a concatenation of "function
442 data-blocks".  Code for a function is not emitted in any particular order with
443 respect to that function's function-header (if any).  The code following a
444 function-header may only be a branch to some other location where the
445 function's "real" definition is.
446
447
448 The following are the three kinds of pointers to code data-blocks:
449    Code pointer (labeled A below):
450       A code pointer is a descriptor, with other-pointer low-tag bits, pointing
451       to the beginning of the code data-block.  The code pointer for the
452       currently running function is always kept in a register (CODE).  In
453       addition to allowing loading of non-immediate constants, this also serves
454       to represent the currently running function to the debugger.
455    Return-PC (labeled B below):
456       The return-PC is a descriptor, with other-pointer low-tag bits, pointing
457       to a location for a function call.  Note that this location contains no
458       descriptors other than the one word of immediate data, so GC can treat
459       return-PC locations the same as instructions.
460    Function (labeled C below):
461       A function is a descriptor, with function low-tag bits, that is user
462       callable.  When a function header is referenced from a closure or from
463       the function header's self-pointer, the pointer has other-pointer low-tag
464       bits, instead of function low-tag bits.  This ensures that the internal
465       function data-block associated with a closure appears to be uncallable
466       (although users should never see such an object anyway).
467
468       Information about functions that is only useful for entry points is kept
469       in some descriptors following the function's self-pointer descriptor.
470       All of these together with the function's header-word are known as the
471       "function header".  GC must be able to locate the function header.  We
472       provide for this by chaining together the function headers in a NIL
473       terminated list kept in a known slot in the code data-block.
474
475
476 A code data-block has the following format:
477    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++  <-- A
478    |  Header-Word count (24 bits)         |  %Code-Type (8 bits)  |
479    ----------------------------------------------------------------
480    |  Number of code words (fixnum tag)                           |
481    ----------------------------------------------------------------
482    |  Pointer to first function header (other-pointer tag)        |
483    ----------------------------------------------------------------
484    |  Debug information (structure tag)                           |
485    ----------------------------------------------------------------
486    |  First constant (a descriptor)                               |
487    ----------------------------------------------------------------
488    |  ...                                                         |
489    ----------------------------------------------------------------
490    |  Last constant (and last word of code header)                |
491    ----------------------------------------------------------------
492    |  Some instructions (non-descriptor)                          |
493    ----------------------------------------------------------------
494    |     (pad to dual-word boundary if necessary)                 |
495    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++  <-- B
496    |  Word offset from code header (24)   |  %Return-PC-Type (8)  |
497    ----------------------------------------------------------------
498    |  First instruction after return                              |
499    ----------------------------------------------------------------
500    |  ... more code and return-PC header-words                    |
501    ----------------------------------------------------------------
502    |     (pad to dual-word boundary if necessary)                 |
503    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++  <-- C
504    |  Offset from code header (24)  |  %Function-Header-Type (8)  |
505    ----------------------------------------------------------------
506    |  Self-pointer back to previous word (with other-pointer tag) |
507    ----------------------------------------------------------------
508    |  Pointer to next function (other-pointer low-tag) or NIL     |
509    ----------------------------------------------------------------
510    |  Function name (a string or a symbol)                        |
511    ----------------------------------------------------------------
512    |  Function debug arglist (a string)                           |
513    ----------------------------------------------------------------
514    |  Function type (a list-style function type specifier)        |
515    ----------------------------------------------------------------
516    |  Start of instructions for function (non-descriptor)         |
517    ----------------------------------------------------------------
518    |  More function headers and instructions and return PCs,      |
519    |  until we reach the total size of header-words + code        |
520    |  words.                                                      |
521    ----------------------------------------------------------------
522
523
524 The following are detailed slot descriptions:
525    Code data-block header-word:
526       The immediate data in the code data-block's header-word is the number of
527       leading descriptors in the code data-block, the fixed overhead words plus
528       the number of constants.  The first non-descriptor word, some code,
529       appears at this word offset from the header.
530    Number of code words:
531       The total number of non-header-words in the code data-block.  The total
532       word size of the code data-block is the sum of this slot and the
533       immediate header-word data of the previous slot.  The system accesses
534       this slot with the system constant, %Code-Code-Size-Slot, offset from the
535       header-word.
536    Pointer to first function header:
537       A NIL-terminated list of the function headers for all entry points to
538       this component.  The system accesses this slot with the system constant,
539       %Code-Entry-Points-Slot, offset from the header-word.
540    Debug information:
541       The DEBUG-INFO structure describing this component.  All information that
542       the debugger wants to get from a running function is kept in this
543       structure.  Since there are many functions, the current PC is used to
544       locate the appropriate debug information.  The system keeps the debug
545       information separate from the function data-block, since the currently
546       running function may not be an entry point.  There is no way to recover
547       the function object for the currently running function, since this
548       data-block may not exist.  The system accesses this slot with the system
549       constant, %Code-Debug-Info-Slot, offset from the header-word.
550    First constant ... last constant:
551       These are the constants referenced by the component, if there are any.
552       The system accesses the first constant slot with the system constant,
553       %Code-Constants-Offset, offset from the header-word.
554
555    Return-PC header word:
556       The immediate header-word data is the word offset from the enclosing code
557       data-block's header-word to this word.  This allows GC and the debugger
558       to easily recover the code data-block from a return-PC.  The code at the
559       return point restores the current code pointer using a subtract immediate
560       of the offset, which is known at compile time.
561
562    Function entry point header-word:
563       The immediate header-word data is the word offset from the enclosing code
564       data-block's header-word to this word.  This is the same as for the
565       retrun-PC header-word.
566    Self-pointer back to header-word:
567       In a non-closure function, this self-pointer to the previous header-word
568       allows the call sequence to always indirect through the second word in a
569       user callable function.  See section "Closure Format".  With a closure,
570       indirecting through the second word gets you a function header-word.  The
571       system ignores this slot in the function header for a closure, since it
572       has already indirected once, and this slot could be some random thing
573       that causes an error if you jump to it.  This pointer has an
574       other-pointer tag instead of a function pointer tag, indicating it is not
575       a user callable Lisp object.  The system accesses this slot with the
576       system constant, %Function-Code-Slot, offset from the function
577       header-word.
578    Pointer to next function:
579       This is the next link in the thread of entry point functions found in
580       this component.  This value is NIL when the current header is the last
581       entry point in the component.  The system accesses this slot with the
582       system constant, %Function-Header-Next-Slot, offset from the function
583       header-word.
584    Function name:
585       This function's name (for printing).  If the user defined this function
586       with DEFUN, then this is the defined symbol, otherwise it is a
587       descriptive string.  The system accesses this slot with the system
588       constant, %Function-Header-Name-Slot, offset from the function
589       header-word.
590    Function debug arglist:
591       A printed string representing the function's argument list, for human
592       readability.  If it is a macroexpansion function, then this is the
593       original DEFMACRO arglist, not the actual expander function arglist.  The
594       system accesses this slot with the system constant,
595       %Function-Header-Debug-Arglist-Slot, offset from the function
596       header-word.
597    Function type:
598       A list-style function type specifier representing the argument signature
599       and return types for this function.  For example,
600          (FUNCTION (FIXNUM FIXNUM FIXNUM) FIXNUM)
601       or
602          (FUNCTION (STRING &KEY (:START UNSIGNED-BYTE)) STRING)
603       This information is intended for machine readablilty, such as by the
604       compiler.  The system accesses this slot with the system constant,
605       %Function-Header-Type-Slot, offset from the function header-word.
606
607
608 \f
609 ;;;; Closure Format.
610
611 A closure data-block has the following format:
612    ----------------------------------------------------------------
613    |  Word size (24 bits)                | %Closure-Type (8 bits) |
614    ----------------------------------------------------------------
615    |  Pointer to function header (other-pointer low-tag)          |
616    ----------------------------------------------------------------
617    |                              .                               |
618    |                   Environment information                    |
619    |                              .                               |
620    ----------------------------------------------------------------
621
622
623 A closure descriptor has function low-tag bits.  This means that a descriptor
624 with function low-tag bits may point to either a function header or to a
625 closure.  The idea is that any callable Lisp object has function low-tag bits.
626 Insofar as call is concerned, we make the format of closures and non-closure
627 functions compatible.  This is the reason for the self-pointer in a function
628 header.  Whenever you have a callable object, you just jump through the second
629 word, offset some bytes, and go.
630
631
632 \f
633 ;;;; Function call.
634
635 Due to alignment requirements and low-tag codes, it is not possible to use a
636 hardware call instruction to compute the return-PC.  Instead the return-PC
637 for a call is computed by doing an add-immediate to the start of the code
638 data-block.
639
640 An advantage of using a single data-block to represent both the descriptor and
641 non-descriptor parts of a function is that both can be represented by a
642 single pointer.  This reduces the number of memory accesses that have to be
643 done in a full call.  For example, since the constant pool is implicit in a
644 return-PC, a call need only save the return-PC, rather than saving both the
645 return PC and the constant pool.
646
647
648 \f
649 ;;;; Memory Layout.
650
651 CMU Common Lisp has four spaces, read-only, static, dynamic-0, and dynamic-1.
652 Read-only contains objects that the system never modifies, moves, or reclaims.
653 Static space contains some global objects necessary for the system's runtime or
654 performance (since they are located at a known offset at a know address), and
655 the system never moves or reclaims these.  However, GC does need to scan static
656 space for references to moved objects.  Dynamic-0 and dynamic-1 are the two
657 heap areas for stop-and-copy GC algorithms.
658
659 What global objects are at the head of static space???
660    NIL
661    eval::*top-of-stack*
662    lisp::*current-catch-block*
663    lisp::*current-unwind-protect*
664    FLAGS (RT only)
665    BSP (RT only)
666    HEAP (RT only)
667
668 In addition to the above spaces, the system has a control stack, binding stack,
669 and a number stack.  The binding stack contains pairs of descriptors, a symbol
670 and its previous value.  The number stack is the same as the C stack, and the
671 system uses it for non-Lisp objects such as raw system pointers, saving
672 non-Lisp registers, parts of bignum computations, etc.
673
674
675 \f
676 ;;;; System Pointers.
677
678 The system pointers reference raw allocated memory, data returned by foreign
679 function calls, etc.  The system uses these when you need a pointer to a
680 non-Lisp block of memory, using an other-pointer.  This provides the greatest
681 flexibility by relieving contraints placed by having more direct references
682 that require descriptor type tags.
683
684 A system area pointer data-block has the following format:
685     -------------------------------------------------------
686     |     1 (data-block words)        | SAP Type (8 bits) |
687     -------------------------------------------------------
688     |                 system area pointer                 |
689     -------------------------------------------------------
690
691 "SAP" means "system area pointer", and much of our code contains this naming
692 scheme.  We don't currently restrict system pointers to one area of memory, but
693 if they do point onto the heap, it is up to the user to prevent being screwed
694 by GC or whatever.