OpenSolaris Launch

1 files changed, 447 insertions, 0 deletions

diff --git a/usr/src/stand/lib/tcp/tcp_sack.c b/usr/src/stand/lib/tcp/tcp_sack.c
new file mode 100644
index 0000000000..d1af003110
--- /dev/null
+++ b/usr/src/stand/lib/tcp/tcp_sack.c
@@ -0,0 +1,447 @@
+/*
+ * CDDL HEADER START
+ *
+ * The contents of this file are subject to the terms of the
+ * Common Development and Distribution License, Version 1.0 only
+ * (the "License").  You may not use this file except in compliance
+ * with the License.
+ *
+ * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+ * or http://www.opensolaris.org/os/licensing.
+ * See the License for the specific language governing permissions
+ * and limitations under the License.
+ *
+ * When distributing Covered Code, include this CDDL HEADER in each
+ * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+ * If applicable, add the following below this CDDL HEADER, with the
+ * fields enclosed by brackets "[]" replaced with your own identifying
+ * information: Portions Copyright [yyyy] [name of copyright owner]
+ *
+ * CDDL HEADER END
+ */
+/*
+ * Copyright 1997-2003 Sun Microsystems, Inc.  All rights reserved.
+ * Use is subject to license terms.
+ */
+
+#pragma ident	"%Z%%M%	%I%	%E% SMI"
+
+/* Modified to be used by inetboot. */
+
+#include <sys/types.h>
+#include <socket_impl.h>
+#include <sys/debug.h>
+#include <netinet/tcp.h>
+#include <sys/systm.h>
+#include <sys/stropts.h>
+#include <netinet/in.h>
+#include <netinet/ip6.h>
+#include <inet/common.h>
+#include <sys/salib.h>
+#include <sys/socket.h>
+
+#include "tcp_inet.h"
+#include "tcp_sack.h"
+
+/*
+ * To insert a new blk to the array of SACK blk in receiver.
+ *
+ * Parameters:
+ *	sack_blk_t *head: pointer to the array of SACK blks.
+ *	tcp_seq begin: starting seq num of the new blk.
+ *	tcp_seq end: ending seq num of the new blk.
+ *	int32_t *num: (referenced) total num of SACK blks on the list.
+ */
+void
+tcp_sack_insert(sack_blk_t *head, tcp_seq begin, tcp_seq end, int32_t *num)
+{
+	int32_t	i, j, old_num, new_num;
+	sack_blk_t tmp[MAX_SACK_BLK - 1];
+
+	/* The array is empty, just add the new one. */
+	if (*num == 0) {
+		head[0].begin = begin;
+		head[0].end = end;
+		*num = 1;
+		return;
+	}
+
+	/*
+	 * Check for overlap.  There are five cases.
+	 *
+	 * 1. there is no overlap with any other SACK blks.
+	 * 2. new SACK blk is completely contained in another blk.
+	 * 3. tail part of new SACK blk overlaps with another blk.
+	 * 4. head part of new SACK blk overlaps with another blk.
+	 * 5. new SACK blk completely contains another blk.
+	 *
+	 * Use tmp to hold old SACK blks.  After the loop, copy them back
+	 * to head.
+	 */
+	old_num = *num;
+	if (old_num > MAX_SACK_BLK - 1) {
+		old_num = MAX_SACK_BLK - 1;
+	}
+	new_num = old_num;
+	j = 0;
+	for (i = 0; i < old_num; i++) {
+		if (SEQ_LT(end, head[i].begin) || SEQ_GT(begin, head[i].end)) {
+			/* Case 1: continue to check. */
+			tmp[j].begin = head[i].begin;
+			tmp[j].end = head[i].end;
+			j++;
+			continue;
+		} else if (SEQ_GEQ(begin, head[i].begin) &&
+		    SEQ_LEQ(end, head[i].end)) {
+			/* Case 2: re-insert the old blk to the head. */
+			begin = head[i].begin;
+			end = head[i].end;
+		} else if (SEQ_LEQ(end, head[i].end) &&
+		    SEQ_GEQ(end, head[i].begin)) {
+			/*
+			 * Case 3: Extend the new blk, remove the old one
+			 * and continue to check.
+			 */
+			end = head[i].end;
+		} else if (SEQ_GEQ(begin, head[i].begin) &&
+		    SEQ_LEQ(begin, head[i].end)) {
+			/* Case 4 */
+			begin = head[i].begin;
+		}
+		/*
+		 * Common code for all cases except the first one, which
+		 * copies the original SACK blk into the tmp storage.  Other
+		 * cases remove the original SACK blk by not copying into
+		 * tmp storage.
+		 */
+		new_num--;
+	}
+
+	head[0].begin = begin;
+	head[0].end = end;
+	for (i = 0; i < new_num; i++) {
+		head[i+1].begin = tmp[i].begin;
+		head[i+1].end = tmp[i].end;
+	}
+	*num = new_num + 1;
+}
+
+
+/*
+ * To remove a SACK block.
+ *
+ * Parameters:
+ *	sack_blk_t *head: pointer to the array of SACK blks.
+ *	tcp_seq end: to remove all sack blk with seq num less than end.
+ *	int32_t *num: (referenced) total num of SACK blks in the array.
+ */
+void
+tcp_sack_remove(sack_blk_t *head, tcp_seq end, int32_t *num)
+{
+	sack_blk_t tmp[MAX_SACK_BLK];
+	int32_t i, j, old_num, new_num;
+
+	if (*num == 0)
+		return;
+
+	old_num = *num;
+	new_num = old_num;
+	j = 0;
+	/* Walk thru the whole list and copy the new list to tmp[]. */
+	for (i = 0; i < old_num; i++) {
+		if (SEQ_GT(end, head[i].begin)) {
+			/*
+			 * Check to see if the old SACK blk needs to be
+			 * removed or updated.  If the old blk is just
+			 * partially covered, update begin and continue.
+			 * If the old blk is completely covered, remove it
+			 * and continue to check.
+			 */
+			if (SEQ_GEQ(end, head[i].end)) {
+				new_num--;
+				continue;
+			} else {
+				tmp[j].begin = end;
+				tmp[j].end = head[i].end;
+			}
+		} else {
+			tmp[j].begin = head[i].begin;
+			tmp[j].end = head[i].end;
+		}
+		j++;
+	}
+	/* Copy tmp[] back to the original list. */
+	for (i = 0; i < new_num; i++) {
+		head[i].begin = tmp[i].begin;
+		head[i].end = tmp[i].end;
+	}
+	*num = new_num;
+}
+
+
+/*
+ * Use the SACK info to insert a "notsack'ed" blk.  The notsack'ed blk list
+ * contains the list of blks which have not been selectively acknowledged
+ * by the receiver.  The SACK info is a blk which is being selectively
+ * acknowledged by the receiver.
+ *
+ * Parameters:
+ *	notsack_blk_t **head: address of the pointer to the list of notsack'ed
+ *		blks.
+ *	tcp_seq begin: starting seq num of the SACK info.
+ *	tcp_seq end: ending seq num of the SACK info.
+ *	int32_t *num: (referenced) total num of notsack'ed blk on the list.
+ *	uint32_t *sum: (referenced) total num of bytes of all the notsack'ed
+ *		blks.
+ */
+void
+tcp_notsack_insert(notsack_blk_t **head, tcp_seq begin, tcp_seq end,
+    int32_t *num, uint32_t *sum)
+{
+	notsack_blk_t *prev, *tmp, *new;
+	uint32_t tmp_sum, tmp_num;
+
+	if (*head == NULL) {
+		return;
+	}
+
+	tmp = *head;
+	prev = NULL;
+	/* Find the right place of updating the list. */
+	while ((tmp != NULL) && SEQ_LEQ(tmp->end, begin)) {
+		prev = tmp;
+		(tmp->sack_cnt)++;
+		tmp = tmp->next;
+	}
+
+	/*
+	 * This can happen only when TCP sends new data but the notsack list
+	 * is not updated.
+	 */
+	if (tmp == NULL) {
+		return;
+	}
+
+	/*
+	 * This means the new SACK info covers something that is not on
+	 * the list anymore.
+	 */
+	if (SEQ_LEQ(end, tmp->begin)) {
+		return;
+	}
+
+	/* The SACK info covers up to this blk.  So just check for this blk. */
+	if (SEQ_LEQ(end, tmp->end)) {
+		/*
+		 * Only this notsack'ed blk is completely covered.  Delete
+		 * it and return.
+		 */
+		if (end == tmp->end && SEQ_LEQ(begin, tmp->begin)) {
+			if (prev != NULL) {
+				prev->next = tmp->next;
+			} else {
+				*head = tmp->next;
+			}
+			(*num)--;
+			*sum -= tmp->end - tmp->begin;
+			bkmem_free(tmp, sizeof (notsack_blk_t));
+			return;
+		}
+		/* This blk is partially covered. */
+		if (SEQ_GEQ(begin, tmp->begin)) {
+			/* Check what needs to be updated. */
+			if (begin == tmp->begin) {
+				*sum -= end - tmp->begin;
+				tmp->begin = end;
+			} else if (end == tmp->end) {
+				*sum -= tmp->end - begin;
+				tmp->end = begin;
+				(tmp->sack_cnt)++;
+			} else {
+				/* Split the notsack blk. */
+				if ((new = (notsack_blk_t *)bkmem_alloc(
+				    sizeof (notsack_blk_t))) == NULL) {
+					return;
+				}
+				new->end = tmp->end;
+				new->begin = end;
+				new->next = tmp->next;
+				new->sack_cnt = 0;
+				tmp->end = begin;
+				tmp->next = new;
+				(tmp->sack_cnt)++;
+				(*num)++;
+				*sum -= end - begin;
+			}
+		} else {
+			*sum -= end - tmp->begin;
+			tmp->begin = end;
+		}
+		return;
+	}
+
+	/* Need to check for coverage of this blk and later blks. */
+	tmp_sum = *sum;
+	tmp_num = *num;
+	if (SEQ_LT(tmp->begin, begin)) {
+		tmp_sum -= tmp->end - begin;
+		tmp->end = begin;
+		(tmp->sack_cnt)++;
+		prev = tmp;
+		tmp = tmp->next;
+	}
+
+	while (tmp != NULL) {
+		/* The coverage stops here. */
+		if (SEQ_GT(tmp->begin, end)) {
+			break;
+		} else {
+			/* Is the blk completely or partially covered? */
+			if (SEQ_LEQ(tmp->end, end)) {
+				tmp_num--;
+				tmp_sum -= tmp->end - tmp->begin;
+				if (prev != NULL) {
+					prev->next = tmp->next;
+					bkmem_free((caddr_t)tmp,
+					    sizeof (notsack_blk_t));
+					tmp = prev->next;
+				} else {
+					*head = tmp->next;
+					bkmem_free((caddr_t)tmp,
+					    sizeof (notsack_blk_t));
+					tmp = *head;
+				}
+			} else {
+				/*
+				 * This blk is partially covered.  It also
+				 * means it should be the end of coverage.
+				 */
+				tmp_sum -= end - tmp->begin;
+				tmp->begin = end;
+				break;
+			}
+		}
+	}
+	*num = tmp_num;
+	*sum = tmp_sum;
+}
+
+
+/*
+ * To remove notsack'ed blks.
+ *
+ * Parameters:
+ *	notsack_blk_t **head: address of the pointer to the list of notsack'ed
+ *		blks.
+ *	tcp_seq end: to remove all notsack'ed blk with seq num less than end.
+ *	int32_t *num: (referenced) total num of notsack'ed blks.
+ *	uint32_t *sum: (referenced) total num of bytes of all the notsack'ed
+ *		blks.
+ */
+void
+tcp_notsack_remove(notsack_blk_t **head, tcp_seq end, int32_t *num,
+    uint32_t *sum)
+{
+	notsack_blk_t *prev, *tmp;
+	uint32_t tmp_sum = *sum;
+
+	if (*head == NULL)
+		return;
+
+	prev = NULL;
+	tmp = *head;
+	while (tmp != NULL) {
+		/* There is nothing to discard. */
+		if (SEQ_GT(tmp->begin, end)) {
+			break;
+		}
+
+		/* Is the blk completely or partially covered? */
+		if (SEQ_GEQ(end, tmp->end)) {
+			(*num)--;
+			tmp_sum -= tmp->end - tmp->begin;
+			if (prev == NULL) {
+				*head = tmp->next;
+				bkmem_free((caddr_t)tmp,
+				    sizeof (notsack_blk_t));
+				tmp = *head;
+			} else {
+				prev->next = tmp->next;
+				bkmem_free((caddr_t)tmp,
+				    sizeof (notsack_blk_t));
+				tmp = tmp->next;
+			}
+		} else {
+			tmp_sum -= end - tmp->begin;
+			tmp->begin = end;
+			break;
+		}
+	}
+	*sum = tmp_sum;
+}
+
+
+/*
+ * To update the notsack'ed list when new data is sent.
+ *
+ * Assumption: this should only be called when new notsack blk is to be added.
+ *
+ * Parameters:
+ *	notsack_blk_t **head: address of the pointer to the list of notsack'ed
+ *		blks.
+ *	tcp_seq begin: beginning seq num of new data.
+ *	tcp_seq end: ending seq num of new data.
+ *	int32_t *num: (referenced) total num of notsack'ed blks.
+ *	uint32_t *sum: (referenced) total num of bytes of all the notsack'ed
+ *		blks.
+ */
+void tcp_notsack_update(notsack_blk_t **head, tcp_seq begin, tcp_seq end,
+    int32_t *num, uint32_t *sum)
+{
+	notsack_blk_t *tmp;
+
+	tmp = *head;
+	/* If the list is empty, create a new one. */
+	if (tmp == NULL) {
+		if ((tmp = (notsack_blk_t *)bkmem_alloc(
+		    sizeof (notsack_blk_t))) == NULL) {
+			return;
+		}
+		tmp->begin = begin;
+		tmp->end = end;
+		tmp->next = NULL;
+		tmp->sack_cnt = 0;
+		*head = tmp;
+		*num = 1;
+		*sum = end - begin;
+		return;
+	}
+
+	/*
+	 * Find the place to add the new blk.  This assumes that new data
+	 * is being sent, so the place to insert the new notsack blk is at
+	 * the end of the list.
+	 */
+	while (tmp->next != NULL) {
+		tmp = tmp->next;
+	}
+
+	/* Does the new blk overlap with old one? */
+	if (SEQ_GEQ(tmp->end, begin)) {
+		*sum += end - tmp->end;
+		tmp->end = end;
+	} else {
+		/* No.  Need to create a new notsack blk. */
+		tmp->next = (notsack_blk_t *)bkmem_alloc(
+		    sizeof (notsack_blk_t));
+		if (tmp->next != NULL) {
+			tmp = tmp->next;
+			tmp->begin = begin;
+			tmp->end = end;
+			tmp->next = NULL;
+			tmp->sack_cnt = 0;
+			(*num)++;
+			*sum += end - begin;
+		}
+	}
+}