Add //pkg/sync:generic_atomicptrmap.

AtomicPtrMap is a generic concurrent map from arbitrary keys to arbitrary
pointer values.

Benchmarks:
name                                                            time/op
StoreDelete/RWMutexMap-12                                        335ns ± 1%
StoreDelete/SyncMap-12                                           705ns ± 3%
StoreDelete/AtomicPtrMap-12                                      287ns ± 4%
StoreDelete/AtomicPtrMapSharded-12                               289ns ± 1%
LoadOrStoreDelete/RWMutexMap-12                                  342ns ± 2%
LoadOrStoreDelete/SyncMap-12                                     662ns ± 2%
LoadOrStoreDelete/AtomicPtrMap-12                                290ns ± 7%
LoadOrStoreDelete/AtomicPtrMapSharded-12                         293ns ± 2%
LookupPositive/RWMutexMap-12                                     101ns ±26%
LookupPositive/SyncMap-12                                        202ns ± 2%
LookupPositive/AtomicPtrMap-12                                  71.1ns ± 2%
LookupPositive/AtomicPtrMapSharded-12                           73.2ns ± 1%
LookupNegative/RWMutexMap-12                                     119ns ± 1%
LookupNegative/SyncMap-12                                        154ns ± 1%
LookupNegative/AtomicPtrMap-12                                  84.7ns ± 3%
LookupNegative/AtomicPtrMapSharded-12                           86.8ns ± 1%
Concurrent/FixedKeys_1PercentWrites_RWMutexMap-12               1.32µs ± 2%
Concurrent/FixedKeys_1PercentWrites_SyncMap-12                  52.7ns ±10%
Concurrent/FixedKeys_1PercentWrites_AtomicPtrMap-12             31.8ns ±20%
Concurrent/FixedKeys_1PercentWrites_AtomicPtrMapSharded-12      24.0ns ±15%
Concurrent/FixedKeys_10PercentWrites_RWMutexMap-12               860ns ± 3%
Concurrent/FixedKeys_10PercentWrites_SyncMap-12                 68.8ns ±20%
Concurrent/FixedKeys_10PercentWrites_AtomicPtrMap-12            98.6ns ± 7%
Concurrent/FixedKeys_10PercentWrites_AtomicPtrMapSharded-12     42.0ns ±25%
Concurrent/FixedKeys_50PercentWrites_RWMutexMap-12              1.17µs ± 3%
Concurrent/FixedKeys_50PercentWrites_SyncMap-12                  136ns ±34%
Concurrent/FixedKeys_50PercentWrites_AtomicPtrMap-12             286ns ± 3%
Concurrent/FixedKeys_50PercentWrites_AtomicPtrMapSharded-12      115ns ±35%
Concurrent/ChangingKeys_1PercentWrites_RWMutexMap-12            1.27µs ± 2%
Concurrent/ChangingKeys_1PercentWrites_SyncMap-12               5.01µs ± 3%
Concurrent/ChangingKeys_1PercentWrites_AtomicPtrMap-12          38.1ns ± 3%
Concurrent/ChangingKeys_1PercentWrites_AtomicPtrMapSharded-12   22.6ns ± 2%
Concurrent/ChangingKeys_10PercentWrites_RWMutexMap-12           1.08µs ± 2%
Concurrent/ChangingKeys_10PercentWrites_SyncMap-12              5.97µs ± 1%
Concurrent/ChangingKeys_10PercentWrites_AtomicPtrMap-12          390ns ± 2%
Concurrent/ChangingKeys_10PercentWrites_AtomicPtrMapSharded-12  93.6ns ± 1%
Concurrent/ChangingKeys_50PercentWrites_RWMutexMap-12           1.77µs ± 2%
Concurrent/ChangingKeys_50PercentWrites_SyncMap-12              8.07µs ± 2%
Concurrent/ChangingKeys_50PercentWrites_AtomicPtrMap-12         1.61µs ± 2%
Concurrent/ChangingKeys_50PercentWrites_AtomicPtrMapSharded-12   386ns ± 1%

Updates #231

PiperOrigin-RevId: 346614776

2 files changed, 19 insertions, 23 deletions

diff --git a/pkg/sentry/vfs/mount_unsafe.go b/pkg/sentry/vfs/mount_unsafe.go
index cb48c37a1..0df023713 100644
--- a/pkg/sentry/vfs/mount_unsafe.go
+++ b/pkg/sentry/vfs/mount_unsafe.go
@@ -12,11 +12,6 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-// +build go1.12
-// +build !go1.17
-
-// Check go:linkname function signatures when updating Go version.
-
 package vfs
 
 import (
@@ -41,6 +36,15 @@ type mountKey struct {
 	point  unsafe.Pointer // *Dentry
 }
 
+var (
+	mountKeyHasher = sync.MapKeyHasher(map[mountKey]struct{}(nil))
+	mountKeySeed   = sync.RandUintptr()
+)
+
+func (k *mountKey) hash() uintptr {
+	return mountKeyHasher(gohacks.Noescape(unsafe.Pointer(k)), mountKeySeed)
+}
+
 func (mnt *Mount) parent() *Mount {
 	return (*Mount)(atomic.LoadPointer(&mnt.key.parent))
 }
@@ -56,23 +60,17 @@ func (mnt *Mount) getKey() VirtualDentry {
 	}
 }
 
