From 7d6c42c89447947de20e4b50390b6c3b3ee8ff9f Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= Date: Sat, 7 Nov 2009 19:21:49 +0100 Subject: cas and container tests --- Makefile | 18 +++++---- cas.c | 113 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ cas.h | 40 ------------------- cas_test.c | 62 ------------------------------ container_of.c | 68 ++++++++++++++++++++++++++++++++ lock_free_queue.c | 14 ++++++- 6 files changed, 205 insertions(+), 110 deletions(-) create mode 100644 cas.c delete mode 100644 cas.h delete mode 100644 cas_test.c create mode 100644 container_of.c diff --git a/Makefile b/Makefile index 2265400..27586c4 100644 --- a/Makefile +++ b/Makefile @@ -3,26 +3,30 @@ CC = gcc STD = _GNU_SOURCE CFLAGS = -DDEBUG -BIN = cas_test lock_free_queue_test lf_fifo_test +BIN = cas container_of lock_free_queue_test lf_fifo .c.o: $(CC) -c -Wall -I. $(CFLAGS) -D$(STD) $< all: $(BIN) -cas_test: cas_test.o - $(CC) cas_test.o -o cas_test +cas: cas.o + $(CC) -S cas.c + $(CC) cas.o -o cas + +container_of: container_of.o + $(CC) -S container_of.c + $(CC) container_of.o -o container_of 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_fifo_cas.h + + +lf_fifo.o: lf_fifo.h lf_cas.h lf_fifo_test: lf_fifo.o lf_fifo_test.o $(CC) lf_fifo.o lf_fifo_test.o -o lf_fifo_test -as: - $(CC) -S lf_fifo.c - clean: rm -f *~ *.o *.s core $(BIN) diff --git a/cas.c b/cas.c new file mode 100644 index 0000000..284c6dc --- /dev/null +++ b/cas.c @@ -0,0 +1,113 @@ +/* + * File : atomic.c + * 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 + +typedef struct split { + volatile void *ptr; + volatile unsigned int count; +} split_t; + +typedef union pointer { + split_t split; + volatile unsigned long long concat; +} 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 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; +} + +/* 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 split_t *mem, + volatile split_t old, + volatile split_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; +} + + +int test_compare_and_swap () { + pointer_t mem, old, new; + return compare_and_swap(&mem.concat, old.concat, new.concat); +} + +int test_cas () { + pointer_t mem, old, new; + return cas(&mem.split, old.split, new.split); +} + +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); + + 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 = cas(&mem.split, old.split, new.split); + printf("ret %d -> (%d,%X)\n", ret, mem.split.count, (unsigned int)mem.split.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.ptr); + + return 0; +} + diff --git a/cas.h b/cas.h deleted file mode 100644 index b04f7c3..0000000 --- a/cas.h +++ /dev/null @@ -1,40 +0,0 @@ -/* - * File : cas.c - * 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. - * - */ - -/* 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 deleted file mode 100644 index a2b92a6..0000000 --- a/cas_test.c +++ /dev/null @@ -1,62 +0,0 @@ -/* - * File : atomic.c - * 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 -#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/container_of.c b/container_of.c new file mode 100644 index 0000000..2c0be09 --- /dev/null +++ b/container_of.c @@ -0,0 +1,68 @@ +/* + * File : lfq_test.c + * 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 "stdio.h" +#include "stdlib.h" +#include "stddef.h" + +#define container_of(ptr, type, member) ({ \ + const typeof( ((type *)0)->member ) *__mptr = (ptr); \ + (type *)( (char *)__mptr - offsetof(type,member) );}) + +struct node { + int data; + int daat2; + int daat3; + int daat4; + int daaat4; +}; +#define OFFSET offsetof(struct node,daat3) +#define my_offset(ptr, type, member) ( { (type*)(((char*)ptr)-offsetof(type,member)); } ) + +struct node n; + +struct node* use_container_of() { + return container_of( &n.daat3, struct node, daat3); +} + +struct node* use_mine() { + return my_offset( &n.daat3, struct node, daat3); +/* return (struct node*)(((char*)&n.daat3)-OFFSET); */ +} + +struct node* use_struct(){ + return &n; +} + +int main(int argc, char *argv[]) { + + printf ("%X\n", (int)use_container_of()); + printf ("%X\n", (int)use_mine()); + printf ("%X\n", (int)use_struct()); + + return EXIT_SUCCESS; +} diff --git a/lock_free_queue.c b/lock_free_queue.c index 217fb0b..e3e128f 100644 --- a/lock_free_queue.c +++ b/lock_free_queue.c @@ -6,12 +6,24 @@ */ #include "stdlib.h" -#include "cas.h" #include "lock_free_queue.h" #ifdef DEBUG #include "stdio.h" #endif +/* 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; +} + void init( lfq_t *q ) { node_t *node = (node_t*)malloc(sizeof(node_t)); node->next.split.ptr = NULL; -- cgit v1.1-2-g2b99