// 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 ( ) // 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. type Cache[, any] struct { // The runtime atomically stores nil to ptable at the start of each GC. ptable atomic.Pointer[cacheTable[, ]] } type cacheTable[, any] [cacheSize]atomic.Pointer[cacheEntry[, ]] // A cacheEntry is a single entry in the linked list for a given hash table entry. type cacheEntry[, any] struct { k * // immutable once created v atomic.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 ( *Cache[, ]) () { registerCache(unsafe.Pointer(&.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 ( *Cache[, ]) () *cacheTable[, ] { for { := .ptable.Load() if == nil { = new(cacheTable[, ]) if !.ptable.CompareAndSwap(nil, ) { continue } } return } } // Clear clears the cache. // The runtime does this automatically at each garbage collection; // this method is exposed only for testing. func ( *Cache[, ]) () { // The runtime does this at the start of every garbage collection // (itself, not by calling this function). .ptable.Store(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 ( *Cache[, ]) ( *) * { := &.table()[uintptr(unsafe.Pointer())%cacheSize] := .Load() for ; != nil; = .next { if .k == { return .v.Load() } } return nil } // Put sets the cached value associated with k to v. func ( *Cache[, ]) ( *, *) { := &.table()[uintptr(unsafe.Pointer())%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 , *cacheEntry[, ] := 0 for { := .Load() := for ; != nil && != ; = .next { if .k == { .v.Store() return } ++ } if == nil { = &cacheEntry[, ]{k: } .v.Store() } .next = if >= 1000 { // If an individual list gets too long, which shouldn't happen, // throw it away to avoid quadratic lookup behavior. .next = nil } if .CompareAndSwap(, ) { return } = } }