From 491770df273ac2628c98a559fe8bbed5e812fbed Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= Date: Sat, 7 Nov 2009 23:54:32 +0100 Subject: lf_fifo don't use union anymore, just for one == --- Makefile | 4 +-- lf_cas.h | 61 ++++++++++++++++++++++++++++++++++++++++++ lf_fifo.c | 84 ++++++++++++++++++++++++++++++---------------------------- lf_fifo.h | 17 ++++-------- lf_fifo_cas.h | 42 ----------------------------- lf_fifo_test.c | 45 +++++++++++++++---------------- 6 files changed, 132 insertions(+), 121 deletions(-) create mode 100644 lf_cas.h delete mode 100644 lf_fifo_cas.h diff --git a/Makefile b/Makefile index 27586c4..a12803a 100644 --- a/Makefile +++ b/Makefile @@ -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 diff --git a/lf_cas.h b/lf_cas.h new file mode 100644 index 0000000..1a21bf1 --- /dev/null +++ b/lf_cas.h @@ -0,0 +1,61 @@ +/* + * File : lf_cas.h + * Author : Jérémy Zurcher + * Date : 01/11/09 + * License : + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + * + */ + +#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 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.ptr), + "c" (new.count), "b" (new.ptr) + : "memory"); + return (int)result; +} + +# ifdef __cplusplus +} +# endif /* __cplusplus */ + +# endif /* _LF_CAS_H_ */ + diff --git a/lf_fifo.c b/lf_fifo.c index ba71847..1f4ab90 100644 --- a/lf_fifo.c +++ b/lf_fifo.c @@ -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; diff --git a/lf_fifo.h b/lf_fifo.h index dc3e87d..cfecee1 100644 --- a/lf_fifo.h +++ b/lf_fifo.h @@ -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_cas.h b/lf_fifo_cas.h deleted file mode 100644 index e380f8e..0000000 --- a/lf_fifo_cas.h +++ /dev/null @@ -1,42 +0,0 @@ -/* - * File : lf_fifo_cas.h - * Author : Jérémy Zurcher - * Date : 01/11/09 - * License : - * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * distribute, sublicense, and/or sell copies of the Software, and to - * permit persons to whom the Software is furnished to do so, subject to - * the following conditions: - * - * The above copyright notice and this permission notice shall be - * included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND - * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE - * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION - * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION - * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - * - */ - -#include "lf_fifo.h" - -/* 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 ) { - 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) - : "memory"); - return (int)result; -} - 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; -- cgit v1.1-2-g2b99