[PD-cvs] pd/src m_fifo.c,1.1.2.10,1.1.2.11
Tim Blechmann
timblech at users.sourceforge.net
Wed May 4 19:14:36 CEST 2005
Update of /cvsroot/pure-data/pd/src
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv21091
Modified Files:
Tag: devel_0_38
m_fifo.c
Log Message:
Grame's beautiful implementation of lock-free fifos
Index: m_fifo.c
===================================================================
RCS file: /cvsroot/pure-data/pd/src/Attic/m_fifo.c,v
retrieving revision 1.1.2.10
retrieving revision 1.1.2.11
diff -C2 -d -r1.1.2.10 -r1.1.2.11
*** m_fifo.c 22 Jan 2005 20:28:22 -0000 1.1.2.10
--- m_fifo.c 4 May 2005 17:14:34 -0000 1.1.2.11
***************
*** 1,3 ****
! /* Copyright (c) 2004, Tim Blechmann
* supported by vibrez.net
* For information on usage and redistribution, and for a DISCLAIMER OF ALL
--- 1,3 ----
! ./* Copyright (c) 2004, Tim Blechmann
* supported by vibrez.net
* For information on usage and redistribution, and for a DISCLAIMER OF ALL
***************
*** 10,248 ****
#include "m_fifo.h"
! typedef struct _fifocell
! {
! void* data; /* pointer to our data */
! struct _fifocell* next;
! } t_fifocell;
!
! #ifndef __POWERPC__
! #define LOCKFREE
! #endif
!
! #ifdef LOCKFREE
!
! /* lock-free fifo implementation adapted from:
! * Dominique Fober, Yann Orlarey, Stephane Letz
! * Lock-Free Techniques for Concurrent Access to Shared Objects
! */
!
! #if defined(__GNUC__) && (defined(_X86_) || defined(__i386__) || defined(__i586__) || defined(__i686__))
!
! /* gcc on i386 */
!
! #define CAS(mem, old, new) \
! ({ int ret = 0; \
! __asm__ __volatile__( \
! "lock cmpxchg %3,%1 \n" \
! "jnz 1f \n" \
! "inc %0 \n" \
! "1: \n" \
! :"=r"(ret) : \
! "m" (*mem), "a" (old), "r" (new), "0"(ret) ); \
! ret; \
! })
!
! #define CAS2(mem, old1, old2, new1, new2) \
! ({ int ret = 0; \
! __asm__ __volatile__( \
! "lock cmpxchg8b %1 \n" \
! "jnz 1f \n" \
! "inc %0 \n" \
! "1: \n" \
! :"=r"(ret) : \
! "m" (*mem), "a" (old1), "d" (old2), \
! "b" (new1), "c"(new2), "0"(ret)); \
! ret; \
! })
!
! #elif defined(NT) && defined(_MSC_VER)
!
! /* msvc on i386 */
!
! int CAS(void** mem, void* old, void* new1)
! {
! int retv = 0;
! __asm {
! mov eax, old
! mov ebx, new1
! mov esi, mem
! lock cmpxchg dword ptr [esi], ebx
! jnz end
! inc [retv]
! end:
! }
! return retv;
! }
!
! int CAS2(void** mem, void* old1, unsigned long old2, void* new1, unsigned long new2)
! {
! int retv = 0;
! __asm {
! mov eax, old1
! mov edx, old2
! mov ebx, new1
! mov ecx, new2
! mov esi, mem
! lock cmpxchg8b qword ptr [esi]
! jnz end
! inc [retv]
! end:
! }
! return retv;
! }
!
! #elif defined(__POWERPC__)
!
! /* gcc on ppc */
! #define CAS(mem, old, new) \
! ({ __typeof__(old) tmp; \
! int ret = 0; \
! __asm__ __volatile__( \
! "lwarx %0,0,%2 \n" \
! "cmpw %0,%3 \n" \
! "bne 1f \n" \
! "sync \n" \
! "stwcx %4,0,%2 \n" \
! "bne 1f \n" \
! "li %1,1 \n" \
! "1: \n" \
! :"=&r"(tmp), "=r"(ret) : \
! "m" (*mem), "r" (old), "r" (new) ); \
! ret; \
! })
!
! /* tb: i'm nut sure, if the handling of the two stwcx instructions
! * works correctly and if it's atomic */
! #define CAS2(mem, old1, old2, new1, new2) \
! ({ __typeof__(old1) tmp1; \
! __typeof__(old2) tmp2; \
! int ret = 0; \
! __asm__ __volatile__( \
! "lwarx %0,0,%3 \n" \
! "cmpw %0,%5 \n" \
! "bne 1f \n" \
! "lwarx %1,0,%4 \n" \
! "cmpw %1,%6 \n" \
! "bne 1f \n" \
! "sync \n" \
! "stwcx %7,0,%3 \n" \
! "bne 1f \n" \
! "stwcx %8,0,%4 \n" \
! "bne 1f \n" \
! "li %2,1 \n" \
! "1: \n" \
! :"=&r"(tmp1), "=&r"(tmp2), "=r"(ret) : \
! "m" (*mem), "m"(*(mem+(sizeof(__typeof__(old1))))), \
! "r" (old1), "r" (old2), \
! "r" (new1), "r"(new2), "0"(ret), ); \
! ret; \
! })
! #endif /* LOCKFREE */
!
! struct _fifo
! {
! t_fifocell* head;
! unsigned long ocount; /* operation counter */
! t_fifocell* tail;
! unsigned long icount; /* operation counter */
! };
!
! t_fifo* fifo_init()
! {
! t_fifo* ret = (t_fifo*) getbytes(sizeof(t_fifo));
! t_fifocell * fifo_begin = (t_fifocell*) getbytes (sizeof (t_fifocell) );
!
! fifo_begin->data = NULL;
! fifo_begin->next = NULL;
!
! ret->head = fifo_begin;
! ret->tail = fifo_begin;
! ret->icount = 0;
! ret->ocount = 0;
!
! return ret;
! }
!
! void fifo_destroy(t_fifo* fifo)
! {
! void * data;
!
! do
! {
! data = fifo_get(fifo);
! }
! while (data != NULL);
!
! freebytes(fifo->head, sizeof(t_fifocell));
! freebytes(fifo, sizeof(t_fifo));
! return;
! }
!
! void fifo_put(t_fifo* fifo, void* data)
! {
! if (data != NULL)
! {
! t_fifocell * cell = (t_fifocell*) getbytes(sizeof(t_fifocell));
! t_fifocell * tail;
! unsigned long icount;
!
! cell->data = data;
! cell->next = NULL;
!
! while(1)
! {
! icount = fifo->icount;
! tail = fifo->tail;
!
! if (CAS(&tail->next, NULL, cell))
! break;
! else
! CAS2(&fifo->tail, tail, icount, tail->next, icount + 1);
! }
!
! CAS2(&fifo->tail, tail, icount, cell, icount + 1);
! return;
! }
! else
! error("invalid data: NULL");
! }
!
!
! void* fifo_get(t_fifo* fifo)
! {
! t_fifocell * head;
! void* data;
!
! while (1)
! {
! unsigned long ocount = fifo->ocount;
! unsigned long icount = fifo->icount;
! t_fifocell * next;
!
! head = fifo->head;
! next = head->next;
!
! if (ocount == fifo->ocount)
! {
! if (head == fifo->tail)
! {
! if (next == NULL)
! return NULL;
! CAS2(&fifo->tail, head, icount, next, icount + 1);
! }
! else
! {
! data = next->data;
! if (CAS2(&fifo->head, head, ocount, next, ocount+1))
! break;
! }
! }
! }
!
! freebytes(head, sizeof(t_fifocell));
! return data;
! }
!
! #else
/* we always have the implementation for posix systems with threadlocks */
--- 10,14 ----
#include "m_fifo.h"
! #ifndef LOCKFREE
/* we always have the implementation for posix systems with threadlocks */
***************
*** 344,346 ****
--- 110,453 ----
return data;
}
+
+ #else /* LOCKFREE */
+
+ /*
+ lockfree fifo adapted from the midishare: Copyright © Grame 1999
+ Grame Research Laboratory, 9, rue du Garet 69001 Lyon - France
+ grame at rd.grame.fr
+ */
+
+
+
+ typedef struct _fifocell
+ {
+ struct _fifocell* next;
+ void* data; /* pointer to our data */
+ } t_fifocell;
+
+ typedef struct _lifo
+ {
+ unsigned long ic; /* operation counter */
+ t_fifocell* top; /* stack pointer */
+ unsigned long oc; /* operation counter */
+ #ifdef __POWERPC__
+ long unused [5]; /* lifo size must be at least 32 bytes */
+ /* to avoid livelock in multiprocessor */
+ #endif
+ } t_lifo;
+
+ struct _fifo
+ {
+ t_lifo in;
+ t_lifo out;
+ };
+
+ /* platform dependent code */
+
+ #ifdef __SMP__
+ #define LOCK lock ;
+ #else
+ #define LOCK
+ #endif
+
+ #if defined(__GNUC__) && defined(__POWERPC__)
+
+ static void* lifo_pop(t_lifo* lifo)
+ {
+ register void * data;
+ register volatile long a, b;
+ register long c=0;
+ asm volatile (
+ "# LFPOP \n"
+ "0: \n"
+ " lwarx %4, %1, %2 \n" /* creates a reservation on lf */
+ " cmpwi %4, 0 \n" /* test if the lifo is empty */
+ " beq- 1f \n"
+ " lwz %5, 0(%4) \n" /* next cell in b */
+ " sync \n" /* synchronize instructions */
+ " stwcx. %5, %1, %2 \n" /* if the reservation is not altered */
+ /* modify lifo top */
+ " bne- 0b \n" /* otherwise: loop and try again */
+ "0: \n"
+ " lwarx %5, %1, %3 \n" /* creates a reservation on lf->count */
+ " addi %5, %5, -1 \n" /* dec count */
+ " sync \n" /* synchronize instructions */
+ " stwcx. %5, %1, %3 \n" /* conditionnal store */
+ " bne- 0b \n"
+ "1: \n"
+ " mr %0, %4 \n"
+ :"=r" (data), "=r" (c)
+ : "r" (&lifo->top), "r" (&lf->oc), "r" (a), "r" (b), "1" (c)
+ : "r0" /* prevents using r0 because of the ambiguity of 'addi' coding: */
+ /* gcc version 2.95.3 20010315 (release - Linux-Mandrake 8.0 for PPC) */
+ /* compiles the instruction "addi 0, 0, n" as li 0, n */
+ );
+ return data;
+ }
+
+ static void* lifo_push(register t_lifo* lifo, register void* data)
+ {
+ register volatile long t1;
+ register long t2=0;
+ asm volatile (
+ "# LFPUSH \n"
+ "0: \n"
+ " lwarx %0, %3, %1 \n"
+ " stw %0, 0(%2) \n"
+ " sync \n"
+ " stwcx. %2, %3, %1 \n"
+ " bne- 0b \n"
+ "0: \n"
+ " lwarx %0, %3, %4 \n"
+ " addi %0, %0, 1 \n"
+ " sync \n"
+ " stwcx. %0, %3, %4 \n"
+ " bne- 0b \n"
+ : "=r" (t1)
+ : "r" (&lifo->top), "r" (data), "r" (t2), "r" (&lf->oc), "0" (t1)
+ : "r0" /* prevents using r0 because of the ambiguity of 'addi' coding: */
+ /* gcc version 2.95.3 20010315 (release - Linux-Mandrake 8.0 for PPC) */
+ /* compiles the instruction "addi 0, 0, n" as li 0, n */
+ );
+ }
+
+ #elif defined(__Macintosh__) || defined(__MacOSX__)
+
+ static void* lifo_pop(t_lifo* lifo)
+ {
+ register cell * data;
+ register long a, b;
+ asm {
+ addi lifo, lifo, 4
+ loop:
+ lwarx a, 0, lifo /* creates a reservation on lifo */
+ cmpwi a, 0 /* test if the lifo is empty */
+ beq- empty
+ lwz b, 0(a) /* next cell in b */
+ sync /* synchronize instructions */
+ stwcx. b, 0, lifo /* if the reservation is not altered */
+ /* modify lifo top */
+ bne- loop /* otherwise: loop and try again */
+
+ addi lifo, lifo, 4
+ dec:
+ lwarx b, 0, lifo /* creates a reservation on lifo->count */
+ addi b, b, -1 /* dec count */
+ sync /* synchronize instructions */
+ stwcx. b, 0, lifo /* conditionnal store */
+ bne- dec
+
+ empty:
+ mr data, a
+ }
+ return data;
+ }
+
+ static void lifo_push (register t_lifo * lifo, register void * data)
+ {
+ register long tmp;
+ asm {
+ addi lifo, lifo, 4
+ loop:
+ lwarx tmp, 0, lifo /* creates a reservation on lifo */
+ stw tmp, 0(data) /* link the new cell to the lifo */
+ sync /* synchronize instructions */
+ stwcx. data, 0, lifo /* if the reservation is not altered */
+ /* modify lifo top */
+ bne- loop /* otherwise: loop and try again */
+
+ addi lifo, lifo, 4
+ inc:
+ lwarx tmp, 0, lifo /* creates a reservation on lifo->count */
+ addi tmp, tmp, 1 /* inc count */
+ sync /* synchronize instructions */
+ stwcx. tmp, 0, lifo /* conditionnal store */
+ bne- inc
+ }
+ }
+
+
+
+ #elif defined(__GNUC__) && (defined(_X86_) || defined(__i386__) || defined(__i586__) || defined(__i686__))
+
+ static void* lifo_pop(t_lifo* lifo)
+ {
+ void * data = 0;
+ __asm__ __volatile__ (
+ "# LFPOP \n\t"
+ "pushl %%ebx \n\t"
+ "pushl %%ecx \n\t"
+ "movl 4(%%esi), %%edx \n\t"
+ "movl (%%esi), %%eax \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 (%%esi) \n\t"
+ "jz 20f \n\t"
+ "testl %%eax, %%eax \n\t"
+ "jnz 10b \n"
+ "20:\t"
+ "popl %%ecx \n\t"
+ "popl %%ebx \n\t"
+ :"=a" (data)
+ :"S" (&lifo->top)
+ :"memory", "edx");
+ return data;
+ }
+
+ static void lifo_push(t_lifo * lifo, void * data)
+ {
+ __asm__ __volatile__ (
+ "# LFPUSH \n\t"
+ "pushl %%ebx \n\t"
+ "pushl %%ecx \n\t"
+ "movl 0(%%esi), %%eax \n\t"
+ "movl 4(%%esi), %%edx \n"
+ "1:\t"
+ "movl %%eax, %%ebx \n\t"
+ "incl %%ebx \n\t"
+ "movl %%edx, (%%ecx) \n\t"
+ LOCK "cmpxchg8b (%%esi) \n\t"
+ "jnz 1b \n\t"
+ "popl %%ecx \n\t"
+ "popl %%ebx \n\t"
+ :/* no output */
+ :"S" (lifo), "c" (data)
+ :"memory", "eax", "edx");
+ }
+
+
+ #elif defined(__Windows__)
+
+ static void* lifo_pop(t_lifo* lifo)
+ {
+ __asm
+ {
+ push ebx
+ push ecx
+ push edx
+ push esi
+ mov esi, lifo
+ add esi, 4
+ mov edx, dword ptr [esi+4]
+ mov eax, dword ptr [esi]
+ test eax, eax
+ jz _end
+ _loop:
+ mov ebx, dword ptr [eax]
+ mov ecx, edx
+ inc ecx
+ LOCK cmpxchg8b qword ptr [esi]
+ jz _end
+ test eax, eax
+ jnz _loop
+ _end:
+ pop esi
+ pop edx
+ pop ecx
+ pop ebx
+ }
+
+ static void lifo_push(t_lifo * lifo, void * data)
+ {
+ __asm
+ {
+ push eax
+ push ebx
+ push ecx
+ push edx
+ push esi
+ mov esi, lifo
+ mov eax, dword ptr [esi]
+ mov ecx, data
+ mov edx, dword ptr 4[esi]
+ _loop:
+ mov ebx, eax
+ inc ebx
+ mov [ecx], edx
+ LOCK cmpxchg8b qword ptr [esi]
+ jnz _loop
+ pop esi
+ pop edx
+ pop ecx
+ pop ebx
+ pop eax
+ }
+ }
+
+
+ #else
+ #error lockfree fifos not available on this platform
+ #endif
+
+
+
+ static void lifo_init(t_lifo* lifo)
+ {
+ lifo->ic = 0;
+ lifo->top = NULL;
+ lifo->oc = 0;
+ }
+
+ t_fifo* fifo_init(void)
+ {
+ t_fifo* ret = (t_fifo*) getbytes(sizeof(t_fifo));
+
+ lifo_init(&ret->in);
+ lifo_init(&ret->out);
+
+ return ret;
+ }
+
+
+ void fifo_destroy(t_fifo* fifo)
+ {
+ void * data;
+ do
+ {
+ data = fifo_get(fifo);
+ }
+ while (data != NULL);
+
+ freebytes(fifo, sizeof(t_fifo));
+ return;
+ }
+
+ void fifo_put(t_fifo* fifo, void* data)
+ {
+ lifo_push(&fifo->in, data);
+ }
+
+ void* fifo_get(t_fifo* fifo)
+ {
+ void * data;
+ t_lifo *out = &fifo->out;
+
+ data = lifo_pop(out);
+
+ if (!data)
+ {
+ void * tmp;
+ t_lifo *in = &fifo->in;
+ data = lifo_pop(in);
+
+ if (data)
+ {
+ while((tmp = lifo_pop(in)))
+ {
+ lifo_push(out, data);
+ data = tmp;
+ }
+ }
+
+ }
+ return data;
+ }
+
+
+
#endif
More information about the Pd-cvs
mailing list