distinct 'static' items never overlap

[RalfJung]

It seems like so far we did not actually guarantee this.

While we are at it, also clarify that static initializers can read even mutable statics, and what happens in that case.

[workingjubilee]

I don't think you understood my example? I was positing that this seems to be a legal interpretation of the reference's current text:

static ZEE: u8 = 0;
static ZED: u8 = 0;
assert_eq!(&raw const ZEE, &raw const ZEE);
assert_eq!(&raw const ZED, &raw const ZED);
assert_eq!(&raw const ZEE, &raw const ZED);

[workingjubilee]

Because this

I would say if a static has a wibbly wobbly address not equal to itself, that's not a "precise memory location". We don't even have addresses that are not equal to themselves.

cannot be a response to what I actually said if it is said with an understanding of what I was trying to say. :/

[RalfJung]

I think I understood the example? I don't understand how that can be a valid interpretation of the text. A static has a location, &raw const gives you a pointer pointing there. Different locations compare inequal.

[RalfJung]

Oh, maybe I didn't quite understand the example.

But statics are certainly intended to be unique and disjoint. That's their point -- they describe a place, distinct from all other places.

More specifically, statics form their own allocated objects that don't overlap with any other allocated object. So in fact ZST statics are not quite unique -- but statics of type i32 are guaranteed to be at least 4 apart.

[RalfJung]

@rustbot label +T-opsem

[RalfJung]

@rfcbot merge since so far it seems like we haven't actually documented "different statics are disjoint". Cc @rust-lang/lang

[rfcbot]

Team member @RalfJung has proposed to merge this. The next step is review by the rest of the tagged team members:

• [x] @CAD97
• [x] @JakobDegen
• [x] @RalfJung
• [x] @digama0
• [x] @saethlin

Concerns:

• clarify-optimization-of-consts resolved by https://github.com/rust-lang/reference/pull/1657#issuecomment--1835224703

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

cc @rust-lang/lang-advisors: FCP proposed for lang, please feel free to register concerns. See this document for info about what commands tagged team members can give me.

[JakobDegen]

Lgtm, with the note that it's important this language remains restricted to static items, and not other language constructs that produce statics - const promotion, vtables, functions, etc. Will check my box when I'm off mobile, as apparently the GH app doesn't let you edit things anymore (or someone can do it for me :) )

[RalfJung]

You probably don't have edit rights here. I don't.

You can use @rfcbot reviewed to check your box.

with the note that it's important this language remains restricted to static items, and not other language constructs that produce statics - const promotion, vtables, functions, etc.

I would argue those aren't statics, they are other kinds of global allocations -- exactly because of this fundamental difference.

[JakobDegen]

@rfcbot reviewed

[workingjubilee]

hmm. how must the addressing work for this, then?

static BLAH: &str = "blah";
static ALSO_BLAH: &str = "blah";

Are these potentially two different pointers to the same string literal?

[RalfJung]

Are these potentially two different pointers to the same string literal?

Yes.

[saethlin]

@rfcbot reviewed

[rfcbot]

:bell: This is now entering its final comment period, as per the review above. :bell:

psst @RalfJung, I wasn't able to add the final-comment-period label, please do so.

[digama0]

@rfcbot reviewed

[CAD97]

@rfcbot reviewed

[workingjubilee]

I have a concern: this proposed definition prevents emitting optimization annotations on non-static items that we may wish to have coalesced via optimizations that exploit the fact that const items have a non-significant address. Even if we wish to guarantee static unicity, it seems pointlessly penalizing to make this guarantee affect the ability to optimize, quite literally, the items that don't have unique addresses.

[saethlin]

@rfcbot concern clarify-optimization-of-consts

I think the proposed text and the previous text have the same meaning, which is unfortunate because I think that we'd already specified that consts are not merged into statics. But given the participation on this PR, and its title which seems to be about overlap of statics, and the fact that I think rustc currently does not implement what is documented here, I would like the implications for consts to be spelled out clearly.

[RalfJung]

But given the participation on this PR, and its title which seems to be about overlap of statics, and the fact that I think rustc currently does not implement what is documented here, I would like the implications for consts to be spelled out clearly.

I gave that a shot, please have a look.

[saethlin]

@rustbot resolve clarify-optimization-of-consts

[RalfJung]

@rustbot resolve clarify-optimization-of-consts

That was the wrong bot. :)

Let's see if I can also do this...

@rfcbot resolve clarify-optimization-of-consts

[RalfJung]

@saethlin maybe you have to issue that command.

[saethlin]

🤦

@rfcbot resolve clarify-optimization-of-consts

[rfcbot]

