单生产者单消费者模式的无锁队列实现

#ifndef FIFO_H
#define FIFO_H

struct FIFO
{
    void **buffer;
    unsigned int size;
    unsigned int in;
    unsigned int out;
};

struct FIFO *FIFO_alloc(unsigned int size);

unsigned int FIFO_put(struct FIFO *FIFO,  void** obj_table, unsigned int n);

unsigned int FIFO_get(struct FIFO *FIFO, void** obj_table, unsigned int len);

#endif // FIFO_H

#include "fifo.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define min(a, b) ((a) > (b))?(b):(a)
#define max(a, b) ((a) > (b))?(a):(b)

#ifdef CONFIG_X86_32
/*指令“lock; addl $0,0(%%esp)”表示加锁，把0加到栈顶的内存单元，该指令操作本身无意义，但这些指令起到内存屏障的作用，让前面的指令执行完成。具有XMM2特征的CPU已有内存屏障指令，就直接使用该指令*/
#define mb() alternative("lock; addl $0,0(%%esp)", "mfence", X86_FEATURE_XMM2)
#define rmb() alternative("lock; addl $0,0(%%esp)", "lfence", X86_FEATURE_XMM2)
#define wmb() alternative("lock; addl $0,0(%%esp)", "sfence", X86_FEATURE_XMM)
#else
#define mb() asm volatile("mfence":::"memory")
#define rmb() asm volatile("lfence":::"memory")
#define wmb() asm volatile("sfence" ::: "memory")
#endif

static inline int fls(int x)
{
    int r;


    __asm__("bsrl %1,%0
	"
            "jnz 1f
	"
            "movl $-1,%0
"
            "1:" : "=r" (r) : "rm" (x));
    return r+1;
}

static inline unsigned int roundup_pow_of_two(unsigned int x)
{
    return 1UL << fls(x - 1);
}

struct FIFO *FIFO_alloc(unsigned int size)
{
    struct FIFO *ret = (struct FIFO*)malloc(sizeof(struct FIFO));

    if (size & (size - 1))
    {
        size = roundup_pow_of_two(size);
    }

    ret->buffer = (void**)malloc(size*sizeof(void*));
    ret->size = size;

    if (!ret->buffer)
    {
        return NULL;
    }

    memset(ret->buffer, 0, size*sizeof(void*));
    ret->in  = 0 ;
    ret->out = 0;

    return ret;
}

unsigned int FIFO_put(struct FIFO *FIFO,  void** obj_table, unsigned int n)
{
    unsigned int l;
    unsigned int len;
    unsigned int i, nCount, nIndex;

    len = min(n, FIFO->size - FIFO->in + FIFO->out);
    mb();

    l = min(len, FIFO->size - (FIFO->in & (FIFO->size - 1)));
    nCount = l;

    nIndex = FIFO->in & (FIFO->size - 1);
    for(i=0; i<nCount; i++)
    {
        FIFO->buffer[nIndex + i] = obj_table[i];
    }

    nCount = len-l;
    for(i=0; i<nCount; i++)
    {
        FIFO->buffer[i] = obj_table[l+ i];
    }

    wmb();

    FIFO->in += len;

    return len;
}

unsigned int FIFO_get(struct FIFO *FIFO, void** obj_table, unsigned int len)
{
    unsigned int l;
    unsigned int nCount, nIndex;
    unsigned int i;

    len = min(len, FIFO->in - FIFO->out);

    rmb();

    l = min(len, FIFO->size - (FIFO->out & (FIFO->size - 1)));


    nCount = l;
    nIndex = FIFO->out & (FIFO->size - 1);
    for(i=0; i<nCount; i++)
    {
        obj_table[i] = FIFO->buffer[nIndex + i];
    }

    nIndex = nCount;
    nCount = len - l;
    for(i=0; i<nCount; i++)
    {
        obj_table[nIndex + i] = FIFO->buffer[i];
    }

    mb();

    FIFO->out += len;

    return len;
}