Checking for overflows

Using a double to do the computation seems reasonable to me. If the overflow you are concerned about is the 32-bit overflow, an 8-byte double can easily accommodate the numbers you'll be handling. Alternatively, you could use a 64-bit integer type.

Quote:

size of a group of things

Like memory used by container? Then std::allocator is a good start. Remember that overflow will occur at least when you break the memory (2^32 char array on 32-bit build or some such).

Quote:

If one of the values is too big, then the result will overflow and be completely wrong.

std containers IIRC have max_elements() or similar function which calculates this.

For linear memory models it's fairly trivial arithmetic. Maximum addressable space is x bits, the rest can be inferred from numeric_limits or similar.

Segmented and other exotic memory models are a pain, but also not generic.


If memory is really limited, then fixed size containers will be used anyway, and those will just check on addition if there is still room. Either way, all the work is actually in defining what "overflow" in this context means precisely, it's not practical to go around trying to invent something generic, since that is provided by STL already.

Quote:

Using a double to do the computation seems reasonable to me.

Using doubles for this purpose, standard or not, is not reasonable. If only standard-compliant compilers are considered, then those target 32 or 64 bit x86 machines almost exclusively. For everything else, the compilers tend to be broken, hardware doesn't support floating point, or is inaccurate or slow.

Given (a,b,M), overflow for operations can be checked pro-actively using integers only. It just becomes a matter of writing enough ifdefs for each supported platform to define maximum ranges.

Quote:

I know for sure that size_t is unsigned in my situation, but how do I calculate it safely? I came up with the following, and while it'll most likely work about everywhere

If it needs to be reliable, then #ifdefs for each platform are the way to go. Note that it might be 16-bit int, but maximum value could be 4096, indicating maximum of 4k continuous memory.

C++ does not define a memory model, it doesn't even assume it's linear. This in part is why std::allocator is so seemingly over-engineered (which for most of today's purpose it is).

@Antheus: I was more talking about C (doing some quite low level stuff - not exactly gaming). For C++ you probably can just rely on the standard library to do the right thing, since that's why it's there in the first place.

The problem with floating comma is if the size of the base is actually smaller than the value of size_t - then there's the risk of having invalid results at the overflow limit.

You could test the Overflow flag using inline assembly. I think the jump used to test it are jo (jump if overvflow) and jno.

The "overflow" here is the problem of memory model, something which is not defined for C or C++.

The sizes here are checking against address space - not numeric overflow. 4096*4096 is perfectly fine numerically, but wouldn't work under DOS, due to 64k pages.

The "overflow" must therefore be checked depending on context of allocation. The following:

sizeof(uint8_t) * size

needs to be examined with regard to how it's used. If malloc were to receive size argument, it needs to use the knowledge of internal allocator state to determine if there exists a chunk of size bytes it can reserve. Allocators frequently fail even though no overflow occurs and there is enough total memory.

Once that problem is solved - the "overflow" issue is solved as well. On a 32-bit machine, the parameter passed to malloc would be a 32-bit int, so overflow as such isn't possible.

As far as caller goes, asking for 2^32 ints will overflow, but that is something that needs to be handled by caller.

std::allocator exposes a rudimentary interface for this - similar mechanism would need to exist in this case. Caller alone cannot determine whether size is valid, but it can be made to conform to required type.

There is no simple answer, since the question is too generic. If such precise memory management is really required, then custom, pre-allocated structures using checked functions to deal with this state are the only way.

Quote:

I know for sure that size_t is unsigned in my situation, but how do I calculate it safely?

There is a MAX value, which defines some maximum size (again, really vague, memory models and addressing modes are tricky). This one is probably #defined for each platform that needs to be supported. Provide a function similar to:

bool test(size_t size, size_t count) {  if (count <= 0) return false;  if (count > MAX) return false;  if (size > MAX) return false;  if (MAX / size > count) return false;  return true;}

MAX may or may not be similar to MAX_INT and similar numeric values. For purposes of memory allocation the numeric ranges are not related. At very least, this doesn't require floats or other magic to test for overflow.

But there simply aren't any other guarantees - it might be possible to compute MAX, but it may be much simpler to just set it. Generic approach doesn't save any time, since it cannot be guaranteed to work correctly.

Assembly isn't portable (not even between compilers, although I'm aiming exclusively for GCC), and is much easier to screw up than hackish C code.

EDIT: er, reading Antheus' post, I was replying to Vortez...

EDIT 2: much at my dislike, there isn't a MAX-like constant for size_t, unlike for the built-in types of the stdint.h types, unless I'm missing something... Actually, I'm gonna check limits.h again, I think I may have missed something there.

Also, with stuff like the one I've shown before it's easy: if I have amount * size, I could check for amount < MAX / size (assuming size is bigger than 0). But what about stuff like width * height * size? In fact, I came here asking because I had that one issue.

EDIT 3: nop, looks like there isn't a MAX constant for size_t in limits.h =/

Quote:

Original post by Sik_the_hedgehog EDIT 2: much at my dislike, there isn't a MAX-like constant for size_t, unlike for the built-in types of the stdint.h types, unless I'm missing something... Actually, I'm gonna check limits.h again, I think I may have missed something there.

No, there isn't. You make a new header, then #ifdef #define for each platform you intend to target, along with each different hardware configuration, different RAM layouts, different memory hierarchies, different addressing models.

On Windows, depending on how application is compiled and depending on how the kernel is booted, the maximum memory on 32-bit might be either 2GB or 3GB, so even though negative 32-bit value might be passed, it could be valid for 2-3GB range.

Quote:

But what about stuff like width * height * size? In fact, I came here asking because I had that one issue.

The only way to handle overflow is on case-by-case basis. (a+b)/2 is notorious error present in all CS textbooks ever written up until 3 or so years ago, when someone at Google finally ran binary search on enough elements to cause the overflow. Without assuming certain behavior of a and b, the only way around it is something like:

x = max(a,b);y = min(a,b);return y + (x-y)/2;

And even this isn't safe (as per all possible binary representations of a and b), it works only if a and b are both positive.

But this isn't relevant for memory allocation. Many functions in C use two parameters for a reason, size and count. The rest is up to user.

First I'd assert that size_t is unsigned. If you don't have a STATIC_ASSERT macro, you can use:Then get the maximum describable array size:This seems like a pretty rare error though.

AFAIK, (size_t)-1 should work on any twos-compliment machine.

Um, you know how I said that with size * amount I could check size < MAX / amount, right? Coming to think on it, width * height * size isn't any different: first I do that check with width and height, then if it successes, I check their multiplication against size (basically, I split it into two multiplications =P). I suppose that could do the job.

EDIT: oh, and thanks to you all =P