atomic pointer types...

[Chris M. Thomasson]

I am not sure why atomic_is_lock_free is returning false for a pointer type, and true for an uintptr_t.

Try running this program:
____________________
#include <stdio.h>
#include <stdint.h>
#include <stdatomic.h>


int main(void)
{
    _Atomic void* ptr = NULL;

    printf("atomic_is_lock_free(void*):%s\n",
           atomic_is_lock_free(&ptr) ? "true" : "false");

    _Atomic uintptr_t uptr = 0;

    printf("atomic_is_lock_free(uintptr_t):%s\n",
           atomic_is_lock_free(&uptr) ? "true" : "false");

    return 0;
}
____________________

I get:

atomic_is_lock_free(void*):(false)
atomic_is_lock_free(uintptr_t):(true)

The void pointer should be atomic wrt the _Atomic keyword. I must be missing something here.

Do I need to cast the pointers to and from uintptr_t?

Thanks.

[frankie]

Well, the first point is the declaration of the void pointer that is wrong.
It should not be:

Code: [Select]

_Atomic void* ptr = NULL;But

Code: [Select]

void * _Atomic  ptr = NULL;The last one will give you the correct response.
Remember that the definitions in C must be read from left to right, in the second case we have that ptr is an atomic variable that holds a pointer to void.

In PellesC atomic_is_lock_free() is a macro defined as:

Code: [Select]

/*
 * atomic_is_lock_free generic function
 */
#define atomic_is_lock_free(X)  (_Bool)(_Generic(*X, \
    _Bool              : 1, \
    char               : 1, \
    char signed        : 1, \
    char unsigned      : 1, \
    short              : 1, \
    short unsigned     : 1, \
    int                : 1, \
    int unsigned       : 1, \
    long               : 1, \
    long unsigned      : 1, \
    long long          : 1, \
    long long unsigned : 1, \
    char16_t           : 1, \
    char32_t           : 1, \
    wchar_t            : 1, \
    void*              : 1, \
    default            : 0))
Substantially any base type which have a size accessible using a locking processor instruction is free from interlock. All others are not.
Your original declaration stated that ptr was a common pointer to void, the last eventually atomic, defaulting to false.

You would eventually test:

Code: [Select]

int main(void)
{
    void * _Atomic  ptr = NULL;

    printf("atomic_is_lock_free(void*):%s\n",
atomic_is_lock_free(&ptr) ? "true" : "false");

    _Atomic uintptr_t uptr = 0;

    printf("atomic_is_lock_free(uintptr_t):%s\n",
atomic_is_lock_free(&uptr) ? "true" : "false");

    _Atomic struct atom{int a; int b;};    //Make compiler happy and break declaration. See note below
    struct atom AtomStruct = {0};

    printf("atomic_is_lock_free(structure):%s\n",
atomic_is_lock_free(&AtomStruct) ? "true" : "false");

    return 0;
}

Note: Just discovered that the generic atomic_store() function doesn't like nameless structures as in:

Code: [Select]

_Atomic struct {int a; int b;} AtomStruct = {0};And this maybe is a bug... 

[TimoVJL]

from http://en.cppreference.com/w/c/language/atomic

According it, this works too: _Atomic(void*) ptr = NULL;

[frankie]

from http://en.cppreference.com/w/c/language/atomic

According it, this works too: _Atomic(void*) ptr = NULL;

Sure, from ISO/IEC 9899:2011:

6.7 Declarations
Syntax
declaration:
declaration-specifiers init-declarator-listopt ;
_Atomic ( type-name ) init-declarator-list ;
static_assert-declaration

[Chris M. Thomasson]

Ahhh! Thank you for the correction. I am getting true on two out of three, I used your struct atom example:

Code: [Select]

#include <stdio.h>
#include <stdint.h>
#include <stdatomic.h>

int main(void)
{
    void* _Atomic ptr = NULL;

    printf("atomic_is_lock_free(void*):%s\n",
           atomic_is_lock_free(&ptr) ? "true" : "false");

    uintptr_t _Atomic uptr = 0;

    printf("atomic_is_lock_free(uintptr_t):%s\n",
           atomic_is_lock_free(&uptr) ? "true" : "false");

    _Atomic struct atom {int a; int b;};    //Make compiler happy and break declaration. See note below
    struct atom AtomStruct = {0};

    printf("atomic_is_lock_free(structure):%s\n",
atomic_is_lock_free(&AtomStruct) ? "true" : "false");

    return 0;
}

The output is:

Code: [Select]

atomic_is_lock_free(void*):true
atomic_is_lock_free(uintptr_t):true
atomic_is_lock_free(structure):false

On x86 the atom structure can be implemented with cmpxchg8b.

Still not sure why I am getting false for atomic_is_lock_free(&AtomStruct).

Well, at least the void pointer is atomic now. Thank you for the feedback. :^)

Fwiw, I need something like structure to be at least lock free:

Code: [Select]

struct ct_dwcas
{
   intptr_t count;
   void* node;
};

Want to build my simple proxy collector using this compiler. Here is a link to working C++11 code:

https://groups.google.com/d/topic/comp.lang.c++/B9Phyf-6N00/discussion

There is a way to hack it, using a proxy algo of mine that does not need double width compare-and-swap (DWCAS).

https://groups.google.com/d/msg/lock-free/X3fuuXknQF0/0VF_u-7shrsJ

[frankie]

Ahhh! Thank you for the correction. I am getting true on two out of three ...
The output is:

