User:Lensovet/cs162
Appearance
Networking
[edit]New Variables
[edit]- Note: A "socket identifier string" is a string that reads "srcport-dstport-dstaddr".
- Kernel Variables
NetKernel.postOffice
: APostOffice
instance that facilitatesPacket
communication.NetKernel.pendingConnects
: AHashMap
that maps local port number integers to anArrayList
of (remote address, remote port) tuples. Entries are added to theHashMap
whenever corresponding SYNPacket
s are received, and this structure is accessed byaccept()
calls to establish connections with remote machines.NetKernel.sendRequests
: ALinkedList
ofSocket
identifier strings, which is populated bywrite()
calls and accessed by the sending thread to determine whichSocket
s to send packets through.NetKernel.unackedPacket
: A class that contains data about packets that have been sent and have yet to be acknowledged. AnunackedPacket
contains aLong
resend time, a local port, a dst port, a dst addr, and a packet sequence number.NetKernel.unackedPackets
: APriorityQueue
ofunackedPackets
, prioritized onunackedPacket.time
. Every time a packet is sent, anunackedPacket
with the corresponding information is added to this global structure.unackedPacket.time
is initialized to thecurrentTime
+ 20,000. The timer thread will send all qualifyingunackedPackets
referenced in this structure. Whenever an ACK is received, we remove the correspondingunackedPacket
entry from the structure.NetKernel.socketHash
: AHashMap
that maps from (local port, dst port, dst addr) toSocket
s.
- Process Variables
NetProcess.descToSocket
: AHashMap
of file descriptor integer to Socket string identifier (local port, dst port, dst addr) mappings. The methodsread()
andwrite()
will access thisHashMap
to determine from whichSocket
to receive and send data.
- Sockets
NetKernel.Socket
: A class that contains socket data. TheNetKernel.socketHash
contains instances of theseSocket
s, mapped by ports and remote addresses. It stores the process ID, a send-data buffer, a receive-data buffer, a receive sliding window, a send sliding window, anint currentSequenceNumber
, and astate enum
.Socket.currentSendSeqNum
: Thisint
is initialized to 1. On sending of aPacket
, thePacket
will be labeled with this integer, and this value will be incremented.Socket.status
: Anenum
that represents the current state of a network connection and dictates what occurs on events. The statuses are the same as those detailed in the Nachos Transport Protocol Specification: CLOSED, SYN_SENT, SYN_RCVD, ESTABLISHED, STP_SENT, STP_RCVD, and CLOSING.Socket.sendBuffer
: On writes, byte data will be queued on thisString
until the sending thread awakens and forms packets out of the data to be sent.Socket.receiveBuffer
: On reads, byte data is returned from thisString
, which is composed of queued data from contiguous blocks ofPacket
s, which are received periodically by the receiving thread.Socket.waitForAccept
: ACondition
variable thatconnect()
sleeps on until the receiving thread wakes it on the reception of a corresponding SYN/ACKPacket
. At that point, theSocket
's state is set to ESTABLISHED.Socket.connectLock
: TheLock
associated withSocket.waitForAccept
.
- Sliding Windows
Socket.receiveSlidingWindow
:- An array that holds 16
Packet
s. This structure keeps track of received packets. Upon packet receipt, the receiving thread addsPacket
s to the array according to their sequence numbers. - All
Packet
are mapped relative to thecurrentLowestReceiveSeqNum
, witharrayIndex = packetSequenceNumber - currentLowestReceiveSeqNum
. - Once there is a contiguous block of
Packet
s starting at the beginning of the array, the receiver thread writes all of data in the contiguous block ofPacket
s to thereceiveBuffer
string. currentLowestReceiveSeqNum
is set to the highest sequence number of the copied block + 1.- The window then "slides" by copying over the remaining
Packet
s to a new array with updated array indices (arrayIndex = packetSequenceNumber - currentLowestReceiveSeqNum
).
- An array that holds 16
Socket.sendSlidingWindow
:- A size 16 array of
<Packet, boolean>
tuples. This structure keeps track ofPacket
s that have not yet been acknowledged. - On the sending of a
Packet
, that packet is added to this array in the same fashion as theSocket.receiveSlidingWindow
. - On reception of an ACK packet, the receiver thread flips the
boolean
of the correspondingPacket
totrue
. - Once there is a contiguous block of acknowledged
Packet
s starting at the beginning of the array,currentLowestSendSeqNum
is set to the highest sequence number of the block + 1. - If any packets are remaining (beyond the contiguous block), they are copied to a new array with their array indices recalculated as for the receiveSlidingWindow.
- An attempt to send
Packet
s with a sequence number exceeding the range of thecurrentLowestSendSeqNum+15
, inclusive, will fail.
- A size 16 array of
Socket.currentLowestSendSeqNum
: Thisint
is initialized to 1. This number indicates at what sequence number the send sliding window begins and limits the range of numberedPacket
s that can be sent.Socket.currentLowestReceiveSeqNum
: Thisint
is initialized to 1. This number indicates at what sequence number the receive sliding window begins and limits the range of numberedPacket
s that can be received.
Implementation Details
[edit]- Note: All packets received that are inappropriate for a particular socket state will be dealt with according to the protocol specification.
- Swap files are uniquely named with the network link address of the Nachos node.
connect()
- Generate random src port. If there is a
Socket
corresponding to the src port, dest address, dest port in theNetKernel.socketHash
which is CLOSED and has an empty read buffer, use it. Otherwise, continue picking random ports until such a socket can be found or no socket for the chosen src port, dest address, dest port exists. In the latter case, create a new Socket object with the appropriate parameters and add it toNetKernel.socketHash
. - Send a SYN packet to the target machine using
PostOffice.send()
, adding it toNetKernel.unackedPackets
, so that the timer thread can automatically resend un-ACK'd SYNs. Set the state of theSocket
to SYN_SENT. - Sleep on the
waitForAccept
in the created/reusedSocket
object. On the reception of a SYN/ACK packet, the receive thread will find the appropriateSocket
fromNetKernel.socketHash
and callwake()
on itswaitForAccept
, at which point theSocket
is switched to the ESTABLISHED state. A new<fileDescriptor, Socket>
mapping will also be added to theNetProcess.descToSocket
accept()
- Upong receipt of SYN
Packet
s, the receive thread stores the request (local address, remote address, and remote port) inNetKernel.pendingConnects
: the local port is mapped to a list of remote addresses/ports. - An
accept()
call searches for a pending request on the requested local port inpendingConnects
. If such a request exists, it is removed fromNetKernel.pendingConnects
. Otherwise,accept()
returns -1. - If a pending connection was found, a new
Socket
is created with its information and is initialized with an ESTABLISHED state. A SYN/ACKPacket
is sent directly usingPostOffice.send()
. A new<fileDescriptor, Socket>
mapping is added to theNetProcess.descToSocket
hash.
write()
NetProcess.descToSocket
is checked to determine if the file descriptor is a Socket, retrieving its identifier (if it is), and adding it to thesendRequests
list.- The write buffer is copied to the
sendBuffer
string andwrite()
returns immediately. The sending thread will take care of the actual communication ofPacket
s. - The following error checks will be performed at the beginning of this method. Failure of these will return -1:
- The
fileDescriptor
maps to aSocket
. - The
Socket
's state is CLOSED or STP_RCVD.
- The
read()
read()
will retrieve theSocket
identifier and then theSocket
from thesocketHash
.- If the
read()
sees that there is some data in thereceiveBuffer
, it will read as much as it can or as much as it has requested. Aread()
is still able to read from a closed socket, as long as the receiveBuffer still contains data. It will return 0 if there was no data available. The receiving thread will take care of actual communication ofPacket
s. - The following error checks will be performed at the beginning of this method. Failure of these will return -1:
- The
fileDescriptor
maps to aSocket
. - The
Socket
is CLOSED. If there is data inreceiveBuffer
, we read it as detailed above.
- The
close()
- Close translates from file descriptor to socket using
descToSocket
. - If the socket is in an ESTABLISHED state, it will check if the send sliding window is currently empty (all packets have been ACK'd).
- If this is true, it will add a FIN packet to the send sliding window, and a reference entry to the FIN packet to the
unackedPackets
structure. Then it will change theSocket
's state to CLOSING. - Otherwise, the send sliding window still has unacked packets, so
close()
will send a STP packet usingPostOffice.send()
and switch theSocket
's state to STP_SENT. - On the reception of more data packets by the receiving thread, if the
Socket
is in the STP_SENT state, we retransmit a STP packet. Once all packets have been ACK'd in the send sliding window, if we are in the STP_SENT state, we proceed to the FIN state as detailed earlier. - On the reception of a STP packet, if a
Socket
is in the ESTABLISHED state, we remove all packets from the send sliding window and theunackedPackets
structure and change the state to STP_RCVD. - On the reception of a FIN packet in the STP_RCVD state, we send a FIN/ACK packet and go to the CLOSED state. The
Socket
that receives a FIN/ACK packet in the CLOSING state will also go to the CLOSED state. - When a
Socket
is in the CLOSED state,write()
calls will not be possible, butread()
calls are possible as long asreadBuffer
still contains data. - If there is no more data in the
receiveBuffer
of aSocket
, we remove the file descriptor mapping fromdescToSocket
.
Permanent threads
[edit]- Sending Thread
- Takes a socket identifier from
NetKernel.sendRequests
and verifies that the correspondingSocket
is not CLOSED and that itssendSlidingWindow
can accommodate morePacket
s. - If these conditions are not fulfilled, the socket identifier is put back onto
NetKernel.sendRequests
and the thread will work on another request.- If these conditions are fulfilled, it removes
packetSize
amount of bytes from thesendBuffer
of the chosen socket and creates a data packet out of those bytes. AMailMessage
is then created with the appropriate addressing information and sent usingPostOffice.send()
. ThePacket
is also added to thesendSlidingWindow
at the appropriate index based on its sequence number.
- If these conditions are fulfilled, it removes
- This process is repeated until the chosen socket's sending window is filled, at which point the sending thread moves on to another request.
- Receiving Thread
- The receiving thread executes the actual reception and interpretation of data packets. It replaces the receiveInterrupt of the postOffice class. On reception of a packet, it verifies to which socket the packet is bound.
- It then verifies that the
Socket
is not CLOSED and that the receive sliding window can accommodate morePacket
s. If the conditions are not fulfilled, the packet is dropped. Otherwise, if thePacket
received is a data packet and theSocket
is in a valid state, thePacket
is placed at the appropriate index of the sliding window. - A corresponding ACK
Packet
is sent directly withPostOffice.send()
. - We continue to receive
Packet
s in this manner until thereceiveSlidingWindow
is filled or we drop aPacket
. - If at any time the sliding window has a contiguous block of
Packet
s starting at index 0, we flush the data of thosePacket
s into theSocket
’sreceiveBuffer
. - On the reception of specialized
Packet
s, we follow the Nachos protocol specification and modify theSocket
state accordingly.- On reception of ACK-type
Packet
s, the correspondingPacket
in thesendSlidingWindow
is marked as ACK’d and the sliding window is adjusted accordingly. - On the reception of a SYN/ACK packet by the receive thread, the Socket will be found using information from the packet and wake() will be called on Socket.waitForAccept, at which point the Socket is switched to the ESTABLISHED state.
- On reception of ACK-type
- Timer Thread
- When the NetKernel initializes, it forks a Timer Thread that runs continuously.
- The timer thread peeks at the top of the
unackedPackets
structure and verifies if thecurrentTime >= unackedPacket.time
. If this is true, resend thePacket
using information from theSocket
corresponding to theunackedPacket
. - Removethe
unackedPacket
off the top ofunackedPackets
and add theunackedPacket
entry back onto the structure with a newcurrentTime + 20,000
value. - The timer thread will keep resending
Packet
s as long as entries fulfill thecurrentTime >= entryTime
condition. Otherwise it will go to sleep.
Pseudocode
[edit]connect(host, port) { do { generate random src port if (src port, dest addr, dest port do not exist in socketHash) { create newSocket; add newSocket to socketHash; break; } if (src port, dest addr, dest port refers to a closed, fully-read socket){ newSocket = existingSocket; break; } } while (true); newSocket.state = SYN_SENT; send SYN packet and add packet information to unackedPackets and sendSlidingWindow; sleep on newSocket.waitForAccept, wait for receiving thread to wake on reception of a SYN/ACK; newSocket.state = ESTABLISHED; add fileDesc, socket mapping to descToSocket; return fileDesc; }
accept(port) { if port in keys of pendingConnects { remove one (addr,port) tuple from associated list } else { return -1; } create newSocket; newSocket.state = ESTABLISHED; send SYN/ACK packet; add new <fileDescriptor, Socket> mapping to descToSocket; return fileDescriptor; }
write() { //only networking code is shown translate from fileDesc to socket identifier using descToSocket; add socket identifier to sendRequests list; copy all data from src buffer to socket's sendBuffer string; return bytes written; // the sending thread deals with actual packet communication }
send() { //"Sending Thread" while (true) { pop sendRequests; if (socket is not CLOSED && sendSlidingWindow is open) { while (sendSlidingWindow is open) { remove packetSize bytes from socket.sendBuffer; create a packet with that data; postOffice.send(packet); add packet to sendSlidingWindow; } } else continue; } }
read() { translate from fileDesc to socket identifier using descToSocket; if (socket is closed) { if (socket still has data to be read) { read available data from socket.receiveBuffer; return bytes read; } else { return -1; } } else { read as much as needed from socket.receiveBuffer; return bytes read; //receive thread takes care of actual packet communication. } }
receive() { //"Receiving Thread" while(true){ packet = postOffice.receive(); if (packet is ACK type) { mark corresponding packet in sendSlidingWindow as ACK; adjust sendSlidingWindow accordingly; } socket = get socket from socketHash with info from packet; if (packet is SYN/ACK type) { socket.waitForAccept.wake(); socket.state = ESTABLISHED; } if (socket is not CLOSED && receiveSlidingWindow is open) { if (packet is data packet && socket.state is valid) put packet at appropriate index of receiveSlidingWindow PostOffice.send(ACK packet); } else { drop packet; break; } if (receiveSlidingWindow is full) { break; } packetsToFlush = []; for (index i of receiveSlidingWindow starting at 0) { if (receiveSlidingWindow[i] has packet) { add packet to packetsToFlush; remove packet from receiveSlidingWindow; } else { break; } } } }
timer() { unackedP = unackedPackets.peek(); while (currentTime >= unackedP.time) { resend unackedP.packet; unackedP = unackedPackets.pop(); put unackedP in unackedPackets with time = currentTime + 20000; unackedP = unackedPackets.peek(); } sleep(); }
close(fileDescriptor) { get Socket s with given fileDescriptor from descToSocket; if (s.state == ESTABLISHED) { if (s.sendSlidingWindow is empty) { add FIN packet to s.sendSlidingWindow; add reference to FIN packet to unackedPackets; s.state = CLOSING; } else { send STP packet with PostOffice.send(); s.state = STP_SENT; } } else if (s.state == STP_RCVD) { send FIN packet to s.sendSlidingWindow; add reference to FIN packet to unackedPackets; s.state = CLOSING; } else { return -1; } return 0; }
Testing
[edit]- Connection
- Set up two Nachos nodes, named A and B:
- Have A connect and B accept on the same port and verify that a connection has been made with print statements on the information from the two newly created sockets.
- Attempt two connects from A with only 1 accept from B on the same port, verify that only one new socket is created on B, but it has a record of the second connect. A subsequent accept should create a new connection with the 2nd connect from A.
- Create a successful connection between A and B, and close the connection. Verify that both socket states are closed.
- After closing, verify that creation of a connection with the same port and addressing information is successful. Also verify that this same test correctly fails if there is still data to be read from the port.
- Create a connection from Port 1 to Port 2. Create a second connection from Port 3 to Port 1.
- Verify that both connections work properly with print statements.
- Verify the reads and writes succeed from Ports 1 and 2 and Ports 1 and 3.
- Reading and Writing
- Set up two Nachos nodes, named A and B:
- Have A run a program that writes a large amount of text to B. Have B run a program that reads text from the same port and verify that the text is the same sent from A.
- With A and B connected, have A call write three times and have B call read only once. Close A.
- Verify that the connection between A and B is dead.
- Verify that writes from B to A will fail.
- Verify that two more reads from B with retrieve the last two messages sent by A.
- Verify that a subsequent read from B will fail.
Chat Program
[edit]Implementation
[edit]New Variables
[edit]chatserver.ClientList
: A struct containing anint fileDescriptor
, a byte arraybyte *partialBuffer
, and anint bufferLen
. Each struct also contains a pointer to the next client. Each server node thus contains a linked list of clients.chatserver.currentClient
: AClient
pointer to the nextClient
from which to read input.chatserver.MAX_LINE_SIZE
: Anint
that determines the maximum size of a line.chat.fileDescriptor
: Anint fileDescriptor
that stores thefileDescriptor
returned byconnect()
.chat.MAX_LINE_SIZE
: Anint
that determines the maximum size of a line.
Implementation Details
[edit]- The main method in
chatserver.c
initializes a byte arraytmp
of lengthMAX_LINE_SIZE
. It then runs a continuous while loop and performs the following actions:- It checks for standard input. If there is standard input, the method breaks from the while loop and exits.
- It calls
accept
on port 15. If there is a chat client waiting to establish a connection, a newClient
node is created with the returnedfileDescriptor
and a new byte array initialized to size 1000. This new client is added to theClientList
. - For each client in the
ClientList
,chatserver
does the following:- It reads up to
MAX_LINE_SIZE
fromcurrentClient.socket
into buffertmp
. - It appends the data in
tmp
tocurrentClient.buffer
- It reads from
currentClient.buffer
. If this read returns -1, we disconnect. Otherwise, we add the returned value tocurrentClient.bufferLen
. - While
currentClient.buffer
contains a newline, it does as follows:- It copies
currentClient.buffer
up to the newline intotmp
. - It moves the rest of the data in
currentclient.buffer
up by however many bytes were copied, subtracting this number fromcurrentClient.bufferLen
. - Finally, for each client in the
ClientList
, it sends out the contents oftmp
.
- It copies
- It reads up to
- Disconnects are handled by catching -1 return values on reads and writes. Since the client has called close() prior to the disconnect, the socket on the server side should reflect the closing of the connection. When a read or write failure occurs, we remove that particular client from the client list.
- The main method in
chat.c
first initializes three byte arrays:currentMsg
,tmp
, andserver
. All these arrays are of lengthMAX_LINE_SIZE
. It then callsconnect()
. It runs a continuous while loop and performs the following actions:- It reads standard input of length
MAX_LINE_SIZE - length of currentMsg
intocurrentMsg
. - If
currentMsg
is not empty, it runs the following while loop on the condition thatcurrentMsg
contains a newline:- It copies the data in
currentMsg
up to the first newline character intotmp
. - If the contents of
tmp
is ".", it callsclose()
and breaks out of the while loop, ending this user's chat session. - It moves the rest of the data in
currentMsg
up by however many bytes were copied. - Then it write the contents of
tmp
to the server.
- It copies the data in
- If
currentMsg
is empty, it reads from client's socket intoserver
a length ofMAX_LINE_SIZE - length of server
byte, before running a while loop on the condition thatserver
contains a newline:- It copies the data in
server
up to the first newline character intotmp
. - It moves the rest of the data in
server
up by however many bytes were copied. - Finally, it prints the contents of
tmp
.
- It copies the data in
- It reads standard input of length
Pseudocode
[edit]chatserver.main() { byte tmp[MAX_LINE_SIZE]; while (true) { if there is standard input { break; } if (newClient = accept(15)) add newClient to clientList; for (currentClient in clientList) { read up to MAX_LINE_SIZE from currentClient.socket into tmp; append the data in tmp to currentClient's buffer currentClient.bufferLen += read(currentClient.socket, currentClient.buffer + currentClient.bufferLen, MAX_LINE_SIZE - currentClient.bufferLen) while (currentClient.buffer contains a newline) { copy currentClient.buffer up to newline into tmp; move the rest of currentClient.buffer left by however many bytes were copied; currentClient.bufferLen -= bytes copied; for (client in clientList) { clientList.socket.write(tmp); } } } } }
chat.main(int addr) { byte currentMsg[MAX_LINE_SIZE], tmp[MAX_LINE_SIZE], server[MAX_LINE_SIZE]; socket = connect(addr, 15); while (true) { read(stdin, currentMsg + length of currentMsg, MAX_LINE_SIZE - length of currentMsg) if (currentMsg is not empty) { while (currentMsg contains a newline) { copy currentMsg up to newline into tmp; if (tmp == ".") { close(); break; } move the rest of currentMsg left by however many bytes were copied; socket.write(tmp); } } else { read(socket, server + length of server, MAX_LINE_SIZE - length of server) while (server contains a newline) { copy server up to newline into tmp; move the rest of server left by however many bytes were copied; print(tmp); } } } }
Test cases
[edit]- Two users:
- One instance of Nachos runs chatserver.c, while Users A and B run chat.c on other separate instances.
- Have A send a message and confirm that both A and B receive the same message from the server.
- Have B send a message and confirm that both A and B receive the same message from the server.
- Three users:
- One instance of Nachos runs chatserver.c, while Users A, B, and C run chat.c on other separate instances.
- Execute the same tests used in the situation with two users.
- Have A send 2 messages, B send 1, and C send 2. Verify that all these messages are received by all chat clients. The two messages from both A and C should have been received in the order they were sent by their respective users.
- Have C disconnect from the chat server, then reconnect. Verify that C can still receive and send messages to A and B as before.
- Four or more users:
- Perform the same tests used for three users.
- Run tests with more messages and more complex ordering of sent messages.
- Have users connect to the server after the chat session has already begun and verify that they can interact with the other users normally.
- Have various users disconnect and reconnect to the server and verify that they can still interact with the other users as before.