netdev - inetpeer with create==0

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date:	Wed, 02 Mar 2011 20:45:45 -0800 (PST)
From:	David Miller <davem@...emloft.net>
To:	eric.dumazet@...il.com
CC:	netdev@...r.kernel.org
Subject: inetpeer with create==0

Eric, I was profiling the non-routing-cache case and something that stuck
out is the case of calling inet_getpeer() with create==0.

If an entry is not found, we have to redo the lookup under a spinlock
to make certain that a concurrent writer rebalancing the tree does
not "hide" an existing entry from us.

This makes the case of a create==0 lookup for a not-present entry
really expensive.  It is on the order of 600 cpu cycles on my
Niagara2.

I added a hack to not do the relookup under the lock when create==0
and it now costs less than 300 cycles.

This is now a pretty common operation with the way we handle COW'd
metrics, so I think it's definitely worth optimizing.

I looked at the generic radix tree implementation, and it supports
full RCU lookups in parallel with insert/delete.  It handles the race
case without the relookup under lock because it creates fixed paths
to "slots" where nodes live using shifts and masks.  So if a path
to a slot ever existed, it will always exist.

Take a look at lib/radix-tree.c and include/linux/radix-tree.h if
you are curious.

I think we should do something similar for inetpeer.  Currently we
cannot just use the existing generic radix-tree code because it only
supports indexes as large as "unsigned long" and we need to handle
128-bit ipv6 addresses.
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html