Ensure all acks are responded to (Chatbug attempt 2)

If you excuse my garbage meme (I'm just trying to keep my sanity together, just cut me some slack, ok?), this patch adds a bit of robustness to the netcode that (hopefully) allows it to recover in case of a packet that a node didn't register in it's acktosend list.

The way reliable packets works is that it uses a table of packets that have been sent with a unique, incremental number that is used to identify a packet that has been responded to. If the target node sends that same number back at some point, it can be certain that the server has read and processed it, and followup packets can be processed as usual. However, in this process, the node also need to keep track of packets that it has processed, in case it fails to send it's acknowledgement back and the other node ends up resending the packet. This is where the acktosend list comes into play: it lists all packets that it has processed recently, and if a packet already in the list appears there, it knows it has seen it already and can safely ignore it.

Here's where I think it goes wrong: there are two procedures for duplicate packets, one is a sliding window that incrementally goes up to process the last packet, and if an acknowledgement number comes before it, it can be sure it's already been processed. Or, at least, should be, since I can think of one theoretical situation where this is false: out-of-order packets. In that case, the server will still try to respond with an ackreturn for that packet for a quick response, but it actually never adds it to the acktosend table since it has assumed it's already been processed. If this happens before the packet was added to acktosend table, it's possible that it ignores the packet and never send an ack back, locking up the node's ackpak list.

The solution to this is by checking the acktosend list for duplicates first, and if it's not there, proceed to add it in the list even if it's perceived to be a duplicate, to really make sure that the node gets the packet acked. This should hopefully eliminate the chances of a lockup in case a node end up not acking it.

I will try to keep a server up with this patch the follow days while I'm awake to really give this a proper and thorough testing. If you want to join, I made a build of this patch that you can use (make a copy of your 2.2.13 installation first - you might lose data otherwise!): srb2win.zip

src/netcode/d_net.c

@@ -307,6 +307,52 @@ static void RemoveAck(INT32 i)
 		Net_CloseConnection(node);
 }
 
+static void CreateAckpak(node_t *node)
+{
+	UINT8 hm1; // head - 1
+	boolean change = true;
+
+	// Is a good packet so increment the acknowledge number,
+	// Then search for a "hole" in the queue
+	UINT8 nextfirstack = (UINT8)(node->firstacktosend + 1);
+	if (!nextfirstack)
+		nextfirstack = 1;
+
+	node->firstacktosend = nextfirstack++;
+	if (!nextfirstack)
+		nextfirstack = 1;
+	hm1 = (UINT8)((node->acktosend_head-1+MAXACKTOSEND) % MAXACKTOSEND);
+	while (change)
+	{
+		change = false;
+		for (INT32 i = node->acktosend_tail; i != node->acktosend_head;
+			i = (i+1) % MAXACKTOSEND)
+		{
+			if (cmpack(node->acktosend[i], nextfirstack) <= 0)
+			{
+				if (node->acktosend[i] == nextfirstack)
+				{
+					node->firstacktosend = nextfirstack++;
+					if (!nextfirstack)
+						nextfirstack = 1;
+					change = true;
+				}
+				if (i == node->acktosend_tail)
+				{
+					node->acktosend[node->acktosend_tail] = 0;
+					node->acktosend_tail = (UINT8)((i+1) % MAXACKTOSEND);
+				}
+				else if (i == hm1)
+				{
+					node->acktosend[hm1] = 0;
+					node->acktosend_head = hm1;
+					hm1 = (UINT8)((hm1-1+MAXACKTOSEND) % MAXACKTOSEND);
+				}
+			}
+		}
+	}
+}
+
 // We have got a packet, proceed the ack request and ack return
 static int Processackpak(void)
 {
@@ -331,76 +377,38 @@ static int Processackpak(void)
 	{
 		UINT8 ack = netbuffer->ack;
 		getackpacket++;
-		if (cmpack(ack, node->firstacktosend) <= 0)
-		{
-			DEBFILE(va("Discard(1) ack %d (duplicated)\n", ack));
-			duppacket++;
-			goodpacket = 1; // Discard packet (duplicate)
-		}
-		else
-		{
-			// Check if it is not already in the queue
-			for (INT32 i = node->acktosend_tail; i != node->acktosend_head; i = (i+1) % MAXACKTOSEND)
-				if (node->acktosend[i] == ack)
-				{
-					DEBFILE(va("Discard(2) ack %d (duplicated)\n", ack));
-					duppacket++;
-					goodpacket = 1; // Discard packet (duplicate)
-					break;
-				}
-			if (goodpacket == 0)
+		// Check if it is not already in the queue
+		for (INT32 i = node->acktosend_tail; i != node->acktosend_head; i = (i+1) % MAXACKTOSEND)
+			if (node->acktosend[i] == ack)
 			{
-				// Is a good packet so increment the acknowledge number,
-				// Then search for a "hole" in the queue
-				UINT8 nextfirstack = (UINT8)(node->firstacktosend + 1);
-				if (!nextfirstack)
-					nextfirstack = 1;
+				DEBFILE(va("Discard(2) ack %d (duplicated)\n", ack));
+				duppacket++;
+				goodpacket = 1; // Discard packet (duplicate)
+				break;
+			}
 
-				if (ack == nextfirstack)
+		if (goodpacket == 0)
+		{
+			if (cmpack(ack, node->firstacktosend) <= 0)
+			{
+				// even if this is a duplicate packet, register it in acktosend so we can respond to it
+				CreateAckpak(node);
+				DEBFILE(va("Discard(1) ack %d (duplicated)\n", ack));
+				duppacket++;
+				goodpacket = 1; // Discard packet (duplicate)
+			}
+			else
+			{
+				if (ack == node->firstacktosend + 1)
 				{
-					UINT8 hm1; // head - 1
-					boolean change = true;
-
-					node->firstacktosend = nextfirstack++;
-					if (!nextfirstack)
-						nextfirstack = 1;
-					hm1 = (UINT8)((node->acktosend_head-1+MAXACKTOSEND) % MAXACKTOSEND);
-					while (change)
-					{
-						change = false;
-						for (INT32 i = node->acktosend_tail; i != node->acktosend_head;
-							i = (i+1) % MAXACKTOSEND)
-						{
-							if (cmpack(node->acktosend[i], nextfirstack) <= 0)
-							{
-								if (node->acktosend[i] == nextfirstack)
-								{
-									node->firstacktosend = nextfirstack++;
-									if (!nextfirstack)
-										nextfirstack = 1;
-									change = true;
-								}
-								if (i == node->acktosend_tail)
-								{
-									node->acktosend[node->acktosend_tail] = 0;
-									node->acktosend_tail = (UINT8)((i+1) % MAXACKTOSEND);
-								}
-								else if (i == hm1)
-								{
-									node->acktosend[hm1] = 0;
-									node->acktosend_head = hm1;
-									hm1 = (UINT8)((hm1-1+MAXACKTOSEND) % MAXACKTOSEND);
-								}
-							}
-						}
-					}
+					CreateAckpak(node);
 				}
 				else // Out of order packet
 				{
 					// Don't increment firsacktosend, put it in asktosend queue
 					// Will be incremented when the nextfirstack comes (code above)
 					UINT8 newhead = (UINT8)((node->acktosend_head+1) % MAXACKTOSEND);
-					DEBFILE(va("out of order packet (%d expected)\n", nextfirstack));
+					DEBFILE(va("out of order packet (%d expected)\n", node->firstacktosend + 1));
 					if (newhead != node->acktosend_tail)
 					{
 						node->acktosend[node->acktosend_head] = ack;