Thread: Atomic compare and swap.

  1. #1
    Registered User Maz's Avatar
    Join Date
    Nov 2005
    Location
    Finland
    Posts
    194

    Atomic compare and swap.

    Hi dee Ho peeps!

    I was pondering how to implement atomic compare and swap (for ix86 at starters) in such a way that return value would tell what the value was pefore instruction was executed. I could write:

    Code:
    int __inline__ atomicCAS( volatile unsigned int *ptr, int cmp, int new)
    {
    
        unsigned char ret;
        unsigned int original = *ptr;
    
        __asm__ __volatile__ (
        " lock\n"
        " cmpxchgl %2,%1\n"
        " sete %0\n"
        : "=q" (ret), "=m" (*ptr)
        : "r" (new), "m" (*ptr), "a" (cmp)
        : "memory");
    
        return original;
    
    }
    But now, in case the *ptr == cmp when value of original is set, there's possibility that something changes the value before we call the asm code.

    => return value would indicate that swap occurred, but in reality it did not.

    My asm skills are *limited*, and I cannot bend my mind around this problem. I of course could just do:

    Code:
    int __inline__ atomicCAS( volatile unsigned int *ptr, int cmp, int new)
    {
    
        unsigned char ret;
    
        __asm__ __volatile__ (
        " lock\n"
        " cmpxchgl %2,%1\n"
        " sete %0\n"
        : "=q" (ret), "=m" (*ptr)
        : "r" (new), "m" (*ptr), "a" (cmp)
        : "memory");
    
        return (int) ret;
    
    }
    where return value just says whether the swap took place, but it would be handy at times to be able to tell what the swapped out value was.

    Any ideas?

    (I have been googling, and read that this kind of function returning original memory contents is usual way to do CAS, so I assume there is a way).

  2. #2
    Registered User Maz's Avatar
    Join Date
    Nov 2005
    Location
    Finland
    Posts
    194
    Just to inform interested persons:
    Problem solved.

    cmpxchgw instruction updates the cmp value to value read from memory - if the swap does not occur. On the other hand, if swap does occur, cmp is already the same value as calue read from memory. Hence we can just return cmp.

  3. #3
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    >> My asm skills are *limited*
    Same here.

    There are a few lock-free/wait-free libraries out there whose source code you can dig through to see how they did their atomic ops.
    AppCore
    atomic-ptr-plus project
    atomic_ops library in qprof project
    Noble
    lock-free-lib

    Lots of cool stuff to look at if you're masochistic like me and enjoy researching/implementing/testing lock-free and wait-free algorithms.

    gg

  4. #4
    Registered User Maz's Avatar
    Join Date
    Nov 2005
    Location
    Finland
    Posts
    194
    Thanks mate.

    Although I assume that after I have succeeded in writing the CAS for the target architectures I need, I will stay out of the asm. (I can create rest of the atomic ops I need using CAS )

    Or actually... I may well try to do something else with inline asm. It is not easy for me, so I take that as a challenge... So perhaps after 50 years I'll be presenting text adventure game written in inline asm (If someone can find a x86 from some cabin )

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Polynomials and ADT's
    By Emeighty in forum C++ Programming
    Replies: 20
    Last Post: 08-19-2008, 08:32 AM
  2. How to write my own qsort routine
    By tonbarius in forum C Programming
    Replies: 3
    Last Post: 05-14-2006, 12:34 PM
  3. swap function
    By SpEkTrE in forum C Programming
    Replies: 8
    Last Post: 02-18-2005, 01:38 PM
  4. a little help with bubble sort
    By cman in forum C Programming
    Replies: 3
    Last Post: 02-06-2003, 03:45 AM