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]

"Adam Warner" <us****@consulting.net.nz> wrote in message
news:pa****************************@consulting.net .nz...

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,

On Fri, 07 Jan 2005 10:18:23 +0000, Alex Fraser wrote:

"Adam Warner" <us****@consulting.net.nz> wrote in message
news:pa****************************@consulting.net .nz...

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?

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]

On Sat, 08 Jan 2005 01:24:24 +1300, Adam Warner wrote:

Hi Alex Fraser,

On Fri, 07 Jan 2005 10:18:23 +0000, Alex Fraser wrote:

"Adam Warner" <us****@consulting.net.nz> wrote in message
news:pa****************************@consulting.net .nz...

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?

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]

Lawrence Kirby wrote:

"Adam Warner" <us****@consulting.net.nz> wrote in message

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?

.... 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.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[infobahn]

CBFalconer wrote:

Lawrence Kirby wrote:

"Adam Warner" <us****@consulting.net.nz> wrote in message

> 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?

... 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.

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.