2013/10/25 Andrey Semashev <andrey.semashev@gmail.com>

intrusive_ptr is not trivial-copyable, precisely because it has to operate on the counter. Using memcpy for copying it is not correct.

For this reason it is

not compatible with atomic<>. You have to use raw pointers with atomic<>.

I don't agree because the standard told us: 1.) 'For any object of trivially copyable type T, whether or not the object holds a valid value of type T, the underlying bytes making up the object can be copied into an array of char or unsigned char. If the content of the array of char or unsigned char is copied back into the object, the object shall subsequently hold its original value.' #define N sizeof(T) char buf[N]; T obj; std::memcpy(buf, &obj, N); std::memcpy(&obj, buf, N); this is correct for intrusive_ptr<T>. 2.) 'For any trivially copyable type T, if two pointers to T point to distinct T objects obj1 and obj2, where neither obj1 nor obj2 is a base-class subobject, if the underlying bytes (1.7) making up obj1 are copied into obj2,41 obj2 shall subsequently hold the same value as obj1.' T* t1p; T* t2p; std::memcpy(t1p, t2p, sizeof(T)); this is correct for intrusive_ptr<T> too. The only open question is: does the use-counter semantics prevent using intrusive_ptr<T> together with atomic?. you could increment the use-counter before and decrement the use-counter after using it with atomic<>.

2013/10/25 Giovanni Piero Deretta <gpderetta@gmail.com>

Intrusive_ptr doesn't have tivial copy constructor (how could it have? it needs to update the counter), ergo is not trivially copyable and the above two point do not apply.

but the standard says 'trivially copyable' not 'trivial copy constructor' - e.g. the code examples by the standard document gives correct results for intrusive_ptr (because all criteria are fulfilled). does this mean the standard document contains a false wording/examples?

On Friday 25 October 2013 10:25:16 Giovanni Piero Deretta wrote:

On Fri, Oct 25, 2013 at 10:22 AM, Oliver Kowalke

<oliver.kowalke@gmail.com>wrote:

...

2013/10/25 Giovanni Piero Deretta <gpderetta@gmail.com>

...

Intrusive_ptr doesn't have tivial copy constructor (how could it have? it needs to update the counter), ergo is not trivially copyable and the

above

...

two point do not apply.

but the standard says 'trivially copyable' not 'trivial copy constructor' - e.g. the code examples by the standard document gives correct results for intrusive_ptr (because all criteria are fulfilled). does this mean the standard document contains a false wording/examples?

I do not have the standard at hand, but a trivially copyable class is a class that: 1. Has no non-trivial copy constructors (this also requires no virtual functions or virtual bases)

2. Has no non-trivial move constructors

3. Has no non-trivial copy assignment operators

4. Has no non-trivial move assignment operators

5. Has a trivial destructor

[from cppreference.com, which may or may not be authoritative]

You are correct, I'll just provide some references: Trivially copyable types are defined in 3.9/9 [basic.types]. [...] Scalar types, trivially copyable class types (Clause 9), arrays of such types, and cv-qualified versions of these types (3.9.3) are collectively called trivially copyable types. [...] Trivially copyable class types are defined in 9/6 [class]. A trivially copyable class is a class that: — has no non-trivial copy constructors (12.8), — has no non-trivial move constructors (12.8), — has no non-trivial copy assignment operators (13.5.3, 12.8), — has no non-trivial move assignment operators (13.5.3, 12.8), and — has a trivial destructor (12.4). A trivial class is a class that has a trivial default constructor (12.1) and is trivially copyable. [ Note: In particular, a trivially copyable or trivial class does not have virtual functions or virtual base classes. — end note ]

On Fri, Oct 25, 2013 at 11:48 AM, Oliver Kowalke <oliver.kowalke@gmail.com>wrote:

2013/10/25 Giovanni Piero Deretta <gpderetta@gmail.com>

I'm referring to standard doc at http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf Section 3.9. Types -> the example code works for intrusive_ptr too.

Well, no, the point is that it won't: char buf[N]; T obj; std::memcpy(buf, &obj, N); std::memcpy(&obj, buf, N); For T = boost::intrusive_ptr<T2>, the above code formally leads to UB, as intrusive_ptr is not trivially copiable. It might (or not) work in practice, but in the case of std::atomic, it will bypass the copy constructor which means that the reference count won't be updated. -- gpd

