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