Thread: Interlocked increment/decrement

  1. #1
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654

    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  2. #2
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    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
    Last edited by phantomotap; 04-12-2009 at 05:46 AM.

  3. #3
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    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.

    "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
    Last edited by phantomotap; 04-12-2009 at 07:10 AM. Reason: O_o

  5. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    These assembly instructions aren't my area... I can't figure out how to use them!
    Is it
    xadd dst, src?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by matsp View Post
    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.

    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?

    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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 Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Elysia View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    There aren't any such (I check the entire file)... I'll go for 32 and 64 for now.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #12
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    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.)?
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  14. #14
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    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).
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  15. #15
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. thread safety using Interlocked
    By George2 in forum C# Programming
    Replies: 0
    Last Post: 05-16-2008, 03:07 AM
  2. Increment/Decrement operator troubles
    By LineOFire in forum C Programming
    Replies: 6
    Last Post: 11-15-2006, 10:28 PM
  3. increment/decrement operators
    By ZakkWylde969 in forum C++ Programming
    Replies: 10
    Last Post: 07-10-2003, 04:17 PM
  4. Increment/Decrement for loop?
    By --]bthNzA in forum C Programming
    Replies: 11
    Last Post: 12-29-2001, 01:10 AM