Setup trace points, add a new ftrace instance in order to not interfere with the rest of the system, filtering by net namespace cookies. Raise a new background thread that parses trace_pipe, matches them with the list of expected events. Wiring up trace events to selftests provides another insight if there is anything unexpected happining in the tcp-ao code (i.e. key rotation when it's not expected). Note: in real programs libtraceevent should be used instead of this manual labor of setting ftrace up and parsing. I'm not using it here as I don't want to have an .so library dependency that one would have to bring into VM or DUT (Device Under Test). Please, don't copy it over into any real world programs, that aren't tests. Signed-off-by: Dmitry Safonov <0x7f454c46@gmail.com> Link: https://patch.msgid.link/20240823-tcp-ao-selftests-upd-6-12-v4-8-05623636fe8c@gmail.com Signed-off-by: Jakub Kicinski <kuba@kernel.org>
Centralize the _GNU_SOURCE definition to CFLAGS in lib.mk. Remove redundant defines from Makefiles that import lib.mk. Convert any usage of "#define _GNU_SOURCE 1" to "#define _GNU_SOURCE". This uses the form "-D_GNU_SOURCE=", which is equivalent to "#define _GNU_SOURCE". Otherwise using "-D_GNU_SOURCE" is equivalent to "-D_GNU_SOURCE=1" and "#define _GNU_SOURCE 1", which is less commonly seen in source code and would require many changes in selftests to avoid redefinition warnings. Link: https://lkml.kernel.org/r/20240625223454.1586259-2-edliaw@google.com Signed-off-by: Edward Liaw <edliaw@google.com> Suggested-by: John Hubbard <jhubbard@nvidia.com> Acked-by: Shuah Khan <skhan@linuxfoundation.org> Reviewed-by: Muhammad Usama Anjum <usama.anjum@collabora.com> Cc: Albert Ou <aou@eecs.berkeley.edu> Cc: André Almeida <andrealmeid@igalia.com> Cc: Darren Hart <dvhart@infradead.org> Cc: Dave Hansen <dave.hansen@linux.intel.com> Cc: Davidlohr Bueso <dave@stgolabs.net> Cc: David S. Miller <davem@davemloft.net> Cc: Eric Dumazet <edumazet@google.com> Cc: Eric W. Biederman <ebiederm@xmission.com> Cc: Fenghua Yu <fenghua.yu@intel.com> Cc: Ingo Molnar <mingo@redhat.com> Cc: Jakub Kicinski <kuba@kernel.org> Cc: Jarkko Sakkinen <jarkko@kernel.org> Cc: Jason Gunthorpe <jgg@ziepe.ca> Cc: Kees Cook <kees@kernel.org> Cc: Kevin Tian <kevin.tian@intel.com> Cc: Palmer Dabbelt <palmer@dabbelt.com> Cc: Paolo Abeni <pabeni@redhat.com> Cc: Paolo Bonzini <pbonzini@redhat.com> Cc: Paul Walmsley <paul.walmsley@sifive.com> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Reinette Chatre <reinette.chatre@intel.com> Cc: Sean Christopherson <seanjc@google.com> Cc: Thomas Gleixner <tglx@linutronix.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
The rules to link selftests are:
> $(OUTPUT)/%_ipv4: %.c
> $(LINK.c) $^ $(LDLIBS) -o $@
>
> $(OUTPUT)/%_ipv6: %.c
> $(LINK.c) -DIPV6_TEST $^ $(LDLIBS) -o $@
The intel test robot uses only selftest's Makefile, not the top linux
Makefile:
> make W=1 O=/tmp/kselftest -C tools/testing/selftests
So, $(LINK.c) is determined by environment, rather than by kernel
Makefiles. On my machine (as well as other people that ran tcp-ao
selftests) GNU/Make implicit definition does use $(LDFLAGS):
> [dima@Mindolluin ~]$ make -p -f/dev/null | grep '^LINK.c\>'
> make: *** No targets. Stop.
> LINK.c = $(CC) $(CFLAGS) $(CPPFLAGS) $(LDFLAGS) $(TARGET_ARCH)
But, according to build robot report, it's not the case for them.
While I could just avoid using pre-defined $(LINK.c), it's also used by
selftests/lib.mk by default.
Anyways, according to GNU/Make documentation [1], I should have used
$(LDLIBS) instead of $(LDFLAGS) in the first place, so let's just do it:
> LDFLAGS
> Extra flags to give to compilers when they are supposed to invoke
> the linker, ‘ld’, such as -L. Libraries (-lfoo) should be added
> to the LDLIBS variable instead.
> LDLIBS
> Library flags or names given to compilers when they are supposed
> to invoke the linker, ‘ld’. LOADLIBES is a deprecated (but still
> supported) alternative to LDLIBS. Non-library linker flags, such
> as -L, should go in the LDFLAGS variable.
[1]: https://www.gnu.org/software/make/manual/html_node/Implicit-Variables.html
Fixes: cfbab37b3da0 ("selftests/net: Add TCP-AO library")
Reported-by: kernel test robot <lkp@intel.com>
Closes: https://lore.kernel.org/oe-kbuild-all/202401011151.veyYTJzq-lkp@intel.com/
Signed-off-by: Dmitry Safonov <dima@arista.com>
Acked-by: Paolo Abeni <pabeni@redhat.com>
Link: https://lore.kernel.org/r/20240110-tcp_ao-selftests-makefile-v1-1-aa07d043f052@arista.com
Signed-off-by: Jakub Kicinski <kuba@kernel.org>
Trivial fix for out-of-tree build that I wasn't testing previously:
1. Create a directory for library object files, fixes:
> gcc lib/kconfig.c -Wall -O2 -g -D_GNU_SOURCE -fno-strict-aliasing -I ../../../../../usr/include/ -iquote /tmp/kselftest/kselftest/net/tcp_ao/lib -I ../../../../include/ -o /tmp/kselftest/kselftest/net/tcp_ao/lib/kconfig.o -c
> Assembler messages:
> Fatal error: can't create /tmp/kselftest/kselftest/net/tcp_ao/lib/kconfig.o: No such file or directory
> make[1]: *** [Makefile:46: /tmp/kselftest/kselftest/net/tcp_ao/lib/kconfig.o] Error 1
2. Include $(KHDR_INCLUDES) that's exported by selftests/Makefile, fixes:
> In file included from lib/kconfig.c:6:
> lib/aolib.h:320:45: warning: ‘struct tcp_ao_add’ declared inside parameter list will not be visible outside of this definition or declaration
> 320 | extern int test_prepare_key_sockaddr(struct tcp_ao_add *ao, const char *alg,
> | ^~~~~~~~~~
...
3. While at here, clean-up $(KSFT_KHDR_INSTALL): it's not needed anymore
since commit f2745dc0ba3d ("selftests: stop using KSFT_KHDR_INSTALL")
4. Also, while at here, drop .DEFAULT_GOAL definition: that has a
self-explaining comment, that was valid when I made these selftests
compile on local v4.19 kernel, but not needed since
commit 8ce72dc32578 ("selftests: fix headers_install circular dependency")
Fixes: cfbab37b3da0 ("selftests/net: Add TCP-AO library")
Reported-by: kernel test robot <lkp@intel.com>
Closes: https://lore.kernel.org/oe-kbuild-all/202312190645.q76MmHyq-lkp@intel.com/
Signed-off-by: Dmitry Safonov <dima@arista.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
Check multiple keys on a socket: - rotation on closed socket - current/rnext operations shouldn't be possible on listen sockets - current/rnext key set should be the one, that's used on connect() - key rotations with pseudo-random generated keys - copying matching keys on connect() and on accept() At this moment there are 3 tests that are "expected" to fail: a kernel fix is needed to improve the situation, they are marked XFAIL. Sample output: > # ./key-management_ipv4 > 1..120 > # 1601[lib/setup.c:239] rand seed 1700526653 > TAP version 13 > ok 1 closed socket, delete a key: the key was deleted > ok 2 closed socket, delete all keys: the key was deleted > ok 3 closed socket, delete current key: key deletion was prevented > ok 4 closed socket, delete rnext key: key deletion was prevented > ok 5 closed socket, delete a key + set current/rnext: the key was deleted > ok 6 closed socket, force-delete current key: the key was deleted > ok 7 closed socket, force-delete rnext key: the key was deleted > ok 8 closed socket, delete current+rnext key: key deletion was prevented > ok 9 closed socket, add + change current key > ok 10 closed socket, add + change rnext key > ok 11 listen socket, delete a key: the key was deleted > ok 12 listen socket, delete all keys: the key was deleted > ok 13 listen socket, setting current key not allowed > ok 14 listen socket, setting rnext key not allowed > ok 15 # XFAIL listen() after current/rnext keys set: the socket has current/rnext keys: 100:200 > ok 16 # XFAIL listen socket, delete current key from before listen(): failed to delete the key 100:100 -16 > ok 17 # XFAIL listen socket, delete rnext key from before listen(): failed to delete the key 200:200 -16 > ok 18 listen socket, getsockopt(TCP_AO_REPAIR) is restricted > ok 19 listen socket, setsockopt(TCP_AO_REPAIR) is restricted > ok 20 listen socket, delete a key + set current/rnext: key deletion was prevented > ok 21 listen socket, force-delete current key: key deletion was prevented > ok 22 listen socket, force-delete rnext key: key deletion was prevented > ok 23 listen socket, delete a key: the key was deleted > ok 24 listen socket, add + change current key > ok 25 listen socket, add + change rnext key > ok 26 server: Check current/rnext keys unset before connect(): The socket keys are consistent with the expectations > ok 27 client: Check current/rnext keys unset before connect(): current key 19 as expected > ok 28 client: Check current/rnext keys unset before connect(): rnext key 146 as expected > ok 29 server: Check current/rnext keys unset before connect(): server alive > ok 30 server: Check current/rnext keys unset before connect(): passed counters checks > ok 31 client: Check current/rnext keys unset before connect(): The socket keys are consistent with the expectations > ok 32 server: Check current/rnext keys unset before connect(): The socket keys are consistent with the expectations > ok 33 server: Check current/rnext keys unset before connect(): passed counters checks > ok 34 client: Check current/rnext keys unset before connect(): passed counters checks > ok 35 server: Check current/rnext keys set before connect(): The socket keys are consistent with the expectations > ok 36 server: Check current/rnext keys set before connect(): server alive > ok 37 server: Check current/rnext keys set before connect(): passed counters checks > ok 38 client: Check current/rnext keys set before connect(): current key 10 as expected > ok 39 client: Check current/rnext keys set before connect(): rnext key 137 as expected > ok 40 server: Check current/rnext keys set before connect(): The socket keys are consistent with the expectations > ok 41 client: Check current/rnext keys set before connect(): The socket keys are consistent with the expectations > ok 42 client: Check current/rnext keys set before connect(): passed counters checks > ok 43 server: Check current/rnext keys set before connect(): passed counters checks > ok 44 server: Check current != rnext keys set before connect(): The socket keys are consistent with the expectations > ok 45 server: Check current != rnext keys set before connect(): server alive > ok 46 server: Check current != rnext keys set before connect(): passed counters checks > ok 47 client: Check current != rnext keys set before connect(): current key 10 as expected > ok 48 client: Check current != rnext keys set before connect(): rnext key 132 as expected > ok 49 server: Check current != rnext keys set before connect(): The socket keys are consistent with the expectations > ok 50 client: Check current != rnext keys set before connect(): The socket keys are consistent with the expectations > ok 51 client: Check current != rnext keys set before connect(): passed counters checks > ok 52 server: Check current != rnext keys set before connect(): passed counters checks > ok 53 server: Check current flapping back on peer's RnextKey request: The socket keys are consistent with the expectations > ok 54 server: Check current flapping back on peer's RnextKey request: server alive > ok 55 server: Check current flapping back on peer's RnextKey request: passed counters checks > ok 56 client: Check current flapping back on peer's RnextKey request: current key 10 as expected > ok 57 client: Check current flapping back on peer's RnextKey request: rnext key 132 as expected > ok 58 server: Check current flapping back on peer's RnextKey request: The socket keys are consistent with the expectations > ok 59 client: Check current flapping back on peer's RnextKey request: The socket keys are consistent with the expectations > ok 60 server: Check current flapping back on peer's RnextKey request: passed counters checks > ok 61 client: Check current flapping back on peer's RnextKey request: passed counters checks > ok 62 server: Rotate over all different keys: The socket keys are consistent with the expectations > ok 63 server: Rotate over all different keys: server alive > ok 64 server: Rotate over all different keys: passed counters checks > ok 65 server: Rotate over all different keys: current key 128 as expected > ok 66 client: Rotate over all different keys: rnext key 128 as expected > ok 67 server: Rotate over all different keys: current key 129 as expected > ok 68 client: Rotate over all different keys: rnext key 129 as expected > ok 69 server: Rotate over all different keys: current key 130 as expected > ok 70 client: Rotate over all different keys: rnext key 130 as expected > ok 71 server: Rotate over all different keys: current key 131 as expected > ok 72 client: Rotate over all different keys: rnext key 131 as expected > ok 73 server: Rotate over all different keys: current key 132 as expected > ok 74 client: Rotate over all different keys: rnext key 132 as expected > ok 75 server: Rotate over all different keys: current key 133 as expected > ok 76 client: Rotate over all different keys: rnext key 133 as expected > ok 77 server: Rotate over all different keys: current key 134 as expected > ok 78 client: Rotate over all different keys: rnext key 134 as expected > ok 79 server: Rotate over all different keys: current key 135 as expected > ok 80 client: Rotate over all different keys: rnext key 135 as expected > ok 81 server: Rotate over all different keys: current key 136 as expected > ok 82 client: Rotate over all different keys: rnext key 136 as expected > ok 83 server: Rotate over all different keys: current key 137 as expected > ok 84 client: Rotate over all different keys: rnext key 137 as expected > ok 85 server: Rotate over all different keys: current key 138 as expected > ok 86 client: Rotate over all different keys: rnext key 138 as expected > ok 87 server: Rotate over all different keys: current key 139 as expected > ok 88 client: Rotate over all different keys: rnext key 139 as expected > ok 89 server: Rotate over all different keys: current key 140 as expected > ok 90 client: Rotate over all different keys: rnext key 140 as expected > ok 91 server: Rotate over all different keys: current key 141 as expected > ok 92 client: Rotate over all different keys: rnext key 141 as expected > ok 93 server: Rotate over all different keys: current key 142 as expected > ok 94 client: Rotate over all different keys: rnext key 142 as expected > ok 95 server: Rotate over all different keys: current key 143 as expected > ok 96 client: Rotate over all different keys: rnext key 143 as expected > ok 97 server: Rotate over all different keys: current key 144 as expected > ok 98 client: Rotate over all different keys: rnext key 144 as expected > ok 99 server: Rotate over all different keys: current key 145 as expected > ok 100 client: Rotate over all different keys: rnext key 145 as expected > ok 101 server: Rotate over all different keys: current key 146 as expected > ok 102 client: Rotate over all different keys: rnext key 146 as expected > ok 103 server: Rotate over all different keys: current key 127 as expected > ok 104 client: Rotate over all different keys: rnext key 127 as expected > ok 105 client: Rotate over all different keys: current key 0 as expected > ok 106 client: Rotate over all different keys: rnext key 127 as expected > ok 107 server: Rotate over all different keys: The socket keys are consistent with the expectations > ok 108 client: Rotate over all different keys: The socket keys are consistent with the expectations > ok 109 client: Rotate over all different keys: passed counters checks > ok 110 server: Rotate over all different keys: passed counters checks > ok 111 server: Check accept() => established key matching: The socket keys are consistent with the expectations > ok 112 Can't add a key with non-matching ip-address for established sk > ok 113 Can't add a key with non-matching VRF for established sk > ok 114 server: Check accept() => established key matching: server alive > ok 115 server: Check accept() => established key matching: passed counters checks > ok 116 client: Check connect() => established key matching: current key 0 as expected > ok 117 client: Check connect() => established key matching: rnext key 128 as expected > ok 118 client: Check connect() => established key matching: The socket keys are consistent with the expectations > ok 119 server: Check accept() => established key matching: The socket keys are consistent with the expectations > ok 120 server: Check accept() => established key matching: passed counters checks > # Totals: pass:120 fail:0 xfail:0 xpass:0 skip:0 error:0 Signed-off-by: Dmitry Safonov <dima@arista.com> Signed-off-by: David S. Miller <davem@davemloft.net>
Check that a rare functionality of TCP named self-connect works with TCP-AO. This "under the cover" also checks TCP simultaneous connect (TCP_SYN_RECV socket state), which would be harder to check other ways. In order to verify that it's indeed TCP simultaneous connect, check the counters TCPChallengeACK and TCPSYNChallenge. Sample of the output: > # ./self-connect_ipv6 > 1..4 > # 1738[lib/setup.c:254] rand seed 1696451931 > TAP version 13 > ok 1 self-connect(same keyids): connect TCPAOGood 0 => 24 > ok 2 self-connect(different keyids): connect TCPAOGood 26 => 50 > ok 3 self-connect(restore): connect TCPAOGood 52 => 97 > ok 4 self-connect(restore, different keyids): connect TCPAOGood 99 => 144 > # Totals: pass:4 fail:0 xfail:0 xpass:0 skip:0 error:0 Signed-off-by: Dmitry Safonov <dima@arista.com> Signed-off-by: David S. Miller <davem@davemloft.net>
Check that both active and passive reset works and correctly sign
segments with TCP-AO or don't send RSTs if not possible to sign.
A listening socket with backlog = 0 gets one connection in accept
queue, another in syn queue. Once the server/listener socket is
forcibly closed, client sockets aren't connected to anything.
In regular situation they would receive RST on any segment, but
with TCP-AO as there's no listener, no AO-key and unknown ISNs,
no RST should be sent.
And "passive" reset, where RST is sent on reply for some segment
(tcp_v{4,6}_send_reset()) - there use TCP_REPAIR to corrupt SEQ numbers,
which later results in TCP-AO signed RST, which will be verified and
client socket will get EPIPE.
No TCPAORequired/TCPAOBad segments are expected during these tests.
Sample of the output:
> # ./rst_ipv4
> 1..15
> # 1462[lib/setup.c:254] rand seed 1686611171
> TAP version 13
> ok 1 servered 1000 bytes
> ok 2 Verified established tcp connection
> ok 3 sk[0] = 7, connection was reset
> ok 4 sk[1] = 8, connection was reset
> ok 5 sk[2] = 9
> ok 6 MKT counters are good on server
> ok 7 Verified established tcp connection
> ok 8 client connection broken post-seq-adjust
> ok 9 client connection was reset
> ok 10 No segments without AO sign (server)
> ok 11 Signed AO segments (server): 0 => 30
> ok 12 No segments with bad AO sign (server)
> ok 13 No segments without AO sign (client)
> ok 14 Signed AO segments (client): 0 => 30
> ok 15 No segments with bad AO sign (client)
> # Totals: pass:15 fail:0 xfail:0 xpass:0 skip:0 error:0
Signed-off-by: Dmitry Safonov <dima@arista.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
Check that on SEQ number wraparound there is no disruption or TCPAOBad segments produced. Sample of expected output: > # ./seq-ext_ipv4 > 1..7 > # 1436[lib/setup.c:254] rand seed 1686611079 > TAP version 13 > ok 1 server alive > ok 2 post-migrate connection alive > ok 3 TCPAOGood counter increased 1002 => 3002 > ok 4 TCPAOGood counter increased 1003 => 3003 > ok 5 TCPAOBad counter didn't increase > ok 6 TCPAOBad counter didn't increase > ok 7 SEQ extension incremented: 1/1999, 1/998999 > # Totals: pass:7 fail:0 xfail:0 xpass:0 skip:0 error:0 Signed-off-by: Dmitry Safonov <dima@arista.com> Signed-off-by: David S. Miller <davem@davemloft.net>
The test plan is: 1. check that TCP-AO connection may be restored on another socket 2. check restore with wrong send/recv ISN (checking that they are part of MAC generation) 3. check restore with wrong SEQ number extension (checking that high bytes of it taken into MAC generation) Sample output expected: > # ./restore_ipv4 > 1..20 > # 1412[lib/setup.c:254] rand seed 1686610825 > TAP version 13 > ok 1 TCP-AO migrate to another socket: server alive > ok 2 TCP-AO migrate to another socket: post-migrate connection is alive > ok 3 TCP-AO migrate to another socket: counter TCPAOGood increased 23 => 44 > ok 4 TCP-AO migrate to another socket: counter TCPAOGood increased 22 => 42 > ok 5 TCP-AO with wrong send ISN: server couldn't serve > ok 6 TCP-AO with wrong send ISN: post-migrate connection is broken > ok 7 TCP-AO with wrong send ISN: counter TCPAOBad increased 0 => 4 > ok 8 TCP-AO with wrong send ISN: counter TCPAOBad increased 0 => 3 > ok 9 TCP-AO with wrong receive ISN: server couldn't serve > ok 10 TCP-AO with wrong receive ISN: post-migrate connection is broken > ok 11 TCP-AO with wrong receive ISN: counter TCPAOBad increased 4 => 8 > ok 12 TCP-AO with wrong receive ISN: counter TCPAOBad increased 5 => 10 > ok 13 TCP-AO with wrong send SEQ ext number: server couldn't serve > ok 14 TCP-AO with wrong send SEQ ext number: post-migrate connection is broken > ok 15 TCP-AO with wrong send SEQ ext number: counter TCPAOBad increased 9 => 10 > ok 16 TCP-AO with wrong send SEQ ext number: counter TCPAOBad increased 11 => 19 > ok 17 TCP-AO with wrong receive SEQ ext number: post-migrate connection is broken > ok 18 TCP-AO with wrong receive SEQ ext number: server couldn't serve > ok 19 TCP-AO with wrong receive SEQ ext number: counter TCPAOBad increased 10 => 18 > ok 20 TCP-AO with wrong receive SEQ ext number: counter TCPAOBad increased 20 => 23 > # Totals: pass:20 fail:0 xfail:0 xpass:0 skip:0 error:0 Signed-off-by: Dmitry Safonov <dima@arista.com> Signed-off-by: David S. Miller <davem@davemloft.net>
Sample output: > 1..36 > # 1106[lib/setup.c:207] rand seed 1660754406 > TAP version 13 > ok 1 Worst case connect 512 keys: min=0ms max=1ms mean=0.583329ms stddev=0.076376 > ok 2 Connect random-search 512 keys: min=0ms max=1ms mean=0.53412ms stddev=0.0516779 > ok 3 Worst case delete 512 keys: min=2ms max=11ms mean=6.04139ms stddev=0.245792 > ok 4 Add a new key 512 keys: min=0ms max=13ms mean=0.673415ms stddev=0.0820618 > ok 5 Remove random-search 512 keys: min=5ms max=9ms mean=6.65969ms stddev=0.258064 > ok 6 Remove async 512 keys: min=0ms max=0ms mean=0.041825ms stddev=0.0204512 > ok 7 Worst case connect 1024 keys: min=0ms max=2ms mean=0.520357ms stddev=0.0721358 > ok 8 Connect random-search 1024 keys: min=0ms max=2ms mean=0.535312ms stddev=0.0517355 > ok 9 Worst case delete 1024 keys: min=5ms max=9ms mean=8.27219ms stddev=0.287614 > ok 10 Add a new key 1024 keys: min=0ms max=1ms mean=0.688121ms stddev=0.0829531 > ok 11 Remove random-search 1024 keys: min=5ms max=9ms mean=8.37649ms stddev=0.289422 > ok 12 Remove async 1024 keys: min=0ms max=0ms mean=0.0457096ms stddev=0.0213798 > ok 13 Worst case connect 2048 keys: min=0ms max=2ms mean=0.748804ms stddev=0.0865335 > ok 14 Connect random-search 2048 keys: min=0ms max=2ms mean=0.782993ms stddev=0.0625697 > ok 15 Worst case delete 2048 keys: min=5ms max=10ms mean=8.23106ms stddev=0.286898 > ok 16 Add a new key 2048 keys: min=0ms max=1ms mean=0.812988ms stddev=0.0901658 > ok 17 Remove random-search 2048 keys: min=8ms max=9ms mean=8.84949ms stddev=0.297481 > ok 18 Remove async 2048 keys: min=0ms max=0ms mean=0.0297223ms stddev=0.0172402 > ok 19 Worst case connect 4096 keys: min=1ms max=5ms mean=1.53352ms stddev=0.123836 > ok 20 Connect random-search 4096 keys: min=1ms max=5ms mean=1.52226ms stddev=0.0872429 > ok 21 Worst case delete 4096 keys: min=5ms max=9ms mean=8.25874ms stddev=0.28738 > ok 22 Add a new key 4096 keys: min=0ms max=3ms mean=1.67382ms stddev=0.129376 > ok 23 Remove random-search 4096 keys: min=5ms max=10ms mean=8.26178ms stddev=0.287433 > ok 24 Remove async 4096 keys: min=0ms max=0ms mean=0.0340009ms stddev=0.0184393 > ok 25 Worst case connect 8192 keys: min=2ms max=4ms mean=2.86208ms stddev=0.169177 > ok 26 Connect random-search 8192 keys: min=2ms max=4ms mean=2.87592ms stddev=0.119915 > ok 27 Worst case delete 8192 keys: min=6ms max=11ms mean=7.55291ms stddev=0.274826 > ok 28 Add a new key 8192 keys: min=1ms max=5ms mean=2.56797ms stddev=0.160249 > ok 29 Remove random-search 8192 keys: min=5ms max=10ms mean=7.14002ms stddev=0.267208 > ok 30 Remove async 8192 keys: min=0ms max=0ms mean=0.0320066ms stddev=0.0178904 > ok 31 Worst case connect 16384 keys: min=5ms max=6ms mean=5.55334ms stddev=0.235655 > ok 32 Connect random-search 16384 keys: min=5ms max=6ms mean=5.52614ms stddev=0.166225 > ok 33 Worst case delete 16384 keys: min=5ms max=11ms mean=7.39109ms stddev=0.271866 > ok 34 Add a new key 16384 keys: min=2ms max=4ms mean=3.35799ms stddev=0.183248 > ok 35 Remove random-search 16384 keys: min=5ms max=8ms mean=6.86078ms stddev=0.261931 > ok 36 Remove async 16384 keys: min=0ms max=0ms mean=0.0302384ms stddev=0.0173892 > # Totals: pass:36 fail:0 xfail:0 xpass:0 skip:0 error:0 >From the output it's visible that the current simplified approach with linked-list of MKTs scales quite fine even for thousands of keys. And that also means that the majority of the time for delete is eaten by synchronize_rcu() [which I can confirm separately by tracing]. Signed-off-by: Dmitry Safonov <dima@arista.com> Signed-off-by: David S. Miller <davem@davemloft.net>