[Bug libstdc++/65033] New: C++11 atomics: is_lock_free result does not always match the real lock-free property

[Bug libstdc++/65033] New: C++11 atomics: is_lock_free result does not always match the real lock-free property

[bin.x.fan at oracle dot com]

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

            Bug ID: 65033
           Summary: C++11 atomics: is_lock_free result does not always
                    match the real lock-free property
           Product: gcc
           Version: 4.9.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: bin.x.fan at oracle dot com

Hi,

The is_lock_free result for an object of type atomic<s3_t>, where s3_t is
size=3, alignment=1 C style struct, does not always match the implementation in
libatomic.so for atomic operations on this object. I think there is either a
bug in the g++ header <atomic> and the g++ 4.9.2 implementation is not C++11
standard conforming, or there is a bug in libatomic.so.

Here is the source code

-bash-4.1$ cat struct3.cc
#include <atomic>
#include <stdio.h>
using namespace std;
#define N 10
struct s3_t {
  char a[3];
};
atomic<s3_t> array[N];
s3_t obj;

int main()
{
  int i;
  for (i=0;i<N;i++) {
      printf ("%x\t", &array[i]);
      printf("%d\t", __atomic_always_lock_free(sizeof(array[i]), &array[i]));
      printf("%d\t", atomic_is_lock_free (&array[i]));
      printf("size: %d, align: %d\n", sizeof(array[i]), alignof(array[i]));
  }

  for (i=0;i<N;i++) {
      atomic_store (&array[i], obj);
  }

  return 0;
}

The bug is found on Solaris-SPARC, but it could be on other platforms as well.
The Solaris OS version is 11.2 Here is my g++ version. 

-bash-4.1$ g++ -v
Using built-in specs.
COLLECT_GCC=/net/dv104/export/tools/gcc/4.9.2/sparc-S2/bin/g++.bin
COLLECT_LTO_WRAPPER=/net/dv104/export/tools/gcc/4.9.2/sparc-S2/libexec/gcc/sparc-sun-solaris2.10/4.9.2/lto-wrapper
Target: sparc-sun-solaris2.10
Configured with: ../gcc-4.9.2/configure
--prefix=/net/dv104/export/tools/gcc/4.9.2/sparc-S2
--enable-languages=c,c++,fortran
--with-gmp=/net/dv104/export/tools/gcc/4.9.2/sparc-S2
--with-mpfr=/net/dv104/export/tools/gcc/4.9.2/sparc-S2
--with-mpc=/net/dv104/export/tools/gcc/4.9.2/sparc-S2
Thread model: posix
gcc version 4.9.2 (GCC) 

Here is the compiling options and run result:

-bash-4.1$ g++ -latomic -std=c++11 struct3.cc
-bash-4.1$ ./a.out
21680   0       1       size: 3, align: 1
21683   0       1       size: 3, align: 1
21686   0       1       size: 3, align: 1
21689   0       1       size: 3, align: 1
2168c   0       1       size: 3, align: 1
2168f   0       1       size: 3, align: 1
21692   0       1       size: 3, align: 1
21695   0       1       size: 3, align: 1
21698   0       1       size: 3, align: 1
2169b   0       1       size: 3, align: 1

The result seems correct. The atomic_is_lock_free always returns 1, which
conform to the C++11 standard 29.4: 
"The function atomic_is_lock_free (29.6) indicates whether the object is
lock-free. In any given program execution, the result of the lock-free query
shall be consistent for all pointers of the same type."

So the lock-free property is per-type, not per-object. atomic_is_lock_free
always returning 1 is a conforming behavior. However, on SPARC, it's impossible
to guarantee a 1-byte aligned 3-byte object to be always lock-free. That was my
first clue of this bug.

Digging it further, I found that for some objects, the atomic_store operation
is locked. To verify it, I ran the program under debugger and set a breakpoint
at function libat_lock_n, and I saw it is called.

=>[1] libat_lock_n(ptr = 0x216c6, n = 3U), line 64 in "lock.c"
  [2] libat_store(n = 3U, mptr = 0x216c6, vptr = 0xffbff580, smodel = 5), line
100 in "gstore.c"
  [3] std::atomic<s3_t>::store(this = 0x216c6, __i = STRUCT, _m =
memory_order_seq_cst), line 199 in "atomic"
  [4] std::atomic_store_explicit<s3_t>(__a = 0x216c6, __i = STRUCT, __m =
memory_order_seq_cst), line 828 in "atomic"
  [5] std::atomic_store<s3_t>(__a = 0x216c6, __i = STRUCT), line 895 in
"atomic"
  [6] main(), line 22 in "struct3.cc"

So one of the following two things could be happening here
1. g++ makes lock-free property per-object, which is not C++11 standard
conforming, and report it incorrectly with atomic_is_lock_free, or
2. g++ tries to make lock-free property per-type, but the libatomic.so
implementation does not match. Also, without changing the alignment, I doubt
that size=3 alignment=1 atomic object can always be lock-free on SPARC or x86.

[Bug libstdc++/65033] C++11 atomics: is_lock_free result does not always match the real lock-free property

[pinskia at gcc dot gnu.org]

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

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Aren't pointers in this case lock free?

[Bug libstdc++/65033] C++11 atomics: is_lock_free result does not always match the real lock-free property

[redi at gcc dot gnu.org]

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

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
See PR54005 for some of the history.

[Bug libstdc++/65033] C++11 atomics: is_lock_free result does not always match the real lock-free property

[jason at gcc dot gnu.org]

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

Jason Merrill <jason at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-02-12
                 CC|                            |jason at gcc dot gnu.org,
                   |                            |rth at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #3 from Jason Merrill <jason at gcc dot gnu.org> ---
