/* from:

Subject: [linux-audio-dev] Lock-free LIFO used in MidiShare 
From: Yann Orlarey (orlarey_AT_grame.fr) 
Date: Fri Jul 21 2000 - 17:06:15 EEST * 

*/

/*****************************************************************
                           DATA STRUCTURES
 *****************************************************************/

typedef struct cell {
    struct cell* link; /* next cell in the lifo */
    /*...*/ /* any data here */
} cell_t;

typedef struct lifo {
    volatile cell_t* top; /* top of the stack */
    volatile unsigned long cnt; /* used to avoid ABA problem */
} lifo_t;

 

//2) Trivial, non synchronized, implementation
//============================================

//We have to define 3 operations : init(), push() and pop(). The cnt
//field is not used here.

#if 0
void init(lifo* lf){
    lf->top = 0;
}

void push (lifo * lf, cell * cl){
    cl->link = lf->top;
    lf->top = cl;
}

cell* pop (lifo * lf){
    cell_t* v;
    v = lf->top;
    if (v) lf->top = v->link;
    return v;
} 
#endif


/*
4) CMPXCHG and CMPXCHG8B
========================

The lock-free implementation use the CMPXCHG and CMPXCHG8B instructions
on the intel version (and the LWARX and STWCX instructions on PowerPC version).

The semantic of CMPXCHG (compare and exchange) is to update a destination
with a new value provided the destination still contains the old value
that was use to compute the new value).

From Intel SDM volume 2, the exact operations performed by CMPXCHG for
32-bits values are :

IF (EAX = DEST) THEN
        ZF <- 1
        DEST <- SRC
ELSE
        ZF <- 0
        EAX <- DEST
END;

where :
        DEST is the destination to update
        SRC is the source of the new value for DEST
        EAX is the old value of DEST

On an SMP machine, the CMPXCHG should be prefixed with "lock;" to lock the
bus for performing atomic read-modify-write operations on system memory.

The CMPXCHG8B performs the same operations as CMPXCHG but on 64-bits values :

IF (EDX:EAX = DEST) THEN
        ZF <- 1
        DEST <- ECX:EBX
ELSE
        ZF <- 0
        EDX:EAX <- DEST

where :
        DEST is the 64-bits destination to update
        SRC is the source of the new 64-bits value for DEST
        EDX:EAX is the old 64-bits value of DEST

This intruction is used for the pop() operation to avoid the ABA problem
(see later).

*/


#ifdef __SMP__
#define LOCK "lock ; "
#else
#define LOCK ""
#endif

void init(lifo_t *lf){
    lf->top = 0;
    lf->cnt = 0;
}

void push (lifo_t * lf, cell_t *cl)
{
    __asm__ __volatile__ (
	"# LFPUSH \n\t"
	"1:\t"
	"movl %2, (%1) \n"
	LOCK "cmpxchg %1, %0 \n\t"
	"jnz 1b \n\t"
	:
	:"m" (*lf), "r" (cl), "a" (lf->top)
	);
}

cell_t* pop (lifo_t *lf)
{
    cell_t* v=0;
    __asm__ __volatile__ (
	"# LFPOP \n\t"
	"testl %%eax, %%eax \n\t"
	"jz 20f \n"
	"10:\t"
	"movl (%%eax), %%ebx \n\t"
	"movl %%edx, %%ecx \n\t"
	"incl %%ecx \n\t"
	LOCK "cmpxchg8b %1 \n\t"
	"jz 20f \n\t"
	"testl %%eax, %%eax \n\t"
	"jnz 10b \n"
	"20:\t"
	:"=a" (v)
	:"m" (*lf), "a" (lf->top), "d" (lf->cnt)
	:"ecx", "ebx" );
    return v;
} 



main(){
    lifo_t lf;
    cell_t c1, c2, c3;
    init(&lf);
    push(&lf, &c1);
    push(&lf, &c2);
    push(&lf, &c3);

    printf("%p\n", pop(&lf));
    printf("%p\n", pop(&lf));
    printf("%p\n", pop(&lf));
    printf("%p\n", pop(&lf));
    printf("%p\n", pop(&lf));
    printf("%p\n", pop(&lf));
    
    
}