From beb67e73a3fd2a98d1f73b9b13dad5b19870864c Mon Sep 17 00:00:00 2001 From: Peizhao Ou Date: Fri, 20 Mar 2015 14:53:50 -0700 Subject: [PATCH] changes --- Makefile | 2 +- chase-lev-deque-bugfix/deque.c | 20 ++- chase-lev-deque-bugfix/interesting.txt | 4 +- chase-lev-deque-bugfix/result4.txt | 36 ++--- chase-lev-deque-bugfix/result5.txt | 190 ++----------------------- chase-lev-deque-bugfix/testcase5.c | 2 +- 6 files changed, 52 insertions(+), 202 deletions(-) diff --git a/Makefile b/Makefile index e89a8f2..e124a04 100644 --- a/Makefile +++ b/Makefile @@ -1,6 +1,6 @@ DIRS := barrier mcs-lock mpmc-queue spsc-queue spsc-bugfix linuxrwlocks \ dekker-fences chase-lev-deque ms-queue chase-lev-deque-bugfix \ - concurrent-hashmap seqlock spsc-example + concurrent-hashmap seqlock spsc-example spsc-queue-scfence .PHONY: $(DIRS) diff --git a/chase-lev-deque-bugfix/deque.c b/chase-lev-deque-bugfix/deque.c index 6328446..fc1e302 100644 --- a/chase-lev-deque-bugfix/deque.c +++ b/chase-lev-deque-bugfix/deque.c @@ -4,6 +4,16 @@ #include #include +Deque * create_size(int size) { + Deque * q = (Deque *) calloc(1, sizeof(Deque)); + Array * a = (Array *) calloc(1, sizeof(Array)+2*sizeof(atomic_int)); + atomic_store_explicit(&q->array, a, memory_order_relaxed); + atomic_store_explicit(&q->top, 0, memory_order_relaxed); + atomic_store_explicit(&q->bottom, 0, memory_order_relaxed); + atomic_store_explicit(&a->size, size, memory_order_relaxed); + return q; +} + Deque * create() { Deque * q = (Deque *) calloc(1, sizeof(Deque)); Array * a = (Array *) calloc(1, sizeof(Array)+2*sizeof(atomic_int)); @@ -19,21 +29,21 @@ int take(Deque *q) { Array *a = (Array *) atomic_load_explicit(&q->array, memory_order_relaxed); atomic_store_explicit(&q->bottom, b, memory_order_relaxed); atomic_thread_fence(memory_order_seq_cst); - size_t t = atomic_load_explicit(&q->top, memory_order_relaxed); + size_t t = atomic_load_explicit(&q->top, memory_order_acquire); // relaxed int x; if (t <= b) { /* Non-empty queue. */ x = atomic_load_explicit(&a->buffer[b % atomic_load_explicit(&a->size,memory_order_relaxed)], memory_order_relaxed); if (t == b) { /* Single last element in queue. */ - if (!atomic_compare_exchange_strong_explicit(&q->top, &t, t + 1, memory_order_seq_cst, memory_order_relaxed)) + if (!atomic_compare_exchange_strong_explicit(&q->top, &t, t + 1, memory_order_relaxed, memory_order_relaxed)) // seq_cst /* Failed race. */ x = EMPTY; - atomic_store_explicit(&q->bottom, b + 1, memory_order_relaxed); + atomic_store_explicit(&q->bottom, b + 1, memory_order_release); // relaxed } } else { /* Empty queue. */ x = EMPTY; - atomic_store_explicit(&q->bottom, b + 1, memory_order_relaxed); + atomic_store_explicit(&q->bottom, b + 1, memory_order_release); // relaxed } return x; } @@ -69,7 +79,7 @@ void push(Deque *q, int x) { } int steal(Deque *q) { - size_t t = atomic_load_explicit(&q->top, memory_order_acquire); + size_t t = atomic_load_explicit(&q->top, memory_order_relaxed); // acquire atomic_thread_fence(memory_order_seq_cst); size_t b = atomic_load_explicit(&q->bottom, memory_order_acquire); int x = EMPTY; diff --git a/chase-lev-deque-bugfix/interesting.txt b/chase-lev-deque-bugfix/interesting.txt index f708c17..48acef2 100644 --- a/chase-lev-deque-bugfix/interesting.txt +++ b/chase-lev-deque-bugfix/interesting.txt @@ -7,12 +7,12 @@ wildcard 5 -> memory_order_relaxed wildcard 6 -> memory_order_relaxed wildcard 7 -> memory_order_relaxed wildcard 8 -> memory_order_seq_cst -wildcard 9 -> memory_order_acquire +wildcard 9 -> memory_order_relaxed wildcard 10 -> memory_order_relaxed wildcard 11 -> memory_order_relaxed wildcard 12 -> memory_order_acquire wildcard 14 -> memory_order_release -wildcard 15 -> memory_order_release +wildcard 15 -> memory_order_relaxed wildcard 16 -> memory_order_relaxed wildcard 17 -> memory_order_relaxed wildcard 18 -> memory_order_relaxed diff --git a/chase-lev-deque-bugfix/result4.txt b/chase-lev-deque-bugfix/result4.txt index f29720b..29479ac 100644 --- a/chase-lev-deque-bugfix/result4.txt +++ b/chase-lev-deque-bugfix/result4.txt @@ -22,12 +22,12 @@ wildcard 21 -> memory_order_relaxed wildcard 22 -> memory_order_relaxed wildcard 23 -> memory_order_release wildcard 24 -> memory_order_relaxed -wildcard 25 -> memory_order_relaxed +wildcard 25 -> memory_order_acquire wildcard 26 -> memory_order_relaxed wildcard 27 -> memory_order_relaxed wildcard 28 -> memory_order_relaxed wildcard 29 -> memory_order_relaxed -wildcard 30 -> memory_order_release +wildcard 30 -> memory_order_relaxed wildcard 31 -> memory_order_release wildcard 32 -> memory_order_relaxed wildcard 33 -> memory_order_relaxed @@ -35,7 +35,7 @@ wildcard 34 -> memory_order_seq_cst wildcard 35 -> memory_order_acquire wildcard 36 -> memory_order_acquire wildcard 37 -> memory_order_relaxed -wildcard 38 -> memory_order_acquire +wildcard 38 -> memory_order_relaxed wildcard 39 -> memory_order_seq_cst Result 1: @@ -62,12 +62,12 @@ wildcard 21 -> memory_order_relaxed wildcard 22 -> memory_order_relaxed wildcard 23 -> memory_order_release wildcard 24 -> memory_order_relaxed -wildcard 25 -> memory_order_acquire +wildcard 25 -> memory_order_relaxed wildcard 26 -> memory_order_relaxed wildcard 27 -> memory_order_relaxed wildcard 28 -> memory_order_relaxed wildcard 29 -> memory_order_relaxed -wildcard 30 -> memory_order_relaxed +wildcard 30 -> memory_order_release wildcard 31 -> memory_order_release wildcard 32 -> memory_order_relaxed wildcard 33 -> memory_order_relaxed @@ -75,7 +75,7 @@ wildcard 34 -> memory_order_seq_cst wildcard 35 -> memory_order_acquire wildcard 36 -> memory_order_acquire wildcard 37 -> memory_order_relaxed -wildcard 38 -> memory_order_relaxed +wildcard 38 -> memory_order_acquire wildcard 39 -> memory_order_seq_cst Result 2: @@ -102,12 +102,12 @@ wildcard 21 -> memory_order_relaxed wildcard 22 -> memory_order_relaxed wildcard 23 -> memory_order_release wildcard 24 -> memory_order_relaxed -wildcard 25 -> memory_order_relaxed +wildcard 25 -> memory_order_acquire wildcard 26 -> memory_order_relaxed wildcard 27 -> memory_order_relaxed wildcard 28 -> memory_order_relaxed wildcard 29 -> memory_order_relaxed -wildcard 30 -> memory_order_release +wildcard 30 -> memory_order_relaxed wildcard 31 -> memory_order_release wildcard 32 -> memory_order_relaxed wildcard 33 -> memory_order_relaxed @@ -115,7 +115,7 @@ wildcard 34 -> memory_order_seq_cst wildcard 35 -> memory_order_acquire wildcard 36 -> memory_order_acquire wildcard 37 -> memory_order_relaxed -wildcard 38 -> memory_order_acquire +wildcard 38 -> memory_order_relaxed wildcard 39 -> memory_order_seq_cst Result 3: @@ -142,12 +142,12 @@ wildcard 21 -> memory_order_relaxed wildcard 22 -> memory_order_relaxed wildcard 23 -> memory_order_release wildcard 24 -> memory_order_relaxed -wildcard 25 -> memory_order_acquire +wildcard 25 -> memory_order_relaxed wildcard 26 -> memory_order_relaxed wildcard 27 -> memory_order_relaxed wildcard 28 -> memory_order_relaxed wildcard 29 -> memory_order_relaxed -wildcard 30 -> memory_order_relaxed +wildcard 30 -> memory_order_release wildcard 31 -> memory_order_release wildcard 32 -> memory_order_relaxed wildcard 33 -> memory_order_relaxed @@ -155,7 +155,7 @@ wildcard 34 -> memory_order_seq_cst wildcard 35 -> memory_order_acquire wildcard 36 -> memory_order_acquire wildcard 37 -> memory_order_relaxed -wildcard 38 -> memory_order_relaxed +wildcard 38 -> memory_order_acquire wildcard 39 -> memory_order_seq_cst Result 4: @@ -182,12 +182,12 @@ wildcard 21 -> memory_order_relaxed wildcard 22 -> memory_order_relaxed wildcard 23 -> memory_order_release wildcard 24 -> memory_order_relaxed -wildcard 25 -> memory_order_relaxed +wildcard 25 -> memory_order_acquire wildcard 26 -> memory_order_relaxed wildcard 27 -> memory_order_relaxed wildcard 28 -> memory_order_relaxed wildcard 29 -> memory_order_relaxed -wildcard 30 -> memory_order_release +wildcard 30 -> memory_order_relaxed wildcard 31 -> memory_order_release wildcard 32 -> memory_order_relaxed wildcard 33 -> memory_order_relaxed @@ -195,7 +195,7 @@ wildcard 34 -> memory_order_seq_cst wildcard 35 -> memory_order_acquire wildcard 36 -> memory_order_acquire wildcard 37 -> memory_order_relaxed -wildcard 38 -> memory_order_acquire +wildcard 38 -> memory_order_relaxed wildcard 39 -> memory_order_seq_cst Result 5: @@ -222,12 +222,12 @@ wildcard 21 -> memory_order_relaxed wildcard 22 -> memory_order_relaxed wildcard 23 -> memory_order_release wildcard 24 -> memory_order_relaxed -wildcard 25 -> memory_order_acquire +wildcard 25 -> memory_order_relaxed wildcard 26 -> memory_order_relaxed wildcard 27 -> memory_order_relaxed wildcard 28 -> memory_order_relaxed wildcard 29 -> memory_order_relaxed -wildcard 30 -> memory_order_relaxed +wildcard 30 -> memory_order_release wildcard 31 -> memory_order_release wildcard 32 -> memory_order_relaxed wildcard 33 -> memory_order_relaxed @@ -235,5 +235,5 @@ wildcard 34 -> memory_order_seq_cst wildcard 35 -> memory_order_acquire wildcard 36 -> memory_order_acquire wildcard 37 -> memory_order_relaxed -wildcard 38 -> memory_order_relaxed +wildcard 38 -> memory_order_acquire wildcard 39 -> memory_order_seq_cst diff --git a/chase-lev-deque-bugfix/result5.txt b/chase-lev-deque-bugfix/result5.txt index 1068f1e..d7eab19 100644 --- a/chase-lev-deque-bugfix/result5.txt +++ b/chase-lev-deque-bugfix/result5.txt @@ -5,93 +5,13 @@ wildcard 3 -> memory_order_relaxed wildcard 4 -> memory_order_relaxed wildcard 5 -> memory_order_relaxed wildcard 6 -> memory_order_relaxed -wildcard 7 -> memory_order_release -wildcard 8 -> memory_order_seq_cst -wildcard 9 -> memory_order_relaxed -wildcard 10 -> memory_order_relaxed -wildcard 11 -> memory_order_relaxed -wildcard 12 -> memory_order_acquire -wildcard 14 -> memory_order_relaxed -wildcard 15 -> memory_order_relaxed -wildcard 16 -> memory_order_relaxed -wildcard 17 -> memory_order_relaxed -wildcard 18 -> memory_order_relaxed -wildcard 19 -> memory_order_relaxed -wildcard 20 -> memory_order_relaxed -wildcard 21 -> memory_order_relaxed -wildcard 22 -> memory_order_relaxed -wildcard 23 -> memory_order_release -wildcard 24 -> memory_order_relaxed -wildcard 25 -> memory_order_acquire -wildcard 26 -> memory_order_relaxed -wildcard 27 -> memory_order_relaxed -wildcard 28 -> memory_order_relaxed -wildcard 29 -> memory_order_relaxed -wildcard 30 -> memory_order_relaxed -wildcard 31 -> memory_order_release -wildcard 32 -> memory_order_relaxed -wildcard 33 -> memory_order_relaxed -wildcard 34 -> memory_order_seq_cst -wildcard 35 -> memory_order_acquire -wildcard 36 -> memory_order_acquire -wildcard 37 -> memory_order_relaxed -wildcard 38 -> memory_order_relaxed -wildcard 39 -> memory_order_release - -Result 1: -wildcard 1 -> memory_order_relaxed -wildcard 2 -> memory_order_relaxed -wildcard 3 -> memory_order_relaxed -wildcard 4 -> memory_order_relaxed -wildcard 5 -> memory_order_relaxed -wildcard 6 -> memory_order_relaxed wildcard 7 -> memory_order_relaxed wildcard 8 -> memory_order_seq_cst -wildcard 9 -> memory_order_acquire -wildcard 10 -> memory_order_relaxed -wildcard 11 -> memory_order_relaxed -wildcard 12 -> memory_order_acquire -wildcard 14 -> memory_order_relaxed -wildcard 15 -> memory_order_relaxed -wildcard 16 -> memory_order_relaxed -wildcard 17 -> memory_order_relaxed -wildcard 18 -> memory_order_relaxed -wildcard 19 -> memory_order_relaxed -wildcard 20 -> memory_order_relaxed -wildcard 21 -> memory_order_relaxed -wildcard 22 -> memory_order_relaxed -wildcard 23 -> memory_order_release -wildcard 24 -> memory_order_relaxed -wildcard 25 -> memory_order_acquire -wildcard 26 -> memory_order_relaxed -wildcard 27 -> memory_order_relaxed -wildcard 28 -> memory_order_relaxed -wildcard 29 -> memory_order_relaxed -wildcard 30 -> memory_order_relaxed -wildcard 31 -> memory_order_release -wildcard 32 -> memory_order_relaxed -wildcard 33 -> memory_order_relaxed -wildcard 34 -> memory_order_seq_cst -wildcard 35 -> memory_order_acquire -wildcard 36 -> memory_order_acquire -wildcard 37 -> memory_order_relaxed -wildcard 38 -> memory_order_relaxed -wildcard 39 -> memory_order_release - -Result 2: -wildcard 1 -> memory_order_relaxed -wildcard 2 -> memory_order_relaxed -wildcard 3 -> memory_order_relaxed -wildcard 4 -> memory_order_relaxed -wildcard 5 -> memory_order_relaxed -wildcard 6 -> memory_order_relaxed -wildcard 7 -> memory_order_release -wildcard 8 -> memory_order_seq_cst wildcard 9 -> memory_order_relaxed wildcard 10 -> memory_order_relaxed wildcard 11 -> memory_order_relaxed wildcard 12 -> memory_order_acquire -wildcard 14 -> memory_order_relaxed +wildcard 14 -> memory_order_release wildcard 15 -> memory_order_relaxed wildcard 16 -> memory_order_relaxed wildcard 17 -> memory_order_relaxed @@ -116,9 +36,9 @@ wildcard 35 -> memory_order_acquire wildcard 36 -> memory_order_acquire wildcard 37 -> memory_order_relaxed wildcard 38 -> memory_order_acquire -wildcard 39 -> memory_order_release +wildcard 39 -> memory_order_seq_cst -Result 3: +Result 1: wildcard 1 -> memory_order_relaxed wildcard 2 -> memory_order_relaxed wildcard 3 -> memory_order_relaxed @@ -130,8 +50,8 @@ wildcard 8 -> memory_order_seq_cst wildcard 9 -> memory_order_acquire wildcard 10 -> memory_order_relaxed wildcard 11 -> memory_order_relaxed -wildcard 12 -> memory_order_acquire -wildcard 14 -> memory_order_relaxed +wildcard 12 -> memory_order_relaxed +wildcard 14 -> memory_order_release wildcard 15 -> memory_order_relaxed wildcard 16 -> memory_order_relaxed wildcard 17 -> memory_order_relaxed @@ -156,49 +76,9 @@ wildcard 35 -> memory_order_acquire wildcard 36 -> memory_order_acquire wildcard 37 -> memory_order_relaxed wildcard 38 -> memory_order_acquire -wildcard 39 -> memory_order_release +wildcard 39 -> memory_order_seq_cst -Result 4: -wildcard 1 -> memory_order_relaxed -wildcard 2 -> memory_order_relaxed -wildcard 3 -> memory_order_relaxed -wildcard 4 -> memory_order_relaxed -wildcard 5 -> memory_order_relaxed -wildcard 6 -> memory_order_relaxed -wildcard 7 -> memory_order_release -wildcard 8 -> memory_order_seq_cst -wildcard 9 -> memory_order_relaxed -wildcard 10 -> memory_order_relaxed -wildcard 11 -> memory_order_relaxed -wildcard 12 -> memory_order_relaxed -wildcard 14 -> memory_order_release -wildcard 15 -> memory_order_relaxed -wildcard 16 -> memory_order_relaxed -wildcard 17 -> memory_order_relaxed -wildcard 18 -> memory_order_relaxed -wildcard 19 -> memory_order_relaxed -wildcard 20 -> memory_order_relaxed -wildcard 21 -> memory_order_relaxed -wildcard 22 -> memory_order_relaxed -wildcard 23 -> memory_order_release -wildcard 24 -> memory_order_relaxed -wildcard 25 -> memory_order_acquire -wildcard 26 -> memory_order_relaxed -wildcard 27 -> memory_order_relaxed -wildcard 28 -> memory_order_relaxed -wildcard 29 -> memory_order_relaxed -wildcard 30 -> memory_order_relaxed -wildcard 31 -> memory_order_release -wildcard 32 -> memory_order_relaxed -wildcard 33 -> memory_order_relaxed -wildcard 34 -> memory_order_seq_cst -wildcard 35 -> memory_order_acquire -wildcard 36 -> memory_order_acquire -wildcard 37 -> memory_order_relaxed -wildcard 38 -> memory_order_relaxed -wildcard 39 -> memory_order_release - -Result 5: +Result 2: wildcard 1 -> memory_order_relaxed wildcard 2 -> memory_order_relaxed wildcard 3 -> memory_order_relaxed @@ -207,52 +87,12 @@ wildcard 5 -> memory_order_relaxed wildcard 6 -> memory_order_relaxed wildcard 7 -> memory_order_relaxed wildcard 8 -> memory_order_seq_cst -wildcard 9 -> memory_order_acquire -wildcard 10 -> memory_order_relaxed -wildcard 11 -> memory_order_relaxed -wildcard 12 -> memory_order_relaxed -wildcard 14 -> memory_order_release -wildcard 15 -> memory_order_relaxed -wildcard 16 -> memory_order_relaxed -wildcard 17 -> memory_order_relaxed -wildcard 18 -> memory_order_relaxed -wildcard 19 -> memory_order_relaxed -wildcard 20 -> memory_order_relaxed -wildcard 21 -> memory_order_relaxed -wildcard 22 -> memory_order_relaxed -wildcard 23 -> memory_order_release -wildcard 24 -> memory_order_relaxed -wildcard 25 -> memory_order_acquire -wildcard 26 -> memory_order_relaxed -wildcard 27 -> memory_order_relaxed -wildcard 28 -> memory_order_relaxed -wildcard 29 -> memory_order_relaxed -wildcard 30 -> memory_order_relaxed -wildcard 31 -> memory_order_release -wildcard 32 -> memory_order_relaxed -wildcard 33 -> memory_order_relaxed -wildcard 34 -> memory_order_seq_cst -wildcard 35 -> memory_order_acquire -wildcard 36 -> memory_order_acquire -wildcard 37 -> memory_order_relaxed -wildcard 38 -> memory_order_relaxed -wildcard 39 -> memory_order_release - -Result 6: -wildcard 1 -> memory_order_relaxed -wildcard 2 -> memory_order_relaxed -wildcard 3 -> memory_order_relaxed -wildcard 4 -> memory_order_relaxed -wildcard 5 -> memory_order_relaxed -wildcard 6 -> memory_order_relaxed -wildcard 7 -> memory_order_release -wildcard 8 -> memory_order_seq_cst wildcard 9 -> memory_order_relaxed wildcard 10 -> memory_order_relaxed wildcard 11 -> memory_order_relaxed wildcard 12 -> memory_order_relaxed wildcard 14 -> memory_order_release -wildcard 15 -> memory_order_relaxed +wildcard 15 -> memory_order_release wildcard 16 -> memory_order_relaxed wildcard 17 -> memory_order_relaxed wildcard 18 -> memory_order_relaxed @@ -276,9 +116,9 @@ wildcard 35 -> memory_order_acquire wildcard 36 -> memory_order_acquire wildcard 37 -> memory_order_relaxed wildcard 38 -> memory_order_acquire -wildcard 39 -> memory_order_relaxed +wildcard 39 -> memory_order_seq_cst -Result 7: +Result 3: wildcard 1 -> memory_order_relaxed wildcard 2 -> memory_order_relaxed wildcard 3 -> memory_order_relaxed @@ -287,7 +127,7 @@ wildcard 5 -> memory_order_relaxed wildcard 6 -> memory_order_relaxed wildcard 7 -> memory_order_relaxed wildcard 8 -> memory_order_seq_cst -wildcard 9 -> memory_order_acquire +wildcard 9 -> memory_order_relaxed wildcard 10 -> memory_order_relaxed wildcard 11 -> memory_order_relaxed wildcard 12 -> memory_order_relaxed @@ -302,12 +142,12 @@ wildcard 21 -> memory_order_relaxed wildcard 22 -> memory_order_relaxed wildcard 23 -> memory_order_release wildcard 24 -> memory_order_relaxed -wildcard 25 -> memory_order_relaxed +wildcard 25 -> memory_order_acquire wildcard 26 -> memory_order_relaxed wildcard 27 -> memory_order_relaxed wildcard 28 -> memory_order_relaxed wildcard 29 -> memory_order_relaxed -wildcard 30 -> memory_order_release +wildcard 30 -> memory_order_relaxed wildcard 31 -> memory_order_release wildcard 32 -> memory_order_relaxed wildcard 33 -> memory_order_relaxed @@ -315,5 +155,5 @@ wildcard 34 -> memory_order_seq_cst wildcard 35 -> memory_order_acquire wildcard 36 -> memory_order_acquire wildcard 37 -> memory_order_relaxed -wildcard 38 -> memory_order_acquire -wildcard 39 -> memory_order_release +wildcard 38 -> memory_order_relaxed +wildcard 39 -> memory_order_seq_cst diff --git a/chase-lev-deque-bugfix/testcase5.c b/chase-lev-deque-bugfix/testcase5.c index 0bbc6db..25716bc 100644 --- a/chase-lev-deque-bugfix/testcase5.c +++ b/chase-lev-deque-bugfix/testcase5.c @@ -13,7 +13,7 @@ int a; int b; int c; -/** Making w14 release */ +/** Making w14 & w15 release */ static void task1(void * param) { b=steal(q); -- 2.34.1