[ipsec-next,0/4] xfrm: speed up policy insertions

Message

Florian Westphal Aug. 22, 2024, 1:04 p.m. UTC

Policy insertions do not scale well, due to both a lienar list walk
to find the insertion spot and another list walk to set the 'pos' value
(a tie-breaker to detect which policy is older when there is ambiguity
 as to which one should be matched).

First patch gets rid of the second list walk on insert.
Rest of the patches get rid of the insertion walk.

This list walk was only needed because when I moved the policy db
implementation to rbtree I retained the old insertion method for the
sake of XFRM_MIGRATE.

Switching that to tree-based lookup avoids the need for the full
list search.

After this, insertion of a policy is largely independent of the number
of pre-existing policies as long as they do not share the same source/
destination networks.

Note that this is compile tested only as I did not find any
tests for XFRM_MIGRATE.

Florian Westphal (4):
  selftests: add xfrm policy insertion speed test script
  xfrm: policy: don't iterate inexact policies twice at insert time
  xfrm: switch migrate to xfrm_policy_lookup_bytype
  xfrm: policy: remove remaining use of inexact list

 include/net/xfrm.h                            |   1 -
 net/xfrm/xfrm_policy.c                        | 201 ++++++++----------
 tools/testing/selftests/net/Makefile          |   2 +-
 .../selftests/net/xfrm_policy_add_speed.sh    |  83 ++++++++
 4 files changed, 175 insertions(+), 112 deletions(-)
 create mode 100755 tools/testing/selftests/net/xfrm_policy_add_speed.sh

Comments

Steffen Klassert Aug. 27, 2024, 8:55 a.m. UTC | #1

On Thu, Aug 22, 2024 at 03:04:28PM +0200, Florian Westphal wrote:
> Policy insertions do not scale well, due to both a lienar list walk
> to find the insertion spot and another list walk to set the 'pos' value
> (a tie-breaker to detect which policy is older when there is ambiguity
>  as to which one should be matched).
> 
> First patch gets rid of the second list walk on insert.
> Rest of the patches get rid of the insertion walk.
> 
> This list walk was only needed because when I moved the policy db
> implementation to rbtree I retained the old insertion method for the
> sake of XFRM_MIGRATE.
> 
> Switching that to tree-based lookup avoids the need for the full
> list search.
> 
> After this, insertion of a policy is largely independent of the number
> of pre-existing policies as long as they do not share the same source/
> destination networks.
> 
> Note that this is compile tested only as I did not find any
> tests for XFRM_MIGRATE.
> 
> Florian Westphal (4):
>   selftests: add xfrm policy insertion speed test script
>   xfrm: policy: don't iterate inexact policies twice at insert time
>   xfrm: switch migrate to xfrm_policy_lookup_bytype
>   xfrm: policy: remove remaining use of inexact list

Applied, thanks a lot Florian!