Linux内核bitmap数据结构拾忆

http://www.blogbus.com/technica-logs/32407481.html
Linux内核中bitmap是一种很常用的结构。
最典型的就是sched.c里面的优先级bitmap: struct prio_array，它提供了atomic和非atomic的两套操作，例如clear_bit是原子操作，而__clear_bit就是非原子操作。区别只是少了一个“LOCK_PREFIX”。
关于lock_prefix，是用于SMP的，
参考：http://blog.csdn.net/flyingcloud_2008/article/details/5833081
展开后是：

.section .smp_locks,"a"
  .align 4
  .long 661f
.previous
661:
        lock

/***********************************

* linux/kernel/sched.c            *
***********************************/
struct prio_array {
    unsigned int nr_active;
    DECLARE_BITMAP(bitmap, MAX_PRIO+1); /* include 1 bit for delimiter */
    struct list_head queue[MAX_PRIO];
};

/***********************************
* linux/include/linux/types.h     *
***********************************/
#define BITS_TO_LONGS(bits) \
        (((bits)+BITS_PER_LONG-1)/BITS_PER_LONG)
#define DECLARE_BITMAP(name,bits) \
        unsigned long name[BITS_TO_LONGS(bits)]

#define BITS_PER_BYTE 8

/***********************************
* linux/include/asm-i386/bitops.h *
***********************************/
/* 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: there are no guarantees that this function will not be reordered
* on non x86 architectures, so if you are writing portable code,
* make sure not to rely on its reordering 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(int nr, volatile unsigned long * addr)
{
    __asm__ __volatile__( LOCK_PREFIX
                "btsl %1,%0"
                :"+m" (ADDR)
                :"Ir" (nr));
}

/**
* 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 unsigned long * addr)
{
        __asm__ __volatile__( LOCK_PREFIX
                "btrl %1,%0"
                :"+m" (ADDR)
                :"Ir" (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 may be reordered on other architectures than x86.
* It also implies a memory barrier.
*/
static inline int test_and_set_bit(int nr, volatile unsigned long * addr)
{
    int oldbit;

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