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 */
55 void
tcp_sack_insert(sack_blk_t * head,tcp_seq begin,tcp_seq end,int32_t * num)56 tcp_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 */
138 void
tcp_sack_remove(sack_blk_t * head,tcp_seq end,int32_t * num)139 tcp_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 */
197 void
tcp_notsack_insert(notsack_blk_t ** head,tcp_seq begin,tcp_seq end,int32_t * num,uint32_t * sum)198 tcp_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 */
341 void
tcp_notsack_remove(notsack_blk_t ** head,tcp_seq end,int32_t * num,uint32_t * sum)342 tcp_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 */
tcp_notsack_update(notsack_blk_t ** head,tcp_seq begin,tcp_seq end,int32_t * num,uint32_t * sum)398 void 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