From 8f9bfa9b7b7739324e73b4f19280caa2011e6ae8 Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Wed, 11 May 2022 15:11:29 -0400 Subject: crypto/internal/boring: factor Cache into crypto/internal/boring/bcache Requested by the maintainers of the OpenSSL-based fork of Go+BoringCrypto, to make maintaining that fork easier. Change-Id: I770e70ecc12b589034da31edecf59c73b2c6e1dd Reviewed-on: https://go-review.googlesource.com/c/go/+/407135 Run-TryBot: Russ Cox TryBot-Result: Gopher Robot Reviewed-by: Ian Lance Taylor Auto-Submit: Russ Cox --- src/crypto/ecdsa/boring.go | 5 +- src/crypto/internal/boring/bcache/cache.go | 141 ++++++++++++++++++++++++ src/crypto/internal/boring/bcache/cache_test.go | 120 ++++++++++++++++++++ src/crypto/internal/boring/bcache/stub.s | 6 + src/crypto/internal/boring/cache.go | 140 ----------------------- src/crypto/internal/boring/cache_test.go | 120 -------------------- src/crypto/internal/boring/stub.s | 6 - src/crypto/rsa/boring.go | 5 +- src/go/build/deps_test.go | 7 +- src/runtime/mgc.go | 2 +- 10 files changed, 279 insertions(+), 273 deletions(-) create mode 100644 src/crypto/internal/boring/bcache/cache.go create mode 100644 src/crypto/internal/boring/bcache/cache_test.go create mode 100644 src/crypto/internal/boring/bcache/stub.s delete mode 100644 src/crypto/internal/boring/cache.go delete mode 100644 src/crypto/internal/boring/cache_test.go delete mode 100644 src/crypto/internal/boring/stub.s (limited to 'src') diff --git a/src/crypto/ecdsa/boring.go b/src/crypto/ecdsa/boring.go index edb723fe0e..4495730b84 100644 --- a/src/crypto/ecdsa/boring.go +++ b/src/crypto/ecdsa/boring.go @@ -9,6 +9,7 @@ package ecdsa import ( "crypto/internal/boring" "crypto/internal/boring/bbig" + "crypto/internal/boring/bcache" "math/big" "unsafe" ) @@ -26,8 +27,8 @@ import ( // still matches before using the cached key. The theory is that the real // operations are significantly more expensive than the comparison. -var pubCache boring.Cache -var privCache boring.Cache +var pubCache bcache.Cache +var privCache bcache.Cache func init() { pubCache.Register() diff --git a/src/crypto/internal/boring/bcache/cache.go b/src/crypto/internal/boring/bcache/cache.go new file mode 100644 index 0000000000..c0b9d7bf2a --- /dev/null +++ b/src/crypto/internal/boring/bcache/cache.go @@ -0,0 +1,141 @@ +// Copyright 2022 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. + +// Package bcache implements a GC-friendly cache (see [Cache]) for BoringCrypto. +package bcache + +import ( + "sync/atomic" + "unsafe" +) + +// A Cache is a GC-friendly concurrent map from unsafe.Pointer to +// unsafe.Pointer. It is meant to be used for maintaining shadow +// BoringCrypto state associated with certain allocated structs, in +// particular public and private RSA and ECDSA keys. +// +// The cache is GC-friendly in the sense that the keys do not +// indefinitely prevent the garbage collector from collecting them. +// Instead, at the start of each GC, the cache is cleared entirely. That +// is, the cache is lossy, and the loss happens at the start of each GC. +// This means that clients need to be able to cope with cache entries +// disappearing, but it also means that clients don't need to worry about +// cache entries keeping the keys from being collected. +// +// TODO(rsc): Make Cache generic once consumers can handle that. +type Cache struct { + // ptable is an atomic *[cacheSize]unsafe.Pointer, + // where each unsafe.Pointer is an atomic *cacheEntry. + // The runtime atomically stores nil to ptable at the start of each GC. + ptable unsafe.Pointer +} + +// A cacheEntry is a single entry in the linked list for a given hash table entry. +type cacheEntry struct { + k unsafe.Pointer // immutable once created + v unsafe.Pointer // read and written atomically to allow updates + next *cacheEntry // immutable once linked into table +} + +func registerCache(unsafe.Pointer) // provided by runtime + +// Register registers the cache with the runtime, +// so that c.ptable can be cleared at the start of each GC. +// Register must be called during package initialization. +func (c *Cache) Register() { + registerCache(unsafe.Pointer(&c.ptable)) +} + +// cacheSize is the number of entries in the hash table. +// The hash is the pointer value mod cacheSize, a prime. +// Collisions are resolved by maintaining a linked list in each hash slot. +const cacheSize = 1021 + +// table returns a pointer to the current cache hash table, +// coping with the possibility of the GC clearing it out from under us. +func (c *Cache) table() *[cacheSize]unsafe.Pointer { + for { + p := atomic.LoadPointer(&c.ptable) + if p == nil { + p = unsafe.Pointer(new([cacheSize]unsafe.Pointer)) + if !atomic.CompareAndSwapPointer(&c.ptable, nil, p) { + continue + } + } + return (*[cacheSize]unsafe.Pointer)(p) + } +} + +// Clear clears the cache. +// The runtime does this automatically at each garbage collection; +// this method is exposed only for testing. +func (c *Cache) Clear() { + // The runtime does this at the start of every garbage collection + // (itself, not by calling this function). + atomic.StorePointer(&c.ptable, nil) +} + +// Get returns the cached value associated with v, +// which is either the value v corresponding to the most recent call to Put(k, v) +// or nil if that cache entry has been dropped. +func (c *Cache) Get(k unsafe.Pointer) unsafe.Pointer { + head := &c.table()[uintptr(k)%cacheSize] + e := (*cacheEntry)(atomic.LoadPointer(head)) + for ; e != nil; e = e.next { + if e.k == k { + return atomic.LoadPointer(&e.v) + } + } + return nil +} + +// Put sets the cached value associated with k to v. +func (c *Cache) Put(k, v unsafe.Pointer) { + head := &c.table()[uintptr(k)%cacheSize] + + // Strategy is to walk the linked list at head, + // same as in Get, to look for existing entry. + // If we find one, we update v atomically in place. + // If not, then we race to replace the start = *head + // we observed with a new k, v entry. + // If we win that race, we're done. + // Otherwise, we try the whole thing again, + // with two optimizations: + // + // 1. We track in noK the start of the section of + // the list that we've confirmed has no entry for k. + // The next time down the list, we can stop at noK, + // because new entries are inserted at the front of the list. + // This guarantees we never traverse an entry + // multiple times. + // + // 2. We only allocate the entry to be added once, + // saving it in add for the next attempt. + var add, noK *cacheEntry + n := 0 + for { + e := (*cacheEntry)(atomic.LoadPointer(head)) + start := e + for ; e != nil && e != noK; e = e.next { + if e.k == k { + atomic.StorePointer(&e.v, v) + return + } + n++ + } + if add == nil { + add = &cacheEntry{k, v, nil} + } + add.next = start + if n >= 1000 { + // If an individual list gets too long, which shouldn't happen, + // throw it away to avoid quadratic lookup behavior. + add.next = nil + } + if atomic.CompareAndSwapPointer(head, unsafe.Pointer(start), unsafe.Pointer(add)) { + return + } + noK = start + } +} diff --git a/src/crypto/internal/boring/bcache/cache_test.go b/src/crypto/internal/boring/bcache/cache_test.go new file mode 100644 index 0000000000..8b2cf3d094 --- /dev/null +++ b/src/crypto/internal/boring/bcache/cache_test.go @@ -0,0 +1,120 @@ +// Copyright 2022 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. + +package bcache + +import ( + "fmt" + "runtime" + "sync" + "sync/atomic" + "testing" + "unsafe" +) + +var registeredCache Cache + +func init() { + registeredCache.Register() +} + +func TestCache(t *testing.T) { + // Use unregistered cache for functionality tests, + // to keep the runtime from clearing behind our backs. + c := new(Cache) + + // Create many entries. + seq := uint32(0) + next := func() unsafe.Pointer { + x := new(int) + *x = int(atomic.AddUint32(&seq, 1)) + return unsafe.Pointer(x) + } + m := make(map[unsafe.Pointer]unsafe.Pointer) + for i := 0; i < 10000; i++ { + k := next() + v := next() + m[k] = v + c.Put(k, v) + } + + // Overwrite a random 20% of those. + n := 0 + for k := range m { + v := next() + m[k] = v + c.Put(k, v) + if n++; n >= 2000 { + break + } + } + + // Check results. + str := func(p unsafe.Pointer) string { + if p == nil { + return "nil" + } + return fmt.Sprint(*(*int)(p)) + } + for k, v := range m { + if cv := c.Get(k); cv != v { + t.Fatalf("c.Get(%v) = %v, want %v", str(k), str(cv), str(v)) + } + } + + c.Clear() + for k := range m { + if cv := c.Get(k); cv != nil { + t.Fatalf("after GC, c.Get(%v) = %v, want nil", str(k), str(cv)) + } + } + + // Check that registered cache is cleared at GC. + c = ®isteredCache + for k, v := range m { + c.Put(k, v) + } + runtime.GC() + for k := range m { + if cv := c.Get(k); cv != nil { + t.Fatalf("after Clear, c.Get(%v) = %v, want nil", str(k), str(cv)) + } + } + + // Check that cache works for concurrent access. + // Lists are discarded if they reach 1000 entries, + // and there are cacheSize list heads, so we should be + // able to do 100 * cacheSize entries with no problem at all. + c = new(Cache) + var barrier, wg sync.WaitGroup + const N = 100 + barrier.Add(N) + wg.Add(N) + var lost int32 + for i := 0; i < N; i++ { + go func() { + defer wg.Done() + + m := make(map[unsafe.Pointer]unsafe.Pointer) + for j := 0; j < cacheSize; j++ { + k, v := next(), next() + m[k] = v + c.Put(k, v) + } + barrier.Done() + barrier.Wait() + + for k, v := range m { + if cv := c.Get(k); cv != v { + t.Errorf("c.Get(%v) = %v, want %v", str(k), str(cv), str(v)) + atomic.AddInt32(&lost, +1) + } + } + }() + } + wg.Wait() + if lost != 0 { + t.Errorf("lost %d entries", lost) + } +} diff --git a/src/crypto/internal/boring/bcache/stub.s b/src/crypto/internal/boring/bcache/stub.s new file mode 100644 index 0000000000..59f2deeb60 --- /dev/null +++ b/src/crypto/internal/boring/bcache/stub.s @@ -0,0 +1,6 @@ +// Copyright 2022 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. + +// This file is here to silence an error about registerCache not having a body. +// (The body is provided by package runtime.) diff --git a/src/crypto/internal/boring/cache.go b/src/crypto/internal/boring/cache.go deleted file mode 100644 index 476e47706c..0000000000 --- a/src/crypto/internal/boring/cache.go +++ /dev/null @@ -1,140 +0,0 @@ -// Copyright 2022 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. - -package boring - -import ( - "sync/atomic" - "unsafe" -) - -// A Cache is a GC-friendly concurrent map from unsafe.Pointer to -// unsafe.Pointer. It is meant to be used for maintaining shadow -// BoringCrypto state associated with certain allocated structs, in -// particular public and private RSA and ECDSA keys. -// -// The cache is GC-friendly in the sense that the keys do not -// indefinitely prevent the garbage collector from collecting them. -// Instead, at the start of each GC, the cache is cleared entirely. That -// is, the cache is lossy, and the loss happens at the start of each GC. -// This means that clients need to be able to cope with cache entries -// disappearing, but it also means that clients don't need to worry about -// cache entries keeping the keys from being collected. -// -// TODO(rsc): Make Cache generic once consumers can handle that. -type Cache struct { - // ptable is an atomic *[cacheSize]unsafe.Pointer, - // where each unsafe.Pointer is an atomic *cacheEntry. - // The runtime atomically stores nil to ptable at the start of each GC. - ptable unsafe.Pointer -} - -// A cacheEntry is a single entry in the linked list for a given hash table entry. -type cacheEntry struct { - k unsafe.Pointer // immutable once created - v unsafe.Pointer // read and written atomically to allow updates - next *cacheEntry // immutable once linked into table -} - -func registerCache(unsafe.Pointer) // provided by runtime - -// Register registers the cache with the runtime, -// so that c.ptable can be cleared at the start of each GC. -// Register must be called during package initialization. -func (c *Cache) Register() { - registerCache(unsafe.Pointer(&c.ptable)) -} - -// cacheSize is the number of entries in the hash table. -// The hash is the pointer value mod cacheSize, a prime. -// Collisions are resolved by maintaining a linked list in each hash slot. -const cacheSize = 1021 - -// table returns a pointer to the current cache hash table, -// coping with the possibility of the GC clearing it out from under us. -func (c *Cache) table() *[cacheSize]unsafe.Pointer { - for { - p := atomic.LoadPointer(&c.ptable) - if p == nil { - p = unsafe.Pointer(new([cacheSize]unsafe.Pointer)) - if !atomic.CompareAndSwapPointer(&c.ptable, nil, p) { - continue - } - } - return (*[cacheSize]unsafe.Pointer)(p) - } -} - -// Clear clears the cache. -// The runtime does this automatically at each garbage collection; -// this method is exposed only for testing. -func (c *Cache) Clear() { - // The runtime does this at the start of every garbage collection - // (itself, not by calling this function). - atomic.StorePointer(&c.ptable, nil) -} - -// Get returns the cached value associated with v, -// which is either the value v corresponding to the most recent call to Put(k, v) -// or nil if that cache entry has been dropped. -func (c *Cache) Get(k unsafe.Pointer) unsafe.Pointer { - head := &c.table()[uintptr(k)%cacheSize] - e := (*cacheEntry)(atomic.LoadPointer(head)) - for ; e != nil; e = e.next { - if e.k == k { - return atomic.LoadPointer(&e.v) - } - } - return nil -} - -// Put sets the cached value associated with k to v. -func (c *Cache) Put(k, v unsafe.Pointer) { - head := &c.table()[uintptr(k)%cacheSize] - - // Strategy is to walk the linked list at head, - // same as in Get, to look for existing entry. - // If we find one, we update v atomically in place. - // If not, then we race to replace the start = *head - // we observed with a new k, v entry. - // If we win that race, we're done. - // Otherwise, we try the whole thing again, - // with two optimizations: - // - // 1. We track in noK the start of the section of - // the list that we've confirmed has no entry for k. - // The next time down the list, we can stop at noK, - // because new entries are inserted at the front of the list. - // This guarantees we never traverse an entry - // multiple times. - // - // 2. We only allocate the entry to be added once, - // saving it in add for the next attempt. - var add, noK *cacheEntry - n := 0 - for { - e := (*cacheEntry)(atomic.LoadPointer(head)) - start := e - for ; e != nil && e != noK; e = e.next { - if e.k == k { - atomic.StorePointer(&e.v, v) - return - } - n++ - } - if add == nil { - add = &cacheEntry{k, v, nil} - } - add.next = start - if n >= 1000 { - // If an individual list gets too long, which shouldn't happen, - // throw it away to avoid quadratic lookup behavior. - add.next = nil - } - if atomic.CompareAndSwapPointer(head, unsafe.Pointer(start), unsafe.Pointer(add)) { - return - } - noK = start - } -} diff --git a/src/crypto/internal/boring/cache_test.go b/src/crypto/internal/boring/cache_test.go deleted file mode 100644 index f9ccb74f6f..0000000000 --- a/src/crypto/internal/boring/cache_test.go +++ /dev/null @@ -1,120 +0,0 @@ -// Copyright 2022 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. - -package boring - -import ( - "fmt" - "runtime" - "sync" - "sync/atomic" - "testing" - "unsafe" -) - -var registeredCache Cache - -func init() { - registeredCache.Register() -} - -func TestCache(t *testing.T) { - // Use unregistered cache for functionality tests, - // to keep the runtime from clearing behind our backs. - c := new(Cache) - - // Create many entries. - seq := uint32(0) - next := func() unsafe.Pointer { - x := new(int) - *x = int(atomic.AddUint32(&seq, 1)) - return unsafe.Pointer(x) - } - m := make(map[unsafe.Pointer]unsafe.Pointer) - for i := 0; i < 10000; i++ { - k := next() - v := next() - m[k] = v - c.Put(k, v) - } - - // Overwrite a random 20% of those. - n := 0 - for k := range m { - v := next() - m[k] = v - c.Put(k, v) - if n++; n >= 2000 { - break - } - } - - // Check results. - str := func(p unsafe.Pointer) string { - if p == nil { - return "nil" - } - return fmt.Sprint(*(*int)(p)) - } - for k, v := range m { - if cv := c.Get(k); cv != v { - t.Fatalf("c.Get(%v) = %v, want %v", str(k), str(cv), str(v)) - } - } - - c.Clear() - for k := range m { - if cv := c.Get(k); cv != nil { - t.Fatalf("after GC, c.Get(%v) = %v, want nil", str(k), str(cv)) - } - } - - // Check that registered cache is cleared at GC. - c = ®isteredCache - for k, v := range m { - c.Put(k, v) - } - runtime.GC() - for k := range m { - if cv := c.Get(k); cv != nil { - t.Fatalf("after Clear, c.Get(%v) = %v, want nil", str(k), str(cv)) - } - } - - // Check that cache works for concurrent access. - // Lists are discarded if they reach 1000 entries, - // and there are cacheSize list heads, so we should be - // able to do 100 * cacheSize entries with no problem at all. - c = new(Cache) - var barrier, wg sync.WaitGroup - const N = 100 - barrier.Add(N) - wg.Add(N) - var lost int32 - for i := 0; i < N; i++ { - go func() { - defer wg.Done() - - m := make(map[unsafe.Pointer]unsafe.Pointer) - for j := 0; j < cacheSize; j++ { - k, v := next(), next() - m[k] = v - c.Put(k, v) - } - barrier.Done() - barrier.Wait() - - for k, v := range m { - if cv := c.Get(k); cv != v { - t.Errorf("c.Get(%v) = %v, want %v", str(k), str(cv), str(v)) - atomic.AddInt32(&lost, +1) - } - } - }() - } - wg.Wait() - if lost != 0 { - t.Errorf("lost %d entries", lost) - } -} diff --git a/src/crypto/internal/boring/stub.s b/src/crypto/internal/boring/stub.s deleted file mode 100644 index 59f2deeb60..0000000000 --- a/src/crypto/internal/boring/stub.s +++ /dev/null @@ -1,6 +0,0 @@ -// Copyright 2022 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. - -// This file is here to silence an error about registerCache not having a body. -// (The body is provided by package runtime.) diff --git a/src/crypto/rsa/boring.go b/src/crypto/rsa/boring.go index fc2842fb34..9b1db564c3 100644 --- a/src/crypto/rsa/boring.go +++ b/src/crypto/rsa/boring.go @@ -9,6 +9,7 @@ package rsa import ( "crypto/internal/boring" "crypto/internal/boring/bbig" + "crypto/internal/boring/bcache" "math/big" "unsafe" ) @@ -31,8 +32,8 @@ type boringPub struct { orig PublicKey } -var pubCache boring.Cache -var privCache boring.Cache +var pubCache bcache.Cache +var privCache bcache.Cache func init() { pubCache.Register() diff --git a/src/go/build/deps_test.go b/src/go/build/deps_test.go index 5b971b93e2..84cc9de8e7 100644 --- a/src/go/build/deps_test.go +++ b/src/go/build/deps_test.go @@ -393,7 +393,7 @@ var depsRules = ` < net/mail; NONE < crypto/internal/boring/sig, crypto/internal/boring/syso; - sync/atomic < crypto/internal/boring/fipstls; + sync/atomic < crypto/internal/boring/bcache, crypto/internal/boring/fipstls; crypto/internal/boring/sig, crypto/internal/boring/fipstls < crypto/tls/fipsonly; # CRYPTO is core crypto algorithms - no cgo, fmt, net. @@ -410,7 +410,10 @@ var depsRules = ` < crypto/internal/nistec < crypto/internal/edwards25519/field, golang.org/x/crypto/curve25519/internal/field < crypto/internal/edwards25519 - < crypto/cipher + < crypto/cipher; + + crypto/cipher, + crypto/internal/boring/bcache < crypto/internal/boring < crypto/boring < crypto/aes, crypto/des, crypto/hmac, crypto/md5, crypto/rc4, diff --git a/src/runtime/mgc.go b/src/runtime/mgc.go index 9b25948255..63e04636d7 100644 --- a/src/runtime/mgc.go +++ b/src/runtime/mgc.go @@ -1579,7 +1579,7 @@ func sync_runtime_registerPoolCleanup(f func()) { poolcleanup = f } -//go:linkname boring_registerCache crypto/internal/boring.registerCache +//go:linkname boring_registerCache crypto/internal/boring/bcache.registerCache func boring_registerCache(p unsafe.Pointer) { boringCaches = append(boringCaches, p) } -- cgit v1.3-5-g9baa