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                 xcount := sort.Search(n, func(i int) bool { return !types.IsExported(m[i].name.Name) })
1279                 ot = dsymptr(lsym, ot, lsym, ot+3*Widthptr+uncommonSize(t))
1280                 ot = duintptr(lsym, ot, uint64(xcount))
1281                 ot = duintptr(lsym, ot, uint64(n))
1282                 dataAdd := imethodSize() * n
1283                 ot = dextratype(lsym, ot, t, dataAdd)
1284
1285                 for _, a := range m {
1286                         // ../../../../runtime/type.go:/imethod
1287                         exported := types.IsExported(a.name.Name)
1288                         var pkg *types.Pkg
1289                         if !exported && a.name.Pkg != tpkg {
1290                                 pkg = a.name.Pkg
1291                         }
1292                         nsym := dname(a.name.Name, "", pkg, exported)
1293
1294                         ot = dsymptrOff(lsym, ot, nsym)
1295                         ot = dsymptrOff(lsym, ot, dtypesym(a.type_))
1296                 }
1297
1298         // ../../../../runtime/type.go:/mapType
1299         case TMAP:
1300                 s1 := dtypesym(t.Key())
1301                 s2 := dtypesym(t.Elem())
1302                 s3 := dtypesym(bmap(t))
1303                 hasher := genhash(t.Key())
1304
1305                 ot = dcommontype(lsym, t)
1306                 ot = dsymptr(lsym, ot, s1, 0)
1307                 ot = dsymptr(lsym, ot, s2, 0)
1308                 ot = dsymptr(lsym, ot, s3, 0)
1309                 ot = dsymptr(lsym, ot, hasher, 0)
1310                 var flags uint32
1311                 // Note: flags must match maptype accessors in ../../../../runtime/type.go
1312                 // and maptype builder in ../../../../reflect/type.go:MapOf.
1313                 if t.Key().Width > MAXKEYSIZE {
1314                         ot = duint8(lsym, ot, uint8(Widthptr))
1315                         flags |= 1 // indirect key
1316                 } else {
1317                         ot = duint8(lsym, ot, uint8(t.Key().Width))
1318                 }
1319
1320                 if t.Elem().Width > MAXELEMSIZE {
1321                         ot = duint8(lsym, ot, uint8(Widthptr))
1322                         flags |= 2 // indirect value
1323                 } else {
1324                         ot = duint8(lsym, ot, uint8(t.Elem().Width))
1325                 }
1326                 ot = duint16(lsym, ot, uint16(bmap(t).Width))
1327                 if isreflexive(t.Key()) {
1328                         flags |= 4 // reflexive key
1329                 }
1330                 if needkeyupdate(t.Key()) {
1331                         flags |= 8 // need key update
1332                 }
1333                 if hashMightPanic(t.Key()) {
1334                         flags |= 16 // hash might panic
1335                 }
1336                 ot = duint32(lsym, ot, flags)
1337                 ot = dextratype(lsym, ot, t, 0)
1338
1339         case TPTR:
1340                 if t.Elem().Etype == TANY {
1341                         // ../../../../runtime/type.go:/UnsafePointerType
1342                         ot = dcommontype(lsym, t)
1343                         ot = dextratype(lsym, ot, t, 0)
1344
1345                         break
1346                 }
1347
1348                 // ../../../../runtime/type.go:/ptrType
1349                 s1 := dtypesym(t.Elem())
1350
1351                 ot = dcommontype(lsym, t)
1352                 ot = dsymptr(lsym, ot, s1, 0)
1353                 ot = dextratype(lsym, ot, t, 0)
1354
1355         // ../../../../runtime/type.go:/structType
1356         // for security, only the exported fields.
1357         case TSTRUCT:
1358                 fields := t.Fields().Slice()
1359
1360                 // omitFieldForAwfulBoringCryptoKludge reports whether
1361                 // the field t should be omitted from the reflect data.
1362                 // In the crypto/... packages we omit an unexported field
1363                 // named "boring", to keep from breaking client code that
1364                 // expects rsa.PublicKey etc to have only public fields.
1365                 // As the name suggests, this is an awful kludge, but it is
1366                 // limited to the dev.boringcrypto branch and avoids
1367                 // much more invasive effects elsewhere.
1368                 omitFieldForAwfulBoringCryptoKludge := func(t *types.Field) bool {
1369                         if t.Sym == nil || t.Sym.Name != "boring" || t.Sym.Pkg == nil {
1370                                 return false
1371                         }
1372                         path := t.Sym.Pkg.Path
1373                         if t.Sym.Pkg == localpkg {
1374                                 path = myimportpath
1375                         }
1376                         return strings.HasPrefix(path, "crypto/")
1377                 }
1378                 newFields := fields[:0:0]
1379                 for _, t1 := range fields {
1380                         if !omitFieldForAwfulBoringCryptoKludge(t1) {
1381                                 newFields = append(newFields, t1)
1382                         }
1383                 }
1384                 fields = newFields
1385
1386                 for _, t1 := range fields {
1387                         dtypesym(t1.Type)
1388                 }
1389
1390                 // All non-exported struct field names within a struct
1391                 // type must originate from a single package. By
1392                 // identifying and recording that package within the
1393                 // struct type descriptor, we can omit that
1394                 // information from the field descriptors.
1395                 var spkg *types.Pkg
1396                 for _, f := range fields {
1397                         if !types.IsExported(f.Sym.Name) {
1398                                 spkg = f.Sym.Pkg
1399                                 break
1400                         }
1401                 }
1402
1403                 ot = dcommontype(lsym, t)
1404                 ot = dgopkgpath(lsym, ot, spkg)
1405                 ot = dsymptr(lsym, ot, lsym, ot+3*Widthptr+uncommonSize(t))
1406                 ot = duintptr(lsym, ot, uint64(len(fields)))
1407                 ot = duintptr(lsym, ot, uint64(len(fields)))
1408
1409                 dataAdd := len(fields) * structfieldSize()
1410                 ot = dextratype(lsym, ot, t, dataAdd)
1411
1412                 for _, f := range fields {
1413                         // ../../../../runtime/type.go:/structField
1414                         ot = dnameField(lsym, ot, spkg, f)
1415                         ot = dsymptr(lsym, ot, dtypesym(f.Type), 0)
1416                         offsetAnon := uint64(f.Offset) << 1
1417                         if offsetAnon>>1 != uint64(f.Offset) {
1418                                 Fatalf("%v: bad field offset for %s", t, f.Sym.Name)
1419                         }
1420                         if f.Embedded != 0 {
1421                                 offsetAnon |= 1
1422                         }
1423                         ot = duintptr(lsym, ot, offsetAnon)
1424                 }
1425         }
1426
1427         ot = dextratypeData(lsym, ot, t)
1428         ggloblsym(lsym, int32(ot), int16(dupok|obj.RODATA))
1429
1430         // The linker will leave a table of all the typelinks for
1431         // types in the binary, so the runtime can find them.
1432         //
1433         // When buildmode=shared, all types are in typelinks so the
1434         // runtime can deduplicate type pointers.
1435         keep := Ctxt.Flag_dynlink
1436         if !keep && t.Sym == nil {
1437                 // For an unnamed type, we only need the link if the type can
1438                 // be created at run time by reflect.PtrTo and similar
1439                 // functions. If the type exists in the program, those
1440                 // functions must return the existing type structure rather
1441                 // than creating a new one.
1442                 switch t.Etype {
1443                 case TPTR, TARRAY, TCHAN, TFUNC, TMAP, TSLICE, TSTRUCT:
1444                         keep = true
1445                 }
1446         }
1447         // Do not put Noalg types in typelinks.  See issue #22605.
1448         if typeHasNoAlg(t) {
1449                 keep = false
1450         }
1451         lsym.Set(obj.AttrMakeTypelink, keep)
1452
1453         return lsym
1454 }
1455
1456 // ifaceMethodOffset returns the offset of the i-th method in the interface
1457 // type descriptor, ityp.
1458 func ifaceMethodOffset(ityp *types.Type, i int64) int64 {
1459         // interface type descriptor layout is struct {
1460         //   _type        // commonSize
1461         //   pkgpath      // 1 word
1462         //   []imethod    // 3 words (pointing to [...]imethod below)
1463         //   uncommontype // uncommonSize
1464         //   [...]imethod
1465         // }
1466         // The size of imethod is 8.
1467         return int64(commonSize()+4*Widthptr+uncommonSize(ityp)) + i*8
1468 }
1469
1470 // for each itabEntry, gather the methods on
1471 // the concrete type that implement the interface
1472 func peekitabs() {
1473         for i := range itabs {
1474                 tab := &itabs[i]
1475                 methods := genfun(tab.t, tab.itype)
1476                 if len(methods) == 0 {
1477                         continue
1478                 }
1479                 tab.entries = methods
1480         }
1481 }
1482
1483 // for the given concrete type and interface
1484 // type, return the (sorted) set of methods
1485 // on the concrete type that implement the interface
1486 func genfun(t, it *types.Type) []*obj.LSym {
1487         if t == nil || it == nil {
1488                 return nil
1489         }
1490         sigs := imethods(it)
1491         methods := methods(t)
1492         out := make([]*obj.LSym, 0, len(sigs))
1493         // TODO(mdempsky): Short circuit before calling methods(t)?
1494         // See discussion on CL 105039.
1495         if len(sigs) == 0 {
1496                 return nil
1497         }
1498
1499         // both sigs and methods are sorted by name,
1500         // so we can find the intersect in a single pass
1501         for _, m := range methods {
1502                 if m.name == sigs[0].name {
1503                         out = append(out, m.isym.Linksym())
1504                         sigs = sigs[1:]
1505                         if len(sigs) == 0 {
1506                                 break
1507                         }
1508                 }
1509         }
1510
1511         if len(sigs) != 0 {
1512                 Fatalf("incomplete itab")
1513         }
1514
1515         return out
1516 }
1517
1518 // itabsym uses the information gathered in
1519 // peekitabs to de-virtualize interface methods.
1520 // Since this is called by the SSA backend, it shouldn't
1521 // generate additional Nodes, Syms, etc.
1522 func itabsym(it *obj.LSym, offset int64) *obj.LSym {
1523         var syms []*obj.LSym
1524         if it == nil {
1525                 return nil
1526         }
1527
1528         for i := range itabs {
1529                 e := &itabs[i]
1530                 if e.lsym == it {
1531                         syms = e.entries
1532                         break
1533                 }
1534         }
1535         if syms == nil {
1536                 return nil
1537         }
1538
1539         // keep this arithmetic in sync with *itab layout
1540         methodnum := int((offset - 2*int64(Widthptr) - 8) / int64(Widthptr))
1541         if methodnum >= len(syms) {
1542                 return nil
1543         }
1544         return syms[methodnum]
1545 }
1546
1547 // addsignat ensures that a runtime type descriptor is emitted for t.
1548 func addsignat(t *types.Type) {
1549         if _, ok := signatset[t]; !ok {
1550                 signatset[t] = struct{}{}
1551                 signatslice = append(signatslice, t)
1552         }
1553 }
1554
1555 func addsignats(dcls []*Node) {
1556         // copy types from dcl list to signatset
1557         for _, n := range dcls {
1558                 if n.Op == OTYPE {
1559                         addsignat(n.Type)
1560                 }
1561         }
1562 }
1563
1564 func dumpsignats() {
1565         // Process signatset. Use a loop, as dtypesym adds
1566         // entries to signatset while it is being processed.
1567         signats := make([]typeAndStr, len(signatslice))
1568         for len(signatslice) > 0 {
1569                 signats = signats[:0]
1570                 // Transfer entries to a slice and sort, for reproducible builds.
1571                 for _, t := range signatslice {
1572                         signats = append(signats, typeAndStr{t: t, short: typesymname(t), regular: t.String()})
1573                         delete(signatset, t)
1574                 }
1575                 signatslice = signatslice[:0]
1576                 sort.Sort(typesByString(signats))
1577                 for _, ts := range signats {
1578                         t := ts.t
1579                         dtypesym(t)
1580                         if t.Sym != nil {
1581                                 dtypesym(types.NewPtr(t))
1582                         }
1583                 }
1584         }
1585 }
1586
1587 func dumptabs() {
1588         // process itabs
1589         for _, i := range itabs {
1590                 // dump empty itab symbol into i.sym
1591                 // type itab struct {
1592                 //   inter  *interfacetype
1593                 //   _type  *_type
1594                 //   hash   uint32
1595                 //   _      [4]byte
1596                 //   fun    [1]uintptr // variable sized
1597                 // }
1598                 o := dsymptr(i.lsym, 0, dtypesym(i.itype), 0)
1599                 o = dsymptr(i.lsym, o, dtypesym(i.t), 0)
1600                 o = duint32(i.lsym, o, typehash(i.t)) // copy of type hash
1601                 o += 4                                // skip unused field
1602                 for _, fn := range genfun(i.t, i.itype) {
1603                         o = dsymptr(i.lsym, o, fn, 0) // method pointer for each method
1604                 }
1605                 // Nothing writes static itabs, so they are read only.
1606                 ggloblsym(i.lsym, int32(o), int16(obj.DUPOK|obj.RODATA))
1607                 i.lsym.Set(obj.AttrContentAddressable, true)
1608         }
1609
1610         // process ptabs
1611         if localpkg.Name == "main" && len(ptabs) > 0 {
1612                 ot := 0
1613                 s := Ctxt.Lookup("go.plugin.tabs")
1614                 for _, p := range ptabs {
1615                         // Dump ptab symbol into go.pluginsym package.
1616                         //
1617                         // type ptab struct {
1618                         //      name nameOff
1619                         //      typ  typeOff // pointer to symbol
1620                         // }
1621                         nsym := dname(p.s.Name, "", nil, true)
1622                         ot = dsymptrOff(s, ot, nsym)
1623                         ot = dsymptrOff(s, ot, dtypesym(p.t))
1624                 }
1625                 ggloblsym(s, int32(ot), int16(obj.RODATA))
1626
1627                 ot = 0
1628                 s = Ctxt.Lookup("go.plugin.exports")
1629                 for _, p := range ptabs {
1630                         ot = dsymptr(s, ot, p.s.Linksym(), 0)
1631                 }
1632                 ggloblsym(s, int32(ot), int16(obj.RODATA))
1633         }
1634 }
1635
1636 func dumpimportstrings() {
1637         // generate import strings for imported packages
1638         for _, p := range types.ImportedPkgList() {
1639                 dimportpath(p)
1640         }
1641 }
1642
1643 func dumpbasictypes() {
1644         // do basic types if compiling package runtime.
1645         // they have to be in at least one package,
1646         // and runtime is always loaded implicitly,
1647         // so this is as good as any.
1648         // another possible choice would be package main,
1649         // but using runtime means fewer copies in object files.
1650         if myimportpath == "runtime" {
1651                 for i := types.EType(1); i <= TBOOL; i++ {
1652                         dtypesym(types.NewPtr(types.Types[i]))
1653                 }
1654                 dtypesym(types.NewPtr(types.Types[TSTRING]))
1655                 dtypesym(types.NewPtr(types.Types[TUNSAFEPTR]))
1656
1657                 // emit type structs for error and func(error) string.
1658                 // The latter is the type of an auto-generated wrapper.
1659                 dtypesym(types.NewPtr(types.Errortype))
1660
1661                 dtypesym(functype(nil, []*Node{anonfield(types.Errortype)}, []*Node{anonfield(types.Types[TSTRING])}))
1662
1663                 // add paths for runtime and main, which 6l imports implicitly.
1664                 dimportpath(Runtimepkg)
1665
1666                 if flag_race {
1667                         dimportpath(racepkg)
1668                 }
1669                 if flag_msan {
1670                         dimportpath(msanpkg)
1671                 }
1672                 dimportpath(types.NewPkg("main", ""))
1673         }
1674 }
1675
1676 type typeAndStr struct {
1677         t       *types.Type
1678         short   string
1679         regular string
1680 }
1681
1682 type typesByString []typeAndStr
1683
1684 func (a typesByString) Len() int { return len(a) }
1685 func (a typesByString) Less(i, j int) bool {
1686         if a[i].short != a[j].short {
1687                 return a[i].short < a[j].short
1688         }
1689         // When the only difference between the types is whether
1690         // they refer to byte or uint8, such as **byte vs **uint8,
1691         // the types' ShortStrings can be identical.
1692         // To preserve deterministic sort ordering, sort these by String().
1693         if a[i].regular != a[j].regular {
1694                 return a[i].regular < a[j].regular
1695         }
1696         // Identical anonymous interfaces defined in different locations
1697         // will be equal for the above checks, but different in DWARF output.
1698         // Sort by source position to ensure deterministic order.
1699         // See issues 27013 and 30202.
1700         if a[i].t.Etype == types.TINTER && a[i].t.Methods().Len() > 0 {
1701                 return a[i].t.Methods().Index(0).Pos.Before(a[j].t.Methods().Index(0).Pos)
1702         }
1703         return false
1704 }
1705 func (a typesByString) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
1706
1707 // maxPtrmaskBytes is the maximum length of a GC ptrmask bitmap,
1708 // which holds 1-bit entries describing where pointers are in a given type.
1709 // Above this length, the GC information is recorded as a GC program,
1710 // which can express repetition compactly. In either form, the
1711 // information is used by the runtime to initialize the heap bitmap,
1712 // and for large types (like 128 or more words), they are roughly the
1713 // same speed. GC programs are never much larger and often more
1714 // compact. (If large arrays are involved, they can be arbitrarily
1715 // more compact.)
1716 //
1717 // The cutoff must be large enough that any allocation large enough to
1718 // use a GC program is large enough that it does not share heap bitmap
1719 // bytes with any other objects, allowing the GC program execution to
1720 // assume an aligned start and not use atomic operations. In the current
1721 // runtime, this means all malloc size classes larger than the cutoff must
1722 // be multiples of four words. On 32-bit systems that's 16 bytes, and
1723 // all size classes >= 16 bytes are 16-byte aligned, so no real constraint.
1724 // On 64-bit systems, that's 32 bytes, and 32-byte alignment is guaranteed
1725 // for size classes >= 256 bytes. On a 64-bit system, 256 bytes allocated
1726 // is 32 pointers, the bits for which fit in 4 bytes. So maxPtrmaskBytes
1727 // must be >= 4.
1728 //
1729 // We used to use 16 because the GC programs do have some constant overhead
1730 // to get started, and processing 128 pointers seems to be enough to
1731 // amortize that overhead well.
1732 //
1733 // To make sure that the runtime's chansend can call typeBitsBulkBarrier,
1734 // we raised the limit to 2048, so that even 32-bit systems are guaranteed to
1735 // use bitmaps for objects up to 64 kB in size.
1736 //
1737 // Also known to reflect/type.go.
1738 //
1739 const maxPtrmaskBytes = 2048
1740
1741 // dgcsym emits and returns a data symbol containing GC information for type t,
1742 // along with a boolean reporting whether the UseGCProg bit should be set in
1743 // the type kind, and the ptrdata field to record in the reflect type information.
1744 func dgcsym(t *types.Type) (lsym *obj.LSym, useGCProg bool, ptrdata int64) {
1745         ptrdata = typeptrdata(t)
1746         if ptrdata/int64(Widthptr) <= maxPtrmaskBytes*8 {
1747                 lsym = dgcptrmask(t)
1748                 return
1749         }
1750
1751         useGCProg = true
1752         lsym, ptrdata = dgcprog(t)
1753         return
1754 }
1755
1756 // dgcptrmask emits and returns the symbol containing a pointer mask for type t.
1757 func dgcptrmask(t *types.Type) *obj.LSym {
1758         ptrmask := make([]byte, (typeptrdata(t)/int64(Widthptr)+7)/8)
1759         fillptrmask(t, ptrmask)
1760         p := fmt.Sprintf("gcbits.%x", ptrmask)
1761
1762         sym := Runtimepkg.Lookup(p)
1763         lsym := sym.Linksym()
1764         if !sym.Uniq() {
1765                 sym.SetUniq(true)
1766                 for i, x := range ptrmask {
1767                         duint8(lsym, i, x)
1768                 }
1769                 ggloblsym(lsym, int32(len(ptrmask)), obj.DUPOK|obj.RODATA|obj.LOCAL)
1770                 lsym.Set(obj.AttrContentAddressable, true)
1771         }
1772         return lsym
1773 }
1774
1775 // fillptrmask fills in ptrmask with 1s corresponding to the
1776 // word offsets in t that hold pointers.
1777 // ptrmask is assumed to fit at least typeptrdata(t)/Widthptr bits.
1778 func fillptrmask(t *types.Type, ptrmask []byte) {
1779         for i := range ptrmask {
1780                 ptrmask[i] = 0
1781         }
1782         if !t.HasPointers() {
1783                 return
1784         }
1785
1786         vec := bvalloc(8 * int32(len(ptrmask)))
1787         onebitwalktype1(t, 0, vec)
1788
1789         nptr := typeptrdata(t) / int64(Widthptr)
1790         for i := int64(0); i < nptr; i++ {
1791                 if vec.Get(int32(i)) {
1792                         ptrmask[i/8] |= 1 << (uint(i) % 8)
1793                 }
1794         }
1795 }
1796
1797 // dgcprog emits and returns the symbol containing a GC program for type t
1798 // along with the size of the data described by the program (in the range [typeptrdata(t), t.Width]).
1799 // In practice, the size is typeptrdata(t) except for non-trivial arrays.
1800 // For non-trivial arrays, the program describes the full t.Width size.
1801 func dgcprog(t *types.Type) (*obj.LSym, int64) {
1802         dowidth(t)
1803         if t.Width == BADWIDTH {
1804                 Fatalf("dgcprog: %v badwidth", t)
1805         }
1806         lsym := typesymprefix(".gcprog", t).Linksym()
1807         var p GCProg
1808         p.init(lsym)
1809         p.emit(t, 0)
1810         offset := p.w.BitIndex() * int64(Widthptr)
1811         p.end()
1812         if ptrdata := typeptrdata(t); offset < ptrdata || offset > t.Width {
1813                 Fatalf("dgcprog: %v: offset=%d but ptrdata=%d size=%d", t, offset, ptrdata, t.Width)
1814         }
1815         return lsym, offset
1816 }
1817
1818 type GCProg struct {
1819         lsym   *obj.LSym
1820         symoff int
1821         w      gcprog.Writer
1822 }
1823
1824 var Debug_gcprog int // set by -d gcprog
1825
1826 func (p *GCProg) init(lsym *obj.LSym) {
1827         p.lsym = lsym
1828         p.symoff = 4 // first 4 bytes hold program length
1829         p.w.Init(p.writeByte)
1830         if Debug_gcprog > 0 {
1831                 fmt.Fprintf(os.Stderr, "compile: start GCProg for %v\n", lsym)
1832                 p.w.Debug(os.Stderr)
1833         }
1834 }
1835
1836 func (p *GCProg) writeByte(x byte) {
1837         p.symoff = duint8(p.lsym, p.symoff, x)
1838 }
1839
1840 func (p *GCProg) end() {
1841         p.w.End()
1842         duint32(p.lsym, 0, uint32(p.symoff-4))
1843         ggloblsym(p.lsym, int32(p.symoff), obj.DUPOK|obj.RODATA|obj.LOCAL)
1844         if Debug_gcprog > 0 {
1845                 fmt.Fprintf(os.Stderr, "compile: end GCProg for %v\n", p.lsym)
1846         }
1847 }
1848
1849 func (p *GCProg) emit(t *types.Type, offset int64) {
1850         dowidth(t)
1851         if !t.HasPointers() {
1852                 return
1853         }
1854         if t.Width == int64(Widthptr) {
1855                 p.w.Ptr(offset / int64(Widthptr))
1856                 return
1857         }
1858         switch t.Etype {
1859         default:
1860                 Fatalf("GCProg.emit: unexpected type %v", t)
1861
1862         case TSTRING:
1863                 p.w.Ptr(offset / int64(Widthptr))
1864
1865         case TINTER:
1866                 // Note: the first word isn't a pointer. See comment in plive.go:onebitwalktype1.
1867                 p.w.Ptr(offset/int64(Widthptr) + 1)
1868
1869         case TSLICE:
1870                 p.w.Ptr(offset / int64(Widthptr))
1871
1872         case TARRAY:
1873                 if t.NumElem() == 0 {
1874                         // should have been handled by haspointers check above
1875                         Fatalf("GCProg.emit: empty array")
1876                 }
1877
1878                 // Flatten array-of-array-of-array to just a big array by multiplying counts.
1879                 count := t.NumElem()
1880                 elem := t.Elem()
1881                 for elem.IsArray() {
1882                         count *= elem.NumElem()
1883                         elem = elem.Elem()
1884                 }
1885
1886                 if !p.w.ShouldRepeat(elem.Width/int64(Widthptr), count) {
1887                         // Cheaper to just emit the bits.
1888                         for i := int64(0); i < count; i++ {
1889                                 p.emit(elem, offset+i*elem.Width)
1890                         }
1891                         return
1892                 }
1893                 p.emit(elem, offset)
1894                 p.w.ZeroUntil((offset + elem.Width) / int64(Widthptr))
1895                 p.w.Repeat(elem.Width/int64(Widthptr), count-1)
1896
1897         case TSTRUCT:
1898                 for _, t1 := range t.Fields().Slice() {
1899                         p.emit(t1.Type, offset+t1.Offset)
1900                 }
1901         }
1902 }
1903
1904 // zeroaddr returns the address of a symbol with at least
1905 // size bytes of zeros.
1906 func zeroaddr(size int64) *Node {
1907         if size >= 1<<31 {
1908                 Fatalf("map elem too big %d", size)
1909         }
1910         if zerosize < size {
1911                 zerosize = size
1912         }
1913         s := mappkg.Lookup("zero")
1914         if s.Def == nil {
1915                 x := newname(s)
1916                 x.Type = types.Types[TUINT8]
1917                 x.SetClass(PEXTERN)
1918                 x.SetTypecheck(1)
1919                 s.Def = asTypesNode(x)
1920         }
1921         z := nod(OADDR, asNode(s.Def), nil)
1922         z.Type = types.NewPtr(types.Types[TUINT8])
1923         z.SetTypecheck(1)
1924         return z
1925 }