Hacker News new | comments | show | ask | jobs | submit login
Baby Steps: Slowly Porting Musl to Rust (adamperry.me)
287 points by pygy_ 464 days ago | hide | past | web | 176 comments | favorite



I'm disappointed by the idea that something is semantic nonsense, but it's okay to do it anyway. The right line of code isn't "return usize::MAX", but "abort()". (I'd also accept "__builtin_unreachable()".)

In general, if a program enters an impossible state, you need to stop running the program, not do something you know is wrong just so the program keeps working a while longer. That's why strcpy_s is much better than strlcpy.

It's also really not fair to compare the legibility of Rust to the legibility of musl: whatever its other merits, musl is written in that old-school C style that makes one imagine that programs run faster when variable names are shorter and braces are omitted.


This is a hobby project for my own edification, and maybe maybe to eventually show Rust's suitability for this kind of work. While I appreciate that the semantics of returning usize::MAX aren't correct, I'm also not an expert on C standard library implementations. Just a hobbyist writing a little bit about something I'm trying out.

Potentially relevant is this section of the repo's README:

https://github.com/dikaiosune/rusl#goals-and-non-goals

EDIT: After a suggestion in a sibling here, here's a version which neither explicitly aborts (musl doesn't do abort or unreachable), nor uses an explicit return of usize::MAX:

https://is.gd/lck8c7

It doesn't autovectorize, but I suspect that with some work I could maybe convince LLVM to do so.


IMO, it would be more interesting to see it done top-down, instead of bottom-up. That is, instead of starting with rewriting `strlen`, why not start with rewriting `getaddrinfo`? That would be a very interesting project because you could write `getaddrinfo` with a safe Rust API (i.e. one that doesn't require using `unsafe` to call it), and then wrap it in an `unsafe` function that exports the unsafe C `getaddrinfo` function. This could arguably then be an improvement on the musl code.


I think it very well could be.

However, I would imagine (not having looked at the problem in depth) that one would want to be able to use things like Vec<T> or CString from the Rust standard library when implementing a DNS resolver. Since the Rust standard library depends on libc, I'm not sure how one would properly allow the Rust symbols to replace the linked-in libc symbols while still depending on the rest of libc. Maybe it's not an issue? Maybe there's some magic which could be done?

Nonetheless, I mostly started doing this to see if it could be done, not to prove any point (although I'd love it if a point is proven along the way), so a bottom-up approach with #![no_std] was the easiest way to prevent any sort of cyclic dependencies and/or linker issues.


> Since the Rust standard library depends on libc, I'm not sure how one would properly allow the Rust symbols to replace the linked-in libc symbols while still depending on the rest of libc. Maybe it's not an issue? Maybe there's some magic which could be done?

Static libraries can have circular dependencies like that. For example, in ring[1] I have C code in one static library, which calls some Rust functions in my Rust code. And, that Rust code calls functions in the C static library. The linker...links them together.

[1] https://github.com/briansmith/ring


Circular dependencies are different than duplicate symbols, though, yes? Anyways, my point is not that it's impossible, but that I'm already working at the edge of my knowledge, and I picked the lowest-risk/smallest-chunk pieces of work to get started.


On Linux, the symbols in glibc are marked as "weak"---that is, if the symbol "malloc" isn't found in another object file, then the one in glibc is used. It's that way so that users can override system provided functions (non-"weak" symbols that are duplicated are considered an error).


Some symbols are. Not all.


Yes, but you have to be careful to ensure that no two functions are dependent on each other.


For safe, well-reviewed wrappers around libc (a different problem, but one which is more realistic to solve), I would encourage you to check out the nix crate (I am a maintainer -- the original author was Carl Lerche). It doesn't look like we have a wrapper for getaddrinfo currently, but it is something I think we would welcome.

https://github.com/nix-rust/nix


> musl doesn't do abort or unreachable

musl doesn't do dlclose either --- doesn't mean it's a bad idea. Let's not confuse glibc being bad with musl being good.


The goal of the project is to reimplement musl in Rust. It's not a value judgement about musl, glibc, or any alternative implementation. It's about managing the scope of a hobby project the goal of which is to learn more, not to necessarily do any better than those who've come before.


No you don't abort, aborting or trapping is of last effort. A shared library aborting will kill whatever it's linked to which allows zero chance of recovering. There are two sane ways to go about handling 'impossible states': The API is designed in a way that it returns error info somehow, a type system that tracks side effects in order to allow rolling back.


You can't roll back real side effects like network I/O; that's what it means to be a side effect.

Plus crashing (on some OSes) dumps a lot of useful process state and the current stack, but if a function just returns some error code 50 there's not even a way to find which bits of its internals returned it.

If you separate things by process, you can have your crash-only recovery and keep the rest of the system going.


You can roll back most real side effects like network I/O, console output it just depends on details such as protocol and framebuffer type. You also handle errors at the point of issue, not exceptions.

The issue with separating by process is you have to flush the TLB on context switches.


This is why "interrupted" and "incomplete" are often valid error states.


Rust does have unreachable!() which panics.


Panics are possible with #![no_std], but it does require that you supply a working implementation of panic_fmt, which I haven't gotten to yet (mostly because I was waiting on panic-as-abort to land which it recently did).


OK, another option is to make it an explicit infinite "loop{...}" which only exits by returning. The "0.." is effectively infinite anyway, because it will overflow freely in release mode. (But surely you'll hit an invalid memory page before that happens.)


You're right, I think this version is a bit clearer:

https://is.gd/lck8c7


NB: you still need panic_fmt with panic == abort; the default panic handler still prints a message, even though it doesn't go through with the unwinding.


panic_fmt can be as simple as (C pseudocode):

    printf("...");
    kill(getpid(), SIGABRT);
    while(true)
      /* In case kill(ABRT) returns, halt. */;


> The right line of code isn't "return usize::MAX", but "abort()".

No, it's not. Assertions and aborts at the library level make a library completely unusable for embedded systems. The caller checks the result for plausibility and then decides to restart or simply not to perform the guarded action.


If the caller didn't verify the plausibility of the parameters before calling the function, why is it safe to assume the caller will verify the plausibility of the function result?

Especially for embedded systems, I want the system to blow up on the developer's desk, not in the field, so I'd prefer to fail early.


Because the caller shouldn't know specifics on what is valid for the callee unless the caller has a specific and different value of valid. You don't leak information from separate functions this is how you get brittle garbage code.


> caller shouldn't know specifics on what is valid for the callee

Why? How do you even use an API if you don't know what you can pass into it?


For example strtol, you may pass whatever (implicitly nul terminated, which is bad) and it either returns a value or an error. I wasnt advocating _you_ don't know what to pass but that the caller doesn't include specifics of the callee.


There's a difference between handling all possible error cases (however unlikely) and handling impossible cases.

The moment you hit the latter case you can no longer make any assumptions about the state of the device and an abort/assert is an entirely appropriate thing to do.


It's really not fair to compare the legibility because that code is not at all doing the same.

He's basically comparing his naive "one byte at a time" strlen to one at least processing at register size. The naive version looks just as good in C, frankly better, because what is this "0.." offset nonsense.


> The naive version looks just as good in C, frankly better, because what is this "0.." offset nonsense.

I'm pretty sure "for i in 0.." is clearer (to a reader unfamiliar with either) than whatever it is you'd do in C. In C it would be something like "for(int i=0;;i++)", right?


I'm pretty sure a simple while loop is better than either:

  size_t strlen(const char * s) {
    size_t index = 0;
    while(s[index] != 0) {
      index += 1;
    }
    return index;
  }


That's substantially harder to follow than the code in the article - you have to jump around to see where index changes and how that interacts with the loop condition.


Just out of curiosity how would you rank strlen{1,2,3} in terms of difficulty to read?

  size_t strlen1(const char * s) {
    const char* it =s ;
    while(*it != '\0') {
      ++it;
    }
    return it - s;
  }

  size_t ptr_distance(const void *begin, const void* end) {
    return end - begin;
  }

  size_t strlen2(const char * s) {
    const char* it =s ;
    while(*it != '\0') {
      ++it;
    }
    return ptr_distance(s,it);
  }

  int is_null(const char* p) {
    return *p == '\0';
  }

  const char* find_first(const char* s, int (*predicate)(const char*)) {
    while(1) {
      if(predicate(s)) {
        return s;
      }
      ++s;
    }
  }

  size_t strlen3(const char * s) {
    return ptr_distance(s,find_first(s,is_null));
  }


As someone whos' written almost no C in over a decade, and read minimal C in that time, I would say strlen1 is clearest because it's so simple and succinct, mainly because of how simple the underlying algorithm is.

strlen3 is easiest to read, as you can make fairly valid assumptions about the helper functions, and easily confirm them if needed, and it very clearly breaks down the algorithm into its conceptual components. I think it would also be clearest (and thus winner) if the algorithm was slightly more involved, as the gains in clarity would outweigh the gains of having everything defined in just a few lines.

strlen2 is worst, because the helper function gains you very little for the cognitive overload of having the implementation being somewhere else. You are just as well served in this case by a trailing comment, IMO.


I agree with this comment more or less, however I would like to point out that strlen{1,2,3} are all wrong, at least in the capacity that they take pointer differences and return a size_t.

In truth, `ptr_distance` and `return it - s;` should both be of type ptrdiff_t, which is not necessarily the same as size_t. In some ways this is why using an explicit index of type size_t that can be incremented is better, because you can avoid some type casting.


I would say strlen3 is easiest to read (assuming we're in a codebase that makes widespread use of find_first, ptr_distance and is_null), then strlen1, then strlen2. I think thinking in terms of ptr distances is still needlessly confusing. It's hard to express what we need directly in C (even the Rust version is using nonlocal return which is not the best thing for readability - we could emulate it with goto but that has its own issues) where we don't have generics, anonymous functions, multiple return or tail call elimination. I mean what I'd write in my head (or another language) translates into C as something like:

    typedef struct {
      boolean continue;
      size_t value;
    } result_size_t;

    int indexed_cata_size_t(
        const char *s, void (*operate)(const char, size_t, result_size_t*)) {
      const char *it = s;
      size_t idx = 0;
      // May get initialization syntax slightly wrong but you get the idea
      result_size_t result;
      result.continue = true;
      while(result.continue)
        operate(it++, idx++, &result);
      return result -> value;
    }
    
    void index_of_first_null_u(const char c, size_t idx, result_size_t *result) {
      if(c == '\0') {
        result -> value = idx;
        result -> continue = false;
      }
    }

    size_t strlen4(const char *s) {
      return indexed_cata_size_t(s, index_of_first_null_u);
    }
but I'm not sure that ends up any clearer.


Nice work, maybe. I really don't know if this is a joke. Wow.

FWIW, strlen in C is 5 to 7 lines of code depending on how you format your code. See my other comment.

For those who are not experienced C programmers, yes the shorter code is more readable.


result_size_t and indexed_cata_size_t are generic things that would only need to be written once / in the standard library. (perhaps as macros so that they could be generic i.e. not tied to size_t). So the thing to compare is index_of_first_null_u and strlen4 vs alternate implementation, not the whole set of code that I wrote.

And yeah, it's still not nice. In my preferred language it would be something like:

    def strlen(s: String) = s.cata[size_t] {
      case Cons(head, tail) => if('\0' == head) 0 else 1 + tail
    }
(yes, a cons list is not the same as an array and this distinction is important at this level - but the logic should look similar)

I do think there's value in having a clear separation between what kind of looping you're doing and the per-entry logic (index_of_first_null_u). Is it worth the overhead of doing that in C? Probably not for native C programmers, but if I was writing C to be maintained by functional programmers (or me) then I probably would do it.


I think we would be very unhappy working on the same project. I use functional style in C when it fits... which is rare because most problems are ill-suited to functional programming. The loop on pointer increment and test is completely natural for this problem, as is the pointer math to get the result. This is exactly what the assembly code would do, possibly moving the -1 up to the top and switching from post-increment to pre-increment. (that alternate layout is a C violation that most compilers would accept)

You mentioned that C is missing "generics, anonymous functions, multiple return or tail call elimination". Well, not really.

generics: use the _Generic keyword

anonymous functions: you can autogenerate names via token pasting

multiple return: you can return a struct (living w/o auto-unboxing) or pass a pointer for an extra return value

tail call elimination: there might not be a language requirement for any particular case, but gcc at least is very good about eliminating tail calls -- that said, code which benefits from this optimization is usually hard for humans to deal with

In case you wonder about the C way to count list items...

  if(!node)
          return 0;
  unsigned n = 0;
  do n++;
  while(node=node->next);
  return n;
Like that loop? :-) Curly braces are not needed, and an assignment (plain '=') produces an rvalue that can be tested.


> The loop on pointer increment and test is completely natural for this problem, as is the pointer math to get the result.

Disagree. "Move the pointer forwards until the value it points to is zero, then measure the distance between where it points and where it started" is a very unnatural way for a human to think about computing the length of a string. The pointer is doing double-duty as a pointer and a counter. It's efficient for the computer, but it's exposing implementation details that don't make a lot of conceptual sense (and don't even match the real implementation these days - modern hardware has to do a lot of work with cache invalidation and the like to maintain the illusion of a unified flat memory space).

> This is exactly what the assembly code would do

Absolutely - but assembly is optimized for the computer, not the human.

> generics: use the _Generic keyword

I don't need to do branching based on a finite set of possible types. I want a generic version of result (where value is of the generic type), and I want indexed_cata to accept an operate that returns whichever generic version of result, and return the same type (I made a mistake in my code - it should return size_t rather than int). Can I do that in C?

> anonymous functions: you can autogenerate names via token pasting

Not good enough I think. I need to be able to create a function at runtime. (I wanted to pass the continuation into operate and then operate can either return directly or call the continuation and return the result of that, rather than have operate return a flag that the caller that indexed_cata checks and loops)

> multiple return: you can return a struct (living w/o auto-unboxing) or pass a pointer for an extra return value

I passed a pointer to result and returned via that for exactly that reason. Could I have had index_of_first_null_u return a result_size_t instead of accepting a result_size_t* and it would all work?

> Like that loop? :-) Curly braces are not needed, and an assignment (plain '=') produces an rvalue that can be tested.

I don't. "=" in a loop test is horrible for readability (it looks like an error (and often is), and has very different semantics from mathematical "=" - pascal-style "while(node := node->next)" would be a much clearer syntax), and returning values that are usually discarded is bad practice (I would like discarding values to be a rare event, probably something that can be a compiler warning - ideally I'd like something like a linear type system). The "do" and "while" look like unrelated statements. The if at the top as the special case is ugly and shouldn't be necessary - when a loop is expressed elegantly the zero case should just fall out naturally.