:bell: This is now entering its final comment period, as per the review above. :bell:

psst @RalfJung, I wasn't able to add the final-comment-period label, please do so.

[joshtriplett]

A concern that came up in the @rust-lang/lang meeting: what is our definition of "overlap"? How does it handle ZSTs? There are multiple possible definitions we could use.

In particular, I don't think it should be possible for a ZST to be in the middle of an unrelated object (e.g. an unrelated array of non-ZSTs).

@nikomatsakis proposed defining overlap as "the start of one object lies between the start and end of the other, exclusive". That would prevent that property.

Another possible definition would be "has one or more bytes in common", but that would allow placing a ZST in the middle of an unrelated array.

[traviscross]

@rfcbot fcp cancel

[rfcbot]

@traviscross proposal cancelled.

[traviscross]

We'll repropose this as a dual FCP and recheck the existing checked boxes from above.

[nikomatsakis]

Discussed in the lang-team design meeting. We are aligned for non-ZST statics but the text seems underspecified for ZSTs. We suggest you either

1. clarify that the text does not apply to ZSTs or else
2. address the questions below.

Questions to be clarified:

• What is the definition of "overlap" (see options below)?

which in turn answers scenarios like this

• Can the address of a ZST static appear "in the middle" of another (non-ZST) static?
  • For example, if static x: (u32, u32) is at address X, can static y: () be at address X + 4?
• Can two ZST statics have the same address?

Considerations:

• If we assert the first property, it implies that non-ZST statics cannot be placed at low addresses like 1 or 2, since e.g. a ZST value with alignment 2 will be assigned address 2. This might be something an embedded platform wants to do, for example.
• If we do not assert the second property, then users need to ensure that their statics have at least one byte if they want to rely on the address.

Two possible definitions for overlap:

fn overlap_a(start1: usize, end1: usize, start2: usize, end2: usize) -> bool {
    // Overlap iff the start of one (potentially trivial) range falls within another non-trivial range.
    //
    // Put another way: no byte of one static can be stored
    // at the starting address of another.
    start1 <= start2 < end1 ||
    start2 <= start1 < end2
}

fn overlap_b(start1: usize, end1: usize, start2: usize, end2: usize) -> bool {
    // Overlap iff they have bytes in common:
    overlap_a(start1, end1, start2, end2)
    && start1 != end1 // <-- empty ranges cannot overlap
    && start2 != end2
}

[RalfJung]

what is our definition of "overlap"?

I would say two ranges do not overlap if end1 <= start2 || end2 <= start1: one range has to end before the other begins. Therefore, they overlap if end1 > start2 && end2 > start1. (That last condition does not look intuitive, but the "no overlap" one is quite intuitive, and I think it is quite elegant since it avoids asymmetries like focusing on the starting address.) So indeed, a ZST static is not allowed to be "in the middle of" another static.

If we assert the first property, it implies that non-ZST statics cannot be placed at low addresses like 1 or 2, since e.g. a ZST value with alignment 2 will be assigned address 2.

I don't think it implies this. There's no ZST allocation created at address 2. It's just a pointer without provenance that has address 2, that's not in conflict with anything.

[RalfJung]

If we assert the first property, it implies that non-ZST statics cannot be placed at low addresses like 1 or 2, since e.g. a ZST value with alignment 2 will be assigned address 2.

Or... do we actually have codegen synthesize addresses like this now? And not just the library by calling NonNull::dangling?

[RalfJung]

Can two ZST statics have the same address?

Yes, definitely. This is desirable, it means one can soundly use the pattern of "my linker defines two symbols that mark the beginning and end of a relevant range of memory" via two ZST statics.

[workingjubilee]

In particular, I don't think it should be possible for a ZST to be in the middle of an unrelated object (e.g. an unrelated array of non-ZSTs).

I don't think that's a coherent model. As far as I have understood, we have said that ZSTs can overlap with non-ZSTs because the overlap is of 0 bytes, each time, and an overlap of 0 bytes is not an overlap. I think going down the route of "an allocation 0 bytes cannot 'overlap' with an existing allocation" is a bad idea, because we would be:

• inviting self-contradiction by complicating the model
• implicitly saying ZSTs cannot actually exist in Rust in a way that is useful, by imposing constraints that say ZSTs can no longer be at certain locations, when programmers actually do rely on the ability to allocate ZSTs at certain locations!
• ultimately, trying to promise programmers things we cannot actually offer, instead of just admitting there is a sharp edge around 1ZSTs being slightly nonintuitive, because the idea of zero is not perfectly intuitive in general

Can T-lang explain the actual utility of this prohibition?

