DIRECTORY IPDefs USING [Datagram, maxDataLength], IPOps USING [HeaderChecksum, MoveBytes], IPReassembly; IPReassemblyImpl: CEDAR MONITOR IMPORTS IPOps EXPORTS IPReassembly = BEGIN OPEN IPReassembly; Clumps: TYPE = LIST OF IPDefs.Datagram; DatagramTooLong: ERROR = CODE; single, arrived, merged, finished, died, bad: PUBLIC INT _ 0; reassemblyQueue: LIST OF Clumps _ NIL; -- Packets on this queue may have incorrect checksums. IsFragment: PUBLIC PROC [data: IPDefs.Datagram] RETURNS [BOOL] = { RETURN [data.inHdr.moreFragments OR data.inHdr.fragmentOffset # 0]; }; Reassemble: PUBLIC ENTRY PROC [data: IPDefs.Datagram] RETURNS [newData: IPDefs.Datagram] = { ENABLE UNWIND => NULL; Adjacent: PROC [d1, d2: IPDefs.Datagram] RETURNS [BOOL] = { RETURN [(d1.inHdr.fragmentOffset + (INT[d1.inHdr.packetLength] - d1.inHdr.IHL*4) / 8) = d2.inHdr.fragmentOffset]; }; Merge: PROC [d1, d2: IPDefs.Datagram] RETURNS [newData: IPDefs.Datagram] = { dataLength1: INT _ d1.inHdr.packetLength - d1.inHdr.IHL*4; dataLength2: INT _ d2.inHdr.packetLength - d2.inHdr.IHL*4; IF dataLength1+dataLength2 > IPDefs.maxDataLength THEN ERROR DatagramTooLong; d1.inHdr.packetLength _ d1.inHdr.packetLength+dataLength2; d1.inHdr.moreFragments _ d2.inHdr.moreFragments; d1.inHdr.timeToLive _ MAX[d1.inHdr.timeToLive, d2.inHdr.timeToLive]; TRUSTED {IPOps.MoveBytes[@d1.data, dataLength1, @d2.data, 0, dataLength2]}; d1.dataLength _ d1.inHdr.packetLength-d1.inHdr.IHL*4; merged _ merged + 1; RETURN [d1]; }; IF ~IsFragment[data] THEN { single _ single + 1; RETURN [data]; }; newData _ NIL; -- assume we won't get a reassembled packet arrived _ arrived + 1; FOR q: LIST OF Clumps _ reassemblyQueue, q.rest WHILE q # NIL DO fq: LIST OF IPDefs.Datagram _ q.first; d: IPDefs.Datagram _ fq.first; IF d.inHdr.fragmentId = data.inHdr.fragmentId AND d.inHdr.protocol = data.inHdr.protocol AND d.inHdr.source = data.inHdr.source AND d.inHdr.destination = data.inHdr.destination THEN { ENABLE DatagramTooLong => { reassemblyQueue _ RemoveClump[fq, reassemblyQueue]; bad _ bad + 1; GOTO Quit}; FOR q2: LIST OF IPDefs.Datagram _ fq, q2.rest UNTIL q2 = NIL DO d2: IPDefs.Datagram _ q2.first; SELECT TRUE FROM Adjacent[d2, data] => { q2.first _ data _ Merge[d2, data]; IF q2.rest # NIL THEN { d2 _ q2.rest.first; IF Adjacent[data, d2] THEN { q2.first _ data _ Merge[data, d2]; q2.rest _ q2.rest.rest; }; }; EXIT; }; data.inHdr.fragmentOffset < d2.inHdr.fragmentOffset => { q2.rest _ CONS[d2, q2.rest]; q2.first _ data; EXIT; }; Adjacent[data, d2] => { q2.first _ data _ Merge[data, d2]; EXIT; }; q2.rest = NIL => { q2.rest _ CONS[data, NIL]; EXIT; }; ENDCASE => NULL; ENDLOOP; IF NOT IsFragment[data] THEN { finished _ finished + 1; reassemblyQueue _ RemoveClump[fq, reassemblyQueue]; data.inHdr.checksum _ IPOps.HeaderChecksum[data]; newData _ data; }; RETURN; }; REPEAT FINISHED => reassemblyQueue _ CONS [LIST[data], reassemblyQueue]; ENDLOOP; EXITS Quit => RETURN; }; AgeFragments: PUBLIC ENTRY PROC [nSeconds: INT] = BEGIN ENABLE UNWIND => NULL; FOR q: LIST OF LIST OF IPDefs.Datagram _ reassemblyQueue, q.rest WHILE q # NIL DO fq: LIST OF IPDefs.Datagram _ q.first; FOR q2: LIST OF IPDefs.Datagram _ fq, q2.rest WHILE q2 # NIL DO d: IPDefs.Datagram _ q2.first; IF INT[d.inHdr.timeToLive]-nSeconds <= 0 THEN { fq.first _ NIL; died _ died + 1; } ELSE d.inHdr.timeToLive _ d.inHdr.timeToLive-nSeconds; ENDLOOP; q.first _ RemoveNilDatagrams[fq]; ENDLOOP; reassemblyQueue _ RemoveNilClumps[reassemblyQueue]; END; RemoveNilDatagrams: PROC [l: LIST OF IPDefs.Datagram] RETURNS [newL: LIST OF IPDefs.Datagram] = BEGIN newL _ NIL; WHILE l # NIL DO IF l.first # NIL THEN newL _ AppendDatagram[newL, l.first]; l _ l.rest; ENDLOOP; END; AppendDatagram: PROC [list: LIST OF IPDefs.Datagram, ref: IPDefs.Datagram] RETURNS[LIST OF IPDefs.Datagram] = INLINE BEGIN z: LIST OF IPDefs.Datagram _ list; IF z = NIL THEN RETURN[CONS[ref, NIL]]; UNTIL z.rest = NIL DO z _ z.rest; ENDLOOP; z.rest _ CONS[ref, NIL]; RETURN[list]; END; RemoveDatagram: PUBLIC PROC [ref: IPDefs.Datagram, list: LIST OF IPDefs.Datagram] RETURNS[val: LIST OF IPDefs.Datagram] = BEGIN z: LIST OF IPDefs.Datagram _ NIL; val _ NIL; UNTIL list = NIL DO IF list.first # ref THEN {IF val = NIL THEN {val _ CONS[list.first, NIL]; z _ val} ELSE {z.rest _ CONS[list.first, z.rest]; z _ z.rest}}; list _ list.rest; ENDLOOP; END; RemoveNilClumps: PROC [l: LIST OF Clumps] RETURNS [newL: LIST OF Clumps] = BEGIN newL _ NIL; WHILE l # NIL DO IF l.first # NIL THEN newL _ AppendClump[newL, l.first]; l _ l.rest; ENDLOOP; END; AppendClump: PROC [list: LIST OF Clumps, ref: Clumps] RETURNS[LIST OF Clumps] = INLINE BEGIN z: LIST OF Clumps _ list; IF z = NIL THEN RETURN[CONS[ref, NIL]]; UNTIL z.rest = NIL DO z _ z.rest; ENDLOOP; z.rest _ CONS[ref, NIL]; RETURN[list]; END; RemoveClump: PUBLIC PROC [ref: Clumps, list: LIST OF Clumps] RETURNS[val: LIST OF Clumps] = BEGIN z: LIST OF Clumps _ NIL; val _ NIL; UNTIL list = NIL DO IF list.first # ref THEN {IF val = NIL THEN {val _ CONS[list.first, NIL]; z _ val} ELSE {z.rest _ CONS[list.first, z.rest]; z _ z.rest}}; list _ list.rest; ENDLOOP; END; END. ZCopyright (C) 1983, 1984 by Xerox Corporation. All rights reserved. The following program was created in 1983 but has not been published within the meaning of the copyright law, is furnished under license, and may not be used, copied and/or disclosed except in accordance with the terms of said license. IPReassemblyImpl.mesa Last Edited by: HGM, October 7, 1984 7:20:03 am PDT Last Edited by: Nichols, August 24, 1983 6:57 pm Last Edited by: Taft, January 5, 1984 5:16 pm Hal Murray May 7, 1985 10:30:41 pm PDT John Larson, July 23, 1987 12:56:01 pm PDT We do fragment reassembly here. Returns NIL or a reassembled datagram. Find a fragment list that matches this one. Create one if need be. Put this fragment on the list, merging it with the preceding and following fragments if we should. Check to see if this has left us with a reassembled datagram. If so, rechecksum it and return it. Return TRUE if d1 and d2 are adjacent fragments. Merge the two fragments and return the result. Execptions? Fixup the header. and the data. Give up on this set of fragments. Now scan down the fragment list trying to fit this one in. Splice it in before the current fragment. Now data points to the merged packet (or to the original which is a fragment). Create a new list for this fragment. Adjust the timeToLive fields in the fragments and toss any that are too old. Э╩Ц "cedar" styleШIcode2ЪЬпЩпheadЩIbodyЩ3MЩ0MЩ-IcodeЩ&NЩ*NЩЪ╧k Ш KЪЬЭЬШ'KЪЬЭЬШ(KЪЬ Ш ЧЧЪ╧nЬЭЬЭШKЪЭЬШ KЪЭЬШKЪЭЬЭЬШKЪЬЭЬЭЬЭЬШ'KЪЮЬЭЬЭЬШKШKЪЬ.Э ЬШ=KЪЬЭЬЭЬ ЭЬ╧c6Ш]Ъ Ю ЬЭЬЭЬЭЬЭЬШBKЪЭЬЭЬ ШCKШЧЪ Ю ЬЭЬЭЬЭЬЭЬШ\ЩGKЩCKЩbKЩbЧKЪЭЬЭЬЭЬШKШЪЮЬЭЬЭЬЭЬШ;KЩ0KЪЭЬЭЬ#ЭЬ'ШtKШЧЪЮЬЭЬЭЬШLKЩ;KЪЬ ЭЬ$ЭЬШ:KЪЬ ЭЬ$ЭЬШ:ЪЭЬ0ЭШ6KЪЭЬШЧKЩKЪЬ:Ш:KЪЬ0Ш0KЪЬЭЬ+ШDKЩ KЪЭЬDШKKЪЬ/ЭЬШ5KШKЪЭЬ ШKШЧЪЭЬЭЬШKЪЬШKЪЭЬШЧKЪЬ ЭЬЯ+Ш;KШЪЭЬЭЬЭЬ"ЭЬЭЬЭШ@KЪЬЭЬЭЬШ&KЪЬШЪ ЭЬ,ЭЬ(ЭЬ$ЭЬ.ЭЬШ╖ЪЭШШKЩ!KЪЬ3Ш3KШKЪЭЬШЧЧKЩ:ЪЭЬЭЬЭЬЭЬЭЬЭШ?KЪЬШЪЭЬЭЬЭШЪЬШKШ"ЪЭЬЭЬЭЬШKЪЬШЪЭЬЭЬШKШ"KШЧЧKЪЭЬШЧЪЬ8Ш8KЩ)KЪЬ ЭЬШKШKЪЭЬШЧKЪЬ;ЭЬШCKЪ Ь ЭЬЭЬЭЬЭЬШ6KЪЭЬЭЬШЧKЪЭЬШЧKЩNЪЭЬЭЬЭЬШKШKЪЬ3Ш3KЪЬ1Ш1KШЧKЪЭЬШ ЧKЪЭШЪЭЬШKЩ$KЪЬЭЬЭЬШ5ЧKЪЭЬШЪЭШKЪЬЭЬШЧЧKШЧЪ ЮЬЭЬЭЬЭЬЭЬШ1KЪЭШKЩLKЪЭЬЭЬЭЬШЪЭЬЭЬЭЬЭЬЭЬ+ЭЬЭЬЭШQKЪЬЭЬЭЬШ&ЪЭЬЭЬЭЬЭЬЭЬЭШ?KЪЬШЪЭЬЭЬ#ЭЬШ/KЪЬЭЬШKЪЬШЧKЪЭЬ2Ш6KЪЭЬШЧKШ!KЪЭЬШЧKШ3KЪЭЬШЧЪЮЬЭЬЭЬЭЬЭЬЭЬЭЬШ_KЪЭШKЪЬЭЬШЪЭЬЭЬЭШKЪЭЬЭЬЭЬ&Ш;KШKЪЭЬШЧKЪЭЬШЧЪЮЬЭЬЭЬЭЬ(ЭЬЭЬЭЬЭШtKЪЭШJЪЬЭЬЭЬШ"JЪЭЬЭЬЭЬЭЬЭЬЭЬШ'JЪЭЬ ЭЬЭЬ ЭЬШ*JЪЬ ЭЬЭЬШJЪЭЬШ JЪЭЬШЧЪЮЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШyKЪЭШJЪЬЭЬЭЬЭЬШ!JЪЬЭЬШ ЪЭЬЭЬЭШЪЭЬЭШJЪЬЭЬЭЬЭЬЭЬ ЭЬШ9JЪЭЬЭЬ#Ш6ЧЧJШJЪЭЬШ JЪЭЬШЧЪЮЬЭЬЭЬЭЬ ЭЬЭЬЭЬ ШJKЪЭШKЪЬЭЬШЪЭЬЭЬЭШKЪЭЬЭЬЭЬ#Ш8KШKЪЭЬШЧKЪЭЬШЧЪЮЬЭЬЭЬЭЬЭЬЭЬЭЬЭШVKЪЭШJЪЬЭЬЭЬШJЪЭЬЭЬЭЬЭЬЭЬЭЬШ'JЪЭЬ ЭЬЭЬ ЭЬШ*JЪЬ ЭЬЭЬШJЪЭЬШ JЪЭЬШЧЪЮЬЭЬЭЬЭЬЭЬ ЭЬЭЬЭЬ Ш[KЪЭШJЪЬЭЬЭЬ ЭЬШJЪЬЭЬШ ЪЭЬЭЬЭШЪЭЬЭШJЪЬЭЬЭЬЭЬЭЬ ЭЬШ9JЪЭЬЭЬ#Ш6ЧJШJЪЭЬШ ЧJЪЭЬШЧKЪЭЬШЧЧЕЧ·!e