Page MenuHomePhabricator

[libcxx] Fix undefined behavior in forward_list
ClosedPublic

Authored by EricWF on Dec 31 2015, 12:37 AM.

Details

Summary

This patch is similar to the <list> fix but it has a few differences. This patch doesn't use a __link_pointer typedef because we don't need to change the linked list pointers because forward_list never stores a __forward_begin_node in the linked list itself.

The issue with forward_list is that the iterators store pointers to __forward_list_node and not __forward_begin_node. This is incorrect because before_begin() and cbefore_begin() return iterators that point to a __forward_begin_node. This means we incorrectly downcast the __forward_begin_node pointer to a __node_pointer. This downcast itself is sometimes UB but it cannot be safely removed until ABI v2. The more common cause of UB is when we deference the downcast pointer. (for example __ptr_->__next_). This can be fixed without an ABI break by upcasting __ptr_ before accessing it.

The fix is as follows:

  1. Introduce a __iter_node_pointer typedef that works similar to __link_pointer in the last patch. In ABI v2 it is always a typedef for __begin_node_pointer.
  2. Change the __before_begin() method to return the correct pointer type (__begin_node_pointer), Previously it incorrectly downcasted the __forward_begin_node to a __node_pointer so it could be used to constructor the iterator types.
  3. Change __forward_list_iterator and __forward_list_const_iterator in the following way:
    1. Change __node_pointer __ptr_; member to have the __iter_node_pointer type instead.
    2. Add additional private constructors that accept __begin_node_pointer in addition to __node_pointer and then correctly cast them to the stored __iter_node_pointer type.
    3. Add __get_begin() and __get_node_unchecked() accessor methods that correctly cast __ptr_ to the expected pointer type. __get_begin() is always safe to use and should be preferred. __get_node_unchecked() can only be used on a deferencible iterator.
  4. Replace direct access to __forward_list_iterator::__ptr_ with the safe accessor methods.

Diff Detail

Repository
rL LLVM

Event Timeline

EricWF updated this revision to Diff 43820.Dec 31 2015, 12:37 AM
EricWF retitled this revision from to [libcxx] Fix undefined behavior in forward_list.
EricWF updated this object.
EricWF added a reviewer: mclow.lists.
EricWF added a subscriber: cfe-commits.
EricWF updated this revision to Diff 43824.Dec 31 2015, 1:07 AM

forward_list and it's iterators should allow incomplete types in C++17 and beyond. I updated the patch to fix this issue as a drive-by.

mclow.lists edited edge metadata.Jan 25 2016, 9:04 AM

This looks good to me.

include/forward_list
369 ↗(On Diff #43824)

I would think about calling this __get_node_dereferencable or something similar.
When I looked at this first, I wondered "is there another call that does checking?"

EricWF updated this revision to Diff 46071.Jan 26 2016, 4:14 PM
EricWF edited edge metadata.

Address @mclow.lists comment about __get_node_unchecked()'s name.

EricWF accepted this revision.Jan 26 2016, 4:15 PM
EricWF added a reviewer: EricWF.

Accepting on phab to reflect @mclow.lists LGTM.

include/forward_list
369 ↗(On Diff #43824)

__get_node_unchecked definitely needs a new name then because the returned pointers are not guaranteed to be dereferencable.

I'll change this to "__get_unsafe_node_pointer".

This revision is now accepted and ready to land.Jan 26 2016, 4:15 PM
EricWF closed this revision.Jan 26 2016, 4:16 PM
This revision was automatically updated to reflect the committed changes.