Cake – C23 and Beyond (2023)

by hudon • 2 years ago

172 126 2 years ago

fl0ki• 2 years ago

Nice. If this can be reasonably retrofitted to existing libraries and projects so that the safety properties compose from local to global, then this could actually be a meaningful improvement to the safety of real-world C code.

There would be many more steps required "toward" memory safety, such as eliminating all forms of UB including uninitialized memory, out of bounds pointers, data races, etc. but if this direction is to be pursued it has to start somewhere.

thradams33• 2 years ago

"uninitialized memory" and "null checks" is part of flow analysis. UB and out of bound is not part of it.

vlovich1233• 2 years ago

It’s hard to imagine that ownership composes all that well.

thradams33• 2 years ago

The real experience so far is the cake source itself.

eatonphil2• 2 years ago

Do I need to use the Cake frontend to use the ownership library or is it actually macros (or an extension?) I could use in code compiled with gcc or clang?

thradams33• 2 years ago

The answer you can have the same source code and compile with gcc, but only cake is implementing the checks at this moment. The have the same source code compiling in any compiler a header ownership.h is used to define owner etc as empty macro. This strategy is used on cake source itself, that is checked with cake, but compiled with gcc msvc and clang.

eatonphil2• 2 years ago

Got it, thank you!

ahgamut• 2 years ago

new methods of communication with the compiler have been established.

From what I understand, this appears to a be separate binary from GCC/Clang that does static analysis and outputs C99.

Can this be a GCC plugin? I know we can write plugins that are activated when a specific macro is provided, and the GCC plugin event list allows intercepting the AST at every function declaration/definition. Unless you're rewriting the AST substantially, I feel this could be a compiler plugin. I'd like to know a bit more about what kinds of AST transformations/checks are run as part of Cake.

thradams33• 2 years ago

Cake is a C23 front end, but it can also be used as a static analysis tool. The qualifiers can be empty macros then the same code can be compiled with gcc , clang and the static analysis of ownership can be using cake.

Inside visual studio for instance, we can have on external tools

C:\Program Files (x86)\cake\cake.exe $(ItemPath) -msvc-output -no-output -analyze -nullchecks

The main annotations are qualifiers (similar to const). C23 attributes were considered instead of qualifiers, but qualifiers have better integration with the type system. In any case, macros are used to be declared as empty when necessary.

The qualifiers and the rules can be applied to any compiler. Something harder to specify (but not impossible) is the flow analysis.

Sample of rule for compilers.

int * owner a; int * b; a = b;

we cannot assign view to an owner object. this kind of rule does not require flow analysis.

pizlonator13• 2 years ago

I think that ownership for C is gross. It's hard to convert code to something like this.

But you could get most of the benefit by just isoheaping (strictly allocate different types in different heaps).

DriftRegion• 2 years ago

Say more about isoheaping and how it helps? Is this related to arena allocation? A quick search doesn't find anything on this. Thanks.

pizlonator13• 2 years ago

One heap per type.

Here’s an allocator optimized for that use case.

https://github.com/WebKit/WebKit/blob/main/Source/bmalloc/li...

saagarjha3• 2 years ago

This doesn’t help for a lot of things, including some of the examples described in the article. For example trying to segregate file descriptors (or similar resource handles) to an isolated heap would be mostly worthless because a UAF through a “stale reference” would let you mess with a completely different file. In general the problem of figuring out which objects are safe to confuse with each other is very difficult. There are a handful of “obvious” types (collections, ports, etc.) that it’s clear cannot be allocated together because they hold capabilities but doing this in general is not tractable.

pizlonator13• 2 years ago

Sure ownership protects against more things. But some coding patterns are impossible under it.

thradams33• 2 years ago

Converting code can be challenging. The cake code has been successfully converted. null-checks are not ready, and something similar already happened to c#.

The experience is similar to changing a header file to use a const argument where previously the argument was non-const. This change will propagate everywhere.

I also think a similar experience is converting JavaScript to typescript. The type system will complain before it stabilizes.

pizlonator13• 2 years ago

