rcu链表综合实践

基础知识 

rcu-read copy update的缩写。和读写锁起到相同的效果。据说牛逼一点。对于我们普通程序员，要先学会使用，再探究其内部原理。

链表的数据结构：

struct list_head {struct list_head *next, *prev;
};

 还有一种：struct hlist_head，本文不做该链表的测试。

struct hlist_head {struct hlist_node *first;
};struct hlist_node {struct hlist_node *next, **pprev;
};

 涉及的文件：include\linux\rculist.h

初始化链表：INIT_LIST_HEAD_RCU

/** INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers* @list: list to be initialized** You should instead use INIT_LIST_HEAD() for normal initialization and* cleanup tasks, when readers have no access to the list being initialized.* However, if the list being initialized is visible to readers, you* need to keep the compiler from being too mischievous.*/
static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
{WRITE_ONCE(list->next, list);WRITE_ONCE(list->prev, list);
}

 添加节点list_add_rcu(插入到头节点后面)

/*** list_add_rcu - add a new entry to rcu-protected list* @new: new entry to be added* @head: list head to add it after** Insert a new entry after the specified head.* This is good for implementing stacks.** The caller must take whatever precautions are necessary* (such as holding appropriate locks) to avoid racing* with another list-mutation primitive, such as list_add_rcu()* or list_del_rcu(), running on this same list.* However, it is perfectly legal to run concurrently with* the _rcu list-traversal primitives, such as* list_for_each_entry_rcu().*/
static inline void list_add_rcu(struct list_head *new, struct list_head *head)
{__list_add_rcu(new, head, head->next);
}

 添加节点list_add_tail_rcu(插入到头节点前面，就是链尾) 

/*** list_add_tail_rcu - add a new entry to rcu-protected list* @new: new entry to be added* @head: list head to add it before** Insert a new entry before the specified head.* This is useful for implementing queues.** The caller must take whatever precautions are necessary* (such as holding appropriate locks) to avoid racing* with another list-mutation primitive, such as list_add_tail_rcu()* or list_del_rcu(), running on this same list.* However, it is perfectly legal to run concurrently with* the _rcu list-traversal primitives, such as* list_for_each_entry_rcu().*/
static inline void list_add_tail_rcu(struct list_head *new,struct list_head *head)
{__list_add_rcu(new, head->prev, head);
}

删除节点list_del_rcu

/*** list_del_rcu - deletes entry from list without re-initialization* @entry: the element to delete from the list.** Note: list_empty() on entry does not return true after this,* the entry is in an undefined state. It is useful for RCU based* lockfree traversal.** In particular, it means that we can not poison the forward* pointers that may still be used for walking the list.** The caller must take whatever precautions are necessary* (such as holding appropriate locks) to avoid racing* with another list-mutation primitive, such as list_del_rcu()* or list_add_rcu(), running on this same list.* However, it is perfectly legal to run concurrently with* the _rcu list-traversal primitives, such as* list_for_each_entry_rcu().** Note that the caller is not permitted to immediately free* the newly deleted entry.  Instead, either synchronize_rcu()* or call_rcu() must be used to defer freeing until an RCU* grace period has elapsed.*/
static inline void list_del_rcu(struct list_head *entry)
{__list_del_entry(entry);entry->prev = LIST_POISON2;
}

删除尾节点hlist_del_init_rcu 

/*** hlist_del_init_rcu - deletes entry from hash list with re-initialization* @n: the element to delete from the hash list.** Note: list_unhashed() on the node return true after this. It is* useful for RCU based read lockfree traversal if the writer side* must know if the list entry is still hashed or already unhashed.** In particular, it means that we can not poison the forward pointers* that may still be used for walking the hash list and we can only* zero the pprev pointer so list_unhashed() will return true after* this.** The caller must take whatever precautions are necessary (such as* holding appropriate locks) to avoid racing with another* list-mutation primitive, such as hlist_add_head_rcu() or* hlist_del_rcu(), running on this same list.  However, it is* perfectly legal to run concurrently with the _rcu list-traversal* primitives, such as hlist_for_each_entry_rcu().*/
static inline void hlist_del_init_rcu(struct hlist_node *n)
{if (!hlist_unhashed(n)) {__hlist_del(n);n->pprev = NULL;}
}

 替换list_replace_rcu：

/*** list_replace_rcu - replace old entry by new one* @old : the element to be replaced* @new : the new element to insert** The @old entry will be replaced with the @new entry atomically.* Note: @old should not be empty.*/
static inline void list_replace_rcu(struct list_head *old,struct list_head *new)
{new->next = old->next;new->prev = old->prev;rcu_assign_pointer(list_next_rcu(new->prev), new);new->next->prev = new;old->prev = LIST_POISON2;
}

计算长度

判空：list_empty

链表尾空时，返回值为1：链表不空时返回0。

        下面这段注释的大体含义就是，当你想用list_empty_rcu的时候，list_empty就足够满足需要了。

