SBCL Internals : tag bit

SBCL Internals
The pages on this CLiki-driven site can be edited by anybody at any time. No warranty of any kind can therefore be made; any implied warranties of merchantability or fitness for a particular purpose are expressly disclaimed

[ Home ]

[ Recent Changes ]

[ About CLiki ]

[ Text Formatting ]

Tag bits are applied to most objects and pointers so that we can tell what type they are. There's a two-level tag bit scheme

Main types - lowtag

Almost everything (both pointers and immediate objects) get the first level, which uses the three least-significant bits of the object

000    even-fixnum
001    instance-pointer
010    other-immediate-0
011    list-pointer
100    odd-fixnum
101    fun-pointer
110    other-immediate-1
111    other-pointer

For 64-bit ports the list is:

0000    even-fixnum
0001    instance-pointer
0010    other-immediate-0
0011    pad0
0100    pad1
0101    pad2
0110    other-immediate-1
0111    list-pointer
1000    odd-fixnum
1001    fun-pointer
1010    other-immediate-2
1011    pad3 
1100    pad4 
1101    pad5
1110    other-immediate-3
1111    other-pointer

This list was taken from src/compiler/generic/early-objdef.lisp sbcl-1.0.5.20. In case of contradiction, that file is normative, not this wiki. The most important thing to note here is probably the way that fixnums are dealt with. A bare integer can be converted into a fixnum by shifting it left 2 bits (3 bits on 64-bit platforms) so that the lsb ends up forming the msb of the tag. This means that

