Coverity: HUF_buildCTableFromTree(): Memory - corruptions

Hello!

This is an experimental semi-automated report about issues detected by Coverity from a scan of next-20221026 as part of the linux-next scan project:
https://scan.coverity.com/projects/linux-next-weekly-scan

You're getting this email because you were associated with the identified lines of code (noted below) that were touched by commits:

Mon Oct 24 12:12:32 2022 -0700

    2aa14b1ab2c4 ("zstd: import usptream v1.5.2")

Coverity reported the following:

*** CID 1525550: Memory - corruptions (OVERRUN) /lib/zstd/compress/huf_compress.c: 673 in HUF_buildCTableFromTree()
667 min += nbPerRank[n];
668 min >>= 1;
669 } }
670 for (n=0; n<alphabetSize; n++)
671 HUF_setNbBits(ct + huffNode[n].byte, huffNode[n].nbBits); /* push nbBits per symbol, symbol order */
672 for (n=0; n<alphabetSize; n++)
vvv CID 1525550: Memory - corruptions (OVERRUN)
vvv Overrunning array "valPerRank" of 13 2-byte elements at element index 255 (byte offset 511) using index "HUF_getNbBits(ct[n])" (which evaluates to 255).
673 HUF_setValue(ct + n, valPerRank[HUF_getNbBits(ct[n])]++); /* assign value within rank, symbol order */
674 CTable[0] = maxNbBits;
675 }
676
677 size_t HUF_buildCTable_wksp (HUF_CElt* CTable, const unsigned* count, U32 maxSymbolValue, U32 maxNbBits, void* workSpace, size_t wkspSize)
678 {

!-------------------------------------------------------------------|
This Message Is From an External Sender

|-------------------------------------------------------------------!

Quoted 15 lines · coverity-bot

Hello!

This is an experimental semi-automated report about issues detected by Coverity from a scan of next-20221026 as part of the linux-next scan project:
https://scan.coverity.com/projects/linux-next-weekly-scan

You're getting this email because you were associated with the identified lines of code (noted below) that were touched by commits:

Mon Oct 24 12:12:32 2022 -0700
2aa14b1ab2c4 ("zstd: import usptream v1.5.2")

Coverity reported the following:

Quoted 16 lines

*** CID 1525550: Memory - corruptions (OVERRUN) /lib/zstd/compress/huf_compress.c: 673 in HUF_buildCTableFromTree()
667 min += nbPerRank[n];
668 min >>= 1;
669 } }
670 for (n=0; n<alphabetSize; n++)
671 HUF_setNbBits(ct + huffNode[n].byte, huffNode[n].nbBits); /* push nbBits per symbol, symbol order */
672 for (n=0; n<alphabetSize; n++)
vvv CID 1525550: Memory - corruptions (OVERRUN)
vvv Overrunning array "valPerRank" of 13 2-byte elements at element index 255 (byte offset 511) using index "HUF_getNbBits(ct[n])" (which evaluates to 255).
673 HUF_setValue(ct + n, valPerRank[HUF_getNbBits(ct[n])]++); /* assign value within rank, symbol order */
674 CTable[0] = maxNbBits;
675 }
676
677 size_t HUF_buildCTable_wksp (HUF_CElt* CTable, const unsigned* count, U32 maxSymbolValue, U32 maxNbBits, void* workSpace, size_t wkspSize)
678 {

I haven't looked at the other warnings, but from a glance this code looks fine to me. Coverity is claiming that some symbols can have 255 bits, but we just went through HUF_setMaxHeight(), which enforced that no symbols have more bits than HUF_TABLELOG_MAX.

Heuristic checks like this are likely to generate lots of false positives in compression code, I think.

!-------------------------------------------------------------------|
This Message Is From an External Sender

|-------------------------------------------------------------------!

Hello!

This is an experimental semi-automated report about issues detected by Coverity from a scan of next-20221026 as part of the linux-next scan project:
https://scan.coverity.com/projects/linux-next-weekly-scan

You're getting this email because you were associated with the identified lines of code (noted below) that were touched by commits:

Mon Oct 24 12:12:32 2022 -0700
2aa14b1ab2c4 ("zstd: import usptream v1.5.2")

Coverity reported the following:

*** CID 1525550: Memory - corruptions (OVERRUN) /lib/zstd/compress/huf_compress.c: 673 in HUF_buildCTableFromTree()
667 min += nbPerRank[n];
668 min >>= 1;
669 } }
670 for (n=0; n<alphabetSize; n++)
671 HUF_setNbBits(ct + huffNode[n].byte, huffNode[n].nbBits); /* push nbBits per symbol, symbol order */
672 for (n=0; n<alphabetSize; n++)
vvv CID 1525550: Memory - corruptions (OVERRUN)
vvv Overrunning array "valPerRank" of 13 2-byte elements at element index 255 (byte offset 511) using index "HUF_getNbBits(ct[n])" (which evaluates to 255).
673 HUF_setValue(ct + n, valPerRank[HUF_getNbBits(ct[n])]++); /* assign value within rank, symbol order */
674 CTable[0] = maxNbBits;
675 }
676
677 size_t HUF_buildCTable_wksp (HUF_CElt* CTable, const unsigned* count, U32 maxSymbolValue, U32 maxNbBits, void* workSpace, size_t wkspSize)
678 {

*** CID 1525549: Memory - illegal accesses (OVERRUN) /lib/zstd/compress/huf_compress.c: 187 in HUF_writeCTable_wksp() 181

182         /* convert to weight */
183         wksp->bitsToWeight[0] = 0;
184         for (n=1; n<huffLog+1; n++)

185 wksp->bitsToWeight[n] = (BYTE)(huffLog + 1 - n);
186 for (n=0; n<maxSymbolValue; n++)
vvv CID 1525549: Memory - illegal accesses (OVERRUN)
vvv Overrunning array "wksp->bitsToWeight" of 13 bytes at byte offset 255 using index "HUF_getNbBits(ct[n])" (which evaluates to 255).
187 wksp->huffWeight[n] = wksp->bitsToWeight[HUF_getNbBits(ct[n])];
188

189         /* attempt weights compression by FSE */
190         if (maxDstSize < 1) return ERROR(dstSize_tooSmall);
191         {   CHECK_V_F(hSize, HUF_compressWeights(op+1, maxDstSize-1, wksp->huffWeight, maxSymbolValue, &wksp->wksp, sizeof(wksp->wksp)) );

192 if ((hSize>1) & (hSize < maxSymbolValue/2)) { /* FSE compressed */

*** CID 1525501: Memory - corruptions (OVERRUN) /lib/zstd/compress/huf_compress.c: 253 in HUF_readCTable()
247 HUF_setNbBits(ct + n, (BYTE)(tableLog + 1 - w) & -(w != 0));
248 } }
249
250 /* fill val */
251 { U16 nbPerRank[HUF_TABLELOG_MAX+2] = {0}; /* support w=0=>n=tableLog+1 */
252 U16 valPerRank[HUF_TABLELOG_MAX+2] = {0};
vvv CID 1525501: Memory - corruptions (OVERRUN)
vvv Overrunning array "nbPerRank" of 14 2-byte elements at element index 255 (byte offset 511) using index "HUF_getNbBits(ct[n])" (which evaluates to 255).

253             { U32 n; for (n=0; n<nbSymbols; n++) nbPerRank[HUF_getNbBits(ct[n])]++; }
254             /* determine stating value per rank */
255             valPerRank[tableLog+1] = 0;   /* for w==0 */
256             {   U16 min = 0;

257 U32 n; for (n=tableLog; n>0; n--) { /* start at n=tablelog <-> w=1 */
258 valPerRank[n] = min; /* get starting value within each rank */

*** CID 1525481: Memory - corruptions (OVERRUN) /lib/zstd/compress/huf_compress.c: 263 in HUF_readCTable()
257 U32 n; for (n=tableLog; n>0; n--) { /* start at n=tablelog <-> w=1 */

258                     valPerRank[n] = min;     /* get starting value within each rank */
259                     min += nbPerRank[n];
260                     min >>= 1;

261 } }
262 /* assign value within rank, symbol order */
vvv CID 1525481: Memory - corruptions (OVERRUN)
vvv Overrunning array "valPerRank" of 14 2-byte elements at element index 255 (byte offset 511) using index "HUF_getNbBits(ct[n])" (which evaluates to 255).
263 { U32 n; for (n=0; n<nbSymbols; n++) HUF_setValue(ct + n, valPerRank[HUF_getNbBits(ct[n])]++); }
264 }
265
266 *maxSymbolValuePtr = nbSymbols - 1;
267 return readSize;
268 }

*** CID 1505962: (UNINIT)
/lib/zstd/compress/zstd_compress.c: 2436 in ZSTD_buildSequencesStatistics()

2430                     prevEntropy->offcodeCTable,
2431                     sizeof(prevEntropy->offcodeCTable),
2432                     entropyWorkspace, entropyWkspSize);

