libalias: Restructure searching
AbandonedPublic
Actions

Authored by donner on May 15 2021, 11:46 PM.

Details

Reviewers

lev
kp

Group Reviewers

network

Summary

In order to switch to a faster data structure for searching, the
current algorithm needs to be understood.

In this step the mix of full qualified entries (real data flow) and
general ones (i.e. port forwardings) is separated. This allows to
simplify the search procedures and factor out the common, relevant
search fields.

Test Plan

As long as there is no mature test suite for the library, only a test
in production could show failures. Tests must contain a huge workload
of active connections and various, unusual protocols.

No commit before test suite is complete.

1_instance:1_singleinit  ->  passed  [0.003s]
1_instance:2_destroynull  ->  expected_failure: Code expects valid pointer.  [0.013s]
1_instance:3_multiinit  ->  passed  [0.005s]
1_instance:4_multiinstance  ->  passed  [0.037s]
2_natout:1_simplemasq  ->  passed  [0.003s]
2_natout:2_unregistered  ->  passed  [0.003s]
2_natout:3_cgn  ->  passed  [0.004s]
2_natout:4_udp  ->  passed  [0.003s]
2_natout:5_sameport  ->  passed  [0.003s]
2_natout:6_cleartable  ->  passed  [0.003s]
2_natout:7_stress  ->  passed  [0.048s]
3_natin:1_portforward  ->  passed  [0.003s]
3_natin:2_portoverlap  ->  passed  [0.003s]
3_natin:3_redirectany  ->  passed  [0.003s]
3_natin:4_redirectaddr  ->  passed  [0.003s]
3_natin:5_lsnat  ->  passed  [0.003s]
3_natin:6_oneshot  ->  passed  [0.003s]

Performance before this patch:

Running perfomance test with parameters:
  Maximum Runtime (max_seconds) = 10
  Amount of valid connections (batch_size) = 2000
  Amount of random, incoming packets (batch_size) = 1000
  Repeat count of a random, incoming packet (attack_size) = 1000
  Amount of open port forwardings (redir_size) = 2000

RND SECOND newNAT RANDOM ATTACK useNAT
  1    0.0   0.59   0.18   0.06   0.10
  2    0.0   0.66   0.16   0.06   0.11
  3    0.0   0.77   0.20   0.06   0.11
  4    0.1   0.85   0.25   0.06   0.10
  5    0.1   0.91   0.23   0.06   0.12
...
135    9.4  54.76  16.33   1.24   0.10
136    9.6  54.52  16.50   0.97   0.10
137    9.7  56.18  16.97   1.11   0.10
138    9.8  58.04  16.60   1.23   0.11
139   10.0

Results
   Rounds  :       138
newNAT ok  :    276410
newNAT fail:         0
useNAT ok  :   2282413 (out)
useNAT fail:         0 (out)
useNAT ok  :  18462687 (in)
useNAT fail:         0 (in)
RANDOM ok  :      1806
RANDOM fail:    136194
ATTACK ok  :         0
ATTACK fail:    138000
             ---------
      Total:  21297510

And now:

Running perfomance test with parameters:
  Maximum Runtime (max_seconds) = 10
  Amount of valid connections (batch_size) = 2000
  Amount of random, incoming packets (batch_size) = 1000
  Repeat count of a random, incoming packet (attack_size) = 1000
  Amount of open port forwardings (redir_size) = 2000

RND SECOND newNAT RANDOM ATTACK useNAT
  1    0.0   0.59   0.14   0.06   0.10
  2    0.0   0.71   0.14   0.05   0.10
  3    0.0   0.78   0.17   0.06   0.11
  4    0.1   0.90   0.18   0.06   0.11
  5    0.1   0.95   0.18   0.06   0.10
...
145    9.6  52.49   1.80   0.11   0.17
146    9.7  51.62   1.91   0.13   0.19
147    9.8  48.77   1.87   0.13   0.17
148   10.0

Results
   Rounds  :       147
newNAT ok  :    295178
newNAT fail:         0
useNAT ok  :   2431666 (out)
useNAT fail:         0 (out)
useNAT ok  :  19669446 (in)
useNAT fail:         0 (in)
RANDOM ok  :      1940
RANDOM fail:    145060
ATTACK ok  :         0
ATTACK fail:    147000
             ---------
      Total:  22690290