Why should there be a statement that a 1ZST cannot be allocated somewhere I could absolutely create a pointer to a zero-sized byte-slice? Why should the reasoning be fundamentally different?

[traviscross]

we have said that ZSTs can overlap with non-ZSTs because the overlap is of 0 bytes, each time, and an overlap of 0 bytes is not an overlap.... there is a sharp edge around 1ZSTs being slightly nonintuitive, because the idea of zero is not perfectly intuitive in general

This I find persuasive.

[chorman0773]

I'm not sure a prohibition here would do anything to users, only to implementations - it would simply prohibit placing a ZST static at an address that lies inside the storage of another static. We're not talking about allocations generally either, just static items in particular. Frankly, I think any reasonable definition of "overlap" not explicitly written to permit this would prohibit doing that. I also think this is true of aggregate layout - any meaningful definition of "overlap" would prohibit the compiler from placing a ZST field at an offset that leaves it "inside" a non-zero sized field.

I'm not sure there's substantial programmer benefit from this prohibition (as this doesn't present any UB concerns like non-zero sized allocations overlapping can, involving aliasing), but I don't think there's substantial implementation benefit from explicitly authorizing it either (I'm not sure why a compiler would want to place a ZST static arbitrarily within some other static, but I doubt it helps any optimizations), so I think the best way forward is the intuitive definition that would disallow it.

[chorman0773]

With the above being said, I think that a definition of "Range R overlaps Range Q if Q.start <= R.start && R.end < Q.end`" is the most reasonable and intuitive definition (also used elsewhere in mathematics when talking about numeric ranges). As mentioned above, I don't see a benefit to us defining this in a way that exempts an empty range R.

[traviscross]

Let's back up to first principles. Two ranges overlap if and only if there is some value that might appear in both ranges. To prove that impossible, when the ranges are ordered, it's necessary and sufficient to prove that the last included value of each range cannot contain the first included value of the other range.

This is why the rule @RalfJung gave above for overlap is correct for such half-open non-empty ranges:

I would say two ranges do not overlap if (ed: and only if) end1 <= start2 || end2 <= start1: one range has to end before the other begins. Therefore, they overlap if (ed: and only if) end1 > start2 && end2 > start1.

To extend this principle to when the ranges might be empty, we need to handle that case and say that they cannot overlap if and only if:

   end1 <= start2
|| end2 <= start1
|| end1 == start1
|| end2 == start2

That is, if either range is empty, then no overlap is possible because there is no way for any value to appear in both ranges.

Turning this around, we recover something similar to @nikomatsakis' overlap_b rule. Specifically, I'd state it as:

fn does_overlap(r1: Range<usize>, r2: Range<usize>) -> bool {
    !(r1.end <= r2.start
      || r2.end <= r1.start
      || r1.is_empty()
      || r2.is_empty())
}

[workingjubilee]

I'm not sure a prohibition here would do anything to users, only to implementations

Hmm. One of my preferred mental models for Rust is one where the compiler is a very trustworthy Rust programmer who writes an unnerving amount of unsafe code, and especially asm!. Likewise, I sometimes explain that the rules of unsafe can often be thought of as manually upholding the rules the compiler also obeys.

And I would find it hard to explain to people who enjoy playing linker tricks with static items why they shouldn't arrange for a given static ZST to be found at an address that might be within a given object, considering it occupies zero bytes. Occasionally they actually link static objects of non-zero size to be potentially-overlapping, and then often a conversation starts where we explain that the bytes of statics can't really overlap like that. But they need the ability to point at addresses somehow. Sometimes we have explained they should use extern static, but the conversation usually arrives at something like "but linking in a separate crate just to make these statics extern is super annoying!" And if a ZST suits their needs of being such a "marker", that seems well-enough.

[workingjubilee]

Note I am happy to be corrected on this if all uses of ZST markers by people engaging in linker-script-shenanigans are compatible with them being ZSTs that are never "within" another object, but my memory was that trick was used in a few ways and that they were always at risk of this being a problem, i.e. they might want to put one or both of those markers inside a larger static.

[CAD97]

I think that allowing zero-sized static places to have an address strictly inside the address range of a different static is the slightly better choice. Because users can place statics at custom addresses by utilizing linker scripts, this isn't solely a question of restricting the implementation, but also one of restricting users. If implementation considerations are otherwise immaterial, the option with less potential UB should be preferred.

Zero-sized accesses/places are already special-cased, so special casing zero-sized static in the rule to explicitly exempt them from overlap rules doesn't seem unreasonable. But there are two very straightforward formulations that don't need to do so:

• static items cannot alias other static items (using the definition of aliasing from the reference aliasing model).
• No byte of memory is contained in more than one static item.

