code review 6137051: runtime: fix hashmap code for large key size

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"
 
 struct Hmap {      /* a hash table; initialize with hash_init() */
         uint32 count;     /* elements in table - must be first */
-        uint32 datasize;   /* amount of data to store in entry */
+        uint8 datasize;   /* amount of data to store in entry */
         uint8 max_power;  /* max power of 2 to create sub-tables */
-        uint8 indirectval;      /* storing pointers to values */
-        uint32 valoff;  /* offset of value in key+value data block */
+        uint8 indirect; /* storing pointers to keys and/or values */
+        uint8 valoff;   /* offset of value in key+value data block */
         int32 changes;        /* inc'ed whenever a subtable is created/grown */
         uintptr hash0;      /* hash seed */
         struct hash_subtable *st;    /* first-level table */
 };
 
 struct hash_entry {
         hash_hash_t hash;     /* hash value of data */
         byte data[1];    /* user data has "datasize" bytes */
 };
 
 struct hash_subtable {
         uint8 power;     /* bits used to index this table */
         uint8 used;       /* bits in hash used before reaching this table */
+        uint8 datasize;      /* bytes of client data in an entry */
         uint8 max_probes;    /* max number of probes when searching */
         int16 limit_bytes;         /* max_probes * (datasize+sizeof (hash_hash_t)) */
-        uint32 datasize;      /* bytes of client data in an entry */
         struct hash_entry *last;      /* points to last element of entry[] */
         struct hash_entry entry[1];  /* 2**power+max_probes-1 elements of elemsize bytes */
 };
 
 #define HASH_DATA_EQ(eq, t, h,x,y) ((eq)=0, (*t->key->alg->equal) (&(eq), t->key->size, (x), (y)), (eq))
 
 #define HASH_REHASH 0x2       /* an internal flag */
 /* the number of bits used is stored in the flags word too */
 #define HASH_USED(x)      ((x) >> 2)
 #define HASH_MAKE_USED(x) ((x) << 2)
 
 #define HASH_LOW        6
 #define HASH_ONE        (((hash_hash_t)1) << HASH_LOW)
 #define HASH_MASK       (HASH_ONE - 1)
 #define HASH_ADJUST(x)  (((x) < HASH_ONE) << HASH_LOW)
 
 #define HASH_BITS       (sizeof (hash_hash_t) * 8)
 
 #define HASH_SUBHASH    HASH_MASK
 #define HASH_NIL        0
 #define HASH_NIL_MEMSET 0
 
 #define HASH_OFFSET(base, byte_offset) \
           ((struct hash_entry *) (((byte *) (base)) + (byte_offset)))
 
 #define HASH_MAX_PROBES 15 /* max entries to probe before rehashing */
