Modernizing C arrays for greater memory safety: a case study in the Linux kernel
people.kernel.org
people.kernel.org
While what the article describes is clever, it is needlessly complex, and filled with various compiler switches and extensions.
In contrast, here's a stupid simple approach:
https://www.digitalmars.com/articles/C-biggest-mistake.html
where bounds-checkable arrays are declared as:
int a[..];
int s[..] = "string";
s[10] = 'x'; // fatal runtime error
int *p = (int*) malloc(10);
int a[..] = p[0 .. 10];
int *p = &a[3]; // point to 3rd element of a[..]
Does it work? We've been doing that with D for over 20 years. Hell yeah, it works. It works fantastically well. It does not disturb any existing C code.
Also what you're proposing...would be an extension!
With the [..] proposal, it is easy enough to convert it back and forth between pointers and [..] to conform to required interfaces. One could even make the [..] implicitly convertible to a pointer.
The reasoning most likely being that a bunch of annotations to structs, and perhaps some changes to calls to kmalloc() would be less destructive and much simpler than breaking the kernel ABI and altering the base size of any struct that used that idiom while also having to change every for loop or whatnot in the kernel that uses an explicit counter member name.
https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...
That pattern allows us to gracefully support new compiler features optionally and gracefully when people upgrade to toolchains that support them.
I suspect with `..` we could do something similar with __has_feature preprocessor guards.
Whether it's these extensions or `..`, we still would need to update struct definitions. That's at least the same amount of work. If we need to update member names due to `..`, then that's even more work!
That said, the two production compilers that can build the Linux kernel already support member attributes, and compiler inserted bounds checks against immediates. It's trivial to key off an attribute to change the inserted bounds check to a runtime load of a the corresponding member (and maybe a min between that and a fixed length, for non-flexible arrays that may not have been fully initialized for instance) and check against that. With `..` I would need to add new tokens, parsing (both for the declaration, slicing, and implicit conversions), and then the codegen.
There are times where we don't care about ABI within the kernel, so I do think it makes sense to have two different extensions here (implicit fat pointers and non-ABI modifying ways of denoting existing struct members are meant to be runtime bounds). Deploying the correct variant will take careful thought I suspect.
I haven't put enough thought into converting to/from fat pointers, so I'm glad you brought that up. It's something I'll have to think about more.
My initial gut reaction to implicit conversions is that C has enough wretched implicit conversions and promotions that are error prone, but perhaps if it is such an ergonomics win...though having a fat pointer decay to a regular pointer _implicitly_ feels like what I never want to happen.
D doesn't do that implicit decay, but I was thinking of the kernel requirements of no API change. A simple way to convert a phat pointer to a pointer is:
&a[0]
Since the pointer <=> phat pointer conversions are trivial operations, one can easily go back and forth between them depending on what part of the code one wants the overflow checks on vs the legacy interfaces.
With a couple of C macros one could turn on/off declaring arrays as pointers or phat pointers, and turn on/off the slicing code. In this way it will still compile with old compilers.
> We can turn a pointer into a bounds checked array by "slicing" it:
> int *p = (int*) malloc(10); > int a[..] = p[0 .. 10];
When `p` is a parameter in a function, the function cannot know that it can create a slice of up to 10 elements (I assume that the `p[0 .. 10]` creates an array indexed from 0 - 9).
What if the line was:
int a[..] = p[0..12]
> A bounds checked array can be turned into a pointer:
> int *p = &a[3]; // point to 3rd element of a[..]
Assuming that a indexes from 0 to 9, what happens when we use p with an out of range index, for example:
int *p = &a[8];
blah = p[3];
That's right, when a bounds checked array is converted to a pointer, the bounds does not go with it. Presumably, the function receiving the p has some way to determine the length (such as strlen, or via another parameter) from which the correct array can be reconstructed by doing a slice.
> What if the line was: int a[..] = p[0..12] Do we still get undefined behaviour?
Yes, if the 12 extends past the end of the data p points to.
> Assuming that a indexes from 0 to 9, what happens when we use p with an out of range index, for example: int *p = &a[8]; blah = p[3];
You get undefined behavior.
> My main concern is how to tell other functions that the array has a maximum size
The same way it's done now, by strlen, passing another argument with the length, or the function is able to get the length by other means. When a bounds checked array is converted to a pointer, the bounds are not part of the pointer.
Some follow up questions:
1. If you could redesign the above mechanism, would you do anything differently?
2. In my Own Toy Language[2], I've toyed with the idea making all native arrays fat objects as it seems the best way to ensure that the compiler, at any point, as the ability to bounds check if necessary. All that goes out the window when you want to do FFI to some C function. Any thoughts on mitigating this?
[1] Sorta like telling people when you speak to some celebrity :-)
[2] Everyone designs their own perfect language; I'm no different.
Nope. It was a home run.
> All that goes out the window when you want to do FFI to some C function.
And there you go! What D does, though, is bounds check the conversion of an array to a pointer, and then (in code marked @safe) not allow arithmetic on the pointer.
Additionally, D introduced the `ref` parameter which eliminates nearly all use cases of needing to pass by pointer to a function.
In that aspect it's like when prototypes were added to C. Nothing changed for existing code, but prototypes are so advantageous people would retrofit existing code incrementally when doing routine maintenance.
I can attest that they are.
> it's not applicable in most of the article's use cases
I don't believe that.
Even the Annex K design was misguided, as it expected parameters to still be separate pointer + length arguments, thus hardly changing anything regarding getting them wrong.
int (p)[n] = malloc(sizeof p); (*p)[i] = 1; // run-time bounds check
https://godbolt.org/z/vb8dqx1od
But yes, having a type that included the bound makes sense. But I do not think using array syntax for pointers as in your proposal makes any sense.
Dennis Ritchie got it right: https://www.bell-labs.com/usr/dmr/www/vararray.pdf
Ritchie DM. Variable-size arrays in C. The Journal of C Language Translation 1990;2:81-86.
void foo(int n, int (*p)[n]) {
(*p)[n] = 1;
}
> Dennis Ritchie got it right
"This paper proposes to extend C by allowing pointers to adjustable arrays and arranging that the pointers contain the array bounds necessary to do subscript calculations and compute sizes."
It appears to be phat pointers.
Having said this, I fully agree with you that having a wide pointer that combines length and pointer would be a useful feature. I just think that the syntax proposed by Dennis Ritchie fits naturally into C.
Meanwhile, unlike C99, this construction is not allowed by any version of the C++ standards, any such use would be a non-standard extension, I think this is unfortunate. I only write C, I wonder if any C++ guru out there can answer this question: does modern C++ have a better solution to implement the same thing?
[1] https://devblogs.microsoft.com/oldnewthing/20040826-00/?p=38...
MyStructA a; MyStructB b;
a = malloc((sizeof a) + (sizeof b)); b = (MyStructB *)&a[1];
You need to make sure that the second struct doesn't have stricter alignment requirements than the one preceding it, but using this technique you can stack any number of structures or arrays of structures in one allocation.
(I would generally not recommend this coding style unless you have very specific requirements of memory usage)
MyStructA {
...
MyStructB b[];
};
MyStructA* a = malloc(sizeof(MyStructA) + sizeof(MyStructB));
b = &a->b[0];
I'm no guru, but I know from experience you can do it in C++:
{0}[calvin ~] cat test.cpp
#include <iostream>
#include <memory>
struct foo {
int len;
int v[];
};
int main(void) {
auto p = std::unique_ptr<foo>(reinterpret_cast<struct foo *>(
malloc(sizeof(struct foo) + sizeof(int) * 2)));
p->v[1] = 99;
std::cerr << p->v[1] << std::endl;
return 0;
}
{0}[calvin ~] g++ -Wall -Wextra -std=c++17 test.cpp -o test
{0}[calvin ~] ./test
99
{0}[calvin ~] clang++ -Wall -Wextra -std=c++17 test.cpp -o test
{0}[calvin ~] ./test
99
[0]: https://stackoverflow.com/questions/35423293/flexible-array-...
I assume it’s broken because it’d expect the actual C++ types to be passed in despite the lack of ABI stability, and only the linking / name mangling is affected (possibly calling conventions as well?) but I’m not actually sure.
But in this case, as other said, it may be accepted as an extension. Still not part of C++
https://gist.github.com/cozzyd/efda739301bb7eb3a4a63a145c93e...
For the latency to be significant digits, there must be a lot of repeated calls which only read/write a very small number of elements in the array. Otherwise the accumulation of read/write operations performed when iterating over the data would dwarf the single pointer dereference.
So I'm curious now-- do OS kernels spend most of their time doing lots of calls that dive into such dynamically-allocated data just to extract a single datum or two?
No, the only standard way is to allocate a buffer large enough, and placement new the header and the bulk payload separately. The manual handling of alignment makes this very cumbersome.
Flexible array members would be nice, but I don't like that it is yet an other overload on some array declaration syntax (other meanings of "T x[]": 1) declare an array of unknown size, 2) in a definition, deduce the size). For some reason C likes to overload the array declaration syntax with widely different meanings (looking at you, VLAs).
[1] https://learn.microsoft.com/en-us/cpp/code-quality/annotatin...
As for C folks, I don't have any hopes of them every going down that route.
And interestingly COBOL handled this in a cleaner way. I forget some of the specfics but there was a way to specify to the compiler that one field of a record specified the length of the following array, allowing the same pattern in a type safe way.
> Zero-length array declarations are not allowed, even though some compilers offer them as extensions (typically as a pre-C99 implementation of flexible array members).
However, as they say, gcc (and therefore clang) have an extension that allows it. So does MSVC but it works slightly differently.
It's saying that C99 implemented flexible array members but before then some compilers introduced their own (nonstandard) implementation of flexible array members, using the (not allowed) zero sized array notation.
1. Pre-C99, no flexible array was allowed.
2. Gradually, people started using the "size-1 array at the end of a sturct but write beyond" hack as flexible array.
3. As an attempt to do the hack in a more ordered manner, some compilers, including GCC, started officially supporting the non-standard "size-0" array extension.
4. C99 added flexible array with indefinite length (array[]), while prohibiting both the undefined-behavior "array[1]" and the non-standard extentios "array[0]".
So when people say "size-0" array, it could mean either of these three things, and it does get a bit confusing. But fundamentally the idea was the same, all of the three techniques are used to achieve the same practical effect.
I don't get all the programmers that scandalize if you use GNU extensions, they are fine, and mostly useful, so if you are using GCC to program I don't see why not use -std=gnu11 instead of -std=c11... who cares if the program is not compliant?
Even if you want to be compliant to share code, the C standard is you last problem, the thing is that you probably use a ton of libraries and header files specific to that implementation (such as POSIX or even worse Linux-specific stuff), so your code is 99% not portable anyway without rewriting most of it.
[1] IIRC on OSX[2] gcc actually invokes clang
[2] stopped upgrading before it became macOS
That is the least reassuring sentence I have read on HN in a while!
- Boss!
- ..yes?!
- I was reading a COBOL code base and got a brilliant idea--
- Say no more, you need a vacation. I am sorry, I have been too pushy. Take 3 weeks; just promise me one thing: no COBOL.
> If the size of the space requested is zero, the behavior is implementation-defined: either a null pointer is returned to indicate an error, or the behavior is as if the size were some nonzero value, except that the returned pointer shall not be used to access an object
So it may actually allocate (although the allocation is unusable).
If malloc(0) gets called as first malloc in the program the system break does not need to be moved, as there is always 0 bytes space available... but malloc does like to move sysbreak by a large amount at a time to reduce the need for repeated calls...
I'm guessing malloc(0) does not move sysbreak and simply returns a pointer to the bottom of the heap?
assume the downvote was from someone that malloc is a system call
so what, an array has a size that sizeof can measure. what is returned from malloc is not an array and what sizeof measures is not reflective of the size of the allocation
This works:
void vla_print(int n)
{
int foo[n];
printf("Got %zu bytes right there!\n", sizeof foo);
}
int main(void)
{
vla_print(47);
return 0;
}
Even if you "hide" n from the compiler, i.e. make its value something that is only known at run-time (which is jumping through hoops, pretty sure the above is enough).
Also, it was jarring that the fine article kept referring to sizeof as sizeof(), a notation that C programmers typically use to identify function names. As everyone knows, sizeof is not a function. It's an operator. I really need to print up that t-shirt soon. Or maybe my first tattoo ... Hm.
I'd say it's also not more dangerous (or equally dangerous, depending on your camp) than a pointer from malloc().
Then fix codebases recursively until it's all ok. At ABI boundaries that don't use such types create values of such types corresponding to the given arguments (e.g., you could count the elements of `argv[]` then create a wrapper for the `argv`).
i give up, what does sizeof say? and why would it be sized by bytes?
> ...due to yet more historical situations (e.g. struct sockaddr, which has a fixed-size trailing array that is not supposed to actually be treated as fixed-size), GCC and Clang actually treat all trailing arrays as flexible arrays.
But I don't know, that doesn't seem to match the result I am getting with clang 13.1.6. It does seem to respect the array size declared in the struct, not treat it as a flexible array. I get -Warray-bounds warnings if I try to access anything past o->variable[3]. Maybe I'm misunderstanding what they're saying or my example is screwed up.
Edit: Actually, I guess it does end up treating it like a flexible array -- it produces -Warray-bounds warnings when compiling, but the resulting binary works (and doesn't trigger asan). Not sure I entirely understand it though.
It seems that a memory safe C would be faster, in that you wouldn't have to learn yet another language and runtime to deploy your stuff.
Does anyone know where I can follow these discussions?
I wish this trope would die. It really never was one.
I am not an expert on C nor assembly and would be curious if you could expand on this. The statement makes sense to me because my impression is that most of what happens in C code gets translated fairly straightforwardly to machine code, with the compiler taking care of bridging differences in the instruction sets of targeted architectures. I guess the reason this is simplistic is the inlining and loop unrolling done by an optimizing compiler. Is this what you mean?
[1] I don't know enough about the early history of C to be able to assert that it was never true, but it certainly hasn't been true since at least 1989.
Of all the popular high level languages, C is still (among) the closest to CPU and memory, especially when taking compiler specific language extensions into account which are often simply not available in even higher level languages.
And while modern compilers do all sorts of funky and sometimes surprising code transformations in their optimizer passes, I can still look at a piece of C code and the compiler's output as assembly, and figure out which parts of the C code result in what parts of the assembly code. Some parts may be massively reduced, some parts expanded (e.g. by loop unrolling), some parts may have disappeared completely or shuffled around, but the relationship is still recognizable.
Also, from the POV of a programmer in the 70's or 80's who's used to manually stamping out separate programs for each CPU type in assembly, and then switches to C and only needs to write code once which then runs on different CPUs as if by magic, C would absolutely count as a "portable assembler", and I guess that's the origin of that phrase.
Not saying C is a great standard, but that idea means that using C instead of assembly doesn't generate a big overhead, and it's still much easier to write C than assembly, especially when compiler support is very common.
I'm currently making a language that translates directly to C.
int some_int;
int some_array[] __attribute__((__element_count__(some_int)));
struct
{
int a;
/* ... */
int b[];
} foo;
struct
{
struct foo;
/* ... */
int c;
} bar;
In other words the C standard could make bounds-checking of arrays possible with a good interop story if the standards committee believed it was worth doing. Compilers would have a flag to enable or disable the runtime checks based on safety/perf tradeoffs. Libraries would slowly add the relevant annotations. Eventually most code would have the option of having all array accesses bounds checked.