Handling unsigned overflow of size_t

[Adam Warner]

Hi all!

When dealing with dynamically adjusted objects are you ever concerned that
you'll double the requested size of the object and overflow size_t so that
the requested size e.g. becomes zero?

I realise it's extremely likely that all memory and address space will be
exhausted before one is able to malloc an object close to the maximum of
size_t. I'd just like to know best practice.

Let's consider a 32-bit address space with an object 0x80000000 size_t.
The algorithm is to always double the size of the object. When you compute
the new size of the object it will be zero.

To avoid this one could start with a size_t one less than a power of two
and always add one before doubling. Afterwards subtracting one again.

So the object above would be 0x7FFFFFFF size_t. One adds 1 (0x80000000),
doubles it (0x00000000) and subtracts 1 (0xFFFFFFFF) so that realloc
doesn't have a hope of succeeding and will return NULL to check for
instead of undefined behaviour resulting from reallocating a smaller
object.

On the other hand it feels odd to request a new size each time that is not
a power of two. Who ever allocates 2^n-1 bytes instead of 2^n?

Thanks for your advice.

Regards,
Adam

 

[Alex Fraser]

When dealing with dynamically adjusted objects are you ever concerned
that you'll double the requested size of the object and overflow size_t
so that the requested size e.g. becomes zero?

If you're concerned, why not just detect the overflow?

Alex

 

[Adam Warner]

Hi Alex Fraser,

If you're concerned, why not just detect the overflow?

I've decided to keep allocating by 2^n except when overflow is detected:

if (new_realloc_size<=old_realloc_size) {
new_realloc_size=SIZE_MAX;
new_stack_size=new_realloc_size/sizeof(void *);
}

I expect this will be more idiomatic than reallocating by a size of
2^n-1, i.e. (previous_size+1)*2-1 each time; where if the previous_size
starts as one less than a power of 2 there is never any need to
explicitly check for unsigned overflow.

Regards,
Adam

 

[Lawrence Kirby]

Hi Alex Fraser,



I've decided to keep allocating by 2^n except when overflow is detected:

if (new_realloc_size<=old_realloc_size) {
new_realloc_size=SIZE_MAX;
new_stack_size=new_realloc_size/sizeof(void *);
}

I expect this will be more idiomatic than reallocating by a size of
2^n-1, i.e. (previous_size+1)*2-1 each time; where if the previous_size

Or just previous_size*2+1

Also consider not doubling the size each time, that can lead to a lot of
wastage. Something like previous_size + previous_size/2 can work well
given a suitable starting size.

starts as one less than a power of 2 there is never any need to
explicitly check for unsigned overflow.

You're assuming that an allocation of SIZE_MAX will fail. That's not
necessarily true, although likely on 32 bit and larger implementations.
You would be much better off testing for overflow, which as others have
said has happened if the new value is less than the old one. You can
probably reject the equal case too.

Lawrence

 

[CBFalconer]

.... snip ...

Also consider not doubling the size each time, that can lead to a
lot of wastage. Something like previous_size + previous_size/2 can
work well given a suitable starting size.

The starting size doesn't affect anything more than in the doubling
scheme. The only real difference is the minimum usage percentage.

 

[infobahn]

The starting size doesn't affect anything more than in the doubling
scheme.

Oh, but it does! With the strategy prev + prev / 2, two starting
values (0 and 1) are most /un/suitable, as I'm sure Mr Kirby is aware.