kernel/linux
0
Fork 0
mirror of https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/ synced 2026-10-24 19:10:26 +00:00
Code Issues Releases Packages Activity
linux/net/ipv4
History
Florian Westphal f5bba514af netfilter: x_tables: speed up jump target validation 
[ Upstream commit f4dc77713f ]

The dummy ruleset I used to test the original validation change was broken,
most rules were unreachable and were not tested by mark_source_chains().

In some cases rulesets that used to load in a few seconds now require
several minutes.

sample ruleset that shows the behaviour:

echo "*filter"
for i in $(seq 0 100000);do
        printf ":chain_%06x - [0:0]\n" $i
done
for i in $(seq 0 100000);do
   printf -- "-A INPUT -j chain_%06x\n" $i
   printf -- "-A INPUT -j chain_%06x\n" $i
   printf -- "-A INPUT -j chain_%06x\n" $i
done
echo COMMIT

[ pipe result into iptables-restore ]

This ruleset will be about 74mbyte in size, with ~500k searches
though all 500k[1] rule entries. iptables-restore will take forever
(gave up after 10 minutes)

Instead of always searching the entire blob for a match, fill an
array with the start offsets of every single ipt_entry struct,
then do a binary search to check if the jump target is present or not.

After this change ruleset restore times get again close to what one
gets when reverting 3647234101 (~3 seconds on my workstation).

[1] every user-defined rule gets an implicit RETURN, so we get
300k jumps + 100k userchains + 100k returns -> 500k rule entries

