SQLite Forum

integer overflow in pager.c
Login

integer overflow in pager.c

(1) By anonymous on 2021-09-13 12:52:17 [link] [source]

hello!

it seems like you have an integer overflow in a pager code right here

pRel->iSubRec have type Pgno (which is an alias to u32) and pPager->pageSize+4 have type int

it may overflow if pageSize is maximum (which is 65536 IIRC) and number of subrecords is also somewhere around 65536. also, on line 3434 iSubRec is casted to i64 before a similar multiplication, which kinda confirms that it is a bug

(2) By Gunter Hick (gunter_hick) on 2021-09-13 13:10:35 in reply to 1 [link] [source]

I don't think so.

Both statements multiply two 32 bit integers yielding a 64 bit result. The values you claim as problematic both use 16 or 17 bits, which would overflow a 32bit result, but come nowhere near overflowing 64 bit integers.

i64 offset = (i64)pSavepoint->iSubRec*(4+pPager->pageSize);

i64 sz = (pPager->pageSize+4)*pRel->iSubRec;

Even multiplying the maximum pagesize (17 bits) by maxint (31 bits) only yields 48 bits of product, well within the 63 bits available for positive integers.

(3) By anonymous on 2021-09-13 13:21:31 in reply to 2 [link] [source]

(pPager->pageSize+4)*pRel->iSubRec has type of u32 and then is assigned to i64

(4) By Larry Brasfield (larrybr) on 2021-09-13 13:31:30 in reply to 2 [link] [source]

Both statements multiply two 32 bit integers yielding a 64 bit result.

That would be a reasonable result, (and conforms to what many/most hardware multipliers do), but does not conform to C rules. In C, this: i64 sz = (pPager->pageSize+4)*pRel->iSubRec; , where the pageSize and iSubRec members are both 32-bit objects, means: Multiply these 32-bit integers to produce a 32-bit integer, then promote that integer to 64 bits (by sign bit extension or 0-fill according to signedness of the operands) and transfer into the 64-bit assignee.

This is counter-intuitive, but it avoids a language design issue where type must flow toward leaves of expression trees.

(5) By ddevienne on 2021-09-13 14:44:51 in reply to 4 [link] [source]

So the anon-OP is right, and a fix is necessary? Not quite clear from your post.

(6) By Larry Brasfield (larrybr) on 2021-09-13 15:01:24 in reply to 5 [source]

My point went only to Gunter's assertion about multiplication details in C, not the OP's bug report. As can be seen in Richard's fix, he thinks a fix is necessary. I had gotten only to determining the limits of each operand's valuea before I saw his determination that an overflow needed to be avoided.


a. Whether an overflow was possible or not depends on the actual maximum operand values rather than just their types. So a deeper code analysis was required than what was evident in the OP's statements.

(7) By Gunter Hick (gunter_hick) on 2021-09-14 06:11:22 in reply to 4 [link] [source]

I asked my C compiler (GCC 4.8.5/RH7/IA64) about this:

    int32_t              a = 65536;
    int32_t              b = 0x7ffffff;
    int64_t              p;

    p = a*b;

and got this

32 bit init:   c7 45 fc 00 00 01 00    movl   $0x10000,-0x4(%rbp)
32 bit init:   c7 45 f8 ff ff ff 07    movl   $0x7ffffff,-0x8(%rbp)
32 bit load:   8b 45 fc                mov    -0x4(%rbp),%eax
32 bit mult:   0f af 45 f8             imul   -0x8(%rbp),%eax
32->64 conv:   48 98                   cltq
64 bit stor:   48 89 45 f0             mov    %rax,-0x10(%rbp)

and then about this:

    int32_t              a = 65536;
    int32_t              b = 0x7ffffff;
    int64_t              p;

    p = (int64_t)a*b;

32 bit init:   c7 45 fc 00 00 01 00    movl   $0x10000,-0x4(%rbp)
32 bit init:   c7 45 f8 ff ff ff 07    movl   $0x7ffffff,-0x8(%rbp)
32 bit load:   8b 45 fc                mov    -0x4(%rbp),%eax
64 bit cast:   48 63 d0                movslq %eax,%rdx
32 bit load:   8b 45 f8                mov    -0x8(%rbp),%eax
32->64 conv:   48 98                   cltq
64 bit mult:   48 0f af c2             imul   %rdx,%rax
64 bit stor:   48 89 45 f0             mov    %rax,-0x10(%rbp)

So yes, there may be truncation without a cast. Machine code is 6 bytes longer and 64 bit multiplication seems to require both operands in registers.