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

[Florian Westphal <fw@strlen.de>]

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

-- 
2.44.2