code review 7746045: runtime: fix gdb printing of maps

src/pkg/runtime/hashmap.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 "runtime.h"
 #include "arch_GOARCH.h"
 #include "malloc.h"
 #include "hashmap.h"
 #include "type.h"
 #include "race.h"
@@ skipping 108 matching lines @@
 };
 
 // Macros for dereferencing indirect keys
 #define IK(h, p) (((h)->flags & IndirectKey) != 0 ? *(byte**)(p) : (p))
 #define IV(h, p) (((h)->flags & IndirectValue) != 0 ? *(byte**)(p) : (p))
 
 enum
 {
         docheck = 0,  // check invariants before and after every op.  Slow!!!
         debug = 0,    // print every operation
+        checkgc = 0 || docheck,  // check interaction of mallocgc() with the garbage collector
 };
 static void
 check(MapType *t, Hmap *h)
 {
         uintptr bucket, oldbucket;
         Bucket *b;
         uintptr i;
         uintptr hash;
         uintgo cnt;
         uint8 top;
@@ skipping 107 matching lines @@
         if(sizeof(void*) == 4 && t->elem->align > 4)
                 runtime·throw("need padding in bucket (value)");
 
         // find size parameter which will hold the requested # of elements
         B = 0;
         while(hint > BUCKETSIZE && hint > LOAD * ((uintptr)1 << B))
                 B++;
 
         // allocate initial hash table
         // If hint is large zeroing this memory could take a while.
-        buckets = runtime·mallocgc(bucketsize << B, 0, 1, 0);
-        for(i = 0; i < (uintptr)1 << B; i++) {
-                b = (Bucket*)(buckets + i * bucketsize);
-                clearbucket(b);
+        if(checkgc) mstats.next_gc = mstats.heap_alloc;
+        if(B == 0) {
+                // done lazily later.
+                buckets = nil;
+        } else {
+                buckets = runtime·mallocgc(bucketsize << B, 0, 1, 0);
+                for(i = 0; i < (uintptr)1 << B; i++) {
+                        b = (Bucket*)(buckets + i * bucketsize);
+                        clearbucket(b);
+                }
         }
 
         // initialize Hmap
         // Note: we save all these stores to the end so gciter doesn't see
         // a partially initialized map.
         h->count = 0;
         h->B = B;
         h->flags = flags;
         h->keysize = keysize;
         h->valuesize = valuesize;
@@ skipping 45 matching lines @@
                         for(i = 0, k = b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) {
                                 if(b->tophash[i] == 0)
                                         continue;
                                 hash = h->hash0;
                                 t->key->alg->hash(&hash, t->key->size, IK(h, k));
                                 // NOTE: if key != key, then this hash could be (and probably will be)
                                 // entirely different from the old hash.  We effectively only update
                                 // the B'th bit of the hash in this case.
                                 if((hash & newbit) == 0) {
                                         if(xi == BUCKETSIZE) {
+                                                if(checkgc) mstats.next_gc = mstats.heap_alloc;
                                                 newx = runtime·mallocgc(h->bucketsize, 0, 1, 0);
                                                 clearbucket(newx);
                                                 x->overflow = newx;
                                                 x = newx;
                                                 xi = 0;
                                                 xk = x->data;
                                                 xv = xk + h->keysize * BUCKETSIZE;
                                         }
                                         x->tophash[xi] = b->tophash[i];
                                         if((h->flags & IndirectKey) != 0) {
                                                 *(byte**)xk = *(byte**)k;               // copy pointer
                                         } else {
                                                 t->key->alg->copy(t->key->size, xk, k); // copy value
                                         }
                                         if((h->flags & IndirectValue) != 0) {
                                                 *(byte**)xv = *(byte**)v;
                                         } else {
                                                 t->elem->alg->copy(t->elem->size, xv, v);
                                         }
                                         xi++;
                                         xk += h->keysize;
                                         xv += h->valuesize;
                                 } else {
                                         if(yi == BUCKETSIZE) {
+                                                if(checkgc) mstats.next_gc = mstats.heap_alloc;
                                                 newy = runtime·mallocgc(h->bucketsize, 0, 1, 0);
                                                 clearbucket(newy);
                                                 y->overflow = newy;
                                                 y = newy;
                                                 yi = 0;
                                                 yk = y->data;
                                                 yv = yk + h->keysize * BUCKETSIZE;
                                         }
                                         y->tophash[yi] = b->tophash[i];
                                         if((h->flags & IndirectKey) != 0) {
@@ skipping 75 matching lines @@
 {
         byte *old_buckets;
         byte *new_buckets;
         uint8 flags;
 
         // allocate a bigger hash table
         if(h->oldbuckets != nil)
                 runtime·throw("evacuation not done in time");
         old_buckets = h->buckets;
         // NOTE: this could be a big malloc, but since we don't need zeroing it is probably fast.
+        if(checkgc) mstats.next_gc = mstats.heap_alloc;
         new_buckets = runtime·mallocgc(h->bucketsize << (h->B + 1), 0, 1, 0);
         flags = (h->flags & ~(Iterator | OldIterator));
         if((h->flags & Iterator) != 0) {
                 flags |= OldIterator;
                 // We can't free indirect keys any more, as
                 // they are potentially aliased across buckets.
                 flags &= ~CanFreeKey;
         }
 
         // commit the grow (atomic wrt gc)
@@ skipping 19 matching lines @@
         uintptr bucket;
         Bucket *b;
         uint8 top;
         uintptr i;
         bool eq;
         byte *k, *k2, *v;
 
         key = *keyp;
         if(docheck)
                 check(t, h);
+        if(h->count == 0)
+                return nil;
         hash = h->hash0;
         t->key->alg->hash(&hash, t->key->size, key);
         bucket = hash & (((uintptr)1 << h->B) - 1);
         if(h->oldbuckets != nil)
                 grow_work(t, h, bucket);
         b = (Bucket*)(h->buckets + bucket * h->bucketsize);
         top = hash >> (sizeof(uintptr)*8 - 8);
         if(top == 0)
                 top = 1;
         do {
@@ skipping 67 matching lines @@
         uint8 *inserti;
         byte *insertk, *insertv;
         uint8 top;
         byte *k, *v;
         byte *kmem, *vmem;
 
         if(docheck)
                 check(t, h);
         hash = h->hash0;
         t->key->alg->hash(&hash, t->key->size, key);
+        if(h->buckets == nil) {
+                h->buckets = runtime·mallocgc(h->bucketsize, 0, 1, 0);
+                b = (Bucket*)(h->buckets);
+                clearbucket(b);
+        }
+
  again:
         bucket = hash & (((uintptr)1 << h->B) - 1);
         if(h->oldbuckets != nil)
                 grow_work(t, h, bucket);
         b = (Bucket*)(h->buckets + bucket * h->bucketsize);
         top = hash >> (sizeof(uintptr)*8 - 8);
         if(top == 0)
                 top = 1;
         inserti = 0;
         insertk = nil;
@@ skipping 24 matching lines @@
         }
 
         // did not find mapping for key.  Allocate new cell & add entry.
         if(h->count >= LOAD * ((uintptr)1 << h->B) && h->count >= BUCKETSIZE) {
                 hash_grow(t, h);
                 goto again; // Growing the table invalidates everything, so try again
         }
 
         if(inserti == nil) {
                 // all current buckets are full, allocate a new one.
+                if(checkgc) mstats.next_gc = mstats.heap_alloc;
                 newb = runtime·mallocgc(h->bucketsize, 0, 1, 0);
                 clearbucket(newb);
                 b->overflow = newb;
                 inserti = newb->tophash;
                 insertk = newb->data;
                 insertv = insertk + h->keysize * BUCKETSIZE;
         }
 
         // store new key/value at insert position
         if((h->flags & IndirectKey) != 0) {
+                if(checkgc) mstats.next_gc = mstats.heap_alloc;
                 kmem = runtime·mallocgc(t->key->size, 0, 1, 0);
                 *(byte**)insertk = kmem;
                 insertk = kmem;
         }
         if((h->flags & IndirectValue) != 0) {
+                if(checkgc) mstats.next_gc = mstats.heap_alloc;
                 vmem = runtime·mallocgc(t->elem->size, 0, 1, 0);
                 *(byte**)insertv = vmem;
                 insertv = vmem;
         }
         t->key->alg->copy(t->key->size, insertk, key);
         t->elem->alg->copy(t->elem->size, insertv, value);
         *inserti = top;
         h->count++;
         if(docheck)
                 check(t, h);
 }
 
 static void
 hash_remove(MapType *t, Hmap *h, void *key)
 {
         uintptr hash;
         uintptr bucket;
         Bucket *b;
         uint8 top;
         uintptr i;
         byte *k, *v;
         bool eq;
 ········
         if(docheck)
                 check(t, h);
+        if(h->count == 0)
+                return;
         hash = h->hash0;
         t->key->alg->hash(&hash, t->key->size, key);
         bucket = hash & (((uintptr)1 << h->B) - 1);
         if(h->oldbuckets != nil)
                 grow_work(t, h, bucket);
         b = (Bucket*)(h->buckets + bucket * h->bucketsize);
         top = hash >> (sizeof(uintptr)*8 - 8);
         if(top == 0)
                 top = 1;
         do {
@@ skipping 70 matching lines @@
         it->B = h->B;
         it->buckets = h->buckets;
 
         // iterator state
         it->bucket = it->endbucket = runtime·fastrand1() & (((uintptr)1 << h->B) - 1);
         it->wrapped = false;
         it->bptr = nil;
 
         // Remember we have an iterator at this level.
         h->flags |= Iterator;
+
+        if(h->buckets == nil) {
+                // Empty map. Force next hash_next to exit without
+                // evalulating h->bucket.
+                it->wrapped = true;
+        }
 }
 
 // initializes it->key and it->value to the next key/value pair
 // in the iteration, or nil if we've reached the end.
 static void
 hash_next(struct hash_iter *it)
 {
         Hmap *h;
         MapType *t;
         uintptr bucket;
@@ skipping 79 matching lines @@
 #define PHASE_OLD_BUCKETS  1
 #define PHASE_TABLE        2
 #define PHASE_OLD_TABLE    3
 #define PHASE_DONE         4
 
 // Initialize the iterator.
 // Returns false if Hmap contains no pointers (in which case the iterator is not initialized).
 bool
 hash_gciter_init (Hmap *h, struct hash_gciter *it)
 {
-        // GC during map initialization
+        // GC during map initialization or on an empty map.
         if(h->buckets == nil)
                 return false;
 
         it->h = h;
         it->phase = PHASE_BUCKETS;
         it->bucket = 0;
         it->b = nil;
 
         // TODO: finish evacuating oldbuckets so that we can collect
         // oldbuckets?  We don't want to keep a partially evacuated
@@ skipping 122 matching lines @@
         }
         if(it->phase != PHASE_DONE)
                 runtime·throw("bad phase at done");
         return false;
 }
 
 //
 /// interfaces to go runtime
 //
 
+void
+reflect·ismapkey(Type *typ, bool ret)
+{
+        ret = typ != nil && typ->alg->hash != runtime·nohash;
+        FLUSH(&ret);
+}
+
 Hmap*
 runtime·makemap_c(MapType *typ, int64 hint)
 {
         Hmap *h;
         Type *key;
 
         key = typ->key;
 
         if(hint < 0 || (int32)hint != hint)
                 runtime·panicstring("makemap: size out of range");
@@ skipping 430 matching lines @@
         t->elem->alg->copy(t->elem->size, av, it->value);
 
         if(debug) {
                 runtime·prints("mapiter2: iter=");
                 runtime·printpointer(it);
                 runtime·prints("; map=");
                 runtime·printpointer(it->h);
                 runtime·prints("\n");
         }
 }