26 ms·
Modernizing C arrays for greater memory safety: a case study in the Linux kernel
- ashvardanian 4y agoCall me crazy, but zero length arrays are a great abstraction, when you working with implicit data-structures. Not safe, but elegant and performant. Many codebases could be 2x faster if their designers embraced that concept.
- zabzonk 4y agoboth c and c++ have the concept of zero-length arrays, if you malloc them - int * a = malloc(0); is ok
- monocasa 4y agoI think the parent is talking about the c pattern of having the last member of a struct be a zero length array, which is actually a dynamically sized array that the struct is only the header to (ostensibly with another field of the struct specifying the length of the array). It's fallen a bit out of favor, but it is a handy way to commingle the header and array with one allocation/pointer. 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.
- ChrisSD 4y agoAccording to the C spec, zero length arrays are explicitly illegal. > 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.
- fsckboy 4y agoyou should be specific about which C spec you are referring to, you talk about "the C spec" and then you mention the "pre-C99 implementation". Maybe you mean they've always been illegal in every version, but it would be more clear.
- deleted 4y ago[deleted]
- ChrisSD 4y agoThe bit after `>` is a quote, not my words. See https://en.cppreference.com/w/c/language/array https://en.cppreference.com/w/c/language/array for the source 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.
- segfaultbuserr 4y agoThe sequence of event was basically: 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.
- alerighi 4y agoIn reality, who cares of what the C spec says? Unless you have to port code on different compilers (which is very unlikely, unless you are building a library meant to be shared with different projects) you only care about the fact that the code works correctly with the compiler you choose to use. 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.
- ufo 4y agoAccording to the article, it's better to use the new flexible array syntax (int arr[]) instead of the old zero-length syntax (int arr[0]), because that allows the compiler emit better warning messages.
- ddtaylor 4y ago> And interestingly COBOL handled this in a cleaner way That is the least reassuring sentence I have read on HN in a while!
- ykonstant 4y agoROFL I can use that. - 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.
- le-mark 4y agoIn cobol it wasn’t dynamic, or infinite. The syntax of the array/table declaration includes a maximum and it would allocate the entire array statically up to the max.
- ChrisSD 4y agoKind of: > 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).
- tmtvl 4y agoHang on, let me think this through... 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?
- monocasa 4y agoImplementation defined. I've heard of returning null (under the case that your free() implementation allows nulls to be passed in) or returning a pointer to a zero length object on the heap like you're suggesting. Really just about the only requirement is that the pointer can subsequently be given to free() since dereferencing the pointer is UB.
- int_19h 4y agofree(NULL) is required to be a no-op by the ISO C standard.
- monocasa 4y agoOh, good call. I had that backwards in my memory. The issue is when you give out non NULL pointers to zero sized objects, you have to make sure to give out unique pointer bit patterns at least versus nonzero sized objects so that the matching calls to free don't stomp on eachother.
- zabzonk 4y agomalloc is a user level library function - c/c++ implementers can do what they like with it assume the downvote was from someone that malloc is a system call
- loeg 4y agoI downvoted for the assumption that sbrk is involved in any way. It's an implementation detail of (some) historical malloc implementations, not some inherent aspect of all implementations. The entire thought experiment is faulty.
- russdill 4y agoThen you have two allocations instead of one and related data is now likely to be farther away, possibly even in a different page.
- kevin_thibedeau 4y agomalloc() doesn't allocate arrays. It allocates blocks of memory. Hence sizeof doesn't work the same for malloc() objects as it does on arrays.
- int_19h 4y agosizeof doesn't work the same for malloc() because the type of the returned value is a pointer, and the behavior of sizeof is dependent solely on the static type. For comparison, calloc() is specifically defined as "allocates space for an array of ... objects" in the Standard, but since return type is still void*, the caveat with sizeof still applies.
- loeg 4y agoWell, sure, but the reason for that is that C's type system simply cannot represent functions returning arrays with known size. This is a weakness of the type system. Arrays degrade to a pointer type, lacking array length, as soon as you pass them between functions.
- kevin_thibedeau 4y agocalloc() doesn't allocate an array either. It's purpose is to allocate blocks of memory larger than SIZE_MAX. Mostly irrelevant now but was an issue on 16-bit systems.
- int_19h 4y agoI literally quoted the Standard (C17 7.22.3.2) in my earlier comment, and it very specifically says that calloc allocates an array. This language isn't from a new standard, either - it goes all the way back to ISO C90.
- fsckboy 4y ago> sizeof is dependent solely on the static type 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
- yyyk 4y agomalloc(0) return value is undefined by POSIX and can return NULL (IIRC it did on NetBSD).
- segfaultbuserr 4y ago> Not safe, but elegant and performant. I'd say it's also not more dangerous (or equally dangerous, depending on your camp) than a pointer from malloc().
- zabzonk 4y ago> Is it actually a 4 element array, or is it sized by the bytes member? i give up, what does sizeof say? and why would it be sized by bytes?
- ntrz 4y agoThe previous paragraph says > ...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.
- tmtvl 4y agoTL;DR is the introduction of C99 VLAs, not Pascal-style arrays, though a potential attribute could be added so we could do int some_int; int some_array[] __attribute__((__element_count__(some_int))); to store the size of some_array in some_int.
- kevin_thibedeau 4y agoThis has nothing to do with VLAs. The article covers FAMs at the end of structs.
- tmtvl 4y agoI must have misunderstood, thank you for the clarification. I thought that having no size specifier in the array declaration turned it into a VLA, which could have repercussions when embedding structs, e.g.: struct { int a; /* ... */ int b[]; } foo; struct { struct foo; /* ... */ int c; } bar; I would expect to have issues when trying to access the other members of struct bar like c.
- deleted 4y ago[deleted]
- loeg 4y agoSibling already pointed out this article is not talking about VLAs, but I do like your flexible-array attribute extension proposal.
- ufo 4y agoDoes anyone know what is the status of their refactoring effort to update all the flexible array declarations in the kernel? How far along are they?
- hgs3 4y agoGood article. If you're compiling C with MSVC then you can use SAL annotations [1] which serve the same purpose. [1] https://learn.microsoft.com/en-us/cpp/code-quality/annotating-structs-and-classes?view=msvc-170#example https://learn.microsoft.com/en-us/cpp/code-quality/annotatin...
- funny_falcon 4y agoWow, such a great annotation language. Wish it were in GCC as well.
- leeter 4y agoI keep hoping that the C and C++ committees will get together and standardize some of that in the form of C23/C++11 style attributes. But that is sadly likely a naïve hope.
- pjmlp 4y agoMicrosoft hopes to be able to map SAL into C++ contracts if they ever be part of the standard, as that was their initial goal when they started implementing lifetimes support in VC++. As for C folks, I don't have any hopes of them every going down that route.
- chungy 4y ago> C is not just a fancy assembler any more I wish this trope would die. It really never was one.
- nequo 4y agoIn 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 simplistic is the inlining and loop unrolling done by an optimizing compiler. Is this what you mean?
- astrange 4y agoC is a language with a specification which defines it in terms of a virtual machine, not translation to machine code. The memory model is also totally different and it has lots of undefined behavior.
- jcranmer 4y agoThe 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 happily apply optimizations that deviate from the semantics of a purported naive translation to machine code. The usual example brought out to explore this difference is signed integer overflow, which has nothing to do with inlining or loop unrolling. [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.
- flohofwoe 4y agoI 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.
- segfaultbuserr 4y agoFor 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 extension" for this purpose was already widespread in both the Linux kernel and Windows [1], but with the disadvantage of triggering memory-safety tools, as the author pointed out. 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=38043 https://devblogs.microsoft.com/oldnewthing/20040826-00/?p=38...
- quelsolaar 4y agoYou can do it without trailing arrays, by stacking the structures after one and other: 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)
- loeg 4y agoThis is pretty similar to: MyStructA { ... MyStructB b[]; }; MyStructA* a = malloc(sizeof(MyStructA) + sizeof(MyStructB)); b = &a->b[0]; (Except, of course, that the syntax for locating 'b' is nicer this way, because you don't have to explicitly address the memory after 'a' and cast it to 'MyStructB'.)
- jcalvinowens 4y ago> Does modern C++ have a better solution to implement the same thing? 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 EDIT: Remove unnecessary extern block, as pointed out by wahern in the replies.
- 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.
- KingLancelot 4y ago[dead]
- cryptonector 4y agoIMO the right approach is to start with counted array struct wrapper types like `struct array_of_xyz { unsigned count; xyz a[1]; };` and use them to hold and pass by reference. When the array sizes are fixed, then use `struct array5_of_xyz { xyz a[5]; };` and pass by reference or by value as needed. Add to this a decoration to indicate that the `count` field is a count of the number of elements in the array and now the compiler can do bounds checking. 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`).
- Gordonjcp 4y ago[flagged]
- tmsln 4y ago> A simpler approach is the addition of struct member attributes, and is under discussion and early development by both the GCC and Clang developer communities. Does anyone know where I can follow these discussions?
- manv1 4y agoEveryone says a memory-safe C would be slower, but has anyone actually tested that recently? 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.