code review 106260045: runtime: simpler and faster GC

src/cmd/gc/reflect.c

 // Copyright 2009 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 #include <u.h>
 #include <libc.h>
 #include "go.h"
 #include "../ld/textflag.h"
 #include "../../pkg/runtime/mgc0.h"
+#include "../../pkg/runtime/typekind.h"
 
 /*
  * runtime interface and reflection data structures
  */
 
 static  NodeList*       signatlist;
 static  Sym*    dtypesym(Type*);
 static  Sym*    weaktypesym(Type*);
 static  Sym*    dalgsym(Type*);
-static  Sym*    dgcsym(Type*);
+static  int     usegcprog(Type*);
+static  void    gengcprog(Type*, Sym**, Sym**);
+static  void    gengcmask(Type*, uint8[16]);
 
 static int
 sigcmp(Sig *a, Sig *b)
 {
         int i;
 
         i = strcmp(a->name, b->name);
         if(i != 0)
                 return i;
         if(a->pkg == b->pkg)
@@ skipping 575 matching lines @@
                         ot = duintptr(s, ot, 0);
                 if(a->tsym)
                         ot = dsymptr(s, ot, a->tsym, 0);
                 else
                         ot = duintptr(s, ot, 0);
         }
 
         return ot;
 }
 
-enum {
-        KindBool = 1,
-        KindInt,
-        KindInt8,
-        KindInt16,
-        KindInt32,
-        KindInt64,
-        KindUint,
-        KindUint8,
-        KindUint16,
-        KindUint32,
-        KindUint64,
-        KindUintptr,
-        KindFloat32,
-        KindFloat64,
-        KindComplex64,
-        KindComplex128,
-        KindArray,
-        KindChan,
-        KindFunc,
-        KindInterface,
-        KindMap,
-        KindPtr,
-        KindSlice,
-        KindString,
-        KindStruct,
-        KindUnsafePointer,
-
-        KindNoPointers = 1<<7,
-};
-
 static int
 kinds[] =
 {
         [TINT]          = KindInt,
         [TUINT]         = KindUint,
         [TINT8]         = KindInt8,
         [TUINT8]        = KindUint8,
         [TINT16]        = KindInt16,
         [TUINT16]       = KindUint16,
         [TINT32]        = KindInt32,
@@ skipping 83 matching lines @@
         return ret;
 }
 
 /*
  * commonType
  * ../../pkg/runtime/type.go:/commonType
  */
 static int
 dcommontype(Sym *s, int ot, Type *t)
 {
-        int i, alg, sizeofAlg;
-        Sym *sptr, *algsym, *zero;
+        int i, alg, sizeofAlg, gcprog;
+        Sym *sptr, *algsym, *zero, *gcprog0, *gcprog1;
+        uint8 gcmask[16];
         static Sym *algarray;
         char *p;
 ········
         if(ot != 0)
                 fatal("dcommontype %d", ot);
 
         sizeofAlg = 4*widthptr;
         if(algarray == nil)
                 algarray = pkglookup("algarray", runtimepkg);
         alg = algtype(t);
@@ skipping 41 matching lines @@
 
         // runtime (and common sense) expects alignment to be a power of two.
         i = t->align;
         if(i == 0)
                 i = 1;
         if((i&(i-1)) != 0)
                 fatal("invalid alignment %d for %T", t->align, t);
         ot = duint8(s, ot, t->align);   // align
         ot = duint8(s, ot, t->align);   // fieldAlign
 
+        gcprog = usegcprog(t);
         i = kinds[t->etype];
         if(t->etype == TARRAY && t->bound < 0)
                 i = KindSlice;
         if(!haspointers(t))
                 i |= KindNoPointers;
+        if(gcprog)
+                i |= KindGCProg;
         ot = duint8(s, ot, i);  // kind
         if(alg >= 0)
                 ot = dsymptr(s, ot, algarray, alg*sizeofAlg);
         else
                 ot = dsymptr(s, ot, algsym, 0);
-        ot = dsymptr(s, ot, dgcsym(t), 0);  // gc
+        // gc
+        if(gcprog) {
+                gengcprog(t, &gcprog0, &gcprog1);
+                if(gcprog0 != S)
+                        ot = dsymptr(s, ot, gcprog0, 0);
+                else
+                        ot = duintptr(s, ot, 0);
+                ot = dsymptr(s, ot, gcprog1, 0);
+        } else {
+                gengcmask(t, gcmask);
+                for(i = 0; i < 2*widthptr; i++)
+                        ot = duint8(s, ot, gcmask[i]);
+        }
         p = smprint("%-uT", t);
         //print("dcommontype: %s\n", p);
         ot = dgostringptr(s, ot, p);    // string
         free(p);
 
         // skip pointer to extraType,
         // which follows the rest of this type structure.
         // caller will fill in if needed.
         // otherwise linker will assume 0.
         ot += widthptr;
@@ skipping 435 matching lines @@
                 snprint(buf, sizeof buf, "memcopy%d", (int)t->width*8);
                 ot = dsymptr(s, ot, pkglookup(buf, runtimepkg), 0);
                 break;
         }
 
         ggloblsym(s, ot, DUPOK|RODATA);
         return s;
 }
 
 static int
