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/internal/gcprog"
   9         "cmd/internal/obj"
  10         "fmt"
  11         "os"
  12         "sort"
  13 )
  14
  15 // runtime interface and reflection data structures
  16 var signatlist *NodeList
  17
  18 // byMethodNameAndPackagePath sorts method signatures by name, then package path.
  19 type byMethodNameAndPackagePath []*Sig
  20
  21 func (x byMethodNameAndPackagePath) Len() int      { return len(x) }
  22 func (x byMethodNameAndPackagePath) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
  23 func (x byMethodNameAndPackagePath) Less(i, j int) bool {
  24         return siglt(x[i], x[j])
  25 }
  26
  27 // siglt reports whether a < b
  28 func siglt(a, b *Sig) bool {
  29         if a.name != b.name {
  30                 return a.name < b.name
  31         }
  32         if a.pkg == b.pkg {
  33                 return false
  34         }
  35         if a.pkg == nil {
  36                 return true
  37         }
  38         if b.pkg == nil {
  39                 return false
  40         }
  41         return a.pkg.Path < b.pkg.Path
  42 }
  43
  44 // Builds a type representing a Bucket structure for
  45 // the given map type.  This type is not visible to users -
  46 // we include only enough information to generate a correct GC
  47 // program for it.
  48 // Make sure this stays in sync with ../../../../runtime/hashmap.go!
  49 const (
  50         BUCKETSIZE = 8
  51         MAXKEYSIZE = 128
  52         MAXVALSIZE = 128
  53 )
  54
  55 func makefield(name string, t *Type) *Type {
  56         f := typ(TFIELD)
  57         f.Type = t
  58         f.Sym = nopkg.Lookup(name)
  59         return f
  60 }
  61
  62 func mapbucket(t *Type) *Type {
  63         if t.Bucket != nil {
  64                 return t.Bucket
  65         }
  66
  67         bucket := typ(TSTRUCT)
  68         keytype := t.Down
  69         valtype := t.Type
  70         dowidth(keytype)
  71         dowidth(valtype)
  72         if keytype.Width > MAXKEYSIZE {
  73                 keytype = Ptrto(keytype)
  74         }
  75         if valtype.Width > MAXVALSIZE {
  76                 valtype = Ptrto(valtype)
  77         }
  78
  79         // The first field is: uint8 topbits[BUCKETSIZE].
  80         arr := typ(TARRAY)
  81
  82         arr.Type = Types[TUINT8]
  83         arr.Bound = BUCKETSIZE
  84         field := make([]*Type, 0, 5)
  85         field = append(field, makefield("topbits", arr))
  86         arr = typ(TARRAY)
  87         arr.Type = keytype
  88         arr.Bound = BUCKETSIZE
  89         field = append(field, makefield("keys", arr))
  90         arr = typ(TARRAY)
  91         arr.Type = valtype
  92         arr.Bound = BUCKETSIZE
  93         field = append(field, makefield("values", arr))
  94
  95         // Make sure the overflow pointer is the last memory in the struct,
  96         // because the runtime assumes it can use size-ptrSize as the
  97         // offset of the overflow pointer. We double-check that property
  98         // below once the offsets and size are computed.
  99         //
 100         // BUCKETSIZE is 8, so the struct is aligned to 64 bits to this point.
 101         // On 32-bit systems, the max alignment is 32-bit, and the
 102         // overflow pointer will add another 32-bit field, and the struct
 103         // will end with no padding.
 104         // On 64-bit systems, the max alignment is 64-bit, and the
 105         // overflow pointer will add another 64-bit field, and the struct
 106         // will end with no padding.
 107         // On nacl/amd64p32, however, the max alignment is 64-bit,
 108         // but the overflow pointer will add only a 32-bit field,
 109         // so if the struct needs 64-bit padding (because a key or value does)
 110         // then it would end with an extra 32-bit padding field.
 111         // Preempt that by emitting the padding here.
 112         if int(t.Type.Align) > Widthptr || int(t.Down.Align) > Widthptr {
 113                 field = append(field, makefield("pad", Types[TUINTPTR]))
 114         }
 115
 116         // If keys and values 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/hashmap.go.
 122         otyp := Ptrto(bucket)
 123         if !haspointers(t.Type) && !haspointers(t.Down) && t.Type.Width <= MAXKEYSIZE && t.Down.Width <= MAXVALSIZE {
 124                 otyp = Types[TUINTPTR]
 125         }
 126         ovf := makefield("overflow", otyp)
 127         field = append(field, ovf)
 128
 129         // link up fields
 130         bucket.Noalg = true
 131         bucket.Local = t.Local
 132         bucket.Type = field[0]
 133         for n := int32(0); n < int32(len(field)-1); n++ {
 134                 field[n].Down = field[n+1]
 135         }
 136         field[len(field)-1].Down = nil
 137         dowidth(bucket)
 138
 139         // Double-check that overflow field is final memory in struct,
 140         // with no padding at end. See comment above.
 141         if ovf.Width != bucket.Width-int64(Widthptr) {
 142                 Yyerror("bad math in mapbucket for %v", t)
 143         }
 144
 145         t.Bucket = bucket
 146
 147         bucket.Map = t
 148         return bucket
 149 }
 150
 151 // Builds a type representing a Hmap structure for the given map type.
 152 // Make sure this stays in sync with ../../../../runtime/hashmap.go!
 153 func hmap(t *Type) *Type {
 154         if t.Hmap != nil {
 155                 return t.Hmap
 156         }
 157
 158         bucket := mapbucket(t)
 159         var field [8]*Type
 160         field[0] = makefield("count", Types[TINT])
 161         field[1] = makefield("flags", Types[TUINT8])
 162         field[2] = makefield("B", Types[TUINT8])
 163         field[3] = makefield("hash0", Types[TUINT32])
 164         field[4] = makefield("buckets", Ptrto(bucket))
 165         field[5] = makefield("oldbuckets", Ptrto(bucket))
 166         field[6] = makefield("nevacuate", Types[TUINTPTR])
 167         field[7] = makefield("overflow", Types[TUNSAFEPTR])
 168
 169         h := typ(TSTRUCT)
 170         h.Noalg = true
 171         h.Local = t.Local
 172         h.Type = field[0]
 173         for n := int32(0); n < int32(len(field)-1); n++ {
 174                 field[n].Down = field[n+1]
 175         }
 176         field[len(field)-1].Down = nil
 177         dowidth(h)
 178         t.Hmap = h
 179         h.Map = t
 180         return h
 181 }
 182
 183 func hiter(t *Type) *Type {
 184         if t.Hiter != nil {
 185                 return t.Hiter
 186         }
 187
 188         // build a struct:
 189         // hiter {
 190         //    key *Key
 191         //    val *Value
 192         //    t *MapType
 193         //    h *Hmap
 194         //    buckets *Bucket
 195         //    bptr *Bucket
 196         //    overflow0 unsafe.Pointer
 197         //    overflow1 unsafe.Pointer
 198         //    startBucket uintptr
 199         //    stuff uintptr
 200         //    bucket uintptr
 201         //    checkBucket uintptr
 202         // }
 203         // must match ../../../../runtime/hashmap.go:hiter.
 204         var field [12]*Type
 205         field[0] = makefield("key", Ptrto(t.Down))
 206
 207         field[1] = makefield("val", Ptrto(t.Type))
 208         field[2] = makefield("t", Ptrto(Types[TUINT8]))
 209         field[3] = makefield("h", Ptrto(hmap(t)))
 210         field[4] = makefield("buckets", Ptrto(mapbucket(t)))
 211         field[5] = makefield("bptr", Ptrto(mapbucket(t)))
 212         field[6] = makefield("overflow0", Types[TUNSAFEPTR])
 213         field[7] = makefield("overflow1", Types[TUNSAFEPTR])
 214         field[8] = makefield("startBucket", Types[TUINTPTR])
 215         field[9] = makefield("stuff", Types[TUINTPTR]) // offset+wrapped+B+I
 216         field[10] = makefield("bucket", Types[TUINTPTR])
 217         field[11] = makefield("checkBucket", Types[TUINTPTR])
 218
 219         // build iterator struct holding the above fields
 220         i := typ(TSTRUCT)
 221
 222         i.Noalg = true
 223         i.Type = field[0]
 224         for n := int32(0); n < int32(len(field)-1); n++ {
 225                 field[n].Down = field[n+1]
 226         }
 227         field[len(field)-1].Down = nil
 228         dowidth(i)
 229         if i.Width != int64(12*Widthptr) {
 230                 Yyerror("hash_iter size not correct %d %d", i.Width, 12*Widthptr)
 231         }
 232         t.Hiter = i
 233         i.Map = t
 234         return i
 235 }
 236
 237 // f is method type, with receiver.
 238 // return function type, receiver as first argument (or not).
 239 func methodfunc(f *Type, receiver *Type) *Type {
 240         var in *NodeList
 241         if receiver != nil {
 242                 d := Nod(ODCLFIELD, nil, nil)
 243                 d.Type = receiver
 244                 in = list(in, d)
 245         }
 246
 247         var d *Node
 248         for t := getinargx(f).Type; t != nil; t = t.Down {
 249                 d = Nod(ODCLFIELD, nil, nil)
 250                 d.Type = t.Type
 251                 d.Isddd = t.Isddd
 252                 in = list(in, d)
 253         }
 254
 255         var out *NodeList
 256         for t := getoutargx(f).Type; t != nil; t = t.Down {
 257                 d = Nod(ODCLFIELD, nil, nil)
 258                 d.Type = t.Type
 259                 out = list(out, d)
 260         }
 261
 262         t := functype(nil, in, out)
 263         if f.Nname != nil {
 264                 // Link to name of original method function.
 265                 t.Nname = f.Nname
 266         }
 267
 268         return t
 269 }
 270
 271 // methods returns the methods of the non-interface type t, sorted by name.
 272 // Generates stub functions as needed.
 273 func methods(t *Type) []*Sig {
 274         // method type
 275         mt := methtype(t, 0)
 276
 277         if mt == nil {
 278                 return nil
 279         }
 280         expandmeth(mt)
 281
 282         // type stored in interface word
 283         it := t
 284
 285         if !isdirectiface(it) {
 286                 it = Ptrto(t)
 287         }
 288
 289         // make list of methods for t,
 290         // generating code if necessary.
 291         var ms []*Sig
 292         for f := mt.Xmethod; f != nil; f = f.Down {
 293                 if f.Etype != TFIELD {
 294                         Fatalf("methods: not field %v", f)
 295                 }
 296                 if f.Type.Etype != TFUNC || f.Type.Thistuple == 0 {
 297                         Fatalf("non-method on %v method %v %v\n", mt, f.Sym, f)
 298                 }
 299                 if getthisx(f.Type).Type == nil {
 300                         Fatalf("receiver with no type on %v method %v %v\n", mt, f.Sym, f)
 301                 }
 302                 if f.Nointerface {
 303                         continue
 304                 }
 305
 306                 method := f.Sym
 307                 if method == nil {
 308                         continue
 309                 }
 310
 311                 // get receiver type for this particular method.
 312                 // if pointer receiver but non-pointer t and
 313                 // this is not an embedded pointer inside a struct,
 314                 // method does not apply.
 315                 this := getthisx(f.Type).Type.Type
 316
 317                 if Isptr[this.Etype] && this.Type == t {
 318                         continue
 319                 }
 320                 if Isptr[this.Etype] && !Isptr[t.Etype] && f.Embedded != 2 && !isifacemethod(f.Type) {
 321                         continue
 322                 }
 323
 324                 var sig Sig
 325                 ms = append(ms, &sig)
 326
 327                 sig.name = method.Name
 328                 if !exportname(method.Name) {
 329                         if method.Pkg == nil {
 330                                 Fatalf("methods: missing package")
 331                         }
 332                         sig.pkg = method.Pkg
 333                 }
 334
 335                 sig.isym = methodsym(method, it, 1)
 336                 sig.tsym = methodsym(method, t, 0)
 337                 sig.type_ = methodfunc(f.Type, t)
 338                 sig.mtype = methodfunc(f.Type, nil)
 339
 340                 if sig.isym.Flags&SymSiggen == 0 {
 341                         sig.isym.Flags |= SymSiggen
 342                         if !Eqtype(this, it) || this.Width < Types[Tptr].Width {
 343                                 compiling_wrappers = 1
 344                                 genwrapper(it, f, sig.isym, 1)
 345                                 compiling_wrappers = 0
 346                         }
 347                 }
 348
 349                 if sig.tsym.Flags&SymSiggen == 0 {
 350                         sig.tsym.Flags |= SymSiggen
 351                         if !Eqtype(this, t) {
 352                                 compiling_wrappers = 1
 353                                 genwrapper(t, f, sig.tsym, 0)
 354                                 compiling_wrappers = 0
 355                         }
 356                 }
 357         }
 358
 359         sort.Sort(byMethodNameAndPackagePath(ms))
 360         return ms
 361 }
 362
 363 // imethods returns the methods of the interface type t, sorted by name.
 364 func imethods(t *Type) []*Sig {
 365         var methods []*Sig
 366         for f := t.Type; f != nil; f = f.Down {
 367                 if f.Etype != TFIELD {
 368                         Fatalf("imethods: not field")
 369                 }
 370                 if f.Type.Etype != TFUNC || f.Sym == nil {
 371                         continue
 372                 }
 373                 method := f.Sym
 374                 var sig = Sig{
 375                         name: method.Name,
 376                 }
 377                 if !exportname(method.Name) {
 378                         if method.Pkg == nil {
 379                                 Fatalf("imethods: missing package")
 380                         }
 381                         sig.pkg = method.Pkg
 382                 }
 383
 384                 sig.mtype = f.Type
 385                 sig.offset = 0
 386                 sig.type_ = methodfunc(f.Type, nil)
 387
 388                 if n := len(methods); n > 0 {
 389                         last := methods[n-1]
 390                         if !(siglt(last, &sig)) {
 391                                 Fatalf("sigcmp vs sortinter %s %s", last.name, sig.name)
 392                         }
 393                 }
 394                 methods = append(methods, &sig)
 395
 396                 // Compiler can only refer to wrappers for non-blank methods.
 397                 if isblanksym(method) {
 398                         continue
 399                 }
 400
 401                 // NOTE(rsc): Perhaps an oversight that
 402                 // IfaceType.Method is not in the reflect data.
 403                 // Generate the method body, so that compiled
 404                 // code can refer to it.
 405                 isym := methodsym(method, t, 0)
 406
 407                 if isym.Flags&SymSiggen == 0 {
 408                         isym.Flags |= SymSiggen
 409                         genwrapper(t, f, isym, 0)
 410                 }
 411         }
 412
 413         return methods
 414 }
 415
 416 var dimportpath_gopkg *Pkg
 417
 418 func dimportpath(p *Pkg) {
 419         if p.Pathsym != nil {
 420                 return
 421         }
 422
 423         // If we are compiling the runtime package, there are two runtime packages around
 424         // -- localpkg and Runtimepkg.  We don't want to produce import path symbols for
 425         // both of them, so just produce one for localpkg.
 426         if myimportpath == "runtime" && p == Runtimepkg {
 427                 return
 428         }
 429
 430         if dimportpath_gopkg == nil {
 431                 dimportpath_gopkg = mkpkg("go")
 432                 dimportpath_gopkg.Name = "go"
 433         }
 434
 435         nam := "importpath." + p.Prefix + "."
 436
 437         n := Nod(ONAME, nil, nil)
 438         n.Sym = Pkglookup(nam, dimportpath_gopkg)
 439
 440         n.Class = PEXTERN
 441         n.Xoffset = 0
 442         p.Pathsym = n.Sym
 443
 444         if p == localpkg {
 445                 // Note: myimportpath != "", or else dgopkgpath won't call dimportpath.
 446                 gdatastring(n, myimportpath)
 447         } else {
 448                 gdatastring(n, p.Path)
 449         }
 450         ggloblsym(n.Sym, int32(Types[TSTRING].Width), obj.DUPOK|obj.RODATA)
 451 }
 452
 453 func dgopkgpath(s *Sym, ot int, pkg *Pkg) int {
 454         if pkg == nil {
 455                 return dgostringptr(s, ot, "")
 456         }
 457
 458         if pkg == localpkg && myimportpath == "" {
 459                 // If we don't know the full path of the package being compiled (i.e. -p
 460                 // was not passed on the compiler command line), emit reference to
 461                 // go.importpath.""., which 6l will rewrite using the correct import path.
 462                 // Every package that imports this one directly defines the symbol.
 463                 var ns *Sym
 464
 465                 if ns == nil {
 466                         ns = Pkglookup("importpath.\"\".", mkpkg("go"))
 467                 }
 468                 return dsymptr(s, ot, ns, 0)
 469         }
 470
 471         dimportpath(pkg)
 472         return dsymptr(s, ot, pkg.Pathsym, 0)
 473 }
 474
 475 // uncommonType
 476 // ../../../../runtime/type.go:/uncommonType
 477 func dextratype(sym *Sym, off int, t *Type, ptroff int) int {
 478         m := methods(t)
 479         if t.Sym == nil && len(m) == 0 {
 480                 return off
 481         }
 482
 483         // fill in *extraType pointer in header
 484         off = int(Rnd(int64(off), int64(Widthptr)))
 485
 486         dsymptr(sym, ptroff, sym, off)
 487
 488         for _, a := range m {
 489                 dtypesym(a.type_)
 490         }
 491
 492         ot := off
 493         s := sym
 494         if t.Sym != nil && t != Types[t.Etype] && t != errortype {
 495                 ot = dgopkgpath(s, ot, t.Sym.Pkg)
 496         } else {
 497                 ot = dgostringptr(s, ot, "")
 498         }
 499
 500         // slice header
 501         ot = dsymptr(s, ot, s, ot+Widthptr+2*Widthint)
 502
 503         n := len(m)
 504         ot = duintxx(s, ot, uint64(n), Widthint)
 505         ot = duintxx(s, ot, uint64(n), Widthint)
 506
 507         // methods
 508         for _, a := range m {
 509                 // method
 510                 // ../../../../runtime/type.go:/method
 511                 ot = dgostringptr(s, ot, a.name)
 512
 513                 ot = dgopkgpath(s, ot, a.pkg)
 514                 ot = dsymptr(s, ot, dtypesym(a.mtype), 0)
 515                 ot = dsymptr(s, ot, dtypesym(a.type_), 0)
 516                 if a.isym != nil {
 517                         ot = dsymptr(s, ot, a.isym, 0)
 518                 } else {
 519                         ot = duintptr(s, ot, 0)
 520                 }
 521                 if a.tsym != nil {
 522                         ot = dsymptr(s, ot, a.tsym, 0)
 523                 } else {
 524                         ot = duintptr(s, ot, 0)
 525                 }
 526         }
 527
 528         return ot
 529 }
 530
 531 var kinds = []int{
 532         TINT:        obj.KindInt,
 533         TUINT:       obj.KindUint,
 534         TINT8:       obj.KindInt8,
 535         TUINT8:      obj.KindUint8,
 536         TINT16:      obj.KindInt16,
 537         TUINT16:     obj.KindUint16,
 538         TINT32:      obj.KindInt32,
 539         TUINT32:     obj.KindUint32,
 540         TINT64:      obj.KindInt64,
 541         TUINT64:     obj.KindUint64,
 542         TUINTPTR:    obj.KindUintptr,
 543         TFLOAT32:    obj.KindFloat32,
 544         TFLOAT64:    obj.KindFloat64,
 545         TBOOL:       obj.KindBool,
 546         TSTRING:     obj.KindString,
 547         TPTR32:      obj.KindPtr,
 548         TPTR64:      obj.KindPtr,
 549         TSTRUCT:     obj.KindStruct,
 550         TINTER:      obj.KindInterface,
 551         TCHAN:       obj.KindChan,
 552         TMAP:        obj.KindMap,
 553         TARRAY:      obj.KindArray,
 554         TFUNC:       obj.KindFunc,
 555         TCOMPLEX64:  obj.KindComplex64,
 556         TCOMPLEX128: obj.KindComplex128,
 557         TUNSAFEPTR:  obj.KindUnsafePointer,
 558 }
 559
 560 func haspointers(t *Type) bool {
 561         if t.Haspointers != 0 {
 562                 return t.Haspointers-1 != 0
 563         }
 564
 565         var ret bool
 566         switch t.Etype {
 567         case TINT,
 568                 TUINT,
 569                 TINT8,
 570                 TUINT8,
 571                 TINT16,
 572                 TUINT16,
 573                 TINT32,
 574                 TUINT32,
 575                 TINT64,
 576                 TUINT64,
 577                 TUINTPTR,
 578                 TFLOAT32,
 579                 TFLOAT64,
 580                 TCOMPLEX64,
 581                 TCOMPLEX128,
 582                 TBOOL:
 583                 ret = false
 584
 585         case TARRAY:
 586                 if t.Bound < 0 { // slice
 587                         ret = true
 588                         break
 589                 }
 590
 591                 if t.Bound == 0 { // empty array
 592                         ret = false
 593                         break
 594                 }
 595
 596                 ret = haspointers(t.Type)
 597
 598         case TSTRUCT:
 599                 ret = false
 600                 for t1 := t.Type; t1 != nil; t1 = t1.Down {
 601                         if haspointers(t1.Type) {
 602                                 ret = true
 603                                 break
 604                         }
 605                 }
 606
 607         case TSTRING,
 608                 TPTR32,
 609                 TPTR64,
 610                 TUNSAFEPTR,
 611                 TINTER,
 612                 TCHAN,
 613                 TMAP,
 614                 TFUNC:
 615                 fallthrough
 616         default:
 617                 ret = true
 618
 619         case TFIELD:
 620                 Fatalf("haspointers: unexpected type, %v", t)
 621         }
 622
 623         t.Haspointers = 1 + uint8(obj.Bool2int(ret))
 624         return ret
 625 }
 626
 627 // typeptrdata returns the length in bytes of the prefix of t
 628 // containing pointer data. Anything after this offset is scalar data.
 629 func typeptrdata(t *Type) int64 {
 630         if !haspointers(t) {
 631                 return 0
 632         }
 633
 634         switch t.Etype {
 635         case TPTR32,
 636                 TPTR64,
 637                 TUNSAFEPTR,
 638                 TFUNC,
 639                 TCHAN,
 640                 TMAP:
 641                 return int64(Widthptr)
 642
 643         case TSTRING:
 644                 // struct { byte *str; intgo len; }
 645                 return int64(Widthptr)
 646
 647         case TINTER:
 648                 // struct { Itab *tab;  void *data; } or
 649                 // struct { Type *type; void *data; }
 650                 return 2 * int64(Widthptr)
 651
 652         case TARRAY:
 653                 if Isslice(t) {
 654                         // struct { byte *array; uintgo len; uintgo cap; }
 655                         return int64(Widthptr)
 656                 }
 657                 // haspointers already eliminated t.Bound == 0.
 658                 return (t.Bound-1)*t.Type.Width + typeptrdata(t.Type)
 659
 660         case TSTRUCT:
 661                 // Find the last field that has pointers.
 662                 var lastPtrField *Type
 663                 for t1 := t.Type; t1 != nil; t1 = t1.Down {
 664                         if haspointers(t1.Type) {
 665                                 lastPtrField = t1
 666                         }
 667                 }
 668                 return lastPtrField.Width + typeptrdata(lastPtrField.Type)
 669
 670         default:
 671                 Fatalf("typeptrdata: unexpected type, %v", t)
 672                 return 0
 673         }
 674 }
 675
 676 // commonType
 677 // ../../runtime/type.go:/commonType
 678
 679 var dcommontype_algarray *Sym
 680
 681 func dcommontype(s *Sym, ot int, t *Type) int {
 682         if ot != 0 {
 683                 Fatalf("dcommontype %d", ot)
 684         }
 685
 686         sizeofAlg := 2 * Widthptr
 687         if dcommontype_algarray == nil {
 688                 dcommontype_algarray = Pkglookup("algarray", Runtimepkg)
 689         }
 690         dowidth(t)
 691         alg := algtype(t)
 692         var algsym *Sym
 693         if alg < 0 || alg == AMEM {
 694                 algsym = dalgsym(t)
 695         }
 696
 697         tptr := Ptrto(t)
 698         if !Isptr[t.Etype] && (t.Sym != nil || methods(tptr) != nil) {
 699                 sptr := dtypesym(tptr)
 700                 r := obj.Addrel(Linksym(s))
 701                 r.Off = 0
 702                 r.Siz = 0
 703                 r.Sym = sptr.Lsym
 704                 r.Type = obj.R_USETYPE
 705         }
 706
 707         gcsym, useGCProg, ptrdata := dgcsym(t)
 708
 709         // ../../../../reflect/type.go:/^type.rtype
 710         // actual type structure
 711         //      type rtype struct {
 712         //              size          uintptr
 713         //              ptrdata       uintptr
 714         //              hash          uint32
 715         //              _             uint8
 716         //              align         uint8
 717         //              fieldAlign    uint8
 718         //              kind          uint8
 719         //              alg           *typeAlg
 720         //              gcdata        *byte
 721         //              string        *string
 722         //              *uncommonType
 723         //      }
 724         ot = duintptr(s, ot, uint64(t.Width))
 725         ot = duintptr(s, ot, uint64(ptrdata))
 726
 727         ot = duint32(s, ot, typehash(t))
 728         ot = duint8(s, ot, 0) // unused
 729
 730         // runtime (and common sense) expects alignment to be a power of two.
 731         i := int(t.Align)
 732
 733         if i == 0 {
 734                 i = 1
 735         }
 736         if i&(i-1) != 0 {
 737                 Fatalf("invalid alignment %d for %v", t.Align, t)
 738         }
 739         ot = duint8(s, ot, t.Align) // align
 740         ot = duint8(s, ot, t.Align) // fieldAlign
 741
 742         i = kinds[t.Etype]
 743         if t.Etype == TARRAY && t.Bound < 0 {
 744                 i = obj.KindSlice
 745         }
 746         if !haspointers(t) {
 747                 i |= obj.KindNoPointers
 748         }
 749         if isdirectiface(t) {
 750                 i |= obj.KindDirectIface
 751         }
 752         if useGCProg {
 753                 i |= obj.KindGCProg
 754         }
 755         ot = duint8(s, ot, uint8(i)) // kind
 756         if algsym == nil {
 757                 ot = dsymptr(s, ot, dcommontype_algarray, alg*sizeofAlg)
 758         } else {
 759                 ot = dsymptr(s, ot, algsym, 0)
 760         }
 761         ot = dsymptr(s, ot, gcsym, 0) // gcdata
 762
 763         p := Tconv(t, obj.FmtLeft|obj.FmtUnsigned)
 764
 765         _, symdata := stringsym(p) // string
 766         ot = dsymptr(s, ot, symdata, 0)
 767         ot = duintxx(s, ot, uint64(len(p)), Widthint)
 768         //fmt.Printf("dcommontype: %s\n", p)
 769
 770         // skip pointer to extraType,
 771         // which follows the rest of this type structure.
 772         // caller will fill in if needed.
 773         // otherwise linker will assume 0.
 774         ot += Widthptr
 775
 776         return ot
 777 }
 778
 779 func typesym(t *Type) *Sym {
 780         return Pkglookup(Tconv(t, obj.FmtLeft), typepkg)
 781 }
 782
 783 func tracksym(t *Type) *Sym {
 784         return Pkglookup(Tconv(t.Outer, obj.FmtLeft)+"."+t.Sym.Name, trackpkg)
 785 }
 786
 787 func typelinksym(t *Type) *Sym {
 788         // %-uT is what the generated Type's string field says.
 789         // It uses (ambiguous) package names instead of import paths.
 790         // %-T is the complete, unambiguous type name.
 791         // We want the types to end up sorted by string field,
 792         // so use that first in the name, and then add :%-T to
 793         // disambiguate. We use a tab character as the separator to
 794         // ensure the types appear sorted by their string field. The
 795         // names are a little long but they are discarded by the linker
 796         // and do not end up in the symbol table of the final binary.
 797         p := Tconv(t, obj.FmtLeft|obj.FmtUnsigned) + "\t" + Tconv(t, obj.FmtLeft)
 798
 799         s := Pkglookup(p, typelinkpkg)
 800
 801         //print("typelinksym: %s -> %+S\n", p, s);
 802
 803         return s
 804 }
 805
 806 func typesymprefix(prefix string, t *Type) *Sym {
 807         p := prefix + "." + Tconv(t, obj.FmtLeft)
 808         s := Pkglookup(p, typepkg)
 809
 810         //print("algsym: %s -> %+S\n", p, s);
 811
 812         return s
 813 }
 814
 815 func typenamesym(t *Type) *Sym {
 816         if t == nil || (Isptr[t.Etype] && t.Type == nil) || isideal(t) {
 817                 Fatalf("typename %v", t)
 818         }
 819         s := typesym(t)
 820         if s.Def == nil {
 821                 n := Nod(ONAME, nil, nil)
 822                 n.Sym = s
 823                 n.Type = Types[TUINT8]
 824                 n.Addable = true
 825                 n.Ullman = 1
 826                 n.Class = PEXTERN
 827                 n.Xoffset = 0
 828                 n.Typecheck = 1
 829                 s.Def = n
 830
 831                 signatlist = list(signatlist, typenod(t))
 832         }
 833
 834         return s.Def.Sym
 835 }
 836
 837 func typename(t *Type) *Node {
 838         s := typenamesym(t)
 839         n := Nod(OADDR, s.Def, nil)
 840         n.Type = Ptrto(s.Def.Type)
 841         n.Addable = true
 842         n.Ullman = 2
 843         n.Typecheck = 1
 844         return n
 845 }
 846
 847 func weaktypesym(t *Type) *Sym {
 848         p := Tconv(t, obj.FmtLeft)
 849         s := Pkglookup(p, weaktypepkg)
 850
 851         //print("weaktypesym: %s -> %+S\n", p, s);
 852
 853         return s
 854 }
 855
 856 // isreflexive reports whether t has a reflexive equality operator.
 857 // That is, if x==x for all x of type t.
 858 func isreflexive(t *Type) bool {
 859         switch t.Etype {
 860         case TBOOL,
 861                 TINT,
 862                 TUINT,
 863                 TINT8,
 864                 TUINT8,
 865                 TINT16,
 866                 TUINT16,
 867                 TINT32,
 868                 TUINT32,
 869                 TINT64,
 870                 TUINT64,
 871                 TUINTPTR,
 872                 TPTR32,
 873                 TPTR64,
 874                 TUNSAFEPTR,
 875                 TSTRING,
 876                 TCHAN:
 877                 return true
 878
 879         case TFLOAT32,
 880                 TFLOAT64,
 881                 TCOMPLEX64,
 882                 TCOMPLEX128,
 883                 TINTER:
 884                 return false
 885
 886         case TARRAY:
 887                 if Isslice(t) {
 888                         Fatalf("slice can't be a map key: %v", t)
 889                 }
 890                 return isreflexive(t.Type)
 891
 892         case TSTRUCT:
 893                 for t1 := t.Type; t1 != nil; t1 = t1.Down {
 894                         if !isreflexive(t1.Type) {
 895                                 return false
 896                         }
 897                 }
 898                 return true
 899
 900         default:
 901                 Fatalf("bad type for map key: %v", t)
 902                 return false
 903         }
 904 }
 905
 906 // needkeyupdate reports whether map updates with t as a key
 907 // need the key to be updated.
 908 func needkeyupdate(t *Type) bool {
 909         switch t.Etype {
 910         case TBOOL,
 911                 TINT,
 912                 TUINT,
 913                 TINT8,
 914                 TUINT8,
 915                 TINT16,
 916                 TUINT16,
 917                 TINT32,
 918                 TUINT32,
 919                 TINT64,
 920                 TUINT64,
 921                 TUINTPTR,
 922                 TPTR32,
 923                 TPTR64,
 924                 TUNSAFEPTR,
 925                 TCHAN:
 926                 return false
 927
 928         case TFLOAT32, // floats can be +0/-0
 929                 TFLOAT64,
 930                 TCOMPLEX64,
 931                 TCOMPLEX128,
 932                 TINTER,
 933                 TSTRING: // strings might have smaller backing stores
 934                 return true
 935
 936         case TARRAY:
 937                 if Isslice(t) {
 938                         Fatalf("slice can't be a map key: %v", t)
 939                 }
 940                 return needkeyupdate(t.Type)
 941
 942         case TSTRUCT:
 943                 for t1 := t.Type; t1 != nil; t1 = t1.Down {
 944                         if needkeyupdate(t1.Type) {
 945                                 return true
 946                         }
 947                 }
 948                 return false
 949
 950         default:
 951                 Fatalf("bad type for map key: %v", t)
 952                 return true
 953         }
 954 }
 955
 956 func dtypesym(t *Type) *Sym {
 957         // Replace byte, rune aliases with real type.
 958         // They've been separate internally to make error messages
 959         // better, but we have to merge them in the reflect tables.
 960         if t == bytetype || t == runetype {
 961                 t = Types[t.Etype]
 962         }
 963
 964         if isideal(t) {
 965                 Fatalf("dtypesym %v", t)
 966         }
 967
 968         s := typesym(t)
 969         if s.Flags&SymSiggen != 0 {
 970                 return s
 971         }
 972         s.Flags |= SymSiggen
 973
 974         // special case (look for runtime below):
 975         // when compiling package runtime,
 976         // emit the type structures for int, float, etc.
 977         tbase := t
 978
 979         if Isptr[t.Etype] && t.Sym == nil && t.Type.Sym != nil {
 980                 tbase = t.Type
 981         }
 982         dupok := 0
 983         if tbase.Sym == nil {
 984                 dupok = obj.DUPOK
 985         }
 986
 987         if myimportpath == "runtime" && (tbase == Types[tbase.Etype] || tbase == bytetype || tbase == runetype || tbase == errortype) { // int, float, etc
 988                 goto ok
 989         }
 990
 991         // named types from other files are defined only by those files
 992         if tbase.Sym != nil && !tbase.Local {
 993                 return s
 994         }
 995         if isforw[tbase.Etype] {
 996                 return s
 997         }
 998
 999 ok:
1000         ot := 0
1001         xt := 0
1002         switch t.Etype {
1003         default:
1004                 ot = dcommontype(s, ot, t)
1005                 xt = ot - 1*Widthptr
1006
1007         case TARRAY:
1008                 if t.Bound >= 0 {
1009                         // ../../../../runtime/type.go:/arrayType
1010                         s1 := dtypesym(t.Type)
1011
1012                         t2 := typ(TARRAY)
1013                         t2.Type = t.Type
1014                         t2.Bound = -1 // slice
1015                         s2 := dtypesym(t2)
1016                         ot = dcommontype(s, ot, t)
1017                         xt = ot - 1*Widthptr
1018                         ot = dsymptr(s, ot, s1, 0)
1019                         ot = dsymptr(s, ot, s2, 0)
1020                         ot = duintptr(s, ot, uint64(t.Bound))
1021                 } else {
1022                         // ../../../../runtime/type.go:/sliceType
1023                         s1 := dtypesym(t.Type)
1024
1025                         ot = dcommontype(s, ot, t)
1026                         xt = ot - 1*Widthptr
1027                         ot = dsymptr(s, ot, s1, 0)
1028                 }
1029
1030         // ../../../../runtime/type.go:/chanType
1031         case TCHAN:
1032                 s1 := dtypesym(t.Type)
1033
1034                 ot = dcommontype(s, ot, t)
1035                 xt = ot - 1*Widthptr
1036                 ot = dsymptr(s, ot, s1, 0)
1037                 ot = duintptr(s, ot, uint64(t.Chan))
1038
1039         case TFUNC:
1040                 for t1 := getthisx(t).Type; t1 != nil; t1 = t1.Down {
1041                         dtypesym(t1.Type)
1042                 }
1043                 isddd := false
1044                 for t1 := getinargx(t).Type; t1 != nil; t1 = t1.Down {
1045                         isddd = t1.Isddd
1046                         dtypesym(t1.Type)
1047                 }
1048
1049                 for t1 := getoutargx(t).Type; t1 != nil; t1 = t1.Down {
1050                         dtypesym(t1.Type)
1051                 }
1052
1053                 ot = dcommontype(s, ot, t)
1054                 xt = ot - 1*Widthptr
1055                 ot = duint8(s, ot, uint8(obj.Bool2int(isddd)))
1056
1057                 // two slice headers: in and out.
1058                 ot = int(Rnd(int64(ot), int64(Widthptr)))
1059
1060                 ot = dsymptr(s, ot, s, ot+2*(Widthptr+2*Widthint))
1061                 n := t.Thistuple + t.Intuple
1062                 ot = duintxx(s, ot, uint64(n), Widthint)
1063                 ot = duintxx(s, ot, uint64(n), Widthint)
1064                 ot = dsymptr(s, ot, s, ot+1*(Widthptr+2*Widthint)+n*Widthptr)
1065                 ot = duintxx(s, ot, uint64(t.Outtuple), Widthint)
1066                 ot = duintxx(s, ot, uint64(t.Outtuple), Widthint)
1067
1068                 // slice data
1069                 for t1 := getthisx(t).Type; t1 != nil; t1 = t1.Down {
1070                         ot = dsymptr(s, ot, dtypesym(t1.Type), 0)
1071                         n++
1072                 }
1073                 for t1 := getinargx(t).Type; t1 != nil; t1 = t1.Down {
1074                         ot = dsymptr(s, ot, dtypesym(t1.Type), 0)
1075                         n++
1076                 }
1077                 for t1 := getoutargx(t).Type; t1 != nil; t1 = t1.Down {
1078                         ot = dsymptr(s, ot, dtypesym(t1.Type), 0)
1079                         n++
1080                 }
1081
1082         case TINTER:
1083                 m := imethods(t)
1084                 n := len(m)
1085                 for _, a := range m {
1086                         dtypesym(a.type_)
1087                 }
1088
1089                 // ../../../../runtime/type.go:/interfaceType
1090                 ot = dcommontype(s, ot, t)
1091
1092                 xt = ot - 1*Widthptr
1093                 ot = dsymptr(s, ot, s, ot+Widthptr+2*Widthint)
1094                 ot = duintxx(s, ot, uint64(n), Widthint)
1095                 ot = duintxx(s, ot, uint64(n), Widthint)
1096                 for _, a := range m {
1097                         // ../../../../runtime/type.go:/imethod
1098                         ot = dgostringptr(s, ot, a.name)
1099
1100                         ot = dgopkgpath(s, ot, a.pkg)
1101                         ot = dsymptr(s, ot, dtypesym(a.type_), 0)
1102                 }
1103
1104         // ../../../../runtime/type.go:/mapType
1105         case TMAP:
1106                 s1 := dtypesym(t.Down)
1107
1108                 s2 := dtypesym(t.Type)
1109                 s3 := dtypesym(mapbucket(t))
1110                 s4 := dtypesym(hmap(t))
1111                 ot = dcommontype(s, ot, t)
1112                 xt = ot - 1*Widthptr
1113                 ot = dsymptr(s, ot, s1, 0)
1114                 ot = dsymptr(s, ot, s2, 0)
1115                 ot = dsymptr(s, ot, s3, 0)
1116                 ot = dsymptr(s, ot, s4, 0)
1117                 if t.Down.Width > MAXKEYSIZE {
1118                         ot = duint8(s, ot, uint8(Widthptr))
1119                         ot = duint8(s, ot, 1) // indirect
1120                 } else {
1121                         ot = duint8(s, ot, uint8(t.Down.Width))
1122                         ot = duint8(s, ot, 0) // not indirect
1123                 }
1124
1125                 if t.Type.Width > MAXVALSIZE {
1126                         ot = duint8(s, ot, uint8(Widthptr))
1127                         ot = duint8(s, ot, 1) // indirect
1128                 } else {
1129                         ot = duint8(s, ot, uint8(t.Type.Width))
1130                         ot = duint8(s, ot, 0) // not indirect
1131                 }
1132
1133                 ot = duint16(s, ot, uint16(mapbucket(t).Width))
1134                 ot = duint8(s, ot, uint8(obj.Bool2int(isreflexive(t.Down))))
1135                 ot = duint8(s, ot, uint8(obj.Bool2int(needkeyupdate(t.Down))))
1136
1137         case TPTR32, TPTR64:
1138                 if t.Type.Etype == TANY {
1139                         // ../../../../runtime/type.go:/UnsafePointerType
1140                         ot = dcommontype(s, ot, t)
1141
1142                         break
1143                 }
1144
1145                 // ../../../../runtime/type.go:/ptrType
1146                 s1 := dtypesym(t.Type)
1147
1148                 ot = dcommontype(s, ot, t)
1149                 xt = ot - 1*Widthptr
1150                 ot = dsymptr(s, ot, s1, 0)
1151
1152         // ../../../../runtime/type.go:/structType
1153         // for security, only the exported fields.
1154         case TSTRUCT:
1155                 n := 0
1156
1157                 for t1 := t.Type; t1 != nil; t1 = t1.Down {
1158                         dtypesym(t1.Type)
1159                         n++
1160                 }
1161
1162                 ot = dcommontype(s, ot, t)
1163                 xt = ot - 1*Widthptr
1164                 ot = dsymptr(s, ot, s, ot+Widthptr+2*Widthint)
1165                 ot = duintxx(s, ot, uint64(n), Widthint)
1166                 ot = duintxx(s, ot, uint64(n), Widthint)
1167                 for t1 := t.Type; t1 != nil; t1 = t1.Down {
1168                         // ../../../../runtime/type.go:/structField
1169                         if t1.Sym != nil && t1.Embedded == 0 {
1170                                 ot = dgostringptr(s, ot, t1.Sym.Name)
1171                                 if exportname(t1.Sym.Name) {
1172                                         ot = dgostringptr(s, ot, "")
1173                                 } else {
1174                                         ot = dgopkgpath(s, ot, t1.Sym.Pkg)
1175                                 }
1176                         } else {
1177                                 ot = dgostringptr(s, ot, "")
1178                                 if t1.Type.Sym != nil &&
1179                                         (t1.Type.Sym.Pkg == builtinpkg || !exportname(t1.Type.Sym.Name)) {
1180                                         ot = dgopkgpath(s, ot, localpkg)
1181                                 } else {
1182                                         ot = dgostringptr(s, ot, "")
1183                                 }
1184                         }
1185
1186                         ot = dsymptr(s, ot, dtypesym(t1.Type), 0)
1187                         ot = dgostrlitptr(s, ot, t1.Note)
1188                         ot = duintptr(s, ot, uint64(t1.Width)) // field offset
1189                 }
1190         }
1191
1192         ot = dextratype(s, ot, t, xt)
1193         ggloblsym(s, int32(ot), int16(dupok|obj.RODATA))
1194
1195         // generate typelink.foo pointing at s = type.foo.
1196         // The linker will leave a table of all the typelinks for
1197         // types in the binary, so reflect can find them.
1198         // We only need the link for unnamed composites that
1199         // we want be able to find.
1200         if t.Sym == nil {
1201                 switch t.Etype {
1202                 case TPTR32, TPTR64, TARRAY, TCHAN, TFUNC, TMAP:
1203                         slink := typelinksym(t)
1204                         dsymptr(slink, 0, s, 0)
1205                         ggloblsym(slink, int32(Widthptr), int16(dupok|obj.RODATA))
1206                 }
1207         }
1208
1209         return s
1210 }
1211
1212 func dumptypestructs() {
1213         var n *Node
1214
1215         // copy types from externdcl list to signatlist
1216         for _, n := range externdcl {
1217                 if n.Op != OTYPE {
1218                         continue
1219                 }
1220                 signatlist = list(signatlist, n)
1221         }
1222
1223         // process signatlist
1224         var t *Type
1225         for l := signatlist; l != nil; l = l.Next {
1226                 n = l.N
1227                 if n.Op != OTYPE {
1228                         continue
1229                 }
1230                 t = n.Type
1231                 dtypesym(t)
1232                 if t.Sym != nil {
1233                         dtypesym(Ptrto(t))
1234                 }
1235         }
1236
1237         // generate import strings for imported packages
1238         for _, p := range pkgs {
1239                 if p.Direct {
1240                         dimportpath(p)
1241                 }
1242         }
1243
1244         // do basic types if compiling package runtime.
1245         // they have to be in at least one package,
1246         // and runtime is always loaded implicitly,
1247         // so this is as good as any.
1248         // another possible choice would be package main,
1249         // but using runtime means fewer copies in .6 files.
1250         if myimportpath == "runtime" {
1251                 for i := EType(1); i <= TBOOL; i++ {
1252                         dtypesym(Ptrto(Types[i]))
1253                 }
1254                 dtypesym(Ptrto(Types[TSTRING]))
1255                 dtypesym(Ptrto(Types[TUNSAFEPTR]))
1256
1257                 // emit type structs for error and func(error) string.
1258                 // The latter is the type of an auto-generated wrapper.
1259                 dtypesym(Ptrto(errortype))
1260
1261                 dtypesym(functype(nil, list1(Nod(ODCLFIELD, nil, typenod(errortype))), list1(Nod(ODCLFIELD, nil, typenod(Types[TSTRING])))))
1262
1263                 // add paths for runtime and main, which 6l imports implicitly.
1264                 dimportpath(Runtimepkg)
1265
1266                 if flag_race != 0 {
1267                         dimportpath(racepkg)
1268                 }
1269                 if flag_msan != 0 {
1270                         dimportpath(msanpkg)
1271                 }
1272                 dimportpath(mkpkg("main"))
1273         }
1274 }
1275
1276 func dalgsym(t *Type) *Sym {
1277         var s *Sym
1278         var hashfunc *Sym
1279         var eqfunc *Sym
1280
1281         // dalgsym is only called for a type that needs an algorithm table,
1282         // which implies that the type is comparable (or else it would use ANOEQ).
1283
1284         if algtype(t) == AMEM {
1285                 // we use one algorithm table for all AMEM types of a given size
1286                 p := fmt.Sprintf(".alg%d", t.Width)
1287
1288                 s = Pkglookup(p, typepkg)
1289
1290                 if s.Flags&SymAlgGen != 0 {
1291                         return s
1292                 }
1293                 s.Flags |= SymAlgGen
1294
1295                 // make hash closure
1296                 p = fmt.Sprintf(".hashfunc%d", t.Width)
1297
1298                 hashfunc = Pkglookup(p, typepkg)
1299
1300                 ot := 0
1301                 ot = dsymptr(hashfunc, ot, Pkglookup("memhash_varlen", Runtimepkg), 0)
1302                 ot = duintxx(hashfunc, ot, uint64(t.Width), Widthptr) // size encoded in closure
1303                 ggloblsym(hashfunc, int32(ot), obj.DUPOK|obj.RODATA)
1304
1305                 // make equality closure
1306                 p = fmt.Sprintf(".eqfunc%d", t.Width)
1307
1308                 eqfunc = Pkglookup(p, typepkg)
1309
1310                 ot = 0
1311                 ot = dsymptr(eqfunc, ot, Pkglookup("memequal_varlen", Runtimepkg), 0)
1312                 ot = duintxx(eqfunc, ot, uint64(t.Width), Widthptr)
1313                 ggloblsym(eqfunc, int32(ot), obj.DUPOK|obj.RODATA)
1314         } else {
1315                 // generate an alg table specific to this type
1316                 s = typesymprefix(".alg", t)
1317
1318                 hash := typesymprefix(".hash", t)
1319                 eq := typesymprefix(".eq", t)
1320                 hashfunc = typesymprefix(".hashfunc", t)
1321                 eqfunc = typesymprefix(".eqfunc", t)
1322
1323                 genhash(hash, t)
1324                 geneq(eq, t)
1325
1326                 // make Go funcs (closures) for calling hash and equal from Go
1327                 dsymptr(hashfunc, 0, hash, 0)
1328
1329                 ggloblsym(hashfunc, int32(Widthptr), obj.DUPOK|obj.RODATA)
1330                 dsymptr(eqfunc, 0, eq, 0)
1331                 ggloblsym(eqfunc, int32(Widthptr), obj.DUPOK|obj.RODATA)
1332         }
1333
1334         // ../../../../runtime/alg.go:/typeAlg
1335         ot := 0
1336
1337         ot = dsymptr(s, ot, hashfunc, 0)
1338         ot = dsymptr(s, ot, eqfunc, 0)
1339         ggloblsym(s, int32(ot), obj.DUPOK|obj.RODATA)
1340         return s
1341 }
1342
1343 // maxPtrmaskBytes is the maximum length of a GC ptrmask bitmap,
1344 // which holds 1-bit entries describing where pointers are in a given type.
1345 // 16 bytes is enough to describe 128 pointer-sized words, 512 or 1024 bytes
1346 // depending on the system. Above this length, the GC information is
1347 // recorded as a GC program, which can express repetition compactly.
1348 // In either form, the information is used by the runtime to initialize the
1349 // heap bitmap, and for large types (like 128 or more words), they are
1350 // roughly the same speed. GC programs are never much larger and often
1351 // more compact. (If large arrays are involved, they can be arbitrarily more
1352 // compact.)
1353 //
1354 // The cutoff must be large enough that any allocation large enough to
1355 // use a GC program is large enough that it does not share heap bitmap
1356 // bytes with any other objects, allowing the GC program execution to
1357 // assume an aligned start and not use atomic operations. In the current
1358 // runtime, this means all malloc size classes larger than the cutoff must
1359 // be multiples of four words. On 32-bit systems that's 16 bytes, and
1360 // all size classes >= 16 bytes are 16-byte aligned, so no real constraint.
1361 // On 64-bit systems, that's 32 bytes, and 32-byte alignment is guaranteed
1362 // for size classes >= 256 bytes. On a 64-bit system, 256 bytes allocated
1363 // is 32 pointers, the bits for which fit in 4 bytes. So maxPtrmaskBytes
1364 // must be >= 4.
1365 //
1366 // We used to use 16 because the GC programs do have some constant overhead
1367 // to get started, and processing 128 pointers seems to be enough to
1368 // amortize that overhead well.
1369 //
1370 // To make sure that the runtime's chansend can call typeBitsBulkBarrier,
1371 // we raised the limit to 2048, so that even 32-bit systems are guaranteed to
1372 // use bitmaps for objects up to 64 kB in size.
1373 //
1374 // Also known to reflect/type.go.
1375 //
1376 const maxPtrmaskBytes = 2048
1377
1378 // dgcsym emits and returns a data symbol containing GC information for type t,
1379 // along with a boolean reporting whether the UseGCProg bit should be set in
1380 // the type kind, and the ptrdata field to record in the reflect type information.
1381 func dgcsym(t *Type) (sym *Sym, useGCProg bool, ptrdata int64) {
1382         ptrdata = typeptrdata(t)
1383         if ptrdata/int64(Widthptr) <= maxPtrmaskBytes*8 {
1384                 sym = dgcptrmask(t)
1385                 return
1386         }
1387
1388         useGCProg = true
1389         sym, ptrdata = dgcprog(t)
1390         return
1391 }
1392
1393 // dgcptrmask emits and returns the symbol containing a pointer mask for type t.
1394 func dgcptrmask(t *Type) *Sym {
1395         ptrmask := make([]byte, (typeptrdata(t)/int64(Widthptr)+7)/8)
1396         fillptrmask(t, ptrmask)
1397         p := fmt.Sprintf("gcbits.%x", ptrmask)
1398
1399         sym := Pkglookup(p, Runtimepkg)
1400         if sym.Flags&SymUniq == 0 {
1401                 sym.Flags |= SymUniq
1402                 for i, x := range ptrmask {
1403                         duint8(sym, i, x)
1404                 }
1405                 ggloblsym(sym, int32(len(ptrmask)), obj.DUPOK|obj.RODATA|obj.LOCAL)
1406         }
1407         return sym
1408 }
1409
1410 // fillptrmask fills in ptrmask with 1s corresponding to the
1411 // word offsets in t that hold pointers.
1412 // ptrmask is assumed to fit at least typeptrdata(t)/Widthptr bits.
1413 func fillptrmask(t *Type, ptrmask []byte) {
1414         for i := range ptrmask {
1415                 ptrmask[i] = 0
1416         }
1417         if !haspointers(t) {
1418                 return
1419         }
1420
1421         vec := bvalloc(8 * int32(len(ptrmask)))
1422         xoffset := int64(0)
1423         onebitwalktype1(t, &xoffset, vec)
1424
1425         nptr := typeptrdata(t) / int64(Widthptr)
1426         for i := int64(0); i < nptr; i++ {
1427                 if bvget(vec, int32(i)) == 1 {
1428                         ptrmask[i/8] |= 1 << (uint(i) % 8)
1429                 }
1430         }
1431 }
1432
1433 // dgcprog emits and returns the symbol containing a GC program for type t
1434 // along with the size of the data described by the program (in the range [typeptrdata(t), t.Width]).
1435 // In practice, the size is typeptrdata(t) except for non-trivial arrays.
1436 // For non-trivial arrays, the program describes the full t.Width size.
1437 func dgcprog(t *Type) (*Sym, int64) {
1438         dowidth(t)
1439         if t.Width == BADWIDTH {
1440                 Fatalf("dgcprog: %v badwidth", t)
1441         }
1442         sym := typesymprefix(".gcprog", t)
1443         var p GCProg
1444         p.init(sym)
1445         p.emit(t, 0)
1446         offset := p.w.BitIndex() * int64(Widthptr)
1447         p.end()
1448         if ptrdata := typeptrdata(t); offset < ptrdata || offset > t.Width {
1449                 Fatalf("dgcprog: %v: offset=%d but ptrdata=%d size=%d", t, offset, ptrdata, t.Width)
1450         }
1451         return sym, offset
1452 }
1453
1454 type GCProg struct {
1455         sym    *Sym
1456         symoff int
1457         w      gcprog.Writer
1458 }
1459
1460 var Debug_gcprog int // set by -d gcprog
1461
1462 func (p *GCProg) init(sym *Sym) {
1463         p.sym = sym
1464         p.symoff = 4 // first 4 bytes hold program length
1465         p.w.Init(p.writeByte)
1466         if Debug_gcprog > 0 {
1467                 fmt.Fprintf(os.Stderr, "compile: start GCProg for %v\n", sym)
1468                 p.w.Debug(os.Stderr)
1469         }
1470 }
1471
1472 func (p *GCProg) writeByte(x byte) {
1473         p.symoff = duint8(p.sym, p.symoff, x)
1474 }
1475
1476 func (p *GCProg) end() {
1477         p.w.End()
1478         duint32(p.sym, 0, uint32(p.symoff-4))
1479         ggloblsym(p.sym, int32(p.symoff), obj.DUPOK|obj.RODATA|obj.LOCAL)
1480         if Debug_gcprog > 0 {
1481                 fmt.Fprintf(os.Stderr, "compile: end GCProg for %v\n", p.sym)
1482         }
1483 }
1484
1485 func (p *GCProg) emit(t *Type, offset int64) {
1486         dowidth(t)
1487         if !haspointers(t) {
1488                 return
1489         }
1490         if t.Width == int64(Widthptr) {
1491                 p.w.Ptr(offset / int64(Widthptr))
1492                 return
1493         }
1494         switch t.Etype {
1495         default:
1496                 Fatalf("GCProg.emit: unexpected type %v", t)
1497
1498         case TSTRING:
1499                 p.w.Ptr(offset / int64(Widthptr))
1500
1501         case TINTER:
1502                 p.w.Ptr(offset / int64(Widthptr))
1503                 p.w.Ptr(offset/int64(Widthptr) + 1)
1504
1505         case TARRAY:
1506                 if Isslice(t) {
1507                         p.w.Ptr(offset / int64(Widthptr))
1508                         return
1509                 }
1510                 if t.Bound == 0 {
1511                         // should have been handled by haspointers check above
1512                         Fatalf("GCProg.emit: empty array")
1513                 }
1514
1515                 // Flatten array-of-array-of-array to just a big array by multiplying counts.
1516                 count := t.Bound
1517                 elem := t.Type
1518                 for Isfixedarray(elem) {
1519                         count *= elem.Bound
1520                         elem = elem.Type
1521                 }
1522
1523                 if !p.w.ShouldRepeat(elem.Width/int64(Widthptr), count) {
1524                         // Cheaper to just emit the bits.
1525                         for i := int64(0); i < count; i++ {
1526                                 p.emit(elem, offset+i*elem.Width)
1527                         }
1528                         return
1529                 }
1530                 p.emit(elem, offset)
1531                 p.w.ZeroUntil((offset + elem.Width) / int64(Widthptr))
1532                 p.w.Repeat(elem.Width/int64(Widthptr), count-1)
1533
1534         case TSTRUCT:
1535                 for t1 := t.Type; t1 != nil; t1 = t1.Down {
1536                         p.emit(t1.Type, offset+t1.Width)
1537                 }
1538         }
1539 }