<> <> <> <> <> <> <> <<>> 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.