1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License").  You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22/*
23 * Copyright 1997-2003 Sun Microsystems, Inc.  All rights reserved.
24 * Use is subject to license terms.
25 */
26
27#pragma ident	"%Z%%M%	%I%	%E% SMI"
28
29/* Modified to be used by inetboot. */
30
31#include <sys/types.h>
32#include <socket_impl.h>
33#include <sys/debug.h>
34#include <netinet/tcp.h>
35#include <sys/systm.h>
36#include <sys/stropts.h>
37#include <netinet/in.h>
38#include <netinet/ip6.h>
39#include <inet/common.h>
40#include <sys/salib.h>
41#include <sys/socket.h>
42
43#include "tcp_inet.h"
44#include "tcp_sack.h"
45
46/*
47 * To insert a new blk to the array of SACK blk in receiver.
48 *
49 * Parameters:
50 *	sack_blk_t *head: pointer to the array of SACK blks.
51 *	tcp_seq begin: starting seq num of the new blk.
52 *	tcp_seq end: ending seq num of the new blk.
53 *	int32_t *num: (referenced) total num of SACK blks on the list.
54 */
55void
56tcp_sack_insert(sack_blk_t *head, tcp_seq begin, tcp_seq end, int32_t *num)
57{
58	int32_t	i, j, old_num, new_num;
59	sack_blk_t tmp[MAX_SACK_BLK - 1];
60
61	/* The array is empty, just add the new one. */
62	if (*num == 0) {
63		head[0].begin = begin;
64		head[0].end = end;
65		*num = 1;
66		return;
67	}
68
69	/*
70	 * Check for overlap.  There are five cases.
71	 *
72	 * 1. there is no overlap with any other SACK blks.
73	 * 2. new SACK blk is completely contained in another blk.
74	 * 3. tail part of new SACK blk overlaps with another blk.
75	 * 4. head part of new SACK blk overlaps with another blk.
76	 * 5. new SACK blk completely contains another blk.
77	 *
78	 * Use tmp to hold old SACK blks.  After the loop, copy them back
79	 * to head.
80	 */
81	old_num = *num;
82	if (old_num > MAX_SACK_BLK - 1) {
83		old_num = MAX_SACK_BLK - 1;
84	}
85	new_num = old_num;
86	j = 0;
87	for (i = 0; i < old_num; i++) {
88		if (SEQ_LT(end, head[i].begin) || SEQ_GT(begin, head[i].end)) {
89			/* Case 1: continue to check. */
90			tmp[j].begin = head[i].begin;
91			tmp[j].end = head[i].end;
92			j++;
93			continue;
94		} else if (SEQ_GEQ(begin, head[i].begin) &&
95		    SEQ_LEQ(end, head[i].end)) {
96			/* Case 2: re-insert the old blk to the head. */
97			begin = head[i].begin;
98			end = head[i].end;
99		} else if (SEQ_LEQ(end, head[i].end) &&
100		    SEQ_GEQ(end, head[i].begin)) {
101			/*
102			 * Case 3: Extend the new blk, remove the old one
103			 * and continue to check.
104			 */
105			end = head[i].end;
106		} else if (SEQ_GEQ(begin, head[i].begin) &&
107		    SEQ_LEQ(begin, head[i].end)) {
108			/* Case 4 */
109			begin = head[i].begin;
110		}
111		/*
112		 * Common code for all cases except the first one, which
113		 * copies the original SACK blk into the tmp storage.  Other
114		 * cases remove the original SACK blk by not copying into
115		 * tmp storage.
116		 */
117		new_num--;
118	}
119
120	head[0].begin = begin;
121	head[0].end = end;
122	for (i = 0; i < new_num; i++) {
123		head[i+1].begin = tmp[i].begin;
124		head[i+1].end = tmp[i].end;
125	}
126	*num = new_num + 1;
127}
128
129
130/*
131 * To remove a SACK block.
132 *
133 * Parameters:
134 *	sack_blk_t *head: pointer to the array of SACK blks.
135 *	tcp_seq end: to remove all sack blk with seq num less than end.
136 *	int32_t *num: (referenced) total num of SACK blks in the array.
137 */
138void
139tcp_sack_remove(sack_blk_t *head, tcp_seq end, int32_t *num)
140{
141	sack_blk_t tmp[MAX_SACK_BLK];
142	int32_t i, j, old_num, new_num;
143
144	if (*num == 0)
145		return;
146
147	old_num = *num;
148	new_num = old_num;
149	j = 0;
150	/* Walk thru the whole list and copy the new list to tmp[]. */
151	for (i = 0; i < old_num; i++) {
152		if (SEQ_GT(end, head[i].begin)) {
153			/*
154			 * Check to see if the old SACK blk needs to be
155			 * removed or updated.  If the old blk is just
156			 * partially covered, update begin and continue.
157			 * If the old blk is completely covered, remove it
158			 * and continue to check.
159			 */
160			if (SEQ_GEQ(end, head[i].end)) {
161				new_num--;
162				continue;
163			} else {
164				tmp[j].begin = end;
165				tmp[j].end = head[i].end;
166			}
167		} else {
168			tmp[j].begin = head[i].begin;
169			tmp[j].end = head[i].end;
170		}
171		j++;
172	}
173	/* Copy tmp[] back to the original list. */
174	for (i = 0; i < new_num; i++) {
175		head[i].begin = tmp[i].begin;
176		head[i].end = tmp[i].end;
177	}
178	*num = new_num;
179}
180
181
182/*
183 * Use the SACK info to insert a "notsack'ed" blk.  The notsack'ed blk list
184 * contains the list of blks which have not been selectively acknowledged
185 * by the receiver.  The SACK info is a blk which is being selectively
186 * acknowledged by the receiver.
187 *
188 * Parameters:
189 *	notsack_blk_t **head: address of the pointer to the list of notsack'ed
190 *		blks.
191 *	tcp_seq begin: starting seq num of the SACK info.
192 *	tcp_seq end: ending seq num of the SACK info.
193 *	int32_t *num: (referenced) total num of notsack'ed blk on the list.
194 *	uint32_t *sum: (referenced) total num of bytes of all the notsack'ed
195 *		blks.
196 */
197void
198tcp_notsack_insert(notsack_blk_t **head, tcp_seq begin, tcp_seq end,
199    int32_t *num, uint32_t *sum)
200{
201	notsack_blk_t *prev, *tmp, *new;
202	uint32_t tmp_sum, tmp_num;
203
204	if (*head == NULL) {
205		return;
206	}
207
208	tmp = *head;
209	prev = NULL;
210	/* Find the right place of updating the list. */
211	while ((tmp != NULL) && SEQ_LEQ(tmp->end, begin)) {
212		prev = tmp;
213		(tmp->sack_cnt)++;
214		tmp = tmp->next;
215	}
216
217	/*
218	 * This can happen only when TCP sends new data but the notsack list
219	 * is not updated.
220	 */
221	if (tmp == NULL) {
222		return;
223	}
224
225	/*
226	 * This means the new SACK info covers something that is not on
227	 * the list anymore.
228	 */
229	if (SEQ_LEQ(end, tmp->begin)) {
230		return;
231	}
232
233	/* The SACK info covers up to this blk.  So just check for this blk. */
234	if (SEQ_LEQ(end, tmp->end)) {
235		/*
236		 * Only this notsack'ed blk is completely covered.  Delete
237		 * it and return.
238		 */
239		if (end == tmp->end && SEQ_LEQ(begin, tmp->begin)) {
240			if (prev != NULL) {
241				prev->next = tmp->next;
242			} else {
243				*head = tmp->next;
244			}
245			(*num)--;
246			*sum -= tmp->end - tmp->begin;
247			bkmem_free(tmp, sizeof (notsack_blk_t));
248			return;
249		}
250		/* This blk is partially covered. */
251		if (SEQ_GEQ(begin, tmp->begin)) {
252			/* Check what needs to be updated. */
253			if (begin == tmp->begin) {
254				*sum -= end - tmp->begin;
255				tmp->begin = end;
256			} else if (end == tmp->end) {
257				*sum -= tmp->end - begin;
258				tmp->end = begin;
259				(tmp->sack_cnt)++;
260			} else {
261				/* Split the notsack blk. */
262				if ((new = (notsack_blk_t *)bkmem_alloc(
263				    sizeof (notsack_blk_t))) == NULL) {
264					return;
265				}
266				new->end = tmp->end;
267				new->begin = end;
268				new->next = tmp->next;
269				new->sack_cnt = 0;
270				tmp->end = begin;
271				tmp->next = new;
272				(tmp->sack_cnt)++;
273				(*num)++;
274				*sum -= end - begin;
275			}
276		} else {
277			*sum -= end - tmp->begin;
278			tmp->begin = end;
279		}
280		return;
281	}
282
283	/* Need to check for coverage of this blk and later blks. */
284	tmp_sum = *sum;
285	tmp_num = *num;
286	if (SEQ_LT(tmp->begin, begin)) {
287		tmp_sum -= tmp->end - begin;
288		tmp->end = begin;
289		(tmp->sack_cnt)++;
290		prev = tmp;
291		tmp = tmp->next;
292	}
293
294	while (tmp != NULL) {
295		/* The coverage stops here. */
296		if (SEQ_GT(tmp->begin, end)) {
297			break;
298		} else {
299			/* Is the blk completely or partially covered? */
300			if (SEQ_LEQ(tmp->end, end)) {
301				tmp_num--;
302				tmp_sum -= tmp->end - tmp->begin;
303				if (prev != NULL) {
304					prev->next = tmp->next;
305					bkmem_free((caddr_t)tmp,
306					    sizeof (notsack_blk_t));
307					tmp = prev->next;
308				} else {
309					*head = tmp->next;
310					bkmem_free((caddr_t)tmp,
311					    sizeof (notsack_blk_t));
312					tmp = *head;
313				}
314			} else {
315				/*
316				 * This blk is partially covered.  It also
317				 * means it should be the end of coverage.
318				 */
319				tmp_sum -= end - tmp->begin;
320				tmp->begin = end;
321				break;
322			}
323		}
324	}
325	*num = tmp_num;
326	*sum = tmp_sum;
327}
328
329
330/*
331 * To remove notsack'ed blks.
332 *
333 * Parameters:
334 *	notsack_blk_t **head: address of the pointer to the list of notsack'ed
335 *		blks.
336 *	tcp_seq end: to remove all notsack'ed blk with seq num less than end.
337 *	int32_t *num: (referenced) total num of notsack'ed blks.
338 *	uint32_t *sum: (referenced) total num of bytes of all the notsack'ed
339 *		blks.
340 */
341void
342tcp_notsack_remove(notsack_blk_t **head, tcp_seq end, int32_t *num,
343    uint32_t *sum)
344{
345	notsack_blk_t *prev, *tmp;
346	uint32_t tmp_sum = *sum;
347
348	if (*head == NULL)
349		return;
350
351	prev = NULL;
352	tmp = *head;
353	while (tmp != NULL) {
354		/* There is nothing to discard. */
355		if (SEQ_GT(tmp->begin, end)) {
356			break;
357		}
358
359		/* Is the blk completely or partially covered? */
360		if (SEQ_GEQ(end, tmp->end)) {
361			(*num)--;
362			tmp_sum -= tmp->end - tmp->begin;
363			if (prev == NULL) {
364				*head = tmp->next;
365				bkmem_free((caddr_t)tmp,
366				    sizeof (notsack_blk_t));
367				tmp = *head;
368			} else {
369				prev->next = tmp->next;
370				bkmem_free((caddr_t)tmp,
371				    sizeof (notsack_blk_t));
372				tmp = tmp->next;
373			}
374		} else {
375			tmp_sum -= end - tmp->begin;
376			tmp->begin = end;
377			break;
378		}
379	}
380	*sum = tmp_sum;
381}
382
383
384/*
385 * To update the notsack'ed list when new data is sent.
386 *
387 * Assumption: this should only be called when new notsack blk is to be added.
388 *
389 * Parameters:
390 *	notsack_blk_t **head: address of the pointer to the list of notsack'ed
391 *		blks.
392 *	tcp_seq begin: beginning seq num of new data.
393 *	tcp_seq end: ending seq num of new data.
394 *	int32_t *num: (referenced) total num of notsack'ed blks.
395 *	uint32_t *sum: (referenced) total num of bytes of all the notsack'ed
396 *		blks.
397 */
398void tcp_notsack_update(notsack_blk_t **head, tcp_seq begin, tcp_seq end,
399    int32_t *num, uint32_t *sum)
400{
401	notsack_blk_t *tmp;
402
403	tmp = *head;
404	/* If the list is empty, create a new one. */
405	if (tmp == NULL) {
406		if ((tmp = (notsack_blk_t *)bkmem_alloc(
407		    sizeof (notsack_blk_t))) == NULL) {
408			return;
409		}
410		tmp->begin = begin;
411		tmp->end = end;
412		tmp->next = NULL;
413		tmp->sack_cnt = 0;
414		*head = tmp;
415		*num = 1;
416		*sum = end - begin;
417		return;
418	}
419
420	/*
421	 * Find the place to add the new blk.  This assumes that new data
422	 * is being sent, so the place to insert the new notsack blk is at
423	 * the end of the list.
424	 */
425	while (tmp->next != NULL) {
426		tmp = tmp->next;
427	}
428
429	/* Does the new blk overlap with old one? */
430	if (SEQ_GEQ(tmp->end, begin)) {
431		*sum += end - tmp->end;
432		tmp->end = end;
433	} else {
434		/* No.  Need to create a new notsack blk. */
435		tmp->next = (notsack_blk_t *)bkmem_alloc(
436		    sizeof (notsack_blk_t));
437		if (tmp->next != NULL) {
438			tmp = tmp->next;
439			tmp->begin = begin;
440			tmp->end = end;
441			tmp->next = NULL;
442			tmp->sack_cnt = 0;
443			(*num)++;
444			*sum += end - begin;
445		}
446	}
447}
448