Solving scalability issue: for chain list "name" searching.
Solving scalability issue: for chain list "name" searching.
Functions: iptcc_find_label(), iptc_is_chain().
Testing if a chain exist, requires a linearly walk of linked list with
chain-names (doing a strcmp(3) in each step). Giving a worst-case
runtime of O(n) where n is the number of chains.
Why is this important to fix?! If only called once, this should not be
a big concern, even-though the string compares are expensive.
The performance issue arise with many chains for example; when using
"iptables-restore", or when listing all "iptables -nL" rules, or when
using CPAN IPTables::libiptc.
Having 50k chains, the rule listing, with the command:
"./iptables -nL > /dev/null",
Without patch it takes approximately 5 minutes,
With the patch it takes 0.5 seconds.
Listing without patch:
real 4m49.426s
user 4m37.993s
sys 0m0.280s
Listing with patch:
real 0m0.558s
user 0m0.484s
sys 0m0.064s
How is it solved?!
The issue is solved introducing a new data structure, that allow us to
do binary search of chain names. Thus, reducing the worst-case runtime
to O(log n).
Being more specific:
The new data structure is called "chain index", which is an array with
pointers into the chain list, with CHAIN_INDEX_BUCKET_LEN spacing.
This facilitates the ability to speedup chain list searching, by find
a more optimal starting points when searching the linked list.
The runtime complexity is actually also affected by this "bucket" size
concept. Thus, O(log(n/k) + k) where k is CHAIN_INDEX_BUCKET_LEN.
A nice property of the chain index, is that the "bucket" list
length is max CHAIN_INDEX_BUCKET_LEN (when just build, inserts will
change this). Oppose to hashing, where the "bucket" list length can
vary a lot.
Peter Warasin [Tue, 15 Jan 2008 15:46:35 +0000 (15:46 +0000)]
Fix CONNMARK mask initialisation
This patch fixes the problem that the CONNMARK mask value
has been set to 0 whenever the CONNMARK target options were
not the last options to be processed.
It initalizes the mask value rather than setting it for
each parse.
Mike Frysinger [Wed, 19 Dec 2007 14:51:17 +0000 (14:51 +0000)]
iptables and NO_SHARED_LIBS/dlfcn.h
if NO_SHARED_LIBS is defined, then iptables shouldnt even include dlfcn.h.
otherwise you hit a build failure when using toolchains that do not provide
dlfcn.h because they do not support shared objects.
This patch is an improvment of r7098 (made by me).
Assuring compatibility between 1.4.0 and older versions,
regarding chain sorting.
Chains from kernel are already sorted, as they are inserted
sorted. But there exists an issue when shifting to 1.4.0
from an older version, as old versions allow last created
chain to be unsorted. This unsorted chain would survive in
1.4.0, as chains are now only sorted on creation.
This patch verifies that chains are sorted, if not it fixes the sorting.
Patrick McHardy [Mon, 3 Dec 2007 15:32:28 +0000 (15:32 +0000)]
Fix showing help text for matches/targets with revision as user
When running as a user iptables can't determine the highest supported
revision and exits. Assume all revision are supported in case we get
a EPERM. If the user is not showing the help text but trying to add
new rules he'll get EPERM later anyway.
iptables/libiptc perf issue: Sorting chain during pull-out
Performance optimize scalability issue:
Sorting chain during pull-out give worst-case runtime O(Chains2).
When pulling out the blob, every chain name is inserted alphabetically
into a linked list (by function iptc_insert_chain()). The problem
with this approach is that the chain names delivered in the blob is
already sorted (as we push it back to the kernel sorted).
This cause chain parsing to always process every element in the chain
list and finish with a tail add. Causing worst-case runtime O(C2/2)
for alphabetically sorting of chains.
The patch solves this by only calling iptc_insert_chain() when
creating new chains.
Jan Engelhardt [Sun, 25 Nov 2007 15:27:56 +0000 (15:27 +0000)]
iptables: always print mask in iptables-save
iptables prints the mask as a prefix length if it is valid;
This patch makes iptables-save do the same.
Also, iptables-save will always print "/32" in the "-s addr/32"
case now. This reduces the amount of code external parsing scripts
need to provide to properly parse iptables-save output.
ip6tables-save already does the right thing, so no change there.
Signed-off-by: Jan Engelhardt <jengelh@computergmbh.de>
Jesper Brouer [Sun, 25 Nov 2007 15:22:18 +0000 (15:22 +0000)]
Fix make/compile error for iptables-1.4.0rc1
Fixing a make/compile issue with iptables, release candidate 1.4.0rc1,
which has existed since SVN changeset 6920. This patch adds ip_tables.h
and ip6_tables.h, and updates x_tables.h, taken from Linus'es git tree.
Changeset 6920 added the include file x_tables.h from kernel source, but
didn't add ip_tables.h and ip6_tables.h.
At some point (Tue Nov 14 19:48:48 2006, by Yasuyuki Kozakai) these
kernel headers where changed, which actually removes certain
depencencies from ip_tables.h and ip6_tables.h to x_tables.h.
If compiling will fail, with old kernel headers (ip_tables.h and
ip6_tables.h) available in systems include path, because they depend on
certaine defines in x_tables.h with is missing in the version in SVN.
Hann-Huei Chiou [Tue, 23 Oct 2007 14:22:34 +0000 (14:22 +0000)]
let DO_MULTI=1 work for ip6tables* binaries
When defining DO_MULTI=1 in Makefile, only iptables is built as
a single multipurpose binary. This patch makes ip6tables also be
built in the same manner.
Max Kellermann [Wed, 17 Oct 2007 16:36:49 +0000 (16:36 +0000)]
[PATCH iptables] print warnings to stderr
iptables prints some of its error messages and warnings to stdout.
This patch applies to svn r7075 and will make iptables print
diagnostic messages to stderr instead.
make print-extensions doesn't show libxt_* extensions
In extensions/Makefile the variable PFX_EXT_SLIB_OPTS is not appended to
OPTIONALS, therefor 'make print-extensions' doesn't show any optional
libxt_* extension.
Jan Engelhardt [Thu, 4 Oct 2007 16:29:39 +0000 (16:29 +0000)]
Unique symbols 6/6
Give symbols of libxt targets unique names (3/3).
Adds unique prefixes to all functions (most of them - especially the hook
functions) so that debugging programs can unambiguously map a symbol to an
address. Also unifies the names of the xtables_match/xtables_target structs,
(based upon libxt_connmark.c/libip6t_*.c).
Jan Engelhardt [Thu, 4 Oct 2007 16:29:21 +0000 (16:29 +0000)]
Unique names 5/6
Give symbols of libxt matches unique names (3/3).
Adds unique prefixes to all functions (most of them - especially the hook
functions) so that debugging programs can unambiguously map a symbol to an
address. Also unifies the names of the xtables_match/xtables_target structs,
(based upon libxt_connmark.c/libip6t_*.c).
Jan Engelhardt [Thu, 4 Oct 2007 16:29:00 +0000 (16:29 +0000)]
Unique names 4/6
Give symbols of libxt targets unique names (2/3).
Adds unique prefixes to all functions (most of them - especially the hook
functions) so that debugging programs can unambiguously map a symbol to an
address. Also unifies the names of the xtables_match/xtables_target structs,
(based upon libxt_connmark.c/libip6t_*.c).
Jan Engelhardt [Thu, 4 Oct 2007 16:28:39 +0000 (16:28 +0000)]
Unique names 3/6
Give symbols of libxt matches unique names (2/3).
Adds unique prefixes to all functions (most of them - especially the hook
functions) so that debugging programs can unambiguously map a symbol to an
address. Also unifies the names of the xtables_match/xtables_target structs,
(based upon libxt_connmark.c/libip6t_*.c).
Jan Engelhardt [Thu, 4 Oct 2007 16:27:30 +0000 (16:27 +0000)]
Unique names 2/6
Give symbols of libxt targets unique names (1/3).
Adds unique prefixes to all functions (most of them - especially the hook
functions) so that debugging programs can unambiguously map a symbol to an
address. Also unifies the names of the xtables_match/xtables_target structs,
(based upon libxt_connmark.c/libip6t_*.c).
Jan Engelhardt [Thu, 4 Oct 2007 16:27:07 +0000 (16:27 +0000)]
Unique symbols 1/6
Give symbols of libxt matches unique names (1/3).
Adds unique prefixes to all functions (most of them - especially the hook
functions) so that debugging programs can unambiguously map a symbol to an
address. Also unifies the names of the xtables_match/xtables_target structs,
(based upon libxt_connmark.c/libip6t_*.c).
iptables (up to 0927 snapshot) keeps complaining of "Couldn't
load (or find, if NO_SHARED_LIBS=1) match `u32'. After comparing
with other libxt_*.c, I found that there's no member ".family"
in the "u32_reg" structure, while ".family = AF_INET6" exists
in "u32_reg6"
Jan Engelhardt [Sun, 23 Sep 2007 15:17:42 +0000 (15:17 +0000)]
Add the libxt_time iptables match
This is libipt_time from POM-ng enhanced by the following:
* day-of-month support (for example "match on the 15th of each month")
* inversion support for --weekdays and --monthdays
* match against UTC or local timezone
* a manpage
Signed-off-by: Jan Engelhardt <jengelh@computergmbh.de>
Jan Engelhardt [Wed, 19 Sep 2007 12:59:33 +0000 (12:59 +0000)]
Fix u32 warnings
warning: format '%ld' expects type 'long int', but argument 3 has type 'int'.
With %u alone, you would get "but arg-start is long" warnings on x64.
With %lu, you would get "but arg-start is int" on x86.
Fix it up by explicitly deciding for one (%u and cast to unsigned int)
and using that.
Makefile for man pages of xtables extensions (Laszlo Attila Toth <panther@balabit.hu>)
* no extra target/match by default :)
* man page of fix modules (PF_EXT_SLIB etc.) plus optional
(...SLIB_OPTS) modules generated, but not all.
* because of the previous one I had to rename PF_EXT_SE_SLIB to
PF_EXT_SELINUX_SLIB etc. as a non-optional variable, original
PF_EXT_SE_SLIB gets the value of PF_EXT_SELINUX_SLIB if DO_SELINUX is
set to 1.
projects / thirdparty / iptables.git / log
