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@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