size.go

     1  // Copyright 2009 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  package types
     6  
     7  import (
     8  	"math"
     9  	"sort"
    10  
    11  	"cmd/compile/internal/base"
    12  	"cmd/internal/src"
    13  	"internal/types/errors"
    14  )
    15  
    16  var PtrSize int
    17  
    18  var RegSize int
    19  
    20  // Slices in the runtime are represented by three components:
    21  //
    22  //	type slice struct {
    23  //		ptr unsafe.Pointer
    24  //		len int
    25  //		cap int
    26  //	}
    27  //
    28  // Strings in the runtime are represented by two components:
    29  //
    30  //	type string struct {
    31  //		ptr unsafe.Pointer
    32  //		len int
    33  //	}
    34  //
    35  // These variables are the offsets of fields and sizes of these structs.
    36  var (
    37  	SlicePtrOffset int64
    38  	SliceLenOffset int64
    39  	SliceCapOffset int64
    40  
    41  	SliceSize  int64
    42  	StringSize int64
    43  )
    44  
    45  var SkipSizeForTracing bool
    46  
    47  // typePos returns the position associated with t.
    48  // This is where t was declared or where it appeared as a type expression.
    49  func typePos(t *Type) src.XPos {
    50  	if pos := t.Pos(); pos.IsKnown() {
    51  		return pos
    52  	}
    53  	base.Fatalf("bad type: %v", t)
    54  	panic("unreachable")
    55  }
    56  
    57  // MaxWidth is the maximum size of a value on the target architecture.
    58  var MaxWidth int64
    59  
    60  // CalcSizeDisabled indicates whether it is safe
    61  // to calculate Types' widths and alignments. See CalcSize.
    62  var CalcSizeDisabled bool
    63  
    64  // machine size and rounding alignment is dictated around
    65  // the size of a pointer, set in gc.Main (see ../gc/main.go).
    66  var defercalc int
    67  
    68  // RoundUp rounds o to a multiple of r, r is a power of 2.
    69  func RoundUp(o int64, r int64) int64 {
    70  	if r < 1 || r > 8 || r&(r-1) != 0 {
    71  		base.Fatalf("Round %d", r)
    72  	}
    73  	return (o + r - 1) &^ (r - 1)
    74  }
    75  
    76  // expandiface computes the method set for interface type t by
    77  // expanding embedded interfaces.
    78  func expandiface(t *Type) {
    79  	seen := make(map[*Sym]*Field)
    80  	var methods []*Field
    81  
    82  	addMethod := func(m *Field, explicit bool) {
    83  		switch prev := seen[m.Sym]; {
    84  		case prev == nil:
    85  			seen[m.Sym] = m
    86  		case !explicit && Identical(m.Type, prev.Type):
    87  			return
    88  		default:
    89  			base.ErrorfAt(m.Pos, errors.DuplicateDecl, "duplicate method %s", m.Sym.Name)
    90  		}
    91  		methods = append(methods, m)
    92  	}
    93  
    94  	{
    95  		methods := t.Methods()
    96  		sort.SliceStable(methods, func(i, j int) bool {
    97  			mi, mj := methods[i], methods[j]
    98  
    99  			// Sort embedded types by type name (if any).
   100  			if mi.Sym == nil && mj.Sym == nil {
   101  				return mi.Type.Sym().Less(mj.Type.Sym())
   102  			}
   103  
   104  			// Sort methods before embedded types.
   105  			if mi.Sym == nil || mj.Sym == nil {
   106  				return mi.Sym != nil
   107  			}
   108  
   109  			// Sort methods by symbol name.
   110  			return mi.Sym.Less(mj.Sym)
   111  		})
   112  	}
   113  
   114  	for _, m := range t.Methods() {
   115  		if m.Sym == nil {
   116  			continue
   117  		}
   118  
   119  		CheckSize(m.Type)
   120  		addMethod(m, true)
   121  	}
   122  
   123  	for _, m := range t.Methods() {
   124  		if m.Sym != nil || m.Type == nil {
   125  			continue
   126  		}
   127  
   128  		// In 1.18, embedded types can be anything. In Go 1.17, we disallow
   129  		// embedding anything other than interfaces. This requirement was caught
   130  		// by types2 already, so allow non-interface here.
   131  		if !m.Type.IsInterface() {
   132  			continue
   133  		}
   134  
   135  		// Embedded interface: duplicate all methods
   136  		// and add to t's method set.
   137  		for _, t1 := range m.Type.AllMethods() {
   138  			f := NewField(m.Pos, t1.Sym, t1.Type)
   139  			addMethod(f, false)
   140  
   141  			// Clear position after typechecking, for consistency with types2.
   142  			f.Pos = src.NoXPos
   143  		}
   144  
   145  		// Clear position after typechecking, for consistency with types2.
   146  		m.Pos = src.NoXPos
   147  	}
   148  
   149  	sort.Sort(MethodsByName(methods))
   150  
   151  	if int64(len(methods)) >= MaxWidth/int64(PtrSize) {
   152  		base.ErrorfAt(typePos(t), 0, "interface too large")
   153  	}
   154  	for i, m := range methods {
   155  		m.Offset = int64(i) * int64(PtrSize)
   156  	}
   157  
   158  	t.SetAllMethods(methods)
   159  }
   160  
   161  // calcStructOffset computes the offsets of a sequence of fields,
   162  // starting at the given offset. It returns the resulting offset and
   163  // maximum field alignment.
   164  func calcStructOffset(t *Type, fields []*Field, offset int64) int64 {
   165  	for _, f := range fields {
   166  		CalcSize(f.Type)
   167  		offset = RoundUp(offset, int64(f.Type.align))
   168  
   169  		if t.IsStruct() { // param offsets depend on ABI
   170  			f.Offset = offset
   171  
   172  			// If type T contains a field F marked as not-in-heap,
   173  			// then T must also be a not-in-heap type. Otherwise,
   174  			// you could heap allocate T and then get a pointer F,
   175  			// which would be a heap pointer to a not-in-heap type.
   176  			if f.Type.NotInHeap() {
   177  				t.SetNotInHeap(true)
   178  			}
   179  		}
   180  
   181  		offset += f.Type.width
   182  
   183  		maxwidth := MaxWidth
   184  		// On 32-bit systems, reflect tables impose an additional constraint
   185  		// that each field start offset must fit in 31 bits.
   186  		if maxwidth < 1<<32 {
   187  			maxwidth = 1<<31 - 1
   188  		}
   189  		if offset >= maxwidth {
   190  			base.ErrorfAt(typePos(t), 0, "type %L too large", t)
   191  			offset = 8 // small but nonzero
   192  		}
   193  	}
   194  
   195  	return offset
   196  }
   197  
   198  func isAtomicStdPkg(p *Pkg) bool {
   199  	if p.Prefix == `""` {
   200  		panic("bad package prefix")
   201  	}
   202  	return p.Prefix == "sync/atomic" || p.Prefix == "runtime/internal/atomic"
   203  }
   204  
   205  // CalcSize calculates and stores the size and alignment for t.
   206  // If CalcSizeDisabled is set, and the size/alignment
   207  // have not already been calculated, it calls Fatal.
   208  // This is used to prevent data races in the back end.
   209  func CalcSize(t *Type) {
   210  	// Calling CalcSize when typecheck tracing enabled is not safe.
   211  	// See issue #33658.
   212  	if base.EnableTrace && SkipSizeForTracing {
   213  		return
   214  	}
   215  	if PtrSize == 0 {
   216  		// Assume this is a test.
   217  		return
   218  	}
   219  
   220  	if t == nil {
   221  		return
   222  	}
   223  
   224  	if t.width == -2 {
   225  		t.width = 0
   226  		t.align = 1
   227  		base.Fatalf("invalid recursive type %v", t)
   228  		return
   229  	}
   230  
   231  	if t.widthCalculated() {
   232  		return
   233  	}
   234  
   235  	if CalcSizeDisabled {
   236  		base.Fatalf("width not calculated: %v", t)
   237  	}
   238  
   239  	// defer CheckSize calls until after we're done
   240  	DeferCheckSize()
   241  
   242  	lno := base.Pos
   243  	if pos := t.Pos(); pos.IsKnown() {
   244  		base.Pos = pos
   245  	}
   246  
   247  	t.width = -2
   248  	t.align = 0 // 0 means use t.Width, below
   249  
   250  	et := t.Kind()
   251  	switch et {
   252  	case TFUNC, TCHAN, TMAP, TSTRING:
   253  		break
   254  
   255  	// SimType == 0 during bootstrap
   256  	default:
   257  		if SimType[t.Kind()] != 0 {
   258  			et = SimType[t.Kind()]
   259  		}
   260  	}
   261  
   262  	var w int64
   263  	switch et {
   264  	default:
   265  		base.Fatalf("CalcSize: unknown type: %v", t)
   266  
   267  	// compiler-specific stuff
   268  	case TINT8, TUINT8, TBOOL:
   269  		// bool is int8
   270  		w = 1
   271  		t.intRegs = 1
   272  
   273  	case TINT16, TUINT16:
   274  		w = 2
   275  		t.intRegs = 1
   276  
   277  	case TINT32, TUINT32:
   278  		w = 4
   279  		t.intRegs = 1
   280  
   281  	case TINT64, TUINT64:
   282  		w = 8
   283  		t.align = uint8(RegSize)
   284  		t.intRegs = uint8(8 / RegSize)
   285  
   286  	case TFLOAT32:
   287  		w = 4
   288  		t.floatRegs = 1
   289  
   290  	case TFLOAT64:
   291  		w = 8
   292  		t.align = uint8(RegSize)
   293  		t.floatRegs = 1
   294  
   295  	case TCOMPLEX64:
   296  		w = 8
   297  		t.align = 4
   298  		t.floatRegs = 2
   299  
   300  	case TCOMPLEX128:
   301  		w = 16
   302  		t.align = uint8(RegSize)
   303  		t.floatRegs = 2
   304  
   305  	case TPTR:
   306  		w = int64(PtrSize)
   307  		t.intRegs = 1
   308  		CheckSize(t.Elem())
   309  
   310  	case TUNSAFEPTR:
   311  		w = int64(PtrSize)
   312  		t.intRegs = 1
   313  
   314  	case TINTER: // implemented as 2 pointers
   315  		w = 2 * int64(PtrSize)
   316  		t.align = uint8(PtrSize)
   317  		t.intRegs = 2
   318  		expandiface(t)
   319  
   320  	case TCHAN: // implemented as pointer
   321  		w = int64(PtrSize)
   322  		t.intRegs = 1
   323  
   324  		CheckSize(t.Elem())
   325  
   326  		// Make fake type to trigger channel element size check after
   327  		// any top-level recursive type has been completed.
   328  		t1 := NewChanArgs(t)
   329  		CheckSize(t1)
   330  
   331  	case TCHANARGS:
   332  		t1 := t.ChanArgs()
   333  		CalcSize(t1) // just in case
   334  		// Make sure size of t1.Elem() is calculated at this point. We can
   335  		// use CalcSize() here rather than CheckSize(), because the top-level
   336  		// (possibly recursive) type will have been calculated before the fake
   337  		// chanargs is handled.
   338  		CalcSize(t1.Elem())
   339  		if t1.Elem().width >= 1<<16 {
   340  			base.Errorf("channel element type too large (>64kB)")
   341  		}
   342  		w = 1 // anything will do
   343  
   344  	case TMAP: // implemented as pointer
   345  		w = int64(PtrSize)
   346  		t.intRegs = 1
   347  		CheckSize(t.Elem())
   348  		CheckSize(t.Key())
   349  
   350  	case TFORW: // should have been filled in
   351  		base.Fatalf("invalid recursive type %v", t)
   352  
   353  	case TANY: // not a real type; should be replaced before use.
   354  		base.Fatalf("CalcSize any")
   355  
   356  	case TSTRING:
   357  		if StringSize == 0 {
   358  			base.Fatalf("early CalcSize string")
   359  		}
   360  		w = StringSize
   361  		t.align = uint8(PtrSize)
   362  		t.intRegs = 2
   363  
   364  	case TARRAY:
   365  		if t.Elem() == nil {
   366  			break
   367  		}
   368  
   369  		CalcSize(t.Elem())
   370  		t.SetNotInHeap(t.Elem().NotInHeap())
   371  		if t.Elem().width != 0 {
   372  			cap := (uint64(MaxWidth) - 1) / uint64(t.Elem().width)
   373  			if uint64(t.NumElem()) > cap {
   374  				base.Errorf("type %L larger than address space", t)
   375  			}
   376  		}
   377  		w = t.NumElem() * t.Elem().width
   378  		t.align = t.Elem().align
   379  
   380  		// ABIInternal only allows "trivial" arrays (i.e., length 0 or 1)
   381  		// to be passed by register.
   382  		switch t.NumElem() {
   383  		case 0:
   384  			t.intRegs = 0
   385  			t.floatRegs = 0
   386  		case 1:
   387  			t.intRegs = t.Elem().intRegs
   388  			t.floatRegs = t.Elem().floatRegs
   389  		default:
   390  			t.intRegs = math.MaxUint8
   391  			t.floatRegs = math.MaxUint8
   392  		}
   393  
   394  	case TSLICE:
   395  		if t.Elem() == nil {
   396  			break
   397  		}
   398  		w = SliceSize
   399  		CheckSize(t.Elem())
   400  		t.align = uint8(PtrSize)
   401  		t.intRegs = 3
   402  
   403  	case TSTRUCT:
   404  		if t.IsFuncArgStruct() {
   405  			base.Fatalf("CalcSize fn struct %v", t)
   406  		}
   407  		CalcStructSize(t)
   408  		w = t.width
   409  
   410  	// make fake type to check later to
   411  	// trigger function argument computation.
   412  	case TFUNC:
   413  		t1 := NewFuncArgs(t)
   414  		CheckSize(t1)
   415  		w = int64(PtrSize) // width of func type is pointer
   416  		t.intRegs = 1
   417  
   418  	// function is 3 cated structures;
   419  	// compute their widths as side-effect.
   420  	case TFUNCARGS:
   421  		t1 := t.FuncArgs()
   422  		// TODO(mdempsky): Should package abi be responsible for computing argwid?
   423  		w = calcStructOffset(t1, t1.Recvs(), 0)
   424  		w = calcStructOffset(t1, t1.Params(), w)
   425  		w = RoundUp(w, int64(RegSize))
   426  		w = calcStructOffset(t1, t1.Results(), w)
   427  		w = RoundUp(w, int64(RegSize))
   428  		t1.extra.(*Func).Argwid = w
   429  		t.align = 1
   430  	}
   431  
   432  	if PtrSize == 4 && w != int64(int32(w)) {
   433  		base.Errorf("type %v too large", t)
   434  	}
   435  
   436  	t.width = w
   437  	if t.align == 0 {
   438  		if w == 0 || w > 8 || w&(w-1) != 0 {
   439  			base.Fatalf("invalid alignment for %v", t)
   440  		}
   441  		t.align = uint8(w)
   442  	}
   443  
   444  	base.Pos = lno
   445  
   446  	ResumeCheckSize()
   447  }
   448  
   449  // CalcStructSize calculates the size of t,
   450  // filling in t.width, t.align, t.intRegs, and t.floatRegs,
   451  // even if size calculation is otherwise disabled.
   452  func CalcStructSize(t *Type) {
   453  	var maxAlign uint8 = 1
   454  
   455  	// Recognize special types. This logic is duplicated in go/types and
   456  	// cmd/compile/internal/types2.
   457  	if sym := t.Sym(); sym != nil {
   458  		switch {
   459  		case sym.Name == "align64" && isAtomicStdPkg(sym.Pkg):
   460  			maxAlign = 8
   461  		case sym.Pkg.Path == "runtime/internal/sys" && sym.Name == "nih":
   462  			t.SetNotInHeap(true)
   463  		}
   464  	}
   465  
   466  	fields := t.Fields()
   467  	size := calcStructOffset(t, fields, 0)
   468  
   469  	// For non-zero-sized structs which end in a zero-sized field, we
   470  	// add an extra byte of padding to the type. This padding ensures
   471  	// that taking the address of a zero-sized field can't manufacture a
   472  	// pointer to the next object in the heap. See issue 9401.
   473  	if size > 0 && fields[len(fields)-1].Type.width == 0 {
   474  		size++
   475  	}
   476  
   477  	var intRegs, floatRegs uint64
   478  	for _, field := range fields {
   479  		typ := field.Type
   480  
   481  		// The alignment of a struct type is the maximum alignment of its
   482  		// field types.
   483  		if align := typ.align; align > maxAlign {
   484  			maxAlign = align
   485  		}
   486  
   487  		// Each field needs its own registers.
   488  		// We sum in uint64 to avoid possible overflows.
   489  		intRegs += uint64(typ.intRegs)
   490  		floatRegs += uint64(typ.floatRegs)
   491  	}
   492  
   493  	// Final size includes trailing padding.
   494  	size = RoundUp(size, int64(maxAlign))
   495  
   496  	if intRegs > math.MaxUint8 || floatRegs > math.MaxUint8 {
   497  		intRegs = math.MaxUint8
   498  		floatRegs = math.MaxUint8
   499  	}
   500  
   501  	t.width = size
   502  	t.align = maxAlign
   503  	t.intRegs = uint8(intRegs)
   504  	t.floatRegs = uint8(floatRegs)
   505  }
   506  
   507  func (t *Type) widthCalculated() bool {
   508  	return t.align > 0
   509  }
   510  
   511  // when a type's width should be known, we call CheckSize
   512  // to compute it.  during a declaration like
   513  //
   514  //	type T *struct { next T }
   515  //
   516  // it is necessary to defer the calculation of the struct width
   517  // until after T has been initialized to be a pointer to that struct.
   518  // similarly, during import processing structs may be used
   519  // before their definition.  in those situations, calling
   520  // DeferCheckSize() stops width calculations until
   521  // ResumeCheckSize() is called, at which point all the
   522  // CalcSizes that were deferred are executed.
   523  // CalcSize should only be called when the type's size
   524  // is needed immediately.  CheckSize makes sure the
   525  // size is evaluated eventually.
   526  
   527  var deferredTypeStack []*Type
   528  
   529  func CheckSize(t *Type) {
   530  	if t == nil {
   531  		return
   532  	}
   533  
   534  	// function arg structs should not be checked
   535  	// outside of the enclosing function.
   536  	if t.IsFuncArgStruct() {
   537  		base.Fatalf("CheckSize %v", t)
   538  	}
   539  
   540  	if defercalc == 0 {
   541  		CalcSize(t)
   542  		return
   543  	}
   544  
   545  	// if type has not yet been pushed on deferredTypeStack yet, do it now
   546  	if !t.Deferwidth() {
   547  		t.SetDeferwidth(true)
   548  		deferredTypeStack = append(deferredTypeStack, t)
   549  	}
   550  }
   551  
   552  func DeferCheckSize() {
   553  	defercalc++
   554  }
   555  
   556  func ResumeCheckSize() {
   557  	if defercalc == 1 {
   558  		for len(deferredTypeStack) > 0 {
   559  			t := deferredTypeStack[len(deferredTypeStack)-1]
   560  			deferredTypeStack = deferredTypeStack[:len(deferredTypeStack)-1]
   561  			t.SetDeferwidth(false)
   562  			CalcSize(t)
   563  		}
   564  	}
   565  
   566  	defercalc--
   567  }
   568  
   569  // PtrDataSize returns the length in bytes of the prefix of t
   570  // containing pointer data. Anything after this offset is scalar data.
   571  //
   572  // PtrDataSize is only defined for actual Go types. It's an error to
   573  // use it on compiler-internal types (e.g., TSSA, TRESULTS).
   574  func PtrDataSize(t *Type) int64 {
   575  	switch t.Kind() {
   576  	case TBOOL, TINT8, TUINT8, TINT16, TUINT16, TINT32,
   577  		TUINT32, TINT64, TUINT64, TINT, TUINT,
   578  		TUINTPTR, TCOMPLEX64, TCOMPLEX128, TFLOAT32, TFLOAT64:
   579  		return 0
   580  
   581  	case TPTR:
   582  		if t.Elem().NotInHeap() {
   583  			return 0
   584  		}
   585  		return int64(PtrSize)
   586  
   587  	case TUNSAFEPTR, TFUNC, TCHAN, TMAP:
   588  		return int64(PtrSize)
   589  
   590  	case TSTRING:
   591  		// struct { byte *str; intgo len; }
   592  		return int64(PtrSize)
   593  
   594  	case TINTER:
   595  		// struct { Itab *tab;	void *data; } or
   596  		// struct { Type *type; void *data; }
   597  		// Note: see comment in typebits.Set
   598  		return 2 * int64(PtrSize)
   599  
   600  	case TSLICE:
   601  		if t.Elem().NotInHeap() {
   602  			return 0
   603  		}
   604  		// struct { byte *array; uintgo len; uintgo cap; }
   605  		return int64(PtrSize)
   606  
   607  	case TARRAY:
   608  		if t.NumElem() == 0 {
   609  			return 0
   610  		}
   611  		// t.NumElem() > 0
   612  		size := PtrDataSize(t.Elem())
   613  		if size == 0 {
   614  			return 0
   615  		}
   616  		return (t.NumElem()-1)*t.Elem().Size() + size
   617  
   618  	case TSTRUCT:
   619  		// Find the last field that has pointers, if any.
   620  		fs := t.Fields()
   621  		for i := len(fs) - 1; i >= 0; i-- {
   622  			if size := PtrDataSize(fs[i].Type); size > 0 {
   623  				return fs[i].Offset + size
   624  			}
   625  		}
   626  		return 0
   627  
   628  	case TSSA:
   629  		if t != TypeInt128 {
   630  			base.Fatalf("PtrDataSize: unexpected ssa type %v", t)
   631  		}
   632  		return 0
   633  
   634  	default:
   635  		base.Fatalf("PtrDataSize: unexpected type, %v", t)
   636  		return 0
   637  	}
   638  }
   639
View as plain text