+
+// Bit masks for Hmap indirect field.
+#define HASH_INDIRECT_KEY 1
+#define HASH_INDIRECT_VAL 2
 
 /* return a hash layer with 2**power empty entries */
 static struct hash_subtable *
 hash_subtable_new (Hmap *h, int32 power, int32 used)
 {
         int32 elemsize = h->datasize + offsetof (struct hash_entry, data[0]);
         int32 bytes = elemsize << power;
         struct hash_subtable *st;
         int32 limit_bytes = HASH_MAX_PROBES * elemsize;
         int32 max_probes = HASH_MAX_PROBES;
@@ skipping 33 matching lines @@
         }
         *max_power = 12;
 }
 
 static void
 hash_init (Hmap *h, int32 datasize, int64 hint)
 {
         int32 init_power;
         int32 max_power;
 
-        assert(datasize >= 0);
-        assert(datasize + offsetof(struct hash_entry, data[0]) <= 0x7fffffff);
         if(datasize < sizeof (void *))
                 datasize = sizeof (void *);
         datasize = runtime·rnd(datasize, sizeof (void *));
         init_sizes (hint, &init_power, &max_power);
         h->datasize = datasize;
         h->max_power = max_power;
         assert (h->datasize == datasize);
         assert (h->max_power == max_power);
         assert (sizeof (void *) <= h->datasize || h->max_power == 255);
         h->count = 0;
@@ skipping 139 matching lines @@
 static int32
 hash_lookup (MapType *t, Hmap *h, void *data, void **pres)
 {
         int32 elemsize = h->datasize + offsetof (struct hash_entry, data[0]);
         hash_hash_t hash;
         struct hash_subtable *st = h->st;
         int32 used = 0;
         hash_hash_t e_hash;
         struct hash_entry *e;
         struct hash_entry *end_e;
+        bool indirectkey;
         bool eq;
 ········
         hash = h->hash0;
         (*t->key->alg->hash) (&hash, t->key->size, data);
         hash &= ~HASH_MASK;
         hash += HASH_ADJUST (hash);
         for (;;) {
                 int32 shift = HASH_BITS - (st->power + used);
                 int32 index_mask = (1 << st->power) - 1;
                 int32 i = (hash >> shift) & index_mask;    /* i is the natural position of hash */
 
                 e = HASH_OFFSET (st->entry, i * elemsize); /* e points to element i */
                 e_hash = e->hash;
                 if ((e_hash & HASH_MASK) != HASH_SUBHASH) {      /* a subtable */
                         break;
                 }
                 used += st->power;
                 st = *(struct hash_subtable **)e->data;
         }
         end_e = HASH_OFFSET (e, st->limit_bytes);
         while (e != end_e && (e_hash = e->hash) != HASH_NIL && e_hash < hash) {
                 e = HASH_OFFSET (e, elemsize);
         }
+        indirectkey = h->indirect & HASH_INDIRECT_KEY;
         while (e != end_e && ((e_hash = e->hash) ^ hash) < HASH_SUBHASH) {
-                if (HASH_DATA_EQ (eq, t, h, data, e->data)) {    /* a match */
+                void *k = e->data;
+                if (indirectkey)
+                        k = *(void**)k;
+                if (HASH_DATA_EQ (eq, t, h, data, k)) {    /* a match */
                         *pres = e->data;
                         return (1);
                 }
                 e = HASH_OFFSET (e, elemsize);
         }
         USED(e_hash);
         *pres = 0;
         return (0);
 }
 
 static int32
 hash_remove (MapType *t, Hmap *h, void *data)
 {
         int32 elemsize = h->datasize + offsetof (struct hash_entry, data[0]);
         hash_hash_t hash;
         struct hash_subtable *st = h->st;
         int32 used = 0;
         hash_hash_t e_hash;
         struct hash_entry *e;
         struct hash_entry *end_e;
         bool eq;
+        bool indirectkey;
 
         hash = h->hash0;
         (*t->key->alg->hash) (&hash, t->key->size, data);
         hash &= ~HASH_MASK;
         hash += HASH_ADJUST (hash);
         for (;;) {
                 int32 shift = HASH_BITS - (st->power + used);
                 int32 index_mask = (1 << st->power) - 1;
                 int32 i = (hash >> shift) & index_mask;    /* i is the natural position of hash */
 
                 e = HASH_OFFSET (st->entry, i * elemsize); /* e points to element i */
                 e_hash = e->hash;
                 if ((e_hash & HASH_MASK) != HASH_SUBHASH) {      /* a subtable */
                         break;
                 }
                 used += st->power;
                 st = *(struct hash_subtable **)e->data;
         }
         end_e = HASH_OFFSET (e, st->limit_bytes);
         while (e != end_e && (e_hash = e->hash) != HASH_NIL && e_hash < hash) {
                 e = HASH_OFFSET (e, elemsize);
         }
+        indirectkey = h->indirect & HASH_INDIRECT_KEY;
         while (e != end_e && ((e_hash = e->hash) ^ hash) < HASH_SUBHASH) {
-                if (HASH_DATA_EQ (eq, t, h, data, e->data)) {    /* a match */
-                        if (h->indirectval)
+                void *k = e->data;
+                if (indirectkey)
+                        k = *(void**)k;
+                if (HASH_DATA_EQ (eq, t, h, data, k)) {    /* a match */
+                        if (indirectkey)
+                                free (k);
+                        if (h->indirect & HASH_INDIRECT_VAL)
                                 free (*(void**)((byte*)e->data + h->valoff));
                         hash_remove_n (st, e, 1);
                         h->count--;
                         return (1);
                 }
                 e = HASH_OFFSET (e, elemsize);
         }
         USED(e_hash);
         return (0);
 }
 
 static int32
 hash_insert_internal (MapType *t, struct hash_subtable **pst, int32 flags, hash_hash_t hash,
                                  Hmap *h, void *data, void **pres)
 {
         int32 elemsize = h->datasize + offsetof (struct hash_entry, data[0]);
         bool eq;
+        bool indirectkey;
 
         if ((flags & HASH_REHASH) == 0) {
                 hash += HASH_ADJUST (hash);
                 hash &= ~HASH_MASK;
         }
+        indirectkey = h->indirect & HASH_INDIRECT_KEY;
         for (;;) {
                 struct hash_subtable *st = *pst;
                 int32 shift = HASH_BITS - (st->power + HASH_USED (flags));
                 int32 index_mask = (1 << st->power) - 1;
                 int32 i = (hash >> shift) & index_mask;    /* i is the natural position of hash */
                 struct hash_entry *start_e =
                         HASH_OFFSET (st->entry, i * elemsize);    /* start_e is the pointer to element i */
                 struct hash_entry *e = start_e;            /* e is going to range over [start_e, end_e) */
                 struct hash_entry *end_e;
                 hash_hash_t e_hash = e->hash;
 
                 if ((e_hash & HASH_MASK) == HASH_SUBHASH) {      /* a subtable */
                         pst = (struct hash_subtable **) e->data;
                         flags += HASH_MAKE_USED (st->power);
                         continue;
                 }
                 end_e = HASH_OFFSET (start_e, st->limit_bytes);
                 while (e != end_e && (e_hash = e->hash) != HASH_NIL && e_hash < hash) {
                         e = HASH_OFFSET (e, elemsize);
                         i++;
                 }
                 if (e != end_e && e_hash != HASH_NIL) {
                         /* ins_e ranges over the elements that may match */
                         struct hash_entry *ins_e = e;
                         int32 ins_i = i;
                         hash_hash_t ins_e_hash;
                         while (ins_e != end_e && ((e_hash = ins_e->hash) ^ hash) < HASH_SUBHASH) {
-                                if (HASH_DATA_EQ (eq, t, h, data, ins_e->data)) {    /* a match */
+                                void *k = ins_e->data;
+                                if (indirectkey)
+                                        k = *(void**)k;
+                                if (HASH_DATA_EQ (eq, t, h, data, k)) {    /* 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 */
                                 ins_e = HASH_OFFSET (ins_e, elemsize);
                                 ins_i++;
                                 if (e_hash <= hash) {          /* set e to insertion point */
                                         e = ins_e;
                                         i = ins_i;
@@ skipping 271 matching lines @@
 hash_visit (Hmap *h, void (*data_visit) (void *arg, int32 level, void *data), void *arg)
 {
         hash_visit_internal (h->st, 0, 0, data_visit, arg);
 }
 
 //
 /// interfaces to go runtime
 //
 
 // hash requires < 256 bytes of data (key+value) stored inline.
-// Only basic types can be key - biggest is complex128 (16 bytes).
+// Biggest basic type is complex128 (16 bytes).
 // Leave some room to grow, just in case.
 enum {
-        MaxValsize = 256 - 64
+        MaxKeysize = 64,
+        MaxValsize = 256 - MaxKeysize
 };
 
 static void**
 hash_indirect(Hmap *h, void *p)
 {
-        if(h->indirectval)
+        if(h->indirect & HASH_INDIRECT_VAL)
                 p = *(void**)p;
         return p;
 }·······
 
 static  int32   debug   = 0;
 
 // makemap(typ *Type, hint uint32) (hmap *map[any]any);
 Hmap*
 runtime·makemap_c(MapType *typ, int64 hint)
 {
         Hmap *h;
+        int32 keysize_in_hash;
         int32 valsize_in_hash;
         Type *key, *val;
 ········
         key = typ->key;
         val = typ->elem;
 
         if(hint < 0 || (int32)hint != hint)
                 runtime·panicstring("makemap: size out of range");
 
         if(key->alg->hash == runtime·nohash)
                 runtime·throw("runtime.makemap: unsupported map key type");
 
         h = runtime·mal(sizeof(*h));
 
-        valsize_in_hash = val->size;
-        if (val->size > MaxValsize) {
-                h->indirectval = 1;
+        if (key->size <= MaxKeysize)
+                keysize_in_hash = key->size;
+        else {
+                h->indirect |= HASH_INDIRECT_KEY;
+                keysize_in_hash = sizeof(void*);
+        }
+
+        if (val->size <= MaxValsize)
+                valsize_in_hash = val->size;
+        else {
+                h->indirect |= HASH_INDIRECT_VAL;
                 valsize_in_hash = sizeof(void*);
-        } 
+        }
 
         // Align value inside data so that mark-sweep gc can find it.
-        h->valoff = key->size;
-        assert(h->valoff == key->size);
+        h->valoff = keysize_in_hash;
         if(valsize_in_hash >= sizeof(void*))
                 h->valoff = runtime·rnd(key->size, sizeof(void*));
 
         hash_init(h, h->valoff+valsize_in_hash, hint);
 
         // these calculations are compiler dependent.
         // figure out offsets of map call arguments.
 
         if(debug) {
                 runtime·printf("makemap: map=%p; keysize=%p; valsize=%p; keyalg=%p; valalg=%p\n",
@@ skipping 136 matching lines @@
         if(runtime·gcwaiting)
                 runtime·gosched();
 
         if(av == nil) {
                 hash_remove(t, h, ak);
                 return;
         }
 
         res = nil;
         hit = hash_insert(t, h, ak, (void**)&res);
-        if(!hit && h->indirectval)
+        if(h->indirect&HASH_INDIRECT_KEY) {
+                if(!hit)
+                        *(void**)res = runtime·mal(t->key->size);
+                t->key->alg->copy(t->key->size, *(void**)res, ak);
+        } else
+                t->key->alg->copy(t->key->size, res, ak);
+        if(!hit && h->indirect&HASH_INDIRECT_VAL)
                 *(void**)(res+h->valoff) = runtime·mal(t->elem->size);
-        t->key->alg->copy(t->key->size, res, ak);
         t->elem->alg->copy(t->elem->size, hash_indirect(h, res+h->valoff), av);
 
         if(debug) {
                 runtime·prints("mapassign: map=");
                 runtime·printpointer(h);
                 runtime·prints("; key=");
                 t->key->alg->print(t->key->size, ak);
                 runtime·prints("; val=");
                 t->elem->alg->print(t->elem->size, av);
                 runtime·prints("; hit=");
@@ skipping 130 matching lines @@
         Hmap *h;
         byte *ak, *res;
         Type *key;
 
         h = it->h;
         ak = (byte*)(&it + 1);
 
         res = it->data;
         if(res == nil)
                 runtime·throw("runtime.mapiter1: key:val nil pointer");
+        if(h->indirect&HASH_INDIRECT_KEY)
+                res = *(void**)res;
 
         key = it->t->key;
         key->alg->copy(key->size, ak, res);
 
         if(debug) {
                 runtime·prints("mapiter2: iter=");
                 runtime·printpointer(it);
                 runtime·prints("; map=");
                 runtime·printpointer(h);
                 runtime·prints("\n");
         }
 }
 
 bool
 runtime·mapiterkey(struct hash_iter *it, void *ak)
 {
         byte *res;
         Type *key;
 
         res = it->data;
         if(res == nil)
                 return false;
+        if(it->h->indirect&HASH_INDIRECT_KEY)
+                res = *(void**)res;
         key = it->t->key;
         key->alg->copy(key->size, ak, res);
         return true;
 }
 
 // For reflect:
 //      func mapiterkey(h map) (key iword, ok bool)
 // where an iword is the same word an interface value would use:
 // the actual data if it fits, or else a pointer to the data.
 void
 reflect·mapiterkey(struct hash_iter *it, uintptr key, bool ok)
 {
         byte *res;
         Type *tkey;
 
         key = 0;
         ok = false;
         res = it->data;
         if(res == nil) {
                 key = 0;
                 ok = false;
         } else {
+                if(it->h->indirect&HASH_INDIRECT_KEY)
+                        res = *(void**)res;
                 tkey = it->t->key;
                 key = 0;
                 if(tkey->size <= sizeof(key))
                         tkey->alg->copy(tkey->size, (byte*)&key, res);
                 else
                         key = (uintptr)res;
                 ok = true;
         }
         FLUSH(&key);
         FLUSH(&ok);
@@ skipping 23 matching lines @@
 
         t = it->t;
         ak = (byte*)(&it + 1);
         av = ak + runtime·rnd(t->key->size, t->elem->align);
 
         res = it->data;
         if(res == nil)
                 runtime·throw("runtime.mapiter2: key:val nil pointer");
 
         h = it->h;
+        if(h->indirect&HASH_INDIRECT_KEY)
+                res = *(void**)res;
         t->key->alg->copy(t->key->size, ak, res);
         t->elem->alg->copy(t->elem->size, av, hash_indirect(h, res+h->valoff));
 
         if(debug) {
                 runtime·prints("mapiter2: iter=");
                 runtime·printpointer(it);
                 runtime·prints("; map=");
                 runtime·printpointer(h);
                 runtime·prints("\n");
         }
 }