News for hackers. Stuff that matters.
Re:Ntimed – NTPD replacement by dbaupp on Tuesday December 23, 2014 @12:01AM (#8786843)
Memory safety is a huge problem: every large C++ has vulnerabilities caused by memory safety problems. E.g. web-browsers get pwned because of memory unsafety. Apparently, all (or close to all) critical security bugs in Firefox were problems that Rust compilers will catch. I believe pcwalton went through Mozilla's bugzilla to check this.

In any case, bounds checking is a tiny side street in how Rust ensures memory safety: ownership and lifetimes are the important novel things (lifetimes especially are novel, only research languages have had anything similar until this point, and I don't know if any have had exactly the same system).

In Rust the story is totally settled: in order from most to least preferred/recommended: use references, no pointers, owning pointers and then start thinking about reference counting/other shared ownership.

Rust doesn't solve race conditions: it solves data races, which are also problematic (they cause memory unsafety). It is impossible/very hard to avoid arbitrary race conditions, but data races are the only ones that can cause memory unsafety directly.

Re:Ntimed – NTPD replacement by asveikau on Tuesday December 23, 2014 @10:11AM (#8788397)
> ownership and lifetimes are the important novel things

The first is very clearly a borrowed C++ feature (from RAII and smart pointers). I'm unfamiliar with the 2nd but it sounds like just making the compiler yell at you more when you break scope rules (like C++ will happily let you do with dangling pointers - I will give you that dangling pointers are bad).

> Rust doesn't solve race conditions: it solves data races, which are also problematic (they cause memory unsafety). It is impossible/very hard to avoid arbitrary race conditions, but data races are the only ones that can cause memory unsafety directly.

This sounds like gibberish to me. When I said "race conditions" please read it as "data races". Many of which will not "cause memory unsafety directly". Many of which low-level code such as a kernel will need to not be abstracted from. (Imagine writing a page fault handler in a language that tries to hide data races from you... Doesn't sound like a great idea.)

Re:Ntimed – NTPD replacement by Jweb_Guru on Tuesday December 23, 2014 @12:58PM (#8789209)
Rust doesn't hide data races. It prevents them.

Even the Linux kernel has very, very few intentional data races. Most of them rely on undefined behavior and Linus has complained before about kernel code breaking when GCC actually tries to exploit that behavior. In those rare cases, it is perfectly reasonable to use unsafe code, along with copious comments explaining why it's safe.

You may want to read this article: https://software.intel.com/en-us/blogs/2013/01/06/benign-dat...

Re:Ntimed – NTPD replacement by asveikau on Tuesday December 23, 2014 @02:17PM (#8789693)
I think you misunderstand me. Data races happen a lot in kernel development, yes Linux too, and you need to handle them and keep behavior sane. Take my example of a page fault handler. You need a strategy to account for the cases where another proc faults on the same page being processed. Or if a page is being unmapped and accessed simultaneously, you may let the access through or you may deliver a signal depending on timing. Handling these is a real task and if you are in lala land pretending data races don't happen, good luck.

This, in my opinion, suggests that what I read about Rust makes it sound unsuitable for certain domains where concurrent writes and data races are an inherent fact of the universe, a reality that the language seems to deny and be working against.

(Didn't even mention lock free algorithms, for example I was reading one day about [I think it was] the dentry cache using lock free algorithms... You can bet there is part of that code that yes, expects data races to happen and handles them.)

Re:Ntimed – NTPD replacement by Jweb_Guru on Tuesday December 23, 2014 @02:50PM (#8789844)
Those aren't data races. Page faults are actually synchronized (they block) and the switch to kernel mode is a synchronization point. They are examples of races, but they're not examples of data races.

Just to be completely clear, since we didn't define what we were talking about: a data race exists when there are two or more unsynchronized accesses to the same memory location, at least one of which is a write. What happens when that occurs is undefined behavior in C, whether or not you are writing a kernel. On some hardware the result is totally unusable (the write is corrupted). Additionally, the compiler and (on some architectures) the processor are free to reorder operations such that other threads will see your writes in the wrong order, or not at all.

This is all hardware level, the kernel has to deal with these problems too. The "relaxed" ordering in the C++11 memory model is essentially the lowest guarantee you can do anything useful with (other than have something like a racy counter, where you literally don't care at all what the value is, which is basically the only place the kernel has intentional data races at all). For some architectures and operations it resolves to a noop (relaxed stores and loads on x86, for example, never require additional synchronization beyond what the compiler provides).

The Linux kernel takes advantage of these semantics for lock-free or mostly-lock-free algorithms like RCU. There's a lot of code in those implementations specifically to ensure the correct barriers and orderings are in place so that there can't be data races. There's no reason they couldn't be implemented in Rust, and it would probably be easier since they could rely on LLVM's implementation of fences and so on rather than reimplementing it for each architecture. And if LLVM didn't have what they needed, they could just implement it in inline assembly (which is what kernel developers already do anyway).

Re:Ntimed – NTPD replacement by asveikau on Tuesday December 23, 2014 @04:24PM (#8790311)
My parenthetical remark which started this tangent is that I see people suggesting rust because "it solves race conditions" and when I looked into that claim it looked basically like the compiler enforcing no data sharing. The scheme is unworkable for lots of domains.

If you define data races to not include race conditions that your code is handling (by placement of atomics, fences, locking etc.) then maybe your points make some sense but it is exactly the code handling these that I am saying does not fit with what I have seen rust advocates claim. You have to reason about these things at some level, and what I hear people advocate on hn is to sidestep it all by preventing sharing, which may be a fine idea but doesn't work for everything.

Lastly, in my mind, if your lock free algorithm works by letting the races happen but using the result of an atomic op and/or fences to ensure consistent behavior, I would still call that a (benign) race. That you needed atomics, fences, or compiler hints to get what you want seems orthogonal.

Re:Ntimed – NTPD replacement by Jweb_Guru on Tuesday December 23, 2014 @05:56PM (#8790688)
Rust definitely allows data sharing. It just doesn't allow data races.

> If you define data races to not include race conditions that your code is handling (by placement of atomics, fences, locking etc.) then maybe your points make some sense but it is exactly the code handling these that I am saying does not fit with what I have seen rust advocates claim.

Its actual guarantees for atomics are not very strong and let you handle all of those things in safe code. What's interesting is that it can guarantee correct behavior for types that have more interesting semantics than "a bytestring," like mutexes or smart pointers. The implementations of those things are still unsafe, but you can generally provide a safe API to them, which you can't do in most other languages. This is because Rust has the notion of thread safety built into the language and enforced by the type system. For example, Rust's `shared_ptr` equivalent, `Arc<T>` is defined to be thread safe to share and send to other threads if and only if `T` is also thread safe to share and send to other threads. That doesn't mean you can't build up a safe type from the lower level atomics, or Rust isn't suited for this domain. It means you can write safe APIs in Rust that you can't in C++.

> You have to reason about these things at some level, and what I hear people advocate on hn is to sidestep it all by preventing sharing, which may be a fine idea but doesn't work for everything.

Rust just forces you to do just enough synchronization to not have undefined behavior. It's not a dogmatic language and doesn't believe there is one right way to do concurrency. Channels were just removed from the prelude for precisely that reason--they're not particularly favored over other concurrency mechanisms.

> Lastly, in my mind, if your lock free algorithm works by letting the races happen but using the result of an atomic op and/or fences to ensure consistent behavior, I would still call that a (benign) race. That you needed atomics, fences, or compiler hints to get what you want seems orthogonal.

Data races are well-defined, and what you're describing aren't data races, benign or otherwise. You basically never want data races, just like you basically never to dereference a dangling pointer. Rust prevents things you basically never want, it doesn't prevent writing useful things like lock-free data structures.

Re:Ntimed – NTPD replacement by asveikau on Tuesday December 23, 2014 @06:08PM (#8790735)
> Data races are well-defined, and what you're describing aren't data races, benign or otherwise. You basically never want data races, just like you basically never to dereference a dangling pointer

Lock free algorithms, or even a lock implementation, does not jive with this. You let the race happen, and you safely detect when you lost or won the race, and then you do stuff accordingly. To use your pointer analogy, it's OK to have a stale pointer in RAM or in a register at a moment in time. It's a violation of the invariants to dereference it.

As for the rest, perhaps I have been misinformed or led to some outdated info on rust when I saw things about no sharing. I will be sure to take a look.

Re:Ntimed – NTPD replacement by dbaupp on Tuesday December 23, 2014 @08:22PM (#8791113)
Lock free algorithms have to be careful to avoid dataraces by using the appropriate atomic instructions on the CPU. Using non-atomic instructions is a data race and may mean you incorrectly detect that you won the race (seeing stale data in a CPU cache or somesuch).

A data race is essentially defined as a race condition between reads and writes where at least one of those is non-atomic. Rust's type system allows one to enforce atomicity by default (e.g. using atomic instructions, or wrapping data in a mutex).

Re:Ntimed – NTPD replacement by asveikau on Tuesday December 23, 2014 @09:55PM (#8791347)
Are you assuming that I haven't written these things in real life or something?

I said "safely" detect, so yes, the final observation that you have won or lost the race must come from an atomic op. However, a "data race" susceptible read can totally be part of the process. The most common idiom I have seen for a lock free atomic read-modify-write has been to do an "unsafe" read, then act like it was OK, then issue compare-and-swap to determine if it really was OK and do the write if successful. (A failed compare and swap means you need to re-fetch and try again.) Yes you need to make sure fences are OK and the compiler is not caching/reordering the read and you need to account for the famous "ABA problem", blah blah blah, but it's what people do and I am not making it up for the purposes of an HN discussion.

The typical RISC approach to atomics, load-link/store-conditional, also encourages what I will call "my kind of thinking" on this issue, though it does so with specialized instructions. You do a special read, then you use ordinary non-atomic register operations, then you do the special store which fails when you lose the race. I will give you that these are specialized instructions and not ordinary C assignments but I would suggest looking into them if you have not already, the semantics are very educational. (And they may just convince you that disallowing data races is an overly restrictive thing to do in some scenarios.)

Re:Ntimed – NTPD replacement by dbaupp on Wednesday December 24, 2014 @02:10AM (#8791919)
I was assuming you were talking about the race & detection as e.g.

  // let the "race" happen:
  old = compare_and_swap(some_shared_memory, 1);
  if old == 0 {
      // we won!
  }
This is perfectly valid data-race-free code if the CAS is atomic, but is invalid if the CAS is not (assuming no other memory fences).

But sure, if you're manually fencing then you can have data races that are benign; however, just because something has some relatively rare uses doesn't mean it's wildly unsafe for the general case, and so disallowing by default it helps the correctness of the vast majority of concurrent code.

In any case, Rust allows one to opt-in to that sort of behaviour using `unsafe` locally, e.g. one would use `unsafe` deep in the internals of the implementation of the lock-free data structure and with careful vetting to ensure it's correct, and then all users can benefit with the compiler ensuring concurrency-safety by default.

Rust tries not to completely disallow behaviour, just make memory safety the default. The programmer can override the compiler via `unsafe` if they truly know better.

Re:Ntimed – NTPD replacement by asveikau on Wednesday December 24, 2014 @11:49AM (#8793449)
Other than the address compare and swap takes two operands: expected value and new value. It does an equality check and (if equal) the swap atomically. Therefore the equality check is handy to atomically check if a previous potentially unsafe read is still valid, and if so, set a new value.
Re:Ntimed – NTPD replacement by asveikau on Wednesday December 24, 2014 @02:46PM (#8794251)
Too late to edit the post but maybe some code sample will help illustrate the pattern. I am typing code into a web form so I make no guarantees that it is perfect.

  // Performs some modification on the input.
  extern int f(int);

  volatile int global_var = /* ... */;

  int expected;
  int new; // assuming C and not C++, where "new" is reserved
  do
  {
     // Do a speculative read
     expected = global_var;

     // Make some (non-atomic) modification
     new = f(expected);

     // loop until the speculative read was OK. (won the race)
  } while (compare_and_swap(&global_var, expected, new) != expected);
Re:Ntimed – NTPD replacement by dbaupp on Thursday December 25, 2014 @05:22PM (#8797361)
Whoops, I got the signature of CAS slightly wrong. In any case, I already understood the pattern and understand why it is OK. However, as I said, it is the exception that a data race is OK, which is why Rust disallows them by default (it does not disallow them completely).