src/cmd/compile/internal/reflectdata/reflect.go

   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 reflectdata
   6
   7 import (
   8         "encoding/binary"
   9         "fmt"
  10         "os"
  11         "sort"
  12         "strings"
  13         "sync"
  14
  15         "cmd/compile/internal/base"
  16         "cmd/compile/internal/bitvec"
  17         "cmd/compile/internal/escape"
  18         "cmd/compile/internal/inline"
  19         "cmd/compile/internal/ir"
  20         "cmd/compile/internal/objw"
  21         "cmd/compile/internal/staticdata"
  22         "cmd/compile/internal/typebits"
  23         "cmd/compile/internal/typecheck"
  24         "cmd/compile/internal/types"
  25         "cmd/internal/gcprog"
  26         "cmd/internal/obj"
  27         "cmd/internal/objabi"
  28         "cmd/internal/src"
  29 )
  30
  31 type ptabEntry struct {
  32         s *types.Sym
  33         t *types.Type
  34 }
  35
  36 func CountPTabs() int {
  37         return len(ptabs)
  38 }
  39
  40 // runtime interface and reflection data structures
  41 var (
  42         // protects signatset and signatslice
  43         signatmu sync.Mutex
  44         // Tracking which types need runtime type descriptor
  45         signatset = make(map[*types.Type]struct{})
  46         // Queue of types wait to be generated runtime type descriptor
  47         signatslice []typeAndStr
  48
  49         gcsymmu  sync.Mutex // protects gcsymset and gcsymslice
  50         gcsymset = make(map[*types.Type]struct{})
  51
  52         ptabs []*ir.Name
  53 )
  54
  55 type typeSig struct {
  56         name  *types.Sym
  57         isym  *obj.LSym
  58         tsym  *obj.LSym
  59         type_ *types.Type
  60         mtype *types.Type
  61 }
  62
  63 // Builds a type representing a Bucket structure for
  64 // the given map type. This type is not visible to users -
  65 // we include only enough information to generate a correct GC
  66 // program for it.
  67 // Make sure this stays in sync with runtime/map.go.
  68 const (
  69         BUCKETSIZE  = 8
  70         MAXKEYSIZE  = 128
  71         MAXELEMSIZE = 128
  72 )
  73
  74 func structfieldSize() int { return 3 * types.PtrSize }       // Sizeof(runtime.structfield{})
  75 func imethodSize() int     { return 4 + 4 }                   // Sizeof(runtime.imethod{})
  76 func commonSize() int      { return 4*types.PtrSize + 8 + 8 } // Sizeof(runtime._type{})
  77
  78 func uncommonSize(t *types.Type) int { // Sizeof(runtime.uncommontype{})
  79         if t.Sym() == nil && len(methods(t)) == 0 {
  80                 return 0
  81         }
  82         return 4 + 2 + 2 + 4 + 4
  83 }
  84
  85 func makefield(name string, t *types.Type) *types.Field {
  86         sym := (*types.Pkg)(nil).Lookup(name)
  87         return types.NewField(src.NoXPos, sym, t)
  88 }
  89
  90 // MapBucketType makes the map bucket type given the type of the map.
  91 func MapBucketType(t *types.Type) *types.Type {
  92         if t.MapType().Bucket != nil {
  93                 return t.MapType().Bucket
  94         }
  95
  96         keytype := t.Key()
  97         elemtype := t.Elem()
  98         types.CalcSize(keytype)
  99         types.CalcSize(elemtype)
 100         if keytype.Size() > MAXKEYSIZE {
 101                 keytype = types.NewPtr(keytype)
 102         }
 103         if elemtype.Size() > MAXELEMSIZE {
 104                 elemtype = types.NewPtr(elemtype)
 105         }
 106
 107         field := make([]*types.Field, 0, 5)
 108
 109         // The first field is: uint8 topbits[BUCKETSIZE].
 110         arr := types.NewArray(types.Types[types.TUINT8], BUCKETSIZE)
 111         field = append(field, makefield("topbits", arr))
 112
 113         arr = types.NewArray(keytype, BUCKETSIZE)
 114         arr.SetNoalg(true)
 115         keys := makefield("keys", arr)
 116         field = append(field, keys)
 117
 118         arr = types.NewArray(elemtype, BUCKETSIZE)
 119         arr.SetNoalg(true)
 120         elems := makefield("elems", arr)
 121         field = append(field, elems)
 122
 123         // If keys and elems have no pointers, the map implementation
 124         // can keep a list of overflow pointers on the side so that
 125         // buckets can be marked as having no pointers.
 126         // Arrange for the bucket to have no pointers by changing
 127         // the type of the overflow field to uintptr in this case.
 128         // See comment on hmap.overflow in runtime/map.go.
 129         otyp := types.Types[types.TUNSAFEPTR]
 130         if !elemtype.HasPointers() && !keytype.HasPointers() {
 131                 otyp = types.Types[types.TUINTPTR]
 132         }
 133         overflow := makefield("overflow", otyp)
 134         field = append(field, overflow)
 135
 136         // link up fields
 137         bucket := types.NewStruct(types.NoPkg, field[:])
 138         bucket.SetNoalg(true)
 139         types.CalcSize(bucket)
 140
 141         // Check invariants that map code depends on.
 142         if !types.IsComparable(t.Key()) {
 143                 base.Fatalf("unsupported map key type for %v", t)
 144         }
 145         if BUCKETSIZE < 8 {
 146                 base.Fatalf("bucket size too small for proper alignment")
 147         }
 148         if uint8(keytype.Alignment()) > BUCKETSIZE {
 149                 base.Fatalf("key align too big for %v", t)
 150         }
 151         if uint8(elemtype.Alignment()) > BUCKETSIZE {
 152                 base.Fatalf("elem align too big for %v", t)
 153         }
 154         if keytype.Size() > MAXKEYSIZE {
 155                 base.Fatalf("key size to large for %v", t)
 156         }
 157         if elemtype.Size() > MAXELEMSIZE {
 158                 base.Fatalf("elem size to large for %v", t)
 159         }
 160         if t.Key().Size() > MAXKEYSIZE && !keytype.IsPtr() {
 161                 base.Fatalf("key indirect incorrect for %v", t)
 162         }
 163         if t.Elem().Size() > MAXELEMSIZE && !elemtype.IsPtr() {
 164                 base.Fatalf("elem indirect incorrect for %v", t)
 165         }
 166         if keytype.Size()%keytype.Alignment() != 0 {
 167                 base.Fatalf("key size not a multiple of key align for %v", t)
 168         }
 169         if elemtype.Size()%elemtype.Alignment() != 0 {
 170                 base.Fatalf("elem size not a multiple of elem align for %v", t)
 171         }
 172         if uint8(bucket.Alignment())%uint8(keytype.Alignment()) != 0 {
 173                 base.Fatalf("bucket align not multiple of key align %v", t)
 174         }
 175         if uint8(bucket.Alignment())%uint8(elemtype.Alignment()) != 0 {
 176                 base.Fatalf("bucket align not multiple of elem align %v", t)
 177         }
 178         if keys.Offset%keytype.Alignment() != 0 {
 179                 base.Fatalf("bad alignment of keys in bmap for %v", t)
 180         }
 181         if elems.Offset%elemtype.Alignment() != 0 {
 182                 base.Fatalf("bad alignment of elems in bmap for %v", t)
 183         }
 184
 185         // Double-check that overflow field is final memory in struct,
 186         // with no padding at end.
 187         if overflow.Offset != bucket.Size()-int64(types.PtrSize) {
 188                 base.Fatalf("bad offset of overflow in bmap for %v", t)
 189         }
 190
 191         t.MapType().Bucket = bucket
 192
 193         bucket.StructType().Map = t
 194         return bucket
 195 }
 196
 197 // MapType builds a type representing a Hmap structure for the given map type.
 198 // Make sure this stays in sync with runtime/map.go.
 199 func MapType(t *types.Type) *types.Type {
 200         if t.MapType().Hmap != nil {
 201                 return t.MapType().Hmap
 202         }
 203
 204         bmap := MapBucketType(t)
 205
 206         // build a struct:
 207         // type hmap struct {
 208         //    count      int
 209         //    flags      uint8
 210         //    B          uint8
 211         //    noverflow  uint16
 212         //    hash0      uint32
 213         //    buckets    *bmap
 214         //    oldbuckets *bmap
 215         //    nevacuate  uintptr
 216         //    extra      unsafe.Pointer // *mapextra
 217         // }
 218         // must match runtime/map.go:hmap.
 219         fields := []*types.Field{
 220                 makefield("count", types.Types[types.TINT]),
 221                 makefield("flags", types.Types[types.TUINT8]),
 222                 makefield("B", types.Types[types.TUINT8]),
 223                 makefield("noverflow", types.Types[types.TUINT16]),
 224                 makefield("hash0", types.Types[types.TUINT32]), // Used in walk.go for OMAKEMAP.
 225                 makefield("buckets", types.NewPtr(bmap)),       // Used in walk.go for OMAKEMAP.
 226                 makefield("oldbuckets", types.NewPtr(bmap)),
 227                 makefield("nevacuate", types.Types[types.TUINTPTR]),
 228                 makefield("extra", types.Types[types.TUNSAFEPTR]),
 229         }
 230
 231         hmap := types.NewStruct(types.NoPkg, fields)
 232         hmap.SetNoalg(true)
 233         types.CalcSize(hmap)
 234
 235         // The size of hmap should be 48 bytes on 64 bit
 236         // and 28 bytes on 32 bit platforms.
 237         if size := int64(8 + 5*types.PtrSize); hmap.Size() != size {
 238                 base.Fatalf("hmap size not correct: got %d, want %d", hmap.Size(), size)
 239         }
 240
 241         t.MapType().Hmap = hmap
 242         hmap.StructType().Map = t
 243         return hmap
 244 }
 245
 246 // MapIterType builds a type representing an Hiter structure for the given map type.
 247 // Make sure this stays in sync with runtime/map.go.
 248 func MapIterType(t *types.Type) *types.Type {
 249         if t.MapType().Hiter != nil {
 250                 return t.MapType().Hiter
 251         }
 252
 253         hmap := MapType(t)
 254         bmap := MapBucketType(t)
 255
 256         // build a struct:
 257         // type hiter struct {
 258         //    key         *Key
 259         //    elem        *Elem
 260         //    t           unsafe.Pointer // *MapType
 261         //    h           *hmap
 262         //    buckets     *bmap
 263         //    bptr        *bmap
 264         //    overflow    unsafe.Pointer // *[]*bmap
 265         //    oldoverflow unsafe.Pointer // *[]*bmap
 266         //    startBucket uintptr
 267         //    offset      uint8
 268         //    wrapped     bool
 269         //    B           uint8
 270         //    i           uint8
 271         //    bucket      uintptr
 272         //    checkBucket uintptr
 273         // }
 274         // must match runtime/map.go:hiter.
 275         fields := []*types.Field{
 276                 makefield("key", types.NewPtr(t.Key())),   // Used in range.go for TMAP.
 277                 makefield("elem", types.NewPtr(t.Elem())), // Used in range.go for TMAP.
 278                 makefield("t", types.Types[types.TUNSAFEPTR]),
 279                 makefield("h", types.NewPtr(hmap)),
 280                 makefield("buckets", types.NewPtr(bmap)),
 281                 makefield("bptr", types.NewPtr(bmap)),
 282                 makefield("overflow", types.Types[types.TUNSAFEPTR]),
 283                 makefield("oldoverflow", types.Types[types.TUNSAFEPTR]),
 284                 makefield("startBucket", types.Types[types.TUINTPTR]),
 285                 makefield("offset", types.Types[types.TUINT8]),
 286                 makefield("wrapped", types.Types[types.TBOOL]),
 287                 makefield("B", types.Types[types.TUINT8]),
 288                 makefield("i", types.Types[types.TUINT8]),
 289                 makefield("bucket", types.Types[types.TUINTPTR]),
 290                 makefield("checkBucket", types.Types[types.TUINTPTR]),
 291         }
 292
 293         // build iterator struct holding the above fields
 294         hiter := types.NewStruct(types.NoPkg, fields)
 295         hiter.SetNoalg(true)
 296         types.CalcSize(hiter)
 297         if hiter.Size() != int64(12*types.PtrSize) {
 298                 base.Fatalf("hash_iter size not correct %d %d", hiter.Size(), 12*types.PtrSize)
 299         }
 300         t.MapType().Hiter = hiter
 301         hiter.StructType().Map = t
 302         return hiter
 303 }
 304
 305 // methods returns the methods of the non-interface type t, sorted by name.
 306 // Generates stub functions as needed.
 307 func methods(t *types.Type) []*typeSig {
 308         if t.HasShape() {
 309                 // Shape types have no methods.
 310                 return nil
 311         }
 312         // method type
 313         mt := types.ReceiverBaseType(t)
 314
 315         if mt == nil {
 316                 return nil
 317         }
 318         typecheck.CalcMethods(mt)
 319
 320         // make list of methods for t,
 321         // generating code if necessary.
 322         var ms []*typeSig
 323         for _, f := range mt.AllMethods().Slice() {
 324                 if f.Sym == nil {
 325                         base.Fatalf("method with no sym on %v", mt)
 326                 }
 327                 if !f.IsMethod() {
 328                         base.Fatalf("non-method on %v method %v %v", mt, f.Sym, f)
 329                 }
 330                 if f.Type.Recv() == nil {
 331                         base.Fatalf("receiver with no type on %v method %v %v", mt, f.Sym, f)
 332                 }
 333                 if f.Nointerface() && !t.IsFullyInstantiated() {
 334                         // Skip creating method wrappers if f is nointerface. But, if
 335                         // t is an instantiated type, we still have to call
 336                         // methodWrapper, because methodWrapper generates the actual
 337                         // generic method on the type as well.
 338                         continue
 339                 }
 340
 341                 // get receiver type for this particular method.
 342                 // if pointer receiver but non-pointer t and
 343                 // this is not an embedded pointer inside a struct,
 344                 // method does not apply.
 345                 if !types.IsMethodApplicable(t, f) {
 346                         continue
 347                 }
 348
 349                 sig := &typeSig{
 350                         name:  f.Sym,
 351                         isym:  methodWrapper(t, f, true),
 352                         tsym:  methodWrapper(t, f, false),
 353                         type_: typecheck.NewMethodType(f.Type, t),
 354                         mtype: typecheck.NewMethodType(f.Type, nil),
 355                 }
 356                 if f.Nointerface() {
 357                         // In the case of a nointerface method on an instantiated
 358                         // type, don't actually apppend the typeSig.
 359                         continue
 360                 }
 361                 ms = append(ms, sig)
 362         }
 363
 364         return ms
 365 }
 366
 367 // imethods returns the methods of the interface type t, sorted by name.
 368 func imethods(t *types.Type) []*typeSig {
 369         var methods []*typeSig
 370         for _, f := range t.AllMethods().Slice() {
 371                 if f.Type.Kind() != types.TFUNC || f.Sym == nil {
 372                         continue
 373                 }
 374                 if f.Sym.IsBlank() {
 375                         base.Fatalf("unexpected blank symbol in interface method set")
 376                 }
 377                 if n := len(methods); n > 0 {
 378                         last := methods[n-1]
 379                         if !last.name.Less(f.Sym) {
 380                                 base.Fatalf("sigcmp vs sortinter %v %v", last.name, f.Sym)
 381                         }
 382                 }
 383
 384                 sig := &typeSig{
 385                         name:  f.Sym,
 386                         mtype: f.Type,
 387                         type_: typecheck.NewMethodType(f.Type, nil),
 388                 }
 389                 methods = append(methods, sig)
 390
 391                 // NOTE(rsc): Perhaps an oversight that
 392                 // IfaceType.Method is not in the reflect data.
 393                 // Generate the method body, so that compiled
 394                 // code can refer to it.
 395                 methodWrapper(t, f, false)
 396         }
 397
 398         return methods
 399 }
 400
 401 func dimportpath(p *types.Pkg) {
 402         if p.Pathsym != nil {
 403                 return
 404         }
 405
 406         // If we are compiling the runtime package, there are two runtime packages around
 407         // -- localpkg and Pkgs.Runtime. We don't want to produce import path symbols for
 408         // both of them, so just produce one for localpkg.
 409         if base.Ctxt.Pkgpath == "runtime" && p == ir.Pkgs.Runtime {
 410                 return
 411         }
 412
 413         str := p.Path
 414         if p == types.LocalPkg {
 415                 // Note: myimportpath != "", or else dgopkgpath won't call dimportpath.
 416                 str = base.Ctxt.Pkgpath
 417         }
 418
 419         s := base.Ctxt.Lookup("type..importpath." + p.Prefix + ".")
 420         ot := dnameData(s, 0, str, "", nil, false)
 421         objw.Global(s, int32(ot), obj.DUPOK|obj.RODATA)
 422         s.Set(obj.AttrContentAddressable, true)
 423         p.Pathsym = s
 424 }
 425
 426 func dgopkgpath(s *obj.LSym, ot int, pkg *types.Pkg) int {
 427         if pkg == nil {
 428                 return objw.Uintptr(s, ot, 0)
 429         }
 430
 431         if pkg == types.LocalPkg && base.Ctxt.Pkgpath == "" {
 432                 // If we don't know the full import path of the package being compiled
 433                 // (i.e. -p was not passed on the compiler command line), emit a reference to
 434                 // type..importpath.""., which the linker will rewrite using the correct import path.
 435                 // Every package that imports this one directly defines the symbol.
 436                 // See also https://groups.google.com/forum/#!topic/golang-dev/myb9s53HxGQ.
 437                 ns := base.Ctxt.Lookup(`type..importpath."".`)
 438                 return objw.SymPtr(s, ot, ns, 0)
 439         }
 440
 441         dimportpath(pkg)
 442         return objw.SymPtr(s, ot, pkg.Pathsym, 0)
 443 }
 444
 445 // dgopkgpathOff writes an offset relocation in s at offset ot to the pkg path symbol.
 446 func dgopkgpathOff(s *obj.LSym, ot int, pkg *types.Pkg) int {
 447         if pkg == nil {
 448                 return objw.Uint32(s, ot, 0)
 449         }
 450         if pkg == types.LocalPkg && base.Ctxt.Pkgpath == "" {
 451                 // If we don't know the full import path of the package being compiled
 452                 // (i.e. -p was not passed on the compiler command line), emit a reference to
 453                 // type..importpath.""., which the linker will rewrite using the correct import path.
 454                 // Every package that imports this one directly defines the symbol.
 455                 // See also https://groups.google.com/forum/#!topic/golang-dev/myb9s53HxGQ.
 456                 ns := base.Ctxt.Lookup(`type..importpath."".`)
 457                 return objw.SymPtrOff(s, ot, ns)
 458         }
 459
 460         dimportpath(pkg)
 461         return objw.SymPtrOff(s, ot, pkg.Pathsym)
 462 }
 463
 464 // dnameField dumps a reflect.name for a struct field.
 465 func dnameField(lsym *obj.LSym, ot int, spkg *types.Pkg, ft *types.Field) int {
 466         if !types.IsExported(ft.Sym.Name) && ft.Sym.Pkg != spkg {
 467                 base.Fatalf("package mismatch for %v", ft.Sym)
 468         }
 469         nsym := dname(ft.Sym.Name, ft.Note, nil, types.IsExported(ft.Sym.Name))
 470         return objw.SymPtr(lsym, ot, nsym, 0)
 471 }
 472
 473 // dnameData writes the contents of a reflect.name into s at offset ot.
 474 func dnameData(s *obj.LSym, ot int, name, tag string, pkg *types.Pkg, exported bool) int {
 475         if len(name) >= 1<<29 {
 476                 base.Fatalf("name too long: %d %s...", len(name), name[:1024])
 477         }
 478         if len(tag) >= 1<<29 {
 479                 base.Fatalf("tag too long: %d %s...", len(tag), tag[:1024])
 480         }
 481         var nameLen [binary.MaxVarintLen64]byte
 482         nameLenLen := binary.PutUvarint(nameLen[:], uint64(len(name)))
 483         var tagLen [binary.MaxVarintLen64]byte
 484         tagLenLen := binary.PutUvarint(tagLen[:], uint64(len(tag)))
 485
 486         // Encode name and tag. See reflect/type.go for details.
 487         var bits byte
 488         l := 1 + nameLenLen + len(name)
 489         if exported {
 490                 bits |= 1 << 0
 491         }
 492         if len(tag) > 0 {
 493                 l += tagLenLen + len(tag)
 494                 bits |= 1 << 1
 495         }
 496         if pkg != nil {
 497                 bits |= 1 << 2
 498         }
 499         b := make([]byte, l)
 500         b[0] = bits
 501         copy(b[1:], nameLen[:nameLenLen])
 502         copy(b[1+nameLenLen:], name)
 503         if len(tag) > 0 {
 504                 tb := b[1+nameLenLen+len(name):]
 505                 copy(tb, tagLen[:tagLenLen])
 506                 copy(tb[tagLenLen:], tag)
 507         }
 508
 509         ot = int(s.WriteBytes(base.Ctxt, int64(ot), b))
 510
 511         if pkg != nil {
 512                 ot = dgopkgpathOff(s, ot, pkg)
 513         }
 514
 515         return ot
 516 }
 517
 518 var dnameCount int
 519
 520 // dname creates a reflect.name for a struct field or method.
 521 func dname(name, tag string, pkg *types.Pkg, exported bool) *obj.LSym {
 522         // Write out data as "type.." to signal two things to the
 523         // linker, first that when dynamically linking, the symbol
 524         // should be moved to a relro section, and second that the
 525         // contents should not be decoded as a type.
 526         sname := "type..namedata."
 527         if pkg == nil {
 528                 // In the common case, share data with other packages.
 529                 if name == "" {
 530                         if exported {
 531                                 sname += "-noname-exported." + tag
 532                         } else {
 533                                 sname += "-noname-unexported." + tag
 534                         }
 535                 } else {
 536                         if exported {
 537                                 sname += name + "." + tag
 538                         } else {
 539                                 sname += name + "-" + tag
 540                         }
 541                 }
 542         } else {
 543                 sname = fmt.Sprintf(`%s"".%d`, sname, dnameCount)
 544                 dnameCount++
 545         }
 546         s := base.Ctxt.Lookup(sname)
 547         if len(s.P) > 0 {
 548                 return s
 549         }
 550         ot := dnameData(s, 0, name, tag, pkg, exported)
 551         objw.Global(s, int32(ot), obj.DUPOK|obj.RODATA)
 552         s.Set(obj.AttrContentAddressable, true)
 553         return s
 554 }
 555
 556 // dextratype dumps the fields of a runtime.uncommontype.
 557 // dataAdd is the offset in bytes after the header where the
 558 // backing array of the []method field is written (by dextratypeData).
 559 func dextratype(lsym *obj.LSym, ot int, t *types.Type, dataAdd int) int {
 560         m := methods(t)
 561         if t.Sym() == nil && len(m) == 0 {
 562                 return ot
 563         }
 564         noff := int(types.Rnd(int64(ot), int64(types.PtrSize)))
 565         if noff != ot {
 566                 base.Fatalf("unexpected alignment in dextratype for %v", t)
 567         }
 568
 569         for _, a := range m {
 570                 writeType(a.type_)
 571         }
 572
 573         ot = dgopkgpathOff(lsym, ot, typePkg(t))
 574
 575         dataAdd += uncommonSize(t)
 576         mcount := len(m)
 577         if mcount != int(uint16(mcount)) {
 578                 base.Fatalf("too many methods on %v: %d", t, mcount)
 579         }
 580         xcount := sort.Search(mcount, func(i int) bool { return !types.IsExported(m[i].name.Name) })
 581         if dataAdd != int(uint32(dataAdd)) {
 582                 base.Fatalf("methods are too far away on %v: %d", t, dataAdd)
 583         }
 584
 585         ot = objw.Uint16(lsym, ot, uint16(mcount))
 586         ot = objw.Uint16(lsym, ot, uint16(xcount))
 587         ot = objw.Uint32(lsym, ot, uint32(dataAdd))
 588         ot = objw.Uint32(lsym, ot, 0)
 589         return ot
 590 }
 591
 592 func typePkg(t *types.Type) *types.Pkg {
 593         tsym := t.Sym()
 594         if tsym == nil {
 595                 switch t.Kind() {
 596                 case types.TARRAY, types.TSLICE, types.TPTR, types.TCHAN:
 597                         if t.Elem() != nil {
 598                                 tsym = t.Elem().Sym()
 599                         }
 600                 }
 601         }
 602         if tsym != nil && tsym.Pkg != types.BuiltinPkg {
 603                 return tsym.Pkg
 604         }
 605         return nil
 606 }
 607
 608 // dextratypeData dumps the backing array for the []method field of
 609 // runtime.uncommontype.
 610 func dextratypeData(lsym *obj.LSym, ot int, t *types.Type) int {
 611         for _, a := range methods(t) {
 612                 // ../../../../runtime/type.go:/method
 613                 exported := types.IsExported(a.name.Name)
 614                 var pkg *types.Pkg
 615                 if !exported && a.name.Pkg != typePkg(t) {
 616                         pkg = a.name.Pkg
 617                 }
 618                 nsym := dname(a.name.Name, "", pkg, exported)
 619
 620                 ot = objw.SymPtrOff(lsym, ot, nsym)
 621                 ot = dmethodptrOff(lsym, ot, writeType(a.mtype))
 622                 ot = dmethodptrOff(lsym, ot, a.isym)
 623                 ot = dmethodptrOff(lsym, ot, a.tsym)
 624         }
 625         return ot
 626 }
 627
 628 func dmethodptrOff(s *obj.LSym, ot int, x *obj.LSym) int {
 629         objw.Uint32(s, ot, 0)
 630         r := obj.Addrel(s)
 631         r.Off = int32(ot)
 632         r.Siz = 4
 633         r.Sym = x
 634         r.Type = objabi.R_METHODOFF
 635         return ot + 4
 636 }
 637
 638 var kinds = []int{
 639         types.TINT:        objabi.KindInt,
 640         types.TUINT:       objabi.KindUint,
 641         types.TINT8:       objabi.KindInt8,
 642         types.TUINT8:      objabi.KindUint8,
 643         types.TINT16:      objabi.KindInt16,
 644         types.TUINT16:     objabi.KindUint16,
 645         types.TINT32:      objabi.KindInt32,
 646         types.TUINT32:     objabi.KindUint32,
 647         types.TINT64:      objabi.KindInt64,
 648         types.TUINT64:     objabi.KindUint64,
 649         types.TUINTPTR:    objabi.KindUintptr,
 650         types.TFLOAT32:    objabi.KindFloat32,
 651         types.TFLOAT64:    objabi.KindFloat64,
 652         types.TBOOL:       objabi.KindBool,
 653         types.TSTRING:     objabi.KindString,
 654         types.TPTR:        objabi.KindPtr,
 655         types.TSTRUCT:     objabi.KindStruct,
 656         types.TINTER:      objabi.KindInterface,
 657         types.TCHAN:       objabi.KindChan,
 658         types.TMAP:        objabi.KindMap,
 659         types.TARRAY:      objabi.KindArray,
 660         types.TSLICE:      objabi.KindSlice,
 661         types.TFUNC:       objabi.KindFunc,
 662         types.TCOMPLEX64:  objabi.KindComplex64,
 663         types.TCOMPLEX128: objabi.KindComplex128,
 664         types.TUNSAFEPTR:  objabi.KindUnsafePointer,
 665 }
 666
 667 // tflag is documented in reflect/type.go.
 668 //
 669 // tflag values must be kept in sync with copies in:
 670 //   - cmd/compile/internal/reflectdata/reflect.go
 671 //   - cmd/link/internal/ld/decodesym.go
 672 //   - reflect/type.go
 673 //   - runtime/type.go
 674 const (
 675         tflagUncommon      = 1 << 0
 676         tflagExtraStar     = 1 << 1
 677         tflagNamed         = 1 << 2
 678         tflagRegularMemory = 1 << 3
 679 )
 680
 681 var (
 682         memhashvarlen  *obj.LSym
 683         memequalvarlen *obj.LSym
 684 )
 685
 686 // dcommontype dumps the contents of a reflect.rtype (runtime._type).
 687 func dcommontype(lsym *obj.LSym, t *types.Type) int {
 688         types.CalcSize(t)
 689         eqfunc := geneq(t)
 690
 691         sptrWeak := true
 692         var sptr *obj.LSym
 693         if !t.IsPtr() || t.IsPtrElem() {
 694                 tptr := types.NewPtr(t)
 695                 if t.Sym() != nil || methods(tptr) != nil {
 696                         sptrWeak = false
 697                 }
 698                 sptr = writeType(tptr)
 699         }
 700
 701         gcsym, useGCProg, ptrdata := dgcsym(t, true)
 702         delete(gcsymset, t)
 703
 704         // ../../../../reflect/type.go:/^type.rtype
 705         // actual type structure
 706         //      type rtype struct {
 707         //              size          uintptr
 708         //              ptrdata       uintptr
 709         //              hash          uint32
 710         //              tflag         tflag
 711         //              align         uint8
 712         //              fieldAlign    uint8
 713         //              kind          uint8
 714         //              equal         func(unsafe.Pointer, unsafe.Pointer) bool
 715         //              gcdata        *byte
 716         //              str           nameOff
 717         //              ptrToThis     typeOff
 718         //      }
 719         ot := 0
 720         ot = objw.Uintptr(lsym, ot, uint64(t.Size()))
 721         ot = objw.Uintptr(lsym, ot, uint64(ptrdata))
 722         ot = objw.Uint32(lsym, ot, types.TypeHash(t))
 723
 724         var tflag uint8
 725         if uncommonSize(t) != 0 {
 726                 tflag |= tflagUncommon
 727         }
 728         if t.Sym() != nil && t.Sym().Name != "" {
 729                 tflag |= tflagNamed
 730         }
 731         if isRegularMemory(t) {
 732                 tflag |= tflagRegularMemory
 733         }
 734
 735         exported := false
 736         p := t.NameString()
 737         // If we're writing out type T,
 738         // we are very likely to write out type *T as well.
 739         // Use the string "*T"[1:] for "T", so that the two
 740         // share storage. This is a cheap way to reduce the
 741         // amount of space taken up by reflect strings.
 742         if !strings.HasPrefix(p, "*") {
 743                 p = "*" + p
 744                 tflag |= tflagExtraStar
 745                 if t.Sym() != nil {
 746                         exported = types.IsExported(t.Sym().Name)
 747                 }
 748         } else {
 749                 if t.Elem() != nil && t.Elem().Sym() != nil {
 750                         exported = types.IsExported(t.Elem().Sym().Name)
 751                 }
 752         }
 753
 754         ot = objw.Uint8(lsym, ot, tflag)
 755
 756         // runtime (and common sense) expects alignment to be a power of two.
 757         i := int(uint8(t.Alignment()))
 758
 759         if i == 0 {
 760                 i = 1
 761         }
 762         if i&(i-1) != 0 {
 763                 base.Fatalf("invalid alignment %d for %v", uint8(t.Alignment()), t)
 764         }
 765         ot = objw.Uint8(lsym, ot, uint8(t.Alignment())) // align
 766         ot = objw.Uint8(lsym, ot, uint8(t.Alignment())) // fieldAlign
 767
 768         i = kinds[t.Kind()]
 769         if types.IsDirectIface(t) {
 770                 i |= objabi.KindDirectIface
 771         }
 772         if useGCProg {
 773                 i |= objabi.KindGCProg
 774         }
 775         ot = objw.Uint8(lsym, ot, uint8(i)) // kind
 776         if eqfunc != nil {
 777                 ot = objw.SymPtr(lsym, ot, eqfunc, 0) // equality function
 778         } else {
 779                 ot = objw.Uintptr(lsym, ot, 0) // type we can't do == with
 780         }
 781         ot = objw.SymPtr(lsym, ot, gcsym, 0) // gcdata
 782
 783         nsym := dname(p, "", nil, exported)
 784         ot = objw.SymPtrOff(lsym, ot, nsym) // str
 785         // ptrToThis
 786         if sptr == nil {
 787                 ot = objw.Uint32(lsym, ot, 0)
 788         } else if sptrWeak {
 789                 ot = objw.SymPtrWeakOff(lsym, ot, sptr)
 790         } else {
 791                 ot = objw.SymPtrOff(lsym, ot, sptr)
 792         }
 793
 794         return ot
 795 }
 796
 797 // TrackSym returns the symbol for tracking use of field/method f, assumed
 798 // to be a member of struct/interface type t.
 799 func TrackSym(t *types.Type, f *types.Field) *obj.LSym {
 800         return base.PkgLinksym("go.track", t.LinkString()+"."+f.Sym.Name, obj.ABI0)
 801 }
 802
 803 func TypeSymPrefix(prefix string, t *types.Type) *types.Sym {
 804         p := prefix + "." + t.LinkString()
 805         s := types.TypeSymLookup(p)
 806
 807         // This function is for looking up type-related generated functions
 808         // (e.g. eq and hash). Make sure they are indeed generated.
 809         signatmu.Lock()
 810         NeedRuntimeType(t)
 811         signatmu.Unlock()
 812
 813         //print("algsym: %s -> %+S\n", p, s);
 814
 815         return s
 816 }
 817
 818 func TypeSym(t *types.Type) *types.Sym {
 819         if t == nil || (t.IsPtr() && t.Elem() == nil) || t.IsUntyped() {
 820                 base.Fatalf("TypeSym %v", t)
 821         }
 822         if t.Kind() == types.TFUNC && t.Recv() != nil {
 823                 base.Fatalf("misuse of method type: %v", t)
 824         }
 825         s := types.TypeSym(t)
 826         signatmu.Lock()
 827         NeedRuntimeType(t)
 828         signatmu.Unlock()
 829         return s
 830 }
 831
 832 func TypeLinksymPrefix(prefix string, t *types.Type) *obj.LSym {
 833         return TypeSymPrefix(prefix, t).Linksym()
 834 }
 835
 836 func TypeLinksymLookup(name string) *obj.LSym {
 837         return types.TypeSymLookup(name).Linksym()
 838 }
 839
 840 func TypeLinksym(t *types.Type) *obj.LSym {
 841         return TypeSym(t).Linksym()
 842 }
 843
 844 func TypePtr(t *types.Type) *ir.AddrExpr {
 845         n := ir.NewLinksymExpr(base.Pos, TypeLinksym(t), types.Types[types.TUINT8])
 846         return typecheck.Expr(typecheck.NodAddr(n)).(*ir.AddrExpr)
 847 }
 848
 849 // ITabLsym returns the LSym representing the itab for concrete type typ implementing
 850 // interface iface. A dummy tab will be created in the unusual case where typ doesn't
 851 // implement iface. Normally, this wouldn't happen, because the typechecker would
 852 // have reported a compile-time error. This situation can only happen when the
 853 // destination type of a type assert or a type in a type switch is parameterized, so
 854 // it may sometimes, but not always, be a type that can't implement the specified
 855 // interface.
 856 func ITabLsym(typ, iface *types.Type) *obj.LSym {
 857         s, existed := ir.Pkgs.Itab.LookupOK(typ.LinkString() + "," + iface.LinkString())
 858         lsym := s.Linksym()
 859
 860         if !existed {
 861                 writeITab(lsym, typ, iface, true)
 862         }
 863         return lsym
 864 }
 865
 866 // ITabAddr returns an expression representing a pointer to the itab
 867 // for concrete type typ implementing interface iface.
 868 func ITabAddr(typ, iface *types.Type) *ir.AddrExpr {
 869         s, existed := ir.Pkgs.Itab.LookupOK(typ.LinkString() + "," + iface.LinkString())
 870         lsym := s.Linksym()
 871
 872         if !existed {
 873                 writeITab(lsym, typ, iface, false)
 874         }
 875
 876         n := ir.NewLinksymExpr(base.Pos, lsym, types.Types[types.TUINT8])
 877         return typecheck.Expr(typecheck.NodAddr(n)).(*ir.AddrExpr)
 878 }
 879
 880 // needkeyupdate reports whether map updates with t as a key
 881 // need the key to be updated.
 882 func needkeyupdate(t *types.Type) bool {
 883         switch t.Kind() {
 884         case types.TBOOL, types.TINT, types.TUINT, types.TINT8, types.TUINT8, types.TINT16, types.TUINT16, types.TINT32, types.TUINT32,
 885                 types.TINT64, types.TUINT64, types.TUINTPTR, types.TPTR, types.TUNSAFEPTR, types.TCHAN:
 886                 return false
 887
 888         case types.TFLOAT32, types.TFLOAT64, types.TCOMPLEX64, types.TCOMPLEX128, // floats and complex can be +0/-0
 889                 types.TINTER,
 890                 types.TSTRING: // strings might have smaller backing stores
 891                 return true
 892
 893         case types.TARRAY:
 894                 return needkeyupdate(t.Elem())
 895
 896         case types.TSTRUCT:
 897                 for _, t1 := range t.Fields().Slice() {
 898                         if needkeyupdate(t1.Type) {
 899                                 return true
 900                         }
 901                 }
 902                 return false
 903
 904         default:
 905                 base.Fatalf("bad type for map key: %v", t)
 906                 return true
 907         }
 908 }
 909
 910 // hashMightPanic reports whether the hash of a map key of type t might panic.
 911 func hashMightPanic(t *types.Type) bool {
 912         switch t.Kind() {
 913         case types.TINTER:
 914                 return true
 915
 916         case types.TARRAY:
 917                 return hashMightPanic(t.Elem())
 918
 919         case types.TSTRUCT:
 920                 for _, t1 := range t.Fields().Slice() {
 921                         if hashMightPanic(t1.Type) {
 922                                 return true
 923                         }
 924                 }
 925                 return false
 926
 927         default:
 928                 return false
 929         }
 930 }
 931
 932 // formalType replaces predeclared aliases with real types.
 933 // They've been separate internally to make error messages
 934 // better, but we have to merge them in the reflect tables.
 935 func formalType(t *types.Type) *types.Type {
 936         switch t {
 937         case types.AnyType, types.ByteType, types.RuneType:
 938                 return types.Types[t.Kind()]
 939         }
 940         return t
 941 }
 942
 943 func writeType(t *types.Type) *obj.LSym {
 944         t = formalType(t)
 945         if t.IsUntyped() || t.HasTParam() {
 946                 base.Fatalf("writeType %v", t)
 947         }
 948
 949         s := types.TypeSym(t)
 950         lsym := s.Linksym()
 951         if s.Siggen() {
 952                 return lsym
 953         }
 954         s.SetSiggen(true)
 955
 956         // special case (look for runtime below):
 957         // when compiling package runtime,
 958         // emit the type structures for int, float, etc.
 959         tbase := t
 960
 961         if t.IsPtr() && t.Sym() == nil && t.Elem().Sym() != nil {
 962                 tbase = t.Elem()
 963         }
 964         if tbase.Kind() == types.TFORW {
 965                 base.Fatalf("unresolved defined type: %v", tbase)
 966         }
 967
 968         if !NeedEmit(tbase) {
 969                 if i := typecheck.BaseTypeIndex(t); i >= 0 {
 970                         lsym.Pkg = tbase.Sym().Pkg.Prefix
 971                         lsym.SymIdx = int32(i)
 972                         lsym.Set(obj.AttrIndexed, true)
 973                 }
 974
 975                 // TODO(mdempsky): Investigate whether this still happens.
 976                 // If we know we don't need to emit code for a type,
 977                 // we should have a link-symbol index for it.
 978                 // See also TODO in NeedEmit.
 979                 return lsym
 980         }
 981
 982         ot := 0
 983         switch t.Kind() {
 984         default:
 985                 ot = dcommontype(lsym, t)
 986                 ot = dextratype(lsym, ot, t, 0)
 987
 988         case types.TARRAY:
 989                 // ../../../../runtime/type.go:/arrayType
 990                 s1 := writeType(t.Elem())
 991                 t2 := types.NewSlice(t.Elem())
 992                 s2 := writeType(t2)
 993                 ot = dcommontype(lsym, t)
 994                 ot = objw.SymPtr(lsym, ot, s1, 0)
 995                 ot = objw.SymPtr(lsym, ot, s2, 0)
 996                 ot = objw.Uintptr(lsym, ot, uint64(t.NumElem()))
 997                 ot = dextratype(lsym, ot, t, 0)
 998
 999         case types.TSLICE:
1000                 // ../../../../runtime/type.go:/sliceType
1001                 s1 := writeType(t.Elem())
1002                 ot = dcommontype(lsym, t)
1003                 ot = objw.SymPtr(lsym, ot, s1, 0)
1004                 ot = dextratype(lsym, ot, t, 0)
1005
1006         case types.TCHAN:
1007                 // ../../../../runtime/type.go:/chanType
1008                 s1 := writeType(t.Elem())
1009                 ot = dcommontype(lsym, t)
1010                 ot = objw.SymPtr(lsym, ot, s1, 0)
1011                 ot = objw.Uintptr(lsym, ot, uint64(t.ChanDir()))
1012                 ot = dextratype(lsym, ot, t, 0)
1013
1014         case types.TFUNC:
1015                 for _, t1 := range t.Recvs().Fields().Slice() {
1016                         writeType(t1.Type)
1017                 }
1018                 isddd := false
1019                 for _, t1 := range t.Params().Fields().Slice() {
1020                         isddd = t1.IsDDD()
1021                         writeType(t1.Type)
1022                 }
1023                 for _, t1 := range t.Results().Fields().Slice() {
1024                         writeType(t1.Type)
1025                 }
1026
1027                 ot = dcommontype(lsym, t)
1028                 inCount := t.NumRecvs() + t.NumParams()
1029                 outCount := t.NumResults()
1030                 if isddd {
1031                         outCount |= 1 << 15
1032                 }
1033                 ot = objw.Uint16(lsym, ot, uint16(inCount))
1034                 ot = objw.Uint16(lsym, ot, uint16(outCount))
1035                 if types.PtrSize == 8 {
1036                         ot += 4 // align for *rtype
1037                 }
1038
1039                 dataAdd := (inCount + t.NumResults()) * types.PtrSize
1040                 ot = dextratype(lsym, ot, t, dataAdd)
1041
1042                 // Array of rtype pointers follows funcType.
1043                 for _, t1 := range t.Recvs().Fields().Slice() {
1044                         ot = objw.SymPtr(lsym, ot, writeType(t1.Type), 0)
1045                 }
1046                 for _, t1 := range t.Params().Fields().Slice() {
1047                         ot = objw.SymPtr(lsym, ot, writeType(t1.Type), 0)
1048                 }
1049                 for _, t1 := range t.Results().Fields().Slice() {
1050                         ot = objw.SymPtr(lsym, ot, writeType(t1.Type), 0)
1051                 }
1052
1053         case types.TINTER:
1054                 m := imethods(t)
1055                 n := len(m)
1056                 for _, a := range m {
1057                         writeType(a.type_)
1058                 }
1059
1060                 // ../../../../runtime/type.go:/interfaceType
1061                 ot = dcommontype(lsym, t)
1062
1063                 var tpkg *types.Pkg
1064                 if t.Sym() != nil && t != types.Types[t.Kind()] && t != types.ErrorType {
1065                         tpkg = t.Sym().Pkg
1066                 }
1067                 ot = dgopkgpath(lsym, ot, tpkg)
1068
1069                 ot = objw.SymPtr(lsym, ot, lsym, ot+3*types.PtrSize+uncommonSize(t))
1070                 ot = objw.Uintptr(lsym, ot, uint64(n))
1071                 ot = objw.Uintptr(lsym, ot, uint64(n))
1072                 dataAdd := imethodSize() * n
1073                 ot = dextratype(lsym, ot, t, dataAdd)
1074
1075                 for _, a := range m {
1076                         // ../../../../runtime/type.go:/imethod
1077                         exported := types.IsExported(a.name.Name)
1078                         var pkg *types.Pkg
1079                         if !exported && a.name.Pkg != tpkg {
1080                                 pkg = a.name.Pkg
1081                         }
1082                         nsym := dname(a.name.Name, "", pkg, exported)
1083
1084                         ot = objw.SymPtrOff(lsym, ot, nsym)
1085                         ot = objw.SymPtrOff(lsym, ot, writeType(a.type_))
1086                 }
1087
1088         // ../../../../runtime/type.go:/mapType
1089         case types.TMAP:
1090                 s1 := writeType(t.Key())
1091                 s2 := writeType(t.Elem())
1092                 s3 := writeType(MapBucketType(t))
1093                 hasher := genhash(t.Key())
1094
1095                 ot = dcommontype(lsym, t)
1096                 ot = objw.SymPtr(lsym, ot, s1, 0)
1097                 ot = objw.SymPtr(lsym, ot, s2, 0)
1098                 ot = objw.SymPtr(lsym, ot, s3, 0)
1099                 ot = objw.SymPtr(lsym, ot, hasher, 0)
1100                 var flags uint32
1101                 // Note: flags must match maptype accessors in ../../../../runtime/type.go
1102                 // and maptype builder in ../../../../reflect/type.go:MapOf.
1103                 if t.Key().Size() > MAXKEYSIZE {
1104                         ot = objw.Uint8(lsym, ot, uint8(types.PtrSize))
1105                         flags |= 1 // indirect key
1106                 } else {
1107                         ot = objw.Uint8(lsym, ot, uint8(t.Key().Size()))
1108                 }
1109
1110                 if t.Elem().Size() > MAXELEMSIZE {
1111                         ot = objw.Uint8(lsym, ot, uint8(types.PtrSize))
1112                         flags |= 2 // indirect value
1113                 } else {
1114                         ot = objw.Uint8(lsym, ot, uint8(t.Elem().Size()))
1115                 }
1116                 ot = objw.Uint16(lsym, ot, uint16(MapBucketType(t).Size()))
1117                 if types.IsReflexive(t.Key()) {
1118                         flags |= 4 // reflexive key
1119                 }
1120                 if needkeyupdate(t.Key()) {
1121                         flags |= 8 // need key update
1122                 }
1123                 if hashMightPanic(t.Key()) {
1124                         flags |= 16 // hash might panic
1125                 }
1126                 ot = objw.Uint32(lsym, ot, flags)
1127                 ot = dextratype(lsym, ot, t, 0)
1128                 if u := t.Underlying(); u != t {
1129                         // If t is a named map type, also keep the underlying map
1130                         // type live in the binary. This is important to make sure that
1131                         // a named map and that same map cast to its underlying type via
1132                         // reflection, use the same hash function. See issue 37716.
1133                         r := obj.Addrel(lsym)
1134                         r.Sym = writeType(u)
1135                         r.Type = objabi.R_KEEP
1136                 }
1137
1138         case types.TPTR:
1139                 if t.Elem().Kind() == types.TANY {
1140                         // ../../../../runtime/type.go:/UnsafePointerType
1141                         ot = dcommontype(lsym, t)
1142                         ot = dextratype(lsym, ot, t, 0)
1143
1144                         break
1145                 }
1146
1147                 // ../../../../runtime/type.go:/ptrType
1148                 s1 := writeType(t.Elem())
1149
1150                 ot = dcommontype(lsym, t)
1151                 ot = objw.SymPtr(lsym, ot, s1, 0)
1152                 ot = dextratype(lsym, ot, t, 0)
1153
1154         // ../../../../runtime/type.go:/structType
1155         // for security, only the exported fields.
1156         case types.TSTRUCT:
1157                 fields := t.Fields().Slice()
1158
1159                 // omitFieldForAwfulBoringCryptoKludge reports whether
1160                 // the field t should be omitted from the reflect data.
1161                 // In the crypto/... packages we omit an unexported field
1162                 // named "boring", to keep from breaking client code that
1163                 // expects rsa.PublicKey etc to have only public fields.
1164                 // As the name suggests, this is an awful kludge, but it is
1165                 // limited to the dev.boringcrypto branch and avoids
1166                 // much more invasive effects elsewhere.
1167                 omitFieldForAwfulBoringCryptoKludge := func(t *types.Field) bool {
1168                         if t.Sym == nil || t.Sym.Name != "boring" || t.Sym.Pkg == nil {
1169                                 return false
1170                         }
1171                         path := t.Sym.Pkg.Path
1172                         if t.Sym.Pkg == types.LocalPkg {
1173                                 path = base.Ctxt.Pkgpath
1174                         }
1175                         return strings.HasPrefix(path, "crypto/")
1176                 }
1177                 newFields := fields[:0:0]
1178                 for _, t1 := range fields {
1179                         if !omitFieldForAwfulBoringCryptoKludge(t1) {
1180                                 newFields = append(newFields, t1)
1181                         }
1182                 }
1183                 fields = newFields
1184
1185                 for _, t1 := range fields {
1186                         writeType(t1.Type)
1187                 }
1188
1189                 // All non-exported struct field names within a struct
1190                 // type must originate from a single package. By
1191                 // identifying and recording that package within the
1192                 // struct type descriptor, we can omit that
1193                 // information from the field descriptors.
1194                 var spkg *types.Pkg
1195                 for _, f := range fields {
1196                         if !types.IsExported(f.Sym.Name) {
1197                                 spkg = f.Sym.Pkg
1198                                 break
1199                         }
1200                 }
1201
1202                 ot = dcommontype(lsym, t)
1203                 ot = dgopkgpath(lsym, ot, spkg)
1204                 ot = objw.SymPtr(lsym, ot, lsym, ot+3*types.PtrSize+uncommonSize(t))
1205                 ot = objw.Uintptr(lsym, ot, uint64(len(fields)))
1206                 ot = objw.Uintptr(lsym, ot, uint64(len(fields)))
1207
1208                 dataAdd := len(fields) * structfieldSize()
1209                 ot = dextratype(lsym, ot, t, dataAdd)
1210
1211                 for _, f := range fields {
1212                         // ../../../../runtime/type.go:/structField
1213                         ot = dnameField(lsym, ot, spkg, f)
1214                         ot = objw.SymPtr(lsym, ot, writeType(f.Type), 0)
1215                         offsetAnon := uint64(f.Offset) << 1
1216                         if offsetAnon>>1 != uint64(f.Offset) {
1217                                 base.Fatalf("%v: bad field offset for %s", t, f.Sym.Name)
1218                         }
1219                         if f.Embedded != 0 {
1220                                 offsetAnon |= 1
1221                         }
1222                         ot = objw.Uintptr(lsym, ot, offsetAnon)
1223                 }
1224         }
1225
1226         // Note: DUPOK is required to ensure that we don't end up with more
1227         // than one type descriptor for a given type, if the type descriptor
1228         // can be defined in multiple packages, that is, unnamed types and
1229         // instantiated types.
1230         dupok := 0
1231         if tbase.Sym() == nil || tbase.IsFullyInstantiated() {
1232                 dupok = obj.DUPOK
1233         }
1234
1235         ot = dextratypeData(lsym, ot, t)
1236         objw.Global(lsym, int32(ot), int16(dupok|obj.RODATA))
1237
1238         // The linker will leave a table of all the typelinks for
1239         // types in the binary, so the runtime can find them.
1240         //
1241         // When buildmode=shared, all types are in typelinks so the
1242         // runtime can deduplicate type pointers.
1243         keep := base.Ctxt.Flag_dynlink
1244         if !keep && t.Sym() == nil {
1245                 // For an unnamed type, we only need the link if the type can
1246                 // be created at run time by reflect.PtrTo and similar
1247                 // functions. If the type exists in the program, those
1248                 // functions must return the existing type structure rather
1249                 // than creating a new one.
1250                 switch t.Kind() {
1251                 case types.TPTR, types.TARRAY, types.TCHAN, types.TFUNC, types.TMAP, types.TSLICE, types.TSTRUCT:
1252                         keep = true
1253                 }
1254         }
1255         // Do not put Noalg types in typelinks.  See issue #22605.
1256         if types.TypeHasNoAlg(t) {
1257                 keep = false
1258         }
1259         lsym.Set(obj.AttrMakeTypelink, keep)
1260
1261         return lsym
1262 }
1263
1264 // InterfaceMethodOffset returns the offset of the i-th method in the interface
1265 // type descriptor, ityp.
1266 func InterfaceMethodOffset(ityp *types.Type, i int64) int64 {
1267         // interface type descriptor layout is struct {
1268         //   _type        // commonSize
1269         //   pkgpath      // 1 word
1270         //   []imethod    // 3 words (pointing to [...]imethod below)
1271         //   uncommontype // uncommonSize
1272         //   [...]imethod
1273         // }
1274         // The size of imethod is 8.
1275         return int64(commonSize()+4*types.PtrSize+uncommonSize(ityp)) + i*8
1276 }
1277
1278 // NeedRuntimeType ensures that a runtime type descriptor is emitted for t.
1279 func NeedRuntimeType(t *types.Type) {
1280         if t.HasTParam() {
1281                 // Generic types don't really exist at run-time and have no runtime
1282                 // type descriptor.  But we do write out shape types.
1283                 return
1284         }
1285         if _, ok := signatset[t]; !ok {
1286                 signatset[t] = struct{}{}
1287                 signatslice = append(signatslice, typeAndStr{t: t, short: types.TypeSymName(t), regular: t.String()})
1288         }
1289 }
1290
1291 func WriteRuntimeTypes() {
1292         // Process signatslice. Use a loop, as writeType adds
1293         // entries to signatslice while it is being processed.
1294         for len(signatslice) > 0 {
1295                 signats := signatslice
1296                 // Sort for reproducible builds.
1297                 sort.Sort(typesByString(signats))
1298                 for _, ts := range signats {
1299                         t := ts.t
1300                         writeType(t)
1301                         if t.Sym() != nil {
1302                                 writeType(types.NewPtr(t))
1303                         }
1304                 }
1305                 signatslice = signatslice[len(signats):]
1306         }
1307
1308         // Emit GC data symbols.
1309         gcsyms := make([]typeAndStr, 0, len(gcsymset))
1310         for t := range gcsymset {
1311                 gcsyms = append(gcsyms, typeAndStr{t: t, short: types.TypeSymName(t), regular: t.String()})
1312         }
1313         sort.Sort(typesByString(gcsyms))
1314         for _, ts := range gcsyms {
1315                 dgcsym(ts.t, true)
1316         }
1317 }
1318
1319 // writeITab writes the itab for concrete type typ implementing interface iface. If
1320 // allowNonImplement is true, allow the case where typ does not implement iface, and just
1321 // create a dummy itab with zeroed-out method entries.
1322 func writeITab(lsym *obj.LSym, typ, iface *types.Type, allowNonImplement bool) {
1323         // TODO(mdempsky): Fix methodWrapper, geneq, and genhash (and maybe
1324         // others) to stop clobbering these.
1325         oldpos, oldfn := base.Pos, ir.CurFunc
1326         defer func() { base.Pos, ir.CurFunc = oldpos, oldfn }()
1327
1328         if typ == nil || (typ.IsPtr() && typ.Elem() == nil) || typ.IsUntyped() || iface == nil || !iface.IsInterface() || iface.IsEmptyInterface() {
1329                 base.Fatalf("writeITab(%v, %v)", typ, iface)
1330         }
1331
1332         sigs := iface.AllMethods().Slice()
1333         entries := make([]*obj.LSym, 0, len(sigs))
1334
1335         // both sigs and methods are sorted by name,
1336         // so we can find the intersection in a single pass
1337         for _, m := range methods(typ) {
1338                 if m.name == sigs[0].Sym {
1339                         entries = append(entries, m.isym)
1340                         if m.isym == nil {
1341                                 panic("NO ISYM")
1342                         }
1343                         sigs = sigs[1:]
1344                         if len(sigs) == 0 {
1345                                 break
1346                         }
1347                 }
1348         }
1349         completeItab := len(sigs) == 0
1350         if !allowNonImplement && !completeItab {
1351                 base.Fatalf("incomplete itab")
1352         }
1353
1354         // dump empty itab symbol into i.sym
1355         // type itab struct {
1356         //   inter  *interfacetype
1357         //   _type  *_type
1358         //   hash   uint32 // copy of _type.hash. Used for type switches.
1359         //   _      [4]byte
1360         //   fun    [1]uintptr // variable sized. fun[0]==0 means _type does not implement inter.
1361         // }
1362         o := objw.SymPtr(lsym, 0, writeType(iface), 0)
1363         o = objw.SymPtr(lsym, o, writeType(typ), 0)
1364         o = objw.Uint32(lsym, o, types.TypeHash(typ)) // copy of type hash
1365         o += 4                                        // skip unused field
1366         if !completeItab {
1367                 // If typ doesn't implement iface, make method entries be zero.
1368                 o = objw.Uintptr(lsym, o, 0)
1369                 entries = entries[:0]
1370         }
1371         for _, fn := range entries {
1372                 o = objw.SymPtrWeak(lsym, o, fn, 0) // method pointer for each method
1373         }
1374         // Nothing writes static itabs, so they are read only.
1375         objw.Global(lsym, int32(o), int16(obj.DUPOK|obj.RODATA))
1376         lsym.Set(obj.AttrContentAddressable, true)
1377 }
1378
1379 func WriteTabs() {
1380         // process ptabs
1381         if types.LocalPkg.Name == "main" && len(ptabs) > 0 {
1382                 ot := 0
1383                 s := base.Ctxt.Lookup("go.plugin.tabs")
1384                 for _, p := range ptabs {
1385                         // Dump ptab symbol into go.pluginsym package.
1386                         //
1387                         // type ptab struct {
1388                         //      name nameOff
1389                         //      typ  typeOff // pointer to symbol
1390                         // }
1391                         nsym := dname(p.Sym().Name, "", nil, true)
1392                         t := p.Type()
1393                         if p.Class != ir.PFUNC {
1394                                 t = types.NewPtr(t)
1395                         }
1396                         tsym := writeType(t)
1397                         ot = objw.SymPtrOff(s, ot, nsym)
1398                         ot = objw.SymPtrOff(s, ot, tsym)
1399                         // Plugin exports symbols as interfaces. Mark their types
1400                         // as UsedInIface.
1401                         tsym.Set(obj.AttrUsedInIface, true)
1402                 }
1403                 objw.Global(s, int32(ot), int16(obj.RODATA))
1404
1405                 ot = 0
1406                 s = base.Ctxt.Lookup("go.plugin.exports")
1407                 for _, p := range ptabs {
1408                         ot = objw.SymPtr(s, ot, p.Linksym(), 0)
1409                 }
1410                 objw.Global(s, int32(ot), int16(obj.RODATA))
1411         }
1412 }
1413
1414 func WriteImportStrings() {
1415         // generate import strings for imported packages
1416         for _, p := range types.ImportedPkgList() {
1417                 dimportpath(p)
1418         }
1419 }
1420
1421 func WriteBasicTypes() {
1422         // do basic types if compiling package runtime.
1423         // they have to be in at least one package,
1424         // and runtime is always loaded implicitly,
1425         // so this is as good as any.
1426         // another possible choice would be package main,
1427         // but using runtime means fewer copies in object files.
1428         if base.Ctxt.Pkgpath == "runtime" {
1429                 for i := types.Kind(1); i <= types.TBOOL; i++ {
1430                         writeType(types.NewPtr(types.Types[i]))
1431                 }
1432                 writeType(types.NewPtr(types.Types[types.TSTRING]))
1433                 writeType(types.NewPtr(types.Types[types.TUNSAFEPTR]))
1434                 writeType(types.AnyType)
1435
1436                 // emit type structs for error and func(error) string.
1437                 // The latter is the type of an auto-generated wrapper.
1438                 writeType(types.NewPtr(types.ErrorType))
1439
1440                 writeType(types.NewSignature(types.NoPkg, nil, nil, []*types.Field{
1441                         types.NewField(base.Pos, nil, types.ErrorType),
1442                 }, []*types.Field{
1443                         types.NewField(base.Pos, nil, types.Types[types.TSTRING]),
1444                 }))
1445
1446                 // add paths for runtime and main, which 6l imports implicitly.
1447                 dimportpath(ir.Pkgs.Runtime)
1448
1449                 if base.Flag.Race {
1450                         dimportpath(types.NewPkg("runtime/race", ""))
1451                 }
1452                 if base.Flag.MSan {
1453                         dimportpath(types.NewPkg("runtime/msan", ""))
1454                 }
1455                 if base.Flag.ASan {
1456                         dimportpath(types.NewPkg("runtime/asan", ""))
1457                 }
1458
1459                 dimportpath(types.NewPkg("main", ""))
1460         }
1461 }
1462
1463 type typeAndStr struct {
1464         t       *types.Type
1465         short   string // "short" here means TypeSymName
1466         regular string
1467 }
1468
1469 type typesByString []typeAndStr
1470
1471 func (a typesByString) Len() int { return len(a) }
1472 func (a typesByString) Less(i, j int) bool {
1473         if a[i].short != a[j].short {
1474                 return a[i].short < a[j].short
1475         }
1476         // When the only difference between the types is whether
1477         // they refer to byte or uint8, such as **byte vs **uint8,
1478         // the types' NameStrings can be identical.
1479         // To preserve deterministic sort ordering, sort these by String().
1480         //
1481         // TODO(mdempsky): This all seems suspect. Using LinkString would
1482         // avoid naming collisions, and there shouldn't be a reason to care
1483         // about "byte" vs "uint8": they share the same runtime type
1484         // descriptor anyway.
1485         if a[i].regular != a[j].regular {
1486                 return a[i].regular < a[j].regular
1487         }
1488         // Identical anonymous interfaces defined in different locations
1489         // will be equal for the above checks, but different in DWARF output.
1490         // Sort by source position to ensure deterministic order.
1491         // See issues 27013 and 30202.
1492         if a[i].t.Kind() == types.TINTER && a[i].t.AllMethods().Len() > 0 {
1493                 return a[i].t.AllMethods().Index(0).Pos.Before(a[j].t.AllMethods().Index(0).Pos)
1494         }
1495         return false
1496 }
1497 func (a typesByString) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
1498
1499 // maxPtrmaskBytes is the maximum length of a GC ptrmask bitmap,
1500 // which holds 1-bit entries describing where pointers are in a given type.
1501 // Above this length, the GC information is recorded as a GC program,
1502 // which can express repetition compactly. In either form, the
1503 // information is used by the runtime to initialize the heap bitmap,
1504 // and for large types (like 128 or more words), they are roughly the
1505 // same speed. GC programs are never much larger and often more
1506 // compact. (If large arrays are involved, they can be arbitrarily
1507 // more compact.)
1508 //
1509 // The cutoff must be large enough that any allocation large enough to
1510 // use a GC program is large enough that it does not share heap bitmap
1511 // bytes with any other objects, allowing the GC program execution to
1512 // assume an aligned start and not use atomic operations. In the current
1513 // runtime, this means all malloc size classes larger than the cutoff must
1514 // be multiples of four words. On 32-bit systems that's 16 bytes, and
1515 // all size classes >= 16 bytes are 16-byte aligned, so no real constraint.
1516 // On 64-bit systems, that's 32 bytes, and 32-byte alignment is guaranteed
1517 // for size classes >= 256 bytes. On a 64-bit system, 256 bytes allocated
1518 // is 32 pointers, the bits for which fit in 4 bytes. So maxPtrmaskBytes
1519 // must be >= 4.
1520 //
1521 // We used to use 16 because the GC programs do have some constant overhead
1522 // to get started, and processing 128 pointers seems to be enough to
1523 // amortize that overhead well.
1524 //
1525 // To make sure that the runtime's chansend can call typeBitsBulkBarrier,
1526 // we raised the limit to 2048, so that even 32-bit systems are guaranteed to
1527 // use bitmaps for objects up to 64 kB in size.
1528 //
1529 // Also known to reflect/type.go.
1530 const maxPtrmaskBytes = 2048
1531
1532 // GCSym returns a data symbol containing GC information for type t, along
1533 // with a boolean reporting whether the UseGCProg bit should be set in the
1534 // type kind, and the ptrdata field to record in the reflect type information.
1535 // GCSym may be called in concurrent backend, so it does not emit the symbol
1536 // content.
1537 func GCSym(t *types.Type) (lsym *obj.LSym, useGCProg bool, ptrdata int64) {
1538         // Record that we need to emit the GC symbol.
1539         gcsymmu.Lock()
1540         if _, ok := gcsymset[t]; !ok {
1541                 gcsymset[t] = struct{}{}
1542         }
1543         gcsymmu.Unlock()
1544
1545         return dgcsym(t, false)
1546 }
1547
1548 // dgcsym returns a data symbol containing GC information for type t, along
1549 // with a boolean reporting whether the UseGCProg bit should be set in the
1550 // type kind, and the ptrdata field to record in the reflect type information.
1551 // When write is true, it writes the symbol data.
1552 func dgcsym(t *types.Type, write bool) (lsym *obj.LSym, useGCProg bool, ptrdata int64) {
1553         ptrdata = types.PtrDataSize(t)
1554         if ptrdata/int64(types.PtrSize) <= maxPtrmaskBytes*8 {
1555                 lsym = dgcptrmask(t, write)
1556                 return
1557         }
1558
1559         useGCProg = true
1560         lsym, ptrdata = dgcprog(t, write)
1561         return
1562 }
1563
1564 // dgcptrmask emits and returns the symbol containing a pointer mask for type t.
1565 func dgcptrmask(t *types.Type, write bool) *obj.LSym {
1566         ptrmask := make([]byte, (types.PtrDataSize(t)/int64(types.PtrSize)+7)/8)
1567         fillptrmask(t, ptrmask)
1568         p := fmt.Sprintf("runtime.gcbits.%x", ptrmask)
1569
1570         lsym := base.Ctxt.Lookup(p)
1571         if write && !lsym.OnList() {
1572                 for i, x := range ptrmask {
1573                         objw.Uint8(lsym, i, x)
1574                 }
1575                 objw.Global(lsym, int32(len(ptrmask)), obj.DUPOK|obj.RODATA|obj.LOCAL)
1576                 lsym.Set(obj.AttrContentAddressable, true)
1577         }
1578         return lsym
1579 }
1580
1581 // fillptrmask fills in ptrmask with 1s corresponding to the
1582 // word offsets in t that hold pointers.
1583 // ptrmask is assumed to fit at least types.PtrDataSize(t)/PtrSize bits.
1584 func fillptrmask(t *types.Type, ptrmask []byte) {
1585         for i := range ptrmask {
1586                 ptrmask[i] = 0
1587         }
1588         if !t.HasPointers() {
1589                 return
1590         }
1591
1592         vec := bitvec.New(8 * int32(len(ptrmask)))
1593         typebits.Set(t, 0, vec)
1594
1595         nptr := types.PtrDataSize(t) / int64(types.PtrSize)
1596         for i := int64(0); i < nptr; i++ {
1597                 if vec.Get(int32(i)) {
1598                         ptrmask[i/8] |= 1 << (uint(i) % 8)
1599                 }
1600         }
1601 }
1602
1603 // dgcprog emits and returns the symbol containing a GC program for type t
1604 // along with the size of the data described by the program (in the range
1605 // [types.PtrDataSize(t), t.Width]).
1606 // In practice, the size is types.PtrDataSize(t) except for non-trivial arrays.
1607 // For non-trivial arrays, the program describes the full t.Width size.
1608 func dgcprog(t *types.Type, write bool) (*obj.LSym, int64) {
1609         types.CalcSize(t)
1610         if t.Size() == types.BADWIDTH {
1611                 base.Fatalf("dgcprog: %v badwidth", t)
1612         }
1613         lsym := TypeLinksymPrefix(".gcprog", t)
1614         var p gcProg
1615         p.init(lsym, write)
1616         p.emit(t, 0)
1617         offset := p.w.BitIndex() * int64(types.PtrSize)
1618         p.end()
1619         if ptrdata := types.PtrDataSize(t); offset < ptrdata || offset > t.Size() {
1620                 base.Fatalf("dgcprog: %v: offset=%d but ptrdata=%d size=%d", t, offset, ptrdata, t.Size())
1621         }
1622         return lsym, offset
1623 }
1624
1625 type gcProg struct {
1626         lsym   *obj.LSym
1627         symoff int
1628         w      gcprog.Writer
1629         write  bool
1630 }
1631
1632 func (p *gcProg) init(lsym *obj.LSym, write bool) {
1633         p.lsym = lsym
1634         p.write = write && !lsym.OnList()
1635         p.symoff = 4 // first 4 bytes hold program length
1636         if !write {
1637                 p.w.Init(func(byte) {})
1638                 return
1639         }
1640         p.w.Init(p.writeByte)
1641         if base.Debug.GCProg > 0 {
1642                 fmt.Fprintf(os.Stderr, "compile: start GCProg for %v\n", lsym)
1643                 p.w.Debug(os.Stderr)
1644         }
1645 }
1646
1647 func (p *gcProg) writeByte(x byte) {
1648         p.symoff = objw.Uint8(p.lsym, p.symoff, x)
1649 }
1650
1651 func (p *gcProg) end() {
1652         p.w.End()
1653         if !p.write {
1654                 return
1655         }
1656         objw.Uint32(p.lsym, 0, uint32(p.symoff-4))
1657         objw.Global(p.lsym, int32(p.symoff), obj.DUPOK|obj.RODATA|obj.LOCAL)
1658         p.lsym.Set(obj.AttrContentAddressable, true)
1659         if base.Debug.GCProg > 0 {
1660                 fmt.Fprintf(os.Stderr, "compile: end GCProg for %v\n", p.lsym)
1661         }
1662 }
1663
1664 func (p *gcProg) emit(t *types.Type, offset int64) {
1665         types.CalcSize(t)
1666         if !t.HasPointers() {
1667                 return
1668         }
1669         if t.Size() == int64(types.PtrSize) {
1670                 p.w.Ptr(offset / int64(types.PtrSize))
1671                 return
1672         }
1673         switch t.Kind() {
1674         default:
1675                 base.Fatalf("gcProg.emit: unexpected type %v", t)
1676
1677         case types.TSTRING:
1678                 p.w.Ptr(offset / int64(types.PtrSize))
1679
1680         case types.TINTER:
1681                 // Note: the first word isn't a pointer. See comment in typebits.Set
1682                 p.w.Ptr(offset/int64(types.PtrSize) + 1)
1683
1684         case types.TSLICE:
1685                 p.w.Ptr(offset / int64(types.PtrSize))
1686
1687         case types.TARRAY:
1688                 if t.NumElem() == 0 {
1689                         // should have been handled by haspointers check above
1690                         base.Fatalf("gcProg.emit: empty array")
1691                 }
1692
1693                 // Flatten array-of-array-of-array to just a big array by multiplying counts.
1694                 count := t.NumElem()
1695                 elem := t.Elem()
1696                 for elem.IsArray() {
1697                         count *= elem.NumElem()
1698                         elem = elem.Elem()
1699                 }
1700
1701                 if !p.w.ShouldRepeat(elem.Size()/int64(types.PtrSize), count) {
1702                         // Cheaper to just emit the bits.
1703                         for i := int64(0); i < count; i++ {
1704                                 p.emit(elem, offset+i*elem.Size())
1705                         }
1706                         return
1707                 }
1708                 p.emit(elem, offset)
1709                 p.w.ZeroUntil((offset + elem.Size()) / int64(types.PtrSize))
1710                 p.w.Repeat(elem.Size()/int64(types.PtrSize), count-1)
1711
1712         case types.TSTRUCT:
1713                 for _, t1 := range t.Fields().Slice() {
1714                         p.emit(t1.Type, offset+t1.Offset)
1715                 }
1716         }
1717 }
1718
1719 // ZeroAddr returns the address of a symbol with at least
1720 // size bytes of zeros.
1721 func ZeroAddr(size int64) ir.Node {
1722         if size >= 1<<31 {
1723                 base.Fatalf("map elem too big %d", size)
1724         }
1725         if ZeroSize < size {
1726                 ZeroSize = size
1727         }
1728         lsym := base.PkgLinksym("go.map", "zero", obj.ABI0)
1729         x := ir.NewLinksymExpr(base.Pos, lsym, types.Types[types.TUINT8])
1730         return typecheck.Expr(typecheck.NodAddr(x))
1731 }
1732
1733 func CollectPTabs() {
1734         if !base.Ctxt.Flag_dynlink || types.LocalPkg.Name != "main" {
1735                 return
1736         }
1737         for _, exportn := range typecheck.Target.Exports {
1738                 s := exportn.Sym()
1739                 nn := ir.AsNode(s.Def)
1740                 if nn == nil {
1741                         continue
1742                 }
1743                 if nn.Op() != ir.ONAME {
1744                         continue
1745                 }
1746                 n := nn.(*ir.Name)
1747                 if !types.IsExported(s.Name) {
1748                         continue
1749                 }
1750                 if s.Pkg.Name != "main" {
1751                         continue
1752                 }
1753                 ptabs = append(ptabs, n)
1754         }
1755 }
1756
1757 // NeedEmit reports whether typ is a type that we need to emit code
1758 // for (e.g., runtime type descriptors, method wrappers).
1759 func NeedEmit(typ *types.Type) bool {
1760         // TODO(mdempsky): Export data should keep track of which anonymous
1761         // and instantiated types were emitted, so at least downstream
1762         // packages can skip re-emitting them.
1763         //
1764         // Perhaps we can just generalize the linker-symbol indexing to
1765         // track the index of arbitrary types, not just defined types, and
1766         // use its presence to detect this. The same idea would work for
1767         // instantiated generic functions too.
1768
1769         switch sym := typ.Sym(); {
1770         case sym == nil:
1771                 // Anonymous type; possibly never seen before or ever again.
1772                 // Need to emit to be safe (however, see TODO above).
1773                 return true
1774
1775         case sym.Pkg == types.LocalPkg:
1776                 // Local defined type; our responsibility.
1777                 return true
1778
1779         case base.Ctxt.Pkgpath == "runtime" && (sym.Pkg == types.BuiltinPkg || sym.Pkg == types.UnsafePkg):
1780                 // Package runtime is responsible for including code for builtin
1781                 // types (predeclared and package unsafe).
1782                 return true
1783
1784         case typ.IsFullyInstantiated():
1785                 // Instantiated type; possibly instantiated with unique type arguments.
1786                 // Need to emit to be safe (however, see TODO above).
1787                 return true
1788
1789         case typ.HasShape():
1790                 // Shape type; need to emit even though it lives in the .shape package.
1791                 // TODO: make sure the linker deduplicates them (see dupok in writeType above).
1792                 return true
1793
1794         default:
1795                 // Should have been emitted by an imported package.
1796                 return false
1797         }
1798 }
1799
1800 // Generate a wrapper function to convert from
1801 // a receiver of type T to a receiver of type U.
1802 // That is,
1803 //
1804 //      func (t T) M() {
1805 //              ...
1806 //      }
1807 //
1808 // already exists; this function generates
1809 //
1810 //      func (u U) M() {
1811 //              u.M()
1812 //      }
1813 //
1814 // where the types T and U are such that u.M() is valid
1815 // and calls the T.M method.
1816 // The resulting function is for use in method tables.
1817 //
1818 //      rcvr - U
1819 //      method - M func (t T)(), a TFIELD type struct
1820 //
1821 // Also wraps methods on instantiated generic types for use in itab entries.
1822 // For an instantiated generic type G[int], we generate wrappers like:
1823 // G[int] pointer shaped:
1824 //
1825 //      func (x G[int]) f(arg) {
1826 //              .inst.G[int].f(dictionary, x, arg)
1827 //      }
1828 //
1829 // G[int] not pointer shaped:
1830 //
1831 //      func (x *G[int]) f(arg) {
1832 //              .inst.G[int].f(dictionary, *x, arg)
1833 //      }
1834 //
1835 // These wrappers are always fully stenciled.
1836 func methodWrapper(rcvr *types.Type, method *types.Field, forItab bool) *obj.LSym {
1837         orig := rcvr
1838         if forItab && !types.IsDirectIface(rcvr) {
1839                 rcvr = rcvr.PtrTo()
1840         }
1841
1842         generic := false
1843         // We don't need a dictionary if we are reaching a method (possibly via an
1844         // embedded field) which is an interface method.
1845         if !types.IsInterfaceMethod(method.Type) {
1846                 rcvr1 := deref(rcvr)
1847                 if len(rcvr1.RParams()) > 0 {
1848                         // If rcvr has rparams, remember method as generic, which
1849                         // means we need to add a dictionary to the wrapper.
1850                         generic = true
1851                         if rcvr.HasShape() {
1852                                 base.Fatalf("method on type instantiated with shapes, rcvr:%+v", rcvr)
1853                         }
1854                 }
1855         }
1856
1857         newnam := ir.MethodSym(rcvr, method.Sym)
1858         lsym := newnam.Linksym()
1859
1860         // Unified IR creates its own wrappers.
1861         if base.Debug.Unified != 0 {
1862                 return lsym
1863         }
1864
1865         if newnam.Siggen() {
1866                 return lsym
1867         }
1868         newnam.SetSiggen(true)
1869
1870         methodrcvr := method.Type.Recv().Type
1871         // For generic methods, we need to generate the wrapper even if the receiver
1872         // types are identical, because we want to add the dictionary.
1873         if !generic && types.Identical(rcvr, methodrcvr) {
1874                 return lsym
1875         }
1876
1877         if !NeedEmit(rcvr) || rcvr.IsPtr() && !NeedEmit(rcvr.Elem()) {
1878                 return lsym
1879         }
1880
1881         base.Pos = base.AutogeneratedPos
1882         typecheck.DeclContext = ir.PEXTERN
1883
1884         tfn := ir.NewFuncType(base.Pos,
1885                 ir.NewField(base.Pos, typecheck.Lookup(".this"), nil, rcvr),
1886                 typecheck.NewFuncParams(method.Type.Params(), true),
1887                 typecheck.NewFuncParams(method.Type.Results(), false))
1888
1889         // TODO(austin): SelectorExpr may have created one or more
1890         // ir.Names for these already with a nil Func field. We should
1891         // consolidate these and always attach a Func to the Name.
1892         fn := typecheck.DeclFunc(newnam, tfn)
1893         fn.SetDupok(true)
1894
1895         nthis := ir.AsNode(tfn.Type().Recv().Nname)
1896
1897         indirect := rcvr.IsPtr() && rcvr.Elem() == methodrcvr
1898
1899         // generate nil pointer check for better error
1900         if indirect {
1901                 // generating wrapper from *T to T.
1902                 n := ir.NewIfStmt(base.Pos, nil, nil, nil)
1903                 n.Cond = ir.NewBinaryExpr(base.Pos, ir.OEQ, nthis, typecheck.NodNil())
1904                 call := ir.NewCallExpr(base.Pos, ir.OCALL, typecheck.LookupRuntime("panicwrap"), nil)
1905                 n.Body = []ir.Node{call}
1906                 fn.Body.Append(n)
1907         }
1908
1909         dot := typecheck.AddImplicitDots(ir.NewSelectorExpr(base.Pos, ir.OXDOT, nthis, method.Sym))
1910         // generate call
1911         // It's not possible to use a tail call when dynamic linking on ppc64le. The
1912         // bad scenario is when a local call is made to the wrapper: the wrapper will
1913         // call the implementation, which might be in a different module and so set
1914         // the TOC to the appropriate value for that module. But if it returns
1915         // directly to the wrapper's caller, nothing will reset it to the correct
1916         // value for that function.
1917         if !base.Flag.Cfg.Instrumenting && rcvr.IsPtr() && methodrcvr.IsPtr() && method.Embedded != 0 && !types.IsInterfaceMethod(method.Type) && !(base.Ctxt.Arch.Name == "ppc64le" && base.Ctxt.Flag_dynlink) && !generic {
1918                 call := ir.NewCallExpr(base.Pos, ir.OCALL, dot, nil)
1919                 call.Args = ir.ParamNames(tfn.Type())
1920                 call.IsDDD = tfn.Type().IsVariadic()
1921                 fn.Body.Append(ir.NewTailCallStmt(base.Pos, call))
1922         } else {
1923                 fn.SetWrapper(true) // ignore frame for panic+recover matching
1924                 var call *ir.CallExpr
1925
1926                 if generic && dot.X != nthis {
1927                         // If there is embedding involved, then we should do the
1928                         // normal non-generic embedding wrapper below, which calls
1929                         // the wrapper for the real receiver type using dot as an
1930                         // argument. There is no need for generic processing (adding
1931                         // a dictionary) for this wrapper.
1932                         generic = false
1933                 }
1934
1935                 if generic {
1936                         targs := deref(rcvr).RParams()
1937                         // The wrapper for an auto-generated pointer/non-pointer
1938                         // receiver method should share the same dictionary as the
1939                         // corresponding original (user-written) method.
1940                         baseOrig := orig
1941                         if baseOrig.IsPtr() && !methodrcvr.IsPtr() {
1942                                 baseOrig = baseOrig.Elem()
1943                         } else if !baseOrig.IsPtr() && methodrcvr.IsPtr() {
1944                                 baseOrig = types.NewPtr(baseOrig)
1945                         }
1946                         args := []ir.Node{getDictionary(ir.MethodSym(baseOrig, method.Sym), targs)}
1947                         if indirect {
1948                                 args = append(args, ir.NewStarExpr(base.Pos, dot.X))
1949                         } else if methodrcvr.IsPtr() && methodrcvr.Elem() == dot.X.Type() {
1950                                 // Case where method call is via a non-pointer
1951                                 // embedded field with a pointer method.
1952                                 args = append(args, typecheck.NodAddrAt(base.Pos, dot.X))
1953                         } else {
1954                                 args = append(args, dot.X)
1955                         }
1956                         args = append(args, ir.ParamNames(tfn.Type())...)
1957
1958                         // Target method uses shaped names.
1959                         targs2 := make([]*types.Type, len(targs))
1960                         origRParams := deref(orig).OrigType().RParams()
1961                         for i, t := range targs {
1962                                 targs2[i] = typecheck.Shapify(t, i, origRParams[i])
1963                         }
1964                         targs = targs2
1965
1966                         sym := typecheck.MakeFuncInstSym(ir.MethodSym(methodrcvr, method.Sym), targs, false, true)
1967                         if sym.Def == nil {
1968                                 // Currently we make sure that we have all the
1969                                 // instantiations we need by generating them all in
1970                                 // ../noder/stencil.go:instantiateMethods
1971                                 // Extra instantiations because of an inlined function
1972                                 // should have been exported, and so available via
1973                                 // Resolve.
1974                                 in := typecheck.Resolve(ir.NewIdent(src.NoXPos, sym))
1975                                 if in.Op() == ir.ONONAME {
1976                                         base.Fatalf("instantiation %s not found", sym.Name)
1977                                 }
1978                                 sym = in.Sym()
1979                         }
1980                         target := ir.AsNode(sym.Def)
1981                         call = ir.NewCallExpr(base.Pos, ir.OCALL, target, args)
1982                         // Fill-in the generic method node that was not filled in
1983                         // in instantiateMethod.
1984                         method.Nname = fn.Nname
1985                 } else {
1986                         call = ir.NewCallExpr(base.Pos, ir.OCALL, dot, nil)
1987                         call.Args = ir.ParamNames(tfn.Type())
1988                 }
1989                 call.IsDDD = tfn.Type().IsVariadic()
1990                 if method.Type.NumResults() > 0 {
1991                         ret := ir.NewReturnStmt(base.Pos, nil)
1992                         ret.Results = []ir.Node{call}
1993                         fn.Body.Append(ret)
1994                 } else {
1995                         fn.Body.Append(call)
1996                 }
1997         }
1998
1999         typecheck.FinishFuncBody()
2000         if base.Debug.DclStack != 0 {
2001                 types.CheckDclstack()
2002         }
2003
2004         typecheck.Func(fn)
2005         ir.CurFunc = fn
2006         typecheck.Stmts(fn.Body)
2007
2008         if AfterGlobalEscapeAnalysis {
2009                 inline.InlineCalls(fn)
2010                 escape.Batch([]*ir.Func{fn}, false)
2011         }
2012
2013         ir.CurFunc = nil
2014         typecheck.Target.Decls = append(typecheck.Target.Decls, fn)
2015
2016         return lsym
2017 }
2018
2019 // AfterGlobalEscapeAnalysis tracks whether package gc has already
2020 // performed the main, global escape analysis pass. If so,
2021 // methodWrapper takes responsibility for escape analyzing any
2022 // generated wrappers.
2023 var AfterGlobalEscapeAnalysis bool
2024
2025 var ZeroSize int64
2026
2027 // MarkTypeUsedInInterface marks that type t is converted to an interface.
2028 // This information is used in the linker in dead method elimination.
2029 func MarkTypeUsedInInterface(t *types.Type, from *obj.LSym) {
2030         if t.HasShape() {
2031                 // Shape types shouldn't be put in interfaces, so we shouldn't ever get here.
2032                 base.Fatalf("shape types have no methods %+v", t)
2033         }
2034         tsym := TypeLinksym(t)
2035         // Emit a marker relocation. The linker will know the type is converted
2036         // to an interface if "from" is reachable.
2037         r := obj.Addrel(from)
2038         r.Sym = tsym
2039         r.Type = objabi.R_USEIFACE
2040 }
2041
2042 // MarkUsedIfaceMethod marks that an interface method is used in the current
2043 // function. n is OCALLINTER node.
2044 func MarkUsedIfaceMethod(n *ir.CallExpr) {
2045         // skip unnamed functions (func _())
2046         if ir.CurFunc.LSym == nil {
2047                 return
2048         }
2049         dot := n.X.(*ir.SelectorExpr)
2050         ityp := dot.X.Type()
2051         if ityp.HasShape() {
2052                 // Here we're calling a method on a generic interface. Something like:
2053                 //
2054                 // type I[T any] interface { foo() T }
2055                 // func f[T any](x I[T]) {
2056                 //     ... = x.foo()
2057                 // }
2058                 // f[int](...)
2059                 // f[string](...)
2060                 //
2061                 // In this case, in f we're calling foo on a generic interface.
2062                 // Which method could that be? Normally we could match the method
2063                 // both by name and by type. But in this case we don't really know
2064                 // the type of the method we're calling. It could be func()int
2065                 // or func()string. So we match on just the function name, instead
2066                 // of both the name and the type used for the non-generic case below.
2067                 // TODO: instantiations at least know the shape of the instantiated
2068                 // type, and the linker could do more complicated matching using
2069                 // some sort of fuzzy shape matching. For now, only use the name
2070                 // of the method for matching.
2071                 r := obj.Addrel(ir.CurFunc.LSym)
2072                 // We use a separate symbol just to tell the linker the method name.
2073                 // (The symbol itself is not needed in the final binary.)
2074                 r.Sym = staticdata.StringSym(src.NoXPos, dot.Sel.Name)
2075                 r.Type = objabi.R_USEGENERICIFACEMETHOD
2076                 return
2077         }
2078
2079         tsym := TypeLinksym(ityp)
2080         r := obj.Addrel(ir.CurFunc.LSym)
2081         r.Sym = tsym
2082         // dot.Offset() is the method index * PtrSize (the offset of code pointer
2083         // in itab).
2084         midx := dot.Offset() / int64(types.PtrSize)
2085         r.Add = InterfaceMethodOffset(ityp, midx)
2086         r.Type = objabi.R_USEIFACEMETHOD
2087 }
2088
2089 // getDictionary returns the dictionary for the given named generic function
2090 // or method, with the given type arguments.
2091 func getDictionary(gf *types.Sym, targs []*types.Type) ir.Node {
2092         if len(targs) == 0 {
2093                 base.Fatalf("%s should have type arguments", gf.Name)
2094         }
2095         for _, t := range targs {
2096                 if t.HasShape() {
2097                         base.Fatalf("dictionary for %s should only use concrete types: %+v", gf.Name, t)
2098                 }
2099         }
2100
2101         sym := typecheck.MakeDictSym(gf, targs, true)
2102
2103         // Dictionary should already have been generated by instantiateMethods().
2104         // Extra dictionaries needed because of an inlined function should have been
2105         // exported, and so available via Resolve.
2106         if lsym := sym.Linksym(); len(lsym.P) == 0 {
2107                 in := typecheck.Resolve(ir.NewIdent(src.NoXPos, sym))
2108                 if in.Op() == ir.ONONAME {
2109                         base.Fatalf("Dictionary should have already been generated: %s.%s", sym.Pkg.Path, sym.Name)
2110                 }
2111                 sym = in.Sym()
2112         }
2113
2114         // Make (or reuse) a node referencing the dictionary symbol.
2115         var n *ir.Name
2116         if sym.Def != nil {
2117                 n = sym.Def.(*ir.Name)
2118         } else {
2119                 n = typecheck.NewName(sym)
2120                 n.SetType(types.Types[types.TUINTPTR]) // should probably be [...]uintptr, but doesn't really matter
2121                 n.SetTypecheck(1)
2122                 n.Class = ir.PEXTERN
2123                 sym.Def = n
2124         }
2125
2126         // Return the address of the dictionary.
2127         np := typecheck.NodAddr(n)
2128         // Note: treat dictionary pointers as uintptrs, so they aren't pointers
2129         // with respect to GC. That saves on stack scanning work, write barriers, etc.
2130         // We can get away with it because dictionaries are global variables.
2131         np.SetType(types.Types[types.TUINTPTR])
2132         np.SetTypecheck(1)
2133         return np
2134 }
2135
2136 func deref(t *types.Type) *types.Type {
2137         if t.IsPtr() {
2138                 return t.Elem()
2139         }
2140         return t
2141 }