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
~ {
Parameter
minFirstFragment:
CARDINAL ← 60;
Guaranteed long enough to hold an entire (TCP, UDP, ICMP) header in worst case.
Types
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]] };
Fragments Table
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] ~ {
Get (and lock) the Fragments entry for b, creating one if it's not there.
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] ~ {
Unlock the fragments object if it's incomplete; if it's complete, remove it from the table and return the datagram chain for dispatching.
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];
};
};
Daemon
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];
};
Reassembly
totalFragmentsReceived: CARD ← 0;
errorIternalNoData: CARD ← 0;
errorInternalMoreFragments: CARD ← 0;
errorOverlap: CARD ← 0;
errorShortFirstFragment: CARD ← 0;
ReassembleAndMoveOptions:
PUBLIC
PROC [b: Buffer]
RETURNS [datagram: Buffers] ~ {
Return a buffer chain acceptable for dispatching, or NIL if we don't have a complete datagram yet.
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 };
This is arguable, but note if the packet had really been dropped there would be no way to tell.
Set [prev, p] to bracket correct position of buf in fragment chain.
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;
};
Set [mergeBack, mergeFwd, holes]
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;
Try moving bytes into existing buffer in chain.
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;
};
};
Swap IP options to end if necessary.
IF myOptionsBytes # 0
THEN {
Copy the buffer, moving options to the right place.
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];
};
Insert b directly into the chain without copying.
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 {
This hack ensures that a higher-level protocol module sees the entire header in the first buffer of the chain.
errorShortFirstFragment ← errorShortFirstFragment.SUCC;
ArpaIP.FreeBuffers[datagram]; datagram ← NIL;
};
};
Initialization
TRUSTED { Process.Detach[ FORK Daemon[] ] };
}...