ConcurrentSkipList Bug
ConcurrentSkipList Bug

Summary:
Bug reported by Yan Lin (not a facebook employee) through @robbert.

@philipp and @jdelong: you are the only two remaining facebookers to have
made non-trivial changes to this code.

Description of bug: layer 0 is 1->4, and we're looking for 3. We pass
over 4, and see that 1 is less than 3 in the for loop. Now a race
condition: another thread inserts 2, so layer 0 is now 1->2->3. Then,
since ht==0, we return pred->skip(0), which is now 2 instead of 4.

Why this is bad: it really breaks the lower_bound function (lower_bound
calls findNode calls findNodeDownRight), since it returns an element
that is lesser.

This patch doesn't change the behavior of the code in the normal case;
it just recycles previously-computed values so that this race condition
doesn't crash and burn.

Patch based off of Yan Lin's in-email suggestion.

Test Plan:
fbconfig -r folly && fbmake runtests

Reviewed By: philipp@fb.com

Subscribers: sdwilsh, folly-diffs@, jdelong, robbert, philipp

FB internal diff: D1732434

Signature: t1:1732434:1418260198:8c707435825cfa2a1093b681e066f320193e98f2

KSreeHarsha/folly,constantine001/folly,project-zerus/folly,constantine001/folly,clearlylin/folly,lifei/folly,fw1121/folly,mqeizi/folly,stonegithubs/folly,sakishum/folly,ykarlsbrun/folly,tomhughes/folly,SammyK/folly,PoisonBOx/folly,Hincoin/folly,shaobz/folly,facebook/folly,SeanRBurton/folly,SammyK/folly,arg0/folly,yangjin-unique/folly,raphaelamorim/folly,sonnyhu/folly,alexst07/folly,gaoyingie/folly,theiver9827/folly,Orvid/folly,chjp2046/folly,lifei/folly,hongliangzhao/folly,CJstar/folly,gaoyingie/folly,ykarlsbrun/folly,facebook/folly,gaoyingie/folly,KSreeHarsha/folly,fw1121/folly,leolujuyi/folly,romange/folly,SeanRBurton/folly,bikong2/folly,clearlinux/folly,theiver9827/folly,brunomorishita/folly,bowlofstew/folly,upsoft/folly,loversInJapan/folly,mqeizi/folly,loversInJapan/folly,arg0/folly,KSreeHarsha/folly,bowlofstew/folly,cppfool/folly,zhiweicai/folly,renyinew/folly,kernelim/folly,Orvid/folly,shaobz/folly,bikong2/folly,ykarlsbrun/folly,guker/folly,Eagle-X/folly,leolujuyi/folly,reddit/folly,stonegithubs/folly,Eagle-X/folly,kernelim/folly,bsampath/folly,guker/folly,renyinew/folly,floxard/folly,Eagle-X/folly,tempbottle/folly,yangjin-unique/folly,alexst07/folly,xzmagic/folly,stonegithubs/folly,yangjin-unique/folly,PPC64/folly,sonnyhu/folly,Eagle-X/folly,romange/folly,tomhughes/folly,juniway/folly,SammyK/folly,nickhen/folly,floxard/folly,juniway/folly,project-zerus/folly,hongliangzhao/folly,tempbottle/folly,loverszhaokai/folly,brunomorishita/folly,loversInJapan/folly,doctaweeks/folly,juniway/folly,cole14/folly,lifei/folly,zhiweicai/folly,clearlylin/folly,tempbottle/folly,project-zerus/folly,reddit/folly,wildinto/folly,CJstar/folly,chjp2046/folly,chjp2046/folly,reddit/folly,lifei/folly,alexst07/folly,tomhughes/folly,loverszhaokai/folly,raphaelamorim/folly,raphaelamorim/folly,kernelim/folly,Hincoin/folly,SeanRBurton/folly,cppfool/folly,shaobz/folly,Eagle-X/folly,floxard/folly,fw1121/folly,clearlinux/folly,juniway/folly,clearlylin/folly,reddit/folly,cppfool/folly,bsampath/folly,sonnyhu/folly,KSreeHarsha/folly,Hincoin/folly,brunomorishita/folly,facebook/folly,nickhen/folly,clearlylin/folly,nickhen/folly,romange/folly,romange/folly,wildinto/folly,cole14/folly,Orvid/folly,PPC64/folly,clearlinux/folly,arg0/folly,juniway/folly,nickhen/folly,Hincoin/folly,loversInJapan/folly,arg0/folly,Orvid/folly,guker/folly,bsampath/folly,cole14/folly,bsampath/folly,mqeizi/folly,doctaweeks/folly,colemancda/folly,bowlofstew/folly,leolujuyi/folly,CJstar/folly,colemancda/folly,bobegir/folly,PPC64/folly,sakishum/folly,cppfool/folly,fw1121/folly,sonnyhu/folly,bobegir/folly,sonnyhu/folly,yangjin-unique/folly,upsoft/folly,zhiweicai/folly,SammyK/folly,project-zerus/folly,lifei/folly,raphaelamorim/folly,hongliangzhao/folly,cole14/folly,bowlofstew/folly,gavioto/folly,doctaweeks/folly,wildinto/folly,kernelim/folly,sakishum/folly,stonegithubs/folly,sakishum/folly,upsoft/folly,charsyam/folly,xzmagic/folly,yangjin-unique/folly,cole14/folly,loverszhaokai/folly,theiver9827/folly,wildinto/folly,chjp2046/folly,mqeizi/folly,leolujuyi/folly,loverszhaokai/folly,facebook/folly,doctaweeks/folly,colemancda/folly,sakishum/folly,brunomorishita/folly,project-zerus/folly,PoisonBOx/folly,xzmagic/folly,kernelim/folly,theiver9827/folly,CJstar/folly,ykarlsbrun/folly,leolujuyi/folly,rklabs/folly,floxard/folly,brunomorishita/folly,charsyam/folly,KSreeHarsha/folly,shaobz/folly,PoisonBOx/folly,nickhen/folly,hongliangzhao/folly,SeanRBurton/folly,xzmagic/folly,colemancda/folly,charsyam/folly,tempbottle/folly,stonegithubs/folly,gavioto/folly,shaobz/folly,theiver9827/folly,ykarlsbrun/folly,tomhughes/folly,bowlofstew/folly,tomhughes/folly,mqeizi/folly,constantine001/folly,raphaelamorim/folly,reddit/folly,floxard/folly,chjp2046/folly,gaoyingie/folly,constantine001/folly,CJstar/folly,rklabs/folly,bikong2/folly,renyinew/folly,PoisonBOx/folly,romange/folly,bobegir/folly,guker/folly,bsampath/folly,SammyK/folly,PPC64/folly,constantine001/folly,rklabs/folly,upsoft/folly,zhiweicai/folly,tempbottle/folly,wildinto/folly,rklabs/folly,clearlinux/folly,gaoyingie/folly,facebook/folly,rklabs/folly,bobegir/folly,fw1121/folly,gavioto/folly,gavioto/folly,zhiweicai/folly,alexst07/folly,alexst07/folly,cppfool/folly,bikong2/folly,bikong2/folly,PoisonBOx/folly,renyinew/folly,hongliangzhao/folly,arg0/folly,Hincoin/folly,doctaweeks/folly,colemancda/folly,PPC64/folly,loversInJapan/folly,Orvid/folly,renyinew/folly,SeanRBurton/folly,gavioto/folly,upsoft/folly,xzmagic/folly,charsyam/folly,clearlylin/folly,bobegir/folly,guker/folly,clearlinux/folly,loverszhaokai/folly