views:

185

answers:

5

To begin with, let me say that I understand how and why the problem I'm describing can happen. I was a Computer Science major, and I understand overflow/underflow and signed/unsigned arithmetic. (For those unfamiliar with the topic, Apple's Secure Coding Guide discusses integer overflow briefly.)

My question is about reporting and recovering from such an error once it has been detected, and more specifically in the case of an Objective-C framework. (I write and maintain CHDataStructures.) I have a few collections classes that allocate memory for storing objects and dynamically expand as necessary. I haven't yet seen any overflow-related crashes, probably because my test cases mostly use sane data. However, given unvalidated values, things could explode rather quickly, and I want to prevent that.

I have identified at least two common cases where this can occur:

  1. The caller passes a very large unsigned value (or negative signed value) to -initWithCapacity:.
  2. Enough objects have been added to cause the capacity to dynamically expand, and the capacity has grown large enough to cause overflow.

The easy part is detecting whether overflow will occur. (For example, before attempting to allocate length * sizeof(void*) bytes, I can check whether length <= UINT_MAX / sizeof(void*), since failing this test will mean that the product will overflow and potentially allocate a much smaller region of memory than desired. On platforms that support it, the checkint.h API is another alternative.) The harder part is determining how to deal with it gracefully. In the first scenario, the caller is perhaps better equipped (or at least in the mindset) to deal with a failure. The second scenario can happen anywhere in the code that an object is added to the collection, which may be quite non-deterministic.

My question, then, is this: How is "good citizen" Objective-C code expected to act when integer overflow occurs in this type of situation? (Ideally, since my project is a framework in the same spirit as Foundation in Cocoa, I'd like to model off of the way it behaves for maximum "impedance matching". The Apple documentation I've found doesn't mention much at all about this.) I figure that in any case, reporting the error is a given. Since the APIs to add an object (which could cause scenario 2) don't accept an error parameter, what can I really do to help resolve the problem, if anything? What is really considered okay in such situations? I'm loath to knowingly write crash-prone code if I can do better...

+3  A: 

With regards to dynamically growing, array-based storage, there's only so much that can be done. I'm a developer on the Moab scheduler for supercomputers, and we also deal with very large numbers on systems with thousands of processors, thousands of jobs, and massive amounts of job output. At some point, you can't declare a buffer to be any bigger, without creating a whole new data-type to deal with sizes larger than UINT_MAX, or LONG_LONG_MAX etc., at which point on most "normal" machines you'll be running out of stack/heap space anyway. So I'd say log a meaningful error-message, keep the collection from exploding, and if the user needs to add that many things to a CHDataStructures collection, they ought to know that there are issues dealing with very large numbers, and the caller ought to check whether the add was successful (keep track of the size of the collection, etc.).

Another possibility is to convert array-based storage to dynamically allocated, linked-list-based storage when you get to the point when you can't allocate a larger array with an unsigned int or unsigned long. This would be expensive, but would happen rarely enough that it shouldn't be terribly noticeable to users of the framework. Since the limit on the size of a dynamically allocated, linked-list-based collection is the size of the heap, any user that added enough items to a collection to "overflow" it then would have bigger problems than whether or not his item was successfully added.

alesplin
+4  A: 

Log and raise an exception.

You can only really be a good citizen to other programmers, not the end user, so pass the problem upstairs and do it in a way that clearly explains what is going on, what the problem is (give numbers) and where it is happening so the root cause can be removed.

Steve Weller
This is a good answer, but I can only choose one, and @bbum's answer has additional helpful detail and context.
Quinn Taylor
+1  A: 

I'd say the correct thing to do would be to do what the Cocoa collections do. For example, if I have the following code:

int main (int argc, const char * argv[]) {
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];

    NSMutableArray * a = [[NSMutableArray alloc] init];

    for (uint32_t i = 0; i < ULONG_MAX; ++i) {
        for (uint32_t i = 0; i < 10000000; ++i) {
            [a addObject:@"foo"];
        }
        NSLog(@"%lu rounds of 10,000,000 completed", i+1);
    }

    [a release];

    [pool drain];
    return 0;
}

..and just let it run, it will eventually die with EXC_BAD_ACCESS. (I compiled and ran this as a 32-bit app so I could be sure to run out of space when I hit 2**32 objects.

In other words, throwing an exception would be nice, but I don't think you really have to do anything.

Dave DeLong
A: 

Using assertions and a custom assertion handler may be the best available option for you.

With assertions, you could easily have many checkpoints in your code, where you verify that things work as they should. If they don't, by default the assertion macro logs the error (developer-defined string), and throws an exception. You can also override the default behavior using a custom assertion handler and implement a different way to handle error conditions (even avoid throwing exceptions).

This approach allows for a greater degree of flexibility and you can easily modify your error handling strategy (throwing exceptions vs. dealing with errors internally) at any point.

The documentation is very concise: Assertions and Logging.

Nick Toumpelis
+3  A: 

There are two issues at hand:

(1) An allocation has failed and you are out of memory.

(2) You have detected an overflow or other erroneous condition that will lead to (1) if you continue.

In the case of (1), you are hosed (unless the failed allocation was both stupid large & you know that the failed allocation was only that one). If this happens, the best thing you can do is to crash as quickly as possible and leave behind as much evidence as you can. In particular, creating a function that calls abort() of a name like IAmCrashingOnPurposeBecauseYourMemoryIsDepleted() will leave evidence in the crash log.

If it is really (2), then there are additional questions. Specifically, can you recover from the situation and, regardless, is the user's data still intact? If you can recover, then grand... do so and the user never has to know. If not, then you need to make absolutely sure that the user's data is not corrupt. If it isn't, then save and die. If the user's data is corrupt, then do your best to not persist the corrupted data and let the user know that something has gone horribly wrong. If the user's data is already persisted, but corrupt, then... well... ouch... you might want to consider creating a recovery tool of some kind.

bbum
Happily, since the code in question is a low-level collections framework, I can't really worry specifically about any user data, since I have no idea how to persist it or check for corruption. In the few places where (2) could occur, I'll plan to do something intelligent, like trying a smaller allocation (if it's a collection growing) or returning nil. In any case, I'll certainly log evidence to help track down the issue. Thanks for the helpful context for doing that.
Quinn Taylor