[Bug libstdc++/100153] New: Undefined behavior in stl_bvector.h

[Bug libstdc++/100153] New: Undefined behavior in stl_bvector.h

[hewillk at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100153

            Bug ID: 100153
           Summary: Undefined behavior in stl_bvector.h
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: hewillk at gmail dot com
  Target Milestone: ---

stl_bvector.h#L505:

  _Bit_type*
  _M_end_addr() const _GLIBCXX_NOEXCEPT
  {
    if (this->_M_end_of_storage)
      return std::__addressof(this->_M_end_of_storage[-1]) + 1;
    return 0;
  }

This one will cause UB if _M_end_of_storage is not nullptr and
_M_end_of_storage is equal to _M_start._M_p.

Consider (https://godbolt.org/z/vvrG6KcWP):

  std::vector<bool> bv{true, false, true};
  bv.clear();
  bv.shrink_to_fit();
  bv.capacity();

When shrink_to_fit() ends, _M_end_of_storage will be equal to _M_start._M_p and
not nullptr. In capacity():

  size_type
  capacity() const _GLIBCXX_NOEXCEPT
  { return size_type(const_iterator(this->_M_impl._M_end_addr(), 0)
    - begin()); }

we will call _M_end_addr() and perform illegal dereference which cause UB, same
with push_back(), insert() and flip().

[Bug libstdc++/100153] Undefined behavior in stl_bvector.h

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100153

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-04-20

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I think the bug is that vector<bool>::shrink_to_fit() always allocates, even if
the new capacity is zero.

It should set _M_start._M_p == _M_end_of_storage == nullptr

[Bug libstdc++/100153] Undefined behavior in stl_bvector.h

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100153

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed downstream:
https://gitlab.com/jonathan-wakely/gcc/-/commit/0df97f13e88fe8383b5663bb51de1fa691537cc4

[Bug libstdc++/100153] Undefined behavior in stl_bvector.h

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100153

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed downstream (corrected URL):
https://gitlab.com/jonathan-wakely/gcc/-/commit/9487ef2967f89f1cd25bcf4f922bd40ecf18e9ea

[Bug libstdc++/100153] Undefined behavior in stl_bvector.h

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100153

--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:681707ec28d56494fa61a80c62500724d55f8586

commit r12-4062-g681707ec28d56494fa61a80c62500724d55f8586
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Apr 20 16:16:13 2021 +0100

    libstdc++: Do not allocate a zero-size vector<bool> [PR 100153]

    The vector<bool>::shrink_to_fit() implementation will allocate new
    storage even if the vector is empty. That then leads to the
    end-of-storage pointer being non-null and equal to the _M_start._M_p
    pointer, which means that _M_end_addr() has undefined behaviour.

    The fix is to stop doing a useless zero-sized allocation in
    shrink_to_fit(), so that _M_start._M_p and _M_end_of_storage are both
    null after an empty vector shrinks.

    Signed-off-by: Jonathan Wakely <jwakely@redhat.com>

    libstdc++-v3/ChangeLog:

            PR libstdc++/100153
            * include/bits/vector.tcc (vector<bool>::_M_shrink_to_fit()):
            When size() is zero just deallocate and reset.

[Bug libstdc++/100153] Undefined behavior in stl_bvector.h

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100153

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |9.5
           Keywords|                            |wrong-code

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed on trunk for now.

[Bug libstdc++/100153] Undefined behavior in stl_bvector.h

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100153

--- Comment #6 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:c04b0f63243d4d474daa66f84874ebf6b9e7b0cd

commit r11-9281-gc04b0f63243d4d474daa66f84874ebf6b9e7b0cd
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Apr 20 16:16:13 2021 +0100

    libstdc++: Do not allocate a zero-size vector<bool> [PR 100153]

    The vector<bool>::shrink_to_fit() implementation will allocate new
    storage even if the vector is empty. That then leads to the
    end-of-storage pointer being non-null and equal to the _M_start._M_p
    pointer, which means that _M_end_addr() has undefined behaviour.

    The fix is to stop doing a useless zero-sized allocation in
    shrink_to_fit(), so that _M_start._M_p and _M_end_of_storage are both
    null after an empty vector shrinks.

    Signed-off-by: Jonathan Wakely <jwakely@redhat.com>

    libstdc++-v3/ChangeLog:

            PR libstdc++/100153
            * include/bits/vector.tcc (vector<bool>::_M_shrink_to_fit()):
            When size() is zero just deallocate and reset.

    (cherry picked from commit 681707ec28d56494fa61a80c62500724d55f8586)

[Bug libstdc++/100153] Undefined behavior in stl_bvector.h

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100153

--- Comment #7 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:60da20c0cdfb6df11bce054ba82b71a0a24a1bd9

commit r10-10575-g60da20c0cdfb6df11bce054ba82b71a0a24a1bd9
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Apr 20 16:16:13 2021 +0100

    libstdc++: Do not allocate a zero-size vector<bool> [PR 100153]

    The vector<bool>::shrink_to_fit() implementation will allocate new
    storage even if the vector is empty. That then leads to the
    end-of-storage pointer being non-null and equal to the _M_start._M_p
    pointer, which means that _M_end_addr() has undefined behaviour.

    The fix is to stop doing a useless zero-sized allocation in
    shrink_to_fit(), so that _M_start._M_p and _M_end_of_storage are both
    null after an empty vector shrinks.

    Signed-off-by: Jonathan Wakely <jwakely@redhat.com>

    libstdc++-v3/ChangeLog:

            PR libstdc++/100153
            * include/bits/vector.tcc (vector<bool>::_M_shrink_to_fit()):
            When size() is zero just deallocate and reset.

    (cherry picked from commit 681707ec28d56494fa61a80c62500724d55f8586)

[Bug libstdc++/100153] Undefined behavior in stl_bvector.h

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100153

--- Comment #8 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-9 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:b4a170bf3a2b0397a5d73f7cac24f6df4298569e

commit r9-10058-gb4a170bf3a2b0397a5d73f7cac24f6df4298569e
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Apr 20 16:16:13 2021 +0100

    libstdc++: Do not allocate a zero-size vector<bool> [PR 100153]

    The vector<bool>::shrink_to_fit() implementation will allocate new
    storage even if the vector is empty. That then leads to the
    end-of-storage pointer being non-null and equal to the _M_start._M_p
    pointer, which means that _M_end_addr() has undefined behaviour.

    The fix is to stop doing a useless zero-sized allocation in
    shrink_to_fit(), so that _M_start._M_p and _M_end_of_storage are both
    null after an empty vector shrinks.

    Signed-off-by: Jonathan Wakely <jwakely@redhat.com>

    libstdc++-v3/ChangeLog:

            PR libstdc++/100153
            * include/bits/vector.tcc (vector<bool>::_M_shrink_to_fit()):
            When size() is zero just deallocate and reset.

    (cherry picked from commit 681707ec28d56494fa61a80c62500724d55f8586)

[Bug libstdc++/100153] Undefined behavior in stl_bvector.h

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100153

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for 9.5, 10.4, 11.3 and 12.1