diff options
| -rw-r--r-- | Makefile | 11 | ||||
| -rw-r--r-- | lfq.c | 113 | ||||
| -rw-r--r-- | lfq.h | 63 | ||||
| -rw-r--r-- | lfq_cas.h | 42 | ||||
| -rw-r--r-- | lfq_test.c | 102 |
5 files changed, 328 insertions, 3 deletions
@@ -3,7 +3,7 @@ CC = gcc STD = _GNU_SOURCE CFLAGS = -DDEBUG -BIN = cas_test lock_free_queue_test +BIN = cas_test lock_free_queue_test lfq_test .c.o: $(CC) -c -Wall -I. $(CFLAGS) -D$(STD) $< @@ -16,6 +16,11 @@ cas_test: cas_test.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 -clean: - rm -f *~ *.o core $(BIN) +lfq_test: lfq_cas.h lfq.o lfq_test.o + $(CC) lfq.o lfq_test.o -o lfq_test + +as: + $(CC) -S lfq.c +clean: + rm -f *~ *.o *.s core $(BIN) @@ -0,0 +1,113 @@ +/* + * File : lfq.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 "lfq.h" +#include "lfq_cas.h" +#include "stdlib.h" + +/* initialize an empty lfq structure */ +void lfq_init( lfq_t *q ) { + q->head.split.next = q->tail.split.next = NULL; + q->head.split.count = q->tail.split.count = 0; +} + +/* push a node at the tail of q */ +void lfq_push( lfq_t *q, pointer_t *node ) { + pointer_t tail; + pointer_t last; + pointer_t tmp; + + /* init node */ + node->split.next = NULL; + node->split.count = 0; + + /* set tmp to point to node */ + tmp.split.next = node; + tmp.split.count = 1; + + for(;;) { + /* snapshot tail */ + tail.concat = q->tail.concat; + /* 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; ??? */ + return; + } else { + /* snapshot last through tail */ + last.concat = (*tail.split.next).concat; + /* if tail is still consistant */ + if (tail.concat == 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; + } else { + /* try to swing tail to the next node */ + last.split.count = tail.split.count+1; + cas( &q->tail.split, tail.split, last.split ); + } + } + } + } + /* try to swing tail to the next node */ + tmp.split.count = tail.split.count+1; + cas( &q->tail.split, tail.split, tmp.split ); +} + +/* shift a node from the head of q */ +pointer_t* shift( lfq_t *q ) { + pointer_t head; + pointer_t tail; + pointer_t tmp; + pointer_t *node; + + for(;;) { + /* snapshot head */ + head.concat = q->head.concat; + /* return NULL if queue is empty */ + if (head.split.next == NULL) { return NULL; } /* TODO before snapshot using q-> ?? */ + /* snapshot tail */ + tail.concat = q->tail.concat; + /* if there is only one node in the queue */ + if ( tail.split.next == head.split.next ) { + /* tail points to NULL */ + tmp.split.next = NULL; + tmp.split.count = tail.split.count+1; + cas( &q->tail.split, tail.split, tmp.split ); + } else { + /* get the node ptr */ + node = (pointer_t *)head.split.next; + /* 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; + } + } + return node; +} + @@ -0,0 +1,63 @@ +/* + * File : lfq.h + * Author : Jérémy Zurcher <jeremy@asynk.ch> + * Date : 02/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 _LFQ_H_ +#define _LFQ_H_ + +# ifdef __cplusplus +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; +} lfq_t; + +/* initialize an empty lfq structure */ +void lfq_init( lfq_t *q ); + +/* push a node at the tail of q */ +void lfq_push( lfq_t *q, pointer_t *node ); + +/* shift a node from the head of q */ +pointer_t* shift( lfq_t *q ); + +# ifdef __cplusplus +} +# endif /* __cplusplus */ + +# endif /* _LFQ_H_ */ + diff --git a/lfq_cas.h b/lfq_cas.h new file mode 100644 index 0000000..a77e1ef --- /dev/null +++ b/lfq_cas.h @@ -0,0 +1,42 @@ +/* + * File : lfq_cas.h + * 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 "lfq.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/lfq_test.c b/lfq_test.c new file mode 100644 index 0000000..2502b8d --- /dev/null +++ b/lfq_test.c @@ -0,0 +1,102 @@ +/* + * File : lfq_test.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 "stddef.h" + +#include "lfq.h" +#include "lfq_cas.h" + +/** + * container_of - cast a member of a structure out to the containing structure + * @ptr: the pointer to the member. + * @type: the type of the container struct this is embedded in. + * @member: the name of the member within the struct. + * + */ +#define container_of(ptr, type, member) ({ \ + const typeof( ((type *)0)->member ) *__mptr = (ptr); \ + (type *)( (char *)__mptr - offsetof(type,member) );}) + +struct node { + int data; + pointer_t link; +}; + +int main(int argc, char *argv[]) { + pointer_t new; + pointer_t old; + pointer_t mem; + int ret; + + lfq_t q; + 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.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); + + /* init data */ + for(i=0; i<10; i++) data[i].data=i; + for(i=0; i<10; i++) printf("data[%d] :%d\n",i,data[i].data); + + /* check lfq */ + lfq_init( &q); + printf("shift %X\n",(unsigned int)shift( &q )); + for(i=0; i<10; i++) lfq_push( &q, &data[i].link ); + + it = (pointer_t*)q.head.split.next; + while(it!=NULL) { + printf("data : %d\n",container_of(it,struct node,link)->data); + it = (pointer_t*)it->split.next; + } + + for(i=0; i<5; i++) { + it = shift( &q ); + printf("shift %X %d\n",(unsigned int)it,container_of(it,struct node,link)->data); + } + it = (pointer_t*)q.head.split.next; + while(it!=NULL) { + printf("data : %d\n",container_of(it,struct node,link)->data); + it = (pointer_t*)it->split.next; + } + + return EXIT_SUCCESS; +} |