Fixes: 3647234101 ("netfilter: x_tables: validate targets of jumps")
Reported-by: Jeff Wu <wujiafu@gmail.com>
Tested-by: Jeff Wu <wujiafu@gmail.com>
Signed-off-by: Florian Westphal <fw@strlen.de>
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
Signed-off-by: Florian Westphal <fw@strlen.de>
Signed-off-by: Sasha Levin <alexander.levin@verizon.com>
History 2016-08-03 11:34:46 -04:00
..
netfilter netfilter: x_tables: speed up jump target validation 2016-08-03 11:34:46 -04:00
af_inet.c net: add validation for the socket syscall protocol argument 2016-01-15 18:41:51 -05:00
ah4.c ipsec: Remove obsolete MAX_AH_AUTH_LEN 2014-09-18 10:54:36 +02:00
arp.c arp: Do not perturb drop profiles with ignored ARP packets 2014-09-28 17:30:35 -04:00
cipso_ipv4.c cipso: don't use IPCB() to locate the CIPSO IP option 2015-03-06 14:52:59 -08:00
datagram.c ipv6: lock socket in ip6_datagram_connect() 2015-09-28 18:57:01 -04:00
devinet.c ipv4: Don't do expensive useless work during inetdev destroy. 2016-07-12 08:47:35 -04:00
esp4.c esp4: Use the IPsec protocol multiplexer API 2014-02-25 07:04:17 +01:00
fib_frontend.c ipv4: Don't do expensive useless work during inetdev destroy. 2016-07-12 08:47:35 -04:00
fib_lookup.h ipv4: make fib_detect_death static 2013-12-28 17:01:46 -05:00
fib_rules.c ipv4: Fix incorrect error code when adding an unreachable route 2014-11-16 14:11:45 -05:00
fib_semantics.c ipv4: fix nexthop attlen check in fib_nh_match 2014-10-14 15:59:37 -04:00
fib_trie.c list: fix order of arguments for hlist_add_after(_rcu) 2014-08-06 18:01:24 -07:00
fou.c fou: clean up socket with kfree_rcu 2016-01-15 18:41:52 -05:00
geneve.c udptunnels: Call handle_offloads after inserting vlan tag. 2015-04-27 17:13:41 -04:00
gre_demux.c net: Fix GRE RX to use skb_transport_header for GRE header offset 2014-09-08 15:23:05 -07:00
gre_offload.c ipv6: gre: support SIT encapsulation 2015-12-03 10:18:20 -05:00
icmp.c icmp: add a global rate limitation 2014-09-23 12:47:38 -04:00
igmp.c ipv6: mld: fix add_grhead skb_over_panic for devs with large MTUs 2014-11-16 16:55:06 -05:00
inet_connection_sock.c ipv4: make ip_local_reserved_ports per netns 2014-05-14 15:31:45 -04:00
inet_diag.c inet_diag: fix possible overflow in inet_diag_dump_one_icsk() 2015-03-24 08:22:19 -04:00
inet_fragment.c inet: frags: remove the WARN_ON from inet_evict_bucket 2014-10-29 15:21:30 -04:00
inet_hashtables.c net: use reciprocal_scale() helper 2014-08-23 12:21:21 -07:00
inet_lro.c lro: remove dead code 2013-12-29 16:34:25 -05:00
inet_timewait_sock.c tcp/dccp: remove twchain 2013-10-08 23:19:24 -04:00
inetpeer.c inet: remove dead inetpeer sequence code 2014-09-08 16:42:42 -07:00
ip_forward.c ip_forward: Drop frames with attached skb->sk 2015-05-11 07:07:55 -04:00
ip_fragment.c inet: frags: fix defragmented packet's IP header for af_packet 2015-09-28 18:57:01 -04:00
ip_gre.c gre: fix the inner mac header in nbma tunnel xmit path 2015-01-27 08:29:32 -08:00
ip_input.c net: Fix memory leak if TPROXY used with TCP early demux 2014-01-27 16:22:11 -08:00
ip_options.c ipv4: rename ip_options_echo to __ip_options_echo() 2014-09-28 16:35:42 -04:00
ip_output.c udp: only allow UFO for packets from SOCK_DGRAM sockets 2015-03-14 15:37:14 -04:00
ip_sockglue.c ip: zero sockaddr returned on error queue 2015-02-26 17:49:00 -08:00
ip_tunnel.c ip_tunnel: fix ipv4 pmtu check to honor inner ip header df 2015-09-27 12:18:54 -04:00
ip_tunnel_core.c ipv4: fix a potential use after free in ip_tunnel_core.c 2014-10-17 23:45:26 -04:00
ip_vti.c ip_vti/ip6_vti: Preserve skb->mark after rcv_cb call 2015-08-27 13:26:14 -04:00
ipcomp.c ipcomp4: Use the IPsec protocol multiplexer API 2014-02-25 07:04:17 +01:00
ipconfig.c ipconfig: Use time_before 2014-08-22 12:23:11 -07:00
ipip.c net: better IFF_XMIT_DST_RELEASE support 2014-10-07 13:22:11 -04:00
ipmr.c net: ipmr: fix static mfc/dev leaks on table destruction 2015-12-14 12:19:25 -05:00
Kconfig openvswitch: fix a compilation error when CONFIG_INET is not setW! 2014-10-07 00:10:49 -04:00
Makefile net: Add Geneve tunneling protocol driver 2014-10-06 00:32:20 -04:00
netfilter.c netfilter: remove double colon 2014-02-19 11:41:25 +01:00
ping.c ipv4: Missing sk_nulls_node_init() in ping_unhash(). 2015-05-11 07:07:54 -04:00
proc.c inet: frag: don't account number of fragment queues 2014-07-27 22:34:36 -07:00
protocol.c net: Export inet_offloads and inet6_offloads 2014-09-19 17:15:31 -04:00
raw.c ipv4: Make IP_MULTICAST_ALL and IP_MSFILTER work on raw sockets 2014-07-23 15:13:26 -07:00
route.c route: do not cache fib route info on local routes with oif 2016-07-12 08:48:07 -04:00
syncookies.c Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/net 2014-10-18 09:31:37 -07:00
sysctl_net_ipv4.c ipv4: disable BH when changing ip local port range 2015-12-14 12:17:30 -05:00
tcp.c tcp: Do not call tcp_fastopen_reset_cipher from interrupt context 2015-07-05 10:12:59 -04:00
tcp_bic.c tcp: whitespace fixes 2014-09-01 18:12:45 -07:00
tcp_cong.c tcp: fix child sockets to use system default congestion control if not set 2015-06-15 14:26:53 -04:00
tcp_cubic.c tcp_cubic: do not set epoch_start in the future 2016-04-23 16:45:18 -04:00
tcp_dctcp.c net: tcp: add DCTCP congestion control algorithm 2014-09-29 00:13:10 -04:00
tcp_diag.c tcp: whitespace fixes 2014-09-01 18:12:45 -07:00
tcp_fastopen.c tcp: Do not call tcp_fastopen_reset_cipher from interrupt context 2015-07-05 10:12:59 -04:00
tcp_highspeed.c tcp: whitespace fixes 2014-09-01 18:12:45 -07:00
tcp_htcp.c tcp: whitespace fixes 2014-09-01 18:12:45 -07:00
tcp_hybla.c tcp: whitespace fixes 2014-09-01 18:12:45 -07:00
tcp_illinois.c tcp: whitespace fixes 2014-09-01 18:12:45 -07:00
tcp_input.c tcp: initialize tp->copied_seq in case of cross SYN connection 2015-12-14 12:19:25 -05:00
tcp_ipv4.c net: fix IP early demux races 2016-01-15 18:41:51 -05:00
tcp_lp.c tcp: remove in_flight parameter from cong_avoid() methods 2014-05-03 19:23:07 -04:00
tcp_memcontrol.c percpu_counter: add @gfp to percpu_counter_init() 2014-09-08 09:51:29 +09:00
tcp_metrics.c tcp: convert cached rtt from usec to jiffies when feeding initial rto 2016-07-12 08:47:27 -04:00
tcp_minisocks.c tcp: fix child sockets to use system default congestion control if not set 2015-06-15 14:26:53 -04:00
tcp_offload.c net: Remove gso_send_check as an offload callback 2014-09-26 00:22:47 -04:00
tcp_output.c tcp: refresh skb timestamp at retransmit time 2016-07-12 08:48:16 -04:00
tcp_probe.c tcp: whitespace fixes 2014-09-01 18:12:45 -07:00
tcp_scalable.c tcp: whitespace fixes 2014-09-01 18:12:45 -07:00
tcp_timer.c tcp: abort orphan sockets stalling on zero window probes 2014-10-01 16:27:52 -04:00
tcp_vegas.c tcp: whitespace fixes 2014-09-01 18:12:45 -07:00
tcp_vegas.h net: ipv4/ipv6: Remove extern from function prototypes 2013-10-19 19:12:11 -04:00
tcp_veno.c tcp: whitespace fixes 2014-09-01 18:12:45 -07:00
tcp_westwood.c net: tcp: split ack slow/fast events from cwnd_event 2014-09-29 00:13:10 -04:00
tcp_yeah.c tcp_yeah: don't set ssthresh below 2 2016-02-15 15:42:44 -05:00
tunnel4.c net: Convert printks to pr_<level> 2012-03-11 23:42:51 -07:00
udp.c ipv4: fix broadcast packets reception 2016-07-12 08:47:40 -04:00
udp_diag.c udp_diag: Fix socket skipping within chain 2015-02-26 17:49:01 -08:00
udp_impl.h net: ipv4/ipv6: Remove extern from function prototypes 2013-10-19 19:12:11 -04:00
udp_offload.c net: gso: use feature flag argument in all protocol gso handlers 2014-10-20 12:38:12 -04:00
udp_tunnel.c udp-tunnel: Add a few more UDP tunnel APIs 2014-09-19 15:57:15 -04:00
udplite.c net: Eliminate no_check from protosw 2014-05-23 16:28:53 -04:00
xfrm4_input.c xfrm4: Add IPsec protocol multiplexer 2014-02-25 07:04:16 +01:00
xfrm4_mode_beet.c ipv4: ERROR: code indent should use tabs where possible 2013-12-26 13:43:21 -05:00
xfrm4_mode_transport.c [IPSEC]: Use IPv6 calling convention as the convention for x->mode->output 2007-10-10 16:55:54 -07:00
xfrm4_mode_tunnel.c inetpeer: get rid of ip_id_count 2014-06-02 11:00:41 -07:00
xfrm4_output.c Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/net 2014-05-24 00:32:30 -04:00
xfrm4_policy.c xfrm: dst_entries_init() per-net dst_ops 2016-02-15 15:42:46 -05:00
xfrm4_protocol.c xfrm4: Remove duplicate semicolon 2014-06-30 07:49:47 +02:00
xfrm4_state.c inet: make no_pmtu_disc per namespace and kill ipv4_config 2013-12-18 16:58:20 -05:00
xfrm4_tunnel.c sit: add IPv4 over IPv4 support 2013-05-31 17:19:05 -07:00