• <div id="0yoao"><tr id="0yoao"></tr></div>
    <dl id="0yoao"></dl>
  • <sup id="0yoao"></sup>
    <div id="0yoao"><tr id="0yoao"></tr></div>
  • <div id="0yoao"><tr id="0yoao"></tr></div>
  • ?

    Linux内核同步机制之(六):Seqlock

    作者:linuxer 发布于:2015-9-9 11:55 分类:内核同步机制

    一、前言

    普通的spin lock对待reader和writer是一视同仁,RW spin lock给reader赋予了更高的优先级,那么有没有让writer优先的锁的机制呢?答案就是seqlock。本文主要描述linux kernel 4.0中的seqlock的机制,首先是seqlock的工作原理,如果想浅尝辄止,那么了解了概念性的东东就OK了,也就是第二章了,当然,?#19968;?#26159;推荐普通的驱动工程师了解seqlock的API,第三章给出了一个简单的例子,了解了这些,在驱动中(或者在其他内核模块)使用seqlock就可以易如反掌了。细节是魔鬼,概念性的东西需要天才的思考,不是说就代码实现的细节就无足轻重,如果想进入seqlock的内心世界,推荐阅读第四章seqlock的代码实现,这一章和cpu体系结构相关的内容我们选择了ARM64(呵呵~~要跟上时代的步伐)。最后一章是参考资料,如果觉得本文描述不清楚,可以参考这些经典文献,在无数不眠之夜,她们给我心灵的?#32771;?#20063;愿能够给读者带来快乐。

    二、工作原理

    1、overview

    seqlock这种锁机制是倾向writer thread,也就是说,除非有其他的writer thread进入了临界区,否则它会长驱直入,无论有多少的reader thread都不能阻挡writer的脚步。writer thread这么霸道,reader肿么办?对于seqlock,reader这一侧需要进行数据访问的过?#35752;?#26816;测是否有并发的writer thread操作,如果检测到并发的writer,那么重新read。通过不断的retry,直到reader thread在临界区的时候,没有任何的writer thread插入即可。这样的设计对reader而言不是很公平,特别是如果writer thread负荷比?#29616;?#30340;时候,reader thread可能会retry多次,从而导致reader thread这一侧性能的下降。

    总结一下seqlock的特点:临界区只允许一个writer thread进入,在没有writer thread的情况下,reader thread可以随意进入,也就是说reader不会阻挡reader。在临界区只有有reader thread的情况下,writer thread可以立?#35752;?#34892;,不会等待。

    2、writer thread的操作

    对于writer thread,获取seqlock操作如下:

    (1)获取锁(例如spin lock),该锁确保临界区只有一个writer进入。

    (2)sequence counter加一

    释放seqlock操作如下:

    (1)释放锁,允许其他writer thread进入临界区。

    (2)sequence counter加一(注意:不是减一哦,sequence counter是一个不断累加的counter)

    由上面的操作可知,如果临界区没有任何的writer thread,那么sequence counter是偶数(sequence counter初始化为0),如果临界区有一个writer thread(当然,也只能有一个),那么sequence counter是奇数。

    3、reader thread的操作如下:

    (1)获取sequence counter的值,如果是偶数,可以进入临界区,如果是奇数,那么等待writer离开临界区(sequence counter变成偶数)。进入临界区时候的sequence counter的值我们称之old sequence counter。

    (2)进入临界区,读取数据

    (3)获取sequence counter的值,如果等于old sequence counter,说明一切OK,否则回到step(1)

    4、?#35270;?#22330;景。一般而言,seqlock?#35270;?#20110;:

    (1)read操作比较频繁

    (2)write操作较少,但是性能要求高,不希望被reader thread阻挡(之所以要求write操作较少主要是考虑read side的性能)

    (3)数据类型比较简单,但是数据的访?#35270;?#26080;法利用原子操作来保护。我们举一个简单的例子来描述:假设需要保护的数据是一个链表,header--->A node--->B node--->C node--->null。reader thread遍历链表的过?#35752;校?#23558;B node的指针赋给了临时变量x,这时候,中断发生了,reader thread被preempt(注意,对于seqlock,reader并没有禁止抢占)。这样在其他cpu?#29616;?#34892;的writer thread有充足的时间释放B node的memory(注意:reader thread中的临时变量x还指向这段内存)。当read thread?#25351;?#25191;行,并通过x这个指针进行内存访问(例如试图通过next找到C node),悲剧发生了……

    三、API示例

    在kernel中,jiffies_64保存了从系?#31216;?#21160;以来的tick数目,对该数据的访问(以及其他jiffies相关数据)需要持有jiffies_lock这个seq lock。

    1、reader side代码如下:

    u64 get_jiffies_64(void)
    {

        do {
            seq = read_seqbegin(&jiffies_lock);
            ret = jiffies_64;
        } while (read_seqretry(&jiffies_lock, seq));
    }

    2、writer side代码如下:

    static void tick_do_update_jiffies64(ktime_t now)
    {
        write_seqlock(&jiffies_lock);

    临界区会修改jiffies_64等相关变量,具体代码略
        write_sequnlock(&jiffies_lock);
    }

    对照上面的代码,任何工程师都可以比着葫芦画瓢,使用seqlock来保护自己的临界区。当然,seqlock的接口API?#27973;?#20016;富,有兴趣的读者可以自?#24615;?#35835;seqlock.h文件。

    四、代码实现

    1、seq lock的定义

    typedef struct {
        struct seqcount seqcount;----------sequence counter
        spinlock_t lock;
    } seqlock_t;

    seq lock实际上就是spin lock + sequence counter。

    2、write_seqlock/write_sequnlock

    static inline void write_seqlock(seqlock_t *sl)
    {
        spin_lock(&sl->lock);

        sl->sequence++;
        smp_wmb();
    }

    唯一需要说明的是smp_wmb这个用于SMP场合下的写内存屏?#24076;?#23427;确保了编译器以及CPU都不会打乱sequence counter内存访问以及临界区内存访问的顺序(临界区的保护是依赖sequence counter的值,因此不能打乱其顺序)。write_sequnlock?#27973;?#31616;单,留给大?#26131;?#24049;看吧。

    3、read_seqbegin

    static inline unsigned read_seqbegin(const seqlock_t *sl)

        unsigned ret;

    repeat:
        ret = ACCESS_ONCE(sl->sequence); ---进入临界区之前,先要获取sequenc counter的快照
        if (unlikely(ret & 1)) { -----如果是奇数,说明有writer thread
            cpu_relax();
            goto repeat; ----如果有writer,那么先不要进入临界区,不断的polling sequenc counter
        }

        smp_rmb(); ---确保sequenc counter和临界区的内存访问顺序
        return ret;
    }

    如果有writer thread,read_seqbegin函数中会有一个不断polling sequenc counter,直到其变成偶数的过程,在这个过?#35752;校?#22914;果不加以控制,那么整体系统的性能会有损失(这里的性能指的是功耗和速度)。因此,在polling过?#35752;校?#26377;一个cpu_relax的调用,对于ARM64,其代码是:

    static inline void cpu_relax(void)
    {
            asm volatile("yield" ::: "memory");
    }

    yield指令用来告知?#24067;?#31995;统,本cpu?#29616;?#34892;的指令是polling操作,没有那么急迫,如果有任何的资源冲突,本cpu可以让出控制权。

    4、read_seqretry

    static inline unsigned read_seqretry(const seqlock_t *sl, unsigned start)
    {
        smp_rmb();---确保sequenc counter和临界区的内存访问顺序
        return unlikely(sl->sequence != start);
    }

    start参数就是进入临界区时候的sequenc counter的快照,比对当前退出临界区的sequenc counter,如果相等,说明没有writer进入打搅reader thread,那么可以愉快的离开临界区。

    还有一个比较有意思的逻辑问题:read_seqbegin为?#25105;?#36827;行奇偶判断?把一切都推到read_seqretry中进行判断不可以吗?也就是说,为何read_seqbegin要等到没有writer thread的情况下才进入临界区?#31185;?#23454;有writer thread也可以进入,反正在read_seqretry中可以进行奇偶以及相等判断,从而保证逻辑的正确性。当然,这样想也?#23884;?#30340;,?#36824;?#22312;performance上有欠?#20445;瑀eader在检测到有writer thread在临界区后,仍然放reader thread进入,可能会导致writer thread的一些额外的开销(cache miss),因此,最好的方法是在read_seqbegin中拦截。

    五、参考文献

    1、Understanding the Linux Kernel 3rd Edition

    2、Linux Kernel Development 3rd Edition

    3、Perfbook (https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html)

     

    原创文章,转发请注明出处。蜗窝科技

    标签: Seqlock

    评论:

    air_123456
    2019-02-08 18:24
    reader在检测到有writer thread在临界区后,仍然放reader thread进入,可能会导致writer thread的一些额外的开销(cache miss)     //这里为什么会导致writer thread的cache miss????
    flyfish
    2017-10-08 23:00
    现在在分析网络子系统,除了看代码之外还需要阅读大量的资料,譬如RFC,还要上班,加班,而工作又跟linux kernel没有太大关系,感觉真累
    wowo
    2017-10-10 16:35
    @flyfish:要有兴趣,?#19981;?#23601;不累了~@
    qnh
    2017-04-11 15:47
    write_sequnlock里:
    sequence counter加一确实应该在释放锁之前,需要这个锁来保护sequence counter
    fanzhang
    2017-07-30 10:06
    @qnh:嗯,对,这里有一个spin_lock,确保只有一个writer.
    will
    2016-08-29 19:18
    释放seqlock操作如下:

    (1)释放锁,允许其他writer thread进入临界区。

    (2)sequence counter加一(注意:不是减一哦,sequence counter是一个不断累加的counter)

    这个加一应该在释放锁之前吧。。???
    linuxer
    2016-08-30 08:35
    @will?#20309;文?#35273;得是加一在前呢?
    js_wawayu
    2016-05-25 14:55
    都是高手,佩服!
    维尼
    2015-09-17 11:13
    都3.10后内核都是64的 但是为什么大部分手机还是32的  
    楼主能 讲一下 怎么看android 手机 内核位数吗  我都是print一下 long类型
    linuxer
    2015-09-17 23:20
    @维尼:linux支持多种cpu,32位的、64位的、ARM、x86、powerPC什么的都支持,只要在编译内核的时候进行配置就OK了。
    维尼
    2015-09-18 08:57
    @linuxer?#21512;?#22312;市面是的手机貌似没有64位的内核啊
    hony
    2017-04-30 12:45
    @维尼:可以查看,cat /proc/cpuinfo
    schedule
    2015-09-13 18:36
    btrfs 目前看没啥前?#26223;。琹inuxer怎么看中了这个模块
    linuxer
    2015-09-14 09:02
    @schedule:原因有几个:
    1、我一直对文件系统比?#32454;行?#36259;,但是之前由于搞嵌入式,因此都是一些小打小闹的文件系统(例如yaffs),一直想了解一个功能比较强大的文件系统的运作机制。
    2、有一段时间我很关注内核的更新情况(现在都没有时间去了解了),看到btrfs更新?#27973;?#39057;?#20445;?#22788;于活跃期,这时候的模块有很多issue,可参与度比较高
    3、我简单的检索了一下资料,似乎btrfs有取代EXT4文件系统的趋势

    文件系统模块,schedule有什么推荐?
    schedule
    2015-09-14 09:18
    @linuxer:其实文件系统方面我就是?#22235;?#32423;别的。
    btrfs更新是很快,但是感觉好多东西都是在模仿ZFS,ZFS 10年前都有商?#25377;?#32626;了,btrfs概念炒的比较厉害,但是总是感觉像付不起的阿斗,有那么点不给力。一直以为红帽会在fedora发行版上作为默认的文件系统,结果XFS 突然上位。

    我觉得现在想在文件系统做投入,要么搞大(像Global FS),要么搞小(F2FS)。PC或者小型机级别的FS都被云概念炒翻了。当然btrfs很多概念很先进,学习是绝对值得的。
    linuxer
    2015-09-14 12:38
    @schedule:schedule,你是做哪一行的?虽然你?#30340;?#26159;?#22235;?#32423;别,?#36824;?#24863;觉对fs还是比较了解的,你是搞服务器(数据中心、云计算什么的)方向的吗?
    schedule
    2015-09-15 20:51
    @linuxer:呃呃呃,我是个医生。。。?#26377;?#23545;电?#24895;行?#36259;,没事就看看代码,
    linuxer
    2015-09-15 22:45
    @schedule:天?#27169;?#25105;已经晕倒......别和我说话,我想静静
    wowo
    2015-09-15 22:48
    @schedule:这才是真正的大神啊,我的偶像啊!把兴趣留给业余时间,不想当厨子的生物学?#20063;?#26159;好程序员啊!羡慕……
    schedule
    2015-09-15 23:25
    @wowo:比不了你们年轻人啊,周围的朋友有爱玩飞行器的,有玩汽车的,偏偏我?#19981;?#38745;心下来看看代码,就像看书似的,就是一种爱好。
    C
    2015-12-18 16:04
    @schedule:这位大哥使我想到一个澳大利亚的kernel hacker,他的正常职业是麻醉师,最早他帮内核写了一个Fair Scheduler,得到大量好评,然后Ingo眼红,跟着写了一个Complete Fair Scheduler, 然后两个scheduler互相PK?#27492;?#33021;进主线, 结果最后linus拍板说CFS进吧,问他为啥,他说,Fair Scheduler的哥们回?#20174;始?#22826;慢了。。。 别人又不是专职的,怎么可能和Ingo这些geek拼时间。
    wowo
    2015-12-18 16:07
    @C:哈哈,让我笑一会…
    tigger
    2015-12-21 10:06
    @schedule:医生啊。。。。。。
    哪个科室?
    听说牙科跟?#38745;?#31185;最挣钱
    lamaboy
    2017-04-14 14:22
    @tigger:其实我有个疑问,一直想清楚,医生在给人看病的时候,是不是像程序员一样先开点药试下,看看效果理想不?? 不理想找问题再试! 会不会是在这个过?#35752;?#25226;病情给耽误了??
    leefong.chen
    2015-09-11 16:14
    @linuxer 你在Linux maillist中提交patch了吗?模块比较多,想为Linux做点贡献,想找些志同道合的人一起分析、讨论内核某个模块,可否建立一个平台,?#20040;?#23478;讨论最新Linux。
    linuxer
    2015-09-11 18:31
    @leefong.chen:很遗憾,我也没有提?#36824;齪atch,如果想要提交patch,自身需要很强才可以,我感觉目前我的水平还不足以向内核提交patch(当然,那种外设驱动级别或者ARM下的某个machine级别的code之类的patch并不需要很高的能力,但是我没有兴趣),因此我现在就是想修炼内功,先把内核的几个基础模块(中断子系?#22330;?#26102;间子系?#22330;?#20869;核同步机制、进程管理、内存管理、I/O系统)研?#23458;赋?#20043;后,然后选定一个内核模块(例如现在比较活跃的btrfs),进行深入理解,思考,看看是否有机会增加其功能或者改善其性能。

    BTW,你想建立平台,让志同道合的人一起分析、讨论内核某个模块,想法当然好,?#36824;?#36825;样的人其实很少,就算是有,又忙于生计,其实是挺困难的一件事情,因此,我对这件事情不看好,很容易虎?#39134;?#23614;......
    leefong.chen
    2015-09-11 21:06
    @linuxer:中国就是这样,先要生计,再谈兴趣。什么时候学习IO系统,一起学?#21834;?/div>
    mj
    2015-09-11 07:09
    什么时候也出一篇关于RCU的文章,特别是update的时机,期待中。
    linuxer
    2015-09-11 09:04
    @mj:蜗窝当然不会忽略RCU这么强大的工具,关于RCU的文档已经开了个头,?#36824;齊CU比?#32454;?#26434;,估计需要酝酿一段时间,^_^

    发表评论:

    Copyright @ 2013-2015 蜗窝科技 All rights reserved. Powered by emlog
    连码三全中是什么
  • <div id="0yoao"><tr id="0yoao"></tr></div>
    <dl id="0yoao"></dl>
  • <sup id="0yoao"></sup>
    <div id="0yoao"><tr id="0yoao"></tr></div>
  • <div id="0yoao"><tr id="0yoao"></tr></div>
  • <div id="0yoao"><tr id="0yoao"></tr></div>
    <dl id="0yoao"></dl>
  • <sup id="0yoao"></sup>
    <div id="0yoao"><tr id="0yoao"></tr></div>
  • <div id="0yoao"><tr id="0yoao"></tr></div>