OpenSolaris_b135/stand/lib/tcp/tcp_sack.c
/*
* 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;
}
}
}