2433 if (ZSTD_isError(countSize)) {
2434 DEBUGLOG(3, "ZSTD_buildCTable for Offsets failed");
2435 stats.size = countSize;
vvv CID 1505962: (UNINIT)
vvv Using uninitialized value "stats". Field "stats.MLtype" is uninitialized.
2436 return stats;
2437 }
2438 if (stats.Offtype == set_compressed)
2439 stats.lastCountSize = countSize;
2440 op += countSize;
2441 assert(op <= oend);
/lib/zstd/compress/zstd_compress.c: 2404 in ZSTD_buildSequencesStatistics()

2398                     prevEntropy->litlengthCTable,
2399                     sizeof(prevEntropy->litlengthCTable),
2400                     entropyWorkspace, entropyWkspSize);

2401 if (ZSTD_isError(countSize)) {
2402 DEBUGLOG(3, "ZSTD_buildCTable for LitLens failed");
2403 stats.size = countSize;
vvv CID 1505962: (UNINIT)
vvv Using uninitialized value "stats". Field "stats.Offtype" is uninitialized.
2404 return stats;
2405 }
2406 if (stats.LLtype == set_compressed)
2407 stats.lastCountSize = countSize;
2408 op += countSize;
2409 assert(op <= oend);

*** CID 1505959: Memory - corruptions (OVERRUN) /lib/zstd/compress/zstd_compress.c: 3220 in ZSTD_estimateBlockSize_sequences()

