__sync_xxx 系列函数似乎我的理解有很大问题

zylthinking

回复 10# zhouzhenghui

测试代码你还要求那么多， 我已经成功了， 使用了一个全新的思路， 跟上面贴出来的完全不一样，
但无论实现复杂度还是性能来说应该都是成倍提升， 你的代码我没有自己读， 但整体感觉其实和我上面的思路差不多， 连出现的 bug 的表现都一样。

zhouzhenghui

代码乱的意思是贴出来的最好做些简化，至少调试需要的代码都去除掉，有助于别人阅读和借鉴。

方法的确不是唯一的，需要的话可以写出很多种，或者按个人的喜好，比如也可以如下写put和get，代码虽多了一些，但逻辑上一致了，也更容易理解：

1.     static struct lognode* head = &root;
   
2.     static struct lognode* tail = &root;
   
3.     static struct lognode end;
   
4. 
   
5.     void lognode_put(struct lognode* node)
   
6.     {
   
7.         struct lognode* last;
   
8.         struct lognode* before;
   
9.         do {
   
10.             last = tail;
    
11.             if (last == &end) {
    
12.                 __sync_val_compare_and_swap(&tail, last, head);
    
13.                 continue;
    
14.             }
    
15.             before = __sync_val_compare_and_swap(&(last->next), NULL, node);
    
16.             if (before != NULL)
    
17.                __sync_val_compare_and_swap(&tail, last, before);
    
18.         } while (before != NULL);
    
19. 
    
20.         __sync_val_compare_and_swap(&tail, last, node);
    
21.     }
    
22. 
    
23.     struct lognode* lognode_get()
    
24.     {
    
25.         struct lognode *node = head->next;
    
26.         if (node == NULL) return &end;
    
27. 
    
28.         __sync_val_compare_and_swap(&tail, head, node);
    
29.         head->next = NULL;
    
30.        
    
31.         lognode_put(&end);
    
32. 
    
33.         __sync_val_compare_and_swap(&tail, &end, head);
    
34. 
    
35.         return node;
    
36.     }
    

复制代码

通过增加了一个end节点作为分割消费者的原子化行为，代码仍然针对单个消费者。

zylthinking

zhouzhenghui 发表于 2013-08-18 21:01
代码乱的意思是贴出来的最好做些简化，至少调试需要的代码都去除掉，有助于别人阅读和借鉴。

方法的确不 ...

你这个照样有 bug， 根本通不过我的测试代码

zhouzhenghui

呵呵，我学乖测试过了，至少在这种场景是没问题的。错误在哪里也说不出来，注意这次队列的末指针是比较cur != &end

zylthinking

zhouzhenghui 发表于 2013-08-18 23:20
呵呵，我学乖测试过了，至少在这种场景是没问题的。错误在哪里也说不出来，注意这次队列的末指针是比较cur  ...

你自己试试嘛

1. 
   
2. 
   
3. #define _GNU_SOURCE
   
4. #include <stdlib.h>
   
5. #include <unistd.h>
   
6. #include <stddef.h>
   
7. #include <stdio.h>
   
8. #include <assert.h>
   
9. #include <pthread.h>
   
10. 
    
11. #define  rmb()  __asm__ volatile("lfence":::"memory")
    
12. #define  wmb()  __asm__ volatile("sfence":::"memory")
    
13. 
    
14. struct lognode {
    
15.     struct lognode* next;
    
16. };
    
17. 
    
18. 
    
19. static struct lognode root = {0};
    
20.     static struct lognode* head = &root;
    
21.     static struct lognode* tail = &root;
    
22.     static struct lognode end;
    
23. 
    
24. void lognode_put(struct lognode* node)
    
25. {
    
26.     struct lognode* last;
    
27.     struct lognode* before ;
    
28.     do {
    
29.         last = tail;
    
30.          before = __sync_val_compare_and_swap(&(last->next), NULL, node);
    
31.         if (before != NULL)
    
32.            __sync_val_compare_and_swap(&tail, last, before);
    
33.     } while (before != NULL);
    
34. 
    
35.     __sync_val_compare_and_swap(&tail, last, node);
    
36. }
    
37. 
    
38. #if 1
    
39. struct lognode* lognode_get()
    