Have you made OpenSSL, or something big like that, completely memory safe this way?

As in, running nothing but memory-safety-ified C code down to the syscall boundary?

matheusmoreira• 2 years ago

But you could get most of the benefit by just isoheaping (strictly allocate different types in different heaps).

Can you elaborate on this? I've been reading up on memory allocation algorithms and most of them seem to favor segregation of blocks by element size instead. Are there additional benefits to coming up with a complex typing scheme for a custom memory allocation interface?

pizlonator13• 2 years ago

No benefits other than safety.

pjc502• 2 years ago

I think that ownership for C is gross

CVEs are gross. How do you prove your code is free from use-after-free and so on?

pizlonator13• 2 years ago

Don't have to if I use isoheaps.

taminka• 2 years ago

lowkey smart pointers are often just used to deflect the responsibility of thinking about memory layouts

https://floooh.github.io/2018/06/17/handles-vs-pointers.html

and most issues can be caught by using a static analyser of a memory leak checker (getting ppl to consistently use them is another issue, but still)

thradams33• 2 years ago

Static analysis has a significant advantage over runtime checks for memory leaks, especially in code that is almost never executed, because bugs can remain hidden until they appear in production. The code where I found the bug last year was executed occasionally, and to create a unit test, it was necessary to integrate with another server. So it wasn't easy to check at runtime.

On the other hand static analysis will catch the error at first compilation even on those almost never executed code.

Animats2• 2 years ago

C safety addons like this (there have been many) is that they don't prevent extracting raw pointers from controlled pointers. Optional memory safety isn't.

If this can be reasonably retrofitted to existing libraries and projects

That's the problem.

If you want to fool around in this space, consider revisiting C++ to Rust conversion. There's something called Corrode, which compiles C to a weird subset of Rust full of objects that implement C raw pointers. The output is verbose and unmaintainable. What's needed is something that can figure out how big things are and who owns what, possibly guessing, and generate appropriate ideomatic Rust. Now that LLMs are sort of working, that might be possible.

Can you ask Github Co-pilot to look at C code and answer the question "What is the length of the array 'buf' passed to this function"? That tells you how to express the array in a language where arrays have enforced lengths, whicn includes both C++ and Rust. With hints like that, ideomatic translation becomes possible. Bad guesses will result in programs that subscript out of range, which is caught at run time. But guesses should be correct most of the time, because C programmers tend to use the same idioms for arrays with lengths. Forms such as "int read(int fd, char* buf, size_t buf_l)" show up often.

Using LLMs to help with tightening up existing code might work.

thradams33• 2 years ago

the cake implementation cannot be mapped to rust. I am not rust specialist but one concept for instance is that a owner pointer owns two resources at same time, the memory and object. In rust it is one concept.

Owner pointers take on the responsibility of owning the pointed object and its associated memory, treating them as distinct entities. A common practice is to implement a delete function to release both resources, as illustrated in Listing 7:

Listing 7 - Implementing the delete function

    #include <ownership.h>

    #include <stdlib.h>


    struct X { 
      char *owner text; 
   };

    void x_delete(struct X *owner p) {
      if (p) {
        /*releasing the object*/ 
        free(p->text);
    
       /*releasing the memory*/ 
       free(p); 
     }
   }

   int main() {
      struct X \* owner pX = calloc( 1, sizeof \* pX);
      if (pX) {
       /*...*/;
       x_delete( pX); 
      }  
   }

pitaj• 2 years ago

I don't see why that couldn't be represented like this in Rust:

    struct X {
        text: Option<Box<str>>,
    }
    fn main() {
        let pX = Box::new(X { text: None });
        // automatically dropped (freed) at end of scope
    }

thradams33• 2 years ago

Can you ask Github Co-pilot to look at C code and answer the question "What is >the length of the array 'buf' passed to this function"? That tells you how to >express the array in a language where arrays have enforced lengths, whicn >includes both C++ and Rust

this is the way you tell C what is the size of array.

    void f(int n, int a[n]) {
    }

a_t482• 2 years ago

