Lock Less Single Linked List

| 分类 Kernel  | 标签 kernel  lock-less  list 

除了之前介绍的双向链表优先级链表 外,内核还提供了用原子操作实现的无锁单向链表 llist

llist 的结构和双向链表类似,但更简单:

1: struct llist_head {
2:     struct llist_node *first;
3: };
4: 
5: struct llist_node {
6:     struct llist_node *next;
7: };

如图:

llist.png

llist_add_batch 中展示了如何使用原子操作来实现 llist_add..

 1: /**
 2:  * llist_add_batch - add several linked entries in batch
 3:  * @new_first:  first entry in batch to be added
 4:  * @new_last:   last entry in batch to be added
 5:  * @head:   the head for your lock-less list
 6:  *
 7:  * Return whether list is empty before adding.
 8:  */
 9: bool llist_add_batch(struct llist_node *new_first, struct llist_node *new_last,
10:              struct llist_head *head)
11: {
12:     struct llist_node *first;
13: 
14:     do {
15:         new_last->next = first = ACCESS_ONCE(head->first);
16:     } while (cmpxchg(&head->first, first, new_first) != first);
17: 
18:     return !first;
19: }
20: EXPORT_SYMBOL_GPL(llist_add_batch);

无锁链表 (无锁队列) 的更多内容可参考: http://coolshell.cn/articles/8239.html


上一篇     下一篇