<> <> <<>> DIRECTORY Arpa USING [Address, nullAddress], ArpaBuf USING [Buffer, DataBytes, FragmentOffsetBytes, maxBodyBytes, maxTimeToLive, MoreFragments, OptionsBytes, Protocol], ArpaICMP USING [AllocBuffer, FreeBuffer, Send, SetBodyBytes], ArpaICMPBuf USING [Body, Buffer], ArpaIP USING [AllocBuffers, FreeBuffers, GetSource, MoveBytes], ArpaIPReassembly USING [], Basics USING [Card16FromH, FWORD, HFromCard16, HWORD], CommDriver USING [Buffer], Process USING [Detach, PauseMsec] ; ArpaIPReassemblyImpl: CEDAR MONITOR IMPORTS ArpaBuf, ArpaICMP, ArpaIP, Basics, Process EXPORTS ArpaIPReassembly ~ { <> minFirstFragment: CARDINAL _ 60; <> <> HWORD: TYPE ~ Basics.HWORD; FWORD: TYPE ~ Basics.FWORD; Address: TYPE ~ Arpa.Address; Protocol: TYPE ~ ArpaBuf.Protocol; Buffer: TYPE ~ ArpaBuf.Buffer; Buffers: TYPE ~ ArpaBuf.Buffer; DriverBuffer: PROC [b: Buffer] RETURNS [CommDriver.Buffer] ~ TRUSTED INLINE { RETURN [LOOPHOLE[b]] }; IPBuffer: PROC [b: CommDriver.Buffer] RETURNS [Buffer] ~ TRUSTED INLINE { RETURN [LOOPHOLE[b]] }; Next: PROC [b: Buffer] RETURNS [Buffer] ~ TRUSTED INLINE { RETURN [LOOPHOLE[b.ovh.next]] }; <> numHashHeaders: CARDINAL ~ 31; HashIndex: TYPE ~ [0 .. numHashHeaders); FragmentTable: TYPE ~ REF FragmentTableRep; FragmentTableRep: TYPE ~ ARRAY HashIndex OF Fragments; Fragments: TYPE ~ REF FragmentsObject; FragmentsObject: TYPE ~ RECORD [ next: Fragments, head: Buffers, tail: Buffer, source, dest: Address _ Arpa.nullAddress, fragmentId: HWORD _ [0, 0], protocol: Protocol _ Protocol.FIRST, waiters: CARDINAL _ 0, free: CONDITION, ttl: CARDINAL _ ArpaBuf.maxTimeToLive, holes: CARDINAL _ 1, -- an empty fragment list comprises a single hole busy: BOOL _ TRUE ]; fragmentTable: FragmentTable ~ NEW[FragmentTableRep]; Hash: PROC [b: Buffer] RETURNS [HashIndex] ~ INLINE { RETURN [Basics.Card16FromH[b.hdr1.fragmentId] MOD numHashHeaders] }; fragmentsFreeList: Fragments _ NIL; NewFragments: INTERNAL PROC RETURNS [f: Fragments] ~ { IF (f _ fragmentsFreeList) # NIL THEN { fragmentsFreeList _ f.next; f.waiters _ 0; f.ttl _ ArpaBuf.maxTimeToLive; f.holes _ 1; f.busy _ TRUE; } ELSE { f _ NEW[FragmentsObject]; }; }; FreeFragments: INTERNAL PROC [f: Fragments] ~ { f.next _ fragmentsFreeList; f.head _ f.tail _ NIL; -- help GC fragmentsFreeList _ f; }; FreeFragmentsList: ENTRY PROC [head, tail: Fragments] ~ { IF head = NIL THEN RETURN; IF tail = NIL THEN ERROR; tail.next _ fragmentsFreeList; fragmentsFreeList _ head; }; GetFragments: ENTRY PROC [b: Buffer] RETURNS [f: Fragments] ~ { <> h: HashIndex ~ Hash[b]; FOR finger: Fragments _ fragmentTable[h], finger.next WHILE finger # NIL DO { OPEN finger, bh: b.hdr1; IF (source # bh.source) OR (dest # bh.dest) OR (fragmentId # bh.fragmentId) OR (protocol # bh.protocol) THEN LOOP; }; IF finger.busy THEN { finger.waiters _ finger.waiters.SUCC; WHILE finger.busy DO WAIT finger.free; ENDLOOP; finger.waiters _ finger.waiters.PRED; }; finger.busy _ TRUE; RETURN [finger]; ENDLOOP; f _ NewFragments[]; { OPEN f, bh: b.hdr1; source _ bh.source; dest _ bh.dest; fragmentId _ bh.fragmentId; protocol _ bh.protocol; }; f.next _ fragmentTable[h]; fragmentTable[h] _ f; }; ReleaseFragments: ENTRY PROC [f: Fragments] RETURNS [chain: Buffers] ~ { <> f.busy _ FALSE; IF f.waiters > 0 THEN { NOTIFY f.free; RETURN [NIL]; }; IF f.holes = 0 THEN { h: HashIndex ~ Hash[f.head]; IF fragmentTable[h] = f THEN fragmentTable[h] _ f.next ELSE FOR finger: Fragments _ fragmentTable[h], finger.next DO IF finger.next = f THEN { finger.next _ f.next; EXIT }; ENDLOOP; chain _ f.head; FreeFragments[f]; }; }; <> secsBetweenSweeps: CARDINAL _ 10; timedOutFragments: CARD _ 0; Daemon: PROC ~ { DO Process.PauseMsec[1000*secsBetweenSweeps]; FOR i: HashIndex IN HashIndex DO dead: Fragments _ AgeAndKillFragments[i]; IF dead # NIL THEN BuryDeadFragmentsList[dead]; ENDLOOP; ENDLOOP; }; AgeAndKillFragments: ENTRY PROC [i: HashIndex] RETURNS [dead: Fragments _ NIL] ~ { saved, p: Fragments; saved _ NIL; p _ fragmentTable[i]; WHILE p # NIL DO next: Fragments ~ p.next; SELECT TRUE FROM (p.ttl > secsBetweenSweeps) => { p.ttl _ p.ttl - secsBetweenSweeps; p.next _ saved; saved _ p; }; (p.busy OR (p.waiters > 0)) => { p.ttl _ 0; p.next _ saved; saved _ p; }; ENDCASE => { p.next _ dead; dead _ p; }; p _ next; ENDLOOP; fragmentTable[i] _ saved; }; BuryDeadFragmentsList: PROC [dead: Fragments] ~ { f: Fragments _ dead; IF dead = NIL THEN ERROR; -- DEBUG DO timedOutFragments _ timedOutFragments.SUCC; IF f.head = NIL THEN ERROR; SendTimeExceededMessage[f.head]; ArpaIP.FreeBuffers[f.head]; f.head _ f.tail _ NIL; IF f.next = NIL THEN EXIT; f _ f.next; ENDLOOP; FreeFragmentsList[dead, f]; }; SendTimeExceededMessage: PROC [b: Buffers] ~ { icmpB: ArpaICMPBuf.Buffer ~ ArpaICMP.AllocBuffer[NIL]; icmpB.hdr2.icmpType _ timeExceeded; icmpB.hdr2.timeExceededCode _ fragmentReassembly; icmpB.body.timeExceeded.unused _ [[0, 0], [0, 0]]; TRUSTED { ArpaIP.MoveBytes[toPtr~@icmpB.body, toOffset~BYTES[FWORD], fromPtr~@b.hdr1, fromOffset~0, bytes~BYTES[ArpaICMPBuf.Body.timeExceeded]-BYTES[FWORD]] }; ArpaICMP.SetBodyBytes[icmpB, BYTES[ArpaICMPBuf.Body.timeExceeded]]; ArpaICMP.Send[NIL, icmpB, ArpaIP.GetSource[b]]; ArpaICMP.FreeBuffer[NIL, icmpB]; }; <> totalFragmentsReceived: CARD _ 0; errorIternalNoData: CARD _ 0; errorInternalMoreFragments: CARD _ 0; errorOverlap: CARD _ 0; errorShortFirstFragment: CARD _ 0; ReassembleAndMoveOptions: PUBLIC PROC [b: Buffer] RETURNS [datagram: Buffers] ~ { <> f: Fragments; totalFragmentsReceived _ totalFragmentsReceived.SUCC; f _ GetFragments[b~b]; f.ttl _ MAX[f.ttl, b.hdr1.timeToLive]; BEGIN myFragmentOffset: CARD16 ~ ArpaBuf.FragmentOffsetBytes[b]; fragmentsAfterMe: BOOL ~ ArpaBuf.MoreFragments[b]; myOptionsBytes: CARD16 ~ ArpaBuf.OptionsBytes[b]; myDataBytes: CARD16 ~ ArpaBuf.DataBytes[b]; mergeBack, mergeFwd: BOOL _ FALSE; p, prev: Buffer; IF (myDataBytes = 0) AND fragmentsAfterMe THEN { errorIternalNoData _ errorIternalNoData.SUCC; GOTO Drop }; <> <> SELECT TRUE FROM (f.tail = NIL) => { prev _ p _ NIL }; (ArpaBuf.FragmentOffsetBytes[f.tail]) < myFragmentOffset -- common case -- => { prev _ f.tail; p _ NIL }; ENDCASE => { prev _ NIL; p _ f.head; WHILE ArpaBuf.FragmentOffsetBytes[p] < myFragmentOffset DO prev _ p; p _ Next[p]; ENDLOOP; }; <<>> <> IF prev = NIL THEN mergeBack _ (myFragmentOffset = 0) ELSE { IF NOT ArpaBuf.MoreFragments[prev] THEN { errorInternalMoreFragments _ errorInternalMoreFragments.SUCC; GOTO Drop }; SELECT (ArpaBuf.FragmentOffsetBytes[prev] + ArpaBuf.DataBytes[prev]) FROM myFragmentOffset => mergeBack _ TRUE; > myFragmentOffset => { errorOverlap _ errorOverlap.SUCC; GOTO Drop }; ENDCASE; }; IF p = NIL THEN mergeFwd _ (NOT fragmentsAfterMe) ELSE { myNextFragmentOffset: CARD16 ~ myFragmentOffset + myDataBytes; IF NOT fragmentsAfterMe THEN { errorInternalMoreFragments _ errorInternalMoreFragments.SUCC; GOTO Drop }; SELECT ArpaBuf.FragmentOffsetBytes[p] FROM < myNextFragmentOffset => { errorOverlap _ errorOverlap.SUCC; GOTO Drop }; myNextFragmentOffset => mergeFwd _ TRUE; ENDCASE; }; f.holes _ f.holes.SUCC; IF mergeBack THEN f.holes _ f.holes.PRED; IF mergeFwd THEN f.holes _ f.holes.PRED; <> IF mergeBack AND (prev # NIL) THEN { offsetInBuffer: CARD16 _ ArpaBuf.DataBytes[prev]; IF ((offsetInBuffer + myDataBytes) <= ArpaBuf.maxBodyBytes) THEN { TRUSTED { ArpaIP.MoveBytes[toPtr~@prev.body, toOffset~offsetInBuffer, fromPtr~@b.body, fromOffset~myOptionsBytes, bytes~myDataBytes] }; prev.hdr1.length _ Basics.HFromCard16[Basics.Card16FromH[prev.hdr1.length] + myDataBytes]; GOTO Drop; }; }; <> IF myOptionsBytes # 0 THEN { <> temp: Buffer ~ b; b _ ArpaIP.AllocBuffers[1]; b.ovh.network _ temp.ovh.network; b.hdr1 _ temp.hdr1; TRUSTED {ArpaIP.MoveBytes[toPtr~@DriverBuffer[b].spaceForOptions, toOffset~0, fromPtr~@temp.body, fromOffset~0, bytes~myOptionsBytes] }; TRUSTED { ArpaIP.MoveBytes[toPtr~@b.body, toOffset~0, fromPtr~@temp.body, fromOffset~myOptionsBytes, bytes~myDataBytes] }; ArpaIP.FreeBuffers[temp]; }; <<>> <> IF prev = NIL THEN { b.ovh.next _ f.head; f.head _ b } ELSE { b.ovh.next _ prev.ovh.next; prev.ovh.next _ b }; IF prev = f.tail THEN f.tail _ b; GOTO Done; EXITS Drop => ArpaIP.FreeBuffers[b]; Done => NULL; END; datagram _ ReleaseFragments[f~f]; IF (datagram # NIL) AND (Next[datagram] # NIL) AND (ArpaBuf.DataBytes[datagram] < minFirstFragment) THEN { <> errorShortFirstFragment _ errorShortFirstFragment.SUCC; ArpaIP.FreeBuffers[datagram]; datagram _ NIL; }; }; <> TRUSTED { Process.Detach[ FORK Daemon[] ] }; }...