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 "unsafe" 184 ) 185 186 // New creates and returns a new Matcher implementing the given pattern. 187 // The pattern syntax is defined in the package doc comment. 188 // 189 // In addition to the pattern syntax syntax, New("") returns nil, nil. 190 // The nil *Matcher is valid for use: it returns true from ShouldEnable 191 // and false from ShouldPrint for all changes. Callers can avoid calling 192 // [Hash], [Matcher.ShouldEnable], and [Matcher.ShouldPrint] entirely 193 // when they recognize the nil Matcher. 194 func New(pattern string) (*Matcher, error) { 195 if pattern == "" { 196 return nil, nil 197 } 198 199 m := new(Matcher) 200 201 p := pattern 202 // Special case for leading 'q' so that 'qn' quietly disables, e.g. fmahash=qn to disable fma 203 // Any instance of 'v' disables 'q'. 204 if len(p) > 0 && p[0] == 'q' { 205 m.quiet = true 206 p = p[1:] 207 if p == "" { 208 return nil, &parseError{"invalid pattern syntax: " + pattern} 209 } 210 } 211 // Allow multiple v, so that “bisect cmd vPATTERN” can force verbose all the time. 212 for len(p) > 0 && p[0] == 'v' { 213 m.verbose = true 214 m.quiet = false 215 p = p[1:] 216 if p == "" { 217 return nil, &parseError{"invalid pattern syntax: " + pattern} 218 } 219 } 220 221 // Allow multiple !, each negating the last, so that “bisect cmd !PATTERN” works 222 // even when bisect chooses to add its own !. 223 m.enable = true 224 for len(p) > 0 && p[0] == '!' { 225 m.enable = !m.enable 226 p = p[1:] 227 if p == "" { 228 return nil, &parseError{"invalid pattern syntax: " + pattern} 229 } 230 } 231 232 if p == "n" { 233 // n is an alias for !y. 234 m.enable = !m.enable 235 p = "y" 236 } 237 238 // Parse actual pattern syntax. 239 result := true 240 bits := uint64(0) 241 start := 0 242 wid := 1 // 1-bit (binary); sometimes 4-bit (hex) 243 for i := 0; i <= len(p); i++ { 244 // Imagine a trailing - at the end of the pattern to flush final suffix 245 c := byte('-') 246 if i < len(p) { 247 c = p[i] 248 } 249 if i == start && wid == 1 && c == 'x' { // leading x for hex 250 start = i + 1 251 wid = 4 252 continue 253 } 254 switch c { 255 default: 256 return nil, &parseError{"invalid pattern syntax: " + pattern} 257 case '2', '3', '4', '5', '6', '7', '8', '9': 258 if wid != 4 { 259 return nil, &parseError{"invalid pattern syntax: " + pattern} 260 } 261 fallthrough 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 atomicPointerDedup 315 } 316 317 // atomicPointerDedup is an atomic.Pointer[dedup], 318 // but we are avoiding using Go 1.19's atomic.Pointer 319 // until the bootstrap toolchain can be relied upon to have it. 320 type atomicPointerDedup struct { 321 p unsafe.Pointer 322 } 323 324 func (p *atomicPointerDedup) Load() *dedup { 325 return (*dedup)(atomic.LoadPointer(&p.p)) 326 } 327 328 func (p *atomicPointerDedup) CompareAndSwap(old, new *dedup) bool { 329 return atomic.CompareAndSwapPointer(&p.p, unsafe.Pointer(old), unsafe.Pointer(new)) 330 } 331 332 // A cond is a single condition in the matcher. 333 // Given an input id, if id&mask == bits, return the result. 334 type cond struct { 335 mask uint64 336 bits uint64 337 result bool 338 } 339 340 // MarkerOnly reports whether it is okay to print only the marker for 341 // a given change, omitting the identifying information. 342 // MarkerOnly returns true when bisect is using the printed reports 343 // only for an intermediate search step, not for showing to users. 344 func (m *Matcher) MarkerOnly() bool { 345 return !m.verbose 346 } 347 348 // ShouldEnable reports whether the change with the given id should be enabled. 349 func (m *Matcher) ShouldEnable(id uint64) bool { 350 if m == nil { 351 return true 352 } 353 return m.matchResult(id) == m.enable 354 } 355 356 // ShouldPrint reports whether to print identifying information about the change with the given id. 357 func (m *Matcher) ShouldPrint(id uint64) bool { 358 if m == nil || m.quiet { 359 return false 360 } 361 return m.matchResult(id) 362 } 363 364 // matchResult returns the result from the first condition that matches id. 365 func (m *Matcher) matchResult(id uint64) bool { 366 for i := len(m.list) - 1; i >= 0; i-- { 367 c := &m.list[i] 368 if id&c.mask == c.bits { 369 return c.result 370 } 371 } 372 return false 373 } 374 375 // FileLine reports whether the change identified by file and line should be enabled. 376 // If the change should be printed, FileLine prints a one-line report to w. 377 func (m *Matcher) FileLine(w Writer, file string, line int) bool { 378 if m == nil { 379 return true 380 } 381 return m.fileLine(w, file, line) 382 } 383 384 // fileLine does the real work for FileLine. 385 // This lets FileLine's body handle m == nil and potentially be inlined. 386 func (m *Matcher) fileLine(w Writer, file string, line int) bool { 387 h := Hash(file, line) 388 if m.ShouldPrint(h) { 389 if m.MarkerOnly() { 390 PrintMarker(w, h) 391 } else { 392 printFileLine(w, h, file, line) 393 } 394 } 395 return m.ShouldEnable(h) 396 } 397 398 // printFileLine prints a non-marker-only report for file:line to w. 399 func printFileLine(w Writer, h uint64, file string, line int) error { 400 const markerLen = 40 // overestimate 401 b := make([]byte, 0, markerLen+len(file)+24) 402 b = AppendMarker(b, h) 403 b = appendFileLine(b, file, line) 404 b = append(b, '\n') 405 _, err := w.Write(b) 406 return err 407 } 408 409 // appendFileLine appends file:line to dst, returning the extended slice. 410 func appendFileLine(dst []byte, file string, line int) []byte { 411 dst = append(dst, file...) 412 dst = append(dst, ':') 413 u := uint(line) 414 if line < 0 { 415 dst = append(dst, '-') 416 u = -u 417 } 418 var buf [24]byte 419 i := len(buf) 420 for i == len(buf) || u > 0 { 421 i-- 422 buf[i] = '0' + byte(u%10) 423 u /= 10 424 } 425 dst = append(dst, buf[i:]...) 426 return dst 427 } 428 429 // MatchStack assigns the current call stack a change ID. 430 // If the stack should be printed, MatchStack prints it. 431 // Then MatchStack reports whether a change at the current call stack should be enabled. 432 func (m *Matcher) Stack(w Writer) bool { 433 if m == nil { 434 return true 435 } 436 return m.stack(w) 437 } 438 439 // stack does the real work for Stack. 440 // This lets stack's body handle m == nil and potentially be inlined. 441 func (m *Matcher) stack(w Writer) bool { 442 const maxStack = 16 443 var stk [maxStack]uintptr 444 n := runtime.Callers(2, stk[:]) 445 // caller #2 is not for printing; need it to normalize PCs if ASLR. 446 if n <= 1 { 447 return false 448 } 449 450 base := stk[0] 451 // normalize PCs 452 for i := range stk[:n] { 453 stk[i] -= base 454 } 455 456 h := Hash(stk[:n]) 457 if m.ShouldPrint(h) { 458 var d *dedup 459 for { 460 d = m.dedup.Load() 461 if d != nil { 462 break 463 } 464 d = new(dedup) 465 if m.dedup.CompareAndSwap(nil, d) { 466 break 467 } 468 } 469 470 if m.MarkerOnly() { 471 if !d.seenLossy(h) { 472 PrintMarker(w, h) 473 } 474 } else { 475 if !d.seen(h) { 476 // Restore PCs in stack for printing 477 for i := range stk[:n] { 478 stk[i] += base 479 } 480 printStack(w, h, stk[1:n]) 481 } 482 } 483 } 484 return m.ShouldEnable(h) 485 } 486 487 // Writer is the same interface as io.Writer. 488 // It is duplicated here to avoid importing io. 489 type Writer interface { 490 Write([]byte) (int, error) 491 } 492 493 // PrintMarker prints to w a one-line report containing only the marker for h. 494 // It is appropriate to use when [Matcher.ShouldPrint] and [Matcher.MarkerOnly] both return true. 495 func PrintMarker(w Writer, h uint64) error { 496 var buf [50]byte 497 b := AppendMarker(buf[:0], h) 498 b = append(b, '\n') 499 _, err := w.Write(b) 500 return err 501 } 502 503 // printStack prints to w a multi-line report containing a formatting of the call stack stk, 504 // with each line preceded by the marker for h. 505 func printStack(w Writer, h uint64, stk []uintptr) error { 506 buf := make([]byte, 0, 2048) 507 508 var prefixBuf [100]byte 509 prefix := AppendMarker(prefixBuf[:0], h) 510 511 frames := runtime.CallersFrames(stk) 512 for { 513 f, more := frames.Next() 514 buf = append(buf, prefix...) 515 buf = append(buf, f.Func.Name()...) 516 buf = append(buf, "()\n"...) 517 buf = append(buf, prefix...) 518 buf = append(buf, '\t') 519 buf = appendFileLine(buf, f.File, f.Line) 520 buf = append(buf, '\n') 521 if !more { 522 break 523 } 524 } 525 buf = append(buf, prefix...) 526 buf = append(buf, '\n') 527 _, err := w.Write(buf) 528 return err 529 } 530 531 // Marker returns the match marker text to use on any line reporting details 532 // about a match of the given ID. 533 // It always returns the hexadecimal format. 534 func Marker(id uint64) string { 535 return string(AppendMarker(nil, id)) 536 } 537 538 // AppendMarker is like [Marker] but appends the marker to dst. 539 func AppendMarker(dst []byte, id uint64) []byte { 540 const prefix = "[bisect-match 0x" 541 var buf [len(prefix) + 16 + 1]byte 542 copy(buf[:], prefix) 543 for i := 0; i < 16; i++ { 544 buf[len(prefix)+i] = "0123456789abcdef"[id>>60] 545 id <<= 4 546 } 547 buf[len(prefix)+16] = ']' 548 return append(dst, buf[:]...) 549 } 550 551 // CutMarker finds the first match marker in line and removes it, 552 // returning the shortened line (with the marker removed), 553 // the ID from the match marker, 554 // and whether a marker was found at all. 555 // If there is no marker, CutMarker returns line, 0, false. 556 func CutMarker(line string) (short string, id uint64, ok bool) { 557 // Find first instance of prefix. 558 prefix := "[bisect-match " 559 i := 0 560 for ; ; i++ { 561 if i >= len(line)-len(prefix) { 562 return line, 0, false 563 } 564 if line[i] == '[' && line[i:i+len(prefix)] == prefix { 565 break 566 } 567 } 568 569 // Scan to ]. 570 j := i + len(prefix) 571 for j < len(line) && line[j] != ']' { 572 j++ 573 } 574 if j >= len(line) { 575 return line, 0, false 576 } 577 578 // Parse id. 579 idstr := line[i+len(prefix) : j] 580 if len(idstr) >= 3 && idstr[:2] == "0x" { 581 // parse hex 582 if len(idstr) > 2+16 { // max 0x + 16 digits 583 return line, 0, false 584 } 585 for i := 2; i < len(idstr); i++ { 586 id <<= 4 587 switch c := idstr[i]; { 588 case '0' <= c && c <= '9': 589 id |= uint64(c - '0') 590 case 'a' <= c && c <= 'f': 591 id |= uint64(c - 'a' + 10) 592 case 'A' <= c && c <= 'F': 593 id |= uint64(c - 'A' + 10) 594 } 595 } 596 } else { 597 if idstr == "" || len(idstr) > 64 { // min 1 digit, max 64 digits 598 return line, 0, false 599 } 600 // parse binary 601 for i := 0; i < len(idstr); i++ { 602 id <<= 1 603 switch c := idstr[i]; c { 604 default: 605 return line, 0, false 606 case '0', '1': 607 id |= uint64(c - '0') 608 } 609 } 610 } 611 612 // Construct shortened line. 613 // Remove at most one space from around the marker, 614 // so that "foo [marker] bar" shortens to "foo bar". 615 j++ // skip ] 616 if i > 0 && line[i-1] == ' ' { 617 i-- 618 } else if j < len(line) && line[j] == ' ' { 619 j++ 620 } 621 short = line[:i] + line[j:] 622 return short, id, true 623 } 624 625 // Hash computes a hash of the data arguments, 626 // each of which must be of type string, byte, int, uint, int32, uint32, int64, uint64, uintptr, or a slice of one of those types. 627 func Hash(data ...any) uint64 { 628 h := offset64 629 for _, v := range data { 630 switch v := v.(type) { 631 default: 632 // Note: Not printing the type, because reflect.ValueOf(v) 633 // would make the interfaces prepared by the caller escape 634 // and therefore allocate. This way, Hash(file, line) runs 635 // without any allocation. It should be clear from the 636 // source code calling Hash what the bad argument was. 637 panic("bisect.Hash: unexpected argument type") 638 case string: 639 h = fnvString(h, v) 640 case byte: 641 h = fnv(h, v) 642 case int: 643 h = fnvUint64(h, uint64(v)) 644 case uint: 645 h = fnvUint64(h, uint64(v)) 646 case int32: 647 h = fnvUint32(h, uint32(v)) 648 case uint32: 649 h = fnvUint32(h, v) 650 case int64: 651 h = fnvUint64(h, uint64(v)) 652 case uint64: 653 h = fnvUint64(h, v) 654 case uintptr: 655 h = fnvUint64(h, uint64(v)) 656 case []string: 657 for _, x := range v { 658 h = fnvString(h, x) 659 } 660 case []byte: 661 for _, x := range v { 662 h = fnv(h, x) 663 } 664 case []int: 665 for _, x := range v { 666 h = fnvUint64(h, uint64(x)) 667 } 668 case []uint: 669 for _, x := range v { 670 h = fnvUint64(h, uint64(x)) 671 } 672 case []int32: 673 for _, x := range v { 674 h = fnvUint32(h, uint32(x)) 675 } 676 case []uint32: 677 for _, x := range v { 678 h = fnvUint32(h, x) 679 } 680 case []int64: 681 for _, x := range v { 682 h = fnvUint64(h, uint64(x)) 683 } 684 case []uint64: 685 for _, x := range v { 686 h = fnvUint64(h, x) 687 } 688 case []uintptr: 689 for _, x := range v { 690 h = fnvUint64(h, uint64(x)) 691 } 692 } 693 } 694 return h 695 } 696 697 // Trivial error implementation, here to avoid importing errors. 698 699 // parseError is a trivial error implementation, 700 // defined here to avoid importing errors. 701 type parseError struct{ text string } 702 703 func (e *parseError) Error() string { return e.text } 704 705 // FNV-1a implementation. See Go's hash/fnv/fnv.go. 706 // Copied here for simplicity (can handle integers more directly) 707 // and to avoid importing hash/fnv. 708 709 const ( 710 offset64 uint64 = 14695981039346656037 711 prime64 uint64 = 1099511628211 712 ) 713 714 func fnv(h uint64, x byte) uint64 { 715 h ^= uint64(x) 716 h *= prime64 717 return h 718 } 719 720 func fnvString(h uint64, x string) uint64 { 721 for i := 0; i < len(x); i++ { 722 h ^= uint64(x[i]) 723 h *= prime64 724 } 725 return h 726 } 727 728 func fnvUint64(h uint64, x uint64) uint64 { 729 for i := 0; i < 8; i++ { 730 h ^= x & 0xFF 731 x >>= 8 732 h *= prime64 733 } 734 return h 735 } 736 737 func fnvUint32(h uint64, x uint32) uint64 { 738 for i := 0; i < 4; i++ { 739 h ^= uint64(x & 0xFF) 740 x >>= 8 741 h *= prime64 742 } 743 return h 744 } 745 746 // A dedup is a deduplicator for call stacks, so that we only print 747 // a report for new call stacks, not for call stacks we've already 748 // reported. 749 // 750 // It has two modes: an approximate but lock-free mode that 751 // may still emit some duplicates, and a precise mode that uses 752 // a lock and never emits duplicates. 753 type dedup struct { 754 // 128-entry 4-way, lossy cache for seenLossy 755 recent [128][4]uint64 756 757 // complete history for seen 758 mu sync.Mutex 759 m map[uint64]bool 760 } 761 762 // seen records that h has now been seen and reports whether it was seen before. 763 // When seen returns false, the caller is expected to print a report for h. 764 func (d *dedup) seen(h uint64) bool { 765 d.mu.Lock() 766 if d.m == nil { 767 d.m = make(map[uint64]bool) 768 } 769 seen := d.m[h] 770 d.m[h] = true 771 d.mu.Unlock() 772 return seen 773 } 774 775 // seenLossy is a variant of seen that avoids a lock by using a cache of recently seen hashes. 776 // Each cache entry is N-way set-associative: h can appear in any of the slots. 777 // If h does not appear in any of them, then it is inserted into a random slot, 778 // overwriting whatever was there before. 779 func (d *dedup) seenLossy(h uint64) bool { 780 cache := &d.recent[uint(h)%uint(len(d.recent))] 781 for i := 0; i < len(cache); i++ { 782 if atomic.LoadUint64(&cache[i]) == h { 783 return true 784 } 785 } 786 787 // Compute index in set to evict as hash of current set. 788 ch := offset64 789 for _, x := range cache { 790 ch = fnvUint64(ch, x) 791 } 792 atomic.StoreUint64(&cache[uint(ch)%uint(len(cache))], h) 793 return false 794 } 795