Diff Detail

Repository

rS FreeBSD src repository - subversion

Lint

Lint Passed

Unit

No Test Coverage

Build Status

Buildable 39215
Build 36104: arc lint + arc unit

Event Timeline

donner created this revision.May 15 2021, 11:46 PM

Herald added subscribers: Contributor Reviews (src), melifaro, imp. · View Herald TranscriptMay 15 2021, 11:46 PM

donner requested review of this revision.May 15 2021, 11:46 PM

Harbormaster completed remote builds in B39214: Diff 89278.May 15 2021, 11:46 PM

donner added a reviewer: network.May 15 2021, 11:47 PM

NO_ADDR for fragments

Harbormaster completed remote builds in B39215: Diff 89279.May 16 2021, 12:02 AM

Fix split point.

Harbormaster completed remote builds in B39216: Diff 89280.May 16 2021, 12:04 AM

donner added a parent revision: D30277: libalias: tidy up housekeeping.May 16 2021, 12:13 AM

NO_ADDR for fragments
Factor out common search pattens in in and out direction.

Harbormaster completed remote builds in B39219: Diff 89293.May 16 2021, 1:55 PM

Further refactoring

Harbormaster completed remote builds in B39220: Diff 89306.May 16 2021, 5:58 PM

Reclassify SCTP links when specifying missing parts.

Harbormaster completed remote builds in B39221: Diff 89307.May 16 2021, 6:10 PM

Added @lev primary for testing of functionality.
There should be some performance improvements due to:

some early breaks in the loops with many active flows
separation of "complete" flows from configured "forwardings"
use of NO_ADDR when possible

I did run the tests from D30335 against this patch:

1_instance:1_singleinit  ->  passed  [0.004s]
1_instance:2_destroynull  ->  expected_failure: Code expects valid pointer.  [0.014s]
1_instance:3_multiinit  ->  passed  [0.004s]
1_instance:4_multiinstance  ->  passed  [0.036s]
2_natout:1_simplemasq  ->  passed  [0.003s]
2_natout:2_unregistered  ->  passed  [0.003s]
2_natout:3_cgn  ->  passed  [0.003s]
2_natout:4_udp  ->  passed  [0.003s]
2_natout:5_sameport  ->  passed  [0.003s]
2_natout:6_cleartable  ->  passed  [0.003s]
2_natout:7_stress  ->  passed  [8.880s]

Compared to the original version, a performance boost in the stress test is observed: Down from 11 seconds to 9 seconds. This is mainly due to early break of lookup loops.

donner edited the test plan for this revision. (Show Details)May 21 2021, 8:44 AM

donner added a parent revision: D30335: test/libalias: Tests for outgoing NAT.

Rebase

Tests show several broken issues:

2_natout:2_unregistered  ->  failed: 2 checks failed
*** Check failed: 2_natout.c:88: addr_eq(cgn, pip->ip_src) not met
*** Check failed: 2_natout.c:89: addr_eq(pub, pip->ip_src) not met
2_natout:3_cgn  ->  failed: 1 checks failed
*** Check failed: 2_natout.c:122: addr_eq(pub, pip->ip_src) not met
3_natin:4_redirectaddr  ->  failed: 3 checks failed
*** Check failed: 3_natin.c:277: addr_eq(pub, p->ip_src) not met
*** Check failed: 3_natin.c:278: addr_eq(pub, p->ip_src) not met
*** Check failed: 3_natin.c:293: addr_eq(pub, p->ip_src) not met

And the new code is terribly slow, simply becaus the 4001er hash table
is gone:

RND SECOND newNAT RANDOM ATTACK useNAT
  1    0.0  33.25  21.74  21.61   3.90
  2    0.7  34.59  22.30  21.68   3.96
  3    1.4  37.09  23.20  21.84   4.11
  4    2.1  38.59  24.23  22.12   4.25
  5    2.9  39.57  25.06  22.08   4.41
  6    3.7  42.10  26.54  22.59   4.80
  7    4.5  44.15  27.81  22.33   4.78
  8    5.4  47.03  28.96  22.68   4.93
  9    6.3  48.78  30.56  23.03   5.15
 10    7.2  52.07  31.30  22.99   5.28
 11    8.1  54.44  32.57  23.00   5.46
 12    9.1  56.62  33.90  23.26

