summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--util/deephash/deephash.go72
-rw-r--r--util/deephash/deephash_test.go36
2 files changed, 73 insertions, 35 deletions
diff --git a/util/deephash/deephash.go b/util/deephash/deephash.go
index 4da7b9ae0..d9866c289 100644
--- a/util/deephash/deephash.go
+++ b/util/deephash/deephash.go
@@ -27,20 +27,29 @@ type hasher struct {
h hash.Hash
bw *bufio.Writer
scratch [128]byte
+ visited map[uintptr]bool
}
// newHasher initializes a new hasher, for use by hasherPool.
func newHasher() *hasher {
- h := &hasher{h: sha256.New()}
+ h := &hasher{
+ h: sha256.New(),
+ visited: map[uintptr]bool{},
+ }
h.bw = bufio.NewWriterSize(h.h, h.h.BlockSize())
return h
}
+func (h *hasher) setBufioWriter(w *bufio.Writer) {
+ h.bw.Flush()
+ h.bw = w
+}
+
// Hash returns the raw SHA-256 (not hex) of v.
func (h *hasher) Hash(v interface{}) (hash [sha256.Size]byte) {
h.bw.Flush()
h.h.Reset()
- printTo(h.bw, v, h.scratch[:])
+ h.print(reflect.ValueOf(v))
h.bw.Flush()
h.h.Sum(hash[:0])
return hash
@@ -84,10 +93,6 @@ func sha256EqualHex(sum [sha256.Size]byte, hx string) bool {
return true
}
-func printTo(w *bufio.Writer, v interface{}, scratch []byte) {
- print(w, reflect.ValueOf(v), make(map[uintptr]bool), scratch)
-}
-
var appenderToType = reflect.TypeOf((*appenderTo)(nil)).Elem()
type appenderTo interface {
@@ -96,16 +101,19 @@ type appenderTo interface {
// print hashes v into w.
// It reports whether it was able to do so without hitting a cycle.
-func print(w *bufio.Writer, v reflect.Value, visited map[uintptr]bool, scratch []byte) (acyclic bool) {
+func (h *hasher) print(v reflect.Value) (acyclic bool) {
if !v.IsValid() {
return true
}
+ w := h.bw
+ visited := h.visited
+
if v.CanInterface() {
// Use AppendTo methods, if available and cheap.
if v.CanAddr() && v.Type().Implements(appenderToType) {
a := v.Addr().Interface().(appenderTo)
- scratch = a.AppendTo(scratch[:0])
+ scratch := a.AppendTo(h.scratch[:0])
w.Write(scratch)
return true
}
@@ -121,13 +129,13 @@ func print(w *bufio.Writer, v reflect.Value, visited map[uintptr]bool, scratch [
return false
}
visited[ptr] = true
- return print(w, v.Elem(), visited, scratch)
+ return h.print(v.Elem())
case reflect.Struct:
acyclic = true
w.WriteString("struct{\n")
for i, n := 0, v.NumField(); i < n; i++ {
fmt.Fprintf(w, " [%d]: ", i)
- if !print(w, v.Field(i), visited, scratch) {
+ if !h.print(v.Field(i)) {
acyclic = false
}
w.WriteString("\n")
@@ -143,7 +151,7 @@ func print(w *bufio.Writer, v reflect.Value, visited map[uintptr]bool, scratch [
acyclic = true
for i, ln := 0, v.Len(); i < ln; i++ {
fmt.Fprintf(w, " [%d]: ", i)
- if !print(w, v.Index(i), visited, scratch) {
+ if !h.print(v.Index(i)) {
acyclic = false
}
w.WriteString("\n")
@@ -151,7 +159,7 @@ func print(w *bufio.Writer, v reflect.Value, visited map[uintptr]bool, scratch [
w.WriteString("}\n")
return acyclic
case reflect.Interface:
- return print(w, v.Elem(), visited, scratch)
+ return h.print(v.Elem())
case reflect.Map:
// TODO(bradfitz): ideally we'd avoid these map
// operations to detect cycles if we knew from the map
@@ -175,22 +183,24 @@ func print(w *bufio.Writer, v reflect.Value, visited map[uintptr]bool, scratch [
}
visited[ptr] = true
- if hashMapAcyclic(w, v, visited, scratch) {
+ vlen0 := len(visited)
+ if false && h.hashMapAcyclic(v) {
return true
}
- return hashMapFallback(w, v, visited, scratch)
+ if len(visited) != vlen0 {
+ panic("it grew")
+ }
+ return h.hashMapFallback(v)
case reflect.String:
w.WriteString(v.String())
case reflect.Bool:
- w.Write(strconv.AppendBool(scratch[:0], v.Bool()))
+ w.Write(strconv.AppendBool(h.scratch[:0], v.Bool()))
case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
- w.Write(strconv.AppendInt(scratch[:0], v.Int(), 10))
+ w.Write(strconv.AppendInt(h.scratch[:0], v.Int(), 10))
case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
- scratch = strconv.AppendUint(scratch[:0], v.Uint(), 10)
- w.Write(scratch)
+ w.Write(strconv.AppendUint(h.scratch[:0], v.Uint(), 10))
case reflect.Float32, reflect.Float64:
- scratch = strconv.AppendUint(scratch[:0], math.Float64bits(v.Float()), 10)
- w.Write(scratch)
+ w.Write(strconv.AppendUint(h.scratch[:0], math.Float64bits(v.Float()), 10))
case reflect.Complex64, reflect.Complex128:
fmt.Fprintf(w, "%v", v.Complex())
}
@@ -252,40 +262,48 @@ func (c valueCache) get(t reflect.Type) reflect.Value {
// hashMapAcyclic is the faster sort-free version of map hashing. If
// it detects a cycle it returns false and guarantees that nothing was
// written to w.
-func hashMapAcyclic(w *bufio.Writer, v reflect.Value, visited map[uintptr]bool, scratch []byte) (acyclic bool) {
+func (h *hasher) hashMapAcyclic(v reflect.Value) (acyclic bool) {
mh := mapHasherPool.Get().(*mapHasher)
defer mapHasherPool.Put(mh)
mh.Reset()
iter := mapIter(mh.iter, v)
defer mapIter(mh.iter, reflect.Value{}) // avoid pinning v from mh.iter when we return
+
+ // Flush the current writer and temporarily restore the bufio
+ // writer we'll be using for future prints.
+ oldw := h.bw
+ defer h.setBufioWriter(oldw) // restore bufio writer
+ h.setBufioWriter(mh.bw)
+
k := mh.val.get(v.Type().Key())
e := mh.val.get(v.Type().Elem())
for iter.Next() {
key := iterKey(iter, k)
val := iterVal(iter, e)
mh.startEntry()
- if !print(mh.bw, key, visited, scratch) {
+ if !h.print(key) {
return false
}
- if !print(mh.bw, val, visited, scratch) {
+ if !h.print(val) {
return false
}
mh.endEntry()
}
- w.Write(mh.xbuf[:])
+ oldw.Write(mh.xbuf[:])
return true
}
-func hashMapFallback(w *bufio.Writer, v reflect.Value, visited map[uintptr]bool, scratch []byte) (acyclic bool) {
+func (h *hasher) hashMapFallback(v reflect.Value) (acyclic bool) {
acyclic = true
sm := newSortedMap(v)
+ w := h.bw
fmt.Fprintf(w, "map[%d]{\n", len(sm.Key))
for i, k := range sm.Key {
- if !print(w, k, visited, scratch) {
+ if !h.print(k) {
acyclic = false
}
w.WriteString(": ")
- if !print(w, sm.Value[i], visited, scratch) {
+ if !h.print(sm.Value[i]) {
acyclic = false
}
w.WriteString("\n")
diff --git a/util/deephash/deephash_test.go b/util/deephash/deephash_test.go
index 2a0a1052b..beccb4126 100644
--- a/util/deephash/deephash_test.go
+++ b/util/deephash/deephash_test.go
@@ -38,8 +38,8 @@ func TestDeepHash(t *testing.T) {
func getVal() []interface{} {
return []interface{}{
&wgcfg.Config{
- Name: "foo",
- Addresses: []netaddr.IPPrefix{netaddr.IPPrefixFrom(netaddr.IPFrom16([16]byte{3: 3}), 5)},
+ //Name: "foo",
+ //Addresses: []netaddr.IPPrefix{netaddr.IPPrefixFrom(netaddr.IPFrom16([16]byte{3: 3}), 5)},
Peers: []wgcfg.Peer{
{
Endpoints: wgcfg.Endpoints{
@@ -48,6 +48,8 @@ func getVal() []interface{} {
},
},
},
+ }
+ return []interface{}{
&router.Config{
Routes: []netaddr.IPPrefix{
netaddr.MustParseIPPrefix("1.2.3.0/24"),
@@ -149,12 +151,14 @@ func TestHashMapAcyclic(t *testing.T) {
bw := bufio.NewWriter(&buf)
for i := 0; i < 20; i++ {
- visited := map[uintptr]bool{}
- scratch := make([]byte, 0, 64)
v := reflect.ValueOf(m)
buf.Reset()
bw.Reset(&buf)
- if !hashMapAcyclic(bw, v, visited, scratch) {
+ h := &hasher{
+ bw: bw,
+ visited: map[uintptr]bool{},
+ }
+ if !h.hashMapAcyclic(v) {
t.Fatal("returned false")
}
if got[string(buf.Bytes())] {
@@ -176,14 +180,17 @@ func BenchmarkHashMapAcyclic(b *testing.B) {
var buf bytes.Buffer
bw := bufio.NewWriter(&buf)
- visited := map[uintptr]bool{}
- scratch := make([]byte, 0, 64)
v := reflect.ValueOf(m)
+ h := &hasher{
+ bw: bw,
+ visited: map[uintptr]bool{},
+ }
+
for i := 0; i < b.N; i++ {
buf.Reset()
bw.Reset(&buf)
- if !hashMapAcyclic(bw, v, visited, scratch) {
+ if !h.hashMapAcyclic(v) {
b.Fatal("returned false")
}
}
@@ -233,3 +240,16 @@ func TestMapCyclicFallback(t *testing.T) {
v.M["m"] = v.M
Hash(v)
}
+
+func TestVisitedFallback(t *testing.T) {
+ t.Skip("known failure: https://github.com/tailscale/tailscale/issues/2342")
+ type V struct {
+ I int
+ }
+ m := map[int]*V{}
+ v1 := &V{1}
+ for i := 0; i < 1000; i++ {
+ m[i] = v1
+ }
+ Hash(m)
+}
Copyright © 2025 - 2026 Wayne Cole. WTFPL. Attribution appreciated. No warranty. Not liable for bodily damages.