On Fri, Oct 25, 2013 at 12:10 PM, Oliver Kowalke <oliver.kowalke@gmail.com>wrote:

2013/10/25 Giovanni Piero Deretta <gpderetta@gmail.com>

...

char buf[N]; T obj; std::memcpy(buf, &obj, N); std::memcpy(&obj, buf, N);

For T = boost::intrusive_ptr<T2>, the above code formally leads to UB, as intrusive_ptr is not trivially copiable.

It might (or not) work in practice, but in the case of std::atomic, it will bypass the copy constructor which means that the reference count won't be updated.

the use-count can be 'adjusted' before, e.g. prevent deallocating the object owned by the intrusive_ptr unintentionally.

that's the tricky part. To adjust the reference count, you must load and dereference the pointer itself, but between those two operations another thread might come in, replace the pointer, adjust the original pointer count down and free the pointed object, together with the counter. You need some way to defer destruction till a safe point (RCU, hazard pointers, etc). -- gpd

On Fri, Oct 25, 2013 at 12:43 PM, Oliver Kowalke <oliver.kowalke@gmail.com>wrote:

2013/10/25 Giovanni Piero Deretta <gpderetta@gmail.com>

...

that's the tricky part. To adjust the reference count, you must load and dereference the pointer itself, but between those two operations another thread might come in, replace the pointer, adjust the original pointer count down and free the pointed object, together with the counter. You need some way to defer destruction till a safe point (RCU, hazard pointers, etc).

what about this

// use-counter in T is an atomic too array< atomic< intrusive_ptr< T > >, 100 > a;

intrusive_ptr< T > p(...); intrusive_ptr_add_ref( p.get() ); // add an intrusive_ptr to the array if ( a[index].compare_exchange_strong(null_ptr,p) ) { // successful added }

// remove an interusive_ptr from array intrusive_ptr< T > e; // points to nothing if ( ! a[index].compare_exchange_strong(e, null_ptr) ) { // successfull removed intrusive_ptr_release( e.get() ); }

Nice! If these produce and consume are the only two operations on the array, from a cursory look, it should work fine. For the producer, a simple store with release semantics might actually be enough. The reason these operations should work is that they are actually move operations and do not change the count itself. What you can't do is copy a value out of the array leaving the original in place. -- gpd

On Friday 25 October 2013 13:43:38 Oliver Kowalke wrote:

2013/10/25 Giovanni Piero Deretta <gpderetta@gmail.com>

...

that's the tricky part. To adjust the reference count, you must load and dereference the pointer itself, but between those two operations another thread might come in, replace the pointer, adjust the original pointer count down and free the pointed object, together with the counter. You need some way to defer destruction till a safe point (RCU, hazard pointers, etc).

what about this

// use-counter in T is an atomic too array< atomic< intrusive_ptr< T > >, 100 > a;

intrusive_ptr< T > p(...); intrusive_ptr_add_ref( p.get() ); // add an intrusive_ptr to the array if ( a[index].compare_exchange_strong(null_ptr,p) ) { // successful added }

// remove an interusive_ptr from array intrusive_ptr< T > e; // points to nothing if ( ! a[index].compare_exchange_strong(e, null_ptr) ) { // successfull removed intrusive_ptr_release( e.get() ); }

That won't work for several reasons. First, as outlined before, you can't store intrusive_ptr in atomic<>. Assuming you store T* instead, then you can't use nullptr as the first argument because CAS accepts it as an lvalue reference. Next, the removal of the pointer is not correct because when CAS fails the pointer is just loaded from the atomic, so you release the pointer and the dangling pointer is left in the array. You have to load e first, then make a loop with CAS and only release if it succeeds and the loaded pointer is not NULL.

On Friday 25 October 2013 14:35:39 Oliver Kowalke wrote:

2013/10/25 Andrey Semashev <andrey.semashev@gmail.com>

...

That won't work for several reasons. First, as outlined before, you can't store intrusive_ptr in atomic<>. Assuming you store T* instead, then you can't use nullptr as the first argument because CAS accepts it as an lvalue reference. Next, the removal of the pointer is not correct because when CAS fails the pointer is just loaded from the atomic, so you release the pointer and the dangling pointer is left in the array. You have to load e first, then make a loop with CAS and only release if it succeeds and the loaded pointer is not NULL.