Do you have source on this syntax? Does the `[n]` actually do anything here? Fooling around in godbolt, `void f(int n, int a[n]) {` is the same as `void f(int n, int a[]) {` and doesn't appear to change assembly or generate any warnings/errors with improper usage.

Animats2• 2 years ago

You can write that in C, but it doesn't really do anything. It's equivalent to

    void f(int n, int a[]) {
    }

Why? So that you can write

    void f(int n, int m, int a[n][m]) {
    }

which declares a 2-dimensional array parameter. In that case, the "m" is used to compute the position in the array for a 2D array. The "m" doesn't do anything. This is equivalent to writing

   void f(int n, int m, int a[][m]) {
   }

This is C's minimal multidimensional array support, known by few and used by fewer.

Over a decade ago, I proposed that sizes in parameters should be checkable and readable I worked out how to make it work.[1] But I didn't have time for the politics of C standards.

[1] http://animats.com/papers/languages/safearraysforc43.pdf

JonChesterfield6• 2 years ago

you're missing the word "static" to have that work as intended. Option (2) at https://en.cppreference.com/w/c/language/array

Parameters like `const double b[static restrict 10]` for at least 10 long and doesn't alias other parameters.

Syntactically this is pretty weird.

quatrefoil• 2 years ago

Optional memory safety isn't.

Optional memory safety is, when you can opt an entire project into a "strict" mode, and this becomes trivially verifiable by others. I imagine that's the goal here.

Optional security is a problem only when you need to remember a million different rules and gotchas, because you will inevitably miss a spot. But if it's a global toggle, it's pretty good. "Use '-fmemsafe' for C/C++" is as tractable as "don't use 'unsafe' in Rust".

Yeah, as you note, library compatibility is an issue. But it's an even bigger issue when bootstrapping a new, safe language: you gotta implement the libraries from scratch, and you never really get to full parity with C/C++. Getting it done for the top 10 most-used libraries would make a spectacular difference in itself.

I should note that I'm not a huge believer in "saving" C/C++ as the memory-safe language of the future - I think there are lingering cultural problems around the standards that we had no luck overcoming for decades - but I also don't think the duo is going away any time soon, so might as well expend some effort on making it a safer tool.

nanolith• 2 years ago

These are tools. How well they work largely depends on the discipline and processes followed by the development team using them. If the concern is that raw pointers can be extracted from controlled pointers, then the development team needs to check for this. No tool is perfect, but tools like these can be used effectively to reduce attack surfaces and improve safety.

Even languages like Rust make memory safety optional. One can drop into an unsafe block and perform all sorts of abominable things. Such escape hatches are necessary to color outside of the lines when one must do system software development or optimize software beyond what the compiler can do on its own. At some point, the developer must be trusted to learn the tool or to use discretion when considering something like unsafe. In both cases, a development team can peer review these choices.

What makes me interested in tools like Cake and similar tools is that these bring us closer to being able to use proof assistants to build up reasoning about the times when we must color outside of the lines. Whether C, C++, or Rust, being able to import code into a proof assistant or extract efficient code from a proof assistant can further assist us when our use cases exceed what is possible with the safety features in our language or tooling.

naitgacem• 2 years ago

    Bad guesses will result in programs that subscript out of range, which is caught at run time.

That is sadly not always the case.

woodruffw2• 2 years ago

I might be missing something, but this seems to require ownership annotations on all functions, e.g. a compatible and correct prototype for `fclose` to correctly note that the owned `FILE *` is moved into the call.

If that's correct, then this is somewhat practically limited: either pre-existing codebases will need to be retrofitted with an essentially bespoke set of macros, or the compiler will need to be "fail open" by default. The tradeoffs between these two are hard (substantial developer pain versus being ineffective against the bulk of a compiled program's API surface).

(Also, this design appears to be for temporal safety only, not spatial safety. But again I might have missed something.)

thradams33• 2 years ago

currently cake uses existing msvc and gcc headers. These headers does not have any owner qualifiers.

