is pointer assignment always atomic?

Is pointer assignment always atomic?

Will this always work:


struct list {
  int n;
  struct list* next;
};

struct stack {
  struct list* top;
};

thread one does:
for(;;) {
  print_list(stack->top);
  // read after write race condition for stack->top.
}

thread two does:
for(int count = 0; true; count++) {
  stack->top = new_int_list(count, stack->top);
}

Will the assignments and reads to stack->top always be atomic? Will the pointer value ever be half written or something, on some architecture?

thread one does:

What kind of fresh pseudo-code hell is this?

Mutable memory
Concurrency

Bad idea. Erlang got it right.

>>1
If each thread gets its own core, you might have to worry about cache coherency. It depends what you're actually doing. I don't think anyone would actually write code like this.

Anyway you should find a lock/mutex API if you want to do thread stuff in C.

>>4
Shit on my dick.

>>3
Linux got it right

OP, I'm fucking uneducated piece of shit. But at school they told me that reading/writing integers on x86 is atomic.

>>7
Only if you use XCHG or the LOCK prefix.

>>2

Imagine that the program reaches a state where there are two threads running, one which is constantly beginning iteration on a linked list stack, and one which is constantly pushing nodes onto the stack, but never modifying anything within the list, just pushing onto the top and modifying the list stack's top pointer.

If there were two threads both trying to push a node onto the same list, there would be some weird issues there, because the push operation is actually two things:


1. Get the current top of the list.
2. Construct a new node whose next is the current top.
3. Set the top to the new node.

Steps 1 and 3 will get strange if two threads both try to push onto the list at the same time.

But when there is only one writer and potentially many readers, I think it would be ok. The read operation can be thought of as:

1. Get the current top of the list.

As long as step 3 of the write process and step 1 of the read process are both atomic, I would think that it would work. The reader will either get the node that was the top before the writer's push, or after the writer's push. In either case, the reader will get something reasonable.

What would be bad is if the reading and writing of a pointer value took multiple instructions. So say the writer writes only half of the pointer value, the reader reads everything, and then the writer writes the rest of the address value. Then the reader will get a garbage value, where the first half of the address is the new top node, and the rest of the address is for the previous top node, and the pointer wont be valid. Maybe an 8 bit microcontroller would be like this? Maybe it could have 16 bit addresses and reading and writing an address would take a separate read or write for the lower and upper 8 bits?

>>1
>Is pointer assignment always atomic?

If you are talking C/C++, it depends on the machine. On an eight bit micro, likely not. 8bit operations, 16 bit pointers...

If I remember correctly operations on 32-bit values are always atomic on x86, and operations on 64-bit are always atomic on x64. I'm probably wrong though.

As long as step 3 of the write process and step 1 of the read process are both atomic, I would think that it would work.
Memory barriers. Not even on x86 is a one CPU guaranteed to see writes in the order issued by another CPU.

Every OS has built-in primitives for these things. Use them, because getting them right is harder than you think.

>>12
This. Use the OS primitives or assembly.

>>13
Ok.

Use these instead of OS bloat.
http://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Atomic-Builtins.html

They're supported by gcc, clang, icc and whatever other irrelevant compilers that support GNU-C.

>>15
thanks for the link. very useful.

>>8
Individual MOV instructions on aligned dwords/words/bytes are atomic.

>>15
>>16
The thing to be aware of with those is that if the target platform doesn't directly support one of those operations they may be implemented using a full mutex, which is kind of a bad if the goal is to write lockless code.

>>18
If the target platform doesn't support atomic assignment of pointers, how else are you going to do it?

>>19
Spinlocks for instance, which is what you'd want for your lockless algorithms.

>>18,20
It's still better than the OS bullshit they were talking about, and how do you know the mutex isn't implemented with a spinlock?

>>21
Sometimes it is. On MacOS, for example.

>>21
How do you know that it is?

>>15
I'd ask you to explain how they're "OS bloat" but that would be like asking a dog to explain the theory of general relativity.

>>20
A spinlock is a lock (as the name implies) and subsequently a mutex.

>>18
true. It would probably be better to have explicit lock free data structure implementations for each supported platform (the differences probably wouldn't be very severe) and then provide a mutex using data structure, which could possibly use a very different approach than the lock free ones.

>>23
I looked at the source of GCC.

>>24
If you had any fucking clue what you were talking about you would realize why you shouldn't even touch the OS when you need to rapidly and atomically alter a pointer value.

>>26
On unsupported platforms it would implicitly be a mutex structure, and the most efficient possible mutex structure as well.

>>27
Please do elucidate on the performance difference between InterlockedExchangePointer and say __sync_val_compare_and_swap or __sync_lock_test_and_set (let's pretend it works as described by Intel).

>>28
Are you fucking confused you stupid piece of shit retard?
InterlockedExchangePointer doesn't even touch the OS at runtime, it is typically implemented with a single instruction or a spinlock just like the __sync_* functions. Do you seriously believe that because it's a Windows only function it needs to be implemented with some stupid slow ass syscall or something, are you seriously this fucking dumb?

>>29
That was _your_ claim.

>>30
No it wasn't, I claimed that it was unnecessarily slow to make calls to the OS at runtime when you're trying to alter a pointer value atomically in an intensive manner.

>>33
nice dubs bro

>>32
Thanks

>>31
No, for some reason you thought the locking functions provided by your OS were slow, when they can be implemented in *exactly* the same way as the compiler built-ins depending on their functionality.

>>34
You're still confused, probably because you're so fucking dumb.
I never said that, keep lying you fucking retard.

>>34
It's really a very different thing. An OS can implement a mutex with a handle and a linked list of processes that are stalled on the mutex. When the process that is holding the mutex releases it, the OS can then wake up the process at the front of the list and remove it from the queue. Then the manager that dispatches the processes will give the woken up process some time to execute, between all the other running processes.

A mutex could be implemented simply as a spin lock. And the process manager could be unaware of any mutex, and instead give every process some time to execute, even if they are just spinning on a spin lock. But this would be inefficient. Consider 100 processes all locked on the same mutex. A good portion of the CPU time will be spent letting these processes spin on this lock. Whereas with the queue of stalled processes approach, no CPU time is needed for the stalled processes. There is the overhead of managing the queue, but it can be better than the spinning.

>>36
Linked List
Linked is shit.

>>37
I guess a reallocatable ring buffer would be better.