From: David Miller <davem@davemloft.net> Date: 2012-07-20 21:25:05
[ Ok I'm going to be a little bit cranky, and I think I deserve it.
I'm basically not going to go through the multi-hour rebase and
retest process again, as it's hit the point of diminishing returns
as NOBODY is giving me test results but I can guarentee that
EVERYONE will bitch and complain when I push this into net-next and
it breaks their favorite feature. If you can't be bothered to test
these changes, I'm honestly going to tell people to take a hike and
fix it themselves. I simply don't care if you don't care enough to
test changes of this magnitude to make sure your favorite setup
still works.
To say that I'm disappointed with the amount of testing feedback
after posting more than a dozen iterations of this delicate patch
set would be an understatement. I can think of only one person who
actually tested one iteration of these patches and gave feedback.
And meanwhile I've personally reviewed, tested, and signed off on
everyone else's work WITHOUT DELAY during this entire process.
I've pulled 25 hour long hacking shifts to make that a reality, so
that my routing cache removal work absolutely would not impact or
delay the patch submissions of any other networking developer. And
I can't even get a handful of testers with some feedback? You
really have to be kidding me.. ]
The ipv4 routing cache is non-deterministic, performance wise, and is
subject to reasonably easy to launch denial of service attacks.
The routing cache works great for well behaved traffic, and the world
was a much friendlier place when the tradeoffs that led to the routing
cache's design were considered.
What it boils down to is that the performance of the routing cache is
a product of the traffic patterns seen by a system rather than being a
product of the contents of the routing tables. The former of which is
controllable by external entitites.
Even for "well behaved" legitimate traffic, high volume sites can see
hit rates in the routing cache of only ~%10.
The general flow of this patch series is that first the routing cache
is removed. We build a completely new rtable entry every lookup
request.
Next we make some simplifications due to the fact that removing the
routing cache causes several members of struct rtable to become no
longer necessary.
Then we need to make some amends such that we can legally cache
pre-constructed routes in the FIB nexthops. Firstly, we need to
invalidate routes which are hit with nexthop exceptions. Secondly we
have to change the semantics of rt->rt_gateway such that zero means
that the destination is on-link and non-zero otherwise.
Now that the preparations are ready, we start caching precomputed
routes in the FIB nexthops. Output and input routes need different
kinds of care when determining if we can legally do such caching or
not. The details are in the commit log messages for those changes.
The patch series then winds down with some more struct rtable
simplifications and other tidy ups that remove unnecessary overhead.
On a SPARC-T3 output route lookups are ~876 cycles. Input route
lookups are ~1169 cycles with rpfilter disabled, and about ~1468
cycles with rpfilter enabled.
These measurements were taken with the kbench_mod test module in the
net_test_tools GIT tree:
git://git.kernel.org/pub/scm/linux/kernel/git/davem/net_test_tools.git
That GIT tree also includes a udpflood tester tool and stresses
route lookups on packet output.
For example, on the same SPARC-T3 system we can run:
time ./udpflood -l 10000000 10.2.2.11
with routing cache:
real 1m21.955s user 0m6.530s sys 1m15.390s
without routing cache:
real 1m31.678s user 0m6.520s sys 1m25.140s
Performance undoubtedly can easily be improved further.
For example fib_table_lookup() performs a lot of excessive
computations with all the masking and shifting, some of it
conditionalized to deal with edge cases.
Also, Eric's no-ref optimization for input route lookups can be
re-instated for the FIB nexthop caching code path. I would be really
pleased if someone would work on that.
In fact anyone suitable motivated can just fire up perf on the loading
of the test net_test_tools benchmark kernel module. I spend much of
my time going:
bash# perf record insmod ./kbench_mod.ko dst=172.30.42.22 src=74.128.0.1 iif=2
bash# perf report
Thanks to helpful feedback from Joe Perches, Eric Dumazet, Ben
Hutchings, and others.
Signed-off-by: David S. Miller <davem@davemloft.net>
From: Eric Dumazet <hidden> Date: 2012-07-20 22:06:05
On Fri, 2012-07-20 at 14:25 -0700, David Miller wrote:
[ Ok I'm going to be a little bit cranky, and I think I deserve it.
I'm basically not going to go through the multi-hour rebase and
retest process again, as it's hit the point of diminishing returns
as NOBODY is giving me test results but I can guarentee that
EVERYONE will bitch and complain when I push this into net-next and
it breaks their favorite feature. If you can't be bothered to test
these changes, I'm honestly going to tell people to take a hike and
fix it themselves. I simply don't care if you don't care enough to
test changes of this magnitude to make sure your favorite setup
still works.
To say that I'm disappointed with the amount of testing feedback
after posting more than a dozen iterations of this delicate patch
set would be an understatement. I can think of only one person who
actually tested one iteration of these patches and gave feedback.
And meanwhile I've personally reviewed, tested, and signed off on
everyone else's work WITHOUT DELAY during this entire process.
I've pulled 25 hour long hacking shifts to make that a reality, so
that my routing cache removal work absolutely would not impact or
delay the patch submissions of any other networking developer. And
I can't even get a handful of testers with some feedback? You
really have to be kidding me.. ]
Hmm, ok, please give me few hours to make some tests ;)
(Apparently we choke on neighbour entries count.
entries = atomic_inc_return(&tbl->entries) - 1;
We need a percpu_counter ? Or something is wrong ?
What do you mean we choke on it? Does it exceed the thresholds
and we start garbage-collecting?
That would indicate a leak, or we are creating new neigh entries when
we shouldn't be, ie. we're not comparing the keys in the hash table
entries correctly during the lookup in net/ipv4/ip_output.c
(Apparently we choke on neighbour entries count.
entries = atomic_inc_return(&tbl->entries) - 1;
We need a percpu_counter ? Or something is wrong ?
What do you mean we choke on it? Does it exceed the thresholds
and we start garbage-collecting?
That would indicate a leak, or we are creating new neigh entries when
we shouldn't be, ie. we're not comparing the keys in the hash table
entries correctly during the lookup in net/ipv4/ip_output.c
I see the problem, we get the key wrong during neigh creation for
loopback.
I'll fix this, thanks.
(Apparently we choke on neighbour entries count.
entries = atomic_inc_return(&tbl->entries) - 1;
We need a percpu_counter ? Or something is wrong ?
What do you mean we choke on it? Does it exceed the thresholds
and we start garbage-collecting?
That would indicate a leak, or we are creating new neigh entries when
we shouldn't be, ie. we're not comparing the keys in the hash table
entries correctly during the lookup in net/ipv4/ip_output.c
I see the problem, we get the key wrong during neigh creation for
loopback.
I'll fix this, thanks.
This should do it:
====================
[PATCH] ipv4: Fix neigh lookup keying over loopback/point-to-point devices.
We were using a special key "0" for all loopback and point-to-point
device neigh lookups under ipv4, but we wouldn't use that special
key for the neigh creation.
So basically we'd make a new neigh at each and every lookup :-)
This special case to use only one neigh for these device types
is of dubious value, so just remove it entirely.
Reported-by: Eric Dumazet <redacted>
Signed-off-by: David S. Miller <davem@davemloft.net>
---
include/net/arp.h | 3 ---
1 file changed, 3 deletions(-)
From: Eric Dumazet <hidden> Date: 2012-07-21 05:40:13
On Fri, 2012-07-20 at 16:13 -0700, David Miller wrote:
quoted hunk
====================
[PATCH] ipv4: Fix neigh lookup keying over loopback/point-to-point devices.
We were using a special key "0" for all loopback and point-to-point
device neigh lookups under ipv4, but we wouldn't use that special
key for the neigh creation.
So basically we'd make a new neigh at each and every lookup :-)
This special case to use only one neigh for these device types
is of dubious value, so just remove it entirely.
Reported-by: Eric Dumazet <redacted>
Signed-off-by: David S. Miller <davem@davemloft.net>
---
include/net/arp.h | 3 ---
1 file changed, 3 deletions(-)
On 20 July 2012 14:25, David Miller [off-list ref] wrote:
On a SPARC-T3 output route lookups are ~876 cycles. Input route
lookups are ~1169 cycles with rpfilter disabled, and about ~1468
cycles with rpfilter enabled.
These measurements were taken with the kbench_mod test module in the
net_test_tools GIT tree:
...
In fact anyone suitable motivated can just fire up perf on the loading
of the test net_test_tools benchmark kernel module. I spend much of
my time going:
bash# perf record insmod ./kbench_mod.ko dst=172.30.42.22 src=74.128.0.1 iif=2
bash# perf report
Dave,
I have been running your routing removal patches for the past 3 days
(upgraded yesterday to latest set including the 17th patch you sent in
response to Eric's comment) and have not seen any issues (crashes
etc).
I used the kbench_mod module in net_test_tools for testing. Averaging
after 16 runs (with 4 samples in each run), I get the following for
output route lookups
(ip_route_output_key):
with route-removal patches: average of 544 cycles with min and max
of 511 and 721
without patches: (commit fa0afcd10 ) : average of 211 cycles with
min and max of 196 and 266
Apart from time spent in fib_table_lookup(), it seems time is also
spent in check_leaf(). I assume this is expected behavior.
Here are 2 sample perf outputs (I have appended the kbench outputs to
each file)
With patches applied:
# ========
# captured on: Sat Jul 21 23:49:43 2012
# hostname : vijaynsu
# os release : 3.5.0-rc7vns+
# perf version : 3.4.13690.gfda9f
# arch : x86_64
# nrcpus online : 8
# nrcpus avail : 8
# cpudesc : Intel(R) Xeon(R) CPU E5320 @ 1.86GHz
# cpuid : GenuineIntel,6,15,11
# total memory : 16407032 kB
# cmdline : /usr/src/net-next/tools/perf/perf record insmod
./kbench_mod.ko dst=172.27.231.128 src=172.27.231.28
# event : name = cycles, type = 0, config = 0x0, config1 = 0x0,
config2 = 0x0, excl_usr = 0, excl_kern = 0, id = { 1, 2, 3, 4, 5, 6,
7, 8 }
# HEADER_CPU_TOPOLOGY info available, use -I to display
# ========
#
# Samples: 458 of event 'cycles'
# Event count (approx.): 209175177
#
# Overhead Command Shared Object Symbol
# ........ ....... ................. .............................
#
40.62% insmod [kernel.kallsyms] [k] fib_table_lookup
24.38% insmod [kernel.kallsyms] [k] __ip_route_output_key
12.33% insmod [kernel.kallsyms] [k] check_leaf
9.29% insmod [kernel.kallsyms] [k] dst_release
6.43% insmod [kernel.kallsyms] [k] __ip_dev_find
2.67% insmod [edac_core] [k] 0x000000000000c1d7
1.33% insmod [kernel.kallsyms] [k] ip_route_output_flow
0.70% insmod [kernel.kallsyms] [k] copy_user_generic_string
0.46% insmod [kernel.kallsyms] [k] path_openat
0.41% insmod [kernel.kallsyms] [k] clear_page_c
0.38% insmod libc-2.11.1.so [.] _dl_addr
0.23% insmod [kernel.kallsyms] [k] native_write_msr_safe
0.22% insmod [kernel.kallsyms] [k] rcu_irq_enter
0.22% insmod [kernel.kallsyms] [k] mem_cgroup_count_vm_event
0.19% insmod [kernel.kallsyms] [k] do_mpage_readpage
0.12% insmod [kernel.kallsyms] [k] math_state_restore
0.02% insmod [kernel.kallsyms] [k] stop_one_cpu
#
# (For a higher level overview, try: perf report --sort comm,dso)
#
Jul 21 23:49:43 vijaynsu kernel: [ 146.382382] kbench:
Jul 21 23:49:43 vijaynsu kernel: [ 146.382382] flow
[IIF(0),OIF(0),MARK(0x00000000),D(172.27.231.128),S(172.27.231.28),TOS(0x00)]
Jul 21 23:49:43 vijaynsu kernel: [ 146.382388] kbench: sizeof(struct
rtable)==176
Jul 21 23:49:43 vijaynsu kernel: [ 146.409943] kbench:
ip_route_output_key tdiff: 546
Jul 21 23:49:43 vijaynsu kernel: [ 146.437490] kbench:
ip_route_output_key tdiff: 546
Jul 21 23:49:43 vijaynsu kernel: [ 146.465064] kbench:
ip_route_output_key tdiff: 511
Jul 21 23:49:43 vijaynsu kernel: [ 146.492615] kbench:
ip_route_output_key tdiff: 672
--------------
Without patches applied : (omitting hardware info)
# Overhead Command Shared Object Symbol
# ........ ....... ................. ............................
#
46.47% insmod [kernel.kallsyms] [k] __ip_route_output_key
17.71% insmod [kernel.kallsyms] [k] dst_release
15.51% insmod [kernel.kallsyms] [k] local_bh_enable
5.92% insmod [kvm] [k] 0x00000000000771ea
4.92% insmod [kernel.kallsyms] [k] local_bh_disable
2.37% insmod [kernel.kallsyms] [k] ip_route_output_flow
1.80% insmod [kernel.kallsyms] [k] clear_page_c
1.32% insmod [kernel.kallsyms] [k] find_get_page
1.31% insmod [kernel.kallsyms] [k] page_remove_rmap
1.15% insmod [kernel.kallsyms] [k] copy_user_generic_string
0.59% insmod [kernel.kallsyms] [k] trace_module_notify
0.59% insmod [kernel.kallsyms] [k] free_pcppages_bulk
0.25% insmod [kernel.kallsyms] [k] __do_fault
0.05% insmod [kernel.kallsyms] [k] wait_for_common
0.02% insmod [kernel.kallsyms] [k] finish_task_switch
0.00% insmod [kernel.kallsyms] [k] native_write_msr_safe
#
# (For a higher level overview, try: perf report --sort comm,dso)
#
Jul 21 23:33:09 vijaynsu kernel: [13465.736545] kbench:
Jul 21 23:33:09 vijaynsu kernel: [13465.736545] flow
[IIF(0),OIF(0),MARK(0x00000000),D(172.27.231.128),S(172.27.231.28),TOS(0x00)]
Jul 21 23:33:09 vijaynsu kernel: [13465.736551] kbench: sizeof(struct
rtable)==216
Jul 21 23:33:09 vijaynsu kernel: [13465.746394] kbench:
ip_route_output_key tdiff: 231
Jul 21 23:33:09 vijaynsu kernel: [13465.756229] kbench:
ip_route_output_key tdiff: 210
Jul 21 23:33:09 vijaynsu kernel: [13465.766062] kbench:
ip_route_output_key tdiff: 196
Jul 21 23:33:09 vijaynsu kernel: [13465.775894] kbench:
ip_route_output_key tdiff: 196
Thanks,
Vijay
I have been running your routing removal patches for the past 3 days
(upgraded yesterday to latest set including the 17th patch you sent in
response to Eric's comment) and have not seen any issues (crashes
etc).
Thanks for testing.
Apart from time spent in fib_table_lookup(), it seems time is also
spent in check_leaf(). I assume this is expected behavior.
Here are 2 sample perf outputs (I have appended the kbench outputs to
each file)
Yes, the two biggest hogs will be fib_table_lookup() and check_leaf().
check_leaf() is expensive largely because that's where we write the
fib_result block, which is a structure on the fib_lookup() caller's
stack.
Your perf traces roughly approximate mine.
Thanks.
From: Paweł Staszewski <hidden> Date: 2012-07-23 18:02:59
W dniu 2012-07-23 09:15, Eric Dumazet pisze:
On Sun, 2012-07-22 at 17:39 -0700, David Miller wrote:
quoted
Just FYI, I'm pushing this work out to net-next now.
--
Excellent !
Thanks a lot David
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Yes
Excellent work.
I make some real life tests with 10Gbit traffic and make some rdos.
With kernel 3.4.5 when I reach 6M routing cache entries - traffic is not
forwarded - on my hardware with 64G RAM
With kernel - 3.5.0-rc7-next-20120720 + David M. patches - route cache
removal + fix
Traffic is forwarder all the time at speed 8.2Mpps RX from traffic
generator and 8.2Mpps TX to the sink
Also I see performance improvement.
With kernel 3.4.5 I can reach maximum od 7.5Mpps with my hardware
And with kernel 3.5.0-rc7-next-20120720 i can reach 8.2Mpps - forwarding
UDP performance - can be more - but my TX pktgen that use 6 cores can't
do more.
Really thanks for this :)
BR
Paweł Staszewski
From: Alexander Duyck <hidden> Date: 2012-07-25 23:02:46
On Fri, Jul 20, 2012 at 2:25 PM, David Miller [off-list ref] wrote:
[ Ok I'm going to be a little bit cranky, and I think I deserve it.
I'm basically not going to go through the multi-hour rebase and
retest process again, as it's hit the point of diminishing returns
as NOBODY is giving me test results but I can guarentee that
EVERYONE will bitch and complain when I push this into net-next and
it breaks their favorite feature. If you can't be bothered to test
these changes, I'm honestly going to tell people to take a hike and
fix it themselves. I simply don't care if you don't care enough to
test changes of this magnitude to make sure your favorite setup
still works.
To say that I'm disappointed with the amount of testing feedback
after posting more than a dozen iterations of this delicate patch
set would be an understatement. I can think of only one person who
actually tested one iteration of these patches and gave feedback.
And meanwhile I've personally reviewed, tested, and signed off on
everyone else's work WITHOUT DELAY during this entire process.
I've pulled 25 hour long hacking shifts to make that a reality, so
that my routing cache removal work absolutely would not impact or
delay the patch submissions of any other networking developer. And
I can't even get a handful of testers with some feedback? You
really have to be kidding me.. ]
Sorry for not responding sooner but I have been on vacation for the
last few days.
I had been testing the patches over the last couple of weeks but I
didn't really feel like I could provide any input of value since I
don't have a strong understanding of the routing stack internals, and
because my test case tends to focus on small packet routing with a
very artificial work flow. I saw an overall drop in performance. I
had attributed to the fact that with so few flows I was exploiting the
routing cache to it's maximum potential, and had not explored it much
further.
My test consists of a SmartBits w/ a 10Gb/s port connected back to
back with one port on an 82599 adapter. I have the SmartBits
generating up to 16 64byte packet flows, each flow is filtered through
an ntuple filter to a specific queue, and each queue is pinned to a
specific CPU. The flows all have a unique source address but the same
destination address. The port doing the routing has two subnets. We
receive packets on the first subnet and then transmit them back out on
the second. I have set-up a static ARP entry for the destination
address in order to avoid the need for ARP address translation since
we are sending such a heavy packet load. My kernel config is stripped
down and does not include netfilter support.
Since your patches are in I have started to re-run my tests. I am
seeing a significant drop in throughput with 8 flows which I expected,
however it looks like one of the biggest issues I am seeing is that
the dst_hold and dst_release calls seem to be causing some serious
cache thrash. I was at 12.5Mpps w/ 8 flows before the patches, after
your patches it drops to 8.3Mpps. If I increase the number of queues
I am using to 16 the throughput drops off to something like 3.3Mpps.
Prior to your patches being applied the top 3 CPU consumers were
ixgbe_poll at around 10%, ixgbe_xmit_frame_ring at around 5%, and
__netif_receive_skb at around 5%. Below is the latest perf results
for 8 flows/queues after your patches:
14.52% [k] __write_lock_failed
10.68% [k] ip_route_input (75% of hits on dst_hold call)
10.18% [k] fib_table_lookup
6.04% [k] ixgbe_poll
5.80% [k] dst_release
4.14% [k] __netif_receive_skb
3.55% [k] _raw_spin_lock
2.84% [k] ip_forward
2.58% [k] ixgbe_xmit_frame_ring
I am also seeing routing fail periodically. I will be moving at rates
listed above and suddenly drop to single digits packets per second.
When this occurs the trace completely changes and __write_lock_failed
jumps to over 90% of the CPU cycles. It seems to occur more often if
I increase the number of CPUs in use while routing. Below is the call
graph I recorded for the function from perf to show the function calls
that are leading to the issue:
14.52% [k] __write_lock_failed
|
|--99.92%-- _raw_write_lock_bh
| __neigh_event_send
| neigh_resolve_output
| ip_finish_output
| ip_output
| ip_forward
| ip_rcv
| __netif_receive_skb
| netif_receive_skb
| napi_skb_finish
| napi_gro_receive
| ixgbe_poll
| net_rx_action
| __do_softirq
| run_ksoftirqd
| kthread
| kernel_thread_helper
--0.08%-- [...]
I am trying to figure out what can be done, but as I said I am not
that familiar with the internals of the IP routing stack itself. If
you need more data let me know and I can see about performing whatever
test, or altering my configuration as needed.
Thanks,
Alex
Since your patches are in I have started to re-run my tests. I am
seeing a significant drop in throughput with 8 flows which I expected,
however it looks like one of the biggest issues I am seeing is that
the dst_hold and dst_release calls seem to be causing some serious
cache thrash. I was at 12.5Mpps w/ 8 flows before the patches, after
your patches it drops to 8.3Mpps.
Yes, this is something we knew would start happening.
One idea is to make cached dsts be per-cpu in the nexthops.
I am also seeing routing fail periodically.
Every 30 seconds by chance? :-)
I will be moving at rates listed above and suddenly drop to single
digits packets per second. When this occurs the trace completely
changes and __write_lock_failed jumps to over 90% of the CPU cycles.
It's probably happening when the nexthop ARP entry expires.
Since your patches are in I have started to re-run my tests. I am
seeing a significant drop in throughput with 8 flows which I expected,
however it looks like one of the biggest issues I am seeing is that
the dst_hold and dst_release calls seem to be causing some serious
cache thrash. I was at 12.5Mpps w/ 8 flows before the patches, after
your patches it drops to 8.3Mpps.
Yes, this is something we knew would start happening.
One idea is to make cached dsts be per-cpu in the nexthops.
Actually I think what really kills your case is the removal of the
noref path for route lookups. I'll work on a patch to restore that
in the case where we use cached routes from the FIB nexthops.
Since your patches are in I have started to re-run my tests. I am
seeing a significant drop in throughput with 8 flows which I expected,
however it looks like one of the biggest issues I am seeing is that
the dst_hold and dst_release calls seem to be causing some serious
cache thrash. I was at 12.5Mpps w/ 8 flows before the patches, after
your patches it drops to 8.3Mpps.
Yes, this is something we knew would start happening.
One idea is to make cached dsts be per-cpu in the nexthops.
Actually I think what really kills your case is the removal of the
noref path for route lookups. I'll work on a patch to restore that
in the case where we use cached routes from the FIB nexthops.
Alex, here is something I tossed together, does it help with the
dst_hold()/dst_release() overhead at all?
@@ -258,8 +258,8 @@ static void ip_expire(unsigned long arg)/* skb dst is stale, drop it, and perform route lookup again */skb_dst_drop(head);iph=ip_hdr(head);-err=ip_route_input(head,iph->daddr,iph->saddr,-iph->tos,head->dev);+err=ip_route_input_noref(head,iph->daddr,iph->saddr,+iph->tos,head->dev);if(err)gotoout_rcu_unlock;
Since your patches are in I have started to re-run my tests. I am
seeing a significant drop in throughput with 8 flows which I expected,
however it looks like one of the biggest issues I am seeing is that
the dst_hold and dst_release calls seem to be causing some serious
cache thrash. I was at 12.5Mpps w/ 8 flows before the patches, after
your patches it drops to 8.3Mpps.
Yes, this is something we knew would start happening.
One idea is to make cached dsts be per-cpu in the nexthops.
Actually I think what really kills your case is the removal of the
noref path for route lookups. I'll work on a patch to restore that
in the case where we use cached routes from the FIB nexthops.
Alex, here is something I tossed together, does it help with the
dst_hold()/dst_release() overhead at all?
I downloaded your patch, applied it, rebuilt the kernel, and then
rebooted. However after the reboot I am unable to access the system
remotely. It looks like I will have to wait until I get into the
office tomorrow to figure out what happened to the system.
I will get you an update on if it helped or not once I figure out what
happened in the morning.
Thanks,
Alex
I downloaded your patch, applied it, rebuilt the kernel, and then
rebooted. However after the reboot I am unable to access the system
remotely. It looks like I will have to wait until I get into the
office tomorrow to figure out what happened to the system.
I will get you an update on if it helped or not once I figure out what
happened in the morning.
Ok, I may have flubbed the patch, I'll let you know if I find any bugs
in it.
Thanks.
Since your patches are in I have started to re-run my tests. I am
seeing a significant drop in throughput with 8 flows which I expected,
however it looks like one of the biggest issues I am seeing is that
the dst_hold and dst_release calls seem to be causing some serious
cache thrash. I was at 12.5Mpps w/ 8 flows before the patches, after
your patches it drops to 8.3Mpps.
Yes, this is something we knew would start happening.
One idea is to make cached dsts be per-cpu in the nexthops.
Actually I think what really kills your case is the removal of the
noref path for route lookups. I'll work on a patch to restore that
in the case where we use cached routes from the FIB nexthops.
Alex, here is something I tossed together, does it help with the
dst_hold()/dst_release() overhead at all?
@@ -1216,9 +1215,15 @@ static void rt_cache_route(struct fib_nh *nh, struct rtable *rt) prev = cmpxchg(p, orig, rt); if (prev == orig) {- dst_clone(&rt->dst); if (orig)- call_rcu_bh(&orig->dst.rcu_head, rt_release_rcu);+ rt_free(orig);+ } else {+ /* Routes we intend to cache in the FIB nexthop have+ * the DST_NOCACHE bit set. However, if we are+ * unsuccessful at storing this route into the cache+ * we really need to clear that bit.+ */+ rt->dst.flags &= ~DST_NOCACHE; } }
Not sure why you removed the dst_clone(&rt->dst) ?
If it is not needed, we might need to release a reference in the else {}
clause, no ?
On Wed, 2012-07-25 at 17:54 -0700, David Miller wrote:
quoted
@@ -1216,9 +1215,15 @@ static void rt_cache_route(struct fib_nh *nh, struct rtable *rt) prev = cmpxchg(p, orig, rt); if (prev == orig) {- dst_clone(&rt->dst); if (orig)- call_rcu_bh(&orig->dst.rcu_head, rt_release_rcu);+ rt_free(orig);+ } else {+ /* Routes we intend to cache in the FIB nexthop have+ * the DST_NOCACHE bit set. However, if we are+ * unsuccessful at storing this route into the cache+ * we really need to clear that bit.+ */+ rt->dst.flags &= ~DST_NOCACHE; } }
Not sure why you removed the dst_clone(&rt->dst) ?
Because "cached" dst objects have no reference count. When such a
cached dst is "released", it is dst_free()'d instead of
dst_release()'d.
If it is not needed, we might need to release a reference in the else {}
clause, no ?
Nope. 'rt' has a reference count of one, which is for the caller, not
for this cached location.
On Wed, 2012-07-25 at 17:54 -0700, David Miller wrote:
quoted
@@ -1216,9 +1215,15 @@ static void rt_cache_route(struct fib_nh *nh, struct rtable *rt) prev = cmpxchg(p, orig, rt); if (prev == orig) {- dst_clone(&rt->dst); if (orig)- call_rcu_bh(&orig->dst.rcu_head, rt_release_rcu);+ rt_free(orig);+ } else {+ /* Routes we intend to cache in the FIB nexthop have+ * the DST_NOCACHE bit set. However, if we are+ * unsuccessful at storing this route into the cache+ * we really need to clear that bit.+ */+ rt->dst.flags &= ~DST_NOCACHE; } }
Not sure why you removed the dst_clone(&rt->dst) ?
Because "cached" dst objects have no reference count. When such a
cached dst is "released", it is dst_free()'d instead of
dst_release()'d.
quoted
If it is not needed, we might need to release a reference in the else {}
clause, no ?
Nope. 'rt' has a reference count of one, which is for the caller, not
for this cached location.
But isnt DST_NOCACHE intent reverted then ?
like you meant :
+ } else {
+ /* Routes we intend to cache in the FIB nexthop have
+ * the DST_NOCACHE bit unset. However, if we are
+ * unsuccessful at storing this route into the cache
+ * we really need to set that bit.
+ */
+ rt->dst.flags |= DST_NOCACHE;
}
But isnt DST_NOCACHE intent reverted then ?
like you meant :
+ } else {
+ /* Routes we intend to cache in the FIB nexthop have
+ * the DST_NOCACHE bit unset. However, if we are
+ * unsuccessful at storing this route into the cache
+ * we really need to set that bit.
+ */
+ rt->dst.flags |= DST_NOCACHE;
}
Indeed, thanks for catching this bug.
Here's a new version of the patch, as I found another error. In
fib_semantics.c, we have to change dst_release() to dst_free() for the
liberation the nexthop cached routes.
@@ -258,8 +258,8 @@ static void ip_expire(unsigned long arg)/* skb dst is stale, drop it, and perform route lookup again */skb_dst_drop(head);iph=ip_hdr(head);-err=ip_route_input(head,iph->daddr,iph->saddr,-iph->tos,head->dev);+err=ip_route_input_noref(head,iph->daddr,iph->saddr,+iph->tos,head->dev);if(err)gotoout_rcu_unlock;
From: Eric Dumazet <hidden> Date: 2012-07-26 09:12:37
On Thu, 2012-07-26 at 01:47 -0700, David Miller wrote:
Indeed, thanks for catching this bug.
Here's a new version of the patch, as I found another error. In
fib_semantics.c, we have to change dst_release() to dst_free() for the
liberation the nexthop cached routes.
Excellent, I did tests here and this seems ok to me
Tested-by: Eric Dumazet <edumazet@google.com>
Acked-by: Eric Dumazet <edumazet@google.com>
From: Eric Dumazet <hidden> Date: 2012-07-26 17:02:44
On Mon, 2012-07-23 at 19:54 +0200, Paweł Staszewski wrote:
I make some real life tests with 10Gbit traffic and make some rdos.
With kernel 3.4.5 when I reach 6M routing cache entries - traffic is not
forwarded - on my hardware with 64G RAM
With kernel - 3.5.0-rc7-next-20120720 + David M. patches - route cache
removal + fix
Traffic is forwarder all the time at speed 8.2Mpps RX from traffic
generator and 8.2Mpps TX to the sink
Also I see performance improvement.
With kernel 3.4.5 I can reach maximum od 7.5Mpps with my hardware
And with kernel 3.5.0-rc7-next-20120720 i can reach 8.2Mpps - forwarding
UDP performance - can be more - but my TX pktgen that use 6 cores can't
do more.
Really thanks for this :)
In real life, with TCP traffic, make sure you
set /proc/sys/net/ipv4/ip_early_demux to 0
But isnt DST_NOCACHE intent reverted then ?
like you meant :
+ } else {
+ /* Routes we intend to cache in the FIB nexthop have
+ * the DST_NOCACHE bit unset. However, if we are
+ * unsuccessful at storing this route into the cache
+ * we really need to set that bit.
+ */
+ rt->dst.flags |= DST_NOCACHE;
}
Indeed, thanks for catching this bug.
Here's a new version of the patch, as I found another error. In
fib_semantics.c, we have to change dst_release() to dst_free() for the
liberation the nexthop cached routes.
I tested this patch and it looks like it runs, but still has the same
performance issue. I did some digging into the annotation for
ip_route_intput_noref and it seems like the issue is that I am hitting
the dst_hold call in __mkroute_input.
You were correct about the ARP entry. It looks like I had messed up
my test script and it wasn't putting the static ARP entry back in.
I'm amazed it was even working since my SmartBits system doesn't
normally even reply to ARPs.
Thanks,
Alex
From: Eric Dumazet <hidden> Date: 2012-07-26 17:31:04
On Thu, 2012-07-26 at 10:18 -0700, Alexander Duyck wrote:
I tested this patch and it looks like it runs, but still has the same
performance issue. I did some digging into the annotation for
ip_route_intput_noref and it seems like the issue is that I am hitting
the dst_hold call in __mkroute_input.
David suggested a percpu cache.
nh_rth_input would be allocated by alloc_percpu(struct dst *)
I can work on this.
From: Eric Dumazet <hidden> Date: 2012-07-26 17:36:21
On Thu, 2012-07-26 at 19:31 +0200, Eric Dumazet wrote:
On Thu, 2012-07-26 at 10:18 -0700, Alexander Duyck wrote:
quoted
I tested this patch and it looks like it runs, but still has the same
performance issue. I did some digging into the annotation for
ip_route_intput_noref and it seems like the issue is that I am hitting
the dst_hold call in __mkroute_input.
David suggested a percpu cache.
nh_rth_input would be allocated by alloc_percpu(struct dst *)
I can work on this.
Wait a minute, on input we should use the noref trick too.
From: Eric Dumazet <hidden> Date: 2012-07-26 17:43:58
On Thu, 2012-07-26 at 19:36 +0200, Eric Dumazet wrote:
On Thu, 2012-07-26 at 19:31 +0200, Eric Dumazet wrote:
quoted
On Thu, 2012-07-26 at 10:18 -0700, Alexander Duyck wrote:
quoted
I tested this patch and it looks like it runs, but still has the same
performance issue. I did some digging into the annotation for
ip_route_intput_noref and it seems like the issue is that I am hitting
the dst_hold call in __mkroute_input.
David suggested a percpu cache.
nh_rth_input would be allocated by alloc_percpu(struct dst *)
I can work on this.
Wait a minute, on input we should use the noref trick too.
From: Eric Dumazet <hidden> Date: 2012-07-26 17:48:21
On Thu, 2012-07-26 at 19:43 +0200, Eric Dumazet wrote:
On Thu, 2012-07-26 at 19:36 +0200, Eric Dumazet wrote:
quoted
On Thu, 2012-07-26 at 19:31 +0200, Eric Dumazet wrote:
quoted
On Thu, 2012-07-26 at 10:18 -0700, Alexander Duyck wrote:
quoted
I tested this patch and it looks like it runs, but still has the same
performance issue. I did some digging into the annotation for
ip_route_intput_noref and it seems like the issue is that I am hitting
the dst_hold call in __mkroute_input.
David suggested a percpu cache.
nh_rth_input would be allocated by alloc_percpu(struct dst *)
I can work on this.
Wait a minute, on input we should use the noref trick too.
Something like : (on top of latest David patch)
Sorry updated patch : (missing skb_dst_set() before 'out' label)
From: Alexander Duyck <hidden> Date: 2012-07-26 18:06:46
On Thu, Jul 26, 2012 at 10:43 AM, Eric Dumazet [off-list ref] wrote:
quoted hunk
On Thu, 2012-07-26 at 19:36 +0200, Eric Dumazet wrote:
quoted
On Thu, 2012-07-26 at 19:31 +0200, Eric Dumazet wrote:
quoted
On Thu, 2012-07-26 at 10:18 -0700, Alexander Duyck wrote:
quoted
I tested this patch and it looks like it runs, but still has the same
performance issue. I did some digging into the annotation for
ip_route_intput_noref and it seems like the issue is that I am hitting
the dst_hold call in __mkroute_input.
David suggested a percpu cache.
nh_rth_input would be allocated by alloc_percpu(struct dst *)
I can work on this.
Wait a minute, on input we should use the noref trick too.
@@ -1423,7 +1422,7 @@ static int __mkroute_input(struct sk_buff *skb,if(!itag){rth=FIB_RES_NH(*res).nh_rth_input;if(rt_cache_valid(rth)){-dst_hold(&rth->dst);+skb_dst_set_noref(skb,&rth->dst);gotoout;}do_cache=true;
@@ -1451,7 +1450,6 @@ static int __mkroute_input(struct sk_buff *skb,rt_set_nexthop(rth,daddr,res,NULL,res->fi,res->type,itag);out:-*result=rth;err=0;cleanup:returnerr;
@@ -1463,21 +1461,13 @@ static int ip_mkroute_input(struct sk_buff *skb,structin_device*in_dev,__be32daddr,__be32saddr,u32tos){-structrtable*rth=NULL;-interr;-#ifdef CONFIG_IP_ROUTE_MULTIPATHif(res->fi&&res->fi->fib_nhs>1)fib_select_multipath(res);#endif/* create a routing cache entry */-err=__mkroute_input(skb,res,in_dev,daddr,saddr,tos,&rth);-if(err)-returnerr;--skb_dst_set(skb,&rth->dst);-return0;+return__mkroute_input(skb,res,in_dev,daddr,saddr,tos);}/*
With your changes in place I see an increase from 7.5Mpps to 9.9Mpps
for 8 queues, and increasing the queues to 9 gets me up to 11Mpps even
if the 9th queue is on another node. This is a HUGE improvement over
what we had before.
The only remaining overhead that has been introduced with the recent
changes appears to be the fib_table_lookup which doesn't have any hot
spots that jump out at me. The performance is in-line with what I was
seeing when I was randomly generating source IPs from a fairly large
set so I suspect this is just the expected behaviour without a routing
cache in place.
Thanks,
Alex
From: Alexander Duyck <hidden> Date: 2012-07-26 18:26:27
On Thu, Jul 26, 2012 at 10:48 AM, Eric Dumazet [off-list ref] wrote:
On Thu, 2012-07-26 at 19:43 +0200, Eric Dumazet wrote:
quoted
On Thu, 2012-07-26 at 19:36 +0200, Eric Dumazet wrote:
quoted
On Thu, 2012-07-26 at 19:31 +0200, Eric Dumazet wrote:
quoted
On Thu, 2012-07-26 at 10:18 -0700, Alexander Duyck wrote:
quoted
I tested this patch and it looks like it runs, but still has the same
performance issue. I did some digging into the annotation for
ip_route_intput_noref and it seems like the issue is that I am hitting
the dst_hold call in __mkroute_input.
David suggested a percpu cache.
nh_rth_input would be allocated by alloc_percpu(struct dst *)
I can work on this.
Wait a minute, on input we should use the noref trick too.
Something like : (on top of latest David patch)
Sorry updated patch : (missing skb_dst_set() before 'out' label)
The previous results were with a slight modifications to your earlier
patch. With this patch applied I am seeing 10.4Mpps with 8 queues,
reaching a maximum of 11.6Mpps with 9 queues.
When we have a final version for this patch let me know and I will
give it a quick run and throw in my tested by.
Thanks,
Alex
I did some digging into the annotation for ip_route_intput_noref and
it seems like the issue is that I am hitting the dst_hold call in
__mkroute_input.
We shouldn't be building any routes in __mkroute_input except for the
very first packet, we should be instead using the cached route in the
FIB info nexthop.
Something's not right.
On Thu, 2012-07-26 at 19:36 +0200, Eric Dumazet wrote:
quoted
On Thu, 2012-07-26 at 19:31 +0200, Eric Dumazet wrote:
quoted
On Thu, 2012-07-26 at 10:18 -0700, Alexander Duyck wrote:
quoted
I tested this patch and it looks like it runs, but still has the same
performance issue. I did some digging into the annotation for
ip_route_intput_noref and it seems like the issue is that I am hitting
the dst_hold call in __mkroute_input.
David suggested a percpu cache.
nh_rth_input would be allocated by alloc_percpu(struct dst *)
I can work on this.
Wait a minute, on input we should use the noref trick too.
Something like : (on top of latest David patch)
Grrr, I only got the local routes didn't I? :-)
That would explain everything.
The previous results were with a slight modifications to your earlier
patch. With this patch applied I am seeing 10.4Mpps with 8 queues,
reaching a maximum of 11.6Mpps with 9 queues.
For fun you might want to see what this patch does for your tests,
it should cut the number of fib_table_lookup() calls roughly in half.
@@ -160,7 +160,7 @@ struct net_device *__ip_dev_find(struct net *net, __be32 addr, bool devref)/* Fallback to FIB local table so that communication*overloopbacksubnetswork.*/-local=fib_get_table(net,RT_TABLE_LOCAL);+local=fib_get_table(net,RT_TABLE_MAIN);if(local&&!fib_table_lookup(local,&fl4,&res,FIB_LOOKUP_NOREF)&&res.type==RTN_LOCAL)
@@ -52,16 +52,10 @@ static int __net_init fib4_rules_init(struct net *net){structfib_table*local_table,*main_table;-local_table=fib_trie_table(RT_TABLE_LOCAL);-if(local_table==NULL)-return-ENOMEM;-main_table=fib_trie_table(RT_TABLE_MAIN);if(main_table==NULL)gotofail;-hlist_add_head_rcu(&local_table->tb_hlist,-&net->ipv4.fib_table_hash[TABLE_LOCAL_INDEX]);hlist_add_head_rcu(&main_table->tb_hlist,&net->ipv4.fib_table_hash[TABLE_MAIN_INDEX]);return0;
@@ -169,7 +163,7 @@ static inline unsigned int __inet_dev_addr_type(struct net *net,if(ipv4_is_multicast(addr))returnRTN_MULTICAST;-local_table=fib_get_table(net,RT_TABLE_LOCAL);+local_table=fib_get_table(net,RT_TABLE_MAIN);if(local_table){ret=RTN_UNICAST;rcu_read_lock();
@@ -712,11 +706,7 @@ static void fib_magic(int cmd, int type, __be32 dst, int dst_len, struct in_ifad},};-if(type==RTN_UNICAST)-tb=fib_new_table(net,RT_TABLE_MAIN);-else-tb=fib_new_table(net,RT_TABLE_LOCAL);-+tb=fib_new_table(net,RT_TABLE_MAIN);if(tb==NULL)return;
The previous results were with a slight modifications to your earlier
patch. With this patch applied I am seeing 10.4Mpps with 8 queues,
reaching a maximum of 11.6Mpps with 9 queues.
For fun you might want to see what this patch does for your tests,
it should cut the number of fib_table_lookup() calls roughly in half.
So with your patch, Eric's patch, and this most recent patch we are
now at 11.8Mpps with 8 or 9 queues. At this point I am staring to hit
the hardware limits since 82599 will typically max out at about 12Mpps
w/ 9 queues.
Here is the latest perf results with all of these patches in place.
As you predicted your patch essentially cut the lookup overhead in
half:
10.65% [k] ixgbe_poll
7.77% [k] fib_table_lookup
6.21% [k] ixgbe_xmit_frame_ring
6.08% [k] __netif_receive_skb
4.41% [k] _raw_spin_lock
3.95% [k] kmem_cache_free
3.30% [k] build_skb
3.17% [k] memcpy
2.96% [k] dev_queue_xmit
2.79% [k] ip_finish_output
2.66% [k] kmem_cache_alloc
2.57% [k] check_leaf
2.52% [k] ip_route_input_noref
2.50% [k] netdev_alloc_frag
2.17% [k] ip_rcv
2.16% [k] __phys_addr
I will probably do some more poking around over the next few days in
order to get my head around the fib_table_lookup overhead.
Thanks,
Alex
The previous results were with a slight modifications to your earlier
patch. With this patch applied I am seeing 10.4Mpps with 8 queues,
reaching a maximum of 11.6Mpps with 9 queues.
For fun you might want to see what this patch does for your tests,
it should cut the number of fib_table_lookup() calls roughly in half.
So with your patch, Eric's patch, and this most recent patch we are
now at 11.8Mpps with 8 or 9 queues. At this point I am staring to hit
the hardware limits since 82599 will typically max out at about 12Mpps
w/ 9 queues.
Here is the latest perf results with all of these patches in place.
As you predicted your patch essentially cut the lookup overhead in
half:
10.65% [k] ixgbe_poll
7.77% [k] fib_table_lookup
6.21% [k] ixgbe_xmit_frame_ring
6.08% [k] __netif_receive_skb
4.41% [k] _raw_spin_lock
3.95% [k] kmem_cache_free
3.30% [k] build_skb
3.17% [k] memcpy
2.96% [k] dev_queue_xmit
2.79% [k] ip_finish_output
2.66% [k] kmem_cache_alloc
2.57% [k] check_leaf
2.52% [k] ip_route_input_noref
2.50% [k] netdev_alloc_frag
2.17% [k] ip_rcv
2.16% [k] __phys_addr
I will probably do some more poking around over the next few days in
order to get my head around the fib_table_lookup overhead.
Thanks,
Alex
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
The fib trie stats are global, you may want to either disable CONFIG_IP_FIB_TRIE_STATS
or convert them to per-cpu.
Here is the latest perf results with all of these patches in place.
As you predicted your patch essentially cut the lookup overhead in
half:
Ok good.
That patch is hard to make legitimate, I'd have to do a bit or work
before we could realize that change.
We can only combine the LOCAL and MAIN tables like that so long as
there are no overlaps in the routes covered by the two tables. We'd
also have to be sure to report the routes properly in dumps too.
I really wish we had never segregated these two tables, it's
completely pointless and hurts performance. But now we have to
accomodate this legacy.
Here is the latest perf results with all of these patches in place.
As you predicted your patch essentially cut the lookup overhead in
half:
Ok good.
That patch is hard to make legitimate, I'd have to do a bit or work
before we could realize that change.
We can only combine the LOCAL and MAIN tables like that so long as
there are no overlaps in the routes covered by the two tables. We'd
also have to be sure to report the routes properly in dumps too.
I really wish we had never segregated these two tables, it's
completely pointless and hurts performance. But now we have to
accomodate this legacy.
Any idea why these look-ups are so expensive in the first place? When
I dump fib_trie it doesn't look like I have much there. I would have
thought the table would be pretty static with just 8 flows all going
to the same destination address, but it seems like I was getting hit
with cache misses for some reason.
Thanks,
Alex
Any idea why these look-ups are so expensive in the first place? When
I dump fib_trie it doesn't look like I have much there. I would have
thought the table would be pretty static with just 8 flows all going
to the same destination address, but it seems like I was getting hit
with cache misses for some reason.
A lot of the overhead comes from write traffic that results from
filling in the "fib_result" structure onto the callers stack.
The return value from a fib_lookup() has far too many components. But
simplifying things is not easy.
From: David Miller <davem@davemloft.net> Date: 2012-07-27 06:02:50
From: David Miller <davem@davemloft.net>
Date: Thu, 26 Jul 2012 20:08:46 -0700 (PDT)
A lot of the overhead comes from write traffic that results from
filling in the "fib_result" structure onto the callers stack.
Here's the longer analysis of how things are now.
There are several components to a route lookup result, and struct
fib_result tries to encapsulate all of this.
Another aspect is that our route tables are broken up into different
datas tructures which reference each other, in order to save space.
So the actual objects in the FIB trie are fib_alias structures, and
those point to fib_info. There is a many to one relationship between
FIB trie nodes and fib_info objects.
The idea is that many routes have the same set of nexthops, metrics,
preferred source address, etc.
So one thing we return in the fib_result is a pointer to the fib_info
and an index into the nexthop array (nh_sel). That's why we have all
of these funny accessor's FIB_RES_X(res) which essentially provide
res.fi->fib_nh[res.nh_sel].X
Therefore one area of simplification would be to just return a pointer
to the FIB nexthop, rather than the fib_info pointer and the nexthop
index. We can get to the fib_info, if we need to, via the nh_parent
pointer of the nexthop.
It seems also that the res->scope value can be cribbed from the
fib_info as well.
res->type is embedded in the fib_alias we select hanging off of the
FIB trie node. And the res->prefixlen is taken from the FIB trie
node.
res->tclassid is problematic, because it comes from the FIB rules
tables rather than the FIB trie. We used to store a full FIB rules
pointer in the fib_result, but I reduced it down to just the u32
tclassid.
This whole area, as well as the FIB trie lookup itself, is an area
ripe for a large number of small micro-optimizations that in the end
make it's overhead much more reasonable.
Another thing I haven't mentioned is that another part of FIB trie's
overhead is that it does backtracking. The shorter prefixes sit at
the top of the trie, so when it traverses down it does so until it
can't get a match, then it walks back up to the root until it does
have a match.
From: Eric Dumazet <hidden> Date: 2012-07-27 10:01:29
From: Eric Dumazet <edumazet@google.com>
On Thu, 2012-07-26 at 23:02 -0700, David Miller wrote:
From: David Miller <davem@davemloft.net>
Date: Thu, 26 Jul 2012 20:08:46 -0700 (PDT)
quoted
A lot of the overhead comes from write traffic that results from
filling in the "fib_result" structure onto the callers stack.
Here's the longer analysis of how things are now.
There are several components to a route lookup result, and struct
fib_result tries to encapsulate all of this.
Another aspect is that our route tables are broken up into different
datas tructures which reference each other, in order to save space.
So the actual objects in the FIB trie are fib_alias structures, and
those point to fib_info. There is a many to one relationship between
FIB trie nodes and fib_info objects.
The idea is that many routes have the same set of nexthops, metrics,
preferred source address, etc.
So one thing we return in the fib_result is a pointer to the fib_info
and an index into the nexthop array (nh_sel). That's why we have all
of these funny accessor's FIB_RES_X(res) which essentially provide
res.fi->fib_nh[res.nh_sel].X
Therefore one area of simplification would be to just return a pointer
to the FIB nexthop, rather than the fib_info pointer and the nexthop
index. We can get to the fib_info, if we need to, via the nh_parent
pointer of the nexthop.
It seems also that the res->scope value can be cribbed from the
fib_info as well.
res->type is embedded in the fib_alias we select hanging off of the
FIB trie node. And the res->prefixlen is taken from the FIB trie
node.
res->tclassid is problematic, because it comes from the FIB rules
tables rather than the FIB trie. We used to store a full FIB rules
pointer in the fib_result, but I reduced it down to just the u32
tclassid.
This whole area, as well as the FIB trie lookup itself, is an area
ripe for a large number of small micro-optimizations that in the end
make it's overhead much more reasonable.
Another thing I haven't mentioned is that another part of FIB trie's
overhead is that it does backtracking. The shorter prefixes sit at
the top of the trie, so when it traverses down it does so until it
can't get a match, then it walks back up to the root until it does
have a match.
We also have cache line misses in this code, and we shouldn't have them
at all.
Following patch helps a lot in my case.
Thanks
[PATCH] ipv4: fib: avoid false sharing
Now IP route cache is removed, we should make sure fib structures
cant share cache lines with possibly often dirtied objects.
On x86, kmalloc-96 cache can be source of such problems.
Problem spotted with perf ... -e cache-misses ... while doing
a forwarding benchmark.
Signed-off-by: Eric Dumazet <edumazet@google.com>
---
include/net/ip_fib.h | 6 ++++++
net/ipv4/fib_frontend.c | 5 +----
net/ipv4/fib_semantics.c | 15 ++++++++-------
net/ipv4/fib_trie.c | 26 +++++++++-----------------
4 files changed, 24 insertions(+), 28 deletions(-)
@@ -1089,10 +1089,7 @@ static int __net_init ip_fib_net_init(struct net *net)interr;size_tsize=sizeof(structhlist_head)*FIB_TABLE_HASHSZ;-/* Avoid false sharing : Use at least a full cache line */-size=max_t(size_t,size,L1_CACHE_BYTES);--net->ipv4.fib_table_hash=kzalloc(size,GFP_KERNEL);+net->ipv4.fib_table_hash=fib_zalloc(size);if(net->ipv4.fib_table_hash==NULL)return-ENOMEM;
From: Eric W. Biederman <hidden> Date: 2012-07-27 14:53:17
Eric Dumazet [off-list ref] writes:
Now IP route cache is removed, we should make sure fib structures
cant share cache lines with possibly often dirtied objects.
On x86, kmalloc-96 cache can be source of such problems.
Signed-off-by: Eric Dumazet <edumazet@google.com>
+static inline void *fib_zalloc(size_t size)
+{
+ /* We want to avoid possible false sharing */
+ return kzalloc(max_t(size_t, 128, size), GFP_KERNEL);
Why the hard coded 128 here?
It seems more portable and obvious to do
return kzalloc(round_up(size, L1_CACHE_BYTES), GFP_KERNEL);
From: Eric Dumazet <hidden> Date: 2012-07-27 15:12:35
On Fri, 2012-07-27 at 07:53 -0700, Eric W. Biederman wrote:
Eric Dumazet [off-list ref] writes:
quoted
Now IP route cache is removed, we should make sure fib structures
cant share cache lines with possibly often dirtied objects.
On x86, kmalloc-96 cache can be source of such problems.
Signed-off-by: Eric Dumazet <edumazet@google.com>
quoted
+static inline void *fib_zalloc(size_t size)
+{
+ /* We want to avoid possible false sharing */
+ return kzalloc(max_t(size_t, 128, size), GFP_KERNEL);
Why the hard coded 128 here?
It seems more portable and obvious to do
return kzalloc(round_up(size, L1_CACHE_BYTES), GFP_KERNEL);
Its not that obvious, because some machines have an apparent
L1_CACHE_BYTES of 64, but hardware prefetching to 128 bytes
But using 2*L1_CACHE_BYTES as minimum allocation size might be overkill
on some arches with 256 bytes cache lines.
From: Eric W. Biederman <hidden> Date: 2012-07-27 16:23:26
Eric Dumazet [off-list ref] writes:
On Fri, 2012-07-27 at 07:53 -0700, Eric W. Biederman wrote:
quoted
Eric Dumazet [off-list ref] writes:
quoted
Now IP route cache is removed, we should make sure fib structures
cant share cache lines with possibly often dirtied objects.
On x86, kmalloc-96 cache can be source of such problems.
Signed-off-by: Eric Dumazet <edumazet@google.com>
quoted
+static inline void *fib_zalloc(size_t size)
+{
+ /* We want to avoid possible false sharing */
+ return kzalloc(max_t(size_t, 128, size), GFP_KERNEL);
Why the hard coded 128 here?
It seems more portable and obvious to do
return kzalloc(round_up(size, L1_CACHE_BYTES), GFP_KERNEL);
Its not that obvious, because some machines have an apparent
L1_CACHE_BYTES of 64, but hardware prefetching to 128 bytes
I am familiar. But does hardware prefetching make a difference
if your object is less than 64 bytes?
I don't believe only allocating 64 bytes will be a problem,
as no one else well be dirtying your cache line.
I suppose you could run into pathologies where your object
is 3*64 bytes in size, but your expression doesn't handle
that case either.
But using 2*L1_CACHE_BYTES as minimum allocation size might be overkill
on some arches with 256 bytes cache lines.
The other alternative to guarantee very good cache behavior is
to ensure you are allocating a power of two size up to some limit,
perhaps page size.
My point is the magic 128 likely requires an explicatory comment and I
think the net result is you have encoded something fragile that is good
for testing but that will in the fullness of time do strange things that
will be easy to overlook.
Eric
From: Eric Dumazet <hidden> Date: 2012-07-27 16:28:58
On Fri, 2012-07-27 at 09:23 -0700, Eric W. Biederman wrote:
I am familiar. But does hardware prefetching make a difference
if your object is less than 64 bytes?
Apparently yes, if the prefetch touches a dirtied neighbour cache line.
I don't believe only allocating 64 bytes will be a problem,
as no one else well be dirtying your cache line.
I suppose you could run into pathologies where your object
is 3*64 bytes in size, but your expression doesn't handle
that case either.
Sure, but in most cases fib objects are under 128 bytes.
The other alternative to guarantee very good cache behavior is
to ensure you are allocating a power of two size up to some limit,
perhaps page size.
Good idea.
My point is the magic 128 likely requires an explicatory comment and I
think the net result is you have encoded something fragile that is good
for testing but that will in the fullness of time do strange things that
will be easy to overlook.
From: Alexander Duyck <hidden> Date: 2012-07-27 19:06:47
On Fri, Jul 27, 2012 at 9:28 AM, Eric Dumazet [off-list ref] wrote:
On Fri, 2012-07-27 at 09:23 -0700, Eric W. Biederman wrote:
quoted
I am familiar. But does hardware prefetching make a difference
if your object is less than 64 bytes?
Apparently yes, if the prefetch touches a dirtied neighbour cache line.
quoted
I don't believe only allocating 64 bytes will be a problem,
as no one else well be dirtying your cache line.
I suppose you could run into pathologies where your object
is 3*64 bytes in size, but your expression doesn't handle
that case either.
Sure, but in most cases fib objects are under 128 bytes.
quoted
The other alternative to guarantee very good cache behavior is
to ensure you are allocating a power of two size up to some limit,
perhaps page size.
Good idea.
quoted
My point is the magic 128 likely requires an explicatory comment and I
think the net result is you have encoded something fragile that is good
for testing but that will in the fullness of time do strange things that
will be easy to overlook.
Sure, I'll send a v2, thanks.
I tested out v1 of your patch and didn't seem much of a change in my
test environment. I figure I will spend most of today going through
the code trying to figure out what is causing the issues I am seeing
and why your changes had no effect on my setup.
Thanks,
Alex
From: David Miller <davem@davemloft.net> Date: 2012-07-28 04:15:29
From: David Miller <davem@davemloft.net>
Date: Thu, 26 Jul 2012 23:02:46 -0700 (PDT)
Therefore one area of simplification would be to just return a pointer
to the FIB nexthop, rather than the fib_info pointer and the nexthop
index. We can get to the fib_info, if we need to, via the nh_parent
pointer of the nexthop.
So I'm about to post an RFC set of patches which show this kind
of simplification. It gets fib_result down to two members:
u32 tclassid;
struct fib_nh *nh;
If I could get rid of that tclassid it would be really nice. But
that's hard because the tclassid is fetched from the fib_rule and
all of that lookup path is abstracted behind a common layer
that's shared between ipv4 and ipv6 so it's a bit of work changing
arg conventions.
These changes help, but only ever so slightly, in my testing.
From: Alexander Duyck <hidden> Date: 2012-07-28 05:45:51
On Fri, Jul 27, 2012 at 9:15 PM, David Miller [off-list ref] wrote:
From: David Miller <davem@davemloft.net>
Date: Thu, 26 Jul 2012 23:02:46 -0700 (PDT)
quoted
Therefore one area of simplification would be to just return a pointer
to the FIB nexthop, rather than the fib_info pointer and the nexthop
index. We can get to the fib_info, if we need to, via the nh_parent
pointer of the nexthop.
So I'm about to post an RFC set of patches which show this kind
of simplification. It gets fib_result down to two members:
u32 tclassid;
struct fib_nh *nh;
If I could get rid of that tclassid it would be really nice. But
that's hard because the tclassid is fetched from the fib_rule and
all of that lookup path is abstracted behind a common layer
that's shared between ipv4 and ipv6 so it's a bit of work changing
arg conventions.
These changes help, but only ever so slightly, in my testing.
I probably won't be able to do any real testing for the patches until
Monday, or at least I may let somebody else test the patches first
just to make sure they don't panic the system before I do anything
with them.
Thanks,
Alex