关于 多核 多读一写 无锁链表，请教

yiifburj

其他很多cpu读链表，单独一个cpu修改链表, 赋值操作为原子操作。

比如单向链表: a->c->NULL

负责修改的cpu插入b节点:
b->next = c;
smp_wb();//保证上面先执行
a->next = b;

其他的只读链表的cpu
cur = a;
cur = cur->next;
visit(cur); //可能为b
mp_read_barrier_depends();
cur = cur->next;//如果为b，是否一定为c
visit(cur);

请问， 这样有没有问题， 不知道链表可不可以看成是data dependency, 如果是，这样写，除非读不到b (a->next==c)，否则(a->next == b) b->next就一定是c。

多谢。


上面的代码是为了说明方便，实际上mp_read_barrier_depends() 定义为do{}while(0) ，读链表的操作为一个for循环
for(...)
    visit(cur);

yiifburj

没有问题，据说那款有问题的cpu早已停产了。

mnipxh

插入应该没问题，删除怎么办？

humjb_1983

看起来好像没问题~

yiifburj

mnipxh 发表于 2014-06-03 17:11
插入应该没问题，删除怎么办？

删除等一会再释放内存。
一个办法是
void wmbdd_barrier(void *unused)
{
        smp_mb();
}

smb_mb();
preempt_disable();
smp_call_function(wmbdd_barrier, NULL, 1);
preempt_enable();

然后再free, 正确性和可行性还不敢保证。

leiweigan1

回复 5# yiifburj
能具体点说明，无锁删除的方法吗？类似于rcu?


   

yiifburj

回复 6# leiweigan1


    on_each_cpu应该有问题， 帖子已更改， 因为on_each_cpu先在其他cpu上执行， 再在本cpu上执行， 应该顺序掉过来。

   双向或单项链表 a b c ， 删除b， 改变a->next和c->prev， 这样b就从链表上下来了， b指针指向不动， 然后smp_mb(); on_each_cpu(...);/* 不需要on_each_cpu, 因为本cpu已经有smp_mb()了， 可以去掉， 忘了那个函数的名字了， 见on_each_cpu的实现，*/ ， 本cpu加入smp_mb(); 表明 a， c里面的指针指向的更改此时此刻已经提交，其他cpu可见， 然后其他cpu执行smp_mb();表明其他cpu执行smp_mb之后的内存操作均在smp_mb后面完成， 这样其他cpu拿到的本cpu的数据就是更新之后的， b可以安全的free掉了。

只是推测， 还不敢保证， 另外可能有更简单的方法， rcu没有仔细研究过。

leiweigan1

回复 7# yiifburj
以单项链表为例，a-》b-》c，删除b，a->next = c，这不是原子操作， 有可能在赋值a-》next的时候，c已经被删除了吧？


   

yiifburj

回复 8# leiweigan1


    抱歉, 忘了来这里了, 这种方法只能同时一个人修改, 当同时多个人改的时候不能无锁, 但只是修改的人需要锁, 读的不需要.