| tcp_lro.c (300731) | tcp_lro.c (301249) |
|---|---|
| 1/*- 2 * Copyright (c) 2007, Myricom Inc. 3 * Copyright (c) 2008, Intel Corporation. 4 * Copyright (c) 2012 The FreeBSD Foundation 5 * Copyright (c) 2016 Mellanox Technologies. 6 * All rights reserved. 7 * 8 * Portions of this software were developed by Bjoern Zeeb --- 17 unchanged lines hidden (view full) --- 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 */ 32 33#include <sys/cdefs.h> | 1/*- 2 * Copyright (c) 2007, Myricom Inc. 3 * Copyright (c) 2008, Intel Corporation. 4 * Copyright (c) 2012 The FreeBSD Foundation 5 * Copyright (c) 2016 Mellanox Technologies. 6 * All rights reserved. 7 * 8 * Portions of this software were developed by Bjoern Zeeb --- 17 unchanged lines hidden (view full) --- 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 */ 32 33#include <sys/cdefs.h> |
| 34__FBSDID("$FreeBSD: head/sys/netinet/tcp_lro.c 300731 2016-05-26 11:10:31Z hselasky $"); | 34__FBSDID("$FreeBSD: head/sys/netinet/tcp_lro.c 301249 2016-06-03 08:35:07Z hselasky $"); |
| 35 36#include "opt_inet.h" 37#include "opt_inet6.h" 38 39#include <sys/param.h> 40#include <sys/systm.h> 41#include <sys/kernel.h> 42#include <sys/malloc.h> --- 339 unchanged lines hidden (view full) --- 382#endif 383 384/* 385 * The tcp_lro_sort() routine is comparable to qsort(), except it has 386 * a worst case complexity limit of O(MIN(N,64)*N), where N is the 387 * number of elements to sort and 64 is the number of sequence bits 388 * available. The algorithm is bit-slicing the 64-bit sequence number, 389 * sorting one bit at a time from the most significant bit until the | 35 36#include "opt_inet.h" 37#include "opt_inet6.h" 38 39#include <sys/param.h> 40#include <sys/systm.h> 41#include <sys/kernel.h> 42#include <sys/malloc.h> --- 339 unchanged lines hidden (view full) --- 382#endif 383 384/* 385 * The tcp_lro_sort() routine is comparable to qsort(), except it has 386 * a worst case complexity limit of O(MIN(N,64)*N), where N is the 387 * number of elements to sort and 64 is the number of sequence bits 388 * available. The algorithm is bit-slicing the 64-bit sequence number, 389 * sorting one bit at a time from the most significant bit until the |
| 390 * least significant one, skipping the constant bits. | 390 * least significant one, skipping the constant bits. This is 391 * typically called a radix sort. |
| 391 */ 392static void 393tcp_lro_sort(struct lro_mbuf_sort *parray, uint32_t size) 394{ 395 struct lro_mbuf_sort temp; 396 uint64_t ones; 397 uint64_t zeros; 398 uint32_t x; 399 uint32_t y; 400 401repeat: | 392 */ 393static void 394tcp_lro_sort(struct lro_mbuf_sort *parray, uint32_t size) 395{ 396 struct lro_mbuf_sort temp; 397 uint64_t ones; 398 uint64_t zeros; 399 uint32_t x; 400 uint32_t y; 401 402repeat: |
| 402 /* for small arrays bubble sort is faster */ | 403 /* for small arrays insertion sort is faster */ |
| 403 if (size <= 12) { | 404 if (size <= 12) { |
| 404 for (x = 0; x != size; x++) { 405 for (y = x + 1; y != size; y++) { 406 if (parray[x].seq > parray[y].seq) { 407 /* swap entries */ 408 temp = parray[x]; 409 parray[x] = parray[y]; 410 parray[y] = temp; 411 } 412 } | 405 for (x = 1; x < size; x++) { 406 temp = parray[x]; 407 for (y = x; y > 0 && temp.seq < parray[y - 1].seq; y--) 408 parray[y] = parray[y - 1]; 409 parray[y] = temp; |
| 413 } 414 return; 415 } 416 417 /* compute sequence bits which are constant */ 418 ones = 0; 419 zeros = 0; 420 for (x = 0; x != size; x++) { --- 459 unchanged lines hidden --- | 410 } 411 return; 412 } 413 414 /* compute sequence bits which are constant */ 415 ones = 0; 416 zeros = 0; 417 for (x = 0; x != size; x++) { --- 459 unchanged lines hidden --- |