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 */
38 kmem_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 */
49 void
tcp_sack_insert(sack_blk_t * head,tcp_seq begin,tcp_seq end,int32_t * num)50 tcp_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 */
132 void
tcp_sack_remove(sack_blk_t * head,tcp_seq end,int32_t * num)133 tcp_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 */
191 void
tcp_notsack_insert(notsack_blk_t ** head,tcp_seq begin,tcp_seq end,int32_t * num,uint32_t * sum)192 tcp_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 */
336 void
tcp_notsack_remove(notsack_blk_t ** head,tcp_seq end,int32_t * num,uint32_t * sum)337 tcp_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 */
tcp_notsack_update(notsack_blk_t ** head,tcp_seq begin,tcp_seq end,int32_t * num,uint32_t * sum)391 void 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