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  	//     groups_entryMask  uint64
   113  	// }
   114  	// must match internal/runtime/maps/table.go:table.
   115  	fields := []*types.Field{
   116  		makefield("used", types.Types[types.TUINT16]),
   117  		makefield("capacity", types.Types[types.TUINT16]),
   118  		makefield("growthLeft", types.Types[types.TUINT16]),
   119  		makefield("localDepth", types.Types[types.TUINT8]),
   120  		makefield("index", types.Types[types.TINT]),
   121  		makefield("groups_data", types.Types[types.TUNSAFEPTR]),
   122  		makefield("groups_lengthMask", types.Types[types.TUINT64]),
   123  		makefield("groups_entryMask", types.Types[types.TUINT64]),
   124  	}
   125  
   126  	n := ir.NewDeclNameAt(src.NoXPos, ir.OTYPE, ir.Pkgs.InternalMaps.Lookup("table"))
   127  	table := types.NewNamed(n)
   128  	n.SetType(table)
   129  	n.SetTypecheck(1)
   130  
   131  	table.SetUnderlying(types.NewStruct(fields))
   132  	types.CalcSize(table)
   133  
   134  	// The size of table should be 40 bytes on 64 bit
   135  	// and 32 bytes on 32 bit platforms.
   136  	if size := int64(3*2 + 2*1 /* one extra for padding */ + 2*8 + 2*types.PtrSize); table.Size() != size {
   137  		base.Fatalf("internal/runtime/maps.table size not correct: got %d, want %d", table.Size(), size)
   138  	}
   139  
   140  	cachedSwissTableType = table
   141  	return table
   142  }
   143  
   144  var cachedSwissMapType *types.Type
   145  
   146  // SwissMapType returns a type interchangeable with internal/runtime/maps.Map.
   147  // Make sure this stays in sync with internal/runtime/maps/map.go.
   148  func SwissMapType() *types.Type {
   149  	if cachedSwissMapType != nil {
   150  		return cachedSwissMapType
   151  	}
   152  
   153  	// type Map struct {
   154  	//     used uint64
   155  	//     seed uintptr
   156  	//
   157  	//     dirPtr unsafe.Pointer
   158  	//     dirLen int
   159  	//
   160  	//     globalDepth uint8
   161  	//     globalShift uint8
   162  	//
   163  	//     writing uint8
   164  	//     // N.B Padding
   165  	//
   166  	//     clearSeq uint64
   167  	// }
   168  	// must match internal/runtime/maps/map.go:Map.
   169  	fields := []*types.Field{
   170  		makefield("used", types.Types[types.TUINT64]),
   171  		makefield("seed", types.Types[types.TUINTPTR]),
   172  		makefield("dirPtr", types.Types[types.TUNSAFEPTR]),
   173  		makefield("dirLen", types.Types[types.TINT]),
   174  		makefield("globalDepth", types.Types[types.TUINT8]),
   175  		makefield("globalShift", types.Types[types.TUINT8]),
   176  		makefield("writing", types.Types[types.TUINT8]),
   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  
   275  	c.Field("Key").WritePtr(s1)
   276  	c.Field("Elem").WritePtr(s2)
   277  	c.Field("Group").WritePtr(s3)
   278  	c.Field("Hasher").WritePtr(hasher)
   279  	c.Field("SlotSize").WriteUintptr(uint64(slotTyp.Size()))
   280  	c.Field("ElemOff").WriteUintptr(uint64(elemOff))
   281  	var flags uint32
   282  	if needkeyupdate(t.Key()) {
   283  		flags |= abi.SwissMapNeedKeyUpdate
   284  	}
   285  	if hashMightPanic(t.Key()) {
   286  		flags |= abi.SwissMapHashMightPanic
   287  	}
   288  	if t.Key().Size() > abi.SwissMapMaxKeyBytes {
   289  		flags |= abi.SwissMapIndirectKey
   290  	}
   291  	if t.Elem().Size() > abi.SwissMapMaxKeyBytes {
   292  		flags |= abi.SwissMapIndirectElem
   293  	}
   294  	c.Field("Flags").WriteUint32(flags)
   295  
   296  	if u := t.Underlying(); u != t {
   297  		// If t is a named map type, also keep the underlying map
   298  		// type live in the binary. This is important to make sure that
   299  		// a named map and that same map cast to its underlying type via
   300  		// reflection, use the same hash function. See issue 37716.
   301  		lsym.AddRel(base.Ctxt, obj.Reloc{Type: objabi.R_KEEP, Sym: writeType(u)})
   302  	}
   303  }
   304
View as plain text