* [bug report] lib: zstd: Upgrade to latest upstream zstd version 1.4.10
@ 2021-10-08 6:37 Dan Carpenter
2021-10-08 17:59 ` Nick Terrell
0 siblings, 1 reply; 4+ messages in thread
From: Dan Carpenter @ 2021-10-08 6:37 UTC (permalink / raw)
To: terrelln, stanjo74; +Cc: kernel-janitors
Hello Nick Terrell,
I grepped the README for zstd and it doesn't appear there is a mailing
list to add to the CC.
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)
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
^ permalink raw reply [flat|nested] 4+ messages in thread* Re: [bug report] lib: zstd: Upgrade to latest upstream zstd version 1.4.10 2021-10-08 6:37 [bug report] lib: zstd: Upgrade to latest upstream zstd version 1.4.10 Dan Carpenter @ 2021-10-08 17:59 ` Nick Terrell 2021-10-08 18:28 ` Nick Terrell 0 siblings, 1 reply; 4+ messages in thread From: Nick Terrell @ 2021-10-08 17:59 UTC (permalink / raw) To: Dan Carpenter; +Cc: stanjo74, kernel-janitors@vger.kernel.org > On Oct 7, 2021, at 11:37 PM, Dan Carpenter <dan.carpenter@oracle.com> 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) > > 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 ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [bug report] lib: zstd: Upgrade to latest upstream zstd version 1.4.10 2021-10-08 17:59 ` Nick Terrell @ 2021-10-08 18:28 ` Nick Terrell 2021-10-09 8:25 ` Dan Carpenter 0 siblings, 1 reply; 4+ messages in thread From: Nick Terrell @ 2021-10-08 18:28 UTC (permalink / raw) To: Dan Carpenter; +Cc: stanjo74, kernel-janitors@vger.kernel.org > On Oct 8, 2021, at 10:59 AM, Nick Terrell <terrelln@fb.com> wrote: > > > >> On Oct 7, 2021, at 11:37 PM, Dan Carpenter <dan.carpenter@oracle.com> 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 > ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [bug report] lib: zstd: Upgrade to latest upstream zstd version 1.4.10 2021-10-08 18:28 ` Nick Terrell @ 2021-10-09 8:25 ` Dan Carpenter 0 siblings, 0 replies; 4+ messages in thread From: Dan Carpenter @ 2021-10-09 8:25 UTC (permalink / raw) To: Nick Terrell; +Cc: stanjo74, kernel-janitors@vger.kernel.org On Fri, Oct 08, 2021 at 06:28:17PM +0000, Nick Terrell wrote: > > 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! Heh. I absolutely filtered the results. regards, dan carpenter ^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2021-10-09 8:25 UTC | newest] Thread overview: 4+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2021-10-08 6:37 [bug report] lib: zstd: Upgrade to latest upstream zstd version 1.4.10 Dan Carpenter 2021-10-08 17:59 ` Nick Terrell 2021-10-08 18:28 ` Nick Terrell 2021-10-09 8:25 ` Dan Carpenter
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox