谁能帮我解释这个无锁链表是怎么实现的，帮我分析一下

finyren

1. 
   
2. /*
   
3. * Copyright (c) 2013, zylthinking
   
4. * All rights reserved.
   
5. *
   
6. * Redistribution and use in source and binary forms, with or without modification,
   
7. * are permitted provided that the following conditions are met:
   
8. *
   
9. * 1. Redistributions of source code must retain the above copyright notice,
   
10. *    this list of conditions and the following disclaimer.
    
11. * 2. Redistributions in binary form must reproduce the above copyright notice,
    
12. *    this list of conditions and the following disclaimer in the documentation and/or
    
13. *    other materials provided with the distribution.
    
14. *
    
15. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    
16. * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
    
17. * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
    
18. * IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
    
19. * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
    
20. * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
    
21. * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
    
22. * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
    
23. * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    
24. */
    
25. 
    
26. #ifndef lkf_h
    
27. #define lkf_h
    
28. 
    
29. struct lkf_node {
    
30.     struct lkf_node* next;
    
31. };
    
32. 
    
33. struct lkf_list {
    
34.     struct lkf_node root;
    
35.     struct lkf_node** tail;
    
36. };
    
37. 
    
38. 
    
39. #define LKF_INIT(name) {.root = {NULL}, .tail = &(name.root.next)}
    
40. #define LKF_LIST(name) \
    
41. struct lkf_list name = LKF_INIT(name)
    
42. 
    
43. #define INIT_LKF(name) \
    
44. do { \
    
45.     name->root.next = NULL; \
    
46.     name->tail = &(name->root.next); \
    
47. } while (0)
    
48. 
    
49. static inline void lkf_node_put(struct lkf_list* list, struct lkf_node* node)
    
50. {
    
51.     struct lkf_node** ptr = __sync_lock_test_and_set(&(list->tail), &(node->next));
    
52.     *ptr = node;
    
53. }
    
54. 
    
55. static inline struct lkf_node* lkf_node_get_one(struct lkf_list* list)
    
56. {
    
57.     struct lkf_node* head = __sync_lock_test_and_set(&(list->root.next), NULL);
    
58.     if (head == NULL) {
    
59.         return NULL;
    
60.     }
    
61. 
    
62.     struct lkf_node* next = head->next;
    
63.     if (next != NULL) {
    
64.         list->root.next = next;
    
65.         head->next = head;
    
66.         return head;
    
67.     }
    
68. 
    
69.     int b = __sync_bool_compare_and_swap(&(list->tail), &(head->next), &(list->root.next));
    
70.     if (b) {
    
71.         head->next = head;
    
72.         return head;
    
73.     }
    
74. 
    
75.     list->root.next = head;
    
76.     return NULL;
    
77. }
    
78. 
    
79. static inline struct lkf_node* lkf_node_get(struct lkf_list* list)
    
80. {
    
81.     struct lkf_node* ptr = __sync_lock_test_and_set(&(list->root.next), NULL);
    
82.     if (ptr == NULL) {
    
83.         return NULL;
    
84.     }
    
85. 
    
86.     struct lkf_node** last = __sync_lock_test_and_set(&(list->tail), &(list->root.next));
    
87.     *last = ptr;
    
88.     return *last;
    
89. }
    
90. 
    
91. static inline struct lkf_node* lkf_node_next(struct lkf_node* node)
    
92. {
    
93.     struct lkf_node* ptr = node->next;
    
94.     if (ptr == NULL || ptr->next == NULL) {
    
95.         return NULL;
    
96.     }
    
97. 
    
98.     if (ptr == node) {
    
99.         return ptr;
    
100.     }
     
101. 
     
102.     node->next = ptr->next;
     
103.     ptr->next = NULL;
     
104.     return ptr;
     
105. }
     
106. 
     
107. #endif
     

复制代码

以下是测试代码

1. 
   
2. #define _GNU_SOURCE
   
3. #include <stdlib.h>
   
4. #include <unistd.h>
   
5. #include <stdio.h>
   
6. #include <pthread.h>
   
7. 
   
8. #include "lkf.h"
   
9. static LKF_LIST(list);
   
10. 
    
11. #define nrp 1000
    
12. #define nrt 500
    
13. 
    
14. static int run = 0;
    
15. static struct lkf_node* pool = NULL;
    
16. static int indx = 0;
    
17. static int nr = 0;
    
18. 
    
19. void* writer(void* any)
    
20. {
    
21.     while (run == 0) {
    
22.         usleep(100);
    
23.     }
    
24. 
    
25.     for (int i = 0; i < nrp; ++i) {
    
26.         int idx = __sync_fetch_and_add(&indx, 1);
    
27.         struct lkf_node* nodep = &pool[idx];
    
28.         nodep->next = NULL;
    
29.         lkf_node_put(&list, nodep);
    
30.     }
    
31. 
    
32.     __sync_sub_and_fetch(&run, 1);
    
33.     printf("writer exits\n");
    
34.     return NULL;
    
35. }
    
36. 
    
37. void* reader(void* any)
    
38. {
    
39.     while (run == 0) {
    
40.         usleep(100);
    
41.     }
    
42. 
    
43.     while (nr > 0) {
    
44.         struct lkf_node* nodep = lkf_node_get(&list);
    
45.         if (nodep == NULL) {
    
46.             continue;
    
47.         }
    
48. 
    
49.         __sync_sub_and_fetch(&nr, 1);
    
50.         struct lkf_node* cur = NULL;
    
51.         do {
    
52.             cur = lkf_node_next(nodep);
    
53.             if (cur == nodep) {
    
54.                 break;
    
55.             }
    
56. 
    
57.             if (cur != NULL) {
    
58.                 __sync_sub_and_fetch(&nr, 1);
    
59.             }
    
60.         } while (1);
    
61.     }
    
62. 
    
63.     printf("reader exit\n");
    
64.     return NULL;
    
65. }
    
66. 
    
67. void* reader2(void* any)
    
68. {
    
69.     while (run == 0) {
    
70.         usleep(100);
    
71.     }
    
72. 
    
73.     while (nr > 0) {
    
74.         struct lkf_node* nodep = lkf_node_get_one(&list);
    
75.         if (nodep == NULL) {
    
76.             continue;
    
77.         }
    
78. 
    
79.         __sync_sub_and_fetch(&nr, 1);
    
80.     }
    
81.     printf("reader2 exit\n");
    
82.     return NULL;
    
83. }
    
84. 
    
85. int main(int argc, char** argv)
    
86. {
    
87.     int n = 0;
    
88.     for (int i = 0; i < nrt; ++i) {
    
89.         pthread_t tid;
    
90.         if(0 == pthread_create(&tid, NULL, writer, NULL)) {
    
91.             ++n;
    
92.             pthread_detach(tid);
    
93.         }
    
94.     }
    
95. 
    
96.     nr = nrp * n;
    
97.     pool = (struct lkf_node *) malloc(sizeof(struct lkf_node) * nr);
    
98.     if (pool == 0) {
    
99.         printf("memory\n");
    
100.         return 0;
     
101.     }
     
102. 
     
103.     int readers = 0;
     
104.     for (int i = 0; i < 500; ++i) {
     
105.         pthread_t tid;
     
106.         if(0 == pthread_create(&tid, NULL, reader2, NULL)) {
     
107.             ++readers;
     
108.             pthread_detach(tid);
     
109.         }
     
110.     }
     
111. 
     
112.     printf("run = %d\n", run);
     
113.     printf("%d writer, %d reader, nr = %d\n", n, readers + 1, nr);
     
114.     run = n;
     
115. 
     
116.     time_t t1 = time(0);
     
117.     if (nr > 0) {
     
118.         //reader(0);
     
119.     }
     
120. 
     
121.     while (1) {
     
122.         usleep(10);
     
123.         struct lkf_node* nodep = 0;//lkf_node_get(&list);
     
124.         time_t t2 = time(0);
     
125.         if (t2 > t1 + 3) {
     
126.             printf("%d %d %p\n", nr, indx, nodep);
     
127.             t1 = t2;
     
128.         }
     
129.     }
     
130.     return 0;
     
131. }
     

复制代码

hellioncu

@zylthinking   

Dannysd

给你个简短的测试代码吧

1. #include <stdio.h>
   
2. #include <pthread.h>
   
3. #include <stdlib.h>
   
4. 
   
5. static int count = 0;
   
6. 
   
7. 
   
8. void *test_func(void *arg)
   
9. {
   
10.         int i=0;
    
11.         for(i=0;i<20000;++i){
    
12.                 __sync_fetch_and_add(&count,1);
    
13.         }
    
14.         return NULL;
    
15. }
    
16. 
    
17. int main(int argc, const char *argv[])
    
18. {
    
19.         pthread_t id[20];
    
20.         int i = 0;
    
21. 
    
22.         for(i=0;i<20;++i){
    
23.                 pthread_create(&id[i],NULL,test_func,NULL);
    
24.         }
    
25. 
    
26.         for(i=0;i<20;++i){
    
27.                 pthread_join(id[i],NULL);
    
28.         }
    
29. 
    
30.         printf("%d\n",count);
    
31.         return 0;
    
32. }

复制代码

Dannysd

https://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Atomic-Builtins.html

shang2010

无锁链表安全吗？？

cobras

据说，原子操作在大量并发的情况下对整个系统的运行效率影响非常大。不知是真是假。

zhaohongjian000

cobras 发表于 2014-11-21 06:49
据说，原子操作在大量并发的情况下对整个系统的运行效率影响非常大。不知是真是假。

原子操作就是实现锁的基本工具。楼主贴的代码，实际是实现了自旋锁。我见过几乎所有的所谓“无锁”数据结构，都不过
是自己实现了自旋锁。

自旋锁在无法取得锁的时候会忙等，冲突几率大的时候白白消耗CPU。

zylthinking

zhaohongjian000 发表于 2014-11-21 09:33
原子操作就是实现锁的基本工具。楼主贴的代码，实际是实现了自旋锁。我见过几乎所有的所谓“无锁”数据 ...

我可没有自旋啊， 我只不过返回空， 你愿不愿意自旋， 就看你愿不愿意接着再调用一次了； 和我有什么关系， 你自己去干其他的我也没有拦着你啊
这玩意最大的毛病在于读 lkf_get_one 的时候实际是单线程的， 而且， 似乎可以实现的更好些， 但当时脑子一根筋了

zhaohongjian000

zylthinking 发表于 2014-11-21 12:23
我可没有自旋啊， 我只不过返回空， 你愿不愿意自旋， 就看你愿不愿意接着再调用一次了； 和我有什么关 ...

自旋锁也可以trylock呀，比如pthread_spin_trylock。当然，trylock就不是忙等了。

zylthinking

zhaohongjian000 发表于 2014-11-21 15:04
自旋锁也可以trylock呀，比如pthread_spin_trylock。当然，trylock就不是忙等了。

那你干脆说所有的无锁结构不过都实现了锁得了， 反正就算是 mutex, 还有 pthread_mutex_try_lock 呢；
可以用 spin_lock  实现 读、写 不互斥？