Automatic Array Limit Checks in C

Everyone insists that C cannot have automatic array limit checking without a massive performance penalty.  I disagree.

I'm assuming that the way it would be implemented is with a new pointer type, which I'll describe here, and then provide some example code that implements something similar in order to see just what the performance impact would be.

To understand how my new "safe" pointers might work, consider how C's existing "complex" float type works.  It is in reality a structure of two floats, but the compiler allows it to be used as if it is a simple variable.  So you can add them together, multiply them, call functions with them, etc., and it just generates the correct code for those operations, e.g. in the case of multiplying two complex floats, it generates four multiplication operations, an addition and a subtraction, then puts the results into the correct places.  It also knows how to allow complex values to interact with ordinary floats, by considering the ordinary floats to be complex floats with a zero imaginary part.  The result is seamless integration of something new into the existing language in a way that is very easy to use.

In the same way, I'd like to see array limit checking integrated as just a new type of pointer:

safe char array[100];

When the compiler stumbles upon this code, it would actually create a char pointer and a size_t, placing "100" into the size_t automatically.

Alternately, you could allocate an array like this:

safe char *array;
array = malloc(100);

Much like a complex float returned from a function actually returns a structure of two floats, the return from this malloc() would be a structure of a char pointer and a size_t that is equal to the size of the memory allocated.  In the event that malloc() were used to assign to an ordinary pointer without size data, the compiler would know how to discard the size data and copy only the pointer data automatically, making a cast unnecessary.  This is good as it makes it compatible with existing code.

Then you could use the array like this:

safe char array[10] = "Cool stuff!";
printf("String: %s\n", array);

This would pass the array pointer and its size to printf() which could then be certain not to read past the end of the array, useful in the case that you failed to put the null character at the end of the string.  Note that this would require a format identifier other than 's' since 's' is already designed to accept the unsafe pointers that don't contain a limit, but as it would have a new identifier, there would be no need for a new printf(), as printf() already accepts any data type as an argument.

You could also call old functions that expect old unsafe pointers like this:

void old_stuff(char *);
safe char array[100];
old_stuff(array);

Here, the compiler would see that the old_stuff() wants a "char *" while our array is a "safe char *", and it would simply turn our "safe char *" into a "char *" by discarding the size data and passing along only the pointer.  This would allow people to immediately use this new data type even before old libraries are updated to use it. 

As for compatibility in the other direction, that would require an explicit cast, to insert the size data either from a constant or from the variable it is being stored in:

void new_stuff(safe char *);
char array[100];
int size;
size = fread(array, 1, 100, file);
new_stuff( (safe char *) {array, size} );

...or that might also be implemented as a compile-time function...

void new_stuff(safe char *);
char array[100];
int size;
size = fread(array, 1, 100, file);
new_stuff( safe_char(array, size) );

I've mentioned this idea before on Slashdot and probably Reddit, but of course, people are always like "that would ruin the performance of C code." Someone even linked me to some C project that would add limit checks to your C programs, which claimed that they caused a 30% slow-down (or something like that) when added to an executable.  If it were that severe then I could see people taking issue with the idea, but frankly, if it slows the code down that much, then I think someone is doing something wrong. 

To demonstrate, I wrote some code in which I implemented a crude form of what I've described above.  I created a structure that contains both a pointer and a size.  I then created a function to allocate memory for this new pointer type, a function to read from it, and a function to write to it.  Since, if it were implemented as I've described above, assignment would be done with the usual '=' operator rather than with functions, I made the functions inline so that the compiler will in-line the limit checking and the assignment, and thus be able to optimize those operations.

This is the code I ended up with:


So just how much does this hurt the performance?

I compiled it like this: gcc -std=gnu99 -g -O9 -o test test.c

This is the assembly code of the first for() loop:


In this loop, the limit checks had no effect on the performance at all, as the compiler recognized that the limit was never going to be violated and thus never included the limit checks.  It also un-rolled the for() loop and reduced the iterations on the loop to only 9, since the last last position in the array is overwritten after the loop.  Clearly this limit-checking isn't slowing down the compiler in this case, as this is exactly the same code it would have created without limit checks.