(In reply to Bin Fan from comment #0)
> 2. g++ tries to make lock-free property per-type, but the libatomic.so
> implementation does not match.

This.  We always pass a null pointer to libatomic and do not pass any
information about the alignment of the type.  rth suggested that we might try
passing a fake, minimally-aligned pointer instead of null as a way of
communicating the alignment without adding a new entry point.

[Bug libstdc++/65033] C++11 atomics: is_lock_free result does not always match the real lock-free property

[rth at gcc dot gnu.org]

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

Richard Henderson <rth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rth at gcc dot gnu.org

--- Comment #4 from Richard Henderson <rth at gcc dot gnu.org> ---
Mine.

[Bug libstdc++/65033] C++11 atomics: is_lock_free result does not always match the real lock-free property

[bin.x.fan at oracle dot com]

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

--- Comment #5 from Bin Fan <bin.x.fan at oracle dot com> ---
(In reply to Jason Merrill from comment #3)
> (In reply to Bin Fan from comment #0)
> > 2. g++ tries to make lock-free property per-type, but the libatomic.so
> > implementation does not match.
> 
> This.  We always pass a null pointer to libatomic and do not pass any
> information about the alignment of the type.  rth suggested that we might
> try passing a fake, minimally-aligned pointer instead of null as a way of
> communicating the alignment without adding a new entry point.

So after the fix, atomic_is_lock_free will always return 0 for size=3,align=1
atomic struct objects?

I understand currently libatomic tries to make an atomic object lock-free if
its memory location fit in a certain sized window. So for atomic operations
such as atomic_store where the actual address is passed in, the operation can
be still either lock-free or locked, right? I'm wondering if it's standard
conforming since the lock-free property is still per-object, or it can be seen
as an optimization, i.e. atomic_is_lock_free query for the object returns 0,
but atomic operations on the object could be lock-free.

[Bug libstdc++/65033] C++11 atomics: is_lock_free result does not always match the real lock-free property

[rth at gcc dot gnu.org]

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

--- Comment #6 from Richard Henderson <rth at gcc dot gnu.org> ---
(In reply to Bin Fan from comment #5)
> So after the fix, atomic_is_lock_free will always return 0 for
> size=3,align=1 atomic struct objects?

Yes.

> I understand currently libatomic tries to make an atomic object lock-free if
> its memory location fit in a certain sized window. So for atomic operations
> such as atomic_store where the actual address is passed in, the operation
> can be still either lock-free or locked, right?

Yes.

> I'm wondering if it's standard conforming since the lock-free property
> is still per-object, or it can be seen as an optimization, i.e. 
> atomic_is_lock_free query for the
> object returns 0, but atomic operations on the object could be lock-free.

My understanding is that it's valid to optimize the operation to lock-free,
but since there may exist objects for which we will have to use the lock,
the atomic_is_lock_free query must return false.

[Bug libstdc++/65033] C++11 atomics: is_lock_free result does not always match the real lock-free property

[rth at gcc dot gnu.org]

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

--- Comment #7 from Richard Henderson <rth at gcc dot gnu.org> ---
Author: rth
Date: Thu Mar 26 18:31:11 2015
New Revision: 221701

URL: https://gcc.gnu.org/viewcvs?rev=221701&root=gcc&view=rev
Log:
PR libstdc++/65033

 * include/bits/atomic_base.h (__atomic_base<T>::is_lock_free): Build
 a fake pointer indicating type alignment.
 (__atomic_base<T *>::is_lock_free): Likewise.
 * include/std/atomic (atomic<T>::is_lock_free): Likewise.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/atomic_base.h
    trunk/libstdc++-v3/include/std/atomic

[Bug libstdc++/65033] C++11 atomics: is_lock_free result does not always match the real lock-free property

[rth at gcc dot gnu.org]

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

Richard Henderson <rth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED
   Target Milestone|---                         |5.0

--- Comment #8 from Richard Henderson <rth at gcc dot gnu.org> ---
Fixed.

[Bug libstdc++/65033] C++11 atomics: is_lock_free result does not always match the real lock-free property

[bin.x.fan at oracle dot com]

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

--- Comment #9 from Bin Fan <bin.x.fan at oracle dot com> ---
I verified this bug is fixed in 5.1.0. However, it is only fixed in g++, so now
in 5.1.0, gcc and g++ reports different result:

-bash-4.1$ cat is_lock_free.c
#include <stdatomic.h>
#include <stdio.h>
#define N 10
typedef struct {
  char a[3];
} s3_t;
_Atomic s3_t array[N];
s3_t obj;

int main()
{
  int i;
  for (i=0;i<N;i++) {
      printf ("%x\t", &array[i]);
      printf("%d\n", atomic_is_lock_free (&array[i]));
  }

  for (i=0;i<N;i++) {
      atomic_store (&array[i], obj);
  }

  return 0;
}

gcc -latomic is_lock_free.c 
./a.out
20ff7   0
20ffa   1
20ffd   1
21000   1
21003   1
21006   0
21009   1
2100c   1
2100f   0
21012   1

-bash-4.1$ cat is_lock_free.cc 
#include <atomic>
#include <stdio.h>
using namespace std;
#define N 10
struct s3_t {
  char a[3];
};
atomic<s3_t> array[N];
s3_t obj;

int main()
{
  int i;
  for (i=0;i<N;i++) {
      printf ("%x\t", &array[i]);
      printf("%d\n", atomic_is_lock_free (&array[i]));
  }

  for (i=0;i<N;i++) {
      atomic_store (&array[i], obj);
  }

  return 0;
}

g++ -std=c++11 -latomic is_lock_free.cc
./a.out
21524   0
21527   0
2152a   0
2152d   0
21530   0
21533   0
21536   0
21539   0
2153c   0
2153f   0

Isn't the difference between C and C++ still a problem?