Having the pointer "doing double-duty as a pointer and a counter" reduces the potential for bugs. If you do otherwise, then you have more variables to think about and they could get out of sync.

It does match the hardware. There is no cache invalidation.

C programmers commonly think in terms of assembly. They might not envision a particular kind of CPU, but low-level operations are in their mind. The better programmers actually check the assembly sometimes. They know that a "do" loop is normally smaller than a "while" loop because the "while" loop gets converted into a "do" loop inside an "if" that handles the case of no iteration.

The _Generic keyword is resolved by the compiler, so there is no branching. One can also use a macro. Macros can be the normal function-like type of course, but there is so much more. Macros can be used to define functions. Macros can be used with repeated inclusion of the same header file, allowing the creation of many different versions of code. This lets you generate indexed_cata__size_t and indexed_cata__uint64_t and so on, which you would then hook up via a macro called indexed_cata that uses _Generic to dispatch (with zero run-time overhead) to the correct implementation.

I probably don't really get what you're looking for with the continuation stuff. Wikipedia compares it to setjmp/longjmp and goto, which doesn't sound too nice. This is all completely off-the-wall alien to a C programmer. It's hard to get excited about learning to understand something that is associated with really slow programming languages.

Being "able to create a function at runtime" is normally incompatible with having a small high-performance runtime. In C you have a choice: fake it, or do things the awesome way. You can fake it with macros, possibly including ones that expand out to define functions. The awesome way is to JIT, and yes I've done this: allocate a chunk of memory, write out some binary instruction code, deal with any permissions/cache/pipeline issues, and then call it as a function or use a bit of inline assembly to reach it. Oh, there is another way that might be more your style: create C code on-the-fly, feed it into the compiler to generate a library, dlopen the library, and call your new function.

Yes, you can return a struct. What you don't yet get is any syntax to automatically split that apart in the caller. The caller will end up with a struct. Hopefully the next C revision will improve this.

Expressing my loop in an alternate way is likely to generate code that is bigger and slower. This particular case is trivial enough that gcc 4.8.4 can optimize it down to the exact same bytes, and a newer gcc probably just substitutes a call to strcpy unless you pass -ffreestanding to stop that optimization. Normally it makes a difference.


> Having the pointer "doing double-duty as a pointer and a counter" reduces the potential for bugs. If you do otherwise, then you have more variables to think about and they could get out of sync.

If you're just adding 1 to both each time then it's pretty hard to get that wrong. I think storing the original pointer and subtracting at the end has more potential to go wrong.

> I probably don't really get what you're looking for with the continuation stuff. Wikipedia compares it to setjmp/longjmp and goto, which doesn't sound too nice.

It's not well-explained - the terminology is arcane, people use the word to mean different things. But done right it can give you the performance and flexibility of goto but with the clarity of regular function calls, and all your control constructs can just be library functions.

> It's hard to get excited about learning to understand something that is associated with really slow programming languages.

Shrug. Almost all programming languages are fast enough these days. Correctness is often much more of an issue.

> Being "able to create a function at runtime" is normally incompatible with having a small high-performance runtime. In C you have a choice: fake it, or do things the awesome way. You can fake it with macros, possibly including ones that expand out to define functions. The awesome way is to JIT, and yes I've done this: allocate a chunk of memory, write out some binary instruction code, deal with any permissions/cache/pipeline issues, and then call it as a function or use a bit of inline assembly to reach it. Oh, there is another way that might be more your style: create C code on-the-fly, feed it into the compiler to generate a library, dlopen the library, and call your new function.

I don't need anything that complicated. Just the ability to partially apply a function would do. Or even ordinary classes. Which I mean sure, I can emulate by passing a struct consisting of a function pointer and the first argument as data, but that's going to be awful to read.


Functional programming throws away the "clarity of regular function calls" by abusing them or their syntax for control flow. It's an unreadable mess. Having control constructs be library functions seems to be an extension of this, making the situation much worse.

I write code to emulate the modern multi-GHz PC and other things running at about a GHz. It's timing sensitive, so the emulator needs to keep up, and we really want to emulate SMP on one core. My coworkers write code to treat a binary executable as a giant equation, solving it to find inputs which cause crashes. We pay lots of money for giant rooms full of computers running our code.

All programming languages are way too slow.

I'd switch to FORTRAN if it was 2x faster. I'm using C99 with lots of non-standard extensions and inline assembly. We use SSE intrinsics to vectorize things by hand.

Meanwhile, people like you are making my web browser too damn slow. It's 2016, and it feels like 1996. Other than a slight increase in pixels and always getting 24-bit color, there has been no improvement in speed despite the hardware being something like 1000 times faster. WTF. I paid good money for that hardware because I wanted things faster. I didn't buy that hardware to be wasted. Your code is not special. Each programmer tests his code in isolation, giving it the whole machine, but out in the wild it must share the machine with other code and/or with numerous instances of itself.

Sometimes gcc's optimizer will partially apply a function. I've seen the result via disassembler. This beats partially applying functions by hand. For example, the function may do different things if a certain parameter is NULL. The compiler makes a version of the function for when the parameter is NULL, and another for when it is not.

Passing a struct with a function pointer and argument seems a little annoying for a trivial situation, but it makes lots of sense when there are multiple functions and multiple arguments. For the trivial case, one would normally just pass the function pointer and argument separately.

I think I've written code that matches your "partially apply a function" idea pretty well, using macros. Like this:

There exist functions for reading/writing memory with names like read_mem_8 and read_mem_32, for several different sizes. I want to make wrapper functions called read8 and read32 and so on. The wrapper functions check for alignment, check a TLB, check for breakpoints, and then call the wrapped function or do the access directly. I make a macro that expands out to the function I want whenever I "call" the macro. No, I don't mean a regular function-like macro. Mine actually creates a real function. I invoke the macro itself at top level, outside of any function, right after creating the macro. I invoke it for each size that I want. Macro expansion generates a function that I can later call.

Invoking it looks like so:

  define_read(8)
  define_read(16)
  define_read(32)
  define_read(64)
  define_write(8)
  define_write(16)
  define_write(32)
  define_write(64)
Note the lack of a semicolon. These macros expand to actual functions that I can call. I could even take the address of the resulting functions if I wanted to, not that I do.

Invoking the result of the macro expansion looks like so:

  write32(cpu,addr,val);
For bigger things, one would put the template-like version of the function in a .h file and then include it repeatedly, each time with different choices. Like so:

  #define CHOSEN_BIT_WIDTH 32
  #define CHOSEN_ENDIANNESS ENDIAN_BIG
  #include "def_stuff.h"
  #undef CHOSEN_BIT_WIDTH
  #undef CHOSEN_ENDIANNESS
  
  // ... and then again with different choices


> Functional programming throws away the "clarity of regular function calls" by abusing them or their syntax for control flow. It's an unreadable mess. Having control constructs be library functions seems to be an extension of this, making the situation much worse.

Shrug - that's the opposite of my experience. When you're working in a world where functions are functions, you don't need explicit control flow - you just want to express what the return value needs to be, and have the computer do whatever it needs to to make it happen as quickly as possible. Restricting yourself to a call stack model is something you have to do for sanity in a language with pervasive mutability and side effects, but as a C programmer you surely know that it means giving up some performance. In a language where your functions are pure (which is often where you want to be for optimization anyway - compare GCC's SSA form) a lot of the need to explicitly reason about control flow goes away.

> Sometimes gcc's optimizer will partially apply a function. I've seen the result via disassembler. This beats partially applying functions by hand. For example, the function may do different things if a certain parameter is NULL. The compiler makes a version of the function for when the parameter is NULL, and another for when it is not.

I'm asking to express a partially applied function in code, not for performance but for clarity and readability.

> I think I've written code that matches your "partially apply a function" idea pretty well, using macros. Like this:

I don't want to do it at compile time, I want to do it at runtime. A super-trivial example would be something like:

    def add(x: Int, y: Int): Int = x + y
    def addX(x: Int): Int => Int = add(x, _)
i.e. I want addX(5) to return a (pointer to a) function that takes an int and returns an int that's that int + 5. How do I do that in C?

    int add(int x, int y) { return x + y; }
    int (*)(int) addX(int x) ???
I can return a struct that contains 5 and a pointer to add, but that requires whatever calls addX to know about the difference between this and a normal function.


Most programs aren't about a return value. They are about global state, including IO and huge data structures. The functional programming hacks for IO are gross. The issue of dealing with huge data structures is generally not solved; when you make a tiny change to a terabyte you have an awkward problem.

It's not standard C, but gcc will let you mark a function as being pure. Even without that, the compiler may notice.

I don't agree that expressing a partially applied function at runtime helps clarity and readability. I suppose tastes differ, and some people have bad taste. :-) The real trouble is that this is not something that is natively supported by the hardware. Your language either interprets a very unnatural machine, or it drags along a compiler.

Interpreting a very unnatural machine is unappealing. It distances you from reality, making it difficult to reason about how your code will perform on the hardware.

Dragging along a compiler is sometimes, rarely, justified. It's appropriate when the partially applied function must run for a long amount of time. Sometimes people even drag along a compiler for a different processor, such as a GPU. We find this to some extent with CUDA and OpenCL.


> Most programs aren't about a return value. They are about global state, including IO and huge data structures.

Not my experience at all. Most of the time if you're using a computer it's because you want to, well, compute. I/O happens but very often it's a simple matter that can be pushed to the edges, and the business logic that you actually need to be thinking about can be cleanly encapsulated.

> The functional programming hacks for IO are gross.

Only because I/O is gross. I find it's more a case of: functional style forces you to expose the ugliness that was always there underneath. Often you uncover things like the family of security vulnerabilities where an application creates a temporary file and then opens it and an attacker can replace it with a symlink in between. If you really want to say "do these I/O operations whenever, it'll all work out" then it's trivial to do that, even in Haskell (you just add "unsafePerformIO $" before all your I/O calls), but most people find it's actually worth explicitly figuring out which order things are supposed to happen in and doing that.

> I don't agree that expressing a partially applied function at runtime helps clarity and readability. I suppose tastes differ, and some people have bad taste. :-) The real trouble is that this is not something that is natively supported by the hardware. Your language either interprets a very unnatural machine, or it drags along a compiler.

Not at all. Every language with classes manages to do this (even Java can do it nowadays), C++ included. It's not hard to implement. What it does require is one more layer of indirection around function calls (if you're really bothered about the overhead you can make it opt-in i.e. "virtual" in C++). I could write my own code to do this in C, but a) I couldn't use the "function(arg1, arg2)" syntax because there's no way to override that (would have to do something like a macro, "VIRTUAL_CALL(function, arg1, arg2)") and b) it wouldn't interoperate with any of the rest of the ecosystem. You might not want to use it in every program, but this is the kind of thing that absolutely needs to be part of a language-wide standard for programs that do want to use it, so that libraries from different people can interoperate with each other.

(FWIW I think the idea of corresponding to the hardware is a false idol - or at least, if there is a way to achieve it, C isn't that. GCC generates something very different from a hand translation into assembly. Even assembly no longer corresponds to what the actual processor will do (microops). Modern processors are inherently parallel and no remotely mainstream language expresses that accurately.)


Probably you'd end up with this:

foo->bar(foo,arg1,arg2)

It's not as simple-looking, but that isn't all bad. It's very clear what is going on. The overhead isn't hidden.

Things needing call-back functions need to support an extra void* of course, and sadly it is often left out.

Understanding how compilers translate C into assembly is a skill that must be practiced. I suggest getting in the habit of looking at the binary. After a while, you will know what to expect. The optimizers are not magic. They do fairly predictable transformations on the code. You can get a feel for when hand-optimization matters, and when it is just pointless. An awareness of cache lines and TLB entries is helpful too.


> Things needing call-back functions need to support an extra void* of course, and sadly it is often left out.

Well when doing the right thing means writing more verbose code, it's no surprise that people do the quick-and-dirty thing (see http://www.haskellforall.com/2016/04/worst-practices-should-... ). Since "everyone knows" that best practice for a callback is to take a function pointer and a void * , wouldn't it be better to have that idiom built into the language? (i.e. a concise syntax for the pair of callback-and-void * , and a concise syntax for "invoking" the pair, passing the extra void * along with the "ordinary" arguments).


Here is the way that is correct and obvious to a modern C programmer. Real C libraries use assembly and/or multi-byte methods that violate aliasing rules.

  size_t strlen(const char *restrict const s){
          const char *restrict t = s;
          while(*t++)
                  ;
          return t-s-1;
  }


I wonder what is the benefit of rewriting the libc in Rust, as most of the functions are actually unsafe. Implementing memcpy in Rust won't make memcpy any safer.

As far as I understand, the main selling point of Rust is safety, so if we don't get any safety, why bother? Am I missing something? (Other than having some fun with Rust, which is obviously welcome :) )


I came to this thread hoping to answer this exact question. :)

There isn't a huge benefit to writing things like strlen in Rust. But a lot of libc is big, complicated things like the DNS resolution logic in gethostbyname. These are also where we find a huge number of vulnerabilities in popular libcs. The internal logic of functions like gethostbyname should be able to profitably take advantage of Rust's safety features.


For this project, the advantage to rewriting strlen in Rust is for my learning and to test my Frankenstein-ian link-time munging, not because Rust is better at unsafely dereferencing random pointers (C's got that pretty well covered). I do hope to soon move on to the more meaty bits and show ways in which Rust can improve safety, but I wanted to get my initial thoughts and results written down so I could reference back to the post later. Frankly did not expect to see it here :).


There are other advantages too. If you rewrite libc in Rust you can also take advantage of link time optimisation, full static compilation and (further) platform independence.

That and people underestimate the value of the entire codebase being in a single programming language and environment. If your language continues to rely on C dynamically linked libraries there remains a barrier that your workflow can't be translated across. This is more pronounced in languages like Ruby/Python/Java ofcourse but it's still true for Rust to some extent. Having everything written in Rust (or whatever language you prefer) has compounding benefits when it comes to productively programming on really large systems.


Don't get me wrong (I mean I'm rewriting in Rust), but:

LTO and static compilation are available to binaries built and statically linked with musl (it's one of the main advantages musl has over glibc, aside from being a more readable and cleaner codebase). And musl has done a lot of work to have correct cross-platform implementations. Granted whenever Rust adds a new target, it should be easier for things to "just work" when cross-compiled, but Rust is far less portable than C + a modicum of macros at the moment.


Here's musl's DNS resolution logic, for other people who may be curious: http://git.musl-libc.org/cgit/musl/tree/src/network/lookup_n...


This exemplifies why I've always been mystified by those that say Perl is line noise, but don't seem to have a problem with C. It's obvious to me that what one considers hard to read code, or colloquially as "line noise", is greatly impacted with how familiar one is with a language and the idioms of that language being used in the code in question.


That is crazy simple. I bet glibc's is a lot longer.



Also, stuff like glob(), fnmatch(), regcomp()/regexec(), should be better in Rust. They involve a bit of parsing.


I'm eager to try out some of the Rust parser combinators for different sections, but I need to make it possible to start using parts of the standard library to import those crates, which is why I'm working on malloc/free and friends right now.


For simple functions like memcpy, I think you're right. But it may be worthwhile to implement higher-level libc features like the DNS resolver in Rust.


I agree that with very unsafe functions Rust's memory guarantees are not particularly relevant. There are however some other benefits which I discussed in the post (sum types, strict integer typing without promotion, etc.).


Has anyone experimented with a C-to-Rust translator?

Google wrote a C-to-Go translator to aid their conversion of the Go compiler from C to Go. Carol Nichols gave a talk about her function-by-function, by-hand rewrite of the Zopfli compression library from C to Rust. I wonder how much of that could be automated, even if most of the resulting Rust code is in unsafe blocks.

Carol's slides:

https://github.com/carols10cents/rust-out-your-c-talk


I guess the output would be very ugly as the C semantics are probably ugly to reproduce in rust. For instance arithmetic with unsigned types in C is defined to be wrapping, so you would need e.g. calls to wrapping_add() instead of + all the time.


I'd be OK with a shallow syntactic translator that only does the first laborious step of the conversion, without trying to preserve too much semantics. Rust with exact C semantics isn't going to be better than C, so I'd prefer readable code that is easier to read & refactor.

I've converted a few utilities from C to Rust. Rewriting `void foo(int a)` to `fn foo(a:int)` is boring menial job. Only the next step of replacing C's pile'o'pointers with Rust idioms is fun.


As a corollary to writing the C standard library in Rust, are there any plans by the Rust devs to remove the C standard library dependency itself? That, to me, is just as interesting of a proposition.


It's not a high priority task, no. (Though it would be quite interesting to see it done.)

On Windows and Mac OS X you shouldn't really avoid C libraries (kernel32.dll and libSystem.dylib respectively) because the syscall interface is considered a private API. (You can avoid it technically, and apps sometimes do, but Microsoft and Apple would be within their rights to break us at any time if we did that.)


In addition to Windows and Mac OS X, illumos and I believe all of the BSDs require you to use libc for the same reason. I'm sure that they exist, but I don't know of any kernels other than Linux where the syscall layer is a stable interface. (I'd love to learn about some others though, if anyone knows.)


But those are technically the OS system calls, not libc.

Would the Rust team accept PR to remove the dependencies on libc for Windows?


> But those are technically the OS system calls, not libc.

They're libc calls, libSystem is the union of a bunch of libraries including libc. In fact, these unioned libraries are just symlinks to libSystem:

    libc.dylib -> libSystem.dylib
    libdbm.dylib -> libSystem.dylib
    libdl.dylib -> libSystem.dylib
    libgcc_s.1.dylib -> libSystem.B.dylib
    libinfo.dylib -> libSystem.dylib
    libm.dylib -> libSystem.dylib
    libmx.dylib -> libSystem.dylib
    libpoll.dylib -> libSystem.dylib
    libproc.dylib -> libSystem.dylib
    libpthread.dylib -> libSystem.dylib
    librpcsvc.dylib -> libSystem.dylib


Still, isn't ironic that a systems programming language isn't able to be used without C, because its runtime was made to rely on libc instead of the raw OS APIs?

I understand the shortcut as a way to reduce development time, but maybe that is something to improve.

Go made the right decision by integrating directly with the OS APIs.


> rely on libc instead of the raw OS APIs?

The argument here is that on Windows and Mac OS X, the libc library is the ‘raw OS API’ and it hence makes perfect sense to rely on it if you want to support such operating systems.


On Windows it isn't. Microsoft has made it clear that you aren't supposed to link to the msvcrt.dlls shipped in Windows. See https://sourceforge.net/p/mingw-w64/wiki2/The%20case%20again...


If I want to zero memory on Windows without libc dependencies, I use ZeroMemory() or FillMemory() and not memset().

No need to have any dependency on msvcr*.dll or the equivalent for Borland, Intel and other Windows compilers, which are effectively the Windows libc.


there is a baremetal rust os that avoids libc. I think it achieves this by avoiding the rust standard library.


On Windows, does Rust currently require/use (nontrivial features of) the C standard library in addition to the C "win32"/"winapi"/w/e libraries?


The math library AFAIK, in order to provide the same wrong results that the MSVC implementation gives.


Heh? Can you point to a description of the wrongness of MSVC maths.

I noticed that they were a bit slow to support infinities and NaN, but that is not the same thing a being wrong.


So, with libcore, you don't have a libc dependency. With libstd, you do. There has been some interest in making it easier to port libstd away from it, but it would likely be a cross target, like musl itself, rather than an official move. We'll see what the future holds!


For me coolest part is the algorithm for determining if word contains zero byte.

    #define ALIGN (sizeof(size_t))
    #define ONES ((size_t)-1/UCHAR_MAX)
    #define HIGHS (ONES * (UCHAR_MAX/2+1))
    #define HASZERO(x) ((x)-ONES & ~(x) & HIGHS)
Assuming sizeof(size_t) is 4 and UCHAR_MAX is FF...

It takes FF FF FF FF (by casting -1 to unsigned size_t), divides it by FF, getting 01 01 01 01 (ONES).

Then gets 80 80 80 80 (HIGHS) by multiplying 01 01 01 01 by 80 (which is gets from (FF+1)/2).

Once it has these two values it tests which bytes are lower than 80 by doing ~(x) & HIGHS and keeps result in highest bit of each byte and zeroes lower ones.

Other part is subtracting ONES from (x) which results in highest bit set in each byte either because (x) had more than 80 in that byte or (x) having zero in that byte and borrowing from higher byte (underflow in case of highest byte).

ANDing those two cases rules out highest bit set due to (x) byte being more than 80. What's left is all zeroes if and only if all bytes of (x) were non-zero.

Funny thing is that if borrowing from higher byte happens (because some byte was zero) it might mess up test for that higher byte but it doesn't matter because you will already detect zero in lower byte so you don't care about test on higher bytes then.

If what I wrote above is unclear then try here: http://stackoverflow.com/a/34643025/166921

This is algorithm that checks if word has a byte that is less than given value (1 in that case, but surely valid up to 7F ... maybe more by some magic? probably not...). Also works for different lengths of "words" and "bytes" provided that whole number of "bytes" fits in a "word".


Thus I give you my first Rust program ;)

    // needs in main.rs or lib.rs #![feature(const_fn)]

    use std::os::raw::c_schar;
    use std::mem;

    const ALLSET:usize = (-1_isize) as usize;
    const MAXCHR:usize = u8::max_value() as usize;
    const ONES:usize = ALLSET / MAXCHR;
    const HIGHS:usize = ONES * ((MAXCHR+1)/2);
    const ALIGN:usize = 8; // mem::size_of::<usize>(); // mem::size_of<T>() is not const fn (yet?)

    pub unsafe extern "C" fn strlen(s: *const c_schar) -> usize {
        let mut i:usize = 0;
        loop {
            if *s.offset(i as isize) == 0 { return i; }
            i += 1;
            if (i % ALIGN) == 0 { break; }
        }
        loop {
            let v = *mem::transmute::<*const c_schar, *const usize>(s.offset(i as isize));
            if v.wrapping_sub(ONES) & !v & HIGHS != 0 {
                break;
            }
            i += ALIGN;
        }
        loop {
            if *s.offset(i as isize) == 0 { return i; }
            i += 1;
        }
    }


Wonderful work! Keep it up!


Thanks!


Any plans for rust to switch to an allocator written in Rust?


On nightly, we have the ability to swap out allocators. But I'm not aware of an allocator written in Rust that's as high-quality as jemalloc yet; it'd have to be pretty good before we'd move over. I'm not aware of any serious effort to write one, yet.


While Rust can indeed provide great benefits over C in many respects (mostly security and safety, but also maintainability), rewriting "everything" in Rust, as the author says, is so monumental an effort that there is no chance of it happening, certainly not before a "better" language than Rust comes along (say, in another ten or fifteen years), and then what? Rewrite everything in that language?

A far more feasible approach (though still very expensive) -- and probably a more "correct" one, even theoretically -- is to verify existing C code using some of the many excellent verification tools (from static analysis to white-box fuzzing and concolic testing) that exist for C[1]. It is more "correct" because, while perhaps not providing some of the other benefits, those tools can prove more properties than the Rust type system can, and such tools don't (yet) exist for Rust.

Even if you want to write a green-field project today that absolutely must be correct, it's better to do so in C (or in some of the verified languages that compile to C, like SCADE) and use its powerful verification tools, than to write it in Rust. Verification tools are usually much more powerful than any language feature (even though Rust's borrowing system seems like it can prevent a lot of expensive real-world bugs). Of course, it would be optimal if we could do both, but the Rust ecosystem simply isn't there just yet.

This is part of a more general problem, namely that rewriting code in new languages -- any new language -- is so costly (and often risky, too), that the benefits are rarely if ever commensurate with the effort. This is why good interop with legacy libraries is so important (something, I understand, Rust does well), often much more important than most language features. Rewriting code is often the worst possible way to increase confidence in a library/program in terms of cost/benefit, both because verification tools are often more powerful than any language feature, as well as because new bugs are introduced -- either in the code or in the compiler (bugs that won't be uncovered by the usually incomplete legacy test suite, but would break some of the millions of clients). Rewriting is usually worth the effort if the codebase is about to undergo a significant change anyway, but almost never to increase confidence in the existing functionality.

EDIT: Clarification: if you're not going to use verification tools in your new project, anyway, than obviously using Rust would give you much better guarantees than C.

[1]: C and Java are the languages with the best collection of powerful verification tools (maybe Ada as well, but there's far less Ada code out there than C or Java).


I don't buy the argument that verification using heavyweight verifiers is less expensive than rewriting in Rust. Formally verifying a piece of code is an enormous effort, while writing in Rust is usually less effort than the original unsafe code took to write, thanks to Rust's ergonomic improvements over C.

Besides, most safe languages for embedded use (SPARK, etc) get their safety by disallowing dynamic allocation, which is great for avionics systems and not so great for libc or any consumer or server software. (Or they use a garbage collector for the heap, which is not what you want for libc for the usual reasons.) Not coincidentally, the novel part of Rust's type system is the marriage of easy-to-use, zero-overhead C++-style dynamic allocation with the flexibility and safety of Cyclone-style region checking.


> while writing in Rust is usually less effort than the original unsafe code took to write, thanks to Rust's ergonomic improvements over C.

Absolutely, but do you think that rewriting billions of lines of C code in Rust is the best, most cost-effective way to increase confidence in them? Also, using verification tools can be done much more gradually (say, function by function) than rewriting in a new language (which may require a lot of ffi if done piecemeal), and there's no need to fear new bugs.

> Besides, most safe languages for embedded use (SPARK, etc) get their safety by disallowing dynamic allocation, which is great for avionics systems and not so great for libc or any consumer or server software.

True. I don't actually suggest using SCADE or SPARK for libc :) Astrée wouldn't work, either, as it also assumes no dynamic code allocation. But something like SLAyer (a tool by MSR based on proving separation logic properties through abstract interpretation) or Facebook's Infer should. I would guess that making those tools work well on more and more real-world code would be a much smaller undertaking than rewriting in Rust and proving no new bugs have been introduced.

I'm generally skeptical of significant, real-world, bottom line benefits new languages provide, but Rust has convinced me that, at least potentially, it can have some very significant benefits over C. But a wholesale rewrite of a near infinite amount of code, much of which may work well enough, plus the risk of adding new bugs in the process, without the means to detect them??? That's like draining the ocean with a spoon in the hope of finding a sunken treasure. Software engineers often speak of using the best tool for the job; rewriting vast amounts of code (with very incomplete test suites) in a new language is certainly far from the best tool for the job of increasing confidence in its correctness (unless a particular piece of code is buggy beyond repair).

Same goes for physical infrastructure, BTW. If your infrastructure is old and you fear some bridges may collapse, you inspect them all. You rebuild the crumbling ones and strengthen those with cracks. What you don't do is rebuild all the bridges in the country. That's not only wasteful and comes at the expense of new bridges you could have built, but may end up increasing the danger in some cases, rather than decreasing it.


Same goes for physical infrastructure, BTW. If your infrastructure is old and you fear some bridges may collapse, you inspect them all. You rebuild the crumbling ones and strengthen those with cracks. What you don't do is rebuild all the bridges in the country. That's not only wasteful and comes at the expense of new bridges you could have built, but may end up increasing the danger in some cases, rather than decreasing it.

I would say this is more like a new building material coming along which allows infrastructure to be built that results in a safer construct. No, you don't want to rebuild everything at once, and maybe you never want to rebuild everything, but sometimes old but serviceable things may be considered for replacement because not only can it be made safeer, but there may be other benefits at the same time (less room, more likely to withstand 1 in X type natural disasters, etc.).

Additionally, I never took the "rewrite everything" camp, as presented here, to really mean "everything" as much as to mean "a stack from the bottom up so there are rust versions to use". Java seems has a lot of this, by virtue of being a contained system that doesn't like to share it's memory, so there are Java versions of just about everything. Rust can use C with zero cost runtime cost, I think people just want to make it so that rust must use C for certain things.


A big part of writing about this was to share one potential strategy for reducing risk in rewrites by doing it function by function. That's a strategy which is available to Rust with zero overhead FFI, so I'm not sure why you're holding that up as a benefit exclusive to static analysis and verification tools.


Because -- and I may be wrong about this -- the FFI has zero runtime overhead, not zero coding effort overhead (i.e., FFI code isn't identical to native Rust code). So you'd want to rewrite again (the FFI code to native code) as you translate more functions.


How does that differ from what's been reported is extensive work to appease static analysis tools?


It differs by being a far more expensive (and probably less effective) way to achieve the goal. Those verification tools were designed to be spectacularly less expensive than a rewrite in a new language (which is often prohibitively expensive), or they wouldn't have been designed in the first place (they're all much newer than safe systems languages like Ada).

I said that using verification tools is expensive, but I'd be surprised if it's not at least one, if not two, orders of magnitude less expensive than a rewrite (I can think of few if any more expensive ways of increasing confidence in such large amounts of legacy code than rewriting it). It can provide similar -- sometimes worse, sometimes better -- guarantees, requires much less creativity, it automatically focuses you on places in the code that are likely to be buggy (or, alternatively, shows you which code is likely not buggy) and cannot introduce new bugs that you have absolutely no way of detecting before pushing the new code to production systems.

(BTW, the chief complaint against those tools -- and what makes them expensive to use -- is that they have too many false-positive reports of potential bugs, but even "too many" is far fewer than every line, which is what you'll need to consider and study when rewriting.)


> and cannot introduce new bugs that you have absolutely no way of detecting before pushing the new code to production systems.

Yes, they can. Remember the Debian OpenSSH vulnerability that arose from blindly making changes that Valgrind suggested?

> It can provide similar -- sometimes worse, sometimes better

Much worse, unless you're talking about systems that verify memory safety problems by disallowing dynamic allocation.

> Those verification tools were designed to be spectacularly less expensive than a rewrite in a new language (which is often prohibitively expensive), or they wouldn't have been designed in the first place (they're all much newer than safe systems languages like Ada).

I don't agree. Are you talking about things like Coverity? Coverity hasn't effective at stemming the tide of use-after-free and whatnot.

I strongly encourage you to familiarize yourself with Rust's ownership and borrowing discipline and to understand how it prevents problems like use-after-free. You'll find that it's very hard to retrofit onto C, and that's why no practical static analyses do it.


I agree that Rust is superior solution if we're talking use-after-free detection. Also agree on tool immaturity. However, recent results might make you reconsider how practical they are.

http://research.microsoft.com/en-us/um/people/marron/selectp...

https://dl.acm.org/citation.cfm?id=2662394&dl=ACM&coll=DL&CF...

IMDEA's Undangle seems to have nailed it totally with one other doing pretty good. You're the compiler expert, though. Does Undangle paper seem to be missing anything as far as UAF detection or is it as total as it appears?


What I think is relevant in this case is not whether an an external tool for C can reach the same levels of safety presented by Rust, but whether an external, optional tool will every be able to provide the same level of assurance given that you can't ensure confirmity on the (source) consumer end without getting all the same tools and rerunning them (which is the situation you have when it's built into the compiler.

Another way of stating this is "code verification tools for C are great! What level of market penetration do you think we can achieve? Oh. That's disappointing..." :/


That's a great point but a bit orthogonal. It's very important if one is aiming for mass adoption. Hence, why C++ was built on C and Java combined a C-like syntax with a marketing technique I call "throw money at it." We still need to consider the techniques in isolation, though.

Here's why. One type of tool needs to either not force conformity or blend in seemlessly with everyone's workflow with wide adoption due to awesome compatibility, safety, efficiency, and price tradeoffs. That's HARD. The other is just there for anyone that chooses to use it recognizing value of quality in a lifecycle. It just needs to be efficient, effective, have low to zero false positives, work with what they're using, be affordable, and ideally plug into an automated build process. These C or C++ techniques for safety largely fall into category number 2.

I totally agree with you on overall uptake potential. There's almost none. Most of the market ends up producing sub-optimal code with quality non-existent or as an after-thought. Those that do quality in general follow the leader on it. It's a rare organization or individual that's carefully researching tools, assessing their value, and incorporating everything usable into the workflow. Nothing I can really do about this except push solutions that are already mainstreaming with the right qualities. Rust, Go, and Visual Basic 6 [1] come to mind.

[1] When hell freezes over...


> Yes, they can. Remember the Debian OpenSSH vulnerability that arose from blindly making changes that Valgrind suggested?

Obviously, I'm not suggesting to blindly make any code changes. But do you honestly think the risk is anywhere at the same level as rewriting the whole thing? At least concentrate the effort where there likely is a problem rather than everywhere.

> Much worse, unless you're talking about systems that verify memory safety problems by disallowing dynamic allocation.

No. I am talking about both tools that are designed to uncover errors somewhat similar to Rust (SLAyer, Infer) as well as tools like CUTE and American fuzzy lop, that have completely different strengths. The former may be much worse; the latter may be much better. But let me suggest this: how about using tools like CUTE or AFL to generate more tests first, just so you at least have a better idea of which code is more problematic than other? You're suggesting to rebuild every bridge before even conducting an inspection that would give you an idea about where most problems lie. Those tools have been proven to be effective (see a very partial list here: https://news.ycombinator.com/item?id=11891635) and they do require orders of magnitude less work than a manual rewrite (they require less effort than even reading the code, let alone translating it). Shouldn't they at least guide the effort, help us concentrate our force where it would yield the biggest advantage?

> I strongly encourage you to familiarize yourself with Rust's ownership and borrowing discipline and to understand how it prevents problems like use-after-free. You'll find that it's very hard to retrofit onto C, and that's why no practical static analyses do it.

I am familiar with Rust's borrowing and I absolutely fucking love it! It is freakin' awesome! I recommend it to every C/C++ developer, and I sing Rust's praises whenever I have the chance; I really (really really) do. I think that Rust is definitely one of the most significant contributions to systems programming in the past couple of decades (if not more), and it is one of the most interesting (and potentially significantly useful) languages of any kind. I love and admire what you've done. Just the other day I told a friend that I'm sad I don't do as much low-level system's programming as I used to just so that I could have a chance to closely work with Rust rather than merely admire it.

But that has little to do with what I'm saying. First, I am not saying that the two approaches would squash the same bugs (see above). Second, suppose you're right about your analysis of the quality of the result (even though I disagree, as above). The question is not which would yield a better result overall (and I might agree that a Rust translation would, if only by ensuring that every line of code out there gets read and analyzed) but whether the result is worth the undertaking, and whether the best, most cost-effective way to improve the safety/correctness of legacy code of unknown, probably widely uneven quality, with little to non-existent test coverage is by rewriting the whole thing whenever a new, safer language comes along. I must say that I am truly surprised that you suggest that to be the most worthwhile, economically reasonable approach. Rebuilding every bridge when a stronger building material is invented really is terrific (provided that the work is infallible); but is that the most economically sensible approach to improve infrastructure? Isn't the effort best spent elsewhere?


I think that since you're making concrete claims about actual cost and benefit, perhaps it's appropriate to suggest that you cite some sources (postmortems, white papers, journal articles) which have found these assertions to be true?


You're suggesting that rewriting billions of lines of code that probably contain lots of bugs somewhere every time a new safer language comes along is the most sensible investment of effort by the software industry in order to improve the quality of our software infrastructure, while I'm saying, wait, maybe we should use some inspection tools first before we decide on an approach, so at least we know where the worst of the problem is, and you think I'm the one who needs to cite sources? Alternatively, do you think that "rewrite all legacy code!" (an effort that would probably cost billions of dollars) does not need to be justified by concrete claims about actual cost and benefit?

But fine, here's a taste (look for what is required to use the tool as well as results):

* http://mir.cs.illinois.edu/marinov/publications/SenETAL05CUT...

* http://lcamtuf.coredump.cx/afl/ (see the "The bug-o-rama trophy case")

* http://research.microsoft.com/pubs/144848/2011%20CAV%20SLAye...

* https://code.facebook.com/posts/1648953042007882

* http://link.springer.com/chapter/10.1007/978-3-319-17524-9_1

Note that there are some strengths, some weaknesses, but I hope those sources make it clear that using those tools first is at least more sensible than "rewriting everything", as they require orders of magnitude less effort, and they do uncover bugs (you're free to guess what percentage of those bugs would be found in a rewrite, and whether the bug density demands a rewrite). We may decide that a rewrite of some libraries is the best approach once we have more information.

Now, do you have any sources suggesting that a complete rewrite is cost-effective?


The biggest problem I (not being the people you've been conversing with so far, for the most part) have with relying on static analysis tools on top of C, instead of a rewrite, is that the analysis tools are not enforceable. You can do all the analysis you want, and put in all the procedures you want, but in the end people are submitting changes to these libraries, and you need to make sure that these people are ensuring the tools get run prior to release. Additionally, from the perspective of a user of this code, my ability to look at the source and know that it's been scanned ranges from uncertain to non-existent. Switching to a compilation system where these constraints are enforced (such as a new language that enforces it) has a benefit in that respect. You could get a similar benefit by releasing a specialized C compiler that enforced some static analysis tools and required a very small amount of syntax change such that the code would not compile on a vanilla C compiler, and then I think the there would be much less of a case for a rewrite in Rust from a safety point of view (even if they would handle slightly different aspects of safety, as you've pointed out).

That said, I'm not sure it makes sense to rewrite "everything" in Rust, but it would be nice to see one or two representatives of each thing in rust, so you can rely on the assurances Rust provides as much as possible as far down the stack as you can, if that's desired. In other words, I don't think we need every compression library ported to Rust, but I would like to see one or two choices for each type of compression, as applicable. An easy way to jump-start this is to take a library and port it.


1. We are not talking about code that is under heavy development. I specifically said that rewriting code may be sensible if you intend to make big changes.

2. Obviously, verification tools (and I'm not just talking about static analysis, but also whitebox fuzzing and concolic testing) do have their downside. The question is not which approach yields the best overall result, but which is more economically sensible given the goal.

> it would be nice to see one or two representatives of each thing in rust

Absolutely, as long as it's done while analyzing the cost vs. benefit. What isn't so nice is to have the software industry waste precious efforts rewriting instead of developing new software, without analyzing where a rewrite would yield the most benefit. Obviously, anyone is free to choose what they want to spend their time on, but I think that as an industry we should at least encourage projects with higher impact first.


> What isn't so nice is to have the software industry waste precious efforts rewriting instead of developing new software, without analyzing where a rewrite would yield the most benefit.

That's entirely subjective based on how short-term and long term your thinking is, and whether you think C will still be the dominant language for some things in 10 or 20 years.

I think C is a local maximum, it's already surpassed its limits as a language (as we're now talking about extra-language tools to enforce non-language constraints), and is approaching its potential limits. We can put X time in making it slightly better, and get closer to the asymptotic limit of C's capabilities, or we can spend some (small) multiple of that time to reimplement in something that is by its nature slightly more capable immediately, and with possibly much more future potential.

Fixing up the old Pinto year after year because it still works and gets you from here to there always looks like a good decision when you are just looking at your monthly outlay. But when you consider environmental impact, safety to yourself and those around you, and comfort, spending that extra money to get the new Focus starts to look really appealing. Sure, look at all that money you're throwing out by buying a newer car, but it's a fallacy to think you got nothing for it, and would have been just as well served by the Pinto. You mght have been, or tomorrow might have been the day you got in an accident. What would you rather be driving when that happens?

Note: This doesn't really mean that Rust needs to be the next thing, but I do think it's a fallacy to look purely and time spent when considering language rewrites, where there are so many important factors that ignores.


But you don't need to fix anything year after year. You only need to fix each bug once. If you decide to significantly modify the code or add new features -- by all means, rewrite if you think it's worth it. But correct untouched code is correct regardless of the language used to write it. And this is what we're talking about here: mostly untouched code. The limits of C as a language are entirely irrelevant, as the vast majority of this code interests us mostly in its machine representation. It's not under heavy development, so who cares what language it's written in if it's correct? And even if you do care, do you care enough to invest so much money to that particular end, money that could be invested elsewhere?

Do you honestly think that the benefits of rewriting mostly correct, mostly untouched code in a new language is the best use of those resources? Do you even think that's the most cost-effective way of catching bugs (if so, I don't think you're aware of the capabilities of modern verification tools)?

> or we can spend some (small) multiple of that time to reimplement in something that is by its nature slightly more capable immediately, and with possibly much more future potential.

I think we're talking about at least a 10x larger effort, possibly 100x, but we won't know until we measure the correctness of said code to the best of our abilities using tools that can approximately do that rather effectively.

> as we're now talking about extra-language tools to enforce non-language constraints

External tools are always necessary if you want to improve correctness, regardless of the language you use. Rust (and virtually every industry language out there) cannot prove most interesting functional properties, either.


> But you don't need to fix anything year after year. You only need to fix each bug once.

I was talking at a language meta-level, not for a particular program.

> But correct untouched code is correct regardless of the language used to write it.

A tautology, but largely irrelevant to the discussion, as if we could easily determine correct for anything other than the most trivial code, then this would be a non-issue. In practice, C has ended up being a poor choice for attempting to write correct code, as evidenced by the last few decades.

> Do you honestly think that the benefits of rewriting mostly correct, mostly untouched code in a new language is the best use of those resources? Do you even think that's the most cost-effective way of catching bugs (if so, I don't think you're aware of the capabilities of modern verification tools)?

The good thing is it doesn't matter. If it's done a little, and seems effective and is prized by users (users being both developers and end users), then it will happen. There isn't some central authority of programming that we need to make a case to, there's a free market to feel around the edges of the problem, and emergent behavior to actually make a choice. The good thing is that I think on average it's a few magnitudes more likely to make a good choice than anyone here as to what's the more useful and effective way to move forward.

> I think we're talking about at least a 10x larger effort, possibly 100x, but we won't know until we measure the correctness of said code to the best of our abilities using tools that can approximately do that rather effectively.

I don't think it's anywhere near that high, given the level both languages operate and and the similarity of the syntax. I think you would only approach those levels for more complex and esoteric pointer use, for small subsets of the code base, and we aren't measuring compared to rewriting in a language with the exact same capabilities, we're measuring compared to C with special analyzers and techniques used to reduce or remove problems, which I though would more than likely require a rewrite of those sections anyway to see any benefit.

> External tools are always necessary if you want to improve correctness, regardless of the language you use. Rust (and virtually every industry language out there) cannot prove most interesting functional properties, either.

That is easily proven false. Rust can be seen as a language that does not enforce memory correctness with a memory correctness tool bundled into the compiler. All the tools for C could be bundled into the compiler and a new language called Cfoo could be defined by what that supports. Every external tool can be bundled into the compiler (or the runtime, as applicable, by the compiler including it in the generated binary or its existence as part of the VM).

In the end, the same arguments regarding correctness apply to varying degrees to things written in assembly, and even raw machine code. We could be applying varying levels of analysis techniques to our assembly at this point, but a shift happened in the past when people saw languages that provided enough benefits that they saw the point of switching. That we mostly settled on C and haven't moved past it yet (depending on how much you consider C++ a C, and how incremental you see the changes) is largely an artifact of momentum, I don't think we should be discouraging people from trying to make that jump out of C for our infrastructure. I think that's the equivalent of you or I sitting in our comfortable homes and offices, carpeted, heated, sturdily built out of wood, steel and concrete, and noting that yes, while the majority of people either work or live in mud huts, it's a waste of resources for them to attempt to replace them with more modern housing when they can just retrofit their mud huts with a heater and portable stove and will be just as "serviceable". The best people to assess whether it's worthwhile or not are those doing the work, not you or I.


> Rust can be seen as a language that does not enforce memory correctness with a memory correctness tool bundled into the compiler.

What you call "memory correctness" is extremely valuable, but isn't correctness (in the software verification sense). Correctness is an external property of an algorithm. There are very few languages that can even express correctness properties. Correctness means something like: "every request will retrieve the relevant user data"; not: "the request will not fail due to a dangling pointer reference".

> I don't think we should be discouraging people from trying to make that jump out of C for our infrastructure

But I'm not discouraging people to move out of the C infrastructure. I want people to write new infrastructure. I just think it's a waste of effort to rewrite old infrastructure in new languages. To use your analogy, people want to rebuild the same mud huts just out of better mud. I say to them: what do you want? Do you want better mud huts? Then reinforce what you have; it will be a lot cheaper. But if you want to build something from scratch, why not build something new? Why spend the development budget on what is essentially maintenance? I don't know if that would be worth it, but at least it seems more worthwhile than re-implementing 1960-70s design with 201x materials, when we can make sure those mud huts stand long enough until we do come up with something new.


> Correctness is an external property of an algorithm.

While true (depending on what you think I meant by correct in that context), it's largely irrelevant to my point. Any external tooling can be merged with the compiler or VM.

> I just think it's a waste of effort to rewrite old infrastructure in new languages.

As you've stated multiple times here. Can I get a few examples of what you mean? I suspect there's a mismatch in our interpretation of the meaning of that statement.

Where does taking a libc implementation and converting with light refactoring fall, given there exists no other implementation in rust?

What about a new libc implementation from scratch in rust, using rust, given that there exist (non-rust) libc implementations?

What about a new libc implementation from scratch in rust, when there exists another rust libc implementation that isn't just a conversion?

What about an SSL library conversion (OpenSSL or NSS)?

What about a new implementation of SSL that conforms to OpenSSL's API?

What about a new implementation of SSL functions that has a completely new API to achieve the same operations?


> Any external tooling can be merged with the compiler or VM.

Not so simple. There is a debate whether it's better to specify correctness in the language or externally.

> Where does taking a libc implementation and converting with light refactoring fall, given there exists no other implementation in rust?

Probably not worth it. But how about writing a Rust standard library in Rust that doesn't implement libc's API?

> What about a new implementation of SSL that conforms to OpenSSL's API?

May be worth it, given OpenSSL's state and importance.

> What about a new implementation of SSL functions that has a completely new API to achieve the same operations?

Go for it!


> Not so simple. There is a debate whether it's better to specify correctness in the language or externally.

What's a benefit of having an external tool for that compared to something built in? Nothing comes to my mind that wouldn't be better handled as a per-location way to turn specific rules on and off (similar to Rust's unsafe blocks).

> Probably not worth it. But how about writing a Rust standard library in Rust that doesn't implement libc's API?

Well, yeah, that would be a good thing, but it's largely irrelevant to my point. In this case libc is just a wildly popular library we are considering presenting a new version of (whether it be largely a "fork" and refactor into rust of an existing one or a new implementation).

> May be worth it, given OpenSSL's state and importance.

Then I don't really think we are in disagreement on the "rewrite everything in rust" stance, as much as how we interpret that statement is different. I take it as far less literal, and more of a shorthand for "let's get rust implementations of critical infrastructure built so we can have some assurance a certain class of bugs can be close to eliminated. If the initial version of that is in some cases a conversion, that's not optimal, but it does provide some benefit, increase the corpus of rust work to refer to, prove rust's capability in the problem space, and provide a springboard for future projects".

That's a far cry from "let's rewrite every line of billions of lines of C code into rust because we want to rewrite it all".


> What's a benefit of having an external tool for that compared to something built in?

Because 1/ building full specification power into the language may make it unnecessarily complex, and 2/ software verification and PL design often progress at different paces, so it's better to have them orthogonal. I

It is unclear how such a language should work, and certainly whether anyone has come up with a decent idea yet. For example, the general dependent type approach used by Coq and Agda (and Idris and ATS) doesn't seem to work well so far for software development. So, perhaps theoretically the two may one day be combined, but we don't know how to do it just yet. You can call it an open research question.


> 1/ building full specification power into the language may make it unnecessarily complex

In that case, I'm not sure how you square the school of thought that you can use these external tools to solve the problems of C, or that it's at least more cost effective than something new, like Rust. If it's unnecessarily complex, does it matter if it's compiler+external tool or compiler+integrated tool? I think the same argument cuts both ways, except that in C it just means the tool won't be used, so the software will be of lower quality.

> 2/ software verification and PL design often progress at different paces, so it's better to have them orthogonal.

Having some verification integrated does not preclude further verification techniques from being developed. Types are a verification technique, and they exist in both C and Rust (at different levels). I'm not sure why it's okay for C to have some included verification, but not for languages to evolve further in this vein.


> If it's unnecessarily complex, does it matter if it's compiler+external tool or compiler+integrated tool? I think the same argument cuts both ways, except that in C it just means the tool won't be used, so the software will be of lower quality.

I'm not arguing in favor of one approach over another. My original point in this thread was solely about legacy codebases that are well-established and are no longer under active development, hence your arguments about enforcements do not apply. Now I'm talking in general. I don't know what you mean by an integrated tool, but there is a difference between making a language able to specify programs (like Idris), which may make it very difficult to use, or using a language that is relatively easy to use, plus a specification language, that's also easy to use.

> I'm not sure why it's okay for C to have some included verification, but not for languages to evolve further in this vein.

Again, my original point was only about codebases that aren't heavily developed, like libc. A language like Rust should and will have external verification tools, too, because its type system isn't powerful enough to specify correctness, and that's a good thing (because we don't yet know how to build friendly type systems that are capable of that). All I said was that if the codebase is huge, and if it is established and largely correct, and if it is no longer being heavily maintained, and if the language has good verification tools, and if there are no tests that will catch new bugs you will introduce in the translation, then it is more effective and far cheaper to use those tools than to rewrite in another language.


I understand your original point (if I still don't agree entirely), I was addressing some topics you brought up as tangents. I understand a language will always develop external tools is used enough, but I don't think that precludes migrating tools that have proved themselves into a language if the trade-off is clearly a good one, or at least a good one for a subset of problems (I think Rust fits this description).

To take a different tack on why I think it's not a waste to focus on rewrites of well established, mature code bases, consider the following: Rust is young. There aren't a lot of projects out there using it (comparatively), and almost none in certain sub-areas where it is supposedly a good fit (low level systems programs). A good way to find pitfalls, develop best practices and idioms, and find the pain points of the language is to use it to reimplement a well known, mature, stable project and see how it turns out.

You can say "sure, but we shouldn't focus on just that!", which is true, but also a non-sequitur, as I'm not sure anyone is actually doing so, or even suggesting it be done exclusively that way. I know what you are arguing, I'm just not sure why you feel the need to argue it, since I don't see anyone actually holding a position opposite you (the "we need to rebuild every project in Rust" view).


> You can do all the analysis you want, and put in all the procedures you want, but in the end people are submitting changes to these libraries, and you need to make sure that these people are ensuring the tools get run prior to release. Additionally

This sounds like a problem that's easily solved with tooling, including continuous integration and mandatory pre-release testing.


Tooling is specifically not the problem. Since you can't enforce the client runs the tooling, you can't ensure the code is actually conformant. You can put policies and tooling in place so that it should be, but there's no way to ensure it. If you're both the developer and the user, sure, you can get pretty close, but what about an open source project that's freely available? You aren't going to get anywhere close to making sure it's tested at most compiles, and if you can't ensure that, you can't really protect against something of someone subverting your tooling, on purpose or accident and getting non-conforming code in the repo.


> You're suggesting that rewriting billions of lines of code that probably contain lots of bugs somewhere every time a new safer language comes along is the most sensible investment of effort by the software industry in order to improve the quality of our software infrastructure

From my own post:

> ... there are a bunch of calls to just rewrite the world in Rust, but even given unlimited resources, is it actually a reasonable thing to do? How well can Rust actually replace C in C’s native domains? What are best practices for managing the risks inherent in a project like that (injecting new bugs/vulnerabilities, missing important edge case functionality, etc.)?

> I don’t really know good answers to these questions...

So I'm not sure exactly where you're getting that argument. This also isn't "every time a new safer language comes along," Rust (AFAIK) is one of very few languages which is generally usable, memory safe, and without a garbage collection.

> ... do you think that "rewrite all legacy code!" (an effort that would probably cost billions of dollars) does not need to be justified by concrete claims about actual cost and benefit?

Absolutely not. But I don't see anywhere that I or others are making that claim. Part of what interests me here is to explore possible avenues of these rewrites.

> so at least we know where the worst of the problem is

I think that CVE's already give us a pretty good idea of places we might start if we were to seriously undertake this endeavor (as opposed to the hobbyist exploration I've started).

> But fine, here's a taste (look for what is required to use the tool as well as results): ...

Some of these look quite promising (and I suspect most on HN are familiar these days with AFL), but the only one which purports to present a cost/benefit analysis or postmortem requires paying $30 for the chapter. I'm not saying that analysis tools are a bad thing (and I would argue are quite badly needed because no matter how badly we want to we could never rewrite "everything" in Rust). I'm not saying that they aren't useful, or that they don't improve existing projects. I'm just saying that I don't yet see evidence that they are strictly always more cost-effective for needed improvements than a safe-language rewrite. I just don't know. I think that the software community barely knows how to properly quantify these things, so it's no surprise that there aren't any good metrics for making these decisions.

> Now, do you have any sources suggesting that a complete rewrite is cost-effective?

It's a small part of what I'm investigating with this project, specifically with regard to Rust. I think that looking into techniques for managing risk in any project (whether the changes are happening due to static analysis warnings or do to a rewrite) is useful.

Although, regarding Rust, one company (MaidSafe, talk about this here: https://www.youtube.com/watch?v=t8z5rA3A1RA) has already reported very promising results from a C++ to Rust rewrite. Dropbox rewrote a core piece of their Magic Pocket infrastructure from Go to Rust to get a handle on memory usage and has also generally reported positive results (wired article: http://www.wired.com/2016/03/epic-story-dropboxs-exodus-amaz..., subsequent HN conversation with Dropbox engineers: https://news.ycombinator.com/item?id=11282948).

All that said, I wouldn't generally advocate for complete ground-up rewrites without an incremental plan. Which is why I'm experimenting with ways to do so successfully and ergonomically between C and Rust.


> From my own post: ...

I acknowledged what you wrote -- and emphatically agreed with it -- in my original comment. I'm not sure what we're arguing about here (I guess I attributed to you something that would disagree with what I had said).

> Rust (AFAIK) is one of very few languages which is generally usable, memory safe, and without a garbage collection.

Similar arguments could have been (and maybe were) made when Ada was introduced, and will be made again if and when ATS or Idris are ever production-quality. Every good new language -- like Rust and like Ada (though I have serious doubts about Idris/ATS) -- improves on its predecessors. But being better -- even much better -- does not imply that a rewrite of legacy code that is not undergoing regular maintenance is the best possible use of resources (even if it were the gold standard, which I'm not sure it is considering the risks involved on top of the effort). I'm convinced that Rust is better than C enough to warrant the effort of switching languages for new code in many, and maybe even most, C shops. But to rewrite legacy code that is not undergoing regular improvement?

> I think that CVE's already give us a pretty good idea of places we might start if we were to seriously undertake this endeavor

Great, then we're in full agreement. My only warning was about deciding to rewrite before weighing alternatives and without having a good handle on precisely where the effort would yield the greatest benefit.

> I'm just saying that I don't yet see evidence that they are strictly always more cost-effective for needed improvements than a safe-language rewrite.

First you need to know what those needed improvements are. Second, some of those tools require very little effort as opposed to a rewrite, which requires a lot of effort, as you pointed out so well. Wouldn't giving them a try first be a more sensible thing to do (if the goal is to improve the quality of legacy code, obviously not if the goal is an experiment in Rust)?

> Although, regarding Rust...

Both of these concern code that is under heavy active development, something that I specifically said may warrant a rewrite (hopefully after weighing alternatives).

> All that said, I wouldn't generally advocate for complete ground-up rewrites without an incremental plan. Which is why I'm experimenting with ways to do so successfully and ergonomically between C and Rust.

Excellent, which is why I agreed with your post and said so. If you want to make your interesting work more impactful on the industry, please keep track of every legacy bug you find in the process, as well as the number of hours you work and how it is broken down to tasks (learning, translating etc.). Such a report could be invaluable.


> It is more "correct" because, while perhaps not providing some of the other benefits, those tools can prove more properties than the Rust type system can

Such as? And in that case, why not lift them into a language type system?

When working on code where particular properties are verified, it's very useful if all the tools share a common understanding of those properties. If you write something in Rust, your IDE will understand the types (and make sure to preserve them when doing automated refactoring), your debugger will know which preconditions were supposed to be semantically impossible, and so on. Last time I looked at external verification tools for C-like languages you often ended up having to explain the same fact twice to two different verification tools with overlapping featuresets, yet alone getting any help from other tools. If we're going to reach critical mass on safety tooling, it will have to be via a commonly understood specification that's a de facto language definition.

So given we're creating a new safe language, what parts of C would we actually want to keep? The lengthy operator precedence table? The preprocessor, and the absence of any module system? The extensive array of language-level operators for doing a wide variety of arcane bit-twiddling operations? The signed/unsigned arithmetic promotion rules that even experts misread? The implicit conversions between arrays and pointers? The lack of any sum (tagged union) type? The for loop that makes arithmetic - or, indeed, arbitrary code - first class, and iterating over an array or other collection something you hand-code every time?

Even if it were as safe as Rust, C would still be harder to read, and harder to write as well. We can and should do better than C.


> And in that case, why not lift them into a language type system?

Easier said than done. First, lifting a new verification property into a type system requires changing the language or creating a new one, so it doesn't solve the problem (another rewrite?). Second, and more fundamentally, some properties cannot always be proven one way or another, but only admit sound classification as yes/no/maybe. Type systems don't usually work well with such properties. There's also the problem of how much of the specification power you want to include in the programming language. More on that below.

> it's very useful if all the tools share a common understanding of those properties.

Sure, but see my response to fpoling.

> it will have to be via a commonly understood specification that's a de facto language definition.

Some such standard or nearly-standard specification languages exist, e.g. JML for Java, and ACSL[1] (inspired JML and supported by frama-C) for C.

> So given we're creating a new safe language

Your new programming language can be whatever you like -- like Rust. The specification language -- for your new or legacy code -- can be rather orthogonal. Even Rust would require a formal specification language for greater correctness, as the language itself cannot specify many interesting properties. Whether, in terms of language design, it's better to unify the specification language and the programming language (as, say, Idris aims to do) or keep them separate is subject to a heated debate (dating all the way back to Dijkstra and Milner). Obviously, if the specification could be unified with the language without it having any negative effect, then that's something desirable; the problem is that many people believe that no such language (or even an idea for one) has been conceived of just yet.

> Even if it were as safe as Rust, C would still be harder to read, and harder to write as well. We can and should do better than C.

Oh, absolutely! I'm all in favor of using Rust over C! But that doesn't mean that rewriting existing code in C is worthwhile in terms of cost-benefit, if your goal is to increase correctness.

[1]: http://frama-c.com/acsl.html


> First, lifting a new verification property into a type system requires changing the language or creating a new one, so it doesn't solve the problem (another rewrite?).

Much of the value in using type systems is that, precisely because they're limited, they force you to write programs whose proofs of correctness would be simpler than if you didn't follow a type discipline. This is true even if you use an external logic for reasoning about your program.

In a language like Rust, I can often arrange things so that the burden of verification is split between type checking and simple high-school algebra calculations. What do I get in C? Gigantic yet intricate state spaces, which need to be split into subsets either manually or mechanically using who knows what heuristics. These subsets are in turn described by formulas containing lots of nested quantification, which is a lot more difficult for humans to deal with than just algebra.

> Second, and more fundamentally, some properties cannot always be proven one way or another, but only admit sound classification as yes/no/maybe. Type systems don't usually work well with such properties.

Type systems err on the side of safety: if no typing derivation can be constructed for your program, your program is wrong, even if your evaluation rules are untyped and your program wouldn't get stuck under them.

> Even Rust would require a formal specification language for greater correctness

This means nothing. Correctness is a binary question: your program is either right or wrong...

> as the language itself cannot specify many interesting properties.

... regardless of whether you've mechanically verified it or not.

> Whether, in terms of language design, it's better to unify the specification language and the programming language (as, say, Idris aims to do) or keep them separate is subject to a heated debate (dating all the way back to Dijkstra and Milner).

It's ultimately a matter of ergonomics, and there's a big continuum in between “prove everything internally” and “prove everything externally”. Rust sits very comfortably at some point in the middle.


My response to Imm was about something a little different from my original point, which is this: Rust is absolutely amazing; I love it! It is leaps and bounds better than C! Yet none of that makes rewriting every line of C out there in Rust the most cost-effective way of improving software quality.


> Yet none of that makes rewriting every line of C out there in Rust the most cost-effective way of improving software quality.

What I know not to be cost-effective in the long run is working around C's inability to enforce its own abstractions. Anything that makes abstractions easier to protect is an improvement over what we have now.


> working around C's inability to enforce its own abstractions

But you don't need to. We are talking about rewriting internal code that no one intends to touch, not about improving APIs.

> Anything that makes abstractions easier to protect is an improvement over what we have now.

Sure, so wrap C code with Rust. That's a whole other matter than rewriting it.


> But you don't need to. We are talking about rewriting internal code that no one intends to touch, not about improving APIs.

But it has to be touched, because it contains mistakes!

> Sure, so wrap C code with Rust. That's a whole other matter than rewriting it.

Reimplementing things in Rust from scratch has an important advantage: abstractions can be redesigned to maximize the extent to which the contract between API implementors and users is captured in types.


> But it has to be touched, because it contains mistakes!

Sure, but where exactly? Is manual translation into another language the best bang-for-the-buck approach you know for finding bugs?

> Reimplementing things in Rust from scratch has an important advantage

Of course it does! But is it the most cost-effective way to improve vast amounts of legacy code that isn't under active development?

Just for the sake of argument, suppose some 10MLOC (which comprise a minuscule, nearly negligible, portion of all legacy C code) contain, say, 500 serious, dangerous bugs, 450 of them could be fixed in a Rust rewrite that would cost $10M, while, say, 400 of them could be fixed using C tools for the cost of, say $1M. Wouldn't it make much more sense not to do the rewrite for 10x the cost and 12% of added utility? Of course the situation could be much more in favor of Rust or in favor of C, but we don't know! Wouldn't it at least be far more responsible to use tools that would help us know where we stand for relatively little effort before we commit to one approach over the other?


> Just for the sake of argument, suppose some 10MLOC (which comprise a minuscule, nearly negligible, portion of all legacy C code) contain, say, 500 serious, dangerous bugs, 450 of them could be fixed in a Rust rewrite that would cost $10M, while, say, 400 of them could be fixed using C tools for the cost of, say $1M. Wouldn't it make much more sense not to do the rewrite for 10x the cost and 12% of added utility?

I don't think 12% is the right way to think about it. The difference between 100 bugs and 50 bugs is at least as big as the difference between 200 bugs and 100 bugs, probably bigger - at least in terms of how much it costs. Suppose you go for the C approach, but turns out you really do need to get down to 50 outstanding bugs - at that point how much is it going to cost to do that in C? Suppose a year later you need to get down to 25? I think it's very easy to end up in a sunk costs situation where at each step improving the existing codebase is cheaper than rewriting, but overall you end up spending far more.

Maybe we need to focus on migration paths. Maybe strategies like targeted rewrites of critical pieces can offer the same level of incrementalism as improving existing C code, but greater overall efficiency. Or maybe there's just no affordable way to salvage existing legacy codebases. IMO in the coming decades we're going to see attackers reach a level of sophistication where any bug in network-facing code is exploited; at that point more-or-less the only useful code will be (provably) bug-free code. I think the path from legacy C code to bug-free code that goes via rewrite-in-Rust-today is ultimately cheaper than the one that goes via use-tooling-to-improve-the-C-today.

> Is manual translation into another language the best bang-for-the-buck approach you know for finding bugs?

For finding a single bug, no. For finding bugs in bulk, yes (or rather, for reducing the bug rate below a certain threshold, if that required threshold is low enough). I honestly think the costs of translating between languages are very much overestimated - it's much more similar to refactoring code for clarity than it is to writing a program from scratch.

(It doesn't have to be manual - there's no reason you can't do a semi-automated translation in the same way you'd do a semi-automated correctness proof.)


> I think it's very easy to end up in a sunk costs situation where at each step improving the existing codebase is cheaper than rewriting, but overall you end up spending far more.

I don't understand this analysis. First, a fixed bug is a fixed bug. You never ever have to rewrite a function that's correct. Second, the whole point of at least first trying to find the bugs, is that the whole effort is orders of magnitude smaller. Doing the verification step first and the rewrite later is as cheap as just doing the rewrite, if not cheaper (because then you at least know what to rewrite). If a codebase turns out to be broken beyond repair, by all means -- rewrite. But we have no reason to assume that's the case, so why make such a costly assumption?

> at that point more-or-less the only useful code will be (provably) bug-free code

In that case, why translate now? Proving bug-freedom is so hard regardless of the language[1], that translating the code first to Rust saves you very little and is just wasted effort that could have gone into improving formal verification tools.

> For finding bugs in bulk, yes

I must say I'm surprised. With all the automated test-generations and new static analysis tools out there, the first thing you reach for is a manual translation?

> it's much more similar to refactoring code for clarity than it is to writing a program from scratch.

I partly agree, but I think that refactoring largely untouched, largely correct code for clarity is also a waste of (much!) effort.

> It doesn't have to be manual - there's no reason you can't do a semi-automated translation in the same way you'd do a semi-automated correctness proof.

The main reason I can think of is that no such tool currently exists. If it did, it may significantly reduce the cost of translation and change the equation. I'd be very excited to have such a tool, and, in fact, I think creating one is a better investment than starting to manually rewrite old, largely untouched and largely correct code.

[1]: I'm giving a talk about this in July at Curry On: http://curry-on.org/2016/sessions/why-writing-correct-softwa...


> First, a fixed bug is a fixed bug. You never ever have to rewrite a function that's correct. Second, the whole point of at least first trying to find the bugs, is that the whole effort is orders of magnitude smaller. Doing the verification step first and the rewrite later is as cheap as just doing the rewrite, if not cheaper (because then you at least know what to rewrite).

I think that's backwards. If you rewrite in Rust then you probably fix bugs without noticing them. If you verify in C first and then rewrite, you have to redo the verification. If we think of the code we're verifying as data, then it's good practice to spend a bit of time getting the representation of the data right before trying to operate on it - that's usually more efficient than starting operating on it now and then changing the representation later.

> In that case, why translate now? Proving bug-freedom is so hard regardless of the language[1], that translating the code first to Rust saves you very little and is just wasted effort that could have gone into improving formal verification tools.

In the medium term: I think verification is much easier when the code is in a better form. (If nothing else translating to Rust will often give you much more concise code to verify). So as long as you're going to put in enough effort for it to be worth doing the translation, translating then analysing will get you a better return than analysing then translating. (Indeed if you analyse and then translate, a lot of your analysis may need to be redone).

In the longer term: I think we're never going to be able to (affordably) prove (general) C code correct. Which in turn means that any static analysis efforts in C will ultimately be wasted (because whatever partial verification we'll get from them won't carry over through translation of the code, and won't help us to translate it either). Whereas even if we're going to end up having to translate into some post-Rust language (and my suspicion is that we will), I think translating into Rust takes us a valuable distance along that path (because the end target language will look a lot more like Rust than like C).

> With all the automated test-generations and new static analysis tools out there, the first thing you reach for is a manual translation?

Yes. I think translation should be the first resort, because it obviates all the other approaches (if a property is guaranteed by the language then that's better than any amount of test coverage), and because better code makes subsequent analysis easier. (I'm certainly interested in automating it though).

> I partly agree, but I think that refactoring largely untouched, largely correct code for clarity is also a waste of (much!) effort.

There's a huge gap between largely correct and entirely correct. If we believe the latter is what we'll eventually need, then such refactoring is valuable - and if there's other work to be done on the same code, then it's usually cheaper to do that work after the refactoring rather than before. I agree that refactoring not driven by a requirement is a waste, and I think many businesses hold a belief (whether they express it this way or not) that they won't ever need 100% proven correctness. (I disagree because I believe technological and social changes in the near future will radically change the economics of hacking, but that's a fringe position that I don't expect to be able to convince business leaders of).


> then it's good practice to spend a bit of time getting the representation of the data right before trying to operate on it - that's usually more efficient than starting operating on it now and then changing the representation later.

I don't really understand this. The tools work better on C code right now, because some/most of them just don't support Rust at all. It's not a theoretical problem, but a real problem: C has better verification tools than Rust at this time; running many of them is far less costly than a rewrite; ergo -- we should run those tools before we rewrite to guide us as to what, if anything, is worth rewriting.

> I think we're never going to be able to (affordably) prove (general) C code correct.

We are likely to never be able to affordably prove code in any language correct. The math is stacked strongly against us. The verification community works to make some specific properties of some kinds of programs affordable to verify; that's pretty much the best we hope for (and I think that's plenty).

> Yes. I think translation should be the first resort, because it obviates all the other approaches... and because better code makes subsequent analysis easier.

And what if it costs 10-100x as much? Because that is very likely to be the case. But we won't know until we run the tools...


> I don't really understand this. The tools work better on C code right now, because some/most of them just don't support Rust at all. It's not a theoretical problem, but a real problem: C has better verification tools than Rust at this time; running many of them is far less costly than a rewrite; ergo -- we should run those tools before we rewrite to guide us as to what, if anything, is worth rewriting.

> And what if it costs 10-100x as much? Because that is very likely to be the case. But we won't know until we run the tools...

Do you agree that if one believes (as I do) that we'll inevitably need to rewrite sooner or later, then running those C verification tools is a wasted effort? They won't generate results that usefully carry-over post-rewrite, and they're only helpful in determining what to rewrite if there's a possible result that would convince one that code is good enough to be used without rewriting.

If your use case is "we need to cut the defect rate of this C code by 50% as a one-off" then sure, I can see static analysis tools and the like being the cheapest way to achieve that. I'm not convinced that's a realistic use case - the requirements that lead one to want to reduce the defect rate are likely to be recurring. I think it gets exponentially harder to do that in C. (I think it still gets exponentially harder in Rust, but with a smaller base - so an exponentially large advantage from a rewrite in the long run).


> Do you agree that if one believes (as I do) that we'll inevitably need to rewrite sooner or later, then running those C verification tools is a wasted effort?

Yeah. But, the software industry wasn't born yesterday, nor ten years ago nor forty. AFAIK, in the entire history of software (at least since the sixties), a rewriting project of established code of such magnitude has never been done. The Linux kernel (incl. filesystems), common drivers, and the runtime library, plus common libraries would come to about 20-50MLOC (possibly much more). Rewriting it all (forget about Windows and OSX) would cost at least $100M, and would probably last 5-10 years. That does not even include common runtimes that actually run most software today (JVM, Python, etc.). The total cost would probably exceed $1B and, like I said, the software industry has never, to the best of my knowledge, opted for this option before (GNU doesn't count because it was there nearly from the start and the codebases weren't established). So my question is, for that price and that timeframe, wouldn't it be better to build something new? I mean you're missing out on a lot just by not having a Rust API, and since you need to relearn everything, why not redesign while you're at it?


Sure - I suspect we won't rewrite to the same interfaces, but rather rewrite in a looser sense of writing new implementations of the functionality we need. (The most plausible path forward I see is using something like rust to write a bootable hypervisor and a library of low-level functions for use in unikernels). That said a lot of language runtimes rely on libc (often as one of a very small number of dependencies), so I think a port of musl could potentially be valuable.


My recollection of current verification efforts is that the kind of code that's insanely difficult to port is exactly the same kind of code that's basically impossible to verify. People playing games with type punning (technically illegal), or worse yet, stuffing a few bits into pointers or stuffing pointers into doubles are surprisingly common (for efficiency reasons), and that's not going to fly with most verifiers.

It's not clear that building verifiers capable of handling the complex C code is any easier than mass rewriting into Rust (or other safe languages), nor that rewriting into more safely-analyzable subsets of C is easier (/more tenable) than into Rust.


First, a rewrite is costly even for simple code, where verification is easier. I don't know what percentage of code that is, but I'd assume not too small.

But even if simple, non-tricky code is the exception, is a rewrite (or verification) really worth it? Maybe in some cases it is, but you'd need to carefully analyze where. A "mass rewrite" is almost always a wasted effort, that would be best put to use elsewhere. Even in writing better tests.


The question is what value do you get from a rewrite. Nearly all post-C languages have strived for eliminating buffer overflows, which produce 80-90% of all security bugs. For string/buffer-laden libraries that get most of their input from the WWW, the value proposition to me seems very high.


Rust -- like any other non-research language -- achieves this particular feature mostly through runtime checks (which, I'd guess, are elided in many circumstances). If you're willing to pay for those, it's much easier to use a C compiler that adds them (and removes them if it can prove they're unnecessary, as I'm sure the Rust compiler does, too). Even adding some of those checks manually is likely a far smaller effort than rewriting everything.

Now, I'm not saying that if you just do that (and not use more powerful verification tools) the result would be as good as rewriting everything in Rust, but the difference would certainly not be worth the cost.

But my main point is this: if the industry decides to make a significant portion of mission-critical C code safer, we should do a careful cost/benefit analysis, and find the best approach to tackle each problem. I'm not saying that manually or automatically injecting overflow checks is what we should do, but I doubt that a wholesale rewrite in any language is the best way to achieve this goal. A complete rewrite of nearly endless code with uneven quality and very partial tests has never been, and likely never will be, a cost-effective or a very productive way of improving its quality (but write your new code in Rust!)


> Rust -- like any other non-research language -- achieves this particular feature mostly through runtime checks

This isn't true, and it's a big part of what makes rust interesting for this kind of work. There are array bounds checks, yes, but only with the indexing operator which is not idiomatic rust (FWIW, Rust has idiomatic iterators which allow LLVM to remove bounds checks at compile time). Nearly all of the other memory safety guarantees are from compile time checks.

It's fine for a general discussion about rewrites to be uninformed about the specifics of the target language, but citing incorrect specifics about a language isn't helping your case.


Yes, I know that, but we are talking about bounds checks! In many places where there is simple iteration, a C compiler would be able to prove no over/underflow, and where the pattern isn't so straightforward, a Rust rewrite would be even more expensive. Now, I don't know how many times I need to say it, but I have no doubts that Rust is "interesting for this kind of work". I absolutely fucking love Rust! I am just seriously questioning the economic sense of rewriting every piece of legacy code out there (billions of LOC!) whenever a new language comes along in an effort to improve its safety/correctness just because we know that there are probably lots of bugs in there somewhere. Draining the ocean with a spoon is guaranteed to find every piece of sunken treasure, but it's probably not the approach with the greatest bang-for-the-buck.

What would you say if in ten years people would say, "Ugh, Rust?! That hardly guarantees any interesting properties. Fine, it ensures there are no data races and dangling pointers, but does it make sure the library/program does what they're supposed to? Let's rewrite every line of code out there in Idris or ATS! That would be the best use of our time!" Whenever a library needs to be replaced -- either it doesn't serve modern requirements, it's hard to maintain and needs to undergo changes, or it is simply shown to be broken beyond repair, by all means -- write it in Rust! Gradually, there will be more and more Rust code out there, which is no doubt much better than C code. But a wholesale rewrite?


Bounds checks aren't really about underflow and overflow though? At least not as typically discussed. They're about determining whether the access to array contents is within the predefined region of memory which is covered by the array. And while Rust has bounds checked when directly indexing into an array, idiomatic Rust relies on iterators which have bounds checks that are nearly always removed by LLVM -- generally eliminating the runtime checks you referred to.

> I absolutely fucking love Rust!

Me too!

> I am just seriously questioning the economic sense of rewriting every piece of legacy code out there (billions of LOC!) whenever a new language comes along in an effort to improve its safety/correctness just because we know that there are probably lots of bugs in there somewhere.

Me too!

I don't know anyone who is seriously advocating for "rewrite literally everything in Rust." I use that expression to describe those who specifically call out OpenSSL, glibc, etc. every time a new CVE comes up which requires a fire drill. Rewriting critical infrastructure is very different from "everything," and even then, I've not made any assertion that we should do so. Just that it's worth looking at how we might do so if we choose to, and that it's also useful to have exploratory projects which can discover some of the pitfalls here.

> What would you say if in ten years people would say, "Ugh, Rust?! That hardly guarantees any interesting properties.

That would be absolutely fantastic! Because if that's happening, perhaps Rust will have improved the overall situation and encouraged using better typing guarantees for systems work. If Rust is displaced by a language with better or more interesting safety properties, I will be elated (at least in part because to be displaced, Rust will have to have done OK in the meantime ;) ). But for now, I think it's worth finding out what mileage we can get out of Rust and its various properties and guarantees.

> Whenever a library needs to be replaced -- either it doesn't serve modern requirements, it's hard to maintain and needs to undergo changes, or it is simply shown to be broken beyond repair, by all means -- write it in Rust! Gradually, there will be more and more Rust code out there, which is no doubt much better than C code. But a wholesale rewrite?

So reading over your various responses, I think we're actually in general agreement. Any major change in a project requires careful risk assessment/management and justification. I'm just choosing to spend a small amount of my free time exploring the possibility space of the Rust rewrite process so I can know more (and also learn more about how my OS and most applications work).


> Bounds checks aren't really about underflow and overflow though?

Buffer overflow, is possibly what is being referred to? That's definitely the province of bounds checking.

I don't know anyone who is seriously advocating for "rewrite literally everything in Rust."

Personally, I assumed that was supposed to mean "some critical subset of infrastructure". I'm not sure why pron settled on the particular interpretation they did (everything in the literal sense), but they've been careful to define that over and over in their comments, and very few have bothered to clarify like you have. It's almost enough to make me wonder a bit if the interpretation you and I have is actually the minority and a sizable portion of the rust community, or at least those involved here, actually want it in a literal sense, but I think that would be silly...


> generally eliminating the runtime checks you referred to.

Yes, but I conjecture that this may be largely irrelevant (and would love to hear an explanation of why my conjecture is false) because one of the following is true in a significant enough portion -- if not the majority -- of the cases where this applies, either: 1/ the proof of no overflow could be determined by a C tool (it may not be a 100% proof that works in the face of, say, concurrent modification like Rust can guarantee, but something that's more than good enough), or 2/ making full use of Rust's contribution in that regard would require an API change, which you can't do. In most other cases, utilizing Rust's contribution would require a careful, very expensive study and analysis of the code (if you don't want to introduce new bugs), and so in that case, too, a C rewrite of that particular piece may still end up being cheaper and not (significantly) less useful (as the rewrite would reshape the code in such a way that a C tool would be able to verify its correctness to a sufficient degree).

Remember that proof (and I don't necessarily mean formal proof) that a piece of C code is correct in some specific regard (overflow) is just as much a guarantee as having that property verified by the Rust compiler, and is just as useful if you don't intend to make changes to the code anyway. If you're writing new code, then obviously it's great having the compiler help you, but when seeking to correct bugs in old code, most of it is likely correct, the justification is different.

> I don't know anyone who is seriously advocating for "rewrite literally everything in Rust."

Then why are people arguing? I honestly don't think I wrote anything even slightly contentious in my original comment. I wrote something that I think is pretty obvious (and meant as an emphasis of what you've written in your post; certainly not to express disagreement) yet worth noting on HN, where some people may be too new-language-trigger-happy but may have less experience with legacy code improvement and various (effective!) verification tools, or may be unaware that the majority program-correctness work is done outside the realm of PL design.

Isn't it obvious that before deciding to rewrite large amounts of largely untouched and largely correct legacy code, we should weigh the relative cost and benefit of other approaches, like tools that can help find and fix lots bugs relatively cheaply, and then wrap the thing and forget about it until compelled to rewrite by some critical necessity? It seems like some people disagree, and favor a preemptive rewrite of as much infrastructure code as possible, merely because it's "better".

I admit I made the mistake of mentioning "totally correct" programs that, while true that they are currently more feasible in C than in Rust (thanks to really expensive tools like Why3 or even automatic code extraction from various provers), it is an entirely different and separate issue, one that applies only to a minuscule portion of software.

> Just that it's worth looking at how we might do so if we choose to, and that it's also useful to have exploratory projects which can discover some of the pitfalls here.

Absolutely. You're doing great work, and like I said, I hope you keep track of the effort you spend as well as the number and kind of bugs you find in the process. That would make your work truly invaluable.

> That would be absolutely fantastic! Because if that's happening, perhaps Rust will have improved the overall situation and encouraged using better typing guarantees for systems work.

Hmm, here we may be in disagreement. I think that making types ever more expressive has diminishing returns, and is, in general, not the best we can do in terms of correctness cost-effectiveness; indeed, most efforts in software correctness research look elsewhere. Types have some advantages when expressing more "interesting" program properties and some disadvantages (although I think Rust's borrow checking is some of the most useful use of advanced typing concepts I've seen in many years; I can't say the same about languages designed for industry use that try to employ general dependent types with interactive proofs).

> But for now, I think it's worth finding out what mileage we can get out of Rust and its various properties and guarantees.

I agree, but I believe more benefit will likely be gained by writing new libraries and programs, not from rewriting old ones. I think only concrete absolute necessity should guide any rewriting effort.

> I'm just choosing to spend a small amount of my free time exploring the possibility space of the Rust rewrite process so I can know more (and also learn more about how my OS and most applications work).

Awesome! Carefully collect data! We need it.


> Then why are people arguing? I honestly don't think I wrote anything even slightly contentious in my original comment.

I think your original interpretation was slightly pedantic, and even though, to your credit, you were very careful to repeat your exact phrasing multiple times in many comments, nobody commented on what was likely the crux of the difference (which I have to admit, I'm confuses as to why that was ignored). Should everyprogram be converted? Definitely not. Is conversion even necessarily the goal? I think not. I think the goal is to get a rust representative of each area for promote choice.

It's about trust, and not necessarily how much I trust the specific developer, but that in using a language the requires specific conformance to compile, I can replace some subset of the trust I had to afford to the developer to the tool I use to compile. Do I trust code written by DJB or the OpenBSD developers? Yes. Would I like a way to transfer some amount of that level of trust to the random author of a library on github that would be really useful for my work? Hell yes. Does that replace my need to look for markers, whether in the code or based on project/author status, to determine whether the project and/or developers are competent and trustworthy? No, but it can reduce it.

> I agree, but I believe more benefit will likely be gained by writing new libraries and programs, not from rewriting old ones. I think only concrete absolute necessity should guide any rewriting effort.

Depending on what you mean by "new libraries" (new concepts or new versions?), I don't think that's sufficient. True, most of the real benefit of a rewrite or new implementation of a need won't happen from a language conversion from an existing library, but if it comes down to getting a new (for example) libc and our choice is to convert a small implementation so there's something or to wait for the next project to come along and hope they don't choose C, I'm happy with the conversion for now. If we're lucky, it will also show those about to start on the next libc-like project that Rust is a viable option, so it isn't done in C.


The C language is sufficiently broken that's it really hard to reliably retrofit any type of safety features on top of it. Since people assume that C is portable assembler, they expect it to map very closely to the underlying machine, which makes even specification-permissible changes effectively impossible (good luck getting fat pointers or non-wraparound integer overflow working on real programs!).

The state of the art here for retrofitting C code is ASAN and tools like SoftBound, SAFECode, and baggy bounds, all of which use shadow memory techniques and impose about 100% overhead. And you can't use them simultaneously because there's a conflict on the shadow memory, which makes actually deploying software with security checks enabled impractical if not impossible.

Disclaimer: I've worked on research projects for automatically adding software protections to C/C++ code (albeit for integer overflows, not memory safety).


Once again: we are not talking about the brokenness of C, but about whether rewriting billions of lines of legacy code whenever a safer language comes along because surely it contains bugs is the most economically sensible way to improve software quality.

I am not talking about providing all the benefits a rewrite would, but I am suggesting something that would be orders of magnitude less expensive, and still very effective (and may actually have some benefits that a rewrite won't), with the net result of being an overall more effective strategy (and I am not talking about runtime tools but about whitebox fuzzing, concolic testing and static analysis tools).


> Rust [...] achieves this particular feature mostly through runtime checks

If you do a 1:1 translation then sure. But idiomatic rust probably uses zero-overhead (or very nearly so, I haven't checked in a while) iterators and other higher level constructs that generate extremely efficient code and don't require bounds checks.

You won't see nearly as many "for (size_t i = 0; i < BOUND; i++) { ... array[i] ...}" in Rust, which means even though array bounds checking might be no faster in Rust, the fact that you don't use it as often is a big win.


>A far more feasible approach (though still very expensive) -- and probably a more "correct" one, even theoretically -- is to verify existing C code using some of the many excellent verification tools (from static analysis to white-box fuzzing and concolic testing) that exist for C

When I tried to verify C code (with hoare calculus, by hand) I found that rewriting that code in haskell and proving that to be correct was much easier. As a result i hardly know anything about the complexity of that code, but for me knowing it produces correct results was enough.


> When I tried to verify C code (with hoare calculus, by hand)

That's not the kind of verification I mean (proof of correctness, let alone deductive proof), but rather automated verification of "internal" program properties (aliasing, dangling pointers etc.), similar to those that could be achieved with type systems like those of Rust or Haskell. However, those tools could also prove stronger properties, probably with a bit more effort.

BTW, if you want to fully formally verify the correctness of C code, you don't need to do it by hand. There are tools that can help you (like Why[1] and various source-level model checkers).

[1]: http://why3.lri.fr/


Easy interaction with other languages is a double-edged sword. Too much of foreign calls may lead to unmaintainable code when knowledge of both languages and their libraries is required to even understand what is going on. And of cause, it makes it even harder to use a whole-program static verification as the tool now must understand both languages.


True, but this downside is still orders of magnitude less costly than rewriting "all" widely used C code out there. This is good as a limited exercise to learn the strengths and limitation of a new language, but as a serious undertaking a gross misuse of resources. Besides, by the time it's done, there will be a new language out there, with the same downside you point out. To avoid it, the software industry would basically do nothing but rewrite legacy code over and over.


"No so easy to use" does not mean no re-use. For this reason I really like how Elm interacts with JavaScript. The language requires to define so-called ports that provide explicit bindings to-from JS world. Thus it is not worth the efforts to call into JS function that does some trivial stuff. But interacting with bigger libraries is straightforward. As a big bonus guarantees of Elm's type system survive interaction with those libraries (unless the JS code in those libraries is malicious), so one does no need to know the details of those libraries to reason about Elm code.

Note that from this point of view rewriting C runtime library in Rust is not good as it creates too tight coupling between C and Rust worlds, requiring to write in a rather unnatural style in Rust. Besides, a lot of Musl essentially translates C calls into kernel ones when Rust typesystem brings no advantages.


> A far more feasible approach (though still very expensive) -- and probably a more "correct" one, even theoretically -- is to verify existing C code using some of the many excellent verification tools (from static analysis to white-box fuzzing and concolic testing) that exist for C[1].

Most static analysis tools for C suck:

(0) Few of them are actually sound. An unsound tool is basically worthless if you really want to be sure that your code has no errors.

(1) They suffer from modularity issues. As you say, they rely on analysis of the control flow of the program (abstract interpretation), which means that, more often than not, the different parts of your program end up related by monstrous preconditions and invariants that expose more implementation details than any sensible programmer would like.

(2) Finally, from a purely pragmatic point of view, they impose the burden of “jumping” between more levels of abstraction: C's syntax (which is already two-layered, thanks to the C preprocessor), some hopefully correct formal semantics for C, and whatever concepts (e.g., sets of states characterized by an invariant) that formal semantics is defined in terms of.

With type systems:

(0) We have a methodology (due to Wright and Felleisen) for proving that a language is type safe.

(1) The type system's intrinsic complexity establishes an upper bound on how intricate the interfaces between modules can be.

(2) For the most part, the programming only needs to care about the denotation of syntax in terms very close to the problem domain. The actual boring syntax processing is the type checker's job.

> It is more "correct" because, while perhaps not providing some of the other benefits, those tools can prove more properties than the Rust type system can, and such tools don't (yet) exist for Rust.

Using a single formal system to prove absolutely everything is impractical. Some things are more convenient to enforce mechanically and internally:

(0) Case analysis exhaustiveness: Humans are comically bad at this. OTOH, it's very easy for a type checker to make sure that a pattern matching block has an arm for every constructor of an algebraic data type.

(1) Separation of concerns: Parametric type abstraction guarantees that abstraction clients aren't exposed to the implementor's design choices.

While other things are easier to prove manually and externally:

(0) Equational laws: Not all algebraic theories are decidable, which means that there's no single search procedure that can decide whether a given equation (with all free variables implicitly universally quantified at the beginning) follows from others.

(1) Routine invariants that are obvious by inspection, and would be too burdensome to annotate in the syntax of a program.


I strongly agree with some of the things you say and strongly disagree with others, but we're not here to discuss the relative merits of static analysis (I'm not talking about deductively proving correctness) vs. type systems. We're talking about the relative merits of rewriting each one of the billions of lines of C code out there in Rust vs. using verification tools, in order to increase our confidence in the safety of the code. The argument isn't even about the quality of the result but the cost/benefit of the approach.


> static analysis (I'm not talking about deductively proving correctness)

What else could be the point to static analysis, if not completely ruling out bugs?

> vs. type systems.

Type-checking is a static analysis.

> We're talking about the relative merits of rewriting every line of C code out there in Rust vs. using verification tools,

Where exactly is the merit in deliberately choosing a more complicated approach to ruling out bugs?

> in order to increase our confidence in the safety of the code.

The conceptually simpler the approach, the more confidence one can have in the result.

> The argument isn't even about the quality of the result but the cost/benefit of the approach.

It's precisely in systems software where the cost of bugs is higher than everywhere else. Anything (types or otherwise) that simplifies the reasoning by which bugs can be ruled out in systems software is a strict improvement on the state of the art.


I don't think this is the place to debate verification theory and practice in general (I will be giving a talk about some aspects of the theory of software verification -- those that I've studied, at least -- at the upcoming Curry On conference in July, though not on the programming/spec language debate -- that is more religion than science; if you're interested, I would gladly debate various aspects of software correctness with you there; I think there’s a lot we disagree on). Here I'm talking about something else altogether.


The first example uses a "unsafe" method. I'm not very familiar with rust, but isn't this an inherently "bad thing"?


Not an inherently bad thing, really. The unsafe keyword has two meanings:

1. An unsafe block tells the compiler "trust me, I know this is unsafe and I know how to do it safely"

2. An unsafe function tells the compiler "this is unsafe! it needs to be put inside another unsafe function or an unsafe block"

So an unsafe block essentially terminates an unsafe call chain. There are a bunch of things which are inherently marked as unsafe in Rust, usually because the compiler can't reason about them, like dereferencing a raw pointer as opposed to a borrow-checked Rust reference. That's what calls for an unsafe function in the case of strlen -- to only iterate over the string once we just have to assume that the pointer points to valid memory and is null-terminated, so like a lot of things in C, we just cross our fingers and go for it. The fact that Rust knows this could fail miserably is why it needs to have an unsafe block.


> 1. An unsafe block tells the compiler "trust me, I know this is unsafe and I know how to do it safely"

Right, so aren't you giving up the biggest advantage of Rust, that your code will be safe by virtue of it getting through the Rust compiler's safety checking?


Yes, although there are other advantages to using Rust (about halfway down there's a "What does Rust offer here?" section that discusses in more detail).

Frankly, the POSIX C standard library does not seem to have been designed with safety in mind (I don't think this requires an expert eye to see). So writing it in Rust is going to require a number of compromises on Rust's safety.

Also, if I were taking this more seriously, the wildly unsafe Rust code would just be a beach head for a bottom-up conversion of a project. You have a project which uses strlen? Great, now use this Rust version. Now incrementally rewrite the strlen-using code in Rust. Now change strlen to use a Rust CString...and so on. Each time you identify a new module boundary, rewrite its dependencies in Rust, and then consume the module while preserving it's outward facing interfaces.


> Frankly, the POSIX C standard library does not seem to have been designed with safety in mind (I don't think this requires an expert eye to see). So writing it in Rust is going to require a number of compromises on Rust's safety.

That's kind of what I'm getting at. If cstdlib is inherently unsafe, and Rust cstdlib is going to be inherently unsafe, what's the point? Because of some other Rust advantages things may end up safer, but there's a lot to be said for years/decades worth of fixing existing cstdlib implementations such that you can be reasonably sure that most of what's in there is as safe as it's going to get.


The interface will have to be `unsafe`, yes (that is, there are conditions that the code calling the functions must satisfy to avoid memory unsafety), but the internals can control this unsafety and avoid having more: libc's have vulnerabilities that are not caused by their inherently unsafe interface.

The power of Rust is the ability to package up `unsafe`ty behind safe interfaces without adding unnecessary cost, so that most users don't have to be super-careful about avoiding memory corruption. This still works at a low-level like in the implementation of a libc or an operating system[1].

Also, Rust is a more expressive language, which helps avoid bugs (e.g. enums/discriminated unions means the programmer can't accidentally access invalid state), allows writing shared algorithms and data structures efficiently once instead of needing to do the bug-prone task of reimplementing (or taking a performance/safety hit with void*), and, subjectively, may be nicer to read/write .

[1]: http://os.phil-opp.com/modifying-page-tables.html


Security and safety isn't a binary relation, it is a continuum.

I think what you are experiencing is a transitive-covering fallacy. The safeties with which you are speaking aren't the same type or the same units. The argument you making is often made by people on security discussion lists to _prove_ that modifying X to make it more secure is pointless because there is still a small possibility of Y.

> years/decades

How long has MUSL been in development? How many programmers there are in the world?


> How long has MUSL been in development?

A bit more than 5 years. The initial public release was 0.5.0 in February 2011: http://www.musl-libc.org/oldversions.html


  > what's the point?
This is directly discussed in the post, under the "What does Rust offer here?" section.


Your #1 should really say "I know this is safe, but since the compiler can't prove it, you'll have to trust me."

That is, using unsafe doesn't mean you're doing anything unsafe, only that the rust compiler doesn't model why it is safe.


It is not inherently a bad thing. In fact, it's very important for Rust to be able to accomplish its goals. As a systems language, we cannot dictate what we wish the machine to be; it doesn't follow our rules.

Unsafe allows for three things: enable extending Rust's guarantees by allowing for humans to vouch for code, the ability to encapsulate these behaviors into a safe interface for users, and give them clear indicators of what to audit if and when they fail at it :).

It's also worth noting that "unsafe" doesn't mean "anything goes." It enables extra behaviors. Regular old references are still borrow checked inside an unsafe block; unsafe unlocks the ability to dereference a raw pointer. In this case, because you're getting a raw pointer from C, unsafe has to be used: Rust can't know if C is playing by the rules.


> As a systems language, we cannot dictate what we wish the machine to be; it doesn't follow our rules.

Except aborting on OOM. Rust's stdlib can have an opinion about that.


Sure. Our opinion is that we like our decision here.

Luckily, that's only the standard library, not the language. But, I have a feeling we've been down this road before...


All C functions are considered unsafe, because they don't have the Rust safety guarantees. Every function in the normal libc crate is marked unsafe.


When you are dealing with pointers (which is a requirement to implement the API of C's stdlib), you are in unsafe territory.

Fortunately, any user of the C stdlib (including other languages) already expects it to be unsafe.


> Fortunately, any user of the C stdlib (including other languages) already expects it to be unsafe.

Yes, but it may be better to phrase it as "Fortunately, any user of the C stdlib already expects it to be unsafe by the standard and definition Rust uses".

People often have their own idea of what unsafe is, and without making it explicitly clear, you might get people objecting to what is an obviously true statement purely because of a terminology mismatch.


From the article:

> All of these are built with generally pretty unsafe code (not just in unsafe blocks, but using lots of pointer offsets and completely opting out of Rust’s ownership system). That said, Rust has already forced me to clarify a bunch of ambiguous type casts and other interesting things. I like the explicitness it has over the C with regard to integer and pointer types and operations, although I’m sure that is at least in part because I’m not very familiar with C.


[flagged]


So... I wrote this comment on the the rust subreddit in reply to someone else who also had a repo named "rusl" where they were planning to do something similar. Not sure how it's relevant here, though. Also, if you're going to quote me it'd be nice if you mark it as a quote and source it :).


Spammers have been copying comments from other places onto HN lately, presumably to build up karma. We ban such accounts. If anyone notices evidence of this please flag the comments and/or let us know at hn@ycombinator.com.


Is there some market value to HN karma? It's even less useful than gold in an MMO!


Things like downvote and flag privileges would allow botnets to censor HN and spin comment threads their way.




Applications are open for YC Winter 2018

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: