src/cmd/compile/internal/gc/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 gc
   6
   7 import (
   8         "cmd/compile/internal/types"
   9         "cmd/internal/gcprog"
  10         "cmd/internal/obj"
  11         "cmd/internal/objabi"
  12         "cmd/internal/src"
  13         "fmt"
  14         "os"
  15         "sort"
  16         "strings"
  17         "sync"
  18 )
  19
  20 type itabEntry struct {
  21         t, itype *types.Type
  22         lsym     *obj.LSym // symbol of the itab itself
  23
  24         // symbols of each method in
  25         // the itab, sorted by byte offset;
  26         // filled in by peekitabs
  27         entries []*obj.LSym
  28 }
  29
  30 type ptabEntry struct {
  31         s *types.Sym
  32         t *types.Type
  33 }
  34
  35 // runtime interface and reflection data structures
  36 var (
  37         signatmu    sync.Mutex // protects signatset and signatslice
  38         signatset   = make(map[*types.Type]struct{})
  39         signatslice []*types.Type
  40
  41         itabs []itabEntry
  42         ptabs []ptabEntry
  43 )
  44
  45 type Sig struct {
  46         name  *types.Sym
  47         isym  *types.Sym
  48         tsym  *types.Sym
  49         type_ *types.Type
  50         mtype *types.Type
  51 }
  52
  53 // Builds a type representing a Bucket structure for
  54 // the given map type. This type is not visible to users -
  55 // we include only enough information to generate a correct GC
  56 // program for it.
  57 // Make sure this stays in sync with runtime/map.go.
  58 const (
  59         BUCKETSIZE  = 8
  60         MAXKEYSIZE  = 128
  61         MAXELEMSIZE = 128
  62 )
  63
  64 func structfieldSize() int { return 3 * Widthptr }       // Sizeof(runtime.structfield{})
  65 func imethodSize() int     { return 4 + 4 }              // Sizeof(runtime.imethod{})
  66 func commonSize() int      { return 4*Widthptr + 8 + 8 } // Sizeof(runtime._type{})
  67
  68 func uncommonSize(t *types.Type) int { // Sizeof(runtime.uncommontype{})
  69         if t.Sym == nil && len(methods(t)) == 0 {
  70                 return 0
  71         }
  72         return 4 + 2 + 2 + 4 + 4
  73 }
  74
  75 func makefield(name string, t *types.Type) *types.Field {
  76         f := types.NewField()
  77         f.Type = t
  78         f.Sym = (*types.Pkg)(nil).Lookup(name)
  79         return f
  80 }
  81
  82 // bmap makes the map bucket type given the type of the map.
  83 func bmap(t *types.Type) *types.Type {
  84         if t.MapType().Bucket != nil {
  85                 return t.MapType().Bucket
  86         }
  87
  88         bucket := types.New(TSTRUCT)
  89         keytype := t.Key()
  90         elemtype := t.Elem()
  91         dowidth(keytype)
  92         dowidth(elemtype)
  93         if keytype.Width > MAXKEYSIZE {
  94                 keytype = types.NewPtr(keytype)
  95         }
  96         if elemtype.Width > MAXELEMSIZE {
  97                 elemtype = types.NewPtr(elemtype)
  98         }
  99
 100         field := make([]*types.Field, 0, 5)
 101
 102         // The first field is: uint8 topbits[BUCKETSIZE].
 103         arr := types.NewArray(types.Types[TUINT8], BUCKETSIZE)
 104         field = append(field, makefield("topbits", arr))
 105
 106         arr = types.NewArray(keytype, BUCKETSIZE)
 107         arr.SetNoalg(true)
 108         keys := makefield("keys", arr)
 109         field = append(field, keys)
 110
 111         arr = types.NewArray(elemtype, BUCKETSIZE)
 112         arr.SetNoalg(true)
 113         elems := makefield("elems", arr)
 114         field = append(field, elems)
 115
 116         // If keys and elems have no pointers, the map implementation
 117         // can keep a list of overflow pointers on the side so that
 118         // buckets can be marked as having no pointers.
 119         // Arrange for the bucket to have no pointers by changing
 120         // the type of the overflow field to uintptr in this case.
 121         // See comment on hmap.overflow in runtime/map.go.
 122         otyp := types.NewPtr(bucket)
 123         if !elemtype.HasPointers() && !keytype.HasPointers() {
 124                 otyp = types.Types[TUINTPTR]
 125         }
 126         overflow := makefield("overflow", otyp)
 127         field = append(field, overflow)
 128
 129         // link up fields
 130         bucket.SetNoalg(true)
 131         bucket.SetFields(field[:])
 132         dowidth(bucket)
 133
 134         // Check invariants that map code depends on.
 135         if !IsComparable(t.Key()) {
 136                 Fatalf("unsupported map key type for %v", t)
 137         }
 138         if BUCKETSIZE < 8 {
 139                 Fatalf("bucket size too small for proper alignment")
 140         }
 141         if keytype.Align > BUCKETSIZE {
 142                 Fatalf("key align too big for %v", t)
 143         }
 144         if elemtype.Align > BUCKETSIZE {
 145                 Fatalf("elem align too big for %v", t)
 146         }
 147         if keytype.Width > MAXKEYSIZE {
 148                 Fatalf("key size to large for %v", t)
 149         }
 150         if elemtype.Width > MAXELEMSIZE {
 151                 Fatalf("elem size to large for %v", t)
 152         }
 153         if t.Key().Width > MAXKEYSIZE && !keytype.IsPtr() {
 154                 Fatalf("key indirect incorrect for %v", t)
 155         }
 156         if t.Elem().Width > MAXELEMSIZE && !elemtype.IsPtr() {
 157                 Fatalf("elem indirect incorrect for %v", t)
 158         }
 159         if keytype.Width%int64(keytype.Align) != 0 {
 160                 Fatalf("key size not a multiple of key align for %v", t)
 161         }
 162         if elemtype.Width%int64(elemtype.Align) != 0 {
 163                 Fatalf("elem size not a multiple of elem align for %v", t)
 164         }
 165         if bucket.Align%keytype.Align != 0 {
 166                 Fatalf("bucket align not multiple of key align %v", t)
 167         }
 168         if bucket.Align%elemtype.Align != 0 {
 169                 Fatalf("bucket align not multiple of elem align %v", t)
 170         }
 171         if keys.Offset%int64(keytype.Align) != 0 {
 172                 Fatalf("bad alignment of keys in bmap for %v", t)
 173         }
 174         if elems.Offset%int64(elemtype.Align) != 0 {
 175                 Fatalf("bad alignment of elems in bmap for %v", t)
 176         }
 177
 178         // Double-check that overflow field is final memory in struct,
 179         // with no padding at end.
 180         if overflow.Offset != bucket.Width-int64(Widthptr) {
 181                 Fatalf("bad offset of overflow in bmap for %v", t)
 182         }
 183
 184         t.MapType().Bucket = bucket
 185
 186         bucket.StructType().Map = t
 187         return bucket
 188 }
 189
 190 // hmap builds a type representing a Hmap structure for the given map type.
 191 // Make sure this stays in sync with runtime/map.go.
 192 func hmap(t *types.Type) *types.Type {
 193         if t.MapType().Hmap != nil {
 194                 return t.MapType().Hmap
 195         }
 196
 197         bmap := bmap(t)
 198
 199         // build a struct:
 200         // type hmap struct {
 201         //    count      int
 202         //    flags      uint8
 203         //    B          uint8
 204         //    noverflow  uint16
 205         //    hash0      uint32
 206         //    buckets    *bmap
 207         //    oldbuckets *bmap
 208         //    nevacuate  uintptr
 209         //    extra      unsafe.Pointer // *mapextra
 210         // }
 211         // must match runtime/map.go:hmap.
 212         fields := []*types.Field{
 213                 makefield("count", types.Types[TINT]),
 214                 makefield("flags", types.Types[TUINT8]),
 215                 makefield("B", types.Types[TUINT8]),
 216                 makefield("noverflow", types.Types[TUINT16]),
 217                 makefield("hash0", types.Types[TUINT32]), // Used in walk.go for OMAKEMAP.
 218                 makefield("buckets", types.NewPtr(bmap)), // Used in walk.go for OMAKEMAP.
 219                 makefield("oldbuckets", types.NewPtr(bmap)),
 220                 makefield("nevacuate", types.Types[TUINTPTR]),
 221                 makefield("extra", types.Types[TUNSAFEPTR]),
 222         }
 223
 224         hmap := types.New(TSTRUCT)
 225         hmap.SetNoalg(true)
 226         hmap.SetFields(fields)
 227         dowidth(hmap)
 228
 229         // The size of hmap should be 48 bytes on 64 bit
 230         // and 28 bytes on 32 bit platforms.
 231         if size := int64(8 + 5*Widthptr); hmap.Width != size {
 232                 Fatalf("hmap size not correct: got %d, want %d", hmap.Width, size)
 233         }
 234
 235         t.MapType().Hmap = hmap
 236         hmap.StructType().Map = t
 237         return hmap
 238 }
 239
 240 // hiter builds a type representing an Hiter structure for the given map type.
 241 // Make sure this stays in sync with runtime/map.go.
 242 func hiter(t *types.Type) *types.Type {
 243         if t.MapType().Hiter != nil {
 244                 return t.MapType().Hiter
 245         }
 246
 247         hmap := hmap(t)
 248         bmap := bmap(t)
 249
 250         // build a struct:
 251         // type hiter struct {
 252         //    key         *Key
 253         //    elem        *Elem
 254         //    t           unsafe.Pointer // *MapType
 255         //    h           *hmap
 256         //    buckets     *bmap
 257         //    bptr        *bmap
 258         //    overflow    unsafe.Pointer // *[]*bmap
 259         //    oldoverflow unsafe.Pointer // *[]*bmap
 260         //    startBucket uintptr
 261         //    offset      uint8
 262         //    wrapped     bool
 263         //    B           uint8
 264         //    i           uint8
 265         //    bucket      uintptr
 266         //    checkBucket uintptr
 267         // }
 268         // must match runtime/map.go:hiter.
 269         fields := []*types.Field{
 270                 makefield("key", types.NewPtr(t.Key())),   // Used in range.go for TMAP.
 271                 makefield("elem", types.NewPtr(t.Elem())), // Used in range.go for TMAP.
 272                 makefield("t", types.Types[TUNSAFEPTR]),
 273                 makefield("h", types.NewPtr(hmap)),
 274                 makefield("buckets", types.NewPtr(bmap)),
 275                 makefield("bptr", types.NewPtr(bmap)),
 276                 makefield("overflow", types.Types[TUNSAFEPTR]),
 277                 makefield("oldoverflow", types.Types[TUNSAFEPTR]),
 278                 makefield("startBucket", types.Types[TUINTPTR]),
 279                 makefield("offset", types.Types[TUINT8]),
 280                 makefield("wrapped", types.Types[TBOOL]),
 281                 makefield("B", types.Types[TUINT8]),
 282                 makefield("i", types.Types[TUINT8]),
 283                 makefield("bucket", types.Types[TUINTPTR]),
 284                 makefield("checkBucket", types.Types[TUINTPTR]),
 285         }
 286
 287         // build iterator struct holding the above fields
 288         hiter := types.New(TSTRUCT)
 289         hiter.SetNoalg(true)
 290         hiter.SetFields(fields)
 291         dowidth(hiter)
 292         if hiter.Width != int64(12*Widthptr) {
 293                 Fatalf("hash_iter size not correct %d %d", hiter.Width, 12*Widthptr)
 294         }
 295         t.MapType().Hiter = hiter
 296         hiter.StructType().Map = t
 297         return hiter
 298 }
 299
 300 // deferstruct makes a runtime._defer structure, with additional space for
 301 // stksize bytes of args.
 302 func deferstruct(stksize int64) *types.Type {
 303         makefield := func(name string, typ *types.Type) *types.Field {
 304                 f := types.NewField()
 305                 f.Type = typ
 306                 // Unlike the global makefield function, this one needs to set Pkg
 307                 // because these types might be compared (in SSA CSE sorting).
 308                 // TODO: unify this makefield and the global one above.
 309                 f.Sym = &types.Sym{Name: name, Pkg: localpkg}
 310                 return f
 311         }
 312         argtype := types.NewArray(types.Types[TUINT8], stksize)
 313         argtype.Width = stksize
 314         argtype.Align = 1
 315         // These fields must match the ones in runtime/runtime2.go:_defer and
 316         // cmd/compile/internal/gc/ssa.go:(*state).call.
 317         fields := []*types.Field{
 318                 makefield("siz", types.Types[TUINT32]),
 319                 makefield("started", types.Types[TBOOL]),
 320                 makefield("heap", types.Types[TBOOL]),
 321                 makefield("openDefer", types.Types[TBOOL]),
 322                 makefield("sp", types.Types[TUINTPTR]),
 323                 makefield("pc", types.Types[TUINTPTR]),
 324                 // Note: the types here don't really matter. Defer structures
 325                 // are always scanned explicitly during stack copying and GC,
 326                 // so we make them uintptr type even though they are real pointers.
 327                 makefield("fn", types.Types[TUINTPTR]),
 328                 makefield("_panic", types.Types[TUINTPTR]),
 329                 makefield("link", types.Types[TUINTPTR]),
 330                 makefield("framepc", types.Types[TUINTPTR]),
 331                 makefield("varp", types.Types[TUINTPTR]),
 332                 makefield("fd", types.Types[TUINTPTR]),
 333                 makefield("args", argtype),
 334         }
 335
 336         // build struct holding the above fields
 337         s := types.New(TSTRUCT)
 338         s.SetNoalg(true)
 339         s.SetFields(fields)
 340         s.Width = widstruct(s, s, 0, 1)
 341         s.Align = uint8(Widthptr)
 342         return s
 343 }
 344
 345 // f is method type, with receiver.
 346 // return function type, receiver as first argument (or not).
 347 func methodfunc(f *types.Type, receiver *types.Type) *types.Type {
 348         inLen := f.Params().Fields().Len()
 349         if receiver != nil {
 350                 inLen++
 351         }
 352         in := make([]*Node, 0, inLen)
 353
 354         if receiver != nil {
 355                 d := anonfield(receiver)
 356                 in = append(in, d)
 357         }
 358
 359         for _, t := range f.Params().Fields().Slice() {
 360                 d := anonfield(t.Type)
 361                 d.SetIsDDD(t.IsDDD())
 362                 in = append(in, d)
 363         }
 364
 365         outLen := f.Results().Fields().Len()
 366         out := make([]*Node, 0, outLen)
 367         for _, t := range f.Results().Fields().Slice() {
 368                 d := anonfield(t.Type)
 369                 out = append(out, d)
 370         }
 371
 372         t := functype(nil, in, out)
 373         if f.Nname() != nil {
 374                 // Link to name of original method function.
 375                 t.SetNname(f.Nname())
 376         }
 377
 378         return t
 379 }
 380
 381 // methods returns the methods of the non-interface type t, sorted by name.
 382 // Generates stub functions as needed.
 383 func methods(t *types.Type) []*Sig {
 384         // method type
 385         mt := methtype(t)
 386
 387         if mt == nil {
 388                 return nil
 389         }
 390         expandmeth(mt)
 391
 392         // type stored in interface word
 393         it := t
 394
 395         if !isdirectiface(it) {
 396                 it = types.NewPtr(t)
 397         }
 398
 399         // make list of methods for t,
 400         // generating code if necessary.
 401         var ms []*Sig
 402         for _, f := range mt.AllMethods().Slice() {
 403                 if !f.IsMethod() {
 404                         Fatalf("non-method on %v method %v %v\n", mt, f.Sym, f)
 405                 }
 406                 if f.Type.Recv() == nil {
 407                         Fatalf("receiver with no type on %v method %v %v\n", mt, f.Sym, f)
 408                 }
 409                 if f.Nointerface() {
 410                         continue
 411                 }
 412
 413                 method := f.Sym
 414                 if method == nil {
 415                         break
 416                 }
 417
 418                 // get receiver type for this particular method.
 419                 // if pointer receiver but non-pointer t and
 420                 // this is not an embedded pointer inside a struct,
 421                 // method does not apply.
 422                 if !isMethodApplicable(t, f) {
 423                         continue
 424                 }
 425
 426                 sig := &Sig{
 427                         name:  method,
 428                         isym:  methodSym(it, method),
 429                         tsym:  methodSym(t, method),
 430                         type_: methodfunc(f.Type, t),
 431                         mtype: methodfunc(f.Type, nil),
 432                 }
 433                 ms = append(ms, sig)
 434
 435                 this := f.Type.Recv().Type
 436
 437                 if !sig.isym.Siggen() {
 438                         sig.isym.SetSiggen(true)
 439                         if !types.Identical(this, it) {
 440                                 genwrapper(it, f, sig.isym)
 441                         }
 442                 }
 443
 444                 if !sig.tsym.Siggen() {
 445                         sig.tsym.SetSiggen(true)
 446                         if !types.Identical(this, t) {
 447                                 genwrapper(t, f, sig.tsym)
 448                         }
 449                 }
 450         }
 451
 452         return ms
 453 }
 454
 455 // imethods returns the methods of the interface type t, sorted by name.
 456 func imethods(t *types.Type) []*Sig {
 457         var methods []*Sig
 458         for _, f := range t.Fields().Slice() {
 459                 if f.Type.Etype != TFUNC || f.Sym == nil {
 460                         continue
 461                 }
 462                 if f.Sym.IsBlank() {
 463                         Fatalf("unexpected blank symbol in interface method set")
 464                 }
 465                 if n := len(methods); n > 0 {
 466                         last := methods[n-1]
 467                         if !last.name.Less(f.Sym) {
 468                                 Fatalf("sigcmp vs sortinter %v %v", last.name, f.Sym)
 469                         }
 470                 }
 471
 472                 sig := &Sig{
 473                         name:  f.Sym,
 474                         mtype: f.Type,
 475                         type_: methodfunc(f.Type, nil),
 476                 }
 477                 methods = append(methods, sig)
 478
 479                 // NOTE(rsc): Perhaps an oversight that
 480                 // IfaceType.Method is not in the reflect data.
 481                 // Generate the method body, so that compiled
 482                 // code can refer to it.
 483                 isym := methodSym(t, f.Sym)
 484                 if !isym.Siggen() {
 485                         isym.SetSiggen(true)
 486                         genwrapper(t, f, isym)
 487                 }
 488         }
 489
 490         return methods
 491 }
 492
 493 func dimportpath(p *types.Pkg) {
 494         if p.Pathsym != nil {
 495                 return
 496         }
 497
 498         // If we are compiling the runtime package, there are two runtime packages around
 499         // -- localpkg and Runtimepkg. We don't want to produce import path symbols for
 500         // both of them, so just produce one for localpkg.
 501         if myimportpath == "runtime" && p == Runtimepkg {
 502                 return
 503         }
 504
 505         str := p.Path
 506         if p == localpkg {
 507                 // Note: myimportpath != "", or else dgopkgpath won't call dimportpath.
 508                 str = myimportpath
 509         }
 510
 511         s := Ctxt.Lookup("type..importpath." + p.Prefix + ".")
 512         ot := dnameData(s, 0, str, "", nil, false)
 513         ggloblsym(s, int32(ot), obj.DUPOK|obj.RODATA)
 514         s.Set(obj.AttrContentAddressable, true)
 515         p.Pathsym = s
 516 }
 517
 518 func dgopkgpath(s *obj.LSym, ot int, pkg *types.Pkg) int {
 519         if pkg == nil {
 520                 return duintptr(s, ot, 0)
 521         }
 522
 523         if pkg == localpkg && myimportpath == "" {
 524                 // If we don't know the full import path of the package being compiled
 525                 // (i.e. -p was not passed on the compiler command line), emit a reference to
 526                 // type..importpath.""., which the linker will rewrite using the correct import path.
 527                 // Every package that imports this one directly defines the symbol.
 528                 // See also https://groups.google.com/forum/#!topic/golang-dev/myb9s53HxGQ.
 529                 ns := Ctxt.Lookup(`type..importpath."".`)
 530                 return dsymptr(s, ot, ns, 0)
 531         }
 532
 533         dimportpath(pkg)
 534         return dsymptr(s, ot, pkg.Pathsym, 0)
 535 }
 536
 537 // dgopkgpathOff writes an offset relocation in s at offset ot to the pkg path symbol.
 538 func dgopkgpathOff(s *obj.LSym, ot int, pkg *types.Pkg) int {
 539         if pkg == nil {
 540                 return duint32(s, ot, 0)
 541         }
 542         if pkg == localpkg && myimportpath == "" {
 543                 // If we don't know the full import path of the package being compiled
 544                 // (i.e. -p was not passed on the compiler command line), emit a reference to
 545                 // type..importpath.""., which the linker will rewrite using the correct import path.
 546                 // Every package that imports this one directly defines the symbol.
 547                 // See also https://groups.google.com/forum/#!topic/golang-dev/myb9s53HxGQ.
 548                 ns := Ctxt.Lookup(`type..importpath."".`)
 549                 return dsymptrOff(s, ot, ns)
 550         }
 551
 552         dimportpath(pkg)
 553         return dsymptrOff(s, ot, pkg.Pathsym)
 554 }
 555
 556 // dnameField dumps a reflect.name for a struct field.
 557 func dnameField(lsym *obj.LSym, ot int, spkg *types.Pkg, ft *types.Field) int {
 558         if !types.IsExported(ft.Sym.Name) && ft.Sym.Pkg != spkg {
 559                 Fatalf("package mismatch for %v", ft.Sym)
 560         }
 561         nsym := dname(ft.Sym.Name, ft.Note, nil, types.IsExported(ft.Sym.Name))
 562         return dsymptr(lsym, ot, nsym, 0)
 563 }
 564
 565 // dnameData writes the contents of a reflect.name into s at offset ot.
 566 func dnameData(s *obj.LSym, ot int, name, tag string, pkg *types.Pkg, exported bool) int {
 567         if len(name) > 1<<16-1 {
 568                 Fatalf("name too long: %s", name)
 569         }
 570         if len(tag) > 1<<16-1 {
 571                 Fatalf("tag too long: %s", tag)
 572         }
 573
 574         // Encode name and tag. See reflect/type.go for details.
 575         var bits byte
 576         l := 1 + 2 + len(name)
 577         if exported {
 578                 bits |= 1 << 0
 579         }
 580         if len(tag) > 0 {
 581                 l += 2 + len(tag)
 582                 bits |= 1 << 1
 583         }
 584         if pkg != nil {
 585                 bits |= 1 << 2
 586         }
 587         b := make([]byte, l)
 588         b[0] = bits
 589         b[1] = uint8(len(name) >> 8)
 590         b[2] = uint8(len(name))
 591         copy(b[3:], name)
 592         if len(tag) > 0 {
 593                 tb := b[3+len(name):]
 594                 tb[0] = uint8(len(tag) >> 8)
 595                 tb[1] = uint8(len(tag))
 596                 copy(tb[2:], tag)
 597         }
 598
 599         ot = int(s.WriteBytes(Ctxt, int64(ot), b))
 600
 601         if pkg != nil {
 602                 ot = dgopkgpathOff(s, ot, pkg)
 603         }
 604
 605         return ot
 606 }
 607
 608 var dnameCount int
 609
 610 // dname creates a reflect.name for a struct field or method.
 611 func dname(name, tag string, pkg *types.Pkg, exported bool) *obj.LSym {
 612         // Write out data as "type.." to signal two things to the
 613         // linker, first that when dynamically linking, the symbol
 614         // should be moved to a relro section, and second that the
 615         // contents should not be decoded as a type.
 616         sname := "type..namedata."
 617         if pkg == nil {
 618                 // In the common case, share data with other packages.
 619                 if name == "" {
 620                         if exported {
 621                                 sname += "-noname-exported." + tag
 622                         } else {
 623                                 sname += "-noname-unexported." + tag
 624                         }
 625                 } else {
 626                         if exported {
 627                                 sname += name + "." + tag
 628                         } else {
 629                                 sname += name + "-" + tag
 630                         }
 631                 }
 632         } else {
 633                 sname = fmt.Sprintf(`%s"".%d`, sname, dnameCount)
 634                 dnameCount++
 635         }
 636         s := Ctxt.Lookup(sname)
 637         if len(s.P) > 0 {
 638                 return s
 639         }
 640         ot := dnameData(s, 0, name, tag, pkg, exported)
 641         ggloblsym(s, int32(ot), obj.DUPOK|obj.RODATA)
 642         s.Set(obj.AttrContentAddressable, true)
 643         return s
 644 }
 645
 646 // dextratype dumps the fields of a runtime.uncommontype.
 647 // dataAdd is the offset in bytes after the header where the
 648 // backing array of the []method field is written (by dextratypeData).
 649 func dextratype(lsym *obj.LSym, ot int, t *types.Type, dataAdd int) int {
 650         m := methods(t)
 651         if t.Sym == nil && len(m) == 0 {
 652                 return ot
 653         }
 654         noff := int(Rnd(int64(ot), int64(Widthptr)))
 655         if noff != ot {
 656                 Fatalf("unexpected alignment in dextratype for %v", t)
 657         }
 658
 659         for _, a := range m {
 660                 dtypesym(a.type_)
 661         }
 662
 663         ot = dgopkgpathOff(lsym, ot, typePkg(t))
 664
 665         dataAdd += uncommonSize(t)
 666         mcount := len(m)
 667         if mcount != int(uint16(mcount)) {
 668                 Fatalf("too many methods on %v: %d", t, mcount)
 669         }
 670         xcount := sort.Search(mcount, func(i int) bool { return !types.IsExported(m[i].name.Name) })
 671         if dataAdd != int(uint32(dataAdd)) {
 672                 Fatalf("methods are too far away on %v: %d", t, dataAdd)
 673         }
 674
 675         ot = duint16(lsym, ot, uint16(mcount))
 676         ot = duint16(lsym, ot, uint16(xcount))
 677         ot = duint32(lsym, ot, uint32(dataAdd))
 678         ot = duint32(lsym, ot, 0)
 679         return ot
 680 }
 681
 682 func typePkg(t *types.Type) *types.Pkg {
 683         tsym := t.Sym
 684         if tsym == nil {
 685                 switch t.Etype {
 686                 case TARRAY, TSLICE, TPTR, TCHAN:
 687                         if t.Elem() != nil {
 688                                 tsym = t.Elem().Sym
 689                         }
 690                 }
 691         }
 692         if tsym != nil && t != types.Types[t.Etype] && t != types.Errortype {
 693                 return tsym.Pkg
 694         }
 695         return nil
 696 }
 697
 698 // dextratypeData dumps the backing array for the []method field of
 699 // runtime.uncommontype.
 700 func dextratypeData(lsym *obj.LSym, ot int, t *types.Type) int {
 701         for _, a := range methods(t) {
 702                 // ../../../../runtime/type.go:/method
 703                 exported := types.IsExported(a.name.Name)
 704                 var pkg *types.Pkg
 705                 if !exported && a.name.Pkg != typePkg(t) {
 706                         pkg = a.name.Pkg
 707                 }
 708                 nsym := dname(a.name.Name, "", pkg, exported)
 709
 710                 ot = dsymptrOff(lsym, ot, nsym)
 711                 ot = dmethodptrOff(lsym, ot, dtypesym(a.mtype))
 712                 ot = dmethodptrOff(lsym, ot, a.isym.Linksym())
 713                 ot = dmethodptrOff(lsym, ot, a.tsym.Linksym())
 714         }
 715         return ot
 716 }
 717
 718 func dmethodptrOff(s *obj.LSym, ot int, x *obj.LSym) int {
 719         duint32(s, ot, 0)
 720         r := obj.Addrel(s)
 721         r.Off = int32(ot)
 722         r.Siz = 4
 723         r.Sym = x
 724         r.Type = objabi.R_METHODOFF
 725         return ot + 4
 726 }
 727
 728 var kinds = []int{
 729         TINT:        objabi.KindInt,
 730         TUINT:       objabi.KindUint,
 731         TINT8:       objabi.KindInt8,
 732         TUINT8:      objabi.KindUint8,
 733         TINT16:      objabi.KindInt16,
 734         TUINT16:     objabi.KindUint16,
 735         TINT32:      objabi.KindInt32,
 736         TUINT32:     objabi.KindUint32,
 737         TINT64:      objabi.KindInt64,
 738         TUINT64:     objabi.KindUint64,
 739         TUINTPTR:    objabi.KindUintptr,
 740         TFLOAT32:    objabi.KindFloat32,
 741         TFLOAT64:    objabi.KindFloat64,
 742         TBOOL:       objabi.KindBool,
 743         TSTRING:     objabi.KindString,
 744         TPTR:        objabi.KindPtr,
 745         TSTRUCT:     objabi.KindStruct,
 746         TINTER:      objabi.KindInterface,
 747         TCHAN:       objabi.KindChan,
 748         TMAP:        objabi.KindMap,
 749         TARRAY:      objabi.KindArray,
 750         TSLICE:      objabi.KindSlice,
 751         TFUNC:       objabi.KindFunc,
 752         TCOMPLEX64:  objabi.KindComplex64,
 753         TCOMPLEX128: objabi.KindComplex128,
 754         TUNSAFEPTR:  objabi.KindUnsafePointer,
 755 }
 756
 757 // typeptrdata returns the length in bytes of the prefix of t
 758 // containing pointer data. Anything after this offset is scalar data.
 759 func typeptrdata(t *types.Type) int64 {
 760         if !t.HasPointers() {
 761                 return 0
 762         }
 763
 764         switch t.Etype {
 765         case TPTR,
 766                 TUNSAFEPTR,
 767                 TFUNC,
 768                 TCHAN,
 769                 TMAP:
 770                 return int64(Widthptr)
 771
 772         case TSTRING:
 773                 // struct { byte *str; intgo len; }
 774                 return int64(Widthptr)
 775
 776         case TINTER:
 777                 // struct { Itab *tab;  void *data; } or
 778                 // struct { Type *type; void *data; }
 779                 // Note: see comment in plive.go:onebitwalktype1.
 780                 return 2 * int64(Widthptr)
 781
 782         case TSLICE:
 783                 // struct { byte *array; uintgo len; uintgo cap; }
 784                 return int64(Widthptr)
 785
 786         case TARRAY:
 787                 // haspointers already eliminated t.NumElem() == 0.
 788                 return (t.NumElem()-1)*t.Elem().Width + typeptrdata(t.Elem())
 789
 790         case TSTRUCT:
 791                 // Find the last field that has pointers.
 792                 var lastPtrField *types.Field
 793                 for _, t1 := range t.Fields().Slice() {
 794                         if t1.Type.HasPointers() {
 795                                 lastPtrField = t1
 796                         }
 797                 }
 798                 return lastPtrField.Offset + typeptrdata(lastPtrField.Type)
 799
 800         default:
 801                 Fatalf("typeptrdata: unexpected type, %v", t)
 802                 return 0
 803         }
 804 }
 805
 806 // tflag is documented in reflect/type.go.
 807 //
 808 // tflag values must be kept in sync with copies in:
 809 //      cmd/compile/internal/gc/reflect.go
 810 //      cmd/link/internal/ld/decodesym.go
 811 //      reflect/type.go
 812 //      runtime/type.go
 813 const (
 814         tflagUncommon      = 1 << 0
 815         tflagExtraStar     = 1 << 1
 816         tflagNamed         = 1 << 2
 817         tflagRegularMemory = 1 << 3
 818 )
 819
 820 var (
 821         memhashvarlen  *obj.LSym
 822         memequalvarlen *obj.LSym
 823 )
 824
 825 // dcommontype dumps the contents of a reflect.rtype (runtime._type).
 826 func dcommontype(lsym *obj.LSym, t *types.Type) int {
 827         dowidth(t)
 828         eqfunc := geneq(t)
 829
 830         sptrWeak := true
 831         var sptr *obj.LSym
 832         if !t.IsPtr() || t.IsPtrElem() {
 833                 tptr := types.NewPtr(t)
 834                 if t.Sym != nil || methods(tptr) != nil {
 835                         sptrWeak = false
 836                 }
 837                 sptr = dtypesym(tptr)
 838         }
 839
 840         gcsym, useGCProg, ptrdata := dgcsym(t)
 841
 842         // ../../../../reflect/type.go:/^type.rtype
 843         // actual type structure
 844         //      type rtype struct {
 845         //              size          uintptr
 846         //              ptrdata       uintptr
 847         //              hash          uint32
 848         //              tflag         tflag
 849         //              align         uint8
 850         //              fieldAlign    uint8
 851         //              kind          uint8
 852         //              equal         func(unsafe.Pointer, unsafe.Pointer) bool
 853         //              gcdata        *byte
 854         //              str           nameOff
 855         //              ptrToThis     typeOff
 856         //      }
 857         ot := 0
 858         ot = duintptr(lsym, ot, uint64(t.Width))
 859         ot = duintptr(lsym, ot, uint64(ptrdata))
 860         ot = duint32(lsym, ot, typehash(t))
 861
 862         var tflag uint8
 863         if uncommonSize(t) != 0 {
 864                 tflag |= tflagUncommon
 865         }
 866         if t.Sym != nil && t.Sym.Name != "" {
 867                 tflag |= tflagNamed
 868         }
 869         if IsRegularMemory(t) {
 870                 tflag |= tflagRegularMemory
 871         }
 872
 873         exported := false
 874         p := t.LongString()
 875         // If we're writing out type T,
 876         // we are very likely to write out type *T as well.
 877         // Use the string "*T"[1:] for "T", so that the two
 878         // share storage. This is a cheap way to reduce the
 879         // amount of space taken up by reflect strings.
 880         if !strings.HasPrefix(p, "*") {
 881                 p = "*" + p
 882                 tflag |= tflagExtraStar
 883                 if t.Sym != nil {
 884                         exported = types.IsExported(t.Sym.Name)
 885                 }
 886         } else {
 887                 if t.Elem() != nil && t.Elem().Sym != nil {
 888                         exported = types.IsExported(t.Elem().Sym.Name)
 889                 }
 890         }
 891
 892         ot = duint8(lsym, ot, tflag)
 893
 894         // runtime (and common sense) expects alignment to be a power of two.
 895         i := int(t.Align)
 896
 897         if i == 0 {
 898                 i = 1
 899         }
 900         if i&(i-1) != 0 {
 901                 Fatalf("invalid alignment %d for %v", t.Align, t)
 902         }
 903         ot = duint8(lsym, ot, t.Align) // align
 904         ot = duint8(lsym, ot, t.Align) // fieldAlign
 905
 906         i = kinds[t.Etype]
 907         if isdirectiface(t) {
 908                 i |= objabi.KindDirectIface
 909         }
 910         if useGCProg {
 911                 i |= objabi.KindGCProg
 912         }
 913         ot = duint8(lsym, ot, uint8(i)) // kind
 914         if eqfunc != nil {
 915                 ot = dsymptr(lsym, ot, eqfunc, 0) // equality function
 916         } else {
 917                 ot = duintptr(lsym, ot, 0) // type we can't do == with
 918         }
 919         ot = dsymptr(lsym, ot, gcsym, 0) // gcdata
 920
 921         nsym := dname(p, "", nil, exported)
 922         ot = dsymptrOff(lsym, ot, nsym) // str
 923         // ptrToThis
 924         if sptr == nil {
 925                 ot = duint32(lsym, ot, 0)
 926         } else if sptrWeak {
 927                 ot = dsymptrWeakOff(lsym, ot, sptr)
 928         } else {
 929                 ot = dsymptrOff(lsym, ot, sptr)
 930         }
 931
 932         return ot
 933 }
 934
 935 // typeHasNoAlg reports whether t does not have any associated hash/eq
 936 // algorithms because t, or some component of t, is marked Noalg.
 937 func typeHasNoAlg(t *types.Type) bool {
 938         a, bad := algtype1(t)
 939         return a == ANOEQ && bad.Noalg()
 940 }
 941
 942 func typesymname(t *types.Type) string {
 943         name := t.ShortString()
 944         // Use a separate symbol name for Noalg types for #17752.
 945         if typeHasNoAlg(t) {
 946                 name = "noalg." + name
 947         }
 948         return name
 949 }
 950
 951 // Fake package for runtime type info (headers)
 952 // Don't access directly, use typeLookup below.
 953 var (
 954         typepkgmu sync.Mutex // protects typepkg lookups
 955         typepkg   = types.NewPkg("type", "type")
 956 )
 957
 958 func typeLookup(name string) *types.Sym {
 959         typepkgmu.Lock()
 960         s := typepkg.Lookup(name)
 961         typepkgmu.Unlock()
 962         return s
 963 }
 964
 965 func typesym(t *types.Type) *types.Sym {
 966         return typeLookup(typesymname(t))
 967 }
 968
 969 // tracksym returns the symbol for tracking use of field/method f, assumed
 970 // to be a member of struct/interface type t.
 971 func tracksym(t *types.Type, f *types.Field) *types.Sym {
 972         return trackpkg.Lookup(t.ShortString() + "." + f.Sym.Name)
 973 }
 974
 975 func typesymprefix(prefix string, t *types.Type) *types.Sym {
 976         p := prefix + "." + t.ShortString()
 977         s := typeLookup(p)
 978
 979         // This function is for looking up type-related generated functions
 980         // (e.g. eq and hash). Make sure they are indeed generated.
 981         signatmu.Lock()
 982         addsignat(t)
 983         signatmu.Unlock()
 984
 985         //print("algsym: %s -> %+S\n", p, s);
 986
 987         return s
 988 }
 989
 990 func typenamesym(t *types.Type) *types.Sym {
 991         if t == nil || (t.IsPtr() && t.Elem() == nil) || t.IsUntyped() {
 992                 Fatalf("typenamesym %v", t)
 993         }
 994         s := typesym(t)
 995         signatmu.Lock()
 996         addsignat(t)
 997         signatmu.Unlock()
 998         return s
 999 }
1000
1001 func typename(t *types.Type) *Node {
1002         s := typenamesym(t)
1003         if s.Def == nil {
1004                 n := newnamel(src.NoXPos, s)
1005                 n.Type = types.Types[TUINT8]
1006                 n.SetClass(PEXTERN)
1007                 n.SetTypecheck(1)
1008                 s.Def = asTypesNode(n)
1009         }
1010
1011         n := nod(OADDR, asNode(s.Def), nil)
1012         n.Type = types.NewPtr(asNode(s.Def).Type)
1013         n.SetTypecheck(1)
1014         return n
1015 }
1016
1017 func itabname(t, itype *types.Type) *Node {
1018         if t == nil || (t.IsPtr() && t.Elem() == nil) || t.IsUntyped() || !itype.IsInterface() || itype.IsEmptyInterface() {
1019                 Fatalf("itabname(%v, %v)", t, itype)
1020         }
1021         s := itabpkg.Lookup(t.ShortString() + "," + itype.ShortString())
1022         if s.Def == nil {
1023                 n := newname(s)
1024                 n.Type = types.Types[TUINT8]
1025                 n.SetClass(PEXTERN)
1026                 n.SetTypecheck(1)
1027                 s.Def = asTypesNode(n)
1028                 itabs = append(itabs, itabEntry{t: t, itype: itype, lsym: s.Linksym()})
1029         }
1030
1031         n := nod(OADDR, asNode(s.Def), nil)
1032         n.Type = types.NewPtr(asNode(s.Def).Type)
1033         n.SetTypecheck(1)
1034         return n
1035 }
1036
1037 // isreflexive reports whether t has a reflexive equality operator.
1038 // That is, if x==x for all x of type t.
1039 func isreflexive(t *types.Type) bool {
1040         switch t.Etype {
1041         case TBOOL,
1042                 TINT,
1043                 TUINT,
1044                 TINT8,
1045                 TUINT8,
1046                 TINT16,
1047                 TUINT16,
1048                 TINT32,
1049                 TUINT32,
1050                 TINT64,
1051                 TUINT64,
1052                 TUINTPTR,
1053                 TPTR,
1054                 TUNSAFEPTR,
1055                 TSTRING,
1056                 TCHAN:
1057                 return true
1058
1059         case TFLOAT32,
1060                 TFLOAT64,
1061                 TCOMPLEX64,
1062                 TCOMPLEX128,
1063                 TINTER:
1064                 return false
1065
1066         case TARRAY:
1067                 return isreflexive(t.Elem())
1068
1069         case TSTRUCT:
1070                 for _, t1 := range t.Fields().Slice() {
1071                         if !isreflexive(t1.Type) {
1072                                 return false
1073                         }
1074                 }
1075                 return true
1076
1077         default:
1078                 Fatalf("bad type for map key: %v", t)
1079                 return false
1080         }
1081 }
1082
1083 // needkeyupdate reports whether map updates with t as a key
1084 // need the key to be updated.
1085 func needkeyupdate(t *types.Type) bool {
1086         switch t.Etype {
1087         case TBOOL, TINT, TUINT, TINT8, TUINT8, TINT16, TUINT16, TINT32, TUINT32,
1088                 TINT64, TUINT64, TUINTPTR, TPTR, TUNSAFEPTR, TCHAN:
1089                 return false
1090
1091         case TFLOAT32, TFLOAT64, TCOMPLEX64, TCOMPLEX128, // floats and complex can be +0/-0
1092                 TINTER,
1093                 TSTRING: // strings might have smaller backing stores
1094                 return true
1095
1096         case TARRAY:
1097                 return needkeyupdate(t.Elem())
1098
1099         case TSTRUCT:
1100                 for _, t1 := range t.Fields().Slice() {
1101                         if needkeyupdate(t1.Type) {
1102                                 return true
1103                         }
1104                 }
1105                 return false
1106
1107         default:
1108                 Fatalf("bad type for map key: %v", t)
1109                 return true
1110         }
1111 }
1112
1113 // hashMightPanic reports whether the hash of a map key of type t might panic.
1114 func hashMightPanic(t *types.Type) bool {
1115         switch t.Etype {
1116         case TINTER:
1117                 return true
1118
1119         case TARRAY:
1120                 return hashMightPanic(t.Elem())
1121
1122         case TSTRUCT:
1123                 for _, t1 := range t.Fields().Slice() {
1124                         if hashMightPanic(t1.Type) {
1125                                 return true
1126                         }
1127                 }
1128                 return false
1129
1130         default:
1131                 return false
1132         }
1133 }
1134
1135 // formalType replaces byte and rune aliases with real types.
1136 // They've been separate internally to make error messages
1137 // better, but we have to merge them in the reflect tables.
1138 func formalType(t *types.Type) *types.Type {
1139         if t == types.Bytetype || t == types.Runetype {
1140                 return types.Types[t.Etype]
1141         }
1142         return t
1143 }
1144
1145 func dtypesym(t *types.Type) *obj.LSym {
1146         t = formalType(t)
1147         if t.IsUntyped() {
1148                 Fatalf("dtypesym %v", t)
1149         }
1150
1151         s := typesym(t)
1152         lsym := s.Linksym()
1153         if s.Siggen() {
1154                 return lsym
1155         }
1156         s.SetSiggen(true)
1157
1158         // special case (look for runtime below):
1159         // when compiling package runtime,
1160         // emit the type structures for int, float, etc.
1161         tbase := t
1162
1163         if t.IsPtr() && t.Sym == nil && t.Elem().Sym != nil {
1164                 tbase = t.Elem()
1165         }
1166         dupok := 0
1167         if tbase.Sym == nil {
1168                 dupok = obj.DUPOK
1169         }
1170
1171         if myimportpath != "runtime" || (tbase != types.Types[tbase.Etype] && tbase != types.Bytetype && tbase != types.Runetype && tbase != types.Errortype) { // int, float, etc
1172                 // named types from other files are defined only by those files
1173                 if tbase.Sym != nil && tbase.Sym.Pkg != localpkg {
1174                         if i, ok := typeSymIdx[tbase]; ok {
1175                                 lsym.Pkg = tbase.Sym.Pkg.Prefix
1176                                 if t != tbase {
1177                                         lsym.SymIdx = int32(i[1])
1178                                 } else {
1179                                         lsym.SymIdx = int32(i[0])
1180                                 }
1181                                 lsym.Set(obj.AttrIndexed, true)
1182                         }
1183                         return lsym
1184                 }
1185                 // TODO(mdempsky): Investigate whether this can happen.
1186                 if tbase.Etype == TFORW {
1187                         return lsym
1188                 }
1189         }
1190
1191         ot := 0
1192         switch t.Etype {
1193         default:
1194                 ot = dcommontype(lsym, t)
1195                 ot = dextratype(lsym, ot, t, 0)
1196
1197         case TARRAY:
1198                 // ../../../../runtime/type.go:/arrayType
1199                 s1 := dtypesym(t.Elem())
1200                 t2 := types.NewSlice(t.Elem())
1201                 s2 := dtypesym(t2)
1202                 ot = dcommontype(lsym, t)
1203                 ot = dsymptr(lsym, ot, s1, 0)
1204                 ot = dsymptr(lsym, ot, s2, 0)
1205                 ot = duintptr(lsym, ot, uint64(t.NumElem()))
1206                 ot = dextratype(lsym, ot, t, 0)
1207
1208         case TSLICE:
1209                 // ../../../../runtime/type.go:/sliceType
1210                 s1 := dtypesym(t.Elem())
1211                 ot = dcommontype(lsym, t)
1212                 ot = dsymptr(lsym, ot, s1, 0)
1213                 ot = dextratype(lsym, ot, t, 0)
1214
1215         case TCHAN:
1216                 // ../../../../runtime/type.go:/chanType
1217                 s1 := dtypesym(t.Elem())
1218                 ot = dcommontype(lsym, t)
1219                 ot = dsymptr(lsym, ot, s1, 0)
1220                 ot = duintptr(lsym, ot, uint64(t.ChanDir()))
1221                 ot = dextratype(lsym, ot, t, 0)
1222
1223         case TFUNC:
1224                 for _, t1 := range t.Recvs().Fields().Slice() {
1225                         dtypesym(t1.Type)
1226                 }
1227                 isddd := false
1228                 for _, t1 := range t.Params().Fields().Slice() {
1229                         isddd = t1.IsDDD()
1230                         dtypesym(t1.Type)
1231                 }
1232                 for _, t1 := range t.Results().Fields().Slice() {
1233                         dtypesym(t1.Type)
1234                 }
1235
1236                 ot = dcommontype(lsym, t)
1237                 inCount := t.NumRecvs() + t.NumParams()
1238                 outCount := t.NumResults()
1239                 if isddd {
1240                         outCount |= 1 << 15
1241                 }
1242                 ot = duint16(lsym, ot, uint16(inCount))
1243                 ot = duint16(lsym, ot, uint16(outCount))
1244                 if Widthptr == 8 {
1245                         ot += 4 // align for *rtype
1246                 }
1247
1248                 dataAdd := (inCount + t.NumResults()) * Widthptr
1249                 ot = dextratype(lsym, ot, t, dataAdd)
1250
1251                 // Array of rtype pointers follows funcType.
1252                 for _, t1 := range t.Recvs().Fields().Slice() {
1253                         ot = dsymptr(lsym, ot, dtypesym(t1.Type), 0)
1254                 }
1255                 for _, t1 := range t.Params().Fields().Slice() {
1256                         ot = dsymptr(lsym, ot, dtypesym(t1.Type), 0)
1257                 }
1258                 for _, t1 := range t.Results().Fields().Slice() {
1259                         ot = dsymptr(lsym, ot, dtypesym(t1.Type), 0)
1260                 }
1261
1262         case TINTER:
1263                 m := imethods(t)
1264                 n := len(m)
1265                 for _, a := range m {
1266                         dtypesym(a.type_)
1267                 }
1268
1269                 // ../../../../runtime/type.go:/interfaceType
1270                 ot = dcommontype(lsym, t)
1271
1272                 var tpkg *types.Pkg
1273                 if t.Sym != nil && t != types.Types[t.Etype] && t != types.Errortype {
1274                         tpkg = t.Sym.Pkg
1275                 }
1276                 ot = dgopkgpath(lsym, ot, tpkg)
1277
1278                 ot = dsymptr(lsym, ot, lsym, ot+3*Widthptr+uncommonSize(t))
1279                 ot = duintptr(lsym, ot, uint64(n))
1280                 ot = duintptr(lsym, ot, uint64(n))
1281                 dataAdd := imethodSize() * n
1282                 ot = dextratype(lsym, ot, t, dataAdd)
1283
1284                 for _, a := range m {
1285                         // ../../../../runtime/type.go:/imethod
1286                         exported := types.IsExported(a.name.Name)
1287                         var pkg *types.Pkg
1288                         if !exported && a.name.Pkg != tpkg {
1289                                 pkg = a.name.Pkg
1290                         }
1291                         nsym := dname(a.name.Name, "", pkg, exported)
1292
1293                         ot = dsymptrOff(lsym, ot, nsym)
1294                         ot = dsymptrOff(lsym, ot, dtypesym(a.type_))
1295                 }
1296
1297         // ../../../../runtime/type.go:/mapType
1298         case TMAP:
1299                 s1 := dtypesym(t.Key())
1300                 s2 := dtypesym(t.Elem())
1301                 s3 := dtypesym(bmap(t))
1302                 hasher := genhash(t.Key())
1303
1304                 ot = dcommontype(lsym, t)
1305                 ot = dsymptr(lsym, ot, s1, 0)
1306                 ot = dsymptr(lsym, ot, s2, 0)
1307                 ot = dsymptr(lsym, ot, s3, 0)
1308                 ot = dsymptr(lsym, ot, hasher, 0)
1309                 var flags uint32
1310                 // Note: flags must match maptype accessors in ../../../../runtime/type.go
1311                 // and maptype builder in ../../../../reflect/type.go:MapOf.
1312                 if t.Key().Width > MAXKEYSIZE {
1313                         ot = duint8(lsym, ot, uint8(Widthptr))
1314                         flags |= 1 // indirect key
1315                 } else {
1316                         ot = duint8(lsym, ot, uint8(t.Key().Width))
1317                 }
1318
1319                 if t.Elem().Width > MAXELEMSIZE {
1320                         ot = duint8(lsym, ot, uint8(Widthptr))
1321                         flags |= 2 // indirect value
1322                 } else {
1323                         ot = duint8(lsym, ot, uint8(t.Elem().Width))
1324                 }
1325                 ot = duint16(lsym, ot, uint16(bmap(t).Width))
1326                 if isreflexive(t.Key()) {
1327                         flags |= 4 // reflexive key
1328                 }
1329                 if needkeyupdate(t.Key()) {
1330                         flags |= 8 // need key update
1331                 }
1332                 if hashMightPanic(t.Key()) {
1333                         flags |= 16 // hash might panic
1334                 }
1335                 ot = duint32(lsym, ot, flags)
1336                 ot = dextratype(lsym, ot, t, 0)
1337
1338         case TPTR:
1339                 if t.Elem().Etype == TANY {
1340                         // ../../../../runtime/type.go:/UnsafePointerType
1341                         ot = dcommontype(lsym, t)
1342                         ot = dextratype(lsym, ot, t, 0)
1343
1344                         break
1345                 }
1346
1347                 // ../../../../runtime/type.go:/ptrType
1348                 s1 := dtypesym(t.Elem())
1349
1350                 ot = dcommontype(lsym, t)
1351                 ot = dsymptr(lsym, ot, s1, 0)
1352                 ot = dextratype(lsym, ot, t, 0)
1353
1354         // ../../../../runtime/type.go:/structType
1355         // for security, only the exported fields.
1356         case TSTRUCT:
1357                 fields := t.Fields().Slice()
1358
1359                 // omitFieldForAwfulBoringCryptoKludge reports whether
1360                 // the field t should be omitted from the reflect data.
1361                 // In the crypto/... packages we omit an unexported field
1362                 // named "boring", to keep from breaking client code that
1363                 // expects rsa.PublicKey etc to have only public fields.
1364                 // As the name suggests, this is an awful kludge, but it is
1365                 // limited to the dev.boringcrypto branch and avoids
1366                 // much more invasive effects elsewhere.
1367                 omitFieldForAwfulBoringCryptoKludge := func(t *types.Field) bool {
1368                         if t.Sym == nil || t.Sym.Name != "boring" || t.Sym.Pkg == nil {
1369                                 return false
1370                         }
1371                         path := t.Sym.Pkg.Path
1372                         if t.Sym.Pkg == localpkg {
1373                                 path = myimportpath
1374                         }
1375                         return strings.HasPrefix(path, "crypto/")
1376                 }
1377                 newFields := fields[:0:0]
1378                 for _, t1 := range fields {
1379                         if !omitFieldForAwfulBoringCryptoKludge(t1) {
1380                                 newFields = append(newFields, t1)
1381                         }
1382                 }
1383                 fields = newFields
1384
1385                 for _, t1 := range fields {
1386                         dtypesym(t1.Type)
1387                 }
1388
1389                 // All non-exported struct field names within a struct
1390                 // type must originate from a single package. By
1391                 // identifying and recording that package within the
1392                 // struct type descriptor, we can omit that
1393                 // information from the field descriptors.
1394                 var spkg *types.Pkg
1395                 for _, f := range fields {
1396                         if !types.IsExported(f.Sym.Name) {
1397                                 spkg = f.Sym.Pkg
1398                                 break
1399                         }
1400                 }
1401
1402                 ot = dcommontype(lsym, t)
1403                 ot = dgopkgpath(lsym, ot, spkg)
1404                 ot = dsymptr(lsym, ot, lsym, ot+3*Widthptr+uncommonSize(t))
1405                 ot = duintptr(lsym, ot, uint64(len(fields)))
1406                 ot = duintptr(lsym, ot, uint64(len(fields)))
1407
1408                 dataAdd := len(fields) * structfieldSize()
1409                 ot = dextratype(lsym, ot, t, dataAdd)
1410
1411                 for _, f := range fields {
1412                         // ../../../../runtime/type.go:/structField
1413                         ot = dnameField(lsym, ot, spkg, f)
1414                         ot = dsymptr(lsym, ot, dtypesym(f.Type), 0)
1415                         offsetAnon := uint64(f.Offset) << 1
1416                         if offsetAnon>>1 != uint64(f.Offset) {
1417                                 Fatalf("%v: bad field offset for %s", t, f.Sym.Name)
1418                         }
1419                         if f.Embedded != 0 {
1420                                 offsetAnon |= 1
1421                         }
1422                         ot = duintptr(lsym, ot, offsetAnon)
1423                 }
1424         }
1425
1426         ot = dextratypeData(lsym, ot, t)
1427         ggloblsym(lsym, int32(ot), int16(dupok|obj.RODATA))
1428
1429         // The linker will leave a table of all the typelinks for
1430         // types in the binary, so the runtime can find them.
1431         //
1432         // When buildmode=shared, all types are in typelinks so the
1433         // runtime can deduplicate type pointers.
1434         keep := Ctxt.Flag_dynlink
1435         if !keep && t.Sym == nil {
1436                 // For an unnamed type, we only need the link if the type can
1437                 // be created at run time by reflect.PtrTo and similar
1438                 // functions. If the type exists in the program, those
1439                 // functions must return the existing type structure rather
1440                 // than creating a new one.
1441                 switch t.Etype {
1442                 case TPTR, TARRAY, TCHAN, TFUNC, TMAP, TSLICE, TSTRUCT:
1443                         keep = true
1444                 }
1445         }
1446         // Do not put Noalg types in typelinks.  See issue #22605.
1447         if typeHasNoAlg(t) {
1448                 keep = false
1449         }
1450         lsym.Set(obj.AttrMakeTypelink, keep)
1451
1452         return lsym
1453 }
1454
1455 // ifaceMethodOffset returns the offset of the i-th method in the interface
1456 // type descriptor, ityp.
1457 func ifaceMethodOffset(ityp *types.Type, i int64) int64 {
1458         // interface type descriptor layout is struct {
1459         //   _type        // commonSize
1460         //   pkgpath      // 1 word
1461         //   []imethod    // 3 words (pointing to [...]imethod below)
1462         //   uncommontype // uncommonSize
1463         //   [...]imethod
1464         // }
1465         // The size of imethod is 8.
1466         return int64(commonSize()+4*Widthptr+uncommonSize(ityp)) + i*8
1467 }
1468
1469 // for each itabEntry, gather the methods on
1470 // the concrete type that implement the interface
1471 func peekitabs() {
1472         for i := range itabs {
1473                 tab := &itabs[i]
1474                 methods := genfun(tab.t, tab.itype)
1475                 if len(methods) == 0 {
1476                         continue
1477                 }
1478                 tab.entries = methods
1479         }
1480 }
1481
1482 // for the given concrete type and interface
1483 // type, return the (sorted) set of methods
1484 // on the concrete type that implement the interface
1485 func genfun(t, it *types.Type) []*obj.LSym {
1486         if t == nil || it == nil {
1487                 return nil
1488         }
1489         sigs := imethods(it)
1490         methods := methods(t)
1491         out := make([]*obj.LSym, 0, len(sigs))
1492         // TODO(mdempsky): Short circuit before calling methods(t)?
1493         // See discussion on CL 105039.
1494         if len(sigs) == 0 {
1495                 return nil
1496         }
1497
1498         // both sigs and methods are sorted by name,
1499         // so we can find the intersect in a single pass
1500         for _, m := range methods {
1501                 if m.name == sigs[0].name {
1502                         out = append(out, m.isym.Linksym())
1503                         sigs = sigs[1:]
1504                         if len(sigs) == 0 {
1505                                 break
1506                         }
1507                 }
1508         }
1509
1510         if len(sigs) != 0 {
1511                 Fatalf("incomplete itab")
1512         }
1513
1514         return out
1515 }
1516
1517 // itabsym uses the information gathered in
1518 // peekitabs to de-virtualize interface methods.
1519 // Since this is called by the SSA backend, it shouldn't
1520 // generate additional Nodes, Syms, etc.
1521 func itabsym(it *obj.LSym, offset int64) *obj.LSym {
1522         var syms []*obj.LSym
1523         if it == nil {
1524                 return nil
1525         }
1526
1527         for i := range itabs {
1528                 e := &itabs[i]
1529                 if e.lsym == it {
1530                         syms = e.entries
1531                         break
1532                 }
1533         }
1534         if syms == nil {
1535                 return nil
1536         }
1537
1538         // keep this arithmetic in sync with *itab layout
1539         methodnum := int((offset - 2*int64(Widthptr) - 8) / int64(Widthptr))
1540         if methodnum >= len(syms) {
1541                 return nil
1542         }
1543         return syms[methodnum]
1544 }
1545
1546 // addsignat ensures that a runtime type descriptor is emitted for t.
1547 func addsignat(t *types.Type) {
1548         if _, ok := signatset[t]; !ok {
1549                 signatset[t] = struct{}{}
1550                 signatslice = append(signatslice, t)
1551         }
1552 }
1553
1554 func addsignats(dcls []*Node) {
1555         // copy types from dcl list to signatset
1556         for _, n := range dcls {
1557                 if n.Op == OTYPE {
1558                         addsignat(n.Type)
1559                 }
1560         }
1561 }
1562
1563 func dumpsignats() {
1564         // Process signatset. Use a loop, as dtypesym adds
1565         // entries to signatset while it is being processed.
1566         signats := make([]typeAndStr, len(signatslice))
1567         for len(signatslice) > 0 {
1568                 signats = signats[:0]
1569                 // Transfer entries to a slice and sort, for reproducible builds.
1570                 for _, t := range signatslice {
1571                         signats = append(signats, typeAndStr{t: t, short: typesymname(t), regular: t.String()})
1572                         delete(signatset, t)
1573                 }
1574                 signatslice = signatslice[:0]
1575                 sort.Sort(typesByString(signats))
1576                 for _, ts := range signats {
1577                         t := ts.t
1578                         dtypesym(t)
1579                         if t.Sym != nil {
1580                                 dtypesym(types.NewPtr(t))
1581                         }
1582                 }
1583         }
1584 }
1585
1586 func dumptabs() {
1587         // process itabs
1588         for _, i := range itabs {
1589                 // dump empty itab symbol into i.sym
1590                 // type itab struct {
1591                 //   inter  *interfacetype
1592                 //   _type  *_type
1593                 //   hash   uint32
1594                 //   _      [4]byte
1595                 //   fun    [1]uintptr // variable sized
1596                 // }
1597                 o := dsymptr(i.lsym, 0, dtypesym(i.itype), 0)
1598                 o = dsymptr(i.lsym, o, dtypesym(i.t), 0)
1599                 o = duint32(i.lsym, o, typehash(i.t)) // copy of type hash
1600                 o += 4                                // skip unused field
1601                 for _, fn := range genfun(i.t, i.itype) {
1602                         o = dsymptr(i.lsym, o, fn, 0) // method pointer for each method
1603                 }
1604                 // Nothing writes static itabs, so they are read only.
1605                 ggloblsym(i.lsym, int32(o), int16(obj.DUPOK|obj.RODATA))
1606                 i.lsym.Set(obj.AttrContentAddressable, true)
1607         }
1608
1609         // process ptabs
1610         if localpkg.Name == "main" && len(ptabs) > 0 {
1611                 ot := 0
1612                 s := Ctxt.Lookup("go.plugin.tabs")
1613                 for _, p := range ptabs {
1614                         // Dump ptab symbol into go.pluginsym package.
1615                         //
1616                         // type ptab struct {
1617                         //      name nameOff
1618                         //      typ  typeOff // pointer to symbol
1619                         // }
1620                         nsym := dname(p.s.Name, "", nil, true)
1621                         ot = dsymptrOff(s, ot, nsym)
1622                         ot = dsymptrOff(s, ot, dtypesym(p.t))
1623                 }
1624                 ggloblsym(s, int32(ot), int16(obj.RODATA))
1625
1626                 ot = 0
1627                 s = Ctxt.Lookup("go.plugin.exports")
1628                 for _, p := range ptabs {
1629                         ot = dsymptr(s, ot, p.s.Linksym(), 0)
1630                 }
1631                 ggloblsym(s, int32(ot), int16(obj.RODATA))
1632         }
1633 }
1634
1635 func dumpimportstrings() {
1636         // generate import strings for imported packages
1637         for _, p := range types.ImportedPkgList() {
1638                 dimportpath(p)
1639         }
1640 }
1641
1642 func dumpbasictypes() {
1643         // do basic types if compiling package runtime.
1644         // they have to be in at least one package,
1645         // and runtime is always loaded implicitly,
1646         // so this is as good as any.
1647         // another possible choice would be package main,
1648         // but using runtime means fewer copies in object files.
1649         if myimportpath == "runtime" {
1650                 for i := types.EType(1); i <= TBOOL; i++ {
1651                         dtypesym(types.NewPtr(types.Types[i]))
1652                 }
1653                 dtypesym(types.NewPtr(types.Types[TSTRING]))
1654                 dtypesym(types.NewPtr(types.Types[TUNSAFEPTR]))
1655
1656                 // emit type structs for error and func(error) string.
1657                 // The latter is the type of an auto-generated wrapper.
1658                 dtypesym(types.NewPtr(types.Errortype))
1659
1660                 dtypesym(functype(nil, []*Node{anonfield(types.Errortype)}, []*Node{anonfield(types.Types[TSTRING])}))
1661
1662                 // add paths for runtime and main, which 6l imports implicitly.
1663                 dimportpath(Runtimepkg)
1664
1665                 if flag_race {
1666                         dimportpath(racepkg)
1667                 }
1668                 if flag_msan {
1669                         dimportpath(msanpkg)
1670                 }
1671                 dimportpath(types.NewPkg("main", ""))
1672         }
1673 }
1674
1675 type typeAndStr struct {
1676         t       *types.Type
1677         short   string
1678         regular string
1679 }
1680
1681 type typesByString []typeAndStr
1682
1683 func (a typesByString) Len() int { return len(a) }
1684 func (a typesByString) Less(i, j int) bool {
1685         if a[i].short != a[j].short {
1686                 return a[i].short < a[j].short
1687         }
1688         // When the only difference between the types is whether
1689         // they refer to byte or uint8, such as **byte vs **uint8,
1690         // the types' ShortStrings can be identical.
1691         // To preserve deterministic sort ordering, sort these by String().
1692         if a[i].regular != a[j].regular {
1693                 return a[i].regular < a[j].regular
1694         }
1695         // Identical anonymous interfaces defined in different locations
1696         // will be equal for the above checks, but different in DWARF output.
1697         // Sort by source position to ensure deterministic order.
1698         // See issues 27013 and 30202.
1699         if a[i].t.Etype == types.TINTER && a[i].t.Methods().Len() > 0 {
1700                 return a[i].t.Methods().Index(0).Pos.Before(a[j].t.Methods().Index(0).Pos)
1701         }
1702         return false
1703 }
1704 func (a typesByString) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
1705
1706 // maxPtrmaskBytes is the maximum length of a GC ptrmask bitmap,
1707 // which holds 1-bit entries describing where pointers are in a given type.
1708 // Above this length, the GC information is recorded as a GC program,
1709 // which can express repetition compactly. In either form, the
1710 // information is used by the runtime to initialize the heap bitmap,
1711 // and for large types (like 128 or more words), they are roughly the
1712 // same speed. GC programs are never much larger and often more
1713 // compact. (If large arrays are involved, they can be arbitrarily
1714 // more compact.)
1715 //
1716 // The cutoff must be large enough that any allocation large enough to
1717 // use a GC program is large enough that it does not share heap bitmap
1718 // bytes with any other objects, allowing the GC program execution to
1719 // assume an aligned start and not use atomic operations. In the current
1720 // runtime, this means all malloc size classes larger than the cutoff must
1721 // be multiples of four words. On 32-bit systems that's 16 bytes, and
1722 // all size classes >= 16 bytes are 16-byte aligned, so no real constraint.
1723 // On 64-bit systems, that's 32 bytes, and 32-byte alignment is guaranteed
1724 // for size classes >= 256 bytes. On a 64-bit system, 256 bytes allocated
1725 // is 32 pointers, the bits for which fit in 4 bytes. So maxPtrmaskBytes
1726 // must be >= 4.
1727 //
1728 // We used to use 16 because the GC programs do have some constant overhead
1729 // to get started, and processing 128 pointers seems to be enough to
1730 // amortize that overhead well.
1731 //
1732 // To make sure that the runtime's chansend can call typeBitsBulkBarrier,
1733 // we raised the limit to 2048, so that even 32-bit systems are guaranteed to
1734 // use bitmaps for objects up to 64 kB in size.
1735 //
1736 // Also known to reflect/type.go.
1737 //
1738 const maxPtrmaskBytes = 2048
1739
1740 // dgcsym emits and returns a data symbol containing GC information for type t,
1741 // along with a boolean reporting whether the UseGCProg bit should be set in
1742 // the type kind, and the ptrdata field to record in the reflect type information.
1743 func dgcsym(t *types.Type) (lsym *obj.LSym, useGCProg bool, ptrdata int64) {
1744         ptrdata = typeptrdata(t)
1745         if ptrdata/int64(Widthptr) <= maxPtrmaskBytes*8 {
1746                 lsym = dgcptrmask(t)
1747                 return
1748         }
1749
1750         useGCProg = true
1751         lsym, ptrdata = dgcprog(t)
1752         return
1753 }
1754
1755 // dgcptrmask emits and returns the symbol containing a pointer mask for type t.
1756 func dgcptrmask(t *types.Type) *obj.LSym {
1757         ptrmask := make([]byte, (typeptrdata(t)/int64(Widthptr)+7)/8)
1758         fillptrmask(t, ptrmask)
1759         p := fmt.Sprintf("gcbits.%x", ptrmask)
1760
1761         sym := Runtimepkg.Lookup(p)
1762         lsym := sym.Linksym()
1763         if !sym.Uniq() {
1764                 sym.SetUniq(true)
1765                 for i, x := range ptrmask {
1766                         duint8(lsym, i, x)
1767                 }
1768                 ggloblsym(lsym, int32(len(ptrmask)), obj.DUPOK|obj.RODATA|obj.LOCAL)
1769                 lsym.Set(obj.AttrContentAddressable, true)
1770         }
1771         return lsym
1772 }
1773
1774 // fillptrmask fills in ptrmask with 1s corresponding to the
1775 // word offsets in t that hold pointers.
1776 // ptrmask is assumed to fit at least typeptrdata(t)/Widthptr bits.
1777 func fillptrmask(t *types.Type, ptrmask []byte) {
1778         for i := range ptrmask {
1779                 ptrmask[i] = 0
1780         }
1781         if !t.HasPointers() {
1782                 return
1783         }
1784
1785         vec := bvalloc(8 * int32(len(ptrmask)))
1786         onebitwalktype1(t, 0, vec)
1787
1788         nptr := typeptrdata(t) / int64(Widthptr)
1789         for i := int64(0); i < nptr; i++ {
1790                 if vec.Get(int32(i)) {
1791                         ptrmask[i/8] |= 1 << (uint(i) % 8)
1792                 }
1793         }
1794 }
1795
1796 // dgcprog emits and returns the symbol containing a GC program for type t
1797 // along with the size of the data described by the program (in the range [typeptrdata(t), t.Width]).
1798 // In practice, the size is typeptrdata(t) except for non-trivial arrays.
1799 // For non-trivial arrays, the program describes the full t.Width size.
1800 func dgcprog(t *types.Type) (*obj.LSym, int64) {
1801         dowidth(t)
1802         if t.Width == BADWIDTH {
1803                 Fatalf("dgcprog: %v badwidth", t)
1804         }
1805         lsym := typesymprefix(".gcprog", t).Linksym()
1806         var p GCProg
1807         p.init(lsym)
1808         p.emit(t, 0)
1809         offset := p.w.BitIndex() * int64(Widthptr)
1810         p.end()
1811         if ptrdata := typeptrdata(t); offset < ptrdata || offset > t.Width {
1812                 Fatalf("dgcprog: %v: offset=%d but ptrdata=%d size=%d", t, offset, ptrdata, t.Width)
1813         }
1814         return lsym, offset
1815 }
1816
1817 type GCProg struct {
1818         lsym   *obj.LSym
1819         symoff int
1820         w      gcprog.Writer
1821 }
1822
1823 var Debug_gcprog int // set by -d gcprog
1824
1825 func (p *GCProg) init(lsym *obj.LSym) {
1826         p.lsym = lsym
1827         p.symoff = 4 // first 4 bytes hold program length
1828         p.w.Init(p.writeByte)
1829         if Debug_gcprog > 0 {
1830                 fmt.Fprintf(os.Stderr, "compile: start GCProg for %v\n", lsym)
1831                 p.w.Debug(os.Stderr)
1832         }
1833 }
1834
1835 func (p *GCProg) writeByte(x byte) {
1836         p.symoff = duint8(p.lsym, p.symoff, x)
1837 }
1838
1839 func (p *GCProg) end() {
1840         p.w.End()
1841         duint32(p.lsym, 0, uint32(p.symoff-4))
1842         ggloblsym(p.lsym, int32(p.symoff), obj.DUPOK|obj.RODATA|obj.LOCAL)
1843         if Debug_gcprog > 0 {
1844                 fmt.Fprintf(os.Stderr, "compile: end GCProg for %v\n", p.lsym)
1845         }
1846 }
1847
1848 func (p *GCProg) emit(t *types.Type, offset int64) {
1849         dowidth(t)
1850         if !t.HasPointers() {
1851                 return
1852         }
1853         if t.Width == int64(Widthptr) {
1854                 p.w.Ptr(offset / int64(Widthptr))
1855                 return
1856         }
1857         switch t.Etype {
1858         default:
1859                 Fatalf("GCProg.emit: unexpected type %v", t)
1860
1861         case TSTRING:
1862                 p.w.Ptr(offset / int64(Widthptr))
1863
1864         case TINTER:
1865                 // Note: the first word isn't a pointer. See comment in plive.go:onebitwalktype1.
1866                 p.w.Ptr(offset/int64(Widthptr) + 1)
1867
1868         case TSLICE:
1869                 p.w.Ptr(offset / int64(Widthptr))
1870
1871         case TARRAY:
1872                 if t.NumElem() == 0 {
1873                         // should have been handled by haspointers check above
1874                         Fatalf("GCProg.emit: empty array")
1875                 }
1876
1877                 // Flatten array-of-array-of-array to just a big array by multiplying counts.
1878                 count := t.NumElem()
1879                 elem := t.Elem()
1880                 for elem.IsArray() {
1881                         count *= elem.NumElem()
1882                         elem = elem.Elem()
1883                 }
1884
1885                 if !p.w.ShouldRepeat(elem.Width/int64(Widthptr), count) {
1886                         // Cheaper to just emit the bits.
1887                         for i := int64(0); i < count; i++ {
1888                                 p.emit(elem, offset+i*elem.Width)
1889                         }
1890                         return
1891                 }
1892                 p.emit(elem, offset)
1893                 p.w.ZeroUntil((offset + elem.Width) / int64(Widthptr))
1894                 p.w.Repeat(elem.Width/int64(Widthptr), count-1)
1895
1896         case TSTRUCT:
1897                 for _, t1 := range t.Fields().Slice() {
1898                         p.emit(t1.Type, offset+t1.Offset)
1899                 }
1900         }
1901 }
1902
1903 // zeroaddr returns the address of a symbol with at least
1904 // size bytes of zeros.
1905 func zeroaddr(size int64) *Node {
1906         if size >= 1<<31 {
1907                 Fatalf("map elem too big %d", size)
1908         }
1909         if zerosize < size {
1910                 zerosize = size
1911         }
1912         s := mappkg.Lookup("zero")
1913         if s.Def == nil {
1914                 x := newname(s)
1915                 x.Type = types.Types[TUINT8]
1916                 x.SetClass(PEXTERN)
1917                 x.SetTypecheck(1)
1918                 s.Def = asTypesNode(x)
1919         }
1920         z := nod(OADDR, asNode(s.Def), nil)
1921         z.Type = types.NewPtr(types.Types[TUINT8])
1922         z.SetTypecheck(1)
1923         return z
1924 }