Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

introduce `allowzero` pointer attribute which makes 0x0 an allowed address #1953

Closed
andrewrk opened this Issue Feb 12, 2019 · 36 comments

Comments

Projects
None yet
10 participants
@andrewrk
Copy link
Member

andrewrk commented Feb 12, 2019

I'm extracting this proposal from #1952. This proposal conflicts with it, and only this one or that one can be accepted.

Add a pointer attribute to zig pointer types marking a pointer as possibly having the address 0:

test "aoeu" {
    var ptr = @intToPtr(*allowzero i32, 0);
}

Pointers which do not have this attribute are not allowed to have the address 0, which is why ?*i32 is guaranteed to have the same bit representation as *i32. But if you made an optional out of an allowzero pointer, like this: ?*allowzero T then it would add a bit of data to the type, just like it would for a ?usize value.

C pointer types (See #1059) would always allow zero, and the attribute would be a compile error. If we did this, then @intToPtr would gain safety safety checked undefined behavior for if the address is 0 and the destination pointer type does not have the allowzero attribute.

This OS kernel code uses a pointer with address 0 and in status quo zig it is in danger of invoking unchecked undefined behavior for the reasons explained in #1952. After this proposal, it would cause safety-checked undefined behavior (crash in debug mode) which would then be fixed by adding the allowzero attribute to the pointer.

@kristate

This comment has been minimized.

Copy link
Contributor

kristate commented Feb 12, 2019

Perhaps I am late to the party here, but why is this not an option?

test "aoeu" {
    var ptr = @intToPtr(?*i32, 0);
}
@kristate

This comment has been minimized.

Copy link
Contributor

kristate commented Feb 12, 2019

To reiterate, the compiler infrastructure to support *allowzero might outweigh the benefits it provides (how does this work with const, etc?) -- are we sure that there is not another way? Also, I feel that this proposal goes against the following zigism:

"Small, simple language. Focus on debugging your application rather than debugging your knowledge of your programming language."

@Rocknest

This comment has been minimized.

Copy link

Rocknest commented Feb 13, 2019

I dislike this new pointer flavour, i think that pointers in zig are overcomplex (especially upcoming(?) zero-terminated data pointer). Also this problem looks like a design flaw of the language, because implementation (or optimisation) of optional pointers interferes with ability to use full address space when not restricted by target platform.

Also any real-world use case for zeroable pointers that i can think of is low level memory management in a kernel. For such a rare task probably this pointer kind should be accessible via builtin function.

const text_boot = @intToPtr(@ZeroablePtr([*]const u8), 0)[0..@ptrToInt(&__end_init)]; // does not look too bad

Or implementation/optimisation of pointers could be platform dependent. When targeting linux/win/mac/bsd pointers would be optimised and when targeting freestanding pointers would be defined like any other optional type (maybe with compiler option to turn on optimisation).

Edit: couldn't find issue about pointers to null terminated data, so im gonna share my thoughts here.
Null terminated data is too fragile (unchecked memset for example), sending and receiving null terminated data over network creates complications, it also creates obstacles for bounds checking. Even more: in C it is not a part of the language, but an api (of the past). So i think that interop with legacy C APIs should not get dedicated feature in the language. Robustness should not be traded for runtime efficiency.

@daurnimator

This comment has been minimized.

Copy link
Contributor

daurnimator commented Feb 13, 2019

couldn't find issue about pointers to null terminated data,

See #265

Even more: in C it is not a part of the language, but an api (of the past). So i think that interop with legacy C APIs should not get dedicated feature in the language

It's not just legacy APIs, e.g. look at any linux syscall that takes a path.

@andrewrk andrewrk removed the accepted label Feb 13, 2019

@emekoi

This comment has been minimized.

Copy link
Contributor

emekoi commented Feb 13, 2019

i don't like this proposal but i do think it falls in line with "Communicate intent precisely."

@andrewrk

This comment has been minimized.

Copy link
Member Author

andrewrk commented Feb 13, 2019

Hey everyone, thanks for pushing back. I think I jumped the gun on this one, and I appreciate the feedback.

Perhaps I am late to the party here, but why is this not an option? @intToPtr(?*i32, 0)

The example use case does this:

const text_boot = @intToPtr([*]const u8, 0)[0..@ptrToInt(&__end_init)];
for (text_boot) |text_boot_byte, byte_index| {

If you put a ? in that @intToPtr it would not work; it is intentionally a compile error to slice an optional pointer.

are we sure that there is not another way?

That's a fair question. Which of the other two proposals (see #1952) to solve this problem do you prefer? Do you have a fourth idea in mind?

@Rocknest

Edit: couldn't find issue about pointers to null terminated data, so im gonna share my thoughts here.

I'm very interested in your opinions on null terminated pointers - would you mind repeating your comment on #265 ?

I removed the accepted label and re-opened #1952 for re-consideration. We do have a problem to solve here. In status quo zig, pointers which have address 0, but are dereferencable, are causing unchecked undefined behavior. This is not relevant for most OS targets, but it is relevant for the freestanding target, which is a first class citizen of zig use cases.

One problem I thought of with this allowzero proposal is that it prevents library code from working in a freestanding environment when a pointer has address 0. For example, if the example code listed above had depended on a gunzip package, and passed a slice which had address 0 to the inflate function, it would be completely reasonable for the gunzip package to not put the allowzero attribute on its input buffer. And it would be reasonable for the kernel code to want to use the gunzip package. Yet because of the way allowzero works, this would be a compile error. That's a serious flaw in this proposal.

@Hejsil

This comment has been minimized.

Copy link
Member

Hejsil commented Feb 13, 2019

Here are my two cents on pointers and optionals. To me, the most correct thing to do (in terms of sane semantics) is to always use 1 extra bit for all optionals. Then there are never any surprises. We don't need allowzero special cases. We avoid the problem of assigning undefined pointers to optional pointers. If we keep this optimization, then people will have to remember all these edge cases.

Reduce the amount one must remember.

We already have slices which are an alternative to null-terminated pointers. Slices are 16 bytes (on 64bit) where null terminated pointers are only 8 (+ @sizeof(T). We need one extra element). Null-terminated pointers use less memory (at least sometimes) but their semantics are hard to use so we avoid them in Zig. I think this null pointer optimization falls under the same category. We take a small hit, but in return, we get simpler semantics that has fewer edge cases.

I don't think optional pointer are very common in Zig code, so I don't think this optimization is really that big anyways (can someone show me code that allocates a lot of optional pointers? Is it really necessary?).

@kristate

This comment has been minimized.

Copy link
Contributor

kristate commented Feb 13, 2019

Sharing an irc log from earlier:

[kristate] thinking aloud about #1953, but I always wondered why we allow undefined behavior in the first place (instead of using the error infrastructure).
[andrewrk] kristate, consider that the + operator can invoke undefined behavior
[kristate] andrewrk: right, for these things, at the moment, we would have to panic, but for function calls where we can catch such things, wouldn't it be best to use the error infrastructure?
[andrewrk] go on
[kristate] andrewrk: well, we already have the compiler infra in place for calling-out to panic, so I wonder why we couldn't simply return an error up the stack instead of generating code to panic?
[kristate] likewise, it might make sense to have a special builtin for @intToPtr when the int is zero, ala @zeroPtr and then make @intToPtr try-able,
[kristate] try @intToPtr([*]const u8, 0) would generate an error.ZeroPointer (for example)
[kristate] likewise, @intToPtr might be called with a runtime variable that is zero, or another address that might be out of bounds
[kristate] right now, if you use try in a function that does not handle errors, the compiler complains, and that gives visibility to the programmer
[andrewrk] that's an interesting idea
[kristate] think of it this way, I know that we want @intToPtr to map as close as possible to llvm intrinsics, but at the same time, you would check code anyway to see if it equals a nullptr or not. try @intToPtr provides a very zig-way to do it, without the tacky if statement
[andrewrk] what do you think should happen on implicit cast from C pointer to Zig pointer? e.g. [*c]u8 to *u8
[kristate] well, I think that there should first be a built-in to do it. it shouldn't be something you can just cast-down to. second, coming from C-land, a nullptr is technically not defined as 0, but is implemented as zero, so I think that this should be impossible: it should only be down-castable to ?*u8
[kristate] andrewrk: this is debatable and something like bikeshedding, but perhaps ptr to zero should only be available as a [*c] ptr
[kristate] would we ever have to cast down to *u8?
[andrewrk] kristate, are you familiar with the motivation behind #1059? are you suggesting only that casting to zig pointers should not be implicit, or also from?
[andrewrk] also, I apologize - I am a bit past my bedtime and I'm sure that I am not speaking with as much clarity as normal
[kristate] andrewrk: please by all means, get some rest :-) about #1059, I am really glad that it is happening and fully supportive of it
[kristate] andrewrk: maybe we can talk later about this subject. I will post this log as a comment on #1952
[andrewrk] sounds good to me
[andrewrk] good night
[kristate] good night

@thejoshwolfe

This comment has been minimized.

Copy link
Member

thejoshwolfe commented Feb 13, 2019

Similar to @Rocknest's proposal

implementation/optimisation of pointers could be platform dependent

We could have allowzero be enablable for all pointers in a binary with a top level option. Then the gzip library still works in bootloaders, as long as the library doesn't assume that ?*T is the same size as *T.

It does seem like more of a target configuration rather than a pointer configuration.

@Rocknest

This comment has been minimized.

Copy link

Rocknest commented Feb 13, 2019

Pointers & slices also have unintuitive behaviour when used with undefined values.

In #1831 following example mentioned as not working:

var b: []const u8 = ([*]const u8)(undefined)[0..0]; // len = 0, ptr = undefined
var b_opt: ?[*]const u8 = b.ptr; // isNull = false, ptr = undefined
@import("std").debug.assert(b_opt != null); // undefined is not the same as null!

If i understand correctly this is also caused by pointer optimisation. So this is a case against the whole 0-special-casing of pointers even on targets such as linux/windows.

Also wouldn't checking undefined optional pointer trigger undefined behaviour? (undetectable at even at runtime?)

fn isNullPtr(ptr: ?*T) bool {
    return (ptr != null);
}
// somewhere else called as
var aPtr: ?*T = undefined;
_ = isNullPtr(aPtr); // what happens now? could be this detected at debug runtime without invisible field &etc.

I dont know how undefined optional pointers could be useful, but also there is u0. For me it is important to have sound and intuitive semantics.

@andrewrk

This comment has been minimized.

Copy link
Member Author

andrewrk commented Feb 13, 2019

@Hejsil what about this use case?

const optional_heap_handle = @atomicLoad(?HeapHandle, &self.heap_handle, builtin.AtomicOrder.SeqCst);

@Rocknest

This comment has been minimized.

Copy link

Rocknest commented Feb 13, 2019

@andrewrk one solution is to do it manually with usize, another one is maybe use the new C pointer type

@andrewrk

This comment has been minimized.

Copy link
Member Author

andrewrk commented Feb 13, 2019

use the new C pointer type

The docs for the C pointer type are going to say "never choose this type for your pointers." It's only for interop with auto-parsed C headers. Using the new C pointer type is not a valid solution to the use case.

@Rocknest

This comment has been minimized.

Copy link

Rocknest commented Feb 13, 2019

Thats good, it leaves us with 'only one obvious way to do things' - convert to usize and make assumptions about special cases by yourself (maybe not so obvious).

@andrewrk

This comment has been minimized.

Copy link
Member Author

andrewrk commented Feb 14, 2019

Here are some things that I would consider to be settled:

  • C pointers may have the address 0.
  • C pointers implicit cast to Zig pointers and vice versa.
  • On non-freestanding OS targets (e.g. linux, windows, macos, freebsd):
    • Zig pointers may not have the address 0.
    • @intToPtr will invoke safety-checked undefined behavior if the value is 0.
    • Dereferencing C pointers which have the address 0 is safety-checked undefined behavior.
    • Implicit casting a C pointer to a Zig pointer invokes safety-checked undefined behavior if the address is 0.
    • Optional zig pointers always have the same bit pattern as non-optional zig pointers.
    • Implicit cast from pointer to optional pointer invokes safety-checked undefined behavior if the address was 0 (since that is not allowed) see very last bullet point at bottom of this comment
    • @ptrCast supports both pointers and optional pointers (since they all have the same bit pattern). If the resulting pointer may not have the address 0 (e.g. it is a non-optional zig pointer), but the result ends up being 0, this invokes safety-checked undefined behavior.
  • On freestanding OS targets:
    • Zig pointers need to be able to have the address 0 sometimes
  • The nonnull LLVM attribute will be used only for pointers which may not have the address 0.

These questions remain:

  • Will zig allow a build option to disable Zig pointers from having address 0 in freestanding code? Will the default be to instead disallow address 0 and the build option would enable address 0 for zig pointers?
  • Do optional pointers on freestanding targets get an extra null bit when zig pointers can be address 0? what about the code this would break?
  • Do optional C pointers get an extra null bit since they can have address 0?
  • If a pointer may be address zero, but has the same bit pattern when it is an optional pointer, what happens when you implicit cast the pointer to the optional pointer and the address is zero?

I hate to say it but upon reconsidering all this stuff all day today, I'm starting to think that the best option is allowzero as proposed, as well as a global build option. This is how it would answer the questions:

  • allowzero on a C pointer is always a compile error. Use a zig pointer please!
  • For non-freestanding targets, allowzero is a compile error. However we may allow allowzero for test builds.
  • For freestanding, the default is still that zig pointers cannot have address zero. A build option would tell zig that 0 is a mappable address, and this would make zig pointers allow address 0. C pointers are allowed to have address 0, and dereferencing them is allowed.
  • When pointers allow address zero, then optional pointers add another bit, and the bit pattern of pointers and optional pointers will be different. This has the potential to cause compile errors for code that depend on optional pointers having the same bit pattern, e.g. if they tried to use an atomic operation on an optional pointer. This is acceptable. Choosing to depend on address 0 being unmappable is a reasonable dependency for code to have, just like choosing to depend on a file system. Choosing to depend on a file system makes compile errors when used in freestanding code, and choosing to depend on address 0 being unmappable makes compile errors when used in freestanding code with the mappable-0-address build option enabled. Note that having optional pointers does not prevent your code from working in freestanding mode with mappable-0-address enabled, as long as you don't depend on the optional pointer having the same bit pattern as the non-optional pointer.
  • In freestanding with the mappable-0-address build option enabled, allowzero is allowed, but redundant.
  • In freestanding, without the mappabble-0-address build option enabled, allowzero on a Zig pointer makes the pointer allowed to have address 0. making it an optional pointer has an extra null bit.
  • Freestanding projects will probably aim for not enabling the mappable-0-address build option. They will then use allowzero explicitly if they need a pointer/slice which can have address 0. If they needed to pass it to the gunzip package as in my example above, they would not be able to do this, since the gunzip package, correctly, did not put allowzero in their function prototypes. However the freestanding project could enable the mappable-0-address build option, and then be able to use the gunzip package. This comes at a potential cost of optimality (and perhaps compile errors, as explained a couple bullet points up) in unrelated code, which now has to introduce extra null bits for optional pointers.
  • Note that with this proposal, it would never be true that a pointer would allow address 0 and its optional pointer would have the same bit pattern
  • #1831 is solved thusly: when a pointer may not be address 0, an optional pointer shall have the same bit pattern. therefore if a pointer which may not be address 0 has an undefined value (See #1947) the bit pattern may be regardless be 0, and when it is implicitly casted to an optional pointer, the optional pointer has an undefined value as well. However, implicit cast from T to ?T even if T is undefined is guaranteed to produce a non-null value. So we have two choices:
    • Implicit cast from ptr which may not be address 0 to optional pointer is not a no-op; if the value is 0 then zig chooses any non-zero bit pattern for the optional pointer. This is sub-optimal in terms of generated machine code, but avoids confusing semantics
    • Make it safety-checked undefined behavior to implicit cast undefined value of pointer which may not have address 0 to optional pointer. In other words, if your pointer is undefined or illegally address 0 and you try to cast it to an optional pointer, boom.
@andrewrk

This comment has been minimized.

Copy link
Member Author

andrewrk commented Feb 14, 2019

I'm accepting this issue again. Still willing to discuss this, but if anyone wants to push back, they'll have to solve all the problems in their counter proposal. Until that happens this is the planned way forward. I want to note that I don't think this issue even would affect anyone in this thread except me since allowzero is a compile error on non-freestanding targets.

@kristate I think your ideas about safety-checked undefined behavior is its own separate proposal that has to do with language-level assertions and how they should work. I invite you to start a new proposal to talk about what constructs should return errors, or have safety-checked undefined behavior.

@andrewrk andrewrk added the accepted label Feb 14, 2019

@rohlem

This comment has been minimized.

Copy link
Contributor

rohlem commented Feb 14, 2019

EDIT: I've now created #1959 for my counter-proposal, which is less of a slog to read through, and hopefully still contains sound reasoning, though it doesn't address all the discussion points here as I think I did in this comment originally.

TL;DWR (this comment/post got really long again, my apologies, but I don't want to trim anything and obfuscate some obvious logic mistakes I might have made along the way):

  • Null pointer representations (of C-ABI-pointer to every C-ABI-type) are a part of the platform's (/configuration's?) C-ABI.
  • To regain the lean-optional-optimization of using a pointer value for "unpopulated optional pointer", we can at compilation time find/choose a single addressing unit (byte for most, word thing on other systems) to leave unused for this exact purpose. The source distribution model of Zig packages makes this feasible fwict.
  • Zig pointers really don't need "null", since we have optional for that. Barring platform specific trickery, optional Zig pointers will fail/error/ "trigger safety check UB" on conversion from this non-optional pointer value, if they lack the state to represent it. Because we only use optional pointers if we truly mean optional, most intentional use cases stick to non-optional pointers and the issue resolves itself. This means actually all-value-and-unpopulated-allowed-pointers are banned from the language. If this turns out to be an actual use case, we could introduce a new stateless type to instantiate via @nonnullptr(child: type) to "overload" functions with (via status-quo generics), or just introduce additional bool arguments / wrapping structs where necessary/useful. Now that I rethink it, it's probably so exotic and fabricated I personally vote against it, but maybe someone else has better arguments than me.

To reiterate: Zig's stance previously was not to use null pointers, and as such I don't see the motivating reason for introducing the null pointer value/concept into Zig pointers, beyond these two distinct use cases:

  • C(-ABI) interoperability
  • a common size optimization, (if at all possible) not to be elevated into the concern / field of vision of programmers

I thought I'd share some details (regarding C via the C standard(s)) that maybe everyone already knows, but shouldn't be overlooked in this conversation. (Note that I have no insight or knowledge about LLVM; to me previous comments suggest that throughout (most?) of their pipeline null pointers do coincide with all-bit-0 representations. Any knowledge all of you have surpasses mine.)

  1. A null pointer is a special pointer value distinct from all valid pointer values, that comes into existence by casting a 0-valued integer to a pointer type ("at compile time", apparently, though I'm not sure if the standards' wordings are as restrictive as that). (Note: Whenever you see the literal "0" in pointer comparisons, well-defined behaviour is only achieved if this is translated to the null pointer constant, not if its integer representation has any say in the matter.)
  2. The representation of this null pointer value is implementation defined (and might even differ between different pointer types!). Thinking about it this way, the null pointer representation of each type really ought to be part of a platform's (/ configuration's?) C ABI. If that is the case, and correctness is among the highest goals, every conversion EDIT: of Zig pointers from and to (C-ABI-)pointers to C-ABI-types should include this check in one form or another. (Note that, as I understand it, a platform is free to implement all the "undefined behaviour" surrounding null pointer usage as "the obvious" be well-defined behaviour of actually using the corresponding address as it would a valid address, so passing it to a function that doesn't mention null pointers in its specification (which excludes malloc for instance) might be a valid use case.)
  3. The "C way" to access this one mystical address nobody's life hopefully actually depends on is to "ask your implementation". As long as Zig provides some way to do communicate this intention (f.e. a u0-like stateless pointer type for this address only) I think it's no worse, even if no better, than C in this regard.

Why do we need null pointers?
If there is no flaw in, or counter-point to, my previous statement - the null pointer representation of each type is a part of the platform's C ABI - then I think it would be a good strategy to explicitly introduce (and at some point audit) these concepts and conversions from C-pointers to Zig-pointers. (Extending a freestanding Zig-target with C modules would then, equivalently, specify C's null pointer representations as part of its C ABI.)

