tech-userlevel archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Questioning the overflow check in jemalloc



			Hi tech-userlevel@,

I just had a look at the implementation of calloc() in NetBSD's libc, which seems to be from jemalloc actually. Its check for integer overflows is as follows, in src/lib/libc/stdlib/jemalloc.c:

3857         /*
3858          * Try to avoid division here.  We know that it isn't possible to
3859          * overflow during multiplication if neither operand uses any of the
3860          * most significant half of the bits in a size_t.
3861          */
3862         } else if ((unsigned long long)((num | size) &
3863            ((unsigned long long)SIZE_T_MAX << (sizeof(size_t) << 2))) &&
3864            (num_size / size != num)) {
3865                 /* size_t overflow. */
3866                 ret = NULL;
3867                 goto RETURN;
3868         }

I think we essentially have two cases here:
- typical 32-bit platform where sizeof(size_t) is 4, therefore
  sizeof(unsigned long long) > sizeof(size_t)
- typical 64-bit platform where sizeof(size_t) is 8, therefore
  sizeof(unsigned long long) == sizeof(size_t)

In the first case SIZE_T_MAX is shifted left by 16 bits and in the second case 32, as intended. But then why is there a cast to unsigned long long at all? The left operand of that binary AND (&) is a size_t anyway, and will not have any bits set past that size, since it's been binary OR'd.

As a side note, wouldn't it be more correct to bsr (Bit Scan Reverse on x86) both operands, add them, and compare them with sizeof(size_t) << 3? That is, on platforms with an equivalent instruction available of course. (Answering to myself: it seems to have portability and performance impact)

References:
- https://github.com/NetBSD/src/blob/trunk/lib/libc/stdlib/jemalloc.c#L3837
- BSR instruction, http://x86.renejeschke.de/html/file_module_x86_id_20.html
- https://en.wikipedia.org/wiki/Find_first_set

Cheers,
--
khorben



Home | Main Index | Thread Index | Old Index