1 /*
2 * Copyright (c) 2012-2021 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28
29 /*-
30 * Copyright (c) 2008 Joerg Sonnenberger <[email protected]>.
31 * All rights reserved.
32 *
33 * Redistribution and use in source and binary forms, with or without
34 * modification, are permitted provided that the following conditions
35 * are met:
36 *
37 * 1. Redistributions of source code must retain the above copyright
38 * notice, this list of conditions and the following disclaimer.
39 * 2. Redistributions in binary form must reproduce the above copyright
40 * notice, this list of conditions and the following disclaimer in
41 * the documentation and/or other materials provided with the
42 * distribution.
43 *
44 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
45 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
46 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
47 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
48 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
49 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
50 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
51 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
52 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
53 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
54 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
55 * SUCH DAMAGE.
56 */
57
58 #ifdef KERNEL
59 #include <sys/param.h>
60 #include <machine/endian.h>
61 #include <sys/mcache.h>
62 #include <sys/mbuf.h>
63 #include <kern/debug.h>
64 #include <libkern/libkern.h>
65 #include <mach/boolean.h>
66 #include <pexpert/pexpert.h>
67 #define CKSUM_ERR(fmt, args...) kprintf(fmt, ## args)
68 #else /* !KERNEL */
69 #ifndef LIBSYSCALL_INTERFACE
70 #error "LIBSYSCALL_INTERFACE not defined"
71 #endif /* !LIBSYSCALL_INTERFACE */
72 #include <stdlib.h>
73 #include <stddef.h>
74 #include <stdint.h>
75 #include <unistd.h>
76 #include <strings.h>
77 #include <mach/boolean.h>
78 #include <skywalk/os_skywalk_private.h>
79 #define CKSUM_ERR(fmt, args...) fprintf_stderr(fmt, ## args)
80 #endif /* !KERNEL */
81
82 /* compile time assert */
83 #ifndef _CASSERT
84 #define _CASSERT(x) _Static_assert(x, "compile-time assertion failed")
85 #endif /* !_CASSERT */
86
87 #ifndef VERIFY
88 #define VERIFY(EX) ((void)0)
89 #endif /* !VERIFY */
90
91 #ifndef CKSUM_ERR
92 #define CKSUM_ERR(fmt, args...) ((void)0)
93 #endif /* !CKSUM_ERR */
94
95 #define PREDICT_TRUE(x) __builtin_expect(!!((long)(x)), 1L)
96 #define PREDICT_FALSE(x) __builtin_expect(!!((long)(x)), 0L)
97
98 /* fake mbuf struct used only for calling os_cpu_in_cksum_mbuf() */
99 struct _mbuf {
100 struct _mbuf *_m_next;
101 void *_m_pad;
102 uint8_t *__sized_by(_m_len) _m_data;
103 int32_t _m_len;
104 };
105
106 extern uint32_t os_cpu_in_cksum(const void *__sized_by(len), uint32_t len, uint32_t);
107 extern uint32_t os_cpu_in_cksum_mbuf(struct _mbuf *, int, int, uint32_t);
108
109 uint32_t
os_cpu_in_cksum(const void * __sized_by (len)data,uint32_t len,uint32_t initial_sum)110 os_cpu_in_cksum(const void *__sized_by(len) data, uint32_t len, uint32_t initial_sum)
111 {
112 /*
113 * If data is 4-bytes aligned (conditional), length is multiple
114 * of 4-bytes (required), and the amount to checksum is small,
115 * this would be quicker; this is suitable for IPv4/TCP header.
116 */
117 if (
118 #if !defined(__arm64__) && !defined(__x86_64__)
119 IS_P2ALIGNED(data, sizeof(uint32_t)) &&
120 #endif /* !__arm64__ && !__x86_64__ */
121 len <= 64 && (len & 3) == 0) {
122 uint32_t plen = len;
123 uint8_t *__sized_by(plen) p = __DECONST(uint8_t *, data);
124 uint64_t sum = initial_sum;
125
126 switch (len) {
127 case 20: /* simple IPv4 or TCP header */
128 sum += *(uint32_t *)(void *)p;
129 sum += *(uint32_t *)(void *)(p + 4);
130 sum += *(uint32_t *)(void *)(p + 8);
131 sum += *(uint32_t *)(void *)(p + 12);
132 sum += *(uint32_t *)(void *)(p + 16);
133 break;
134
135 case 32: /* TCP header + timestamp option */
136 sum += *(uint32_t *)(void *)p;
137 sum += *(uint32_t *)(void *)(p + 4);
138 sum += *(uint32_t *)(void *)(p + 8);
139 sum += *(uint32_t *)(void *)(p + 12);
140 sum += *(uint32_t *)(void *)(p + 16);
141 sum += *(uint32_t *)(void *)(p + 20);
142 sum += *(uint32_t *)(void *)(p + 24);
143 sum += *(uint32_t *)(void *)(p + 28);
144 break;
145
146 default:
147 while (plen) {
148 sum += *(uint32_t *)(void *)p;
149 p += 4;
150 plen -= 4;
151 }
152 break;
153 }
154
155 /* fold 64-bit to 16-bit (deferred carries) */
156 sum = (sum >> 32) + (sum & 0xffffffff); /* 33-bit */
157 sum = (sum >> 16) + (sum & 0xffff); /* 17-bit + carry */
158 sum = (sum >> 16) + (sum & 0xffff); /* 16-bit + carry */
159 sum = (sum >> 16) + (sum & 0xffff); /* final carry */
160
161 return sum & 0xffff;
162 }
163
164 /*
165 * Otherwise, let os_cpu_in_cksum_mbuf() handle it; it only looks
166 * at 3 fields: {next,data,len}, and since it doesn't care about
167 * the authenticity of the mbuf, we use a fake one here. Make
168 * sure the offsets are as expected.
169 */
170 #if defined(__LP64__)
171 _CASSERT(offsetof(struct _mbuf, _m_next) == 0);
172 _CASSERT(offsetof(struct _mbuf, _m_data) == 16);
173 _CASSERT(offsetof(struct _mbuf, _m_len) == 24);
174 #else /* !__LP64__ */
175 _CASSERT(offsetof(struct _mbuf, _m_next) == 0);
176 _CASSERT(offsetof(struct _mbuf, _m_data) == 8);
177 _CASSERT(offsetof(struct _mbuf, _m_len) == 12);
178 #endif /* !__LP64__ */
179 #ifdef KERNEL
180 _CASSERT(offsetof(struct _mbuf, _m_next) ==
181 offsetof(struct mbuf, m_next));
182 _CASSERT(offsetof(struct _mbuf, _m_data) ==
183 offsetof(struct mbuf, m_data));
184 _CASSERT(offsetof(struct _mbuf, _m_len) ==
185 offsetof(struct mbuf, m_len));
186 #endif /* KERNEL */
187 struct _mbuf m = {
188 ._m_next = NULL,
189 ._m_data = __DECONST(uint8_t *, data),
190 ._m_len = len,
191 };
192
193 return os_cpu_in_cksum_mbuf(&m, len, 0, initial_sum);
194 }
195
196 #if defined(__i386__) || defined(__x86_64__)
197
198 /*
199 * Checksum routine for Internet Protocol family headers (Portable Version).
200 *
201 * This routine is very heavily used in the network
202 * code and should be modified for each CPU to be as fast as possible.
203 *
204 * A discussion of different implementation techniques can be found in
205 * RFC 1071.
206 *
207 * The default implementation for 32-bit architectures is using
208 * a 32-bit accumulator and operating on 16-bit operands.
209 *
210 * The default implementation for 64-bit architectures is using
211 * a 64-bit accumulator and operating on 32-bit operands.
212 *
213 * Both versions are unrolled to handle 32 Byte / 64 Byte fragments as core
214 * of the inner loop. After each iteration of the inner loop, a partial
215 * reduction is done to avoid carry in long packets.
216 */
217
218 #if !defined(__LP64__)
219 /* 32-bit version */
220 uint32_t
os_cpu_in_cksum_mbuf(struct _mbuf * m,int len,int off,uint32_t initial_sum)221 os_cpu_in_cksum_mbuf(struct _mbuf *m, int len, int off, uint32_t initial_sum)
222 {
223 int mlen;
224 uint32_t sum, partial;
225 unsigned int final_acc;
226 uint8_t *data;
227 boolean_t needs_swap, started_on_odd;
228
229 VERIFY(len >= 0);
230 VERIFY(off >= 0);
231
232 needs_swap = FALSE;
233 started_on_odd = FALSE;
234 sum = (initial_sum >> 16) + (initial_sum & 0xffff);
235
236 for (;;) {
237 if (PREDICT_FALSE(m == NULL)) {
238 CKSUM_ERR("%s: out of data\n", __func__);
239 return (uint32_t)-1;
240 }
241 mlen = m->_m_len;
242 if (mlen > off) {
243 mlen -= off;
244 data = m->_m_data + off;
245 goto post_initial_offset;
246 }
247 off -= mlen;
248 if (len == 0) {
249 break;
250 }
251 m = m->_m_next;
252 }
253
254 for (; len > 0; m = m->_m_next) {
255 if (PREDICT_FALSE(m == NULL)) {
256 CKSUM_ERR("%s: out of data\n", __func__);
257 return (uint32_t)-1;
258 }
259 mlen = m->_m_len;
260 data = m->_m_data;
261 post_initial_offset:
262 if (mlen == 0) {
263 continue;
264 }
265 if (mlen > len) {
266 mlen = len;
267 }
268 len -= mlen;
269
270 partial = 0;
271 if ((uintptr_t)data & 1) {
272 /* Align on word boundary */
273 started_on_odd = !started_on_odd;
274 #if BYTE_ORDER == LITTLE_ENDIAN
275 partial = *data << 8;
276 #else
277 partial = *data;
278 #endif
279 ++data;
280 --mlen;
281 }
282 needs_swap = started_on_odd;
283 while (mlen >= 32) {
284 __builtin_prefetch(data + 32);
285 partial += *(uint16_t *)(void *)data;
286 partial += *(uint16_t *)(void *)(data + 2);
287 partial += *(uint16_t *)(void *)(data + 4);
288 partial += *(uint16_t *)(void *)(data + 6);
289 partial += *(uint16_t *)(void *)(data + 8);
290 partial += *(uint16_t *)(void *)(data + 10);
291 partial += *(uint16_t *)(void *)(data + 12);
292 partial += *(uint16_t *)(void *)(data + 14);
293 partial += *(uint16_t *)(void *)(data + 16);
294 partial += *(uint16_t *)(void *)(data + 18);
295 partial += *(uint16_t *)(void *)(data + 20);
296 partial += *(uint16_t *)(void *)(data + 22);
297 partial += *(uint16_t *)(void *)(data + 24);
298 partial += *(uint16_t *)(void *)(data + 26);
299 partial += *(uint16_t *)(void *)(data + 28);
300 partial += *(uint16_t *)(void *)(data + 30);
301 data += 32;
302 mlen -= 32;
303 if (PREDICT_FALSE(partial & 0xc0000000)) {
304 if (needs_swap) {
305 partial = (partial << 8) +
306 (partial >> 24);
307 }
308 sum += (partial >> 16);
309 sum += (partial & 0xffff);
310 partial = 0;
311 }
312 }
313 if (mlen & 16) {
314 partial += *(uint16_t *)(void *)data;
315 partial += *(uint16_t *)(void *)(data + 2);
316 partial += *(uint16_t *)(void *)(data + 4);
317 partial += *(uint16_t *)(void *)(data + 6);
318 partial += *(uint16_t *)(void *)(data + 8);
319 partial += *(uint16_t *)(void *)(data + 10);
320 partial += *(uint16_t *)(void *)(data + 12);
321 partial += *(uint16_t *)(void *)(data + 14);
322 data += 16;
323 mlen -= 16;
324 }
325 /*
326 * mlen is not updated below as the remaining tests
327 * are using bit masks, which are not affected.
328 */
329 if (mlen & 8) {
330 partial += *(uint16_t *)(void *)data;
331 partial += *(uint16_t *)(void *)(data + 2);
332 partial += *(uint16_t *)(void *)(data + 4);
333 partial += *(uint16_t *)(void *)(data + 6);
334 data += 8;
335 }
336 if (mlen & 4) {
337 partial += *(uint16_t *)(void *)data;
338 partial += *(uint16_t *)(void *)(data + 2);
339 data += 4;
340 }
341 if (mlen & 2) {
342 partial += *(uint16_t *)(void *)data;
343 data += 2;
344 }
345 if (mlen & 1) {
346 #if BYTE_ORDER == LITTLE_ENDIAN
347 partial += *data;
348 #else
349 partial += *data << 8;
350 #endif
351 started_on_odd = !started_on_odd;
352 }
353
354 if (needs_swap) {
355 partial = (partial << 8) + (partial >> 24);
356 }
357 sum += (partial >> 16) + (partial & 0xffff);
358 /*
359 * Reduce sum to allow potential byte swap
360 * in the next iteration without carry.
361 */
362 sum = (sum >> 16) + (sum & 0xffff);
363 }
364 final_acc = ((sum >> 16) & 0xffff) + (sum & 0xffff);
365 final_acc = (final_acc >> 16) + (final_acc & 0xffff);
366 return final_acc & 0xffff;
367 }
368
369 #else /* __LP64__ */
370 /* 64-bit version */
371 uint32_t
os_cpu_in_cksum_mbuf(struct _mbuf * m,int len,int off,uint32_t initial_sum)372 os_cpu_in_cksum_mbuf(struct _mbuf *m, int len, int off, uint32_t initial_sum)
373 {
374 int mlen;
375 uint64_t sum, partial;
376 unsigned int final_acc;
377 uint8_t *data;
378 boolean_t needs_swap, started_on_odd;
379
380 VERIFY(len >= 0);
381 VERIFY(off >= 0);
382
383 needs_swap = FALSE;
384 started_on_odd = FALSE;
385 sum = initial_sum;
386
387 for (;;) {
388 if (PREDICT_FALSE(m == NULL)) {
389 CKSUM_ERR("%s: out of data\n", __func__);
390 return (uint32_t)-1;
391 }
392 mlen = m->_m_len;
393 if (mlen > off) {
394 mlen -= off;
395 data = m->_m_data + off;
396 goto post_initial_offset;
397 }
398 off -= mlen;
399 if (len == 0) {
400 break;
401 }
402 m = m->_m_next;
403 }
404
405 for (; len > 0; m = m->_m_next) {
406 if (PREDICT_FALSE(m == NULL)) {
407 CKSUM_ERR("%s: out of data\n", __func__);
408 return (uint32_t)-1;
409 }
410 mlen = m->_m_len;
411 data = m->_m_data;
412 post_initial_offset:
413 if (mlen == 0) {
414 continue;
415 }
416 if (mlen > len) {
417 mlen = len;
418 }
419 len -= mlen;
420
421 partial = 0;
422 if ((uintptr_t)data & 1) {
423 /* Align on word boundary */
424 started_on_odd = !started_on_odd;
425 #if BYTE_ORDER == LITTLE_ENDIAN
426 partial = *data << 8;
427 #else
428 partial = *data;
429 #endif
430 ++data;
431 --mlen;
432 }
433 needs_swap = started_on_odd;
434 if ((uintptr_t)data & 2) {
435 if (mlen < 2) {
436 goto trailing_bytes;
437 }
438 partial += *(uint16_t *)(void *)data;
439 data += 2;
440 mlen -= 2;
441 }
442 while (mlen >= 64) {
443 __builtin_prefetch(data + 32);
444 __builtin_prefetch(data + 64);
445 partial += *(uint32_t *)(void *)data;
446 partial += *(uint32_t *)(void *)(data + 4);
447 partial += *(uint32_t *)(void *)(data + 8);
448 partial += *(uint32_t *)(void *)(data + 12);
449 partial += *(uint32_t *)(void *)(data + 16);
450 partial += *(uint32_t *)(void *)(data + 20);
451 partial += *(uint32_t *)(void *)(data + 24);
452 partial += *(uint32_t *)(void *)(data + 28);
453 partial += *(uint32_t *)(void *)(data + 32);
454 partial += *(uint32_t *)(void *)(data + 36);
455 partial += *(uint32_t *)(void *)(data + 40);
456 partial += *(uint32_t *)(void *)(data + 44);
457 partial += *(uint32_t *)(void *)(data + 48);
458 partial += *(uint32_t *)(void *)(data + 52);
459 partial += *(uint32_t *)(void *)(data + 56);
460 partial += *(uint32_t *)(void *)(data + 60);
461 data += 64;
462 mlen -= 64;
463 if (PREDICT_FALSE(partial & (3ULL << 62))) {
464 if (needs_swap) {
465 partial = (partial << 8) +
466 (partial >> 56);
467 }
468 sum += (partial >> 32);
469 sum += (partial & 0xffffffff);
470 partial = 0;
471 }
472 }
473 /*
474 * mlen is not updated below as the remaining tests
475 * are using bit masks, which are not affected.
476 */
477 if (mlen & 32) {
478 partial += *(uint32_t *)(void *)data;
479 partial += *(uint32_t *)(void *)(data + 4);
480 partial += *(uint32_t *)(void *)(data + 8);
481 partial += *(uint32_t *)(void *)(data + 12);
482 partial += *(uint32_t *)(void *)(data + 16);
483 partial += *(uint32_t *)(void *)(data + 20);
484 partial += *(uint32_t *)(void *)(data + 24);
485 partial += *(uint32_t *)(void *)(data + 28);
486 data += 32;
487 }
488 if (mlen & 16) {
489 partial += *(uint32_t *)(void *)data;
490 partial += *(uint32_t *)(void *)(data + 4);
491 partial += *(uint32_t *)(void *)(data + 8);
492 partial += *(uint32_t *)(void *)(data + 12);
493 data += 16;
494 }
495 if (mlen & 8) {
496 partial += *(uint32_t *)(void *)data;
497 partial += *(uint32_t *)(void *)(data + 4);
498 data += 8;
499 }
500 if (mlen & 4) {
501 partial += *(uint32_t *)(void *)data;
502 data += 4;
503 }
504 if (mlen & 2) {
505 partial += *(uint16_t *)(void *)data;
506 data += 2;
507 }
508 trailing_bytes:
509 if (mlen & 1) {
510 #if BYTE_ORDER == LITTLE_ENDIAN
511 partial += *data;
512 #else
513 partial += *data << 8;
514 #endif
515 started_on_odd = !started_on_odd;
516 }
517
518 if (needs_swap) {
519 partial = (partial << 8) + (partial >> 56);
520 }
521 sum += (partial >> 32) + (partial & 0xffffffff);
522 /*
523 * Reduce sum to allow potential byte swap
524 * in the next iteration without carry.
525 */
526 sum = (sum >> 32) + (sum & 0xffffffff);
527 }
528 final_acc = (sum >> 48) + ((sum >> 32) & 0xffff) +
529 ((sum >> 16) & 0xffff) + (sum & 0xffff);
530 final_acc = (final_acc >> 16) + (final_acc & 0xffff);
531 final_acc = (final_acc >> 16) + (final_acc & 0xffff);
532 return final_acc & 0xffff;
533 }
534 #endif /* __LP64 */
535
536 #endif /* __i386__ || __x86_64__ */
537