Hardening checks should detect dereferencing map.end() and set.end()

[davidben]

One of the most common patterns with map and set types is to call find, check the iterator against end(), and dereference the iterator. If you forget to perform this check, libc++'s hardening mode doesn't seem to catch this and just returns garbage values.

• std::map: https://godbolt.org/z/TddKM3r1M
• set::set: https://godbolt.org/z/67a61a7n7
• set::unordered_map: https://godbolt.org/z/beGesh9j3
• std::unordered_set: https://godbolt.org/z/q9q7qrKqj

(CC @danakj)

[davidben]

Looking at the std::map it looks like end() points to a special valueless end node embedded inside the container. If that's right, I think that means referencing end() causes you to read whatever follows the std::map in memory, so definitely something to harden!

I couldn't find an obvious way to distinguish the end node from normal nodes, given a pointer, but I see __tree_node_base contains:

  pointer __right_;
  __parent_pointer __parent_;
  bool __is_black_;

So that means we have plenty of padding left. We'd still have to take an ABI break because inlined functions would stop working, but I'd suggest sticking a bool __is_end_ after __is_black_ and asserting on that.

[davidben]

I am a little confused why the unordered ones aren't already cleanly segfaulting though. If I'm reading that right, the end iterator is just a null pointer? Might be misreading that one.

[davidben]

...oh. It's because Clang has noticed that code unconditionally dereferences a null pointer and kindly deleted the entire function, including the return. So it's just continued on executing garbage. Pretty impressive but perhaps not indicative of what will happen to real-world code. Still, we can stick a _LIBCPP_ASSERT_NON_NULL in there.

[davidben]

Another option for std::map and std::set: #80234 (comment)

That's probably the way to go.

[davidben]

Okay, that also doesn't work. That means non-end iterators are invalidated after move, and we're required to preserve those iterators, just not the end iterator for some reason. (Such a weird set of guarantees...)
https://eel.is/c++draft/container.requirements.general#container.reqmts-66.6

Also my idea about __is_end_ above doesn't work because the end node only has __left_.

New new idea: pay a single extra pointer per std::map and move __parent_ from the base into the end node. Then detect the end node because it's the only node without a parent. (Alas that won't translate to std::list because std::list is circular. And getting the compiler to delete it will be tricky.)