first version of single linked lock free queue

5 files changed, 328 insertions, 3 deletions

diff --git a/Makefile b/Makefile
index 63e4a7c..67d1f5c 100644
--- a/Makefile
+++ b/Makefile
@@ -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)
diff --git a/lfq.c b/lfq.c
new file mode 100644
index 0000000..b2bd3e3
--- /dev/null
+++ b/lfq.c
@@ -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;
+}
+
diff --git a/lfq.h b/lfq.h
new file mode 100644
index 0000000..2391112
--- /dev/null
+++ b/lfq.h
@@ -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;
+}