tcp_input.c 165 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341334233433344334533463347334833493350335133523353335433553356335733583359336033613362336333643365336633673368336933703371337233733374337533763377337833793380338133823383338433853386338733883389339033913392339333943395339633973398339934003401340234033404340534063407340834093410341134123413341434153416341734183419342034213422342334243425342634273428342934303431343234333434343534363437343834393440344134423443344434453446344734483449345034513452345334543455345634573458345934603461346234633464346534663467346834693470347134723473347434753476347734783479348034813482348334843485348634873488348934903491349234933494349534963497349834993500350135023503350435053506350735083509351035113512351335143515351635173518351935203521352235233524352535263527352835293530353135323533353435353536353735383539354035413542354335443545354635473548354935503551355235533554355535563557355835593560356135623563356435653566356735683569357035713572357335743575357635773578357935803581358235833584358535863587358835893590359135923593359435953596359735983599360036013602360336043605360636073608360936103611361236133614361536163617361836193620362136223623362436253626362736283629363036313632363336343635363636373638363936403641364236433644364536463647364836493650365136523653365436553656365736583659366036613662366336643665366636673668366936703671367236733674367536763677367836793680368136823683368436853686368736883689369036913692369336943695369636973698369937003701370237033704370537063707370837093710371137123713371437153716371737183719372037213722372337243725372637273728372937303731373237333734373537363737373837393740374137423743374437453746374737483749375037513752375337543755375637573758375937603761376237633764376537663767376837693770377137723773377437753776377737783779378037813782378337843785378637873788378937903791379237933794379537963797379837993800380138023803380438053806380738083809381038113812381338143815381638173818381938203821382238233824382538263827382838293830383138323833383438353836383738383839384038413842384338443845384638473848384938503851385238533854385538563857385838593860386138623863386438653866386738683869387038713872387338743875387638773878387938803881388238833884388538863887388838893890389138923893389438953896389738983899390039013902390339043905390639073908390939103911391239133914391539163917391839193920392139223923392439253926392739283929393039313932393339343935393639373938393939403941394239433944394539463947394839493950395139523953395439553956395739583959396039613962396339643965396639673968396939703971397239733974397539763977397839793980398139823983398439853986398739883989399039913992399339943995399639973998399940004001400240034004400540064007400840094010401140124013401440154016401740184019402040214022402340244025402640274028402940304031403240334034403540364037403840394040404140424043404440454046404740484049405040514052405340544055405640574058405940604061406240634064406540664067406840694070407140724073407440754076407740784079408040814082408340844085408640874088408940904091409240934094409540964097409840994100410141024103410441054106410741084109411041114112411341144115411641174118411941204121412241234124412541264127412841294130413141324133413441354136413741384139414041414142414341444145414641474148414941504151415241534154415541564157415841594160416141624163416441654166416741684169417041714172417341744175417641774178417941804181418241834184418541864187418841894190419141924193419441954196419741984199420042014202420342044205420642074208420942104211421242134214421542164217421842194220422142224223422442254226422742284229423042314232423342344235423642374238423942404241424242434244424542464247424842494250425142524253425442554256425742584259426042614262426342644265426642674268426942704271427242734274427542764277427842794280428142824283428442854286428742884289429042914292429342944295429642974298429943004301430243034304430543064307430843094310431143124313431443154316431743184319432043214322432343244325432643274328432943304331433243334334433543364337433843394340434143424343434443454346434743484349435043514352435343544355435643574358435943604361436243634364436543664367436843694370437143724373437443754376437743784379438043814382438343844385438643874388438943904391439243934394439543964397439843994400440144024403440444054406440744084409441044114412441344144415441644174418441944204421442244234424442544264427442844294430443144324433443444354436443744384439444044414442444344444445444644474448444944504451445244534454445544564457445844594460446144624463446444654466446744684469447044714472447344744475447644774478447944804481448244834484448544864487448844894490449144924493449444954496449744984499450045014502450345044505450645074508450945104511451245134514451545164517451845194520452145224523452445254526452745284529453045314532453345344535453645374538453945404541454245434544454545464547454845494550455145524553455445554556455745584559456045614562456345644565456645674568456945704571457245734574457545764577457845794580458145824583458445854586458745884589459045914592459345944595459645974598459946004601460246034604460546064607460846094610461146124613461446154616461746184619462046214622462346244625462646274628462946304631463246334634463546364637463846394640464146424643464446454646464746484649465046514652465346544655465646574658465946604661466246634664466546664667466846694670467146724673467446754676467746784679468046814682468346844685468646874688468946904691469246934694469546964697469846994700470147024703470447054706470747084709471047114712471347144715471647174718471947204721472247234724472547264727472847294730473147324733473447354736473747384739474047414742474347444745474647474748474947504751475247534754475547564757475847594760476147624763476447654766476747684769477047714772477347744775477647774778477947804781478247834784478547864787478847894790479147924793479447954796479747984799480048014802480348044805480648074808480948104811481248134814481548164817481848194820482148224823482448254826482748284829483048314832483348344835483648374838483948404841484248434844484548464847484848494850485148524853485448554856485748584859486048614862486348644865486648674868486948704871487248734874487548764877487848794880488148824883488448854886488748884889489048914892489348944895489648974898489949004901490249034904490549064907490849094910491149124913491449154916491749184919492049214922492349244925492649274928492949304931493249334934493549364937493849394940494149424943494449454946494749484949495049514952495349544955495649574958495949604961496249634964496549664967496849694970497149724973497449754976497749784979498049814982498349844985498649874988498949904991499249934994499549964997499849995000500150025003500450055006500750085009501050115012501350145015501650175018501950205021502250235024502550265027502850295030503150325033503450355036503750385039504050415042504350445045504650475048504950505051505250535054505550565057505850595060506150625063506450655066506750685069507050715072507350745075507650775078507950805081508250835084508550865087508850895090509150925093509450955096509750985099510051015102510351045105510651075108510951105111511251135114511551165117511851195120512151225123512451255126512751285129513051315132513351345135513651375138513951405141514251435144514551465147514851495150515151525153515451555156515751585159516051615162516351645165516651675168516951705171517251735174517551765177517851795180518151825183518451855186518751885189519051915192519351945195519651975198519952005201520252035204520552065207520852095210521152125213521452155216521752185219522052215222522352245225522652275228522952305231523252335234523552365237523852395240524152425243524452455246524752485249525052515252525352545255525652575258525952605261526252635264526552665267526852695270527152725273527452755276527752785279528052815282528352845285528652875288528952905291529252935294529552965297529852995300530153025303530453055306530753085309531053115312531353145315531653175318531953205321532253235324532553265327532853295330533153325333533453355336533753385339534053415342534353445345534653475348534953505351535253535354535553565357535853595360536153625363536453655366536753685369537053715372537353745375537653775378537953805381538253835384538553865387538853895390539153925393539453955396539753985399540054015402540354045405540654075408540954105411541254135414541554165417541854195420542154225423542454255426542754285429543054315432543354345435543654375438543954405441544254435444544554465447544854495450545154525453545454555456545754585459546054615462546354645465546654675468546954705471547254735474547554765477547854795480548154825483548454855486548754885489549054915492549354945495549654975498549955005501550255035504550555065507550855095510551155125513551455155516551755185519552055215522552355245525552655275528552955305531553255335534553555365537553855395540554155425543554455455546554755485549555055515552555355545555555655575558555955605561556255635564556555665567556855695570557155725573557455755576557755785579558055815582558355845585558655875588558955905591559255935594559555965597559855995600560156025603560456055606560756085609561056115612561356145615561656175618561956205621562256235624562556265627562856295630563156325633563456355636563756385639564056415642564356445645564656475648564956505651565256535654565556565657565856595660566156625663566456655666566756685669567056715672567356745675567656775678567956805681568256835684568556865687568856895690569156925693569456955696569756985699570057015702570357045705570657075708570957105711571257135714571557165717571857195720572157225723572457255726572757285729573057315732573357345735573657375738573957405741574257435744574557465747574857495750575157525753575457555756575757585759576057615762576357645765576657675768576957705771577257735774577557765777577857795780578157825783578457855786578757885789579057915792579357945795579657975798579958005801580258035804580558065807580858095810581158125813581458155816581758185819582058215822582358245825
  1. /*
  2. * INET An implementation of the TCP/IP protocol suite for the LINUX
  3. * operating system. INET is implemented using the BSD Socket
  4. * interface as the means of communication with the user level.
  5. *
  6. * Implementation of the Transmission Control Protocol(TCP).
  7. *
  8. * Authors: Ross Biro
  9. * Fred N. van Kempen, <waltje@uWalt.NL.Mugnet.ORG>
  10. * Mark Evans, <evansmp@uhura.aston.ac.uk>
  11. * Corey Minyard <wf-rch!minyard@relay.EU.net>
  12. * Florian La Roche, <flla@stud.uni-sb.de>
  13. * Charles Hedrick, <hedrick@klinzhai.rutgers.edu>
  14. * Linus Torvalds, <torvalds@cs.helsinki.fi>
  15. * Alan Cox, <gw4pts@gw4pts.ampr.org>
  16. * Matthew Dillon, <dillon@apollo.west.oic.com>
  17. * Arnt Gulbrandsen, <agulbra@nvg.unit.no>
  18. * Jorge Cwik, <jorge@laser.satlink.net>
  19. */
  20. /*
  21. * Changes:
  22. * Pedro Roque : Fast Retransmit/Recovery.
  23. * Two receive queues.
  24. * Retransmit queue handled by TCP.
  25. * Better retransmit timer handling.
  26. * New congestion avoidance.
  27. * Header prediction.
  28. * Variable renaming.
  29. *
  30. * Eric : Fast Retransmit.
  31. * Randy Scott : MSS option defines.
  32. * Eric Schenk : Fixes to slow start algorithm.
  33. * Eric Schenk : Yet another double ACK bug.
  34. * Eric Schenk : Delayed ACK bug fixes.
  35. * Eric Schenk : Floyd style fast retrans war avoidance.
  36. * David S. Miller : Don't allow zero congestion window.
  37. * Eric Schenk : Fix retransmitter so that it sends
  38. * next packet on ack of previous packet.
  39. * Andi Kleen : Moved open_request checking here
  40. * and process RSTs for open_requests.
  41. * Andi Kleen : Better prune_queue, and other fixes.
  42. * Andrey Savochkin: Fix RTT measurements in the presence of
  43. * timestamps.
  44. * Andrey Savochkin: Check sequence numbers correctly when
  45. * removing SACKs due to in sequence incoming
  46. * data segments.
  47. * Andi Kleen: Make sure we never ack data there is not
  48. * enough room for. Also make this condition
  49. * a fatal error if it might still happen.
  50. * Andi Kleen: Add tcp_measure_rcv_mss to make
  51. * connections with MSS<min(MTU,ann. MSS)
  52. * work without delayed acks.
  53. * Andi Kleen: Process packets with PSH set in the
  54. * fast path.
  55. * J Hadi Salim: ECN support
  56. * Andrei Gurtov,
  57. * Pasi Sarolahti,
  58. * Panu Kuhlberg: Experimental audit of TCP (re)transmission
  59. * engine. Lots of bugs are found.
  60. * Pasi Sarolahti: F-RTO for dealing with spurious RTOs
  61. */
  62. #include <linux/mm.h>
  63. #include <linux/module.h>
  64. #include <linux/sysctl.h>
  65. #include <net/dst.h>
  66. #include <net/tcp.h>
  67. #include <net/inet_common.h>
  68. #include <linux/ipsec.h>
  69. #include <asm/unaligned.h>
  70. #include <net/netdma.h>
  71. int sysctl_tcp_timestamps __read_mostly = 1;
  72. int sysctl_tcp_window_scaling __read_mostly = 1;
  73. int sysctl_tcp_sack __read_mostly = 1;
  74. int sysctl_tcp_fack __read_mostly = 1;
  75. int sysctl_tcp_reordering __read_mostly = TCP_FASTRETRANS_THRESH;
  76. int sysctl_tcp_ecn __read_mostly;
  77. int sysctl_tcp_dsack __read_mostly = 1;
  78. int sysctl_tcp_app_win __read_mostly = 31;
  79. int sysctl_tcp_adv_win_scale __read_mostly = 2;
  80. int sysctl_tcp_stdurg __read_mostly;
  81. int sysctl_tcp_rfc1337 __read_mostly;
  82. int sysctl_tcp_max_orphans __read_mostly = NR_FILE;
  83. int sysctl_tcp_frto __read_mostly = 2;
  84. int sysctl_tcp_frto_response __read_mostly;
  85. int sysctl_tcp_nometrics_save __read_mostly;
  86. int sysctl_tcp_moderate_rcvbuf __read_mostly = 1;
  87. int sysctl_tcp_abc __read_mostly;
  88. #define FLAG_DATA 0x01 /* Incoming frame contained data. */
  89. #define FLAG_WIN_UPDATE 0x02 /* Incoming ACK was a window update. */
  90. #define FLAG_DATA_ACKED 0x04 /* This ACK acknowledged new data. */
  91. #define FLAG_RETRANS_DATA_ACKED 0x08 /* "" "" some of which was retransmitted. */
  92. #define FLAG_SYN_ACKED 0x10 /* This ACK acknowledged SYN. */
  93. #define FLAG_DATA_SACKED 0x20 /* New SACK. */
  94. #define FLAG_ECE 0x40 /* ECE in this ACK */
  95. #define FLAG_DATA_LOST 0x80 /* SACK detected data lossage. */
  96. #define FLAG_SLOWPATH 0x100 /* Do not skip RFC checks for window update.*/
  97. #define FLAG_ONLY_ORIG_SACKED 0x200 /* SACKs only non-rexmit sent before RTO */
  98. #define FLAG_SND_UNA_ADVANCED 0x400 /* Snd_una was changed (!= FLAG_DATA_ACKED) */
  99. #define FLAG_DSACKING_ACK 0x800 /* SACK blocks contained D-SACK info */
  100. #define FLAG_NONHEAD_RETRANS_ACKED 0x1000 /* Non-head rexmitted data was ACKed */
  101. #define FLAG_SACK_RENEGING 0x2000 /* snd_una advanced to a sacked seq */
  102. #define FLAG_ACKED (FLAG_DATA_ACKED|FLAG_SYN_ACKED)
  103. #define FLAG_NOT_DUP (FLAG_DATA|FLAG_WIN_UPDATE|FLAG_ACKED)
  104. #define FLAG_CA_ALERT (FLAG_DATA_SACKED|FLAG_ECE)
  105. #define FLAG_FORWARD_PROGRESS (FLAG_ACKED|FLAG_DATA_SACKED)
  106. #define FLAG_ANY_PROGRESS (FLAG_FORWARD_PROGRESS|FLAG_SND_UNA_ADVANCED)
  107. #define TCP_REMNANT (TCP_FLAG_FIN|TCP_FLAG_URG|TCP_FLAG_SYN|TCP_FLAG_PSH)
  108. #define TCP_HP_BITS (~(TCP_RESERVED_BITS|TCP_FLAG_PSH))
  109. /* Adapt the MSS value used to make delayed ack decision to the
  110. * real world.
  111. */
  112. static void tcp_measure_rcv_mss(struct sock *sk, const struct sk_buff *skb)
  113. {
  114. struct inet_connection_sock *icsk = inet_csk(sk);
  115. const unsigned int lss = icsk->icsk_ack.last_seg_size;
  116. unsigned int len;
  117. icsk->icsk_ack.last_seg_size = 0;
  118. /* skb->len may jitter because of SACKs, even if peer
  119. * sends good full-sized frames.
  120. */
  121. len = skb_shinfo(skb)->gso_size ? : skb->len;
  122. if (len >= icsk->icsk_ack.rcv_mss) {
  123. icsk->icsk_ack.rcv_mss = len;
  124. } else {
  125. /* Otherwise, we make more careful check taking into account,
  126. * that SACKs block is variable.
  127. *
  128. * "len" is invariant segment length, including TCP header.
  129. */
  130. len += skb->data - skb_transport_header(skb);
  131. if (len >= TCP_MIN_RCVMSS + sizeof(struct tcphdr) ||
  132. /* If PSH is not set, packet should be
  133. * full sized, provided peer TCP is not badly broken.
  134. * This observation (if it is correct 8)) allows
  135. * to handle super-low mtu links fairly.
  136. */
  137. (len >= TCP_MIN_MSS + sizeof(struct tcphdr) &&
  138. !(tcp_flag_word(tcp_hdr(skb)) & TCP_REMNANT))) {
  139. /* Subtract also invariant (if peer is RFC compliant),
  140. * tcp header plus fixed timestamp option length.
  141. * Resulting "len" is MSS free of SACK jitter.
  142. */
  143. len -= tcp_sk(sk)->tcp_header_len;
  144. icsk->icsk_ack.last_seg_size = len;
  145. if (len == lss) {
  146. icsk->icsk_ack.rcv_mss = len;
  147. return;
  148. }
  149. }
  150. if (icsk->icsk_ack.pending & ICSK_ACK_PUSHED)
  151. icsk->icsk_ack.pending |= ICSK_ACK_PUSHED2;
  152. icsk->icsk_ack.pending |= ICSK_ACK_PUSHED;
  153. }
  154. }
  155. static void tcp_incr_quickack(struct sock *sk)
  156. {
  157. struct inet_connection_sock *icsk = inet_csk(sk);
  158. unsigned quickacks = tcp_sk(sk)->rcv_wnd / (2 * icsk->icsk_ack.rcv_mss);
  159. if (quickacks == 0)
  160. quickacks = 2;
  161. if (quickacks > icsk->icsk_ack.quick)
  162. icsk->icsk_ack.quick = min(quickacks, TCP_MAX_QUICKACKS);
  163. }
  164. void tcp_enter_quickack_mode(struct sock *sk)
  165. {
  166. struct inet_connection_sock *icsk = inet_csk(sk);
  167. tcp_incr_quickack(sk);
  168. icsk->icsk_ack.pingpong = 0;
  169. icsk->icsk_ack.ato = TCP_ATO_MIN;
  170. }
  171. /* Send ACKs quickly, if "quick" count is not exhausted
  172. * and the session is not interactive.
  173. */
  174. static inline int tcp_in_quickack_mode(const struct sock *sk)
  175. {
  176. const struct inet_connection_sock *icsk = inet_csk(sk);
  177. return icsk->icsk_ack.quick && !icsk->icsk_ack.pingpong;
  178. }
  179. static inline void TCP_ECN_queue_cwr(struct tcp_sock *tp)
  180. {
  181. if (tp->ecn_flags & TCP_ECN_OK)
  182. tp->ecn_flags |= TCP_ECN_QUEUE_CWR;
  183. }
  184. static inline void TCP_ECN_accept_cwr(struct tcp_sock *tp, struct sk_buff *skb)
  185. {
  186. if (tcp_hdr(skb)->cwr)
  187. tp->ecn_flags &= ~TCP_ECN_DEMAND_CWR;
  188. }
  189. static inline void TCP_ECN_withdraw_cwr(struct tcp_sock *tp)
  190. {
  191. tp->ecn_flags &= ~TCP_ECN_DEMAND_CWR;
  192. }
  193. static inline void TCP_ECN_check_ce(struct tcp_sock *tp, struct sk_buff *skb)
  194. {
  195. if (tp->ecn_flags & TCP_ECN_OK) {
  196. if (INET_ECN_is_ce(TCP_SKB_CB(skb)->flags))
  197. tp->ecn_flags |= TCP_ECN_DEMAND_CWR;
  198. /* Funny extension: if ECT is not set on a segment,
  199. * it is surely retransmit. It is not in ECN RFC,
  200. * but Linux follows this rule. */
  201. else if (INET_ECN_is_not_ect((TCP_SKB_CB(skb)->flags)))
  202. tcp_enter_quickack_mode((struct sock *)tp);
  203. }
  204. }
  205. static inline void TCP_ECN_rcv_synack(struct tcp_sock *tp, struct tcphdr *th)
  206. {
  207. if ((tp->ecn_flags & TCP_ECN_OK) && (!th->ece || th->cwr))
  208. tp->ecn_flags &= ~TCP_ECN_OK;
  209. }
  210. static inline void TCP_ECN_rcv_syn(struct tcp_sock *tp, struct tcphdr *th)
  211. {
  212. if ((tp->ecn_flags & TCP_ECN_OK) && (!th->ece || !th->cwr))
  213. tp->ecn_flags &= ~TCP_ECN_OK;
  214. }
  215. static inline int TCP_ECN_rcv_ecn_echo(struct tcp_sock *tp, struct tcphdr *th)
  216. {
  217. if (th->ece && !th->syn && (tp->ecn_flags & TCP_ECN_OK))
  218. return 1;
  219. return 0;
  220. }
  221. /* Buffer size and advertised window tuning.
  222. *
  223. * 1. Tuning sk->sk_sndbuf, when connection enters established state.
  224. */
  225. static void tcp_fixup_sndbuf(struct sock *sk)
  226. {
  227. int sndmem = tcp_sk(sk)->rx_opt.mss_clamp + MAX_TCP_HEADER + 16 +
  228. sizeof(struct sk_buff);
  229. if (sk->sk_sndbuf < 3 * sndmem)
  230. sk->sk_sndbuf = min(3 * sndmem, sysctl_tcp_wmem[2]);
  231. }
  232. /* 2. Tuning advertised window (window_clamp, rcv_ssthresh)
  233. *
  234. * All tcp_full_space() is split to two parts: "network" buffer, allocated
  235. * forward and advertised in receiver window (tp->rcv_wnd) and
  236. * "application buffer", required to isolate scheduling/application
  237. * latencies from network.
  238. * window_clamp is maximal advertised window. It can be less than
  239. * tcp_full_space(), in this case tcp_full_space() - window_clamp
  240. * is reserved for "application" buffer. The less window_clamp is
  241. * the smoother our behaviour from viewpoint of network, but the lower
  242. * throughput and the higher sensitivity of the connection to losses. 8)
  243. *
  244. * rcv_ssthresh is more strict window_clamp used at "slow start"
  245. * phase to predict further behaviour of this connection.
  246. * It is used for two goals:
  247. * - to enforce header prediction at sender, even when application
  248. * requires some significant "application buffer". It is check #1.
  249. * - to prevent pruning of receive queue because of misprediction
  250. * of receiver window. Check #2.
  251. *
  252. * The scheme does not work when sender sends good segments opening
  253. * window and then starts to feed us spaghetti. But it should work
  254. * in common situations. Otherwise, we have to rely on queue collapsing.
  255. */
  256. /* Slow part of check#2. */
  257. static int __tcp_grow_window(const struct sock *sk, const struct sk_buff *skb)
  258. {
  259. struct tcp_sock *tp = tcp_sk(sk);
  260. /* Optimize this! */
  261. int truesize = tcp_win_from_space(skb->truesize) >> 1;
  262. int window = tcp_win_from_space(sysctl_tcp_rmem[2]) >> 1;
  263. while (tp->rcv_ssthresh <= window) {
  264. if (truesize <= skb->len)
  265. return 2 * inet_csk(sk)->icsk_ack.rcv_mss;
  266. truesize >>= 1;
  267. window >>= 1;
  268. }
  269. return 0;
  270. }
  271. static void tcp_grow_window(struct sock *sk, struct sk_buff *skb)
  272. {
  273. struct tcp_sock *tp = tcp_sk(sk);
  274. /* Check #1 */
  275. if (tp->rcv_ssthresh < tp->window_clamp &&
  276. (int)tp->rcv_ssthresh < tcp_space(sk) &&
  277. !tcp_memory_pressure) {
  278. int incr;
  279. /* Check #2. Increase window, if skb with such overhead
  280. * will fit to rcvbuf in future.
  281. */
  282. if (tcp_win_from_space(skb->truesize) <= skb->len)
  283. incr = 2 * tp->advmss;
  284. else
  285. incr = __tcp_grow_window(sk, skb);
  286. if (incr) {
  287. tp->rcv_ssthresh = min(tp->rcv_ssthresh + incr,
  288. tp->window_clamp);
  289. inet_csk(sk)->icsk_ack.quick |= 1;
  290. }
  291. }
  292. }
  293. /* 3. Tuning rcvbuf, when connection enters established state. */
  294. static void tcp_fixup_rcvbuf(struct sock *sk)
  295. {
  296. struct tcp_sock *tp = tcp_sk(sk);
  297. int rcvmem = tp->advmss + MAX_TCP_HEADER + 16 + sizeof(struct sk_buff);
  298. /* Try to select rcvbuf so that 4 mss-sized segments
  299. * will fit to window and corresponding skbs will fit to our rcvbuf.
  300. * (was 3; 4 is minimum to allow fast retransmit to work.)
  301. */
  302. while (tcp_win_from_space(rcvmem) < tp->advmss)
  303. rcvmem += 128;
  304. if (sk->sk_rcvbuf < 4 * rcvmem)
  305. sk->sk_rcvbuf = min(4 * rcvmem, sysctl_tcp_rmem[2]);
  306. }
  307. /* 4. Try to fixup all. It is made immediately after connection enters
  308. * established state.
  309. */
  310. static void tcp_init_buffer_space(struct sock *sk)
  311. {
  312. struct tcp_sock *tp = tcp_sk(sk);
  313. int maxwin;
  314. if (!(sk->sk_userlocks & SOCK_RCVBUF_LOCK))
  315. tcp_fixup_rcvbuf(sk);
  316. if (!(sk->sk_userlocks & SOCK_SNDBUF_LOCK))
  317. tcp_fixup_sndbuf(sk);
  318. tp->rcvq_space.space = tp->rcv_wnd;
  319. maxwin = tcp_full_space(sk);
  320. if (tp->window_clamp >= maxwin) {
  321. tp->window_clamp = maxwin;
  322. if (sysctl_tcp_app_win && maxwin > 4 * tp->advmss)
  323. tp->window_clamp = max(maxwin -
  324. (maxwin >> sysctl_tcp_app_win),
  325. 4 * tp->advmss);
  326. }
  327. /* Force reservation of one segment. */
  328. if (sysctl_tcp_app_win &&
  329. tp->window_clamp > 2 * tp->advmss &&
  330. tp->window_clamp + tp->advmss > maxwin)
  331. tp->window_clamp = max(2 * tp->advmss, maxwin - tp->advmss);
  332. tp->rcv_ssthresh = min(tp->rcv_ssthresh, tp->window_clamp);
  333. tp->snd_cwnd_stamp = tcp_time_stamp;
  334. }
  335. /* 5. Recalculate window clamp after socket hit its memory bounds. */
  336. static void tcp_clamp_window(struct sock *sk)
  337. {
  338. struct tcp_sock *tp = tcp_sk(sk);
  339. struct inet_connection_sock *icsk = inet_csk(sk);
  340. icsk->icsk_ack.quick = 0;
  341. if (sk->sk_rcvbuf < sysctl_tcp_rmem[2] &&
  342. !(sk->sk_userlocks & SOCK_RCVBUF_LOCK) &&
  343. !tcp_memory_pressure &&
  344. atomic_read(&tcp_memory_allocated) < sysctl_tcp_mem[0]) {
  345. sk->sk_rcvbuf = min(atomic_read(&sk->sk_rmem_alloc),
  346. sysctl_tcp_rmem[2]);
  347. }
  348. if (atomic_read(&sk->sk_rmem_alloc) > sk->sk_rcvbuf)
  349. tp->rcv_ssthresh = min(tp->window_clamp, 2U * tp->advmss);
  350. }
  351. /* Initialize RCV_MSS value.
  352. * RCV_MSS is an our guess about MSS used by the peer.
  353. * We haven't any direct information about the MSS.
  354. * It's better to underestimate the RCV_MSS rather than overestimate.
  355. * Overestimations make us ACKing less frequently than needed.
  356. * Underestimations are more easy to detect and fix by tcp_measure_rcv_mss().
  357. */
  358. void tcp_initialize_rcv_mss(struct sock *sk)
  359. {
  360. struct tcp_sock *tp = tcp_sk(sk);
  361. unsigned int hint = min_t(unsigned int, tp->advmss, tp->mss_cache);
  362. hint = min(hint, tp->rcv_wnd / 2);
  363. hint = min(hint, TCP_MIN_RCVMSS);
  364. hint = max(hint, TCP_MIN_MSS);
  365. inet_csk(sk)->icsk_ack.rcv_mss = hint;
  366. }
  367. /* Receiver "autotuning" code.
  368. *
  369. * The algorithm for RTT estimation w/o timestamps is based on
  370. * Dynamic Right-Sizing (DRS) by Wu Feng and Mike Fisk of LANL.
  371. * <http://www.lanl.gov/radiant/website/pubs/drs/lacsi2001.ps>
  372. *
  373. * More detail on this code can be found at
  374. * <http://www.psc.edu/~jheffner/senior_thesis.ps>,
  375. * though this reference is out of date. A new paper
  376. * is pending.
  377. */
  378. static void tcp_rcv_rtt_update(struct tcp_sock *tp, u32 sample, int win_dep)
  379. {
  380. u32 new_sample = tp->rcv_rtt_est.rtt;
  381. long m = sample;
  382. if (m == 0)
  383. m = 1;
  384. if (new_sample != 0) {
  385. /* If we sample in larger samples in the non-timestamp
  386. * case, we could grossly overestimate the RTT especially
  387. * with chatty applications or bulk transfer apps which
  388. * are stalled on filesystem I/O.
  389. *
  390. * Also, since we are only going for a minimum in the
  391. * non-timestamp case, we do not smooth things out
  392. * else with timestamps disabled convergence takes too
  393. * long.
  394. */
  395. if (!win_dep) {
  396. m -= (new_sample >> 3);
  397. new_sample += m;
  398. } else if (m < new_sample)
  399. new_sample = m << 3;
  400. } else {
  401. /* No previous measure. */
  402. new_sample = m << 3;
  403. }
  404. if (tp->rcv_rtt_est.rtt != new_sample)
  405. tp->rcv_rtt_est.rtt = new_sample;
  406. }
  407. static inline void tcp_rcv_rtt_measure(struct tcp_sock *tp)
  408. {
  409. if (tp->rcv_rtt_est.time == 0)
  410. goto new_measure;
  411. if (before(tp->rcv_nxt, tp->rcv_rtt_est.seq))
  412. return;
  413. tcp_rcv_rtt_update(tp, jiffies - tp->rcv_rtt_est.time, 1);
  414. new_measure:
  415. tp->rcv_rtt_est.seq = tp->rcv_nxt + tp->rcv_wnd;
  416. tp->rcv_rtt_est.time = tcp_time_stamp;
  417. }
  418. static inline void tcp_rcv_rtt_measure_ts(struct sock *sk,
  419. const struct sk_buff *skb)
  420. {
  421. struct tcp_sock *tp = tcp_sk(sk);
  422. if (tp->rx_opt.rcv_tsecr &&
  423. (TCP_SKB_CB(skb)->end_seq -
  424. TCP_SKB_CB(skb)->seq >= inet_csk(sk)->icsk_ack.rcv_mss))
  425. tcp_rcv_rtt_update(tp, tcp_time_stamp - tp->rx_opt.rcv_tsecr, 0);
  426. }
  427. /*
  428. * This function should be called every time data is copied to user space.
  429. * It calculates the appropriate TCP receive buffer space.
  430. */
  431. void tcp_rcv_space_adjust(struct sock *sk)
  432. {
  433. struct tcp_sock *tp = tcp_sk(sk);
  434. int time;
  435. int space;
  436. if (tp->rcvq_space.time == 0)
  437. goto new_measure;
  438. time = tcp_time_stamp - tp->rcvq_space.time;
  439. if (time < (tp->rcv_rtt_est.rtt >> 3) || tp->rcv_rtt_est.rtt == 0)
  440. return;
  441. space = 2 * (tp->copied_seq - tp->rcvq_space.seq);
  442. space = max(tp->rcvq_space.space, space);
  443. if (tp->rcvq_space.space != space) {
  444. int rcvmem;
  445. tp->rcvq_space.space = space;
  446. if (sysctl_tcp_moderate_rcvbuf &&
  447. !(sk->sk_userlocks & SOCK_RCVBUF_LOCK)) {
  448. int new_clamp = space;
  449. /* Receive space grows, normalize in order to
  450. * take into account packet headers and sk_buff
  451. * structure overhead.
  452. */
  453. space /= tp->advmss;
  454. if (!space)
  455. space = 1;
  456. rcvmem = (tp->advmss + MAX_TCP_HEADER +
  457. 16 + sizeof(struct sk_buff));
  458. while (tcp_win_from_space(rcvmem) < tp->advmss)
  459. rcvmem += 128;
  460. space *= rcvmem;
  461. space = min(space, sysctl_tcp_rmem[2]);
  462. if (space > sk->sk_rcvbuf) {
  463. sk->sk_rcvbuf = space;
  464. /* Make the window clamp follow along. */
  465. tp->window_clamp = new_clamp;
  466. }
  467. }
  468. }
  469. new_measure:
  470. tp->rcvq_space.seq = tp->copied_seq;
  471. tp->rcvq_space.time = tcp_time_stamp;
  472. }
  473. /* There is something which you must keep in mind when you analyze the
  474. * behavior of the tp->ato delayed ack timeout interval. When a
  475. * connection starts up, we want to ack as quickly as possible. The
  476. * problem is that "good" TCP's do slow start at the beginning of data
  477. * transmission. The means that until we send the first few ACK's the
  478. * sender will sit on his end and only queue most of his data, because
  479. * he can only send snd_cwnd unacked packets at any given time. For
  480. * each ACK we send, he increments snd_cwnd and transmits more of his
  481. * queue. -DaveM
  482. */
  483. static void tcp_event_data_recv(struct sock *sk, struct sk_buff *skb)
  484. {
  485. struct tcp_sock *tp = tcp_sk(sk);
  486. struct inet_connection_sock *icsk = inet_csk(sk);
  487. u32 now;
  488. inet_csk_schedule_ack(sk);
  489. tcp_measure_rcv_mss(sk, skb);
  490. tcp_rcv_rtt_measure(tp);
  491. now = tcp_time_stamp;
  492. if (!icsk->icsk_ack.ato) {
  493. /* The _first_ data packet received, initialize
  494. * delayed ACK engine.
  495. */
  496. tcp_incr_quickack(sk);
  497. icsk->icsk_ack.ato = TCP_ATO_MIN;
  498. } else {
  499. int m = now - icsk->icsk_ack.lrcvtime;
  500. if (m <= TCP_ATO_MIN / 2) {
  501. /* The fastest case is the first. */
  502. icsk->icsk_ack.ato = (icsk->icsk_ack.ato >> 1) + TCP_ATO_MIN / 2;
  503. } else if (m < icsk->icsk_ack.ato) {
  504. icsk->icsk_ack.ato = (icsk->icsk_ack.ato >> 1) + m;
  505. if (icsk->icsk_ack.ato > icsk->icsk_rto)
  506. icsk->icsk_ack.ato = icsk->icsk_rto;
  507. } else if (m > icsk->icsk_rto) {
  508. /* Too long gap. Apparently sender failed to
  509. * restart window, so that we send ACKs quickly.
  510. */
  511. tcp_incr_quickack(sk);
  512. sk_mem_reclaim(sk);
  513. }
  514. }
  515. icsk->icsk_ack.lrcvtime = now;
  516. TCP_ECN_check_ce(tp, skb);
  517. if (skb->len >= 128)
  518. tcp_grow_window(sk, skb);
  519. }
  520. static u32 tcp_rto_min(struct sock *sk)
  521. {
  522. struct dst_entry *dst = __sk_dst_get(sk);
  523. u32 rto_min = TCP_RTO_MIN;
  524. if (dst && dst_metric_locked(dst, RTAX_RTO_MIN))
  525. rto_min = dst_metric_rtt(dst, RTAX_RTO_MIN);
  526. return rto_min;
  527. }
  528. /* Called to compute a smoothed rtt estimate. The data fed to this
  529. * routine either comes from timestamps, or from segments that were
  530. * known _not_ to have been retransmitted [see Karn/Partridge
  531. * Proceedings SIGCOMM 87]. The algorithm is from the SIGCOMM 88
  532. * piece by Van Jacobson.
  533. * NOTE: the next three routines used to be one big routine.
  534. * To save cycles in the RFC 1323 implementation it was better to break
  535. * it up into three procedures. -- erics
  536. */
  537. static void tcp_rtt_estimator(struct sock *sk, const __u32 mrtt)
  538. {
  539. struct tcp_sock *tp = tcp_sk(sk);
  540. long m = mrtt; /* RTT */
  541. /* The following amusing code comes from Jacobson's
  542. * article in SIGCOMM '88. Note that rtt and mdev
  543. * are scaled versions of rtt and mean deviation.
  544. * This is designed to be as fast as possible
  545. * m stands for "measurement".
  546. *
  547. * On a 1990 paper the rto value is changed to:
  548. * RTO = rtt + 4 * mdev
  549. *
  550. * Funny. This algorithm seems to be very broken.
  551. * These formulae increase RTO, when it should be decreased, increase
  552. * too slowly, when it should be increased quickly, decrease too quickly
  553. * etc. I guess in BSD RTO takes ONE value, so that it is absolutely
  554. * does not matter how to _calculate_ it. Seems, it was trap
  555. * that VJ failed to avoid. 8)
  556. */
  557. if (m == 0)
  558. m = 1;
  559. if (tp->srtt != 0) {
  560. m -= (tp->srtt >> 3); /* m is now error in rtt est */
  561. tp->srtt += m; /* rtt = 7/8 rtt + 1/8 new */
  562. if (m < 0) {
  563. m = -m; /* m is now abs(error) */
  564. m -= (tp->mdev >> 2); /* similar update on mdev */
  565. /* This is similar to one of Eifel findings.
  566. * Eifel blocks mdev updates when rtt decreases.
  567. * This solution is a bit different: we use finer gain
  568. * for mdev in this case (alpha*beta).
  569. * Like Eifel it also prevents growth of rto,
  570. * but also it limits too fast rto decreases,
  571. * happening in pure Eifel.
  572. */
  573. if (m > 0)
  574. m >>= 3;
  575. } else {
  576. m -= (tp->mdev >> 2); /* similar update on mdev */
  577. }
  578. tp->mdev += m; /* mdev = 3/4 mdev + 1/4 new */
  579. if (tp->mdev > tp->mdev_max) {
  580. tp->mdev_max = tp->mdev;
  581. if (tp->mdev_max > tp->rttvar)
  582. tp->rttvar = tp->mdev_max;
  583. }
  584. if (after(tp->snd_una, tp->rtt_seq)) {
  585. if (tp->mdev_max < tp->rttvar)
  586. tp->rttvar -= (tp->rttvar - tp->mdev_max) >> 2;
  587. tp->rtt_seq = tp->snd_nxt;
  588. tp->mdev_max = tcp_rto_min(sk);
  589. }
  590. } else {
  591. /* no previous measure. */
  592. tp->srtt = m << 3; /* take the measured time to be rtt */
  593. tp->mdev = m << 1; /* make sure rto = 3*rtt */
  594. tp->mdev_max = tp->rttvar = max(tp->mdev, tcp_rto_min(sk));
  595. tp->rtt_seq = tp->snd_nxt;
  596. }
  597. }
  598. /* Calculate rto without backoff. This is the second half of Van Jacobson's
  599. * routine referred to above.
  600. */
  601. static inline void tcp_set_rto(struct sock *sk)
  602. {
  603. const struct tcp_sock *tp = tcp_sk(sk);
  604. /* Old crap is replaced with new one. 8)
  605. *
  606. * More seriously:
  607. * 1. If rtt variance happened to be less 50msec, it is hallucination.
  608. * It cannot be less due to utterly erratic ACK generation made
  609. * at least by solaris and freebsd. "Erratic ACKs" has _nothing_
  610. * to do with delayed acks, because at cwnd>2 true delack timeout
  611. * is invisible. Actually, Linux-2.4 also generates erratic
  612. * ACKs in some circumstances.
  613. */
  614. inet_csk(sk)->icsk_rto = (tp->srtt >> 3) + tp->rttvar;
  615. /* 2. Fixups made earlier cannot be right.
  616. * If we do not estimate RTO correctly without them,
  617. * all the algo is pure shit and should be replaced
  618. * with correct one. It is exactly, which we pretend to do.
  619. */
  620. }
  621. /* NOTE: clamping at TCP_RTO_MIN is not required, current algo
  622. * guarantees that rto is higher.
  623. */
  624. static inline void tcp_bound_rto(struct sock *sk)
  625. {
  626. if (inet_csk(sk)->icsk_rto > TCP_RTO_MAX)
  627. inet_csk(sk)->icsk_rto = TCP_RTO_MAX;
  628. }
  629. /* Save metrics learned by this TCP session.
  630. This function is called only, when TCP finishes successfully
  631. i.e. when it enters TIME-WAIT or goes from LAST-ACK to CLOSE.
  632. */
  633. void tcp_update_metrics(struct sock *sk)
  634. {
  635. struct tcp_sock *tp = tcp_sk(sk);
  636. struct dst_entry *dst = __sk_dst_get(sk);
  637. if (sysctl_tcp_nometrics_save)
  638. return;
  639. dst_confirm(dst);
  640. if (dst && (dst->flags & DST_HOST)) {
  641. const struct inet_connection_sock *icsk = inet_csk(sk);
  642. int m;
  643. unsigned long rtt;
  644. if (icsk->icsk_backoff || !tp->srtt) {
  645. /* This session failed to estimate rtt. Why?
  646. * Probably, no packets returned in time.
  647. * Reset our results.
  648. */
  649. if (!(dst_metric_locked(dst, RTAX_RTT)))
  650. dst->metrics[RTAX_RTT - 1] = 0;
  651. return;
  652. }
  653. rtt = dst_metric_rtt(dst, RTAX_RTT);
  654. m = rtt - tp->srtt;
  655. /* If newly calculated rtt larger than stored one,
  656. * store new one. Otherwise, use EWMA. Remember,
  657. * rtt overestimation is always better than underestimation.
  658. */
  659. if (!(dst_metric_locked(dst, RTAX_RTT))) {
  660. if (m <= 0)
  661. set_dst_metric_rtt(dst, RTAX_RTT, tp->srtt);
  662. else
  663. set_dst_metric_rtt(dst, RTAX_RTT, rtt - (m >> 3));
  664. }
  665. if (!(dst_metric_locked(dst, RTAX_RTTVAR))) {
  666. unsigned long var;
  667. if (m < 0)
  668. m = -m;
  669. /* Scale deviation to rttvar fixed point */
  670. m >>= 1;
  671. if (m < tp->mdev)
  672. m = tp->mdev;
  673. var = dst_metric_rtt(dst, RTAX_RTTVAR);
  674. if (m >= var)
  675. var = m;
  676. else
  677. var -= (var - m) >> 2;
  678. set_dst_metric_rtt(dst, RTAX_RTTVAR, var);
  679. }
  680. if (tp->snd_ssthresh >= 0xFFFF) {
  681. /* Slow start still did not finish. */
  682. if (dst_metric(dst, RTAX_SSTHRESH) &&
  683. !dst_metric_locked(dst, RTAX_SSTHRESH) &&
  684. (tp->snd_cwnd >> 1) > dst_metric(dst, RTAX_SSTHRESH))
  685. dst->metrics[RTAX_SSTHRESH-1] = tp->snd_cwnd >> 1;
  686. if (!dst_metric_locked(dst, RTAX_CWND) &&
  687. tp->snd_cwnd > dst_metric(dst, RTAX_CWND))
  688. dst->metrics[RTAX_CWND - 1] = tp->snd_cwnd;
  689. } else if (tp->snd_cwnd > tp->snd_ssthresh &&
  690. icsk->icsk_ca_state == TCP_CA_Open) {
  691. /* Cong. avoidance phase, cwnd is reliable. */
  692. if (!dst_metric_locked(dst, RTAX_SSTHRESH))
  693. dst->metrics[RTAX_SSTHRESH-1] =
  694. max(tp->snd_cwnd >> 1, tp->snd_ssthresh);
  695. if (!dst_metric_locked(dst, RTAX_CWND))
  696. dst->metrics[RTAX_CWND-1] = (dst_metric(dst, RTAX_CWND) + tp->snd_cwnd) >> 1;
  697. } else {
  698. /* Else slow start did not finish, cwnd is non-sense,
  699. ssthresh may be also invalid.
  700. */
  701. if (!dst_metric_locked(dst, RTAX_CWND))
  702. dst->metrics[RTAX_CWND-1] = (dst_metric(dst, RTAX_CWND) + tp->snd_ssthresh) >> 1;
  703. if (dst_metric(dst, RTAX_SSTHRESH) &&
  704. !dst_metric_locked(dst, RTAX_SSTHRESH) &&
  705. tp->snd_ssthresh > dst_metric(dst, RTAX_SSTHRESH))
  706. dst->metrics[RTAX_SSTHRESH-1] = tp->snd_ssthresh;
  707. }
  708. if (!dst_metric_locked(dst, RTAX_REORDERING)) {
  709. if (dst_metric(dst, RTAX_REORDERING) < tp->reordering &&
  710. tp->reordering != sysctl_tcp_reordering)
  711. dst->metrics[RTAX_REORDERING-1] = tp->reordering;
  712. }
  713. }
  714. }
  715. /* Numbers are taken from RFC3390.
  716. *
  717. * John Heffner states:
  718. *
  719. * The RFC specifies a window of no more than 4380 bytes
  720. * unless 2*MSS > 4380. Reading the pseudocode in the RFC
  721. * is a bit misleading because they use a clamp at 4380 bytes
  722. * rather than use a multiplier in the relevant range.
  723. */
  724. __u32 tcp_init_cwnd(struct tcp_sock *tp, struct dst_entry *dst)
  725. {
  726. __u32 cwnd = (dst ? dst_metric(dst, RTAX_INITCWND) : 0);
  727. if (!cwnd) {
  728. if (tp->mss_cache > 1460)
  729. cwnd = 2;
  730. else
  731. cwnd = (tp->mss_cache > 1095) ? 3 : 4;
  732. }
  733. return min_t(__u32, cwnd, tp->snd_cwnd_clamp);
  734. }
  735. /* Set slow start threshold and cwnd not falling to slow start */
  736. void tcp_enter_cwr(struct sock *sk, const int set_ssthresh)
  737. {
  738. struct tcp_sock *tp = tcp_sk(sk);
  739. const struct inet_connection_sock *icsk = inet_csk(sk);
  740. tp->prior_ssthresh = 0;
  741. tp->bytes_acked = 0;
  742. if (icsk->icsk_ca_state < TCP_CA_CWR) {
  743. tp->undo_marker = 0;
  744. if (set_ssthresh)
  745. tp->snd_ssthresh = icsk->icsk_ca_ops->ssthresh(sk);
  746. tp->snd_cwnd = min(tp->snd_cwnd,
  747. tcp_packets_in_flight(tp) + 1U);
  748. tp->snd_cwnd_cnt = 0;
  749. tp->high_seq = tp->snd_nxt;
  750. tp->snd_cwnd_stamp = tcp_time_stamp;
  751. TCP_ECN_queue_cwr(tp);
  752. tcp_set_ca_state(sk, TCP_CA_CWR);
  753. }
  754. }
  755. /*
  756. * Packet counting of FACK is based on in-order assumptions, therefore TCP
  757. * disables it when reordering is detected
  758. */
  759. static void tcp_disable_fack(struct tcp_sock *tp)
  760. {
  761. /* RFC3517 uses different metric in lost marker => reset on change */
  762. if (tcp_is_fack(tp))
  763. tp->lost_skb_hint = NULL;
  764. tp->rx_opt.sack_ok &= ~2;
  765. }
  766. /* Take a notice that peer is sending D-SACKs */
  767. static void tcp_dsack_seen(struct tcp_sock *tp)
  768. {
  769. tp->rx_opt.sack_ok |= 4;
  770. }
  771. /* Initialize metrics on socket. */
  772. static void tcp_init_metrics(struct sock *sk)
  773. {
  774. struct tcp_sock *tp = tcp_sk(sk);
  775. struct dst_entry *dst = __sk_dst_get(sk);
  776. if (dst == NULL)
  777. goto reset;
  778. dst_confirm(dst);
  779. if (dst_metric_locked(dst, RTAX_CWND))
  780. tp->snd_cwnd_clamp = dst_metric(dst, RTAX_CWND);
  781. if (dst_metric(dst, RTAX_SSTHRESH)) {
  782. tp->snd_ssthresh = dst_metric(dst, RTAX_SSTHRESH);
  783. if (tp->snd_ssthresh > tp->snd_cwnd_clamp)
  784. tp->snd_ssthresh = tp->snd_cwnd_clamp;
  785. }
  786. if (dst_metric(dst, RTAX_REORDERING) &&
  787. tp->reordering != dst_metric(dst, RTAX_REORDERING)) {
  788. tcp_disable_fack(tp);
  789. tp->reordering = dst_metric(dst, RTAX_REORDERING);
  790. }
  791. if (dst_metric(dst, RTAX_RTT) == 0)
  792. goto reset;
  793. if (!tp->srtt && dst_metric_rtt(dst, RTAX_RTT) < (TCP_TIMEOUT_INIT << 3))
  794. goto reset;
  795. /* Initial rtt is determined from SYN,SYN-ACK.
  796. * The segment is small and rtt may appear much
  797. * less than real one. Use per-dst memory
  798. * to make it more realistic.
  799. *
  800. * A bit of theory. RTT is time passed after "normal" sized packet
  801. * is sent until it is ACKed. In normal circumstances sending small
  802. * packets force peer to delay ACKs and calculation is correct too.
  803. * The algorithm is adaptive and, provided we follow specs, it
  804. * NEVER underestimate RTT. BUT! If peer tries to make some clever
  805. * tricks sort of "quick acks" for time long enough to decrease RTT
  806. * to low value, and then abruptly stops to do it and starts to delay
  807. * ACKs, wait for troubles.
  808. */
  809. if (dst_metric_rtt(dst, RTAX_RTT) > tp->srtt) {
  810. tp->srtt = dst_metric_rtt(dst, RTAX_RTT);
  811. tp->rtt_seq = tp->snd_nxt;
  812. }
  813. if (dst_metric_rtt(dst, RTAX_RTTVAR) > tp->mdev) {
  814. tp->mdev = dst_metric_rtt(dst, RTAX_RTTVAR);
  815. tp->mdev_max = tp->rttvar = max(tp->mdev, tcp_rto_min(sk));
  816. }
  817. tcp_set_rto(sk);
  818. tcp_bound_rto(sk);
  819. if (inet_csk(sk)->icsk_rto < TCP_TIMEOUT_INIT && !tp->rx_opt.saw_tstamp)
  820. goto reset;
  821. tp->snd_cwnd = tcp_init_cwnd(tp, dst);
  822. tp->snd_cwnd_stamp = tcp_time_stamp;
  823. return;
  824. reset:
  825. /* Play conservative. If timestamps are not
  826. * supported, TCP will fail to recalculate correct
  827. * rtt, if initial rto is too small. FORGET ALL AND RESET!
  828. */
  829. if (!tp->rx_opt.saw_tstamp && tp->srtt) {
  830. tp->srtt = 0;
  831. tp->mdev = tp->mdev_max = tp->rttvar = TCP_TIMEOUT_INIT;
  832. inet_csk(sk)->icsk_rto = TCP_TIMEOUT_INIT;
  833. }
  834. }
  835. static void tcp_update_reordering(struct sock *sk, const int metric,
  836. const int ts)
  837. {
  838. struct tcp_sock *tp = tcp_sk(sk);
  839. if (metric > tp->reordering) {
  840. int mib_idx;
  841. tp->reordering = min(TCP_MAX_REORDERING, metric);
  842. /* This exciting event is worth to be remembered. 8) */
  843. if (ts)
  844. mib_idx = LINUX_MIB_TCPTSREORDER;
  845. else if (tcp_is_reno(tp))
  846. mib_idx = LINUX_MIB_TCPRENOREORDER;
  847. else if (tcp_is_fack(tp))
  848. mib_idx = LINUX_MIB_TCPFACKREORDER;
  849. else
  850. mib_idx = LINUX_MIB_TCPSACKREORDER;
  851. NET_INC_STATS_BH(sock_net(sk), mib_idx);
  852. #if FASTRETRANS_DEBUG > 1
  853. printk(KERN_DEBUG "Disorder%d %d %u f%u s%u rr%d\n",
  854. tp->rx_opt.sack_ok, inet_csk(sk)->icsk_ca_state,
  855. tp->reordering,
  856. tp->fackets_out,
  857. tp->sacked_out,
  858. tp->undo_marker ? tp->undo_retrans : 0);
  859. #endif
  860. tcp_disable_fack(tp);
  861. }
  862. }
  863. /* This must be called before lost_out is incremented */
  864. static void tcp_verify_retransmit_hint(struct tcp_sock *tp, struct sk_buff *skb)
  865. {
  866. if ((tp->retransmit_skb_hint == NULL) ||
  867. before(TCP_SKB_CB(skb)->seq,
  868. TCP_SKB_CB(tp->retransmit_skb_hint)->seq))
  869. tp->retransmit_skb_hint = skb;
  870. if (!tp->lost_out ||
  871. after(TCP_SKB_CB(skb)->end_seq, tp->retransmit_high))
  872. tp->retransmit_high = TCP_SKB_CB(skb)->end_seq;
  873. }
  874. static void tcp_skb_mark_lost(struct tcp_sock *tp, struct sk_buff *skb)
  875. {
  876. if (!(TCP_SKB_CB(skb)->sacked & (TCPCB_LOST|TCPCB_SACKED_ACKED))) {
  877. tcp_verify_retransmit_hint(tp, skb);
  878. tp->lost_out += tcp_skb_pcount(skb);
  879. TCP_SKB_CB(skb)->sacked |= TCPCB_LOST;
  880. }
  881. }
  882. static void tcp_skb_mark_lost_uncond_verify(struct tcp_sock *tp,
  883. struct sk_buff *skb)
  884. {
  885. tcp_verify_retransmit_hint(tp, skb);
  886. if (!(TCP_SKB_CB(skb)->sacked & (TCPCB_LOST|TCPCB_SACKED_ACKED))) {
  887. tp->lost_out += tcp_skb_pcount(skb);
  888. TCP_SKB_CB(skb)->sacked |= TCPCB_LOST;
  889. }
  890. }
  891. /* This procedure tags the retransmission queue when SACKs arrive.
  892. *
  893. * We have three tag bits: SACKED(S), RETRANS(R) and LOST(L).
  894. * Packets in queue with these bits set are counted in variables
  895. * sacked_out, retrans_out and lost_out, correspondingly.
  896. *
  897. * Valid combinations are:
  898. * Tag InFlight Description
  899. * 0 1 - orig segment is in flight.
  900. * S 0 - nothing flies, orig reached receiver.
  901. * L 0 - nothing flies, orig lost by net.
  902. * R 2 - both orig and retransmit are in flight.
  903. * L|R 1 - orig is lost, retransmit is in flight.
  904. * S|R 1 - orig reached receiver, retrans is still in flight.
  905. * (L|S|R is logically valid, it could occur when L|R is sacked,
  906. * but it is equivalent to plain S and code short-curcuits it to S.
  907. * L|S is logically invalid, it would mean -1 packet in flight 8))
  908. *
  909. * These 6 states form finite state machine, controlled by the following events:
  910. * 1. New ACK (+SACK) arrives. (tcp_sacktag_write_queue())
  911. * 2. Retransmission. (tcp_retransmit_skb(), tcp_xmit_retransmit_queue())
  912. * 3. Loss detection event of one of three flavors:
  913. * A. Scoreboard estimator decided the packet is lost.
  914. * A'. Reno "three dupacks" marks head of queue lost.
  915. * A''. Its FACK modfication, head until snd.fack is lost.
  916. * B. SACK arrives sacking data transmitted after never retransmitted
  917. * hole was sent out.
  918. * C. SACK arrives sacking SND.NXT at the moment, when the
  919. * segment was retransmitted.
  920. * 4. D-SACK added new rule: D-SACK changes any tag to S.
  921. *
  922. * It is pleasant to note, that state diagram turns out to be commutative,
  923. * so that we are allowed not to be bothered by order of our actions,
  924. * when multiple events arrive simultaneously. (see the function below).
  925. *
  926. * Reordering detection.
  927. * --------------------
  928. * Reordering metric is maximal distance, which a packet can be displaced
  929. * in packet stream. With SACKs we can estimate it:
  930. *
  931. * 1. SACK fills old hole and the corresponding segment was not
  932. * ever retransmitted -> reordering. Alas, we cannot use it
  933. * when segment was retransmitted.
  934. * 2. The last flaw is solved with D-SACK. D-SACK arrives
  935. * for retransmitted and already SACKed segment -> reordering..
  936. * Both of these heuristics are not used in Loss state, when we cannot
  937. * account for retransmits accurately.
  938. *
  939. * SACK block validation.
  940. * ----------------------
  941. *
  942. * SACK block range validation checks that the received SACK block fits to
  943. * the expected sequence limits, i.e., it is between SND.UNA and SND.NXT.
  944. * Note that SND.UNA is not included to the range though being valid because
  945. * it means that the receiver is rather inconsistent with itself reporting
  946. * SACK reneging when it should advance SND.UNA. Such SACK block this is
  947. * perfectly valid, however, in light of RFC2018 which explicitly states
  948. * that "SACK block MUST reflect the newest segment. Even if the newest
  949. * segment is going to be discarded ...", not that it looks very clever
  950. * in case of head skb. Due to potentional receiver driven attacks, we
  951. * choose to avoid immediate execution of a walk in write queue due to
  952. * reneging and defer head skb's loss recovery to standard loss recovery
  953. * procedure that will eventually trigger (nothing forbids us doing this).
  954. *
  955. * Implements also blockage to start_seq wrap-around. Problem lies in the
  956. * fact that though start_seq (s) is before end_seq (i.e., not reversed),
  957. * there's no guarantee that it will be before snd_nxt (n). The problem
  958. * happens when start_seq resides between end_seq wrap (e_w) and snd_nxt
  959. * wrap (s_w):
  960. *
  961. * <- outs wnd -> <- wrapzone ->
  962. * u e n u_w e_w s n_w
  963. * | | | | | | |
  964. * |<------------+------+----- TCP seqno space --------------+---------->|
  965. * ...-- <2^31 ->| |<--------...
  966. * ...---- >2^31 ------>| |<--------...
  967. *
  968. * Current code wouldn't be vulnerable but it's better still to discard such
  969. * crazy SACK blocks. Doing this check for start_seq alone closes somewhat
  970. * similar case (end_seq after snd_nxt wrap) as earlier reversed check in
  971. * snd_nxt wrap -> snd_una region will then become "well defined", i.e.,
  972. * equal to the ideal case (infinite seqno space without wrap caused issues).
  973. *
  974. * With D-SACK the lower bound is extended to cover sequence space below
  975. * SND.UNA down to undo_marker, which is the last point of interest. Yet
  976. * again, D-SACK block must not to go across snd_una (for the same reason as
  977. * for the normal SACK blocks, explained above). But there all simplicity
  978. * ends, TCP might receive valid D-SACKs below that. As long as they reside
  979. * fully below undo_marker they do not affect behavior in anyway and can
  980. * therefore be safely ignored. In rare cases (which are more or less
  981. * theoretical ones), the D-SACK will nicely cross that boundary due to skb
  982. * fragmentation and packet reordering past skb's retransmission. To consider
  983. * them correctly, the acceptable range must be extended even more though
  984. * the exact amount is rather hard to quantify. However, tp->max_window can
  985. * be used as an exaggerated estimate.
  986. */
  987. static int tcp_is_sackblock_valid(struct tcp_sock *tp, int is_dsack,
  988. u32 start_seq, u32 end_seq)
  989. {
  990. /* Too far in future, or reversed (interpretation is ambiguous) */
  991. if (after(end_seq, tp->snd_nxt) || !before(start_seq, end_seq))
  992. return 0;
  993. /* Nasty start_seq wrap-around check (see comments above) */
  994. if (!before(start_seq, tp->snd_nxt))
  995. return 0;
  996. /* In outstanding window? ...This is valid exit for D-SACKs too.
  997. * start_seq == snd_una is non-sensical (see comments above)
  998. */
  999. if (after(start_seq, tp->snd_una))
  1000. return 1;
  1001. if (!is_dsack || !tp->undo_marker)
  1002. return 0;
  1003. /* ...Then it's D-SACK, and must reside below snd_una completely */
  1004. if (!after(end_seq, tp->snd_una))
  1005. return 0;
  1006. if (!before(start_seq, tp->undo_marker))
  1007. return 1;
  1008. /* Too old */
  1009. if (!after(end_seq, tp->undo_marker))
  1010. return 0;
  1011. /* Undo_marker boundary crossing (overestimates a lot). Known already:
  1012. * start_seq < undo_marker and end_seq >= undo_marker.
  1013. */
  1014. return !before(start_seq, end_seq - tp->max_window);
  1015. }
  1016. /* Check for lost retransmit. This superb idea is borrowed from "ratehalving".
  1017. * Event "C". Later note: FACK people cheated me again 8), we have to account
  1018. * for reordering! Ugly, but should help.
  1019. *
  1020. * Search retransmitted skbs from write_queue that were sent when snd_nxt was
  1021. * less than what is now known to be received by the other end (derived from
  1022. * highest SACK block). Also calculate the lowest snd_nxt among the remaining
  1023. * retransmitted skbs to avoid some costly processing per ACKs.
  1024. */
  1025. static void tcp_mark_lost_retrans(struct sock *sk)
  1026. {
  1027. const struct inet_connection_sock *icsk = inet_csk(sk);
  1028. struct tcp_sock *tp = tcp_sk(sk);
  1029. struct sk_buff *skb;
  1030. int cnt = 0;
  1031. u32 new_low_seq = tp->snd_nxt;
  1032. u32 received_upto = tcp_highest_sack_seq(tp);
  1033. if (!tcp_is_fack(tp) || !tp->retrans_out ||
  1034. !after(received_upto, tp->lost_retrans_low) ||
  1035. icsk->icsk_ca_state != TCP_CA_Recovery)
  1036. return;
  1037. tcp_for_write_queue(skb, sk) {
  1038. u32 ack_seq = TCP_SKB_CB(skb)->ack_seq;
  1039. if (skb == tcp_send_head(sk))
  1040. break;
  1041. if (cnt == tp->retrans_out)
  1042. break;
  1043. if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una))
  1044. continue;
  1045. if (!(TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_RETRANS))
  1046. continue;
  1047. if (after(received_upto, ack_seq) &&
  1048. (tcp_is_fack(tp) ||
  1049. !before(received_upto,
  1050. ack_seq + tp->reordering * tp->mss_cache))) {
  1051. TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS;
  1052. tp->retrans_out -= tcp_skb_pcount(skb);
  1053. tcp_skb_mark_lost_uncond_verify(tp, skb);
  1054. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPLOSTRETRANSMIT);
  1055. } else {
  1056. if (before(ack_seq, new_low_seq))
  1057. new_low_seq = ack_seq;
  1058. cnt += tcp_skb_pcount(skb);
  1059. }
  1060. }
  1061. if (tp->retrans_out)
  1062. tp->lost_retrans_low = new_low_seq;
  1063. }
  1064. static int tcp_check_dsack(struct sock *sk, struct sk_buff *ack_skb,
  1065. struct tcp_sack_block_wire *sp, int num_sacks,
  1066. u32 prior_snd_una)
  1067. {
  1068. struct tcp_sock *tp = tcp_sk(sk);
  1069. u32 start_seq_0 = get_unaligned_be32(&sp[0].start_seq);
  1070. u32 end_seq_0 = get_unaligned_be32(&sp[0].end_seq);
  1071. int dup_sack = 0;
  1072. if (before(start_seq_0, TCP_SKB_CB(ack_skb)->ack_seq)) {
  1073. dup_sack = 1;
  1074. tcp_dsack_seen(tp);
  1075. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPDSACKRECV);
  1076. } else if (num_sacks > 1) {
  1077. u32 end_seq_1 = get_unaligned_be32(&sp[1].end_seq);
  1078. u32 start_seq_1 = get_unaligned_be32(&sp[1].start_seq);
  1079. if (!after(end_seq_0, end_seq_1) &&
  1080. !before(start_seq_0, start_seq_1)) {
  1081. dup_sack = 1;
  1082. tcp_dsack_seen(tp);
  1083. NET_INC_STATS_BH(sock_net(sk),
  1084. LINUX_MIB_TCPDSACKOFORECV);
  1085. }
  1086. }
  1087. /* D-SACK for already forgotten data... Do dumb counting. */
  1088. if (dup_sack &&
  1089. !after(end_seq_0, prior_snd_una) &&
  1090. after(end_seq_0, tp->undo_marker))
  1091. tp->undo_retrans--;
  1092. return dup_sack;
  1093. }
  1094. /* Check if skb is fully within the SACK block. In presence of GSO skbs,
  1095. * the incoming SACK may not exactly match but we can find smaller MSS
  1096. * aligned portion of it that matches. Therefore we might need to fragment
  1097. * which may fail and creates some hassle (caller must handle error case
  1098. * returns).
  1099. *
  1100. * FIXME: this could be merged to shift decision code
  1101. */
  1102. static int tcp_match_skb_to_sack(struct sock *sk, struct sk_buff *skb,
  1103. u32 start_seq, u32 end_seq)
  1104. {
  1105. int in_sack, err;
  1106. unsigned int pkt_len;
  1107. unsigned int mss;
  1108. in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq) &&
  1109. !before(end_seq, TCP_SKB_CB(skb)->end_seq);
  1110. if (tcp_skb_pcount(skb) > 1 && !in_sack &&
  1111. after(TCP_SKB_CB(skb)->end_seq, start_seq)) {
  1112. mss = tcp_skb_mss(skb);
  1113. in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq);
  1114. if (!in_sack) {
  1115. pkt_len = start_seq - TCP_SKB_CB(skb)->seq;
  1116. if (pkt_len < mss)
  1117. pkt_len = mss;
  1118. } else {
  1119. pkt_len = end_seq - TCP_SKB_CB(skb)->seq;
  1120. if (pkt_len < mss)
  1121. return -EINVAL;
  1122. }
  1123. /* Round if necessary so that SACKs cover only full MSSes
  1124. * and/or the remaining small portion (if present)
  1125. */
  1126. if (pkt_len > mss) {
  1127. unsigned int new_len = (pkt_len / mss) * mss;
  1128. if (!in_sack && new_len < pkt_len) {
  1129. new_len += mss;
  1130. if (new_len > skb->len)
  1131. return 0;
  1132. }
  1133. pkt_len = new_len;
  1134. }
  1135. err = tcp_fragment(sk, skb, pkt_len, mss);
  1136. if (err < 0)
  1137. return err;
  1138. }
  1139. return in_sack;
  1140. }
  1141. static int tcp_sacktag_one(struct sk_buff *skb, struct sock *sk,
  1142. int *reord, int dup_sack, int fack_count,
  1143. u8 *sackedto, int pcount)
  1144. {
  1145. struct tcp_sock *tp = tcp_sk(sk);
  1146. u8 sacked = TCP_SKB_CB(skb)->sacked;
  1147. int flag = 0;
  1148. /* Account D-SACK for retransmitted packet. */
  1149. if (dup_sack && (sacked & TCPCB_RETRANS)) {
  1150. if (after(TCP_SKB_CB(skb)->end_seq, tp->undo_marker))
  1151. tp->undo_retrans--;
  1152. if (sacked & TCPCB_SACKED_ACKED)
  1153. *reord = min(fack_count, *reord);
  1154. }
  1155. /* Nothing to do; acked frame is about to be dropped (was ACKed). */
  1156. if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una))
  1157. return flag;
  1158. if (!(sacked & TCPCB_SACKED_ACKED)) {
  1159. if (sacked & TCPCB_SACKED_RETRANS) {
  1160. /* If the segment is not tagged as lost,
  1161. * we do not clear RETRANS, believing
  1162. * that retransmission is still in flight.
  1163. */
  1164. if (sacked & TCPCB_LOST) {
  1165. *sackedto &= ~(TCPCB_LOST|TCPCB_SACKED_RETRANS);
  1166. tp->lost_out -= pcount;
  1167. tp->retrans_out -= pcount;
  1168. }
  1169. } else {
  1170. if (!(sacked & TCPCB_RETRANS)) {
  1171. /* New sack for not retransmitted frame,
  1172. * which was in hole. It is reordering.
  1173. */
  1174. if (before(TCP_SKB_CB(skb)->seq,
  1175. tcp_highest_sack_seq(tp)))
  1176. *reord = min(fack_count, *reord);
  1177. /* SACK enhanced F-RTO (RFC4138; Appendix B) */
  1178. if (!after(TCP_SKB_CB(skb)->end_seq, tp->frto_highmark))
  1179. flag |= FLAG_ONLY_ORIG_SACKED;
  1180. }
  1181. if (sacked & TCPCB_LOST) {
  1182. *sackedto &= ~TCPCB_LOST;
  1183. tp->lost_out -= pcount;
  1184. }
  1185. }
  1186. *sackedto |= TCPCB_SACKED_ACKED;
  1187. flag |= FLAG_DATA_SACKED;
  1188. tp->sacked_out += pcount;
  1189. fack_count += pcount;
  1190. /* Lost marker hint past SACKed? Tweak RFC3517 cnt */
  1191. if (!tcp_is_fack(tp) && (tp->lost_skb_hint != NULL) &&
  1192. before(TCP_SKB_CB(skb)->seq,
  1193. TCP_SKB_CB(tp->lost_skb_hint)->seq))
  1194. tp->lost_cnt_hint += pcount;
  1195. if (fack_count > tp->fackets_out)
  1196. tp->fackets_out = fack_count;
  1197. }
  1198. /* D-SACK. We can detect redundant retransmission in S|R and plain R
  1199. * frames and clear it. undo_retrans is decreased above, L|R frames
  1200. * are accounted above as well.
  1201. */
  1202. if (dup_sack && (*sackedto & TCPCB_SACKED_RETRANS)) {
  1203. *sackedto &= ~TCPCB_SACKED_RETRANS;
  1204. tp->retrans_out -= pcount;
  1205. }
  1206. return flag;
  1207. }
  1208. static int tcp_shifted_skb(struct sock *sk, struct sk_buff *prev,
  1209. struct sk_buff *skb, unsigned int pcount,
  1210. int shifted, int fack_count, int *reord,
  1211. int *flag, int mss)
  1212. {
  1213. struct tcp_sock *tp = tcp_sk(sk);
  1214. u8 dummy_sacked = TCP_SKB_CB(skb)->sacked; /* We discard results */
  1215. BUG_ON(!pcount);
  1216. /* Tweak before seqno plays */
  1217. if (!tcp_is_fack(tp) && tcp_is_sack(tp) && tp->lost_skb_hint &&
  1218. !before(TCP_SKB_CB(tp->lost_skb_hint)->seq, TCP_SKB_CB(skb)->seq))
  1219. tp->lost_cnt_hint += pcount;
  1220. TCP_SKB_CB(prev)->end_seq += shifted;
  1221. TCP_SKB_CB(skb)->seq += shifted;
  1222. skb_shinfo(prev)->gso_segs += pcount;
  1223. BUG_ON(skb_shinfo(skb)->gso_segs < pcount);
  1224. skb_shinfo(skb)->gso_segs -= pcount;
  1225. /* When we're adding to gso_segs == 1, gso_size will be zero,
  1226. * in theory this shouldn't be necessary but as long as DSACK
  1227. * code can come after this skb later on it's better to keep
  1228. * setting gso_size to something.
  1229. */
  1230. if (!skb_shinfo(prev)->gso_size) {
  1231. skb_shinfo(prev)->gso_size = mss;
  1232. skb_shinfo(prev)->gso_type = sk->sk_gso_type;
  1233. }
  1234. /* CHECKME: To clear or not to clear? Mimics normal skb currently */
  1235. if (skb_shinfo(skb)->gso_segs <= 1) {
  1236. skb_shinfo(skb)->gso_size = 0;
  1237. skb_shinfo(skb)->gso_type = 0;
  1238. }
  1239. *flag |= tcp_sacktag_one(skb, sk, reord, 0, fack_count, &dummy_sacked,
  1240. pcount);
  1241. /* Difference in this won't matter, both ACKed by the same cumul. ACK */
  1242. TCP_SKB_CB(prev)->sacked |= (TCP_SKB_CB(skb)->sacked & TCPCB_EVER_RETRANS);
  1243. if (skb->len > 0) {
  1244. BUG_ON(!tcp_skb_pcount(skb));
  1245. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_SACKSHIFTED);
  1246. return 0;
  1247. }
  1248. /* Whole SKB was eaten :-) */
  1249. if (skb == tp->retransmit_skb_hint)
  1250. tp->retransmit_skb_hint = prev;
  1251. if (skb == tp->scoreboard_skb_hint)
  1252. tp->scoreboard_skb_hint = prev;
  1253. if (skb == tp->lost_skb_hint) {
  1254. tp->lost_skb_hint = prev;
  1255. tp->lost_cnt_hint -= tcp_skb_pcount(prev);
  1256. }
  1257. TCP_SKB_CB(skb)->flags |= TCP_SKB_CB(prev)->flags;
  1258. if (skb == tcp_highest_sack(sk))
  1259. tcp_advance_highest_sack(sk, skb);
  1260. tcp_unlink_write_queue(skb, sk);
  1261. sk_wmem_free_skb(sk, skb);
  1262. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_SACKMERGED);
  1263. return 1;
  1264. }
  1265. /* I wish gso_size would have a bit more sane initialization than
  1266. * something-or-zero which complicates things
  1267. */
  1268. static int tcp_shift_mss(struct sk_buff *skb)
  1269. {
  1270. int mss = tcp_skb_mss(skb);
  1271. if (!mss)
  1272. mss = skb->len;
  1273. return mss;
  1274. }
  1275. /* Shifting pages past head area doesn't work */
  1276. static int skb_can_shift(struct sk_buff *skb)
  1277. {
  1278. return !skb_headlen(skb) && skb_is_nonlinear(skb);
  1279. }
  1280. /* Try collapsing SACK blocks spanning across multiple skbs to a single
  1281. * skb.
  1282. */
  1283. static struct sk_buff *tcp_shift_skb_data(struct sock *sk, struct sk_buff *skb,
  1284. u32 start_seq, u32 end_seq,
  1285. int dup_sack, int *fack_count,
  1286. int *reord, int *flag)
  1287. {
  1288. struct tcp_sock *tp = tcp_sk(sk);
  1289. struct sk_buff *prev;
  1290. int mss;
  1291. int pcount = 0;
  1292. int len;
  1293. int in_sack;
  1294. if (!sk_can_gso(sk))
  1295. goto fallback;
  1296. /* Normally R but no L won't result in plain S */
  1297. if (!dup_sack &&
  1298. (TCP_SKB_CB(skb)->sacked & (TCPCB_LOST|TCPCB_SACKED_RETRANS)) == TCPCB_SACKED_RETRANS)
  1299. goto fallback;
  1300. if (!skb_can_shift(skb))
  1301. goto fallback;
  1302. /* This frame is about to be dropped (was ACKed). */
  1303. if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una))
  1304. goto fallback;
  1305. /* Can only happen with delayed DSACK + discard craziness */
  1306. if (unlikely(skb == tcp_write_queue_head(sk)))
  1307. goto fallback;
  1308. prev = tcp_write_queue_prev(sk, skb);
  1309. if ((TCP_SKB_CB(prev)->sacked & TCPCB_TAGBITS) != TCPCB_SACKED_ACKED)
  1310. goto fallback;
  1311. in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq) &&
  1312. !before(end_seq, TCP_SKB_CB(skb)->end_seq);
  1313. if (in_sack) {
  1314. len = skb->len;
  1315. pcount = tcp_skb_pcount(skb);
  1316. mss = tcp_shift_mss(skb);
  1317. /* TODO: Fix DSACKs to not fragment already SACKed and we can
  1318. * drop this restriction as unnecessary
  1319. */
  1320. if (mss != tcp_shift_mss(prev))
  1321. goto fallback;
  1322. } else {
  1323. if (!after(TCP_SKB_CB(skb)->end_seq, start_seq))
  1324. goto noop;
  1325. /* CHECKME: This is non-MSS split case only?, this will
  1326. * cause skipped skbs due to advancing loop btw, original
  1327. * has that feature too
  1328. */
  1329. if (tcp_skb_pcount(skb) <= 1)
  1330. goto noop;
  1331. in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq);
  1332. if (!in_sack) {
  1333. /* TODO: head merge to next could be attempted here
  1334. * if (!after(TCP_SKB_CB(skb)->end_seq, end_seq)),
  1335. * though it might not be worth of the additional hassle
  1336. *
  1337. * ...we can probably just fallback to what was done
  1338. * previously. We could try merging non-SACKed ones
  1339. * as well but it probably isn't going to buy off
  1340. * because later SACKs might again split them, and
  1341. * it would make skb timestamp tracking considerably
  1342. * harder problem.
  1343. */
  1344. goto fallback;
  1345. }
  1346. len = end_seq - TCP_SKB_CB(skb)->seq;
  1347. BUG_ON(len < 0);
  1348. BUG_ON(len > skb->len);
  1349. /* MSS boundaries should be honoured or else pcount will
  1350. * severely break even though it makes things bit trickier.
  1351. * Optimize common case to avoid most of the divides
  1352. */
  1353. mss = tcp_skb_mss(skb);
  1354. /* TODO: Fix DSACKs to not fragment already SACKed and we can
  1355. * drop this restriction as unnecessary
  1356. */
  1357. if (mss != tcp_shift_mss(prev))
  1358. goto fallback;
  1359. if (len == mss) {
  1360. pcount = 1;
  1361. } else if (len < mss) {
  1362. goto noop;
  1363. } else {
  1364. pcount = len / mss;
  1365. len = pcount * mss;
  1366. }
  1367. }
  1368. if (!skb_shift(prev, skb, len))
  1369. goto fallback;
  1370. if (!tcp_shifted_skb(sk, prev, skb, pcount, len, *fack_count, reord,
  1371. flag, mss))
  1372. goto out;
  1373. /* Hole filled allows collapsing with the next as well, this is very
  1374. * useful when hole on every nth skb pattern happens
  1375. */
  1376. if (prev == tcp_write_queue_tail(sk))
  1377. goto out;
  1378. skb = tcp_write_queue_next(sk, prev);
  1379. if (!skb_can_shift(skb) ||
  1380. (skb == tcp_send_head(sk)) ||
  1381. ((TCP_SKB_CB(skb)->sacked & TCPCB_TAGBITS) != TCPCB_SACKED_ACKED) ||
  1382. (mss != tcp_shift_mss(skb)))
  1383. goto out;
  1384. len = skb->len;
  1385. if (skb_shift(prev, skb, len)) {
  1386. pcount += tcp_skb_pcount(skb);
  1387. tcp_shifted_skb(sk, prev, skb, tcp_skb_pcount(skb), len,
  1388. *fack_count, reord, flag, mss);
  1389. }
  1390. out:
  1391. *fack_count += pcount;
  1392. return prev;
  1393. noop:
  1394. return skb;
  1395. fallback:
  1396. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_SACKSHIFTFALLBACK);
  1397. return NULL;
  1398. }
  1399. static struct sk_buff *tcp_sacktag_walk(struct sk_buff *skb, struct sock *sk,
  1400. struct tcp_sack_block *next_dup,
  1401. u32 start_seq, u32 end_seq,
  1402. int dup_sack_in, int *fack_count,
  1403. int *reord, int *flag)
  1404. {
  1405. struct tcp_sock *tp = tcp_sk(sk);
  1406. struct sk_buff *tmp;
  1407. tcp_for_write_queue_from(skb, sk) {
  1408. int in_sack = 0;
  1409. int dup_sack = dup_sack_in;
  1410. if (skb == tcp_send_head(sk))
  1411. break;
  1412. /* queue is in-order => we can short-circuit the walk early */
  1413. if (!before(TCP_SKB_CB(skb)->seq, end_seq))
  1414. break;
  1415. if ((next_dup != NULL) &&
  1416. before(TCP_SKB_CB(skb)->seq, next_dup->end_seq)) {
  1417. in_sack = tcp_match_skb_to_sack(sk, skb,
  1418. next_dup->start_seq,
  1419. next_dup->end_seq);
  1420. if (in_sack > 0)
  1421. dup_sack = 1;
  1422. }
  1423. /* skb reference here is a bit tricky to get right, since
  1424. * shifting can eat and free both this skb and the next,
  1425. * so not even _safe variant of the loop is enough.
  1426. */
  1427. if (in_sack <= 0) {
  1428. tmp = tcp_shift_skb_data(sk, skb, start_seq,
  1429. end_seq, dup_sack,
  1430. fack_count, reord, flag);
  1431. if (tmp != NULL) {
  1432. if (tmp != skb) {
  1433. skb = tmp;
  1434. continue;
  1435. }
  1436. in_sack = 0;
  1437. } else {
  1438. in_sack = tcp_match_skb_to_sack(sk, skb,
  1439. start_seq,
  1440. end_seq);
  1441. }
  1442. }
  1443. if (unlikely(in_sack < 0))
  1444. break;
  1445. if (in_sack) {
  1446. *flag |= tcp_sacktag_one(skb, sk, reord, dup_sack,
  1447. *fack_count,
  1448. &(TCP_SKB_CB(skb)->sacked),
  1449. tcp_skb_pcount(skb));
  1450. if (!before(TCP_SKB_CB(skb)->seq,
  1451. tcp_highest_sack_seq(tp)))
  1452. tcp_advance_highest_sack(sk, skb);
  1453. }
  1454. *fack_count += tcp_skb_pcount(skb);
  1455. }
  1456. return skb;
  1457. }
  1458. /* Avoid all extra work that is being done by sacktag while walking in
  1459. * a normal way
  1460. */
  1461. static struct sk_buff *tcp_sacktag_skip(struct sk_buff *skb, struct sock *sk,
  1462. u32 skip_to_seq, int *fack_count)
  1463. {
  1464. tcp_for_write_queue_from(skb, sk) {
  1465. if (skb == tcp_send_head(sk))
  1466. break;
  1467. if (after(TCP_SKB_CB(skb)->end_seq, skip_to_seq))
  1468. break;
  1469. *fack_count += tcp_skb_pcount(skb);
  1470. }
  1471. return skb;
  1472. }
  1473. static struct sk_buff *tcp_maybe_skipping_dsack(struct sk_buff *skb,
  1474. struct sock *sk,
  1475. struct tcp_sack_block *next_dup,
  1476. u32 skip_to_seq,
  1477. int *fack_count, int *reord,
  1478. int *flag)
  1479. {
  1480. if (next_dup == NULL)
  1481. return skb;
  1482. if (before(next_dup->start_seq, skip_to_seq)) {
  1483. skb = tcp_sacktag_skip(skb, sk, next_dup->start_seq, fack_count);
  1484. skb = tcp_sacktag_walk(skb, sk, NULL,
  1485. next_dup->start_seq, next_dup->end_seq,
  1486. 1, fack_count, reord, flag);
  1487. }
  1488. return skb;
  1489. }
  1490. static int tcp_sack_cache_ok(struct tcp_sock *tp, struct tcp_sack_block *cache)
  1491. {
  1492. return cache < tp->recv_sack_cache + ARRAY_SIZE(tp->recv_sack_cache);
  1493. }
  1494. static int
  1495. tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb,
  1496. u32 prior_snd_una)
  1497. {
  1498. const struct inet_connection_sock *icsk = inet_csk(sk);
  1499. struct tcp_sock *tp = tcp_sk(sk);
  1500. unsigned char *ptr = (skb_transport_header(ack_skb) +
  1501. TCP_SKB_CB(ack_skb)->sacked);
  1502. struct tcp_sack_block_wire *sp_wire = (struct tcp_sack_block_wire *)(ptr+2);
  1503. struct tcp_sack_block sp[TCP_NUM_SACKS];
  1504. struct tcp_sack_block *cache;
  1505. struct sk_buff *skb;
  1506. int num_sacks = min(TCP_NUM_SACKS, (ptr[1] - TCPOLEN_SACK_BASE) >> 3);
  1507. int used_sacks;
  1508. int reord = tp->packets_out;
  1509. int flag = 0;
  1510. int found_dup_sack = 0;
  1511. int fack_count;
  1512. int i, j;
  1513. int first_sack_index;
  1514. if (!tp->sacked_out) {
  1515. if (WARN_ON(tp->fackets_out))
  1516. tp->fackets_out = 0;
  1517. tcp_highest_sack_reset(sk);
  1518. }
  1519. found_dup_sack = tcp_check_dsack(sk, ack_skb, sp_wire,
  1520. num_sacks, prior_snd_una);
  1521. if (found_dup_sack)
  1522. flag |= FLAG_DSACKING_ACK;
  1523. /* Eliminate too old ACKs, but take into
  1524. * account more or less fresh ones, they can
  1525. * contain valid SACK info.
  1526. */
  1527. if (before(TCP_SKB_CB(ack_skb)->ack_seq, prior_snd_una - tp->max_window))
  1528. return 0;
  1529. if (!tp->packets_out)
  1530. goto out;
  1531. used_sacks = 0;
  1532. first_sack_index = 0;
  1533. for (i = 0; i < num_sacks; i++) {
  1534. int dup_sack = !i && found_dup_sack;
  1535. sp[used_sacks].start_seq = get_unaligned_be32(&sp_wire[i].start_seq);
  1536. sp[used_sacks].end_seq = get_unaligned_be32(&sp_wire[i].end_seq);
  1537. if (!tcp_is_sackblock_valid(tp, dup_sack,
  1538. sp[used_sacks].start_seq,
  1539. sp[used_sacks].end_seq)) {
  1540. int mib_idx;
  1541. if (dup_sack) {
  1542. if (!tp->undo_marker)
  1543. mib_idx = LINUX_MIB_TCPDSACKIGNOREDNOUNDO;
  1544. else
  1545. mib_idx = LINUX_MIB_TCPDSACKIGNOREDOLD;
  1546. } else {
  1547. /* Don't count olds caused by ACK reordering */
  1548. if ((TCP_SKB_CB(ack_skb)->ack_seq != tp->snd_una) &&
  1549. !after(sp[used_sacks].end_seq, tp->snd_una))
  1550. continue;
  1551. mib_idx = LINUX_MIB_TCPSACKDISCARD;
  1552. }
  1553. NET_INC_STATS_BH(sock_net(sk), mib_idx);
  1554. if (i == 0)
  1555. first_sack_index = -1;
  1556. continue;
  1557. }
  1558. /* Ignore very old stuff early */
  1559. if (!after(sp[used_sacks].end_seq, prior_snd_una))
  1560. continue;
  1561. used_sacks++;
  1562. }
  1563. /* order SACK blocks to allow in order walk of the retrans queue */
  1564. for (i = used_sacks - 1; i > 0; i--) {
  1565. for (j = 0; j < i; j++) {
  1566. if (after(sp[j].start_seq, sp[j + 1].start_seq)) {
  1567. struct tcp_sack_block tmp;
  1568. tmp = sp[j];
  1569. sp[j] = sp[j + 1];
  1570. sp[j + 1] = tmp;
  1571. /* Track where the first SACK block goes to */
  1572. if (j == first_sack_index)
  1573. first_sack_index = j + 1;
  1574. }
  1575. }
  1576. }
  1577. skb = tcp_write_queue_head(sk);
  1578. fack_count = 0;
  1579. i = 0;
  1580. if (!tp->sacked_out) {
  1581. /* It's already past, so skip checking against it */
  1582. cache = tp->recv_sack_cache + ARRAY_SIZE(tp->recv_sack_cache);
  1583. } else {
  1584. cache = tp->recv_sack_cache;
  1585. /* Skip empty blocks in at head of the cache */
  1586. while (tcp_sack_cache_ok(tp, cache) && !cache->start_seq &&
  1587. !cache->end_seq)
  1588. cache++;
  1589. }
  1590. while (i < used_sacks) {
  1591. u32 start_seq = sp[i].start_seq;
  1592. u32 end_seq = sp[i].end_seq;
  1593. int dup_sack = (found_dup_sack && (i == first_sack_index));
  1594. struct tcp_sack_block *next_dup = NULL;
  1595. if (found_dup_sack && ((i + 1) == first_sack_index))
  1596. next_dup = &sp[i + 1];
  1597. /* Event "B" in the comment above. */
  1598. if (after(end_seq, tp->high_seq))
  1599. flag |= FLAG_DATA_LOST;
  1600. /* Skip too early cached blocks */
  1601. while (tcp_sack_cache_ok(tp, cache) &&
  1602. !before(start_seq, cache->end_seq))
  1603. cache++;
  1604. /* Can skip some work by looking recv_sack_cache? */
  1605. if (tcp_sack_cache_ok(tp, cache) && !dup_sack &&
  1606. after(end_seq, cache->start_seq)) {
  1607. /* Head todo? */
  1608. if (before(start_seq, cache->start_seq)) {
  1609. skb = tcp_sacktag_skip(skb, sk, start_seq,
  1610. &fack_count);
  1611. skb = tcp_sacktag_walk(skb, sk, next_dup,
  1612. start_seq,
  1613. cache->start_seq,
  1614. dup_sack, &fack_count,
  1615. &reord, &flag);
  1616. }
  1617. /* Rest of the block already fully processed? */
  1618. if (!after(end_seq, cache->end_seq))
  1619. goto advance_sp;
  1620. skb = tcp_maybe_skipping_dsack(skb, sk, next_dup,
  1621. cache->end_seq,
  1622. &fack_count, &reord,
  1623. &flag);
  1624. /* ...tail remains todo... */
  1625. if (tcp_highest_sack_seq(tp) == cache->end_seq) {
  1626. /* ...but better entrypoint exists! */
  1627. skb = tcp_highest_sack(sk);
  1628. if (skb == NULL)
  1629. break;
  1630. fack_count = tp->fackets_out;
  1631. cache++;
  1632. goto walk;
  1633. }
  1634. skb = tcp_sacktag_skip(skb, sk, cache->end_seq,
  1635. &fack_count);
  1636. /* Check overlap against next cached too (past this one already) */
  1637. cache++;
  1638. continue;
  1639. }
  1640. if (!before(start_seq, tcp_highest_sack_seq(tp))) {
  1641. skb = tcp_highest_sack(sk);
  1642. if (skb == NULL)
  1643. break;
  1644. fack_count = tp->fackets_out;
  1645. }
  1646. skb = tcp_sacktag_skip(skb, sk, start_seq, &fack_count);
  1647. walk:
  1648. skb = tcp_sacktag_walk(skb, sk, next_dup, start_seq, end_seq,
  1649. dup_sack, &fack_count, &reord, &flag);
  1650. advance_sp:
  1651. /* SACK enhanced FRTO (RFC4138, Appendix B): Clearing correct
  1652. * due to in-order walk
  1653. */
  1654. if (after(end_seq, tp->frto_highmark))
  1655. flag &= ~FLAG_ONLY_ORIG_SACKED;
  1656. i++;
  1657. }
  1658. /* Clear the head of the cache sack blocks so we can skip it next time */
  1659. for (i = 0; i < ARRAY_SIZE(tp->recv_sack_cache) - used_sacks; i++) {
  1660. tp->recv_sack_cache[i].start_seq = 0;
  1661. tp->recv_sack_cache[i].end_seq = 0;
  1662. }
  1663. for (j = 0; j < used_sacks; j++)
  1664. tp->recv_sack_cache[i++] = sp[j];
  1665. tcp_mark_lost_retrans(sk);
  1666. tcp_verify_left_out(tp);
  1667. if ((reord < tp->fackets_out) &&
  1668. ((icsk->icsk_ca_state != TCP_CA_Loss) || tp->undo_marker) &&
  1669. (!tp->frto_highmark || after(tp->snd_una, tp->frto_highmark)))
  1670. tcp_update_reordering(sk, tp->fackets_out - reord, 0);
  1671. out:
  1672. #if FASTRETRANS_DEBUG > 0
  1673. WARN_ON((int)tp->sacked_out < 0);
  1674. WARN_ON((int)tp->lost_out < 0);
  1675. WARN_ON((int)tp->retrans_out < 0);
  1676. WARN_ON((int)tcp_packets_in_flight(tp) < 0);
  1677. #endif
  1678. return flag;
  1679. }
  1680. /* Limits sacked_out so that sum with lost_out isn't ever larger than
  1681. * packets_out. Returns zero if sacked_out adjustement wasn't necessary.
  1682. */
  1683. static int tcp_limit_reno_sacked(struct tcp_sock *tp)
  1684. {
  1685. u32 holes;
  1686. holes = max(tp->lost_out, 1U);
  1687. holes = min(holes, tp->packets_out);
  1688. if ((tp->sacked_out + holes) > tp->packets_out) {
  1689. tp->sacked_out = tp->packets_out - holes;
  1690. return 1;
  1691. }
  1692. return 0;
  1693. }
  1694. /* If we receive more dupacks than we expected counting segments
  1695. * in assumption of absent reordering, interpret this as reordering.
  1696. * The only another reason could be bug in receiver TCP.
  1697. */
  1698. static void tcp_check_reno_reordering(struct sock *sk, const int addend)
  1699. {
  1700. struct tcp_sock *tp = tcp_sk(sk);
  1701. if (tcp_limit_reno_sacked(tp))
  1702. tcp_update_reordering(sk, tp->packets_out + addend, 0);
  1703. }
  1704. /* Emulate SACKs for SACKless connection: account for a new dupack. */
  1705. static void tcp_add_reno_sack(struct sock *sk)
  1706. {
  1707. struct tcp_sock *tp = tcp_sk(sk);
  1708. tp->sacked_out++;
  1709. tcp_check_reno_reordering(sk, 0);
  1710. tcp_verify_left_out(tp);
  1711. }
  1712. /* Account for ACK, ACKing some data in Reno Recovery phase. */
  1713. static void tcp_remove_reno_sacks(struct sock *sk, int acked)
  1714. {
  1715. struct tcp_sock *tp = tcp_sk(sk);
  1716. if (acked > 0) {
  1717. /* One ACK acked hole. The rest eat duplicate ACKs. */
  1718. if (acked - 1 >= tp->sacked_out)
  1719. tp->sacked_out = 0;
  1720. else
  1721. tp->sacked_out -= acked - 1;
  1722. }
  1723. tcp_check_reno_reordering(sk, acked);
  1724. tcp_verify_left_out(tp);
  1725. }
  1726. static inline void tcp_reset_reno_sack(struct tcp_sock *tp)
  1727. {
  1728. tp->sacked_out = 0;
  1729. }
  1730. static int tcp_is_sackfrto(const struct tcp_sock *tp)
  1731. {
  1732. return (sysctl_tcp_frto == 0x2) && !tcp_is_reno(tp);
  1733. }
  1734. /* F-RTO can only be used if TCP has never retransmitted anything other than
  1735. * head (SACK enhanced variant from Appendix B of RFC4138 is more robust here)
  1736. */
  1737. int tcp_use_frto(struct sock *sk)
  1738. {
  1739. const struct tcp_sock *tp = tcp_sk(sk);
  1740. const struct inet_connection_sock *icsk = inet_csk(sk);
  1741. struct sk_buff *skb;
  1742. if (!sysctl_tcp_frto)
  1743. return 0;
  1744. /* MTU probe and F-RTO won't really play nicely along currently */
  1745. if (icsk->icsk_mtup.probe_size)
  1746. return 0;
  1747. if (tcp_is_sackfrto(tp))
  1748. return 1;
  1749. /* Avoid expensive walking of rexmit queue if possible */
  1750. if (tp->retrans_out > 1)
  1751. return 0;
  1752. skb = tcp_write_queue_head(sk);
  1753. if (tcp_skb_is_last(sk, skb))
  1754. return 1;
  1755. skb = tcp_write_queue_next(sk, skb); /* Skips head */
  1756. tcp_for_write_queue_from(skb, sk) {
  1757. if (skb == tcp_send_head(sk))
  1758. break;
  1759. if (TCP_SKB_CB(skb)->sacked & TCPCB_RETRANS)
  1760. return 0;
  1761. /* Short-circuit when first non-SACKed skb has been checked */
  1762. if (!(TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED))
  1763. break;
  1764. }
  1765. return 1;
  1766. }
  1767. /* RTO occurred, but do not yet enter Loss state. Instead, defer RTO
  1768. * recovery a bit and use heuristics in tcp_process_frto() to detect if
  1769. * the RTO was spurious. Only clear SACKED_RETRANS of the head here to
  1770. * keep retrans_out counting accurate (with SACK F-RTO, other than head
  1771. * may still have that bit set); TCPCB_LOST and remaining SACKED_RETRANS
  1772. * bits are handled if the Loss state is really to be entered (in
  1773. * tcp_enter_frto_loss).
  1774. *
  1775. * Do like tcp_enter_loss() would; when RTO expires the second time it
  1776. * does:
  1777. * "Reduce ssthresh if it has not yet been made inside this window."
  1778. */
  1779. void tcp_enter_frto(struct sock *sk)
  1780. {
  1781. const struct inet_connection_sock *icsk = inet_csk(sk);
  1782. struct tcp_sock *tp = tcp_sk(sk);
  1783. struct sk_buff *skb;
  1784. if ((!tp->frto_counter && icsk->icsk_ca_state <= TCP_CA_Disorder) ||
  1785. tp->snd_una == tp->high_seq ||
  1786. ((icsk->icsk_ca_state == TCP_CA_Loss || tp->frto_counter) &&
  1787. !icsk->icsk_retransmits)) {
  1788. tp->prior_ssthresh = tcp_current_ssthresh(sk);
  1789. /* Our state is too optimistic in ssthresh() call because cwnd
  1790. * is not reduced until tcp_enter_frto_loss() when previous F-RTO
  1791. * recovery has not yet completed. Pattern would be this: RTO,
  1792. * Cumulative ACK, RTO (2xRTO for the same segment does not end
  1793. * up here twice).
  1794. * RFC4138 should be more specific on what to do, even though
  1795. * RTO is quite unlikely to occur after the first Cumulative ACK
  1796. * due to back-off and complexity of triggering events ...
  1797. */
  1798. if (tp->frto_counter) {
  1799. u32 stored_cwnd;
  1800. stored_cwnd = tp->snd_cwnd;
  1801. tp->snd_cwnd = 2;
  1802. tp->snd_ssthresh = icsk->icsk_ca_ops->ssthresh(sk);
  1803. tp->snd_cwnd = stored_cwnd;
  1804. } else {
  1805. tp->snd_ssthresh = icsk->icsk_ca_ops->ssthresh(sk);
  1806. }
  1807. /* ... in theory, cong.control module could do "any tricks" in
  1808. * ssthresh(), which means that ca_state, lost bits and lost_out
  1809. * counter would have to be faked before the call occurs. We
  1810. * consider that too expensive, unlikely and hacky, so modules
  1811. * using these in ssthresh() must deal these incompatibility
  1812. * issues if they receives CA_EVENT_FRTO and frto_counter != 0
  1813. */
  1814. tcp_ca_event(sk, CA_EVENT_FRTO);
  1815. }
  1816. tp->undo_marker = tp->snd_una;
  1817. tp->undo_retrans = 0;
  1818. skb = tcp_write_queue_head(sk);
  1819. if (TCP_SKB_CB(skb)->sacked & TCPCB_RETRANS)
  1820. tp->undo_marker = 0;
  1821. if (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_RETRANS) {
  1822. TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS;
  1823. tp->retrans_out -= tcp_skb_pcount(skb);
  1824. }
  1825. tcp_verify_left_out(tp);
  1826. /* Too bad if TCP was application limited */
  1827. tp->snd_cwnd = min(tp->snd_cwnd, tcp_packets_in_flight(tp) + 1);
  1828. /* Earlier loss recovery underway (see RFC4138; Appendix B).
  1829. * The last condition is necessary at least in tp->frto_counter case.
  1830. */
  1831. if (tcp_is_sackfrto(tp) && (tp->frto_counter ||
  1832. ((1 << icsk->icsk_ca_state) & (TCPF_CA_Recovery|TCPF_CA_Loss))) &&
  1833. after(tp->high_seq, tp->snd_una)) {
  1834. tp->frto_highmark = tp->high_seq;
  1835. } else {
  1836. tp->frto_highmark = tp->snd_nxt;
  1837. }
  1838. tcp_set_ca_state(sk, TCP_CA_Disorder);
  1839. tp->high_seq = tp->snd_nxt;
  1840. tp->frto_counter = 1;
  1841. }
  1842. /* Enter Loss state after F-RTO was applied. Dupack arrived after RTO,
  1843. * which indicates that we should follow the traditional RTO recovery,
  1844. * i.e. mark everything lost and do go-back-N retransmission.
  1845. */
  1846. static void tcp_enter_frto_loss(struct sock *sk, int allowed_segments, int flag)
  1847. {
  1848. struct tcp_sock *tp = tcp_sk(sk);
  1849. struct sk_buff *skb;
  1850. tp->lost_out = 0;
  1851. tp->retrans_out = 0;
  1852. if (tcp_is_reno(tp))
  1853. tcp_reset_reno_sack(tp);
  1854. tcp_for_write_queue(skb, sk) {
  1855. if (skb == tcp_send_head(sk))
  1856. break;
  1857. TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST;
  1858. /*
  1859. * Count the retransmission made on RTO correctly (only when
  1860. * waiting for the first ACK and did not get it)...
  1861. */
  1862. if ((tp->frto_counter == 1) && !(flag & FLAG_DATA_ACKED)) {
  1863. /* For some reason this R-bit might get cleared? */
  1864. if (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_RETRANS)
  1865. tp->retrans_out += tcp_skb_pcount(skb);
  1866. /* ...enter this if branch just for the first segment */
  1867. flag |= FLAG_DATA_ACKED;
  1868. } else {
  1869. if (TCP_SKB_CB(skb)->sacked & TCPCB_RETRANS)
  1870. tp->undo_marker = 0;
  1871. TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS;
  1872. }
  1873. /* Marking forward transmissions that were made after RTO lost
  1874. * can cause unnecessary retransmissions in some scenarios,
  1875. * SACK blocks will mitigate that in some but not in all cases.
  1876. * We used to not mark them but it was causing break-ups with
  1877. * receivers that do only in-order receival.
  1878. *
  1879. * TODO: we could detect presence of such receiver and select
  1880. * different behavior per flow.
  1881. */
  1882. if (!(TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED)) {
  1883. TCP_SKB_CB(skb)->sacked |= TCPCB_LOST;
  1884. tp->lost_out += tcp_skb_pcount(skb);
  1885. tp->retransmit_high = TCP_SKB_CB(skb)->end_seq;
  1886. }
  1887. }
  1888. tcp_verify_left_out(tp);
  1889. tp->snd_cwnd = tcp_packets_in_flight(tp) + allowed_segments;
  1890. tp->snd_cwnd_cnt = 0;
  1891. tp->snd_cwnd_stamp = tcp_time_stamp;
  1892. tp->frto_counter = 0;
  1893. tp->bytes_acked = 0;
  1894. tp->reordering = min_t(unsigned int, tp->reordering,
  1895. sysctl_tcp_reordering);
  1896. tcp_set_ca_state(sk, TCP_CA_Loss);
  1897. tp->high_seq = tp->snd_nxt;
  1898. TCP_ECN_queue_cwr(tp);
  1899. tcp_clear_all_retrans_hints(tp);
  1900. }
  1901. static void tcp_clear_retrans_partial(struct tcp_sock *tp)
  1902. {
  1903. tp->retrans_out = 0;
  1904. tp->lost_out = 0;
  1905. tp->undo_marker = 0;
  1906. tp->undo_retrans = 0;
  1907. }
  1908. void tcp_clear_retrans(struct tcp_sock *tp)
  1909. {
  1910. tcp_clear_retrans_partial(tp);
  1911. tp->fackets_out = 0;
  1912. tp->sacked_out = 0;
  1913. }
  1914. /* Enter Loss state. If "how" is not zero, forget all SACK information
  1915. * and reset tags completely, otherwise preserve SACKs. If receiver
  1916. * dropped its ofo queue, we will know this due to reneging detection.
  1917. */
  1918. void tcp_enter_loss(struct sock *sk, int how)
  1919. {
  1920. const struct inet_connection_sock *icsk = inet_csk(sk);
  1921. struct tcp_sock *tp = tcp_sk(sk);
  1922. struct sk_buff *skb;
  1923. /* Reduce ssthresh if it has not yet been made inside this window. */
  1924. if (icsk->icsk_ca_state <= TCP_CA_Disorder || tp->snd_una == tp->high_seq ||
  1925. (icsk->icsk_ca_state == TCP_CA_Loss && !icsk->icsk_retransmits)) {
  1926. tp->prior_ssthresh = tcp_current_ssthresh(sk);
  1927. tp->snd_ssthresh = icsk->icsk_ca_ops->ssthresh(sk);
  1928. tcp_ca_event(sk, CA_EVENT_LOSS);
  1929. }
  1930. tp->snd_cwnd = 1;
  1931. tp->snd_cwnd_cnt = 0;
  1932. tp->snd_cwnd_stamp = tcp_time_stamp;
  1933. tp->bytes_acked = 0;
  1934. tcp_clear_retrans_partial(tp);
  1935. if (tcp_is_reno(tp))
  1936. tcp_reset_reno_sack(tp);
  1937. if (!how) {
  1938. /* Push undo marker, if it was plain RTO and nothing
  1939. * was retransmitted. */
  1940. tp->undo_marker = tp->snd_una;
  1941. } else {
  1942. tp->sacked_out = 0;
  1943. tp->fackets_out = 0;
  1944. }
  1945. tcp_clear_all_retrans_hints(tp);
  1946. tcp_for_write_queue(skb, sk) {
  1947. if (skb == tcp_send_head(sk))
  1948. break;
  1949. if (TCP_SKB_CB(skb)->sacked & TCPCB_RETRANS)
  1950. tp->undo_marker = 0;
  1951. TCP_SKB_CB(skb)->sacked &= (~TCPCB_TAGBITS)|TCPCB_SACKED_ACKED;
  1952. if (!(TCP_SKB_CB(skb)->sacked&TCPCB_SACKED_ACKED) || how) {
  1953. TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_ACKED;
  1954. TCP_SKB_CB(skb)->sacked |= TCPCB_LOST;
  1955. tp->lost_out += tcp_skb_pcount(skb);
  1956. tp->retransmit_high = TCP_SKB_CB(skb)->end_seq;
  1957. }
  1958. }
  1959. tcp_verify_left_out(tp);
  1960. tp->reordering = min_t(unsigned int, tp->reordering,
  1961. sysctl_tcp_reordering);
  1962. tcp_set_ca_state(sk, TCP_CA_Loss);
  1963. tp->high_seq = tp->snd_nxt;
  1964. TCP_ECN_queue_cwr(tp);
  1965. /* Abort F-RTO algorithm if one is in progress */
  1966. tp->frto_counter = 0;
  1967. }
  1968. /* If ACK arrived pointing to a remembered SACK, it means that our
  1969. * remembered SACKs do not reflect real state of receiver i.e.
  1970. * receiver _host_ is heavily congested (or buggy).
  1971. *
  1972. * Do processing similar to RTO timeout.
  1973. */
  1974. static int tcp_check_sack_reneging(struct sock *sk, int flag)
  1975. {
  1976. if (flag & FLAG_SACK_RENEGING) {
  1977. struct inet_connection_sock *icsk = inet_csk(sk);
  1978. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPSACKRENEGING);
  1979. tcp_enter_loss(sk, 1);
  1980. icsk->icsk_retransmits++;
  1981. tcp_retransmit_skb(sk, tcp_write_queue_head(sk));
  1982. inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS,
  1983. icsk->icsk_rto, TCP_RTO_MAX);
  1984. return 1;
  1985. }
  1986. return 0;
  1987. }
  1988. static inline int tcp_fackets_out(struct tcp_sock *tp)
  1989. {
  1990. return tcp_is_reno(tp) ? tp->sacked_out + 1 : tp->fackets_out;
  1991. }
  1992. /* Heurestics to calculate number of duplicate ACKs. There's no dupACKs
  1993. * counter when SACK is enabled (without SACK, sacked_out is used for
  1994. * that purpose).
  1995. *
  1996. * Instead, with FACK TCP uses fackets_out that includes both SACKed
  1997. * segments up to the highest received SACK block so far and holes in
  1998. * between them.
  1999. *
  2000. * With reordering, holes may still be in flight, so RFC3517 recovery
  2001. * uses pure sacked_out (total number of SACKed segments) even though
  2002. * it violates the RFC that uses duplicate ACKs, often these are equal
  2003. * but when e.g. out-of-window ACKs or packet duplication occurs,
  2004. * they differ. Since neither occurs due to loss, TCP should really
  2005. * ignore them.
  2006. */
  2007. static inline int tcp_dupack_heurestics(struct tcp_sock *tp)
  2008. {
  2009. return tcp_is_fack(tp) ? tp->fackets_out : tp->sacked_out + 1;
  2010. }
  2011. static inline int tcp_skb_timedout(struct sock *sk, struct sk_buff *skb)
  2012. {
  2013. return (tcp_time_stamp - TCP_SKB_CB(skb)->when > inet_csk(sk)->icsk_rto);
  2014. }
  2015. static inline int tcp_head_timedout(struct sock *sk)
  2016. {
  2017. struct tcp_sock *tp = tcp_sk(sk);
  2018. return tp->packets_out &&
  2019. tcp_skb_timedout(sk, tcp_write_queue_head(sk));
  2020. }
  2021. /* Linux NewReno/SACK/FACK/ECN state machine.
  2022. * --------------------------------------
  2023. *
  2024. * "Open" Normal state, no dubious events, fast path.
  2025. * "Disorder" In all the respects it is "Open",
  2026. * but requires a bit more attention. It is entered when
  2027. * we see some SACKs or dupacks. It is split of "Open"
  2028. * mainly to move some processing from fast path to slow one.
  2029. * "CWR" CWND was reduced due to some Congestion Notification event.
  2030. * It can be ECN, ICMP source quench, local device congestion.
  2031. * "Recovery" CWND was reduced, we are fast-retransmitting.
  2032. * "Loss" CWND was reduced due to RTO timeout or SACK reneging.
  2033. *
  2034. * tcp_fastretrans_alert() is entered:
  2035. * - each incoming ACK, if state is not "Open"
  2036. * - when arrived ACK is unusual, namely:
  2037. * * SACK
  2038. * * Duplicate ACK.
  2039. * * ECN ECE.
  2040. *
  2041. * Counting packets in flight is pretty simple.
  2042. *
  2043. * in_flight = packets_out - left_out + retrans_out
  2044. *
  2045. * packets_out is SND.NXT-SND.UNA counted in packets.
  2046. *
  2047. * retrans_out is number of retransmitted segments.
  2048. *
  2049. * left_out is number of segments left network, but not ACKed yet.
  2050. *
  2051. * left_out = sacked_out + lost_out
  2052. *
  2053. * sacked_out: Packets, which arrived to receiver out of order
  2054. * and hence not ACKed. With SACKs this number is simply
  2055. * amount of SACKed data. Even without SACKs
  2056. * it is easy to give pretty reliable estimate of this number,
  2057. * counting duplicate ACKs.
  2058. *
  2059. * lost_out: Packets lost by network. TCP has no explicit
  2060. * "loss notification" feedback from network (for now).
  2061. * It means that this number can be only _guessed_.
  2062. * Actually, it is the heuristics to predict lossage that
  2063. * distinguishes different algorithms.
  2064. *
  2065. * F.e. after RTO, when all the queue is considered as lost,
  2066. * lost_out = packets_out and in_flight = retrans_out.
  2067. *
  2068. * Essentially, we have now two algorithms counting
  2069. * lost packets.
  2070. *
  2071. * FACK: It is the simplest heuristics. As soon as we decided
  2072. * that something is lost, we decide that _all_ not SACKed
  2073. * packets until the most forward SACK are lost. I.e.
  2074. * lost_out = fackets_out - sacked_out and left_out = fackets_out.
  2075. * It is absolutely correct estimate, if network does not reorder
  2076. * packets. And it loses any connection to reality when reordering
  2077. * takes place. We use FACK by default until reordering
  2078. * is suspected on the path to this destination.
  2079. *
  2080. * NewReno: when Recovery is entered, we assume that one segment
  2081. * is lost (classic Reno). While we are in Recovery and
  2082. * a partial ACK arrives, we assume that one more packet
  2083. * is lost (NewReno). This heuristics are the same in NewReno
  2084. * and SACK.
  2085. *
  2086. * Imagine, that's all! Forget about all this shamanism about CWND inflation
  2087. * deflation etc. CWND is real congestion window, never inflated, changes
  2088. * only according to classic VJ rules.
  2089. *
  2090. * Really tricky (and requiring careful tuning) part of algorithm
  2091. * is hidden in functions tcp_time_to_recover() and tcp_xmit_retransmit_queue().
  2092. * The first determines the moment _when_ we should reduce CWND and,
  2093. * hence, slow down forward transmission. In fact, it determines the moment
  2094. * when we decide that hole is caused by loss, rather than by a reorder.
  2095. *
  2096. * tcp_xmit_retransmit_queue() decides, _what_ we should retransmit to fill
  2097. * holes, caused by lost packets.
  2098. *
  2099. * And the most logically complicated part of algorithm is undo
  2100. * heuristics. We detect false retransmits due to both too early
  2101. * fast retransmit (reordering) and underestimated RTO, analyzing
  2102. * timestamps and D-SACKs. When we detect that some segments were
  2103. * retransmitted by mistake and CWND reduction was wrong, we undo
  2104. * window reduction and abort recovery phase. This logic is hidden
  2105. * inside several functions named tcp_try_undo_<something>.
  2106. */
  2107. /* This function decides, when we should leave Disordered state
  2108. * and enter Recovery phase, reducing congestion window.
  2109. *
  2110. * Main question: may we further continue forward transmission
  2111. * with the same cwnd?
  2112. */
  2113. static int tcp_time_to_recover(struct sock *sk)
  2114. {
  2115. struct tcp_sock *tp = tcp_sk(sk);
  2116. __u32 packets_out;
  2117. /* Do not perform any recovery during F-RTO algorithm */
  2118. if (tp->frto_counter)
  2119. return 0;
  2120. /* Trick#1: The loss is proven. */
  2121. if (tp->lost_out)
  2122. return 1;
  2123. /* Not-A-Trick#2 : Classic rule... */
  2124. if (tcp_dupack_heurestics(tp) > tp->reordering)
  2125. return 1;
  2126. /* Trick#3 : when we use RFC2988 timer restart, fast
  2127. * retransmit can be triggered by timeout of queue head.
  2128. */
  2129. if (tcp_is_fack(tp) && tcp_head_timedout(sk))
  2130. return 1;
  2131. /* Trick#4: It is still not OK... But will it be useful to delay
  2132. * recovery more?
  2133. */
  2134. packets_out = tp->packets_out;
  2135. if (packets_out <= tp->reordering &&
  2136. tp->sacked_out >= max_t(__u32, packets_out/2, sysctl_tcp_reordering) &&
  2137. !tcp_may_send_now(sk)) {
  2138. /* We have nothing to send. This connection is limited
  2139. * either by receiver window or by application.
  2140. */
  2141. return 1;
  2142. }
  2143. return 0;
  2144. }
  2145. /* Mark head of queue up as lost. With RFC3517 SACK, the packets is
  2146. * is against sacked "cnt", otherwise it's against facked "cnt"
  2147. */
  2148. static void tcp_mark_head_lost(struct sock *sk, int packets)
  2149. {
  2150. struct tcp_sock *tp = tcp_sk(sk);
  2151. struct sk_buff *skb;
  2152. int cnt, oldcnt;
  2153. int err;
  2154. unsigned int mss;
  2155. WARN_ON(packets > tp->packets_out);
  2156. if (tp->lost_skb_hint) {
  2157. skb = tp->lost_skb_hint;
  2158. cnt = tp->lost_cnt_hint;
  2159. } else {
  2160. skb = tcp_write_queue_head(sk);
  2161. cnt = 0;
  2162. }
  2163. tcp_for_write_queue_from(skb, sk) {
  2164. if (skb == tcp_send_head(sk))
  2165. break;
  2166. /* TODO: do this better */
  2167. /* this is not the most efficient way to do this... */
  2168. tp->lost_skb_hint = skb;
  2169. tp->lost_cnt_hint = cnt;
  2170. if (after(TCP_SKB_CB(skb)->end_seq, tp->high_seq))
  2171. break;
  2172. oldcnt = cnt;
  2173. if (tcp_is_fack(tp) || tcp_is_reno(tp) ||
  2174. (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED))
  2175. cnt += tcp_skb_pcount(skb);
  2176. if (cnt > packets) {
  2177. if (tcp_is_sack(tp) || (oldcnt >= packets))
  2178. break;
  2179. mss = skb_shinfo(skb)->gso_size;
  2180. err = tcp_fragment(sk, skb, (packets - oldcnt) * mss, mss);
  2181. if (err < 0)
  2182. break;
  2183. cnt = packets;
  2184. }
  2185. tcp_skb_mark_lost(tp, skb);
  2186. }
  2187. tcp_verify_left_out(tp);
  2188. }
  2189. /* Account newly detected lost packet(s) */
  2190. static void tcp_update_scoreboard(struct sock *sk, int fast_rexmit)
  2191. {
  2192. struct tcp_sock *tp = tcp_sk(sk);
  2193. if (tcp_is_reno(tp)) {
  2194. tcp_mark_head_lost(sk, 1);
  2195. } else if (tcp_is_fack(tp)) {
  2196. int lost = tp->fackets_out - tp->reordering;
  2197. if (lost <= 0)
  2198. lost = 1;
  2199. tcp_mark_head_lost(sk, lost);
  2200. } else {
  2201. int sacked_upto = tp->sacked_out - tp->reordering;
  2202. if (sacked_upto < fast_rexmit)
  2203. sacked_upto = fast_rexmit;
  2204. tcp_mark_head_lost(sk, sacked_upto);
  2205. }
  2206. /* New heuristics: it is possible only after we switched
  2207. * to restart timer each time when something is ACKed.
  2208. * Hence, we can detect timed out packets during fast
  2209. * retransmit without falling to slow start.
  2210. */
  2211. if (tcp_is_fack(tp) && tcp_head_timedout(sk)) {
  2212. struct sk_buff *skb;
  2213. skb = tp->scoreboard_skb_hint ? tp->scoreboard_skb_hint
  2214. : tcp_write_queue_head(sk);
  2215. tcp_for_write_queue_from(skb, sk) {
  2216. if (skb == tcp_send_head(sk))
  2217. break;
  2218. if (!tcp_skb_timedout(sk, skb))
  2219. break;
  2220. tcp_skb_mark_lost(tp, skb);
  2221. }
  2222. tp->scoreboard_skb_hint = skb;
  2223. tcp_verify_left_out(tp);
  2224. }
  2225. }
  2226. /* CWND moderation, preventing bursts due to too big ACKs
  2227. * in dubious situations.
  2228. */
  2229. static inline void tcp_moderate_cwnd(struct tcp_sock *tp)
  2230. {
  2231. tp->snd_cwnd = min(tp->snd_cwnd,
  2232. tcp_packets_in_flight(tp) + tcp_max_burst(tp));
  2233. tp->snd_cwnd_stamp = tcp_time_stamp;
  2234. }
  2235. /* Lower bound on congestion window is slow start threshold
  2236. * unless congestion avoidance choice decides to overide it.
  2237. */
  2238. static inline u32 tcp_cwnd_min(const struct sock *sk)
  2239. {
  2240. const struct tcp_congestion_ops *ca_ops = inet_csk(sk)->icsk_ca_ops;
  2241. return ca_ops->min_cwnd ? ca_ops->min_cwnd(sk) : tcp_sk(sk)->snd_ssthresh;
  2242. }
  2243. /* Decrease cwnd each second ack. */
  2244. static void tcp_cwnd_down(struct sock *sk, int flag)
  2245. {
  2246. struct tcp_sock *tp = tcp_sk(sk);
  2247. int decr = tp->snd_cwnd_cnt + 1;
  2248. if ((flag & (FLAG_ANY_PROGRESS | FLAG_DSACKING_ACK)) ||
  2249. (tcp_is_reno(tp) && !(flag & FLAG_NOT_DUP))) {
  2250. tp->snd_cwnd_cnt = decr & 1;
  2251. decr >>= 1;
  2252. if (decr && tp->snd_cwnd > tcp_cwnd_min(sk))
  2253. tp->snd_cwnd -= decr;
  2254. tp->snd_cwnd = min(tp->snd_cwnd, tcp_packets_in_flight(tp) + 1);
  2255. tp->snd_cwnd_stamp = tcp_time_stamp;
  2256. }
  2257. }
  2258. /* Nothing was retransmitted or returned timestamp is less
  2259. * than timestamp of the first retransmission.
  2260. */
  2261. static inline int tcp_packet_delayed(struct tcp_sock *tp)
  2262. {
  2263. return !tp->retrans_stamp ||
  2264. (tp->rx_opt.saw_tstamp && tp->rx_opt.rcv_tsecr &&
  2265. before(tp->rx_opt.rcv_tsecr, tp->retrans_stamp));
  2266. }
  2267. /* Undo procedures. */
  2268. #if FASTRETRANS_DEBUG > 1
  2269. static void DBGUNDO(struct sock *sk, const char *msg)
  2270. {
  2271. struct tcp_sock *tp = tcp_sk(sk);
  2272. struct inet_sock *inet = inet_sk(sk);
  2273. if (sk->sk_family == AF_INET) {
  2274. printk(KERN_DEBUG "Undo %s %pI4/%u c%u l%u ss%u/%u p%u\n",
  2275. msg,
  2276. &inet->daddr, ntohs(inet->dport),
  2277. tp->snd_cwnd, tcp_left_out(tp),
  2278. tp->snd_ssthresh, tp->prior_ssthresh,
  2279. tp->packets_out);
  2280. }
  2281. #if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE)
  2282. else if (sk->sk_family == AF_INET6) {
  2283. struct ipv6_pinfo *np = inet6_sk(sk);
  2284. printk(KERN_DEBUG "Undo %s %pI6/%u c%u l%u ss%u/%u p%u\n",
  2285. msg,
  2286. &np->daddr, ntohs(inet->dport),
  2287. tp->snd_cwnd, tcp_left_out(tp),
  2288. tp->snd_ssthresh, tp->prior_ssthresh,
  2289. tp->packets_out);
  2290. }
  2291. #endif
  2292. }
  2293. #else
  2294. #define DBGUNDO(x...) do { } while (0)
  2295. #endif
  2296. static void tcp_undo_cwr(struct sock *sk, const int undo)
  2297. {
  2298. struct tcp_sock *tp = tcp_sk(sk);
  2299. if (tp->prior_ssthresh) {
  2300. const struct inet_connection_sock *icsk = inet_csk(sk);
  2301. if (icsk->icsk_ca_ops->undo_cwnd)
  2302. tp->snd_cwnd = icsk->icsk_ca_ops->undo_cwnd(sk);
  2303. else
  2304. tp->snd_cwnd = max(tp->snd_cwnd, tp->snd_ssthresh << 1);
  2305. if (undo && tp->prior_ssthresh > tp->snd_ssthresh) {
  2306. tp->snd_ssthresh = tp->prior_ssthresh;
  2307. TCP_ECN_withdraw_cwr(tp);
  2308. }
  2309. } else {
  2310. tp->snd_cwnd = max(tp->snd_cwnd, tp->snd_ssthresh);
  2311. }
  2312. tcp_moderate_cwnd(tp);
  2313. tp->snd_cwnd_stamp = tcp_time_stamp;
  2314. }
  2315. static inline int tcp_may_undo(struct tcp_sock *tp)
  2316. {
  2317. return tp->undo_marker && (!tp->undo_retrans || tcp_packet_delayed(tp));
  2318. }
  2319. /* People celebrate: "We love our President!" */
  2320. static int tcp_try_undo_recovery(struct sock *sk)
  2321. {
  2322. struct tcp_sock *tp = tcp_sk(sk);
  2323. if (tcp_may_undo(tp)) {
  2324. int mib_idx;
  2325. /* Happy end! We did not retransmit anything
  2326. * or our original transmission succeeded.
  2327. */
  2328. DBGUNDO(sk, inet_csk(sk)->icsk_ca_state == TCP_CA_Loss ? "loss" : "retrans");
  2329. tcp_undo_cwr(sk, 1);
  2330. if (inet_csk(sk)->icsk_ca_state == TCP_CA_Loss)
  2331. mib_idx = LINUX_MIB_TCPLOSSUNDO;
  2332. else
  2333. mib_idx = LINUX_MIB_TCPFULLUNDO;
  2334. NET_INC_STATS_BH(sock_net(sk), mib_idx);
  2335. tp->undo_marker = 0;
  2336. }
  2337. if (tp->snd_una == tp->high_seq && tcp_is_reno(tp)) {
  2338. /* Hold old state until something *above* high_seq
  2339. * is ACKed. For Reno it is MUST to prevent false
  2340. * fast retransmits (RFC2582). SACK TCP is safe. */
  2341. tcp_moderate_cwnd(tp);
  2342. return 1;
  2343. }
  2344. tcp_set_ca_state(sk, TCP_CA_Open);
  2345. return 0;
  2346. }
  2347. /* Try to undo cwnd reduction, because D-SACKs acked all retransmitted data */
  2348. static void tcp_try_undo_dsack(struct sock *sk)
  2349. {
  2350. struct tcp_sock *tp = tcp_sk(sk);
  2351. if (tp->undo_marker && !tp->undo_retrans) {
  2352. DBGUNDO(sk, "D-SACK");
  2353. tcp_undo_cwr(sk, 1);
  2354. tp->undo_marker = 0;
  2355. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPDSACKUNDO);
  2356. }
  2357. }
  2358. /* Undo during fast recovery after partial ACK. */
  2359. static int tcp_try_undo_partial(struct sock *sk, int acked)
  2360. {
  2361. struct tcp_sock *tp = tcp_sk(sk);
  2362. /* Partial ACK arrived. Force Hoe's retransmit. */
  2363. int failed = tcp_is_reno(tp) || (tcp_fackets_out(tp) > tp->reordering);
  2364. if (tcp_may_undo(tp)) {
  2365. /* Plain luck! Hole if filled with delayed
  2366. * packet, rather than with a retransmit.
  2367. */
  2368. if (tp->retrans_out == 0)
  2369. tp->retrans_stamp = 0;
  2370. tcp_update_reordering(sk, tcp_fackets_out(tp) + acked, 1);
  2371. DBGUNDO(sk, "Hoe");
  2372. tcp_undo_cwr(sk, 0);
  2373. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPPARTIALUNDO);
  2374. /* So... Do not make Hoe's retransmit yet.
  2375. * If the first packet was delayed, the rest
  2376. * ones are most probably delayed as well.
  2377. */
  2378. failed = 0;
  2379. }
  2380. return failed;
  2381. }
  2382. /* Undo during loss recovery after partial ACK. */
  2383. static int tcp_try_undo_loss(struct sock *sk)
  2384. {
  2385. struct tcp_sock *tp = tcp_sk(sk);
  2386. if (tcp_may_undo(tp)) {
  2387. struct sk_buff *skb;
  2388. tcp_for_write_queue(skb, sk) {
  2389. if (skb == tcp_send_head(sk))
  2390. break;
  2391. TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST;
  2392. }
  2393. tcp_clear_all_retrans_hints(tp);
  2394. DBGUNDO(sk, "partial loss");
  2395. tp->lost_out = 0;
  2396. tcp_undo_cwr(sk, 1);
  2397. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPLOSSUNDO);
  2398. inet_csk(sk)->icsk_retransmits = 0;
  2399. tp->undo_marker = 0;
  2400. if (tcp_is_sack(tp))
  2401. tcp_set_ca_state(sk, TCP_CA_Open);
  2402. return 1;
  2403. }
  2404. return 0;
  2405. }
  2406. static inline void tcp_complete_cwr(struct sock *sk)
  2407. {
  2408. struct tcp_sock *tp = tcp_sk(sk);
  2409. tp->snd_cwnd = min(tp->snd_cwnd, tp->snd_ssthresh);
  2410. tp->snd_cwnd_stamp = tcp_time_stamp;
  2411. tcp_ca_event(sk, CA_EVENT_COMPLETE_CWR);
  2412. }
  2413. static void tcp_try_keep_open(struct sock *sk)
  2414. {
  2415. struct tcp_sock *tp = tcp_sk(sk);
  2416. int state = TCP_CA_Open;
  2417. if (tcp_left_out(tp) || tp->retrans_out || tp->undo_marker)
  2418. state = TCP_CA_Disorder;
  2419. if (inet_csk(sk)->icsk_ca_state != state) {
  2420. tcp_set_ca_state(sk, state);
  2421. tp->high_seq = tp->snd_nxt;
  2422. }
  2423. }
  2424. static void tcp_try_to_open(struct sock *sk, int flag)
  2425. {
  2426. struct tcp_sock *tp = tcp_sk(sk);
  2427. tcp_verify_left_out(tp);
  2428. if (!tp->frto_counter && tp->retrans_out == 0)
  2429. tp->retrans_stamp = 0;
  2430. if (flag & FLAG_ECE)
  2431. tcp_enter_cwr(sk, 1);
  2432. if (inet_csk(sk)->icsk_ca_state != TCP_CA_CWR) {
  2433. tcp_try_keep_open(sk);
  2434. tcp_moderate_cwnd(tp);
  2435. } else {
  2436. tcp_cwnd_down(sk, flag);
  2437. }
  2438. }
  2439. static void tcp_mtup_probe_failed(struct sock *sk)
  2440. {
  2441. struct inet_connection_sock *icsk = inet_csk(sk);
  2442. icsk->icsk_mtup.search_high = icsk->icsk_mtup.probe_size - 1;
  2443. icsk->icsk_mtup.probe_size = 0;
  2444. }
  2445. static void tcp_mtup_probe_success(struct sock *sk, struct sk_buff *skb)
  2446. {
  2447. struct tcp_sock *tp = tcp_sk(sk);
  2448. struct inet_connection_sock *icsk = inet_csk(sk);
  2449. /* FIXME: breaks with very large cwnd */
  2450. tp->prior_ssthresh = tcp_current_ssthresh(sk);
  2451. tp->snd_cwnd = tp->snd_cwnd *
  2452. tcp_mss_to_mtu(sk, tp->mss_cache) /
  2453. icsk->icsk_mtup.probe_size;
  2454. tp->snd_cwnd_cnt = 0;
  2455. tp->snd_cwnd_stamp = tcp_time_stamp;
  2456. tp->rcv_ssthresh = tcp_current_ssthresh(sk);
  2457. icsk->icsk_mtup.search_low = icsk->icsk_mtup.probe_size;
  2458. icsk->icsk_mtup.probe_size = 0;
  2459. tcp_sync_mss(sk, icsk->icsk_pmtu_cookie);
  2460. }
  2461. /* Do a simple retransmit without using the backoff mechanisms in
  2462. * tcp_timer. This is used for path mtu discovery.
  2463. * The socket is already locked here.
  2464. */
  2465. void tcp_simple_retransmit(struct sock *sk)
  2466. {
  2467. const struct inet_connection_sock *icsk = inet_csk(sk);
  2468. struct tcp_sock *tp = tcp_sk(sk);
  2469. struct sk_buff *skb;
  2470. unsigned int mss = tcp_current_mss(sk, 0);
  2471. u32 prior_lost = tp->lost_out;
  2472. tcp_for_write_queue(skb, sk) {
  2473. if (skb == tcp_send_head(sk))
  2474. break;
  2475. if (skb->len > mss &&
  2476. !(TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED)) {
  2477. if (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_RETRANS) {
  2478. TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS;
  2479. tp->retrans_out -= tcp_skb_pcount(skb);
  2480. }
  2481. tcp_skb_mark_lost_uncond_verify(tp, skb);
  2482. }
  2483. }
  2484. tcp_clear_retrans_hints_partial(tp);
  2485. if (prior_lost == tp->lost_out)
  2486. return;
  2487. if (tcp_is_reno(tp))
  2488. tcp_limit_reno_sacked(tp);
  2489. tcp_verify_left_out(tp);
  2490. /* Don't muck with the congestion window here.
  2491. * Reason is that we do not increase amount of _data_
  2492. * in network, but units changed and effective
  2493. * cwnd/ssthresh really reduced now.
  2494. */
  2495. if (icsk->icsk_ca_state != TCP_CA_Loss) {
  2496. tp->high_seq = tp->snd_nxt;
  2497. tp->snd_ssthresh = tcp_current_ssthresh(sk);
  2498. tp->prior_ssthresh = 0;
  2499. tp->undo_marker = 0;
  2500. tcp_set_ca_state(sk, TCP_CA_Loss);
  2501. }
  2502. tcp_xmit_retransmit_queue(sk);
  2503. }
  2504. /* Process an event, which can update packets-in-flight not trivially.
  2505. * Main goal of this function is to calculate new estimate for left_out,
  2506. * taking into account both packets sitting in receiver's buffer and
  2507. * packets lost by network.
  2508. *
  2509. * Besides that it does CWND reduction, when packet loss is detected
  2510. * and changes state of machine.
  2511. *
  2512. * It does _not_ decide what to send, it is made in function
  2513. * tcp_xmit_retransmit_queue().
  2514. */
  2515. static void tcp_fastretrans_alert(struct sock *sk, int pkts_acked, int flag)
  2516. {
  2517. struct inet_connection_sock *icsk = inet_csk(sk);
  2518. struct tcp_sock *tp = tcp_sk(sk);
  2519. int is_dupack = !(flag & (FLAG_SND_UNA_ADVANCED | FLAG_NOT_DUP));
  2520. int do_lost = is_dupack || ((flag & FLAG_DATA_SACKED) &&
  2521. (tcp_fackets_out(tp) > tp->reordering));
  2522. int fast_rexmit = 0, mib_idx;
  2523. if (WARN_ON(!tp->packets_out && tp->sacked_out))
  2524. tp->sacked_out = 0;
  2525. if (WARN_ON(!tp->sacked_out && tp->fackets_out))
  2526. tp->fackets_out = 0;
  2527. /* Now state machine starts.
  2528. * A. ECE, hence prohibit cwnd undoing, the reduction is required. */
  2529. if (flag & FLAG_ECE)
  2530. tp->prior_ssthresh = 0;
  2531. /* B. In all the states check for reneging SACKs. */
  2532. if (tcp_check_sack_reneging(sk, flag))
  2533. return;
  2534. /* C. Process data loss notification, provided it is valid. */
  2535. if (tcp_is_fack(tp) && (flag & FLAG_DATA_LOST) &&
  2536. before(tp->snd_una, tp->high_seq) &&
  2537. icsk->icsk_ca_state != TCP_CA_Open &&
  2538. tp->fackets_out > tp->reordering) {
  2539. tcp_mark_head_lost(sk, tp->fackets_out - tp->reordering);
  2540. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPLOSS);
  2541. }
  2542. /* D. Check consistency of the current state. */
  2543. tcp_verify_left_out(tp);
  2544. /* E. Check state exit conditions. State can be terminated
  2545. * when high_seq is ACKed. */
  2546. if (icsk->icsk_ca_state == TCP_CA_Open) {
  2547. WARN_ON(tp->retrans_out != 0);
  2548. tp->retrans_stamp = 0;
  2549. } else if (!before(tp->snd_una, tp->high_seq)) {
  2550. switch (icsk->icsk_ca_state) {
  2551. case TCP_CA_Loss:
  2552. icsk->icsk_retransmits = 0;
  2553. if (tcp_try_undo_recovery(sk))
  2554. return;
  2555. break;
  2556. case TCP_CA_CWR:
  2557. /* CWR is to be held something *above* high_seq
  2558. * is ACKed for CWR bit to reach receiver. */
  2559. if (tp->snd_una != tp->high_seq) {
  2560. tcp_complete_cwr(sk);
  2561. tcp_set_ca_state(sk, TCP_CA_Open);
  2562. }
  2563. break;
  2564. case TCP_CA_Disorder:
  2565. tcp_try_undo_dsack(sk);
  2566. if (!tp->undo_marker ||
  2567. /* For SACK case do not Open to allow to undo
  2568. * catching for all duplicate ACKs. */
  2569. tcp_is_reno(tp) || tp->snd_una != tp->high_seq) {
  2570. tp->undo_marker = 0;
  2571. tcp_set_ca_state(sk, TCP_CA_Open);
  2572. }
  2573. break;
  2574. case TCP_CA_Recovery:
  2575. if (tcp_is_reno(tp))
  2576. tcp_reset_reno_sack(tp);
  2577. if (tcp_try_undo_recovery(sk))
  2578. return;
  2579. tcp_complete_cwr(sk);
  2580. break;
  2581. }
  2582. }
  2583. /* F. Process state. */
  2584. switch (icsk->icsk_ca_state) {
  2585. case TCP_CA_Recovery:
  2586. if (!(flag & FLAG_SND_UNA_ADVANCED)) {
  2587. if (tcp_is_reno(tp) && is_dupack)
  2588. tcp_add_reno_sack(sk);
  2589. } else
  2590. do_lost = tcp_try_undo_partial(sk, pkts_acked);
  2591. break;
  2592. case TCP_CA_Loss:
  2593. if (flag & FLAG_DATA_ACKED)
  2594. icsk->icsk_retransmits = 0;
  2595. if (tcp_is_reno(tp) && flag & FLAG_SND_UNA_ADVANCED)
  2596. tcp_reset_reno_sack(tp);
  2597. if (!tcp_try_undo_loss(sk)) {
  2598. tcp_moderate_cwnd(tp);
  2599. tcp_xmit_retransmit_queue(sk);
  2600. return;
  2601. }
  2602. if (icsk->icsk_ca_state != TCP_CA_Open)
  2603. return;
  2604. /* Loss is undone; fall through to processing in Open state. */
  2605. default:
  2606. if (tcp_is_reno(tp)) {
  2607. if (flag & FLAG_SND_UNA_ADVANCED)
  2608. tcp_reset_reno_sack(tp);
  2609. if (is_dupack)
  2610. tcp_add_reno_sack(sk);
  2611. }
  2612. if (icsk->icsk_ca_state == TCP_CA_Disorder)
  2613. tcp_try_undo_dsack(sk);
  2614. if (!tcp_time_to_recover(sk)) {
  2615. tcp_try_to_open(sk, flag);
  2616. return;
  2617. }
  2618. /* MTU probe failure: don't reduce cwnd */
  2619. if (icsk->icsk_ca_state < TCP_CA_CWR &&
  2620. icsk->icsk_mtup.probe_size &&
  2621. tp->snd_una == tp->mtu_probe.probe_seq_start) {
  2622. tcp_mtup_probe_failed(sk);
  2623. /* Restores the reduction we did in tcp_mtup_probe() */
  2624. tp->snd_cwnd++;
  2625. tcp_simple_retransmit(sk);
  2626. return;
  2627. }
  2628. /* Otherwise enter Recovery state */
  2629. if (tcp_is_reno(tp))
  2630. mib_idx = LINUX_MIB_TCPRENORECOVERY;
  2631. else
  2632. mib_idx = LINUX_MIB_TCPSACKRECOVERY;
  2633. NET_INC_STATS_BH(sock_net(sk), mib_idx);
  2634. tp->high_seq = tp->snd_nxt;
  2635. tp->prior_ssthresh = 0;
  2636. tp->undo_marker = tp->snd_una;
  2637. tp->undo_retrans = tp->retrans_out;
  2638. if (icsk->icsk_ca_state < TCP_CA_CWR) {
  2639. if (!(flag & FLAG_ECE))
  2640. tp->prior_ssthresh = tcp_current_ssthresh(sk);
  2641. tp->snd_ssthresh = icsk->icsk_ca_ops->ssthresh(sk);
  2642. TCP_ECN_queue_cwr(tp);
  2643. }
  2644. tp->bytes_acked = 0;
  2645. tp->snd_cwnd_cnt = 0;
  2646. tcp_set_ca_state(sk, TCP_CA_Recovery);
  2647. fast_rexmit = 1;
  2648. }
  2649. if (do_lost || (tcp_is_fack(tp) && tcp_head_timedout(sk)))
  2650. tcp_update_scoreboard(sk, fast_rexmit);
  2651. tcp_cwnd_down(sk, flag);
  2652. tcp_xmit_retransmit_queue(sk);
  2653. }
  2654. /* Read draft-ietf-tcplw-high-performance before mucking
  2655. * with this code. (Supersedes RFC1323)
  2656. */
  2657. static void tcp_ack_saw_tstamp(struct sock *sk, int flag)
  2658. {
  2659. /* RTTM Rule: A TSecr value received in a segment is used to
  2660. * update the averaged RTT measurement only if the segment
  2661. * acknowledges some new data, i.e., only if it advances the
  2662. * left edge of the send window.
  2663. *
  2664. * See draft-ietf-tcplw-high-performance-00, section 3.3.
  2665. * 1998/04/10 Andrey V. Savochkin <saw@msu.ru>
  2666. *
  2667. * Changed: reset backoff as soon as we see the first valid sample.
  2668. * If we do not, we get strongly overestimated rto. With timestamps
  2669. * samples are accepted even from very old segments: f.e., when rtt=1
  2670. * increases to 8, we retransmit 5 times and after 8 seconds delayed
  2671. * answer arrives rto becomes 120 seconds! If at least one of segments
  2672. * in window is lost... Voila. --ANK (010210)
  2673. */
  2674. struct tcp_sock *tp = tcp_sk(sk);
  2675. const __u32 seq_rtt = tcp_time_stamp - tp->rx_opt.rcv_tsecr;
  2676. tcp_rtt_estimator(sk, seq_rtt);
  2677. tcp_set_rto(sk);
  2678. inet_csk(sk)->icsk_backoff = 0;
  2679. tcp_bound_rto(sk);
  2680. }
  2681. static void tcp_ack_no_tstamp(struct sock *sk, u32 seq_rtt, int flag)
  2682. {
  2683. /* We don't have a timestamp. Can only use
  2684. * packets that are not retransmitted to determine
  2685. * rtt estimates. Also, we must not reset the
  2686. * backoff for rto until we get a non-retransmitted
  2687. * packet. This allows us to deal with a situation
  2688. * where the network delay has increased suddenly.
  2689. * I.e. Karn's algorithm. (SIGCOMM '87, p5.)
  2690. */
  2691. if (flag & FLAG_RETRANS_DATA_ACKED)
  2692. return;
  2693. tcp_rtt_estimator(sk, seq_rtt);
  2694. tcp_set_rto(sk);
  2695. inet_csk(sk)->icsk_backoff = 0;
  2696. tcp_bound_rto(sk);
  2697. }
  2698. static inline void tcp_ack_update_rtt(struct sock *sk, const int flag,
  2699. const s32 seq_rtt)
  2700. {
  2701. const struct tcp_sock *tp = tcp_sk(sk);
  2702. /* Note that peer MAY send zero echo. In this case it is ignored. (rfc1323) */
  2703. if (tp->rx_opt.saw_tstamp && tp->rx_opt.rcv_tsecr)
  2704. tcp_ack_saw_tstamp(sk, flag);
  2705. else if (seq_rtt >= 0)
  2706. tcp_ack_no_tstamp(sk, seq_rtt, flag);
  2707. }
  2708. static void tcp_cong_avoid(struct sock *sk, u32 ack, u32 in_flight)
  2709. {
  2710. const struct inet_connection_sock *icsk = inet_csk(sk);
  2711. icsk->icsk_ca_ops->cong_avoid(sk, ack, in_flight);
  2712. tcp_sk(sk)->snd_cwnd_stamp = tcp_time_stamp;
  2713. }
  2714. /* Restart timer after forward progress on connection.
  2715. * RFC2988 recommends to restart timer to now+rto.
  2716. */
  2717. static void tcp_rearm_rto(struct sock *sk)
  2718. {
  2719. struct tcp_sock *tp = tcp_sk(sk);
  2720. if (!tp->packets_out) {
  2721. inet_csk_clear_xmit_timer(sk, ICSK_TIME_RETRANS);
  2722. } else {
  2723. inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS,
  2724. inet_csk(sk)->icsk_rto, TCP_RTO_MAX);
  2725. }
  2726. }
  2727. /* If we get here, the whole TSO packet has not been acked. */
  2728. static u32 tcp_tso_acked(struct sock *sk, struct sk_buff *skb)
  2729. {
  2730. struct tcp_sock *tp = tcp_sk(sk);
  2731. u32 packets_acked;
  2732. BUG_ON(!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una));
  2733. packets_acked = tcp_skb_pcount(skb);
  2734. if (tcp_trim_head(sk, skb, tp->snd_una - TCP_SKB_CB(skb)->seq))
  2735. return 0;
  2736. packets_acked -= tcp_skb_pcount(skb);
  2737. if (packets_acked) {
  2738. BUG_ON(tcp_skb_pcount(skb) == 0);
  2739. BUG_ON(!before(TCP_SKB_CB(skb)->seq, TCP_SKB_CB(skb)->end_seq));
  2740. }
  2741. return packets_acked;
  2742. }
  2743. /* Remove acknowledged frames from the retransmission queue. If our packet
  2744. * is before the ack sequence we can discard it as it's confirmed to have
  2745. * arrived at the other end.
  2746. */
  2747. static int tcp_clean_rtx_queue(struct sock *sk, int prior_fackets,
  2748. u32 prior_snd_una)
  2749. {
  2750. struct tcp_sock *tp = tcp_sk(sk);
  2751. const struct inet_connection_sock *icsk = inet_csk(sk);
  2752. struct sk_buff *skb;
  2753. u32 now = tcp_time_stamp;
  2754. int fully_acked = 1;
  2755. int flag = 0;
  2756. u32 pkts_acked = 0;
  2757. u32 reord = tp->packets_out;
  2758. u32 prior_sacked = tp->sacked_out;
  2759. s32 seq_rtt = -1;
  2760. s32 ca_seq_rtt = -1;
  2761. ktime_t last_ackt = net_invalid_timestamp();
  2762. while ((skb = tcp_write_queue_head(sk)) && skb != tcp_send_head(sk)) {
  2763. struct tcp_skb_cb *scb = TCP_SKB_CB(skb);
  2764. u32 end_seq;
  2765. u32 acked_pcount;
  2766. u8 sacked = scb->sacked;
  2767. /* Determine how many packets and what bytes were acked, tso and else */
  2768. if (after(scb->end_seq, tp->snd_una)) {
  2769. if (tcp_skb_pcount(skb) == 1 ||
  2770. !after(tp->snd_una, scb->seq))
  2771. break;
  2772. acked_pcount = tcp_tso_acked(sk, skb);
  2773. if (!acked_pcount)
  2774. break;
  2775. fully_acked = 0;
  2776. end_seq = tp->snd_una;
  2777. } else {
  2778. acked_pcount = tcp_skb_pcount(skb);
  2779. end_seq = scb->end_seq;
  2780. }
  2781. /* MTU probing checks */
  2782. if (fully_acked && icsk->icsk_mtup.probe_size &&
  2783. !after(tp->mtu_probe.probe_seq_end, scb->end_seq)) {
  2784. tcp_mtup_probe_success(sk, skb);
  2785. }
  2786. if (sacked & TCPCB_RETRANS) {
  2787. if (sacked & TCPCB_SACKED_RETRANS)
  2788. tp->retrans_out -= acked_pcount;
  2789. flag |= FLAG_RETRANS_DATA_ACKED;
  2790. ca_seq_rtt = -1;
  2791. seq_rtt = -1;
  2792. if ((flag & FLAG_DATA_ACKED) || (acked_pcount > 1))
  2793. flag |= FLAG_NONHEAD_RETRANS_ACKED;
  2794. } else {
  2795. ca_seq_rtt = now - scb->when;
  2796. last_ackt = skb->tstamp;
  2797. if (seq_rtt < 0) {
  2798. seq_rtt = ca_seq_rtt;
  2799. }
  2800. if (!(sacked & TCPCB_SACKED_ACKED))
  2801. reord = min(pkts_acked, reord);
  2802. }
  2803. if (sacked & TCPCB_SACKED_ACKED)
  2804. tp->sacked_out -= acked_pcount;
  2805. if (sacked & TCPCB_LOST)
  2806. tp->lost_out -= acked_pcount;
  2807. tp->packets_out -= acked_pcount;
  2808. pkts_acked += acked_pcount;
  2809. /* Initial outgoing SYN's get put onto the write_queue
  2810. * just like anything else we transmit. It is not
  2811. * true data, and if we misinform our callers that
  2812. * this ACK acks real data, we will erroneously exit
  2813. * connection startup slow start one packet too
  2814. * quickly. This is severely frowned upon behavior.
  2815. */
  2816. if (!(scb->flags & TCPCB_FLAG_SYN)) {
  2817. flag |= FLAG_DATA_ACKED;
  2818. } else {
  2819. flag |= FLAG_SYN_ACKED;
  2820. tp->retrans_stamp = 0;
  2821. }
  2822. if (!fully_acked)
  2823. break;
  2824. tcp_unlink_write_queue(skb, sk);
  2825. sk_wmem_free_skb(sk, skb);
  2826. tp->scoreboard_skb_hint = NULL;
  2827. if (skb == tp->retransmit_skb_hint)
  2828. tp->retransmit_skb_hint = NULL;
  2829. if (skb == tp->lost_skb_hint)
  2830. tp->lost_skb_hint = NULL;
  2831. }
  2832. if (likely(between(tp->snd_up, prior_snd_una, tp->snd_una)))
  2833. tp->snd_up = tp->snd_una;
  2834. if (skb && (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED))
  2835. flag |= FLAG_SACK_RENEGING;
  2836. if (flag & FLAG_ACKED) {
  2837. const struct tcp_congestion_ops *ca_ops
  2838. = inet_csk(sk)->icsk_ca_ops;
  2839. tcp_ack_update_rtt(sk, flag, seq_rtt);
  2840. tcp_rearm_rto(sk);
  2841. if (tcp_is_reno(tp)) {
  2842. tcp_remove_reno_sacks(sk, pkts_acked);
  2843. } else {
  2844. /* Non-retransmitted hole got filled? That's reordering */
  2845. if (reord < prior_fackets)
  2846. tcp_update_reordering(sk, tp->fackets_out - reord, 0);
  2847. /* No need to care for underflows here because
  2848. * the lost_skb_hint gets NULLed if we're past it
  2849. * (or something non-trivial happened)
  2850. */
  2851. if (tcp_is_fack(tp))
  2852. tp->lost_cnt_hint -= pkts_acked;
  2853. else
  2854. tp->lost_cnt_hint -= prior_sacked - tp->sacked_out;
  2855. }
  2856. tp->fackets_out -= min(pkts_acked, tp->fackets_out);
  2857. if (ca_ops->pkts_acked) {
  2858. s32 rtt_us = -1;
  2859. /* Is the ACK triggering packet unambiguous? */
  2860. if (!(flag & FLAG_RETRANS_DATA_ACKED)) {
  2861. /* High resolution needed and available? */
  2862. if (ca_ops->flags & TCP_CONG_RTT_STAMP &&
  2863. !ktime_equal(last_ackt,
  2864. net_invalid_timestamp()))
  2865. rtt_us = ktime_us_delta(ktime_get_real(),
  2866. last_ackt);
  2867. else if (ca_seq_rtt > 0)
  2868. rtt_us = jiffies_to_usecs(ca_seq_rtt);
  2869. }
  2870. ca_ops->pkts_acked(sk, pkts_acked, rtt_us);
  2871. }
  2872. }
  2873. #if FASTRETRANS_DEBUG > 0
  2874. WARN_ON((int)tp->sacked_out < 0);
  2875. WARN_ON((int)tp->lost_out < 0);
  2876. WARN_ON((int)tp->retrans_out < 0);
  2877. if (!tp->packets_out && tcp_is_sack(tp)) {
  2878. icsk = inet_csk(sk);
  2879. if (tp->lost_out) {
  2880. printk(KERN_DEBUG "Leak l=%u %d\n",
  2881. tp->lost_out, icsk->icsk_ca_state);
  2882. tp->lost_out = 0;
  2883. }
  2884. if (tp->sacked_out) {
  2885. printk(KERN_DEBUG "Leak s=%u %d\n",
  2886. tp->sacked_out, icsk->icsk_ca_state);
  2887. tp->sacked_out = 0;
  2888. }
  2889. if (tp->retrans_out) {
  2890. printk(KERN_DEBUG "Leak r=%u %d\n",
  2891. tp->retrans_out, icsk->icsk_ca_state);
  2892. tp->retrans_out = 0;
  2893. }
  2894. }
  2895. #endif
  2896. return flag;
  2897. }
  2898. static void tcp_ack_probe(struct sock *sk)
  2899. {
  2900. const struct tcp_sock *tp = tcp_sk(sk);
  2901. struct inet_connection_sock *icsk = inet_csk(sk);
  2902. /* Was it a usable window open? */
  2903. if (!after(TCP_SKB_CB(tcp_send_head(sk))->end_seq, tcp_wnd_end(tp))) {
  2904. icsk->icsk_backoff = 0;
  2905. inet_csk_clear_xmit_timer(sk, ICSK_TIME_PROBE0);
  2906. /* Socket must be waked up by subsequent tcp_data_snd_check().
  2907. * This function is not for random using!
  2908. */
  2909. } else {
  2910. inet_csk_reset_xmit_timer(sk, ICSK_TIME_PROBE0,
  2911. min(icsk->icsk_rto << icsk->icsk_backoff, TCP_RTO_MAX),
  2912. TCP_RTO_MAX);
  2913. }
  2914. }
  2915. static inline int tcp_ack_is_dubious(const struct sock *sk, const int flag)
  2916. {
  2917. return (!(flag & FLAG_NOT_DUP) || (flag & FLAG_CA_ALERT) ||
  2918. inet_csk(sk)->icsk_ca_state != TCP_CA_Open);
  2919. }
  2920. static inline int tcp_may_raise_cwnd(const struct sock *sk, const int flag)
  2921. {
  2922. const struct tcp_sock *tp = tcp_sk(sk);
  2923. return (!(flag & FLAG_ECE) || tp->snd_cwnd < tp->snd_ssthresh) &&
  2924. !((1 << inet_csk(sk)->icsk_ca_state) & (TCPF_CA_Recovery | TCPF_CA_CWR));
  2925. }
  2926. /* Check that window update is acceptable.
  2927. * The function assumes that snd_una<=ack<=snd_next.
  2928. */
  2929. static inline int tcp_may_update_window(const struct tcp_sock *tp,
  2930. const u32 ack, const u32 ack_seq,
  2931. const u32 nwin)
  2932. {
  2933. return (after(ack, tp->snd_una) ||
  2934. after(ack_seq, tp->snd_wl1) ||
  2935. (ack_seq == tp->snd_wl1 && nwin > tp->snd_wnd));
  2936. }
  2937. /* Update our send window.
  2938. *
  2939. * Window update algorithm, described in RFC793/RFC1122 (used in linux-2.2
  2940. * and in FreeBSD. NetBSD's one is even worse.) is wrong.
  2941. */
  2942. static int tcp_ack_update_window(struct sock *sk, struct sk_buff *skb, u32 ack,
  2943. u32 ack_seq)
  2944. {
  2945. struct tcp_sock *tp = tcp_sk(sk);
  2946. int flag = 0;
  2947. u32 nwin = ntohs(tcp_hdr(skb)->window);
  2948. if (likely(!tcp_hdr(skb)->syn))
  2949. nwin <<= tp->rx_opt.snd_wscale;
  2950. if (tcp_may_update_window(tp, ack, ack_seq, nwin)) {
  2951. flag |= FLAG_WIN_UPDATE;
  2952. tcp_update_wl(tp, ack, ack_seq);
  2953. if (tp->snd_wnd != nwin) {
  2954. tp->snd_wnd = nwin;
  2955. /* Note, it is the only place, where
  2956. * fast path is recovered for sending TCP.
  2957. */
  2958. tp->pred_flags = 0;
  2959. tcp_fast_path_check(sk);
  2960. if (nwin > tp->max_window) {
  2961. tp->max_window = nwin;
  2962. tcp_sync_mss(sk, inet_csk(sk)->icsk_pmtu_cookie);
  2963. }
  2964. }
  2965. }
  2966. tp->snd_una = ack;
  2967. return flag;
  2968. }
  2969. /* A very conservative spurious RTO response algorithm: reduce cwnd and
  2970. * continue in congestion avoidance.
  2971. */
  2972. static void tcp_conservative_spur_to_response(struct tcp_sock *tp)
  2973. {
  2974. tp->snd_cwnd = min(tp->snd_cwnd, tp->snd_ssthresh);
  2975. tp->snd_cwnd_cnt = 0;
  2976. tp->bytes_acked = 0;
  2977. TCP_ECN_queue_cwr(tp);
  2978. tcp_moderate_cwnd(tp);
  2979. }
  2980. /* A conservative spurious RTO response algorithm: reduce cwnd using
  2981. * rate halving and continue in congestion avoidance.
  2982. */
  2983. static void tcp_ratehalving_spur_to_response(struct sock *sk)
  2984. {
  2985. tcp_enter_cwr(sk, 0);
  2986. }
  2987. static void tcp_undo_spur_to_response(struct sock *sk, int flag)
  2988. {
  2989. if (flag & FLAG_ECE)
  2990. tcp_ratehalving_spur_to_response(sk);
  2991. else
  2992. tcp_undo_cwr(sk, 1);
  2993. }
  2994. /* F-RTO spurious RTO detection algorithm (RFC4138)
  2995. *
  2996. * F-RTO affects during two new ACKs following RTO (well, almost, see inline
  2997. * comments). State (ACK number) is kept in frto_counter. When ACK advances
  2998. * window (but not to or beyond highest sequence sent before RTO):
  2999. * On First ACK, send two new segments out.
  3000. * On Second ACK, RTO was likely spurious. Do spurious response (response
  3001. * algorithm is not part of the F-RTO detection algorithm
  3002. * given in RFC4138 but can be selected separately).
  3003. * Otherwise (basically on duplicate ACK), RTO was (likely) caused by a loss
  3004. * and TCP falls back to conventional RTO recovery. F-RTO allows overriding
  3005. * of Nagle, this is done using frto_counter states 2 and 3, when a new data
  3006. * segment of any size sent during F-RTO, state 2 is upgraded to 3.
  3007. *
  3008. * Rationale: if the RTO was spurious, new ACKs should arrive from the
  3009. * original window even after we transmit two new data segments.
  3010. *
  3011. * SACK version:
  3012. * on first step, wait until first cumulative ACK arrives, then move to
  3013. * the second step. In second step, the next ACK decides.
  3014. *
  3015. * F-RTO is implemented (mainly) in four functions:
  3016. * - tcp_use_frto() is used to determine if TCP is can use F-RTO
  3017. * - tcp_enter_frto() prepares TCP state on RTO if F-RTO is used, it is
  3018. * called when tcp_use_frto() showed green light
  3019. * - tcp_process_frto() handles incoming ACKs during F-RTO algorithm
  3020. * - tcp_enter_frto_loss() is called if there is not enough evidence
  3021. * to prove that the RTO is indeed spurious. It transfers the control
  3022. * from F-RTO to the conventional RTO recovery
  3023. */
  3024. static int tcp_process_frto(struct sock *sk, int flag)
  3025. {
  3026. struct tcp_sock *tp = tcp_sk(sk);
  3027. tcp_verify_left_out(tp);
  3028. /* Duplicate the behavior from Loss state (fastretrans_alert) */
  3029. if (flag & FLAG_DATA_ACKED)
  3030. inet_csk(sk)->icsk_retransmits = 0;
  3031. if ((flag & FLAG_NONHEAD_RETRANS_ACKED) ||
  3032. ((tp->frto_counter >= 2) && (flag & FLAG_RETRANS_DATA_ACKED)))
  3033. tp->undo_marker = 0;
  3034. if (!before(tp->snd_una, tp->frto_highmark)) {
  3035. tcp_enter_frto_loss(sk, (tp->frto_counter == 1 ? 2 : 3), flag);
  3036. return 1;
  3037. }
  3038. if (!tcp_is_sackfrto(tp)) {
  3039. /* RFC4138 shortcoming in step 2; should also have case c):
  3040. * ACK isn't duplicate nor advances window, e.g., opposite dir
  3041. * data, winupdate
  3042. */
  3043. if (!(flag & FLAG_ANY_PROGRESS) && (flag & FLAG_NOT_DUP))
  3044. return 1;
  3045. if (!(flag & FLAG_DATA_ACKED)) {
  3046. tcp_enter_frto_loss(sk, (tp->frto_counter == 1 ? 0 : 3),
  3047. flag);
  3048. return 1;
  3049. }
  3050. } else {
  3051. if (!(flag & FLAG_DATA_ACKED) && (tp->frto_counter == 1)) {
  3052. /* Prevent sending of new data. */
  3053. tp->snd_cwnd = min(tp->snd_cwnd,
  3054. tcp_packets_in_flight(tp));
  3055. return 1;
  3056. }
  3057. if ((tp->frto_counter >= 2) &&
  3058. (!(flag & FLAG_FORWARD_PROGRESS) ||
  3059. ((flag & FLAG_DATA_SACKED) &&
  3060. !(flag & FLAG_ONLY_ORIG_SACKED)))) {
  3061. /* RFC4138 shortcoming (see comment above) */
  3062. if (!(flag & FLAG_FORWARD_PROGRESS) &&
  3063. (flag & FLAG_NOT_DUP))
  3064. return 1;
  3065. tcp_enter_frto_loss(sk, 3, flag);
  3066. return 1;
  3067. }
  3068. }
  3069. if (tp->frto_counter == 1) {
  3070. /* tcp_may_send_now needs to see updated state */
  3071. tp->snd_cwnd = tcp_packets_in_flight(tp) + 2;
  3072. tp->frto_counter = 2;
  3073. if (!tcp_may_send_now(sk))
  3074. tcp_enter_frto_loss(sk, 2, flag);
  3075. return 1;
  3076. } else {
  3077. switch (sysctl_tcp_frto_response) {
  3078. case 2:
  3079. tcp_undo_spur_to_response(sk, flag);
  3080. break;
  3081. case 1:
  3082. tcp_conservative_spur_to_response(tp);
  3083. break;
  3084. default:
  3085. tcp_ratehalving_spur_to_response(sk);
  3086. break;
  3087. }
  3088. tp->frto_counter = 0;
  3089. tp->undo_marker = 0;
  3090. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPSPURIOUSRTOS);
  3091. }
  3092. return 0;
  3093. }
  3094. /* This routine deals with incoming acks, but not outgoing ones. */
  3095. static int tcp_ack(struct sock *sk, struct sk_buff *skb, int flag)
  3096. {
  3097. struct inet_connection_sock *icsk = inet_csk(sk);
  3098. struct tcp_sock *tp = tcp_sk(sk);
  3099. u32 prior_snd_una = tp->snd_una;
  3100. u32 ack_seq = TCP_SKB_CB(skb)->seq;
  3101. u32 ack = TCP_SKB_CB(skb)->ack_seq;
  3102. u32 prior_in_flight;
  3103. u32 prior_fackets;
  3104. int prior_packets;
  3105. int frto_cwnd = 0;
  3106. /* If the ack is newer than sent or older than previous acks
  3107. * then we can probably ignore it.
  3108. */
  3109. if (after(ack, tp->snd_nxt))
  3110. goto uninteresting_ack;
  3111. if (before(ack, prior_snd_una))
  3112. goto old_ack;
  3113. if (after(ack, prior_snd_una))
  3114. flag |= FLAG_SND_UNA_ADVANCED;
  3115. if (sysctl_tcp_abc) {
  3116. if (icsk->icsk_ca_state < TCP_CA_CWR)
  3117. tp->bytes_acked += ack - prior_snd_una;
  3118. else if (icsk->icsk_ca_state == TCP_CA_Loss)
  3119. /* we assume just one segment left network */
  3120. tp->bytes_acked += min(ack - prior_snd_una,
  3121. tp->mss_cache);
  3122. }
  3123. prior_fackets = tp->fackets_out;
  3124. prior_in_flight = tcp_packets_in_flight(tp);
  3125. if (!(flag & FLAG_SLOWPATH) && after(ack, prior_snd_una)) {
  3126. /* Window is constant, pure forward advance.
  3127. * No more checks are required.
  3128. * Note, we use the fact that SND.UNA>=SND.WL2.
  3129. */
  3130. tcp_update_wl(tp, ack, ack_seq);
  3131. tp->snd_una = ack;
  3132. flag |= FLAG_WIN_UPDATE;
  3133. tcp_ca_event(sk, CA_EVENT_FAST_ACK);
  3134. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPHPACKS);
  3135. } else {
  3136. if (ack_seq != TCP_SKB_CB(skb)->end_seq)
  3137. flag |= FLAG_DATA;
  3138. else
  3139. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPPUREACKS);
  3140. flag |= tcp_ack_update_window(sk, skb, ack, ack_seq);
  3141. if (TCP_SKB_CB(skb)->sacked)
  3142. flag |= tcp_sacktag_write_queue(sk, skb, prior_snd_una);
  3143. if (TCP_ECN_rcv_ecn_echo(tp, tcp_hdr(skb)))
  3144. flag |= FLAG_ECE;
  3145. tcp_ca_event(sk, CA_EVENT_SLOW_ACK);
  3146. }
  3147. /* We passed data and got it acked, remove any soft error
  3148. * log. Something worked...
  3149. */
  3150. sk->sk_err_soft = 0;
  3151. icsk->icsk_probes_out = 0;
  3152. tp->rcv_tstamp = tcp_time_stamp;
  3153. prior_packets = tp->packets_out;
  3154. if (!prior_packets)
  3155. goto no_queue;
  3156. /* See if we can take anything off of the retransmit queue. */
  3157. flag |= tcp_clean_rtx_queue(sk, prior_fackets, prior_snd_una);
  3158. if (tp->frto_counter)
  3159. frto_cwnd = tcp_process_frto(sk, flag);
  3160. /* Guarantee sacktag reordering detection against wrap-arounds */
  3161. if (before(tp->frto_highmark, tp->snd_una))
  3162. tp->frto_highmark = 0;
  3163. if (tcp_ack_is_dubious(sk, flag)) {
  3164. /* Advance CWND, if state allows this. */
  3165. if ((flag & FLAG_DATA_ACKED) && !frto_cwnd &&
  3166. tcp_may_raise_cwnd(sk, flag))
  3167. tcp_cong_avoid(sk, ack, prior_in_flight);
  3168. tcp_fastretrans_alert(sk, prior_packets - tp->packets_out,
  3169. flag);
  3170. } else {
  3171. if ((flag & FLAG_DATA_ACKED) && !frto_cwnd)
  3172. tcp_cong_avoid(sk, ack, prior_in_flight);
  3173. }
  3174. if ((flag & FLAG_FORWARD_PROGRESS) || !(flag & FLAG_NOT_DUP))
  3175. dst_confirm(sk->sk_dst_cache);
  3176. return 1;
  3177. no_queue:
  3178. /* If this ack opens up a zero window, clear backoff. It was
  3179. * being used to time the probes, and is probably far higher than
  3180. * it needs to be for normal retransmission.
  3181. */
  3182. if (tcp_send_head(sk))
  3183. tcp_ack_probe(sk);
  3184. return 1;
  3185. old_ack:
  3186. if (TCP_SKB_CB(skb)->sacked) {
  3187. tcp_sacktag_write_queue(sk, skb, prior_snd_una);
  3188. if (icsk->icsk_ca_state == TCP_CA_Open)
  3189. tcp_try_keep_open(sk);
  3190. }
  3191. uninteresting_ack:
  3192. SOCK_DEBUG(sk, "Ack %u out of %u:%u\n", ack, tp->snd_una, tp->snd_nxt);
  3193. return 0;
  3194. }
  3195. /* Look for tcp options. Normally only called on SYN and SYNACK packets.
  3196. * But, this can also be called on packets in the established flow when
  3197. * the fast version below fails.
  3198. */
  3199. void tcp_parse_options(struct sk_buff *skb, struct tcp_options_received *opt_rx,
  3200. int estab)
  3201. {
  3202. unsigned char *ptr;
  3203. struct tcphdr *th = tcp_hdr(skb);
  3204. int length = (th->doff * 4) - sizeof(struct tcphdr);
  3205. ptr = (unsigned char *)(th + 1);
  3206. opt_rx->saw_tstamp = 0;
  3207. while (length > 0) {
  3208. int opcode = *ptr++;
  3209. int opsize;
  3210. switch (opcode) {
  3211. case TCPOPT_EOL:
  3212. return;
  3213. case TCPOPT_NOP: /* Ref: RFC 793 section 3.1 */
  3214. length--;
  3215. continue;
  3216. default:
  3217. opsize = *ptr++;
  3218. if (opsize < 2) /* "silly options" */
  3219. return;
  3220. if (opsize > length)
  3221. return; /* don't parse partial options */
  3222. switch (opcode) {
  3223. case TCPOPT_MSS:
  3224. if (opsize == TCPOLEN_MSS && th->syn && !estab) {
  3225. u16 in_mss = get_unaligned_be16(ptr);
  3226. if (in_mss) {
  3227. if (opt_rx->user_mss &&
  3228. opt_rx->user_mss < in_mss)
  3229. in_mss = opt_rx->user_mss;
  3230. opt_rx->mss_clamp = in_mss;
  3231. }
  3232. }
  3233. break;
  3234. case TCPOPT_WINDOW:
  3235. if (opsize == TCPOLEN_WINDOW && th->syn &&
  3236. !estab && sysctl_tcp_window_scaling) {
  3237. __u8 snd_wscale = *(__u8 *)ptr;
  3238. opt_rx->wscale_ok = 1;
  3239. if (snd_wscale > 14) {
  3240. if (net_ratelimit())
  3241. printk(KERN_INFO "tcp_parse_options: Illegal window "
  3242. "scaling value %d >14 received.\n",
  3243. snd_wscale);
  3244. snd_wscale = 14;
  3245. }
  3246. opt_rx->snd_wscale = snd_wscale;
  3247. }
  3248. break;
  3249. case TCPOPT_TIMESTAMP:
  3250. if ((opsize == TCPOLEN_TIMESTAMP) &&
  3251. ((estab && opt_rx->tstamp_ok) ||
  3252. (!estab && sysctl_tcp_timestamps))) {
  3253. opt_rx->saw_tstamp = 1;
  3254. opt_rx->rcv_tsval = get_unaligned_be32(ptr);
  3255. opt_rx->rcv_tsecr = get_unaligned_be32(ptr + 4);
  3256. }
  3257. break;
  3258. case TCPOPT_SACK_PERM:
  3259. if (opsize == TCPOLEN_SACK_PERM && th->syn &&
  3260. !estab && sysctl_tcp_sack) {
  3261. opt_rx->sack_ok = 1;
  3262. tcp_sack_reset(opt_rx);
  3263. }
  3264. break;
  3265. case TCPOPT_SACK:
  3266. if ((opsize >= (TCPOLEN_SACK_BASE + TCPOLEN_SACK_PERBLOCK)) &&
  3267. !((opsize - TCPOLEN_SACK_BASE) % TCPOLEN_SACK_PERBLOCK) &&
  3268. opt_rx->sack_ok) {
  3269. TCP_SKB_CB(skb)->sacked = (ptr - 2) - (unsigned char *)th;
  3270. }
  3271. break;
  3272. #ifdef CONFIG_TCP_MD5SIG
  3273. case TCPOPT_MD5SIG:
  3274. /*
  3275. * The MD5 Hash has already been
  3276. * checked (see tcp_v{4,6}_do_rcv()).
  3277. */
  3278. break;
  3279. #endif
  3280. }
  3281. ptr += opsize-2;
  3282. length -= opsize;
  3283. }
  3284. }
  3285. }
  3286. static int tcp_parse_aligned_timestamp(struct tcp_sock *tp, struct tcphdr *th)
  3287. {
  3288. __be32 *ptr = (__be32 *)(th + 1);
  3289. if (*ptr == htonl((TCPOPT_NOP << 24) | (TCPOPT_NOP << 16)
  3290. | (TCPOPT_TIMESTAMP << 8) | TCPOLEN_TIMESTAMP)) {
  3291. tp->rx_opt.saw_tstamp = 1;
  3292. ++ptr;
  3293. tp->rx_opt.rcv_tsval = ntohl(*ptr);
  3294. ++ptr;
  3295. tp->rx_opt.rcv_tsecr = ntohl(*ptr);
  3296. return 1;
  3297. }
  3298. return 0;
  3299. }
  3300. /* Fast parse options. This hopes to only see timestamps.
  3301. * If it is wrong it falls back on tcp_parse_options().
  3302. */
  3303. static int tcp_fast_parse_options(struct sk_buff *skb, struct tcphdr *th,
  3304. struct tcp_sock *tp)
  3305. {
  3306. if (th->doff == sizeof(struct tcphdr) >> 2) {
  3307. tp->rx_opt.saw_tstamp = 0;
  3308. return 0;
  3309. } else if (tp->rx_opt.tstamp_ok &&
  3310. th->doff == (sizeof(struct tcphdr)>>2)+(TCPOLEN_TSTAMP_ALIGNED>>2)) {
  3311. if (tcp_parse_aligned_timestamp(tp, th))
  3312. return 1;
  3313. }
  3314. tcp_parse_options(skb, &tp->rx_opt, 1);
  3315. return 1;
  3316. }
  3317. #ifdef CONFIG_TCP_MD5SIG
  3318. /*
  3319. * Parse MD5 Signature option
  3320. */
  3321. u8 *tcp_parse_md5sig_option(struct tcphdr *th)
  3322. {
  3323. int length = (th->doff << 2) - sizeof (*th);
  3324. u8 *ptr = (u8*)(th + 1);
  3325. /* If the TCP option is too short, we can short cut */
  3326. if (length < TCPOLEN_MD5SIG)
  3327. return NULL;
  3328. while (length > 0) {
  3329. int opcode = *ptr++;
  3330. int opsize;
  3331. switch(opcode) {
  3332. case TCPOPT_EOL:
  3333. return NULL;
  3334. case TCPOPT_NOP:
  3335. length--;
  3336. continue;
  3337. default:
  3338. opsize = *ptr++;
  3339. if (opsize < 2 || opsize > length)
  3340. return NULL;
  3341. if (opcode == TCPOPT_MD5SIG)
  3342. return ptr;
  3343. }
  3344. ptr += opsize - 2;
  3345. length -= opsize;
  3346. }
  3347. return NULL;
  3348. }
  3349. #endif
  3350. static inline void tcp_store_ts_recent(struct tcp_sock *tp)
  3351. {
  3352. tp->rx_opt.ts_recent = tp->rx_opt.rcv_tsval;
  3353. tp->rx_opt.ts_recent_stamp = get_seconds();
  3354. }
  3355. static inline void tcp_replace_ts_recent(struct tcp_sock *tp, u32 seq)
  3356. {
  3357. if (tp->rx_opt.saw_tstamp && !after(seq, tp->rcv_wup)) {
  3358. /* PAWS bug workaround wrt. ACK frames, the PAWS discard
  3359. * extra check below makes sure this can only happen
  3360. * for pure ACK frames. -DaveM
  3361. *
  3362. * Not only, also it occurs for expired timestamps.
  3363. */
  3364. if ((s32)(tp->rx_opt.rcv_tsval - tp->rx_opt.ts_recent) >= 0 ||
  3365. get_seconds() >= tp->rx_opt.ts_recent_stamp + TCP_PAWS_24DAYS)
  3366. tcp_store_ts_recent(tp);
  3367. }
  3368. }
  3369. /* Sorry, PAWS as specified is broken wrt. pure-ACKs -DaveM
  3370. *
  3371. * It is not fatal. If this ACK does _not_ change critical state (seqs, window)
  3372. * it can pass through stack. So, the following predicate verifies that
  3373. * this segment is not used for anything but congestion avoidance or
  3374. * fast retransmit. Moreover, we even are able to eliminate most of such
  3375. * second order effects, if we apply some small "replay" window (~RTO)
  3376. * to timestamp space.
  3377. *
  3378. * All these measures still do not guarantee that we reject wrapped ACKs
  3379. * on networks with high bandwidth, when sequence space is recycled fastly,
  3380. * but it guarantees that such events will be very rare and do not affect
  3381. * connection seriously. This doesn't look nice, but alas, PAWS is really
  3382. * buggy extension.
  3383. *
  3384. * [ Later note. Even worse! It is buggy for segments _with_ data. RFC
  3385. * states that events when retransmit arrives after original data are rare.
  3386. * It is a blatant lie. VJ forgot about fast retransmit! 8)8) It is
  3387. * the biggest problem on large power networks even with minor reordering.
  3388. * OK, let's give it small replay window. If peer clock is even 1hz, it is safe
  3389. * up to bandwidth of 18Gigabit/sec. 8) ]
  3390. */
  3391. static int tcp_disordered_ack(const struct sock *sk, const struct sk_buff *skb)
  3392. {
  3393. struct tcp_sock *tp = tcp_sk(sk);
  3394. struct tcphdr *th = tcp_hdr(skb);
  3395. u32 seq = TCP_SKB_CB(skb)->seq;
  3396. u32 ack = TCP_SKB_CB(skb)->ack_seq;
  3397. return (/* 1. Pure ACK with correct sequence number. */
  3398. (th->ack && seq == TCP_SKB_CB(skb)->end_seq && seq == tp->rcv_nxt) &&
  3399. /* 2. ... and duplicate ACK. */
  3400. ack == tp->snd_una &&
  3401. /* 3. ... and does not update window. */
  3402. !tcp_may_update_window(tp, ack, seq, ntohs(th->window) << tp->rx_opt.snd_wscale) &&
  3403. /* 4. ... and sits in replay window. */
  3404. (s32)(tp->rx_opt.ts_recent - tp->rx_opt.rcv_tsval) <= (inet_csk(sk)->icsk_rto * 1024) / HZ);
  3405. }
  3406. static inline int tcp_paws_discard(const struct sock *sk,
  3407. const struct sk_buff *skb)
  3408. {
  3409. const struct tcp_sock *tp = tcp_sk(sk);
  3410. return ((s32)(tp->rx_opt.ts_recent - tp->rx_opt.rcv_tsval) > TCP_PAWS_WINDOW &&
  3411. get_seconds() < tp->rx_opt.ts_recent_stamp + TCP_PAWS_24DAYS &&
  3412. !tcp_disordered_ack(sk, skb));
  3413. }
  3414. /* Check segment sequence number for validity.
  3415. *
  3416. * Segment controls are considered valid, if the segment
  3417. * fits to the window after truncation to the window. Acceptability
  3418. * of data (and SYN, FIN, of course) is checked separately.
  3419. * See tcp_data_queue(), for example.
  3420. *
  3421. * Also, controls (RST is main one) are accepted using RCV.WUP instead
  3422. * of RCV.NXT. Peer still did not advance his SND.UNA when we
  3423. * delayed ACK, so that hisSND.UNA<=ourRCV.WUP.
  3424. * (borrowed from freebsd)
  3425. */
  3426. static inline int tcp_sequence(struct tcp_sock *tp, u32 seq, u32 end_seq)
  3427. {
  3428. return !before(end_seq, tp->rcv_wup) &&
  3429. !after(seq, tp->rcv_nxt + tcp_receive_window(tp));
  3430. }
  3431. /* When we get a reset we do this. */
  3432. static void tcp_reset(struct sock *sk)
  3433. {
  3434. /* We want the right error as BSD sees it (and indeed as we do). */
  3435. switch (sk->sk_state) {
  3436. case TCP_SYN_SENT:
  3437. sk->sk_err = ECONNREFUSED;
  3438. break;
  3439. case TCP_CLOSE_WAIT:
  3440. sk->sk_err = EPIPE;
  3441. break;
  3442. case TCP_CLOSE:
  3443. return;
  3444. default:
  3445. sk->sk_err = ECONNRESET;
  3446. }
  3447. if (!sock_flag(sk, SOCK_DEAD))
  3448. sk->sk_error_report(sk);
  3449. tcp_done(sk);
  3450. }
  3451. /*
  3452. * Process the FIN bit. This now behaves as it is supposed to work
  3453. * and the FIN takes effect when it is validly part of sequence
  3454. * space. Not before when we get holes.
  3455. *
  3456. * If we are ESTABLISHED, a received fin moves us to CLOSE-WAIT
  3457. * (and thence onto LAST-ACK and finally, CLOSE, we never enter
  3458. * TIME-WAIT)
  3459. *
  3460. * If we are in FINWAIT-1, a received FIN indicates simultaneous
  3461. * close and we go into CLOSING (and later onto TIME-WAIT)
  3462. *
  3463. * If we are in FINWAIT-2, a received FIN moves us to TIME-WAIT.
  3464. */
  3465. static void tcp_fin(struct sk_buff *skb, struct sock *sk, struct tcphdr *th)
  3466. {
  3467. struct tcp_sock *tp = tcp_sk(sk);
  3468. inet_csk_schedule_ack(sk);
  3469. sk->sk_shutdown |= RCV_SHUTDOWN;
  3470. sock_set_flag(sk, SOCK_DONE);
  3471. switch (sk->sk_state) {
  3472. case TCP_SYN_RECV:
  3473. case TCP_ESTABLISHED:
  3474. /* Move to CLOSE_WAIT */
  3475. tcp_set_state(sk, TCP_CLOSE_WAIT);
  3476. inet_csk(sk)->icsk_ack.pingpong = 1;
  3477. break;
  3478. case TCP_CLOSE_WAIT:
  3479. case TCP_CLOSING:
  3480. /* Received a retransmission of the FIN, do
  3481. * nothing.
  3482. */
  3483. break;
  3484. case TCP_LAST_ACK:
  3485. /* RFC793: Remain in the LAST-ACK state. */
  3486. break;
  3487. case TCP_FIN_WAIT1:
  3488. /* This case occurs when a simultaneous close
  3489. * happens, we must ack the received FIN and
  3490. * enter the CLOSING state.
  3491. */
  3492. tcp_send_ack(sk);
  3493. tcp_set_state(sk, TCP_CLOSING);
  3494. break;
  3495. case TCP_FIN_WAIT2:
  3496. /* Received a FIN -- send ACK and enter TIME_WAIT. */
  3497. tcp_send_ack(sk);
  3498. tcp_time_wait(sk, TCP_TIME_WAIT, 0);
  3499. break;
  3500. default:
  3501. /* Only TCP_LISTEN and TCP_CLOSE are left, in these
  3502. * cases we should never reach this piece of code.
  3503. */
  3504. printk(KERN_ERR "%s: Impossible, sk->sk_state=%d\n",
  3505. __func__, sk->sk_state);
  3506. break;
  3507. }
  3508. /* It _is_ possible, that we have something out-of-order _after_ FIN.
  3509. * Probably, we should reset in this case. For now drop them.
  3510. */
  3511. __skb_queue_purge(&tp->out_of_order_queue);
  3512. if (tcp_is_sack(tp))
  3513. tcp_sack_reset(&tp->rx_opt);
  3514. sk_mem_reclaim(sk);
  3515. if (!sock_flag(sk, SOCK_DEAD)) {
  3516. sk->sk_state_change(sk);
  3517. /* Do not send POLL_HUP for half duplex close. */
  3518. if (sk->sk_shutdown == SHUTDOWN_MASK ||
  3519. sk->sk_state == TCP_CLOSE)
  3520. sk_wake_async(sk, SOCK_WAKE_WAITD, POLL_HUP);
  3521. else
  3522. sk_wake_async(sk, SOCK_WAKE_WAITD, POLL_IN);
  3523. }
  3524. }
  3525. static inline int tcp_sack_extend(struct tcp_sack_block *sp, u32 seq,
  3526. u32 end_seq)
  3527. {
  3528. if (!after(seq, sp->end_seq) && !after(sp->start_seq, end_seq)) {
  3529. if (before(seq, sp->start_seq))
  3530. sp->start_seq = seq;
  3531. if (after(end_seq, sp->end_seq))
  3532. sp->end_seq = end_seq;
  3533. return 1;
  3534. }
  3535. return 0;
  3536. }
  3537. static void tcp_dsack_set(struct sock *sk, u32 seq, u32 end_seq)
  3538. {
  3539. struct tcp_sock *tp = tcp_sk(sk);
  3540. if (tcp_is_sack(tp) && sysctl_tcp_dsack) {
  3541. int mib_idx;
  3542. if (before(seq, tp->rcv_nxt))
  3543. mib_idx = LINUX_MIB_TCPDSACKOLDSENT;
  3544. else
  3545. mib_idx = LINUX_MIB_TCPDSACKOFOSENT;
  3546. NET_INC_STATS_BH(sock_net(sk), mib_idx);
  3547. tp->rx_opt.dsack = 1;
  3548. tp->duplicate_sack[0].start_seq = seq;
  3549. tp->duplicate_sack[0].end_seq = end_seq;
  3550. tp->rx_opt.eff_sacks = tp->rx_opt.num_sacks + 1;
  3551. }
  3552. }
  3553. static void tcp_dsack_extend(struct sock *sk, u32 seq, u32 end_seq)
  3554. {
  3555. struct tcp_sock *tp = tcp_sk(sk);
  3556. if (!tp->rx_opt.dsack)
  3557. tcp_dsack_set(sk, seq, end_seq);
  3558. else
  3559. tcp_sack_extend(tp->duplicate_sack, seq, end_seq);
  3560. }
  3561. static void tcp_send_dupack(struct sock *sk, struct sk_buff *skb)
  3562. {
  3563. struct tcp_sock *tp = tcp_sk(sk);
  3564. if (TCP_SKB_CB(skb)->end_seq != TCP_SKB_CB(skb)->seq &&
  3565. before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) {
  3566. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_DELAYEDACKLOST);
  3567. tcp_enter_quickack_mode(sk);
  3568. if (tcp_is_sack(tp) && sysctl_tcp_dsack) {
  3569. u32 end_seq = TCP_SKB_CB(skb)->end_seq;
  3570. if (after(TCP_SKB_CB(skb)->end_seq, tp->rcv_nxt))
  3571. end_seq = tp->rcv_nxt;
  3572. tcp_dsack_set(sk, TCP_SKB_CB(skb)->seq, end_seq);
  3573. }
  3574. }
  3575. tcp_send_ack(sk);
  3576. }
  3577. /* These routines update the SACK block as out-of-order packets arrive or
  3578. * in-order packets close up the sequence space.
  3579. */
  3580. static void tcp_sack_maybe_coalesce(struct tcp_sock *tp)
  3581. {
  3582. int this_sack;
  3583. struct tcp_sack_block *sp = &tp->selective_acks[0];
  3584. struct tcp_sack_block *swalk = sp + 1;
  3585. /* See if the recent change to the first SACK eats into
  3586. * or hits the sequence space of other SACK blocks, if so coalesce.
  3587. */
  3588. for (this_sack = 1; this_sack < tp->rx_opt.num_sacks;) {
  3589. if (tcp_sack_extend(sp, swalk->start_seq, swalk->end_seq)) {
  3590. int i;
  3591. /* Zap SWALK, by moving every further SACK up by one slot.
  3592. * Decrease num_sacks.
  3593. */
  3594. tp->rx_opt.num_sacks--;
  3595. tp->rx_opt.eff_sacks = tp->rx_opt.num_sacks +
  3596. tp->rx_opt.dsack;
  3597. for (i = this_sack; i < tp->rx_opt.num_sacks; i++)
  3598. sp[i] = sp[i + 1];
  3599. continue;
  3600. }
  3601. this_sack++, swalk++;
  3602. }
  3603. }
  3604. static inline void tcp_sack_swap(struct tcp_sack_block *sack1,
  3605. struct tcp_sack_block *sack2)
  3606. {
  3607. __u32 tmp;
  3608. tmp = sack1->start_seq;
  3609. sack1->start_seq = sack2->start_seq;
  3610. sack2->start_seq = tmp;
  3611. tmp = sack1->end_seq;
  3612. sack1->end_seq = sack2->end_seq;
  3613. sack2->end_seq = tmp;
  3614. }
  3615. static void tcp_sack_new_ofo_skb(struct sock *sk, u32 seq, u32 end_seq)
  3616. {
  3617. struct tcp_sock *tp = tcp_sk(sk);
  3618. struct tcp_sack_block *sp = &tp->selective_acks[0];
  3619. int cur_sacks = tp->rx_opt.num_sacks;
  3620. int this_sack;
  3621. if (!cur_sacks)
  3622. goto new_sack;
  3623. for (this_sack = 0; this_sack < cur_sacks; this_sack++, sp++) {
  3624. if (tcp_sack_extend(sp, seq, end_seq)) {
  3625. /* Rotate this_sack to the first one. */
  3626. for (; this_sack > 0; this_sack--, sp--)
  3627. tcp_sack_swap(sp, sp - 1);
  3628. if (cur_sacks > 1)
  3629. tcp_sack_maybe_coalesce(tp);
  3630. return;
  3631. }
  3632. }
  3633. /* Could not find an adjacent existing SACK, build a new one,
  3634. * put it at the front, and shift everyone else down. We
  3635. * always know there is at least one SACK present already here.
  3636. *
  3637. * If the sack array is full, forget about the last one.
  3638. */
  3639. if (this_sack >= TCP_NUM_SACKS) {
  3640. this_sack--;
  3641. tp->rx_opt.num_sacks--;
  3642. sp--;
  3643. }
  3644. for (; this_sack > 0; this_sack--, sp--)
  3645. *sp = *(sp - 1);
  3646. new_sack:
  3647. /* Build the new head SACK, and we're done. */
  3648. sp->start_seq = seq;
  3649. sp->end_seq = end_seq;
  3650. tp->rx_opt.num_sacks++;
  3651. tp->rx_opt.eff_sacks = tp->rx_opt.num_sacks + tp->rx_opt.dsack;
  3652. }
  3653. /* RCV.NXT advances, some SACKs should be eaten. */
  3654. static void tcp_sack_remove(struct tcp_sock *tp)
  3655. {
  3656. struct tcp_sack_block *sp = &tp->selective_acks[0];
  3657. int num_sacks = tp->rx_opt.num_sacks;
  3658. int this_sack;
  3659. /* Empty ofo queue, hence, all the SACKs are eaten. Clear. */
  3660. if (skb_queue_empty(&tp->out_of_order_queue)) {
  3661. tp->rx_opt.num_sacks = 0;
  3662. tp->rx_opt.eff_sacks = tp->rx_opt.dsack;
  3663. return;
  3664. }
  3665. for (this_sack = 0; this_sack < num_sacks;) {
  3666. /* Check if the start of the sack is covered by RCV.NXT. */
  3667. if (!before(tp->rcv_nxt, sp->start_seq)) {
  3668. int i;
  3669. /* RCV.NXT must cover all the block! */
  3670. WARN_ON(before(tp->rcv_nxt, sp->end_seq));
  3671. /* Zap this SACK, by moving forward any other SACKS. */
  3672. for (i=this_sack+1; i < num_sacks; i++)
  3673. tp->selective_acks[i-1] = tp->selective_acks[i];
  3674. num_sacks--;
  3675. continue;
  3676. }
  3677. this_sack++;
  3678. sp++;
  3679. }
  3680. if (num_sacks != tp->rx_opt.num_sacks) {
  3681. tp->rx_opt.num_sacks = num_sacks;
  3682. tp->rx_opt.eff_sacks = tp->rx_opt.num_sacks +
  3683. tp->rx_opt.dsack;
  3684. }
  3685. }
  3686. /* This one checks to see if we can put data from the
  3687. * out_of_order queue into the receive_queue.
  3688. */
  3689. static void tcp_ofo_queue(struct sock *sk)
  3690. {
  3691. struct tcp_sock *tp = tcp_sk(sk);
  3692. __u32 dsack_high = tp->rcv_nxt;
  3693. struct sk_buff *skb;
  3694. while ((skb = skb_peek(&tp->out_of_order_queue)) != NULL) {
  3695. if (after(TCP_SKB_CB(skb)->seq, tp->rcv_nxt))
  3696. break;
  3697. if (before(TCP_SKB_CB(skb)->seq, dsack_high)) {
  3698. __u32 dsack = dsack_high;
  3699. if (before(TCP_SKB_CB(skb)->end_seq, dsack_high))
  3700. dsack_high = TCP_SKB_CB(skb)->end_seq;
  3701. tcp_dsack_extend(sk, TCP_SKB_CB(skb)->seq, dsack);
  3702. }
  3703. if (!after(TCP_SKB_CB(skb)->end_seq, tp->rcv_nxt)) {
  3704. SOCK_DEBUG(sk, "ofo packet was already received \n");
  3705. __skb_unlink(skb, &tp->out_of_order_queue);
  3706. __kfree_skb(skb);
  3707. continue;
  3708. }
  3709. SOCK_DEBUG(sk, "ofo requeuing : rcv_next %X seq %X - %X\n",
  3710. tp->rcv_nxt, TCP_SKB_CB(skb)->seq,
  3711. TCP_SKB_CB(skb)->end_seq);
  3712. __skb_unlink(skb, &tp->out_of_order_queue);
  3713. __skb_queue_tail(&sk->sk_receive_queue, skb);
  3714. tp->rcv_nxt = TCP_SKB_CB(skb)->end_seq;
  3715. if (tcp_hdr(skb)->fin)
  3716. tcp_fin(skb, sk, tcp_hdr(skb));
  3717. }
  3718. }
  3719. static int tcp_prune_ofo_queue(struct sock *sk);
  3720. static int tcp_prune_queue(struct sock *sk);
  3721. static inline int tcp_try_rmem_schedule(struct sock *sk, unsigned int size)
  3722. {
  3723. if (atomic_read(&sk->sk_rmem_alloc) > sk->sk_rcvbuf ||
  3724. !sk_rmem_schedule(sk, size)) {
  3725. if (tcp_prune_queue(sk) < 0)
  3726. return -1;
  3727. if (!sk_rmem_schedule(sk, size)) {
  3728. if (!tcp_prune_ofo_queue(sk))
  3729. return -1;
  3730. if (!sk_rmem_schedule(sk, size))
  3731. return -1;
  3732. }
  3733. }
  3734. return 0;
  3735. }
  3736. static void tcp_data_queue(struct sock *sk, struct sk_buff *skb)
  3737. {
  3738. struct tcphdr *th = tcp_hdr(skb);
  3739. struct tcp_sock *tp = tcp_sk(sk);
  3740. int eaten = -1;
  3741. if (TCP_SKB_CB(skb)->seq == TCP_SKB_CB(skb)->end_seq)
  3742. goto drop;
  3743. __skb_pull(skb, th->doff * 4);
  3744. TCP_ECN_accept_cwr(tp, skb);
  3745. if (tp->rx_opt.dsack) {
  3746. tp->rx_opt.dsack = 0;
  3747. tp->rx_opt.eff_sacks = tp->rx_opt.num_sacks;
  3748. }
  3749. /* Queue data for delivery to the user.
  3750. * Packets in sequence go to the receive queue.
  3751. * Out of sequence packets to the out_of_order_queue.
  3752. */
  3753. if (TCP_SKB_CB(skb)->seq == tp->rcv_nxt) {
  3754. if (tcp_receive_window(tp) == 0)
  3755. goto out_of_window;
  3756. /* Ok. In sequence. In window. */
  3757. if (tp->ucopy.task == current &&
  3758. tp->copied_seq == tp->rcv_nxt && tp->ucopy.len &&
  3759. sock_owned_by_user(sk) && !tp->urg_data) {
  3760. int chunk = min_t(unsigned int, skb->len,
  3761. tp->ucopy.len);
  3762. __set_current_state(TASK_RUNNING);
  3763. local_bh_enable();
  3764. if (!skb_copy_datagram_iovec(skb, 0, tp->ucopy.iov, chunk)) {
  3765. tp->ucopy.len -= chunk;
  3766. tp->copied_seq += chunk;
  3767. eaten = (chunk == skb->len && !th->fin);
  3768. tcp_rcv_space_adjust(sk);
  3769. }
  3770. local_bh_disable();
  3771. }
  3772. if (eaten <= 0) {
  3773. queue_and_out:
  3774. if (eaten < 0 &&
  3775. tcp_try_rmem_schedule(sk, skb->truesize))
  3776. goto drop;
  3777. skb_set_owner_r(skb, sk);
  3778. __skb_queue_tail(&sk->sk_receive_queue, skb);
  3779. }
  3780. tp->rcv_nxt = TCP_SKB_CB(skb)->end_seq;
  3781. if (skb->len)
  3782. tcp_event_data_recv(sk, skb);
  3783. if (th->fin)
  3784. tcp_fin(skb, sk, th);
  3785. if (!skb_queue_empty(&tp->out_of_order_queue)) {
  3786. tcp_ofo_queue(sk);
  3787. /* RFC2581. 4.2. SHOULD send immediate ACK, when
  3788. * gap in queue is filled.
  3789. */
  3790. if (skb_queue_empty(&tp->out_of_order_queue))
  3791. inet_csk(sk)->icsk_ack.pingpong = 0;
  3792. }
  3793. if (tp->rx_opt.num_sacks)
  3794. tcp_sack_remove(tp);
  3795. tcp_fast_path_check(sk);
  3796. if (eaten > 0)
  3797. __kfree_skb(skb);
  3798. else if (!sock_flag(sk, SOCK_DEAD))
  3799. sk->sk_data_ready(sk, 0);
  3800. return;
  3801. }
  3802. if (!after(TCP_SKB_CB(skb)->end_seq, tp->rcv_nxt)) {
  3803. /* A retransmit, 2nd most common case. Force an immediate ack. */
  3804. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_DELAYEDACKLOST);
  3805. tcp_dsack_set(sk, TCP_SKB_CB(skb)->seq, TCP_SKB_CB(skb)->end_seq);
  3806. out_of_window:
  3807. tcp_enter_quickack_mode(sk);
  3808. inet_csk_schedule_ack(sk);
  3809. drop:
  3810. __kfree_skb(skb);
  3811. return;
  3812. }
  3813. /* Out of window. F.e. zero window probe. */
  3814. if (!before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt + tcp_receive_window(tp)))
  3815. goto out_of_window;
  3816. tcp_enter_quickack_mode(sk);
  3817. if (before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) {
  3818. /* Partial packet, seq < rcv_next < end_seq */
  3819. SOCK_DEBUG(sk, "partial packet: rcv_next %X seq %X - %X\n",
  3820. tp->rcv_nxt, TCP_SKB_CB(skb)->seq,
  3821. TCP_SKB_CB(skb)->end_seq);
  3822. tcp_dsack_set(sk, TCP_SKB_CB(skb)->seq, tp->rcv_nxt);
  3823. /* If window is closed, drop tail of packet. But after
  3824. * remembering D-SACK for its head made in previous line.
  3825. */
  3826. if (!tcp_receive_window(tp))
  3827. goto out_of_window;
  3828. goto queue_and_out;
  3829. }
  3830. TCP_ECN_check_ce(tp, skb);
  3831. if (tcp_try_rmem_schedule(sk, skb->truesize))
  3832. goto drop;
  3833. /* Disable header prediction. */
  3834. tp->pred_flags = 0;
  3835. inet_csk_schedule_ack(sk);
  3836. SOCK_DEBUG(sk, "out of order segment: rcv_next %X seq %X - %X\n",
  3837. tp->rcv_nxt, TCP_SKB_CB(skb)->seq, TCP_SKB_CB(skb)->end_seq);
  3838. skb_set_owner_r(skb, sk);
  3839. if (!skb_peek(&tp->out_of_order_queue)) {
  3840. /* Initial out of order segment, build 1 SACK. */
  3841. if (tcp_is_sack(tp)) {
  3842. tp->rx_opt.num_sacks = 1;
  3843. tp->rx_opt.dsack = 0;
  3844. tp->rx_opt.eff_sacks = 1;
  3845. tp->selective_acks[0].start_seq = TCP_SKB_CB(skb)->seq;
  3846. tp->selective_acks[0].end_seq =
  3847. TCP_SKB_CB(skb)->end_seq;
  3848. }
  3849. __skb_queue_head(&tp->out_of_order_queue, skb);
  3850. } else {
  3851. struct sk_buff *skb1 = tp->out_of_order_queue.prev;
  3852. u32 seq = TCP_SKB_CB(skb)->seq;
  3853. u32 end_seq = TCP_SKB_CB(skb)->end_seq;
  3854. if (seq == TCP_SKB_CB(skb1)->end_seq) {
  3855. __skb_queue_after(&tp->out_of_order_queue, skb1, skb);
  3856. if (!tp->rx_opt.num_sacks ||
  3857. tp->selective_acks[0].end_seq != seq)
  3858. goto add_sack;
  3859. /* Common case: data arrive in order after hole. */
  3860. tp->selective_acks[0].end_seq = end_seq;
  3861. return;
  3862. }
  3863. /* Find place to insert this segment. */
  3864. do {
  3865. if (!after(TCP_SKB_CB(skb1)->seq, seq))
  3866. break;
  3867. } while ((skb1 = skb1->prev) !=
  3868. (struct sk_buff *)&tp->out_of_order_queue);
  3869. /* Do skb overlap to previous one? */
  3870. if (skb1 != (struct sk_buff *)&tp->out_of_order_queue &&
  3871. before(seq, TCP_SKB_CB(skb1)->end_seq)) {
  3872. if (!after(end_seq, TCP_SKB_CB(skb1)->end_seq)) {
  3873. /* All the bits are present. Drop. */
  3874. __kfree_skb(skb);
  3875. tcp_dsack_set(sk, seq, end_seq);
  3876. goto add_sack;
  3877. }
  3878. if (after(seq, TCP_SKB_CB(skb1)->seq)) {
  3879. /* Partial overlap. */
  3880. tcp_dsack_set(sk, seq,
  3881. TCP_SKB_CB(skb1)->end_seq);
  3882. } else {
  3883. skb1 = skb1->prev;
  3884. }
  3885. }
  3886. __skb_queue_after(&tp->out_of_order_queue, skb1, skb);
  3887. /* And clean segments covered by new one as whole. */
  3888. while ((skb1 = skb->next) !=
  3889. (struct sk_buff *)&tp->out_of_order_queue &&
  3890. after(end_seq, TCP_SKB_CB(skb1)->seq)) {
  3891. if (before(end_seq, TCP_SKB_CB(skb1)->end_seq)) {
  3892. tcp_dsack_extend(sk, TCP_SKB_CB(skb1)->seq,
  3893. end_seq);
  3894. break;
  3895. }
  3896. __skb_unlink(skb1, &tp->out_of_order_queue);
  3897. tcp_dsack_extend(sk, TCP_SKB_CB(skb1)->seq,
  3898. TCP_SKB_CB(skb1)->end_seq);
  3899. __kfree_skb(skb1);
  3900. }
  3901. add_sack:
  3902. if (tcp_is_sack(tp))
  3903. tcp_sack_new_ofo_skb(sk, seq, end_seq);
  3904. }
  3905. }
  3906. static struct sk_buff *tcp_collapse_one(struct sock *sk, struct sk_buff *skb,
  3907. struct sk_buff_head *list)
  3908. {
  3909. struct sk_buff *next = skb->next;
  3910. __skb_unlink(skb, list);
  3911. __kfree_skb(skb);
  3912. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPRCVCOLLAPSED);
  3913. return next;
  3914. }
  3915. /* Collapse contiguous sequence of skbs head..tail with
  3916. * sequence numbers start..end.
  3917. * Segments with FIN/SYN are not collapsed (only because this
  3918. * simplifies code)
  3919. */
  3920. static void
  3921. tcp_collapse(struct sock *sk, struct sk_buff_head *list,
  3922. struct sk_buff *head, struct sk_buff *tail,
  3923. u32 start, u32 end)
  3924. {
  3925. struct sk_buff *skb;
  3926. /* First, check that queue is collapsible and find
  3927. * the point where collapsing can be useful. */
  3928. for (skb = head; skb != tail;) {
  3929. /* No new bits? It is possible on ofo queue. */
  3930. if (!before(start, TCP_SKB_CB(skb)->end_seq)) {
  3931. skb = tcp_collapse_one(sk, skb, list);
  3932. continue;
  3933. }
  3934. /* The first skb to collapse is:
  3935. * - not SYN/FIN and
  3936. * - bloated or contains data before "start" or
  3937. * overlaps to the next one.
  3938. */
  3939. if (!tcp_hdr(skb)->syn && !tcp_hdr(skb)->fin &&
  3940. (tcp_win_from_space(skb->truesize) > skb->len ||
  3941. before(TCP_SKB_CB(skb)->seq, start) ||
  3942. (skb->next != tail &&
  3943. TCP_SKB_CB(skb)->end_seq != TCP_SKB_CB(skb->next)->seq)))
  3944. break;
  3945. /* Decided to skip this, advance start seq. */
  3946. start = TCP_SKB_CB(skb)->end_seq;
  3947. skb = skb->next;
  3948. }
  3949. if (skb == tail || tcp_hdr(skb)->syn || tcp_hdr(skb)->fin)
  3950. return;
  3951. while (before(start, end)) {
  3952. struct sk_buff *nskb;
  3953. unsigned int header = skb_headroom(skb);
  3954. int copy = SKB_MAX_ORDER(header, 0);
  3955. /* Too big header? This can happen with IPv6. */
  3956. if (copy < 0)
  3957. return;
  3958. if (end - start < copy)
  3959. copy = end - start;
  3960. nskb = alloc_skb(copy + header, GFP_ATOMIC);
  3961. if (!nskb)
  3962. return;
  3963. skb_set_mac_header(nskb, skb_mac_header(skb) - skb->head);
  3964. skb_set_network_header(nskb, (skb_network_header(skb) -
  3965. skb->head));
  3966. skb_set_transport_header(nskb, (skb_transport_header(skb) -
  3967. skb->head));
  3968. skb_reserve(nskb, header);
  3969. memcpy(nskb->head, skb->head, header);
  3970. memcpy(nskb->cb, skb->cb, sizeof(skb->cb));
  3971. TCP_SKB_CB(nskb)->seq = TCP_SKB_CB(nskb)->end_seq = start;
  3972. __skb_queue_before(list, skb, nskb);
  3973. skb_set_owner_r(nskb, sk);
  3974. /* Copy data, releasing collapsed skbs. */
  3975. while (copy > 0) {
  3976. int offset = start - TCP_SKB_CB(skb)->seq;
  3977. int size = TCP_SKB_CB(skb)->end_seq - start;
  3978. BUG_ON(offset < 0);
  3979. if (size > 0) {
  3980. size = min(copy, size);
  3981. if (skb_copy_bits(skb, offset, skb_put(nskb, size), size))
  3982. BUG();
  3983. TCP_SKB_CB(nskb)->end_seq += size;
  3984. copy -= size;
  3985. start += size;
  3986. }
  3987. if (!before(start, TCP_SKB_CB(skb)->end_seq)) {
  3988. skb = tcp_collapse_one(sk, skb, list);
  3989. if (skb == tail ||
  3990. tcp_hdr(skb)->syn ||
  3991. tcp_hdr(skb)->fin)
  3992. return;
  3993. }
  3994. }
  3995. }
  3996. }
  3997. /* Collapse ofo queue. Algorithm: select contiguous sequence of skbs
  3998. * and tcp_collapse() them until all the queue is collapsed.
  3999. */
  4000. static void tcp_collapse_ofo_queue(struct sock *sk)
  4001. {
  4002. struct tcp_sock *tp = tcp_sk(sk);
  4003. struct sk_buff *skb = skb_peek(&tp->out_of_order_queue);
  4004. struct sk_buff *head;
  4005. u32 start, end;
  4006. if (skb == NULL)
  4007. return;
  4008. start = TCP_SKB_CB(skb)->seq;
  4009. end = TCP_SKB_CB(skb)->end_seq;
  4010. head = skb;
  4011. for (;;) {
  4012. skb = skb->next;
  4013. /* Segment is terminated when we see gap or when
  4014. * we are at the end of all the queue. */
  4015. if (skb == (struct sk_buff *)&tp->out_of_order_queue ||
  4016. after(TCP_SKB_CB(skb)->seq, end) ||
  4017. before(TCP_SKB_CB(skb)->end_seq, start)) {
  4018. tcp_collapse(sk, &tp->out_of_order_queue,
  4019. head, skb, start, end);
  4020. head = skb;
  4021. if (skb == (struct sk_buff *)&tp->out_of_order_queue)
  4022. break;
  4023. /* Start new segment */
  4024. start = TCP_SKB_CB(skb)->seq;
  4025. end = TCP_SKB_CB(skb)->end_seq;
  4026. } else {
  4027. if (before(TCP_SKB_CB(skb)->seq, start))
  4028. start = TCP_SKB_CB(skb)->seq;
  4029. if (after(TCP_SKB_CB(skb)->end_seq, end))
  4030. end = TCP_SKB_CB(skb)->end_seq;
  4031. }
  4032. }
  4033. }
  4034. /*
  4035. * Purge the out-of-order queue.
  4036. * Return true if queue was pruned.
  4037. */
  4038. static int tcp_prune_ofo_queue(struct sock *sk)
  4039. {
  4040. struct tcp_sock *tp = tcp_sk(sk);
  4041. int res = 0;
  4042. if (!skb_queue_empty(&tp->out_of_order_queue)) {
  4043. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_OFOPRUNED);
  4044. __skb_queue_purge(&tp->out_of_order_queue);
  4045. /* Reset SACK state. A conforming SACK implementation will
  4046. * do the same at a timeout based retransmit. When a connection
  4047. * is in a sad state like this, we care only about integrity
  4048. * of the connection not performance.
  4049. */
  4050. if (tp->rx_opt.sack_ok)
  4051. tcp_sack_reset(&tp->rx_opt);
  4052. sk_mem_reclaim(sk);
  4053. res = 1;
  4054. }
  4055. return res;
  4056. }
  4057. /* Reduce allocated memory if we can, trying to get
  4058. * the socket within its memory limits again.
  4059. *
  4060. * Return less than zero if we should start dropping frames
  4061. * until the socket owning process reads some of the data
  4062. * to stabilize the situation.
  4063. */
  4064. static int tcp_prune_queue(struct sock *sk)
  4065. {
  4066. struct tcp_sock *tp = tcp_sk(sk);
  4067. SOCK_DEBUG(sk, "prune_queue: c=%x\n", tp->copied_seq);
  4068. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_PRUNECALLED);
  4069. if (atomic_read(&sk->sk_rmem_alloc) >= sk->sk_rcvbuf)
  4070. tcp_clamp_window(sk);
  4071. else if (tcp_memory_pressure)
  4072. tp->rcv_ssthresh = min(tp->rcv_ssthresh, 4U * tp->advmss);
  4073. tcp_collapse_ofo_queue(sk);
  4074. tcp_collapse(sk, &sk->sk_receive_queue,
  4075. sk->sk_receive_queue.next,
  4076. (struct sk_buff *)&sk->sk_receive_queue,
  4077. tp->copied_seq, tp->rcv_nxt);
  4078. sk_mem_reclaim(sk);
  4079. if (atomic_read(&sk->sk_rmem_alloc) <= sk->sk_rcvbuf)
  4080. return 0;
  4081. /* Collapsing did not help, destructive actions follow.
  4082. * This must not ever occur. */
  4083. tcp_prune_ofo_queue(sk);
  4084. if (atomic_read(&sk->sk_rmem_alloc) <= sk->sk_rcvbuf)
  4085. return 0;
  4086. /* If we are really being abused, tell the caller to silently
  4087. * drop receive data on the floor. It will get retransmitted
  4088. * and hopefully then we'll have sufficient space.
  4089. */
  4090. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_RCVPRUNED);
  4091. /* Massive buffer overcommit. */
  4092. tp->pred_flags = 0;
  4093. return -1;
  4094. }
  4095. /* RFC2861, slow part. Adjust cwnd, after it was not full during one rto.
  4096. * As additional protections, we do not touch cwnd in retransmission phases,
  4097. * and if application hit its sndbuf limit recently.
  4098. */
  4099. void tcp_cwnd_application_limited(struct sock *sk)
  4100. {
  4101. struct tcp_sock *tp = tcp_sk(sk);
  4102. if (inet_csk(sk)->icsk_ca_state == TCP_CA_Open &&
  4103. sk->sk_socket && !test_bit(SOCK_NOSPACE, &sk->sk_socket->flags)) {
  4104. /* Limited by application or receiver window. */
  4105. u32 init_win = tcp_init_cwnd(tp, __sk_dst_get(sk));
  4106. u32 win_used = max(tp->snd_cwnd_used, init_win);
  4107. if (win_used < tp->snd_cwnd) {
  4108. tp->snd_ssthresh = tcp_current_ssthresh(sk);
  4109. tp->snd_cwnd = (tp->snd_cwnd + win_used) >> 1;
  4110. }
  4111. tp->snd_cwnd_used = 0;
  4112. }
  4113. tp->snd_cwnd_stamp = tcp_time_stamp;
  4114. }
  4115. static int tcp_should_expand_sndbuf(struct sock *sk)
  4116. {
  4117. struct tcp_sock *tp = tcp_sk(sk);
  4118. /* If the user specified a specific send buffer setting, do
  4119. * not modify it.
  4120. */
  4121. if (sk->sk_userlocks & SOCK_SNDBUF_LOCK)
  4122. return 0;
  4123. /* If we are under global TCP memory pressure, do not expand. */
  4124. if (tcp_memory_pressure)
  4125. return 0;
  4126. /* If we are under soft global TCP memory pressure, do not expand. */
  4127. if (atomic_read(&tcp_memory_allocated) >= sysctl_tcp_mem[0])
  4128. return 0;
  4129. /* If we filled the congestion window, do not expand. */
  4130. if (tp->packets_out >= tp->snd_cwnd)
  4131. return 0;
  4132. return 1;
  4133. }
  4134. /* When incoming ACK allowed to free some skb from write_queue,
  4135. * we remember this event in flag SOCK_QUEUE_SHRUNK and wake up socket
  4136. * on the exit from tcp input handler.
  4137. *
  4138. * PROBLEM: sndbuf expansion does not work well with largesend.
  4139. */
  4140. static void tcp_new_space(struct sock *sk)
  4141. {
  4142. struct tcp_sock *tp = tcp_sk(sk);
  4143. if (tcp_should_expand_sndbuf(sk)) {
  4144. int sndmem = max_t(u32, tp->rx_opt.mss_clamp, tp->mss_cache) +
  4145. MAX_TCP_HEADER + 16 + sizeof(struct sk_buff);
  4146. int demanded = max_t(unsigned int, tp->snd_cwnd,
  4147. tp->reordering + 1);
  4148. sndmem *= 2 * demanded;
  4149. if (sndmem > sk->sk_sndbuf)
  4150. sk->sk_sndbuf = min(sndmem, sysctl_tcp_wmem[2]);
  4151. tp->snd_cwnd_stamp = tcp_time_stamp;
  4152. }
  4153. sk->sk_write_space(sk);
  4154. }
  4155. static void tcp_check_space(struct sock *sk)
  4156. {
  4157. if (sock_flag(sk, SOCK_QUEUE_SHRUNK)) {
  4158. sock_reset_flag(sk, SOCK_QUEUE_SHRUNK);
  4159. if (sk->sk_socket &&
  4160. test_bit(SOCK_NOSPACE, &sk->sk_socket->flags))
  4161. tcp_new_space(sk);
  4162. }
  4163. }
  4164. static inline void tcp_data_snd_check(struct sock *sk)
  4165. {
  4166. tcp_push_pending_frames(sk);
  4167. tcp_check_space(sk);
  4168. }
  4169. /*
  4170. * Check if sending an ack is needed.
  4171. */
  4172. static void __tcp_ack_snd_check(struct sock *sk, int ofo_possible)
  4173. {
  4174. struct tcp_sock *tp = tcp_sk(sk);
  4175. /* More than one full frame received... */
  4176. if (((tp->rcv_nxt - tp->rcv_wup) > inet_csk(sk)->icsk_ack.rcv_mss
  4177. /* ... and right edge of window advances far enough.
  4178. * (tcp_recvmsg() will send ACK otherwise). Or...
  4179. */
  4180. && __tcp_select_window(sk) >= tp->rcv_wnd) ||
  4181. /* We ACK each frame or... */
  4182. tcp_in_quickack_mode(sk) ||
  4183. /* We have out of order data. */
  4184. (ofo_possible && skb_peek(&tp->out_of_order_queue))) {
  4185. /* Then ack it now */
  4186. tcp_send_ack(sk);
  4187. } else {
  4188. /* Else, send delayed ack. */
  4189. tcp_send_delayed_ack(sk);
  4190. }
  4191. }
  4192. static inline void tcp_ack_snd_check(struct sock *sk)
  4193. {
  4194. if (!inet_csk_ack_scheduled(sk)) {
  4195. /* We sent a data segment already. */
  4196. return;
  4197. }
  4198. __tcp_ack_snd_check(sk, 1);
  4199. }
  4200. /*
  4201. * This routine is only called when we have urgent data
  4202. * signaled. Its the 'slow' part of tcp_urg. It could be
  4203. * moved inline now as tcp_urg is only called from one
  4204. * place. We handle URGent data wrong. We have to - as
  4205. * BSD still doesn't use the correction from RFC961.
  4206. * For 1003.1g we should support a new option TCP_STDURG to permit
  4207. * either form (or just set the sysctl tcp_stdurg).
  4208. */
  4209. static void tcp_check_urg(struct sock *sk, struct tcphdr *th)
  4210. {
  4211. struct tcp_sock *tp = tcp_sk(sk);
  4212. u32 ptr = ntohs(th->urg_ptr);
  4213. if (ptr && !sysctl_tcp_stdurg)
  4214. ptr--;
  4215. ptr += ntohl(th->seq);
  4216. /* Ignore urgent data that we've already seen and read. */
  4217. if (after(tp->copied_seq, ptr))
  4218. return;
  4219. /* Do not replay urg ptr.
  4220. *
  4221. * NOTE: interesting situation not covered by specs.
  4222. * Misbehaving sender may send urg ptr, pointing to segment,
  4223. * which we already have in ofo queue. We are not able to fetch
  4224. * such data and will stay in TCP_URG_NOTYET until will be eaten
  4225. * by recvmsg(). Seems, we are not obliged to handle such wicked
  4226. * situations. But it is worth to think about possibility of some
  4227. * DoSes using some hypothetical application level deadlock.
  4228. */
  4229. if (before(ptr, tp->rcv_nxt))
  4230. return;
  4231. /* Do we already have a newer (or duplicate) urgent pointer? */
  4232. if (tp->urg_data && !after(ptr, tp->urg_seq))
  4233. return;
  4234. /* Tell the world about our new urgent pointer. */
  4235. sk_send_sigurg(sk);
  4236. /* We may be adding urgent data when the last byte read was
  4237. * urgent. To do this requires some care. We cannot just ignore
  4238. * tp->copied_seq since we would read the last urgent byte again
  4239. * as data, nor can we alter copied_seq until this data arrives
  4240. * or we break the semantics of SIOCATMARK (and thus sockatmark())
  4241. *
  4242. * NOTE. Double Dutch. Rendering to plain English: author of comment
  4243. * above did something sort of send("A", MSG_OOB); send("B", MSG_OOB);
  4244. * and expect that both A and B disappear from stream. This is _wrong_.
  4245. * Though this happens in BSD with high probability, this is occasional.
  4246. * Any application relying on this is buggy. Note also, that fix "works"
  4247. * only in this artificial test. Insert some normal data between A and B and we will
  4248. * decline of BSD again. Verdict: it is better to remove to trap
  4249. * buggy users.
  4250. */
  4251. if (tp->urg_seq == tp->copied_seq && tp->urg_data &&
  4252. !sock_flag(sk, SOCK_URGINLINE) && tp->copied_seq != tp->rcv_nxt) {
  4253. struct sk_buff *skb = skb_peek(&sk->sk_receive_queue);
  4254. tp->copied_seq++;
  4255. if (skb && !before(tp->copied_seq, TCP_SKB_CB(skb)->end_seq)) {
  4256. __skb_unlink(skb, &sk->sk_receive_queue);
  4257. __kfree_skb(skb);
  4258. }
  4259. }
  4260. tp->urg_data = TCP_URG_NOTYET;
  4261. tp->urg_seq = ptr;
  4262. /* Disable header prediction. */
  4263. tp->pred_flags = 0;
  4264. }
  4265. /* This is the 'fast' part of urgent handling. */
  4266. static void tcp_urg(struct sock *sk, struct sk_buff *skb, struct tcphdr *th)
  4267. {
  4268. struct tcp_sock *tp = tcp_sk(sk);
  4269. /* Check if we get a new urgent pointer - normally not. */
  4270. if (th->urg)
  4271. tcp_check_urg(sk, th);
  4272. /* Do we wait for any urgent data? - normally not... */
  4273. if (tp->urg_data == TCP_URG_NOTYET) {
  4274. u32 ptr = tp->urg_seq - ntohl(th->seq) + (th->doff * 4) -
  4275. th->syn;
  4276. /* Is the urgent pointer pointing into this packet? */
  4277. if (ptr < skb->len) {
  4278. u8 tmp;
  4279. if (skb_copy_bits(skb, ptr, &tmp, 1))
  4280. BUG();
  4281. tp->urg_data = TCP_URG_VALID | tmp;
  4282. if (!sock_flag(sk, SOCK_DEAD))
  4283. sk->sk_data_ready(sk, 0);
  4284. }
  4285. }
  4286. }
  4287. static int tcp_copy_to_iovec(struct sock *sk, struct sk_buff *skb, int hlen)
  4288. {
  4289. struct tcp_sock *tp = tcp_sk(sk);
  4290. int chunk = skb->len - hlen;
  4291. int err;
  4292. local_bh_enable();
  4293. if (skb_csum_unnecessary(skb))
  4294. err = skb_copy_datagram_iovec(skb, hlen, tp->ucopy.iov, chunk);
  4295. else
  4296. err = skb_copy_and_csum_datagram_iovec(skb, hlen,
  4297. tp->ucopy.iov);
  4298. if (!err) {
  4299. tp->ucopy.len -= chunk;
  4300. tp->copied_seq += chunk;
  4301. tcp_rcv_space_adjust(sk);
  4302. }
  4303. local_bh_disable();
  4304. return err;
  4305. }
  4306. static __sum16 __tcp_checksum_complete_user(struct sock *sk,
  4307. struct sk_buff *skb)
  4308. {
  4309. __sum16 result;
  4310. if (sock_owned_by_user(sk)) {
  4311. local_bh_enable();
  4312. result = __tcp_checksum_complete(skb);
  4313. local_bh_disable();
  4314. } else {
  4315. result = __tcp_checksum_complete(skb);
  4316. }
  4317. return result;
  4318. }
  4319. static inline int tcp_checksum_complete_user(struct sock *sk,
  4320. struct sk_buff *skb)
  4321. {
  4322. return !skb_csum_unnecessary(skb) &&
  4323. __tcp_checksum_complete_user(sk, skb);
  4324. }
  4325. #ifdef CONFIG_NET_DMA
  4326. static int tcp_dma_try_early_copy(struct sock *sk, struct sk_buff *skb,
  4327. int hlen)
  4328. {
  4329. struct tcp_sock *tp = tcp_sk(sk);
  4330. int chunk = skb->len - hlen;
  4331. int dma_cookie;
  4332. int copied_early = 0;
  4333. if (tp->ucopy.wakeup)
  4334. return 0;
  4335. if (!tp->ucopy.dma_chan && tp->ucopy.pinned_list)
  4336. tp->ucopy.dma_chan = get_softnet_dma();
  4337. if (tp->ucopy.dma_chan && skb_csum_unnecessary(skb)) {
  4338. dma_cookie = dma_skb_copy_datagram_iovec(tp->ucopy.dma_chan,
  4339. skb, hlen,
  4340. tp->ucopy.iov, chunk,
  4341. tp->ucopy.pinned_list);
  4342. if (dma_cookie < 0)
  4343. goto out;
  4344. tp->ucopy.dma_cookie = dma_cookie;
  4345. copied_early = 1;
  4346. tp->ucopy.len -= chunk;
  4347. tp->copied_seq += chunk;
  4348. tcp_rcv_space_adjust(sk);
  4349. if ((tp->ucopy.len == 0) ||
  4350. (tcp_flag_word(tcp_hdr(skb)) & TCP_FLAG_PSH) ||
  4351. (atomic_read(&sk->sk_rmem_alloc) > (sk->sk_rcvbuf >> 1))) {
  4352. tp->ucopy.wakeup = 1;
  4353. sk->sk_data_ready(sk, 0);
  4354. }
  4355. } else if (chunk > 0) {
  4356. tp->ucopy.wakeup = 1;
  4357. sk->sk_data_ready(sk, 0);
  4358. }
  4359. out:
  4360. return copied_early;
  4361. }
  4362. #endif /* CONFIG_NET_DMA */
  4363. /* Does PAWS and seqno based validation of an incoming segment, flags will
  4364. * play significant role here.
  4365. */
  4366. static int tcp_validate_incoming(struct sock *sk, struct sk_buff *skb,
  4367. struct tcphdr *th, int syn_inerr)
  4368. {
  4369. struct tcp_sock *tp = tcp_sk(sk);
  4370. /* RFC1323: H1. Apply PAWS check first. */
  4371. if (tcp_fast_parse_options(skb, th, tp) && tp->rx_opt.saw_tstamp &&
  4372. tcp_paws_discard(sk, skb)) {
  4373. if (!th->rst) {
  4374. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_PAWSESTABREJECTED);
  4375. tcp_send_dupack(sk, skb);
  4376. goto discard;
  4377. }
  4378. /* Reset is accepted even if it did not pass PAWS. */
  4379. }
  4380. /* Step 1: check sequence number */
  4381. if (!tcp_sequence(tp, TCP_SKB_CB(skb)->seq, TCP_SKB_CB(skb)->end_seq)) {
  4382. /* RFC793, page 37: "In all states except SYN-SENT, all reset
  4383. * (RST) segments are validated by checking their SEQ-fields."
  4384. * And page 69: "If an incoming segment is not acceptable,
  4385. * an acknowledgment should be sent in reply (unless the RST
  4386. * bit is set, if so drop the segment and return)".
  4387. */
  4388. if (!th->rst)
  4389. tcp_send_dupack(sk, skb);
  4390. goto discard;
  4391. }
  4392. /* Step 2: check RST bit */
  4393. if (th->rst) {
  4394. tcp_reset(sk);
  4395. goto discard;
  4396. }
  4397. /* ts_recent update must be made after we are sure that the packet
  4398. * is in window.
  4399. */
  4400. tcp_replace_ts_recent(tp, TCP_SKB_CB(skb)->seq);
  4401. /* step 3: check security and precedence [ignored] */
  4402. /* step 4: Check for a SYN in window. */
  4403. if (th->syn && !before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) {
  4404. if (syn_inerr)
  4405. TCP_INC_STATS_BH(sock_net(sk), TCP_MIB_INERRS);
  4406. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPABORTONSYN);
  4407. tcp_reset(sk);
  4408. return -1;
  4409. }
  4410. return 1;
  4411. discard:
  4412. __kfree_skb(skb);
  4413. return 0;
  4414. }
  4415. /*
  4416. * TCP receive function for the ESTABLISHED state.
  4417. *
  4418. * It is split into a fast path and a slow path. The fast path is
  4419. * disabled when:
  4420. * - A zero window was announced from us - zero window probing
  4421. * is only handled properly in the slow path.
  4422. * - Out of order segments arrived.
  4423. * - Urgent data is expected.
  4424. * - There is no buffer space left
  4425. * - Unexpected TCP flags/window values/header lengths are received
  4426. * (detected by checking the TCP header against pred_flags)
  4427. * - Data is sent in both directions. Fast path only supports pure senders
  4428. * or pure receivers (this means either the sequence number or the ack
  4429. * value must stay constant)
  4430. * - Unexpected TCP option.
  4431. *
  4432. * When these conditions are not satisfied it drops into a standard
  4433. * receive procedure patterned after RFC793 to handle all cases.
  4434. * The first three cases are guaranteed by proper pred_flags setting,
  4435. * the rest is checked inline. Fast processing is turned on in
  4436. * tcp_data_queue when everything is OK.
  4437. */
  4438. int tcp_rcv_established(struct sock *sk, struct sk_buff *skb,
  4439. struct tcphdr *th, unsigned len)
  4440. {
  4441. struct tcp_sock *tp = tcp_sk(sk);
  4442. int res;
  4443. /*
  4444. * Header prediction.
  4445. * The code loosely follows the one in the famous
  4446. * "30 instruction TCP receive" Van Jacobson mail.
  4447. *
  4448. * Van's trick is to deposit buffers into socket queue
  4449. * on a device interrupt, to call tcp_recv function
  4450. * on the receive process context and checksum and copy
  4451. * the buffer to user space. smart...
  4452. *
  4453. * Our current scheme is not silly either but we take the
  4454. * extra cost of the net_bh soft interrupt processing...
  4455. * We do checksum and copy also but from device to kernel.
  4456. */
  4457. tp->rx_opt.saw_tstamp = 0;
  4458. /* pred_flags is 0xS?10 << 16 + snd_wnd
  4459. * if header_prediction is to be made
  4460. * 'S' will always be tp->tcp_header_len >> 2
  4461. * '?' will be 0 for the fast path, otherwise pred_flags is 0 to
  4462. * turn it off (when there are holes in the receive
  4463. * space for instance)
  4464. * PSH flag is ignored.
  4465. */
  4466. if ((tcp_flag_word(th) & TCP_HP_BITS) == tp->pred_flags &&
  4467. TCP_SKB_CB(skb)->seq == tp->rcv_nxt) {
  4468. int tcp_header_len = tp->tcp_header_len;
  4469. /* Timestamp header prediction: tcp_header_len
  4470. * is automatically equal to th->doff*4 due to pred_flags
  4471. * match.
  4472. */
  4473. /* Check timestamp */
  4474. if (tcp_header_len == sizeof(struct tcphdr) + TCPOLEN_TSTAMP_ALIGNED) {
  4475. /* No? Slow path! */
  4476. if (!tcp_parse_aligned_timestamp(tp, th))
  4477. goto slow_path;
  4478. /* If PAWS failed, check it more carefully in slow path */
  4479. if ((s32)(tp->rx_opt.rcv_tsval - tp->rx_opt.ts_recent) < 0)
  4480. goto slow_path;
  4481. /* DO NOT update ts_recent here, if checksum fails
  4482. * and timestamp was corrupted part, it will result
  4483. * in a hung connection since we will drop all
  4484. * future packets due to the PAWS test.
  4485. */
  4486. }
  4487. if (len <= tcp_header_len) {
  4488. /* Bulk data transfer: sender */
  4489. if (len == tcp_header_len) {
  4490. /* Predicted packet is in window by definition.
  4491. * seq == rcv_nxt and rcv_wup <= rcv_nxt.
  4492. * Hence, check seq<=rcv_wup reduces to:
  4493. */
  4494. if (tcp_header_len ==
  4495. (sizeof(struct tcphdr) + TCPOLEN_TSTAMP_ALIGNED) &&
  4496. tp->rcv_nxt == tp->rcv_wup)
  4497. tcp_store_ts_recent(tp);
  4498. /* We know that such packets are checksummed
  4499. * on entry.
  4500. */
  4501. tcp_ack(sk, skb, 0);
  4502. __kfree_skb(skb);
  4503. tcp_data_snd_check(sk);
  4504. return 0;
  4505. } else { /* Header too small */
  4506. TCP_INC_STATS_BH(sock_net(sk), TCP_MIB_INERRS);
  4507. goto discard;
  4508. }
  4509. } else {
  4510. int eaten = 0;
  4511. int copied_early = 0;
  4512. if (tp->copied_seq == tp->rcv_nxt &&
  4513. len - tcp_header_len <= tp->ucopy.len) {
  4514. #ifdef CONFIG_NET_DMA
  4515. if (tcp_dma_try_early_copy(sk, skb, tcp_header_len)) {
  4516. copied_early = 1;
  4517. eaten = 1;
  4518. }
  4519. #endif
  4520. if (tp->ucopy.task == current &&
  4521. sock_owned_by_user(sk) && !copied_early) {
  4522. __set_current_state(TASK_RUNNING);
  4523. if (!tcp_copy_to_iovec(sk, skb, tcp_header_len))
  4524. eaten = 1;
  4525. }
  4526. if (eaten) {
  4527. /* Predicted packet is in window by definition.
  4528. * seq == rcv_nxt and rcv_wup <= rcv_nxt.
  4529. * Hence, check seq<=rcv_wup reduces to:
  4530. */
  4531. if (tcp_header_len ==
  4532. (sizeof(struct tcphdr) +
  4533. TCPOLEN_TSTAMP_ALIGNED) &&
  4534. tp->rcv_nxt == tp->rcv_wup)
  4535. tcp_store_ts_recent(tp);
  4536. tcp_rcv_rtt_measure_ts(sk, skb);
  4537. __skb_pull(skb, tcp_header_len);
  4538. tp->rcv_nxt = TCP_SKB_CB(skb)->end_seq;
  4539. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPHPHITSTOUSER);
  4540. }
  4541. if (copied_early)
  4542. tcp_cleanup_rbuf(sk, skb->len);
  4543. }
  4544. if (!eaten) {
  4545. if (tcp_checksum_complete_user(sk, skb))
  4546. goto csum_error;
  4547. /* Predicted packet is in window by definition.
  4548. * seq == rcv_nxt and rcv_wup <= rcv_nxt.
  4549. * Hence, check seq<=rcv_wup reduces to:
  4550. */
  4551. if (tcp_header_len ==
  4552. (sizeof(struct tcphdr) + TCPOLEN_TSTAMP_ALIGNED) &&
  4553. tp->rcv_nxt == tp->rcv_wup)
  4554. tcp_store_ts_recent(tp);
  4555. tcp_rcv_rtt_measure_ts(sk, skb);
  4556. if ((int)skb->truesize > sk->sk_forward_alloc)
  4557. goto step5;
  4558. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPHPHITS);
  4559. /* Bulk data transfer: receiver */
  4560. __skb_pull(skb, tcp_header_len);
  4561. __skb_queue_tail(&sk->sk_receive_queue, skb);
  4562. skb_set_owner_r(skb, sk);
  4563. tp->rcv_nxt = TCP_SKB_CB(skb)->end_seq;
  4564. }
  4565. tcp_event_data_recv(sk, skb);
  4566. if (TCP_SKB_CB(skb)->ack_seq != tp->snd_una) {
  4567. /* Well, only one small jumplet in fast path... */
  4568. tcp_ack(sk, skb, FLAG_DATA);
  4569. tcp_data_snd_check(sk);
  4570. if (!inet_csk_ack_scheduled(sk))
  4571. goto no_ack;
  4572. }
  4573. if (!copied_early || tp->rcv_nxt != tp->rcv_wup)
  4574. __tcp_ack_snd_check(sk, 0);
  4575. no_ack:
  4576. #ifdef CONFIG_NET_DMA
  4577. if (copied_early)
  4578. __skb_queue_tail(&sk->sk_async_wait_queue, skb);
  4579. else
  4580. #endif
  4581. if (eaten)
  4582. __kfree_skb(skb);
  4583. else
  4584. sk->sk_data_ready(sk, 0);
  4585. return 0;
  4586. }
  4587. }
  4588. slow_path:
  4589. if (len < (th->doff << 2) || tcp_checksum_complete_user(sk, skb))
  4590. goto csum_error;
  4591. /*
  4592. * Standard slow path.
  4593. */
  4594. res = tcp_validate_incoming(sk, skb, th, 1);
  4595. if (res <= 0)
  4596. return -res;
  4597. step5:
  4598. if (th->ack)
  4599. tcp_ack(sk, skb, FLAG_SLOWPATH);
  4600. tcp_rcv_rtt_measure_ts(sk, skb);
  4601. /* Process urgent data. */
  4602. tcp_urg(sk, skb, th);
  4603. /* step 7: process the segment text */
  4604. tcp_data_queue(sk, skb);
  4605. tcp_data_snd_check(sk);
  4606. tcp_ack_snd_check(sk);
  4607. return 0;
  4608. csum_error:
  4609. TCP_INC_STATS_BH(sock_net(sk), TCP_MIB_INERRS);
  4610. discard:
  4611. __kfree_skb(skb);
  4612. return 0;
  4613. }
  4614. static int tcp_rcv_synsent_state_process(struct sock *sk, struct sk_buff *skb,
  4615. struct tcphdr *th, unsigned len)
  4616. {
  4617. struct tcp_sock *tp = tcp_sk(sk);
  4618. struct inet_connection_sock *icsk = inet_csk(sk);
  4619. int saved_clamp = tp->rx_opt.mss_clamp;
  4620. tcp_parse_options(skb, &tp->rx_opt, 0);
  4621. if (th->ack) {
  4622. /* rfc793:
  4623. * "If the state is SYN-SENT then
  4624. * first check the ACK bit
  4625. * If the ACK bit is set
  4626. * If SEG.ACK =< ISS, or SEG.ACK > SND.NXT, send
  4627. * a reset (unless the RST bit is set, if so drop
  4628. * the segment and return)"
  4629. *
  4630. * We do not send data with SYN, so that RFC-correct
  4631. * test reduces to:
  4632. */
  4633. if (TCP_SKB_CB(skb)->ack_seq != tp->snd_nxt)
  4634. goto reset_and_undo;
  4635. if (tp->rx_opt.saw_tstamp && tp->rx_opt.rcv_tsecr &&
  4636. !between(tp->rx_opt.rcv_tsecr, tp->retrans_stamp,
  4637. tcp_time_stamp)) {
  4638. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_PAWSACTIVEREJECTED);
  4639. goto reset_and_undo;
  4640. }
  4641. /* Now ACK is acceptable.
  4642. *
  4643. * "If the RST bit is set
  4644. * If the ACK was acceptable then signal the user "error:
  4645. * connection reset", drop the segment, enter CLOSED state,
  4646. * delete TCB, and return."
  4647. */
  4648. if (th->rst) {
  4649. tcp_reset(sk);
  4650. goto discard;
  4651. }
  4652. /* rfc793:
  4653. * "fifth, if neither of the SYN or RST bits is set then
  4654. * drop the segment and return."
  4655. *
  4656. * See note below!
  4657. * --ANK(990513)
  4658. */
  4659. if (!th->syn)
  4660. goto discard_and_undo;
  4661. /* rfc793:
  4662. * "If the SYN bit is on ...
  4663. * are acceptable then ...
  4664. * (our SYN has been ACKed), change the connection
  4665. * state to ESTABLISHED..."
  4666. */
  4667. TCP_ECN_rcv_synack(tp, th);
  4668. tp->snd_wl1 = TCP_SKB_CB(skb)->seq;
  4669. tcp_ack(sk, skb, FLAG_SLOWPATH);
  4670. /* Ok.. it's good. Set up sequence numbers and
  4671. * move to established.
  4672. */
  4673. tp->rcv_nxt = TCP_SKB_CB(skb)->seq + 1;
  4674. tp->rcv_wup = TCP_SKB_CB(skb)->seq + 1;
  4675. /* RFC1323: The window in SYN & SYN/ACK segments is
  4676. * never scaled.
  4677. */
  4678. tp->snd_wnd = ntohs(th->window);
  4679. tcp_init_wl(tp, TCP_SKB_CB(skb)->ack_seq, TCP_SKB_CB(skb)->seq);
  4680. if (!tp->rx_opt.wscale_ok) {
  4681. tp->rx_opt.snd_wscale = tp->rx_opt.rcv_wscale = 0;
  4682. tp->window_clamp = min(tp->window_clamp, 65535U);
  4683. }
  4684. if (tp->rx_opt.saw_tstamp) {
  4685. tp->rx_opt.tstamp_ok = 1;
  4686. tp->tcp_header_len =
  4687. sizeof(struct tcphdr) + TCPOLEN_TSTAMP_ALIGNED;
  4688. tp->advmss -= TCPOLEN_TSTAMP_ALIGNED;
  4689. tcp_store_ts_recent(tp);
  4690. } else {
  4691. tp->tcp_header_len = sizeof(struct tcphdr);
  4692. }
  4693. if (tcp_is_sack(tp) && sysctl_tcp_fack)
  4694. tcp_enable_fack(tp);
  4695. tcp_mtup_init(sk);
  4696. tcp_sync_mss(sk, icsk->icsk_pmtu_cookie);
  4697. tcp_initialize_rcv_mss(sk);
  4698. /* Remember, tcp_poll() does not lock socket!
  4699. * Change state from SYN-SENT only after copied_seq
  4700. * is initialized. */
  4701. tp->copied_seq = tp->rcv_nxt;
  4702. smp_mb();
  4703. tcp_set_state(sk, TCP_ESTABLISHED);
  4704. security_inet_conn_established(sk, skb);
  4705. /* Make sure socket is routed, for correct metrics. */
  4706. icsk->icsk_af_ops->rebuild_header(sk);
  4707. tcp_init_metrics(sk);
  4708. tcp_init_congestion_control(sk);
  4709. /* Prevent spurious tcp_cwnd_restart() on first data
  4710. * packet.
  4711. */
  4712. tp->lsndtime = tcp_time_stamp;
  4713. tcp_init_buffer_space(sk);
  4714. if (sock_flag(sk, SOCK_KEEPOPEN))
  4715. inet_csk_reset_keepalive_timer(sk, keepalive_time_when(tp));
  4716. if (!tp->rx_opt.snd_wscale)
  4717. __tcp_fast_path_on(tp, tp->snd_wnd);
  4718. else
  4719. tp->pred_flags = 0;
  4720. if (!sock_flag(sk, SOCK_DEAD)) {
  4721. sk->sk_state_change(sk);
  4722. sk_wake_async(sk, SOCK_WAKE_IO, POLL_OUT);
  4723. }
  4724. if (sk->sk_write_pending ||
  4725. icsk->icsk_accept_queue.rskq_defer_accept ||
  4726. icsk->icsk_ack.pingpong) {
  4727. /* Save one ACK. Data will be ready after
  4728. * several ticks, if write_pending is set.
  4729. *
  4730. * It may be deleted, but with this feature tcpdumps
  4731. * look so _wonderfully_ clever, that I was not able
  4732. * to stand against the temptation 8) --ANK
  4733. */
  4734. inet_csk_schedule_ack(sk);
  4735. icsk->icsk_ack.lrcvtime = tcp_time_stamp;
  4736. icsk->icsk_ack.ato = TCP_ATO_MIN;
  4737. tcp_incr_quickack(sk);
  4738. tcp_enter_quickack_mode(sk);
  4739. inet_csk_reset_xmit_timer(sk, ICSK_TIME_DACK,
  4740. TCP_DELACK_MAX, TCP_RTO_MAX);
  4741. discard:
  4742. __kfree_skb(skb);
  4743. return 0;
  4744. } else {
  4745. tcp_send_ack(sk);
  4746. }
  4747. return -1;
  4748. }
  4749. /* No ACK in the segment */
  4750. if (th->rst) {
  4751. /* rfc793:
  4752. * "If the RST bit is set
  4753. *
  4754. * Otherwise (no ACK) drop the segment and return."
  4755. */
  4756. goto discard_and_undo;
  4757. }
  4758. /* PAWS check. */
  4759. if (tp->rx_opt.ts_recent_stamp && tp->rx_opt.saw_tstamp &&
  4760. tcp_paws_check(&tp->rx_opt, 0))
  4761. goto discard_and_undo;
  4762. if (th->syn) {
  4763. /* We see SYN without ACK. It is attempt of
  4764. * simultaneous connect with crossed SYNs.
  4765. * Particularly, it can be connect to self.
  4766. */
  4767. tcp_set_state(sk, TCP_SYN_RECV);
  4768. if (tp->rx_opt.saw_tstamp) {
  4769. tp->rx_opt.tstamp_ok = 1;
  4770. tcp_store_ts_recent(tp);
  4771. tp->tcp_header_len =
  4772. sizeof(struct tcphdr) + TCPOLEN_TSTAMP_ALIGNED;
  4773. } else {
  4774. tp->tcp_header_len = sizeof(struct tcphdr);
  4775. }
  4776. tp->rcv_nxt = TCP_SKB_CB(skb)->seq + 1;
  4777. tp->rcv_wup = TCP_SKB_CB(skb)->seq + 1;
  4778. /* RFC1323: The window in SYN & SYN/ACK segments is
  4779. * never scaled.
  4780. */
  4781. tp->snd_wnd = ntohs(th->window);
  4782. tp->snd_wl1 = TCP_SKB_CB(skb)->seq;
  4783. tp->max_window = tp->snd_wnd;
  4784. TCP_ECN_rcv_syn(tp, th);
  4785. tcp_mtup_init(sk);
  4786. tcp_sync_mss(sk, icsk->icsk_pmtu_cookie);
  4787. tcp_initialize_rcv_mss(sk);
  4788. tcp_send_synack(sk);
  4789. #if 0
  4790. /* Note, we could accept data and URG from this segment.
  4791. * There are no obstacles to make this.
  4792. *
  4793. * However, if we ignore data in ACKless segments sometimes,
  4794. * we have no reasons to accept it sometimes.
  4795. * Also, seems the code doing it in step6 of tcp_rcv_state_process
  4796. * is not flawless. So, discard packet for sanity.
  4797. * Uncomment this return to process the data.
  4798. */
  4799. return -1;
  4800. #else
  4801. goto discard;
  4802. #endif
  4803. }
  4804. /* "fifth, if neither of the SYN or RST bits is set then
  4805. * drop the segment and return."
  4806. */
  4807. discard_and_undo:
  4808. tcp_clear_options(&tp->rx_opt);
  4809. tp->rx_opt.mss_clamp = saved_clamp;
  4810. goto discard;
  4811. reset_and_undo:
  4812. tcp_clear_options(&tp->rx_opt);
  4813. tp->rx_opt.mss_clamp = saved_clamp;
  4814. return 1;
  4815. }
  4816. /*
  4817. * This function implements the receiving procedure of RFC 793 for
  4818. * all states except ESTABLISHED and TIME_WAIT.
  4819. * It's called from both tcp_v4_rcv and tcp_v6_rcv and should be
  4820. * address independent.
  4821. */
  4822. int tcp_rcv_state_process(struct sock *sk, struct sk_buff *skb,
  4823. struct tcphdr *th, unsigned len)
  4824. {
  4825. struct tcp_sock *tp = tcp_sk(sk);
  4826. struct inet_connection_sock *icsk = inet_csk(sk);
  4827. int queued = 0;
  4828. int res;
  4829. tp->rx_opt.saw_tstamp = 0;
  4830. switch (sk->sk_state) {
  4831. case TCP_CLOSE:
  4832. goto discard;
  4833. case TCP_LISTEN:
  4834. if (th->ack)
  4835. return 1;
  4836. if (th->rst)
  4837. goto discard;
  4838. if (th->syn) {
  4839. if (icsk->icsk_af_ops->conn_request(sk, skb) < 0)
  4840. return 1;
  4841. /* Now we have several options: In theory there is
  4842. * nothing else in the frame. KA9Q has an option to
  4843. * send data with the syn, BSD accepts data with the
  4844. * syn up to the [to be] advertised window and
  4845. * Solaris 2.1 gives you a protocol error. For now
  4846. * we just ignore it, that fits the spec precisely
  4847. * and avoids incompatibilities. It would be nice in
  4848. * future to drop through and process the data.
  4849. *
  4850. * Now that TTCP is starting to be used we ought to
  4851. * queue this data.
  4852. * But, this leaves one open to an easy denial of
  4853. * service attack, and SYN cookies can't defend
  4854. * against this problem. So, we drop the data
  4855. * in the interest of security over speed unless
  4856. * it's still in use.
  4857. */
  4858. kfree_skb(skb);
  4859. return 0;
  4860. }
  4861. goto discard;
  4862. case TCP_SYN_SENT:
  4863. queued = tcp_rcv_synsent_state_process(sk, skb, th, len);
  4864. if (queued >= 0)
  4865. return queued;
  4866. /* Do step6 onward by hand. */
  4867. tcp_urg(sk, skb, th);
  4868. __kfree_skb(skb);
  4869. tcp_data_snd_check(sk);
  4870. return 0;
  4871. }
  4872. res = tcp_validate_incoming(sk, skb, th, 0);
  4873. if (res <= 0)
  4874. return -res;
  4875. /* step 5: check the ACK field */
  4876. if (th->ack) {
  4877. int acceptable = tcp_ack(sk, skb, FLAG_SLOWPATH);
  4878. switch (sk->sk_state) {
  4879. case TCP_SYN_RECV:
  4880. if (acceptable) {
  4881. tp->copied_seq = tp->rcv_nxt;
  4882. smp_mb();
  4883. tcp_set_state(sk, TCP_ESTABLISHED);
  4884. sk->sk_state_change(sk);
  4885. /* Note, that this wakeup is only for marginal
  4886. * crossed SYN case. Passively open sockets
  4887. * are not waked up, because sk->sk_sleep ==
  4888. * NULL and sk->sk_socket == NULL.
  4889. */
  4890. if (sk->sk_socket)
  4891. sk_wake_async(sk,
  4892. SOCK_WAKE_IO, POLL_OUT);
  4893. tp->snd_una = TCP_SKB_CB(skb)->ack_seq;
  4894. tp->snd_wnd = ntohs(th->window) <<
  4895. tp->rx_opt.snd_wscale;
  4896. tcp_init_wl(tp, TCP_SKB_CB(skb)->ack_seq,
  4897. TCP_SKB_CB(skb)->seq);
  4898. /* tcp_ack considers this ACK as duplicate
  4899. * and does not calculate rtt.
  4900. * Fix it at least with timestamps.
  4901. */
  4902. if (tp->rx_opt.saw_tstamp &&
  4903. tp->rx_opt.rcv_tsecr && !tp->srtt)
  4904. tcp_ack_saw_tstamp(sk, 0);
  4905. if (tp->rx_opt.tstamp_ok)
  4906. tp->advmss -= TCPOLEN_TSTAMP_ALIGNED;
  4907. /* Make sure socket is routed, for
  4908. * correct metrics.
  4909. */
  4910. icsk->icsk_af_ops->rebuild_header(sk);
  4911. tcp_init_metrics(sk);
  4912. tcp_init_congestion_control(sk);
  4913. /* Prevent spurious tcp_cwnd_restart() on
  4914. * first data packet.
  4915. */
  4916. tp->lsndtime = tcp_time_stamp;
  4917. tcp_mtup_init(sk);
  4918. tcp_initialize_rcv_mss(sk);
  4919. tcp_init_buffer_space(sk);
  4920. tcp_fast_path_on(tp);
  4921. } else {
  4922. return 1;
  4923. }
  4924. break;
  4925. case TCP_FIN_WAIT1:
  4926. if (tp->snd_una == tp->write_seq) {
  4927. tcp_set_state(sk, TCP_FIN_WAIT2);
  4928. sk->sk_shutdown |= SEND_SHUTDOWN;
  4929. dst_confirm(sk->sk_dst_cache);
  4930. if (!sock_flag(sk, SOCK_DEAD))
  4931. /* Wake up lingering close() */
  4932. sk->sk_state_change(sk);
  4933. else {
  4934. int tmo;
  4935. if (tp->linger2 < 0 ||
  4936. (TCP_SKB_CB(skb)->end_seq != TCP_SKB_CB(skb)->seq &&
  4937. after(TCP_SKB_CB(skb)->end_seq - th->fin, tp->rcv_nxt))) {
  4938. tcp_done(sk);
  4939. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPABORTONDATA);
  4940. return 1;
  4941. }
  4942. tmo = tcp_fin_time(sk);
  4943. if (tmo > TCP_TIMEWAIT_LEN) {
  4944. inet_csk_reset_keepalive_timer(sk, tmo - TCP_TIMEWAIT_LEN);
  4945. } else if (th->fin || sock_owned_by_user(sk)) {
  4946. /* Bad case. We could lose such FIN otherwise.
  4947. * It is not a big problem, but it looks confusing
  4948. * and not so rare event. We still can lose it now,
  4949. * if it spins in bh_lock_sock(), but it is really
  4950. * marginal case.
  4951. */
  4952. inet_csk_reset_keepalive_timer(sk, tmo);
  4953. } else {
  4954. tcp_time_wait(sk, TCP_FIN_WAIT2, tmo);
  4955. goto discard;
  4956. }
  4957. }
  4958. }
  4959. break;
  4960. case TCP_CLOSING:
  4961. if (tp->snd_una == tp->write_seq) {
  4962. tcp_time_wait(sk, TCP_TIME_WAIT, 0);
  4963. goto discard;
  4964. }
  4965. break;
  4966. case TCP_LAST_ACK:
  4967. if (tp->snd_una == tp->write_seq) {
  4968. tcp_update_metrics(sk);
  4969. tcp_done(sk);
  4970. goto discard;
  4971. }
  4972. break;
  4973. }
  4974. } else
  4975. goto discard;
  4976. /* step 6: check the URG bit */
  4977. tcp_urg(sk, skb, th);
  4978. /* step 7: process the segment text */
  4979. switch (sk->sk_state) {
  4980. case TCP_CLOSE_WAIT:
  4981. case TCP_CLOSING:
  4982. case TCP_LAST_ACK:
  4983. if (!before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt))
  4984. break;
  4985. case TCP_FIN_WAIT1:
  4986. case TCP_FIN_WAIT2:
  4987. /* RFC 793 says to queue data in these states,
  4988. * RFC 1122 says we MUST send a reset.
  4989. * BSD 4.4 also does reset.
  4990. */
  4991. if (sk->sk_shutdown & RCV_SHUTDOWN) {
  4992. if (TCP_SKB_CB(skb)->end_seq != TCP_SKB_CB(skb)->seq &&
  4993. after(TCP_SKB_CB(skb)->end_seq - th->fin, tp->rcv_nxt)) {
  4994. NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPABORTONDATA);
  4995. tcp_reset(sk);
  4996. return 1;
  4997. }
  4998. }
  4999. /* Fall through */
  5000. case TCP_ESTABLISHED:
  5001. tcp_data_queue(sk, skb);
  5002. queued = 1;
  5003. break;
  5004. }
  5005. /* tcp_data could move socket to TIME-WAIT */
  5006. if (sk->sk_state != TCP_CLOSE) {
  5007. tcp_data_snd_check(sk);
  5008. tcp_ack_snd_check(sk);
  5009. }
  5010. if (!queued) {
  5011. discard:
  5012. __kfree_skb(skb);
  5013. }
  5014. return 0;
  5015. }
  5016. EXPORT_SYMBOL(sysctl_tcp_ecn);
  5017. EXPORT_SYMBOL(sysctl_tcp_reordering);
  5018. EXPORT_SYMBOL(sysctl_tcp_adv_win_scale);
  5019. EXPORT_SYMBOL(tcp_parse_options);
  5020. #ifdef CONFIG_TCP_MD5SIG
  5021. EXPORT_SYMBOL(tcp_parse_md5sig_option);
  5022. #endif
  5023. EXPORT_SYMBOL(tcp_rcv_established);
  5024. EXPORT_SYMBOL(tcp_rcv_state_process);
  5025. EXPORT_SYMBOL(tcp_initialize_rcv_mss);