From 3b81bac147743fe83c7058a2394098ffd5093155 Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Sat, 22 Sep 2012 05:53:47 +1000 Subject: [PATCH] [release-branch.go1] runtime: detect hash map collision problems MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit ««« backport f99b9475b914 runtime: detect hash map collision problems This can only happen if the hash function we're using is getting far more than it's fair share of collisions, but that has happened to us repeatedly as we've expanded the allowed use cases for hash tables (issue 1544, issue 2609, issue 2630, issue 2883, issue 3695). Maybe this will help the next time we try something new. R=golang-dev, r CC=golang-dev https://golang.org/cl/6306083 »»» --- src/pkg/runtime/hashmap.c | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) diff --git a/src/pkg/runtime/hashmap.c b/src/pkg/runtime/hashmap.c index ea9887a19f..e8965a68d5 100644 --- a/src/pkg/runtime/hashmap.c +++ b/src/pkg/runtime/hashmap.c @@ -416,8 +416,12 @@ hash_insert_internal (MapType *t, struct hash_subtable **pst, int32 flags, hash_ *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 */ -- 2.50.0