> On Oct 8, 2021, at 10:59 AM, Nick Terrell <terrelln@xxxxxx> wrote: > > > >> On Oct 7, 2021, at 11:37 PM, Dan Carpenter <dan.carpenter@xxxxxxxxxx> wrote: >> >> Hello Nick Terrell, >> >> I grepped the README for zstd and it doesn't appear there is a mailing >> list to add to the CC. > > Thanks for the report Dan! Yeah, we don’t have a mailing list, but we use GitHub Issues. > Mind if I open up an issue for this bug? > > The `nbCompares == -1` looks like a real bug. It won’t cause infinite loops, because the > tree data structure has a bounded depth, but it could cause longer execution time than > intended. > > I’ll look into it and fix it! > > Best, > Nick > >> The patch c684b4e9a301: "lib: zstd: Upgrade to latest upstream zstd >> version 1.4.10" from Sep 11, 2020, leads to the following Smatch static >> checker warnings: >> >> lib/zstd/compress/zstd_opt.c:695 ZSTD_insertBtAndGetAllMatches() warn: should this be 'nbCompares == -1' >> lib/zstd/compress/zstd_lazy.c:360 ZSTD_DUBT_findBestMatch() warn: should this be 'nbCompares == -1' >> lib/zstd/compress/zstd_lazy.c:1267 ZSTD_compressBlock_lazy_extDict_generic() warn: inconsistent indenting >> lib/zstd/compress/zstd_compress.c:726 ZSTD_CCtxParams_setParameter() warn: no lower bound on 'value' >> lib/zstd/decompress/zstd_decompress.c:177 ZSTD_createDDictHashSet() warn: variable dereferenced before check 'ret' (see line 174) I’m not sure if you pre-filtered the Smatch results for true bugs, but I’m super impressed that all of these are true bugs! And I just want to say thank you again for the report, this is the most useful static analysis bug report I’ve ever seen. Normally when people submit a static analysis warnings, it is a list of garbage false positives, and there are far too many false positives to sort through to find any potential true bugs. I’m working on fixing these upstream now [0][1][2]. Thanks, Nick [0] https://github.com/facebook/zstd/pull/2817 [1] https://github.com/facebook/zstd/pull/2818 [2] https://github.com/facebook/zstd/pull/2819 >> lib/zstd/compress/zstd_opt.c >> 508 FORCE_INLINE_TEMPLATE >> 509 U32 ZSTD_insertBtAndGetAllMatches ( >> 510 ZSTD_match_t* matches, /* store result (found matches) in this table (presumed large enough) */ >> 511 ZSTD_matchState_t* ms, >> 512 U32* nextToUpdate3, >> 513 const BYTE* const ip, const BYTE* const iLimit, const ZSTD_dictMode_e dictMode, >> 514 const U32 rep[ZSTD_REP_NUM], >> 515 U32 const ll0, /* tells if associated literal length is 0 or not. This value must be 0 or 1 */ >> 516 const U32 lengthToBeat, >> 517 U32 const mls /* template */) >> 518 { >> 519 const ZSTD_compressionParameters* const cParams = &ms->cParams; >> 520 U32 const sufficient_len = MIN(cParams->targetLength, ZSTD_OPT_NUM -1); >> 521 const BYTE* const base = ms->window.base; >> 522 U32 const curr = (U32)(ip-base); >> 523 U32 const hashLog = cParams->hashLog; >> 524 U32 const minMatch = (mls==3) ? 3 : 4; >> 525 U32* const hashTable = ms->hashTable; >> 526 size_t const h = ZSTD_hashPtr(ip, hashLog, mls); >> 527 U32 matchIndex = hashTable[h]; >> 528 U32* const bt = ms->chainTable; >> 529 U32 const btLog = cParams->chainLog - 1; >> 530 U32 const btMask= (1U << btLog) - 1; >> 531 size_t commonLengthSmaller=0, commonLengthLarger=0; >> 532 const BYTE* const dictBase = ms->window.dictBase; >> 533 U32 const dictLimit = ms->window.dictLimit; >> 534 const BYTE* const dictEnd = dictBase + dictLimit; >> 535 const BYTE* const prefixStart = base + dictLimit; >> 536 U32 const btLow = (btMask >= curr) ? 0 : curr - btMask; >> 537 U32 const windowLow = ZSTD_getLowestMatchIndex(ms, curr, cParams->windowLog); >> 538 U32 const matchLow = windowLow ? windowLow : 1; >> 539 U32* smallerPtr = bt + 2*(curr&btMask); >> 540 U32* largerPtr = bt + 2*(curr&btMask) + 1; >> 541 U32 matchEndIdx = curr+8+1; /* farthest referenced position of any match => detects repetitive patterns */ >> 542 U32 dummy32; /* to be nullified at the end */ >> 543 U32 mnum = 0; >> 544 U32 nbCompares = 1U << cParams->searchLog; >> ^^^^^^^^^^^^^^ >> This is unsigned. >> >> >> 545 >> 546 const ZSTD_matchState_t* dms = dictMode == ZSTD_dictMatchState ? ms->dictMatchState : NULL; >> 547 const ZSTD_compressionParameters* const dmsCParams = >> 548 dictMode == ZSTD_dictMatchState ? &dms->cParams : NULL; >> 549 const BYTE* const dmsBase = dictMode == ZSTD_dictMatchState ? dms->window.base : NULL; >> 550 const BYTE* const dmsEnd = dictMode == ZSTD_dictMatchState ? dms->window.nextSrc : NULL; >> 551 U32 const dmsHighLimit = dictMode == ZSTD_dictMatchState ? (U32)(dmsEnd - dmsBase) : 0; >> 552 U32 const dmsLowLimit = dictMode == ZSTD_dictMatchState ? dms->window.lowLimit : 0; >> 553 U32 const dmsIndexDelta = dictMode == ZSTD_dictMatchState ? windowLow - dmsHighLimit : 0; >> 554 U32 const dmsHashLog = dictMode == ZSTD_dictMatchState ? dmsCParams->hashLog : hashLog; >> 555 U32 const dmsBtLog = dictMode == ZSTD_dictMatchState ? dmsCParams->chainLog - 1 : btLog; >> 556 U32 const dmsBtMask = dictMode == ZSTD_dictMatchState ? (1U << dmsBtLog) - 1 : 0; >> 557 U32 const dmsBtLow = dictMode == ZSTD_dictMatchState && dmsBtMask < dmsHighLimit - dmsLowLimit ? dmsHighLimit - dmsBtMask : dmsLowLimit; >> 558 >> 559 size_t bestLength = lengthToBeat-1; >> 560 DEBUGLOG(8, "ZSTD_insertBtAndGetAllMatches: current=%u", curr); >> 561 >> 562 /* check repCode */ >> 563 assert(ll0 <= 1); /* necessarily 1 or 0 */ >> 564 { U32 const lastR = ZSTD_REP_NUM + ll0; >> 565 U32 repCode; >> 566 for (repCode = ll0; repCode < lastR; repCode++) { >> 567 U32 const repOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode]; >> 568 U32 const repIndex = curr - repOffset; >> 569 U32 repLen = 0; >> 570 assert(curr >= dictLimit); >> 571 if (repOffset-1 /* intentional overflow, discards 0 and -1 */ < curr-dictLimit) { /* equivalent to `curr > repIndex >= dictLimit` */ >> 572 /* We must validate the repcode offset because when we're using a dictionary the >> 573 * valid offset range shrinks when the dictionary goes out of bounds. >> 574 */ >> 575 if ((repIndex >= windowLow) & (ZSTD_readMINMATCH(ip, minMatch) == ZSTD_readMINMATCH(ip - repOffset, minMatch))) { >> 576 repLen = (U32)ZSTD_count(ip+minMatch, ip+minMatch-repOffset, iLimit) + minMatch; >> 577 } >> 578 } else { /* repIndex < dictLimit || repIndex >= curr */ >> 579 const BYTE* const repMatch = dictMode == ZSTD_dictMatchState ? >> 580 dmsBase + repIndex - dmsIndexDelta : >> 581 dictBase + repIndex; >> 582 assert(curr >= windowLow); >> 583 if ( dictMode == ZSTD_extDict >> 584 && ( ((repOffset-1) /*intentional overflow*/ < curr - windowLow) /* equivalent to `curr > repIndex >= windowLow` */ >> 585 & (((U32)((dictLimit-1) - repIndex) >= 3) ) /* intentional overflow : do not test positions overlapping 2 memory segments */) >> 586 && (ZSTD_readMINMATCH(ip, minMatch) == ZSTD_readMINMATCH(repMatch, minMatch)) ) { >> 587 repLen = (U32)ZSTD_count_2segments(ip+minMatch, repMatch+minMatch, iLimit, dictEnd, prefixStart) + minMatch; >> 588 } >> 589 if (dictMode == ZSTD_dictMatchState >> 590 && ( ((repOffset-1) /*intentional overflow*/ < curr - (dmsLowLimit + dmsIndexDelta)) /* equivalent to `curr > repIndex >= dmsLowLimit` */ >> 591 & ((U32)((dictLimit-1) - repIndex) >= 3) ) /* intentional overflow : do not test positions overlapping 2 memory segments */ >> 592 && (ZSTD_readMINMATCH(ip, minMatch) == ZSTD_readMINMATCH(repMatch, minMatch)) ) { >> 593 repLen = (U32)ZSTD_count_2segments(ip+minMatch, repMatch+minMatch, iLimit, dmsEnd, prefixStart) + minMatch; >> 594 } } >> 595 /* save longer solution */ >> 596 if (repLen > bestLength) { >> 597 DEBUGLOG(8, "found repCode %u (ll0:%u, offset:%u) of length %u", >> 598 repCode, ll0, repOffset, repLen); >> 599 bestLength = repLen; >> 600 matches[mnum].off = repCode - ll0; >> 601 matches[mnum].len = (U32)repLen; >> 602 mnum++; >> 603 if ( (repLen > sufficient_len) >> 604 | (ip+repLen == iLimit) ) { /* best possible */ >> 605 return mnum; >> 606 } } } } >> 607 >> 608 /* HC3 match finder */ >> 609 if ((mls == 3) /*static*/ && (bestLength < mls)) { >> 610 U32 const matchIndex3 = ZSTD_insertAndFindFirstIndexHash3(ms, nextToUpdate3, ip); >> 611 if ((matchIndex3 >= matchLow) >> 612 & (curr - matchIndex3 < (1<<18)) /*heuristic : longer distance likely too expensive*/ ) { >> 613 size_t mlen; >> 614 if ((dictMode == ZSTD_noDict) /*static*/ || (dictMode == ZSTD_dictMatchState) /*static*/ || (matchIndex3 >= dictLimit)) { >> 615 const BYTE* const match = base + matchIndex3; >> 616 mlen = ZSTD_count(ip, match, iLimit); >> 617 } else { >> 618 const BYTE* const match = dictBase + matchIndex3; >> 619 mlen = ZSTD_count_2segments(ip, match, iLimit, dictEnd, prefixStart); >> 620 } >> 621 >> 622 /* save best solution */ >> 623 if (mlen >= mls /* == 3 > bestLength */) { >> 624 DEBUGLOG(8, "found small match with hlog3, of length %u", >> 625 (U32)mlen); >> 626 bestLength = mlen; >> 627 assert(curr > matchIndex3); >> 628 assert(mnum==0); /* no prior solution */ >> 629 matches[0].off = (curr - matchIndex3) + ZSTD_REP_MOVE; >> 630 matches[0].len = (U32)mlen; >> 631 mnum = 1; >> 632 if ( (mlen > sufficient_len) | >> 633 (ip+mlen == iLimit) ) { /* best possible length */ >> 634 ms->nextToUpdate = curr+1; /* skip insertion */ >> 635 return 1; >> 636 } } } >> 637 /* no dictMatchState lookup: dicts don't have a populated HC3 table */ >> 638 } >> 639 >> 640 hashTable[h] = curr; /* Update Hash Table */ >> 641 >> 642 while (nbCompares-- && (matchIndex >= matchLow)) { >> ^^^^^^^^^^^^ >> This is a post op so it will exit the loop with nbCompares set to -1U. >> >> 643 U32* const nextPtr = bt + 2*(matchIndex & btMask); >> 644 const BYTE* match; >> 645 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ >> 646 assert(curr > matchIndex); >> 647 >> 648 if ((dictMode == ZSTD_noDict) || (dictMode == ZSTD_dictMatchState) || (matchIndex+matchLength >= dictLimit)) { >> 649 assert(matchIndex+matchLength >= dictLimit); /* ensure the condition is correct when !extDict */ >> 650 match = base + matchIndex; >> 651 if (matchIndex >= dictLimit) assert(memcmp(match, ip, matchLength) == 0); /* ensure early section of match is equal as expected */ >> 652 matchLength += ZSTD_count(ip+matchLength, match+matchLength, iLimit); >> 653 } else { >> 654 match = dictBase + matchIndex; >> 655 assert(memcmp(match, ip, matchLength) == 0); /* ensure early section of match is equal as expected */ >> 656 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iLimit, dictEnd, prefixStart); >> 657 if (matchIndex+matchLength >= dictLimit) >> 658 match = base + matchIndex; /* prepare for match[matchLength] read */ >> 659 } >> 660 >> 661 if (matchLength > bestLength) { >> 662 DEBUGLOG(8, "found match of length %u at distance %u (offCode=%u)", >> 663 (U32)matchLength, curr - matchIndex, curr - matchIndex + ZSTD_REP_MOVE); >> 664 assert(matchEndIdx > matchIndex); >> 665 if (matchLength > matchEndIdx - matchIndex) >> 666 matchEndIdx = matchIndex + (U32)matchLength; >> 667 bestLength = matchLength; >> 668 matches[mnum].off = (curr - matchIndex) + ZSTD_REP_MOVE; >> 669 matches[mnum].len = (U32)matchLength; >> 670 mnum++; >> 671 if ( (matchLength > ZSTD_OPT_NUM) >> 672 | (ip+matchLength == iLimit) /* equal : no way to know if inf or sup */) { >> 673 if (dictMode == ZSTD_dictMatchState) nbCompares = 0; /* break should also skip searching dms */ >> ^^^^^^^^^^^^^^ >> Or it could exit here. >> >> 674 break; /* drop, to preserve bt consistency (miss a little bit of compression) */ >> 675 } >> 676 } >> 677 >> 678 if (match[matchLength] < ip[matchLength]) { >> 679 /* match smaller than current */ >> 680 *smallerPtr = matchIndex; /* update smaller idx */ >> 681 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */ >> 682 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */ >> 683 smallerPtr = nextPtr+1; /* new candidate => larger than match, which was smaller than current */ >> 684 matchIndex = nextPtr[1]; /* new matchIndex, larger than previous, closer to current */ >> 685 } else { >> 686 *largerPtr = matchIndex; >> 687 commonLengthLarger = matchLength; >> 688 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */ >> 689 largerPtr = nextPtr; >> 690 matchIndex = nextPtr[0]; >> 691 } } >> 692 >> 693 *smallerPtr = *largerPtr = 0; >> 694 >> --> 695 if (dictMode == ZSTD_dictMatchState && nbCompares) { >> ^^^^^^^^^^ >> The should this be check for if nbCompares == -1? This could be >> intentional. Hard to tell. >> >> 696 size_t const dmsH = ZSTD_hashPtr(ip, dmsHashLog, mls); >> 697 U32 dictMatchIndex = dms->hashTable[dmsH]; >> 698 const U32* const dmsBt = dms->chainTable; >> 699 commonLengthSmaller = commonLengthLarger = 0; >> 700 while (nbCompares-- && (dictMatchIndex > dmsLowLimit)) { >> 701 const U32* const nextPtr = dmsBt + 2*(dictMatchIndex & dmsBtMask); >> 702 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ >> 703 const BYTE* match = dmsBase + dictMatchIndex; >> 704 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iLimit, dmsEnd, prefixStart); >> 705 if (dictMatchIndex+matchLength >= dmsHighLimit) >> 706 match = base + dictMatchIndex + dmsIndexDelta; /* to prepare for next usage of match[matchLength] */ >> 707 >> 708 if (matchLength > bestLength) { >> 709 matchIndex = dictMatchIndex + dmsIndexDelta; >> 710 DEBUGLOG(8, "found dms match of length %u at distance %u (offCode=%u)", >> 711 (U32)matchLength, curr - matchIndex, curr - matchIndex + ZSTD_REP_MOVE); >> 712 if (matchLength > matchEndIdx - matchIndex) >> 713 matchEndIdx = matchIndex + (U32)matchLength; >> 714 bestLength = matchLength; >> 715 matches[mnum].off = (curr - matchIndex) + ZSTD_REP_MOVE; >> 716 matches[mnum].len = (U32)matchLength; >> 717 mnum++; >> 718 if ( (matchLength > ZSTD_OPT_NUM) >> 719 | (ip+matchLength == iLimit) /* equal : no way to know if inf or sup */) { >> 720 break; /* drop, to guarantee consistency (miss a little bit of compression) */ >> 721 } >> 722 } >> 723 >> 724 if (dictMatchIndex <= dmsBtLow) { break; } /* beyond tree size, stop the search */ >> 725 if (match[matchLength] < ip[matchLength]) { >> 726 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */ >> 727 dictMatchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */ >> 728 } else { >> 729 /* match is larger than current */ >> 730 commonLengthLarger = matchLength; >> 731 dictMatchIndex = nextPtr[0]; >> 732 } >> 733 } >> 734 } >> 735 >> 736 assert(matchEndIdx > curr+8); >> 737 ms->nextToUpdate = matchEndIdx - 8; /* skip repetitive patterns */ >> 738 return mnum; >> 739 } >> >> regards, >> dan carpenter >
