<> <> <> <> <> <> <> DIRECTORY List USING [Nconc1], IPDefs USING [Datagram, DByte], TCPLogging USING [Direction, PrintMessage, PrintStateChange, PrintTCPPacket], TCPOps USING [ChecksumsMatch, Flip, pktsDuplicate, pktsFromFuture, pktsFromPast, pktsRcvd, pktsWithNoConnection, pktsWithBadChecksum, repacketizing, sendBufferLength, SetTimeout, TCPChecksum, TCPHandle, TCPHeaderP, TCPRcvBuffer, tcpSegmentLife], TCPReceiving USING [], TCPStates USING [CloseConnection, FindHandle, GetInitialSequenceNumber], TCPTransmit USING [RemoveAckedSegments, SendReset, SendSYN, TryToSend, TryToSendData]; TCPReceivingImpl: CEDAR MONITOR LOCKS handle USING handle: TCPHandle IMPORTS List, TCPLogging, TCPOps, TCPStates, TCPTransmit EXPORTS TCPReceiving = BEGIN OPEN TCPOps, TCPReceiving; SeqCode: TYPE = {pastSeq, okSeq, futureSeq}; ProcessRcvdSegment: PUBLIC PROC [rcvdDatagram: IPDefs.Datagram] = TRUSTED { <> <> <> <> <> tcpHdrPtr: TCPHeaderP; nSeqBytes: INT; handle: TCPHandle; checksum: IPDefs.DByte _ TCPOps.TCPChecksum[rcvdDatagram]; pktsRcvd _ pktsRcvd + 1; tcpHdrPtr _ LOOPHOLE[@rcvdDatagram.data]; IF ~TCPOps.ChecksumsMatch[checksum, tcpHdrPtr.checksum] THEN { pktsWithBadChecksum _ pktsWithBadChecksum + 1; TCPLogging.PrintMessage["Bad checksum"]; RETURN; }; nSeqBytes _ rcvdDatagram.dataLength - tcpHdrPtr.dataWordOffset * 4; IF tcpHdrPtr.syn THEN nSeqBytes _ nSeqBytes + 1; IF tcpHdrPtr.fin THEN nSeqBytes _ nSeqBytes + 1; <> handle _ TCPStates.FindHandle[rcvdDatagram]; TCPLogging.PrintTCPPacket[handle, rcvdDatagram, fromNet]; IF handle = NIL THEN { IF ~tcpHdrPtr.rst THEN -- if no matching TCB IF tcpHdrPtr.ack THEN -- if not a reset, then send a reset TCPTransmit.SendReset[NIL, tcpHdrPtr.dstnPort, tcpHdrPtr.sourcePort, rcvdDatagram.inHdr.source, Flip[tcpHdrPtr.ackNumber], 0] -- with no ack ELSE TCPTransmit.SendReset[NIL, tcpHdrPtr.dstnPort, tcpHdrPtr.sourcePort, rcvdDatagram.inHdr.source, 0, Flip[tcpHdrPtr.seqNumber] + nSeqBytes]; -- with ack pktsWithNoConnection _ pktsWithNoConnection + 1; TCPLogging.PrintMessage["No connection"]; RETURN; }; ContinueProcessingRcvdSegment[handle, rcvdDatagram]; }; ContinueProcessingRcvdSegment: ENTRY PROC [handle: TCPHandle, rcvdDatagram: IPDefs.Datagram] = { <> <> <> <> <> <> <> <> <> <> <> ENABLE UNWIND => NULL; tcpRcvBufferPtr: REF TCPRcvBuffer; -- info block for rcvd packet tcpHdrPtr: TCPHeaderP; -- pointer to tcp header ackNumber, seqNumber: INT; -- from tcpHdrPtr, Flipped for us seqResult: SeqCode; -- result of seq number check nSeqBytes: INT; -- number of data bytes + syn, fin continueProcessing: BOOL; -- true if more processing to do freeSegment: BOOL; -- true to dispose of segment finFlag: BOOL; -- true if segment contains fin sendAck: BOOL; -- set to send ack sendData: BOOL; -- set to send data connectionClosed: BOOL; -- set when close connection so that its not referenced again DisposeRcvdBuffer: PROC = { -- dispose of pkts on fromNet queue IF handle.fromNetQueue # NIL THEN handle.fromNetQueue _ handle.fromNetQueue.rest; }; ProcessReset: PROC = { SELECT handle.state FROM listen => freeSegment _ TRUE; -- ignore the reset synSent => TRUSTED { -- if segment has acceptable ack, close connection IF tcpHdrPtr.ack AND ackNumber-handle.iss > 0 AND ackNumber-handle.sndNxt <= 0 THEN { TCPStates.CloseConnection[handle, remoteAbort]; connectionClosed _ TRUE; }; }; synRcvd => -- if were listening, return to listen else reset IF ~handle.active THEN { TCPLogging.PrintStateChange[handle, listen]; handle.state _ listen; } ELSE { TCPStates.CloseConnection[handle, remoteAbort]; connectionClosed _ TRUE; }; established, finWait1, finWait2, closeWait, closing, lastAck, timeWait => { TCPStates.CloseConnection[handle, remoteAbort]; connectionClosed _ TRUE; }; ENDCASE; }; SignalUserUrgent: INTERNAL PROC = { NOTIFY handle.urgentAvailable; }; ProcessUrgent: INTERNAL PROC = TRUSTED { IF ~handle.urgentMode THEN { <> handle.urgentMode _ TRUE; handle.rcvUp _ tcpHdrPtr.urgentPtr + seqNumber; IF handle.state = established OR handle.state = finWait1 OR handle.state = finWait2 THEN SignalUserUrgent[] } ELSE -- else update urgent pointer IF handle.rcvUp < tcpHdrPtr.urgentPtr + seqNumber THEN handle.rcvUp _ tcpHdrPtr.urgentPtr + seqNumber; }; ProcessAck: INTERNAL PROC = { nDataBytesAcked: INT; SELECT handle.state FROM listen => {-- no acks are acceptable, send reset TRUSTED {TCPTransmit.SendReset[handle, handle.localPort, tcpHdrPtr.sourcePort, rcvdDatagram.inHdr.source, ackNumber, 0]}; freeSegment _ TRUE; continueProcessing _ FALSE; RETURN; }; synRcvd, synSent => IF ackNumber - handle.iss <= 0 OR ackNumber - handle.sndNxt > 0 THEN { -- if unacceptable ack, then send reset TRUSTED {TCPTransmit.SendReset[handle, handle.localPort, handle.foreignPort, handle.foreignAddr, ackNumber, 0]}; freeSegment _ TRUE; continueProcessing _ FALSE; RETURN; } ENDCASE; IF ackNumber - handle.sndNxt > 0 THEN { -- ack from future send an ack and discard the packet sendAck _ TRUE; freeSegment _ TRUE; continueProcessing _ FALSE; RETURN; }; <> IF (handle.sndWL1 - seqNumber < 0 OR handle.sndWL1 = seqNumber AND handle.sndWL2 - ackNumber <= 0) OR (handle.sndWL1 = 0 AND handle.sndWL2 = 0) THEN { <> TRUSTED {handle.sndWnd _ MIN[tcpHdrPtr.window, TCPOps.sendBufferLength]}; handle.sndWL1 _ seqNumber; handle.sndWL2 _ ackNumber; }; IF ackNumber - handle.sndUna <= 0 THEN -- duplicate ack RETURN; -- ignore ack <> nDataBytesAcked _ ackNumber - handle.sndUna; IF handle.sndUna = handle.iss AND nDataBytesAcked # 0 THEN nDataBytesAcked _ nDataBytesAcked - 1; IF (SELECT handle.state FROM finWait1, finWait2, closing, lastAck, timeWait => TRUE ENDCASE => FALSE) AND ackNumber - handle.finSequence >= 0 AND nDataBytesAcked # 0 THEN nDataBytesAcked _ nDataBytesAcked - 1; IF handle.nBytesToSend >= nDataBytesAcked THEN -- Occasional BoundsFault handle.nBytesToSend _ handle.nBytesToSend - nDataBytesAcked; IF repacketizing THEN -- if repacketizing, update send ptr in TCP buffer handle.sendSlot _ (handle.sendSlot + nDataBytesAcked) MOD sendBufferLength; TRUSTED {handle.sndUna _ Flip[tcpHdrPtr.ackNumber]}; -- update ack info in handle TCPTransmit.RemoveAckedSegments[handle]; -- dispose of acked segments or return to user NOTIFY handle.windowAvailable; -- tell waiters that there may be some room now SELECT handle.state FROM synRcvd => { TCPLogging.PrintStateChange[handle, established]; handle.state _ established; IF handle.urgentMode THEN -- if rcvd urgent when in synrcvd state SignalUserUrgent[]; -- then tell user now sendData _ TRUE; }; established => sendData _ TRUE; finWait1 => IF ackNumber - handle.finSequence > 0 THEN {-- if our fin acked, then state is finwait2 TCPLogging.PrintStateChange[handle, finWait2]; handle.state _ finWait2; }; <> closeWait => { continueProcessing _ FALSE; freeSegment _ TRUE; sendData _ TRUE; -- try to send more data }; closing => { IF ackNumber > handle.finSequence THEN { -- if fin acked, state is timewait TCPLogging.PrintStateChange[handle, timeWait]; handle.state _ timeWait; handle.timeWaitTime _ SetTimeout[tcpSegmentLife*1000*2]; -- tcpSegmentLife is in seconds; SetTimeout takes milliseconds; *2 is for round-trip }; continueProcessing _ FALSE; freeSegment _ TRUE; }; lastAck => { IF ackNumber > handle.finSequence THEN { -- close connection if fin acked TCPStates.CloseConnection[handle, handle.reason]; connectionClosed _ TRUE } ELSE freeSegment _ TRUE; continueProcessing _ FALSE } ENDCASE }; -- ProcessAck ProcessSyn: INTERNAL PROC = { SELECT handle.state FROM listen => { TCPLogging.PrintStateChange[handle, synRcvd]; handle.state _ synRcvd; handle.irs _ seqNumber; handle.rcvNxt _ seqNumber + 1; handle.iss _ TCPStates.GetInitialSequenceNumber[]; handle.sndUna _ handle.iss; NOTIFY handle.notListening; handle.matchForeignAddr _ TRUE; handle.matchForeignPort _ TRUE; handle.foreignAddr _ tcpRcvBufferPtr.datagramPtr.inHdr.source; TRUSTED {handle.foreignPort _ tcpHdrPtr.sourcePort}; TCPTransmit.SendSYN[handle]; -- send a syn and ack tcpRcvBufferPtr.dataByteCount _ tcpRcvBufferPtr.dataByteCount - 1; tcpRcvBufferPtr.offsetSeqNo _ tcpRcvBufferPtr.offsetSeqNo + 1; TRUSTED {tcpHdrPtr.syn _ FALSE}; -- don't reprocess syn continueProcessing _ FALSE; -- don't process data or fin until in established state }; synSent => { handle.irs _ seqNumber; -- initial rcv sequence handle.rcvNxt _ seqNumber + 1; tcpRcvBufferPtr.dataByteCount _ tcpRcvBufferPtr.dataByteCount - 1; tcpRcvBufferPtr.offsetSeqNo _ tcpRcvBufferPtr.offsetSeqNo + 1; IF handle.sndUna > handle.iss THEN { -- if our syn was acked then conn. established TCPLogging.PrintStateChange[handle, established]; handle.state _ established; } ELSE { -- if our syn not acked, state becomes synRcvd TCPLogging.PrintStateChange[handle, synRcvd]; handle.state _ synRcvd; continueProcessing _ FALSE; -- wait till in established state }; TRUSTED {tcpHdrPtr.syn _ FALSE}; -- don't reprocess syn sendAck _ TRUE; -- ack the syn received }; synRcvd => { TCPLogging.PrintStateChange[handle, listen]; handle.state _ listen; -- return to listen (why? -DN) continueProcessing _ FALSE; -- stop processing freeSegment _ TRUE; -- dispose of buffer } ENDCASE => { -- in any other state, reset connection TCPStates.CloseConnection[handle, protocolViolation]; connectionClosed _ TRUE; } }; -- ProcessSyn ProcessFin: INTERNAL PROC = { SELECT handle.state FROM synRcvd, established => { TCPLogging.PrintStateChange[handle, closeWait]; handle.state _ closeWait; handle.reason _ remoteClose; }; finWait1 => { TCPLogging.PrintStateChange[handle, closing]; handle.state _ closing; }; finWait2 => { TCPLogging.PrintStateChange[handle, timeWait]; handle.state _ timeWait; handle.timeWaitTime _ SetTimeout[tcpSegmentLife*1000*2]; -- tcpSegmentLife is in seconds; SetTimeout takes milliseconds; *2 is for round-trip }; ENDCASE; NOTIFY handle.dataAvailable; -- tell the user that that data is never coming now. }; -- ProcessFin <<>> <> TRUSTED { tcpHdrPtr _ LOOPHOLE[@rcvdDatagram.data]; ackNumber _ Flip[tcpHdrPtr.ackNumber]; seqNumber _ Flip[tcpHdrPtr.seqNumber]; nSeqBytes _ rcvdDatagram.dataLength - tcpHdrPtr.dataWordOffset * 4; IF ~(handle.state = listen OR handle.state = synSent) THEN { seqResult _ CheckSequenceNumber[seqNumber, nSeqBytes, handle.rcvNxt, handle.rcvWnd]; IF seqResult # okSeq THEN { SELECT seqResult FROM pastSeq => { TCPLogging.PrintMessage["Duplicate packet"]; pktsFromPast _ pktsFromPast + 1; }; futureSeq => { TCPLogging.PrintMessage["Future packet"]; pktsFromFuture _ pktsFromFuture + 1; }; ENDCASE => ERROR; IF ~tcpHdrPtr.rst THEN TCPTransmit.TryToSend[handle]; -- ~reset => send an ack RETURN; }; }; IF tcpHdrPtr.syn THEN nSeqBytes _ nSeqBytes + 1; IF tcpHdrPtr.fin THEN nSeqBytes _ nSeqBytes + 1; <> continueProcessing _ TRUE; -- more info in packet to process freeSegment _ FALSE; -- don't dispose of packet sendAck _ FALSE; -- set to send an ack sendData _ FALSE; -- set to try to send more data connectionClosed _ FALSE; -- set if the connection closes IF tcpHdrPtr.rst THEN { -- if its a reset, process it and exit ProcessReset[]; RETURN; }; IF tcpHdrPtr.ack THEN { -- if its an ack, process it ProcessAck[]; IF connectionClosed THEN RETURN; IF freeSegment OR (nSeqBytes = 0 AND ~tcpHdrPtr.urg) OR ~continueProcessing THEN GOTO SendAndExit; }; IF tcpHdrPtr.urg THEN -- if in state where data is acceptable, process urgent SELECT handle.state FROM synRcvd, established, finWait1, finWait2 => ProcessUrgent[]; ENDCASE => NULL; IF nSeqBytes > handle.rcvWnd THEN { <> <> SIGNAL PacketTooBig; -- HGM want's to look at one TCPLogging.PrintMessage["Packet too big"]; nSeqBytes _ handle.rcvWnd; }; <> tcpRcvBufferPtr _ NEW[TCPRcvBuffer]; -- set up receive info block tcpRcvBufferPtr.datagramPtr _ rcvdDatagram; tcpRcvBufferPtr.dataByteCount _ nSeqBytes; tcpRcvBufferPtr.dataOffset _ tcpHdrPtr.dataWordOffset * 4; tcpRcvBufferPtr.offsetSeqNo _ Flip[tcpHdrPtr.seqNumber]; tcpRcvBufferPtr.tcpHdrPtr _ tcpHdrPtr; QueueRcvdSegment[handle, tcpRcvBufferPtr]; -- put on handle fromNet queue DO <> IF handle.fromNetQueue = NIL THEN GOTO SendAndExit; tcpRcvBufferPtr _ NARROW[handle.fromNetQueue.first]; IF ~(handle.state = listen OR handle.state = synSent) THEN -- if in synced state and IF tcpRcvBufferPtr.offsetSeqNo # handle.rcvNxt THEN -- dont have next seq GOTO SendAndExit ; tcpHdrPtr _ tcpRcvBufferPtr.tcpHdrPtr; ackNumber _ Flip[tcpHdrPtr.ackNumber]; seqNumber _ Flip[tcpHdrPtr.seqNumber]; <> IF tcpHdrPtr.syn THEN { ProcessSyn[]; IF connectionClosed THEN RETURN; IF freeSegment OR tcpRcvBufferPtr.dataByteCount = 0 THEN { DisposeRcvdBuffer[]; IF continueProcessing THEN -- dispose of processed or empty packets LOOP; -- get next packet to process }; IF ~continueProcessing THEN GOTO SendAndExit; }; IF handle.state = listen OR handle.state = synSent THEN {-- can't do anything more in these states DisposeRcvdBuffer[]; GOTO SendAndExit; }; IF ~tcpHdrPtr.ack THEN { -- ignore segments without acks (why? -DN) DisposeRcvdBuffer[]; LOOP; }; -- get next packet to process <> handle.rcvNxt _ handle.rcvNxt + tcpRcvBufferPtr.dataByteCount; IF tcpHdrPtr.fin THEN { -- remember if fin is set as buffer is sent to user finFlag _ TRUE; tcpRcvBufferPtr.dataByteCount _ tcpRcvBufferPtr.dataByteCount - 1; } ELSE finFlag _ FALSE; IF tcpRcvBufferPtr.dataByteCount > 0 THEN { -- if there's data then send it to the user handle.fromNetQueue _ handle.fromNetQueue.rest; SendDataToUser[handle, tcpRcvBufferPtr]; -- send to user and update window sendAck _ TRUE; } -- remember to send an ack ELSE { DisposeRcvdBuffer[]; -- if no data dispose of buffer IF finFlag THEN sendAck _ TRUE; }; <> IF finFlag THEN ProcessFin[]; ENDLOOP; EXITS -- repeat processing each segment received SendAndExit => SELECT TRUE FROM sendAck => TCPTransmit.TryToSend[handle] ;-- send ack and data sendData => TCPTransmit.TryToSendData[handle]; -- send only if data to send ENDCASE; }; }; -- ProcessRcvdSegment CheckSequenceNumber: INTERNAL PROC [seq, segLen, rcvNxt, rcvWnd: INT] RETURNS [result: SeqCode] = { <> rcvEnd: INT _ rcvWnd + rcvNxt; -- rcvwnd is rcvNxt to rcvEnd-1 inclusive segEnd: INT _ seq + segLen - 1; -- segment is seq to segEnd inclusive IF segLen = 0 AND rcvWnd = 0 THEN IF seq = rcvNxt THEN result _ okSeq ELSE IF seq - rcvNxt > 0 THEN result _ futureSeq ELSE result _ pastSeq ELSE IF segLen = 0 AND rcvWnd > 0 THEN IF seq - rcvNxt < 0 THEN result _ pastSeq ELSE IF seq - rcvEnd >= 0 THEN result _ futureSeq ELSE result _ okSeq ELSE IF rcvWnd = 0 THEN IF seq >= rcvNxt THEN result _ futureSeq ELSE result _ pastSeq ELSE IF segEnd < rcvNxt THEN result _ pastSeq ELSE IF seq >= rcvEnd THEN result _ futureSeq ELSE result _ okSeq }; -- CheckSequenceNumber QueueRcvdSegment: INTERNAL PROC [handle: TCPHandle, newBufferPtr: REF TCPRcvBuffer] = { <> newStart: INT; -- first seq number in new segment newEnd: INT; -- last seq number in new segment oldStart: INT; -- first seq number in segment on queue oldEnd: INT; -- last seq number in segment on queue oldBufferPtr: REF TCPRcvBuffer; -- buffer on from net queue l, prevL: LIST OF REF ANY; -- point to the cons cells as we walk the list IF ~(handle.state = listen OR handle.state = synSent) THEN -- if in synced state IF newBufferPtr.offsetSeqNo < handle.rcvNxt THEN { <> newBufferPtr.dataByteCount _ newBufferPtr.dataByteCount - (handle.rcvNxt - newBufferPtr.offsetSeqNo); newBufferPtr.dataOffset _ newBufferPtr.dataOffset + (handle.rcvNxt - newBufferPtr.offsetSeqNo); newBufferPtr.offsetSeqNo _ handle.rcvNxt; }; IF handle.fromNetQueue = NIL THEN { < put new segment at head >> handle.fromNetQueue _ LIST[newBufferPtr]; RETURN; }; prevL _ NIL; l _ handle.fromNetQueue; newStart _ newBufferPtr.offsetSeqNo; newEnd _ newStart + newBufferPtr.dataByteCount - 1; WHILE l # NIL DO oldBufferPtr _ NARROW[l.first]; oldStart _ oldBufferPtr.offsetSeqNo; oldEnd _ oldStart + oldBufferPtr.dataByteCount - 1; SELECT TRUE FROM newStart < oldStart AND newEnd < oldStart => { -- new segment is before old one IF prevL = NIL THEN handle.fromNetQueue _ CONS[newBufferPtr, handle.fromNetQueue] ELSE prevL.rest _ CONS[newBufferPtr, prevL.rest]; RETURN; }; newStart > oldEnd => NULL; -- new segment is after old one, keep going newStart >= oldStart AND newEnd <= oldEnd => { <> pktsDuplicate _ pktsDuplicate + 1; RETURN; }; newStart <= oldStart AND newEnd >= oldEnd => { <> pktsDuplicate _ pktsDuplicate + 1; oldBufferPtr.datagramPtr _ NIL; IF prevL = NIL THEN handle.fromNetQueue _ l _ l.rest ELSE prevL.rest _ l _ l.rest; IF l = NIL THEN { -- if queue is now empty, just enqueue new buffer IF prevL = NIL THEN handle.fromNetQueue _ LIST[newBufferPtr] ELSE prevL.rest _ LIST[newBufferPtr]; RETURN; } ELSE LOOP; }; -- else continue searching queue newEnd < oldEnd => { -- tail of new overlaps old <> newBufferPtr.dataByteCount _ oldStart - newStart; IF prevL = NIL THEN handle.fromNetQueue _ CONS[newBufferPtr, handle.fromNetQueue] ELSE prevL.rest _ CONS[newBufferPtr, prevL.rest]; RETURN }; ENDCASE => { -- head of new overlaps old <> newStart _ oldEnd + 1; newBufferPtr.offsetSeqNo _ newStart; newBufferPtr.dataByteCount _ newEnd - oldEnd; newBufferPtr.dataOffset _ newBufferPtr.dataOffset + oldEnd - newStart + 1; }; prevL _ l; l _ l.rest; ENDLOOP; -- check for more overlapping segments -- IF prevL = NIL THEN handle.fromNetQueue _ LIST[newBufferPtr] ELSE prevL.rest _ LIST[newBufferPtr]; }; -- QueueRcvdSegment <> PacketTooBig: SIGNAL = CODE; NegativeWindow: SIGNAL = CODE; SendDataToUser: INTERNAL PROC [handle: TCPOps.TCPHandle, tcpRcvBufferPtr: REF TCPRcvBuffer] = TRUSTED { <> IF tcpRcvBufferPtr.tcpHdrPtr.urg THEN { tcpRcvBufferPtr.urg _ TRUE; tcpRcvBufferPtr.endUrgentData _ handle.rcvUp - tcpRcvBufferPtr.offsetSeqNo; handle.urgentMode _ FALSE} ELSE tcpRcvBufferPtr.urg _ FALSE; IF tcpRcvBufferPtr.dataByteCount > handle.rcvWnd THEN { <> <> SIGNAL PacketTooBig; -- HGM want's to look at one TCPLogging.PrintMessage["Packet too big."]; tcpRcvBufferPtr.dataByteCount _ handle.rcvWnd; }; handle.rcvWnd _ handle.rcvWnd - tcpRcvBufferPtr.dataByteCount; IF handle.rcvWnd < 0 THEN SIGNAL NegativeWindow; handle.readyToReadQueue _ List.Nconc1[handle.readyToReadQueue, tcpRcvBufferPtr]; NOTIFY handle.dataAvailable; }; END.