[nikomatsakis]

I'm finding this conversation interesting but I also feel a bit of a hostile tone that I am finding confusing. This is not the only instance, but one example is where @workingjubilee wrote the following:

Can T-lang explain the actual utility of this prohibition?

The actual comment in question said that the text as written was ambiguous and asked for clarification. Certainly some people in the discussion felt that having the start address of a ZST static lie within another static ought not to be allowed but others did not, and hence we decided to ask that the text either not answer the question or provide an answer.

I'm highlighting this because lately I've noticed a lot of technical discussions that feel heated to me and it's starting to wear me out. It would be really helpful to me at least if we can try to explore the pros/cons of this question and others in a more neutral way.

[nikomatsakis]

My two cents:

I agree with @workingjubilee's model of the compiler as "just another Rust programmer", that's how I like to think of it too (and I like to think of the type system as "guardrails" that keep you on the straight-and-narrow, but which you can choose to take off).

I don't know of specific utility from defining overlap based on the "start address", though I will say that I initially found it surprising to think of the address of a ZST-static falling inside another one, and so I can imagine people making that (perhaps incorrect) assumption. All this says is that we should be clear to document it whichever way we decide.

I am curious what people think about the uniqueness of ZST-statics as well. I think if I just consider the pointer value of a ZST-static to be effectively meaningless and arbitrary, which seems to be implied by definitions of overlap that focus on actual bytes, then it all makes a lot more sense to me and I agree seems consistent.

[pnkfelix]

@nikomatsakis wrote:

The actual comment in question said that the text as written was ambiguous and asked for clarification. Certainly some people in the discussion felt that having the start address of a ZST static lie within another static ought not to be allowed but others did not, and hence we decided to ask that the text either not answer the question or provide an answer.

Just to emphasize this point further: Niko's original comment neglected to include one point that I think all of T-lang agreed upon during our meeting yesterday: During our conversation, I believe the whole team agreed that we would support allowing this PR to make progress if it simply restricted the guarantee to be solely regarding interactions between positively-sized statics.

I.e., that would allow us leave the question of whether ZSTs also participated in the guarantee to be a matter we can resolve later.

(Obviously this would have the short-term effect of making the guarantees of zero-sized static items an implementation-specific detail that a programmer cannot rely upon (e.g. when writing unsafe code or linker scripts or whatnot), which is not an ideal state of affairs for the long-term. But it seemed to me from skimming the conversation in this thread that the participants here mostly cared about strengthening the guarantees for sets of positively-sized static items, and thus this compromise would be a reasonable way to make progress in the short term.)

---

Just to be clear: I do recognize that this compromise position would effectively mean delaying pinning down the definition of what "overlap" means, since the whole point of writing out overlap_a vs overlap_b was indeed about formally stating how zero-sized types (and, I think, values in general) should be treated. But I also think it is okay to delay that decision, as long as we e.g. open an issue saying that it still needs to be decided.

[nikomatsakis]

Thinking on this a bit more, what my message could've made clearer is that we were actively looking for a recommendation here (along with rationale) because it seemed unclear what was best and we recognize others are much closer to the discussion. If there was not consensus amongst those participants (or if we find we don't agree with the rationale) another option is to defer the question.

The motivation then to include the questions for consideration is that these are things that came up in the meeting so if the rationale or decision does not address this then we will likely just have the same questions again.

[workingjubilee]

What I was responding to was specifically @joshtriplett's comment:

In particular, I don't think it should be possible for a ZST to be in the middle of an unrelated object (e.g. an unrelated array of non-ZSTs).

@nikomatsakis proposed defining overlap as "the start of one object lies between the start and end of the other, exclusive". That would prevent that property.

Which doesn't seem to have a clear motivation behind why preventing that property is desirable, and it sounded pretty definite, at least? Perhaps I am attaching too much finality to "I don't think it should be possible"?

I'm aware I can come across as needling, and I don't particularly enjoy it either. I feel I get into situations like the one that started with this PR often enough, where everyone signs off on something within 2 hours and then suddenly raising my concern and making sure people understand it is immediately on a timer. Then I feel rushed and have to fumble together an explanation before people have Made Up Their Minds.

and honestly @nikomatsakis I'm sorry because I didn't read your message very closely as, seeing @joshtriplett's first, I was already typing and only kinda scanned what you said.

[nikomatsakis]

Thanks for the clarification, @workingjubilee, I appreciate your message. I believe @joshtriplett's comment was meant to convey his personal opinion, but it can be difficult to tell the difference sometimes, and I already said how I felt my message could've been clearer.