So what about the second loop where the limit is violated?


Here the compiler recognizes that every access except the last one is valid.  So it reduces the for() loop to only 10 iterations, then in place of the 11th iteration, it instead places a copy of the code that generates the error message and calls exit(). 

The result is that, in every case where the limit was not violated, this limit checking added no new code to the program.  Indeed, where the limit was violated, the compiler removed the code for that operation from the program, meaning that using the limit checks actually sped up the execution of the program by some insignificant amount.  That's a fine result there.

Now obviously in more complex programs the compiler is going to occasionally actually have to check the limit.  An example is when a function is called in a function in an external object file.  So what happens if we do that?

I created a multi-file example, but rather than put multiple files of code in this post, I'll just make a download link for it.  The above example is in there as well. 

The new code is basically the same as the above example, just that I put the safe_malloc() call in one file, then the safe_char_pointer is passed as a function argument to a function in another file which contains the for() loops and the printf() calls, then each file is compiled separately to ensure that GCC generates a function that works with an array of any length since it doesn't know what the array length will be when it compiles the function.

The new function isn't so awesome.  Basically, the compiler chose to unroll the loop, and each iteration looks roughly like this, just with different values:


So it is performing the limit check on every iteration of the loop.  That's a bummer, as there is no reason it has to do that. 

The exit() involved in the error routine means that, if the limit is violated, what ends up in the array is irrelevant.  Thus there is no reason that the array size needs to be checked more than once.  ...and the compiler knows that.  If I modify the first example so that the first for() loop goes to 11, it creates an executable which has code that first calls malloc(), then calls fprintf(), then calls exit(), with no sign of the for() loop or the rest of the program anywhere. 

The problem seems to be that, while the compiler realizes that if the limit is greater than 9 then it is also greater than everything less than 9, it doesn't consider that perhaps it can perform that comparison to 9 before it performs the comparison to the smaller numbers, and in doing so, avoid all of the other comparisons.  Indeed, if I comment out the assignment within safe_write(), the generated code is just a long list of compares and conditional jumps which could quite obviously be optimized by eliminating all but the last one.  So either this is an obvious optimization that the compiler simply doesn't yet know how to make, or it is some sort of bug in the optimizer causing it to miss this optimization.

Anyway, hoping to force the compiler to make this optimization, before the first for() loop I added a safe_write() call that writes to the tenth element of the array, to "trick" the compiler into performing that comparison first.  So the code now looks like this:


Upon compiling that code, I get this:


That's what I expected it to do to begin with.  It put one check at the beginning of the function for the limit, and if it succeeds, it proceeds to the un-rolled for() loop, this time without limit checks.  It also skips writing the value from that initial call to safe_write() since it knows it is overwritten by the for() loop.  Thus the performance penalty here is one compare and one conditional jump, exactly what you'd get if you were to implement the limit checks manually by passing a size along with every pointer and simply checking the size at the top of the function.

Anyway, that's an optimization that I think the compiler authors could easily implement when adding support for this new pointer type with limit checking, and with that, the performance penalty of limit checks would be almost non-existent.

...but I know people won't think that's good enough.  Any performance penalty is too much for some people.  The way I look at it, I can buy a faster computer, but I can't buy a more secure one.  So even if something like this cut my computer down to half speed, I'd be loving every minute of it as I finally feel confident enough to open the SSH port on my router.

...and besides, in cases where people really don't care about security, they can just disable the limit checks with a compiler flag.  Meanwhile, the fact that the limit checks are even an option will mean that some people will use them and so bugs will be discovered and fixed.  The result of that will be that software is safer even when compiled without the limit checks.

Hopefully this idea will catch on someday.  I've noticed that I sometimes spot people repeating ideas I was talking about five to ten years ago.  I don't know if the ideas started with me or if they were independently discovered (certainly no one seemed to like the ideas when I was talking about them, so I assume it's the latter), but either way, it's nice that stuff isn't doomed to never improve.  So I expect C will eventually have pointers like this, it just might be five to twenty years before it happens.