From cec79cfe07dea7f730f0f0c928a34689f2119809 Mon Sep 17 00:00:00 2001 From: Peizhao Ou Date: Wed, 6 Aug 2014 18:39:41 -0700 Subject: [PATCH] add seqlock --- Makefile | 2 +- benchmarks.mk | 3 +- build.sh | 11 ++++++ doc/scanalysis_result.txt | 11 ++++++ seqlock/Makefile | 9 +++++ seqlock/seqlock | Bin 0 -> 49421 bytes seqlock/seqlock.c | 75 ++++++++++++++++++++++++++++++++++++++ 7 files changed, 109 insertions(+), 2 deletions(-) create mode 100755 build.sh create mode 100644 doc/scanalysis_result.txt create mode 100644 seqlock/Makefile create mode 100755 seqlock/seqlock create mode 100644 seqlock/seqlock.c diff --git a/Makefile b/Makefile index e988a49..f47efe7 100644 --- a/Makefile +++ b/Makefile @@ -1,5 +1,5 @@ DIRS := barrier mcs-lock mpmc-queue spsc-queue spsc-bugfix linuxrwlocks \ - dekker-fences chase-lev-deque ms-queue chase-lev-deque-bugfix + dekker-fences chase-lev-deque ms-queue chase-lev-deque-bugfix seqlock .PHONY: $(DIRS) diff --git a/benchmarks.mk b/benchmarks.mk index 7f82f92..4f0031f 100644 --- a/benchmarks.mk +++ b/benchmarks.mk @@ -8,7 +8,8 @@ UNAME = $(shell uname) LIB_NAME = model LIB_SO = lib$(LIB_NAME).so -BASE = ../.. +#BASE = ../.. +BASE = $(CDS_DIR) INCLUDE = -I$(BASE)/include -I../include # C preprocessor flags diff --git a/build.sh b/build.sh new file mode 100755 index 0000000..d78b2e0 --- /dev/null +++ b/build.sh @@ -0,0 +1,11 @@ +#!/bin/bash + +CHECKER_DIR=~/model-checker-priv/model-checker-priv + +if [ -z $1 ] ; then + echo "Use default CDS checker directory" +else + CHECKER_DIR=$1 +fi + +make CDS_DIR=$CHECKER_DIR diff --git a/doc/scanalysis_result.txt b/doc/scanalysis_result.txt new file mode 100644 index 0000000..c93472a --- /dev/null +++ b/doc/scanalysis_result.txt @@ -0,0 +1,11 @@ +Chase-Lev (buggy) 65 24 0.0021 0.13 68 3.2*10^-5 +Chase-Lev (correct) 49 1 0.0016 0.06 75 3.2*10^-5 +SPSC (buggy) 10 2 0.0002 0.03 26 1.7*10^-5 +SPSC (correct) 15 0 0.0004 0.03 29 2.7*10^-5 +Barrier 7 0 0.0002 0.01 23 2.9*10^-5 +Dekker 2313 0 0.0793 10.19 52 3.4*10^-5 +MCS lock 12609 0 0.3409 4.85 65 2.7*10^-5 +MPMC queue 11306 +M&S queue 114 +Linux RW lock 1348 +Seqlock 9124 0 0.4895 3.818 38 5.3*10^-5 diff --git a/seqlock/Makefile b/seqlock/Makefile new file mode 100644 index 0000000..98375f9 --- /dev/null +++ b/seqlock/Makefile @@ -0,0 +1,9 @@ +include ../benchmarks.mk + +all: seqlock + +seqlock: seqlock.c + $(CXX) -o $@ $< $(CXXFLAGS) $(LDFLAGS) + +clean: + rm -f seqlock diff --git a/seqlock/seqlock b/seqlock/seqlock new file mode 100755 index 0000000000000000000000000000000000000000..32a01ab25181c3da5c460991f6e76a3d2e526a6b GIT binary patch literal 49421 zcmeHwd3+Yt_4h1K$dIr+5Xb@uksXl$VG&#tAsRF&Wl>xovOJJL7D%2XV4>pH8Y33m zt5#{n-MUn*xM3(*wRL^nP;5m-1<{IYaVziloVjOao|$<<{r%q0`&TEQnS1Bl?>YC} zbI(2Z&hkvoEh#(B&~;5VLpxfdv$Z{nm}DO{&ANk66>W;vRV&hlYeTdyprm0h;u1>j zoTU4dXh|)FGm%EHPcdx56r+eUk`A!Rnxvv3rBt806{)P9uFADfCDpWiCJ-O#y6+%9 zMY@19l3uLzSg%syqf_F`AINZ|3pgWbhf+*ZX&<$X_PI*lT%!nQbY4V>Hl2@dN?6)v zeUPZ4e7C-QinNF`l5Vicnxw+_Gw_j~|LG=r&Q|rMvWunkmsB-Z8(UjbF?r(H+Nv?N zHTBKQ$1I;RdCcUA1x*bFh1~8a6d~;KC(UD(#E#TGq;nta6oO|8M1uG{{cwx+SD<4_&d5<@j z%^z_0iSKt*EgXE)qwin7vd=qzC|GlIU!(r&ywMvL558$}*J-cMh`n*!iWy7(G_B;d zPrCPc@5aK4?VrB&{QEaPJn6{mpRFF%(e3bSGVhpw`*-J$${qgBUzXOL^7|{6ebBXG zy{Gy>_EJ!K2dJ91G6nsYDd^on&&TfHXk6v{i8$}0hu3=}%EI(HF$MkM6!fJj=x3#% zAD)7KOA7k;Dd?r#t{&RHK1D#d+azSEU8_~Rlal9vAFOrPB3VUDYE}iGz}0%ev)1M> zV2X^RTR`uvWoj39FH%T583Q>{?eqPs6VXJCyg`$r`N^-XK zEMm$=ML!Do{E&A2R@vuv)vl2Wf0Ck~qx|7FivGE(ceoE*o!cVcu znud5<*H9I&MF`bmu|;(a^|7Wzd1E3L(_$yI#Ae4A)ifpIjnit&o0{THT60spF;-Vz zQ?D^stg)^&R$iH?X>bVf@~UJ?Yhz6!E~G?tV^yrOFs#wwiH(Ae zonBQttHmv-lmff*n);fAP|%L1L{;VJ(KHuKrlu@k9$Ol3Y-*@4udPX}h_#HPwl1oy zj5QHtycU~R-&#{&g(fyN*Tt!@Qg|t^%)o7p#jDB_cV)UvN~2?RaH_G2AA3=!opQ0Eq3MORpm{IhQ@fx+C${c zI2nzts;Q5m*U?zFanlM(c8rW7<_M@-IH9tkZfQB!SXo_OzbFo9V?+I-lG!zZy5@|B zyLse~XZenCsiW<-Oj2!e?C=xXL)}8P_-s0f?GkQJA9N!1UrC7JK@uyIuKu32y?ltfy!xX z?pM=Q(+urJRlZ};0;bd2QsyWo98`oHomUgf?j8HF4Lg?3 zsS9?$#OH_8IhlTU2cH+xxk=~u@%bTiPF=ZsJ)aMzbGoG3y_V1W(K&U+?$vzWo6e~V zb}!}g3_2&%?_R*?2Az}1chBPU?|R{!Ouf5^&%dB^GV$(leEu<=lWBM7^Z9#pPA1(Q z#rgP8XSBV1c4^ytr5EhnJ8SNYr#on6Q2O*{n(#}Xewx;4yG8)`)!MaWv(omoJP0Vg zs3T$Qe~C@D*1OFsZTnyj0aqWj7C5c>#K)qzgag|p#CF~ui_SKGZ zpe`i@ja&zj4;i~4<0&Aha6AgzN`A1*i|10yXSJ=myR@x&{gc#ZyWakB|NhdpEv0Sm z?0OjzOWO{*gjm;<-1jJowM_}ElSokH-@vUY>9DC+E9yUqdriqpHg%(-ZX;@Y$$i9E zYv(&CzrfDFMESYM+t#>X>#Q@1&pd0(jJB<$#S#>hwe29x4rEo!^Qm2J%{w7>S7}?x z-u8Kv-P`s$;Yxu+Bip5&Xk-9iveQPCR=z}xr8eh4a3;~fUv`^``8~y>#soA z)gEmx`D*H)dtTXbVMpSi_L6z&wnGqVZ2PqRdGmLJHh(-wf9Zl9`ly#K*rz9^5R?T9{Cg+?>#_)``6JMdDA{NC z_V3th*Y5d^L;Th_L6C_3uQp@_bpOeq`nL2=uUGupl>-Tb3DqwS4dL%u~#7k!!-Fn&AD zUuA9Im9>2{z3sE&{e9jpy);@8<6fqx)o^z^7bJeinJbG zQHHb+{Ex1+Hz1vkl0kTz?375-6NU~ZGGQ>iY1cykaYQKY5&fkxt$UXx5QI}Iufl#i%K6@dlsCBL7oz-e zl=Hm2ji*#4#@*L*tfA4P~(zQkrCC;0Z#vI|sdSZUYv2alCrhf!wYi2>fy zXn@Hg3r6E$Mrpm8wvR?s+8gjkJ#7wfMp_x&5KcQH3XIl;pk~$yz@(4p2Tc0to^;Fv zM(^@1ygYKlcq+UMj<2U*gW;p6FC9Y1)fg&z`i~Jh{+~QL9(f2I51CBIek?3ApYo3$ zM905p6pRh^nP4EOT8{(uOfPw%PU0k_NGD}b&);(@1L+EahrA!X`=adD+@Oy66mX{*pU z{qI!v%HhJ(On^CU!$@qM@(#J1RGxRPWj)6NEX*WQn9+5OW2m{gD$;9;0 z@IWJy-UyHB@*;$!O_>56dv?hr6GT^&zIqO6(yNgAeh6iaAzE+!b+T8#-@|uV&woIV zkFjS>B&}`j`snYX7xn)AVRxOb8ZuGl1@zU62cl@uRcP%o#FtM1di1SloQNZ;(v3nm zYPNMaPIJheaxFS$^D)=@8OV7=i2jmQy|g!c%U1OsN7b465cuma&|p@z4LobHXAxG% zn-L$5Lb~>4^6*fFmO>9wXtGjB_L$!KIdEb9aucRv z&{qJYL2ih+$>b+j%0 z_#0C3pj)|$YtE4>9s=}loxr*Oe*4@+O)DUS?F4i$!6&l$4#!bboqSU+dWqFe1Jz>? z>dah_@(#iwhr&d*McG`7(7BdPp<}L9L^#SuFNI`F|Km*vA9i=|pe%bPclSeixZA_k zEeFrJ*t32IfYaT7isI>wekJI)P}%)dmO&!K*4*6>*TKt)s&4}7uP)Nt-5aMN?lI_n z0KRfTUUA$Fk8Bn1>5iTpiCtCvFjefpMFsAQN7LYU+>m16&pZ$h*YnuG!HTCD`1Vvh z(%ny-CAQiC=%by$52H!r$x~o^Ztp9A?sVaogD$#XOzz$B1i~aEe*~%r8mZdrMY0P$ z_3Thhdx8u-0*48N+(Ks=&*BI@8T9lg=y?`b2I_nQx%~#vcnV2>or>9lLCXMG<$|bA zIO8r-?D>Z!C^QX3i>1}dxpv~NQ4-a{qf^Tpb%9* z38>Ruq}Lz!)Qwi4CIBvUL0)m}C!g*|WM<#`El?X>0~Zz8A3r+>vl#Qd4E!et z;^BHeKOM6g^Q2*U(I2~NU~)a;k6&JZ>KQ%}&=Wd=vp;@ahAw5JR05iC;Z6e}nEmlz zufaDMxdx~k!;v3iM%2Ik467SPJ`B_|;mB1(fc(A^Ycoc^3)C0k$miiG`i~D_l4WFO z29~$j1Km8pc63w!4WO@5KTihiSc1MqXBj(i#LAe5Lz;fWBqi`nAn4hwM<7sF(n`$I zcVO&swdVtInTz5z$pC#c4TwzruaL~B+ktp6fMQua^f%BDM!f*UYYqyPv6x=^72Ooz zGZcQ~1@P$XqyG~#9!rR#!U5Qmb>`ujqyGYdgHe-#I5vR#5Ya;Kr=KRBbS4n=EIL`% zfZ;$Lq*o#svaIugxXgz-NdIyKQ2F|M=uAd!@F8dg^(od4+14hM8_3LSH;4+%%vfj4tlI9h)lanp_qSL(EKM_d@7^E_3o--?Ndo&8{#ZY1_BLhITf zdtGv@-W`(kqfu}&6@EyC86?CWmILgC$#nf*ybeoby#}ym7s{bwfW0y)(cAMC>eoQ5 zcTrw}JZ6vA=VGw1Vvhp$nhX5|8n_CG791RA=z9?jndvhyWWbA+!r@F@(}{Yntb&Gu z;qX*UFd0`eQ_n!u;Y#KLySNiP$A^>kx5P9T0(+H<_codX#Lx88#Xk1}))5Zn2r)-* zhIg~U-vVq;IFv)gJpDTiREDOZv$L^>bR)-zQ}rd7nHV|_u;Oqi5C60D?pSwxLGEw{ zV2cR4kDcS+IKo(ris=vbRszohVokC@pm<3 z11OeNt$!f0z69bs2ZhQwNG#DSr9b*W)Bf0Pa{$0WqF&E}^Kdr;OKCz{uMN|qr*S-3zMS5_4=O?o!Qlo z0o!rdvk2`(ha2>ZX}UTS1$9&y!I;%ENQjI}UN_vRlM#um{|c}xT&OoX+@u$eQK&xv zvB^bw1@f5vo&G8Y3M;k^urFO`1~hOL5G{D%-mL!?L6(`iW5kcdt`rVu;+k&Jufv?m zOvi$OE|@}@;1*oTZFMA*;!f}!9q!N@4^@r+J+KeBcyFUQI^3m~6e#HPfc+yJ z%F*EudI!3R4ZaVst{8(MeZ$e=UOf(l89D^8iQ!O=4)^QBVL*nS1XwH_%H#fFJq8zx zk~^#b>>`3@vvUl<5yoQFBl_e*CGaL7?jn@yLO}6|eq5i2YdWs>DIi{UQQqkAq`nkk znNfRy_*VeMvi_{!fB?s+Ua(LucDqJY#?j#^{RQcdLKIH*0ysK6qkl3=NtlDem;+$1 zgBXquf71^er%)?^xF~?)=WyZu1C>_e&O@T&fIta2Ik zkq?1r@Eu5b`*FyjJ6qWnWpgb;=UO&}j=9!g^iCdS2i}WrGW0L>-msS)9ZHRsr0DRq zJ`ht74~?_HR)sx_&`xytMt_EG$(@6Ob}Af9g&8D7#wACGefoo#pNOpA0@(d7)EgbX z)eA=`)Zc)3+eLW=@|gWzk77Dx#l8WoS6`>@kBcR%RAs5zSfh`?9?~})9l9E~Vv)>P*V2xBoS%lI7YY!>(g5YHwH1d2y=w(*ge=zSnQb5Y*tkY}_Z zIuq)vIZF2#D-&mnCzfX8Apdf#!-kXEM^u8PxS&gIt(_pV2#3nWhh+b z0NCpwhNHtU<5V%#H9*`PKyh>!Y21s*Y_}hXX9FmX4x^37;p2>YABfL0$F3@T() z8cgizZi)uEAmtr|Lk`{R#{Dm3b1g#WS~i7_xc@~s$_{*pqeGc74(kIuI{e;fPl^sF z8&?-9SN}QK&c~ibXeT<%G8*Xu=~@)rL4`$Bm_b5hTyk`nZ5)SyOk{lvU@yARX6OKm z@;%QvMlpmjYBvzyxhStd9<%d|-^lHNKDa3|7Q3qZIB4K1AX@OiJ=J(k7X358P<0?C zuIV&mJJjar@Cz_pnTiRG;7ZOg#tHr&V7GRH=jd>jQICm{8~qPpKXdWkMsswC8U1i& z#L%vIWI|6TLJZE)q1@OqSV1QORuT^7=ul~_7X@N~Ee(fqbch>gA@Z>TmjHHsIF!fz z5~CQi6WvwO9|CMML1(jb%*PSNVpN@R++j-Kb|5}V76=rN=%vOf=r^ub$7Mlx?5f?~ z=+I<*gB3rcMgTD(fMQuK2HiSh)J!1eIw(}e(P4#gF6JEu)T6N33*hLm(x}F&fC0Zo z;q?xHy$)hHI-G0to}^F@0kJuN;^=U`@d}K=vbF>9Q2@o!;UeRF#85`*FkW};o_^O< zbhy|UA){xA4}oYvzMOXi4mtGnE8C)Mu0=9&JCZ4M%(c!Y9AyVS2F)V+t;R|D5*>ap z$lmUKhdYcRSVi&B_zl?BW6vVA6CLg}ZpN_J|Ad04sqkznbe})LRvaDfHeN!7BwK$M zuuom6H#+>mco^nkR6159x!6Ml@|eBXSUgfGRtVTk7g_}kTm_P%!~Mq1(waqJIR8LQ zT+;(a-b7W?4Pf|VDke0Qqr*c6rZ(GT&jI^hCwPty4;%OqoZaXjfbEWXDWuUH9Ud`G zMyzK0i~wv(IFzHqW5xuGG=|OwtTG(R(cuXr2QxE6R{?feIFzHqlg4^DAVY5l?2&LN zkNc;LZGbK&cX$P`cL=(aoudUu7>iL)8|$UVzXc)<3usT{f#MPUSL2tMhq>B8K#UHc zcvwGgT!ED*qe_7ISpdbdUNXAD2N<;kh(-s6%2>=RMlX0411?436Ghu4is=wSx@ z0fmn^0QNeF;pp(D@pr^|M!f>WI{_3&hqsNDg8CMSG?*s2{TvqJw7EA~M-)hf~bU zlcIxZevMA!=2u0QN>W zl*j!bvkjy0VseMi0sE1lm$7qPi6a`%sDsVv@Mu;u2LWIRc8?1I#UpyCc_h}%j5-R4 z87_*v8z>&uBg~az$Vwm@0w|Vsh&fC=u?>i|4obv~F`p7KccSoqFMy-NIFo++&D#78 zg>N_j_Bx2+=rF;Y*+ro~2ja&7ilf71b5d7nKg==&dvg0ZI!rY`!W3+`ABY(~l!^{V znzOK`VN}eAKs0CsDX$fWob&Q2I#4#(B6O~0Q|Op$T}L>|4t!dpC+nx1mmpZ$(cwN5 z!_%{NILpk&4GMPk*TD8R_AEj>(cx_KxgI$E0tF_npt7!`!VD53;`?yt1!?J_6WZ!=W4FhQ z*Wpke_bbc^P~cW_hn|?y`(w|#o1Np2IHK{4`ng$ph!Qvnh+;yyE(8>h=wFx{a3Rc% zIRl7AF3KAn&NJ!dLPnhj#F_w#WnE}Kfq2BI+km*oL7_4ZGQTo!7BSDD@I^0xqr)ZU zVt6}C*p0%k9RPbB#Bg+2W6nl98PyY+{@9aS#?fJ|xl6{yBp`|dD2@(Sm^Wj>VOeJY zvB-x~(cxi`VoN9$W~Bqba>3n%~z;$AR1kiS0InsC(Im7%&gd@fZgUoH$eke0nvg7?vv*I z-4xSiFuZ*rCa!6-xh7pPeFKJWXopfgxhA*;SF*(%m8fu&a(Q{g!}JY`nEzt}XV z0K3S=dmGKs;c4@0^glz-1MKo}C`X59&G+!gfT4E-_Cz?8qr>0K%dwDT=o^6T3WsuZ zc-}k_OG$=oiVk~C9b=VcUGGC68r%a?-UB$~&|9?G7G-lSLg!jGg^sz_>x851K)NGh z={+KU!HUF=4pp3YqeHLAk22f#8UtqRS}r5a&+hu z`8oWW$ogr3#a*a3I`oY^hyq5Pi_BUV97y3Tc?chZV9=Lgt zPq1iYrgy;b-GP|6rv8ybCn=^rxIRAwyJ}@}O>hgYA;@e37(_FphyHt zaibH!UgYAPMnE)2hl3+|xJqZ}O@Q4O4&~@DBr?fV(7ytVOZpo3{Nn&MrRpcL2VS0q#sj}M-#Hs*_ zqr>r$nNZViKM*(jP%1i{5P1OwjC#a}z^@U~E{E%6Td$xbZyOFd^m=`^McG`7m~t(f zLdRU|d%{t6;F}yIsv~>QopzAe#CbPJEQwr)7{DGs8BzQw>{(v`?F5P1$VU*T&p|;I z6&e^&dIkxU;mJXwKJsu+yqZItzX0qK7wQcX4UwZKDAWcZ9&%A$fjo4VMfPK=W5r$s z>|+;dK?7F-(SpZsQ{?)nVv1lM8H8Oa9L~fwHAiN4RZLUCK(_}&ncy8fWi(l;C= z&W$`IR_})l{SF}n%0c41$dHIqpaif}!l69;e-+t~g*T1K9hL&NlAwLqIr`xUV=<~N zvH;!4ExHP^2qscSe9kM z9eZN8YeZ!nB(93QfK>wnMxk(=7r;T{+Q>%S#A3h+C_Kdhu-8Eh2Z`$=Ut)2@sHH%x z44^nj+!(nEa~-3u2IBVt6bFglMJ|<=Jr2Y(K9mX)8zRs2RkHr!L(or_=nFvE);^Tv z{fI*jU9e@XAUp@ME^7mb2``fE)bvkP%20a zOgk4V97dTiv8TH+q9bWLvnePXgp$0$IONa|^0F<;=32y*YuOY!;*lreDBCl=#|P-I zp6R{za?r2q!}(b29u`PDat!KYOMhdO9a#7jjbA$jPK% za5Ci*PL6D5(MO%Y$mEPXR_HBO$XvJa+~La*xOF*y z@Z1r{E6x6#q~Ug@;jEE^dIP^*iJw1`ZM9t~Ty6K*_H>$|jCBnoi^%)8s}8J!CF$3# z(g68g_G&a_gVT_{{DW3wU8${kUv@!b-E>>=zC4GbT_avs`VH-EThz8>c82Xc^GAM- zD6MB_*uGO`>zS>D)sDOh7uZf|H6BIK`w)NVCMwBK#CJfor=i-H*bmt>*v{z2x@udw zd%D>!Rb?x8PdD4K7if8B=R+pFMsa^PktIJfFMXBrHsvcs6(X}+}(~rUL`LG{K_M?oh*#vcl!CIJ@=$y==FrEW3+5AJQ!~RM0)%Xb@=v~dV z`3p4KvaM$zRnvRv!+K<8nmzjW=%vrr=XHr<*cwB%%*>-fM72|O(>gr!h)g{T4ieGL z9+{bPnl@51dkpA~X)7BUqRs#)JqssCVmh!CHI1lU3&09U+L7HzQbw9a)XW0?m~J-x zS4BN$WZ8w?lBhPVdlHS1xFl6-T3B#c8r4s)zDKk4aQUVZ>BH~bxGi{TQ#fz2JEHx z){DB3kl|^z0inGC?MGz7WoQ{Va$*vF6mcDqX7kxbJA^pNs>C;%%JVbrl0&5gF{(fx zuWGZ)@T2$fT+>)r54&VsCj1kDM^y~Vli)&}vWMEI6O_8DbRztYOWg)d0>Z;E*)_oo zPqPnmYdMA+pxuU{Y-pKix~_lUqdSiLzhLNmY;{9jeC*PA%{kTO4Gm-YOYdVUtK*eR z;*DdLHrBL+k!tEIYn!X$+Sul%#uCzLHMgez#BY&3k;Ay~#c~vZA@BHZi8A9#ac#T@49q<|94zoyNhi3y89AG&_hm z%qGeL&)nKmxAKhW^7j)`=PmfZ4sky4*U=#mPK|_kkX> zjv8n02amG`vn8w(IBB7yb(-gRI^`crKAdK@JjzW~-)v9*cz(!dHe)QPhAnSsELrSl zkxISzrDY|H{dCf$6C+nv`UQJ*`JXq)uLaq$uC9dt*Mql}6%7rwuy2Lnla1Sn-ieg| z_rYrrWx%H9iUS)^sYw5!A&!6Jp?W#^9}`ljnyRx?D=JP_OEshGmW$-10&(v8s*>gY zuJSW9QD?_bF2VoY2=z!5wW0|BSwoDJJU#>efFV$!_aANGe~2t=u4#<>D^sHq-HLxg z60QhZON#KQak`xC;BomCf!Y;^*r%DAyL74RRgNegnqoQp*N>FWlFTv1?rjXWlni1x za$NN!=BiQgz|E~(J1T$;-&qsPyE_ZXhcH;p^minv@%4=SY^Y~74$!PY}XTQ z+4DNlc6rK?CkAsoF{!W6Pvy(){{a&)j&h!W9YS?OYn|xe>(&(iTt&GcJC|Q1&uS@W zr@A_S*J$>zz%(S1e9cZZ%n<^dVJ^1*>7L@ta`m_e`$Ip$Cm{tSBmxpJRRD__@Pj`)jHh zXGJh@DsLb!l`a&6u%%KuLv?k)8B`zm+^`cX1eZIk!-?K-K})Ieg*8q1S5K8oVhbDN z@f7Bmf=@UFrW0j6EP(0ag2d*u{9Y%97pw! zx5zV_2CfsNjwFkzSuJJfOCPDlkb=)@@wZomI}PALCGLe4T`$X&s; zB*h`J$AKJ&tgRFeSz?4PygiBs*Ip_((~45fw6KmCz_D)U!GM+*$?cOW5%*HsN`&)J z#2UjHipio<#~`X!x>Q~Ds(NW98*D1|5!qXOj7%9YcaopuhElAu$#H03Wnr@>$@D0Z zvWt@2*vU{2&ZoRqt&ImKQ?HlORr>*Bzr7kt6$gT=WN`~IAURFSSXmLcGLaZXeURM# zKri^BHMdN8eacpeR^+RQ?3JRe_!$eamushZ z85Bhic5iPu5Cc$my5T%H8BzP}E5-0G#LVx6T2CLiE}OCo{Hh_a#MI!gsfyPpY8KYG z|CU?8-2bSv&WU_u#sqHw(*rYqM|q}QT7CsvswR2<_t*BVOITK5&l0Jb zJ=1SBo+8xREjT^IVl<`Ns}-;5SX9{9k$=4I{M&c+{s5w<7}l|CQpb7Xdw9>m-eNdq z(@qQ#yhG^;qf#$79g)yk208`g7|wdZ8(}FXg*BTZtZ=h!Qm$gd*9x)Na(Ai_LF`sg zBQUM={D#O@EuER{p_m)&8zCO0SXPP&&Nq`YR01`IV{p1v!!gvKI10Ef9qdai)G9Ua zePL-tQnNh~H&}m|!furZ#IuU%_ux{6`aNaO1@D}P_!P@dDI&Pm@raNy-l-B{H+Aic z8^;IiONmr>AUb`5Azi=@hPl03rt=if@nZ4iOKWQ?Yn;V_j8M6NO{GQ3%U2pmUPHjk z!*4ot?#m)Vtx;;RlBscqd9tO%)3H2G(17vYtn#}i_pZk^gWm0PP487UEnN?Ml}*o0 zFvU1)ZkC|#BD#<3Jkz;%W=ZP5PQqiSt}M1AKZFki%&$vqB4>xIA@5F{QLpQp-Q5}Bli2WBa*12D&p{^!P)7CI8B ziRkq3faES|LcPb+URrcZLwt^CYkv}JKPNF^stVx;8rOd7&8i8k8RtxJFLhTsR!igzByWfdzaO9<&8_4eD9BX3e=j-S+SkX-6~7F ziS*{CyC_Mn-C3*1=%vB`pT}wp0%x3i1gD%(L);N}UVMhda@a4Q6zeE7}vFow?HiM`7PUe7c)A8$L0Rz%hfDnxJ zW~?Q+PG$S1=;PMLnnYYy5u~fg7X8Tp(BJ8GXSDO`5+%-3RycS%Nqt`+_>9C~pD-!El!j2#Q<%+%B>TIOBY1tR;NsWn`pD%-c~d^QIo@jxuaX!$PXGAo z!1U`psSy^Mh9*_g)3pEag`3We;KW0+f+rq^&W5yp^!UG;Ee;r)d6gB`d~#W|(RpJ> z+DN*j?ET;(-Qz(?&2hUZWoweVsFML5^f_^Ssgj43TV?Rhl=H>`HIKQy7r!)aQpGcm z&E56Ne`a>idOD>Mqy^r!C*3MK;3UcnDLX3oRK;&H=JzhKef}^0h^vRtLFQSVsYvI2 z^IV$69RoKDyf8#Oo+^TmbbNt=+%;uugLh0r+)^6sOyr`Y*YtE>GiZ9bEr6#?feS;C zVh^+#?yU8GEMx)6R&yp^SlZV&t|NwaP2ipls&_iTsh%rQVdQ}K zet9PJdW&aRNH@Z3Q;rL#R6xW=cV{ywdy*jzDhg(qDc+L(RP12Od7R2q#1``udG8cam`oY=f~#m%sW=nO zYbgX%R8qzb9TB92V_a4qUg@lHrB$qYO8tU&gk=&E1xX7DADC!TY9e^{l{qQy+;qO! zk`bboklrPcw1)2wyRkKRyVaQo>KAFvP4UK9U3pEtv`M6Ji17MPlJX~!@-feg{ZdM% zaO+NK38{s<#Ki~aEakj{7pyXM|Y7y>xQQ#o-;F z@m8ojFIbuUJaV1-6o#R-T9Uugr9~zGq(f_oN?v|VNxb&YF5RP)ZFcxtEy-_nX;I04 z>CjrDl9wN5hRK(*uN}TtOY-|%T2%6f_9|lK46P+9dHIQFn0zTKaQIp+$&YtwQOR#{ zXf096%MU}tQx$h+ysO04rv|;k4 z><)*o)sp<(E-fng7adwlRPypm+%Wl4_Oip*YDxZ8mll=0sXi(}{waC+J#UzNDNA$s zS}n<2E-fngW{1`im3)gsYqcaVU)dl%+|g|3}o7KlF2qXFBE-fngs~lQORPypojWGFAc8$Z=YDxY&mll=$!w#(_D*25LEg18p z>=6$}@{hZ;sN~;pXf096Z*yot`BL_#2P65nU0PJ~E1Wpk5|#Wp4z1Oayvzk*eV(QI zHK9`RlU8-^_mPj49?Mict5hm=`0>)`QZA{?ACgMEmsH}jq!LdhmG~#A#4AZ9zDO$Z zKvEgMlFE3KRK|&n3Gr)x`?P|l6?KX73Zx1AGMv(C$zdT9Z(OPs)HfvJ1;xkC7?Z#o zPxcwUtx!OpG^iR=Q>7KqS#^0+wN_BIq8{?>G|_06w8R^mY8vX3PGTsdUm6mF$}O!; zXa)TKOF<&O9QlPfL0JR7s!*;K#H;ZWtMa;dthx%kat5K5mAGuFj4w^Zpnh#!E2zZl zl1)&-P8L@Jj#|p`VFsWZAQ*=NuFaNQ(F8Oe6V>6hA3)<3&5L5V62YrqB!y3F>K8Uh zzPzHMG2S9)wKesq(ni5uOIMcLze13;EX{XdL{6fDF7%%@6#Xm*y&r%LU{6zBe zUj`aMNI%*x?p~x)PMrGfGrKOyQ`&~z%fDXnukUW7_S%Val<8g4D}DTHdlWHtZ4aBJ zS`@QSHQ`gI+I7fy>))ql|9$v0D{V@QeS)KMC+B=Ua>U^o=y7w^NT*=Y0I+h6~izi(odHHh{f3D*9*XKX~ z0Q@qxsK$K7pRf2kRD;EhgkReAPhb5z1}z{l+Kxe-IOD}WbH|U!`4R#MlQ|gqPFKj}YC2r3o+Lwt0? z(k5vX8Ohrv_VLbqJKgIgBJalzO2L2K!8YUJ#mNHv{G(Iwzgl7QjTXZwF@FB3Dfsut zZHBviY!KYH4@g#mp#bNbpkK26RY2xy1 z{`x&dfvgGbrWi#bbOY<7FuJM9`p3&;ViveI6rZN8HpAp}(PSNxEGHf7iZHyT$+{sK z-xceCFnoq4^L#Qs)0w}M>D@G$my_w;HJNXd={+==N0aG2HJKli=}}GQy<~bXP3E&? zdT&kUsbqSVCi71+y$|M-1zr;8O|7pc^M$w2)UusK(mp^0zB zOFT}d_tPZKCevv(AKc8qD&EGJ+Cf1uD5j<+FJGytsYxY3&-YR6Q&T%Q1$}UUPUFhZ zx@(WC^_KuBK18(7_shAY1CY_RV1Lnkp=-hZn!@y8f0ckv_3rT1dj{iOJIlCVtmqf3 zc~0ih_b@Ey1;ZpykDsHN?v-rk zPXL|d$Q_<$1vx7PzDnWcj?`3z|6L0F1EBZP+_){*AAe4Pe^tqsJ5Upq{GFgjL;Cmg z6mou4a^y}IjepvTFxmG;d*!a;Mw_gi06N*hU+?J(pRfFct~Y60tnhN@t->a2cQIa_ zc#=(^_tN@l^2uL`8(Tn+BEI?K`HM=v+{u&v{Z7&4j^1EZ2mJ?`Fh8fyJd^xu^A~uu z!T0x5;7?R|zdo}Set|DeHl>i$4m#PhBU;4uNvw4luHXZA)-nc^} z_XV6rRF>D)#un8z)W`UDmReB(VideYem(>z60 z4Y5VF4Hft{0pHk*l{YWvpWfBR6Y;8o$&)6G*Qg*?Q?;DVCTRBE!m8%FI=o+L*Hd!R zbgt&O*~K$UVsb{+NZzf5?;>(7>Rn+{_w=&y<@|xbvhfuvt)%q$vXhT3E{mOf+;MYC z=Emk0A6r&J&8cc?h*jguT(~Q#+9vhTeNNnDY%E_9i{nj%SjFikFN%-AM*Lp(QpuzNn@Nw~MFMmNzxw#%b`C33;|0{&tY9z18&X19At zncdZ7S|NXq$u{XzE3d M|Mx#2;SsL=Us}&xF#rGn literal 0 HcmV?d00001 diff --git a/seqlock/seqlock.c b/seqlock/seqlock.c new file mode 100644 index 0000000..3762374 --- /dev/null +++ b/seqlock/seqlock.c @@ -0,0 +1,75 @@ +#include +#include + +typedef struct seqlock { + // Sequence for reader consistency check + atomic_int _seq; + // It needs to be atomic to avoid data races + atomic_int _data; + + seqlock() { + atomic_init(&_seq, 0); + atomic_init(&_data, 0); + } + + int read() { + while (true) { + int old_seq = _seq.load(memory_order_acquire); // acquire + if (old_seq % 2 == 1) continue; + + int res = _data.load(memory_order_acquire); // acquire + if (_seq.load(memory_order_relaxed) == old_seq) { // relaxed + return res; + } + } + } + + void write(int new_data) { + while (true) { + // This might be a relaxed too + int old_seq = _seq.load(memory_order_acquire); // acquire + if (old_seq % 2 == 1) + continue; // Retry + + // Should be relaxed!!! + if (_seq.compare_exchange_strong(old_seq, old_seq + 1, + memory_order_relaxed, memory_order_relaxed)) // relaxed + break; + } + + // Update the data + _data.store(new_data, memory_order_release); // release + + _seq.fetch_add(1, memory_order_release); // release + } + +} seqlock_t; + + +seqlock_t *lock; + +static void a(void *obj) { + lock->write(3); +} + +static void b(void *obj) { + lock->write(2); +} + +static void c(void *obj) { + int r1 = lock->read(); +} + +int user_main(int argc, char **argv) { + thrd_t t1, t2, t3, t4; + lock = new seqlock_t(); + + thrd_create(&t1, (thrd_start_t)&a, NULL); + thrd_create(&t2, (thrd_start_t)&b, NULL); + thrd_create(&t3, (thrd_start_t)&c, NULL); + + thrd_join(t1); + thrd_join(t2); + thrd_join(t3); + return 0; +} -- 2.34.1