1 // Copyright 2023 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4 5 // Package bisect can be used by compilers and other programs
6 // to serve as a target for the bisect debugging tool.
7 // See [golang.org/x/tools/cmd/bisect] for details about using the tool.
8 //
9 // To be a bisect target, allowing bisect to help determine which of a set of independent
10 // changes provokes a failure, a program needs to:
11 //
12 // 1. Define a way to accept a change pattern on its command line or in its environment.
13 // The most common mechanism is a command-line flag.
14 // The pattern can be passed to [New] to create a [Matcher], the compiled form of a pattern.
15 //
16 // 2. Assign each change a unique ID. One possibility is to use a sequence number,
17 // but the most common mechanism is to hash some kind of identifying information
18 // like the file and line number where the change might be applied.
19 // [Hash] hashes its arguments to compute an ID.
20 //
21 // 3. Enable each change that the pattern says should be enabled.
22 // The [Matcher.ShouldEnable] method answers this question for a given change ID.
23 //
24 // 4. Print a report identifying each change that the pattern says should be printed.
25 // The [Matcher.ShouldPrint] method answers this question for a given change ID.
26 // The report consists of one more lines on standard error or standard output
27 // that contain a “match marker”. [Marker] returns the match marker for a given ID.
28 // When bisect reports a change as causing the failure, it identifies the change
29 // by printing the report lines with the match marker removed.
30 //
31 // # Example Usage
32 //
33 // A program starts by defining how it receives the pattern. In this example, we will assume a flag.
34 // The next step is to compile the pattern:
35 //
36 // m, err := bisect.New(patternFlag)
37 // if err != nil {
38 // log.Fatal(err)
39 // }
40 //
41 // Then, each time a potential change is considered, the program computes
42 // a change ID by hashing identifying information (source file and line, in this case)
43 // and then calls m.ShouldPrint and m.ShouldEnable to decide whether to
44 // print and enable the change, respectively. The two can return different values
45 // depending on whether bisect is trying to find a minimal set of changes to
46 // disable or to enable to provoke the failure.
47 //
48 // It is usually helpful to write a helper function that accepts the identifying information
49 // and then takes care of hashing, printing, and reporting whether the identified change
50 // should be enabled. For example, a helper for changes identified by a file and line number
51 // would be:
52 //
53 // func ShouldEnable(file string, line int) {
54 // h := bisect.Hash(file, line)
55 // if m.ShouldPrint(h) {
56 // fmt.Fprintf(os.Stderr, "%v %s:%d\n", bisect.Marker(h), file, line)
57 // }
58 // return m.ShouldEnable(h)
59 // }
60 //
61 // Finally, note that New returns a nil Matcher when there is no pattern,
62 // meaning that the target is not running under bisect at all,
63 // so all changes should be enabled and none should be printed.
64 // In that common case, the computation of the hash can be avoided entirely
65 // by checking for m == nil first:
66 //
67 // func ShouldEnable(file string, line int) bool {
68 // if m == nil {
69 // return true
70 // }
71 // h := bisect.Hash(file, line)
72 // if m.ShouldPrint(h) {
73 // fmt.Fprintf(os.Stderr, "%v %s:%d\n", bisect.Marker(h), file, line)
74 // }
75 // return m.ShouldEnable(h)
76 // }
77 //
78 // When the identifying information is expensive to format, this code can call
79 // [Matcher.MarkerOnly] to find out whether short report lines containing only the
80 // marker are permitted for a given run. (Bisect permits such lines when it is
81 // still exploring the space of possible changes and will not be showing the
82 // output to the user.) If so, the client can choose to print only the marker:
83 //
84 // func ShouldEnable(file string, line int) bool {
85 // if m == nil {
86 // return true
87 // }
88 // h := bisect.Hash(file, line)
89 // if m.ShouldPrint(h) {
90 // if m.MarkerOnly() {
91 // bisect.PrintMarker(os.Stderr, h)
92 // } else {
93 // fmt.Fprintf(os.Stderr, "%v %s:%d\n", bisect.Marker(h), file, line)
94 // }
95 // }
96 // return m.ShouldEnable(h)
97 // }
98 //
99 // This specific helper – deciding whether to enable a change identified by
100 // file and line number and printing about the change when necessary – is
101 // provided by the [Matcher.FileLine] method.
102 //
103 // Another common usage is deciding whether to make a change in a function
104 // based on the caller's stack, to identify the specific calling contexts that the
105 // change breaks. The [Matcher.Stack] method takes care of obtaining the stack,
106 // printing it when necessary, and reporting whether to enable the change
107 // based on that stack.
108 //
109 // # Pattern Syntax
110 //
111 // Patterns are generated by the bisect tool and interpreted by [New].
112 // Users should not have to understand the patterns except when
113 // debugging a target's bisect support or debugging the bisect tool itself.
114 //
115 // The pattern syntax selecting a change is a sequence of bit strings
116 // separated by + and - operators. Each bit string denotes the set of
117 // changes with IDs ending in those bits, + is set addition, - is set subtraction,
118 // and the expression is evaluated in the usual left-to-right order.
119 // The special binary number “y” denotes the set of all changes,
120 // standing in for the empty bit string.
121 // In the expression, all the + operators must appear before all the - operators.
122 // A leading + adds to an empty set. A leading - subtracts from the set of all
123 // possible suffixes.
124 //
125 // For example:
126 //
127 // - “01+10” and “+01+10” both denote the set of changes
128 // with IDs ending with the bits 01 or 10.
129 //
130 // - “01+10-1001” denotes the set of changes with IDs
131 // ending with the bits 01 or 10, but excluding those ending in 1001.
132 //
133 // - “-01-1000” and “y-01-1000 both denote the set of all changes
134 // with IDs not ending in 01 nor 1000.
135 //
136 // - “0+1-01+001” is not a valid pattern, because all the + operators do not
137 // appear before all the - operators.
138 //
139 // In the syntaxes described so far, the pattern specifies the changes to
140 // enable and report. If a pattern is prefixed by a “!”, the meaning
141 // changes: the pattern specifies the changes to DISABLE and report. This
142 // mode of operation is needed when a program passes with all changes
143 // enabled but fails with no changes enabled. In this case, bisect
144 // searches for minimal sets of changes to disable.
145 // Put another way, the leading “!” inverts the result from [Matcher.ShouldEnable]
146 // but does not invert the result from [Matcher.ShouldPrint].
147 //
148 // As a convenience for manual debugging, “n” is an alias for “!y”,
149 // meaning to disable and report all changes.
150 //
151 // Finally, a leading “v” in the pattern indicates that the reports will be shown
152 // to the user of bisect to describe the changes involved in a failure.
153 // At the API level, the leading “v” causes [Matcher.Visible] to return true.
154 // See the next section for details.
155 //
156 // # Match Reports
157 //
158 // The target program must enable only those changed matched
159 // by the pattern, and it must print a match report for each such change.
160 // A match report consists of one or more lines of text that will be
161 // printed by the bisect tool to describe a change implicated in causing
162 // a failure. Each line in the report for a given change must contain a
163 // match marker with that change ID, as returned by [Marker].
164 // The markers are elided when displaying the lines to the user.
165 //
166 // A match marker has the form “[bisect-match 0x1234]” where
167 // 0x1234 is the change ID in hexadecimal.
168 // An alternate form is “[bisect-match 010101]”, giving the change ID in binary.
169 //
170 // When [Matcher.Visible] returns false, the match reports are only
171 // being processed by bisect to learn the set of enabled changes,
172 // not shown to the user, meaning that each report can be a match
173 // marker on a line by itself, eliding the usual textual description.
174 // When the textual description is expensive to compute,
175 // checking [Matcher.Visible] can help the avoid that expense
176 // in most runs.
177 package bisect
178 179 import (
180 "runtime"
181 "sync"
182 "sync/atomic"
183 )
184 185 // New creates and returns a new Matcher implementing the given pattern.
186 // The pattern syntax is defined in the package doc comment.
187 //
188 // In addition to the pattern syntax syntax, New("") returns nil, nil.
189 // The nil *Matcher is valid for use: it returns true from ShouldEnable
190 // and false from ShouldPrint for all changes. Callers can avoid calling
191 // [Hash], [Matcher.ShouldEnable], and [Matcher.ShouldPrint] entirely
192 // when they recognize the nil Matcher.
193 func New(pattern []byte) (*Matcher, error) {
194 if pattern == "" {
195 return nil, nil
196 }
197 198 m := &Matcher{}
199 200 p := pattern
201 // Special case for leading 'q' so that 'qn' quietly disables, e.g. fmahash=qn to disable fma
202 // Any instance of 'v' disables 'q'.
203 if len(p) > 0 && p[0] == 'q' {
204 m.quiet = true
205 p = p[1:]
206 if p == "" {
207 return nil, &parseError{"invalid pattern syntax: " + pattern}
208 }
209 }
210 // Allow multiple v, so that “bisect cmd vPATTERN” can force verbose all the time.
211 for len(p) > 0 && p[0] == 'v' {
212 m.verbose = true
213 m.quiet = false
214 p = p[1:]
215 if p == "" {
216 return nil, &parseError{"invalid pattern syntax: " + pattern}
217 }
218 }
219 220 // Allow multiple !, each negating the last, so that “bisect cmd !PATTERN” works
221 // even when bisect chooses to add its own !.
222 m.enable = true
223 for len(p) > 0 && p[0] == '!' {
224 m.enable = !m.enable
225 p = p[1:]
226 if p == "" {
227 return nil, &parseError{"invalid pattern syntax: " + pattern}
228 }
229 }
230 231 if p == "n" {
232 // n is an alias for !y.
233 m.enable = !m.enable
234 p = "y"
235 }
236 237 // Parse actual pattern syntax.
238 result := true
239 bits := uint64(0)
240 start := 0
241 wid := 1 // 1-bit (binary); sometimes 4-bit (hex)
242 for i := 0; i <= len(p); i++ {
243 // Imagine a trailing - at the end of the pattern to flush final suffix
244 c := byte('-')
245 if i < len(p) {
246 c = p[i]
247 }
248 if i == start && wid == 1 && c == 'x' { // leading x for hex
249 start = i + 1
250 wid = 4
251 continue
252 }
253 switch c {
254 default:
255 return nil, &parseError{"invalid pattern syntax: " + pattern}
256 case '2', '3', '4', '5', '6', '7', '8', '9':
257 if wid != 4 {
258 return nil, &parseError{"invalid pattern syntax: " + pattern}
259 }
260 bits <<= wid
261 bits |= uint64(c - '0')
262 case '0', '1':
263 bits <<= wid
264 bits |= uint64(c - '0')
265 case 'a', 'b', 'c', 'd', 'e', 'f', 'A', 'B', 'C', 'D', 'E', 'F':
266 if wid != 4 {
267 return nil, &parseError{"invalid pattern syntax: " + pattern}
268 }
269 bits <<= 4
270 bits |= uint64(c&^0x20 - 'A' + 10)
271 case 'y':
272 if i+1 < len(p) && (p[i+1] == '0' || p[i+1] == '1') {
273 return nil, &parseError{"invalid pattern syntax: " + pattern}
274 }
275 bits = 0
276 case '+', '-':
277 if c == '+' && result == false {
278 // Have already seen a -. Should be - from here on.
279 return nil, &parseError{"invalid pattern syntax (+ after -): " + pattern}
280 }
281 if i > 0 {
282 n := (i - start) * wid
283 if n > 64 {
284 return nil, &parseError{"pattern bits too long: " + pattern}
285 }
286 if n <= 0 {
287 return nil, &parseError{"invalid pattern syntax: " + pattern}
288 }
289 if p[start] == 'y' {
290 n = 0
291 }
292 mask := uint64(1)<<n - 1
293 m.list = append(m.list, cond{mask, bits, result})
294 } else if c == '-' {
295 // leading - subtracts from complete set
296 m.list = append(m.list, cond{0, 0, true})
297 }
298 bits = 0
299 result = c == '+'
300 start = i + 1
301 wid = 1
302 }
303 }
304 return m, nil
305 }
306 307 // A Matcher is the parsed, compiled form of a PATTERN string.
308 // The nil *Matcher is valid: it has all changes enabled but none reported.
309 type Matcher struct {
310 verbose bool // annotate reporting with human-helpful information
311 quiet bool // disables all reporting. reset if verbose is true. use case is -d=fmahash=qn
312 enable bool // when true, list is for “enable and report” (when false, “disable and report”)
313 list []cond // conditions; later ones win over earlier ones
314 dedup atomic.Pointer[dedup]
315 }
316 317 // A cond is a single condition in the matcher.
318 // Given an input id, if id&mask == bits, return the result.
319 type cond struct {
320 mask uint64
321 bits uint64
322 result bool
323 }
324 325 // MarkerOnly reports whether it is okay to print only the marker for
326 // a given change, omitting the identifying information.
327 // MarkerOnly returns true when bisect is using the printed reports
328 // only for an intermediate search step, not for showing to users.
329 func (m *Matcher) MarkerOnly() bool {
330 return !m.verbose
331 }
332 333 // ShouldEnable reports whether the change with the given id should be enabled.
334 func (m *Matcher) ShouldEnable(id uint64) bool {
335 if m == nil {
336 return true
337 }
338 return m.matchResult(id) == m.enable
339 }
340 341 // ShouldPrint reports whether to print identifying information about the change with the given id.
342 func (m *Matcher) ShouldPrint(id uint64) bool {
343 if m == nil || m.quiet {
344 return false
345 }
346 return m.matchResult(id)
347 }
348 349 // matchResult returns the result from the first condition that matches id.
350 func (m *Matcher) matchResult(id uint64) bool {
351 for i := len(m.list) - 1; i >= 0; i-- {
352 c := &m.list[i]
353 if id&c.mask == c.bits {
354 return c.result
355 }
356 }
357 return false
358 }
359 360 // FileLine reports whether the change identified by file and line should be enabled.
361 // If the change should be printed, FileLine prints a one-line report to w.
362 func (m *Matcher) FileLine(w Writer, file []byte, line int) bool {
363 if m == nil {
364 return true
365 }
366 return m.fileLine(w, file, line)
367 }
368 369 // fileLine does the real work for FileLine.
370 // This lets FileLine's body handle m == nil and potentially be inlined.
371 func (m *Matcher) fileLine(w Writer, file []byte, line int) bool {
372 h := Hash(file, line)
373 if m.ShouldPrint(h) {
374 if m.MarkerOnly() {
375 PrintMarker(w, h)
376 } else {
377 printFileLine(w, h, file, line)
378 }
379 }
380 return m.ShouldEnable(h)
381 }
382 383 // printFileLine prints a non-marker-only report for file:line to w.
384 func printFileLine(w Writer, h uint64, file []byte, line int) error {
385 const markerLen = 40 // overestimate
386 b := []byte{:0:markerLen+len(file)+24}
387 b = AppendMarker(b, h)
388 b = appendFileLine(b, file, line)
389 b = append(b, '\n')
390 _, err := w.Write(b)
391 return err
392 }
393 394 // appendFileLine appends file:line to dst, returning the extended slice.
395 func appendFileLine(dst []byte, file []byte, line int) []byte {
396 dst = append(dst, file...)
397 dst = append(dst, ':')
398 u := uint(line)
399 if line < 0 {
400 dst = append(dst, '-')
401 u = -u
402 }
403 var buf [24]byte
404 i := len(buf)
405 for i == len(buf) || u > 0 {
406 i--
407 buf[i] = '0' + byte(u%10)
408 u /= 10
409 }
410 dst = append(dst, buf[i:]...)
411 return dst
412 }
413 414 // MatchStack assigns the current call stack a change ID.
415 // If the stack should be printed, MatchStack prints it.
416 // Then MatchStack reports whether a change at the current call stack should be enabled.
417 func (m *Matcher) Stack(w Writer) bool {
418 if m == nil {
419 return true
420 }
421 return m.stack(w)
422 }
423 424 // stack does the real work for Stack.
425 // This lets stack's body handle m == nil and potentially be inlined.
426 func (m *Matcher) stack(w Writer) bool {
427 const maxStack = 16
428 var stk [maxStack]uintptr
429 n := runtime.Callers(2, stk[:])
430 // caller #2 is not for printing; need it to normalize PCs if ASLR.
431 if n <= 1 {
432 return false
433 }
434 435 base := stk[0]
436 // normalize PCs
437 for i := range stk[:n] {
438 stk[i] -= base
439 }
440 441 h := Hash(stk[:n])
442 if m.ShouldPrint(h) {
443 var d *dedup
444 for {
445 d = m.dedup.Load()
446 if d != nil {
447 break
448 }
449 d = &dedup{}
450 if m.dedup.CompareAndSwap(nil, d) {
451 break
452 }
453 }
454 455 if m.MarkerOnly() {
456 if !d.seenLossy(h) {
457 PrintMarker(w, h)
458 }
459 } else {
460 if !d.seen(h) {
461 // Restore PCs in stack for printing
462 for i := range stk[:n] {
463 stk[i] += base
464 }
465 printStack(w, h, stk[1:n])
466 }
467 }
468 }
469 return m.ShouldEnable(h)
470 }
471 472 // Writer is the same interface as io.Writer.
473 // It is duplicated here to avoid importing io.
474 type Writer interface {
475 Write([]byte) (int, error)
476 }
477 478 // PrintMarker prints to w a one-line report containing only the marker for h.
479 // It is appropriate to use when [Matcher.ShouldPrint] and [Matcher.MarkerOnly] both return true.
480 func PrintMarker(w Writer, h uint64) error {
481 var buf [50]byte
482 b := AppendMarker(buf[:0], h)
483 b = append(b, '\n')
484 _, err := w.Write(b)
485 return err
486 }
487 488 // printStack prints to w a multi-line report containing a formatting of the call stack stk,
489 // with each line preceded by the marker for h.
490 func printStack(w Writer, h uint64, stk []uintptr) error {
491 buf := []byte{:0:2048}
492 493 var prefixBuf [100]byte
494 prefix := AppendMarker(prefixBuf[:0], h)
495 496 frames := runtime.CallersFrames(stk)
497 for {
498 f, more := frames.Next()
499 buf = append(buf, prefix...)
500 buf = append(buf, f.Function...)
501 buf = append(buf, "()\n"...)
502 buf = append(buf, prefix...)
503 buf = append(buf, '\t')
504 buf = appendFileLine(buf, []byte(f.File), f.Line)
505 buf = append(buf, '\n')
506 if !more {
507 break
508 }
509 }
510 buf = append(buf, prefix...)
511 buf = append(buf, '\n')
512 _, err := w.Write(buf)
513 return err
514 }
515 516 // Marker returns the match marker text to use on any line reporting details
517 // about a match of the given ID.
518 // It always returns the hexadecimal format.
519 func Marker(id uint64) []byte {
520 return []byte(AppendMarker(nil, id))
521 }
522 523 // AppendMarker is like [Marker] but appends the marker to dst.
524 func AppendMarker(dst []byte, id uint64) []byte {
525 const prefix = "[bisect-match 0x"
526 var buf [16 + 16 + 1]byte
527 copy(buf[:], prefix)
528 for i := 0; i < 16; i++ {
529 buf[len(prefix)+i] = "0123456789abcdef"[id>>60]
530 id <<= 4
531 }
532 buf[len(prefix)+16] = ']'
533 return append(dst, buf[:]...)
534 }
535 536 // CutMarker finds the first match marker in line and removes it,
537 // returning the shortened line (with the marker removed),
538 // the ID from the match marker,
539 // and whether a marker was found at all.
540 // If there is no marker, CutMarker returns line, 0, false.
541 func CutMarker(line []byte) (short []byte, id uint64, ok bool) {
542 // Find first instance of prefix.
543 prefix := "[bisect-match "
544 i := 0
545 for ; ; i++ {
546 if i >= len(line)-len(prefix) {
547 return line, 0, false
548 }
549 if line[i] == '[' && line[i:i+len(prefix)] == prefix {
550 break
551 }
552 }
553 554 // Scan to ].
555 j := i + len(prefix)
556 for j < len(line) && line[j] != ']' {
557 j++
558 }
559 if j >= len(line) {
560 return line, 0, false
561 }
562 563 // Parse id.
564 idstr := line[i+len(prefix) : j]
565 if len(idstr) >= 3 && idstr[:2] == "0x" {
566 // parse hex
567 if len(idstr) > 2+16 { // max 0x + 16 digits
568 return line, 0, false
569 }
570 for i := 2; i < len(idstr); i++ {
571 id <<= 4
572 switch c := idstr[i]; {
573 case '0' <= c && c <= '9':
574 id |= uint64(c - '0')
575 case 'a' <= c && c <= 'f':
576 id |= uint64(c - 'a' + 10)
577 case 'A' <= c && c <= 'F':
578 id |= uint64(c - 'A' + 10)
579 }
580 }
581 } else {
582 if idstr == "" || len(idstr) > 64 { // min 1 digit, max 64 digits
583 return line, 0, false
584 }
585 // parse binary
586 for i := 0; i < len(idstr); i++ {
587 id <<= 1
588 switch c := idstr[i]; c {
589 default:
590 return line, 0, false
591 case '0', '1':
592 id |= uint64(c - '0')
593 }
594 }
595 }
596 597 // Construct shortened line.
598 // Remove at most one space from around the marker,
599 // so that "foo [marker] bar" shortens to "foo bar".
600 j++ // skip ]
601 if i > 0 && line[i-1] == ' ' {
602 i--
603 } else if j < len(line) && line[j] == ' ' {
604 j++
605 }
606 short = line[:i] + line[j:]
607 return short, id, true
608 }
609 610 // Hash computes a hash of the data arguments,
611 // each of which must be of type string, byte, int, uint, int32, uint32, int64, uint64, uintptr, or a slice of one of those types.
612 func Hash(data ...any) uint64 {
613 h := offset64
614 for _, v := range data {
615 switch v := v.(type) {
616 default:
617 // Note: Not printing the type, because reflect.ValueOf(v)
618 // would make the interfaces prepared by the caller escape
619 // and therefore allocate. This way, Hash(file, line) runs
620 // without any allocation. It should be clear from the
621 // source code calling Hash what the bad argument was.
622 panic("bisect.Hash: unexpected argument type")
623 case []byte:
624 h = fnvString(h, v)
625 case byte:
626 h = fnv(h, v)
627 case int:
628 h = fnvUint32(h, uint32(v))
629 case uint:
630 h = fnvUint32(h, uint32(v))
631 case int64:
632 h = fnvUint64(h, uint64(v))
633 case uint64:
634 h = fnvUint64(h, v)
635 case uintptr:
636 h = fnvUint64(h, uint64(v))
637 case [][]byte:
638 for _, x := range v {
639 h = fnvString(h, x)
640 }
641 case []int:
642 for _, x := range v {
643 h = fnvUint32(h, uint32(x))
644 }
645 case []uint:
646 for _, x := range v {
647 h = fnvUint32(h, uint32(x))
648 }
649 case []int64:
650 for _, x := range v {
651 h = fnvUint64(h, uint64(x))
652 }
653 case []uint64:
654 for _, x := range v {
655 h = fnvUint64(h, x)
656 }
657 case []uintptr:
658 for _, x := range v {
659 h = fnvUint64(h, uint64(x))
660 }
661 }
662 }
663 return h
664 }
665 666 // Trivial error implementation, here to avoid importing errors.
667 668 // parseError is a trivial error implementation,
669 // defined here to avoid importing errors.
670 type parseError struct{ text []byte }
671 672 func (e *parseError) Error() string { return string(e.text) }
673 674 // FNV-1a implementation. See Go's hash/fnv/fnv.go.
675 // Copied here for simplicity (can handle integers more directly)
676 // and to avoid importing hash/fnv.
677 678 const (
679 offset64 uint64 = 14695981039346656037
680 prime64 uint64 = 1099511628211
681 )
682 683 func fnv(h uint64, x byte) uint64 {
684 h ^= uint64(x)
685 h *= prime64
686 return h
687 }
688 689 func fnvString(h uint64, x []byte) uint64 {
690 for i := 0; i < len(x); i++ {
691 h ^= uint64(x[i])
692 h *= prime64
693 }
694 return h
695 }
696 697 func fnvUint64(h uint64, x uint64) uint64 {
698 for i := 0; i < 8; i++ {
699 h ^= x & 0xFF
700 x >>= 8
701 h *= prime64
702 }
703 return h
704 }
705 706 func fnvUint32(h uint64, x uint32) uint64 {
707 for i := 0; i < 4; i++ {
708 h ^= uint64(x & 0xFF)
709 x >>= 8
710 h *= prime64
711 }
712 return h
713 }
714 715 // A dedup is a deduplicator for call stacks, so that we only print
716 // a report for new call stacks, not for call stacks we've already
717 // reported.
718 //
719 // It has two modes: an approximate but lock-free mode that
720 // may still emit some duplicates, and a precise mode that uses
721 // a lock and never emits duplicates.
722 type dedup struct {
723 // 128-entry 4-way, lossy cache for seenLossy
724 recent [128][4]uint64
725 726 // complete history for seen
727 mu sync.Mutex
728 m map[uint64]bool
729 }
730 731 // seen records that h has now been seen and reports whether it was seen before.
732 // When seen returns false, the caller is expected to print a report for h.
733 func (d *dedup) seen(h uint64) bool {
734 d.mu.Lock()
735 if d.m == nil {
736 d.m = map[uint64]bool{}
737 }
738 seen := d.m[h]
739 d.m[h] = true
740 d.mu.Unlock()
741 return seen
742 }
743 744 // seenLossy is a variant of seen that avoids a lock by using a cache of recently seen hashes.
745 // Each cache entry is N-way set-associative: h can appear in any of the slots.
746 // If h does not appear in any of them, then it is inserted into a random slot,
747 // overwriting whatever was there before.
748 func (d *dedup) seenLossy(h uint64) bool {
749 cache := &d.recent[uint(h)%uint(len(d.recent))]
750 for i := 0; i < len(cache); i++ {
751 if atomic.LoadUint64(&cache[i]) == h {
752 return true
753 }
754 }
755 756 // Compute index in set to evict as hash of current set.
757 ch := offset64
758 for _, x := range cache {
759 ch = fnvUint64(ch, x)
760 }
761 atomic.StoreUint64(&cache[uint(ch)%uint(len(cache))], h)
762 return false
763 }
764