Differential D21582 Diff 63881 head/sys/netinet/tcp_stacks/sack_filter.c

Changeset View

Standalone View

head/sys/netinet/tcp_stacks/sack_filter.c

/*-		/*-
* Copyright (c) 2017 Netflix, Inc.		* Copyright (c) 2017-9 Netflix, Inc.
*		*
* Redistribution and use in source and binary forms, with or without		* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions		* modification, are permitted provided that the following conditions
* are met:		* are met:
* 1. Redistributions of source code must retain the above copyright		* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.		* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright		* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the		* notice, this list of conditions and the following disclaimer in the
▲ Show 20 Lines • Show All 124 Lines • ▼ Show 20 Lines
* the sackblock b is on the score		* the sackblock b is on the score
* board. Update it along the way		* board. Update it along the way
* if part of it is on the board.		* if part of it is on the board.
*/		*/
static int32_t		static int32_t
is_sack_on_board(struct sack_filter sf, struct sackblk b)		is_sack_on_board(struct sack_filter sf, struct sackblk b)
{		{
int32_t i, cnt;		int32_t i, cnt;

for (i = sf->sf_cur, cnt=0; cnt < SACK_FILTER_BLOCKS; cnt++) {		for (i = sf->sf_cur, cnt=0; cnt < SACK_FILTER_BLOCKS; cnt++) {
if (sack_blk_used(sf, i)) {		if (sack_blk_used(sf, i)) {
if (SEQ_LT(b->start, sf->sf_ack)) {		if (SEQ_LT(b->start, sf->sf_ack)) {
/* Behind cum-ack update */		/* Behind cum-ack update */
b->start = sf->sf_ack;		b->start = sf->sf_ack;
}		}
if (SEQ_LT(b->end, sf->sf_ack)) {		if (SEQ_LT(b->end, sf->sf_ack)) {
/* End back behind too */		/* End back behind too */
b->end = sf->sf_ack;		b->end = sf->sf_ack;
}		}
if (b->start == b->end)		if (b->start == b->end) {
return(1);		return(1);
		}
/* Jonathans Rule 1 */		/* Jonathans Rule 1 */
if (SEQ_LEQ(sf->sf_blks[i].start, b->start) &&		if (SEQ_LEQ(sf->sf_blks[i].start, b->start) &&
SEQ_GEQ(sf->sf_blks[i].end, b->end)) {		SEQ_GEQ(sf->sf_blks[i].end, b->end)) {
/**		/**
* Our board has this entirely in		* Our board has this entirely in
* whole or in part:		* whole or in part:
*		*
* board \|-------------\|		* board \|-------------\|
▲ Show 20 Lines • Show All 144 Lines • ▼ Show 20 Lines	for(i=0, num=0; i<numblks; i++) {
if (is_sack_on_board(sf, &in[i]))		if (is_sack_on_board(sf, &in[i]))
continue;		continue;
memcpy(&blkboard[num], &in[i], sizeof(struct sackblk));		memcpy(&blkboard[num], &in[i], sizeof(struct sackblk));
num++;		num++;
}		}
if (num == 0)		if (num == 0)
return(num);		return(num);

/* Now what we are left is either		/* Now what we are left with is either
* completely merged on to the board		* completely merged on to the board
* from the above steps, or are new		* from the above steps, or is new
* and need to be added to the board		* and need to be added to the board
* with the last one updated to current.		* with the last one updated to current.
*		*
* First copy it out we want to return that		* First copy it out, we want to return that
* to our caller for processing.		* to our caller for processing.
*/		*/
memcpy(in, blkboard, (num * sizeof(struct sackblk)));		memcpy(in, blkboard, (num * sizeof(struct sackblk)));
numblks = num;		numblks = num;
/* Now go through and add to our board as needed */		/* Now go through and add to our board as needed */
for(i=(num-1); i>=0; i--) {		for(i=(num-1); i>=0; i--) {
if (is_sack_on_board(sf, &blkboard[i]))		if (is_sack_on_board(sf, &blkboard[i])) {
continue;		continue;
		}
/* Add this guy its not listed */		/* Add this guy its not listed */
sf->sf_cur++;		sf->sf_cur++;
sf->sf_cur %= SACK_FILTER_BLOCKS;		sf->sf_cur %= SACK_FILTER_BLOCKS;
if ((sack_blk_used(sf, sf->sf_cur)) &&		if ((sack_blk_used(sf, sf->sf_cur)) &&
(sf->sf_used < SACK_FILTER_BLOCKS)) {		(sf->sf_used < SACK_FILTER_BLOCKS)) {
sack_move_to_empty(sf, sf->sf_cur);		sack_move_to_empty(sf, sf->sf_cur);
}		}
#ifndef _KERNEL		#ifndef _KERNEL
▲ Show 20 Lines • Show All 120 Lines • ▼ Show 20 Lines	for(i=0; i<SACK_FILTER_BLOCKS; i++) {
if (j_d > i_d) {		if (j_d > i_d) {
sack_collapse(sf, j, i);		sack_collapse(sf, j, i);
} else		} else
sack_collapse(sf, i, j);		sack_collapse(sf, i, j);
}		}
}		}

#ifndef _KERNEL		#ifndef _KERNEL
		uint64_t saved=0;
		uint64_t tot_sack_blks=0;

		static void
		sack_filter_dump(FILE out, struct sack_filter sf)
		{
		int i;
		fprintf(out, " sf_ack:%u sf_bits:0x%x c:%d used:%d\n",
		sf->sf_ack, sf->sf_bits,
		sf->sf_cur, sf->sf_used);

		for(i=0; i<SACK_FILTER_BLOCKS; i++) {
		if (sack_blk_used(sf, i)) {
		fprintf(out, "Entry:%d start:%u end:%u\n", i,
		sf->sf_blks[i].start,
		sf->sf_blks[i].end);
		}
		}
		}
		#endif

		#ifndef _KERNEL
static		static
#endif		#endif
int		int
sack_filter_blks(struct sack_filter sf, struct sackblk in, int numblks, tcp_seq th_ack)		sack_filter_blks(struct sack_filter sf, struct sackblk in, int numblks,
		tcp_seq th_ack)
{		{
int32_t i, ret;		int32_t i, ret;

if (numblks > TCP_MAX_SACK) {		if (numblks > TCP_MAX_SACK) {
		#ifdef _KERNEL
panic("sf:%p sb:%p Impossible number of sack blocks %d > 4\n",		panic("sf:%p sb:%p Impossible number of sack blocks %d > 4\n",
sf, in,		sf, in,
numblks);		numblks);
		#endif
return(numblks);		return(numblks);
}		}
		#ifndef _KERNEL
		if ((sf->sf_used > 1) && (no_collapse == 0))
		sack_board_collapse(sf);

		#else
		if (sf->sf_used > 1)
		sack_board_collapse(sf);
		#endif
if ((sf->sf_used == 0) && numblks) {		if ((sf->sf_used == 0) && numblks) {
/*		/*
* We are brand new add the blocks in		* We are brand new add the blocks in
* reverse order. Note we can see more		* reverse order. Note we can see more
* than one in new, since ack's could be lost.		* than one in new, since ack's could be lost.
*/		*/
		int cnt_added = 0;

sf->sf_ack = th_ack;		sf->sf_ack = th_ack;
for(i=(numblks-1), sf->sf_cur=0; i >= 0; i--) {		for(i=(numblks-1), sf->sf_cur=0; i >= 0; i--) {
memcpy(&sf->sf_blks[sf->sf_cur], &in[i], sizeof(struct sackblk));		memcpy(&sf->sf_blks[sf->sf_cur], &in[i], sizeof(struct sackblk));
sf->sf_bits = sack_blk_set(sf, sf->sf_cur);		sf->sf_bits = sack_blk_set(sf, sf->sf_cur);
sf->sf_cur++;		sf->sf_cur++;
sf->sf_cur %= SACK_FILTER_BLOCKS;		sf->sf_cur %= SACK_FILTER_BLOCKS;
sf->sf_used++;		sf->sf_used++;
		cnt_added++;
#ifndef _KERNEL		#ifndef _KERNEL
if (sf->sf_used > highest_used)		if (sf->sf_used > highest_used)
highest_used = sf->sf_used;		highest_used = sf->sf_used;
#endif		#endif
}		}
if (sf->sf_cur)		if (sf->sf_cur)
sf->sf_cur--;		sf->sf_cur--;
return(numblks);
		return (cnt_added);
}		}
if (SEQ_GT(th_ack, sf->sf_ack)) {		if (SEQ_GT(th_ack, sf->sf_ack)) {
sack_filter_prune(sf, th_ack);		sack_filter_prune(sf, th_ack);
}		}
if (numblks) {		if (numblks) {
if (SEQ_GEQ(th_ack, sf->sf_ack)) {		if (SEQ_GEQ(th_ack, sf->sf_ack)) {
ret = sack_filter_new(sf, in, numblks, th_ack);		ret = sack_filter_new(sf, in, numblks, th_ack);
} else {		} else {
ret = sack_filter_old(sf, in, numblks);		ret = sack_filter_old(sf, in, numblks);
}		}
} else		} else
ret = 0;		ret = 0;
#ifndef _KERNEL
if ((sf->sf_used > 1) && (no_collapse == 0))
sack_board_collapse(sf);

#else
if (sf->sf_used > 1)
sack_board_collapse(sf);

#endif
return (ret);		return (ret);
}		}

#ifndef _KERNEL		void
uint64_t saved=0;		sack_filter_reject(struct sack_filter sf, struct sackblk in)
uint64_t tot_sack_blks=0;

static void
sack_filter_dump(FILE out, struct sack_filter sf)
{		{
		/*
		* Given a specified block (that had made
		* it past the sack filter). Reject that
		* block triming it off any sack-filter block
		* that has it. Usually because the block was
		* too small and did not cover a whole send.
		*
		* This function will only "undo" sack-blocks
		* that are fresh and touch the edges of
		* blocks in our filter.
		*/
int i;		int i;
fprintf(out, " sf_ack:%u sf_bits:0x%x c:%d used:%d\n",
sf->sf_ack, sf->sf_bits,
sf->sf_cur, sf->sf_used);

for(i=0; i<SACK_FILTER_BLOCKS; i++) {		for(i=0; i<SACK_FILTER_BLOCKS; i++) {
if (sack_blk_used(sf, i)) {		if (sack_blk_used(sf, i) == 0)
fprintf(out, "Entry:%d start:%u end:%u\n", i,		continue;
sf->sf_blks[i].start,		/*
sf->sf_blks[i].end);		* Now given the sack-filter block does it touch
		* with one of the ends
		*/
		if (sf->sf_blks[i].end == in->end) {
		/* The end moves back to start */
		if (SEQ_GT(in->start, sf->sf_blks[i].start))
		/* in-blk \|----\| */
		/* sf-blk \|---------\| */
		sf->sf_blks[i].end = in->start;
		else {
		/* It consumes this block */
		/* in-blk \|---------\| */
		/* sf-blk \|------\| */
		/* <or> */
		/* sf-blk \|---------\| */
		sf->sf_bits = sack_blk_clr(sf, i);
		sf->sf_used--;
}		}
		continue;
}		}
		if (sf->sf_blks[i].start == in->start) {
		if (SEQ_LT(in->end, sf->sf_blks[i].end)) {
		/* in-blk \|----\| */
		/* sf-blk \|---------\| */
		sf->sf_blks[i].start = in->end;
		} else {
		/* It consumes this block */
		/* in-blk \|----------\| */
		/* sf-blk \|-------\| */
		/* <or> */
		/* sf-blk \|----------\| */
		sf->sf_bits = sack_blk_clr(sf, i);
		sf->sf_used--;
}		}
		continue;
		}
		}
		}

		#ifndef _KERNEL

int		int
main(int argc, char **argv)		main(int argc, char **argv)
{		{
char buffer[512];		char buffer[512];
struct sackblk blks[TCP_MAX_SACK];		struct sackblk blks[TCP_MAX_SACK];
FILE *err;		FILE *err;
tcp_seq th_ack, snd_una;		tcp_seq th_ack, snd_una, snd_max = 0;
struct sack_filter sf;		struct sack_filter sf;
int32_t numblks,i;		int32_t numblks,i;
int snd_una_set=0;		int snd_una_set=0;
double a, b, c;		double a, b, c;
int invalid_sack_print = 0;		int invalid_sack_print = 0;
uint32_t chg_remembered=0;		uint32_t chg_remembered=0;
uint32_t sack_chg=0;		uint32_t sack_chg=0;
char line_buf[10][256];		char line_buf[10][256];
int line_buf_at=0;		int line_buf_at=0;

in = stdin;		in = stdin;
out = stdout;		out = stdout;
while ((i = getopt(argc, argv, "ndIi:o:?h")) != -1) {		while ((i = getopt(argc, argv, "ndIi:o:?h")) != -1) {
Show All 34 Lines	main(int argc, char **argv)
memset(blks, 0, sizeof(blks));		memset(blks, 0, sizeof(blks));
numblks = 0;		numblks = 0;
fprintf(out, "************************************\n");		fprintf(out, "************************************\n");
while (fgets(buffer, sizeof(buffer), in) != NULL) {		while (fgets(buffer, sizeof(buffer), in) != NULL) {
sprintf(line_buf[line_buf_at], "%s", buffer);		sprintf(line_buf[line_buf_at], "%s", buffer);
line_buf_at++;		line_buf_at++;
if (strncmp(buffer, "QUIT", 4) == 0) {		if (strncmp(buffer, "QUIT", 4) == 0) {
break;		break;
} else if (strncmp(buffer, "DONE", 4) == 0) {		} else if (strncmp(buffer, "DUMP", 4) == 0) {
		sack_filter_dump(out, &sf);
		} else if (strncmp(buffer, "MAX:", 4) == 0) {
		snd_max = strtoul(&buffer[4], NULL, 0);
		} else if (strncmp(buffer, "COMMIT", 6) == 0) {
int nn, ii;		int nn, ii;
if (numblks) {		if (numblks) {
uint32_t szof, tot_chg;		uint32_t szof, tot_chg;
for(ii=0; ii<line_buf_at; ii++) {		for(ii=0; ii<line_buf_at; ii++) {
fprintf(out, "%s", line_buf[ii]);		fprintf(out, "%s", line_buf[ii]);
}		}
fprintf(out, "------------------------------------\n");		fprintf(out, "------------------------------------\n");
nn = sack_filter_blks(&sf, blks, numblks, th_ack);		nn = sack_filter_blks(&sf, blks, numblks, th_ack);
Show All 39 Lines	if (strncmp(buffer, "QUIT", 4) == 0) {
}		}
} else if (strncmp(buffer, "EXIT", 4) == 0) {		} else if (strncmp(buffer, "EXIT", 4) == 0) {
sack_filter_clear(&sf, snd_una);		sack_filter_clear(&sf, snd_una);
sack_chg = chg_remembered = 0;		sack_chg = chg_remembered = 0;
} else if (strncmp(buffer, "SACK:", 5) == 0) {		} else if (strncmp(buffer, "SACK:", 5) == 0) {
char *end=NULL;		char *end=NULL;
uint32_t start;		uint32_t start;
uint32_t endv;		uint32_t endv;

start = strtoul(&buffer[5], &end, 0);		start = strtoul(&buffer[5], &end, 0);
if (end) {		if (end) {
endv = strtoul(&end[1], NULL, 0);		endv = strtoul(&end[1], NULL, 0);
} else {		} else {
fprintf(out, "--Sack invalid skip 0 start:%u : ??\n", start);		fprintf(out, "--Sack invalid skip 0 start:%u : ??\n", start);
continue;		continue;
}		}
		if (SEQ_GT(endv, snd_max))
		snd_max = endv;
if (SEQ_LT(endv, start)) {		if (SEQ_LT(endv, start)) {
fprintf(out, "--Sack invalid skip 1 endv:%u < start:%u\n", endv, start);		fprintf(out, "--Sack invalid skip 1 endv:%u < start:%u\n", endv, start);
continue;		continue;
}		}
if (numblks == TCP_MAX_SACK) {		if (numblks == TCP_MAX_SACK) {
fprintf(out, "--Exceeded max %d\n", numblks);		fprintf(out, "--Exceeded max %d\n", numblks);
exit(0);		exit(0);
}		}
blks[numblks].start = start;		blks[numblks].start = start;
blks[numblks].end = endv;		blks[numblks].end = endv;
numblks++;		numblks++;
		} else if (strncmp(buffer, "REJ:n:n", 4) == 0) {
		struct sackblk in;
		char *end=NULL;

		in.start = strtoul(&buffer[4], &end, 0);
		if (end) {
		in.end = strtoul(&end[1], NULL, 0);
		sack_filter_reject(&sf, &in);
		} else
		fprintf(out, "Invalid input END:A:B\n");
		} else if (strncmp(buffer, "HELP", 4) == 0) {
		fprintf(out, "You can input:\n");
		fprintf(out, "SACK:S:E -- to define a sack block\n");
		fprintf(out, "RXT -- to clear the filter without changing the remembered\n");
		fprintf(out, "EXIT -- To clear the sack filter and start all fresh\n");
		fprintf(out, "ACK:N -- To advance the cum-ack to N\n");
		fprintf(out, "MAX:N -- To set send-max to N\n");
		fprintf(out, "COMMIT -- To apply the sack you built to the filter and dump the filter\n");
		fprintf(out, "DUMP -- To display the current contents of the sack filter\n");
		fprintf(out, "QUIT -- To exit this program\n");
		} else {
		fprintf(out, "Command %s unknown\n", buffer);
}		}
memset(buffer, 0, sizeof(buffer));		memset(buffer, 0, sizeof(buffer));
}		}
if (in != stdin) {		if (in != stdin) {
fclose(in);		fclose(in);
}		}
if (out != stdout) {		if (out != stdout) {
fclose(out);		fclose(out);
Show All 16 Lines