| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
Signed-off-by: Jesper Dangaard Brouer <hawk@comx.dk>
|
| |
|
|
|
|
| |
Introduce a counter for number of user defined chains.
Signed-off-by: Jesper Dangaard Brouer <hawk@comx.dk>
|
| |
|
|
|
|
|
| |
The two functions are obvious candidates for inlining.
Using gprof(1) shows that they actually affects performance.
Signed-off-by: Jesper Dangaard Brouer <hawk@comx.dk>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
Signed-off-by: Jesper Dangaard Brouer <hawk@comx.dk>
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
Signed-off-by: Jesper Dangaard Brouer <hawk@comx.dk>
|
| | |
|
| |
|
|
| |
prototypes
|
| |
|
|
|
|
|
| |
The recent kernel has compat layer for iptables. It doesn't have
compat layer for libipq and ip6tables, but ip6tables with
KERNEL_64_USERSPACE_32 is still broken. We should fix kernel instead of
fixing them if and when we want use their 32bit binary with 64bit kernel.
|
| |
|
|
|
|
| |
counters (Andy Gay <andy@andynet.net>)
https://bugzilla.netfilter.org/bugzilla/show_bug.cgi?id=502
|
| |
|
|
|
|
|
|
|
| |
Correcting a chain references increment bug in libiptc.
The bug lies in function iptc_delete_entry() / TC_DELETE_ENTRY. The
problem is the construction of "r" the rule entry, that is used for
comparison. The problem is that the function iptcc_map_target()
increase the target chains references count.
|
| |
|
|
| |
Fixes "Unknown error 4294967295" message (bugzilla #460).
|
| | |
|
| |
|
|
| |
1), the error message "Unknown error 4294967295" is displayed; (Closes: #460)
|
| |
|
|
|
| |
- Cleanup error path of TC_COMMIT()
- Correctly propagate errors of setsockopt to calling function
|
| |
|
|
| |
<list-netfilter@debarth.co.uk>
|
| | |
|
| | |
|
| |
|
|
|
|
| |
and the other one needs more investigation to why valgrind is complaining.
Noticed and reverted by Phil Oester.
|
| | |
|
| |
|
|
|
|
|
|
| |
in all major TC_* functions. This is necessary because in certain cases, an error return from a function that doesn't set 'iptc_fn' will conflict with a function-specific error return from one that does, causing TC_STRERROR() to return the wrong error string. This ensures that the right one will be returned.
- Implements a simple reference counter for the netlink socket global variable 'sockfd'; this is necessary for IPTables::IPv4, where multiple tables (filter, nat, mangle, untracked) may be opened at one time. The way libiptc does it in the official version causes previously-opened tables to break such that attempts to commit changes will fail.
- Adds a couple of memset() invocations in TC_COMMIT, based on past analysis with valgrind. It claimed that allocated structure were not being fully initialized, and adding the memset()s corrected this warning.
(Derrik Pates <demon@devrandom.net>)
|
| |
|
|
|
| |
Enhance MARK match with second revision.
Committed in anticipation of the kernel patch being applied.
|
| |
|
|
| |
delete-by-matching-rule (found by nfsim test).
|
| |
|
|
| |
Stolen from TC_DELETE_NUM_ENTRY.
|
| |
|
|
|
|
|
| |
Make target testing aware of different kinds of rules.
Change reverse logic: target_different now target_same.
Set type to MODULE in iptcc_map_target.
Add testcase for this.
|
| |
|
|
|
|
|
| |
(ie. without -O) on old kernels where ipt_get_target() was defined "extern inline". These days it's "static inline", and only developers build without -O anyway.
Fix up DUMP_ENTRIES a little, but remove calls: it only dumps the table as loaded, not the changed (cached) table, which is misleading.
Fix TC_DELETE_ENTRY: we need to use iptcc_map_target() before comparing, otherwise "-j DROP" (as an example) doesn't work.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
in a chain.
before:
insert 50k rules without any previous rules
real 0m1.314s
user 0m1.184s
sys 0m0.123s
insert 50k with one already existing rule
real 2m38.052s
user 2m37.296s
sys 0m0.353s
insert 50k rules in the middle of 20k already existing rules
real 2m43.831s
user 2m43.005s
sys 0m0.414s
delete rule #70000 10k times with 100k rules
real 1m37.990s
user 1m37.247s
sys 0m0.500s
after:
insert 50k without any previous rules
real 0m1.315s
user 0m1.184s
sys 0m0.125s
insert 50k with one already existing rule
real 0m1.313s
user 0m1.189s
sys 0m0.119s
insert 50k rules in the middle of 20k already existing rules
real 0m8.550s
user 0m8.327s
sys 0m0.197s
delete rule #70000 10k times with 100k rules
real 0m35.566s
user 0m35.062s
sys 0m0.416s
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
Do the same with TC_DELETE_NUM_ENTRY() when deleting the last rule.
My rule management script does both of these things in certain situations.
Created a file with 50.000 rules which my script converted into
iptables-restore format but inserting each rule with an index instead of
appending like the iptables-save output does. That took a while without this
optimization. Same thing when deleting the 45.000 last rules in that chain,
the script outputs deletes by number starting from the bottom.
Inserting or deleting (by number) in the middle of the chain is still O(n)
where n is the rulenumber where the insert/delete is taking place.
|
| | |
|
| |
|
|
|
| |
All jumps to nonexisting chains were believed to be jumps to builtin chains,
that's bad as it made it impossible to add rules with external targets.
|
| |
|
|
|
| |
Makes flushing of chains containing more than a few entries work without
potentially oopsing the kernel.
|
| | |
|
| | |
|
| |
|
|
|
|
|
| |
It checked if a rule existed on the position we were inserting to.
Thus inserting into an empty chain didn't work.
And it didn't care about the fact that the first rule in the chain has index 1
the rulenumer we get starts at 0...
|
| | |
|
| |
|
|
|
|
| |
Type was only set for standard targets.
Harald: please review.
|
| |
|
|
| |
ipt_get_entries plus the size
|
| | |
|
| |
|
|
| |
minutes to 1.255 seconds (!). Might still contain bugs, use with caution.
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| |
|
|
|
| |
Please report bugs to bugzilla, we need to fix this up before releasing
the next iptables version.
|
| |
|
|
|
|
| |
pointers. This is needed for my current libiptc optimization work, since
it needs the chain cache to still be correct after it has been reallocated
to a different address.
|
| |
|
|
| |
This shouldn't break anything, things were already broken.
|
| |
|
|
| |
Josefsson)
|
