Is it possible to for the Zig to implement mock_head without UB?

Help
1

I’m new to Zig. After encountering issues in C++, I turned to Zig—a language that caught my eye as a compelling alternative. The concept of “mock_head” mentioned in the title is difficult to explain textually; the best way to understand it is to check the README in my repository:

It includes visual descriptions. Essentially, mock_head unifies intrusive linked list implementations, simplifies coding, and can reduce conditional branches. However, its downside in C++ is that it introduces Undefined Behavior (UB), causing some tests to fail. While I have a closed-source refactored version that passes tests, the UB isn’t fully eliminated—which remains a latent risk. In short, C++ seems unable to implement mock_head without UB, leading me to search for a language that could achieve this idea with zero overhead and no UB. That’s how I discovered Zig.

In C++, mock_head violates object boundaries, lifetime rules, and potentially strict aliasing—multiple violations in total.

Admittedly, mock_head has other drawbacks, such as making some lists self-referential and move-only. But I’ve noticed Zig’s powerful compile-time capabilities might allow controlling mock_head via a compile-time parameter to support more scenarios. Further, we could validate at compile-time whether a node’s memory layout meets the conditions for enabling mock_head.

Since I’m just starting with Zig and unfamiliar with its features, I’d greatly appreciate your insights. Thank you!

2

Hello,
if i am not mistaken all linked lists in zig std are intrusive (singly linked for example).

Overall intrusive data structures are really easy to do in Zig via @fieldParentPtr().

To the case of UB, i dont think this is possible to implement without some levels of it. Because the compiler does the reflection for you, you can be sure for the reflection not to “miss” due to different in memory representation that optimisations might introduce. Again it is strongly based on what you deem as UB since you can still give it a wrong pointer and “miss”.

To the case of more advanced automatic / generic mocking of data structures for those intrusive lists, it is 100% possible, altho LSP might not be able to follow the new generated types well afterwards.

Robert :blush:

1 Like
3

Is this the UB you were refering?

struct node *prev = MOCK_HEAD(&head, struct node, next);
for (struct node *cur = prev->next; cur != NULL;)

Reading the prev->next of the head pointer when it is null?

You can solve it by defining head as a node, instead of as a pointer:

static struct node head = {NULL};

struct node *remove_with_mock_head(struct node *n) {
    struct node *prev = &head;

    // Now this is legal.
    for (struct node *cur = prev->next; cur != NULL;) {

What other UBs were you seeing?

4

Thank you for your reply! Trust me, once you understand mock_head, you’ll see it offers significant advantages over other intrusive linked list implementations (including Linux kernel’s). Beyond reducing branches and improving performance, it also eliminates the need for second-level pointers and simplifies the code.

The sample code I provided can handle cases where head is a null pointer. There is no undefined behavior (UB) due to null pointers here – feel free to run it. Here is the code on compiler explorer: https://godbolt.org/z/vdaEcP57e.

I’m not a C++ novice, I wouldn’t make such a beginner mistake, I assure you.

In both C and C++, container_of itself inherently involves UB. Take a look at last year’s proposal:
Make idiomatic usage of offsetof well-defined
It details the specific violations, a significant number of C/C++ codebases implement linked lists without using container_of. This isn’t because they’re unaware of the technique, but because it violates the standards (particularly in C++, where it violates more rules). This isn’t just language-lawyer pedantry, it conflicts with certain compiler checks and optimization passes. This is the fundamental reason container_of can’t be standardized. Code appearing to work correctly after using container_of is essentially a coincidence with very high probability.

mock_head aims for true zero-overhead abstraction. Defining the head node as a full data node wastes space – only the next pointer within it is useful, the rest is redundant. If you tried to use such a list to implement a hash table, it would incur significant memory overhead, violating the principle of zero-cost abstraction.

Regarding the potential UB introduced by mock_head, which I listed in my question, I’ll reiterate them here:

  1. The pointer obtained via mock_head points beyond the boundaries of the original object.
  2. It points to an object that doesn’t actually exist, violating object lifetime rules.
  3. Others, including potential strict aliasing violations in some scenarios. Ultimately, the specific UB introduced by container_of depends heavily on its actual usage context.
1 Like
5

Thank you for your response! Zig appears to be more lenient with pointer handling. After looking into it, I also found that Zig doesn’t employ strict aliasing optimizations. I’ll try implementing mock_head in Zig during my free time, though I need to learn the language first.

6

@fieldParentPtr() is equivalent to container_of in C language. It is a builtin function and will not cause UB.

As far as I know, C/C++ pointers only allow addition and subtraction operations within an array, and operations outside the array are undefined. One possibility is to use uintptr_t to convert it into an integer before operation, which can downgrade the undefined behavior to a specified defined behavior, but it is hard to say that there are no other problems.
For the zig language, there are multiple types of pointers, among which [*]T allows operations with integers and has no further restrictions. See the relevant content in the documentation:Pointers, @ptrCast

3 Likes
7

Pointing beyond boundaries is allowed in Zig (obviously, as long as you don’t deference it). I think Andrew explicitly mentioned this somewhere, but I can’t find it now.
Zig treats data as just a bunch of bytes, so no strict aliasing and no lifetimes, only the lifetimes of the underlying bytes matter.
container_of in Zig is @fieldParentPtr, and since it’s a builtin, it’s legal.
I think this solves all your problems.

1 Like
8

The act of converting a pointer to an integer type like uintptr_t does not, by itself, magically eliminate the potential for UB in operations that would otherwise be UB (like pointer arithmetic on the integer value, or converting it back to an invalid pointer). uintptr_t provides an integer representation of the pointer value, but it doesn’t change the fundamental rules of pointer validity and aliasing. Operations performed using that integer value might still result in UB.

While reviewing the documentation for @fieldParentPtr, I came across the following description:

“If field_ptr does not point to the field_name field of an instance of the result type, and the result type has ill-defined layout, this invokes unchecked Illegal Behavior.”

Regarding my mock_head implementation: since the input pointer doesn’t actually point to a field within a real instance of the result type (as no such instance genuinely exists), this usage appears to violate the requirements for @fieldParentPtr in Zig. This would invoke unchecked Illegal Behavior, or have I misunderstood the documentation?

9

Let me guess your needs: your needs are not actually container_of, you have neither the parent structure instance nor the child field instance, you just need to input a fake pointer and calculate another fake pointer based on its offset, what you really need is just offsetof and pointer addition and subtraction operations, right?
There is also a builtin function @offsetOf

2 Likes
10

Exactly! You understood what I meant, and I’ll try that approach.

11

Wouldn’t @field be a more direct solution than @offsetOf?

The zelda project uses @field to implement intrusive linked lists.

12

The OP’s requirement is very special. There is no real object, nor a real field value. It is just using imaginary objects’ pointers to perform some arithmetic operations. I think @field is not a solution. It will perform real memory access.

13

If I understand that proposal correctly, they say that it’s only UB in C++, but not in C.

1 Like
14

You are correct! While container_of isn’t strictly compliant with the C language standard, it doesn’t lead to unintended results under normal usage. Therefore, there’s no need to be overly concerned about whether container_of constitutes UB in C.

15

After testing, I found that mock_head only passes tests in Zig’s Debug mode but fails in Release mode. It appears that mock_head violates something in Zig as well. Here is the test code on Compiler Explorer: https://zig.godbolt.org/z/Mz6s18af3

16

looks like llvm is misbehaving, it seems to have determined that your code always returns an error.

The custom backend works as expected, though it has little optimisations as it’s currently intended only for debug, and the one shipped with 0.14 is incomplete, but it works for your code snippet.

2 Likes