The temporary solution, is the re-declare the malloc etc when compiling with cake and not complain withe the function signature difference only by owner qualifiers.

if this ownership were standard then gcc and mscv headers would have the qualifiers there enabled or not , but they would be there.

JonChesterfield6• 2 years ago

Compilers cheat when working with known libraries - they don't need annotations on known functions, much like they don't need the specific implementation of them to know the semantics. This occasionally goes wrong when the compiler assumes any function with a given name must be that function from libc, e.g. the programmer writes a function called `sin`, there's a risk of it being mistaken for the libm function.

woodruffw2• 2 years ago

Right. It's less known libraries I'm worried about (libc can easily be layered over, as you've said) and more unknown ones.

In particular: there are a lot of ~universally used libraries with ludicrously complex C APIs that undergo significant own/borrow semantic changes between releases. Things like OpenSSL. These libraries will need to carry these annotations upstream for correctness and up-datedness reasons.

dataflow• 2 years ago

This is awesome. Could they reconcile this with [[gsl::Owner]] or gsl::owner<T> somehow so we don't end up with multiple syntaxes in C++?

https://reviews.llvm.org/D64448

https://github.com/microsoft/GSL/blob/main/docs/headers.md#g...

thradams33• 2 years ago

I think gsl::Owner is related with RAII.

The difference with cake ownership and RAII , is that with C++ RAII, the destructor is unconditionally called at end of scope. Then flow analysis is not required in RAII.

Cake requires flow analysis because "destructor" is not unconditionally called.

When the compiler can see that the owner is not owning a object (because the pointer is null for instance) then the "destructor" is not necessary.

To understand the difference.

With flow analysis (how it works today)

    int main() 
    {
      FILE *owner f = fopen("file.txt", "r"); 
      if (f)
        fclose(f);
    }

Without flow analysis (or with a very simple one, where the destroy must be the last statement)

    void fclose2(FILE * owner p) {
       if (p) fclose(p);
    }

    int main() 
    {
      FILE *owner f = fopen("file.txt", "r"); 
      if (f){
      }
      fclose2(f);
    }

thradams33• 2 years ago

the other difference in RAII destructor cannot be turned off. In cake the same object can be a "view"

    struct X x = {0};
    //...
    view struct X x2 = x;
    destroy(&x);
    //x2 does not need destructor

ActorNightly9• 2 years ago

This is overly complicated, there is no need to bring Rust semantics to C to ensure memory safety.

A good mempool implementation is all you need (i.e keeps track of every request, and zeros out the memory on release)

Voultapher6• 2 years ago

Compiler optimizations and other forms of UB like integer overflow would like a word with you. If it were that simple, someone would have had success at scale by now https://alexgaynor.net/2020/may/27/science-on-memory-unsafet....

ActorNightly9• 2 years ago

If it were that simple, someone would have had success at scale by now

A lot of code in that article doesn't use mempools, and furthermore, just because a double free exists doesn't mean that its always exploitable. And if its exploitable, it doesn't mean that you can gain a shell or even exfil data, sometimes it means you can just crash the program.

Fundamentally, if you write a wrapper around memory management that keeps track of allocated resources, much in the same way how rust includes some runtime code during compilation for memory safety, you gain the same functionality.

thradams33• 2 years ago

mempool does not solve double free, use after free (at least at compile time) or fopen sample. But mempool and ownership can be complementary.

ActorNightly9• 2 years ago

If you are talking about a very naive version of mempool, then you are correct, but thats why I said a good implementation.

The whole point of a good mempool is that you malloc once, and only call free when you exit the program. The data structures for memory allocation will never get corrupted. And the memory pool will never release chunk twice cause it keeps tracks of allocated chunks.

User after free is mitigated in the same way. When you allocate, you get a struct back that contains a pointer to the data. When you release, that pointer is zeroed out.

irogers• 2 years ago

Agreed this is awesome, obviously sanitizers fill some of this gap currently but they aren't great with things like reference counting that RAII makes a doddle. Fwiw, here is an implementation of a runtime RAII style checking on top of leak sanitizer: https://perf.wiki.kernel.org/index.php/Reference_Count_Check... There's an interesting overlap with the cleanup attribute that is now appearing in the Linux kernel (by way of systemd): https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...

thradams33• 2 years ago

Cake implements defer as an extension, where ownership and defer work together. The flow analysis must be prepared for defer.

    int * owner p = calloc(1, sizeof(int));
    defer free(p);

However, with ownership checks, the code is already safe. This may also change the programmer's style, as generally, C code avoids returns in the middle of the code.

In this scenario, defer makes the code more declarative and saves some lines of code. It can be particularly useful when the compiler supports defer but not ownership.

One difference between defer and ownership checks, in terms of safety, is that the compiler will not prompt you to create the defer. But, with ownership checks, the compiler will require an owner object to hold the result of malloc, for instance. It cannot be ignored.

The same happens with C++ RAII. If you forgot to free something at our destructor or forgot to create the destructor, the compiler will not complain.

In cake ownership this cannot be ignored.

    struct X {
      FILE * owner file;
    };

    int main(){
       struct X x = {};
       //....
       
    } //error x.file not freed

yau8edq12i4• 2 years ago

I've been dabbling in embedded programming. Everything is written in C. I just don't understand why. C++ solves pretty much all problems if you want it too (RAII, smart pointers, move semantics) and the frameworks writers wouldn't need to implement their bespoke OOP system on top of opaque pointers and callbacks.

Maybe it was bad luck on my part, and other embedded frameworks are better; but I got into both ESP32 and STM32, both frameworks are the worst spaghetti code I have ever seen. You need to jump through at least one, often two layers of indirection to understand what a particular function call will do. Here's an example of what I mean:

    // peripheral_conf.h
    #define USE_FOOBAR_PERIPHERAL 1
    // obj_t.h
    #define USE_OBJ_PARAM2

    // In the library header
    #ifdef USE_FOOBAR_PERIPHERAL
    #define DoSomethingCallback FoobarCallback
    #endif

   // foobar.h
   status_t FoobarCallback(int32_t data, int32_t param);

    // obj_t.c
    status_t Init(Obj_t* obj) {
        obj->param1 = obj->init.initparam & 0xFF;
        #ifdef USE_OBJ_PARAM2
        obj->param2 = (obj->init.initparam >> 16) & 0xFF;
        #endif
        obj->callback = DoSomethingCallback;
        return OK;
    }
    
    status_t DoSomething(Obj_t *obj, int32_t data) {
        #ifdef USE_OBJ_PARAM2
        return obj->callback(data, obj->param2);
        #else
        return obj->callback(data, obj->param1);
        #endif
    }

    // main.c
    Obj obj = {0};
    obj.init.initparam = 0x12345678;
    Init(obj);
    DoSomething(obj, 0x42);

And that's an easy example. Macros everywhere, you need to grok what's happening in four different files to understand what the hell a single function call will actually do. Sure, the code is super efficient, because once it's compiled all the extraneous information is pre-processed away if you don't use such and such peripheral or configuration option. But all this could be replaced by an abstract class, perhaps some templates... And if you disable stuff you may not need (RTTI, exceptions) then you'd get just as efficient compiled code. It would be much easier to understand what going on, and you wouldn't be able call DoSomething on uninitialized data... Because you'd have to call the constructor first to even have access to the method.

Anyway, thank god for debuggers, step-by-step execution, and IDEs.

outsomnia• 2 years ago

But all this could be replaced by an abstract class, perhaps some templates... And if you disable stuff you may not need (RTTI, exceptions) then you'd get just as efficient compiled code.

Isn't it just that your personal in-head GPT has been trained on C++ and wants to see it everywhere? It's not so easy to make very small embedded implementations and there's a reason after 25+ years C++ has not made inroads there.

yau8edq12i4• 2 years ago

I'd appreciate if you made your point in a less condescending and dismissing manner. Anyway.

No, C++ is not even my programming language of predilection. Not sure why you would make assumptions about my background while knowing nothing about me. But I can recognize OOP patterns when I see them. There's even a book about that https://www.cs.rit.edu/~ats/books/ooc.pdf C-styled OOP is not a new concept. C++ just does it better.

The reason C++ has "not made inroads" may just be inertia, you know. And look at Arduino - if C++ code can run on an 8bit ATmega MCU, it can run anywhere. The whole language is designed around "pay for what you use and nothing else".

JonChesterfield6• 2 years ago

C doesn't need to look like this. Some of it does, because it comes from the days where function inlining and dead code elimination were aspirational, but your C compiler is probably derived from clang or gcc now and totally capable of folding away branches on constant data.

An abstract class is a struct with function pointers in it. Mark the fields const and the instance const and it'll be devirtualised and optimised away. If you miss overloading, `static inline __attribute__((overloadable))` wrappers in a header will bring it back.

Code generators can be better for debugging than built in templates. At the source level they look the same, but if it's behaving weirdly, you can look at the generated C instead of the templated layer.

C code can look rather like modern C++. If you're up for feeding it to a custom preprocessor to implement templates, or especially if you've gone as hardcore as the compiler front end under discussion here, C++ starts to look a lot like a syntactic obfuscation over C.

[it's not quite syntax over C, the languages play divergent games with semantics as well, but picking a different set of syntax abstractions over C to the C++ one is an interesting way to go]

yau8edq12i4• 2 years ago

I can't say I understand the overall point you're trying to make.

Rucadi• 2 years ago

This project is amazing because it also seems that has #embed included, IIRC no other compiler has it yet.

Just for that #embed directive I would already use cake for the moment (although it seems like it is only doing the file->array conversion)

andai• 2 years ago

Odin has this! (I thought Zig as well, but I can't find that.)

flohofwoe• 2 years ago

In Zig it's called @embedFile (https://ziglang.org/documentation/master/#embedFile)

odiroot• 2 years ago

V also has this https://github.com/vlang/v/blob/master/doc/docs.md#embed_fil...

thradams33• 2 years ago

(by the way, embed is not working on web version because of include directory bug - it is an open issue and regression)

JonChesterfield6• 2 years ago

I think this is a really interesting direction.

That it can translate C23 to C89 means it has most of the work in place to translate C23 to C23, or C99 to C99 etc. If that is done in a (mostly) reversible fashion - successfully re-encode back to the original, where you `preprocess -> parse -> unparse -> re-preprocess` which is a nuisance but possible, then it opens the door to much more aggressive type systems.

In particular, the input can be C with the ownership annotations, and if they're valid, the output can be C with those annotations dropped to be fed into some other compiler. Or whatever other invariant systems the compiler dev is interested in.

Or the input could be C extended with namespace {} syntax, C++ style lambdas, contract checking - whatever you wish really, and the output can be the extensions desugared into C. Templates (possibly the D style ones) can be implemented as instantiating normal functions from said template.

That the output is C means this is usable in all the pipelines that already work with C.

Good stuff, thanks for posting.

thradams33• 2 years ago

The idea is to keep cake aligned with C, not a language fork. But Cake itself could have a fork to Cake++. :D

JonChesterfield6• 2 years ago

A 'C' -> C compiler which preserves most source code unchanged (i.e. would be the identity transform on some input) and which implements something like constexpr on functions (by running the interpreter during the transform) could be argued to be a forward looking C implementation. Specifically C23 has constexpr, but in an extremely limited form, and aspires to extend that to be more useful later.

Equally one which replaces 'auto' with the name of the type (and similar desugaring games) is still a C to C compiler, just running as a C23 to C99 or whatever. Resolve the branch in _Generic before emitting code as part of downgrading C11.

The lifetime annotations are an interesting one because they're a different language which, if it typechecks, can be losslessly converted into C (by dropping the annotations on the way out).

I'm not sure where in that design space the current implementation lies. In particular folding preprocessed code back into code that has the #defines and #includes in is a massive pain and only really valuable if you want to lean into the round trip capability.

Cake – C23 and Beyond (2023)

Related Stories