Code: [Select]

atomic_is_lock_free(void*):true
atomic_is_lock_free(uintptr_t):true
atomic_is_lock_free(structure):false

On x86 the atom structure can be implemented with cmpxchg8b.

Still not sure why I am getting false for atomic_is_lock_free(&AtomStruct).

The atomic qualifier is supposed to assure that operations on the object are made atomically, substantially the whole object is modified or acquired integrally without contamination from concurrent accesses. This basically means that whatever object having correspondence with a processor atomic instruction is intrinsically atomic.
A structure is by default larger of CPU atomic instructions, then is intrinsically not free from lock. And this is the correct answer you get.
Anyway changing a member of the structure, that is one of the intrinsically atomic instructions of the CPU, will be executed in standard way. I.e. The following:

Code: [Select]

atomic_store(&AtomStruct.a, 1);Will be in X86-32bits:

Code: [Select]

  mov  eax,1
  xchg  dword ptr [AtomStruct],eax
I hope to have been clear.

[Chris M. Thomasson]

Ahhh! Thank you for the correction. I am getting true on two out of three ...
The output is:

Code: [Select]

atomic_is_lock_free(void*):true
atomic_is_lock_free(uintptr_t):true
atomic_is_lock_free(structure):false

On x86 the atom structure can be implemented with cmpxchg8b.

Still not sure why I am getting false for atomic_is_lock_free(&AtomStruct).

The atomic qualifier is supposed to assure that operations on the object are made atomically, substantially the whole object is modified or acquired integrally without contamination from concurrent accesses. This basically means that whatever object having correspondence with a processor atomic instruction is intrinsically atomic.
A structure is by default larger of CPU atomic instructions, then is intrinsically not free from lock. And this is the correct answer you get.
Anyway changing a member of the structure, that is one of the intrinsically atomic instructions of the CPU, will be executed in standard way. I.e. The following:

Code: [Select]

atomic_store(&AtomStruct.a, 1);Will be in X86-32bits:

Code: [Select]

  mov  eax,1
  xchg  dword ptr [AtomStruct],eax
I hope to have been clear.

Wrt to my DWCAS proxy collector, I need a pointer and an intptr_t to be at least lock-free.

Code: [Select]

struct ct_proxy_dwcas
{
    struct ct_proxy_node* node;
    intptr_t count;
};

We can do this in 32-bit systems with cmpxchg8b. We can do this in 64-bit systems with cmpxchg16b.

https://www.felixcloutier.com/x86/CMPXCHG8B:CMPXCHG16B.html

We can do this in IBM wrt the Principals of Operation for a lock-free stack and ABA counter:

http://publibfp.dhe.ibm.com/epubs/pdf/dz9zr009.pdf

Take a look at Appendix A-50 Free Pool Manipulation.

Also, what about, 32-bit x86:

Code: [Select]


AC_SYS_APIEXPORT
int AC_CDECL
np_ac_i686_atomic_dwcas_fence
( void*,
  void*,
  const void* );


np_ac_i686_atomic_dwcas_fence PROC
  push esi
  push ebx
  mov esi, [esp + 16]
  mov eax, [esi]
  mov edx, [esi + 4]
  mov esi, [esp + 20]
  mov ebx, [esi]
  mov ecx, [esi + 4]
  mov esi, [esp + 12]
  lock cmpxchg8b qword ptr [esi]
  jne np_ac_i686_atomic_dwcas_fence_fail
  xor eax, eax
  pop ebx
  pop esi
  ret

np_ac_i686_atomic_dwcas_fence_fail:
  mov esi, [esp + 16]
  mov [esi + 0],  eax;
  mov [esi + 4],  edx;
  mov eax, 1
  pop ebx
  pop esi
  ret
np_ac_i686_atomic_dwcas_fence ENDP

Double Width Compare and Swap (DWCAS) should be on C11 and C++11 when the architecture supports it.

I know that C++11 totally supports lock-free DWCAS on architectures that provide it, works like a charm. Read:

https://groups.google.com/forum/#!original/lock-free/X3fuuXknQF0/Ho0H1iJgmrQJ

Why is atomic_is_lock_free wrt a pointer to a double width structure giving me false, when it totally works lock-free on the architecture itself?

[frankie]

Chris sorry for the delay in answer.
It is very clear that atomic access to large memory areas nowadays can be efficiently performed on the majority of available architectures.
The PellesC compiler seems to handle only a minor subset of them, only basic data types and the void pointer. This kind of implementation doesn't need to analyze the object, and its size, to define if it can be implemented in a lock-free fashion.
Such approach keep things simple maybe as first implementation.
I can't say if in a future release there will be in-compiler support for lock-free atomic structures, only Pelle can decide.

[Chris M. Thomasson]

Chris sorry for the delay in answer.
It is very clear that atomic access to large memory areas nowadays can be efficiently performed on the majority of available architectures.
The PellesC compiler seems to handle only a minor subset of them, only basic data types and the void pointer. This kind of implementation doesn't need to analyze the object, and its size, to define if it can be implemented in a lock-free fashion.
Such approach keep things simple maybe as first implementation.
I can't say if in a future release there will be in-compiler support for lock-free atomic structures, only Pelle can decide.

Great for a first implementation! I am crossing my fingers that a future release will allow atomic POD structures that contain data such that the size of the said structure equals the size of two pointers. That ability alone allows for a much richer realm of algorithms to be implemented...

Thank you.