Do ALWAYS() checks in btree.c test correct condition?

(1) By zmiklank on 2024-05-27 10:37:54 [source]

Hi,

file btree.c uses ALWAYS check multiple times for hardening the conditions in for loops. Examples:

 7503   for(k=0; ALWAYS(k<NB*2) && pCArray->ixNx[k]<=i; k++){}

 7586   for(k=0; ALWAYS(k<NB*2) && pCArray->ixNx[k]<=i ; k++){}

 8697     for(k=0; ALWAYS(k<NB*2) && b.ixNx[k]<=j; k++){}

I understand that the ALWAYS macros should not be needed really, and are present only for making the sqlite more resilient. However, if something goes wrong and they are used then checking if (k<6) in above mentioned cases does not prevent the overflows, because k would still be incremented to 6 and it is used for accessing arrays of size 6 afterwards. Shouldn't the condition be ALWAYS(k<(NB*2)-1) then?

Note: this was brought to my attention by a static analysis tool.

Thanks,

Zuzana Miklankova.

(2) By Dan Kennedy (dan) on 2024-05-27 11:03:42 in reply to 1 [link] [source]

I don't think I follow this report. Which line might the array be accessed with k=6 from?

In C, if the expression (k<6 && a[k]) is evaluated, a[6] will not be accessed, regardless of the value of k.

Also: https://sqlite.org/testing.html#static_analysis

(3) By Richard Hipp (drh) on 2024-05-27 11:33:08 in reply to 1 [link] [source]

No.

ALWAYS() means that the condition is always true. That means that k is never greater than or equal to 6, even after the k++, which means that the array accesses that follow will never overflow.

Check-in 857f6d530949221d adds new assert() statements after the loop to help you static analyzer realize this.

(4) By zmiklank on 2024-05-27 11:37:31 in reply to 2 [link] [source]

Sorry, I should have made the examples more informative.

Here, on line 7571 pCArray->apEnd would be (potentially) accessed at sixth position:

 7570   for(k=0; ALWAYS(k<NB*2) && pCArray->ixNx[k]<=i; k++){}
 7571   pSrcEnd = pCArray->apEnd[k];

This is similar situation. Also on line 7683 array pCArray->ixNx would be accessed on sixth position.

 7653   for(k=0; ALWAYS(k<NB*2) && pCArray->ixNx[k]<=i ; k++){}
 7654   pEnd = pCArray->apEnd[k];
.
.
.
 7683     if( pCArray->ixNx[k]<=i ){

Here, b.apEnd on sixth position would be accessed on line 8765:

 8764     for(k=0; ALWAYS(k<NB*2) && b.ixNx[k]<=j; k++){}
 8765     pSrcEnd = b.apEnd[k];

Also: https://sqlite.org/testing.html#static_analysis

Thanks for pointing this out.

(5) By zmiklank on 2024-05-27 14:06:07 in reply to 3 [link] [source]

Thank you for your reply.

From the code comments:

 516 /*
 517 ** The ALWAYS and NEVER macros surround boolean expressions which
 518 ** are intended to always be true or false, respectively.  Such
 519 ** expressions could be omitted from the code completely.  But they
 520 ** are included in a few cases in order to enhance the resilience
 521 ** of SQLite to unexpected behavior - to make the code "self-healing"
 522 ** or "ductile" rather than being "brittle" and crashing at the first
 523 ** hint of unplanned behavior.
 524 **
 525 ** In other words, ALWAYS and NEVER are added for defensive code.
 526 **
 527 ** When doing coverage testing ALWAYS and NEVER are hard-coded to
 528 ** be true and false so that the unreachable code they specify will
 529 ** not be counted as untested code.
 530 */
 531 #if defined(SQLITE_OMIT_AUXILIARY_SAFETY_CHECKS)
 532 # define ALWAYS(X)      (1)
 533 # define NEVER(X)       (0)
 534 #elif !defined(NDEBUG)
 535 # define ALWAYS(X)      ((X)?1:(assert(0),0))
 536 # define NEVER(X)       ((X)?(assert(0),1):0)
 537 #else
 538 # define ALWAYS(X)      (X)
 539 # define NEVER(X)       (X)
 540 #endif

I understood from the documentation that they might be used to ensure some behavior which should be the standard one if no error occurs. Meaning, they could be needed when something goes wrong and unexpectedly. I might have understood this incorrectly.

Also thank you for adding the asserts.