runtime: new itab lookup table

Keep itabs in a growable hash table.
Use a simple open-addressable hash table, quadratic probing, power
of two sized.
Synchronization gets a bit more tricky. The common read path now
has two atomic reads, one to get the table pointer and one to read
the entry out of the table.

I set the max load factor to 75%, kind of arbitrarily. There's a
space-speed tradeoff here, and I'm not sure where we should land.

Because we use open addressing the itab.link field is no longer needed.
I'll remove it in a separate CL.

Fixes #20505

Change-Id: Ifb3d9a337512d6cf968c1fceb1eeaf89559afebf
Reviewed-on: https://go-review.googlesource.com/44472
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

3 files changed, 161 insertions, 86 deletions

diff --git a/src/runtime/iface.go b/src/runtime/iface.go
index 58ed61e3aa..3aa2fe6fde 100644
--- a/src/runtime/iface.go
+++ b/src/runtime/iface.go
@@ -10,21 +10,24 @@ import (
 	"unsafe"
 )
 
-const (
-	hashSize = 1009
-)
+const itabInitSize = 512
 
 var (
-	ifaceLock mutex // lock for accessing hash
-	hash      [hashSize]*itab
+	itabLock      mutex                               // lock for accessing itab table
+	itabTable     = &itabTableInit                    // pointer to current table
+	itabTableInit = itabTableType{size: itabInitSize} // starter table
 )
 