-func (mnt *Mount) saveKey() VirtualDentry { return mnt.getKey() }
-
 // Invariant: mnt.key.parent == nil. vd.Ok().
 func (mnt *Mount) setKey(vd VirtualDentry) {
 	atomic.StorePointer(&mnt.key.parent, unsafe.Pointer(vd.mount))
 	atomic.StorePointer(&mnt.key.point, unsafe.Pointer(vd.dentry))
 }
 
-func (mnt *Mount) loadKey(vd VirtualDentry) { mnt.setKey(vd) }
-
 // mountTable maps (mount parent, mount point) pairs to mounts. It supports
 // efficient concurrent lookup, even in the presence of concurrent mutators
 // (provided mutation is sufficiently uncommon).
 //
 // mountTable.Init() must be called on new mountTables before use.
-//
-// +stateify savable
 type mountTable struct {
 	// mountTable is implemented as a seqcount-protected hash table that
 	// resolves collisions with linear probing, featuring Robin Hood insertion
@@ -84,8 +82,7 @@ type mountTable struct {
 	// intrinsics and inline assembly, limiting the performance of this
 	// approach.)
 
-	seq  sync.SeqCount `state:"nosave"`
-	seed uint32        // for hashing keys
+	seq sync.SeqCount `state:"nosave"`
 
 	// size holds both length (number of elements) and capacity (number of
 	// slots): capacity is stored as its base-2 log (referred to as order) in
@@ -150,7 +147,6 @@ func init() {
 
 // Init must be called exactly once on each mountTable before use.
 func (mt *mountTable) Init() {
-	mt.seed = rand32()
 	mt.size = mtInitOrder
 	mt.slots = newMountTableSlots(mtInitCap)
 }
@@ -167,7 +163,7 @@ func newMountTableSlots(cap uintptr) unsafe.Pointer {
 // Lookup may be called even if there are concurrent mutators of mt.
 func (mt *mountTable) Lookup(parent *Mount, point *Dentry) *Mount {
 	key := mountKey{parent: unsafe.Pointer(parent), point: unsafe.Pointer(point)}
-	hash := memhash(gohacks.Noescape(unsafe.Pointer(&key)), uintptr(mt.seed), mountKeyBytes)
+	hash := key.hash()
 
 loop:
 	for {
@@ -247,7 +243,7 @@ func (mt *mountTable) Insert(mount *Mount) {
 // * mt.seq must be in a writer critical section.
 // * mt must not already contain a Mount with the same mount point and parent.
 func (mt *mountTable) insertSeqed(mount *Mount) {
-	hash := memhash(unsafe.Pointer(&mount.key), uintptr(mt.seed), mountKeyBytes)
+	hash := mount.key.hash()
 
 	// We're under the maximum load factor if:
 	//
@@ -346,7 +342,7 @@ func (mt *mountTable) Remove(mount *Mount) {
 // * mt.seq must be in a writer critical section.
 // * mt must contain mount.
 func (mt *mountTable) removeSeqed(mount *Mount) {
-	hash := memhash(unsafe.Pointer(&mount.key), uintptr(mt.seed), mountKeyBytes)
+	hash := mount.key.hash()
 	tcap := uintptr(1) << (mt.size & mtSizeOrderMask)
 	mask := tcap - 1
 	slots := mt.slots
@@ -386,9 +382,3 @@ func (mt *mountTable) removeSeqed(mount *Mount) {
 		off = (off + mountSlotBytes) & offmask
 	}
 }
-
-//go:linkname memhash runtime.memhash
-func memhash(p unsafe.Pointer, seed, s uintptr) uintptr
-
-//go:linkname rand32 runtime.fastrand
-func rand32() uint32
diff --git a/pkg/sentry/vfs/save_restore.go b/pkg/sentry/vfs/save_restore.go
index 8f070ed53..8998a82dd 100644
--- a/pkg/sentry/vfs/save_restore.go
+++ b/pkg/sentry/vfs/save_restore.go
@@ -101,6 +101,9 @@ func (vfs *VirtualFilesystem) saveMounts() []*Mount {
 	return mounts
 }
 
+// saveKey is called by stateify.
+func (mnt *Mount) saveKey() VirtualDentry { return mnt.getKey() }
+
 // loadMounts is called by stateify.
 func (vfs *VirtualFilesystem) loadMounts(mounts []*Mount) {
 	if mounts == nil {
@@ -112,6 +115,9 @@ func (vfs *VirtualFilesystem) loadMounts(mounts []*Mount) {
 	}
 }
 
+// loadKey is called by stateify.
+func (mnt *Mount) loadKey(vd VirtualDentry) { mnt.setKey(vd) }
+
 func (mnt *Mount) afterLoad() {
 	if atomic.LoadInt64(&mnt.refs) != 0 {
 		refsvfs2.Register(mnt)