SeaHash: A fast, portable hash function in Rust
docs.rs
docs.rs
I wonder how the Rust version compares with plain-jane C.
-Austin (murmurhash guy).
For example, if IV1 and IV2 match and the block pattern is ABCDABCDABCD, then BACDBACDBACD will produce the same hash value.
A minor finalizer change would fix it for any IV (pseudocode as I don't actually know Rust) -
vec[0] ^= diffuse(vec[1]); vec[1] ^= diffuse(vec[0]); vec[2] ^= diffuse(vec[3]); vec[3] ^= diffuse(vec[2]);
u64 result = diffuse(vec[1] ^ diffuse(vec[3]));
that's probably overkill but should work.
The operating mode of this hash is broken by default. The author calls it Merkle-Damgard, but that is not what it is. Merkle-Damgard uses a compression function, whereas what we have here is more like a sponge with full state absorption (you can pretend F(IV ^ m) is a compression function, but it is trivially susceptible to collisions F(IV ^ m) = F(m ^ IV)). Meaning, without a secret IV and some sort of truncation there's no way this mode can be secure, even with an ideal diffuse() function.
> Warning! This is not a cryptographic function, and it certainly should not be used as one.
So the focus here is speed, not resistance to malicious actors attempting to generate collisions.
That said, I haven't really looked into the theory much.
Murmur was notable at the time for its use in Java and Ruby. Ruby has since moved to SipHash-2-4, while Java (OpenJDK) has thrown up its hands in disgust at the problem and created a binary tree fallback mode for its HashMaps[1]. Which at this point I'm pretty confident is the only rigorously correct solution.
Degrading only individual buckets is of course a nice middle ground that avoids harsh discontinuities in performance for slightly bad inputs.
It's technically impossible to declare a hash function used in hash table secure, a countermeasure against DoS attacks. djb made a bad mistake here. You always get seed exposure somehow. It is independent on the hash function. You can always brute-force it.
So java is right. The only countermeasure against collision attacks are fixes in the collision resolution. Adding stronger hash functions only makes the table slower, but not secure. And lot's of prominent hash tables are insecure, since they drank djb's cool aid.
[0] https://docs.rs/crate/seahash/2.0.0/source/src/buffer.rs
Ideally, yes. In practice, maybe. We're probably going to see "unsafe" code that assumes good behavior on the part of the caller. That's a classic problem with APIs.
In this case, the byteorder crate would have been more appropriate than handrolling unsafe code.
That's not at all clear. It's worth looking at unsafe code and asking "why was this necessary"? What couldn't you do within the language? As patterns reoccur, it may become clear what new safe primitives are needed.
C++ is trying to add move semantics via templates, but can't get all the way to Rust's borrow checker that way.
- should be safe in Rust but isn't
- needs /compiler/ support to work well (can't be done cleanly as a library)
- isn't already on the track for implementation (non-lexical lifetimes, SEME regions)
You did mention uninitialized arrays but uninitialized data is inherently unsafe. It's not an operation that can be made safe. Instead, you make it safe by encoding the invariants specific to your use case in your code and creating a safe wrapper -- these invariants differ by use case, so it can't be made a generic operation.
Sure it can. You just need primitives which can be used in asserts such as
is_initialized(tab,i,j)
assert(is_initialized(tab,i,j-1));
... initialize tab[j]
assert(is_initialized(tab,i,j));
Sounds like you're going along the path of a dependent type system (in this specific case)? Yes, that could be done, and would perhaps let you reduce a couple of unsafe blocks in the implementation of Vec and other buffer-based abstractions (but not get rid of all of them).
FWIW there is active work going on for formal verification of Rust (both safe and unsafe code), in the RustBelt project.
In general making unsafe blocks run formal verification would be an interesting thing to do (and would solve this problem completely). I don't think it deserves language support, however (nice-to-have, not must-have). This is a very different goal from your original point of adding a few language features that ease writing lower level abstractions.
--------
Ultimately, you're right. While pcwalton did mention "There's no way to solve that problem without just forbidding unsafe code entirely."; this is a possible alternative -- have language support for scoped formal verification that allows you to use "unsafe" operations safely. I think this is an extreme solution to what I consider to be a mostly nonexistent problem.
For really security sensitive code this would indeed be very useful (and is probably a big motivator behind the RustBelt project). Or just use SPARK or something.
But for most Rust users I think the current system is pretty robust and provides enough primitives to write clean, easy-to-verify abstractions with (verifiable) safe API boundaries. (when I say "verify" here I mean it in the informal sense). I haven't come across unsafe code doing contortions, and I have had the (mis?)fortune of going through a lot of unsafe code. The only rough edges are with FFI, and these are mostly due to a lot of things about unsafe code being underspecified (which don't crop up as often in pure rust unsafe code, but do crop up when you through some C/++ FFI in the mix). There is active work on specifying the exact semantics of unsafe code however, so that should be fixable once it happens.
Although I'm not getting into this dispute, I will add in general that Rust might benefit from such contracts or push-button verification of key properties as deployed successfully in Eiffel, SPARK, Ada 2012, and Perfect Developer. A language subset might be used like in SPARK to allow automated verification of those sections against common types of errors. Three follow-up benefits will be easier changes/integrations in maintenance phase, automated test generation from specs, and aiding dynamic analysis by giving it invariants to look at. Could be optimization benefits but I'm not qualified to say on that. Intuitively seems possible like using minimum-sized, data structure for a number range in spec or type. Stuff like that.
These techniques are really under-utilized despite being proven out many times over in high-reliability products.
In fact it would make it less safe, since we'd be debugging code that emits LLVM IR instead of writing in an actual language.
In these cases you have a choice between inventing a safe language primitive or inventing a safe library primitive. This exists in most cases for seemingly-safe operations, like the byteorder crate in this case.
If it were a language primitive it would be just as trustworthy as the corresponding verified library primitive.
That the byteorder crate exists is irrelevant in as much as this was an example of the urge for premature optimization leading the developer down the wrong path. The same amount of time pondering whether to even bother using a pre-existing library might have been better spent second-guessing the urge to type-pun at all.
Also, looking at the byteorder crate, I wouldn't be surprised if it's even slower than the simpler and correct loop I posted elsethread. read_num_bytes in that create uses copy_nonoverlapping, which I assume is analogous to memcpy in C. That's a very round-a-bout and inefficient way to accomplish the task, and likely patterned after similarly bad C code.
To even make it worthwhile, any byteorder library should provide some kind of iterator interface so that it can maintain alignment state while permitting the loop to be unrolled by the compiler. (And it might require a closure or someway of expanding a block of code inline.) That's probably the only way it could outperform the simple, hand-rolled, endianness- and alignment-neutral solution. But it doesn't provide that kind of interface AFAICT.
It's all sort of ironic, which I suppose was the point upthread--this is an example of the irrational urge for premature optimization and of bad programming idioms being hauled into Rust land completely unhindered by Rust's type safety features. And the better, correct, and likely more performant way of accomplishing this task could have been done just as safely from C as it could from Rust.
It wasn't patterned after any C code. ptr::copy_nonoverlapping doesn't necessarily compile down to memcpy. Namely, concrete sizes are given, so the compiler backend can optimize this down to simple loads and stores on x86, which is probably going to do better than the bit-shifting approach. Namely, loading a little-endian encoded integer on a little-endian architecture should be as simple as a single word-sized load (because the byte swap is unnecessary). It would be interesting to consider whether the safer and more readable bit-shifting approach could be compiled down to the same code, but when I wrote the byteorder crate, this wasn't the case.
This isn't the only place that ptr::copy_nonoverlapping is useful. I used it in my snappy[1] implementation as well, specifically to avoid the overhead of memcpy. To be clear, this wasn't my idea. This is what the C++ Snappy reference implementation does as well. Avoiding memcpys in favor of unaligned loads/stores is a dramatic win. I know this because I tried to write my Snappy implementation without specific unaligned loads/stores, and it performed quite a bit worse. The performance of the Rust implementation is now on par with the C++ implementation. Of course, this is always dealing with raw bytes---there's no type punning here.
ptr::copy_nonoverlapping is a bit generic for this use case. That's why we recently accepted an RFC to add read_unaligned/write_unaligned to the standard library[2]. (Which are implemented via straight-forward calls to ptr::copy_nonoverlapping.)
[1] - https://github.com/BurntSushi/rust-snappy/blob/master/src/de...
[2] - https://github.com/rust-lang/rfcs/blob/master/text/1725-unal...
Namely, concrete sizes are given, so the compiler backend can optimize this down to simple loads and stores, which is going to do better than the bit-shifting approach
FWIW, memcpy can be similarly optimized in C. memcpy -> scalar assignment is an optimization that GCC (and probably clang) performs. But if it can't prove alignment it can't optimize it to a scalar load/store, and alignment typically can't be proven except for small functions where the optimizer can see the definition of the array _and_ can prove any pointer derived from the array is properly aligned. That's generally not the case when juggling user-provided strings because there are too many conditionals between where memcpy is invoked and the origin of the pointer.
Also, as a general rule unaligned loads are slower even on x86, so it often times makes sense to check for alignment regardless, especially to optimize the case of loading a long series of integers. And when performance matters, that's precisely what you want to do if you can. You want to batch load the series of integers because doing operations in batches is the key to performance on any modern processor. Indeed, it's the key to SeaHash as well. And that's what I meant by saying effort and code complexity is better spent refactoring the algorithm at a higher level than trying to micro-optimize such a small operation. And in addition to often reaping much better gains, you often marginalize if not erase any benefit the micro-optimization might had provided. It's beyond dispute that the gains from SeaHash primarily come from how it refactored its inner loop to operate on a 64-bit word instead of 8 8-bit words.
I had edited my comment after-the-fact to include the "on x86" qualification.
> And that's what I meant by saying effort and code complexity is better spent refactoring the algorithm at a higher level than trying to micro-optimize such a small operation.
Your advice is overspecified. If you want to make something faster, then build a benchmark that measures the time you care about and iterate on it. If "micro optimizations" make it faster, then there's nothing wrong with that. I once doubled the throughput of a regex implementation by eliminating a single pointer indirection in the inner loop. It doesn't get any more micro then that, but consumers are no doubt happier with the increased throughput. In general, I find most of your hand waving about performance curious. You seem keen on making a strong assertion about performance, but the standard currency for this sort of thing is benchmarks.
I did all of this with byteorder when I built it years ago. I'll do it again for you.
$ curl -sOL https://gist.github.com/anonymous/042d05e1e480b89434a673b30534efd8/raw/d2c9a4516a57c26da23c8beaffd5ad583da0a889/Cargo.toml
$ curl -sOL https://gist.github.com/anonymous/042d05e1e480b89434a673b30534efd8/raw/d2c9a4516a57c26da23c8beaffd5ad583da0a889/lib.rs
$ RUSTFLAGS="--emit asm" cargo bench
test bit_shifting ... bench: 1,999,496 ns/iter (+/- 53,427)
test type_punning ... bench: 476,105 ns/iter (+/- 11,920)
The benchmark reads 1,000,000 64 bit integers from a buffer in memory and sums them.
Analyzing the hotspots of each benchmark using `perf` is instructive. For type_punning:
$ perf record target/release/deps/benchbytes-a1cc37a72d289957 --bench type_punning
$ perf report
cmpq $7, %rsi
jbe .LBB4_10
movq (%rbx), %rcx
addq (%rcx,%rax), %rdi
addq $8, %rax
addq $-8, %rsi
cmpq %rax, %rdx
ja .LBB4_6
$ perf record target/release/deps/benchbytes-a1cc37a72d289957 --bench bit_shifting
$ perf report
.LBB5_6:
cmpq $7, %rsi
jbe .LBB5_10
movzbl (%rdx,%rbx), %ecx
movzbl 1(%rdx,%rbx), %eax
shlq $8, %rax
orq %rcx, %rax
movzbl 2(%rdx,%rbx), %ecx
shlq $16, %rcx
orq %rax, %rcx
movzbl 3(%rdx,%rbx), %eax
shlq $24, %rax
orq %rcx, %rax
movzbl 4(%rdx,%rbx), %ecx
shlq $32, %rcx
orq %rax, %rcx
movzbl 5(%rdx,%rbx), %eax
shlq $40, %rax
orq %rcx, %rax
movzbl 6(%rdx,%rbx), %ecx
shlq $48, %rcx
movzbl 7(%rdx,%rbx), %edi
shlq $54, %rdi
orq %rcx, %rdi
orq %rax, %rdi
addq %rdi, %r12
addq $8, %rbx
addq $-8, %rsi
cmpq %rbx, %r11
ja .LBB5_6
I could be reasonably accused of micro-optimizing here, but I do feel like reading 1,000,000 integers from a buffer is a pretty generalizable use case, and the performance difference here in particular is especially dramatic. Finding a real world problem that this helps is left as an exercise to the reader. (I've exceeded my time budget for a single HN comment.)
> It's beyond dispute that the gains from SeaHash primarily come from how it refactored its inner loop to operate on a 64-bit word instead of 8 8-bit words.
Do you feel anyone has contested this point? I note your use of the word "primarily." If type punning gives a 10% boost to something that is already fast, do you care? If not, do you think other people might care? If they do, then what exactly is your point again?
Note that I am responding to your criticism of byteorder in particular. I don't really know whether the OP's optimization of reading little-endian integers is actually worth while or not. I would hazard a guess, but would suspend certainty until I saw a benchmark. (And even then, it is so incredibly easy to misunderstand a benchmark.)
Notice how tight this loop is. In particular, we're dealing with a single simple load to read our u64.
Try running the code so that the buffer is dynamically allocated, and so that the first access is unaligned.
Now, I'm not saying that type-punning can't be faster, but to do it properly from a general-purpose library it should be done correctly so that every case is as fast as possible.
Assuming I'm correct and that the modified benchmark sees substantially different results, reimplement byteorder such that it produces the same tight loop even when the data isn't aligned.
I don't think it can be done without modifying the byteorder interface to expose something more iterator-like, because it needs to maintain state across invocations for doing the initial unaligned parse followed by the aligned parse.
If you can get it done in a reasonable amount of time[1], look at the difference between type-punning and byte-loading. I'll bet that relative difference will be much smaller than the difference between the unaligned performance before you refactored the interface, and the unaligned performance after refactoring the interface. In that case my point would stand--the most important part is refactoring code at a higher-level; gains quickly diminish thereafter.
If my argument is over-specified, that's because it's meant as a rule of thumb. Specifying a rule of thumb but then qualifying it with "unless" is counter-productive. For inexperienced engineers "unless" is an excuse to avoid the the rule; for experienced engineers "unless" is implied.
Note that I'm no stranger to optimizing regular expressions. I wrote a library to transform PCREs (specifically, a union of thousands of them, many of which used zero-width assertions that required non-trivial transformations and pre- and post-processing of input) into Ragel+C code and got a >10x improvement over PCRE. After that improvement micro-optimizations were the last thing on our minds. (RE2 couldn't even come close to competing; and unlike re2c, the Ragel-based solution would compile on the order of minutes, not lifetimes.)
We eventually got to >50x improvement by doubling-down on the strategy and paying someone to modify Ragel internally to improve the quality of the transformations.
[1] Doubtful as I bet it's non-trivial and you have much better things to do with your time. But I would very much like to see just benchmarks numbers after making the initial changes--dynamic allocation and unaligned access. I don't have a Rust dev environment. I'll try to do this myself later this week if I can. However, given that I've never written any Rust code whatsoever it'd be helpful if somebody copy+pasted the code to dynamically allocate the buffer. I can probably figure the rest out from there.
It is not statically allocated. The data is on the heap. The give-away is that the data is in a `Vec`, which is always on the heap.
> and so that the first access is unaligned
I modified both benchmarks in this fashion:
let mut sum: u64 = 0;
let mut i = 1;
while i + 8 <= data.len() {
sum += LE::read_u64(&data[i..]);
i += size_of::<u64>();
}
sum
test bit_shifting ... bench: 2,293,921 ns/iter (+/- 65,243)
test type_punning ... bench: 659,350 ns/iter (+/- 15,550)
.LBB4_6:
leaq -8(%rcx), %rdi
cmpq %rdi, %rsi
jb .LBB4_11
cmpq $7, %rax
jbe .LBB4_12
movq (%rbx), %rdi
addq -8(%rdi,%rcx), %rdx
addq $8, %rcx
addq $-8, %rax
cmpq %rsi, %rcx
jbe .LBB4_6
You haven't actually told me what is improper with byteorder. I think that I've demonstrated that type punning is faster than bit-shifts on x86.
You have mentioned other workloads where the bit-shifts may parallelize better. I don't have any data to support or contradict that claim, but if it were true, then I'd expect to see a benchmark. In that case, perhaps there would be good justification for either modifying byteorder or jettisoning it for that particular use case. With that said, the data seems to indicate the the current implementation of byteorder is better than using bit-shifts, at least on x86. If I switched byteorder to bit-shifts and things got slower, I have no doubt that I'd hear from folks whose performance at a higher level was impacted negatively.
> Note that I'm not stranger to optimizing regular expressions. I wrote a library to transform PCREs (specifically, a union of thousands of them, many of which used zero-width assertions that required non-trivial transformations and pre- and post-processing of input) into Ragel+C code and got a >10x improvement over PCRE. After that improvement micro-optimizations were the last thing on our minds. We eventually got to >50x improvement by doubling-down on that strategy and modifying Ragel internally. Much like micro-optimizations RE2 couldn't even come close to competing; and unlike re2c, the Ragel-based solution would compile on the order of minutes, not lifetimes.
My regex example doesn't have anything to do with regexes really. I'm simply pointing out that a micro-optimization can have a large impact, and is therefore probably worth doing. This is in stark contrast to some of your previous comments, which I found particularly strongly worded ("irrational" "premature" "bad" "incorrect"). For example:
> It's all sort of ironic, which I suppose was the point upthread--this is an example of the irrational urge for premature optimization and of bad programming idioms being hauled into Rust land completely unhindered by Rust's type safety features. And the better, correct, and likely more performant way of accomplishing this task could have been done just as safely from C as it could from Rust.
Note that I am not making the argument that one shouldn't do problem-driven optimizations. But if I'm going to maintain general purpose libraries for regexes or integer conversion, then I must work within a limited set of constraints.
(OT: Neither PCRE nor RE2 (nor Rust's regex engine) are built to handle thousands of patterns. You might consider investigating the Hyperscan project, which specializes in that particular use case (but uses finite automata, so you may miss some things from PCRE): https://github.com/01org/hyperscan)
I strongly suspect we don't support enough of this:
> many of which used zero-width assertions that required non-trivial transformations and pre- and post-processing of input
... to really support your use case. But we're interested in the workload, especially as we're looking at extensions to handle more of the zero-width assertion cases. We'll never be able to handle some of them in streaming mode (they break our semantics and the assumption that stream state is a fixed size for a given set of regular expressions).
Can you share anything about what you're doing with zero-width assertions?
I have yet to see any of this.
I have noticed that it's harder to write correct unsafe code when it comes to parallelism and FFI, but parallelism has always been a hard problem and the FFI problems generally come from the fact that you need to know the invariants being upheld on the other end, which is trickier.
But for this kind of unsafe code -- designing (non-parallel) abstractions -- upholding invariants is pretty straightforward.
mem::forget-pocalypse was this. (Rc/Arc, Vec::drain, thread::scoped)
Any UB bug that results from an overflow is kind've implicitly this.
BTreeMap::range still has an UB bug from trusting the caller! I literally asked you to fix it! https://github.com/rust-lang/rust/issues/33197
Bugs happen man.
I would say that this is from a time when the invariants were not understood. In particular, the fact that leaking is safe to do in safe code was not known.
(The invariants are still not completely understood, but there's work to specify that, and IMO they're understood enough to be able to avoid unsafe bugs)
> BTreeMap::range still has an UB bug from trusting the caller!
Fair :) I'd completely forgotten about that one.
Yeah, but it's not like "oh this is an obvious thing to consider trusting the caller about". It's an exceptionally niche problem that you'd only know about if someone told you about it. Especially since a Rust programmer shouldn't be expected to write unsafe code often, if ever!
Similarly: not trusting traits to be implemented correctly. Not trusting closures to not-unwind.
These days I've been writing a lot of unsafe code (for FFI) and I do want to get around to penning a concise guide (or just expanding the nomicon). But I'm mostly waiting for the unsafe code subteam to figure out a couple things before doing this (specifically, the exact boundaries of rust's noalias UB becomes important in FFI and this is not specified yet).
But yeah, it's not necessarily obvious. I'd like to make it easier to get this understanding of unsafe code though.
(I don't have any particular point to make btw. Just sharing thoughts.)
As with all such things, it's harder to enumerate what's in your head :)
This is a misconception.
You can write un-abusable unsafe code pretty easily. There are a couple of invariants that the language requires you to uphold. As long as you uphold them you are fine. If your unsafe code can be broken by external safe code that is a bug in your unsafe code, on par with doing `let p = ptr::null(); print(*p);` in your unsafe code.
It might be nice to factor this out into a separate library, but it's fairly harmless.
Another advantage over C++ is that it's much more clear what code is safe and what isn't, as unsafe code is wrapped in `unsafe` blocks, as you mentioned.
I'm no expert on the topic. IIRC, Rust does not have the same kind/amount of unspecified behavior as C/C++ do.
FYI: This is a "highly optimized version of SeaHash" (see comment in first line) with "optimized" meaning fiddling with raw pointers. You can find a version without any unsafe code is in `reference.rs`. I have no idea how fast the reference implementation is.
I think this code could potentially be refactored with smaller unsafe blocks, if that were a goal.
The benefit in general is present for many reasons, among which is that you still have to opt-in to unsafe{} and SeaHash consumers wouldn't need to in order to leverage these features.
The benefit for SeaHash specifically is that Rust isn't merely a safer language, it's also one with arguably newer/better language features than C++. And it's one that has support for several targets today.
let mut ptr = buf.as_ptr();
let end_ptr = buf.as_ptr().offset(buf.len() as isize & !0x1F) as usize;
while end_ptr > ptr as usize {
a = a ^ read_u64(ptr);
ptr = ptr.offset(8);
b = b ^ read_u64(ptr);
ptr = ptr.offset(8);
c = c ^ read_u64(ptr);
ptr = ptr.offset(8);
d = d ^ read_u64(ptr);
ptr = ptr.offset(8);
....
match excessive {
0 => {},
1...7 => {
a = a ^ read_int(slice::from_raw_parts(ptr as *const u8, excessive));
a = diffuse(a);
},
8 => {
a = a ^ read_u64(ptr);
a = diffuse(a);
},
9...15 => {
a = a ^ read_u64(ptr);
ptr = ptr.offset(8);
excessive = excessive - 8;
....
If Rust let you access a slice of bytes as an slice of ints, alignment and length permitting, the code above could be much more straightforward. That's what I mean about expressive power. The hack to do that used here:
let end_ptr = buf.as_ptr().offset(buf.len() as isize & !0x1F) as usize;
We used to implement things like vectors directly in the compiler, but it was a big headache for no gain. Writing actual code is way easier than writing code to generate LLVM IR.
Anyway, there is a commonly-used crate for this: byteorder. Had I written the library, I would have just used that crate. But it's not a big deal either way.
> Why is there an "isize" (a signed quantity) in there?
Because pointer arithmetic is signed.
> The documentation for Rust's "std::ops::BitAnd" doesn't say what the semantics are for signed numbers
Bitwise operations on signed integers are applied to their twos complement representations.
> What would happen on a 32-bit machine if someone allocated a buffer bigger than 2GB?
It would work.
> Exploitable?
No.
Which libraries? I see very few that do this, and all of them are safe abstractions containing some unsafe code.
You keep repeating this claim but I haven't seen any evidence to back it up.
> If Rust let you access a slice of bytes as an slice of ints, alignment and length permitting, the code above could be much more straightforward. That's what I mean about expressive power. The hack to do that used here:
The byteorder crate lets you do this. Of course, it uses unsafe code, but that's safely encapsulated away (and easy to verify). This crate doesn't use it, but it could. Not every operation needs to be baked into the language semantics.
The Rust core team is relatively relaxed about the community's usage of `unsafe`. I say this because they do not seem to be interested in actively discouraging it's usage. i.e. `unsafe` is discouraged in documentation, not via tools.
"Hey please don't use `unsafe` unless you know what you're doing". Is like writing a comment in Javascript, `function(x /* int */) {`.
Ideally, the usage of `unsafe` should be discouraged by the compiler via friction. The compiler should, at the least, spit out some metrics after a compile cycle about the percentage of `unsafe` lines/instructions. Even more ideal, when the compiler detects an `unsafe` it would pause and ask, "Is Crate Z trusted [y/N]?". Cargo can then make this easy in Cargo.toml.
All of a sudden Crate writers need to think twice about their usage of `unsafe`, will users be willing to trust my code? is using `unsafe` here really worth the risk of adopting fewer users? is there already a library that solves this which is generally trusted?
A tool for tracking unsafe dependencies has been talked about before, though. Sounds like a good idea to me. Like I said I don't think there's a particular need for it, but it would be nice to have.
IMHO any metrics would be gamed and prioritized above actually quality. As actual quality isn't suffering, why add the unsafe metric in at all? Seems like paranoia not born out of experience.
Yeah. Most often in FFI code (when the invariants are much harder to uphold). Rarely when writing unsafe abstractions. The few times I remember this happening with abstractions is due to really old code that broke in a compiler upgrade (pre-1.0).
> IMHO any metrics would be gamed and prioritized above actually quality.
Yeah, there have been discussions in the past about a "safe code" badge for crates and stuff like this, and the conclusion is that it might discourage people from using unsafe code where they actually should be.
I have been bitten by inexplicit casts.
I have been bitten by segfaults.
I have been bitten by poor/no tests.
I have been bitten by mutable containers.
In every case, more constraints and more explicitness have liberated portions of my cognitive load. I've ended up with fewer bugs, more flexibility to play, reduced ramp-up time for new devs, increased speed of iteration. Why would this trend, to add constraints and explicitness, not continue to be beneficial?
P.S. You haven't been bitten by unsafe code, yet, because the people that write Rust, are still builders of the language. It is still in the early adopter stage. Think about Java, which is now predominantly written by users of the language, imagine that for Rust. The teams currently working with Rust, chose to do so as an experiment. They don't have to get a feature out tomorrow, but that will come. Similarly, there isn't "legacy Rust", yet (except in the compiler - which is fine because it is literally maintained by the experts). Is it really worth waiting for crappy code to get written, then re-written, then forgotten and finally broken, and to relive our mistakes, before we fix a predictable problem?
I'm not a Rust user. I've never written a line of Rust code in my life. So my opinion is not worth much. And I'm exaggerating a bit. But still.
I don't think I can explain my real reason for objecting to such a thing; it's more emotional than rational, but at least let me give one rational-sounding example of where I think even you would agree such a policy would backfire.
Some library comes out, becomes fairly popular. Eventually a version 2 is released, but the new version has a few lines of unsafe code, whereas the old one did not. Maybe it's to enable a new feature, or maybe it's for performance. Maybe the author was properly paranoid and did a full-fledged correctness proof that his code had no bugs compared to the documentation, and then verified the proof with several different interactive proof assistants. (This is getting a bit unrealistic, but bear with me for a few more sentences.)
But he now has to rename his crate, instantly making the upgrade process for existing users way more annoying. And to add insult to injury, the new name is wrong! There's nothing unsafe about his code, as far as users are concerned. The only trouble is that the Rust compiler could not prove it safe. As you pointed out yourself, this is not surprising: it can't even cope with a linked list! Sophomores in college implement these things, but the borrow checker can't cope with them. So of course unsafe is needed.
And if version 3 finds a workaround, so that unsafe is no longer needed, do you rename it yet again? People think Java's checked exceptions are annoying, but surely this is far worse?
This is enforced via tools: you have to say 'unsafe' to use something unsafe. That's the speed bump.
In addition, there's a lint that you can on to fail the build if you use `unsafe`. This won't apply to your dependencies, but you can make it apply to your code.
1. Crate discoverability could be improved.
2. He wanted full control of the abstraction.
3. This particular library is just an experiment.
4. ...
Regardless of the reason, the reality is the same, `unsafe` could have been ignored but wasn't. Instead, the path of least resistance was to re-write `unsafe` blocks. IMO, it is not truly "friction"/discouraged if it is also the path of least resistance.
Unless improving the flexibility of the existing abstraction has been explored and deemed infeasible, re-building an abstraction instead of working with the existing abstraction's owner, to improve its flexibility, is taking the path of least resistance.
Probably because they were an experienced dev and are experienced enough with unsafe code to write good unsafe code without worrying about it. It was a minor unsafe operation of which the validity is easily proven. Doesn't really prove that there isn't an aversion to unsafe code in the community.
I would generally put the folks who work on Redox in the bucket of "experienced people who know how to write unsafe code" and am pretty sure that they're more comfortable with writing unsafe code than most. Byteorder is a crate that handles this neatly and well (including endianness and stuff), but for ticki's purposes, really, a simple type pun on integers is not that bad. It's like the left-pad of unsafe code.
This sounds very similar to C or C++ developers who criticize Rust. "Experienced C / C++ developers know what they are doing. Why do we need the borrow checker. In my code, these issues Rust claims to solve haven't been an issue for a decade."
The argument seems a little hypocritical. Anyways, its not a big deal, it just seems like an easy problem to solve today, but a tedious problem to live with tomorrow. I'll stop playing devil's advocate now.
That's not what I'm saying. I'm saying that I can understand why ticki just reimplemented it here; because they are experienced enough to know what they're doing, AND because this isn't a dangerous unsafe operation. The AND is important here. There are a couple of unsafe operations which are basically no big deal, and this is one of them (another is the use of unchecked indexing in some cases).
An inexperienced Rust programmer would generally still avoid unsafe like the plague and ask around before doing this. We get this often enough -- folks asking how to do lower level operations well (and often getting pointed to crates like byteorder).
An experienced Rust programmer knows that this specific operation is trivial enough to not worry that much. I know about byteorder, so I would use it in this case, but if I hadn't I'm pretty sure I wouldn't be too averse to just doing the type pun.
I'm not talking about general unsafe code here. I've seen very experienced Rust programmers ask for help in getting rid of or double-checking unsafe code. I'm talking about this specific instance, and saying that it's not in the category of unsafe code that needs to be worried about.
It is definitely a red flag for a function that just reads some bytes to be entirely wrapped in an unsafe block, and I don't think it makes sense to defend it while also saying that the Rust community discourages gratuitous use of `unsafe`. The whole point of Rust is the "experts know what they're doing" argument doesn't work in practice, and people shouldn't get a free pass for large amounts of seemingly undocumented and unjustified `unsafe` just because they have some prominent projects.
This bothers me about Rust.
There's too much "unsafe" code in libraries.
The language is unable to express some essential concepts.
[1] https://docs.rs/crate/seahash/2.0.0/source/src/buffer.rs
Known areas of trouble include partial initialization of an array, needed to implement growable collections
https://doc.rust-lang.org/std/vec/struct.Vec.html
and single ownership doubly linked lists.
https://doc.rust-lang.org/std/collections/struct.LinkedList....
If Rust let you access a slice of bytes as an slice of ints, alignment and length permitting,
the code above could be much more straightforward.
What would happen on a 32-bit machine if someone allocated a buffer bigger than 2GB? Exploitable?
> The same code the parent poster highlighted [1] is
> undefined behavior in C/C++ (with standard types). So
> really no language has the ability to express those
> concepts. Your doing pointer casts and possibly unaligned
> dereferences at the same time. This has zero consistency
> between CPU vendors.
Moreover, type-punning is generally a warning of bad code in C. Both C and Rust will generally[1] diagnose a type-pun. And you can silence the diagnostic in both languages by using special syntax--unsafe in Rust, a cast in C. But in both cases the way that you silence the warning is over-broad; you often need to silence it for good reason, X, while accidentally silencing the diagnostic for usage Y.
The correct way to read in a little-endian integer in C is the same way you'd do it anywhere else:
unsigned char *p;
size_t plen;
uint64_t n;
// initialize p and plen
_Static_assert(CHAR_BIT == 8, "CHAR_BIT != 8"); // [2]
n = 0;
for (size_t i = 0; i < MIN(plen, sizeof n); i++) {
n |= p[i] << (8 * i);
}
I've never seen a situation in C where type-punning of this sort was a good idea. The performance aspect is negligible. My parsers generally runs rings around code that uses type-punning. The gains are nothing compared to what you can get by better restructuring of higher-level code. For example, with hashing functions you're generally hashing small strings; thus the alignment checks you would need to add would typically cost more than the benefit because they couldn't be amortized well.
If you really had to, then C11 provides _Alignof that can be used to type-pun in a safe manner just like you could in Rust. (If a builtin type has padding issues, so would the same Rust code. It just so happens that Rust affirmatively has selected at the outset to never support such architectures. Thus, running the same code on the same architecture would work correctly in both languages.) It's not even type-punning if in addition to correct alignment you can prove that all bits are value bits. That would be the case for both the fixed-sized integer types, as well as for unsigned types where you can prove there are no padding bits (which can be accomplished using well-defined code as well).
So for general usage, if you really want to you could implement two versions of the code--one that type-punned correctly for long strings, and a simpler, more concise, more obviously correct one for typical strings. So it can be done correctly while still reaping the same performance; it's just more hassle than writing incorrect code. But even the incorrect code is more obtuse than the trivially correct version, which is why I've never had a good reason to type-pun.
[1] The exception in C is implicit conversions through a void pointer. But in C++, which lacks implicit void pointer conversions, engineers will often instinctively add an explicit cast where you would normally use a void pointer in C, substantially blunting the benefit of removing the implicit conversion from the language. And that habit to cast can easily lead to more bugs, just like in this case, where unsafe was used to permit the use of a broken idiom that is poor code even in C.
Good C rarely uses casts. Avoiding casts is a good habit to get into in C. And I've personally never seen good reason to type-pun anything, period, in C.
[2] The code could be trivially made correct on platforms where CHAR_BIT > 8 if the convention was that input strings only filled the bottom 8 bits of char. It would just be a distraction here, though.
I recently implemented my own version of SHA-3 in C. The original reference code from the authors (Google "Keccak-readable-and-compact.c") used type-punning in the inner loops (inside the the round function) on little-endian. On non-little-endian systems a macro was used to read and convert the 64-bit value.
This is typical premature optimization that is habitual among some developers, and another example of needless use of type-punning.
My code uses the simple code above to read bytes into the uint64_t buffer in the outer loop (outside the round function). Not only is my code simpler and easier to understand, it's no slower than the type-punning code even on x86-64.
Seriously, people, just don't type-pun. It's bad practice--in C, in Rust, in any language when using a remotely modern compiler. The only time it _might_ make sense is in very peculiar circumstances with peculiar access patterns, you've exhausted other easy gains, _and_ you've benchmarked and confirmed that type-punning is an improvement worth the cost in code complexity.
And even then, at least implement it correctly and safely. If you've already met the prerequisites above, the additional effort is negligible in the grander scheme of things. And committing to always writing correct and safe code keeps you honest when assessing whether performance hacks are truly necessary.
Type punning is perfectly allowed in Rust, I'm not aware of any lints against it. Although you need to use an annotation to specify the struct layout algorithm to do it "correctly" for custom types.
We use it in BTreeMap to implement a kind of inheritance between nodes. Internal nodes have the same layout as Leaf nodes, except internal nodes have an extra field for their array of edges (which you don't want to allocate for leaf nodes). So everything stores pointers to leaf nodes, and mostly manipulates all nodes as leaf nodes, but sometimes you "down cast" them to internal nodes to manipulate the edges.
In this particular case we use the standard C++ pattern of making a LeafNode the first field of an InternalNode.
https://doc.rust-lang.org/nightly/src/collections/up/src/lib...
The other common usage of punning in Rust is to gain access to some raw representation of a type. For instance, last time I worked on Rust, this was how fat pointers (&[T], &Trait) were constructed and decomposed at the lowest level.
I can't speak to whether the usage of punning in this code is particularly good though.
Specifically, the following common macro in C is _not_ type-punning, at least not the kind I had in mind.
#define container_of(ptr, type, member) \
(type *)((char *)(ptr) - offsetof(type, member))
In C, as long as the last access to an object had the same type as the type you're accessing that object from (and provided it's the same object), that's perfectly well-defined. People think that this is an aliasing violation in C, but it's not. Aliasing issues only come into play when there are side-effects (including order of evaluation) that you implicitly depend on but that the compiler cannot see. That issue is too complex to bother discussing in fine detail here, but suffice it to say that Rust either has similar undefinedness issues, or it assumes any pointer however derived can alias even inside an unsafe block and therefore cannot perform the same optimizations that a C compiler can. I doubt the latter is the case given that rustc relies on the LLVM backend.
Note that the general rule in C is that all pointers of the same type can alias, so if you derive two object pointers to the same type through explicit conversion (casting) or implicit conversion, and as long as they're actually referring to the same object, then as long as the last access is through the same type as the last store all is well-defined.[1] This is not type-punning. If this wasn't allowed by the language there wouldn't even be any use for casting at all. The cast is a way to stop the optimizer in its tracks and ensure that it doesn't fubar otherwise correct code.
The aliasing issue typically comes into play when you access at least one object through a structure or union, and there's no union definition in scope that hints that the layout is such that the sub-members of the union or structure might alias. Though the dereferenced expressions might have the same type, the dereference isn't occurring through pointers with the proper compatible type. This is one of the few cases where the compiler isn't required to assume that accesses might alias. And this is why the C standard requires those types of evaluations to occur through pointers to a union.
Type-punning, at least the kind I had in mind, is violating the core rule that access can only happen through an object with the same type as the last store. This is type-punning:
unsigned long l = 1;
unsigned *i;
i = (unsigned *)&l;
printf("i:%d\n", *i);
An example that isn't type-punning per se, but raises the aliasing issue,
struct foo {
int i;
}
int add(struct foo *fp, int *ip) {
int i;
fp->i = 0;
i = *ip;
return fp->i + i;
}
int main(void) {
struct foo f;
return add(&f, &f.i);
}
(Note: I'm having trouble using the asterisk without bolding everything. Please keep that in mind.)
The above can be made correct simply by casting:
int add(struct foo *fp, int *ip) {
int i;
*(int *)&fp->i = 0;
i = *ip;
return *(int *)&fp->i + i;
}
As you can see, this is a much more contrived scenario. It's not as common as you'd think. It's most common when type-punning--storing through one type and accessing through another. Don't type-pun and you won't run into this issue very often, if ever. It's not even that common when using the typical C OOP-like inheritance tricks. It can happen in a silent and deadly way, but that requires some serious hackery. Don't pretend that C is Java and you're unlikely to write such code. One of the common places this occurs in practice is type-punning struct sockaddr, struct sockaddr_storage, etc. That's a very unique situation for many reasons. But as optimizations in compilers improve it is admittedly an increasing problem; it's a loaded gun, for sure.
FWIW, C11 defines type-punning in a footnote 95 of section 6.5.2.3p3.
If the member used to read the contents of a union object is
not the same as the member last used to store a value in the
object, the appropriate part of the object representation of
the value is reinterpreted as an object representation in
the new type as described in 6.2.6 (a process sometimes
called ‘‘type punning’’). This might be a trap
representation.
[1] Storing a value through char is also okay as long as you ensure the representation is valid. Which is trivial when dealing with the standard fixed-width unsigned types. And access is always valid through char. That's why sometimes you'll see a seemingly superfluous cast through (char *). It's not necessarily type-punning; it might be used because a pointer-to-char can alias _anything_, and that can be useful as a barrier to prevent an optimizer from deciding two expressions might not alias.
Actually you can enforce that on Intel too. I do that for some hash functions in debugging mode, to avoid valgrind slowdown.
e.g. https://github.com/perl11/cperl/blob/master/cpan/Digest-MD5/...
#if defined(U32_ALIGNMENT_REQUIRED) && defined(__GNUC__) && (defined(__x86_64__) || defined(__i386))
/* Generate SIGBUS on unaligned access even on x86:
Set AC in EFLAGS. See http://orchistro.tistory.com/206
Also see https://sourceforge.net/p/predef/wiki/Architectures/
for possible other compilers. Here only GNU C: gcc, clang, icc.
MSVC would be nice also. */
#ifdef __x86_64__
__asm__("pushf\n"
"orl $0x40000, (%rsp)\n"
"popf");
#else
__asm__("pushf\n"
"orl $0x40000, (%esp)\n"
"popf");
#endif
#endif
The pseudocode for FNV looks like this:
hash = FNV_offset_value
for each byte_of_data to be hashed
{
hash = hash XOR byte_of_data
hash = hash × FNV_prime
}
return hash
hash = {offset_1, offset_2, offset_3, offset_4}
for (int data_index = 0;
data_index < data.length_in_64_bit_words;
data_index = data_index + 4_words_in_hash)
{
for (int hash_index = 0; hash_index < 4; hash_index++)
{
// Mix in data
hash[hash_index] = hash[hash_index] XOR data[data_index + hash_index]
// Diffuse
hash[hash_index] = hash[hash_index] XOR (hash[hash_index] RSHIFT 32)
hash[hash_index] = hash[hash_index] × seahash_prime
hash[hash_index] = hash[hash_index] XOR (hash[hash_index] RSHIFT 32)
hash[hash_index] = hash[hash_index] × seahash_prime
hash[hash_index] = hash[hash_index] XOR (hash[hash_index] RSHIFT 32)
}
}
result = hash[0] XOR hash[1] XOR hash[2] XOR hash[3] XOR data.length_in_bytes
result = result XOR (result RSHIFT 32)
result = result × seahash_prime
result = result XOR (result RSHIFT 32)
result = result × seahash_prime
result = result XOR (result RSHIFT 32)
return result
FNV is completely sequential. Until the first byte is hashed, no work can be done on the second byte. In seahash, as you observed, parallelism can be exploited. The second, third, and fourth bytes are all completely independent of the first byte, as bytes 6, 7, and 8 are independent of byte 5, and so on. You can have four independent threads each do a quarter of the work, and then put the result back together at the end.
> SeaHash achieves the performance by heavily exploiting Instruction-Level Parallelism.
> This means that almost always the CPU will be able to run the instructions in parallel.
I might have to bookmark this as a project to take on. A heavily parallel hashing algorithm that takes advantage of OpenCL would immensely increase the efficiency wouldn't it?
(I'm dipping my toes in parallel processing as of late and am genuinely curious in this topic and question)
The first line, "x ← x ≫ 32", might have a typo? It's actually assigning (x XOR (x >> 32)).
With "x ← px", p is a fixed prime number being multiplied by x.
I predict Rust will also begin to find use as a backend server language, and begin to eat into Java, Go, Python, and Ruby mindshare. Though there's a learning curve with Rust, it doesn't take too long to become productive. I'm also excited to see how Rust makes inroads in game development.
I think we're all going to start seeing more Rust in our headlines. It's a great language, and the people I know that use it are in love with it (myself included).
BTW, the hyperlink for "reference" in the "Specification" section is broken.
"Warning!
This is not a cryptographic function, and it certainly should not be used as one. If you want a good cryptograhic hash function, you should use SHA-3 (Keccak) or BLAKE2."
But it only seeds one of the lanes, so you can still make collisions trivially in one of the other lanes. I guess it could still be useful for namespacing.