diff options
| -rw-r--r-- | Makefile | 4 | ||||
| -rw-r--r-- | lf_cas.h (renamed from lf_fifo_cas.h) | 33 | ||||
| -rw-r--r-- | lf_fifo.c | 84 | ||||
| -rw-r--r-- | lf_fifo.h | 17 | ||||
| -rw-r--r-- | lf_fifo_test.c | 45 |
5 files changed, 97 insertions, 86 deletions
@@ -3,7 +3,7 @@ CC = gcc STD = _GNU_SOURCE CFLAGS = -DDEBUG -BIN = cas container_of lock_free_queue_test lf_fifo +BIN = cas container_of lock_free_queue_test lf_fifo_test .c.o: $(CC) -c -Wall -I. $(CFLAGS) -D$(STD) $< @@ -21,8 +21,6 @@ container_of: container_of.o lock_free_queue_test: lock_free_queue.o lock_free_queue_test.o $(CC) lock_free_queue.o lock_free_queue_test.o -o lock_free_queue_test - - lf_fifo.o: lf_fifo.h lf_cas.h lf_fifo_test: lf_fifo.o lf_fifo_test.o @@ -1,5 +1,5 @@ /* - * File : lf_fifo_cas.h + * File : lf_cas.h * Author : Jérémy Zurcher <jeremy@asynk.ch> * Date : 01/11/09 * License : @@ -25,18 +25,37 @@ * */ -#include "lf_fifo.h" +#ifndef _LF_CAS_H_ +#define _LF_CAS_H_ + +# ifdef __cplusplus +extern "C" { +# endif /* __cplusplus */ + +struct lf_pointer; + +typedef struct lf_pointer { + volatile struct lf_pointer *ptr; + volatile unsigned int count; +} lf_pointer_t; + /* CMPXCHG8B m64 Compare EDX:EAX with m64. If equal, set ZF and load ECX:EBX into m64. Else, clear ZF and load m64 into EDX:EAX. */ -static inline unsigned int cas( volatile struct split *mem, - volatile struct split old, - volatile struct split new ) { +static inline unsigned int cas( volatile lf_pointer_t *mem, + volatile lf_pointer_t old, + volatile lf_pointer_t new ) { char result; __asm__ __volatile__("lock; cmpxchg8b %0; setz %1;" : "=m"(*mem), "=q"(result) - : "m"(*mem), "d" (old.count), "a" (old.next), - "c" (new.count), "b" (new.next) + : "m"(*mem), "d" (old.count), "a" (old.ptr), + "c" (new.count), "b" (new.ptr) : "memory"); return (int)result; } +# ifdef __cplusplus +} +# endif /* __cplusplus */ + +# endif /* _LF_CAS_H_ */ + @@ -26,86 +26,90 @@ */ #include "lf_fifo.h" -#include "lf_fifo_cas.h" #include "stdlib.h" +union ptr_u { + lf_pointer_t ptr; + volatile long long concat; +}; + /* initialize an empty lf_fifo structure */ void lf_fifo_init( lf_fifo_t *q ) { - q->head.split.next = q->tail.split.next = NULL; - q->head.split.count = q->tail.split.count = 0; + q->head.ptr = q->tail.ptr = NULL; + q->head.count = q->tail.count = 0; } /* push a node at the tail of q */ -void lf_fifo_push( lf_fifo_t *q, pointer_t *node ) { - pointer_t tail; - pointer_t last; - pointer_t tmp; +void lf_fifo_push( lf_fifo_t *q, lf_pointer_t *node ) { + lf_pointer_t tail; + lf_pointer_t last; + lf_pointer_t tmp; /* init node */ - node->split.next = NULL; - node->split.count = 0; + node->ptr = NULL; + node->count = 0; /* set tmp to point to node */ - tmp.split.next = node; - tmp.split.count = 1; + tmp.ptr = node; + tmp.count = 1; for(;;) { /* snapshot tail */ - tail.concat = q->tail.concat; + tail = q->tail; /* nothing in tail link as first node */ - if ( tail.split.next==NULL && cas( &q->tail.split, tail.split, tmp.split ) ) { /* TODO right place ?? */ - q->head.split.next = node; - /* q->head.split.count = 1; ??? */ + if ( tail.ptr==NULL && cas( &q->tail, tail, tmp ) ) { /* TODO right place ?? */ + q->head.ptr = node; + /* q->head.count = 1; ??? */ return; } else { /* snapshot last through tail */ - last.concat = (*tail.split.next).concat; + last = *tail.ptr; /* if tail is still consistant */ - if (tail.concat == q->tail.concat) { + if (((union ptr_u)tail).concat == ((union ptr_u)q->tail).concat) { /* if last is the last node */ - if (last.split.next == NULL) { - tmp.split.count = last.split.count+1; - if ( cas( &tail.split.next->split, last.split, tmp.split ) ) break; + if (last.ptr == NULL) { + tmp.count = last.count+1; + if ( cas( tail.ptr, last, tmp ) ) break; } else { /* try to swing tail to the next node */ - last.split.count = tail.split.count+1; - cas( &q->tail.split, tail.split, last.split ); + last.count = tail.count+1; + cas( &q->tail, tail, last ); } } } } /* try to swing tail to the next node */ - tmp.split.count = tail.split.count+1; - cas( &q->tail.split, tail.split, tmp.split ); + tmp.count = tail.count+1; + cas( &q->tail, tail, tmp ); } /* pop a node from the head of q */ -pointer_t* pop( lf_fifo_t *q ) { - pointer_t head; - pointer_t tail; - pointer_t tmp; - pointer_t *node; +lf_pointer_t* pop( lf_fifo_t *q ) { + lf_pointer_t head; + lf_pointer_t tail; + lf_pointer_t tmp; + lf_pointer_t *node; for(;;) { /* snapshot head */ - head.concat = q->head.concat; + head = q->head; /* return NULL if queue is empty */ - if (head.split.next == NULL) { return NULL; } /* TODO before snapshot using q-> ?? */ + if (head.ptr == NULL) { return NULL; } /* TODO before snapshot using q-> ?? */ /* snapshot tail */ - tail.concat = q->tail.concat; + tail = q->tail; /* if there is only one node in the queue */ - if ( tail.split.next == head.split.next ) { + if ( tail.ptr == head.ptr ) { /* tail points to NULL */ - tmp.split.next = NULL; - tmp.split.count = tail.split.count+1; - cas( &q->tail.split, tail.split, tmp.split ); + tmp.ptr = NULL; + tmp.count = tail.count+1; + cas( &q->tail, tail, tmp ); } else { /* get the node ptr */ - node = (pointer_t *)head.split.next; + node = (lf_pointer_t *)head.ptr; /* get the next head ready */ - tmp.split.next = node->split.next; - tmp.split.count = head.split.count+1; - if ( cas( &q->head.split, head.split, tmp.split ) ) break; + tmp.ptr = node->ptr; + tmp.count = head.count+1; + if ( cas( &q->head, head, tmp ) ) break; } } return node; @@ -25,6 +25,7 @@ * */ +#include "lf_cas.h" #ifndef _LF_FIFO_H_ #define _LF_FIFO_H_ @@ -33,27 +34,19 @@ extern "C" { # endif /* __cplusplus */ -typedef union pointer { - struct split { - volatile union pointer *next; - volatile unsigned int count; - } split; - volatile unsigned long long concat; -} pointer_t; - typedef struct queue { - pointer_t head; - pointer_t tail; + lf_pointer_t head; + lf_pointer_t tail; } lf_fifo_t; /* initialize an empty lf_fifo structure */ void lf_fifo_init( lf_fifo_t *q ); /* push a node at the tail of q */ -void lf_fifo_push( lf_fifo_t *q, pointer_t *node ); +void lf_fifo_push( lf_fifo_t *q, lf_pointer_t *node ); /* pop a node from the head of q */ -pointer_t* pop( lf_fifo_t *q ); +lf_pointer_t* pop( lf_fifo_t *q ); # ifdef __cplusplus } diff --git a/lf_fifo_test.c b/lf_fifo_test.c index 9d5a6bc..86898cb 100644 --- a/lf_fifo_test.c +++ b/lf_fifo_test.c @@ -30,41 +30,38 @@ #include "stddef.h" #include "lf_fifo.h" -#include "lf_fifo_cas.h" -#define container_of(ptr, type, member) ({ \ - const typeof( ((type *)0)->member ) *__mptr = (ptr); \ - (type *)( (char *)__mptr - offsetof(type,member) );}) +#define container_of(ptr, type, member) ( { (type*)(((char*)ptr)-offsetof(type,member)); } ) struct node { int data; - pointer_t link; + lf_pointer_t link; }; int main(int argc, char *argv[]) { - pointer_t new; - pointer_t old; - pointer_t mem; + lf_pointer_t new; + lf_pointer_t old; + lf_pointer_t mem; int ret; lf_fifo_t q; - pointer_t *it; + lf_pointer_t *it; struct node data[10]; int i; /* check comprae_and_swap */ - mem.split.count = 0; - old.split.count = 6; - new.split.count = 666; - mem.split.next = (void*)&argc; - old.split.next = (void*)&argc; - new.split.next = (void*)&argv; - ret = cas(&mem.split, old.split, new.split); - printf("ret %d -> (%d,%X)\n", ret, mem.split.count, (unsigned int)mem.split.next); + mem.count = 0; + old.count = 6; + new.count = 666; + mem.ptr = (void*)&argc; + old.ptr = (void*)&argc; + new.ptr = (void*)&argv; + ret = cas(&mem, old, new); + printf("ret %d -> (%d,%X)\n", ret, mem.count, (unsigned int)mem.ptr); - mem.split.count=6; - ret = cas(&mem.split, old.split, new.split); - printf("ret %d -> (%d,%X)\n", ret, mem.split.count, (unsigned int)mem.split.next); + mem.count=6; + ret = cas(&mem, old, new); + printf("ret %d -> (%d,%X)\n", ret, mem.count, (unsigned int)mem.ptr); /* init data */ for(i=0; i<10; i++) data[i].data=i; @@ -75,20 +72,20 @@ int main(int argc, char *argv[]) { printf("pop %X\n",(unsigned int)pop( &q )); for(i=0; i<10; i++) lf_fifo_push( &q, &data[i].link ); - it = (pointer_t*)q.head.split.next; + it = (lf_pointer_t*)q.head.ptr; while(it!=NULL) { printf("data : %d\n",container_of(it,struct node,link)->data); - it = (pointer_t*)it->split.next; + it = (lf_pointer_t*)it->ptr; } for(i=0; i<5; i++) { it = pop( &q ); printf("pop %X %d\n",(unsigned int)it,container_of(it,struct node,link)->data); } - it = (pointer_t*)q.head.split.next; + it = (lf_pointer_t*)q.head.ptr; while(it!=NULL) { printf("data : %d\n",container_of(it,struct node,link)->data); - it = (pointer_t*)it->split.next; + it = (lf_pointer_t*)it->ptr; } return EXIT_SUCCESS; |