40. {
    
41.     if (head == tail) return head;
    
42. 
    
43.     struct lognode *node = head->next;
    
44.     if (!node) return head;
    
45. 
    
46.     head->next = NULL;
    
47.     lognode_put(head);
    
48. 
    
49.     return node;
    
50. }
    
51. #else
    
52. struct lognode* lognode_get()
    
53. {
    
54.     struct lognode *node = head->next;
    
55.     if (node == NULL) return &end;
    
56. 
    
57.     __sync_val_compare_and_swap(&tail, head, node);
    
58.     head->next = NULL;
    
59. 
    
60.     lognode_put(&end);
    
61. 
    
62.     __sync_val_compare_and_swap(&tail, &end, head);
    
63. 
    
64.     return node;
    
65. }
    
66. #endif
    
67. 
    
68. #define nrp 10000
    
69. #define nrt 1
    
70. 
    
71. static volatile int run = 0;
    
72. static struct lognode* pool = NULL;
    
73. static volatile int indx = 0;
    
74. 
    
75. void* writer(void* any)
    
76. {
    
77.     while (run == 0) {
    
78.         usleep(100);
    
79.     }
    
80. 
    
81.     for (int i = 0; i < nrp; ++i) {
    
82.         int idx = __sync_fetch_and_add(&indx, 1);
    
83.         struct lognode* nodep = &pool[idx];
    
84.         nodep->next = NULL;
    
85.         lognode_put(nodep);
    
86.     }
    
87. 
    
88.     __sync_sub_and_fetch(&run, 1);
    
89.     return NULL;
    
90. }
    
91. 
    
92. 
    
93. int main(int argc, char** argv)
    
94. {
    
95.     int n = 0;
    
96.     for (int i = 0; i < nrt; ++i) {
    
97.         pthread_t tid;
    
98.         if(0 == pthread_create(&tid, NULL, writer, NULL)) {
    
99.             ++n;
    
100.             pthread_detach(tid);
     
101.         }
     
102.     }
     
103. 
     
104.     int nr = nrp * n;
     
105.     pool = (struct lognode *) malloc(sizeof(struct lognode) * nr);
     
106.     if (pool == 0) {
     
107.         printf("memory\n");
     
108.         return 0;
     
109.     }
     
110.     run = n;
     
111.     printf("run = %d\n", run);
     
112. 
     
113.     printf("%d writer, nr = %d\n", n, nr);
     
114.     time_t t1 = time(0);
     
115. 
     
116. 
     
117.     while (run > 0) {
     
118.         struct lognode* nodep = lognode_get();
     
119.         struct lognode* cur = nodep;
     
120.         while (cur != &end) {
     
121.             nodep = nodep->next;
     
122.             cur = nodep;
     
123.             --nr;
     
124.         }
     
125. 
     
126.         time_t t2 = time(0);
     
127.         if (t2 > t1 + 3) {
     
128.             printf("%d %d\n", nr, indx);
     
129.             t1 = t2;
     
130.         }
     
131.     }
     
132. 
     
133.     struct lognode* nodep = lognode_get();
     
134.     struct lognode* cur = nodep;
     
135.     while (cur != &end) {
     
136.         nodep = nodep->next;
     
137.         cur = nodep;
     
138.         --nr;
     
139.     }
     
140. 
     
141.     printf("done %d\n", nr);
     
142.     return 0;
     
143. }
     

复制代码

根据 #if 不同定义编译两次各自运行：
zylthinking@linux:~/code/test$ gcc a.c -lpthread -std=c99 -ggdb
zylthinking@linux:~/code/test$ ./a.out
run = 1
1 writer, nr = 10000
done 3981
zylthinking@linux:~/code/test$ gcc a.c -lpthread -std=c99 -ggdb
zylthinking@linux:~/code/test$ ./a.out
run = 1
1 writer, nr = 10000
Segmentation fault (core dumped)

zylthinking

无论采用你最新的代码还是你之前说应该怎么做的代码， 我都有测试， 都通不过

zhouzhenghui

贴我的测试代码，简化了，避免不必要的复杂性

1. #include <assert.h>
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <unistd.h>
   
5. #include <pthread.h>
   
6. 
   
7. struct lognode {
   
8.     int value;
   
9.     struct lognode* next;
   
10. };
    
11. 
    
12. #define nrp 10000
    
13. #define nrt 50
    