Results
   Rounds  :        11
newNAT ok  :     24000
newNAT fail:         0
useNAT ok  :         0 (out)
useNAT fail:    194573 (out)
useNAT ok  :   1576057 (in)
useNAT fail:         0 (in)
RANDOM ok  :       157
RANDOM fail:     11843
ATTACK ok  :         0
ATTACK fail:     12000
             ---------
      Total:   1818630

Harbormaster completed remote builds in B39438: Diff 89808.May 25 2021, 10:44 AM

I'm writing this comment to this change almost arbitrary, as it is meta-comments on your (great!) work.

(1) I think, that performance baseline with 4001-sized (default) hashtable is almost meaningless, as this size is laughable even for SOHO router (in my experience), Replacing 4001 with 65537 gives almost +50% on low-end hardware without any other changes.

(2) According to my profiling with dtrace and flamegraphs, all performance is lost in contention over single mutex, not in data structures processing, like search or update, as soon as mutex is locked.

In D30283#683929, @lev wrote:

I'm writing this comment to this change almost arbitrary, as it is meta-comments on your (great!) work.

Thanks.

(1) I think, that performance baseline with 4001-sized (default) hashtable is almost meaningless, as this size is laughable even for SOHO router (in my experience), Replacing 4001 with 65537 gives almost +50% on low-end hardware without any other changes.

They will be replaced anyway.

(2) According to my profiling with dtrace and flamegraphs, all performance is lost in contention over single mutex, not in data structures processing, like search or update, as soon as mutex is locked.

That's right, so I have 64 or 128 libalias instances in parallel. Other data structures will probably allow shared access.

Rework the whole patch to get rid of failures of the test suite and to
only improve the performance.

Rename NO_ADDR to ANY_ADDR
Factor out the common Out filter
Factor out the common In filter
Search fully specified links first.
Separate the partially specified links into a separate data structure.
Use a (smaller) hash table to speed up the partially link access.
Clean program flow in _FindLinkIn
Factor out the outgoing search function.
Fix small error in termination.
Factor out Cleanup and Use for links.
Cleanup the partial find procedure
Rework the incoming search over full know links.
Just another early exit of the search loop

Harbormaster completed remote builds in B39462: Diff 89899.May 26 2021, 1:40 PM

Reorder incoming links by grouping of common search terms.

Major performance improvement for unmatched incoming flows (RANDOM or
ATTACK).

Harbormaster completed remote builds in B39477: Diff 89927.May 26 2021, 6:56 PM

donner edited the test plan for this revision. (Show Details)May 26 2021, 7:04 PM

@lev may you consider testing this patch in your environment? It should speed up you use case.

Remove LSNAT from outgoing search.

Slight speedup due to less comparsions in the loop.

Harbormaster completed remote builds in B39488: Diff 89945.May 27 2021, 7:14 AM

Touch links for PPTP on use, too.

Harbormaster completed remote builds in B39489: Diff 89946.May 27 2021, 7:18 AM

In D30283#684871, @donner wrote:

@lev may you consider testing this patch in your environment? It should speed up you use case.

I'll test this at this weekend or later next week, payed job takes too much time now, sorry.

BTW, I'm testing with BSD Router Project methodology:

"beefy computer N1 with netmap+pkt-gen" - 1G Link -> DUT - 1G Link -> "beefy computer N2 with traffic mirror" - 10G Link -> "beefy computer N1 with pkt-gen as receiver", and script search for highest packet rate which has no drops. It allows to get exact maximum PPS, but can not benchmark situation when part of traffic is dropped by firewall/nat (because it is impossible to distinguish reasons of packet drop with pkt-gen and shell scripts) and it can use only UDP.

So, my testing scenario will not notice some changes, as a lot of failed lookups ("attack") or TCP-specific processing.

Let PPTP use their own data structure.

Harbormaster completed remote builds in B39518: Diff 90022.May 27 2021, 6:29 PM

