diff options
| -rw-r--r-- | Makefile | 21 | ||||
| -rw-r--r-- | cas.h | 40 | ||||
| -rw-r--r-- | cas_test.c | 62 | ||||
| -rw-r--r-- | lock_free_queue.c | 88 | ||||
| -rw-r--r-- | lock_free_queue.h | 31 | ||||
| -rw-r--r-- | lock_free_queue_test.c | 59 |
6 files changed, 301 insertions, 0 deletions
diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..63e4a7c --- /dev/null +++ b/Makefile @@ -0,0 +1,21 @@ + + +CC = gcc +STD = _GNU_SOURCE +CFLAGS = -DDEBUG +BIN = cas_test lock_free_queue_test + +.c.o: + $(CC) -c -Wall -I. $(CFLAGS) -D$(STD) $< + +all: $(BIN) + +cas_test: cas_test.o + $(CC) cas_test.o -o cas_test + +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 + +clean: + rm -f *~ *.o core $(BIN) + @@ -0,0 +1,40 @@ +/* + * File : cas.c + * Author : Jérémy Zurcher <jeremy@asynk.ch> + * 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. + * + */ + +/* 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;" + : "=m"(*mem), "=q"(result) + : "m"(*mem), "d" ((unsigned long)(old>>32)), "a" ((unsigned long)old), + "c" ((unsigned long)(new>>32)), "b" ((unsigned long)new) + : "memory"); + return (int)result; +} + diff --git a/cas_test.c b/cas_test.c new file mode 100644 index 0000000..a2b92a6 --- /dev/null +++ b/cas_test.c @@ -0,0 +1,62 @@ +/* + * File : atomic.c + * Author : Jérémy Zurcher <jeremy@asynk.ch> + * 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 <stdio.h> +#include "cas.h" + +#define MAKE_LONG_LONG(lo, hi) ((hi)<<32)+(lo) + +typedef union pointer { + struct { + volatile void *ptr; + volatile unsigned int count; + } split; + volatile unsigned long long concat; +} pointer_t; + +int main( int argc, char*argv[], char*env[] ) { + int ret; + + pointer_t mem, old, new; + + mem.split.count = 0; + old.split.count = 6; + new.split.count = 666; + mem.split.ptr = (void*)&argc; + old.split.ptr = (void*)&argc; + new.split.ptr = (void*)&argv; + + ret = compare_and_swap(&mem.concat, old.concat, new.concat); + printf("ret %d -> (%d,%X)\n", ret, mem.split.count, (unsigned int)mem.split.ptr); + + mem.split.count=6; + ret = compare_and_swap(&mem.concat, old.concat, new.concat); + printf("ret %d -> (%d,%X)\n", ret, mem.split.count, (unsigned int)mem.split.ptr); + + return 0; +} + diff --git a/lock_free_queue.c b/lock_free_queue.c new file mode 100644 index 0000000..217fb0b --- /dev/null +++ b/lock_free_queue.c @@ -0,0 +1,88 @@ +/* + * File : lock_free_queue.c + * Author : Jérémy Zurcher <jeremy@asynk.ch> + * Date : 01/11/09 + * License : stolen from http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf + */ + +#include "stdlib.h" +#include "cas.h" +#include "lock_free_queue.h" +#ifdef DEBUG +#include "stdio.h" +#endif + +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; + + 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(;;) { + 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; +} + diff --git a/lock_free_queue.h b/lock_free_queue.h new file mode 100644 index 0000000..ac8a859 --- /dev/null +++ b/lock_free_queue.h @@ -0,0 +1,31 @@ +/* + * File : lock_free_queue.c + * Author : Jérémy Zurcher <jeremy@asynk.ch> + * Date : 01/11/09 + * License : stolen from http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf + */ + +struct node; + +typedef union pointer { + struct { + volatile struct node *ptr; + volatile unsigned int count; + } split; + volatile unsigned long long concat; +} pointer_t; + +typedef struct node { + void *data; + pointer_t next; +} node_t; + +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 ); + diff --git a/lock_free_queue_test.c b/lock_free_queue_test.c new file mode 100644 index 0000000..64544eb --- /dev/null +++ b/lock_free_queue_test.c @@ -0,0 +1,59 @@ +/* + * File : lock_free_queue.c + * Author : Jérémy Zurcher <jeremy@asynk.ch> + * 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 "stdio.h" +#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; + + 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] ); + + 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) { + 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; +} |