Source file src/internal/bisect/bisect.go
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 string) (*Matcher, error) { 194 if pattern == "" { 195 return nil, nil 196 } 197 198 m := new(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 fallthrough 261 case '0', '1': 262 bits <<= wid 263 bits |= uint64(c - '0') 264 case 'a', 'b', 'c', 'd', 'e', 'f', 'A', 'B', 'C', 'D', 'E', 'F': 265 if wid != 4 { 266 return nil, &parseError{"invalid pattern syntax: " + pattern} 267 } 268 bits <<= 4 269 bits |= uint64(c&^0x20 - 'A' + 10) 270 case 'y': 271 if i+1 < len(p) && (p[i+1] == '0' || p[i+1] == '1') { 272 return nil, &parseError{"invalid pattern syntax: " + pattern} 273 } 274 bits = 0 275 case '+', '-': 276 if c == '+' && result == false { 277 // Have already seen a -. Should be - from here on. 278 return nil, &parseError{"invalid pattern syntax (+ after -): " + pattern} 279 } 280 if i > 0 { 281 n := (i - start) * wid 282 if n > 64 { 283 return nil, &parseError{"pattern bits too long: " + pattern} 284 } 285 if n <= 0 { 286 return nil, &parseError{"invalid pattern syntax: " + pattern} 287 } 288 if p[start] == 'y' { 289 n = 0 290 } 291 mask := uint64(1)<<n - 1 292 m.list = append(m.list, cond{mask, bits, result}) 293 } else if c == '-' { 294 // leading - subtracts from complete set 295 m.list = append(m.list, cond{0, 0, true}) 296 } 297 bits = 0 298 result = c == '+' 299 start = i + 1 300 wid = 1 301 } 302 } 303 return m, nil 304 } 305 306 // A Matcher is the parsed, compiled form of a PATTERN string. 307 // The nil *Matcher is valid: it has all changes enabled but none reported. 308 type Matcher struct { 309 verbose bool // annotate reporting with human-helpful information 310 quiet bool // disables all reporting. reset if verbose is true. use case is -d=fmahash=qn 311 enable bool // when true, list is for “enable and report” (when false, “disable and report”) 312 list []cond // conditions; later ones win over earlier ones 313 dedup atomic.Pointer[dedup] 314 } 315 316 // A cond is a single condition in the matcher. 317 // Given an input id, if id&mask == bits, return the result. 318 type cond struct { 319 mask uint64 320 bits uint64 321 result bool 322 } 323 324 // MarkerOnly reports whether it is okay to print only the marker for 325 // a given change, omitting the identifying information. 326 // MarkerOnly returns true when bisect is using the printed reports 327 // only for an intermediate search step, not for showing to users. 328 func (m *Matcher) MarkerOnly() bool { 329 return !m.verbose 330 } 331 332 // ShouldEnable reports whether the change with the given id should be enabled. 333 func (m *Matcher) ShouldEnable(id uint64) bool { 334 if m == nil { 335 return true 336 } 337 return m.matchResult(id) == m.enable 338 } 339 340 // ShouldPrint reports whether to print identifying information about the change with the given id. 341 func (m *Matcher) ShouldPrint(id uint64) bool { 342 if m == nil || m.quiet { 343 return false 344 } 345 return m.matchResult(id) 346 } 347 348 // matchResult returns the result from the first condition that matches id. 349 func (m *Matcher) matchResult(id uint64) bool { 350 for i := len(m.list) - 1; i >= 0; i-- { 351 c := &m.list[i] 352 if id&c.mask == c.bits { 353 return c.result 354 } 355 } 356 return false 357 } 358 359 // FileLine reports whether the change identified by file and line should be enabled. 360 // If the change should be printed, FileLine prints a one-line report to w. 361 func (m *Matcher) FileLine(w Writer, file string, line int) bool { 362 if m == nil { 363 return true 364 } 365 return m.fileLine(w, file, line) 366 } 367 368 // fileLine does the real work for FileLine. 369 // This lets FileLine's body handle m == nil and potentially be inlined. 370 func (m *Matcher) fileLine(w Writer, file string, line int) bool { 371 h := Hash(file, line) 372 if m.ShouldPrint(h) { 373 if m.MarkerOnly() { 374 PrintMarker(w, h) 375 } else { 376 printFileLine(w, h, file, line) 377 } 378 } 379 return m.ShouldEnable(h) 380 } 381 382 // printFileLine prints a non-marker-only report for file:line to w. 383 func printFileLine(w Writer, h uint64, file string, line int) error { 384 const markerLen = 40 // overestimate 385 b := make([]byte, 0, markerLen+len(file)+24) 386 b = AppendMarker(b, h) 387 b = appendFileLine(b, file, line) 388 b = append(b, '\n') 389 _, err := w.Write(b) 390 return err 391 } 392 393 // appendFileLine appends file:line to dst, returning the extended slice. 394 func appendFileLine(dst []byte, file string, line int) []byte { 395 dst = append(dst, file...) 396 dst = append(dst, ':') 397 u := uint(line) 398 if line < 0 { 399 dst = append(dst, '-') 400 u = -u 401 } 402 var buf [24]byte 403 i := len(buf) 404 for i == len(buf) || u > 0 { 405 i-- 406 buf[i] = '0' + byte(u%10) 407 u /= 10 408 } 409 dst = append(dst, buf[i:]...) 410 return dst 411 } 412 413 // MatchStack assigns the current call stack a change ID. 414 // If the stack should be printed, MatchStack prints it. 415 // Then MatchStack reports whether a change at the current call stack should be enabled. 416 func (m *Matcher) Stack(w Writer) bool { 417 if m == nil { 418 return true 419 } 420 return m.stack(w) 421 } 422 423 // stack does the real work for Stack. 424 // This lets stack's body handle m == nil and potentially be inlined. 425 func (m *Matcher) stack(w Writer) bool { 426 const maxStack = 16 427 var stk [maxStack]uintptr 428 n := runtime.Callers(2, stk[:]) 429 // caller #2 is not for printing; need it to normalize PCs if ASLR. 430 if n <= 1 { 431 return false 432 } 433 434 base := stk[0] 435 // normalize PCs 436 for i := range stk[:n] { 437 stk[i] -= base 438 } 439 440 h := Hash(stk[:n]) 441 if m.ShouldPrint(h) { 442 var d *dedup 443 for { 444 d = m.dedup.Load() 445 if d != nil { 446 break 447 } 448 d = new(dedup) 449 if m.dedup.CompareAndSwap(nil, d) { 450 break 451 } 452 } 453 454 if m.MarkerOnly() { 455 if !d.seenLossy(h) { 456 PrintMarker(w, h) 457 } 458 } else { 459 if !d.seen(h) { 460 // Restore PCs in stack for printing 461 for i := range stk[:n] { 462 stk[i] += base 463 } 464 printStack(w, h, stk[1:n]) 465 } 466 } 467 } 468 return m.ShouldEnable(h) 469 } 470 471 // Writer is the same interface as io.Writer. 472 // It is duplicated here to avoid importing io. 473 type Writer interface { 474 Write([]byte) (int, error) 475 } 476 477 // PrintMarker prints to w a one-line report containing only the marker for h. 478 // It is appropriate to use when [Matcher.ShouldPrint] and [Matcher.MarkerOnly] both return true. 479 func PrintMarker(w Writer, h uint64) error { 480 var buf [50]byte 481 b := AppendMarker(buf[:0], h) 482 b = append(b, '\n') 483 _, err := w.Write(b) 484 return err 485 } 486 487 // printStack prints to w a multi-line report containing a formatting of the call stack stk, 488 // with each line preceded by the marker for h. 489 func printStack(w Writer, h uint64, stk []uintptr) error { 490 buf := make([]byte, 0, 2048) 491 492 var prefixBuf [100]byte 493 prefix := AppendMarker(prefixBuf[:0], h) 494 495 frames := runtime.CallersFrames(stk) 496 for { 497 f, more := frames.Next() 498 buf = append(buf, prefix...) 499 buf = append(buf, f.Function...) 500 buf = append(buf, "()\n"...) 501 buf = append(buf, prefix...) 502 buf = append(buf, '\t') 503 buf = appendFileLine(buf, f.File, f.Line) 504 buf = append(buf, '\n') 505 if !more { 506 break 507 } 508 } 509 buf = append(buf, prefix...) 510 buf = append(buf, '\n') 511 _, err := w.Write(buf) 512 return err 513 } 514 515 // Marker returns the match marker text to use on any line reporting details 516 // about a match of the given ID. 517 // It always returns the hexadecimal format. 518 func Marker(id uint64) string { 519 return string(AppendMarker(nil, id)) 520 } 521 522 // AppendMarker is like [Marker] but appends the marker to dst. 523 func AppendMarker(dst []byte, id uint64) []byte { 524 const prefix = "[bisect-match 0x" 525 var buf [len(prefix) + 16 + 1]byte 526 copy(buf[:], prefix) 527 for i := 0; i < 16; i++ { 528 buf[len(prefix)+i] = "0123456789abcdef"[id>>60] 529 id <<= 4 530 } 531 buf[len(prefix)+16] = ']' 532 return append(dst, buf[:]...) 533 } 534 535 // CutMarker finds the first match marker in line and removes it, 536 // returning the shortened line (with the marker removed), 537 // the ID from the match marker, 538 // and whether a marker was found at all. 539 // If there is no marker, CutMarker returns line, 0, false. 540 func CutMarker(line string) (short string, id uint64, ok bool) { 541 // Find first instance of prefix. 542 prefix := "[bisect-match " 543 i := 0 544 for ; ; i++ { 545 if i >= len(line)-len(prefix) { 546 return line, 0, false 547 } 548 if line[i] == '[' && line[i:i+len(prefix)] == prefix { 549 break 550 } 551 } 552 553 // Scan to ]. 554 j := i + len(prefix) 555 for j < len(line) && line[j] != ']' { 556 j++ 557 } 558 if j >= len(line) { 559 return line, 0, false 560 } 561 562 // Parse id. 563 idstr := line[i+len(prefix) : j] 564 if len(idstr) >= 3 && idstr[:2] == "0x" { 565 // parse hex 566 if len(idstr) > 2+16 { // max 0x + 16 digits 567 return line, 0, false 568 } 569 for i := 2; i < len(idstr); i++ { 570 id <<= 4 571 switch c := idstr[i]; { 572 case '0' <= c && c <= '9': 573 id |= uint64(c - '0') 574 case 'a' <= c && c <= 'f': 575 id |= uint64(c - 'a' + 10) 576 case 'A' <= c && c <= 'F': 577 id |= uint64(c - 'A' + 10) 578 } 579 } 580 } else { 581 if idstr == "" || len(idstr) > 64 { // min 1 digit, max 64 digits 582 return line, 0, false 583 } 584 // parse binary 585 for i := 0; i < len(idstr); i++ { 586 id <<= 1 587 switch c := idstr[i]; c { 588 default: 589 return line, 0, false 590 case '0', '1': 591 id |= uint64(c - '0') 592 } 593 } 594 } 595 596 // Construct shortened line. 597 // Remove at most one space from around the marker, 598 // so that "foo [marker] bar" shortens to "foo bar". 599 j++ // skip ] 600 if i > 0 && line[i-1] == ' ' { 601 i-- 602 } else if j < len(line) && line[j] == ' ' { 603 j++ 604 } 605 short = line[:i] + line[j:] 606 return short, id, true 607 } 608 609 // Hash computes a hash of the data arguments, 610 // each of which must be of type string, byte, int, uint, int32, uint32, int64, uint64, uintptr, or a slice of one of those types. 611 func Hash(data ...any) uint64 { 612 h := offset64 613 for _, v := range data { 614 switch v := v.(type) { 615 default: 616 // Note: Not printing the type, because reflect.ValueOf(v) 617 // would make the interfaces prepared by the caller escape 618 // and therefore allocate. This way, Hash(file, line) runs 619 // without any allocation. It should be clear from the 620 // source code calling Hash what the bad argument was. 621 panic("bisect.Hash: unexpected argument type") 622 case string: 623 h = fnvString(h, v) 624 case byte: 625 h = fnv(h, v) 626 case int: 627 h = fnvUint64(h, uint64(v)) 628 case uint: 629 h = fnvUint64(h, uint64(v)) 630 case int32: 631 h = fnvUint32(h, uint32(v)) 632 case uint32: 633 h = fnvUint32(h, v) 634 case int64: 635 h = fnvUint64(h, uint64(v)) 636 case uint64: 637 h = fnvUint64(h, v) 638 case uintptr: 639 h = fnvUint64(h, uint64(v)) 640 case []string: 641 for _, x := range v { 642 h = fnvString(h, x) 643 } 644 case []byte: 645 for _, x := range v { 646 h = fnv(h, x) 647 } 648 case []int: 649 for _, x := range v { 650 h = fnvUint64(h, uint64(x)) 651 } 652 case []uint: 653 for _, x := range v { 654 h = fnvUint64(h, uint64(x)) 655 } 656 case []int32: 657 for _, x := range v { 658 h = fnvUint32(h, uint32(x)) 659 } 660 case []uint32: 661 for _, x := range v { 662 h = fnvUint32(h, x) 663 } 664 case []int64: 665 for _, x := range v { 666 h = fnvUint64(h, uint64(x)) 667 } 668 case []uint64: 669 for _, x := range v { 670 h = fnvUint64(h, x) 671 } 672 case []uintptr: 673 for _, x := range v { 674 h = fnvUint64(h, uint64(x)) 675 } 676 } 677 } 678 return h 679 } 680 681 // Trivial error implementation, here to avoid importing errors. 682 683 // parseError is a trivial error implementation, 684 // defined here to avoid importing errors. 685 type parseError struct{ text string } 686 687 func (e *parseError) Error() string { return e.text } 688 689 // FNV-1a implementation. See Go's hash/fnv/fnv.go. 690 // Copied here for simplicity (can handle integers more directly) 691 // and to avoid importing hash/fnv. 692 693 const ( 694 offset64 uint64 = 14695981039346656037 695 prime64 uint64 = 1099511628211 696 ) 697 698 func fnv(h uint64, x byte) uint64 { 699 h ^= uint64(x) 700 h *= prime64 701 return h 702 } 703 704 func fnvString(h uint64, x string) uint64 { 705 for i := 0; i < len(x); i++ { 706 h ^= uint64(x[i]) 707 h *= prime64 708 } 709 return h 710 } 711 712 func fnvUint64(h uint64, x uint64) uint64 { 713 for i := 0; i < 8; i++ { 714 h ^= x & 0xFF 715 x >>= 8 716 h *= prime64 717 } 718 return h 719 } 720 721 func fnvUint32(h uint64, x uint32) uint64 { 722 for i := 0; i < 4; i++ { 723 h ^= uint64(x & 0xFF) 724 x >>= 8 725 h *= prime64 726 } 727 return h 728 } 729 730 // A dedup is a deduplicator for call stacks, so that we only print 731 // a report for new call stacks, not for call stacks we've already 732 // reported. 733 // 734 // It has two modes: an approximate but lock-free mode that 735 // may still emit some duplicates, and a precise mode that uses 736 // a lock and never emits duplicates. 737 type dedup struct { 738 // 128-entry 4-way, lossy cache for seenLossy 739 recent [128][4]uint64 740 741 // complete history for seen 742 mu sync.Mutex 743 m map[uint64]bool 744 } 745 746 // seen records that h has now been seen and reports whether it was seen before. 747 // When seen returns false, the caller is expected to print a report for h. 748 func (d *dedup) seen(h uint64) bool { 749 d.mu.Lock() 750 if d.m == nil { 751 d.m = make(map[uint64]bool) 752 } 753 seen := d.m[h] 754 d.m[h] = true 755 d.mu.Unlock() 756 return seen 757 } 758 759 // seenLossy is a variant of seen that avoids a lock by using a cache of recently seen hashes. 760 // Each cache entry is N-way set-associative: h can appear in any of the slots. 761 // If h does not appear in any of them, then it is inserted into a random slot, 762 // overwriting whatever was there before. 763 func (d *dedup) seenLossy(h uint64) bool { 764 cache := &d.recent[uint(h)%uint(len(d.recent))] 765 for i := 0; i < len(cache); i++ { 766 if atomic.LoadUint64(&cache[i]) == h { 767 return true 768 } 769 } 770 771 // Compute index in set to evict as hash of current set. 772 ch := offset64 773 for _, x := range cache { 774 ch = fnvUint64(ch, x) 775 } 776 atomic.StoreUint64(&cache[uint(ch)%uint(len(cache))], h) 777 return false 778 } 779