donner added a child revision: D30516: libalias: Switch to efficient data structure for outgoing traffic.May 27 2021, 10:42 PM

Fix "freeing wrong structure" bug
Factor out pptpLists

Harbormaster completed remote builds in B39535: Diff 90056.May 28 2021, 2:29 PM

Factor out the search for a new port. Improves the perfomance a bit.

Harbormaster completed remote builds in B39539: Diff 90061.May 28 2021, 4:56 PM

Get rid of PORT_BASE. Replace by AliasRange.

Harbormaster completed remote builds in B39540: Diff 90063.May 28 2021, 5:18 PM

Rename pptpTable to pptpList

Harbormaster completed remote builds in B39553: Diff 90088.May 28 2021, 9:02 PM

donner added a reviewer: kp.May 28 2021, 9:03 PM

donner mentioned this in rGb03a41befeaf: libalias: Fix nameing and initialization of a constant.May 30 2021, 1:48 PM

donner edited parent revisions, added: D30566: libalias: Promote per instance global variable timeStamp; removed: D30277: libalias: tidy up housekeeping.May 31 2021, 11:47 AM

This is too complex.
I'll split it into smaller parts.

donner removed a child revision: D30516: libalias: Switch to efficient data structure for outgoing traffic.May 31 2021, 4:56 PM

donner removed a parent revision: D30566: libalias: Promote per instance global variable timeStamp.

donner added a child revision: D30516: libalias: Switch to efficient data structure for outgoing traffic.Jun 1 2021, 9:29 AM

donner removed a child revision: D30516: libalias: Switch to efficient data structure for outgoing traffic.Jun 1 2021, 9:32 AM

donner added a child revision: D30516: libalias: Switch to efficient data structure for outgoing traffic.Jun 13 2021, 8:52 PM

donner removed a child revision: D30516: libalias: Switch to efficient data structure for outgoing traffic.Jun 14 2021, 9:37 PM

Revision Contents
Changeset List

Path

Size

sys/

netinet/

libalias/

alias_db.c

268 lines

alias_local.h

14 lines

Diff 89279

View Options

