text: /*
   * 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;
  		}
  	}
  }
  