14. 
    
15.     static struct lognode root = {0};
    
16.     static struct lognode* head = &root;
    
17.     static struct lognode* tail = &root;
    
18.     static struct lognode end;
    
19.     static int sum = 0;
    
20.     static volatile int run;
    
21. 
    
22.     void lognode_put(struct lognode* node)
    
23.     {
    
24.         struct lognode* last;
    
25.         struct lognode* before;
    
26.         do {
    
27.             last = tail;
    
28.             if (last == &end) {
    
29.                 __sync_val_compare_and_swap(&tail, last, head);
    
30.                 continue;
    
31.             }
    
32.             before = __sync_val_compare_and_swap(&(last->next), NULL, node);
    
33.             if (before != NULL)
    
34.                __sync_val_compare_and_swap(&tail, last, before);
    
35.         } while (before != NULL);
    
36. 
    
37.         __sync_val_compare_and_swap(&tail, last, node);
    
38.     }
    
39. 
    
40.     struct lognode* lognode_get()
    
41.     {
    
42.         struct lognode *node = head->next;
    
43.         if (node == NULL) return &end;
    
44. 
    
45.         __sync_val_compare_and_swap(&tail, head, node);
    
46.         head->next = NULL;
    
47.        
    
48.         lognode_put(&end);
    
49. 
    
50.         __sync_val_compare_and_swap(&tail, &end, head);
    
51. 
    
52.         return node;
    
53.     }
    
54. 
    
55. void* writer(void* any)
    
56. {
    
57.     while (run == 0) {
    
58.         usleep(100);
    
59.     }
    
60. 
    
61.     for (int i = 0; i < nrp; ++i) {
    
62.         struct lognode* nodep = malloc(sizeof(struct lognode));
    
63.         int value = rand();
    
64.         __sync_fetch_and_add(&sum, value);
    
65.         nodep->value = value;
    
66.         nodep->next = NULL;
    
67.         lognode_put(nodep);
    
68.     }
    
69. 
    
70.     __sync_sub_and_fetch(&run, 1);
    
71.     return NULL;
    
72. }
    
73. 
    
74. int main(int argc, char** argv)
    
75. {
    
76. 
    
77.     int n = 0;
    
78.     for (int i = 0; i < nrt; ++i) {
    
79.         pthread_t tid;
    
80.         if(0 == pthread_create(&tid, NULL, writer, NULL)) {
    
81.             ++n;
    
82.             pthread_detach(tid);
    
83.         }
    
84.     }
    
85.     run = n;
    
86. 
    
87.     while (run > 0) {
    
88.         struct lognode* nodep = lognode_get();
    
89.         while (nodep != &end) {
    
90.             __sync_sub_and_fetch(&sum, nodep->value);
    
91.             nodep = nodep->next;
    
92.         }
    
93.     }
    
94. 
    
95.     struct lognode* nodep = lognode_get();
    
96.     while (nodep != &end) {
    
97.         __sync_sub_and_fetch(&sum, nodep->value);
    
98.         nodep = nodep->next;
    
99.     }
    
100. 
     
101.     assert(sum == 0);
     
102.     printf("success\n");
     
103. 
     
104. }
     
105. 
     

复制代码

zylthinking

回复 17# zhouzhenghui

那应该是你走运了
我原样粘过去运行了一把：
zylthinking@linux:~/code/test$ gcc a.c -lpthread -std=c99 -ggdb
a.c: In function ‘writer’:
a.c:58:9: warning: implicit declaration of function ‘usleep’ [-Wimplicit-function-declaration]
zylthinking@linux:~/code/test$ ./a.out
Segmentation fault (core dumped)

zylthinking

Program received signal SIGSEGV, Segmentation fault.
0x00000000004009b2 in main (argc=1, argv=0x7fffffffdf6 at a.c:90
90                    __sync_sub_and_fetch(&sum, nodep->value);
(gdb)

zhouzhenghui

虽然我的测试显示没有问题，但我也承认get函数仍然存在不稳定逻辑，并且代码中稍微偷了一下懒，这样逻辑清晰一些。

因为我的测试都通过，我也没有看出导致问题的地方，希望看到更多负面测试结果。有问题也是有可能的，说明了设计并行程序的复杂性，同时只有在特殊情况下才可能复用静态数据。