I have a few takeaways from this:

• When writing for the team, be explicit about when the team has a consensus position and when it does not.
• When writing for oneself, it never hurts to be extra explicit about whether you are speaking for yourself or the team.

In general, I like the pattern of teams like opsem (or types) providing recommendations and rationale, and lang having the role of "double checking" and raising questions. In some sense, I view lang as playing the role of the non-expert, whereas the teams are the experts in the domain. The result has to make sense to both.

[RalfJung]

I think going down the route of "an allocation 0 bytes cannot 'overlap' with an existing allocation" is a bad idea, because we would be: [...] inviting self-contradiction by complicating the model

I don't think so, the definition of "disjointness" that I suggested above is not particularly complicated.

implicitly saying ZSTs cannot actually exist in Rust in a way that is useful, by imposing constraints that say ZSTs can no longer be at certain locations, when programmers actually do rely on the ability to allocate ZSTs at certain locations!

That is the question, isn't it? Do they rely on this? Generally programmers can't allocate things at certain locations, the allocator picks the location. But people writing linker scripts might indeed be choosing locations for their statics.

Let's back up to first principles. Two ranges overlap if and only if there is some value that might appear in both ranges.

No, I don't think that has to be the usual definition of overlap of a range. Ranges are not sets.

I don't know which definition is more widely used in mathematics. @chorman0773 said my definition is used there; do you have a source for that? @digama0 do you have any idea?

To extend this principle to when the ranges might be empty, we need to handle that case and say that they cannot overlap if and only if:

No, my definition already covered the "empty range" case in the intended way. Sorry for not being clear about that.

fn does_overlap(r1: Range<usize>, r2: Range<usize>) -> bool {
    !(r1.end <= r2.start || r2.end <= r1.start)
}

---

Anyway, I'm also fine with just punting on the question for ZST for now. :shrug: It just pains me a little since I think many of the ways in which people think ZST are special aren't actually anything special, they fall out of the same general principles. For instance, people say things like "two &mut T have different addresses except when T is a ZST"... which is true but (a) unnecessarily complicated, and (b) unnecessarily weak. Instead we can say "two &mut T point to disjoint ranges of memory", and this is (a) stronger (e.g. if T is i32, it tells us they are at least 4 bytes apart), and (b) doesn't need an "except".

But in the interest of documenting what we have consensus on and not closing the door on future possibilites, I can try to adjust the PR to only be about non-ZST statics.

[digama0]

No, I don't think that has to be the usual definition of overlap of a range. Ranges are not sets.

I don't know which definition is more widely used in mathematics. @chorman0773 said my definition is used there; do you have a source for that? @digama0 do you have any idea?

I think that the definition of overlap of sets is clearly that they have empty intersection, but I think your definition makes more sense in this context. The difference of course is whether we want to say that [0, 2) overlaps [1, 1), which is false for sets because the latter set is empty, but is true under the endpoint-based definition. Off the top of my head I don't know a formalization of this interval order, I think it's not likely to come up except in CS-like contexts and in that case the definitions are usually tailored to the application anyway.

I recall a related version of this issue: We currently allow ZST's to be magicked up anywhere, such that <*const ()>::dangling(n) produces a valid pointer for any n. But if so, then that implies that we can also create ZST allocations in the middle of other allocations, so it would not be the case that allocations must be disjoint in the interval sense (although they are still disjoint in the set-of-bytes sense).

[RalfJung]

I recall a related version of this issue: We currently allow ZST's to be magicked up anywhere, such that <*const ()>::dangling(n) produces a valid pointer for any n. But if so, then that implies that we can also create ZST allocations in the middle of other allocations,

As mentioned above, "maigcking up" a ZST like that does not create a ZST allocation. It just creates a pointer/reference without provenance. Those are not the same thing.

---

I wonder if we are constrained by LLVM here... @nikic do you know if there will be trouble with LLVM when we have a zero-sized static located "inside" another static (or inside a stack/heap allocation)? When I do x = malloc(10), is LLVM then allowed to optimize static_addr <= x || static_addr >= x+10 to true?

[workingjubilee]

I went surveying various embedded software implementations using Rust today. Many of them do in fact use patterns that would prefer to be able to place static ZSTs at fairly arbitrary locations (including inside another static) and use those markers to generate slices in the ways we've discussed, because they need to somehow reason about fixed ranges of memory in slice-like manners. Ideally we would have some sort of pattern that enables writing this, and if not by using the setoid-based rule here, then we'd want something else.

One or two do in fact do everything in the most tedious way (entirely asm! and linker script), but not many seem to tolerate slogging through that mire (...they still gotta suffer through the linker script though).