Source file src/cmd/compile/internal/reflectdata/map_noswiss.go

     1  // Copyright 2024 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 reflectdata
     6  
     7  import (
     8  	"internal/abi"
     9  
    10  	"cmd/compile/internal/base"
    11  	"cmd/compile/internal/ir"
    12  	"cmd/compile/internal/rttype"
    13  	"cmd/compile/internal/types"
    14  	"cmd/internal/obj"
    15  	"cmd/internal/objabi"
    16  	"cmd/internal/src"
    17  )
    18  
    19  // OldMapBucketType makes the map bucket type given the type of the map.
    20  func OldMapBucketType(t *types.Type) *types.Type {
    21  	// Builds a type representing a Bucket structure for
    22  	// the given map type. This type is not visible to users -
    23  	// we include only enough information to generate a correct GC
    24  	// program for it.
    25  	// Make sure this stays in sync with runtime/map.go.
    26  	//
    27  	//	A "bucket" is a "struct" {
    28  	//	      tophash [abi.OldMapBucketCount]uint8
    29  	//	      keys [abi.OldMapBucketCount]keyType
    30  	//	      elems [abi.OldMapBucketCount]elemType
    31  	//	      overflow *bucket
    32  	//	    }
    33  	if t.MapType().OldBucket != nil {
    34  		return t.MapType().OldBucket
    35  	}
    36  
    37  	keytype := t.Key()
    38  	elemtype := t.Elem()
    39  	types.CalcSize(keytype)
    40  	types.CalcSize(elemtype)
    41  	if keytype.Size() > abi.OldMapMaxKeyBytes {
    42  		keytype = types.NewPtr(keytype)
    43  	}
    44  	if elemtype.Size() > abi.OldMapMaxElemBytes {
    45  		elemtype = types.NewPtr(elemtype)
    46  	}
    47  
    48  	field := make([]*types.Field, 0, 5)
    49  
    50  	// The first field is: uint8 topbits[BUCKETSIZE].
    51  	arr := types.NewArray(types.Types[types.TUINT8], abi.OldMapBucketCount)
    52  	field = append(field, makefield("topbits", arr))
    53  
    54  	arr = types.NewArray(keytype, abi.OldMapBucketCount)
    55  	arr.SetNoalg(true)
    56  	keys := makefield("keys", arr)
    57  	field = append(field, keys)
    58  
    59  	arr = types.NewArray(elemtype, abi.OldMapBucketCount)
    60  	arr.SetNoalg(true)
    61  	elems := makefield("elems", arr)
    62  	field = append(field, elems)
    63  
    64  	// If keys and elems have no pointers, the map implementation
    65  	// can keep a list of overflow pointers on the side so that
    66  	// buckets can be marked as having no pointers.
    67  	// Arrange for the bucket to have no pointers by changing
    68  	// the type of the overflow field to uintptr in this case.
    69  	// See comment on hmap.overflow in runtime/map.go.
    70  	otyp := types.Types[types.TUNSAFEPTR]
    71  	if !elemtype.HasPointers() && !keytype.HasPointers() {
    72  		otyp = types.Types[types.TUINTPTR]
    73  	}
    74  	overflow := makefield("overflow", otyp)
    75  	field = append(field, overflow)
    76  
    77  	// link up fields
    78  	bucket := types.NewStruct(field[:])
    79  	bucket.SetNoalg(true)
    80  	types.CalcSize(bucket)
    81  
    82  	// Check invariants that map code depends on.
    83  	if !types.IsComparable(t.Key()) {
    84  		base.Fatalf("unsupported map key type for %v", t)
    85  	}
    86  	if abi.OldMapBucketCount < 8 {
    87  		base.Fatalf("bucket size %d too small for proper alignment %d", abi.OldMapBucketCount, 8)
    88  	}
    89  	if uint8(keytype.Alignment()) > abi.OldMapBucketCount {
    90  		base.Fatalf("key align too big for %v", t)
    91  	}
    92  	if uint8(elemtype.Alignment()) > abi.OldMapBucketCount {
    93  		base.Fatalf("elem align %d too big for %v, BUCKETSIZE=%d", elemtype.Alignment(), t, abi.OldMapBucketCount)
    94  	}
    95  	if keytype.Size() > abi.OldMapMaxKeyBytes {
    96  		base.Fatalf("key size too large for %v", t)
    97  	}
    98  	if elemtype.Size() > abi.OldMapMaxElemBytes {
    99  		base.Fatalf("elem size too large for %v", t)
   100  	}
   101  	if t.Key().Size() > abi.OldMapMaxKeyBytes && !keytype.IsPtr() {
   102  		base.Fatalf("key indirect incorrect for %v", t)
   103  	}
   104  	if t.Elem().Size() > abi.OldMapMaxElemBytes && !elemtype.IsPtr() {
   105  		base.Fatalf("elem indirect incorrect for %v", t)
   106  	}
   107  	if keytype.Size()%keytype.Alignment() != 0 {
   108  		base.Fatalf("key size not a multiple of key align for %v", t)
   109  	}
   110  	if elemtype.Size()%elemtype.Alignment() != 0 {
   111  		base.Fatalf("elem size not a multiple of elem align for %v", t)
   112  	}
   113  	if uint8(bucket.Alignment())%uint8(keytype.Alignment()) != 0 {
   114  		base.Fatalf("bucket align not multiple of key align %v", t)
   115  	}
   116  	if uint8(bucket.Alignment())%uint8(elemtype.Alignment()) != 0 {
   117  		base.Fatalf("bucket align not multiple of elem align %v", t)
   118  	}
   119  	if keys.Offset%keytype.Alignment() != 0 {
   120  		base.Fatalf("bad alignment of keys in bmap for %v", t)
   121  	}
   122  	if elems.Offset%elemtype.Alignment() != 0 {
   123  		base.Fatalf("bad alignment of elems in bmap for %v", t)
   124  	}
   125  
   126  	// Double-check that overflow field is final memory in struct,
   127  	// with no padding at end.
   128  	if overflow.Offset != bucket.Size()-int64(types.PtrSize) {
   129  		base.Fatalf("bad offset of overflow in bmap for %v, overflow.Offset=%d, bucket.Size()-int64(types.PtrSize)=%d",
   130  			t, overflow.Offset, bucket.Size()-int64(types.PtrSize))
   131  	}
   132  
   133  	t.MapType().OldBucket = bucket
   134  
   135  	bucket.StructType().Map = t
   136  	return bucket
   137  }
   138  
   139  var oldHmapType *types.Type
   140  
   141  // OldMapType returns a type interchangeable with runtime.hmap.
   142  // Make sure this stays in sync with runtime/map.go.
   143  func OldMapType() *types.Type {
   144  	if oldHmapType != nil {
   145  		return oldHmapType
   146  	}
   147  
   148  	// build a struct:
   149  	// type hmap struct {
   150  	//    count      int
   151  	//    flags      uint8
   152  	//    B          uint8
   153  	//    noverflow  uint16
   154  	//    hash0      uint32
   155  	//    buckets    unsafe.Pointer
   156  	//    oldbuckets unsafe.Pointer
   157  	//    nevacuate  uintptr
   158  	//    clearSeq   uint64
   159  	//    extra      unsafe.Pointer // *mapextra
   160  	// }
   161  	// must match runtime/map.go:hmap.
   162  	fields := []*types.Field{
   163  		makefield("count", types.Types[types.TINT]),
   164  		makefield("flags", types.Types[types.TUINT8]),
   165  		makefield("B", types.Types[types.TUINT8]),
   166  		makefield("noverflow", types.Types[types.TUINT16]),
   167  		makefield("hash0", types.Types[types.TUINT32]),      // Used in walk.go for OMAKEMAP.
   168  		makefield("buckets", types.Types[types.TUNSAFEPTR]), // Used in walk.go for OMAKEMAP.
   169  		makefield("oldbuckets", types.Types[types.TUNSAFEPTR]),
   170  		makefield("nevacuate", types.Types[types.TUINTPTR]),
   171  		makefield("clearSeq", types.Types[types.TUINT64]),
   172  		makefield("extra", types.Types[types.TUNSAFEPTR]),
   173  	}
   174  
   175  	n := ir.NewDeclNameAt(src.NoXPos, ir.OTYPE, ir.Pkgs.Runtime.Lookup("hmap"))
   176  	hmap := types.NewNamed(n)
   177  	n.SetType(hmap)
   178  	n.SetTypecheck(1)
   179  
   180  	hmap.SetUnderlying(types.NewStruct(fields))
   181  	types.CalcSize(hmap)
   182  
   183  	// The size of hmap should be 56 bytes on 64 bit
   184  	// and 36 bytes on 32 bit platforms.
   185  	if size := int64(2*8 + 5*types.PtrSize); hmap.Size() != size {
   186  		base.Fatalf("hmap size not correct: got %d, want %d", hmap.Size(), size)
   187  	}
   188  
   189  	oldHmapType = hmap
   190  	return hmap
   191  }
   192  
   193  var oldHiterType *types.Type
   194  
   195  // OldMapIterType returns a type interchangeable with runtime.hiter.
   196  // Make sure this stays in sync with runtime/map.go.
   197  func OldMapIterType() *types.Type {
   198  	if oldHiterType != nil {
   199  		return oldHiterType
   200  	}
   201  
   202  	hmap := OldMapType()
   203  
   204  	// build a struct:
   205  	// type hiter struct {
   206  	//    key         unsafe.Pointer // *Key
   207  	//    elem        unsafe.Pointer // *Elem
   208  	//    t           unsafe.Pointer // *OldMapType
   209  	//    h           *hmap
   210  	//    buckets     unsafe.Pointer
   211  	//    bptr        unsafe.Pointer // *bmap
   212  	//    overflow    unsafe.Pointer // *[]*bmap
   213  	//    oldoverflow unsafe.Pointer // *[]*bmap
   214  	//    startBucket uintptr
   215  	//    offset      uint8
   216  	//    wrapped     bool
   217  	//    B           uint8
   218  	//    i           uint8
   219  	//    bucket      uintptr
   220  	//    checkBucket uintptr
   221  	//    clearSeq    uint64
   222  	// }
   223  	// must match runtime/map.go:hiter.
   224  	fields := []*types.Field{
   225  		makefield("key", types.Types[types.TUNSAFEPTR]),  // Used in range.go for TMAP.
   226  		makefield("elem", types.Types[types.TUNSAFEPTR]), // Used in range.go for TMAP.
   227  		makefield("t", types.Types[types.TUNSAFEPTR]),
   228  		makefield("h", types.NewPtr(hmap)),
   229  		makefield("buckets", types.Types[types.TUNSAFEPTR]),
   230  		makefield("bptr", types.Types[types.TUNSAFEPTR]),
   231  		makefield("overflow", types.Types[types.TUNSAFEPTR]),
   232  		makefield("oldoverflow", types.Types[types.TUNSAFEPTR]),
   233  		makefield("startBucket", types.Types[types.TUINTPTR]),
   234  		makefield("offset", types.Types[types.TUINT8]),
   235  		makefield("wrapped", types.Types[types.TBOOL]),
   236  		makefield("B", types.Types[types.TUINT8]),
   237  		makefield("i", types.Types[types.TUINT8]),
   238  		makefield("bucket", types.Types[types.TUINTPTR]),
   239  		makefield("checkBucket", types.Types[types.TUINTPTR]),
   240  		makefield("clearSeq", types.Types[types.TUINT64]),
   241  	}
   242  
   243  	// build iterator struct holding the above fields
   244  	n := ir.NewDeclNameAt(src.NoXPos, ir.OTYPE, ir.Pkgs.Runtime.Lookup("hiter"))
   245  	hiter := types.NewNamed(n)
   246  	n.SetType(hiter)
   247  	n.SetTypecheck(1)
   248  
   249  	hiter.SetUnderlying(types.NewStruct(fields))
   250  	types.CalcSize(hiter)
   251  	if hiter.Size() != int64(8+12*types.PtrSize) {
   252  		base.Fatalf("hash_iter size not correct %d %d", hiter.Size(), 8+12*types.PtrSize)
   253  	}
   254  
   255  	oldHiterType = hiter
   256  	return hiter
   257  }
   258  
   259  func writeOldMapType(t *types.Type, lsym *obj.LSym, c rttype.Cursor) {
   260  	// internal/abi.OldMapType
   261  	s1 := writeType(t.Key())
   262  	s2 := writeType(t.Elem())
   263  	s3 := writeType(OldMapBucketType(t))
   264  	hasher := genhash(t.Key())
   265  
   266  	c.Field("Key").WritePtr(s1)
   267  	c.Field("Elem").WritePtr(s2)
   268  	c.Field("Bucket").WritePtr(s3)
   269  	c.Field("Hasher").WritePtr(hasher)
   270  	var flags uint32
   271  	// Note: flags must match maptype accessors in ../../../../runtime/type.go
   272  	// and maptype builder in ../../../../reflect/type.go:MapOf.
   273  	if t.Key().Size() > abi.OldMapMaxKeyBytes {
   274  		c.Field("KeySize").WriteUint8(uint8(types.PtrSize))
   275  		flags |= 1 // indirect key
   276  	} else {
   277  		c.Field("KeySize").WriteUint8(uint8(t.Key().Size()))
   278  	}
   279  
   280  	if t.Elem().Size() > abi.OldMapMaxElemBytes {
   281  		c.Field("ValueSize").WriteUint8(uint8(types.PtrSize))
   282  		flags |= 2 // indirect value
   283  	} else {
   284  		c.Field("ValueSize").WriteUint8(uint8(t.Elem().Size()))
   285  	}
   286  	c.Field("BucketSize").WriteUint16(uint16(OldMapBucketType(t).Size()))
   287  	if types.IsReflexive(t.Key()) {
   288  		flags |= 4 // reflexive key
   289  	}
   290  	if needkeyupdate(t.Key()) {
   291  		flags |= 8 // need key update
   292  	}
   293  	if hashMightPanic(t.Key()) {
   294  		flags |= 16 // hash might panic
   295  	}
   296  	c.Field("Flags").WriteUint32(flags)
   297  
   298  	if u := t.Underlying(); u != t {
   299  		// If t is a named map type, also keep the underlying map
   300  		// type live in the binary. This is important to make sure that
   301  		// a named map and that same map cast to its underlying type via
   302  		// reflection, use the same hash function. See issue 37716.
   303  		lsym.AddRel(base.Ctxt, obj.Reloc{Type: objabi.R_KEEP, Sym: writeType(u)})
   304  	}
   305  }
   306  

View as plain text