Linux 内核的同步机制--原子操作

    一 原子操作

    所谓原子操作，就是该操作绝不会在执行完毕前被任何其他任务或者事件打断，也就所说，它是最小的执行单元，不可能有更小的执行单元，因此这里的原子实际是使用了物理学里面道物质微粒的概念。

    原子操作需要硬件的支持，因此是架构相关的，其api和原子类型道定义都定义在内核源码树的include\asm-x86_64\atomic.h,下面仅仅正对x86-64处理器类型进行举例说明。其由汇编实现，因为C语言并不能实现这样的操作。    

    我们通过分析其具体实现来了解其功能。在进行源码分析之前，可以先了解内联汇编的使用，这样有助于理解源代码。 

    下面对具体代码进行分析：
 

#ifdef CONFIG_SMP
#define LOCK "lock ; "
#else
#define LOCK ""
#endif
CONFIG_SMP 配置选项控制内核是否支持SMP，针对指定机器进行内核裁剪只用。

/*
 * Make sure gcc doesn't try to be clever and move things around
 * on us. We need to use _exactly_ the address the user gave us,
 * not some alias that contains the same information.
 */
typedef struct { volatile int counter; } atomic_t;
定义atomic_t结构，实际上包含一个整形的变量，使用volatile 修饰，告诉gcc不要对该类型的数据进行优化处理，对它的访问都是对内存访问，而不是对寄存器的访问；

#define ATOMIC_INIT(i)    { (i) }
初始化atomic_t

/**
 * atomic_read - read atomic variable
 * @v: pointer of type atomic_t
 *
 * Atomically reads the value of @v.
 */
#define atomic_read(v)        ((v)->counter)
对原子类型的变量进行原子操作，它返回原子类型的变量v的值；

/**
 * atomic_set - set atomic variable
 * @v: pointer of type atomic_t
 * @i: required value
 *
 * Atomically sets the value of @v to @i.
 */
#define atomic_set(v,i)        (((v)->counter) = (i))
设置原子类型的变量v值为i;

/**
 * atomic_add - add integer to atomic variable
 * @i: integer value to add
 * @v: pointer of type atomic_t
 *
 * Atomically adds @i to @v.
 */
static __inline__ void atomic_add(int i, atomic_t *v)
{
    __asm__ __volatile__(
        LOCK "addl %1,%0"
        :"=m" (v->counter)
        :"ir" (i), "m" (v->counter));
}
原子类型的变量v增加值i, addl %1,%0 即实现了此原子的增加，如果了解了内联汇编，理解这段代码就很容易了；

/**
 * atomic_sub - subtract the atomic variable
 * @i: integer value to subtract
 * @v: pointer of type atomic_t
 *
 * Atomically subtracts @i from @v.
 */
static __inline__ void atomic_sub(int i, atomic_t *v)
{
    __asm__ __volatile__(
        LOCK "subl %1,%0"
        :"=m" (v->counter)
        :"ir" (i), "m" (v->counter));
}
原子类型的变量v减去值i；

/**
 * atomic_sub_and_test - subtract value from variable and test result
 * @i: integer value to subtract
 * @v: pointer of type atomic_t
 *
 * Atomically subtracts @i from @v and returns
 * true if the result is zero, or false for all
 * other cases.
 */
static __inline__ int atomic_sub_and_test(int i, atomic_t *v)
{
    unsigned char c;

    __asm__ __volatile__(
        LOCK "subl %2,%0; sete %1"
        :"=m" (v->counter), "=qm" (c)
        :"ir" (i), "m" (v->counter) : "memory");
    return c;
}
该函数从原子类型的变量v中减去i，并判断结果是否为0，如果为0，返回真，否则返回假；

/**

 * atomic_inc - increment atomic variable

 * @v: pointer of type atomic_t

 *

 * Atomically increments @v by 1.

 */

static __inline__ void atomic_inc(atomic_t *v)

{

    __asm__ __volatile__(

        LOCK "incl %0"

        :"=m" (v->counter)

        :"m" (v->counter));

}


原子类型的变量v自增1；

/**
 * atomic_dec - decrement atomic variable
 * @v: pointer of type atomic_t
 *
 * Atomically decrements @v by 1.
 */
static __inline__ void atomic_dec(atomic_t *v)
{
    __asm__ __volatile__(
        LOCK "decl %0"
        :"=m" (v->counter)
        :"m" (v->counter));
}
原子类型的变量v自减1；

/**
 * atomic_dec_and_test - decrement and test
 * @v: pointer of type atomic_t
 *
 * Atomically decrements @v by 1 and
 * returns true if the result is 0, or false for all other
 * cases.
 */
static __inline__ int atomic_dec_and_test(atomic_t *v)
{
    unsigned char c;

    __asm__ __volatile__(
        LOCK "decl %0; sete %1"
        :"=m" (v->counter), "=qm" (c)
        :"m" (v->counter) : "memory");
    return c != 0;
}
对原子类型的变量v原子地减1，并判断结果是否为0，如果为0，返回真，否则返回假；