sys/netinet/libalias/alias_db.c

	Show First 20 Lines • Show All 50 Lines • ▼ Show 20 Lines
	#include "opt_verbose_sysinit.h"			#include "opt_verbose_sysinit.h"

	#include <sys/param.h>			#include <sys/param.h>
	#include <sys/kernel.h>			#include <sys/kernel.h>
	#include <sys/epoch.h>			#include <sys/epoch.h>
	#include <sys/exec.h>			#include <sys/exec.h>
	#include <sys/file.h>			#include <sys/file.h>
	#include <sys/filedesc.h>			#include <sys/filedesc.h>
				#include <sys/imgact.h>
	#include <sys/jail.h>			#include <sys/jail.h>
	#include <sys/ktr.h>			#include <sys/ktr.h>
	#include <sys/lock.h>			#include <sys/lock.h>
	#include <sys/loginclass.h>			#include <sys/loginclass.h>
	#include <sys/mount.h>			#include <sys/mount.h>
	#include <sys/mutex.h>			#include <sys/mutex.h>
	#include <sys/syscallsubr.h>			#include <sys/syscallsubr.h>
	#include <sys/sysctl.h>			#include <sys/sysctl.h>
	▲ Show 20 Lines • Show All 644 Lines • ▼ Show 20 Lines

	/*			/*
	* Start the initial user process; try exec'ing each pathname in init_path.			* Start the initial user process; try exec'ing each pathname in init_path.
	* The program is invoked with one argument containing the boot flags.			* The program is invoked with one argument containing the boot flags.
	*/			*/
	static void			static void
	start_init(void *dummy)			start_init(void *dummy)
	{			{
	vm_offset_t addr;			struct image_args args;
	struct execve_args args;
	int options, error;			int options, error;
	size_t pathlen;			size_t pathlen;
				char flags[8], *flagp;
	char var, path;			char var, path;
	char free_init_path, tmp_init_path;			char free_init_path, tmp_init_path;
	char ucp, uap, arg0, *arg1;
	struct thread *td;			struct thread *td;
	struct proc *p;			struct proc *p;

	TSENTER(); /* Here so we don't overlap with mi_startup. */			TSENTER(); /* Here so we don't overlap with mi_startup. */

	td = curthread;			td = curthread;
	p = td->td_proc;			p = td->td_proc;

	vfs_mountroot();			vfs_mountroot();

	/* Wipe GELI passphrase from the environment. */			/* Wipe GELI passphrase from the environment. */
	kern_unsetenv("kern.geom.eli.passphrase");			kern_unsetenv("kern.geom.eli.passphrase");

	/*
	* Need just enough stack to hold the faked-up "execve()" arguments.
	*/
	addr = p->p_sysent->sv_usrstack - PAGE_SIZE;
	if (vm_map_find(&p->p_vmspace->vm_map, NULL, 0, &addr, PAGE_SIZE, 0,
	VMFS_NO_SPACE, VM_PROT_ALL, VM_PROT_ALL, 0) != 0)
	panic("init: couldn't allocate argument space");
	p->p_vmspace->vm_maxsaddr = (caddr_t)addr;
	p->p_vmspace->vm_ssize = 1;

	if ((var = kern_getenv("init_path")) != NULL) {			if ((var = kern_getenv("init_path")) != NULL) {
	strlcpy(init_path, var, sizeof(init_path));			strlcpy(init_path, var, sizeof(init_path));
	freeenv(var);			freeenv(var);
	}			}
	free_init_path = tmp_init_path = strdup(init_path, M_TEMP);			free_init_path = tmp_init_path = strdup(init_path, M_TEMP);

	while ((path = strsep(&tmp_init_path, ":")) != NULL) {			while ((path = strsep(&tmp_init_path, ":")) != NULL) {
	pathlen = strlen(path) + 1;			pathlen = strlen(path) + 1;
	if (bootverbose)			if (bootverbose)
	printf("start_init: trying %s\n", path);			printf("start_init: trying %s\n", path);

	/*			memset(&args, 0, sizeof(args));
	* Move out the boot flag argument.			error = exec_alloc_args(&args);
	*/			if (error != 0)
				panic("%s: Can't allocate space for init arguments %d",
				__func__, error);

				error = exec_args_add_fname(&args, path, UIO_SYSSPACE);
				if (error != 0)
				panic("%s: Can't add fname %d", __func__, error);

				error = exec_args_add_arg(&args, path, UIO_SYSSPACE);
				if (error != 0)
				panic("%s: Can't add argv[0] %d", __func__, error);

	options = 0;			options = 0;
	ucp = (char *)p->p_sysent->sv_usrstack;			flagp = &flags[0];
	(void)subyte(--ucp, 0); /* trailing zero */			*flagp++ = '-';
	if (boothowto & RB_SINGLE) {			#ifdef BOOTCDROM
	(void)subyte(--ucp, 's');			*flagp++ = 'C';
	options = 1;			options++;
	}			#endif
	#ifdef notyet			#ifdef notyet
	if (boothowto & RB_FASTBOOT) {			if (boothowto & RB_FASTBOOT) {
	(void)subyte(--ucp, 'f');			*flagp++ = 'f';
	options = 1;			options++;
	}			}
	#endif			#endif
				if (boothowto & RB_SINGLE) {
				jhbUnsubmitted Done Inline Actions The reordering makes the diff a bit harder to read. Did you sort them alphabetically it seems? jhb: The reordering makes the diff a bit harder to read. Did you sort them alphabetically it seems?
				brooksAuthorUnsubmitted Done Inline Actions The they are reversed because the old code builds the argument backwards (from the top of the pseudo stack). brooks: The they are reversed because the old code builds the argument backwards (from the top of the…
				jhbUnsubmitted Done Inline Actions Ok. I don't think the order of the flags passed to init matters, so would probably have preserved the existing code order to minimize the diff, but either way is fine. jhb: Ok. I don't think the order of the flags passed to init matters, so would probably have…
	#ifdef BOOTCDROM			*flagp++ = 's';
	(void)subyte(--ucp, 'C');			options++;
	options = 1;			}
	#endif

	if (options == 0)			if (options == 0)
	(void)subyte(--ucp, '-');			*flagp++ = '-';
				jhbUnsubmitted Done Inline Actions This handling now seems kind of wrong. Previously this was adding the '-' in front of all of the options if there were any, now it is adding a second '-' so that you get '--' if there were no options. You could instead perhaps keep the 'options = 1' from the previous code and instead and perhaps just omit flags entirely if options is 0, e.g.: options = 0; flagp = &flags[0]; flagp++ = '-'; #ifdef BOOTCDROM flagp++ = 'C' options = 1; #endif /* other options / flagp++ = 0; KASSERT(...); if (options != 0) { error = exec_args_add_arg(&args, flags, UIO_SYSSPACE); if (error != 0) panic(...); } This seems cleaner than adding a dummy '--' option. jhb: This handling now seems kind of wrong. Previously this was adding the '-' in front of all of…
				brooksAuthorUnsubmitted Done Inline Actions That doesn't match my read of the old code. The old options==0 case adds the a second '-' if there weren't any options and the code at line 784 adds the first hyphen unconditionally. brooks: That doesn't match my read of the old code. The old options==0 case adds the a second '-' if…
				jhbUnsubmitted Done Inline Actions Huh, that seems kind of silly to pass --. I guess it was because the old code always copied out arg1 and didn't want to deal with having it be optional. Maybe as a followup we can remove the '--' as I do think it's just a kludge to avoid having arg1 being optional. The 'options = 1' bit would reduce the diff a little still. jhb: Huh, that seems kind of silly to pass --. I guess it was because the old code always copied…
				brooksAuthorUnsubmitted Done Inline Actions After this change, I'm going to do a pass removing BOOTCDROM (init warns and ignores about -C), the RB_FASTBOOT case (ifdef notyet since at least the 4.4lite import), and --. That will leave a single case of exec_args_add_arg(&args, "-s", UIS_SYSSPACE). brooks: After this change, I'm going to do a pass removing BOOTCDROM (init warns and ignores about -C)…
	(void)subyte(--ucp, '-'); /* leading hyphen */			*flagp++ = 0;
	arg1 = ucp;			KASSERT(flagp <= &flags[0] + sizeof(flags), ("Overran flags"));
				error = exec_args_add_arg(&args, flags, UIO_SYSSPACE);
				if (error != 0)
				panic("%s: Can't add argv[0] %d", __func__, error);

	/*			/*
	* Move out the file name (also arg 0).
	*/
	ucp -= pathlen;
	copyout(path, ucp, pathlen);
	arg0 = ucp;

	/*
	* Move out the arg pointers.
	*/
	uap = (char **)rounddown2((intptr_t)ucp, sizeof(intptr_t));
	(void)suword((caddr_t)--uap, (long)0); /* terminator */
	(void)suword((caddr_t)--uap, (long)(intptr_t)arg1);
	(void)suword((caddr_t)--uap, (long)(intptr_t)arg0);

	/*
	* Point at the arguments.
	*/
	args.fname = arg0;
	args.argv = uap;
	args.envv = NULL;

	/*
	* Now try to exec the program. If can't for any reason			* Now try to exec the program. If can't for any reason
	* other than it doesn't exist, complain.			* other than it doesn't exist, complain.
	*			*
	* Otherwise, return via fork_trampoline() all the way			* Otherwise, return via fork_trampoline() all the way
	* to user mode as init!			* to user mode as init!
	*/			*/
	if ((error = sys_execve(td, &args)) == EJUSTRETURN) {			if ((error = kern_execve(td, &args, NULL)) == EJUSTRETURN) {
				kibUnsubmitted Done Inline Actions error cannot be non-zero. You panic a line before. kib: error cannot be non-zero. You panic a line before.
	free(free_init_path, M_TEMP);			free(free_init_path, M_TEMP);
	TSEXIT();			TSEXIT();
	return;			return;
	}			}
	if (error != ENOENT)			if (error != ENOENT)
	printf("exec %s: error %d\n", path, error);			printf("exec %s: error %d\n", path, error);
	}			}
	free(free_init_path, M_TEMP);			free(free_init_path, M_TEMP);
	▲ Show 20 Lines • Show All 67 Lines • Show Last 20 Lines