-gcinline(Type *t)
-{
-        switch(t->etype) {
-        case TARRAY:
-                if(t->bound == 1)
-                        return 1;
-                if(t->width <= 4*widthptr)
-                        return 1;
-                break;
-        }
-        return 0;
-}
-
-static int
-dgcsym1(Sym *s, int ot, Type *t, vlong *off, int stack_size)
-{
-        Type *t1;
-        vlong o, off2, fieldoffset, i;
-
-        if(t->align > 0 && (*off % t->align) != 0)
-                fatal("dgcsym1: invalid initial alignment, %T", t);
-
+usegcprog(Type *t)
+{
+        vlong size, nptr;
+
+        if(!haspointers(t))
+                return 0;
         if(t->width == BADWIDTH)
                 dowidth(t);
- ·······
+        // Calculate size of the unrolled GC mask.
+        nptr = (t->width+widthptr-1)/widthptr;
+        size = nptr;
+        if(size%2)
+                size *= 2;      // repeated
+        size = size*PointersPerByte/8;  // 4 bits per word
+        // Decide whether to use unrolled GC mask or GC program.
+        // We could use a more elaborate condition, but this seems to work good in practice.
+        // For small objects GC program can't give significant reduction.
+        // While large objects usually contain arrays; and even if it don't
+        // the program uses 2-bits per word while mask uses 4-bits per word,
+        // so the program is still smaller.
+        return size > 2*widthptr;
+}
+
+// Generates sparse GC bitmask (4 bits per word).
+static void
+gengcmask(Type *t, uint8 gcmask[16])
+{
+        Bvec *vec;
+        vlong xoffset, nptr, i, j;
+        int  half, mw;
+        uint8 bits, *pos;
+
+        memset(gcmask, 0, 16);
+        if(!haspointers(t))
+                return;
+
+        // Generate compact mask as stacks use.
+        xoffset = 0;
+        vec = bvalloc(2*widthptr*8);
+        twobitwalktype1(t, &xoffset, vec);
+
+        // Unfold the mask for the GC bitmap format:
+        // 4 bits per word, 2 high bits encode pointer info.
+        pos = (uint8*)gcmask;
+        nptr = (t->width+widthptr-1)/widthptr;
+        half = 0;
+        mw = 0;
+        // If number of words is odd, repeat the mask.
+        // This makes simpler handling of arrays in runtime.
+        for(j=0; j<=(nptr%2); j++) {
+                for(i=0; i<nptr; i++) {
+                        bits = bvget(vec, i*BitsPerPointer) | bvget(vec, i*BitsPerPointer+1)<<1;
+
+                        //bits = ((uint8*)vec->b)[i*BitsPerPointer/8];

[rsc, 2014/07/23 16:23:20]

Delete debugging dregs.

[dvyukov, 2014/07/23 19:01:44]

Done.

+                        //bits >>= (i*BitsPerPointer)%8;
+                        //bits &= (1<<BitsPerPointer)-1;
+                        //print("BITS %d %d [%d %d]\n", bits, (bvget(vec, i*BitsPerPointer)<<1) | bvget(vec, i*BitsPerPointer+1), bvget(vec, i*BitsPerPointer), bvget(vec, i*BitsPerPointer+1));
+
+                        // Some fake types (e.g. Hmap) has missing fileds.
+                        // twobitwalktype1 generates BitsDead for that holes,
+                        // replace BitsDead with BitsScalar.
+                        if(!mw && bits == BitsDead)
+                                bits = BitsScalar;
+                        mw = !mw && bits == BitsMultiWord;
+                        bits <<= 2;
+                        if(half)
+                                bits <<= 4;
+                        *pos |= bits;
+                        half = !half;
+                        if(!half)
+                                pos++;
+                }
+        }
+}
+
+// Helper object for generation of GC programs.
+typedef struct ProgGen ProgGen;
+struct ProgGen
+{
+        Sym*    s;
+        int32   datasize;
+        uint8   data[256/PointersPerByte];
+        vlong   ot;
+};
+
+static void
+proggeninit(ProgGen *g, Sym *s)
+{
+        g->s = s;
+        g->datasize = 0;
+        g->ot = 0;
+        memset(g->data, 0, sizeof(g->data));
+}
+
+static void
+proggenemit(ProgGen *g, uint8 v)
+{
+        g->ot = duint8(g->s, g->ot, v);
+}
+
+// Emits insData block from g->data.
+static void
+proggendataflush(ProgGen *g)
+{
+        int32 i, s;
+
+        if(g->datasize == 0)
+                return;
+        proggenemit(g, insData);
+        proggenemit(g, g->datasize);
+        s = (g->datasize + PointersPerByte - 1)/PointersPerByte;
+        for(i = 0; i < s; i++)
+                proggenemit(g, g->data[i]);
+        g->datasize = 0;
+        memset(g->data, 0, sizeof(g->data));
+}
+
+static void
+proggendata(ProgGen *g, uint8 d)
+{
+        g->data[g->datasize/PointersPerByte] |= d << ((g->datasize%PointersPerByte)*BitsPerPointer);
+        g->datasize++;
+        if(g->datasize == 255)
+                proggendataflush(g);
+}
+
+// Skip v bytes due to alignment, etc.
+static void
+proggenskip(ProgGen *g, vlong off, vlong v)
+{
+        vlong i;
+
+        for(i = off; i < off+v; i++) {
+                if((i%widthptr) == 0)
+                        proggendata(g, BitsScalar);
+        }
+}
+
+// Emit insArray instruction.
+static void
+proggenarray(ProgGen *g, vlong len)
+{
+        int32 i;
+
+        proggendataflush(g);
+        proggenemit(g, insArray);
+        for(i = 0; i < widthptr; i++, len >>= 8)
+                proggenemit(g, len);
+}
+
+static void
+proggenarrayend(ProgGen *g)
+{
+        proggendataflush(g);
+        proggenemit(g, insArrayEnd);
+}
+
+static vlong
+proggenfini(ProgGen *g)
+{
+        proggendataflush(g);
+        proggenemit(g, insEnd);
+        return g->ot;
+}
+
+static void gengcprog1(ProgGen *g, Type *t, vlong *xoffset);
+
+// Generates GC program for large types.
+static void
+gengcprog(Type *t, Sym **pgc0, Sym **pgc1)
+{
+        Sym *gc0, *gc1;
+        vlong nptr, size, ot, xoffset;
+        ProgGen g;
+

[rsc, 2014/07/23 16:23:19]

please add

g.type = t;

[rsc, 2014/07/23 16:24:17]

Ignore. This was a dreg from a suggestion to detect deeply nested arrays.
Checking for >=2 elements makes the detection unnecessary.

[dvyukov, 2014/07/23 19:01:44]

Acknowledged.

+        nptr = (t->width+widthptr-1)/widthptr;
+        size = nptr;
+        if(size%2)
+                size *= 2;      // repeated twice
+        size = size*PointersPerByte/8;  // 4 bits per word
+        size++; // unroll flag in the beginning
+        // emity space in BSS for unrolled program
+        *pgc0 = S;
+        // Don't generate it if it's too large, runtime will unroll directly into GC bitmap.
+        if(size <= MaxGCMask) {
+                gc0 = typesymprefix(".gc", t);
+                ggloblsym(gc0, size, DUPOK|NOPTR);
+                *pgc0 = gc0;
+        }
+
+        // program in RODATA
+        gc1 = typesymprefix(".gcprog", t);
+        proggeninit(&g, gc1);
+        xoffset = 0;
+        gengcprog1(&g, t, &xoffset);
+        ot = proggenfini(&g);
+        ggloblsym(gc1, ot, DUPOK|RODATA);
+        *pgc1 = gc1;
+}
+
+// Recursively walks type t and writes GC program into g.
+static void
+gengcprog1(ProgGen *g, Type *t, vlong *xoffset)
+{
+        vlong fieldoffset, i, o, n;
+        Type *t1;
+
         switch(t->etype) {
         case TINT8:
         case TUINT8:
         case TINT16:
         case TUINT16:
         case TINT32:
         case TUINT32:
         case TINT64:
         case TUINT64:
         case TINT:
         case TUINT:
         case TUINTPTR:
         case TBOOL:
         case TFLOAT32:
         case TFLOAT64:
         case TCOMPLEX64:
         case TCOMPLEX128:
-                *off += t->width;
+                proggenskip(g, *xoffset, t->width);
+                *xoffset += t->width;
                 break;
-
         case TPTR32:
         case TPTR64:
-                // NOTE: Any changes here need to be made to reflect.PtrTo as well.
-                if(*off % widthptr != 0)
-                        fatal("dgcsym1: invalid alignment, %T", t);
-
-                // NOTE(rsc): Emitting GC_APTR here for *nonptrtype
-                // (pointer to non-pointer-containing type) means that
-                // we do not record 'nonptrtype' and instead tell the·
-                // garbage collector to look up the type of the memory in
-                // type information stored in the heap. In effect we are telling
-                // the collector "we don't trust our information - use yours".
-                // It's not completely clear why we want to do this.
-                // It does have the effect that if you have a *SliceHeader and a *[]int
-                // pointing at the same actual slice header, *SliceHeader will not be
-                // used as an authoritative type for the memory, which is good:
-                // if the collector scanned the memory as type *SliceHeader, it would
-                // see no pointers inside but mark the block as scanned, preventing
-                // the seeing of pointers when we followed the *[]int pointer.
-                // Perhaps that kind of situation is the rationale.
-                if(!haspointers(t->type)) {
-                        ot = duintptr(s, ot, GC_APTR);
-                        ot = duintptr(s, ot, *off);
-                } else {
-                        ot = duintptr(s, ot, GC_PTR);
-                        ot = duintptr(s, ot, *off);
-                        ot = dsymptr(s, ot, dgcsym(t->type), 0);
-                }
-                *off += t->width;
-                break;
-
         case TUNSAFEPTR:
         case TFUNC:
-                if(*off % widthptr != 0)
-                        fatal("dgcsym1: invalid alignment, %T", t);
-                ot = duintptr(s, ot, GC_APTR);
-                ot = duintptr(s, ot, *off);
-                *off += t->width;
+        case TCHAN:
+        case TMAP:
+                proggendata(g, BitsPointer);
+                *xoffset += t->width;
                 break;
-
-        // struct Hchan*
-        case TCHAN:
-                // NOTE: Any changes here need to be made to reflect.ChanOf as well.
-                if(*off % widthptr != 0)
-                        fatal("dgcsym1: invalid alignment, %T", t);
-                ot = duintptr(s, ot, GC_CHAN_PTR);
-                ot = duintptr(s, ot, *off);
-                ot = dsymptr(s, ot, dtypesym(t), 0);
-                *off += t->width;
+        case TSTRING:
+                proggendata(g, BitsMultiWord);
+                proggendata(g, BitsString);
+                *xoffset += t->width;
                 break;
-
-        // struct Hmap*
-        case TMAP:
-                // NOTE: Any changes here need to be made to reflect.MapOf as well.
-                if(*off % widthptr != 0)
-                        fatal("dgcsym1: invalid alignment, %T", t);
-                ot = duintptr(s, ot, GC_PTR);
-                ot = duintptr(s, ot, *off);
-                ot = dsymptr(s, ot, dgcsym(hmap(t)), 0);
-                *off += t->width;
+        case TINTER:
+                proggendata(g, BitsMultiWord);
+                if(isnilinter(t))
+                        proggendata(g, BitsEface);
+                else
+                        proggendata(g, BitsIface);
+                *xoffset += t->width;
                 break;
-
-        // struct { byte *str; int32 len; }
-        case TSTRING:
-                if(*off % widthptr != 0)
-                        fatal("dgcsym1: invalid alignment, %T", t);
-                ot = duintptr(s, ot, GC_STRING);
-                ot = duintptr(s, ot, *off);
-                *off += t->width;
-                break;
-
-        // struct { Itab* tab;  void* data; }
-        // struct { Type* type; void* data; }   // When isnilinter(t)==true
-        case TINTER:
-                if(*off % widthptr != 0)
-                        fatal("dgcsym1: invalid alignment, %T", t);
-                if(isnilinter(t)) {
-                        ot = duintptr(s, ot, GC_EFACE);
-                        ot = duintptr(s, ot, *off);
+        case TARRAY:
+                if(isslice(t)) {
+                        proggendata(g, BitsMultiWord);
+                        proggendata(g, BitsSlice);
+                        proggendata(g, BitsScalar);
                 } else {
-                        ot = duintptr(s, ot, GC_IFACE);
-                        ot = duintptr(s, ot, *off);
-                }
-                *off += t->width;
-                break;
-
-        case TARRAY:
-                if(t->bound < -1)
-                        fatal("dgcsym1: invalid bound, %T", t);
-                if(t->type->width == BADWIDTH)
-                        dowidth(t->type);
-                if(isslice(t)) {
-                        // NOTE: Any changes here need to be made to reflect.SliceOf as well.
-                        // struct { byte* array; uint32 len; uint32 cap; }
-                        if(*off % widthptr != 0)
-                                fatal("dgcsym1: invalid alignment, %T", t);
-                        if(t->type->width != 0) {
-                                ot = duintptr(s, ot, GC_SLICE);
-                                ot = duintptr(s, ot, *off);
-                                ot = dsymptr(s, ot, dgcsym(t->type), 0);
+                        t1 = t->type;
+                        if(t1->width == 0) {
+                                // ignore
+                        } if(t->bound*t1->width < 32*widthptr) {

[rsc, 2014/07/23 16:23:20]

} else if(t->bound <= 1 || t->bound*t1->width < 32*widthptr) {

Adding the t->bound <= 1 will avoid generating array instructions for array size
0/1.

Making sure that the array instructions only happen for 2 or more elements
bounds the possible nesting that the runtime recursion will have to deal with
to at most the number of addressable bits. The runtime certainly has room for
64 frames on the stack.

But without the condition someone could overflow the runtime stack by creating
a [1][1][1][1][1][1]...*byte.

[dvyukov, 2014/07/23 19:01:44]

Done.

+                                for(i = 0; i < t->bound; i++)
+                                        gengcprog1(g, t1, xoffset);
+                        } else if(!haspointers(t1)) {
+                                n = t->width;
+                                n -= -*xoffset&(widthptr-1); // skip to next ptr boundary
+                                proggenarray(g, (n+widthptr-1)/widthptr);
+                                proggendata(g, BitsScalar);
+                                proggenarrayend(g);
                         } else {
-                                ot = duintptr(s, ot, GC_APTR);
-                                ot = duintptr(s, ot, *off);
-                        }
-                        *off += t->width;
-                } else {
-                        // NOTE: Any changes here need to be made to reflect.ArrayOf as well,
-                        // at least once ArrayOf's gc info is implemented and ArrayOf is exported.
-                        // struct { byte* array; uint32 len; uint32 cap; }
-                        if(t->bound < 1 || !haspointers(t->type)) {
-                                *off += t->width;
-                        } else if(gcinline(t)) {
-                                for(i=0; i<t->bound; i++)
-                                        ot = dgcsym1(s, ot, t->type, off, stack_size);  // recursive call of dgcsym1
-                        } else {
-                                if(stack_size < GC_STACK_CAPACITY) {
-                                        ot = duintptr(s, ot, GC_ARRAY_START);  // a stack push during GC
-                                        ot = duintptr(s, ot, *off);
-                                        ot = duintptr(s, ot, t->bound);
-                                        ot = duintptr(s, ot, t->type->width);
-                                        off2 = 0;
-                                        ot = dgcsym1(s, ot, t->type, &off2, stack_size+1);  // recursive call of dgcsym1
-                                        ot = duintptr(s, ot, GC_ARRAY_NEXT);  // a stack pop during GC
-                                } else {
-                                        ot = duintptr(s, ot, GC_REGION);
-                                        ot = duintptr(s, ot, *off);
-                                        ot = duintptr(s, ot, t->width);
-                                        ot = dsymptr(s, ot, dgcsym(t), 0);
-                                }
-                                *off += t->width;
+                                proggenarray(g, t->bound);
+                                gengcprog1(g, t1, xoffset);
+                                *xoffset += (t->bound-1)*t1->width;
+                                proggenarrayend(g);
                         }
                 }
                 break;
-
         case TSTRUCT:
                 o = 0;
-                for(t1=t->type; t1!=T; t1=t1->down) {
+                for(t1 = t->type; t1 != T; t1 = t1->down) {
                         fieldoffset = t1->width;
-                        *off += fieldoffset - o;
-                        ot = dgcsym1(s, ot, t1->type, off, stack_size);  // recursive call of dgcsym1
+                        proggenskip(g, *xoffset, fieldoffset - o);
+                        *xoffset += fieldoffset - o;
+                        gengcprog1(g, t1->type, xoffset);
                         o = fieldoffset + t1->type->width;
                 }
-                *off += t->width - o;
+                proggenskip(g, *xoffset, t->width - o);
+                *xoffset += t->width - o;
                 break;
-
         default:
-                fatal("dgcsym1: unexpected type %T", t);
+                fatal("gengcprog1: unexpected type, %T", t);
         }
-
-        return ot;
 }
-
-static Sym*
-dgcsym(Type *t)
-{
-        int ot;
-        vlong off;
-        Sym *s;
-
-        s = typesymprefix(".gc", t);
-        if(s->flags & SymGcgen)
-                return s;
-        s->flags |= SymGcgen;
-
-        if(t->width == BADWIDTH)
-                dowidth(t);
-
-        ot = 0;
-        off = 0;
-        ot = duintptr(s, ot, t->width);
-        ot = dgcsym1(s, ot, t, &off, 0);
-        ot = duintptr(s, ot, GC_END);
-        ggloblsym(s, ot, DUPOK|RODATA);
-
-        if(t->align > 0)
-                off = rnd(off, t->align);
-        if(off != t->width)
-                fatal("dgcsym: off=%lld, size=%lld, type %T", off, t->width, t);
-
-        return s;
-}