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