/** Why is there no list_empty_rcu()?  Because list_empty() serves this* purpose.  The list_empty() function fetches the RCU-protected pointer* and compares it to the address of the list head, but neither dereferences* this pointer itself nor provides this pointer to the caller.  Therefore,* it is not necessary to use rcu_dereference(), so that list_empty() can* be used anywhere you would want to use a list_empty_rcu().*/

获取节点对应的数据：list_entry_rcu

/*** list_entry_rcu - get the struct for this entry* @ptr:        the &struct list_head pointer.* @type:       the type of the struct this is embedded in.* @member:     the name of the list_head within the struct.** This primitive may safely run concurrently with the _rcu list-mutation* primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().*/
#define list_entry_rcu(ptr, type, member) \container_of(READ_ONCE(ptr), type, member)

遍历 list_for_each_entry_rcu：

/*** list_for_each_entry_rcu	-	iterate over rcu list of given type* @pos:	the type * to use as a loop cursor.* @head:	the head for your list.* @member:	the name of the list_head within the struct.* @cond:	optional lockdep expression if called from non-RCU protection.** This list-traversal primitive may safely run concurrently with* the _rcu list-mutation primitives such as list_add_rcu()* as long as the traversal is guarded by rcu_read_lock().*/
#define list_for_each_entry_rcu(pos, head, member, cond...)		\for (__list_check_rcu(dummy, ## cond, 0),			\pos = list_entry_rcu((head)->next, typeof(*pos), member);	\&pos->member != (head);					\pos = list_entry_rcu(pos->member.next, typeof(*pos), member))

链表综合实验代码

        测试内容包括添加、计算长度、遍历数据、删除节点、替换节点。最后在卸载函数中释放链表资源。

#include <linux/module.h>
#include <linux/init.h>
#include <linux/rculist.h>
#include <linux/slab.h>
#include <linux/vmalloc.h>#define _DEBUG_INFO
#ifdef _DEBUG_INFO#define DEBUG_INFO(format,...)	\printk(KERN_ERR"%s:%d -- "format"\n",\__func__,__LINE__,##__VA_ARGS__)
#else#define DEBUG_INFO(format,...)
#endifstruct rcu_private_data{struct list_head list;
};struct my_list_node{struct list_head node;int number;
};static int list_size(struct rcu_private_data *p){struct my_list_node *pos;struct list_head *head = &p->list;int count = 0;if(list_empty(&p->list)){DEBUG_INFO("list is empty");return 0;}else{DEBUG_INFO("list is not empty");}list_for_each_entry_rcu(pos,head,node){count++;}return count;
}//遍历链表
void show_list_nodes(struct rcu_private_data *p){struct my_list_node *pos;struct list_head *head = &p->list;if(list_empty(&p->list)){DEBUG_INFO("list is empty");return;}else{DEBUG_INFO("list is not empty");}list_for_each_entry_rcu(pos,head,node){DEBUG_INFO("pos->number = %d",pos->number);}
}//清空链表
void del_list_nodes(struct rcu_private_data *p){struct my_list_node *pos;struct list_head *head = &p->list;if(list_empty(&p->list)){DEBUG_INFO("list is empty");return;}else{DEBUG_INFO("list is not empty");}list_for_each_entry_rcu(pos,head,node){DEBUG_INFO("pos->number = %d\n",pos->number);vfree(pos);}
}struct rcu_private_data *prpd;static int __init ch02_init(void){int i = 0;static struct my_list_node * new[6];struct rcu_private_data *p = (struct rcu_private_data*)vmalloc(sizeof(struct rcu_private_data));prpd = p;INIT_LIST_HEAD_RCU(&p->list);DEBUG_INFO("list_empty(&p->list) = %d",list_empty(&p->list));for(i = 0;i < 5;i++){new[i] = (struct my_list_node*)vmalloc(sizeof(struct my_list_node));INIT_LIST_HEAD_RCU(&new[i]->node);new[i]->number = i;list_add_rcu(&new[i]->node,&p->list);}DEBUG_INFO("list_size = %d",list_size(p));//添加后的结果，应该是5 4 3 2 1//遍历链表：show_list_nodes(p);//删除链表节点 new[3];list_del_rcu(&new[3]->node);vfree(new[3]);DEBUG_INFO("list_size = %d",list_size(p));//遍历链表：show_list_nodes(p);//替换一个链表节点new[5] = (struct my_list_node*)vmalloc(sizeof(struct my_list_node));INIT_LIST_HEAD_RCU(&new[5]->node);new[5]->number = i;list_replace_rcu(&new[1]->node,&new[5]->node);vfree(new[1]);//遍历链表：show_list_nodes(p);DEBUG_INFO("init");return 0;
}static void __exit ch02_exit(void){del_list_nodes(prpd);vfree(prpd);DEBUG_INFO("exit");
}module_init(ch02_init);
module_exit(ch02_exit);
MODULE_LICENSE("GPL");

测试

加载模块

卸载模块 

小结