code review 6306083: runtime: detect hash map collision problems

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 "hashmap.h"
 #include "type.h"
 
 /* Hmap flag values */
 #define IndirectVal  (1<<0)     /* storing pointers to values */
@@ skipping 398 matching lines @@
                         hash_hash_t ins_e_hash;
                         void *key;
                         while (ins_e != end_e && ((e_hash = ins_e->hash) ^ hash) < HASH_SUBHASH) {
                                 key = ins_e->data;
                                 if (h->flag & IndirectKey)
                                         key = *(void**)key;
                                 if (HASH_DATA_EQ (eq, t, h, data, key)) {    /* a match */
                                         *pres = ins_e->data;
                                         return (1);
                                 }
-                                assert (e_hash != hash || (flags & HASH_REHASH) == 0);
-                                hash += (e_hash == hash);          /* adjust hash if it collides */
+                                if (e_hash == hash) {      /* adjust hash if it collides */
+                                        assert ((flags & HASH_REHASH) == 0);
+                                        hash++;
+                                        if ((hash & HASH_MASK) == HASH_SUBHASH)
+                                                runtime·throw("runtime: map hash collision overflow");
+                                }
                                 ins_e = HASH_OFFSET (ins_e, elemsize);
                                 ins_i++;
                                 if (e_hash <= hash) {          /* set e to insertion point */
                                         e = ins_e;
                                         i = ins_i;
                                 }
                         }
                         /* set ins_e to the insertion point for the new element */
                         ins_e = e;
                         ins_i = i;
@@ skipping 751 matching lines @@
         t->elem->alg->copy(t->elem->size, av, hash_valptr(h, res));
 
         if(debug) {
                 runtime·prints("mapiter2: iter=");
                 runtime·printpointer(it);
                 runtime·prints("; map=");
                 runtime·printpointer(h);
                 runtime·prints("\n");
         }
 }