size.go

Documentation: cmd/compile/internal/types

     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  	"bytes"
     9  	"fmt"
    10  	"sort"
    11  
    12  	"cmd/compile/internal/base"
    13  	"cmd/internal/src"
    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 betypeinit (see ../amd64/galign.go).
    66  var defercalc int
    67  
    68  func Rnd(o int64, r int64) int64 {
    69  	if r < 1 || r > 8 || r&(r-1) != 0 {
    70  		base.Fatalf("rnd %d", r)
    71  	}
    72  	return (o + r - 1) &^ (r - 1)
    73  }
    74  
    75  // expandiface computes the method set for interface type t by
    76  // expanding embedded interfaces.
    77  func expandiface(t *Type) {
    78  	seen := make(map[*Sym]*Field)
    79  	var methods []*Field
    80  
    81  	addMethod := func(m *Field, explicit bool) {
    82  		switch prev := seen[m.Sym]; {
    83  		case prev == nil:
    84  			seen[m.Sym] = m
    85  		case AllowsGoVersion(t.Pkg(), 1, 14) && !explicit && Identical(m.Type, prev.Type):
    86  			return
    87  		default:
    88  			base.ErrorfAt(m.Pos, "duplicate method %s", m.Sym.Name)
    89  		}
    90  		methods = append(methods, m)
    91  	}
    92  
    93  	for _, m := range t.Methods().Slice() {
    94  		if m.Sym == nil {
    95  			continue
    96  		}
    97  
    98  		CheckSize(m.Type)
    99  		addMethod(m, true)
   100  	}
   101  
   102  	for _, m := range t.Methods().Slice() {
   103  		if m.Sym != nil || m.Type == nil {
   104  			continue
   105  		}
   106  
   107  		if !m.Type.IsInterface() {
   108  			base.ErrorfAt(m.Pos, "interface contains embedded non-interface %v", m.Type)
   109  			m.SetBroke(true)
   110  			t.SetBroke(true)
   111  			// Add to fields so that error messages
   112  			// include the broken embedded type when
   113  			// printing t.
   114  			// TODO(mdempsky): Revisit this.
   115  			methods = append(methods, m)
   116  			continue
   117  		}
   118  
   119  		// Embedded interface: duplicate all methods
   120  		// (including broken ones, if any) and add to t's
   121  		// method set.
   122  		for _, t1 := range m.Type.AllMethods().Slice() {
   123  			// Use m.Pos rather than t1.Pos to preserve embedding position.
   124  			f := NewField(m.Pos, t1.Sym, t1.Type)
   125  			addMethod(f, false)
   126  		}
   127  	}
   128  
   129  	sort.Sort(MethodsByName(methods))
   130  
   131  	if int64(len(methods)) >= MaxWidth/int64(PtrSize) {
   132  		base.ErrorfAt(typePos(t), "interface too large")
   133  	}
   134  	for i, m := range methods {
   135  		m.Offset = int64(i) * int64(PtrSize)
   136  	}
   137  
   138  	t.SetAllMethods(methods)
   139  }
   140  
   141  func calcStructOffset(errtype *Type, t *Type, o int64, flag int) int64 {
   142  	// flag is 0 (receiver), 1 (actual struct), or RegSize (in/out parameters)
   143  	isStruct := flag == 1
   144  	starto := o
   145  	maxalign := int32(flag)
   146  	if maxalign < 1 {
   147  		maxalign = 1
   148  	}
   149  	lastzero := int64(0)
   150  	for _, f := range t.Fields().Slice() {
   151  		if f.Type == nil {
   152  			// broken field, just skip it so that other valid fields
   153  			// get a width.
   154  			continue
   155  		}
   156  
   157  		CalcSize(f.Type)
   158  		if int32(f.Type.Align) > maxalign {
   159  			maxalign = int32(f.Type.Align)
   160  		}
   161  		if f.Type.Align > 0 {
   162  			o = Rnd(o, int64(f.Type.Align))
   163  		}
   164  		if isStruct { // For receiver/args/results, do not set, it depends on ABI
   165  			f.Offset = o
   166  		}
   167  
   168  		w := f.Type.Width
   169  		if w < 0 {
   170  			base.Fatalf("invalid width %d", f.Type.Width)
   171  		}
   172  		if w == 0 {
   173  			lastzero = o
   174  		}
   175  		o += w
   176  		maxwidth := MaxWidth
   177  		// On 32-bit systems, reflect tables impose an additional constraint
   178  		// that each field start offset must fit in 31 bits.
   179  		if maxwidth < 1<<32 {
   180  			maxwidth = 1<<31 - 1
   181  		}
   182  		if o >= maxwidth {
   183  			base.ErrorfAt(typePos(errtype), "type %L too large", errtype)
   184  			o = 8 // small but nonzero
   185  		}
   186  	}
   187  
   188  	// For nonzero-sized structs which end in a zero-sized thing, we add
   189  	// an extra byte of padding to the type. This padding ensures that
   190  	// taking the address of the zero-sized thing can't manufacture a
   191  	// pointer to the next object in the heap. See issue 9401.
   192  	if flag == 1 && o > starto && o == lastzero {
   193  		o++
   194  	}
   195  
   196  	// final width is rounded
   197  	if flag != 0 {
   198  		o = Rnd(o, int64(maxalign))
   199  	}
   200  	t.Align = uint8(maxalign)
   201  
   202  	// type width only includes back to first field's offset
   203  	t.Width = o - starto
   204  
   205  	return o
   206  }
   207  
   208  // findTypeLoop searches for an invalid type declaration loop involving
   209  // type t and reports whether one is found. If so, path contains the
   210  // loop.
   211  //
   212  // path points to a slice used for tracking the sequence of types
   213  // visited. Using a pointer to a slice allows the slice capacity to
   214  // grow and limit reallocations.
   215  func findTypeLoop(t *Type, path *[]*Type) bool {
   216  	// We implement a simple DFS loop-finding algorithm. This
   217  	// could be faster, but type cycles are rare.
   218  
   219  	if t.Sym() != nil {
   220  		// Declared type. Check for loops and otherwise
   221  		// recurse on the type expression used in the type
   222  		// declaration.
   223  
   224  		// Type imported from package, so it can't be part of
   225  		// a type loop (otherwise that package should have
   226  		// failed to compile).
   227  		if t.Sym().Pkg != LocalPkg {
   228  			return false
   229  		}
   230  
   231  		for i, x := range *path {
   232  			if x == t {
   233  				*path = (*path)[i:]
   234  				return true
   235  			}
   236  		}
   237  
   238  		*path = append(*path, t)
   239  		if findTypeLoop(t.Obj().(TypeObject).TypeDefn(), path) {
   240  			return true
   241  		}
   242  		*path = (*path)[:len(*path)-1]
   243  	} else {
   244  		// Anonymous type. Recurse on contained types.
   245  
   246  		switch t.Kind() {
   247  		case TARRAY:
   248  			if findTypeLoop(t.Elem(), path) {
   249  				return true
   250  			}
   251  		case TSTRUCT:
   252  			for _, f := range t.Fields().Slice() {
   253  				if findTypeLoop(f.Type, path) {
   254  					return true
   255  				}
   256  			}
   257  		case TINTER:
   258  			for _, m := range t.Methods().Slice() {
   259  				if m.Type.IsInterface() { // embedded interface
   260  					if findTypeLoop(m.Type, path) {
   261  						return true
   262  					}
   263  				}
   264  			}
   265  		}
   266  	}
   267  
   268  	return false
   269  }
   270  
   271  func reportTypeLoop(t *Type) {
   272  	if t.Broke() {
   273  		return
   274  	}
   275  
   276  	var l []*Type
   277  	if !findTypeLoop(t, &l) {
   278  		base.Fatalf("failed to find type loop for: %v", t)
   279  	}
   280  
   281  	// Rotate loop so that the earliest type declaration is first.
   282  	i := 0
   283  	for j, t := range l[1:] {
   284  		if typePos(t).Before(typePos(l[i])) {
   285  			i = j + 1
   286  		}
   287  	}
   288  	l = append(l[i:], l[:i]...)
   289  
   290  	var msg bytes.Buffer
   291  	fmt.Fprintf(&msg, "invalid recursive type %v\n", l[0])
   292  	for _, t := range l {
   293  		fmt.Fprintf(&msg, "\t%v: %v refers to\n", base.FmtPos(typePos(t)), t)
   294  		t.SetBroke(true)
   295  	}
   296  	fmt.Fprintf(&msg, "\t%v: %v", base.FmtPos(typePos(l[0])), l[0])
   297  	base.ErrorfAt(typePos(l[0]), msg.String())
   298  }
   299  
   300  // CalcSize calculates and stores the size and alignment for t.
   301  // If CalcSizeDisabled is set, and the size/alignment
   302  // have not already been calculated, it calls Fatal.
   303  // This is used to prevent data races in the back end.
   304  func CalcSize(t *Type) {
   305  	// Calling CalcSize when typecheck tracing enabled is not safe.
   306  	// See issue #33658.
   307  	if base.EnableTrace && SkipSizeForTracing {
   308  		return
   309  	}
   310  	if PtrSize == 0 {
   311  		// Assume this is a test.
   312  		return
   313  	}
   314  
   315  	if t == nil {
   316  		return
   317  	}
   318  
   319  	if t.Width == -2 {
   320  		reportTypeLoop(t)
   321  		t.Width = 0
   322  		t.Align = 1
   323  		return
   324  	}
   325  
   326  	if t.WidthCalculated() {
   327  		return
   328  	}
   329  
   330  	if CalcSizeDisabled {
   331  		if t.Broke() {
   332  			// break infinite recursion from Fatal call below
   333  			return
   334  		}
   335  		t.SetBroke(true)
   336  		base.Fatalf("width not calculated: %v", t)
   337  	}
   338  
   339  	// break infinite recursion if the broken recursive type
   340  	// is referenced again
   341  	if t.Broke() && t.Width == 0 {
   342  		return
   343  	}
   344  
   345  	// defer CheckSize calls until after we're done
   346  	DeferCheckSize()
   347  
   348  	lno := base.Pos
   349  	if pos := t.Pos(); pos.IsKnown() {
   350  		base.Pos = pos
   351  	}
   352  
   353  	t.Width = -2
   354  	t.Align = 0 // 0 means use t.Width, below
   355  
   356  	et := t.Kind()
   357  	switch et {
   358  	case TFUNC, TCHAN, TMAP, TSTRING:
   359  		break
   360  
   361  	// SimType == 0 during bootstrap
   362  	default:
   363  		if SimType[t.Kind()] != 0 {
   364  			et = SimType[t.Kind()]
   365  		}
   366  	}
   367  
   368  	var w int64
   369  	switch et {
   370  	default:
   371  		base.Fatalf("CalcSize: unknown type: %v", t)
   372  
   373  	// compiler-specific stuff
   374  	case TINT8, TUINT8, TBOOL:
   375  		// bool is int8
   376  		w = 1
   377  
   378  	case TINT16, TUINT16:
   379  		w = 2
   380  
   381  	case TINT32, TUINT32, TFLOAT32:
   382  		w = 4
   383  
   384  	case TINT64, TUINT64, TFLOAT64:
   385  		w = 8
   386  		t.Align = uint8(RegSize)
   387  
   388  	case TCOMPLEX64:
   389  		w = 8
   390  		t.Align = 4
   391  
   392  	case TCOMPLEX128:
   393  		w = 16
   394  		t.Align = uint8(RegSize)
   395  
   396  	case TPTR:
   397  		w = int64(PtrSize)
   398  		CheckSize(t.Elem())
   399  
   400  	case TUNSAFEPTR:
   401  		w = int64(PtrSize)
   402  
   403  	case TINTER: // implemented as 2 pointers
   404  		w = 2 * int64(PtrSize)
   405  		t.Align = uint8(PtrSize)
   406  		expandiface(t)
   407  
   408  	case TCHAN: // implemented as pointer
   409  		w = int64(PtrSize)
   410  
   411  		CheckSize(t.Elem())
   412  
   413  		// make fake type to check later to
   414  		// trigger channel argument check.
   415  		t1 := NewChanArgs(t)
   416  		CheckSize(t1)
   417  
   418  	case TCHANARGS:
   419  		t1 := t.ChanArgs()
   420  		CalcSize(t1) // just in case
   421  		if t1.Elem().Width >= 1<<16 {
   422  			base.ErrorfAt(typePos(t1), "channel element type too large (>64kB)")
   423  		}
   424  		w = 1 // anything will do
   425  
   426  	case TMAP: // implemented as pointer
   427  		w = int64(PtrSize)
   428  		CheckSize(t.Elem())
   429  		CheckSize(t.Key())
   430  
   431  	case TFORW: // should have been filled in
   432  		reportTypeLoop(t)
   433  		w = 1 // anything will do
   434  
   435  	case TANY:
   436  		// not a real type; should be replaced before use.
   437  		base.Fatalf("CalcSize any")
   438  
   439  	case TSTRING:
   440  		if StringSize == 0 {
   441  			base.Fatalf("early CalcSize string")
   442  		}
   443  		w = StringSize
   444  		t.Align = uint8(PtrSize)
   445  
   446  	case TARRAY:
   447  		if t.Elem() == nil {
   448  			break
   449  		}
   450  
   451  		CalcSize(t.Elem())
   452  		if t.Elem().Width != 0 {
   453  			cap := (uint64(MaxWidth) - 1) / uint64(t.Elem().Width)
   454  			if uint64(t.NumElem()) > cap {
   455  				base.ErrorfAt(typePos(t), "type %L larger than address space", t)
   456  			}
   457  		}
   458  		w = t.NumElem() * t.Elem().Width
   459  		t.Align = t.Elem().Align
   460  
   461  	case TSLICE:
   462  		if t.Elem() == nil {
   463  			break
   464  		}
   465  		w = SliceSize
   466  		CheckSize(t.Elem())
   467  		t.Align = uint8(PtrSize)
   468  
   469  	case TSTRUCT:
   470  		if t.IsFuncArgStruct() {
   471  			base.Fatalf("CalcSize fn struct %v", t)
   472  		}
   473  		w = calcStructOffset(t, t, 0, 1)
   474  
   475  	// make fake type to check later to
   476  	// trigger function argument computation.
   477  	case TFUNC:
   478  		t1 := NewFuncArgs(t)
   479  		CheckSize(t1)
   480  		w = int64(PtrSize) // width of func type is pointer
   481  
   482  	// function is 3 cated structures;
   483  	// compute their widths as side-effect.
   484  	case TFUNCARGS:
   485  		t1 := t.FuncArgs()
   486  		w = calcStructOffset(t1, t1.Recvs(), 0, 0)
   487  		w = calcStructOffset(t1, t1.Params(), w, RegSize)
   488  		w = calcStructOffset(t1, t1.Results(), w, RegSize)
   489  		t1.Extra.(*Func).Argwid = w
   490  		if w%int64(RegSize) != 0 {
   491  			base.Warn("bad type %v %d\n", t1, w)
   492  		}
   493  		t.Align = 1
   494  
   495  	case TTYPEPARAM:
   496  		// TODO(danscales) - remove when we eliminate the need
   497  		// to do CalcSize in noder2 (which shouldn't be needed in the noder)
   498  		w = int64(PtrSize)
   499  	}
   500  
   501  	if PtrSize == 4 && w != int64(int32(w)) {
   502  		base.ErrorfAt(typePos(t), "type %v too large", t)
   503  	}
   504  
   505  	t.Width = w
   506  	if t.Align == 0 {
   507  		if w == 0 || w > 8 || w&(w-1) != 0 {
   508  			base.Fatalf("invalid alignment for %v", t)
   509  		}
   510  		t.Align = uint8(w)
   511  	}
   512  
   513  	base.Pos = lno
   514  
   515  	ResumeCheckSize()
   516  }
   517  
   518  // CalcStructSize calculates the size of s,
   519  // filling in s.Width and s.Align,
   520  // even if size calculation is otherwise disabled.
   521  func CalcStructSize(s *Type) {
   522  	s.Width = calcStructOffset(s, s, 0, 1) // sets align
   523  }
   524  
   525  // when a type's width should be known, we call CheckSize
   526  // to compute it.  during a declaration like
   527  //
   528  //	type T *struct { next T }
   529  //
   530  // it is necessary to defer the calculation of the struct width
   531  // until after T has been initialized to be a pointer to that struct.
   532  // similarly, during import processing structs may be used
   533  // before their definition.  in those situations, calling
   534  // DeferCheckSize() stops width calculations until
   535  // ResumeCheckSize() is called, at which point all the
   536  // CalcSizes that were deferred are executed.
   537  // CalcSize should only be called when the type's size
   538  // is needed immediately.  CheckSize makes sure the
   539  // size is evaluated eventually.
   540  
   541  var deferredTypeStack []*Type
   542  
   543  func CheckSize(t *Type) {
   544  	if t == nil {
   545  		return
   546  	}
   547  
   548  	// function arg structs should not be checked
   549  	// outside of the enclosing function.
   550  	if t.IsFuncArgStruct() {
   551  		base.Fatalf("CheckSize %v", t)
   552  	}
   553  
   554  	if defercalc == 0 {
   555  		CalcSize(t)
   556  		return
   557  	}
   558  
   559  	// if type has not yet been pushed on deferredTypeStack yet, do it now
   560  	if !t.Deferwidth() {
   561  		t.SetDeferwidth(true)
   562  		deferredTypeStack = append(deferredTypeStack, t)
   563  	}
   564  }
   565  
   566  func DeferCheckSize() {
   567  	defercalc++
   568  }
   569  
   570  func ResumeCheckSize() {
   571  	if defercalc == 1 {
   572  		for len(deferredTypeStack) > 0 {
   573  			t := deferredTypeStack[len(deferredTypeStack)-1]
   574  			deferredTypeStack = deferredTypeStack[:len(deferredTypeStack)-1]
   575  			t.SetDeferwidth(false)
   576  			CalcSize(t)
   577  		}
   578  	}
   579  
   580  	defercalc--
   581  }
   582  
   583  // PtrDataSize returns the length in bytes of the prefix of t
   584  // containing pointer data. Anything after this offset is scalar data.
   585  func PtrDataSize(t *Type) int64 {
   586  	if !t.HasPointers() {
   587  		return 0
   588  	}
   589  
   590  	switch t.Kind() {
   591  	case TPTR,
   592  		TUNSAFEPTR,
   593  		TFUNC,
   594  		TCHAN,
   595  		TMAP:
   596  		return int64(PtrSize)
   597  
   598  	case TSTRING:
   599  		// struct { byte *str; intgo len; }
   600  		return int64(PtrSize)
   601  
   602  	case TINTER:
   603  		// struct { Itab *tab;	void *data; } or
   604  		// struct { Type *type; void *data; }
   605  		// Note: see comment in typebits.Set
   606  		return 2 * int64(PtrSize)
   607  
   608  	case TSLICE:
   609  		// struct { byte *array; uintgo len; uintgo cap; }
   610  		return int64(PtrSize)
   611  
   612  	case TARRAY:
   613  		// haspointers already eliminated t.NumElem() == 0.
   614  		return (t.NumElem()-1)*t.Elem().Width + PtrDataSize(t.Elem())
   615  
   616  	case TSTRUCT:
   617  		// Find the last field that has pointers.
   618  		var lastPtrField *Field
   619  		fs := t.Fields().Slice()
   620  		for i := len(fs) - 1; i >= 0; i-- {
   621  			if fs[i].Type.HasPointers() {
   622  				lastPtrField = fs[i]
   623  				break
   624  			}
   625  		}
   626  		return lastPtrField.Offset + PtrDataSize(lastPtrField.Type)
   627  
   628  	default:
   629  		base.Fatalf("PtrDataSize: unexpected type, %v", t)
   630  		return 0
   631  	}
   632  }
   633
View as plain text