132 karma · joined November 30, 2023
Otherwise, that seems unwise to me. Not every user of a generic type has to be generic. A major selling point of generic types is that you write a library once, then everyone can instantiate it. Even if that is the only instance they need in their use case, you have saved them the trouble of reinventing the wheel.
No colleague of mine may need 10 different instances of any of my generic libraries, but I bet that all of them combined do, and that our bosses are happy that we don't have to debug and maintain 10+ different implementations.
while (i <= x) {
// ...
}
just needs a slight transformation to while (1) {
if (i > x)
break;
// ...
}
and C11's special permission does not apply any more since the controlling expression has become constant.Analyzes and optimizations in compiler backends often normalize those two loops to a common representation (e.g. control-flow graph) at some point, so whatever treatment that sees them differently must happen early on.
I don't doubt that compilers occasionally break language specs, but in that case Clang is correct, at least for C11 and later. From C11:
> An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a for statement) its expression-3, may be assumed by the implementation to terminate.
ProvenCore (https://provenrun.com/provencore/) has a proof that covers correctness (memory safety, and more generally absence of UB, termination, etc.), functional properties (e.g. the fork() system call is a refinement of an abstract "clone" operation of abstract machines), and security properties (memory isolation).
And nouns as interjections.
static inline uint32_t load_le32(void const *p)
{
unsigned char const *p_ = p;
_Static_assert(sizeof(uint32_t) == 4, "uint32_t is not 4 bytes long");
return
(uint32_t)p_[0] << 0 |
(uint32_t)p_[1] << 8 |
(uint32_t)p_[2] << 16 |
(uint32_t)p_[3] << 24;
}
static inline void store_le32(void *p, uint32_t v)
{
unsigned char *p_ = p;
_Static_assert(sizeof(uint32_t) == 4, "uint32_t is not 4 bytes long");
p_[0] = (unsigned char)(v >> 0);
p_[1] = (unsigned char)(v >> 8);
p_[2] = (unsigned char)(v >> 16);
p_[3] = (unsigned char)(v >> 24);
}
All that nonsense about masking with an int must stop. You want a result in uint32_t? Convert to that type before shifting. Done.Now, the C standard could still get in the way and assign a lower conversion rank to uint32_t than to int, so uint32_t operands would get promoted to int (or unsigned int) before shifting, but those left shifts would still be defined as the result would be representable in the promoted type (as promotion only makes sense if it preserves values, which implies that all values of the type before promotion are representable in the type after promotion).
Dependency management is one of those issues. Proofs require an acyclic dependency graph, in order to prevent circular arguments. By intermixing code and proofs, you force everything to fit in a single global dependency order. The point is not that it is impossible (it is possible), but that it is a maintenance nightmare. Sometimes you have to break an otherwise perfectly coherent module into smaller modules, just because you need to insert some other modules between them in the dependency order, that are only relevant to some minor proof. You have to constantly refactor your code as you reason on more aspects of your program. Have you already tested and certified your code and existing proofs? Too bad, your latest proof will require lots of handwaving and recertification to convince everyone that the big refactoring does not threaten the existing properties.
Runnable code stands on its own, and should not be polluted with logical parts for every aspect of the program one may want to reason about.
You can establish any provable property of a program using only basic logical tools: a single precondition and a single postcondition per function, a single invariant per loop, maybe dependent types, a few ghost values here and there, etc, and stuff all your reasoning in them in huge messy conjunctions mixing all the concerns together. That would be the equivalent of using nothing but a Turing machine to write a program. It is possible, it is theoretically appealing, but it does not scale.
Software engineering is a thing for a reason. So is proof engineering.
Rice's theorem implies that automatic static analysis (like Rust's borrow checker) will only get you that far. To go further, you must equip the program with a proof, which can be an order of magnitude more complex than the program.
Don't get me wrong, Rust is excellent for developing security-critical applications. Its borrow checker solves many memory safety and concurrency issues, and its type system more generally forces error paths to be explicit. The next step would be to use deductive methods to check that the error paths cannot be taken.
> make invalid states unrepresentable
That is a nice ideal, but not very practical. You need dependent types for that (for example, a sigma-type that bundles a value in a carrier type with a proof that it satisfies an invariant). They have their uses (e.g. at the interface of a library), but they are a pain to work with. You must build the proof terms together with the runtime values, thus entangling program and proofs into an unmaintainable mess. Oh, and forget about modular proof development: the dependent type encodes every constraint on the value, therefore most types must change across the program when you decide to prove an additional property of the program. You can't just keep the existing proof around and prove something else on top of it.
By all means, please keep some invalid states representable, and cleanly separate the program from its various proofs.
if buffer.len.saturating_sub(buffer.write.load()) >= write_len {
// not shown: check `read` to make sure there's enough free room
buffer.watermark.store(buffer.write.load() + write_len);
buffer.write.store(buffer.write.load() + write_len);
}
I would have to look at the implementation to know for sure, but that part looks incorrect to me. Suppose that the writer has placed a watermark strictly before the end of the buffer, wrapped around, and is about to write a new message; meanwhile, the reader has not reached the watermark yet (and therefore, has not wrapped around), but it has made enough progress to leave room for the writer's new message. In that case, we have write <= write + write_len < read <= watermark < len. As written, it would seem that the snippet above would incorrectly update watermark, whose value is still needed by the reader.It seems to me that watermark need not be atomic anyway: it is owned by the writer when read <= write, and by the reader when write < read. Whoever wraps around implicitly passes the ownership to the other thread. More precisely:
* In the initial state, and until the writer reaches the end of the buffer, read <= write, and the writer owns watermark, whose value is irrelevant. In particular, the reader makes sure not to overtake write, and knows that it must not access watermark.
* When the writer needs to wrap around, it first sets the watermark (possibly at len, if the hole is empty), then updates write. With its usual release memory ordering constraint, the atomic store to write transfers to the reader the ownership of the written messages, but also of watermark.
* Eventually, the reader notices that write has wrapped around, and then uses watermark to know where to stop reading. Meanwhile, the writer may fill the beginning of the buffer, carefully not overtaking read - 1, and never touching watermark.
* When the reader finally wraps around, the atomic write to read transfers to the writer the ownership of the consumed message slots, but also of watermark, and we are back in the first phase.
IOW, watermark has the same owner as the last element of the array.
What do you think? What have I missed?
In order to enqueue an element, you have to change two atomic pointers: tail->next and tail. That cannot be done atomically.
enqueue() assumes that the queue is not empty.
enqueue() happily overwrites current_tail->next even if it is not null (which may happen if some other producer has enqueued something since we read current_tail).
Then there is the old-time favourite ABA problem.
By the way, when used in a loop, compare_exchange_weak is preferred to compare_exchange_strong, and there is no need to reload the atomic every time: compare_exchange_* do that for you by updating the argument containing the expected value.
void fun();
(which you typically find in a header file) indeed does not say anything about the function's arguments. You have to write void fun(void);
to specify that the function takes no arguments. For consistency, you can (and probably should) also use that style in the function's definition, but you don't have to.Anyway, C23 will align C's behavior with C++: void fun() will mean the same thing as void fun(void), whether as part of a function definition or not.
Indeed, but _Alignof(max_align_t) is a good compromise for a default alignment requirement in an allocator interface, which is what eqvinox calls for. Standard C does exactly that: malloc(), realloc(), and calloc() promise that they satisfy _Alignof(max_align_t), but nothing stricter. To reach for extended alignment requirements, your only standard tool is aligned_alloc().
How so? The context parameter identifies the allocator instance. What if the library needs to allocate objects with different alignment requirements with the same allocator instance?
Alignment requirement is just like allocation size (*). It varies from call to call, and generic allocators need to deal with heterogeneous alignments and sizes.
(*) Case in point: Rust's Allocator interface (https://doc.rust-lang.org/std/alloc/trait.Allocator.html) bundles them up in a single Layout object.
Possibly. IIRC Microsoft's CRT does not support aligned_alloc() because their implementation of free() cannot deal with extended alignment requirements, so they have separate functions for aligned (de)allocation. To be fair, they probably do not support posix_memalign() either.
> it becomes a serious pain to go through all allocations and figure out a reasonable alignment value
Sure, you can pass _Alignof(max_align_t) in almost all cases, or have generic (= not reimplemented by each allocator) convenience wrapper functions that do that for you. If you want to pass the least restrictive alignment in all cases, you can enlist the help of a macro, but this is a bit more awkward. For instance:
#define ALLOC(ptr, size) ((ptr) = alloc(_Alignof(typeof(*(ptr))), (size)))
foo_t *p;
ALLOC(p, 42 * sizeof *p);
(Note that this uses the typeof() operator, which should become standard with C23.)Alternatively, the allocator could treat reallocation as a multi-step process ( a) reserve new space, b) move data, c) free old space), with enough state tracking to allow a) and c) to be different calls to the allocator, so that b) could be performed by the caller.
There is no perfect solution to this problem. I suppose that's why C++ does not have a standard reallocation counterpart to new/delete/new[]/delete[].
There is no default alignment if all the functions of the allocator take it as a parameter, but it is reasonable for an allocator implementation to be optimized for a particular alignment requirement such as _Alignof(max_align_t).
4. All functions take the alignment requirement as a parameter. The alignment requirement must be a power of 2. The reallocation and deallocation functions must be passed the same alignment requirement value as was passed to the allocation function when the block was first allocated.
A common motivation for rolling out your custom allocator is dealing with extended alignment requirements. This should be reflected in the allocator's API. uint64_t load64(uint8_t const *b) {
union {
uint64_t u64;
uint8_t u8[8];
} u = {.u8 = {
b[0], b[1], b[2], b[3], b[4], b[5], b[6], b[7]
}};
return u.u64;
}
Type punning through a union is explicitly supported by the C standard, insofar as we do not evaluate uninitialized memory or trap representations. We are fine here, as uint64_t has no trap representations, and must have exactly the size of 8 uint8_ts, as those types have no padding bits.GCC appears to compile this function to a plain unaligned load at optimization level 2, when supported, e.g. on arm64 (see https://godbolt.org/z/frEox67sG).