From: Bernd Eckenfels <ecki@calista.eckenfels.6bone.ka-ip.net>
To: linux-kernel@vger.kernel.org
Subject: Re: Lockless file reading
In-Reply-To: <MDEHLPKNGKAHNMBLJOLKEEEEFMAA.davids@webmaster.com>
User-Agent: tin/1.5.19-20030610 ("Darts") (UNIX) (Linux/2.4.20-xfs (i686))
Message-Id: <E19sUzl-0004Az-00@calista.inka.de>
Date: Fri, 29 Aug 2003 00:11:57 +0200
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 25657
Lines: 379

In article <MDEHLPKNGKAHNMBLJOLKEEEEFMAA.davids@webmaster.com> you wrote:
>        Find those GIFs, double-check, and publish immediately. That would be
> amazingly big news and would probably cause huge numbers of people to switch
> from MD5 to SHA1 overnight.

Why is that? For a hash with n bits there are at least
2^y / 2^n = 2^(y-n) files with the same hash, if they have size y bits.
Three are even more, if you consider all files up to this size.

With n=128 (md5) and y=80000 (10k file) x=2^79872 different files with the same
hash, which is:

73758771305612149138757973947840453624822288693642912037251984265061\
00114977473466610342516138996953532522212913684506495987369027376247\
15680102183899956755293229604036298841899346896312975318416816792181\
27163102430377376805525407677117167195273455353500937474682475767850\
59179157052570202917558881297004500267146311552672331119254293941288\
81200564802772472735124212232463022640846529434844027943281412745730\
85139886962923676798297010059108583228148158547397805954834594989809\
72953082523096457840274668781301014306803374729359559243555477575414\
40743184860888676456545815644014580307967389124314445607714035149073\
07589212426013390575273338209003958822345762588652779339518192543309\
86317487722170491968583142374006999722192982951269179790768422998167\
08449702141611939030460451116251870263862094621134152440907522456787\
51931691226465546945055073850028999878309015830845841569473374428818\
38069014874242916295358660843459867579762128717086485255524813917818\
93048437497315173334429979530572030202862199229371143871214566570030\
75727422692477487723119025817627046899875118936499627544458020896601\
57937925093115270533258873516793039117097872784457478242527803568668\
28631394601551771044737759212698144953003036178706026830838663271584\
01592980859584723256093157100606730021922520778222789293516580288692\
25264244660543124963539004344523631091601054705861145611115771926445\
77478534613667305980110146817904878379835989090392217842151012038447\
32903904630045111054945146422201082791203805511249222706103705145946\
71820615624444389237027551184044272914241672227827166453175228687028\
66938683553829374974281116729061361295584136766500184918365115021199\
37169541145849843445053788883266574169813935549175907371700139138138\
72502071050440159721888802465338768753780473818364722509365607509899\
90281003295942592341570547210474186910921077818634263104420109401884\
65729426198803625408484236068350211025109659994524663107915732813683\
23249026269135868577867279765840583230539982435092205081214139636131\
52716158876922016303074856693366702970999646715276255547943011782454\
30451711340888832195663444371564861489518840602769168182051363706921\
56348391007580137339506987160160155329372785718654816692279404095002\
71631290709679864507500640424102364928586816669728574941400097861766\
98623345776769276035921922328812527260139781666739266290331711100138\
69355520506331079686339512263367217460717946825089940625062127323177\
86653058251722203905147108918559635723363913322812633573852636358143\
05929154109676275195321548031664387835763338445788114635589758368895\
17974907569210022960592177775660950422645740978394883220940559863725\
17922274955785951581660617914435597347391402963730377168547070736184\
09409184312862027981853714218127309283218818430216375047782183166306\
16773059670202724953584786650536914280599829953639402884772276266175\
74429349374567546167841892184392743355864837653142407213100256586750\
41336949647306338065403113935569936012036214119515511822780434287340\
30928734800002296824907120604076897989376531011143837044498904591969\
67573317525873614600338869535377596304879781797541287906717071752299\
79432009185387838666393216748127057247821526828251843082459605902721\
91898927046995849949526294260125716903061767423516291316259448887102\
21455117996027263044925703914568589351096240255287529058558303698852\
12851051794252832424631653450392428817783210001109070180912805870873\
07386072771724226933940298630758819641696078651336928520241718916016\
03519077021589676947417102185394484893439475195997406265182485474944\
59178017073695377899466712572589814669494675411536769252318932662247\
42203943726665732107904396523581039784309768624193293669453454613822\
15749223233434417462994719818283525937442572314803099751885933759868\
16634054700507294873752867437781563278323662445301928131033228617590\
35430194103956670055593952506967036312263794347882662751144124966996\
91351677629105493982971530018612054379318441420814383739436560078198\
43138418873116377898447796602758998473352233358353697569513976917684\
45423037648290442116492517078342243822589633273690408706974851274325\
08132319738846084567101570415478070907066126456504167969509604493072\
48645914957093677769177377246870165130337742440748526644770151979128\
47211604618032267059204616591999117507548440215522308874869279619705\
44790645926520397665781107515922450033794810695414009529069301089709\
73157072428268136340204167242984153890552777305481674601484732441017\
28560824403131840588191220521738725204457330809940997294315972715083\
60725305431083136292963174671514146443703870465945021837055000033974\
71343654123104963598692282015717496687304002201274588103720513379013\
73625443109735850169152345779367135337891706905992705940277701946037\
51485390147093579878750275097249158482766343355558089592208214469361\
42276931894022033384129759100364979210001950264216905954876971408322\
93770122779579100592816803465994717468500525380304100505203551456609\
49222119718024454375095356130282351572692787346489597961086730476245\
84334725114957596993473817425633275365545763431282993581470273699983\
69757127063885542311338579547488527586375582908609448860018780419534\
19537297554404836539225811986557499970844823045184713996979552418442\
74406760049159007279015378851550531580664049422653169603166655301827\
48599352193666664508497247573119948382046576805640670494290298734858\
84417223231477087092260452907970029505261005523561715560411919810056\
26325051985436811764833953794260944157856829720560313439000417881996\
66649136236854393658468387755348570975402758189647533662960697427372\
12412647608184960382793382969692900066773207105873069629313639145519\
80713895245632909242920773336712845268455388312926807578615068583681\
14735015718512752431993230816015076649376333137154762997959604419405\
40830019834949523547804904348975842603471995834045489085385950422244\
21421527056856660062948296226796218876244177325383754033674652041604\
73794980904792158435418276687436661921442912299388028773041675317063\
41702985744933602467081363806581646503634957766157218777471663915518\
02627490937845991300518517420026319487215368719584336485771425750960\
74147906392458647321632082098445775029982834370708320917720129979770\
70455506307814353531726531033563236535836642541212334872049648262139\
75871050354308249098506454123665816967377687075573519014546199680718\
25504901192973448419707741143954204819897813037578850381034208321065\
90313529679084091518649506694968971633222734828354332911155417094032\
10171315988545986151874205830881181014135272806355975146559095444333\
46904167367553579042699361907200322278137701375922580419478734423318\
06121488248550399697475750553850800216488249799595528934562185651076\
98483900622844796406822349397868990356392508055418557772495336464051\
84315867243632263128883584334516110866716220279538827000535200550974\
00891217955190870275336026052153821633475850086009198501611505257778\
47933885680755163296870602837070256783151019285961820158384372038595\
17860622613336775309534151796578569381023269452368108582507056951247\
98793404504540912203957292887715691948144120313016926351322062639192\
87532878209614118770056914646891704747300580355118133346576439497968\
43441915977050748964333072943054209320237827891228838972888080894003\
90308897490656128265393212239169918857054561600215188074809617435067\
81432282933335020500424666690346752022172982638444273323437620748833\
52465137449659970847203193277839245531164554835482556691810957680344\
96966689035036985236456367028660016192169034841287219164333818992502\
01221473697763200027508042141909843428691750233206647821600433304062\
18891775169474513534619981893727149433699742028109319843146130300790\
48374620733930112399742313419818337405590406519992557821007628973929\
00113044791623585643793713735052077993606309171905986641896042192953\
02914470680005418423614268207498056056631718569685347881208192391048\
12736436159629914835075343477182008191330928785768860373127939973177\
63052494277204358579240174730488245462349822120037469207659121017510\
01218092291272699027706462817620604198339134745323293916578572282549\
24116244533223866364856865317114967557066663536376343128567680906720\
61764562620886039013573861476592226708854287846592304969334912469803\
12507139147064808903612376733627058308253758999654545653079870971966\
39352239897170601807293538529571930214655824923553210628065441410082\
64909257175626977532187270976620686987192211027534081125067087406140\
04272207570560217022276862167201738705591967047132029817306091706167\
88511161829178775447774522166205835983174468078354646490355262626185\
92707769692650015463072254012707290128020704879925204262894366607928\
64569688539411097568820564002708260545302498646096613541573488053035\
29464112666464799579334001389463815093626821732035568867075693046582\
56066956011728344932544832226503455818172038856422008742254965154356\
66307452484032159959349389526776258180342580543432325682116409135613\
88088767367314844519622100290218802495202321475300477340729565680783\
24011223601204141085691954438204937682332227360382936775988886545128\
93525280821911159972971397574162898085649998565393045404760240604331\
59456659730073515088831333039887309968528845217110079369331693213177\
05558397796379108248708431620233189642397710829943933934005835585902\
17513252794090844735190314941878898989170740854188417518129638056086\
07436762139072615685935122969736651233387075068866259306433410312065\
73504562435401771168805144280321002849860775467143169339505355458866\
35914375988685051115119841307132244418293162454216614670787597317746\
66702911316829023341512709925133948717354523200459998088061675060047\
00566452526710346126651489557268627487651204778699369531585918862201\
59394424745148402742835964929610173703136610804997257202644221090466\
98365297814614744314991928707978437775163172405897520668685112787838\
76745065718227414525009485074009755851181719599276687557225114880046\
03173249464073454779191764341396098872621419423704644007522244100096\
27738372944337782228361617675552100763578393891200653283263519950059\
32714093086973120414639660768933627220032232042053664212501154040067\
41174802564325712314623332216263370677113891935181869723499560650683\
86380815056042861307598414035089442567526704536760404967820726566472\
34670879286692361894969928723752609821775353401149541579651197092514\
39298884447458964811457837922247753902245800878298397829819244600259\
60945304748005444929411694097677373095316194496470938817202711690246\
79164873737588149815425937970573045094656554393364961182798975769812\
79063271606896233814472483059102258115803176451232829617731169473560\
56583472626947527000930777640604734587567158760154364347063261832083\
30385996594589042026405412914351169274159744595075192817784749916345\
62470152751910309001973543268287070146028018506822943624359351696941\
89166494104952290716061467283074936182290043354342490250743196513357\
17212673549917050251415008968860641379683205051131693384563804473690\
89903250787076735030486079965562026803790996240143092356323469108949\
07845535789793689147065546557522839031958055488735322364364131104340\
87166908595780193040642500443843720507588834041902825237277938594405\
15509518379205857942740777802594442587952768392559677020956217589081\
33581899255243337125974255338488475972519745646623282832498001302879\
97096502521398591719712234914109280948285965958478557415471893042412\
37475503214912860261669526560018289994451491775859964901871011582605\
60397222346597960243475095118473975946655966278677300109917282300025\
91196061133760791076031926996915150405486810283942043845416405992441\
04234755865756841005862837001581295460756719973524643902069661443476\
62959323040510506366321536923369435204548433728840037610657060117916\
95218686643134430952095557859827160438074418388249761882170083975363\
49979442098222565355493523403865857324728074954237197296535659279741\
76818946685603045371134466487089332172645850146950210739544416499959\
11699854986965051039658459578956685582448600003884615796462271186448\
17152459906468747763647302588605751100068841061137998158161515420480\
22318750114714645614691409738870229881884135960615681233518827274646\
97655884831524317196513396138604061144709084173127050169960969426206\
52655647298123938967996892262704749484308663243367637233409236395877\
16158838490461567162279329710757545371095127926752344490557461174904\
98350296783037094146290240832642344526951036992128964662104823342328\
54326936859341427510045192855933515626979981579879097216743613480412\
84130111347086326278853018443938104571356527897125855276423431718226\
89948184483964355088191096584486312766049989136785882316252089805747\
91742304600477823361721935335348605132172666045313701386462122287056\
68758394818039394561931249752372359921860235500907703617657471112468\
36477879522500385199108709199684161073878090521604160929658824487302\
08189162141752889696881176598927266776983392249528725466796126147755\
84837319880970278900349346884424939463657023804336647859408884059715\
87012385007902709564185245198547735808691732425755879909338114582324\
96496038851490551258638486060560640779848053453363726807356342381429\
06674320609564946079226292351275912040951590375532791423187152515437\
23852827475892552409562375800889091489173683224781236872060328011056\
48781494027495854853889407259647716580473257070974609155548989153057\
01770396652955542660500535945575049924043963937672274745980419440159\
73418948752580407334724228608155102768772518992593039260939482902676\
68501092440834712572791048398198968952196157492831517190068185690130\
54317743725067865519433837861089656827013210893936524514466555291774\
10118234887021100028017166818373039407738256677074456585169768128673\
31216559786733796846363998574307817534685493308372883174988103338379\
77555499797541822977140710754411379683506825653833835598576632482517\
06897089238260684742063540778170332874744726525838301125226609661605\
75675563264013373771866481097747281315582164490082018932862351602307\
75895597782979091503504290038602647497360256570951098586836413102875\
05985508624511969413092808738775819236922993770908434526013048298335\
63019052110438767283756977888399786317944181262208218736332067033822\
80782661106911795601344763359694750182233827973870280096262437147106\
21345220816897690852045590174605218233496926136141353580378360441714\
28438525233992119663994156239594488313118082243243369528158085152773\
57113378544700236891699113941209103476577008555151150115939550291435\
84311784078501339810706274047644249675445910838212985742593658736726\
05590639634037920190032975704406638099883233645741951743468840995139\
43095512100364094192434566607233069670007691516971518451704593177588\
61282246970125199204660143691272485688286787069963298843415512939777\
64698968031194340606574494573123788121878504563898097114591153445491\
29114045251097051865489399353650136868661016594913875104276448322279\
38508327655772735551923801839886882663244185808346800338063200999436\
16634873166641664790809023885607426914349049558044907612956164113179\
41293084012994951583428416228171274647443699568963003542273548716725\
17543291905739230393954548707021174633513110455440690091273680401298\
12811462097001540223298427500619842282324231271218044540375197467894\
28787621198614457986071126897232495087089840730512905845441161761976\
66601236384032968167285587365409796297465633367726141545996988226883\
94404671657814361092082070588158359501103729598165458354758606730331\
06290923381456909223490297830648362593407596156948828105259159998540\
44681640786318943172502512008752140731673485710162423305221273151554\
14015776177271915335460332199341190875273337813209488648738342833559\
09991792529769222004989099471330675361053443603329769538381697759223\
41487298533047095302388789420693497992006089184803515480781920674919\
09075112364663390621356691339916840245607264564259595373510560189888\
83101152955043503694233791483780253651442819969176278483653883495740\
57348801797457787746560339910935082336178277998340420138860067492161\
80813845520161575668483836859059768645273848264199471732826240207283\
38944009476728508602225488515628992665747699225194127625115010282470\
11255421483010324323934269992453569693406756352625863659617370205694\
46730077567953286193905468530935524416186408220535319273409812154850\
66824640573392916854142528081849040648607925797094385311506922861842\
29144703260429506651941695600111589700081612805239764675960599037895\
85277505278580936871197464961945900796506521050743626513365790652639\
56267995795043841000443373363843188371190067977723895217943323322350\
07131769451445041372122674930206828784929068233225437967059745018449\
24032625385535746044191547305282331530150508122071323064899819715044\
74449341068915282166440199819997121493518122097904841256853371980242\
48686646703791404029568587332628302419928168479892841143897873463368\
91001511064038809491058043208641187299641201395772810244836614652387\
82450681130790331970820232940957236616253594577206591272486713707415\
46948035707641090744852030891472775930637435026651131633879270089970\
44303247964187045852327022149531568482844729534374639100547599878437\
44909519052859764561719309116739679668953213767053177134351858393487\
62085012809637892432061609006747375297605894263669573918014684415911\
77903552657797646888181858087038285788571519109995872900507911395336\
80048417655055459938566880542365695507252330830042280914049463078624\
33569004674540996019078694725685882888530273965971773466249177582671\
42332603208213018856233359235015599937114645865169765977699011678178\
65491574334292488980604052665130357287858832893782241288755784638960\
64397859346154929859372879633696613249742905340795597385119890246889\
08688700640311194450755763678975202118000072107423667977807786843802\
46174591520518486946282593854915117798362423931239232306806408129269\
34708055912784899835082772799444653961132222086104558970432767747437\
88633596584638516429917747859701245255267497057587911651007806899367\
83605388585832329612519332348998714112329223819072111733578428201610\
89626170510883461035298725572775800706131604421628258178566484068261\
12405337928043939969536697946870334885024960249216783531029555972097\
84824503847059549111252017217901866557048983055500910349584743702027\
02270184957931102654283893318223648235659233326009586692028246496989\
60710329892077654990141054083454257677162385124341509709606214608731\
38194953833855587315682647117056971213294828892548510635009164117322\
69780817879546310416971723639232724179897303295326084797910865848021\
71103436912274354278556604836788582218736050493567224034486228435752\
75772545021730137777109249271305862854606379162479556321716369747012\
71058026509724749532545806263542358710308420248483382469723776037376\
69597983214319566329384729274790976182741310687825587124747694271202\
28994119273457226536530124689674046719121694781331975885866944397414\
80646928865900476175693828843742554200741632048619852118186250519076\
96565875277089012694058827876101297079720952161195398523023828552657\
02759085017247705446867703237841506390589295997796632748329114874936\
18403281978323594239953480189136997128462682656651813935559548642366\
91344303935616433794560077739844540045026897632503760550277165908180\
44396002251991670687351585740943555336338404437656999031317379460574\
33644039340780171677598011917530775848363921450425665793612984955814\
46229638868178745565157046098390502162983892266194312085128770307885\
03935195697010019173631562502099772732135285257616457457496713081114\
27698087930936134900937786460750887725990966034866935651522844738350\
67836613842467245269685348426064212529884648042396191418842320783973\
75995845907852205274837621277373785446822230566103387366537283783471\
14733090624177806365035413997882073568160227884766259995743233063926\
04323525627951228768897375175821617018283853002830565486213078784078\
55148910934828741195385502504757742265796083683664577440469374407863\
13164696065151429326584359520661070954626038065790919987475229950740\
98216024048599560662121214665212267608906887699061900342360030929097\
47880445733354436868505653643898815979415719223075312881714224290123\
41103905501102814618080271895011309165724524105825798203841299390522\
77992971203468621022598279406809300700081197021715469489274684846553\
77079370486851280632467450720757578010346887352264309727206549952369\
84430678997862148905029984576703819937255833785743720341765540435032\
96646736240918734453057541699910818180971797288574782433416947290678\
37280856433367250804218572773292211981900395475951298227991332978940\
27393755102812354289041266547584803540291969245091496543899626015439\
20544328434478996976635560702205616427714866475845230636742677201248\
54833564014964014561785203285877295747933756675009893281551897328021\
59418768491468356922541194834374009854217058462894766713723976242506\
33501980447527984054506287725044344865461692582424535946790342675202\
19477924778192351335239273036438409900357736968995545750602630916862\
07145824980908319494765273379305286696173544270167015094012422019461\
10110887380826756316024097822574773598557194695478247372939507966203\
29705858302812528783680908061271781318308853066172524646574009812058\
15491577412033628444516865373536840299843225279750680250512209287726\
70397253246630246078780479868717275510620978044054573646725585953242\
24758324770955832253706182177378996095677809200493210148738421043729\
74274161518014481783974080854045256838062599340760051731497627412507\
47265737662102660719976929447755810323498446434442537511040265468910\
43510141536688577299258638010109977110563868273874430671291803629871\
60935608539042562755537099055435404432514293203203439433284377871436\
57994132148348689166418229564255038075101142940868371859796958043423\
95574667099069464561787497638061471023478899430045148689551367991881\
21566086064763654052446414731052255138606247622016854079994875327395\
48336043017691288701099997564691519979028704748160129306878648076267\
78807483332466167739993336059393439458713795495027130913477137163967\
33212638853761959999943498955186589302026949447117881641750014115955\
94467826370160249803549647393175426177149199867597218424686918372730\
78980944010070138138080752013831258280466907055392611875371510020251\
51800106836557368069728552452932087455607278280099606979325749370959\
32140319187190721617428623235849046666769248377704247592637495100653\
16908459137057163937207803590262164206824274693991636821189334048631\
18357431296069511882893876953799136574175178784539883682427570859050\
23638256014536405998794647819608013589296597158733008320056824712260\
63549827856575391246729828051534769056050117993691741808160658338919\
44097905646550003580396419617760070019081705875625972878012366674679\
89292342512250048487425437546815015357199615226915228311396456047784\
77865786121932224656620803395855540010187517792883116941453865099079\
74150833888842573806312810859398218917803622873821251271610417946046\
11112073413623443045273514117087181250817162098103623756234695368183\
13329645002476824195759384817251427574077359703488481671707390563123\
29489572243615805666703488202767581029534591772098940413043218935233\
90863085401224517659534671566110922764069066448030558833184012635309\
67680593942113177332551690381005762329396768070186525893092140568792\
80842586082843501854057032456535635578215444814064662533030013057318\
31828990009857758497553071226979016224998850520128961978321074633694\
72596920941676631197534864178982171496812717822255063769725399908483\
22022524322928978677204857120686863585204689473401131106177840652358\
37371614145085538055371518912620992897032714169143489868354092566936\
48812775003327275943150768750860164679671172857179015820811479158914\
84122397219348846942722048529334135862982966040930598883092702070297\
01021054310366548846285483053033629752307019066118768758621856563205\
61077991767594949026864421630980354592182135940618795388702995460780\
15244528568453393510567298824950473694304626782827092561451548697001\
58655671621640122290190060058355755003380914495159377600243284934348\
30830232919737374256470494422199465871651077565986045910787485717984\
28640454849863473825645873938305511859807699766243416400243821342352\
03754512014015085697869209666106500847867745391449969654486637962121\
96099816021654477490828443488872228300302385780318236684548929433912\
93263596581118329352900643557103898820061908796437986587441214584341\
11988752772398357121525143168135648985355335801715938044069098157455\
59287951656187194689448537276786455279919640158591032349477352564508\
41323717085310676425390779501257241835410944478913727273009603729220\
56811212360534469226325897656316758584230613651821772025561754082913\
7151881915423973881943439830877204381696

files.

Greetings
Bernd
-- 
eckes privat - http://www.eckes.org/
Project Freefire - http://www.freefire.org/
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/