fixnums can be added/subtracted without having to worry about tags
indexing into vectors of four-byte objects using a fixnum involves no shifting (8-byte objects on 64-bit platforms).
we can take advantage of hardware tagging support on machines that have two bit hardware tags (though as the tagged insns on the SPARC have been deprecated, I don't think this is the advantage it used to be)
For x86, we can use the (base+offset) memory address mode to strip off the lowtag when used as a pointer without using any extra instructions.

There are other constraints as well, not all of which are obvious, or documented, or necessarily even known. If you find any not in the comments in early-objdef.lisp, please send patches. Note that there used to be a PPC-specific need to have function-pointer >= 4, but that's no longer necessary

Heap types - widetag

Objects in the heap get a little more information stored in them. Including the main tag bits (which is other-immediate-0 or other-immediate-1 there's a full eight bits of type information in the header words for these objects. Again, you can find out the numbers by looking at early-objdef.lisp.

The other 24 bits of a heap object header is according to CMUCL internals docs ignored, but that might be untrue.

Here is an example list of widetags from sbcl 1.0.5.20

(defenum (:suffix -widetag
          ;; The first widetag must be greater than SB!VM:LOWTAG-LIMIT
          ;; otherwise code in generic/early-type-vops will suffer
          ;; a long, horrible death.  --njf, 2004-08-09
          :start (+ (ash 1 n-lowtag-bits) other-immediate-0-lowtag)
          :step 4)
  ;; NOTE: the binary numbers off to the side are only valid for 32-bit
  ;; ports; add #b1000 if you want to know the values for 64-bit ports.
  ;; And note that the numbers get a little scrambled further down.
  ;;   --njf, 2004-08-09
  bignum                            ; 00001010
  ratio                             ; 00001110
  single-float                      ; 00010010
  double-float                      ; 00010110
  complex                           ; 00011010
  complex-single-float              ; 00011110
  complex-double-float              ; 00100010

  code-header                       ; 00100110

  simple-fun-header                 ; 00101010
  closure-header                    ; 00101110
  funcallable-instance-header       ; 00110010

  return-pc-header                  ; 00110110
  value-cell-header                 ; 00111010
  symbol-header                     ; 00111110
  character                         ; 01000010
  sap                               ; 01000110
  unbound-marker                    ; 01001010
  weak-pointer                      ; 01001110
  instance-header                   ; 01010010
  fdefn                             ; 01010110

  no-tls-value-marker               ; 01011010
  #!-(and sb-lutex sb-thread)
  unused01
  #!+(and sb-lutex sb-thread)
  lutex                             ; 01011110
  unused02                          ; 01100010
  unused03                          ; 01100110
  unused04                          ; 01101010
  unused05                          ; 01101110
  unused06                          ; 01110010
  unused07                          ; 01110110
  #!+#.(cl:if (cl:= 32 sb!vm:n-word-bits) '(and) '(or))
  unused08                          ; 01111010
  #!+#.(cl:if (cl:= 32 sb!vm:n-word-bits) '(and) '(or))
  unused09                          ; 01111110

  #!+#.(cl:if (cl:= 32 sb!vm:n-word-bits) '(and) '(or))
  unused10                          ; 10000010
  #!+#.(cl:if (cl:= 32 sb!vm:n-word-bits) '(and) '(or))
  unused11                          ; 10000110

  simple-array-unsigned-byte-2      ; 10001010
  simple-array-unsigned-byte-4      ; 10001110
  simple-array-unsigned-byte-7      ; 10010010
  simple-array-unsigned-byte-8      ; 10010110
  simple-array-unsigned-byte-15     ; 10011010
  simple-array-unsigned-byte-16     ; 10011110
  simple-array-nil                  ; 10100010
  simple-base-string                ; 10100110
  #!+sb-unicode simple-character-string
  simple-bit-vector                 ; 10101010
  simple-vector                     ; 10101110
  #!+#.(cl:if (cl:= 32 sb!vm:n-word-bits) '(and) '(or))
  simple-array-unsigned-byte-29     ; 10110010
  simple-array-unsigned-byte-31     ; 10110110
  simple-array-unsigned-byte-32     ; 10111010
  #!+#.(cl:if (cl:= 64 sb!vm:n-word-bits) '(and) '(or))
  simple-array-unsigned-byte-60
  #!+#.(cl:if (cl:= 64 sb!vm:n-word-bits) '(and) '(or))
  simple-array-unsigned-byte-63
  #!+#.(cl:if (cl:= 64 sb!vm:n-word-bits) '(and) '(or))
  simple-array-unsigned-byte-64
  simple-array-signed-byte-8        ; 10111110
  simple-array-signed-byte-16       ; 11000010
  #!+#.(cl:if (cl:= 32 sb!vm:n-word-bits) '(and) '(or))
  simple-array-signed-byte-30       ; 11000110
  simple-array-signed-byte-32       ; 11001010
  #!+#.(cl:if (cl:= 64 sb!vm:n-word-bits) '(and) '(or))
  simple-array-signed-byte-61
  #!+#.(cl:if (cl:= 64 sb!vm:n-word-bits) '(and) '(or))
  simple-array-signed-byte-64
  simple-array-single-float         ; 11001110
  simple-array-double-float         ; 11010010
  simple-array-complex-single-float ; 11010110
  simple-array-complex-double-float ; 11011010
  simple-array                      ; 11011110
  complex-vector-nil                ; 11100010
  complex-base-string               ; 11100110
  #!+sb-unicode complex-character-string
  complex-bit-vector                ; 11101010
  complex-vector                    ; 11101110
  complex-array                     ; 11110010

  #!+#.(cl:if (cl:= 32 sb!vm:n-word-bits) '(and) '(or))
  unused12                          ; 11110110
  #!+(and #.(cl:if (cl:= 32 sb!vm:n-word-bits) '(and) '(or))
          (not sb-unicode))
  unused13                          ; 11111010
  #!+(and #.(cl:if (cl:= 32 sb!vm:n-word-bits) '(and) '(or))
          (not sb-unicode))
  unused14                          ; 11111110
)

Garbage Collection

Inside the garbage collector there is a 256-element table, indexed by widetag, containing functions that will "transport" objects from the space that is being collected to some "newspace".

This page is linked from: gdb lowtag PPC

CLiki pages can be edited by anyone at any time. Imagine a fearsomely comprehensive disclaimer of liability. Now fear, comprehensively