/**
 * atomic_inc_and_test - increment and test
 * @v: pointer of type atomic_t
 *
 * Atomically increments @v by 1
 * and returns true if the result is zero, or false for all
 * other cases.
 */
static __inline__ int atomic_inc_and_test(atomic_t *v)
{
    unsigned char c;

    __asm__ __volatile__(
        LOCK "incl %0; sete %1"
        :"=m" (v->counter), "=qm" (c)
        :"m" (v->counter) : "memory");
    return c != 0;
}
对原子类型的变量v原子地增加1，并判断结果是否为0，如果为0，返回真，否则返回假；

/**
 * atomic_add_negative - add and test if negative
 * @v: pointer of type atomic_t
 * @i: integer value to add
 *
 * Atomically adds @i to @v and returns true
 * if the result is negative, or false when
 * result is greater than or equal to zero.
 */
static __inline__ int atomic_add_negative(int i, atomic_t *v)
{
    unsigned char c;

    __asm__ __volatile__(
        LOCK "addl %2,%0; sets %1"
        :"=m" (v->counter), "=qm" (c)
        :"ir" (i), "m" (v->counter) : "memory");
    return c;
}
对原子类型的变量v原子地增加I，并判断结果是否为负数，如果是，返回真，否则返回假；

      原子操作通常用于实现资源的引用计数，在编写代码的时候，能使用原子操作的时候，就尽量不要使用复杂的锁机制。对于多数体系结构来说，原子与更复杂的同步方法相比较，给系统带来的开销小，对高速缓存行的影响也小。
 
    除原子整形操作外，内核还提供了一组针对这一级数据进行操作的函数，其定义在include\asm-x86_64\bitops.h中，位操作函数是对普通的内存地址进行操作的。参数为一个指针和一个位号，第0位是给定地址的最低有效位。32位机上，第31位是给定地址的最高有效位，而第32位是下一个字节的最低有效位。

#define ADDR (*(volatile long *) addr)
把addr强制转换为(volatile long ) 类型的指针，即对指针的操作范围是addr开始的4个字节(long 型),暂时记作p,那么就是
#define ADDR *p,即为p指针指向位置的内容。这里可以通过内存寻址访问到寄存器ADDR,可以进行读写操作。
假设内存0xaaaaaaaa是一个寄存器，如果要访问它，可以这样：
#define ADDR (*(volatile long *) 0xaaaaaaaa )
读：tmp = ADDR;
写：ADDR = 0xAABBCCDD;

/**
 * set_bit - Atomically set a bit in memory
 * @nr: the bit to set
 * @addr: the address to start counting from
 *
 * This function is atomic and may not be reordered. See __set_bit()
 * if you do not require the atomic guarantees.
 * Note that @nr may be almost arbitrarily large; this function is not
 * restricted to acting on a single-word quantity.
 */
static __inline__ void set_bit(long nr, volatile void * addr)
{
    __asm__ __volatile__( LOCK_PREFIX
        "btsq %1,%0"
        :"=m" (ADDR)
        :"dIr" (nr) : "memory");
}
bts( bit test and set),bts oprd1, oprd2 : 即位测试并置位,被测试位送CF并且被测试位置1；上面的内联汇编代码即将addr指向的内容第nr位置1；
此为原子操作，而且是不可重新排序的；@nr 可以很大，并非只能是单个word的数量的限制。

/**
 * __set_bit - Set a bit in memory
 * @nr: the bit to set
 * @addr: the address to start counting from
 *
 * Unlike set_bit(), this function is non-atomic and may be reordered.
 * If it's called on the same region of memory simultaneously, the effect
 * may be that only one operation succeeds.
 */
static __inline__ void __set_bit(int nr, volatile void * addr)
{
    __asm__ volatile(
        "btsl %1,%0"
        :"=m" (ADDR)
        :"dIr" (nr) : "memory");
}
非原子位操作函数，与set_bit对应，__set_bit不保证原子性,内核对每个操作都提供了原子位操作数的版本，以及非原子位操作的版本，其操作完全相同，只是后者名字前缀多两个下划线，以下仅对原子位操作进行说明。

/**
 * clear_bit - Clears a bit in memory
 * @nr: Bit to clear
 * @addr: Address to start counting from
 *
 * clear_bit() is atomic and may not be reordered. However, it does
 * not contain a memory barrier, so if it is used for locking purposes,
 * you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
 * in order to ensure changes are visible on other processors.
 */
static __inline__ void clear_bit(int nr, volatile void * addr)
{
    __asm__ __volatile__( LOCK_PREFIX
        "btrl %1,%0"
        :"=m" (ADDR)
        :"dIr" (nr));
}

static __inline__ void __clear_bit(int nr, volatile void * addr)
{
    __asm__ __volatile__(
        "btrl %1,%0"
        :"=m" (ADDR)
        :"dIr" (nr));
}
#define smp_mb__before_clear_bit()    barrier()
#define smp_mb__after_clear_bit()    barrier()

