Interlocked increment/decrement

OK, this is a tough one. It might be spread across several boards, too, so I'll just post it here, so moderators can move it if they think it necessary.

Anyway, the question is atomic increment and decrement operations.
Windows provides two such functions for signed 32-bit values, which obviously is less than ideal since I want to use 8 to 64 bits and unsigned, as well.
The other option is to use VS specific memory barriers to carry out atomic operations, but then it would be locked to the VS compiler.

What way should I take? Any other solutions?
I'm merely looking for a way to increment and decrement a value in a thread-safe manner.

I'm fairly certain you could use the "x86" `xadd' to increment/decrement 8, 16, and 32 bit values atomically. I'm also fairly certain that you can't magically combine other atomic or locking primitives, to fake atomic 64 bit operations. (Mostly because I'm fairly certain an atomic operation always takes a known number of ticks wheres a `mutex' and the like may very well be random.)

What are you trying to do? The "compare and exchange" operations tend to be much more useful and there you have `cmpxchg8b' on a handful of processors. (Edit: As far as it goes, you can use `cmpxchg8b' to get an atomic increment, decrement, or fail of a 64 bit value.)

If you are going for a lock-free data structure... beware! They are notoriously difficult to get right.

Soma

Lock-free smart pointer to increase the ref count is what I'm trying to do.
The ref count can be 8, 16, 32 or 64 bits. Or that was the intention anyway.
I know VS has a 64-bit interlocked increment, too, so it isn't impossible.

O_o

I suppose a lock-free smart pointer is a lock-free data structure after a fashion.

Anyway, drop the 8, 16, and 64 bit versions. You would need at least 32 gigabytes of memory for a reference count above 32 bits. The 8 and 16 bit versions will not save an appreciable amount of memory memory--at most 3 bytes per referenced object--and maybe nothing at all considering padding.

"I know VS has a 64-bit interlocked increment, too, so it isn't impossible."

Yes... I did say: "As far as it goes, you can use `cmpxchg8b' to get an atomic increment, decrement, or fail of a 64 bit value.". You could certainly use `cmpxchg8b' in a loop--repeating on failure--to implement such a function easily enough.

Quote:

---

"You could certainly use `cmpxchg8b' in a loop--repeating on failure--to implement such a function easily enough."

---

O_o

"easily enough"

O_O

Did I say that out loud? ^_^;

Soma

These assembly instructions aren't my area... I can't figure out how to use them!
Is it
xadd dst, src?

Are you sure that it's meaningful to have more than 2^31 references to a pointer?

That being said, Interlocked Increment/Decrement [at least up to machine words] can easily be written in assembler:

Code:

---

__asm
{
  mov ecx, offset target
  mov eax, 1
  lock xadd [ecx], eax
  inc eax    // eax contains old value, so add 1.
}

---

Also, while the prototype in winbase.h may say that the value is "signed", there is no difference between signed and unsigned when it comes to adding/subtracting.

However, it looks like there are 8, 16, 32 and 64 bit versions of the InterlockedXXX instructions if you look at winbase.h.

--
Mats

Quote:

---

Quote:

---

Originally Posted by matsp

Are you sure that it's meaningful to have more than 2^31 references to a pointer?

---

*shrug* Don't know, but better safe than sorry, no?
Plus if there are 8, 16 and 32, why not 64?

That being said, Interlocked Increment/Decrement [at least up to machine words] can easily be written in assembler:

Code:

---

__asm
{
  mov ecx, offset target
  mov eax, 1
  lock xadd [ecx], eax
  inc eax    // eax contains old value, so add 1.
}

---

---

How does this work, exactly?
I don't understand the

mov eax, 1
lock xadd [ecx], eax
inc eax // eax contains old value, so add 1.

bit.

Quote:

---

Also, while the prototype in winbase.h may say that the value is "signed", there is no difference between signed and unsigned when it comes to adding/subtracting.

---

What if the value is > 0x7FFFFFFF? Then signed add would do overflow, no?

Quote:

---

However, it looks like there are 8, 16, 32 and 64 bit versions of the InterlockedXXX instructions if you look at winbase.h.

---

