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