-func itabhash(inter *interfacetype, typ *_type) uint32 {
+//Note: change the formula in the mallocgc call in itabAdd if you change these fields.
+type itabTableType struct {
+	size    uintptr             // length of entries array. Always a power of 2.
+	count   uintptr             // current number of filled entries.
+	entries [itabInitSize]*itab // really [size] large
+}
+
+func itabHashFunc(inter *interfacetype, typ *_type) uintptr {
 	// compiler has provided some good hash codes for us.
-	h := inter.typ.hash
-	h += 17 * typ.hash
-	// TODO(rsc): h += 23 * x.mhash ?
-	return h % hashSize
+	return uintptr(inter.typ.hash ^ typ.hash)
 }
 
 func getitab(inter *interfacetype, typ *_type, canfail bool) *itab {
@@ -41,50 +44,141 @@ func getitab(inter *interfacetype, typ *_type, canfail bool) *itab {
 		panic(&TypeAssertionError{"", typ.string(), inter.typ.string(), name.name()})
 	}
 
-	h := itabhash(inter, typ)
-
-	// look twice - once without lock, once with.
-	// common case will be no lock contention.
 	var m *itab
-	var locked int
-	for locked = 0; locked < 2; locked++ {
-		if locked != 0 {
-			lock(&ifaceLock)
-		}
-		for m = (*itab)(atomic.Loadp(unsafe.Pointer(&hash[h]))); m != nil; m = m.link {
-			if m.inter == inter && m._type == typ {
-				if m.bad {
-					if !canfail {
-						// this can only happen if the conversion
-						// was already done once using the , ok form
-						// and we have a cached negative result.
-						// the cached result doesn't record which
-						// interface function was missing, so try
-						// adding the itab again, which will throw an error.
-						additab(m, locked != 0, false)
-					}
-					m = nil
-				}
-				if locked != 0 {
-					unlock(&ifaceLock)
-				}
-				return m
-			}
-		}
+
+	// First, look in the existing table to see if we can find the itab we need.
+	// This is by far the most common case, so do it without locks.
+	// Use atomic to ensure we see any previous writes done by the thread
+	// that updates the itabTable field (with atomic.Storep in addItab).
+	t := (*itabTableType)(atomic.Loadp(unsafe.Pointer(&itabTable)))
+	if m = t.find(inter, typ); m != nil {
+		goto finish
 	}
 
+	// Not found.  Grab the lock and try again.
+	lock(&itabLock)
+	if m = itabTable.find(inter, typ); m != nil {
+		unlock(&itabLock)
+		goto finish
+	}
+
+	// Entry doesn't exist yet. Make a new entry & add it.
 	m = (*itab)(persistentalloc(unsafe.Sizeof(itab{})+uintptr(len(inter.mhdr)-1)*sys.PtrSize, 0, &memstats.other_sys))
 	m.inter = inter
 	m._type = typ
-	additab(m, true, canfail)
-	unlock(&ifaceLock)
-	if m.bad {
+	m.init()
+	itabAdd(m)
+	unlock(&itabLock)
+finish:
+	if !m.bad {
+		return m
+	}
+	if canfail {
 		return nil
 	}
-	return m
+	// this can only happen if the conversion
+	// was already done once using the , ok form
+	// and we have a cached negative result.
+	// The cached result doesn't record which
+	// interface function was missing, so initialize
+	// the itab again to get the missing function name.
+	panic(&TypeAssertionError{concreteString: typ.string(), assertedString: inter.typ.string(), missingMethod: m.init()})
+}
+
+// itabFind finds the given interface/type pair in t.
+// Returns nil if the given interface/type pair isn't present.
+func (t *itabTableType) find(inter *interfacetype, typ *_type) *itab {
+	// Implemented using quadratic probing.
+	// Probe sequence is h(i) = h0 + i*(i+1)/2 mod 2^k.
+	// We're guaranteed to hit all table entries using this probe sequence.
+	mask := t.size - 1
+	h := itabHashFunc(inter, typ) & mask
+	for i := uintptr(1); ; i++ {
+		p := (**itab)(add(unsafe.Pointer(&t.entries), h*sys.PtrSize))
+		// Use atomic read here so if we see m != nil, we also see
+		// the initializations of the fields of m.
+		// m := *p
+		m := (*itab)(atomic.Loadp(unsafe.Pointer(p)))
+		if m == nil {
+			return nil
+		}
+		if m.inter == inter && m._type == typ {
+			return m
+		}
+		h += i
+		h &= mask
+	}
+}
+
+// itabAdd adds the given itab to the itab hash table.
+// itabLock must be held.
+func itabAdd(m *itab) {
+	t := itabTable
+	if t.count >= 3*(t.size/4) { // 75% load factor
+		// Grow hash table. Use an atomic write: see comment in getitab.
+		// t2 = new(itabTableType) + some additional entries
+		// We lie and tell malloc we want pointer-free memory because
+		// all the pointed-to values are not in the heap.
+		t2 := (*itabTableType)(mallocgc((2+2*t.size)*sys.PtrSize, nil, true))
+		t2.size = t.size * 2
+		atomicstorep(unsafe.Pointer(&itabTable), unsafe.Pointer(t2))
+
+		// Copy over entries.
+		// Note: while copying, other threads may look for an itab and
+		// fail to find it. That's ok, they will then try to get the itab lock
+		// and as a consequence wait until this copying is complete.
+		for i := uintptr(0); i < t.size; i++ {
+			if m2 := *(**itab)(add(unsafe.Pointer(&t.entries), i*sys.PtrSize)); m2 != nil {
+				itabAdd(m2)
+			}
+		}
+		if itabTable.count != t.count {
+			throw("mismatched count during itab table copy")
+		}
+		// Adopt the new table as our own.
+		t = itabTable
+		// Note: the old table can be GC'ed here.
+	}
+	// See comment in itabFind about the probe sequence.
+	// Insert new itab in the first empty spot in the probe sequence.
+	mask := t.size - 1
+	h := itabHashFunc(m.inter, m._type) & mask
+	for i := uintptr(1); ; i++ {
+		p := (**itab)(add(unsafe.Pointer(&t.entries), h*sys.PtrSize))
+		m2 := *p
+		if m2 == m {
+			// A given itab may be used in more than one module
+			// and thanks to the way global symbol resolution works, the
+			// pointed-to itab may already have been inserted into the
+			// global 'hash'.
+			return
+		}
+		if m2 == nil {
+			// Use atomic write here so if a reader sees m, it also
+			// sees the correctly initialized fields of m.
+			// NoWB is ok because m is not in heap memory.
+			// *p = m
+			atomic.StorepNoWB(unsafe.Pointer(p), unsafe.Pointer(m))
+			t.count++
+			return
+		}
+		h += i
+		h &= mask
+	}
+}
+
+// Adds m to the set of initial itabs.
+// itabLock must be held.
+func itabAddStartup(m *itab) {
+	m.init() // TODO: remove after CL 44341
+	itabAdd(m)
 }
 
-func additab(m *itab, locked, canfail bool) {
+// init fills in the m.fun array with all the code pointers for
+// the m.inter/m._type pair. If the type does not implement the interface,
+// it sets m.fun[0] to 0 and returns the name of an interface function that is missing.
+// It is ok to call this multiple times on the same m, even concurrently.
+func (m *itab) init() string {
 	inter := m.inter
 	typ := m._type
 	x := typ.uncommon()
@@ -97,6 +191,7 @@ func additab(m *itab, locked, canfail bool) {
 	nt := int(x.mcount)
 	xmhdr := (*[1 << 16]method)(add(unsafe.Pointer(x), uintptr(x.moff)))[:nt:nt]
 	j := 0
+imethods:
 	for k := 0; k < ni; k++ {
 		i := &inter.mhdr[k]
 		itype := inter.typ.typeOff(i.ityp)
@@ -119,45 +214,25 @@ func additab(m *itab, locked, canfail bool) {
 						ifn := typ.textOff(t.ifn)
 						*(*unsafe.Pointer)(add(unsafe.Pointer(&m.fun[0]), uintptr(k)*sys.PtrSize)) = ifn
 					}
-					goto nextimethod
+					continue imethods
 				}
 			}
 		}
 		// didn't find method
-		if !canfail {
-			if locked {
-				unlock(&ifaceLock)
-			}
-			panic(&TypeAssertionError{"", typ.string(), inter.typ.string(), iname})
-		}
 		m.bad = true
-		break
-	nextimethod:
+		return iname
 	}
-	if !locked {
-		throw("invalid itab locking")
-	}
-	h := itabhash(inter, typ)
-	m.link = hash[h]
-	m.inhash = true
-	atomicstorep(unsafe.Pointer(&hash[h]), unsafe.Pointer(m))
+	return ""
 }
 
 func itabsinit() {
-	lock(&ifaceLock)
+	lock(&itabLock)
 	for _, md := range activeModules() {
 		for _, i := range md.itablinks {
-			// itablinks is a slice of pointers to the itabs used in this
-			// module. A given itab may be used in more than one module
-			// and thanks to the way global symbol resolution works, the
-			// pointed-to itab may already have been inserted into the
-			// global 'hash'.
-			if !i.inhash {
-				additab(i, true, false)
-			}
+			itabAddStartup(i)
 		}
 	}
-	unlock(&ifaceLock)
+	unlock(&itabLock)
 }
 
 // panicdottypeE is called when doing an e.(T) conversion and the conversion fails.
@@ -533,9 +608,12 @@ func reflect_ifaceE2I(inter *interfacetype, e eface, dst *iface) {
 }
 
 func iterate_itabs(fn func(*itab)) {
-	for _, h := range &hash {
-		for ; h != nil; h = h.link {
-			fn(h)
+	// Note: only runs during stop the world, so no locks/atomics needed.
+	t := itabTable
+	for i := uintptr(0); i < t.size; i++ {
+		m := *(**itab)(add(unsafe.Pointer(&t.entries), i*sys.PtrSize))
+		if m != nil {
+			fn(m)
 		}
 	}
 }
diff --git a/src/runtime/plugin.go b/src/runtime/plugin.go
index 682caacb21..34b306ae25 100644
--- a/src/runtime/plugin.go
+++ b/src/runtime/plugin.go
@@ -54,13 +54,11 @@ func plugin_lastmoduleinit() (path string, syms map[string]interface{}, mismatch
 	pluginftabverify(md)
 	moduledataverify1(md)
 
-	lock(&ifaceLock)
+	lock(&itabLock)
 	for _, i := range md.itablinks {
-		if !i.inhash {
-			additab(i, true, false)
-		}
+		itabAddStartup(i)
 	}
-	unlock(&ifaceLock)
+	unlock(&itabLock)
 
 	// Build a map of symbol names to symbols. Here in the runtime
 	// we fill out the first word of the interface, the type. We
diff --git a/src/runtime/runtime2.go b/src/runtime/runtime2.go
index adfdec6eac..456b650f5c 100644
--- a/src/runtime/runtime2.go
+++ b/src/runtime/runtime2.go
@@ -624,14 +624,13 @@ type _func struct {
 // Needs to be in sync with
 // ../cmd/compile/internal/gc/reflect.go:/^func.dumptypestructs.
 type itab struct {
-	inter  *interfacetype
-	_type  *_type
-	link   *itab
-	hash   uint32 // copy of _type.hash. Used for type switches.
-	bad    bool   // type does not implement interface
-	inhash bool   // has this itab been added to hash?
-	unused [2]byte
-	fun    [1]uintptr // variable sized
+	inter *interfacetype
+	_type *_type
+	_     uintptr
+	hash  uint32 // copy of _type.hash. Used for type switches.
+	bad   bool   // type does not implement interface
+	_     [3]byte
+	fun   [1]uintptr // variable sized
 }
 
 // Lock-free stack node.