From 3e68cf92ed7c9eeba4df08228bda9284856ad0da Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= Date: Wed, 30 Jan 2013 11:37:51 +0100 Subject: cleanup lock_free_queue --- lock_free_queue.c | 157 +++++++++++++++++++++++++++---------------------- lock_free_queue.h | 44 +++++++++----- lock_free_queue_test.c | 48 +++++++-------- 3 files changed, 141 insertions(+), 108 deletions(-) diff --git a/lock_free_queue.c b/lock_free_queue.c index e3e128f..a21d1ce 100644 --- a/lock_free_queue.c +++ b/lock_free_queue.c @@ -1,7 +1,7 @@ /* * File : lock_free_queue.c * Author : Jérémy Zurcher - * Date : 01/11/09 + * Date : 2009/11/01 * License : stolen from http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf */ @@ -14,87 +14,102 @@ /* 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 compare_and_swap(volatile unsigned long long *mem, volatile unsigned long long old, - volatile unsigned long long new) { - char result; - __asm__ __volatile__("lock; cmpxchg8b %0; setz %1;" + volatile unsigned long long new) +{ + char result; + __asm__ __volatile__("lock; cmpxchg8b %0; setz %1;" : "=m"(*mem), "=q"(result) - : "m"(*mem), "d" ((unsigned long)(old>>32)), "a" ((unsigned long)old), - "c" ((unsigned long)(new>>32)), "b" ((unsigned long)new) + : "m"(*mem), "d" ((unsigned long)(old>>32)), "a" ((unsigned long)old) + , "c" ((unsigned long)(new>>32)), "b" ((unsigned long)new) : "memory"); - return (int)result; + return (int)result; } -void init( lfq_t *q ) { - node_t *node = (node_t*)malloc(sizeof(node_t)); - node->next.split.ptr = NULL; - node->next.split.count = 0; - q->head.split.ptr = q->tail.split.ptr = node; - q->head.split.count = q->tail.split.count = 0; +void init(lfq_t *q) +{ + node_t *node = (node_t*)malloc(sizeof(node_t)); + node->next.split.ptr = NULL; + node->next.split.count = 0; + q->head.split.ptr = q->tail.split.ptr = node; + q->head.split.count = q->tail.split.count = 0; } -void enqueue( lfq_t *q, void *data ) { - node_t *node; - pointer_t tail; - pointer_t next; - pointer_t tmp; +void enqueue(lfq_t *q, void *data) +{ + node_t *node; + pointer_t tail; + pointer_t next; + pointer_t tmp; - node = (node_t*)malloc(sizeof(node_t)); - node->data = data; - node->next.split.ptr = NULL; - /* node->next.split.count = 0; */ - for(;;) { - tail.concat = q->tail.concat; /* copy tail pointer */ - next.concat = tail.split.ptr->next.concat; /* copy next pointer */ - if (tail.concat == q->tail.concat) { /* tail is still consistent */ - if (next.split.ptr == NULL) { /* next is still the last node */ - /* if tail->next is the same as next, link node at the end of the list */ - tmp.split.ptr = node; - tmp.split.count = next.split.count+1; - if ( compare_and_swap( &tail.split.ptr->next.concat, next.concat, tmp.concat ) ) break; - } else { - /* try to swing tail to the next node, if q-> tail is still tail => next is ok */ - tmp.split.ptr = next.split.ptr; - tmp.split.count = tail.split.count+1; - compare_and_swap( &q->tail.concat, tail.concat, tmp.concat ); - } - } - } - /* try to swing tail to the next node, may have been done by a concurrent push */ - tmp.split.ptr = node; - tmp.split.count = tail.split.count+1; - compare_and_swap( &q->tail.concat, tail.concat, tmp.concat ); + node = (node_t*)malloc(sizeof(node_t)); + node->data = data; + node->next.split.ptr = NULL; + /* node->next.split.count = 0; */ + for(;;) + { + tail.concat = q->tail.concat; /* copy tail pointer */ + next.concat = tail.split.ptr->next.concat; /* copy next pointer */ + if (tail.concat == q->tail.concat) + { /* tail is still consistent */ + if (next.split.ptr == NULL) + { /* next is still the last node */ + /* if tail->next is the same as next, link node at the end of the list */ + tmp.split.ptr = node; + tmp.split.count = next.split.count+1; + if ( compare_and_swap( &tail.split.ptr->next.concat, next.concat, tmp.concat ) ) break; + } + else + { + /* try to swing tail to the next node, if q-> tail is still tail => next is ok */ + tmp.split.ptr = next.split.ptr; + tmp.split.count = tail.split.count+1; + compare_and_swap( &q->tail.concat, tail.concat, tmp.concat ); + } + } + } + /* try to swing tail to the next node, may have been done by a concurrent push */ + tmp.split.ptr = node; + tmp.split.count = tail.split.count+1; + compare_and_swap( &q->tail.concat, tail.concat, tmp.concat ); } -void* dequeue( lfq_t *q ) { - void *data; - pointer_t head; - pointer_t tail; - node_t *next; - pointer_t tmp; - - for(;;) { +void* dequeue(lfq_t *q) +{ + void *data; + pointer_t head; + pointer_t tail; + node_t *next; + pointer_t tmp; + + for(;;) + { head.concat = q->head.concat; tail.concat = q->tail.concat; next = (node_t *)head.split.ptr; - if (head.concat == q->head.concat) { - if (head.split.ptr == tail.split.ptr) { /* still consistent */ - if (next->next.split.ptr == NULL) { /* queue empty */ - return NULL; - } - /* new node has been linked, but tail is behind, should advance it */ - tmp.split.ptr = next->next.split.ptr; - tmp.split.count = tail.split.count+1; - compare_and_swap( &q->tail.concat, tail.concat, tmp.concat ); - } else { - data = next->data; - /* try to swing head to the next node */ - tmp.split.ptr = next->next.split.ptr; - tmp.split.count = head.split.count+1; - if( compare_and_swap( &q->head.concat, head.concat, tmp.concat ) ) break; - } - } - } - free((void*)head.split.ptr); - return data; + if (head.concat == q->head.concat) + { + if (head.split.ptr == tail.split.ptr) + { /* still consistent */ + if (next->next.split.ptr == NULL) + { /* queue empty */ + return NULL; + } + /* new node has been linked, but tail is behind, should advance it */ + tmp.split.ptr = next->next.split.ptr; + tmp.split.count = tail.split.count+1; + compare_and_swap( &q->tail.concat, tail.concat, tmp.concat ); + } + else + { + data = next->data; + /* try to swing head to the next node */ + tmp.split.ptr = next->next.split.ptr; + tmp.split.count = head.split.count+1; + if( compare_and_swap( &q->head.concat, head.concat, tmp.concat ) ) break; + } + } + } + free((void*)head.split.ptr); + return data; } diff --git a/lock_free_queue.h b/lock_free_queue.h index 14a2cae..0bce83e 100644 --- a/lock_free_queue.h +++ b/lock_free_queue.h @@ -1,31 +1,47 @@ /* * File : lock_free_queue.h * Author : Jérémy Zurcher - * Date : 01/11/09 + * Date : 2009/11/01 * License : stolen from http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf */ +#ifndef _LOCK_FREE_QUEUE_H_ +#define _LOCK_FREE_QUEUE_H_ + +# ifdef __cplusplus +extern "C" { +# endif /* __cplusplus */ + struct node; -typedef union pointer { - struct { +typedef union pointer +{ + struct + { volatile struct node *ptr; volatile unsigned int count; - } split; - volatile unsigned long long concat; + } split; + volatile unsigned long long concat; } pointer_t; -typedef struct node { - void *data; - pointer_t next; +typedef struct node +{ + void *data; + pointer_t next; } node_t; -typedef struct queue { - pointer_t head; - pointer_t tail; +typedef struct queue +{ + pointer_t head; + pointer_t tail; } lfq_t; -void init( lfq_t *q ); -void enqueue( lfq_t *q, void *data ); -void* dequeue( lfq_t *q ); +void init(lfq_t *q); +void enqueue(lfq_t *q, void *data); +void* dequeue(lfq_t *q); + +# ifdef __cplusplus +} +# endif /* __cplusplus */ +# endif /* _LOCK_FREE_QUEUE_H_ */ diff --git a/lock_free_queue_test.c b/lock_free_queue_test.c index 3a067d7..157c984 100644 --- a/lock_free_queue_test.c +++ b/lock_free_queue_test.c @@ -1,7 +1,7 @@ /* * File : lock_free_queue_test.c * Author : Jérémy Zurcher - * Date : 01/11/09 + * Date : 2009/11/01 * License : * * Permission is hereby granted, free of charge, to any person obtaining @@ -11,10 +11,10 @@ * 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 @@ -29,31 +29,33 @@ #include "stdlib.h" #include "lock_free_queue.h" -int main(int argc, char *argv[]) { - lfq_t q; - node_t *it; - int data[10]; - int i; +int main(int argc, char *argv[]) +{ + lfq_t q; + node_t *it; + int data[10]; + int i; + + for(i=0; i<10; i++) data[i]=i; + for(i=0; i<10; i++) printf("data[i] :%d (%X)\n",data[i],(unsigned int)&data[i]); - for(i=0; i<10; i++) data[i]=i; - for(i=0; i<10; i++) printf("data[i] :%d (%X)\n",data[i],(unsigned int)&data[i]); - - init( &q); - for(i=0; i<10; i++) enqueue( &q, (void*)&data[i] ); + init( &q); + for(i=0; i<10; i++) enqueue( &q, (void*)&data[i] ); - it = (node_t*)q.head.split.ptr; - while(it!=NULL) { + it = (node_t*)q.head.split.ptr; + while(it!=NULL) + { if(it->data>0)printf("data : %X %d\n",(unsigned int)it->data,*((int*)it->data)); it = (node_t*)it->next.split.ptr; - } - - for(i=0; i<5; i++) printf("unqueue %X\n",(unsigned int)dequeue( &q )); - it = (node_t*)q.head.split.ptr; - while(it!=NULL) { + } + + for(i=0; i<5; i++) printf("unqueue %X\n",(unsigned int)dequeue( &q )); + it = (node_t*)q.head.split.ptr; + while(it!=NULL) + { if(it->data>0)printf("data : %X %d\n",(unsigned int)it->data,*((int*)it->data)); it = (node_t*)it->next.split.ptr; - } - + } - return EXIT_SUCCESS; + return EXIT_SUCCESS; } -- cgit v1.1-2-g2b99