4 ms·
> int flex[] __attribute__((__element_count__(items))); While what the article describes is clever, it is needlessly complex, and filled with various compiler
by WalterBright 4y ago
> int flex[] __attribute__((__element_count__(items)));
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 https://www.digitalmars.com/articles/C-biggest-mistake.html
where bounds-checkable arrays are declared as:
int a[..];
`a` consists of two fields, a `length` and a `pointer`. Indexing it means the compiler can (optionally) insert a bounds check it.
int s[..] = "string";
s[10] = 'x'; // fatal runtime error
We can turn a pointer into a bounds checked array by "slicing" it:
int *p = (int*) malloc(10);
int a[..] = p[0 .. 10];
A bounds checked array can be turned into a pointer:
int *p = &a[3]; // point to 3rd element of a[..]
That's all there is to it. No pages and pages of compiler switches and extensions.
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.
- ndesaulniers 4y agoThat's nice, but attributes let us easily retrofit existing C code such as the Linux kernel in a way that supports multiple compilers and compiler versions. Just extensions, not compiler switches. And they don't muck with the ABI which is a requirement for stable kernel driver interfaces. Also what you're proposing...would be an extension!
- WalterBright 4y agoReading the article, it doesn't look easy at all. 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.
- ezy 4y agoMost of the article is devoted to complications related to handling arrays that are inline at the tail of existing structs that usually are layout and size sensitive. Hence the related two restrictions that the count variable keep the same name and location in the struct, and there is no explicit array head pointer (just the implicit location at which the array starts at the end of the struct). 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.
- ndesaulniers 4y agoTake a look at how we use __has_attribute in the kernel. https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/compiler_attributes.h 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.
- WalterBright 4y ago> 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] which is used in D to interface with C code. Note that the syntax still works if `a` is a pointer! 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.
- downvotetruth 4y agoStarting with "That's nice" is extremely flippant and is an immediate turn off to any subsequent statement. A stronger opening to discredit the [..] proposal would be to take the closing quote "We've been doing that with D for over 20 years" and point out that storing the length of an array of a certain type is a specialization to arrays of dependent typing that has been around since Howard and de Bruijn extended lambda calculus to match predicate logic by creating types for dependent functions and pairs. Each axis of the lambda cube is another source of nondeterminism that has to be reasoned with and languages that explicitly exclude said functionality for simplicity can point to as justification for such restrictions.
- ndesaulniers 4y agoThat's nice, but this is a Wendy's.
- WalterBright 4y agoI didn't say D invented it, so no need to discredit it. I said D has been using it for 20 years and proves it works famously with C style pointers and arrays.
- deleted 4y ago[deleted]
- downvotetruth 4y agoAnd no claim was made about what D invented. Continuous use does not prevent door latch bushings from disintegrating; How long some thing has been used for is not proof that the replacement will work.
- ImprobableTruth 4y agoFat pointers are a purely value level construct. STLC alone covers that. Non-determinism isn't really related to the lambda cube, even CoC is deterministic.
- downvotetruth 4y ago
- eklitzke 4y agoThis isn't the same thing though. A flex array includes the data inline in the struct so allocating a struct with a flex array at the end requires just one call to malloc and avoids a pointer indirection when indexing into the array.
- WalterBright 4y agoBounds checked arrays do not have an extra indirection.
- dzaima 4y agoThe question here is about what happens when such an array is part of a heap-allocated struct where there's already a layer of indirection. As far as I can tell, the [..] proposal would effectively be equivalent to pointer & length fields as far as data layout goes, but there are no pointers stored for a flexible array member, as getting the address of an element is just adding an offset to the struct's address, hence it has less indirection.
- lelanthran 4y agoI like how this is going, but I'm missing a few things here: > 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] Do we still get undefined behaviour? > 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]; My main concern is how to tell other functions that the array has a maximum size, and how to determine (inside a function) what the maximum length of its parameters is.
- WalterBright 4y ago> 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). 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.
- lelanthran 4y agoThank you. I'm always pleased when I get a reply from WalterBright[1]. 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.
- planede 4y agoThe problem is that this would have one specific ABI, which probably wouldn't match many existing structs with a flexible array member at the end. Could potentially be used for new code (while requiring every user to upgrade the standard they compile with), but has the risk of not usable for modernizing old code.
- WalterBright 4y agoYou're right that bounds checked arrays do nothing at all for existing code. But they can be added incrementally to an existing code base, as a normal part of working on the code. 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.
- planede 4y agoI presume prototypes could be added to transform much of existing code without compatibility problems (ABI nor API), which is a clear advantage compared to checked arrays. Checked arrays might worth it regardless, but it's not applicable in most of the article's use cases.
- WalterBright 4y ago> Checked arrays might worth it regardless I can attest that they are. > it's not applicable in most of the article's use cases I don't believe that.
- cassepipe 4y agoI had always assumed it was because of backwards compat that the proposal was never accepted but since it turns out that is not the issue, do you have any idea why the proposal was never accepted ?
- pjmlp 4y agoObjective-C and C++ never had any issues having additionaly types for arrays and strings, C could do the same, but WG14 has clearly decided they don't want to do that.
- cassepipe 4y agoYes, so why WG14 or whoever in charge has not accepted that one simple addition responsible for so many errors ? It's not like it would affect performance. For strings, it would even make it better, simply moving the lenght around with the compiler's help.
- pjmlp 4y agoMost likely as they have proven during the last 40 years, security is not in their agenda. 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.
- WalterBright 4y agoIt turns out that bounds checked arrays are ideal for strings. One no longer has to run strlen, which is inherently slow and cache-unfriendly. One can also slice a substring without needing to allocate and copy.
- crabbone 4y agoYou aren't going to get a lot of love from C programmers by casting malloc() result...
- uecker 4y agoWe have bounds-checkable arrays already since C99: int (p)[n] = malloc(sizeof p); (*p)[i] = 1; // run-time bounds check https://godbolt.org/z/vb8dqx1od 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 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.
- WalterBright 4y ago> We have bounds-checkable arrays already since C99 void foo(int n, int (*p)[n]) { (*p)[n] = 1; } which has failed to catch on, because it still stores the pointer and the length as two separately handled objects. > 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.
- uecker 4y agoIt is unclear why it has failed to catch on. One reason probably was that Microsoft decided at one point that it will not support C99 because everything should program in C++ which put a damper on the adoption of newer C features. The other reason is that compilers did not actually supported bounds checking here (I added it in GCC for UBSan in 2015) and it is still possible to lose the bound at function calls (I have patch to GCC I hope I can submit for the next version). So for a long time most people thought that VM-types were useful only for numerics. 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.