3214                                                       const ZSTD_fseCTablesMetadata_t* fseMetadata,
3215                                                       void* workspace, size_t wkspSize,
3216                                                       int writeEntropy)

3217 {
3218 size_t sequencesSectionHeaderSize = 1 /* seqHead */ + 1 /* min seqSize size */ + (nbSeq >= 128) + (nbSeq >= LONGNBSEQ);
3219 size_t cSeqSizeEstimate = 0;
vvv CID 1505959: Memory - corruptions (OVERRUN)
vvv Overrunning array "OF_defaultNorm" of 29 2-byte elements by passing it to a function which accesses it at element index 31 (byte offset 63) using argument "31U".
3220 cSeqSizeEstimate += ZSTD_estimateBlockSize_symbolType(fseMetadata->ofType, ofCodeTable, nbSeq, MaxOff,

3221                                              fseTables->offcodeCTable, NULL,
3222                                              OF_defaultNorm, OF_defaultNormLog, DefaultMaxOff,
3223                                              workspace, wkspSize);

3224 cSeqSizeEstimate += ZSTD_estimateBlockSize_symbolType(fseMetadata->llType, llCodeTable, nbSeq, MaxLL,
3225 fseTables->litlengthCTable, LL_bits,

If these are false positives, please let us know so we can mark it as such, or teach the Coverity rules to be smarter. If not, please make sure fixes get into linux-next. :) For patches fixing this, please include these lines (but double-check the "Fixes" first):

Reported-by coverity-bot <[email protected]>

Addresses-Coverity-ID: 1525550 ("Memory - corruptions")

Fixes 2aa14b1ab2c4 ("zstd: import usptream v1.5.2")

Thanks for your attention!

Signature · 1 line

Coverity-bot

Quoted 4 lines

If these are false positives, please let us know so we can mark it as such, or teach the Coverity rules to be smarter. If not, please make sure fixes get into linux-next. :) For patches fixing this, please include these lines (but double-check the "Fixes" first):

These are all false positives.