The Rune Programming Language
github.com
github.com
I was like I know C++ and I’ve never heard of MemoryPool.
Turns out that MemoryPool doesn’t exist in <memory>. In the source code they’re talking about it’s an alias to std::pmr::monotonic_buffer_resource.
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
This code, as written, makes left node accesses temporally correlated with other left node accesses (and by symmetry must do the same for right nodes), allowing the caches at all levels to have a higher hit rate. Whether that higher rate is actually attained depends on the architecture, compiler, other running code, linker, and all sorts of other garbage, but it has a lot higher chance of better behavior anyway.
DataDraw runs the depth=21 case (single threaded, -O3) in about 4.6 seconds on my M1. It has the built-in advantage of reusing the table allocations as the database is global and implicit, the indexes being u32 sized. The existing C++g++#7/MemoryPool and Rust#5/bumpalo versions (both array-of-structs) are discarding their allocations on every iteration. Running Rust#5/bumpalo with RAYON_NUM_THREADS=1 runs in about 2.7 seconds. So in addition to the implementation being someone else's and possibly misused LGPL, the claims re the binary tree benchmark are not really made out.
Nevertheless you can very closely approximate in Rust what DataDraw does, without macros or anything else, by creating a single global struct of `slab::Slab`s, inserting a dummy first element, converting the usize keys to NonZeroU32 and using this as your SOA. If you do that, then you get roughly the same perf except that DataDraw isn't doing bounds checks. So the Rust version can do it in about 5.5 seconds vs 4.6. Obviously this can't be parallelised as you're passing a single &mut SOA around or using a thread-local.
I also compared the perf for a `slotmap::SlotMap`. It was about 7 seconds, but it solves the ABA problem with the generational indices, so that may be worth it.
Finally I compared the perf for a global Slab<Node>, i.e. global AOS style, to avoid clouding the AOS results with bumpalo's insane performance. It ran quicker than the global SOA style, in 4.6 seconds, because the overhead of managing two arrays, their separate allocations and their bounds checks was too much for the memory access pattern to do anything, if there indeed was any advantage to it.
Second example is very neat. Actually I thought about using sqlite with tmpfs database for application state. That could be useful for some kinds of applications. That said, using functional API over traditional data structures seems like a traditional and widely accepted approach. Interesting to see where that experiment will go.
The example doesn't spell this out explicitly, but I think those are the semantics of secret.
There are plenty of other interesting features, such as disallowing conditional branching on the contents of secrets, all the way down to enforcing Spectre and Meltdown mitigations around secrets without necessarily globally taking that performance hit on sensitive and non-sensitive data alike.
Spectre/Meltdown mitigation is a great example of the latter. The compiler can be careful to emit instructions that don't permit speculative branching, or disable other optimizations that might expose a security risk. Libraries don't typically get the kind of access that would permit them to do that, and it's not clear to me that a language that does permit such access would be appropriate for safety- or security-critical applications.
As for why if statements are a security risk, they give a tidy little example of that at the bottom of their overview page, under the heading, "Can you see the security flaw in this code?" I can't say I understand it terribly well. I personally take that as a sign that, while I can speculate about why they're doing things this way, and even be arrogant enough to do so in public on the Internet, I'm very, very, very far from being qualified to suggest that their basic approach is wrong. Chesterton's Fence sometimes strikes me as being overblown, but Chesterton's Safety Belt is no joke.
x^2 means x squared, orphaning the XOR operator. Rune is for crypto, so math comes first.
https://github.com/google/rune/blob/main/bootstrap/database/...
That innovation does seem like a potential footgun.
Unicode, OTOH, doesn’t have this problem.
Rationale: in normal usage, short-circuiting logical operators are, in effect, a special kind of control flow statement, and control flow statements are typically spelled out. Bitwise operators are more unequivocally meant for calculation, and therefore perhaps more deserving of similar syntax to the arithmetic operators, despite their less frequent usage.
I think that this way of drawing the distinction might be particularly relevant in a language that disallows conditional branching - and, by extension, short-circuiting logical operations - on certain kinds of data the way Rune does.
With a strong type system, it knows if the input is bool or integer
But hey, if Google says math comes first...
It would've been wiser to duplicate C's bit operators ( ~ ^ & | << >> ) than give the emperor some "new clothes."
Welcome to another "Not Invented Here" language dying to be special and full of surprises. It's a fail.
I'm not convinced that implicit nullability is a good idea, either in SQL or in newly designed languages.
I don't see the connection between implicit nullability and SoA. If you have a link to some example, that would be interesting to read.
As for SoA, I'm thinking of two relatively new formats and applications that have default nullable types, are SoA, and are specifically targeting memory intensive applications: apache arrow and duckdb, both seeing some success and well deserved hype
https://www.infoq.com/presentations/Null-References-The-Bill...
TT
// lib.h
struct SecureString {
uint8_t *content;
size_t len;
}
bool secure_str_eq(l *SecureString, r *SecureString) {
// some constant-time algorithm
}
SecureString *new_secur_string() {
struct SecureString *s = malloc(sizeof(struct SecureString));
// initialize s
return s;
}
// #include "lib.h"
import "C"
type SecureString struct {
ptr *C.struct_SecureString
}
func NewSecureString() *SecureString {
return &SecureString {
ptr: C.new_secure_string(),
}
}
func (s *SecureString) Eq(other SecureString*) bool {
return C.secure_str_eq(h.ptr, other.ptr)
}Also how do you even operate on a SecureUserCreatedStructuredData that is serialized into a SecureString or SecureBytes?
Does my function that operates on a SecureUserCreatedStructureData take in a SecureString, which is documented as needing to be deserializable to a SecureUserCreatedStructureData? If so, that's just a secure void*, with all the problems void* has, and slower.
Uses LLVM for execution.
Parsers are Lex and Yacc.
Hand-coded parser-lexers are far more powerful because their diagnostics are useful and are much easier to maintain.
Lex/yacc / flex/bison products by contrast have awful diagnostics and become steaming piles of confusion that have to be rewritten.
The main point of the discussed project is to alter data structure to be more CPU cache friendly and thus try to be faster than C++. The paradigm.
From https://github.com/google/rune/blob/main/benchmarks/mandelbr...
for k = 0u32, k < 8u32, k += 1 {
cr0[k] = 2.0 * <f64>(8 * x + k) / <f64>width - 1.5;
}It's slot-based, vaguely like Python, and has reference-counting GC, like Python. That's how I understand it.
Also, memory-safe and blazingly fast in certain circumstances. Not complete though, some tests currently fail.
Then why is it under github.com/google ?
Oh good, maybe it’ll be here a while.
do {
c = getNextChar()
} while c != ‘\0’ {
processChar(c)
}
loop {
c = getNextChar()
break if c == ‘\0’
processChar(c)
}
Edit: I had to correct my post because Tabs were used in the original, so alignment was all wrong.
I don't want to make too much hay about my challenges because I'm not sure they realistically qualify as a disability. But my own meager experience in this department does demonstrate to me first-hand that "it would be nice if accessibility affordances were optional" largely defeats the purpose of accessibility.
if a == b {
do this
} else {
do that
}"Assume the attacker can tell how long it takes for mac == computedMac to run. If the first byte of an attacker-chosen mac is wrong for the attacker-chosen message, the loop terminates after just one comparison. With 256 attempts, the attacker can find the first byte of the expected MAC for the attacker-controlled message. Repeating this process, the attacker can forge an entire MAC."
How precisely should an attacker guess how long the comparison runs?
This is white-box security, a hypothetical setting where we assume the attacker has access to the entire knowledge of the system and to every oracle they want (like an oracle telling them how much time each function takes), but don't know any secret, like private or symmetrical keys. If you can prove that your function is secure in that setting, then it's secure in real-case situations where the attacker knows even less.
For the normal way to safely compare MAC values, see for example: https://docs.python.org/3/library/hmac.html#hmac.compare_dig...
byte [32] (actualMac, expectedMac)
for int x = 0..31
if (actualMac[x] != expectedMac[x])
return false;
fi
end
return true;
This is why we should check the arrays in constant time - compare every byte in both arrays before returning. We do not return early so we can’t leak information
Also ignoring the fact that calling constant_strcompare(string, string) instead of strcompare(string, string) when working with secrets isn't that big of an ask.
why is it called constant time if it isn't constant with respect to array length? Just seems confusing because the algorithm is linear without a short circuit
What's even more confusing is that it is also constant time in the complexity analysis sense given that the mac is usually a fixed-size string after choosing a hashing algorithm.
Many current memcmp implementations use such large comparisons because they avoid hard-to-predict data-dependent branches for extracting the specific point of mismatch.
(Note that Java’s MessageDigest.isEqual has been constant time since shortly after that article and you should use it rather than writing your own in Java).
You're asking a different question, though. You're asking about precision.
The answer here is that in many cases timing attacks pose a theoretical risk, but they can't be exploited in practice due to a low signal-to-noise ratio.
It really depends on the attack vector.
Measuring the latency of a network call (TCP) from across the other side of the world, as an example, is going to be too noisy (in many cases). Especially if the attacker wants to remain covert.
timing safe means always using the full loop and not branching away on certain values. every value needs the same time.
The former is trivial to implement in Rust and C++, the latter is a bit more complicated, but also implementable in both via macros, in a reasonably ergonomic way.
What is the advantage then?
For example, in D you can write a container that automatically switches from AoS to SoA but most benchmarks are just copy-pasted C++
Very interested in trying seeing how it's 'SOA memory management' turns out in practice.
I think when Carbon came out people's reaction was stronger than deserved (like saying that Google don't believe in Rust, or that Go has been a failure because it hasn't replaced C++ etc.) while in reality all of this is very experimental and very early in its development. I kind of expect similar reactions to Rune and Mangle with some people trying to make a big deal out of nothing.
"Hey I built a thing, let's toss it over the wall but let people know what not to expect" is a perfectly fine thing for anybody to do.
Since Google owns the copyright it almost makes sense.
Also, being in the Google organization doesn't mean that Google is involved in it. I'm maintaining a project there (`google/double-conversion`), despite not having worked for Google for years. Nobody at Google has any influence or reviews on that project.
And Google is not really known to release high quality projects overall. Only some of them are.
> Users of Rune are protected, because the compiler sees that macSecret is secret, and thus the result of hmacSha256 is secret. The string comparison operator, when either operand is secret, will run in constant time, revealing no timing information to the attacker. Care must still be taken in Rune, but many common mistakes like this are detected by the compiler, and either fixed or flagged as an error.
Then define the equals operator for "secret" to behave in the needed way.
The advantages of monads include exactly the opposite decoupling: the hmac algorithm implementation is true to its bare specification, and it is the context that changes some of its behavior.
Also, I can't overload return values on their own in C++, I would have to overload the whole signature. In fact, to get the same monadic result, I need 2^n-1 overloads for a function with n arguments (one for each subset of the arguments except the empty one).
Of course monads' advantages can be coded directly, just as functions can be coded directly in assembly. Personally I code in C++, so I've never used proper monads, but I see where they save work.
I can do this, sure, and if I forget then I'll have a security bug. This is similar to the situation with c++ destructors over c's manual malloc+free. If you're happy freeing at every function's end, then this secrets thing adds nothing for you, and that's cool. It's your own choice what language to use.
That's nice to see they went with C
I like the syntax
They should be more careful picking the name.
There is nothing nefarious here. There is no cabal. These things happen all the time. I've had it happen to two of my own small/obscure projects. It happens.
Perhaps Google as an employer shouldn't allow employees to choose any name they like, and do some diligence to avoid name clashes. This may sound quite reasonable for outsiders, but internally this will be another step that requires manual review in the process of publishing open source code, and employees will see this as red tape and get discouraged from open sourcing their code in the first place.
The benefit of requiring every project to go through a name clash review is also questionable: there are 2.5k repos under https://github.com/google, and most of the them will never become popular enough for name clashes to be a problem anyway. This repo only has 177 stars despite hitting HN homepage.
IMO Google should instead make it easy for people to publish their open source code wherever they like, but I suppose there are some messy legal reasons why they prefer employees to put their repos under https://github.com/google. (It's not a hard requirement, but they do make you jump through extra hoops to open source your code elsewhere.)
(I'm a Google employee, but I didn't know this project and don't work for the department responsible for the process of open sourcing code.)
Now perl stealing prolog's file extension on the other hand...
But in the spirit of being real: what are you trying to do by calling the Rune devs "a couple of hobbyists"? Is that an attempt to minimize them, as if they are not a corporation therefore they don't have any naming rights to their projects? "A couple hobbyists" are how many great language you know and love started out. Their rights are important too. We don't want the norm to be big corporations snuffing out hobbyist projects by making them unsearchable, like Google did to Go!. That's bad for everyone.
This is the kind of disrespect that pushed people to create trademark laws.
(By the way, the reverse scenario here should be okay, too. If Google makes a project with with a common noun name, then others should be able to use that noun to name their projects.)
No, I’m saying that nobody has “claim over the name”. Naming collisions happen all the time, and I don’t know why we get so bent out of shape about it. There are two multibillion-dollar software companies called Epic. There are a million businesses called AAA. I’ve been to three different breakfast restaurants called Sunrise.
For a language dev, the name of the language is all you really own about it. These days, developers expect their languages and tools to be free, and of course open source and permissively licensed. The name and logo of the language is really the only IP most PL devs actually fully control, and costs actual money and time to maintain (registering and defending trademarks, domains, etc.)
To just step on names like Google has repeatedly done shows a crass disregard for what independent language devs go through.
Google isn't exactly innovative with their naming: Fuchsia, Dart, Pixel, Go, Drive, Ara, ... Aside from rare short-term experiments like Stadia everything outside a basic dictionary should be safe.
I'm not going to defend Google, but this specific case isn't one that I'd lose my mind over.
The first settler? The first settler that held it for at least a year, 10 or 100? The most powerful entity claiming it?
In the modern western mind there is the notion that whoever grabs it first rightfully owns it. Which is a simple rule, but encourages squatting and holding but not using. The squatter can then hold ransom against somebody who would be the rightful owner.
At least with patents or electromagnetic spectrum there is a time of expiration. You come first and claim it for a few years after which it becomes public domain. Or we hold an auction each 5 years to maintain stable and efficient allocation of a finite and scarce resource.
With concepts like programming languages, the case with stronger base wins, like in the example of Go. People associate the Go label with Pike's Golang, not with the previous Go!.
It used to be that if you have lived on the land for 3 generations it's yours.
A programming language is such a common personal project, it’s inevitable to not see this happen. It also doesn’t help that 95% of these languages aren’t known.
In most languages, a similar implementation of checkMac would not pass the test, because they will usually implement some sort of short-circuiting. Which essentially means that checkMac will take longer to execute the closer you get to the true mac of that message.
Let's say computeMac(secret, "a") == "a21a". The attacker could pass in message="a" mac="0000" at first. Let's say that takes 1 unit of time, because "0000" == "a21a" only has to look at the first character. So the attacker knows that 0 is wrong. They then try "1000", then "2000", up until they get to "a000". Then, the algorithm takes 2 units of time, the first one is comparing '0' == 'a' and the second one is '0' == '2'. Now the attacker knows the first character of the mac. They keep going like this until they find out the entire mac of the message. In a nutshell, the time the function takes to execute leaks informartion that an attacker could use.
In this language, when you do use the secret(string) type, it will always compare all the characters of the string, even after it knows it will be false anwyay, just to make sure no information is leaked.
Edit: ^ the above had the wrong tone. Thanks to dang for pointing it out. What I meant to express was that it's possible to accomplish a similar safety/ergonomics at the library level in rust in not too many SLOC. My personal preference is towards Rust's approach because the type system gives really powerful composable primitives which makes it possible to have the compiler check a wide range of invariants, instead of just the ones that are common/special enough to go into the language itself
(Example edited after comments from mumblemumble)
// The struct is public, but the contents are private, meaning you can't directly access the secret once it's inside the struct
pub struct Secret<T>(T);
impl<T> Secret<T> {
// The only public way to access the secret, returns a new secret
pub fn map<U>(&self, func: impl FnOnce(&T) -> U) -> Secret<U> {
Secret(func(&self.0))
}
}
impl<T: AsRef<[u8]>> PartialEq<&[u8]> for Secret<T> {
// == does the correct thing (and only works for types that would make sense (`AsRef<[u8]>`)
fn eq(&self, other: &&[u8]) -> bool {
constant_time_eq(self.0.as_ref(), other)
}
}
/* Some other file */
use secret::Secret;
// Translated from the example
fn check_mac<T: AsRef<[u8]>>(mac_secret: Secret<T>, message: &[u8], mac: &[u8]) -> bool {
// This returns a new Secret<[u8; 32]>
let computed_mac = mac_secret.map(|secret| hmac_sha_256(secret.as_ref(), message));
// This uses the `constant_time_eq` impl from above
computed_mac == mac
}
Edit: mumblemumble helpfully points out I demonstrated this poorly, so I tried to better demostrate what I was going for in this comment https://news.ycombinator.com/item?id=33764037
The Rust code above depends on the programmer to consistently remember to enforce safety, and to do so correctly every time.
Sure, you could probably implement that as a library. But, "We don't see much value in compiler help with this, a combination of libraries and being careful gets the job done," would be a peculiar position for a rustacean to defend.
pub struct Secret<T>(T);
impl<T> Secret<T> {
pub fn map<U>(&self, func: impl FnOnce(&T) -> U) -> Secret<U> {
Secret(func(&self.0))
}
}
impl<T: AsRef<[u8]>> PartialEq<&[u8]> for Secret<T> {
fn eq(&self, other: &&[u8]) -> bool {
constant_time_eq(self.0.as_ref(), other)
}
}
/* Some other file */
use secret::Secret;
// Translated from the example
fn check_mac<T: AsRef<[u8]>>(mac_secret: Secret<T>, message: &[u8], mac: &[u8]) -> bool {
// This returns a new Secret<[u8; 32]>
let computed_mac = mac_secret.map(|secret| hmac_sha_256(secret.as_ref(), message));
// This uses the `constant_time_eq` impl from above
computed_mac == mac
}
I guess my main point is that when you have a instead of having to add new things at the language _level_, if I have something as powerful as the rust type system I can implement the same functionality in not much of code.
"need a Monad" sounds scary but in practice it looks like this
impl<T> Secret<T> {
pub fn map<U>(&self, func: impl FnOnce(&T) -> U) -> Secret<U> {
Secret(func(&self.0))
}
pub fn flat_map<U>(&self, func: impl FnOnce(&T) -> Secret<U>) -> Secret<U> {
func(&self.0)
}
}
impl<T> Secret<T> {
pub unsafe fn reveal(&self) -> &T {
&self.0
}
} func(param1: A, param2: B) -> C
flat_map(secret1, |param1|
map(secret2, |param2|
func(param1, param2)
)
)
do! {
param1 <- secret1;
param2 <- secret2;
Secret(func(param1, param2));
}
func(secret1, secret2)I don't know enough about the subject to really evaluate this in detail, but I am more than willing to at least entertain the notion that the problem space is thorny enough that a language-level solution really can do some things that can't be as effectively accomplished with a library solution. Even in a language with a strong compiler like Rust.
Rune also has an interesting approach to pointer safety that's significantly different from Rust's: https://github.com/google/rune/blob/main/doc/index.md#runes-...
As someone who uses rust, I assume you would prefer the former absolutely.
Don't quite grok why it eliminates the need for ref counting though. Tree structures are fine when you have them, but frequently you don't. The docs claim Rune programmers never write destructors even though there's no GC, so is there no equivalent of RAII? How do you model graphs?
The constant time stuff doesn't matter. Virtually nothing needs to be constant time like that and when it does you're probably writing in assembly anyway.