Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Modernizing C arrays for greater memory safety: a case study in the Linux kernel

people.kernel.org

Post reply on HN
Print view View original

91–100 of 126 posts

Re: Modernizing C arrays for greater memory safety: a case study in the Linux kernel

#91

Post by lelanthran »

WalterBright wrote: post #51

> 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 where bounds-checkable arrays are declared as: int a[..]; `a` consists of two fields, a `length` and a `pointer`. Indexing it mean…

I 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.

Re: Modernizing C arrays for greater memory safety: a case study in the Linux kernel

#92

Post by WalterBright »

lelanthran wrote: post #91
WalterBright wrote: post #51

> 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 where bounds-checkable arrays are declared as: int a[..]; `a` consists of two fields, a `length` and a `pointer`. Indexing it mean…

I 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 sti…

> 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.

Re: Modernizing C arrays for greater memory safety: a case study in the Linux kernel

#93

Post by WalterBright »

eklitzke wrote: post #85
WalterBright wrote: post #51

> 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 where bounds-checkable arrays are declared as: int a[..]; `a` consists of two fields, a `length` and a `pointer`. Indexing it mean…

This 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.

Bounds checked arrays do not have an extra indirection.

Re: Modernizing C arrays for greater memory safety: a case study in the Linux kernel

#94

Post by planede »

WalterBright wrote: post #51

> 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 where bounds-checkable arrays are declared as: int a[..]; `a` consists of two fields, a `length` and a `pointer`. Indexing it mean…

The 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.

Re: Modernizing C arrays for greater memory safety: a case study in the Linux kernel

#95

Post by lelanthran »

WalterBright wrote: post #92
lelanthran wrote: post #91

Earlier quoted context omitted.

I 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 sti…

> 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…

Thank 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.

Re: Modernizing C arrays for greater memory safety: a case study in the Linux kernel

#96

Post by planede »

segfaultbuserr wrote: post #23

For code that is critical to performance, C99's "flexible array at the end of a struct" is an useful tool. It basically allows you to attach a header at the beginning of some dynamically-allocated binary data of infinite length (yes, it can be implemented as a pointer at the end of the struct, but the extra latency of another pointer chasing can reduce performance). Before C99, the "size-1 hack" or "size-0 GCC extens…

> does modern C++ have a better solution to implement the same thing?

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).

Re: Modernizing C arrays for greater memory safety: a case study in the Linux kernel

#97

Post by cassepipe »

WalterBright wrote: post #51

> 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 where bounds-checkable arrays are declared as: int a[..]; `a` consists of two fields, a `length` and a `pointer`. Indexing it mean…

I 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 ?

Re: Modernizing C arrays for greater memory safety: a case study in the Linux kernel

#98

Post by jokoon »

chungy wrote: post #21

> C is not just a fancy assembler any more I wish this trope would die. It really never was one.

Care to explain?

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.

Re: Modernizing C arrays for greater memory safety: a case study in the Linux kernel

#99

Post by dzaima »

WalterBright wrote: post #93
eklitzke wrote: post #85

Earlier quoted context omitted.

This 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.

Bounds checked arrays do not have an extra indirection.

The 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.

Re: Modernizing C arrays for greater memory safety: a case study in the Linux kernel

#100

Post by flohofwoe »

jcranmer wrote: post #64
nequo wrote: post #31

Earlier quoted context omitted.

In what sense was C never a fancy assembler? 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 simpl…

The basic problem with this assumption is that people who follow it tend to get it in their heads that since C is merely "translat[ing] fairly straightforwardly to machine code", they assume they can rely on the semantics of the machine code being the semantics of their C program. That isn't true, and hasn't been for a long time [1]: compilers are only required to uphold the looser semantics of C, and they will happi…

I think compiler writers understand this "C is a portable assembler" entirely differently than regular compiler users, because compiler writes are in the trenches all day long and focus (too much?) on relatively minor code generation and memory model details which are just not relevant for most compiler users in their day to day work.

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.

Post reply on HN