src/runtime/mgc1.go

   1 // Copyright 2012 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // Garbage collector (GC)
   6
   7 package runtime
   8
   9 const (
  10         // Four bits per word (see #defines below).
  11         gcBits             = 4
  12         wordsPerBitmapByte = 8 / gcBits
  13 )
  14
  15 const (
  16         // GC type info programs.
  17         // The programs allow to store type info required for GC in a compact form.
  18         // Most importantly arrays take O(1) space instead of O(n).
  19         // The program grammar is:
  20         //
  21         // Program = {Block} "insEnd"
  22         // Block = Data | Array
  23         // Data = "insData" DataSize DataBlock
  24         // DataSize = int // size of the DataBlock in bit pairs, 1 byte
  25         // DataBlock = binary // dense GC mask (2 bits per word) of size ]DataSize/4[ bytes
  26         // Array = "insArray" ArrayLen Block "insArrayEnd"
  27         // ArrayLen = int // length of the array, 8 bytes (4 bytes for 32-bit arch)
  28         //
  29         // Each instruction (insData, insArray, etc) is 1 byte.
  30         // For example, for type struct { x []byte; y [20]struct{ z int; w *byte }; }
  31         // the program looks as:
  32         //
  33         // insData 3 (BitsPointer BitsScalar BitsScalar)
  34         //      insArray 20 insData 2 (BitsScalar BitsPointer) insArrayEnd insEnd
  35         //
  36         // Total size of the program is 17 bytes (13 bytes on 32-bits).
  37         // The corresponding GC mask would take 43 bytes (it would be repeated
  38         // because the type has odd number of words).
  39         insData = 1 + iota
  40         insArray
  41         insArrayEnd
  42         insEnd
  43 )
  44
  45 const (
  46         // Pointer map
  47         _BitsPerPointer  = 2
  48         _BitsMask        = (1 << _BitsPerPointer) - 1
  49         _PointersPerByte = 8 / _BitsPerPointer
  50
  51         // If you change these, also change scanblock.
  52         // scanblock does "if(bits == BitsScalar || bits == BitsDead)" as "if(bits <= BitsScalar)".
  53         _BitsDead          = 0
  54         _BitsScalar        = 1                                // 01
  55         _BitsPointer       = 2                                // 10
  56         _BitsCheckMarkXor  = 1                                // 10
  57         _BitsScalarMarked  = _BitsScalar ^ _BitsCheckMarkXor  // 00
  58         _BitsPointerMarked = _BitsPointer ^ _BitsCheckMarkXor // 11
  59
  60         // 64 bytes cover objects of size 1024/512 on 64/32 bits, respectively.
  61         _MaxGCMask = 65536 // TODO(rsc): change back to 64
  62 )
  63
  64 // Bits in per-word bitmap.
  65 // #defines because we shift the values beyond 32 bits.
  66 //
  67 // Each word in the bitmap describes wordsPerBitmapWord words
  68 // of heap memory.  There are 4 bitmap bits dedicated to each heap word,
  69 // so on a 64-bit system there is one bitmap word per 16 heap words.
  70 //
  71 // The bitmap starts at mheap.arena_start and extends *backward* from
  72 // there.  On a 64-bit system the off'th word in the arena is tracked by
  73 // the off/16+1'th word before mheap.arena_start.  (On a 32-bit system,
  74 // the only difference is that the divisor is 8.)
  75 const (
  76         bitBoundary = 1 // boundary of an object
  77         bitMarked   = 2 // marked object
  78         bitMask     = bitBoundary | bitMarked
  79         bitPtrMask  = _BitsMask << 2
  80 )