map.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  	"cmd/compile/internal/base"
     9  	"cmd/compile/internal/ir"
    10  	"cmd/compile/internal/rttype"
    11  	"cmd/compile/internal/types"
    12  	"cmd/internal/obj"
    13  	"cmd/internal/objabi"
    14  	"cmd/internal/src"
    15  	"internal/abi"
    16  	"internal/buildcfg"
    17  )
    18  
    19  // MapGroupType makes the map slot group type given the type of the map.
    20  func MapGroupType(t *types.Type) *types.Type {
    21  	if t.MapType().Group != nil {
    22  		return t.MapType().Group
    23  	}
    24  
    25  	// Builds a type representing a group structure for the given map type.
    26  	// This type is not visible to users, we include it so we can generate
    27  	// a correct GC program for it.
    28  	//
    29  	// Make sure this stays in sync with internal/runtime/maps/group.go.
    30  
    31  	keytype := t.Key()
    32  	elemtype := t.Elem()
    33  	types.CalcSize(keytype)
    34  	types.CalcSize(elemtype)
    35  	if keytype.Size() > abi.MapMaxKeyBytes {
    36  		keytype = types.NewPtr(keytype)
    37  	}
    38  	if elemtype.Size() > abi.MapMaxElemBytes {
    39  		elemtype = types.NewPtr(elemtype)
    40  	}
    41  
    42  	var fields []*types.Field
    43  	if buildcfg.Experiment.MapSplitGroup {
    44  		// Split layout (KKKKVVVV):
    45  		// type group struct {
    46  		//     ctrl  uint64
    47  		//     keys  [abi.MapGroupSlots]keyType
    48  		//     elems [abi.MapGroupSlots]elemType
    49  		// }
    50  		keyArr := types.NewArray(keytype, abi.MapGroupSlots)
    51  		keyArr.SetNoalg(true)
    52  
    53  		elemArr := types.NewArray(elemtype, abi.MapGroupSlots)
    54  		elemArr.SetNoalg(true)
    55  
    56  		fields = []*types.Field{
    57  			makefield("ctrl", types.Types[types.TUINT64]),
    58  			makefield("keys", keyArr),
    59  			makefield("elems", elemArr),
    60  		}
    61  	} else {
    62  		// Interleaved slot layout (KVKVKVKV):
    63  		// type group struct {
    64  		//     ctrl  uint64
    65  		//     slots [abi.MapGroupSlots]struct {
    66  		//         key  keyType
    67  		//         elem elemType
    68  		//     }
    69  		// }
    70  		slotFields := []*types.Field{
    71  			makefield("key", keytype),
    72  			makefield("elem", elemtype),
    73  		}
    74  		slot := types.NewStruct(slotFields)
    75  		slot.SetNoalg(true)
    76  
    77  		slotArr := types.NewArray(slot, abi.MapGroupSlots)
    78  		slotArr.SetNoalg(true)
    79  
    80  		fields = []*types.Field{
    81  			makefield("ctrl", types.Types[types.TUINT64]),
    82  			makefield("slots", slotArr),
    83  		}
    84  	}
    85  
    86  	group := types.NewStruct(fields)
    87  	group.SetNoalg(true)
    88  	types.CalcSize(group)
    89  
    90  	// Check invariants that map code depends on.
    91  	if !types.IsComparable(t.Key()) {
    92  		base.Fatalf("unsupported map key type for %v", t)
    93  	}
    94  	if group.Size() <= 8 {
    95  		// internal/runtime/maps creates pointers to slots, even if
    96  		// both key and elem are size zero. In this case, each slot is
    97  		// size 0, but group should still reserve a word of padding at
    98  		// the end to ensure pointers are valid.
    99  		base.Fatalf("bad group size for %v", t)
   100  	}
   101  	if t.Key().Size() > abi.MapMaxKeyBytes && !keytype.IsPtr() {
   102  		base.Fatalf("key indirect incorrect for %v", t)
   103  	}
   104  	if t.Elem().Size() > abi.MapMaxElemBytes && !elemtype.IsPtr() {
   105  		base.Fatalf("elem indirect incorrect for %v", t)
   106  	}
   107  
   108  	t.MapType().Group = group
   109  	group.StructType().Map = t
   110  	return group
   111  }
   112  
   113  var cachedMapTableType *types.Type
   114  
   115  // mapTableType returns a type interchangeable with internal/runtime/maps.table.
   116  // Make sure this stays in sync with internal/runtime/maps/table.go.
   117  func mapTableType() *types.Type {
   118  	if cachedMapTableType != nil {
   119  		return cachedMapTableType
   120  	}
   121  
   122  	// type table struct {
   123  	//     used       uint16
   124  	//     capacity   uint16
   125  	//     growthLeft uint16
   126  	//     localDepth uint8
   127  	//     // N.B Padding
   128  	//
   129  	//     index int
   130  	//
   131  	//     // From groups.
   132  	//     groups_data       unsafe.Pointer
   133  	//     groups_lengthMask uint64
   134  	// }
   135  	// must match internal/runtime/maps/table.go:table.
   136  	fields := []*types.Field{
   137  		makefield("used", types.Types[types.TUINT16]),
   138  		makefield("capacity", types.Types[types.TUINT16]),
   139  		makefield("growthLeft", types.Types[types.TUINT16]),
   140  		makefield("localDepth", types.Types[types.TUINT8]),
   141  		makefield("index", types.Types[types.TINT]),
   142  		makefield("groups_data", types.Types[types.TUNSAFEPTR]),
   143  		makefield("groups_lengthMask", types.Types[types.TUINT64]),
   144  	}
   145  
   146  	n := ir.NewDeclNameAt(src.NoXPos, ir.OTYPE, ir.Pkgs.InternalMaps.Lookup("table"))
   147  	table := types.NewNamed(n)
   148  	n.SetType(table)
   149  	n.SetTypecheck(1)
   150  
   151  	table.SetUnderlying(types.NewStruct(fields))
   152  	types.CalcSize(table)
   153  
   154  	// The size of table should be 32 bytes on 64 bit
   155  	// and 24 bytes on 32 bit platforms.
   156  	if size := int64(3*2 + 2*1 /* one extra for padding */ + 1*8 + 2*types.PtrSize); table.Size() != size {
   157  		base.Fatalf("internal/runtime/maps.table size not correct: got %d, want %d", table.Size(), size)
   158  	}
   159  
   160  	cachedMapTableType = table
   161  	return table
   162  }
   163  
   164  var cachedMapType *types.Type
   165  
   166  // MapType returns a type interchangeable with internal/runtime/maps.Map.
   167  // Make sure this stays in sync with internal/runtime/maps/map.go.
   168  func MapType() *types.Type {
   169  	if cachedMapType != nil {
   170  		return cachedMapType
   171  	}
   172  
   173  	// type Map struct {
   174  	//     used uint64
   175  	//     seed uintptr
   176  	//
   177  	//     dirPtr unsafe.Pointer
   178  	//     dirLen int
   179  	//
   180  	//     globalDepth uint8
   181  	//     globalShift uint8
   182  	//
   183  	//     writing uint8
   184  	//     tombstonePossible bool
   185  	//     // N.B Padding
   186  	//
   187  	//     clearSeq uint64
   188  	// }
   189  	// must match internal/runtime/maps/map.go:Map.
   190  	fields := []*types.Field{
   191  		makefield("used", types.Types[types.TUINT64]),
   192  		makefield("seed", types.Types[types.TUINTPTR]),
   193  		makefield("dirPtr", types.Types[types.TUNSAFEPTR]),
   194  		makefield("dirLen", types.Types[types.TINT]),
   195  		makefield("globalDepth", types.Types[types.TUINT8]),
   196  		makefield("globalShift", types.Types[types.TUINT8]),
   197  		makefield("writing", types.Types[types.TUINT8]),
   198  		makefield("tombstonePossible", types.Types[types.TBOOL]),
   199  		makefield("clearSeq", types.Types[types.TUINT64]),
   200  	}
   201  
   202  	n := ir.NewDeclNameAt(src.NoXPos, ir.OTYPE, ir.Pkgs.InternalMaps.Lookup("Map"))
   203  	m := types.NewNamed(n)
   204  	n.SetType(m)
   205  	n.SetTypecheck(1)
   206  
   207  	m.SetUnderlying(types.NewStruct(fields))
   208  	types.CalcSize(m)
   209  
   210  	// The size of Map should be 48 bytes on 64 bit
   211  	// and 32 bytes on 32 bit platforms.
   212  	if size := int64(2*8 + 4*types.PtrSize /* one extra for globalDepth/globalShift/writing + padding */); m.Size() != size {
   213  		base.Fatalf("internal/runtime/maps.Map size not correct: got %d, want %d", m.Size(), size)
   214  	}
   215  
   216  	cachedMapType = m
   217  	return m
   218  }
   219  
   220  var cachedMapIterType *types.Type
   221  
   222  // MapIterType returns a type interchangeable with internal/runtime/maps.Iter.
   223  // Make sure this stays in sync with internal/runtime/maps/table.go.
   224  func MapIterType() *types.Type {
   225  	if cachedMapIterType != nil {
   226  		return cachedMapIterType
   227  	}
   228  
   229  	// type Iter struct {
   230  	//    key  unsafe.Pointer // *Key
   231  	//    elem unsafe.Pointer // *Elem
   232  	//    typ  unsafe.Pointer // *MapType
   233  	//    m    *Map
   234  	//
   235  	//    groupSlotOffset uint64
   236  	//    dirOffset       uint64
   237  	//
   238  	//    clearSeq uint64
   239  	//
   240  	//    globalDepth uint8
   241  	//    // N.B. padding
   242  	//
   243  	//    dirIdx int
   244  	//
   245  	//    tab *table
   246  	//
   247  	//    group unsafe.Pointer // actually groupReference.data
   248  	//
   249  	//    entryIdx uint64
   250  	// }
   251  	// must match internal/runtime/maps/table.go:Iter.
   252  	fields := []*types.Field{
   253  		makefield("key", types.Types[types.TUNSAFEPTR]),  // Used in range.go for TMAP.
   254  		makefield("elem", types.Types[types.TUNSAFEPTR]), // Used in range.go for TMAP.
   255  		makefield("typ", types.Types[types.TUNSAFEPTR]),
   256  		makefield("m", types.NewPtr(MapType())),
   257  		makefield("groupSlotOffset", types.Types[types.TUINT64]),
   258  		makefield("dirOffset", types.Types[types.TUINT64]),
   259  		makefield("clearSeq", types.Types[types.TUINT64]),
   260  		makefield("globalDepth", types.Types[types.TUINT8]),
   261  		makefield("dirIdx", types.Types[types.TINT]),
   262  		makefield("tab", types.NewPtr(mapTableType())),
   263  		makefield("group", types.Types[types.TUNSAFEPTR]),
   264  		makefield("entryIdx", types.Types[types.TUINT64]),
   265  	}
   266  
   267  	// build iterator struct holding the above fields
   268  	n := ir.NewDeclNameAt(src.NoXPos, ir.OTYPE, ir.Pkgs.InternalMaps.Lookup("Iter"))
   269  	iter := types.NewNamed(n)
   270  	n.SetType(iter)
   271  	n.SetTypecheck(1)
   272  
   273  	iter.SetUnderlying(types.NewStruct(fields))
   274  	types.CalcSize(iter)
   275  
   276  	// The size of Iter should be 96 bytes on 64 bit
   277  	// and 64 bytes on 32 bit platforms.
   278  	if size := 8*types.PtrSize /* one extra for globalDepth + padding */ + 4*8; iter.Size() != int64(size) {
   279  		base.Fatalf("internal/runtime/maps.Iter size not correct: got %d, want %d", iter.Size(), size)
   280  	}
   281  
   282  	cachedMapIterType = iter
   283  	return iter
   284  }
   285  
   286  func writeMapType(t *types.Type, lsym *obj.LSym, c rttype.Cursor) {
   287  	// internal/abi.MapType
   288  	gtyp := MapGroupType(t)
   289  	s1 := writeType(t.Key())
   290  	s2 := writeType(t.Elem())
   291  	s3 := writeType(gtyp)
   292  	hasher := genhash(t.Key())
   293  
   294  	var keysOff int64
   295  	var keyStride int64
   296  	var elemsOff int64
   297  	var elemStride int64
   298  	var elemOff int64
   299  	if buildcfg.Experiment.MapSplitGroup {
   300  		// Split layout: field 1 is keys array, field 2 is elems array.
   301  		keysOff = gtyp.Field(1).Offset
   302  		keyStride = gtyp.Field(1).Type.Elem().Size()
   303  		elemsOff = gtyp.Field(2).Offset
   304  		elemStride = gtyp.Field(2).Type.Elem().Size()
   305  	} else {
   306  		// Interleaved layout: field 1 is slots array.
   307  		// KeysOff = offset of slots array (first key).
   308  		// KeyStride = ElemStride = slot stride.
   309  		// ElemsOff = offset of slots + offset of elem within slot.
   310  		keysOff = gtyp.Field(1).Offset
   311  		slotTyp := gtyp.Field(1).Type.Elem()
   312  		slotSize := slotTyp.Size()
   313  		elemOffInSlot := slotTyp.Field(1).Offset
   314  		keyStride = slotSize
   315  		elemsOff = keysOff + elemOffInSlot
   316  		elemStride = slotSize
   317  		elemOff = slotTyp.Field(1).Offset
   318  	}
   319  
   320  	c.Field("Key").WritePtr(s1)
   321  	c.Field("Elem").WritePtr(s2)
   322  	c.Field("Group").WritePtr(s3)
   323  	c.Field("Hasher").WritePtr(hasher)
   324  	c.Field("GroupSize").WriteUintptr(uint64(gtyp.Size()))
   325  	c.Field("KeysOff").WriteUintptr(uint64(keysOff))
   326  	c.Field("KeyStride").WriteUintptr(uint64(keyStride))
   327  	c.Field("ElemsOff").WriteUintptr(uint64(elemsOff))
   328  	c.Field("ElemStride").WriteUintptr(uint64(elemStride))
   329  	c.Field("ElemOff").WriteUintptr(uint64(elemOff))
   330  	var flags uint32
   331  	if needkeyupdate(t.Key()) {
   332  		flags |= abi.MapNeedKeyUpdate
   333  	}
   334  	if hashMightPanic(t.Key()) {
   335  		flags |= abi.MapHashMightPanic
   336  	}
   337  	if t.Key().Size() > abi.MapMaxKeyBytes {
   338  		flags |= abi.MapIndirectKey
   339  	}
   340  	if t.Elem().Size() > abi.MapMaxElemBytes {
   341  		flags |= abi.MapIndirectElem
   342  	}
   343  	c.Field("Flags").WriteUint32(flags)
   344  
   345  	if u := t.Underlying(); u != t {
   346  		// If t is a named map type, also keep the underlying map
   347  		// type live in the binary. This is important to make sure that
   348  		// a named map and that same map cast to its underlying type via
   349  		// reflection, use the same hash function. See issue 37716.
   350  		lsym.AddRel(base.Ctxt, obj.Reloc{Type: objabi.R_KEEP, Sym: writeType(u)})
   351  	}
   352  }
   353
View as plain text