Yeah, I had a look (why doesn't msn mention the 64-bit ones?), but there are only for 32-bit and 64-bit... and of course, they're signed.

Around line 2383 in winbase.h (note that depending on which version of Windows you are using, this may not be what is actually happening in your system - but there is one like it for all recent versions of Windows - look it up in MSDN for compatibility/availability):

Code:

---

FORCEINLINE
LONGLONG
InterlockedIncrement64 (
    __inout LONGLONG volatile *Addend
    )
{
    LONGLONG Old;

    do {
        Old = *Addend;
    } while (InterlockedCompareExchange64(Addend,
                                          Old + 1,
                                          Old) != Old);

    return Old + 1;
}

---

Adding one to 7FFFFFFF gives 80000000 - as long as you use an unsigned type when comparing the value, it is a valid positive number. The processor has only one type of add, subtract instructions - they are both signed and unsigned. The only time when the signed vs. unsigned matters is when performning comparisons - you may need to have a cast somewhere to convert from unsigned to signed and back again, but it's perfectly valid to do that [I'm sure the C standard may object, but are you actually plannning to run this on very obscure machines [which won't have "InterlockedIncrement64" anyways], or are you happy to run on x86, ARM, MIPS, 29K, 68K, Alpha, Sparc and most other commonly available processors?].

--
Mats

Oh yes, due some obscurity, 0x80000000 is the largest negative number available, right? That means that math instructions would work regardless of signedness... Good to know.
That solves the problems for 32-bit and 64-bit instructions, but what about 16 and 8 bits?
x86 only is enough for me (it's the only platform Windows runs on anyway... well, desktops anyway).

Quote:

---

Originally Posted by Elysia

Oh yes, due some obscurity, 0x80000000 is the largest negative number available, right? That means that math instructions would work regardless of signedness... Good to know.
That solves the problems for 32-bit and 64-bit instructions, but what about 16 and 8 bits?
x86 only is enough for me (it's the only platform Windows runs on anyway... well, desktops anyway).

---

I didn't specifically look for InterlockedIncrement8 or 16, but I'm fairly sure they exist (and I just closes Visual Studio). I would however consider that Phantomotap's advice and ignore any reference counter smaller than 32. It is VERY unlikely that there is ANY benefit in supporting that at all.

--
Mats

There aren't any such (I check the entire file)... I'll go for 32 and 64 for now.

I'm fairly new to the term "atomic". Does wikipedia have the general idea correct?
Atomic operation - Wikipedia, the free encyclopedia

This sounds similar to the concept of a "transaction" in database system. Am I correct in thinking that atomic operations would really only be useful when you have multiple threads/processes accessing the same data (similar to locks/mutex/etc.)?

Yes, it's very much like transaction in database, and you do need atomic operations to implement many forms of interprocess communication. The typical case is race-conditions where one process reads the mutes, sees it "free" and decides to "get" the mutex. The other process, at the same time, reads the it, and also sees it "free" and decides to get the mutex. If there is no deterministic, atomic way to ensure that ONE BUT NOT THE OTHER of these process, then you can not make a multiprocessor OS.

--
Mats

Thanks!

I had taken an operating systems course in school, but we had never discussed "atomic operations" -- most of the class was theory and no actual practice of implementing parts of an OS (other than a shell).

There was absolutely zero practice in my operating systems course at the university, but a very, very thorough discussion about synchronization primitives.

I think Windows doesn't provide the 8- and 16-bit atomics because some platforms that MS has targeted in the past, targets now, or possibly wants to target in the future don't support sub-word reading. Windows NT for the Alpha, for example. The Alpha cannot read or write less than a machine word - 64 bits - so a simple update of a 32-bit memory value cannot be a single atomic instruction.
There's also simply no point in doing atomics on values smaller than 32 bits. Alignment requirements, cache coherency requirements - sub-32 accesses will very rarely safe space, and can easily hurt performance.

Quote:

---

Originally Posted by Elysia

Lock-free smart pointer to increase the ref count is what I'm trying to do.
The ref count can be 8, 16, 32 or 64 bits. Or that was the intention anyway.
I know VS has a 64-bit interlocked increment, too, so it isn't impossible.

---

You're either decades ahead of your time, or insane. 32 bits for a ref count should be enough for the next 20 years or so.

I like being mad :)

Quote:

---

Originally Posted by matsp

Are you sure that it's meaningful to have more than 2^31 references to a pointer?

---

Leaving aside design considerations, it's flat-out impossible. Under 32-bit addressing, you only have 4 gigabytes of RAM anyway. If the reference count was actually equal to 2^32-1, that would imply an equal number of references to an object, and since any such reference will be at least as large as a pointer, this would require 16 gigabytes to represent. But we don't have 16 gigabytes, as we already said we are using 32-bit addressing. Contradiction. QED.