array< atomic< T * >, 100 > a{ atomic< T* >( 0) };

That's not correct, it should be: array< atomic< T * >, 100 > a; for (auto& p : a) p.store(NULL, memory_order_relaxed);

T * desired = new T(); T * expected = 0; if ( a[index].compare_exchange_strong( expected, desired) ) { // desired added }

T * expected1 = 0; T * expected2 = 0; if ( ! a[index].compare_exchange_strong( expected1, expected2) ) { // expected1 is not NULL, expected1 removed == a[index] contains NULL }

No, that's not right. If compare_exchange_strong returns false, the operation have failed and a[index] != NULL (at least, that's how compare_exchange_strong have left it). It should be: T* expected = a[index].load(memory_order_acquire); while (!a[index].compare_exchange_weak(expected, NULL, memory_order_release, memory_order_acquire)) { } if (expected) // The expected value was removed from the array else // The array element was removed by some other thread

2013/10/25 Andrey Semashev <andrey.semashev@gmail.com>

Actually, it can be much simpler:

T* p = a[index].exchange(NULL); if (expected) // The expected value was removed from the array else // The array element was removed by some other thread

you mean 'if ( p)' ;^)

2013/10/25 Andrey Semashev <andrey.semashev@gmail.com>

...

T * expected1 = 0; T * expected2 = 0; if ( ! a[index].compare_exchange_strong( expected1, expected2) ) { // expected1 is not NULL, expected1 removed == a[index] contains NULL }

No, that's not right. If compare_exchange_strong returns false, the operation have failed and a[index] != NULL (at least, that's how compare_exchange_strong have left it). It should be:

T* expected = a[index].load(memory_order_acquire); while (!a[index].compare_exchange_weak(expected, NULL, memory_order_release, memory_order_acquire)) { }

if (expected) // The expected value was removed from the array else // The array element was removed by some other thread

agreed - but shouldn't we use strong memory-order (I remember that Herb S. recommended to use memory_order_strong in one of its sessions)

Oliver Kowalke wrote:

what about this

// use-counter in T is an atomic too array< atomic< intrusive_ptr< T > >, 100 > a;

intrusive_ptr< T > p(...); intrusive_ptr_add_ref( p.get() ); // add an intrusive_ptr to the array if ( a[index].compare_exchange_strong(null_ptr,p) ) { // successful added }

// remove an interusive_ptr from array intrusive_ptr< T > e; // points to nothing if ( ! a[index].compare_exchange_strong(e, null_ptr) ) { // successfull removed intrusive_ptr_release( e.get() ); }

For this, you don't seem to need atomic<intrusive_ptr> though; atomic<T*> works just as well, doesn't it? array< atomic< T* >, 100 > a; intrusive_ptr< T > p(...); // add an intrusive_ptr to the array intrusive_ptr_add_ref( p.get() ); if ( a[index].compare_exchange_strong(null_ptr,p.get()) ) { // successfully added } else { intrusive_ptr_release(p.get()); // failed to add } // remove an intrusive_ptr from array T* e = 0; if ( ! a[index].compare_exchange_strong(e, null_ptr) ) { // successfully removed intrusive_ptr<T> e2( e, false ); // return e2; }

Oliver Kowalke wrote:

yes, I could use atomic<T*> but the other code tracks T* in intrusive_ptr< T > and it looks a little bit awkward if I release a raw-ponter from a smart-pointer in order to store it in a container.

You're already doing manual addref/release on the pointer in the container, so it's logically treated as a raw pointer. Even if you could store an intrusive_ptr there, its additional addref/release would be wasted. The rest of the code never sees the raw pointer; the functions that store and retrieve from the container take/return intrusive_ptr.

2013/10/25 Giovanni Piero Deretta <gpderetta@gmail.com>

The details of the safety of putting an intrusive_ptr in an atomic are discussed elsethread, I just wanted to remind you here that, unless you rely on exotic deferred reclamation techniques, to safely concurrently update a shared pointer normally you need to manipulate both the pointer itself and the shared count.

This means either a DCAS, transactional memory or a (spin) lock. As the former two are implemented by no or few mainstream architectures, you pretty much need a lock. That's the path taken by boost::shared_ptr for example.

the intention behind my question was an algorithm for work-stealing/sharing using atomic-ops.