Zig's stance on null pointers was made very clear as "strongly against" (I believe), although the actual runtime benefits of smaller storage size should not be dismissed completely, so discussion for reintroducing the lean representation of optional pointers by sacrificing one address should still be held. On this front, if LLVM's intrinsics around these attributes (reminder: I know nothing about them) are hyper-optimized for an all-bit-0 representation, the correct choice might be to use that. (Additionally, C-pointer to Zig-pointer conversions can be no-ops, if the representations for the involved pointer types coincide.)
In that case, a @nonnullpointer(child: type) literal of a new, special stateless pointer variety is a reasonable solution, I think. It would mean that all primitive operations, built-in functions etc. gain a new overload, to be added to their test matrices, that is automatically selected if this special type is used. (Oh, right, function overloading technically doesn't exist in Zig - the function would be required to become generic, gain an additional argument allow_null: bool, or an overload <> ++ "_nonnull" (that could technically drop the relevant, now stateless, pointer argument).


There is a pragmatic solution to finding a null pointer value (as in address corresponding to specific representation) for Zig-pointers:

  • Use an invalid (f.e. misaligned) address.
  • Use an address known to be free.

The first is trivial for any pointer with alignment > 1, and completely realizable on current x64 systems f.e. by misusing their purposefully-limited pointer representation.
The second alternative is status-quo, already guaranteed by the null pointer value of the C ABI of any hosted platform. For freestanding, all it would take would be to reserve a single addressing unit (byte on most, other-word on some systems), anywhere (via a "linker script" I guess? I lack technical knowledge on those) to guarantee its address is fit for this purpose. (I would naively also think using a 1-byte offset into a known-to-remain-constant-compiled-function would work as well. If you somehow end up there using pointer arithmetic, translating the result to an optional pointer would result in failure/error however.)

To be honest, I lack to see the issue brought up in the library use case, via the "gunzip" example.

  • Afaik, the plan for Zig packaging was to distribute modules in source form (to enable any and all metaprogramming/reflection capabilities, for one). In this case, the null pointer value can be determined at translation time, which for Zig is also link time, when all information is known and all pointer-representation questions are still open for any answer the compiler sees most practical.
  • If we're talking about the current gunzip package which is (or I assume to be?) C, then we have a C-ABI boundary to translate on/over. A compiled C module that filters out null pointer values will never be able to read address 0 after compilation, unless you reverse engineer it to remove that restriction as an afterthought; kind of a lost cause on the language level.
  • I don't think we actually want the library interface of a module (only pre-inlining, pre-optimization etc.) to profit from the lean-representation of null-means-unpopulated-optional pointers, because we don't define interfaces that way. Thinking of a compression module, why would we want f.e. the data: *c_void argument to be optional? What is there to un-/compress in that case? If it is a configuration parameter, where unpopulated signals "default", there are other ways to implement this - introducing a factory function to produce this "default configuration value", or just living with the couple of bytes extra the optional parameter costs us. (Note: When it really comes down to it, I think these populated-bits of arguments could be packed into a single additional argument as a size-optimization, if packing and unpacking doesn't become unreasonably expensive in comparison.)
@rohlem

This comment has been minimized.

Copy link
Contributor

rohlem commented Feb 14, 2019

Looks like I joined too late / took too long. In response to @andrewrk 's second-last comment:
C pointers may have the address 0 - per the C standard(s), the null pointer value is distinct from any data ("object") and function pointer value. The all-bit-0 representation may be usable. Behaviour, outside of functions that mention it in their specification, is undefined.
(A platform letting it slide would mean that there is a pointer to data that compares equal to the null pointer, which violates the spec... though maybe it could be a NaN-style comparison if you squint really hard? Maybe? Probably not.)

@andrewrk

This comment has been minimized.

Copy link
Member Author

andrewrk commented Feb 14, 2019

@rohlem the C ABI that Zig uses is determined by the "environment" part of the target. You can use zig targets to see the list of C ABIs available:

Environments:
  unknown
  gnu (native)
  gnuabin32
  gnuabi64
  gnueabi
  gnueabihf
  gnux32
  code16
  eabi
  eabihf
  android
  musl
  musleabi
  musleabihf
  msvc
  itanium
  cygnus
  coreclr
  simulator

(Side note, I should open a proposal to rename "environment" to "C ABI" and audit the "unknown" one)

As far as I'm aware, all of these C ABIs use 0 as the NULL pointer. Are you suggesting to support an additional C ABI, which uses something other than 0 for NULL? What is it called, and on what systems is it used?

@rohlem

This comment has been minimized.

Copy link
Contributor

rohlem commented Feb 14, 2019

@andrewrk If it's true that all supported target "environments"/C-ABIs agree that NULL has both representation and value (address) 0, then this silent assumption from before was correct. It was more of a detail of exposition for my argument.

(TL;DR: Sry, my comment got bloated again. Bottom line: I don't think there are motivating use cases for letting users decide "allowzero" on a per-variable basis (cases 1, 2 vs 4, 3 below), and I think it is reasonably possible to either find an invalid pointer representation, or "ban" a single addressable byte/word, even on freestanding systems (making cases 2 and 4 below obsolete) - note this doesn't have to be address 0. )

The more important thing to note is that, being the null pointer, "distinct from any pointer to data/function", this value (apparently address 0) cannot be used in standard C to load from, nor store to the corresponding data (and therefore, allowing it for C-pointers in Zig seems counter-intuitive to me). That is why this optimization works for C. If we want the same optimization for optional pointers in Zig, it makes sense to use this same address to make conversions easier. In this case we lose the ability to represent this address using optional pointers, just as C pointers cannot (legally) represent this address. This is not actually an issue, however, because:

Pointer operations are meaningless for both the null pointer (as C defines it "pointing to neither function nor data"), as well as an unpopulated optional pointer (the same way arithmetic is "meaningless" on unpopulated optional integers).
I might not have not been seeing eye-to-eye with the actual issue and solution proposed here, my apologies. Here's a succint list of my judgement/understanding of the "allowzero attribute" proposed in combination with optionality:

  • Optional, "regular" (non-"allowzero") pointers can be supported without size growth, the easiest and least-surprising way by using the same representation for "unpopulated" as C pointers use for the null pointer.
  • Non-optional, "allowzero" pointers can be supported, the easiest and (in my opinion) least-surprising way by ignoring the double-meaning of the mythical null address and just exposing it for use.
    These first two items don't change the inherent meaning of C null / Zig unpopulated as "not in use", and so null-/unpopulated-checks when converting them are justified.
  • Non-optional, "regular" (non-"allowzero") pointers don't appear useful to me: This would mean we are actively banning the address corresponding to the null pointer from use, without a reason. This inhibits f.e. reading from it, like in the freestanding example.
    (If we want to do this for safety measures, because we are sure nobody would want this on the corresponding target, that would lead to an "allow null" compile flag rather than distinct type/attribute, and we could add/keep/foster checks against it, although there are much larger address regions than just the null-address to worry about. All out-of-bounds addresses should be checked, and are already checked in the form of segfaults on modern systems, although I suppose more safety would never hurt in debug builds. I still don't see a compelling reason to add a pointer type for this specific case/combination. If we already know this address is always unsupported/meaningless, like we do for address 0 on hosted systems with C-ABI-null-address 0, and really want nobody able to use it, we should drop case 2 instead of exposing both to programmers.)
  • Optional, "allowzero" pointers simply require more size than non-optional "allowzero" pointers. As stated before, all actual operations on pointers only make sense if the pointer is "valid", not on a C-null- or optional-unpopulated pointer. The same way, I think library interfaces could be designed in a way not to use optional pointers at all. However, note that this only becomes relevant on a platform without any invalid (C-ABI-null value) addresses. I think there are valid implementation techniques for deducing such a representation on any platform, even if it might require us to reserve a single byte/word for only this purpose.

As might be obvious, the first two combinations seem the most meaningful to me.
I cannot imagine an actual use case of the third case, since it means sacrificing generality as mentioned in the library example, without any benefit. (I might be undervaluing the LLVM attributes mentioned in #1952.) However, if the target platform does have an "invalid" address to use as Zig-unpopulated-representation, then we can make case 2 and 3 coincide, so whichever implementation is more advantageous (quite possibly 3, limiting the addresses usable on that platform for free conversion from and to optional pointers) should probably be chosen in every scenario, instead of making it a case-by-case user decision by adding an "allowzero" attribute into the type system.
Case 4 would mean giving up this optimization just so we can represent one more address than C. Note that it doesn't have to be address 0, but could be any address, possibly of a specially-allocated byte/word when linking, reserved for exactly this purpose, of which we can guarantee it cannot be touched by code. If we have any byte/word unit we can state as "unused", case 4 coincides with case 1 (leading to this imo simplest solution). (You immediately regain the sacrificed single byte/word unit the moment you use an optional pointer, which now occupies 1 unit less storage).
I think an "allow null" compile flag to enable this behaviour is a reasonable idea, although I do not see an actual motivated use case (a system in which every addressable unit will be addressed directly by an optional pointer in code). If this use case does exist, I think it invites mistakes to expose both cases 4 and 1 for this system, by extending the type system, and have code manage both "allowzero" and non-"allowzero" pointers next to one another - what heuristics / flow chart decision tree would one use to decide whether a single particular pointer should "allowzero" or not? (If only a handful of pointers actually allowzero, the reasonably obvious workaround to support case 4 would be a userland implementation of optional allowzero pointers using a struct of non-optional pointer and populated: bool tag. The other way around, implementing your own case 1 null pointer representation and remembering to check for it everywhere, appears more error prone to me, although technically possible as well.)

@andrewrk

This comment has been minimized.

Copy link
Member Author

andrewrk commented Feb 14, 2019

The more important thing to note is that, being the null pointer, "distinct from any pointer to data/function", this value (apparently address 0) cannot be used in standard C to load from, nor store to the corresponding data (and therefore, allowing it for C-pointers in Zig seems counter-intuitive to me

Did you see these bullet points in my comment?

  • On non-freestanding OS targets (e.g. linux, windows, macos, freebsd):
    • Dereferencing C pointers which have the address 0 is safety-checked undefined behavior.

This is coherent with what you're saying about NULL in C. For C pointers address 0 represents an invalid pointer. It's allowed in C pointers, not so that you can read or write to it, but because it more closely matches the semantics of actual C pointers. C code can be translated into Zig code like this:

#include <stddef.h>
static int *foo(void) {
    return NULL;
}
static void bar(void) {
    int *ptr = foo();
    if (ptr != NULL) {
        *ptr += 1;
    }
}
pub fn foo() [*c]c_int {
    return 0;
}
pub fn bar() void {
    var ptr: [*c]c_int = foo();
    if (ptr != NULL) {
        ptr.* += 1;
    }
}
pub const NULL = if (@typeId(@typeOf(0)) == @import("builtin").TypeId.Pointer) @ptrCast([*c]void, 0) else if (@typeId(@typeOf(0)) == @import("builtin").TypeId.Int) @intToPtr([*c]void, 0) else ([*c]void)(0);

Yep that NULL declaration is nasty, but that's what we have to do when we see #define NULL ((void*)0). Compare this to master branch (which actually cannot build without compile errors):

pub fn foo() ?[*]c_int {
    return null;
}
pub fn bar() void {
    var ptr: ?[*]c_int = foo();
    if (ptr != @ptrCast(?[*]c_int, (?*c_void)(0))) {
        ptr.?.* += 1;
    }
}

Pointer operations are meaningless for both the null pointer

This may be true in C but it's not true in LLVM and in Zig we can make up whatever rules we want.

I don't think there are motivating use cases for letting users decide "allowzero" on a per-variable basis

I don't see your comment taking into account the use case I explicitly mentioned in this thread, or my comment #1953 (comment)
I get the impression that you did not see this crucial point:

  • For non-freestanding targets, allowzero is a compile error.
@Rocknest

This comment has been minimized.

Copy link

Rocknest commented Feb 14, 2019

Some interesting information that i found:

  1. Because of C on Windows first 16 pages (64KiB) of virtual address space of every process are used to efficiently catch null pointer dereferences (myArrayTotallyNotNull[index])
  2. Rust docs say that 'Therefore, two pointers that are null may still not compare equal to each other'. Why would they say that?
  3. (void*) 0 is just a syntactic sugar
@emekoi

This comment has been minimized.

Copy link
Contributor

emekoi commented Feb 14, 2019

Note that unsized types have many possible null pointers, as only the raw data pointer is considered, not their length, vtable, etc. Therefore, two pointers that are null may still not compare equal to each other.
this is due to rust's concept of fat pointers which rust uses to store vtables and other similar information.

@Rocknest

This comment has been minimized.

Copy link

Rocknest commented Feb 14, 2019

@andrewrk

This may be true in C but it's not true in LLVM and in Zig we can make up whatever rules we want.

However zig's pointer are basically C's pointers extended with type safe comptime attributes, but inside they are backed up by C's vague spec (because of seamless interop of zig<->c pointers).

Edit: are pointers received from C checked for alignment etc.?

@andrewrk

This comment has been minimized.

Copy link
Member Author

andrewrk commented Feb 14, 2019

However zig's pointer are basically C's pointers extended with type safe comptime attributes, but inside they are backed up by C's vague spec (because of seamless interop of zig<->c pointers).

This is incorrect. Zig pointers are defined by the zig language specification (#75) and interop with C pointers is defined by the C ABI part of the selected target. (currently named "environ")
As noted above all supported C ABIs have 0 as the null pointer.

Let me repeat: the C specification has no bearing on Zig. Let's make sure that rumor doesn't start flying around.

@Rocknest

This comment has been minimized.

Copy link

Rocknest commented Feb 14, 2019

Oh okay, but what about new special C pointer?

@Rocknest

This comment has been minimized.

Copy link

Rocknest commented Feb 15, 2019

WebAssembly loads modules into virtual linear memory starting from address 0, it seems that linkers required to put some useless thing at the start if a language wishes to use 0 as the null pointer.

@rohlem

This comment has been minimized.

Copy link
Contributor

rohlem commented Feb 16, 2019

After the recent discussion in IRC I realized I was indeed misinterpreting just how specialized this change would be, and if extending the type system really is the easiest solution, it seems a valid approach (knowing most code won't make use of it).

I just thought of an edge case with (I assume) undefined behaviour I wanted to mention here, so it is at least documented:
Since the address-of operator returns a non-allowzero pointer (or so I'd assume, otherwise we would emit conversion-checks everywhere for freestanding targets), taking the address of an object located at address 0 is an invalid operation. (Address 0 refers to the null-address in this comment, since it was decided in #1959 that nonzero null addresses are, for the time being, not planned to be supported.)
This could potentially happen in two scenarios:

  • The linker decides to put a variable/symbol at address 0. As I don't know much about linkers, I'm not sure this is even possible. If this happens randomly (very unlikely), it is only determined after the translation phases and the compiler can't do much about in this particular scenario.
    If the variable/symbol is annotated to be placed at address 0 however, then Zig could potentially realize this and flag its type under-the-hood, so that taking its address actually generates an allowzero-enabled pointer.
  • The stack starts at / grows into this address. As it's unreasonable (I think) to add a null-check to every single address-of operation on stack variables, it would probably necessitate a heuristic to check whether the default stack can possibly be located there, and limit it to exclude address 0.

Additionally, I assume a builtin @addressOfAllowZero for querying a variable/symbol 's address as allowzero-pointer might be useful, although without C++ - references there actually doesn't seem to be a fitting argument type to refer to the symbol to take the address of.
It would probably have to take the non-allowzero pointer, and be hard-wired to require the compiler to find the necessary code-pattern during translation, then retroactively erase all mentions of nonzero-attributes etc. (similarly to how @inlineCall and @noInlineCall affect optimization passes, and comptime-error to indicate failure).

(I assume checking the result of non-allowzero-pointer arithmetic for 0 is easier to spot, and therefore already on the agenda.)

@Rocknest

This comment has been minimized.

Copy link

Rocknest commented Feb 16, 2019

I still like @rohlem's original idea:

  • Zig pointer can use all of the address space
  • Optional pointer reserves an address to use it as null

However if a special pointer is easier to implement (and this special type is going to be used only once in a kernel) then maybe it is good idea to hide it in a builtin function (@AllowPointToZero([*]const u8)).

@rohlem

This comment has been minimized.

Copy link
Contributor

rohlem commented Feb 16, 2019

@Rocknest Here's how I understand the reasoning behind the proposal:

  • Any time we switch allowzero-dness, we need/want a safety check. If we go with my idea, that means on every wrapping and unwrapping between non-optional and optional pointers. If allowzero is integrated into the type system, these checks only ever need to occur on these designated boundaries (because it's safe to assume a non-allowzero value is never zero as input to any operation).
  • allowzero provides the opportunity to enable these nonzero LLVM attributes for potential optimization intrinsics on all non-allowzero pointers (virtually everywhere).
  • allowzero will only be usable in freestanding targets, and even then only for very specific operations, not more than a couple dozen times over the entire code base. So even there, 99% of the time these same optimization opportunities apply.

While I still think yet another type flag makes the language harder to reason about, the alternative (not marking these exceptional uses with allowzero) brings "regular" code closer to unknowingly reaching and spreading null pointers.

allowzero will never come up in libraries or otherwise reusable code. It allows greater explicitness in stating intent, and if one day the details surrounding it change, making it obsolete or even more specialized, it still won't break anything outside of bare-metal kernel territory.

@vegecode

This comment has been minimized.

Copy link
Contributor

vegecode commented Feb 20, 2019

I don't understand the use case still. The code that you showed as the use case works as long as the pointer is not declared as optional? Why would you want it to be optional in that use case? How can a hardcoded address be optional? You are filling out the pointer contents with an address in the declaration.

The LLVM docs referenced in #1952 say that while loads from a pointer containing the address 0 is undefined behavior, it is never checked or enforced. Realistically that means it will just try to load from it, right? So a comptime known hardcoded pointer with an address of zero could just be the special case?

Also, the problem could be skipped for this special use case by just doing a compare in assembly, then doing the rest of the addresses starting at one or four or whatever your alignment needs are in Zig. That is not a huge burden on the programmer that deals with issues like this. Encapsulate the ugly business in a function call and it even looks pretty.

I feel like I must be missing the point.

@rohlem

This comment has been minimized.

Copy link
Contributor

rohlem commented Feb 21, 2019

@vegecode Even if the address being 0 is never checked or enforced by LLVM, I think in Zig we would want to check and enforce this: As safety feature in debug builds, and optimization opportunity in optimized builds. (Even if LLVM optimizers were currently unable to do this - which I doubt, given the mentioned nonzero attribute readily available - it might be useful for earlier, Zig-internal analysis at some point.)

Using assembly to work around the problem makes the code non-portable; plus it requires the programmers to learn and understand the respective assembly.
The general motivation behind integrating these special scenarios into the type system - even having a type system in the first place - is to be able to propagate semantics and coupled assertions. If a function argument - at any point - is a pointer with 0 being a valid address, then not having a special type to represent it would mean overloading the type system, hurting readability and spawning bugs.
If we work around it by "just doing these parts manually", that makes it harder to modularize these program components, or reuse already-existing code. If you want std.memcpy for address 0, "just write it in assembly". If you want std.memcmp for address 0, "just write it in assembly". I think that approach/mentality is generally prone to oversights and doesn't scale well.

At the end of the day, this proposal is completely self-contained. If it turns out not to be a viable solution, for whatever reason, nobody outside of the intended target audience will even have had to notice it in hindsight.

@vegecode

This comment has been minimized.

Copy link
Contributor

vegecode commented Feb 22, 2019

@rohlem First of all, thank you for taking the time to respond. I appreciate feedback always. You make good points, although I think you missed my main point by focusing on the assembly section. Also, this use case is non portable. It's dealing with the machine directly, not the abstractions layered on top.

Secondly, you misrepresent my argument by compressing multiple statements in my previous comment to one inaccurate paraphrase and then placing it in quotes. That is rude enough, but I can understand if that is coming from misunderstanding my point or from a lack of clarity in my description. You took it a step further even by then elevating your mischaracterization of my thoughts on this specific use case to an overall "mentality." If you meant nothing by it, know that it was not taken as nothing.

My main point was that a hardcoded comptime int address pointer could be the exception where null wasn't checked for. If you're using those, you should know what you're doing. Also it would be one less piece to add to the language.

Overall I think the proposal is a fair one, and perfectly reasonable. The only thing that rubbed me the wrong way was your response. I won't hold it against you, but I think it's important to be upfront when a social interaction is sub-optimal.

@rohlem

This comment has been minimized.

Copy link
Contributor

rohlem commented Feb 22, 2019

@vegecode First of all, I'm sorry to have offended or even mischaracterized you (/ your statements) in any way. I tend to (apparently mis-)use quotes often, not to claim paraphrasing someone else's statement, but to point out I'm heavily reducing from surrounding context in these cases, and that those elements are not to be taken literally, but understood and taken in context.
It seems as though that came across exactly opposite of how I intended it - "just doing these parts manually" for instance was not intended to represent your view wasn't justified or well-thought out, but simply to reduce the length of my comment, indicating that "obviously a well-reasoned approach can be argumented at this point, which I am not going to detail here, so take this reductive exaggeration with a grain of salt". "Mentality" was also meant to apply only to the hyperbolic representation in my comment, not to actually make implications towards your, or anyone's, more distinguished stance - though now I see how its literal meaning can/would be understood the other way around.
I apologize.

I understand and agree with your fundamental stance that a fixed, comptime-known int/address is not optional. In this way it reflects my earlier proposal of "just banning optional allowzero pointers, and making all non-optional pointers allowzero, that is, able to load from and store to address 0 without issue.".
The main motivation for not going with this approach, as far as I understand it, is that most uses of pointer types can profit from LLVM-optimizations that rely on them never being 0. That means this "exception to the rule" of comptime-known zero would need to be enforced by the compiler outside of the pointer types present in the type system, which leads to increased complexity handling this special case in affected areas (most of all pointer operations).
In a way, allowzero is vocabulary to express exactly this "exceptional hardcoded 0 case", and while its value to be used as a type in data structures and function interfaces is debatably small, the fact that we can use the type system to "ward off" these unusual use cases and separate their implementation and influence on the rest of the language, in my opinion, provides a good mechanism to signal this special handling to programmers.

Also, while I admittedly don't know a lot about embedded systems, to me it seems the special handling of null pointers was an original, "artificial" invention of the C language, influencing LLVM's mechanisms surrounding it. In this context, I seem to be missing the point of why the use case of dereferencing address 0 were any less portable than using a pointer to dereference any other address.

Thank you for pointing out the/my miscommunication, and I'm sorry should parts of this comment still read as if I valued my own opinions and logic over anyone else's view on the matter (which is, generally, a stupid mindset I'd want to avoid having or representing, if possible).

@vegecode

This comment has been minimized.

Copy link
Contributor

vegecode commented Feb 22, 2019

@rohlem Thank you very much for responding so thoughtfully.

It makes sense to value your own thoughts and opinions above others, just not to denigrate other's opinions, which I can see was not your intention.

I think one of the best things about the small Zig community so far is that everyone is open to the free exchange of ideas and mature about handling disagreements when they arise.

Thanks for being excellent and empathetic!

@shawnl

This comment has been minimized.

Copy link
Contributor

shawnl commented Mar 20, 2019

For example, if the example code listed above had depended on a gunzip package, and passed a slice which had address 0 to the inflate function, it would be completely reasonable for the gunzip package to not put the allowzero attribute on its input buffer. And it would be reasonable for the kernel code to want to use the gunzip package. Yet because of the way allowzero works, this would be a compile error. That's a serious flaw in this proposal.

  1. I do not like the proposal of a global build flag
  2. the kernel usually would use a special in-place inflate function, rather than the general purpose one
  3. I think the package should be required to use the allowzero attribute, if needed, in the specific places it is needed. regular pointers should implicitly cast to allowzero pointers (which just mean this specific llvm optimization is turned off), so that the code can have this attribute without most people having to know what it does.

@andrewrk andrewrk closed this in 5eaead6 Mar 25, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.