I’ve tried it a few times during the last months but always returned to helix when lapce either crashed, stopped, consumed 100% CPU or otherwise behaved erratically.
That said, I like the idea of having a non textmode editor at my disposal, and I’m certainly not wed to modal editing.
Why do you intend to migrate from Qdrant? Is there a specific thing you are unhappy with? Or is there a missing feature that would persuade you to stay?
I’m loving the attention here :) — no, the thing I’d be hoping to gain is tighter integration with the rest of my data. For most of my data, I can use transactions, constraints, foreign keys, etc. But for Qdrant, it’s an external system where I have to build that stuff in myself. TL;DR the usual arguments against NoSQL or eventual consistent systems.
That’s interesting! So I suppose the rest of your data is in Postgres? How would you like to integrate it further?
I’m asking because I’m currently prototyping a Postgres extension for Qdrant. It’s just a proof of concept at the moment, but I think it might be valuable to get to know the requirements actual users have.
I love the cheap chunk lookup by counting leading zeroes in the index! That’s a useful idea independently of the lock-free-ness. It can be useful to have a cheap-to-grow vector with stable item references; sometimes I use a std::deque for this in C++, but I don’t know if it uses the doubling chunk size trick.
I would move the “stored” flags out of the items, into a parallel bitmap, to save space.
This vector can support overwrites (set) as long as the value type doesn’t require freeing (isn’t Droppable, in Rust.) Or it could support moving an item out, I think.
Unfortunately, the value types would need to be atomically updateable to make overwrites sound, because threads reading in parallel could experience tearing. This can, alas, only be fixed with some form of locking (e.g. a “locked” flag that gets set before writing and unset afterwards, in combination with a spin lock on the reader side) to keep readers from examining the value until it’s completely written.
That’s true; I was thinking of values either being smallish or references, both of which can be updated atomically. (IIRC many current 64-bit CPUs can atomically store 128-bit values.)
You are correct: 128-bit atomic operations have been supported for many years. They are useful for tagging pointers in lock-free data structures to avoid the ABA problem.
Specifically you can’t CAS a pointer assuming it uniquely identifies a single object for all time. An object could have been freed, and a new object allocated with the same address. Instead you should CAS a (counter, pointer) pair or similar.
I think the article already deals with the same issue at initialization time:
Because of this, we can’t rely on the counter to determine which elements are initialized, so entries need an additional atomic flag.
So you’d just set this flag at the start of any update, and clear it at the end, and the readers would use the same logic they already use to safely handle the fact that initialization may be non-atomic. (Importantly, in this data structure the entries aren’t lock-free, but the vector-as-a-whole has no global lock that blocks all concurrent readers).
Author here. This was an experiment to see if I could create a semantic search from free services (for non-commercial use, in one part limited to one year after which it will cost a few pennies) that people could use on their personal websites.
As a cloud sceptic, I expected a lot of decorum, and indeed, the first steps setting up the function were a bit jargon-laden for my taste, but afterwards using the cli and writing the code was surprisingly smooth thanks to Rust + the lambda libraries.
This is old news; it was a semi-troll-ish response to the first trademark policy draft which had people wondering if they can still say “Rust” out loud without summoning a register of lawyers.
More full-troll-ish… anyone who had even the most cursory understanding of trademark law knew the policy was absolutely fine and didn’t substantially alter what they already could (or could not) do with someone else’s trademark.
A semi-troll-ish move would be to fork their fork and call it GreenGlandLang… for those who know that crabs habitually urinate in their own faces.
More full-troll-ish… anyone who had even the most cursory understanding of trademark law knew the policy was absolutely fine and didn’t substantially alter what they already could (or could not) do with someone else’s trademark.
Yeah, this is part of the problem with soliciting the community for feedback. Developers are not at all qualified to read legalese and have no idea how trademarks work.
There were some issues with the policy, but nothing glaring, and nothing nearly as bad as people were implying, like “omg they can sue us for writing rust”.
Well, Python 1.0 also came out in ‘94, and Java was called Oak before being renamed to the hot brew we all know and love. But I’ll gladly admit one could argue either way.
it’s still no match for easy-entry languages like Python or Go. But learning it is a one-time cost. Contrast this with Go, where you may find the apparent simplicity is only skin-deep.
Thanks, I wish people would be more vocal about this. The “hard” part of Rust is learning the language, the hard part of so many other languages is learning the quirks and bad design decisions. You learn the former upfront, you learn the latter from incidents.
I don’t know. I have a static site generator that I ported from Python to Go to Rust and now back to Go. The first three were just ways to explore new languages, but the final iteration was “I actually use this, and the Rust version is really hard to maintain” (specifically, despite being more elegant and performant, adding functionality was so much more cumbersome for minimal benefit even as someone who knows Rust pretty well by now).
Additionally, I made more mistakes writing the Rust version than the first Go version despite having the benefit of hindsight and a robust type system. I flubbed some filepath/URL manipulation code in large part because I was so focused on the type system (making decisions about borrowing vs cloning).
In a separate project, I was dealing with a lot of integer IDs which identified different kinds of resources—in order to make sure I used the right ID for the right resource type, I wanted to create an integer newtype (struct FooID(u64)), but there was a lot of tedium in making all of the necessary arithmetic and conversion traits to have something that was basically usable as an integral type and I still had a couple of frustrations: (1) I still couldn’t automatically instantiate a typed variable from an integer literal a la Go’s x = 0; rather, I had to type x = FooID::new(0) or x = 0.into() or similar and (2) I couldn’t use those arithmetic traits in const contexts, so I had to define a bunch of const functions with similar names. Go just kind of does what I want out of the box—it doesn’t let me implicitly convert between types, it lets me do const arithmetic, and I can instantiate variables from untyped integer constants. If I had to do it again, I’d be tempted just to use u64s for everything (I’ve seen quite a few projects do the same, but I’m not sure which approach is idiomatic), but this is definitely going to yield more bugs.
I’m glad to hear that you found a good tool for your job. So do you feel that you can write robust misuse-resistant interfaces in Go? What are your techniques for achieving this?
I’m not sure what you mean. I don’t have many problems with people misusing code. Usually the type annotation makes usage pretty obvious and where it isn’t obvious, I add a small, precise, clear comment. Mostly though I try to keep my interfaces as simple as possible.
I’m not saying Go is perfect; const and Rusty enums would be great, and I would love better compiler optimizations. But Go is just wildly more productive than Rust for most applications in my experience (productivity is not always the most paramount concern either).
Yeah, when I wrote some Go, I was missing enums dearly. Also the ? operator; the error handling gets quite wordy. I still think that it’s mostly down to familiarity: Having written Rust code for some time, I can now write stuff in Rust faster than I could in Go, while I allege that someone who’s more fluent in Go will have a contrary experience.
I don’t think it’s just fluency. I’m wayyy more versed in Rust than say TypeScript (like nearly 10 years more experienced), but I’m wayyy more productive in TypeScript. I agree that error handling in Go is more verbose than in Rust if you’re not adding context to your errors, but I prefer to add context for debugability (fmt.Errorf(“doing foo: %w”, err)). You can do this in Rust with anyhow but that seems like bad practice for library code. Further, I spend a lot of time in Rust crafting error enums and setting up the necessary traits (including convenience traits like From). thiserror helps but I still find myself fighting compilation errors in the generated output. Similarly, I also agree that Rust enums would be nice in Go, but unless I’m writing a compiler or something that is just enums all the way down, I just make a struct with a tag field or use interfaces and move on with life (definitely a loss of safety, but I can move so much faster than with Rust that I have plenty of time to test).
in order to make sure I used the right ID for the right resource type, I wanted to create an integer newtype (struct FooID(u64)), but there was a lot of tedium in making all of the necessary arithmetic and conversion traits
I don’t want to push you to return to Rust if you didn’t like it, but I think this is a use-case for ambassador (or delegation, the non-existent built-in equivalent). (Using a procedural macro like ambassador surely will not reduce the difference between Go’s and Rust’s compilation speeds, though….)
I don’t think I understand why one would want integer newtypes used as IDs to support arithmetic, though.
I should note that I still like Rust; I just don’t relate to some of the comparisons with Go. Specifically, Rust is great for systems programming or high performance programming; basically stuff where C and C++ is used today. I also like Rust in theory—the emphasis on zero-cost abstraction and so on.
To give a background why is that: UB is not an event that happens in the program. Instead, “UB is impossible” is an assumption that is baked into the compilers.
The compilers don’t have if is_UB() { screw_you() } anywhere. The no-UB assumptions can be implicit and pervasive. Like an assumption that opposite of true is false, so if (x) {do} and if (!x) {} else {do} are equivalent. If you magically made a 3-valued bool with filenotfound, then it’s not merely triggering some else { lol() } code path in the optimizer. Instead, it makes all the assumptions about boolean algebra invalid and full of impossible-to-reason about paradoxes. And it’s hard to warn about this, because UB is not an event or a code path. The compiler would have to warn about every non-issue like “here I’ve assumed that the opposite of false is true”.
The second reason is dealing with complexity of optimizations. It’s too difficult to optimize code in the high-level form you write it. There are too many tree structures to work with, too many scopes, too many constraints to preserve. Instead, the code is “lowered” to a simpler assembler-like representation that no longer resembles the source code. In this form programmer’s intention is hard to see, so it’s no longer obvious what should and shouldn’t be optimized out.
To manage the complexity, optimizations are applied to low-level code in multiple independent passes. This way instead of having to consider all of the C spec for any change, each pass can focus on one thing at a time, e.g. “can I change !!x to x”. There’s a pass that simplifies arithmetic, there’s a pass that checks which expressions are always true, and there’s a pass that removes unreachable code. They can end up removing your null or overflow checks, but they don’t mean to — each pass does its own thing that in isolation seems sensible, spec-compliant, and is useful for most of the code.
And finally, majority of the optimizers in C compilers are shared across all architectures. They evaluate code as if it ran on the hypothetical portable machine that the C spec describes, not your particular CPU. So it doesn’t matter that your CPU knows how to overflow a signed int or has caches coherent across threads. The low-level virtual machine the optimizer optimizes for doesn’t have that, and code under optimizer will “run” in the C way instead.
Instead, it makes all the assumptions about boolean algebra invalid and full of impossible-to-reason about paradoxes
This is a great explanation, but substitute ‘integer’ for ‘boolean’ and you get why C compilers really like that signed integer overflow is undefined. If you write something that loops performing some addition on an integer, then you have an induction variable that can be modelled as an arithmetic sequence. If you have a nested loop, then the induction variable can be modelled as a geometric sequence. This model is completely wrong in every regard if adding two positive values together can result in a negative number. Having to understand this case precludes any transform from making use of this information. This precludes a large number of loop optimisations.
Signed overflow is UB so compilers get to pretend it can’t happen. The lack of UB on unsigned integer overflow means that many compilers don’t optimize unsigned arithmetic nearly as aggressively, for precisely the reason you point out. The difference is that compilers aren’t allowed to ignore the possibility of unsigned overflow since it’s well-defined and allowed to happen.
My favorite example of undefined behavior: creating a pointer into the stack and messing around with its contents. In C or unsafe Rust or something like that, compiler has literally no way of preventing you from doing this, and no way of detecting that it has occurred. It’s not even “this is on you to make it safe” territory, because the compiler is allowed to assume the contents of the stack doesn’t change out from underneath it… it may juggle local variables in and out of registers or something and, within the bounds of the calling convention, you get make zero assumptions about how it works. Just ‘cause one compiler puts a particular local var at [rsp+24] or whatever doesn’t mean it will be there the next time you compile the program.
Yes, you can do it. You can even make it work, if you know exactly how the compiler works and the compiler doesn’t change. But you’re breaking the invariants that the compiler fundamentally uses to function, and it is incapable of noticing that you are doing it.
(Update: Notably, if you pass -O3 to most versions of gcc in godbolt it will generate the code you expect, but clang will almost invariably nope out and just return 1 or 0 or nothing at all. Fun!)
That’s not what I imagined a pointer into the stack would be from your description.
That’s a pointer into a local variable. The compiler wouldn’t even allocate stack space if you compile with optimizations.
Pointers to local variables are not UB.
Edit: What is UB in this case is that you incremented “b” outside the array bounds (a pointer to a single object is considered to be a pointer into an array of 1 element).
Edit 2: You can freely use such pointers while the compiler passes variables into and out of registers and your program will still work just fine. But your pointer is not allowed to go outside the bounds of the array (except to point one-past the array, but then you can’t dereference it).
You are correct, the UB in this case is incrementing the pointer out of its bounds. The thing is that a local variable (edit: usually) has to exist on the stack if you have a pointer to it that does arithmetic. So the easy way to get a pointer to a random place on the stack is to start from a local variable. You can also have a function that returns a pointer to a local var, you can start in the data segment or heap, or you can just make a good guess of where your stack is and hope ASLR doesn’t ruin your fun.
Or if you really want to go hard, you can ask a user to type in a number and use that as an address. Who knows what they’ll type in? The compiler sure doesn’t.
So the easy way to get a pointer to a random place on the stack is to start from a local variable.
No, you don’t necessarily get a pointer to a random place on the stack if you do that. The local variable or array may not even exist on the stack.
If you go outside the object/array bounds with pointer arithmetic, you get UB which does not have to (and many times won’t) translate into a random pointer, it will just mean that your code will break (and it can break in many different ways).
You should really, really, carefully read @kornel’s top post to understand how UB works.
You can also have a function that returns a pointer to a local var
That’s UB but again, you won’t necessarily get a random pointer to the stack, as the variable may not even exist on the stack. And even if it does exist, your code can break in completely different ways than getting a random pointer to the stack.
you can start in the data segment or heap
You’d get UB if your pointer goes outside of a malloc()-allocated area, but again, you wouldn’t necessarily get a pointer value. You’re making the exact same false assumptions that @kornel talks about.
Your code could simply be completely optimized out, or it may cause other very strange effects that have nothing to do with pointers.
or you can just make a good guess of where your stack is and hope ASLR doesn’t ruin your fun.
Even if you knew exactly where your stack is, I don’t think there is a way to deterministically create such a pointer without implementation-specific behavior (e.g. assembly code).
Edit: updated Godbolt link due to a typo in the code.
Or if you really want to go hard, you can ask a user to type in a number and use that as an address. Who knows what they’ll type in? The compiler sure doesn’t.
I believe converting an arbitrary integer into a pointer is also UB and you don’t necessarily get a pointer like you think you will, your code can just completely break in lots of different ways (including simply being optimized out).
You’d have to enable some kind of special implementation-specific compiler option to do something like that without UB.
What is not UB, I believe, is to e.g. pass a pointer value into an intptr_t variable and then back into a pointer without changing the value.
And yet this is also how just about every device driver under the sun works.
Because of this:
You’d have to enable some kind of special implementation-specific compiler option to do something like that without UB.
Edit:
Correction: technically speaking, it seems that the integer-to-pointer conversion itself is not UB if you use an explicit cast, but the C standard says the result is implementation-defined, so the code can behave differently depending on which compiler (or compiler version, or compiler flags) you’re using.
In fact, the C standard says that the resulting value can be a trap representation, which means that it could trigger UB as soon as you tried to do anything with that pointer.
Even if your implementation allows doing that and even if the integer is a valid memory location, I would imagine it would still be possible to trigger UB by violating other constraints, like creating a duplicate copy of another pointer of a different type (which could violate strict aliasing constraints), or creating a pointer with the wrong alignment, or calling free(ptr) if the memory location hadn’t been allocated with malloc() before, etc.
I believe converting an arbitrary integer into a pointer is also UB
The int-to-ptr operation is actually fundamentally implementation-defined. So you won’t find the UB rules for ptr-to-int and int-to-ptr in the standard, you need to look at the LLVM LangRef instead.
But that’s on GCC (probably clang does the same). There might be C compilers that are C-standard-compliant that might not generate an error.
If you are asking why doesn’t the C standard specify that such conversions are invalid rather than UB? No idea!
Edit: oh wait, I made a mistake! The above error is when compiling in C++ mode (the Compiler Explorer’s default, annoyingly). In C mode, it’s not an error, it’s a warning by default:
I don’t think this is the kind of error you’re expecting to see - if you change the code to int *a = (int *)4 it should compile without warning. I don’t know if this is even supposed to be undefined behaviour - when talking to devices you need to know the exact memory address “as a number” and write to it or read to it (think VGA video memory addressing and such), which is or was traditionally often done in C under DOS in real mode, for example.
Although it might be that this has sort-of been retconned into “always having been wrong” like relying on hardware behaviour on integer overflow has been.
Local variables are generally allocated on the stack. In some cases, it may be able to not allocate memory at all and keep the local variable purely in a register, but any time you mess around with pointers to local variables – especially when those pointers are passed across non-inlined function boundaries – that pointer is to the stack-allocated local variable.
With optimizations disabled, you can look at the assembly code and stack frame and verify that ‘a’ is allocated on the stack and ‘b’ is a pointer to that stack-allocated variable in icefox’s example. Here’s a slightly modified example where the pointer is passed across a function boundary to be dereferenced: https://godbolt.org/z/x8zEKEr1E
Yes, I know that, but @icefox was talking about “creating a pointer to the stack”, but as far as I can see there is no way to create a pointer to the stack in the C language, or at least no portable way to do it (i.e. without relying on implementation-defined behavior).
The C18 standard, as far as I can see, doesn’t even have the word “stack” in the 535-page document!
Someone else mentioned alloca() but even that is not part of any standard.
Then he said:
In C (…) [the] compiler has literally no way of preventing you from doing this,
Which seems to make little sense because if you’re relying on implementation-defined behavior (which has to be documented) to create a pointer to the stack, then that means that the compiler has already promised to give you a pointer to the stack. So of course it can’t prevent you from messing around with it.
It’s not like you “tricked” the compiler into giving you such a pointer, usually it’s actually the opposite: the compiler is the one who tricks you into thinking that you have a pointer to the stack when in fact the local variables (and even arrays) that the pointer points to, may only exist in registers or, since all the values of the variable might be possible to determine at compile time, may not exist at all!
Edit: That said, yes, I understand that if you rely on implementation-defined behavior then it is possible to deterministically create such a pointer (e.g. with alloca()) and mess around with it, such as corrupting the stack and causing UB. Which is what I meant when I said that you’d have to call some (platform-specific) library function to do that, it’s not like there’s a construct in the C language that says: “this is how you create a pointer to the stack”.
You can’t find the word “stack” in the C standard because the C standard indeed has no concept of a “stack”. As far as the standard is concerned, local variables have automatic storage and are alive until the function returns, variables allocated with malloc and the like have allocated storage and are alive until they are freed with free.
However, the common implementations have a chunk of memory they call “the stack”, where each function gets a sub-chunk called a “stack frame” which is where the compiler puts, among other things, the variables with automatic storage (except for those variables which it optimizes out or keeps in registers only). Therefore, when you take the address of a variable with automatic storage, the implementation will give you an address to the place in the function’s stack frame where that variable is kept; you have a pointer to somewhere in the stack.
There is some mixing of abstraction levels here. You never have a “pointer to a variable allocated on the stack” in terms of the C abstract machine, you have a “pointer to a variable with automatic storage”. But when we lower that into the level of concrete machine code for some operating system, we can see that in the right circumstances, our “pointer to a variable with automatic storage” gets lowered into a “pointer to a chunk of memory in the function’s stack frame”. So we can create an example program which proves @icefox’s point (namely that the “compiler has literally no way of preventing you from doing this, and no way of detecting that it has occurred”):
a.c:
// This function assumes it gets a pointer to a chunk of memory with at least 5 ints, and sets the 5th to 0.
// There is nothing at all wrong with this function, assuming the pointer does indeed point to 5+ mutable ints.
// There is no way for the compiler to detect that anything wrong is going on here.
void clear_fifth_int(int *ints) {
ints[4] = 0;
}
b.c:
void clear_fifth_int(int *ints);
// This function creates a local variable 'x', which the implementation will put on the stack,
// then calls 'clear_fifth_int' with a pointer to 'x'.
// There is nothing at all wrong with this function, *if* the 'get_fifth_int' function only dereferences the
// pointed-to int, so there's no way for the compiler to detect that anything wrong is going on here.
// However, we know that clear_fifth_int will touch whatever happens to be 4*sizeof(int) bytes after 'x'
// on the stack.
void stupid() {
int x = 10; // x ends up allocated on the stack
clear_fifth_int(&x); // &x gets a pointer to somewhere in the stack
}
No individual function in this example does anything wrong, but in combination, they mess around with the stack in ways which the implementation can’t anticipate.
No individual function in this example does anything wrong, but in combination, they mess around with the stack in ways which the implementation can’t anticipate.
You don’t actually know if they mess around with the stack, they may very well not. With link-time optimization all of that code could be inlined together and no pointers to the stack would even be created.
What you are saying is actually a result of the following:
The pointer points to a single object, rather than a sufficiently-large array of objects. Which results in UB when you do pointer arithmetic past the bounds of the array.
Or, in other situations, it could result in UB due to dereferencing a pointer past the lifetime of the object (which could happen both for automatic storage and for heap-allocated storage).
It has nothing to do with “the stack” or a “pointer to the stack”. It is simply the result of having “a pointer” (to some non-permanent storage).
You are assuming that a specific implementation detail will happen. How do you know that’s what will happen? Does your C compiler or some other standard guarantee that? I assume the compiler documentation or a calling convention such as the System V ABI may be able to guarantee that. But if it does guarantee it, how is that “the implementation not anticipating”?
I don’t understand what you are disagreeing with me about. Clearly, we have some C code, where all translation units are correct in isolation, but in common implementations, their combination might (and likely will, but is not guaranteed by any standard to) result in machine code which messes with values on the stack in a way the compiler can’t account for. That much is inarguable, and I don’t see you claiming otherwise; so where is the contention?
Clearly, we have some C code, where all translation units are correct in isolation but where their combination might (and likely will) result in machine code which messes up values on the stack in a way the compiler doesn’t expect. That much is inarguable, and I don’t see you disagreeing with it
Indeed, that is correct.
so where is the contention?
The contention is in the following two points:
In suggesting that “In C (…) the compiler has literally no way of preventing you from doing this, and no way of detecting that it has occurred”, where “this” is creating a pointer to the stack and messing around with the stack.
I think that phrase is a bit misleading, because:
The C language has no construct to create a pointer to the stack, which means you’re either:
Relying on implementation-defined behavior, which means that the compiler is actually giving you such a pointer on purpose
Or it means there’s no way to deterministically create such a pointer, because the pointer may not even exist, i.e. the compiler may optimize it out.
Which means that the compiler can prevent you from doing that. And if it can’t, it’s probably because you’re relying on the calling convention which is implementation-defined behavior, therefore documented and the compiler would be doing it on purpose.
Or it means you’re relying on some library function or assembly code to create such a pointer, which is what I thought he meant and why I asked him to clarify as it’s not very common to do this!
The other contention point, which I admit is (even more?) pedantic, is:
In saying that all of this is specific to “pointers to the stack” when it is actually just a result of having pointers and going outside their bounds or the lifetime of the storage they point to, which applies to all types of pointers.
That said, yes, I understand that when going outside the bounds of a pointer (for example) to heap storage is unlikely to corrupt the stack (even though it’s possible) and that stack corruption is a very particular type of corruption which usually has very… interesting side-effects!
So in conclusion, I think we are in agreement with regards to the underlying issues, I just disagree with the phrasing and particularly, how it appears to be suggesting that the compiler is powerless to prevent it, when in fact you’re either breaking the invariants of the language itself, or the compiler is actually going out of its way to help you do that, on purpose (just in case you like to shoot yourself in the foot)!
Edit: “external library” -> “library”
Edit 2: in other words, you haven’t really forced the compiler to give you a pointer to the stack, it was the compiler who decided to give that to you, and it could just as easily have decided to do something else if it wanted (proof: the existence of conforming C compilers for architectures that don’t even have a stack).
If the compiler has a concept of what we would conventionally call a “stack”, and it has put a variable on the stack, the compiler has no way to prevent you from taking a pointer to that variable and messing around with other stuff that’s also on the stack and no way of detecting that it has occurred, assuming the compiler implements pointer arithmetic in the way all the common implementations do.
Personally, I think the original comment was clear enough, adding all those caveats just muddies the meaning IMO. But I won’t disagree that it’s assuming a few things which aren’t strictly guaranteed by the C standard.
[…] I just disagree with the phrasing and particularly, how it appears to be suggesting that the compiler is powerless to prevent it, when in fact you’re either breaking the invariants of the language itself, or the compiler is actually going out of its way to help you do that, on purpose […]
Well, you are breaking the invariants of the language, but I don’t understand how that means the compiler can prevent it. The compiler gives you a pointer to a variable which the complier has decided to put on what it calls “the stack”. The language has features which make compile-time tracking of where pointers come from impossible. The language has features which lets you do arithmetic on pointers. Given those facts, if a compiler is implemented in such a way that there exists a stack which contains stuff like the return address and local variables, the compiler is powerless to prevent you from messing with stuff the compiler has to assume is left unchanged.
I agree that a compiler might be implemented differently, it might store the return address stack separately from the variable stack, it might allocate every local variable in a separate heap allocation and automatically free them when the function returns, it might do runtime checking of all pointer dereferences, or any number of other things. But under the assumption that the implementation works roughly like all the major C implementations currently do, everything icefox said is correct.
If the compiler has a concept of what we would conventionally call a “stack”, and it has put a variable on the stack, the compiler has no way to prevent you from taking a pointer to that variable and messing around with other stuff that’s also on the stack and no way of detecting that it has occurred, assuming the compiler implements pointer arithmetic in the way all the common implementations do.
This phrasing is also wrong. The compiler can do all of those things and yet the pointer is not a pointer to the stack, it’s a pointer to the variable (which may currently be stored in a register or even may only exist as a constant in this exact moment, even though there’s an allocation for the variable in the stack).
For example if you have this code:
void some_function(int *y, bool condition) {
*y = *y + 5;
if (condition) {
y += 100000;
*y = 20;
}
}
void foo() {
int x[100] = {0};
int *y = &x[50];
some_function(y, false);
printf("%d", *y);
(...)
}
… it may not do what you think it does. Why? Because the compiler is allowed to transform that code into this equivalent code:
int some_specialized_function() {
return 5;
}
void foo() {
int x[100] = {0};
int z = some_specialized_function();
printf("%d", z);
x[50] = z; // this line may or may not exist, e.g. if x[50] is never used again
(...)
}
So even if there’s an allocation for x[] in the stack frame for some reason (let’s say some further code manipulates the array), you think that y is a pointer to the stack, but it may very well not even exist as such, even if the code for some_function hasn’t been inlined!
And even if you call some_function(y, true) instead of false, you think you tricked the compiler into corrupting the stack, but the compiler can clearly see that y points to &x[50] so increasing y by 100000 is absurd and the entire if block of the specialized some_function() implementation can be removed.
So yes, the compiler can prevent you from messing around with the stack even in that case.
The compiler gives you a pointer to a variable which the complier has decided to put on what it calls “the stack”.
Yes, you said it very well here, even though that doesn’t always happen. The compiler has decided. You haven’t forced it to do that. The compiler could have decided something else. It was an implementation choice, which means the compiler could have prevented it.
I agree that a compiler might be implemented differently, it might store the return address stack separately from the variable stack, it might allocate every local variable in a separate heap allocation and automatically free them when the function returns, it might do runtime checking of all pointer dereferences, or any number of other things.
Exactly! Which means that the compiler can actually prevent you from doing the things icefox said.
But under the assumption that the implementation works roughly like all the major C implementations currently do, everything icefox said is correct.
Well, it’s not possible for me to prove this, but to be honest, I think icefox had a misconception, as evidenced by the fact that (before he edited it) his reply to my comment said that just doing pointer arithmetic on a pointer to a local variable means that the compiler is forced to give you a pointer to the stack, when this is not true: compilers often optimize such pointers out of the code completely.
And you know, this entire debate could have been avoided if he just said “it’s often possible to corrupt the stack [perhaps by doing such and such], which has all these interesting effects” rather than suggesting that C compilers have some underlying limitation and are powerless to prevent you from messing with what they do.
But you know, apart from that, I think we are in agreement!
So it doesn’t matter that your CPU knows how to overflow a signed int.
I would say, it doesn’t matter that virtually all CPU in active use since… say the start of the 21st century, know how to overflow a signed int. Some platforms somewhere that existed at some point in time don’t know how to overflow signed integers, and so the standard committee thought it was a good idea to mark it “UB”, probably for portability reasons, and the compiler writers later thought it was a good idea to interpret it literally, for optimisation reasons.
This is where the standard committee should really have said something along the lines of:
Signed integer overflow is implementation defined…
except on platforms that produce non-deterministic results, in which case it’s unspecified…
except on platforms that fault, in which case it aborts the program, whatever that should mean…
except on platforms that fall into an inconsistent state, in which case it’s Undefined Behaviour™.
Sure, the specs are wordier this way, but that would have gotten rid of a huge swath of security vulnerabilities. And while some code would be slower, compiler writers would have told everyone they should use unsigned size_t indices for their loops.
But no, they didn’t define behaviour depending on the platform. If something is undefined in one supported platform, no matter how niche, then it’s undefined in all supported platforms. Just so it could be a little bit faster without requiring users to touch their source code.
My understanding of undefined behaviour is now as follows: compilers will, in the face of undefined behaviour, generate code that under the “right” conditions causes your hard drive to be encrypted and print a ransom message. The most useful threat model of a compiler is that of a sentient adversary: if there’s any UB in your code, it will eventually find it, and cause as much harm as it can up to and including causing people to die.
The compiler isn’t out to get you, and generally won’t include disk-encrypting code into your program if it wasn’t there before. The line about playing DOOM on UB is meant as humor and to demonstrate that it’s still not a compiler bug if this happens. But in reality, it isn’t actually going to happen in GCC, or Clang, or rustc, or any other compiler that wasn’t purpose-built to do that. It’s not guaranteed to not happen, but compilers are in practice not written to maliciously manufacture instructions out of whole cloth just to mess with you on purpose.
But at the same time, providing guarantees about undefined behavior … makes it not-undefined anymore. There can certainly be less undefined behavior (e.g. mandating the equivalent of NullPointerException, or Rust’s “safe Rust is UB-free Rust, or it’s a bug in the compiler” guarantee), but any real compiler will still have some UB. UB just means “this is an invariant that I expect and internally continue to uphold, and I don’t know what happens if something breaks it.” Even my toy compiler for the Advent of Code day 23 problem from last year contains a notion of UB, which I plan to discuss in an upcoming episode of my Compiler Adventures blog series – and that’s for a programming language that doesn’t even have if statements or loops!
I guess the playing DOOM on UB being humorous is written with MMU-using operating system mindset. I witnessed IRL a situation where a simple read from stdin, do some calculations, write to stdout C program was quite reliably opening CD-ROM tray… That was on Windows 3.11 I think.
My dad once traced a client-reported bug in his company’s software down to a bad CPU in the client’s machine. When adding two very specific 3-digit integers together, the sum was incorrect. It wasn’t UB that time, just bad hardware, but it doesn’t sound like it was fun to track down. And the accountants using the software certainly didn’t appreciate the fact that the computer was adding up their numbers wrong…
Since it’s the accountants’ computer that is broken, they have a catch 22. They need to ask for their money back, but the computer they do all their sums on is broken, so how much refund should they be asking for!? They can’t possibly calculate it. ;)
The compiler isn’t out to get you, and generally won’t include disk-encrypting code into your program if it wasn’t there before.
Correct, but ransomware authors are out to get me, and they’ll exploit any vulnerability they can. And UB driven compilers are a source of vulnerabilities that wouldn’t be there if more behaviour was defined. That’s where my threat model comes from. Blaming the compiler as if it was the enemy isn’t accurate, but it is simpler and more vivid.
Oh, and that talk from Chandler Carruth? I’ve watched it several time, its misleading and harmful. All the more because he’s such a good speaker. He’s trying to reassure people about the consequences of their bugs. Sure the compiler itself won’t actively summon the nasal demons, but outside attackers finding vulnerabilities will. And the result is the same: UB does enable the summoning of nasal demons.
But he’s not saying that out loud, because that would drive people away from C and C++.
But at the same time, providing guarantees about undefined behavior … makes it not-undefined anymore.
Correct, which is why I advocate for defining more behaviours in C.
Correct, which is why I advocate for defining more behaviours in C.
I think that’s a lost cause. Instead, it would be nice to have more options like -fwrapv that at least impose sane behaviour for things that are UB, strictly speaking.
I think the larger point is that, effectively, people who write C have to treat the compiler as a deadly hyperintelligent enemy deliberately attempting to cause as much harm as possible via any means available. Otherwise they just end up being hurt by the compiler, and then when they write it up they get mocked and belittled by people who tell them it’s their fault that this happened.
And since it’s effectively impossible to write useful/non-trivial C programs without UB, the takeaway for me is “don’t ever write C”.
FWIW I feel similarly. I’ve switched to Rust because I don’t trust myself to not write UB and to not commit memory safety errors. I still haven’t needed unsafe in Rust anywhere thus far, and “if it compiles then it’s memory-safe and UB-free” is worth a lot to me.
C users as a whole are hostile to any overheads and speed regressions in compilers. Compilers get benchmarked against each other, and any “unnecessary” instructions are filed as issues to fix.
Look how long it is taking to zero-init all variables in C and C++, even though overhead is rare and minimal, and the change is good for security and reliability.
I can’t imagine users accepting speed regressions when indexing by int, especially when it’s such a common type.
The most useful threat model of a compiler is that of a sentient adversary:
I just wrote a whole post trying to explain this couldn’t be further from the truth, so I don’t get what you’re trying to say here.
The most useful threat model of a compiler is that of a sentient adversary:
I just wrote a whole post trying to explain this couldn’t be further from the truth, so I don’t get what you’re trying to say here.
It’s an oversimplification. There are sentient adversaries out there out to exploit whatever vulnerabilities that may arise from your code. And mr compiler here, despite being neither sentient nor actively hostile, does tend to magnify the consequence of many bugs, or to turn into bugs idioms that many long time practitioners thought were perfectly reasonable.
Thus, I like to pretend the compiler itself is hostile. It makes my threat model simpler and more vivid. Which I pretty much need when I’m writing a cryptographic library in C, which I ship in source form with no control over which compilation flags may be used.
For example, you can compile an entire Linux distro with the -fwrapv gcc and clang flags and you’ll get the behavior you want (i.e. well-defined signed overflow with wrapping behavior).
All code that was previously C-standard-conformant will still remain C-standard-conformant. Additionally, code which previously triggered UB on signed overflow now also becomes well-defined.
Although I do sympathize with your point that this should probably be the default even if it has a performance cost, also note that in many cases such well-defined signed overflow can lead straight into UB or a crash anyway, because these integers in many cases are used as array indexes or on array index calculations.
Edit: might I suggest deterministically aborting on signed overflow/underflow? You can use -ftrapv for that.
I do wonder if one could extend LLVM with a visualization that tells us what optimizations used which assumptions, somehow summarizing on a top-level view while allowing us to drill down to each block. That would be a great teaching and debugging tool indeed.
That would be cool! But it sounds quite difficult to be honest. I’ve been thinking about ways to describe and represent information flow in my Compiler Adventures blog series on how compiler optimizations are implemented, and even for the massively-simplified language used there (no loops, no branches, no functions!) it’s still quite difficult to track “who did what where because of whose info.”
Of course this doesn’t say it can’t be done, and I really hope someone takes up that challenge. I’ll be excited to see the results.
If your compiler has 10 individual optimizations which get performed iteratively in a total of 30 optimization passes, you could imagine recording the output of every one of the 30 optimization passes and then showing that to the user, allowing him to go to the previous/next pass and see a diff of what changed.
You wouldn’t know exactly why an optimization happened if you’re not familiar with the optimization, but I think it would still be immensely instructive.
Although you’d need different visualizations and diff algorithms for different intermediate compiler languages (C AST, LLVM IR, assembly, etc).
This is a very good way to understand the behaviour of the compiler you’re using.
Fwiw you don’t need to store all the intermediate results if the compiler is deterministic, you can generate the one you want to look at by running all the passes up to that point.
I think you can do this right now with clang? By changing the list of passes and dumping IL.
You can do something like this with ghc-core for Haskell. :)
That is a load-bearing phrase right there :) Making compilers behave deterministically is possible but quite difficult. Folks working on reproducible builds have gone down this road, so we can learn from their experiences.
It might be a topic for a future “falsehoods programmers believe about compilers” post :)
I’d be a quite an ambitious project. Consider how incomplete debug information is in optimized programs. Optimizers already struggle with even the most basic tracking of where the code came from. So tracking all the changes, their causes, and their assumptions would be even harder.
There’s a lot of passes (that’s where majority of compilation time is spent). They are a mix of analysis and transformations passes that aren’t explicitly connected. Some passes even generate new unoptimized code that is meant to be cleaned up by other passes, so it’s hard to track meaningful causality throughout all of that.
Optimizers work on a low-level code representation where your variables don’t exist any more (SSA form), there are no for, while or if constructs, only goto between chunks of assembly-like code (CFG). So even if you collect all the data without running out of memory, filter it down to only relevant bits, it would still be difficult to present it in a way that is relevant to C programmers.
Compilers have these in what they call back-ends, which are usually separate from their main optimiser, and are language-independent, so the concept of C’s UB doesn’t exist there any more.
What good does your company’s existence do for humanity (or the community, depends on the type of compny)? Conversely what bad outcome for humanity are you willing to accept for the financial success of the company?
I’m not too fond of coding challenges. People can look at my github and see I can code at a glance. This will needlessly filter out people who are not privvy to the project, are nervous because of the interview situation, or worst of all are bad at live coding (which is unusual to do on the job).
I usually have one question when I interview people for coding positions. I give that question out beforehand and am happy to let applicants prepare for it. The question is: What piece of code are you most proud of (Feel free to brag)?
A toy bcrypt hash cli tool I wrote in Java 7 years ago. I haven’t programmed professionally in Java for… 7 years.
A Ruby gem for pretty printing tables that I literally don’t remember writing, definitely didn’t publish, and surprisingly has a README and basic tests. I have never programmed professionally in Ruby.
A private repo for a private guild administration mod for an MMO I used to play. Written in some truly abhorrent Lua, containing numerous bug fixes of the form “if this specific case happens, twiddle some state so wrong things don’t happen.” Almost all of these bugs could be fixed by refactoring the code into something sensible. I have only briefly programmed professionally in Lua, before rewriting the application in Go because no one else wanted to maintain a Lua/C++ project. The repo is private anyway, thankfully.
None of these things are remotely representative of my abilities. I have significantly more skill and experience writing C++ (most of my career). I’m currently working as an SRE writing lots of bash and Terraform.
Maybe coding challenges are bad. But GitHub is absolute garbage for gauging anything about many developers.
I’m also not fond of coding challanges, but if it there has to be one, I’d much rather take one as described in these article than the contrived, shuffle-things-around-in-arrays-in-two-hours-and-hope-you-don’t-get-stuck-on-some-edge-case or make-some-service-from-scratch-and-hope-it-matches-the-tradeoffs-and-style-preferences-the-reviewer-silently-expects kind.
I think your question will also have a few people who won’t like it. For example: fresh graduates who aren’t enthusiasts (proud of code?), people with wildly different experience (I’ve got 10 really lines shitty of AutoIT that keep bringing me money, probably not what you want to hear), people in jobs they can’t talk about in details (obvious). It’s a cool question for many people, but I wouldn’t want to miss out on the rest.
Not really: idiomatically, build.rs should generate code to OUT_DIR and not to the src, and that would be quite a different pattern. But yeah, I should’ve added build.rs approach as penultimate one.
Between build.rs writing to OUT_DIR, and test modifying src, I find that test work better, when it is feasible:
Generated code is human visible.
If this is a library, than reverse-dependencies don’t have to run build.rs (build-dependencies are contagious, while dev-dependencies are not).
With tests, you get more control over when the code generation is run, which is helpful when you hacking on code generation itself. More generally, build.rs is a pain to debug.
Kinda esoteric, but tests allow reflectiony-things – unlike build.rs, the test has access to the crate itself, so it can use types defined therein. As an example, in rust-analyzer we use the real Config type we use at runtime to generate documentation (source)
However, if you want the output of code generation to actually not be reproducible, and instead depend on the host where the compilation is happening (this is useful, to, e.g., bind to system’s libraries), build.rs is the only way to go. That’s the core difference between two approaches: one runs code generation at build time, another at development time.
As an aside, I always found it disagreeable that Rust assumes tests are only run during development. I can see many reasons (different platforms, different versions of dependencies, to name a few) why I as a user would want to run tests of a crate I use. But maybe I am missing something.
Hm, I don’t think Rust assumes that? You can run tests of dependencies. For example, in rust-analyzer I can do cargo test --package num_cpus to check if that dependency works.
Though, to be fair, this often fails (with a nice error message) if the dependency in question have dev-dependencies. Cargo intentionally doesn’t prepare dev-dependencies of dependencies, so it can’t compile tests using those. But it doesn’t seem to be a fundamental limitation – I think it would be feasible to make cargo test --package dep for any dependency, it just needs some code and design legwork (eg, how lockfiles and transitive dev dependencies interact).
In practice, when I want to run tests for my dependency, I usually just checkout the dependency locally and run the tests there.
Nice article. The author correctly identified places that newcomers feel uneasy with in Rust:
needing to always name all the trait bounds. There’s a RFC for that and I hope it gets implemented this year
lifetimes are something I continuously explain. Though I still feel that the great error messages make up for any trouble you have declaring them
macros may sometimes be overused. The risk of having a hammer, I guess. That said, when used with some care, you can get great results. Serde is a good example here, because the derive macros bridge arbitrary formats and data types
error handling: Just have fn main() -> Result<(), Box<std::error::Error>> { .. } and use ? everywhere.
And ATS, which provides the ability to do pointer arithmetic and dereferencing safely without garbage collection. In general, claims of “only one that does” and “first to do” should be avoided.
It depends a bit on how you define garbage collection. I’ve seen it used to mean both any form of memory management that does not have explicit deallocation or specifically tracing-based approaches. Swift inherits Objective-C’s memory management model, which uses reference counting with explicit cycle detection. Rust uses unique ownership. C++ provides manual memory management, reference counting, and unique ownership.
Ada isn’t completely memory safe, though I would say it’s a lot safer than C or C++ with all of the additional built-in error checking semantics it provides (array bounds checks, pre/post conditions, numeric ranges, lightweight semantically different (derived) numeric types, type predicates). I’ve found it hard to write bugs in general in Ada-only code. It’s definitely worth checking out if you haven’t.
As for modern C++, it feels like we made these great strides forward in safety only for coroutines to make it easy to add a lot of silent problems to our code. They’re super cool, but it has been a problem area for myself.
Rust is also not completely memory safe: it has an unsafe escape hatch and core abstractions in the standard library as well as third-party frameworks require it.
I agree. Not a lot of people are familiar with Ada, so my point was to dispel the myth it is completely safe, while also answering the common reply I’ve seen that “Ada isn’t memory safe, hence you shouldn’t use it.”
One could say that everything that deviates from manual memory management is some form of GC. Still, we do have the traditional idea that, generically speaking, GC implies a background process that deallocates the objects asynchronously at runtime.
If you think about it, stacks are GC because they automatically allocate and deallocate in function calls. 🤔 That’s why they were called “auto” variables in early C.
Galaxy brain: malloc is GC because it manages which parts of the heap are free or not. 🤯
ahahah great viewpoints, wow I learned so much with your comment, it got me looking into “auto” C variables. never realised that all vars in C are implicitly auto because of the behaviour that they get removed when they go out of scope 🤯 (I wonder how did they got explicitly removed back then? and how it all relates to alloca()? could it have been designed that way to allow for multiple stacks at the same time with other segments besides the stack segment?)
that last bit about malloc is amazing, it is indeed managing virtual memory, it is us who make the leaks 😂
all vars in C are implicitly auto because of the behaviour that they get removed when they go out of scope 🤯 (I wonder how did they got explicitly removed back then?
Back in the day, as I understand it, there was no “going out of scope” for C. All the variables used by a function had to be declared at the very top of the function so the compiler could reserve enough stack space before getting to any code. They only got removed when you popped the stack.
Hmm, helpful, but perhaps not as helpful as it could be.
“Linked lists” could be better described as “cyclic data structures”. For most graph algorithms I’ve seen the adjacency-list representation is more convenient anyway, so I tend to find graphs represented as nodes and pointers to be something of a white elephant. I’m far from an expert though.
Self-referencing data structures are now possible with Pin, though reading the docs there still are probably enough to convince anyone that they don’t want want a self-referential data structure after all.
The main reason not to have global mutable state, besides the sanity of the person who has to read the code later, is thread safety. They talk about mutexes and such but never say “global mutable state becomes unsafe once you have threads”.
All in all a good post though. As for initializing an array without re-initializing it, I had to give it a go and see what happened. The results were, hilariously at once more and less than I could hope.
True, the problem with doubly linked lists (as well as other cyclic data structures) is indeed the ownership being muddled.
Yes, you can build self-referential data using pin, but why do it by hand when you can use a macro?
Regarding global mutable state, I have a // I solemny swear that I'm up to no good, and also single threaded. comment in the code example, but perhaps that was too easy to miss.
Thanks for sharing, here! I like this approach to trying to learn Rust, because there are a handful of patterns in other languages that aren’t feasible in Rust
I’d say there’s a difference between “here’s some useful Rust stuff, btw use our logging SaaS at the end” and “here’s why you should use our logging SaaS”
Personally, I don’t mind it. There’s a lot of great and interesting content out there published by companies that usually includes some sort of “ad” for their service. I don’t want to cut that out just because they say, “hey, use our stuff” at the end. Especially because I can just ignore the ad bit and still learn something.
This is a blast from the past. Seeing my old 2016 quote in the introduction brought up some memories. Also the fireflowers blogstravaganza has a longer version of that quote.
mrustc can compile Rust to C. So it doesn’t depend on LLVM (with some caveats). Also fuzzing cannot match static guarantees. The former is: “I did a search through all code paths I could find and didn’t find a bug”, whereas the latter is “there may be no bug, no matter what code path is taken”.
Case in point: I once had a bug in a string handling library that was extensively fuzzed, but all that fuzzing didn’t find the UTF-8 short space character that led to a byte index landing within a UTF8 character.
Would it ever be possible or desired for a variable to check for common traits as a secondary option when the types of the branches of its assignment don’t match up? In this case, inferring impl Read for that variable in your example.
I suspect this is not a desired feature primarily because it would lead to some very confusing errors and behavior, but it also seems more correct than having to go through an initial, superficially superfluous, binding process.
Esteban Kuber already told me that there’s some logic in the Rust compiler that will lead to nicer error messages in some cases already; just the (quite special) case I was showing in my blog wasn’t covered yet.
I’ve tried it a few times during the last months but always returned to helix when lapce either crashed, stopped, consumed 100% CPU or otherwise behaved erratically.
That said, I like the idea of having a non textmode editor at my disposal, and I’m certainly not wed to modal editing.
Ah this is great. I’ll migrate to this when it gets more stable.
btw: the
mltag is for the ML-family of programming languages, like OCaml, StandardML, etc.Thanks! Will you need filter feature like https://qdrant.tech/articles/filtrable-hnsw/?
Yes
We have a blog to illustrate the filtering feature: https://modelz.ai/blog/pgvecto-rs-condition-filtering
Gotcha. Are you using qdrant, pinecone, or something else?
qdrant
Hi, Qdrant DevRel employee here.
Why do you intend to migrate from Qdrant? Is there a specific thing you are unhappy with? Or is there a missing feature that would persuade you to stay?
I’m loving the attention here :) — no, the thing I’d be hoping to gain is tighter integration with the rest of my data. For most of my data, I can use transactions, constraints, foreign keys, etc. But for Qdrant, it’s an external system where I have to build that stuff in myself. TL;DR the usual arguments against NoSQL or eventual consistent systems.
Yeah, I think in some cases you just do not need a specialized vector db. We have a blog post for it: https://modelz.ai/blog/pgvector .
PS: I also like the qdrant project.
That’s interesting! So I suppose the rest of your data is in Postgres? How would you like to integrate it further?
I’m asking because I’m currently prototyping a Postgres extension for Qdrant. It’s just a proof of concept at the moment, but I think it might be valuable to get to know the requirements actual users have.
Hi, we already implemented the pre-filter in pgvecto.rs. We will release it and write a blog post for it. Will let you know!
https://github.com/tensorchord/pgvecto.rs/commit/4ba136052cc9420528bc5fa463570113f0f181e5
I love the cheap chunk lookup by counting leading zeroes in the index! That’s a useful idea independently of the lock-free-ness. It can be useful to have a cheap-to-grow vector with stable item references; sometimes I use a std::deque for this in C++, but I don’t know if it uses the doubling chunk size trick.
I would move the “stored” flags out of the items, into a parallel bitmap, to save space.
This vector can support overwrites (set) as long as the value type doesn’t require freeing (isn’t Droppable, in Rust.) Or it could support moving an item out, I think.
Unfortunately, the value types would need to be atomically updateable to make overwrites sound, because threads reading in parallel could experience tearing. This can, alas, only be fixed with some form of locking (e.g. a “locked” flag that gets set before writing and unset afterwards, in combination with a spin lock on the reader side) to keep readers from examining the value until it’s completely written.
That’s true; I was thinking of values either being smallish or references, both of which can be updated atomically. (IIRC many current 64-bit CPUs can atomically store 128-bit values.)
You are correct: 128-bit atomic operations have been supported for many years. They are useful for tagging pointers in lock-free data structures to avoid the ABA problem.
Specifically you can’t CAS a pointer assuming it uniquely identifies a single object for all time. An object could have been freed, and a new object allocated with the same address. Instead you should CAS a (counter, pointer) pair or similar.
I think the article already deals with the same issue at initialization time:
So you’d just set this flag at the start of any update, and clear it at the end, and the readers would use the same logic they already use to safely handle the fact that initialization may be non-atomic. (Importantly, in this data structure the entries aren’t lock-free, but the vector-as-a-whole has no global lock that blocks all concurrent readers).
Author here. This was an experiment to see if I could create a semantic search from free services (for non-commercial use, in one part limited to one year after which it will cost a few pennies) that people could use on their personal websites.
As a cloud sceptic, I expected a lot of decorum, and indeed, the first steps setting up the function were a bit jargon-laden for my taste, but afterwards using the cli and writing the code was surprisingly smooth thanks to Rust + the lambda libraries.
This is old news; it was a semi-troll-ish response to the first trademark policy draft which had people wondering if they can still say “Rust” out loud without summoning a register of lawyers.
More full-troll-ish… anyone who had even the most cursory understanding of trademark law knew the policy was absolutely fine and didn’t substantially alter what they already could (or could not) do with someone else’s trademark.
A semi-troll-ish move would be to fork their fork and call it GreenGlandLang… for those who know that crabs habitually urinate in their own faces.
Yeah, this is part of the problem with soliciting the community for feedback. Developers are not at all qualified to read legalese and have no idea how trademarks work.
There were some issues with the policy, but nothing glaring, and nothing nearly as bad as people were implying, like “omg they can sue us for writing rust”.
Python is not a bit younger than Java, it’s the other way around. Python 0.9.0 came out in 1991 and Java 1.0 alpha came out in 1994.
Well, Python 1.0 also came out in ‘94, and Java was called Oak before being renamed to the hot brew we all know and love. But I’ll gladly admit one could argue either way.
Thanks, I wish people would be more vocal about this. The “hard” part of Rust is learning the language, the hard part of so many other languages is learning the quirks and bad design decisions. You learn the former upfront, you learn the latter from incidents.
I don’t know. I have a static site generator that I ported from Python to Go to Rust and now back to Go. The first three were just ways to explore new languages, but the final iteration was “I actually use this, and the Rust version is really hard to maintain” (specifically, despite being more elegant and performant, adding functionality was so much more cumbersome for minimal benefit even as someone who knows Rust pretty well by now).
Additionally, I made more mistakes writing the Rust version than the first Go version despite having the benefit of hindsight and a robust type system. I flubbed some filepath/URL manipulation code in large part because I was so focused on the type system (making decisions about borrowing vs cloning).
In a separate project, I was dealing with a lot of integer IDs which identified different kinds of resources—in order to make sure I used the right ID for the right resource type, I wanted to create an integer newtype (
struct FooID(u64)), but there was a lot of tedium in making all of the necessary arithmetic and conversion traits to have something that was basically usable as an integral type and I still had a couple of frustrations: (1) I still couldn’t automatically instantiate a typed variable from an integer literal a la Go’sx = 0; rather, I had to typex = FooID::new(0)orx = 0.into()or similar and (2) I couldn’t use those arithmetic traits in const contexts, so I had to define a bunch of const functions with similar names. Go just kind of does what I want out of the box—it doesn’t let me implicitly convert between types, it lets me do const arithmetic, and I can instantiate variables from untyped integer constants. If I had to do it again, I’d be tempted just to use u64s for everything (I’ve seen quite a few projects do the same, but I’m not sure which approach is idiomatic), but this is definitely going to yield more bugs.I’m glad to hear that you found a good tool for your job. So do you feel that you can write robust misuse-resistant interfaces in Go? What are your techniques for achieving this?
I’m not sure what you mean. I don’t have many problems with people misusing code. Usually the type annotation makes usage pretty obvious and where it isn’t obvious, I add a small, precise, clear comment. Mostly though I try to keep my interfaces as simple as possible.
I’m not saying Go is perfect; const and Rusty enums would be great, and I would love better compiler optimizations. But Go is just wildly more productive than Rust for most applications in my experience (productivity is not always the most paramount concern either).
Yeah, when I wrote some Go, I was missing enums dearly. Also the ? operator; the error handling gets quite wordy. I still think that it’s mostly down to familiarity: Having written Rust code for some time, I can now write stuff in Rust faster than I could in Go, while I allege that someone who’s more fluent in Go will have a contrary experience.
I don’t think it’s just fluency. I’m wayyy more versed in Rust than say TypeScript (like nearly 10 years more experienced), but I’m wayyy more productive in TypeScript. I agree that error handling in Go is more verbose than in Rust if you’re not adding context to your errors, but I prefer to add context for debugability (
fmt.Errorf(“doing foo: %w”, err)). You can do this in Rust withanyhowbut that seems like bad practice for library code. Further, I spend a lot of time in Rust crafting error enums and setting up the necessary traits (including convenience traits likeFrom).thiserrorhelps but I still find myself fighting compilation errors in the generated output. Similarly, I also agree that Rust enums would be nice in Go, but unless I’m writing a compiler or something that is just enums all the way down, I just make a struct with a tag field or use interfaces and move on with life (definitely a loss of safety, but I can move so much faster than with Rust that I have plenty of time to test).I don’t want to push you to return to Rust if you didn’t like it, but I think this is a use-case for
ambassador(or delegation, the non-existent built-in equivalent). (Using a procedural macro likeambassadorsurely will not reduce the difference between Go’s and Rust’s compilation speeds, though….)I don’t think I understand why one would want integer newtypes used as IDs to support arithmetic, though.
I should note that I still like Rust; I just don’t relate to some of the comparisons with Go. Specifically, Rust is great for systems programming or high performance programming; basically stuff where C and C++ is used today. I also like Rust in theory—the emphasis on zero-cost abstraction and so on.
A filesystem needs to convert between block numbers and byte offsets and so on.
Ah, I had been thinking of otherwise meaningless identifiers (such as
mio::Token,id_arena::Id, and a number of types in Salsa).To give a background why is that: UB is not an event that happens in the program. Instead, “UB is impossible” is an assumption that is baked into the compilers.
The compilers don’t have
if is_UB() { screw_you() }anywhere. The no-UB assumptions can be implicit and pervasive. Like an assumption that opposite oftrueisfalse, soif (x) {do}andif (!x) {} else {do}are equivalent. If you magically made a 3-valued bool withfilenotfound, then it’s not merely triggering someelse { lol() }code path in the optimizer. Instead, it makes all the assumptions about boolean algebra invalid and full of impossible-to-reason about paradoxes. And it’s hard to warn about this, because UB is not an event or a code path. The compiler would have to warn about every non-issue like “here I’ve assumed that the opposite offalseistrue”.The second reason is dealing with complexity of optimizations. It’s too difficult to optimize code in the high-level form you write it. There are too many tree structures to work with, too many scopes, too many constraints to preserve. Instead, the code is “lowered” to a simpler assembler-like representation that no longer resembles the source code. In this form programmer’s intention is hard to see, so it’s no longer obvious what should and shouldn’t be optimized out.
To manage the complexity, optimizations are applied to low-level code in multiple independent passes. This way instead of having to consider all of the C spec for any change, each pass can focus on one thing at a time, e.g. “can I change
!!xtox”. There’s a pass that simplifies arithmetic, there’s a pass that checks which expressions are always true, and there’s a pass that removes unreachable code. They can end up removing your null or overflow checks, but they don’t mean to — each pass does its own thing that in isolation seems sensible, spec-compliant, and is useful for most of the code.And finally, majority of the optimizers in C compilers are shared across all architectures. They evaluate code as if it ran on the hypothetical portable machine that the C spec describes, not your particular CPU. So it doesn’t matter that your CPU knows how to overflow a signed int or has caches coherent across threads. The low-level virtual machine the optimizer optimizes for doesn’t have that, and code under optimizer will “run” in the C way instead.
This is a great explanation, but substitute ‘integer’ for ‘boolean’ and you get why C compilers really like that signed integer overflow is undefined. If you write something that loops performing some addition on an integer, then you have an induction variable that can be modelled as an arithmetic sequence. If you have a nested loop, then the induction variable can be modelled as a geometric sequence. This model is completely wrong in every regard if adding two positive values together can result in a negative number. Having to understand this case precludes any transform from making use of this information. This precludes a large number of loop optimisations.
But isn’t that just as true of unsigned integer overflow? You don’t unexpectedly get a negative sum, but you do get one that’s completely wrong.
Signed overflow is UB so compilers get to pretend it can’t happen. The lack of UB on unsigned integer overflow means that many compilers don’t optimize unsigned arithmetic nearly as aggressively, for precisely the reason you point out. The difference is that compilers aren’t allowed to ignore the possibility of unsigned overflow since it’s well-defined and allowed to happen.
My favorite example of undefined behavior: creating a pointer into the stack and messing around with its contents. In C or unsafe Rust or something like that, compiler has literally no way of preventing you from doing this, and no way of detecting that it has occurred. It’s not even “this is on you to make it safe” territory, because the compiler is allowed to assume the contents of the stack doesn’t change out from underneath it… it may juggle local variables in and out of registers or something and, within the bounds of the calling convention, you get make zero assumptions about how it works. Just ‘cause one compiler puts a particular local var at
[rsp+24]or whatever doesn’t mean it will be there the next time you compile the program.Yes, you can do it. You can even make it work, if you know exactly how the compiler works and the compiler doesn’t change. But you’re breaking the invariants that the compiler fundamentally uses to function, and it is incapable of noticing that you are doing it.
Wait, what? How do you create such a pointer, exactly?
You’d have to use assembly code I assume? Or some library that uses assembly code?
The alloca function returns a pointer to memory allocated on the stack! I’m surprised it hasn’t been mentioned in the thread yet.
https://www.man7.org/linux/man-pages/man3/alloca.3.html
D’oh! Of course, how didn’t I remember that? Thanks!
Edit: goes to show how often that function is used, hah!
…You mean playing around with the stack isn’t the first thing everyone does when learning how C works?
https://godbolt.org/z/GYzq87G4s
(Update: Notably, if you pass
-O3to most versions of gcc in godbolt it will generate the code you expect, but clang will almost invariably nope out and just return 1 or 0 or nothing at all. Fun!)That’s not what I imagined a pointer into the stack would be from your description.
That’s a pointer into a local variable. The compiler wouldn’t even allocate stack space if you compile with optimizations.
Pointers to local variables are not UB.
Edit: What is UB in this case is that you incremented “
b” outside the array bounds (a pointer to a single object is considered to be a pointer into an array of 1 element).Edit 2: You can freely use such pointers while the compiler passes variables into and out of registers and your program will still work just fine. But your pointer is not allowed to go outside the bounds of the array (except to point one-past the array, but then you can’t dereference it).
You are correct, the UB in this case is incrementing the pointer out of its bounds. The thing is that a local variable (edit: usually) has to exist on the stack if you have a pointer to it that does arithmetic. So the easy way to get a pointer to a random place on the stack is to start from a local variable. You can also have a function that returns a pointer to a local var, you can start in the data segment or heap, or you can just make a good guess of where your stack is and hope ASLR doesn’t ruin your fun.
Or if you really want to go hard, you can ask a user to type in a number and use that as an address. Who knows what they’ll type in? The compiler sure doesn’t.
What? No, that’s not true. See for yourself: https://godbolt.org/z/PvfEoGTnc
No, you don’t necessarily get a pointer to a random place on the stack if you do that. The local variable or array may not even exist on the stack.
If you go outside the object/array bounds with pointer arithmetic, you get UB which does not have to (and many times won’t) translate into a random pointer, it will just mean that your code will break (and it can break in many different ways).
You should really, really, carefully read @kornel’s top post to understand how UB works.
That’s UB but again, you won’t necessarily get a random pointer to the stack, as the variable may not even exist on the stack. And even if it does exist, your code can break in completely different ways than getting a random pointer to the stack.
You’d get UB if your pointer goes outside of a malloc()-allocated area, but again, you wouldn’t necessarily get a pointer value. You’re making the exact same false assumptions that @kornel talks about.
Your code could simply be completely optimized out, or it may cause other very strange effects that have nothing to do with pointers.
Even if you knew exactly where your stack is, I don’t think there is a way to deterministically create such a pointer without implementation-specific behavior (e.g. assembly code).
Edit: updated Godbolt link due to a typo in the code.
I believe converting an arbitrary integer into a pointer is also UB and you don’t necessarily get a pointer like you think you will, your code can just completely break in lots of different ways (including simply being optimized out).
You’d have to enable some kind of special implementation-specific compiler option to do something like that without UB.
What is not UB, I believe, is to e.g. pass a pointer value into an
intptr_tvariable and then back into a pointer without changing the value.And yet this is also how just about every device driver under the sun works.
Because of this:
Edit:
Correction: technically speaking, it seems that the integer-to-pointer conversion itself is not UB if you use an explicit cast, but the C standard says the result is implementation-defined, so the code can behave differently depending on which compiler (or compiler version, or compiler flags) you’re using.
In fact, the C standard says that the resulting value can be a trap representation, which means that it could trigger UB as soon as you tried to do anything with that pointer.
Even if your implementation allows doing that and even if the integer is a valid memory location, I would imagine it would still be possible to trigger UB by violating other constraints, like creating a duplicate copy of another pointer of a different type (which could violate strict aliasing constraints), or creating a pointer with the wrong alignment, or calling
free(ptr)if the memory location hadn’t been allocated withmalloc()before, etc.The int-to-ptr operation is actually fundamentally implementation-defined. So you won’t find the UB rules for ptr-to-int and int-to-ptr in the standard, you need to look at the LLVM LangRef instead.
Yes, I mentioned that in my other reply.
But note: it is undefined behavior if you don’t use an explicit cast, e.g. if you do this:
int *a = 4, then it is UB.Why is it not a compile error?
It is a compile error:
https://godbolt.org/z/Gq8qbW559
But that’s on GCC (probably clang does the same). There might be C compilers that are C-standard-compliant that might not generate an error.
If you are asking why doesn’t the C standard specify that such conversions are invalid rather than UB? No idea!
Edit: oh wait, I made a mistake! The above error is when compiling in C++ mode (the Compiler Explorer’s default, annoyingly). In C mode, it’s not an error, it’s a warning by default:
https://godbolt.org/z/rP3KoGbx3
That said, you can transform that into an error by adding
-Werrorto the compiler flags, of course.I don’t think this is the kind of error you’re expecting to see - if you change the code to
int *a = (int *)4it should compile without warning. I don’t know if this is even supposed to be undefined behaviour - when talking to devices you need to know the exact memory address “as a number” and write to it or read to it (think VGA video memory addressing and such), which is or was traditionally often done in C under DOS in real mode, for example.Although it might be that this has sort-of been retconned into “always having been wrong” like relying on hardware behaviour on integer overflow has been.
Local variables are generally allocated on the stack. In some cases, it may be able to not allocate memory at all and keep the local variable purely in a register, but any time you mess around with pointers to local variables – especially when those pointers are passed across non-inlined function boundaries – that pointer is to the stack-allocated local variable.
With optimizations disabled, you can look at the assembly code and stack frame and verify that ‘a’ is allocated on the stack and ‘b’ is a pointer to that stack-allocated variable in icefox’s example. Here’s a slightly modified example where the pointer is passed across a function boundary to be dereferenced: https://godbolt.org/z/x8zEKEr1E
Yes, I know that, but @icefox was talking about “creating a pointer to the stack”, but as far as I can see there is no way to create a pointer to the stack in the C language, or at least no portable way to do it (i.e. without relying on implementation-defined behavior).
The C18 standard, as far as I can see, doesn’t even have the word “stack” in the 535-page document!
Someone else mentioned
alloca()but even that is not part of any standard.Then he said:
Which seems to make little sense because if you’re relying on implementation-defined behavior (which has to be documented) to create a pointer to the stack, then that means that the compiler has already promised to give you a pointer to the stack. So of course it can’t prevent you from messing around with it.
It’s not like you “tricked” the compiler into giving you such a pointer, usually it’s actually the opposite: the compiler is the one who tricks you into thinking that you have a pointer to the stack when in fact the local variables (and even arrays) that the pointer points to, may only exist in registers or, since all the values of the variable might be possible to determine at compile time, may not exist at all!
Edit: That said, yes, I understand that if you rely on implementation-defined behavior then it is possible to deterministically create such a pointer (e.g. with
alloca()) and mess around with it, such as corrupting the stack and causing UB. Which is what I meant when I said that you’d have to call some (platform-specific) library function to do that, it’s not like there’s a construct in the C language that says: “this is how you create a pointer to the stack”.Edit 2: clarified the comment a bit.
You can’t find the word “stack” in the C standard because the C standard indeed has no concept of a “stack”. As far as the standard is concerned, local variables have automatic storage and are alive until the function returns, variables allocated with
mallocand the like have allocated storage and are alive until they are freed withfree.However, the common implementations have a chunk of memory they call “the stack”, where each function gets a sub-chunk called a “stack frame” which is where the compiler puts, among other things, the variables with automatic storage (except for those variables which it optimizes out or keeps in registers only). Therefore, when you take the address of a variable with automatic storage, the implementation will give you an address to the place in the function’s stack frame where that variable is kept; you have a pointer to somewhere in the stack.
There is some mixing of abstraction levels here. You never have a “pointer to a variable allocated on the stack” in terms of the C abstract machine, you have a “pointer to a variable with automatic storage”. But when we lower that into the level of concrete machine code for some operating system, we can see that in the right circumstances, our “pointer to a variable with automatic storage” gets lowered into a “pointer to a chunk of memory in the function’s stack frame”. So we can create an example program which proves @icefox’s point (namely that the “compiler has literally no way of preventing you from doing this, and no way of detecting that it has occurred”):
a.c:
b.c:
No individual function in this example does anything wrong, but in combination, they mess around with the stack in ways which the implementation can’t anticipate.
You don’t actually know if they mess around with the stack, they may very well not. With link-time optimization all of that code could be inlined together and no pointers to the stack would even be created.
What you are saying is actually a result of the following:
The pointer points to a single object, rather than a sufficiently-large array of objects. Which results in UB when you do pointer arithmetic past the bounds of the array.
Or, in other situations, it could result in UB due to dereferencing a pointer past the lifetime of the object (which could happen both for automatic storage and for heap-allocated storage).
It has nothing to do with “the stack” or a “pointer to the stack”. It is simply the result of having “a pointer” (to some non-permanent storage).
You are assuming that a specific implementation detail will happen. How do you know that’s what will happen? Does your C compiler or some other standard guarantee that? I assume the compiler documentation or a calling convention such as the System V ABI may be able to guarantee that. But if it does guarantee it, how is that “the implementation not anticipating”?
Edit: API -> ABI
I don’t understand what you are disagreeing with me about. Clearly, we have some C code, where all translation units are correct in isolation, but in common implementations, their combination might (and likely will, but is not guaranteed by any standard to) result in machine code which messes with values on the stack in a way the compiler can’t account for. That much is inarguable, and I don’t see you claiming otherwise; so where is the contention?
Indeed, that is correct.
The contention is in the following two points:
I think that phrase is a bit misleading, because:
Which means that the compiler can prevent you from doing that. And if it can’t, it’s probably because you’re relying on the calling convention which is implementation-defined behavior, therefore documented and the compiler would be doing it on purpose.
The other contention point, which I admit is (even more?) pedantic, is:
That said, yes, I understand that when going outside the bounds of a pointer (for example) to heap storage is unlikely to corrupt the stack (even though it’s possible) and that stack corruption is a very particular type of corruption which usually has very… interesting side-effects!
So in conclusion, I think we are in agreement with regards to the underlying issues, I just disagree with the phrasing and particularly, how it appears to be suggesting that the compiler is powerless to prevent it, when in fact you’re either breaking the invariants of the language itself, or the compiler is actually going out of its way to help you do that, on purpose (just in case you like to shoot yourself in the foot)!
Edit: “external library” -> “library”
Edit 2: in other words, you haven’t really forced the compiler to give you a pointer to the stack, it was the compiler who decided to give that to you, and it could just as easily have decided to do something else if it wanted (proof: the existence of conforming C compilers for architectures that don’t even have a stack).
So you would be completely happy with:
Personally, I think the original comment was clear enough, adding all those caveats just muddies the meaning IMO. But I won’t disagree that it’s assuming a few things which aren’t strictly guaranteed by the C standard.
Well, you are breaking the invariants of the language, but I don’t understand how that means the compiler can prevent it. The compiler gives you a pointer to a variable which the complier has decided to put on what it calls “the stack”. The language has features which make compile-time tracking of where pointers come from impossible. The language has features which lets you do arithmetic on pointers. Given those facts, if a compiler is implemented in such a way that there exists a stack which contains stuff like the return address and local variables, the compiler is powerless to prevent you from messing with stuff the compiler has to assume is left unchanged.
I agree that a compiler might be implemented differently, it might store the return address stack separately from the variable stack, it might allocate every local variable in a separate heap allocation and automatically free them when the function returns, it might do runtime checking of all pointer dereferences, or any number of other things. But under the assumption that the implementation works roughly like all the major C implementations currently do, everything icefox said is correct.
This phrasing is also wrong. The compiler can do all of those things and yet the pointer is not a pointer to the stack, it’s a pointer to the variable (which may currently be stored in a register or even may only exist as a constant in this exact moment, even though there’s an allocation for the variable in the stack).
For example if you have this code:
… it may not do what you think it does. Why? Because the compiler is allowed to transform that code into this equivalent code:
So even if there’s an allocation for
x[]in the stack frame for some reason (let’s say some further code manipulates the array), you think thatyis a pointer to the stack, but it may very well not even exist as such, even if the code forsome_functionhasn’t been inlined!And even if you call
some_function(y, true)instead offalse, you think you tricked the compiler into corrupting the stack, but the compiler can clearly see thatypoints to&x[50]so increasingyby100000is absurd and the entireifblock of the specializedsome_function()implementation can be removed.So yes, the compiler can prevent you from messing around with the stack even in that case.
Yes, you said it very well here, even though that doesn’t always happen. The compiler has decided. You haven’t forced it to do that. The compiler could have decided something else. It was an implementation choice, which means the compiler could have prevented it.
Exactly! Which means that the compiler can actually prevent you from doing the things icefox said.
Well, it’s not possible for me to prove this, but to be honest, I think icefox had a misconception, as evidenced by the fact that (before he edited it) his reply to my comment said that just doing pointer arithmetic on a pointer to a local variable means that the compiler is forced to give you a pointer to the stack, when this is not true: compilers often optimize such pointers out of the code completely.
And you know, this entire debate could have been avoided if he just said “it’s often possible to corrupt the stack [perhaps by doing such and such], which has all these interesting effects” rather than suggesting that C compilers have some underlying limitation and are powerless to prevent you from messing with what they do.
But you know, apart from that, I think we are in agreement!
Edit: renamed function name to clarify the code.
I would say, it doesn’t matter that virtually all CPU in active use since… say the start of the 21st century, know how to overflow a signed int. Some platforms somewhere that existed at some point in time don’t know how to overflow signed integers, and so the standard committee thought it was a good idea to mark it “UB”, probably for portability reasons, and the compiler writers later thought it was a good idea to interpret it literally, for optimisation reasons.
This is where the standard committee should really have said something along the lines of:
Sure, the specs are wordier this way, but that would have gotten rid of a huge swath of security vulnerabilities. And while some code would be slower, compiler writers would have told everyone they should use unsigned
size_tindices for their loops.But no, they didn’t define behaviour depending on the platform. If something is undefined in one supported platform, no matter how niche, then it’s undefined in all supported platforms. Just so it could be a little bit faster without requiring users to touch their source code.
My understanding of undefined behaviour is now as follows: compilers will, in the face of undefined behaviour, generate code that under the “right” conditions causes your hard drive to be encrypted and print a ransom message. The most useful threat model of a compiler is that of a sentient adversary: if there’s any UB in your code, it will eventually find it, and cause as much harm as it can up to and including causing people to die.
A plea to compiler writers: please rein that in?
(post author here)
Unfortunately, it’s not that easy.
The compiler isn’t out to get you, and generally won’t include disk-encrypting code into your program if it wasn’t there before. The line about playing DOOM on UB is meant as humor and to demonstrate that it’s still not a compiler bug if this happens. But in reality, it isn’t actually going to happen in GCC, or Clang, or rustc, or any other compiler that wasn’t purpose-built to do that. It’s not guaranteed to not happen, but compilers are in practice not written to maliciously manufacture instructions out of whole cloth just to mess with you on purpose.
But at the same time, providing guarantees about undefined behavior … makes it not-undefined anymore. There can certainly be less undefined behavior (e.g. mandating the equivalent of
NullPointerException, or Rust’s “safe Rust is UB-free Rust, or it’s a bug in the compiler” guarantee), but any real compiler will still have some UB. UB just means “this is an invariant that I expect and internally continue to uphold, and I don’t know what happens if something breaks it.” Even my toy compiler for the Advent of Code day 23 problem from last year contains a notion of UB, which I plan to discuss in an upcoming episode of my Compiler Adventures blog series – and that’s for a programming language that doesn’t even haveifstatements or loops!I highly recommend this talk on UB if you have 40min: https://www.youtube.com/watch?v=yG1OZ69H_-o
I guess the playing DOOM on UB being humorous is written with MMU-using operating system mindset. I witnessed IRL a situation where a simple read from stdin, do some calculations, write to stdout C program was quite reliably opening CD-ROM tray… That was on Windows 3.11 I think.
That’s amazing :)
My dad once traced a client-reported bug in his company’s software down to a bad CPU in the client’s machine. When adding two very specific 3-digit integers together, the sum was incorrect. It wasn’t UB that time, just bad hardware, but it doesn’t sound like it was fun to track down. And the accountants using the software certainly didn’t appreciate the fact that the computer was adding up their numbers wrong…
Since it’s the accountants’ computer that is broken, they have a catch 22. They need to ask for their money back, but the computer they do all their sums on is broken, so how much refund should they be asking for!? They can’t possibly calculate it. ;)
Correct, but ransomware authors are out to get me, and they’ll exploit any vulnerability they can. And UB driven compilers are a source of vulnerabilities that wouldn’t be there if more behaviour was defined. That’s where my threat model comes from. Blaming the compiler as if it was the enemy isn’t accurate, but it is simpler and more vivid.
Oh, and that talk from Chandler Carruth? I’ve watched it several time, its misleading and harmful. All the more because he’s such a good speaker. He’s trying to reassure people about the consequences of their bugs. Sure the compiler itself won’t actively summon the nasal demons, but outside attackers finding vulnerabilities will. And the result is the same: UB does enable the summoning of nasal demons.
But he’s not saying that out loud, because that would drive people away from C and C++.
Correct, which is why I advocate for defining more behaviours in C.
I think that’s a lost cause. Instead, it would be nice to have more options like
-fwrapvthat at least impose sane behaviour for things that are UB, strictly speaking.Of course, your position is valid: it sounds like you are making an even more conservative set of assumptions than the minimum necessary set.
I wish more people took more precautions than strictly necessary, rather than fewer than necessary as is frequently the case :)
I think the larger point is that, effectively, people who write C have to treat the compiler as a deadly hyperintelligent enemy deliberately attempting to cause as much harm as possible via any means available. Otherwise they just end up being hurt by the compiler, and then when they write it up they get mocked and belittled by people who tell them it’s their fault that this happened.
And since it’s effectively impossible to write useful/non-trivial C programs without UB, the takeaway for me is “don’t ever write C”.
FWIW I feel similarly. I’ve switched to Rust because I don’t trust myself to not write UB and to not commit memory safety errors. I still haven’t needed
unsafein Rust anywhere thus far, and “if it compiles then it’s memory-safe and UB-free” is worth a lot to me.C users as a whole are hostile to any overheads and speed regressions in compilers. Compilers get benchmarked against each other, and any “unnecessary” instructions are filed as issues to fix.
Look how long it is taking to zero-init all variables in C and C++, even though overhead is rare and minimal, and the change is good for security and reliability.
I can’t imagine users accepting speed regressions when indexing by
int, especially when it’s such a common type.I just wrote a whole post trying to explain this couldn’t be further from the truth, so I don’t get what you’re trying to say here.
It’s an oversimplification. There are sentient adversaries out there out to exploit whatever vulnerabilities that may arise from your code. And mr compiler here, despite being neither sentient nor actively hostile, does tend to magnify the consequence of many bugs, or to turn into bugs idioms that many long time practitioners thought were perfectly reasonable.
Thus, I like to pretend the compiler itself is hostile. It makes my threat model simpler and more vivid. Which I pretty much need when I’m writing a cryptographic library in C, which I ship in source form with no control over which compilation flags may be used.
Strictly speaking, undefined behavior allows implementation-specific behavior ;)
For example, you can compile an entire Linux distro with the
-fwrapvgcc and clang flags and you’ll get the behavior you want (i.e. well-defined signed overflow with wrapping behavior).All code that was previously C-standard-conformant will still remain C-standard-conformant. Additionally, code which previously triggered UB on signed overflow now also becomes well-defined.
Although I do sympathize with your point that this should probably be the default even if it has a performance cost, also note that in many cases such well-defined signed overflow can lead straight into UB or a crash anyway, because these integers in many cases are used as array indexes or on array index calculations.
Edit: might I suggest deterministically aborting on signed overflow/underflow? You can use
-ftrapvfor that.I do wonder if one could extend LLVM with a visualization that tells us what optimizations used which assumptions, somehow summarizing on a top-level view while allowing us to drill down to each block. That would be a great teaching and debugging tool indeed.
Apparently you can now see optimization passes in LLVM on the Compiler Explorer, but I don’t think it has assumptions or things like that.
That would be cool! But it sounds quite difficult to be honest. I’ve been thinking about ways to describe and represent information flow in my Compiler Adventures blog series on how compiler optimizations are implemented, and even for the massively-simplified language used there (no loops, no branches, no functions!) it’s still quite difficult to track “who did what where because of whose info.”
Of course this doesn’t say it can’t be done, and I really hope someone takes up that challenge. I’ll be excited to see the results.
I think that e-class (program equivalence classes) graph edges could be annotated with which optimization produced the candidate equivalent program
If your compiler has 10 individual optimizations which get performed iteratively in a total of 30 optimization passes, you could imagine recording the output of every one of the 30 optimization passes and then showing that to the user, allowing him to go to the previous/next pass and see a diff of what changed.
You wouldn’t know exactly why an optimization happened if you’re not familiar with the optimization, but I think it would still be immensely instructive.
Although you’d need different visualizations and diff algorithms for different intermediate compiler languages (C AST, LLVM IR, assembly, etc).
This is a very good way to understand the behaviour of the compiler you’re using.
Fwiw you don’t need to store all the intermediate results if the compiler is deterministic, you can generate the one you want to look at by running all the passes up to that point.
I think you can do this right now with clang? By changing the list of passes and dumping IL.
You can do something like this with ghc-core for Haskell. :)
That is a load-bearing phrase right there :) Making compilers behave deterministically is possible but quite difficult. Folks working on reproducible builds have gone down this road, so we can learn from their experiences.
It might be a topic for a future “falsehoods programmers believe about compilers” post :)
I think in practice they mostly are.
I’d be a quite an ambitious project. Consider how incomplete debug information is in optimized programs. Optimizers already struggle with even the most basic tracking of where the code came from. So tracking all the changes, their causes, and their assumptions would be even harder.
There’s a lot of passes (that’s where majority of compilation time is spent). They are a mix of analysis and transformations passes that aren’t explicitly connected. Some passes even generate new unoptimized code that is meant to be cleaned up by other passes, so it’s hard to track meaningful causality throughout all of that.
Optimizers work on a low-level code representation where your variables don’t exist any more (SSA form), there are no
for,whileorifconstructs, onlygotobetween chunks of assembly-like code (CFG). So even if you collect all the data without running out of memory, filter it down to only relevant bits, it would still be difficult to present it in a way that is relevant to C programmers.There may also be asm optimization passes
Compilers have these in what they call back-ends, which are usually separate from their main optimiser, and are language-independent, so the concept of C’s UB doesn’t exist there any more.
My fav questions:
What good does your company’s existence do for humanity (or the community, depends on the type of compny)? Conversely what bad outcome for humanity are you willing to accept for the financial success of the company?
In the past I weeded out quite a bit of that by making it clear to the recruiter I refused to do any military/defense only projects.
I’m not too fond of coding challenges. People can look at my github and see I can code at a glance. This will needlessly filter out people who are not privvy to the project, are nervous because of the interview situation, or worst of all are bad at live coding (which is unusual to do on the job).
I usually have one question when I interview people for coding positions. I give that question out beforehand and am happy to let applicants prepare for it. The question is: What piece of code are you most proud of (Feel free to brag)?
My GitHub has virtually nothing on it:
None of these things are remotely representative of my abilities. I have significantly more skill and experience writing C++ (most of my career). I’m currently working as an SRE writing lots of bash and Terraform.
Maybe coding challenges are bad. But GitHub is absolute garbage for gauging anything about many developers.
I’m also not fond of coding challanges, but if it there has to be one, I’d much rather take one as described in these article than the contrived, shuffle-things-around-in-arrays-in-two-hours-and-hope-you-don’t-get-stuck-on-some-edge-case or make-some-service-from-scratch-and-hope-it-matches-the-tradeoffs-and-style-preferences-the-reviewer-silently-expects kind.
I think your question will also have a few people who won’t like it. For example: fresh graduates who aren’t enthusiasts (proud of code?), people with wildly different experience (I’ve got 10 really lines shitty of AutoIT that keep bringing me money, probably not what you want to hear), people in jobs they can’t talk about in details (obvious). It’s a cool question for many people, but I wouldn’t want to miss out on the rest.
Instead of doing this via a test, I think the idiomatic approach is to run this code in
build.rswhenever the specific source file changes.Not really: idiomatically, build.rs should generate code to OUT_DIR and not to the src, and that would be quite a different pattern. But yeah, I should’ve added build.rs approach as penultimate one.
Between build.rs writing to OUT_DIR, and test modifying src, I find that test work better, when it is feasible:
build.rs(build-dependenciesare contagious, whiledev-dependenciesare not).build.rsis a pain to debug.Configtype we use at runtime to generate documentation (source)However, if you want the output of code generation to actually not be reproducible, and instead depend on the host where the compilation is happening (this is useful, to, e.g., bind to system’s libraries), build.rs is the only way to go. That’s the core difference between two approaches: one runs code generation at build time, another at development time.
Yeah that makes sense. Pity that
cargodoesn’t exposedev-dependenciesand the crate in a more general fashion, like ascriptssubdirectory.As an aside, I always found it disagreeable that Rust assumes tests are only run during development. I can see many reasons (different platforms, different versions of dependencies, to name a few) why I as a user would want to run tests of a crate I use. But maybe I am missing something.
Hm, I don’t think Rust assumes that? You can run tests of dependencies. For example, in rust-analyzer I can do
cargo test --package num_cpusto check if that dependency works.Though, to be fair, this often fails (with a nice error message) if the dependency in question have
dev-dependencies. Cargo intentionally doesn’t prepare dev-dependencies of dependencies, so it can’t compile tests using those. But it doesn’t seem to be a fundamental limitation – I think it would be feasible to makecargo test --package depfor any dependency, it just needs some code and design legwork (eg, how lockfiles and transitive dev dependencies interact).In practice, when I want to run tests for my dependency, I usually just checkout the dependency locally and run the tests there.
I kind of love that the build process is coupled to running tests here though.
The downside is that
build.rshas to be compiled and run before compiling your crate, thus exacerbating compile time even if the enum didn’t change.Nice article. The author correctly identified places that newcomers feel uneasy with in Rust:
fn main() -> Result<(), Box<std::error::Error>> { .. }and use?everywhere.I’m not sure if this holds, for instance, Swift does memory management without using a GC.
And ATS, which provides the ability to do pointer arithmetic and dereferencing safely without garbage collection. In general, claims of “only one that does” and “first to do” should be avoided.
ATS is the first language to have a “t@ype” keyword.
ATS is very interesting! thanks for sharing it
Check out Aditya Siram’s “A (Not So Gentle) Introduction To Systems Programming In ATS,” it’s a great overview.
It depends a bit on how you define garbage collection. I’ve seen it used to mean both any form of memory management that does not have explicit deallocation or specifically tracing-based approaches. Swift inherits Objective-C’s memory management model, which uses reference counting with explicit cycle detection. Rust uses unique ownership. C++ provides manual memory management, reference counting, and unique ownership.
Both Rust and C++ provide all three.
The problem is that C++ can also provide stuff you don’t want in your code usually - without using an unsafe {}.
Ada meets that definition, too.
Even modern C++ could claim to have run-time memory safety without GC, but that obviously requires the developer to use it correctly.
Ada isn’t completely memory safe, though I would say it’s a lot safer than C or C++ with all of the additional built-in error checking semantics it provides (array bounds checks, pre/post conditions, numeric ranges, lightweight semantically different (derived) numeric types, type predicates). I’ve found it hard to write bugs in general in Ada-only code. It’s definitely worth checking out if you haven’t.
As for modern C++, it feels like we made these great strides forward in safety only for coroutines to make it easy to add a lot of silent problems to our code. They’re super cool, but it has been a problem area for myself.
Rust is also not completely memory safe: it has an
unsafeescape hatch and core abstractions in the standard library as well as third-party frameworks require it.I agree. Not a lot of people are familiar with Ada, so my point was to dispel the myth it is completely safe, while also answering the common reply I’ve seen that “Ada isn’t memory safe, hence you shouldn’t use it.”
Isn’t atomic reference counting a form of GC as well?
One could say that everything that deviates from manual memory management is some form of GC. Still, we do have the traditional idea that, generically speaking, GC implies a background process that deallocates the objects asynchronously at runtime.
If you think about it, stacks are GC because they automatically allocate and deallocate in function calls. 🤔 That’s why they were called “auto” variables in early C.
Galaxy brain: malloc is GC because it manages which parts of the heap are free or not. 🤯
ahahah great viewpoints, wow I learned so much with your comment, it got me looking into “auto” C variables. never realised that all vars in C are implicitly auto because of the behaviour that they get removed when they go out of scope 🤯 (I wonder how did they got explicitly removed back then? and how it all relates to
alloca()? could it have been designed that way to allow for multiple stacks at the same time with other segments besides the stack segment?)that last bit about malloc is amazing, it is indeed managing virtual memory, it is us who make the leaks 😂
Back in the day, as I understand it, there was no “going out of scope” for C. All the variables used by a function had to be declared at the very top of the function so the compiler could reserve enough stack space before getting to any code. They only got removed when you popped the stack.
Hmm, helpful, but perhaps not as helpful as it could be.
Pin, though reading the docs there still are probably enough to convince anyone that they don’t want want a self-referential data structure after all.All in all a good post though. As for initializing an array without re-initializing it, I had to give it a go and see what happened. The results were, hilariously at once more and less than I could hope.
// I solemny swear that I'm up to no good, and also single threaded.comment in the code example, but perhaps that was too easy to miss.Thanks for sharing, here! I like this approach to trying to learn Rust, because there are a handful of patterns in other languages that aren’t feasible in Rust
Glad you like it. And yes, Rust chooses some tradeoffs differently than other languages, which sometimes trips up people new to the language.
This is a helpful article for me, thank you for posting!
Does Lobsters allow posts like these, though? It’s a great article, but includes an ad for a service as the last section.
It’s a useful article until then so it’s worth letting the votes govern its relevance, imo.
I’d say there’s a difference between “here’s some useful Rust stuff, btw use our logging SaaS at the end” and “here’s why you should use our logging SaaS”
Author here, glad you like it.
I will add a conclusive sentence to make the distinction between the article and the advertisement clearer.
Thanks for the article, I didn’t mind the ad. Do you inspect the stack frames non-intrusively via sampling?
if it’s not too intrusive its okay, for example when you can read the article without the ad and you don’t miss big parts of the post
Personally, I don’t mind it. There’s a lot of great and interesting content out there published by companies that usually includes some sort of “ad” for their service. I don’t want to cut that out just because they say, “hey, use our stuff” at the end. Especially because I can just ignore the ad bit and still learn something.
Knowing these impossible cases is quite useful — it can save you from fighting with the borrow checker a battle that you can’t win.
Well, not exactly impossible, just needs a bit of unsafe and – Oh god why are there dolphins swimming in my pretzel bath (undefined behavior)?
This is a blast from the past. Seeing my old 2016 quote in the introduction brought up some memories. Also the fireflowers blogstravaganza has a longer version of that quote.
mrustc can compile Rust to C. So it doesn’t depend on LLVM (with some caveats). Also fuzzing cannot match static guarantees. The former is: “I did a search through all code paths I could find and didn’t find a bug”, whereas the latter is “there may be no bug, no matter what code path is taken”.
Case in point: I once had a bug in a string handling library that was extensively fuzzed, but all that fuzzing didn’t find the UTF-8 short space character that led to a byte index landing within a UTF8 character.
Would it ever be possible or desired for a variable to check for common traits as a secondary option when the types of the branches of its assignment don’t match up? In this case, inferring impl Read for that variable in your example.
I suspect this is not a desired feature primarily because it would lead to some very confusing errors and behavior, but it also seems more correct than having to go through an initial, superficially superfluous, binding process.
Esteban Kuber already told me that there’s some logic in the Rust compiler that will lead to nicer error messages in some cases already; just the (quite special) case I was showing in my blog wasn’t covered yet.