bts( bit test and reset), btr oprd1,oprd2 位测试并复位指令，被测试位送CF并且被测试位清0；上面的内联汇编代码原子地清除addr所指对象的第nr位。它不包含内存屏障（当多个CPU同时访问一块内存，或者CPU和设备同时访问一块内存，为了实现访问的一致性，需要内存屏障），因此只是用于锁，为了确保在其他的进程中可见，你应该先调用 smp_mb__before_clear_bit()， smp_mb__after_clear_bit()；

/**
 * __change_bit - Toggle a bit in memory
 * @nr: the bit to change
 * @addr: the address to start counting from
 *
 * Unlike change_bit(), this function is non-atomic and may be reordered.
 * If it's called on the same region of memory simultaneously, the effect
 * may be that only one operation succeeds.
 */
static __inline__ void __change_bit(int nr, volatile void * addr)
{
    __asm__ __volatile__(
        "btcl %1,%0"
        :"=m" (ADDR)
        :"dIr" (nr));
}

/**
 * change_bit - Toggle a bit in memory
 * @nr: Bit to change
 * @addr: Address to start counting from
 *
 * change_bit() is atomic and may not be reordered.
 * Note that @nr may be almost arbitrarily large; this function is not
 * restricted to acting on a single-word quantity.
 */
static __inline__ void change_bit(int nr, volatile void * addr)
{
    __asm__ __volatile__( LOCK_PREFIX
        "btcl %1,%0"
        :"=m" (ADDR)
        :"dIr" (nr));
}
原子的翻转addr所指对象的第nr位；

/**
 * test_and_set_bit - Set a bit and return its old value
 * @nr: Bit to set
 * @addr: Address to count from
 *
 * This operation is atomic and cannot be reordered.
 * It also implies a memory barrier.
 */
static __inline__ int test_and_set_bit(int nr, volatile void * addr)
{
    int oldbit;

    __asm__ __volatile__( LOCK_PREFIX
        "btsl %2,%1\n\tsbbl %0,%0"
        :"=r" (oldbit),"=m" (ADDR)
        :"dIr" (nr) : "memory");
    return oldbit;
}

/**
 * __test_and_set_bit - Set a bit and return its old value
 * @nr: Bit to set
 * @addr: Address to count from
 *
 * This operation is non-atomic and can be reordered.
 * If two examples of this operation race, one can appear to succeed
 * but actually fail. You must protect multiple accesses with a lock.
 */
static __inline__ int __test_and_set_bit(int nr, volatile void * addr)
{
    int oldbit;

    __asm__(
        "btsl %2,%1\n\tsbbl %0,%0"
        :"=r" (oldbit),"=m" (ADDR)
        :"dIr" (nr));
    return oldbit;
}
原子的设置addr所指对象的第nr位，并返回原先的值；

/**
 * test_and_clear_bit - Clear a bit and return its old value
 * @nr: Bit to clear
 * @addr: Address to count from
 *
 * This operation is atomic and cannot be reordered.
 * It also implies a memory barrier.
 */
static __inline__ int test_and_clear_bit(int nr, volatile void * addr)
{
    int oldbit;

    __asm__ __volatile__( LOCK_PREFIX
        "btrl %2,%1\n\tsbbl %0,%0"
        :"=r" (oldbit),"=m" (ADDR)
        :"dIr" (nr) : "memory");
    return oldbit;
}

/**
 * __test_and_clear_bit - Clear a bit and return its old value
 * @nr: Bit to clear
 * @addr: Address to count from
 *
 * This operation is non-atomic and can be reordered.
 * If two examples of this operation race, one can appear to succeed
 * but actually fail. You must protect multiple accesses with a lock.
 */
static __inline__ int __test_and_clear_bit(int nr, volatile void * addr)
{
    int oldbit;

    __asm__(
        "btrl %2,%1\n\tsbbl %0,%0"
        :"=r" (oldbit),"=m" (ADDR)
        :"dIr" (nr));
    return oldbit;
}
原子的清空addr所指对象的第nr位，并返回原先的值；

/* WARNING: non atomic and it can be */
static __inline__ int __test_and_change_bit(int nr, volatile void * addr)
{
    int oldbit;

    __asm__ __volatile__(
        "btcl %2,%1\n\tsbbl %0,%0"
        :"=r" (oldbit),"=m" (ADDR)
        :"dIr" (nr) : "memory");
    return oldbit;
}

/**
 * test_and_change_bit - Change a bit and return its old value
 * @nr: Bit to change
 * @addr: Address to count from
 *
 * This operation is atomic and cannot be reordered.
 * It also implies a memory barrier.
 */
static __inline__ int test_and_change_bit(int nr, volatile void * addr)
{
    int oldbit;

    __asm__ __volatile__( LOCK_PREFIX
        "btcl %2,%1\n\tsbbl %0,%0"
        :"=r" (oldbit),"=m" (ADDR)
        :"dIr" (nr) : "memory");
    return oldbit;
}
原子的翻转addr所指对象的第nr位，并返回原先的值；

to be continue ......

参考：

   《汇编语言程序设计》

   《linux内核设计实现》

    Linux 内核的同步机制，第 1 ，2部分

    http://www.ibm.com/developerworks/cn/linux/l-synch/part1/

   http://www.ibm.com/developerworks/cn/linux/l-synch/part2/

   linux内存屏障浅析