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