8

When I compile this program:

#include <list>

int main() {
    std::list<int> l = {1, 2};
    l.remove(l.front());
}

With clang using ASAN and debug:

clang++-8 -fno-omit-frame-pointer -g -fsanitize=address -D_GLIBCXX_DEBUG -std=c++11 list-remove.cpp

I get a heap-use-after-free:

==31868==ERROR: AddressSanitizer: heap-use-after-free on address 0x603000000020 at pc 0x0000004fa1ae bp 0x7fff52cc5630 sp 0x7fff52cc5628
READ of size 4 at 0x603000000020 thread T0
    #0 0x4fa1ad in std::__debug::list<int, std::allocator<int> >::remove(int const&) /usr/bin/../lib/gcc/x86_64-linux-gnu/7.4.0/../../../../include/c++/7.4.0/debug/list:649:18
    #1 0x4f990f in main /tmp/list-remove.cpp:5:7
    #2 0x7ff27d974b96 in __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:310
    #3 0x41b879 in _start (/tmp/list-remove+0x41b879)

It seems when remove finds x matches the first element, it removes the element from the list and deletes it. When it goes to check the second element, it then uses x which has already been deleted to compare the element.

Is this a correct implementation according to C++ standard? It seems it would be better for it to move the elements to the end first and then delete them. This will avoid the heap-use-after-free error, but perhaps such an implementation is not required.

From cppreference it makes no mention that the value cannot be an alias to the element in the container.

Here is the c++ version I am using:

$ /usr/bin/c++ --version
c++ (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Paul Fultz II
  • 17,682
  • 13
  • 62
  • 59
  • @FrançoisAndrieux Did you build with `-D_GLIBCXX_DEBUG`? – Paul Fultz II Sep 20 '19 at 18:00
  • 4
    Hmm. We don't require `std::remove` to work in such scenarios. I'm not sure why we'd require `list::remove` to, but the wording is missing. – T.C. Sep 20 '19 at 18:03
  • Looking at the standard as is, it is a bug. That said, I would assume the usual self referencing rule should apply like it does for `std::remove` and instead the standard has a defect and the code is correct. – NathanOliver Sep 20 '19 at 18:06
  • The online draft also doesn't mention that limitation for `std::list`: http://eel.is/c++draft/list#ops-15 Neither does if for `std::remove()` though: http://eel.is/c++draft/alg.remove – Deduplicator Sep 20 '19 at 18:13
  • @T.C. I can't actually find anything in the standard saying `remove` doesn't have to work when a reference to an element is passed. Do you know where that is/why cppreference has it in the note? – NathanOliver Sep 20 '19 at 18:22
  • 1
    @NathanOliver We only require move assignment, so it can't possibly work. This was brought up in the library reflector this April. Responses were...unsympathetic. – T.C. Sep 20 '19 at 18:35
  • @T.C. It just seems weird that there is no wording one way or the other. `std::valarray` for instance [handles things like this](http://coliru.stacked-crooked.com/a/5f05dd2580db3164) without any wording about it. – NathanOliver Sep 20 '19 at 18:45
  • @T.C. It seems that libc++ now collects the deleted elements in a separate list and delete them together after all elements are checked. This way, copy isn't required – L. F. Oct 03 '19 at 05:38
  • @L.F. For `list::remove`, yes, it's doable. For `std::remove`, no. – T.C. Oct 06 '19 at 23:59
  • @T.C. Oops, sorry. I misread your comment somehow. – L. F. Oct 07 '19 at 00:29

1 Answers1

6

This question was asked (and answered) in LWG 526, which said:

list::remove(value) is required to work because the standard doesn't give permission for it not to work.

This was fixed in libc++ back in 2014

Marshall Clow
  • 15,972
  • 2
  • 29
  • 45