[LLVMbugs] [Bug 18488] New: std::list-functions executed in the wrong order (seemingly due to a strict-aliasing problem)

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=18488

            Bug ID: 18488
           Summary: std::list-functions executed in the wrong order
                    (seemingly due to a strict-aliasing problem)
           Product: libc++
           Version: unspecified
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: All Bugs
          Assignee: hhinnant at apple.com
          Reporter: buglibcxx at lancom.de
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

Created attachment 11875
  --> http://llvm.org/bugs/attachment.cgi?id=11875&action=edit
Source file which is miscompiled due to this bug

The following function should prepend one item to the list and return an
iterator to that item. In my setup, it returns an iterator to the first list
element before the insert instead (or end() if the list was empty), just as if
it had executed the two calls in the opposite order.

typedef std::list<int> tList;
tList::iterator prepend(tList &list, int value)
{
  list.push_front(value);
  return list.begin();
}

Steps to reproduce:
* Checkout head:
  * svn co http://llvm.org/svn/llvm-project/libcxx/trunk libcxx
* Build according to guidelines using libsup++:
  * mkdir libcxx/build & cd libcxx/build
  * CC=clang CXX=clang++ cmake -G "Unix Makefiles" -DLIBCXX_CXX_ABI=libsupc++
-DLIBCXX_LIBSUPCXX_INCLUDE_PATHS="/usr/include/c++/4.7/;/usr/include/x86_64-linux-gnu/c++/4.7/"
-DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX=. ..
  * make
  * make install (abort an endless loop when header files are copied)
* Build sample file main.cpp from checkout dir:
  * g++ -g -std=c++11 -nostdinc++ -O3 -Ilibcxx/build/include/c++/v1
-Llibcxx/build/lib/ -lsupc++ main.cpp
* Execute: ./a.out && echo "OK"
  * This should output "OK", but due to the bug it is silent instead
* As a simple workaround declare the variables __prev_ and __next_ of struct
__list_node_base in include/list as volatile and try again. This time you see
the "OK"

Software versions in my case:
* Ubuntu Linux 13.04, 64-bit
* svn, Version 1.7.5 (r1336830)
* libc++ SVN-Revision 199221 (recent head revision)
* cmake version 2.8.10.1
* g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3

Here is what g++ produces in the erroneous case with my annotations:
Dump of assembler code for function prepend(std::__1::list<int,
std::__1::allocator<int> >&, int):
   0x00000000004007a0 <+0>:    mov    %rbx,-0x10(%rsp)
   0x00000000004007a5 <+5>:    mov    %rbp,-0x8(%rsp)
   0x00000000004007aa <+10>:    mov    %rdi,%rbx              ; now %rbx points
to __list_imp.__end_
   0x00000000004007ad <+13>:    sub    $0x18,%rsp
   0x00000000004007b1 <+17>:    mov    $0x18,%edi             ; size argument
for the following call
   0x00000000004007b6 <+22>:    mov    %esi,%ebp              ; now %ebp
contains the value
   0x00000000004007b8 <+24>:    callq  0x400640 <_Znwm at plt>   ; allocate memory
for __list_node
   0x00000000004007bd <+29>:    cmp    $0xfffffffffffffff0,%rax
   0x00000000004007c1 <+33>:    mov    %rax,%rdx              ; now %rdx points
to the allocated __list_node
   0x00000000004007c4 <+36>:    je     0x4007c9 <prepend(std::__1::list<int,
std::__1::allocator<int> >&, int)+41>
   0x00000000004007c6 <+38>:    mov    %ebp,0x10(%rax)        ; set
__list_node::__value_
   0x00000000004007c9 <+41>:    mov    0x8(%rbx),%rax         ; now %rax
contains __list_imp.__end_.__next_
   0x00000000004007cd <+45>:    mov    0x10(%rsp),%rbp
   0x00000000004007d2 <+50>:    mov    (%rax),%rcx            ; now %rcx
contains __list_imp.__end_.next->prev, which points back to __list_imp.__end_
   0x00000000004007d5 <+53>:    mov    %rdx,0x8(%rcx)         ; redirects
__list_imp.__end_.__next_ to point to the new node
   0x00000000004007d9 <+57>:    mov    %rcx,(%rdx)            ; inits __prev_
of the new node to point back to __list_imp.__end_
   0x00000000004007dc <+60>:    mov    %rax,0x8(%rdx)         ; inits __next_
of the new node to point to the former successor of __list_imp.__end_
   0x00000000004007e0 <+64>:    mov    %rdx,(%rax)            ; redirects
__prev_ of the former successor of __list_imp.__end_ to point to the new node
   0x00000000004007e3 <+67>:    addq   $0x1,0x10(%rbx)
   0x00000000004007e8 <+72>:    mov    0x8(%rsp),%rbx
   0x00000000004007ed <+77>:    add    $0x18,%rsp
   0x00000000004007f1 <+81>:    retq                          ; return %rax,
which was last set in line <+41> and points to the *former* successor of
__list_imp.__end_, but not to the added node, which is the *new* successor of
__list_imp.__end_ now

I have investigated the cause of that misbehaviour and found the following bug:
list::push_front() calls list::__link_nodes, which alters the __prev_ and
__next_ fields of several nodes via __node_pointers, which have the target type
__list_node. In the case of list::push_front(), however, one of the writes
changes the field __next_ of __list_imp::__end_, which has the type
__list_node_base. According to the C++ standard, chapter 3.10.10 (strict
aliasing), the behaviour of this write is undefined, because you have a glvalue
of type __list_node, but the accessed object has a dynamic type of
__list_node_base, which is not a subclass of __list_node (instead, it is a base
class thereof).

Here is, what I guess, what the compiler thinks:
The first line of list::__link_nodes() writes to __next_ through a
__list_node*. According to the usual rules, a __list_node* may point to an
object of class __list_node or any subclass thereof. list::begin(), however,
just reads __list_imp.__end_.__next_, and here the compiler knows, that the
runtime type of __list_imp.__end_ is exactly __list_node_base and not and
subclass thereof. So we have a write to a __list_node-or-subclass object and a
read from a __list_node_base object. Since no object can possibly be both of
type __list_node_base and of a subclass of __list_node, the write and the read
are obviously independent and may thus be executed in any order. Furthermore,
the compiler sees that list::__link_nodes() has already called list::begin()
before and its result is still in register %rax. So it can safely refrain from
reading that value from memory again.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20140115/f21c151c/attachment.html>